SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inference
Authors: Jintao Zhang
Chendong Xiang
Haofeng Huang
Jia wei
Haocheng Xi
Jun Zhu
Jianfei Chen
Venue: ICML 2025 poster (2025)
Keywords: Efficient attention
sparse attention
inference acceleration
Dit
Video generation
AI Infrastructure
LLM Infrastructure
Primary area: deep_learning->attention_mechanisms
TL;DR: Accurate and Training-free Sparse Attention Accelerating Any Model Inference

Abstract: An efficient attention implementation is essential for large models due to its quadratic time complexity. Fortunately, attention commonly exhibits sparsity, i.e., many values in the attention map are near zero, allowing for the omission of corresponding computations. Many studies have utilized the sparse pattern to accelerate attention. However, most existing works focus on optimizing attention within specific models by exploiting certain sparse patterns of the attention map. A universal sparse attention that guarantees both the speedup and end-to-end performance of diverse models remains elusive. In this paper, we propose SpargeAttn, a universal sparse and quantized attention for any model. Our method uses a two-stage online filter: in the first stage, we rapidly and accurately predict the attention map, enabling the skip of some matrix multiplications in attention. In the second stage, we design an online softmax-aware filter that incurs no extra overhead and further skips some matrix multiplications. Experiments show that our method significantly accelerates diverse models, including language, image, and video generation, without sacrificing end-to-end metrics.

SpargeAttention:
Accurate and Training-free Sparse Attention Accelerating Any Model Inference
Jintao Zhang"
Chendong Xiang" !
Haofeng Huang" 12 Jia Wei
Haocheng Xi
Jun Zhu'
Jianfei Chen
https://github. http:/ub...ootttmmm////aarraaaee
Abstract
Full Attention End-to-End 1897s on L40
An efficient attention implementation essen- tial for large models due its quadratic time complexity. Fortunately, attention commonly ex- hibits sparsity, i.e., many values in the attention map are near zero, allowing for the omission of corresponding computations. Many studies have utilized the sparse pattern to accelerate at- tention. However, most existing works focus on optimizing attention within specific models by exploiting certain sparse patterns of the atten- tion map. A universal sparse attention that guarantees both the speedup and end-to-end performance of diverse models remains elu- sive. In this paper, we propose tn. a universal sparse and quantized attention for any model. Our method uses a two-stage on- line filter: in the first stage, we rapidly and ac- curately predict the attention map, enabling the skip of some matrix multiplications in attention. In the second stage, we design an online softmax- aware filter that incurs no extra overhead and fur- ther skips some matrix multiplications. Experi- ments show that our method significantly acceler- ates diverse models, including language, image, and video generation, without sacrificing end-to- end metries. The code is available at https! / //github. com http:thhummmmmp/ /Stp//ttaaggttttnom
SpargeAttn End-to-End Time:
1037s L40
1.83x Speedup
Figure I. Spar rgeattetttt tn can achieve 1.83x speedup on Mochi on L40 GPU, with no video quality loss.
1. Introduction
As sequence lengths in large models become longer, such as 158K in video generation and language models (Yang
at.
Bao et al. 2024 Dubey et al. [0224] Zhang the time consuming of attention occupies significant portion of inference latency in large mod- cls (Zhang et al. 2025d). Fortunately, the attention map Softmax QK /Vd) exhibits inherent sparsity, as the softmax operation often creates many values approach- ing zero (Deng al. 2024). Sparse attention exploit such sparsity to accelerate attention by (1) constructing a "sparse mask", which indicates the important non- non-zero entries of the attention map P that should be computed, and (2) comput- ing attention only for the parts corresponding to the sparse mask. There are three distinct categories of sparse atten- tion methods based on how the sparse mask is generated. puttern-based method (Zhang et al. 2023 Xiao et al.
2025b
et al. 2025c),
2024a
Fu et al.) 2024] Zhu et al.) 2024 Xiao et al.) 2025
2024b
Eqqual contribution Dept.. of Comp. Sci. and Tech., Insti- tute for AI, BNRist Center, THBI Lab, Tsinghua-Boss Bosch Joint ML Center, Tsinghua University IInstitute for Interdisciplinary Information Scienees, Tsinghua University 'EECS, University of California, Berkeley. Correspondence to: Jun Zhu <dc- szj @ mmii..ssighua..cuuccm
Zhang et al. 2025h) relies on specific sparsity patterns based on empirical observations, dynamic sparse attention (Ribar
et al. 2024
Singhania et al. 2024, Jiang et al., 2024] Lai
et al 2025 Gao et al. 2024 Xi et al. 2025 Yang et al.
2025a Zhang et al. 20251) computes the mask on-the-fly
based the inputs, and
method (Kitaev
Proceedings of the 4dnd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
et al. 2020 Pagliardini et al.) 2023 Zhang et al.] 2025i directly train models with native sparse attention.
All experiments using SpargeAttn is based on SageAttention. An updated implementation based on SageAttention2, is avail- com/ httttthumm/ss///e httl//ppaggttttt. It further offers a 30% speedup over the attention in this paper.
Limitation. (L1. Universality) Though existing sparse at-
able
tention methods already demonstrate promising speedup on some tasks, their universality still limited. Existing works

---

