KV Cache Eviction and Compression

At 128k context, a Llama-3-70B request carries roughly 40 GiB of KV cache, more than the weights of the model it is serving. PagedAttention fixed fragmentation and prefix caching fixed redundancy, but neither reduces the intrinsic size of one long conversation's cache. When that cache is the binding constraint on batch size, the remaining options all amount to storing less information than the model wrote down, and the interesting engineering question is which information you can afford to lose.

Three distinct levers

They are frequently conflated and they fail differently.

Eviction (token dropping) removes entries permanently. The cache shrinks; the tokens are gone. Quantisation keeps every token at lower precision. Nothing is lost structurally, but every read is lossy. Selection (sparse attention) keeps the full cache in memory, often offloaded, and reads only part of it per step. Memory is unchanged; bandwidth per token drops.

An eviction policy that looks excellent on summarisation can be catastrophic on a later needle-style query about a dropped span, because the evidence no longer exists. Selection has no such cliff, since a later query can retrieve what an earlier one ignored, but it does not relieve memory pressure.

What the eviction policies actually key on

The empirical foundation is that attention is heavily concentrated: a small fraction of positions absorb most of the attention mass at any step.

• Attention sinks. The first few tokens of a sequence receive large attention weight regardless of content, functioning as a place for the softmax to dump probability mass when no key is relevant. Dropping them wrecks a sliding-window cache; keeping four of them plus a recent window lets a model stream over millions of tokens without perplexity blowup (Xiao et al., 2023, Efficient Streaming Language Models with Attention Sinks, arXiv:2309.17453). This buys stability, not context: the model still cannot use what left the window.
• Heavy hitters. H2O keeps a budget of tokens with the highest accumulated attention scores plus a recent window, evicting greedily as generation proceeds (Zhang et al., 2023, arXiv:2306.14048).
• Observation-window voting. SnapKV uses the attention pattern of the last few prompt tokens to vote on which earlier prompt positions matter, then compresses the prompt's KV once, before decoding starts (Li et al., 2024, arXiv:2404.14469).
• Per-layer budgets. Attention is diffuse in early layers and sharply peaked in deep ones, so a uniform per-layer budget is wrong in both directions. PyramidKV allocates more cache to lower layers and less to upper ones (Cai et al., 2024, arXiv:2406.02069).
• Per-head budgets. Only some heads do long-range retrieval; the rest behave like local windows. DuoAttention identifies retrieval heads offline and gives only those a full cache, reporting up to 2.55× memory reduction for MHA models and 1.67× for GQA (Xiao et al., 2024, arXiv:2410.10819).

Quantising the cache

Keys and values have different distributions, and this is the load-bearing detail. Keys show large per-channel outliers, so quantising them per token smears an outlier channel's scale across the whole vector; values are better behaved per token. KIVI quantises keys per channel and values per token at 2 bits without any tuning, reporting up to 2.6× memory reduction and 3.47× throughput from the larger batches that fit (Liu et al., 2024, arXiv:2402.02750). Most production stacks default to something less aggressive, fp8 or int4 with a per-block scale, because the accuracy risk is lower and the kernels are simpler.

Query-aware selection

If the cache lives in memory but only part of it is read, the criticality of a page depends on the query being decoded. Quest tracks per-page minimum and maximum key values, uses them to upper-bound the attention score any token in that page could achieve, and loads only the top-K pages (Tang et al., 2024, arXiv:2406.10774). This preserves the ability to recall anything, at the cost of an index and an approximation that can be wrong.

When it breaks

• Benchmarks disagree with production. A systematic comparison of more than ten methods across seven long-context task families found that no method dominates and that headline results are task-dependent, with retrieval-heavy and multi-hop tasks degrading long before summarisation does (Yuan et al., 2024, KV Cache Compression, But What Must We Give in Return?, arXiv:2407.01527). Evaluate on your own traffic mix.
• Eviction and prefix caching fight each other. A compressed cache is specific to the query that compressed it. Reusing it for a different follow-up turn silently answers from a cache that was pruned against a different question.
• Compression ratios are quoted at the point of maximum flattery. A 4× reduction measured on a 32k prompt with a 128-token generation says little about a 200k-token agent trace.
• The kernels are the hard part. Non-contiguous, per-head, per-layer budgets defeat the batched-page layouts that make attention kernels fast. A method that saves 40% of memory and costs 30% of throughput is not obviously a win.