Linearized Relative Positional Encoding
Authors: Zhen Qin
Weixuan Sun
Kaiyue Lu
Hui Deng
Dongxu Li
Xiaodong Han
Yuchao Dai
Lingpeng Kong
Yiran Zhong
Venue: Accepted by TMLR ()

Abstract: Relative positional encoding is widely used in vanilla and linear transformers to represent positional information. However, existing encoding methods of a vanilla transformer are not always directly applicable to a linear transformer, because the latter requires a decomposition of the query and key representations into separate kernel functions. Nevertheless, principles for designing encoding methods suitable for linear transformers remain understudied. In this work, we put together a variety of existing linear relative positional encoding approaches under a canonical form and further propose a family of linear relative positional encoding algorithms via unitary transformation. Our formulation leads to a principled framework that can be used to develop new relative positional encoding methods that preserve linear space-time complexity. Equipped with different models, the proposed linearized relative positional encoding (LRPE) family derives effective encoding for various applications. Experiments show that compared with existing methods, LRPE achieves state-of-the-art performance in language modeling, text classification, and image classification. Meanwhile, it emphasizes a general paradigm for designing broadly more relative positional encoding methods that are applicable to linear transformers.

Published in Transactions on Machine Learning Research (07/2023)
Linearized Relative Positional Encoding
ZZen Qin
'Hui Deng Yuchao Dai LLngpeng Kong Yiran Zhong
2,3 Weixuan Sun
"Kaiyue Lu
DDongxu Li "Xiaodong Han
Shanghai AT Laboratory OOpeNNIPPab
Australion National University The University of Hong Kong
Northwesterm Polgtechnical University
Reviewed on OpenReview: https: // o/pp///veew.......em form?? id=zolyps2gge
Abstract
Relative positional encoding is widely used in vanilla and linear transformers to repre- sent positional information. However, existing encoding methods of vanilla transformer are not always directly applicable to a linear transformer, because the latter requires decomposition of the query and key representations into separate kernel functions. Never- theless, principles for designing encoding methods suitable for linear transformers remain understudied. In this work, we put together a variety of existing linear relative positional encoding approaches under canonical form and further propose family of linear rela- tive positional encoding algorithms via unitary transformation. Our formulation leads to principled framework that can be used to develop relative positional encoding methods that preserve linear space-lime complexity. Equipped with different models, the proposed linearized relative positional encoding (LRPE) family derives effective encoding for vari- ous applications. Experiments show that compared with cxisting methods, LRPE achieves state-of-the-art performance in language modeling, text classification, and image classifi- cation. Meanwhile, it emphasizes general paradigm for designing broadly more relative positional encoding methods that are applicable to linear transformers.
1 Introduction
Transformers have achieved remarkable progress in natural language processing (Dvliin et al. 2019 Radford
et al., 2019 Brown et al., 2020), computer vision (Dosovitskiy et al. 2020 Liu et al. 2021 Arnab et al. 2021
and audio processing (Karita al. 2019 Zhang et al., 2020 Gulati et al. 2020 Sun et al. 2022)
As an
important ingredient in transformers, positional encoding assigns a unique representation for each position of token in sequence so that the transformers can break the permutation invariance property. Among these
encoding methods, absolute positional encoding (Vaswani et al. 2017 Sukhbaatar et al.
2015 Devlin et al.
2019 Liu et al. 2020) maps each individual position index into continuous encoding. W Whereas relative
ional encoding (Shaw et al., 2018 Su et al. 2021 Horn el al.
2021 Liutkus et al.
2021
Huang el. al.
2020 Raffel et al. 2019) generates encoding for each query-key pair, representing their relative positional
offset. We focus on relative positional encoding as they are not constrained by input lengths (Chen 2021
while showing superior performance (Shaw al. 2018).
Linear transformers CChen 2021
Qin et al. 2022b a Liu al. 2022 Lu et al. 2022 attract more attention
recently as they can achieve linear space-time complexity with respect to input sequence length, while main- taining comparable performance with vanilla transformers. Most existing linear transformers use absolute positional encoding methods to encode positional information, since most existing relative positional encod- ing methods are designed for vanilla transformers and are not directly applicable to linear transformers. The main cause behind this limitation that linear transformers decompose key and value representations the self-attention modules into separate kernel functions achieve linear space-time complexity. Such an additional requirement the decomposibility is not always satisfied by existing relative positional encoding
* Tndicctes the corresponding author. Email: zhongyirandgmail.com

---

Published in Transactions on Machine Learning Research (07 (07/202) /023)
Softmax
d
d d
d
d d
Wt-s
Wt
Ws
KT
O(d'd O(n)
O(ne + ndf )~ On)
Figure 1: Illustration of existing relative positional encoding (left) and the proposed LRPE (right). Q, K, and V are all in the shape of n by d, where is input length and d is feature dimension. Tensors in the dashed line box are associated for computation. In the vanilla relative positional encoding, query key attention has to be calculated first, leading to quadratic complexity. Wi-s refers to relative positional encoding, where 8 are two positional indices the query and key, respectively. Our LRPE achieves a decomposable encoding, i.e., W, and W, are only dependent on positions of the query and key, making it fully compatible with linear transformers. When dealing with long sequences, d < n, the computation complexity is dominated by n, rendering d negligible.
methods. On the other hand, despite some individual works (Qin et al. 2022b Chen 2021 ) general princi- ples for designing relative positional encoding for linear transformers remain largely understudied. A recent work, RoPE Su ct al.] (2021) proposes a new set of multiplicative encoding solutions based on rotational positional encoding and can be applied to linear transformers. In Appendix [D.1] show that RoPE be seen special form of LRPE.
In this work, we aim to bridge this gap and study the principal framework to develop relative positional encoding applicable for linear transformers. To this end, we start by presenting a canonical form of relative positional encoding, which reveals that differences in existing encoding methods boil down to choices of a set of query, key and relative positional matrix primilives. By properly selecting and composing these primitives, we could derive various existing encoding methods for transformers.
Taking advantage of the canonical form, we introduce the main contribution of our work, i.c., special family of relative positional encoding methods called linearized relative positional encoding (LRPE). Specifically, we supply a sufficient condition for designing compatible encoding methods, especially for linear transformers, and prove that the linearized relative positional encoding is a unitary transformation. The benefits of using unitary transformation are twofold. On one side, since it is derived from the decomposable positional matrix, it can maintain the linear space-time complexity as shown Fig. [ Second, the unitary transformation property allows us to effectively derive the family of closed-form solutions. In particular, we show that a number of encoding methods pertain to the LRPE family, including those used in RoPE (Su et al.) 2021 and PermuteFormer (Chen 2021).
Furthermore, LRPE sheds light on simple yet flexible theoretical paradigm to develop new effective rela- tive positional encoding. To demonstrate this, we derive non-exhaustively three additional LRPE encoding methods by parameterizing the generic solution differently, including solutions living in either real or com- plex domains. Since unitary transformations are special cases of relative positional matrix, LRPE is applicable to linear transformers and exclusively suitable within encoder and/or decoder layers. We exper- imentally demonstrate the effectiveness of the LRPE family autoregressive and bidirectional language modeling, text classification, and image classification. Results show that LRPE achieves superior capability in represcnting relative positional information, commonly resulting in unrivalled performance than previous encoding methods.
summary, our main contributions are as follow:
We present canonical form of relative positional encoding, which derives most existing relative positional encoding methods as its special case, including those used in linear transformers.
2

---

Published in Transactions on Machine Learning Research (07/2023)
Based the canonical form, propose linearized relative position encoding (LRPE), simple yet principal formulation to derive an encoding family that respects the linear space-time complexity in linear transformers. We show several existing relative positional encoding methods in linear transformers are in LRPE family. We also provide additional solutions from this generic form. Experiments on various downstream lasks, such as language modeling, lext. classification, and image classification show that the LRPE family more robust and consistently produces better results across tasks than previous relative encoding methods, are flexible in being plugged into encoder and/or decoder layers in linear models. In addition, it is generic to derive existing and potentially new encoding methods.
2 Background and Preliminary
In this section, we provide preliminary knowledge and describe related work to facilitate the rest discussions. In the following, we denote the k-th row of matrix M as m the d-dimensional identity matrix as Ia- We omit the subscript when it is unambiguous from the context. The complete list of notations can be found in Appendix
2.1 Transformer and its linearization
We first briefly review vanilla transformer (Vaswani al. 2017) and its linearization (Katharopoulos et al. 2020).. The key component of transformer models the self-attention block, which involves three matrices Q (Query), K (Key) and V(Value); each of them is a linear projection taking X Raxd input:
Q = D== XWK, XWv E Radd
(1)
The output O Raxd is computed using the Softmax weighted sum:
0 Softmax (QK* /Vdvv.
(2)
The computation overhead of the vanilla transformer grows quadratically with respect to the sequence length n, which becomes the bottleneck for transformers to handle long input sequences. Linearization of self- attention aims to reduce the computation complexity linear (Katharopoulos et al. 2020 Ke et al. 2021
Qin et al. 2022b: Vyas et al. 2020: Peng et al.
2021 Xiong al., 2021 [Sun et al. 5555 typically achieved
via a decomposable kernel function Φ: Rd + Rd. Specifically, the output of linear attention computed as:
0 = A - (Q)[((()
A diag(o 1,.)).
The key property of linear attention the decomposability of the kernel function. This enables to compute VV Radd first, which leads to the O(nd²) complexity, further reducing to O(n) with longer inputs (d < n). See Appendix B for detailed discussion.
2.2 Positional encoding
Self-attention is capable of parallel sequence processing but cannot capture positional information of each token. To address this issue, positional encoding methods are proposed, which can be generally categorized into two groups: absolute positional encoding and relative positional encoding.
A bsolute positional encoding employs handcraft functions (Vaswani et al. 2017 Sukhbaatar et al, 2015) or learnable encoding lookup tables P E Raxd (Devlin al.) 2019 Liu al. 2020) to represent position indices as encodings. These encodings are then combined with the context vector additively:
qs Wo(x, p.), k, = WR(x, + Ps),
(4)
V. Wr(x, +p))
where the encoding formulation only depends on the absolute position index s, and the positional encoding size is restricted by the input sequence length.
3

---

Published in Transactions on Machine Learning Research (07/2023)
Relative positional encoding considers relative position offsets between two input tokens (Sha et al. 2018 Qin et al. 2023), C.C.,
est = x X
+ f(x,, -
(5)
where s, t are the two positional indeices, Cat denotes the attention score before softmax. Compared to absolute posilional encoding, relative positional encoding generally achieves beller performance as it can handle variable imput length (Chen 2021 However, extra cost on computation and memory makes it not
so efficient than absolute positional encoding (Likhomancnko et al.
2021
Most existing relative positional encoding methods (Rallel et al. 2019 Shaw el al., 2018 Huang et al. 2020 Chi et al., 2022) require computing query-key attention QK' and combine with relative positional information, which incurs quadratic complexity. In contrast, linear attention avoids such a query-key product to achieve the linear complexity. Therefore, common relative positional encoding methods are usually not applicable in linear transformers.
3 Our Method
In this section, we present our main technical contribution on linearized relative positional encoding, which is an encoding family that preserves linear space-time complexity. Specifically, we start by presenting a canonical form of relative positional encoding and show that existing encoding methods can be derived by instantiating the canonical form with different choices of so-called primitive queries, keys, and positional matricos in Section 3.1 When imposing the decomposability constraint this canonical form, we obtain sufficient condition for linearized relative positional encoding (LRPE) and derive family of concrete We provide an implementation sketch in Section 3.3
solutions in real and complex domains in Section 3.2
3.1 Canonical form of relative positional encoding
In order to better establish connections between existing relative positional encoding methods and understand their design principles, we first present a canonical form of relative positional encoding in this section. In particular, given a query qa and key k, pair, their relative positional encoding fret Cd x Cd + C can be represented as:
frel(e. ko) (.
1) RD
(6)
where H represents conjugate transposition and represents number of primitives. We refer q.0) E C4f) (2()) E C. (( t-s E x4d" as query, key and relative positional matrix primitives, respectively, used as constituent components to construct the relative positional encoding. Note that query primitives do not always indicate a reliance on query embeddings, similarly for other primitives. For example, an identify matrix can also serve as primitive, we will show shortly in Section 3.1.1
To demonstrate Eq. is a generic formulation, we show that it flexibly induces wide range of existing relative encoding methods (Shaw et al.) 2018 Su et al. 2021 Horn et al. 2021 Liutkus et al. 2021 Huang et al. 2020 Raffel et al.] 2019) by selecting and compositing different choices of primitives. Among them. we highlight four examples in the following section and leave the complete discussions in the Appendix
3.1.1 Typical encoding examples
Additive. In (Huang et al. 2020), the relative positional encoding is formulated as an extra additive term to the query-key inner-product:
fralqe kt) = H + Wt-s:
(7)
which can be derived by including an extra identity term as a primitive, formally denoted as:
m 2,
6 = qs K k, (11)
t-s = Id. (2) 1., k. = 1a, (!
(8)
t-8 = (Wi- LJ.
4

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Multiplicative. In RoPE (Su et al. 2021 the relative positional encoding works in the form of the weighted inner product:
fral k.) - -.¹ Wr
(9)
which can be denoted as:
11 1 1, a k() k., w W.-..
(10)
3.1.2 Simplification
For the ease of the remaining discussion, we introduce the necessary notations and simplify Eq.
d Σ
10 de =
!1)
2
1-1
1=1
i. (Ga ..... (m!m))y)
Ct. kr,
(kk 5 ..... (k. ( E cd,
(11)
W = dlogk-diag W
(1) t-s.... ".......!!) cdidd
With these notations, we can rewrite Eq. 6 into the matrix form: fial k.) = á k.. Since every component of q, and k, are handled with no difference, without losing generality, we only discuss cases where
fralq,, k,) - g W.
(12)
3.2 Linearized relative position encoding
Eq. is canonical form of relative positional encoding, meaning that its variants are applicable to vanilla transformers but not necessarily for linear ones. To design relative encoding compatible with linear trans- formers, the attention computation has to respect the decomposibilty condition. This additional condition leads the linearized relative position encoding (LRPE) family, defined as follows.
Definition 3.1. A relative posilion encoding is called linearized relative position encoding (LRPE), when the following holds:
yq,, E Cd (ral(q,,)) k.) = 9th W..
(13)
=(M.q,) (M,,,) = C.M.M.k..
where q, go,ke Cd, W., M, Caxd Wo 14.
The assumption of Wo La implies that the interaction between tokens from the same position only depends on the content, which is reasonable enough that most encoding methods respect. In its essence, Eq. 13 ensures the positional matrix decomposable. In this way, the query-key inner-product can be avoided in the altention computation. Consequently, complexity of computing LRPE is O(nd), where is sequence length, d is embedding dimension as Appendix C.2 shows in detail.
We prove that Eq. 13 can be simplified based on the following proposition:
Proposition 3.2. Eq. 13 is equivalent to Eq. and W. is Unitary matria,
W W...
(14)
Proof of Proposition
3.2
According to the arbitrariness of qe kr, Eq. 13 equivalent to
W = MM.M........
(15)
Take - in Eq 13
get (since assume that Wo = Ia):
M Wo Ia-
(16)
5

---

Published in Transactions on Machine Learning Research (07/2023)
Thus, M. is unitary matrix. On the other hand, note that for any unitary matrix P, always have
Wi- M, = M.
(17)
-M (PM,)*
This means that left multiplying M, by unitary matrix does not change Eq. 13 Since M, and My are also unitary matrices, we can perform the following transformation:
M, M
(18)
With Mg, Eq.
15
becomes
W = M
(19)
Take = 0, we have
W, M M. M. L,M M..
(20)
Thus Eq. 19 becomes
--==WWWt Since M, is unitary matrix, W. is also unitary matrix, L.e.
(21)
W I
In the following section, derive some particular solutions of Eq. 14
3.2.1 Particular solutions
In this section, discuss Eq. 14 and give family of solutions. It is worth noting that the solutions provide all in the form of W pH (,), where P, (x)) are unitary matrices. The complete derivation can be found in Appendix
Unitary (Solution 1) The first case is discussed in the complex domain, which not common in transformer models yet exhibiting an elegant solution.
Proposition 3.3. The following form of W. Cdxd satisfies Eq. 14
W , (*
(22)
(+) diag (xpp(sat)).... explisaa))
where P E Cixd is unitary matriz, ag, k 1.....d d are parameters.
Orthogonal (Solution 2) Now we consider the real domain, a more general case transformers.
Proposition 3.4. The following form of W, ddxd satisfies Eq.
14
W. A (+) P. A
diag A B(+)), A E 22222
A (5) block-diagt diagf A (9)
B = I, Ro*9
(23)
A (+) (cos)) (sn()))))
- sin(sar)
cos(soR)
where P Baxd is orthogonal matrir, 0gk, 1, 1....,d parameters.
Permutation (Solution 3) The last case is inspired by PermuteFormer Chen 2021 which is associated with the permutation matrix:
Proposition 3.5. The following form of Wa Raxd satisfies Eq. 14
We PPPAAA (k)
π {1,2,
d} {1, d} is permutation,
(24)
A (K) (I)
where P E pdxd is the orthogonal matria.

