LLM & VLM courseBlog
88Track 5: LLM inference and serving · session 11 of 65

Prompt pruning: Selective Context, LLMLingua, LongLLMLingua

Long prompts are slow and expensive: every token must go through prefill, and API calls are billed per token. Prompt pruning deletes the tokens, sentences or examples that carry little information before the big model sees them. A small language model decides what to delete by measuring how surprising each token is. This session builds Selective Context, LLMLingua and LongLLMLingua step by step, with real numbers from GPT-2.

Time: 2.5 to 3.5 hours (reading 2 hours, exercises 1 hour)Level: IntermediateBefore this: Sessions 3, 78 and 81 (cross-entropy and perplexity, the generation loop, inference metrics)

What you will learn

  • Why prompt length drives prefill time, time to first token, memory and API cost, and what the compression rate τ and ratio 1/τ mean
  • Self-information −log₂ p from a small LM as an importance score, and why predictable tokens can be deleted
  • Selective Context: lexical units (token, phrase, sentence) and percentile filtering
  • LLMLingua: the budget controller, coarse-to-fine pruning of demonstrations, iterative token-level compression and distribution alignment
  • LongLLMLingua: question-aware document scores, contrastive perplexity, document reordering and dynamic per-document budgets for RAG prompts
  • When pruning pays off end to end (the compressor has a cost too), and where it fails: numbers, names, code and broken phrases

Why this matters

The prompt is often the biggest part of an LLM request. A RAG system pastes 20 retrieved documents, an agent pastes its whole history, a few-shot prompt pastes eight worked examples. The answer may be 50 tokens long while the prompt is 3,000 tokens. Prompt pruning asks a simple question: which of these 3,000 tokens could we delete without changing the answer?

Every prompt token costs something. In session 78 you saw that the whole prompt goes through prefill before the first output token appears, so prefill time, and with it the time to first token (TTFT), grows with the prompt length. Each prompt token also adds an entry to the KV cache for the whole request (session 80). And API providers bill per input token. Make the prompt four times shorter and you pay for about four times fewer input tokens, and prefill does about four times less work.

The efficient-inference survey of Zhou et al. puts this idea under data-level optimization → input compression. Its first family is prompt pruning: delete tokens, phrases, sentences or whole examples that carry little information, and send the shorter prompt to the same model. Nothing in the target model changes. You can even prune prompts for a closed API model. [Certain] This session builds the three classic methods in order: Selective Context (Li et al., 2023), LLMLingua (Jiang et al., 2023) and LongLLMLingua (Jiang et al., 2023/2024). The next session, session 89, covers the other families: rewriting the prompt as a summary, and replacing it by learned vectors.

One word about notation, used in all three papers. If the original prompt has \(L\) tokens and the pruned prompt has \(\tilde L\) tokens, then

\[ \tau = \frac{\tilde L}{L} \in [0, 1], \qquad \text{compression ratio} = \frac{1}{\tau} \tag{88.1} \]
Read the symbols
\(\tau\)
the compression rate: the fraction of tokens we keep. \(\tau = 0.25\) keeps one token in four
\(1/\tau\)
the compression ratio: “4x compression” means \(\tau = 0.25\)

Careful: Selective Context reports the opposite number, the fraction removed (its “ratio 0.5” means half the content is deleted). Always check which convention a paper uses.

Is pruning worth it? The end-to-end cost

Pruning is not free. A small compressor model must first read the full prompt to score its tokens. So the real time of one request is

\[ T_{\text{total}} \approx T_{\text{compress}}(L) + T_{\text{prefill}}(\tau L) + n_{\text{out}} \cdot T_{\text{token}} \tag{88.2} \]
Read the symbols
\(T_{\text{compress}}(L)\)
time for the small model to score all \(L\) original tokens (one forward pass, sometimes several)
\(T_{\text{prefill}}(\tau L)\)
prefill of the big model on the shorter prompt
\(n_{\text{out}} \cdot T_{\text{token}}\)
decode time: number of output tokens times the time per output token (TPOT, session 81)

Pruning wins when the compressor is much cheaper than the target model, or when you pay per token to an API. It also lowers decode cost a little, because every decode step reads a shorter KV cache.

Worked example: a RAG prompt of 2,946 tokens

In the LongLLMLingua paper, a NaturalQuestions prompt with 20 documents has 2,946 tokens on average, and the compressed prompt has 748 tokens: \(\tau = 748/2946 = 0.254\), a ratio of 3.9x. [Certain] Use the prefill rule from session 25: about \(2N\) FLOPs per token for a model with \(N\) parameters (ignoring attention).

Target 70B, compressor 7B (LongLLMLingua uses LLaMA-2-7B-Chat as compressor). Without pruning: \(2 \cdot 70\times10^9 \cdot 2946 = 4.12\times10^{14}\) FLOPs. With pruning: compressor \(2 \cdot 7\times10^9 \cdot 2946 = 4.12\times10^{13}\), plus target \(2 \cdot 70\times10^9 \cdot 748 = 1.05\times10^{14}\), total \(1.46\times10^{14}\). That is 2.8x less prefill compute.

Target 7B, compressor 7B. Without pruning \(4.12\times10^{13}\); with pruning \(4.12\times10^{13} + 1.05\times10^{13} = 5.17\times10^{13}\). That is 25% more compute than not pruning at all. A compressor as large as the target only pays off if you pay per token to someone else, or if the answer gets better. A GPT-2-sized compressor (124M parameters) would cost only \(7.3\times10^{11}\) FLOPs for the same prompt.

