Traveling Salesman-Based Token Ordering Improves Stability in Homomorphically Encrypted Language Models
This work addresses the problem of secure and practical encrypted interaction for users of large language models, representing an incremental improvement in a specific domain.
The paper tackled the challenge of text generation in homomorphically encrypted language models by proposing a traveling salesman-based token reordering strategy, which prevented collapse and improved coherence in generated text while preserving data privacy.
As users increasingly interact with large language models (LLMs) using private information, secure and encrypted communication becomes essential. Homomorphic encryption (HE) provides a principled solution by enabling computation directly on encrypted data. Although prior work has explored aspects of running LLMs under HE, the challenge of text generation, particularly next-token prediction, has received limited attention and remains a key obstacle to practical encrypted interaction. In this work, we propose a TSP-based token reordering strategy to address the difficulties of encrypted text generation, together with a post-processing step that further reduces approximation error. Theoretical analysis and experimental results demonstrate that our method prevents collapse, improves coherence in generated text, and preserves data privacy throughout. Overall, our contributions advance the feasibility of practical and privacy-preserving LLM inference.