Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary
* This paper proposes a linear time and space attention variant that matches (or exceeds) the accuracy of standard attention while maintaining the speedup of prior work in linear time/space attention.
* The approach is centered around a linear approximation of softmax attention, and is extended with a gating mechanism similar to a GRU.
* The accuracy improvements from the gated extension are demonstrated via language modeling on WikiText-103, while the speed-ups are demonstrated on translation.

Contributions
* Demonstrates the importance of the choice of kernel in RFA, as prior results from Katharopoulos et. al [1] underperforms softmax attention, while this work gets comparable performance by changing the kernel.
* Proposes an extension of RFA with gating that improves accuracy on language modeling, relative to softmax attention.

Strengths
* The RFA-gated formulation is both more accurate and potentially faster (at least for decoding) than softmax attention, as demonstrated on language modeling.
* The writing was clear and thorough.
* The experiments support the claims of improved accuracy via choice of kernel and gating, and preservation of speedups inherited from the linear attention formulation.

Weaknesses
*  The improved accuracy and speed over the baseline transformer are great, and the experiments serve to nicely illustrate those independently. I would like to see a third application where these two qualities are demonstrated together.
* The gating mechanism could also be applied to the output of softmax attention, but that comparison is not included. Please correct me if this is incorrect.

Recommendation: Weak Accept
* Well-written and timely exploration of linear attention.
* Empirical results demonstrate accuracy improvement over softmax attention, while preserving the linear time complexity.
* Extension of RFA with a gating mechanism appears to be effective, but I do not believe the claim that it is hard to apply this to softmax attention is valid, leaving the main contribution an exploration of a couple different kernels for linear attention.

Questions
* Can you clarify how the RFA defined in section 3.1 differs from the linear attention in Katharopoulos et. al. [1]? What is different other than the choice of phi?
* Associative reductions such as those described in sections 3.1 and 3.2 can be computed in time logarithmic in sequence length (at the cost of n log n memory consumption) on a parallel device using a binary reduction or the prefix sum trick. Would this result in speed gains, or is the performance of attention in the parallelizable softmax setting already saturated?
* Are there experiments with a bidirectional gated RFA in the conditional setting, i.e. in the encoder for translation?

Nits
* The formatting of equation 5 is a bit strange, as the start of the equation is inline while the rest is not.

[1] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and Francois Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention. In Proc. of ICML, 2020.

Edit: I have updated my rating based on author response.

review_title: Linear-time attention with a gating mechanism that is both more accurate and faster than standard softmax attention

final_score: rating: 4: Ok but not good enough - rejection
review_content: 1. The logic in the introduction is a bit contradictive to me:

Some are able to achieve better asymptotic complexity (citations). while it
is more challenging to improve on shorter sequences: the additional computation steps required by
some approaches can overshadow the time and memory they save.

Doesn't this simply mean that for short sequences there is no such computational burden? 
I think the story starts with pointing out the importance for long-sequence but turns to the topic on short sequence
which is confusing. The need for short sequence acceleration needs to be justified IMO.

2. Following 1, the baseline should be added.

For a fair comparison, I think the baseline should add those methods as claimed in the introduction
(Lee et al., 2019; Child et al., 2019; Sukhbaatar et al., 2019; Beltagy et al., 2020, inter alia), (Kitaev et al., 2020; Wang et al.,
2020; Roy et al., 2020, inter alia) and let us know how badly they performed under the short sequence. In particular we don't know
if the sacrifice of short sequence time would benefit a lot in long sequences for existing methods. The current experimental baseline can't reflect this.

3. Is the speedup over total computational time or just the attention part?

To best of my knowledge, under many circumstances in particular for short sequence, attention alone might not be the 
most time-consuming part of the model. I think it will be helpful for authors to have a complete graph of the computational model used instead of only figure 1 concept graph. Specifically, is there
any feed-forward computation involved and how many layers of the models used in comparison.


4. Introduction of Eq 6,7 is confusing. 

Up to eq 5 it's clear whatr's going, but it comes from nowhere to intorduce these 2 modules in eq 6,7. So my understanding is that
RFA simply refers to the approximation of computing the softmax. So the statement:

for softmax-attention. The latter is typically used in two different ways in the transformer architecture, each resulting in a different computation for RF

is confusing as the RFA is now redefined. I believe RFA should only refer one thing and I don't think eq(6) and eq(5) leads to the
same result. On the other hand, eq 7 should be the same as eq 5. Is this correct?
In addition, the notation in (6) looks wrong to me. \phi(x) as introduced in eq 2 is in R^{2D} but S_{t-1} is in R{D}, not sure what does + mean in this context.
I couldn't find out where you properly define the meaning of D either.


5. Clarification of contribution

Eq 6,7 reads like RNN style update but the intuition is lacking. Do you want to claim that this structure design is inspired by RNN and it leads to a better result?
Put in another way, using RFA in transformer is from Rawat et al., 19 so do you think your major contribution is to design such 
a gated usage of RFA?


5. Discussion of D

Since RF is not the major contribution, you summarize existing results of FA in sec2.2. I think I'd like to see a discussion of
sufficient number D analytically or empirically. Could you also cite the convergence bound on this approximation? To me, D looks to be an important efficiency tradeoff. Say sequence length is M
and feature in d dimension. Original Attention is O(M^2 d). The computation of RFA
requires outer product, which is O(D^2d) so overall it's O(M D^2 d), if M is around 64 or 128 (common usage) and D is 64, I actually
don't see why RFA could improve 2x. Do you pre-compute and pre-store anything?


