Thank you for your time and effort in reviewing our work and highlighting the positive attributes of our method. We will address each of your concerns in turn below.

I wonder does it requires task-specific tuning for ultra-long contexts.

We did no task specific tuning for ultra long contexts, except for the reasoning experiment listed below. $\gamma$ is the only tunable parameter in delta attention. We uniformly chose $\gamma = 64$ in our original submission for all experiments except for ablations on $\gamma$.

Correction efficacy diminishes in higher network layers (Appendix Figs. 13-15), which may limit the gains in more complex and reasoning tasks. | the proposed method seems rely on an assumption that nearby tokens have similar representations, this may not be the case in complex or reasoning tasks

Thank you for the insightful comment. To evaluate the method’s effectiveness on reasoning tasks involving long contexts, we conducted additional experiments on RepoQA, a challenging benchmark for repository-level code question answering that requires understanding long-range dependencies (e.g., reasoning about function-class relationships). In this experiment, we reduced $\gamma$ to 16 to improve correction efficacy. Importantly, even at $\gamma = 16$, the compute overhead of the query sparse attention remains at 1/16 that of Flash Attention. Our method demonstrates strong empirical performance on this task, suggesting that it remains effective even in complex reasoning scenarios.

Note that in this task, the threshold setting in the top row is a similarity threshold for score matching (0.8 is default).

Table: RepoQA with Qwen3 235B A22B Reasoning Activated

Thank you again for your time and care in reviewing our work. We have done our best to address your concerns within the allotted time period. We will incorporate any new results into the final version of our work. We remain open to further discussion throughout the end of the discussion period.

Thank you for your time and effort in reviewing our work and highlighting that our method improves upon sparse attention methods with clear and extensive empirical results. We will address each of your concerns in turn below.

There is no statistical significance test. I'd like to encourage the authors report standard test results such as paired permutation tests.

We performed a paired permutation test for the RULER experiments. As QA tasks and Non-QA tasks use different evaluation metric functions for correctness, we have split the test by QA tasks and non QA tasks. We have highlighted all results which surpass the one-sided significance threshold of 0.05. The results match our intuitions about which results are significant in the text (noted by color gradient in the submission). Our method shows significant improvements over Str.LLM at all context lengths and a significant improvement over MInference and HiP at the longest context lengths.

Please note that due to a unexpected server failure, the machine which contained the HiP prediction files from our original submission was lost, therefore we had to re-run them which requires RULER to regenerate the dataset and therefore there are slight deviations in the HiP results from the original submission, but no significant differences. These are the HiP results averaged over all tasks which contributed to the HiP p-values above. We will update them in the final revision of our work.

The writeup could benefit from analysis of more sophisticated interpolation methods.

We tried this experiment with linear interpolation between delta correction values. We find a small but statistically insignificant improvement overall. Additionally, the interpolation poses a theoretical problem in that it violates the causality of the causal attention mask. Interpolation between neighboring delta corrections would introduce influence from the $i + \gamma^{\text{th}}$ row of the attention matrix into the $i^{\text{th}}$ output which is why we decided to repeat the attention rows instead of interpolating in our original work.

Thank you for your time and effort in reviewing our work. We will add these new results into the final version of our work. We sincerely hope we have addressed your concerns and remain open to further discussion throughout the discussion period.

I think It might be possible to design a regression scheme that obeys a causal constraint by only considering left-side values.

Thank you for your suggestion. This is an interesting idea, as we were originally thinking of interpolation as a way of minimizing the gap between tokens. Left side only interpolation would essentially increase the gap between tokens since the closest token on the left side is the last $\gamma^{\text{th}}$ token. As we see it, the upside may be that although we are bringing in "older" information, it would provide a smoother transition between delta corrections rather than a discrete jump in delta correction at every $\gamma^{\text{th}}$ token.

