Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

🤗 Upvotes: 50 | cs.CL

Authors:
Heng Wang, Jielin Qiu, Wenting Zhao, Cheng Qian, Liangwei Yang, Jiawei Han, Heng Ji, Silvio Savarese, Shelby Heinecke, Huan Wang

Title:
Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

Arxiv:
http://arxiv.org/abs/2609.03430v1

Abstract:
Large language models achieve superior performance on tasks that require extended reasoning, but long chains of thought make the KV cache a severe memory bottleneck. Existing KV cache compression methods share one paradigm: score each cached token by some estimate of how much it will matter later, and keep the top-scoring ones. We show that the selection signal contributes almost nothing. Random Attention keeps the prompt and evicts uniformly at random within each attention head, computing no score at all; across four models and six reasoning tasks it matches the strongest prior evictor while serving 32-43% higher throughput than it in vLLM deployment. Controlled experiments explain this by showing that 1) the prompt is the fragile part of the cache, and most of the gap between selectors is just whether their selection signal happened to keep it; 2) the reasoning trace protects itself against eviction with redundancy at two levels, in the text (the model restates what it still needs as it works) and across attention heads (each keeps its own copy of the trace), so once the prompt is safe, a random draw retains enough copies of what the model still needs, and no score is required to pick them. Our code is publicly available at https://github.com/SalesforceAIResearch/Random-Attention.

What is Daily Paper Cast?

