RESA: Bringing Back What Sparse Attention Ignores with Residual Estimation
Authors: Weihao Yang
Hao Huang
Ningke Li
Shihao Wang
Darong Yang
Yanqi Pan
Wen Xia
Shiyi Li
Xiangyu Zou
Venue: ICLR 2026 Poster (2026)
Keywords: Sparse Attention
Attention Redundancy
Low-rank Approximation
Primary area: foundation or frontier models, including LLMs
TL;DR: We propose RESA to compensate the results of sparse attention for a more accurate output.

Abstract: Large Language Models (LLM) have gained significant attention.
    KV cache, stored to avoid quadratic complexity of attention, becomes a bottleneck due to the demands for long-context.
    Sparse attention (SA) has been proposed to address this by only selecting critical KVs for attention, which may degrade model quality in less sparse scenarios.
    To improve quality, rather than selecting more KVs, this paper reveals another perspective by estimating the contributions of remaining KVs, called Residual Estimation. 
    We find that attention logits (before softmax) exhibit substantial redundancy due to its inherent low-rank nature.
    We perform Singular Value Decomposition (SVD) on logits matrix in prefilling and find the spectral dominance of principal singular value and its linearly scaling property with sequence length.
    These imply that increasing sequence length leads to replication-like logits growth with significant redundancy.
    However, it is impossible to perform SVD at each decoding step in practice due to its heavy costs.
    To this end, we propose RESA, a training-free framework compensating SA's output with an estimated low-rank prior of logits.
    RESA introduces (i) a Prior Estimator that derives a prior distribution from a typical query as a rank-1 approximation at the end of prefilling, and (ii) an Online Aggregator that fuses the prior with SA at each decoding step via lightweight scaling and merging.
    Besides, we further show that RESA's effect comes from priors being used as attention bias for knowledge injection.
    Extensive experiments show that without extra overheads, RESA improves model quality by up to 26\% across various tasks with the same KV budget compared to state-of-the-art.
    Moreover, RESA maintains the same quality with up to 33.2\% KV budget reduction and 1.23$\times$ attention throughput improvement.

Published as a conference paper at ICLR 2026
RESA: BRINGING BACK WHAT SPARSE ATTENTION IGNORES WITH RESIDUAL ESTIMATION
Weihao Yang f, Hao Huang', Ningke Li', Shihao Wang', Darong Yang', Yanqi Pan', Wen Xia 1i, Shiyi Li', Xiangyu Zou'
Harbin Institute of Technology, Shenzhen, Pengcheng Laboratory t: weihao. yang mang00@hotmaill com, #: xiawen@hit.ee www.eehhttueuuu....... en
ABSTRACT
Large Language Models (LLM) have gained significant attention. KV cache, stored avoid quadratic complexity of attention, becomes a bottleneck due the demands for long-context. Sparse attention (SA) has been proposed to ad- dress this by only selecting critical KVs for attention, which may degrade model quality in less sparse scenarios. To improve quality, rather than selecting more KVs, this paper reveals another perspective by estimating the contributions of re- maining KVs, called Residual Estimation. We find that attention logits (before softmax) exhibit substantial redundancy due to its inherent low-rank nature. We perform Singular Value Decomposition (SVD) on logits matrix in prefilling and find the spectral dominance of principal singular value and its linearly scaling property with sequence length. These imply that increasing sequence length leads to replication- like logits growth with significant redundancy. However, is impos- sible to perform SVD at each decoding step in practice due to its heavy costs. To this end, we propose RESA, a training- frrei free framework compensating SA's output with an estimated low-rank prior of logits. RESA introduces (i) Prior Estimator that derives prior distribution from typical query as a rank-1 approximation at the end of prefilling, and (ii) an Online Aggregator that fuses the prior with SA each decoding step via lightweight scaling and merging, Besides, we further show that RESA's effect comes from priors being used as attention bias for knowledge injection. Extensive experiments show that without extra overheads, RESA im- proves model quality by up to 26% across various tasks with the same KV budget compared to state-of-the-arts Moreover, RESA maintains the same quality with up to 33.2% KV budget reduction and 1.23x attention throughput improvement.
INTRODUCTION
The success of large language models (LLMs) has brought heavy computational overhead due to the quadratic complexity the attention. KV cache alleviates this by storing intermediate results of Q, K with linear space complexity, thereby avoiding redundant recomputation. However, the grow- ing demand for long-context models leads a rapid expansion of KVs, becoming new bottleneck.
Sparse attention (SA) is proposed to mitigate KV cache bottleneck. By exploiting the inherent spar- sity in attention, SA selects only the highest-scoring KVs for computation. Existing works mainly focus on two perspectives: (1) How to precisely identify the critical KVs? As we cannot globally retrieve attention scores for ideal top-k selection, this leads to the adoption of Approximate Nearest Neighbor (ANN) algorithms to improve selection accuracy. (2) How many critical KVs should be selected? As different attention heads exhibit varying sparsity, this leads to dynamic KV budget allo- cation for each head to avoid excessive resource wastage. However, when facing complex scenarios that attention scores are less sparse, it seems that the only way is to select more KVs to maintain eooource-constrainng
model quality, leading to the gradual loss of SA's advantages, especially vices. We identify the core problem lies in a common assumption of above perspectives, that is only selected KVy can contribute to the final atlention outpul, while unselected KVs contribute nothing.
de-
"Corresponding Author Wen Xia.

---

Published as a conference paper at ICLR 2026
Ideal Attention Full Attention
D Logits
&& Scores
Selected
Logits
Residual Estimation & for Sparse Attention é
Full Attention
Sparse Attention
Accuracy
RESA T AR
KV Budget=8
KV Budget=2
Aprior distribution
Budget- 2
Methods of Sparse Attention
KV position
KV position
KV position
Accuracy: highest
Accuracy: moderate
Accuracy: higher
KV budget (overhead)
Budget: large
Budget: small
Budget: small
Figure 1: Schematic diagram of RESA's effect and comparison between FA, SA and our pro- posed RESA. RESA pushes current SA methods to higher accuracy. It estimates the prior distri- bution for KVs ignored by SA in a lightweight and accurate way for a more accurate output.
We couldn't 't help thinking: even if we don't select more KVs, is there any way we can use the unselected VVs to compensate for the SA output?
Our work introduces the third, orthogomal perspective: How to efficiently and accurately estimate the contribution of remaining KVs without selecting them? We call this process residual estimation. Our motivation is simple, that is there exists significant redundancy in attention calculations, thus the contribution of unselected KVs can be roughly estimated without exact calculation. Specifically, we reveal the fact of redundancy due to the inherent low-rank nature of the attention logits matrix (before softmax), which is upper bounded by the head dimension and independent of sequence length. Taking Ilama3.1 1-BB as example, given the sequence length of 8k, the effective rank of attention logits matrix (E &k x8 is only 128. Our experiments further show that the princi- pal singular value of attention logits across different settings can account for 40% of the total energy, indicating that few ranks can accurately reconstruct the entire attention logits. This reinforces the rationale of residual estimation for reducing redundant calculations, especially in long-context cases.
To this end, we propose RESA (Residual Estimated for Sparse Attention), a training-free framework compensate SA. As shown in Figure 1 RESA can push existing SA methods closer to a more ideal attention mechanism with higher accuracy and less budget. RESA captures low-rank structure during prefilling and estimates unselected KV'' logits (i.e., prior distribution) for sparse decoding. RESA has two modules: the Prior Estimator to determine the logits of remaining KVs, and the Online Aggregator to compensate for sparse attention outputs. To avoid the heavy overhead of online SVD, the Prior Estimator finds representative query to approximate the contribution of principal singular value and precomputes with all keys as prior during prefilling. The Online Aggregator then integrates the estimated residuals with the sparse attention output in a lightweight manner. By rescaling and merging the results in a delta-mannnn manter, the computational complexity maintains the same vanilla SA. These two modules ensure RESA to improve the accuracy of SA without introducing additional overhead. Finally, we explore the reasons for RESA's effectiveness and find that the prior distribution injects knowledge from the remaining KVs by imposing biases to the attention. We further analyze how it can guide possible model optimization at training-time.
In summary, contributions are as follows:
We identify the redundancy of attention logits due its inherent low-rank nature, providing a new perspective to estimate residual ignored by sparse attention for compensation.
We propose RESA, training free framework capturing low-rank structure in prefilling and estimate residual for decoding. RESA uses the Prior Estimator to estimate a prior distribution for residual, and the Online Aggregator merge it with sparse attention lightly.
We further reveal that RESA'S effect comes from the prior being used as attention biases for knowledge injection, which is worth exploring more of its features at training-time.
We conducted various experiments and verify RESA's effects. Given RULER and LongBench benchmark, RESA can improve the accuracy of a single task by up to 26%. Such improvements can be scaled to different context length. RESA also reduces the error of attention scores between full attention and sparse attention by up to 77%. When maintaining the same model quality, RESA can reduce the KV budget by up to 33.2% and improve attention throughput by 1.23x.
2

---

Published as a conference paper at ICLR 2026
2 RELATED WORKS
Long-context Model. Long-context L.IMs have become popular to support complex applications
like CoT Wei et al. (202)). TOT Yao et al. (2023) and GoT GoT Besta et al. (2024). Therefore, existing LLMs usually use Rotary Position Embeddings (RoPE) Su et al. (2024) and YaRN et al. (2024)
to extend their context windows beyond the initial training limits. For example, OpenAl GPT- supports a context window of up to million tokens, Claude offfers a context window of 200K, Gemini 1.5 Pro /Team al. (2024) features a context length in the millions, and KL Team et al. 20025) demonstrates strong performance with a 128K context window.
4. A.peOOpeA
Efficient Attention and Sparse Attention. vL.LM K Kwon al. (2023) uses page to efficiently man- :: [Sahh et (2024) co-design
age the KV cache. FlashAttention series al. (2022): Dao 2024
with hardware to minimize I/O cost for acceleration. Some other methods He & Zhai (2024); HHong
et al. (2024): Jiang et al.] 2 Aminabadi et al. 2022) also overlaps computation and 1/O for efficient inference. For KV selection in sparse attention, StreamingLLM Xiao et al. (2024b) han-
dles long context with attention sinks. TOVA Oren et al. (2024) permanently discard tokens based on the current query. The statical decision on important KV cache leads to performance degrada- tion. H20 Zhang et al. (2023) and FastGen Ge et al. (2024) uses the historical attention scores and sophisticated strategy to identify the important KV. SparQ Ribar et al. (2024), infiniGen Lee et al. (2024), infLLM Xiao et al. (2024a) and IMPRESS Chen et al. (2025a) maintain all KV and calculate approximate attention scores for selection. PSA Zhou et al. (2025) and Twilight Lin et al. (2025) set the threshold of accumulated attention scores dynamically decide KV budget. Other methods like magicpig Chen et al. (2025b) performs token-level LSH- -bsed sampling to select K.V.
BACKGROUND AND MOTIVATION
3.1 SPARSE ATTENTION WITH KV CACHE
Given matrices: Q E 14 K E R/ xd and V E Rd where las 4xv, d denotes the sequence length of query, key/value, and head dimension respectively. The attention can be written as
M = K /vd,
= softmax (M) E RR OF (S- V) E R4xxd
(I)
where M, are called attention logit and score, respectively. St,, reflects the importance between i- th and j-th token. The process of LLM inference is split into prefilling and decoding stages, where prefilling takes user requests as tokens generate the first token, and decoding takes the latest token to generate new tokens step-by-step. Note that during the decoding stage, the K, V will be appended by newly generated key value states. Due the huge computational cost, Sparse Attention (SA) lects only critical K Vs according to given budgets. Specifically, common SA method partitions all KVs into blocks and selects KVs at the block level. Each block is represented by compact metadata (e.g.. bounding cuboid estimation). Therefore, block-level relevance is approximated by dot prod- uets between metadata and queries. The top-K relevant blocks are retrieved for SA computation. Our paper focuses on the SA methods applying in decoding stage.
3.2 MOTIVATION ON RESIDUAL ESTIMATION
The residual used correct SA requires a prior logit distribution assigned to the positions that are not selected by SA. Fortunately, the prior distribution can be approximated without obtaining actual Ks, which is supported by both theoretical analysis and experimental observations.
Analysis 1: Low-Rank Basis of Attention Logits Matrix. Previous studies Singhania et al. 2024 Bhojanapalli et al.] (2020); Sanyal et al. (2024) suggest that the attention logit matrix M = Q K" kT/Vd, M E xle, exhibits an inherent low-rank structure. Specifically, the minimal dimension of Q, K is the head dimension d, thus the effective rank of M is upper bounded by d (c.g., 128), which is much smaller than the sequence length l or 4eu (c.g., 8k). This strongly indicates that as the sequence length increases, the full attention map still lies in much smaller subspace, implying substantial redundancy in the original attention computation.
Observation 1: Dominance of the Principal Singular Value in Attention Logits Matrix. To further observe the low-rank structure, we conducted singular value decomposition (SVD) of atten- tion logits matrices across different layers, heads and sequence lengths, which can be formulated as
3

