Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper introduces the Attention Free Transformer (AFT), an alternative to multi-head attention (MHA) operation in Transformer. While the motivation of the authors is to replace MHA with more cost-efficient operation, it is not clear whether the proposed method is the better alternative.

Pros:
1. AFT shows better asymptotic space and time complexities than MHA.
2. The implementation of AFT allows for faster training with larger batches.

Cons:
1. Theoretical analysis is conducted for the extreme case of num_heads=hidden_dim and ReLu non-linearity. It is not clear how to generalize them to more practical cases with num_heads<hidden_dim and SoftMax non-linearity. There is a missing link between the theory (and motivation arising from it) and the best-performing implementation (AFT-softmax).
2. AFT-softmax does not fully complies with the title of the paper as the proposed operation contains aggregation via softmax. Also, despite the claim that AFT can "be readily adopted as a plug in alternative to Transformers", the architectures from the experimental section also use vanilla MHA blocks in addition to AFT. Thus, it is an exaggeration to say that the Transformers evaluated in the paper are attention-free.
3. Language modeling experiments on WikiText-103 draw an ambiguous picture. Baseline Transformer implementation has large positive difference between train and val/test PPL at 70k iterations which decreases as the training progresses. For AFT models, on the other hand, this difference is negative which might suggest that they have already overfit at 70k iterations and they will never reach the resulting performance achievable by the baseline. The plot with train&val PPL / number of iterations for those experiments would be more informative than the table.
review_title: A replacement to multi-head self-attention operation with vague usefulness

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper suggest an alternative to the Multi-Head Attention (MHA)  operation, which is one of the core elements in Transformers models. The proposed alternative is targeting the non-linear soft-max operator (in the MHA) and suggest to replace it with the "relu" operator. After doing so they could reformulate the new attention mechanism as a O(T) operator instead of the original O(T^2) operator (where T is the context size).

Arguably, the MHA is one of the important components of the transformers architecture and reducing its memory and time complexity is crucial to increasing the training batch-sizes and the usage of more context.

The paper is nicely written and presents a comprehensive experimentation section, ranging over several machine learning benchmarks in computer vision and NLP.

Strong points:
- simple solution
- comparable results with reduced memory and latency
- the paper is clear and nicely written  
- comprehensive experimentation section

Weak points:
- moving from AFT-relu to AFT-softmax is is not sufficiently motivated (only empirically) i would expect more experimentation to clear this point
- not all experiments show improved or comparable results (for example table 5)
review_title: Replacing the soft-max in the Mult-Head Attention operation with "relu" for Transformers (O(T^2) -> O(T))

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes an efficient transformer variant by replacing softmax in the self-attention layer with a RELU activation and arranging the computation using element-wise products and global/local pooling. This reduces complexity to linear complexity in the non-autoregressive case and log-linear complexity in the autoregressive case. The evaluation shows that it can reach the performance of a vanilla transformer in most of the examined tasks while having fewer memory requirements in general. 

**Strengths**: 

The paper is reasonably well-written and clear for the most part. The problem of scaling transformers to longer sequences is an important one since transformers cannot deal otherwise with long sequences due to their quadratic complexity. 

The proposed idea is interesting and reminiscent of recent methods that re-arrange self-attention computation using kernels albeit it differs in the way the computation is carried out. This one is simple computation-wise and does not aim to approximate the original computation in any way. 

The evaluation performed on multiple tasks shows that the proposed approach can reach the quality of a vanilla transformer and be more memory-efficient. 

**Weaknesses**: 

(1) The motivation of AFT and the positioning with respect to prior work were somewhat weak. The introduction does not acknowledge recent efforts towards efficient transformers and what is the unique contributions of this work. What are the benefits of AFT compared to recent established efficient transformers such as Sparse Transformer (Child et al., 2019), Reformer (Kitaev et al., 2019), or Linear transformer (Katharopoulos et al., 2020)? It is unclear why one should prefer the proposed variants over existing ones both from theoretical and practical perspectives.  Related work states some previous efficient transformers without any individual discussion about their merits or limitations in comparison to AFT. 