6. Time analysis on language modeling is not presented. Since it's a efficiency paper, I think it should be complete.



Overall, I think the paper provides an interesting view of discussion, but there are many flaws in the current version which needs to be corrected before a more serious consideration.  Especially, in terms novelty, the paper is relatively limited as the RF is explored in Rawat et al., 19. So my point 5 is important to answer and I would like to see all the details are clarified in order to make the contribution stronger. 


review_title: Interesting direction but the detailed/clarified discussions are needed

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper presents a linear time and space attention mechanism based on random features to approximate the softmax. The paper is clearly written and easy to follow. The results are convincing: not chasing SOTA, but comparing to sensible baselines, namely [Baevski & Auli 2019] for language modeling on Wikitext-103, and [Vaswani et al. 2017] for machine translation on WMT14 EN-DE/EN-FR and IWSLT14 DE-EN.

The difference between theoretical speed-up and experimental speed-up is honestly discussed, and the overhead of the random features is not swept under the rug. However, having an experimental study on the random features dimensions' impact on empirical compute time vs. approximation performance vs. end-task performance would have been a plus.

I had read "Rethinking Attention with Performers" when I reviewed this paper, and I originally thought it was the same paper, but (along with notation being different) they start to differ on page 3. Where "Performers" goes with positive orthogonal random features (to improve over vanilla RFA), this paper adds a gating mechanism: this adds the possibility to learn some monotically decaying attention over older context, similar to learned receptive fields of attention (as in e.g. [Sukhbaatar et al. 2019]).

Overall, this is a good paper, and I don't see why we should downplay it in light of simultaneous ("Performers" got on ArXiV on September 30th, the ICLR deadline was October 2nd) quite similar contribution that the authors took the time to discuss. (It would be even better if they could compare to it in a future version.)
review_title: Yet another "linear attention", still, a good paper!

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: ##### Summary:
This paper presents Random Kernel Attention which is based on replacing the kernel function in the Linear Attention with random projection kernels. In general, I think the method is novel and quite impactful. Nowadays, some people are still staying away from attention because of its quadratic time and space complexity. To the best of my knowledge, it is the first attention method with linear complexity that can match or even outperforms the conventional attention.

##### Strengths:
- The method is intuitive and interesting to me.
- The results are strong. Unlike Linear Attention, the proposed RFA outperforms the original multi-head attention baseline on both LM and MT tasks. This is quite impressive. Based on my experience the Linear Attention with ELU non-linearity can bearly match the performance of the original attention mechanism.
- The authors provide several in-depth analyses in the appendix. I like the experiments in C.2.
- It is nice to see that the authors confess that the training is actually increased when using the RFA compared to the original Transformer. Usually, the inference time and memory usage are more important in practice.
- It is great to see that the authors compare with the baselines that cache the query/key/value representations. Nowadays, some papers avoid it make their speedup look better.


##### Weaknesses & suggestions:
- It is not clear what D is used in the experiments. The authors just vaguely say that they don't observe the improvement by setting it great than 2d. However, it would be better to see plots at least in the appendix. Also, I wonder if it would behave differently with different d. Also, it would be great to see what exactly the number is in the experimental setup to make this paper more reproducible.
- The arccos feature maps have only D-dimensional features, unlike the Gaussian feature maps which have 2D. It is not clear whether the authors use the same D for both variants or double the D of arccos to keep the feature dimensions the same.
- After introducing the random projection weights, the number of parameters would increase. It would be better if the number of parameters and the inference speed are both provided in Tables 1 & 2.
- The authors should clarify that the time complexity in Table 3 is based on the assumption that we have infinite number of threads or GPT/TPU cores that can be scaled up when M is increased. Otherwise, the time complexity of training the softmax model is still O(M^2) because there is a matrix multiplication between matrices of sizes M-by-M and M-by-d. 

##### Questions:
- Based on the experiments, it seems that the Gaussian random feature maps don't really try to approximate 
- How would the gating mechanism perform on the encoder side? Similar to BiLSTM, half of the dimensions can be applied in a backward manner to make it bidirectional.
- Do you resample the random weights during the time? 
- I wonder if the authors will release their implementation. Based on my quick re-implementation, the proposed RFA doesn't really converge on some other dataset. I believe there might be some differences in how the parameters are initialized which is not clearly described in the paper. Admittedly, there is a chance that I have a bug in the code.
- Based on the conclusion in C.2 that RFA is not approximating the softmax kernel, would it be better if we just trained those projection matrices instead of fixing them as random matrices?

review_title: Interesting and impactful

Meta-review: 
This paper proposes an efficient attention mechanism linear in time and space using random features.
The approach has some similarities with the simultaneous ICLR 2021
submission "Rethinking Attention with Performers", with a key difference of a gating
mechanism present in this work, motivated by recency bias. This paper is a
valuable contributions to the efficient attention research topic. The reviewers
appreciate the experiments and the in-depth analysis. I recommend acceptance.

A noteworthy concern brought up in the discussion period has to do with whether the attention mechanism dominates the feed-forward computations in the neural network, and how much this is architecture-specific. The authors provide TPU timings, but I encourage the authors to add a discussion and timings of relative performance of feed-forward vs. attention layers that covers GPU and CPU optimizers as well.
Decision: Accept (Spotlight)