Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

AI summary

Overview

Research area: Efficient inference for large language models — specifically KV cache compression (eviction) during long chain-of-thought reasoning.

Technical level: Intermediate. The core idea is simple, but the experiments assume familiarity with attention, KV caching, and serving frameworks such as vLLM.

Scope: The paper proposes a signal-free KV cache eviction policy that keeps the prompt and evicts uniformly at random per attention head, shows it matches the strongest learned scoring baselines across four models and six reasoning tasks, and explains why selection scores contribute almost nothing.

What This Paper Is About

Every existing KV cache eviction method for reasoning follows the same paradigm: assign each cached token a score estimating how much it will matter later, then keep the top-scoring tokens. The authors test whether that scoring signal is actually doing the work. Their answer is no: a policy that pins the prompt and otherwise evicts tokens uniformly at random per head matches the strongest baseline while serving substantially faster, because the prompt is the fragile part of the cache and the reasoning trace is redundantly stored in ways that survive random pruning.

Key Contributions

1. A signal-free eviction policy. Random Attention keeps all prefill positions (system prompt, chat template, question) with score $+\infty$ and assigns every other cached position an i.i.d. $\mathrm{Uniform}(0,1)$ score, keeping the top-$K$ independently per KV head. The entire per-eviction cost is one rand and one topk.
2. Evidence that the selection signal is near-worthless. Across Qwen3-4B, Qwen3-14B, Qwen3-32B and Phi-4-reasoning, and six reasoning tasks, Random Attention is significantly ahead in 31 of the 60 baseline cells of the main table and significantly behind in one.
3. A controlled explanation in two parts. (a) The prompt is the fragile element: giving every baseline the same prompt-protection rule erases most of the gap between methods. (b) The working state protects itself via redundancy in the text and across attention heads, so a random draw retains enough copies of what the model needs.
4. A measured deployment benefit. In vLLM with PagedAttention on one H200, Random Attention serves 32–43% higher throughput than TriAttention at matched budget, because it never runs a scoring pass.

Main Findings

• Random selection matches learned selection. On Qwen3-4B at MATH500 ($K{=}1024$), Random Attention scores 0.874 against TriAttention's 0.864, with full attention at 0.939. On Phi-4-reasoning GPQA-D ($K{=}2048$), it scores 0.678 against TriAttention's 0.684, with full attention at 0.707. On Qwen3-32B LiveCodeBench ($K{=}3072$), it scores 0.806 against TriAttention's 0.834, with full attention at 0.886.
• Signal buys nothing on math and science. Random Attention beats VaSE and SnapKV significantly on every model on MATH500 and GPQA-D, and R-KV significantly on Qwen3-4B. No selector beats it significantly on these tasks; nominal leads of 0.3–0.6 points on two GPQA-D cells sit inside the noise.
• Competition math separates only under tighter budgets. On AIME (30 problems each for 2025 and 2026, pooled) and HMMT (60 problems), run-to-run standard deviation is $\pm 5$ points, and nominal VaSE leads of 1.7 and 1.5 points on Qwen3-32B run opposite to the trend seen when budgets tighten.
• Code reasoning is the exception, and the prompt explains it. LiveCodeBench prompts average 557 tokens, six times MATH500's under the same tokenizer, and the longest can consume up to half of the $K{=}3072$ budget. SnapKV loses 20–35 points to Random Attention on every model, and VaSE collapses on Phi-4-reasoning at 0.373, 29 points behind. TriAttention's roughly three-point lead on Qwen3-32B is the single significant baseline win, traced to prompt length rather than the selection signal.
• Tighter budgets widen the gap against non-protecting selectors. From 2× to 16× compression on Qwen3-4B and Phi-4-reasoning across the four math and science tasks, Random Attention stays tied with TriAttention while both pull away from VaSE.
• Protecting the prompt erases most of the baseline gap. Giving every method the same keep-the-prompt rule produces gains proportional to how much of the question each score had been losing: SnapKV gains up to 22.5 points (Phi-4-reasoning GPQA-D), VaSE gains 4.2 and 10.2 points on Phi-4-reasoning but little on Qwen3-4B, and R-KV, which retained the most prompt already, never gains more than 1.9 points. After the rule, the three baselines land within 2.2 points of one another in every setting.
• Losing the prompt is catastrophic; cutting the trace at random is not. Without the rule, a recency window scores as low as 0.09 and Random Attention falls to 0.23–0.76. With the rule, Random Attention is the best policy in every setting and a plain recency window comes within two points of the best baseline.
• Copies pool across attention heads. In a planted-fact probe where the fact sits 1,536 tokens before the question and the cache is evicted 15 times in between, only three of Qwen3-4B's eight KV heads retain a usable trace alone; the best single head yields the value in 3% of trials and the next in 1%. Two heads together yield it in 60% of trials, three in 83%, and all eight in 99%. Two different facts held in different heads give $R{=}0.31$ together against 0.10 and 0.16 alone.
• The shape of surviving copies does not matter. Dealing the fact out token by token so no head holds a readable span changes retrieval from 0.39 to 0.33 and recall from $R{=}0.76$ to $R{=}0.75$. On real MATH500 traces, keeping history in contiguous blocks costs nothing up to block size 64; accuracy drops only at block size 256, where the budget leaves a head four blocks ($K{=}1024$) or two ($K{=}512$).
• What a signal still buys is a rare once-stated fact. For a passcode announced once, 57 compression rounds before the question, Random Attention retrieves it in 0.000 of traces ($\log p = -18.35$), SnapKV in 0.004 ($-11.11$), TriAttention in 0.016 ($-11.11$), VaSE in 0.344 ($-3.88$), and R-KV in 0.836 ($-0.71$). R-KV, the best needle-finder, leads only one column of the main table, while TriAttention, the strongest baseline there, recovers almost nothing here.
• Serving throughput. Under vLLM with PagedAttention on one H200 ($K{=}2048$, 1k-token prompts, 32k-token generations, 128 requests), Random Attention reaches 2046 tok/s on Qwen3-4B (1.58× full attention), 1737 on Phi-4-reasoning (2.23×), 1819 on Qwen3-14B (1.97×), and 923 on Qwen3-32B (2.67×) — margins of +37%, +43%, +40% and +32% over TriAttention.
• Where the scoring cost goes. One eviction round costs 0.30 ms under Random Attention and 1.47–1.64 ms under TriAttention. With 128 concurrent requests each compressed every 64 of its own tokens, vLLM compresses some request roughly 62k times per workload at a synchronisation point between batched steps. On Qwen3-14B, TriAttention's extra 910 s over a 32k run amounts to about 15 ms of whole-batch waiting per compression.
• A second efficiency protocol. At equal memory on one 143 GB H200 at $K{=}3072$ with 32k generations, full attention fits 28 (Qwen3-4B) and 20 (Qwen3-14B) concurrent sequences while compressed caches fit 109–200. Random Attention fits the largest batch at the smallest peak footprint (101 and 89 GB) and reaches 10.0× and 8.8× full-attention throughput; at the $K{=}1024$ of MATH500 the same protocol reaches 28.8×. The authors note the threefold gap to TriAttention here reflects an unfused re-implementation of its scorer, not the method itself, and that 32–43% is the margin they claim.