Sparge-Atenntoo: Accurate and Training-fre Sparse Attention Accelerating Any Model Inference
typically developed for specific tasks, such language modeling, utilizing task-specific patterns such sliding windows or attention sinks. However, the attention pattern varies significantly across tasks (see examples in Fig. 2). making these patterns hard to generalize. (1.2. Usability) Moreover, it is difficult to implement both accurate and efficient sparse attention for any input. This because ac- curacy demands precise prediction of the sparse regions in the attention map, while efficiency requires the overhead of this prediction to be minimal. However, current methods are difficult to effectively satisfy both of the requirements si- multancously. For example, MInference (Jiang et al.) (2024) requires a large sequence length, such as 100K, to achieve a noticeable speedup.
CogvideaX
Stable- Diffusion3.5
Goal. We aim to design a training-free sparse attention operator that accelerates all models without metrics loss.
Uama3.1
Our approach. In this work, we develop SpargeAttn, training-free sparse attention that can be adopted universally on various tasks, including language modeling and text-to- image/video, and various sequence lengths. We propose three main techniques to improve the universality, accuracy, and efficiency. First, we propose universal sparse mask prediction algorithm, which constructs the sparse mask by compressing each block of Q, K to single token. Impor- tantly, we compress selectively based on the similarity of tokens within the block, so the algorithm can accurately predict sparse masks universally across tasks. Second, we propose a sparse online softmax algorithm at the GPU warp level, which further omits some PV products by leveraging the difference between global maximum values and local maximum values in online softmax. Third, we integrate this sparse approach into the 8-bit quantized SageAtten- tion framework for further acceleration.
Figure 2. Some sampled patterns attention map P in video, image, and language generation models.
ct al. 2025) rely on sliding window pattern. SampleAt- tention (Zu et al., (024). MOA (Fu et al.) (024)) and
StreamingLLM (Xiao et al. 2024b) rely on sliding window and attention sink pattern. DitFastAttn (Yuan et al. 2024)
relies on sliding window patterns and similarities between different attention maps. Moreover, DitFastAttn is restricted to simple diffusion transformers, showing incompatibility with language models and MMDiT models like Flux (Black Forest Labs 2023), Stable Diffusion3 and 3.5 (Stability Al 2023), and Cog VideoX (Yang et al., 2025b). As the pattern varies across models, these methods may not universally work for different models. (2) Dynamic sparse methods dynamically construct the sparse mask based the input without the need of preset patterns, and are thus potentially more universal. Existing works can be further categorized into channel compression and token compression. Channel compression methods include SparQAtth (Ribar et al. 2024 and LokiAttn (Singhania et al. 2024). They construct the mask by carrying full attention with reduced dimensionality. However, the dimension is already small, e.g., 64, 1 128, in commonly used attention, the speedup potential might be limited. Token compression methods include MInfer- ence (Jiang et al. 2024) and FlexPrefill (Lai et al. 2025). They construct the mask by compressing each block of to- kens to single token and compute attention on this shorter sequence. However, this approximation is too aggressive: missing important blocks of P is possible if they do not have large attention score on the compressed sequence. SeerAttention (Gao et al. (024) requires training of addi- tional parameters for attention, which is expensive to use. Moreover, they are all designed for language models, and their applicability to other model types, such as diffusion models, remains uncertain. (3) Training-basee methods
To the best of
our knowledge, SpargeAt tn is the first sparse attention method that can actually accelerate across language, image, and video models without compromising accuracy.
Result. We evaluate SpargeAttn a variety of gen- erative tasks, including language modeling and text-to- image/video, with comprehensive performance metrics on the model quality. SpargeAtt can robustly retain model end-to-end performance while existing sparse attention base- lines incur degradation. Moreover, Spa rg 2.5x 5x faster than existing dense and sparse attention models.
2. Related Work
Depending on how the sparsity mask is constructed, sparse attention methods can be divided into three types: (1) Pat- tern required methods rely on some fixed patterns of the attention map, such as sliding windows or attention sinks (Xiao et al.] 2024b). H20 (Zhang et al. 2023). InfLLM (Xiao al. 2024a), and DUOAttention (iaao
2

---

SpargeAttention:: Accurate and Training-free Sparse Attention Accelerating Any Model Inference
modify the attention computation logic, requiring retraining the entire model, such Reformer (Kitaev et al. 2020) and FastAttention |Pagliardini et al. 2023). These methods are much more expensive to use than training-free methods.
is either 0 or 1. These masks determine which computations are skipped in the sparse attention mechanism. Definition 2 (Sparse FlashAttention). The computation rules for sparse FlashAttention based on the masks are de- fined as follows:
There are other ways to accelerate attention, such as opti- mizing the kernel implementation (Dao et al. 2022 Dao 2024,
Q.K.. PuVy are skipped if Mg[t,]] = 0.
(2)
Shah et al., 2024), quantization (Zhang et al. (025d). distributing the workload (Liu et al., (2024a), and designing
PoVy is skipped if Mpa =0.
(3)
linear time attention (Wang et al. 2020 Choromanski et al.
2021
Yu et al. 2022 Katharopoulos et al. 2020). They are
3.2. Selective Token Compression for Sparse Prediction
orthogonal to our approach.
Key idea. Although attention maps vary across models, we observe that various models exhibit a common trait: Most neighboring tokens in the query and key matrices of the at- tention show high similarity (See Fig. A. Consequently, for blocks composed of highly similar tokens, we consoli- date these tokens into single representative token for the block. Based on this observation, we propose a pattern-free online prediction method for identifying sparse blocks in P to skip some computation of Q,K, and PvyV, during the Fttentttention process. Specifically, we first compress blocks exhibiting high self-similarity within Q and K into tokens. Then, we swiftly compute compressed attention map P using the compressed Q and K. Finally, we selec- tively compute {Q.K, Pı5Vi} for those pairs (i,j) where [P[i,j]} accumulates high score in the compressed atten- tion map. Notably, block selection was only performed in the high self-similarity blocks, which we also refer as "se- lective blocks." For those non-self- similar blocks, as good presentation token for the whole block is hard to find, we choose to always compute the non-self-similee block in the attention operation, which we also refer to as "fix blocks." " Importantly, compressing only the token blocks with high self-similarity is crucial, as omitting computations for fix blocks can result in the loss of critical information. This will be confirmed in Sec. 4 and
3. SpargeAttn
SpargeAIth t contains a two-stage online filter to imple- ment sparse FlashAttention. First, as shown in Step1 and Step2 in Fig. 3 we design fast and accurate method to predict the sparse block in the attention map, thereby skipping the corresponding products of K;Kj and P.ş V-- Second, as shown in Sp in Fig. S we design a sparse online softmax method to further skip the products of P.g Vy-
3.1. Sparse FlashAttentin
SpargeAItn adopts the tiling strategy of FlashAtten- tion (Dao 2024). and skip computing the blocks that are filtered out. Consider an attention operation = QK /Vd. P = (S), O = PV, where (S)).) exp((.))/ Ex exp(S is the softmax operation. Let N be the sequence length and d be the dimensionality of each head; the matrices Q, K, and V each have dimensions N x d, while the matrix S and P is N x N. PlashAttention proposes to tile Q. K, and V from the token dimension into blocks {Q,), {Ka), [V.) with block sizes by. bj. bj. respec- tively. Then, it uses online softmax Miilakov & Gimelshein 2018) to progressively compute each block of O, i.c., O,:
S.y = Q.KJ /Vd, (may. Poy) (m. Sit).
Prediction. As shown in Stepl in Fig. 3 we first compute mean cosine similarity across tokens for each block of Q and K. Next, we compress each block into a single token by calculating a mean across tokens. Then, we compute a compressed QKT using the compressed Q and K. Finally, to prevent interference from the block similarity less than aaper-parameter 8, we set the corresponding values in S to -oo and then obtain a compressed attention map through softmax. This algorithm can be expressed as:
4g = exp(mi.j 111 mi Mag-1 + rowsum (Pis), Oiy = diag (cxp(ma.j- m.²)) Oij-1+ + P.VVV, (1)
where my and lÚj are by x 1 vectors, which are initialized to -oo and 0 respectively. The ă() is an operator similar max(ma,j-.. (m..j-1, rowmax(S.;),, } P.j exp(S.g - m. Finally, the output O2 can be computed by O = diag((4,)-10) OO,..
blocks, i.e.,
to softmax.: maj- = max
Implementing sparse FlashAttention intuitive. By skip- ping certain block matrix multiplications of K.K3 and P.yVy. we can accelerate the attention computation. We formulate sparse attention based on FlashAttention in the following definitions.
q = { = {mean( (Q,, axis = 0))
k: = (k,) = {mean( (K,, axis = =0)
8.i = CosSim(Q:), 8kj- = CosSim(()
Š = qik: $1:,5] = -o, If sky < 0
Definition 1 (Block Masks). Let Mg and Mp be binary masks of dimensions [N/b,] x [N/bx], 1. where each value
P = Softmax(S1p) ($1:))
3

---

Sparge-Ateentio:: Accurate and Training-fre Sparse Attention Accelerating Any Model Inference
Stepl. Sparse Block Online Prediction
Step2. Sparse Block Online Masking
K
K2 2
K3
K4
K
N
K1
K2
2
K3
K4
FlashAttention Inner Loop
Low Cosine Similarity
Q1K1
SKIP
4143
SKIP
Mean Pooling
Self Cosine Similarity
High Cosine Similarity
Compute the Local Max Mocal
Matmul+ Softmax
22
Kig
Update Every
Iteration
711
m23
772...
FlashAtfention Inner Loop
GRU Warp
V1
0.9
1
0
Mean
42
0.1
0.9
0
IF max MMocal Mylobal) <
N
Q2
Pooling
43
Migloba
Then Further Skip PV
V2
Top
V3
Q3
Self Cosine Similarity
For
Row
O
to
0
O
Vi
SKIP
SKIP
SKIP
VA
Block Sparse Mask
Step3. Sparse Warp Online Softmax
Figure 3. Workflow SpargeAttn.
Algorithm 1 Implementation of SpargeAttn.
I: Input: Matrices (FFP16), K (FP16), V (FP16) E R Nxd block size by, buc. count of GPU Warps c.. parametarssssers т, 0, and A.
2: Divide Q to T.. = N/b, blocks {Q:}: divide K, V To N/bb.. blocks {K.} and (V:).
3: Qu Ky 8q. 6x Quant Q,, K2 ) // per-block quantization in SageAttention.
4: q = {4:} = {mean((; axis 0)} & [ky} (mm]==(man((((
axis 0)}
5: = qk" Syx = CosSim Q.); 8kj = (aSSim(K)); $[:.]] = oc, If skj < 0;
Pli Softmax(S[t))
M(.:]] TopCar(Pl() M[.: 1, snz 0: M [.
If skj 0:
7: for = to Tm do
8: Load Q; and [i into SM;
9: for j in [1, T.] do
A. [[ j]
then
11:
Load K, Vg, and 6x [o] into the SM; S.y Matmul(Q Qu, K3) x 8q x 8x /// dequantization of SageAttention.
12:
13:
Macal = rowmax (S.z); mij max(mn;, j-1, Mocca)) P. = exp(Sig mis); 1y =e em rowsum(P.) (:)):
1. range(c..) In Ln= (1)+b)
14:
6w
15:
if max (axxmmaall22 [w] miy mis(Tw) [To)) > X then
16:
end [T, diag(e"".. - my [nl) 1 [ Matmul (Ptmul(PP[[a)... Vz) :// Paralleled by ou warps.
17:
18:
end if
end for
20:
O = diag(14.r.)-10...
21:
Write O
22:
end for
23:
return O {
where Q, E Xd and CosSim(X) mean( max[XX measures the cosine-similarity within a block.
9s E IR 1xd K5 E Rdxxd maxd,k ky E Rixd
in MMli, :], while all other positions are set to 0.
Mgli, :] (P)),)
(4)
For each row of P. i.e., PM. we select the positions of
where the TopCdf (P(i) can be formulated follows.
the top values whose cumulative sum reaches - "' P(i). where 7 is hapeeeparameter. These positions

---

SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inference
by exp(m - mma) and then plus the Pay Vz:
128 Tokens
128 Tokens
CogvideoX
Mocall =rowmax(S4)); maj max (0 Mocal)
Channel
Channel
1.9
13
0 diag (exp(ma.j-1 m.;)) 0 1 P.yV,
Stable-
Diffusion3.5
If rowmax (Siz) < maj. then myj - mi.-i Consequently, Oi = O P.yV, Furthermore, if rowmax < myy holds true, then all values in P.- exp(S.) m.y) are close to O. This results in all values in Pi being close to O. This condition implies that P.yV; is negligible when rowmax(Si;)
128
128
Channel
Channel
120 "olcems
Llama3,1
120
Siy) ) is significantly smaller than m,y:
K
120 Tokers
Flux
Ois ~ Ot.-11 if max (exp(S.) - mzy)) - 0 max (exp(Sig - -mm)) + 0 <> max(1 mi)) < X
Channel
Channel
Figure 4. Exemplary patterns of the query and key in the attention of various models.
The above equivalence is satisfied when À is small enough.
Therefore, based on the analysis above, we propose a sim- ple yet effective sparse method to further skip the V computation. Specifically, in the inner loop of FlashAtten- tion, the Sig will be split by Cu GPU warps to {St,]
det Top_cdt (P[1), taul:
sozted_P, idx serch.sort [ descerding-True) dim-0)
cusum_F - wwrch. cumeum
mask cusum_P <- tau P[il ()
M_1 - zeroc..eroo_.liee like (mask) [_i[ddx] - mask return M_1
[fw
Our ::],. where in is the index of the GPU warp. Let
I = =luueb (bm+t))mb If max [mm] may [w]]]To]) < A, where is small enough, then Oig [m]] s Oiz- [4m] and we will skip the computation of P.j [n][n]V which is used to update Oig(
Finally, we need to ensure that calculations involving non- self-similar blocks(fix block) of Q or K are not omitted. Therefore, we set all values in the rows of My corresponding to not self-similar blocks of Q to 1, and all values in the columns of My corresponding to non-self-similat blocks of K I.
3.5. Combined with SageAttenting
To further accelerate our implementation of sparse attention, we integrate our method into SageAttention (Zhang et al.,
Mgli :] 1, If s6i < 0; Mglis]] = 1, If 8kj < 0 (5)
2025a bl). which proposes a quantized method for ac- celerating attention. Since quantization (Hu et al. 2025 Zhang et al., 2025i) operations and sparse operations are orthogonal, sparse computation can be directly applied to SageAttenntion. The complete algorithm is shown in Algo- rithm Specifically, first, we need to add one judgment at the beginning of the inner loop of SageAttenntinn (Line 10, [ to decide whether to skip the whole inner loop once. Second, we add another judgment before the updating of O.j in the inner loop of SageAttention (Line, in Algorithm M to decide whether to skip the computation of Pey Vg. Moreover, minimize the attention map prediction overhead, implement the prediction using CUDA and adopt some kernel fusion techniques.
3.3. Masking of the First Stage
Masking, The M2 can be applied in FlashAttention di- rectly save some computation. In the inner loop of FlashAttention, ie.. during computing attention between Q, and [K [Vi), we can skip (Q.KJ, P.yVz Vi} when Ma M =. O.
Skip QuKJ and PoV,, If M,bi.]= 0
(6)
3.4. Sparse Warp Online Softmax
Key idea. We can further identify the small enough values in the attention map during the online softmax process. If all values in Ps are close enough to zero, the P.jV, V, will be negligible and can be omitted.
3.6. Hy Alyper-parametee Determination for Model Layer
Based the method description in Sec. 3.2 and 3.4
method incorporates three hyper-parameters. T (0, 1),
0 E (-1, 1), and X < 0. The parameter determination pro- cess for each attention layer in any model is straightforward. We aim to identify a set of hyperparameters that not only maximize attention sparsity but also constrain the attention
To identify which P,, = exp(S,3 - mi.)) (See Sec. 3.1 contains values small enough to be omitted, we note that in every inner loop of FlashAutention, the Oi will be scaled
5

---

SpargeAttention: Accurate and Training-fre faeining-free Sparse Attention Accelerating Any Model Inference
error across five different model inputs. To evaluate atten- tion accuracy, we employ a strict error metric, the Relative LI distance, defined as L1 = 1 [O). The process begins by setting two LI error thresholds 1 and l2, e.g. 1 = 0.05, 1/ = 0.06. We first conduct grid search for T and 0 to identify the optimal pair that maximizes sparsity while ensuring L1 < 4. Subsequently, we perform an- other grid search for À to find the optimal value that further maximizes sparsity while maintaining L1 < lz.
text-to-text, CogvideoX (2B), Mochi Team 2024
and Open-Sora-Plan (Lin et al.) 2024) for text-to- video, Flux (.I-dev) (Black Forest Labs,
2023) and
Stable-Diffusions 5 (large) (Stabilityy Al 2023 for text-to-imaae.
Datasets. The Text-to-text model is evaluated on four zero- shot tasks: WikiText (Merity et al. 2017) to assess the model's prediction confidence, Longbench (Bai et al. 2024) and Mn.MC of InfiniteBench (Zhang et al. 2024 for a com-
prehensive assessment of long context understanding capa- bilities, and the Needle-in-a-Hayste to assess the model's 's retrieval ability. Text-to-video mod- els are evaluated using the open-sora (Zheng et al., 2202cc)
Tokens a block are not self sim
All block are self-sim
task (Kamradt 2023)
buck)
Row unjjot onder Flattex
Hilbert order Fluttes
prompt sets. Text-to-image models are assessed on COCO annotations (Lin et al. 2014).
End-to-end metries. For L1ama3. 1, we use perplex- ity (ppl.) (Jelinek et al. 1977) for WikiText, Longhench score (Bai et al. 2024), and retrival accuracy for the Needle- in-a-Haystack task (Kamradt 2023). For text-to-video mod- cls, following Zhao et al. (2025b), we evaluate the quality of generated videos on five metrics: CLIPSIM and CLIP- Temp (CLIP-T) (Liu al. 2024b) to measure the text-video aligmment; VQA-a a and VQA-t to assess the video aesthetic and technical quality, and Flow-score (FScore) for tempo- ral consistency (Wu et al.) 2023). For text-to-image mod- els, generated images are compared with the images in the COCO dataset in three aspects: FID (Heusel et al. (017) for fidelity evaluation, Clipscore (CLIP) (Hessel et al. 2021) for text-image alignment, and ImageReward (IR) (Xu et al. 2024) for human preference.
Visual tokera Thitearne
UNdjooent tolens similar color)
Notself siza Mooks
- Reonder patt
SSpli blocks
Figure 5. Illustration of different token permutation methods in 1 6 x space, with block size of 4.
3.7. HilbertCurve Permutation
Key idea. Improving sparsity while maintaining accuracy is a key challenge in enhancing the performance of sparse attention. In our algorithm, increasing the self-similarity of key and query blocks can reduce the number of fix blocks. This allows more selective blocks to participate in TopCdf selection, thereby improving sparsity. Since at- tention is computationally invariant token permutations, the problem reduces to finding a permutation that enhances the similarity of adjacent tokens.
Speed and sparsity metric. We use TOPS (tera operations per second) to evaluate the speed of sparse attention meth- ods. Specifically, TOPS = ((att) /t, where (attn) rep- resents the total number of operations in a standard attention computation, and is the latency from a given (Q, K, V) to the output of attention. Note that this speed metric is completely fair. This is because the O(attn) is fixed for set of inputs, and then the speed is determined by 4, which includes the time spent predicting the sparse region of the attention map. We define Sparsity as the proportion of the Matmul of K,KJ plus P.y V, that are skipped relative to the total number of Q:KJ plus PtyV V2 in full attention required.
Image and video models benefit from strong priors: adjacent pixels are likely to be similar. To better leverage this prior, we propose the HilbertCurve permutation, given 3D visual tokens Q, K, V Tx Wxxd We use the Hilbert Curve to fill the 3D space and then flatten tokens along the curve into shape RR-xd L- T x H x W. Fig. 5 illustrates an example of 1 x 6 x 6 visual tokens flattened by row- major order and HilbertCurve. The Hilbert Curve preserves locality effectively, traversing the entire 3D space without crossing rows or columns, thereby increasing the similarity of adjacent tokens and the sparsity of attention.
Implementation and Hypee-ppraametes. We implement our method using CUDA. As discussed in Sec. 3.6 we need to determine 4, 12 for models. We use (h, = 0.08, l2 =
4. Experiment
0.09) for Ll Llama3.3 1, (4 = 0.05, l2 = 0.06) for CogvideoX and Mochi, and (12 = 0.07, 12 0.08) for Stable-Di Del--iiffuii ffuiiinn. 5 and F Flux, (11 0.03,, lg 0.035) for Open-Sora-Pi
4.1. Setup
Models. We validate the effectiveness of SpargeAttn across diverse representative models from language, im- age, and video generation. Specifically, we conduct ex- periments on Ilamaa. (8B) (Dubey et af.) 2024) for
Baselines, Currently, sparse attention methods applicable
6

---

SpargeAtteenton:: Accurate and Training-fre Sparse Attention Accelerating Any Model Inference
Table End-to-end metrics across text, image, and video generation models. indicates inability to generate results for evaluation.
The speed and sparsity are the average for each layer in the model in real generation tasks described in Sec. 4.1 Llama3. are measured the Needle-ing Haystack task 128K sequence length.
The speed and sparsity of
Model (ee)
Attention (Sparsity)
Speed (TOPS)
Wikifext (Ppl.)
Longbench t InfiniteBench
NIAH
Full-Attention
156.9
6.013
38.682
0.6399
0.907
Minference (0.5)
140.1
10,631
28,860
0.5152
0.832
Llama3
FlexPrefill (0.5)
240.6
6.476
38.334
0.6460
0.858
(128K)
Minference (0.3)
115.7
6.705
34.074
0.6532
0.870
FlexPrefill (0.42)
206.9
6.067
38.334
0.6581
0.878
SpargoAt tn (0.54)
708.1
6.020
39.058
0.6638
0.909
Model (seq]een)
Attention (Sparsity)
Speed (TOPS)
CLIPSIM
CLIP-T
VQA-a f
VQA-t
FScore 1
Full-Attention
166.0
0.1819
0.9976
80.384
75.946
5.342
Minference (0.5)
264.6
0.1728
0.9959
70.486
62.410
2.808
CogvideoX
FlexPrefill (0.6)
175.3
0.1523
0.9926
1,5171
4.5034
1.652
(17K)
Minference (0.3)
196.9
0.1754
0.9964
77.326
63.525
3.742
FlexPrefill (0.45)
142.0
0.1564
0.9917
7.7259
8.8426
2.089
SpazgeAt (0.46)
507.9
0.1798
0.9974
78.276
74,846
5.030
Full-Attention
164.2
0.1725
0.9990
56,472
67,663
1.681
Minference (0.5)
202.4
0.1629
0.9891
6.668
50.839
0.653
Mochi
FlexPrefill (0.48)
191.3
0.1667
0.9898
0.582
0.0043
(22K)
Minference (0.3)
147.7
0.1682
0.9889
14.541
42,956
0.833
FlexPrefill (0.4)
171.7
0.1677
0.9909
2.941
0.7413
X
SpargeAt (0.47)
582.4
0.1720
0.9990
54.179
67.219
1.807
Model len) Sppen-Scr--i aaan (38K)
Attention (Sparsity)
CLIPSIM
CLIP-T
VQA-a
VQA-L
FScore
Latency
Full-Attention
0.1650
0.9994
81.40
80.60
0.847
629s
SpargeAttn (0.34)
0.1686
0.9985
77.59
76.91
0.839
393s
Model len)
Attention (Sparsity)
Speed (TOPS)
FID J.
CLIP
IR
Full-Atention
158.2
166.103
31,217
0.8701
Minference (0.5)
151.8
180.650
30.235
0.4084
Flux
FlexPrefill (0.48)
47.7
443.928
18,3377
-2.2657
(4.5K)
Minference (0.3)
118.9
170.221
31.001
0.7701
FlexPrefill (0.41)
40.9
405.04
19.5591
-22362
SpazgeAtin (0.38)
280.3
163.982
31.448
0.9207
Full-Attention
164.2
166.101
32.007
0,9699
Minference (0.5)
186.4
348.930
18.3024
2.2678
Stable- Diffusion3.5 (4.5K)
FlexPrefill (0.37)
23.1
350.497
18.447
-22774
Minference (0.3)
150.3
337.530
18.099
-2,2647
FlexPrefill (0.35)
22.7
348.612
18.147
-2,2756
SpargeAttn (0.31)
293.0
166.193
32.114
0.9727
across different model types are limited. We choose block- sparse MInference (Jiang et al.) 2024) and FlexPrefill (Lai et al. 2025) as our baselines. To vary the sparsity of these baselines, we use 30% and 70% for MInference, and use 7 0.95 and 0.99 for FlexPrefill according to their paper.
Flux, Stable-Diffusionss
Mochi, and Open-Sora-Plant showing that SpargeAttn incurs no performance loss and outperforms baselines.
Attention speed. Table TableTshee shows that our method achieves faster speeds compared to Full-Attention and surpasses base- lines with various sparsity levels in terms of attention speed. Fig. 10 illustrates the kernel speeds of various methods across different sparsity, highlighting the efficiency of our approach and its significant advantage over other methods.
4.2. Quality and Efficiency Evaluation
End-to-end metrics. assess the end-to-end metries of various models using SpargeAttn compared to using full attention and baselines. [ the results. We observe that method incurs almost no end-to-end metric loss across various models compared to Full-Attention and surpasses baselines with various sparsity levels in terms of end-to-end accuracy. Fig. 6 and 12 show some visible comparison examples on CogvideoX,
4.3. Ablation Study and key Insights
Overhead of sparse block prediction. Table com- pares the overhead of dynamic sparse block prediction in SpargeAttn compared with attention execution latency.

---

SpargeAttention: Accurate and Training- free Sparse Attention Accelerating Any Model Inference
Attention
Attention
Sparge
Full Attention
Attention
Figure 6. Visible examples on CogvideoX using SpargeAttention.
Attention
SpargeAttention
Minference
FlexPrefill
Full Attention
Phompet
SpargeAttention
Promptt
Minference
Phomprt
Slable- Diffuiion..
Phompie
FlexPrefill
Flux and Stable-Di ffus cn3.. cn3.5. 5. The sparsity of SpargeAttn, MInference and FlexPrefill is 0.38, 0.3, and 0.4 Flux and 0.31, 0.3, and 0.35 on Stable-Difll 5.fuiion3...
Figure 7. Comparison
examples
Figure 8. Comparison examples Mochi. The sparsity of SpazgeAttn, Minference and FlexPrefiil is 0.47, 0.3, and 0.4.
The results indicate that the prediction overhead minimal compared to attention, particularly for longer sequences.
Table 3. Overhead of sparse block prediction in SpargeAttn.
Sequence Len Prediction (ms) Full Attention (ms) Overhead
8k
0.251
6,649
3,78%
Table and- generation latency using SpargeAttn.
16k
0.487
26.83
1.82%
32k
0,972
106.68
0.911%
Model
GPU
64k
2.599
424.24
0.612%
CogvideoX
RTX4090
87
68 s
53
128k
8.764
1696.2
0.516%
Mochi
L40
1897 s
1544
1037
Llama3. 1 (24K)
RTX4090
4.01
3,53
2.6
Llama3. (128K)
L40
52
42s
29.98
impact of Hilbert Curve permutation on Mochi by compar- ing three metrics: average block similarity across blocks of query or key, L. error defined in Sec. 3.6 and sparsity. Table 4 shows that the HilbertCurve permutation consis- tently achieves superior block self-similarity and sparsity, with only marginal difference in accuracy. Please see Appendix A.T for more analysis and details.
End-to-end speedup. Table 2 shows the end-to-end la- deoX, Mochi, and I.lama3.1 using
tency on Cogvideox, SpargeAttn. Notably, SpargeAttn achieves 1.83x speedup on Mochi.
Effect Hilbert Curve permutation. We evaluate the
8

---

SpargeAttennion: Accurate and Training-fre Sparse Attention Accelerating Any Model Inference
Full Attention
SpargeAttention
Table 6. Analysis of sparsity from My and Mpo.
9.907
0.0-
Strategy
only Mg
only Mp
Mg +Mp
11.0
11.0
22.6
Sparsity
51.2%
27.7%
54%
33.0
Death (%6
33.0
$0.0
$6.0
70.0
0.2
78.0
Ablation of self-similarity judge We ablate the effect of the self-similarity judge on Mochi. As shown in Table we find that self-similarity judge can guarantee end-to-end accuracy. Please see Appendix [A.2 Appendix/A.2]oorr for more analysis.
100.6
100.0
0.0
Token Limit
Token Limit
Minference
FlexPrefill
0.0
Analysis of sparsity from Mg and Mp-- 6 the sparsity when only using Mg. only using Mpe. and using My+Mpo on L. ama 1 in Needle-in-a-Hayseee Haystack task with 128K sequence length.
11.0
11.0
22.6
(%0
33.0
Death (%6
33.0
0
58.00
0.4
18.2
78.0
SpargeAttn enhance the LLM performance. From Table 1 Fig- p and [1] observe that SpargeAttn enhances LLM performance in long-context tasks. This improvement may result from the fact that sparse attention helps the LLM focus on more relevant information.
0.2
100.0
100.9
0.0
Token Limit
Token Limit
comparison example on Llama3.1. 1. The sparsity of SpargeAttn, MInference, and FlexPrefill is 0.5, 0.5, and 0.54.
Figure 9.
Table 7. Sparsity increases with sequence length under constant accuracy bound Ll Llama3.1.
SpargeAtin+FA2
Minference
FlashAttn SageAttn
Sequence Len
16K
48K
128K
SpargeAttn+Sage SpargeAttn+Sage2
Flexprefill
Sparsity 6.8%
26.4%
35.7%
49.8%
900
800
700
Sparsity increases with sequence length. As shown in Table we find that on Llama3. 1, sparsity increases with sequence length. This suggests that the longer contexts, the higher speedup of Spa rgeAttn can achieve.
600
500
400
300
200
Sparsity analysis over diffuusion model. We conduct de- tailed analysis of sparsity in CogvideoX across all layers, heads, timesteps, and samples using SpargeAt tn to get more insights (See Appendix A.4 for detailed figures). We find that sparsity varied with layers and heads, indicating that setting different byperparameters for each layer and head is necessary. We also find that for diffusion models, the sparsity increases with the sample timesteps.
100
Sparsity
Figure Kernel speed comparison under varying sparsity. Input tensors have sequence length of 22K and a head dimension of 128. SpargeAtm FA2 means deploying our method on Attenionn
Table Effect of permutation on sparsity and accuracy. Sim-q and Sim-k are the average block self-similarity of the query and key.
5. Conclusion
Method
Sim-q
Sim-k t
4
Sparsity
Random
0.321
0.019
0.0414
0.048
In this paper. we propose SpargeAt a universal sparse and quantized attention that executes attention efficiently and accurately for any input. Our method uses two-stage online filter: in the first stage, we rapidly and accurately predict the attention map, enabling the skip of some matrix multiplications in attention. In the second stage, design online softmax-aware filter that incurs extra overhead and further skips some matrix multiplications. Experiments show that Spare rgett tn accelerates diverse models, includ- ing language, image, and video generation models, without sacrificing end-to-end metrics.
Rowmajor
0.551
0.390
0.0307
0.363
Timemajor
0.514
0,367
0.0342
0,338
HilbertCurve
0.572
0.479
0.0389
0.392
Table Abalation of self-similarity judge.
Method
VQA-a
VQA-t
FScore 1
W/o. self-sim Judge
34.664 54.179
44.722
1.138
With self-sim Judge
67.219
1.807

---

SpargeAttention: Accurate and Training-fre Sparse Attention Accelerating Any Model Inference
Acknowledgment
Fu, T., Huang, H., Ning, X., Zhang, G., Chen, B., Wu, T., Wang, H., Huang, Z.., Li, S., Yan, S., al. Moa: Mixture of sparse attention for automatic large language model compression. arXiv preprint arXiv:2406. 14909, 2024.
This work was supported by the NSFC Projects (Nos. 92270001, 62376131). J.Z is also supported by the XPlorer Prize.
Gao, Y., Zeng. Z., Du, D., Cao, S., So, H. K.-H., Cao, T., Yang, E,, and Yang, M. Seerattention: Learning intrinsic sparse attention in your Ilms. arXiv preprint arXi::2410.13276 2024.
Impact Statement
This paper presents work that aims to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Hessel, J., Holtzman, A., Forbes, M., Le Bras, R., and Choi, Y. CLIPScore: A reference-free evaluation metric for image captioning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 7514-7528, 2021.
References
Bai, Y., Lv, X., Zhang, J., Lyu, H., Tang, J., Huang, Z., Du, Z., Liu, X., Zeng, A., Hou, L., Dong, Y., Tang, J., and J. 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, 2024.
Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter, S. Gans trained by two time-scale update rule converge to a local nash equilibrium. Advances in neural information processing systems, 30, 2017.
Hu, Y., Huang, W., Liang, Z., Chen, C., Zhang, J., Zhu, J., and Chen, J. Identifying sensitive weights via post- quantization integral. arXiv preprint arXiv:2503.011 2025.
Bao, F. Xiang, C., Yue, G., He, G., Zhu, H., Zheng, K., Zhao, M., Liu, S., Wang, Y., and Zhu, J. Vidu: a highly consistent, dynamic and skilled text-to-video generator with diffusion models. arXiv preprint 2rXi::2455.042333 2024.
Jelinek. F., Mereer, R. L., Bahl, L. R., and Baker. K. Per- plexity a measure of the difficulty of speech recognition tasks. The Journal of the Acoustical Society of America, 62(S1) (2($1):S63-S66 1977.
Black Forest Labs. Flux. https://githuk com/
black Forest labs/a/a/// flux 2023.
Jiang. H., LI, Y., Zhang, C., Wu, Q., Luo, X., Ahn, S., Han, Z., Abdi, A. H., Li, D., Lin, C.-Y., Yang, Y., and Qiu, L. MInference 1.0: Accelerating pre-filling for long-context LLMs via dynamic sparse attention. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Choromanski, K. M., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J. Q., Mo-
hiuddin, A., Kaiser, L.. Belanger, D. B., Colwell, L. J., and Weller, A. Rethinking attention with performers. In International Conference on Learning Representations, 2021.
Kamradt, G. testing 1lms. https://github com/ gkamradt/ LLMTest Needle
Limtest needle in haystack-pressum
Dao, T. Flashattention-2: Faster attention with better paral- lelism and work partitioning. In The Twelfth International Conference on Learning Representations, 2024.
2023.
Katharopoulos, A., Vyas, A., Pappas, N., and Fleuret, F. Transformers mans: Fast autoregressive transformers with linear attention. In International conference chine learning, pp. 5156-5166 5165. PMLR, 2020.
Dao. T., Fu, D., Ermon, S., Rudra, A., and Ré, C. Flashat- tention: Fast and memory-effician exact attention with io-awareness. Advances in Neural Information Process- ing Systems, 15:16334-16665 16359, 2022.
Kitaev, N., Kaiser, L., and Levskaya, A. Reformer: The efficient transformer. In International Conference on Learning Representations, 2020.
Deng, Y., Song, Z., and Yang, C. Attention is naturally sparse with gaussian distributed input. arXiv preprint arXiv:2404.002690, 2024.
Lai, X., Lu, J., Luo, Y., Ma, Y., and Zhou, X. Flexprefill: A context-aware sparse attention mechanism for efficient long-sequence inference. In The Thirteenth International Conference on Learning Representations, 2025.
Dubey, A.. Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The Ilama herd of models. arXiv preprint arXiv:2407.21788 2024.
Lin, B., Ge, Y., Cheng, X., Li, Z., Zhu, B., Wang, S., He, X., Ye, Y., Yuan, S., Chen, L.,, et al. Open-sora
10

---

Sparge-ttention:: Accurate and Training-free Sparse Attention Accelerating Any Model Inference
plan: Open-source large video generation model. arXiv preprint arXiv:24/2.00131, 2024.
Wang, S., Li, B. Z., Khabsa, M., Fang, H., and Ma, H. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.088 047666 2020.
Lin, T.-Y, Maire, M., Belongie, S., Hays, J., Perona, P., Ra- manan, D., Dollár, P., and Zitnick, C. L. Microsoft coco: Common objects in context. In Computer Vision-ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13, pp. 740- 755. Springer, 2014.
Wang, Y., Chen, Z., Chen, X., Zhu, J. and Chen, Frame-
bridge: Improving image-to-viders generation with bridge models. arXiv preprint arXivv2410.15377, 2024.
Wu, H.,, Zhang, E., Liao, L., Chen, C., Hou, J., Wang, A., Sun, W., Yan, Q., and Lin, W. Exploring video quality assessment user generated contents from aesthetic and technical perspectives. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 20144- 201 2023.
Liu, H., Zaharia, M., and Abbeel, P. Ringattention with blockwise transformers for near-infinite context. In The Twelfth International Conference on Learning Represen- tations, 2024a.
Xi, H., Yang. S., Zhao, Y., Xu, Li, X.,, Lin, Y., Cai, H., Zhang. J., Li, D., et al. Sparse videogen: Accelerating video diffusion transformers with spatial-temporal spar- sity. In International Conference on Machine Learning (ICML), 2025.
Liu, Y., Cun, X., Liu, X., Wang. X., Zhang, Y., Chen, H., Liu, Y.. Zeng, T., Chan, R., and Shan, Y. Evalcrafter: Benchmarking and evaluating large video generation models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 22139- 22149, 2024b.
Xiao, C.,, Zhang, P., Han, X., Xiao, G., Lin, Y., Zhang, Z., Liu, Z., and Sun, M. Infilm: Training-fres long- context extrapolation for Ilms with an efficient context memory. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024a.
Merity, S., Xiong, C., Braddurr, J., and Socher, R. Pointer sentinel mixture models. In International Conference on Learning Representations, 2017.
Milakov, M. and Gimelshein, N. Online normalizer cal- culation for softmax. arXiv preprint arXiv:1805.02867, 2018.
Xiao, G., Tian, Y., Chen, B., Han, S., and Lewis, M. Ef- ficient streaming language models with attention sinks. In The Twelfth International Conference on Learning Representations, 2024b.
Pagliardini, M., Paliotta, D., Jaggi, M., and Fleuret, F. Fast attention over long sequences with dynamic sparse flash attention. Advances in Neural Information Processing Systems, 36:59808-598311 2023.
Xiao, G., Tang, J., Zuo, J., Guo, J., Yang. S., Tang, H., Fu, Y. and Han, S. Ducattention: Efficient long-context IIm inference with retrieval and streaming heads. In The International Conference on Learning Representations, 2025.
Ribar, L., Chelombiev, I., Hudlass-Galley, L., Blake, C.,, Luschi, C., and Orr. D. Sparq attention: Bandwidth- efficient LLM inference. In Forty-first International Con- ference on Machine Learning, 2024.
Xu, J., Liu, X., Wu, Y., Tong, Y., Li, Q., Ding, M., Tang, J., and Dong, Y. Imagereward: Learning and evaluating hu- man preferences for text-to-image generation. Advances in Neural Informtion Processing Systems, 36, 2024.
Shah, J.. Bikshandi, G., Zhang, Y., Thakkar, V., Ramani, P., and Dao, T. Flashattention-3: Fast and accurate attention with asynchrony and oo-preccsioo. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Yang, S., Xi, H., Zhao, Y., Li, M., Zhang, J., Cai, H., Lin, Y., Li, X., Xu, C., Peng, K., et al. Sparse videogen2: Accel- erate video generation with sparse attention via semantic- aware permutation. arXiv preprint 250i:22505.1877. 2025a.
Singhania, P., Singh, S., He, S., Feizi, S., and Bhatele, A. Loki: Low-rank keys for efficient sparse attention. In The ehihty- Annual Conference on Neural Information Processing Systems, 2024.
Yang, Z., Teng, J., Zheng, W., Ding, M., Huang, S., Xu, J., Yang, Y., Hong, W., Zhang, X., Feng, G., et al. Cogvideox: Text-to-video diffusion models with an ex- pert transformer. In The Thirteenth International Confer- ence on Learning Representations, 2025b.
Stability
AL.
Introducing stable diffusion
3.5.
awt.w///etttta..ss////eeem /
i int mntroducinnsstaaleeddl -ta.le-diifussoon---33 2023.
Yu, W. Luo, M., Zhou, P., Si, C.,, Zhou, Y., Wang. X., Feng, J., and Yan, S. Metaformer is actually what you need for vision. In Proceedings of the IEFE/CVE conference
Team, G. Mochi 1. htttps//github.co com/
genmoa h/mmmmaimm/meelleam 2024.

---

SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inference
on compuler vision and pattern recognition, pp. 10819- 10829, 2022.
In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Pro- ceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 15262-15277 2024.
Yuan, 7., Zhang, H., Pu, I., Ning, X., Zhang. I.., Zhao, T., Yan, S., Dai, G., and Wang, Y. DiTFastattn: Attention compression for diffusion transformer models. In The eighth Annual Conference on Neural Information Processing Systems, 2024.
Zhang, Z., Sheng, Y., Zhou, T., Chen, T., Zheng, L.,, Cai, R., Song, Z., Tian, Y., Ré, C., Barrett, C., et al. H20: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36:34661-34711 2023.
Zhang. J., Huang, H., Zhang, P., Wei, J., Zhu, J., and Chen, J. Sageattention2: Efficient attention with thorough outlier smoothing and per-thread int4 quantization. Interna- tional Conference on Machine Learning (ICML), 2025a.
Zhao, M., Zhu, H., Xiang, C., Zheng, K., Li, C., and Zhu, J. Identifying and solving conditional image leak- age in image-to-vider video diffusion model. arXiv preprint arXiv:2406.113
Zhang, J., Huang, H., Zhang, P., Wei, J., Zhu, J., and Chen, J. Sageattention2: Efficient attention with smoothing q and per-thread guantization. 2025b.
2024.
Zhao, M., He, G., Chen, Y., Zhu, H., Li, C., and Zhu, J. Riflex: A free lunch for length extrapolation in video diffusion transformers. arXiv preprint arXiv:2502. 158944, 2025a.
Zhang, J., Li, G., and Su, J. Sage: A framework of precise retrieval for rag. In 2025 IEEE 41st International Confer- ence on Data Engineering (ICDE), pp. 1388-1401. IEEE Computer Society, 2025c.
Zhao, T., Fang, T., Huang, H., Liu, E., Wan, R., Soedar- madji, W., Li, S., Lin, Z., Dai, G., Yan, S., Yang, H., et al. Vidit-q: Efficient and accurate quantization of dif- fusion transformers for image and video generation. In International Conference on Learning Representations, 2025b.
Zhang. J., Wei, J., Zhang, P., Chen, J., and Zhu, J. Sageatten- tion: Accurate 8-bit attention for plug plug-and-pll ana-play inference acceleration. In International Conference on Learning Representations, 2025d.
Zhang. J., Wei, J., Zhang, P., Xu, X., Huang, H., Wang. H.,, Jiang, K., Zhu, J., and Chen, Sageattention3: Microscal- ing fp4 attention for inference and an exploration of 8-bit training, arXiv preprint arXiv:2505. 11594, 2025e.
Zheng, K., Lu, C., Chen, J., and Zhu, J. Dpm-solver-v3: Im- proved diffusion ode solver with empirical model statis- tics. Advances in Neural Information Processing Systems, 36:55502-5555 55542, 2023.
Zhang, J., Xiang, C., Huang. H., Wei, J., Xi, H., Zhu, J., and Chen, J. Spargeattn: Training-fres sparse attention accelerating any model inference. 2025f.
Zheng, K., Chen, Y., Mao. H. Liu, M.-Y., Zhu, J., and Zhang. Q. Masked diffusion models are secretly time- agnostic masked models and exploit inaccurate categori- cal sampling. arXiv preprint arXiv:2409.02900 2024a.
Zhang, J.. Xu, X., Wei, J., Huang, H.. Zhang, P., Chendong, X., Zhu, J., and Chen, J. Sageattention2++: A more efficient implementation of sageattention2. arXiv preprint arXiv:2505.21136, 2025g.
Zheng, K., He, G., Chen, J., Bao, F., and Zhu, J. Diffusson bridge implicit models. arXiv preprint 15888 2024b.
Zhang, P., Chen, Y., Su, R., Ding, H., Stoica, I., Liu, Z., and Zhang, H. Fast video generation with sliding tile attention. arXiv preprint arXiv:2502.04500 2025h.
Zheng, K., Chen, Y., Chen, H., He, G., Liu, M.-Y., Zhu, J., and Zhang, Q. Direct discriminative optimization: Your reelihodd-based visual generative model is secretly gan discriminator. arXiv preprint arXiv:2503.00 01 103, 2025.
Zhang, P., Huang. H., Chen, Y., Lin, W., Liu, Z., Sto- ica, I, Xing, E. P., and Zhang, H. Faster video dif- fusion with trainable sparse attention. arXiv preprint arXiv:2505.13388 2025i.
Zheng, Z., Peng, X., Yang, T., Shen, C., Li, S., Liu, H., Zhou, Y., Li, T., and You, Y. Open-sora: Democratiz- ing efficient video production for all. arXiv preprint arXiv:2412.200 2024c.
Zhang, P., Wei, J., Zhang, J., Zhu, J., and Chen, Accurate int8 training through dynamic block-level fallback. arXiv preprint ar 211::250300804 2025j.
Li. Zhu, Q. Duan, J., Chen, C., Liu, Li, X., Feng, Lv, X..
Cao, H., Chuanfu, X., Zhang, X., et al. Sampleattention:
Near-lossless acceleration of long context 1lm inference with adaptive structured sparse attention. arXiv preprint arXiv:2406. 15486, 2024.
Zhang, X., Chen, Y. Hu, S., Xu, Z., Chen, J., Hao, M., Han, X., Thai, Z. Wang, S., Liu, Z., and Sun, M. ocBench: Extending long context evaluation beyond 100K tokens.
12

---

SpargeAttention:
Accurate and Training-fre Sparse Attention Accelerating Any Model Inference
A. Appendix
A.1. Detailed Explain and results of permutation ablation
We use five distinct prompts and pre-searched hyperparameters with 1 = 0.05, /2 0.06 on both CogvideoX and Mochi models. The permutation are performed separately in attention operation for Q, K, V after position embedding. To retain the original order of the input sequence, an inverse permutation is performed the output of attention; for models using visual-language joint self-attention(e.g. Cogvi decX), we only permute the visual tokens. When evaluating block self-similarity, we choose a block size of 128 for query and 64 for key, which aligns with our kernel implementation. The precision metric(LI) is evaluated using FlashAttention2 output as ground truth.
CogvidexX)
We choose different permutation methods to compare their impact on the performance of attention operations. Given a 3D visual token tensor with shape T H x W x d, the permutation finally results tensor with shape L x d, where T H x W. The permutation methods and their detailed descriptions are shown in Table
Table 8. The detailed description of different permutation methods.
Method
Detailed Description
Random
Random permutation of tokens, the order recorded to perform inverse permutation.
Rowmajor
Permutation following row-major order. Tokens are continuous along the W dimension. Permutation following column- major order. Tokens continuous along the H dimension. Permutation following tijerrjoor order. Tokens are continuous along T dimension. Permutation following a Hilbert curve.
Columnmajor
Timemajor
HilbertCurve
Detailed results of permutation ablation for the Cogv i deoX and Mochi models are presented in Table The HilbertCurve permutation consistently achieves superior block self-similarity and sparsity, with only a marginal loss in precision. This suggests that the HilbertCurve permutation effectively enhances block self-similarity and sparsity. is worth noting that the random permutation retains the precision metries but sacrifices sparsity. This indicates that our algorithm has the property of dynamically adjusting and robust to complex token sequences.
Table The impact of permutation on CogvideoX and Mochi models. Sim-q is the black self-similarity of the query, and Sim-k is the block self-similarity of the key.
Sim-q
Sim-kt
Precision(L1))
Sparsityt
Method
Cogvideox
Mochi
CogvideoX
Mechi
CogvideoX
Mochi
CogvideoX
Mochi
Random
0.502
0.321
0.025
0.019
0.0348
0,0414
0.027
0.048
Rowmajor
0.676
0.551
0.435
0.390
0,0265
0,0307
0.242
0.363
Columnmajor
0.633
0.547
0.335
0.394
0.0274
0.0342
0.198
0.366
Timemajor
0.692
0.514
0.479
0.367
0.0294
0.0342
0.238
0.338
HilbertCurve 0.709
0,572
0,523
0.479
0,0323
0,0389
0.265
0.392
A.2. Ablation Study of Self-Similarity Judge
To investigate the impact of the self-similarity judge attention performance, we follow the experimental setting outlined in Sec. A and conduct an ablation study by removing the self-similarity judge. In most cases, the presence of highly localized patterns results in a minimal number of non-self-simila blocks, leading to only minor differences in precision and sparsity when averaging across all tensor cases. To obtain more meaningful and interpretable insights, we specifically analyze cases where the precision difference statistically significant.
To this end, we apply a threshold-basee based selection criterion, retaining only those cases where the absolute difference between L1 21sim-jver sim-judge (precision error with the self-sim self-similarity judge) and L1 Lino-judge (precision error without the self-similarity judge) exceeds 0.05. This criterion results in approximately 2% of the tensor cases being retained for further analysis. We employ precision (I.1 error) and sparsity as evaluation metrics assess the influence of the self-similarity judge on the attention output. The results are summarized in Table 10
The findings demonstrate that the self-similaryty judge effectively mitigates extreme precision loss while introducing only a marginal reduction sparsity. Furthermore, we observe that a significant proportion of cases exhibiting notable differences
13

---

SpargeAttentiio: Accurate and Training-free Sparse Attention Accelerating Any Model Inference
Table 10. Impact of the self-similarity judge the accuracy and sparsity of attention.
w/ judge
w/o judge
filter w/ judge
filter w/o judge
Method
Cogvideox
Mochi
Cogvi deoX
Mochi
Cogvi deox
Machi
Cogvi deox
Mochi
L1 error. Sparsity f
0.0316
0.0343
0.0325
0.0365
0.0843 0.242
0.0555
0.214 0.275
0.154
0.199
0.301
0.203
0.305
0.371
0.392
originate from Random permutation category in the Cogvi deoX model. This observation further highlights the role of the self-similarity judge in enhancing the model's robustness to complex token sequences while maintaining high precision.
Full Attention
SpargeAttention Overall Score: 0.863
Overa Score: 0 838
1.0
22.0
Depth (%)
0.6
0.6
44
56.0
0.4
67.0
67.0
78.0
78.0
0.2
0.
89.0
89.0
100.0
100.0
10k
10k
Token Limit
Token Limit
Minference Overa Score: 0 652
FlexPrefill Overall Score: 0.797
1.0
0.8
0.8
Depth (%)
33
33.0
0.6
08
56
56
0.4
0.4
67.0
67.0
78.0
78.0
022
89.0
89.0
100.0
100.0
Token Limit
Token Limit
Figure 11. A Needle-in-al Haystack comparison example on Llama3. 1. The sparsity of SpargeAtto, Minference, 0.36, 0.3, and 0.3.
MlnffreeetaMMMMeennecee. and FlexPrefill
Table I1. End-to-on end metrics Liama3. 3.1 in the Needle in a- Haystack task with 16-28K sequence lengths.
Model len)
Attention (Sparsity)
Speed (TOPS)
NIAH
Full-Attention
156.9
0.838
Minference (0.5)
122.5
0.635
Llama3.1 1 (24K)
FlexPrefill (0.6)
179.6
0.776
Minference (0.3)
102.3
0.652
FlexPrefill (0.3)
117.6
0.797
SpargeAttn (0.36)
443.6
0.863
A.3. Additional Experiments
In this section, we present additional experimental results further to evaluate the performance of SpargeAt tn compared baselines. Fig. and show the results on Ll amaa. in the Needle-in-a-Hlaystee task with 16-28K sequence length. Fig shows visible comparison example Mochi.
14

---

SpargeAttention: Accurate and Training-free frre Sparse Attention Accelerating Any Model Inference
Full Attention
Sparge Attention
Full Attention
Sparge Attention
Figure 12. Visible examples on Open Open-sora-Plan
Full Attention
SpargeAttention
Minference
FlexPrefill
Figure 1.3. Comparison examples on Mochi. The sparsity of Spargeettn, MInference, and FlexPrefill is 0.47, 0.3, and 0.4.
15

---

SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inference
A.4. Sparsity analysis over diffusion model
In this section, we analyze the sparsity patterns in CogvideoX across different dimensions: model layers, denoising timesteps. input samples, and attention heads. Figure 14 illustrates the layer-wise sparsity. digunsttseemosstratess timestep-
demonstrates wise sparsity. Figure [6 highlights sample-wisc sparsity. Figure 17 presents head-wise sparsity, illustrating the diversity in
attention behavior across different heads. These analyses are helpful for the design of some diffusion algorithms (Zheng
et al. 2023 2024b a 2025
Zhao et al. 2024 2025a
Wang et al. 2024
Layer-wise Sparsity Analysis
(Across samples, timestops and attention heads)
Laye Spursty Gake Moue 024
114
1508:
10
TEP
Figure 14, Layer-wise sparsity of Cogvideox.
Average Sparsity Arross TI Timettass
Avarage Sparsity
10
30
Timestep
Figure 15. Timestep-wise sparsity of Cogvi deox.
(Mean across timestepa, blocks, batches and heads)
Ovarall Maar. 9271
0.77
0.00
E204
120
Acerge
0.54
3357
0336
Figure 16. Sample-wise sparsity of CogvideoX.
16

---

SpargeAttention: Accurate and Training-fre frre Sparse Attention Accelerating Any Model Inference
0000
0000
Laper5
Leper
Loaer
Lowe
Figure 17. Head-wise sparsity of Cogvi deox.
17


Reviews:
[{"review_id": "ShP65rStYu", "reviewer": "Reviewer_P2oG", "summary": "This paper proposes a universal sparse attention mechanism that ensures both speedup and end-to-end performance of diverse models. Specifically, the method adopts a two-stage filtering schemed: In the first stage, it computes attention based on compressed tokens of self-similar blocks of query and key, and skip the computation of entries that have low cumulative sums; In the second stage, the method further identify small enough values in the attention map, and skip the negligible values. The experimental results show that the proposed method is able to maintain end-to-end metrics performance to full attention, while achieving significantly faster processing speed in diverse set of tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer P2oG,  \nThank you for your valuable suggestions and questions. Below, we address each point raised.\n\n---\n> **Q1.** Since the attention computation among tokens is permutation invariant, why would using the Hilbertcurve permutation method result in a slightly worse precision compared to other permutation variants, as shown in Table 9 in the supplementary material?\n\n**Reply**: \nThank you for your question. Yes, standard attention is token permutation invariant. However, we use sparse attention instead. After HilbertCurve permutation, the similarity in blocks of Q, K, and V increases, which enhances attention sparsity. This allows us to omit more computations, slightly increasing errors but improving speed.\n\nAn Example:  \n\n*Without permutation:*  \n\n- Self-similar blocks: 80% (sparsity within self-similar blocks = 0.3)  \n- Non-similar blocks: 20% (always computed in attention)  \n  → **Effective sparsity**: 0.3 × 0.8 = 0.24  \n  → **Blocks computed**: (1 - 0.3) × 0.8 + 0.2 = 0.76  \n\n*With permutation:*  \n\n- Self-similar blocks: 90% (sparsity within self-similar blocks = 0.3)  \n- Non-similar blocks: 10% (always computed  in attention)  \n  → **Effective sparsity**: 0.3 × 0.9 = 0.27  \n  → **Blocks computed**: (1 - 0.3) × 0.9 + 0.1 = 0.73 \n\nAdditionally, we analyze and plot the sparsity and error brought by Hilbertcurve permutation, Random permutation, and Row-major permutation on CogvideoX tensors at this Link: https://anonymous.4open.science/r/tmp-442D/sparsity_error_of_permutation.pdf. It can be observed that the Hilbertcurve permutation achieves the highest sparsity under the same error. \n\n---\n>Last but importantly, the Hilbertcurve permutation is a relatively minor aspect of our work. The **key contributions** of SpargeAttn are:\n\n1. **Effectiveness**: We design the first sparse attention method that can actually accelerate **across language, image, and video models** without compromising accuracy.\n\n2. **Method Innovations**:\n- First to enable block-wise sparse computation via selective compression.\n- First to propose sparse online softmax (a fundamentally novel approach).\n- First to establish guaranteed error bounds for all attention layers in the model.\n\nMoreover, we summarize some representative methods from four aspects, including whether needing a training process, whether relying on specific attention map patterns, whether being applicable to all models (language and diffusion), and whether implementing attention quantization:\n\n|Method|Training Free|Pattern Free|Universal|Quantization|\n|-|-|-|-|-|\n|MInference|✓|✓|✓|-|\n|DuoAttention|✗|✗|✗|-|\n|SeerAttention|✗|✓|✗|-|\n|FlexPrefill|✓|✓|✓|-|\n|H2O|✓|✗|✗|-|\n|InfLLM|✓|✗|✗|-|\n|DitFastAttn|✓|✗|✗|-|\n|SparQAttn|✓|✓|✗|-|\n|LokiAttn|✓|✓|✗|-|\n|SampleAttention|✓|✗|✗|-|\n|FastAttention|✗|✓|✗|-|\n|MOA|✗|✗|✗|-|\n|Reformer|✗|✓|✓|-|\n|**Ours**|**✓**|**✓**|**✓**|**✓**|\n\n---\n---\nIf you feel your concerns have been resolved, we would greatly appreciate it if you consider raising the score.", "claims_and_evidence": "The sparsity prediction mechanism proposed in the paper makes intuitive sense, and its strength is supported by the strong performance / processing speed trade off over related sparse attention baselines in experiment section.", "methods_and_evaluation_criteria": "The benchmark datasets cover a wide range of tasks, supporting the universality claim of the proposed method, and for each task, the metrics used are suitable to measure the performance. The paper uses speed and sparsity to measure the computational efficiency of the proposed method, which also makes sense.", "theoretical_claims": "There are no theoretical claims in this paper", "experimental_designs_or_analyses": "Yes, I checked all the subsections of the experiment section, the design of the experiments are valid and the results positively support the ideas of the paper.", "relation_to_broader_scientific_literature": "The token tiling strategy used in this paper is adopted from flashattention [1], \n\n[1] Dao, Tri. \"Flashattention-2: Faster attention with better parallelism and work partitioning.\" arXiv preprint arXiv:2307.08691 (2023).", "essential_references_not_discussed": "I haven't found missing essential references", "other_strengths_and_weaknesses": "1. The paper is well written and easy to follow", "other_comments_or_suggestions": "please see questions", "questions_for_authors": "1. Since the attention computation among tokens is permutation invariant, why would using hilbertcurve permutation method result in a slightly worse precision comparing to other permutation variants as shown in Table 9 in the supplementary material?", "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": "OrE675EYgO", "reviewer": "Reviewer_ciBv", "summary": "The paper proposes SpargeAttn, a universal and training-free sparse attention mechanism intended to accelerate inference across diverse models, including language, image, and video generation. SpargeAttn operates in two stages: initially, it rapidly predicts sparse regions of the attention map using selective token compression; subsequently, it employs a warp-level sparse softmax to further omit negligible computations without extra overhead. Experiments conducted on various benchmarks (including Llama3.1, CogvideoX, Mochi, Flux, and Stable-Diffusion3.5) suggest that SpargeAttn achieves significant speedups (up to 5x faster) without negatively impacting model accuracy or end-to-end performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer ciBv,  \nThank you for your valuable suggestions and questions. Below, we address each point raised.\n\n---\n> **Essential References Not Discussed**\n\n**Reply.** Thank you so much for providing the reference. We will discuss it in our paper.\n\n---\n> **W1.** How robust is SpargeAttn when deployed on models with highly diverse or previously unseen attention patterns? NSA [1] employs three branches—Compression, Selection, and Sliding—to compensate for block-wise attention. In contrast, SparseAttn applies attention exclusively to selected blocks. Could this selective strategy lead to information loss?\n\n**Reply**: Thank you for your question. We believe there may be a few misunderstandings:  \n\n1. **Attention Patterns**: *SparseAttn* is a test-time sparse attention method that does not rely on previously unseen patterns.  \n2. **Training vs. Inference**: NSA requires model retraining, while *SparseAttn* is applied directly during inference.  \n3. **Robustness**: All sparse attention for inference will loss some information.  However, *SparseAttn* is robust because it is error-bounded and dynamically adjusts sparsity per input to maintain accuracy. For example, if an input lacks sparsity, *SparseAttn* predicts zero sparsity and skips no computations.\n\nFinally, we directly compare *SparseAttn* and NSA for inference on Llama3.1-8B, with results shown in the table:\n\n|Attention|Speed (TOPS) ↑|WikiText (Ppl.) ↓|Longbench ↑|NIAH ↑|\n|-|-|-|-|-|\n|Full-Attention|156.9|6.013|38.682|0.907|\n|NSA|1098.8|78.335|7.496|0.07|\n|SpargeAttn|708.1|6.02|39.058|0.909|\n\n\n---\n> **W2.** What are the practical guidelines or strategies recommended for systematically selecting hyperparameters ($\\tau, \\theta, \\lambda$) in real-world deployment? The reliance on heuristic hyperparameter tuning ($\\tau, \\theta, \\lambda$) for optimal performance could limit straightforward generalization. Large attention models, in particular, require substantial training resources. The authors perform a grid search over hyperparameters for each attention layer, significantly increasing computational costs. Could the authors clarify how they address or mitigate these computational burdens?\n\n**Reply**: Thank you for the vital advice.\n\nFirst, we can use fixed hyperparameters (τ=0.5, θ=0.95, λ=-25) for inference without tuning. Although the sparsity is not as high as tuning, it is a convenient way. The results on CogVideo are presented in the Table:\n\n|Attention|Speed (TOPS) ↑|CLIPSIM ↑|CLIP-T ↑|VQA-a ↑|VQA-t ↑|FScore ↑|\n|-|-|-|-|-|-|-|\n|Full-Attention|166|0.1819|0.9976|80.384|75.946|5.342|\n|SpargeAttn|402.39|0.1802|0.9974|79.416|74.931|5.104|\n\nSecond, we would like to clarify that the tuning phase doesn't require training - it only needs 5-10 inference passes. On a server with 8×4090 GPUs:\n\n - Llama-3.1-8B takes just 14 minutes to tune.\n - CogVideoX requires 2.6 hours.\n   Once tuned, the model can be used permanently for inference. We will also release pre-tuned models for immediate use.\n\n\n---\n> **W3.** The contribution appears primarily engineering-focused, with relatively incremental methodological advances. Could the authors clarify or elaborate on how their contributions distinctly advance beyond previous block-wise attention methods?\n\n**Reply**: Thank you for your suggestion, and we summarize our contributions:  \n**Key Contributions:**\n\n1. **Effectiveness**: We design the first sparse attention method to **accelerate across language, image, and video models** without compromising accuracy.\n\n2. **Method Innovations**:\n - First to enable block-wise sparse computation via selective compression.\n - First to propose sparse online softmax (a fundamentally novel approach).\n - First to establish guaranteed error bounds for all attention layers in the model.\n\nMoreover, we summarize some representative methods from four aspects, including whether needing a training process, whether relying on specific attention map patterns, whether being applicable to all models (language and diffusion), and whether implementing attention quantization:\n\n|Method|Training Free|Pattern Free|Universal|Quantization|\n|-|-|-|-|-|\n|MInference|✓|✓|✓|-|\n|DuoAttention|✗|✗|✗|-|\n|SeerAttention|✗|✓|✗|-|\n|FlexPrefill|✓|✓|✓|-|\n|InfLLM|✓|✗|✗|-|\n|SparQAttn|✓|✓|✗|-|\n|LokiAttn|✓|✓|✗|-|\n|MOA|✗|✗|✗|-|\n|**Ours**|**✓**|**✓**|**✓**|**✓**|\n\n---\nIf you feel your concerns have been resolved, we would greatly appreciate it if you consider raising the score.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No theoretical results are included.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "This work is closely related to NSA [1] and MoBA [2]; however, both of these studies were published after ICML submission.\n\n[1] Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention, arXiv\n[2] MoBA: Mixture of Block Attention for Long-Context LLMs, arXiv", "essential_references_not_discussed": "[3] also leveraged the Z-order curve (another type of space-filling curve similar to the Hilbert curve) in sparse attention. It would be beneficial if the authors could include a discussion on this closely related work.\n\n[3] ZETA: Leveraging Z-order Curves for Efficient Top-k Attention, ICLR 2025", "other_strengths_and_weaknesses": "Strengths:\n\n1. General applicability across various model types (language, image, video).\n\n2. Effective speedups demonstrated empirically on a wide range of benchmarks.\n\n3. Minimal overhead introduced in sparse attention prediction, especially beneficial for long sequences.\n\n4. Practical implementation details, including integration with quantization methods, enhance its usability.\n\nWeaknesses:\n\n1. How robust is SpargeAttn when deployed on models with highly diverse or previously unseen attention patterns? NSA [1] employs three branches—Compression, Selection, and Sliding—to compensate for block-wise attention. In contrast, SparseAttn applies attention exclusively to selected blocks. Could this selective strategy lead to information loss?\n\n\n2. What are the practical guidelines or strategies recommended for systematically selecting hyperparameters $(\\tau, \\theta, \\lambda)$ in real-world deployment? The reliance on heuristic hyperparameter tuning $(\\tau, \\theta, \\lambda)$ for optimal performance could limit straightforward generalization. Large attention models, in particular, require substantial training resources. The authors perform a grid search over hyperparameters for each attention layer, significantly increasing computational costs. Could the authors clarify how they address or mitigate these computational burdens?\n\n3. The contribution appears primarily engineering-focused, with relatively incremental methodological advances. Could the authors clarify or elaborate on how their contributions distinctly advance beyond previous block-wise attention methods?\n\n[1] Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention, arXiv", "other_comments_or_suggestions": "Typo: Line 237, ture -> true", "questions_for_authors": "See weakness", "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": "ZBETnKufdx", "reviewer": "Reviewer_m9qG", "summary": "The paper proposes SpargeAttn, a universal sparse and quantized attention for any model, accelerates diverse models, including language, image, and video generation, without sacrificing end-to-end metrics. For blocks composed of highly similar tokens, they consolidate these tokens into a single representative token for the block, skipping the computation and further identify the small enough values in the attention map during the online softmax process.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer m9qG,  \nThank you for your valuable suggestions and questions.\n\n---\n>### Essential References\n\n**Reply**: We check STA (FastVideo) and confirm it is after the ICML submission deadline.\n\n---\n>### Comment1 and Question5\n\n**Reply**: Thank you for your valuable suggestion. We conducted detailed analysis and visualization of sparsity and sparse patterns on CogVideoX across all layers, timesteps, and heads at https://anonymous.4open.science/r/SpargeAttn_Re, named **[Analysis Repo]**.\n\nAccording to **[Analysis Repo]**, we conclude that:\n\n**Analysis of heads**: (1) There is a noticeable variation in sparsity across different heads. (2) Different heads exhibit distinct sparsity patterns.\n\n**Analysis of timesteps**: Sparsity increases as the sampling steps. This aligns with the intuition that image noise diminishes, allowing more semantic patterns to emerge and highlighting the advantage of the dynamic sparse method.\n\n**Analysis of Layers**: The model exhibits lower sparsity in the initial and final layers, while intermediate layers tend to have higher sparsity.\n\n---\n>### Comment2\n\n**Reply**: Thank you for the suggestion, and we summarize our contributions:\n\n**Key Contributions:**\n\n1. **Effectiveness**: We design the first sparse attention method that can actually accelerate **across language, image, and video models** without compromising accuracy.\n\n2. **Method Innovations**:\n- First to enable block-wise sparse computation via selective compression.\n- First to propose sparse online softmax (a fundamentally novel approach).\n- First to establish guaranteed error bounds for all attention layers in the model.\n\nMoreover, we summarize some representative methods from four aspects, including whether needing a training process, whether relying on specific attention map patterns, whether being applicable to all models (language and diffusion), and whether implementing attention quantization:\n\n|Method|Training Free|Pattern Free|Universal|Quantization|\n|-|-|-|-|-|\n|MInference|✓|✓|✓|-|\n|DuoAttention|✗|✗|✗|-|\n|SeerAttention|✗|✓|✗|-|\n|FlexPrefill|✓|✓|✓|-|\n|H2O|✓|✗|✗|-|\n|InfLLM|✓|✗|✗|-|\n|DitFastAttn|✓|✗|✗|-|\n|SparQAttn|✓|✓|✗|-|\n|LokiAttn|✓|✓|✗|-|\n|SampleAttention|✓|✗|✗|-|\n|FastAttention|✗|✓|✗|-|\n|MOA|✗|✗|✗|-|\n|Reformer|✗|✓|✓|-|\n|**Ours**|**✓**|**✓**|**✓**|**✓**|\n\n---\n>### Comment3\n\n**Reply**: \nWe provide more video demos of CogvideoX and Open-Sora-Plan at: https://anonymous.4open.science/r/spa-videos/README.md.\n\n---\n>### Question1\n\n**Reply**: Thank you for the reasonable suggestion. We compare the score of attention recall and the relative L2 distance of the final video/image outputs on CogvideoX and Stable-Diffusion-3.5. The results are shown in the following Tables.\n\n**Comparison on CogvideX:**\n|Attenion|Attention Recall|Relative L2 of outputs|\n|-|-|-|\n|Minference|0.862|0.228|\n|FlexPrefill|0.811|0.378|\n|SpargeAttn|0.892|0.056|\n\n**Comparison on Stable-Diffusion-3.5:**\n|Attenion|Attention Recall|Relative L2 of outputs|\n|-|-|-|\n|Minference|0.922|0.419|\n|FlexPrefill|0.854|0.464|\n|SpargeAttn|0.936|0.126|\n\n---\n>### Question2\n\n**Reply**: \nThank you for your insightful question. Simply splitting heads to different GPUs will result in a load balance problem. To address the problem, we can obtain the sparsity of each head in the tuning process and evenly distribute these heads according to the sparsities. We conduct a small experiment on a set of CogVideoX tensors:\n\n||Simple Split to Two GPUs|Split According to Tuning Sparsity|\n|-|-|-|\n|GPU1-Latency|15.9ms|16.8ms|\n|GPU2-Latency|17.6ms|16.7ms|\n|Final Latency|17.6ms|16.8ms|\n\nFortunately, the split method is compatible with Ulysses parallel method. \n\n---\n>### Question3\n\n**Reply**: \nThank you for the insightful question. We analyze the sparsity and sparse patterns across heads at **[Analysis Repo]**. There are heads with no sparsity, i.e., no acceleration, and heads with very high sparsity, i.e., high acceleration. However, it is not a serious problem generally. For example, for a set of Q, K, V in the shape of (2, 30, 16384, 64), it needs to launch 2 * 30 * 16384/128=7680 GPU blocks to do FlashAttention individually. A GPU usually only has about 100 SMs. The latency variance of blocks is not a serious problem because the overall throughput is determined by the average sparsity. A significant load imbalance may only occur in a multi-GPU environment, and this issue has already been addressed in the previous response.\n\n---\n>### Question4\n\n**Reply**: \nWe conduct an experiment on Open-Sora-Plan, and the result is as follows:\n\n|Attention|Sparsity↑|CLIPSIM↑|CLIP-T↑|VQA-a↑|VQA-t↑|FScore↑|End-to-end Latency↓|\n|-|-|-|-|-|-|-|-|\n|Original Attention|0|0.16503646|0.999496|81.40257|80.601264|0.84729|629s|\n|SpargeAttn|0.341|0.168645|0.99859|77.5948|76.9102|0.83938|393s|\n\nAlso, we provide video demos of Open-Sora-Plan at https://anonymous.4open.science/r/spa-videos/README.md.\n\n---\nIf you feel your concerns have been resolved, we would greatly appreciate it if you consider raising the score.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes.\n1. Lack in generated video / video demos as the metrics evaluation only is not reliable\n2. Lack in report of Attention score recall and l2 difference of output video/image (given same initial noise with fixed seed)", "theoretical_claims": "No issues", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "a new pattern-free, training-free attention accleration method for video generation due to its well generalization", "essential_references_not_discussed": "please check STA (FastVideo) whether they are  concurrent work. If not, it would be better to compare with them.", "other_strengths_and_weaknesses": "Weakness:\n1. Lack in generated video / video demos as the metrics evaluation only is not reliable\n1. Lack in analysis on sparsity of each head\n2. Lack in generalization to multi-GPU parallel inference settings", "other_comments_or_suggestions": "1. Provide with more analysis on sparsity of each head.\n2. Provide more conclusive description on main difference to previous methods and core contribution to community. \n3. Provide video demos", "questions_for_authors": "1. Current evaluation (FID, Clip score, etc.) is not reliable. Please provide attention score recall and l2 difference of output video/image if given same initial noise with fixed seed. \n2. While the proposed method demonstrates promising results on a single GPU, it would be valuable to further explore how the approach handles potential load imbalance issues in sequence and head parallelism scenarios, particularly given the varying sparsity rates across different heads. Additionally, an investigation into whether the acceleration benefits can be maintained in multi-GPU parallel inference settings would significantly strengthen the practical relevance of the work. These aspects could provide interesting directions for future research and further enhance the applicability of the method in real-world scenarios.\n3. The paper presents a universal approach for online acceleration. However, it would be insightful to investigate whether certain heads might pose challenges to acceleration due to their inherent characteristics. Specifically, providing a detailed analysis of the sparsity levels and acceleration performance for each individual head would strengthen the study. This analysis could help identify potential limitations or exceptions to the universality claim and offer a more comprehensive understanding of the method's applicability across different scenarios.\n4. The authors emphasize the universality of their proposed acceleration method as a key contribution. However, it would be valuable to explore whether the method remains effective when applied to models that have already incorporated sparse architectural designs during the pre-training phase. For instance, demonstrating the acceleration performance on state-of-the-art open-source models, such as the latest version of Opensora-plan, could provide compelling evidence of the method's robustness and generalizability across diverse model architectures. This additional analysis would further strengthen the universality claim and enhance the practical relevance of the work.\n5. analysis on different timesteps of diffusion video model\n\nI will raise my score if most of my concerns could be addressed.", "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": "i4YWcvsArq", "reviewer": "Reviewer_YtrB", "summary": "The authors propose a method for sparse attention computation which works for both language and visual models. The method constructs a sparse mask using mean pooling of blocks of queries and keys along with a measure of self similarity within the blocks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer YtrB,  \nThank you for your valuable questions. Below, we address each point raised.\n\n---\n>### Weaknesses1\n\n**Reply**: Sorry for the confusion. To clarify: We need to predict sparse areas in the attention map to skip unnecessary computations. However, a naive approach - compressing all blocks of $Q, K$ via mean pooling to get a compressed attention map $P$ - is inaccurate, because mean pooling cannot properly represent non-self-similar blocks. Therefore, we only apply mean pooling to self-similar blocks to generate the compressed attention map. The non-self-similar blocks skip this prediction phase and directly participate in the full attention computation.\n\nThank you for your suggestion. We will revise our paper to make the method part be clear.\n\n---\n>### Weaknesses1.1\n\n**Reply**: There may be some misunderstanding between compressing and computation. Not compressing does not mean not computation. Compressing blocks is for judging which blocks can be omitted from attention computation. We clarify the concepts of compressing, computation, self-similar blocks, and non-self-similar blocks:\n\n- *Computation*: The FlashAttention computation, i.e., the block matrix multiplications of $QK^T$ and $PV$.\n\n- *Compressing*: Compressing is doing mean pooling for blocks of $Q, K$ to judge which blocks of $Q, K, V$ can be omitted from attention computation. Because the mean pooling results of non-self-similar blocks can not represent the information of blocks, we skip the compressing process for non-self-similar blocks, but directly compute all of them in attention, i.e., we do not omit any computation for Non-self-similar blocks.\n\nWe will revise the paper to rename the 'self-similar blocks' to 'selective blocks' and the 'non-self-similar blocks' to 'fix blocks'.\n\n---\n>### Weaknesses2\n\n**Reply**: Sorry for the confusion. We do not use the word 'eliminate' in our paper, and we suppose the 'eliminate' means not participating in the compressing. Therefore, as explained in the reply for *W1.1*, non-self-similar will not be compressed, but directly participate in the attention computation.\n\n---\n>### Weaknesses3\n\n**Reply**: The embeddings of tokens corresponding to similar pixels are relatively similar. The HilbertCurve clusters tokens from similar pixels together, increasing the similarity between the blocks of Q and K. As a result, more 'selective blocks' participate in the sparse prediction process, while the 'fixed blocks' that always computed decrease, leading to higher sparsity.\n\n---\n>### Weaknesses3.1\n\n**Reply**: Thank you for pointing out the typo in the equation. Actually, we will compute a mean of the dq×dq matrix as a value, just as Line 201 of our paper: \"We first compute a mean cosine similarity across tokens for each block of Q and K.\"\n\n---\n>### Weaknesses3.2\n\n**Reply**: Yes, standard attention is token permutation invariant. However, we use sparse attention. After the HilbertCurve permutation, the similarity in blocks of Q, K increases, which raises attention sparsity. This allows us to omit more computations, improving speed. As shown in Table 9, HilbertCurve Permutation increases block self-similarity, raising the sparsity of attention.\n\nAn Example:\n\n*Without permutation:*  \n- Self-similar blocks: 80% (sparsity within similar blocks=0.3)\n- Non-similar blocks: 20% (always computed in attention)  \n*Effective sparsity*: 0.3×0.8=0.24  \n*Blocks computed*: (1-0.3)×0.8+0.2=0.76\n\n*With permutation:*  \n- Self-similar blocks: 90% (sparsity within similar blocks=0.3)\n- Non-similar blocks: 10% (always computed in attention)  \n*Effective sparsity*: 0.3×0.9=0.27  \n*Blocks computed*: (1-0.3)×0.9+0.1=0.73\n\n---\n>Last but importantly, the Hilbertcurve permutation is a relatively minor aspect of our work. The **key contributions** of SpargeAttn are:\n\n1. **Effectiveness**: We design the first sparse attention method that can actually accelerate **across language, image, and video models** without compromising accuracy.\n\n2. **Method Innovations**:\n- First to enable block-wise sparse computation via selective compression\n- First to propose sparse online softmax (a fundamentally novel approach)\n- First to establish guaranteed error bounds for all attention layers in the model\n\nWe summarize some representative methods from four aspects, including whether needing a training process, whether relying on specific attention map patterns, whether being applicable to all models (language and diffusion), and whether implementing attention quantization:\n\n|Method|Training Free|Pattern Free|Universal|Quantization|\n|-|-|-|-|-|\n|MInference|✓|✓|✓|-|\n|DuoAttention|✗|✗|✗|-|\n|SeerAttention|✗|✓|✗|-|\n|FlexPrefill|✓|✓|✓|-|\n|H2O|✓|✗|✗|-|\n|InfLLM|✓|✗|✗|-|\n|DitFastAttn|✓|✗|✗|-|\n|SparQAttn|✓|✓|✗|-|\n|LokiAttn|✓|✓|✗|-|\n|SampleAttention|✓|✗|✗|-|\n|FastAttention|✗|✓|✗|-|\n|MOA|✗|✗|✗|-|\n|Reformer|✗|✓|✓|-|\n|**Ours**|**✓**|**✓**|**✓**|**✓**|\n\n---\n---\nIf your concerns have been resolved, we would greatly appreciate it if you consider raising the score.", "claims_and_evidence": "The experiments seem to validate the method, which shows strong performance on both language and visual tasks.", "methods_and_evaluation_criteria": "The evaluations are relevant to the method.", "theoretical_claims": "The correctness of the algorithm seems to be correct, however, there are confusing parts which are not well specified in my opinion. See further comments for details.", "experimental_designs_or_analyses": "The experimental design appears to be sound.", "relation_to_broader_scientific_literature": "The contributions are relevant to recently published literature in sparse attention.", "essential_references_not_discussed": "The references covered are sufficient.", "other_strengths_and_weaknesses": "## Weaknesses\n\nI find the presentation of the method confusing to follow. In particular, I do not think the explanation of the self similarity was properly motivated or explained. \n\n- I am confused by this statement --> \"Importantly, compressing only the token blocks with high self-similarity is crucial, as omitting computations for non-self-similar blocks can result in the loss of critical information. This will be confirmed in Sec. 4 and A.2.\"\n  - If you compress only token blocks with high self similarity, it sounds as if you are omitting computations for non-self similar blocks by definition. \n\n- I am also confused by this statement --> \"Finally, we need to ensure that calculations involving nonself-similar blocks of Q or K are not omitted.\" The algorithm described up until this point went to great lengths to eliminate blocks which are not self similar. If you want to ultimately include these blocks regardless, then why do we need to eliminate them?\n\n- I do not understand the significance of section 3.7 which describes the HilbertCurve Permutation. While I can see that comparing neighboring pixels in this way would be advantageous for image models, I do not get how this applies to the self similarity which is proposed by the algorithm thus far.\n\n  - To my knowledge, the self similarity described in L213C1 should be like $Q_i \\in \\mathbb{R}^{b_q \\times d}$ and the cosine similarity would be calculated as something like $\\sum \\frac{Q_i Q_i^\\top}{\\vert max(Q_i Q_i^\\top) \\vert}$. I assume the sum because until this point, there has been no mention of how this $d_q \\times d_q$ matrix is reduced to a scalar. \n  - Therefore, if the reduction is a permutation invariant sum, then what benefit could the HilbertCurve Permutation provide?", "other_comments_or_suggestions": "I would suggest rewriting the method section to have more intuitive explanations for the derived method. To create space, the precise algorithm and a few equations could be moved to the appendix.", "questions_for_authors": "Please see the above \"Weaknesses\" section. I do believe the authors can clear up any misconceptions during the rebuttal, so I await their responses.\n\n## Post Rebuttal\n\nThank you for answering my questions in my review. You have cleared up many of my concerns. I have raised my score.", "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:

Meta-review: This is my summary of the strengths and weaknesses of this submission.

- Strengths:
  - Really elaborate empirical evaluation across various transformer-based models and modalities such as text, image, and video, highlighting both the speedup in the attention step (up to 5$\times$) as well as the ability to match the predictive performance of full attention. The authors also provided various additional evaluations and empirical analyses as per reviewer suggestions, and all the results provide useful intuition about the sparsity patterns, and highlight the robustness of the proposed scheme.
  - The sparsity pattern is adaptive, allowing the system to automatically pick the sparsity level as needed, and can work in a training-free manner, thereby making this an easy drop-in replacement in existing pretrained models for improved inference speed without loss in predictive performance.
- Weaknesses:
  - The hyperparameters introduced in this setup could require tuning to get optimal speed-accuracy tradeoff. However, the authors mentioned in their responses that (i) There is a default value that still provides a strong tradeoff, and (ii) The tuning of these hyperparameters only requires some number of inference passes, which take relatively less amount of time.
- The authors mention that error in the attention layers is guaranteed to be bounded. However, I do not see any theoretical analysis or derivation showing this bound. This needs to be clarified.

I would strongly suggest that the submission incorporates the clarifications of the reviewer confusion and misunderstanding in the revision of the paper.
Decision: Accept (poster)