Delta Attention: Fast and Accurate Sparse Attention Inference by Delta Correction
Authors: Jeffrey Willette
Heejun Lee
Sung Ju Hwang
Venue: NeurIPS 2025 poster ()
Keywords: sparse attention
transformer
LLM
efficiency
Primary area: deep_learning
TL;DR: We identify a problem with sparse attention inference and propose a simple solution. Our solution increases performance by a large margin while maintaining low latency.

Abstract: The attention mechanism of a transformer has a quadratic complexity, leading to high inference costs and latency for long sequences. However, attention matrices are mostly sparse, which implies that many entries may be omitted from computation for efficient inference. Sparse attention inference methods aim to reduce this computational burden; however, they also come with a troublesome performance degradation. We discover that one reason for this degradation is that the sparse calculation induces a distributional shift in the attention outputs. The distributional shift causes decoding-time queries to fail to align well with the appropriate keys from the prefill stage, leading to a drop in performance. We propose a simple, novel, and effective procedure for correcting this distributional shift, bringing the distribution of sparse attention outputs closer to that of quadratic attention. Our method can be applied on top of any sparse attention method, and results in an average 36\%pt performance increase, recovering 88\% of quadratic attention accuracy on the 131K RULER benchmark when applied on top of sliding window attention with sink tokens while only adding a small overhead. Our method can maintain approximately 98.5\% sparsity over full quadratic attention, making our model 32 times faster than Flash Attention 2 when processing 1M token prefills.

