Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, authors propose a new attention algorithm to operate the input sequence recurrently. Each time, the staircase attention process the seen and unseen tokens at the same time. They conduct several experiments on various tasks including ones which can be done by the standard Transformer. For other tasks, their method try to obtain a better efficiency vs performance tradeoff.
strengths_and_weaknesses: Strengths:
1. Their idea is easy to follow and their motivation is clear.
2. They conduct a list of experiments to show the performance of their models and compare to other models.
3. Comparison to relevant models is sufficient and clear.

Weakness:
1. My major concern is the tradeoff between the standard staircase attention and cased one. It seems that staircase attention is able to obtain much better performance than cached attention but with low efficiency. For the cached one, it can not achieve great performance compared to other models such as feedback transformer. Can you find a better tradeoff between cache and original staircase attention.
2. Will you release the code? It seems not straightforward to implement the proposed method.
3. Is that possible to try various recurrent steps for cached staircase (or do I miss something here)? Also ablation study between M and N for cached staircase attention.
questions: Please refer to the above section.
limitations: Yes.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper falls into a set of efforts that incorporate recurrence mechanisms in Transformer-based models while keeping the model reasonably efficient. While Transformers have been outperforming recurrent models in a number of practical tasks, some prior works have highlighted limitations of Transformer's feedforward-like architecture on tasks that involve state-tracking (among others).
 
Several prior works have tried to integrate recurrence in a Transformer-like architecture to mitigate such limitations but most of them end up being computationally inefficient compared to standard Transformers. One such approach was Feedback Transformer (FeedT) which this paper builds on. Although feedback Transformer reportedly performed better than Transformer across different tasks, it suffered from efficiency issues. This paper takes a step towards mitigating the efficiency issues while preserving some of the benefits of recurrence.
 
They propose a modified version of attention architecture namely Staircase attention which recurrently processes different chunks/blocks of tokens and processes each chunk in a parallel manner. The computation for each chunk depends on the state of some previous chunks which makes the model recurrent. Compared to FeedT which incrementally processes each token (like an RNN) this reduces the computational cost by a factor of the size of the chunks. Additionally, each chunk can go through multiple recurrent computations. They also introduce a cached version of the model where the number of recurrent computations for each chunk is limited to reduce computational costs. They compare their approach against several Transformer variants and report the performance on 3 language modeling and 2 synthetic algorithmic tasks. Their results indicate that Staircase models achieve near-perfect accuracy in synthetic tasks while performing well on language modeling tasks.
strengths_and_weaknesses: 
 
### Strengths
 
(S1) **Simplicity.** The proposed idea seems simple and does not seem to make tedious modifications to standard Transformers. From the results, it seems to achieve the advantages of both recurrence (strong performance on state tracking tasks) and attention (in terms of preserving efficiency) while obtaining competitive performance on practical language modeling tasks. 
 
(S2) **Good results.** The experimental setup and evaluation seem sound. In particular, relevant baselines such as universal Transformers and Transformers-XL have been included apart from direct ones such as feedback Transformers. The results indicating slightly better performance on LM tasks with a similar number of parameters and training time look promising. 
 
 
(S3) **Writing.** The paper is well written and the general narrative of the paper is easy to follow. The problem is well-motivated and the experiments/results are well-explained. However, there is some lack of clarity about the details of the model (more on that below). 
 
 
  
### Weakness
  
 

(W1) **Evaluation.** The set of tasks seems quite narrow and it seems like a lot more could have been done to support the efficacy of the proposed approach. The method is evaluated on 2 synthetic tasks and 3 LM tasks. Although the results on those tasks look promising it does not seem to provide a broad picture of the effectiveness of the method. The improvements in LM tasks are also incremental which is not an issue if the method consistently performs competitively across more tasks. I believe a comprehensive analysis across different tasks and across different aspects of the model is important to judge its effectiveness.
 
**[Possible Improvements]**

