A reasoning model generating thirty thousand tokens builds a key-value cache it cannot afford to keep. Every method for shrinking it works the same way: score each cached token by how much it will matter later, keep the winners, drop the rest. This paper replaces the score with a coin flip — pin the original prompt permanently, then evict uniformly at random inside each attention head — and it matches the strongest scoring evictor across four models and five reasoning tasks, while serving 32–43% more tokens per second because there is no scoring pass to run. The control that makes the case: force every rival method to keep the prompt too, and the differences between them mostly vanish. Random eviction gains 41.5 points from that one rule; the strongest scorer gains 0.2. The score was not selecting well. It was protecting the question, and that was nearly all it was doing.
The setting is decode, not long-context reading: a short question followed by a very long chain of thought. Every generated token adds a key-value pair per head, so the cache grows linearly with the trace and quickly dominates memory. An evictor gives each head a fixed budget K and, whenever a small buffer fills, throws away everything above it. The only question is which pairs survive.
Now the mechanism itself. Random Attention's rule is two lines long: give every prompt position a score of positive infinity, give every generated position a uniform random draw, keep the top K. Independently, per head. The infinity is doing something structural — it is not a tie-break, it is a hard reservation — and the slider below shows why that matters more than anything the random draw does.
Without the reservation, a uniform draw treats the ninety-odd tokens of the question exactly like the twenty thousand tokens of scratch work, so the question is the first thing to go — statistically, almost all of it. With the reservation the question is never at risk and the budget contest is only ever over the trace. That single difference is what section 03 measures, and it is worth 41.5 points.
The comparison set is the real one: SnapKV, R-KV, VaSE and TriAttention, each of which computes a per-token importance estimate, against a rule that computes nothing. Full-cache accuracy is the ceiling nobody reaches under a budget.
Across the four models and the full comparison grid, Random Attention comes out significantly ahead in 31 of 60 baseline comparisons and behind in none of the aggregate readings the paper reports. Sweep the compression ratio from 2× to 16× and it stays tied with the strongest scorer the whole way: at 2× every method sits near full attention, and as the budget tightens the two of them pull away from VaSE together. There is no crossover where the score starts earning its keep.
Here is the experiment the paper is really built on. Take each evictor, keep its own scoring function exactly as designed, and bolt on one extra rule: the prompt is never evicted. If the scores were selecting well, this should do very little — a good scorer already keeps the important tokens, and the question is obviously important. Measure what each method gains.
Read the four numbers as a set. SnapKV gains 12.6 points, because its score was losing part of the question. R-KV and VaSE gain almost nothing, because their scores were already keeping it. Random eviction gains 41.5, because on its own it keeps nothing in particular. The rule pays each method exactly in proportion to how much of the prompt its score was failing to hold — which is another way of saying the score's contribution, once the prompt is safe, is close to zero.
Once the question is safe, why does throwing away random pieces of the working-out not hurt? Because the working-out is written redundantly. The model restates what it still needs as it goes — a chain of thought is full of "so we have x = 3" repeated in four different sentences — and separately, each attention head carries its own copy of the trace.
The head-level version is measurable. Plant a synthetic fact about 1,500 tokens before the question and then ask how often it can be retrieved when only some heads keep it.
One head recovers the planted fact 3% of the time. Two heads recover it 60%. That is wildly superadditive — a pair is worth twenty times the sum of its singles — and it is the whole argument for why a random draw is safe. A uniform sample does not need to pick the right copy. It needs to leave some copies standing across the eight heads, which it does with high probability at any sensible budget.
The block test isolates the text-level half. Random eviction removes tokens scattered through the trace, so redundant restatements survive somewhere. Removing a contiguous run destroys all copies of whatever was said in that stretch — and it costs nothing up to 64 tokens, only starting to bite at 256. That is a direct read on how far apart the restatements sit.
Matching a scorer on accuracy would be a curiosity. The reason it matters is that the scoring pass itself costs real serving throughput: it walks the paged key-value state every eviction step, and skipping it is free speed.
Turn that into the number a service owner cares about. If your reasoning endpoint is throughput-bound, a percentage on tokens per second is a percentage off the fleet.
The fleet arithmetic is illustrative — a real endpoint has a request mix, a latency target and a prompt-length distribution the paper does not model. The ratios driving it are measured: one H200, 11k-token prompts, 32k-token generations, 128 concurrent requests, K=2048. And the honest caveat sits in the same table: this is the decode regime, a short prompt followed by a long generation. On a long-context task where a fact appears once and is never restated, the redundancy argument does not hold, and selection is a real skill again.