Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper aims at improving the computational efficiency of the attention mechanism by leveraging the specific sparse pattern supported by sparse tensor cores of NVIDIA A100, with a particular focus on delivering practical running speedup. To achieve this, the authors proposed DFSSATTEN, which shows both theoretical and empirical advantage in terms of performance and speedup compared to various baselines. In particular, DFSSATTEN yields 1.27~1.89x speedup over the vanilla attention network across different sequence lengths.
main_review: Strengths:

This paper offers a simple method with clean code implementation to leverage sparse tensor cores for attention speedup. It demonstrates that the 50% sparsity pattern can retain model performance very well, and it yields 1.27~1.89x practical speedup over the vanilla attention across different sequence lengths.

Weaknesses:

* The speed analysis is narrowed down to the attention alone, which is not *practical*.
* Comparison across different models might not be fair.
* The proposed method is very specific to the sparse pattern offered by NVIDIA A100, which is not generalizable.


Detailed comments:
1)	Since the major goal of this paper is to achieve “practical” speedup over baselines, showing speedups over the attention component alone is far from enough and not *practical* at all. As a user, I would care about whether the proposed model could make the overall training faster or could allow larger-batch training so that reduce the gradient accumulation steps. Unfortunately, neither is analyzed. Based on my own experiments, attention computation, i.e. QK, softmax, and AV used in the paper, only takes a small proportion of the whole Transformer. To prove the significance of DFSSATTEN, more analysis should be given.
a)	Particularly, I would like to see further analysis on the speedup of the whole Transformer with respect to sequence length, model dimension and model depth.
2)	The proposed method is based on new sparse operations supported by the latest NVIDIA GPUs, or A100. The fact that A100 is very expensive, and many institutes can’t afford it at this moment largely devalues this paper. How does the model perform on other old GPUs, like 1080 and 2080 GPUs? Would we get slower running speed? Also, the proposed attention method doesn’t solve the quadratic attention complexity issue. So, the generalization ability of DFSSATTEN is highly doubtful. 
3)	The speedup given by DFSSATTEN is mostly from the low-level optimization and hardware support. However, many existing algorithms like Performer and Reformer are often not deeply optimized. So directly comparing with them might be unfair. Besides, in introduction, the authors argue that these methods are usually trained from scratch. This is actually a very significant direction since pretraining becomes very popular and important nowadays. Then a question is whether DFSSATTEN supports training from scratch. It would be great if DFSSATTEN could accelerates the training from scratch, but this is not studied in the paper.

summary_of_the_review: In summary, this paper provides a solution based on sparse tensor cores (specific to NIVIDIA A100) to optimize and accelerate attention operations. Although it yields good performance and nice attention speedup, its practical value on Transformer efficiency is unclear and its generalization to other devices is also unclear (at least, we shouldn’t get slow running on other GPUs or CPUs).
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents DFSSATTEN, a fine-grained structured sparse attention mechanism. 
Experiments show that the proposed method achieves speedups in A100 GPU. 
main_review: Strength: A new idea of applying structured sparse patterns to approximate self-attention in Transformer. 

Weakness:
1. Approximate self-attention analysis. Why quality of Attention lottery is a good indication of softmax matrix approximation $A$
, instead of the error between true softmax matrix $A$ and approximate softmax matrix $\tilde{A}$? Since $A$ is a softmax matrix and $A$ only has a 1 entry for each row, $Q^p = 1$ is not meaningful that approximate $A$ is the worst approximation when $m \odot A$ does not pick that entry.  The authors should give a more direct approximation analysis, such as $||A - \tilde{A}||_F$ or $||A - \tilde{A}||_F/||A||_F$, and present comparison with other baselines, such as longformer. 

2. Efficiency analysis. Eq. 4 shows an upper bound of speedup. Why $s < 4.5\%$, leads to speedup $> 1$? Eq. 5 shows an upper bound. Why Eq. 6 shows an equality? How the comparison with Top-K sparsity presents an upper bound in Eq. 7 and Eq. 8 presents an approximation equality?

3. LRA benchmark. LRA benchmark has 5 tasks. Why only 3 tasks are used for comparison? Recommend to include state-of-the-art efficient self-attention methods on LRA, such as [1], [2], and [3]?

4. Speedup experiment. The authors only compare the self-attention part, which does not necessarily represent the speedup of the proposed method for Transformer (forward and backward). The authors should report the running time and memory consumption for a vanilla Transformer with respect to different sequence lengths and compare with other baselines as in [4]. How about the speedup on commonly used GPU, e.g., 2080Ti/V100s?

[1] Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention

[2] SOFT: Softmax-free Transformer with Linear Complexity

[3] H-Transformer-1D: Fast One-Dimensional Hierarchical Attention for Sequences

[4] You Only Sample (Almost) Once: Linear Cost Self-Attention Via Bernoulli Sampling
summary_of_the_review: This paper presents an efficient self-attention mechanism and achieves speedup. But the analysis and experiments have some issues (see weakness). I will give a borderline due to those concerns and change it accordingly based on rebuttal.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a method that exploits the 50% structured sparsity supported by tensor cores on modern GPUs. To do so attention scores ($QK^T$) are dynamically pruned such that only 50% attention scores are kept. This improves the computation required for softmax as well as matrix multiplication between pruned attention weight $A$ and value matrix $V$. The authors evaluate the proposed method on LRA and MLM tasks to show that the method can provide practical speed-ups especially for moderately long sequence lengths where other proposed efficient attention mechanisms struggle due to overheads.
main_review: Strengths:
 - Overall, I found the work to be interesting and the speed-ups quite significant especially for moderately long sequences ($\lt 512$) where most efficient attention mechanisms struggle due to the overheads involved.
 - The paper is well structured and clearly written. The results relating to the quality of approximation / lottery tickets in conjunction with the theoretical speed-ups also shed some light on when different sparsity patterns should be used.
 - The experiments on LRA show that proposed method can train from scratch with no loss in performance while the results on MLM tasks show that the DFSSATTEN can be finetuned from a model pre-trained with full attention. Furthermore, results from Table 1, 2, and 3 also demonstrate that the DFSSATTEN can well approximate pre-trained model with no finetuning.

