# The Impact of Positional Encoding on Length Generalization in Transformers

Amirhossein Kazemnejad1,2, Inkit Padhi3
Karthikeyan Natesan Ramamurthy3, Payel Das3, Siva Reddy1,2,4
1Mila - Québec AI Institute; 2McGill University;
3IBM Research; 4Facebook CIFAR AI Chair
<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Length generalization, the ability to generalize from small training context
sizes to larger ones, is a critical challenge in the development of
Transformer-based language models. Positional encoding (PE) has been
identified as a major factor influencing length generalization, but the exact
impact of different PE schemes on extrapolation in downstream tasks remains
unclear. In this paper, we conduct a systematic empirical study comparing the
length generalization performance of decoder-only Transformers with five
different position encoding approaches including Absolute Position Embedding
(APE), T5’s Relative PE, ALiBi, and Rotary, in addition to Transformers
without positional encoding (NoPE). Our evaluation encompasses a battery of
reasoning and mathematical tasks. Our findings reveal that the most commonly
used positional encoding methods, such as ALiBi, Rotary, and APE, are not well
suited for length generalization in downstream tasks. More importantly, NoPE
outperforms other explicit positional encoding methods while requiring no
additional computation. We theoretically demonstrate that NoPE can represent
both absolute and relative PEs, but when trained with SGD, it mostly resembles
T5’s Relative PE attention patterns. Finally, we find that scratchpad is not
always helpful to solve length generalization and its format highly impacts
the model’s performance. Overall, our work suggests that explicit position
encodings are not essential for decoder-only Transformers to generalize well
to longer sequences.

##  1 Introduction

The ability to generalize from smaller training context sizes to larger ones,
commonly known as length generalization, is a major challenge for Transformer-
based language models (Vaswani et al., 2017; Deletang et al., 2023; Zhang et
al., 2023). Even with larger Transformers, this issue persists (Brown et al.,
2020; Furrer et al., 2020). With larger context sizes, a model can benefit
from more in-context-learning examples, higher numbers of reasoning and
planning steps, or longer text generation. However, training a Transformer
with a larger context size can be excessively slow and memory-intensive. This
is even more pronounced in the recent paradigm of model finetuning on
instruction-following datasets (Wei et al., 2022a; Chung et al., 2022; Ouyang
et al., 2022). It is not only infeasible to train the model on all possible
context lengths, but also the number of training examples drops dramatically
as the sequence length increases requiring the model to generalize from finite
and shorter-length training examples. In this work, we focus on the effect of
_positional encoding_ on length generalization in the “decoder-only"
Transformers on various tasks trained from scratch. Figure 1 summarizes our
finding that using no positional encoding is better than using explicit
positional encodings.

Positional encoding (PE) seems to be a major factor in the length
generalization of Transformers as the model has to systematically encode
tokens in _all_ possible positions. To this end, the original Transformer
architecture (Vaswani et al., 2017) used non-parametric periodic functions to
represent _absolute position embeddings_ (APE) in a systematic manner, but
further studies have shown that these functions are inadequate for length
generalization (Ontanon et al., 2022). The prevailing belief is that relative
PEs (Shaw et al., 2018; Raffel et al., 2020) are more effective in length
generalization than APE variants (Ontanon et al., 2022; Csordás et al., 2021).
However, recent work has shown that even Transformers with relative PEs, such
as Rotary (Su et al., 2021), are poor at length generalization and proposed
new position encoding schemes, ALiBi, that generalize well (Press et al.,
2022). But these studies use language modeling perplexity as the sole
evaluation metric which does not shed light on downstream task performance
(Tay et al., 2022). As a result, a key question arises: what exactly is the
influence of positional encoding on length generalization at various
downstream tasks? Moreover, since a decoder-only Transformer’s attention is
shown to model sequences without explicit position information (Tsai et al.,
2019), what is the effect of no positional encoding (NoPE)?

Recently, asking models to emit intermediate computation steps into a
scratchpad, also referred to as _chain-of-thought_ , has been adopted to
improve the length extrapolation in Transformers (Nye et al., 2021; Wei et
al., 2022b). These techniques are architecture-independent and can be used
with any positional encoding method. However, it remains an open question
whether these techniques, at least in regard to length generalization, render
the choice of positional encoding irrelevant, especially given that model
performance is highly sensitive to the scratchpad format (Bueno et al., 2022;
Akyurek and Akyurek, 2022).

\begin{overpic}[width=346.89731pt]{figures/paper_teaser.pdf} \put(76.0,17.0){
\begin{minipage}{130.08731pt} \scriptsize Positional Encodings \\\ used in
GPT3-style \\\ LLMs: \\\ BLOOM
(\cite[citeyear]{\@@bibref{Year}{Scao2022:BLOOM}{}{}}), \\\ PaLM
(\cite[citeyear]{\@@bibref{Year}{Chowdhery2022:PaLM}{}{}}), \\\ and LLaMA
(\cite[citeyear]{\@@bibref{Year}{Touvron2023:LLaMA}{}{}}). \end{minipage} }
\end{overpic} Figure 1:  No positional encoding (NoPE) outperforms all other
positional encodings at length generalization of decoder-only Transformers
(GPT-style) trained from scratch and evaluated on a battery of reasoning-like
downstream tasks. This figure shows aggregate ranking of positional encoding
methods across 10 tasks.

In this work, we conduct a systematic empirical study on the length
generalization of decoder-only Transformers, popularized by the GPT-family of
models (Radford et al., 2019), with the most commonly used positional encoding
schemes, both with and without scratchpad. Specifically, we evaluate APE
(Vaswani et al., 2017), T5’s Relative PE (Raffel et al., 2020), ALiBi (Press
et al., 2022), Rotary (Su et al., 2021) and NoPE on a battery of reasoning and
mathematical tasks. Our results show that:

  * •

Most commonly used positional encoding methods, including ALiBi, Rotary, and
APE, are ill-suited for length generalization in downstream tasks and are
outperformed by T5’s Relative PE.

  * •

Transformers without positional encoding (NoPE) outperform all explicit
positional encoding schemes. They achieve this without computing additional
terms in the attention mechanism (in contrast to explicit PEs).

  * •

We show that NoPE is theoretically capable of representing both absolute and
relative PEs. But empirically, it is closer to the relative encoding scheme
similar to T5’s Relative PE.

  * •

Scratchpad is not always helpful for length generalization and its format
highly impacts the performance. The attention distributions reveal that NoPE
and T5’s Relative PE encourage attending to both long and short-range
positions, ALiBi to recent positions, and Rotary and APE to no particular
positions.

##  2 Background: Positional Encoding in Transformers

Transformers, in contrast to sequential models such as RNNs, are parallel
architectures that employ positional encoding to help encode word order. The
most common choices for positional encoding are either _absolute_ , where each
absolute position (e.g. 1, 2, 3, …) is directly represented, or _relative_ ,
where the distance between tokens is used as positional information. In this
section, we briefly review the popular encoding methods used in Transformers
(Refer to Appendix B for more formal details).

_Absolute Position Embedding_ (APE), embeds each absolute position $i$ into
position vector ${\bm{p}}_{i}$ and adds word embeddings to their corresponding
${\bm{p}}_{i}$ before feeding them to the model. The non-parametric variant of
APE uses periodic functions such as sine and cosine to generate embeddings for
any position $i$ (Vaswani et al., 2017). On the other hand, a learned version
of APE, used in GPT3 (Brown et al., 2020) and OPT (Zhang et al., 2022), trains
the position embeddings along with the model parameters, and it cannot
generate a position embedding for unseen positions, so the context window is
set to a fixed length.

_T5’s Relative bias_ , first maps the relative distance $(i-j)$ between tokens
at positions $i$ and $j$ to a scalar bias value $b=f(i-j)$, where $f$ is a
lookup table. The relative bias $b$ (learned during training) then is added to
the dot product of the query and key in the self-attention mechanism. The
lookup table maps distances larger than a threshold to the same parameter to
enable generalization to unseen distances.

_Rotary_ , used in PaLM (Chowdhery et al., 2022) and LLaMA (Touvron et al.,
2023), rotates the query and key representations with an angle proportional to
their absolute positions before applying the dot product attention. As a
result of this rotation, the attention dot product will only depend on the
relative distance between tokens, effectively making it a relative positional
encoding (Su et al., 2021).

_ALiBi_ , used in BLOOM (Scao et al., 2022a), is similar to T5’s Relative Bias
but instead subtracts a scalar bias from the attention score. This bias grows
linearly with the distance between the query and key tokens. This, in effect,
creates a preference toward recent tokens (recency bias).

Note that encoder-only Transformers, such as BERT, become bag-of-words models
in the absence of positional encoding. However, decoder-only Transformers with
causal attention mask are not permutation invariant and can model sequences
even without explicit position information (Tsai et al., 2019). But it is
unclear if these models encode position information implicitly or generalize
to unseen lengths. We demystify this in Section 5.

##  3 Model Evaluation

#### Length Generalization Setup

Following Anil et al. (2022), we focus on algorithmic tasks such as copying,
addition, etc. For each task, we train on a finite number of examples of up to
a certain length and test them on both seen and unseen lengths at inference.
We present these problems as sequence-to-sequence tasks, where the input
sequence is the problem instance and the output sequence is the solution.
Formally, let $\mathcal{D}=\\{({\bm{x}}_{i},{\bm{y}}_{i})\\}$ denote a dataset
of such task where ${\bm{x}}_{i}$ is the input and ${\bm{y}}_{i}$ is the
output sequence. For each task a function
$\lambda:\mathcal{D}\rightarrow\mathbb{N}$ can be defined that returns the
length bucket of a task instance $d\in\mathcal{D}$. This can be the number of
tokens or any general notion of length/depth of reasoning. Using this function
and a threshold $L$, we employ samples where $\lambda\leq L$ for learning the
task and samples where $\lambda>L$ for evaluating generalization. The
performance on each instance is reported as the exact-match accuracy of its
answer with the ground truth.

Table 1: Examples of the input and output of the tasks.

Task | Input Example | Output Example
---|---|---
Primitive Tasks
Copy | Copy the following words: <w1> <w2> <w3> <w4> <w5> | <w1> <w2> <w3> <w4> <w5>
Reverse | Reverse the following words: <w1> <w2> <w3> <w4> <w5> | <w5> <w4> <w3> <w2> <w1>
Mathematical and Algroithmic Tasks
Addition | Compute: 5 3 7 2 6 + 1 9 1 7 ? | The answer is 5 5 6 4 3.
Polynomial Eval. | Evaluate x = 3 in ( 3 x ** 0 + 1 x ** 1 + 1 x ** 2 ) % 10 ? | The answer is 5.
Sorting | Sort the following numbers: 3 1 4 1 5 ? | The answer is 1 1 3 4 5.
Summation | Compute: ( 1 + 2 + 3 + 4 + 7 ) % 10 ? | The answer is 7.
Parity | Is the number of 1’s even in [ 1 0 0 1 1] ? | The answer is No.
LEGO | If a = -1; b = -a; c = +b; d = +c. Then what is c? | The answer is +1.
Classical Length Generalization Datasets
SCAN | jump twice and run left | JUMP JUMP TURN_LEFT RUN
PCFG | shift prepend K10 R1 K12 , E12 F16 | F16 K10 R1 K12 E12

