CAOTE: Efficient Caching through Attention Output based Token Eviction

We thank the reviewer for their thoughtful feedback. Below, we address each of the reviewer’s points in detail:

1. Average prompt and generation lengths per dataset

We will include these details in the appendix. Below are the average prompt and generation lengths across tasks:

Prompt Lengths:

• QA tasks: 4k – 16k
• Summarization: 2.1k – 16k
• Few-shot learning: 5.2k – 22.4k
• Synthetic tasks: 7k – 11k
• Code: 1.5k – 4.2k
• Needle-in-the-haystack: up to 32k

Generation Lengths:

• QA tasks: 100–300 tokens
• Summarization: 300–800 tokens
• Multi-document reasoning: 500–1000 tokens
• Code: ~500 tokens

Thus, the total token usage is typically >4k, and often exceeds 6k or 8k, validating the relevance of our token budgets. As shown in the main paper, CAOTE consistently improves performance over baselines at 2k and 4k budgets.

2. Handling Grouped Query Attention (GQA)

In our current implementation, we evict the same token index across heads. For GQA, we compute the maximum CAOTE score across groups for each token and use that for eviction. We will clarify this in the paper.

Our method, like other token eviction strategies, can be extended to head-wise eviction, as explored in AdaKV.

3. KV cache eviction per layer

Yes, we perform KV cache eviction at every attention layer, consistent with the baselines we compare against.

4. Difference from [1] Feng et al. (2025)

Our method differs from [1] in both formulation and implementation:

• We derive a closed-form expression for the perturbation in attention output due to token eviction, grounded in optimization theory.
• In contrast, [1] proposes an upper bound on output perturbation, which is also discussed in [2].
• Algorithm 1 in [1] uses scores of the form, $(A+\epsilon).|V|_1$, where $A$ is the attention scores and $V$ is the value vectors, which is a heuristic approximation involving value vectors. This is fundamentally different from our CAOTE score, which is derived from exact optimization for single-token eviction.

References:

[1] Feng, Yuan, et al. "Identify Critical KV Cache in LLM Inference from an Output Perturbation Perspective." arXiv:2502.03805 (2025)

[2] Feng, Yuan, et al. "AdaKV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference." arXiv:2407.11550 (2024)

5. Generalizing CAOTE to other eviction methods

We agree that directly using CAOTE with methods like H2O or SnapKV may deviate from the theoretical assumptions in Section 3.1. However, we propose a reasonable generalization:

• Many custom eviction scores (e.g., H2O, SnapKV) are functions of attention scores, and can be interpreted as effective attention scores.
• We normalize these scores before applying CAOTE, which preserves token ranking but allows us to compute a meaningful CAOTE score using value vectors.
• Simply using attention scores based on last token with CAOTE is same as TOVA + CAOTE, which already boosts performance, however, is not suitable for other eviction methods.

Our empirical results show that this generalization is effective in practice, and we believe it opens up a flexible framework for combining CAOTE with a wide range of eviction strategies.

6. On CAOTE’s performance and gap to dense baselines

We respectfully disagree with the claim that CAOTE leads to marginal or worse performance. In Tables 2 and 3, CAOTE consistently improves the performance of baseline methods.

For example, on the Musique dataset with a 2k token budget:

• Dense baseline: 32.25
• H2O: 2.17
• TOVA: 14.77
• SnapKV: 16.53
• H2O+CAOTE: 22.06
• H2O+FastCAOTE: 24.55

This shows a significant improvement over all baselines, including SoTA methods. We observe similar trends across other QA tasks like Qasper and MF-en.

We believe CAOTE reduces the gap between dense inference and token-eviction-based methods, and we expect this to hold for more challenging tasks like RULER as well

We thank the reviewer again for their thoughtful feedback and hope our clarifications and additional analyses address the concerns raised.

We thank the reviewer for acknowledging the novelty and theoretical grounding of CAOTE. Below, we address each of the reviewer’s points in detail:

1. On multi-token eviction and suboptimality during prefill

We agree that our theoretical framework is based on single-token eviction, and we acknowledge that block-wise prefill involves evicting multiple tokens simultaneously. In this case, our current implementation uses a greedy, independent-eviction strategy, which may not be globally optimal.

We discuss the challenges associated with CAOTE's multi-token formulation. Below, we provide a detailed analysis of the sub-optimality of greedy, independent eviction and how CAOTE can be extended to handle multiple tokens jointly.

To illustrate, consider evicting two tokens in order $i=1, j=2$. From CAOTE, the single-token eviction error for token 1 is:

After evicting token 1, the updated attention output becomes:

Now, evicting token 2 from this updated distribution yields:

This leads to the following insights:

• The updated attention output can be expressed as:

• The eviction error for removing token 2 after token 1 is:

• Substituting the expressions above, we obtain a closed-form joint eviction score:

