Reading Notes of LLMLingua: Compressing Prompts for Accelerated Inference of Large Language Models

TL;DR: using perplexity on a small LLM as the heuristic. The assumption is that context tokens with lower surprisal can be deleted. Not really optimize the policy model to minimize the cost. The difference to Selective Context is that it (a) scores every unit independently, so it doesn’t know what has already been deleted, and (b) ignores the mismatch between the small scoring LM and the target LLM.

Reference: https://arxiv.org/abs/2310.05736

1. Summary

Can we shorten a model’s input without losing its ability to answer? LLMLingua uses a smaller model to select useful examples, then delete predictable tokens while updating its scores as earlier text changes. With GPT-3.5-Turbo, it preserves GSM8K math accuracy within 1.52 percentage points at 20× prompt compression, but harder BBH reasoning degrades sooner; conversation and summarization also outperform prior compression methods. Ablations favor iterative deletion and budget allocation over instruction tuning. Tests with Claude and reported latency reductions suggest practical value, although compression ratios do not equal speedups.

2. Motivation

Worked examples and conversation history help LLMs but increase input length, latency, and cost. Changing model weights is unavailable for closed APIs; generating summaries costs extra and can omit reasoning steps. Selective-Context deletes predictable text using a small model, but its scores become outdated after deletion, and its judgments may differ from the target model’s. LLMLingua therefore protects instructions/questions, selects whole examples before deleting tokens, updates scores using compressed history, and instruction-tunes the scorer. This motivation is clear; the weak assumption is that surprising text is useful text, and generic instruction tuning only indirectly addresses target-model mismatch.

3. Math: objective, pipeline, and evaluation

Setup and objective

Let $x=(i,d,q)$ contain an instruction $i$, worked examples or context $d$, and a question $q$. Let $P$ be the frozen target LLM and $p_\theta$ the smaller compression model. The shortened input $\tilde{x}$ is formed by deleting text, not generating a summary.

$$L=|x|,\qquad B=\lfloor rL\rfloor,\qquad r=\frac{|\tilde{x}|}{|x|},\qquad C=\frac{1}{r}.$$

Here $r$ is the retained fraction and $C$ the compression factor: retaining 5% means $C=20$. In budget calculations, $r$ is the requested fraction; after compression, measure the actual fraction separately.

$$\min_{\tilde{x}:\,|\tilde{x}|\le B} D_{\mathrm{KL}}\!\left(P(\cdot\mid\tilde{x})\,\Vert\,P(\cdot\mid x)\right).$$

This rewrites the paper’s goal: preserve the target model’s answer distribution under a length budget. LLMLingua does not directly optimize or measure this KL divergence. It uses the following heuristics as a proxy.

Step 0: instruction-tune the scorer offline

Given instruction–answer pairs $(u,a)$ generated by an LLM, train the small model with ordinary next-token prediction:

$$\theta^*=\arg\min_\theta; \mathbb{E}_{(u,a)}\left[-\sum_t\log p_\theta(a_t\mid u,a_{<t})\right].$$

This is a clean response-token form of the paper’s instruction-tuning objective; its exact loss masking is not specified. Only the small model changes. Experiments use Alpaca instruction data, whose answers come from text-davinci-003, so this is indirect alignment rather than distillation from each evaluated target, GPT-3.5-Turbo-0301 or Claude-v1.3.

Step 1: allocate space and select whole examples

Write $L_i=|i|$, $L_d=|d|$, and $L_q=|q|$. Reserve fractions $r_i=0.85$ and $r_q=0.90$ for instructions and questions; assign the remaining target budget to examples:

$$B_d=rL-r_iL_i-r_qL_q,\qquad r_d=\frac{B_d}{L_d}.$$

Score each example $d_j$ by average surprise, equivalently by perplexity:

$$H(d_j)=-\frac{1}{|d_j|}\sum_t\log p_\theta(d_{j,t}\mid d_{j,<t}), \qquad \operatorname{PPL}(d_j)=e^{H(d_j)}.$$

Select high-scoring examples into $D$, using a coarse budget of approximately $kB_d$, with $k=2$. Keeping whole examples first aims to avoid reducing every example to disconnected fragments. The paper then adjusts instruction/question retention using