---

Published as a conference paper at ICLR 2026
Layer 15, Head 15
Layer
1.0
0.6
15000
head
Cumsuu Ratio
Layer Index
10
Singular Value
10000
head 16
head 24
0.5
0.4
5000
0.0
0.2
0
30
60
90
120
0
20 Index
500
1000
1500
2000
Ranks
Seq Length
(a) Accumulate ratio of singular (b) The ratio of principal singular
(c) Linear scaling of singular values with different context length.
values with various context length. value across layers and heads.
Figure 2: Llama-3.1-8B's redundancy in attention calculations from low rank perspective. (a) shows the energy contribution of singular values, whose sparsity remains nearly constant across different context lengths. (b) further shows the percentage of the total energy of the main singular values across layers and heads, which remains stable 40%-50% (c) shows that the size of the main singular values increases almost linearly with context length.
M = USVT. We first observed the obvious dominance of the principal singular value, shown in Vigure[(a) a). We then observed this phenomenon across layers and heads, and a consistent pattern emerges: the principal singular value alone almost accounts for 40%-50% of the total sum of singu- lar values, as shown in Figure (b). Intuitively, this implies that coarse approximation of attention logits matrices can be reconstructed with very few ranks, and the first rank contributes almost half of the basic global pattern between different queries and keys.
Observation 2: Linear Scaling of the Principal Singular Value with Sequence Length. As illustrated in Figure [ic), we find that the principal singular value grows approximately linearly with the sequence length lRv- Intuitively, this scaling behavior indicates that as more tokens are introduced, the dominant global structure simply amplifies without fundamentally altering its ori- entation. In other words, with the expansion sequence length, the logit matrix expands a replication-like manner. For example, given matrix Mi E R with sequence length L, when sequence length grows to 2L, the corresponding logit matrix M2 E 221x22 can be approximated as M M1 Mi
M2
which implies the main structure of attention logits is persistent and predictable.
M
Beyond Sparsity: A Low-Rank Perspective for Compensating Sparse Attention. The above analysis and observations reveal the significant low-rank nature of attention logits and its replication- like expansion pattern. Therefore, attention inherently has a lot of redundant calculations and can be approximated by low-rank structures. However, most current efficient attention methods primarily rely on sparsity approximate precise attention logits (i.e., sparse attention), selecting top-k logits and treating remaining KVs as zero contributions. Indeed, sparsity can capture salient fine-grained features more accurately, but it ignores the global low-rank structure of the attention logits. The core significance of our work lies fully combining these two different perspectives. They are mutually exclusive but complementary: sparse approximations exploit fine-grained importance, whereas low- lank approximations preserve global structure of attention. Together, they provide an opportunity approximate the full attention logits more accurately.
Main Challenges. However, directly extracting singular values and vectors via online SVD is com- putationally prohibitive during inference. Thus the key challenge is design lightweight and curate estimators of the dominant rank structure without explicit decomposition. Addressing this challenge is central to bridging the gap between theoretical low-rank properties and practical esti- mation methods, which leads to our method Residual Estimation for Sparse Attention (RESA).
4 METHODOLOGGY
4.1 RESA OVERVIEW
General Framework of RESA. As shown in Figure Bia), RESA adds a new computational branch to the vanilla SA process. RESA mainly consists of two submodules, the Prior Estimator deter- mines a prior distribution of attention logits and calculates its corresponding O Ests and the Online Aggregator combine the priors and SA's result with scaling factors get accurate output.
4

---

