Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

2609.03430 ↗ · 2026-09-03 · cs.CL

Heng Wang, Jielin Qiu, Wenting Zhao, Cheng Qian, Liangwei Yang, Jiawei Han, Heng Ji, Silvio Savarese, Shelby Heinecke, Huan Wang

The finding

Headline claim

For KV cache eviction in reasoning LLMs, the selection signal contributes almost nothing: keeping the prompt and evicting uniformly at random per head matches the strongest scored evictors while serving 32 to 43 percent higher throughput, because the prompt is the fragile part and the reasoning trace protects itself via redundancy.

The test

Four reasoning models (Qwen3-4B/14B/32B, Phi-4-reasoning) across six tasks (MATH500, GPQA-D, AIME pooled, HMMT, LiveCodeBench v6) at roughly 4x cache compression (3x for code), with paired clustered bootstrap significance tests, controlled prompt-protection ablations, a planted-fact probe, and vLLM serving throughput at 32k-token generations.

Effect size & scope

Random Attention is significantly ahead in 31 of 60 baseline cells, significantly behind in one (TriAttention on LiveCodeBench with Qwen3-32B, about 3 points, traced to long prompts). It delivers 32 to 43 percent higher serving throughput than TriAttention in vLLM. Prompt protection alone recovers 12 to 22 points for SnapKV and 42 to 60 points for a recency window, showing prior gaps were mostly protection, not signal. Gaps widen in Random Attention's favor as compression tightens from 2x to 16x. Holds at 4x compression on math, science, and most code settings; long prompts consume budget and remain open.

Limitations

Authors concede: prompt pinning can consume a large variable share of the budget on code tasks, and smarter prompt compression is left to future work; a content signal may still be needed for rare once-stated facts, which their traces seldom contain but other workloads might. Unstated: results are limited to math/science/code reasoning on four open-weight models, short prompts (average 200-token questions), eviction only (not sparse attention), accuracy measured by boxed-answer match, and small competition-math sets (30 to 60 problems) with roughly plus-or-minus 5 point run-to-run variance; production RAG or long-document workloads are untested.

Counterpoint

A skeptic would note the null result may be trace-specific: chains of thought that restate intermediates are exactly the regime where random eviction works, so generalization to retrieval-heavy or multi-turn agentic workloads is unproven. Baselines were run as released with their default prompt handling, which the authors themselves show conflates score and protection; AIME/HMMT cell sizes are tiny; and the throughput win partly follows from skipping any scoring pass, an expected property of a scoring-free method rather than a surprising result.

Economy implication

Marginal for AI economics in the next 12 to 24 months beyond a modest inference-efficiency data point: it suggests memory-bound serving of reasoning models can be cheaper than assumed, since KV cache compression needs no learned scoring, slightly lowering serving costs for long chains of thought. If nothing else, it signals that serving-stack optimization is still finding easy wins, reinforcing the pattern of falling cost per unit of useful output.

Who this matters for

Technical Capability: Researchers building KV cache compression should treat prompt protection plus random eviction as the null their scoring signals must beat, redirecting effort to prompt budgeting and rare-fact recovery.

Market & Valuation: Serving providers of reasoning models get a tuning-free, higher-throughput eviction default, a small but real reduction in memory-bound inference cost.

Bears on (advisory · papers never write evidence)

[3.1] Inference cost per unit of capability is falling rapidly.

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.