Venue: NeurIPS 2022 Conference

Reviews:

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 presents URPE, a new universal relative position embed for stronger transformer architecture.
Starting from "absolute position embed-based transformers are universal approximators of continuous
sequence-to-sequence functions on a compact domain, authors analyze the approximation power of relative
position embedding in mathematics, and conclude that RPE-based transformers are not universal
approximators. Then authors propose a new relative position embedding with simple but effective
improvement to achieve universal representations. Experiments on both language and graph datasets show
URPE-based transformer’s advantages. Detailed ablation experiments and analyses make the improvements of
URPE reliable.
strengths_and_weaknesses: ### Strengths
1. The motivation and method of this paper are both proven in mathematics.
2. The proposed URPE is easy to implement and can adapt to any RPE-based transformers for further
improvements. It only introduces a few extra parameters to the original RPE.
3. This paper is well written and organized. Motivations, methods, and concerns in experiments are all very
clear and easy to follow.

### Weaknesses
1. Improvements seem to be marginal.
2. Experiments in each table are conducted under a single transformer architecture(e.g., Transformer-Base in
Tab.). It’s interesting to see how many gains URPE can obtain with all kinds of transformer architectures
(e.g., Transformer-Tiny/Small/Large, etc.).
3. Experiments in Vision Transformer. Relative Position Embedding is also widely used in many vision
transformers (e.g., Swin-Transformer). The results of the URPE-based vision transformer are important to prove
URPE’s generalization to other modalities.
questions: See Weaknesses.
limitations: The authors briefly discussed their limitations in L348-350.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper presents an analysis which shows that transformers with relative positional encoding are not universal sequence to sequence function approximators. This is shown rigorously but also intuitively based on the fact that traditional attention will sum to 1 hence given the same inputs the output is always going to be the same. The paper further shows that if an attention function satisfies two conditions then the resulting transformer model is a universal approximator for sequence to sequence functions. Based on this analysis the authors propose a simple and easy to understand modification to the attention function and show experimentally that 1) the resulting transformer can identify absolute positions in the sequence and 2) it improves upon the traditional attention in a variety of real world tasks.
strengths_and_weaknesses: Strengths
------------

- The theoretical assessment of the limitations of RPE is novel, interesting and very simple to follow
- The proposed universal RPE is also interesting and simple to follow
- I particularly enjoyed both synthetic tasks that clearly showcase that RPE cannot calculate the absolute positions of tokens while universal RPE can
- The experimental evaluation showcases that this simple proposed improvement can improve the results in various tasks

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

- There is very little comparison to using both RPE and absolute positional encoding. For instance the synthetic tasks could all be solved using absolute positional encoding and although I understand that the point of these experiments is to showcase the universality of URPE the question remains for other tasks like language modeling for instance.
- Similarly there is little intuition and understanding that can be drawn from the paper regarding the need for absolute positions. For instance, why would absolute positions be needed for language modeling? All things being equal, does it change anything if a certain subdocument is between positions 100-150 vs 50-100? How can we know if the improvement actually comes from the increased expressivity or improved learning dynamics?
- Although the number of parameters is increased only marginally, there is little mention wrt the possible increase in computational and memory cost. Element-wise multiplication is cheap but it does require another activation map the same size as the attention to be kept in the accelerator's memory.
questions: My questions as mentioned in the weaknesses section above are mostly regarding the comparison to combining an absolute positional encoding and traditional RPE or even fixed RPE like ALiBi. Why would this approach be preferred? Have you experimented with adding APE together with RPE in your baselines?

