Efficient Decoding Methods for Language Models on Encrypted Data

Association for Computational Linguistics, Matan Avitan, Moran Baruch, Gilad Ezov, Yoav Goldberg, Itamar ZimermanUnderline 2025 · DOI · OpenAlex

Abstract

Large language models (LLMs) power modern AI applications, but processing sensitive data on untrusted servers raises privacy concerns. Homomorphic encryption (HE) enables computation on encrypted data for secure inference. However, neural text generation requires decoding methods like argmax and sampling, which are non-polynomial and thus computationally expensive under encryption, creating a significant performance bottleneck. We introduce CutMax, an HE-friendly argmax algorithm that reduces ciphertext operations compared to prior methods, enabling practical greedy decoding under encryption. We also propose the first HE-compatible nucleus (top-p) sampling method, leveraging CutMax for efficient stochastic decoding with provable privacy guarantees. Both techniques are polynomial, supporting efficient inference in privacy-preserving settings. Moreover, their differentiability facilitates gradient-based sequence-level optimization as a polynomial alternative to straight-through estimators. We further provide strong theoretical guarantees for CutMax, proving its convergence via exponential amplification of the gap ratio between the maximum and runner-up elements. Evaluations on realistic LLM outputs show latency reductions of $24\times$–$35\times$ over baselines, advancing secure text generation.

Introduction: The Privacy-Performance Bottleneck

When users interact with cloud-based LLMs, their prompts are typically processed in plaintext by the service provider. While Homomorphic Encryption (HE) offers a theoretical path to private inference by allowing computation on encrypted data, it is constrained by the fact that it only natively supports polynomial operations (addition and multiplication).

Standard text generation relies on non-polynomial operations like argmax for greedy decoding and nucleus sampling for stochastic generation. Implementing these via HE has traditionally required thousands of slow, comparison-heavy operations, creating a massive performance bottleneck that makes real-time private text generation impractical.

The private inference pipeline: Client-side encryption and server-side iterative generation using the proposed HE-friendly decoding methods.

Methods: The CutMax Approach

The researchers introduce CutMax, a novel algorithm designed to find the maximum element in an encrypted vector without explicit comparisons. Instead of a tournament-style comparison tree, CutMax uses an iterative "stretching" technique.

In each iteration, the algorithm calculates the mean and variance of the encrypted logits, standardizes them, and raises the values to a high odd power (e.g., $x^{11}$). This process exponentially amplifies the gap between the maximum value and the rest of the distribution. After a few iterations, the distribution effectively becomes a "one-hot" vector where only the maximum element remains significant. This approach is highly efficient in HE because calculating inverse square roots and polynomial powers is computationally "shallower" than approximating the sign functions required for comparisons.

Convergence of the CutMax algorithm over iterations, demonstrating how the maximum element is amplified to the highest quantile.

HE-Friendly Nucleus Sampling

Building on CutMax, the authors developed the first HE-compatible nucleus (top-p) sampling method. This "one-shot" approach adds mathematically calibrated noise (drawn from a Beta distribution) to the encrypted logits before applying CutMax. The noise is designed such that only tokens within the top-p probability mass have a realistic chance of being selected as the maximum, effectively performing complex stochastic sampling through a single argmax call.

Key Results and Performance

The proposed methods were evaluated using models like Mistral-7B and QWEN2.5 across various benchmarks. The results demonstrate a significant leap in efficiency:

  • Speedup: On a Mistral-7B model (32K vocabulary), CutMax reduced decoding latency from ~79 seconds to just 3.37 seconds—a 24x improvement. For larger vocabularies (150K), the speedup reached 35x.
  • Accuracy: Despite being a polynomial approximation, CutMax achieved 100% accuracy in recovering the correct tokens compared to plaintext baselines.
  • Differentiability: Unlike standard argmax, CutMax is fully differentiable. This allows it to be used as a drop-in replacement for non-differentiable operations in gradient-based sequence-level optimization, potentially improving how models are fine-tuned for private environments.

Conclusion

By replacing discrete comparisons with continuous polynomial stretching, CutMax and its associated sampling methods remove one of the primary barriers to private LLM inference. These advancements make secure, encrypted text generation feasible for real-world applications where data privacy is paramount.

Summary updated

Abstract

Large language models (LLMs) power modern AI applications, but processing sensitive data on untrusted servers raises privacy concerns. Homomorphic encryption (HE) enables computation on encrypted data for secure inference. However, neural text generation requires decoding methods like argmax and sampling, which are non-polynomial and thus computationally expensive under encryption, creating a significant performance bottleneck. We introduce cutmax, an HE-friendly argmax algorithm that reduces ciphertext operations compared to prior methods, enabling practical greedy decoding under encryption. We also propose the first HE-compatible nucleus (top-p) sampling method, leveraging cutmax for efficient stochastic decoding with provable privacy guarantees. Both techniques are polynomial, supporting efficient inference in privacy-preserving settings. Moreover, their differentiability facilitates gradient-based sequence-level optimization as a polynomial alternative to straight-through estimators. We further provide strong theoretical guarantees for cutmax, proving its convergence via exponential amplification of the gap ratio between the maximum and runner-up elements. Evaluations on realistic LLM outputs show latency reductions of $24\times$–$35\times$ over baselines, advancing secure text generation.
BibTeX
@inproceedings{linguistics2025efficient,
  author = {Association for Computational Linguistics and Matan Avitan and Moran Baruch and Gilad Ezov and Yoav Goldberg and Itamar Zimerman and Matan Avitan and Yoav Goldberg},
  title = {{Efficient Decoding Methods for Language Models on Encrypted Data}},
  booktitle = {Underline},
  year = {2025},
  doi = {10.48448/5m9b-fb06},
}

Loading related content...

Figure