---

Published in Transactions on Machine Learning Research (07/2023)
Table 1: Quantitative results of the Roberta model fine-tuned on the GLUE dataset. MNLI is reported by the match/ match//issmtch splits. CoLA is reported by Matthews correlation coefficient. All the other tasks are measured by accuracy. The best result is highlighted with bold. means smaller is better. The experimental results are the average of five trials, and = represents the standard deviation.
Method
Loes
MNTT
QNLI
SST
SIAFCT
COLAT
STS-DT
Musec
6.35
76,37 0.84 76.41 0.85
28.26.200036
88.20 0.54
52:30 2 0.55
89.91 =: 1,00
70.36 0.00
2
RaPE
5:17
76.57 0.84/86.6
S1.0
83.38 1.28
55.98 0.55
00.65 1.22
70.10 1.006
30.23
49.58 0.45
SPE
6.07
PER
6.52
77:31 + 0.58/28.5
53.31+000
55.81
00.12 0.65
71.45 0.774
08.83++0:12
68.00 0.95
Typel
6.15
79.15 00.15:0.000/ 0.00 0:20
8Y.31 0.79
80-45 1.12
05.5=00.5
30..0 1.25
12.00:0..8.
18.36 0..71
61.922
Typel
6.12
80.30 = 0.99 80.88808888388 1.16
87.37
89:07 0.87
69.33 0.51
91.90 1.07
73.49 0.77
49.61 + 0.26
70.01 0.89
6.25
76.70
0.96
99.001 0.58
58.30
1.37
76.44 0.88
3.3 The LRPE family
LRPE (W, = P (P)))))) contains two components, d.e., a fixed unitary matrix and a unitary matrix 3.4,
and 3.5 The P can be seen as rotation matrix that rotates the token feature a particular coordinate system and the (x) derives the positional information from the rotated feature.
lamily ( as mentioned in Proposition 3.3
and 3.5 P needs to be an orthogonal matrix. We empirically find that when P is a householder matrix Golub & Van Loan 2013), the overall performance is better than other options such as permutation matrix and Identity matrix. We provide a detailed ablation in Table 5 For ease expression, we use Type for the unitary solution, Type 2 for the orthogonal solution, and Type 3 for the permutation solution. Details can be found in Appendix D.1
To meet all the requirements in Proposition 3.3
3.4
4 Experiments
In this section, we validate the effectiveness of the proposed LRPE on natural language processing tasks and computer vision tasks that resort to different Transformer architectures. Specifically, first study the autoregressive language model (Radford et al.) 2018). This is followed by the bidirectional language model, which adopts the Roberta. architecture (Liu et al.] 2020) and is pretrained and then fine-tuned on several downstream tasks from the GLUE benchmark (Wang et al. 2018). We also extend our evaluation on image classification task to verify the generalization ability of LRPE.
4.1 Experimental settings
Dataset We use Wikitext-103 Merity et al. (2016), Books Zhu al. (2015), and WikiBook Wettig et al.) (202)) datasets for NLP task evaluation and ImageNet-1k 1k Deng al. (2099) for image classification evalu- ation. Wikitext-103 is small dataset containing preprocessed version of the Wikipedia dataset. Books consists of a large number of novels, making it suitable for long sequence modeling evaluation. WikiBook is large corpus (22 GB) of Wikipedia articles and books collected by Wettig et al. (2022). ImageNet- 1k is the most popular large image classification dataset. It contains 1000 object classes and over 1 million training images and is often used to verify the performance of models in image modeling.
Configurations Our experiments are implemented in the Fairseq framework (Ott et al. 2019) and trained with V100 GPUs. All the methods share the same configurations such as learning rate, batch size, and optimizer. The detailed configurations are listed in Appendix
Competing methods Our baseline (marked as Base) is a Linear Transformer with 1 ++elu(-) Kat harhooop los et al. 2020 as the kernel function with sinusoidal positional encoding (Vaswani et al. 2017 For com- parison, we choose several statc-of-tho-art methods, ie., RoPE (Su ct al.) (021). SPE (Liutkus et al. 2021]. PermuteFormer (abbreviated as "PER") (Chen 2021). We also choose the method without positional encoding competitor (abbreviated 'NoPE').

---

Published in Transactions on Machine Learning Research (07 (07/202) /202)
37
28
36
RaPE
PER LRPE
PER
LRPE
34
20
33
18
31
30000
35000
40000
45000
50000
5000
7500
10000
12500
15000
17500 20000
22500
Step
Smp
Figure 2: The validation result of Autoregressive language model the Wikitext-103 dataset(left) and Roberta on the Wikibook drigset(right).. In both cases, the best result of the proposed LRPE has a better PPL and faster convergence speed than competing methods.
Quantitative results of the autoregressive language model on the WikiText-103 and Books dataset. The best result is highlighted with bold. means smaller is better. The experimental results are the average of five trials, and = represents the standard deviation.
Table 2:
Wikitext-
Books
Method
Vall
Test
Val.
Test
Base
33.97 + 0.19
13.67+0.11
9.13 0.05
8.79 0.02
NoPE
35.96 + 0.24
35.38 0.18
9.61 + 0.08
9.18 + 0.04
RoPE
33.36 + 0.20
33.15 +: 0.22
9.00 0.06
8.65 0.04
SPE
43.36 = 0.19
11.76
11.85 0.09
10.85 + 0.06
PER
32.88 + 0.09
82.51 + 0.25
8.53 0.04
8.21 + 0.07
Typel
31.83 0.08
31.60 0.19
8.50 = 0.03
8.18 0.06
Type2
32.02 + 0.15
0.24 31.74 0.24
8.48 + 0.03
8.14 + 0.05
Type3
33.81 + 0.21
33.85 + 0.18
8.66 0.05
8.43 1 0.05
4.2 Results
Autoregressive language model. The autoregressive language model has 6 decoder layers and is trained the WikiText-103 dataset (Merity et al. 2011)). In order to test the performance of the method on long se- quence modeling, we tested the performance of the model on the Books (Zhu et al.) 2015 dataset. We use the Perplexity (PPL) as the evaluation metric and report the results in Table 2 We observe that all variants of LRPE present performance gain over the bascline. Notably, Type and Type 2 models achiove the best per- formance on Wikitext-103 and Books, respectively, demonstrating superior capability language modeling. Bidirectional language model. The bidirec- tional model follows encoder-only structure, i.c., Roberta (Liu et al. 2020). with 12 layers. In order to verify the performance of the model on large data. set, we adopt the Wikibook dataset used by Wettig et al. (022)) for pre-training and used their config- urations to update 23k times. The results are Table and Figure 4.1 In the pro-training phase, LRPE outperforms all competitors. Next, we fine- tune the model for the GLUE task. As shown in Table [ our method outperforms competing meth- ods on all tasks with a clear margin.
Table 3: Quantitative results of image classification on the ImageNet-1k dataset. The best result. is high- lighted with bold. means larger is better. The ex- perimental results are the average of five trials, and + represents the standard deviation.
Method
Acc 78.04 1 0.15
Params
Base
22.04
RoPE
78.64 1 0.28
22.04
PER
77.81 + 0.23
22.04
Typel
78.60 0.28
22.05
Type2
78.77 0.21
22.05
Type3
77.72 + 0.18
22.05
Image classification model. To verify the ro-
bustness and effectiveness of LRPE under different modal tasks, we test our method on the computer vision domain. Specifically, we conduct experiments on Imagenet- 1k Deng et al. (2009) dataset using the Deit-small architecture Touvron et al. (2021) the image classification task. Tn particular, we replace the Attention
8

---

Published in Transactions on Machine Learning Research (07/2023)
with Linear Attention Katharopoulos et al. 2020) and then adopt various relative positional encoding. As shown in Table 3 LRPE beats all the competing methods.
Long-Range Arena. In order to validate the effectiveness of LRPE on long-sequence modeling tasks, we
conducted experiments on has positive effects on almost all tasks.
Arena benchmark TTay et al, 2020 As shown in Table LRPE
Table 4: Quantitative results of classification tasks the Long-Range Arena benchmark. The bost result is highlighted with bold. t means larger is better. The experimental results are the average of five trials, and
+ +A represents the standard deviation.
Model
Textf
ListOpst
Retrievalf
Pathfinderf
Imaget
AVG1
Base
60.10 + 0.37
39.22 + 0.24
84.96 0.58
71.34 + 0.32
41.15 + 0.17
60.39
RoPE
66.08 + 0.28
40.74 + 0.28
78.64 0.52
72.70 + 0.46
62.60 + 0.43
64.15
PER
65.52 = 0.43
39.14 + 0.11
83.33 0.45
69.50 = 0.40
42.05 = 0.27
59.91
Typel
66.75 0.35
39.98 + 0.12
82.31 0.67
74.20 0.40
63.53 0.46
65.35
Type2
66.43 + 0.62
39.63 + 0.29
81.83 0.34
73.48 = 0.33
62.39 + 0.34
64.75
Type3
65.01 1: 0.23
39.54 1 0.27
83.91 0.36
70.85 1 0.32
45.19 1 0.22
60.90
4.3 Discussion
An explanation LRPE. According to the discussion in Section. 3.3 The proposed LRPE rotates the token feature through P, and encodes the positional information through ( In Table 5 we ablate the effectiveness of the P matrix on the autoregressive language modoling task. Our approach with the House- holder matrix achieves better results than the one equipped with other metrics. It indicates that we can get better performance by carefully selecting the projection of the positional encoding.
Table Ablation results with different rotation matrix for language modeling on the WikiText-103 dataset.
(6)
Unitary
Orthogonal
Permutation
Avg.
Householder Identity
31.90
31.95
33.90
32.58
32.04
31.86
34.53
32.80
Permutation
32.09
31.59
34.16
32.61
Complexity and efficiency. The imple- mentation of the proposed LRPE does not af- fect the computational complexity of the linear transformer, f.e., preserving the linear complex- ity as On)). We also measure the training speed of the bidirectional language model on the same local machine and observe that the speed after using LRPE is only bit slower than the base- line on average. The detailed comparison of the
Table 6: Training speed of different methods on the bidirec- tional language model. The value standards for the speed relative to the basc method. t means larger is faster.
Method
Relative speed?
Base
1.00
Rope
0.86
SPE
0.61
PER
0.94
Typel
0.82
efficiency can be found in Table [ In general, LRPE does not incur significant computational burden to the transformer, and can fulfill the practical needs by maintaining comparable efficiency.
Type2
0.82
Type3
0.89
5 Conclusion
In this paper, we standardize the form of relative positional encoding for linear attention. The unitary transformation is employed as a special solution to the lincarized relative positional encoding, and the solutions as per various constraints constitute the unitary relative positional encoding (LRPE) family. We validate the effectiveness of LRPE through extensive experiments on both natural language processing and computer vision tasks with different transformer architectures. It outperforms competing methods in all tasks. In addition, it highlights a broad paradigm for formulating linear transformer-appleee positional encoding techniques that are more generically relative.
9

---

Published in Transactions on Machine Learning Research (07 2223))
References
Anurag Arnab, Mostafa Dehghani, Georg Heigold, Chen Sun, Mario Lučić, and Cordelia Schmid. Vivit: A video vision transformer. In Proceedings of the IEEE/CE CCVF International Conference on Computer Vision pp. 6836 6846, 2021.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Peng Chen. Permuteformer: Efficient. relative position encoding for long sequences. arv preprinl arXiv:2109.0255 2021.
Ta-Chung Chi, Ting-Han Fan, Peter Ramadge, and Alexander Rudnicky. KERPLE: Kernelized rela- tive positional embedding for length extrapolation. In Alice H. Oh, Alekh Agarwal, Danielle Bel- grave, and Kyunghyun Cho (eds.), Advonces in Neural Information Processing Systems, 2022. URL
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 TEEE conference on computer vision and paltern recognition, pp. 248-255. Teee, 2009.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidi- rectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Vol- ume (Tong and Short Papers), pp. 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 10118653/v/N191 1423. URL
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, Mostafa. Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gclly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 11929, 2020.
Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
Anmol Gulati, James Qin, Chung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, and Ruoming Pang. Conformer: Convolution-auugmeneee Transformer for Speech Recognition. In Proc. Interspeech 2020, pp. 5036-5040, 2020. doi: 10.21487/nnerssecch.000 wtw.eeecccch220311110
Max Horn, Kumar Shridhar, Elrich Groenewald, and Philipp FM Baumann. Translational equivariance in kernelizable attention. ar preprint arXiv:2102.07666 2021.
Weizhe Hua, Zihang Dai, Hanxiao Liu, and Quoe V Le. Transformer quality in linear time. arXiv preprint arXim:2202.1000 10447, 2022.
Zhiheng Huang, Davis Liang, Peng Xu, and Bing Xiang- Improve transformer models with better relative position embeddings. In Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 3327 3335, Online, November 2020. Association for Computational Linguistics. doi: 10.16653/v1/2020. findings- findings-emnll.22 emagp..9nl...99 298. URL https://accaattoooooooooo/////// org./0000 findings-emnlp
Shigeki Karita, Nclson Enrique Yalta Soplin, Shinji Watanabe, Mare Deleroix, Atsunori Ogawa, and Tomo- hiro Nakatani. Improving Transformer-Based End-to-End Speech Recognition with Connectionist Tempo- ral Classification and Language Model Integration. In Proc. Interspeech 2019, pp. 1408-1412, 1412, 2019. doi:
10.21 1.221437//nterspech.00111-
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rmns: Fast autorogressive transformers with lincar attention. In International Conference Machine Learning, pp. PMLR, 2020.
Guolin Ke, Di He, and Tie- Yan Liu. Rethinking positional encoding in language pre-training. In International Conference Learning Representations, 2021. httpp://ppppeeeeeeeeeeerrrrrrrra
10

