Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper presents combiner, a new variant of sparse Transformer, which is inspired by viewing self-attention as a conditional expectation over embeddings at each location. The authors show that combiners achieve better performance than existing sparse Transformer variants.
main_review: Strengths:
1. The proposed method is novel and simple. It is surprising to see that simple max-pooling already produces strong performance.
2. The paper is well written and easy to follow.
3. It is great to see some significant improvement over the previous methods on a wide range of tasks.

Weaknesses:
1. It would be great if we could see a table containing the memory footprint and inference speed results following the setup in Table 2 in the Long Range Arena paper. Otherwise, it is unclear whether the proposed method saves the memory as well. Also, having such a table provides the numbers for future works to compare with.
2. The authors only time the speed of Combiner-Axial and Combiner-Fixed. The speed overhead of Combiner-Mixture is unrevealed.
3. It is unclear to me how many partitions and what they are in the Combiner-Mixture model in Table 1.
4. The proposed Combiner-Logsparse is not evaluated in the experiment section. I wonder what the reason is.
5. On some tasks Combiner-Axial outperforms Combiner-Fixed, but on some others, it doesn't. This makes it hard for the practitioners to decide which to use.
6. It would be better to see an ablation study on different alternatives to max-pooling when combining queries and keys. For example, how do DeepSets mentioned in subsection 3.2 perform?


Overall, the proposed method is original, interesting, and effective, so I recommend accepting it. Admittedly, if the authors can address the weaknesses above (at least the first four) in their rebuttal, I will raise my rating to 8.
limitations_and_societal_impact: The main limitation of the paper is that the real overhead using the proposed methods is not fully revealed (see the weaknesses part above).
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: This paper proposes the combiner, which could achieve full attention capability while maintaining sub-quadratic computational and memory cost.
main_review: Originality: This paper is pretty novel.

Clarity: This article is very clear and the formula derivation is detailed and rigorous.

Significance: For a long time, self-attention has been computationally cumbersome, especially when dealing with some very long sequences. This article makes self-attention more efficient while ensuring expressive ability. The theoretical derivation in this article is very sufficient, and the experiments are also very solid.

Question: I am curious about the comparison between this paper with the spatial linear layer[1,2]. Could this method be more efficient? 

[1]. Synthesizer: Rethinking Self-Attention for Transformer Models
[2]. Pay attention to MLPs
limitations_and_societal_impact: Yes, this method keeps the full attention capability while maintaining low computation and memory complexity.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Combiner - a new cheaper computationally attention algorithm. By introducing a new factorization structure, the design an algorithm with low complexity but capability close to full attention.
Numerous experiments demonstrate the utility of the proposed approach.
main_review: The topic of approximate attention is a valid question.
The current paper seems to have a very performant approach to that, and their experimental results seem solid.
However, I am concerned that some of the mechanics of the method are not fully explained, and too strong claims are made. Some revisions could make it better.

- l. 5 "full attention capability" l.132 "full attention model almost for free" - I am puzzled by the claims that the method is equivalent to full attention, while other sections of the paper say it is an approximation. Please clarify this exactly.

- l.123 subquadratic cost. I do not understand fully the claim. In general, if A(x_i) is attention for one query position i, and there are L such positions i. To calculate each A(x_i) in equation (8) one sums over all j positions, which are also L --> it seems to me still quadratic.

- also, please discuss how the choice of n_i, the partition size and count, affects the computation costs and model capacity of the Combiner

- section 3.3 tradeoffs - please improve and  clarify that section, my above comments are also concerned with better understanding of the factorization and its expressiveness

- l.150 I do not understand how exactly max pooling is applied, is it per dimension d of the keys k_j, or the most active key overall, or some other way to do it?

- reference [40] BigBird seems very related to the Combiner. While it is good there is an empirical comparison with it, would be good to mention it also in the introduction related works.  The claims of both papers (efficient attention that keep the properties of full attention due to complicated patterns) seem related to me, so would be good to elaborate on that. I saw that the appendix has some mentions on both papers and the "universal approximation property", but it did not answer fully my questions for the comparison of the two methods.

- Experiments, in table 4 the Combiner is even better than full attention, please discuss this, e.g. mention whether this is due to some inductive bias or other reason?

