Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

TL;DR: An entire subfield has been building ever-cleverer importance scores to decide which KV-cache entries to evict during long chain-of-thought generation. This paper shows the score is nearly worthless: pin the prompt, evict everything else uniformly at random, independently per attention head, and you match the strongest published evictor across four models and six reasoning benchmarks—while serving 32–43% higher throughput in vLLM because you never compute a score. The mechanistic explanation is the real payoff: reasoning traces are self-protecting because the model restates what it still needs (redundancy in the text) and every KV head holds its own copy of every token (redundancy across heads). The only fragile thing in the cache is the prompt.

The problem: reasoning models drown in their own thoughts

A reasoning model answering a 200-token math question may generate 10,000–30,000 tokens of chain of thought. Every generated token adds a key-value pair to every attention head in every layer, so the KV cache grows linearly and quickly becomes the binding constraint on how many requests fit on a GPU. At 32k tokens, a single full-length Qwen3-32B request carries over 8 GB of KV.

Eviction attacks this by keeping a fixed budget of K cached pairs per head and permanently discarding the rest as decoding proceeds. (This is stricter than sparse attention, which attends to a subset but keeps everything in memory.) The framework, standardized by recent work: keep a small buffer of the r most recent tokens, and every r steps run an eviction round—assign each cached position i a score s_i, keep the top-K, discard the rest forever.

The whole literature is a sequence of better s_i: accumulated attention (H2O), attention from a recent query window (SnapKV), attention plus a key-redundancy penalty (R-KV), value magnitude (VaSE), calibrated position-dependent key statistics (TriAttention). The shared premise: which tokens you keep is what decides accuracy under compression.

The method that shouldn't work

Random Attention is a two-line policy:

where \ell_{\mathrm{p}} is the prompt length. Never evict the prompt; give every trace token an i.i.d. uniform score, drawn independently in each KV head, and keep each head's top-K. The per-eviction cost is one rand and one topk. No calibration, no attention statistics, nothing to tune.

The authors frame this as both a deployable method and a null hypothesis: any selector that can't beat it at matched budget and matched prompt protection is not extracting usable information from its signal.

It works

At roughly 4× compression of typical trace length, across Qwen3-4B/14B/32B and Phi-4-reasoning, on MATH500, GPQA-Diamond, AIME 2025+2026, HMMT, and LiveCodeBench:

With paired, problem-clustered bootstrap tests, Random Attention is significantly ahead in 31 of 60 baseline comparisons and significantly behind in exactly one (TriAttention on Qwen3-32B code, by ~3 points—more on that below). Sweeping compression from 2× to 16× widens the gap in random's favor: at 2× everyone is near full attention; as budgets tighten, Random Attention stays tied with the best method while VaSE falls away.

So a decade's worth of scoring heuristics—cumulative attention, recency windows, value statistics—contribute essentially nothing over noise. The interesting question is why.

Why: the cache has two very different halves

The paper's diagnosis is that the KV cache during reasoning contains two kinds of content with opposite failure modes. The prompt is stated once and never restated; lose it and it's gone. The trace—the working state of the computation—is written and rewritten continually as the model reasons.

Finding 1: the prompt is the fragile part, and it explains most of the differences between prior methods. Prior evictors quietly differ in whether the prompt survives: TriAttention pins the whole input by rule; SnapKV, R-KV, and VaSE keep only attention-sink tokens and let their score decide the rest. So published comparisons across papers were partly comparing protection regimes, not scores. The controlled experiment: give every method the same "keep the prompt" rule and re-measure.

The pattern is diagnostic: each method gains exactly as much as its score had been losing of the question, measured by logging prompt survival round by round. SnapKV, whose score retains the least of the prompt, gains up to +22.5 points; R-KV, which already retains most of it, never gains more than 1.9. Once everyone keeps the prompt, the baselines land within ~2 points of each other—and where a residual gap survives protection, it runs in random's favor (all three protected learned scores trail Random Attention by 4–6 points on Qwen3-4B). This also explains why earlier evaluations reported random baselines falling far behind scored selection: their random baselines were losing the prompt.

