Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: This submission presents an efficient approximation method of attention matrices. This work demonstrates the effectivenss of the proposed method really well in the domain of dense attention, e.g., Transformer or self-attention.

The authors provided thorough motivational examples, both theoretical and empirical analyses, and discussions. 

This work achieves a new trade-off point that works likely to be better than sparse or low-rank counterparts by using sparse + low-rank decomposition.
The proposed method maintains both favorable properties of Performer and Reformer, and extends the working regime of the algorithm by sacrificing a bit of cost over Reformer.

The developed algorithm is simple and exact in Supp(S). Also, the authors design the experiment very well, and show effectively that the proposed scatterbrain has lower approximation errors. In various tasks, it is shown that the proposed method maintains the efficiency of Reformer at a similar level, while extending the successful working regimes.

The proposed method is practical in that the pre-trained attention-based models can be sped up by replacing the attention computation as a drop-in replacement that maintains the original quality as much as possible.

I'm happy to be selected as a reviewer of this work. I'm enjoying reading this work, and appreciate the authors submitting high-quality work.
main_review: 
Pros
- A new good trade-off between speed and accuracy is achieved
- Very well-motivated and thoroughly analyzed
- The proposed algorithm is well-designed such that it is easy to replace the pre-trained components of Transformer.

Cons
- I'm biased; thus, I couldn't find any major cons.
- Discussion about the rank hyper-parameter and its experiment is not discussed.


<Comments>

* This work mainly focuses on the efficiency improvement of the pre-trained attention-based models. However, in practice, the most bottleneck to adopt such large attention-based models is on training. This reviewer is aware of the fine-tuning experiment in the supplementary material, but it would be more impactful to demonstrate full training from scratch. This is likely to amplify the gap with Reformer or Performer (especially against Performer), because gradient efficiency of the scatterbrain is much higher.

* There must be a balance hyper-parameter between rank and sparsity. It acts as another trade-off controller. The discussion and phase transition on how to set the proper balance would be helpful to readers.



================= After rebuttal =================

The authors' responses answer this reviewer's questions and comments appropriately.
This reviewer keeps supporting the original rating.
limitations_and_societal_impact: The authors discussed the positive effect of the proposed method on efficiency and energy saving. Also, they warned about spreading fake data due to the advance of the generative models in multiple domains, e.g., NLP, image, and video, and its extension to privacy and fairness issues. They also argued the necessity of addressing those problems individually. 

The discussion is reasonable and agreed upon.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes ScatterBrain a combination of sparse and low-rank attention and shows that it outperforms both Reformer and Performer on language modeling, Long range arena and vision tasks. 
main_review: Essentially, despite what this paper is trying hard*not* to be, this seems like a simple combination of sparse (Reformer) LSH attention with low rank (Performer) attention. I would rate the novelty quite low especially with the way the methods are combined (just adding Reformer attention with Performer's low rank attention). 

I think many prior work (BigBird, ETC, Luna, Long short Transformers etc) have already shown that a combination of multiple sparse patterns or global components are useful. Along this line, I think the narrative of multiple attention being useful is not entirely new either. 

If this paper was pitching itself "evaluating the effectiveness of a combination of different xformer variants", I can see how this is useful but the number of examples enumerated here is only a single method. I would encourage the authors to reframe this paper as such and evaluate more components rather than pitching a single combination (Reformer + Performer). Still, it is great to know that this outperforms standalone Performer and Reformer but i think the contribution is not really enough. 

Furthermore, I also have some concerns about experiments, namely:

1. The performance of Performer on Copy and Wikitext is horrible. Have the authors tuned the model carefully? I think the kernel choice in Performer is important, it would be good to know if Performer was adequately tuned. 
2. For Long Range arena, Reformer and Performer are only reported. Given that there are other models evaluated in LRA, why did the authors not compare with the other models? For example, did the model outperform BigBird in the LRA paper? 
3. For language modeling, can the authors provide a strong local attention baseline? I think local attention should always at least be reported whenever xformer comes into play, given that it is the "simple naive baseline" 

More questions:
1. The sparse variant here is Reformer, which is form of learnable sparsity. What about fixed sparse patterns, like Sparse Transformer or Longformer/Sparse Transformer?

More thoughts and suggestions: 
1. Try combining different sparse and low-rank models, and draw insights from that. Are there benefits of different composition of attention types? What about different types of sparse models.
2.  What about interleaving layers? Does interleaving Reformer and Performer give on the necessary inductive bias as ScatterBrain? 

limitations_and_societal_impact: Yes, i have no concerns.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The work proposes to combine sparse attention and low-rank attention to form a better approximation to full attention. Theoretical analysis shows sparse attention is particularly good for approximating low-entropy attention while low-rank attention is good for the high-entropy case. By combining the two, the proposed Scatterbrain is able to outperform both low-rank and sparse attention alone on post-training approximation with BigGAN and T2T-ViT as well as end-to-end training on language modeling and long range arena. As a result, Scatterbrain makes the gap between full attention and linear-complexity attention closer.
main_review: The idea of combining sparse attention and low-rank attention is intuitively reasonable and well motivated by the theoretical analysis. Although there is still a clear gap compared to the full attention, the empirical results is already encouraging. 

One suggestion is to add some study of the impact of parameter budget under language modeling (as it's more realistic) as well as the speed & memory test (Fig 6). This will provide additional helpful insights, especially for practical applications. 
limitations_and_societal_impact: The limitations are clearly discussed in the paper and I don't see any potential negative societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: Recently, sparse- and low-rank approximations are proposed to reduce the computational cost of the Transformer. However, each approximation works well in different areas. The authors show that the softmax temperature (entropy) determines which approximation is more appropriate. To enjoy the best of both approaches, this paper proposes Scatterbrain, which uses both sparse- (as Reformer) and low-rank (as Performer) attention computation. The key idea is to make sparse matrix S to match (A – QK) instead of A. Experiments on both pre-trained networks and end-to-end training show that Scatterbrain can achieve much smaller approximation error and better performance, respectively.
main_review: Overall, the idea and the motivation are clear. The paper is well-written and easy to follow. The selection of baselines is appropriate, and they are properly compared with the proposed algorithm. The analysis of the attention temperature is novel and meaningful. The result is also well visualized (ex: Fig 4, 5). Using robust-PCA as the most accurate approximation also helps readers to get the sense of the ‘golden’ combination.

Suggestions:

(1)	I think figure 2 needs more explanations. (… what points and color mean, how they are visualized, etc.) In fact, is the figure necessary?

(2)	It would be great if a simpler way (just add S + QK, line (198-200)) is also compared in experiments.

(3)	In figure 6, the legend should be Reformer -> SMYRF.

limitations_and_societal_impact: The authors well addressed the limitations and potential negative social impact.
review_title: null

Meta-review: In this paper, the authors discussed the effect of sparse and low-rank approximation for the transformer. The proposed combination leads to better performances comparing to the existing fast transformer with each approximation scheme only.  The paper is well-motivated and the theoretical and empirical analyses are reasonable. Therefore, I recommend the accept this submission. 

The paper can be further improved by taking the reviewers' suggestions about the experiments, e.g., full-training-from-the-scratch  (Reviewer Gfk7), comparison on LRA (6aFS), tradeoff between memory vs. accuracy (QK3S), and comparing with more baselines (Hndw). 

Decision: Accept (Poster)