We apologize for any confusion caused. Your suggestions are highly valuable, and we have revised our manuscript to address unclear statements. These changes have greatly enhanced the clarity of our work. Thank you for your meaningful contribution!

Reply to Question1 and Question2：

Thank you for pointing out the typos, and we apologize for any confusion caused. We have corrected these issues in the revised version.

Reply to Question 3：

Yes, you are right. Thanks for pointing out the imprecise wording. We have revised the paper by moving the algorithm section to precede the theoretical analysis, improving the overall readability. Additionally, we have provided detailed proof for Theorem 3, which has significantly enhanced the presentation of our work.

Reply to Question4 Needle-in-the-Haystack Results：

Thanks for your suggestions! We have added the needle-in-the-haystack test, with detailed results included in Appendix E of our paper. Using Llama-3.1-8B with a budget of 128, we extended inference up to the model’s maximum supported length of 128K. Under the Full Cache setting, the retrieval score reached 87.58. Our algorithm enhances the long-context retrieval capabilities of all cache eviction methods, including SnapKV, Pyramid, and AdaKV, improving their retrieval scores from 81.01, 82.53, and 82.71 to 82.01, 82.95, and 83.35, respectively.

Reply to Question4 Larger LLM Results：

Thanks for your suggestions! However, we found that for 70B LLMs, even with cache compression, running long-sequence benchmarks demands immense computational resources. This is primarily due to the significant computational overhead during the prefill stage for long sequences and the substantial GPU memory consumption resulting from the model's large parameter size. We believe this may also explain why most cache compression studies typically evaluate on small parameter sizes like 7B or 8B.

To address your concerns within our feasible resource constraints, we opted to evaluate another model, Qwen-2.5-32B, a leading open-source LLM. We assessed SnapKV, both with and without our algorithm, under budgets of 128 and 1024. With the discussion phase already halfway through, we look forward to engaging with all reviewers promptly to resolve concerns. Thus, we present experimental results have achieved so far, with the complete experimental findings to be included in the final version of the paper.

We hope our responses have helped address your concerns. Should you have any additional questions, we would be more than happy to provide further clarification.

Reply to performance and budget constraints

the average improvement achieved is often marginal.

We clarify that the improvement achieved by our method is not marginal.

1. Significant Budget Savings: As demonstrated in Figure 1 of our paper, our method achieves an average additional budget saving of 19.7% and up to 34% compared to current SOTA cache eviction methods, all while maintaining the same quality score. This is primarily due to the inherent trade-off in cache eviction tasks, where significant budget investment typically yields only minimal accuracy improvements. Consequently, any enhancement in accuracy is highly valuable. This means our method allows for substantial additional budget savings while maintaining equivalent accuracy, directly translating into significant KV cache memory reductions and accelerating subsequent decoding processes.

2. Robust and Universal: Our algorithm is a robust and broadly applicable cache eviction enhancement method. It can seamlessly integrate with any current SOTA methods based on attention weights to further boost performance. Given its simplicity and generality, the observed performance improvements are quite remarkable.

the performance degradation at budget b appears too severe to be practical in real-world settings.

Thanks for your question. We would like to clarify that, on the contrary, the accuracy degradation is minimal. For instance, as shown in Table 3, the Llama-3.1-8B model achieves an average quality score of 49.20 with the full KV cache and an average sequence length of 6711. With Ada-KV combined with our method, using a budget of 1024 (6.6x compression ratio) results in only a 2.2% reduction in the quality score (48.13). At a budget of 512 (13.2x compression ratio), the quality reduction is merely 3.07% (47.70). In practical applications, this means that with just a 3% accuracy trade-off, you can compress a sequence by 13.2x. Under the same KV cache capacity, this represents a highly practical and efficient trade-off for real-world scenarios.

Notably, increasing compression from 6.6x to 13.2x costs only 0.87% in accuracy, underscoring the value of even slight accuracy improvements. Such gains can enable further compression, yielding significant practical benefits in real-world applications.

Could the authors provide insight on the specific budget value 1024 < b<6711 perhaps (2048, 4096) at which both their approach and other key-value eviction strategies yield comparable performance to the baseline? Additionally, is there a discernible advantage to the proposed method under these conditions?

