Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a set of techniques called Fast Attention Via positive Orthogonal Random features (FAVOR+) to approximate softmax self attention in Transformers and achieve better space and time complexity when the sequence length is much higher than feature dimensions ($L\gg d$). The resulting architecture, Performers, is provably and practically accurate in estimating regular full-rank attention without relying on any priors such as sparsity or low-rankness. It can also be applied to efficiently model other kernalizable attention mechanisms beyond softmax, achieving better empirical results than regular Transformers on some datasets with such strong representation power. Performers are tested on a rich set of tasks including pixel-prediction, language modeling and protein sequence modeling, and demonstrated competitive results with other examined efficient sparse and dense attention models. I think this paper is a solid step towards more efficient Transformers for practical long-sequence data, and should be accepted. Below I raise two potential questions and look forward to the solutions in the future. 

1. For Performers, speedup can only be achieved when $L\gg d$, which means Performers might have less advantages on wider Transformers. The time complexity of Performers for approximating the attention matrix is $O(Ld^2\log(d))$, while a regular Transformer has a time complexity of $O(L^2d)$ to compute the attention matrix. From Figure 3, it looks like for a model similar to BERT-Base, Performers is only faster when the sequence length is larger than 512. I wonder how wide Performers can be while  preserving faster speed than Transformers with the same size on the current datasets, and how their test scores compare. 

2. It looks like Performers do not converge as fast as Transformers on larger language modeling datasets like PG-19. I wonder whether similar phenomenon will happen in other domains when the dataset is larger, and feel quite curious about the cause.
review_title: Another step forward towards efficient transformers

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This is a solid paper that presents a computationally less expensive, unbiased, low-variance estimator of the Transformer architecture. 

**Strengths**:
1. The authors provide mathematical guarantees for the suggested estimator.
2. The estimator (called FAVOR+) seems a more scalable replacement for regular attention.
3. Theory is empirically verified in a variety of experimental settings.

**Question**: 
In Introduction, you mention that your method does not rely on low-rankness, but doesn't your equation (4) as well as Fig. 1 assume that the attention matrix $\mathbf{A}$ allows low-rank decomposition? (I suppose $r<d$)

**Suggestion**:
Will it be possible to compare a pre-trained Performer-based encoder (like BERT) against its competitors (Linformer, Reformer) on a [GLUE benchmark](https://openreview.net/pdf?id=rJ4km2R5t7) or on [probing tasks](https://openreview.net/forum?id=SJzSgnRcKX)? I see that you compare them (Per-/Lin-/Re-former) against the original Transformer on the pre-training task itself (Fig. 5), but I am wondering how well the pre-training performance transfers to downstream tasks in each case.

**Minor issues**:
1. In the proof of Lemma 1 you first prove that $\exp(\left\lVert\mathbf{x}+\mathbf{y}\right\rVert^2/2)=\mathbb{E}_{\omega\sim\mathcal{N}(\mathbf{0},\mathbf{I})}[\exp(\omega^\top\mathbf{x})\cdot\exp(\omega^\top\mathbf{y})]$, however this is simply an m.g.f. of $\omega$ at $\mathbf{x}+\mathbf{y}$, and thus IMHO does not need to be redirived. (I assume that the formula for the m.g.f. of a multivariate Gaussian random vector is well-known).
2. Similarly, eq. (16) is the m.g.f. of $\omega\sim\mathcal{N}(\mathbf{0},\mathbf{I})$, it does not have to "immediately follow from" some other fact.

**Typos**:
1. In eq. (18), a norm is missing in the last term: $\mathbf{z}^2$ -> $\left\lVert\mathbf{z}\right\rVert^2$.
2. In the text after eq. (18): inequality -> equality

**Update after the author's response**: The authors have answered my questions during the rebuttal period and I am satisfied with the response. Hence updating my score: 7 $\to$ 8.
review_title: A solid paper that will likely affect the way Transformers are estimated

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: ##########################################################################

Summary:
 

The paper proposed a theoretically grounded O(N) approximation of the softmax attention. The key idea is to interpret attention as a kernel function and construct the random feature projection that can reproduce this kernel. It is highly non-trivial to derive a feature mapping that can accurately approximate the softmax kernel. To better approximate the softmax kernel, the author proposed some important design choices, all of which are supported by theoretical and empirical evidences. The author showed that 1) adopting non-negative random features is very essential to the approximation and the proposed Positive Random Features (PRF) can effectively reduce the variance when the attention values are small, 2) drawing orthogonal random matrices can further reduce the variance of the approximation, 3) the final proposed Performer model runs faster, takes less memory, and has better performance than other O(N) and O(N logN) attention methods.