#### Architecture

We use a conventional decoder-only Transformer architecture as a base for all
experiments and consider different approaches for encoding positions: Absolute
Position Embedding (APE), ALiBi, Rotary and T5’s Relative Bias. We also
consider removing the positional encoding (NoPE) to better understand its role
in length generalization. Note that we use APE with sinusoidal functions
(Vaswani et al., 2017) as the learnable variant cannot produce embeddings for
unseen positions. Given the absence of publicly available Transformer-based LM
trained with aforementioned PEs on the same pretraining data, we opt to train
our models from scratch for each task on its training data with the
autoregressive language modeling objective $\log
p_{\theta}({\bm{y}}|{\bm{x}})=\sum_{t=1}^{T}\log
p_{\theta}(y_{t}|{\bm{x}},{\bm{y}}_{1:t-1})$. We use the same hyperparameters
for all PEs and employ the “base” model size configuration, popular in
HuggingFace library (Wolf et al., 2020), resulting in $\sim$107M trainable
weights (List of all hyperparameters in Section D.2).

#### Tasks

Our study of length generalization is concentrated on downstream tasks.
Particularly, we evaluate the models on three categories (Table 1) of
synthetic tasks that have been widely used in the literature to investigate
length generalization: (1) Primitive tasks such as Copying and Reversing
(Ontanon et al., 2022), (2) Mathematical and reasoning tasks such as Addition
(Nye et al., 2021), Polynomial Evaluation, Sorting, Summation (Saxton et al.,
2019), Parity (Anil et al., 2022), LEGO (Zhang et al., 2023) and (3) Classical
length generalization datasets such as SCAN (Lake and Baroni, 2018) and PCFG
(Hupkes et al., 2020). These tasks provide us with complete control over the
train-test distribution, while also requiring reasoning and compositionality
skills, which serve as fundamental building blocks for more complex tasks. For
the first two categories, we generate the corresponding datasets.
Specifically, we first sample the length of the task instance from the uniform
distribution $\mathcal{U}(1,L)$, and then, according to the task’s generative
process, we sample the input and output sequences. For the test set, we follow
the same procedure but sample length from $\mathcal{U}(1,2L)$ to include both
seen and unseen lengths. Throughout the paper, unless otherwise stated, we use
$L=20$. For the third category of tasks, we use length generalization splits
from the corresponding datasets. Table 1 provides an example of each task
(More examples in Section D.1).

We report the results of our empirical evaluation over ten tasks and three
seeds per dataset-PE pair.

##  4 What Is The Effect of Positional Encoding?

In this section we provide comparative results of positional encodings at
length generalization. To provide a holistic view, following Liang et al.
(2022), we report the mean ranking of various models in Figures 1 and 2 when
compared against each other for all tasks and scenarios. Furthermore, we
showcase the accuracy of models evaluated on examples of various lengths in
Figure 3. (Detailed results for each task and scenario can be found in
Appendix E).

Figure 2:  Aggregate ranking of positional encoding methods on length
extrapolation across three different groups of tasks. No PE and T5’s Relative
Bias outperform other encoding methods in these categories.  Figure 3:
Showcasing the generalization behavior of different positional encodings on 6
datasets. The shaded area represents evaluation examples with I.I.D. lengths
(i.e. seen during training). Since all models perform perfectly, or close to
it, on the I.I.D. lengths (measured on unseen examples), for improved
readability, we only show a subset of them in the figure. Refer to Appendix E
for more detailed plots.

First, we observe that in most tasks, models achieve a perfect or near-perfect
accuracy (Figure 3) on the I.I.D. lengths, which indicates that models have no
problem fitting to the training data. However, the differences among
positional encoding methods become more apparent when we evaluate on lengths
that are larger than seen during training. In most extrapolation scenarios,
T5’s Relative Bias outperforms other explicit positional encodings. ALiBi
positions itself in the middle of the pack, while APE and Rotary show poor
generalization performance.

Although Rotary is often considered a relative encoding method (Ontanon et
al., 2022), our results show that it performs more similarly to APE than to
other relative schemes. Moreover, ALiBi, despite its promise for length
generalization, underperforms with respect to T5’s Relative Bias in most
cases. This result aligns with Taylor et al. (2022) who found no significant
improvement from ALiBi.

Surprisingly, the NoPE model, which is just a decoder-only Transformer without
any positional encoding, performs on par with or even better than the best-
performing explicit PE, T5’s Relative Bias. NoPE achieves the same level of
generalization without _any computational overhead_ since it does not compute
any additional term in the attention mechanism. This property has a direct
impact on the runtime and memory footprint of the model. For instance, Press
et al. (2022) reported that the additional computation incurred by T5’s
Relative Bias can make the training and inference time of the model almost two
times slower than the Transformer with APE.

##  5 How Does NoPE Represent Positions?

Figure 4:  Distance of NoPE attention patterns with other positional encoding
schemes measured across instances of SCAN dataset. The left figure shows the
distance per layer, and the right figure shows the average distance across all
layers. NoPE’ denotes NoPE trained with a different seed.

The surprising performance of NoPE model suggests that it capture useful
positional information that can also generalize. But, how it does so is the
primary question. In the next two sections, we provide theoretical and
empirical analysis towards answering this question.

###  5.1 NoPE can theoretically represent both absolute and relative PEs

Let $f_{\theta}$ be a NoPE decoder-only Transformer model, where $\theta$
denotes the model parameters. $f_{\theta}$ processes the input sequence
${\bm{x}}=\left[\texttt{<bos>},x_{1},\ldots,x_{T}\right]$ by applying a series
of layers. Note that since $f_{\theta}$ does not have any PE, the input
${\bm{x}}$ is not augmented with positional information (e.g.
$[1,2,\ldots,T]$). Each layer $l$, consisting of self-attention heads and a
feed-forward sub-layer, reads the previous hidden state ${\bm{H}}^{(l-1)}$ and
produces the hidden state at layer $l$: ${\bm{H}}^{l}$. Each head is
parameterized by a query ${\bm{W}}_{Q}$, key ${\bm{W}}_{K}$, value
${\bm{W}}_{V}$, and output ${\bm{W}}_{O}$ matrices, where
${\bm{W}}_{Q},{\bm{W}}_{K},{\bm{W}}_{V}\in\mathbb{R}^{h\times d}$ and
${\bm{W}}_{O}\in\mathbb{R}^{d\times h}$. $d$ and $h$ are the model’s hidden
state size and attention dimension, respectively.
${\bm{W}}_{1},{\bm{W}}_{2}\in\mathbb{R}^{d\times k.d}$ are the weight matrices
of the feed-forward sub-layer.

######  Theorem 1 (Absolute Encoding).

Let ${\bm{x}}$ be an input sequence of length $T+1$ to the model. Then, the
first layer of $f_{\theta}$ can recover absolute positions $[1,\ldots,T+1]$ in
the hidden state ${\bm{H}}^{(1)}$. That is, there exist ${\bm{W}}_{Q}$,
${\bm{W}}_{K}$, ${\bm{W}}_{V}$, ${\bm{W}}_{O}$, ${\bm{W}}_{1}$, and
${\bm{W}}_{2}$ such that the self-attention and feedforward operations in the
first layer compute absolute positions and write it to the next hidden state.

We refer to Section C.1 for the complete proof of 1. This theorem shows that
stochastic gradient descent (SGD) can potentially learn to recover absolute
positions in NoPE Transformers. Next, we demonstrate how relative PE can be
implemented in subsequent layers:

######  Theorem 2 (Relative Encoding).

Suppose that the hidden state ${\bm{H}}^{(1)}$ contains absolute positional
information, as stated in 1, and assume that it is not overwritten by any
subsequent layers. Then, the self-attention in all subsequent layers can
implement a relative positional encoding: there exists a parameterization of
$f_{\theta}$ such that, for $l\geq 2$, the attention dot product between query
${\bm{q}}_{n}$ and key ${\bm{k}}_{m}$ at positions $n$ and $m$ can be
expressed as: $\displaystyle\langle{\bm{q}}_{n},{\bm{k}}_{m}\rangle$
$\displaystyle=f_{\mathrm{cnt}}({\bm{q}},{\bm{k}})+f_{\mathrm{rel}}(n-m)\ $
(1) where $f_{\mathrm{cnt}}$ is a function of their content, and
$f_{\mathrm{rel}}$ is a function of their relative distance.

Section C.2 provides the complete proof of 2. Our theoretical results suggest
that SGD can choose between relative and absolute encoding in NoPE
Transformers. But, what mechanism SGD learns in practice is not clear. We next
investigate this question empirically.

###  5.2 NoPE learns to use relative PE in practice

In order to explore the mechanisms that NoPE employs in practice, we conduct a
quantitative analysis by comparing its attention pattern to models trained
with different positional encoding techniques. The hypothesis is that if NoPE
utilizes a similar algorithm to other PEs, then the attention patterns of
these models should be quite similar.

To this end, we feed the same input to both models and, at layer $l$, we
compute the minimum distance between the attention distribution of any heads
in the first model and any head in the second model. Formally, let
$\mathrm{P}_{t}=p({\bm{k}}|{\bm{q}}_{t})$ be a probability distribution
produced by a causal self-attention head for query at position $t$, over the
keys ${\bm{k}}\in[{\bm{k}}_{1},\dots\bm{k}_{t}]$ in a given transformer layer.
Over a sequence of length $T$, we define the similarity between two heads
$\mathrm{P}$ and $\mathrm{Q}$ as
$D_{\mathrm{AT}}(\mathrm{P},\mathrm{Q})=\frac{1}{T}\sum_{t=1}^{T}D_{\mathrm{JSD}}(\mathrm{P}_{t}||\mathrm{Q}_{t})$
which averages the Jensen–Shannon divergence (JSD) between the two heads over
all positions. For the distance of two models $A$ and $B$ at layer $l$, we
take the minimum distance between all pairs of attention heads in the
corresponding layer:

$\displaystyle D^{(l)}(A,B)$ $\displaystyle=\min_{(\mathrm{P},\mathrm{Q})\in
A_{l}\times B_{l}}D_{\mathrm{AT}}(\mathrm{P},\mathrm{Q})$ (2)