For this, we think that an exponential moving average ($\hat{x}_i = (1 - \beta) x_i + \beta \hat{x}_j$ for $\beta \in [0, 1]$ and $j = i - 1$) over the tokens (after repeating the delta correction in the $\gamma$ window) would provide the proper left-side only interpolation between the delta correction terms. As this was straightforward to try, we performed an experiment on RULER to test out left side only interpolation and achieved the following results.

We used 3 EMA coefficients (0.5, 0.75, 0.95) to test any difference between faster/slower transitions.

[CORRECTED EMA TABLE CAN BE SEEN BELOW]

We found that the left side only interpolation gave a slight increase in performance for the $\beta=0.95$ coefficient, but it did not pass the threshold of statistical significance when comparing to our base model (top row). Surprisingly, $\beta \in \{0.5, 0.75\}$ seems to not have changed any predictions in the model, as the accuracies are identical.

Thank you for your comment and suggesting this experiment, as we did not think about left-side interpolation originally. We will add these new results to the final version of our work. We remain available for further discussion until the end of the discussion period.

Thank you for this suggestion. Upon trying to implement a simple ($\alpha,\beta,\gamma$)-filter we found a bug in our EMA implementation which rendered it almost inert. In fixing it, we have found that Pytorch level iterative operations which scan over the whole sequence (up to 131K in RULER) are too slow to be practically useful (~7000ms per layer). The only way we were able to implement something fast enough for practical use is by writing a kernel-level EMA and $\alpha,\beta,\gamma$-filter which runs in ~50ms per layer (for 131K). We report both results below.

EMA Kernel

We chose an ($\alpha,\beta\gamma$)-filter as it is a simplified, special case of the more general Kalman filter. It's a third-order filter, meaning it estimates position, velocity, and acceleration, and also predicts future values.

($\alpha,\beta,\gamma$)-filter Kernel

For all three types of interpolation (causality breaking linear interpolation, EMA and ($\alpha,\beta,\gamma$)-filters), we have seen that the performance is not improved. However, we agree with the intuition that discrete jumps in the delta correction are a likely place to look for improvement and represent a promising direction for future work. We hope that our discovery of the distribution shift and delta correction will inspire others to experiment with more sophisticated imputation methods, especially those which may learn the imputation function.

Thank you for suggesting these experiments. As the discussion period is coming to a close today, we hope we have fully addressed your comments. We feel these three additional experiments have contributed to our work, and we will add these new results to the final text.

Thank you for your time and care in reviewing our work and noting the positive aspects of our method such as practicality, minimal overhead, easy integration, motivation, and evaluation. We will address you individual concerns in turn below.

2.1 When comparing to Streaming LLM, the authors fail to acknowledge that delta attention requires storing all KV pairs, which increases the storage burden.

We think this is a misunderstanding of our experimental setup. In our experiments, all models are allowed to see the full KV cache during decoding (including Streaming LLM). In this way, Streaming LLM is, in effect, similar to [2, 4, 5] (Cacheblend, APE, Star Attention), where the attention pattern is sparse during the prefill phase and dense during the decoding phase. We would like to highlight that even though Streaming LLM has access to all KV tokens during decode, it still mismatches queries and keys due to the distributional shift which our method is able to fix. We will update Lines 213-215 of our text to make this point clearer.

2.2 For (HiP, MInference) improvements marginal (4-8%), raising questions about cost-effectiveness when applied to already sophisticated approaches. The paper lacks an analysis of why the method shows such stark performance differences across baseline categories

We think this is quite an intuitive pattern. Naive sparse models like Streaming LLM have the most room for improvement because it shows the worst task performance. MInference and HiP are more sophisticated methods of selecting top-k attention which is to say that they have more precise approximation to the full attention matrix and therefore less room for improvement.

We would like to note, however, that even though HiP and MInference are sophisticated methods, they still benefit (~4-8%) from applying our simple delta correction. We maintain that a 4-8% improvement on recent SOTA sparse attention methods is not trivial.