Thanks for your question! The table below provides the accuracy of various methods under a budget of 4096, along with their respective accuracy loss ratios compared to the Full Cache scenario. Indeed, when the budget is increased to a large value, such as 4096, the average compression ratio becomes minimal. Consequently, all methods—including SnapKV, Pyramid, and AdaKV, as well as their enhanced versions using our approach—achieve nearly identical lossless accuracy, around 0.6% loss on LongBench.

However, we emphasize that practical applications prioritize smaller compression budgets, such as budget 128-1024, which are more relevant for real-world deployment. For example, using SnapKV with our enhancements, increasing the compression ratio from 1.6x to 6.6x (budget 4096 → 1024) results in only a modest accuracy drop of 1.28% (from 0.65% to 1.93%), demonstrating an appealing trade-off.

It is also important to note that cache eviction is primarily useful in scenarios requiring high compression ratios, typically exceeding 10x. At such ratios, it demonstrates outstanding advantages over full cache methods, making it motivating for real-world applications. This is supported by related works, such as PyramidKV and SnapKV, which also focus on compression budgets ranging from 128 to 1024 in their LongBench evaluation.

We hope our responses have helped address your concerns. Should you have any additional questions, we would be more than happy to provide further clarification.

Reply to arbitrary choice of $\alpha$

I also find that Appendix A does not sufficiently address the arbitrary selection of α. Does the model’s performance change with varying α, and would such variation impact the conclusions drawn?

This is a good question.

First, we would like to clarify that even when $\alpha$ is set to 0, our algorithm remains effective. This is supported by the ablation study presented in Appendix D: although the performance is slightly degraded compared to the setting where $\alpha = 0.25$ (as used in the main experiments), it still significantly outperforms the vanilla baseline. Second, we agree with your observation that the model’s performance changes with varying $\alpha$. This relationship can be better understood through a conceptual lens: $\alpha$ represents the modification strength of our algorithm relative to conventional Top-K selection. When $\alpha = 0$, the algorithm fully incorporates both the norm of the projected value states and the attention weights in its decision-making. Conversely, when $\alpha = 1$, our algorithm degrades into a vanilla attention-weights-based Top-K selection (vanilla SnapKV Pyramid or AdaKV). Both extremes, as shown by our ablation and main experiments, are suboptimal choices.

Then why do we choose $\alpha = 0.25$ in this paper?

Given the computational overhead of hyperparameter tuning in LLMs on the LongBench evaluation, conventional grid search for $\alpha$ is impractical. Instead, we followed a theoretically guided approach: we determined that an $\alpha$ portion of 0.25 sufficiently satisfies our Assumption 1 across most attention heads. While it is true that a small number of heads may violate this assumption, their adverse impact is negligible, as the advantages gained from other heads overwhelmingly compensate for these exceptions. Further optimizing $\alpha$ on a finer granularity—for instance, setting $\alpha$ on a per-head basis to address such outliers—could offer additional benefits. However, this would require careful consideration of multiple factors, including model-specific characteristics, budget constraints, and downstream tasks, thereby introducing considerable algorithm complexity. Consequently, we think this is an interesting direction for future research.

Thank you for your valuable suggestions on our paper. Based on your feedback, we have revised the manuscript and addressed your concerns as follows:

Reply to some writing and formatting issues

Section 3.2: In my opinion, this section needs to be reformatted and partially rewritten to be more concise with a clearer structure. As the most essential part of the paper, it is currently challenging to read, with many notations introduced ambiguously and references placed somewhat haphazardly.

Thank you for your valuable feedback! We have rewritten this section to provide more precise statements, included relevant references, and simplified the notation to enhance clarity.

Equation Alias: The author should create an alias for $\frac{N \odot A}{\sum_n N_i A_i}$ to simplify and streamline the equations that reference this expression.

Thank you for your suggestion! We recognize the necessity of simplifying notation in theoretical formulations. As a result, we have revised the statement of Theorem 1 to explicitly define $A' = \frac{N \odot A}{\sum_n N_i A_i}$. Additionally, we have rewritten the subsequent theorems and their proofs, ensuring a clear and rigorous presentation.

Assumption 1 and Theorem 3: I believe these should form their own subsection,