##########################################################################

Reasons for score: 
 

The paper is very well-written and should be accepted. This is an important landmark in the research about O(N) attention. The design of the random feature mapping is reasonable and theoretical analysis is convincing. Experiments show that Performer is better than the other O(N) attention methods and also other efficient attention methods.
 

##########################################################################

Pros: 
 

1. The paper gives a provable O(N) approximation of the softmax attention. The method works without assumptions on the structure of the attention map (like sparsity). The theoretical proofs provide good insights on how to design a good O(N)-complexity approximation to the  attention mechanism.

2. Apart from approximating the softmax attention, the proposed FAVOR+ method can be utilized to approximate other attention kernels. In fact, the author has experimented with Performer-ReLU, which outperforms Performer in some experiments. This provides the insight that softmax attention may not be the best choice.

3. The author conducted very comprehensive ablation studies on different components of the proposed method. This includes: 1) effectiveness of using the positive features, 2) drawing orthogonal random samples, 3) redrawing the random samples
 

##########################################################################

Cons: 
 

1. From Figure 5 and also Figure 15, periodic redrawing is quite essential. However, the author has not mentioned about the implementation details on how they redraw the random samples and how to choose the period. For me, I feel that this hyper-parameter should be important because the model may need to ensure that each group of samples has been trained for a sufficient amount of time.

2. Performer-ReLU has replaced the attention kernel and can sometimes be better than the softmax attention. Thus, I feel the author may also want to compare with the linear attention method in ((Katharopoulos et al., 2020) "Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention".


##########################################################################

Questions during rebuttal period: 
 

Please address and clarify the cons above 
 

#########################################################################

Typos: 

(1) Page 5, after "than those from SM_{2m}(x, y)", there is an additional right bracket.
review_title: Theoretically grounded O(N) approximation of the softmax attention

final_score: rating: 7: Good paper, accept
review_content: ### Summary

The authors propose to use the kernel feature map self-attention formulation introduced in [1] to efficiently approximate the softmax attention. The main contribution of the paper lies in the proposed _positive random features_ that can approximate softmax with a strictly positive feature map without which the training is unstable. The authors also show that an approximation of softmax is not necessary for good performance and actually use ReLU random features to achieve their best results when training from scratch.

### Strengths

- The paper deals with a very pressing and important issue, that of the scalability of self-attention.
- The positive random features are also useful outside of the context of self-attention for efficiently approximating softmax.
- The experimental results provide strong evidence about the performance of training transformers with kernel feature-maps.

### Weaknesses

The biggest weakness of the paper in my opinion is the lack of comparison with a simple feature-map as proposed in [1]. Since the authors also use the ReLU random features, we establish that approximating softmax is not necessary for good performance.

1. What would the performance be if a simple deterministic feature map was used?
2. What would it be if the computational cost was equalized either by adding more layers or by increasing the dimensionality of the queries and keys?

The second weakness of the paper concerns the evaluation of the practical softmax approximation capabilities. I find the theoretical results interesting and important but I would like more experimental evidence. Without fine-tuning, the authors provide evidence that the approximation does not work (Fig 5).

1. What would happen, for instance, in a toy task where the Lipschitz constant of the transformer layers was kept low? How big would the feature map need to be in order for the approximation to work in such a simple case?
2. What is being approximated in Fig 4? Is it a randomly initialized attention? What is the rank of the attention matrix?
3. How good would the approximation be for an attention matrix that is almost full rank and how many features would we need then?

### Reasons for my recommendation

I am recommending acceptance because I believe that the positive random features is an important contribution both for transformers and for kernel approximation. In addition, the experimental results are impressive and show that fast kernelized attention indeed works in practice. My only reservation for a higher score is, as mentioned in the weaknesses section, the lack of comparison with simpler feature maps under equalized computation time.

[1]: Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
review_title: Great theoretical and experimental results but missing time equalized comparisons with simple baselines 

Meta-review: This is a solid paper that proposes a new method for approximating softmax attention in transformer architectures that scales linearly with the size of the sequence. Even though linear architectures have been proposed before using a similar idea (Katharopoulos et al 2020), this paper provides a better solution along with theoretical analysis and makes a rigorous empirical comparison against other methods. All reviewers agree that this is a strong paper that should be accepted. I suggest citing the recent paper https://arxiv.org/abs/2011.04006 (Long Range Arena, mentioned in the discussion) which provides further comparisons on long-range benchmarks, including the method presented in this paper and Katharopoulos et al 2020, along with a detailed discussion of the differences between the two methods.
Decision: Accept (Oral)