Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

Hugging Face Daily Papers Papers
kv-cache-eviction reasoning llm efficiency memory-optimization random-attention throughput

Summary

The paper proposes Random Attention, a KV cache eviction method that uses random selection instead of scoring, matching selective methods while improving throughput in reasoning tasks.

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.
Original Article
View Cached Full Text

Cached at: 09/04/26, 03:56 AM

Paper page - Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

Source: https://huggingface.co/papers/2609.03430

Abstract

Random eviction of reasoning tokens matches selective KV cache compression because reasoning traces are self-protecting through redundancy, making scoring unnecessary once prompts are preserved.

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. ExistingKV cache compressionmethods 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) thereasoning traceprotects itself against eviction withredundancyat two levels, in the text (the model restates what it still needs as it works) and acrossattention 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.

View arXiv pageView PDFAdd to collection

Get this paper in your agent:

hf papers read 2609\.03430

Don’t have the latest CLI?curl \-LsSf https://hf\.co/cli/install\.sh \| bash

Models citing this paper0

No model linking this paper

Cite arxiv.org/abs/2609.03430 in a model README.md to link it from this page.

Datasets citing this paper0

No dataset linking this paper

Cite arxiv.org/abs/2609.03430 in a dataset README.md to link it from this page.

Spaces citing this paper0

No Space linking this paper

Cite arxiv.org/abs/2609.03430 in a Space README.md to link it from this page.

Collections including this paper0

No Collection including this paper

Add this paper to acollectionto link it from this page.

Similar Articles

Random Attention (GitHub Repo)

TLDR AI

Random Attention presents a signal-free KV-cache eviction policy for reasoning models that matches or exceeds the performance of learned methods on benchmarks like MATH-500 and LiveCodeBench, while being faster in inference.

Epiphany-Aware KV Cache Eviction Without the Attention Matrix

arXiv cs.LG

This paper introduces EpiKV, a KV cache eviction method that scores token importance via changes in internal representations (epiphany score) instead of attention weights, avoiding the need to materialize the attention matrix. It achieves competitive performance on reasoning benchmarks while enabling up to 16× longer context lengths.

Information-Aware KV Cache Compression for Long Reasoning

arXiv cs.CL

This paper proposes InfoKV, an entropy-aware KV cache compression framework that combines token-level predictive uncertainty with attention scores to improve long-context reasoning efficiency. Experiments show it outperforms existing attention-based methods on Llama-3.1, Llama-3.2, and DeepSeek-R1.

Thought-Aware KV Cache Compaction for Reasoning via Adaptive Attention Matching

arXiv cs.CL

This paper introduces Thought-Aware Attention Matching (TAM), a method for compressing KV caches during long chain-of-thought reasoning by segmenting reasoning traces, adaptively allocating compression budgets, and protecting pivotal tokens. Experiments on AIME 2024 and MATH-500 with Qwen3-4B show significant memory reduction while maintaining accuracy.