This paper addresses the memory bottleneck created by large key-value caches during extended LLM reasoning by proposing Random Attention, which evicts cached tokens uniformly at random rather than relying on sophisticated scoring mechanisms, while always preserving the original prompt. The method matches the performance of more complex learned eviction strategies while achieving 32-43% higher throughput in vLLM deployments. The authors find that reasoning traces carry enough redundancy across attention heads and through textual restatement that random selection performs on par with scoring-based approaches. The result simplifies KV cache management for inference-serving systems without sacrificing reasoning quality.
