Summary (Overview)

• Random Attention is a signal-free KV cache eviction policy that keeps the prompt and evicts uniformly at random within each attention head, computing no score at all.
• Across four models (Qwen3-4B, 14B, 32B, Phi-4-reasoning) and six reasoning tasks, it matches the strongest prior evictor (TriAttention) while serving 32–43% higher throughput in vLLM deployment.
• The paper demonstrates that the selection signal contributes almost nothing: the prompt is the fragile part of the cache, and the reasoning trace protects itself through redundancy at two levels (text-level restatement and cross-head duplication).
• In 31 of 60 baseline comparisons, Random Attention is significantly ahead; only one cell (code reasoning on Qwen3-32B) shows a baseline significantly ahead, traced to prompt length rather than selection quality.
• The method requires no calibration, no tuning, and no scoring pass, making it both a deployable method and a null hypothesis for future eviction research.

---

Introduction and Theoretical Foundation

Background and Motivation

Reasoning models solve hard problems by generating chains of thought that can run to tens of thousands of tokens. The key-value (KV) cache grows linearly with generation length, creating a severe memory bottleneck. KV cache eviction methods address this by keeping a fixed budget of KV cache entries and discarding the rest as decoding proceeds.

The Prevailing Paradigm

Existing KV cache eviction methods follow a single paradigm: score each cached token by an estimate of how much it will matter later, and keep the top-scoring ones. This line of work includes:

• H2O (Zhang et al., 2023): accumulated attention scores
• SnapKV (Li et al., 2024): attention from a recent window
• R-KV (Cai et al., 2025): attention combined with redundancy penalty
• VaSE (Chang et al., 2026): value magnitude
• TriAttention (Mao et al., 2026): position-dependent key statistics

The premise behind all of these is that the score decides accuracy under compression. The paper tests this premise directly and shows it is largely false.

Formal Setting

At step $t$, an attention head holds $N$ cached key-value pairs $(k_i, \nu_i)$, $i = 1, \ldots, N$, with $k_i, \nu_i \in \mathbb{R}^d$. The head forms its output from the current query $q_t$ as:

$$o_t = \sum_{i \leq N} \alpha_i^{(t)} v_i, \quad \alpha_i^{(t)} = \frac{\exp\left(q_t^{\top} k_i / \sqrt{d}\right)}{\sum_{j \leq N} \exp\left(q_t^{\top} k_j / \sqrt{d}\right)}, \tag{1}$$

where $\alpha_i^{(t)}$ is the attention weight at step $t$. Eviction decisions are made independently in every layer and KV head.

Periodic eviction framework: The cache keeps a persistent budget of $K$ pairs plus a buffer of $r \ll K$ most recent pairs. Each eviction keeps the $K$ highest-scoring candidates:

$$\mathcal{S}_t = \operatorname{top-}K_{i \in \mathcal{C}_t} s_i, \tag{2}$$

where $s_i$ is a policy-specific score.

---

Methodology

Random Attention Algorithm

Random Attention is defined by two structural choices:

1. Protect the question: Positions $1, \ldots, \ell_p$ (the entire prefill — system prompt, chat template, and question) are never evicted.
2. Scatter the rest, per head: Every remaining cached position receives an i.i.d. uniform random score, and each KV head keeps its top-$K$ independently.

The entire method is:

$$s_i = \begin{cases} +\infty, & i \leq \ell_p \quad (\text{the prompt}), \\ u_i \sim \text{Uniform}(0, 1), & \text{otherwise}, \end{cases} \tag{3}$$

drawn independently per KV head at every eviction.

Algorithm 1: Random Attention scoring (one eviction event; runs per layer)
Require: batch size B; number of KV heads H_kv; number of cached positions S; 
        prompt length ℓ_p; budget K
Ensure: keep, the K positions each KV head retains, of shape (B, H_kv, K)

1:  s ← rand(B, H_kv, S)          ▷ i.i.d. uniform score per cached position, per KV head
2:  s[:, :, 0:ℓ_p] ← +∞           ▷ force-keep the question
3:  keep ← topk(s, K)             ▷ independent top-K per KV head
4:  return keep

The per-eviction cost is one rand and one topk — the weakest possible selection signal.

Experimental Setup

• Models: Qwen3-4B, Qwen3-14B, Qwen3-32B, Phi-4-reasoning (14B)
• Tasks: MATH500, GPQA-Diamond, AIME 2025+2026, HMMT, LiveCodeBench-v6 medium
• Compression: ~4× compression of typical trace (~3× for LiveCodeBench)
• Baselines: SnapKV, R-KV, VaSE, TriAttention, full attention (ceiling)
• Statistics: Paired, problem-clustered percentile bootstrap (95% CI) plus exact sign test

Controlled Experiments

Experiment 1 (Prompt fragility): Give every method the same rule (keep the prompt) and measure how much each method gains relative to its score alone.

Experiment 2 (Cross-head redundancy): A planted-fact probe inserts a synthetic fact (e.g., "Let z_q = 4729") into real MATH500 reasoning traces, 1,536 tokens before a question needing the value. The fact is pinned in a chosen set of heads and evicted from all others. Two metrics measure survival:

• Retrieval: fraction of traces whose greedy decode reproduces the value
• Graded recall:

$$R = \frac{\sum_i \left(\mathrm{LP}_i - \mathrm{LP}_i^{\mathrm{del}}\right)}{\sum_i \left(\mathrm{LP}_i^{\mathrm{kept}} - \mathrm{LP}_i^{\mathrm{del}}\right)}, \tag{4}$$

where $\mathrm{LP}_i$ is the log-probability of the correct value under the tested condition, $\mathrm{LP}_i^{\mathrm{kept}}$ with the fact in every cache, and $\mathrm{LP}_i^{\mathrm{del}}$ with it deleted from every cache. $R=1$ means surviving copies are as good as never evicting.

---

Empirical Validation / Results

Main Results

Table 1: Accuracy under KV cache eviction at ~4× compression

Key findings:

• Random Attention is significantly ahead in 31 of 60 baseline cells, significantly behind in only one.
• On math and science reasoning (MATH500, GPQA-D), no selector beats Random Attention significantly.
• On code reasoning (LiveCodeBench), most signal-based selectors collapse due to much longer prompts (average 557 tokens vs. ~100 for MATH500); Random Attention pins every prompt token.

Compression Pressure

From 2× to 16× compression, Random Attention stays tied with TriAttention while the gap from both to VaSE opens. At 2×, every method sits near full attention.

Prompt Protection Experiment

Table 2: Performance before and after protecting the prompt

The rule pays each method according to how much of the question its score was losing. Once every method keeps the prompt, baselines land within 2.2 points of one another.

Cross-Head Redundancy Findings

• Copies pool across heads: Only 3 of Qwen3-4B's 8 KV heads retain a usable trace of a fact alone (best single head: 3% retrieval). But two heads together yield 60%, three heads 83%, all eight 99%. Pooling is strongly superadditive.
• The shape of copies does not matter: Dealing the fact out token-by-token across heads barely moves retrieval (0.33 vs. 0.39 for an intact sentence) and recall is essentially unchanged ($R=0.75$ vs. $0.76$).

Needle-Finding (What's Left for a Signal)

Table 3: Passcode stated once, 57 compression rounds before the question

R-KV, the best needle-finder, leads only one column of Table 1, while TriAttention, the strongest baseline there, recovers almost nothing here. On real traces this case is rare because the model keeps restating what it is still using.

Serving Throughput

Table 4: Serving throughput under vLLM with PagedAttention on one H200 (K=2048, 1k-token prompts, 32k-token generations)

The margin comes from skipping the scoring pass: with 128 concurrent requests, vLLM compresses some request at nearly every decoding step (~62k times per workload), and all requests wait during each compression.

---

Theoretical and Practical Implications

Theoretical Implications

1. The ranking problem is largely irrelevant: The accuracy of an evictor is decided by what it protects, not by how it ranks the rest.

2. Two-level redundancy explains robustness:

   • Text-level: Reasoning traces restate what they are still using, so a value that matters rarely lives at one position only.
   • Cross-head: Each KV head caches its own copy of every token; a token is only lost when all heads drop it. Independent per-head random draws maximize the chance that some head keeps a needed value.

3. The prompt is the fragile part: The question is stated once and cannot be recovered if evicted. Methods differ mainly in whether their score happens to preserve it.

Practical Implications

1. Random Attention is a deployable method: It needs no calibration, no tuning, and no scoring pass. It is the fastest evictor measured at equal accuracy, making it a reasonable default for serving reasoning models under a memory budget.

2. New baseline for eviction research: Any new selection signal must beat Random Attention at matched budget and matched prompt protection.

3. Redirected research questions:

   • How to budget long prompts, especially in code tasks where protecting the entire prompt consumes a substantial fraction of the cache budget.
   • How to recover rare once-stated facts that only a content-dependent signal can preserve.

---

Conclusion

KV cache eviction for reasoning has been treated as a ranking problem: estimate which cached tokens will matter and keep those. The paper finds that the ranking contributes almost nothing. A policy that keeps the prompt and evicts uniformly at random within each head:

• Matches the strongest baselines across four models and six tasks
• Serves 32–43% higher throughput in vLLM deployment
• Requires no scoring pass, calibration, or tuning

The explanation rests on two findings: (1) the prompt is the fragile part of the cache, and once every method keeps it, most gaps disappear; (2) the reasoning trace protects itself through redundancy in the text and across heads, so a random draw keeps enough copies of what the model still needs.

Future directions: The open questions move to where protection still matters — budgeting long prompts (especially code tasks) and recovering rare once-stated facts. The code is publicly available at https://github.com/SalesforceAIResearch/Random-Attention.