Published as a conference paper at ICLR 2026
Prefill stage
Decode stage
typical 4
Prior Estimator
Estimated/RR cal Logits(Scores)
k4
v1
v2
v3
v
Full KV Cache
Select& Attention
Vanilla SA Output
kI-5
v1-5
prior distribution
bias
0 Est
(from SA) Online Aggregator
① Prior Estimator
Online Aggregator merging
Prior Distribution
RESA Output
v1 from SA)
merging
0
RESA
f(a OEse
(a) Overview of RESA framework.
(b) Workflow RESA'S submodules.
Figure 3: RESA framework and the workflow of its sub-modules. (a) shows how RESA compen- sates SA with two sub-modules: The Prior Estimator lightly estimate the prior distribution, and then the Online Aggregator merges it with the result of SA. (b) shows the details of two sub-modules. The Prior Estimator uses typical q to estimate prior distribution at the end of prefilling. The Online Aggregator uses two scaling factors a, B and reuses results Estimator for lightweight merging.
Layer 10, Head 10, Token 1000
Layer 8, Head 8
Layer 16, Head 16
Logit
0-
1.000
Cosine
Layer 20, Head 20, Token 2000
Logit
0.995
20
1000
2000
1000
2000
1000
2000
4000
Seq Length
Seq Length
Time step
(a) The historical logits of randomly selected tokens.
(b) The cosine between D and no K"
Figure 4: The phenomenon that historical logits are concentrated around the mean and the cosine between a un and yo This indicates that PoK" can be used as a very lightweight and accurate approximation of the first rank's contribution.
Note that RESA does not focus specific sparse attention algorithms or system optimizations. As general framework, RESA mainly contributes to how to enhance different sparse attention methods in lightweight but effective way.
4.2 PRIOR ESTIMATOR: RANK-1 PRIOR LOGITS APPROXIMATION
Goal, Due to the heavy cost of SVD, we can not apply it at each decoding step. so it is difficult directly estimate the contribution of different ranks. Considering this, we simplify the problem and only estimate the contribution of the principal singular value, which can already provide a meaningful prior. Thus, our goal to accurately approximate the contribution of principal SVD component, and (ii) efficiently calculate the corresponding output Ogst of the prior.
Approximating the Contribution of Principal SVD component. Our estimation method is
"un1,iyi POK"" .q.KT = PQKTT + (g. -M 8, (g. pQ)(K - pk)
where qi, denote the i-th query and all Key caches (fky at current decoding step. #Q: Px denote the mean of previous queries and keys, 0141, denotes the first rank's contribution of qs. which is called the principal SVD component. 8, denotes the error between true and estimated logits. Our estimation consists of a prior term (approximation to rank-l) and a bias term. For the prior term "Q it represents the mean of historical logits, which aligns closely with the principal SVD component o UI.,. Given the true logits matrix M, the i-th row of it is M,.- 9.KT, our prior Hoo"" ( E ²T = E'_ M., = M, representing the mean value across the entire prefilling attention logits for all Ks. Using this as the prior is because that we observed the historical logits of each token (i.e., a column of logits matrix) exhibit a concentrated structure: these logits mostly revolve around their mean logit with relative small fluctuations,
shown in Figure 4fa). Thus, we can represent the i-th row of logits matrix as M,,- = M + e;, where e; is the small fluctuations of i-th row. This leads to the rank-1 spike phenomenon in attention logits matrix, thus
5

---

Published as a conference paper at ICLR 2026
the mean of rows M (i.e., our prior P²K") is almost aligning with the principal SVD component. In Figure 4b), we show the cosine similarity between duu1 and pak", which is very close to 1 and proves the effectiveness. We further use a bias term (q - pq) . to align the mean of true logits qi K" and the prior, avoiding the distortions for the following Aggregation. Considering softmax very sensitive to the relative magnitude of logits, this bias eliminates global shifts when aggregating with logits selected by SA, which is crucial to avoid systematic distortions of final output. More detailed discussions can be found in Appendix.
Efficient Computation of Prior. An important property of our estimation is that the computation of prior distribution μlQ K" 2 is independently of the query index i, indicating can be pre-computed once, rather than recomputed each decoding step. As shown in Figure (b),, specifically, at the end of prefilling, we compute the prior distribution, apply softmax to it, and directly use to weight all Vs output Est- This is equivalent to appending changing the context length from I to L+ 1. Since prefilling typically already has very large I., the increased overhead is negligible compared to the overall cost, yet provides the necessary prior to all subsequent decoding steps. Note that in practice, we use the chunked prefill Agrawal et al. (2023) to avoid OOM and merge the calculation of prior into the last chunk to fully utilize computing power, indicating that only the size of the last chunk is increased by 1.
extra query the end of the prefilling, that is
4.3 ONLINE AGGREGATOR: RESCALING AND DELTA MERGING
Naive Aggregation. For each decoding step, the Aggregator aims to merge the priors and SA for a more accurate output. An intuitive way is to use the logits obtained by SA to replace the logits the corresponding position of priors. Given prior logits and the corresponding scores P,S E R BxHX X
where B, H, L denotes batch size, the number of heads and the sequence length, respectively. All real logits computed by SA is denoted as PSA e R [x and their indices construct set I S {I...., L. Thus, the aggregated logits P' and the corresponding output O ORESA can be written as
PSA JEI, P
P
S' softmax P'). O ORESA = VS).
(3)
j$I,
This naive way requires O(L) complexity, which is the same FA and loses advantages of SA. Thus, we need to derive an efficient aggregation with O(Z)) complexity, which is the same as SA.
Online Aggregation: Rescale. Let Z exp(P,) be the exponential sum of prior, and Z' E, EP)((P)) be the new one. Z can be pre-calculated only once in the prefilling stage with the prior calculation, avoiding online heavy costs. For Z', the only difference between
to replace Ejez exp(P,) with Ejez (xp(P which only requires Ó((Z) complexity (like SA) without any matrix multiplications. Thus Z' can be obtained online lightly. Given Z and Z', the rescale step uses two scaling factors to align the prior and SA's scores with s", which can be written as
aa Sr.S II 5 sy= 55=88 B. 3 EIT,
Z z
ΣjEz exp (XP(
S softmax(PPA) SSSA,
B
(4)
Z'
Online Aggregation: Delta Merging, According to Eq 4
rewrite the ORESA in Eq 3 as
OreSA= = =Eez a Sy +V+ B- SSA y.. To avoid online O(L) complexity and reuse the
result of Estimator Est. O ORESA can be written a delta-update manner, which expressed as
O RESA
Eas,v, Eas,v, Vj
Σ JEI
3SSAV; a O Est + (B-Sf* S - 3r)Vzz Vz, (5)
JEI
where Vz the V caches corresponding to the indices in the set I. Eq 5 maintains the same com-
plexity O(IZ)) as SA. The above process can is summarized in Figure 3 b). Note that for numerical stability, we use the log-sum-exp tricks and the shifted logit tricks (minus the largest logit) to avoid overflow, which widely used in previous works Dao et al. 2022 Dao 2024)
Shah et al. 2024).
Hyper-parameter for Controlling the Importance of Priors. To cope with the changing task scenarios. we further introduce hyperparameter X [0. 1] to control the importance of the prior. Specifically, we use a' = X a to replace the a in Eq 5 When À equals to 0, RESA degenerates to
the vanilla SA. More details can be found in our experiments 5..

---

Published as a conference paper at ICLR 2026
Table 1: Model quality verification of RULER benchmark on Llama-3.1-8B,
L.ama-3.2-3BB-
128k, Mistral-7B-512k and LWM-Text-7B- 7B--2KK models. For each SA method, we compare it with its
version (+RESA). RESA can improve accuracy by up to 26% for a single task.
Methods
Model
Niah2
Niah3
MK2
MK3
MV
MQ
QA
Queat(-RESA)
Llama-3,1888-128,
100(100)
99(100)
87(91)
24(40)
89.5(96)
97(98)
86(87)
ArkVale(+REEA.
3.amm-3.1-8811222
100(100)
90(93)
27(43)
88(94)
97.25(99)
86(87)
Ideal-Topke Tap -RESA)
1.ama-211881-12M6.
100()00)
100 100)
100(100)
98(100)
98.5(99.75)
99.25(99.75)
86(87)
Ques((+RESA)
Llamma-3.2-388-1
3.2-318-128
91(92)
58,84)
74(82)
3(6)
71.75(84.25)
83,25(933
59x62)
ArkVale(+RESA.
89(89)
84(97)
78(79)
3(6)
77(88)
90.5(94)
62(62)
Mtall-Top(-RRSA.
-.ama-3.2-3--122..
95(95)
100 100)
99(99)
(1(92)
92. 92.75(9T)
97.75(98.55
63(63)
Ques((+RESA)
Mistral-7B-312k
91X99)
71(93)
92(93)
9(27)
71(74)
94(94.5)
83(87)
AtVaalo(+REAA)
Mistral-7B-511k
100/100)
95:99)
96(96)
28(44)
80.5180,75)
97.5:98)
87(92)
(op((EAAA)
Mistral-7B-S12k
1000100)
100(100)
100/100)
99(99)
93.75(94)
100X100)
90X90)
Quet(+REEA)
LeM--ext-7B--1NA
73(74)
89(90)
25(26)
2(3)
75,5(82)
76184)
28(30)
Ark VaValle+REEAA
75(75)
90,90)
29(30)
2(3)
80183.25)
74.75(89.25)
30X30)
TopK(-RES))
TNM--Text-..118k
98(98)
91(91)
93(94)
50(70)
83(83)
88.5(92.5)
41(41)
4.4 PRIOR DISTRIBUTION IMPOSES ATTENTION BIAS FOR KNOWLEDGE INJECTION
The core of RESA is to determine the prior distribution, which can be viewed as a bias in the at- tention mechanism. This bias manifests in two ways: (1) The prior distribution directly influences the attention scores. Specifically, in the softmax calculation, the prior distribution becomes part of the denominator. This adjustment allows the prior distribution to shape the distribution of attention scores. (2) The weighted sum of V caches determined by the prior distribution will be aggregated to the final attention output (like RESA's compensation for sparse attention). Thus, the prior distribu- tion serves to adjust both the attention scores and the final output.
Diversity of Prior's Effects. Beyond RESA'S training-free compensation for SA, the prior dis- tribution can be also leveraged for additional purposes at training time. Case 1: OpenAl's recent open-source model GPT-oss introduces a Iearnable bias for sparse attention layers, which is dis- carded after the softmax computation. This can be interpreted as the model is learning an implicit prior distribution during training, effectively marking certain positions as irrelevant by setting their output to zero, thus guiding the model to focus model quality. Case 2: Previous work (un et al. (0024) introduces a learnable K and V to reduce extreme outliers in LLM activations, which can be explained as learning implicit prior that evenly spreads the impact of large outliers across all positions, mitigating their disproportionate influence.
more meaningful positions and improving the
EVALUATION
5.1 EXPERIMENTAL SETUP
Testbed. Our experiments were conducted on a host equipped with a single 3090 GPU with 24GB HBM, an Intel(R) Xeon(R) Gold 5218 CPU @ 2.30GHz, and 128GB of DRAM. The GPU and CPU are connected via PCIe 4, which provides the bandwidth of 32GB/s.
Models. Our evaluated models include Llama-3.1 Grattafiori al. 2024 with 128k context length, Llama-3.2233 Grattafiori et al. (2024) with 128k context length, Mistral-7B Jiang et al. (202)) with 512k context length and LWM-Text-7B Liu et al. (2025) with 128k context context We use two Llama models with different sizes to show the generalization across model size, then use Mistral and LWM model show the generalization across model types. These models include both Melti-Head Attention (MHA) and Group-Query Attention (GQA).
Benchmark. Our evaluations are tested on the LongBench Bai et al. (024) and RULER Hsieh al. (024). LongBench is famous benchmark built on diverse real-world long-context tasks, covering task categories like document QA, summarization, and few-shot learning. Its primary goal is to evaluate how well models can utilize extended contexts in practical applications. RULER is another famous benchmark that generates synthetic examples of 13 tasks to evaluate long contextt language models. RULER can configure task complexity in friendly and flexible way, thus more settings can be configured to evaluate the effect of RESA. Together, they provide complementary perspectives: I Leng tests utility in practice, whereas RULER examines capability in controlled settings.
7

---

