Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: To help Transformer learn long sequence efficiently, the paper performs attention on selective timesteps that have high expire-span scores. For each timestep, the expire-span score is computed by mapping the corresponding hidden feature to a number, which is learnt during training. Soft masking is applied to make the learning differentiable. An additional loss is introduced to reduce the average span, making the attention sparse. The proposed attention is integrated into each layer of Transformer and tested on several synthetic tasks and two language modelling datasets, yielding promising results. 

Pros:
- The proposed solution (computing expire score and minimizing the average span) is elegant and seems novel within Transformer context
- The properties and behaviours of the method are well illustrated with detailed analysis and visualization
- Diverse experiments are conducted

Cons:
- Insufficient comparison with other Transformer-based baselines 
- The results on real data are weak

Detail comments and questions

- Sec 4.1, the equation computing o_t should be a summation over i
- Before Transformer, sparse attention has been studied deeply in the literature. It may be beneficial to review some works (e.g., [1,2,3]) and try to integrate them into Transformer as additional baselines to make the experiment stronger. 
- No experimental result demonstrates that the method can reduce computation complexity. Please consider including a comparison of running time or physical memory usages between your method and other Transformers
- It is unclear what are the baselines mentioned in the experiments. Are they vanilla Transformers? How did the authors control the memory size of the baseline as in Fig.3, 4 and 7?
- For some synthetic tasks, it is better to include stronger baselines [4,5] to show the advantage of the proposed method over other variants of Transformer
- In Table 2, the performance gap is significant. Is it possible to improve your performance with more parameters? 

[1] Ke, Nan Rosemary, Anirudh Goyal ALIAS PARTH GOYAL, Olexa Bilaniuk, Jonathan Binas, Michael C. Mozer, Chris Pal, and Yoshua Bengio. "Sparse attentive backtracking: Temporal credit assignment through reminding." In Advances in neural information processing systems, pp. 7640-7651. 2018. 

[2] Martins, Andre, and Ramon Astudillo. "From softmax to sparsemax: A sparse model of attention and multi-label classification." In International Conference on Machine Learning, pp. 1614-1623. 2016. 

[3] Niculae, Vlad, and Mathieu Blondel. "A regularized framework for sparse and structured neural attention." In Advances in neural information processing systems, pp. 3338-3348. 2017. 

[4] Gonc¸alo M Correia, Vlad Niculae, and Andre FT Martins. Adaptively sparse transformers. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 2174–2184, 2019.  

[5] Sainbayar Sukhbaatar, Edouard Grave, Piotr Bojanowski, and Armand Joulin. Adaptive attention ´ span in transformers. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 331–335, 2019a. 

review_title: A solid improvement of Transformer's attention mechanism, yet the baselines and empirical results are not strong

final_score: rating: 6: Marginally above acceptance threshold
review_content: Modified score: thank you authors for your thorough response. Given the new information and baselines, I think this is a promising paper that passes the acceptance threshold.

Overall Quality: The authors present a method to improve the efficiency of transformer models when computing attention over previous time steps. Although this presents a neat idea that has the potential to improve an increasingly important model architecture, the experiments fall short of matching the claim that this method provides enables more efficient attention computation over memories _in practice_. Specifically, their baselines do not include relevant transformer modifications aimed at efficiency and they provide no detailed analysis on the memory size in practice. If the authors included more thorough experiments, this would be a strong paper. In their absence, it is marginally below the acceptance threshold. 

Clarity: The abstract, introduction, background, and methods section were detailed yet easy to follow. The comparison of time complexity of prior work in the background section was particularly helpful. However, this precision did not carry over into the experimental section, which lacked thorough experimentation (detailed under weaknesses below) and figures 3-5 were out of order relative to the prose (the latter point is minor and does not affect my rating).

Significance: The potential impact is very high, especially as applications for transformers grow. If the authors could address the weaknesses outlined below, this could be an enormously helpful augmentation to the transformer architecture.

Strengths:
- The authors focus on an important problem for a very relevant architecture.
- The writing is clear and enjoyable. Section 3 in particular is a very friendly introduction to transformer time complexity.
- Evaluations performed over a variety of applications, spanning simple/toy to more realistic tasks.

Weaknesses:
- Corridor, instruction, portal, copy, pg-19, and colliding objects tasks only show comparisons for standard transformer models, as opposed to (at least one or two) comparable efficiency-optimized models. Giving the authors the benefit of the doubt, the first few experiments may serve more as proofs of concepts, where direct comparison with prior work is not as relevant or useful. But this leaves only one task in the paper with comparison to prior work on improving transformer efficiency: en-wiki-8. On en-wiki-8, the authors compare with just 1 modification and the improvement seems rather small. Small margins of improvement alone are not enough to reject a paper, but, given that this is the only result with a head to head comparison of efficiency optimized transformers, it makes it difficult for the community to discern the contribution of the work. Furthermore, on pg-19, copy task, and object collision, the authors do not provide the memory size/average memory size/effective memory size. This makes it difficult to understand if performance gains correspond with performance improvements, which is the methods stated purpose.
- Intuitively, an inductive bias to expire memories would make a learned model more brittle when transferring to new tasks. E.g., in the instruction task a new form of instruction may become relevant in a test task that was never relevant in training tasks Why is this a reasonable trade-off to make?

Question:
- What value is shown in table 2? The caption says bit-per-byte, but the numbers are inconsistent with figure 7.
- in figure 11, how is memory computed?
review_title: Impactful Idea with Clear Exposition, but Experiments Fall Short

final_score: rating: 5: Marginally below acceptance threshold
review_content: **Summary**
The paper proposes a method for overcoming the long-term memory bottleneck of transformers. The idea is to assign a value (expire-span) to each formed memory, which indicates how long the memory should be stored and be available for the transformer to access it. The authors demonstrate the performance of their approach on a set of
synthetic and character-level language modeling benchmarks. 

**Significance**
While the idea seems to be quite interesting and the presentation of the paper is clear and sound, I have the following concerns:

- As the expire-span does not seem to be updated, the model must know how long to keep the memory when the memory is formed. Couldn't this potential cause issues when information arriving in the future would influence
the span of how long the memory should be kept? 
- From the author's descriptions, the method appears relatively brittle to hyperparameter choice. In particular, the method requires some sophisticated form of regularization for the performed benchmarks. Thus, raising my concerns about the stability and scalability of the approach. 

I would appreciate it if the authors could elaborate on my concerns.

- The paper misses important related work in this domain. The paper Gers et al. "Learning to forget continual prediction with LSTM" already proposes a mechanism to remove memories that are not needed anymore. Moreover, the proposed approach is adaptive as for each token, the network decides if it should clear some of its memory. 


review_title: Overcoming the long-term memory bottleneck of transformers

Meta-review: The paper studies the problem of identifying what information to forget in attention mechanisms, with the goal of enabling attention mechanisms to deal with longer contexts. This is a simple yet intuitive extension:  self-attention is augmented with an expiration value  prediction. Experiments were carried out on NLP and RL tasks.
Overall, the paper has novelty in the proposed idea, however, there are concerns about the strength of the experiments; that the experiments fall short.
Decision: Reject