One-sentence Summary

Random Attention, proposed by Salesforce AI Research and the University of Illinois Urbana-Champaign, is a KV cache eviction method that preserves the prompt and randomly evicts tokens per attention head without scoring, matching the strongest prior evictor across four models and six reasoning tasks while delivering $32\textendash43\%$32\textendash43% higher throughput in vLLM deployment, and demonstrating that selection signals are unnecessary because the prompt is fragile and reasoning traces are redundant.

Key Contributions

• Random Attention is a KV cache eviction policy that retains the prompt and evicts tokens uniformly at random within each attention head, without computing importance scores. It matches the strongest prior evictors on four models and six reasoning tasks while serving 32–43% higher throughput in vLLM deployment.
• Controlled experiments show that the prompt is the fragile part of the cache, and once preserved, the performance gap between selection signals nearly vanishes. This explains why random eviction matches sophisticated scoring.
• Reasoning traces protect themselves through redundancy at two levels: textual restatements and cross-head duplication, so after the prompt is safe, a random draw retains enough copies of needed information, making selection scores unnecessary.

Introduction

Large language models designed for reasoning tasks generate extremely long chains of thought, causing the key-value (KV) cache to grow linearly and create a severe memory bottleneck. Prior work addresses this by evicting cached tokens under a fixed budget, using heuristic scoring rules (accumulated attention, value magnitude, key statistics) that assume the score determines accuracy under compression. The authors test that premise directly and find that the selection signal contributes almost nothing. They introduce Random Attention, a simple policy that keeps the prompt and evicts uniformly at random within each attention head, which matches or surpasses strong baselines across multiple models and reasoning tasks while delivering 32–43% higher throughput because it never runs a scoring pass.

Method

The authors introduce Random Attention, a simple and signal-free eviction policy for managing the KV cache during autoregressive generation. The core idea is to separate the irreplaceable input (the prompt) from the model-generated reasoning trace, applying different retention strategies to each. The prompt is stated only once and cannot be recovered if evicted, so it must be fully protected. In contrast, the reasoning trace is continuously revisited and restated as generation proceeds, making it highly redundant and amenable to random sampling.

The method consists of two structural rules. First, all positions belonging to the prefill—including the system prompt, chat template, and user question—are permanently retained. These positions $1,\dots,\ell_p$1,…,ℓp​ are never evicted. Second, every other cached position receives an i.i.d. uniform random score, drawn independently per KV head. Each head then keeps its top-$k$k positions according to these random scores, where $k$k is determined by the available cache budget. This per-head independence scatters the retained budget evenly across the entire reasoning trace and ensures that different heads keep different subsets of the trace.

Formally, the score $s_i$si​ for each cached position $i$i is defined as

with the random draws performed independently for every KV head at each eviction step. The eviction step then simply selects the positions with the highest scores per head, discarding the rest. The per-eviction computational cost is minimal: one random number generation and one top-$k$k operation per head.

Random Attention serves both as a practical deployment method and as a null hypothesis for KV cache eviction. Because it uses no signal from attention weights or hidden states, any signal-based selector that fails to outperform it at a matched budget is not extracting usable information from its signal. The authors later demonstrate that this random policy is surprisingly effective because the prompt is fragile and must be preserved, while the working state is stored redundantly across both text restatements and multiple attention heads. Independent per-head random draws maximize the chance that at least one head retains a copy of any needed value, exploiting the model’s inherent cross-head redundancy without requiring any selection heuristic.

Experiment

The evaluation compares random KV-cache eviction (Random Attention) against several signal-based selectors on Qwen3 and Phi-4-reasoning models across math, science, and code reasoning tasks at around 4× compression. Main results show that Random Attention matches or outperforms learned selectors on math and science, while code reasoning reveals that protecting the prompt closes most performance gaps. Further analysis finds that the prompt is the fragile component, whereas the model's own reasoning trace is highly redundant across text and attention heads, making random eviction robust. Efficiency tests demonstrate that skipping the scoring pass yields 32–43% higher throughput under paged serving, as the scoring overhead compounds with concurrent requests.

A simple random eviction policy (Random Attention) matches or exceeds the accuracy of attention-scoring methods across math, science, and code reasoning tasks at high compression. On math and science benchmarks, no selector significantly outperforms Random Attention, while on code tasks with long prompts, SnapKV and VaSE suffer large drops. The only significant advantage for a selection-based method is a modest gain for TriAttention on one model in code. Random Attention significantly outperforms SnapKV and VaSE on MATH500 and GPQA-D across all models, and R-KV on Qwen3-4B. On LiveCodeBench, SnapKV loses 20–35 points to Random Attention on every model, and VaSE collapses on Phi-4-reasoning, trailing by 29 points.

Protecting the prompt dramatically improves performance across all methods, while the choice of selection signal matters little once the prompt is retained. Methods that lose the prompt by default, such as SnapKV and signal-free policies, see the largest gains, and Random Attention with prompt protection becomes the best overall policy. SnapKV, whose default score discards much of the prompt, gains up to 22.5 points when the prompt is explicitly kept. Random Attention with prompt protection matches or exceeds all signal-based selectors, confirming that prompt retention, not the scoring method, is the main driver of accuracy.

When a passcode is stated once and needed 57 compression rounds later, only R-KV, which accumulates attention over the full history, reliably retrieves it (84% of traces, near-certain log-probability). Random Attention and methods that prioritize recent windows fail almost completely, while VaSE retrieves it about a third of the time. Random Attention never reproduces the passcode, and its average log-probability of -18.35 shows the information is effectively lost from the cache. R-KV retrieves the passcode in 83.6% of traces with a log-probability of -0.71, close to certainty. VaSE retrieves the passcode 34.4% of the time, whereas SnapKV and TriAttention retrieve it less than 2% of the time, similar to random selection. Retrieval success directly tracks the attention statistic each policy scores by: full-history accumulation preserves the fact, while recent-window signals do not.

Random Attention delivers 1.6–2.7× the throughput of full attention and 32–43% higher throughput than TriAttention across four models under vLLM with PagedAttention. The gains come from a smaller KV cache that allows more concurrent requests and from eliminating the scoring pass, which reduces per-compression latency and avoids synchronization stalls in batched serving. Random Attention yields 1.6–2.7× the throughput of full attention and 32–43% higher throughput than TriAttention across all tested models. Skipping the scoring pass cuts per-eviction time from 1.47–1.64 ms to 0.30 ms, and the accumulated savings translate into the observed serving speedups.

Random Attention matches or surpasses attention-scoring eviction methods on math, science, and code reasoning tasks, with prompt retention emerging as the primary driver of accuracy rather than the choice of scoring signal. In a long-range retrieval test, only a policy that accumulates attention over the full history reliably preserves distant information, while random and recent-window selectors lose it almost entirely. Random Attention also delivers significant throughput improvements over both full attention and scoring-based selectors by eliminating the scoring pass and enabling higher concurrency.