Published as a conference paper at ICLR 2026
Table 2: Model quality verification of Longbench benchmark on Llama-3.1-8B-128k Llama-3.2-
3B- 128k, Mistral-7B-512K and LWM--eext-7--1288 For each SA method, we compare it with its RESA-enhanced version (+RESA). RESA improves accuracy by up to 8.22% for single task.
Methods
Model
2WMQA
Qas
MFQA
GR
MN
PR
Quest(+ REES)) Llama-3.1888-128.
3.2666.36)
10.88(10.98)
22.43(22.588
24.55(24.95)
21.68/2168)
98. 38.39(98.39)
Llama-311-8--188.
5.31(6.52)
10.25()0.36)
24.59/24.65) 21.65(22.06)
21(2166)
89.19(94.84)
Ideal TopK(+RESA)
3-mm-3.1-88B-125-
5.23(6)
10.59(10.99)
20,89(23.23)
24.91(25.11)
21,1(21))
98.79(98.399
Quest+ (EESA)
Llama-3.2-31-1222
15.82(17.77)
34.01(34,28)
23.7(23.91) 49.49149.78)
20.53/20.71)
90.86(900977)
ArVVale(-RESA)
Lamm-3.2-39--1255
36.17(36.57) 15.96(16.23)
49.49(51.33)
22.75(23.23)
20.8(21.16)
85.93887.63)
11mu--32-3B-1222
20.34(20.64)
35 35.34(36.32)
50.62(50.8)
23.37(24.63)
20.82(20.93)
91A(9144)
QJest(-RESA)
Mistral-7B-512k
22.41(34063)
10.6(10.79)
32.48(38.56)
19.97(20.07)
19.56(19.76)
T00X
Ad\aalo(-REA))
-Bstra
24.9127.18)
80.111
20.43(20.64) 33.89(38.54)
19.6(19.67)
100:100)
Ideal (op((RRSA)
Mistral-7B-S12k
27.13(30.3)
11.27
33.28(36.91)
20.06/20.17)
20.67(20.67)
100(100)
Ques(=REEA)
LWM--Text-BB-IAE
3.67(4.08)
7.91(8.89)
(2.8912.89)
18 (3.888))))7)
(0.03(12.55)
3.76/9,77)
ArkYale(-RESA)
LWM--1ext-B--125
3.79(4.23)
7.14(8.65)
13.19(13.54)
19.34(19.42)
10.2(12.38)
3.76(8.26)
(-RK() LWWM-Text-BB-12S.
4.06(4.48)
8.24(10.05)
13.95(14.82)
18.49(19.66)
12.44(12.8)
10.6(12.68)
Compared Methods. We first compare RESA with Quest Tang et al. (2024), Ark Vale Chen et al. (2024), and Ideal Top-K. Quest and Vrle are popular SA methods that take into account both system efficiency and accuracy in identifying critical KV pages. Ideal Top-K is a token-grained SA method, which identifies the most important i KVs and can be considered as the theoretical upper bound. We then show how KV budgets are reduced with RESA and adopt to A Feng et al. (2024) and PSA Zhou et al. (205)). which automatically determine KV budget for each head.
Additional Configuration. Due to the limited GPU memory, we use chunked prefill to avoid out- of-memory (OOM) error. Specifically, the chunk size is 1024. When given a 16K length input, it will be split into 16 chunks and perform prefill 16 times. For the KV cache layour, we follow existing works [i et al. (2024); [Chen et al. (2025b); Tang et al. (2024); Xiao et al. (2024a) to use the first 4 tokens (initial token) and the last 64 tokens (local token) as fixed budget. Note that unlike previous works Chen et al. (2024): Tang et al. (2024); Chen et al. 2025b) preserve certain layers as full attention,
sparse attention for all layers.
5.2 ACCURACY IMPROVEMENT
Evaluation. We conducted various experiments LongBench and RULER to show generalization capability of RESA. Results are shown in Table[]and T We only show the result of the budget 2.5% under 8K context. More results can be found in the appendix. RESA improves accuracy of single task by up to 16%, 26%, 22%, 20% for four models on RULER and 5.65%. 1.95%. 8.22%, 6.01% LongBench, respectively. Ideal-Topk has the smallest improvement because it is already very close to the full attention. We further show RESA's improvement with different context length in Figure 5ja). Generally speaking, the longer the context, the larger the improvement brought by RESA. This is mainly because the longer the context, the more redundant calculations are in the attention, which can be effectively captured by RESA. Note that tasks in LongBench are real-world tasks whose length cannot be controlled. Thus we mainly use RULER for more analysis.
Deeper Relationship between RESA's Low-rank Prior and ROPE. We further delve into un- derstanding the effectiveness of RESA. We visualized the typical query μQ and keys μu as shown in Figure (()). Empirically, the high-frequency channels are almost zero because they are canceled out when averaged across sequence, leaving only the few-frequency channels intact (like low-pass filter), which indicates that RESA's prior distribution is almost calculated by low- www-frequency signals. Surprisingly, this is consistent with the findings of previous work Barbero et al. (2025), arguing that low www-freuenccy components in RoPE primarily serve as semantic carriers. Thus, RESA's 's prior can be considered global semantic bias that guides the estimation of logits for unselected KVs. For more details about the selection of typical query μo- please refer to the Appendix.
5.3 ERROR ANALYSIS
The Error of Attention Scores between FA and SA (w/ and w/o RESA). Take Quest as an exam- ple, Figure shows the averaged error of all layers. For almost all heads, compared to vanilla SA, RESA enhanced version can reduce the error about 55%.70%. This is because the prior provides contributions of unselected KVs, which is more accurate than directly setting them to zero
8

---

Published as a conference paper at ICLR 2026
Nish2
Niah3
Layer 8, Head 8: Ho
Score
95-
100
Value
2.5
low frequency.
high frequency
Quest
80
Quest
0.0
M/A
85
Questi RESA
Quest+
-2.5
MV
MQ
Layer 8, Head 8: Py
100
Score
90
Value
low frequency
high Erequency
80
Quest
Quest
70
Onestt RESA
Ouest+RESA
10
5000
10000
15000
5000
10000
15000
40
80
100
120
Soq Length
Seg Length
Head dim
(a) Accuracy of tasks under various context length.
(b) The mean of all queries μio and all keys juc.
Figure 5: Improvement of RESA with various context length and the visualization of µo and
ja.- (a) shows that the longer the context, the greater the improvement brought by RESA. (b) shows the specific value of bio and μиk. Their high-frequency channels are almost cancelled out, which indicates RESA's low-rank prior mainly constructed by low-frequency signals in RoPE.
Layer 15, Head 15
Layer 15, Head
0.4
Quest Quest RESA
0.8
Delta
0.5
0.2
0.0
0.2
-2.5
-0.1
0.0
0.4
10
2 A
16
3
10
12
26 28
30
200
400
20
40
60
80
Head ID
Inference step
Lag
(a) The error of attention scores.
(b) The error of attention logits.
Figure 6: Error Analysis of attention scores and logits. (a) shows the layers' average error be-
tween FA's attention scores and SA's scores. RESA reduce the error significantly. (b) shows the error between real and estimated logits. The left one shows obvious mean reversion property. The right one plots the autocorrelation function (ACF) of it, revealing temporal dependencies or periodicity.
The Error between RESA's Estimated Logits and Real Logits. According to the Eq the error can be written as E = (g: #Q) (K - =xx)" Figure b visualizes the error at each inference reversion property. Thus we consider it time series data and further examine its temporal dependency with autocorrelation function (ACF). We plot the ACF values over different lags, where the blue bars indicate the correlation coefficients and the shaded region marks the 95% confidence interval under the null hypothesis of white noise. A significant spike at a given lag suggests strong linear dependence between the series and its lagged version. This suggests that the sequence is not independently distributed, but instead retains substantial temporal structure that worth future exploring. More details can refer to the appendix.
step, we find an obvious
5.4 HYPER-PARE PARAMETER TUNING
We find two patterns how hyper-parameter À affects accuracy. Firstly, for most retrieval tasks, the accuracy increases as À increases, as shown in Figure (Ja) left. We guess that in this type of task, the prior may help eliminate incorrect candidates, thereby improving model's confidence of retrieval results. For the second case, mainly in summary or comprehension tasks, the accuracy first increases slightly and then drops rapidly as X increases, as shown Figure 7 right. We guess that this type of task, the prior may interfere model's understanding of the context, through intrinsic parameter knowledge. A typical example is the CWE task in RULER, where the model outputs the most common words of training corpus rather than context.
it can only answer
5.5 EFFICIENCY ANALYSIS
KV Budget Reduction and Throughput Improvements. We limit the accuracy loss within 2% and see how RESA can reduce the KV budget and improve throughput. We use PSA and Ada-KV to determine the KV budget, results are shown in Figure (Tb) left side. The first three clusters of bars represent PSA, while the remaining represent Ada-KV. For a single task. RESA can further reduce the KV budget by up to 33.2% and 28.7%, respectively. Figure (b) right side shows the attention throughput of corresponding tasks, which achieve up to 1.23x and 1.16x improvement compared to PSA and Ada-KV, V, and 2, x and 2.49 improvement compared vanilla attention.

---

Published as a conference paper at ICLR 2026
wo RESA
w/ RESA
85
75
Ratio
0.25
80
baseline
baseline RESA
75
RESA
0,00
MK
VT
MK
Q
MK3 Q*
VT
MK3Q
QA
0.0
0.5
1.0
0.0
0.5
1.0
2.
Task
Task
(a) Two patterns of how À affects accuracy.
(b) Efficiency improvement of PSA and Ada-KV.
Figure 7: Hyper-parameter the prior (controlled by A) can be beneficial detrimental in different tasks. (b) shows that RESA can achieve a smaller budget and higher attention throughput.
tuning and efficiency improvement- (a) shows that the importance of
Table 3: The layer-wise prefilling latency (ms) of RESA using Llama-3.1-68 under varying context
length. We demonstrate in two ways: the impact on the last chunk and the entire prefilling process.
Measured ways
The last chunk of prefiling
The entire process of prefilling
context length
8k
16k
32k
64k
1281.
8k
lók
32k
64k
128k
w/o RESA
6.8
13.3
25
48.7
96
27.3
106.3
399.8
1554.8
6140.4
w/ RESA
7.3
14
26.2
51.1
100.6
27.8
106.9
400.8
1556.7
6143.8
overhend ratio
7.35%
5.26%
4.80%
4.93%
4.79%
1.83%
0.56%
0.25%
0.12%
0.06%
Analysis of Extra Overheads of Prefilling. The extra overhead of prefilling mainly comes from the prior estimation, which is measured by comparing the time (w/ and w/o RESA) of the last chunk and the entire prefilling. Given chunk size 1024 and the varying context length from 8k to I 128k, the layer-wise latency (ms) of the last chunk and the entire prefilling of Llama-3.1-8 is shown in Table 3] with each test runs 100 times and averaged. We can that the ratio of extra overhead almost gradually decreases and tends to stabilize with the expansion of context length. For the last chunk, the extra overhead is nearly stable at 5%. However, in practice we primarily concern the entire prefilling, whose extra overhead is negligible. This is because the longer the context, the more chunks need be computed, while RESA only applies prior estimation the last chunk.
Analysis of Extra Overhcads of De- coding. The extra overhead of decoding mainly comes from the Online Aggre- gator, which merges the prior and real logits selected by SA. Given the same KV budget 500, we compare the layer- wise latency (ms) of each step w/ and w/o RESA. The results are shown in Table with each test run 100 times and averaged. We can see that the extra overhead is less than 3.13% Tor each step. As the sequence increases, the additional overhead gradually decreases. This is because we keep the computational complexity of Online Aggregator the same as SA and all the extra computations of the Online Aggregator are lightweight, element-wise multiplication or addition, without any matrix multiplication.
Table 4: The wise decoding latency (ms) of RESA
using -..ma-..--8----.. 128k under varying context length.
context length w/o RESA w/ RESA extra overhead ratio
8k
I6k
24k
32k
1.92
2.81
3.68
4.28
1.98
2.89
3.77
4.38
3.13%
2.85%
2.45%
2.34%
Analysis of Extra Overheads of Memory. For specific layer, the extra memory overhead mainly consists of four parts: 1. The prior logits with shape (B, H, L, 1). 2. The output Öest corresponds to the prior with shape (B, H, 1, d). The mean of queries po with shape (B, H, d). 4. The mean of keys μk with shape (B, H, 1, d). B, H, L, d denote batch size, number of head, sequence length and head dim. Considering that the original KV cache size is (B, H. d.. therefore. the ratio of extra memory overhead is: r = 1/2 + 3 of d 128, 256 etc., the extra memory overhead less than 1% and can be ignored.
L. When L is very large, r = 2. Since a common configuration
6 CONCLUSION
In this paper, we propose RESA to enhance current sparse attention to improve model quality and efficiency. RESA fully explores the low-rank nature of attention logits matrix and leverages it to esti- mate a prior distribution for KV caches ignored by sparse attention. RESA then performs lightweight online aggregation to merge the prior and sparse attention's 's output. Experiments show that RESA improves model quality and efficiency compared current sparse attention methods.
10

---

Published as a conference paper at ICLR 2026
7 ACKNOWLEDGMENT
We thank the anonymous reviewers for their constructive suggestions. This research was partly supported by the Major Key Project PCL under Grant PCL2024A05, the National Natural Science Foundation of China under Grants 62472127 and 62502119, and GuangDong Basic and Applied Basic Research Foundation under Grant 2023A15151 10072.
REFERENCES
Introducing the next generation of claude.
URL
claude-3- 3- 3-fmmlyy
Amey Agrawal, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S. Gulavani, and Ra- machandran Ramjee. SARATHI: efficient L.LM inference by piggybacking decodes with chunked prefills. CoRR, abs/2308. 2023.
Reza Yazdani Aminabadi, Samyam Rajbhandari, Ammar Ahmad Awan, Cheng Li, Du Li, Elton Zheng, Olatunji Ruwase, Shaden Smith, Minjia Zhang. Jeff Rasley, and Yuxiong Hc. Deepspeed- inference: Enabling efficient inference transformer models at unprecedented scale. lix Wolf, Sameer Shende, Candace Culhane, Sadaf R. Alam, and Heike Jagode (eds.), SC22: International Conference for High Performance Computing. Networking, Storage and Analysis, Dallas, TX, USA, November 13- 18, 2022, pp. 46:1 46:15. IEEE, 2022.
Fe-
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. Longbench: A bilingual, multitask benchmark for long context understanding. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.). Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2024, Bangkok, Thailand, August 11-16. 2024, pp. 3119-3137, Association for Computational Linguistics, 2024.
Federico Barbero, Alex Vitvitskyi, Christos Perivolaropoulos, Razvan Pascanu, and Petar Velick- ovic. Round and round we go! what makes rotary positional encodings useful? In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025. URL
http::///ppeeeeeeieeeeee net h
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Giani- nazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoe- fler. Graph of thoughts: Solving elaborate problems with large language models. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan (eds.), Shirty-Eighthh AAAI Conference Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference Innovative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2014, February 20-27, 2024, Vancouver, Canada, pp. 17682-17690. AAAT Press, 2024.
Srinadh Bhojanapalli, Chulhee Yun, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. Low-rank bottleneck in multi-head attention models. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 864 873. PMLR, 2020.
Renze Chen, Zhuofeng Wang, Beiquan Cao, Tong Wu, Size Zheng, Xiuhong Li, Xuechao Wei, Shengen Yan, Meng Li, and Yun Liang. Arkvale: Efficient generative LLM inference with re- callable key-value eviction. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.), Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024. Vancouver, BC, Canada, December 10 15, 2024, 2024.
Weijian Chen, Shuibing He, Haoyang Qu, Ruidong Zhang. Siling Yang, Ping Chen, Yi Zheng, Baoxing Huai, and Gang Chen. IMPRESS: An Importance-Infowt Informed Multi-Tiee Tier prefix KV stor- age system for large language model inference. 23rd USENIX Conference on File and Storage Technologies (FAST 25), pp. 187-201, Santa Clara, CA, 2025a. ISBN 978-1-939133-4555