Some questions and concerns:
 - While the empirical evidence showing that the proposed structured sparse attention can approximate the full attention is very convincing, I am not sure how well does the assumption $\frac{QK^T}{\sqrt{d}}$ follows i.i.d.  $\mathcal{N}(\mu, \sigma)$ (proposition 4.1) hold in practice? This is important as a lot of the claims regarding the quality are hinged on this.
 - The results from Table 2 and 3 (without finetuning) show that DFSSATTEN can be used as drop-in plug in during inference time. It would also be interesting to see what happens if full attention is used on model finetuned with DFSSATTEN, this would help to understand if the DFSSATTEN and full attention learn similar patterns. It would also be useful to compare attention distribution for models finetuned with full and DFSSATTEN.
 - Speedup: From equation (6), for DFSS attention, the speed up would be $\approx$1.5X for long sequences, i.e., when $n \gg d$, however the actual speed ups reported seem to be around 1.87X for long sequences. I am concerned if using only memory access for theoretical estimates is a good approximation.  It would be good to have a plot similar to figure 4 comparing random sparsity, and fix sparsity for few different values of $s$.
 - Figure 10, It would also be nice to add a row showing the actual Bert accuracy plots for different sparsity.
 - How was the fixed sparsity pattern selected in figure 10?
 - Could you please elaborate on the sentence "On the other hand, we have theoretical value of $\sigma \approx 1$ and $p \ge 1$ based on the observation that the edges with higher magnitude are more influential." Specifically why $\sigma \approx 1$ if higher magnitude edges are more influential?

Minor issues:
 - Page 16, before eq. 17, Therefore, $L^p$ quality of ~Top-K~ fixed sparsity.
 - References missing in the table 4
summary_of_the_review: The paper showcases speed-ups for a large range of sequences as well as the ability to do both training from scratch and finetuning with no loss in performance. Moreover its compatibility with other efficient attention mechanisms makes it a good choice for a wide range of applications.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper focus on the dynamic N:M fine-grained structured sparse attention implementation on transformers. 
Firstly, the authors analyze the theoretical efficiency of Top-K Sparsity, Fixed sparsity and dynamic 1:2/2:4 sparsity, 
which demonstrates the dynamic N:M sparse attention can achieve considerable speedup and high-quality approximation.

Then, the authors evaluate the accuracy and the practical speed of the transformer model from the Huggingface model Zoo using the DFSSATTEN module and explain the detailed implementation using the cutlass library.
main_review: pros:

The motivation of this paper, accelerating and maintaining performance using N:M fine-grained structured dynamic sparse attention, is clear and persuasive.

The authors provide the source code with clear comments.

The paper is well-written and easily follow for industrial deployment.
 
cons:

In section3.1, the reason why this paper started from stage1 confused me, Chen focus on Nvidia Volta Architecture without sparse tensor core, this paper conduct experiments on Ampere Architecture.
what about the speed of QK^T with N:M structured sparse on Ampere Architecture? 

How about backward function during finetune sparse models?

Related work, https://arxiv.org/abs/2102.04010 which was the first research paper to train N:M fine-grained static sparse weight from scratch  (including transformer) should be mentioned.

Under bf16 data type, QK^T is slower than the dense baseline? So, according to the reasons, the speedup of dynamic sparse attention may be difficult with a higher sparse ratio (e.g., 2:8) in the future?

summary_of_the_review: The paper presents dynamic sparse attention to accelerate the attention module. I give a weak acceptance due to the weakness, I may raise my score according to rebuttal.
review_title: null

Meta-review: This paper presents a package for "Dynamic Fine-grained Structured Sparse Attention Mechanism" (DFSSATTEN), which aims to improve the computational efficiency of attention mechanisms by leveraging the specific sparse pattern supported by sparse tensor cores of NVIDIA A100. DFSSATTEN shows theoretical and empirical advantage in terms of performance and speedup compared to various baselines, with 1.27~1.89x speedup over the vanilla attention network across different sequence lengths.

Reviewers praised the simplicity of the method and the clean code implementation. Speeding up attention mechanisms is an important problem is leveraging sparse tensor cores for attention speedup is a sensible idea. The practical speedups are significant (1.27~1.89x over the vanilla attention across different sequence lengths). However, they also pointed out some weaknesses: the fact that the proposed method is very specific to the particular sparse pattern offered by NVIDIA A100, and not easily generalizable to other future hardware; the fact that the method focuses on inference acceleration and not training from scratch (not completely clear in the paper), which limits its scope; and the fact that the method still has O(N^2) complexity (it still requires the computation of QK^T, which has quadratic memory and computation cost), and therefore it does not really address the quadratic bottleneck of transformers, unlike other existing work in efficient transformers for long sequences. 

I tend to agree with the reviewers and, even though the package can be potentially useful to other researchers, the scope seems limited and the paper seems a bit thin to deserve publication at ICLR.

Other comments and suggestions:
- When talking about linear transformers, you should cite [1], which predates Performers
- It is not clear to me why 1:2 and 2:4 are called "fine-grained *structured* sparsity"
- Citations for the systems in Tab 4 are missing
- When comparing to other methods, it would be include to include their Pareto curves since those methods have tradeoffs in terms of sparsity / approximation error (or downstream accuracy).

[1] Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention. Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, François Fleuret (https://arxiv.org/abs/2006.16236)
Decision: Reject