Thank you for your suggestion! We have revised our paper by splitting the original Section 3.3 into three sections: 3.3, 3.4, and 3.5. The new Section 3.3 focuses on addressing the argument: "Are attention weights sufficient for identifying critical cache entries?" Section 3.4 is dedicated to presenting the core method, while Section 3.5 emphasizes its theoretical analysis.

Reply to unclear points

Additionally, there are several points I still find unclear...

These statements critique the empirical reliance on attention weights as indicators of importance. Could the authors clarify how they reconcile these criticisms with their own assumption about using attention scores to represent the importance of key-value entries?

Thanks for your question! We do allocate a small portion of the budget in Assumption 1(Stage 1 in our algorithm) to collect some critical cache entries. However, this does not contradict our core argument that solely relying on attention weights is insufficient for identifying critical cache entries. The evidence lies in the fact that the majority of our budget is allocated to simultaneously consider both attention weights and the norm of projected value states for improved critical cache selection (Stage 2 in our algorithm). While it is feasible to rely solely on stage 2, omitting stage 1 (Assumption 1) entirely, our algorithm still demonstrates significant benefits as shown in the ablation study(Appendix D). However, the inclusion of stage 1 provides a stronger theoretical foundation and consistently enhances performance, as demonstrated by our analysis and experimental results.

Our algorithm operates in two distinct stages. Stage 1 (under Assumption 1) utilizes a small portion of the budget $b'$ to collect critical cache entries solely based on attention weights. Stage 2, which forms the core of our method, allocates the majority of budget $b''$ to account for both attention weights and the norm of projected value states. This two-stage algorithm is specifically designed to constrain the worst-case perturbations during selection.

Overall, stage 1 in our algorithm serves as a preparatory step rather than the primary focus of our work. However, its inclusion is necessary for both theoretical and practical reasons. From a theoretical perspective, as shown in Theorem 3, the collection of $b'$ in stage 1 ensures the objective of stage 2 to align with constraining output perturbations, i.e. $\hat{\theta}$, enabling the effective selection of critical KV cache entries. From a practical standpoint, we demonstrate the necessity of the first stage in the ablation study presented in Appendix D. When the first stage is removed $\alpha = 0$, the algorithm's performance exhibits a noticeable decline. In this revised version of our paper, we have made the relationship and distinction between the two stages more explicit, ensuring a clearer presentation of their respective roles and contributions.

Reply to Question of Experiments

I highly suggest the author to evaluate the proposed algorithm in other popular LLM benchmarks (e.g., AlpacaEval). This is necessary to understand the performance of the proposed algorithm on a wider spectrum of scenarios.

Thanks for your suggestion! Following your recommendation, we test the performance of SnapKV and SnapKV with ours using Llama-3.1-8B in AlpacaEval with Deepseek-chat and Yi-Large as Auto-annotators. The results, which demonstrate an impressive performance improvement with our method, have been included in Appendix L. Regarding compression settings, we analyze AlpacaEval and find that the average input length is 36.5 tokens, while the average generated length is 567 tokens. Thus, we conduct compression experiments by compressing the cache size to 64 tokens when the context length exceeds 256 tokens—approximately half of the average generated length. As shown in the table, our enhanced version of SnapKV significantly outperforms the original SnapKV version. For instance, using Yi-Large as the Auto-annotator, our method improves the scores for Win Rate and LC Win Rate from 19.61 and 18.76 to 21.20 and 19.79, respectively.

We hope our responses have helped address your concerns. Should you have any additional questions, we would be more than happy to provide further clarification.

Thank you for your feedback and recognition of our work. We have revised our manuscript based on your suggestions, which has further improved its quality.

Reply to Question of Writing

On the proposed kv cache eviction algorithm, it would be better to discuss the connection and difference with FastGen [1] and MInference [2] in more details, given the similarity of the resulting algorithm. Also, as to the output perturbation, I feel it would be helpful to discuss the existing success of this concept's adaptation in other deep learning algorithms (e.g., [3] and [4])

Thanks for your suggestions! We have added an additional section in Appendix J discussing the relationship between these works with our method. Below is a summary of our key points:

