A team at Salesforce AI Research has published a paper challenging the prevailing approach to KV cache compression in large language models. The standard method scores each cached token by its predicted future importance and retains only the top-scoring ones. The new study, titled "Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning," argues that this selection signal is nearly useless.
The researchers propose a simpler method: keep the prompt intact and evict tokens uniformly at random within each attention head, without computing any scores. Across four models and six reasoning tasks, this random approach matches the performance of the strongest prior eviction strategy, while serving 32-43% higher throughput in vLLM deployment.
The paper explains this surprising result through controlled experiments. It finds that the prompt is the most fragile part of the cache, and that most differences between selection methods stem from whether they happened to preserve it. Furthermore, reasoning traces are self-protecting: the model restates needed information as it works, and each attention head keeps its own copy, creating redundancy that makes random eviction sufficient once the prompt is safe.
The authors have released their code publicly at github.com/SalesforceAIResearch/Random-Attention, inviting further exploration of this counterintuitive approach.