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 it converges globally to a unique two-level fixed point, independent of the input values beyond the identity of the maximizer, which explains its rapid convergence in just a few iterations. Evaluations on realistic LLM outputs show latency reductions of 24x-35x over baselines, advancing secure text generation.
Abstract (translated)
大型语言模型（LLMs）是现代人工智能应用的核心，但在不可信的服务器上处理敏感数据引发了隐私问题。同态加密（HE）可以在不解密的情况下对加密的数据进行计算，从而实现安全推理。然而，神经文本生成需要使用argmax和采样这样的解码方法，这些方法是非多项式的，并且在加密条件下运行时计算成本高昂，这成为了性能瓶颈的主要原因。 我们提出了cutmax算法，这是一种与同态加密兼容的argmax算法，相比以前的方法减少了密文操作次数，从而支持了实际情况下基于加密环境下的贪婪解码。此外，我们也提出了一种新颖的HE兼容核采样（top-p）方法，利用cutmax实现高效的随机解码，并具有可证明的隐私保证。 这两种技术都是多项式的，因此能够在保护隐私的同时高效地进行推理。它们的可微性还支持基于梯度序列级别的优化作为直通估算器的多项式替代方案。 此外，我们对cutmax算法提供了强大的理论保障，证明其能够全局收敛到一个独立于输入值（除了最大化的身份）的独特两级固定点，这解释了它只需要几次迭代就可以快速收敛的原因。在针对现实LLM输出进行评估时发现，与基准方法相比，延迟减少了24-35倍，推动了安全文本生成的发展。
URL
https://arxiv.org/abs/2509.08383
