Random Attention: Random KV Cache Eviction Rivals Best Baselines, Boosts Throughput 43%

Large reasoning models generate extremely long chains of thought, causing KV cache memory to grow linearly with sequence length and become a deployment bottleneck. Prior work addresses this by scoring each cached key-value pair for importance and evicting the lowest-scored entries. Salesforce AI Research and UIUC introduce Random Attention , a deliberately simple alternative: fully protect the input prompt, then for each KV head independently assign random scores to the model-generated reasoning tokens and keep only the top‑K.

Method

Random Attention has two rules:

Prompt protection : system prompt, chat template, and user question KV entries are never evicted.

Per‑head random retention : for every KV head, generate random scores for candidate reasoning positions and retain the top‑K.

Because a token must survive repeated random eviction rounds to stay in cache, the scheme naturally creates a soft recency bias — newer reasoning tokens are almost always kept, older ones sparsely scattered across heads.

Experimental Setup

Models : Qwen3‑4B, Qwen3‑14B, Qwen3‑32B, Phi‑4‑reasoning.

Tasks : MATH500, GPQA‑Diamond, AIME 2025, AIME 2026, HMMT, LiveCodeBench.

Compression : ~4× KV cache budget (LiveCodeBench ~3×), max generation 32k tokens.

Baselines : SnapKV, R‑KV, VaSE, TriAttention (all training‑free, decode‑time eviction).

Main Results

Across 60 baseline comparisons, Random Attention significantly outperforms 31 baselines and loses to only 1. Average accuracy at ~4× compression matches the strongest baseline (TriAttention). In vLLM serving on a single H200 (PagedAttention, K=2048, 1k prompt, 32k generation), throughput increases over TriAttention are:

Qwen3‑4B: +37% (2046 tok/s)

Phi‑4‑reasoning: +43% (1737 tok/s)

Qwen3‑14B: +40% (1819 tok/s)

Qwen3‑32B: +32% (923 tok/s)

Relative to full attention, Random Attention delivers 1.6–2.7× throughput. The speedup comes from eliminating the content‑dependent scoring pass; in batched serving, that pass forces synchronization across the whole batch and requires extra memory accesses to paged KV state.

Why Random Works: Two Layers of Redundancy

1. Prompt Protection Is the Real Differentiator

Reasoning KV splits into the user prompt (appears once) and the model’s working state (repeatedly rewritten). If the prompt is evicted, the information is gone forever; intermediate reasoning values are often re‑emitted later. The authors show that baseline methods differ in how they treat the prompt: TriAttention and Random Attention protect the full prompt, while SnapKV, R‑KV, and VaSE only keep initial sink tokens. When all methods are given identical full‑prompt protection, their accuracy gaps shrink to within 2.2 percentage points.

2. Reasoning Trace Redundancy

Long reasoning exhibits two redundancy layers:

Textual repetition : models restate variables, formulas, and partial conclusions throughout the trace.

Cross‑head copies : the same token has independent KV representations in each head; Random Attention samples per head, so a fact dropped in one head may survive in another.

A planted‑fact probe inserts a random fact (e.g., zq = 4729) into a real MATH500 trace and measures retrieval after multiple evictions. With the fact kept in only one head, retrieval accuracy is ~3%; with two heads it reaches 60%; three heads 83%; eight heads 99%. Moreover, facts stored in different heads can be combined: joint recall exceeds the sum of individual recalls.

Changing the retained pattern from scattered tokens to contiguous blocks (block size 1→64) barely affects accuracy; only when blocks become very large (256) does performance drop, indicating that quantity of surviving information matters more than its exact layout .

Where Selection Signals Still Help: Isolated Facts

When a fact appears once, is never restated, and must be recalled after many compression rounds (a “needle‑in‑haystack” passcode test), Random Attention fails (0% retrieval). R‑KV recovers 83.6%, VaSE 34.4%, while SnapKV and TriAttention also approach zero. This shows content‑aware selection is valuable for non‑redundant, once‑stated facts , but such facts are rare in typical reasoning traces. Notably, the best needle retriever (R‑KV) is not the best overall reasoning baseline (TriAttention).

System‑Level Efficiency

In vLLM, each request triggers compression every 64 generated tokens. With 128 concurrent requests, the scoring pass becomes a synchronization bottleneck and forces extra traversal of paged KV buffers. Random Attention avoids this entirely, performing only random score generation and the mandatory cache compaction.

Conclusions & Future Directions

For training‑free, decode‑time eviction, once prompt protection is equalized, complex importance ranking adds little over random selection. The critical question shifts from “which KV is most important?” to “which information is truly irrecoverable?”. Prompt tokens and isolated once‑stated facts are irrecoverable; the bulk of reasoning working state is highly redundant. Future work should focus on compressing replaceable parts of long prompts while identifying and protecting genuinely irrecoverable content. Random Attention serves as a strong null baseline: any new selector must demonstrate clear gains over it under matched budget and prompt protection.

Perhaps we should first figure out what the model truly fears forgetting.

Paper : https://arxiv.org/abs/2609.03430

Project page : https://arthur-heng.github.io/Random-Attention-page/

Code : https://github.com/SalesforceAIResearch/Random-Attention