# Efficient Decoding Methods for Language Models on Encrypted Data

arXiv: https://arxiv.org/abs/2509.08383 · HTML: https://mlsanity.com/paper/2509.08383/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 40 references that are in the map.
- First posted on arXiv 10 Sep 2025.

## Builds on (most cited first, 13 of 13)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [A Discourse-Aware Attention Model for Abstractive Summarization of Long Documents](https://mlsanity.com/paper/1804.05685/) (2018)
- [A* Sampling](https://mlsanity.com/paper/1411.0030/) (2014)
- [On Protecting the Data Privacy of Large Language Models (LLMs): A Survey](https://mlsanity.com/paper/2403.05156/) (2024)
- [HeLayers: A Tile Tensors Framework for Large Neural Networks on Encrypted Data](https://mlsanity.com/paper/2011.01805/) (2020)
- [Converting Transformers to Polynomial Form for Secure Inference Over Homomorphic Encryption](https://mlsanity.com/paper/2311.08610/) (2023)
- [A methodology for training homomorphicencryption friendly neural networks](https://mlsanity.com/paper/2111.03362/) (2021)
- [Private and Reliable Neural Network Inference](https://mlsanity.com/paper/2210.15614/) (2022)
- [SPEED: Secure, PrivatE, and Efficient Deep learning](https://mlsanity.com/paper/2006.09475/) (2020)
- [Efficient Ranking, Order Statistics, and Sorting under CKKS](https://mlsanity.com/paper/2412.15126/) (2024)

## Built on by (most cited first, 5 of 5)

- [Traveling Salesman-Based Token Ordering Improves Stability in Homomorphically Encrypted Language Models](https://mlsanity.com/paper/2510.12343/) (2025)
- [HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation](https://mlsanity.com/paper/2609.01730/) (2026)
- [Static Bootstrap Placement for Encrypted Language Model Decoding](https://mlsanity.com/paper/2610.04912/) (2026)
- [HE-OFT: Privacy-Preserving One-Shot Federated Fine-Tuning under Homomorphic Encryption](https://mlsanity.com/paper/2610.08255/) (2026)
- [A Graph-Based Analysis of Comparability, Scale, and Attribution in Private Transformer Inference](https://mlsanity.com/paper/2610.19607/) (2026)

## Abstract (arXiv)

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 24x-35x over baselines, advancing secure text generation.