Random KV Cache Eviction Matches SOTA: 32–43% Faster

KV cache eviction is an arms race of scoring functions: H2O's accumulated attention, SnapKV's recent window, R-KV's attention-plus-redundancy blend, VaSE's value magnitudes, TriAttention's position-dependent key statistics. Each paper's premise: a better score decides what survives compression. A paper posted Sep 3 by Heng Wang et al. (Salesforce AI Research & UIUC) tested that premise with a coin flip. The receipts: evicting uniformly at random, per attention head, with no score at all, matches the strongest scored evictor across 4 models and 6 reasoning tasks — and serves 32–43% more tokens per second in vLLM. It was significantly ahead in 31 of 60 comparisons. Behind in one.

The Problem: Long Reasoning Fills the Cache

Reasoning models generate chains of thought that run to tens of thousands of tokens, and the KV cache grows linearly with every generated token — at scale, it's the memory bottleneck, not the weights. The established fix is eviction: keep a per-head budget K of KV pairs plus a small recent buffer, and periodically score every cached token by how much it will matter later, dropping the losers. Five years of work is a sequence of better scores. The question nobody had asked directly: does the score actually decide anything?

The Method: Pin the Prompt, Evict at Random

Random Attention keeps two things and scores nothing. First, the prompt is pinned — it never enters the eviction lottery. Second, everything else is decided per attention head by uniform random draws each time the buffer fills and the cache must shrink back to budget K. No calibration, no tuning, no scoring pass. Same decode-phase eviction framework as R-KV and VaSE: identical budgets, identical buffers, only the selection signal differs — and one arm has none.

flowchart LR
    A["Long chain-of-thought
generation"] --> B["KV cache grows
to memory bottleneck"]
    B --> C{"Eviction policy"}
    C -->|"score each token"| D["H2O / SnapKV / R-KV
VaSE / TriAttention"]
    C -->|"no score — random draw
per head, prompt pinned"| E["Random Attention"]
    D --> F["Scoring pass overhead
every eviction round"]
    E --> G["Same accuracy
32–43% higher throughput"]
            

The Results: A Coin Flip Ties the State of the Art

Across Qwen3-4B, 14B, 32B and Phi-4-reasoning, on MATH500, GPQA-Diamond, pooled AIME 2025/26, HMMT and LiveCodeBench-v6, at roughly 4× compression (~3× on code), random ties or beats everything. Paired clustered-bootstrap tests put it significantly ahead in 31 of 60 baseline cells and significantly behind in exactly one — LiveCodeBench on Qwen3-32B, by about three points, traced to prompt length, not selection quality. On code, the scored methods fall apart: SnapKV loses 20–35 points to random on every model, and VaSE collapses on Phi-4-reasoning (29 points behind). The throughput number is the deployment headline: at 32k-token generations in vLLM, 32–43% more tokens per second than the strongest baseline — there is no scoring pass.

Why Scores Don't Matter: The Trace Protects Itself

Two controlled experiments explain the embarrassment. First, the prompt is the fragile part of the cache. Prior evictors differ mainly in whether their score happened to keep the prompt; pin it for everyone and most of the gap between methods vanishes — each method gains back almost exactly what its score had been costing it. Second, the reasoning trace is redundant at two levels: in the text, the model restates what it still needs as it works, and across heads, every attention head holds its own copy of every token while eviction decides per head. A planted-fact probe shows a fact kept in one head is almost never retrieved; kept in several, it almost always is. A random draw retains enough copies. What a score still buys is the rare fact stated once and never restated — and reasoning traces seldom produce one.

Limitations

This is a compression-regime result: on short generations where the cache never gets tight, eviction doesn't pay. The competition-math comparisons ride on small samples — 30-problem AIME sets with ±5-point run-to-run variance — though 16 sampled runs per problem and the significance tests blunt that. Long code prompts are the edge case: LiveCodeBench prompts average 557 tokens, and that's where the one significant baseline win (TriAttention on Qwen3-32B) lives. Porting an evictor to a paged runtime like vLLM is real engineering work, and the evaluation covers four open reasoning models, not every architecture.

Why Builders Should Care

If you serve reasoning models under a memory budget, Random Attention is a deployable default — open-source, no tuning, and the fastest evictor at equal accuracy. Pin your prompt regardless of evictor; that single rule recovers most of what the fancy scores cost you. And if you're building a new selection signal, the bar is now brutal and cheap to test: beat a coin flip. The deeper point survives the specifics — five papers of scoring machinery were, at the margin, modeling their own prompts, not the value of their traces.

Verdict: receipts, not rhetoric. Five years of scoring refinements, and the strongest of them ties uniform random at equal accuracy while serving 32–43% fewer tokens per second. Keep the prompt. Randomize the rest. Audit your baseline against a dice roll before you publish another score.