FastRPB: a Scalable Relative Positional Encoding for Long Sequence Tasks
Authors: Maksim Zubkov
Daniil Gavrilov
Venue: ICLR 2022 Submitted (2022)
Keywords: transformer
linear transformer
long sequences
fast Fourier transform
positional encoding
long range arena

Abstract: Transformers achieve remarkable performance in various domains, including NLP, CV, audio processing, and graph analysis. However, they do not scale well on long sequence tasks due to their quadratic complexity w.r.t. the input’s length. Linear Transformers were proposed to address this limitation. However, these models have shown weaker performance on the long sequence tasks comparing to the original one. In this paper, we explore Linear Transformer models, rethinking their two core components. Firstly, we improved Linear Transformer with  $\textbf{S}$hift-$\textbf{I}$nvariant $\textbf{K}$ernel $\textbf{F}$unction $\textbf{SIKF}$, which achieve higher accuracy without loss in speed. Secondly, we introduce $\textbf{FastRPB}$ which stands for $\textbf{Fast}$ $\textbf{R}$elative $\textbf{P}$ositional $\textbf{B}$ias, which efficiently adds positional information to self-attention using Fast Fourier Transformation. FastRPB is independent of the self-attention mechanism and can be combined with an original self-attention and all its efficient variants. FastRPB has $\mathcal{O}(N\log{N})$ computational complexity, requiring $\mathcal{O}(N)$ memory w.r.t. input sequence length $N$. 

We compared introduced modifications with recent Linear Transformers in different settings: text classification, document retrieval, and image classification. Extensive experiments with FastRPB and SIKF demonstrate that our model significantly outperforms another efficient positional encodings method in accuracy, having up to x1.5 times higher speed and requiring up to x10 times less memory than the original Transformer. 

Under review as a conference paper at ICLR 2022
FASTRPB: A SCALABLE RELATIVE POSITIONAL EN- CODING FOR LONG SEQUENCE TASKS
Anonymous authors Paper under double-blind review
ABSTRACT
Transformers achieve remarkable performance in various domains, including NLP, CV, audio processing, and graph analysis. However, they do not scale well on long sequence tasks due to their quadratic complexity w.r.t. the input's length. Linear Transformers were proposed to address this limitation. However, these models have shown weaker performance on the long sequence tasks comparing to the original one. In this paper, explore Linear Transformer models, rethink- ing their two core components. Firstly, we improved Linear Transformer with Shift- Invar-anvarinnt Kernel Function SIKF, which achieve higher accuracy without loss in speed. Secondly, we introduce FastRPB which stands for Fast Relative Positional Bias, which efficiently adds positional information to self-attention us- ing Fast Fourier Transformation. FastRPB independent of the self-attention mechanism and can be combined with an original self-attention and all its ef- ficient variants. FastRPB has (NN log N) computational complexity, requiring (N) memory w.r.t. input sequence length N.
We compared introduced modifications with recent Linear Transformers in dif- ferent settings: text classification, document retrieval, and image classification. Extensive experiments with FastRPB and SIKF demonstrate that our model sig- nificantly outperforms another efficient positional encodings method in accuracy. having up to x x1.5 times higher speed and requiring up to x10 times less memory than the original Transformer.
INTRODUCTION
Transformer architecture (Vaswani et al., 2017) originally proposed for machine translation tasks has shown impressive results in a wide range of domains, including natural language processing, image recognition, audio captioning, graph analysis, and bioinformatics (Lin et al. 202I}. How- ever, in applications that require processing long sequences, the benefits of transformers accompanied by high consumption of computational and memory resources. The main bottleneck the transformer's core component, the self-attention mechanism. Self-attention computes similar- ity scores for all pairs of tokens in the input sequence, and therefore, it has a quadratic complexity (NN2) in computations and memory relative to the length of the input sequence N
often
Recently, several approaches have been introduced to reduce the computational complexity and memory footprint of self-attention. Some works utilize the sparsity of the attention map (Belt- agy et al., 2200), others express self-attention as a linear dot-product of kernel feature maps +()) Katharopoulos al. 2020), or utilize random feature vectors (Choromanski et al. 2020). Pro- posed approaches reduce the computational complexity to O(N One of the promising variants of a transformer is the Linear Transformer (Katharopoulos et al., 2020) since, along with linear com- plexity, it requires constant (11) memory in auto-regressive language modeling. Experiments with the long sequence benchmark Long Range Arena (LRA) (Ty et al. 2020 have indeed shown that
1 'The full complexity self-attention also depends on attention head size For the original self-attention, complexity is (N)
II contrast, for Linear Transformer (Katharopoulos ity of linear self-attention D²) long sentences, N assumed to be around thousands of tokens. Therefore, switching to linear self-attention appears beneficial.
2020 Choromanski al. 2020p, the complex-
In benchmark sequences ranging from 1K to 16K tokens

---

Under review as a conference paper at ICLR 2022
Vertcl coodrett
10
Ausigred weightt,
530
Lafos
65
4001
12
62
Relative distance between toikems,
Horizoncal coarsinare
Figure I: Learned weights w, assigned pair- wise distances between tokens in FastRPB ID for different text LRA tasks.
Figure 2: Learned FastRPB 2D weights assigned to distances from pixel (12. 10) to each other pixel MNIST 28 28 image classification.
the Linear Transformer is 5x times faster than the vanilla Transformer in training speed. However, the drawback of this architecture lower performance compared to the original Transformer.
One way reduce the performance gap between the Linear Transformer and the original one is to select a more suitable kernel function o(.) in linear attention (Choromanski et al. 2020 Schlag al. 202T). The poor performance of efficient transformers the model's ability to capture positional information. The original Transformer model utilizes only absolute positional information, which is added through positional embeddings contextual em- beddings of the tokens. Other approaches, which enrich self-attention with additional information about relative distances between tokens, have recently shown visible improvements in performance. Some of them directly add a matrix of relative distances to the attention map (Shaw et al. 2018),
LRA also be attributed to
others compute separate attention scores between positional embeddings (He al. 2020). We hy- pothesize that adding relative positional information could improve efficient transformers. However, most of the current implementations possess quadratic computational complexity, which neutralizes all efficiency of the Linear Transformer. To deal with this problem. linear complexity stochastic positional encoding (SPE) was proposed (Liutkus et al. 2021). Despite linear asymptotic, SPE re- mains relatively inefficient in training time due its stochastic nature, while the improvement in accuracy brings is relatively small on several LRA tasks.
The contribution of this paper is two-fold. At first, propose the Ihiff--Ivariant Kernel Function (SIKF). It could be used as a kernel for the Linear Transformer model and holds the shift-invariance property of softmax in the original attention. Second, propose Fast Relative Positional Bias (FastRPB) - Fast Fourier Transform-basee
bias for self-attention that represents relative posi- tional information within sequences, has O log N) complexity and requires only ((N) memory. FastRPB is orthogonal to the self-attention mechanism and can be combined with both efficient and original implementations.
We observed that SIKF is comparable to more complex kernels (Choromanski et al. 2020 Schlag al. (222)) while being as fast as the original one (Katharopoulos et al. 20200). We also evaluated FastRPB under different long-context scenarios, such as image classification and Long Range Arena tasks. Through comprehensive study, we showed that the proposed technique outperforms the prior fast positional encoding method (Liutkus et al., 2021) by significant margin without adding a substantial computational footprint.
RECENT WORKS
2.1 ATTENTION MECHANISM
The core component of Transformer Vaswani et al., 2017) is the attention layer, which computes attention weights Am, measuring how important the role of n-th key word is in shaping the mean- ing of m-th output word. Using A Am, we can construct attention matrix A MxN, and rewrite
2

---

Under review as a conference paper at ICLR 2022
Danr CRR ELUT
Lnee 2a01
Uner 23P9
Oegad Peitio
Unsor (D-FL) Foshin
100
Uiter 2001 nesting
Rutiora:: Earkes
Aul, Facoin
Fartrnar hothrr
800
Samp
1800
1503
2000
576
3024
1650
2304 2500
Num pixels
Num pixels
(a) Evaluation memory consumption.
(b) Evaluation time.
Figure 3: Evaluation time and memory for various type of transformer on Nvidia A100 with respect to number of pixels in the input image. For memory consumption y-axis is log-scaled.
the equation using matrix notation. The output of the attention layer Y is defined based three matrices Q E RR MXD
K E XD and V E NxD (Queries, Keys, and Values) as follows:
== AV = softmax (A)V = softmax(QK" (QK") /VDVV
(1)
In vanilla Transformer, the attention matrix A computed explicitly, which leads O(MND) complexity, and (MMN) memory to store the matrix
2.2 EFFICIENT ATTENTION MECHANISM
Linear Transformer variants Katharopoulos et al. reduce the complexity of attention from quadratic to linear using the associative property of matrix products and kernel reformulation attention.
2020 Choromanski et al. 2020) are way to
By substituting the softmax function in Equation
I we obtain m-th row ym of matrix Y:
En exp ohe ken DD En sim(q,, kn Unn Ym Σn exp( /n/ /DD
Σ, sim 9m, kn))
where exp(gT.k./v/ is generalized by any arbitrary defined similarity function sim k.)))
The core idea of Linear Transformer is to replace sim 9m k,) with a dot-product using kernel function di-) and then use associative property of matrix products as follows:
(im-
En plqm)) (kk,)) Φ(qm)) ) En ( )(qm) ) 1n0(kkk
Um En (lqm) (o(k))
(3)
Original attention has O(N2 D) time complexity, where N represents the sequence length, and ONN) for the memory footprint, while linear attention has time and memory complexity ONN D²), which scales linearly with sequence length N.
2.3 KERNEL FUNCTION VARIANTS
An open question is selecting an appropriate kernel function for Linear Transformer since different kernel functions dramatically affect trained model accuracy and speed.
ELU + 1. Originaly proposed kernel an element-wise ELU(-) + (Katharopoulos et al. 2020
((x) = ELU(x) + +1 { x + 1,
x > 0 (exp(x), < 0
(4)
The choice of ELU(-) + over ReLU(-) was prompted by its non-zero gradients for negative values.
'In case of self-attention, M equals to N, and thus the complexity is O(N2 D) and memory requirements ((2)).

---

Under review as a conference paper at ICLR 2022
Performer. The core idea is to approximate the softmax average using random features (Choro- manski et al. 2020p. The kernel function is evaluated as:
h():))
exp (Ræ) exp( exp(- RR))
1 ||/|| exp (-2
(<x) (x)
where h(xc) /2
(5)
vm
exp exp(R.x) RR exp(
Here
states for concatenation of vectors exp(Ræ) and exp( RRx) along feature di-
R.x:)
mension, each row I² of matrix R RRx is sampled from normal distribution (0 ID),
and dimension size R is a hyperparameter.
The main drawback of Performer is that sampling of matrix R requires extra computations and introduces variance into the model's output.
DPFP. Deterministic parameter- free projection is an alternative approach (Schlag al. 2021 The kernel function, designed to facilitate orthogonality in the projected space RP is described as:
Pin (x) = ReLU ([
ReLU ([=x
where @ RD + Da
(6)
140
here i- indicates the index of vector ((x), E {1, ... is an index and v E 21, hyperparameter, controlling the capacity of kernel function o(-). Linear Transformer with DPFP model outperforms model with default kernel and Performer, even if Drroj is relatively small.
Also, DPFP showed be faster than models utilizing random features, but still slightly slower than ELU +
2.4 POSITIONAL INFORMATION
Attention is permutation-ines invariannt,, which means that the attention layer does not make use of the order of the sequence. There exist different ways encode positional information in the attention:
Absolute Positional Encoding (APE) proposed original Transformer architecture uses real- valued vector p; E R.D assigned each positions i. Some approaches, such vanilla Trans- former Vaswwani et al. 2017). use predefined vectors, while others employ learnable vectors, e.g.
in BERT (Devlin al. 2018).
Relative Positional Encoding (RPE) is complement to the absolute positional encoding, which explicitly adds relative positional information between vectors (Shaw al. 2018 to the model. Raffel et al. (2019) proposed to directly embed positional information to the matrix A (see the Equation []. This approach was then improved by separating semantic correlation words and their positions correlation by Ke et al. 22220). The component Am, of matrix A then calculated as:
1 VD
Am,
I kn +
(UQPm))
VD
where Pr. and Pm are embeddings of corresponding positions n and m, and Uq. UK DxD are learnable projection matrices for the positional embedding.
By design, these approaches have quadratic computational complexity. Thus their usage with Linear Transformer is challenging since the naive application will neutralize all effectiveness of linear computation time.
Stochastic Positional Encoding (SPE) proposed by Liutkus et al. (2021) is, to the best of our knowledge, currently the only positional encoding method compatible with Linear Transformer variants due to its linear complexity. The key idea for SPE is to represent the attention relative distances matrix as covariance. Following the notation from equation we can express Am, as:
Am, amd Pa(m,n) n) Kn.d/ V.D where Pa(m, n) = E (qa(m)) [x(n))
(8)
here Qm,d and Kndd components of matrices Q and K respectively. (m(m) and ka(n) two real and zero-meat random variables such that their covariance function matches Pa- Varying the structure of matrices Pa authors designed two variants of SPE: sinSPE and convSPE. The first
4

---

Under review as a conference paper at ICLR 2022
Positional Encoding
None
FastRPB
sinSPE
conySPE
RPE
Original
OOM
0OM
OOM
0OM
OOM
Linear, DPFP
61.01 =
64.79 1.52
61.53 0.75
63.52 0.71
N/A
AAN
Linear, SIKF
0.3
67.19 e 1.64
62.0 0.36
58.93
1.65
N/A
Linear, ReLU
58.78
64.94 1.6
62.39 + 0.59
61.00 = 1.34
N/A
Performer
59.84 1.46
66.65 1 0.91
60.00 = 1.20
57.22
N/A
Original
14.43
14.6 + 4.14
OOM
ListOps
Linear, DPFP
20.67 3.99
17.97 11.68
17.57 = 0.18
N/A
Linear, SIKF
1..55
11.47
13.25 = 8.97
17.8 = 0.0
N/A
Linear, ReLU
17.58
0..57
17.80 =
9.50 1.17 17.80
N/A
Performer
17.80
17.39
17.43 + 0.32
N/A
Original
0.48
39.02
N/A
CIFAR
Linear, DPFP
41.96 0.27
0.009
41.97 = 1.24
41.33 = 0.84
N/A
Linear, SIKF
0.15
40.73 # 0.58
42.94 # 0.51
N/A
Linear, ReLU
42.25
4.121 08.4
39.96 1.31
N/A
Performer 41.81 + 1.16
3.556
1.70
40.06
N/A
Original
0.8
2.002
55.7 1.94
Linear, DPFP
6
62.76 6..62
62.78 0,48
N/A
Linear, SIKF
0.82
63.37 0.22
62.24 + 0,56
N/A
Linear, ReLU
58.78 + 0.93
0.166
62.39 + 0.59
61.00 # 1.34
N/A
Performer 59.84 1.46
62.66 0.11
60.00 1.20
57.22
N/A
Table 1: Experiments on Long Range Arena benchmark, the best model is boldface, double underline is top-2 result. Results for Performer and Linear Transformer (ReLU) copied from SPE (Liutkus et al. 202I), except experiments with FastRPB. We mark experiments that failed due to memory limitations OOM (Out of Memory). Since RPE is compatible only with the Original Transformer, we marked other experiments as Not Applicable (N/A). RPE is N/A for CIFAR since plain RPE is designed for 1D sequences. We marked experiments that too long to train as "L"
yields periodic covariance functions, which showed be beneficial in such tasks as music generation. The second utilizes vanishing covariance functions, a promising concept introduced in Wang et al. (2020), which yields notably smaller validation losses in some SPE experiments.
Although SPE was beneficial some music generation tasks, it still requires many computations due its stochastic nature. In practice, it could be dozens of times slower than the original Transformer, as we will show feather.
3 APPROACH
3.1 SHIFT-INVARIANT KERNEL FUNCTION (SIKF)
We hypothesize that the shift-invariance property of sofumax function (i.e., the fact that softmax; c) softmax,(2r), where is some vector, is constant, which is added to ery component of æ)) is an important property which makes original Transformer perform better than Linear Transformer with an arbitrary kernel. Based on this assumption, we propose SIKF as o(z) = exp (z), which satisfies the property of shift-invariance. If we substitute this function in the linear attention from Equation 3 then for every
constants e and we will get:
ó(am + C) 6k,, + d)vn ( )T Σn d Un ó(gm)) En ((kn) 5 (m(m)) ) En. (bkk)) (lgm)) ) En, Φ(ka)
(9)
6ggm + c)T Em Ck dd)
Thus, attention in Linear Transformer with exp(-) kernel function holds the same shift-invariance property as plain softmax.
Based experiments, conclude that SIKF is faster than Performer and DPFP, simultaneously has comparable accuracy, and does not provide an extra memory footprint, which is essential for scaling Linear Transformer extremely long sequences.
5

---

Under review as a conference paper at ICLR 2022
Model
w/o FastRPB
w/ FastRPB
Original
97.34 0.23
98.27 0.19
Linear, DPFP
9..99
97.66 0.22
Linear, SIKF
96.49 0.20
97.37 0.35
Lincar, ELU +1
94.01 + 0.31
96,71 + 0,40
Performer
96.6 0.29
97.52 0.26
Table MNIST F1 score. All the experiments run on Nvidia Tesla T4.
3.2 FAST RELATIVE POSITIONAL BIAS (FASTRPB)
Although adding positional information in the attention mechanism beneficial for model aceu- racy, current approaches are relatively inefficient in long sequences in terms of speed and memory footprint. In this context, there is a desire to design an approach that will add relative positional in- formation to attention efficiently and simultancously be compatible with various efficient attention modifications. To achieve this goal, we propose FastRPE as a separate term for attention.
More formally, output matrix Y of attention layer with FastRPB is defined as:
Y
AttentionVVriaan(( Q, K, V) WV
(10)
here matrix W E RRMX consists of learnable weights W Wm, representing relative distances be- tween m and n embedding vectors from matrix V. Note that Equation i0 is invariant choosing specific attention mechanism and could be used with both vanilla attention and its linear variants (Equations) Jespecccic)
One can think of the matrix W bias term to the usual attention matrix A from equation correcting the attention weights according to the relative distance between corresponding tokens. However, adding positional bias term in the Equation 10 requires O(N D) computations due to the matrix product and (N M) memory to store the bias matrix W In this regard, in the following two subsections, we will construct FastRPB positional bias terms matrices W1a and W24 for different types of sequences, that can be efficiently multiplied by V. Wi utilized in the case of ID sequences (e.g., natural language texts), and its coefficients will correspond to distances between words in ID sequences. For 2D sequences we will utilize W2a. which coefficients will represent distances between elements of 2D sequences (i.e., pixels). We will show that these specific matrices Wid and W2s could be multiplied with V using only O(DN log N) computations, and requiring only O(N) memory.
D.
Further, work with self-attention sequences lengths are the same, i.c. N = M. In the general case of attention, when we have an input sequence of length N and output sequence of length M, we can pad the longer one make the input and output lengths match.
variant of attention mechanism, where input and output
3.2. ID SEQUENCE CASE
Suppose have ID sequence with N tokens. In such sequence, there exactly 2N relative distances between tokens Let's assign a learnable parameter E R for each relative distance E {-N + +1, .... 1,,0, ... 1]. We then will obtain a of parameters:
{W-N+11 w-1, wo, W1, WN-1
(11)
Next we will construct matrix Wia using parameters [w:)WWl - (n, m)-th element of matrix Wia to be assigned to the relative distance between from withh token to
N+1 The basic intuition is to make
$ 'There was a desire to name FastRPB as FastRPE to represent that it is like a faster RPE. However, we change one letter to emphasize that FastRPB is orthogonal to the selection of an attention algorithm and could be seen as separate bias term to the attention map.
'O(N2 D) and ((N2) respectively in the case of self-attention "Relative distance from m-th token to n-th token is values, in this regard we have exactly 2N learnable parameters
which can have both positive and negative

---

Under review as a conference paper at ICLR 2022
n-th token, ie., Wm-n- Therefore matrix Wid will have the following structure:
W0
W2
WN-1
W-1
Wp
W1
WN-2
Wid
(12)
W--++1
W-N42
N-3
By definition, Wia is Toeplitz matrix (Gray 2001). A naive way to calculate product Wid V requires O(N computations case of sell aat--ttettion It turns out that it can be efficiently multiplied by matrix V according the following proposition:
For every Toeplitz matrix Wia E NNN for every matrix V RND matrix product Wid V requires ODD log N) operations and O(N) memory. Here N is length of the input sequence.
Proposition 3.1
Using proposition 3.1 we can claim that FastRPB for ID sequence will require O(DN log N) com- putational operations. Moreover, we only need (NV) memory for storing parameters {w,) i==-N+1 generating Toeplitz matrix WId- For the proof and a more detailed explanation of proposed proper- ties Appendix B.2
3.2.2 2D SEQUENCE CASE
In the case of 2D sequences (e.g., images), similar matrix to Wid could be defined. We will call this matrix W2,, and it will consist of learnable weights assigned pairwise distances from each pixel of the image to the rest of the pixels. Here we will consider only the case of square images of size N
The natural way to process images of the size N x N in the Transformer model is to flatten them into a vector of size N this regard, matrix pairwise distances W24 2d needs be of size N N2, For simplicity we will assume images to be presented a N x N matrix, and W2a will be expressed as tensor 22 of size (N x N) x (N x N), which (n, m, I, k) component represents distance from pixel (1, k:) pixel (n, m))
We will assume the distance between two pixels to be a sum of two distances: the vertical and horizontal 10 In this regard, tensor W2a be decomposed on vertical and horizontal tensor terms and Y, respectively, as W2a = X Y. Similar to the ID case, we will assign shared learnable parameters [w: -N=+ for horizontal and vertical distances. Then to compute a matrix product of tensor 22 of size N2 x N2 with matrix V of size N2 x D we will simply flatten tensors X and Y, and obtain matrices far and Yna of shape N2 x N and compute W28V X V- Yna
It turns out that the structure of matrices X flat and Yian is very similar to Toeplitz matrices from the Section 3.2.1 In this regard, W2a can be multiplied by V efficiently, according the following proposition:
Proposition 3.2 Product of matrix W2a E R with matrix V E NRD using matrices X and Yiu requires O(DN log N) and O(N) memory.
Using the above proposition 3.2 we conclude that FastRPB 2D will require O(DN log N) com- putational operations. Moreover, is not essential to store whole tensors X and Y to compute the product, we only need (NN) of memory for parameters [w;][N-1, generating this tensors. (See Appendix B.3 for the proof).
4 EXPERIMENTS
Long Range Arena. We evaluate proposed methods in the Long Range Arena (Tay et al. 2020). benchmark for efficient Transformers with several text and image long sequence tasks. The
Matrrx V has size N x D, where D is hidden size
'I we work with non-square images size N x M, we can simply pad them with zeros to make square. 19 we consider two pixels Pı (3, 2) and P2 = (0. 1) of image of size 4 x 4, the horizontal relative distance from pixel p2 to pixel P1 then will he 2 1, and the vertical will be

---

Under review as a conference paper at ICLR 2022
Training time (hours)
Peak Memory Usage (GB)
None
FastRPB
sinSPE
convSPE
RPE
None
FastRPB
sinSPE
conv
RPE
Original
0OM
OOM
OOM
0OM
OOM
5.81
6.03
9.69
Linear, DPFP
0.36
0.43
2.45
15.41
N/A
0.31
0.57
0.78
0.87
N/A
AAN
Linear, SIKF
0.36
0.45
1.22
9.12
N/A
0.31
0.57
0.78
0.83
N/A
Linear, ReLU
0.36
0.45
1.26
9.13
N/A
0.31
0.57
0.78
0.83
N/A
Performer
0.6
0.79
1.6
10.52
N/A
0.54
0.68
0.77
0.87
N/A
Original
0.74
0.85
OOM
3.25
3,49
3.66
ListOps
Linear, DPFP
0.26
0.36
2.3
13.8
N/A
0.68
0.85
1.32
1.33
N/A
Linear, SIKF
0.24
0.34
0.95
6.85
N/A
0.68
0.85
1.32
1.33
N/A
Linear, ReLU
0.24
0.34
0.98
6.87
N/A
0.68
0.85
1.32
1.33
N/A
Performer
0.38
0.48
1.06
8.7
N/A
0.67
0.9
1.03
1.32
N/A
Original
1.94
1.97
N/A
12.36
12.39
N/A
CIFAR
Linear, DPFP
1.94
1.97
2.07
2.44
N/A
12.36
12.39
12.57
12.58
N/A
Linear, SIKF
1.96
2.06
2.43
N/A
12.36
12.39
12.57
12.58
N/A
Linear, ReLU
1.94
1.97
2.06
2.44
N/A
12.36
12.39
12.57
12.58
N/A
Performer
1.94
1.96
2.07
2.44
N/A
12.36
T2.39
12.57
12.58
N/A
Original
1.81
2.24
6.58
0.52
0.52
0.78
Lincar, DPFP
1.48
1,58
4.25
13.56
N/A
0.23
0.23
0.33
0.43
N/A
Lincar, SIKF
1,56
1.62
3.52
9.85
N/A
0.23
0.23
0.33
0.43
N/A
Lincar, ReLU
1.46
1.62
3.54
9.85
N/A
0.23
0.23
0.33
0.43
N/A
Performer 1.93
2.38
5.81
40.09
N/A
0.33
0.41
0.33
0.47
N/A
Table 3: Benchmark results LRA with experiment setup proposed in SPE (Liutkus al. 202
All the above experiments were conducted using a single Nvidia A100 GPU. The best model boldface, the double underline is top-2 result, and the single underline is top-3 result. We mark experiments that failed due to limited memory as OOM (Out of Memory). We did not run Original Transformer with sinSPE and convSPE since they require too much time to train.
main challenge these tasks is dictated by the large sequence lengths, which average varies from 1K 16K toker"" In our experiments,
used the following tasks from this benchmark: (1) ListOps, which test if model is capable of parsing hierarchical expressions (Nangia & Bowman 2018: (2) TC, which consist of movie review sentiment analysis on the IMDB corpus (Maas al,, 2011: (3) All About NLP (AAN), which evaluates the model performance in matching and retrieval
tasks Radev et al. 2013); and (4) CIFARIO, image classification dataset (Krizhevsky 2009).
We compared Vanilla Transformer, Linear Transformer with all kernels observed in section 2.3 with SIKE, combined with different positional encodings, namely: sineSPE, convSPE, FastRPB. We also report results of experiments w/o adding any relative positional information. All models also used trainable Absolute Positional Encodings.
All experiments and hyperparameters were conducted following instructions for the LRA dataset. We also used LRA tasks to measure memory during the evaluation and computational footprints during the training.
Due to the fact that in LRA CIFARIO experiment only single layer transformer is used, we conducted another image recognition experiment with larger networks. We evaluated all the above models w/ and w/o FastRPB on classical image classification dataset MNIST (Lecun et al. 1998). In this experiment, observed in LRA, they require dozens of times more training time in experiments with multi-layer transformers with large size of hidden states.
MNIST.
did not compare FastPRE with other positional encoding methods since,
For all experiments, we used a model with 8 layers, 8 attention heads, a hidden size equal to 256, and batch equal to 160. We trained models using AdamW optimizer and made 20 runs Bayesian hyperparameter search to find the optimal learning rate and than trained all models for 25 epochs. Parameters are presented in Appendix We linearly decayed the learning rate during the training. Final results are averaged over T0 runs with different values of random seed.
11 We do not include another synthetic image classification task, Pathfinder, since were unable repro- duce the results, obtained in the original paper (Tay al. 2020
8

---

Under review as a conference paper at ICLR 2022
5 RESULTS
Long Range Arena. See Table 1 for the evaluation results. Linear Transformer with SIKF kernel comes out in the top two results for every dataset, except CIFARIO, which we will discuss separately. Memory footprint (see Table 3 of SIKF is indeed very tight the ReLU, DPFP, and Performer, while DPFP and Performer constantly performed slower (up to 1.4x times).
Linear Transformer equipped with FastRPB showed significantly higher results on ANN and TC both in memory, speed, and accuracy, achieving even better results than Original Transformer. More- over, architectures with FastRPB, confirming the above propositions 3.1 and 3.2 proved to have memory and computation consumption comparable with the default architectures. For the ListOps dataset, the best performance was obtained by the model without any relative positional encoding- We attribute this result to the fact that relative distances can be confusing in parse hierarchical struc- ture, such as expressions for ListOps or source code (e.g., the distance between IF and ELSE in source code can be pretty large, however, these statements are inwardly connected). We measured memory and computational footprint of models (see Table 3) according to which FastRPB requires up to 30x less time to train than conySPE, and up 3x less then sinSPE. Simultancously, FastRPB has 1.5x smaller memory footprint on evaluation then sinSPE and convSPE. Thus we conclude that FastRPB is the fastest and the most accurate method among others.
The learned weights of FastRPB for different text tasks sequence is presented in Figure ! where x--xxis represents relative distance m from n-th token to m-th token, and color denotes the value of (Wid)n.m = Wm-n- In the AAN task FastRPB forces the model to attend more to the very end of the text. Such observation can be attributed the fact that AAN mainly consists of scientific texts, which final part usually contains conclusion. As for ListOps, learned FastRPB weights are usually relatively small, which supports the hypothesis that relative positional encodings in such tasks should be designed using the text hierarchy information. In the TC task, learned weights mainly draw the model's 's focus forward and backward to enable the model to capture long- range dependencies.
In experiments with CIFAR, usage of FastRPB was shown to decrease the model's performance, and the best result was obtained with convSPE, which outperformed others by significant margin. We attributed this to the experiment setup, where single-layer network is utilized. In this regard, we conduct the experiments with a more extensive network on the MNIST dataset.
MNIST. In this task, each of the above models equipped with FastRPB showed superior perfor- mance (see Table 2), requiring quite a small amount of additional memory and computational time (see Figures 3a and 3b respectively). As can be observed from the plots, of Linear Transformer with FastRPB is up to 10x times less than the original ones. Moreover, in terms of speed Linear Transformer with FastRPB is 5x time faster in evaluation time compared original Transformer.
The detailed view of trained FastRPB could be found in Figure - where we learned slice (224)...2,10 which represents pairwise distances from pixel (12, 10) to every other pixel of 28 28 MNIST image. We observed that FastRPB enforced the model to look at more distinct pixels rather than to close ones.
6 CONCLUSION
We presented two novel approaches aimed increase the accuracy of the Linear Transformer model without additional memory footprint and significant loss in speed. Contribution is two-fold: we first make linear attention shift-invariance and then add bias term to attention scores, representing pairwise distances between tokens of the sequence. We computed this bias term efficiently and achieved (N log N) complexity and (NN) memory w.r.t. sequence length.
We demonstrate the superiority of approach among others using four long sequence tasks from the Long Range Arena benchmark and on the MNIST dataset. Our model performs significantly better than previous approaches, obtaining the best accuracy several tasks while being almost as efficient in terms of speed and memory as plain Linear Transformer.
We believe that the principles presented in this work serve basis for future research on the role of positional information encoding in transformer architectures. To this end, we open- open-source all the code and trained models.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Bassam Bamieh. Discovering transforms: A tutorial on circulant matrices, circular convolution, and the discrete fourier transform, 2020.
Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.0m 20t.:2000400055000 05/ 2020.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009.1477 14794, 2020.
Jacob Devlin, Ming- Ming-Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 2018.
Robert Gray. Toeplitz and circulant matrices: review. Foundations and Trends@ in Communica- tions and Information Theory, 2, 10 2001. doi: 10.1561/0100000006
Pengcheng He, Xiaodong I. Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhanced bert with disentangled attention. arXiv preprint arXiv:2006.0366 2020.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers mns: Fast autoregressive transformers with linear attention. In International Conference on Ma- chine Learning, pp. 5156-5165. PMLR, 2020.
Guolin Ke, Di He, and Tie- Yan Liu. Rethinking positional encoding in language pre-training, arXiv preprint arXiv:2006. /5595, 2020.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- based learning applied to document recog- nition. Proceedings of the IEEE, 86(1 86(11):2278-2324 1998. doi: 10. 109/5.72679)
Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu. A survey of transformers, 2021.
Antoine Liutkus, Ondfej Cifka, Shih-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.
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 142-150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URI http: 7/ 7/www. ac web. www.g//athhtiooooooooo htt.anoooooooo1111011111
Nikita Nangia and Samuel Bowman. Listops: diagnostic dataset for latent tree learning. arXiv preprint arXiv: 18888000602 2018.
Dragomir R Radev, Pradeep Muthukrishnan. Vahed Qazvinian, and Amjad Abu-Jbara. The acl anthology network corpus. Language Resources and Evaluation, 47(4))919-944, 2013.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yangi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv:1910.1066
2019.
Andreas Rosowski. On fast computation of a circulant matrix-vector product. arXiv preprint W.Xiv:2103.02605 2021.
Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear transformers are secretly fast weight memory systems. arXiv preprint arXiv:2102. 2021.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representa- tions. arXiv preprint 100.00/00 2018.
10

---

Under review as a conference paper at ICLR 2022
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: benchmark for efficient transformers. arXiv preprint arX1v:2011.04000 2020.
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 information processing systems, pp. 5998-6008, 2017.
Benyou Wang, Donghao Zhao, Christina I Lioma, Qiuchi Li, Peng Zhang, and Jakob Grue Simonsen. Encoding word order in complex embeddings, 2020.
A MNIST HYPERPARAMTERTS SEARCH
Model
w/o FastRPB
w/ FastRPB
Original
1.05 10
1.35 10
Linear, DPFP
1.3-
0.7 10
Linear, SIKF
1.25
1.45 10
Linear, ELU+
1.3 10
1.25 10
Performer
10-4
1.0 1.0-1044
Table 4: Best Learning Rate values obtained from 20 runs of Bayesian hyperparameters search
B PROPOSITION PROOFS
B.1 CIRCULANT MATRICES
To design more efficient positional encoding method, we leveraged circulant matrices - a subclass of matrices with some special properties due to their relation the Fast Fourier Transform (FFT) and circular convolution Bamieh (2020). Here we will only focus on the property that allows per- forming matrix-vector product fast and efficient in terms of speed and memory. Given vector (Co, ct.,,, Cn-1..,G-11) we will define the associated n x n circulant matrix C circ(c) which first column is exactly c, and each subsequent column is obtained by circular shift of the previous column:
co
Cn
Cn-2
C1
Cu
Cn-1
C2
C=
C2
C1
Cu
C3
(13)
Cn-1
CR-2
Cn-3
It can be shown that for every vector æ of size matrix-vector product C* requires only On log n) computation Rosowski (2021). Moreover, store the whole matrix C' in memory; it is enough to only keep in memory O(n) parameters of vector c. Further, will prove that FastRPB and FastRPB 2D can be expressed through circular matrices, and hence relative positional information can be embedded efficiently in the self-attention mechanism.
compute the above product, it is not necessary to
B.2 PROPOSITION
In 3.2.1 we introduced a Toeplitz matrix Wia of shape N x N:
u/p
W1
W12
WN
W-1
W/
W1
WN-2
W id
W-
W-1
W0
WN-3
(14)
-+1
W-N42
W-N+3
w0
11

---

Under review as a conference paper at ICLR 2022
AAN
Assigned weight, 177
0.04
0.02
0,00
0.00
Relative distance between tokens, i
(a) Learned in AAN task weights wy assigned pairwise distances between tokens i FastRPB ID.
ListOps
Assigned weight,
0.30
0000
-0.04
Relative distance between tokens, i
(b) Learned in ListOps task weights assigned to pairwise distances between tokens FastRPB
TC
Assigned weight,
00.0
0..00
0.01
Relative distance between tokens,
(c) Learned in TC task weights w; assigned to pairwise distances between tokens i in FastRPB ID.
12

---

Under review as a conference paper at ICLR 2022
Our goal is to efficiently multiply Wid by arbitrary matrix V of shape N D. As was stated in section Circulant matrices) special class of matrices, namely circulant matrices, can be multiplied by vector efficienlly in ( log N) operations and requires ((N) memory. We will extend ma- trix Wia with additional rows and columns and thus obtain circulant matrix Wid- Then we will introduce Veu, modified version of matrix V, which W will be multiplied by. Finally, will select a slice from the product W ld Vea, which will be exactly Wid" V.
The first step is define W.s.
w W-N+1
W-N+2
W0
W1
W2
WN-1
WN-1
W-N+1
W-1
W0
W1
WN-2
WN-2
WN-1
W-2
W-1
Wg
WN-3
W ld
(15)
W1
W2
W-N+1
W-N+2
W-1
Wo
N42
W-N43
WN-1
N+++1
As can be seen, constructed matrix Wed is indeed circulant. Moreover, the right upper comer ld of West is essentially W1d- Hence, Wid can be expressed as slice We following numpy notation: Wid (W12), NN-
:N-1'
Now we want to calculate matrix product Wia- V using matrix W ld of size (2N - 1) x (2N 1). Due to this fact will need multiply W with appropriate matrix Vest of size 2.V 1 D. Since, as we seen, Wid is a slice of W we only will need first N rows of the resulting product Wid Vau More formally we need to find such matrix Vea that: Wia V = (Wig V NN++ To achieve with will basically pad V with N additional rows filled with zeros follows:
0
0
0
Vext
(16)
V0,0
10,1
Wo,
01,0
01,1
01.D-1
UN-100
UN-1,
UN-1,D-1/
To complete the proof lets explicitly show that Wid (Wiy
Vol).
Lets assume
N+11
D 1, generalization for bigger dimensions can be done using similar operations:
W. N--N-1
WD
W1
WN
WN-1
W
Wg
WN-2
(Wot VXx) ld
WN
W1-2
W-1
WNN-3
0
(17)
00
01
W1
W-N+1
W-N+2
wo
UN-1
Wip
W
WN
Up
W-_1
W0
WN-2
U1
W-2
W1
WN-3
Wid V
(18)
UN-1
N41
W-N42
Wo
The last thing we have to do is to calculate the complexity of matrix product of circulant matrix
West with you Since matrix West is circulant of size (2N 1) x (2N 1), according to the
13

---

Under review as a conference paper at ICLR 2022
section Circulant matrices it requires O(N) memory to it, and O log. N) operations to perform a matrix- vector product with vector size 2N 1. In this regard to compute matrix product with matrix V of size N X D, will need to perform D times operations more, i.c. O(DN log N)
operations.
B.3 PROPOSITION 2
In the following sections, will be considering example of 3 x 3 image. In section Structure of pairwise distances tensors) we will study the general structure of tensors X and Y, which were introduced in section. In section Flattening of the tensors will reshape these tensors and obtain new pair of tensors Xtta and Yit. which will be then efficiently multiplied by V matrix in the final section Efficient matrix product
B.3.1 STRUCTURE OF PAIRWISE DISTANCES TENSORS
First of all, to gain deeper understanding of structure of tensors X and Y, we will explicitly write down components this tensors for an image of size 3 x 3. Consider X1. and Yi. which contains weights assigned to vertical and horizontal relative distances from pixel (1, 1) to all other pixels:
WW-1
W-1 W-1
W W0
X 11
Wp
We
Wo
YI,1. =
w-1
Wp
W1
(19)
W1
W1
W1
W--1
Wb
W1
One can observe, that X nnmmii and Y n.mmi have the property of symmetry, through which it can be proven that:
Proposition B.1 Xn....: Xn and Yina Yymaa for every n, E (o.... 1}. and this property holds for image of every size.
Taking advantage of the proposition B.I we can write out explicit form tensors X and Y in case of 3 3 images. We will introduce the following notation:
W-2
w-2
W-2
WW-1
w-1
w-1
(W
Wo
Wo
A =
B
wo
C
(20)
W0
Wo
w1
w1
W122
U/2
U22
It can be seen that different slices of tensor X can be expressed using matrices A, B
C:
Xo.o..: = Xo,1, = Xo,2,. = C
(21)
X1,0;; X1 X11 X1,2, B
(22)
X2.0.: = X2,1, = X2,2 = A
(23)
Moreover, matrices A, B, C also applicable for tensor Y:
You..: YU,1.:: Yu,..:. C
(24)
Y1,..:: VI.... V12... B
(25)
Y2,0.:: Y2,1.. Y2,2.. A
(26)
B.3.2 FLATTENING OF THE TENSORS
In transformer architecture before processing the image of size N N, it is usually flattened into 1-dimensional vector of size N2. To define flatten operation, consider an arbitrary matrix M of shape 3, than its flattened version maa will have the following structure:
Mo.0
m
mp.2
110,0
m1.0
flattening
M
11,00
77111
11.12
Maa
m8.11
(27)
172,00
m2,1
22.2
M1,2
m2,00
72,1
m2,2
14

---

Under review as a conference paper at ICLR 2022
Due to the flatten of images in transformer, matrix V in will have shape N2 D and hence it is essential to reshape tensors X and Y from size (N x N) x (N x N) to size N x N We will denoted reshaped versions of tensors X and Y as X and fla respectively. Reshaping of the above tensors can be decomposed into two consecutive flatten operations firstly applied to last two dims of tensors X and Y and then to the first two ones. Flattening of the last dimensions is equivalent to flattening of each of the matrix A, B, C, after this operation in case of 3 x images we will obtain the following three vectors:
W0
W
W0
Wo
Wo
W
10
W1
W/
W1
bust
W0
Citat
1
(28)
W1
Wg
W2
W1
100
U2
W1
W0g
112
w00
Than after next flattening operation we will get:
Wo
W0
Wp
W1
W1
W1
W22
W02
Wo
Wo
W0
W1
W1
W1
W2
W22
002
Wo
Wo
W0
W1
001
112
102
102
W!
W0
Wg
W70
W1
W0
001
X Xreehhpee (N2 N22)
w
W
W0
W0
170
W/1
(29)
W
10 1
W 1
WO
W0
W0
W1
W1
00
W-
2
10 2
W 1
W 1
W-11 1
W0
W-
-1-2
011
01 1
W 1
W 1
W/p
10g
16g
10
01 2
01
00
W 1
W70
000
(60)
W0
W1
112
W/
W1
W2
W/p
W/1
0/2
10g
W1
W/o
W1
W-_1
W0
W1
W
W
W
W
WD
W-
W
100
100
011
W2
W0
W1
W12
Wg
W1
102
Yıu = Yreehhape(N22 222
W-11
W111
W-11
WD
W1
(30)
W W-
W0
W 2
W W-1
WD
W W-
W
W0
W1
Wp
W1
W2
W-1
W0g
W11
W0 W1-1
W0
W1
W1-1
WP
W1
10
W
W
W_1
Note that rows of the Xua and Yia are aiaa, bua and Cjaat-
Now we have flattened representation Xtaa and Yis and the last step we have to take is to compute matrix product Xua V and Yna V.
B.3.3 EFFICIENT MATRIX PRODUCT
Calculation of Yoa V
In case of x images is easy to see that the matrix Y presented formula 30 consists identical blocks, we will denote this blocks as R:
R
R
R
Wlp
W1
W12
Yua =
R
R
R
where R =
W-1
Wp
W1
(31)
R
R
R
W
W-1
Wt/
Note that matrix R is just a block of Y, not its element. Also a very important fact is that can matrix R is Toeplitz, which means that it be efficiently multiplied by vector, according to Propossiino Our goal is to efficiently multiply Yıa with a matrix of shape N2 x D. Since V is basically / times stacked vectors of size N it will be enough consider matrix-vector product
15

---

Under review as a conference paper at ICLR 2022
of Yaa with vector of shape N².
The product can be expressed as:
U1
Up
03s
16
U1
+
R
14
+
R
17
R
R
R
Bai V
R
R
R
U2
(32)
R
R
R
U6
U/g
Uu
26 23
R
U1
2/4
27
U/
05
+ 1/8
(33)
Lets introduce an additional notation, we will denote as Vn tensor of size N N D, which was obtained as reshape of matrix V of size N x D. Vn will have the following structure:
UD
022
Vm
U/3
04
055
reshaape(N, N, D)
(34)
0g
Then:
U0 + 1/ 16
VT
.smmm1
U1 + 044 07
(35)
U2 + Ub
0s
Finally using notation 34 and result of product
33 we can conclude that:
R
VT sum(1)
Yaat
V
(36)
Note that the summation by dim = 1, not by dim = 1, since in general case, when D is not 1, the latter dimension refers hidden size.
R is a Topleitz matrix we worked with in the previous paragraph B.2 that is, the product of matrix R with V .smm1) can be efficiently computed using the properties of Toeplitz matrix. Finally we can conclude that for N x N image computation of product Yıa V require O(DN Nog N) computations and (NN) memory to store vector, generating matrix R.
Calculation of Xam V
Here we will apply the following trick: by rearranging the columns of matrix ha we will construct matrix X dar and accordingly construct matrix U by rearranging the rows of matrix V in such way that the equality holds X V = X U. We still will work with the D case since, as was noted previously, it can be easily generalized for higher dimensions.
w0
W1
W1
W1
W2
W2
W2
Wg
Wg
Wg
W1
W1
W1
W2
U2
W12
U11
W0
W
W
W
W/
W/p
Wg
W1
101
03
X dat V
W1
W11
W71
(37)
W
W
W_1
W/
W/
W0
M/1
W11
05
W-2
W
W-2
10
W-22
W
WP
W0
Wo
W
W
10
10
W-1
W
W0
W0
w0p
07
00
0-
W
W1
W
MP
W/
w0p
16

---

Under review as a conference paper at ICLR 2022
w0
W1
102
W0
W1
W2
Wg
W1
W2
100
Wg
W1
U2
Wu
W1
W2
Wbp
W1
W22
06
W0
W1
W0
W1
W0
W/
w
W/
W1
W
W0
W1
044
X
Bai
U
=
(38)
W0
W1
W1
W-1
W0
W1
w
W-11
W0
W--2
W-11
W-2
W--1
W0
0/2
2
10
W
W0
W0
?
10
0F-1
W0
W--2
W-11
WD
W--2
W1-1
W/
178
Now lets use already introduced matrix Vn:
W1
U12
100
U1
U2
R (V mum(mm)
w-11
W0
W1
1/3
+
1/4
25
(39)
2
1
WD/
1/6
17
28
100
U1
1/2
V3 Un
+
U4
R
05
(40)
U7
088
And finally:
200002
a
a'
X Mai
U
B
3
reshape(AN3)
(41)
7
R (V, su..ummm) (1))
...) reshape 2
(42)
B.3.4 CONCLUSION
As we proved in the previous section, products X V and Ynat V can be computed using just two products: R (vm-su((1) and R ( -smmm)) respectively. Moreover, matrix R utilized in the above products is a Toeplitz, and this regard this products can be computed efficiently ac- cording to Proposition I Summarizing it all we get that FastRBP 2D will require be O(DN log N) computations and O(N) memory.
17


Reviews:
[{"review_id": "wGSnw-RYjsr", "reviewer": "Reviewer_VGvT", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The main contributions of the papers are: 1) a new kernel for Linear Transformer using the exponential function as the activation and 2) a fast way to apply relative positional bias to attention, in both 1-d and 2-d sequence cases.\n\nThe paper claims that the shift-invariant property of the exponential function can improve the performance of linear Transformers, while the experimental results do not support this claim. From Table 1, most of the best models are with DPFP or ReLU activations. Besides, the paper doesn't present more theoretical justification for their choice of the kernel function.\n\nBesides, the paper missed an important citation [1]. [1] described the exact same method as the fast relative positional bias proposed in this paper, i.e., using FFT to accelerate multiplying a Toeplitz positional bias matrix in the 1D sequence setting. But this paper further generalizes the fast relative positional bias to the 2D sequence case to deal with image-like data, which can be regarded as a new contribution.\n\nFinally, the paper conduct experimental results on the long-range-arena benchmark, where most tasks are of very small scales. I would suggest the authors further conduct one or two large-scale experiments (e.g., GLUE, machine translation, language modeling, ImageNet classification) to verify the effectiveness of the proposed model.\n\n[1]: Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding. NeurIPS 2021", "summary_of_the_paper": "The paper proposes two modifications of linear Transformer: 1) a new kernel for Linear Transformer using the exponential function as the activation and 2) a fast way to apply relative positional bias to attention, in both 1-d and 2-d sequence cases. The experiments are only conducted on the long-range-arena benchmark, and the performance improvement does not seem to be significant.\n", "summary_of_the_review": "Given the weak theoretical and experimental supports of the proposed method and duplication of previous work, I would recommend the rejection of the paper.", "strength_and_weaknesses": "", "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": "alA6nwWZeZv", "reviewer": "Reviewer_7TLj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "Strengths: \n\n1. The proposed FastRPB gained a higher training speed and required less memory.\n\nWeaknesses:\n\n1. This is an incremental study for two existing issues of the Transformer framework on the long sequence tasks.\n\n2. The proposed approach does not achieve good results on all tasks in Tables 1 and 3.\n\nComments:\n\n1. The whole paper indeed explored two existing issues of the Transformer framework: inefficient scaling and weak performance on long sequence tasks. However, this title only focused on the first issue: inefficient scaling on long sequence tasks. What is the relationship between inefficient scaling and weak performance on long sequence tasks? \n\n2. Experimental results demonstrated that the proposed two methods cooperated with each other to improve the performance of Linear Transformer models on part of long sequence tasks. What kind of information is captured by the proposed two methods to improve the performance of Linear Transformer models on part of long sequence tasks? Particularly, both of them cooperated with each other.", "summary_of_the_paper": "This paper focused on two existing issues of the Transformer framework: inefficient scaling and weak performance on long sequence tasks. Take the Linear Transformer model as an example, the authors proposed the Shift-Invariant Kernel Function (SIKF) for the weak performance issue and the Fast Relative Positional Bias (FastRPB) for the weak performance issue, respectively. The proposed methods were evaluated on several long sequence tasks.", "summary_of_the_review": "This is an incremental study for two existing issues of the Transformer framework on the long sequence tasks.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JGJYE-fME95", "reviewer": "Reviewer_8WRr", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n1. The proposed method can solve the limitations of Linear Transformer by improving the kernel function and relative position bias.\n2. The proposed method show improvement over linear Transformer on several benchmark dataset.\n\nWeakness:\n1. The proposed method is still not comparable to SOTA models on this benchmark, such as BigBird which is also a simple and effective method.\n2. The modification over Linear Transformer is limited, especially the kernel part. Thus it's not surprising that the speed and memory usage is close to Linear Transformer.\n3. FastRPB is quite a general method. It would be better to test it with different Transformer structures.\n4. FastRPB is more novel, but it cannot lead to better performance than other baselines in most cases.\n5. Related work is too long.\n6. It would be better if the proposed method can further improve the vision Transformer on imagenet.", "summary_of_the_paper": "The proposed method is mainly based on Linear Transformer. The authors propose Shift-Invariant Kernel Function (SIKF) by replacing the kernel function in Linear Transformer with exp (x), which satisfies the property of shift-invariance. Besides, the authors also proposed FastRPB which adds Relative Positional Bias to self-attention weights. The experiments show that both methods are important to improve Linear Transformer. Moreover, the proposed method is fast and memory efficient.", "summary_of_the_review": "Overall, the improvement over kernel function and position bias is simple, but it hasn't led to significant improvement.  The performance is still far behind SOTA performance. Either SIKF or FastRPB is actually not leading to significant improvement over baselines on most of the tasks. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5cm9emo0AiC", "reviewer": "Reviewer_L9JY", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n1. The proposed SIKF kernel is fast in practice, easy in implementation and achieves good performance\n2. The proposed Relative Position Bias method provides a novel method of incorporating relative positional bias for Linear Transformers. The presented experimental results show that the proposed method outperforms the baselines for AAN and TC.\n\nWeaknesses :\n\n1. Regarding Shift Invariance 1: The authors claim that the shift invariant property of the softmax function is important for Transformers performance. However, why this might be important is not very well motivated: what causes this property to help with the performance? \n\n2. Regarding Shift Invariance 2: The original \\hat{SM_{m}}^{+} estimator presented in the Performer paper is also shift invariant. From the current version of the paper, it is not very clear why having SIKF would be more advantageous, since both offer shift invariance.\n\n3. Regarding improved performance of SIKF: The claim that the SIKF kernel offers comparable performance to existing methods is slightly strong. From Table 1, considering the performance without any positional embeddings to remove confounders, the Linear DPFP kernel outperforms SIKF on all 4 tasks (noteworthy being ListOps with an 8 point delta). Additionally, from Table 3, the peak memory usage as well as training time for Linear DPFP and SIKF is very similar for the no positional encoding setting. Thus the benefits of SIKF are somewhat unclear.\n\n4. Regarding stability of SIKF: Computing dot product of exponentiated quantities might result in overflow issues, especially when training with reduced precision. It would be good to have an experiment to show if that is indeed the case for the SIKF kernel or not.\n\n5. Regarding FastRPB: The proposal for using scalars for distances between two points is quite commonly used (eg [1]). However, a key difference between the previous approaches and the one presented in this paper is that of binning the large distances (done logarithmically in [1]). Having that variant in the experiments would be quite useful (especially for tasks where the sequence lengths vary and hence the updates to the larger difference weights is a lot more sparse).\n\n6. CIFAR Results: The reason given for the poor result on CIFAR is that only a single layer network was utilised. However, it is not very clear why that would result in a poor performance for FastRPB. What property of small networks affects the generalisability of FastRPB, and why does that not factor in for the other positional encoding methods.\n\n7. Results presented on MNIST: Given that MNIST is a fairly easy dataset (eg: 2 layer MLPs achieve strong accuracy on the dataset), training a 8 layer Transformer for the task might not be necessary. In my opinion, if the purpose of the experiment is to show generalisation on a larger Vision dataset, where training a larger model is necessary, then considering CIFAR 100 / mini Imagenet might be better to draw conclusions.\n\n8. Besides training time, reporting inference time (eg: on dev set for all the models) might also help compare model speed: a model may be slower to train, but might have faster inference time. This would help distinguish between that.\n\n\nPresentation improvement suggestions:\n1. For Equation (2) and (3), having the summation outside the fraction would help improve clarity\n2. Section 3.2, last para: we can pad the \"shorter\" one to make the input and output lengths match.\n\nReferences\n\n[1] Raffel, Colin, et al. \"Exploring the limits of transfer learning with a unified text-to-text transformer.\" arXiv preprint arXiv:1910.10683 (2019).\n", "summary_of_the_paper": "The paper presents two contributions\n1. It expands on Linear Transformers by introducing a feature map \\phi = exp(x) function whose dot product approximates the softmax kernel (dubbed Shift Invariant Kernel Function SIKF); whose motivation comes from the shift invariant property of the softmax function. They show that it performs comparably to other proposed approximations in literature while improving training efficiency and reducing the memory footprint\n2. It presents a way to use relative position bias with Linear Transformers. Dubbed Fast Relative Position Bias (FastRPB), the method proposes to learn a scalar for pairwise difference of positions, and draw a connection between the distance matrix and Circulant Matrices. They use this to efficiently compute the relative position bias in O(ND log N ) operations with O(N) memory. They show that FastRBP outperforms other relative positional bias methods while not substantially increasing compute.", "summary_of_the_review": "The paper presents a fast novel kernel (SIKF) and relative positional embeddings for Linear Transformers (FastRPB). The results with SIKF are quite mixed, and the motivation not very clear. FastRPB shows good gains against other baselines on 2 of the 4 datasets presented. However for the other two, the results are quite mixed. The reasoning provided for why FastRPB is bad needs further investigation. Additionally, having results on an image dataset more difficult than MNIST would help draw better conclusions. \n", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers are in agreement to reject this paper. The main objection is that the tasks chosen are small scale and that the mixed results are not strong enough. The authors did not attempt to raise substantial issues to be discussed.
Decision: Reject