# Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

arXiv: https://arxiv.org/abs/2609.03430 · HTML: https://mlsanity.com/paper/2609.03430/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 44 of its 48 references that are in the map.
- First posted on arXiv 3 Sep 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)
- Efficient LLM inference and serving / [Efficient reasoning and agent inference](https://mlsanity.com/inference/efficient-reasoning-and-agent-inference/)

## Builds on (most cited first, 30 of 44)

- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache](https://mlsanity.com/paper/2402.02750/) (2024)
- [KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization](https://mlsanity.com/paper/2401.18079/) (2024)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time](https://mlsanity.com/paper/2305.17118/) (2023)
- [PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling](https://mlsanity.com/paper/2406.02069/) (2024)
- [MathArena: Evaluating LLMs on Uncontaminated Math Competitions](https://mlsanity.com/paper/2505.23281/) (2025)
- [DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads](https://mlsanity.com/paper/2410.10819/) (2024)
- [Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference](https://mlsanity.com/paper/2407.11550/) (2024)
- [Retrieval Head Mechanistically Explains Long-Context Factuality](https://mlsanity.com/paper/2404.15574/) (2024)
- [Phi-4-reasoning Technical Report](https://mlsanity.com/paper/2504.21318/) (2025)
- [LM-Infinite: Zero-Shot Extreme Length Generalization for Large Language Models](https://mlsanity.com/paper/2308.16137/) (2023)
- [R-KV: Redundancy-aware KV Cache Compression for Reasoning Models](https://mlsanity.com/paper/2505.24133/) (2025)
- [KeyDiff: Key Similarity-Based KV Cache Eviction for Long-Context LLM Inference in Resource-Constrained Environments](https://mlsanity.com/paper/2504.15364/) (2025)
- [NACL: A General and Effective KV Cache Eviction Framework for LLMs at Inference Time](https://mlsanity.com/paper/2408.03675/) (2024)
- [SeerAttention-R: Sparse Attention Adaptation for Long Reasoning](https://mlsanity.com/paper/2506.08889/) (2025)
- [TriAttention: Efficient Long Reasoning with Trigonometric KV Compression](https://mlsanity.com/paper/2604.04921/) (2026)
- [Cache What Lasts: Token Retention for Memory-Bounded KV Cache in LLMs](https://mlsanity.com/paper/2512.03324/) (2025)
- [LazyEviction: Lagged KV Eviction with Attention Pattern Observation for Efficient Long Reasoning](https://mlsanity.com/paper/2506.15969/) (2025)
- [The Pitfalls of KV Cache Compression](https://mlsanity.com/paper/2510.00231/) (2025)

## Built on by (most cited first, 1 of 1)

- [Spend Bytes on Breadth: Precision-Count Trade-offs for Decode-Time KV Compression in Long Chain-of-Thought Reasoning](https://mlsanity.com/paper/2610.05685/) (2026)

## Abstract (arXiv)

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 baseline in task performance while delivering 32-43% higher throughput than that method when deployed with vLLM. 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.