Finally, I would also like to know about possible memory and computational cost increase with URPE. 
limitations: There were no obvious limitations that needed to be addressed.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: In the paper the authors first presented theoretical proof that the Relative Positional Encoding (RPE) based Transformers are not universal function approximators, unlike the originally designed Absolute Positional Encoding (APE) based Transformers are. One primary reason for this is that most RPEs are placed inside the softmax in the attention module. The softmax operator always generates a right stochastic matrix. This restricts the network from capturing positional information in the RPEs and limits its capacity. The paper also conducted synthetic experiments to support this claim empirically. To overcome this limitation, the authors provided two sufficient conditions for RPE-based Transformers to achieve universal function approximation. With this results, the authors proposed a new attention module called Universal RPE-based (URPE) Attention. The transformers with URPE-based Attention, called URPE-based Transformers, are universal function approximators. Finally they presented experimental results to demonstrate the effectiveness of Transformers with the proposed URPE-based Attention.
strengths_and_weaknesses: Strengths:
As the authors noted that RPE-based Transformers generalize better on longer sequences compared to their APE-based counterparts. Transformers with RPE can achieve strong performance in language understanding and language generation tasks. RPEs are also popularly used in other domains to encode translation/rotation-invariant structural signals. Also, RPE makes Transformer easily be extended to other data modalities, such as image and graph, as the relative distance naturally preserves invariant properties for several important transformations like rotation and translation. Hence, there are many advantages of using RPEs and therefore these encodings became increasingly popular. But the authors pointed out one major limitation of RFE-based transformers. Transformers with RPE are not universal function approximators. That is, there exist continuous sequence-to-sequence functions that RPE-based Transformers cannot approximate no matter how deep and wide the neural network is. This paper not only pointed out this limitation, but also proposed Universal RPE-based (URPE) Attention to overcome this drawback. The authors presented theoretical proofs and experimental results to support their claims.
questions: Longformer, Big Bird such models try to solve the sequence length limitation of APE-based transformers from a different angle. Is it possible to provide a comparison of the URPE-based Transformers with these architectures in terms of model size and performance?
limitations: I found the paper well rounded and a good addition to the Transformer literature. A more though comparison can help boost confidence on this 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 shows the Transformer with Relational Positional Encoding (RPE) is not a universal function approximator theoretically and empirically. Thereafter, it presents sufficient conditions to be a universal function approximator and proposes a new method that achieve them, Universal RPE (URPE). It shows that URPE-based Transformers predict the position more accurately than Transformer with RPE and outperform the Transformer with other RPE on a wide range of applications.

============================

Great paper, and they addressed my concern enough. I'd like to sustain my score.
strengths_and_weaknesses: Strengths:
- Even though when $d=1$, why Transformer with RPE is not universal approximator is shown theoretically.
- It presents conditions to be a universal function approximator.
- It proposes URPE. URPE-based Transformer can cover the conditions suggested to be a universal function approximator.
- It evaluates URPE-based Transformers for a variety of tasks and transformer types (e.g., TrXL, Graphormer) and they show better performance than the Transformers without URPE.

Weaknesses:
- I couldn't find the critical weakness even though I tried to find by reading the manuscripts several times with references.

questions: - In Figure 1, it is weird RPE-based Transformers fail to predict the position when the number of tokens is 10. I expected that when the context length is short, RPE and URPE work fine and as the length increases, RPE fails. Could you explain this?

limitations: It proves it's argument (RPE-based Transformer is not a universal function approximator) and validates it's model URPE-based Transformer outperforms RPE-based Transformer for synthetic tasks and language modeling and graph learning. I think they addressed what they must consider so I don't have any concerns about the limitations over that.
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 authors propose present an analysis showing that Transformers with Relative Position Encodings (RPE) are not universal function approximations and provide an alternative formulation, namely URPE, that satisfies the conditions for universal function approximation. The authors further perform a small empirical study showing that the proposed method outperforms baseline RPE both on synthetic tasks as well as real world datasets.
strengths_and_weaknesses: Transformers build the foundation of many modern applications both in the research as well as the industrial community. As such improving the theoretical understanding and underpinning of those popular architecture is of great importance to the research community. 

I appreciate that the analysis is presented in a clear and concise manner which makes it easy for the reader to follow. 

I cannot come up with obvious weaknesses, however with the caveat that I am not very familiar with the underlying theory.
questions: Would it be possible for the authors to visualize the learned relative position embeddings? This tends often tends to be a good indicator to get an impression for what the position embeddings are actually learning.
limitations: As far as I can tell, the authors have not addressed potential limitations, but no limitations are apparent.
review_title: null

Meta-review: metareview: This paper studies relative positive embeddings based Transformers. The authors present a negative result that there exist continuous sequence-to-sequence functions that relative based Transformers cannot approximate (irrespective of the depth and width of the network). The authors then propose a novel attention module, called Universal RPE-based (URPE) Attention which resolves this problem and show superior performance on a wide range of applications. There is a strong consensus amongst the reviewers that the paper is technically-solid, novel, well-motivated and has good practical applications. I agree with the reviewers and recommend acceptance.
confidence: Certain
Decision: Accept