A Attention: Fast and Accurate Sparse Attention Inference by Delta Correction
Jeffrey Willette', Heejun Lee', Sung Ju Hwang!
KAIST DeepAuto.aii (jwillette, ainl, sjhwaag822 ac.
Abstract
The attention mechanism of a transformer has a quadratic complexity, leading to high inference costs and latency for long sequences. However, attention matrices are mostly sparse, which implies that many entries may be omitted from computa- tion for efficient inference. Sparse attention inference methods aim to reduce this computational burden; however, they also come with a troublesome performance degradation. We discover that reason for this degradation is that the sparse calculation induces a distributional shift in the attention outputs. The distributional shift causes decoding-tinee queries fail to align well with the appropriate keys from the prefill stage, leading to a drop in performance. We propose a simple, novel, and effective procedure for correcting this distributional shift, bringing the distribution of sparse attention outputs closer to that of quadratic attention. Our method can applied on top of any sparse attention method, and results in an average 36%pt performance increase, recovering 88% of quadratic attention accuracy on the 131K RULER benchmark when applied on top of sliding window attention with sink tokens while only adding small overhead. Our method can maintain approximately 98.5% sparsity over full quadratic attention, making our model 32 times faster than Flash Attention when processing 1M token prefills.
1
Introduction
The main operation that powers modern transformers, self-attention [Vaswani al., 2017], creates causal pairwise comparisons for every item in sequence. While powerful and expressive, this operation comes with a quadratic complexity, leading to the need for large amounts of computation during inference on long sequences. This increases direct costs for hardware and electricity well as negative externalities such as CO2 emissions. Training- free sparse attention modifications aim to lower the quadratic complexity at inference time, but come with unwanted side effects such as accuracy degradation due to the sparsification the attention matrix.
Flach Alsetiice
Strvansng LLM
Stremming LIM +
HNP
NNNS HIP
Mildronee
Minftrnnes
100
spi (0000)
98
Aceuacy (%)
78
112
50
35
28
25
0
NIAH 1-3
NIAH
MK
MK
QA
2
Figure 1: RULER 131K Subsets. At long context lengths, sparse attention can degrade performance by a large margin. Our simple A correction improves performance and only requires an additional 1.5% of the full quadratic attention computation.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Recent works on sparse attention have found that a sparse sliding window can be added at inference time without a total loss of model stability. This is accomplished by saving a small number of initial tokens, and applying sliding window on all subsequent tokens (Streaming LLM [Xiao et al., 2023]). Subsequent works such as Star Attention [Acharya et al., 2024] have proposed a similar sparse prefill strategy with fully dense decoding procedure to generate new tokens. This strategy has the positive attribute sparse prefill while still performing attention with all tokens during generation. This should allow the model to accurately recall context buried deep within the prompt. However, we find that this is not the case in practice. For example, there is a challenging subset of the RULER [Hsieh et al., 2024] benchmark titled MultiKey-3, which consists entirely of unique UUID keys and values, and the large language model (LLM) must be able to recall the proper value for particular key in order to get correct answer. In this setting, a sliding window of 2048 tokens provides more than adequate room for encoding individual key and value pairs together within the window. One would then expect that dense decode procedure would be able to retrieve the proper UUID given user query. However, we find that this is not the case and the dense decode achieves a surprisingly low accuracy of 0% opposed 62% when using quadratic attention.
We find this drop in accuracy arises from a distributional shift in the output tokens of each layer due to the sparse prefill. This distributional shift causes problems with the query-key dot products in long contexts and therefore results in extreme drop in performance as the queries no longer align with the expected keys. We study this problem and found a surprisingly simple fix which we dub A Attention that improves the accu- racy of sliding window attention from 0% to 44% (Figure 1, NIAH MK3) on this challenging subset while maintaining more than 1I-fold speedup over plain Flash Attention 2 [Dao, 2023] for processing 131K context lengths (Figure 2). Through evaluations on perplexity, natural language understanding, and synthetic tasks, we demonstrate that our method consistently
BUILER BaK Aug. Acetrcy
90 8
Fleeh Actertion
LLM
Ste, LLM A
HPP
33-
HiP
Labrey (maa 13IK
Figure 2: Comparing RULER 131K prefill attention latency and accu- racy for sparse attention methods. results in better performance while maintaining the low latency of the sparse prefill.
Our contributions are as follows:
We identify a distributional shift in tokens when applying an inference-time sparse attention method to pretrained transformers, which interferes with query-key alignment on long contexts and leads to drop in performance.
We introduce Delta (A) Attention, a sparse post-processing correction that realigns sparse outputs with full quadratic attention.
Our method adds negligible latency overhead compared to plain sparse attention, while drastically increasing performance over purely sparse methods.
Our method is designed to work in the attention output space, so it can be seamlessly integrated with existing sparse attention kernels and inference pipelines without major modification.
2 Background & Related Work
The self attention mechanism of a transformer takes an input sequence X E Nxd of individual tokens x; E RR for i (L..N). After applying linear projections Wo. WK. Wy E gaxd dd to the input X to achieve the respective Q, V matrices, positional encodings such as [Su et al., 2024] are applied to Q and K. With representing the softmax operation over the last dimension, the self-attention operation for an arbitrary layer in a transformer is the following,
QK
V = (
AV = a Vd
v
XWv
Vd
We omit the output projections, attention heads, and post-attention multilayer perceptrons (MLPs). For deeper discussion of these topics in transformers, please see [Vaswani et al., 2017]. The most expensive operation in Equation (1) that arises from the multiplication inside a() which results in the implicit construction of an attention matrix A E NxN which is computationally expensive for

---

large N. Due to the causality condition of language, token x; may only influence another token x; where the index i S j. In practice, this means that only the lower triangle of A is computed.
After traversing through the layers of the network, the next token in the sequence XN+1 is generated (predicted) and added to the input sequence to generate the next token and so until the sequence terminates. In this generation phase, each iteration may use the previously computed tokens, which are stored within a cache at each layer, so that we may avoid re-caleulating the entire attention matrix in Equation (I). With a union operator U which concatenates matrices by adding new rows, and considering that K, V contain tokens with indices (1..N} J. and the newly generated token has index i = N - 1, the generative process for the next token proceeds through the attention layers as,
9. [K [KU (VUv))
(a v): =
Vdl
Sparse attention prefill methods aim to reduce the quadratic computation in Equation (1) by computing subset of entries within A, forming sparse matrix A' where the number of computed entries Eig (J > 0} < N² with minimal information loss. However, in practice, large portions of the attention matrix are ignored, which may cause unintended differences in the output tokens and lead to unexpected behavior of future query-key dot products, which could degrade performance on downstream tasks. Previous works have studied in-context learning (ICL) processes such as induction heads [Olsson et al., 2022], which are responsible for copying relevant content from earlier tokens into later tokens in the sequence [Musat, 2024]. Induction heads are known be more prevalent in the lower layers of the network [Yin and Steinhardt, 2025], which implies that a distributional mismatch between queries and keys at the lower layers of the network will inhibit ICL processes. Additionally, Wu et al. [2024] showed that these induction or retrieval heads are universal for all transformer model types and further highlighted that interfering with these special attention heads causes catastrophic drop in performance on downstream tasks during inference.
Recent works on sparse attention, such as Streaming LLM [Xiao et al., 2023], have shown that pretrained quadratic transformers can be modified on-the-fly at test time into a stable sparse attention model by utilizing sink tokens and sliding windows. This has inspired multitude of recent works that utilize this knowledge for inference time adaptations that selectively prune the less important 'middle' tokens from the KV-cache during inference. Two approaches, H2O [Zhang et al., 2024b] and SnapKV [Li et al., 2024] accomplish this by looking at historical attention scores to decide which tokens to prune. However, these works still leave the quadratic prompt in place, which requires a computation overhead of Onn)).
Other recent works have therefore made efforts lower the complexity of the prompt as well. Big Bird [Zaheer al., 2020] studies the effect of randomly choosing keys for every new query in the attention matrix. However, random key selection has been shown to underperform a more targeted selection of keys in HiP Attention [Lee et al., 2024a,b], which applies a brsed pruning mechanism that masks out less important blocks of keys in order to sparsify the computation of the attention matrix. MInfer- ence [Jiang et al., 2024] studies reliably recurring patterns in the attention matrix of specific attention heads, and builds set of sparse kernels which apply sparse attention following these patterns. Star Attention [Acharya et al., 2024] uses sparse strategy akin to that of Streaming L.M with a sliding window, initial tokens, and a fully dense decode procedure which evaluates the dot product between every past key for new queries during the decoding phase. As we show in our experiments, this scheme does not work for all tasks unless the sliding window represents a large percentage of the total context length (see Table 1).
LLM
Str. LLM +
25
0.9
Atta. Outout CleSki
0.5
0.7
0.6
0.5
0.4
Layer:4
0.50
0.85
0.90
0.95
50
Rank Correation of Asin. Rows
Comparing sparse attention methods to quadratic attention. Our
Figure 3:
A correction results in outputs that more similar to quadratic attention.
To illustrate how our findings integrate with these prior works, we provide an example in Figure 3. In this experiment, we use quadratic attention and Streaming L.LM to prefill a 131K length input from the RULER benchmark. We then compute the cosine similarity cos([A [V]: [AV].) of the sparse and quadratic outputs, and also construct the last part of the full attention matrix using the
3

---

Full
AV
Sparse Attn.
AV
Deltn Query-aaryfae
Compute
Correction
Delta
Full Attm.
AV
Approsimated Atta.
ÁV
Sparse
AV
Repeated A
far Quena
Compute Sparse Attention with A
Figure 4: Overview of A Attention. (Top) Given an arbitrary sparse attention method we calculate the difference between the sparse attention and full attention for small subset of queries. The subset size is controlled by a hyperparameter y. (Bottom) We then repeat the calculated difference for all output tokens and add the result to the full sparse attention output. The result is an approximation to the original quadratic attention.
last 128 queries in order to compare the rank correlation coefficient p(A", A,) in the final rows of the attention matrix. If the sparse attention method does not cause distributional shift, then the attention outputs should have a high cosine similarity to quadratic attention, and sorting the rows of the attention matrix should lead to the same order, which implies that the relative importance (ranking) between queries and keys has been maintained. As seen in Figure 3, in both dimensions, the sparse attention of Streaming LLM causes drift in the distribution of tokens, which causes the degradation in task performance seen in Figure I. However, we find we can correct this distributional shift with the addition of A term which we will describe in the following section.
3 Method
Given the distributional shift shown in Figure 3, our method answers the following question: How may shift the distribution of attention outputs such that they are closer to the representation which is expected during quadratic attention? Specifically, we wish to add term to the sparse attention output A "V such that we recover the attention contribution A A from the places where sparse attention has given zero weight. This region is usually located somewhere inside the lower triangle of the attention matrix and resembles a delta shape. We propose to approximate this A region by a simple difference of attention outputs, as geometrically depicted in Figure Specifically.
Falli Autl-Attration
Spare Attentiin Output
Minieg Ama
AV
A
Figure 5: Intuition for A Attention. The difference of attention outputs approximates the missing attention contribution.
AA AV A'V
Note that the softmax normalization of sparse attention methods generally only computes the normal- ization constant over the nonzero values. Thus, A and A have different normalization constants, which makes the relation approximation. We consider A and A to share the same softmax normalization constant. Let the full attention softmax normalization constant be T + H, and the sparse attention normalization constant be T.
Lemma 1. w.l.o.g. Consider an arbitrary row in the attention matrix a and arbitrary column of the values v, with both a and v being sorted according to rank of a such that a = (ar(1) S Gr(2) S S dr(N)): For a top-k sparse atlention matrix which only computes the top-k atlention scores, one only needs to compute a" TV= = -+- a" Vi. With A = vv- -a" T error of our attention approximation as.
v, may bound the
k+1
H
A
V <
max [1s]
H+T
Proof. See Section G.
We ultimately seek a shift in the attention outputs such that A'V + A AV. Trivially, choose A = -V A'V, we have exact equality; however, calculating A requires the full

---

quadratic attention procedure that we wish to avoid. As AV - A'V & AAV, if we further assume that V); (AA for v ? and y E N. then we may approximate (AV)it> R () + (A*V) Under this approximation, one only needs to compute every 7th row of the attention matrix, which maintains a sparse computation by only computing a subset of rows of A. To do this, we select fixed fraction of row indices from Q, such that,
LAU Q
= i mod y O: A e
(4)
and therefore AV (QK V which is sparse in the query dimension, but dense in the key dimension. One possible approach would be to substitute this representation into the appropriate rows of the sparse output A V such that the final representation A, is the following,
make dense output row if mod 7 0
(Av), = (A')), + 1f2 mod y = 0} ÄV [3) - (A (A'V) [
fE.L..N (5)
We dub this approach as 'recompute', as we are essentially using the sparse representation with some densely computed output tokens interwoven at regular intervals. However, we find that this approach still does not shift the distribution of attention outputs far enough towards the expected representation under quadratic attention (see Figure 9). Therefore, in order to apply shift to all tokens in the output of A V while maintaining sparse computation, we instead apply the following correction to the sparse attention output,
(AV] = (A'V); + (A V) 1
(6)
= -A'V)) + ÄV L (A (A'V [41
correction term
Which is equivalent to swapping in a dense row of the attention matrix at every 7th row, and applying the difference between the dense and sparse attention for
Algorithm 1: Attention Algorithm
the previous 7th row otherwise. A visual depiction of this process can be seen in Figure 4, and pseudocode in Algorithm 1. Since our method is applied directly on the attention outputs, we may utilize existing sparse attention kernels to compute A "V and make use of a minimally modified flash attention kernel to compute our query-sparse attention AV.
Require: f0.f f*( Q,K.
I/ sparse attention for all of Q A A + /
Q + Eqqutionn 4
I/ dense attention every 7th query
AV + f(Q. K, V)
I/ collect proper indices for A construction
8 {i i mod ? 0}
Assuming that row index j of the attention matrix is not evenly divisible by 7, this means that an attention differential from previous the current row j. The intuition from this operation comes from prior works which have studied attention locality [Lee et al., 2024a], finding that the difference between attention scores for neighboring tokens is generally small. Likewise, our conjecture is that the low attention score regions from neighboring rows of the attention matrix also have a negligible difference, allowing for the less important part of the row of the attention matrix to be reused multiple times. Specifically, as stated above Equation (4), we assume that (A A)v z (AAV). for D .1. and y N. To validate this assumption, we examine the average cosine similarity of (A* V), within r window on an input from the RULER 131K task set for various values of ? in Figure 6b. We find a high average cosine similarity within the window, implying that (A A AV); may be reused for multiple rows of the attention output.
A +- AV - (A*V) Viie
is being applied to
I/ repeat A and apply correction
AV A repeat( A 7)
return AV
Experiments
We evaluate our method in terms of perplexity (PPL.) and long context perplexity using the Long [Fang et al., 2024] metric on QA version of the PG19 [Rae et al., 2019] test set, which was recently proposed as a long context understanding dataset [He et al., 2025]. We also provide
5

---

Table I: RULER (Llama 3.1 8B Instruct and Mistral NeMo 12B) for sparse attention methods. Adding A Attention results in better overall accuracy, with the largest improvement occurring at the longest context length and on the most naive sparse method (Streaming LLM). Colors are relative to each attention method group + Flash Attention 2.
Model
Llama 3.1 8B Instruct
Mistral NeMo 12B
Flash Atm.
SFr
115
Str.
Str. 11M
Str. LLM-A
Minf.
MInf+
Нip
HiP+A
Flash Att..
Sir LLM
Str: MII--A
Hip
HiP+A
Aun.
Method
Wind.
2K
4K
16K
32K
2K
3K
3K
3K
3K
2K
2k
3K
3K
4K
96.24
90.sz
96.71
96.71
96.71
96.44
96.74
96.7
96.00
96.1
90mm
71.
90xz
90.3
90.ss
8K
.3.22
1 60.s
93.76
93.76
93.76
92.51
93.6
93.89 1 94.56
94.13
1
87.67
44,9
85
88836 36
87.6 .9
16K
'90.s;
38.s
68.oz
91.15
91.15
88.s|
92.32
91.M1
|9..0
94.10
93.s
81.=²
33.23
78.0
78
8
32K
88.s4
30
43.s
56.32
85.g
81
86.75
85.
1 89.92
89.3
62.s4
12.z7
34%
58.76
60.ss
65K
18..2
18.9
34.0x
41.28
58.s
25
84.43
83.67
82.s1
84
|
46.8
03.2s
16.
35.s7
41.56
13IK
73.16
27
30.32
40.s1
49.17
64.10
65.73
73.31
68.74
73.71
18.09
02.25
01
10.10
10.0
Avg.
87.54
25
61.u5
69.9
79.16
83,06
86.60
87.4
87.37
88.76
64.60
27.x3
5
6602s
62.03
evaluations of our method on the RULER [Hsich et al., 2024] benchmark, which tests models' perfor- mance under a number of long context retrieval tasks. Additionally, we evaluate our A Attention on Infinite-ennch [Zhang et al., 2024a]. and also provide analysis that evaluates the effect of our A correction on the distribution of attention outputs and scores, and overall attention latency. Our work considers that the decoding process shown in Equation (2) is dense along the key dimension and should be able to successfully learn from previously encoded information during the sparse prefill.
We apply our method in conjunction with the sparse attention methods Streaming LLM [Xiao et al., 2023], HiP [Lee et al., 2024a.b), and MInference [Jiang et al., 2024], on models from the Llama [Dubey et al., 2024] (3.1 and 4), and Mistral [Jiang et al., 2023] model families. Unless otherwise noted, our standard setting uses y = 64 which means we calculate every 64 query row (approximately 98.5% sparsity) in the attention computation required by A Attention.
RULER. For baselines on needle-in-a- in-a--aysstack type tasks, we compare our method in addition to Streaming LLM, HiP, and MInference for both Llama and Mistral models. In all cases, A Attention shows a large improvement upon the given sparse methods, and especially at the longer context lengths in Table 1. In particular, we note an improvement of nearly 37%pt over Streaming LLM with the same 2K window size for 131K with Llama 3.1. For Streaming LLM, if we adjust for the extra computation needed by our method, we find that the approximate window size of our method is 3072 (see Section F for calculation). This is due to the fact that we also use a sliding window of 2048 and compute every t4 row of the lower triangle in the attention matrix. Therefore, even when Streaming LLM is allowed higher computational budget of a 4K window, A Attention still results in an increase of 34%pt, more than doubling the accuracy of Streaming LLM (+112% relative). Even when Streaming LLM is allowed 32K window, Streaming LLM A with a 2K window still delivers higher accuracy.
Perplexity (PPL) and Long Perplexity (LongPPL). We generated a QA dataset based on the PG19 test set according to the procedure outlined by He al. [2025]. This results in long context task where an entire book is used as context, along with a series of LLM-generater questions and answer pairs with total context lengths of approximately 100K. In order ex- cel at this task, a model must be able to retain all information and facts from the text, which may be asked in the follow-up QA session. We evaluate both PPL and LongPPL, where the latter metric selects a subset of tokens that are found to rely heavily on long context for the final loss calculation. LongPPL. has been shown to have stronger correlation with long context performance over PPI. [Fang et al., 2024]. We use Llama 3.1 8B instruction-tume models for this experiment. Results can be seen in Table 2 and Figure 6. When
Table 2: Perplexity on PG19 Long QA [He et al., 2025]. Our simple A correction results in a signif- icant drop in both PPL and Long PPL.
Method
Long PPL 4
PPL
Flash Attention
5.11
3.33 (-)
Streaming LLM
7.02 (+1.91)
3.54 (+0.21)
Streaming LLM + A
5.96 (+0.85)
3.41 (+0.08)
HiP Attention
6.29 (+1.18)
3.48 (+0.15)
HiP Attention + A
5.45 (+0.34)
3.37 (+0.04)

---

Table 3: oc-bench results. Colors are made relative to the best and worst metrics within each model group, with Flash Attention being part of every group. Our A correction improves overall performance in every case. En. EAR displays recall for the En.QA subset.
Model
Method
Ctx Len.
Fr.MC
Fa.QA
ERQAR
SumSum
Passkey
Number
KV
Math.F
Avg.
Flash Attention
126K
64.19
35.89
44.69
31.59
99.13
99.83
92.40
24.86
61.57
Llama 3.1
HiP
126K
54.15
31.49
38. 12
31.06
75.08
96.10
30.60
18.86
46.93
8B Instruct
HiP + A
126K
61.14
33.70
43.54
31.30
100.0
97.97
69.60
25.71
57.87
Str. L.M
126K
27.95
07.25
14.67
20.57
02.71
01.36
01.20
25.14
12.51
LLM + A
126K
56.33
24.93
33.35
26.95
96.27
68.81
00.40
25.43
41.66
Flash Attention
384K
82.10
44.34
48.82
35.30
100.0
100.0
99.20
43.14
69.11
Llama
HiP HiP A
384K
74.67
43.19
48.29
34.28
100.0
99.83
99.40
41.14
67.60
Scout 109B
384K
78.60
42.84
48.14
34.06
100.0
99.66
97.20
44.29
68.10
Str. L.LM
384K
49.78
15.23
26.11
31.50
52.88
08.31
03 .0
40.57
28.47
Str. LLM+ + A
384K
73.80
37.82
43.03
30.62
94.75
91.36
46.60
40.86
57.35
Fash Atretiio
Stoomin
HiP
Streaming LLM
3.50
3.00
Clvite Suntberiy
0.00
3.00
2.55
1101
0.5
Layers
(a) Perplexity and Long Perplexity
(b) cos([A A V);, [A V1++))
Figure 6: (a) Perplexity metrics for increasing 7 E {23 ...., 28. For PPL and LongPPL, increasing the query stride shows a slight trend towards higher PPL with higher sparsity. (b) Measures the average cosine similarity between the approximate (A (); and (A) for v E (I.....7)
for Streaming LLM and finds high similarity within y neighborhood of attention outputs. High similarity implies (A VV) can be reused within the y neighborhood.
our A Attention is applied on top of both HiP and Streaming LLM, we achieve between a 50-75% reduction the PPL performance gap between quadratic attention. This trend holds true for both PPL and LongPPI.. Figure 6 shows the effect of varying the 7 parameter form 8-256. As y also controls the sparsity, we find that as the sparsity increases, both perplexity metrics tend to rise.
Infinite Bench. /hhag et al., 2024a] For both LLama 3.1 8B and Llama 4 Scout 109B, results are displayed Table The display colors are encoded to show the performance difference within each model group. and including flash attention in all groups For Llama (Streaming LLM), the addition of A resulted in an increase of 40%pt, which leads recapturing 82% of quadratic attention accuracy (up from 41%). Similarly, for Llama 3.1, the addition of A increased overall performance by 29%pt, which moves from 20% of full attention accuracy to recovering 67%. The realized performance gains when applying our method to HiP result in a 10%pt increase for Llama 3.1 and a 0.5%pt increase for llama Note that HiP with Llama 4 only shows total of 1.5% gap in performance, which means that A Attention was able to recapture 33% of the total performance gap.
4.1 Ablation & Analysis
Latency. For a single attention layer, our method shows large reduction in latency when compared to Flash Attention 2 benchmarked at 1M tokens. In Figure 7, HiP + A runs more than 8 times faster. For Streaming LLM + A this factor increases over 32, which means that Attention may perform more than 32 attention operations for single quadratic Flash Attention 2 operation. While our method does require more computation than the standalone sparse methods Figure 7b, the relative increase is modest in comparison to the latency of quadratic attention. MInference has been excluded from these latency results due to the current public implementation not fully utilizing hardware parallelization in this experiment. For further details, please see Section E.
7

---

-
Silf Altratio Larracy ((na)
St. LLM
St..
(r- 1250
St. LLM
HIP +.
800H
2000C
HiP
Ste.
Cy 0022
Alteation
Selt Artestie
K.01X Paarie than FA2
600
1000
2.18X SLLM
1000
32.16X
20
Cinlact Langth
Contest Tangt
Coerest Lenglh
(a) Latency vs. Flash Attention
(b) Latency vs. Sparse Methods
(c) Lateney for increasing ?
Figure 7: (a) shows latency comparisons against flash attention at 1M tokens. Our method maintains most of the large latency reductions of sparse methods. (b) compares latency against plain sparse methods. Our method introduces slight overhead due to requiring computation equivalent to 1.5% of the whole attention matrix. (c) evaluates the effect of different Y parameters on latency. We find that increasing the stride between queries leads to expected decrease in latency.
How does the A affect attention outputs and scores? To study the effect of the A correction on the attention outputs and scores, we evaluate both attention output cosine similarity and the Spearman rank correlation coefficient [Spearman, 1904] of the attention rows for the last 128 queries of the prefill. For this, we used sample from the MultiKey-3 RULER (131K) benchmark with the Llama3. 8B instruction tuned model. A subset of layers is depicted in Figure 9, where each point the plot and histogram is random sample from one of the 32 128 (attention heads and queries). Additional plots for all layers in the network can be seen in Figures 13 to 15 in the appendix. At the key lower layers where the induction heads are known to be most prevalent, we find that the A correction results in a large corrective shift in both the rank correlation and cosine similarity, making both metrics much closer to the ground truth distributions of quadratic attention. Notably, only using 'Recompute', which densely recomputes some rows of the attention matrix, is not enough to shift the distribution, as it indistinguishable from the plain Streaming LLM model in Figure
In Section I, we stated that A Attention shifts the distribution of attention outputs towards the distribution which would be seen under fully quadratic attention. Figure 9 provides three more examples of lower layers which show the same shift as shown in Figure 3. It is notable, however, that this strong shift towards the distribution of quadratic attention is not present in all layers of the network. Figures 13 to 15 together show all layers. A Attention appears to maintain a strong similarity to quadratic attention at the lower layers, which gradually dissipates until layer 10, when the three methods become indistinguishable However, there is a sudden rise in attention output cosine similarity again towards the last layers of the network
While both the output cosine similarity and the rank correlation are important, the high rank correlation coefficient provides crucial insight as to how the A correction aids in improving performance. For sparse methods, the last 128 queries from a 131K K context have undergone a distributional shift induced by the sparse method, which means that they key tokens during dot- product attention. A high rank correlation, however, implics that the ranking (importance order) of dot products across entire row of the attention matrix remains largely intact and therefore, should result in outputs with higher similarity to quadratic attention outputs. This suggests that dense decoding can now effectively access information buried deep in the prompt, which is something our experiments show sparse attention methods struggle to do.
longer correctly align with the appropriate
Does Equation (5) or Equation (6) Perform Bet- ter? In the previous paragraph we gave qualitative examples of the difference between Equation (5) and Equation (6) on the attention output cosine similar- ity. Now ask, how does this observed difference affect the performance of the model? Table 4 shows the effect of 'recompute" from Equation (5), which recomputes a selected number of queries with dense attention and does not apply the difference to
Table 4: RULER ablation for Equation (5) 'recompute" and Equation (6) A.
Model
131K 65K 32K
Avg.
Str. LLM
27.45 18.59 30.25
44.25
Str. LLM Recompute 52.67 72.71
78.39
79.999
Str. L.MM+ + A 64.40
75.22 81.27
883.0
subsequent tokens in the y neighborhood. Only recomputing tokens results in a 37%pt increase over all context lengths and is only 3 3%pt short of matching A. However, at the longest context length, A still delivers more than 1 1pt increase in accuracy.
Figure& shows 'recompute' compared to A Attention for individual subsets of the RULER- 131K context length. We find that the only case where 'recompute' outperforms our method is on the
8

---

LLM
St.. LLM Rocsmpule
LLM
0.5-
Atta. Outpet CoeSin
Arta. Outgut CoeSin
0.7
R6-
0.2)
Lawer:33
Layer:5
Layer:6
0,90
B:56
G0
3U55
0.30
2050
0.5 Donic Cormdation Attn. Rows
Dania Cormlation Attn. Donss
Doniz Cordiation Atnn, Tonn
Figure 9: For RULER with a context length 131K, we look at the final 128 tokens in the attention output and the final 128 queries in the attention matrix. We compare the cosine similarity of the outputs and the rank correlation of the attention rows to quadratic attention. We find that for both measures, A Attention is more similar quadratic attention.
variable tracking subset (VT). We are unsure of the cause this anomaly, although it is important to note that 'recompute" that there is some structure within this task that happened to benefit from 'recompute'. In general, flash attention should represent general. Note that the CWE subset of RULER is removed from this plot, as all methods (including flash attention) score 0% on the 13 context length.
outperformed flash attention by approximately 15%pt, which implies
upper bound to sparse attention, which is what observe in
5 Discussion & Limitations
Flash Actention
Str. LLM + Recorapute
Our method presented thus far has been simple extension to existing sparse attention methods, which can be applied with a minimal addition of overhead and very simple modification to the attention layer. The common way of computing sparse attention in prior work is to compute attention output that dense in the queries and sparse the keys, so that there is at least one output for every input query token. One way to view our Attention extension that are mixing key-sparse (and query -eere) atten- tion output with query-sparse (and key-dense) attention output in order to arrive representation which is closer to the quadratic attention output that is dense in both the queries and keys.
St: LLM
Str. LLM + A
QAI
FWE.
MTAI
NIAI
1100
NIAH
NEAT MK
The idea of viewing attention sparsity from both dimen- sions holds the potential for future works to explore novel ways of combining various combinations of sparse meth- ods in order to approximate the full attention operation. With Lemma 1, we were able to show that the difference of attention outputs approximates the missing attention output, however, we only have empirical evidence of the secondary approximation that (A V);; R (A (A ++ for v E {1,....? 7. While this empirically validated in our experiments and by the high cosine similarity in Figure 6b, future works may study this approximation further,
NIAH MIK
Figure 8: Comparing the effects Equa- tion (5) 'recompute' and Equation (6) A on RULER 131K subsets.
which could lead to creating a smarter selection criteria for the query sparse attention, as our method uses only a fixed hyperparameter to set the size of the gap between query tokens.
6 Conclusion
In this work, we first diagnose harmful distributional shift induced by sparse attention prefill methods. We then propose a remedy with our lightweight, pparse-kernel agnostic A Attention procedure. A Attention corrects sparse outputs to align better with full quadratic attention outputs, requiring only small post-processing step that can be integrated seamlessly into existing inference pipelines. Across all benchmarks, and especially at the longest context lengths, our method delivers significant accuracy gains while maintaining high sparsity and low latency.

---

7 Acknowledgments
This work was supported by:
Institute for Information & communications Technology Planning & Evaluation(IITP) grant funded by the Korea government(MSII) (RS-2019-11190075, Artificial Intelligence Graduate School Program(KAIST))
National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2023-00256255)
Artificial intelligence industrial convergence cluster development project funded by the Ministry of Science and ICT(MSIT, Korea) & Gwangju Metropolitan City
The Institute of Information & Communications Technology Planning & Evaluation (IITP) with a grant funded by the Ministry Science and ICT (MSIT) the Republic Korea in connection with the Global AI Frontier Lab International Collaborative Research. (No. RS- 2024-00469482 RS- 00-2002-00000229)
DeepAuto R&D Program (No. DA-RS-2025-01)
A gift grant from Google
References
S. Acharya, F. Jia, and B. Ginsburg. Star attention: Efficient Ilm inference over long sequences. arXiv preprint arXiv:2411.17116 2024.
T. Dao. Flashattentionn2:: Faster attention with better parallelism and work partitioning. arXiv preprint TrXiv:2307.0869/ 2023.
H. Dong, X. Yang, Z. Zhang, Z. Wang. Y. Chi, and B. Chen. Get more with less: Synthesizing recurrence with kv cache compression for efficient Ilm inference. arXiv preprint arXiv:4402.09398, 2024.
A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Yang, A. Fan, et The Ilama 3 herd of models. arXiv preprint arXiv:2407.2178. 2024.
Fang, Wang, Z. Liu, C. Zhang, S. Jegelka, Gao, B. Ding, and Y. Wang. What wrong with perplexity for long-context language modeling? arXiv preprint arXiv:2410.237711 2024.
L. He, J. Wang, M. Weber, S. Zhu, B. Athiwaratkun, and C. Zhang. Scaling instruction-tuned llms million-token contexts via hierarchical synthetic data generation. arXiv preprint arXiv:2504. 12637, 2025.
C.-.. Hsieh, Sun, S. Kriman, S. Acharya, Rekesh, F. Jia, Y. Zhang, and B. Ginsburg. Ruler: What's the real context size of your long-context language models? arXiv preprint arXiv:2404.06654, 2024.
A. Q. Jiang, A. Sablayrolles, A. Mensch, C. Bamford, D. S. Chaplot, D. d. I. Casas, F. Bressand, G. Lengyel, G. Lample, L. Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.06825 2023.
H. Jiang, Y. Li, C. Zhang, Q. Wu, X. Luo, Ahn, Z. Han, A. Abdi, D. Li, C.-Y. Lin, al. Minference 1.0: Accelerating pre-filling for long- cong-context lims via dynamic sparse attention. arXiv preprint Xii:24407.02490 2024.
H. Lee, G. Park, Y. Lee, J. Suh, J. Kim, W. Jeong, B. Kim, H. Lee, M. Jeon, and S. J. Hwang. A training- free sub-quadratic cost transformer model serving framework with hierarchically praned attention. arXiv preprint 2xXiv:2406009827, 2024a.
H. Lee, G. Park, J. Suh, and S. J. Hwang. Infinitchip: Extending language model context up to million tokens on single gpu. arXiv preprint arXiv:2502. 08910. 2024b.
Y. Li, Y. Huang, Yang, Venkitesh, A. Locatelli, H. Ye, Cai, P. Lewis, and D. Chen. Snapkv: Lim knows what you are looking for before generation. arXiv preprint urXiv:2404.14466 2024.
10

---

J. Liu, J. L. Tian, V. Daita, Y. Wei, Y. Ding, Y. K. Wang, J. Yang, and L. ZHANG. RepoQA: Evaluating long context code understanding, In First Workshop on Long-Context Context Foundation Models @ ICMI. 2024, 2024. Btt.https://ppenreviee
net/foormmidd--KWssPuu
T. Musat. Mechanism and emergence of stacked attention heads in multi-layer transformers. arXiv preprint arXiv:2411.12118, 2024.
C. Olsson, N. Elhage, N. Nanda, N. Joseph, N. DasSarma, T. Henighan, B. Mann, A. Askell, Y. Bai, A. Chen, et al. In-context learning and induction heads. arXiv preprint arXiv:2209. 1895, 2022.
W. Rac, A. Potapenko, S. M. Jayakumar, C. Hillier, and T. Lillicrap. Compressive transformers for long-range sequence modelling. arXiv preprint, 2019. URL 05507.
orgp ab9111.
C. Spearman. The proof and measurement of association between two things. American Journal of Psychology, 15:88-103, 1904.
J. Su, M. Ahmed, Y. Lu, S. Pan, W. Bo, and Y. Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 568:127063, 2024.
Y. Sun, T. Ye, L. Dong, Y. Xia, J. Chen, Y. Gao, S. Cao, J. Wang, and F. Wei. Rectified sparse attention. arXiv preprini arXiv:2506.00 108, 2025.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
W. Wu, Y. Wang, G. Xiao, H. Peng, and Y. Fu. Retrieval head mechanistically explains long-context factuality. arXiv preprint arXiv:2404. 15574, 2024.
G. Xiao, Y. Tian, B. Chen, S. Han, and M. Lewis. Efficient streaming language models with attention sinks. arXiv preprint arXiv:2309.17453. 2023.
X. Yang, T. Chen, and B. Chen. Ape: Faster and longer context-augment generation via adaptive parallel encoding. arXiv preprini arXiv:2502.0544// 2025.
J. Yao, H. Li, Y. Liu, S. Ray, Y. Cheng, Q. Zhang, K. Du, S. Lu, and J. Jiang. Cacheblend: Fast large language model serving with cached knowledge fusion. arXiv e-prints, pages arXiv-2405, 2024.
K. Yin and J. Steinhardt. Which attention heads matter for in-context learning? arXiv preprint arXiv:2502. 14010, 2025.
M. Zaheer, G. Guruganesh, K. A. Dubey, J. Ainslie, C. Alberti, S. Ontanon, P. Pham, A. Ravula, Q Wang, L. Yang, et al. Big bird: Transformers for longer sequences. Advances in neural information processing systems,
172977 2020.
X. Zhang, Y. Chen, S. Hu, Z. Xu, Chen, M. K. Hao, X. Han, Z. L. Thai, S. Wang, Z. Liu, et al. Infinity bench: Extending long context evaluation beyond 100k tokens. arXiv preprint a4Xiv:2402.1 13718, 2024a.
Z. Zhang, Sheng. T. Zhou, T. Chen, L. Zheng, R. Cai, Z. Song, Y. Tian, C. Ré, C. Barrett, et al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36, 2024b.

---

A Appendix Contents
Section Discusses the broader impact of work.
Figures 13 15 shows individual plots comparing cosine similarities and rank correlation
coefficients against quadratic attention for all layers, analogous to Figure 9.
Figure 10 shows an additional study on the parameter and latency for Hil, analogous to Figure 7c.
Section C discusses details about the implementation of our method.
Section discusses details regarding latency for MInference.
Figure 12 shows bar charts for the full set of datasets for the RULER 131K context length.
Section states the computing resources that were used for the experiments in this work.
Section discusses additional related works and comparisons.
Section I shows the performance of our method on code understanding.
Section J discusses and shows results for interpolation/innutatiion between delta terms.
Section K contains paired permutation statistical significance test corresponding the
RULER results in Table 1.
B Broader Impact
We are not aware of any negative potential impacts of our work beyond impacts that are general to all machine learning models. However, lowering the computational cost for inference has the potential to lower costs such as electricity consumption, hardware requirements, and latency for end users. this can effectively be done with minimal degradation in the performance of the underlying model, will likely be beneficial to both producers and consumers of AI models.
C Implementation Details
In addition to the index selection in Equation (4), in practice, we also select a block of queries for dense recomputation at the end of the prefill sequence, which makes the part of the prefill which requires a delta correction evenly divisible by 7. We do this for both ease of implementation and also to provide the decoding tokens with the most accurate block of recent context. The block of queries at the end the sequence allows us to simply reshape tensor and project the A correction onto every element in the block, the tensor that needs delta correction will have regular size that is divisible by ?..
D Compute Resources
For LLM inference on benchmark datasets, we use Google Cloud Platform's 8x NVIDIA H100 node. For latency measurements, we use standalone machine with an NVIDIA RTX 4090 in order to have controlled environment. Here, we show the detailed specification of the latency benchmarking machine:
CPU
AMD Ryzen 7950X, 16 Core, 32 Thread 128GB, DDR5 5600 Mhz Nvidia RTX 4090, VRAM 24GB
RAM
GPU
PCIe
Gen 4.0 x8
OS
Ubuntu 22.04.4 LTS 535.171.04
GPU Driver
E Latency of MInference with Delta Attention
We did not report the latency MInference the main paper, because MInference shows unusually slower latency than other tested methods, including Flash Attention. We think this is due (1)
12

---

HiP ( 64)
Self Attention Lateney (ms)
[НР A 128)
[hP A ( 256)
HiP (1 512)
2000
0.0
0.2
0.4
0.6
0.8
1.0
Context Length
Figure 10: Lateney measurements for different settings of y which controls the gap size between queries and also the overall sparsity of the calculation. This figure accompanies the latency ablation for Streaming LLM in the main text, Figure 7c.
insufficient optimization of the publicly available kernel and (2) MInference uses for-loop across the head dimension that prevents the head dimension from being parallelized within the GPU. This limitation the publicly available implementation will cause the latency to suffer the attention calculation for each head does not fully utilize the hardware. This for-loop structure was likely implemented in this way because MInference uses different sparse attention strategies for each head. Therefore, as MInference is algorithmically faster than flash attention, we do not report the latency in Figure 7, as this would be misleading to readers who are not familiar with the low-level details of the implementations.
We capture the kernel latencies and hardware utilization MInference. In our analysis with Nsight Systems, their vertical slash pattern kernel _trrttnn__ seap__ixe____eeee aal___saaaeattae aetee_ttt_____tt _ttn_fwd_____________________ fyd_keenel', shows around 32 milliseconds latency for single head, while flash attention shows only 462 milliseconds for 32 heads. The MInference kernel shows noticeably low utilization of streaming multiprocessor warps, which around 9%.
However, for completeness, put the latency measurements of MInference in Table 5. In our measurement using their official codebase without meaningful modification, with pre-compiled model configuration for head-wise sparse method settings. Minference is about 1.377 times slower than Flash Attention. We believe this only due the lack of fully parallelized kernel and not the design of the method.
Table 5: Prefill latency measurements (ms) that include MInference on RTX 4090 up to 256K context length.
32K
64K
128K
256K
FA
34.27
119.77
462.39
1858.60
HiP
53.61
118.53
255.05
562.24
HiP
A
55.44
123.49
268.02
602.74
Minference
135.28
395.92
1083.66
2559.47
F Approx Window Size Calculation
When comparing out method to Streaming LLM, we would like to know how much computation overhead is increased in order to estimate the approximate window size of method due to the fact that A Attention computes extra tokens. We can calculate this as follows with C as the context size, and the window size in single of the attention matrix, our method will
13

---

compute every 7 row of the attention matrix which would be equivalent to C when amortized into each row calculation. This brings the total calculation per row to w + 25' In the case of 131K context, a window size of 2048, and 7 = 64 (our standard setting) this would be evaluated as 2 2048 + 2(2%) 2048 + 2 2048 + 1024 3072.
G Restatement and proof of Lemma 1
We want show that the difference of A A x AV A'V is approximately equal to the missing delta-shaped attention output, which is pictured Figure 5. w.l.o.g.. we will consider a single arbitrary row of the attention matrix and single column vector from the values The following true regardless of the selected entries in a, however, in order to create tighter error bound, we assume the existence of sparse attention method which chooses the largest attention values in when calculating the sparse dot product v a". Specifically,
Lemma (Lemma 1). Let (ā),... aa) E Rdd be the pre-softmax vector which is sorted and satisfies,
a S 02 ... S... aN,,
then any exact top-k sparse attention method which selects the top-k attention scores should select the last k elements of a. Fix an integer S k S N. Define the head-sum H, tail-sum T, and normalization constant Z be the following:
k
H=
(8)
N
T
(9)
i=N
Z H T
(10)
Set
0,
is N k,
c
a; Z
a' ;
ch
i>N-K
T
For any = (Ui,...,val vd) E Rd which is sorted according to the rank of elements in define the tail-max as,
Meall
max
11
is.N 8
write
= a v - a² v,
we have the exact decomposition
N-k
A
a, V; + R.
where the "remainder" term
N
R =
Σ
a. - a²
N=N-k-1
is upper bounded by
H
R
<
M
H T
Therefore,
A
a V;
=|
(11)
H
Muail
(12)
H + T
14

---

Proof. Split
N-k
A
a
Σ
|a; a
(13)
N=
N
a V + R.
(14)
t=1
N k.
e
c T
T
a.;
H+T
T
H +T
H T
SO
T
a.
a
aj
(15)
H
H H+T -1)
T
aa;
(16)
H
-
(17)
H
Thus
H
N
R
Σ
a a'
H+T
N+1
and since Ei=N Ni=N-K11 k+1 a"; = 1 and [vs] < Mrail on the tail,
H
|A|
a' Vi
(18)
H
(=N-k+]
< H
a' avilvsl
(19)
H T
i= N=++
H
<
H Mrail-
(20)
completing the proof.
If we assume that T' Hl as is the expected outcome with sparse attention, then the bound becomes tighter, as the denominator H T > H. This implies that better sparse top-k approximations will result in lower error bound. We empirically verified this difference in Figure 11, which analyzes both the error bound and the empirical eтror on real input from the RULER- subset. Figure 1 la measures the bound and empirical error of an oracle top-k attention while Figure llb measures the same bound and empirical error for Streaming LLM, which chooses sliding window and attention sink. We find that the bound is generally tighter for the oracle top-k attention, but both cases, the overall empirical approximation error remains low.
15

---

(2% sporse)
44% sqaane)
88% spanse)
(93.75% squae))
R bound (90 22% spurse)
R. houmd (98 44% spane)
bound (96.95% sparse)
R2. bound (53 75% spans))
AV A4v
0.20
AV 4'V AAV/
0.8
0.15
0.6
0.10
0.4
0.05
0.2
[R]
[R]
0.00
0.0
Layers
Layers
(a) Oracle top-k sparse attention.
(b) Streaming LLM.
Figure 11: Empirically analyzing the approximation and bound from Lemma 1. A more precise sparse top-k attention method, such as an oracle (a) maintains tighter bound on the approximation error. Streaming LLM (b) results in a looser bound, however the empirical approximation error (solid lines) remains low in both methods.
Fash Alrerioo
Straming LLM
N00 Stremming LLM
HiP
N000
HIP
Minforooe
2000
Minference
DULER 131K Stlertts
100
M NIAH MKC
Accurey (9))
50
NIAH
NIAH 2
NIAH
NIAH MK
NIAH MK
RULER 131K Sabeets
100
Accuniyy (X)
20
NIAH MV
NIAH MQ
VT
PWE
QA
Figure 12: All RULER 131K subsets. This is companion to Figure The CWE subset is excluded, as all models, including quadratic attention, scored 0%.
16

---

H Extended Related Work
In addition to the related work cited in Section 2, there are number of additional works which deal with related topics that we wish to highlight.
LESS [Dong et al., 2024] requires training a low rank cache compressor. LESS mentions differences in attention distributions between dense and sparse attention, however, the authors 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 induced by the sparse prefill.
Cacheblend [Yao al., 2024] proposes using one dense attention layer identify important tokens, and then selectively recomputing these tokens in later layers to add missing parts of the sparse attention cached KV pairs. Cacheblend proposed this way augment and consolidate independently processed chunks of RAG pipeline. In practice, however, this would effectively be similar 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. As out experiments show, this is not always sufficient to fix the distributional shift between sparse and dense prefills.
APE (Yang et al., 2025] 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 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.
Rectified Sparse Attention [Sun et al., 2025] (a concurrent work) considers dense prefills and a sparse decoding procedure. Their sparse decoding procedure is similar to what call "recompute" in Table 4 and Figures 8, and 13 to 15 where we showed that this "recomptue" method is insufficient mitigate the distributional shift in the outputs.
Comparisons to these extended related works, and to Star Attention [Acharya et al., 2024] can be seen in Table 6.
Table 6: RULER comaprison to related works sparse attention and sparse RAG works.
Method
131K
65K
32K
16K
8K
4K
Avg.
Str.LLM
27.45
18.59
30.25
38.13
60.53
90.52
44.25
Cachblend
0.00
0.21
0.31
1.49
24.42
96.27
20.45
APE
26.76
43.03
53.13
67.50
77.25
93.76
60.24
Str.LLM + Delta
64.40
75.22
81.27
88.66
92.25
96.54
83.06
Star Attention Mask
12.00
14.86
20.43
31.66
51.60
78.62
34.86
Star Attention Mask + Delta
58.84
70.12
74.77
82.69
89.12
93.28
78.13
I RepoQA
We evaluate A Attention on code understanding by using the RepoQA [Liu et al., 2024] dataset that asks the model to retrieve function from long block of input text. In this dataset, the long input text contains the code from many functions and the query contains a plain language description of what the function does. The model is then supposed to return back the correct function output. We compare Streaming LLM with and without our delta correction in Table 7
Interpolation
The method presented in Section 3 proposes to use single delta correction at index i to influence the next + 7 attention outputs. This causes discrete jump in the delta correction at every 7tth output. It may be the case that a better strategy would be to smooth out the transition or impute the delta corrections within the window by some imputation function. In Table 8, we look at three different possible imputation functions and evaluate the overall effect on RULER.
17

---

Table RepoQA results for Streaming LLM and Streaming LLM + Delta. Plain FA3 is included for reference.
Threshold
0.0
0.1
0.2
0.3
0.4
0.5
0.7
0.8
0.9
1.0
Avg
Vanilla (FA3)
94.8
92.2
90.6
89.4
88.8
88.4
86.8
85.4
84.4
83.2
76
87.27
Str.LLM
73.6
64.0
60.6
58.8
57.6
56.8
55.0
53.0
50.4
44.2
35.6
55.42
Str.LLM + Delta
85.8
78.0
73.8
72.0
70.6
67.0
64.8
61.2
57.2
50.4
42.6
65.76
Algorithm 2: a, 8, Filter
Require: B and A vectors zero vector like A
< Ao
- zero vector like p
< zero vector like p
< An
for i in [1....,len( A)] do
y f A,
// update approx position and velocity
p + p p+ + 0.5a
0 +
1/ calculate difference between real and predicted position
3 y
11 update position, velocity, and acceleration.
p p +r
V +- 0 + Br
+ "
+
end for return 0
Linear Interpolation. For linear interpolation, we first compute all delta corrections, and then produce mixing coefficients B E [0, 1] which linearly increase from [0. .o., 1]. Interpolation is then performed between consecutive delta correction terms by the function Å (1 8x 8x)a, + A+41 Each A term will therefore expand into J = Y terms, such that the number of delta corrections now matches the sparse attention output size. These expanded, and smoothed delta corrections will be treated as the new correction term, providing smoother transition between terms.
EMA. Instead of linear interpolation, which technically violates the causality of the attention mecha- nism by incorporating information from the future into the past, may instead expand the delta correction term by repeating each vector times, and then perform an exponential moving aver- age (EMA) the full of vectors using coefficient E [0, 1] and computing the EMA as A; = (1 3-) 3A, The EMA acts as smoothing mechanism which smooths the transition between delta terms.
a, 3, Filter. third option to use a Kalman style filter. We chose to use an a, 3, filter where is position coefficient, 3 is velocity coefficient, and r is acceleration coefficient. At each step. position, velocity, and acceleration are updated based on a mixture of the real position and the accumulated statistics for position, velocity, and acceleration. We consider every operation to be elementwise scalar operation. The algorithm for the a, 3, y filter can be seen in Algorithm 2
Although there are slight improvements using these imputation methods in Table 8, no method shows conclusive improvements over our original method. However, we think delta smoothing or imputation shows promising direction for future research.
18

---

Table Interpolation Experiments.
Method
131K
65K
32K
16K
8K
4K
Avg.
St.LLM + Delta Linear Interpolation
65.15
75.65
81.26
88.26
92.34
96.66
83.22
Str. LLM Della EMA (3 0.3)
63.21
75.22
81.27
88.66
92.25
96.54
82.85
Str. LLM Delta EMA (3 0.75)
63.40
74.60
80.76
88.52
92.29
96.62
82.69
Str. LLM Della EMA (3 = 0.95)
63.16
75.87
81.03
88.27
92.26
96.59
82.86
LLM
0.05.
.y 10-50 Filter
58.35
73.48
80.54
88.15
92.03
81.50
Str. LLM Delta (ar = 0.1, = x 10 3,7 1,66 10 4 Filter
57.99
72.70
79.64
88,58
92.42
96.57
81.31
Str. LLM Delta 0.2,3
3.5 10-3) Filter
61.47
74.31
80.29
88.47
92.32
96.58
82.24
StrLLM Delta
64.40
75.22
81.27
88.66
92.25
96.54
83.06
K Statistical Significance Tests
We assess the statistical significance of the results presented Table For this, we use one-sided paired permutation test to test the significance of the difference between the versions of Streaming LLM, HiP and MInference with and without our delta correct applied. The results are shown in Table 9. We split RULER tasks according to QA non- retrieval tasks. The statistical significance shows a high correlation with the displayed colors in Table and verifies that our results statistically significant.
Table 9: Interpolation Experiments. Each entry is a p-value assessing whether or not our delta correction results in significant improvement (significance level is p < 0.05).
Method
131K
65K
32K
16K
8K
4K
Str.LLM (all non qa tasks)
0.0001
0.0001
0.0001
0.0001
0.0001
0.0001
Str.LLM (all qa tasks)
0.0001
0.0001
0.0001
0.0001
0.0001
0,4958
HiP (all non qa tasks)
0.0001
0.0018
0.7112
0.5018
0.8331
0.5747
HiP (all qa tasks)
0.4918 18
0.7252
0.9245
0.8076
0.5009
Minference (all non qa tasks)
0.0001
0.858
0.6485
0.5116
0.8774
MInference (all qa tasks)
0.0004
0.8813
0.9848
0.8777
0.499
19

---

Str. Rocooppiee
1,00
Atta Outpat CooStnn
0.00
Attn Outgat CoeSin
0.5
0.003
0.000
1
Layer:2
Loyer:3
0.550
6:455
0:500
Conreltton
Rows
Str 1LM
Str. LLM Rocompute
Str. LLM &
0.9
Atta. Output CodSin
0.0
Atm. Ourgat Coelin
0.5
0.7
0.1
Lag
Layer:
Layer:6
0.00
Corrdatio Atto.
Corddatio
Att. Rons
Str 1LM
Str. LLM Bocompute
Str. LLM
0.0
Output Coclin
Atmn Ourput Codlin
0.8
0.77
0.6
0.7
8.c
86
Layer:7
Layer:8
Layer:9
0.7
Corndiaion Altu.
Bouia Conndalno
Baws
Carrdalio
Rowsi
Str LLM
Str. LLM Rocompute
Str. LLM
A
10
6.9
Octpp Coolan
Atn. Ouantt Coslmn
0.5
Output
0.71
6.6
6.5-
8.4
Layce:10
Layorg11
Roak Chendition
Bauic Conddation
Rons
Figure 13: Attention output cosine similarity (compared to full attention) for Streaming LLM with our method. Figures 13 to show the results from every layer, and are counterpart to Figure in the main text. For the lower layers where induction heads are most prevalent, our method shows higher cosine similarity and attention row rank correlation as compared to quadratic attention.
20

---

Str. Rocomptte
10
0.5
CooSinn
Ann. Ourput CooBann
Output
Layerzl
Layer:1
0.5
0.
0.5
0.6
0.7
0.9
0.6
0.S
Runi Corrdiaion of Alto. Rows
Ronz Corrdation of Arno Rums
Rani Corrdation of Altn. Rows
Str. Bocompute
10
Atta. Output CorSarr
Attn. Outpur Coulaan
Rd
Output
0.
Layer:16
Layer:17 17
Layer:18
Cormiation
Ronic Correlation
Corndotion
Str 1LM
Str. LLM Rocompute
Str. LLM
Atta Outpa CadSin
0.6
Atta Outpet CuaSin
Outpect
64-
Laysr:19
0.9
Layer:20
Layer:21
B19
0.2
0SS
07
Bonk Coenelation Attn, Rows
Ronic Cormlation
Attn, Roxes
Ron's Corndation of Attn, Rows
Str 11M
Str. TLM Recompate
Str. LLM
10
0.6
Auta Outpet CoeSin
0.6
Atn. Outpot CosSin
Outpet
0.6
8e-
0.2
Layer:22
0.2
Laylrr25
Layor:24
1N7 Donis Cormdation Atto. Rows
110
C6
0.7
0.5
03
Doniz Cormeatton of Attn. Rowe
Raak Cocndatton of Attn. Rows
Figure 14: Attention output cosine similarity (compared full attention) for Streaming LLM with our method. Figures 13 to 15 show the results from every layer, and are a counterpart to Figure in the main text. For the lower layers where induction heads are most prevalent, our method shows higher cosine similarity and attention row rank correlation as compared to quadratic attention.
21

---

Str 1LM
Str. LLM Rocompute
Str. LLM
Att.. Output Ocelen
88
Ast. Ourput CooBenn
Layer:25
82
Layer:20
Tayer:27
D.7
0.5
0.3
0.9
Ranic Cormiation Altnn Roos
Ronic Cormlation Attn. Ross
Ronic Cormistion of Athn. Powss
1LM
Str. LLM Rocompute
LLM
6.6
Attn Coditn
0.55
Asto, Outpett Cuslm
Ourput
6.6-
0.4
0.2
Layor/28
Layer:29
Layer:30
0D0
10
0.9
10
Brak Cocrelation of Attn, Rows
Bank Coenelation of Attn. Towr
Ran's Cormintion of Attni Rown
11M
Recompate
10
0.6
Art.. Output Codiim
Nen. Output CooSan
0.6
Layer:31
Layer:32
A11 Enyere
017
0..
0.5
0.80
0.55
(L.0)
1.50
0.0
0.7
0.8
0.0
100
Danis Corrlation Attn. Rows
Danis
Cormdation of Attn. Powns
Rank Corndation of Artz. Tumn
Figure 15: Attention output cosine similarity (compared full attention) for Streaming LLM with our method. Figures 13 to 15 show the results from every layer, and are counterpart to Figure in the main text. For the lower layers where induction heads are most prevalent, our method shows higher cosine similarity and attention row rank correlation as compared to quadratic attention.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the abstract and introduction are verified in our experiments conducted in Section 4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed limitations of our method in Section 5.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification: We have one theoretical result in Lemma 1, which was stated briefly in the main text. We have included a more detailed derivation and statement in Section G. This section was also referenced under the lemma in the main text.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have provided all necessary information to reproduce our results. Our method only relies on publicly available pretrained models. We have included experimental code as well.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
24

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: The datasets we use are publicly available and cited. We generated one dataset according to a previous paper (PG19 Long QA), which has been included in our supplementary materials. The code for our experiments is included in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: ctapss.cc/pubiic/geee http/puublcgguudess... Sttp//uuddds/oeeuubbimii
CCodeSubmissac ssi assionooicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have one hyperparameter which is specified in Section 4. We have also provided Algorithm
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Our method is deterministic and works pretrained models. Therefore, there no stochasticity present in order to report error bars. Instead we conduct range of experiments different datasets in Section 4 in order verify that the results do not randomly favor our method for a particular experiment. However, we do provide a paired permutation test for the RULER experiments in Section K.
Guidelines:
25

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have stated the full range of compute resources in Section D.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that NeurlPS Code of Ethics https //neurrrisp... cc httppbliicttiiiccciiieeeeeeeeeel
didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the
Answer: [Yes]
Justification:
We have read the ethics guidelines, and we believe our paper conforms to
them.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
26

---

Justification: In Section we discuss the enormous costs and negative externalities caused by inference compute requirements. We also discuss the broader impacts in Section B.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: We create no new data or models to release, our method proposes a modification to existing pretrained models for inference efficiency.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The datasets we use are publicly available and cited included in the supple- mentary material. The dataset included in the supplementary material is a derivation of publicly available dataset, and the method for constructing it has been cited in Section
Guidelines:
The answer NA means that the paper does not existing assets.
27

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license ge.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi twodde com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pane re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We are releasing QA set which was specified by previous work, but released by those authors directly. We have generated the dataset according to their code, and are releasing with our supplementary materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not applicable
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
28

---

Justification:
Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality the research, declaration is required.
Answer: [NA]
Justification: Not applicable
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https htt.r/ips..c/oooffeeeee/e/////// for what should or should not be described.
29


Reviews:
[{"review_id": "T0pLhtImis", "reviewer": "Reviewer_QxjE", "summary": "This paper addresses a critical limitation in sparse attention methods: the performance degradation caused by distributional shift in attention outputs. The authors propose ∆ Attention, a post-processing correction method that computes the difference between sparse and full attention for a subset of queries and applies this correction across all positions. The method achieves performance improvements on various tasks while maintaining computational efficiency.", "questions": "See weaknesses", "limitations": "See weaknesses", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n1. The proposed ∆ Attention is practical for improving accuracy with minimal computational overhead, which can be applied to various existing sparse attention techniques.\n2. Excellent motivation by identifying the root cause of sparse attention degradation: distributional shift between dense and sparse attention\n3. Evaluation across multiple benchmarks, including RULER, Infinite-Bench, and PG19\n\n**Weaknesses:**\n1. The paper fails to provide convincing theoretical evidence for why computing full attention for only sparse queries (every γ-th position) is sufficient to correct the distributional shift across all positions. The core assumption that (A∆V)i ≈ (A∆V)i+ν is supported merely by empirical cosine similarity measurements (Figure 6b), lacking rigorous theoretical grounding. This fundamental gap undermines our understanding of when and why the method works\n2. The experimental evaluation suffers from two critical issues: (1): When comparing with KV cache eviction methods (e.g., StreamingLLM), the authors fail to explicitly acknowledge that ∆ Attention requires storing complete Key-Value pairs, dramatically increasing memory requirements from ~2K tokens to the full sequence length. This makes the comparison fundamentally unfair, as the methods operate under entirely different memory budgets. (2): For advanced sparse attention techniques with dynamic sparsity (HiP, MInference), the improvements are marginal (4-8%), raising questions about the method's 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.\n3. Some previous work has already worked on fixing the distribution shift for different kinds of sparse attention at test time, including:\n    \n      [1]. Dong, Harry, et al. \"Get more with less: Synthesizing recurrence with kv cache compression for efficient llm inference.\" arXiv preprint arXiv:2402.09398 (2024).\n\n      [2]. Yao, Jiayi, et al. \"CacheBlend: Fast large language model serving for RAG with cached knowledge fusion.\" Proceedings of the Twentieth European Conference on Computer Systems. 2025.\n\n\n      [3]. Sun Y, Ye T, Dong L, et al. Rectified Sparse Attention[J]. arXiv preprint arXiv:2506.04108, 2025.\n\n      [4]. Yang X, Chen T, Chen B. APE: Faster and Longer Context-Augmented Generation via Adaptive Parallel Encoding[J]. arXiv preprint arXiv:2502.05431, 2025.\n\nThese methods will further refine the distribution at test time. However, the authors do not discuss about these related work.", "was_revised": true, "final_justification": "My problems have been addressed. Therefore, I increase the score to 5.", "rebuttal": "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.\n\n---\n\n> 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.\n\nWe 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.\n\n---\n\n> 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\n\nWe 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.\n\nWe 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.  \n\n---\n\n> 3. Some previous work [1-4] has already worked on fixing the distribution shift for different kinds of sparse attention at test time\n\n**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:\n\nRegarding [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.\n\nRegarding [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.\n\nWe ran the officially published code for Cacheblend to compare with our method (results are posted below)\n\nRegarding [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.\n\nRegarding [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. \n\nOur 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.\n\nWe 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.\n\n|  | 131K | 65K | 32K | 16K | 8K | 4K | Avg. |\n|---|---|---|---|---|---|---|---|\n| Str.LLM | 27.45 | 18.59 | 30.25 | 38.13 | 60.53 | 90.52 | 44.25 |\n| Cachblend [2] | 0.00 | 0.21 | 0.31 | 1.49 | 24.42 | 96.27 | 20.45 |\n| APE [4] | 26.76 | 43.03 | 53.13 | 67.50 | 77.25 | 93.76 | 60.24 |\n| Str.LLM + Delta | **64.40** | **75.22** | **81.27** | **88.66** | **92.25** | **96.54** | **83.06** |\n\n---\n\n>  1. lacking theoretical grounding.\n\nIn 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 \n\n$\\langle q_i', q_j' \\rangle \n= \\langle R(\\theta_i)q_i, R(\\theta_j)q_j \\rangle\n= \\langle q_i, R(\\theta_j-\\theta_i)q_j \\rangle$\n\nSo 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. \n\n| $\\gamma$ | 2 | 4 | 8 | 16 | 32 | 64 |\n|---|---|---|---|---|---|---|\n| cos(q, q') Avg. | 0.9584$\\pm$0.0082 | 0.9095$\\pm$0.0152 | 0.8592$\\pm$0.0224 | 0.8119$\\pm$0.0283 | 0.7768$\\pm$0.0305 | 0.7488$\\pm$0.0315 |\n\nAlso 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).\n\n---\n\n### References\n\n[5] Acharya, S., Jia, F., & Ginsburg, B. (2024). Star attention: Efficient llm inference over long sequences. *arXiv preprint arXiv:2411.17116*.\n\n---\n\nThank 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."}, {"review_id": "N5ChFVGUVr", "reviewer": "Reviewer_7eBZ", "summary": "This work aims to bridge the gap between attention scores obtained from sparse attention methods and those from full attention during the prefilling stage. The core idea is to introduce a $\\Delta$ matrix that approximates the difference between sparse and full attention scores. To construct this $\\Delta$ matrix, the authors compute full attention for a small subset of queries (e.g., 1/64) and assume that neighboring queries exhibit similar delta values. Based on this assumption, the $\\Delta$ values from the small subset are repeated across neighboring positions to approximate the full matrix.\n\nThe proposed $\\Delta$ attention mechanism adds negligible latency compared to standard sparse attention methods, while providing clear performance improvements.", "questions": "- Do the $\\Delta$ matrices look similar across different inputs? In other words, to what extent is the $\\Delta$ matrix query-dependent versus being a property of the model itself?", "limitations": "Please see Weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The idea of using a small number of full attention computations to correct or enhance sparse attention scores is novel and interesting.\n- The experimental results effectively demonstrate the benefits of the approach.\n- The paper is well-written and easy to follow.\n\n**Weaknesses**\n1. A key assumption in the method is that delta values for neighboring queries are similar. However, this assumption is not empirically validated. It would strengthen the paper if the authors provided an analysis of the actual $\\Delta$ matrix, such as measuring correlations between neighboring delta values.\n2. Such an analysis could also inspire better methods for constructing the approximated $\\Delta$ matrix. For instance, instead of simply duplicating delta values, interpolation techniques might yield more accurate approximations. It's unclear how performance scales with the parameter $\\gamma$ (i.e., the fraction of queries used for full attention). At what $\\gamma$ value does the method match the performance of full attention?", "was_revised": true, "final_justification": "I'd like to keep my positive rating.", "rebuttal": "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. \n\n---\n\n> 1. A key assumption is that delta values for neighboring queries are similar … not empirically validated. … \n\nIf 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. \n\nAs 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.\n\n| $\\gamma$ | 2 | 4 | 8 | 16 | 32 | 64 |\n|---|---|---|---|---|---|---|\n| cos(q, q') Avg. | 0.9584$\\pm$0.0082 | 0.9095$\\pm$0.0152 | 0.8592$\\pm$0.0224 | 0.8119$\\pm$0.0283 | 0.7768$\\pm$0.0305 | 0.7488$\\pm$0.0315 |\n\n---\n\n> 2.1 Interpolation techniques might yield more accurate approximations. \n\nWe 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.  \n\nThe 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)\n\n|  | 131K | 65K | 32K | 16K | 8K | 4K | Avg. |\n|---|---|---|---|---|---|---|---|\n| Str.LLM + Delta | 64.40 | 75.22 | 81.27 | 88.66 | 92.25 | 96.54 | 83.06 |\n| Str.LLM + Delta (smooth) | 65.15 | 75.65 | 81.26 | 88.26 | 92.34 | 96.66 | 83.22 |\n| p-value (all non-qa tasks) | 0.1708 | 0.5185 | 0.3818 | 0.4279 | 0.5782 | 0.0001 | - |\n| p-value (all qa tasks) | 0.766 | 0.2455 | 0.8698 | 1 | 0.5043 | 1 | - |\n\n---\n\n> 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?\n\nIn our submission we have include an ablation in Figure 6a which shows how performance scales as a function of gamma.\n\n---\n\n> Q.1 To what extent is the matrix query-dependent versus being a property of the model itself?\n\nIf 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).\n\nIf 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.\n\nThank you for suggesting this experiment, we will add it to the final version of our work. \n\n| $\\gamma$ | 2 | 4 | 8 | 16 | 32 | 64 |\n|---|---:|---:|---:|---:|---|---:|\n| NIAH/QA Self Avg. | 0.938 | 0.91545 | 0.9043 | 0.89165 | 0.8855 | 0.8774 |\n| NIAH/QA Cross Avg. | 0.1435 | 0.1417 | 0.1448 | 0.1417 | 0.1417 | 0.1425 |\n\n---\n\nThank 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."}, {"review_id": "Kc7caithEP", "reviewer": "Reviewer_1VjR", "summary": "This work proposes $\\Delta$ Attention, a method for mitigating the bias caused by sparse attention. The proposed method computes the residual between full attention and sparse attention on a subset of queries, and subsequently applies them as residuals for all queries under sparse attention. Empirically the proposed method improves performance for several sparse attention methods on 3 datasets.", "questions": "Please see my interpolation comment. Did the authors try alternate interpolation methods?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Interesting new method which improves quality for sparse attention models.\n- Extensive empirical results.\n- Clear presentation.\n\nWeakness:\n- While the experiments span multiple base models and datasets, there is no statistical significance test. Statistical significance tests are useful even for deterministic methods. I'd like to encourage the authors report standard test results such as paired permutation tests.\n- The writeup could benefit from analysis of more sophisticated interpolation methods. In Eq 7 the same correction is applied for contiguous $\\gamma$ rows. But what if we linearly interpolate between corrections in these $\\gamma$ rows, for example?", "was_revised": true, "final_justification": "Updated my score after the new experiments.", "rebuttal": "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.\n\n---\n\n>  There is no statistical significance test. I'd like to encourage the authors report standard test results such as paired permutation tests.\n\nWe 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. \n \n|  | 131K | 65K | 32K | 16K | 8K | 4K |\n|---|---|---|---|---|---|---|\n| Str.LLM (all non qa tasks) | **0.0001** | **0.0001** | **0.0001** | **0.0001** | **0.0001** | **0.0001** |\n| Str.LLM (all qa tasks) | **0.0001** | **0.0001** | **0.0001** | **0.0001** | **0.0001** | 0.4958 |\n| HiP (all non qa tasks) | **0.0001** | **0.0018** | 0.7112 | 0.5018 | 0.8331 | 0.5747 |\n| HiP (all qa tasks) | 0.4918 | 0.7252 | 0.9245 | 0.8076 | 0.5009 | 1 |\n| MInference (all non qa tasks) | **0.0001** | 0.858 | 0.6485 | 0.5116 | 0.8774 | 1 |\n| MInference (all qa tasks) | **0.0004** | 0.8813 | 0.9848 | 0.8777 | 0.499 | 1 |\n\nPlease 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. \n\n|  | 131K | 65K | 32K | 16K | 8K | 4K |\n|---|---|---|---|---|---|---|\n| HiP (rerun) | 68.74 | 82.51 | 89.92 | 94.10 | 94.56 | 96.80 | \n| HiP + Delta (rerun) | 73.71 | 84.89 | 89.39 | 93.86 | 94.43 | 96.31 |\n\n---\n\n> The writeup could benefit from analysis of more sophisticated interpolation methods.\n\nWe 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. \n\n|  | 131K | 65K | 32K | 16K | 8K | 4K | Avg. |\n|---|---|---|---|---|---|---|---|\n| Str.LLM + Delta | 64.40 | 75.22 | 81.27 | 88.66 | 92.25 | 96.54 | 83.06 |\n| Str.LLM + Delta (smooth) | 65.15 | 75.65 | 81.26 | 88.26 | 92.34 | 96.66 | 83.22 |\n| p-value (all non-qa tasks) | 0.1708 | 0.5185 | 0.3818 | 0.4279 | 0.5782 | 0.0001 | - |\n| p-value (all qa tasks) | 0.766 | 0.2455 | 0.8698 | 1 | 0.5043 | 1 | - |\n\n---\n\nThank 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."}, {"review_id": "3SyLFgfv8V", "reviewer": "Reviewer_wJZr", "summary": "- This work proposes a new sparse attention method targeting the computational complexity of self-attetion during the model inference.\n- This method exploits the distribution shift between the full attention and sparse attention, and proposes a delta method to bridge this distribution gap.\n- This method is extensively evaluated on several long context tasks, achieving superior performances than existing methods while keeping sparsity.", "questions": "- i wonder does it requires task-specific tuning for ultra-long contexts. \n- 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, while the proposed method is mostly evaluated on long context benchmarks.", "limitations": "Please refer to the weakness and questions", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# strength\n- The paper is well written and the motivation is clear. the analysis about the distribution shift of attention scores shown in fig 3 is insightful.\n- The performance gains seem significant, while the increased latency is minimum. the ablations about $\\Delta$ and recomputation are comprehensive.\n- As reported, this method could be seamlessly integrated with existing sparse methods.\n# weakness\n- Ablation of $\\gamma$ on down-stream tasks are preferred to be reported (now only ppl). i wonder does it requires task-specific tuning for ultra-long contexts. \n- Correction efficacy diminishes in higher network layers (Appendix Figs. 13-15), which may limit the gains in more complex and reasoning tasks.", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n\n> I wonder does it requires task-specific tuning for ultra-long contexts.\n\nWe 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$.\n\n---\n\n> 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\n\nThank 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.\n\nNote that in this task, the threshold setting in the top row is a similarity threshold for score matching (0.8 is default).\n\n**Table: RepoQA with Qwen3 235B A22B Reasoning Activated**\n\n\nThreshold | 0.0 | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0 | Avg\n-- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | --\nStr.LLM | 73.6 | 64 | 60.6 | 58.8 | 57.6 | 56.8 | 55 | 53 | 50.4 | 44.2 | 35.6 | 55.42\nStr.LLM + Delta | **85.8** | **78** | **73.8** | **72** | **70.6** | **67** | **64.8** | **61.2** | **57.2** | **50.4** | **42.6** | **65.76**\n\n\n---\n\nThank 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."}]

Author rebuttal:

Meta-review: This paper proposes a new sparse attention method to reduce computational complexity of self-attention during the model inference. The proposed method identifies the distribution shift between the full attention and sparse attention as a source of performance degradation, and proposes a delta method to correct this distribution gap. Empirical evaluation on several long context tasks indicate superior performances than baselines while keeping sparsity. Overall, reviewers found this paper well written and with a clear motivation. The paper sheds light on the distribution shift between the full attention and sparse attention which is insightful and useful. The empirical analysis is solid and includes ablation experiments. Some of the weaknesses have been well addressed during the rebuttal stage. I recommend acceptance.
Decision: Accept (poster)