3. Some previous work [1-4] has already worked on fixing the distribution shift for different kinds of sparse attention at test time

We would like to highlight the fact that [3] is not a previous work, as it was only published on arxiv on 6/4/2025 which is nearly a month after the NeurIPS paper deadline of 5/15/2025. Therefore, it would have been impossible for us to know about this work at the time of submission. However, we will discuss any possible connection to the cited references below:

Regarding [1]: The method titled LESS requires training a low rank cache compressor, while ours is a training-free modification. LESS also only experiments with a maximum of 4K context length which is well below the minimum length we tested (Our experiments go up to 384K). This work briefly mentions differences in attention distributions between dense and sparse attention. However they make no mention of the critical insight of our work, namely that a dense decode fails to properly align with the tokens resulting from a sparse prefill due to the distributional shift of the keys that is induced by the sparse prefill.

Regarding [2]: Cacheblend proposes using one dense attention layer to identify important tokens, and then selectively recomputing these tokens in later layers to add missing parts of the sparse attention to cached KV pairs. Cacheblend proposed this as a way to augment and consolidate independently processed chunks of a RAG pipeline. In practice, however, this would effectively be similar to a "smart" sparse prefill method like HiP or MInference which fills in some of the missing tokens in the attention matrix which are outside of the local window context.

We ran the officially published code for Cacheblend to compare with our method (results are posted below)

Regarding [3]: It would have been impossible for us to cite this work, as it was not even on arxiv at the time of submission. However, we note that this work only considers dense prefills and a sparse decoding procedure. Their sparse decoding procedure is similar to what we call “recompute” in Table 4 and Figures 8,9,13-15. We showed that this “recomptue” method is insufficient to mitigate the distributional shift in the outputs.

Regarding [4]: APE is in practice similar to [5] which we cited in our paper. The only difference we notice is that APE proposes temperature scaling and rescaling the attention post-hoc in order to correct any error introduced. However, APE misses the crucial insight of our work, namely that sparse and dense attention result in completely different token distributions which means that there is a problem of query-key matching during decoding. APE only considers query and key geometry as a function of a) position and b) input. They deduce that because they key states of the first few keys (sink tokens) are relatively stable, then the geometry of all other keys are also stable.

Our crucial insight is that different attention operations themselves induce different distributions of query-key geometries and therefore when moving from sparse to dense during decoding (like APE does) there will be a mismatch between queries and keys. This is precisely what our delta correction fixes.

We have run experiments against the officially published codebases of [2,4] on the RULER benchmark and find that our method results in better performance due to the delta correction.

1. lacking theoretical grounding.

In our submission, we were able to show that the difference between the full attention and the sparse attention output is an approximation to the missing attention region (of the full attention matrix). Figure 11 in the appendix shows that in practice, the approximation tends to be lower than the derived bound in Lemma 1. However, the applicability of the delta correction to subsequent rows of the output relies on local similarities of the queries within a given window (If queries are locally similar, then they will result in a similar row of the attention matrix and therefore a similar delta correction). Note that the queries receive the same ROPE positional adjustment as the keys, and therefore

$\langle q_i', q_j' \rangle = \langle R(\theta_i)q_i, R(\theta_j)q_j \rangle = \langle q_i, R(\theta_j-\theta_i)q_j \rangle$

So the queries are biased by ROPE to likely have a higher similarity within a local region. We measure the query similarity from inputs related to both NIAH and QA (natural language) tasks, and observe that across all layers, queries within a given $\gamma$-window show a reliable relationship of cosine similarities.

Also note that we tested our method in conjunction with Llama 4, which uses no ROPE embeddings on the dense attention layers, and we still show an improvement in accuracy on Infinitebench (Table 3 in our submission).

References

[5] Acharya, S., Jia, F., & Ginsburg, B. (2024). Star attention: Efficient llm inference over long sequences. arXiv preprint arXiv:2411.17116.