---

Published as a conference paper at ICLR 2026
Zhuoming Chen, Ranajoy Sadhukhan, Zihao Ye, Yang Zhou, Jianyu Zhang, Niklas Nolte, Yuandong Tian, Matthiss Douze, Léon Bottou, Zhihao Jia, and Beidi Chen. Magicpig: LSH sampling for ef- ficient LLM generation. In The Thirteenth International Conference Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025b.
Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024.
Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
Yuan Feng, Junlin Lv, Yukun Cao, Xike Xie, and S. Kevin Zhou. Ada-kv: Optimizing KV cache eviction by adaptive budget allocation for efficient LLM inference. CoRR, abs/2407. 1550, 2024.
Suyu Ge. Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. Model tells you what to discard: Adaptive KV cache compression for llms. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. Open- Review.net, 2024.
Aaron Grattafiori Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, Amy Yang, Angela Fan, and et al. The Ilama 3 herd of models, 2024.
Jiaao He and Jidong Zhai. Fastdecode: High-throughput gpu-efficient LLM serving using heteroge- neous pipelines. CoRR, abs/2403. 1421, 2024.
Ke Hong, Guohao Dai, Jiaming Xu, Qiuli Mao, Xiuhong Li, Jun Liu, Kangdi Chen, Yuhan Dong, and Yu Wang. Flashdecoding++: Faster large language model inference with asynchroniza- tion, flat GEMM optimization, and heuristics. In Phillip B. Gibbons, Gennady Pekhimenko, and Christopher De Sa (eds.). Proceedings of the Seventh Annual Conference on Machine Learning and Systems, MLSys 2024, Santa Clara, CA, USA, May 13-16, 2024, misys.org, 2024.
Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, Shantanu Acharya, Dima Rekesh, Fei Jia, and Boris Ginsburg. RULER: What's 's the real context size of your long-context language models? In First Conference on Language Modeling, 2024.
Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chap- lot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b, 2023.
Huiqiang Jiang, Yucheng Li, Chengruidong Zhang, Qianhui Wu, Xufang Luo, Surin Ahn, Zhenhua Han, Amir Abdi, Dongsheng Li, Chin-Yew Lin, Yuqing Yang, and Lili Qiu. Minference 1.0: Accelerating pre-filling for long-context Ilms via dynamic sparse attention. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Uirich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.). Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurlPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Jason Flinn, Margo Seltzer, Peter Druschel, Antoine Kaufmann, and Jonathan Mace (eds.). Proceedings of the 29th Symposium on Operating Systems Principles, SOSP 2023, Koblenz, Germany, October 23-26, 2023, pp. 1611-26..20 ACM, 2023.
Wonbeom Lee, Jungi Lee, Junghwan Seo, and Jaewoong Sim. InfiniGen: Efficient generative inference of large language models with dynamic KV cache management. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pp. 155-172, Santa Clara, CA, 2024. ISBN 978- 979-119331333-4--3
12

---

Published as a conference paper at ICLR 2026
Yuhong Li, Yingbing Huang, Bowen Yang. Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: LLM knows what you are looking for before generation. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan. Ulrich Pa- quet, Jakub M. Tomczak, and Cheng Zhang (eds.), Advances in Neural Information Processing Systems 38: Annual Conference Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024.
Chaofan Lin, Jiaming Tang, Shuo Yang, Hanshuo Wang, Tian Tang, Boyu Tian, lon Stoica, Song Han, and Mingyu Gao. Twilligh:: Adaptive attention sparsity with hierarchical top-p pruning. CoRR, abs/2502.02770,, 2025.
Hao Liu, Wilson Yan, Matei Zaharia, and Pieter Abbeel. World model on million-length video and language with blockwise ringattention. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025.
OpenAl. GPT technical report. CoRR, abs/23303.08877 2023. doi: 10.48500ARX1222330007774 URL htt::p:::/oo..rrroooeoto 10.
Matanel Oren, Michael Hassid, Yarden Nir, Yossi Adi, and Roy Schwartz. Transformers are multi- state mns. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, EMNLP 2024, Miami, FL. USA, November 12-16, 2024, pp. 2024.
Association for Computational Linguistics,
Bowen Peng, Jeffrey Quesnelle, Honglu Fan, and Enrico Shippole. Yarn: Efficient context win- dow extension of large language models. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024.
Luka Ribar, Ivan Chelombiev, Luke Mudlass-Galleyy Charlie Blake, Carlo Luschi, and Douglas Orr. Sparq attention: Bandwidth-efffcient LLM inference. In Forty-first International Conference Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024.
Sunny Sanyal, Ravid Shwartz-Ziv, Alexandros G. Dimakis, and Sujay Sanghavi. When attention collapses: How degenerate layers in llms enable smaller, stronger models. 2024.
Jay Shah, Ganesh Bikshandi, Ying Zhang, Vijay Thakkar, Pradeep Ramani, and Tri Dao. Flashattention-3: Fast and accurate attention with asynchrony and low-precision. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tom- czak, and Cheng Zhang (eds.), Advances in Neural Information Processing Systems 38: Annual Conference Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024.
Prajwal Singhania, Siddharth Singh, Shwai He, Soheil Feizi, and Abhinav Bhatele. Loki: Low-rank keys for efficient sparse attention. Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.), Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024. Vancouver, BC, Canada, December 10 15, 2024, 2024.
Jianlin Su, Murtadha H. M. Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing. 568:127063 2024.
Mingjie Sun, Xinlei Chen, J. Zico Kolter, and Zhuang Liu. Massive activations in large language models. CoRR, abs/2402.17762,, 2024.
Jiaming Tang, Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikei, and Song Han. QUEST: query-aware sparsity for efficient long-context LLM inference. In Forty-first International Conference Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenRe- view.net, 2024.
Gemini Team, Petko Georgiev. Ving Ian Lei, Ryan Burnell, Libin Bai, Anmol Gulati, and et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context, 2024. URL htl.:tts::// peattps//arxiiee org/ wtw.///////00.ao.//////// 2453.
13

---

Published as a conference paper at ICLR 2026
Kimi Team, Angang Du, Bohong Yin. Bowei Xing. Bowen Qu, and et al. Kimi-vl technical report, 2025. htttpp////ax....o////aa..a/e
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
Chaojun Xiao, Pengle Zhang, Xu Han, Guangxuan Xiao, Yankai Lin, Zhengyan Zhang, Zhiyuan Liu, and Maosong Sun. Inflim: Training- frreeing-frre free long-context extrapolation for Ilms with efficient context memory. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, UIrich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.), Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurlPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024a.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024b.
Shunyu Yao. Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark W. Barrett, Zhangyang Wang, and Beidi Chen. H2O: heavy-hitter oracle for efficient generative inference of large language models. In Al- ice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA. USA. December 10 16, 2023, 2023.
Qihui Zhou, Peiqi Yin, Pengfei Zuo, and James Cheng. Progressive sparse attention: Algorithm and system co-design for efficient attention in LLM serving. CoRR, abs/2503.00392. 2025.
14

---

