- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper addresses the cost of reading the KV cache during long-context inference and proposes VestigeKV for NoPE-MLA models. The method keeps the complete cache on the GPU, preselects a subset of tokens for attention, and uses a low-dimensional index to retrieve additional archived tokens based on decode queries, aiming to reduce KV reads per decoding step. The authors integrate the method into sglang and evaluate it on Kimi Linear 48B. In the continuous-generation experiment, decoding speed at 512k context reaches 1.45× that of the dense baseline.
Critical strengths
- The paper integrates the method into a serving system and demonstrates faster long-context decoding. The authors integrate the method into sglang, support CUDA-graph execution, and evaluate it at the system level on Kimi Linear 48B. Figure 2 reports 1.45× the dense baseline's decoding speed at 512k context in the continuous-generation experiment. This result demonstrates a practical benefit from reducing KV reads during long-context decoding.
Critical weaknesses
- The claimed guarantees go beyond what the paper actually proves.
-
The paper claims lasting validity of a precomputed ranking, but the proof fixes the query. The abstract and Appendix A.1 describe the ranking as remaining valid throughout subsequent decoding, whereas Proposition 1 considers a fixed query. During generation, queries change, and token attention scores change with them. The proposition therefore does not establish that tokens selected in advance remain important during later decoding.
-
The paper claims that the provisional setting cannot miss retrieval targets, but its error correction is smaller than the theoretical bound. Sections 4.2 and 6.3 state that the default setting before calibration can only over-fetch, not under-recall. Under the default parameters in Equation 4, however, the correction is only approximately 37.8% of the worst-case bound in Lemma 3. Errors exceeding this correction can leave important tokens underestimated and unselected. Falling back to dense attention when too many tokens are retrieved cannot detect such omissions.
-
The recall analysis uses the current query, but the implementation uses the previous query. Section 4.2 explicitly states that the system selects tokens for the current step using the previous step's query. The paper does not establish that these steps require the same tokens, so the theoretical recall guarantee does not cover the deployed decoding procedure. The authors should identify which guarantees have been proved, revise statements that exceed those guarantees, and provide an analysis of the actual configuration and decoding procedure.
- The comparisons and experiments do not adequately establish the additional contribution or practical benefit.
-
The differences from the closest methods are not validated experimentally. Loki (Singhania et al., 2024) already uses a low-dimensional PCA index to estimate scores and select tokens; Quest (Tang et al., 2024) already uses page metadata to read KV selectively. Without comparisons under matched conditions, the paper does not establish the additional benefit of its first-tier selection and calibrated retrieval rule. Excluding these baselines on the grounds of query independence is also unconvincing, because VestigeKV's second-tier retrieval itself depends on queries.
-
The ablations do not demonstrate a distinctive contribution from the proposed first-tier selector. Section 4 reports unchanged two-tier needle-retrieval results at 32× and 128× when the selector is replaced by stride, norm, recency, or random selection; stride also produces similar retrieval telemetry. The authors should explain these results and demonstrate the selector's contribution on tasks that distinguish the alternatives.
-
Quality losses and speed gains are not adequately connected on the same workloads. In Table 6, 64k QA scores decrease from 0.76 to 0.64 on SQuAD and from 0.62 to 0.54 on HotpotQA. In Table 11, LongBench v2 accuracy decreases from 0.313 to 0.300, while wall-clock time changes only from 47.9 to 47.8 minutes, with substantial variation across runs. These results do not demonstrate a clear complete-request speedup. Figure 2's continuous-decoding speedup does not establish the practical benefit obtained in exchange for these quality losses. The authors should report quality, complete-request latency, and memory use together under matched workloads and quality targets.
-
The main text repeatedly explains which comparisons do not apply without clearly establishing the new insight. In the abstract, introduction, and related work, this defensive framing displaces a clear account of the problem, methodological contribution, and supporting evidence. Sections 3–5 mix standard mathematical facts, theoretical claims, and implementation details without a clear progression of the argument. Section 5's command-line options, indexing expressions, and detailed kernel interfaces should move to the appendix. The main text should focus on the key design choices, differences from prior methods, and experiments supporting those choices.
Questions for authors
- Why should tokens selected in advance remain important during later generation? Proposition 1 fixes the query, but queries change as the model generates different tokens, and the information requiring attention can change with them. Which result proves that the precomputed ranking remains valid during subsequent generation? Please state the conditions under which this conclusion holds and revise statements in the abstract and Appendix A.1 that exceed the proof.
- Can the system retrieve important tokens in time for the step that needs them? The implementation in Section 4.2 selects tokens using the previous step's query and uses a gate to decide whether to search the archive. What recall rate does this procedure guarantee, when can it miss important tokens, and what supports the claim of no under-recall before calibration is complete? Does the probability guarantee apply on average across all queries, or also to queries that actually need archived information? Please address the omitted-top-row results in Appendix C, page 15.
- How much do the new design choices improve on existing methods? Please adapt Quest or Loki to the same model and compare accuracy, runtime, and memory use on the same hardware and workloads, under matched quality targets. Also keep the index and first-tier selection unchanged and compare two retrieval rules: retrieving tokens whose scores exceed a calibrated threshold, and retrieving a fixed number of the highest-scoring tokens. This comparison would test whether the benefit comes from the proposed retrieval rule.
- Is there a setting that limits quality loss and also completes the entire request faster? Appendix C already adjusts retrieval settings to improve accuracy, but the overhead on short-answer tasks fails the authors' stated cost criterion. On QA and long-generation workloads, please compare accuracy, total time from input processing to completion of the answer, memory use, and dense-fallback frequency across retrieval settings. Which settings reduce the observed quality losses while retaining a practical speedup? Please include both the dense baseline and the closest existing retrieval method.
- Have the authors read and technically checked the manuscript paragraph by paragraph? If AI-assisted writing was used, did the authors subsequently read and verify the entire manuscript paragraph by paragraph? The guarantees stated in the abstract and introduction do not match the conditions of the proofs and the deployed implementation, and Sections 3–5 do not clearly distinguish established results, the paper's contributions, and implementation details. Please correct these issues and connect each main claim to explicit theoretical or experimental evidence.
Thank you for the detailed response and additional experiments.
The new comparisons and ablation studies help clarify the contributions of the selector and dynamic retrieval. I also appreciate the authors' willingness to acknowledge and correct several theoretical claims.
However, my main concerns remain. The response confirms that Proposition 1 applies to a fixed query, that the provisional clamp does not provide the claimed worst-case recall guarantee, and that the previous-query implementation is not covered by the current-query analysis. These issues affect the theoretical justification of the deployed method.
The new quality–latency experiments also reinforce my concerns about its practical benefits. On MRCR, the default configuration substantially reduces accuracy while increasing latency. Increasing the retrieval margin recovers much of the accuracy, but the resulting configuration remains slower than dense attention. The fixed-memory experiments similarly show no throughput advantage. I recognize the reported speedup for very long continuous decoding, but the practical benefits appear limited to that setting.
The rebuttal has clarified several aspects of the work, but it has not resolved my main concerns about theoretical soundness and the quality–efficiency trade-off. I will therefore maintain my rating of 1 (Clear Rejection).