We have cited two related works, FastGen and Minference, and provided a detailed discussion of their relationship to our work. Notably, these two works stand out for their use of adaptive strategies, leveraging distinct critical cache selection mechanisms tailored to the characteristics of different attention heads. For instance, some heads employ attention weight-based selection, while others utilize fixed patterns, such as recent-window-based selection. In our paper, we demonstrate that our method effectively enhances the performance of solely attention-weight-based selection. This suggests a promising direction for future research: further enhancing strategies specifically designed for heads using attention-weight-based selection, thereby improving the overall quality of adaptive methods.

We have also expanded the discussion on prior perturbation-based analyses, including Catformer and Admin, both of which represent valuable contributions to neural network interpretability. The Catformer applies perturbation analysis to design more stable architectures, while Admin examines output perturbations in residual blocks to improve training stability. Our work extends perturbation analysis to the attention mechanism, focusing on perturbations caused by cache eviction. We propose improved critical cache selection metrics that mitigate these perturbations. These works collectively address perturbations in different components, such as residual connections and attention mechanisms. Future research could integrate these perturbation analysis strategies to conduct a more comprehensive investigation into network perturbations. Such an approach could guide the development of more robust architectures, training methodologies, and inference schemes.

Reply to Question of Analyses

Additional theoretical analysis could strengthen the output perturbation perspective. A key area for investigation is the correlation between worst-case output perturbation predictions and actual perturbation measurements in real-world applications.

Thank you for highlighting this critical aspect. However, conducting a comprehensive theoretical analysis of actual perturbations remains challenging. The gap between theoretical perturbation and real-world perturbation measurements arises from inherently complex and difficult-to-analyze factors, such as the cumulative effects of multiple Transformer layers, residual connections, and feed-forward networks.

Nonetheless, we attempted further analysis of output perturbations. As detailed in Appendix F, we demonstrate that the previously proposed method, based solely on attention weights, is equivalent to optimizing a relaxed upper bound, $\hat{\theta}^{relax}$. In contrast, our algorithm optimizes a tighter upper bound $\hat{\theta}$. While this does not guarantee that our approach will yield a strictly better solution, intuitively, an algorithm designed to optimize a tighter bound often achieves better results.

From the perspective of actual perturbation measurements, in Section 5, we provide an empirical analysis under various conditions. As shown in Figure 2, our method significantly reduces perturbations across most heads in all tested models. Furthermore, in Figure 3, we demonstrate that these reductions propagate effectively, leading to a notable decrease in final-layer perturbations under various budget constraints. This, in turn, mitigates the quality degradation often observed with conventional cache eviction methods. To some extent, these results also validate the effectiveness of our theory. We hope this addresses your concerns.

Dear Reviewer YE2P,

We hope this message finds you well. Thank you for your thoughtful reviews of our submission.

We have carefully addressed your concerns and made the necessary revisions to improve our work. As the discussion phase nears its conclusion, we kindly request your evaluation of our responses. If our revisions have satisfactorily addressed your concerns, we would be deeply grateful for your reconsideration of the overall score.

Should you have any additional points that require clarification, please do not hesitate to reach out—we would be happy to engage in further discussion. Thank you once again for your valuable feedback and contributions to improving our work.

Best regards,

Authors.

Thank you for your effort and feedback; it means a lot to us. We will address your concerns below, and the related discussions have been added to the appendix of the revised manuscript to offer a broader perspective on our work.

Reply to Weakness 1

For example, why a subset of KV is sufficient for LLM inference? Instead of claiming that it is a commonly accepted assumption from empirical studies, more insights from theoretical perspective are expected since this paper emphasizes its theoretical contributions.

Thank you for your suggestions. We have included a detailed theoretical analysis in Appendix F for this assumption. In Appendix F, we derive a relaxed upper bound $\hat{\theta}^{relax}$ for output perturbation that directly correlates with attention weights. Considering H2O's observation[1] that attention weights follow a power-law distribution—only a small fraction of KV cache entries have significant attention weights, while the majority exhibit weights close to zero. Thus discarding most KV cache entries with near-zero attention weights has minimal impact on this bound. Consequently, the perturbation to the actual output is also bounded by this upper bound. This result provides a theoretical analysis for the widely accepted assumption that a subset of KV entries suffices for LLM inference.

[1] Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher R ́e, Clark Barrett, et al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36, 2024b

