The Impact of Positional Encoding on Length Generalization in Transformers
Authors: Amirhossein Kazemnejad
Inkit Padhi
Karthikeyan Natesan
Payel Das
Siva Reddy
Venue: NeurIPS 2023 poster (2023)
Keywords: Transformers
Positional Encoding
Length Generalization

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 embeddings are not essential for decoder-only Transformers to generalize well to longer sequences.

The Impact of Positional Encoding on Length Generalization in Transformers
Amirhossein Kazemnejad', Inkit Padhi
Karthikeyan Natesan Ramamurthy", Payel Das Siva Reddy1.3.4
Mila, McGill University; 2IBM Research;
Faacbook CIFAR AI Chair; 'ServiceNow Research
(amirhossein. kwwemne siva. reddy)emill @mila. quebec inkpad@ibng bm, com, (knatesa, daspa) ibm. com
Abstract
Length generalization, the ability to generalize from small training context sizes larger ones, is 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 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 battery 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 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, 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 not essential for decoder-only Transformers generalize well to longer sequences.
Introduction
The ability to generalize from smaller training context sizes to larger ones, commonly known as length generalization, is a major challenge for Transformer-basee language models (Vaswani et al., 2017; Deletang 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, model can benefit from more in-context-leaminng examples, higher numbers of reasoning steps, or longer text generation. However, training Transformer with larger context size can be excessively slow and -intensiee This even more pronounced in the recent paradigm of model finetuning on ciarructionfoollowiie datasets (Wei al., 2022a; Chung al., 2022; Ouyang et al., 2022). It is not only infeasible train the model on all possible context lengths, but also the number 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 positional encoding on length generalization the "decoder-only" Transformers various tasks trained from scratch. Figure 1 summarizes finding that using no positional encoding is better than using explicit positional encodings.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

No Positional Encoding
0.69
T5's Relative PE
0.55
ALiBi
0.50
Positional Encodings
used GPT3-style
Rotary
0.33
LLMs:
BLOOM (2022a),
PaLM (2022),
Absolute Position Embedding
and LLaMA (2023).
0.1
0.2
0.3
0.4
0.5
0.6
0.7
Mean Reciprocal Rank (Higher better -+)
Figure No positional encoding (NoPE) outperforms all other positional encodings at length generalization of decoder-only Transformers (GPT-style) trained from scratch and evaluated on battery of reasoning- like downstream tasks. This figure shows aggregate ranking of positional encoding methods across 10 tasks.
Positional encoding (PE) seems be a major factor in the length generalization of Transformers as the model has to systematically encode tokens in all possible positions. The original Transformer architecture (Vaswani al., 2017) used non-parametric periodic functions to represent absolute position embeddings (APE) in systematic manner, but further studies have shown that these functions are inadequate for length generalization (Ontanon al., 2022). The prevailing belief that relative PEs (Shaw et al., 2018: 8: Raffel et al., 2020) are more effective in length generalization than APE variants (Ontanon et al., 2022; Csordás al., 2021). However, Press Transformers with relative PEs, such as Rotary (Su et al., 2021), can be poor length generalization. But the evaluation of PEs often relies on language modeling perplexity as key metric (Haviv et al., 2022; Press et al., 2022) which does not always align with the performance on downstream tasks (Tay et al., 2022). This raises important questions: what exactly is the influence of positional encoding on length generalization downstream tasks? Morcover, early empirical evidence shows that decoder- only Transformers without explicit position information (Tsai et al., 2019; Haviv al., 2022) can perform well existing PEs in in-distribution settings, but its effects on length generalization and downstream performance are unclear.
(2022) has shown that even
Recently, asking models to emit intermediate computation steps into a scratchpad, also referred to as chain-offthoughtt, has been adopted to improve the length extrapolation Transformers (Nye et al., 2021; Wei et al., 2022b). These techniques are architecture-indeeendeen and can be used with any PE method. However, it remains an open question whether these techniques, at least in regard length generalization, render the choice of PE irrelevant, especially given that model performance is highly sensitive to the scratchpad format (Bueno et al., 2022; Akyurek and Akyurek, 2022).
To answer these questions, we conduct a systematic study on the length generalization of decoder- only Transformers, popularized by the GPT-family of models (Radford 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 al., 2022), Rotary (Su et al., 2021) and no positional encoding (NoPE) on 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 the attention mechanism (in contrast to explicit PEs).
We show that NoPE 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 not always helpful for length generalization and format highly impacts performance. The attention distributions reveal that NoPE and T5's Relative PE encourage attending to both long and short-range positions, ALiBBi to recent positions, and Rotary and APE to 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. I, 1, 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 Appendix B for more formal details).
Absolute Position Embedding (APE), embeds each absolute position into position vector p; and adds word embeddings their corresponding p: before feeding them to the model. The non-pan 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 position embedding for unseen positions, 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 scalar bias value 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 this rotation, the attention dot product will only depend on the relative distance between tokens, effectively making it relative positional encoding (Su et al., 2021).
ALiBi, used in BLOOM (Scao al., 2022a), is similar to T5's Relative Bias but instead subtracts scalar bias from the attention score. This bias grows linearly with the distance between the query and key tokens. This, effect, creates a preference toward recent tokens (recency bias).
Note that encoder-only Transformers, such as BERT, become bfg-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 generalize unseen lengths. We demystify this in Section 5.
3 Model Evaluation
Length Generalization Setup Following Anil et al. (2022), we focus 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 both seen and unseen lengths at inference. We present these problems as to-euuence tasks, where the input sequence is the problem instance and the output sequence is the solution. Formally, let D = {2,,, yt)} denote dataset of such task where æ; is the input and y: is the output sequence. For each task a function À D N can be defined that returns the length bucket of a task instance d E D. This can be the number of tokens any general notion of length/depth of reasoning. Using this function and a threshold L., we employ samples where À < T. for learning the task and samples where L for evaluating generalization. The performance on each instance is reported as the exact-match accuracy of its answer with the ground truth.
conventional decoder-only Transformer architecture 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) the learnable variant cannot produce embeddings for unseen positions. Given the absence of publicly available Transformer-basee 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 Po(yylær) = E'n log po (ye /æc, y1:--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 107M trainable weights (List of all hyperparameters in Appendix D.2).
Architecture We
3

---

Table 1; Examples of the input and output of the tasks.
Input Example
Output Example
Primitive Tasks
Copy
Copy following words: <x2> <y3>
Revense
Reverse the folloving words:
<el> <>2> <u3>
<ad>>
<ub>
<ub> <ud> <x3>
<o2>
<rl>
Mathematical and Algrvithmic Tasks
Addition
Compute: 9
The anever is 5 4 3. The anaver 5.
Polynomial Eval.
Evaluate x = 3 0 1
20
Sorting
Sort the following numbers: 314159
1 4 5. The ansver 7.
The
Summation
Compute: (1 +
Parity
the
1
01000
LEGO
If -1; b -a; +b; d Pc. Then what is c?
The anzver is +1.
Classical Length Generalization Dutasets
SCAN
jump tvice and run left
JUMP JUMP TURN LEFT RUN X12
PCPG
shift prepend K12
Primitive Tasks
Mathematical & Resconing
Classic Lon. Gen. Datasets
Mcan Rank (+)
0.75
0.50
0.25
NoPE
T5
ALIB:
Rotary
APE
NoPE
T3
ALIBI
Rotary
APE
NoPE
T5
ALBI
Rotary
APE
Positional
Encoding
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.
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 al., 2021). Polynomial Evaluation, Sorting, Summation (Saxton et al., 2019), Parity (Anil et al.. 2022), LEGO (Zhang al., 2023) and (3) Classical length generalization datasets such 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 the task instance from the uniform distribution (1,, L), and then, according to the task's generative process, sample the input and output sequences. For the test set, we follow the same procedure but sample length from (111, 2L) to include both seen and unseen lengths. Throughout the paper, unless otherwise stated, 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 Appendix D.I).
L = 20.
We report the results of our empirical evaluation over ten tasks and three seeds per dataset-PE, pair.
What Is The Effect of Positional Encoding?
In this section 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 and 2 when compared against each other for all tasks and scenarios. Furthermore, we showcase the accuracy models evaluated on examples of various lengths in Figure 3. (Detailed results for each task and scenario can be found in Appendix E).
First, we observe that in most tasks, models achieve perfect or near-perfect accuracy (Figure 3) on the I.I.D. lengths, which indicates that models have 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

---

Copy
Addition
SCAN
0.6
0.4
Accuracy
20
30
10
12
Reverse
Summatiin
PCFG
0.8
0.6
0.2
0
15
20
25
30
35
40
10
12
14
10
20
30
Problem Length
Positional Encoding
NoPE TS's Relative
ALiBi
Rotary
Absolute Position Embedding
Figure 3: Showcasing the generalization behavior of different positional encodings on 6 datasets. The shaded area represents evaluation examples with L.I.. lengths (i.e. seen during training). Since all models perform perfectly, close to it, the L.D., lengths (measured unseen examples), for improved readability, we only show a subset of them in the figure. Refer to Appendix E for more detailed plots.
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 relative encoding method (Ontanon 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 decoder-only Transformer without any positional encoding, performs on par with or even better than the best-performing explicit PE, TS's Relative Bias. NoPE achieves the same level of generalization without wry computational overhead since it does not compute any additional term 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.
How Does NoPE Represent Positions?
The surprising performance of NoPE model suggests that capture useful positional information that can also generalize. But, how it does so 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 fo be a NoPE decoder-only Transformer model, where 0 denotes the model parameters. fo processes the input sequence [<bos>, .i,...,,yy .r by applying series of layers. Note that since fe does not have any PE, the input is not augmented with positional information (e.g. 21. 77). Each layer consisting of self-attention heads and feed-forward sub-layer, reads the previous hidden state ((-1) and produces the hidden state at layer I: H' Each head parameterized by query Wo. key WK. value Wv. and output Wo matrices, where Wo, WK. Wy E hxd and Wo E d d and / are the model's hidden state size and attention dimension, respectively. W1. W2 2 E dd are the weight matrices of the feed werdwrd sub-layer.

---

Layer g00
Layer #002
15
1.90
Averoge D(NoPE, 54)
0.5
DINoPE M)
Lper
0.75
1.5
0.25
0
10
Example Length
Example Length
Positional Encoding (M)
NoPE
15's Relative
ALIBI
Rotary
Absolute Fosition Embedding
Figure 4: Distance 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.
Theorem (Absolute Encoding). Let be input sequence of length T + the model. Then, the first layer of fe can recover absolute positions [,...., + 1] in the hidden state H That is, there exist Wo. WK. Wv, Wo. Wi, and W2 such that the self-atlention and feedforward operations in the first layer compute absolute positions and write it to the next hidden state.
We refer to Appendix C.1 for the complete proof Theorem 1. This thcorem shows that stochastic gradient descent (SGD) potentially learn recover absolute positions in NoPE Transformers. Next, we demonstrate how relative PE can be implemented subsequent layers:
Theorem 2 (Relative Encoding). Suppose that the hidden state H1) contains absolute positional information, as stated in Theorem 1, and assume that it is not overwritten by any subsequent layers. Then, the self-attention in all subsequent layers can implement relative positional encoding: there exists a parameterization of Je such that, for I 2 2, the attention dot product between query On and key km at positions n and m can be expressed as:
(gn, km) = feus(ge (g, k) + fra((n-m) m)
(1)
where feat is a function of their content, and frel is function of their relative distance.
Appendix C.2 provides the complete proof of Theorem 2. Our theoretical results suggest that SGD can choose between relative and absolute encoding in NoPE Transformers, But, what mechanism SGD learns in practice
clear. We next investigate this question empirically.
5.2
NoPE learns to use relative PE in practice
In order explore the mechanisms that NoPE employs in practice, we conduct quantitative analysis by comparing its attention pattern to models trained with different positional encoding techniques. The hypothesis that if NoPE utilizes similar algorithm other PEs, then the attention patterns of these models should be quite similar.
To this end, feed the same input to both models and, at layer I, compute the minimum distance between the attention distribution of any heads in the first model and any head in the second model. Formally, let P, p(k] q:) be probability distribution produced by causal self- attention head for query at position f, over the keys & E [k],... ky] in a given transformer layer. Over sequence of length T. define the similarity between two heads P and
D DA (P, Q) T Ei DISD (P*|(Q,) 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 we take the minimum distance
1

---

between all pairs of attention heads in the corresponding layer:
(A,
min DAT(P, Q)
(2)
(P.Q)
where A and B1 are the attention heads in layer of models 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 F.7). We find that NoPE's attention patterns 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 when averaged across all layers. These results potentially suggest that a Transformer model without positional encoding, trained with stochastic gradient descent learns represent positions in a way similar T5's Relative PE, which is relative positional encoding scheme.
Does Scratchpad Render The Choice of Positional Encoding Irrelevant?
In scratchpad/CotT prompting, the model generates intermedi- computations required to reach the final answer 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 Transform- ers even small scale (Nye al., 2021). Since scratchpad only modifies the model's input and output (not the architecture), is unclear and unexplored how architectural choices such as positional encoding affect the length generalization in the pres- ence 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.
Input (ar)
Compute
Output (s; 3/) <scratch>
7, 1 Por digits
C
We have 6 carry
10 13 10 13 10
0
Which is equal to 3
y
We update carry to 13 //
So. the remaiving input is
R
6372+191
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).
</ecratch> anever 555643
To account for those, we consider five components in each step of scratchpad: <input>, <computation>, <output>, <variable, update>, , and <remaining.inppe (Figure 5). In experiments,
Figure 5: Example of an addition task depicted with its first scratch- pad step. Each step consists of five components:
create different variations of seratch- pad format by enabling or disabling each component, which allows us systematically study their impact.' Figure 6 sum- marizes 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 positional encoding with robust length generalization is crucial since scratchpad/Cot alone may not enhance the generalization.
Step Input I, Step Computation C. Step Output O Intermediate Variable Updates V. and Remaining Input R.
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 (R) in each step of the scratchpad. But, the attention can attend to this information directly from the main input. So, remains unclear which specific part of the scratchpad different PEs rely
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
Since using scratchpad creates very long sequences, we follow Nye et al. (2021) and set the length threshold 8 for tasks that use it avoid out-of memory emrors.
7

