Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

Heng Wang, Jielin Qiu, Wenting Zhao, Cheng Qian, Liangwei Yang, Jiawei Han, Heng Ji, Silvio Savarese, Shelby Heinecke, Huan Wang

Random Attention replaces complex KV cache scoring with uniform random eviction, matching baseline accuracy while increasing serving throughput by up to 43%.

Can we replace complex, signal-based KV cache eviction policies with a simple random eviction strategy without sacrificing reasoning performance?

Large language models generating long chains of thought face a severe memory bottleneck as the key-value (KV) cache grows linearly with sequence length. Existing eviction methods attempt to solve this by scoring tokens to predict their future importance, but these scoring passes add significant overhead and complexity to the decoding process. Random Attention is a signal-free eviction policy: it protects the entire prompt and evicts remaining tokens uniformly at random within each attention head. This approach eliminates the scoring pass entirely while leveraging the inherent redundancy of reasoning traces. Across four models and six reasoning tasks, Random Attention matches or exceeds the performance of complex, signal-based baselines. In vLLM deployment, it delivers 32–43% higher throughput than the strongest prior evictor.

Paper Primer

The core mechanism hinges on two structural choices: pinning the prefill (prompt) to prevent catastrophic loss of the question, and scattering the reasoning trace across heads using independent random draws. This works because reasoning models restate their intermediate steps (text-level redundancy) and cache copies across multiple heads (cross-head redundancy), making a sophisticated ranking of individual tokens unnecessary.

Selection signals provide negligible accuracy gains over random eviction when the prompt is protected.

In controlled experiments where all methods were forced to keep the prompt, the performance gap between complex scorers and Random Attention vanished or favored the random policy. Random Attention significantly outperformed or tied baselines in 59 out of 60 test cells, with the only significant baseline win occurring in a code-reasoning task driven by prompt length.

Why do previous studies report that random eviction performs poorly compared to signal-based methods?

Previous random baselines often failed to protect the prompt. Because the prompt is the most fragile part of the cache, losing it causes catastrophic accuracy drops, which researchers incorrectly attributed to the lack of a "smart" selection signal.

Are there any scenarios where a selection signal is actually necessary?

Yes, when the model must retrieve a "needle" (a specific fact) that is stated exactly once, never restated, and needed much later in the generation. Random eviction cannot guarantee the survival of such isolated facts, whereas signal-based methods can.

For reasoning models, the accuracy of an eviction policy is determined by what it protects, not how it ranks the rest. Researchers should shift focus from optimizing ranking scores to better managing prompt budgets and recovering rare, non-redundant facts.

Introduction: The KV Cache Bottleneck

We expose why long‑chain reasoning reshapes KV‑cache eviction needs.

Reasoning models generate long chains of thought, causing the KV cache to grow linearly and become a severe memory bottleneck. Existing eviction methods all rely on scoring each cached token and keeping the top‑scoring ones, assuming that a better score improves accuracy. We show that the scoring signal contributes almost nothing, and that simple random eviction with prompt protection suffices.

KV cache eviction decides which past key‑value pairs to discard during autoregressive decoding so that the cache stays within a fixed memory budget.

The shift from long‑context retrieval to long‑chain reasoning changes the cache eviction requirements.

The Reasoning Decoding Regime

Define the KV‑cache eviction setting and notation needed to study policies.

Reasoning models generate extremely long chains of thought, so the KV‑cache quickly reaches its memory budget. When the cache is full, older key‑value pairs must be evicted, which permanently discards information and can break the reasoning process.

We formalize the setting: at decode step $t$ each attention head stores $N$ cached pairs $(k_i, v_i)$, with $k_i, v_i \in \mathbb{R}^d$. The query $q_t \in \mathbb{R}^d$ produces the output $o_t$ by weighted summation over the values, where the weights $\alpha_i(t)$ are softmax‑scaled dot products.

Eviction proceeds periodically: the cache keeps a hard budget of $K$ pairs plus a small buffer of the most recent $r$ pairs, which are never scored. After every $r$ decoding steps the buffer fills and triggers an eviction round.

