Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning
Heng Wang and colleagues at Salesforce AI Research, UIUC and Cornell show that the token-importance scores every KV cache evictor computes are close to worthless: evicting uniformly at random inside each head matches the strongest prior evictor while serving 32 to 43% higher throughput.
Ask this paper
Random Attention is the whole method: keep the prompt, then evict uniformly at random within each attention head, computing no score at all. It matches the best scored evictor across four models and six reasoning tasks.
The prompt is the fragile part: most of the measured gap between competing selectors is just whether their scoring signal happened to protect the prompt, not whether it ranked reasoning tokens well.
The trace protects itself twice over: redundancy in the text, because the model restates what it still needs as it works, and redundancy across heads, because each head keeps its own copy. Once the prompt is safe, a random draw retains enough copies.
32 to 43% higher throughput in vLLM: the win comes precisely from deleting the scoring machinery, so the gain is real deployment speed rather than a benchmark number.
Why it matters: an entire subfield has been optimizing a signal that contributes almost nothing. This is the rare negative result with a faster system attached.
Abstract
Large language models achieve superior performance on tasks that require extended reasoning, but long chains of thought make the KV cache a severe memory bottleneck. Existing KV cache compression methods share one paradigm: score each cached token by some estimate of how much it will matter later, and keep the top-scoring ones. We show that the selection signal contributes almost nothing. Random Attention keeps the prompt and evicts uniformly at random within each attention head, computing no score at all; across four models and six reasoning tasks it matches the strongest prior evictor while serving 32-43% higher throughput than it in vLLM deployment. Controlled experiments explain this by showing that 1) the prompt is the fragile part of the cache, and most of the gap between selectors is just whether their selection signal happened to keep it; 2) the reasoning trace protects itself against eviction with redundancy at two levels, in the text (the model restates what it still needs as it works) and across attention heads (each keeps its own copy of the trace), so once the prompt is safe, a random draw retains enough copies of what the model still needs, and no score is required to pick them. Our code is publicly available at https://github.com/SalesforceAIResearch/Random-Attention.