Thank you for your time and effort in reviewing our work. We sincerely hope we have addressed the concerns you raised. We plan to add these additional results to the final version of our paper. We are available to answer any remaining concerns throughout the discussion period.

For comparison with LESS, I agree that the work focuses on sparse encoding and dense decoding, whereas LESS focuses on correcting sparse encoding and decoding with a low-rank cache. However, since there are not many methods available for correcting the difference between sparse and dense attention, I think a comparison is not necessary; however, it is reasonable to mention this in the related work.

We will mention this work and the other mentioned references [1-4] in the final version of our related work.

Moreover, I was wondering why we consider sparse encoding + dense decoding instead of sparse encoding + decoding.

We agree that sparse decoding is an interesting next step. However the main purpose of our work was in identifying the cause of failure in the sparse prefill/dense decode setting and proposing a solution which is effective in mitigating the problem.

This scenario seems to be a little narrow, which only designed for long-context retrieval tasks.

Our setup is not only designed for long context retrieval, as we also present results on InfiniteBench (Table 3) which includes Question Answering, Multiple Choice Questions, and Summarization, all of which are NLP-based and not retrieval tasks.

—

We thank you again for your review and responses, we hope this added evidence has demonstrated the strength and novelty of our analysis of the problem and our proposed solution. We remain open to further discussion until the end of the discussion period.

Thank you for your prompt response to our rebuttal, we would like to provide more evidence of the novelty and significance of our contribution.

Therefore, I will define this as a weak baseline, as we all know it should have a huge problem in retrieval-related tasks. It is not reasonable to include this baseline when computing averaging improvements. We can still compare it separately.

Streaming LLM with a dense decode has the nearly the same attention pattern as Star Attention and APE, therefore, we do not see why it should be considered a weak baseline. Furthermore, we disagree that “we all know it should have a problem in retrieval based tasks.” This was the precise question which motivated our work.

To provide further evidence that it is not obvious, we direct your attention to Figure 4 and the conclusion of the Star Attention paper.

Star Attention (Figure 4 Caption): All runs use a block and anchor block size set to one-quarter of the total sequence length

Star Attention (Conclusion): The role and optimal size of anchor blocks relative to context blocks require further exploration. Additionally, while Star Attention performs effectively with block sizes set to one-quarter of the sequence length, accuracy degrades when using smaller blocks on longer sequences. Future work will focus on refining the anchor block mechanism.

If the reason for requiring 1/4 of the context length were obvious the authors would not have suggested that the block sizing effect on accuracy needs further investigation.

In fact, we started our investigation with the following question:

If a sliding window (or block chunk) is large enough to fit relevant chunks of context, and all chunks of context are conditionally independent, then why should there be a problem retrieving the relevant context later when it can see all of the keys during decoding?

We do not think it is sufficient to state this is obvious without precisely identifying why there should be any problem retrieving context which was fully contained in the sliding window. Our work precisely describes and identifies the mechanism which causes this to happen, and offers an effective solution which can be applied. Both the description of the cause and the solution have not been properly identified in prior work.

I think another possible experiment is to show that Star Attention/APE can be further improved with the delta rule. It will improve the quality of the paper.

Please see Figure 2 in the Star Attention paper. This is almost identical to the attention pattern of Streaming LLM with a dense decode. This is why we chose to use Streaming LLM with dense decode as a baseline. To further illustrate that this is the case, we ran an experiment with a block mask identical to that of Star Attention with a block size of 2K and achieved the following results.

This result provides further evidence towards the fact that our delta correction can improve upon the block attention pattern of Star Attention and that Streaming LLM with dense decode should not be considered a weak baseline as it outperforms the block attention mask of Star Attention due to the added information which is missing in the block structure of the Star Attention mask.

Continued...

