Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a variant of the transformer network. The authors base their work on their analysis of softmax attention. They argue that softmax works well because of two reasons (i) it stabilizes training due to reweighing the attention as well as associated connections within the network, and (ii) it forces non negative values in the attention matrix. Utilizing these observations, they propose two modifications (i) a linear projection kernel i.e. ReLU to compute similarity, and (ii) a cosine function for reweighing the attention values. With exhaustive experiments on 5 benchmarks, authors demonstrate that the proposed modifications lead to state of the art performance with reduced computational compelxity.   
main_review: Strengths
+ The paper is very well written and organized. It explains the problem and the proposed solution clearly.
+ The authors have been thorough in experimental analysis, and have shown the results on benchmarks as well as the generalization ability of the method. 
+ The idea of reweighing with a cos based function is faily novel. 

Weaknesses
- In Section 3.2,  it is mentioned that "in typical natural language tasks, the feature dimension of one head is always much smaller than the 
 input sequence length N". What implications it could have when d is not that small. Would the analysis will still be applicable (especially the computational speedup for domains such as images) ?
-  In Table 4, results on "Pathfinder", the method significantly lags behind the state of the art (~10%). An explaination would help understand the challenges of this particular setting. 
- As the method is shown to significantly outperform state of the art on a few benchmarks, a few examples on where it performs better while the other methods perform inferior should be provided to qualitatively analyse the improvement. 
- A few typos (i) Section 3.1 "...the Eq. 2 become" -> Eq. 2 becomes (ii) Section 3.4, "...such locality bias, ie.,..." -> i.e. (note the dots)

summary_of_the_review: The paper is generally well written and the problem is motivated clearly. The paper also highlights contribution with reference to the compared methods. The experiments (empirical) are exhaustive, however, a few qualitative results on explanations of a few disparities in the performance of the proposed method (as indicated in the detailed review) would help understand the impact of the proposed method better.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a substitute of the vanilla self-attention module, which claims a linear complexity. Like Performer and many other previous works, it introduces kernel functions and change the computation order among QKV in the self-attention module. Essentially, it replaces softx with ReLU and a cosine operation. Experiments are done on several benchmarks.
main_review: ## Strengths

1. The proposed method accelerates the inference speed of the model.

## Weakness

1. The motivation of using ReLU is unclear. Though softmax promises a non-negative weight, there is no evidence showing that non-negative weights is essential.

2. The motivation of cosine operation is unclear. The success of self-attention partly attributes to its ability of building long-distance dependency. The authors introduce locality into self-attention through consine operation but do not show its rationality.

3. Lack of essential ablation studies. How about the model without ReLU?

4. Limited improvement. In terms of Table 6, the performance gain induced by the cosine operation is limited (~0.13) on some models.
summary_of_the_review: Totally, I think the paper is still not well-prepared for publication.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work introduces a simple and elegant way to incorporate recency bias for kernelized linear attention mechanism using cos-based re-weighting mechanism.  This cosine re-weighting can be effectively implemented via query and key matrix transformations for linear attention mechanisms. The authors experiment with LRA, and both language modeling with autoregressive and bidirectional setups to show the efficacy of proposed method.
main_review: Strengths:
- The proposed method is simple and intuitive and experimentation on both LRA and real world language modeling task shows that it provides better speed-accuracy trade-offs when compared against other effective attention mechanisms.
- The paper is well written and easy to follow.

Some questions and concerns:

- Related work section could be expanded to include discussion on other efficient attentions such as:
    - Approximating softmax atttention:
        - SMYRF: Efficient Attention using Asymmetric Clustering
        - Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention
        - Fast Transformers with Clustered Attention
    - Sparsity pattern
        - Efficient Content-Based Sparse Attention with Routing Transformers
    - Low rank projections:
        - Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks
- Related work on the properties for kernelized attention (non-negative similarity scores):
    - Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernel

- Clarification:
    - For bidirectional modeling, why are the models pre-trained only to 50K iterations? From figure 4, the validation perplexity still seems to be decreasing especially for the vanialla attentions.
    - In the table 1, is $\phi_{ReLU}$ linear attention with ReLU as the non-linear activation to get positive similary scores?
    - Similarly for table 6, without re-weighing is linear attention with ReLU activations?

- Relation with relative positional encodings for linear attentions:
    - The cosine re-weighing can also be looked as an efficient way to introduce relatve positional bias to the linear attention. In this regard it would be good to contrast this to recently introduced relative positional encoding for linear attention such as (a) Rotary Position Embedding and (b) Relative Positional Encoding for Transformers with Linear Complexity       