This formulation generalizes to evicting $m$ tokens jointly:

This expression highlights the combinatorial nature of multi-token eviction: for $n$ tokens and $m$-token eviction, there are $\binom{n}{m}$ possible combinations. This makes exact computation intractable for large $m$, motivating the need for approximate or greedy strategies.

Importantly, existing token eviction methods typically rely only on attention scores and assume independence between tokens. As a result, the relative ranking of tokens remains unchanged even after evictions, which limits their effectiveness in multi-token settings.

In contrast, CAOTE explicitly models the interplay between attention scores and value vectors, capturing how evicting one token affects the contribution of others. This introduces interdependencies between tokens during eviction, which are critical for accurate multi-token decisions.

We are actively exploring connections to discrete optimization to develop efficient algorithms for joint multi-token eviction, potentially leveraging submodular optimization or greedy approximations with theoretical guarantees.

2. Quantitative analysis of CAOTE and FastCAOTE overhead

We analyze the computational overhead of CAOTE and FastCAOTE during both prefill and generation phases. Let:

• $s$: sequence length
• $d$: hidden dimension
• $d_{KV}$: KV hidden dimension
• $d_{FFN}$: intermediate dimension
• $d_V$: vocabulary size
• $L$: number of hidden layers.

Floating-point Operation count:

• prefill flops: $2Lsd(d + d_{KV} + d_{FFN}+2s+6) + dd_V$
• generation flops: $2Ld(d + d_{KV} + d_{FFN}+2s+6) + dd_V$
• CAOTE flops: $Ls(7d+ 3)$
• FastCAOTE flops: $Ls(4d+3)+L$

Relative overhead for LLaMA3.1-8B:

Prefill Overhead Ratio: (CAOTE flops)/(prefill flops)

Generation Overhead Ratio: (CAOTE flops)/(generation flops)

These results show that CAOTE adds negligible latency, especially during prefill, and FastCAOTE is even more efficient.

3. On error propagation across layers

We refer the reviewer to Appendix B.2, where we relate the CAOTE score (eviction error) to downstream accuracy. Unlike other methods, CAOTE directly minimizes the change in attention output, which helps mitigate error propagation.

Our theoretical analysis suggests that early-layer errors propagate more significantly, motivating per-layer optimization. In future work, we plan to explore joint optimization across layers and adaptive cache budgeting, where earlier layers may receive larger budgets to reduce cumulative error.

4. Interaction with adaptive budget methods (e.g., AdaKV)

As discussed on lines 245–249, CAOTE complements AdaKV. While AdaKV dynamically adjusts cache size per layer based on attention scores, it does not consider value vectors. Integrating CAOTE into AdaKV can further improve eviction decisions by incorporating richer information.

5. On empirical justification for FastCAOTE

FastCAOTE approximates the CAOTE score by replacing the attention output with the mean value vector. While heuristic, we provide empirical evidence for its effectiveness.

We compare the value errors of both which is the main difference

• CAOTE: $|X_{attn}-v_i|_2$
• FastCAOTE: $|\mu(V)-v_i|_2$, where $\mu(V)$ is the mean value vector

Using a sample from NarrativeQA, we compute Spearman correlations across all layers for LLama3.2-3B:

[0.99 0.98 0.91 0.97 0.92 0.88 0.85 0.82 0.81 0.9 0.84 0.92 0.83 0.86, 0.91 0.88 0.94 0.96 0.92 0.95 0.99 0.99 0.96 0.98 0.98 0.88 0.99 0.96]

These high correlations demonstrate that FastCAOTE closely tracks CAOTE, justifying its use as a lightweight approximation. We will include this analysis in the camera-ready version.

6. On results with larger MoE models

We appreciate the reviewer’s suggestion. Our current focus has been on efficient frontier models such as LLaMA3 and Qwen2.5, which are well-suited for edge deployment scenarios where compute and memory constraints are critical.

We agree that evaluating CAOTE on larger Mixture-of-Experts (MoE) models would further demonstrate its generality. However, many state-of-the-art MoE models (e.g., DeepSeekMoE, Mixtral) are significantly larger and less practical for edge use cases. That said, we plan to include results on at least one open-source MoE model in the camera-ready version to strengthen the empirical scope of our work.

7. On comparison with CAKE (ICLR 2025)

Thank you for pointing this out. We will revise the Related Work section to include CAKE. Furthermore, CAOTE can be integrated with CAKE, which uses attention scores for slicing. Since CAOTE incorporates value vectors, the two methods are complementary and could be combined for further gains.

We thank the reviewer again for their thoughtful feedback and hope our clarifications and additional analyses address the concerns raised.

We thank the reviewer for their thoughtful feedback and for recognizing the novelty of incorporating value vector information in token eviction. Below, we address each of the reviewer’s points in detail:

1. Writing quality in Introduction and Method sections

We agree that the Introduction and Method sections can better highlight our contributions. In the camera-ready version, we will:

• Condense background material to make space for a clearer and more focused introduction to CAOTE.
• Add a concise explanation of how value vectors are integrated into the eviction score.
• Expand Figure 1 to illustrate the full CAOTE pipeline, not just the motivation

2. Incomplete experiments and social impact

We would like to clarify that our experimental setup aligns with recent token eviction papers. Importantly, CAOTE is not a competing method, but a boosting mechanism that improves the downstream accuracy of existing eviction strategies.

Regarding social impact, we believe our work is highly relevant for edge deployment, where memory and compute constraints are critical. By improving KV-cache compression, CAOTE enables:

• More accurate inference on edge devices,
• Reduced energy consumption,
• Enhanced user privacy by minimizing cloud dependency.

We will include a dedicated discussion on social impact in the camera-ready version.

3. Additional baselines: StreamingLLM, Quest, CAM

We appreciate the reviewer’s suggestions and clarify the following:

• CAOTE is complementary, not competitive. It can be applied on top of existing methods to improve performance.
• We included StreamingLLM (referred to as Sink in the paper) in Tables 6 and 7 (Appendix). It performs worse than TOVA, SnapKV, and their CAOTE-augmented versions.
• H2O+Caote outperforms StreamingLLM on LLaMA3 and Qwen2.5-3B models on QA tasks for 2k budget: Musique, 2WikiMQA, Qasper, MF-en.

We will:

• Add StreamingLLM results for additional budgets (2k, 4k).
• Include Quest and CaM in the Related Work section.

On Quest: It uses approximate attention scores. We believe CAOTE can be combined with Quest by approximating value vectors (e.g., using min/max pooling) and computing approximate attention outputs to guide eviction.

On CaM: It uses Eq. (14) based solely on attention scores. CAOTE can enhance this by incorporating value vector information. Note that CaM only reports results on LLaMA2, without comparisons to other eviction methods.

We will explore and report Quest+CAOTE and CaM+CAOTE results in the camera-ready version.

4. Scale of experiments

We agree that scaling to longer contexts is important. However, our focus is on edge deployment, where 1M-token contexts are currently impractical.

We emphasize that:

• Most baselines mentioned by the reviewer use outdated LLaMA2-7B models.
• We use state-of-the-art models like LLaMA3 and Qwen2.5, which have shorter context lengths but are more relevant for current applications.

Regarding InftyBench:

• Many open-source models require fine-tuning (e.g., LongLoRA, Qwen-Long) to be compatible.
• Once token eviction methods are evaluated on InftyBench, CAOTE can be applied to boost their performance.

We plan to include InftyBench results using fine-tuned long-context models in the camera-ready version.

5. On understanding why CAOTE works and clarification on Figure 3

(a) Why CAOTE works:

We believe the primary reason why CAOTE boosts the performance of existing cache eviction methods is because it optimizes for the change in attention output and seamlessly combines attention scores with value vectors—an underexplored component in token eviction.

Even though attention scores (or their variants) can be used to gauge the importance of a token, ultimately it is the value hidden state that is passed through the model layers and finally projected to logits to sample a token.

CAOTE's optimization is grounded in strong theoretical backing, as shown in Theorem 3.1 in the main manuscript, which establishes the connection between eviction error and dependence on value vectors:

This demonstrates how CAOTE computes the optimal eviction strategy.

Additionally, we discuss the relationship between CAOTE and downstream task performance in Appendix B.2.

Finally, the multitude of experiments on LongBench (QA, summarization, coding, etc.), perplexity, and retrieval tasks show that CAOTE consistently boosts the performance of existing token eviction methods.

(b) On Figure 3: We acknowledge that in some cases, the performance gap between baseline methods and their CAOTE-augmented versions may appear small. This is expected when the baseline is already near a local optimum. However, CAOTE helps push toward a global optimum. The gains are more pronounced in challenging settings. For example, on the Musique dataset (context length ~15k), using LLaMA3.1-8B with a 2k token budget, we observe:

• H2O: 8.78
• TOVA: 14.77
• SnapKV: 16.53
• H2O+CAOTE: 22.06

This significant improvement supports our theoretical claims and demonstrates CAOTE’s practical value.

6. On inference latency of CAOTE

We analyze the computational overhead of CAOTE and FastCAOTE during both prefill and generation phases. The overhead is minimal, especially for FastCAOTE.

Let $s$ be sequence length, $d$ the hidden dimension, $d_{KV}$ the KV hidden dimension, $d_{FFN}$ the intermediate dimension, $d_V$ the vocabulary size, and $L$ the number of hidden layers.

Floating-point Operation count:

