EDEN: Efficient Decoding Methods for Language Models on Encrypted Data

Abstract

Inference with large language models (LLMs) over encrypted data promises strong confidentiality for user inputs, intermediate features, and outputs, yet the decoding loop remains the bottleneck for practicality[1]. Even if one assumes the existence of an upstream mechanism that produces logits under privacy-preserving computation—via homomorphic encryption (HE), secure multiparty computation (MPC), functional encryp- tion, or trusted execution—the act of turning a large, encrypted logit vector into the next token by sampling or search typically requires operations that are ill-suited to privacy-preserving substrates: softmax normalization is nonlinear and numerically sensitive; top-k and nucleus filtering involve comparisons and conditional pruning over vocabularies with V ≈ 105; and sampling demands generation of high-quality randomness and inverse-CDF selections without revealing intermediate structure. Naïvely porting plaintext decoders either leaks through access patterns and partial revelations or incurs prohibitive latency through deep Boolean circuits or high-degree polynomial ap- proximations. This paper presents EDEN, a family of decoding methods that preserves statistical fidelity while substantially reducing cryptographic and communication overhead.