vAttention: Verified Sparse Attention via Sampling
Authors: Aditya Desai
Kumar Krishna Agrawal
Shuo Yang
Alejandro Cuadron
Luis Gaspar Schroeder
Matei Zaharia
Joseph E. Gonzalez
Ion Stoica
Venue: ICLR 2026 Poster (2026)
Keywords: sparse attention
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: State-of-the-art sparse attention methods for reducing decoding latency fall into two main categories: approximate top-$k$ (and its extension, top-$p$) and recently introduced sampling-based estimation. However, these approaches are fundamentally limited in their ability to approximate full attention: they fail to provide consistent approximations across heads and query vectors and, most critically, lack guarantees on approximation quality, limiting their practical deployment. We observe that top-$k$ and random sampling are complementary: top-$k$ performs well when attention scores are dominated by a few tokens, whereas random sampling provides better estimates when attention scores are relatively uniform. Building on this insight and leveraging the statistical guarantees of sampling, we introduce vAttention, the first practical sparse attention mechanism with user-specified $(\epsilon, \delta)$ guarantees on approximation accuracy. These guarantees make vAttention a compelling step toward practical, reliable deployment of sparse attention at scale. By unifying top-k and sampling, vAttention outperforms both individually, delivering a superior quality–efficiency trade-off. Our experiments show that vAttention significantly improves the quality of sparse attention (e.g., $\sim$4.5 percentage points for Llama-3.1-8B-Inst and Deepseek-R1-Distill-Llama-8B on RULER-HARD ), and effectively bridges the gap between full and sparse attention (e.g., across datasets, it matches full model quality at 10x–20x sparsity). We also demonstrate that it can be deployed in long-generation scenarios to achieve fast decoding without compromising model quality (e.g., vAttention achieves full model quality on AIME2024 at 10\% sparsity with up to 32K token generations).

