acceptodds
Withdrawn from ICLR 2027

ReadSpan: Anticipating Where Decoding Reads for KV Cache Eviction

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Key-value (KV) cache eviction reduces the memory of long-context inference by keeping only the input positions that an observation window at the end of the input attends to. This snapshot misses a recurring pattern of grounded responses: decoding jumps from the cue that the window attends to onto a nearby entry point and then reads forward through a span that the window barely sees and eviction removes first. We propose \method, a training-free method that anticipates this span from the first output token, which prefill predicts before any eviction. On top of a head-matched base selection, \method routes the window scores to the positions holding the first output token, extends them forward, and shifts each head's budget toward the span only to the extent that the base selection misses it, without any extra forward pass. On LongBench and RULER with Llama-3.1-8B-Instruct and Qwen3-4B, \method outperforms six training-free baselines on the combined score in all four model–budget settings; at 5% KV cache, it raises the RULER average over the strongest baseline by 3.4 and 7.2 points.\newline Code and data: https://anonymous.4open.science/r/ReadSpan-5443anonymous.4open.science/r/ReadSpan-5443.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV cache compression, KV cache eviction, long-context inference, efficient inference, large language models, training-free

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_sDEmOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper focuses on KV cache eviction that occurs once after the prefill phase (as in SnapKV). It argues that window-based scores can identify the "cue" the question refers to but fail to capture the following span, which the model actually copies during decoding. ReadSpan addresses this issue in two stages: first, a head-matched base selector (HM) which evaluates positions based on the attention multiplied by the projected-value norm and divides the budget among the different layers and heads; and second, a refinement process that locates the positions in the input which match the first output token, transfers the window scores to those positions, extends forward from them, and then combines this with the base scores using a weight that takes coverage into account.

Critical strengths

1-The observation known as 'jump-and-read' is simple and intuitive, and it seems interesting to use the first output token as a reference point. ​ 2-The motivation for the coverage-aware weight is good, and it has a short and correct proof.

Critical weaknesses

1- Looking at Table 3, the main point turns out to be of little significance. Extension from all positions (with no first-token anchoring) scores 88.83 compared to 89.06 for full ReadSpan, which means that the anchoring only contributes about 0.2 points. The removal of routing or setting beta equal to 1 causes changes in the results of between 0.01 and 0.40 points. Since there are 50 inputs per RULER task (one input being worth 2 points on a task), these differences are just noise. Most of the improvement over the baseline is due to the forward extension and to HM itself (HM on its own is already better than ReST-KV at 5% on Llama).

2-RocketKV (ICML25) already addresses the problem in question, which the paper doesn’t compare it with this work. The main point is that the window at the end of the prefill phase cannot know what the decoding process will read. RocketKV tackles this issue by maintaining a type of eviction similar to that used in SnapKV after the prefill phase, and then, at each decoding step, it chooses the top-k tokens using the actual decode query rather than making a guess based on a single token. ReadSpan should carry out a comparison with RocketKV regarding both the matched KV memory and the matched per-step traffic, and it should explain why it is preferable to make a one-token guess at prefill time rather than using the real decode queries. Moreover, HM is mainly a combination of existing techniques, some of which go unmentioned. The concept of a layer budget seems just the layer-preference rule from CAKE (ICLR 2025), which is not cited. The approach of taking the single top-k from the concatenated head scores is AdaKV. Head-level budget allocation was also investigated by HeadKV-R2 (ICLR 2025), even though it is not cited or compared. Value-aware scoring comes from CriticalKV; the only new element is the matching of attention and value on a per-query head basis within the GQA group, and there is no ablation study that isolates this feature.

3-There is no integration with a real inference engine such as vLLM or SGLang. The per-head or even per-layer variable-length arrangements are typically not well suited to vLLM-style serving and the practice of evicting after the prefill phase causes prefix caching to break down for use in multi-turn conversations. It is not easy to achieve a noticeable improvement over using the full key and value (kv) stores when incorporating such methods into vLLM-based designs. In vLLM, SGLang and TensorRT-LLM the paged cache holds all the heads of a token in the same block and the attention kernel assumes a single sequence length per request. Based Table 3, head-wise allocation is worth about 0.7 points on average, and thus the engineering effort involved might not be justified.

4- There is no TTFT, TBT, and no measured GPU memory. The statement that decoding reads a cache 10-20X smaller is an assumption from the budget, not a measurement, and it ignores the gather cost of rebuilding a compacted cache per head.