The idea: delete what the reader can guess

Read this: “The Danube second-long river Europe starts Black Forest in Germany …”. You still understand it. The words we deleted (“is”, “the”, “-est”, “in”) were easy to guess. Information theory gives a number for “easy to guess”. The self-information (also called surprisal) of a token is

\[ I(x_t) = -\log_2 p(x_t \mid x_0, \dots, x_{t-1}) \tag{88.3} \]
Read the symbols
\(x_t\)
the token at position \(t\) of the prompt
\(p(x_t \mid x_{\lt t})\)
the probability that a small language model (GPT-2, LLaMA-7B, …) gives to this token, after reading all earlier tokens
\(I(x_t)\)
measured in bits because of \(\log_2\). It is the per-token cross-entropy loss from session 3, in bits instead of nats

A token the model expected (high \(p\)) has low self-information: deleting it loses little, because a reader (or the big LLM) can fill it back in. A token the model did not expect (a name, a number, a new fact) has high self-information: it is the content. Perplexity is the same quantity averaged and exponentiated, so the papers also say “keep high-perplexity tokens”.

Worked example: bits for a few probabilities

\(p = 0.5\) gives \(I = 1\) bit. \(p = 0.25\) gives 2 bits. \(p = 0.01\) gives 6.64 bits. \(p = 0.95\) gives only 0.074 bits.

Real values from GPT-2 (124M) on the passage of Figure 1: after “The Danube is the second-long”, the token “est” has 0.01 bits: GPT-2 is almost sure of it. After “four capital”, “cities” has 0.27 bits. The name “Dan” (the start of “Danube”) has 14.2 bits and “ten” (as in “ten countries”) has 10.7 bits. The whole 48-token passage carries 185.7 bits, 3.87 bits per token on average.

Why should a big LLM be fine with a prompt that a small LM finds predictable? The bet is that the two models agree on what is predictable: “the” after “in” is easy for both. The bet fails for words that are hard for the small model but easy for the big one, and the other way round. LLMLingua attacks this gap directly with distribution alignment, below.

Selective Context: units and a percentile

Selective Context (Li, Dong, Lin and Guerin, EMNLP 2023) turns formula (88.3) into a pruning method with two more steps. [Certain]

1. Group tokens into lexical units. Deleting single subword tokens can cut a word in half (“Dan” without “ube”). So tokens are merged into units: tokens, phrases (noun phrases, found with spaCy’s noun chunks), or sentences (found with the NLTK sentence splitter). Self-information is additive (the log of a product of conditional probabilities is a sum), so a unit gets the sum:

\[ I(u) = \sum_{x_t \in u} I(x_t) \tag{88.4} \]

2. Keep units above a percentile. Compute all unit scores, find the value \(I_p\) below which \(p\%\) of them fall, and delete those units:

\[ I_p = \operatorname{percentile}\big(\{I(u_1), \dots, I(u_K)\},\ p\big), \qquad \text{keep } u_i \iff I(u_i) \ge I_p \tag{88.5} \]
Read the symbols
\(u_1, \dots, u_K\)
the \(K\) units (tokens, phrases or sentences) of the context
\(p\)
the share of units to remove, in percent; the paper tests removal ratios 0.2, 0.35, 0.5, 0.65 and 0.8
\(I_p\)
the threshold. Using a percentile (not a fixed number of bits) makes the method adapt to each text

The paper reports that the phrase level works best. The scoring model is LLaMA-7B for the LLaMA and Vicuna targets and a smaller GPT-3 model (curie) for the OpenAI targets. At a removal ratio of 0.5, the abstract reports a 50% reduction in context cost, 36% less inference memory and 32% less inference time, with a small drop in BERTScore and faithfulness. [Certain]

Algorithm 1: Selective Context
  1. input: context \(C\), small LM, unit level (token, phrase or sentence), removal share \(p\)
  2. run the small LM once over \(C\); \(I(x_t) \leftarrow -\log_2 p(x_t \mid x_{\lt t})\) for every token // formula (88.3)
  3. split \(C\) into units \(u_1, \dots, u_K\) (spaCy noun chunks, or sentences)
  4. \(I(u_i) \leftarrow \sum_{x_t \in u_i} I(x_t)\) // formula (88.4)
  5. \(I_p \leftarrow\) the \(p\)-th percentile of \(\{I(u_i)\}\) // formula (88.5)
  6. return the units with \(I(u_i) \ge I_p\), in their original order

Figure 1 runs this on a real passage, with real self-information values from GPT-2.

darker = more bits (more surprising to GPT-2)struck out = deleted
Figure 1. Selective Context on a 48-token passage. The colors are the real self-information of each GPT-2 token (formula 88.3). Units are scored by the sum of their token bits (88.4) and units below the percentile are deleted (88.5). The phrase units are noun phrases chunked by hand in the way spaCy’s noun chunks would group them.
How to read Figure 1

Hover or tap a token to see its bits. At the token level with \(p = 50\), the kept half of the tokens still holds 78.9% of all bits: the deleted tokens were cheap. But look at “Black Sea”: “Sea” (0.67 bits) is deleted, because after “the Black” GPT-2 expects it. The big LLM now sees “flows to Black”, which is ambiguous. Switch to phrases: “the Black Sea” is one unit and survives or dies as a whole. Switch to sentences: pruning becomes coarse, and one percentile step removes many tokens at once. Note that the percentile counts units, so the share of tokens removed differs from \(p\) when units have different sizes.