Tasks. Since the method builds on feedback Transformers I was expecting most tasks explored in that paper to be naturally a part of the experiments here. For instance, copy, reverse, and counting should be easy to implement and experiment with. There are formal language tasks where standard Transformers have also been found to struggle compared to RNNs. If the method can perform well on those while maintaining efficiency it could strengthen the case. On the practical side, long document datasets such as GitHub, arxiv, and PG19 datasets could be explored. Positive results on some of the above-mentioned tasks could significantly help strengthen the case for the proposed method.
 
Model Analysis. The effect of varying parameters such as chunk size and recurrence across depth is unclear. For algorithmic tasks, it could be easier to study the effect of increasing the chunk size. I would guess as the chunk size becomes very large, the model would get closer to standard Transformers and its performance might decrease. Similarly, it could be helpful to highlight if and where recurrence across depth leads to any advantage.
 
(W2) **Novelty.** The contribution in terms of algorithmic novelty is weak in my opinion. Given the previous approaches, it seems like an extension to reduce computational costs. The recurrence across depth seems different but it is not clear if it leads to improvements. In my opinion, it is not necessarily an issue if the method consistently achieves strong performance across several tasks.


Other Comments.
 
(W3) **Method description.** The main method (Staircase attention model) is not very clearly described. It seems to be described in an informal and conceptual manner. Although the method is clear up to a certain degree, I am not confident if I were to reimplement it based on my understanding then it would be the same as the author's version. 
[Suggestion] It would be helpful to the readers if a very detailed description of the model is provided in the appendix. 
 


 
questions: (Q1) Is there any limitation of processing chunks compared to the standard recurrent model? Maybe when the chunk size is large? I do not think there would be any limitation in terms of expressiveness of the model until recurrence is removed but there could be differences in performance as the chunk size grows larger. 
 
 
(Q2) Table 2: Are the recurrent steps in universal transformers and the Staircase model comparable?
 
(Q3) Is there any relation between the proposed model to the Block-recurrent Transformers method [1]? On a high level, there seems to be some similarity in terms of processing blocks of tokens in parallel and recurrently processing blocks.  
 
 
[1] BLOCK-RECURRENT TRANSFORMERS. https://arxiv.org/pdf/2203.07852.pdf
 
 
 
Typos:
 
Line 55
Figure 1: Indentity -> Identity?
limitations: Not clear where limitations are explicitly discussed in the paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper builds upon the Feedback Transformer (Fan et al., 2020) to introduce recurrence into the Transformer architecture. While a regular transformer processes C tokens in parallel, the proposed approach - staircase attention - processes C new tokens at each time step and NC-C tokens from prior time steps. Thus, the transformer core moves ahead in time and resembles a staircase. The output for a given token is generated after N passes. The approach is compute-heavy compared to a regular transformer but uses the same number of parameters. To save computation, the paper proposes a variant that caches states to decrease recurrence while keeping the context size fixed. The paper shows that staircase attention outperforms transformer variants (transformer XL) on state tracking tasks (Random walk and Algorithm) as well as language modeling (Enwik8, Reddit, BASE). The staircase attention obtains a similar performance as the Feedback transformer on the state tracking tasks and improves upon it on some language models tasks (Reddit/BASE). 


strengths_and_weaknesses: Strengths:
* Novel idea to introduce recurrence into a transformer architecture
* Architecture allows a control between amount of recurrence and context size
* Proposes a cached version which controls the amount of recurrence and provides speeds at the cost of performance
* Demonstrates improvements over Feedback transformer in terms of training speed

Weaknesses:
* It would be useful to add results from standard transformer and LSTM for all state-tracking/LM tasks in Table 1. Such a comparison would be useful to all researchers.
* It would be useful to provide some more analysis (see below).
* Given that staircase attention is compute heavy, it would be useful to see a comparison of the inference speed between all models for say one of the tasks (e.g. Reddit). This would enable researchers to understand the trade-off between performance gains vs added compute. 


