Your Transformer May Not be as Powerful as You Expect
Authors: Shengjie Luo
Shanda Li
Shuxin Zheng
Tie-Yan Liu
Liwei Wang
Di He
Venue: NeurIPS 2022 Accept (2022)
Keywords: Transformer
Positional Encoding
Expressive Power

Abstract: Relative Positional Encoding (RPE), which encodes the relative distance between any pair of tokens, is one of the most successful modifications to the original Transformer. As far as we know, theoretical understanding of the RPE-based Transformers is largely unexplored. In this work, we mathematically analyze the power of RPE-based Transformers regarding whether the model is capable of approximating any continuous sequence-to-sequence functions. One may naturally assume the answer is in the affirmative---RPE-based Transformers are universal function approximators. However, we present a negative result by showing there exist continuous sequence-to-sequence functions that RPE-based Transformers cannot approximate no matter how deep and wide the neural network is. One key reason lies in that most RPEs are placed in the softmax attention that always generates a right stochastic matrix. This restricts the network from capturing positional information in the RPEs and limits its capacity. To overcome the problem and make the model more powerful, we first present sufficient conditions for RPE-based Transformers to achieve universal function approximation. With the theoretical guidance, we develop a novel attention module, called Universal RPE-based (URPE) Attention, which satisfies the conditions. Therefore, the corresponding URPE-based Transformers become universal function approximators. Extensive experiments covering typical architectures and tasks demonstrate that our model is parameter-efficient and can achieve superior performance to strong baselines in a wide range of applications. The code will be made publicly available at https://github.com/lsj2408/URPE.