LLMLingua: a budget, then coarse-to-fine

Selective Context treats the prompt as one flat text. Real prompts have parts with different value. A few-shot reasoning prompt has an instruction (“Answer the math question step by step”), many demonstrations (worked examples), and the question. Deleting a word from the question is far more dangerous than deleting a whole demonstration. LLMLingua (Jiang, Wu, Lin, Yang and Qiu, EMNLP 2023) adds three ideas. [Certain]

  1. A budget controller gives each part its own compression rate, and removes whole demonstrations first (coarse).
  2. Iterative token-level prompt compression (ITPC) then removes tokens (fine), segment by segment, recomputing probabilities after each deletion.
  3. Distribution alignment fine-tunes the small LM so that its idea of “predictable” matches the target LLM.

The budget controller

Let \(L_{\text{ins}}, L_{\text{dems}}, L_{\text{que}}\) be the token counts of the instruction, the demonstrations and the question, with \(L = L_{\text{ins}} + L_{\text{dems}} + L_{\text{que}}\). The instruction and question get fixed, gentle rates (the paper uses \(\tau_{\text{ins}} = 0.85\) and \(\tau_{\text{que}} = 0.9\)). The demonstrations get whatever budget is left to reach the overall target \(\tau\):

\[ \tau_{\text{dems}} = \frac{\tau L - \left(\tau_{\text{ins}} L_{\text{ins}} + \tau_{\text{que}} L_{\text{que}}\right)}{L_{\text{dems}}} \tag{88.6} \]

Then the controller picks whole demonstrations. It scores each demonstration by its perplexity under the small LM,

\[ \operatorname{PPL}(d) = \exp\!\left( -\frac{1}{|d|} \sum_{x_t \in d} \ln p(x_t \mid x_{\lt t}) \right) \tag{88.7} \]

sorts them from highest to lowest perplexity (high perplexity = more new information), and adds them in that order while the selected set \(\mathcal{D}\) stays within \(k \cdot \tau_{\text{dems}} L_{\text{dems}}\) tokens. The factor \(k = 2\) (the “granular control coefficient”) lets the coarse step keep twice the final demonstration budget, so the fine step has something left to squeeze. If \(\mathcal{D}\) ends up smaller than this cap, the unused tokens go back to the instruction and question:

\[ \Delta\tau = \frac{k \cdot \tau_{\text{dems}} L_{\text{dems}} - \tilde L_{\mathcal{D}}}{L_{\text{ins}} + L_{\text{que}}} \tag{88.8} \]
Read the symbols
\(\tau\)
the target overall rate (formula 88.1), for example 0.2 for 5x
\(\tau_{\text{ins}}, \tau_{\text{que}}\)
preset rates for the instruction and the question (0.85 and 0.9 in the paper)
\(k\)
granular control coefficient, 2 in the paper
\(\tilde L_{\mathcal{D}}\)
number of tokens in the selected demonstrations \(\mathcal{D}\)
\(\Delta\tau\)
extra rate given to the instruction and the question in the fine step: they are compressed at \(\tau_{\text{ins}} + \Delta\tau\) and \(\tau_{\text{que}} + \Delta\tau\)
Worked example: a 2,000-token few-shot prompt at 5x

Instruction 100 tokens, question 100 tokens, six demonstrations of 300 tokens (\(L_{\text{dems}} = 1800\)), \(L = 2000\), target \(\tau = 0.2\), so 400 tokens in the end.

Formula (88.6): \(\tau_{\text{dems}} = (0.2 \cdot 2000 - (0.85 \cdot 100 + 0.9 \cdot 100)) / 1800 = (400 - 175)/1800 = 0.125\). The coarse cap is \(k \tau_{\text{dems}} L_{\text{dems}} = 2 \cdot 0.125 \cdot 1800 = 450\) tokens. The highest-perplexity demonstration (300 tokens) fits; a second one would make \(600 > 450\), so the controller stops with one demonstration.

Formula (88.8): \(\Delta\tau = (450 - 300)/200 = 0.75\). Then \(\tau_{\text{ins}} + \Delta\tau = 1.6\), which we cap at 1: the instruction and question are kept whole. To reach 400 tokens, the fine step must shrink the 300-token demonstration to 200 tokens. (The paper gives the formulas; how the code balances the last tokens is our reading. [Likely]) Try other numbers in Figure 2.

Figure 2. The LLMLingua budget controller (formulas 88.6 to 88.8) with the paper’s \(\tau_{\text{ins}} = 0.85\), \(\tau_{\text{que}} = 0.9\). The top bar is the original prompt; each demonstration is labeled with a toy perplexity (made up for this figure). The bottom bar shows what survives the coarse step and the token budgets of the fine step.
How to read Figure 2

Demonstrations are tried in order of perplexity, highest first, and kept while the selected set fits under the cap \(k\tau_{\text{dems}}L_{\text{dems}}\). Raise the ratio to 15x or 20x: \(\tau_{\text{dems}}\) becomes tiny, or even negative when the instruction and question alone use more than the budget. Then no demonstration fits and the method falls back to squeezing the instruction and question. Lower \(k\) to 1: the coarse step keeps fewer demonstrations, so more of the budget comes back as \(\Delta\tau\). With mixed lengths, a long high-perplexity demonstration can block the next one even when a short one would still fit.

Iterative token-level compression

