Research map / Large language models / Language, safety and interpretability
Fundamental Limits of Prompt Compression: A Rate-Distortion Framework for Black-Box Language Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formalizes hard-prompt compression for black-box LLMs as a rate-distortion problem, computes the optimal distortion-rate function via a dual LP, and proposes Adaptive QuerySelect, a query-aware variable-rate LLMLingua-2 variant that nearly matches the optimum on a synthetic binary-prompt task.
Problem
Prompt compression for black-box LLMs lacks a formal framework, and it is unknown how far existing token-level compression methods are from the fundamental rate-distortion limit, or how much query-awareness and tokenization matter.
Approach
Model the compressor as a conditional distribution over compressed prompts with a rate constraint, write the distortion-rate function as a linear program, and solve its dual efficiently via a lower-left convex envelope algorithm; use this as the optimal baseline to evaluate existing compressors and propose a query-aware, variable-rate threshold-based LLMLingua-2 adaptation.
Key results
- The dual-LP algorithm computes the optimal query-agnostic and query-aware distortion-rate curves exactly on the synthetic binary dataset, revealing a large gap between existing compressors and the optimum.
- Adaptive QuerySelect matches the optimal query-aware curve on some queries and is the only method that outperforms the optimal query-agnostic strategy on average.
- Restricting compressed prompts to token-pruned subsequences yields distortion-rate curves nearly identical to using all shorter sequences, reducing the search space from sum of |V|^i to 2^len(x).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Condition compression on the query (QuerySelect vs. LLMLingua-2) | LLMLingua-2 prompt compression · Synthetic dataset | distortion | Helped |
| Use query-aware, variable-rate compression (Adaptive QuerySelect) instead of fixed-rate compression | LLMLingua-2 prompt compression · Synthetic dataset | distortion | Helped |
| Use query-aware, variable-rate compression (Adaptive QuerySelect) instead of fixed-rate compression | LLMLingua-2 prompt compression · Small natural language dataset | distortion | Helped |
| Use query-aware compression (QuerySelect) instead of query-agnostic compression (LLMLingua-2) | LLMLingua-2 prompt compression · Small natural language dataset | distortion | Helped |
| Use query-aware, variable-rate compression (Adaptive QuerySelect) instead of fixed-rate query-aware compression (QuerySelect) | LLMLingua-2 prompt compression · Synthetic dataset, selected query | distortion | No clear effect |
| Use query-aware compression (LLMLingua Query) instead of vanilla LLMLingua | LLMLingua · Synthetic dataset, selected query | distortion | Mixed |
| Use standard tokenization instead of forced tokenization (ablation) | Prompt compression methods · Synthetic dataset | distortion | No clear effect |
| Restrict candidate compressed prompts to pruned versions of the original prompt instead of all shorter sequences (ablation) | Optimal distortion-rate strategy · Small natural language dataset | distortion | No clear effect |
| Use LLMLingua-2-based compression instead of no compression | LLMLingua-2 methods · Small natural language dataset | distortion | Helped |
| Use query-aware rather than query-agnostic compression | Prompt compression methods · NarrativeQA | distortion | Helped |
Surprising findings
- The optimal distortion-rate curves eventually fall below the no-compression baseline, meaning compression can improve downstream performance.
- Tokenization has little effect on the optimal curves, and standard tokenization often matches or exceeds forced tokenization at fixed rate.
Limitations
- Exact optimal curves are only computable for short binary prompts; natural language results rely on pruned-prompt restriction and beam search upper bounds.
- The natural-language gap may be inflated by GPT-4-generated labels that are not optimal ground truth.
- Experiments on natural language are small (ten prompts, four queries).
Experimental setup
Datasets: Databricks Dolly 15k NarrativeQA
Benchmarks: NarrativeQA
Metrics: log loss 0/1 loss RougeL BertScore
Baselines: Selective Context LLMLingua LLMLingua Query LLMLingua-2 QuerySelect
Builds on: LLMLingua-2 LLMLingua Selective Context LongLLMLingua
Closest papers by meaning
- Soft Prompt Recovers Compressed LLMs, Transferably (ICML 2024 · similarity 0.90)
- Prompt Compression with Context-Aware Sentence Encoding for Fast and Improved LLM Inference (AAAI 2025 · similarity 0.90)
- On the Worst Prompt Performance of Large Language Models (NeurIPS 2024 · similarity 0.90)
- Leveraging Attention to Effectively Compress Prompts for Long-Context LLMs (AAAI 2025 · similarity 0.90)
- Compressing LLMs: The Truth is Rarely Pure and Never Simple (ICLR 2024 · similarity 0.90)
- Compact Language Models via Pruning and Knowledge Distillation (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.