5- The performance gains are not significant. On LongBench, the method leads by only 1.00/0.63 at 5% budget and 0.27/0.21 at 10%, based on a single greedy evaluation over 100 inputs per task. Furthermore, the advantage over the top baseline stems almost entirely from two tasks, CWE and a single UUID task (K3), with S3 providing an advantage only against weaker baselines. This outcome conflicts with Section 4.3 assertion that aggregation tasks favor different baselines, given that ReadSpan substantially outperforms others on CWE. Also, although the authors acknowledge using both benchmarks during development to tune and fix hyperparameters (D, R, gamma, and W), they provide no sensitivity analysis.

Questions for authors

Please check the weakness section. Authors are expected to address the weaknesses. The authors also need to show how the method works for the multi-turn scenario datasets like SCBench.

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

ReadSpan performs one-time KV-cache eviction after prefill. It uses the first generated token, without an additional model forward pass, to anticipate input spans that may be copied during decoding. A forward extension of entry-anchor scores is combined with a head-matched base scorer while preserving each head's original budget. The method is evaluated on LongBench and RULER with Llama-3.1-8B and Qwen3-4B, showing small average gains, especially on copying tasks, along with nontrivial selection overhead.

Critical strengths
  1. The targeted failure mode is well chosen. Observation-window attention can miss spans that decoding later copies, and using the already-available first generated token is a lightweight way to anticipate those spans. Preserving head budgets and falling back to the base scorer when no token match exists are sensible safeguards.
  2. The evaluation covers modern scorers and useful ablations. The paper compares against six compressed-cache baselines, includes HM/refinement/all-position-forward controls, tests two models and both LongBench and RULER, and uses shared hyperparameters across settings. The ablation design makes it possible to inspect where the proposed routing does and does not help.
Critical weaknesses
  1. The incremental contribution over simpler variants is small and not independently validated. In Table 3, full ReadSpan averages 89.06 versus 88.83 for forward extension from all positions and 88.85 for entry-anchored β=1; the HM-only average is 87.69. Gains are concentrated in long-UUID copying, while Appendix B.3 states that both benchmarks were used during development and reports no uncertainty estimates. Proposition 1 bounds score correction but does not establish task-accuracy improvement.
  2. The practical memory–latency case is incomplete. Budgets are nominal, dense prefill is still retained until eviction, and generated tokens are appended afterward. Total selection overhead is 9–40% of prefill (0.32–1.85 s), but the paper does not report a complete end-to-end frontier covering physical peak memory, baseline selection costs, decode time, and output-length break-even. ChunkKV and Lookahead Q-Cache are cited but absent from the main matched-budget experiments.
Questions for authors
  1. Please expand the related-work discussion to include EAKV (https://openreview.net/forum?id=wyT47sv2o8), MadaKV (https://arxiv.org/abs/2506.15724), FastGen (https://openreview.net/forum?id=uNrFpDPMyo), MiKV (https://arxiv.org/abs/2402.18096), and MEDA (https://arxiv.org/abs/2502.17599). FastGen and MiKV are directly relevant text-cache allocation/mixed-precision neighbors; EAKV, MadaKV, and MEDA should be distinguished as adaptive-allocation context. Please clarify ReadSpan’s incremental contribution beyond their existing mechanisms.
  2. Can you evaluate on a genuinely held-out benchmark or configuration and provide confidence intervals? Please stratify results by first-token match frequency, absent/common/repeated matches, extractive versus non-extractive answers, and task type, so the benefit of token-identity routing can be separated from UUID-specific gains.
  3. How sensitive are the results to D=64, R=32, and γ=0.95, and how were these values selected? Please add statistical comparisons among HM, all-position forward extension, entry-anchored β=1, and full ReadSpan, including cases where irrelevant common-token matches could redirect budget.
  4. Can you report actual physical bytes and peak prefill/decode memory, plus end-to-end latency including every baseline's selection cost? A sweep over output lengths would clarify when the 9–40% prefill overhead pays off. Matched-budget comparisons with the already-cited ChunkKV and Lookahead Q-Cache would also strengthen the empirical case.
Reviewer_cDt4OpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Despite an anonymous repo, it inlcudes an non-anonymous github link that could relate to personal information. The submission should be desk rejected.

Critical strengths

NA

Critical weaknesses

NA

Questions for authors

NA

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

Related papers

Discussion (0)

Sign in to comment.