The last post about KV cache was an accounting note: every retained token leaves keys and values in GPU memory. This one is about the crueler question.

When the cache is too small, which tokens get to keep existing?

Autoregressive attention is usually written as if the whole past is available:

\[\operatorname{softmax}\left(q_t K_{<t}^{\top}/\sqrt{d}\right)V_{<t}.\]

But a serving system with a bounded KV cache has to choose a subset \(S_t\) of old positions. The practical computation becomes closer to

\[\operatorname{softmax}\left(q_t K_{S_t}^{\top}/\sqrt{d}\right)V_{S_t}.\]

That subset is not an implementation detail. It is a memory policy. It is also a bet about the future attention pattern.

The naive bet is:

recent tokens are the useful tokens

That is often true. It is also dramatically incomplete.

In 2023, StreamingLLM made the failure mode unusually crisp. Plain window attention keeps only the most recent keys and values. Xiao, Tian, Chen, Han, and Lewis show that this can fail once the text length exceeds the cache size, and that keeping a few initial tokens, called attention sinks, can recover much of the behavior.1 Those first tokens may not be semantically useful. They are structurally useful because many models put surprising attention mass on them.

So the cache starts with a small embarrassment:

the first token can be important even when it says nothing

Eviction Is an Attention Approximation

Let \(a_{t,i}\) be the full-cache attention mass from the current token \(t\) to an old token \(i\). If a cache policy keeps subset \(S_t\), then one crude diagnostic is the retained mass

\[R_t(S_t) = \sum_{i\in S_t} a_{t,i}.\]

This is not a complete quality metric. Values can cancel. A token with small attention can still matter if it carries a rare fact. Different heads and layers serve different jobs. But retained attention mass is a useful first instrument: if the policy repeatedly throws away the tokens that the full model would have looked at, it is probably not a harmless memory optimization.

That framing explains three families of KV-cache policies.

Sliding window. Keep the most recent tokens. This is cheap, stable, and good when attention is mostly local. It fails on old facts and attention sinks.

Sink plus window. Pin the first few positions and spend the rest of the budget on recency. This is the StreamingLLM move: a small structural exception to the recency rule.1

Heavy hitters plus recent tokens. H2O observes that a small subset of tokens contributes much of the attention value, and proposes a KV-cache eviction policy that retains a balance of recent tokens and heavy hitters.2 This turns eviction into an online scoring problem.

Observation-window voting. SnapKV attacks a related but different pain: long prompts whose KV cache is already huge before generation begins. It finds important prompt positions from an observation window near the end of the prompt and keeps clustered important positions per head.3 That is a prompt-time prediction: before generation, ask what the prompt seems likely to need.

These are not interchangeable tricks. They are different answers to:

what evidence tells us an old key-value pair is still useful?

The lab below builds a small synthetic attention stream so those answers can be compared without needing a real model checkpoint. It has:

  1. first-token sink mass;
  2. exponentially decaying recency mass;
  3. old fact tokens that become relevant during generation;
  4. a prompt observation window that can reveal future fact needs;
  5. a fixed cache budget.

The policies are simplified versions of the ideas above. They are not implementations of StreamingLLM, H2O, or SnapKV. The point is to expose the shape of the tradeoff.

Sliding window Sink + window Heavy + recent Observation vote Active old fact

Deterministic synthetic attention stream. The audit checks normalized attention, cache-budget invariants, bounded retained mass, sink-window recovery, heavy-hitter recovery, and observation-window fact retention.

The top-left panel is the retained attention mass over generated tokens. The cache map shows what each policy still remembers at the selected step. Vertical red marks are old facts; if the selected step is querying one, the active fact is drawn more strongly. The lower-right panel shows the full attention distribution in gray and the part retained by the observation-window policy in purple.

Start with streaming chat. Sliding window does not keep the first tokens, so it loses the sink mass. Sink plus window recovers that structural mass. Heavy hitters and observation voting also keep old fact positions when the observation window has revealed them.

Switch to needle QA and shrink the budget. Recency looks especially foolish: the fact can be hundreds of tokens back, and no amount of recent-token loyalty will resurrect it after eviction.

Switch to diffuse attention. Now the old facts are weaker. A policy that spends budget on high-scoring old positions can lose average retained mass relative to a boring sliding window. That is not a contradiction. It is the point. A cache policy is a hypothesis about the attention distribution.

Why the First Token Becomes Infrastructure

Attention sinks are strange because they are not just old facts.

