Random KV Cache Eviction Rivals Top Baselines, Boosts Throughput 43%

Background: KV Cache Bottleneck in Long Reasoning

As reasoning models generate thousands of tokens for math, science, and code tasks, the Key-Value (KV) cache grows linearly with sequence length, becoming a major memory bottleneck. A common solution is KV cache eviction: set a fixed budget and repeatedly decide which historical KV pairs to keep.

Prevailing Approach: Importance-Based Selection

Prior methods (SnapKV, R-KV, VaSE, TriAttention) design content-dependent importance scores—accumulated attention, recent query attention, value magnitude, key statistics—to predict which KV entries will be needed later. The shared intuition: more accurate importance signals should retain more valuable KV pairs.

Random Attention: A Null Baseline

The paper "Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning" (arXiv:2609.03430) asks: how much do those carefully crafted signals actually contribute? The proposed Random Attention follows two simple rules:

Full prompt protection – system prompt, chat template, and user question are never evicted.

Random retention for reasoning trace – for each KV head independently, assign random scores to candidate positions and keep the top-K.

This yields a natural soft recency bias: newer tokens survive multiple random rounds, older tokens sparsely remain across heads. The method requires only one random-number generation and one top-K operation per eviction step.

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: Accuracy and Throughput

Across 60 baseline comparisons, Random Attention significantly outperforms 31 baselines and is significantly worse than only 1. Average accuracy at ~4× compression matches the strongest baseline (TriAttention).

In vLLM serving (H200, PagedAttention, K=2048, 1k prompt, 32k generation), Random Attention achieves 2046, 1737, 1819, 923 output tokens/s on the four models— 37%, 43%, 40%, 32% higher than TriAttention —because it eliminates the content-dependent scoring pass. At higher compression (2× to 16×), Random Attention stays close to TriAttention while VaSE degrades more sharply.

Discovery 1: The Real Fragility Is the Prompt

Reasoning KV cache splits into prompt (appears once) and working state (repeatedly rewritten). If the prompt is evicted, the model can never recover it; intermediate reasoning variables are often re-emitted later. Baselines differed in prompt protection: TriAttention and Random Attention protect the full prompt, while SnapKV, R-KV, VaSE only keep initial sink tokens and rely on their scores for the rest.

Controlled experiment: Adding full prompt protection to SnapKV, R-KV, VaSE boosts their scores by 2.2–22.5 percentage points, collapsing the gap to within 2.2 points. Hence, much of the apparent "selection signal advantage" was actually a "prompt protection advantage."

Discovery 2: Reasoning Trace Protects Itself via Two-Layer Redundancy

Why does random deletion of reasoning tokens not hurt? Two redundancy layers:

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

Cross-head replicas – each token has KV representations in multiple heads; Random Attention samples independently per head, so a token lost in one head may survive in others.

Planted-fact probe: Insert a random fact (e.g., zq=4729) into a real MATH500 trace, control which heads retain it, then query the fact after multiple evictions. Retrieval accuracy: 1 head → 3%, 2 heads → 60%, 3 heads → 83%, 8 heads → 99%.

Further, forcing all heads to keep the same random positions barely changes accuracy on real MATH500, indicating textual redundancy alone is often sufficient; cross-head redundancy acts as a backup when a fact isn't restated.

Discovery 3: Selection Signals Shine Only for Isolated, Non-Redundant Facts

Constructed a worst-case for Random Attention: a passcode given once at the beginning, never mentioned again, then requested after 57 compression rounds. Random Attention retrieval → 0%. R-KV recovers 83.6%, VaSE 34.4%, SnapKV and TriAttention near 0%. This shows content-dependent signals are valuable for "needle-in-haystack" facts lacking redundancy. Notably, the best needle retriever (R-KV) is not the overall reasoning champion (TriAttention), so needle retrieval ≠ reasoning performance.

Discovery 4: Skipping Scoring Pass Yields Real Serving Speedups

In single-stream decoding, scoring overhead is a few percent. In serving, two factors amplify it:

High concurrency: 128 requests, compression every 64 generated tokens, synchronization across batch.

PagedAttention memory access: content-dependent selectors must read key/value pages or recompute attention statistics, while Random Attention only does random selection + compulsory cache compaction.

Thus Random Attention removes an entire content-dependent scoring pass and its repeated synchronization/memory-access costs.

Implications and Future Directions

When prompt protection is equalized, complex ranking signals add limited extra value for training-free decode-time eviction. The critical question shifts from "which KV is most important?" to "which information is truly irrecoverable?" Prompt and once-stated rare facts are irrecoverable; model-generated working state is highly redundant and tolerates forgetting.

Random Attention serves as a strong null baseline: any new selector must beat random selection under matched budget and prompt protection. Future work may focus on compressing the prompt itself (e.g., LiveCodeBench prompts average 557 tokens, up to half the budget) while identifying truly irrecoverable content, rather than ranking all reasoning tokens more precisely.

Perhaps we should first ask: what does the model truly fear forgetting?