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.
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
- 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
- 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.
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
- 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”.
\(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:
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:
- 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]
- input: context \(C\), small LM, unit level (token, phrase or sentence), removal share \(p\)
- 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)
- split \(C\) into units \(u_1, \dots, u_K\) (spaCy noun chunks, or sentences)
- \(I(u_i) \leftarrow \sum_{x_t \in u_i} I(x_t)\) // formula (88.4)
- \(I_p \leftarrow\) the \(p\)-th percentile of \(\{I(u_i)\}\) // formula (88.5)
- 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.
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]
- A budget controller gives each part its own compression rate, and removes whole demonstrations first (coarse).
- Iterative token-level prompt compression (ITPC) then removes tokens (fine), segment by segment, recomputing probabilities after each deletion.
- 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\):
Then the controller picks whole demonstrations. It scores each demonstration by its perplexity under the small LM,
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:
- 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\)
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.
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:
- 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.
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]
- input: instruction, demonstrations \(d_1..d_n\), question, target \(\tau\), \(\tau_{\text{ins}}, \tau_{\text{que}}, k\), aligned small LM
- \(\tau_{\text{dems}} \leftarrow\) formula (88.6)
- sort demonstrations by \(\operatorname{PPL}(d)\), highest first // formula (88.7)
- \(\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
- \(\Delta\tau \leftarrow\) formula (88.8) // return unused budget
- split [instruction, \(\mathcal{D}\), question] into segments \(s_1, s_2, \dots\) of about 100 tokens; prefix \(\leftarrow\) empty
- 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
- 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.”:
- 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:
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:
- 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:
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.
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
| Setting | What gets pruned | Best method family |
|---|---|---|
| RAG question answering over many documents | Whole irrelevant documents, then filler tokens inside the kept ones | LongLLMLingua: question-aware \(r_k\), reordering, dynamic budgets |
| Few-shot and chain-of-thought prompts (GSM8K-style) | Whole demonstrations first, then tokens | LLMLingua budget controller (coarse-to-fine) |
| Long documents for summarization, meeting transcripts | Predictable phrases and sentences; no single question to guide it | Selective Context, LLMLingua-2 (task-agnostic) |
| Agents and chat with long histories | Old turns and tool outputs (logs, HTML, JSON) | Token-level pruning with the latest user turn as the “question” [Likely] |
| Video-RAG and video QA | ASR transcripts, per-clip captions and OCR text retrieved for a question; keep the clips whose text predicts the question | Question-aware coarse scores over clip captions, then token pruning (session 210) [Likely] |
| Key-moment detection over long broadcasts | Captions of thousands of segments sent to an LLM to find highlights | Coarse pruning by question-aware score before the LLM call [Speculation] |
| Vision-language models | Image 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
Why is self-information from a small LM a good importance score? When does it fail?core
Explain LLMLingua’s budget controller with a numeric example.core
Why does LLMLingua compress iteratively, segment by segment?core
What is distribution alignment in LLMLingua, and why is it needed?advanced
How does LongLLMLingua score documents, and why condition the question on the document and not the reverse?core
What is contrastive perplexity?advanced
Why can a compressed prompt give a better answer than the full one?core
When is prompt compression not worth it?advanced
Selective Context vs LLMLingua vs LLMLingua-2: how do they differ?basic
Design question: a Video-RAG service sends 50 clip transcripts (about 12,000 tokens) per query. How would you cut cost?advanced
Exercises
- 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?
- 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\).
- 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\).
- 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?
- 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).
- Why does LongLLMLingua’s coarse score use \(p(\text{question} \mid \text{document})\) and a restrictive statement, rather than the document’s perplexity?
Answerscheck
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
References for this session
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Li et al. (2023). Compressing Context to Enhance Inference Efficiency of Large Language Models (Selective Context)
- Jiang et al. (2023). LLMLingua: Compressing Prompts for Accelerated Inference of Large Language Models
- Jiang et al. (2023). LongLLMLingua: Accelerating and Enhancing LLMs in Long Context Scenarios via Prompt Compression
- Pan, Wu, Jiang et al. (2024). LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression
- Liu et al. (2023). Lost in the Middle: How Language Models Use Long Contexts
- Radford et al. (2019). Language Models are Unsupervised Multitask Learners
- Xu et al. (2023). RECOMP: Improving Retrieval-Augmented LMs with Compression and Selective Augmentation