Methodology in Plain English

The authors set up eviction as a periodic process: the cache holds a fixed budget of $K$ key-value pairs plus a small recent buffer, and every time the buffer fills, a method scores every candidate outside the buffer and keeps the top $K$. They replace the score with a coin flip per cached position, except that all prompt positions are forced to survive.

They then run this against four prior evictors — SnapKV, R-KV, VaSE and TriAttention — at an equal budget and matched prompt protection, using FlashAttention-2 kernels without PagedAttention, across four models and six tasks. Budgets are set at roughly 4× compression of each task's typical trace (roughly 3× for LiveCodeBench). Answers are judged by whether the final boxed answer is correct. Each claim of a margin is gated by a paired, problem-clustered percentile bootstrap with a 95% confidence interval plus an exact sign test.

To explain the result, they run two controlled experiments. First, they replay every baseline with an explicit keep-the-prompt rule and log how much of the prompt each original score was retaining, so that the effect of the score can be separated from the effect of prompt protection. Second, they build a planted-fact probe: a synthetic variable and value are inserted into real model-generated MATH500 reasoning traces, with a question requiring that value appended at the end. The experimenter controls which KV heads keep the fact, while standard per-head uniform eviction runs everywhere else. Success is measured by whether greedy decoding reproduces the value, and — because retrieval falls to zero in hard conditions — by a graded recall $R$ comparing the model's log-probability of the correct value against the all-kept and all-deleted references, scored on the same 250–500 planted traces.

Why This Matters

Impact on research: The paper reframes KV cache eviction from a ranking problem to a protection problem. If the selection signal contributes almost nothing beyond uniform random selection, then the open questions move to what an evictor protects — how to budget long prompts, and how to recover rare facts that only a content-dependent signal can preserve. It also establishes a null hypothesis any new scorer must beat at matched budget and matched prompt protection.

Real-world applications:

• Serving reasoning models under a fixed GPU memory budget, where longer chains of thought translate directly into more concurrent requests.
• Code generation and code-reasoning assistants, where prompts are long and a naive selector can lose 20–35 points.
• Long chain-of-thought deployments (math, science, competition-style problem solving) where the trace, not the prompt, fills the cache.
• Any paged-attention serving stack where content-dependent scoring must traverse block tables layer by layer and stalls the whole batch at each synchronisation point.

Industry relevance: Random Attention needs no calibration, no tuning and no scoring pass, which makes it cheap to integrate into existing vLLM deployments. The measured benefit is 32–43% higher throughput than the strongest prior evictor at matched budget, with the smallest peak footprint in the equal-memory comparison.

Future Directions

• Prompt budgeting. On code tasks, protecting the entire prompt consumes a substantial fraction of the cache budget; much of a code prompt is scaffolding (I/O formats, harness instructions) that a smarter rule might compress rather than pin whole. The authors explicitly leave this to future work.
• Recovering once-stated facts. The passcode experiment shows a residual niche where content-dependent signals such as R-KV's accumulated attention genuinely beat random selection. Determining when that niche is worth paying a scoring pass for is unresolved.
• Protocol standardisation. The paper argues comparisons across prior work partly compare protection regimes rather than scores, and points to concurrent work on prompt-boundary guarding and on folding eviction into training.
• Re-examining prior random-baseline claims. The authors attribute earlier reports that random retention trails scored selection to random baselines that lost the prompt, and suggest the same confound may affect other results in this literature.

Target Audience

Inference and systems engineers who serve reasoning models under memory budgets; KV cache and long-context compression researchers who need a matched-budget null hypothesis for new scoring functions; and practitioners evaluating whether a scoring pass is worth its cost in a paged serving stack. Some background in attention and LLM serving is assumed, but the central argument — protect the prompt, don't bother ranking the rest — is stated in plain terms.

Authors’ 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.