acceptodds
Under review as a conference paper at ICLR 2027

When is prefix KV reuse compatible with sparse prefill?

Abstract

In sparse prefill with input-dependent attention selection, a prefix cache can depend on tokens outside that prefix. A selector may use later queries to choose the prefix's attention connections, even though the retained attention connections remain causal. We investigate when this dependence affects prefix key/value (KV) reuse in a reference implementation. Across 80 constructed document tasks, switching cache donors changed generated outputs in 11 tasks under sparse attention and 2 under dense attention. In a separate intervention, we tested 4 input pairs with identical prefixes and matched execution shapes. Dynamic routing produced different prefix KV states within each pair. These differences disappeared when the inputs shared attention connections while independently recomputing their own Q/K/V. We derive sufficient conditions for cache reuse to preserve the mathematical result. With matched deterministic execution and cache representation, these conditions also ensure that reuse and recomputation produce identical floating-point representations. On the task set, restricting reuse to complete prefill-call boundaries yielded 72 nonempty cache hits with unchanged reference outputs. Our results provide a diagnostic protocol and a conditional rule for recovering reference outputs during prefix-cache reuse.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language models, Sparse Attention, KV cache reuse

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_qqU6OpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the compatibility of prefix KV cache reuse with adaptive sparse prefill, where attention selection may depend on the input. Although the retained attention connections remain causal, queries from suffix tokens can influence the attention patterns within the shared prefix, potentially resulting in different prefix KV states across requests with identical prefixes.

The authors conduct a series of controlled experiments to investigate this issue. On 80 constructed document tasks, switching cache donors changes the generated outputs in 11/80 cases under sparse attention and 2/80 cases under dense attention. Since these differences may also involve execution-shape effects, the authors further conduct matched-shape interventions, showing that dynamic attention selection can produce different prefix KV states, while sharing the same attention connections eliminates these differences.

The paper also derives sufficient conditions for preserving mathematical and bitwise equivalence during cache substitution and proposes a diagnostic protocol for cache reuse. In their reference implementation, restricting reuse to complete prefill-call boundaries recovers the outputs of the corresponding cold runs, at the cost of additional token computation.

Overall, this work primarily provides an empirical diagnosis and a formal characterization of prefix-cache compatibility in adaptive sparse prefill, rather than introducing a new sparse attention algorithm or an optimized caching system.

Critical strengths

S1. A meaningful observation supported by controlled experiments.

The paper identifies an interesting compatibility issue between adaptive attention selection and prefix KV reuse. In particular, the matched-shape intervention that fixes attention connections while independently recomputing Q/K/V provides useful evidence that suffix-dependent attention selection can affect prefix representations. The distinction between cache-source effects, restart effects, and attention-selection effects is also valuable.

Critical weaknesses

W1. Limited novelty and insufficient motivation for the practical significance of the problem.

While the observation is interesting, the technical novelty appears limited. The proposed sufficient conditions largely formalize the requirement that equivalent dependency graphs and matching execution procedures should produce equivalent results. Similarly, restricting cache reuse to complete prefill-call boundaries seems to be a relatively straightforward conservative strategy rather than a fundamentally new caching method.

Furthermore, the paper does not sufficiently establish the practical significance of the identified compatibility issue. It remains unclear how frequently such incompatibilities occur in realistic serving workloads, how severely they affect downstream performance, and why the proposed compatibility framework offers substantial advantages over existing dependency-aware or conservative caching strategies. Consequently, the motivation and overall contribution of the work are not sufficiently convincing.

W2. Limited generalizability and incomplete empirical validation.

The experiments are primarily conducted using a single model, Qwen2.5-7B-Instruct, and a local adaptation of MInference with uniform attention budgets and masked-dense execution. This setup differs from the released sparse attention implementation and does not evaluate native sparse kernels. The paper also reports substantial discrepancies between its local fp32 selector and the released bfloat16 selector under the main budget configuration.

In addition, the main output-level experiments involve only 80 constructed tasks, while the matched-shape mechanism intervention is limited to four input pairs. The observed donor-swap output differences cannot be directly attributed to suffix-dependent selection, since producer execution shapes also vary. The separate mechanism experiment does not evaluate generated answers.

These limitations make it difficult to assess whether the identified behavior and proposed reuse rule generalize across sparse attention methods, model architectures, execution backends, and realistic workloads. The reported token-computation overhead also does not establish the actual serving performance of the proposed approach.

Questions for authors

Q1. Generalizability.

Could the authors demonstrate that the observed suffix-dependent prefix KV differences and the proposed compatibility rule generalize beyond the current MInference adaptation? In particular, would the same conclusions hold for other adaptive sparse attention methods, the released MInference configuration, different model architectures, and native sparse attention kernels?

**Q2. Causal attribution. **

Could the authors quantify how much of the output-level variation observed in the 80 tasks is actually caused by suffix-dependent attention selection, rather than differences in producer execution shapes or numerical execution? For example, could the shared-connection intervention be extended to end-to-end generation under matched execution conditions?

Q3. Novelty and practical impact.

What is the concrete advantage of the proposed compatibility framework over existing conservative or dependency-aware caching strategies? Could the authors demonstrate that the proposed conditions enable meaningful additional cache reuse or practical serving benefits, especially considering the reported 43.9% increase in consumer-side token computation relative to page-aligned reuse?

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

