Random attention: why KV cache eviction doesn't need a scoring function

I've spent enough time tuning KV cache eviction policies to have opinions about which scoring heuristic is least bad. So when I read Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning — Wang, Qiu, Zhao, Qian, Yang, Han, Ji, Savarese, Heinecke, and Wang, posted September 3 — my first reaction was skepticism. The claim: for long chain-of-thought reasoning, you can drop the scoring step entirely, evict cached tokens uniformly at random, and match the accuracy of the best scored evictor while running 32-43% faster in vLLM. Across four models and six reasoning tasks. No score computed, anywhere.

That's not a small efficiency trick. It's a challenge to the premise nearly every KV cache compression method shares.

The paradigm being replaced

Long chain-of-thought reasoning is expensive largely because the KV cache grows with every token the model writes, including the thousands of tokens of intermediate reasoning it produces before an answer. The standard fix is eviction: rank cached tokens by some estimate of future importance — accumulated attention mass, a running "heavy hitter" count, a heuristic proxy for relevance — and discard the lowest-ranked ones. Methods in this lineage differ in scoring detail, but they all agree on the method: compute a signal, keep the top of it.

Random Attention keeps the one structural choice that lineage makes — protect the prompt — and deletes the rest of the machinery. Within the reasoning trace, it evicts tokens uniformly at random, independently per attention head, with no score, no ranking, no running statistics to maintain.

What the paper actually measures

The headline result: across four models and six reasoning benchmarks, Random Attention matches the strongest scored evictor the authors compare against. It isn't winning by exploiting a quirk of one benchmark — the authors report it as a general finding — and it converts directly into a systems win: 32-43% higher throughput than that evictor when deployed in vLLM. Removing the scoring computation isn't just conceptually simpler, it's cheaper per token, and that shows up directly in serving throughput.

A result like this needs a mechanism, not just a benchmark table, or it's just a curiosity. The paper supplies one, built from two controlled experiments.

Why a coin flip does as well as a score

The prompt is the fragile part of the cache. The authors show that once you control for other differences between scoring methods, most of the accuracy gap between evictors traces back to a single binary fact: did the method's selection signal happen to keep the prompt intact? Evictors that protect the prompt — whether by design or by the accident of scoring it highly — perform well. Evictors that let prompt tokens get scored low and evicted degrade sharply. The sophistication of the scoring function contributes almost nothing once this one factor is accounted for.

The reasoning trace protects itself. Once the prompt is safe, what happens inside the trace barely matters, because the trace carries its own redundancy at two levels. In the text itself, the model habitually restates what it still needs — a long chain of thought re-derives and re-references earlier steps as it works, so losing one mention of a fact rarely means losing the fact. Across attention heads, each head maintains its own copy of what it's attending to in the trace, so a token evicted from one head's cache doesn't take the information out of the model's reach entirely. A uniformly random draw, applied independently per head, is statistically likely to leave enough surviving copies of anything that actually mattered.

Put together: the prompt needs protecting because it has little redundancy — each prompt token typically says something once. The trace doesn't need the same protection, because it says most things more than once. Scoring the trace is solving a problem that redundancy already solved.

Why this matters for anyone serving reasoning models

If you're running long chain-of-thought models in production, the KV cache is very often the actual bottleneck on throughput and concurrency, not FLOPs. Every scored eviction method adds computation to the hot path of decoding — some cheaper than others, but none free — and usually requires extra memory to hold running statistics per token. Random Attention's mechanism costs a random number generator and a fixed prompt boundary. That's a meaningfully smaller footprint to implement, tune, and keep correct across model and hardware changes, and the 32-43% throughput gain the authors report in vLLM is the kind of number that changes a capacity planning conversation, not just a leaderboard entry.

My take

The result I find most useful here isn't the throughput number, it's the diagnosis: the field had been building increasingly elaborate scoring functions to solve a problem that turns out to be almost entirely about one design decision — protect the prompt — plus a property the reasoning trace already has for free. That's a pattern worth watching for elsewhere in LLM systems work: when a broad class of methods converges on similar performance despite very different mechanisms, it's worth asking whether they're all quietly relying on the same one or two things that actually matter, dressed up in different amounts of engineering. Here, the extra engineering wasn't just unnecessary, it was strictly worse, since it cost throughput without buying accuracy. I'd want to see this replicated on trace lengths well beyond what's in the paper, and on tasks with less redundant intermediate reasoning — terse chains of thought, code, tool-call sequences — before treating uniform random eviction as a default. But as a starting point for anything serving long chain-of-thought models today, it's the one I'd reach for first.