Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning
Heng Wang, Jielin Qiu, Wenting Zhao, Cheng Qian, Liangwei Yang, Jiawei Han, Heng Ji, Silvio Savarese, et al.
cs.CL
Quick verdict
Argues eviction scores add little: keep prompt + random per-head eviction matches strongest baselines on 4 models, 6 tasks; rigorous, convincing null result.
Summary
This paper argues that the selection signal in KV cache eviction contributes almost nothing for reasoning workloads. It proposes Random Attention, which pins the entire prompt and evicts uniformly at random within each attention head, computing no score. Across Qwen3-4B/14B/32B and Phi-4-reasoning, on MATH500, GPQA-D, pooled AIME 2025-2026, HMMT, and LiveCodeBench-v6 at about 4x compression, it matches the strongest baselines (SnapKV, R-KV, VaSE, TriAttention): significantly ahead in 31 of 60 main-table cells and significantly behind in one (TriAttention on Qwen3-32B code). In vLLM on H200 it serves 32-43% more tokens per second than TriAttention at 32k-token generations (1.58-2.67x full attention). Controlled experiments attribute baseline gaps to prompt protection: adding a prompt-pinning rule closes most gaps (Tables 2 and 6), and a planted-fact probe shows reasoning traces self-protect through textual restatement and per-head copies. The boundary is a fact stated once and never restated: Random Attention retrieves a passcode 0% of the time versus R-KV's 84% (Table 3). Limitations: small competition-math sets (30-60 problems), no multiple-comparison correction across roughly 60 tests, a paged serving comparison limited to TriAttention, synthetic single-model probes, and concurrent work reaching similar protection-dominance conclusions.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- The selection signal in KV cache eviction contributes almost nothing once the prompt is protected: keeping the prompt and evicting uniformly at random per head matches the strongest scored baselines across four models and six reasoning tasks.
- Random Attention serves 32-43% higher throughput than TriAttention in vLLM at 32k-token generations (1.58-2.67x full attention) because it runs no scoring pass.
- The prompt is the fragile part of the cache: imposing prompt protection on every baseline closes most inter-method gaps, with gains tracking each method's logged prompt-survival deficit.
- Reasoning traces self-protect via two redundancy levels - textual restatement and per-head copies - so a random draw retains enough usable copies; a fact held in one head is retrieved 3% of the time, in all eight heads 99%.
- The boundary case is a fact stated once and never restated: Random Attention retrieves a passcode 0% of the time versus R-KV's 84% (Table 3).
Strengths
Controlled disentangling of protection vs selection signal
The matched-protection grid (Tables 2 and 6, fifteen model-task settings) gives every baseline the same prompt-pinning rule; gains are ordered by logged prompt-survival deficits (SnapKV retains 0.32-0.42 union and gains +35.2 on Phi-4 GPQA-D, while R-KV retains 0.55-0.91 and never gains more than 1.9 points). This is the paper's core identification device and it is convincing.
Statistical discipline unusual for systems-adjacent ML work
Every margin is gated by a paired, problem-clustered percentile bootstrap (95% CI) plus an exact sign test; cells use 2-16 independently sampled runs; per-cell run-to-run standard deviations are tabulated (Table 8); probe confidence intervals use instance-clustered bootstrap with 4,000 replicates.
Honest efficiency reporting
Well-validated mechanistic instrument
Calibrated baselines in one engine
Weaknesses
Headline vs the Qwen3-14B appendix results
No multiple-comparison correction
Paged serving comparison covers only one baseline
Mechanistic generality rests on one small model
Novelty is regime-specific amid concurrent work
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper targets decode-time KV cache **eviction** for reasoning LLMs (long chains of thought at a 32k budget), explicitly distinguished from sparse-attention selection that keeps all pairs in memory. The central claim is a negative result: the selection signal contributes almost nothing. A signal-free policy - keep the prompt, evict uniformly at random per KV head (Eq. 3) - matches the strongest scored evictors (SnapKV, R-KV, VaSE, TriAttention) on Qwen3-4B/14B/32B and Phi-4-reasoning across MATH500, GPQA-D, pooled AIME 2025-2026, HMMT and LiveCodeBench-v6 at ~4x compression (~3x for code), and serves 32-43% more throughput in vLLM. Two mechanistic claims explain it: prompt fragility (§5.1) and two-level redundancy of the reasoning trace (§5.2), with an explicitly bounded failure mode for once-stated facts (§5.3, Table 3).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is Random Attention in KV cache eviction?
Random Attention is a KV cache eviction policy for reasoning LLMs that keeps the entire prompt (the question and system text) and evicts all other cached tokens uniformly at random, independently within each attention head, without computing any importance score. The paper shows it matches the accuracy of the strongest scoring-based evictors across four models and six reasoning tasks while serving faster.
Why does random KV cache eviction work as well as scored eviction?
According to the paper, two reasons: (1) the prompt is the only irreplaceable content, and many scored methods lose parts of it, which explains most of their gaps; (2) the reasoning trace is redundant - the model restates what it still needs, and every attention head keeps its own copy of every token - so a random draw retains enough usable copies once the prompt is safe.
How much faster is Random Attention than other KV eviction methods?
In vLLM on one NVIDIA H200 with 32k-token generations, it delivers 1.58-2.67x full-attention throughput and 32-43% more tokens per second than the strongest prior evictor (TriAttention), because it skips the scoring pass entirely. In an equal-memory batched setting it reaches 8.8-10x full-attention throughput.
When does random KV cache eviction fail?
When a needed fact is stated exactly once and never restated. In the paper's passcode probe (a synthetic fact planted 57 eviction rounds before a question), Random Attention reproduced the passcode 0% of the time, while R-KV - which accumulates attention over the whole history - retrieved it 84% of the time.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Metadata lists 8 authors; the paper byline carries 10 (Shelby Heinecke and Huan Wang added) - this review is keyed to the byline.
- Figures 1-5 are extracted as scattered axis/tick text only; all numbers cited in this review are taken from the tables and in-text figures of merit, not from reading the plots.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.