(2) One major limitation that stands out from the experiments, despite their size, is that there is no head-to-head or controlled comparison with a previously established efficient transformer such as the ones mentioned above. The results compared to Sparse Transformer given in Table 3 are not directly comparable since the model size and design are quite different.  In brief, it is not very clear what are the practical benefits compared to previous efficient alternatives. 

(3) The memory benefits are not reflected or they are not as important when looking at the quality achieved in the tasks where a speed-quality trade-off was reported.  In language modeling,  AFT has higher perplexity (even when it uses a much larger number of parameters) which makes the memory benefits less interesting. In MT, AFT reaches the performance of the baseline but then the efficiency benefits are not present. So, I am curious is it the same in the two former tasks when comparing to the vanilla transformer? Under what circumstances we should expect AFT to reach vanilla transformer performance and still offer clear efficiency benefits when using the same setup?

(4) In terms of training speed, AFT is generally slower than the vanilla transformer when the form reaches the same quality as the latter. Also, it is especially slower when the depth is small in Table 2 (~30% with 12 layers). Could the authors elaborate a bit on why that happens?  Moreover, it would be useful to show in Table 2 what is the quality (NLL or bits/dim) achieved by each model because it's hard to tell how good the speed-quality tradeoff is. 

(5) Recent studies have shown that it is possible to speed up inference time using efficient transformers (see above). What is the benefit of AFT during inference time? 
review_title: Interesting idea, motivation & evaluation require more effort

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper introduces a method to replace qkv-attention by a simpler, efficient building block. This is done by element-wise multiplication of a query representation with a compressed kv-memory. Per-channel attention pooling is used to compress the kv-memory. The model is derived from a softmax-free version of self-attention. The results show good performance on a couple of standard image and language modeling tasks while occasionally exhibiting favorable training speed. The results are largely on par with transformer baselines.

I have a couple of major concerns with this paper:

1) The derivation: The model is derived by using relus on the QK dot-product andthen simplified in Eq. 4, which basically makes the resulting model different from the starting point (Eq. 2-3). The final model is further changed by a applying a softmax over the keys, channel by channel (Eq. 5). So I am not sure how the resulting model actually still relates to the original formulation in Eq. 2. That leaves me with the impression that the derivation just exists to establish a connection with standard qkv-attention which is a bit hand-wavy. The results (Figure 2) even suggest that without a per-channel softmax over the input elements, the method doesn't work well. The arbitrariness of the derivation is exemplified further by the fact that one could have similarly started from using no non-linearity at all after the dot-product, which directly leads to Eq.4. The non-linearities on K and Q could be arbitrarily applied before the dot-product.

2) The efficiency comes at a cost of a strong memory bottleneck as we basically pool the entire memory into one fixed state on hidden size. That won't scale well to larger inputs. The conducted experiments are mostly on smaller scale settings (small images, standard text lengths) which reinforces my impression that this approach won't help solving the efficiency issues of self-attention. Using larger receptive fields (though costly) typically leads to better performance in standard self-attention. Here, however, due to the strong bottleneck results are getting worse after a point (Table 1). This makes also sense because the memory pooling imposes a very strong information bottleneck, that is, much of the memory has to be forgotten.

3) There should be at least some controlled baselines from related work that tries to eliminate the self-attention bottleneck with similar compression techniques, e.g. Linformer, Sinkhorn Transformer, Compressive transformer, Performers.

4) The potential efficiency gains are never put to practice, that is, the authors don't show any application of the model to very large input sequences.


Other comments and questions:

- The work reminds me of dynamic convolutions [1], which compute depth-wise convolution kernels dynamically based on the current context. Here we compute a dynamic depthwise 1x1 convolution on the Qs, based on the context around each Q. I think this connection might be more closely connected to the proposed model than attention.

- Why were the models not trained till convergence in on WikiText-103?


[1] https://arxiv.org/abs/1901.10430
review_title: Hand-wavy connection to qkv-attention, missing baselines and no proper exploitation of increased efficiency.

Meta-review: The new non linearity proposed in this paper present interesting observations and improvements on image and text datasets.
However, reviewers point out that there should’ve been more comparisons to other efficient transformers and on more datasets.
The speed improvements are also not clear.
I’d encourage the authors to revise and submit in the future.
Decision: Reject