Paper Walkthrough: Random Attention — Throwing KV Cache Entries Away at Random Works Just as Well

The importance score that decides what leaves the KV cache turns out to buy almost nothing. Keep the prompt, evict uniformly at random inside each head, and you match the strongest prior evictor while serving 32-43% more tokens per second in vLLM. A walkthrough of the measurements across four models and six tasks, and the two controlled experiments that explain them.

Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

The paper that stopped trying to pick well

The original title is "Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning" (Heng Wang et al., Salesforce AI Research / University of Illinois Urbana-Champaign, arXiv:2609.03430, 3 September 2026).

The abstract goes like this. Reasoning models emit chains of thought long enough that the KV cache becomes a severe memory bottleneck. Every existing KV cache compression method shares one paradigm — score each cached token by an estimate of how much it will matter later, keep the top scorers — and that selection signal contributes almost nothing. Random Attention keeps the prompt and evicts uniformly at random within each attention head, computing no score at all. Across four models and six reasoning tasks it matches the strongest prior evictor, and it serves 32–43% higher throughput than that evictor under vLLM. Two things explain it: (1) the prompt is the fragile part of the cache, and most of the gap between methods is just whether their score happened to keep it; (2) the reasoning trace protects itself with redundancy at two levels — in the text, because the model restates what it still needs, and across attention heads, because each head holds its own copy.

What everyone treated as a ranking problem was really a protection problem. The code is public at SalesforceAIResearch/Random-Attention on GitHub.

Setup: the cache is filled by the model's own writing

A transformer stashes the Key and Value of every past token and reuses them (KV caching from scratch covers the mechanism). That cache grows linearly with generation length, and for reasoning models that is fatal: in the paper's setting (§2), a model answering a ~200-token math question may generate more than 10,000 tokens of thought. What fills the cache is not the user's input but the model's own prose.

One remedy is eviction — physically discarding key-value pairs once the cache hits a budget. Discarded pairs are gone for good. Unlike sparse attention, which keeps everything resident and merely attends to a subset, eviction is the only route that actually bounds peak memory. In the paper's framework the cache holds a persistent budget of $K$ pairs plus a buffer of the $r$ most recent ones ($r \ll K$), so an eviction fires every $r$ decode steps. Each candidate outside the buffer gets a score $s_i$, and the top $K$ survive:

Equation (1) just says: out of the candidate set $\mathcal{C}_t$, keep the $K$ positions with the highest score $s_i$. $\mathcal{S}_t$ is the set that survives the round.

The only thing separating prior methods is how they build $s_i$

Rewritten in one notation (§2), every major method collapses to a choice of $s_i$. H2O accumulates the attention weight a position has received since it entered the cache. SnapKV sums attention from only the last $w$ queries. R-KV blends the SnapKV score with a redundancy term $(1-\bar c_i)$, where $\bar c_i$ is the mean cosine similarity of $k_i$ to the other cached keys, so a restated fact is not kept twice. VaSE scores value magnitude rather than keys. TriAttention scores distance from the current query through a trigonometric series whose coefficients are calibrated per head. The field is a lineage of better scores, and the shared premise is that the score decides accuracy under compression.

Most of those scores are built from attention weights — a softmax over Query-Key dot products. How peaked that distribution is changes what "take the top $K$" even means: on a flat distribution, the top $K$ and an arbitrary $K$ are not far apart. The paper does not measure attention entropy, but the intuition helps the results go down.

Random Attention is two decisions

The method (§3) is startlingly short. The idea is to separate the irreplaceable input from the model's own scratch work: the question is stated once and cannot be recovered if evicted, whereas the trace keeps rewriting the intermediates it still needs.

1. Protect the question. Positions $1,\dots,\ell_{\mathrm{p}}$ — the entire prefill, meaning system prompt, chat template and question — are never evicted.
2. Scatter the rest, per head. Every remaining position gets an i.i.d. uniform random score, and each KV head keeps its own top $K$ independently.

Equation (2) reads: give prompt positions an infinite score so they always survive, and roll a die for everything else. $\ell_{\mathrm{p}}$ is the prompt length and $u_i$ is a uniform draw between 0 and 1. The implementation is one rand and one topk. The paper's own framing is the sharpest one available: this is the weakest selection signal anyone can write down, which makes Random Attention both a deployable method and a null hypothesis. Any scorer that cannot beat it at matched budget is not extracting usable information from its signal.