where $A_{l}$ and $B_{l}$ are the attention heads in layer $l$ of models $A$
and $B$ respectively. We empirically measure the distance between NoPE and
other positional encoding schemes after training. Specifically, we sample
examples from each length bucket and feed them (the concatenation gold input
and output) to compute the attention maps and the distance using Equation 2.
We also consider the distance between different seeds of NoPE as a baseline.
Figure 4 shows the distance per layer for the first four layers. (later layers
show similar trends Figure E.5). We find that NoPE’s attention patterns are
most similar to that of T5’s Relative PE, and least similar to APE and Rotary.
The same trend can be observed across all layers and length buckets, and even
when averaged across all layers. These results potentially suggest that a
Transformer model without positional encoding, trained with stochastic
gradient descent learns to represent positions in a way similar to T5’s
Relative PE, which is a relative positional encoding scheme.

##  6 Does Scratchpad Render The Choice of Positional Encoding Irrelevant?

Input (${\bm{x}}$)
Compute 5 3 7 2 6 + 1 9 1 7 = Output (${\bm{s}};{\bm{y}}$)
<scratch> $\mathcal{I}$$\mathcal{I}$ For digits 6 and 7,
$\mathcal{C}$$\mathcal{C}$ We have ( 6 + 7 + carry ) % 10 = 13 % 10 = 13 % 10
$\mathcal{O}$$\mathcal{O}$ Which is equal to 3 . $\mathcal{V}$$\mathcal{V}$ We
update carry to 13 // 10 = 1. $\mathcal{R}$$\mathcal{R}$ So, the remaining
input is 5 3 7 2 + 1 9 1 …
</scratch>
The answer is 5 5 6 4 3. Figure 5: Example of an addition task depicted with
its first scratchpad step. Each step consists of five components: AA Step
Input $\mathcal{I}$, AA Step Computation $\mathcal{C}$, AA Step Output
$\mathcal{O}$, AA Intermediate Variable Updates $\mathcal{V}$, and AA
Remaining Input $\mathcal{R}$.

In scratchpad/CoT prompting, the model generates intermediate computations
required to reach the final answer as explicit parts of the output. Such
mechanisms, in effect, provide a direct decomposition and storage for
intermediate values, which has been shown to improve the length generalization
of Transformers even at small scale (Nye et al., 2021). Since scratchpad only
modifies the model’s input and output (not the architecture), it is unclear
and unexplored how architectural choices such as positional encoding affect
the length generalization in the presence of scratchpad. To answer this
question, we train all PEs _with_ and _without_ scratchpad on the mathematical
and reasoning group of tasks, and compare their performance.

Moreover, the decision of how to represent the intermediate computations in
the scratchpad, i.e. the scratchpad format, is an important design choice that
has a non-trivial impact on the model’s performance (Bueno et al., 2022).

To account for those, we consider five components in each step of scratchpad:
<input>, <computation>, <output>, <variable_update>, and <remaining_input>
(Figure 5). In our experiments, we create different variations of scratchpad
format by enabling or disabling each component, which allows us to
systematically study their impact.111Since using scratchpad creates very long
sequences, we follow Nye et al. (2021) and set the length threshold $L=8$ for
tasks that use it to avoid out-of-memory errors. Figure 6 summarizes our
results. Similar to the remarks made by (Nye et al., 2021; Anil et al., 2022)
we observe that across all PEs and regardless of the format, scratchpad is
beneficial solely for the addition task. Additionally, our findings indicate
that having a positional encoding with robust length generalization is crucial
since scratchpad/CoT alone may not enhance the generalization.

Figure 6:  Mean ranks of scratchpad format aggregated across all models per
each dataset. The effectiveness of scratchpad is task dependent.

###  6.1 Which part of the sequence is attended to?

The scratchpad format that is often used (Nye et al., 2021), similar to Figure
5, contains redundant information. One such example is the repetition of the
remaining portion of an input ($\mathcal{R}$) in each step of the scratchpad.
But, the attention can attend to this information directly from the main
input. So, it remains unclear which specific part of the scratchpad different
PEs rely on to solve the task.

To address this question, we take the models trained with full Format on
addition, the case in which scratchpad is helpful across all PEs, and examine
their attentions. Specifically, for tokens in the output sequence, we
calculate the _distance $d$_ between the current query ${\bm{q}}_{t}$ and the
attended

Figure 7: Distribution of the normalized distance between the query and the
key of the self-attention (addition task + full scracthpad), averaged across
all layers and heads.

key ${\bm{k}}_{n}$ as $(t-n+1)$ and subsequently normalize it based on the
length of the sequence at the present step. The normalized value is denoted as
$\bar{d}$.

Figure 7 depicts the distribution of $\bar{d}$. Values of $\bar{d}$ close to 0
indicate attention to tokens near the current position (e.g. current
scratchpad step), while values close to 1 signify attention to distant tokens
(e.g. the input). NoPE and T5’s Relative PE resemble each other and exhibit a
bimodal distribution, reflecting both short-range and long-range attention.
Conversely, ALiBi (due to its recency bias) strongly favors short-range
attention. Rotary, on the other hand, produces a distribution resembling APE,
which is more uniformly distributed. Notably, NoPE and T5’s RPE are the top-
performing PEs in this setup, which suggest the bimodal distribution to be
more optimal.

##  7 Discussion

Practitioners have to make important choices about the nuances of the
Transformer architecture like positional encoding before undertaking the
costly pretraining process. In the I.I.D evaluation of PEs, we demonstrate
similar performance across different PEs, in line with observations of Haviv
et al. (2022) and Scao et al. (2022b), which makes the choice of optimal
positional encoding challenging. Moreover, human language processing may be
subject to cognitive constraints (Gibson, 1998; Gibson et al., 2019) that
could create a false impression of how well PEs can generalize over length in
natural language modeling evaluations. Indeed, Tay et al. (2022) showed that
perplexity is an inadequate proxy for downstream performance of LLMs.

In our paper, we utilize length generalization in downstream tasks as a means
to assess the expressivity of positional encodings. Our setup, in contrast to
the I.I.D. evaluation, reveals a clear distinction among approaches of
encoding positions. We find that NoPE outperforms explicit PEs, and within
explicit PEs, commonly used methods lag behind T5’s Relative PE. In fact, the
recent release of LLMs (Touvron et al., 2023; Chowdhery et al., 2022) suggests
a shift towards adopting Rotary as a replacement for APE in the Transformer
architecture. However, our result in Section 4 clearly demonstrates that
Rotary marginally outperforms APE at length generalization. Furthermore, it
exhibits similar behavior to APE, as shown in Section 6.1, indicating
potential susceptibility to the same limitations. Moreover, the _Recency Bias_
, embedded in positional encodings such as ALiBi, might be a reasonable choice
for modeling language, however, our results in Sections 4 and 6.1 show it
might not be optimal for length generalization for reasoning tasks.

The disadvantages of explicit PEs over NoPE in length extrapolation contribute
to the growing evidence that positional encodings pose challenges for
Transformers (Sinha et al., 2022; Luo et al., 2021). Our empirical results and
theoretical analysis suggest that removing positional encoding holds promise
as a modification to the widely used decoder-only Transformer architecture.

##  8 Related Work

#### Length Generalization Failure In Transformers

The length generalization problem has been a topic of interest in the study of
neural sequence models for a long time (Graves et al., 2016; Kaiser and
Sutskever, 2016; Lake and Baroni, 2018; Hupkes et al., 2020; Yehudai et al.,
2021). Transformers, being state-of-the-art sequence models, have been no
exception. A group of studies showed the generalization failure of
conventional Transformers with APE on specific datasets such as PCFG (Hupkes
et al., 2020), LEGO (Zhang et al., 2023), or CLUTRR (Sinha et al., 2019;
Gontier et al., 2020). The length generalization problem has been reported
even in pretrained Transformers such as T5 (Furrer et al., 2020) and LaMDA
(Anil et al., 2022). Csordás et al. (2021) and Ontanon et al. (2022) study the
effect of positional encoding on length generalization but mainly focus on
showing relative PE outperforms APEs. Press et al. (2022), on the other hand,
propose a new encoding method, ALiBi, and demonstrate that it outperforms
popular PEs on extrapolation but only in the context of human language
modeling. Most relevant is Deletang et al. (2023)’s recent study on length
generalization in various neural sequence models (including RNNs, Stacked-
RNNs) for tasks from Chomsky hierarchy. However, they do not analyze
positional encoding differences extensively or focus on autoregressive models.
Unlike these studies, our work extensively compares length generalization in
popular PEs for a wide range of tasks, specifically focusing on autoregressive
models, which represent many contemporary LLMs.

#### Positional Encoding

A core component of Transformers is the positional encoding mechanism, which
helps the model represent the order of the input sequence. Self-attention
mechanism in the encoder of Transformers is order-invariant and requires PE to
avoid becoming a bag-of-word model. Many methods have been proposed for this
purpose. Originally, Vaswani et al. (2017) introduced absolute positional
encoding sinusoidal functions (a learned variant popularized by Devlin et al.
(2019)). Relative approach for encoding positional information was further
introduced by Shaw et al. (2018), which gave rise to a number of pre-trained
LM with relative encodings such as TransformerXL (Dai et al., 2019) and T5
(Raffel et al., 2020) that perform well in length generalization. More
recently, Su et al. (2021) takes the concept of sinusoidal functions and
suggests a new way of encoding positional information by rotating the hidden
representations before applying self-attention. This method, referred to as
_Rotary_ , has become a popular choice in the recent LLMs. Press et al. (2022)
simplify the T5’s Relative encoding and introduced a more efficient variant
called ALiBi, while keeping the same or improving extrapolation performance.
Decoder-only Transformers, due to their causal attention mask, are not order-
agnostic and can be used without any positional encoding. This was observed
early on by Shen et al. (2018) and later confirmed by Tsai et al. (2019). In
our work, we theoretically show that they are capable of learning both
absolute and relative encoding.

##  9 Conclusion

We studied the robustness of different positional encodings, in decoder-only
Transformers, at length generalization on various downstream mathematical and
reasoning tasks. Our extensive empirical study shows the effectiveness of
NoPE, and further demonstrates that widely used explicit PEs are not suited
for length generalization. We also prove that NoPE can implicitly learn both
absolute and relative positions, but uses the latter in practice. Finally, we
find the effectiveness of scratchpad is task-dependent, and is not a reliable
solution for length generalization.

## Limitations

Our work primarily focuses on positional encodings as a design choice in the
Transformers decoder architecture. We could not study how large-scale
pretraining affects different PEs because there are no publicly available
large language models trained with various PEs under similar conditions. We
leave this for future work due to our limited compute budget.

## Acknowledgements

The Mila-IBM grant program provided the funding for this project. SR
acknowledges the support provided by the NSERC Discovery Grant program and the
Facebook CIFAR AI Chair program. This research was enabled in part by compute
resources provided by Mila and the Digital Research Alliance of Canada.