Thank you for your continued discussion and evaluation of our comments. We agree that Star Attention and APE focus on contributions related to parallelization over hosts, and RAG precomputation which are orthogonal to our work which focuses on the distributional shift which can result from such attention patterns when switching to decoding.

We will highlight this distinction when mentioning these methods in our final paper, and we hope that our contribution will inspire future works to devise methods of mitigating the distributional shift in distributed or precomputed chunked prefills.

Thank you for your time and effort in reviewing our work.

Thank you for your time in reviewing our work and noting that our method is novel and interesting, effective, and easy to follow. We will address each concern you raise in turn below.

1. A key assumption is that delta values for neighboring queries are similar … not empirically validated. …

If we understand the concern correctly, we have provided this experiment in Figure 6b. In this case we study the average cosine similarity between $(A^\Delta V)_i$ and $(A^\Delta V)_j$ for $j \in [i+1, \dots, i+\gamma]$ (notation changed from paper due to math rendering issue in OpenReview). This means that we computed the full attention output minus the sparse attention output and evaluated the average cosine similarity for different gamma windows. In Figure 6b we find a generally high cosine similarity for all delta windows, although it does show a tendency to decrease for larger windows. This high cosine similarity implies that the delta may be re-used over multiple output rows.

As a follow up experiment, we also evaluate the similarity of queries within a given gamma window, as similar queries transitively implies that rows of the attention matrix will have a similar distribution of attention scores, and therefore may be re-used in neighboring rows. We find the following correlations which tracks closely to that of Figure 6B.

2.1 Interpolation techniques might yield more accurate approximations.

We tried this experiment by linearly interpolating between neighboring rows of delta terms instead of just plainly repeating them. We found that performance was largely unchanged by this fact. Additionally, linearly interpolating between delta terms introduces a theoretical concern of violating causality, as after the interpolation output token $i + \gamma$ has influenced the prediction of output token $i$, which is why we decided on repeating the delta correction in our original submission.

The p-values are the result of a one sided paired permutation test (as suggested by reviewer 1VjR) to show whether there is a significant improvement added by the delta interpolation (p<0.05 is considered significant and therefore, there is no significant improvement seen by interpolation)

2.2 It's unclear how performance scales with the parameter (i.e., the fraction of queries used for full attention). At what value does the method match the performance of full attention?

In our submission we have include an ablation in Figure 6a which shows how performance scales as a function of gamma.

Q.1 To what extent is the matrix query-dependent versus being a property of the model itself?

If we understand the question correctly, you are asking if the direction of the delta correction is dependent on the query, or if the direction may be a fixed position learned within the model itself. To test this, we performed a variant of the experiment we did in Figure 6B. We took an input from RULER NIAH MultiKey3 and also an input from the QA2 task which is a more NLP oriented. We calculated the delta correction and averaged the cosine similarity within 6 gamma windows over all layers of Llama3.1-8b-instruct. The top row shows NIAH/QA2 cosine similarity average, where the cosine similarity was calculated within the gamma window of the current input (Self Avg. Same as Figure 6B but including a second task in the average). We also calculated the cosine similarity between the delta correction of the two tasks $\text{cos}(NIAH, QA)$ (Cross Avg).

If the delta correction were a stable artifact of the model itself, we would expect to see a similar relationship in cosine similarity, i.e. it should start high for a small gamma window and slowly decrease as the gamma window increases). However, we find that between tasks, the cosine similarity between delta corrections remains low and shows no relationship with an increasing gamma window. Therefore, we can conclude that the delta correction is query/input dependent and not a fixed artifact of the model.

Thank you for suggesting this experiment, we will add it to the final version of our work.

Thank you for your time and effort in evaluating our work. We will incorporate these new results into the final version of our work. We have done our best to respond to your concerns within the rebuttal period and remain open to further discussion throughout the discussion period.

Thank you for your time and effort in reviewing our work, if there are any remaining concerns we remain open to further discussions until the very end of the discussion period.