# Efficient Decoding Methods for Language Models on Encrypted Data

**Authors:** Matan Avitan, Moran Baruch, Nir Drucker, Itamar Zimerman, Yoav Goldberg  
**arXiv:** [2509.08383](https://arxiv.org/abs/2509.08383)  
**Date:** 2025-09-10  
**Summary page:** https://www.summarizepaper.com/en/paper/2509.08383v1/

## Key points

- Authors: Matan Avitan, Moran Baruch, Nir Drucker, Itamar Zimerman, Yoav Goldberg
- Topic: Efficient Decoding Methods for Language Models on Encrypted Data
- Privacy Concerns: Addressed in processing sensitive data on untrusted servers using large language models (LLMs)
- Homomorphic Encryption (HE): Potential for enabling secure inference on encrypted data
- Cutmax Algorithm: Novel HE-friendly argmax algorithm to reduce computational complexity under encryption
- Nucleus Sampling Method: HE-compatible method leveraging cutmax for efficient stochastic decoding with privacy guarantees
- Benefits: Support efficient inference in privacy-preserving settings and facilitate gradient-based optimization
- Theoretical Guarantees: Strong theoretical guarantees for cutmax with global convergence to a unique fixed point
- Latency Reductions: Significant latency reductions of 24x-35x demonstrated compared to baseline methods

## Summary

In their paper titled "Efficient Decoding Methods for Language Models on Encrypted Data," authors Matan Avitan, Moran Baruch, Nir Drucker, Itamar Zimerman, and Yoav Goldberg address the privacy concerns associated with processing sensitive data on untrusted servers using large language models (LLMs). They highlight the potential of homomorphic encryption (HE) in enabling secure inference on encrypted data. The authors introduce a novel HE-friendly argmax algorithm called cutmax to overcome the non-polynomial and computationally expensive nature of traditional decoding methods under encryption. This reduces the number of ciphertext operations and makes greedy decoding feasible. Additionally, they propose a HE-compatible nucleus (top-p) sampling method that leverages cutmax for efficient stochastic decoding while ensuring provable privacy guarantees. These techniques support efficient inference in privacy-preserving settings and facilitate gradient-based sequence-level optimization as an alternative to straight-through estimators. The authors provide strong theoretical guarantees for cutmax and demonstrate its global convergence to a unique two-level fixed point independent of input values beyond the maximizer's identity. Through evaluations on realistic LLM outputs, significant latency reductions of 24x-35x are demonstrated compared to baseline methods. These contributions advance secure text generation by enabling efficient and secure inference processes in privacy-sensitive applications.