The cache that eats the machine
Start with the number that motivates everything. For a decoder with L layers, H key/value heads of dimension d_h, storing both K and V in b bytes each, a context of N tokens costs:
bytes = 2 × N × L × H × d_h × bPlug in a mid-size model: L = 32, H = 32, d_h = 128, b = 2 (fp16), and N = 32768 tokens. That is 2 × 32768 × 32 × 32 × 128 × 2 ≈ 17.2 GB for a single sequence, on top of the weights, and it doubles again if you double the context. Quantization can chip b from 2 down to roughly 0.5, a useful 4×. But N grows without bound as applications demand longer prompts, and no bit-width trick touches it. Compression attacks N (and sometimes d_h) directly.
Compression is not quantization
The two ideas are orthogonal and compose, so state the line sharply. Quantization keeps every cached token but stores each key and value in a lower-precision format (int8, int4, or a grouped scheme), trading numerical fidelity for bytes. Its ceiling is the bit-width.
Compression changes how many things you store, via three broad levers. Eviction deletes cache entries for tokens judged unimportant, shrinking N. Low-rank projection shrinks the d_h dimension by mapping K/V into a smaller subspace. Merging fuses several tokens’ entries into one, again cutting N. Because they act on different terms, a real system often stacks them: evict to a budget, then quantize what survives. The distinction matters because the failure modes differ: quantization degrades gracefully, while eviction can catastrophically drop the one token you needed.
Token eviction: keep a budget, drop the rest
Eviction methods impose a fixed cache budget of k tokens (say 512 or 1024) and, whenever the cache would exceed it, discard the least useful entry. Memory then stops growing: it is O(k) instead of O(N), regardless of prompt length. The entire game is the eviction policy: how you decide which token is least useful.
The insight that makes eviction viable is that attention is sparse. At any decoding step the softmax over past tokens concentrates almost all of its mass on a small handful of positions; the long tail gets near-zero weight and contributes almost nothing. If a token has been receiving negligible attention, evicting its K/V pair barely perturbs future output. The risk is that ‘barely’ is not ‘never’: a token ignored for a thousand steps can suddenly matter, which is why eviction policies differ mainly in how they estimate future importance from past behavior.
H2O: evict by accumulated attention
H2O (Heavy-Hitter Oracle) formalizes the sparsity observation. It tracks, for each cached token, the running sum of attention scores it has received across all past query steps. Tokens with high accumulated scores are the ‘heavy hitters’; the rest are eviction candidates.
Concretely, the budget is split into two pools: recent tokens (always kept, because locality dominates) and heavy hitters selected by cumulative score. When the budget is full, H2O drops the lowest-scoring non-recent token. The policy is greedy and never revisits a decision, yet it recovers most of the full-cache quality at a fraction of the memory, because accumulated attention predicts future relevance well for many tokens. Its weakness is that greediness: a token evicted early can never come back, so H2O can lose information that only becomes important much later in a topically shifting document.
Scissorhands: the persistence-of-importance hypothesis
Scissorhands rests on a sharper empirical claim, the persistence of importance: a token that has been influential (pivotal) in recent steps tends to stay influential in the near future, and one that has been ignored tends to stay ignored. Importance is temporally sticky, not random.
Operationally this resembles H2O (maintain a budget, score tokens by attention, keep the top ones), but the framing changes what you measure. Scissorhands counts how often a token appears among the top attended positions within a recent window, rather than an all-time cumulative sum, making the estimate adaptive to where the model’s focus currently is. Because recent importance predicts imminent importance, a windowed statistic tracks shifting attention better than a lifetime total that can be dominated by long-dead history. Both methods rest on the same fact: attention’s sparsity is structured enough that a small, well-chosen subset reproduces the full model closely.
StreamingLLM and the attention-sink surprise
A naive fix for unbounded context is a sliding window: keep only the last w tokens’ K/V and discard everything older, the cheapest possible eviction policy. But it fails dramatically, perplexity exploding, the moment the very first tokens of the sequence scroll out of the window, even though those tokens are semantically trivial (often just a beginning-of-sequence marker).
StreamingLLM diagnosed why: transformers dump excess attention onto the first few positions as attention sinks. Softmax must sum to one, so when a query has nothing important to attend to, it parks the leftover probability mass on these early tokens. Evict them and the distribution is thrown off across every head. The fix is almost trivially cheap: always retain the first few tokens (the sinks) alongside the sliding window. With just four sink tokens plus a rolling window, models decode over millions of tokens at stable perplexity and O(w) memory — a striking sign that which tokens you keep can matter more than how many.
Low-rank projection: shrink the dimension, not the count
Eviction cuts N. Low-rank methods instead cut the per-token size by exploiting that the K and V matrices are empirically low-rank: their information lives in a subspace far smaller than the nominal d_h. If a key matrix K ∈ R^(N×d_h) is well approximated by rank r < d_h, you store an N×r projection plus a small r×d_h basis instead of the full matrix.
The most consequential version is architectural rather than post-hoc: Multi-head Latent Attention (MLA), used in DeepSeek models, trains the model to cache a single compressed latent vector per token and reconstruct per-head K and V from it on the fly. Because the compression is learned end-to-end, the retained subspace is the one that matters, so MLA reaches far smaller caches than naive truncation at similar quality. The tradeoff is extra compute per step to reconstruct, trading memory bandwidth for arithmetic, often the right call on memory-bound hardware.
Merging: fuse tokens instead of dropping them
Eviction is destructive: the evicted token’s information is gone. Merging softens this by combining several cache entries into one representative rather than deleting outright. If two adjacent tokens carry redundant content, a weighted average of their K and V vectors preserves most of what attention would have retrieved from either, at half the storage.
The appeal is that merging degrades more gracefully than hard eviction: instead of a cliff when a needed token vanishes, you get a gentle blur as nearby tokens are pooled. Practical schemes cluster cache entries by key similarity and merge within clusters, leaving heavy hitters untouched. The danger is averaging across a boundary, fusing tokens that look similar in key space but belong to different facts, which yields a plausible-but-wrong retrieval. Good merging is conservative: it fuses only where redundancy is high and importance is low.