## References

  * Akyurek and Akyurek (2022) Ekin Akyurek and Afra Feyza Akyurek. 2022.  Notes on teaching gpt-3 adding numbers.
  * Akyurek et al. (2023) Ekin Akyurek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. 2023.  What learning algorithm is in-context learning? investigations with linear models.  In _The Eleventh International Conference on Learning Representations_.
  * Anil et al. (2022) Cem Anil, Yuhuai Wu, Anders Johan Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Venkatesh Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. 2022.  Exploring length generalization in large language models.  In _Advances in Neural Information Processing Systems_.
  * Ba et al. (2016) Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016.  Layer normalization.  _ArXiv_ , abs/1607.06450.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Bueno et al. (2022) Mirelle Candida Bueno, Carlos Gemmell, Jeff Dalton, Roberto Lotufo, and Rodrigo Nogueira. 2022.  Induced natural language rationales and interleaved markup tokens enable extrapolation in large language models.  In _Proceedings of the 1st Workshop on Mathematical Natural Language Processing (MathNLP)_ , pages 17–24, Abu Dhabi, United Arab Emirates (Hybrid). Association for Computational Linguistics.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2022.  Palm: Scaling language modeling with pathways.  _ArXiv_ , abs/2204.02311.
  * Chung et al. (2022) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al. 2022.  Scaling instruction-finetuned language models.  _ArXiv_ , abs/2210.11416.
  * Csordás et al. (2021) Róbert Csordás, Kazuki Irie, and Juergen Schmidhuber. 2021.  The devil is in the detail: Simple tricks improve systematic generalization of transformers.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 619–634, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Dai et al. (2019) Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. 2019.  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. Association for Computational Linguistics.
  * Deletang et al. (2023) Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A Ortega. 2023.  Neural networks and the chomsky hierarchy.  In _International Conference on Learning Representations_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  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 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Elhage et al. (2021) Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, et al. 2021.  A mathematical framework for transformer circuits.  _Transformer Circuits Thread_.
  * Furrer et al. (2020) Daniel Furrer, Marc van Zee, Nathan Scales, and Nathanael Schärli. 2020.  Compositional generalization in semantic parsing: Pre-training vs. specialized architectures.  _ArXiv_ , abs/2007.08970.
  * Gibson (1998) Edward Gibson. 1998.  Linguistic complexity: locality of syntactic dependencies.  _Cognition_ , 68(1):1–76.
  * Gibson et al. (2019) Edward Gibson, Richard Futrell, Steven P Piantadosi, Isabelle Dautriche, Kyle Mahowald, Leon Bergen, and Roger Levy. 2019.  How efficiency shapes human language.  _Trends in cognitive sciences_ , 23(5):389–407.
  * Gontier et al. (2020) Nicolas Gontier, Koustuv Sinha, Siva Reddy, and Christopher Pal. 2020.  Measuring systematic generalization in neural proof generation with transformers.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Graves et al. (2016) Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska-Barwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. 2016.  Hybrid computing using a neural network with dynamic external memory.  _Nature_ , 538(7626):471–476.
  * Haviv et al. (2022) Adi Haviv, Ori Ram, Ofir Press, Peter Izsak, and Omer Levy. 2022.  Transformer language models without positional encodings still learn positional information.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 1382–1390, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Hendrycks and Gimpel (2020) Dan Hendrycks and Kevin Gimpel. 2020.  Gaussian error linear units (gelus).  _ArXiv_ , abs/1606.08415.
  * Hupkes et al. (2020) Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. 2020.  Compositionality decomposed: How do neural networks generalise? _Journal of Artificial Intelligence Research_ , 67:757–795.
  * Kaiser and Sutskever (2016) Lukasz Kaiser and Ilya Sutskever. 2016.  Neural gpus learn algorithms.  In _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_.
  * Lake and Baroni (2018) Brenden M. Lake and Marco Baroni. 2018.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 2879–2888. PMLR.
  * Liang et al. (2022) Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, et al. 2022.  Holistic evaluation of language models.  _ArXiv_ , abs/2211.09110.
  * Lindner et al. (2023) David Lindner, János Kramár, Matthew Rahtz, Thomas McGrath, and Vladimir Mikulik. 2023.  Tracr: Compiled transformers as a laboratory for interpretability.  _ArXiv_ , abs/2301.05062.
  * Longpre et al. (2023) Shayne Longpre, Le Hou, Tu Vu, Albert Webson, Hyung Won Chung, Yi Tay, Denny Zhou, Quoc V. Le, Barret Zoph, Jason Wei, and Adam Roberts. 2023.  The flan collection: Designing data and methods for effective instruction tuning.  _ArXiv_ , abs/2301.13688.
  * Luo et al. (2021) Ziyang Luo, Artur Kulmizev, and Xiaoxi Mao. 2021.  Positional artefacts propagate through masked language model embeddings.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 5312–5327, Online. Association for Computational Linguistics.
  * Nye et al. (2021) Maxwell Nye, Anders Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. 2021.  Show your work: Scratchpads for intermediate computation with language models.  _ArXiv_ , abs/2112.00114.
  * Ontanon et al. (2022) Santiago Ontanon, Joshua Ainslie, Zachary Fisher, and Vaclav Cvicek. 2022.  Making transformers solve compositional tasks.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 3591–3607, Dublin, Ireland. Association for Computational Linguistics.
  * Ouyang et al. (2022) Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. 2022.  Training language models to follow instructions with human feedback.  _ArXiv_ , abs/2203.02155.
  * Park et al. (2020) Sejun Park, Chulhee Yun, Jaeho Lee, and Jinwoo Shin. 2020.  Minimum width for universal approximation.  _ArXiv_.
  * Press et al. (2022) Ofir Press, Noah A. Smith, and Mike Lewis. 2022.  Train short, test long: Attention with linear biases enables input length extrapolation.  In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.  _OpenAI Blog_ , 1(8):9.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21:140:1–140:67.
  * Saxton et al. (2019) David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. 2019.  Analysing mathematical reasoning abilities of neural models.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net.
  * Scao et al. (2022a) Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilić, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Matthias Gallé, et al. 2022a.  Bloom: A 176b-parameter open-access multilingual language model.  _ArXiv_ , abs/2211.05100.
  * Scao et al. (2022b) Teven Le Scao, Thomas Wang, Daniel Hesslow, Lucile Saulnier, Stas Bekman, M Saiful Bari, Stella Biderman, Hady Elsahar, Jason Phang, Ofir Press, Colin Raffel, Victor Sanh, Sheng Shen, Lintang Sutawika, Jaesung Tae, Zheng Xin Yong, Julien Launay, and Iz Beltagy. 2022b.  What language model to train if you have one million GPU hours? In _Challenges & Perspectives in Creating Large Language Models_.
  * Shaw et al. (2018) Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. 2018.  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 2 (Short Papers)_ , pages 464–468, New Orleans, Louisiana. Association for Computational Linguistics.
  * Shen et al. (2018) Tao Shen, Tianyi Zhou, Guodong Long, Jing Jiang, Shirui Pan, and Chengqi Zhang. 2018\.  Disan: Directional self-attention network for rnn/cnn-free language understanding.  In _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018_ , pages 5446–5455. AAAI Press.
  * Sinha et al. (2022) Koustuv Sinha, Amirhossein Kazemnejad, Siva Reddy, Joelle Pineau, Dieuwke Hupkes, and Adina Williams. 2022.  The curious case of absolute position embeddings.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 4449–4472, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Sinha et al. (2019) Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. 2019.  CLUTRR: A diagnostic benchmark for inductive reasoning from text.  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 4506–4515, Hong Kong, China. Association for Computational Linguistics.
  * Su et al. (2021) Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu. 2021.  Roformer: Enhanced transformer with rotary position embedding.  _ArXiv_ , abs/2104.09864.
  * Tay et al. (2022) Yi Tay, Mostafa Dehghani, Jinfeng Rao, William Fedus, Samira Abnar, Hyung Won Chung, Sharan Narang, Dani Yogatama, Ashish Vaswani, and Donald Metzler. 2022\.  Scale efficiently: Insights from pretraining and finetuning transformers.  In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net.
  * Taylor et al. (2022) Ross Taylor, Marcin Kardas, Guillem Cucurull, Thomas Scialom, Anthony Hartshorn, Elvis Saravia, Andrew Poulton, Viktor Kerkez, and Robert Stojnic. 2022\.  Galactica: A large language model for science.  _ArXiv_ , abs/2211.09085.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023.  LLaMA: Open and efficient foundation language models.  _ArXiv_ , abs/2302.13971.
  * Tsai et al. (2019) Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhutdinov. 2019.  Transformer dissection: An unified understanding for transformer’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 4344–4353, Hong Kong, China. Association for Computational Linguistics.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 5998–6008.
  * Wang et al. (2022) Yizhong Wang, Swaroop Mishra, Pegah Alipoormolabashi, Yeganeh Kordi, Amirreza Mirzaei, Atharva Naik, Arjun Ashok, Arut Selvan Dhanasekaran, Anjana Arunkumar, David Stap, et al. 2022.  Super-NaturalInstructions: Generalization via declarative instructions on 1600+ NLP tasks.  In _Proc. of EMNLP_ , pages 5085–5109, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Wei et al. (2022a) Jason Wei, Maarten Bosma, Vincent Y. Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M. Dai, and Quoc V. Le. 2022a.  Finetuned language models are zero-shot learners.  In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net.
  * Wei et al. (2022b) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou. 2022b.  Chain of thought prompting elicits reasoning in large language models.  In _Advances in Neural Information Processing Systems_.
  * Weiss et al. (2021) Gail Weiss, Yoav Goldberg, and Eran Yahav. 2021.  Thinking like transformers.  In _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 11080–11090. PMLR.
  * Wolf et al. (2020) 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. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Yehudai et al. (2021) Gilad Yehudai, Ethan Fetaya, Eli A. Meirom, Gal Chechik, and Haggai Maron. 2021\.  From local structures to size generalization in graph neural networks.  In _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 11975–11986. PMLR.
  * Zhang et al. (2022) Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer. 2022.  Opt: Open pre-trained transformer language models.  _ArXiv_ , abs/2205.01068.
  * Zhang et al. (2023) Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. 2023.  Unveiling transformers with lego: a synthetic reasoning task.  _ArXiv_ , abs/2206.04301.

##  Appendix A Number of instances decreases rapidly as sequence length grows

Figure A.1:  Histogram of instruction lengths in two instruction finetuning
datasets: FLAN (CoT subset) (Longpre et al., 2023) and Super Natural
Instructions (Wang et al., 2022). The dotted line indicates the median length
of the instructions in each dataset.

