Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a new attention mechanism that depends only on the relative positions of tokens and is independent of the features themselves. Since the attention coefficient depend only on the relative positions, the resulting attention matrix is Toeplitz. This results in a reduction in the number of parameters and in time complexity of feature updates, since Toeplitz matrices can be applied in O(n log n) time, where n is the sequence length. The authors demonstrate that the proposed method closely matches the performance of conventional attention models, while being faster in terms of training time. 
strength_and_weaknesses: Strengths: 

The proposed idea is very interesting and novel. It is quite surprising to see that attention coefficients that depend on just relative positions perform well. The paper is well-written and the the flow if ideas is great. The provided experimental evidence is sufficient to demonstrate the merit of the proposed ideas. 

Weaknesses:

The paper is quite good as is and does not have many weaknesses. I do have the following suggestions/ questions to the authors:

1. In designing the RPE, the authors claim that learning the weights of Toeplitz matrix performs worse compared to the RPE network. This is a bit unintuitive, since the former should be able to degenerate to the latter. I am surprised to see that learning the weights directly does not perform well. Maybe the authors could shed more light on this. 

2. It would be great to have visualizations of the learnt attention. I am curious to see the kind of associations that are learnt on the datasets considered. Does the model identify semantic relationships in the language? What is the intuition behind using only relative position based attention to capture associations between words?

3. Are there any extensions possible to incorporate multi-headed attention?
clarity,_quality,_novelty_and_reproducibility: Quality: The paper is well-written and is an interesting read. 

Clarity: The paper is clearly written.

Originality: The presented ideas are quite novel. 
summary_of_the_review: The paper presents a very interesting and novel idea. The  proposed ideas are backed up with good experimental evidence. Overall, this paper is quite refreshing to read and I recommend acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces a new way to model the attention mechanism in the transformer architecture for sequence modeling. The proposed approach, while retaining comparable performance compared to other transformer architectures and approaches, improves the efficiency of transformer's capability in sequence modeling in two respects: 1) efficiency of the attention matrix operation (via the Toeplitz matrix formulation); and 2) efficiency of long sequence (which can be longer than the sequence on which the model is being trained) modeling during inference (via a generalized exponential decay bias on the attention scores). 

The experiments demonstrate improved efficiency and performance in particular in long range sequence modeling. In addition, the authors also demonstrate comparable performance of the proposed approach with baselines in various text modeling tasks and an image modeling task, with a table showing the theoretical improved efficiency in the matrix operation.

strength_and_weaknesses: ### strengths 
- The idea of using Toeplitz matrices is interesting and, to my knowledge, new
- Combining Toeplitz matrices and exponential decay bias lead to improved performance and efficiency in long range sequence modeling

### weaknesses
One of the main contributions of the proposed approach, in my opinion, is the improved efficiency without sacrificing performance. However, I wish the experiments can include more evidence to support this contribution.

- My first concern is a lack of clear explanation of the role of Toeplitz matrices and exponential decay bias, respectively, in modeling long sequences (e.g., for the LRA benchmark). It seems to me that, what enables the proposed approach to be able to operate on long sequences is not because of Toeplitz matrices but because of a generalized version of ALiBi. Since ALiBi and the proposed approach have similar performance (according to Table 14, last two columns), an experiment comparing the **efficiency** between ALiBi and the proposed approach would make it very clear that Toeplitz matrices are indeed more efficient for long sequence modeling during inference. 
- Since the performance of the proposed approach is similar in the other experiments, I wish the authors can also include, in addition to the performance metrics, the computational efficiency for the experiments in addition to the LRA experiment. I understand that the authors have a table on the theoretical efficiency improvement; I think some empirical evidence would make this efficiency claim much stronger. For example, Table 2, 3, and 6 do not seem to demonstrate the proposed method's advantage because 1) performance is similar to the baseline(s) and 2) efficiency comparison is missing.  