---

Scratchpad Format Scratchpad
Mean Reciprecal Rank (-)
Full "Stop Input"
"Step Computation"
0.50
"Step Outpuc"
"Intermediate Vars"
0.25
0
Fall "Ramaining Parts"
(Only Compute-Qutputt
Addition
LEGO
Parity
Polynomial Eval.
Sort
Summation
Figure 6: Mean ranks of scratchpad format aggregated across all models per each dataset. The effectiveness of scratchpad is task dependent.
NoPE
the output sequence, calculate the distance d between
70000
the current query q, and the attended key k as (t (t-mp n +++ 1) and subsequently normalize it based the length of the sequence at the present step. The normalized value is denoted as d.
35000
T5's s Relative
70000
Figure depicts the distribution d. Values d close to 0 indicate attention tokens near the current position (e.g.
35000
current scratchpad step), while values close to signify attention distant tokens (e.g, the input). NoPE and T5's Relative PE resemble each other and exhibit bimodal distribution, reflecting both short-range and long-range attention. Conversely, ALiBi (due to its recency bias) strongly favors short-range attention. Rotary, 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 be more optimal.
ALiBi
70000
35000
Rotary
70000
35000
Absolute Position Embedding (APE)
Discussion
70000
35000
Practitioners have to make important choices about the
nuances the Transformer architecture like positional encoding before undertaking the costly pretraining process. In the L.LD 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.
0
0.25
0.50
0.75
Normalized Attended Distance (d)
Figure Distribution of the normalized distance between the query and the key the self-attention (addition task + full scracthpad), averaged across all layers and heads.
In our paper, we utilize length generalization in down- stream tasks as mean assess the expressivity of po- sitional encodings. Our setup, 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 al., 2022) suggests shift towards adopting Rotary as a replacement for APE in the Transformer architecture. However, 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.
The disadvantages explicit PEs over NoPE in length extrapolation contribute to 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 modification to the widely used decoder-only Transformer architecture.

---

Scaling up to 1B models In order to study the behavior of position embeddings at scale, we trained three IB variants post-submission ALiBi, Rotary and NoPE with context length of 1024 tokens on a subset of StarCoder training set (Li et al., 2023). For more details, refer to Appendix F. Our results on language modeling show that at I.I.D all variants have similar perplexity, but at length generalization, Rotary fails to generalize as its perplexity explodes. NoPE and ALiBi generalize similarly to larger context sizes up to almost twice their training context size, and for larger contexts ALiBi is relatively more stable than NoPE (see the discussion on perplexity vs. downstream performance). Preliminary exploration of fine-tuning the pretrained models, on datasets in Section 3, yielded to identical performance among PE variants as the training context size of the 1.3B models is much larger than instance lengths in our datasets. A comprehensive downstream evaluation of these models remains subject for future research.
Perplexity downstream Performance Due human cognitive constraints (Gibson, 1998; Kiyono et al., 2021), language modeling data might encompasses short-range dependencies. The combination of this naturally occurring structure (which can be abundant in internet- based corpora) with the Recency Bias inherent in positional encodings like ALiBi could portray an unrealistic representation of models' length generalization performance. In fact, Chi et al. (2023) recently demonstrated that ALiBi's length generalization performance could be replicated using a window attention mask, where tokens beyond a window size w are masked out. Interestingly, we also observe that T5's Relative PE, which can be regarded as trainable version of ALiBi, learns to attend both large and short range dependencies (Figure F.3). This is in line with Tay al. (2022) observation and underscores the importance of evaluation setups on downstream tasks as compared to solely relying on perplexity.
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 of-theoft 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 extrapolation but only in the context of human language modeling. Most relevant is Deletang et al. (2023)'s s recent study on length generalization in various neural sequence models (including RNNs and Stacked-RNNG for tasks from Chomsky hierarchy. However, they do not focus on the difference among positional encoding or on autoregressive models. Unlike these studies, work extensively compares length generalization in popular PEs for a wide range of tasks, specifically focusing on autoregressive models, which represent many contemporary L.MMs.
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 learned variant popularized by Devlin al. (2019)). Relative approach for encoding positional information was further introduced by Shaw et al. (2018), which gave rise 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 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 not order-agnostic and can operate without explicit positional information.

---

This was observed early on by Shen et al. (2018) and later explained by Tsai et al. (2019). The observation that Transformers without positional encoding can perform on par with explicit PE has been made in various domains such as machine translation (Yang et al., 2019), language modelling (Irie et al., 2019 Haviv et al., 2022), and even other domains like vision or speech (Likhomanenko et al., 2021). In our work, not only we demonstrate that Transformers can operate without explicit position information, but also we present an important setup where they outperform explicit PEs. Furthermore, we theoretically show how they are capable of learning both absolute and relative encodings.
Conclusion
We studied the robustness of different positional encodings, in decoder-only Transformers, 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 practice. Finally, we find the effectiveness of scratchpad task-dependent, and is not reliable solution for length generalization.
Limitations
Our work primarily focuses on positional encodings as 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 our limited compute budget.
Acknowledgements
We grateful to anonymous reviewers, Nicolas Chapados, and Omer Levy for their invaluable suggestions and discussions 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 Al Chair program. This research was enabled in part by compute resources provided by Mila, the Digital Research Alliance of Canada and ServiceNow.
References
Ekin Akyurek and Afra Feyza Akyurek. 2022. Notes on teaching gpt-3 adding numbers.
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.
Loubna Ben Allal, Raymond Li, Denis Kocetkov, Chenghao Mou, Christopher Akiki, Carlos Munoz Ferrandis, Niklas Muennighoff, Mayank Mishra, Alex Gu, Manan Dey, Logesh Kumar Umapathi, et al. 2023. Santacoder: don't reach for the stars! ArXiv, abs/2301 .03988.
Cem Anil, Yuhuai Wu, Anders Johan Andreassen, Aitor Lewkowyez. Vedant Misra, Vinay Venkatesh Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. 2022. Exploring length generalization in large language models. Advances Neural Information Processing Systems.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016. Layer normalization. ArXiv, abs/1607.06455
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Voeberrt-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
10

---

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, NeurlPS 2020, December 6-12, 2020, viriual.
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 Ist Workshop on Mathematical Natural Language Processing (MathNLP), pages 17-24, Abu Dhabi, United Arab Emirates (Hybrid). Association for Computational Linguisties.
Ta-Chung Chi, Ting-Han Fan, Alexander Rudnicky, and Peter Ramadge. 2023. Dissecting transformer length extrapolation via the lens of receptive field analysis. Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 13522- 13537, Toronto, Canada. Association for Computational Linguistics.
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,
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 restuuttoo-finetuueed language models. ArXiv, abs/2210.1144
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.
Zihang Dai, Zhilin Yang. Yiming Yang. Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. 2019. Transformer-Xit XL: Attentive language models beyond 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.
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. International Conference on Learning Representations.
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.
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.
Daniel Furrer, Mare van Zee, Nathan Scales, and Nathanael Schärli. 2020. Compositional generaliza- tion in semantie parsing: Pre-training specialized architectures. ArXiv, abs/2007.08970.
Edward Gibson. 1998. Linguistic complexity: locality of syntactic dependencies. Cognition, 68(1):1- 76.
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: Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual.
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 neural network with dynamic external memory. Nature, 53847626):411-76
11

---

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.
Dan Hendrycks and Kevin Gimpel. 2020. Gaussian error linear units (gelus). ArXiv, htss/1606.0441
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Blia Bruni. 2020. Compositionality decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795.
Kazuki Irie, Albert Zeyer, Ralf Schlüter, and Hermann Ney. 2019. Language modeling with deep trans- formers. In Interspeech 2019, 20th Annual Conference of the International Speech Communication Association, Graz, Austria, 15-19 September 2019, pages 3905-3909.
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.
Shun Kiyono, Sosuke Kobayashi, Jun Suzuki, and Kentaro Inui. 2021. SHAPE: Shifted absolute position embedding for transformers. In Proceedings of the 202/ Conference on Empirical Methods in Natural Language Processing, pages 3309-3321, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
Brenden M. Lake and Marco Baroni. 2018. Generalization without systematicity: On the composi- tional skills of sequence-to-sequene recurrent networks. In Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockholmsmüsssan Stockholm, Sweden, July 10-15, 15, 2018, volume 80 Proceedings of Machine Learning Research, pages 2879-2888. PMLR.
Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Mare Marone, Christopher Akiki, Jia Li, Jenny Chim, Qian Liu, Evgenii Zheltonozhskii, Terry Yue Zhuo, et al. 2023. Starcoder: may the source be with you! ArXiv, abs/2305.06161.
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, 0tbs/2211.091111
Tatiana Likhomanenko, Qiantong Xu, Gabriel Synnaeve, Ronan Collobert, and Alex Rogozhnikov. 2021. CAPE: Encoding relative positions with continuous augmented positional embeddings. In Advances in Neural Information Processing Systems.
David Lindner, János Kramár, Matthew Rahtz, Thomas McGrath, and Vladimir Mikulik. 2023, Tracr: Compiled transformers laboratory for interpretability. ArXiv, abs/2301.05062.
Shayne Longpre, Le Hou, Tu Vu, Albert Webson, Hyung Won Chung, Yi Tay, Denny Zhou, Quoe Le, Barret Zoph, Jason Wei, and Adam Roberts. 2023. The flan collection: Designing data and methods for effective instruction tuning. ArXiv, abs/2301.13688.
Ziyang Luo, Artur Kulmizev, and Xiaoxi Mao. 2021. Positional artefacts propagate through masked language model embeddings. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference Natural Language Processing (Volume 1: Long Papers), pages 5312-5327, Online. Association for Computational Linguistics.
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/21 12.00114.
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 Com- putational Linguistics (Volume 1: Long Papers), pages 3591-36077 Dublin, Ireland. Association for Computational Linguisties.
12

