Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: A fast and memory-efficient transformer architecture based on a sparse attention mechanism inspired by the fast multipole method (FFM). It decomposes attention matrices into the sum of a banded matrix (capturing near-range interactions) and a low rank matrix (capturing long-range interactions). This low rank matrix is itself expressed as a sum of rank 1 matrices, each characterized by a given feature map. Experiments on the LRA benchmark and WikiText-103 show promising results in terms of test accuracy/perplexity Vs training/inference speedups.
main_review: **Overall appreciation (originality, quality, clarity, and significance)**
- Originality: Adapts the intuition from the fast multipole method to sparsify attention maps, and leverage several tricks (e.g., kernel trick for linear transformers from ​​Katharopoulos et al.) to obtain a simple and intuitive formulation.
- Quality: Method is well motivated and there are a few promising experimental results. However the experimental design has significant gaps (see suggestions below).
- Clarity: Easy to read overall. There are some subsections that felt unnecessary / not concisely written (see below).
- Significance: Although difficult to draw conclusions given the shortcomings of current experiments, the idea appears to have potential. The duality of local attention vs long-range attention controlled by two separate components is compelling. Additional guidance/analyses on relative performance tradeoffs between widening the banded matrix Vs adding more feature maps in low rank matrix, as well as on the way to choose these feature maps would be very valuable.

**Clarifying questions**
- Fig 4 & 5: Are these showing cross entropy loss on the training set or validation set? If on the training set then results are not surprising (you are training networks with strictly more parameters). If on validation set, then the language (line 201) is a bit misleading

**Suggestions**
- Section 2.1 - This subsection could be made more concise: several definitions and propositions are introduced but subsequently not used anywhere (could be moved to appendix)
- Section 3 - Guidance on how to select / craft these feature maps would strengthen your paper 
- Fig 4 & 5 - It appears you have not yet converged on the longer sequences experiment (length=512) which makes your conclusion on line 202 not clear. Additionally, I would keep consistent the y-axis scales between the three columns: as such they are a bit hard to compare across.
- Section 4 - This section is lacking a speed vs acc/perplexity analysis (in particular on LRA). Currently, section 4.1 has . Would be good to have in table format for speedups to appreciate actual gains. FIg. 
- Section 4 - It would be very helpful to perform a thorough ablation analysis that shows relative trade-offs (on accuracy/perplexity, speed, memory) from increasing the banded matrix bandwidth Vs increasing the number of feature maps considered for the low rank matrix.
- Section 4 - There are many sparse attention transformer architectures out there (e.g., Performer, Linformer). It is important to compare FMMformer to these other methods (besides linear transformers) to understand relative performance trade-offs
Section 4 - Would recommend keeping things more consistent in terms of choice of parameters across experiments (number of kernels and bandwidth in particular)

**Minor points**
- Line 72/73: “and has been regarded as one of the top 10 algorithms in scientific computing in the 20th century” → unnecessary, would suggest to drop this sentence
- Line 86-87: “For the illustration purpose” → “For illustrative purposes”
- Line 94: Define C (e.g., positive constant)
- Line 153: ‘using the fact that LV= …” → would drop -- you have the same identity just above
- Line 159: Would indicate what these assumptions are here
- Line 174/175: “It is easy to check that [...] linearly independent for almost all x” → Add proof in appendix
- Line 220: “capturing long-term dependency’ → “long-range dependencies”

limitations_and_societal_impact: Limitations are discussed, although they are a bit scattered throughout -- would be helpful to synthesize them in conclusion.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper proposed FMMformers, and propose to combine banded attention with low-rank attention in a single model. They conduct experiments on wikitext, copy and long range arena. 
main_review: The combination of different types of attention is not new. Models like BigBird, ETC, long short transformers, luna etc. already proposed this idea. The authors learn to blend the attention types together by a linear combination. I don't think this paper is terribly interesting given this naive composition. 

This paper combines banded attention with kernel (low-rank) attention by combining the attention weights before multiplying by V. I think we can think of it as linear/performer transformers with a sprinkle of local attention.  I really think the FMM (fast multipole) angle is **not** main text worthy as it can be just distracting and does not add much value to the understanding of the method. 

I think the authors can be upfront that this method is simply add(low rank attention, local_attention). The story does not seem to contribute anything to the understanding of the method and is making things "fancy" unnecessarily. Please consider a more down to earth method if we hope that this method to be more widely adopted. I would appreciate a model name and title that better explains what the method is doing (local+kernel attention) seems to be more appropriate. 

Some concerns/weaknesses:
1. The choices of sub-modules "near field" and "far-field" are quite arbitrary. 
2. Is the banded matrix just local attention? it seems so. if so, please call it a local attention so it is just less confusing or at least tell us why it is different.
3. Not all models are compared in the long range arena even though the results are already in the original paper. 
4. is language modeling the right choice of experiments for long range transformers? 





limitations_and_societal_impact: No
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The work proposes FMMformer, which borrows ideas from fast multipole method (FMM) to approximate the quadratic Softmax attention with a linear complexity. Specifically, the approximation consists of a near-field Softmax term (i.e. local attention) and a far-field multi-kernel linear attention. Some theoretical analysis is included to support the idea. The proposed model is evaluated on one synthetic copy task, long range arena and wikitext-103 language modeling. On the three tasks, the proposed model has a better quality compared to linear attention, though the gap between FMMformer and the standard transformer is still significant.
main_review: The key idea of the proposed model is intuitive and well motivated. The theoretical analysis is easy to follow. The practical instantiation of the proposed model is also neat. 

However, the empirical study of the work is relatively weak. 
- First of all, in terms of baseline, Sparse Transformer (i.e. local + sparse low rank) should be included given its closeness to the proposed model. In addition, the work only considers local attention baselines of bandwidth of at most 20, which could be too limited and won't be able to utilize the full parallelization of GPUs anyway. As the bandwidth increases, local attention could be a strong baseline.
- Secondly, for the 3 tasks in consideration, synthetic copy is overly simplified and long-range arena has relatively large variance and noise. As for wikitext-103, the reported performances of the baselines & proposed model are generally far from the SOTA, weakening the overall credibility of the evaluation.
limitations_and_societal_impact: Overall speaking, there won't be any additional negative social impact from the proposed model. In terms of limitation, it would be helpful if authors can discuss that the empirical studies are performed in relatively small scales and in text domain mainly.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposed the new efficient transformer (FMMformers), which decomposes the attention computation into direct and coarse-grained computations. The coarse-grained computation is handled by the low-rank matrix and the direct computation is handled by a banded matrix. The proposed method shows better performance on the LRA dataset and comparable performance on the language modeling with the original transformer 

main_review: The paper is well written and easy to follow. 

The proposed method is well-motivated from the physical computation of n-body problems, which seems to be a good extension to the linear kernel attention. It is also developed with the solid support of both theoretical and experimental results for the approximated softmax with certain error bounds. Experiments with multiple random seeds might be preferable to show the significance of the proposed methods. The attached code makes the paper easier for reproduction. 
limitations_and_societal_impact: (1) Implementation details: given that local window approach like Big-Bird or Longformer generally needs to have a customized kernel to achieve real speedup due to the caching issues. Just wondering if there exists any specific modification w.r.t the real implementation of the proposed method. 

(2) It is possible to have a full theortical time and memory complexity that takes the k also into account? Given that from the language modeling experiments, large bandwidth may affect a lot in the final performance. (20 v.s. 256 context length might not be eligible to be considered as "<<") 

(3) More experimental details: 
for Figure 5, is there missing one line about high rank with banded attention?

for the language modeling experiments, could the authors provide the sliding window that is used in the main text as well (256 in the appendix)? Moreover, is it able to have the results where the computation of the FMMformer and the transformer have the same compute while the FMMformer could have a longer context window, wondering if that is the more real application we want from the efficient transformer design?
review_title: null

Meta-review: This paper proposed a fast and memory-efficient transformer approximation, inspired by the fast multiple method (FFM), which combined the sparse and low-rank approximation. The method is well-motivated and easy-to-follow. The authors demonstrated the benefits of the proposed neural architecture empirically on synthetic data, LRA benchmark, and language modeling on WikiText-103.  

There are several existing work on combining sparse transformer with low-rank transformer,  as pointed by the reviewers (pp7v and MHtR), however, since these are the co-current work, the novelty of the submission should not be discounted. Actually, as opposite. it actually strengthens the significancy of the method. I personally like Sec 2.1 to motivate the FMM. 

The major criticism from most of the reviewers actually lies in the empirical experiment part, which makes the claim of the paper relatively weak. In my opinion, these suggestions are reasonable. For example, the comprehensive comparison with more baselines, detailed ablation study on the trade-off between accuracy, speed, memory vs. architecture parameters, and more practical tasks on real-world benchmarks should be included. The authors rebuttal addressed some of them, but some of them are still missing. 

In sum, the idea and new architecture proposed by this paper is novel and well-motivated, however, the benefits of this architecture is not well empirically justified. I hope in the final version, the authors can take the reviewers' comments into account to improve the weakness of the paper. 

 
Decision: Accept (Poster)