acceptodds
Under review as a conference paper at ICLR 2027

Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

25 views

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 baseline in task performance while delivering 32-43% higher throughput than that method when deployed with vLLM. 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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV Cache Eviction, Efficiency, LLM Reasoning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_g34kOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces Random Attention, a KV cache eviction method that preserves the prompt and randomly retains reasoning tokens independently across attention heads. Across four reasoning models and six tasks, it achieves accuracy comparable to strong training-free eviction baselines and delivers 32–43% higher throughput than TriAttention in the evaluated vLLM setup. Controlled experiments suggest that prompt protection accounts for much of the performance gap between existing methods, while redundancy in reasoning traces helps tolerate random eviction. However, the method struggles with facts stated only once and needed much later, and its efficiency gains depend on workload and implementation.

Critical strengths
  1. The paper offers an interesting perspective: preserving the prompt can help maintain long-context capabilities in extended reasoning tasks, reducing the need for sophisticated KV cache eviction metrics.
  2. The authors propose a method that combines prompt preservation with random eviction, improving inference efficiency while maintaining competitive performance, and integrate it with existing inference kernels.
  3. The authors conduct extensive comparisons with training-free KV cache compression methods across multiple models and benchmarks, demonstrating the advantages of their approach.
  4. Further analysis shows that incorporating prompt preservation into existing methods can also improve their performance.
Critical weaknesses
  1. Is this method applicable to agentic and multi-turn settings? When the prompt spans multiple conversational turns, does the method remain effective?
  2. Could existing KV cache compression methods, particularly training-based approaches, implicitly learn to preserve the prompt? In other words, could prompt preservation account for much of their performance advantage over some training-free methods?
  3. The effectiveness of the proposed method should be validated across a broader range of model families.
  4. Does the method fail when the prompt is long or the KV cache budget is small? I suggest that the authors include a comparative analysis of its limitations under these conditions against other methods.
Questions for authors

Seeing Weakneesses.

Reviewer_pongOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper revisits KV cache compression for long chain-of-thought reasoning and proposes Random Attention, a simple eviction rule that keeps prompt tokens and randomly evicts generated tokens under a fixed KV budget. Its main empirical claim is that sophisticated importance scoring may be unnecessary for effective eviction in this setting. It evaluate the method on several reasoning benchmarks and reports competitive accuracy and throughput compared to existing importance-based eviction methods.

Critical strengths
  1. An interesting empirical finding about KV cache compression for reasoning.
    The paper challenges the assumption that effective KV eviction requires sophisticated importance scoring. The result that random eviction can match importance-based methods is surprising and offers a useful perspective on the memory needs of long chain-of-thought reasoning. The analysis of prompt preservation also highlights a meaningful distinction between prompt tokens and generated reasoning tokens.

  2. A simple, low-overhead method that serves as a practical baseline.
    Random Attention avoids explicit importance scoring, making it simple and computationally cheap. It achieves competitive accuracy across several reasoning models and benchmarks and reports throughput gains in a vLLM-based serving setup. These properties make it a useful reference point for future KV eviction methods.

Critical weaknesses
  1. The explanation for robustness to random eviction is insufficiently substantiated. The authors mainly attribute this robustness to redundancy in reasoning traces, but the current analyses provide limited direct evidence. It also remains unclear whether the effect reflects properties specific to reasoning traces or more general traits of long-form generation, and how non-redundant long-range dependencies affect random eviction. Since the main contribution is an empirical finding that challenges importance-based KV selection, a clearer account of the underlying factors would strengthen its scientific value and delimit the conditions under which it holds.

  2. Robustness under sustained KV eviction is not sufficiently validated.
    Aggregate accuracy may mask differences between correct and incorrect predictions. Correct predictions may concentrate on shorter traces with limited eviction, while longer traces could degrade more severely. A finer-grained analysis by reasoning length and eviction pressure is needed to establish whether the reported robustness holds under sustained KV compression.

Questions for authors
  1. Please clarify how the evaluated reasoning workloads differ from other long-generation workloads, such as agentic tasks, in terms of information redundancy and long-range dependencies, and provide evidence on whether the frequency of such dependencies explains the observed robustness to random eviction.
  2. Please report generation-length distributions separately for correct and incorrect predictions, and accuracy stratified by reasoning length or effective eviction pressure.
Reviewer_YUiQOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Random Attention, a simple KV cache eviction method for LLM reasoning. Existing cache compression techniques score each cached token by estimating how much it will matter later and keeps only the top scoring ones. This paper argues that this score keeping mechanism contributes nothing. The proposed algorithm preserves all prompt tokens and randomly evicts generated reasoning tokens, without computing importance scores. Experiments show that this method has an accuracy comparable to the strongest baseline while improving throughput by 32-43%. This method is just as effective as the existing methods because the prompt is the fragile part. The rest of the cache consists of the models reasoning trace, which is redundant by nature. Thus, it preserves itself.

Critical strengths

Strengths:

  • Improves throughput by 32-43%, which is impressive.
  • Very simple approach with interesting observations
Critical weaknesses

Weakness

  • Does not evaluate on a diverse set of models. It covers 4 models, 3 of which belong to the Qwen3 family. Also, although the paper tests 2×–16× compression, the sweep covers only Qwen3-4B and Phi-4-reasoning. Whether the findings hold across budgets for larger models remains unclear.
  • On Qwen3-32B code tasks, Random Attention produces 44% longer traces, which removes its end-to-end speed advantage?
Questions for authors

See weakness.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.