Random Attention: evicting KV cache uniformly at random matches every scored evictor and serves 32-43% more throughput

arXiv·high signalXBlueskyLinkedInCopy link

Salesforce AI Research (arXiv 2609.03430, 2026-09-03) shows the whole scoring paradigm behind KV cache eviction contributes almost nothing. Random Attention keeps the prompt, then evicts uniformly at random inside each attention head with no score computed at all, and across four models and six reasoning tasks it matches the strongest prior evictor while serving 32-43% higher throughput in vLLM. The explanation is that the prompt is the fragile part and the reasoning trace protects itself through redundancy at two levels, restating what it needs in the text and duplicating it across heads, so once the prompt is safe a random draw retains enough copies. Code is at github.com/SalesforceAIResearch/Random-Attention.