• prefill flops: $2Lsd(d + d_{KV} + d_{FFN}+2s+6) + dd_V$
• generation flops: $2Ld(d + d_{KV} + d_{FFN}+2s+6) + dd_V$
• CAOTE flops: $Ls(7d+ 3)$
• FastCAOTE flops: $Ls(4d+3)+L$

Relative overhead for LLaMA3.1-8B:

Prefill Overhead Ratio: (CAOTE flops)/(prefill flops)

Generation Overhead Ratio: (CAOTE flops)/(generation flops)

These results show that CAOTE adds negligible latency, especially during prefill, and FastCAOTE is even more efficient.

7. On adaptation with inference engines

We agree that adapting CAOTE to inference engines like vLLM and SGLANG is important. However, we note that these frameworks currently do not support token eviction methods such as H2O, TOVA, or SnapKV either.

Once these methods are integrated into such engines, CAOTE can be seamlessly adopted as it builds on top of them. While this is outside the scope of the current paper, we view it as a valuable direction for future work.

We thank the reviewer again for their thoughtful feedback and hope our clarifications and additional analyses address the concerns raised.

Dear reviewer DSfh,

This is a kind reminder that reviewers should participate in discussions with authors. Please provide explanations about your updated (or not-updated) score and submit the “Mandatory Acknowledgement”. Please try to engage with the authors based on their rebuttal before the deadline. Your feedback is essential for the decision on this paper.

Thank you!

AC

We thank the reviewer for highlighting the strengths of our work. Below, we provide detailed responses to each of the reviewer’s questions:

1. Statistical significance and variability of CAOTE’s performance

We appreciate the suggestion to include variability measures. In the paper, H2O+CAOTE consistently shows strong performance, often surpassing TOVA and SnapKV. We refer the reviewer to Tables 2 and 3, particularly under the 2k token budget for QA tasks such as Qasper, MF-en, 2WikiMQA, and Musique, where H2O+CAOTE achieves the best results.

To further support this, we analyzed all baseline eviction methods with (and without) CAOTE on perplexity. We computed the difference between accuracy (or perplexity) per sample of a baseline method against baseline+CAOTE (and baseline+FastCAOTE). We report the mean, standard-deviation, minimum and maximum of this difference. We observe that with CAOTE the mean is always positive (showing gains), additionally the maximum gain ($\Delta$ Max Positive) is always much greater than the maximum loss ($\Delta$ Max Negative).

Statistics on perplexity improvement (decrease) for Lama3.2-3B with 2k budget

Therefore, sample-wise analysis shows that CAOTE (and FastCAOTE) help decrease downstream perplexity.

We will include additional variability analyses in the camera-ready version.

2. Extension to multi-token eviction

Extending CAOTE to multi-token eviction is an exciting direction, and we appreciate the reviewer’s interest in this aspect. Below, we provide a detailed analysis of the sub-optimality of greedy, independent eviction and how CAOTE can be extended to handle multiple tokens jointly.

To illustrate, consider evicting two tokens in order $i=1, j=2$. From CAOTE, the single-token eviction error for token 1 is:

After evicting token 1, the updated attention output becomes:

Now, evicting token 2 from this updated distribution yields:

This leads to the following insights:

• The updated attention output can be expressed as:

• The eviction error for removing token 2 after token 1 is:

• Substituting the expressions above, we obtain a closed-form joint eviction score:

This formulation generalizes to evicting $m$ tokens jointly:

This expression highlights the combinatorial nature of multi-token eviction: for $n$ tokens and $m$-token eviction, there are $\binom{n}{m}$ possible combinations. This makes exact computation intractable for large $m$, motivating the need for approximate or greedy strategies.

Importantly, existing token eviction methods typically rely only on attention scores and assume independence between tokens. As a result, the relative ranking of tokens remains unchanged even after evictions, which limits their effectiveness in multi-token settings.

In contrast, CAOTE explicitly models the interplay between attention scores and value vectors, capturing how evicting one token affects the contribution of others. This introduces interdependencies between tokens during eviction, which are critical for accurate multi-token decisions.

We are actively exploring connections to discrete optimization to develop efficient algorithms for joint multi-token eviction, potentially leveraging submodular optimization or greedy approximations with theoretical guarantees.

3. Clarification of notation in Eq. (8)

Thank you for the feedback. We will revise the notation in Eq. (8) and elsewhere to improve clarity. Specifically, all terms used in Eq. (8) are defined in the paragraph immediately preceding it (lines 124–126). In the camera-ready version, we will add more intuitive explanations to aid understanding

We thank the reviewer again for their thoughtful feedback and hope our clarifications and additional analyses address the concerns raised.

Dear reviewer V5hN,

This is a kind reminder that reviewers should participate in discussions with authors. Please provide explanations about your updated (or not-updated) score and submit the “Mandatory Acknowledgement”. Please try to engage with the authors based on their rebuttal before the deadline. Your feedback is essential for the decision on this paper.

Thank you! AC