# Fundamental Limits of Prompt Compression: A Rate-Distortion Framework for Black-Box Language Models

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Placed in Prompt and context compression, one of 12 directions in Efficient LLM inference and serving.
- Builds on 28 of its 52 references that are in the map.
- First posted on arXiv 22 Jul 2024.

## Placed in

- Efficient LLM inference and serving / [Prompt and context compression](https://mlsanity.com/inference/prompt-and-context-compression/)

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [BERTScore: Evaluating Text Generation with BERT](https://mlsanity.com/paper/1904.09675/) (2019)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling](https://mlsanity.com/paper/2304.01373/) (2023)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [A General Language Assistant as a Laboratory for Alignment](https://mlsanity.com/paper/2112.00861/) (2021)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [The NarrativeQA Reading Comprehension Challenge](https://mlsanity.com/paper/1712.07040/) (2017)
- [LongLLMLingua: Accelerating and Enhancing LLMs in Long Context Scenarios via Prompt Compression](https://mlsanity.com/paper/2310.06839/) (2023)
- [Learning to Compress Prompts with Gist Tokens](https://mlsanity.com/paper/2304.08467/) (2023)
- [Adapting Language Models to Compress Contexts](https://mlsanity.com/paper/2305.14788/) (2023)
- [LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression](https://mlsanity.com/paper/2403.12968/) (2024)
- [LLMLingua: Compressing Prompts for Accelerated Inference of Large Language Models](https://mlsanity.com/paper/2310.05736/) (2023)
- [In-context Autoencoder for Context Compression in a Large Language Model](https://mlsanity.com/paper/2307.06945/) (2023)
- [Compressing Context to Enhance Inference Efficiency of Large Language Models](https://mlsanity.com/paper/2310.06201/) (2023)
- [Prompt Compression and Contrastive Conditioning for Controllability and Toxicity Reduction in Language Models](https://mlsanity.com/paper/2210.03162/) (2022)
- [Discrete Optimization for Unsupervised Sentence Summarization with Word-Level Extraction](https://mlsanity.com/paper/2005.01791/) (2020)
- [Efficient Unsupervised Sentence Compression by Fine-tuning Transformers with Reinforcement Learning](https://mlsanity.com/paper/2205.08221/) (2022)
- [Neural Estimation of the Rate-Distortion Function With Applications to Operational Source Coding](https://mlsanity.com/paper/2204.01612/) (2022)
- [Deleter: Leveraging BERT to Perform Unsupervised Successive Text Compression](https://mlsanity.com/paper/1909.03223/) (2019)
- [Estimating the Rate-Distortion Function by Wasserstein Gradient Descent](https://mlsanity.com/paper/2310.18908/) (2023)

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

- [Understanding and Improving Information Preservation in Prompt Compression for LLMs](https://mlsanity.com/paper/2503.19114/) (2025)
- [Prompt Compression in the Wild: Measuring Latency, Rate Adherence, and Quality for Faster LLM Inference](https://mlsanity.com/paper/2604.02985/) (2026)
- [OSCAR: Online Soft Compression And Reranking](https://mlsanity.com/paper/2504.07109/) (2025)
- [A Rate-Distortion Framework for Summarization](https://mlsanity.com/paper/2501.13100/) (2025)
- [ArcAligner: Adaptive Recursive Aligner for Compressed Context Embeddings in RAG](https://mlsanity.com/paper/2601.05038/) (2026)
- [Reliability-Aware Determinantal Point Processes for Robust Informative Data Selection in Large Language Models](https://mlsanity.com/paper/2602.00885/) (2026)
- [Fixed RAG Compression Collapses Measured Reader Scaling](https://mlsanity.com/paper/2606.21807/) (2026)
- [Cache-Aware Prompt Compression:A Two-Tier Cost Model for LLM API Caching](https://mlsanity.com/paper/2607.15516/) (2026)
- [ADKO: Agentic Decentralized Knowledge Optimization](https://mlsanity.com/paper/2605.07863/) (2026)
- [Dense Contexts Are Hard Contexts: Lexical Density Limits Effective Context in LLMs](https://mlsanity.com/paper/2606.06203/) (2026)
- [Every Time I Hire a Linguist, Inference Costs Go Down: On Linguistic Rules as Effective Prompt Compressors](https://mlsanity.com/paper/2607.25335/) (2026)
- [Relevant but Incomplete: Referential Dangling as a Paradigm-Level Failure Mode in Hard Prompt Compression](https://mlsanity.com/paper/2608.04569/) (2026)
- [Handover of In-Context Learning State Across Session Boundaries](https://mlsanity.com/paper/2608.14528/) (2026)
- [What Does Context Compression Cost an Agent? Interaction Costs Unrevealed by Task-Completion Metrics](https://mlsanity.com/paper/2608.16370/) (2026)
- [MORSE: Multi-Context Ordering via Reverse Scoring for Evidence-Preserving Compression](https://mlsanity.com/paper/2609.27380/) (2026)
- [HasMem: Hard-Origin Adaptively Softened Memory for Long-Term LLM Agents](https://mlsanity.com/paper/2609.30797/) (2026)
- [LAM: Efficient Lossy Agent Memory Framework With A Retrieval-Score Error Bound](https://mlsanity.com/paper/2609.32256/) (2026)
- [Learning from Research: Toward Lifelong Agent Harness Evolution](https://mlsanity.com/paper/2609.40169/) (2026)
- [TPBench: A Turning-Point Benchmark for Dialogue Compression](https://mlsanity.com/paper/2610.02736/) (2026)

## Abstract (arXiv)

We formalize the problem of prompt compression for large language models (LLMs) and present a framework to unify token-level prompt compression methods which create hard prompts for black-box models. We derive the distortion-rate function for this setup as a linear program, and provide an efficient algorithm to compute this fundamental limit via the dual of the linear program. Using the distortion-rate function as the baseline, we study the performance of existing compression schemes on a synthetic dataset consisting of prompts generated from a Markov chain, natural language queries, and their respective answers. Our empirical analysis demonstrates the criticality of query-aware prompt compression, where the compressor has knowledge of the downstream task/query for the black-box LLM. We show that there is a large gap between the performance of current prompt compression methods and the optimal strategy, and propose Adaptive QuerySelect, a query-aware, variable-rate adaptation of a prior work to close the gap. We extend our experiments to a small natural language dataset to further confirm our findings on our synthetic dataset.