(1)Why L1 distance is a good metric for measuring the output perturbation? L1 distance is well-known for its sparsity-sensitivity, but the attention outputs are dense. Any further explanation or theoretical supports for this metric?

This is an interesting question, and we have included our views in Appendix G in the revised manuscript. In this paper, we employ the simplest distance metric, L1 distance, for our analysis, while future work could explore the use of L2 distance or other metrics. We chose $L_1$ distance for the following two reasons:

1. Theoretical Perspective: The L1 distance, as a straightforward metric, facilitates the construction and derivation of our theoretical framework. As you mentioned, $L_1$ distance is likely to be sparsity-sensitive. However, the $L_1$ distance used in this work could encourage the sparsity of perturbations rather than directly influencing the attention output itself. Therefore, we believe that the sparsity induced by $L_1$ regularization does not compromise the quality of the results.

2. Practical Perspective: Considering that BF16 (half-precision floating-point) is commonly used in inference computations, the L1 distance operations derived from our algorithm provide better numerical precision. In contrast, metrics such as $L_2$ distance may introduce numerical precision issues due to the squaring and square-rooting operations inherent in their computation.

Fundamentally, the choice of distance metric is orthogonal to our primary contributions. We also appreciate your suggestions and plan to further investigate the impact of different distance metrics in future work.

Reply to Weakness 1(Continued)

(2)What's the relationship between output perturbation and the generation quality? Perturbation measures the deviation from the original output, but does this deviation have a significant impact on determining the output token?

Thanks for your question! Output perturbation indeed has a significant impact on determining the output token thereby affecting generation quality. We directly measure the difference in token vocabulary distributions between SnapKV (and SnapKV with our method) and the original full KV Cache case on 200 samples from the Qasper dataset (QA dataset in Longbench). The comparison, shown in the table below, focuses on the first four generated tokens. Regardless of the token position or whether $L_1$ distance or KV divergence is used as the metric, our method consistently reduces perturbation in the token vocabulary distribution for most samples. This demonstrates that our enhanced approach significantly improves consistency with the token distribution of the uncompressed case, effectively mitigating the quality degradation caused by compression.

The number of samples with lower perturbation in token vocabulary distributions for generation (higher is better).

Next, we approach this from a different perspective and incorporate this discussion into Appendix I in the revised manuscript.

In LLM computations, the attention output serves as an input to the FeedForward Neural Network (FFN) module, producing outputs that are subsequently passed to the Language Model (LM) head to generate the token vocabulary distribution. Our algorithm specifically aims to reduce perturbations in attention outputs caused by cache eviction methods. This reduction lowers the perturbations in the inputs to downstream network components (FFN and LM head), thereby mitigating perturbations in the final token vocabulary distribution. Consequently, our method reduces the impact of cache eviction on output token generation.

This conclusion is supported both theoretically and empirically. Theoretically, the relationship between reduced input perturbations and diminished output variations is well-established, as seen in Lipschitz continuity [2-3], which posits that functions with bounded Lipschitz constants exhibit smaller output differences for smaller input differences. This principle is consistent with our approach to minimizing attention output perturbations, thereby ensuring subsequent generated tokens. Similarly, FFN pruning techniques in LLMs[4-5] also demonstrate the practical success of minimizing perturbations to downstream layers' outputs, further validating our strategy.

[2] Harry Dong, Beidi Chen, and Yuejie Chi. Prompt-prompted adaptive structured pruning for efficient llm generation. 2024.

[3] Mingjie Sun, Zhuang Liu, Anna Bair, and J. Zico Kolter. A simple and effective pruning approach for large language models, 2024.

[4] Yuesheng Xu and Haizhang Zhang. Uniform convergence of deep neural networks with lipschitz continuous activation functions and variable widths. IEEE Transactions on Information Theory,70(10):7125–7142, 2024.

[5] Grigory Khromov and Sidak Pal Singh. Some fundamental aspects about lipschitz continuity of neural networks, 2024.

Reply to Weakness 2

For example, StreamingLLM should be considered since it is an important empirical work.

Based on your suggestion, we have added StreamingLLM as a baseline for comparison in Appendix H.