---

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, 005//203.001155.
Sejun Park, Chulhee Yun, Jaeho Lee, and Jinwoo Shin. 2020. Minimum width for universal approxi- mation, ArXiv.
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.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners. OpenAl Blog, 1(8):9.
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 unified text-to-text transformer. Journal of Machine Learning Research, 10:14:67
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.
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/221 1. .05100.
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, Jacsung 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.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. 2018 Self-attention with relative position representations. In Proceedings of the 2018 Conference of the North American Chupter of the Association for Computational Linguistics: Humun Language Technologies, Volume 2 (Short Pupers), pages 464 468, New Orleans, Louisiana. Association for Computational Linguistics.
Tao Shen, Tianyi Zhou, Guodong Long, Jing Jiang, Shirui Pan, and Chengqi Zhang. 2018. Disan: Directional self-attention network for mn/cnnnfree language understanding. In Proceedings of the Shiirty-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.
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.
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-ICCLLP), pages 4506-4515, Hong Kong, China. Association for Computational Linguistics.
Jianlin Su, Yu Lu. Shengfeng Pan, Bo Wen, and Yunfeng Liu. 2021. Roformer: Enhanced transformer with rotary position embedding. ArXiv, abs/2104.09864.
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.
13

---

Ross Taylor, Marcin Kardas, Guillem Cucurull, Thomas Scialom, Anthony Hartshorn, Elvis Saravia, Andrew Poulton, Viktor Kerkez, and Robert Stojnic. 2022. Galactica: large language model for science. ArXiv, abs/221 01222211.000 1.09085..
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.
Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhut- dinov. 2019. Transformer dissection: An unified understanding for transformer's attention via the lens of kernel. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Process- ing (EMNLP-IJCNLP), pages 4344-4353, Hong Kong, China. Association for Computational Linguistics.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention all you need. 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.
Yizhong Wang, Swaroop Mishra, Pegah Alipoormolabashi, Yeganeh Kordi, Amirreza Mirzaei, Atharva Naik, Arjun Ashok, Arut Selvan Dhanasekaran, Anjana Arunkumar, David Stap, al. Generalization via declarative instructions on 1600+ NLP tasks. In Proc. of EMNLP, pages 5085-5109, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
2022. Super-Naturallnnsruetie
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 29-29, 2022. OpenReview.net.
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.
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.
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 Demonsirations, pages 38-45, Online. Association for Computational Linguistics.
Baosong Yang, Longyue Wang, Derek F. Wong, Lidia S. Chao, and Zhaopeng Tu. 2019. Assessing the ability of self- attentttention networks learn word order. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3635-3644, Florence, Italy. Association for Computational Linguistics.
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, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 1 11975-119999 1986. PMLR.
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.0106
14

---

Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. 2023, Unveiling transformers with lego: synthetic reasoning task. ArXiv, abs/2206.04301.
15

---

FLAN (CoT)
Super-Natural Instructions
60000
Coint
45000
30000
15000
1000
2000
3000
4000
1000
2000
3000
4000
Example Length
Figure A.I: 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.
A Number of instances decreases rapidly as sequence length grows
The recent trend of SFT-RLHF pipeline (Ouyang et al., 2022) relies on finetuning L.LMs on the instruction following tasks. However, the training data of these datasets is often skewed towards shorter sequences. Figure A.I 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. fact, the models are supposed learn from short instructions and generalize to ones during inference that might be much longer.
B
Background
B.1
Preliminaries
In this section, we lay the groundwork and introduce the notation throughout the paper. We will refer to this in Appendices C.I and C.2.
Let fe be decoder-only Transformer model, where 0 denotes the full set of model parameters. fe processes the input sequence æ [zo, .1. ØT] and maps it to the output sequence y = [yo, V1...., 3/T by applying 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 TLayer ( (H( 0t), consisting of self-attention heads and feed-forward sub-layer, reads the previous hidden state (1-1) and produces the hidden state layer (: H', where / is the layer index, and 6 is the set of parameters of the 1-th layer. Each hidden state H (T+( is matrix where column denoted as h is the hidden state at position t.
layer is parameterized by a set of parameters 0; = {WW W W W Wi, W2). where W W
K W E A and W E Rdxh are the query, key, value, and output matrices of the m-th head, respectively. W1. W2 ddd are the weight matrices of the feed-forward sub-layer. d denotes the model's hidden state size, is the attention dimension (where h. ) and is a multiplier of the hidden state size the feed-forward sub-layer (it is usually set to 4 in common implementations of the Transformer). Note that drop the layer index i and the attention head index m where it is clear from the context.
The Transformer layer TLayer (1) processes each column of (1-1) independently and in parallel to produce the output. The computation of the f-th column of (D) is as follows:
h FF(((a, + +h(h-1) + a, +h,
(3)
16

---

where FF is the feed-forward sub-layer. À is layer normalization, and E R is the output of the multi-head self-attention sub-layer at position t. Specifically, a, computed as:
02 Σ
Attn (m)) (h, (h) (11)) (1(1)))
m
where Attn (m)) is the m-th attention head. Let O2 E Rd denote the output of an attention head at position Then, o, is computed as:
o, Wo
Σ ag
where â softmax(a)) E (2(++1), and is the attention weight vector such that:
a [g:: ko), (g:, ki)...., (gr: kc)]
(6)
where q: Woh Rh, k; W (1-1) Ra and es Wvh (1-1) CRA. (,)) denotes the Wyh!-
(1-1)
dot product operation.
The feed-forward sub-layer FF()) E d is two-layer MLP:
FF(#) (Wo
(7)
where a is non-linear activation function (usually ReLU or GeLU (Hendrycks and Gimpel, 2020)). Additionally, X(-) E Rd layer normalization (Ba 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 al., 2017) as is easier to understand and analyze. But, they are mathematically equivalent (Elhage al., 2021).
The hidden state is initialized with a learned embedding of the input sequence H (0) WE X, where WE E RdxV is the embedding matrix and X E RVx(++1) the one-hot encoded input sequence. V is the vocabulary size.
B.2 Positional Encoding
Almost all positional encoding methods can explained and formulated how they implement the dot product operation in Equation (6). So, in this section, we explain how the dot product (ge, k.) is implemented in different positional encoding schemes.
Absolute Positional Encoding (APE) The process of Absolute Positional Encoding (APE) involves assigning position vector p, to each absolute position and combining them with word embeddings before inputting them into the model. So, APE first modifies how the hidden state is initialized:
H = WEX + WpP
(8)
where Wr E dR is the positional embedding matrix and P E (T++) is the one-hot encoded absolute position sequence. Vp the maximum absolute position. Therefore, the hidden state at column is:
h = eg + Pj
where e, E RRd is the word embedding of token r, and P, E Rdd is the positional embedding for position Then, the dot product for the first layer in Equation (6) is computed as:
(qe. k.)
(Wah (0)
(
(Wolee + P.), WK + Pi))
(Wole: + +p)) (Wx +p:))
+ +p
(10)
17

---