---

Published in Transactions on Machine Learning Research (07/2023)
Tatiana Likhomanenko, Qiantong Xu, Gabriel Synnaeve, Ronan Collobert, and Alex Rogozhnikov. Cape: Encoding relative positions with continuous augmented positional embeddings. Advances in Neural Infor- mation Processing Systems, 34:16079 16092, 2021.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. ]o A robustly optimized {bert) pretraining approach, 2020.
URL https://openreviiet htt.:///ww...ooooooooooaaa////ad
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. In Proceedings of the IEER/CVP International Conference on Computer Vision, pp. 10012 10022, 2021.
Zexiang Liu, Dong Li, Kaiyue Lu, Zhen Qin, Weixuan Sun, Jiacheng Xu, and Yiran Zhong. Neural archi- tecture search on efficient transformers and beyond. arXiv preprinl arXiv:2207. 13955,, 2022.
Antoine Liutkus, Ondřej Cifka, Shil-Lun Wu, Umut Simsekli, Yi-Hsuan Yang, and Gael Richard. Relative positional encoding for transformers with linear complexity. In International Conference on Machine Learning, pp. 7067-7079. PMLR, 2021.
Kaiyue Lu, Zexiang Liu, Jianyuan Wang, Weixuan Sun, Zhen Qin, Dong Li, Xuyang Shen, Hui Deng, Xiaodong Han, Yuchao Dai, et al. Linear video transformer with feature fixation. arXiv preprint arXiv:2210.08100 2022.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models, 2016.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. 5th International Conference on Learning Representations, ICLR, Toulon, France, 2017.
Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: A fast, extensible toolkit for sequence modeling. arXiv preprint Xix::904400000 2019.
Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah Smith, and Lingpeng Kong. Ran- dom feature attention. In International Conference on Learning Representations, 2021. URL https:
//openreview.o wwwparrvveeenne/foorreoeee
Zhen Qin, Xiaodong Han, Weixuan Sun, Dongxu Li, Lingpeng Kong, Nick Barnes, and Yiran Zhong. The devil in linear transformer. In Proceedings of the 2022 Conference Empirical Methods in Natural Language Processing, pp. 7025-7041, Abu Dhabi, United Arab Emirates, December 2022a. Association for Computational Linguistics. URL htttp://acclanthollgg
emnlp-main. -aiinm-7mann473
Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan, Lingpeng Kong, and Yiran Zhong. cosformer: Rethinking softmax in attention. In International Conference on Learning Representations, 2022b. URL https:///pperreview www.:eee/fffoeeee attee/oorummm1--110000222000
Zhen Qin, Xiaodong Han, Weixuan Sun, Bowen He, Dong Li, Dongxu Li, Yuchao Dai, Lingpeng Kong, and Yiran Zhong. Tocplitz neural network for sequence modeling. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreviess mett/foorumidd==xxxeememam
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever, Improving languge understanding by generative pre-training. gegguaggeunauperriie////aaag hwwngguugeuudeerttttnnnnggggggee
pdf 2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog. 188):9, 2019.
Colin Raffel, Noam Shazcer, Adam Roberts, Katherine Lec, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Xixiv preprint or Xie: 10683, 2019.
11

