H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models

Eviction as the third lever

There are three ways to shrink the KV cache. You can store each entry in fewer bits (quantization). You can compress the cache's structure (grouped-query attention, latent attention). Or you can simply keep fewer entries — decide that some cached tokens are not worth their memory and evict them. The third lever is the most aggressive, because dropping a token's key and value means it can never again contribute to attention; it is gone. The question H2O answers is which tokens you can afford to drop, and its answer rests on a sharp empirical observation about how attention is actually distributed.

Attention is sparse, and concentrated on a few

If you accumulate the attention scores across a generation — for every token, sum the attention weight it receives from all the later positions that query it — the distribution is heavily skewed. A small fraction of tokens absorb the overwhelming majority of the total attention mass. The paper calls these tokens Heavy Hitters (H2). Most positions, once past, are attended to only weakly by everything that follows; a few positions remain attention magnets for the rest of the sequence. The attention matrix, in other words, is effectively sparse, and the sparsity is structured — it picks out a persistent set of important tokens.

This is the foundation for eviction. If most tokens contribute negligibly to future attention, then evicting them costs almost nothing, and the cache can be held at a fraction of the full sequence length as long as you keep the heavy hitters. The heavy hitters carry the load; the rest are deadweight you are paying memory to retain.

A greedy oracle you can actually run

The ideal policy would be an oracle: knowing the entire future, keep exactly the tokens that will turn out to matter and evict the rest. That oracle is unavailable at generation time — you cannot see the attention a token will receive from positions that have not been generated yet. H2O approximates it with a greedy policy driven by accumulated attention scores so far. Each cached token carries a running sum of the attention it has received up to the current step. When the cache is full and a new token must be admitted, the token with the lowest accumulated attention score is evicted. Tokens that have been important historically are retained; tokens that have been ignored are dropped.

The greedy local rule turns out to be a good stand-in for the unavailable global oracle, because attention importance is persistent — a token that has been a heavy hitter so far tends to remain one. The paper frames the eviction formally as a dynamic submodular problem and shows the greedy heuristic enjoys the kind of near-optimality guarantee that submodular structure provides, which is the theoretical backbone under the simple "evict the least-attended" rule.

Heavy hitters plus a recent window

H2O does not keep heavy hitters alone. It maintains the high-scoring historical tokens together with a window of the most recent tokens, which are kept regardless of their accumulated score because local context — the tokens immediately preceding the current position — is reliably important to the next prediction and may not yet have accumulated a high score simply because few positions have queried them. The retained cache is therefore a union of two sets: the persistent heavy hitters scattered anywhere in the history, and the recent local window. This combination is what lets a small cache budget reproduce full-attention behavior closely, and it echoes a pattern that recurs across the cache-eviction literature — keep the structurally special positions plus the recent ones.

Results: small cache, intact quality, more throughput

The empirical claim is that H2O matches full-cache model quality while retaining only a fraction of the KV entries, evaluated across a range of tasks on OPT, LLaMA, and GPT-NeoX models without any fine-tuning. Because the cache is the constraint that limits how many sequences you can batch and how long they can run, shrinking it frees memory that converts directly into larger batches and higher concurrency. The paper reports throughput improvements up to roughly 29× against strong inference baselines on these models — the cache reduction letting far more work stay resident on the GPU at once. As with the other tuning-free cache methods, the appeal is that it bolts onto an existing checkpoint with no retraining.

Where it sits among the alternatives

H2O is best understood alongside its neighbors. StreamingLLM keeps a fixed, structural set — the first few attention-sink tokens plus a recent window — and evicts everything else by position; it is simple and bounded but blind to content, so a genuinely important token in the middle of the document is dropped along with the unimportant ones. H2O is content-aware: by scoring on accumulated attention it can retain an important mid-sequence token wherever it sits, at the cost of having to track the attention-score history that the selection depends on. And quantization (INT8, or 2-bit schemes like KIVI) is orthogonal — it shrinks each retained entry rather than choosing which to retain — so eviction and quantization compose, evicting the unimportant tokens and storing the survivors in fewer bits.

Limitations

Eviction is irreversible, and the greedy score is an approximation of an unknowable future. A token that looked unimportant by its accumulated attention and got evicted is unrecoverable, so if a later query would have wanted it, the information is simply absent — the failure mode is silent, showing up as a subtly wrong continuation rather than an error. The accumulated-attention bookkeeping also adds overhead relative to a position-only policy like a plain sliding window, which is the price of being content-aware. And as with every cache-compression method, the guarantee is statistical: it preserves quality on average across tasks at a given budget, while any specific long-range dependency that happened to ride on an evicted token can still be lost. The contribution is showing that attention's concentration on a few heavy hitters is strong and persistent enough that a cheap greedy eviction can exploit it without retraining the model.