Published as a conference paper at ICLR 2026
A APPENDIX
A.1 MORE DETAILS OF RESA'S PRIOR LOSITS APPROXIMATION
We provide a clearer and more formal explanation of why our approximation is effective:
The prior PO represents the mean of historical logits, which aligns closely with the principal SVD component. For query qo given the true logit 2; = 9,K", our prior HO E 9:) g){² = E Zi, which represents the mean value across the entire prefilling attention logits. Using this as the prior is because that we observed the historical logits of each token (i.e., a column of attention logits matrix) exhibit a concentrated structure: these logits mostly revolve around their averaged logit with relative small fluctuations (figures will be added in the final version). Thus, the corresponding elements in each row of the attention logits matrix are unlikely to change significantly (if there are significant changes, they will be captured by sparse attention). This leads to the rank-1 1 spike in attention logits. In such cases, when rows of attention logits matrix share strong similarities at most time, their mean vector is almost collinear with the principal singular vector. Thus, KºK" naturally aligns with the principal SVD component. However, note that the mean of q. here assumes that the attention logits matrix has no causal mask (i.e., a complete square matrix). If it has causal mask (i.e., lower triangular square matrix), then the more recent the token, the fewer the historical logits, which is more likely to cause fluctuations for prior estimation.
2. The bias term (% f6--M -2) 1 enforces exact alignment of the true logit mean, which avoids the distortions when merging with sparse attention. Given the true logits q,K", the mean value of q: over all keys is 9ilk. where Pg estimation fO KT, its mean value is pouk which is not aligning with the ground truth. Thus, our proposed bias term (g: - (2)) 1i provides an exact correction such that the estimated logits and the true logits share the same mean. Aligning the mean of prior and ground truth eliminating global bias shifts, which is crucial to avoid systematic distortions of original attention. This is because softmax is very sensitive to relative, not absolute logits, so when aggregating prior and real logits selected by sparse attention, a large global bias will significantly change the distribution of attention scores. Thus, the bias term (a: (Q)) n6 can significantly stabilize the approximation, and it is deterministic, training-free free and can be adaptively adjusted through online query q.
T is the mean of all keys. However, considering our prior
3. The remaining error is a second-order interaction of query/key deviations that is relative small. For qi the error 5 between true logits and our estimated logits is d 9: (pok** + (n: (pp)) . (( = (q: (q)) (K - px)"², which shows that 5 is a bilinear interaction between query deviation and key deviation. Hence, it is second-order relative to the dominant baan- structure. In Figure 6(b) of our paper, we visualized this error term and found some mean-reverting patterns. While there is no definitive hypothesis, we do believe there is a strong correlation between error and RoPE. Specifically, comparing attention logits with and without ROPE, we found that in some heads, RoPE does provide a near- pear-periodic, relatively fixed bias, which we call the positional bias, and its trend closely resembles that of error. However, this is not universally applicable, and quantitative relationship cannot be well established. We are now conducting further investigations to reveal the deeper relationship.
A.2 MORE DETAILS OF SELECTING TYPICAL QUERY PQ
In our paper, po is indeed defined as the average of all queries. First, we need to clarify that such determination actually utilizes the mean of historical logits the prior (historical logits often exhibit mean regression characteristics). Second, for other methods of choosing HQ, such as directly selecting the last query, we experimentally demonstrate that their performance is inferior to the average of the queries. Some results of Llama-3.2-3B is shown in Table A.2
Table 5: The performance of Llama3,2-3 with different typical query µQ-
Llama3.2.3B-8K
Niaha
MK1
MK2
MK3
MV
MQ
ArkVale-mean-q
97
98
79
88
94
ArkValc-last-q
97
82
92.75
Quest-mean-q
84
98
82
84.25
93
Quest-last-q
94
74.5
89,5
15

---

Published as a conference paper at ICLR 2026
A.3 MORE DETAILS OF MOTIVATIONS
First of all, for Llama-3.1-8B, we provide the accumulate ratio of singular values for more layers and heads. Then we provide the ratio of the principal singular value with different context length. Finally, we show the linear scaling property of principal singular values for different layers and heads. It is easy to observe that the logits matrix has a significant low rank property, and the main singular value is very important. This also fully reveals there are substantial redundancy in the logits.
19W5
Casssn Cuscaadae Creena Carae Rab Camn Caneaaate Carastrr Dasan
Mall
Hed
Heal
Read
Hard
Rlad
12
Hest
Real In
H2
Heed II
Hard
Hasd to
Bevi 21
Thed 23
Mead 24
Dlad 25
Hond De
100
100
100
Rado
Reabo
Rado
Bado
Figure 8: The accumulate ratio of singular values for layer 8.
0
-066
0.6
0.6
Layer Index
10.
Layer Index
10
Layer Index
10
0.4
-04
30
0.2
0.2
0.2
0
20
0
20
0
20
Head Index
Head Index
Head Index
(a) Context length 512.
(b) Context length 1024.
(c) Context length 2048.
Figure 9: The ratio of principal singular value under different context length.
Table 6: 1lama3.1-80 quality verification of RULER with Quest under different budget.
11ama3.1-80 1-88b
Niahl
Niah2
Niah?
MKI
MK2
MK3
MV
MQ
VT
CWF
FWR
QAI
QA2
5%
100
100
97
50
97.75
49,9
78.67
88
quest- guesst-5% RESA
100
100
100
100
96
69
99.5
99.5
96.2
49.7
79.67
88
57
quest-7A8 7.5%
100
100
100
100
100
74
98
99
95.2
65.3
78
88
55
quest-7.55 5%
100
100
100
82
99.75
99.5
95.2
65.5
78
88
57
quest- 10%
100
100
100
100
99
86
99
99.25
95.6
73.8
76.67
88
56
quest- 10%+
100
100
100
100
99
91
99.75
99.5
95.6
74.2
76.67
88
57
16

---

Published as a conference paper at ICLR 2026
Inge'
legd D001
legi I9W
legi
leggl Nole
leight
Diuas Canraa Cueees Tads Cuantah Caaanaa Caazzakr Carestatia Camnm
Hell
Med
Howlz
Hadd
Hadd
Fkadd
Ilad 9
Teed 18
Host 13
Head 1s
Host 14
Heat
He
Heed
24
Herd
Head 25
Dlaa 29
New to
100
Rads
Bado
Figure 10: The accumulate ratio of singular values for layer 16.
Iogaa 1:2
kagli IGG4
lagi 1336
kagt. 2N4
lagii 2M0
loppl.302 3012
Cueran Cysmes Bada Caaasaa Cassaadi Cuesa Cuentaal Cacamtal kerm
Bead
Hadd 1
Host
Hous
Heal's
Head
Heads
Head
Haud
Hed
Hed
Hoai to
Beal 21
Hewd tt
Herd3
Hhad h4
Thua 36
Ioae 36
Tlcad to
Toat
100
43
190
S0
100
10c
Aado
Rasio
Hanks
Figure 11: The accumulate ratio of singular values for layer 24.
17

---

Published as a conference paper at ICLR 2026
1hadd
Head
Dlad22
1kad
2006
1993)
2000
11000
1099
966
take
10000
18300
5039
500
Hot 10
Bsad
10900
2006
Heal
Hed 11
1990
Iteal La
80000
5030
2000
7000
incos
X006
2000
5000
5006
Flavd 30
Houd 23
Fias
1006
18300
18900
$300
200
500
Viear Shopla Nake
18000
10000
1890
2300
5000
18000
1931
5000
Figure 12: The ratio of principal singular values for layer 8.
18000
30000
1890)
1990
3060
500
15000
10000
Heat
15000
3kadd
18000
500
15900
18200
5000
2000
Nabe Shalle 10ke
Thoal
13
Hot 14
Iead 1.5
15000
2000
(8200
8000
Jxx0
200
Frad
15000
2000
18000
5000
5000
28000
3000
X00e
20000
Saetbrrin Sheate
18000
Basd 24
Raad35
Hond 26
Read
13200
15000
1839
2000
5000
2000
Stuptar tabe
1992)
1839
15000
2006
10900
5000
100
1000
1540
2000
300
1000
1500
3000
500
3000
1900
2830
260
1030
(500
300
Leugh
Sig
Sog Lengt
Figure 13: The ratio of principal singular values for layer 16.
18

---

Published as a conference paper at ICLR 2026
Thad
Head
Dlad22
Stapts take Stets
2006
1900
13000
15000
1906
1933
18300
10000
JA00
1993)
5000
1030
Shodae Vike
Hot 10
Bsad
15300
15000
2000
13331
1839
1000
3x66
1883)
3300
5030
Susta Nahe
Hhal
Hed 11
2000
Itaal La
1990
19037
Stepla
Flavd 3u
Houd 23
Flad
I0e0d
10000
Yxed
1003)
10000
3000
Suaaka Shopte
Head
1330
183M
10000
2006
3300
5000
1560
1000
Seg
SnyLeggh
Figure 14: The ratio of principal singular values for layer 24.
A.4 MORE DETAILS OF ACCURACY EVALUATION
We show more results of RULER and LoongBench with different configurations.
Table 7: Llama3.1 quality verification of RULER with Arkvale under different budget.
Uamma31180
Niahl
Nlah2
Niah3
MKI
MK2
MK3
MV
MQ
CWE
FWE
QAI
QA2
arkvale-3%
100
100
100
100
97
60
97.5
99.5
97.8
56.1
79
89
54
arkvale SE++REA
100
100
100
100
97
66
98.5
99.5
98.2
56.2
80
89
54
arkvale-..3%
100
100
98
97.2
67.1
78.67
55
ark arkvale-7 7.5%-RAAA
100
100
100
100
98
84
99.75
99.5
98.8
71.4
80.33
89
57
arkvale-10%
100
100
100
100
99
99.25
99.5
98.6
73.6
79.33
89
55
arkvale- 10%-+RESA
100
100
100
100
99
95
99.5
99.5
98.6
73.6
79.33
89
57
Table 8: Llama3.2-33 quality verification of RULER with Quest under different budget.
laaaa32-33 2-3b
Niahi
Niah2
Niah3
MK1
MK2
MK3
MV
MQ
VI
CWE
FWB
QAI
QA2
5%
100
93
94
11
96.25
68.8
25.4
71.67
64
45
quest-5% RSA
100
93
94
99
94
12
92.75
97
68.8
25.4
71.67
64
49
quest.7.55%
95
20
30.9
74
65
quess-7 7.55%
100
95
97
100
95
28
94.5
97.25
68.6
30.9
74
65
48
quest-10%$ 10%
100
95
99
100
96
34
92
97.75
69.6
32
76
63
48
quest- quesi-105
95
94.75
97.75
Table 9: Llama3.2-34 quality verification of RULER with Arkvale under different budget.
laama3 2.3b
Niahl
Niah2
Niah3
MKI
MK2
MK3
MV
MQ
VT
CWF
PWF:
QAI
QA2
arkovale-5g
100
70.4
26.4
69.67
62
49
arkvale-5%% 5EAA
100
94
100
98
94
16
94.5
96.25
70.4
26.4
69.67
63
49
arkvale-7.5%
100
95
100
99
95
26
93
97
71.6
31.8
72.67
49
Mrkvalc-7.5&+RESS
100
100
95
94.25
71.6
31.8
72.67
62
49
arkvall-10%%
100
95
100
100
97
44
93.25
97.75
70.2
31.4
75
63
48
100
100
100
97
94.5
97.75
70.2
31.4
49
19

