KERPLE: Kernelized Relative Positional Embedding for Length Extrapolation
Authors: Ta-Chung Chi
Ting-Han Fan
Peter Ramadge
Alexander Rudnicky
Venue: NeurIPS 2022 Accept (2022)
Keywords: Transformer Language Modeling
Length Extrapolation
Kernel Method

Abstract: Relative positional embeddings (RPE) have received considerable attention since RPEs effectively model the relative distance among tokens and enable length extrapolation. We propose KERPLE, a framework that generalizes relative position embedding for extrapolation by kernelizing positional differences. We achieve this goal using conditionally positive definite (CPD) kernels, a class of functions known for generalizing distance metrics. To maintain the inner product interpretation of self-attention, we show that a CPD kernel can be transformed into a PD kernel by adding a constant offset. This offset is implicitly absorbed in the Softmax normalization during self-attention. The diversity of CPD kernels allows us to derive various RPEs that enable length extrapolation in a principled way. Experiments demonstrate that the logarithmic variant achieves excellent extrapolation performance on three large language modeling datasets. Our implementation and pretrained checkpoints are released at~\url{https://github.com/chijames/KERPLE.git}.

KERPLE: Kernelized Relative Positional Embedding for Length Extrapolation
Ta-Chung Chi"
Ting-Han Fan" Princeton University singhanf@princetonn edu
Carnegie Mellon University tachungc@andrew. cmu. edu
Peter J. Ramadge
Alexander I. Rudnicky
Princeton University
Carnegie Mellon University airêcs. cmu. edu
ramadge@princeton edu
Abstract
Relative positional embeddings (RPE) have received considerable attention since RPEs effectively model the relative distance among tokens and enable length ex- trapolation. We propose KERPLE, framework that generalizes relative position embedding for extrapolation by kernelizing positional differences. We achieve this goal using conditionally positive definite (CPD) kernels, a class of functions known for generalizing distance metrics. To maintain the inner product interpretation of self-attention, we show that a CPD kernel can be transformed into PD kernel by adding a constant offset. This offset is implicitly absorbed in the Softmax normaliza- tion during self-attention. The diversity of CPD kernels allows us to derive various RPEs that enable length extrapolation in principled way. Experiments demon- strate that the logarithmic variant achieves excellent extrapolation performance three large language modeling datasets. Our implementation and pretrained checkpoints are released at ftthttt://// http///ggttu..../// com/ chi james/ Hames/KERRE /ERPLE. ..Et
1 Introduction
transformer-based models have excelled in various natural language processing tasks such as chat- bot [Roller al. 202T]. code completion [Chen al.) [021a]. and paper abstract summariza- tion [Zhang et al. 2020 These sequence modeling tasks often require the model to operate well on significantly longer sequences than the fixed maximum length used at training time. Training (or retraining) the model using substantially larger value of L is often infeasible since the trans- former training cost O Hence, one desires a transformer that continues to perform well on longer sequences than those used during training: i.e., perform length extrapolation at inference time. Most transformer designs do not have this property [Press al. 2022]. While recent work on absolute positional embeddings demonstrated the extrapolation ability [Kyyono et al. 2021 Likhomanenko al. 2021], it is believed that relative positional embeddings are more robust to input length change Likhomanenko et al. 2021], for example, ALiBi [Press et al. 2022 and T5 (Raffel et al. 2020] Hence, we are motivated to study the inner workings relative positional embeddings.
Relative positional embeddings (RPE) encode the idea of shift-invariance: for any shift (m + pn+ m n. is often added directly the self-atee afffaattenton matrix before Softmax normalization [Chen et al. 2021b). Inspired by shift- inffttinvariance and the ability of kernel to define similarity function, there have been studies on shift-invarine kernels for RPE [Wennberg and Henter 2021]
with a focus on Gaussian kernel. However, in our preliminary experiments, the Gaussian kernel
Equal contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The 3-Para-Log Variant of Our KERPLE Framework. b, and p are learnable parameters in each attention head shared across layers. Since of heads is H, there are 3 H learnable parameters. The learnable parameters are trained with length-3 sequences. At the inference time, the last row (in dashed squares) becomes active, and the model extrapolates to length-4 sequences. Note focus causal language modeling following ALiBi, the matrices are triangular.
Figure 1:
OP
42kk
1. OP
-b logg 1 +
4zh,
aaka
2
1.
a- OP
quka
aaks
qake
3P
2
a- a-
demonstrates limited length extrapolation ability (see Appendix A.. Hence, distinct class of shift-invariin kernels is needed to achieve adequate length extrapolation.
To this end, note of well-established conditionally positive definite (CPD) kernels suitable for modeling distance metrics [Schölkopf] (000). However, CPD kernels do not conform to an inner product. We can remedy this issue by transforming CPD kernel into PD kernel by adding sufficiently large constant. This constant offset is subsequently absorbed implicitly in the Softmax normalization (see the discussion below Eq. (2). For example, ALiBi implicitly admits a PD kernel of the form mm n| (see the end of section 4), which is reduced to CPD kernel -Im n/. The CPD kernel and Softmax normalization combination opens the door sea of possible CPD kernels. We investigate structures from this class that exhibit strong length extrapolation ability, like ALiBi.
Our main result is framework for KErnelize Relative Positional Embedding for Length Extrapolation (KERPLE). The framework elucidates key principles that encourage the length extrapolation property. We show that ALiBi is particular instance within framework. Our subsequent experiments suggest that the proposed method yields better length extrapolation on large datasets such OpenWeeTex12, GitHub, and ArXiv.
2 Background and Related Work
2.1 Preliminary
Let { [wm 1i be the input tokens to transformer model, where L is the total number of tokens. Each Wm is scalar and is used to index the embedding vector E IRd as the input to the transformer. A transformer converts each e. into query, key, and value vectors in Rdd: qm Wymms k.n W.em- Un W.em where Wg. Wk. W. E Rd are learnable matrices. Then, the self-attention module computes the scaled attention scores and generates the output vector On at position m as:
expla Vd)
O.
On
am, Vn-
Di=1 ex /Vd)
Since the operation is position-agnostic it is believed that positional information helps model token interactions (Vaswani et al. 2017]. which we survey in the next subsection.
2.2 Positional Embedding
Absolute. Absolute positional embeddings assign positional vector Pm to each position and
adds P.. to the embedding vector e.. The very first version of which the predefined sinusoidal
function (Vaswani et al. 2017). Followed by the success of BERT (Devlin et al., 2019). learnable
absolute positional embeddings have been applied the task of masked language modeling (Devlin
et al. 2019 Liu et al. 2019 Clark et al.) 2020 Lan et al.] 2020], Autoregressive-decoodii
[Radford
ct al.
2018
2019) and sequence-to-sequencc [Gehring et al.) 2017 Lewis et al., 2019) settings.
Recent work studied ways to extrapolate sinusoidal positional embeddings to longer sequences
by randomly shifting absolute positions during training [Kiyono et al., 202T or augmenting with continuous signals [Lihhomanenoo et al. 2021

---

Relative. As opposed to the modeling of absolute position m, relative positional embeddings (RPE)
that model the positional difference m n has become popular in the literature (Shaw et al. 2018
Huang et al. 2019 Dai et al.) 2019 Yang et al.) 2019 Huang et al. 2020 He et al. 2021 Ke et al.
2021, Chen et al. 202 In particular, the T5 model that considers bucketed relative distances and
log-binning has been shown to perform well on various transformer architectures (Raffel et al. 2020]
Rotary positional embedding (Su et al. 2021] encodes the position with rotations: f(qm m)
Rm qm where Rm is rotation matrix with angles proportional to m. With the rotation's property, the query-key product exhibits a positional difference: f(am, m) f(k,, 71) = qm Rn
We note that the overview above focuses on the NLP domain. Recent work has applied positional embeddings other domains such as vision [Wu et al. 2021a] and speech [Likhomanenko et al..
2021]. A survey can be found in Dufter et al. 2022
2.3 Kernel and its Application in Transformer
The kernel trick classic approach to generalize the inner product to high dimensional spaces [Mika et al. 1998| Schölkopi| Leslie et al., [200T] Dhillon et a [2004] Takeda et al. [007]. In the context of transformers, there has been interest in applying kernels the self-attention structure to enhance the performance. Examples of such work include kernel for positional embeddings [Tsai jtt al. 2019 [W et al. 2021b WWenbberg and Henter [202] [uo et al. [021]. Another line of research leverages the kernel's s feature map |Rahimi and Recht 2007 to linearize the self-attention module
and reduce the computational cost (Katharopoulos et al. 2020 Chen et al. 2021c. Xiong et al. 2021
Peng et al. 2021 Choromanski et al. [2021 Qin et al. 2022
3 Theoretical Foundations of CPD Kernels
3.1 PD and CPD Kernels
In this work, we use shift-invariant conditionally positive definite (CPD) kernels to model the effect of relative positional differences. We propose this formulation because the notion of relative is modeled by a shift-invariant function: a bivariate function l over two positions (m, n) such that k(m,n) n) = f(m n) for some univariate f. The notion of positional difference n is generalized by the CPD kernel. We review the definitions of PD and CPD kernels below.
Definition (PD Kernel). A (real) symmetric function kernel for any integer N and any {x, E EXNN
x R is a positive definite Hi (c E RR the quadratic form is nonnegative:
X
-
EN Ej= Ge,k(xs 24) 2
Definition (CPD Kernel), A (real) symmetric function To X X IR a conditionally positive definite kernel if for any integer N and any {az E X)N the quadratic form is conditionally Ej=1 (c3g)(1, 2 ffr {cr E RR with E 1= 0.
nonnegative: Σ
Fact 1 (Berg et al.
1984] and Prop. 5 of Schölkopf (2000). Let k X X (-oe, 0] be CPD
Vz E X. Then, there exists a Hilbert space and a mapping @ X H such that [[x(x)) (('')l -kr, x').
kernel with k(xx x))
Fact D Juggests that CPD kernels generalize distance metrics to high dimensional spaces. Since are interested in positional differences, we examine modeling the distance between positions using CPD kernels.
However, Fact 1 also implies that CPD kernels do not encode inner products as required by self- attention for the computation of pairwise relations. PD kernels represent inner products. To better understand the effect of CPD kernels on self-attention, we need establish relations between CPD and PD kernels. As noted in Schölkkof 22000). if one takes any PD kernel and offsets it by a constant, the result at least a CPD kernel. In the next subsection, we show that the converse is nearly true: if & is CPD, so is e + le for large enough e E R (Lemma 1). Therefore, we may generate the CPD kernels of interest and transform them into PD kernels if needed.
3

---

3.2 Constructing PD Kernels From CPD Kernels via Constant Shifts
In this subsection, we review a few properties CPD kernels and use these to generate a variety of CPD kernels. Then, we present lemma that transforms CPD kernels into PD kernels via constant shifts. This enables the production of a family of PD kemels from CPD kernels. Finally, we present critical observation that the exact value of the constant shift is not needed, thanks to nice property Softmax normalization.
Below some important facts about CPD kernels.
Fact 2 (Scaling and Summation). If k and 22 are CPD, then so are a ki (for a > 0) and ky + k2- Fact 3 [Berg et al. 1984 and Prop. 4 of Schhlkopp (2000). If X X (-00, 0] is CPD, then < and log k).
so are k-) for
Fact 4 (Page of Schölkopf 2000)). The negative squared distance - -1 x'1 I is CPD.
The three Facts above jointly yield rich family CPD kernels as shown below.
Corollary 1. The following are CPD kernels.
(a) (x,x²') - -|| r'|l" with 0 < <ps 2 and a >> O.
(b) (z,x²) b log(1 + a||= z' 2²1 with 0 < p S and a, b 0.
We note that it is possible keep iterating between Fact 2 and 3 and generate more complicated examples, e.g., -a|1 æ'| - b log( a|| x' [2] or - b log + al| x' [|2] for 0 < < 1. However, since relative positional embeddings are of our interest, we only consider simple CPD kernels. Those with complicated forms are deferred to future work.
Now that Corollary has presented few class of CPD kernels, prove lemma (in Appendix AA.I) that constructs PD kernels from CPD kernels through shifting. Later in Eq. (2). we will see that the shifting construction is combined neatly with the Softmax normalization of self-attention.
Lemma 1 (CPD Shift Lemma. Proof in Appendix A.1
Let k X x X + IR be CPD kernel.
There exists c 2 0 such that c + k is PD kernel.
Lemma implies the CPD kernels in Corollary can be made PD if a large enough constant is added. For example, c || 2/|lP for large enough c. Although Lemma [ does not have explicit construction of thanks to the shift-invariant property of the Softmax normalization, we can leave it as under-determined constant our positional embedding design (Eq. ( in section 4 Given set of test points {x, J.2) one can do a geometric sequence search to search for a such that the N N matrix [c k(x,, x; ) it if needed, e.g., deriving the feature map of c + k.
0. Hence, we do not need the value of but we can compute
Alternative Proof of of || IlI While the CPD shift lemma is convenient, one can prove | | is PD for large enough using a kernel representation theorem in Schoenberg [1988] See Appendix A.2 for details.
Kernelized Relative Positional Embedding
Let (qm and (k;, Him be the input queries and keys. Let (r1,..., r2) be learnable parameters. We propose a kernelized relative positional embedding as follows.
exp ((g kn kr.,..., (m, n))/val
Omn. Els (osp(aqThkk 4 ky
re (m, i))/va)
where kr......r (m, n) is any shift-invariant CPD kernel with & parameters. Due to Lemma can be reformulated into its kernel form as follows.
Eq.
By geometric sequence search, we can enlarge e by 2, 4, 8, 16, and so on until we find the required large enough constant.

---

(+) exp ((qmiin + +c k n))/vvl
Om,n
El= exp((qm) ki + + be...... (m, vd)
(2)
CXP (qm kn + krumnr ( (m, n n)))/ Vd)
exp (h:omp((qqm: ml. [kn n2)/ /d)
Lemma
i==1 exp(qm k; + kr (m, /d) E exp (kcomp( ((mm: m), [k; el)/vd)
(*) is due to the shift-invariant property of the Softmax normalization:
exp(z,)
exp(x:+t)
Σ, exp(aty Σ, exp(a, +
for any E. The second equality defines bias kernel which is positive definite using Lemmal
Kri....re + kr....,re'
The last equality introduces composite kernel kcomp: Rd-1 Rd+1 - R as ke m/], [ki, n1)) q knn ky (m, n).
(4)
The proposed method can be interpreted applying a composite kernel to self- attention. The composite kernel combines the information from query qm. key k, and positions (m.n) in a way that augments the original self-attention structure by multiplicative and additive position embeddings. The augmentation allows c.omp to not only retain the original k but also include positional information from the bias kernel kri....re
Interpretation.
Practical Choice. In section 5.2 we fix t 2 and experiment on two variants of the composite
kernel, Eq. 4 where we call these the power variant and the logurithmic variant of our proposed
KERPLE framework, Eq. (2) These are from combination of Corollary and Eq. (3)
(power) k.copp ([mm. m], [k,,, ri]) = qm kn + c V1 Im - -1|"² with v1 > and 0 < r2 S
(logarithmic) kuomp ([qm: m., [k,,, m.] = 4m k;n + c- T1 loog1 + r2 m - nzl) with 11. 72 >> 0.
We note that these are not the only variants of the composite kerne.. In section [5.3] we experiment with two more complicated variants, but only find lower training speeds and marginal improvement in perplexities (e.g., logarithmic variant 3-para-log). Thus, based on study, the choices above hold advantages in both performance and speed.
Connection to Prior Work. When the bias kernel, Eq. (3). is triangle kernel: - Im n/. our model reduces to ALiBi [Press et al.) 2022]. Wennberg and Henter [2021] discuss the situation where the bias kernel is a Gaussian kernel. Tsai et al. [[019] is the case where there is no bias kernel and the attention product q kn is multiplied by an exponentiated inner product kernel, exp(x* yy) Since ALiBi is the state-of-the-ee and has great input length extrapolation, will focus comparison with ALiBi in our experiments.
The logarithmic variant has an implicit connection to T5 positional bias Raffel et al. 2020]. According to the official GitHub repository https:: //gi thub. wtt.:/oolee-eeeeeeeeeeeeeeeeeeee research/ text to- text transtrrannfee er transf ormer and the HuggingFace Transformer [Wolf et al.) 2020]. T5 bias implemented with log-binning strategy. For each head of the transformer, they maintain bucket of 32 learnable parameters and assign the relative positional bias bm n to these parameters as
bucket[m- m] bucket[min(311 16 log((m=n)/10) (og(128/16
0 m
16
Oy
16]] if m 2 16,
where I.J is the floor function. Note that the log factor is approximately 7.7 log -- Therefore, T5 using a logarithmic bucket assignment, which turns out to extrapolate to different input lengths. Compared with T5, our logarithmic variant uses less parameters (2x12 vs. 32x12) but cannot learn non-monotonie relations (the log function is monotonic). We will conduct more comparisons with T5 bias in our experiments.
Experiments
5.1 Dataset and Implementation Description
Dataset. We conduct experiments on OpenWebTex12, GitHub, and ArXiv datasets gathered in
Gao et al. [2020]. OpenWebText2 includes recent content from Reddit submissions until 2020,
5

---

content from multiple languages, document metadata, multiple dataset versions, and open- replication code. GitHub includes open-source repositories written in primary coding languages such as Java, C/C++, Python, and Go. ArXiv includes papers written in LaTex in Math, Computer Science, Physics, and some related fields. These tasks are motivated by the downstream applications such as online chatting [Roller et 202T), code completion [Chen et al. [021a], and academic paper summarization (Zhang et al. 2020].
Table 1: Dataset Overview. Raw Size is the size before any up- or down-
Open Web'lex22
GitHub
ArXiv
Raw Size Type
66.77 GB
95.16 GB
56.21 GB
Internet
Coding
Academic
Implementation. We adapt our model from GPT-NeoX [Black al., 2021]. a transformer imple- mentation by the EleutherAl team. The codebase is based on NVIDIA Megatron Language Model Shoeybi et al., 2019] and further accelerated using Microsoft DeepSpeed library (Rasley et al. 2020]
Our model is trained on a machine with one NVIDIA A100 GPU with 40 GB of memory. We adopt almost all configurations of small GPT-NcoX except that we change the train-miero-batch-siie to 32, seq-length to 512, and max max-posinee maxxpposition-e position--mbedddiinee embeddings to 512. Table summarizes the important configurations fixed throughout our experiments. In particular, the floating- -pontt encoding set as
Table 2: 162M Model Configurations.
# Layers
Hidden Size
# Attention Heads
Train Seq. Len.
# #Trainable Params.
12
64
512
162M
Optimizer
Batch Size 32
Train Steps 50,000
Precision b6loat16
# #Trainable Params. for RPEs at most 36
Adam (Ir 6e-4)
6 (Brain Floating Point, developed by Google Brain) so that the training can be accelerated by half- malf-precision computation with reliable stability Kalamkar et al. 2019). Hidden size 64 means that 64 in Eq. I
5.2 Experimental Results (Also c.f. Appendix to A.7
We conduct experiments to cover aspects such as input length extrapolation, application on different domains, and comparison with the prior work. These are elaborated on below. (i) Motivated by the input length extrapolation demonstrated in [Press et al. 2022). we train our model with length 512 and test on lengths ranging from 512 to 16384. We hope that the emphasis extrapolation enables the application of transformers to longer sequences. (ii) To evaluate the applicability of the model Open
GitHub, and ArXiv datasets. (iii) To validate the effectiveness of our method, we compare KERPLE with Sinusoidal (Vaswani et al. [Su et al. 2021]. T5 [Raffel et al. 2020), and ALiBi [Press et al.) 2022
in different domains, we conduct experiments
2017). Rotary
Table reports the perplexities at different extrapolation lengths. We perform non-overlapping evaluation: Suppose text is segmented in different manner for 512 and 1024 tokens, we have sentences and N/2 correspondingly to evaluate. We also perform a paired two-sided t-test to validate the statistical significance (significance level=0.05). We compare each candidate RPE with our proposed logarithmic variant and mark the candidate with if the log variant is statistically 4 reports the training speeds. These tables yield three conclusions. First, within the KERPLE framework, the logarithmic variant is better than the power variant. Secondly, the logarithmic variant is 9.7% faster than T5. In terms of extrapolation, the logarithmic variant generally does better than T5 but could be slightly worse than T5 at shorter lengths. Third, the logarithmic variant is slightly slower than some prior work (ALiBi, Rotary, and Sinusoidal) but consistently outperform these methods at all extrapolation lengths. More details are given below.
significantly better. Table

---

Logarithmic Variant vs. Power Variant. In our proposed KERPLE framework, the logarithmic variant is better than the power variant. Precisely, the logarithmic variant is 4.4% faster and has lower perplexities across all extrapolation lengths and all tasks.
Logarithmic Variant vs. T5. In terms of speed, the logarithmic variant is 9.7% faster than T5. In terms of extrapolation perplexity, the logarithmic variant is close to or slightly worse than TS when the extrapolation length is shorter than 2048, and consistently excels T5 at longer extrapolation lengths. The tendency of extrapolation holds for all datasets evaluated in this work.
Logarithmic Variant vs. ALiBi, Rotary, and Sinusoidal. The logarithmic variant is 1.6% slower, 7.5% faster, and 3.0% slower than ALiBBi, Rotary, and Sinusoidal. The speed comparison makes sense because we require only limited amount of learnable parameters for RPEs (at most -f), Also, the logarithmic variant consistently outperforms prior work at all extrapolation lengths and tasks.
Table 3: Perplexity Comparison on Open Tex GitHub, and ArXiv. All models are trained for 50k steps with training length 512 and five random seeds. x² means our log variant is statistically significantly better than æ. The test used is paired two-sided t-test with 0.05.
OpenWehText2
KERPLE
Extrp.
ALiBi
T5
Rotary
Sinusoidal
(log)
(power)
512
23.9 0.6
23.9 + 0.6
23.9 0.6
23.7 + 0.6
24.2 + 0.6
33 + 1
1024
22.0
22.1::00
0.5
21.9 0.6
32.8 + 1.71
750 + 346
2048
2.3
0.2
0.21
2.27
62.4 + 6.1
5507 = 2607
4096
21.2
2.5t
2.65 0.4
111 13.8
14039 = 2325t
8192
21.3 0.4
21.6 0.4
2
25.5
185 + 18.9
22621 1927t
16384
21.4 0.6
21.6
31.4
269 + 33.0
30046 + 4824
GitHub
KERPLE
Extrp.
ALiBi
T5
Rotary
Sinusoidal
(log)
(power)
512
3,40 0.20
3.42 0.20
3.42 2 0.21
3.38 + 0.21
3.44 + 0.201
4 0.2
1024
0.14
3.02 3.15 0.16
#.251
105 + 39f
2048
2.86
3.10 2.08
2.09
5 0.64
1380 + 404
4096
2.74
3.04 0.06
2.78
11.1 1.55t
5217 = 1118
8192
2.71 0.05
2.76
3.04 + 0.03
2.95
+ 0.13t
20.2 +: 2.751
10081 + 35831
16384
2.75
+ 0.16
2.76
0.13
3.02 = 0.13
3.35 + 0.27
31.3 + 5.20
16443 + 8503
ArXiv
KERPLE
Extrp.
ALiBi
T5
Rotary
Sinusoidal
(log)
(power)
512
6.07 + 0.26
6.10:...
6.12 + 0.26
6.03 + 0.26
6.07 + 0.27
43 + 44
1024
5.61
+ 0.10
5.65
+ 0.10
5.82 + 0.09t
5.58
0.09
7.49 + 0.34
221 + 136t
2048
5.22
0.12
5.26
5.71
+.144
5.21
14.2
1.81
730 + 3431
4096
5.25
5.32 0.08
30.1 + 4.32
1998 + 4971
8192
5.01 0.10
0.14 0.15
0.39
54.3 + 6.221
4228 = 2645
16384
5.07
+ 0.16
0.19
5.78 0.15t
6,25 + 0.61f
85.4 + 7.40t
6674 + 5696
Table 4: Training Time Comparison on GitHub
KERPLE
ALiBi
T5
Rotary
Sinusoidal
(log)
(power)
sec/step 0.307
0.321
0.302
0.340
0.332
0.298
5.3 Experiments Complicated Kernels
In addition to the practical variants (power logarithmic) in section 4 we consider two complicated versions of the composite kernel, Eq. 4 follows.
7

---

(bias+wht) bias + weight:
kcomp (l9m m]. [k, n.) qm k, exp((rrlmm-n)) + ri ri/m- n|²²
with r3 and 0 < r2, 1 2.
(3-para-log) 3- --prameter- k (l4m, ml. kk, nl) = 4m kn + - log + r2 - n2 with "2 and r3 I 2. Recall the tensor product property k((1, v), v/)) ki (z,=²)kk (v, v/) is kernel on X' x 3/ Therefore, (bias+wht) is the setting where we train weight exp(-ra) /ramm-----a (m- mm--/"3 -n=")) and a bias kernel c- 71 [m -n|"². q. is multiplied by the weight kernel and then added with the bias kernel. (3-para-log) the setting where we consider m -2 in the log. When 13 = 1, it is reduced to the logarithmic variant proposed in section 4
kernel: if ki is kernel on and k2 a kernel on V then
We plug in these composite kernel ccomp into KERPLE framework, Eq. 2 and test the perfor- mance of these RPE. Compared with section 5.2 Table 5 suggests that these variants do not have clear advantage in extrapolation performance, e.g.. 3-para-log is slightly better in perplexity than the (two-parameter) logarithmic variant. Thus, enlarging the complexity of kernels does not necessarily give better performance in the context of RPE.
Table 5: Perplexity Comparison for KERPLE with Complicated Kernels Open WebText2, GitHub, and ArXiy. All models are trained for 50k steps with training length 512 and five seeds random. OOM means out of memory.
OpenWehText
GitHub
ArXiv
Extrp.
(bias+wht)
(3-para-log)
(bias+wht)
(3-para-log)
(bias+wht)
(3-para-log)
512
24.1
0.6
23.8 + 0.6
3.44 + 0.21
+.20
6.21
6.06 + 0.27
1024
22.2 + 0.6
0.7
3.08 + 0.15
0.14
5.66
5.61 + 0.10
2048
21.9 0.4
2.2
2.90 + 0.12
2.85
5.21 0.12
4096
21.5
2.4
2.79 + 0.06
2.73
5.31 0.08
5.18 0.09
8192
21.4 1.4:... 0.5
21.3 1:3:00 0.4
2.76 + 0.03
2.68 + 0.04
5.16 0.18
5.00 + 0.11
16384
OOM
0OM
00M
0OM
0OM
0OM
5.4 Plots of Kernel Functions
We plot kernel functions including the power, log variants, and ALiBi for different heads to see their contributions to softmax. We use the GitHub dataset for demonstration. Please see Figure 3 and Both ALiBi and its generalized power variant quickly reach a very negative value. In contrast, the log variant successfully discovers several flat kernels, effectively extending the window attention. This corroborates our previous observation that KERPLE- can utilize more distant token information.
Figure 2: Kernel Functions of Learned by the Log Variant.
-4
Kernel Value
-6
-10
-12
15
2530
5000
7560
13000
12500
15000
Positional Differences Between Tokens [m-n]
8

---

Figure 3: Kernel Functions Learned by the Power Variant. Note the y-axis should be multiplied by 1e8, which is a very negative value.
168
Kernel Value
-2
-4
Positional Differences Between Takens m-n]
Figure 4: Kernel Functions Learned by ALiBi.
2000
Kermel Value
4000
-8000
-10000
-12000
2500
7500
10000
32500
15000
Pusilional
[m--]]
5.5 Position-wise Perplexity Evaluation
We plot the position-wis perplexity with evaluation length=4096 in Figure 5 Please see Ap- pendix [A.6 similar length=16384 result. The evaluation done by measuring the loss at each position in each sequence and averaging over the sequences.
We note that PPL@512 of KERPLE-log the lowest among all model variants. We can derive several critical observations for evaluation length=4096 in Figure First, KERPLE-log lies below KERPLE- usage more distant information than window attention: If our
log-windowed 512, indicating model does not use more information other than a 511dowiino the y-values after position=512 should overlap with the line windowed 512. This clearly not the case. In addition, the PPL of KERPLE-KE continues to decrease till the end of 4096 positions (Not plateauing). Second, T5 @ 512 most of the time and fluctuates around KERPLE-log- windowed @ 512 after length=3000. It is still worse than KERPIEE-log. Third, ALiBi lies above ShRPPLE-log-windowerr 512 for almost all the positions, indicating that window attention might be better choice than ALiBi.
lies below CERrPLE-log-windooe
Although window attention a strong baseline, our KERPLE-log almost like free lunch compared to window attention: With only 24 additional learnable parameters (2 para. for each head), the almost same training speed, and the same train length=512 as window attention, is able achieve lower PPLs across different positions.
6 Conclusion and Future Work
A general framework, KERPLE, is proposed to kernelize relative positional embeddings for length extrapolation. At the core of this framework the application CPD kernels and the derivation of practical variants. We show that these CPD kemnels be implicitly converted to PD kernels, which

---

Figure 5: Position-wise Perplexity GitHub at Evaluation Length=4096 Compared to Window Attention@512.
Position-wise Perplexity at Evaluation Length=4096
20.0
Rotary
17.5
ALiBi
T5
15.0
Average Perplexity
KERPLE-IOg
KERPLE-og-wwindoee@0515
12.5
10.0
7.5
5.0
2.5
0.0
1000
2000
3000
4000
Position
keep the inner product interpretation of self-attention. We also demonstrate that the logarithmic variant achieves exceptional extrapolation performance on three large language modeling datasets. We helieve our work paves the way for some interesting future directions that resolve our limitations. For instance, we can consider general kernel families and model non-monotonic effects due to positional differences. generalization to inputs higher than one-dimensional. Last but not least, there is always room for improving memory efficiency by adjusting the model architecture and training procedure.
addition, the use of learnable parameters in KERPLE might enable better
7 Broader Impact
Our work develops a better understanding of relative positional embedding for transformers based on expressive kernel classes that adapt well various datasets. The results apply domains where the positional information helpful in the modeling, e.g.. natural language, programming language, and DNNA/protein sequences for biology/medicine. The studies of transformers may have positive economic effects by enabling new tasks which cannot be done by humans or enhancing accuracy and efficiency. But inappropriate use can have negative societal impacts. These include job loss due to automation, the ethical challenges from improper text generation, and the privacy issues in the data collection process. These implications apply any research on natural language processing and not associated with any specific work.
8 Acknowledgement
We thank the anonymous reviewers for their insightful feedback and suggestions. We thank Princeton Research Computing for the technical support on the Della and the Adroit clusters. The third author acknowledges support from NSF MRI Award: 1919452.
10

---

References
Stephen Roller, Emily Dinan, Naman Goyal, Da Ju, Mary Williamson, Yinhan Liu, Jing Xu, Myle Out, Eric Michael Smith, Y-Lan Boureau, and Jason Weston. Recipes for building an open-domain chatbot. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguisties: Main Volume, pages 300-325, Online, April 2021. Association for Computational Linguisties.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph. Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021a
Jingqing Zhang, Yao Zhao, Mohammad Salch, and Peter Liu. Pegasus: Pre-training with extracted gap-sentences for abstractive summarization. In International Conference on Machine Learning. pages 1:328-11339 PMLR, 2020.
Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations, 2022.
Shun Kiyono, Sosuke Kobayashi. Jun Suzuki, and Kentaro Inui. SHAPE: Shifted absolute position embedding for transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 3309-3321 Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.
Tatiana Likhomanenko, Qiantong Xu, Gabriel Synnaeve, Ronan Collobert, and Alex Rogozhnikov. Cape: Encoding relative positions with continuous augmented positional embeddings. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 16079-16092. Curran Associates, Inc., 2021.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140): 2020.
Pu-Chin Chen, Henry Tsai, Srinadh Bhojanapalli, Hyung Won Chung, Wen Chang, and Chun- Sung Ferng. A simple and effective positional encoding for transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 2974-2988. 2021b.
Ulme Wennberg and Gustav Eje Henter. The case for translation- invariiant self-attention in transformer- based language models. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers), pages 130-140, Online, August 2021. Association for Computational Linguisties.
Bernhard Schölkopf. The kernel trick for distances. In T. Leen, T. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems, volume 13. MIT Press, 2000.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pages 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint
2019.

---

Kevin Clark, Minh-Thang Luong, Quoe V. Le, and Christopher D. Manning. Electra: Pre-training text encoders as discriminators rather than generators. International Conference on Learning Representations, 2020.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for self-supervised learning of language representations. In International Conference on Learning Representations, 2020.
Alec Radford, Karthik Narasimhan, Tim Salimans, and llya Sutskever. Improving language under- standing by generative pre-training. OpenAl blog, 2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N. Dauphin. Convolutional sequence to sequence learning. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, 17, page 1243-1252. JMLR. 2017.
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. Bart: Denoising eqquence-t--squenne pre-training for natural language generation, translation, and comprehension. arXiv preprint arXiv:1910.13461. 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 Computational Linguistics: Human Language Technologies, Volume (Short Papers), pages 468, New Orleans, Louisiana, June 2018. Association for Computational Linguistics.
Cheng-Zhi Anna Huang, Ashish Vaswani, Jakob Uszkoreit, lan Simon, Curtis Hawthorne, Noam Shazeer, Andrew M. Dai, Matthew D. Hoffman, Monica Dinculescu, and Douglas Eck. Music transformer. In International Conference on Learning Representations, 2019.
Zihang Dai, Zhilin Yang. Yiming Yang, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov: Transformer-XL. Attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978-2988, Florence, Italy, July 2019. Association for Computational Linguisties.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc Le. Xinet: Generalized autoregressive pretraining for language understanding. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Zhiheng Huang, Davis Liang, Peng Xu, and Bing Xiang. Improve transformer models with better rel- ative position embeddings. In Findings of the Association for Computationall Linguistics: EMNLP 2020. pages 3327-3335, Online, November 2020. Association for Computational Linguistics.
Pengeheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. (DEBERTA): (DECODING)- (enhanced) (bert) (wihh) (disentangled) (attention). In International Conference on Learning Representations, 2021.
Guolin Ke, Di He, and Yin Liu. Rethinking positional encoding in language pre-training. In International Conference on Learning Representations, 2021.
Jianlin Su, Yu Lu. Shengfeng Pan, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. arXiv preprint 1rXiv:2104.0986. 2021.
Kan Wu, Houwen Peng, Minghao Chen, Jianlong Fu, and Hongyang Chao. Rethinking and improving relative position encoding for vision transformer. In 202/ IEEE/CVE International Conference on Computer Vision (ICC),, pages 10013-10021, 2021a.
Philipp Dufter, Martin Schmitt, and Hinrich Schütze. Position Information in Transformers: An Overview. Computational Linguisties, pages 1-31, 07 2022.
Sebastian Mika, Bernhard Schölkopf, Alex Smola, Klaus- Müller, Matthias Scholz, and Gunnar Rätsch. Kernel pea and de-noising feature spaces. Advances in neural information processing systems, 11, 1998.
12

---

Christina Leslie, Eleazar Eskin, and William Stafford Noble. The spectrum kernel: A string kernel for svm protein classification. In Biocomputing 2002, pages 564-575. World Scientific, 2001.
Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and nor- malized cuts. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 551-556, 2004.
Hiroyuki Takeda, Sina Farsiu, and Peyman Milanfar. Kernel regression for image processing and reconstruction. IEEE Transactions on image processing, 16(2):349-366, 2007.
Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhut- dinov. Transformer dissection: An unified understanding for transformer's s attention via the lens of kernel. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP- IJCNLP), pages 1334-4353, Hong Kong, China, November 2019. Association for Computational Linguistics.
Chuhan Wu, Fangzhao Wu, and Yongfeng Huang. DA-transtormer: Distance-aware transformer. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2059-2068, Online, June 2021b.
Association for Computational Linguistics.
Shengjie Luo, Shanda Li, Tianle Cai, Di He, Dinglan Peng, Shuxin Zheng, Guolin Ke, Liwei Wang, and Tie- Liu. Stable, fast and accurate: Kernelized attention with relative positional encoding. Advances in Neural Information Processing Systems, 34, 2021.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20, Curran Associates, Inc., 2007.
Angelos Katharopoulos, Apoory Vyas, Nikolaos Pappas, and François Fleuret. Transformers are RNNs: Fast autoregressive transformers with linear attention. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5156-5165. PMLR, 13-18 Jul 2020.
Yifan Chen, Qi Zeng, Heng Ji, and Yun Yang. Skyformer: Remodel self-attention with gaussian kernel and nystr)." om method. Advances in Neural Information Processing Systems, 34, 2021c
Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmformer: A nystöm-based algorithm for approximating self-attention. In Proceedings of the... AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence, volume 35, page 14138. NIH Public Access, 2021.
Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah Smith, and Lingpeng Kong. Random feature attention. In International Conference on Learning Representations, 2021.
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song. Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Ben- jamin Belanger, Lucy J Colwell, and Adrian Weller. Rethinking attention with performers. In International Conference Learning Representations, 2021.
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.
Christian Berg, Jens Peter Reus Christensen, and Paul Ressel. Harmonic analysis semigroups:
theory of positive definite and related functions, volume 100. Springer, 1984.
Isaac Schoenberg. Metric spaces and positive definite functions. Transactions of the American Mathematical Society, 44(3):522-536, 1938.
13

---

Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick Von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. Transformers: State-of-the-ar natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38-45, Online, October 2020, Association for Computational Linguisties.
Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al. The pile: An 800gb dataset of diverse text for language modeling. arXiv preprint arXiv:2/01.00022 2020.
Sid Black, Stella Biderman, Alex Andonian, Quentin Anthony, Preetham Gali, Leo Gao, Eric Hallahan, Josh Levy-Kramer, Connor Leahy, Lucas Nestler, Kip Parker, Jason Phang, Michael Pieler. Shivanshu Purohit, Tri Songz, Phil Wang, and Samuel Weinbach. GPT-NeoX: Large scale autoregressive language modeling in pytorch, 2021. gpt-neox
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catan- zaro. Megatron-Im: Training multi-billion parameter language models using model parallelism. arXiv preprint 1rXIv:1909008055 2019.
Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He. Deepspeed: System optimiza- tions enable training deep learning models with over 100 billion parameters. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3505-3506, 2020.
Dhiraj Kalamkar, Dheevatsa Mudigere, Naveen Mellempudi, Dipankar Das, Kunal Banerjee, Sasikanth Avancha. Dharma Teja Vooturi, Nataraj Jammalamadaka, Jianyu Huang, Hector Yuen, al. A study of bíloat16 for deep learning training. arXiv preprint 0Xiv:1905.11322. 2019.
14


Reviews:
[{"review_id": "ouIsgl3WeH", "reviewer": "Reviewer_e9dG", "summary": "As you know transformer is permutation invariant and we add positional embedding to break this invariance (in additive / multiplicative manner, in absolute or relative manner). Recent results demonstrated problems with extrapolation to larger lengths of sequences not only for absolute positional embedding but also for relative positional embedding (which was supposed to solve this problem). Last works proposed different ways on improving positional embedding like augmentation absolute positions (SHAPE, CAPE, Universal Transformer) or having fast decreasing function defined on relative position $m-n$ (T5, ALiBi). This paper continues the study on improving the relative positional embedding to be generalizable to longer sequences: it provides mathematical connection and generalization for T5 and ALiBi approaches with conditional positive-definite kernels (CPD) and positive-definite kernels (PD). With that authors experimented with polynomial and logarithmic bias functions for $m-n$ and found that logarithmic has the best behavior mostly outperforming T5 and ALiBi (and also standard embedding: rotary and sinpos) on 3 large text datasets for language modeling task.", "questions": "Thanks authors for providing interesting analysis on what context has contribution to the attention for every head (Fig. 2), careful math formulation (including known facts, and properties) without typos (it is very simple to read and follow) and formulation as CPD/PD kernels. Happy to see some math behind and connection to it for positional embedding!\n\n**References**\n\n[mentioned in rows 21-23]: There are recent several papers which studied augmentation of absolute sinusoidal positional embedding to be able to extrapolate. I recommend to add their links in the introduction and change a bit statement that the success is not only in relative positional embedding. \"Kiyono S, Kobayashi S, Suzuki J, Inui K. Shape: Shifted absolute position embedding for transformers. EMNLP 2021\" https://aclanthology.org/2021.emnlp-main.266/, and \"Likhomanenko, T., Xu, Q., Synnaeve, G., Collobert, R. and Rogozhnikov, A., 2021. CAPE: Encoding relative positions with continuous augmented positional embeddings. Advances in Neural Information Processing Systems, 34, pp.16079-16092.\" https://proceedings.neurips.cc/paper/2021/hash/865bf46435bd84fa5d89f64cf3ba7347-Abstract.html \n\n[mentioned in Sec 2.2] Would be nice to add recent works on different positional embeddings in other domains like vision, speech, etc. At least the recent overview paper on positional embeddings for transformers \"Dufter, P., Schmitt, M. and Schütze, H., 2021. Position information in transformers: An overview. Computational Linguistics, pp.1-31.\" https://arxiv.org/abs/2102.11090.\n\n[mentioned in Sec. 2.2 line 62]. Could authors add a bit more description for rotary positional embedding as it is different from all previous in the sense of being multiplicative, not additive and having math formulation to be shift invariant?\n\n[line 72]. Do authors have an exact proposal how to use KERPLE in linearized case? Because rotary positional embedding and absolute positional embedding are applicable directly to \"linear attention\". And rotary positional embedding (as far as I know) is the first relative positional embedding which is applicable to \"linear attention\". I would suggest to mention this (other relpos are not extended yet for this case).\n\n**Typos and improving text**\n- line 53 missed space \"Autoregressive decoding[..]\" -> \"Autoregressive decoding [..]\"\n- The message on why we want PD kernel is a bit lost in the text. Maybe a bit clearly formulate this in Sec. 4 or at the end of Sec. 3.\n- line 118: \". We prove\" -> \"we prove\"\n- line 124: \"Lemma. 1\" -> \"Lemma 1\"\n- line 135-136 formula - I didn't get why authors have different functions for numerator and denominator? In the denominator it should be the same as in nominator. Same in lines 137-138 formula. I would even simplify this a bit with just proper notations and having only (*) equality and the final expression with specifying what we have right now in lines 138-140\n- line 141: \"applying a composite kernel to the softmax function\" - strange formulation, I have in mind that we do $k(softmax(x))$ not vice versa.\n- line 144: How do authors come up with multiplicative positional embedding? in this case all theory is broken as we will have $k_1(q_m, k_n) * k_2(m, n) + k_3(m, n)$ which is not PD or CPD. We can only have $k_1(q_m, k_n) + k_3(m, n)$ being PD/CPD. Some clarification here is needed why we do multiplicative posemb.\n- Appendix, line 492: it is a bit obvious but for reader with less math background it is great to add why it is enough to find $c$ only for $v$ on the unit sphere and not the whole space.\n- Appendix, line 519: $T_\\delta \\subset S_{\\delta_2}$ - I think it is wrongly to write this subset property. I would say we should just write that \"then $v'$ also belongs to $S_{\\delta_2}$ and thus ...\"\n\n\n**Experiments**\n\n- First, I would suggest to perform additional experiment on understanding how much extra context is really giving us as for now it seems that methods like T5, ALiBi and the current paper just propose to restrict attention. This reminds local / fixed-context attention, like in Big Bird window attention. I know that T5 and even recent ALiBi didn't investigate this and one can argue (which stated in the current paper) that we see improved perplexity on the dataset with longer context evaluation. This depends how evaluation is done exactly, but here I assume that the text is just segmented in different manner for say 512 and 1024 tokens and then we have just N sentences and N/2 correspondingly to evaluate. In this case perplexity is not fully comparable as tokens at positions 0, 1, .. are different ones, but magnitude of perplexity can give us understanding if something is broken (like in sinpos embedding). If you agree with these points then the test with window attention (as we do same exact evaluation) will give us understanding if we are using larger context and embedding is really helpful (as this is claimed in the paper).\n\n- Another helpful analysis I propose is the following. When we evaluate for particular length, say 1024, we measure average perplexity for current position: we take words at position $k$ and compute their average perplexity. We plot this for every $k\\in[1, ..., 1024]$ for different models. In this case we can analyze at which positions particular positional embedding is broken or not. I would suggest to have this plot for say 512, 4096 and 16384.\n\n- I would like to see in Appendix description of how evaluation on different lengths is done (please confirm my above comment how I think it is done). Otherwise it is not obvious as I can come up with several (even expensive) methods.\n\n- Why logarithmic variant of KERPLE is slower than T5 and ALiBi? I would say there probably should no be any difference as number of learnable params is very negligible compared to model size used in experiments.\n\n- How were the parameters of training optimized? On T5 or ALiBi? or just taken some reasonable to be able to train in reasonable time? On which architecture / dataset they were optimized? It is very fair to have in the end exact setting and just vary positional embedding (please confirm this too - maybe it is worth to be specific in the text on this too).\n\n- Would be nice to have also relative positional embedding \"Dai, Z., Yang, Z., Yang, Y., Carbonell, J.G., Le, Q. and Salakhutdinov, R., 2019, July. Transformer-XL: Attentive Language Models beyond a Fixed-Length Context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (pp. 2978-2988). \" as baseline as before it demonstrated some generalization ability on long sequences and recently (see SHAPE, CAPE) it was shown to have problems (but not in context of LM). I know ALiBi didn't provide great benchmarking on this and didn't check Transformer-XL variant. Yes, it is very expensive, but for comprehensive analysis would be nice to understand how it behaves in comparison.\n\n- Do authors have any idea why T5 in Table 3 behaves so good compared to results on extrapolation in ALiBi where they report that T5 do not extrapolate for >5k lengths and it was consistent in their paper?\n\n- One last thing I propose is to add in addition to Fig. 2 the plot of the kernel function itself for different heads (not doing thresholding and selecting exp(-2)) for all methods to see the difference in tail and contribution to softmax.  \n", "limitations": "Limitations are discussed in Conclusion and in Sec 4.\n\n**Update on the rating** Based on all discussions, new revision version, all extra experiments, analysis and ablations I would like to raise my score from 6 to 7.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- [clarity] Paper is very well written with only little typos and very well math background and explanations. However, some details (e.g. how evaluation exactly done, how hyperparams were optimized) are needed.\n- [originality] The work is providing general formulation of kernelized version of positional embedding where prior works like T5 and ALiBi can be considered as particular cases. I am glad to see nice connection and formulation supported with experiments.\n- [quality] current experiments look strong and reasonable, significance test is showing that proposed logarithmic kernel improves over previous results, additional ablations are given in Appendix comparing different kernel variations and even more complex ones. Analysis on the heads (Fig.2) how much context is involved in self-attention looks good to me. Math part and explanations are also correct.\n- [significance] It is nice to have general formulation and investigation of different kernels.\n\n**Weaknesses**\n- [quality] In my opinion (as in prior work this study is absent) some extra experiments and analysis are needed: analysis how every position is recognized, window attention as a baseline to understand if we are inferring anything from larger context, analysis on the tail of kernel function values, probably Transformer-XL baseline comparison (every this point see in Questions section with more context).\n- [significance] The work presents results only for language modeling task and it is open question how it is applicable to other domains, like vision transformer and speech recognition. Also current results (though significance test is showing improvements) doesn't show huge improvement from the simple ALiBi / T5 variant. That is why would be great to have some more analysis what is going on with this type of embeddings to strengthen the papers results and observations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WMxEfbXEJ6", "reviewer": "Reviewer_QqrL", "summary": "Previous work, ALiBi, presented a new position embedding method that conveys positional information by subtracting a linearly growing bias from the key-query dot product in the attention mechanism. \n\nHere the authors present two new position embedding methods that build on ALiBi and claim to improve it by changing the way in which the bias grows as the distance between the key and query increases. In ALiBi this was just a simple linear function but here two slightly more complex alternatives are presented. \n\nThere are experiments on a few dataset but none of these results are compared to results published in existing papers. For example, it would've been very helpful to see results on the commonly-used WikiText-103 benchmark.\n\nI feel like this exploration is interesting and might lead to impactful results but I don't feel like it is quite ready yet. \n\n", "questions": "Are there any advantages to the power variant?", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) New formulation of the 'increasing position bias' method from ALiBi that does better on multiple language modeling datasets, as compared to strong baselines (ALiBi, Rotary and the T5 bias).\n\nWeaknesses:\n1) The authors only present results for one model size, 162M parameters. I think using the ALiBi baseline on WikiText-103, with 247M parameters would make this paper much stronger.\n2) The authors run all the baselines themselves and don't compare to any existing numbers from the literature. This means that if the authors made some error in how they train or run their models, we wouldn't know- all numbers in the paper were produced by the authors themselves. Therefore I would again recommend having the WikiText-103 baseline and comparing to numbers from the ALiBi paper, that way we can ground your results in existing performance numbers from the literature.\n3) The authors only train their model on one sequence length, 512. I feel like having experiments on at least one more sequence length would make the paper stronger. \n4) The math in section 3 and 4 seems unnecessary.\n5) Two alternatives are presented- log and power, but it seems like the 'log' method is superior in every single dimension, so it's not clear why the power method was presented at all in the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UvyMG032lm4", "reviewer": "Reviewer_NUAF", "summary": "The paper presents several new self-attention variants that extrapolate better to longer contexts. The proposed KERPLE self-attentions are closely related to ALiBi self-attention. In the ALiBi method a linear bias proportional to the distance between token positions n and m is added to the pre-softmax attention score for all position pairs n and m. The paper’s contribution is to consider non-linear bias terms: a logarithmic one and a power-law one. The theoretical justification of these specific terms is that with them (as well as with ALiBi) the pre-softmax attention computation can still be seen as kernel computation. \n\nThe key empirical result is that the log version of KERPLE attention achieves better log-likelihood on 3 language modelling tasks in a challenging extrapolation regime (train on length 512, test on 16K). The improvement upon ALiBi is very clear, the improvement upon T5-style bucketing is smaller, but noticeable. ", "questions": "Does the attention before softmax really have to be a kernel? My understanding is that an attention mechanism could be trained even if the underlying function is not a kernel. \n", "limitations": "Not sure if the paper's results can really be called \"extrapolation\".", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- well-written paper with a clear empirical result \n- nice connections to prior (ALiBi and T5 bucketing) and kernel literatures\nWeaknesses\n- it would be good to see how the presented extrapolation results compare to training with longer contexts. Do we observe extrapolation, or just slower degradation?\n- limited improvement upon T5 bucketing \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "BTnU-aYVue0", "reviewer": "Reviewer_adkx", "summary": "The paper proposes a family of relative position biases that can be viewed as shift-invariant CPD kernels. It proves that in the presence of softmax normalization, there is an equivalent formulation based on an inner product of position representations that lie in a latent feature space. Experimental results show that one kernel in this family results in a relative attention scheme that successfully extrapolates to longer sequences than were seen during training, whereas prior approaches to relative attention have more limited or even no generalization capability for longer sequences.", "questions": "Do you have any thoughts regarding my concerns about sliding-window attention effects?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The theoretical portion of the work presents a sound argument for why CPD kernels used in the context of softmax-normalized attention have an equivalent formulation in terms of inner products of position embeddings lying in a latent feature space. This family of kernels maintains the familiar structure of attention, as well as shift invariance, and the paper provides examples of kernels that lie in this family. Separately, the paper shows that 3-para-log variant within this family leads to models that effectively generalize to longer sequences, whereas prior approaches either do not generalize at all or have degraded generalization once the sequence length at inference is sufficiently large.\n\nOne potential concern regarding length extrapolation is that it's not clear whether the relative attention scheme in question could be exhibiting a windowing effect where all attention past a certain distance is effectively prohibited, and that cutoff length is smaller than the sequence length seen during training. Local attention based on sliding windows could actually be effective for dealing with longer sequences, because the effective context would still grow with each layer applied (like in Transformer-XL). As far as I can tell none of the baseline methods use sliding windows; they all seem to attempt to allow attention between very distant tokens with some extrapolation for what the relative bias should be. In that sense the baselines used could exhibit a failure mode that windowed attention simply does not have. The results would be stronger if they compared the proposed method to a window-based approach.\n\nAnother potential weakness of the paper is that the theoretical examination of CPD kernels and the empirical results on length extrapolation don't have the strongest of connections. The implementation of relative attention can use any relative biasing scheme of the form $bias = f(m - n)$, for any arbitrary function f (even bucketed/stepwise/other approaches, including T5), so it could be that the 3-para-log approach happens to work well for reasons that have limited or no relation to the theoretical portions of the paper. Likewise, the correspondence between CPD kernels and inner products doesn't appear to have any bearing on the practical implementation, which need not deal with inner products for the attention scheme.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept