Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes new variants of relative positional encoding (PE) that are applicable for linear transformers - relative PE with unitary transformation (URPE). The proposed URPE variants preserve a linear time-space complexity, and demonstrates a comparable performance against the standard/vanilla transformer, across tasks such as LM and MT.   
strength_and_weaknesses: Strengths 
- Unlike recurrent networks, transformers are dependent on the PE for learning the sequential arrangement of the input representation. In the past, literature relied either on an absolute, learned/relative PE's. As an integral part of transformer, this work, provides a principled approach to simplify PE for linear computation.
- In addition to a comparable result in a LM and MT tasks, the proposed URPE approaches preserves a linear (O(n)) compute complexity, with a relatively minor (9%) training speed delay.

Weaknesses
-  Despite the results for tasks the LM, MT, and text classification, the experimental setting is quite narrow. Given the depth of formalization of both the vanilla, linearized and the proposed URPE approaches, this work, can be benefited from more tasks and broad experimental settings. For instance, summarization, given longer sequence length input and document level MT can be a good starting point to further probe the complexity vs quality metrics. 
- Despite 8 variants of URPE (Table 1), this work, lacks a detailed comparison and analysis of each variants. Only performance difference for LM and MT tasks are provided.
clarity,_quality,_novelty_and_reproducibility: Clarity 
- this work, is well written, can be easily understood for readers with strong background in the formalization of vanilla transformer, linear transformers. 

Quality
- the work is well organized, starting from a motivation for why a new variant of URPE, relation with linear transformation, and formalization and experimental sections.

Novelty 
- achieving a complexity of O(n) for PE, this work, adds a novel contribution to linear transformers. Moreover, the approach is flexible enough to be applied in the standard transformer.  

Reproducibility 
- requires multiple pass to understand the theoretical background 
- the provided pseudo-code of the URPE can be utilized to replicate the approach.
summary_of_the_review: This work, proposes a new variant of relative positional encoding, that can achieve a complexity of O(n). The proposed approach can be applied both for linear and the vanilla transformers. The proposed approach, with a detailed theoretical background, shows comparable result with strong baseline and related work. Although, the presented result can be benefit from additional tasks such as summarization.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Positional embedding is an important component of transformer to give position information and also provide better generalization and usage of longer context. Recently several papers attempted to resolve the problem of generalization to longer sequences as well as better designing relative positional embedding. The main issue was applicability to popular optimized linear attention as relative positional embedding is modifying attention and was not applicable. RoFormer was the first to formulate properly the problem with unitary transformation (by rotating on some angle) and propose multiplicative embedding to be applicable to linear attention. This paper continue this generalization: it formulates general property we need for linear attention from positional embedding and obtains generalization of RoFormer with unitary transformation and additional projection matrix. With that many relative positional embeddings can be reformulated in the proposed unification, many new designs are further proposed in the paper with different unitary and projection matrices. All of them are tested for language modeling, machine translation and downstream NLP tasks. In many cases different proposed embeddings improve results over the baselines and previously proposed relative positional embeddings.
strength_and_weaknesses: **Strength**
- general formulation of relative positional embedding for linear attention which can be used now for both linear and vanilla transformers (many proposed embedding can be rewritten in terms of the proposed general formulation)
- nice simple math & extension of RoFormer
- experiments with many variations of proposed general relative positional embedding for language models, machine translation and downstream NLP tasks.