---

Published as a conference paper at ICLR 2026
Table 10: Llama3. 1-8b quality verification of Longhench with 0-4k context length.
Nama3,
HQA
2WMQA
QAs
MFQA
MN
TQA
quest 58
4.6
6.89
11.15
17.69
26.26
25.37
50
91.82
20.47
93.47
quest+RESA-5%
4.7
6.91
11.49
17.92
26.31
25.73
50
91.89
20.59
97.28
4.14
RKvalo+RESA-19
4.59
7.69
11.28
16.48
26.99
26.24
50
90.1
26.95
92.79
topk-3%
6.71
9.35
12.1
20.96
26.85
25.19
50
95.24
21.61
94.14
topK+RESA-5%%
6.79
9.65
12.1
25.23
Table 11: Llama3.2 22-3b quality verification of Longbench with 0-4k context length.
2-33332-3b
2WMQA
MFQA
GR
MN
quest-5%
35.18
23.74
45.39
47.89
24.97
24.92
45.83
81.9
18.75
88.33
gues-RREAA-11
35.67
23.91
45.39
48.15
25.77
25.36
45.83
81.94
18.75
90.52
arkvalo-39
35.47
25.75
41.51
45.41
26.45
25.37
41.67
82.02
18.75
arkvale-RESA-5%
35.87
29.13
44.09
47.73
26.46
25.51
41.67
82.26
18.75
89.91
10p
38.16
32.6
45.51
47.72
27.73
26.64
45.83
84.02
18.75
96.37
55
43.7
32.81
45.51
48.77
27.73
26.64
45.83
84.02
18.75
97.37
Table 12: Mistral-7B quality verification of Longbench with ()-4k context length.
Mistral-7B
HQA
2WMQA
QAs
MFQA
GR
MN
Tre
TQA
PC
PR
quesi 5%
29.81
36.38
9.8
44.68
23.66
23.46
37.5
95.71
0
100
RESA-55
10.95
23.66
arkvale 558
32.41
32.31
12.19
43.04
22.94
22.92
41.67
94.76
100
urkvale+RESA.-S
40.33
32,83
12.9
47.07
23.28
25.07
41.67
94.76
100
1opk-5%
topk+RESA-5%
33.94
34.23
13.64
44.88
23.5
24.23
41.67
92.86
100
Table 13: LWM-Text-7B quality verification of Longbench with 0-4k context length.
LWM-TTxt-7R
HQA
2WMQA
QAs
MFQA
GR
MN
Tre
TQA
PC
PR
quest-5%
3.16
3.55
6.22
16.07
22.4
16.58
37.5
94.15
0.74
4.02
qUeSE-RESA-5%
4.16
37.5
arkvale-5%
2.98
3.74
7.5
13.19
21.71
13.53
33.33
94.15
0.6
6.01
arkval--RESA-5
4.17
7.64
17.54
21.79
17.59
37.5
96.19
3.47
1opk-55%
3.49
4.19
7.58
15.21
22.34
19.98
41.67
95.24
3.12
7.3
RoPK=RESA-5%
3.52
4.37
8.78
15.67
22.39
19.98
41.67
97.62
3.12
7.3
Table 14: Llama3. 1-8b quality verification Longbench with 8k+ context length.
Damma 1-8b
HQA
2WMQA
QAs
MFQA
GR
MN
Tre
TQA
PC
PR
quest-5%8
5.6
4.12
8.98
23.41
20.41
71.05
94.38
10.24
91.81
quem+RRSA..S 5%%
6.2
4.23
9.75
23,05
23.74
20.81
71.05
94.38
12.86
93.46
arkvalee 5%g
5.35
4.15
10.52
21.88
22.89
19.64
71.05
94.38
12:44
92.65
arkvale+RESAA.S.
71.05
1opk-5%
5.02
4.14
11.69
21.88
23.48
20.32
71.05
94.38
93.42
lopk+RESA..5
5.37
4.95
11.78
22.21
23.61
20.26
71.05
94.38
13.79
93.89
Table 15: 1lama3.2-3b quality verification Longbench with 8k+ context length.
3.23332.3b
HQA
2WMQA
QAs
MFQA
MN
Tre
TQA
PC
PR
quest-51E
26.24
13.97
56.21
85.08
28.09
14.55
36.52
56.88
23.33
21.18
71.05
92.67
3.03
88.71
arkvale-5%%
25.68
14.18
31.06
55.84
23.69
19.92
71.05
90.67
3.03
85.23
arkvalo-REAA-5%
27.17
14.89
35.72
57.88
21.74
90.67
3.03
87.05
topk-5%
31.35
17.33
29.17
57.78
23.13
19.35
71.05
90.67
3.03
$8.48
RooK+RESA-5%
33.26
18.25
31.51
57.78
23.83
21.37
71.05
92.67
3.03
88.48
20

---

Published as a conference paper at ICLR 2026
Table 16: Mistral-7B quality verification of Longbench with 8k+ context length.
Mistral-7B
HQA
2WMQA
QAs
MFQA
TQA
PR
quest-58
29.81
7.31
10.01
65.84
19.88
20.26
78.95
89.3
96.77
30.41
9.75
10.01
63.84
19.92
20.26
78.95
89.3
0.11
96.77
5%
30.19
96.77
uKvalo=RESAA-55
30.19
12.31
10.58
67.02
19.66
20.8
78.95
92.63
96.77
topk-5%
29.77
12.09
9.93
69.78
19.07
20.02
78.95
90.63
96.77
1opK+RESA-5%
35.86
16.03
69.92
90.63
96.77
Table 17:
quality verification of Longbench with 8k+ context length.
LWM Text-7B
HQA
2WMQA
QAs
MFQA
Tre
TQA
PC
PR
quest-55%
0.07
3.77
13.16
0.97
0.24
0.38
8.55
3,77
4.17
13.16
12
1.35
arkvalo-3%
1.34
10.12
4.9
5.27
13.16
AES
1.54
0.42
0.38
10.12
4.95
5.79
13.16
12
2.54
lopk 5%
1.04
0.97
0.39
10.95
4,83
5.47
15.79
12
1.53
A.5 MORE DETAILS OF ERROR ANALYSIS
We show some randomly selected tokens and their error between real logits and the estimated logits given by RESA.
Layer 15, Head
Layer 15, Head 15
Layer Head 15
Layer 15, Head
2.5
ACF
Delta
0.0
ACF
200 400
100
200
400
50
100
Inference stop
Lag
Inference step
Lag
(a) The eтror and AFC of token 1000.
(b) The error and AFC of token 1500.
Layer 15, Head 15
Layer 15, Head 15
Layer 15, Head 15
Layer 15, Head 15
Delta
ACF
0-
-2.5
-1
200
400
50
100
0
200
400
50
100
Inference step
Lag
Inference slep
Lag
(c) The error AFC of token 2000.
(d) The error and AFC token 2500.
Figure 15: The error between real logits and estimated logits (randomly selected tokens.)
21


