Random Attention

The result

The selection signal contributes almost nothing

We evaluate at a roughly 4×-compressed cache budget on MATH500, GPQA-Diamond, AIME 2025, AIME 2026, HMMT and LiveCodeBench, on Qwen3-4B/14B/32B and Phi-4-reasoning, with matched budgets and paired significance tests throughout. Random Attention matches the strongest prior evictor on every model, is significantly ahead of a baseline in 31 of the 60 main-table comparisons, and is significantly behind in exactly one (code reasoning on Qwen3-32B, explained below).

Pushing compression harder does not change the ordering. From 2× to 16×, on both model families, Random Attention stays tied with TriAttention while the gap from both to VaSE opens — compression pressure widens the gap in the random policy's favour.

Mechanism I

The prompt is the fragile part of the cache

Methods disagree about the prompt: TriAttention keeps the whole input by default, while SnapKV, R-KV and VaSE keep only sink tokens and leave every slot to the score. Giving every method the same rule — keep the prompt, score only the generated trace — separates the score from the protection, and the rule pays each method according to how much of the question its score was losing: SnapKV, whose score retains the least of the prompt, gains up to +22.5 points; R-KV, which already retains the most, never gains more than 1.9. Once every method keeps the prompt, the three baselines land within 2.2 points of one another in every setting — and every learned score still trails the policy that ranks nothing.

Losing the prompt is catastrophic; cutting the trace at random is not. That is what makes the prompt the fragile part of the cache.

Mechanism II

The reasoning trace protects itself

Why does random eviction of the trace not hurt? Because the trace is stored redundantly at two levels. In the text: the model restates the intermediates it still needs as it works, so a needed value usually has a recent copy. Across attention heads: every head holds its own copy of every token, and eviction decides per head which copies die — a token is only lost when every head happens to drop it. A planted-fact probe makes the second level visible: we insert a synthetic fact into real reasoning traces 1,536 tokens before a question that needs it (15 eviction rounds pass in between) and control which KV heads keep it. A fact surviving in a single head is almost never retrieved (3%), while the same fact surviving in several heads is retrieved almost always (99% with all eight) — and the shape of the surviving copies barely matters.

The boundary

What is left for a selection signal

The one case a signal-free policy cannot cover is a fact stated once, never restated, and needed much later — the case redundancy cannot reach. In a passcode probe (announced once, 57 eviction rounds before the question), Random Attention never reproduces it, while R-KV — whose score accumulates attention over the whole history — finds it 84% of the time. Needle-finding is real selection skill, but it neither implies nor follows from aggregate strength: R-KV, the best needle-finder, leads only one column of the main grid, and TriAttention, the strongest baseline there, recovers almost nothing. On real traces the case is rare, because the model keeps restating what it is still using. The other honest cost is code reasoning: prompts average 557 tokens (six times MATH500's), so pinning them consumes a large share of the budget — the setting behind the single significant baseline win.

Serving

No scoring pass means real speed

Random Attention needs no calibration, no tuning, and no per-step scoring. Under paged vLLM serving it delivers 1.6–2.7× full-attention throughput across the four models — 32–43% more than TriAttention on the same kernels at 32k-token generations, a margin that holds at capacity. In an iso-memory benchmark (largest batch fitting one H200), the compressed cache fits 109–200 concurrent sequences where full attention fits 20–28, and Random Attention reaches up to 10× full-attention throughput at K=3072 and 28.8× at MATH500's tighter K=1024. It is also the baseline any new selection signal has to beat, at matched budget and matched prompt protection.

Implications & future work

What this changes for eviction research

Two practical implications follow. First, Random Attention is a deployable method in its own right: it needs no calibration, no tuning and no scoring pass, and it is the fastest evictor we measured at equal accuracy — a reasonable default for serving reasoning models under a memory budget, and the baseline any new selection signal has to beat at matched budget and matched prompt protection. Second, the findings redirect what eviction research should optimise: the accuracy of an evictor is decided by what it protects, not by how it ranks the rest.

That moves the open questions to where protection still matters:

• Budgeting long prompts. On code reasoning, pinning the whole prompt consumes a large share of the cache budget, yet much of a code prompt is scaffolding (I/O formats, harness instructions) that a smarter rule might compress rather than pin whole. We leave this to future work, since Random Attention's value as a null lies in having nothing to tune.
• Recovering rare once-stated facts. A fact stated once, never restated, and needed much later is the one case only a content-dependent signal can preserve — real selection skill, but one that current aggregate benchmarks neither reward nor measure.

Use it

Try it on your own model

The repository contains the eviction engine (every method in the paper as an eviction mode), the evaluation harness, the paired significance tests, the efficiency benchmarks and the vLLM port.

git clone https://github.com/SalesforceAIResearch/Random-Attention && cd Random-Attention
bash setup.sh && . env.sh

# one (model, task, method, budget) accuracy cell
scripts/run_cell.sh Qwen3-4B math random_pp   # Random Attention, K defaults to the ~4x point
scripts/run_cell.sh Qwen3-4B math triattn     # strongest baseline, per-model calibration
scripts/grade_cell.sh Qwen3-4B math_K1024 random_pp,triattn_ph_memofix

Citation

BibTeX

@article{wang2026random,
  title         = {Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning},
  author        = {Wang, Heng and Qiu, Jielin and Zhao, Wenting and Qian, Cheng and
                   Yang, Liangwei and Han, Jiawei and Ji, Heng and Savarese, Silvio and
                   Heinecke, Shelby and Wang, Huan},
  journal       = {arXiv preprint arXiv:2609.03430},
  year          = {2026},
  eprint        = {2609.03430},
  archivePrefix = {arXiv},
  primaryClass  = {cs.CL}
}

References

Key references

1. Zhang et al. "H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models." NeurIPS 2023.
2. Li et al. "SnapKV: LLM Knows What You are Looking for Before Generation." NeurIPS 2024.
3. Cai et al. "R-KV: Redundancy-aware KV Cache Compression for Reasoning Models." NeurIPS 2025.
4. Chang et al. "Value-Aware Stochastic KV Cache Eviction for Reasoning Models (VaSE)." arXiv:2606.03928.
5. Mao et al. "TriAttention: Efficient Long Reasoning with Trigonometric KV Compression." ICML 2026.
6. Xiao et al. "Efficient Streaming Language Models with Attention Sinks." ICLR 2024.
7. Kwon et al. "Efficient Memory Management for Large Language Model Serving with PagedAttention." SOSP 2023.
8. X. Wang. "How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers." arXiv:2604.17935.