Long-chain chains-of-thought create a KV-cache memory bottleneck for LLM inference; counterintuitively, the paper shows that most selection signals add little value once the prompt is preserved. The core insight is that protecting the prompt plus relying on redundancy across attention heads and text restatement lets a head-wise uniform random eviction retain enough of the reasoning trace to match sophisticated selectors while improving serving throughput.
Key Findings
- Random per-head eviction (no scoring) matches the strongest prior deterministic evictor on average across four models and six reasoning tasks, contradicting the assumption that fine-grained importance scoring is necessary for reasoning accuracy. This parity holds when the prompt is preserved.
- Throughput gains of 32–43% in vLLM deployment are reported versus the strongest prior evictor, because random eviction avoids scoring overhead and simplifies memory movement.
- Two redundancy mechanisms explain robustness: the model restates what it needs in the token stream (textual redundancy), and multiple attention heads independently preserve copies of the reasoning trace (cross-head redundancy). Together these make random retention effective without per-token importance estimates.
- Empirical ablations show the prompt is the fragile part of the cache; many selector differences trace to whether they incidentally preserved prompt content rather than to superior scoring.
Who It's For and Tradeoffs
Great fit if you deploy LLMs for long-context reasoning under strict static memory budgets and want higher inference throughput with minimal engineering: Random Attention is simple to implement, removes scoring computation, and scales well in vLLM-like serving.
Look elsewhere if your workload critically depends on preserving very specific, non-redundant token signals that do not appear repeatedly in text or across heads, or if you need formal guarantees about worst-case attention error—randomized eviction trades deterministic selection for empirical robustness and throughput.
Where It Fits
This paper reframes cache-compression alternatives: selection-based sparse attention keeps the whole KV cache and reduces compute but not memory; deterministic eviction scores and prunes but can be brittle; Random Attention shows a low-cost, high-throughput eviction recipe that attains similar average accuracy in reasoning tasks by leveraging model-level redundancy rather than per-token importance scoring. Code is published by the authors for reproducibility and deployment tests.