Some other comments/questions
- Does multi-head attention change any part (e.g., implementation) of the proposed approach?
- Another approach for improving the efficiency of transformers is to leverage sparse/structured matrices (e.g., [1]). It seems that references to this body of work is missing from the paper (or not discussed much). Could the authors comment how their work relates to prior work in speeding up transformers by leveraging sparse/structure matrices?
- What is the unit of the metric being reported in Table 4?
- Why do the authors choose GLU instead of other operators (also: GLU is introduced without defining it)?
- It seems that a citation in third paragraph above Section 2 is not anonymized (in the third line from the last line in that paragraph). But I think it does not matter at this point.

[1] https://openreview.net/pdf?id=Nfl-iXa-y7R
clarity,_quality,_novelty_and_reproducibility: The paper is clearly presented for the most part. Some experiments can include more explanations, perhaps deferring to the appendix due to space constraints in the main text.

I think if the authors include a figure about the key components in classic transformer architecture design and place it side by side with the proposed approach in Figure 2, and highlight the difference and similarities, would help make the proposed approach's uniqueness.
summary_of_the_review: The proposed approach is a very interesting idea of exploiting Toeplitz matrices' structure for improving transformer architecture's computational efficiency. However, I think the empirical evidence does not fully substantiate the efficiency claim: empirical computational efficiency results are missing for all experiments except for LRA. It is also unclear how the proposed approach compares to other works in exploiting matrix sparsity/structure for improving transformer's efficiency. I think this paper has a lot of potential. I'm very open to increase my score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a new token mixing architecture called Toeplitz Neural Networks (TNN). In particular the attention in the popular transformer architecture is replaced with a Gated Toeplitz Unit which is a GLU but before the scalar multiplication the transformed input is multiplied ("mixed") with a toeplitz matrix. The parameters for the matrix are predicted by a neural network in order to make the architecture compatible with any sequence length. The paper shows in various experiments that TNNs work equally well to transformers while being significantly faster both in practice and asymptotically.
strength_and_weaknesses: Strengths
------------

- The idea of the paper is very intuitive and has several precursors like S4s.
- The use of a network to predict the toeplitz matrices based on the sequence index is interesting.
- The results show that TNNs perform equally well to transformers in the example tasks.

Weaknesses
---------------

- The tasks except the LRA benchmark are not particularly large sequence tasks. It would be great to have some experiments for instance on autoregressive image generation or larger scale transformer experiments.
- Similarly to the above, LRA is not a particularly good indicator of real world performance as it can be seen also by the rest of the experiments.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and the idea is simple enough that it can be easily reproduced.
summary_of_the_review: I believe that the paper has sufficient novel contributions and adequate experimental evaluation to make a very good ICLR paper. My only grievances had to do with the evaluation which at the same time is both lacking and thorough. Namely lacking larger and more convincing experiments, but also has enough ablations and experiments with different modalities to be sufficient.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: For modeling long sequences, as an alternative to the attention+softmax based weights that are typically utilized in the transformer models, this paper proposes to use relative position dependent weights that are generated by a ‘relative position encoder’ network, together with an exponential decay bias on the weights.  Due to the use of position encoder network to generate weights the number of parameters in the model is fixed regardless of the length of sequence being modeled.  Also, since relative position dependent weights naturally occur in a Toeplitz structure, the paper proposes to utilize special properties of Toeplitz matrix-vector multiply to achieve computation efficiency.
strength_and_weaknesses: Pros:
* An efficient approach for long range dependency modeling that relies only on relative position dependent weights

Cons:
* The performance of baseline S4 model is substantially lower (AVG. 70.87) as compared to that reported in the S4 paper by Gu et al. (AVG. 80.48).  What is the reason for this discrepancy?
* Paper lacks clarity, especially in describing the proposed model.  For instance:	
	* Define d in Eq. 1
	* What role does W play in Section 3.2?  Does Eq. (4) need a +W term?
	* Section 3.3 states that inputs to the position encoder network are -(n-1) … (n-1).  Does this mean the network has 2n-1 inputs?  Or is it a single positive integer as input?
	* Similarly, section 3.3 states that output of the position encoder network is a d dim vector, but Fig. 2 indicates it is (2n-1) d dim vectors?
	* Is there a separate T matrix for every layer?

