- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies how KV-cache eviction changes autoregressive generation. It decomposes token mismatch into first-divergence effects and post-divergence disagreement, proves a sharp partial-identification result for finite divergence-aligned observations, and proposes an unbiased conditional Monte Carlo estimator. Experiments with Llama-3.1-8B-Instruct and Qwen2.5-7B-Instruct find that delaying or avoiding divergence explains most of the mismatch reduction from SnapKV relative to recent-token eviction.
Critical strengths
Provides a clear, mathematically grounded decomposition of cumulative disagreement. The partial-identification theorem precisely characterizes what finite observations can establish. Uses an independent 90%-retention cohort and document-level uncertainty estimates to support key empirical findings. Carefully distinguishes divergence-aligned behavior from averages over generation positions.
Critical weaknesses
Practical significance remains unclear. Token mismatch and next-token total variation do not directly establish differences in task accuracy, semantic quality, or user-perceived output quality. Experiments cover only two language models, a horizon of 128 generated tokens, and a specific sampling setup, limiting generalizability. The central findings depend on a specified maximal-coupling construction; the implications for other ways of comparing model outputs are not established. The conditional Monte Carlo method is theoretically justified, but its practical computational advantage for full-scale Transformer inference remains insufficiently demonstrated.
Questions for authors
- How well do the proposed divergence metrics correlate with downstream task performance or semantic quality?
- Do the main findings hold across longer generation horizons, additional models, and different sampling temperatures?
- What is the wall-clock and compute-normalized benefit of the conditional Monte Carlo estimator on full-scale models?
2 comments
Response to Reviewer 2yhy (Part 2)
W3. “The central findings depend on a specified maximal-coupling construction; the implications for other ways of comparing model outputs are not established.”
We thank the reviewer for this observation. The coupling preserves both marginal generation laws. Common-token probabilities fix the first-divergence law across stepwise maximal couplings, while residual pairings can change histories after divergence. At each history pair, the conditional mismatch probability equals the total variation between the two next-token distributions (§3.1).
W4. “The conditional Monte Carlo method is theoretically justified, but its practical computational advantage for full-scale Transformer inference remains insufficiently demonstrated.”
We thank the reviewer for this comment. The estimator integrates out the zero-loss event of full agreement. It weights the sampled suffix by the total first-divergence mass along the auxiliary overlap path. Proposition 4.1 establishes unbiasedness and variance at most that of one ordinary coupled replicate for cumulative mismatch. Wall time includes the scan, replay, and suffix costs (Section 4).
Q3. “What is the wall-clock and compute-normalized benefit of the conditional Monte Carlo estimator on full-scale models?”
We thank the reviewer for this question. The measured error–time trade-off differs by model. At H = 128, we evaluate 48 documents per model and three SnapKV budgets. The SWRB-to-ordinary ratios of the mean per-replicate product of squared error and estimator wall time are 2.38 on Llama-3.1-8B and 0.897 on Qwen3-8B, favoring ordinary sampling for Llama and SWRB for Qwen3. Squared error is measured against an independent 16-replicate SWRB reference mean, and timing covers estimator execution after prefill and initial cache compaction (Appendix C.1).
Taken together, the results specify the law used to compare trajectories and show how the variance guarantee and measured efficiency answer different questions.
Response to Reviewer 2yhy (Part 1)
Thank you for the valuable feedback. We are particularly encouraged by your comments appreciating our motivation and experiments. Below, we address your questions in detail.
We thank the reviewer for this observation. Task-native LongBench scores reveal a different selector ranking on Qwen. We evaluate Qasper, HotpotQA, and GovReport (568 questions from 518 context parents per model). Mismatch comes from the 128-step coupled rollouts, and the LongBench mean equally weights the three task-native scores (Table 2). The final column gives the mean change from FullKV in points, with pointwise 95% paired context-parent bootstrap intervals (Table 15).
On Qwen, CriticalKV has the lowest mismatch, while SnapKV has the highest task-score point estimate among compressed selectors.
We thank the reviewer for this question. Timing metrics improve pooled retrospective prediction of content-score changes. On saved 128-step HELMET and RULER trajectories, adding divergence probability and exposure reduces document-grouped out-of-fold MSE from 0.04061 to 0.03703 (8.8%). The baseline includes cumulative mismatch, fixed-history TV, and covariates. The 95% document-bootstrap interval for the MSE reduction is [0.00210, 0.00545].
In the split-half analysis described in Appendix F.1, we compute trajectory features from 32 of the 64 rollouts and content-score changes from the other 32. The pooled MSE reduction is 0.00361 when features come from the first half and 0.00327 when the halves are reversed. In the full-sample analysis, MSE improves in all three RULER strata and worsens in all three HELMET strata by point estimate. The MAE reduction interval spans zero.
We thank the reviewer for this comment. We extend the generation horizon from 128 to 512 steps using the original sampling protocol (§5.1). We retain both checkpoints and temperature-one coupling and follow each selector's early-divergence cohort into later windows. Q2 below reports the paired early-to-late TV contrasts for all three selectors. Figure 7 shows the full branch profiles.
We thank the reviewer for this question. Late branch TV falls on Llama and rises on Qwen. At 512 steps we compare three selectors at matched bytes (50% retention, 72 documents, six strata, K = 16). Mean TV is for trajectories diverging by step 64. Intervals are pointwise 95% paired document-bootstrap intervals (Table 13).
Figure 7 shows the full profiles. Llama's decline also appears in the pre-EOS summaries (Appendix E.1).
Together, the LongBench scores and longer rollouts show that selector rankings can vary with the evaluation objective and that late branch evolution differs by model.