Finding 2: the trace protects itself with two levels of redundancy. In the text: reasoning traces continually restate the intermediates still in use, so a value that matters rarely lives at one position only (this was R-KV's observation—ironically, used there to penalize redundancy). Across heads: every KV head holds its own copy of every token, and per-head eviction means copies die independently.

The cross-head level is established with a planted-fact probe that's the most satisfying part of the paper (§5.2). Insert a synthetic fact (Let zq = 4729) into real reasoning traces, 1,536 tokens—15 eviction rounds—before a question that needs it. Then control exactly which heads keep it, pinning the fact's tokens in a chosen set of heads and force-evicting it everywhere else. The results on Qwen3-4B (8 KV heads):

• Best single head: fact retrieved in 3% of trials. Next best: 1%.
• Those same two heads together: 60%.
• Three heads: 83%. All eight: 99%.

Pooling is strongly superadditive—a pair is worth many times the sum of its singles. It even crosses facts: two values held in different heads, both needed for the answer, give graded recall R = 0.31 together against 0.10 and 0.16 alone. And the shape of the surviving copies doesn't matter: dealing the fact out token-by-token across heads so no head holds a readable span barely moves retrieval (0.33 vs. 0.39). What matters is whether some usable copy survives somewhere, not which head or in what configuration. Independent per-head random draws are almost the optimal policy for maximizing "some copy survives somewhere"—which is exactly what a signal-free method does for free.

A nice twist in Appendix D: on real traces at 4× compression, a shared draw (same random positions in every head, killing cross-head diversity) scores within 0.3 points of Random Attention—because the text-level redundancy already keeps a restated copy of anything needed. The two redundancies are substitutes; the cross-head level is load-bearing only for facts the text doesn't restate, which is precisely the probe's regime.

What a selection signal is still for

The paper is careful to map the boundary. Plant a passcode stated once, 57 compression rounds before the question, with no restating. Random Attention retrieves it 0% of the time (\log p = -18.35: effectively gone). R-KV, whose score accumulates attention over the whole history, retrieves it 84% of the time. So needle-finding is real selection skill—but strikingly, it neither implies nor follows from aggregate accuracy: R-KV, the best needle-finder, leads only one column of the main table, while TriAttention, the strongest baseline overall, recovers the passcode almost never (1.6%). On real reasoning traces the once-stated-never-restated case is rare, because the model keeps restating what it uses.

The throughput dividend

Skipping the scoring pass matters more than its raw kernel time suggests. One eviction round costs 0.30 ms for Random Attention (pure compaction) vs. 1.47–1.64 ms for TriAttention—a few percent of single-stream decode time. But under vLLM serving with 128 concurrent requests, some request gets compressed at nearly every decode step, each compression happens at a synchronization barrier where all 128 requests wait, and content-dependent scores are extra expensive under paging (fused kernels don't materialize attention weights; cache statistics require an extra pass through block tables). The small cost multiplies into a large one.

In an unpaged equal-memory setting the compressed cache buys 3–10× over full attention for every evictor (the small cache is what admits the big batch), and at MATH500's tighter budget Random Attention hits 28.8× full-attention throughput. Integration cost is the other quiet win: porting an attention-weight scorer into a paged runtime is ~849 lines across 13 vLLM files; adding Random Attention to TriAttention's plugin took one function.

What to make of it

If this holds, the practical takeaway is blunt: the accuracy of an evictor is decided by what it protects, not by how it ranks the rest. Random-plus-prompt-protection should become the default baseline that any new selection signal must beat at matched budget and matched protection—a null hypothesis the field has been skipping. It also redirects research toward the two places selection genuinely matters: budgeting long prompts, and recovering rare once-stated facts.

Reasons for caution:

• The regime is specific. Short prompt, long self-generated trace, on tasks (math, science, competition problems) where models naturally narrate their working state. Long-context understanding—big document in, short answer out—is explicitly a different regime, and the paper's own passcode experiment proves random eviction fails when redundancy is absent. Code is the visible crack: LiveCodeBench prompts average 557 tokens (6× MATH500's), the longest consume half the budget, and TriAttention's one significant win is 32B code. Tasks with long-range, non-restated references (large codebases, agentic tool traces with sparse pointers) may behave more like the passcode than like MATH500.
• Compression was pushed to 16×, not further, and only on math/science; whether the redundancy argument survives more aggressive budgets is open. The headline grid is ~4×.
• Eviction can lengthen generation (the model re-derives what it lost). Appendix E checks this: Random Attention is the shortest- or near-shortest-generating evictor, so parity isn't bought with extra tokens—but it's worth remembering that all evictors generate ~15–35% longer traces than full attention.
• The 32–43% margin is against TriAttention specifically, the only strong baseline with a vLLM port; the threefold gaps elsewhere use an unfused reimplementation, which the authors flag honestly.

There's also a lesson beyond KV caches: the planted-fact probe is a genuinely nice piece of mechanistic methodology, showing the transformer performs distributed, superadditive readout across heads—each head's copy is weak alone, but the model pools fragments across heads (and even across facts) at read time. That's relevant to anyone thinking about how information is stored and retrieved in attention, not just to serving engineers.

Where to spend your time: Section 5 is the heart of the paper—§5.1's protection-controlled comparison and §5.2's planted-fact probe carry the argument; §5.3 marks the honest boundary of the claim. Appendix D's keep-log measurements (prompt survival rates per method, the "soft recency window" interpretation of random eviction) reward a second read.