Published as a conference paper at ICLR 2026
VÂTTENTION: VERIFIED SPARSE ATTENTION
Aditya Desai Kumar Krishna Agrawal
Shuo Yangat Alejandro Cuadron e 8
Luis Gaspar Schroeder
Joseph E. Gonzalez Ion Stoica Electrical Engincering and Computer Sciences, University of California, Berkeley,
Matei 7
9 Department of Computer Sciences, ETH Zürich
ABSTRACT
State-of-the-arr sparse attention methods for reducing decoding latency fall into two main categories: approximate top-k (and its extension, top-p) and recently in- troduced sampling-hasse based estimation. However, these approaches are fundamentally limited in their ability to approximate full attention: they fail to provide consistent approximations across heads and query vectors and, most critically, lack guarantees approximation quality, limiting their practical deployment. We observe that top- k and random sampling are complementary: top-k performs well when attention scores are dominated by a few tokens, whereas random sampling provides better estimates when attention scores are relatively uniform. Building on this insight and leveraging the statistical guarantees of sampling, we introduce vAttention, the first practical sparse attention mechanism with user-specified (c, 6) guarantees on approximation accuracy (thus, "verified"). These guarantees make VAttention a compelling step toward practical, reliable deployment of sparse attention at scale. By unifying top-k and sampling. v vAttention outperforms both individually, deliver- ing superior quality-effior eeffcciencyy trade-off. Our experiments show that vAttention significantly improves the quality of sparse attention (e.g.. ~4.5 percentage points for Llama-3.1-88 1-8B-Instt and Deepseek-RI --Distill-Llamaa effectively bridges the gap between full and sparse attention (e.g., across datasets, it matches full model quality with upto 20x sparsity). We also demonstrate that it can be deployed in reasoning scenarios to achieve fast decoding without compromising model quality (e.g., vAttention achieves full model quality AIME2024 at 10x sparsity with up to 32K token generations).
on (OLER-HARD) and
INTRODUCTION
As the application of AI expands and workflows grow more complex, the volume of context that large language models (LLMs) must maintain is rapidly increasing Touvron et al. 2023 Achiam et al, 2023) Liu et al., 2024a). However, Scaled Dot Product Attention (SDPA) operator, the core operation behind the success of transformer architectures! Vaswani 2017] Brown al. 2020). is not well suited for handling such long contexts during generation. Large contexts produce massive key-value (KV) embedding caches, and in autoregressive models, these caches must be repeatedly read for every new token prediction. This makes the decoding step inherently memory- bound and time-consuming (Kim al. 2023). The problem becomes even more severe when the KV caches exceed available GPU memory and must be offloaded to CPU RAM, requiring costly transfers across the CPU-GPU boundary. These bottlenecks highlight a fundamental scalability issue in attention mechanisms, limiting the ability of LLMs to efficiently consider long contexts. A mitigation strategy is sparse attention, which reduces memory movement by attending only to a subset of tokens in the KV cache. A good sparse attention would offer highly accurate approximations of full attention that it replaces.
The core abstract problem in approximating Scaled Dot Product Attention (SDPA; see Eq. 3) is estimating the sum of n quantities (scalars for denominator and vectors for numerator in SDPA). Since, in hindsight, the tokens that contribute most to the attention output those with the highest asllvella (Desai et al.) 2025), a natural approach is to choose tokens i with the largest key inner products k g. also known as the top-k approach (top-p, its extension, chooses budgets per
Equull contribution, system lead, (enissoonnencc(pppesseee kagrawal, istoi @berkel

---

Published as a conference paper at ICLR 2026
Response: The book long print and vittulll... ..
Performance Performance-Eficiencyy Trade-off
Error (é) Tolerance (e) Correlation
Linear fi: O 0.68B3x 0.0353
0.32
Average Layer Error (2)
27-
Average Quality
VAttention
2
0.23
Local Error Tolerance (c)
0.20
Context: Early life. Picarda was born in lenez die Frontera,
22.
FitlAttertion
the Province of Cádizin Andoluci
HashAteerton
Crack top-k
0.10
Prompt: Picurdo created a ilustrations for book named (Diaujos de Josn luis Picardoo 1980, where this original book kept now?
Cracle (MashAttentoo)
Correlatin 0.9910
R 0 9822
0.2
p-value 1.4512e-08
VAttantion Ccracle-oop44
Reduction in #reads to KVCache
Tolerance (E)
Figure I: [Left:] vAttention accepts user tolerance parameter and ensures that sparse attention errors are controlled be within this tolerance. [Middle] VAttention achieves a SOTA trade-off, outperforming leading methods like HashAttention and even a strong oracle top-p mix from long- context benchmarks (RULER32K, LongBench, Loogle). [Right] There is a strong correlation between the approximation error in the layer attention output and the user-defined parameter accepted by vAttention with verified denominator-only approximation, validating the practical relevance of é parameter
head). Thus, sparse attention research is dominated by approaches designed to approximate top-k
(Xiao et al. 2024 Tang et al. 22024 Desai et al., 2025 Li et al., 2024b Hooper et al., 2024; Zhang ctt al. 2025) and top-p (Zhu et al. 2025) efficiently. However, any deterministic sparsity, such as top-k. assumes that the contextual embedding of the current token can be determined by small set of specific tokens in the context as if information is encoded in discrete units an assumption that is clearly not true in input layer (e.g. next word does not depend only few words) and cannot be reliably assumed in deeper layers. It is not surprising that attention scores are not always sharply distributed, and in such cases, top-k methods fail to give good approximation (see Fig. 2). While top-k tokens often dominate attention outputs, contextual meaning arises from the entire distribution of key-value vectors across all tokens. This motivates the statistical perspective behind Verified Sparse Attention (vAttention).
Recently, LSH-based sampling was used to approximate attention (Chen et al. 2024). vAttention is inspired by this work. vAttention is based on a key observation for approximating a sum of n terms. the sum is sharply dominated by few terms, selecting those terms provides the best approximation. Conversely, if the terms are similar in value, case in which top-p leads to choosing an unnecessarily large number of terms, a sampling-bol vAttention combines both strategies, and adjusts the sample size to guarantee user-specified (c, 6) approximation to the target sum. Using this intuition, VAttention approximates both the numerator and denominator
estimator can approximate the sum with a small sample.
specified accuracy, ensuring that the overall error in attention output incurs at most an 6 relative error with probability (1 8), thus providing a "verified" sparse attention. To the best of our knowledge, vAttention the first practical algorithm to provide approximation guarantees while giving users explicit control over the quality-efficient tradeoff. This not only provides state-of-the-art quality on sparse attention, but also makes compelling argument in favor of deploying sparse attention reliably in the wild.
We extensively evaluate VAttention across diverse models (Llama-3., 3...a....BB----B 1-8B-Inntruut, Deepseek-R1- Distill-Llama- 8B, -
and benchmarks (RULER (Hsich et al.) (024). Long- Bench (Bai et al. 2024). Loogle (Li al. 2023), AIME (Maxwell-Jia) 2024)) and composing it with oracle-top-k, and HashAttention (Desai et al. 2025). state-of-thh-art approximate top-k. We find that vAttention consistently achieves higher accuracy than top-k methods and delivers a superior quality-efficiencc trade-off, surpassing even the strongest oracle top-p baseline (See Figure For example, at 10% sparsity, vAttention combined with HashAttention improves RULER32K-HAPP accuracy by upto 4.5 percentage points over HashAttention across models. Furthermore, owing its low approximation error, vAttention supports accurate long-form generation, producing sequences of up to 32K tokens while matching full-attention accuracy Aaae(Maxxell-Jia 2024). Additionally,
2

---

Published as a conference paper at ICLR 2026
show that there is near near-perfect correlation between the user-specified tolerance and the aver- age empirically observed error in attention outputs, showcasing the effectiveness of vAttention in exposing the -fffcieyeffcccencc trade-off of sparse attention to the end user (see Figure Tp.
2 RELATED WORK
Existing work on sparse attention can be categorized into the following types, covering early explo- rations to recent efforts. Detailed related work is presented in Appendix
Static Sparse Attention and KV Cache compression methods Early sparse attention methods used fixed patterns limit tokens during decoding. For instance, StreamingI.LM (Xiao al.) (203)) attends to "attention sinks" (early tokens) and a sliding window of recent tokens. Later work (Zhang et al. 2023 Xiao al. (024) showed that such static patterns fail to generalize, motivating dynamic sparsity. Streaming LL''s key insight-that sinks and local windows are essential-remainss central to subsequent methods. Another direction compresses the KV cache by discarding tokens, in ScissorHands (Liu et al., 2024b), H2O (Zhang et al. 2023), FastGen (Ge et al.) (023), and SnapKV (Li al.) 2024a). While memory-efficient, these approaches lack generality, since irreversible pruning struggles in settings like multi-turn dialogue, where token relevance shifts across turns.
Approximate top-k based Sparse Attention class of sparse attention methods approximates top-k token snrection-identffye
tokens with the highest query-key inner products srnducts-since since exact computation is ((nd) and undermines efficiency. Examples include Double Sparsity (Yang et al. 2015), which sparsifies partial channels; Loki (Singhania et al., 2024), which applies low-rank decomposition; and InfLLM (Xiao et al., 2024 and Quest (Tang et al.] 2024), which use page-level approximations. As top-k identification essentially inner product search problem (Desai et al.
2025), many methods adapt approximate nearest neighbor (ANN) techniques: PQCache (Zhang et al.
2025 leverages product quantization, SqueezeAttention (Hooper al. 2024) employs hierarchical
clustering, Retrieval Attention (Li et al. (004bb) adopts graph-based ANN search, and Attention
(Desai al. 2025) encodes queries and keys as bit signatures. These approaches improve scalability by narrowing the search to promising tokens, but their dependence on oracle top-k selection imposes a fundamental limitation. As demonstrated in MagicPig (Chen et al., 2024) and further analyzed here, even access to the exact top-k tokens under full attention does not always suffice to approximate the original output, highlighting the need move beyond top-k selection in sparse attention design.
Approximate Top-P based Sparse Attention A key limitation of top-k-based sparse attention is that a fixed sparsity level fails to generalize across modules. To address this, recent work adopts Top-p coverage, selecting variable number of tokens whose cumulative attention scores exceed a threshold p. thereby adapting to varying importance distributions while offering error control. Exact Top-p. however, is even costlier than top-k as it requires sorting aggregating all scores; methods therefore approximate coverage- for example, Tactic (Zhu et al. 2025) models attention decay with power-law distribution to estimate the required number of tokens. As show, Top-p is not the most efficient way to achieve a target error bound; more principled mechanisms, including Atttention, attain comparable better accuracy with fewer tokens.
MagicPig: LSH sampling-based Sparse Attention MagicPig (Chen et al. 2024) was among the first highlight the issues with top-k-based sparse attention. It employs Locality Sensitive Hashing (Gsh)s et al. 1999) to select tokens for attention computation. While LSH is suboptimal for approximate nearest neighbor (ANN) search due to its data-agnostic projections, in this context, provides principled sampling- sampling-based based mechanism for approximating attention (Luo & Shrivastava 2018). Tokens retrieved via LSH have associated probabilities reflecting how they were sampled under the randomized construction of the LSH table. Early exploration of v VAttention was inspired by MagicPig, and we elaborate further on the attention computation in subsequent sections. Another related work, SamplcAttention (Zhu et al. 2024), samples structured patterns to approximate attention.
Theoretical exploration of top-k and sampling There is extensive literature on theoretically ana- lyzing softmax attention and introducing approximations for faster training and inference, including Performers [Chormmankii et al. (2020), Linformer WWan et al. (2020). HyperAttention Han et al. (2023). and that must be trained end-to-end and are primarily focused on performance (training and inference) post training from scratch. In contrast, our work targets inference-time attention approximation to
Haris (2024). These works develop subquadratic attention mechanisms
3

---

Published as a conference paper at ICLR 2026
9-9. h-21
9-61, h-21
61.
1.0
1.0
1.0
Cumulstive Attention
0.8
(5.0K, 0,90)
(1.7K, 0.90)
0.8
(18.00 0,901
[1.9K, 0.75)
[388, 0.75)
(12.6K, 0.75)
0.6
(321. 0.50)
0.6
0.6
16.3K. 0.50)
[81. 0.50)
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
OK
20.0K
10.0K
20.0K
10.0K
20.0K
Token Index
Taken Index
Token Index
1.0
1.0
1.0
0.8
0.8
Reletive Enror
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0
10. OK
20.0K
10. OK
20.0K
10.0K
20.0K
Budget
Budget
Budget
oracle-top
0.5 oracle-top 0.5 random-sample
random-sample
MagicFigtsink=4, best of k=(2, 4, 8) (= 16, 32, 64, 128))
Figure 2: Top pane: cumulative sum of attention scores sorted in descending order of magnitude, showing the number of tokens required achieve a (0, 1) coverage the scores. Bottom: relative local attention errors across token budgets, indexed by head h and query index
accelerate decoding in off-the-shelf models. A key point of comparison with ANN-Attention Haris (2024), which investigates top-k selection and sampling through lazy Gumbel sampling and proposes plus sampling as a relaxation. However, their emphasis is on training, with theoretical treatment and objectives that differ substantially and do address inference acceleration for existing models. vAttention, by contrast, provides simple, practical theoretical foundation that directly yields an implementable algorithm, which we rigorously evaluate across multiple off-the-shel models and benchmarks.
Existing methods for inference time acceleration lack guarantees on the quality of approximation. In contrast, vAttention offers explicit control over approximation quality, providing both reliability and flexibility.
BACKGROUND AND MOTIVATION
We begin by describing the three categories of attention computation considered in this paper. For clarity, we restrict our exposition to the case of batch size one with a single query vector. Consider KVCache K, V d and query vector q x d.
Full Scaled Dot Product Attention (SDPA)
n
exp KK (),g))
SDPA(K, V.
Σ
(a, V(i) where 0; Σ cxp KK KKpl.
where a, are referred to as attention scores. This represents full attention computation.
Sparse Attention with deterministic index selection: Let S denote the sequence of indices selected by a deterministic suchho--such as attention sinks, sliding window, top-k selection, or a combination of them. The sparse attention computation based this deterministie index set is given by:
exp (K[i) g)
SDPAs (K, V.g)
Σ (a.Vii) where à; ΣSEs exp (K(j..
Sparse Attention with randomized index selection: Let denote the sequence of indices selected by randomized method such random sampling MagicPig, and let P be the corresponding
4

---

Published as a conference paper at ICLR 2026
sequence of selection probabilities. Given S and P. the attention computation is defined as:
exp (Kli), 4)
SDPAs,p(K.V.))
E
(a) where ā = L(pp))E(SP)) vy exp (K])..g
(3)
(LP:))(S.P)
This definition subsumes deterministic index selection (here probabilities associated are 1) and can be used to represent a selection that is a combination of deterministic and randomized selection.
We motivate our approach through a simple ablation. We use the following baseline: oracle-top: selects the tokens with the highest inner products, constrained by the budget, and uses deterministic uniformly samples a subset of tokens (without replacement)
attention computation. random-sampi of size equal to the budget, and applies sampling-bass based attention computation. MagicPig: Does LSH-based index retrieval followed by sampling estimation. If more tokens are retrieved than the budget allows, a subset of size equal to the budget is randomly selected; otherwise, all retrieved tokens are used. We plot the configuration among (I: {2, 4, 8) L {8, 16, 32, 64, 128)) that yields the best errors for particular sparsity. We use a sample from the GSM-Infinite (Zhou et al. 2025) dataset of length 2 and use the last 128 queries for attention computation.
As shown in Figure 2 the quality-efficiencc tradeoff depends on the distribution of attention scores, and no baseline is universally superior. We observe that the ordering is inconsistent- for given query across heads, or for a given head across highhighnnn the need for dynamic behavior per head per query. Moreover, when attention scores are sharply distributed, oracle top-k provides better tradeoff. In contrast, random sampling performs better in the presence of long tail (looking the distribution of attention scores sorted in descending order). MagicPig, though based on importance sampling, also fails to outperform other methods consistently. Drawing inspiration from these observations, we propose to combine top-k and sampling methods. As a representative, we use oracle-top random-sample: using half the budget for oracle-top and the other half for sample. We find that this combination consistently yields superior results in all three cases. This hybrid strategy serves simplification of our proposed vAttention method.
4 VATTENTION: VERIFIED SPARSE ATTENTION
Restricting attention to only fraction of tokens alters model behavior by introducing errors in the intermediate calculations of the numerator and denominator. These errors propagate, impacting per-head attention and, ultimately, the overall attention computation at each layer. While directly controlling the resulting errors in per-layer outputs or overall model behavior is mathematically challenging,
effectively regulate the errors in these fundamental computations, which correlate strongly with per-layer attention deviations and, by extension, model behavior. VAttention provides recipe for (e, verified computation for numerator, denominator and per-head attention. In general, (e, 6) verified-X' algorithm is,
Definition 4.1 ((e, 5) -)-rriffie--X'. For any given computation Rdh -> Rdaa for some di d2 E N, an algorithm X' is (e, 8--veiffee if the following holds for any E Rd:
Pr [1xx(xx) -X(x)l2
>0) < -
1x(x))1
We will first describe the recipes for verified-N and verified-ID D for numerator and denominator computations. Then we show how to combine then for per-head attention.
4.1 VERIFIED-D AND VERIFIED-N
Let the KV cache for given attention head be denoted by K, V RRaxd and the query by g E Rgxxd Both numerator and denominator are sum of n terms. vAttention breaks down the problem of approximation into two parts: (1) identifying outlier or heavy-hitter tokens, and (2) approximating the residual long tail of tokens with similar attention scores using uniform random sampling. The key idea is two fold. First, if the heavy tokens are correctly identified, the contribution of the residual tail can be approximated with small sample. Second, the convergence properties of uniform sampling can be leveraged to provide guarantees on approximation errors. We describe the exact algorithm and its mathematical foundations below.
5

---

Published as a conference paper at ICLR 2026
Query
GPU
Okons
IDX compuaaiion happers GPU
L1-Cache 221B/
Sink
tap-k
Local
basa random
L2-Cache
semple
Active Probabilty
8038, 71Bts
1/5
1/5
HBM3
Budgel Computation
[c. d)
Budgel Computalion, heppens on GPU
User Spocifistiion
Additional sample
PCIe5.0
-128G8/s
Active Index Probabiity
CPU
1/3
1/3
System DRAM 0MerriTa 9W-00308))
Use stochastic varsion sparse attention
Final Altention computation felches KV from GPU/ CPU
Figure 3: vAttention composes, sink, sliding window, and approximate top-k based attention along with random sampling based selection whose budget is governed by adaptive sampling module which ensures user specified (e, ō) guarantees hold for each attention head every layer. The index computation and budget computation occur entirely on the GPU, and the final attention computation can retrieve the KV cache from either the GPU/CPU, depending on its location.
The index selection procedure in vAttention is illustrated in Figure 3 vAttention selects mixture of deterministic and stochastic indices, and is parameterized by f fi, ft, e, E (0, 1). For the deterministic component, VAttention includes sink indices Ia, [Zal fan. local window indices I, | fin, and predicted top-k tokens Iz, [Z| = f.n. These correspond to the most salient tokens expected to dominate the attention distribution, i.c., those with high attention scores. vAttention can be composed with any off fff-the-hhelf approximate top-k method. Incorporating such "heavy hitters" is crucial for strong performance, since the stochastic only approximate the residual attention accurately with small sample when the remaining distribution does not have significant outliers (i.e., when residual attention scores have comparable magnitudes). Let I U I U and [Z,| [ [z| Tlf.
cevoonent-unffrrmn sampled indices- can
Let n. n denote the number of residual indices. vAttention uniformly samples indices Idyn from residual indices. The set of indices and associated sampling probabilities can be expressed as,
Idgnl if Idyn and 1 otherwise
S I Uddn
P
(5)
Thi
Then the VAttention computation for numerator and denominator can be written as,
N = Ny + Ndyn
Σ
(exp (K(()
Σ (exp (K())
(6)
Idyn
iEI,
jEIdun
D = Dy + Dayn
Σ
(exp (K()).))) +
Th
(exp (Kb).
(7)
Idynl
EE
jETayn
where N, (alt. Dy) comes from deterministic indices and Nayn (alt. Ddgn) comes from stochastic indices that estimate the rest of the numerator (alt. denominator).
The theoretical guarantees in vAttention arise from the careful choice of the sample size, i.e., [ The sample size is selected to ensure that the attention approximation is c-relative accurate with probability 1 - 5. We now explain how the budget chosen. The choice of sample size is guided by the following result on estimating the sum of n quantities (See Appendix D for proof)
Lemma 4.1 (Estimating vector sum). Let E ri, E Rd be a sum of n. vector quantities r; E R& Vi which has to estimated using a sample I, of size b. Let be the covariance matrix for the population {r, yh,, Let S;, nz (Eier, re) be the estimate. Let t be the CDF for the normal distribution. Then for a large enough b if.
2
(1)
8
n Tr
b2 ④
then Pr(I|s s/12 > T) 5
(8)
for any arbitrary T R and E (0, 1).

---

Published as a conference paper at ICLR 2026
Algorithm 1 vAttention
Algorithm 2 budgetx
Require: X' E (N, D. SPDA ccmmpuutainn to keep verified, KVCache K, V d, q 1 x d. Parameters fa. ft, ft E (0.1) fraction of total tokens for sink, slid- ing window and top-k tokens. Adaptive sampling parameters fb E (0, 1) base sampling rate, e, 8 (0,1) user specified guarantee.
Require: KVCache K, V n x d, 1 d
Parameters: n, sampling range, fo E (0. 1)
base sampling rate, e, E (0. 1) probabilistic guarantee required by user, Ij static index.
1: Iss f uni uniform-sampe (I fb.
thenn 2: =D then
3: o², D + get--statss(Z, In., V,
b=bple, D, V.g)
I, (0, ......... [
5: else if X- then
2: Iı - {n [in] ............111
Tr(E), get-sttss Ibs K, V.9)
3: I, + poed-top- ttt-ttoo--iindipppeeee K, V.
7: b= 6, Tr( K, V.
4: I T UZ UUIUU.P. .r =
8: else
5: t n [yy
9: Tr(2), o², || D
ns e, K, V,9) 6: b- budgetx (I,, n,
compute stats (I, K, V.q)
7: Iayn t tiniform-sen sampl eT b,
10: b=bSDPA Tr(E), 6, 1| D, D.K.
1 [ 8: Páyn n,
11: end if
9: S+ [T. Idynamic
12: return
10: p f- [pt. Pdynamic
return SDPAs,p
KK (p, V.g)
Comment We leverage the Central Limit Theorem (CLT) to approximate the sum using a sufficiently large sample. We can obtain similar result for scalar quantities by setting d = 1 in the theorem above. Detailed empirical analysis using optimistic CLT and conservative Hoeffding' 's method for budget computation is presented in E
We can use the above lemma to compute budget required for (e, d) approximations the numerator and denominator independently as mentioned in Corollary D.2 D.3 These obtained by setting T ||2 and т = eD in the numerator and denominator cases, respectively.
4.2 VERIFIED-SDPA
Let (p(c, ó, a, D, K,V, V, (resp. by(c, Tr(E), || V,)))) denote the minimum budget re- quired to achieve an (c, 8) -aprroximationn for the denominator (resp. numerator). When parameters are clear from the context, we will drop those from the expression for convenience. The individual approximation results for the numerator and denominator can be combined to yield a bound on the quality the approximated attention output, as stated in the lemma below.
Lemma 4.2. If bD and by are chosen such that we have (c1, 51) and (c2, 52) approximation on numerator and denominator respectively and eq < 0.5, then using b = max(bb, bN) ensures that
N D
Ñ D
N
Pr
2(c + 62)
+22)
< (61 + 82)
Comment.Thh The lemma above shows that if both the numerator and denominator are well approximated, then the overall attention output also well approximated.
The results above can be combined into single theorem providing algorithm to select budget for (c, 8) approximation of attention output.
Theorem 4.3 ((e, 8) verífied-SDPP/KK V,q)). Let E, be the covariance matrix for the population (exp (K()), (Vld)) Let a be the standard deviation for the population (exp (K [[i,, q) het,
Then, if the budget is
max 6p : (5:0) .6N .NN (5-66-- -80-)))]]]
min ((0
then
(10)
Pr[[ K, V.g) SDPA(K, V, 9112 > SDPAAA g, v)ll2) 5
7

---

Published as a conference paper at ICLR 2026
Crocie
Top
HeshAttention kopk
uMttendoonirrade top
QA 2 RULER 32K
HotpotQA LongBench
ShortDep Cloze Loogle
0.33
50
55
0.50
40
54
0.40
46
0.35
0.05 0.08 0.10 012 0.15 6.50 5.00
0.05
0.08
6.10 5.12 0.55 0.8 0.0
5.05
0.0
0.10
0.17 015 018 0.20
Density
Dansity
Density
0.25
0.20
0.15
80:15
0.10
0.05
0.03
0.000
6.56
0.10
0.15
0.20
00000
0.26
0,00
0.15
0.20
80:
0.05
0.10
0.15 Density
0.20
0.55
0.30
Density
Density
Figure 4: Pareto curves (Quality and Error vs. Density) for different baselines and their combination model. More pareto
with vAttention across different datasets/henchmarks for Llama-3.1-88 results are in Appendix A.I
Let bSDPA (e, 6, Eo, || D, K, V. q) denote the minimum budget required for an (c, 6) approxi- mation of SDPA attention. When parameters are clear from the context, will drop those in the expression for convenience. In practice, Σ and a as well as exact ||/i|| and D are not known apriori. However,
base sample from residual tokens to estimate them in order to compute these quantities. In our algorithm, VAttention is parameterized by fa. which denotes the fraction of n, to be used as a sample for this estimation. The complete algorithms are provided in Algo. and Algo.
Implementation Details The index computation for vAttention efficient even when the KV cache resides the CPU. The computation is naturally vectorizable and well-suited for GPUs. Although vAttention requires partial access to the KV cache for budget calculations, this can be handled on the GPU using a small random cache that incrementally populated and updated during token generation. When combined with approximate top-k methods such as HashAttention or DoubleSparsity, the auxiliary structures (e.g., bit cache or label cache) for top-k selection orders of magnitude smaller than the full KV cache-can be stored directly on the GPU. For example, HashAttention requires only 32 bits per token per head for its bit cache.
5 EXPERIMENTS
Table 1: Average performance of different methods on RULER32K-HARD benchmark (consits of 7 datasets from RULER) at 10% sparsity. HashAttention denoted as HAT. Detailed results are in Appendix A.3
Llama-3. 1-8B-Inst
D
Mistral-7B-Innt--Wl
SDPA
88.74
65.41
64.05
oracle-top-k
87,18
64,87
64.37
vAttentionforacle-op... top-k)
88.61
65.15
64.
HAT vAttention(HAT)
81.94
60.70
54.66
86.56
65.06
56.90
We perform an elaborate evaluation of vAttention against oracle and approximate baselines on multiple datasets, models, and generation lengths. The evaluation setup is explained below.
Datasets and Models. We evaluate vAttention on four benchmark suites: RULER (32K con- text length) Hsiih al. (2024), LongBench Bai et al.) (2024), and Loogle (truncated to 16K) Li et al. (2023), providing a broad basis for comparison. We further extract seven tasks from RULER32K into RULER32K-HARR to isolate cases where top-k methods are known struggle.
8

---

Published as a conference paper at ICLR 2026
Table @IME@ 2024 with DeeeekaaiiieeeSee------iiiii
with vAttention (e 0.05, 5 = 0.05, ft = 0.025, ft = 0.025, sink and local tokens are set to absolute 128). The generations are capped at 32K tokens. More details on the evolution of density and errors along sequence length are provided in Appendix A.5 Average density at 16K length is around 10-15% % for Atttniten
Type
2
3
4
avg
dense
43.30
36.67
33.33
33.33
36.66
V (Ateentionorracle-to--k))
43.33
40.00
26.66
36.67
36.67
VAtrentiom(HasiAAttennion)
30.00
36.66
46.66
26.66
35.00
RULER32K-HARD consists of qa-1, qa.2, vt, fwe, niah.multikey. and iiahhmuuliive
selected based on the HashAttention paper, where these datasets were shown to be challenging. Detailed results are provided in the Appendix, with partial results included here. We also use AIME2024 to evaluate VAttention on long generation and reasoning tasks. For models, we consider three L.Mss: Llama-3. 1-8B-Instruct, Mistral-7B-v0.3, and DeepSeek-R1-Dice R-Distill- Llama-8B, evaluated across different subsets of benchmarks.
Baselines. In our study, we choose oracle-top-k as baseline, which serves as the theoretical gold standard for all approximate top-k methods, and oracle-top-p, the strongest oracle-top-basee baseline, as it can provide dynamic oracle-top-& based on the attention score distribution. As representative of approximate top-k methods, we select HashAttention, which outperforms Quest Tang et al. (2024). Double Sparsity Yang et al. 2024). InfLLM Xiao et al. (2024). and others. For completeness, comparative table is provided in Appendix A.4 We report results for vAttention in combination with both oracle-top-k and HashAttention. When aiming achieve partieular sparsity in experiment, we search for the best parameters within a defined search space that yield the lowest local attention errors while meeting the target sparsity. Details of the search space are provided in Table Following (Desai et al.) 2025 Jegou et al. 2024 Hooper et al. 2024), we use full attention for context processing and sparse attention for question and generation. Under this setup, MagicPig does not perform well.
We provide additional details in Appendix
Superior quality of vAttention at different sparsities The Pareto results comparing the quality of sparse attention across different densities (i.e., the number of tokens used) are presented in Figure We also compare average improvements across models in Table We observe:
vAttention significantly improves the quality and approximation error versus density tradeoff when combined with a top-k method (both HashAttention and oracle top-k). vAttention combined with oracle top-k yields the best results, indicating that more accurate top-k methods are essential for the overall quality of sparse attention, even with vAttention.
Oracle top-p, representing the best achievable top-k approximation, does not always reach full model quality or provide the best approximation error at reasonable sparsities. For example, on the RULER 32K benchmarks, vAttention combined with oracle top-k even outperforms oracle top-p. vAttention combined with oracle top-k achieves full model accuracy at reasonable sparsity levels across all benchmark datasets considered.
v VAttention increases the average quality of 10%-sparse HashAttention RULER-HARD by 4.6 percentage points for Llama3. 1-8B and by 4.3 points for Deepseek- -1itt--ill--ii-aamaaee
Long Generation with vAttention in the wild: The AIME2024 results presented in Table 2 We deploy vAttention with natural configuration parameters, without any parameter tuning, as would be done in real-world settings. Token generation is capped 32K tokens. We find that both vAttention (oracle-top-k) and v Atttetion (HashAttention) match the full model quality (Avg@4), demonstrating the effective long-sequence generation capacity of vAttention.
Efficiency with vAttention: We compare the speedups of Llama-3-8B and Llama-2-7B with vAttention when the KV cache is hosted the CPU, shown in Figure For this comparison, use a naive PyTorch implementation of v vAttention index computation together with our optimized sparse attention backend. With more careful implementation, the performance of vAttention can be further improved for CPU-hosted KV caches and will yield gains for GPU-hosted KV caches. However, developing optimized CUDA kernels for VAttention is beyond the scope of this paper.

---

Published as a conference paper at ICLR 2026
Llama2-78
Llama-3/
CTX 62CK
CTX 262K
CTX 131K
CTX 6GK
-TTX 520K A CTX 262K
CTX 131K
CTX BBK
speotup
Speedup
243
270
1:13
110
2x 4x
Ox
10x
16x
Recuction in Memory Read (Speristy Factor)
Reduction Memory Read (Spersity Factor)
Figure 5: For Llama models with the KV cache hosted on the CPU, we observe a near- speedup, as inference is memory-boung and latency primarily depends on the amount of KV cache read. This experiment is conducted using naive PyTorch code for index computation, and the results can be further improved with dedicated CUDA implementation.
CONCLUSION
The mainstream approach to sparse attention has been to approximate top-k token selection. However, we show in this paper, even oracle versions of top-k and top-p are either insufficient for accurate attention approximation or require unnecessarily large numbers of tokens. More importantly, none of the existing methods--piimarily designed approximate these oracle cesiions-offee guarantees or user control over approximation errors. vAttention is the first verified sparse attention method that not only provides fine-grained user control over approximation, but also achieves superior -ufiity-efficiency trade-offs compared to top-k approaches. It makes a compelling case for reliable deployment and for realizing the significant quality-efficiency benefits sparse attention can offer. We believe v Attention will enable the practical adoption of sparse attention in the wild.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint 2xXiv:2333.08774 2023.
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 Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 3119-3137, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 18653/111 a02-.acl-long. 172.
org 2024 acl- 11m...7722...
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Zhuoming Chen, Ranajoy Sadhukhan, Zihao Ye, Yang Zhou, Jianyu Zhang, Niklas Nolte, Yuandong Tian, Matthijs Douze, Leon Bottou, Zhihao Jia, et al. Magicpig: Lssh sampling for efficient Ilm generation. arXiv preprint arXiv:2410.1677 2024.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009.1479. 2020.
Aditya Desai, Shuo Yang, Alejandro Cuadron, Matei Zaharia, Joseph E. Gonzalez, and Ion Stoica. Hashattention: Semantic sparsity for faster inference. In Forty- International Conference on Machine Learning, 2025. URL htwph: http:::///ppeeeeeeeeeee
net. htt.:tttt///peeeeiiiieee
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. arXiv preprint arXiv:23/000180,, 2023.
10

---

Published as a conference paper at ICLR 2026
Aristides Gionis, Piotr Indyk, Rajeev Motwani, al. Similarity search in high dimensions via hashing. In Vldb, volume 99, pp. 318-529, 1999.
Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P Woodruff, and Amir Zandieh. Hyperattention: Long-context attention in near-linear time. arXiv preprint arXiv:2310.0580 05..8699, 2023.
Themistoklis Haris. & nn attention demystified: A theoretical exploration for scalable transformers. arXiv preprini arXiv:2411.0400 1.04013, 2024.
Coleman Hooper, Sehoon Kim, Hiva Mohammadzadeh, Monishwaran Maheswaran, June Paik, Michael W Mahoney, Kurt Keutzer, and Amir Gholami. Squeezed attention: Accelerating long context length I1m inference. arXiv preprint arXiv:241..09653 2024.
Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, Shantanu Acharya, Dima Rekesh, Fei Jia, Yang Zhang, and Boris Ginsburg. Ruler: What's the real context size of your long-context language models? arXiv preprint arXiv:2404.0m 06654, 2024.
Simon Jegou, Maximilian Jeblick, Alessio Devoto, Jiwei Liu, and David Austin. Kvpress: Efficient kv cache compression for long-context Ilms, 2024. URL CtLhhtts:/ www.thu..co.m.iiii..
kvpress] Version 1.2.0.
Sehoon Kim, Coleman Hooper, Thanakul Wattanawong, Minwoo Kang, Ruohan Yan, Hasan Genc, Grace Dinh, Qijing Huang, Kurt Keutzer, Michael W Mahoney, et al. Full stack optimization of transformer inference: a survey. arXiv preprint 22t.::2302.140117 2023.
Jiaqi Li, Mengmeng Wang, Zilong Zheng, and Muhan Zhang. Loogle: Can long-context language models understand long contexts? arXiv preprint urXiv:2311.04993 2023.
Yuhong Li, Yingbing Huang, Bowen Yang. Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Lim knows what you are looking for before generation. arXiv preprint arXiv:2404. /4469, 2024a.
Zhuowan Li, Cheng Li, Mingyang Zhang, Qiaozhu Mei, and Michael Bendersky, Retrieval augmented generation or long-context lims? comprehensive study and hybrid approach. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: Industry Track, pp- 881-893, 2024b.
Hao Liu, Wilson Yan, Matei Zaharia, and Pieter Abbeel. World model on million-length video and language with ringattention. arXiv e-prints, pp. arXiv-2402, 2024a.
Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava. Scissorhands: Exploiting the persistence of importance hypothesis for 11m kv cache compression at test time. Advances in Neural Information Processing Systems, 36, 2024b.
Chen Luo and Anshumali Shrivastava. Arrays of (locality-sensitivee) count estimators (ace) anomaly detection on the edge. In Proceedings of the 2018 World Wide Web Conference, pp. 1439-1444 1448, 2018.
Maxwell-Jia. Aime 2024 dataset. Dataset, Hugging Face, 2024. URL htt.httss//hugiggaaaae. /o/ dataaats /Mw.//awwwelllleeeaa laaeeeeel--aaaaaa Jia/AIME 2024
Prajwal Singhania, Siddharth Singh, Shwai He, Soheil Feizi, and Abhinav Bhatele. Loki: Low-rank keys for efficient sparse attention. arXiv preprint wwXiv:2406.025422 2024.
Jiaming Tang, Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, and Song Han. Quest: Query-aware sparsity for efficient long-context Ilm inference. arXiv preprint 1rXiv:2406.10774. 2024.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
11

---

Published as a conference paper at ICLR 2026
A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang. and Hao Ma. Linformer: Self-attention with
linear complexity. arXiv preprint arXiv:2006.04770 2020.
Chaojun Xiao, Pengle Zhang, Xu Han, Guangxuan Xiao, Yankai Lin, Zhengyan Zhang, Zhiyuan Liu, Song Han, and Maosong Sun. Infllm: Unveiling the intrinsic capacity of ilms for understanding extremely long sequences with training-free memory. arXiv preprint arXiv:2402.04617 2024.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv preprint arXiv:2309.17553, 2023.
Shuo Yang, Ying Sheng, Joseph E Gonzalez, lon Stoica, and Lianmin Zheng. Post-training sparse attention with double sparsity. arXiv preprint arXiv:2408.0000 2024.
Zichao Yang, Marcin Moczulski, Misha Denil, Nando De Freitas, Alex Smola, Le Song, and Ziyu Wang. Deep fried convnets. In Proceedings of the IEEE international conference on computer vision, pp. 1476-1483, 2015.
Hailin Zhang, Xiaodong Ji, Yilin Chen, Fangcheng Fu, Xupeng Miao, Xiaonan Nie, Weipeng Chen, and Bin Cui. Pqcache: Product quantization-basee kveache for long context Ilm inference. Proceedings of the ACM on Management of Data, 3(3):1-30, 2025.
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 08844661-37110 2023.
Yang Zhou, Hongyi Liu, Zhuoming Chen, Yuandong Tian, and Beidi Chen. Gsm-infinite: How do your Ilms behave over infinitely increasing context length and reasoning complexity? arXiv preprint arXiv:2502.05252 2025.
Kan Zhu, Tian Tang, Qinyu Xu, Yile Gu, Zhichen Zeng, Rohan Kadekodi, Liangyu Zhao, Ang Li, Arvind Krishnamurthy, and Baris Kasikei. Tactie: Adaptive sparse attention with clustering and distribution fitting for long-context 1lms. arXiv preprint arXiv:2502. 12216, 2025.
Qianchao Zhu, Jiangfei Duan, Chang Chen, Siran Liu, Xiuhong Li, Guanyu Feng, Xin Lv, Huanqi Cao, Xiao Chuanfu, Xingcheng Zhang, et Sampleattention: Near-lossless acceleration of long context Iim inference with adaptive structured sparse attention. arXiv preprint arXiv:2406. /5486, 2024.
12

---

Published as a conference paper at ICLR 2026
A
ADDITIONAL EXPERIMENTS RESULTS AND DETAILS
A.1 PARETO PLOTS FOR LLAMA-3. 1---M--3--BB-IISTTRRE
Sparse Methods Comparison
ShortDep OA Loogle
61e
0.50
0.3
0.00
Eooe 0425 0.350 1875 2339 8325 6358 6.75 0.00
650 6535 cast
0.00 ais 9:39 9375 1259
605
0.00
Dansty
ShortDap Cloze Loogle
HotpotOA LongBench
MultiFleldQA Longtlench
0.00
0.3
5:10
0.08
0.35
3.22
E.35
1.30
0L10
Hastiilattion Spp-c
Dracke villartierionaceelsppa Oracle Top-p
Figure 6: Attention approximation errors vs. Density for different approaches with and without VAttention.
Quality vs Density Across Different Datasets
OA. 1 RULER 32K
OA. 2 RULER 32K
MultiField@A LongBench
25.5
55.2
Qualiy
Quality
20
51.
523
0.44
834
Denuity
Deraity
Dens
HotpotOA LongBench
ShortDep Cloze Loogle
ShortDep OA Loogle
0.5
Qua R2
82
0.835
0.45
8.05
6804
0.35
Deriity
Danalyy
Figure 7: Quality vs. Density for different approaches with and without vAttention.
13

---

Published as a conference paper at ICLR 2026
A.2 ACHIEVING REQUIRED SPARSITY.
To achieve the required sparsity, we search for the configuration parameters on a few examples from the dataset and select the configuration with the minimum local attention approximation error while maintaining the target sparsity. The search space used is mentioned table
Table 3: For local and sink tokens we use fixed 128 tokens throughout experiments for all methods.
Target Sparsity
Parameter Grid
MugicPig oracle-top-p
K = [4, 8, 16, 32] [16, 64, 128)
p=[0.1. 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8. 0.85, 0.9, 0.95, 0.98, 0.99]
fo [0.01, 0.02, 0.033
f:: [0.05, 0.1. 0.15]
vAttention
<:
0.2, 0.3]
4: [0.05, 0.1, 0.2,
fa [0.025, 0.05, 0.075]
f:: [0.05, 0.075, 0.11
VAttention
10
c10.025, 0.05, 0.1. 0.2]
6: [0.025, 0.05, O.1, 0.2]
10.025, 0.05, 0.075, 0.1]
f:: [0.025, 0.05, 0.075]
vAttention
15
=:(0.01, 0.025, 0.05, 0.1]
4: 0.025,
0.1]
[0.05, 0.1, 0.15] f:: [0.01, 0.02, 0.03]
vÅttention
20
e: [0.01, 0.025, 0.05, 0.1]
5 [0.01, 0.025, 0.05,
A.3 DETAILED RESULTS 10% SPARSITY
Table 4: RULER @ 32K Meeta-llaaa/Llmma 3. 1-8B-Instruee at 10% sparsity full benchmark results. As mentioned the paper, half datasets are quite easy and solvable by HashAttention. However, the harder datasets is where vAttention bridges the gap between full attention and HashAttention / oracle-top-k significantly.
niah multiquery
multivalue
niah multikey. ..2
mulivvluee
niah 1
niah single.2
mihhsingge..3
niah maw.mmiiii mumlibee
malikeey
Ewe
full attention
98.5
97.4
80.5
51.5
99.12
(itentiionoracle-to---)
100
100
100
100
97
98
12
97.5
79.5
51.5
93.17
99.5
100
99.12
oracle-top-k
100
100
100
100
98.5
97.5
1.2
97.6
73.5
48
93.17
99.5
99.5
99
VAtlention (Hashiinn
76
48
98.38
HashAttention
100
100
100
100
99
98
3.6
89
73
45.5
91.33
88.5
87.5
98.75
Table 5: RULER @ 32K Saataallamm//lamm-333 1-88--1--snnttete average score
Easy Average
Hard Average
Full Average
full attention
85.30
88.
87,02
vAttentionnoracleetop..
85.17
88.61
86.89
oracle-top-k
85.31
87.18
86,25
(Attention(HashhAteeninn
84.57
86.56
85.57
Attentttn
85.80
81.94
83.87
14

---

Published as a conference paper at ICLR 2026
Table [Context length capped at 32K and new tokens capped to 100 and 10% sparsity] Some
datasets from Longbench benchmark with 1amma-..--B-Inseee
multificlqga.c en
hurrativege
musique
gasper
gmsum
2wiki
dataset
Avg
full attention
54.25
55.75
29.25
46.87
31.07
24.98
46.51
41,24
-Attention(oracle-tt---/)
54.46
55.95
29.17
47.79
30.57
25.10
46.27
41.33
oracle-top-k
52.95
51.98
30.01
44.48
23.29
25.45
47.28
39.35
Attention(HasAAtttnnln
53.21
55.59
31.34
43.05
27.58
25.15
44.33
40.04
HashAttention
53.79
52.57
27.15
43.96
23.13
24.38
45.50
38.64
Table RULER 32K (deepseckai/DeepseekR---- -iiiseekk-R---isiil-Laa------ at 10% sparsity full bench-
mark results. We only evaluate hard datasets for this setting
niah multikey_2
niah multikey-3
niah multivalue
qa_l
qu_2
fwe
dataset
M
Avg
full attention
21.20
46.00
58.00
90.67
82.00
68.00
92.00
65.41
vAttention(oraclc-to--11)
18.40
44.00
60.00
90.67
82.00
70.00
91.00
65.15
oracle-top-k
35.60
42.00
58.00
88.00
74.00
66.00
90.50
64.87
"Attention(HashhAttenn
30.40
46.00
56.00
90.00
78.00
64.00
91.00
65.06
HashAttention
40.40
36.00
56.00
84.00
70.00
50.00
88.50
60.70
Table RULER @ 32K (mistralai/Mistral-7B.. (nst-uttttutt at 10% sparsity full benchmark results.
We only evaluate hard datasets for this setting
niah multikey-2 .2
niah multikey_3
niah multivalue
qa_1
Qu.2
fwe
dataset
At
Avg
full attention
88.00
50.00
48.00
91.33
60.00
20.00
91.00
64.05
VAttention(oracle-oo---))
88.00
52.00
44.00
91.33
60
24
89.5
64.12
oracle-top-k
84.40
56.00
40.00
90.67
54.00
34.00
91.50
64.37
VAttention(HahhAttenioo
85.60
46.00
44.00
90.67
36
92
$6.90
HashAttention
72.80
46.00
38.00
93.33
34.00
4
94.50
54.66
15

---

Published as a conference paper at ICLR 2026
A.4 COMPARATIVE RESULTS OF HASHÄTTENTION vs. OTHERS
The results are presented in Table 9
Table 9: Comparison of approximate top-k basclines with HashAttention on datasets from LongBench for LLama-3.1 1-0---.118711 1-8B-Instruct. All baselines used at 32 bits per token per head of auxilliary memory. The table is adapted from (Desai et al. 2025
Category
MQA HPQA
SQA MFQA
Summ QmSm
FS-Learn TQA
Synthetic PassR
Code RepoB
Model
Aux.bits/token
Tokens
Average
Full Model
NA
NA
54.83
55.17
24.91
91.31
100.00
55.07
63.55
Oracle(top)
NA
52.10
53.45
25.14
91.39
100.00
58.49
H20
NA
512
36.62
26.61
17.83
80.75
43.43
55.55
43.47
Streaml LM
NA
512
33.32
27.98
17.93
51.95
11.43
57.07
33.28
InfLLM
256 16,bit=16)
512
48.27
53.09
22.90
88.88
32.81
43.45
48.23
DS
32(ch= 16,bir22
512
50.39
50.57
23.41
90.32
98.86
37.72
61.88
Quest
(6.g=1),hi==2)
512
53.13
51.31
23.01
90.15
98.29
58.29
62.36
HashAltention
32
54.08
53.35
92.41
100.00
59.98
64.15
A.5 LONG GENERATION WITH VÀTTENTION
The error and density evolution with token generation for AIME for two examples in Figures 8 vAttention adapts the sparsity in each layer for each head and for each specific query. The average density of attention at 32K tokens is around 12%. Even with natural parameter values for parameters of AAttention, it can achieve the required density, which leads to stable long generation.
Foregle Deeddy VOC
Aerag Jente
200
Figure 8: Example 0
A.6
ABLATION (E,
B
DETAILED RELATED WORK
Existing work on sparse attention can be categorized into the following types, covering early explorations to recent efforts.
B. STATIC SPARSE ATTENTION
Early work on sparse attention focused on fixed sparsity patterns to reduce the number tokens considered during decoding. For instance, Streamingl.IMM (Xiao et al. 2023) employs fixed attention
16

---

Published as a conference paper at ICLR 2026
Euarpl 2: Dortly and
Figure 9: Example 3
Average Denaity
Average Layer Error
Average Accuracy
0:37
111
OVE
C343
67.0
643
0:003
5.341
6.334
5,00
03M
025
6.5
6.5
222
Figure 10: How the average density, average relative attention approximation error and overall quality on RULER-32K(QA1, QA2) tasks vary when using only denominator-guaranen approximation
both "attention sinks" (typically the first few tokens) and a sliding window over recent tokens. However, subsequent studies (Zhang et al., [023 Xiao et al., 2024) have shown that static patterns often fail to generalize well, highlighting the importance dynamic sparsity in attention mechanisms. While StreamingLLM itself does not fully support dynamic token selection, its key insight that insight-that
attention sinks and local windows are crucial has strongly influenced later approaches. Most recent sparse attention methods now incorporate sink and local tokens as foundational components of their selection strategies.
B.2 KV CACHE COMPRESSION METHODS
A parallel line of research focuses on KV cache compression, wherein tokens are selectively dis- carded based on heuristics aimed at reducing memory overhead. Representative approaches include ScissorHands (Liu et al. 2024b), H2O (Zhang et al. 2023), FastGen (Ge et al.) 2023), and SnapK V (Li al. 2024a). While these methods can be effective in lowering memory usage, they often lack generalizability across tasks due to their irreversible token pruning. This limitation is particularly pronounced in settings such as multi turn dialogue/inerrattion where the relevance contextual tokens may vary significantly between turss, making fixed pruning strategies inadequate.
17

---

Published as a conference paper at ICLR 2026
B.3 APPROXIMATE T BASED SPARSE ATTENTION
line of sparse attention methods grounded in the observation that only a small subset of tokens significantly contribute to attention cnspuuation-typicall those associated with the highest attention scores under full attention. For given query vector q. the most relevant tokens are those whose key vectors k yield the highest inner products k. In theory, optimal sparsity could be achieved by selecting the top-k tokens with the highest inner products. However, computing all pairwise inner products requires ((dd) operations, which diminishes the potential computational savings. Consequently, most methods in this class rely on various approximations to efficiently estimate the top-k tokens.
Recent methods in this direction introduce specific strategies to reduce the computational costs of inner products. For instance, Double Sparsity (Yang et al. 2024) approximates inner products using reduced set of channels, while Loki (Singhania et al. (2024) leverages low-rank projections to operate in compressed, lover-dimensional space. Other techniques, such InfLLM (Xiao et al. 2024) and Quest (Tang et al., 2024), employ page-level summary vectors to identify potentially important tokens at the block level, thereby limiting the number of inner products evaluated. Despite their computational benefits, these methods often rely on heuristic approximations, which can lead to poor recall in identifying the true top-k tokens critical for accurate attention computation.
Given that the task of identifying top-k tokens effectively reduces to the Maximum Inner Product Search (MIPS) problem (Desai et al. (025),, a number of recent methods have adopted techniques from approximate nearest neighbor (ANN) search. For example, PQCache (Zhang et al., 2025)
leverages product quantization to accelerate MIPS, while SqueezeAttention (Hooper et al. 2024
employs hicrarchical clustering improve the efficiency of top-k retrieval. Retrieval Attention (Li et al. 2024b) adopts graph-based ANN search, and HashAttention (Desai et al. (025) encodes queries and keys as bit signatures, enabling efficient similarity computation in Hamming space.
Although these approaches improve scalability by narrowing the search to the most promising tokens, their reliance on approximating the oracle top-k tokens introduces fundamental limitation. As shown in MagicPig (Chen et al. 2024), and further analyzed in this work, even access to the exact top-k tokens under full attention does not always suffice faithfully approximate the original attention output- highlightinhiii the need to go beyond top-k selection in designing effective sparse attention mechanisms.
B.4 APPROXIMATE TOP-p BASED SPARSE ATTENTION
key limitation observed in top-k-based sparse attention methods is that a fixed sparsity level fails to generalize across different attention modules within model. To address this, recent approaches have shifted towards achieving top-p coverage, where the goal is to select a variable number of tokens whose cumulative attention scores under full attention exceed threshold p. This adaptive strategy better aligns with the varying importance distributions across layers and heads. Additionally. it provides control over the amount of eттor an attention module can make.
However, identifying the exact set of tokens that satisfy the top-p criterion-i.e., those whose cumulative attention scores exceed predefined threshold p-is computationally more demanding than top-k selection, as it requires sorting or aggregating over all token scores. To mitigate this cost, recent methods approximate the coverage estimation to efficiently select token indices that collectively capture the desired attention mass. One such approach is Tactic (Zhu et al., (025). which approximates top-p attention by modeling the decay of attention scores using a power-law distribution, allowing for efficient estimation of how many top-scoring tokens are needed to meet the coverage threshold.
As we will show in this paper, while top-p attention offers some degree of error control- to the quality of its approximation is not the most efficient approach for achieving a given error bound. More principled mechanisms can attain comparable or lower error using fewer tokens. In this work, we introduce one such method: vAttention, which enables improved error control through adaptive and token-efficient selection.
18

---

Published as a conference paper at ICLR 2026
B.5 MAGICPIG: LSH SAMPLING BASED SPARSE ATTENTION
To the best of our knowledge, MagicPig was the first work to highlight the issues associated with top-k-based sparse attention.
The method leverages Locality Sensitive Hashing (LSH) (Gionis et al. 1999) to select which tokens participate in attention computation. While LSH is generally considered suboptimal for approximate nearest neighbor (ANN) search due to its data-agnostic projections, its use here offers a principled and novel mechanism for approximating attention. LSH-based retrieval can be viewed as a sampler (Luo & Shrivastaval 2018). Thus, the tokens retrieved from LSH have probabilities associated with them, under which they were sampled in the randomized construction of the LSH table. We can estimate the numerator and denominator of attention using the importance sampling formulation. Early exploration for VAttentionwas inspired by MagicPig, and we will elaborate more on the attention computation in subsequent sections.
While LSH gives a principled way to compute attention, the issue associated with using LSH remains. Firstly, given the orthogonal distribution of keys and queries (Chen et al. 2024), LSH fails to distinguish between the different keys to the level at which original softmax demands - often leading to highly skewed distribution of buckets (some buckets are very heavy while other buckets empty). Centering is considered to be a practical solution to this. However, is easy to prove that under centering, the original ordering among tokens for arbitrary query is not preserved, making the operation ad hoc. Even if centering is valid, the number of hashes required to achieve sufficient recall significantly higher than that of related methods, such HashAttention(Desaa et al., 2025). necessitating the involvement of CPU RAM.
Finally, none of the existing methods across categories offer conerete guarantees on the quality of approximation--vve even at the level of a single attention head. In contrast, vAttention addresses this gap by providing principled solution the problem of uncontrolled approximation in sparse attention. Our method enables explicit control over the approximation quality for each individual attention head, offering both reliability and flexibility.
C EVALUATION SETUP AND COMPARISON ON MAGICPIG
Since our work is primarily concerned with the efficiency of sparse attention during decoding, it common practice to preprocess long contexts using full attention. Under this paradigm, two evaluation setups for sparse attention are typically employed:
1. [Setup AJ Full-prompt preprocessing with dense attention followed by sparse decoding The entire prompt is first processed with full attention, and sparse attention applied only during the decoding phase. In this setup, the first token generated already benefits from full attention.
2. [Setup BJ Split-prompt processing (context vs. question): The prompt is divided into two parts:
(a) Context is processed with full attention
(b) Question subsequent generations processed with sparse attention
Some earlier works, such as MagicPig, adopt the first setup. In contrast, more recent ap- procches-including HashAttention and SqueezzcAteentionn-llloo the second. A methodology similar to the second is also used in NVIDIA's KVPress framework to compare KV cache compression methods, where the KV cache compressed after the context processed but before the question is introduced. We argue that the second setup is the more meaningful choice.
The reasoning is as follows. Sparse attention for long- long-context evaluation is usually tested on datasets with relatively short generations (e.g.. RULER, Longhench, etc). Suppose the entire context is first processed by full attention (setup 1). that case, all the necessary information to answer the question has already been extracted by the time the first token is predicted. Applying sparse attention only after this point, especially with a fixed local attention window, does not truly test its ability to retrieve and utilize information from the long context. This hypothesis is validated by observations where, under setup A, MagicPig appears to perform well, but their performance collapses under setup B. (see Table 10
19

---

Published as a conference paper at ICLR 2026
Therefore, genuinely assess the effectiveness of sparse attention in long-content settings, it is essential to adopt setup B
Table 10: Faithful reproduction of MagicPig results on RULER and differences from our MagicPig implemenation and evaluation setup. Evaluation-A: preprocess full context+question via full atten- tion followed by sparse attention only for genreation. Evaluation-B: preprocess only context with full attention and question along with generations are processed by sparse attention. MagicPig-A: (logic in Authors Code) which does not use simpleLSH transform for inner product search (only uses angular LSH) and uses dense layers for 0,16. MagicPig- of our base code) uses simpleLSH transform for inner product search as per theory, does not use any dense layers. In our evaluation setup, which a more reasonable evaluation, MagicPig does not perform well.
niah mwltikuy.33 3
niah. multivalue
niah multikey
niah single.1
niah single 2
niah single
setup
MagicPig (K=8,L=75)
Authors code
=B (core paper description) dense layers(0,16)
questions processed via
100
100
100
98
98
98
dense attention
no simpleI.SH transform
Our code
B
B
100
96
76
46
12
81.5
B
100
96
74
60
84.5
dense layers(0,16)
B
A
100
98
98
94
90
88
dense layers(0,16)
A
A
100
100
100
98
98
95.5
Furthermore, some methods deliberately mix dense and sparse attention across layers. We take different stance: sparse attention itself should be sufficiently adaptive each layer's requirements, increasing its effective density when necessary rather than relying on dense layers as a fallback.
D THEORY
D.1 DERIVATION VIA CENTRAL LIMIT THEOREM (CLT)
Lemma D.1 (Estimating vector sum). Lets = E Fi, 8 E Rd be a sum of ng vector quantities r E Rd Vi which have to be estimated using a sample In of size Let E be the covariance matrix for the population {x, Vh Let S; nx (Etez, rz) be the estimate. Let & be the CDF for the normal distribution. Then for large enough b if.
2
b2
10-(1-7
n Tr
then Pr(I|s s|12 > T) 5
(1I)
for any arbitrary T E R and e (0,
Using the Multivariate Central Limit Theorem,
vb
Σ
4 AO E).
r
11
bb
Σ
4
A E).
ri
n
IEI,
20

---

Published as a conference paper at ICLR 2026
vb
( s) 4 2).
vb
11 (8 8) 4 N(0, u Eu).
T
u (S s) 4 N u Eu).
To achieve a error within t for we must have
b V (u ΣujΦ
(1
(1 2
8
<
This can achieved if
n Vb (vr(E))
1 (1-2
0)
<
Solving for
b> 11 (V
6 1 (1 2
2
D.2 COROLLARIES FOR NUMERATOR AND DENOMINATOR
Corollary D.2 ((e, approximation of N). Let E be the covariance matrix for the population {exp (K(1,,) V(ll, Let Ñ N2 + "f (Eietag exp (K(),, vV(() be the estimate when using sample Idyn of size Let & be the CDF for the normal distribution. Then for a large enough and for any arbitrary e, E (0, 1). if
5) nay (2 -1-1
b Φ
then Pr(IIñ N112 elIN112) S 8
(12)
N|2
Corollary D.3 ((e, approximation of D). Let be the standard deviation for the population (exp Klil,ahett Les D = DD + Re EieTam exp (Kli), 4) be the estimate when using sample Idgn of size b. Let & be the CDF for the normal distribution. Then for a large enough b, for any arbitrary e, E 10, if
b2
4-1 1
ngO
then Pr( - >
(13)
eD
D.3 COMBINATION APPROXIMATIONS NUMERATOR AND DENOMINATOR
Lemma D.4. bp and bn are chosen such that we have 81) and (e2, 62) approximation numerator and denominator respectively and 62 < 0.5, then using b = max(bp. by) ensures that
Ñ
N
Pr
> 2( + +22
< (61 + 62)
(14)
D
D
2
If have (e1, 81) approxiamtion for numerator and (e2, 62) for denominator. Consider the following expression
DN DN
ll2
(15)
D
DD
21

---

Published as a conference paper at ICLR 2026
With probability (1 - 81 - -82)
DÑ DN + e2DN
N N E
(16)
DD
D
I1 N112 + 62 e2
(17)
61 <|I + E2 |
(18)
D + (2)
||/112
= (a + +2)
(19)
D(1 - -(2)
||
$ (E1 + +x2 + 2E2)
e2 < 0.5
(20)
D
$ 2 + (2) ||/
(21)
D
(22)
D.4 WHY REDUCING BIAS IN ESTIMATION IS MORE IMPORTANT THAN REDUCING VARIANCE.
The propagation of errors through the model can be modeled as random walk of Łee; steps for simplicity.
The argument follows from the standard analysis of mean-square error of random walk of steps. Let each step have mean square eπrоr of size e².
case Entire MSE is attributed to bias
Then the MSE at step n²
case 2: Entire MSE is attributed to variance
Then the MSE at step is ne²
Thus, the impact of bias on error propagation much stronger than that of variance.
Generally, if the bias and standard deviation of error each step μ4, then the MSE step is
MSF(n) = n 1.² + no² MSE(n) (n(n 1))²²² ne Thus the compounding effect of bias is much stronger than that of variance.
(23)
(24)
22

---

Published as a conference paper at ICLR 2026
E EMPIRICAL ANALYSIS OF TIGHTNESS FOR CLT AND HOEFFDING BOUNDS
In this section, we present an empirical analysis of the tightness of our theoretical bounds for denominator approximation. We compare the Central Limit Theorem (CLT) based approximation
with Hoeffding's 's inequality, focusing on the configuration 0.1, ô = 0.2 with 5% oracle top-k selection.
E. SUMMARY ANALYSIS ACROSS LAYERS
The results presented in Figure II and Figure 12
evaluated the tightness of both bounds with the following setup:
Approximation parameters: 0.1 and d 0.2
Oracle top-k: 5% of total tokens selected deterministically
Model: Llama-3.1-8P Instrrutt on RULER dataset with 16K context length
DeArbbbter Rebitie Entrs ttre 100
DIAVBUS on sudyets
131
127
137
187
137
dee sreggee
baget
5.105
M
5.0
Figure 11: CLT-based approximation analysis with 0.1, 0.2 and 5% oracle top-k.
Comparing the two results (Figure II and Figure 12 we find:
Conservative bounds: Hoeffding equires 2.8x more samples (average 874) compared to
CLT for the same guarantees.
Robust guarantees: Hoeffing Achieves near-zero failure rate (< 2%) but at significant computational cost.
23

---

Published as a conference paper at ICLR 2026
Delributce TeMiiv Enera DPM
Dutrtbution HOeTORi Budgets
Sage!
NW
300
30
Figure 12: Hoeffding-based approximation analysis with 0.1, 0.2 and 5% oracle top-k,
showing consistently higher sample requirements than CLT.
E.2 EPPECISCCIIIC ANALYSIS
For a given query, the distribution of attention scores PLA varies significantly across different heads/layers. The adaptive design of vAttention allows for dynamic budget for given tolerance level (c, 8). Across different layers (layer 1/16/32) of the --ama-3.1-B--nsttree sure the empirical budget for the CLT and Hoeffding- baased budget estimates. In particular, for 0.2). investigate the distribution of relative errors and average budget/head in
model, mea-
(e 0.1, 8
Figures 13
15
24

---

Published as a conference paper at ICLR 2026
O -eved-Level Analysis (drop 5.0%)
033
30% ge!
Head
Mar 1:00
055
(a) CLT budget: (top-left) mean and maximum average relative per head; the dashed line is the target error tolerance (c) (top-right) the fraction queries (6) that are within the specified error tolerance (c) (bottom-left) VAttention budget per head with CLT relaxation (bottom-right) distribution of relative errors (é) across heads
Layer O- Head-Level Analysis Edrop 5.0%)
Moan and Pix Pididtrr Head
Prastin Usor Uin
Most Erel
1.3-
0.
Meant LOCTTING Budget by (lead
Dicribattonn of The ative Crrees Head
8030
4063
2890
(b) Hoeffding budget : (top-left) mean and maximum average relative emor per head; the dashed line the target error tolerance (c) (top-right) the fraction of queries (8) that within specified error tolerance (c) (bottom-left) vAttention budget per head with Hoeffding bound b << N (bottom- right) distribution of relative emrors (epsilon) across heads
Figure 13: Layer 1 analysis: For early layers, the Hoeffding budget is non- vacuous and is highly
likely to meet the verification thresholds. Further, the budget with CLT relaxation leads to much smaller budgets while providing decent likelihood with average relative error within the tolerance error (e)
25

---

Published as a conference paper at ICLR 2026
Layer
Heed Level Analysis (drap 5.0%)
Teppr po0 Mex Pere
30% oaige
2.23
8.30
Hoad
10/0
693
8327
(a) CLT budget: (top-left) mean and maximum average relative per head; the dashed line is the target error tolerance (c) (top-right) the fraction queries (6) that are within the specified error tolerance (e) (bottom-left) vAttention budget per head with CLT relaxation (bottom-right) distribution of relative errors (é) across heads
Layer 15 Head-Level Analysis (drop 5.0%)
Moan and Pix Indettrc
Head
Prastin Uuori Ulncem012
0.300
6.375
0325
0300
0.75
0.22%
01:01
Meant OOCTTINGG Budget by Ilead
Dicrrbbutton of De attve Crrees Hene
30089
02.00
22.09
Tinget CHIL
JE's parsee 2-1
Heed
(b) Hoeffding budget : (top-left) mean and maximum average relative emor per head; the dashed line the target error tolerance (c) (top-right) the fraction of queries (8) that within specified error tolerance (c) (bottom-left) vAttention budget per head with Hoeffding bound b << N (bottom- right) distribution of relative emrors (epsilom) across heads
Figure 14: Layer 16 analysis: For middle layers, the Hoeffding budget is more conservative and requires high budget meet the verification thresholds. Further, the budget with CLT relaxation leads to much smaller budgets while providing a decent likelihood with average relative error within the tolerance error (e), but have higher local errors
26

---

Published as a conference paper at ICLR 2026
Layer 31 Level-Levl Level Analysia (drap 5.0%)
Mean Mac hertthe Enarity Hladd
Frecton Quertss within cub.3
30% lagee
622
633
0.3
0.28
00
15
MedO sudjpet by Head
0120 Eudion of selor EmorS Head
Target cn13
00
(a) CLT budget: : (top-left) mean and maximum average relative error per head; the dashed line is target error tolerance (c) (top-right) fraction queries (ō) are within the specified error tolerance (c) (bottom-left) v Attention budget per head with CLT relaxation (bottom-right) distribution of relative errors (é) actoss heads
Layer 31 Heed Level Analysis (drap 5.0%)
Vean and Vaci Selettve Coler fleed
Traction of Queree is thin ruB3
Moue Free
2.29
1000 Molere sudget Moad
109C of Helltivee errees MOND
www. wear
.0.0
2000
Herd
(b) Hoeffding budget: (top-left) mean maximum average relative emror per head; the dashed line is the target error tolerance (e) (top-right) the fraction of queries (8) that within the specified error tolerance (c) (bottom-left) vAttention budget per head with Hoeffding bound << N (bottom- right) distribution of relative emrors (epsilon) across hcads
Figure 15: Layer 32 analysis: For late layers, the Hoeffding budget less likely to meet verification thresholds. Further, the budget with CLT relaxation leads to much smaller budgets while providing decent likelihood with average relative error within the tolerance error (c)
27

---

Published as a conference paper at ICLR 2026
F ABLATION OF DIFFERENT E, å CHOICES FOR NUMERATOR AND DENOMINATOR VERIFIED APPROXIMATION
Attention Density va Epsilonn (Mode: Denominator)
Attention Output Error vs Epsilon (Mode: Denominator)
0.30
3-03
Poae Peerroge Commeetch Attlette Colcud
D.pt
Avenge Beawe Abartton
0.20
02-
0.5-
66
Epetion DO
Figure 16: Denominator-verrinn approximation. Average density and average layer enror for different configurations. Note that for reasonable choices of 6, the correlations between user defined e and average layer error is very high, implying fine-graine grained control over errors. These plots are created for niah multikey with f. fi = 128, ft = 0.05, fo = 0.05 and we do not lower cap the computed budget by base sampling budget as we do in experiments to produce these plots.
Attention Density Epsilon
Attention Output Error Epsilon (Mode: Numerator)
(Mode: Numerator)
3
1-61
Avae age Tammercc Aicention Olipuul Emie
Jusrage Beweerch Densiry
0.35
0.50
0.25
0.00
Eastoon
Figure 17: Numerator- verified approximation. Average density and average layer error for different configurations. Note that for reasonable choices of à, the correlations between user defined e and average layer error is very high, implying fine- mne-grained control over errors. These plots are created for Miah_multikey 2 with fs fi 128, ft 0.05, fo 0.05 and we do not lower cap the computed budget by base sampling budget as we do in experiments to produce these plots.
Few things to note in Figure 16 Figure 17
The correlations of average layer error with in both cases is very high (almost linear relation). Which means that both the verified recipes are effective in providing fine-grained control over actual errors.
Varying the c, 5 you can span a wide range of sparsity. The settings for the numerator have be higher since numerator operates the guarantee in a higher-dimensional space (head dim). And in higher dimensions, the volume contained in e radius ball is exponen- tially smaller than in lower dimensions (e.g. 1 for the denominator)
28

---

Published as a conference paper at ICLR 2026
G BOOT STRAPPING THE o² FOR DENOMINATOR AND TR(2) FOR NUMERATOR, HOW BIG BASE SAMPLES DO WE NEED?
Table 11 shows the errors in estimating the required statistics for numerator and denominator verified recipes.
Table 11: The average error in estimating variance in the denominator (σ²) and trace in numerator (Tr(E)). We see that even with tiny samples, the important variances and traces are approximated very well. The relative error in estimation increases when we look at smaller variances, but these not not very important to estimate since the true budget associated with those variances is orders of magnitude smaller and is lower-capped by base budget in most cases in the implementation.
niah 2ull_mu 2
base sampling rate
Tokens
denominator var var 00.01
numerator trace trace
>0.01)
0.025
1000
4.74%
2.77%
0..55
2000
4.45%
3.16%
0.1
4000
3.10%
2.00%
1
base sampling rate
Tokens
denominator var 00.001
numerator trace trace > 0.01)
0.025
820
4.91%
2.67%
0.05
1640
3.78%
2.04%
3280
2.57%
1.30%
vt
base sampling rate
Tokens
denominator var var 00.001)
numerator trace trace > (.01)
0.025
820
5.31%
2.69%
0.05
1640
3.63%
1.72%
0.1
3280
2.46%
1.42%
H
QQ PLOTS FOR DENOMINATOR
Figure 18 shows that the estimator of denominator is indeed normally distributed following CLT.
29

---

Published as a conference paper at ICLR 2026
5.0%
4531
CD Pitte GMES
Head
Pitts
NEW
Figure 18: Validity of CLT: The above histogram and QQ plots show that the estimator constructed for the denominator indeed follows distribution very close the normal distribution, validating the use of CLT in the vAttention procedure. The sampling rate is relative to context window size which in this experiment 32K
30

---

Published as a conference paper at ICLR 2026
1 SENSITIVITY ANALYSIS FOR DIFFERENT PARAMETERS OF VATTENTION
To understand the stable region of parameters, we perform the following experiment. Starting from natural config
sink_size=128,
window_size=128,
HashAttenntinnTop (heavy_size=0, 05)
base pase_rate__st ptt__ratt__aapp_ll aawattessmlling..00.
epeilon=0.05,
delta=0.05,
vary each individual parameter at time in the following ranges
sink_size= 2, 4, 8, 16, 32, 64, 128] window_size=10, 2, 4, 8, 16, 32, 64, 128] HashAtrentionToop sisavvysiiee_a_e base_ @ase_rate_samplinge
0.005, 0.01, 0.025, 0.05, 0.1]
0.005, 0.01, 0.025, 0.05, 0.1]
epsilon=[C.022: 0.05, 0.1, 0.2, 0.3, 0.4, 0.5] delta=(0.025, 0. 0.05, 0.1, 0.2, 0.3, 0.4, 0.5]
The layer errors observed are presented in the following figure.
Sensitivity analysis of parameter values for qa_
0.00
Layer Error
0.75
0.70
+
Rate
Efror
Epsilon Heavy Size
0.15
Normal Dansity Layer Error Tradcoff
0.10
0.025
0.05
0.050
0.075
0.100
0.125
0.150
0.175
0.200
0.225
0.250
Density
Figure 19: The figure shows layer enror function of density while varying each parameter across a range of values mentioned manuscript. The black fitted curve represents the typical relationship between layer eтrоr and density. Different parameter settings move the system along this curve, and departures from it reveal unstable regions for each parameter. From these trends we can conclude that sink size and window size should not be extremely small. Setting either of them to zero leads to very large errors. Sink sizes of at least two and window sizes of at least sixty four remain stable. The base rate for sampling should also not be small. A value of least 0.025, meaning 2.5% of the context window, is stable. The heavy size for top k should again not be too small, and values of 0.025 or higher are stable. By choosing safe values for these core parameters, the layer error versus sparsity tradeoff can then be explored through the epsilon and delta values.
31

---

Published as a conference paper at ICLR 2026
J
WIDER EMPIRICAL RESULTS
Modkl
Densily
DoubleSpuriit
MagicPig
OracleTopk
OrackeTopP
PQCache
dense vAlientionnOraslllepph.
2%
22.00
20.67
90.58
92.27
90.91
90.89
538
25.22
91.75
90.94
201
59.57
69.25
91.08
91.33
91.17
90.63
1000%
91.02
Owen5-4B-Instraz-25000 Instrract-2507
2%
18.39
86.33
83.83
85.80
87.61
538
29.33
87.56
88.17
10%
26
39.63
87.61
88.33
87.67
M6.94
205
47.50
76.37
$8.22
87.72
87.67
88.22
10055
Llama-3.1 Inttrrr
555
52.83
24.83
83.83
87.01
83.14
86.72
10%
74.75
30,20
$6.37
$7.45
86.29
$7.50
20%
83.40
87.62
86.08
3.2-1- IB-Instruct
25
6.05
25.38
31.30
21.18
36.78
555
12.12
11.30
32.66
34.74
30.47
$7.80
10%
15.57
35.22
35.81
36.18
37,83
100%
37.47
Llama 3.2ma-3.233B 3.2--3B-nntttruu
25
18.57
17.22
41.57
51.19
39.30
59.25
5%
24.32
21.86
47.32
56.41
46,32
65.45
20%
40.25
36.19
$9.00
62.15
59.25
63.95
100%
66.25
Table 12: Model performance across different baselines and sparsity levels
32


Reviews:
[{"review_id": "59jBt6aG3i", "reviewer": "Reviewer_VSCh", "summary": "This paper introduces vAttention, a verified sparse attention method designed to address the memory and computational bottlenecks of standard scaled dot-product attention (SDPA) in large language models (LLMs) when processing long contexts.", "questions": "Please see Weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "*   **Hybrid & Adaptive:** Intelligently combines deterministic \"heavy-hitter\" tokens (sinks, local, top-k) with stochastic sampling of the tail, adapting per head and query.\n*   **State-of-the-Art Performance:** Outperforms strong baselines (e.g., HashAttention, oracle top-p), often matching full-model accuracy with high sparsity (10-15%).\n*   **Efficient Long-Context Inference:** Effectively reduces the memory and computational bottleneck of large KV caches, enabling faster generation, especially when the cache is offloaded to CPU.\n*   **Practical & Versatile:** Can be integrated with existing approximate top-k methods and works well on diverse, challenging long-context benchmarks.", "weaknesses": "*   **Relaxation of Theoretical Guarantees:** The core theoretical contribution provides an \\((\\epsilon, \\delta)\\) guarantee for the *entire* attention output. However, the authors explicitly state that in practice, they use a **relaxation that only guarantees the denominator**. While they provide empirical justification (strong correlation with final error), this significantly weakens the formal \"verified\" claim. The method is no longer provably guaranteed for the final output, but rather for an intermediate component.\n*   **Dependence on CLT and Large Sample Assumptions:** The theoretical bounds rely on the Central Limit Theorem (CLT), which holds for \"large enough\" sample sizes. The paper provides an empirical analysis (Appendix E) showing CLT is tighter than Hoeffding's bound, but the validity of the CLT approximation for *all* layers and heads, especially with small budgets, is not rigorously proven. This makes the \"verification\" approximate rather than exact.\n*   **Circular Dependency in Budget Calculation:** To compute the required sample size \\(b\\), the algorithm needs to know population statistics like the covariance matrix \\(\\Sigma\\) and the norm \\(||N||_2\\). Since these are unknown, the method uses a **base sample** (governed by \\(f_b\\)) to estimate them. The accuracy of the initial estimate directly impacts the final guarantee, creating a potential circularity that is not fully addressed theoretically.\n*   **Sensitivity to Hyperparameters:** The method introduces several new hyperparameters (\\(f_s, f_l, f_t, f_b, \\epsilon, \\delta\\)). While the paper shows a search can find good values, this adds complexity for practitioners compared to simpler methods like top-\\(k\\). The \"natural configuration\" used in AIME2024 is promising but requires validation across more diverse tasks.\n\n* **Computational Overhead of Budget Calculation:** The process of calculating the adaptive budget for each head and query, including drawing a base sample and estimating statistics, introduces **non-trivial overhead**. The paper admits this is done in \"naive PyTorch\" and that a CUDA kernel is future work. This overhead could offset the speed gains from sparse attention, especially for shorter sequences or GPU-hosted KV caches.\n*   **Dependence on Approximate Top-\\(k\\) Methods:** vAttention's performance is not standalone; it's a framework that incorporates an approximate top-\\(k\\) method (e.g., HashAttention). The results show that **\"more accurate top-\\(k\\) methods are essential for the overall quality.\"** Therefore, vAttention's weaknesses are, in part, the weaknesses of its underlying top-\\(k\\) component. If the top-\\(k\\) method fails to identify crucial \"heavy hitters,\" vAttention's sampling-based tail approximation may not be sufficient to recover.\n*   **No End-to-End Speed Evaluation:** The efficiency claims are primarily supported by a model showing near-linear speedup when the KV cache is on the CPU (Figure 5). There is **no comprehensive evaluation of end-to-end latency or throughput** (tokens/second) comparing vAttention to baselines under equal hardware and sparsity budgets. The gains for GPU-resident KV caches are stated but not demonstrated.", "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": "EaRShDo3nB", "reviewer": "Reviewer_5pmM", "summary": "This paper introduces **vAttention**, a sparse attention mechanism with verifiable accuracy control. The key observation is that top-k and random sampling are complementary: top-k captures sharp, heavy-tailed score distributions while sampling better covers near-uniform regions. vAttention unifies them: it deterministically selects heavy-hitters (sink tokens, a local window, and approximate top-k) and then uniformly samples from the residual “long tail.” Users set \\\\((\\epsilon,\\delta)\\\\) and the method computes a per-query, per-head sampling budget via CLT-based estimates. Experiments show clear gains over strong baselines and narrow the gap to full attention, matching full-attention quality under high sparsity (≈10–15% density; ≈12% at 32K) in long-generation settings.", "questions": "1. **Cost of full \\\\(N\\\\)&\\\\(D\\\\) guarantee:** What is the empirical overhead and final density increase when enforcing the full Theorem 4.3 guarantee versus the denominator-only relaxation? Is the expense dominated by estimating \\\\(\\mathrm{Tr}(\\Sigma)\\\\) for the vector-valued numerator, and can that be approximated efficiently without breaking the guarantee?\n\n2. **Budget partitioning guidance:** The method composes sink/local/top-k (deterministic) with uniform sampling (stochastic). Experiments grid-search the fractions \\\\((f_s,f_l,f_t)\\\\). Is there any theoretical prescription for allocating budget between deterministic heavy-hitters and stochastic sampling to minimize total density for a target \\\\((\\epsilon,\\delta)\\\\)?\n\n3. **Early-token behavior:** For very early tokens in long generation, when the residual set size \\\\(n_s\\\\) is small, CLT assumptions are weaker. Does Algorithm 2 switch to heavier reliance on the deterministic set \\\\(\\mathcal{I}_f\\\\) or adaptive rules for minimum base samples to keep the guarantees meaningful in this regime?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Principled guarantees.** vAttention is presented as a practical algorithm that exposes user-controllable \\\\((\\epsilon,\\delta)\\\\) error targets. Empirically, the realized approximation error correlates strongly with the user tolerance \\\\(\\epsilon\\\\) (correlation \\\\(>0.99\\\\)).\n\n2. **Robust hybrid design.** The deterministic heavy-hitter stage plus stochastic long-tail sampling is well-motivated. A simple combination of oracle-top-k with random sampling consistently outperforms either component alone.\n\n3. **Strong empirical results.**\n   - **Accuracy:** Improves over HashAttention on RULER-HARD by ≈4.5 points (e.g., +4.6 for Llama-3.1-8B and +4.3 for DeepSeek-R1-Distill-Llama-8B).\n   - **Oracle comparison:** vAttention + oracle-top-k can outperform oracle-top-p on RULER-32K, suggesting limits of pure top-k/top-p schemes.\n   - **Long generation:** Matches full-attention quality on AIME@32K at ≈12% average density; at ≈16K, densities around 10–15% are reported.", "weaknesses": "1. **Theory–practice relaxation.** The paper proves joint \\\\((\\epsilon,\\delta)\\\\) guarantees for **both** SDPA numerator \\\\(N\\\\) and denominator \\\\(D\\\\) (Theorem 4.3), leveraging a composition of bounds (with Lemma 4.2 for separate approximations). Computing the full budget is reported as expensive. Consequently, **all experiments** adopt a relaxation that provides an \\\\((\\epsilon,\\delta)\\\\) guarantee **only for the denominator** \\\\(D\\\\). The “verified” claim in practice is therefore supported by the strong empirical correlation \\\\(>0.99\\\\) rather than the full \\\\(N\\\\)&\\\\(D\\\\) guarantee.\n\n2. **Budget/latency overhead under-measured on GPU.** Speedups are shown in memory-bound regimes with KV on CPU and with a naive PyTorch implementation. A CUDA kernel is left to future work. The end-to-end latency trade-off when KV fits in HBM is not fully benchmarked, so the actual GPU-resident benefit remains uncertain.", "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": "WwVr7SlkBd", "reviewer": "Reviewer_YGRV", "summary": "This paper introduces vAttention, a sparse attention mechanism that unifies deterministic top-k selection with sampling-based estimation and provides formal ($\\epsilon, \\delta$)\nguarantees on the approximation of full attention. Theoretical results show that the estimator achieves bounded error under Central Limit Theorem–based sampling, and experiments across Llama-3.1, DeepSeek, and Mistral models demonstrate strong quality-efficiency trade-offs, often outperforming existing top-k methods.", "questions": "This paper is solidly motivated and theoretically sound, and the idea of providing formal guarantees for sparse attention is timely. However, several issues limit its empirical completeness and clarity. Below, I describe these concerns and follow with specific technical questions.\n\nThe relaxation that approximates only the denominator is a major simplification. While it is argued to control bias and match observed errors, there is no ablation comparing the full \n $(\\epsilon, \\delta)$ approximation to this relaxed version. The paper would benefit from quantifying how much quality or efficiency is gained or lost through this relaxation. In addition, since the method introduces user-defined $(\\epsilon, \\delta)$ parameters, it would be useful to know how these affect token selection and runtime. The paper does not clearly show how many tokens are chosen for a given accuracy on the benchmark compared to baselines.\n\nThe efficiency evaluation focuses on CPU-bound experiments and does not provide GPU results. Sparse attention acceleration is most relevant for GPU decoding workloads, so the lack of CUDA implementation or end-to-end throughput measurements makes it hard to judge the real benefit. Even a partial GPU prototype would help demonstrate scalability.\n\nThe comparison with oracle top-p is not conclusive. In some plots (Appendix A.1), vAttention performs worse than oracle top-p at the same density, but this is not discussed. Since top-p offers a different adaptive coverage mechanism, further comparison or integration could clarify the relative advantages.\n\nFinally, parameter tuning remains underexplained. The authors mention grid search over $(\\epsilon, \\delta)$ and sampling fractions but give no practical guideline for setting them. For deployment, it would be important to know if there exists a stable range that generalizes across models or if these need per-benchmark tuning.\n\n\nQuestions:\n\n1. How large is the empirical performance gap between the full numerator-denominator estimation and the denominator-only relaxation?\n\n2. In Eq. (5), the deterministic and stochastic terms are directly summed. Would importance weighting or probability normalization further reduce bias?\n\n3. Are there engineering challenges that prevent implementing the methods in CUDA? Could it reuse GPU primitives for top-k?\n\n4. What are the average token counts or densities achieved under different $(\\epsilon, \\delta)$ values, and how do they translate to runtime gains on GPU?\n\n5. When vAttention underperforms oracle top-p at fixed sparsity, is that due to attention distribution skewness, or to the approximation of only the denominator? Could vAttention be compatible with existing top-p methods?\n\n6. Why does vAttention sometimes outperform dense attention on AIME (Table 2)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The mathematical derivation is clear and connects attention approximation to classical sum-estimation theory.\n\n2. Shows consistent empirical gains on long-context benchmarks and stable long-generation quality.\n\n3. The framework is compatible with existing top-k implementations.\n\n4. Writing and organization are clear, with well-motivated theoretical and experimental sections.", "weaknesses": "1. No ablation on the relaxation that only approximates the denominator.\n\n2. No GPU runtime results or CUDA implementation to verify efficiency gains.\n\n3. Missing quantitative reporting on selected token counts and achieved sparsity.\n\n4. Comparison to oracle top-p and newer top-p-based methods is incomplete.\n\n5. Parameter selection procedure for $\\delta$ and $\\epsilon$ is heuristic and underexplained.", "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": "yzZyhoNCDS", "reviewer": "Reviewer_rduG", "summary": "This paper combines top-k attention with a token sampling approach, seeking an interpolation of the two. It seeks provable and tunable approximation guarantees of the attention function and a practical method that can be deployed to save time and memory without sacrificing model quality. Numerous experiments are performed against many benchmarks to validate the method's performance.", "questions": "1. For the experimental section, it is mentioned that it is expensive to calculate the numerator so it is skipped? Why is it expensive? How can we afford to skip that approximation without suffering later on? This seems to be a different algorithm than what was argued earlier.", "limitations": "", "rating": 2, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written, with the exception of some details. It is concise, to the point and effective at communicating its message. \n2. The paper tackles the important problem of achieving efficient attention in Transformers without sacrificing model quality. Improvements in this space undoubtedly have profound consequences on the landscape of AI. In this space, the paper contributes a method that offers a lot of practical promise by combining the existing approaches of top-k and sampling attention.\n3. The paper performs numerous experiments on a variety of benchmarks to support its claims. There are also lots of ablation studies with other attention methods. \n4. The paper quantifies the tradeoff between approximation quality and model decline, at least empirically. This is something very few works in this space do, so it is an important contribution by itself.", "weaknesses": "1. The idea of combining sampling and top-k attention is not novel to this paper. The work of [1], for instance, seems to precisely propose the vAttention estimator in eq. (5). Furthermore, [1] also analyzes the approximation guarantees of their estimator rigorously. Beyond [1], numerous other works rigorously analyze the approximation quality of subquadratic attention mechanisms [2,3,4], making me feel uneasy about this paper's claim to  be the \"first\" algorithm to rigorously allow for quality-efficiency tradeoff control. I would say that the point of departure of this work from [1] and other such works seems to be mainly the fact that this work makes the sample size a tunable hyperparameter, and I worry that this is not a novel enough contribution. \n    * That being said, the experimental and empirical study provided by this paper are another one of its contributions. Prior works have not analyzed top-k attention in such an extent, so these insights are definitely valuable to the community. However, the paper is suggesting that it is the first to propose these methods and rigorously analyze them, which, in my opinion, is not accurate. \n2. The mathematical rigor of the paper has some notable issues:\n    * Lemma 4.1: The $\\Phi$ function in Lines 301-303 is applied to the entire term? It is a little hard to see what's happening here.\n    * Lemma 4.1: Why are $r_i$ considered random variables with some covariance matrix $\\Sigma$? The distribution on the scores is highly unknown and $\\Sigma$ is impossible to estimate. Yet the lower bound on $b$ depends on the trace of $\\Sigma$. The authors mention this and ultimately set the threshold arbitrarily, but the formal algorithm cannot be stated in terms of this $\\Sigma$.\n    * Lemma 4.1: The use of CLT here is a bit troublesome. The argument can only work in the limit $n_s \\to \\infty$, in which case I am also confused as to how the lower bound is ultimately proven. Hoeffding's inequality can salvage things and give a concrete bound, but the paper does not have this proof. Instead it is claimed that in practice the CLT-bound is superior, which again raises the question of how $\\Sigma$ is calculated. As a whole, Lemma 4.1 is a bit weak in my opinion.\n    * Lemma 4.2: This is the approximation guarantee. I don't think it parses very well: The probability is multiplied with $||N/D||_2$? Also, the statement is shown for $||N||_2/D$ instead in the appendix.\n\nOverall, the paper makes a compelling case for the use of top-k and sampling attention (or interpolation of these) in practice. However, I feel like it currently suffers from issues of originality and rigor.\n\n[1] Haris, Themistoklis. \"kNN Attention Demystified: A Theoretical Exploration for Scalable Transformers.\" The Thirteenth International Conference on Learning Representations.\n[2] Han, I., Jayaram, R., Karbasi, A., Mirrokni, V., Woodruff, D. P., & Zandieh, A. (2023). Hyperattention: Long-context attention in near-linear time. arXiv preprint arXiv:2310.05869.\n[3] Choromanski, K., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J., Mohiuddin, A., Kaiser, L. and Belanger, D., 2020. Rethinking attention with performers. arXiv preprint arXiv:2009.14794.\n[4] Alman, Josh, and Zhao Song. \"Fast rope attention: Combining the polynomial method and fast fourier transform.\" arXiv preprint arXiv:2505.11892 (2025).", "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)