# Traveling Salesman-Based Token Ordering Improves Stability in Homomorphically Encrypted Language Models

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 48 references that are in the map.
- First posted on arXiv 14 Oct 2025.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [DeBERTa: Decoding-enhanced BERT with Disentangled Attention](https://mlsanity.com/paper/2006.03654/) (2020)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [Generating Sequences With Recurrent Neural Networks](https://mlsanity.com/paper/1308.0850/) (2013)
- [Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models](https://mlsanity.com/paper/1610.02424/) (2016)
- [Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs](https://mlsanity.com/paper/2407.01082/) (2024)
- [Locally Typical Sampling](https://mlsanity.com/paper/2202.00666/) (2022)
- [Precise Approximation of Convolutional Neural Networks for Homomorphically Encrypted Data](https://mlsanity.com/paper/2105.10879/) (2021)
- [Encryption-Friendly LLM Architecture](https://mlsanity.com/paper/2410.02486/) (2024)
- [HETAL: Efficient Privacy-preserving Transfer Learning with Homomorphic Encryption](https://mlsanity.com/paper/2403.14111/) (2024)
- [Fidelity-Enriched Contrastive Search: Reconciling the Faithfulness-Diversity Trade-Off in Text Generation](https://mlsanity.com/paper/2310.14981/) (2023)
- [Private and Reliable Neural Network Inference](https://mlsanity.com/paper/2210.15614/) (2022)
- [Efficient Decoding Methods for Language Models on Encrypted Data](https://mlsanity.com/paper/2509.08383/) (2025)
- [Fast and Accurate Homomorphic Softmax Evaluation](https://mlsanity.com/paper/2410.11184/) (2024)

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

- [Static Bootstrap Placement for Encrypted Language Model Decoding](https://mlsanity.com/paper/2610.04912/) (2026)

## Abstract (arXiv)

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.