Selective Context scores all tokens in one pass, conditioned on the original text. But the big LLM will read the compressed text. Once you delete “the” and “in”, the probability of the next word changes. Scoring tokens as if they were independent of each other’s deletion is wrong. LLMLingua splits the prompt into segments \(s_1, s_2, \dots\) (100 tokens each in the paper) and scores each segment conditioned on the already compressed earlier segments:

\[ I(s_{j,i}) = -\log_2 p\big(s_{j,i} \mid \tilde s_1, \dots, \tilde s_{j-1},\ s_{j,\lt i}\big), \qquad \text{keep } s_{j,i} \iff I(s_{j,i}) \gt \gamma_j \tag{88.9} \]
Read the symbols
\(s_{j,i}\)
token \(i\) of segment \(j\)
\(\tilde s_1, \dots, \tilde s_{j-1}\)
the compressed versions of the earlier segments: what the target LLM will actually see
\(\gamma_j\)
a per-segment threshold, chosen from the distribution of scores in the segment so that the segment keeps its rate (\(\tau_{\text{ins}} + \Delta\tau\), \(\tau_{\text{dems}}\) or \(\tau_{\text{que}} + \Delta\tau\))

This costs one small forward pass per segment instead of one for the whole prompt, but with a KV cache for the compressed prefix the extra work is small. Figure 3 compares the two ways on the Danube passage, with 12-token segments and a 50% rate per segment.

One pass (scores conditioned on the original text)
Iterative (scores conditioned on the compressed prefix, formula 88.9)
darker = more bitsred frame = the two methods disagree
Figure 3. Iterative token-level compression on the Danube passage. Each step adds one 12-token segment and keeps its 6 most surprising tokens. All bits are real GPT-2 values. In the iterative row, GPT-2 reads only the compressed earlier segments, so the scores of later segments change.
How to read Figure 3

Segment 1 has no earlier context, so both rows agree. From segment 2 on, the iterative row conditions on a telegram-style prefix. After the prefix “The Dan second-long river. It starts Black in Germany”, GPT-2 is much less sure of what follows, so “Sea” gets 3.78 bits instead of 0.67 and is kept: the iterative method notices that, given what is left, “Sea” is no longer predictable. Ten of the 48 keep/drop decisions differ between the two rows.

Distribution alignment

The small LM (in the paper Alpaca-7B, or GPT-2 small fine-tuned on Alpaca) is instruction-tuned on text generated by the target LLM: pairs of instructions and target-LLM answers from the Alpaca data. After this, the small model’s probabilities are closer to the target’s, so “predictable for the small model” means more often “predictable for the target”. The paper’s ablation without this step (plain LLaMA-7B) does worse. [Certain]

Algorithm 2: LLMLingua, coarse to fine
  1. input: instruction, demonstrations \(d_1..d_n\), question, target \(\tau\), \(\tau_{\text{ins}}, \tau_{\text{que}}, k\), aligned small LM
  2. \(\tau_{\text{dems}} \leftarrow\) formula (88.6)
  3. sort demonstrations by \(\operatorname{PPL}(d)\), highest first // formula (88.7)
  4. \(\mathcal{D} \leftarrow \{\}\); for each \(d\) in that order: if \(\tilde L_{\mathcal{D}} + |d| \le k\,\tau_{\text{dems}} L_{\text{dems}}\) then add \(d\) to \(\mathcal{D}\) else stop
  5. \(\Delta\tau \leftarrow\) formula (88.8) // return unused budget
  6. split [instruction, \(\mathcal{D}\), question] into segments \(s_1, s_2, \dots\) of about 100 tokens; prefix \(\leftarrow\) empty
  7. for each segment \(s_j\): score its tokens given prefix (88.9); choose \(\gamma_j\) so that \(s_j\) keeps its part’s rate; append the kept tokens \(\tilde s_j\) to prefix
  8. return prefix // the compressed prompt, sent to the target LLM

On GSM8K (grade-school math with chain-of-thought demonstrations) with GPT-3.5-Turbo, the full few-shot prompt gives 78.85 exact match. LLMLingua at 5x gives 79.08, and at 20x gives 77.33, a drop of 1.52 points. Selective Context under the same 1-shot budget (about 5x) gives 53.98. [Certain] Removing whole demonstrations is much safer than shredding all of them evenly.

LongLLMLingua: prune with the question in mind

LLMLingua scores tokens by how surprising they are in general. In RAG the prompt is a question plus many retrieved documents, and most documents do not contain the answer. A document about the Alps can be very surprising (high perplexity) and still useless for the question “Which river flows through Vienna?”. LongLLMLingua (Jiang et al., ACL 2024) makes every score question-aware, and it uses the known position bias of LLMs. [Certain]

Coarse step: which documents matter?

Instead of asking “how surprising is this document?”, ask “how well does this document predict the question?”. Put the document first and measure the average loss of the question, plus a fixed restrictive statement “We can get the answer to this question in the given documents.”:

\[ r_k = -\frac{1}{N_c} \sum_{i=1}^{N_c} \ln p\big(x^{\text{que,restrict}}_i \mid x^{\text{doc}}_k\big), \qquad k = 1, \dots, K \tag{88.10} \]
Read the symbols
\(x^{\text{doc}}_k\)
the \(k\)-th retrieved document, placed before the question
\(x^{\text{que,restrict}}\)
the question followed by the restrictive statement; \(N_c\) is its number of tokens
\(r_k\)
the average negative log-likelihood (in nats) of the question given the document. Lower is better: the document makes the question easy to predict