During an eviction round the candidates $\mathcal{C}_t$ are all cached positions outside the buffer. Each candidate receives a real‑valued score $s_i$ computed by the policy, and the $K$ highest‑scoring candidates are retained, restoring the cache size to $K+r$.

Existing policies differ in how they compute $s_i$. SnapKV scores only the last $w$ queries, H2O uses the maximum attention received, R‑KV adds a redundancy term based on cosine similarity, VaSE scores based on value range and samples the rest, and TriAttention scores by temporal distance modulated by query‑key norm.

The Random Attention Policy

Random Attention evicts KV entries by protecting prompts and randomly keeping others per head.

Reasoning models keep growing KV caches, turning the cache into a memory bottleneck. Existing eviction methods spend compute scoring each token, whereas Random Attention sidesteps scoring entirely.

Instead of trying to guess which cached token is useful, we keep the prompt untouched and let every KV head pick a few positions at random.

Draw random scores for each head: Head 1 → $[\,\color{gray}{\infty},\color{gray}{\infty},0.73,0.12,0.58\,]$, Head 2 → $[\,\color{gray}{\infty},\color{gray}{\infty},0.41,0.95,0.33\,]$.

Apply top‑$K$ per head: Head 1 keeps positions 3 and 5 (scores 0.73, 0.58); Head 2 keeps positions 4 and 3 (scores 0.95, 0.41).

The retained set per head is therefore Head 1 → $\{1,2,3,5\}$, Head 2 → $\{1,2,3,4\}$ (positions 1 & 2 are always kept).

Random scores spread the budget evenly, so no single region of the trace dominates the retained memory, while the prompt is guaranteed to survive.

We treat the initial question as irreplaceable: if it disappears, the model loses the only way to know what it is answering.

Generate a tensor $s$ of shape $(B, H_{KV}, S)$ with uniform random values.

Overwrite the first $\ell_p$ entries of $s$ with $+\infty$ to protect the prompt.

For each head, select the indices of the top‑$K$ scores, producing the keep mask.

Return the keep mask, which is used to prune the KV cache.

How does Random Attention differ from a naïve uniform random eviction that does not protect the prompt?

Naïve random eviction would assign random scores to *all* positions, so the prompt could be dropped. Prompt Protection forces the prompt’s scores to $+\infty$, guaranteeing its retention while still randomizing the rest.

Performance Benchmarks

Random Attention matches or beats complex baselines across multiple model scales.

Across four model sizes, Random Attention matches or exceeds all baselines on most tasks, leading in 31 of 60 baseline cells and falling behind only once. On math and science benchmarks (MATH500, GPQA‑D) no selector beats Random Attention, with TriAttention only marginally ahead on two cells. For competition‑math tasks (AIME, HMMT) Random Attention is never significantly outperformed, and any nominal leads fall within run‑to‑run variance.

Code‑reasoning tasks expose larger gaps: SnapKV loses 20–35 points and VaSE collapses, while Random Attention ties or slightly trails TriAttention only on the largest model. Long prompts (≈557 tokens) consume up to half of the $K=3072$ budget, explaining why selectors that ignore prompt structure suffer.

Random Attention leads over baselines on 31 of 60 evaluated cells.

Paired statistical tests show significance in 31 cells and a single loss.

**Figure 1.** (a) Mean accuracy over the six reasoning tasks of Tables 1 and 5 at ~4x compression: Random Attention matches the strongest prior evictor on every model (the small gaps to TriAttention at 14B and 32B are mostly driven by code reasoning, where long prompts consume the budget, §4.2). (b) vLLM serving throughput at 32k-token generations (Table 4); labels give Random Attention’s multiple of full attention and its margin over TriAttention: with no scoring pass it serves 32–43% higher throughput.

