mlsanityData to 7 Oct 2026

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

arXiv 2407.15504 ↗First posted 22 Jul 2024cs.LG cs.CL cs.ITcited by 18

On the map: Efficient LLM inference and serving → Prompt and context compression

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.

Key facts. Cited by 18 papers in the map (data through 7 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.

Builds on

28 of 52 references.

Closest ancestors · 4

Same direction, newest first

  1. 2024LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression19 Mar
  2. 2023LongLLMLingua: Accelerating and Enhancing LLMs in Long Context Scenarios via Prompt Compression10 Oct
  3. 2023In-context Autoencoder for Context Compression in a Large Language Model13 Jul
  4. 2022Prompt Compression and Contrastive Conditioning for Controllability and Toxicity Reduction in Language Models6 Oct

Other references · 24

  1. 2017Attention Is All You Needcited by 59,932
  2. 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,084
  3. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,266
  4. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  5. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,767
  6. 2019BERTScore: Evaluating Text Generation with BERTcited by 5,462
  7. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
  8. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  9. 2023Lost in the Middle: How Language Models Use Long Contextscited by 3,383
  10. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,551
  11. 2023Pythia: A Suite for Analyzing Large Language Models Across Training and Scalingcited by 1,734
  12. 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
12 more
  1. 2021A General Language Assistant as a Laboratory for Alignmentcited by 1,023
  2. 2023RWKV: Reinventing RNNs for the Transformer Eracited by 814
  3. 2017The NarrativeQA Reading Comprehension Challengecited by 590
  4. 2023Learning to Compress Prompts with Gist Tokenscited by 379
  5. 2023Adapting Language Models to Compress Contextscited by 350
  6. 2023LLMLingua: Compressing Prompts for Accelerated Inference of Large Language Modelscited by 279
  7. 2023Compressing Context to Enhance Inference Efficiency of Large Language Modelscited by 185
  8. 2020Discrete Optimization for Unsupervised Sentence Summarization with Word-Level Extractioncited by 23
  9. 2022Efficient Unsupervised Sentence Compression by Fine-tuning Transformers with Reinforcement Learningcited by 18
  10. 2022Neural Estimation of the Rate-Distortion Function With Applications to Operational Source Codingcited by 9
  11. 2019Deleter: Leveraging BERT to Perform Unsupervised Successive Text Compressioncited by 5
  12. 2023Estimating the Rate-Distortion Function by Wasserstein Gradient Descentcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 15.

18 papers.

Sort:

By area:

  1. 2025Understanding and Improving Information Preservation in Prompt Compression for LLMscited by 13
  2. 2026Prompt Compression in the Wild: Measuring Latency, Rate Adherence, and Quality for Faster LLM Inferencecited by 8
  3. 2025OSCAR: Online Soft Compression And Rerankingcited by 4
  4. 2025A Rate-Distortion Framework for Summarizationcited by 3
  5. 2026ArcAligner: Adaptive Recursive Aligner for Compressed Context Embeddings in RAGcited by 1
  6. 2026Reliability-Aware Determinantal Point Processes for Robust Informative Data Selection in Large Language Modelscited by 1
  7. 2026Fixed RAG Compression Collapses Measured Reader Scalingcited by 1
  8. 2026Cache-Aware Prompt Compression:A Two-Tier Cost Model for LLM API Cachingcited by 1
  9. 2026ADKO: Agentic Decentralized Knowledge Optimizationcited by 0
  10. 2026Dense Contexts Are Hard Contexts: Lexical Density Limits Effective Context in LLMscited by 0
  11. 2026Every Time I Hire a Linguist, Inference Costs Go Down: On Linguistic Rules as Effective Prompt Compressorscited by 0
  12. 2026Relevant but Incomplete: Referential Dangling as a Paradigm-Level Failure Mode in Hard Prompt Compressioncited by 0
6 more
  1. 2026Handover of In-Context Learning State Across Session Boundariescited by 0
  2. 2026What Does Context Compression Cost an Agent? Interaction Costs Unrevealed by Task-Completion Metricscited by 0
  3. 2026MORSE: Multi-Context Ordering via Reverse Scoring for Evidence-Preserving Compressioncited by 0
  4. 2026HasMem: Hard-Origin Adaptively Softened Memory for Long-Term LLM Agentscited by 0
  5. 2026LAM: Efficient Lossy Agent Memory Framework With A Retrieval-Score Error Boundcited by 0
  6. 2026Learning from Research: Toward Lifelong Agent Harness Evolutioncited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Prompt Compression for Large Language Models: A Survey
  2. 2025Dynamic Compressing Prompts for Efficient Inference of Large Language Models
  3. 2024Prompt-SAW: Leveraging Relation-Aware Graphs for Textual Prompt Compression
  4. 2025An Empirical Study on Prompt Compression for Large Language Models
  5. 2025Cmprsr: Abstractive Token-Level Question-Agnostic Prompt Compressor
  6. 2026Lexical Prompt Compression for Large Language Models: A Training-Free, Deterministic Pipeline with Empirical Pareto Analysis Across Eleven Task Categories
  7. 2024LanguaShrink: Reducing Token Overhead with Psycholinguistics
  8. 2024Style-Compress: An LLM-Based Prompt Compression Framework Considering Task-Specific Styles