Why this direction (question given document, not document given question)? A long document has many tokens that have nothing to do with the question, so \(p(\text{doc} \mid \text{question})\) is dominated by noise. The question is short and the same for all documents, so the scores are comparable. The restrictive statement pushes the model to reward documents that answer the question, not only ones that share its words. The paper reports that this score retrieves the right document more often than BM25, Gzip, SentenceBERT and OpenAI embeddings. [Certain]

Fine step: contrastive perplexity

Inside a kept document, which tokens matter for the question? LongLLMLingua compares each token’s surprise with and without the question in front:

\[ s_i = \operatorname{PPL}(x_i \mid x_{\lt i}) - \operatorname{PPL}(x_i \mid x^{\text{que}}, x_{\lt i}) \tag{88.11} \]

Here \(\operatorname{PPL}(x_i \mid \cdot) = 1/p(x_i \mid \cdot)\) is the perplexity of one token. If seeing the question makes a token much easier to predict, the token is related to the question, and \(s_i\) is large. The paper shows this is tied to how strongly the token predicts the question (a conditional pointwise mutual information). [Certain]

Reordering and dynamic budgets

LLMs use information at the start and the end of a long prompt better than in the middle (“lost in the middle”, Liu et al. 2023). So LongLLMLingua reorders the kept documents by \(r_k\), best first. It also gives better documents a bigger token budget:

