# No Free Lunch Theorem for Privacy-Preserving LLM Inference

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 35 references that are in the map.
- First posted on arXiv 31 May 2024.

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

- [BERTScore: Evaluating Text Generation with BERT](https://mlsanity.com/paper/1904.09675/) (2019)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Teaching Machines to Read and Comprehend](https://mlsanity.com/paper/1506.03340/) (2015)
- [Neural Text Generation with Unlikelihood Training](https://mlsanity.com/paper/1908.04319/) (2019)
- [Information Leakage in Embedding Models](https://mlsanity.com/paper/2004.00053/) (2020)
- [Text Embeddings Reveal (Almost) As Much As Text](https://mlsanity.com/paper/2310.06816/) (2023)
- [Beyond Memorization: Violating Privacy Via Inference with Large Language Models](https://mlsanity.com/paper/2310.07298/) (2023)
- [Learning to Break the Loop: Analyzing and Mitigating Repetitions for Neural Text Generation](https://mlsanity.com/paper/2206.02369/) (2022)
- [Sentence Embedding Leaks More Information than You Expect: Generative Embedding Inversion Attack to Recover the Whole Sentence](https://mlsanity.com/paper/2305.03010/) (2023)
- [Differential Privacy for Text Analytics via Natural Text Sanitization](https://mlsanity.com/paper/2106.01221/) (2021)
- [Overlearning Reveals Sensitive Attributes](https://mlsanity.com/paper/1905.11742/) (2019)
- [MPCFormer: fast, performant and private Transformer inference with MPC](https://mlsanity.com/paper/2211.01452/) (2022)
- [DP-OPT: Make Large Language Model Your Privacy-Preserving Prompt Engineer](https://mlsanity.com/paper/2312.03724/) (2023)
- [Natural Language Understanding with Privacy-Preserving BERT](https://mlsanity.com/paper/2104.07504/) (2021)
- [PUMA: Secure Inference of LLaMA-7B in Five Minutes](https://mlsanity.com/paper/2307.12533/) (2023)
- [Privacy-Preserving Parameter-Efficient Fine-Tuning for Large Language Model Services](https://mlsanity.com/paper/2305.06212/) (2023)
- [No Free Lunch Theorem for Security and Utility in Federated Learning](https://mlsanity.com/paper/2203.05816/) (2022)
- [Joint Prompt Optimization of Stacked LLMs using Variational Inference](https://mlsanity.com/paper/2306.12509/) (2023)
- [Grounding Foundation Models through Federated Transfer Learning: A General Framework](https://mlsanity.com/paper/2311.17431/) (2023)
- [LLMs Can Understand Encrypted Prompt: Towards Privacy-Computing Friendly Transformers](https://mlsanity.com/paper/2305.18396/) (2023)
- [Primer: Fast Private Transformer Inference on Encrypted Data](https://mlsanity.com/paper/2303.13679/) (2023)
- [InvBERT: Reconstructing Text from Contextualized Word Embeddings by inverting the BERT pipeline](https://mlsanity.com/paper/2109.10104/) (2021)
- [You Don't Know My Favorite Color: Preventing Dialogue Representations from Revealing Speakers' Private Personas](https://mlsanity.com/paper/2205.10228/) (2022)
- [A Split-and-Privatize Framework for Large Language Model Fine-Tuning](https://mlsanity.com/paper/2312.15603/) (2023)
- [East: Efficient and Accurate Secure Transformer Framework for Inference](https://mlsanity.com/paper/2308.09923/) (2023)

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

- [On-Device Language Models: A Comprehensive Review](https://mlsanity.com/paper/2409.00088/) (2024)
- [Ten Challenging Problems in Federated Foundation Models](https://mlsanity.com/paper/2502.12176/) (2025)
- [Taming the Titans: A Survey of Efficient LLM Inference Serving](https://mlsanity.com/paper/2504.19720/) (2025)
- [Privacy-preserved LLM Cascade via CoT-enhanced Policy Learning](https://mlsanity.com/paper/2410.08014/) (2024)
- [LLM Access Shield: Domain-Specific LLM Framework for Privacy Policy Compliance](https://mlsanity.com/paper/2505.17145/) (2025)
- [How Privacy-Savvy Are Large Language Models? A Case Study on Compliance and Privacy Technical Review](https://mlsanity.com/paper/2409.02375/) (2024)
- [Anti-adversarial Learning: Desensitizing Prompts for Large Language Models](https://mlsanity.com/paper/2505.01273/) (2025)
- [Learning Obfuscations Of LLM Embedding Sequences: Stained Glass Transform](https://mlsanity.com/paper/2506.09452/) (2025)
- [Sanitize Your Responses: Mitigating Privacy Leakage in Large Language Models](https://mlsanity.com/paper/2509.24488/) (2025)
- [Preempting Text Sanitization Utility in Resource-Constrained Privacy-Preserving LLM Interactions](https://mlsanity.com/paper/2411.11521/) (2024)
- [When Agents Handle Secrets: A Survey of Confidential Computing for Agentic AI](https://mlsanity.com/paper/2605.03213/) (2026)
- [AI-Model Network: Concept, Current State and Future](https://mlsanity.com/paper/2606.27382/) (2026)
- [SpliTEE: Fast and Private LLM Inference by Coupling GPU-Assisted Trusted Execution Environments with Differential Privacy](https://mlsanity.com/paper/2609.15039/) (2026)

## Abstract (arXiv)

Individuals and businesses have been significantly benefited by Large Language Models (LLMs) including PaLM, Gemini and ChatGPT in various ways. For example, LLMs enhance productivity, reduce costs, and enable us to focus on more valuable tasks. Furthermore, LLMs possess the capacity to sift through extensive datasets, uncover underlying patterns, and furnish critical insights that propel the frontiers of technology and science. However, LLMs also pose privacy concerns. Users' interactions with LLMs may expose their sensitive personal or company information. A lack of robust privacy safeguards and legal frameworks could permit the unwarranted intrusion or improper handling of individual data, thereby risking infringements of privacy and the theft of personal identities. To ensure privacy, it is essential to minimize the dependency between shared prompts and private information. Various randomization approaches have been proposed to protect prompts' privacy, but they may incur utility loss compared to unprotected LLMs prompting. Therefore, it is essential to evaluate the balance between the risk of privacy leakage and loss of utility when conducting effective protection mechanisms. The current study develops a framework for inferring privacy-protected Large Language Models (LLMs) and lays down a solid theoretical basis for examining the interplay between privacy preservation and utility. The core insight is encapsulated within a theorem that is called as the NFL (abbreviation of the word No-Free-Lunch) Theorem.