Since StreamingLLM does not rely on attention weights based selection for cache eviction and instead retains only the several initial cache entries and those within the recent window, it can't be combined with our algorithm. Due to the non-selective nature of its eviction strategy, StreamingLLM performs significantly worse than existing selection based cache eviction methods, e.g. SnapKV.

For instance, consider SnapKV w/ ours on Llama3.1-8B as a representative example of selection-based cache eviction approaches. The quality scores of StreamingLLM under cache budgets ranging from 128 to 1024 are 38.42, 39.75, 41.52, and 42.56, respectively. In contrast, the selection-based cache eviction methods achieve significantly higher scores of 43.25, 45.66, 47.41, and 48.25 under the same budget configurations. Detailed results can be found in Appendix H.

Besides, the naïve attention mechanism (without any KV dropping) should also be included. The authors should demonstrate the generation quality gap between eviction methods and the ground-truth.

The naïve attention mechanism without KV dropping is described in Tables 1, 2, and 3 of the paper, labeled as "Full Cache", where its performance is thoroughly presented. Using the SOTA method AdaKV w/ours as an example, when the existing cache eviction algorithm is enhanced by our method, the quality loss is only 1.45% at a 1024 budget with compression. For a further 8x compression at a 128 budget, the quality loss only increases to 9.2%.

Additional long-text retrieval Benchmark ：Needle-in-the-Haystack Test

We have also added a widely used benchmark for long-text retrieval task, the needle-in-the-haystack test, with detailed results provided in Appendix E. Using the Llama-3.1-8B model and a budget of 128, we extended inference to the model's maximum supported length of 128K, achieving up to a 1000x compression ratio. Under the Full Cache setting, the retrieval score reaches 87.58. Our algorithm improves the long-context retrieval performance of all cache eviction methods - SnapKV, Pyramid, and AdaKV - boosting their retrieval scores from 81.01, 82.53, and 82.71 to 82.01, 82.95, and 83.35, respectively. This further underscores the effectiveness of our algorithm in cache compression for long-sequence retrieval tasks.

We hope our responses have helped address your concerns. Should you have any additional questions, we would be more than happy to provide further clarification.

Reply to Weakness 1(Continued)

Why set alpha to 0.25? The attention weights obey the power-law distribution, but why setting a fixed hyper-parameter is reasonable for any models and input distributions? Deriving this parameter directly from the attention weight distribution seems to be more reasonable.

Setting $\alpha$ as an adaptive threshold for individual heads can indeed improve quality further. However, after careful consideration, we decided not to adopt this approach for the following reasons:

1. Increased Complexity and limiting practical application: To implement an adaptive threshold, distinct values of $\alpha$ must be set for each head in different LLMs, across various budget configurations, and even for different input tasks. In the case of a 7B or 8B model, this requires setting unique $\alpha$ values for 32 $\times$ 32 heads. Whether through offline or online analysis, this approach introduces substantial search overhead, which further complicates the process and restricts its practical applicability.

2. A Simple, Effective Solution with a Fixed $\alpha$ = 0.25: A fixed $\alpha = 0.25$ serves as a simple and robust solution. Visualizations in Appendix A demonstrate that this fixed threshold satisfies Assumption 1 for the majority of heads, leaving a 75% budget to execute our novel selection strategy. While there are exceptions in a few heads in shallow layers, our analysis shows that these discrepancies are effectively mitigated by the advantages of subsequent layers. By the final Transformer layer, output perturbations are significantly reduced.

Overall, a straightforward and robust $\alpha$ = 0.25 setting allows our algorithm to achieve up to 34% cache budget savings, as illustrated in Figure 1, under comparable generation quality across three existing eviction algorithms (SnapKV, Pyramid, and AdaKV) tested on two LLMs.

Dear Reviewer hVtB,

We hope this message finds you well. Thank you for your thoughtful reviews of our submission.

We have carefully addressed your concerns and made the necessary revisions to improve our work. As the discussion phase nears its conclusion, we kindly request your evaluation of our responses. If our revisions have satisfactorily addressed your concerns, we would be deeply grateful for your reconsideration of the overall score.

Should you have any additional points that require clarification, please do not hesitate to reach out—we would be happy to engage in further discussion. Thank you once again for your valuable feedback and contributions to improving our work.

Best regards,

Authors.