**Table 1.** Comparison of different attention methods across various model architectures (Qwen3-4B, Phi-4-reasoning, Qwen3-14B, Qwen3-32B). The table displays raw performance values and speedup factors (in parentheses) for "Full", "TriAttention", and "Random Attention (ours)". The final row shows the percentage improvement of "Random Attention" over "TriAttention".

Scaling Under Compression

Random Attention preserves accuracy under extreme compression while other methods fall off.

We evaluate how compression pressure affects four families of KV‑cache eviction methods on two models and four reasoning benchmarks.

Random Attention matches TriAttention accuracy up to 16× compression, while VaSE drops up to 0.7 points.

Figure 2 demonstrates this trend for Qwen3‑4B and Phi‑4‑reasoning across MATH500, GPQA‑D, AIME, and HMMT.

**Figure 2.** Accuracy from 2x to 16x compression on Qwen3-4B and Phi-4-reasoning, on the four math and science tasks; dashed lines mark full attention.

Table 2 details per‑method scores before and after applying prompt protection, highlighting that R‑KV’s gains never exceed 1.9 points, SnapKV consistently improves, and VaSE’s improvements are limited to Phi‑4‑reasoning.

Why Selection Signals Fail

We test how protecting the prompt and exploiting working‑state redundancy affect performance.

The central premise is that reasoning models keep the prompt in the KV cache, which is easy to lose, while the intermediate reasoning trace is stored redundantly enough that random eviction rarely harms accuracy.

During autoregressive reasoning the model writes the same intermediate token into every KV head, so the cache contains multiple copies of each value.

How does this redundancy differ from simple token‑level duplication?

Token‑level duplication repeats the same value in the text, which the model can read directly. Cross‑head redundancy stores separate copies in each KV head, so even if the text no longer contains the value, any surviving head can supply it to attention.

Protecting the prompt yields large gains for methods that otherwise discard it.

SnapKV improves by 22.5 points on Phi‑4‑reasoning GPQA‑D, VaSE gains +4.2 and +10.2 points, while R‑KV gains at most 1.9 points.

Removing cross‑head redundancy hurts performance only marginally.

When the same random positions are evicted in every head, the score drops by about 0.3 points compared to full Random Attention.

**Figure 4.** Fraction of positions of a given age that a head still holds (log scale; Qwen3-4B MATH500, K=1024). Random Attention decays geometrically with age; VaSE concentrates and freezes a tail of old favourites; TriAttention spends almost uniformly across ages, keeping less of the recent middle than Random Attention but several times more of the very old tail.

Failure Modes and Caveats

Shows where signal‑free policies break down on rare, unrepeated facts.

A signal‑free policy cannot preserve a fact that appears only once, never restated, and is needed many steps later. We test this with a passcode announced once, then compressed for 57 rounds before the question.

**Table 3.** A passcode stated once, 57 compression rounds before the question.

These numbers show that random eviction alone cannot keep a unique fact, whereas scoring the whole history (R‑KV) succeeds. The gap demonstrates that selection signals matter when redundancy is absent.

Wang (2026) formally prove that random caches must lose information in pointer‑chasing scenarios lacking redundancy, confirming the empirical failure of signal‑free policies on the passcode test.

Table 4 (throughput) shows that Random Attention speeds up generation on all tested models, achieving up to 2.23× the token‑per‑second rate of full attention. For example, Qwen3‑4B improves from 1296 to 2046 tok/s (1.58×) and Phi‑4‑reasoning from 780 to 1737 tok/s (2.23×), outpacing TriAttention.

**Figure 3.** (a) A fact held in one head is almost never retrieved; held in several it is. (b) Two facts in *different* heads are worth more together than the sum of each alone (dashed). (c) Real MATH500: contiguous blocks cost nothing up to size 64; accuracy drops only once a head is left with 4 (K=1024) or 2 (K=512) blocks.

Overall, selection skill does not imply aggregate strength: R‑KV, the best needle‑finder, improves only one column of Table 1, while TriAttention, the strongest baseline there, recovers almost nothing in this passcode scenario.

Throughput and Latency

