acceptodds
Under review as a conference paper at ICLR 2027

VestigeKV: Query-Independent Sparse Attention with Certified Recall for NoPE-MLA Caches

Abstract

A long-lived KV cache must be compressed before the queries that will read it exist. Methods ranking by observed attention are built for the opposite order and are not compared against here: with no query, the statistic they rank by is undefined rather than weak. VestigeKV decides before any query exists and makes the decision non-destructive. Reading 11% of each row, a statistic the cache already carries, it partitions the cache into an attended tier and a GPU-resident archive no row ever leaves, reachable each step by a certified, query-adaptive trigger. The certificate is what carries the result: swapping the first tier's statistic for a stride, a norm, a recency window or a random draw leaves every cell of the retrieval table unchanged, so the recovery is the archive's and not the selector's, and we report that rather than claim the selector. Nothing is trained and nothing is stored below 16 bits. On Kimi Linear 48B the two tiers recover every needle trial at 32x and 128x (1.00, 1.00) and 32/32 on the served path at 128k; delete tier 2 and the algorithm is incomplete. Both tiers stay on the GPU and the cache grows 1.14x, so the win is bandwidth, not memory: the per-step scan reads  26% of the bytes dense attention would, and on a two-GPU sglang deployment the crossover sits at  24k context, reaching 1.45x at 512k. Two conditions bound the claim, and both are measured. It holds under NoPE, where the score is position-free so a ranking taken at prefill is permanent: with rotation the only variable it inflates the winner set a fixed cone can select by 1.1-2.1x (Prop. 1), and exact merging is provably impossible there. And it holds on natural text, where the selector's overlap with an oracle sits at 3.3x the random floor against 1.6x on a synthetic haystack; the overflow fallback owns that minority regime. All thresholds were frozen before their data; 20 archived verdicts and 8 closed routes accompany the paper.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV cache compression, sparse attention, long-context inference, LLM serving, NoPE, Multi-head Latent Attention, query-independent selection, conformal calibration

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_euo2OpenReview ↗
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
  1. 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
  1. 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.


  1. 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
  1. 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.

  1. 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.

  1. 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.

  1. 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.

  1. 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.
1 comment

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).

Reviewer_R2vxOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper tackles the kv cache compression problem, dedicatedly for the NoPE-MLA models. The method splits the cache into an attended tier and an archive tier, both kept on the GPU.

Critical strengths

There is no clear critical strengths. There might be some novelties in the approach design, but is not directly presented and it is extremely hard to “guess and mine” them out of the current writeup.

Critical weaknesses

W1. The structure of the paper shows that the paper is LLM generated. Without making my recommendations based on this judgement, this paper requires significant polishing to reach the level of a publishable paper at ICLR. There is no motivation, intuitions or supporting evidences behind the approach at all.

W2. The experiments are also very limited, and do not establish a clear advantage of the proposed approach.

Questions for authors

N/A

1 comment

I appreciate the authors rebuttal. However, it is still very hard for me to follow and understand the main intuitions behind the approach design, for example, what motivates there should be two tiers, why every tier is strictly necessary, and how this design differs fundamentally from the baselines that solve the same problem. I notice there are some baselines in the appendix, and I suggest the authors to include them in the main experiments section. Given the current status of the paper, I would like maintain my scores.

Reviewer_LxGCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes VestigeKV to reduce KV-cache read traffic during long-context decoding in NoPE-MLA models. It uses high-pass residuals of cache vectors to partition the cache into an attended tier and an archive, then dynamically retrieves archived rows using a low-rank index and calibrated scores. The complete KV cache remains on the GPU, so the primary objective is to reduce memory bandwidth consumption rather than memory capacity. The authors implement an sglang backend for Kimi Linear 48B and evaluate retrieval and generation quality, as well as performance across context lengths and concurrency levels.

