TL;DR
This paper shifts the focus of KV-cache compression from what tokens to keep to when to evict them. By introducing Draft-Guided Eviction (DGE), which defers cache pruning until just two tokens into the generation phase, the authors achieve near-parity with uncompressed models, demonstrating that the initial "trajectory anchoring" of a response is more critical than the specific scoring algorithm used for eviction.
What Problem Does This Paper Address?
Serving long-context Large Language Models (LLMs) is primarily a memory bottleneck. The Key-Value (KV) cache, which stores past token representations to avoid recomputation, grows linearly with context length. To manage this, researchers use "training-free eviction" methods (like SnapKV or H2O) that score tokens at the end of the "prefill" stage and discard the least important ones before generation begins.
The authors identify two fundamental flaws in this "prefill-time" eviction strategy:
- Compensation Failure: Methods that try to "make up" for lost tokens by merging them or adding biases can recover attention mass but fail to recover actual task quality because content is not fungible.
- Selection Failure: Prefill-time signals are just estimates. Evicting before the actual answer starts can lead to fragmented cache spans, causing the model to lose the coherent information needed to reconstruct a correct answer.
Methods
The authors propose Draft-Guided Eviction (DGE). Unlike standard methods that evict immediately after prefill (Figure 1b), DGE follows a two-phase approach:
- Phase A (Drafting): The model generates the first $k$ tokens (typically $k=2$) using the full, uncompressed cache. This allows the model to "anchor" its decoding trajectory using all available information.
- Phase B (Eviction): Only after these $k$ tokens are generated does the model perform a one-time, irrevocable eviction to meet the memory budget.
The authors also introduce DGE-W, a control variant that uses the exact same scoring logic as SnapKV but simply changes the timing of the eviction. This isolates the effect of timing from the quality of the scoring signal.
Datasets
The method was evaluated across a diverse set of models and benchmarks:
- Backbones: Llama-3.1-8B-Instruct (primary), Mistral-7B-Instruct-v0.2, Qwen2.5-7B/14B-Instruct, Llama-3.2-3B-Instruct, and Llama-3-8B-Instruct.
- Benchmarks:
- LongBench: A comprehensive suite of 16 English datasets covering single/multi-doc QA, summarization, few-shot learning, and code completion.
- Needle-in-a-Haystack: A synthetic retrieval task used to test the model's ability to find specific information buried in long contexts.
Key Insights and Ideas
- Trajectory Anchoring: This is the paper's central "aha" moment. The first few tokens of a response are high-information "steering segments." Generating them on a full cache fixes the model's path. Once the trajectory is set, the model becomes remarkably robust to subsequent cache compression.
- Timing > Scoring: Surprisingly, the experiments show that when you evict matters much more than what you keep. DGE-W (using standard window scores but deferred timing) performs just as well as DGE (using real decode queries).
- Mass is not Content: The authors prove that simply preserving "attention mass" (a geometric property) does not guarantee task quality. If the preserved tokens are fragmented rather than in coherent spans, the model fails to retrieve the necessary information.
- Budget Invariance: DGE remains effective even at extremely tight budgets (e.g., keeping only 32 tokens per head), where standard methods like SnapKV typically collapse.
Key Results
- Near-FullKV Performance: On LongBench with Llama-3.1-8B, DGE achieved a score of 44.2, nearly matching the uncompressed FullKV score of 44.3, while SnapKV trailed at 35.3.
- Needle-in-a-Haystack Recovery: At a tight budget of $B=32$, SnapKV's accuracy dropped to 74.7% and H2O to 42.1%. DGE2 restored accuracy to a perfect 100%.
- Efficiency: DGE leaves the asymptotic peak memory unchanged. While it adds a small one-time latency cost for "cache surgery," it actually improves Time-To-First-Token (TTFT) to 0.93x of SnapKV because eviction is moved off the critical prefill path.
Limitations and Future Work
- Greedy Decoding: The study focuses on greedy decoding. How "trajectory anchoring" holds up under stochastic sampling remains an open question.
- Short Answer Termination: If an answer is very short and finishes within the $k$ draft tokens, no eviction occurs. While this is "rational" (the cache is freed anyway), it means the compression benefits aren't realized for very brief interactions.
- Memory Layout: The prototype implementation has a temporary memory overhead during the draft phase. The authors suggest that native Grouped-Query Attention (GQA) layout optimizations can reduce this overhead from 2.0x to 1.13x of FullKV's working set.
Summary updated