Random Attention cuts eviction cost by up to 43% and boosts decode throughput by up to 10×.

Random Attention reduces eviction round cost by 32–43% compared to TriAttention under paged serving.

Measured on an H200 GPU with $K=2048$, 1k‑token prompts, 32k‑token generations, and 128 concurrent requests.

Random Attention achieves 1.6–2.7× the full‑attention throughput across the four models, and reaches 10.0× on Qwen3‑4B and 8.8× on Qwen3‑14B, far outpacing TriAttention’s 41–42% advantage at capacity.

**Table 9.** Cost of one eviction round (scoring + compaction), measured with CUDA events on an otherwise idle H200: $K=1024$, 4096 decode steps, single stream. Random Attention performs no scoring, so its round time is the compaction floor every evictor pays; the excess over it is the price of the selection signal. The ordering, and the per-call costs to within 12%, are unchanged across a 3.5$\times$ change in model size.

**Figure 5.** Equal-memory serving: decode throughput relative to full attention at each method's largest batch on one H200 (K=3072, 32k generations). *TriAttention* here is an unfused re-implementation of its scorer, far slower than the vLLM version.

Prior Eviction Paradigms

Prior approaches to KV‑cache management for long contexts and reasoning.

This section surveys how prior work has tackled the KV‑cache bottleneck for both long‑context inputs and chain‑of‑thought reasoning.

Eviction decisions are driven by a computed signal—such as attention weight, value magnitude, or positional statistic—that estimates each token’s future usefulness.

Reduces KV memory by storing each token at lower numeric precision, trading a small loss in fidelity for large space savings.

Discard tokens under a fixed memory budget, using a signal to rank importance. Signals include cumulative attention, persistence across steps, and recent‑query windows; budgets may be allocated per head or per layer, and structural rules enforce recent‑window constraints.

Instead of evicting, this family keeps the full cache but, for each query, attends only to a subset of tokens selected by a relevance signal.

At inference time, unmarked leaf tokens are evicted uniformly at random from a prefix‑sharing cache, improving robustness to dynamic or adversarial query patterns.

Samples a subset of tokens to cover the input under a global cache cap; when prompt‑boundary tokens are protected, the choice of scoring becomes secondary and a random policy performs competitively.

Adapts sparse‑attention mechanisms to chain‑of‑thought generation, but retains the full KV cache in memory, so peak GPU usage still grows with trace length.

Methods that estimate KV importance during generation and evict low‑importance entries. Includes R‑KV (SnapKV‑style score with redundancy penalty), VaSE (value‑magnitude scoring with stochastic fill), earlier score‑guided random eviction, TriAttention (position‑based trigonometric scoring), LazyEviction (future‑importance prediction from recurring patterns), and SpeContext (distilled‑model retrieval head for importance prediction).

Maintains only the prompt and a recent window of tokens (recency + prompt policy). Some variants integrate KV eviction into training.

Across these families, prior work consistently treats the prompt as the most fragile cache component, protecting it while varying the eviction or selection strategy for the remaining tokens.

Generality Across Architectures

Random Attention tops compression baselines on Qwen3‑14B across benchmarks.

Random Attention matches or exceeds all compression baselines on Qwen3‑14B across the five benchmarks.

Table 5 shows Random Attention achieving the highest compression‑method scores on GPQA‑D (0.628) and HMMT (0.820), and competitive results on the other benchmarks.

**Table 5.** Generality: additional models. Table 5 repeats the main grid on Qwen3-14B, an intermediate scale within the headline family. The picture from Table 1 replicates: Random Attention beats VaSE and SnapKV on MATH500 and GPQA-D (both significant). Three baseline cells are significantly ahead at this scale: TriAttention on LiveCodeBench (+2.6 points, p=.007), matching its code win on Qwen3-32B and the prompt-length account of §4.2, TriAttention on MATH500 (+2.1 points, p=.02), and VaSE on AIME (+2.6 points, p=.007), consistent with its nominal AIME edge on Qwen3-32B. Every cell here uses the same rollout count as the corresponding cell of Table 1 (R=2 on MATH500, 4 on GPQA-D and LiveCodeBench, 16 on HMMT; the Random Attention AIME cell pools 32) for every method.

Control Experiments: Prompt Protection

Prompt‑protection boosts most baselines, with the largest gains for SnapKV.

We now ask whether applying the prompt‑protection rule to each baseline hurts performance. The rule forces the model to keep the original prompt tokens unchanged during generation, and we measure the resulting score changes across several models and benchmarks.

**Table 2.** Performance before and after protecting the prompt. R-KV never gains more than 1.9 points, SnapKV gains everywhere. VaSE gains materially only on Phi-4-reasoning.

**Table 6.** Matched protection in the settings Table 2 does not cover (LiveCodeBench: pass@1; others: accuracy; AIME pools 2025+2026). Small numbers give the gain from the rule in points, red when at least 2; bold marks the best protected method in each setting. TriAttention and Random Attention keep the prompt by construction and appear only in the protected column (values as in Table 1).

SnapKV benefits most from prompt protection, gaining up to +35.2 points on LiveCodeBench.

Table 6 reports a +35.2‑point increase for SnapKV when the rule is applied.

VaSE also improves markedly, with a +27.3‑point gain on the same benchmark.

Table 6 lists a +27.3 increase for VaSE under prompt protection.

R‑KV shows essentially no effect, with a net change of only +0.9 points.

Across all five settings in Table 6 the R‑KV column varies between –1.4 and +0.9, averaging near zero.

Retention Logging Methodology

We log eviction rounds to quantify coverage, prompt survival, and age‑based retention across policies.

We recorded every eviction round from nineteen policy‑cell logs, each containing sixteen traces and roughly $10^4$–$10^5$ rounds, capturing the keep‑set and age of each retained position for every (layer, key‑value head) pair.

Slot coverage – the fraction of candidate positions retained by at least one head immediately after a round – is near‑perfect (0.999–1.000) for Random Attention and VaSE, 0.993 for TriAttention, and drops to 0.938 for the shared‑draw control, which lacks cross‑head diversity by design.

Prompt survival – the fraction of prompt positions still held – remains high for Random Attention (0.994–0.999 both union and per‑head), while R‑KV, VaSE, and SnapKV show markedly lower union ranges (0.55–0.91, 0.56–0.70, 0.32–0.42) and per‑head ranges (0.26–0.67, 0.20–0.29, 0.11–0.22) across the four model‑task settings.

Survival by age – the fraction of positions in a given age band a head still holds – for the 1–2 k band is 0.188 for Random Attention, 0.161 for the shared draw, 0.145 for SnapKV, 0.105 for R‑KV, and 0.086 for VaSE; the cross‑head union reaches 0.776 for Random Attention but only 0.368 for VaSE and 0.161 for the shared draw.

Although no explicit score is computed, the policy exhibits an implicit age bias: a position surviving one eviction faces a fresh draw next round, giving a survival probability of $(K-\ell p)^n\approx0.94^n$ at $K\!=\!1024$ and $r\!=\!64$, effectively a soft recency window.

The shared‑draw control, which forces all heads to use the same random keep‑set, attains 0.871 accuracy on Qwen3‑4B MATH500 at $K\!=\!1024$ (0.788 at $K\!=\!512$), virtually matching Random Attention’s 0.874 and 0.789, indicating that cross‑head diversity contributes little when the primary redundancy is present.

**Table 7.** Mean generated tokens (thousands) per cell of Tables 1 and 5, measured over every run of the cell; Avg = unweighted mean over the five tasks.

**Table 8.** Run-to-run variability: standard deviation of per-run accuracy (points) across each cell’s independent sampled runs, including LiveCodeBench, whose runs are graded individually by test execution.

Implementation Details: Eviction Engine

Describes the per‑KV‑head eviction process used in the VaSE engine and reports its token‑generation performance.

