Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

Random Attention. Rethinking KV Cache Eviction for Efficient Reasoning. By Heng Wang and nine others, from Salesforce AI Research and the University of Illinois Urbana-Champaign. Published on the third of September. Its code repository is worked out: about one hundred source files, with a readme and a licence.

Long chains of thought make the key-value cache a severe memory bottleneck, and every existing compression method shares one paradigm to deal with it: score each cached token by some estimate of how much it will matter later, then keep the top-scoring ones. This paper's claim is that the selection signal contributes almost nothing. Their method keeps the prompt, evicts uniformly at random within each attention head, and computes no score whatsoever.

Across four models and six reasoning tasks, random eviction matches the strongest prior evictor, while serving between thirty-two and forty-three percent higher throughput than it in deployment. The throughput gain is the direct consequence of the negative result: scoring every cached token costs something, and if the score buys nothing, not computing it is free speed. But the controlled experiments explaining why are the more valuable part. First, the prompt is the fragile part of the cache, and most of the apparent gap between competing selectors turns out to be just whether their signal happened to preserve it. Second, the reasoning trace protects itself against eviction through redundancy at two separate levels. In the text, because the model restates what it still needs as it works. And across attention heads, because each head keeps its own copy of the trace. So once the prompt is safe, a random draw retains enough copies of whatever the model still needs, and no score is required to find them.

Notice how much of the claim rests on the reasoning setting specifically. The self-protecting redundancy comes from a model restating its own working, which is a property of long chains of thought rather than of language models generally. The result is reported across four models and six reasoning tasks, and nothing here establishes what happens to a cache carrying no such trace, such as a long document being read rather than a chain of thought being written.

The reframing is that the field was solving the wrong problem carefully. The question was never which tokens to keep, it was whether the prompt survives, and once you protect that explicitly the sophisticated part of the machinery turns out to have been paying for itself with nothing.

Random Attention. Rethinking KV Cache Eviction for Efficient Reasoning. By Heng Wang and nine others, from Salesforce AI Research and the University of Illinois Urbana-Champaign. Published on the third of September. This is the long version: the whole paper rather than the abstract.

This is a negative result, and it is the useful kind: it does not merely say the existing methods fail, it says what they were actually doing when they appeared to succeed. A whole line of research turns out to have been improving something that was not the bottleneck, and the paper explains what was.

The setting first. Reasoning models generate chains of thought running to tens of thousands of tokens, and the key-value cache grows linearly with that, so memory becomes the constraint. Eviction methods keep a fixed budget of cache entries and discard the rest as decoding proceeds. Every one of them follows the same paradigm: score each cached token by an estimate of how much it will matter later, and keep the top-scoring ones. The literature is a sequence of better scores. Accumulated attention, then attention from a recent window, then attention combined with redundancy, then value magnitude, then position-dependent key statistics. Each new score is motivated by a heuristic observed to correlate with accuracy, and the shared premise underneath all of them is that the score is what decides accuracy under compression.

Random Attention tests that premise by removing the score entirely. It keeps the prompt, and then evicts uniformly at random within each attention head. No scoring pass, no calibration, nothing to tune. Across four models and six reasoning tasks spanning maths, science and code, it is comparable to the strongest baseline, and significantly ahead in thirty-one of the sixty comparisons in the main table. Because it never runs a scoring pass, it serves between thirty-two and forty-three percent more tokens per second than the strongest baseline at thirty-two thousand token generations.

The second experiment explains why the rest of the cache tolerates random eviction, and it is the more interesting half. The reasoning trace protects itself, redundantly, at two levels. In the text, because a model working through a problem restates what it is still using. And across attention heads, because every head holds its own copy of every token, and eviction decides per head which copies die. A planted-fact probe shows the model reading a value from whichever heads still hold it: a fact retained in only one head is almost never retrieved, a fact retained in several almost always is, and the particular shape of the surviving copies does not matter. So once the prompt is safe, a random draw keeps enough copies of whatever the model still needs, and no score is required to find them.

The one cell where a baseline is significantly ahead is code reasoning on the largest model, and the authors trace it to prompt length rather than to the selection signal: code prompts are long enough that protecting the whole prompt consumes a substantial share of the cache budget. That is a consistent story rather than an excuse, because it locates the exception in the same variable the rest of the paper says matters. The throughput figures range from about one point six to two point seven times full attention across the four models, and the margin over the strongest baseline is largest on the smallest model, where the scoring pass is a bigger share of the work. Two practical implications follow. Random Attention is deployable on its own terms, needing no calibration, no tuning and no scoring pass, which also makes it the baseline any new selection signal now has to beat at matched budget and matched prompt protection. That second point is the sharper one: previous comparisons were not matched on prompt protection, so they were partly measuring a rule rather than a score.

There is no limitations section, so the boundaries have to be read off the argument. Everything here is reasoning workloads, and the self-protecting redundancy is a property of a model restating its own working, not of long context generally. A long document being read rather than a chain of thought being written has no such redundancy, and nothing here speaks to it. The planted-fact probe is a constructed test rather than a natural one.

The redirection the authors propose is the part to keep. The accuracy of an evictor is decided by what it protects, not by how it ranks the rest. That moves the open questions to how to budget long prompts, particularly for code, and how to recover the rare fact that gets stated once. Both are questions about protection, and neither is a better score.