**Weaknesses** 
- Paper can be simplified to have only LRPE definition and inheriting the proper form with assumption $W_0=I_d$
- Ablation on usage $P$ as identity to understand the effect of the extra linear transformation on top of the rotational operation. Why do we need $P$ matrix at all as in examples it is still unitary / orthogonal, why this decomposition into $P$ and $\Lambda$ is helpful? There is one ablation in Table 5, but would be great to have more and see consistent picture here. Any analysis on understanding why we need $P$ would be very useful. What will happen if we learn this matrix for baselines too? 
- Results in Table 3 for vanilla transformer are not convincing. Seems we even don't need any relative information to perform the best.
- Machine Translation experiments are weak. It is known that test and validation for WMT-14 En-De are not very well correlated, probably due to small data size. Here all results should be reported with statistical significance, otherwise it is too huge variation could be. I would suggest to redo experiments either with several seeds or for En-Fr which is larger and stable results are observed there. Improvements 0.05 authors reports here is out of statistical significance, so it should be ignored for now.
- I think overall experimental outcomes shows that there is huge variability between embeddings and moreover there is no one formulation which behaves consistently better in all experiments over the baselines. In this case I am not sure how general formulation can be helpful from practical point. Yes, theoretical formulation and math behind is very cool, but it could be the case that it is not practical in the end and does not bring too much improvement (some negative result that original baselines are good enough). Maybe more broader experiments in other domains, like vision and speech could help to resolve this issue, but it is future work obviously.
clarity,_quality,_novelty_and_reproducibility: **Clarity**
The paper is very well written, however several parts can be simplified (see below my comments)

**Quality**
Overall setup of experiments, math and ablations looks strong. The issue mainly with results which I specified above and below. At least better justification is needed for machine translation.

**Novelty**
The work is definitely new and provide extension on top of many embedding by unification of their formulation. Also it heavily extends RoFormer mainly adding additional projection matrix and different variations of orthogonal transformations.

**Reproducibility**
Details are extensively given in the paper with fairseq code link and hyperparameters in the Appendix.

**Major comments and suggestions to improve the paper**
- introduction: mentioning about RoFormer - first it is multiplicative embedding which is very different from a huge amount of embeddings we used before (it was only additive) and also it is general enough formulation, not just individual work I think. I think more careful formulation should be done in the text about RoFormer.
- Sec 2 background on the relative positional embedding. I think authors should mention that in the end relative positional embedding is not so efficient: it gives extra computational cost and memory, which slow down training (e.g. in LM/MT domains people mostly use only absolute positional embedding anyway, in speech it is observed 2-3x slow down, see [3]). Also there is generalization issue with relative positions still, see [3]. As a solution people developed things like [1-4] in the past year. Also what do authors mean by "more flexible"? In that sense sinusoidal pos. embedding is good, it is applicable to any position. Also worth to clearly mention that a lot of works tried to modify attention mechanism directly to introduce positional embedding which is not generalizable to linear transformers.
- Eq 6 - introduce $m$ here, otherwise not clear what is it.
- Eq 7 seems wrong to me as dot product is a value while $W_{t-s}$ is a matrix if compare Eq 7 and 8.
- I think RoFormer is the closest work to the current paper in the sense of unitary operator formulation and multiplicative nature of embedding. That is why I prefer to see more detailed discussion of RoFormer and formulation in 3.1.1 RoFormer in terms of the proposed framework, showing what is the main difference and last step (e.g. additional projection matrix on top of rotational matrix) RoFormer did not do and why more general formulation performs better in experiments.
- Sec 3.1.2 - usage of tilda could be reduced, just use notation of hat.
- Definition 3.1 Why we assume that matrices $M_t$ and $M_s$ the same? We could say that $W_{t-s}$ should decompose into $M_t M'_s$ - more general formulation.
- Be consistent on usage words encoding <-> embedding
- LRPE and URPE, its equivalence and Proof of Theorem 3.3 can be simplified and text could be squeezed. It is in the end a bit trivial. I have several suggestion how to improve this. First do not introduce both LRPE and URPE, but just LRPE and then with several rows only show that this leads to $W_{t-s}$ being unitary and equal to $W_t W_s$. To show this add after definition 3.1:
  - $W_0=I_d = M_s^H M_s$ -> $M_s$ is unitary. $W$ is decomposed as product of unitary matrices, thus W is also unitary (as unitary matrices is a group, or check by definition). 
  - Then for $s=0$ we have $W_t=M_0^H M_t$ and then multiply by identity which is equal to $M_0^H M_0$ and get $W_{t-s}=M_s^H M_t=M_s^H (M_0 M_0^H) M_t= (M_0^H M_s)^H (M_0^H M_t) = W_s^H W_t$.
  - Appendix C3 can be removed then entirely. Also theorem C1 and C2 are about Jordan form for unitary matrices, so this can be simplified as reference.
  - Right now it is very confusing and hard to read. With above simplification it should be very obvious what is happening and no need for two definition. We just want to have some decomposition, and from it and our reasonable assumption on $W_0=I_d$ we get particular form on matrices and unitary property.