Reviews:
[{"review_id": "m2FIKDHeAR", "reviewer": "Reviewer_2Wxj", "summary": "This paper addresses a key limitation of Sparse Attention (SA) methods used in LLM inference. While SA accelerates decoding by selecting and computing only a small subset of \"critical\" Key-Value (KV) pairs, it completely ignores the contribution of all unselected KVs, leading to a degradation in model quality.\n\nThe authors propose RESA (Residual Estimation for Sparse Attention), a novel, training-free framework that \"brings back what sparse attention ignores\". Instead of just ignoring the unselected KVs, RESA estimates their collective contribution (the \"residual\") and adds it back to the sparse attention output, thereby improving accuracy.\n\nThe core insight is that the attention logits matrix (pre-softmax $QK^T$) is inherently low-rank. The authors show via Singular Value Decomposition (SVD) that the effective rank is upper-bounded by the head dimension (e.g., 128) regardless of sequence length (e.g., 8k), and that the principal singular value (rank-1) is dominant, accounting for 40-50% of the matrix's energy. SA methods excel at capturing fine-grained sparse peaks but discard this global low-rank structure.", "questions": "1. Prior Estimator Cost: Could you please quantify the one-time wall-clock latency (in ms) of the \"Prior Estimator\" step at the end of prefill? How does this cost scale as sequence length L increases from 8k to 128k?\n\n2. Could you please provide a precise definition for the \"typical query\" $\\mu_Q$? Is it computed as the simple average of all $L$ query vectors in the prefill context? How sensitive is the model's accuracy to this choice (e.g., mean of all queries vs. just the last query)?\n\n3. The paper's motivation (low-rank logits) applies to the prefill stage as well (Figure 2a). While the proposed mechanism is for the decoding stage, could a similar \"residual estimation\" idea be used to accelerate the $O(N^2)$ prefill stage itself?\n\n4. The error of the logit estimation (Fig 6b) shows a clear periodic, mean-reverting pattern. You note this \"temporal structure\" is worth exploring. Do you have a hypothesis for what causes this periodicity? Does it align with any known properties of RoPE or the model architecture?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Originality and Significance: The paper's core idea is highly original. The vast majority of SA research focuses on \"how to select the top-k KVs more accurately or efficiently\". This work introduces a completely orthogonal and complementary perspective: \"how to efficiently account for the $N-k$ KVs that were not selected\". This reframes the problem from simple sparsity to a more robust sparse + low-rank approximation. The resulting improvements are very significant: boosting accuracy (up to 26%) or saving 33.2% of the KV budget for free is a major practical contribution.\n\n2. RESA's effectiveness is demonstrated across multiple models (Llama-3, Mistral, LWM) and multiple challenging long-context benchmarks (RULER, LongBench).", "weaknesses": "Please see Questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LN8LfdsKUY", "reviewer": "Reviewer_WqTC", "summary": "The paper proposes RESA, a training-free residual estimation framework that complements sparse attention by estimating the contributions of the key–value pairs that sparse attention discards. The key insight is that attention logits are strongly low-rank, allowing a rank-1 prior (computed from the mean query and key vectors) to approximate the global structure of attention. During decoding, RESA merges this prior with sparse attention outputs through an rescaling and delta update, keeping computational cost unchanged. Experiments on LongBench and RULER show that RESA can improve task accuracy and reduce KV budget while maintaining comparable performance.", "questions": "1. How is the prior computed when prefilling is chunked? Is the prior accumulated across all chunks, or only computed at the final chunk? Can you quantify the prefill-time overhead relative to standard sparse attention?\n\n2. Have you explored an adaptive λ schedule, for example, using entropy or sparsity of the attention logits as a signal to modulate prior strength dynamically?\n\n3. Can you compare RESA with low-rank inference baselines such as a learned rank-1 bias or lin-attention variant to clarify its novelty relative to existing low-rank approaches?\n\n4. Summarization and comprehension tasks appear to degrade at larger λ. Can you analyze failure cases and propose mitigation strategies beyond manually reducing λ?\n\n5. For numerical stability, since α and β are computed via log-sum-exp normalization, did you observe pathological heads or tokens with extreme α/β? Were any clipping or smoothing techniques applied?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces a simple yet effective approach to compensate for the information loss in sparse attention using a low-rank residual estimation. It is training-free, computationally efficient, and integrates seamlessly with existing sparse attention mechanisms. The empirical results are consistent across different models and benchmarks, demonstrating tangible performance and throughput improvements. The low-rank analysis provides interesting insight into the structure of attention logits, which may inspire future theoretical or practical extensions.", "weaknesses": "1. The theoretical justification is incomplete. The proposed estimator is intuitive and empirically validated but lacks formal analysis or error bounds. Providing theoretical guarantees or conditions for the rank-1 prior to hold would greatly strengthen the claims.\n\n2. The computation of the prior under chunked prefill remains ambiguous. It is unclear whether the prior is aggregated across chunks or derived from the last chunk only, and the paper lacks a detailed runtime breakdown to justify the claimed negligible overhead.\n3. The performance is sensitive to the hyperparameter λ, which controls the influence of the prior. Larger λ values can hurt summarization or comprehension tasks, but there is no guidance on automatic or adaptive tuning strategies.\n4. Some tables contain minor formatting errors and inconsistencies. (Table 7 and Table 8, \"quert\" should be \"quest\")", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RlAFSLy28b", "reviewer": "Reviewer_WmEf", "summary": "This paper presents a novel and well-motivated approach to improving sparse attention (SA) mechanisms by leveraging the low-rank nature of attention logits. The proposed method, RESA, is training-free and introduces a lightweight residual estimation framework that compensates for the contributions of unselected key-value pairs. The idea is innovative and supported by solid theoretical and empirical analysis. However, the evaluation could be strengthened by more comprehensive comparisons and deeper ablations to better understand the method's generality and limitations.", "questions": "See the weaknesses section for details", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper provides a fresh perspective on the redundancy in attention logits due to their inherent low-rank structure, supported by singular value decomposition (SVD) analysis and visualizations. This offers a principled foundation for residual estimation in sparse attention.  \n- RESA is a training-free framework that effectively captures low-rank priors during prefilling and integrates them during decoding via a lightweight online aggregation mechanism. This makes it practical and easy to deploy.  \n- The method demonstrates consistent improvements across multiple models and benchmarks (RULER and LongBench), with significant gains (up to 26% on certain tasks) under the same KV budget.  \n- The authors further interpret RESA’s mechanism as a form of attention bias for knowledge injection, opening up interesting directions for training-time optimizations.", "weaknesses": "1. **Comparison with Recent SA Methods**:  \n   The paper primarily compares against Quest, ArkVale, and an Ideal Top-K baseline. However, several recent and relevant SA methods such as SnapKV, HeadKV, PSA, and Ada-KV are not included in the main evaluation. It would be beneficial to see how RESA performs when integrated with these more recent approaches, especially on the same benchmarks.\n\n2. **Efficiency Evaluation**:  \n   While the method claims to be lightweight, there is no concrete reporting of prefilling time, inference latency, or memory footprint. Including such metrics would help readers better assess the practical overhead of RESA, especially in resource-constrained settings.\n\n3. **Evaluation on Complex Tasks**:  \n   The current experiments focus heavily on retrieval and simple QA tasks. To better demonstrate the robustness of RESA, we suggest evaluating on more challenging benchmarks such as InfiniteBench or complex reasoning tasks from lm-eval, which involve few-shot learning, long-context reasoning, or multi-step inference.\n\n4. **Prefilling Overhead**:  \n   The authors mention that the prior estimation is computed once at the end of prefilling, but the computational and memory cost of this step is not quantified. A brief analysis of the prefilling stage overhead would help clarify the trade-offs.\n\n5. **Ablation Studies**:  \n   Although a hyperparameter \\( \\lambda \\) is introduced to control the prior's influence, more thorough ablations are needed. For instance:  \n   - How does the choice of rank-1 approximation affect performance? Would a higher-rank prior help?  \n   - Are there alternative weighting schemes (e.g., recency-based) that could improve the prior?  \n   - How sensitive are the scaling factors \\( \\alpha \\) and \\( \\beta \\) in Eq. 5?  \n   These experiments would provide deeper insights into the design choices and their impact.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Tv1FFsf41z", "reviewer": "Reviewer_5DL8", "summary": "This paper proposes RESA (Residual Estimation for Sparse Attention), a novel, training-free framework to improve the accuracy of sparse attention (SA) during LLM inference. The authors argue that standard SA methods, which select a small subset of KVs and ignore the rest, suffer from accuracy degradation by effectively zeroing out the contribution of unselected tokens.\n\nRESA's core idea is to *estimate* the contribution of these ignored KVs rather than discarding them. This is motivated by the empirical observation that the attention logit matrix ($QK^T$) is inherently low-rank and is dominated by its principal (rank-1) singular value, which accounts for a significant portion (40-50%) of the total energy.\n\nInstead of performing a costly SVD, RESA proposes a lightweight approximation for this rank-1 component. This approximation is used by a \"Prior Estimator\" to compute a global \"prior output\" ($O_{Est}$) once at the end of the prefill stage. Then, at each decoding step, an \"Online Aggregator\" merges this pre-computed $O_{Est}$ with the output of a standard SA method (e.g., Quest, ArkVale). The paper presents a key algorithmic contribution in the form of a \"delta merging\" formula (Eq 5), which allows this aggregation to be performed in $O(|\\mathcal{I}|)$ time—the same asymptotic complexity as the original SA method—by cleverly rescaling and combining the pre-computed and online components.\n\nExperiments across multiple models (Llama 3.1, Mistral) and benchmarks (RULER, LongBench) demonstrate that RESA consistently improves the accuracy of existing SA methods, or alternatively, allows for a significant reduction in the KV budget (up to 33.2%) while maintaining the same accuracy.", "questions": "1.  Could the authors please provide a derivation or at least a more formal justification for Equation 2? How is the expression $\\mu_{Q}\\cdot K^{T}+(q_{i}-\\mu_{Q})\\cdot\\mu_{K}^{T}$ formally linked to the principal SVD component $\\sigma_{1}u_{1,i}v_{1}^{T}$? \n2.  To clarify the true overhead, what is the measured, per-token wall-clock latency (at the *same* KV budget, e.g., 5%) for a baseline like Quest versus Quest+RESA? This would quantify the constant-factor overhead of the Online Aggregator.\n3.  What is the additional *memory* overhead of RESA? The $O_{Est}$ vector (size $d$) and the prior scores $S$ (size $L$) must be stored for every head and every layer, correct? How does this extra storage compare to the size of the KV cache itself?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.  **Novel and Valuable Perspective:** The core idea of \"residual estimation\" is a significant conceptual strength. It reframes the problem of information loss in SA and provides a new, orthogonal axis for improvement.\n2.  **Strong Empirical Motivation:** The SVD analysis in Section 3.2 (Figure 2) is clear, convincing, and provides a strong, data-driven justification for why a low-rank (specifically, rank-1) approximation is a sensible approach.\n3.  **Algorithmically Efficient Design:** The \"delta merging\" technique in Section 4.3 is a key technical contribution. Deriving a formula (Eq 5) that correctly merges the pre-computed prior with the online sparse logits, all while maintaining the $O(|\\mathcal{I}|)$ asymptotic complexity of vanilla SA, is non-trivial and essential for the method's practicality.\n4.  **Training-Free and General:** The fact that RESA requires no re-training and can be applied as a wrapper around existing SA methods (Quest, ArkVale, etc.) makes it highly general and easy to adopt.\n5.  **Consistent Positive Results:** The experiments compellingly show that RESA provides a clear benefit, either by improving accuracy at a fixed budget (Tables 1, 2) or by enabling significant budget reduction (up to 33.2%) for a fixed accuracy target (Figure 7b).\nMarkdow", "weaknesses": "1.  **Missing Derivation for the Core Approximation (Eq 2):** This is the paper's most significant weakness. The \"Prior Estimator\" is built entirely on the approximation $q_{i}\\cdot K^{T}\\approx\\mu_{Q}\\cdot K^{T}+(q_{i}-\\mu_{Q})\\cdot\\mu_{K}^{T}$. The paper provides no derivation for this formula or theoretical justification for why it should approximate the rank-1 SVD component $\\sigma_{1}u_{1,i}v_{1}^{T}$. It is simply presented, and its validity is only asserted empirically (Figure 4). This leaves a critical gap in the paper's technical story.\n2.  **Speculative RoPE Analysis:** The connection made in Section 5.2 between the $\\mu_Q$/$\\mu_K$ terms and the \"low-frequency semantic carriers\" of RoPE (Figure 5b) is interesting but highly speculative. It reads as a post-hoc justification rather than a core part of the method's design, and it's not strictly necessary to validate the method's performance.\n3.  **Ambiguity in \"Overhead\":** The paper claims \"without extra overheads\" and \"maintains the same complexity $O(|\\mathcal{I}|)$ as SA.\" While asymptotically true for the *decoding step*, this glosses over:\n    * (a) The $O(L \\cdot d)$ computation and $O(L)$ softmax for $O_{Est}$ at the end of prefill (though this one-time cost is likely amortized and acceptable).\n    * (b) The *constant factor* overhead of the delta-merge (Eq 5) at *every* decoding step. The paper shows throughput gains *after* reducing the budget (Fig 7b), but it never shows a direct, per-token latency comparison of SA vs. SA+RESA at the *same* budget.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)