$$\Delta=\frac{kB_d-|D|}{L_i+L_q},\qquad (r_i',r_d',r_q')=(r_i+\Delta,\;r_d,\;r_q+\Delta).$$

Specification caveat: these are the paper’s budget rules, not an exact budget-solving algorithm. The prose and Algorithm 1 disagree about stopping before or after exceeding the coarse budget; clipping invalid fractions and handling an infeasible $B_d$ are not specified. These formulas also do not by themselves guarantee exactly $B$ final tokens. Check actual output length in a reproduction.

Step 2: delete tokens using the already-compressed history

Split the selected prompt $(i,D,q)$ into segments $s_1,\ldots,s_m$ of 100 tokens. For token $t$ in segment $j$, compute

$$h_{j,t}=-\log p_\theta\!\left(s_{j,t}\mid \tilde{s}_{<j},s_{j,<t}\right),\qquad \tilde{s}_j=\operatorname{KeepInOrder}\{s_{j,t}:h_{j,t}\ge\gamma_j\}.$$

Choose threshold $\gamma_j$ to retain approximately the segment’s allocated fraction $r_i'$, $r_d'$, or $r_q'$. Concatenate retained segments and send them directly to $P$:

$$\tilde{x}=\tilde{s}_1\oplus\cdots\oplus\tilde{s}_m, \qquad \hat{y}=\operatorname{Decode}_{T=0}P(\cdot\mid\tilde{x}).$$

The key distinction is compressed previous segments, but original preceding tokens within the current segment. Thus dependencies are updated between segments, not perfectly after every individual deletion. A predictable word can become informative after its earlier supporting context disappears. High $h$ means low probability and is retained: Eq. (7)’s notation confuses probability with perplexity, so the surprise score above removes that ambiguity. No decompression call is required.

Evaluation metrics

For reasoning, compare the extracted answer with ground truth. For conversation/summarization, compare generated text with the target LLM’s output from the uncompressed input.

$$\mathrm{EM}=\frac{100}{N}\sum_{n=1}^{N} \mathbf{1}[\operatorname{answer}(\hat{y}_n)=y_n^*],\qquad \Delta\mathrm{EM}=\mathrm{EM}_{\mathrm{compressed}}-\mathrm{EM}_{\mathrm{full}}.$$

For candidate text $a$ and reference $b$, the remaining metrics can be summarized using precision $P_m$ and recall $R_m$ of matching units:

$$F_1(P_m,R_m)=\frac{2P_mR_m}{P_m+R_m},\qquad \mathrm{BLEU}=\underbrace{\min(1,e^{1-|b|/|a|})}_{\text{brevity penalty}} \exp\!\left(\sum_{n=1}^{K}w_n\log P_n\right).$$

Metric	What counts as a match?	Interpretation
BLEU	Clipped matching $n$-grams; $\sum_n w_n=1$	Similar wording, penalizing overly short outputs
ROUGE-1 / ROUGE-2	Matching words / adjacent word pairs	Lexical overlap
ROUGE-L	Longest common subsequence; $P_m=\mathrm{LCS}(a,b)/\lvert a\rvert$, $R_m=\mathrm{LCS}(a,b)/\lvert b\rvert$	Similar ordering of words
BERTScore F1	Maximum cosine similarity between contextual token embeddings in each direction, combined with $F_1$	Semantic similarity

For BERTScore, with normalized candidate embeddings $u_t$ and reference embeddings $v_s$,

$$P_{\mathrm{BS}}=\frac{1}{|a|}\sum_t\max_s u_t^\top v_s, \qquad R_{\mathrm{BS}}=\frac{1}{|b|}\sum_s\max_t u_t^\top v_s.$$

These are standard core definitions; BLEU order/smoothing, ROUGE aggregation, and BERTScore encoder/weighting/rescaling are not fully specified in this paper. Scores are displayed on a 0–100 scale; BERTScore 89 does not mean 89% factual accuracy.

$$\mathrm{Speedup}=\frac{t_{\mathrm{full}}} {t_{\mathrm{compress}}+t_{\mathrm{target,compressed}}},\qquad \mathrm{TokenSaving}=1-\frac{|\tilde{x}|}{|x|}.$$

The paper’s rough computation model becomes coherent if its Eq. (9) uses compression factor $C$, rather than retained fraction $r$:

$$\mathrm{Compute}\approx \left[L+\frac{(k+1)L}{C}\right]c_s+\frac{L}{C}c_P.$$

Here $c_s,c_P$ are assumed per-token costs of the small and target models. Under its illustrative assumption $c_s/c_P=1/25$, $k=2$, and $C=5$, the ratio to $Lc_P$ is $0.264$. This is a simplified estimate, not measured FLOPs or a full decoding/serving cost model.

4. Results and analysis: three questions

The experiments form a useful sequence: A, does compressed input preserve useful behavior across tasks? B, which design choices explain the performance? C, does the approach transfer and reduce runtime? Unless stated otherwise, the target is GPT-3.5-Turbo-0301, the scorer is Alpaca-7B, temperature is 0, and compression uses $k=2$, instruction/question retention 0.85/0.90, and 100-token segments. The implementation uses PyTorch 1.12.0, Transformers, a V100 32GB GPU, and tiktoken for reported token counts. Comparisons include full prompts, fewer examples, random sentence selection, phrase-based Selective-Context with the same scorer, and GPT-4 compression using the best of ten instructions. All score differences below are percentage points or metric points, not relative percentages.

A. Does useful behavior survive compression?

The four benchmarks test two distinct properties: correct answers on reasoning tasks, then similarity to uncompressed-model responses on conversation and summarization. Reasoning budgets are labeled “one-shot,” “half-shot,” and “quarter-shot”: these are approximate length constraints relative to one worked example, not literal fractional examples. Actual output lengths differ across methods, so the comparisons are not perfectly token matched.

Benchmark	Input and evaluation set	Metric/reference
GSM8K	Grade-school math; approximately 1,300 test questions as described in the paper; eight complex worked examples	Exact-match final answer vs. ground truth
BBH	6,500 problems across 23 task subsets; three worked examples	Exact match vs. ground truth
ShareGPT	575 conversations; dialogue history excluding the final round	BLEU, ROUGE, BERTScore vs. full-input GPT-3.5 response
Arxiv-March23	500 papers; first five sections, each truncated to 10,000 characters	Same similarity metrics vs. full-input GPT-3.5 summary

• Takeaway 1 — High compression works especially well on the redundant GSM8K prompt; the tolerable compression level is task dependent. GSM8K retains 77.33 EM versus 78.85 uncompressed at about 20×, a 1.52-point loss, while beating Selective-Context by 33.13 points in the same budget category. At moderate compression, gains over full prompts are only 0.23 points on GSM8K and 0.04 on BBH, with no significance analysis. BBH loses 13.22 points by about 7×. The general-language tests favor LLMLingua over Selective-Context, but establish response similarity rather than independent factual correctness.

Task / budget	LLMLingua EM	Tokens / factor	Selective-Context EM / tokens	Full-input EM	LLMLingua minus full
GSM8K / one-shot	79.08	446 / 5×	53.98 / 452	78.85	+0.23
GSM8K / half-shot	77.41	171 / 14×	52.99 / 218	78.85	−1.44
GSM8K / quarter-shot	77.33	117 / 20×	44.20 / 157	78.85	−1.52
BBH / one-shot	70.11	288 / 3×	54.27 / 276	70.07	+0.04
BBH / half-shot	61.60	171 / 5×	54.02 / 155	70.07	−8.47
BBH / quarter-shot	56.85	110 / 7×	47.37 / 108	70.07	−13.22

The simpler one-example baseline is already strong: 77.10 GSM8K EM at 422 tokens, versus LLMLingua’s 79.08 at 446. GPT-4-generated compression reaches only 56.33 GSM8K EM at 188 tokens in the quarter-shot category. Thus LLMLingua’s most compelling advantage is maintaining accuracy at very small budgets, not merely beating an uncompressed prompt. The paper’s 20× figure is its reported prompt-token accounting: zero-shot rows list only 11/16 tokens, indicating that these lengths cannot represent the complete per-question API request. Verify question and message-overhead accounting before treating 20× as total request savings.

Task / budget	Tokens: SC → LLMLingua	LLMLingua factor	BLEU: SC → LLMLingua	ROUGE-L: SC → LLMLingua	BERTScore F1: SC → LLMLingua
ShareGPT / nominal 2×	307 → 304	1.9×	25.42 → 27.36	36.99 → 38.55	88.92 → 89.52
ShareGPT / nominal 3×	180 → 177	3.3×	15.79 → 19.55	28.89 → 30.98	87.12 → 87.70
Arxiv / 350 tokens	356 → 345	4×	21.41 → 23.15	36.73 → 42.74	89.60 → 90.33
Arxiv / 175 tokens	185 → 176	9×	12.23 → 13.45	29.47 → 34.94	88.16 → 89.03

SC means Selective-Context. LLMLingua does not win every metric: sentence selection has higher ShareGPT BLEU under the first constraint, 28.59 versus 27.36, while retaining more tokens, 388 versus 304. The paper’s prose swaps the ShareGPT/Arxiv compression factors; Table 1 gives the values above.

B. Which components matter?

The ablation fixes GSM8K and the one-shot budget, then removes or changes one component. Removing iteration scores tokens in one pass; removing the budget controller also removes coarse selection; removing dynamic ratios keeps selection but treats prompt components uniformly. These comparisons test the value of adaptive deletion and budget allocation, although token counts vary. [Paper, §5.4, Table 3.]

• Takeaway 2 — Updating token scores and choosing examples carefully contribute much more than the tested alignment step. Disabling iteration costs 6.15 EM points, removing the controller costs 5.46, and random example selection costs 6.30. Replacing Alpaca-7B with untuned LLaMA-7B costs only 0.46. This supports the compression design but is weak evidence that target-distribution alignment is the main reason it works.

GSM8K ablation	EM	Change from complete method	Tokens
Complete LLMLingua	79.08	—	439
No iterative compression	72.93	−6.15	453
No budget controller	73.62	−5.46	486
No dynamic component ratios	77.26	−1.82	457
Random example selection	72.78	−6.30	477
No instruction-tuning alignment	78.62	−0.46	452
Remove stop words instead	76.27	−2.81	1,882

The complete method is listed as 439 tokens here but 446 in Table 2. The text claims a 0.56-point alignment gain; the displayed scores imply 0.46. Neither discrepancy is explained.

C. Does it transfer and save time?

The paper changes the target to Claude-v1.3 on GSM8K while retaining the same Alpaca scorer, then separately replaces the scorer with GPT2-small tuned on Alpaca. It also reports GSM8K latency using a V100 32GB setup and plots output lengths. These tests address portability and overhead rather than establish broad generalization.

• Takeaway 3 — The approach works with another target and a smaller scorer, and reported latency falls, but speedup evidence needs qualification. Claude reaches 83.51/82.61 EM at about 5×/14×, versus 81.8 for its simple-prompt baseline; no uncompressed Claude baseline is reported. GPT2-Alpaca retains 77.02 EM at about 5×, 2.06 points below Alpaca-7B. Reported end-to-end latency drops from 8.6 to 1.3 seconds at 10× compression, but the table’s speedup labels do not consistently match its own times.

GSM8K configuration	EM	Reported tokens / factor	Relevant comparison
Claude + Alpaca scorer / one-shot	83.51	439 / 5×	+1.71 vs. simple prompt
Claude + Alpaca scorer / half-shot	82.61	171 / 14×	+0.81 vs. simple prompt
Claude / simple prompt	81.80	691 / 3×	Shortened baseline, not full prompt
GPT-3.5 + GPT2 scorer / one-shot	77.02	447 / 5×	−2.06 vs. Alpaca scorer
GPT-3.5 + GPT2 scorer / half-shot	76.42	173 / 14×	−0.99 vs. Alpaca scorer
GPT-3.5 + GPT2 scorer / quarter-shot	76.27	128 / 18×	−1.06, with more tokens retained

Compression factor	Reported total time	Compression time, included	Paper’s speedup label	Speedup recomputed from 8.6 s
1×, uncompressed	8.6 s	—	—	1.00×
2×	4.9 s	0.8 s	1.7×	1.76×
5×	2.3 s	0.3 s	3.3×	3.74×
10×	1.3 s	0.2 s	5.7×	6.62×

Figure 2 also shows shorter generated answers as compression increases. This may reduce decoding cost, but shorter output could reflect lost detail; it is not automatically a quality improvement. Appendix B estimates historical API costs, e.g. GSM8K 5.2 → 0.5 dollars, without a complete accounting of local compression expense. These are historical estimates, not current prices.

5. Three essential limitations (AI)

1. Surprise is not task relevance or faithfulness. A rare but irrelevant detail can receive a high score, while a predictable negation, number, or constraint can be essential. The original method does not explicitly score information by its usefulness to the current question, and segment-wise updates still approximate dependencies within segments. There is no guarantee that token deletion preserves a logical relationship: even the paper’s Figure 9 conversation example produces corrupted numerical values after compression. BBH’s 13.22-point loss at about 7× and GSM8K’s deterioration around 25–30× show that strong compression is not universally safe. For reliable RAG, validate answer-critical facts rather than choose a ratio from the headline alone.

2. The evidence supports behavior preservation more strongly than semantic correctness or broad generality. Conversation and summarization are judged against the same target model’s uncompressed responses, so preserving its mistakes can score well. Reasoning focuses on particular few-shot prompts, which may contain unusually high redundancy; cross-target evaluation covers only Claude on GSM8K. There are no confidence intervals supporting the tiny gains over full prompts. Reconstruction examples are also weak evidence: Figure 4 recovers a worked answer of 115 by changing the problem’s meaning; interpreting the original five boxes as 150 pens gives profit 95. Recovering text is therefore not proof of recovering correct reasoning.

3. Alignment and efficiency claims are not established precisely enough for deployment predictions. Alpaca tuning is not direct alignment to either evaluated target, and its ablation gain is only 0.46 points without uncertainty estimates. A 7B scorer also incurs memory and latency costs; the simplified computation model assumes per-token costs scale with parameter counts. The latency experiment does not adequately identify the target-serving configuration, repeated-run variability, or controls for changing output length, and its printed speedups conflict with the times. Token-accounting ambiguity and tokenizer differences further prevent treating 20× prompt compression as a guaranteed reduction in total latency or monetary cost.

6. How to reproduce

Step 1 — Pin the original implementation. Use the official Microsoft LLMLingua repository, which provides pip install llmlingua, the PromptCompressor API, an experiments directory, and a CoT example notebook. Record a commit and dependencies. The repository now contains several methods: select original LLMLingua, not LLMLingua-2 or LongLLMLingua. Its current parameter documentation lists defaults such as a Llama-2 scorer and 200-token segments, which differ from this paper; a default installation is not an exact reproduction. I verified the repository/documentation, not a working end-to-end experimental run.

Step 2 — Recover the precise inputs. Obtain GSM8K and its complex eight-example prompt through the paper-linked Chain-of-Thought Hub, and BBH with its three-example prompts from BIG-Bench-Hard. For the 575 ShareGPT conversations and 500 Arxiv-March23 papers, the Selective-Context repository provides dataset-release instructions and dataset links. Apply the preprocessing in Part A, then preserve the exact sample IDs and full-input GPT-3.5 reference outputs. Availability of the upstream data is established; an exact match to LLMLingua’s processed subsets and cached references was not verified.

Step 3 — Prepare the scorer and compression settings. Recover Alpaca-7B using the Stanford Alpaca resources, or reproduce the small-scorer experiment by tuning GPT2-small on Alpaca for eight epochs with AdamW and learning rate $10^{-4}$; the paper reports about 150 minutes on a V100 32GB. Use the stated $k=2$, retention fractions 0.85/0.90, and segment size 100. Match each budget category and record achieved target-tokenizer lengths. Missing or unclear paper details include exact checkpoint revisions, GPT2 training batch size/seed/scheduler/loss masking, and several budget edge cases; resolve these from the pinned implementation rather than inventing settings.

Step 4 — Generate and evaluate paired outputs. For each identical test input, run the full prompt, LLMLingua, and comparison methods with temperature 0; reproduce the named GPT-3.5-Turbo-0301 and Claude-v1.3 targets if accessible. If they are unavailable, use an explicit replacement and call the result a new-model replication, not an exact reproduction. Keep the same Alpaca scorer for Selective-Context and use Appendix C’s ten GPT-4 compression instructions. Save compressed text, complete sent requests, model outputs, answer extraction, metric configuration, and token counts. Exact metric-library settings, baseline selection protocol, cached responses, and historical API availability were not fully established here.

Step 5 — Reproduce the tradeoff, not just one score. Sweep budgets to reconstruct quality versus actual tokens, then repeat the component ablations. Measure compression time and complete target-response time separately, control or report generated lengths, and use paired accuracy confidence intervals and repeated latency measurements. Count the final question and API-message overhead in complete-request savings. The paper does not supply enough latency-protocol detail or internally consistent arithmetic to promise exact Table 6 replication; report measured ratios directly and retain the settings needed to audit them.