---

Published in Transactions on Machine Learning Research (07/2023)
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Compula- tional Linguistics: Human Language Technologies, Volume 2 (Short Papers), pp. 464 468, New Orleans, Louisiana, June 2018. Association for Computational Linguistics. doi: (011663/v1/N155 2074. URL
Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rolary position embedding. arXiv preprint arXic:2104. 09864, 2021.
Sainbayar Sukhbaatar, Jason Weston, Rob Fergus, et al. End-to-end memory networks. Advances in newral information processing systems, 28, 2015.
Jingyu Sun, Guiping Zhong, Dinghao Zhou, Baoxiang Li, and Yiran Zhong. Locality matters: A locality- biased lincar attention for automatic speech recognition. arxiv preprint wrXiv:2203.1500 2022.
W. Sun, Z. Qin, H. Deng, J. Wang, Y. Zhang, K. Zhang, N. Barnes, S. Birchfield, L. Kong, and Y. Zhong, Vicinity vision transformer. IEEE Transactions on Pattern Analysis and Machine Intelligence, (01):1 14, jun 5555. ISSN 1939-3539. doi: 10.1109/TP.AA 2023 328.396556.
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient transformers. In International Conference on Learning Representations, 2020.
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Herve Je- gou. Training data-efficient image transformers &amp; distillation through attention. In International Conference on Machine Learning, volume 139, pp. 10347-10357, July 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informalion processing systems, 30, 2017.
Apoory Vyas, Angelos Katharopoulos, and François Fleuret. Fast transformers with clustered attention. Advances Neural Information Processing Systems, 33:21665-21674, 2020.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Glue: A multi- task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackborNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 353 355, 2018.
Alexander Wettig, Tianyu Gao, Zexuan Zhong, and Danqi Chen. Should you mask 15% in masked language modeling?, 2022.
Yunyang Xiong, Zhanpeng Zeng. Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmformer: A nyström-based algorithm for approximating self-attention. In AAAI, 2021.
Musheng Yao and Advanced Algebra. Advanced Algebra. Fudan University Press, 2015.
Qian Zhang, Han Lu, Hasim Sak, Anshuman Tripathi, Erik McDermott, Stephen Koo, and Shankar Kumar. Transformer transducer: A streamable speech recognition model with transformer encoders and rnn-t loss. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 7839-7833. IEEE, 2020.
Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. Aligning books and movies: Towards story-like visual explanations by watching movies and reading books. In The IEEE International Conference on Computer Vision (ICCV), December 2015.
12

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Appendix
A
Mathematical Notations
Notation
Meaning
X
Hidden state.
Q,K, V
Query, key, value.
Wo. Wx. Wv
Weight matrices for Q.K.V.
O m m. Φ
Attention output.
s-th row of matrix (real domain).
8-th of matrix M (complex domain).
Kernel function for linear attention. All-ones vector with dimention d.
1a
L block-diag
Identity matrix with dimention d. Combining matrices into larger
block diagonal matrices as in Eq. 25
Table 7: Mathematical notations used in the paper.
W1
W2
Block-diag[W. W,...., W.)
(25)
W
n
B Computation of Vanilla/Linear Attention
B.1 Basic Notations
Both vanilla and linear attention blocks involve three matrices, ie.. Q (Query), K (Key) and V (Value).
All them are linear projections of input E Caxd i.e.,
X =
E Raxd
x
q
x WW
Q
XW
nad
q
x W
(26)
k
x
K
=
XW K
E R Boxd
K
x JWK
vT
x Wyy
=
XW
[WW
where Wo. WK. Wy e Bddd
The vector form is organized as
9. WT WT Wox,, WT.,, WTx.
(27)
13

---

Published in Transactions on Machine Learning Research (07 (07/202) /203)
The attention output is
0
0
_aad
(28)
0
B.2 Vanilla Attention
In vanilla attention, the output is computed using the Softmax weighted sum, ie.,
0g Attention(a. K, V)
ast
exp ( vd)
(29)
Σ/ Fr=n exp (g.k//Vd))
Softmax QK" /Vd/V.
B.3 Linear Attention
The linear atlention is formulated as follows,
O, Lincar At K, V)
as
((q,) (T.))oll (qq)) (k:)) Ve
Σ
21=1 p(q.) J (kk,)
(30)
E ((q.)) (k(k))
( En (kk))
((g,)1 ) En ((k))
0 A ((Q))(K))V
A -1 (QQ))(()) VJ.
A diag( 1,)). 1.)))
C Proof of Theorem
C.1 More Examples
In the following, we provide two additional examples of relative positional encoding with the canonical form.
DeBERTa (Huang et al. 2020
fra(ge, k.) =g + k ((-)) 1
kt,
0 5 cc
(31)
g(x) = 2c - 2
x + others.
14

---

Published in Transactions on Machine Learning Research (07 (07/202) 2023)
The canonical form is
3,
1 9s, k( = k, (!!) i-s = IdN
La, w!2) (2) 1
q.¹ ys k
i-s [g(s--)
k kg(e= t)
(32)
columns
1 Ia, R((0) k.
(3) t-
[g(t-s) 8)
gg(t-s)
columns
RPR
Shaw et al. 2018
frel kt) = q, k: + C1-
Ct- -elip(t-s.k))
(33)
clip(ar, k) mmxx(-k; (k;
We E CA, - S
The canonical form
111 = 2,
(1) 9 q kj
k2 W (1) Ltt
(34)
q (2 9s. k(2)
Ia. W 1- d
Cl-s ci-s)
columns
cosFormer
QQin et al. 2022b
fre k.) q.t cos(a(t- 8)),
(35)
which indicates that the relative positional encoding effectively a coefficient term in the attention matrix, as such, it can be derived via a positional matrix primitive with the coefficients.
1, 9 9s, k()) = k., w = cos(a(t- - s))
(36)
C.2 Speed analysis
Proof of Lrpe speed. For this, we only need prove that the time complexity linear with respect to n. To this end, we first give basic notations follows,
q
Q
E cnxd K=
E Coxd V= =
E Caxd
H
kt
v!
(37)
(M1q1)" H1
(Miki)") H
Q
E C K k=
E Codd
(M,..))
[(M,k,)*
The time complexity of transforming Q,K K to Q,
K. is O(nd). The next step is to calculate the output, ie.,
0 Q(K Cnxd
0 A A-'OK">
(38)
= A -Q[K'V
A diag (Q)
Clearly, Eq. 38 a standard formulation for the linear attention with the time complexity as O(nd?) Combing it with the first step, have the total time complexity O(nd2), which is unchanged.
15

---

Published in Transactions on Machine Learning Research (07 (022))
C.3 Linearized Relative Positional Encoding
Before the proof, we first give the following theorems Yao Algebra 2015
Theorem C.1. If matrix We E Cdxd a unitary matrix, there erists another unitary matriz P Caxd such that
W p* AP,
A (es((eepii))....... exp(ifs))
(39)
8 -.
Theorem C.2. If matrir W Raxd is an orthogonal matrir, there erists another orthogonal matrix P E Rddd such that
PT AP,
A diag A...... Ari 1, .,,..,1,. 1}. cos Ok sin 0%
(40)
A
cos 0z n = 1....T.
sin 0
C.4 Unitary (Solution
Proof of Proposition 3.5
According to Theorem
C.1
we can assume that W, has the following form (P E
Cdxd is a unitary matrix),
W, p* A (8) P,
(41)
(5) diag (exp((e))(i)())). )...e))((((())))
Hence, Eq. 14
equivalent to
WHW, = Wi-s
AM PP" A' = (t-s0
pd ( A ( = p (t-elp
H
(42)
A H A (t-ss)
diag {s(08) - o( of."), ... 10 ) = diag {oo 50 ... -
In this case, 4k = 1,...,dd d, we have
@ e(()) = g(t-s) + 21T,, K 1 E Z.
(43)
Note that 2/T does not affect the result, we assume = 0, i.e.,
(00) o(.)) 00 (c--
(44)
Taking / = 8 1, we get
(0+1) 8(.) = (1)
(45)
(1)) = )Qg
(1) A s0ak
16

---

Published in Transactions on Machine Learning Research (07 (07/2023)
C.5
Orthogonal (Solution 2)
Proof of Proposition 3.4 According to Theorem C.2 Rdxd is an orthogonal matrix),
we can assure that Wa has the following form (P E
W. A 1
P,
(+))
4
B (+)
C(+)
A
A
E 2p222
(46)
A
B (+) Ig R
C($)
I, E R
A cos (())
sin ((a) cos 0
sin (()))
Hence, Eq.
14 is equivalent to
W.W, Wi-
PT ( PP A P OP
A A 10) -P'AAC-
A ( T A (1) = A(-)),
(47)
A
(1))
A (t-a)
B
B
((t-s)
C T
CC
C(C-s)
where
A ( A (9) A (1-s)
(+) B (((-s)
(48)
CO) C ((t-s).
For (+), considering the k-th component, we get
A (s)
A
A (*
cos o(0) sin o(()
][
cos (())
sin ((4)
sin ((2)
cos ((
sin 0
cos (i))
cos of cos (()
sin of
sin ((0) cos ((0) cos g(²) sin (())
sin ((0)
k cos (/)) + cos 8(.0 sin (())
cos B(2) cos 1)
& + sin 00 sin o(()
(49)
0(0)
sin ( 0(2))
sin (t) ((0)
0 ((
A (t-s)
k
cos (t=s)
sin 0(t-s)
sin 0
(s-))
cos of
17

---

Published in Transactions on Machine Learning Research (07 (022))
Hence, vk = 1....,d,, d, we have
- -00 - = 0 2kT, h E
(50)
Note that 21T does not affect the result, so assume 1 = 0, i.e.
h 0(0) (0
(51)
Taking s 1, we have
4 0% = 8
(52)
(()) $ & 80rk-
Next, for ((d,, the conclusion more obvious, i.e.,
B (+) ((t) I
=1
(53)
((==s)
Finally, for C(+), we have
C c(0) = (-I+)(-I,,)
I
(54)
# ((t-s),
In that case, must have 0.
C.6 Permutation
Prior to the proof, we first provide some relevant definitions and propositions. Definition C.3. Permutation x is bijection defined on the integer set:
T: (1,2,- ... d) + (1,2. ... .d.
(55)
Definition C.4. For matrir
m
m2
M
E R dxd
m. E BR.K k= 1.,...... I....,d,
(56)
M2 defined as
m (2)
M
(57)
Definition C.5. For identity matric Ia ddd and permutation n, we defone
A (I.)
(58)
For Ag, have the following important properties:
Lemma C.6. For permutation n, motriz M ddxd and As E Bdxd defined C.5 we have
M, A,M.
(59)
18

---

Published in Transactions on Machine Learning Research (07 (0722)23)
Proof. We first organize Ia Raxd in the following form, where e₁ E R k 1.... d represents the one-hot vector with the k-th element one, i.e.,
I
(60)
Notice that
MM
m
(61)
so we get
e [(1)
((2)
A
M
(((d)
cT
(0)
M
M
(62)
((d)
M
(())
(2)
(d)
M,
7
Theorem C.7. For Aş defined in C.5 we have:
Ag = AR.
(63)
Proof. We induction for the proof.
For k= 1, the conclusion is obvious. Now assuming that the conclusion holds for h = 1, when & = 8, we have
A = (Ia)
((I))a--1) 1
(64)
(As-1)x
(A )r-
The next step is to prove
(A (A/-1), )r = Ai = AAAT-1
(65)
The above conclusion follows from C.6
Theorem C.8. A E Baxd defined in C.5 are orthogonal matrices, i.c.,
A AT I
(66)
19

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Proof. We first prove that the conclusion holds for k 1:
c I(I)
(2))
A
[ex(1)
ex(2)
ex(d)]
x(d)
(67)
[A
(x) (())
8st:
A ld-
Since A is square matrix, we also have In general cases, we only use C.7 i.e.,
ATAi IIa
(68)
A = AR(AN)
A
AT A
(69)
= AT (AT)
La-
With the same proof, get
A.AA La-
(70)
Based on the above conclusions, we can prove Proposition 3.5 below.
Proof of Proposition 3.5 According to Theorem C.8 and the product of the orthogonal matrix is thogonal matrix, we can assume that We has the following form (P E ddxd is an orthogonal matrix),
ie.,
W = P A (
(71)
The next step is to verify that it satisfies Eq. 14 which follows Theorem C.7 and C.S
W.W. PT (T) AP
= =PAAO OP
= -PAG (A
-PTAG) (A Wy
(72)
-PTA -PAG
( (A
=PTA (t-S)
WW
20

---

Published in Transactions on Machine Learning Research (07 (07/202) 2023)
D Implementation
D.1 Theory
LRPE(W, = (P) contains two components, (.c. the fixed unitary matrix P and the unitary matrix
family ( mentioned in proposition 3.3 3.4 and 3.5 We first introduce the choice of matrices P/A (6),
and then illustrate some implementation tricks.
Choice of matrices
For matrix P, We list the species mentioned in the paper below:
Householder matrix: denoted as vector v E Rd i.e.
= -vv /vlv/vv
(73)
In our implementation, sample from standard normal distribution, and make it determin- istic.
Permutation matrix: formulated per the following permutation (inspired by Flash Hua et al. 2022)), ie.,
m2kk) (2k + = [d/2] + +1, 2k, 2h + 1 $ d.
(74)
Identity matrix.
For matrix family (d), we use the following settings:
For unitary (Solution 3.3 we use the same method in (Su et al. 2021 with initialized 10000-21/d and make it learnable.
For orthogonal (Solution 2) ized 100000002000 2t/d as in Suu et al. 2021 and make it learnable.
3.4
choose the dimension of identity submatrix 0 with initial-
Another notable version to choose the dimension of the identity submatrix 0 with initialized a; = 1200 as in (Su et al., 2021), and make it deterministic. When using this version along with the identity matrix, we can get RoPE (Su et al. 2021)
For permutation (Solution 3)
3.5 we randomily choose the permulation and make it deterministic.
Notice that when combing this method with identity matrix, we can get version of Permute- Former Chen
2021
Implementation tricks
According to the following facts, can simplify the computation, Le..
q W.H. = * "PP*A (
= (s)))) Pk,
(75)
= (A (A
Pk.).
Hence, in practice, we use W, A (8) instead of W, (+) to reduce the computational costs.
21

---

Published in Transactions on Machine Learning Research (07 (022))
D.2 Pseudocode
In this section, we provide pseudocodes for LRPE in Python:
import torch
import torch.n. nn as mn
import numpy np
class Lrpe Module))
def (self, core_matrix, p.matrix, nax_positions=512, @abedddng_ddim=6..
theta_typer "a"e"",,,"" Pheta_learnod-aalee, householder learned-False): (ereeoooldd_._errodPPaaa.l)))
self. cor.loorrriiiii core_ core_matrix self p_matrix = p_matrix
self, thettatyt_ypee theta_type type
self. taffttheta_lee learned
teat theta learned theta_learned
self. holff.husehooder__11 learned householder_leaat learned
Lambda matrix
if self. core matrix 1:
if self. theta Sheta_learned:
print ("Learn theta!") self. theta mn. Paramateee (10000 ** (-2 / embedding_dim torch.arange arange (embedding_dim // 2)) r1shape 1, -1))
else:
print (f""heta_tyy type (self, typee") elif self www.loorreertrteee = 2:
elif self.core_mattin == 3:
print ("Permtttttta))oon")
permutation self get_perautation (max_ (mariiiiiiimarpptpiiiiiioooo positiiossoo,, embedding_diz.
self Dolf.register_buffeee ("pertrrrperutaationn persutation)
elif self. cllf.core_matt matrix core_matrix 4:
Frint("Complex exp")
if self. theeaalleareee
print (antt"Leest ("Learn theta!")
self.thet theta mn. www.aaaaeeee10000 (10000 (-2 / embedding dim
forch.arange (embedding dim)) reshape 1, -1))
else:
print(f (fietaaTTeta_yypp {self wellftthetattppe theta_type)""
matrix
if self.p_mn p_mttrix == 1:
prin(((Innttity") elif self.p.matrix == 2:
print("Husshooddeer
if self. mnseehodder_leareed. print("lears ("learn householder!")
self.r v = nn. Parammeetr
embedding_dim, 1))
else:
Sorch.randn(( embedding.ding 1)
torch, norm(v)
@rint(""oussholl norm is ftorch. norm (v))
self.v Parameteer,,, requires_grad-Pales
elif self p_maarix =- 3:
print ('Fouuier))
elif self, aalf.p_matee natrix ==
print ("Oddddddedeee even")
22

---

Published in Transactions on Machine Learning Research (07 (07/2023)
seli.p p self get_p((
self. core transform = self. welf.eet_eooeeeee get_corre_tramsffrm ()
def fsel, x):
input shape: (b, 1, e), b stands for batch size, 1 stands for sequence length, stands for embedding dimension.
".
==sel. self.p(x)
self core, transffrr(m)
return x
def get_p(self):
if self P_ mataiix ==
def f(x):
return
elif self. faffpp_aarix
return self householder
elif self, Salf.p_aatrix
def f(x):
return torch. fft.ffttt,, norm="ortho")
return
elif self.p_matrix
return self.odd, weld_evve__errutattlle
def get_core transform(self):
if self. core watllooorerriitaaaee patrix == 1:
elif self.reflect = 2:
return colf.mix_reflesee
elif self. www.looreeaaaeeeeee core_matrix -- 3:
return self saff.do_peznnee pww.peeprrtttiion = 4:
elif self return self. colp.eommp
def get_perautation(ee1f,, max_ max_positione, (abbedding_dim)
permutation rarcherandperi (embedding dim) reshape (1, -1)
expanded [torch. arange (embedding, dim) unsqueeze(0) [0)]
for
range (angemmmx_ostttii
1):
previous expanded [-1]
current previous. peevious-gathe((11 gather(-1,
permutation)
expanded. (current)
expanded torch.stack stack (expande,, dim=1)
return expanded
def odd _od__even_peed (sl. x):
2k->k, 2k+1->d+x
x.shape[-1)
e 2
permutation torch. arange
index torch. arange(()
permutation[: :] index[::2] //
permutation[1:: = (index [ondex[1::22 1) // 2 + d
permutation permutation. to (x.device)
aggather-1,, permutation. expand_as (x))
return
23

---

Published in Transactions on Machine Learning Research (07 (073))
def do_ (s1e x):
b, 1, x. shape
xx..ather (-1, self, permutationI: :1, :1 exxeaaddddd.. as (x))
reflect x): b, 1, d x. shape
1 else return self transform(x, e)
=
def mix_ rex_reflect x):
b, 1, d shape assert d >- split // to even
%
+= return self. transform(x, (x, e)
tranfformsself, x, e): assert % 2 ==
b, 1, d shape
do identity transformation
x1 = x(:, e:]
do reflection
= x(:, :, :e]
if self. thetahetta___a telf,tthta__eareeee learned:
theta theta
else:
if self theta_httttpt type -- "a":
theta 10000 (-2
torch. (range // 2))
elif self. theta_ tape == "b":
theta np.pi / 2 / 1 / (e // 2) torch arange(1, e // 1)
elif telfatheta_tppe
== "c":
theta pp / 2 / / torch. arange // 2 1)
theta theta. (1, thetal, dim=-1) reshapee 1, e)
.t)
theta torch stacsssacc((hhttt
theta theta torch. (1) reahape -1, to(x)
(-q1, -q3), (q0, Q2) -> (-q1, q0, -q3, q2)
half strch.stack ((=x((( 1::2], x(..., ::2]], dim=-1) rwwhapeeeshseeeeee
x_ transform x * torch. coach.cosstheeee (theta)) x_half torch. (itch.)) merge if != d: x_transform torch. ([x_ transform, x1], dim=-1)
return x_ x_trameform
def cxmpleexexp(self,, x):
b, s.shep
if self, theta learned: tearede theta self. theta else:
if self theta type "a": theta 10000 ** (-2 / e torch. arange())) theta reshapee,
-i)xco().device
natrix = theta * torch arange (1) r1sshape -1, 1). 20.toxx.devick
24

---

Published in Transactions on Machine Learning Research (07/2023)
sin_cos torch. complex(torch. cos (matrix) torch. sin (matrix)) (x. device)
self element_wwiieteeeeeeeeeeeeeeeeee wise_complexe sin_cos)
return
def element cireet__vie__ommleeeeeee t1, t2):
return torch. complex(t1.rea) t2 real - t1. s1.imag t2.real)
t2. imag, t1 r1.real
* 22.imag + t1. t1.imag
householderrselff, x, eps=ie-6);
if self wwwshhhllerr_eeareeeeeeee
v self.v (torch.norm (self..v) epe)
else:
v self.v
(b, n, e), (1, e, -> (1, n, 1)
torch. matmulxx v)
(1, n, 1), (1, 1, -> (1, n, e) norch.matmu (y, v. transpose 2))
return x
E Configuration
Table 8: Detailed configurations used in our experiments. "Total batch size" means batch per gpu update_freee num gpus, "Attention dropout" is only used for vanilla attention. "ALM": autoregressive
Language Model. "BLM": bidirectional Language Model. "IM": Image Modeling.
ALM
BLM
IM
Data
WikiText- 103/B00l/o
Wikibook
ImageNet-Il 1k
Tokenizer method
BPE
BPE
Vocab size
267744/50265
50265
Encoder layers
12
12
Decoder layers
0
0
Hidden dimensions
512
768
384
Number of heads
12
6
FFN dimensions
2048
3072
1536
FFN activation function
Relu
Gelu
Gelu
Sequuce length
512
Total batch size
128
512
1600
Number of updates
50k updates
updates
300 epochs
Warmup steps Peak learning rate Learning rate scheduler Optimizer
4k steps
3k steps
20 epochs
5e-1
5e-1
5e-4
Inverse sqrt Adam
Polynomial decay
Cosine
Adam
Adamw
Adam
16-8
1c-6
1e-8
Adam (8,.3 32)
(0.9, 0.98)
(0.9, 0.98)
(0.9, 0.98)
Weight decay
0.01
0.01
0.05
25

---

Published in Transactions on Machine Learning Research (07/2023)
Table 9: Detailed configurations used in LRA experiments. 'BN' stands for batch normalization. All methods use the same configuration, except for relative positional encodings.
Task
Feature dim
Layer
Norm
Batch size
Epoch
Lr
Text
128
4
BN
256
32
0.001
ListOps
128
4
BN
256
40
0.0001
Retrieval
64
4
BN
64
20
0.001
Pathfinder
32
4
BN
128
200
0.0005
Image
100
12
BN
100
200
0.001
26


Reviews:
[{"review_id": "ERTumj6f5f", "reviewer": "Reviewer_cq1E", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The authors proposed a formulation of linear relative positional encoding that unifies the existing methods.\n- The proposed linear relative positional encoding performs consistently better than existing methods on a number of experiments.\n\nWeaknesses\n- The unified formulation of positional encoding is straightforward.\n- The formulation of the proposed linear relative positional encoding is hard to follow. It would be nice to have a clean formulation of the proposed encoding.\n- The proposed linear relative positional encoding reused the components proposed in previous methods such as (Su et al., 2021). A detailed comparison of the proposed encoding and existing formulations is necessary.\n- Not much details of the experiments are provided.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "\nThis paper proposes a canonical form of linear relative positional encoding and  a family of linear relative positional encoding algorithms via unitary transformation. With experiments, the authors compared the proposed family of linear relative position encoding with previous relative positional encoding methods on a number of tasks such as language modeling, text classification and image classification. The experiment results show that the proposed method is better than previous methods.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Are $\\hat{q}_s^{(2)}$ and $\\hat{k}_t^{(2)}$ vectors or matrices? According to the text, $\\hat{q}_s^{(1)}$ and $\\hat{q}_s^{(1)}$ are vectors. On the other hand, $I_d$ is an identity matrix.\n- Two propositions are named as “Proposition 3.2”, one in Section 3.2 and the other in Section 3.2.1.\n- In Figure 2, it is unclear which figure is for the result of Wikibook and which one is for Wikitext103.\n- Could you provide error bars to the results in Table 1-4?\n- (see some of the points in weaknesses.)\n", "broader_impact_concerns": "This paper is for a technical improvement of linear Transformer. There are no obvious ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dKZDshdJNZ", "reviewer": "Reviewer_nPXJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis work is well written and organized, demonstrating a clear and concise presentation of ideas. The motivation is clear and well established\nA notable strength of this work lies in the proposal of a comprehensive and versatile formulation. By introducing a general framework, the authors have adeptly covered a wide range of related works within their study. Mathematical undestanding has also been equipped for this framework.\nThe authors have conducted comprehensive experiments, and the resulting empirical evidence serves as a testament to the effectiveness of their proposed formulation.\n\nWeakness / Questions:\n\nThe inclusion of some more recent related works, such as 'Kernelized Relative Positional Embedding for Length Extrapolation,' would strengthen the comprehensiveness of the related works.\nWhile the formulation is good, my main concerns are on evaluations:\nThe authors are encouraged to explore the application of their proposed methodology to additional tasks, such as machine translation, in order to further validate the versatility and effectiveness of their approach.\nThe performance on GLUE exhibits a considerable decrease. I would suggest referring to https://huggingface.co/roberta-base as a valuable resource in this regard and double-check the fine-tuning setting of the experiments. The relatively significant gap of ten points below widely adopted benchmarks makes it challenging to ascertain the adequacy of the methods employed.\nLooking at Figure 2, it becomes apparent that the observed convergence speed does not exhibit any noticeable improvement. However, it is worth highlighting that only LRPE demonstrates a favorable initialization approach, resulting in a lower perplexity. Additionally, RoPE has two values around 48000 steps which is also very weird.\nIt is recommended to incorporate additional simple baselines, such as a variant that excludes the utilization of any positional encoding.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper delves into the investigation of principles and methodologies behind designing encoding techniques specifically tailored for linear transformers. The authors developed a family of linear relative positional encoding algorithms, employing unitary transformation. This approach establishes a framework for the development of innovative methods that preserve linear space-time complexity. Notably, the proposed method exhibits good performance in a range of tasks such as language modeling, text classification, and image classification.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the above comments. Basically a new set of set of experiments is required to better demonstrate the effectiveness of experiment. ", "broader_impact_concerns": "This work should be no significant broader impact concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "PE4o9Lg8uC", "reviewer": "Reviewer_uzZa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I would like to point out that I have reviewed this anonymous submission two times before for other journals/conferences. The paper is improved a lot and a lot of comments I had in past were incorporated including Long-Range Arena benchmark. \n\n**Strengths**\n- general form of positional embedding for linear transformers, which includes popular RoPE\n- diverse (images and text input data, different datasets) empirical results with justification that different variants of proposed general form can improve performance\n\n**Weaknesses**\n- I think deeper analysis on the long sequences can be done, though Long-Range Arena benchmark is provided (though PathFinder task is not provided for some reason). I would like to see comparison with prior works on Long-Range Arena benchmark too (at least copy from the prior work e.g. for PER where they report numbers). This is a minor concern which doesn't reflect my overall impression of the work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Positional embedding is a key for transformers especially in the light of generalization to longer sequences and learning long range dependencies. There were a lot of proposals in past years on positional embedding, however most of all relative positional embedding formulations (which are more powerful) are based on the attention modification which is not applicable / extendable to the linear transformers. Couples of works proposed new variants of relative positional embeddings to be applicable to linear transformers.\n\nThe  current paper makes a huge step further in developing relative positional embedding for linear transformers by formulating general property (unitary operator) for a positional matrix with which it is decomposed then into product of two matrices at different two positions. Thus, provided abstraction and unitary property allow to generalize many previous relative positional (e.g. RoPE, cosformer, learnable relative one, DeBERTA) embeddings in one simple yet effective form. Note, that for RoPE authors provide a more general formulation by adding additional unitary transformation on top of the positional matrix.\n\nFor the theoretical part authors provide general formulation and proof different forms of it including examples how existing positional embeddings are a particular cases. For the empirical part authors consider different benchmarks for linear transformer including Long-Range Arena, language modeling on WikiText-103/Books and image recognition with ImageNet-1k. In all these tasks with varying only positional embedding (the rest parameters stay the same) authors shows improvements on top of the baselines and prior works.\n\nOverall, community will benefit from the paper in different aspects:\n- general form of positional embedding which people can adapt depending on their task and prior inductive bias\n- math inspired formulation of positional embeddings which empirically works\n- well defined empirical setup and helpful observations across several domains\n- justification for RoPE (as prior work doesn't have enough and proper empirical evidence)", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Couple of questions:\n- Maybe I incorrect but could we include matrix $P$ into $W_q$ and $W_k$ learning matrices? Or decomposition that there is common component for both of them in the end make a difference? \n- For speech recognition there should be some earlier references to works where transformer were used successfully, e.g. check papers from Interspeech 2019 e.g. Conformer is way later paper on combination of convolutions and transformer. \n- What is configuration in Table 8 for Long-Range Arena benchmark?\n- What is the performance of vanilla transformer (not linear one)? do we match linear transformer with LRPE vs vanilla one with relative positional embedding?\n-  Do author use separate embeddings for x-axis and for y-axis for images and stack them as done for the baseline?\n- \"In our implementation, we sample v from a standard normal distribution, and make it deterministic.\" What do authors mean under \"make deterministic\"?\n- Typos:\n  - be consistent on \"twofold\" and \"three-fold\"\n  - \"indexes\" -> \"indices\"\n  - \"matrixs\" -> \"matrices\"\n  - \"in proposition\" -> \"in Proposition\"\n  - \"PermutateFormer\" it is actually \"PermuteFormer\"\n  - in Table 4.2 -> in Table 4\n  - \"production of the orthogonal matrix\" -> \"product ...\"\n- For Long-Range Arena couple of questions: I think it is worth to include SPE/PER numbers into Table 4; Why there is no Path Finder dataset test (any specific reason)? Any discussion around very low performance for the \"Base\" for image benchmark here? I see actually very high fluctuations for the \"Base\" among datasets if we compare with PER reported numbers in prior work (some in the current paper way better, some way worse) - any reason why?", "broader_impact_concerns": "It is theoretical / empirical work on improving transformer architecture which itself doesn't imply any ethical or other concerns, however could have an impact on large language models developments which can have negative effect on the society.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a formalism for positional embeddings in the case of linear transformers which achieve linear space-time complexity with respect to input sequence length, while maintaining comparable performance with vanilla transformer. The formalism encompasses the ROPE embeddings as a special case. Other variants of their positional embeddings outperform ROPE and other baselines (absolute, etc.). All reviewers were positive about the paper. Some concerns regarded results below SOTA for the tasks. Although performances reported here do not quite match SOTAs, the methods are well-compared against reasonable baselines and the paper deserves acceptance.

I suggest the authors to add to the final version of the paper the following suggestions as mentioned by reviewers:
- Add to Table 1-4 the fact that results are reported as mean across 5 trials. Add variance (or at least mention it in the caption).
- Add results on no positional embedding as it is quite interesting for the community.
Decision: Accept (poster)