Your Transformer May Not be as Powerful as You Expect
Shengjie Luol.s, Shanda Lif*, Shuxin Zheng', Tie-Yan Liu Liwei Wang Di Helt
NNatioaal Key Laboratory of General Artificial Intelligence.
School of Intelligence Science and Technology. Peking University
Machine Learning Department, School of Computer Science, Carnegie Mellon University Microsoft Research *Center for Data Science, Peking University 3Zhejiang Lab luoejBatu, pareutu.pu.... enu en, shandal@cs. cmu edu, (shuz, tyliu))microsoft. com, (wanglw, dihe &pku. @pku..du..e.
Abstract
Relative Positional Encoding (RPE), which encodes the relative distance between any pair of tokens, one of the most successful modifications to the original Transformer. As far as we know, theoretical understanding of the RPE-based Transformers is largely unexplored. power of RPE-based Transformers regarding whether the model is capable of approximating any continuous sequence-to-seqqeenee functions. One may naturally assume the answer is in the Settrnatvve-RE--aasseee Transformers are universal function approximators. However, we present a negative result by showing there exist continuous sequence- ceruuence-t-seqqeeee -equeenecce functions that aPE-based Transformers cannot approximate no matter how deep and wide the neural network is. One key reason lies in that most RPEs are placed in the softmax attention that always generates a right stochastic matrix. This restricts the network from capturing positional information in the RPEs and limits its capacity. To overcome the prob- lem and make the model more powerful, we first present sufficient conditions for RPE-based Transformers to achieve universal function approximation. With the theoretical guidance, we develop a novel attention module, called Universal RPE-based (URPE) Attention, which satisfies the conditions. Therefore, the cor- responding URPE-based Transformers become universal function approximators. Extensive experiments covering typical architectures and tasks demonstrate that our model is purameter-efficient and can achieve superior performance to strong baselines wide range of applications. The code will be made publicly available at https::/// // thub. com/ls 2408/URPE.
this work, we mathematically analyze the
Introduction
Transformer [61] is well acknowledged as powerful neural network in modeling sequential data [12, 42]. Relative Positional Encoding (RPE) is one of the most successful modifications the Transformer model [49]. Unlike the originally designed Absolute Positional Encoding (APE) that encodes each position as an embedding vector, RPE encodes the relative distance between any pair of tokens and is usually placed in the softmax exponentiation in the self-attention module. Empirically, many studies show that RPE-based Transformers can achieve impressive performance on various language tasks [54, 10] and have better extrapolation ability longer sequences [52]. Another point worth noting is that RPE makes Transformer easily be extended to other data modalities,
"qqual contribution. The order is decided by rolling the dice. t "Coreeponnence to: Di He<dihe@pku. edu. en>, Liwei Wang <wanglw@pku. edu.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

such as image [14, 43] and graph [67]. as the relative distance naturally preserves invariant properties for several important transformations like rotation and translation.
In this paper, we first investigate the theoretical aspect of the RPE-based Transformers. In particular, we study their expressive power which describes models' ability to approximate any continuous func- tions. Recently Yun et al. [69] proved that the APE-based Transformers are universal approximators of continuous
functions on a compact domain, and one may expect that the RPE-based Transformers enjoy the same property. However, we provide a surprising theoretical find- ing which shows that widely-used Transformers with RPE are not universal function approximators, ie., there exist continuous sequence- requence-to-sequeees seuueeue functions that the models cannot approximate no matter how deep and wide the model is. One key observation that the RPEs are placed inside the softmax in the attention module. The softmax operator always generates right stochastic matrix, which fails to reflect enough positional information encoded in RPE to the output. Synthetic tasks are conducted to support this mathematical claim.
To design more powerful RPE-based Transformer, we delve into the limitation of the model and theoretically derive two sufficient conditions to achieve universal function approximation: the attentive condition and position-aware condition. Both conditions together state that the RPE-based attention function class should cover some special cases of the originally designed attention and break the right-stochastic-male attention module called Universal RPE-based (URPE) Attention that satisfies the above conditions. Therefore, the Transformers with URPE-based Attention, called URPE-based Transformers, are universal function approximators. We show our proposed architecture is easy to implement and parameter-efficiet extensive experiments covering typical model architectures [54, 10, 67] and tasks (synthetic tasks, language modeling, and graph learning). Our model brings consistent performance gains compared with existing RPE-based Transformers on a wide range of tasks.
limitation. With such theoretical guidance, we develop a new
The paper is organized as follows. In Section 2, we introduce background on the Transformer archi- tecture and positional encoding approaches. In Section 3, we prove that the widely-used RPE-based Transformers are not universal function approximators. In Section 4, we further present sufficient conditions for RPE-based Transformers to achieve universal approximation, and develop a new attention module. URPE-based Attention, to build a universal RPE-based Transformer. Experiments are presented in Section 5 to demonstrate the effectiveness of Transformers with our proposed URPE-based Attention. Related works and the conclusion are discussed in the last two sections.
2 Preliminary
The Transformer architecture is composed of stacked Transformer blocks [61, 12]. A Transformer block is a grquence-to-sequenee mapping from Rxd Rxd, where n is the sequence length and d is the dimension of token embedding. A Transformer block consists of two layers: self-attention layer followed by feed-forward layer, with both layers having normalization (e.g., LayerNorm [1], RMSNorm [71] and skip connections. For an input X E Raxd, the self-attention layer and feed-forward layer are defined as follows:
(x) = softmax (XW)) (XW)
(1)
Attn(X) X ("
(2)
h=1 FFN(X) X ReLU
where Wh E Rduxdd Wh. W/ W E Rdxdv, W1 Rxr W2 E Rexd H is the number of attention heads, dy is the dimension of each head, and r is the dimension of the hidden layer. A^ usually referred to the attention matrix. Given pre-defined H, du and r, we refer to the function class of the Transformer blocks as T blolocks( H, dh.r).
Transformer with Absolute Positional Encoding. Self-attention layers and feed-forward layers defined in (2) and (3) are entirely invariant to sequence order. Therefore, purely stacked Trans- former blocks cannot distinguish information at different positions. The original Transformer [61] proposes Absolute Positional Encoding (APE) endow Transformer networks with the ability to

---

capture positional information. In particular. a (learnblee) real-valued embedding e E IR is assigned each position i, leading to an Absolute Positional Encoding matrix E [e..... Gn I which will
be added to the input sequence. Formally speaking, the function class represented by APE-based Transformers
(d APE
(f(x) = g(x + E g 9L 91:: T_bllock(HH. du r); EN).
APE essentially enhances the expressive power of Transformers. Yun et al. [69] proved the following theoretical result, which shows that APE-based Transformers can approximate any continuous sequence-to-sequence function in a compact domain.
Theorem (informal [69]). Given n. d E N", the function class of Traansformers with APE, D is universal approximator for continuous functions that map a compact domain in Rnxd to R Rexd
Though Transformers with APE are conceptionally simple and enjoy good theoretical properties, they have few known shortcomings. For example, Press et al. [52] showed that APE-based Transformers usually generalize poorly to longer sequences, as those positional embeddings for large indexes are hardly trained. Many works [58, 10, 54, 33, 26] employ Relative Positional Encoding (RPE), which becomes increasingly popular as a powerful way to encode positional information for Transformers and largely overcomes the disadvantages of APE.
Transformer with Relative Positional Encoding. Different from APE that assigns an embedding for each position Relative Positional Encoding (RPE) encodes relative distance i - - for each position pair (i. With the relative positional encoding, most previous works modified the attention computation defined in Eq.(I) as follows:
4 A X) softmax ( X + BB.
where an n X n matrix. The (i, j-th entry of B, denoted by bij. models the interaction between the i-th and j-th position. Different parameterizations of B lead to different model architectures. A few well-known examples include:
Shaw's RPE [58]: bij = X.W where rı-j are learnable vectors.
T5 [54]: byj mi-jj where mi-j are learnable scalars, i.e., B is parameterized Toeplitz matrix [22, 45].
DeBERTa [25]: bij X.W.rr.... 8 S W.) where rı-5 and 8;-j are learnable
vectors.
Transformer-XL. [10]: bij- = x, W + u X + v(r W )T, where
u, and W are all learnable vectors/matrix, and rı-j are sinusoidal positional encoding vectors fixed during training.
Several interesting phenomena suggest that RPE-based Transformers have many advantages compared to their APE-based counterparts. Press et al. [52] demonstrated that RPE-based Transformers generalize better on longer sequences. T5 [54] and Transformer-X. [10] show that Transformers with RPE can achieve strong performance in language understanding and language generation tasks. Recently, RPEs are also popularly used in other domains to encode translation/roiationnnnnaa invvaraaatt structural signals. Typical examples include Swin Transformer [43] and Graphormer [67], both of
which use RPE and achieve kate-of-the-ar performance image and graph representation learning.
Transformers with RPE are not Universal Approximators
We interested in the expressive power of Transformers with RPE and investigate whether this architecture is as powerful as the original APE-based Transformers. To make comparison, we similarly define the function class of the Transformer blocks with RPE-based attention (Fq.(4)) as T_blocksgpEl H, du, r), in which the relative positional encoding matrix B assumed to be an matrix. The function class represented
arbitrary parameterized mapping from the input X to by Transformers with RPE is defined as:
n H.dg. r [6L 01 na + gaxd ... ,L
ΩRPE
IL E T (_blockkspE(HH r),r), N*).
3

---

Proof. Without loss of generality, prove the theorem for d 1. The proof can be easily extended to > settings. Given M > O, we consider a specific sequencceto-sequemee function target: 9M X - (2M,0,... O0 To show sepxED 1l (X) - (X))l > M holds for any g D we pick up an input X", which is composed of n identical row vectors in IR,, i.e., the sequence consists of n identical tokens. Since the function AfrE (X) outputs a right stochastic matrix, it is easy to check that Attn(X] identical row vectors in Rd. Note that FFN(X) and normalizations operate identically each row vector, we can obtain that the final output of Transformer block with RPF-based attention still Surprisingly, we present negative theoretical result: we prove that the function class of Transformers with RPE, RPE
f..d.rr is not universal approximator for peuuence-t--equeene functions.
Theorem 2. Given n > 2, d and D _ Rndd assume that the all-zero matrix O E DD For any M > 0,
there exists continuous function 9M D BF sscch that
10M (X) - g(X)l M XED
sup
(5)
holds for any g E S2 SRRE
o., where H, M,
X x Σ ( XXXW)) W is also composed of n
composed of n. identical row vectors in Rd.
Since g is a composition of multiple Transformer blocks in T b_blocksRPE (H, dæ, r) and is com- posed of identical row vectors in Rá, we conclude from the analysis above that g is also composed of identical row vectors in Rd, i.e., there exists e E Rd such that g(0) cl Therefore, by applying Cauchy-Schward Inequality we obtain
4M
ll (0) - -(0]
M
sup XED
ll (X) x(X)llr > M,
1+ n-1
which completes the proof.
Discussions. The key observation in Theorem is that ARPE(X) (X) always outputs a right stochastic matrix. Even if RPE carries rich positional information, such signal will be suppressed to satisfy ARPE(X)1 = for arbitrary X E =gd where 1 is an all-one n-dimensional vector. As a result, the attention module fails to reflect enough positional information encoded in RPE to the output, which restricts the model capacity. The problem will be significant when the target function ğ is very Dusition-sensitvve (in the extreme case, only depends on the position indexes). We also conduct experiments on simple srguence-to-sequeee claim in Section 5. One may expect that simply removing the denominator in the softmax can break the limitation. However, this modification brings significant optimization instability in practice. Given that RPE has many advantages compared to APE, it's appealing to design RPE-based Transformer variant that is a universal approximator of sequence-to-sequenee functions and easy to optimize. This is what we precisely work on in the next section.
tasks using synthetic data to support this mathematical
4 Making RPE-based Transformers Universal Approximators
This section contains two sub-sections. In the first sub-section, we provide a sufficient condition for the RPE-bbased Transformers to achieve universal approximation. In the second sub-section, we offer practical instantiation of the Transformer with RPE that satisfies the requirement and is parameter-efficien.
'On one hand, we claim that RPE-based Transformers cannot achieve universal function approximation (while APE-based models can achieve). On the other hand, we claim RPE is empirically advantageous compared APE, according to previous works. One may feel there exists contradiction and get confused. We would like to clarify that the two claims are made different settings. For example, RPE empirically performs well in generalization to longer sequences, while the theoretical analysis of approximation capability focuses on functions with bounded input lengths (See Theorem where is given). Our goal is to design an RPE variant with the same expressiveness APE in the theoretical setting and enjoys its usefulness in practical scenarios.

---

4.1 A Sufficient Condition to Achieve Universal Approximation
Motivated by formulation (1) and (4), we consider general form A RRad - Rax= and define the corresponding attention layer as
H
(tt (x)= = Σ
A((X)XX)
(6)
h=1
We further define the function class of the corresponding Transformer block T T_bloccsu((H, dn, r), and define the function class of Transformers composed of stacked T_blocksu dir, as:
S H. H.d [gr. ogr. og Raad Rnxd ".,-.", gr. T T_bloccsu dn, r), (7)
Our goal is to investigate the requirements on A under which the induced function class D can become universal approximators of continuous sequence-to-sequence functions. We provide one sufficient condition in the following theorem. Following Yun et al. [69] and many other previous theoretical works [44, 24, 70], we study the expressiveness of simplified version of Transformer in which normalization layers are omitted, as it is widely believed that normalization mainly helps optimization but does not hurt the expressive power of the network [32, l].
Theorem 3. Given d E Nº, [1, +00), sequence-to-sequeeeee -osuuenece function f D Rn Assume that Ale satisfies the following conditions:
O, compact set D S guxd, and continuous
Attentive condition. For any E Rdx1 and e E R. there exists parametrization of A such that ( softmax (Xu(Xu- - -c
Position-aware condition. There exists a parametrization of A and vector E Th. whose entries are all distinct, such that A (x)1=0) for any E Bundd
Then there exists a Transformer network g E Dg. such that (ollf()) ((((X)))((X(((() g(Xi < E, where || Ilp denotes the entry-wise E norm for matrices.
The detailed proof of Theorem 3 can be found in Appendix A. Theorem presents two conditions to make RPE-based Transformers become universal approximators. Intuitively, the attentive condition states that AD should contain a special case of the original attention matrix in Eq.(1), where Wq = WK E Rdu and dæ 1. The position-aware condition states that A needs break the limitation of A(X) being right stochastic matrix (i.e., A(X) 1 1 for all X E Bxxd) We will present a concrete example satisfying these conditions in the next subsection.
4.2 A Universal RPE-based Transformer
We develop Transformer variant which satisfies the conditions above. In particular, multiply the softmax attention matrix with another matrix, and obtain
(x softmax (X (XWR) + BB
(8)
where @ denotes entry-wiss product. B can take any form described in Section 2. We refer to this attention variant as Universal RPE-based Attention (URPE-based attention).
To make URPE-based attention rely relative positional information, we set C' E Raxx to be learnable Toeplitz matrix in which each element on the descending diagonal from left to right has same value. Note that Toeplitz matrix of shape n. x has 2n 1 degrees of freedom. Therefore, we only need 2n new parameters for each C. can be proved that URPE-based Attention satisfies the two conditions in Theorem and the proof can be found in Appendix B.
Proposition 4. URPE-based Attention defined in (8) satisfies the conditions in Theorem 3. Consequently, given n, N* Transformers using form of attention are universal approximators of continuous sequence-to-sequencce functions that map compact domain in Raxd to Raxd
To further improve parameter efficiency, we set C to be shared across different layers but to unique for each attention head. As example, in Transformer-Xi (see Section 5.2), we introduce only about
5

---

Position Identification
Even Token Prediction
1.0
AP
Accuracy
Accuracy
0.6
0.6
0.2
02
M|=10
M==1,000
M=110,00
[V]=10
|V=11000
MV=10,000
Figure 1: Results on synthetic sequence-tor sequence-to-sequeen -osseuunnce tasks: (1) Position Identification (Left Panel); (2) Even Token Prediction (Right Panel). [V] is the vocabulary size. The URPE-based Transformer model consistently solves both tasks across di different settings while other methods fail.
1:20
0.23
03
0.15
0.19
1.30
02
3.0
0.03
0.03
0.25
0.05
-32
57
00.0
-03
5.8
matnx B, task
matri C, task
matnx B, LIP task
matrix C, ETP task
Figure 2: Visualizations of the Iearned Universal RPE (matrix B and C' in (8)) It can be easily seen that the matrix B and C capture different aspects of positional information.
4K new parameters, which is negligible compared to the 151M parameters of the Transformer-XL model but still leads non-trivial improvements.
We make two more discussions for our designed URPE-basee attention. The first one is about applying URPE-based attention in the causal setting. Causal attention is important in language generation tasks.
Attention is compatible with it as one can set the (i.j)-th entry C to be 0 for > j. The second one is the initialization of C. In practice, the matrix C can be initialized as an all-one matrix. Therefore, the model behaves identically to the original RPE-based model at initialization, and the additional parameters in C are learned gradually. We can also fine-tune any well-trained RPE-based Transformer to its URPE-based counterpart by setting C as an all-one matrix and further fine-tuning the model to learn C.
5 Experiments
In this section, we empirically study the effectiveness of the proposed model. In particular, we aim at answering the following questions through experiments:
Can the theoretical results on the approximation capability of RPE--based Transformer and URPE-based Transformer be reflected in certain experiments?
Question 1:
Question 2: With different RPE methods (the matrix B in Eq)(8)), can URPE-based
Transformer outperform RPE-based counterpart real-world applications?
Question 3: Can URPE-bbaed Attention serve versatile module to improve the general Transformers beyond language tasks?
We will answer each question with carefully designed experiments in the following sub-sections. Due to space limitation, we only present results on representative model architectures, task types, and data modalities in the main body of the paper. More results presented in the appendix. All codes implemented based on the official codebases of Fairseq [50] and Graphormer [67] in PyTorch [51].
5.1 Synthetic Tasks
To empirically verify our theoretical results on the approximation capability of RPE-based Trans- former and URPE-based Transformer, we design two synthetic tasks: 1) Position Identification; 2) Even Token Prediction.

---

Table 1:
Language model perplexity scores on WikiText- 103 validation and test set. We use * to indicate the best performance. All the results of the baseline methods are reported in [10]
Model
#Params
Valid Perplexity
Test Perplexity
LSTM [21]
48.7
TCN [2]
45.2
GCNN-8 [11]
44.9
LSTM+Neural cache [21]
40.8
GCNN-14 [11]
37.2
QRNN [46]
151M
33.0
Hebbian+Cache [53]
29.9
Transformer- XL Base [10]
151M
23.1
24.0
Transformer-a XL Base + URPE-based based Attention (ours)
15IM
22.4"
23.2"
Both Position Identification (PI) task and Even Token Prediction (ETP) task are sequence-to-sqquenge prediction tasks. Given a sequence of tokens (W1, u2,..- , the PI task is to predict the position index of each token in the sequence, i.c., the target sequence-to-sequenee function f to approximate can be defined as
SPI(WI, W2, m.,) = (1,2,-...,)))
The ETP task is defined follows: for the first half of positions in sequence, the task requires the model to output the input tokens at positions with even number index; for the remaining half of positions, the task requires the model output the special token End-Of-Sentence (FOS), i.e.,
fETP 11, W2. wr) = (w2, w4, Wny EOS, .EOS)
(10)
Both tasks require the model to accurately encode the positional information, which would be difficult for RPE-based Transformers capture. For both tasks, we use synthetic datasets with randomly generated sequences. In detail, we vary the token vocabulary size from [10, 1000, 10000] and set the sequence length to 128. We choose the vanilla Transformer the base model and compare the following ways to encode positional information: 1) no positional encodings (noPE); 2) T5-stylc relative positional encoding (RPE) [54]: 3) URPE with T5-style RPE backbone Transformer. The number of layers and the number of attention heads are set to 3 and 12, respectively. The hidden dimension
768.
Results. We use token-level accuracy as the evaluation metric. The experimental results are shown in Figure 1. From the figure, it can be easily seen that the Transformer without PE and the Transformer with T5-style RPE cannot perfectly solve the synthetic tasks (less than 60% accuracy). On the contrary, the URPE-based Transformer achieves 100% accuracy on both tasks. Firstly, this result clearly indicates that our proposed model outperforms the backhone T5-style RPE-baaed Transformer by a large margin. Furthermore, we can see that even for such simple tasks, the Transformer with T5-style RPE sometimes fails, while the URPE-based Transformer succeeds and approximates the target function well, which consistent with our theoretical findings. Lastly, we provide visualizations of the learned Universal RPE (8). on both tasks in Figure 2, which show that the matrix and capture different aspects positional information.
5.2 Language Modeling
We use language modeling to study the effectiveness of the proposed URPE-based Attention. Lan- guage modeling is important practical application which usually requires the modelling of long- term dependency between tokens. We conduct experiments on the WikiText- dataset [47]. which contains 103M training tokens from 28K articles, with an average length of 3.6K tokens per arti- cle. Relative positional encoding methods are popularly used in language modelling. We choose Transformer-Xi model [10] as the backbone model of our URPE-based Transformer. Following [10], the number of layers and the number of attention heads are set to 16 and 10 respectively. The dimension of hidden layers and feed-forward layers are set to 410 and 2100. The detailed descriptions of the baselines and training settings are presented in the appendix.
7

---

Table 2: Mean Absolute Error (MAE) on ZINC test set. We use
to indicate the best performance.
Model
Params
Test MAE SlNSeSubset
Test MAE ZINC-Full
GIN [66]
509,549
0.526=0.051
0.088
GraphSAGE [23]
505,341
0.398=0.002
0.126=00003
GAT [62]
531,345
0.38410.007
0.111110.02
GCN [35]
505,079
0.367=0.011
0.113=0.002
MoNet [48]
504,013
0.002
0.090++0.002
GatedGCN-PE [5]
505,011
0.014=0.006
(PNN(sum) [20]
480,805
0.145=00007
HIMP [17]
614,516
0.151=0.006
0.036=00.002
PNA [8]
387,155
0.142-10.010
GT [15]
588,922
0.226_0.0114
SAN [37]
508.577
0.139=0.006
Gruphormer [67]
489.321
0.122=0.006
0.052=00000 0.028++0.002
Graphommer--URPEB-asee Attention (ours)
491,737
0.086-00.07
Table 3:
Results on PCQM4M from OGB-LSC. We use to indicate the best performance. The
results of the baselines are reported in [67, 29].
Model
iParrms
Valid MAE
GCN [35]
2.0M
0.1691
GIN [66]
3.8M
0.1537
GCN-VN [35
4.9M
0.1485
GIN-VN [66, 20]
6.7M
0.1395
GINE-VN [6, 20]
13.2M
0.1430
DeeperGCN-VN [38, 20]
25.5M
0.1398
GT [15]
0.6M
0.1400
GT-Wide [15]
83.2M
O. 1.1408
Graphormer [67]
12.5M
0.1264
Graphormer+ URPE-based Attention (ours)
12.5M
0. 0238
Results. We show the perplexity scores on both validation and test set of different models in Table 1. It can be easily seen that the Transformer-Xe equipped with our URPE-based attention achieves 22.4 and 23.2 valid and test perplexity scores, respectively, which are 0.7 and 0.8 lower than the backbone Transformer-XI. model and also significantly better than other baselines. First, the results suggest that our proposed URPE-based attention can be well applied Transformer-Xi in real- world applications. Together with the observations in Section 5.1, we believe our URPE can be used in other RPE-based architectures, such as [58, 26]. It is worth noting that our model has negligible more parameters (about 4k) compared to the backbone Transformer-XL. Thus, the improvement in the perplexity should be mostly attributed to the stronger expressiveness the model.
5.3 Graph Learning
We further examine whether the proposed URPE-based Attention serve versatile module to improve the general RPE-based Transformers beyond language tasks. The Transformer- models have become increasingly popular in the graph learning area [67, 37, 15]. Among those models, the recently proposed Graphormer [67] achieves oftte-of-theann performance in many graph learning tasks [68, 59]. In Graph Transformers, RPE is used rather than APE since RPE only calculates distances between nodes, which naturally preserves many invariant and equivariant properties.
The attention computation in Graphormer also follows the (4) in Section 2. Specifically, Graphormer calculates the shortest-path distance between any pair of nodes and encodes this in- formation bias term in the softmax attention reflect the relative position of any node in the

---

Table Comparison of RPE-based and UPRE-based Transformer- XL models of different sizes. We report perplexity scores on WikiTexx- 103 validation set. L denotes the number of layers.
Model
L
1
L = 8
L 16
Transformer-XL.
29.6
26.0
23.1
Transformer- XL + URPE- based Attention (ours)
28.7
25.2
22.4
Table 5: Inference Runtime (ms in log base 2) and Peak Memory Usage (GB) of RPE-based Transformer and URPE-based Transformer. N denotes the input sequence length.
Inference Runtime
Peak Memory Usage
Model
N 128
N 256
N = 512
N 128
N
256
N
512
RPE-bbased Transformer
4.55
5.60
6.79
0.96
1.12
1.86
URPE-based Transformer (ours)
4.59
5.66
6.91
0.97
1.17
2,04
graph. We refer the readers to [67] for the detailed description of Graphormer. Similar to previous experiments, we adapt the URPE-based Attention to the Graphormer and compare them on two benchmark datasets covering graph representation learning tasks from small to large scale datasets: ZINC from Benchmarking SaanhaaariingGGNN GNNs [16] and PCQM4M from Open Graph Benchmark Large Scale Challenge (OGB-LSC) [29]. For both tasks, choose several competitive Transformer based models and GNNs as our baselines. Details of the experimental settings are presented in the appendix.
ZINC. ZINC is real- dataset which consists of 250K molecular graphs. The task is to predict the constrained solubility of a molecule which is an important chemical property for drug discovery. We train our models on both the ZINC-Full and ZINC-Subset (12K selected graphs following [16]). To demonstrate the power of our method and for fair comparison, we set the parameter budget of the model to be less than 500K following [16, 67J. We build on the Graphormer [67] model which consists of 12 layers. The dimension of hidden layers and feed-forward layers are set to 80. The number of attention heads set to 32.
PCQM4M. PCQM4M is a quantum chemistry regression task in OGB-LSC [29]. The PCQM4M dataset contains more than 3.8 million molecular graphs in total, which is currently the largest graph-level prediction dataset. The state-of-the-arr architecture for this task the Graphormer model introduced above. We still follow [67] to set the hyper-pane parameters in the Graphromer model and equip with URPE. In detail, our Graphormer with URPE-based Attention consists of layers and 32 attention heads. The dimension of hidden layers and feed-forward layers are set to 512.
Results. The experimental results ZINC and PCQM4M shown in Table 2 and 3, where the score is averaged over four experiments with different seeds. It can be easily seen that the Graphormer model equipped with our URPE-basee based Attention consistently outperforms the backbone Graphormer model on both ZINC and PCQM4M tasks. In particular, our URPEE-asee Attention enables the Graphormer model reduce more than 40% relative mean absolute error on the test of ZINC-Subset and ZINC-Full. On the PCQM4M task, the improvement is around 0.003 mean absolute eтror which is also significant improvement under the quantum chemistry precision. It is worth noting that our Graphormer model with URPE-based Attention achieves competitive performance compared to the Graphormer Base model with 48.3M parameters reported [67]. Therefore, we believe our proposed architecture significantly improves the expressive power of the Transformer backbones and can be well extended to practical scenarios beyond language tasks.
5.4 More Analyses
URPE-based Attention consistently improves the performance of models of different sizes. We conduct ablation experiments on the Language Modeling task and vary the number of layers in [4, 16] to investigate different model sizes. Following the experiment settings in Section 5.2, the number of attention heads is set to 10. The hidden dimension set to 41. The dimension of the feed-forward layer is set to 2100. The results are presented in Table 4. It can be easily seen that our URPE-based Attention consistently reduces the perplexity scores of Transformer-Xl. models of different sizes, which indeed demonstrates the versatility of our TRPE-based Attention.

---

Runtime and Memory Usage Evaluation. We further conduct memory and time costs profiling experiments on our URPE-based Transformers. We choose the vanilla Transformer as the backbone model. The number of layers and the hidden dimension are set to 12 and 768 respectively. The number of attention heads set to 12. The batch size set to 32. We vary the sequence length from [128, 256, 512]. We run profiling of all the models on 16GB NVIDIA Tesla V100 GPU. Following Combiner [55], we compare the inference speed and memory costs of the vanilla Transformer with RPE and our URPE. The results are presented in Table 5, which show that our URPE only increases minor computational costs.
Summary. In this section, we design series of experiments to answer the questions on the effectiveness and upplicability of the proposed URPE-based Attention. All the experimental results suggest that our theoretical findings are convincing, and Transformers with our modification are effective, powerful, and widely applicable across different tasks.
Related Work
Expressive power of Neural Networks. Quantifying the capacity of neural networks is an important research direction in the literature on deep learning. [9. 19, 27, 4] showed that neural network with one hidden layer and unbounded width can approximate arbitrary continuous functions on compact support with arbitrarily small error. Many works also studied the width efficiency on the expressive power of neural networks [44, 24, 40] and proved that ReLU networks with a bounded width but unlimited depth can achieve universal function approximation. Recently, there has been increasing interest in the theoretical understanding of Transformer models. Yun et al. [69] theoretically showed that Transformers can approximate any continuous sequence-to-sequene approximation) on a compact domain by proving that stacking of self- attention layers can compute contextual mappings of the input embeddings. Dong et al. [13] analyzed the limitations of attention- only Transformers without considering FFN blocks, normalizations, and skip connections. Hron et al. [28] analyzed the behavior of multi-head attention and connect it with the Gaussian process when the number of heads tends to be infinity. In [7], it is proved that multi-head attention layer with enough heads is at least as expressive as any convolution layer. All works above consider Transformers with absolute positional encoding, which is the main difference between them and our work.
functions (i.e., universal
Positional encoding methods in Transformers. In [6]], the vanilla Transformer encodes the positional information via the absolute positional encoding (APE). Shaw et al. [58] is the first to introduce relative positional encoding (RPE) to Transformer. From then on, many works explored different RPE strategies based on [58]. Transformer-Xi [10] re-paramcterizes the self-attention to integrate relative positional encoding and enables long sequence modelling. T5 [54] simplifies the vector representations of relative positions to scalars. Kitaev al. [36] disentangles the positional and content information in the Transformer encoder, which leads to an improved constituency parser. Ke et al. [33] further shows that such disentanglement also improves Transformer in general language pre-training and achieves superior performance on various downstream tasks. There are also works that encodes the positional information via other tools like trees [60], complex numbers [63], dynamic systems [41], Fourier features [39]. Compared to most previous works inspired by practical scenarios, our URPE-based attention is theoretically motivated by investigating the expressive power of RPE-based Transformers in a principled way.
7 Conclusion
In this paper, we first investigate the theoretical aspect of the RPE-based Transformers. In particular, we study their expressive power and provide a surprising theoretical finding which shows that widely- used Transformers with RPE are not universal function approximators. To design a more powerful RPE-based Transformer, we present sufficient conditions on the attention module to achieve universal function approximation and develop novel Universal RPE-based Transformer using new relative positional encoding approach. We conduct carefully designed experiments on synthetic sequence data, natural language, and graphs to show that our model brings consistent performance gains compared with existing RPE-based Transformers. In the future, we will benchmark our Universal RPE on other RPF-baaed Transformers and typical tasks to further verify its versatility as basic module for Transformer-basee models.
10

---

Acknowledgements
We thank Tianle Cai and Jianlin Su for the helpful discussions. We also thank all the anonymous reviewers for the very careful and detailed reviews as well as the valuable suggestions. Their help has further enhanced our work. This work is supported by National Science Foundation of China (NSFC62276005), The Major Key Project of PCL (PCL2021A11) 12), Exploratory Research Project of Zhejiang Lab (No. 2022RC0AN02), and Project 2020BD006 supported by PKUBaidu Fund.
References
[1] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization, arXiv preprint arXiv:1607.06450, 2016.
[2] Shaojie Bai, J Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling, arXiv preprint 1r03v.1803.1127. 2018.
[3] Hangbo Bao, Li Dong, Furu Wei, Wenhui Wang, Nan Yang. Xiaodong Liu, Yu Wang, Songhao Piao, Jianfeng Gao, Ming Zhou, et al. Unilmv2: Pseudo-masked language models for unified language model pre-training. arXiv preprint arXiv:2002. /2804, 2020.
[4] Andrew R Barron. Approximation and estimation bounds for artificial neural networks, Machine learning, 14(1):115-133) 1994.
[5] Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint 1711 2017.
[6] Rémy Brossard, Oriel Frigo, and David Dehaene. Graph convolutions that can finally model local structure. arXiv preprint arXiv:2011.15069 2020.
[7] Cean-Baptiste Cordonnier, Andreas Loukas, and Martin Jaggi. On the relationship between self- attention and convolutional layers. In International Conference on Learning Representations, 2020.
[8] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pictro Liò, and Petar Veličković. Principal neighhourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 13271, 2020.
[9] George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
[10] Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978-2988, 2019.
[11] Yann N Dauphin, Angela Fan, Michael Auli, and David Grangier. Language modeling with gated convolutional networks. In International conference on machine learning, pages 933-941, PMLR, 2017.
[12] Jacob Devlin, Ming-We Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 18X0v:18/0.0480 2018.
[13] Yihe Dong, attention loses rank doubly exponentially with depth. In International Conference on Machine Learning, pages 2793-2800 PMLR, 2021.
Cordonnier, and Andreas Loukas. Attention is not all you need: Pure
[14] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference Learning Representations, 2021.

---

[15] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
[16] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982) 2020.
[17] Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular graphs. arXiv preprint WrXi:2206.12219, 2020.
[18] Gerald B Folland. Real analysis: modern techniques and their applications, volume 40. John Wiley & Sons, 1999.
[19]
Ken-Ichi Funahashi. On the approximate realization of continuous mappings by neural networks. Neural networks, 2(3):183-192, 1989.
[20] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263-1272, PMLR, 2017.
[21] Edouard Grave, Armand Joulin, and Nicolas Usunier. Improving neural language models with a continuous cache. arXiv preprint arXiv:1612.04423 2016.
[22] Robert M Gray. Toeplitz and circulant matrices: A review. now publishers inc, 2006.
[23] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[24] Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. arXiv preprint
2017.
[25] Pengeheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhancee bert with disentangled attention. arXiv preprint arXiv:2006.0366 2020.
[26] Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhancee bert with disentangled attention. In International Conference on Learning Representations, 2021.
[27] Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2):251-277, 1991.
[28] Jiri Hron, Yasaman Bahri, Jascha Sohl-Dickstein, and Roman Novak. Infinite attention: Nngp and ntk for deep attention networks. In International Conference on Machine Learning, pages 4376-4386. PMLR, 2020.
[29] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb- Isc: A large-scale challenge for machine learning on graphs. arXiv preprint arXiv:2103.09493 2021.
[30] Gao Huang, Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q Weinberger. Deep networks with stochastic depth. In European conference computer vision, pages 646-661. Springer, 2016.
[31] Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out-performs graph neural networks. In International Conference on Learning Representations, 2020.
[32] Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference machine learning, pages 448-456 PMLR, 2015.
[33] Guolin Ke, Di He, and Tie- Yan Liu. Rethinking positional encoding in language pre-training. In International Conference on Learning Representations, 2021.
[34] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
12

---

[35] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 2016.
[36] Nikita Kitaev and Dan Klein. Constituency parsing with a self-attentive encoder. arXiv preprint arXiv:1805.01052, 2018.
[37] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létournau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Pro- cessing Systems, 34, 2021.
[38] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.07739, 2020.
[39] Yang Li, Si Si, Gang Li, Cho-Jui Hsieh, and Samy Bengio. Learnable fourier features for multi-dimensional spatial positional encoding. Advances in Neural Information Processing Systems, 34, 2021.
[40] Hongzhou Lin and Stefanie Jegelka. Resnet with one-neuron hidden layers is universal approximator. Advances in neural information processing systems, 31. 2018.
[41] Xuanqing Liu, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh. Learning to encode position for transformer with continuous dynamical model. arXiv preprint arXiv:2003.09229, 2020.
[42] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: robustly optimized bert pretraining approach. arXiv preprint 1907.
2019.
[43] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. arXiv preprint arXiv:2103. 14030, 2021.
[44] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Advances in neural information processing systems, 30, 2017.
[45] Shengjie Luo, Shanda Li, Tianle Cai, Di He, Dinglan Peng, Shuxin Zheng, Guolin Ke, Liwei Wang, and Tie- Yan Liu. Stable, fast and accurate: Kernelized attention with relative positional encoding. Advances in Neural Information Processing Systems, 34, 2021.
[46] Stephen Merity, Nitish Shirish Keskar, and Richard Socher. An analysis of neural language modeling at multiple scales. arXiv preprint 1803.08400 2018.
[47] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint 1rXiv:1609.072 2016.
[48] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5115-5124, 2017.
[49] Sharan Narang, Hyung Won Chung, Yi Tay, William Fedus, Thibault Fevry, Michael Matena, Karishma Malkan, Noah Fiedel, Noam Shazeer, Zhenzhong Lan, et al. Do transformer modifi- cations transfer across implementations and applications? arXiv preprint 192. 2021.
[50] Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: fast, extensible toolkit for sequence modeling. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations)) pages 48-53, 2019.
[51] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
13

---

[52] 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.
[53] Jack Rae, Chris Dyer, Peter Dayan, and Timothy Lillicrap. Fast parametric learning with activation memorization. In International Conference on Machine Learning, pages 4228-4231 PMLR, 2018.
[54] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with unified text-to-text transformer. arXiv preprint arXiv: 1910. 10683, 2019.
[55] Hongyu Ren, Hanjun Dai, Zihang Dai, Mengjiao Yang, Jure Leskovee, Dale Schuurmans, and Bo Dai. Combiner: Full attention transformer with sparse computation cost. Advances in Neural Information Processing Systems, 34:22470-22482, 2021.
[56] Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11 / 198, 2020.
[57] Michael Schlichtkrull, Thomas Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In European semantic web conference, pages 593-607. Springer, 2018.
[58] Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position rep- resentations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Short Papers), pages 464 468, New Orleans, Louisiana, June 2018. Association for Computational Linguistics.
[59] Yu Shi, Shuxin Zheng, Guolin Ke, Yifei Shen, Jiacheng You, Jiyan He, Shengjie Luo, Chang Liu, Di He, and Tie- Yan Liu. Benchmarking graphormer on large-scale molecular modeling datasets. arXiv preprint arXiv:2203. 04810, 2022.
[60] Vighnesh Shiv and Chris Quirk. Novel positional encodings to enable tree-based transformers. In Advances in Neural Information Processing Systems, pages 12058 12068, 2019.
[61] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Informa- tion Processing Systems, pages 6000-6010, 2017.
[62] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[63] Benyou Wang, Donghao Zhao, Christina Lioma, Qiuchi Li, Peng Zhang, and Jakob Grue Simonsen. Encoding word order in complex embeddings. arXiv preprint arXiv: 12333, 2019.
[64] Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396-43,, 2020.
[65] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning. pages 6861-6871. PMLR, 2019.
[66] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[67] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34, 2021.
14

---

[68] Chengxuan Ying, Mingqi Yang. Shuxin Zheng, Guolin Ke, Shengjie Luo, Tianle Cai, Chenglin Wu, Yuxin Wang. Yanming Shen, and Di He. First place solution of kdd cup 2021 & ogb large-scale challenge graph prediction track. arXiv preprint arXiv:2 106.08279, 2021.
[69] Chulhee Yun, Srinadh Bhojanapalli,, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequeee functions? International Conference Learning Representations, 2019.
[70] Chulhee Yun, Yin- Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. O (n) connections are expressive enough: Universal approximability of sparse transformers. Advances in Neural Information Processing Systems, 33:13783-13794, 2020.
[71] Biao Zhang and Rico Sennrich. Root mean square layer normalization. In H. Wallach,
H. Larochelle, A. Beygelzimer, F. d'Alché-Buu E. Fox, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] see Section
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "pdA4B0WIkU", "reviewer": "Reviewer_gvHj", "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.", "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?\n\nFinally, 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.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n------------\n\n- The theoretical assessment of the limitations of RPE is novel, interesting and very simple to follow\n- The proposed universal RPE is also interesting and simple to follow\n- I particularly enjoyed both synthetic tasks that clearly showcase that RPE cannot calculate the absolute positions of tokens while universal RPE can\n- The experimental evaluation showcases that this simple proposed improvement can improve the results in various tasks\n\nWeaknesses\n---------------\n\n- 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.\n- 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?\n- 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lCVBF1aW-_Y", "reviewer": "Reviewer_TbAW", "summary": "This paper presents URPE, a new universal relative position embed for stronger transformer architecture.\nStarting from \"absolute position embed-based transformers are universal approximators of continuous\nsequence-to-sequence functions on a compact domain, authors analyze the approximation power of relative\nposition embedding in mathematics, and conclude that RPE-based transformers are not universal\napproximators. Then authors propose a new relative position embedding with simple but effective\nimprovement to achieve universal representations. Experiments on both language and graph datasets show\nURPE-based transformer’s advantages. Detailed ablation experiments and analyses make the improvements of\nURPE reliable.", "questions": "See Weaknesses.", "limitations": "The authors briefly discussed their limitations in L348-350.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. The motivation and method of this paper are both proven in mathematics.\n2. The proposed URPE is easy to implement and can adapt to any RPE-based transformers for further\nimprovements. It only introduces a few extra parameters to the original RPE.\n3. This paper is well written and organized. Motivations, methods, and concerns in experiments are all very\nclear and easy to follow.\n\n### Weaknesses\n1. Improvements seem to be marginal.\n2. Experiments in each table are conducted under a single transformer architecture(e.g., Transformer-Base in\nTab.). It’s interesting to see how many gains URPE can obtain with all kinds of transformer architectures\n(e.g., Transformer-Tiny/Small/Large, etc.).\n3. Experiments in Vision Transformer. Relative Position Embedding is also widely used in many vision\ntransformers (e.g., Swin-Transformer). The results of the URPE-based vision transformer are important to prove\nURPE’s generalization to other modalities.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UDqgijb7kqQ", "reviewer": "Reviewer_BbEH", "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.\n\n============================\n\nGreat paper, and they addressed my concern enough. I'd like to sustain my score.", "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?\n", "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.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Even though when $d=1$, why Transformer with RPE is not universal approximator is shown theoretically.\n- It presents conditions to be a universal function approximator.\n- It proposes URPE. URPE-based Transformer can cover the conditions suggested to be a universal function approximator.\n- 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.\n\nWeaknesses:\n- I couldn't find the critical weakness even though I tried to find by reading the manuscripts several times with references.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MDPWUjwa6DE", "reviewer": "Reviewer_zNBv", "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.", "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.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nAs 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KXCso_8veZB", "reviewer": "Reviewer_hYM6", "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.", "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.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nI appreciate that the analysis is presented in a clear and concise manner which makes it easy for the reader to follow. \n\nI cannot come up with obvious weaknesses, however with the caveat that I am not very familiar with the underlying theory.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept