Relative Positional Encoding Family via Unitary Transformation
Authors: Zhen Qin
Weixuan Sun
Kaiyue Lu
Hui Deng
Dongxu Li
XiaoDong Han
Yuchao Dai
Lingpeng Kong
Yiran Zhong
Venue: Submitted to ICLR 2023 (2023)
Keywords: Linear Transformer
Relative positional encoding
Unitary transformation

Abstract: Relative position encoding is widely used in vanilla and linear transformers to represent positional information. However, the 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 to design encoding methods suitable for linear transformers remain under-studied. In this work, we put together a variety of existing encoding methods under a canonical form and further propose a family of relative positional encodings 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. Equipping with different parameters, the proposed unitary relative positional encoding family (URPE) derives effective encoding for various applications. Experiments show that compared with existing encoding methods, unitary encoding achieves competitive performance on language modeling and various challenging downstream tasks, such as machine translation and text classification. In the meantime, it highlights a general paradigm to design broadly more relative positional encoding methods, applicable inclusively to linear and vanilla transformers.

Under review as a conference paper at ICLR 2023
RELATIVE POSITIONAL ENCODING FAMILY VIA UNITARY TRANSFORMATION
Anonymous authors Paper under double-blind review
ABSTRACT
Relative positional encoding is widely used in vanilla and linear transformers represent positional information. However, existing encoding methods of a vanilla transformer are not always directly applicable to linear transformer, because the latter requires a decomposition of the query and key representations into separate kernel functions. Nevertheless, principles to design encoding methods suitable for linear transformers remain under-studied. In this work, we put together a variety of existing encoding approaches under canonical form and further propose a family of relative positional encoding algorithms via unitary transformation. Our formulation leads to a principled framework that can be used to develop new rel- ative positional encoding methods that preserve the linear space-time complexity. Equipped with different parameters, the proposed linearized relative positional en- coding (LRPE) family derives effective encoding for various applications. Exper- iments show that compared with existing methods, LRPE achieves competitive performance on language modeling and various challenging downstream tasks, e.g., machine translation and text classification. In the meantime, it highlights a general paradigm to design broadly more relative positional encoding methods, applicable inclusively to linear and vanilla transformers.
INTRODUCTION
Transformers have achieved remarkable progress in natural language processing (Devlin et al. 2019 Radford et al. 2019: Brown al., 2020), computer vision (Dosovitskiy et al. 2020 Liu et al, Arnab et al. 2021) and audio processing GGulti et al. 2020). As an important ingredient in transformers, positional encoding assigns a unique representation for each position of token in sequence so that the transformers can sense the position of input tokens. Among these encoding
methods, absolute positional encoding (Vaswani et al., 2017 Sukhbaatar et al., 2015 Devlin et al.,
2019 Liu al. 2020) maps each individual position index into a continuous encoding. Whereas relative positional encoding (Shaw et al.] 2018 Su et al. [021 Horn et al. 2021 Liutkus et al. [021]
Huang al. 2020 Raffel et 20199 generates encoding for each query key pair, representing their
relative positional offset. We focus on relative positional encoding as they are not constrained by
lengths (Chen 2021 while showing superior performance (Shaw et al. 2018).
Linear transformers Chen (2021); Qin et al. (2022): Su et al. (2021) attract more attention recently they can achieve linear space-time complexity with respect 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 encoding methods are designed for vanilla transformers and are not directly applicable to linear transformers. The main cause behind this limitation is that linear transformers decompose key and value representations in the self-attention modules into separate kernel functions to achieve linear space-time complexity. Such an additional requirement on the decomposibility not always satisfied by existing relative positional encoding methods. On the other hand, despite some individ- ual works (Qin et al. [2022 Chen 2021), general principles to design relative positional encoding for linear transformers remain largely under-studied. A recent work, RoPE Su et al. (202 I) proposes new set of multiplicative encoding solutions based on rotate positional encoding and can be applied to linear transformers. In Section C.7
we show that RoPE can be seen as a special form of LRPE.

---

Under review as a conference paper at ICLR 2023
Softmax
d d
d d
d*
Wr-s
KT
Wr
Ws
KT
O(N'd + +rd)==)))==0)))))
O(ne + ndf )=
Figure I: 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 n input length and d is feature dimension. Tensors in the same dashed line box are associated for computation. In the vanilla relative positional encoding, query key attention has to be calculated first, leading to a quadratic complexity. W,-s refers relative positional encoding, where 4 two positional indices the query and key, respectively. Our LRPE achieves a decomposable encoding, i.e., We 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.
In this work, we aim to bridge this gap and study principal framework to develop relative positional encoding applicable for both linear and vanilla transformers. 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 primitives. By properly selecting and composing these primitives, we could derive various existing encoding meth-
ods for vanilla Vaswani et al. 2017 Huang et al. 2020 Shaw et al. 2018) and linear (Qin et al., 2022) transformers.
Taking advantage of the canonical form, we introduce the main contribution of our work, i.e., a special family of relative positional encoding methods called linearized relative positional encod- ing (LRPE). Specifically, we supply sufficient condition to design compatible encoding methods specially for linear transformers and prove that the linearized relative positional encoding unitary transformation. Benefits of using unitary transformation are two-fold. On one side, since it is de- rived from the decomposable positional matrix, can maintain the linear space-time complexity as shown in Fig. [1] Second, the property of the unitary transformation allows us to effectively derive the family of closed-form solutions. In particular, we show that number of encoding methods per- tain to the LRPE family, including those used in RoPE (Su et al. 2021 and PermuteFormer (Chen 202T.
Furthermore, LRPE sheds light on a simple yet flexible theoretical paradigm to develop new effec- tive relative positional encodings. 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 complex domains. Since unitary transformations are special cases of rela- tive positional matrix, LRPE are applicable in both linear and vanilla transformers, and exclusively suitable within encoder and/or decoder layers. We experimentally demonstrate the effectiveness of the LRPE family on autoregressive and bidirectional language modelling, and challenging downstream tasks, including machine translation and text classification. Results show that LRPE achieves competitive capability in representing relative positional information, commonly resulting in superior performance than previous encoding methods.
In summary, our main contributions are three-fold:
We present a canonical form of relative positional encoding, which derives most existing relative positional encoding methods as special case, including those used in linear and vanilla transformers.
Based on the canonical form, we propose linearized relative position encoding (LRPE), simple yet principal formulation to derive an encoding family that respect the linear space- time complexity in linear transformers, while being also applicable to vanilla transformers. We show several existing relative positional encoding methods in linear transformers are in LRPE family. We also provide additional particular solutions from this generic form. Experiments various downstream tasks, including language modeling, machine transla- tion and text classification show that the LRPE family show more robust and commonly superior results across tasks than previous relative encoding methods, are flexible in be-
2

---

Under review as a conference paper at ICLR 2023
ing plugged into linear/vanilla models, in encoder and/or decoder layers. 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 Le- We omit the subscript d when it is unambiguous from the context. The complete list of notations can be found in Appendix A
2.1 TRANSFORMER AND ITS I.NEARIZATION
We first briefly review vanilla transformer (Vaswani et al. 2017) and its linearization (Katharopoulos al., (020). 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 linear projection taking X e
gaxd as input:
Q XWQ. K = XWW, K, V XW E 1
(1)
The output E [Ra computed using the Softmax weighted sum:
O Softmax /vdvv.
(2)
The computation overhead of the vanilla transformer grows quadratically with respect to the se- quence length n, which becomes the bottleneck for transformers to handle long input sequences. Linearization of self-attention aims to reduce the computation complexity to linear (Katharopoulos et al. 2020 Ke et al. [202]] Qin et al.] [2022] Vyas al. 20200 Peng et al. [2021] Xiong al. 2021),
typically achieved via decomposable kernel function Φ Rd
Rd. Specifically, the output of
linear attention is computed as:
0 A ( (Q))o(()V]]
(3)
A diag( (Q) ((K)
The key property of linear attention is the decomposability of the kernel function. This enables to compute o(K) E Raxd first, which leads to the ((nd)) complexity, further reducing to ((n) with longer inputs (d & n). See Appendix B for detailed discussion.
2.2 POSITIONAL ENCODING
Self-attention 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.
Absolute positional encoding employs handcraft functions (Vaswani et al. 2017 Sukhbaatar et al.)
2015) or learnable encoding lookup tables P E Raadd (Devlin et al. 2019 Liu al. 2020) to represent position indices as encodings. These encodings are then combined with the context vector additively:
q We(x, + p.), (x + ps), Wv(x, + Ps).
where the encoding formulation only depends on the absolute position index s, and the positional encoding size is restricted by the input sequence length.
Relative positional encoding considers relative position offsets between two input tokens Shaw et al. 2018), i.e.,
est x WT W kx; Xx,
where s, are the two positional indexes, C2t denotes the attention score before softmax. Compared to absolute positional encoding, relative positional encoding generally achieves better performance as it can handle variable input length (Chen 2021). However, extra cost computation and memory makes it not so efficient than absolute positional encoding (Likhomanenko et al. 2021
Most existing relative positional encoding methods (Raffel al.) 2019 Shaw al. 2018 Huang
et al. 2020) require computing query-key attention QKT and combine with relative positional in- formation, which incurs quadratic complexity. In contrast, linear attention avoids such query-key product to achieve the linear complexity. Therefore, common relative positional encoding methods are usually not applicable linear transformers.
3

---

Under review as a conference paper at ICLR 2023
3 OUR METHOD
In this section, present main technical contribution lincarized relative positional encoding, which is an encoding family that preserve the linear space-time complexity. Specifically, we start by presenting canonical form of relative positional encoding, and show that existing encoding meth- ods can be derived by instantiating the canonical form with different choices of so-called primitive queries, keys and positional matrices Section 3.1 When imposing the decomposability constraint on this canonical form, we obtain a sufficient condition for linearized relative positional encoding (LRPE) and derive family of concrete solutions in real and complex domains in Section 3.2 We provide implementation sketch in Section 3.3
3.1 CANONICAL FORM RELATIVE POSITIONAL ENCODING
In order to better establish connections between existing relative positional encoding methods and understand their design principles, in this section, first present canonical form of relative po- sitional encoding. In particular, given query q. and key k, pair, their relative positional encoding frel: Cdd C can be represented as:
fral ko) = G W 1 R.
(6)
1=1
where represents conjugate transposition and m represents number of primitives. We refer (!) Cdf K E C4" w C4"xx4 xd6 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 reliance query embeddings, similarly for other primitives. For example, an identify matrix can also serve as primitives, as we will show shortly in Section 3.1.1
To demonstrate Eq. 6 is a generic formulation, we show that flexibly induces a wide range of existing relative encoding methods (Shaw al. 2018 [Su al. [2021] Horn et al. [021]] Liutkus jet al. 2021] Huang et al. 2020 Raffel et al.) (019)) by selecting and compositing different choices of primitives. Among them, highlight two examples in the following section, and leave the complete discussions in the Appendix
3.1.1 TYPICAL ENCODING EXAMPLES FROM THE CANONICAL FROM
Additive. In (Huang al. 2020), the relative positional encoding is formulated as an extra additive term to the query-key inner- product:
frei k.) = =9
q k; + Wt-s:
which can be derived by including an extra identity term as a primitive, formally denoted as:
m = 2,
c = q, k (1) = k,, (
i-s = Idz ( L2, k L2, w( W1-sLa.
(8)
Multiplicative. In RoPE (Su et al. 2021), the relative positional encoding works in the form of the weighted inner product:
fre(ge,, = W.
(9)
which can be denoted as:
m 1,
(10)
9.11 = qs k = k., (1)
t-s W,-..
4

---

Under review as a conference paper at ICLR 2023
3.1.2 SIMPLIFICATION
For the ease of remaining discussion, we introduce necessary notations and simplify Eq.
d = Σ
1 d2 = Σ
d2
1=1
1=1
(II)
q = [Go ..... ................................ W t- block-diag (W t-s...., wi C xd2
(q: (m)
| Ccd. ki Ccd,
[Kk(
..... (k,
E Cds
with these notations, we can rewrite Eq. 6 into the matrix form: fral k,) = W.WW.,kk Since every component of 9, and k, are handled with no difference, without losing generality, only discuss cases where m = 1:
(r k,) d.' W.
(12)
3.2 LINEARIZED RELATIVE POSITION ENCODING
Eq. 6 is a 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 transformers, the attention computation has to respect the decomposibilty condition. This additional condition leads to the linearized relative position encoding (LRPE) family, defined as follows.
Definition 3.1. A relative position encoding is called linearized relative position encoding (LRPE), when the following holds:
Vq,, ke E Cd. [r k.) 4, W.W.W.WW... W..kk (M.k.) -."M"
(13)
where qs kG E Cd,, W. E Cdxd, Wo = La-
The assumption of W, = I implies that the interaction between tokens from the same position only depends the content, which is reasonable enough that most encoding methods respect. In its essence, Eq. 13 ensures the positional matrix is decomposable. In this way, the query-key inner- product can be avoided in the attention computation. Consequently, complexity of computing LRPE ( where n is sequence length, 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. is equivalent to Eq. 14 and W, is Unitary matrix,
W W = W:
(14)
Proof of Proposition
3.2
According to the arbitrariness q. k, Eq. 13 equivalent
W M.
(15)
Take s = t in Eq 13 we get (since we assume that Wo I,):
M = W, =1--
(16)
Thus, M, is unitary matrix. On the other hand, note that for any unitary matrix P. we always have
W, M M.LM, MMP"PM, (PM,) (PM.).
(17)
This means that left multiplying M, by unitary matrix P does not change Eq. 13 Since M, and My are also unitary matrices, we can perform the following transformation:
M, MH.,
(18)
With M., Eq. 15 becomes
W M.
(19)
Take s = 0, we have
W, M M, MHMMM I,M, M.
(20)
5

---

Under review as a conference paper at ICLR 2023
Thus Eq. 19 becomes
Wi-- = W.
(21)
Since M, is unitary matrix, W, is also a unitary matrix, i.e.
W Ld-
(22)
The detailed proof can be found in Appendix 3.2 In the following section, we derive some particular solutions for Eq. 14
3.2.1
PARTICULAR SOLUTIONS
In this section, we discuss Eg. [4]and and give a family of solutions, It is worth noting that the solutions we provide are all the form W, = A where P, (+) are unitary matrix. The complete derivation be found in Appendix C.4 C.6
Table 1: LRPE variants. The rows of the table represent the type of the P matrix, and the columns represent the type the (+) matrix.
(+) type
Unitary (Solution 1)
Orthogonal (Solution 2)
Orthogonal learnable (Solution
Permutation (Solution 3)
P type
Householder
Typel
Type2
Type4
Householder learnable
Type3
Permutation
Type5
Type6
Type7
FFT
Type8
Unitary (Solution 1)
The first case discussed in the complex domain, which is not common in transformer models yet exhibiting an elegant solution.
Proposition 3.1. The following form of W Cdxd satisfies Eq. 14
W. pM A (
(23)
A ()) diag (x. exp(isaa))
where P [dxd is unitary matrix, oge, 1 = 1,....d are parameters.
Orthogonal (Solution 2) Now we consider the real domain, a more general case in transformers. Proposition 3.2. The following form of W. E RRdxd satisfies Eq. 14
(s)s
W, = A C
((*)
A
[cos(saa)
- -snn(sa)) )
A (+)
E Rpx22p ((a) = =I, E R9x9 A =
sin(saa)
cos(sar)
A (+)
(24)
where P pddd orthogonal matrix, ag, 1,... are parameters.
Permutation (Solution 3) The last case is inspired by PermuteFormer (Chen 2021 which is associated with the permutation matrix:
Proposition 3.3. The following form of We E Rdxd satisfies Eq. 14
W; = PT (1) P,
{1,2,
d) {1.2,
d) is permutation,
(25)
A (k) (I)
where P RRdxd is the orthogonal matrix.

---

Under review as a conference paper at ICLR 2023
3.3 THE LRPE FAMILY
LRPE (W, = PH A (4) P) contains two components, i.e., a fixed unitary matrix P and a unitary ma- trix family A (s) as mentioned in proposition 3.1 3.2 and The P can be seen as a rotation matrix that rotates the token feature to a particular coordinate system and the A (a) derives the positional information from the rotated feature.
In this paper, we select three types of commonly used orthogonal matrix, ie., (1) householder matrix (Golub & Van Loan 2013). (2) permutation matrix, and (3) FFT matrix (Bracewell & Bracewell] 1986). We combine the selected Matrix P with three LRPE solutions above to obtain practical LRPE types as shown in Table Detailed information be found in Appendix C.7
EXPERIMENTS
Table Quantitative results of the autoregressive language model on the WikiText- 103 dataset. The best result is highlighted with bold and the second best with underlined. J mcans smaller is better.
Linear attention
Vanilla attention
Method
PPL (val)
PPL (test)
PPL (val)
PPL (test)
Base
33.94 33.94
33.74
30.82
29.78
RoPE
33.40
33.13
30.13
29.31
SPE
43.50
41.91
32.99
32.26
Competitors
PER
32.86
32.53
32.21
31.95
30.70
29.74
XL
32.93
34.36
Typel 33.65
33.58
29.66
28.88 88.80
Type2
32.83
32.80
29.60
28.69
Householder
Type3
33.04
32.81
29.62
28.81
Type4
35.05
34.80
31,66
31.32
Type5
34.24
33.89
29.92
29.10
Permutation
Type6
33.13
33.05
29.83
28.87
Type7
34.07
33.87
31.96
31.37
FFT
Type8 36.78
36.31
29.85
28.96
Figure 2: Validation PPL of linear (left) and vanilla attention (right) of the bidirectional language model pretrained the WikiText- 103 dataset. In both cases, the best result of proposed LRPE has better PPL and faster converge speed than competing methads.
10.5
5.30
Base
Base
RePE
RoPE
SPE
SPE
LRPE
2aR PR2
LRPE
5.9
5.0
3.75
3.50
Valid
4.1
EXPERIMENTAL SETTINGS
Primary tasks. We validate the effectiveness of the proposed LRPE on various NLP tasks that resort to different Transformer architectures. Specifically, we first study the autoregressive language model (Radford et al. (018) with GPT-like decoder-only structure. This is followed by the bidirec- tional language model (encoder-only), which adopts the Roberta architecture (Liu al., 2020) and is pretrained and then fine-tuned on several downstream tasks from the GLUE benchmark (Wang al. 2018). Then, evaluate LRPE machine translation (encoder-decoder)
Competing methods. Our baseline is the Transformer model (Vaswani et al. 2017) without relative positional encoding. For comparison, also choose four state-of-the -ft--offfhhrrrrr art methods i.e., RoPE (Sul ct al. 2021), SPE (Liutkus et al.) 202I), PermutateFormec (abbreviated as "PER") (Chen (02T). T5 (Raffel al. 2019) and Transformer-XI. (Dai al. 2019) (abbreviated as "XI."), and test them in

---

Under review as a conference paper at ICLR 2023
both linear attention and vanilla attention. In the linear attention, employ 1 c+cl Katharopou- los et al. 2020) as the kernel function.
Training configuration. Our experiments implemented in the Fairseq framework (Ott et al. 2019 with V100 GPUs. All the methods share the same configurations which are listed in Appendix D.1
Table 3: Quantitative results of the Roberta model tinettuned on the GLUE dataset. MNLI is re- ported by the match/mismatch splits. All the downstream tasks are measured by the accuracy. The best result is highlighted with bold and the second with underlined. t means larger is better.
Attention
Method
MNLI
QNLI
QQP
SST-2
AVG1
Base
74.87/ 75.37
82.59
88.17
87.27
81.65
RoPE
67.13/67.69
79.97
85.11
78.21
77.61
SPE
67.07/68.51
74.79
71.43
78.67
72.99
Linear
PER
67.43/69.26
76.13
83.93
86.93
78.61
Type5
74.66/75.05
83.10
85,98
88.30
83.01
Base
79,37/19.07
87.79
88.33
90.25
86.44
RoPF
75.21/76.06
86,20
87.34
87.73
84.12
Vanilla
SPE
76.01/76.61
85.67
87.66
89.33
84.67
T5
77.83778.84
86.93
87.78
89.91
85.61
Type1
79.18/79.85
87.57
87.89
89.11
85.94
4.2 RESULTS IN LINEAR SETTING
Autoregressive language model. The autoregressive language model has 6 decoder layers and is trained on the WikiTexxt 103 dataset (Merity et al.) 2017). We use the Perplexity (PPL) as the evalu- ation metric and report the results in Table We observe that under the linear setting, most variants of LRPE present performance gain over the baseline. Our best model, i.e., Type2, outperforms RoPE and SPE on both validation and test to large margin, and achieves comparable results to PER with minor difference. Clearly, the proposed method is effective in encoding causal data.
Bidirectional language model. The bidirectional model follows an encoder-only structure, i.e. Roberta (Liu et al., 2020). with 12 layers. We first pretrain it on the WikiText-103 dataset, and present the results Fig. 2 and Appendix D.2 Generally, LRPE (Type2 in this case) has better performance, i.e., smaller validation PPL in all evaluation steps, than competing methods. Notably, surpasses RoPE, SPE and PER by nearly 10%, 27% and 37% in terms of the final PPL, indicating its superiority in bidirectional language modeling.
We then fine-tune the pretrained model on the GLUE dataset (Wang et al. 2018). We use different learning rates among le-5, 3e-5, 6e-5, le-4 and choosing the best result after fine-tuning for 3 epochs. From Table 3 we find that the two representative LRPE variants, ie., Type5, perform consistently better than other methods in all metrics. The average score of Type5 beats ROPE, SPE, and PER by more than 4.4%.
Machine translation. For this task, adopt the base transformer model which consists of en- coder layers and decoder layers, and train on the WMT 14 En-De dataset (Bojar et al.) 2014). We ran each experiment 5 times and report the averaged results. Note that in practical, embed the linear attention and its corresponding relative positional encoding in encoders, since we empirically find that the model cannot converge appropriately when the linear attention appears in decoders. We measure the accuracy with BLEU, and the quantitative results on both validation and test sets are displayed in Table 4 Most variants in the LRPE family have comparable perfor- mances to the competing methods on the validation set, and Type4 ranks first on the test data, which demonstrates again the validity of our LRPE.
only
However, few variants present less competitive results than the state-of-the-ars on the test data. Empirically, this caused by the relatively high sensitivity of parameter tuning on the machine translation performance while all listed methods share the identical parameter setting. We will concentrate on how to further improve their accuracy by specializing the parameters for each variant in the future work.
8

---

Under review as a conference paper at ICLR 2023
Table 4: Quantitative results of machine translation the WMT En-De dataset. Evaluation
metrics include the validation loss, validation BLEU (Papineni et al. 2002). and test Post 2018). The best result is highlighted with bold and the second with underlined. means
arger is better. +A means standard deviation.
Linear attention
Vanilla attention
Method
BLEU (val)²
BLEU (test)f
BLEU (valyf
BLEU (test)
Base
29.57
0.06
26.34 1.05
29.92 0.3
27.50 + 0.18
RoPE
29.60
0.04
26.32 + 0.36
30.09 + 0.06
27.25 + 0.39
Baselines
SPE
29.39 + 0.02
26.74 + 0.12
29.76 + 0.06
27.34 + 0.12
PER
29.84 0.04
27.47 = 0.1
29.73 0.08
27.19 + 0.30
T5
29.95 + 0.09
27.56 + 0.22
Type1
29.60 0.05
26.16 0.51
30.09 + 0.02
27.18 0.27
Type2
29.65
0.04
26.13 + 0.77
30.07 + 0.02
27.28 + 0.37
Houscholder
Type3
29.68 + 0.03
26.02 + 0.61
30.08 + 0.03
27.44 + 0.16
Type4
29.78 0.05
27.47 0.45
29.95 + 0.05
27.41 + 0.16
Type5
29.61
0.04
26.13 1.5
30.08 1 0.05
27.18 1 0.52
Permutation
Type6
29.71
0.04
26.13
1.16
30.09 1 0.02
27.39
Type7
29.82 - 0.03
27.45
0.12
29.96 - 0.03
27.21 = 0.28
FFT
Type8
30.10 + 0.06
27.46 + 0.22
Table 5: Ablation results with different rotation matrix P for language modeling on the WikiTText-
103 dataset.
Linear attention
Vanilla attention
Method
PPL (val)
PPL (test)
PPL (val)
PPL (test)
Householder
32.83
32.80
29.60
28.69
Permutation
33.13
33.05
29.83
28.87
Identity
34.09
33.70
30.05
29.24
4.3 MODEL ANALYSIS
An explanation of LRPE. According to the discussion in Section. 3.3 The LRPE rotates the token feature through P, and encodes the positional information through A In Table we ablate the effectiveness of the P matrix on the autoregressive language modeling task. Our approach with the Householder matrix and the Permutation matrix achieve marginally better results than the one without rotation (Identity matrix). indicates that we can get better performance by carefully selecting the projection of the positional encoding.
Complexity and efficiency. The implementation of the proposed LRPE does not affect the com- putational complexity of the linear transformer, i.e., preserving the linear complexity (nn). We also measure the training speed of the bidirectional language model on the same local machine (i.e., GeForce GTX 1060 card), and observe that the speed after using LRPE is only 9% slower than the baseline on average. The detailed comparison of the efficiency can be found in Appendix D.3 In general, UPRE does not incur significant computational burden the transformer, and can fulfill the practical needs by maintaining comparable efficiency.
Generalization to vanilla attention. Finally, we investigate the generalization LRPE towards the vanilla attention. The results are reported in Fig. [ Table and The conclusion is con- sistent with that of the linear setting, iee, improving the vanilla transformer baseline and achieving competitive performance to the competing methods. It indicates the good flexibility of LRPE as it can be seamlessly applied to any attention type.
CONCLUSION
In this paper, we standardize the form of relative positional encoding in both linear and vanilla transformers, and focus the case in the linear attention. The unitary transformation is employed as a special solution to the linearized relative positional encoding, and the solutions as per various constraints constitute the unitary relative positional encoding (LRPE) family. We validate the effec- tiveness of LRPE through extensive experiments on several NLP tasks with different transformer architectures. It outperforms state-of-the-art methods under both linear and vanilla settings.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Anurag Arnab, Mostafa Dehghani, Georg Heigold, Chen Sun, Mario Lučié, and Cordelia Schmid. Vivit: video vision transformer. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 6836-6846, 2021.
Ondrej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Leveling, Christof Monz, Pavel Pecina, Matt Post, Herve Saint-Amand, al. Findings of the 2014 workshop statistical machine translation. Proceedings of the ninth workshop on statistical machine translation, pp.
12-58, 2014.
Ronald Newbold Bracewell and Ronald N Bracewell. The Fourier transform and its applications, volume 31999. McGraw-hill New York, 1986.
Tom Brown, Benjamin Mann, Nick Ryder, Mclanie Subbiah, Jared D Kaplan, Pratulla Dhariwal, Arvind Nec- lakantan, Pranav Shyam, Girish Sastry, Amanda Askell, al. Language models few-shot learners. Advances neural information processing systems, 33:1877-1901, 2020.
Peng Chen. Permuteformer: Efficient relative position encoding for long sequences. arXiv preprint arXiv:2 2021.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc V Le, and Ruslan Salakhutdinov. Transformer- xl: Attentive language models beyond fixed-length context. arXiv preprint
2019.
Jacob Devlin, Ming-Wes Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. Proceedings of the 2019 Conference of the North American Chapter of the A Association for Computational Linguistics: Human Language Technologies, Volume / (Long and Short Pupers), pp. 4171-4188 Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 1419
org/N19-1423
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image worth 16x16 words:
Transformers for image recognition at scale. arXiv preprint arXiv:2010./ 1929, 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-angmeente Transformer for Speech Recognition. In Proc. Interspeech 2020, pp. 5036 5040, 2020. doi: 10.21437/mterspeechh 2020-3011 3015.
Max Horn, Kumar Shridhar, Elrich Groenewald, and Philipp FM Baumann. Translational equivariance in kernelizable attention. arXiv preprint arXiv:2102.07688 2021.
Weizhe Hua, Zihang Dai, Hanxiao Liu, and Quoe V Le. Transformer quality in linear time. arXiv preprint arXiv:2202. 10447, 2022.
Zhiheng Huang, Davis Liang. Peng Xu, Bing Xiang. Improve transformer models 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. (0.18653/v1/ 1/2020. findings-cmmlp.298 o
findings-es 1p 298
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers autoregressive transformers with lincar attention. International Conference on Machine Learning, pp. 5156-510 5165. PMLR, 2020.
Fast
Guolin Ke, Di He, and Tie-Yan Liu. Rethinking positional encoding in language pre-training. In Interna- tional Conference on Learning Representations, 2021. URL
1d=0y- 52
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 Syxtems, 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. Ro/hert)a: robustly optimized (bert) pretraining approach, 2020.
URL
net. Formmmi d=
10

---

Under review as a conference paper at ICLR 2023
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 IEEE/CVF Inter- national Conference on Computer Vision, pp.
2021.
Antoine Liutkus, Ondiejj Cifka, Shih-Lun Wu, Umut Simsekli, Yi-Hsuan Yang, and Gacl Richard. Relative po- sitional encoding for transformers with lincar complexity. International Conference on Machine Learning. pp. 7067-7079. PMLR, 2021.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. Sth International Conference on Learning Representations, ICLR, Toulon, France, 2017.
Myle Otl, 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 arXiv: 1904.01038, 2019.
Kishore Papineni, Salim Roukos, Todd Ward. and Wei-Jing Zhu. Bleu: method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pp. 31 1-318, 2002.
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:
/openreviee net. wttffoormmmmo////m d--rrummmiiuti... TTT.:/GGGGGTTTTVTTVVET. TKTdVFRRR
Matt Post. A call for clarity in reporting BLEU scores. In Proceedings of the Thind Conference on Machine Translation: Research Papers, pp. 186-191, Brussels, Belgium, October 2018. Association for Computa- tional Linguistics. doi:
18- 6919. URL/httss://ccaantta htt.acaannnhoooooy..oo...ooooo.l org//18 8 6319
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 Learning Representations, 2022. /ttLbttts///peeeeee/ee wwwp//eet//tnneeeeee XCQrx2Up4
Alec Radford, Karthik Narasimhan, Tim Salimans, and llya Sutskever. Improving language understanding by generative pre-training. https: west amazonaws..aoo.....oooo......... com/ openal a Ltwpeerrs_agggagguuuuueeue
understanding paper.
2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog. 1(8)99, 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv: 10683, 2019.
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 Computa- tional Linguistics: Human Language Technologies. Volume 2 (Short Papers), pp. 464-468, New Orleans, Louisiana, June 2018 Association for Computational Linguistics. doi: 10.1865331//118-00272 URL
Jianlin Su, Yu Lu. Shengfeng Pan, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. arXiv preprint arXiv:2104. 098.6, 2021.
Sainbayar Sukhbaatar, Jason Weston, Rob Fergus, al. End-to-end memory networks. Advances in neural information processing systems, 28, 2015.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Atlention is all you need. Advances neural information processing systems, 30, 2017.
Apoorv Vyas, Angelos Katharopoulos. and François Fleuret. Fast transformers with clustered attention. Ad- vances 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. Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 353-355, 2018.
Yunyang Xiong. Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmformer: nyström-basee based algorithm for approximating sclf-attention. In AAAI, 2021.
Musheng Yao and Advanced Algebra. Advanced Algebra. Fudan University Press, 2015.
11

---

Under review as a conference paper at ICLR 2023
Appendix
A
MATHEMATICAL NOTATIONS
Notation
Meaning
X
Hidden state.
Q.K,
Query, key. value.
We. W k.
Wv
Weight matrices for Q.K.V.
Attention output.
m
s-th row matrix M (real domain).
m
s-th row of matrix M (complex domain).
Kernel function for linear attention. All-ones vector with dimention d. Identity matrix with dimention d. Combining matrices into larger block diagonal matrices in Eq. 26
1a Ia block-diag
Table 6: Mathematical notations used in the paper.
Wi
W
2
block-diag (W,, W2,... W
(26)
W m
B COMPUTATION OF VANILLA/LINEAR ATTENTION
B. 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 X Caxd iee.
x
E R
x
[q
x x
Q=
XW Q
q
x [Wo
(27)
kT
x[W
K
XW
Roxd
kl
x [
vT
x Wy
-
XW
Budd
x
where Wo. WK. Wv Bddd
The vector form is organized as The attention output
q
W Wgx,kK k, W v. WTx..
(28)
[
0
E paxd
(29)
T
12

---

Under review as a conference paper at ICLR 2023
B.2 VANILLA ATTENTION
In vanilla attention, the output is computed using the Softmax weighted sum, i.e.
0g Attention qs, K, V)
V
exp 9 /t/ vd) V2
(30)
-r=1 exp lg.k/vv
n
Softmax QK! /vd/V.
B.3 LINEAR ATTENTION
The linear attention formulated as follows,
O2 LinearAutention(q.. K, V)
V
t=l
( (Kik)
Σ ((q.) To(k))
((q,)) (kk)),
(31)
E ((q,) (K(e))
)qg)) En o(k))v,
((q.)" Ei=ro(k) o(k))
0 A 8 (Q))(())
A [Q)[((()))
A diag (6(())(()))))))))) [Q) (
C PROOF OF THEOREM
C.I MORE EXAMPLES
In the following, we provide two additional examples of relative positional encoding with the canon- ical form.
RPR (Shaw et al. 2018):
frel kt) qikk + c Ct-s = Welip(t-s.k)
(32)
clip(r, k) = max m)n,
E Cd, -k < k.
The canonical form is
m = 2,
i q k; k, ((1) (1)
1-s = Las
(33)
a q.
(2) Il, W (2) 1
(2
i-8 7 [c--s Cr-o
columns
13

---

Under review as a conference paper at ICLR 2023
DeBERTa (Huang al. 2020
(ra kt) - =9, k; + +. k + qt 1o(t-o)
x -c
(34)
g(x)
2c
x cc
r + others.
The canonical form
3,
(1)
qs (1) = kt, W 1-8 Las
q q k
(2)
La w (2) 1
K ky(s-1) K kg(s-1) n))
d
(35)
d columns
Φ Ia, k(
kr, W L-
ag(t-a) s)
9ott-s)
columns
cosFormer
QQn et al. 2022):
(ra k,) 9 cos(a(t s)),
(36)
which indicates that the relative positional encoding effectively coefficient term in the attention matrix, as such, it can be derived via a positional matrix primitive with the coefficients.
m 1,
(37)
g 9s, K = kG w = cos(a(t- - sd
C.2 LINEARIZED RELATIVE POSITIONAL ENCODING
Proof of 3.2 For this, only need to prove that the time complexity is linear with respect n. To this end, we first give basic notations as follows,
qf
Q
Caxd K
:
@nndd
v=
E Cnxd
kH
vH
(38)
(Miqi)#
(Miki) H
Q
E k=
E Caxd
(M,gg)
(M,kn)
The time complexity of transforming output, i.e.,
Q, K. to Q K. is O(nd)). The next step is to calculate the
0 Q(K Caxd
O A A-'QK"V
(39)
= A - VQK"V,
A diag( QQ]
Clearly, Eq. 39 is standard formulation for the linear attention with the time complexity ((nd?) Combing it with the first step, we have the total time complexity as O(nd²), which is unchanged.
C.3 LINEARIZED RELATIVE POSITIONAL ENCODING
Before the proof, we first give the following theorems Yao & Algebra 2015
14

---

Under review as a conference paper at ICLR 2023
Theorem C.1. If matrix W Cd is unitary matrix, there exists another unitary matrix P Cdxd, such that
W A*АP,
A diagfexp (ixp(ex((i0))...... i0.).....................)...i exp(id.))
(40)
-.
Theorem C.2. Iamrrii W E Raxd is an orthogonal mulrix, there exists another orthogonal matrix P E Raxd, such that
W AP,
A diag 1,,..., Arj bril,... ...,,, ,.,,, 1},
(41)
[os 0g
sin 0x
A
kk 1....r. cos 0z
sin 0/
C.4 UNITARY (SOLUTION 1)
Proof of Proposition 3.7 According to Theorem C.I form (P E dxdd is unitary matrix),
we can assume that W, has the following
W, = A (,)
(42)
(*) diaggeep(( (exp((00)11))) )x
Hence, Eq.
14
equivalent to
W = WiS.
PMAGH PP" A = =P"A(tS) P.
PHA A 10)p A (t-olp
A A A0 A((ss))
diag - ((00) )
j(0 o diag {jg(( ( ....
50((-=))
(43)
In this case, 4k: 1,.... d, we have
(6))) =0 (1--s) + 2km, ko E Z.
(44)
Note that 2t does affect the result, so we can assume 0, i.e.
g()) g(() = (e-
(45)
Taking f + 1, we get
0 (( ((5) 0
(46)
((0) $0() (1) sOn.
15

---

Under review as a conference paper at ICLR 2023
C.5 ORTHOGONAL (SOLUTION 2)
Proof of Proposition 3.2 According to Theorem form (P E [Rdxd is orthogonal matrix),
C.2
we can assume that Wa has the following
W.
PT A
P,
A (+)
A (s)
(
C
A (8)
A
2p
(47)
An (x)
B I E R
C I, R
cos 0
sin (())
A (
sin 0%
cos g
Hence, Eq. 14 is equivalent to
W Wi-
(7) PP A == -PTAA--PP
( (0) P -P'AAL-
(x) A (t) = 11-s)
(48)
AG)
((
A (t-s)
B
B
B(t-a)
=
7
C
CC
C(C-s)
where
A (s)T A (9) = A (1-s)
( B ( ((-s)
(49)
(+) B (CC-s)
For A (+),
considering the k-th component, we get
(5)
(t)
(t-s)
cos ((a)
sin (s)
cos g(0)
sin (()
sin ((a)
sin (
cos
cos
cos ((a) cos (() sin 0
cos (1)
sin 0 g())
cos (!) cos g(+) sin g(1)
sin (()) cos + cos
sin 000
cos k
(s)
cos 00 + sin g: sin g()
(50)
cos (
((a)
( e(.))
sin
sin (
( 0(.))
A ()
cos 0 (t=
sin ((c
cos of (((-s)
sin A
Hence, Vk = 1, 1,.., d, we have
(()) ((.)) (((-5)
2km, k E Z.
(51)
16

---

Under review as a conference paper at ICLR 2023
Note that 2tv does not affect the result, assume i = 0, i.e.
% 0% 0% (t-5))
(52)
Taking t + 1, we have
0 (e+1) 0 0
(53)
()) a S00k
Next, for (ss), the conclusion is more obvious. i.e.,
( ( 1
= l
(54)
= B((-s)
Finally, for C(s), we have
CO c(1)
= (-I+))-I,)
I,
(55)
# (t-+))
In that case, we must have r O.
C.6 PERMUTATION (SOLUTION 3)
Prior to the proof, we first provide some relevant definitions and propositions. Definition C.3. Permutation a bijection defined on the integer set:
x: 21,2.-.. d} + 11,2, ........,,,,E dz,
(56)
Definition C.4. For matrix
mg
M
E R Rdd
ma E IR k -,,,,,.. .,....d,
(57)
m
M2 defined as
m ((2)
M
(58)
Definition C.5. For identity matrix I E Rx and permutation n, we define
A = (I)
(59)
For Ag, we have the following important properties:
Lemma C.6. For permulation n, matrix M E ddd and Ag E IRdxd defined in C.5
we have
M, = A,M.
(60)
Proof. We first organize I d in the following form, where es Rdd, k 1, ..... d represents the one-hot vector with the k-th element as one, i.e.,
I
(61)
17

---

Under review as a conference paper at ICLR 2023
Notice that
M
m
T
(62)
we get
a(1)
7(2)
A,M
M
(()))
cT
M
M
((2)
(63)
M
m(a)
(())
(d)
M
Theorem C.7. For Ag defined in C.5 have:
As Ak
(64)
Proof. We use induction for the proof.
For 1, the conclusion obvious. Now assuming that the conclusion holds for when k we have
A = (La)
((Ia)
(65)
(Aa-1)a
(A1-1) )z-
The next step is to prove
(A
)x = A A
(66)
The above conclusion follows from C.6
Theorem C.8. Ag E Rdxd defined in
C.5 are orthogonal matrices, i.e.,
A
AT Lt-
(67)
Proof. We first prove that the conclusion holds for k: = 1:
((1)
A
#22)
[ex(1)
eT(2)
ex(4]
(d))
(68)
A st
T (c)) ex(t)
dat.
A = la-
18

---

Under review as a conference paper at ICLR 2023
Since A1 is square matrix, also have
A1 = Ia.
(69)
general cases, we only use C.7 i.e.
A
AT
AF(AT)
AA (AT
(70)
=A
La-
With the same proof, we get
ALAx la-
(71)
Based on the above conclusions, we can prove Proposition 3.3
below.
Proof of Proposition 3.3 According to Theorem C.rorem/C.8aan and the production of the orthogonal matrix is an orthogonal matrix, we assume that We & has the following form (P E RRd is an orthogonal matrix), i.e.
Wg k
P A (M)
(72)
The next step is to verify that it satisfies Eq.
4 which follows Theorem C.7 and C.8.
W.w, = PT (3) PP P
P P P
P (P
=PT (A PP
(73)
-PTAO) A ( (A
APA
W.-
C.7 IMPLEMENTATION
LRPE(W, =PHA (+) A contains two components. i.e., the fixed unitary matrix P and the unitary matrix family A (s) mentioned in proposition 3.1 3.2 and 3.3 We first introduce the choice of matrices P/ (+), and then illustrate some implementation tricks.
Choice of matrices
For matrix P, we employ three types as follows,
Houscholder matrix: denoted as vector v E Rdd i.e.,
w W Ia
2vv /
(74)
In our implementation, we sample v from standard normal distribution, and make it deter- ministic or learnable.
Permutation matrix: formulated per the following permutation (inspired by Flash Hua
et al. 2022 ). i.e.,
(2k) = k. (2k + 1) [d/2] + 1,1 1,1 24, 2k + 1 d.
(75)
19

---

Under review as a conference paper at ICLR 2023
FFT matrix: matrix form of FFT (Fast Fourier Transform).
For matrix family A (+), we use the following settings:
For unitary (Solution 1) (3.I). we use the same method in (Su et al. 2021) with initialized ag 10000 2t/d and make it deterministic. Since this method involves complex numbers, we only the FFT matrix for the choice of P.
For orthogonal (Solution 2) (3.2), we test with two versions. In the first version, we set [d/2|, initialized o₂ 10000-2:/4 as in (Su et al. 202T) and make deterministie. In the second version, we choose the dimension of identity submatrix q with initialized a, 10000 22/d as in (Su et al. 202 and make learnable.
the dimension of the identity submatrix
Another notable version choose the dimension the identity submatrix & 0 with 2t/d
initialized a, 10000-2t/4 as in (Su et 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) terministic.
33.
we randomly choose the permutation and make it de-
Notice that when combing this method with identity matrix, can get version of PermutateFormer (Chen 2021).
Implementation tricks
According to the following facts, we can simplify the computation, i.e.,
q. Ww., = प. P** PPH A (k,
= - (8) Pk)
(76)
Pq. (1) Pk.).
Hence, in practice, we can use W, PP (s) (*) instead of W, (*)) to reduce the computa-
tional costs.
C.8 PSEUDOCODE
In this section, we provide pseudocodes for LRPE in Python:
import torch
import torch.nn as nn
import numpy as np
class Lrpe (on.Med
def innit_ core_matrix, p_matrix, max_positions=512,
embeddding_dim-768,, theta_type-""a,, "aamed=Faaaa)
super() init_()
self.core_matriae core matrix
celf.p_matris = matrix
self.theta_type theta_type
self.theta_learnet theta_learned self.householler_leemmm
musseholder_learneee
$ Lambda matrix
if self.core matrix == 1:
if welf.theta_leatee print ("Learn theta!")
self.theta = Paramttt (10000 ** (-2 / embedding_din
torch. (embedding_din, // 2) rrehappe (1, 1, -1))
else: print (f"/heta_type (self. t.thtta_ttttt
20

---

Under review as a conference paper at ICLR 2023
elif self. core matrix 2: print ("Mixed")
clif self.core_matan = 3:
print ("Pormutaat)))))
permutatiion = sewf. pew._ttattrttttiionnnn (max_ mmx_poositions, embedding_dis _iim)
httpggiistttrbuufffeeeeetrttteae elif self.core_matrix:
permutation)
4:
("Complx_ exp")
it self.theta_learned::
print ("Learn theta!")
self.theta Pn.aaaaeter (10000 (-2 / umbedding_dim
torch. (embeediiggdg) rresappe (1, 1, -1))
else: print (E"Theta type Seala,theta_typee
P matrix if sclf.p_matrix == 1:
print ("Identity) elif sclf.p_matrix 2: print ("Householder") if hels.houshholeer_eeann
("1earn househelder!")
self.v Parameett (torch. randn (1, embedding_das dim, 1]
else:
v torch. randn (1, embedding 1)
v v torch.norm(vv
print (f"loossehlldr norm is
self.v Parameter requires_graa-raal.. elif self.p_matrix
print ("Fourier") 3:
elif self.p_matrix == 4:
print ("Odd__on"))))
self.p = self self.get_p()
self.core_transfomm sel self. tef..eetcore_trrnsffrr
def forward (self, x):
"'
input shape: (b, 1, e), stands for batch size, 1 stands for sequence length, e stands for embedding dimension.
self.p(x)
x selff.core.transfommt return x
def get_ (se_)(s)))):
if half.p_matris def f(x): return X
return & elif self.p self.p_matrix 2: return self. householder elif self.p_matrix 3: def f(x):
return torch. fft. (x, norm="ortho")
return elif self-p_natrix return self.ode oalffoodd.ceen_permutaatt
def get get_ccre_trannee coor__transoom(se1555
if helf.corremmatris
return self.reflect
elit self. matrix == 2: return self.mix. reflect nelf.mixxreefect elif self.core matrix == 3:
21

---

Under review as a conference paper at ICLR 2023
return self.do permutation elif self.core_matrix 4:
return self.complox_ckg
def ret_permutationnsee (self, max_pesitions, enbedding_ _ddd):
permutation morchhrandped (embedding_dim) reshape (1, -1)
expanded atanch (embeddingg uussquezze (0)]
for in range (max poaxpoosiiions :) previcus expandedl-1]
current seeevoossggathee. (-1, permutation)
expanded appanded.appendcoee (curreet)
expanded corch.stace (expanded, dim=1)
return expanded
def odd even permutation (self, x)
2k-2k, 2k+1->d+k
c = x. s.shape [-1] á = // 2
permutation corch.arange (c)
index torch. aarch.arange(e (e)
permutation [:2] index[::2] // 2
permutation [1: - [1: - 1) // 2 d
permutation permutation. to (x. device)
x..aather(11, permutaticn expand as (x))
return x
def do_permutationnself,, x):
b, shape
x x=x.gather(-1y self. self.perrutationn1, :1, :] expendd as (x))
return X
def Peflect(self, x):
b, 1, d shapee e - if d $ 2 - 1 else d
return self.transform(x, e)
def mix reflect (self, x):
b, 1, = shape assert d >> i split
i to even if e 2: += 1
return self.trrasform(s, e)
def transiorm(self, x, e)
assert e ==
b, 1, d x.shape
do identity transformation
x1 - x[;, ;, e:]
# do reflection
x == xxx,,
:e]
if self.theta. learned:
theta telta
clsc:
if sclf.theta_tt == "a":
theta 10000 (-2 / torch.arange (e // 2))
elif self. type "b":
theta np.pi 2
(e // 2) torch e //
1)
elit self.theta type = "c": theta np.pi 2 corch.arange (1, // 1)
22

---

Under review as a conference paper at ICLR 2023
theta theta. theta.reshape (1, 1, -1) [x)
theta torch. stack ([theta, thetal, dim=-1) reshape 1, e)
theta theta torch. (1) reshape (1, -1, tx
f (-ql, -q3), (q0, q2) -> (-ql, q0, -93, 92)
half = torch.stack ([-x..... 1::2], x!...r ::2]],
dim=-1) rwwhapeehaaaaaeeee
x x_transform x torch.cos (theta) x_half torch. (theta)
merge
it e != d: x_transform torch.cat (Ix_ transtorm,, xil, dim=-1)
return x_transform
def complex exp (self, x):
b, shape self.theta_ techett__learedd learned:
theta self. clsc:
if sclf. type "a";
theta 10000 (-2 torch.arange (e))
theta theta reshape (1, 1, -1) (x.device)
matrix - theta *
(1). reshape -I, tx.to(x.dee) device)
sin
torch. complex (torch. cos (matrix), torch. sin (matrix)) tt (x. device) x wtt.:eeeeeetwwsseoommlplllll (8, sin_cos) return x
def element wise wwwe_wissweeeeeeeeeeeee (sel,, tl, t2):
return torch, complex * t2.real t1..tim.aaa.... * t2. imag,
tl.real * t2.imag tl.imag * t2.real)
def houscholder x, eps-lc-6);
self www.hhhhhlleerreereeeet
v self.v / (torch. (selfs).. eps)
else:
v self.v
(b, n, 8), (1, e, 1) (1, n, 1)
y torch. natmul (x, v)
# (1, n, 1), (1, 1, e) -> (1, n, e) torch. natcul (y, v.transpose (1, 2)
return x
2
D EXPERIMENT
D.I CONFIGURATION
We provide detailed data, model and training configurations in Table 7 For published datasets, WikiText-100 103 is obtained from mode-ooo- with Creative Commons Attribution Attribution-ShareAlle ShareAlike License. The GLUE dataset obtained from httpss//luebenccmarr.com The WMT' 14 EN-DE dataset is downloaded from https//wwww.saatm.orr//www/
Lkkteex--deeendeeey-lnnggggu www.uagg-mmoeeliggg--ee-o.-
D.2 RESULTS OF BIDIRECTIONAL LANGUAGE MODEL
We report the pretrained results of the bidirectional language model in Table 8 Our LRPE achieves competitive performance in both linear attention and vanilla attention. Notably, the UPPE variant U PRR ol h has the best quantitative results in all evaluation metrics.
23

---

Under review as a conference paper at ICLR 2023
Table 7: Detailed configurations used in experiments. "Total batch size" means batch-per.ae -ppu update_freq x num-gpus. "Attention dropout" is only used for vanilla atten-
tion. "ALM": autoregressive Language Model. "BLM": bidirectional Language Model. "MT":
Machine Translation.
AML
BLM
Data
WikiText--03
WikiText-
WMT14 EN-DE
Tokenizer method
BPE
BPE
BPE
Src Vocab size
267744
50265
40480
Tgt Vocab size
42720
Encoder layers
Decoder layers
0
6
Hidden dimensions
512
768
512
Number of heads
8
12
8
FFN dimensions
2048
3072
2048
FFN activation function
Relu
Gelu
Relu
Segence length
512
512
Total batch size
128
512
/
Max token per batch
/
4400
Number of updates
50k
50k
100k
Warmup steps
4k
3k
4k
Peak learning rate Learning rate scheduler
5e-4
5e-4
7e-4
Inverse sqrt
Polynomial decay
Inverse sqrt
Optimizer
Adam
Adam
Adam
Adam e
le-8
Ic-6
lc-8
Adam (81, .22)
(0.9, 0.98)
(0.9, 0.98)
(0.9, 0.98)
Weight decay
0.01
0.01
0
Gradient clipping
0.0(1.0 for Type8)
0
0
Hidden dropouut
0.1
0.1
0.1
Attention dropout
0.1
0
Table 8: Quantitative results of the Roberta model pretrained on the WikiText- 103 dataset. The best
result is highlighted with bold and the second with underlined. 4 means smaller is better.
Linear attention
Vanilla attention
Method
Loss (val)}
PPL (val))
Loss (val).
PPL (val))
Base
2.32
4.98
1.92
3.77
RoPE
2.21
4.64
1.85
3.60
Competitors
SPE
2.74
6.68
2.04
4.11
PER
2.54
5.81
T5
1.90
3.72
Typel
2.34
5.06
1.83
3.55
Type2
2.08
4.22
1.82
3.53
Householder
Type3
2.09
4.26
1.83
3.55
Type4
2.31
4.95
2.02
4.06
Type5
2.29
4.90
1.85
3.61
Permutation
Typeб
2.11
4.30
1.82
3.54
Type7
2.27
4.81
2.07
4.18
FFT
Type8
1.88
3.68
D.3 EFFICIENCY
We compare the training speed of LRPE with other methods in Table D.2 which indicates that our method maintains good efficiency without incurring too much computational burden.
24

---

Under review as a conference paper at ICLR 2023
Table 9: Training speed of different methods on the bidirectional language model. The value stan- dards for the speed relative to the base method. 1 means larger is faster.
Linear attention
Vanilla attention
Method
Relative speedt
Relative speedf
Base /Vaswani et al. 2017)
1.00
1.00
RoPF (Su et al. 2021)
0.95
0.97
SPE (Liutkus al. (2021)
0.42
0.41
PER (Chen, 2021
0.88
T3 (Rattel et al. 2019)
0.70
LRPE
0.91
0.93
25


Reviews:
[{"review_id": "wrzIUCdD89", "reviewer": "Reviewer_YduU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper focuses on the problem of designing relative positional encoding schemes that are compatible with linear transformer architectures. This problem attracted some research already, and the main idea of the paper is to express the problem in a general way, by putting some emphasis on the fact that linear complexity requires considering the relative weighting through its SVD. Doing so, they derive some variants, based on how they design the matrices involved. Performance is on par with other existing schemes, and a bit better sometimes.", "summary_of_the_review": "another paper on relative positional encoding with linear complexity, whose highlight is on the factorization of the relative attention weight through SVD. The paper provides good background, although could be a bit more objective since I believe that the proposed method it is almost equivalent to several other previously proposed ones,.\nAll in all, a good paper on a topic I'm interested in, with borderline+ contribution, but still a nice read.", "strength_and_weaknesses": "The paper provides a good overview (although a bit biased, since I believe that several previous works already highlighted the SVD thing). The proposed method makes sense, and I didn't check the implementation, but it is claimed that it will be made open.\nThen, experiments are fine, although I believe that:\n*  it would have been interesting to try everything with \"no positional encoding\". I indeed found out that it is quite common that PE is useless altogether for some tasks. \n* It is likely in my opinion that the other methods would probably have given better results if tuned. But it's ok I guess that using the default parameters for their implementations is fine.\n\nThe main weakness I can see is novelty. I am really not convinced that factorizing the relative weights through SVD and then designing some particular cases is so new. It is claimed that this method subsumes most state of the art (indeed it's the case, necessarily), but it would have been good to highlight in what sense. For instance, \"the method from [xxx] is equivalent to picking P as ... and \\Lambda as ...\". Another weakness is that computing time / memory usage is not reported very well.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "l_yHl9P-3y", "reviewer": "Reviewer_o67a", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Positional embedding is an important component of transformer to give position information and also provide better generalization and usage of longer context. Recently several papers attempted to resolve the problem of generalization to longer sequences as well as better designing relative positional embedding. The main issue was applicability to popular optimized linear attention as relative positional embedding is modifying attention and was not applicable. RoFormer was the first to formulate properly the problem with unitary transformation (by rotating on some angle) and propose multiplicative embedding to be applicable to linear attention. This paper continue this generalization: it formulates general property we need for linear attention from positional embedding and obtains generalization of RoFormer with unitary transformation and additional projection matrix. With that many relative positional embeddings can be reformulated in the proposed unification, many new designs are further proposed in the paper with different unitary and projection matrices. All of them are tested for language modeling, machine translation and downstream NLP tasks. In many cases different proposed embeddings improve results over the baselines and previously proposed relative positional embeddings.", "summary_of_the_review": "The paper proposes general formulation of relative positional embedding which is applicable to linear and vanilla transformer due to multiplicative nature. I like a lot math extension and general formulation of RoFormer with unitary operators which is done in the paper. Finally we have very fundamental (and correct from math point) definition of relative positional embedding (done with RoFormer too, but it is extended further). The paper gives overview of many embeddings which can be formulated in terms of the proposed definition. Authors study different variations of matrices which are used in the decomposition of the general relative positional embedding. However, from experiments on language modeling, machine translation and downstream performance on NPL tasks we can see that there is no one positional embedding from proposed formulation which performs the best among others in all tasks. Also there are weak experiments and justification in machine translation domain and NLP downstream tasks. Moreover I think the main key point of having some projection matrix is not studied well and its effect is not understood.\n\n**Update** After rebuttal and discussion: With additional experiments and ablations authors made the paper stronger on both technical and empirical sides. I change correctness evaluation from 2 to 4. I support acceptance of the paper, but keeping score of 6 as empirical results are not showing consistent improvement for one proposed embedding and there is no score of 7 :) . In this light I suggest to rephrase a bit the text to make it clear that the focus of the paper is the general framework itself and the theory under it, not one new embedding in particular to perform the best. Also I encourage authors to include all results from rebuttal period, including vision domain with ViT.", "strength_and_weaknesses": "**Strength**\n- general formulation of relative positional embedding for linear attention which can be used now for both linear and vanilla transformers (many proposed embedding can be rewritten in terms of the proposed general formulation)\n- nice simple math & extension of RoFormer\n- experiments with many variations of proposed general relative positional embedding for language models, machine translation and downstream NLP tasks.\n\n**Weaknesses** \n- Paper can be simplified to have only LRPE definition and inheriting the proper form with assumption $W_0=I_d$\n- Ablation on usage $P$ as identity to understand the effect of the extra linear transformation on top of the rotational operation. Why do we need $P$ matrix at all as in examples it is still unitary / orthogonal, why this decomposition into $P$ and $\\Lambda$ is helpful? There is one ablation in Table 5, but would be great to have more and see consistent picture here. Any analysis on understanding why we need $P$ would be very useful. What will happen if we learn this matrix for baselines too? \n- Results in Table 3 for vanilla transformer are not convincing. Seems we even don't need any relative information to perform the best.\n- Machine Translation experiments are weak. It is known that test and validation for WMT-14 En-De are not very well correlated, probably due to small data size. Here all results should be reported with statistical significance, otherwise it is too huge variation could be. I would suggest to redo experiments either with several seeds or for En-Fr which is larger and stable results are observed there. Improvements 0.05 authors reports here is out of statistical significance, so it should be ignored for now.\n- I think overall experimental outcomes shows that there is huge variability between embeddings and moreover there is no one formulation which behaves consistently better in all experiments over the baselines. In this case I am not sure how general formulation can be helpful from practical point. Yes, theoretical formulation and math behind is very cool, but it could be the case that it is not practical in the end and does not bring too much improvement (some negative result that original baselines are good enough). Maybe more broader experiments in other domains, like vision and speech could help to resolve this issue, but it is future work obviously.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PrLk7CUsB7E", "reviewer": "Reviewer_e2DD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposed to unify relative positional encoding methods by formulating them as a quadratic form and introduced a class of decomposable relative positional encoding that is equipable by linear attention.", "summary_of_the_review": "In summary, I think the unified view of relative positional encoding is interesting, but the results in the paper are not strong enough. Also, the baselines and reviews in the paper are not comprehensive enough.", "strength_and_weaknesses": "Strength:\n- The unified form of relative positional encoding is meaningful in the sense that this formulation makes things clear and helps to design new relative positional encoding schemes.\n- The examples in this paper provide a diverse view of how to design relative positional encoding and decomposable relative positional encodings.\nWeakness:\n- Though the paper is motivated by designing relative positional encoding for linear attention, the empirical performance on linear attention is rather weak. Meanwhile, the paper claims that the problem of adding relative positional encoding to linear attention is under-studied, which is not true even though the paper has cited some of the related work. Concretely, there exist several works studying this problem, including [1, 2, 3] where [2] has significantly better performance than the proposed method (e.g., GLUE). Also to study linear attention, it is important to report the running time, it would be great to add discussion on this (though I understand the additional overhead is small for the method proposed in this paper)\n- Some of the numbers of the baseline methods is too low. For, example, it is easy to reach 80+ on MNLI, 30- on Wikitext-103.\n\n[1] Relative Positional Encoding for Transformers with Linear Complexity\n[2] Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding\n[3] PermuteFormer: Efficient Relative Position Encoding for Long Sequences", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8C5JmdDPyon", "reviewer": "Reviewer_JvG7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This work proposes new variants of relative positional encoding (PE) that are applicable for linear transformers - relative PE with unitary transformation (URPE). The proposed URPE variants preserve a linear time-space complexity, and demonstrates a comparable performance against the standard/vanilla transformer, across tasks such as LM and MT.   ", "summary_of_the_review": "This work, proposes a new variant of relative positional encoding, that can achieve a complexity of O(n). The proposed approach can be applied both for linear and the vanilla transformers. The proposed approach, with a detailed theoretical background, shows comparable result with strong baseline and related work. Although, the presented result can be benefit from additional tasks such as summarization. ", "strength_and_weaknesses": "Strengths \n- Unlike recurrent networks, transformers are dependent on the PE for learning the sequential arrangement of the input representation. In the past, literature relied either on an absolute, learned/relative PE's. As an integral part of transformer, this work, provides a principled approach to simplify PE for linear computation.\n- In addition to a comparable result in a LM and MT tasks, the proposed URPE approaches preserves a linear (O(n)) compute complexity, with a relatively minor (9%) training speed delay.\n\nWeaknesses\n-  Despite the results for tasks the LM, MT, and text classification, the experimental setting is quite narrow. Given the depth of formalization of both the vanilla, linearized and the proposed URPE approaches, this work, can be benefited from more tasks and broad experimental settings. For instance, summarization, given longer sequence length input and document level MT can be a good starting point to further probe the complexity vs quality metrics. \n- Despite 8 variants of URPE (Table 1), this work, lacks a detailed comparison and analysis of each variants. Only performance difference for LM and MT tasks are provided.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject