The KV cache is the price of fast autoregressive decoding: to avoid recomputing attention over the whole prefix at every step, a transformer stores the key and value vectors of every past token. That cache grows linearly with sequence length and, past a few thousand tokens, dwarfs the model weights themselves in memory. Quantization attacks this by storing each cached number in fewer bits. Compression, the subject here, attacks a different axis: keep fewer entries. Instead of shrinking each key/value pair, we throw some away, project them to a smaller space, or merge them. This article walks the main families — token eviction (H2O, Scissorhands), attention sinks (StreamingLLM), low-rank projection, and merging — with the memory math behind each and the accuracy tradeoff every one is quietly making.
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.
The accuracy vs memory tradeoff, made concrete
Every method here spends accuracy to buy memory, so it helps to see the shape of the curve. Take the 17 GB, 32k-token cache from the opening. Impose an H2O-style budget of k = 1024 tokens and the cache shrinks to 1024/32768 ≈ 1/32 of its size — about 540 MB, a 32× reduction. On tasks dominated by local coherence and a few salient facts, quality loss is often within a point or two of perplexity.
But the curve is not flat. Push the budget too low and you fall off a cliff, especially on tasks that need uniform access to the whole context: exact retrieval, aggregation over many positions, or reasoning that revisits early premises. These are precisely the cases where attention is not sparse, so the assumption that justifies eviction breaks and the dropped token is the answer. In short: compression is nearly free on locally-focused generation and dangerous on needle-in-a-haystack workloads. Know which one you are running.
Why this matters most on CPU and small models
On a high-bandwidth GPU a bloated KV cache is merely a cost. On a CPU running a small language model, it is frequently the binding constraint. Decoding is memory-bound: each generated token requires streaming the entire KV cache through the attention computation, so time-per-token scales with cache size. A 17 GB cache re-read every step on a machine with modest bandwidth makes long-context generation painfully slow, or impossible if it does not fit in RAM at all.
Compression changes the feasibility line, not just the speed. A 512–1024 token budget can turn an out-of-memory failure into a workload that runs at interactive latency, because you now stream kilobytes, not gigabytes, per step. This is why StreamingLLM-style sinks-plus-window and aggressive eviction are so attractive for on-device inference: they convert an unbounded cache into a bounded, cache-friendly one, exactly the trade a memory-starved CPU wants to make.
Pitfalls and how to not get burned
The recurring trap is evaluating compression on the wrong benchmark. Perplexity on generic text is forgiving (it rewards local fluency, which survives heavy eviction), so a method can look nearly lossless there and still fail catastrophically on long-context retrieval. Always test on a task that actually exercises distant context if that is your use case.
A second trap is prefill: eviction saves memory during decoding, but the pruning decision often needs attention scores from the prompt, so a naive implementation still materializes the full cache for the prompt before pruning, saving on generation but not on the prompt peak. Third, watch position encodings: dropping tokens leaves gaps, and schemes like StreamingLLM must re-index kept tokens by their position within the cache, or rotary embeddings drift. Finally, resist over-tuning the budget to one dataset; attention sparsity is workload-dependent, and a budget generous for chat can be starvation for document QA.