The VaSE engine evicts entries on a per‑KV‑head basis. Every $r=64$ decode steps, once the cache size exceeds $K+r$, each KV head scores all cached positions except the most recent $r$‑token buffer, retains the top‑$K$ slots, and compacts the tensors via a gather operation.

Per‑KV‑head eviction loop in VaSE.

Table 7 reports the mean number of generated tokens (in thousands) per cell for each method across five benchmark tasks. Random Attention (our method) consistently matches the Full baseline while using the simple random eviction strategy, confirming that sophisticated scoring is unnecessary for maintaining reasoning accuracy.

Eviction Engine: Monotonicity and Sampling

Engine Details Part 2 clarifies baselines, variability reporting, hardware, and per‑task budgets.

All baselines run in the same engine under identical budget, trigger, and buffer settings. VaSE uses $n_{\text{large}} = K/4$ (fixed at 256 for larger budgets), R‑KV adopts $\lambda = 0.5$ (the setting that reproduces Chang et al. 2026 within 2.3 points on MATH500), and TriAttention is taken verbatim from its official implementation with per‑head calibration that yields a mean reciprocal rank of 0.99. The full‑attention path reproduces the accuracies reported by Chang et al. 2026 on Qwen3‑4B to within 0.5 points across all four shared tasks.

Table 8 reports the run‑to‑run variability as the standard deviation of per‑run accuracy (points) for each cell, including LiveCodeBench where each run is graded by test execution. The table lists variability for five models (Full, SnapKV, R‑KV, VaSE, TriAttention, Random Attention) across five benchmarks (MATH500, GPQA‑D, AIME, HMMT, LiveCodeBench).

All experiments run on a mixed fleet of NVIDIA H200 nodes, with each job occupying a single GPU and no other workload on the node. Decoding proceeds until an end‑of‑sequence token or a uniform $32\,\text{k}$‑token limit, whichever comes first.

The per‑task budgets follow the main grid: MATH500 $K$ = 1024, GPQA‑D $K$ = 2048, AIME/HMMT $K$ = 4096, and Live‑CodeBench $K$ = 3072, representing roughly a three‑fold compression of the full‑attention traces. Sampling and prompting use the reference repository defaults for every method, ensuring a consistent evaluation protocol across models.

Experimental Setup and Protocols

Efficiency protocols compare Random Attention to baselines under identical vLLM settings.

The vLLM experiments (Table 4) run bf16 on a single H200 using vLLM v0.19.0 with PagedAttention, a budget of 2048 tokens and 1 k‑token prompts; both Random Attention and TriAttention share identical attention kernels, paging, scheduler, and compression triggers, differing only in which positions are retained, with compression invoked every 64 generated tokens.

At the 128‑request point, near the capacity plateau, Random Attention raises steady‑state throughput on Qwen3‑4B from 2046 to 2188 tok/s (+7 %), while decoding adds only 9.5 ms + 0.415 ms per resident sequence, keeping throughput already 85 % batch‑proportional.

In the short‑generation regime where compression offers no benefit, Random Attention attains only 0.52×–0.96× the full‑attention throughput on Qwen3‑4B, 14B, 32B, and 0.76× on Phi‑4‑reasoning, whereas TriAttention reaches 0.38×–0.70×, preserving a consistent margin of +35 % to +42 % in Random’s favor.

Two tooling pitfalls were discovered: vLLM’s benchmark ignores the requested output length, preventing the compression threshold from being reached, and the integration’s deduplication guard can halt later compaction after a single under‑budget round; both were fixed without altering selection or kernel semantics.

**Table 11.** Equal memory at a tighter budget. The multiple over full attention is set by the batch the cache admits, so it grows as the budget shrinks. Table 11 repeats the protocol on Qwen3-4B at K=1024, the MATH500 budget of Table 1: the compressed caches now fit 544–584 sequences against 28, and Random Attention serves 28.8× the full-attention throughput, 16% more than SnapKV and 20% more than VaSE at their own largest batches.

Read the original paper

Open the simplified reader on Paperglide

Browse all simplified papers