The recent trend of SFT-RLHF pipeline (Ouyang et al., 2022) relies on
finetuning LLMs on the instruction following tasks. However, the training data
of these datasets is often skewed towards shorter sequences. Figure A.1 shows
the distribution of instruction lengths in two instruction finetuning
datasets: FLAN (CoT subset) (Longpre et al., 2023) and Super Natural
Instructions (Wang et al., 2022). The median length of instructions in these
datasets is quite short compared to the maximum length that exists. Such
distribution shape highlights the importance of length generalization in these
tasks. In fact, the models are supposed to learn from short instructions and
generalize to ones during inference that might be much longer.

##  Appendix B Background

###  B.1 Preliminaries

In this section, we lay the groundwork and introduce the notation we use
throughout the paper. We will refer to this in Sections C.1 and C.2.

Let $f_{\theta}$ be a decoder-only Transformer model, where $\theta$ denotes
the full set of model parameters. $f_{\theta}$ processes the input sequence
${\bm{x}}=\left[x_{0},x_{1},\ldots,x_{T}\right]$ and maps it to the output
sequence ${\bm{y}}=\left[y_{0},y_{1},\ldots,y_{T}\right]$ by applying a
sequence of Transformer layers. Note that being decoder-only means the
attention mechanism in each layer is causal, i.e. the attention weights are
computed based on the previous positions only.

The layer $\mathrm{TLayer}^{(l)}({\bm{H}}^{(l-1)};\theta_{l})$, consisting of
self-attention heads and a feed-forward sub-layer, reads the previous hidden
state ${\bm{H}}^{(l-1)}$ and produces the hidden state at layer $l$:
${\bm{H}}^{l}$, where $l$ is the layer index, and $\theta_{l}$ is the set of
parameters of the $l$-th layer. Each hidden state
${\bm{H}}^{(l)}\in\mathbb{R}^{d\times(T+1)}$ is matrix where column $t$,
denoted as ${\bm{h}}_{t}^{(l)}$, is the hidden state at position $t$.