\[ \tau_k = \max\!\Big(\min\!\Big(\big(1 - \tfrac{2\, I(r_k)}{K'}\big)\,\delta\tau + \tau_{\text{doc}},\ 1\Big),\ 0\Big) \tag{88.12} \]
Read the symbols
\(I(r_k)\)
the rank of document \(k\) by its score (we count from 0 for the best document [Likely])
\(K'\)
the number of documents kept after the coarse step
\(\tau_{\text{doc}}\)
the base rate for documents, from LLMLingua’s budget controller
\(\delta\tau\)
how much to tilt the budget toward top documents (0.3 in the paper)

So the best document gets \(\tau_{\text{doc}} + \delta\tau\), the middle one about \(\tau_{\text{doc}}\), and the last ones less. Finally, subsequence recovery fixes the answer: if the LLM copies a damaged name from the compressed prompt (for example a name with one subword deleted), the method finds the matching span in the original prompt and restores it.

Figure 4 runs the coarse and fine steps on a toy RAG prompt with six short documents. All scores are real GPT-2 values: \(r_k\) from formula (88.10), document perplexity (88.7) for the question-unaware ranking, and \(s_i\) from (88.11).

Question:

Figure 4. LongLLMLingua on a toy RAG prompt. The documents are shown in the order the target LLM would see them. The green frame marks the document that contains the answer. Bars show each document’s keep rate \(\tau_k\) (88.12); struck-out tokens are removed by the fine step.
How to read Figure 4

With question-aware scores, GPT-2 puts the Vienna–Danube document first (\(r_k = 3.094\) nats), then the general Danube document (3.312). With question-unaware perplexity, the most “surprising” documents are the Alps (perplexity 55.2) and the coffee houses (54.9): with \(K' = 3\), the answer document is dropped. In retrieval order, the answer sits at position 3, in the middle. The fine step keeps the tokens with the largest contrastive score \(s_i\) in question-aware mode, and the highest-bit tokens otherwise. Push \(\delta\tau\) to 0.5 to see the budget tilt toward the top document.

How much does this help? Figure 5 shows the paper’s NaturalQuestions results with 20 documents and GPT-3.5-Turbo, where the answer document is moved to different positions.

original prompt (2,946 tokens)LongLLMLingua, 4x budget (748 tokens)
Figure 5. Accuracy (%) on NaturalQuestions multi-document QA, by the position of the document that holds the answer (numbers from the LongLLMLingua paper, GPT-3.5-Turbo). The original prompt shows the U shape of “lost in the middle”. The compressed prompt is almost flat and higher, with about a quarter of the tokens.

At position 10 the accuracy rises from 54.1% to 71.2% (+17.1 points), while at position 1 it moves from 75.7% to 75.0%. So pruning helped most where the original prompt hurt most: in the middle. A shorter prompt with less noise can give a better answer, not only a cheaper one. The paper’s abstract also reports up to 21.4% better NaturalQuestions performance with about 4x fewer tokens, a 94.0% cost cut on LooGLE, and 1.4x to 2.6x lower end-to-end latency at 2x to 6x compression on prompts of about 10k tokens. [Certain]

Code: all three ideas with GPT-2

This script uses the Hugging Face transformers GPT-2 (124M) as the small LM. It runs on a CPU in a few seconds and is deterministic (no sampling). It prints the outputs shown in the comments, which are the numbers behind Figures 1 and 4.

import math, torch
from transformers import AutoTokenizer, AutoModelForCausalLM
torch.manual_seed(0)
tok = AutoTokenizer.from_pretrained("gpt2")                  # the small scoring LM (124M)
lm  = AutoModelForCausalLM.from_pretrained("gpt2").eval()

@torch.no_grad()
def bits(ids, ctx=()):
    """Self-information -log2 p(x_t | ctx, x_<t) of every token in ids, formula (88.3)."""
    x = torch.tensor([[tok.bos_token_id, *ctx, *ids]])
    logp = torch.log_softmax(lm(x).logits[0].float(), dim=-1)
    start = 1 + len(ctx)                                     # position of ids[0]
    pos = torch.arange(start, start + len(ids))
    return -logp[pos - 1, torch.tensor(ids)] / math.log(2)   # nats -> bits

def selective_context(text, remove=0.5):
    """Token-level Selective Context: drop units below the percentile, (88.5)."""
    ids = tok(text)["input_ids"]
    I = bits(ids)
    thr = torch.quantile(I, remove)                          # same as np.percentile(I, 100*remove)
    keep = [t for t, v in zip(ids, I) if v >= thr]
    return tok.decode(keep), len(keep), len(ids)

def rank_documents(question, docs):
    """LongLLMLingua coarse score r_k, formula (88.10): low = relevant."""
    q = tok(" " + question + " We can get the answer to this question in the given documents.")["input_ids"]
    r = [bits(q, tok(" " + d)["input_ids"]).mean().item() * math.log(2) for d in docs]
    return sorted(range(len(docs)), key=lambda k: r[k]), r

def doc_budgets(order, tau_doc=0.4, dtau=0.3):
    """Dynamic per-document keep rate, formula (88.12); order[0] is the best document."""
    K = len(order)
    return {k: max(min((1 - 2 * i / K) * dtau + tau_doc, 1.0), 0.0) for i, k in enumerate(order)}

text = ("The Danube is the second-longest river in Europe. It starts in the Black Forest in Germany "
        "and flows to the Black Sea. Along the way, the river passes through ten countries and four "
        "capital cities, including Vienna and Budapest.")
short, n_keep, n = selective_context(text, remove=0.5)
print(n_keep, "of", n, "tokens:", short)
# 24 of 48 tokens: The Danube second-long river Europe starts Black Forest in Germany to Black
#                  Along passes ten countries and four capital Vienna Budapest

docs = ["Paris is the capital of France. The Seine river flows through the centre of the city.",
        "The Alps cover much of western Austria. Many visitors come in winter to ski in the mountains.",
        "Vienna is the capital of Austria. The Danube river flows through the city, past the old town.",
        "Vienna is famous for its coffee houses, where people read newspapers and eat cake for hours.",
        "Prague is the capital of the Czech Republic. The Vltava river runs through the old city.",
        "The Danube is the second-longest river in Europe and flows through ten countries."]
order, r = rank_documents("Which river flows through the city of Vienna?", docs)
print("order:", order, "r_k:", [round(v, 3) for v in r])
# order: [2, 5, 4, 0, 1, 3] r_k: [3.449, 3.562, 3.094, 3.591, 3.373, 3.312]
print({k: round(v, 2) for k, v in doc_budgets(order).items()})
# {2: 0.7, 5: 0.6, 4: 0.5, 0: 0.4, 1: 0.3, 3: 0.2}

For production use, the authors’ open-source llmlingua package implements LLMLingua, LongLLMLingua and LLMLingua-2 behind one PromptCompressor class. [Likely]

Where this is used

SettingWhat gets prunedBest method family
RAG question answering over many documentsWhole irrelevant documents, then filler tokens inside the kept onesLongLLMLingua: question-aware \(r_k\), reordering, dynamic budgets
Few-shot and chain-of-thought prompts (GSM8K-style)Whole demonstrations first, then tokensLLMLingua budget controller (coarse-to-fine)
Long documents for summarization, meeting transcriptsPredictable phrases and sentences; no single question to guide itSelective Context, LLMLingua-2 (task-agnostic)
Agents and chat with long historiesOld turns and tool outputs (logs, HTML, JSON)Token-level pruning with the latest user turn as the “question” [Likely]
Video-RAG and video QAASR transcripts, per-clip captions and OCR text retrieved for a question; keep the clips whose text predicts the questionQuestion-aware coarse scores over clip captions, then token pruning (session 210) [Likely]
Key-moment detection over long broadcastsCaptions of thousands of segments sent to an LLM to find highlightsCoarse pruning by question-aware score before the LLM call [Speculation]
Vision-language modelsImage and video tokens instead of text tokens; the same idea of “drop what carries little information”Visual token pruning and merging (session 183)

Common mistakes

  • Pruning the question or the instruction as hard as the context. One missing “not” changes the task. Give them gentle rates, as LLMLingua does (0.85 and 0.9), or protect them completely.
  • Deleting the “predictable” half of a name, number or code token. “Dan” survives and “ube” goes; “3.14” becomes “3.”. Use phrase or word units, or force-keep numbers, entities and code. LongLLMLingua’s subsequence recovery exists because of this.
  • Ignoring the compressor’s own cost. A 7B compressor in front of a 7B target uses more prefill compute than no compression (worked example above). Measure end-to-end latency, formula (88.2).
  • Mixing up rate and ratio. \(\tau = 0.2\) keeps 20%; Selective Context’s “ratio 0.2” removes 20%. Check before comparing numbers across papers.
  • Using question-unaware scores for RAG. High perplexity means “surprising”, not “relevant”. In Figure 4 the Alps document wins on perplexity and the answer document is dropped.
  • Breaking the prefix cache. If the same system prompt is reused across requests, a provider may cache its KV entries. Pruning it differently per request destroys that cache hit, which can cost more than the tokens you saved. Prune only the parts that change. [Likely]
  • Evaluating only on the average. Pruning can fail badly on a few prompts (wrong number, missing condition). Check worst cases and tasks with exact answers, not only ROUGE or BERTScore.

Interview questions

What is prompt pruning and why does it speed up inference?basic
Prompt pruning removes tokens, phrases, sentences or whole examples from the prompt that carry little information, and sends the shorter prompt to the unchanged model. Prefill work, TTFT, KV-cache size and per-token API cost all grow with prompt length, so a prompt with rate \(\tau\) (kept fraction) costs about \(\tau\) times as much prefill. It is a data-level optimization: it needs no change to the model and even works with closed APIs.
Why is self-information from a small LM a good importance score? When does it fail?core
\(I(x_t) = -\log_2 p(x_t \mid x_{\lt t})\) measures how hard a token is to guess. Low-surprise tokens (function words, endings of words) can be rebuilt by the target LLM, so removing them loses little. It fails when the small and the large model disagree on what is predictable, when a token is predictable but critical (the second half of a name, a negation, a digit of a number), and when the task needs specific content that is not surprising in general (relevance to a question). Alignment (LLMLingua), phrase units (Selective Context) and question-aware scores (LongLLMLingua) each fix one of these.
Explain LLMLingua’s budget controller with a numeric example.core
The instruction and question get fixed rates (0.85, 0.9); the demonstrations get the rest: \(\tau_{\text{dems}} = (\tau L - \tau_{\text{ins}}L_{\text{ins}} - \tau_{\text{que}}L_{\text{que}})/L_{\text{dems}}\). Demonstrations are sorted by perplexity (highest first) and added while the set fits in \(k\tau_{\text{dems}}L_{\text{dems}}\) tokens, \(k = 2\). Unused budget returns to instruction and question as \(\Delta\tau\). Example: 100 + 1800 + 100 tokens at 5x: \(\tau_{\text{dems}} = 0.125\), cap 450, one 300-token demonstration fits, \(\Delta\tau = 0.75\), so instruction and question are kept whole and the demonstration is squeezed to about 200 tokens.
Why does LLMLingua compress iteratively, segment by segment?core
A one-pass method scores each token conditioned on the original text, which assumes deletions do not affect each other. But the target reads the compressed text, where the probability of a token depends on which earlier tokens were removed. ITPC scores each segment conditioned on the already compressed earlier segments, so a token that became unpredictable after earlier deletions (like “Sea” after “starts Black in Germany” in Figure 3) is kept. The cost is one extra small forward per segment, cheap with a KV cache over the compressed prefix.
What is distribution alignment in LLMLingua, and why is it needed?advanced
The small LM is instruction-tuned on instruction–answer pairs generated by the target LLM (Alpaca data). This moves the small model’s token distribution closer to the target’s, so the small model’s “predictable” better matches what the target can reconstruct. Without it, the method prunes using the wrong reader’s expectations; the paper’s ablation with plain LLaMA-7B is worse.
How does LongLLMLingua score documents, and why condition the question on the document and not the reverse?core
\(r_k\) is the average negative log-likelihood of the question plus a restrictive statement (“We can get the answer to this question in the given documents.”), given document \(k\) in front. Lower means the document makes the question predictable, so it is likely relevant. The reverse, \(p(\text{doc} \mid \text{question})\), is dominated by the many document tokens unrelated to the question, and document lengths differ; the short, fixed question gives comparable scores across documents. The paper reports higher recall than BM25, Gzip, SentenceBERT and OpenAI embeddings.
What is contrastive perplexity?advanced
\(s_i = \operatorname{PPL}(x_i \mid x_{\lt i}) - \operatorname{PPL}(x_i \mid x^{\text{que}}, x_{\lt i})\): how much easier token \(x_i\) becomes when the question is in front. A large drop means the token is related to the question. It replaces plain surprisal for the fine step, so filler that is surprising but unrelated to the question is removed, and question-related words are kept. The paper links it to conditional pointwise mutual information between the token and the question.
Why can a compressed prompt give a better answer than the full one?core
Two reasons. (1) Position bias: LLMs use the start and end of long prompts better than the middle (“lost in the middle”). LongLLMLingua reorders documents so the most relevant ones come first. (2) Noise: irrelevant documents distract the model. On NaturalQuestions with 20 documents and GPT-3.5-Turbo, the answer document at position 10 gives 54.1% with the full prompt and 71.2% with LongLLMLingua at about 4x fewer tokens.
When is prompt compression not worth it?advanced
When the compressor’s cost is close to the savings: short prompts, a compressor as large as the target (7B in front of 7B uses about 25% more prefill compute for a 3.9x compression), or a prompt prefix that is reused and already served from a prefix cache. Also when exactness matters (code, legal text, numbers) and dropped tokens cannot be rebuilt, or when decode, not prefill, dominates latency (long outputs). Measure end-to-end time, \(T_{\text{compress}} + T_{\text{prefill}}(\tau L) + n_{\text{out}}T_{\text{token}}\), not prompt length.
Selective Context vs LLMLingua vs LLMLingua-2: how do they differ?basic
Selective Context: one pass of a causal LM, sum self-information per unit (token, phrase, sentence), delete units below a percentile. LLMLingua: adds a per-part budget, coarse removal of whole demonstrations, iterative token-level scoring on the compressed prefix and an aligned small LM. LLMLingua-2: replaces surprisal with a trained bidirectional encoder (XLM-RoBERTa or mBERT) that classifies each token keep/drop, trained on labels distilled from a large LLM; it is faster and task-agnostic. LongLLMLingua is the question-aware RAG version of LLMLingua.
Design question: a Video-RAG service sends 50 clip transcripts (about 12,000 tokens) per query. How would you cut cost?advanced
First, coarse: score each clip transcript by the question’s loss given the transcript (\(r_k\)), or a cheap embedding retriever, and keep the top few. Reorder them best first. Second, fine: token-level pruning with a small model and question-aware scores, with numbers, timestamps and names protected. Give top clips bigger budgets (formula 88.12). Keep the fixed system prompt unpruned so the prefix cache still hits. Validate on answer accuracy and timestamp accuracy, not just token count, and measure end-to-end latency including the compressor.

Exercises

  1. A token has probability 0.125 under the small LM, another 0.9. Compute their self-information in bits. Which one would you delete first?
  2. A prompt has instruction 50, question 50, and six demonstrations of 150 tokens each. Target 4x (\(\tau = 0.25\)), \(\tau_{\text{ins}} = 0.85\), \(\tau_{\text{que}} = 0.9\), \(k = 2\). Compute \(\tau_{\text{dems}}\), the cap, the number of demonstrations kept, and \(\Delta\tau\).
  3. LongLLMLingua keeps \(K' = 4\) documents with \(\tau_{\text{doc}} = 0.5\), \(\delta\tau = 0.2\). Using ranks 0 to 3, give each document’s rate \(\tau_k\).
  4. A 70B target model, a 7B compressor, a 10,000-token prompt, 4x compression. How much less prefill compute (in the \(2N\) per token model) is used end to end?
  5. In Figure 1 at the token level, “Sea” is deleted but at the phrase level it is kept. Explain why, using formulas (88.3) and (88.4).
  6. Why does LongLLMLingua’s coarse score use \(p(\text{question} \mid \text{document})\) and a restrictive statement, rather than the document’s perplexity?
Answerscheck
1. \(-\log_2 0.125 = 3\) bits; \(-\log_2 0.9 = 0.152\) bits. Delete the 0.9 token first: it is easy to guess. 2. \(\tau_{\text{dems}} = (0.25 \cdot 1000 - (42.5 + 45))/900 = 162.5/900 = 0.181\). Cap \(= 2 \cdot 0.181 \cdot 900 = 325\) tokens. Two demonstrations fit (300); a third would make 450. \(\Delta\tau = (325 - 300)/100 = 0.25\), so the instruction rate becomes 1.1 and the question rate 1.15, both capped at 1. 3. \((1 - 0)\cdot0.2 + 0.5 = 0.7\), \((1 - 0.5)\cdot0.2 + 0.5 = 0.6\), \(0.5\), \((1 - 1.5)\cdot 0.2 + 0.5 = 0.4\). 4. Without: \(2 \cdot 70\times10^9 \cdot 10^4 = 1.4\times10^{15}\). With: compressor \(1.4\times10^{14}\) + target on 2,500 tokens \(3.5\times10^{14}\) = \(4.9\times10^{14}\). Ratio 2.86x less. 5. As a single token after “the Black”, “Sea” has only 0.67 bits: GPT-2 expects it, so it falls below the token percentile. As part of the phrase “the Black Sea”, its bits are summed with “the” and “Black” (88.4), and the phrase total is high, so the whole phrase is kept. 6. Document perplexity measures surprise, not relevance: in Figure 4 the Alps and coffee-house documents have the highest perplexity but do not answer the question. \(p(\text{question} \mid \text{document})\) is high only if the document makes the question predictable, and the restrictive statement rewards documents that contain the answer.

Key takeaways

  • Prompt length drives prefill compute, TTFT, KV-cache size and API cost. Pruning keeps a fraction \(\tau\) of the tokens (88.1), but the compressor’s own cost counts (88.2).
  • Self-information from a small LM (88.3) is the basic importance score: delete what the reader can guess.
  • Selective Context sums bits over tokens, phrases or sentences (88.4) and deletes units below a percentile (88.5); phrases protect names and fixed expressions.
  • LLMLingua gives each prompt part a budget (88.6, 88.8), drops whole high-redundancy demonstrations first (88.7), then prunes tokens iteratively on the compressed prefix (88.9), with a small LM aligned to the target.
  • LongLLMLingua makes everything question-aware (88.10, 88.11), reorders documents best first and tilts budgets toward them (88.12). On NaturalQuestions it is both shorter and more accurate in the middle positions.

Key formulas

\[ I(x_t) = -\log_2 p(x_t \mid x_{\lt t}), \qquad \tau_{\text{dems}} = \frac{\tau L - \tau_{\text{ins}}L_{\text{ins}} - \tau_{\text{que}}L_{\text{que}}}{L_{\text{dems}}} \]
\[ r_k = -\frac{1}{N_c}\sum_i \ln p\big(x^{\text{que,restrict}}_i \mid x^{\text{doc}}_k\big), \qquad s_i = \operatorname{PPL}(x_i \mid x_{\lt i}) - \operatorname{PPL}(x_i \mid x^{\text{que}}, x_{\lt i}) \]

References for this session

  1. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  2. Li et al. (2023). Compressing Context to Enhance Inference Efficiency of Large Language Models (Selective Context)
  3. Jiang et al. (2023). LLMLingua: Compressing Prompts for Accelerated Inference of Large Language Models
  4. Jiang et al. (2023). LongLLMLingua: Accelerating and Enhancing LLMs in Long Context Scenarios via Prompt Compression
  5. Pan, Wu, Jiang et al. (2024). LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression
  6. Liu et al. (2023). Lost in the Middle: How Language Models Use Long Contexts
  7. Radford et al. (2019). Language Models are Unsupervised Multitask Learners
  8. Xu et al. (2023). RECOMP: Improving Retrieval-Augmented LMs with Compression and Selective Augmentation