Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new module that reduces the quadratic complexity of standard Transformers. The key idea is to slice the input sequence into various groups and then perform local and global attention respectively. Experimental results indicate that the local-to-global approach can indeed accelerate the processing speed and save memory costs. Also, the proposed model achieves state-of-the-art performance on several popular NLP benchmarks.
strength_and_weaknesses: [ Strength ]
+ The general idea is new. Existing studies on reducing the quadratic complexity focus on either the global or the local pattern, and their combination is seldom explored. The proposed local-to-global method can have benefits from both patterns, i.e., local for higher efficiency and global for higher accuracy. Therefore, the idea is new and technically sound. 
+ Theoretical analysis is solid. The authors give very detailed theoretical analysis on the motivation of the proposed method, which makes the theory solid and rigorous.
+ The performance on several benchmarks is consistently state-of-the-art.

[ Weakness ]
- The main body of the paper is not self-contained. Unfortunately, many important statements and analysis are put into Appendix, e.g., the formulation of CSA at the beginning of Section 4. Without these, readers can hardly understand the content clearly. It is not realistic for all readers to refer to Appendix frequently.
- Some important ablations are not in the main paper. Again, critical ablations such as the speed with respect to the sequence length and the impact of primary hyper-parameters are all put in Appendix, making the paper not self-contained. I strongly advise the authors to re-organize the paper structure and move some important ablations in the experimental section. For example, the two figures in Figure 1 indicate the same meaning, so only retaining one of them could save more space for text. 
- Lack of the comparison to some SOTA linear Transformers, e.g., 
[1] Flowformer: Linearizing Transformers with Conservation Flows
[2] COSFORMER : RETHINKING SOFTMAX IN ATTENTION
clarity,_quality,_novelty_and_reproducibility: The originality of the method is good, but the presentation is a little bit unclear as many important contents are put in Appendix.
summary_of_the_review: I acknowledge the originality and effectiveness of the proposed method, but the paper presentation is not self-contained and should be carefully re-organized.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper the authors propose the Composite Slice Transformer (CST) which consists of a composition of attentions applied to a stacked, slice representation of the input sequence at different scales, coupled with a multi-scale volatile instant positional embedding.

To do this, first the input sequence of length N is divided into N/L slices of size L. Then, local self-attention is performed within each slice of text, to obtain a local context vector for each input token. 
These context vectors also go through a mean-pooling layer (one per slice) to obtain a vector that represents each slice. Then global self-attention is performed using the vectors outputted by the pooling layer. Finally, the final context vector that corresponds to each input token is obtained by summing the local context vector with the global context vector (broadcasted with the broadcast-add operation, to restore the sequence length).

As CST has two attention mechanisms with different granularities, it uses two positional embedding layers, one for the local attention and another for the global attention. These embeddings are only summed to the queries and keys, to prevent the accumulation of the positional information over the layers of the model.

For a fixed slice length L, CST has a complexity of O(NL + N^2/L^2) while the vanilla transformer has a complexity of O(N^2), where N is the input sequence length.

The authors perform experiments in three tasks: Long Range Arena, auto-regressive language modeling, and masked language modeling, and compare the results with a broad set of efficient transformers and the vanilla transformer.

On the Long Range Arena, CST leads to the best average score while being the fastest model and one of the efficient transformers that requires less GPU memory.

On auto-regressive language modeling, experiments on the Wikitext-103 with a sequence length of 256 show gains in perplexity when comparing with the Linear Transformer and the FMMformer while having 1.5x speed-up when compared to the vanilla transformer.
Further experiments, using a sequence length of 1024, show improvements over Reformer, Performer, and Scatterbrain.

On masked language modeling with input sequences of 128 tokens, CST leads to a lower perplexity and better GLUE average score than Nystromformer, Performer, Luna, and FNet.

strength_and_weaknesses: Strengths:
- The model description (besides the extension ratio) is quite clear and well written.
- The proposed way to combine the local and global attention is quite simple and intuitive.
- The authors perform experiments on a wide set of tasks, which show the model’s advantages and wide applicability.