We update every weekday to discuss highest-voted papers from Huggingface Daily Paper (https://huggingface.co/papers). Both the podcast scripts and audio are generated by AI. Feedback and suggestions are welcome! Email us: [e-mail]

Creator:
Jingwen Liang, 3D ML, https://www.linkedin.com/in/jingwen-liang/
Gengyu Wang, LLM ML, http://wanggengyu.com

Listen on:
Spotify: https://open.spotify.com/show/21nrhmdaA8qoBiH8q03NXL
Apple Podcast: https://podcasts.apple.com/us/podcast/daily-paper-cast/id1777620236

Cover Image by Kawen Kuang https://kawen.art

Evan: Welcome to Daily Paper Cast.

Ashley: Today's paper is featured in the Hugging Face daily paper list of September 4, 2026, and it has garnered 50 upvotes.

Evan: The title of the paper is 'Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning,' and it's from Salesforce AI Research.

Ashley: The first two authors are Heng Wang and Jielin Qiu, with Heng Wang being the corresponding author.

Evan: And their affiliations include Salesforce AI Research and the University of Illinois Urbana-Champaign.

Ashley: Let's dive into the Introduction section of this paper.

Evan: Large language models are known for their superior performance in tasks that require extended reasoning, but they face a significant challenge due to memory limitations, especially when dealing with long chains of thought.

Ashley: The core of the issue lies in the key-value, or KV, cache.

Essentially, as the model generates text, it creates a cache that grows linearly with the length of the generation.

This cache can become a severe memory bottleneck.

Evan: Existing methods to manage this cache involve various compression techniques.

These methods usually score each cached token based on how much it will matter later and then keep the top-scoring tokens.

Ashley: However, this paper challenges that approach.

The authors propose a new method called Random Attention, which does things quite differently.

Instead of scoring each token, it simply keeps the prompt intact and evicts other tokens at random within each attention head.

Evan: That's interesting.

So, no scoring at all.

Just to clarify, what is the KV cache and why is it crucial for reasoning tasks?

Ashley: Great question.

The KV cache stores key-value pairs that a model uses to keep track of information during text generation.

Essentially, it's like the model's short-term memory.

Without effective management of this cache, the model can quickly run out of memory, which limits its capability to process long sequences.

Evan: Got it.

So, what exactly did the authors find in their investigation?

Ashley: They found that the selection signal, or the scoring of tokens, actually contributes almost nothing to the efficiency or performance of the model.

Random Attention, which avoids scoring altogether, matches the strongest previous methods in performance.

Evan: Fascinating.

How does Random Attention manage to achieve this?

Ashley: Their experiments showed two key insights.

First, the prompt is the most fragile part of the cache.

If the prompt is lost, the model's performance degrades significantly, irrespective of how the rest of the cache is handled.

By keeping the prompt, Random Attention ensures that the most crucial part of the information is always retained.

Evan: And the second insight?

Ashley: The second insight is that the reasoning trace, or the tokens generated during reasoning, already contain redundancy.

Essentially, the model restates what it needs as it works through a problem.

Additionally, each attention head keeps its own copy of the trace.

So, even if some tokens are evicted, as long as the prompt is safe, a random draw retains enough copies of what the model still needs.

Evan: So, by treating the prompt and the reasoning trace differently, Random Attention simplifies the process and still manages to perform just as well as more complex methods?

Ashley: Exactly.

It avoids the overhead of scoring, which translates to higher throughput.

Specifically, Random Attention delivers 32 to 43 percent higher throughput than the strongest prior methods when served through the vLLM deployment.

Evan: This sounds like a significant improvement.

So, in summary, Random Attention keeps the prompt intact and evicts other tokens at random within each attention head, achieving efficiency without the need for scoring.

Ashley: Precisely.

And that's the end of the Introduction section.

Evan: Alright, let's move on to the method section of this paper where they detail the Random Attention approach.

Ashley: Random Attention is defined by two key structural choices.

First, it protects the question prompt entirely.

This means that positions corresponding to the prompt are never evicted from the cache.

Evan: Right, and the second choice?

Ashley: The second choice is to scatter the remaining tokens uniformly at random across each attention head.

Essentially, every cached position, except for the prompt, receives a unique, independently drawn uniform random score.

Each key-value head then retains its top-K positions based on these random scores.

Evan: Interesting.

So how exactly is this implementation achieved?

Ashley: It’s implemented through a simple algorithm.

At each eviction event, a fresh uniform random score is assigned to each cached position for every key-value head.

Specifically, the score is set to infinity for prompt positions to ensure they are always kept.

Then, each key-value head independently selects the top K positions based on these scores.

Evan: You mentioned a simple algorithm.

Can you break it down for us into steps?

Ashley: Of course.

Here’s how it works in four main steps: First, initialize a random score for each cached position in each key-value head.

Second, set the scores of the prompt positions to infinity.

Third, each key-value head individually selects the top-K positions based on these scores.

Finally, retain these selected positions and discard the rest.

Evan: Got it, pretty straightforward.

Does this method run into any performance bottlenecks?

Ashley: Actually, one of the key benefits is that it avoids a scoring pass, which significantly reduces the computational overhead.

The process of scoring is often a major bottleneck in existing methods, so eliminating it allows Random Attention to achieve greater efficiency.

Evan: Makes sense.

So, what experimental setup did they use to validate this method?

Ashley: They compared Random Attention against four existing eviction methods: SnapKV, R-KV, VaSE, and TriAttention.

The evaluations were done across four models – Qwen3-4B, Qwen3-14B, Qwen3-32B, and Phi-4-reasoning – on six reasoning tasks spanning math, science, and code.

Evan: What were these six reasoning tasks?

Ashley: The tasks included MATH500, GPQA-Diamond, AIME 2025 and 2026, HMMT via MathArena, and LiveCodeBench-v6 medium.

Each of these tasks come with distinct characteristics often requiring long chains of thought and significant reasoning capability.

Evan: And how did they measure the performance?

Ashley: The primary metric was accuracy, judged by whether the final boxed answer was correct.

They also looked at the throughput, specifically the number of tokens processed per second under vLLM serving.

Evan: Okay, so they ran these models with and without eviction.

How did Random Attention fare compared to others?

Ashley: Random Attention matched or even exceeded the performance of the best existing methods in many cases.

It was particularly efficient, delivering 32 to 43 percent more tokens per second at 32k-token generations compared to competing methods.

For example, on the Qwen3-32B model, Random Attention provided a throughput of 2.67 times more than full attention, while the closest competitor was behind by 32 percent.

Evan: What about accuracy?

Did the selection signal matter at all?

Ashley: Interestingly, Random Attention was shown to be on par with the best existing methods in almost every task, suggesting that the selection signal contributes little beyond the random draw once the prompt is protected.

Evan: It’s quite impressive that such a simple method worked so effectively.

Did they conduct any controlled experiments to understand why this method works?

Ashley: Yes, they did two critical experiments.

First, they confirmed that protecting the prompt is fundamental because it's the most fragile part of the cache.

If the prompt is retained, the differences between various methods' performances narrow significantly.

Evan: And the second experiment?

Ashley: The second experiment showed that the reasoning trace is inherently redundant.

The model restates what it still needs, and each attention head holds its own copy.

This redundancy means that even a random eviction approach retains enough useful tokens for the model to function effectively.

Evan: So, each head working independently contributes to the robustness of Random Attention.

Are there any practical implications mentioned in the paper?

Ashley: Definitely.

Random Attention is not only a highly deployable method due to its simplicity and efficiency, but it also highlights that future research on eviction should focus more on what to protect rather than on how to rank the rest.

Evan: It sounds like this could be a new direction for optimizing memory management in large language models.

Anything else of importance in their methodology?

Ashley: One last point is that Random Attention needs no calibration or tuning, making it a reasonable default for serving reasoning models under a memory budget.

This is particularly useful in production settings where ease of deployment and maintenance are crucial.

Evan: Very true.

A method that provides strong results with minimal complexity is always welcome.

So, to wrap up this section, Random Attention achieves efficient KV cache management by protecting the prompt and applying random eviction, proving itself both effective and straightforward.

Ashley: Exactly.

And that's the end of the Method section.

Evan: Let's turn our attention to the experiments and results section to see how Random Attention performed in various tests.

Ashley: Sure.

The authors conducted extensive evaluations using four different models: Qwen3-4B, Qwen3-14B, Qwen3-32B, and Phi-4-reasoning.

Evan: And they tested on six reasoning tasks, correct?

Ashley: Exactly.

The six tasks were MATH500, GPQA-Diamond, AIME 2025 and 2026, HMMT via MathArena, and LiveCodeBench-v6.

These tasks span various domains like math, science, and code reasoning, offering a comprehensive evaluation landscape.

Evan: That’s right.

They reported accuracy metrics primarily.

Can you break down the main findings for us?

Ashley: Across all tested models, Random Attention showed comparable accuracy to the best existing eviction methods.

Specifically, on tasks like MATH500 and GPQA-D, Random Attention actually outperformed several baselines such as VaSE and SnapKV.

Evan: Interesting.

Were there any tasks where the other methods had an edge?

Ashley: Yes.

For code reasoning tasks in LiveCodeBench, TriAttention had a slight edge in some cases, particularly on the large Qwen3-32B model.

But overall, Random Attention was still very competitive.

Evan: And what about throughput performance?

Ashley: Throughput was where Random Attention truly excelled.

By avoiding the scoring pass, Random Attention achieved 32 to 43 percent higher throughput across various models when compared to the strongest baseline, TriAttention.

For instance, on Qwen3-4B and Phi-4-reasoning, Random Attention served 32-43% more tokens per second in vLLM deployments.

Evan: That’s notable.

Higher throughput usually translates to more efficient use of resources and potentially lower costs.

Ashley: Indeed.

Another key point was the evaluation of the effectiveness under different compression pressures.

They tested compression factors from 2x to 16x to see how well Random Attention handled different levels of cache size reduction.

Evan: How did Random Attention perform under these varying conditions?

Ashley: Remarkably well.

At 2x compression, all methods were close to full attention in terms of accuracy.

But, as compression increased, Random Attention maintained its strong performance, staying competitive with TriAttention, while outpacing VaSE significantly.

Evan: It seems like Random Attention remains robust even as the cache budget tightens, which is crucial for practical deployments.

What about the methods' performance stability?

Ashley: They reported that Random Attention showed consistent performance across different runs with low variability, indicating stable and reliable behavior even under different conditions and across multiple datasets.

Evan: That’s good to hear.

Consistency is key when deploying these models in production environments.

Ashley: The consistent accuracy and higher throughput make Random Attention very compelling for real-world applications.

Evan: Were there any specific scenarios or tasks where Random Attention had particular strengths or weaknesses?

Ashley: Random Attention performed exceptionally well in math and science reasoning tasks, staying on par or even surpassing other methods.

However, for code reasoning, while still competitive, it occasionally lagged slightly behind TriAttention, especially as the model size increased and prompt lengths became a larger fraction of the cache budget.

Evan: Any other noteworthy observations from these experiments?

Ashley: One interesting point is that when the prompt was protected across all methods, the performance gap between different eviction strategies narrowed considerably.

This underscores the importance of prompt protection in achieving high performance.

Evan: So, protecting the prompt is a key takeaway here.

Anything else?

Ashley: They also performed planted-fact probes to test how well the methods retain critical information.

Random Attention showed that, due to cross-head redundancy, even randomly evicted data can still lead to high retrieval accuracy, thanks to the multiple restated information within the model’s layers.

Evan: It’s impressive how the method leverages the model's inherent redundancy to maintain performance.

Ashley: Indeed.

So in summary, Random Attention not only simplifies cache management but also delivers high performance and efficiency across a range of tasks and models.

Evan: That’s a comprehensive overview of the experimental results.

And with that, we've reached the end of the Experiment section.

Evan: Now, let's dive into the Related Work section of the paper to understand how Random Attention fits into the broader landscape of research in KV cache management and reasoning models.

Ashley: Sure.

The field of KV cache management for reasoning models has seen significant attention, especially given the memory bottlenecks that come with managing long sequences.

Various methods have been developed to address these challenges.

Evan: A major avenue of research has been around improving the efficiency of KV cache, particularly for tasks involving long-context understanding.

What's the general approach taken by these methods?

Ashley: One common approach involves quantization.

Studies like those by Liu et al. (2024) and Hooper et al. (2024) have looked into lowering the precision of stored tokens to maintain more within the same memory footprint.

Evan: Right, and aside from quantization, eviction methods themselves have been a primary focus, haven't they?

Ashley: Exactly.

Eviction methods aim to discard tokens under a budget while still preserving crucial information.

For instance, methods like StreamingLLM by Xiao et al. (2024) and H2O by Zhang et al. (2023) rely on scoring mechanisms to decide which tokens to keep.

Evan: And what kinds of scoring mechanisms are typically employed?

Ashley: Scoring mechanisms vary widely.

Accumulated attention scores, as in Zhang et al. (2023), attention from a sliding window, and redundancy-aware scores, as in R-KV by Cai et al. (2025), are all common approaches.

Each method introduces new heuristics believed to correlate with task accuracy.

Evan: So much focus on scoring.

But Random Attention seems to challenge this entire paradigm, doesn't it?

Ashley: Precisely.

This study shows that these complex scoring strategies may not be as critical as previously thought.

Their results indicate that protecting the prompt and using random eviction within attention heads can achieve comparable, if not better, performance.

Evan: It's quite a shift from the conventional approaches.

What about research into query-aware selection and sparse attention?

Ashley: Query-aware selection and sparse-attention mechanisms try to keep every token but attend to a subset per query, aiming to save on compute rather than memory.

This includes methods like SpeContext by Xu et al. (2026) and TriAttention by Mao et al. (2026), which employ calibrated trigonometric functions to score token retention.

Evan: And how does this fit into the long-context question-answering domain?

Ashley: Long-context QA often focuses on reducing memory usage during the prefill stage by compressing the input documents.

Some approaches, like those by Roy et al. (2026), aim for coverage of the input, while others, like Garcia (2026), show that protecting the prompt is as effective as optimizing the score.

Evan: How about the redundancy aspect that Random Attention leverages?

Ashley: Redundancy is a key concept highlighted by this paper.

Redundancy within the text and across attention heads means that even random eviction can retain enough useful information.

This is supported by findings from earlier works, like those by Cai et al. (2025), who demonstrate how reasoning traces can self-repair through restatements.

Evan: It's fascinating how these insights challenge the necessity of complex scoring mechanisms.

Were there any other types of related work mentioned?

Ashley: Indeed, the paper also discusses work on structurally focused methods like attention sinks and adaptive budget allocation, such as Ada-KV by Feng et al. (2025).

These involve rules that prioritize certain parts of the input over others.

Evan: And what about frameworks and tools that facilitate these methods?

Ashley: Frameworks like vLLM and plugins for different models play a crucial role by providing the runtime environment for these methods.

Tools that help manage memory dynamically are essential for implementing and testing new eviction strategies, as highlighted in works by Kwon et al. (2023) and others.

Evan: So, overall, while many methods and heuristics have been developed to manage the KV cache, Random Attention stands out by simplifying the process and leveraging inherent redundancies.

Ashley: Exactly.

And that's the end of the Related Work section.

Evan: We're nearing the end of our discussion on this fascinating paper.

Let's summarize the key contributions and takeaways.

Ashley: Sure.

The primary contribution of this paper is the introduction of the Random Attention method for KV cache eviction in large language models.

It challenges the conventional scoring-based eviction methods by demonstrating that random eviction, coupled with prompt protection, can achieve comparable performance and higher efficiency.

Evan: And by avoiding the scoring pass, Random Attention significantly boosts throughput, making it 32 to 43 percent more efficient in vLLM deployments compared to the best existing methods.

Ashley: Exactly.

The experiments showed that Random Attention maintains high accuracy across various reasoning tasks, including math, science, and code.

It performed exceptionally well in scenarios with compressed caches, demonstrating robustness and reliability.

Evan: The key insights include the importance of protecting the prompt and leveraging the redundancy of the reasoning trace, which is restated within the text and across attention heads.

Ashley: In essence, Random Attention simplifies the cache eviction process while maximizing performance and efficiency, making it a viable and deployable method for real-world applications.

Evan: That wraps up our discussion on 'Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning.' We hope you found this episode informative.

Ashley: Thank you for joining us today.

We invite you to tune in for future episodes where we continue to delve into exciting research in AI and machine learning.

Evan: See you next time on Daily Paper Cast!