Critical strengths
  1. The paper addresses a meaningful practical problem. Long-context decoding repeatedly reads a large KV cache, while permanently deleting cached entries can cause irreversible information loss. Reducing read traffic while retaining access to historical information is a worthwhile research direction.
  2. The solution is interesting and includes a working system implementation. Combining a preselected attended tier with a complete, dynamically retrievable archive is an appealing design. The authors integrate the method into sglang and demonstrate performance gains at long contexts. They also report quality degradation, additional cache memory usage, and fallback behavior, which help clarify the method’s operating range.
Critical weaknesses
  1. The accuracy degradation is substantial and raises concerns about the reliability of the current retrieval mechanism on important tasks.

    In Table 2, RULER accuracy drops from 92.2% to 86.0% on the Base checkpoint and from 94.2% to 92.0% on the Instruct checkpoint. These averages also hide larger regressions on individual tasks. In Table 6, the Instruct checkpoint’s accuracy on multi-key UUID retrieval at 64k drops from 100% to 76%, while accuracy on the SQuAD QA task at 64k drops from 76% to 64%. These results show that the problem is not limited to a particular synthetic input format; question answering over real passages is also affected.

    I do not expect an approximate method to be entirely lossless, but these drops raise substantial concerns about its practical usefulness. Retaining the complete KV cache only ensures that the information remains available; it does not ensure that the right information will be retrieved when needed. The analysis of a particular multi-key retrieval task in Appendix C also shows that the highest-scoring row can be omitted at critical steps. This is therefore more than a benchmark-selection issue: it exposes limitations of the current index and retrieval rules. The conditional guarantees behind “certified recall” do not adequately resolve concerns about final answer quality.

    The paper also lacks a sufficiently thorough analysis of the quality–performance trade-off. The strongest speedups and the main accuracy results come from different evaluations, so they do not directly establish whether the accuracy loss is justified by the performance gains. The margin sweep in the appendix improves accuracy but increases retrieval and dense-fallback costs. The paper needs to report accuracy and latency across configurations on the same tasks and demonstrate competitive performance gains while keeping quality degradation small.

  2. The connection between the motivation and the core design is not sufficiently established, and the ablations and baseline comparisons do not yet demonstrate why the design is necessary.

    The paper is primarily motivated by the need to decide how to compress a cache before future queries are available. However, the complete system retains all KV entries, increases the cache footprint by approximately 14%, and still uses decoding queries to determine which archived rows to read. It also collects decoding queries for calibration. Combining an advance partition with dynamic retrieval can be reasonable, but the paper does not sufficiently establish what independent advantage this partition provides over directly selecting entries to read based on the query.

    The paper does include component-removal and selector-replacement experiments, but these results do not sufficiently support the proposed selection strategy. Section 4 shows that several simple selectors achieve identical needle-recovery results when the retrieval tier is enabled, and uniform sampling produces calibration statistics close to those of the proposed selector. More controlled comparisons on the final deployed implementation, at matched task quality or actual read budgets, are needed to separate the contributions of the selector, retrieval tier, and fallback mechanism. Differences between the harness used for some ablations and the deployed system further limit how directly those findings apply to the complete system.

    The baseline comparisons also need strengthening. Since the primary objective is to reduce read traffic, excluding query-aware sparse-reading methods solely because their decisions occur at a different time is not sufficiently justified. In the comparison with KVzip, matching the initial retained fraction does not match total memory usage or actual read traffic, because VestigeKV retains the complete archive and performs dynamic retrieval. The existing comparisons therefore do not establish its advantage under comparable resource or quality constraints.

Questions for authors
  1. Can the accuracy degradation be substantially reduced while preserving the performance gains? Please vary the recall target, index rank, or retrieval margin on the same multi-key retrieval and real-document QA tasks, and jointly report accuracy, request latency, retrieved-row counts, and dense-fallback rates.
  2. What primarily causes retrieval failures at critical answer steps? Can the authors separate the effects of low-rank index error, calibration distribution shifts, and using the previous step’s query? Which events does the current “certified recall” guarantee protect, and which important failures cannot be detected by the fallback mechanism?
  3. Are the proposed selector and advance partition necessary? On the final deployed implementation, can uniform sampling with the same retrieval mechanism achieve similar quality and speed? Compared with query-aware sparse-reading methods, how much advantage remains after matching task quality or resource budgets?