questions: * Although the cached version of the staircase attention is similar to the feedback transformer, they do not perform similarly on Algorithm and BASE. It would be useful to provide more analysis to understand why this is the case.
* Why does validation error increase when going from 6 to 8 recurrence steps for the 'Algorithm' task?
* Enwik8: "The Cached-Staircase model works better on this dataset, and only 0.1bpc behind the Feedback Transformer despite being much faster to train. ". It'd be good to understand why Cached-Staircase performs better than standard staircase for this task.
* Eqn 2: Please mention that TC stands for 'transformer core' when this acronym is used for the first time.

Typos:
* Figure 1: 'indentity' -> 'identity'
* Sec 2: 'non-recurrent models have superseded in popularity recurrent' -> 'non-recurrent models have superseded recurrent' or 'non-recurrent models have become more popular than recurrent'


limitations: Yes, the authors have addressed limitations. They have not discussed potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduces recurrences into transformers with staircase attention. Most existing transformer models process the entire input sequence through multiple layers. Staircase attention departs from this. It segments the input sequence into multiple chunks. As the model processes the input vertically (i.e., feeding into upper layers), it “slides forward” along the input, receiving a new chunk of input while dropping the oldest one. The neural architecture used to process the input chunks is the same as the transformer. To improve the model’s efficiency and flexibility, a cached variant is proposed, disabling the gradient updates of certain (older) input chunks, thereby reducing the computational cost. The proposed models are evaluated on multiple sequence modeling benchmarks, including variants of language modeling tasks and others. Results show that staircase attention achieves a better tradeoff between modeling sizes (in terms of the number of parameters) and performance and that the recurrence it introduces is crucial in certain tasks.

The paper is interesting and novel to the best of my knowledge, and it is clearly written. Most of the claims are reasonable, except that some important experiment details are missing. This is the reason why my initial review is a bit reserved. I’m happy to revise it if the authors can clarify some details (see below in the question section).

strengths_and_weaknesses: Strengths:
- Staircase attention is interesting and novel to my knowledge.
- The experiments cover a diverse set of sequence modeling tasks, and have a detailed analysis.
- Well-written.

Weaknesses:
- Details on the context sizes need to be clarified (see below)
- The claim on the benefits of recurrences could be better supported (see below).
- Missing discussion of several recent recurrences <-> transformer works [1,2,3,4,5,6].
- Efficiency discussion should be complemented by a discussion on memory overhead, time overhead of the entire training procedure, inference efficiency, etc.

[1] https://arxiv.org/abs/2006.16236
[2] https://arxiv.org/abs/2103.02143
[3] https://arxiv.org/abs/2102.11174
[4] https://arxiv.org/abs/2106.06295
[5] https://aclanthology.org/2021.emnlp-main.602/
[6] https://arxiv.org/abs/2110.02488
questions: - Could the authors clarify the connections to sliding-window attention?
- For the “random walk” and “algorithm” tasks, which representation is fed into the classification layer?
- Have the authors compared to a staircase baseline ablating the recurrences? For example, such a baseline for a “4-layer staircase transformer with N=8” would be, a canonical 32-layer transformer model, but ties the parameters of layers 1–8, 9–16, 17–24, and 25–32. This baseline has more computational overhead, but is important to establish the claims on the benefits of recurrences.  
- In the language modeling experiments, say we have a staircase model with C=1. Is it the case that the model always has the access to N-1 preceding tokens when making a prediction? This relates to the “context size” in [7], and has a substantial impact on transformer language models’ performance. It would be great if the authors can clarify and make sure the models are comparable.

[7] https://arxiv.org/abs/1809.10853
limitations: The paper did not explicitly discuss the limitations or the potential negative societal impact.
review_title: null

Meta-review: metareview: The paper proposes staircase attention to model recurrence with the Transformer architecture. Reviewers are generally on the acceptance side, as they believe the proposed approach is interesting and achieves good empirical performance.
confidence: Certain
Decision: Accept