A layer $l$ is parameterized by a set of parameters
$\theta_{l}=\\{({\bm{W}}_{Q}^{m},{\bm{W}}_{K}^{m},{\bm{W}}_{V}^{m},{\bm{W}}_{O}^{m})_{m},{\bm{W}}_{1},{\bm{W}}_{2}\\}$,
where
${\bm{W}}_{Q}^{m},{\bm{W}}_{K}^{m},{\bm{W}}_{V}^{m}\in\mathbb{R}^{h\times d}$
and ${\bm{W}}_{O}^{m}\in\mathbb{R}^{d\times h}$ are the query, key, value, and
output matrices of the $m$-th head, respectively.
${\bm{W}}_{1},{\bm{W}}_{2}\in\mathbb{R}^{d\times k.d}$ are the weight matrices
of the feed-forward sub-layer. $d$ denotes the model’s hidden state size, $h$
is the attention dimension (where $h=\frac{d}{\text{\\# heads}}$), and $k$ is
a multiplier of the hidden state size in the feed-forward sub-layer (it is
usually set to 4 in common implementations of the Transformer). Note that we
drop the layer index $l$ and the attention head index $m$ where it is clear
from the context.

The Transformer layer $\mathrm{TLayer}^{(l)}$ processes each column of
${\bm{H}}^{(l-1)}$ independently and in parallel to produce the output. The
computation of the $t$-th column of ${\bm{H}}^{(l)}$ is as follows:

$\displaystyle{\bm{h}}_{t}^{(l)}=\mathrm{FF}(\lambda({\bm{a}}_{t}+{\bm{h}}_{t}^{(l-1)}))+{\bm{a}}_{t}+{\bm{h}}_{t}^{(l-1)}$
(3)

where $\mathrm{FF}$ is the feed-forward sub-layer, $\lambda$ is layer
normalization, and ${\bm{a}}_{t}\in\mathbb{R}^{d}$ is the output of the multi-
head self-attention sub-layer at position $t$. Specifically, ${\bm{a}}_{t}$ is
computed as:

$\displaystyle{\bm{a}}_{t}=\sum_{m}\mathrm{Attn}^{(m)}({\bm{h}}_{t}^{(l-1)},{\bm{H}}^{(l-1)})$
(4)

where $\mathrm{Attn}^{(m)}$ is the $m$-th attention head. Let
${\bm{o}}_{t}\in\mathbb{R}^{d}$ denote the output of an attention head at
position $t$. Then, ${\bm{o}}_{t}$ is computed as:

$\displaystyle{\bm{o}}_{t}={\bm{W}}_{O}\left(\sum_{i\leq
t}\hat{{\bm{\alpha}}}_{i}{\bm{v}}_{i}\right)$ (5)

where
$\hat{{\bm{\alpha}}}=\mathrm{softmax}({\bm{\alpha}})\in\mathbb{R}^{(t+1)}$,
and ${\bm{\alpha}}$ is the attention weight vector such that:

$\displaystyle{\bm{\alpha}}=\left[\langle{\bm{q}}_{t},{\bm{k}}_{0}\rangle,\langle{\bm{q}}_{t},{\bm{k}}_{1}\rangle,\ldots,\langle{\bm{q}}_{t},{\bm{k}}_{t}\rangle\right]^{\intercal}$
(6)

where ${\bm{q}}_{t}={\bm{W}}_{Q}{\bm{h}}_{t}^{(l-1)}\in\mathbb{R}^{h}$,
${\bm{k}}_{i}={\bm{W}}_{K}{\bm{h}}_{i}^{(l-1)}\in\mathbb{R}^{h}$, and
${\bm{v}}_{i}={\bm{W}}_{V}{\bm{h}}_{i}^{(l-1)}\in\mathbb{R}^{h}$.
$\langle\cdot,\cdot\rangle$ denotes the dot product operation.

The feed-forward sub-layer $\mathrm{FF}(\cdot)\in\mathbb{R}^{d}$ is a two-
layer MLP:

$\displaystyle\mathrm{FF}({\bm{x}})={\bm{W}}_{2}\sigma({\bm{W}}_{1}^{\intercal}{\bm{x}})$
(7)

where $\sigma$ is a non-linear activation function (usually ReLU or GeLU
(Hendrycks and Gimpel, 2020)). Additionally, $\lambda(\cdot)\in\mathbb{R}^{d}$
is layer normalization (Ba et al., 2016). Note that we take the _additive_
(Elhage et al., 2021) view of attention heads in Equation 4 instead of
_concatenate and multiple_ view (Vaswani et al., 2017) as it is easier to
understand and analyze. But, they are mathematically equivalent (Elhage et
al., 2021).

The hidden state is initialized with a learned embedding of the input sequence
${\bm{H}}^{(0)}={\bm{W}}_{E}{\bm{X}}$, where
${\bm{W}}_{E}\in\mathbb{R}^{d\times V}$ is the embedding matrix and
${\bm{X}}\in\mathbb{R}^{V\times(T+1)}$ is the one-hot encoded input sequence.
$V$ is the vocabulary size.

###  B.2 Positional Encoding

Almost all positional encoding methods can be explained and formulated as how
they implement the dot product operation in Equation 6. So, in this section,
we explain how the dot product $\langle{\bm{q}}_{t},{\bm{k}}_{i}\rangle$ is
implemented in different positional encoding schemes.

#### Absolute Positional Encoding (APE)

The process of Absolute Positional Encoding (APE) involves assigning a
position vector ${\bm{p}}_{i}$ to each absolute position $i$ and combining
them with word embeddings before inputting them into the model. So, APE first
modifies how the hidden state is initialized:

$\displaystyle{\bm{H}}^{(0)}={\bm{W}}_{E}{\bm{X}}+{\bm{W}}_{P}{\bm{P}}$ (8)

where ${\bm{W}}_{P}\in\mathbb{R}^{d\times T}$ is the positional embedding
matrix and ${\bm{P}}\in\mathbb{R}^{V_{p}\times(T+1)}$ is the one-hot encoded
absolute position sequence. $V_{p}$ is the maximum absolute position.
Therefore, the hidden state at column $j$ is:

$\displaystyle{\bm{h}}_{j}^{(0)}={\bm{e}}_{j}+{\bm{p}}_{j}$ (9)

where ${\bm{e}}_{j}\in\mathbb{R}^{d}$ is the word embedding of token $x_{j}$
and ${\bm{p}}_{j}\in\mathbb{R}^{d}$ is the positional embedding for position
$j$. Then, the dot product for the first layer in Equation 6 is computed as:

$\displaystyle\langle{\bm{q}}_{t},{\bm{k}}_{i}\rangle$
$\displaystyle=\langle{\bm{W}}_{Q}{\bm{h}}_{t}^{(0)},{\bm{W}}_{K}{\bm{h}}_{i}^{(0)}\rangle$
$\displaystyle=\langle{\bm{W}}_{Q}({\bm{e}}_{t}+{\bm{p}}_{t}),{\bm{W}}_{K}({\bm{e}}_{i}+{\bm{p}}_{i})\rangle$
$\displaystyle=\left({\bm{W}}_{Q}({\bm{e}}_{t}+{\bm{p}}_{t})\right)^{\intercal}\left({\bm{W}}_{K}({\bm{e}}_{i}+{\bm{p}}_{i})\right)$
$\displaystyle={\bm{e}}_{t}^{\intercal}{\bm{W}}_{Q}^{\intercal}{\bm{W}}_{K}{\bm{e}}_{i}+{\bm{e}}_{t}^{\intercal}{\bm{W}}_{Q}^{\intercal}{\bm{W}}_{K}{\bm{p}}_{i}$
$\displaystyle\phantom{=}+{\bm{p}}_{t}^{\intercal}{\bm{W}}_{Q}^{\intercal}{\bm{W}}_{K}{\bm{e}}_{i}+{\bm{p}}_{t}^{\intercal}{\bm{W}}_{Q}^{\intercal}{\bm{W}}_{K}{\bm{p}}_{i}$

In the learned variant of APE, ${\bm{p}}_{j}\in\mathbb{R}^{d}$ is learned
during training. In the sinusoidal variant, ${\bm{p}}_{j}$ is calculated using
a non-parametric function. Specifically, ${\bm{p}}_{j}$ is computed as:

$\displaystyle{\bm{p}}_{j}=\left[\sin(\omega_{1}.j),\cos(\omega_{1}.j),\sin(\omega_{2}.j),\cos(\omega_{2}.j),\ldots,\sin(\omega_{d/2}.j),\cos(\omega_{d/2}.j)\right]^{\intercal}$
(11)

where $\omega_{i}=\frac{1}{10000^{2i/d}}$.

#### T5’s Relative PE

The Relative bias in T5 is a type of relative positional encoding that
initially calculates the relative distance $(t-i)$ between tokens at positions
$t$ and $i$. This distance is then transformed into a scalar bias value $b$
and is incorporated into the dot product between the query and key. $b$ is
learned during training. Thus, the dot product in every layer can be written
as:

$\displaystyle\langle{\bm{q}}_{t},{\bm{k}}_{i}\rangle$
$\displaystyle={\bm{q}}_{t}^{\intercal}{\bm{k}}_{i}+b_{\mathrm{bucket}(n-m)}$
(12)

where

$\mathrm{bucket}(n)=\begin{cases}n&\text{if}\ n<\frac{\mathcal{B}}{2}\\\
\frac{\mathcal{B}}{2}+\left\lfloor\frac{\log{\left(\frac{n}{\mathcal{B}/2}\right)}}{\log{\left(\frac{\mathcal{D}}{\mathcal{B}/2}\right)}}\times\frac{\mathcal{B}}{2}\right\rfloor&\text{if}\
\frac{\mathcal{B}}{2}\leq n<\mathcal{D}\\\ \mathcal{B}-1&\text{if}\
n\geq\mathcal{D}\end{cases}$

This function maps the relative distance $d$ to a bucket index, which will be
used to look up the weight corresponding to that bucket. $\mathcal{B}$ is the
number of buckets, $\mathcal{D}$ is the maximum distance. It assigns half of
the buckets to distances smaller than $\frac{\mathcal{D}}{2}$ with linear
spacing and the other half to distances larger than $\frac{\mathcal{D}}{2}$
with logarithmic spacing. The weight for distances larger than $\mathcal{D}$
is the same. This is to facilitate generalization to unseen distances. In the
original implementation of T5, $\mathcal{B}=32$ and $\mathcal{D}=128$.
Following shows an example of the bucket function with $\mathcal{B}=5$ and
$\mathcal{D}=6$:

$\mathrm{bucket}(\begin{bmatrix}0&0&0&0&0&0&0&0&0&0\\\ 1&0&0&0&0&0&0&0&0&0\\\
2&1&0&0&0&0&0&0&0&0\\\ 3&2&1&0&0&0&0&0&0&0\\\ 4&3&2&1&0&0&0&0&0&0\\\
5&4&3&2&1&0&0&0&0&0\\\ 6&5&4&3&2&1&0&0&0&0\\\ 7&6&5&4&3&2&1&0&0&0\\\
8&7&6&5&4&3&2&1&0&0\\\ 9&8&7&6&5&4&3&2&1&0\\\
\end{bmatrix})=\begin{bmatrix}0&0&0&0&0&0&0&0&0&0\\\ 1&0&0&0&0&0&0&0&0&0\\\
2&1&0&0&0&0&0&0&0&0\\\ 3&2&1&0&0&0&0&0&0&0\\\ 3&3&2&1&0&0&0&0&0&0\\\
4&3&3&2&1&0&0&0&0&0\\\ 4&4&3&3&2&1&0&0&0&0\\\ 4&4&4&3&3&2&1&0&0&0\\\
4&4&4&4&3&3&2&1&0&0\\\ 4&4&4&4&4&3&3&2&1&0\end{bmatrix}$

#### ALiBi

Similar to T5’s Relative PE, ALiBi subtracts a scalar bias from the attention
score. As the distance between the query and key tokens increases, the bias
grows linearly. Specifically, the dot product in every layer can be written
as:

$\displaystyle\langle{\bm{q}}_{t},{\bm{k}}_{i}\rangle$
$\displaystyle={\bm{q}}_{t}^{\intercal}{\bm{k}}_{i}-(t-i).C^{(m+1)}$ (13)

where $m$ is head index and $C$ is a constant defined as:

$C=2^{-2^{-\log_{2}(\text{\\# heads}+3)}}$

For example, if the number of heads is 8, then we have
$\frac{1}{2},\frac{1}{2^{2}},\dots,\frac{1}{2^{8}}$ (Press et al., 2022).

#### Rotary

The Rotary is a relative PE that applies a rotation to the query and key
representations based on their absolute positions before dot product
attention. Due to this rotation, the attention dot product relies solely on
the relative distance between tokens.

First, we formulate Rotary for model dimension $d=2$. Rotary positional
encoding defines the dot product as:

$\displaystyle\langle{\bm{q}}_{t},{\bm{k}}_{i}\rangle=$
$\displaystyle\langle\mathrm{Rot}({\bm{q}}_{t},t),\mathrm{Rot}({\bm{k}}_{i},i)\rangle$
$\displaystyle=$
$\displaystyle\langle{\bm{R}}^{t\theta}{\bm{q}}_{t},{\bm{R}}^{i\theta}{\bm{k}}_{i}\rangle$
$\displaystyle=$
$\displaystyle({\bm{R}}^{t\theta}{\bm{q}}_{t})^{\intercal}({\bm{R}}^{i\theta}{\bm{k}}_{i})$
$\displaystyle=$
$\displaystyle{{\bm{q}}_{t}}^{\intercal}({\bm{R}}^{t\theta})^{\intercal}{\bm{R}}^{i\theta}{\bm{k}}_{i}$
$\displaystyle=$
$\displaystyle{{\bm{q}}_{t}}^{\intercal}{\bm{R}}^{(i-t)\theta}{\bm{k}}_{i}$

where ${\bm{R}}^{t\theta}$ is a rotation matrix that rotates ${\bm{x}}$ by
$t\theta$ radians:

$\displaystyle{\bm{R}}^{n\theta}=\begin{bmatrix}\cos(n\theta)&-\sin(n\theta)\\\
\sin(n\theta)&\cos(n\theta)\end{bmatrix}$ (15)

for $d>2$, Rotary applies the same approach on every two consecutive
dimensions of ${\bm{q}}_{t}$ and ${\bm{k}}_{i}$, but with different $\theta$
angles. Refer to Su et al. (2021) for the exact formulation.

#### NoPE

NoPE does not explicitly encode positional encodings. So, the dot product in
every layer can be written as:

$\displaystyle\langle{\bm{q}}_{t},{\bm{k}}_{i}\rangle$
$\displaystyle={\bm{q}}_{t}^{\intercal}{\bm{k}}_{i}$ (16)

##  Appendix C Proofs

In this section, we provide proof of why NoPE can implicitly learn both
absolute and relative positions. We refer the readers to Section B.1 for the
notation and definitions used in this section.

###  C.1 Absolute Positional Encoding in NoPE

This section discusses how NoPE can recover absolute positions in the hidden
state. Our proof is inspired by Weiss et al. (2021); Lindner et al. (2023) and
relies on the causal attention mask in the decoder-only Transformer and the
$\mathrm{softmax}$ function to recover absolute positions.

[Absolute Encoding]thmEncodeAbsolute Let
${\bm{x}}=\left[\texttt{<bos>},x_{1},\ldots,x_{T}\right]$ be an input sequence
of length $T+1$ to the model. Then, the first layer of $f_{\theta}$ can
recover absolute positions $[1,\ldots,T+1]$ in the hidden state
${\bm{H}}^{(1)}$. That is, there exist ${\bm{W}}_{Q}$, ${\bm{W}}_{K}$,
${\bm{W}}_{V}$, ${\bm{W}}_{O}$, ${\bm{W}}_{1}$, and ${\bm{W}}_{2}$ such that
the self-attention and feedforward operations in the first layer compute
absolute positions and write it to the next hidden state.

Proof.

Our proof only specifies the weights of a single attention head in the first
layer (and additionally the parameterization of feedforward sub-layer). In
this parameterization, we only require the first three dimensions of the
hidden states. The rest of the heads, as long as they do not override the
first three dimensions, can be arbitrary. This does not impose any challenges
as Transformers used in practice usually have a very large model dimension
$d$. In the rest, we provide the construction of the weights and then verify
that they can recover absolute positions.

First, we construct the word embedding matrix
${\bm{W}}_{E}\in\mathbb{R}^{d\times V}$, where each column is the embedding of
a token in the vocabulary. We construct ${\bm{W}}_{E}$ such that it always
sets the first dimension of every embedding vector to be 1. Additionally, it
sets the second dimension to 1 if and only if the token is <bos>. Otherwise,
it sets it to zero. The third dimension of all embedding vectors is set to
zero. Other dimensions can take any arbitrary values. Without loss of
generality, assume <bos> is the first token in the vocabulary, i.e. The first
column. Then, we have:

$\displaystyle{\bm{W}}_{E}=\begin{bmatrix}1&1&1&\dots&1\\\ 1&0&0&\dots&0\\\
0&0&0&\dots&0\\\ e_{4,1}&e_{4,2}&e_{4,3}&\dots&e_{4,V}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
e_{d,1}&e_{d,2}&e_{d,2}&\dots&e_{d,V}\end{bmatrix}_{d\times V}$ (17)

where $e_{d,i}\in\mathbb{R}$.

Secondly, for head dimensions $h\geq 1$, we construct the weights
${\bm{W}}_{Q},{\bm{W}}_{K},{\bm{W}}_{V},{\bm{W}}_{O}$ of the first attention
head in the first layer. Specifically,

$\displaystyle\begin{array}[]{ccc}{\bm{W}}_{K}=\begin{bmatrix}1&0&\dots&0\\\
1&0&\dots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
1&0&\dots&0\end{bmatrix}_{h\times
d}&{\bm{W}}_{V}=\begin{bmatrix}0&1&0&\dots&0\\\ 0&0&0&\dots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ 0&0&0&\dots&0\end{bmatrix}_{h\times
d}\end{array}$ (19)

${\bm{W}}_{K}$ reads from the first dimension of the hidden state, which is
initialized with 1 using the embedding matrix. Since all word embeddings have
one in their first dimension, this parameterization will result all key
vectors to be the same. Moreover, ${\bm{W}}_{V}$ reads from the second
dimension of the hidden state, which is initialized with 1 if the token is
<bos>. So, the value vector will have 1 in its first dimension only if the
corresponding token is <bos>.

${\bm{W}}_{Q}$ can be any arbitrary matrix. ${\bm{W}}_{O}$ will write the
result of the attention to the third dimension of the hidden state and can be
constructed as:

$\displaystyle{\bm{W}}_{O}=\begin{bmatrix}0&0&0&0&\dots&0\\\
0&0&0&0&\dots&0\\\ 1&0&0&0&\dots&0\\\ 0&0&0&0&\dots&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&0&\dots&0\end{bmatrix}_{d\times h}$ (20)

Now, we verify that for any input sequence
${\bm{x}}=\left[\texttt{<bos>},x_{1},\ldots,x_{T}\right]$, the first layer can
recover absolute positions $[1,\ldots,T+1]$ in the hidden state
${\bm{H}}^{(1)}$. We verify this for column $t$ of ${\bm{H}}^{(1)}$. That is,
we show that absolute position information is available in the third dimension
of ${\bm{h}}_{t}^{(1)}$.

First, we use the word embedding matrix ${\bm{W}}_{E}$ to compute the
embedding ${\bm{H}}^{(0)}$:

$\displaystyle{\bm{H}}^{(0)}={\bm{W}}_{E}{\bm{X}}=\begin{bmatrix}1&1&1&\dots&1\\\
1&0&0&\dots&0\\\ 0&0&0&\dots&0\\\ e_{4,1}&e_{4,2}&e_{4,3}&\dots&e_{4,V}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
e_{d,1}&e_{d,2}&e_{d,2}&\dots&e_{d,V}\end{bmatrix}_{d\times(T+1)}$ (21)

We now provide the attention computation at position $1\leq t\leq T+1$. First,
we use ${\bm{W}}_{Q}$ to compute the query vector ${\bm{q}}_{t}$ by applying
${\bm{q}}_{t}={\bm{W}}_{Q}{\bm{h}}_{t}^{(0)}$:

$\displaystyle{\bm{q}}_{t}=[q_{1},q_{2},q_{3},\dots,q_{h}]^{\intercal}$ (22)

Recall that ${\bm{W}}_{Q}$ can be any arbitrary matrix. So,
$q_{j}\in\mathbb{R}$ can take any arbitrary value. Next, we compute the key
vectors by applying ${\bm{k}}_{i}={\bm{W}}_{K}{\bm{h}}_{i}^{(0)}$:

$\displaystyle\begin{array}[]{cccc}{\bm{k}}_{1}=\begin{pmatrix}1\\\ 1\\\
\vdots\\\ 1\end{pmatrix}&{\bm{k}}_{2}=\begin{pmatrix}1\\\ 1\\\ \vdots\\\
1\end{pmatrix}&\dots&{\bm{k}}_{t}=\begin{pmatrix}1\\\ 1\\\ \vdots\\\
1\end{pmatrix}\end{array}$ (24)

Note that all key vectors are the same and we only need to compute them up to
position $t$ as the attention mask is causal, i.e query can only look at
positions $\leq t$. Next, we compute the attention weight vectors
${\bm{\alpha}}$:

$\displaystyle{\bm{\alpha}}=$
$\displaystyle\left[\langle{\bm{q}}_{t},{\bm{k}}_{1}\rangle,\langle{\bm{q}}_{t},{\bm{k}}_{2}\rangle,\ldots,\langle{\bm{q}}_{t},{\bm{k}}_{t}\rangle\right]^{\intercal}$
(25) $\displaystyle=$
$\displaystyle\left[\alpha^{*},\alpha^{*},\ldots,\alpha^{*}\right]^{\intercal}$
(26)

where $\alpha^{*}=q_{1}+q_{2}+\ldots+q_{h}$. Next, we apply $\mathrm{softmax}$
to compute the attention probabilities. Since all ${\bm{\alpha}}^{i}$’s are
the same, we have:

$\displaystyle\hat{{\bm{\alpha}}}=\mathrm{softmax}({\bm{\alpha}})=\left[\frac{1}{t},\frac{1}{t},\ldots,\frac{1}{t}\right]^{\intercal}$
(27)

Now, we compute the value vectors by applying
${\bm{v}}_{i}={\bm{W}}_{V}{\bm{h}}_{i}^{(0)}$:

$\displaystyle\begin{array}[]{cccc}{\bm{v}}_{1}=\begin{pmatrix}1\\\ 0\\\
\vdots\\\ 0\end{pmatrix}&{\bm{v}}_{2}=\begin{pmatrix}0\\\ 0\\\ \vdots\\\
0\end{pmatrix}&\dots&{\bm{v}}_{t}=\begin{pmatrix}0\\\ 0\\\ \vdots\\\
0\end{pmatrix}\end{array}$ (29)

Finally, we compute the output of the attention head by applying
${\bm{W}}_{O}$:

$\displaystyle{\bm{o}}_{t}={\bm{W}}_{O}\left(\sum_{i\leq
t}\hat{{\bm{\alpha}}}_{i}{\bm{v}}_{i}\right)={\bm{W}}_{O}\left(\frac{1}{t}\sum_{i\leq
t}{\bm{v}}_{i}\right)={\bm{W}}_{O}\begin{pmatrix}1/t\\\ 0\\\ \vdots\\\
0\end{pmatrix}_{h}=\begin{pmatrix}0\\\ 0\\\ 1/t\\\ 0\\\ \vdots\\\
0\end{pmatrix}_{d}$ (30)

Thus, the output of our constructed attention head recovers the absolute
position information and writes it to the third dimension of output.

We used the decoder-only property of Transformer implicitly in Equation 25,
which helped us to only attend to position $\leq t$. So, the lengths of the
attended sequence are always $t$. Moreover, the presence of <bos> token in the
input sequence helped us to anchor the absolute position information. This is
not a problem as in practice models are often prompted with some instructions
which can act as <bos> token.

With this information available to the rest of the network, the feedforward
sub-layer, with sufficient hidden width, can recover the absolute positions
$[1,2,\dots,T+1]$ from the third dimension of attention output. This is
because the feedforward sub-layer is MLP with ReLU activation. So, it can
learn any arbitrary function (Park et al., 2020). Note that the layer-norm
operation can be bypassed as explained by Akyurek et al. (2023). ∎

###  C.2 Relative Positional Encoding in NoPE

In this section, we show if the hidden state contains absolute positional
information as explained in the previous section, then the attention mechanism
in all subsequent layers can implement a relative positional encoding. We
refer the readers to Sections B.1 and C.1 for the notation and definitions
used in this section.  [Relative Encoding]thmEncodeRelative Suppose that the
hidden state ${\bm{H}}^{(1)}$ contains absolute positional information, as
stated in 1, and assume that it is not overwritten by any subsequent layers.
Then, the self-attention in all subsequent layers can implement a relative
positional encoding: there exists a parameterization of $f_{\theta}$ such
that, for $l\geq 2$, the attention dot product between query ${\bm{q}}_{t}$
and key ${\bm{k}}_{i}$ at positions $t$ and $i$ ($t\geq i$) can be expressed
as: $\displaystyle\langle{\bm{q}}_{t},{\bm{k}}_{i}\rangle$
$\displaystyle=f_{\mathrm{cnt}}({\bm{q}}_{t},{\bm{k}}_{i})+f_{\mathrm{rel}}(t-i)\
$ (31) where $f_{\mathrm{cnt}}$ is a function of their content, and
$f_{\mathrm{rel}}$ is a function of their relative distance. Proof.

Our proof only specifies a few entries of weight matrices for attention heads
in layers $l\geq 2$, which does not impose any challenges for Transformers
used in practice as they usually have a very large model dimension $d$.
Moreover, we require to have absolute positions in the third dimension of the
hidden state as explained in 1. To show NoPE can implement relative encoding,
we only need to prove that its attention dot product depends on the relative
distance between tokens (See Section B.1 for an overview of relative encoding
methods). In the rest, we provide the construction of the weights and then
verify that they can implement relative position encoding.

For head dimension $h\geq 2$, we construct the weights
${\bm{W}}_{Q},{\bm{W}}_{K}$ of the attention heads in the second layers and
above. Specifically,

$\displaystyle{\bm{W}}_{Q}=\begin{bmatrix}1&0&0&0&\dots&0\\\
0&0&-1&0&\dots&0\\\ w_{3,1}&w_{3,2}&w_{3,3}&w_{3,4}&\dots&w_{3,d}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
w_{h,1}&w_{h,2}&w_{h,3}&w_{h,4}&\dots&w_{h,d}\end{bmatrix}_{h\times d}$ (32)
$\displaystyle{\bm{W}}_{V}=\begin{bmatrix}0&0&1&0&\dots&0\\\
1&0&0&0&\dots&0\\\
w^{\prime}_{3,1}&w^{\prime}_{3,2}&w^{\prime}_{3,3}&w^{\prime}_{3,4}&\dots&w^{\prime}_{3,d}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
w^{\prime}_{h,1}&w^{\prime}_{h,2}&w^{\prime}_{h,3}&w^{\prime}_{h,4}&\dots&w^{\prime}_{h,d}\end{bmatrix}_{h\times
d}$ (33)

where $w_{i,j},w^{\prime}_{i,j}\in\mathbb{R}$ can take any arbitrary value.
Their corresponding ${\bm{W}}_{V}$ and ${\bm{W}}_{O}$ can take any arbitrary
values as long as they do not override the first three dimensions of the
residual stream.

Now we verify that for any input sequence
${\bm{x}}=\left[\texttt{<bos>},x_{1},\ldots,x_{T}\right]$, the attention dot
product between query ${\bm{q}}_{t}$ and key ${\bm{k}}_{i}$ at positions $t$
and $i$ ($t\geq i$) will depend the relative distance between tokens.

First, assume that absolute positions are computed in the hidden state
${\bm{H}}^{(l)}$ for $l\geq 1$, as stated in 1. Specifically,

$\displaystyle{\bm{H}}^{(l)}=\begin{bmatrix}1&1&1&1&\dots&1\\\
1&0&0&0&\dots&0\\\ 1&2&3&4&\dots&T+1\\\
h_{4,1}&h_{4,2}&h_{4,3}&h_{4,4}&\dots&h_{4,T+1}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
h_{d,1}&h_{d,2}&h_{d,3}&h_{d,4}&\dots&h_{d,T+1}\end{bmatrix}_{d\times(T+1)}$
(34)

where $h_{i,j}\in\mathbb{R}$ can be any arbitrary value as the first three
dimensions of the hidden state are reserved for PE computation. The rest of
the dimensions can take any arbitrary values as in regular computation of
Transformers.

We now present the attention computations at position $1\leq t\leq T+1$. We
use ${\bm{W}}_{Q}$ to compute the query vector ${\bm{q}}_{t}$ by applying
${\bm{q}}_{t}={\bm{W}}_{Q}{\bm{h}}_{t}^{(l)}$:

$\displaystyle{\bm{q}}_{t}=[1,-t,q_{3},\dots,q_{h}]^{\intercal}$ (35)

where $q_{j}\in\mathbb{R}$ can take any arbitrary value. Next, we compute the
key vectors by applying ${\bm{k}}_{i}={\bm{W}}_{K}{\bm{h}}_{i}^{(l)}$:

$\displaystyle\begin{array}[]{ccccc}{\bm{k}}_{1}=\begin{pmatrix}1\\\ 1\\\
k_{3,1}\\\ \vdots\\\ k_{h,1}\end{pmatrix}&{\bm{k}}_{2}=\begin{pmatrix}2\\\
1\\\ k_{3,2}\\\ \vdots\\\
k_{h,2}\end{pmatrix}&{\bm{k}}_{3}=\begin{pmatrix}3\\\ 1\\\ k_{3,3}\\\
\vdots\\\ k_{h,3}\end{pmatrix}&\dots&{\bm{k}}_{t}=\begin{pmatrix}t\\\ 1\\\
k_{3,t}\\\ \vdots\\\ k_{h,t}\end{pmatrix}\end{array}$ (37)

where $k_{(\cdot,\cdot)}\in\mathbb{R}$ can have any arbitrary value. So, for
${\bm{k}}_{i}$ we have:

$\displaystyle{\bm{k}}_{i}=[i,1,k_{3,i},\dots,k_{h,i}]^{\intercal}$ (38)

Next, we let us present the attention dot product between ${\bm{q}}_{t}$ and
${\bm{k}}_{i}$:

$\displaystyle\langle{\bm{q}}_{t},{\bm{k}}_{i}\rangle=$ $\displaystyle
1.i+(-t).1+q_{3}.k_{3,i}+\dots+q_{h}.k_{h,i}$ (39) $\displaystyle=$
$\displaystyle i-t+\sum_{j=3}^{h}q_{j}.k_{j,i}$ (40) $\displaystyle=$
$\displaystyle\left(\sum_{j=3}^{h}q_{j}.k_{j,i}\right)-(t-i)$ (41)
$\displaystyle=$ $\displaystyle
f_{\mathrm{cnt}}({\bm{q}}_{t},{\bm{k}}_{i})+f_{\mathrm{rel}}(t-i)$ (42)

Thus, the dot product between ${\bm{q}}_{t}$ and ${\bm{k}}_{i}$ depends on the
relative distance between tokens (assuming the rest of the terms do not cancel
out which can be easily avoided by setting the respective weights in Equations
32 and 33). Note that our proof uses the linear spacing between tokens, but
the MLP the first layer can write any arbitrary function of absolute positions
to the third dimension of the hidden state, which enables more complex
relative encoding schemes. ∎

##  Appendix D Experimental Details

###  D.1 Tasks

Here we provide the details and more examples of the tasks and datasets we
used in our evaluation. For each task, we sample 100K examples for the
training set and 10K for the test. Also, we use 15% of the train as the
validation set.

#### Addition

The addition task (Nye et al., 2021) asks the model to compute the sum of two
numbers. Each number is represented as a sequence of digits that are separated
by space. So, the model has access to the exact digits.

Input Compute: 5 3 7 2 6 + 1 9 1 7 ? Output The answer is 5 5 6 4 3.

we create each length bucket based on the number of digits in each number,
e.g. 6-by-3, 6-by-4, etc. For the training set, we use buckets where one of
the numbers has at most $L$ digits. For the test set, we use buckets where any
of the numbers have at most $L$ digits. The model is evaluated on the
correctness of its predicted result.

#### Polynomial Evaluation

The polynomial evaluation task (Nye et al., 2021) asks the model to evaluate a
polynomial expression at a given value of $x$. The polynomial terms and digits
are separated to make just the tokenizer does not glue symbols together.

Input Evaluate x = 3 in ( 3 x ** 0 + 1 x ** 1 + 1 x ** 2 ) % 10 ? Output The
answer is 5.

The length bucket is created based on the number of terms in the polynomial
expression. We sample $x$ from $\mathcal{U}(-2,2)$, the degree of each term
from $\mathcal{U}(0,3)$, and the coefficient of each term from
$\mathcal{U}(-3,3)$. We take the modulo of the result by 10 to make the task
easier for the model and make sure we only measure the generalization of the
length of the problem instance not the value of the polynomial. The model is
evaluated on the correctness of its predicted result.

#### Sorting

The sorting task (Saxton et al., 2019) asks the model to sort a sequence of
input numbers. We use this task in two variants: Single Token and Multi Digit.
In the Single Token variant, we create an alphabet of 50 tokens from the
model’s vocabulary and fix some canonical ordering among them through task.
Each instance is a sequence of tokens from the alphabet in a random order, and
the model is asked to sort them in the canonical order.

Input Sort the following numbers: 3 1 4 1 5 ? Output The answer is 1 1 3 4 5.

In the Multi Digit variant, we simply present a sequence of multi digit/tokens
numbers to the model, and ask it to sort them in ascending order. Each number
is represented by its digits and they are separated by a space.

Input Sort the following numbers: 3 1, 4 1, 5 9, 1 2 6, 5 3 3 ? Output The
answer is 3 1, 4 1, 5 9, 1 2 6, 5 3 3.

In this case, we sample each number from $\mathcal{U}(0,10000)$. In both
cases, the length bucket is created based on the length of the input sequence.
The model is evaluated on the correctness of its predicted result.

#### Summation

In this task (Saxton et al., 2019), we ask the model to compute the sum of a
sequence of input numbers modulo 10 as we want to specifically measure how the
model generalizes to longer sequences not the value of summation result:

Input Compute: ( 1 + 2 + 3 + 4 + 7 ) % 10 ? Output The answer is 7.

Each digit is randomly sampled from $\mathcal{U}(1,9)$. The length bucket is
created based on the length of the input sequence. The model is evaluated on
the correctness of its predicted result.

#### Parity

In the parity task (Anil et al., 2022), we ask the model to compute the parity
of a binary sequence.

Input Is the number of 1’s even in [ 1 0 0 1 1] ? Output The answer is No.

#### LEGO

In the LEGO task (Zhang et al., 2023), the model is provided with a simple
computation graph (DAG), where each node represents a variable, and variables
are connected by simple operations which created the edges in the computation
graph. We refer to Zhang et al. (2023) for a detailed description.

Input If a = -1; b = -a; c = +b; d = +c. Then what is c? Output The answer is
+1.

To sample each example, we first sample the list of variables based on the
length of the example, and then we uniformly sample the value of each variable
to make sure all variables are represented with both -1 and +1. Finally, given
the value of variables, we deterministically compute the operation on each
edge. For each example, we query all variables from the middle of the
computation graph to the end. The model is evaluated on the correctness of its
predicted result.

#### Copy

The copy task is straightforward. The model has to repeat the input sequence
in the output.

Input Copy the following words: <w1> <w2> <w3> <w4> <w5> . Output <w1> <w2>
<w3> <w4> <w5>

We create multiple variants of this task to better understand the models’
generalization behavior. In the first variant, the input tokens are the same,
so the model has to basically count the number of input tokens. In the second
variant, the model has to replace the input tokens with another token sampled
from the vocabulary. In the third variant, we sample the input tokens from the
model’s vocabulary, and the model has to predict them in the same order. We
also create 2x versions of variants 1 and 3 to make the tasks more
challenging.

#### Reverse

In this task the model, the model has to reverse the order of input tokens in
its output.

Input Reverse the following words: <w1> <w2> <w3> <w4> <w5> . Output <w5> <w4>
<w3> <w2> <w1> .

As in the copy task, we create multiple variants of this task. In the first
variant, the model has to reverse the order of input tokens, where the tokens
are randomly sampled from the model’s vocabulary. In the second variant, the
model has to reverse the order of input tokens, as in the first variant, but
also it has to reverse it one more time, recreating the original input.

###  D.2 Hyperparameters

Table 2 shows the hyperparameters we used in our experiments. We use the same
hyperparameters for all models and positional encoding schemes. In our initial
experiment, we tried a few more hyperparameters such as
$\mathrm{lr}\in\\{0.00001,0.00003,0.00005\\}$ and
$\mathrm{WeightDecay}\in\\{0,0.05,0.1\\}$, but we did not observe any
significant difference in the results. So, we decided to use the same
hyperparameters throughout our experiments.

###  D.3 Compute

In our experiments, we used single-GPU training setup for the models.
Specifically, we ran our experiments on a mix of NVIDIA V100 32G, NVIDIA
RTX8000 48G, NVIDIA A100 40G, and NVIDIA A100 80G GPUs. Depending on the GPU
type and the positional encoding, each of our training runs took 6 to 15
hours, per each seed, on average to complete. Considering all the datasets,
and positional encoding schemes, in addition to the scratchpad experiments,
and three seeds, we ran about 870 individual training runs for the results in
this paper.

###  D.4 Reproducibility

In this study, all experiments employed open-source libraries, specifically
HuggingFace (Wolf et al., 2020) from which we utilized their implementation as
a foundation for the training loop, optimizer, and the Transformer
architecture. To ensure reproducibility, we will also release a singularity
binary with all dependencies and libraries to enable running our experiments
on any machine with NVIDIA GPUs and at any time in the future. Moreover, every
reported number in this paper is linked to the source code package that
deterministically (up to GPU stochasticity) reproduces the results, which we
release publicly on GitHub at https://github.com/McGill-NLP/length-
generalization.

Table 2: Summary of hyperparamters used in the experiments. Parameter | Value
---|---
Optimizer | AdamW
Learning rate | 0.00003
Weight Decay | 0.05
Batch size | 64
Learning Rate Scheduler | Polynomial
Warm Up | 6% of training steps
# Train Steps | 40K steps
Dropout (taken from HuggingFace) | 0.1
Model dimension (taken from HuggingFace) | 768
# Layers (taken from HuggingFace) | 12
# Attention Heads (taken from HuggingFace) | 12

##  Appendix E Full Results

###  E.1 Detailed Model Accuracy

We report the detailed results of our experiments in Figures E.2, E.3 and E.4.
We refer the readers to Section D.1 for the description of each task.

###  E.2 Detailed Head Distance

Figure E.5 shows the layer-wise distance of No PE’s attention patterns with
other positional encoding schemes measured across instances of the SCAN
dataset. We refer the readers to Section 5.2 for the details and analysis of
these results.

###  E.3 Detailed Model Accuracy On Various Scratchpad Formats

Figure E.6 shows the generalization of various scratchpad formats for each
model aggregated across all datasets. Figures E.7, E.8, E.9, E.10, E.11, E.12
and E.13 show the generalization of various scratchpad formats for each model
on each dataset. We refer the readers to Section 6 for the details and
analysis of these results.

Figure E.2: Generalization behavior of positional encoding schemes on
Primitive tasks. Figure E.3: Generalization behavior of positional encoding
schemes on Mathematical & Reasoning tasks. Figure E.4: Generalization behavior
of positional encoding schemes on Classic Length Generalization tasks. Figure
E.5: Layer-wise distance of No PE’s attention patterns with other positional
encoding schemes measured across instances of SCAN dataset. Figure E.6:  The
optimal scratchpad format is aggregated across all datasets per each model.
The optimal scratchpad format is different for each model.  Figure E.7:
Generalization of various scratchpad formats for each model on the Addition
task.  Figure E.8:  Generalization of various scratchpad formats for each
model on the Summation task.  Figure E.9:  Generalization of various
scratchpad formats for each model on the Parity task.  Figure E.10:
Generalization of various scratchpad formats for each model on the Sorting
task (Single Digit).  Figure E.11:  Generalization of various scratchpad
formats for each model on the Sorting task (Multi Digit).  Figure E.12:
Generalization of various scratchpad formats for each model on the Polynomial
Evaluation task.  Figure E.13:  Generalization of various scratchpad formats
for each model on the LEGO task.