- Page 5: "The non-linear re-weighting mechanism introduced by the softmax attention can concentrate the distribution of the attention weights and therefore stabilize the training process. It also means that, to some extent, it will punish far-away connections and enforce locality." While this is empirically observed, softmax normalization doesn't introduce such inductive biases. It might be better to rephrase this differently.

summary_of_the_review: This work introduces a simple mechanism to add relative attention / locality bias to linear attention to significantly improve their performance. The results showcase that using the proposed cosine re-weighting the linear attention achieves similar performance to vanilla transformers while being significantly faster.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents cosFormer which presents a linear operator to replace the softmax operator in calculating self-attention for transformer architectures, maintaining competitive predication accuracy while enjoying linear space and time complexity instead of quadratic costs compared to the vanilla baseline. Under this context, the authors emperically show that two factors are critical to improve the efficiency of transformers: (1) the self-attention matrix should have non-negative elements and (2) aggregating negatively-correlated information needs the non-linear re-weighting strategy. Based on the insightful analysis, the proposed cosFormer adopts ReLU and the Ptolemy’s theorem (cosine re-weighting) in designing a linear replacement of the softmax operator. The performance of cosFormer is validated with the language modeling (autogressive in both causal and non-causal cases) on WikiText-103 dataset,  the finetuning on a lot of downstream datasets such as GLUE, IMDB and AMAZON, and the comparison with state of the art methods on the long-range-arena benchmark.  
main_review: **Strengths**

- The paper is well-written. With a clear logic flow, the paper is also easy to understand.   

- Two factors for improving the efficiency of transformers: (1) the attention matrix should have non-negative elements and (2) aggregating negatively-correlated information needs the non-linear re-weighting strategy, are reasonable, especially the latter one.

- The proposed cosForm, leveraging ReLU and  the Ptolemy’s theorem (cosine re-weighting), is simple yet new, to the best of my knowledge. Glad to see it shows a good accuracy-efficiency tradeoff when applying it to replace the softmax operator in calculating self-attention for transformers. 

**Weaknesses**

- In the Method section, when analyzing the computational complexity for the vanilla self-attention and the linearized design, the authors assume " The input length is N and feature dimension is d, with d << N." However, in the experiments, such an assumption does not well hold. For instance, in section 4.1, the sequence length is 512 while the projected feature dimension is 1024. In this perspective, I am concerned by the claimed motivation/advantage of the proposed method, can "linear space and time complexity" still be well supported? 

- The limitations of cosForm should be discussed, particularly a more in-depth discussion of its connections to many existing works is necessary. 

- As for the comparison of runtime speed in training and inference on the long-range-arena benchmark, did the authors adopt the same transformer architecture for all methods? Why different methods sometime show distinct trends for runtime speed in training vs. inference, e.g. Linear Trans. vs. cosFormer?

- How about the performance of applying cosFormer to other tasks such as in computer vision besides NLP tasks? 

- Some grammar errors or typos:

   on page 2, "Kitaev et al. (2020) group"->"Kitaev et al. (2020) groups"

   on page 4, "a computation complexity of O(Nd)"->"a computation complexity of O(Nd^2)"

   on page 7, "despite Longformer (Beltagy et al., 2020) achieve"->"despite Longformer (Beltagy et al., 2020) achieves"
summary_of_the_review: Please see the comments in "Main Review".
review_title: null

Meta-review: This paper introduces a new linear attention mechanism for transformer based models.  This is accomplished by replacing the softmax in the standard transformer self-attention with a cosine-based re-weighting mechanism.  The empirical results are good, and cosFormer generally outperforms existing efficient transformers for autoregressive language modeling, fine-tuning, and on the long range arena.

The reviewers were generally positive regarding the paper, with all reviewers voting to accept.  The discussion period focused on particular choices regarding the ReLU activation function vs. other non-negative activation functions, further motivating the cosine operation, and comparing the speed of cosFormer vs. other efficient transformers.  The authors responded by providing additional ablations to empirically validate the choice of ReLU, motivated the cosine operation by noting that it introduces a locality bias, and further described the computation requirements of their transformer vs. prior work.

Overall, this is an interesting addition to the linear / efficient transformer literature, with solid empirical results supporting the various design decisions.
Decision: Accept (Poster)