Reviewer_FQZdOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

VestigeKV is a two-tier KV cache for NoPE-MLA models. Before decoding starts, a subset of tokens is selected and kept resident; everything else goes into a GPU-side archive that the decoder can query as it generates. The authors build this in SGLang and evaluate mostly on Kimi Linear 48B. At 512k they report a 1.45x end-to-end speedup, with roughly 14% more KV memory spent on the archive. The systems work looks solid to me. What I cannot yet judge is how reliable the retrieval is, and what that does to output quality.

Critical strengths

The problem being attacked is real. Deciding which cache entries to keep without knowing what the model will ask next is genuinely hard, and splitting the cache into a small resident set plus a searchable archive is a reasonable way to sidestep the hard part rather than pretend it away. I also value that the numbers come from SGLang under actual serving load instead of from a synthetic needle test, and that the paper is candid about scan overhead and the memory bill the archive brings. Systems papers routinely leave that accounting out. The ablation tables are not curated to flatter the method: the selector comparison and the degraded RULER numbers are all there. That makes the evaluation easier for me to trust, even where the numbers are bad news.

Critical weaknesses

(1) The recall argument does not survive contact with the decoder, at least not in the form presented. From what I can reconstruct, Section 4.2 retrieves with the previous decoding step's query rather than the current one. The paper admits this, then goes on reporting recall figures as though the two were interchangeable. They are not, and I found no measurement of what that one-step lag actually costs. The conformal part is where I have the bigger problem: it leans on exchangeability, and successive queries from an autoregressive decoder are close to the opposite of exchangeable, since each is conditioned on the token the model just produced. As written, the sketch bound, the conformal statement and the empirical recall curve are three separate claims sharing one section, and I cannot tell which of them the 512k results are meant to be evidence for.

(2) The RULER losses deserve more attention than they get. Both checkpoints degrade, and multi-key retrieval and document QA fall hard in Table 6. Appendix C then reports that for one multi-key setting the most relevant entry is missing from the retrieved set in 20% of samples. That is retrieval breaking, not compression shaving a point or two off accuracy. If a fifth of the samples never see the passage they need, aggregate accuracy tells me very little about behaviour on tasks that require combining several facts, and I would want that breakdown on a multi-hop task before accepting the quality story.

(3) I cannot isolate what the selector contributes. Uniform, norm-based, recency and random selection all land in roughly the same place on several needle tests, which already suggests the first stage is not doing much. And because the archive is rescanned at every decoding step, the scan may dominate cost no matter what the selector picks. Reporting retrieval quality, admission rate, fallback frequency and latency side by side under one budget would settle it; without that, the spectral residual idea remains a proposal rather than a demonstrated gain.

(4) All results are Kimi Linear 48B on two GPUs. The discussion suggests Gated-MLA would behave the same way, but nothing is shown, and I would want a second NoPE-MLA checkpoint before assuming the selection signal transfers.

(5) The speedup is measured against configurations that happen to fit on the hardware, which is not the comparison a serving team would run. The archive consumes memory that would otherwise hold concurrent requests, so throughput at a fixed memory budget is the number that decides whether this is deployable. Related: on short generations the index build may cost more than the cache savings return, and that figure does not appear anywhere.

Questions for authors

(1) Which recall statements in Section 4 still hold once retrieval uses the previous step's query? I would want the measured loss from that lag, not an acknowledgment of it. And on what basis is exchangeability claimed for queries the decoder generates itself?

(2) For the RULER failures, how often is the needed entry simply absent from the retrieved set, and how do those misses correlate with wrong answers? Multi-key retrieval and document QA would be the places to start.

(3) Holding memory and latency fixed, is there any configuration where spectral residual clearly beats uniform or random?

(4) Any results on a second NoPE-MLA model? And is there an argument for the selector transferring to Gated-MLA, or is that just an expectation?

(5) What happens to throughput when the archive and index are counted inside a fixed GPU budget? And what does index construction cost on short generations?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.