- Sec 3.3.2, please add what is $P$ matrix: projection, arbitrary? later it is clear, but better to introduce right away. 
- From section 3.3.2 it is clear that mostly new formulation adds only some linear transformation on top of the rotational matrix. I think it is in line with work Li, Y., Si, S., Li, G., Hsieh, C.J. and Bengio, S., 2021. Learnable fourier features for multi-dimensional spatial positional encoding. Advances in Neural Information Processing Systems, 34, pp.15816-15829. where it was shown that additional transformation on top of the positional embedding is very helpful. I think it is worth to quantify this difference in the paper and perform ablation where matrix $P$ is selected as identity.
- Table 2: what about Transfromer-XL baseline?
- Could author give more info on why having relative positional embedding in the decoder for linear attention doesn't allow models to converge? is it true also for the baselines or only for proposed rel.pos.?
- Table 4: please mark with bolt only valid performance, as we select best based on valid and then look at the test. It is misleading just mark with bolt test on its own. Then we clearly will see that for linear attention all proposed rel.pos. actually worse than the baseline and for vanilla one almost same story (there is huge variation on test for two embeddings performing same on valid, 1BLEU difference, so more seeds or experiments are needed here).
- Eq 23 Appendix - values are forgotten in the formula
- could authors confirm that for all experiments the same model is used and only positional embedding is varied? Maybe it is worth to clearly state in the text (maybe I missed this).

**Missing citations:**
- [1] KERPLE: Kernelized Relative Positional Embedding for Length Extrapolation https://arxiv.org/abs/2205.09921 NeurIPS 2022
- [2] (AliBi) Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations, 2022.
- [3] (CAPE) Likhomanenko, T., Xu, Q., Synnaeve, G., Collobert, R. and Rogozhnikov, A., 2021. CAPE: Encoding relative positions with continuous augmented positional embeddings. Advances in Neural Information Processing Systems, 34, pp.16079-16092.
- [4] (SHAPE) Kiyono, S., Kobayashi, S., Suzuki, J. and Inui, K., 2021, November. SHAPE: Shifted Absolute Position Embedding for Transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing (pp. 3309-3321).
- [5] Dai, Z., Yang, Z., Yang, Y., Carbonell, J.G., Le, Q. and Salakhutdinov, R., 2019, July. Transformer-XL: Attentive Language Models beyond a Fixed-Length Context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (pp. 2978-2988).


summary_of_the_review: The paper proposes general formulation of relative positional embedding which is applicable to linear and vanilla transformer due to multiplicative nature. I like a lot math extension and general formulation of RoFormer with unitary operators which is done in the paper. Finally we have very fundamental (and correct from math point) definition of relative positional embedding (done with RoFormer too, but it is extended further). The paper gives overview of many embeddings which can be formulated in terms of the proposed definition. Authors study different variations of matrices which are used in the decomposition of the general relative positional embedding. However, from experiments on language modeling, machine translation and downstream performance on NPL tasks we can see that there is no one positional embedding from proposed formulation which performs the best among others in all tasks. Also there are weak experiments and justification in machine translation domain and NLP downstream tasks. Moreover I think the main key point of having some projection matrix is not studied well and its effect is not understood.

