SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inference

Dear Reviewer YtrB,
Thank you for your valuable questions. Below, we address each point raised.

---

Weaknesses1

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.

Thank you for your suggestion. We will revise our paper to make the method part be clear.

---

Weaknesses1.1

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:

• Computation: The FlashAttention computation, i.e., the block matrix multiplications of $QK^T$ and $PV$.

• 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.

We will revise the paper to rename the 'self-similar blocks' to 'selective blocks' and the 'non-self-similar blocks' to 'fix blocks'.

---

Weaknesses2

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.

---

Weaknesses3

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.

---

Weaknesses3.1

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."

---

Weaknesses3.2

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.

An Example:

Without permutation:

• Self-similar blocks: 80% (sparsity within similar blocks=0.3)
• Non-similar blocks: 20% (always computed in attention)
  Effective sparsity: 0.3×0.8=0.24
  Blocks computed: (1-0.3)×0.8+0.2=0.76

With permutation:

• Self-similar blocks: 90% (sparsity within similar blocks=0.3)
• Non-similar blocks: 10% (always computed in attention)
  Effective sparsity: 0.3×0.9=0.27
  Blocks computed: (1-0.3)×0.9+0.1=0.73

---

Last but importantly, the Hilbertcurve permutation is a relatively minor aspect of our work. The key contributions of SpargeAttn are:

1. Effectiveness: We design the first sparse attention method that can actually accelerate across language, image, and video models without compromising accuracy.

2. Method Innovations:

• First to enable block-wise sparse computation via selective compression
• First to propose sparse online softmax (a fundamentally novel approach)
• First to establish guaranteed error bounds for all attention layers in the model

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:

---

---

If your concerns have been resolved, we would greatly appreciate it if you consider raising the score.

Dear Reviewer m9qG,
Thank you for your valuable suggestions and questions.

---

Essential References

Reply: We check STA (FastVideo) and confirm it is after the ICML submission deadline.

---

Comment1 and Question5

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].

According to [Analysis Repo], we conclude that:

Analysis of heads: (1) There is a noticeable variation in sparsity across different heads. (2) Different heads exhibit distinct sparsity patterns.

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.

Analysis of Layers: The model exhibits lower sparsity in the initial and final layers, while intermediate layers tend to have higher sparsity.

---

Comment2

Reply: Thank you for the suggestion, and we summarize our contributions:

Key Contributions:

1. Effectiveness: We design the first sparse attention method that can actually accelerate across language, image, and video models without compromising accuracy.

2. Method Innovations:

• First to enable block-wise sparse computation via selective compression.
• First to propose sparse online softmax (a fundamentally novel approach).
• First to establish guaranteed error bounds for all attention layers in the model.

Moreover, 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:

---

Comment3

Reply: We provide more video demos of CogvideoX and Open-Sora-Plan at: https://anonymous.4open.science/r/spa-videos/README.md.

---

Question1

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.

Comparison on CogvideX:

Comparison on Stable-Diffusion-3.5:

---

Question2

Reply: Thank 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:

Fortunately, the split method is compatible with Ulysses parallel method.

---

Question3

Reply: Thank 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.

---

Question4

Reply: We conduct an experiment on Open-Sora-Plan, and the result is as follows:

Also, we provide video demos of Open-Sora-Plan at https://anonymous.4open.science/r/spa-videos/README.md.

---

If you feel your concerns have been resolved, we would greatly appreciate it if you consider raising the score.

Dear Reviewer ciBv,
Thank you for your valuable suggestions and questions. Below, we address each point raised.

---

Essential References Not Discussed

Reply. Thank you so much for providing the reference. We will discuss it in our paper.

---

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?

Reply: Thank you for your question. We believe there may be a few misunderstandings:

1. Attention Patterns: SparseAttn is a test-time sparse attention method that does not rely on previously unseen patterns.
2. Training vs. Inference: NSA requires model retraining, while SparseAttn is applied directly during inference.
3. 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.

Finally, we directly compare SparseAttn and NSA for inference on Llama3.1-8B, with results shown in the table:

---

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?

Reply: Thank you for the vital advice.

First, 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:

Second, 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:

• Llama-3.1-8B takes just 14 minutes to tune.
• CogVideoX requires 2.6 hours. Once tuned, the model can be used permanently for inference. We will also release pre-tuned models for immediate use.

---

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?

Reply: Thank you for your suggestion, and we summarize our contributions:
Key Contributions:

1. Effectiveness: We design the first sparse attention method to accelerate across language, image, and video models without compromising accuracy.

2. Method Innovations:

• First to enable block-wise sparse computation via selective compression.
• First to propose sparse online softmax (a fundamentally novel approach).
• First to establish guaranteed error bounds for all attention layers in the model.

Moreover, 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:

---

If you feel your concerns have been resolved, we would greatly appreciate it if you consider raising the score.

Dear Reviewer P2oG,
Thank you for your valuable suggestions and questions. Below, we address each point raised.

---

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?

Reply: Thank 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.

An Example:

Without permutation:

• Self-similar blocks: 80% (sparsity within self-similar blocks = 0.3)
• Non-similar blocks: 20% (always computed in attention)
  → Effective sparsity: 0.3 × 0.8 = 0.24
  → Blocks computed: (1 - 0.3) × 0.8 + 0.2 = 0.76

With permutation:

• Self-similar blocks: 90% (sparsity within self-similar blocks = 0.3)
• Non-similar blocks: 10% (always computed in attention)
  → Effective sparsity: 0.3 × 0.9 = 0.27
  → Blocks computed: (1 - 0.3) × 0.9 + 0.1 = 0.73

Additionally, 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.

---

Last but importantly, the Hilbertcurve permutation is a relatively minor aspect of our work. The key contributions of SpargeAttn are:

1. Effectiveness: We design the first sparse attention method that can actually accelerate across language, image, and video models without compromising accuracy.

2. Method Innovations:

• First to enable block-wise sparse computation via selective compression.
• First to propose sparse online softmax (a fundamentally novel approach).
• First to establish guaranteed error bounds for all attention layers in the model.

Moreover, 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:

---

---

If you feel your concerns have been resolved, we would greatly appreciate it if you consider raising the score.