In the learned variant of APE, P) E R is learned during training. In the sinusoidal variant, Py is calculated using a non-parametric function. Specifically, Pj is computed as:
[iin(w1-J), cos(w)-))) cis(w..)),sin(wu>. cos(ws (w))
son(sar)))).coc(uap2..)) cos(wa//--))
(11)
where w/ 10000
T5's Relative PE The Relative bias in T5 is a type of relative positional encoding that initially calculates the relative distance (t --x) between tokens positions and This distance then transformed into scalar bias value b and is incorporated into the dot product between the query and key. is learned during training. Thus, the dot product every layer can be written as:
(ge, k.) q K; bbucket(n--ng
(12)
where
i
bucket(n) =
BB +
log
x B 2
<n<D
2
log
B
if
This function maps the relative distance d to bucket index, which will be used to look up the weight corresponding to that bucket. is the number buckets, D is the maximum distance. It assigns half of the buckets to distances smaller than with linear spacing and the other half to distances larger than with logarithmic spacing. The weight for distances larger than D the same. This is to facilitate generalization to unseen distances. In the original implementation of T5, B = 32 and D 128. Following shows an example of the bucket function with B 5 and D 6:
0
0
0
0
0
0
0
07
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
2
1
0
0
0
0
0
0
0
2
1
0
0
0
0
0
2
1
0
0
0
0
3
2
1
0
0
0
0
0
3
2
1
0
0
0
0
bucket
3
2
1
0
0
3
3
2
0
0
0
4
3
2
0
0
4
3
3
2
0
0
0
5
4
3
0
0
0
4
4
3
3
0
0
0
7
6
5
4
1
0
0
4
4
4
2
1
0
9
8
7
6
5
4
2
1
0
4
4
4
4
4
3
3
2
1
0
Similar to T5's Relative PE, ALiBi subtracts scalar bias from the attention score. As the distance between the query and key tokens increases, the bias grows linearly. Specifically, the dot product every layer can be written as:
ALiBi
(g k.) = q. k. - (t i). (m++1)
(13)
where m is head index and C is a constant defined as:
C = 2 logg
For example, if the number of heads is 8, then we have 1 1
2 27 2 (Press et al., 2022).
Rotary
The Rotary is relative PE that applies rotation 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:
18

---

(g: k.) (Rot( qt, 1), Rot(ks, ())
= =RR qr. R.d k;)
= =RR' qi) (R k;)
=q (RR R kiOk k:
=9. (1(--))
(14)
where R is a rotation matrix that rotates æ by radians:
cos((n))
sin(n0)
RT
(15)
(nn( cos(n10)
for d >> 2, Rotary applies the same approach on every two consecutive dimensions qe and k, but
with different 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:
(g:, k.) = q k.
(16)
C Proofs
In this section, we provide proof of why NoPE can implicitly learn both absolute and relative positions. We refer the readers Appendix 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 softmax function to recover absolute positions.
Theorem (Absolute Encoding). Let <bos>, 21...., FTl be an input sequence of length T to the model. Then, the first layer of fo can recover absolute positions [l..... + 1] the hidden state H(), That is, there exist Wq. WK. Wv. Wo. W,, and W₂ such that the self-at self-attention and feedforward operations in the first layer compute absolute positions and write 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, long as they do not override the first three dimensions, can 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 WE E RdxVV where each column the embedding of token in the vocabulary. We construct W such that it always sets the first dimension of every embedding vector to be 1. Additionally, it sets the second dimension to if and only if the token <bos>, Otherwise, it sets it zero. The third dimension of all embedding vectors is zero. Other dimensions can take any arbitrary values. Without loss of generality, assume <bos> is the first token the vocabulary, i.e. The first column. Then, we have:
1
1
0
0
WE WET
(17)
64,1
64,2
64,3
C4.V
Ed,1
6d,2
6d,2
6d,V
dxV
19

---

where Ed,s E R.
Secondly, for head dimensions h 1, construct the weights Wo: WK, Wv, Wo of the first attention head in the first layer. Specifically,
0
0
0
0
WK =
Wv
(18)
hxd
Axd
WK reads from the first dimension of the hidden state, which is initialized with I 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, Wy reads from the second dimension of the hidden state, which is initialized with if the token is <bos>. So, the value vector will have in its first dimension only if the corresponding token is <bos>.
We can be any arbitrary matrix. Wo will write the result of the attention to the third dimension of the hidden state and can be constructed as:
0
0
0
0
1
0
0 ..
0
Wo.
0
(19)
Now, verify that for any input sequence [<bos>, .,,...,......................... IT], the first layer recover
absolute positions , T
1] in the hidden state H We verify this for column t of H That is, we show that absolute position information available in the third dimension h (
First, we use the word embedding matrix We g to compute the embedding ()):
1
1
1
0
0
0
H ()
WEX
(20)
64.1
64,2
64.3
64.V
6d,1
64,2
6d.2
CdVV dx(r-1)
We now provide the attention computation position 1515 T First, we We compute the query vector by applying q: = (0).
gt (1 92, 13 .......... [h
(21)
Recall that We be any arbitrary matrix. So, Oj R can take any arbitrary value. Next, compute the key vectors by applying k; = W h (0)
1
i
ki
22
k
(22)
Note that all key vectors the same and we only need compute them up position & as the attention mask is causal, i.e query can only look at positions < t. Next, we compute the attention weight vectors
= -(gs ki), (g,, k2) K2).... .....
K.)
(23)
= =aa", a", "a....,"""
(24)
20

---

where a² Q1 92 .... + Next, we apply softmax to compute the attention probabilities.
Since all a''s are the same, have:
1 1 7
- softmax(())
(25)
Now, we compute the value vectors by applying
Wvh: :
11
472
(26)
Finally, we compute the output of the attention head by applying Wo:
0
0: = Wo
Σ 6 151
Wo
1 Σ vi i
Wo
0
1/t
0
(27)
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 (23), which helped us to only attend to position S So, the lengths of the attended sequence are always Moreover, the presence of <bos> token in the input sequence helped us to anchor the absolute position information. This is not problem in practice models are often prompted with some instructions which can act <bos> token.
With this information available the of the network, the feedforward sub-layer, with sufficient hidden width, can recover the absolute positions [1, 2....... ..., T +++ from the third dimension of attention output. This is because the feedforward sub-layer is MLP with ReLU activation. So, 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, show if the hidden state contains absolute positional information explained in the previous section, then the attention mechanism in all subsequent layers can implement relative positional encoding. We refer the readers to Appendices B.1 and C.I for the notation and definitions used this section.
Theorem (Relative Encoding). Suppose that the hidden state (1) contains absolute positional information, stated in Theorem 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 parameterization of fo such that, for I 2, the attention dot can be expressed as:
product between query and key k; at positions and (t 2 i)
(q,, ka) feor (gt, k.) ftel(t-)
(1)
where Sent is a function of their content, and Sret is function of their relative distance.
Proof.
Our proof only specifies few entries of weight matrices for attention heads in layers 2 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 Theorem To show NoPE can implement relative encoding, we only need to prove that its attention dot product depends on the relative distance between tokens (Sec
21

---

Appendix 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 2 2, we construct the weights Wo: WK of the attention heads the second layers and above. Specifically,
1
0
0
0
0
-1
0
WQ
W3,1
W3,2
W3,3
W3,4
W3,d
(28)
10h11
10
Wh,3
Wh.4
Wh.d hxd
0
0
0
0
Wv
W/,1
3,2
W3,3
3,44
W/sdd
(29)
10, 2,2
h,3
h,4
w/y h.dd
where wijs why E R can take any arbitrary value. Their corresponding Wy and Wo can take any arbitrary values long they do not override the first three dimensions of the residual stream.
Now we verify that for any input sequence æ [<bos>, Zi...., ..T]. the attention dot product between query qi and key k; at positions and (t 2 i) will depend the relative distance between tokens.
First, assume that absolute positions are computed in the hidden state H for 2 1, as stated in Theorem 1. Specifically,
1
1
0
0
0
0
3
T
H
h4.1
h4.2
h4.3
h4,4
h4.7+1
(30)
ha,1
hd.2
ha.s
ha,4
har dx(T+1)
where hiy E R can be any arbitrary value the first three dimensions of the hidden state reserved for PE computation. The rest of the dimensions can take any arbitrary values as in regular computation of Transformers.
now present the attention computations at position S 1. use We to compute query vector qe by applying q: Woh!". (1)
q: [1. -t, 23.3..... ...
(31)
where oj IR can take any arbitrary value. Next, we compute the key vectors by applying k; W W (
2
3
1
1
1
13
ka.2
ka,
122
K3
kr
(32)
kn.
kn.2
kn.3/
kint/
where k(,)) E IR can have any arbitrary value. So, for K; we have:
k; = i1, 1, Ka kn
(33)
22

---

Next, we let us present the attention dot product between qi and k;;
(gt, k.) =1.1 +
+ k3. + ... + Qn -2.
(34)
=i ++
Σ
-
(35)
/=3
h
- (t (t-
(36)
=nent (qt; kss) Srei -)
(37)
Thus, the dot product between and k; depends on the relative distance between tokens (assuming the of the terms do not cancel out which can be easily avoided by setting the respective weights in Equations (28) and (29)). Note that our proof uses the linear spacing between tokens, but the MLP the first layer can write any arbitrary function absolute positions the third dimension of the hidden state, which enables more complex relative encoding schemes.
D Experimental Details
D.1 Tasks
Here provide the details and more examples of the tasks and datasets 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 the validation set.
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.
Addition
Input
Compute:
5
7 2 + 1917?
Output
The answer is 5 5 6 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 digits. For the test set, buckets where any of the numbers have most L digits. The model is evaluated on the correctness of its predicted result.
Polynomial Evaluation The polynomial evaluation task (Nye al., 2021) asks the model to evaluate a polynomial expression at a given value of æ. The polynomial terms and digits are separated to make just the tokenizer does not glue symbols together.
Input
Evaluate
3
0
1
x ** ) % 10
Output
The answer is
The length bucket created based on the number of terms in the polynomial expression. We sample from U([ (4(-2,2) 2), the degree of each term from (1(0, 3), and the coefficient of each term from 2(-3, 3). We take the modulo of the result by 10 to make the task casier 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 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 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
23

---

through task. Each instance is sequence of tokens from the alphabet in random order, and the model is asked sort them in the canonical order.
Input
Sort the following numbers: 3 1 4 1
Output
The answer is 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:
1, 1, 9, 2 6, 3
Output
The answer is 3 1, 1, 5 9, 1 6, 5 3.
In this case, we sample each number from 2/(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 want specifically measure how the model generalizes to longer sequences not the value of summation result:
Input
Compute:
1 +
7 02044 10 ?
Output
The answer is 7.
Each digit is randomly sampled from (111, 9). The length bucket is created based on the length of the input sequence. The model is evaluated the correctness of its predicted result.
Parity In the parity task (Anil et al., 2022), we ask the model to compute the parity binary sequence.
Input
Is the number of 's in Output
The answer is No.
In the LEGO task (Zhang et al., 2023), the model is provided with a simple computation graph (DAG), where each node represents variable, and variables connected by simple operations which created the edges in the computation graph. We refer to Zhang et al. (2023) for detailed description.
LEGO
Input
If -1; -a; +b; +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 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 the end. The model is evaluated on the correctness of its predicted result.
24

---

Copy
The copy task is straightforward. The model has to repeat the input sequence in the output.
Input
Copy the following words:
<w1>
<>2>
<#3>
<W4>
<W5>
Output
<w1>
<w2> <n3>
<x4>
<55>
We create multiple variants of this task to better understand the models' generalization behavior. In the first variant, the imput 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 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>
<x2>
<u3>
<W4>
<W5>
Output
<w5> <W4>
<w3>
<#2>
<w1>
As in the copy task, 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 used in experiments. We the same hyperparameters for all models and positional encoding schemes. In our initial experiment, we tried a few more hyperparameters such as Ir {0.00001, 0.00003, 0.00005) and WeightDecay E {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 experiments.
D.3 Compute
In our experiments, we used single-GPU training setup for the models. Specifically, we ran our experiments on mix of NVIDIA V100 32G, NVIDIA RTX8000 48G, NVIDIA A100 40G, and NVIDIA A 100 80G GPUs. Depending on the GPU type and the positional encoding, each of our training runs took 6 to 15 hours, per each seed, 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 foundation for the training loop, optimizer, and the Transformer architecture. To ensure reproducibility, we will also release singularity binary with all dependencies and libraries enable running experiments any machine with NVIDIA GPUs and at any time in the future. Moreover, every reported number this paper is linked to the source code package that deterministically (up to GPU stochasticity) reproduces the results, which release publicly on GitHub at https:/ / //tptbbbttuttt//g//// thub. Coom/MGGil1-NLPPPPA leigggh--geeraazzzaa.a..
E
Full Results
E.1
Detailed Model Accuracy
We report the detailed results of our experiments Figures F.4 F.6. We refer the readers to Appendix D.I for the description of each task.
25

---

Table Summary of hyperparamters used in the experiments.
Parameter
Value
Optimizer
AdamW
Learning rate
0.00003
Weight Decay
0.05
Batch size
64
Learning Scheduler
Polynomial 6% of training steps 40K steps
Warm Up
# Train Steps
Decoding Method
Greedy (No Sampling)
Dropout (taken from HuggingFace)
0.1
Model dimension (taken from HuggingFace)
768
# Layers (taken from HuggingFace)
12
# Attention Heads (taken from FaggingFace)
12
E,2 Detailed Head Distance
Figure F.7 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 Section 5.2 for the details and analysis of these results.
E.3 Detailed Model Accuracy On Various Scratchpad Formats
Figure F88 shows the generalization of various scratchpad formats for each model aggregated across all datasets. Figures F.9 to F.15 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.
Pretraining at 1.3B Scale
In this section, we elucidate our preliminary assessment of length generalization on a pretrained LLM scaled to 1.3B. Ensuring fair evaluation, pretrain models across varied positional encodings, all on identical data with consistent parameters. Given the intrinsic significance element positions to the semantics in code data, our choice leaned towards code-based pretraining.
F.1 Model Architecture
Our approach remains consistent with the original codebase, merely increasing the model dimensions. Specifically, adopt a decoder-only Transformer structure encompassing 24 layers. The config- uration details are as follows: dmodel = 1024, dev 128, di 16, 384, and 32 attention heads. Transformer model with 1.3B parameters. We train the models with
Consequently, this amounts context size of 1024 tokens. For the rest of training hyperparameters, we follow Allal et al. (2023). Specifially, we use a global batch size of 256 and AdamW optimizer with 81 0.9, 3g 0.95. = 10 8 and weight decay 0.1. Also, the learning rate of 2 x 10 with cosine decay and 2% warm-up is used.
F.2 Dataset Selection
We utilize subset of 30M documents from the StarCoder dataset (Li et al., 2023). constituting a blend 40% Python, 25% Java, 25% JavaScript, 5% GitHuu issues, and 5% GitHub commits. Processed through the StarCoder tokenizer with vocab size of 49, 152, the dataset results in 30B tokens. We have trained the model for single epoch. For comprehensive details on remaining hyperparameters, direct readers Allal et al. (2023).
26

---

F.3 Generalization Evaluation
Our evaluation aims assess how the model's performance in predicting a given token varies with changes in context size, especially when the context size exceeds the training context size. Ideally, we expect the perplexity generally improve as the context size increases since the model has access to more information. In this experiment, we select sample of 1500 validation documents, each representing a single source code file. For each document, we calculate the perplexity of the last tokens, considering various context sizes ranging from 512 to 2560 (Note the model itself is pretrained with a context size of 1024) This approach allows us evaluate the model's perplexity under both in-distribution and out-of-distribution conditions. To keep the computation and number of inferences tractable, we measure the perplexity on a maximum of last 200 tokens the document and ensure exactly the same set of tokens are evaluated per each context size.
To obtain a comprehensive understanding of the model's performance, we also categorize documents into buckets based on their lengths and calculate the average perplexity within each bucket. This categorization enables us to examine the nature dependencies within each bucket, recognizing that longer documents do not always imply longer dependencies.
We present the results in Figure F.2 and Tables 3 and 4. First, is observed that all models benefit from a larger context up to the training size of 1024. In the I.I.. case (context length < 1024), no significant differences among the models are discernible across all length buckets. Conversely, in the O.O.D. case (context length >> 1024), the model trained with Rotary fails to generalize as its perplexity explodes in all cases, aligning with our findings Section 4. NoPE and ALiBi effectively generalize to larger context sizes up to 1800. However, as context sizes grow beyond that, ALiBi exhibits relative stability compared to NoPE, though both models show a pattern of increasing perplexity, potentially indicating inefficiencies to capture longer dependencies.
27

---

7550, 1000]
11000, 1250]
[1250. 1500)
5
3
2
1
550
600
500
600
700
800
600
800
1000
1200
11500, 1750
[1750, 2000]
22000, 2250
1500
10000
400
5000
1000
200
500
5000
10000
500
750
1000
1250
500
750
1000
1250
1500
500
1000
22500, 2500]
22500,
2750]
2750,
3000]
1500
1500
1000
1000
1000
500
500
500
1000
1500
1000
1500
500
1000
1500
2000
[3000,
3250]
3250,
3500]
[3500,
3750
2000
1500
1500
1000
1000
1000
500
0
500
1000
1500
2000
500
1000
1500
500
1000
2000
3750, 4000
14000.
4250)
42250,
4500
6000
2000
1500
4000
1000
2000
1000
0
500
2000
4000
500
1000
1500
2000
500
1000
1500
2000
500
1000
15000
2000
Context Size
Positional Encoding
NoPE
ALIBI
Rotary
Figure F22: Perplexity the three pretrained models on examples from various length buckets.
Each model is trained with different positional encoding schemes on identical training data and hyperparameters.
28

---

Table 3: The detailed perplexity (represented along with Figure F.2 for completeness). of the three pretrained models on examples from various length buckets (Part I)
Model
Context Size
Length Bucket [750, 1000
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
2560
NoPE
2.456
2.314
ALiBi
2.427
2.310
Rotary
2,401
2.271
Length [1000, 1250]
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
2560
NoPE
2.958
2.372
2.282
2.192
ALiBi
2.944
2.392
2.375
2.263
Rotary
2,920
2.344
2.259
2.170
Length Bucket 1250, 1500)
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
2560
3.122
2.951
2.722
2.676
2.618
ALiBi
3,077
2.940
2,816
2.723
2,678
2,670
Rotary
3.044
2.882
2.657
2.619
2.559
Length Bucket [1500, 1750]
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
2560
NoPE
2,620
2.541
2.467
2.258
2.187
2.158
2.121
ALiBi
2.616
2.564
2.527
2.305
2.226
2.249
2.307
Rotary
2:580
2.502
2.418
2.220
2,146
2.749
251.684
Length Bucket [1750,2000
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
2560
NoPE
3,002
2.911
2.853
2.704
2,436
2.397
4,581
ALiBi
2,966
2.908
2.954
2.774
2,480
2.487
2.595
4,114
Rotary
2.929
2.845
2,790
2.646
2.390
3.098
248.698
2054.099
Length
[2000,, 2250]
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
2560
NoPE
4,130
3.998
3,892
3.849
3.751
3.348
3.338
6.325
39.413
3,988
4.049
Rotary
4.007
3.878
3.787
3.744
3.657
4.190
146.958
531.824
722.276
Length Bucket [2250, 2500)
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
2560
2.493
146.219
ALBBi
2,764
2.655
2.647
2.570
2.499
2.441
2.361
3.695
17.
44.089
Rotary
2.732
2.514
Length Bucket [2500, 2760]
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
2560
NoPE
2,805
2.716
2.645
2.614
2.574
2,534
2.367
2,954
25.694
114,870
259.222
2.651
2.681
Rotary
2.776
2.686
2.615
2.587
2,554
3.302
120,402
503.155
621.873
676.160
732.808
Longth Bucket (2750, 3000)
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
2560
NoPE
2.776
2.728
2.694
2.666
2.620
151.810
311.138
536.225
ALiBi
2,830
2.789
2,825
2.766
2.735
2.742
2.741
3,680
13,814
42.951
102.930
150,322
Rotary
Length Bucket [3000, 3250)
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
2560
NoPE
2,783
2.697
2.639
2.395
2.555
2,519
2,498
4.239
32.277
153,248
312.356
$21.752
2.782
2.750
Rotary
2.733
2.649
2,589
2.542
2.506
3.107
169.800
471.389
619.115
670.209
804.750
824.417
Length Bucket [3250, 3500)
512
640
760
1024
1200
1400
1600
2048
2304
2560
3.260
3.140
3.009
2.828
143.613
ALiBi
3,206
3.116
3.127
3.073
2.922
2,940
3.104
5.077
16.838
47.832
106.607
151.288
Rotary
29

---

Table 4: The detailed perplexity (represented along with Figure F.2 for completeness). of the three pretrained models on examples from various length buckets (Part II)
Model
Context Size
Length Bucket (3500,3750)
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
25600
NoPE
3,070
3,003
2,969
2,942
2,894
2,826
2.816
3.808
30.840
122.338
278.935
473.120
ALiBi
3.054
3.011
3,069
3,006
2.954
2.971
3.107
4.845
15.691
46.406
106.966
156.849
Rotary
3.719
169.445
Length Bucket [3750, 10000
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
2560
NoPE
2.703
2.593
2.564
2.517
2,466
2.440
2.427
3.447
35.851
135.291
281.145
438.679
ALiBi
2.657
2.570
2,614
2,553
2,515
2.541
2.639
4.049
14.112
40.070
94.953
138.232
Rotary
2.645
2.536
2.506
2.461
2.416
2,981
147.012
508.386
671991
707.306
861.924
873.948
Longth Bucket (250))
NoPE
3.096
3.021
2.947
2,905
2,862
2.843
2,809
3.459
27.171
109.982
244.809
414.226
ALiBi
3.086
3.040
3,064
3,028
2,931
2,983
3,058
4.316
13.509
37,900
88.864
129.419
Rotury
3,054
2.973
2.906
2.868
2,831
3.626
158.974
723.175
1114.522
989.245
1057.793
960.442
Length Bucket [4250, 4500]
512
640
760
878
1024
1200
1400
1600
1800
2048
2304
2560
NoPE
2.992
2,869
2,815
2.786
2.872
8.839
42.054
133. 110
255. 355.007
ALBBi
3,004
3.008
3.022
2,975
2,913
2.975
3.097
4,913
15,522
43.614
98.910
142.342
Rotary
2,899
2,838
2.775
2.731
3.603
174.717
528.865
694.649
741.368
806.988
857,006
Entzedding Dimensions
Dimesim
Dimemdion
Oronddie
Ciemsraion
_11
-20
-10
-20
-25
Dimercian
Iin..
Urboddrg 1996
-10
Ericcee Vatee
-30
-25
500
KOKK
Figure F.3: The learnt bias value bbacket() (taken from the pretrained T5-3b model) visualized for relative distance bucket bucket(.) E (1]) and 12 heads. Bucket exclusively used for all distances larger than 128 tokens. These results demonstrate that while T5 has heads that mask distant tokens, other heads attend to distant tokens when required.
30

---

Copy (Variant 1)
Copy (Variant 1 (2x))
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
30
40
30
40
Copy (Variant 2)
Copy (Variant 3)
0.6
0.4
0.4
0.2
0.2
Accuracy
10
20
30
40
10
20
30
40
Copy (Variant 3 (2x))
Reverse (Variant 1)
10
20
30
40
10
20
30
40
Reverse (Variant (2x))
Reverse (Variant 2)
30
40
30
40
Problem Length
Positional Encoding
NoPE
Relative PE
ALiBI
Rotary
Absolute Position Embedding
Figure F.4: Generalization behavior of positional encoding schemes Primitive tasks.
31

---

Addition
Summation
0.8
0.8
0.6
0.6
16
Parity
Sorting (Single Token)
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
Accuracy
16
16
Sorting (Multi Token)
Polynomial Evaluation
0.8
0.6
0.6
0.4
0.4
0.2
0.2
8
12
16
12
16
LEGO
12
16
Problem Length
Positional Encoding
NoPE
T5's Relative PE
ALiBI
Rotary
Absolute Position Embedding
Figure F.5: Generalization behavior of positional encoding schemes on Mathematical Reasoning tasks.
32

---

SCAN
PCFG
900000000000000000 9983
0.8
0.8
Accuracy
0.6
0.6
20
30
40
50
10
20
30
Problem Length
Positional Encoding
NoPE
T5's Relative PE
ALiBi
Rotary
Absolute Position Embedding
Figure F.6: Generalization behavior of positional encoding schemes on Classic Length Generalization tasks.
Layer #01
Layer #002
Layer #003
Layer #/04
0.5
Layer #05
Layer #06
Layer #00
Layer #08
DINoPE, .M)
1.5
0.5
Layer #09
Layer #10
Layer #111
Layer #112
0.5
Example Length
Positional Encoding (M)
NoPE
Rotary
Embodding
Figure F.7: Layer-wise distance PE's attention patterns with other positional encoding schemes
measured across instances of SCAN dataset.
Scratchpad Format
Mean Reciprecal Rank (-)
No Scratchped
Full
"Step Input"
0.50
"Step Computation"
"Step Output"
0.25
Fall "Intermeditte Vord"
"Remaining Parts"
Minimal (Only Compute-
No PE
T5's Rel.
Bias
ALiBi
Rotary
APE
Figure F.8: The optimal scratchpad format is aggregated across all datasets per each model. The optimal scratchpad format is different for each model.
33

---

0.20
0115
T3's PE
Accuracy (Ang. over all OOD lengths
0.20
0115
ALiBi
0.20
0.15
0.05
Rotary
0155
0.10
0.00
Absolute Position Embedding
0.15
8.09
No Scratchoad
Mininal (Olly Computes Outpur)
Full
Fut "Stop loput"
Full SStp Computation"
Full "Sto Outpot"
Full Intermediate Vers"
Full- Remaining Parts"
Scratchpad Config
Figure F9: Generalization of various scratchpad formats for each model on the Addition task.
No PE
0.4
0.3
02
01
0
Relative
Accuracy (Avg. over all ODD lengths)
0.3
ALIBi
0.4
Rotary
0.4
Absolute Position Embedding
0.4
0.3
0.2
0.1
0
No Scratchoad
Misinal (Gnly Compute Outpur)
Full
Full "Stap Ioput"
Full "Stop Computation
Full SSop Outpot"
Full "Intermediats Vary"
Full "Romainiig Pang
Scratchpad Config
Figure F.10: Generalization of various scratchpad formats for each model on the Summation task.
34

---

No PE
0.8
0.6
0.4
02
Relative
Accuracy (Avg. over all OOD lengtts)
0.8
0.6
0.4
0.2
ALiBI
Rotary
Absolute Position Embedding
0.8
0.0
0.4
0.2
0
Scratchpad
Minimal (Only Compute Ourpus)
Full
"Step Ieput"
Full
"Ste Outpon"
Intormediioee Vass"
Full- "Reinaining Pang
Computation"
Scratchpad Config
Figure F.11: Generalization of various scratchpad formats for each model on the Parity task.
No PE
0.75
0.50
0.25
T5's Relative
Accuracy (Aug. over all OOD lengths)
0.75
0.50
0.25
ALiBi
Rotary
0.75
0.50
0.25
ute Embrdding
0.25
No Seratchpad
Mininal (Owty Compute Compute--utgoul Outgur)
Full
Full "Step Inpus"
Full: "See Output"
Full. "Remaining Part
Scratchpad Config
Figure F.12: Generalization various scratchpad formats for each model on the Sorting task (Single Digit).
35

---

No
0.75
0.50
0.25
T5's Relative
Accuracy (Avg. over all OOD lengths)
0.75
0.50
0.25
ALiBi
0.75
0.50
0.25
Rocary
0.50
0.25
Absolute ute Position Embedding
0.75
0.50
No Scratchpad
Misinal (Only Computo Compute-Ourpuut) Ourput)
Full
Full "Stop Input"
Full "Stop Output"
Full "Ronsining Parts
Scratchpad Config
Figure F.13: Generalization of various scratchpad formats for each model on the Sorting task (Multi Digit).
PE
0.6
0.2
15's Relative PE
Accuracy (Avg. over all OOD lengstt)
0.6
0.4
0.2
0
ALiBi
0.6
0.4
0
Rotary
0.6
0.4
0.2
Absolute Position Embedding
0.6
0.4
0.2
No Scratchpad
Minimal (Gnly Computte Outpon)
Full
Pull "Step loput"
Full SSep Computationn
Full "teep Output"
Full "Itormadatt Vars"
Full "Ramaining Pany
Scratchpad Config
Figure F.14: Generalization of various scratchpad formats for each model on the Polynomial Evaluation task.
36

---

06
0.6
T5 Relative PE
Accuracy (Avg over all (0DD lengtha)
0.8
04
02
0
0.8
0.6
Rotary
04
Embedding
0.8
0.6
No Scretchpad
Mininal (Oaly Computo Outtuut) Outpue)
Full
Full "Step Imput"
Full "Step Ourgut"
Full "Remaining Parts"
Scratchpad Config
Figure F.15: Generalization of various scratchpad formats for each model on the LEGO task.
37


Reviews:
[{"review_id": "WREoCO8si5", "reviewer": "Reviewer_VbrS", "summary": "The paper presents a comprehensive study on the role of positional encodings in Transformer models, focusing on their ability to generalize over sequence lengths. The authors introduce a novel positional encoding method, which does not use explicit positional information.", "questions": "1. How would NoPE perform in a broader range of tasks beyond the mathematical and reasoning tasks evaluated in this study?\n2. Could the authors elaborate on the potential implications of their findings for the design of future Transformer models?", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper introduces a novel positional encoding method, which is a significant contribution to the field. \n2. The paper is well-written and easy to follow. ", "weaknesses": " The authors did not study how large-scale pretraining affects different PEs due to the lack of publicly available large language models trained with various PEs under similar conditions. This leaves a significant aspect of the problem unexplored.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time in providing useful feedback and questions which we now address:\n\n> Effect of large-scale pretraining on PEs\n\nThank you for raising the concern regarding the exploration of large-scale pretraining effects on different PEs. It's worth noting that the pretraining of large language models (LLMs) demands significant computational resources. For instance, training StartCoder-13B necessitated ~320K hours on NVIDIA A100 80G GPUs [1], while MPT-7B utilized a cluster of about 500 A100 GPUs for 10 days, translating to a cost nearing $200K [2]. Given the constraints of our available resources, such extensive undertakings are well beyond our capacity. Although the scale of our models was limited, we made sure to perform extensive evaluations across many tasks and seeds to support our conclusions.\n\nHaving said that, we have provided preliminary results on larger-scale models and pretraining experiments in the General Response. These scaled up experiments exhibit patterns *consistent with those presented in our submission* suggesting the same result might hold for larger scales. Moving forward, we are preparing the necessary resources for pretraining at 1B parameters (albeit at limited scale) to further improve the empirical results of the draft.\n\n\n> NoPE performance in a broader range of tasks \n\nWe would like to point out that although we used mathematical and reasoning tasks—common benchmarks in length generalization literature [3,4]— in our evaluation, these are foundational and can be seen as representative of more complex tasks. Nonetheless, our empirical investigation suggests that NoPE overfits less than other explicit PEs, making it a suitable choice in scenarios prone to positional shortcuts [6]. \n\nMoreover, results in section 6.1 demonstrate that NoPE, in contrast to ALiBi, can reliably attend to both long and short range dependencies. Coincidentally, Liu et al [5] recently observed that LLMs are more sensitive to context provided early or late in the context. This suggests that LLMs trained with NoPE could potentially offer more benefits in such contexts when compared to those trained with ALiBi.\n\n\n> Implications of our findings\n\nWe believe our findings can impact the development of future Transformer models in two primary ways:\n\nFirst, as acknowledged by Reviewer 2 (qZrr), our finding on the commonly used PEs (such as Rotary & ALiBi) can inform the community about their potential shortcoming especially in terms of length generalization and encourage further development and research on better positional encoding methods. This is especially important as training LLMs is an extremely expensive and resource-intensive undertaking; any hidden shortcomings in the model architecture could be vastly wasteful and harmful to the environment.\n\nSecondly, and more notably, our theoretical and empirical analyses reveal that decoder-only Transformers possess inherent mechanisms for representing positions. These mechanisms perform better than or on par with other explicit PE schemes. This, as suggested by Reviewer 4 (C4oP), could guide the design of more streamlined and simpler Transformer architecture and positional encodings that leverage and strengthen these internal mechanisms.\n\nWe hope that the clarifications provided have resolved any lingering questions. Would you consider increasing your ratings  given the main clarifying points outlined?\n\n- [1] Li et al, StarCoder: may the source be with you!, 2023\n- [2] https://www.mosaicml.com/blog/mpt-7b, 2023\n- [3] Delétang et al, https://arxiv.org/abs/2207.02098, ICLR 2023\n- [4] Ruoss et al,https://aclanthology.org/2023.acl-short.161.pdf, ACL 2023\n- [5] Liu et al., https://arxiv.org/pdf/2307.03172.pdf, 2023\n- [6] Sinha et al, ​​https://arxiv.org/abs/2210.12574, EMNLP 2022 Findings"}, {"review_id": "Vo5h0gmlLV", "reviewer": "Reviewer_qZrr", "summary": "Length generalization is one of hot topics for transformers. In this paper authors investigate how positional embedding influences this generalization for **decoder-only** models on **reasoning tasks**. Authors compare for variety of tasks (e.g. copy, summation, sorting, etc.) sinusoidal positional embedding, T5, AliBi, Rotary and no positional embedding (NoPE). \nFirst, authors proof by construction that NoPE for decoder-only models is able to learn positional information due to causal masking. Then authors show that none of the positional embeddings generalizes to longer sequences, while NoPE in some cases performs even better than others (though performance is still bad compared to seen lengths). Empirically by comparing attention patterns authors show that NoPE learns attention similar to T5 models. Finally authors also play with scratchpad and show that it is not always helping generalization for longer sequences.", "questions": "- from the Abstract and introduction I expected to see NoPE working well for GPT-models, while main results are provided for small-scale models and reasoning tasks rather than language modeling itself. I guess could be better to state about reasoning tasks in the abstract in addition to the restriction to the decoder-only models to be considered\n- From results (Appendix plots) I can see that actually no any positional embedding (including NoPE) generalized to long sequences for the reasoning tasks, so the statement \"Overall, our work suggests that explicit position embeddings are not essential for decoder-only Transformers to generalize well to longer sequences.\" is not supported as NoPE also doesn't work (works only for very couple cases + sequence length is not very large compared to training one).\n- For RoPE did authors try to insert it in every layer similar to T5 or AliBi which are used in every transformer layer? Otherwise could be not fair comparison in the end if the positional embedding saturates over the layers.\n- Eq. (2) why do we take min? Also do we consider all possible pairs of attention heads or we do pairing head1 from A and head1 from B? For other part of evaluation I found smart to use another seed with NoPE to measure how it changes to see that it actually like T5.\n- line 40-49: even for relative positional embedding it was shown that it could fail to generalize, see \"CAPE: Encoding Relative Positions with Continuous Augmented Positional Embeddings\", NeurIPS 2021. In the same paper as well as e.g. in \"An image is worth 16x16 words: Transformers for image recognition at scale\", ICLR 2021 \"Conditional Positional Encodings for Vision Transformers\", ICLR 2023 there were reported that NoPE can works for the encoder-based models.\n- line 301-305: yes, authors consider LLMs style models (which is just decoders) but the data / tasks are different, so that we cannot just generalize from the observations to the LM data as in LM data we saw opposite behaviour. I found confusing the whole paragraph in this context.\n- Limitations stated as \"not study how large-scale pretraining affects\" - AliBi did study on WikiText103 which not large-scale + model was also rather small <1B params. I believe the issue is the data / task type (see below comments).  \n- Notation of multiplication as dot is weird. Prefer to see normal multiplication in $k.d$ -> $k\\cdot d$\n- Eq. 29 $W_V$ -> $W_K$\n- Fig. E2 for Copy Variant 1: did authors check if bias in T5 is learnt to be negative or positive? As in AliBi it emulate smoothed window attention and far away positions are mainly ignored, while for the task if copy you need to look at the whole sequence indeed. So could be that design of the positional embeddings are not designed for specific tasks where another reasoning on the positions is done (e.g. for LM we just need some summary context, but not exact values for every positions as we don't do e.g. copy task). Wonder to see what T5 bias then learnt to be consistent or disprove this hypothesis. For now the hypothesis seems to be consistent along all plots shown in the Appendix: e.g. for all copy tasks and reverse AliBi doens't work); for sorting Rotary is the best - which can be explained as we can solve sort by just comparing neighbors and reordering them, so strong relative position bias is needed; for other more or less different positional embeddings behave similarly.\n- Why do authors consider only 2L sequence generalization and not longer as in AliBi? I see that in the end we are not able to generalize even from 20 positions to 40 positions for simple reasoning tasks, while in LM (e.g. AliBi) they generalize to longer contexts, e.g. 16k tokens. I think in the main text it is overstated that some positional embeddings do not work - there should be clearly expressed \"let's consider reasoning tasks different from LM and investigate how there length generalization happens.\" I find that it would be interesting to have discussion on the difference between LM task and considered in the paper, as right now for me it is not clear why LM generalization with AliBI e.g. works nicely for even 16k tokens while in the simpler reasoning tasks this is not the case. Is it model? data? task itself? I presume we have more complex dependence on the positions and sequence length than in standard LM where simple summarization of far away context could be enough for good generation longer sequences while in reasoning task it is crucially to have proper positions distinguishing.", "limitations": "Limitations in the main text, however main restriction on considering non-LM tasks is not clearly delivered in the paper.\n\n**Update: Originally score was 3 for contribution and overall score 6-weak accept. After rebuttal and discussion they are raised to 4 for contribution and 7-accept.**", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- first time (at least I didn't see in prior works) formal proofs that decoder-only models are capable of positional embedding reconstruction (I went through the proof, no issue found with the math)\n- emergency for other positional embeddings development or investigation of transformers failure for the longer sequence generalization for reasoning tasks\n- interesting empirical results for reasoning tasks showing that mainly all positional embeddings currently widely used do not work for reasoning task on longer sequences while no positional embedding (NoPE) works similarly or even better sometimes\n- interesting insights on the NoPE (learnt attention pattern is more similar to models trained with T5 bias) and results on scratchpad", "weaknesses": "- overstatement in the test about positional embeddings for the decoder-only models: here it should be clarified about the type of the tasks where we apply, as for LMs we know that e.g. AliBi is working.\n- small scale experiments and limited length generalization evaluation.\n- no in-depth comparison of the root for the different behaviour e.g. for AliBi between the reasoning tasks and LM task.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your positive and detailed feedback! We now address the key questions and concerns in detail below:\n\n> Clarifying the Scope and Generalization Setup\n\nThank you for bringing attention to the perceived overstatement concerning generalization capability of our evaluated models. We recognize the importance of clearly defining the scope and context in which our findings apply. Our intention was to explore the impact of positional encoding on length extrapolation in *downstream* tasks, particularly focusing on reasoning and mathematical tasks. We have attempted to articulate this scope in both the **abstract** (lines 4-6, 9-11) and the **introduction** (lines 44-47, 60-61, 63-64), where we describe our evaluation encompassing these domains as downstream tasks.\n\nHowever, acknowledging your observation, we realize that further clarification may be necessary to prevent any confusion. Therefore, we plan to revise the introduction and abstract to underscore the scope more explicitly. Additionally, we will include a nuanced discussion regarding the distinction between \"language modeling perplexity vs downstream performance,\" as a framework for assessing length generalization.\n\n\n> Small scale & Length Generalization Evaluation\n\nWe acknowledge the reviewer’s concern regarding the scale of our models. In the absence of LLMs trained with various PE under the same condition, it is increasingly difficult to evaluate the impact of PEs in pretrained models on length generalization. We'd like to point out that our chosen model size is consistent with approaches taken in recent research [1,2]. Even with these constraints, we ensured a robust evaluation process, conducting comprehensive assessments across numerous tasks and seeds to reinforce our findings.\n\nMoreover, we've already started to address these concerns by including preliminary **larger scales** and **language model pretraining** results in the limited timeframe of the rebuttal period (see General Response). These insights align with our original findings, suggesting they may apply at larger scales. We're gathering resources for pretraining at a 1B-parameter level, albeit on a limited scale, to further enhance the empirical aspect of our work.\n\n> Analysis on discrepancy in ALiBi’s performance in Language Modeling vs Downstream Task\n\nThe reviewer makes an astute observation regarding ALiBi inductive bias as “smoothed window attention,” a phenomenon we refer to as Recency Bias in the paper (Sec. 6.1). Indeed, ALiBi (in the its paper) reports successful generalization to longer sequences in terms of language modeling (LM) perplexity (PPL), a contrast to our findings where ALiBi fails in downstream tasks even for much shorter sequences. This is the underlying reason why we opted for 2L, as we identified that models already falter for these shorter sequences.\n\nWe hypothesize that this discrepancy stems from the unique combination of the nature of the language modeling task and the recency bias in ALiBi. In general, modeling natural language often requires a shorter context due to human cognitive constraints, and brief information about past context may suffice for predicting the next token. In support of this, Chi et al. [6] have recently shown that ALiBi's length extrapolation on LM PPL can be emulated using windowed attention. (Refer to General Response for more discussion)\n\nHowever, this inductive bias, while potentially beneficial for LM PPL, does not universally translate to success in downstream reasoning tasks. These tasks often necessitate long-range dependencies, a requirement where ALiBi can underperform. As Reviewer cleverly noted, this is evident in tasks like Copy and Reverse, where ALiBi typically lags behind other relative PEs. Please refer to General Response for much detailed discussion.\n\n> Clarifying the statement in lines 18-20\n\nWe acknowledge the concern regarding this sentence. Our aim was to show that explicit PEs underperform NoPE in length generalization, aligning with evidence that they can challenge Transformers [4,5]. We'll revise the wording to accurately convey our findings.\n\n> Inserting RoPE in every layer.\n\nYes. we apply rotary in every layer, our implementation is borrowed from GPT-NeoX. We will add this detail in the appendix.\n\n> All possible pairs of attention heads and the intuition behind the lower bound on distance in Eq. 2.\n\nYes, we do consider **all** possible pairs of attention i.e. head_i from A and head_j from B where i, j$ \\in$ [1, num_heads]. We chose min to have a more strict evaluation to find if there is any meaningful and significant difference among NoPE and absolute PE encoding models. The evaluation would be more reliable if two models are shown to be different from each other even if we take the min. Nevertheless, taking the mean will also result in the same pattern and ranking (see Fig. 2 in the uploaded PDF)\n\n> References to generalization in relative PEs in vision Transformers\n\nWe thank the reviewer for the reference. We will incorporate them in the paper. Also, we'd like to note that in the text domain, encoder-only transformers become bag of words without PE [3].\n\n> Potential Confusion in line 301-305\n\nWe appreciate the reviewer's insight. Our intention was to highlight our evaluation's unique focus on decoder-only models and downstream tasks. We will revise this paragraph to eliminate any confusion.\n\n> Typos\n\nThank you for spotting them! We will correct them.\n\nWith these clarifications, would you kindly consider increasing your score? \n- [1] Delétang et al, https://arxiv.org/abs/2207.02098, ICLR 2023\n- [2] Ruoss et al,https://aclanthology.org/2023.acl-short.161.pdf, ACL 2023\n- [3] Haviv et al, https://aclanthology.org/2022.findings-emnlp.99/, EMNLP 2022 Findings\n- [4] Sinha et al, ​​https://arxiv.org/abs/2210.12574, EMNLP 2022 Findings\n- [5] Luo et al, https://aclanthology.org/2021.acl-long.413/, ACL 2021\n- [6] Chi et al. https://arxiv.org/abs/2212.10356, ACL 2023"}, {"review_id": "mdpUqITeeQ", "reviewer": "Reviewer_rWd9", "summary": "This work follows a long line of work analysing the effectiveness of various types of positional encodings and, in particular, a line of work exploring the effectiveness of causal masking without any positional encodings [1 - 8]. To that end, they evaluate the length generalisation performance of Transformers trained with various types of positional encoding schemes on a diverse set of reasoning and algorithmic tasks and find that Transformers without positional encoding schemes generalise better to higher lengths than other encoding schemes.\n \n \nThey consider 3 three types of tasks -- primitive (copying or reversing strings), algorithmic (addition, parity, etc.), and prior length generalisation benchmarks (e.g. SCAN). They evaluate five different encoding schemes, including Alibi and rotary encodings. They use autoregressive decoder-only Transformers of sizes of the order of 100M. For each task, Transformers are first trained on a set of examples using a language modelling objective and are then evaluated on examples of higher lengths.\n \nAcross the three types of tasks, they find that Transformers without positional encoding (but with masking) and T5's relative bias outperform other encoding schemes. Additionally, they show via a construction that Transformers without positional encodings can simulate both absolute and relative encoding schemes. They compare the attention patterns of Transformers trained without positional encoding schemes with other schemes and find that the attention patterns are most similar to relative positional encodings. Lastly, they find that when trained with a scratchpad, T5's relative positional encoding scheme and no positional encodings seem more effective than others.\n \n ", "questions": "(Q1) Regarding Section 5.2, if the models are trained with different positional encoding schemes from scratch, how can similarity between attention patterns help us determine how the model is computing positional information? Is it not possible that the models have very different learning trajectories? What about cases when Transformer without positional encoding performs better than relative encodings, wouldn't the underlying mechanism be different in that scenario? I think it is interesting the attention patterns without encodings are relatively much closer to ones with relative encodings (close to the baseline with different initialisations) than other ones, and that does provide some evidence that it is closer to relative encodings. But it is not clear to me why comparing the attention patterns should help us determine which type of positional information is being used.\n", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\n(S1) **Interesting results.** Overall, I believe there are several interesting findings in the paper. I believe the contributions in the paper take a step forward in understanding the effectiveness of Transformers with just causal masking. The analysis with the scratchpad setup demonstrating the importance of PE for scratchpad and the effect of scratchpad for length generalisation is interesting as well.\n \n \n(S2) **Sound experimental setup and well-motivated.** The question of understanding and identifying the most effective positional encoding scheme is an important problem, and this work takes a step forward in that direction. The choice of tasks seems interesting, and the evaluation with Transformers trained with language modelling objectives is more aligned with practice than prior works that have explored this direction.\n \n \n(S3) **Well written.** The paper is well-written, the motivations are clearly outlined, and the arguments are well-presented.\n \n", "weaknesses": "\n(W1) **Novelty of results is slightly overclaimed.** Based on my limited knowledge, the use of Transformers without positional embeddings and with only causal masking was first studied in [1]. It was later analysed empirically [2,3] and theoretically [3, 5] in further works. These works mostly suggested that Transformers without positional encodings are competitive with standard encoding schemes on machine translation and language modelling tasks. On synthetic formal language tasks, [4] and more recently [6] have noted that using no positional encoding leads to better length generalisation performance. In more practical settings, recently [7, 8] have shown that large language models trained with only causal masking are competitive with models with positional encoding.\n \nThe fact that Transformers with only causal masking can encode positional information and generalise well to higher lengths is not entirely new. To be fair to the authors, I do not think that they explicitly claim this. I think the paper does a good job of establishing that just causal masking is better at length generalisation than various other schemes in a more systematic way. However, given the prior work exploring Transformers with only causal masking, the framing of the introduction seems a bit odd, and some of the papers mentioned above [1-8] are mentioned passively in the paper. It could be helpful to readers unfamiliar with the area if the prior work was presented in a more comprehensive manner.\n \n \n(W2) **Effect of scale.** Since the tasks in the paper are confined to synthetic tasks and models with ~100M parameters, it is still unclear if training LLMs without positional encodings will be better for length generalisation in practice. Modifications to Transformers at this scale for effectiveness on such tasks have often not scaled to LLMs in practice. As mentioned in the paper, that could require a larger computational budget which is understandable to some extent. But at the same time, comparing Transformers trained for language modelling on text data on higher lengths would have been useful. Based on the results in [7, 8], it seems like positional encoding schemes help improve perplexity in language modelling, but it may be interesting to see if that changes for length generalisation tasks.\n \n \n \n \n   \n   \n[1] DiSAN: Directional Self-Attention Network for RNN/CNN-Free Language Understanding. 2017  \n[2] Assessing the Ability of Self-Attention Networks to Learn Word Order. 2019  \n[3] Transformer Dissection: An Unified Understanding for Transformer's Attention via the Lens of Kernel. 2019  \n[4] On the Ability and Limitations of Transformers to Recognise Formal Languages. 2020  \n[5] On the Computational Power of Transformers and its Implications in Sequence Modeling. 2020  \n[6] Transformers Learn Shortcuts to Automata. 2022  \n[7] Transformer Language Models without Positional Encodings Still Learn Positional Information. 2022  \n[8] Bloom: A parameter open-access multilingual language model. 2022  \n \n \n \n \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you, we are delighted that you like our work!\n\n> Novelty of results\n\nThank you for your insightful comment on the novelty of our results and the framing of our introduction. We agree that the field has seen previous work on Transformers without positional encodings, as you have detailed.\n\nWhat sets our work apart, however, is the systematic evaluation we conduct on the impact of widely used positional encodings on length generalization specifically in *downstream tasks* for autoregressive (decoder-only) Transformers. The downstream aspect of our work differentiates us with works such [7] and [8]. While other works such as [6] have explored various aspects of Transformers without positional encodings, our focus is unique in its in-depth examination of differences between widely used PEs. Furthermore, our study moves beyond showing that NoPE performs on par with other methods in IID settings, to demonstrate its potential superiority in OOD scenarios, thereby differentiating our findings from [7, 1, 2]. Our theoretical contributions are also distinctive, as we are the first to directly show that both relative and absolute encoding are recoverable in decoder-only transformers, in contrast to the theoretical analysis in [3] (understanding attention through lens of kernels) and [5] (turing-completeness via emulating RNNs).\n\nTo ensure clarity for readers unfamiliar with this area of study, we appreciate your suggestion to refine the related work section and the introduction. We will take care to present a more comprehensive review of the prior work and history of NoPE, including the specific contributions you've highlighted, and position our work within this context to reflect its unique contributions to the field. This adjustment will further enhance the paper's accessibility and relevance to its intended audience.\n\n> Effect of scale. \n\nWe acknowledge the reviewer’s concerns about the effect of scale. As the reviewers correctly points out, training LLMs in practice requires large amounts of compute budget (even at relatively small scales such as 7B) and expertise, which is only possible at few industrial labs. The challenging nature of such undertaking is evident in the underwhelming performance of various open-source LLMs [9].\n\nWith that said, we take initial steps in addressing this concern by providing the preliminary results for scaling the model size and pertaining to the General Response section. These results affirm our initial findings, offering encouragement for their applicability at larger scales. Furthermore, we're actively working on more extensive pretraining experiments with diverse data and larger models (1B), to the extent of our available resources.\n\n> (Q1) Similarity Between Attention Patterns\n\nWe appreciate this thought-provoking question, and we recognize the complexity of evaluating positional information through attention patterns. But, we’d like to point out that in our experiments, the models share identical configurations except for the positional encoding, so most variation in their behavior can be attributed to the different PE methods. This provides a foundation for comparing their behavior, although, as you correctly noted, the learning trajectories might diverge across models.\n\nTo counteract this potential divergence and offer a more robust measure, we compare all pairs of attention heads within a given layer across multiple seeds. This allows us to observe consistent trends that go beyond individual variations.\n\nIt's noteworthy to mention that in the interpretability literature, attention patterns have emerged as a prevalent method to probe the internal mechanisms of Transformer models [10,11]. While this may not provide an absolute understanding of the underlying positional information computation, our findings offer valuable insights into the relative influence of different encodings. The observation that attention patterns of NoPE are closer to relative encodings than others provides preliminary evidence of their internal workings.\n\n\n- [1] DiSAN: Directional Self-Attention Network for RNN/CNN-Free Language Understanding. 2017\n- [2] Assessing the Ability of Self-Attention Networks to Learn Word Order. \n- [3] Transformer Dissection: A Unified Understanding for Transformer's Attention via the Lens of Kernel. 2019\n- [4] On the Ability and Limitations of Transformers to Recognise Formal Languages. \n- [5] On the Computational Power of Transformers and its Implications in Sequence Modeling. 2020\n- [6] Transformers Learn Shortcuts to Automata. 2022\n- [7] Transformer Language Models without Positional Encodings Still Learn Positional Information. 2022\n- [8] Bloom: A parameter open-access multilingual language model. 2022\n- [9] https://kaistai.github.io/FLASK/\n- [10] https://aclanthology.org/P17-1088/\n- [11] https://aclanthology.org/2020.acl-main.312/\n"}, {"review_id": "2KdpD881PM", "reviewer": "Reviewer_C4oP", "summary": "Beyond model training, sequence length is one of the crucial aspect impacting the fluency, accuracy and completeness of LM outputs. For transformer based model's positional embeddings (PE) are used to explicitly represent the location of tokens. Over the past few years several works have attempted to propose a better PE approach, particularly aiming to improve over the original absolute PE of the Transformer. \n\nThis work, proposes a no positional encoding (noPE) model training for decoder only Transformer, to better generalize on generation length. The proposed noPE LM is evaluated on set of maths and reasoning tasks, using a small size (~100M parameter) LM. Findings show that noPE based LM performs similarly with relative PE based model (from the T5 model), and outperforms models with alternative PE variants such as Rotary, AliBi, and absolute PE for length generalization. Along with the evaluation results, detailed empirical analysis and theoretical arguments are provided for why noPE LM can intrinsically support an absolute and relative token position representations.\n", "questions": "- In addition to the mean rank, can authors add more task specific evaluation metrics, or could you please provide more motivation on why not to report task specific performance metric?\n- This can be a hypothetical one, have you considered a fine-tuning approach for LM's, for instance removing the PE when fine-tuning for down-stream tasks?\n- Can authors expand more on the selection of the LM size (100M parameters)? can we expect similar findings to hold if model size changes (i.e. larger LM's with more diverse and large scale train data)?  ", "limitations": "Limitation is provided, specifically explaining why the proposed noPE is not applied for large scale LM training. The limitation, not being able to access publicly available LM can be further expanded, for instance why not use 500M? If there is any identified societal impact its encouraged to include it. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This work, provided an in-depth analysis of Transformer LM training and inference without using PE. Although, the focus is to address the question of LM length generalization, the findings inform future possibility of an increasingly simplified transformer based LM's. In addition to the surprising results where noPE works in a similar way as the best performing relative PE (T5's PE), the work, delivered a thorough discussion as to why noPE works.\n \n", "weaknesses": "Despite the finding not using PE (noPE) can generalize for sequence length, the following points remain unanswered or not fully investigated:\n- Tasks selected for modeling and evaluation does not cover challenging length generalization scenarios. For instance, the noPE approach could have been testing using a summarization task which is highly impacted by the length of the summary.\n- Regardless of the provided results on length generalization, detailed and task specific performance metrics comparing LM's with PE's and noPE LM is missing. The absence of these comparison leaves open question on task specific performance comparison.   ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's insightful feedback and questions, and we will now address them:\n\n> Inclusion of other tasks such as summarization\n\nWe acknowledge the reviewer's concern about including more challenging tasks, such as summarization. However, we'd like to clarify why we focused on reasoning and mathematical tasks in our evaluation.\n\n1. **Standard Test Bed**: \nThese tasks have become the de facto standard for assessing length generalization in related literature [1,2,3,4]. and although they may seem simple, they require compositionality skills to solve, fundamental for more complex tasks.\n2. **Control over Problem Length**: The synthetic nature of the chosen tasks enables full control over the data generation process. It permits a train/test split designed to measure length generalization exclusively, with task difficulty tied to problem length.\n3. **Challenges with Naturally Collected Tasks**: While tasks like summarization might appear more ideal, creating a train/test split measuring length generalization is highly non-trivial for such naturally collected/crowdsourced tasks. Notably, sample length and sample difficulty are not necessarily correlated.  One might be tempted to create splits using sample length, however, since we don’t have control over the data generating distribution, longer samples may not be necessarily more challenging to solve. For example, it is unclear if testing with longer documents or summaries would reflect increased difficulty. Longer documents might not be more difficult (e.g. source document mostly contains irrelevant content), and longer summaries may not entail harder examples (e.g source document is so small that creating a summary only requires a mere copy-paste from the input).\n4. **Alignment with Prior Work**: Considering these factors, we followed existing practices, evaluating on a similar set of tasks and including a diverse range (10 in our work) to offer a comprehensive view of the results.\n\nIn conclusion, our task selection was grounded in established methodologies for assessing length generalization. We believe this approach provided a robust examination of the subject, though we appreciate any suggestion or elaboration on our choice of tasks.\n\n\n> Task-specific performance metrics\n\nWe appreciate the reviewer’s comment. To address this concern, we would like to clarify and politely remind the Reviewer that our evaluation **does indeed include task-specific metrics**, particularly exact-match accuracy, which are reported not only per each task but also for each length bucket in both the main paper and the appendix section. \n\nParticularly, Fig. 3 in the main paper illustrates six task-specific evaluations, encompassing both in-distribution (IID) and out-of-distribution (OOD) scenarios. Additionally, Figs. E.2, E.3, and E.4 in the appendix provide detailed evaluations for each specific task. The evaluation result for all mathematical tasks, complete with eight different scratchpad format configurations, are thoroughly documented in Figs. E.7 to E.13.\n\nAdditionally, the motivation for mean rank is to offer a more holistic perspective. Utilizing mean rank is a standard practice [5] in situations where the evaluation spans multiple diverse tasks in which the mean rank and task-specific results are reported simultaneously. We directly follow this practice as it provides a more comprehensive view.\n\nWe hope this clarification reassures you of the rigor and depth of our evaluation (as acknowledged by Reviewer rWd9). If any part still appears ambiguous or incomplete, we are open to further elaboration to enhance the clarity of our work.\n\n> Finetuning approach for removing PE\n\nWe are glad our thought processes match. At the preliminary stage of our research, we did indeed consider removing positional encoding in pretrained models and subsequently fine-tuning them on downstream tasks. This consideration, however, was tempered by existing findings in the literature. Specifically, prior work by Sinha et al. [6] has demonstrated that positional encoding instills such a bias during pretraining that proves challenging to mitigate, even with further finetuning. In light of these observations, we made the deliberate choice to forgo fine-tuning to avoid introducing a potential confounder into our study. Nevertheless, we recognize the intriguing nature of this question and fully endorse its exploration as an important avenue for future research.\n\n\n> Selection of the model size and transferability to larger models\n\nWe appreciate the question about the size of our models. Without LLMs trained with different PEs under uniform conditions, assessing the effect of PEs on length in pretrained or bigger models is tough. As a result, we had to train decoder-only Transformer models from scratch, constrained by our computational limits. The model size chosen aligns with recent research on length generalization [1,2].\n\nNonetheless, despite our limited budget, we've begun addressing concerns by including initial scaling and language model pretraining results in the rebuttal period (see General Response). These insights show patterns aligned with our findings, suggesting our conclusions may apply at larger scales. We're gathering resources to conduct pretraining at a 1B-parameter level, albeit limited.\n\nWe express our gratitude once more to the reviewer for their valuable time and insights. We hope that our detailed explanations have resolved any remaining questions. Would you consider increasing your scores given the points of clarification that we have provided above?\n- [1] Delétang et al, https://arxiv.org/abs/2207.02098, ICLR 2023\n- [2] Ruoss et al,https://aclanthology.org/2023.acl-short.161.pdf, ACL 2023\n- [3] Anil et al, https://arxiv.org/abs/2207.04901, NeurIPS 2022\n- [4] Ontañón et al, https://arxiv.org/abs/2108.04378, ACL 2022\n- [5] Liang et al, https://arxiv.org/abs/2211.09110, 2022.\n- [6] Sinha et al, ​​https://arxiv.org/abs/2210.12574, EMNLP 2022 Findings\n"}]

Author rebuttal:
## General Response
We thank the reviewers for their positive feedback and constructive criticism.

We are glad that Reviewers 1 (VbRS) and 3 (rWd9) found our paper to be **“well-written and easy to follow,”** and that they believe it provides a “thorough and in-depth analysis,” as highlighted by Reviewer 4 (C4oP).

We are further pleased that Reviewer 2 (qZrr) acknowledges the **mathematical rigor** in our work, and Reviewer 3 (rWd9) recognizes our experimental rigor, especially noting that our evaluation methodology is “**more aligned with practice** than prior works that have explored this direction.”

Reviewer 2 (qZrr) kindly underscored the **originality** of our formal proofs and insights such as the "learned attention patterns of NoPE" and its working mechanism, also noted by Reviewer 4 (C4oP). We further appreciate Reviewers 3 (rWd9), 2 (qZrr), and 4 (C4oP) recognizing our interesting and surprising results, strengthening our confidence in the innovative nature of our findings.

Finally, we are glad Reviewers 1 (VbrS) and 3 (rWd9) considered our work **"a significant contribution"** and "a step forward in understanding Transformers with causal masking", reflecting our aim to address this important aspect. Moreover, we appreciate Reviewers 2 (qZrr) and 4 (C4oP) recognizing our impact on development of positional encoding and more simplified Transformer architectures.

We now clarify the main shared concern among the reviewers below and address reviewer specific questions in the individual responses.

### Language Modeling and Larger Models
During the limited time of the rebuttal, we performed preliminary **pretraining** experiments on **larger scale** models. Specifically, we trained a 300M decoder-only Transformer with NoPE and ALiBi on Wikitext103 with training context size of *512* (following Press et al [1]).

We observe almost identical perplexity for both NoPE and ALiBi on the test set with context sizes of 128 to 630. From context sizes of 630 to 1120, we see that NoPE's perplexity diverges but ALiBi's perplexity stays the same. However, when we take these exact checkpoints (that are pretrained on Wikitext103) and finetune them on downstream tasks, we observe NoPE still outperforms ALiBi (Figure 1 in the uploaded PDF), which is consistent with results reported in the original draft. 

**Language Modeling Perplexity vs. Downstream Performance**

As we argue in the manuscript, we believe that language modeling perplexity is not well suited for evaluating length generalization since the downstream task performance is what we really care about in practice: precisely the focus of our evaluation.There are various observations in the literature showing that perplexity is not correlated [2,3] and sometimes is anti-correlated [4] with downstream task performance.

More importantly, Chi el al. [5] recently showed that ALiBi can be emulated using window attention. That is, NoPE+windowed attention mask (where every token attends only to those within $w$ tokens of itself, and $w$ is the window size $\lt$ context size) can achieve length generalization in term language modeling perplexity similar to ALiBi [5]. Furthermore, Chi el al. [5] demonstrate that large slope magnitude in ALiBi formulation is needed for length generalization as large slopes inherently create a narrow window attention mask such that far away tokens are ignored.

These results suggest that Recency bias incorporated in ALiBi's design (as suggested by Reviewer 2 (qZrr)) might create an unrealistic impression of how well it generalizes over length in natural language modeling. Especially, as the prediction of the next token may only need a brief summary of the past context and natural language inherently contains local dependencies due cognitive constraints [6, 7]. On the other hand, for complex reasoning tasks that require long term dependencies, the Recency Bias of ALiBi can hinder the model, while positional encoding such as NoPE can freely attend to them (Fig. 7 in the main draft). The limitation of Recency Bias in ALiBi can be observed in the Reverse and Copy tasks (Fig. 3 in the main draft) where long range dependencies are needed.

We understand that these details may not have been sufficiently discussed in the original draft but we hope these explanations fully address the questions by reviewers. We make sure to have a more comprehensive discussion of LM vs. Downstream in the updated manuscript.

Nevertheless, we are preparing our resources (to the best of our ability) to train larger scale (1B) models with NoPE and ALiBi to fully reflect the effect of pretraining. We will update the camera-ready with the new results.

- [1] Press et al, Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation, ICLR 2022
- [2] Tay et al. Scale Efficiently: Insights from Pretraining and Finetuning Transformers, ICLR 2022
- [3] Liu et al. Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Models, 2022
- [4] Zhou et al. LIMA: Less Is More for Alignment, 2023
- [5] Chi et al. Dissecting Transformer Length Extrapolation via The Lens of Receptive Field Analysis, ACL 2023
- [6] Gibson et al, Linguistic complexity: locality of syntactic dependencies, 1998
- [7] Gibson et al, How efficiency shapes human language, 2019


Meta-review: The paper examines the extrapolation behavior of transformers without positional embeddings, showing strong results on several algorithmic tasks.

Reviewers appreciated the well motivated experiments, interesting empirical results, and theoretical justification. There is also interesting analysis, such as the comparison with T5 positional embeddings.

There are some concerns about overclaiming. The title/abstract should do a better job of discussing the scope of tasks they experiment with (for example, some reviewers were disappointed by the lack of natural language tasks such as summarization). Some reviewers were also left with the impression that NoPE is novel, so the paper needs to acknowledge related work more clearly. While the paper doesn't say anything false here, I think the presentation is somewhat misleading.

The paper would also benefit from discussing behavior on pre-training tasks. The author response mentions an interesting experiment showing that NoPE *doesn't* extrapolate well for language modeling - including this result, and discussing the reasons for different conclusions to algorithmic tasks, would be very interesting (at least to me).

Overall the paper is borderline, but leaning accept.
Decision: Accept (poster)