**Update** After rebuttal and discussion: With additional experiments and ablations authors made the paper stronger on both technical and empirical sides. I change correctness evaluation from 2 to 4. I support acceptance of the paper, but keeping score of 6 as empirical results are not showing consistent improvement for one proposed embedding and there is no score of 7 :) . In this light I suggest to rephrase a bit the text to make it clear that the focus of the paper is the general framework itself and the theory under it, not one new embedding in particular to perform the best. Also I encourage authors to include all results from rebuttal period, including vision domain with ViT.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper focuses on the problem of designing relative positional encoding schemes that are compatible with linear transformer architectures. This problem attracted some research already, and the main idea of the paper is to express the problem in a general way, by putting some emphasis on the fact that linear complexity requires considering the relative weighting through its SVD. Doing so, they derive some variants, based on how they design the matrices involved. Performance is on par with other existing schemes, and a bit better sometimes.
strength_and_weaknesses: The paper provides a good overview (although a bit biased, since I believe that several previous works already highlighted the SVD thing). The proposed method makes sense, and I didn't check the implementation, but it is claimed that it will be made open.
Then, experiments are fine, although I believe that:
*  it would have been interesting to try everything with "no positional encoding". I indeed found out that it is quite common that PE is useless altogether for some tasks. 
* It is likely in my opinion that the other methods would probably have given better results if tuned. But it's ok I guess that using the default parameters for their implementations is fine.

The main weakness I can see is novelty. I am really not convinced that factorizing the relative weights through SVD and then designing some particular cases is so new. It is claimed that this method subsumes most state of the art (indeed it's the case, necessarily), but it would have been good to highlight in what sense. For instance, "the method from [xxx] is equivalent to picking P as ... and \Lambda as ...". Another weakness is that computing time / memory usage is not reported very well.
clarity,_quality,_novelty_and_reproducibility: The paper is clear enough, and the quality is good. My main concern is novelty, as I wrote. I think it is fair though, because the paper *does* bring yet another highlight on the topic. Still, my point is that maybe this is not sufficient for such a selective conference as ICLR, justifying my score.
summary_of_the_review: another paper on relative positional encoding with linear complexity, whose highlight is on the factorization of the relative attention weight through SVD. The paper provides good background, although could be a bit more objective since I believe that the proposed method it is almost equivalent to several other previously proposed ones,.
All in all, a good paper on a topic I'm interested in, with borderline+ contribution, but still a nice read.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposed to unify relative positional encoding methods by formulating them as a quadratic form and introduced a class of decomposable relative positional encoding that is equipable by linear attention.
strength_and_weaknesses: Strength:
- The unified form of relative positional encoding is meaningful in the sense that this formulation makes things clear and helps to design new relative positional encoding schemes.
- The examples in this paper provide a diverse view of how to design relative positional encoding and decomposable relative positional encodings.
Weakness:
- Though the paper is motivated by designing relative positional encoding for linear attention, the empirical performance on linear attention is rather weak. Meanwhile, the paper claims that the problem of adding relative positional encoding to linear attention is under-studied, which is not true even though the paper has cited some of the related work. Concretely, there exist several works studying this problem, including [1, 2, 3] where [2] has significantly better performance than the proposed method (e.g., GLUE). Also to study linear attention, it is important to report the running time, it would be great to add discussion on this (though I understand the additional overhead is small for the method proposed in this paper)
- Some of the numbers of the baseline methods is too low. For, example, it is easy to reach 80+ on MNLI, 30- on Wikitext-103.

[1] Relative Positional Encoding for Transformers with Linear Complexity
[2] Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding
[3] PermuteFormer: Efficient Relative Position Encoding for Long Sequences
clarity,_quality,_novelty_and_reproducibility: The paper is clear though the significance of the performance and the novelty remain unclear.
summary_of_the_review: In summary, I think the unified view of relative positional encoding is interesting, but the results in the paper are not strong enough. Also, the baselines and reviews in the paper are not comprehensive enough.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Various concerns have raised during the reviewing process, including the novelty, weak experimental performance and limited evaluation tasks. The authors have not fully addressed these concerns.

Also, even during rebuttal, results on additional tasks are reported, considering the motivation of the work, the proposed approach should be tested on NLP tasks with long inputs. e.g., various datasets proposed on long narrative stories such as books and movie scripts.
justification_for_why_not_higher_score: Various concerns have raised during the reviewing process, including the novelty, weak experimental performance and limited evaluation tasks. The authors have not fully addressed these concerns.

Also, even during rebuttal, results on additional tasks are reported, considering the motivation of the work, the proposed approach should be tested on NLP tasks with long inputs. e.g., various datasets proposed on long narrative stories such as books and movie scripts.
Decision: Reject