Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning
AuthorsHeng Wang, Jielin Qiu, Wenting Zhao, Cheng Qian, Liangwei Yang, Jiawei Han, Heng Ji, Silvio Savarese, Shelby Heinecke, Huan Wang
Instead of carefully scoring which tokens to keep, this work shows that protecting the prompt and randomly evicting the rest can make long-form LLM reasoning substantially faster.
Key results
Random Attention was significantly ahead in 31 of 60 baseline comparisons.
It delivered up to 43% higher throughput than TriAttention.
Random Attention reached 2.67× full-attention throughput on Qwen3-32B.
Retrieval reached 99% when all eight Qwen3-4B KV heads retained the fact.
R-KV recovered a once-stated passcode 84% of the time after 57 compression rounds.
What the paper found
A Salesforce study challenges the assumption that KV-cache eviction for long-chain reasoning requires sophisticated token-importance scores. Random Attention permanently protects the entire prompt, then assigns independent uniform-random scores within each attention head and retains the top-K entries, eliminating the scoring pass. Across Qwen3-4B, Qwen3-14B, Qwen3-32B, and Phi-4-reasoning on six reasoning tasks, including MATH500, GPQA-D, AIME, HMMT, and LiveCodeBench-v6 medium, it matched the strongest prior evictor and was significantly better in 31 of 60 baseline comparisons. In vLLM serving on a single NVIDIA H200 with 32k-token generations, it delivered 32–43% higher throughput than TriAttention, reaching 2.67× full-attention throughput on Qwen3-32B. Controlled experiments identify prompt retention—not ranking quality—as the main accuracy determinant: reasoning traces are redundantly represented because models restate intermediate information in text and preserve copies across heads. In a planted-fact probe on Qwen3-4B, retrieval rose from 3% for the best single head to 99% when all eight KV heads retained the fact. The limitation is nonredundant information: after 57 compression rounds, Random Attention never recovered a passcode stated once, while R-KV retrieved it 84% of the time. The paper therefore positions Random Attention as both a deployable default and a null hypothesis: future eviction methods must demonstrate gains beyond prompt protection and uniform per-head coverage.
Original 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.
Read the original paperMore in Efficient AI
Browse all 55 papers →Decoding Looped Transformers Better for (Almost) Free
Weihao Liu, Huangjie Zheng, Tianrong Chen, Rohit Dilip, Richard He Bai, Yizhu Jiao, Yuyang Wang, Ruixiang Zhang
LoopCD turns the partially computed states of looped Transformers into free guidance, improving accuracy while often cutting inference compute nearly in half.
Scaling Laws for Looped Mixture of Experts
Yanbei Chen, Anirudh Goyal, Raghuraman Krishnamoorthi
This work develops scaling laws that explain how looping and sparse experts can be combined to build more capable models with less training and inference compute.
When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse
Yiyu Liu, Minlan Yu, Juncheng Yang
For LLM prefix caches, simple recency may beat fancy eviction rules, especially when workloads follow predictable session patterns.