limitations_and_societal_impact: see above comments for approximation properties of the Combiner
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper focuses on the problem of reducing the computational cost of attention in transformers. In particular, it addresses the lack of expressiveness in existing attention approaches that leverage sparsity. To this end, the authors propose to view attention as a conditional expectation of embeddings for each token which can be approximated with a structured factorization that includes a direct expectation and an indirect/local expectation term.  Existing sparse attention patterns with sub-quadratic cost can then be used to design such factorizations which result in more expressive attention mechanisms with the same theoretical cost. The evaluation shows that this model can also reach competitive performance in several benchmarks.
main_review: The paper proposes a new way to factorize attention in transformers using sparse patterns without sacrificing expressiveness.  Even though prior work has achieved linear time complexity attention without sacrificing expressiveness using exponential kernel approximations, the conditional expectation view of attention is a novel contribution that should be of interest in the research community that focuses on efficient transformers.

The proposed framework is theoretically sound and provides a unified view of existing sparse attention patterns and how they can be converted to full attention approximations which is a solid contribution.  The exposition of the structured factorization and its instantiations were clear and comprehensive for the most part. One limitation that was not addressed in the discussion is the computational cost which is bounded by that of the sparse pattern methods, namely sub-quadratic, which is still higher than linear complexity methods. Prior work has shown that both low-rank and full-rank blocks in the approximation are more powerful in theory but it is not clear if it holds up for the proposed approximation since it uses a mixture model to improve expressiveness.  Also, being more powerful also comes at a computational cost; the main point of efficient attention is to achieve a competitive speed-quality tradeoff.  This is an aspect that was not addressed in the model or the evaluation sections (see details below).  

The evaluation which is mainly quality-driven shows that the proposed models provide consistent improvements compared to sparse attention methods; the results support the main claim of the paper about improving expressiveness with sparse computational cost. However, the differences between them in terms of speed in practice have not been explored. The proposed models have some additional components that potentially add computational cost in practice. The rest of the evaluation mostly focuses on achieving state-of-the-art results which is great but I think it lacks emphasis on the speed-quality tradeoffs and it lacks an ablation analysis of the components used in the design of the architectures such as Deep Sets for representing the abstraction and the mixture of softmax to obtain a high-rank approximation.  There are also some details that would be helpful for better assessing the results e.g. including the number of parameters for each attention method and reporting the speed achieved by each method in the Long-Range arena benchmark. The only part that involves speed experiments is in Figure 3 which is not thoroughly discussed in the text.  

Questions: 

- What is the impact of deep sets and the mixture of softmaxes on the performance of the model? An ablation analysis would help to show which component is most important and how good is the approximation without adding any additional parameters. 

- The experiment in Figure 3 lacks a detailed description.  One would expect Performer to be faster since it has lower complexity than the proposed models but it's not the case. Could the authors elaborate on that? Does the experiment measure the time it takes to encode or generate sequences of X length? Ideally, we would want to see what happens when generating sequences which is a  challenging setting where parallelization is not possible.

- For the long-range arena, it would be informative to show the runtime for each of the methods so that it is easy to compare methods in terms of speed-quality tradeoffs. Currently, it's not possible to know how good tradeoffs the proposed models achieve in practical tasks.  
limitations_and_societal_impact: The papers discuss theoretical limitations regarding the expressiveness of the proposed factorization which is quite informative. It would be worth including some discussion about the reliance on hand-designed sparsity patterns, the computational cost compared to linear time and space attention methods, and investigate how good speed-quality tradeoffs the proposed models can achieve in practice compared to alternatives. There is no discussion provided about the potential positive or negative societal impact of the work. Although there is no obvious concern, it would be good to see that the authors have thought about it.
review_title: null

Meta-review: This paper proposes a novel efficient Transformer variant, called Combiner, which is a drop-in replacement of attention, achieving full attention with sub-quadratic cost using structured factorization. The reviewers have several concerns regarding the experimental analysis in the initial review. During the rebuttal period, the authors provided intensive analysis and addressed most of the concerns from the reviewers.

All reviewers recommend acceptance, and I hope the authors could include the new experimental results and ablation studies in the camera-ready version.
Decision: Accept (Spotlight)