This paper studies the compatibility of prefix KV caching with adaptive sparse attention. As sparse attention gains adoption, understanding when prefix caches can be safely reused is an important systems question. However, the paper’s main observations and claimed contributions appear largely predictable from the dependency structure of causal and sparse attention. For instance, Section 4.2 shows that different sparse attention masks can produce different KV states for a shared prefix, whereas fixing the same causal masks across inputs preserves those states under matched conditions. The sufficient conditions in Section 5.1 similarly formalize expected consequences of matching computational dependencies and execution. The paper would benefit from clarifying what these results establish beyond these expected properties. The presentation also needs substantial improvement, particularly in defining notation, explaining the experimental setup, and connecting each experiment to the claim it supports.

Critical strengths

The paper studies an interesting and practically relevant topic: prefix caching under sparse attention. This topic is timely, as a growing number of open-source models natively incorporate sparse attention mechanisms.

Critical weaknesses
  1. The main claims and observations are largely predictable from the underlying computational structure.
  2. The presentation is largely unclear, with key definitions and experimental details underspecified.
Questions for authors

Under chunked prefill, when sparse mask selection depends only on the current chunk and preceding cached states, the results and claim in Section 4 and 5 appear to folow directly from causal dependency. What nontrivial insight do these results provide beyond those expected properties?

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

This paper studies when prefix KV caches can be reused under suffix-influenced sparse prefill (e.g. MInference-style sparse prefill).

  1. A selector may use later queries to determine kv cache for earlier positions, making the resulting prefix states depend on the suffix.
  2. Cache reuse may also change call boundaries of chunked-prefill and numerical execution, introducing differences independently of the cache donor.

The authors develop controlled comparisons to separate the effects of cache source from those of restarting computation. They demonstrate the selection-dependent failure mode in a reference implementation, give conditions under which reuse preserves the original computation, and test a conservative strategy that reuses only complete prefill chunks. This strategy reproduces the corresponding outputs obtained by computing the request from scratch, at the cost of recomputing more tokens. The contribution is a diagnostic framework and conditional guidance for combining suffix-influenced sparse prefill with prefix caching.

Critical strengths
  1. The paper clearly explains how suffix-dependent selection can invalidate prefix reuse. Earlier tokens may read only earlier values while the choice of which values to read depends on later queries. This distinction explains how identical prefix tokens can yield different later-layer KV states in the studied methods.

  2. The controls help distinguish different causes of output disagreement. Reusing a request's own cached states provides a useful control for changes introduced by restarting computation. Separately, fixing the selected connections while independently recomputing each input's states helps isolate the role of attention selection. These controls strengthen the mechanism-level evidence.

  3. The paper carefully limits the interpretation of its results. It distinguishes agreement in KV states, logits, generated text, and task correctness; states the assumptions needed for exact reuse; and acknowledges implementation differences and inconclusive quality comparisons. Preserving a reference output is not presented as proof that the output is better.

Critical weaknesses

W1. The practical importance of the chosen problem setting is not convincingly established

My main reservation concerns the value of suffix-influenced, training-free sparse prefill as a deployment target. Open source models such as Qwen3.8, DeepSeek-V4.1Flash, Minimax M3, incorporate sparse attention through training, e.g. NSA[1], MSA[2] and DSA[3]. In this context, I am not convinced that the class of training-free methods targeted here offers a sufficiently compelling quality–efficiency trade-off to make its cache-compatibility limitations an important deployment concern.

Serving previous dense model could motivate this setting, but the paper does not demonstrate a concrete workload where the targeted methods remain attractive after accounting for compatible reuse. Its conservative strategy requires additional recomputation, and the reference implementation cannot establish the resulting latency trade-off. The separate policy comparison also leaves the benefit of query-aware recomputation unresolved. These results do not prove that the target methods lack value, but they leave the central motivation insufficiently supported.

[1] Yuan, Jingyang, et al. "Native sparse attention: Hardware-aligned and natively trainable sparse attention." Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

[2] Lai, Xunhao, et al. "MiniMax Sparse Attention." arXiv preprint arXiv:2606.13392. 2026.

[3] Xu, Anyi, et al. "Deepseek-v4. 1-flash: Pushing the limits of kv cache compression." arXiv preprint arXiv:2609.19969 (2026).

W2. Limited analysis of numerical sensitivity to call boundaries

Section 5.1 and Appendix E locate execution-dependent differences at the layer and token level, but do not identify the operators, kernel choices, or reduction orders responsible. An operator-level analysis with attention connections fixed would help isolate the numerical causes. The remedy preserves complete-call boundaries, leaving unclear whether targeted numerical controls could recover consistency with less recomputation.

Questions for authors
  1. What concrete workload makes suffix-influenced sparse prefill a compelling deployment choice? Within the intended setting, what evidence shows a useful quality–cost advantage after accounting for compatible cache reuse and its additional recomputation? This is the central issue affecting my assessment of significance.

  2. Can you isolate selection dependence in an answer-changing example? With producer shapes matched, does sharing the selected connections remove the answer difference? This would connect the mechanism more directly to the reported task-level consequences.

  3. With attention connections fixed, which operator first introduces numerical differences when call boundaries change? Can you identify the kernel or reduction behavior responsible?

  4. Could targeted numerical controls preserve consistency without requiring complete-call reuse? A focused test and its recomputation or execution cost would clarify the scope for a less restrictive remedy.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.