clarity,_quality,_novelty_and_reproducibility: Clarity: lacks clarity, especially in stating the proposed model and in the Long Range Arena baseline numbers.
Novelty: somewhat novel for long sequence modeling
Reproducibility: should be reproducible once proposed model is clarified
summary_of_the_review: See pros and cons above.  My main reason for a 'reject' rating is unclarity around the LRA baseline numbers.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: I Summary:

- I.1 Investigated Problem:
The paper investigated the problem of long-sequence modelling. As an alternative to the classical softmax-based attention weights used transformers, this paper proposes to
    - use relative position dependent weights that are generated by a ‘relative position encoder’ network where:
         - sequence modeling is solely based on the relative positional information.
    - an exponential decay bias on the weights in order to have input length extrapolation ability and deal with different sequence lengths. 

- I.2 Proposed Solution:
Since relative position-dependent weights naturally occur in a Toeplitz structure, the proposed solution leverages properties of Toeplitz matrix-vector multiply to achieve computation efficiency.

- I.3 Validity Proof of the Proposed Solution:
Empirical evidence is provided to support the validity of the proposed solution as extensive experiments on:
    - Autoregressive and bidirectional language; 
    - Image modeling,;
    - Long-range Arena Benchmark:
        - Which encompasses modalities such as text, natural, synthetic images, and mathematical expressions requiring similarity, structural, and visual-spatial reasoning, 
show that the proposed method outperforms existing solutions in the literature while being significantly faster.

II Strengths:

- II.1 From a structural (organization) point of view:
As mentioned by one of the reviewers, the paper is well-written and the flow if ideas is easy to follow;

- II.2 From an analytical (development) point of view:
    - Empirical evidence is provided to support the case of the proposed solution is an efficient approach for long-range dependency modeling and is capable to incorporate multi-headed attention. 
    - Visualization of the learned attention has been added to the appendix where it shows that similar behaviour to conventional transformer attention matrices (where the diagonal concentrates the most attention) is observed;
    - It is important to mention that when the proposed solution is used without multi-head attention, it enjoys a lower perplexity (PPL) and faster processing speed. When combined with multi-headed attention, empirical results show that the proposed solution is insensitive to the number of heads used.

-  II.3 From a perspective of soundness (development, unity, and coherence) and completeness (correctness):
    - The strength points mentioned above are sufficient evidence of the soundness and completeness of the paper.

III What can be thought of as weaknesses:

- The proposed solution is clearly presented and does not have many weaknesses. From an analytical point of view, one can point out that large-scale tasks have not been considered (one has to admit that it is not necessarily an obvious task to conduct if we want to be fair and objective). The authors mentioned during the rebuttal that this would be considered in future work.

- Concerns raised by the reviewers have been clarified and detailed questions have been answered in a proper manner with empirical evidence supporting claims and adding value to the proposed solution. We thank the reviewers for their excellent questions and we thank the authors for taking care to respond quickly and meticulously to the questions asked. Unanimously, the reviewers agree on the acceptance of the submission.

IV Potential of the paper: 

- The presented idea is quite novel and has the potential to be of great benefit to the community. It would work can be more impactful if source code is provided.



justification_for_why_not_higher_score: it would be unfair to the authors of the paper to state an arbitrary reason for not attributing a higher score. The paper has significant potential to be impactful. As a meta-reviewer who tries to be fair, objective and intellectually honest, the only reason for which the paper has not been considered for the spotlight or oral is that it has a grade not strictly greater than 7.
justification_for_why_not_lower_score: Honestly, Recommending whether an accepted paper should be attributed to the mention of a poster, spotlight or an oral is very subjective if it does not follow fair and objective rules. A proxy to such desired fairness and objectivity are the reviews and the grades attributed to the paper. The benefits of the proposed solution and emphatic and all reviews were positive with a decent level of confidence (Average grade: 7 Average confidence: 3.75). For this reason, at least a spotlight mention should be attributed to the proposed solution.
Decision: Accept: notable-top-25%