StreamingLLM argues that initial tokens receive strong attention scores as a sink even when they are not semantically important.1 In a pure sliding window, those positions disappear. The model is then asked to operate with a different attention substrate from the one it learned.

That suggests a useful distinction:

semantic memory: tokens kept because their content may be needed
structural memory: tokens kept because the computation expects them

The first few tokens can be structural memory. A cited paragraph, function definition, or financial figure is semantic memory. Recency can be either.

This is why “just keep the last 8k tokens” is too blunt. It treats all old tokens as equally stale. But attention has roles, and some roles are not monotone in position.

Heavy Hitters Are Online Evidence

H2O’s phrase “heavy hitter” is wonderfully concrete. If a small portion of tokens receives most of the attention value, then eviction should not be blind to that concentration.2

The lab’s heavy-hitter policy is intentionally simple:

score each cached token by accumulated attention received
reserve some cache for recent tokens
evict low-score non-recent tokens first

The real H2O paper goes much further: it studies the emergence of heavy hitters, relates them to co-occurrence, frames eviction as a dynamic submodular problem, and validates on multiple model families and tasks.2 But the toy policy already shows the central move. Eviction becomes measurement.

There is an important asymmetry here. Once a token is evicted, an ordinary decode step cannot observe its future attention because the key is gone. So the policy must preserve enough candidates to keep learning. That is why recent tokens remain in the budget. They are not always important yet, but they need a probation period.

In production terms:

recency is exploration
heavy-hitter score is exploitation

Prompt-Time Voting Is a Different Bet

SnapKV is motivated by a different setting: long prompts with much shorter generation. Think document QA, long summarization, codebase questions, or annual reports. The prompt itself can dominate KV memory before the model has generated many tokens.

SnapKV observes that attention heads often focus on specific prompt features during generation, and that these patterns can be obtained from an observation window near the end of the prompt.3 It then selects clustered important KV positions for each head.

The lab’s observation-vote policy is a cartoon version:

look at the end-of-prompt observation window
score old prompt positions by attention from that window
keep the high-vote prompt positions plus a rolling recent window

When the observation window asks the same kind of question generation will answer, this works well. When the task drifts, it can be stale. In the topic drift scenario, dynamic heavy hitters can adjust during generation, while a purely prompt-time vote is slower to adapt.

This is a good example of a broader serving pattern:

prefill knows the prompt
decode learns the response

A cache policy can use one or both.

Layer Budgets Are Another Axis

The lab pretends there is one attention layer and one cache budget. Real transformers are not that tidy.

PyramidKV reports a “pyramidal information funneling” pattern: lower layers scatter attention more widely, while higher layers consolidate onto critical tokens such as attention sinks.4 Its policy allocates different cache sizes across layers rather than using one uniform budget.

That should not be surprising. If layers do different work, a uniform retention rule is another hidden assumption. A token might be useful in lower-layer local composition but irrelevant in higher-layer answer selection, or vice versa.

The cache policy is not one question. It is a stack of questions:

which layer?
which head?
which prompt segment?
which generation phase?
which quality failure are we willing to risk?

What This Lab Verifies

The JavaScript backing the figure is not a benchmark. It is a controlled toy world with known attention mass. That lets the audit check the mechanics:

every synthetic attention vector sums to one
attention weights are nonnegative
each policy obeys the cache budget at every step
retained attention mass stays between zero and one
sink+window beats sliding when sink mass is present
heavy hitters beat sliding in the fact-heavy setting
observation voting retains old facts in the needle setting

Those are small claims, but they are falsifiable. They keep the visualization honest.

The larger claim is architectural:

KV-cache compression is not just smaller storage.
It is an approximation to the model's future attention computation.

That is why good methods look like memory managers, online algorithms, and model interpretability tools at the same time. They are deciding what the model is still allowed to look at.

The cache does not forget uniformly. It forgets by policy.

  1. Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis, “Efficient Streaming Language Models with Attention Sinks,” ICLR 2024. arXiv. ↩ ↩2 ↩3

  2. Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Re, Clark Barrett, Zhangyang Wang, and Beidi Chen, “H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models,” NeurIPS 2023. arXiv. ↩ ↩2 ↩3

  3. Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen, “SnapKV: LLM Knows What You are Looking for Before Generation,” NeurIPS 2024. OpenReview. ↩ ↩2

  4. Zefan Cai, Yichi Zhang, Bofei Gao, Yuliang Liu, Yucheng Li, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Junjie Hu, and Wen Xiao, “PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling,” 2024. arXiv. ↩