Weaknesses:
- Despite performing experiments on a wide set of tasks, the lengths of the inputs used for auto-regressive and masked language  are always quite small (256 and 1024 for autoregressive LM and 128 for MLM). As the complexity problems of the vanilla transformer are more problematic for long inputs, I do not understand why the authors chose these lengths for the experiments.
- The autoregressive LM experiments are only performed on Wikitext-103. In my opinion the paper would benefit from having experiments on a dataset with more long-range dependencies, such as PG-19 (https://github.com/deepmind/pg19), using a bigger input length. This would allow the reader to understand how good the global attention mechanism is. 
- I also think that it would be interesting to have an experiment in which the computational requirements of CST equal the ones of the vanilla transformer (for example by having longer sequences for CST than for the vanilla transformer)  to understand the gains obtained while having the same computational requirements.
- There is no reference to the S4 model (Efficiently Modeling Long Sequences with Structured State Spaces, Gu et al., CLR 2022), which according to the S4 paper results is far better than the CST on the Long Range Arena tasks.

clarity,_quality,_novelty_and_reproducibility: The paper is quite clear and very well written. The only problem I see is that the extension ratio (\alpha) is only defined in the appendix. You should consider moving it to the main part of the paper because having it in the appendix makes Table 2 and 3 very difficult to understand.

In terms of novelty, the combination of local and global attention is not novel. 
However, the way it is done in this paper is novel (as far as I know) and it seems very simple and intuitive. 

In terms of reproducibility, the model and the hyperparameters are clearly defined so it should be quite easy to reproduce the results. 
However, I did not see any mention of the intention to publicly release the model’s code. This could lead to a lot more usage from the community.

summary_of_the_review: To sum up, I really liked reading this paper and found the model proposed very interesting and widely applicable (as shown by the wide set of experiments in which the model performs well).

However, I found the experiment's setting to be a bit disappointing since the authors only considered small sequence lengths for the language modeling tasks.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed an effecient self-attention block for transformer structure. The proposed block first splits the input sequence into multiple local sequences. Then it first conducts self-attention on the local sequences and then aggregates local sequences and conducts self-attention on the aggregated sequences to achieve global attention. The proposed method is evaluated on multiple datasets and shows better performance than previous efficient transformer.
strength_and_weaknesses: Strength
1. The paper is well written and easy to follow.
2. Although local+global attention has been used in previous works to reduce computational complexity, the author proposed a new form.
3. The proposed method achieves better performance than previous efficient transformer.

Weakness
1. The proposed CSA is similar to previous axial attention [1,2], where they conduct self-attention sequentially along one dimension and then another. The difference may be that the proposed method also used attention abstraction and multi-scale position embedding. It would be better if the author could give some more detailed discussions about the difference from previous works.
2. I am not sure I understand the multi-scale position embedding. First, I am not sure why it is called multi-scale, is it just because the length of local and global sequences are different? Second, how is this different from previous relative positional embedding? And there should be an ablation study to show its effect.
clarity,_quality,_novelty_and_reproducibility: The paper is clear and easy to follow. The quality of the paper is good but I am not sure how much novelty in the proposed method as explained in the weakness part. There are details on how to reproduce the results.
summary_of_the_review: I think the paper is well written and the proposed method has some new technical contributions. But I am not sure how significant these contributions are and I would like to see the response from the author.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a hierarchical attention mechanism to model sequence data efficiently. Several experiments have been conducted to demonstrate the effectiveness of the proposed method.
strength_and_weaknesses: Strength:
* The authors focus on an important problem in sequence modeling
* The paper is organized well and easy to follow
* The technical details are presented well

Weakness:
* The novelty needs to be better justified
* More ablation study may benefit understanding the proposed method


clarity,_quality,_novelty_and_reproducibility: Overall the results look promising and the technical details are sufficient. I suggest the authors to better justify the novelty of the proposed method.
summary_of_the_review: My major concern is on the novelty of the proposed method. It would be better if the authors can further justify how the proposed model is different from MSMRA-based methods, and why the contribution is considered not incremental.

It would be also better if the authors can explore how more slice length choices may affect model performance from the ablation study. The authors use L=8/16 in LRA benchmark and 32/64 in the MLM/NLU transfer learning evaluation, it would be great if the authors can justify why selecting different slice lengths and how this may affect performance here.

Some technical terms also need to be better presented, e.g., the extension rate is not well introduced in the main paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a new local-global attention mechanism (composite-slice attention) to overcome the quadratic complexity of standard transformers. The key idea is to slice the input sequence into various groups and then perform local and global attention respectively. Experimental results indicate that the local-to-global approach can indeed accelerate the processing speed and save memory costs, achieving good performance on several popular NLP benchmarks. Overall, there was some disagreement among reviewers about this paper, with most reviewers feeling overall positive. The authors seem to have addressed most of the reviewers' concerns in their rebuttal, adding experiments in a more challenging dataset which benefits more from long context (PG-19) to the revised version of their paper. Therefore I am recommending acceptance.
justification_for_why_not_higher_score: Novelty is a bit limited in my opinion for this paper to deserve a spotlight or oral presentation. 
justification_for_why_not_lower_score: The paper still provides valuable contributions and I would like to see it accepted.
Decision: Accept: poster