Mesa-Extrapolation: A Weave Position Encoding Method for Enhanced Extrapolation in LLMs
Authors: Xin Ma
Yang Liu
Jingjing Liu
Xiaoxu Ma
Venue: NeurIPS 2024 poster (2024)
Keywords: Large language models
extrapolation
position encoding
transformers
self-attention
Primary area: generative_models

Abstract: Large language models (LLMs), although having revolutionized many fields, still suffer from the challenging extrapolation problem, where the inference ability of LLMs sharply declines beyond their max training lengths. In this work, we conduct a theoretical analysis to better understand why No Position Encoding (NoPE) fails outside its effective range, as well as examining the power of Position Encoding (PE) in this context. Our findings reveal that with meticulous weave position, PE can indeed be extended beyond effective range. Our theorems establish that LLMs equipped with weave PE can achieve improved extrapolation performance without additional cost. Furthermore, we introduce a novel weave PE method, Mesa-Extrapolation, which utilizes a chunk-based triangular attention matrix and applies Stair PE to manage the final chunk. This method not only retains competitive performance but also offers substantial benefits such as significantly reduced memory demand and faster inference speed. Extensive experiments validate the effectiveness of Mesa-Extrapolation, demonstrating its potential as a scalable solution to enhancing LLMs’ applicative reach.

Mesa-Extrapolation: A Weave Position Encoding Method for Enhanced Extrapolation in LLMs
Xin Ma', Yang
Liu', Xiaoxu Ma
Diiital Research Institute, Enn Group, Beijing, China Institute for AI Industry Research, Tsinghua University, Beijing, China *Shanghai Artificial Intelligence Laboratory, China (xin. ma000, xiaoxuma)@gmail. com, (liuy03, jjliu]@air. tsinghua. edu.
Abstract
Large language models (LLMs), although having revolutionized many fields, still suffer from the challenging extrapolation problem, where the inference ability of LLMs sharply declines beyond their max training lengths. In this work, we conduct theoretical analysis better understand why No Position Encoding (NoPE) fails outside its effective range, as well as examining the power of Position Encoding (PE) in this context. Our findings reveal that with meticulous weave position, PE can indeed be extended beyond effective range. Our theorems establish that LLMs equipped with weave PE can achieve improved extrapolation performance without additional cost. Furthermore, we introduce novel weave PE method, Mesa- Extrapolation, which utilizes chunk-baser triangular attention matrix and applies Stair PE to manage the final chunk. This method not only retains competitive performance but also offers substantial benefits such as significantly reduced memory demand and faster inference speed. Extensive experiments validate the effectiveness Mesa-Exxtraoolaionn, demonstrating its potential as a scalable solution to enhancing LLMs applicative reach. Our code is available at https: //github. com/ soacker /Mesccaerreeeaaaaa Extrraolattttaataaatoooooooaooot
Introduction
Large Language Models (LLMs) with their powerful in-context learning capabilities Brown et al. (2020) offer versatile solutions to a wide-range of intelligent applications. However, one pressing challenge, the extrapolation problem Delétang et al. (2022) Zhang et al. (2022). dictates that the inference ability of LLMs sharply declines beyond their max training lengths, imposing serious limitation applications with long inputs. An naive solution is extend the length of training samples. However, the inherent quadratic complexity of calculations presents practical challenges, demanding more resources, longer training time and higher cost.
Positional encoding (PE) has become a pivotal component Transformer architecture, to compensate for the overlooking of position information by the attention mechanism. In the realm of extrapolation capability, PE is considered as key factor influencing the extrapolating ability of L.MMs. few PE approaches, such as the popular RoPE,Su et al. (2023) and ALiBi Press et al.) (202T). claim to offer improved extrapolation capabilities and have gained widespread usage in industrial applications. Mcanwhile, a counter-narratiin has emerged. Some works demonstrate that Transformer can achieve better extrapolation capabilities by removing position encoding (NoPE) Kazemnejad et al. (2023). and contend that the mask already plays significant role in capturing position information.
Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Inspired by Kazemnejad et al. (2023), we conduct thorough investigation of the extrapolation problem by designing a specific Transformer model for this purpose and presenting detailed theoretical analysis. To the best of our knowledge, this is the first theoretical endeavor to understand the inner workings of extrapolation. We first elucidate the cause of NoPE's failure when input exceeds the effective window length in Theorem 3.1] and analyse PE's failure in 3.2 Building upon Theorem 3.2 we prove in Theorem 3.3 that through meticulous weave position, (i.c., weave PE), it is feasible to achieve extrapolation beyond the effective window length.
Kay Vectors
denotio suil dller ton score cursrnt toven
1-th
soif fron
current
cencotss accuunk 1-th denatre the firs, and nith denotes the Lust Except the and the chuniss, other chuatics
num maaked
wooee cenahee máne
k
B
posittora
cecaptin
On-f-th-qhur
Ar
Axi
Ax
R:
6
relative postions n-th
Figure I: Chunk-base triangular attention matrix, PE and Stair PE. The left figure shows the Chunk-based triangular attention matrix (before SoftMax operation) of Mesa- Extrapolation when an exemplar sequence of length 13 fod into a LLM. The right figure shows an example of PE and Stair PE. The Stair PE is used to weave the relative position in Mesa-Extrapollatio.
We further introduce novel weave-PE- PE-based method, Mesa-Exie Extrappxttaalotiion which demonstrates substantial extrapolation prowess without the need for additional training. Specifically, we use chunk-based triangular attention matrix, aiming memory Ilfft,, and we employ Stair PE to handle the last chunk (Figure right below), effectively making Mesa-E Dessa-Exrrapoatioon completely free plug-in for LLMs.
resource consumption (Figure
Our contributions are summarized as follows:
1. Theoretical Analysis We provide comprehensive theoretical analysis the challenges encountered by NoPE beyond its effective window length, and investigate the effect of PE in this context. Our theorems prove that through meticulous weave position, PE can be effectively extrapolated beyond the effective window length. This theoretical foundation establishes clear understanding of the extrapolation problem and potential solutions for LLMs utilizing PE.
2. Introduction of Extrrppplatatonii We introduce a novel extrapolation approach called "Mesa-Est Extssa-Extrpootaiinn Based triangular attention matrix, this method strategically orga- nizes input tokens into chunks, with the final chunk employing a weave PE method (c.g.. Stair PE) to integrate all token states. Mesa-Extrapo Extrapoloooo provides practical and effective solution to the extrapolation problem.
3. Empirical Validation Comprehensive experiments demonstrate that our approach achieves competitive performance, offering the benefits of extremely low memory usage and the fastest inference speed compared to existing methods. Importantly, it an easy plug- in and can enhance extrapolation performance of LLMs without any additional resource consumption.
Background
Since the self-attention mechanism itself does not contain position information, PE components have become an integral part of the Transformer architecture. Cmmon choices for PE are either absolute, where each absolute position (e.g., 1, 3,..) directly represented, or relative, where the distance between tokens is used positional information. Absolute Position Embedding (APE) embeds

---

each absolute position i into position vector P; and adds word embeddings to their corresponding Pt. before feeding them to the LLMs Vaswani al. (2017). However, the extrapolation ability is limited because it cannot generalize to unseen positions. RoPF et al. 2023) rotates the query and key vectors with an angle proportional their absolute positions, so the attention dot production only depends relative distance between tokens, providing a relative positional encoding. T5's Relative Bias first maps the relative distance (i - j) between tokens at positions and to a scalar bias value 6 = f(i j), where f is a lookup table. ALiBi is similar to T5's Relative Bias but instead subtracts a scalar bias from the attention score Press et al. (2021 [ (refer to Appendix D.2 for more details). Recent works such ReRoPE and Leaky-ReRoPE Su (2023b) achieve effective extrapolation without fine-tune fine-tuning by meticulously weaving relative positions RoPE. We refer to this class of methods that achieve extrapolation by weaving the relative positions of PE without fine-tuning as Weave PE.
Kazemnejad et al. (2023) indicates that the decoder-only transformer with position encoding removed (NoPE) demonstrates stronger extrapolation capabilities. Furthermore, theoretically shows that specific transformer model can get relative and absolute positional information, even in the absence of Haviv et al. (2022) also demonstrates NoPE achieves comparative performance to standard Transformer models. These new studies pose key challenge regarding the choice of whether using PE or not in Transformer architecture (refer to Appendix A for more related works).
Model Extrapolation: NoPE vs. Weave PE
3.1 Problem Definition
We mainly consider relative PE methods and formally define their self-attention dot product as function fPg. which takes the query q: located position t, the key k2 located on position i, and their relative positions - as input parameters, as follows:
(g. k:) frelg,, k,, i),
(1)
where fPE denotes relative PE method such as RoPE or ALiBi. For ALiBi,
(gr, ks)) == SALiBI k; i) q:¹ k; (t (t- ()) -m+1
where m is head index and C 2-2 2- logg Porgg (phnad++3)) For NoPE,
(qt, kt) == qe k,
Based on Equ Te formally define weave PE as follows:
(g kv) == fweavaPE(q k., 1 i) fpE(q), k., W(t 1)),
(2)
where W a weave function which takes the relative position i as input parameter.
For example, ReRoPE Su 2023b) can he considered as an example of weave PE, with its W function defined as follows:
t-i N t-i> N
W(t - 1)
where N is constant. ReRoPE's dot-product attention is:
(g., k.) fReRoPE(q. k,, i) fROPE(q. k, W(t i)) q. W( k.
where a rotation matrix that rotates W(t - i)0 radians. This is based on RoPE's dot-product attention:
(gt, k.) = fROPE(q: k 1)) q.d ((t k)0
3.2 Motivation
Chen et al. 2023) explores the evolution of hidden state values and reveals noticable phenomenon: as the position increases, the hidden state values will explode. This finding appears consistent with observed failures in extrapolation. Through probe experiments (refer to Appendix F), we investigate
3

---

the alterations in hidden state values across various positions and layers. Results show significant shift the hidden state's value range upon surpassing the effective window. Interestingly, when employing extrapolation techniques, hidden state values exhibit noticeable suppression. This indicates that the effective range of hidden state values likely lies within a specific threshold. When the position exceeds the effective window length, the hidden state values surpass this threshold, resulting in extrapolation failures.
Previous work Kazemnejad et al. 2023) utilizes a constructive approach. By constructing the Transformer's weights, it enables the first and second layers independently generate position information. Drawing inspiration from this, we endeavor to construct Transformer model capable of mirroring this observation.
3.3 Theoretical Analysis
In a multi-layer neural network, each layer's outputs, a.k.a hidden state values o, become the inputs for the subsequent layer. To maintain stable network behavior, these values must remain within reasonable range. We define this observable boundary as the threshold H. This threshold can be either upper bound lower bound. For our analysis, we focus the lower bound of this threshold. A successful extrapolation occurs when a large model consistently generates accurate next tokens for long input sequence. Conversely, a failed extrapolation happens when the model produces incorrect or nonsensical next tokens. Based on these definitions, we make the following assumptions:
Assumptions. In LLM, there lower bound as threshold for the hidden state value o specific dimension and specific layer. Let M be the max window length for LLM. Predefine query Wo. key WK. value Wr and output Wo matrices, and ferd-forward sub-layer WI, W2 matrices. When > fails.
H. LLM extrapolates successfully. Once < H. LLM extrapolation
These assumptions indicate that by observing whether the hidden state value in this dimension exceed the threshold H. we can predict whether the large model's ' extrapolation has failed. Building upon these assumptions, theoretical results for NoPE exceeding the effective window length are as follows:
Theorem 3.1 (NoPE Extrapolation). Let x = {< bos 21 .T] be an imput sequence of length T + 1 to the model. Then, there exists WQ. WK. Wv, Wo. Wi, and W2 matrices. such that when T < M, or > H; and when > M, OT < H.
Full proof is given in Appendix E. This theorem reveals the internal mechanism of NoPE extrapola- tion the input length changes. The theoretical results for PE
follows:
Theorem 3.2 (PE Extrapolation). Let x = II bos >, .1....,, ITl be an input sequence of length T+1 to the model. Consider simple relative PE schema where dot product between query qs and key k; at positions t and (t 2 i) can be expressed as: (q,, k,) == q: k; (t i). Then, there exists WQ. W Wv, Wo. WT. and W₂ matrices, such that when T M, or > H.; and when T > M, or H.
Full proof is given in Appendix E.2 Theorems 3.1 and 3.2 state the failure of length extrapolation in NoPE and PE, respectively.
Building on Theorem 3.2 we further investigate the case for carefully orchestrated weave PE, The theoretical result is as follows:
Theorem 3.3 (Weave PE Extrapolation). Let N be a positive constant. Consider a simple
weave PE extrapolation schema: when - << N, Wit -i) = i; and when t - i N,
W(t - i) N. Then, the attention dot product is fixed as below:
(qt, ks) = {
q. k. qi k.
t-i<N
t-i2N
where N & M. Then, applying Wo K. Wv. Wo. Wi, and W9 matrices from Theorem we have when T > M. OT > H.
3.2

---

Full proof is given in Appendix E.3 This theorem suggests that for existing LLMs relying on PE, simply weaving its relative positional encoding can effectively extend the input window.
Through Theorem 3.1 and Theorem 3.2 we formulate pertinent theoretical models for NoPE and PE, respectively, shedding light the intricate relationship between extrapolation and the effective window length. Building upon these findings, Theorem 3.3 delves deeper into the realm of explicit PE, revealing that a well-designed weave PE scheme can effectively broaden the original effective window length. The theorems show the existence of an effective length M, which is typically related the maximum training window length of the LLM. Furthermore, within the proof of Theorem 3.3 our results indicate that N < M, consistent to experimental findings in Su (2023b). where although the extrapolation position can theoretically start from 2048, the best extrapolation starting position 512. More experimental parameters also validate this setting (refer to Appendix B.2).
3.4 Validating Extrapolation Using Observed Thresholds
Further, we design probe experiments (refer Appendix F33 for more results) to validate the observed phenomena and our theorems, as shown in Figure 2 From Figure 2 two observations are noted: Firstly, for hidden state values of the same dimension, the first layer undergoes minimal change. while the second layer exhibits a more pronounced transition. Exceeding the threshold implies extrapolation failure. This observation aligns with our theoretical model construction, where the first layer primarily refines positional information, with sigmificant signal changes occurring in the second layer, as demonstrated in Theorem 3.2 Secondly, based on observational thresholds, when the length of the input sequence is around 12k, the values of hidden state corresponding to Dynamic-NTH
Liu et al. (2023) surpass the threshold, implying extrapolation failure. Conversely, for ReRoPE Su (2023b), extrapolation succeeds. These two predictive outcomes corroborate with subsequent experimental results.
Layen1, Dimension:1
Layen2, Dimension:1
Layen:1, Dimension.6
Layen2, Dimenston.6
0.3
0.0
-.01-
-0.2
-0.3
-0.0
14k
Origie
DymemicoNNT
Ros Toon
Figure 2: Thresholds for hidden states observed specific dimensions on LLaMA2-7B- -B-Chtt, allowing for extrapolative judgments based on these thresholds. The vertical black dashed line indicate the position of maximum training length of the model. In this case, it is 4k for LLLMA2-7B--hhe model. The hidden state value this position is designated as the observed threshold and marked with horizontal red dashed line. When the hidden state value exceeds the red dashed line the position changes, signifies that the hidden value has surpassed the threshold, suggesting a failure extrapolation after that position.
4 Mesa-Extrapolatton
In this section, we begin by introducing a novel weave position encoding method, termed Stair Position Encoding (Stair PE). Following this, propose chunk-based triangular attention matrix. Building on these concepts, we introduce the implementation of Dessa-xxrapplttiin. Lastly, we discuss the theoretical properties of these innovations.
4.1 Stair PE
Following the concept of weave PE in Equ 2 we define a novel weave PE method, namely Stair PE follows:
{
i-isN
(ge, ki) == fsteirPE(qt, ki, 1- frela, Ks W(t - +)), and W(t - -)
1-15
(3)
5

---

where I= N + - N denotes the extrapolated position, and E denotes the extrapolated width. Both N and E are positive constants. Stair PE can be applied to existing relative PEs such as RoPE and ALiBi. For example, for RoPE:
(g, k.) == Ro Qt, k,, i) FROPE ks W(t (V(t-i) - qi (2
Taken a sequence of length 10 an example, the right subplot of Figure [ shows that the relative positions generated by PE (Both RoPE and ALiBi) are linear, while those generated by Stair PE (here N = 4 and E 2) are non-linear. Since weave PE changes the linear relative position, has to calculate the attention matrix more than once Su (2023b). Compared with ReRoPE (detailed on Appendix B.3). Stair PE provides finer-grained extrapolated positions. Meanwhile, compared with Leaky-ReRoPE, Stair PE reuses known positions, reducing possible generalization errors. We also provide an ablation experiment to compare these weave PE methods (refer to Appendix (.6).
While our work was conducted independently, we note that et al. (024) have recently explored a similar idea through flooring the original positions and obtaining the relative position matrix with grouped self-attention. Although the two parallel thought processes are different, under certain conditions their formulations are equivalent (refer Appendix G Consequently, Self-Extend be categorized as a Weave PE method. Our proposed Chunk-basee Triangular Attention Matrix (detailed in Section 4.2) and its corresponding theoretical properties (Section 4.4) are also applicable this parallel approach.
4.2 Chunk-based Triangular Attention Matrix
We design a chunk-based triangular attention matrix as shown in the left subplot of Figure T To achieve approximate linear memory consumption and computational speed, we further split the triangular attention matrix into several chunks and concatenate these chunks. We segment the input sequence into several sub-sequences according to DynamicSplit function (defined in Appendix 2 which divides sequence into sub-sequences of equal length, with the exception of the first and last sequences. The length of each sub-sequence is determined by both the input token length and the max training length. Each of the generated sub-sequences then undergoes self-attention operation to generate a corresponding chunk. That is, a sub-sequence of length will generate a corresponding chunk with the size 1 x l.
4.3 Implementation
Mesa Desa--xxrapolationn mainly utilizes the chunk- based triangular attention matrix and Stair PE.
Algorithm 1 Mesa--xtraaplattion Algorithm
Notice that regular PE (such as RoPE or ALiBi) is applied to all chunks except for the last chunk, for which Stair PE applied. For the last chunk, all previous chunks concatenated, and Stair PE is used to rearrange relative positional encod- ing to achieve extrapolation beyond the effective window length.
Require: DynamicSplit, LLM, StairPE
Input: s(0: (input tokens with length T) Output: s(T, 1,...
# Prefill Stage
1: first length, chankk bhinkkwwithh width +- DynamicSplitss)
2: K cache, V V_eache + 0.0
first_K Kirst LLLMMs(0 first_lengte
4: Append first_K to K_aache, first_V to
In summary, the process of Mesa- Extrapolation mainly contains four steps (Algorithm [I: The first three steps correspond to the prefill stage, which is used to calculate all input tokens. The last step corresponds to the decoding stage, which is used to generate next-token one by one.
V eache
5: i <- first length
while i < T T 11 chank width do K, V + LLM(s|ii : i chunkkwwithhe first_
first 8:
K __cce append K, V __cache append V
9: i i+ chunk_widdhh
10: end while
Firstly, DynamicSplit function segments the input sequence, and the first segmented sub- sequence is fed into LLM to generate the first attention matrix chunk (line 3 in Algo. Sec- ondly, subsequential sequences are iteratively processed while sinultaneously feeding the key and value pairs of the first chunk into LLM to generate subsequent chunks (line 6-10 in Algo. I). Thirdly, the last sub-sequence is processed by concatenating the key and value pairs of all previous chunks together and using Stair PE to modify the relative positional encoding. Then, it is fed into
1l: apply Stair PF fix positions
12: K, V t- LLM(s T' 1], _cache, V V_aache)
# Decoding Stage
13: apply StairPE fix positions
14: generate next-token by one

---

the LLM to produce the last chunk (line 11-12 in Algo.1). Finally, Stair PE is applied to process the current token and cached Key and Value pairs to generate next-token one by one (line 13-14 in 1) We establish the effectiveness of our proposed Mesa-Extrrapolation in the next section.
4.4 Theoretical Properties
Theorem 3.2 establishes a theoretical measurement for evaluating the effectiveness of extrapolation. We consistently apply this indicator, along with adjustments in relative positioning using Stair PE, to validate the feasibility of extrapolation. The result is as below:
Corollary 4.1 (Mesa Extrapolation). Let N be positive constant. Consider simple Stair PE extrapolation schema, and the attention dot product is fixed as:
q: k. i)- 1-i<N 1-i2N
(q k.) = fatauPe(qi k., k2,t-
k.
where N M, I I= N [ and the extrapolated width E. is constant. Then, Apply
Wº. WK. Wv, Wo. W1, and W2 matrices from Theorem 3.2 Although T > M, it still OT H.
Full proof is provided in Appendix E.4 outside the max window length.
We prove that Mesa-Extrapolation can effectively extrapolate
5
Experiments
In this section, validate the performance of Mesa- Eetesa--xtappottionn through experiments measured over multiple metrics. We choose GovReport Huang et al. (202T). Pile Cao et al. (2020), LongBench
Bai et al. 2023), and LongEval Krishna et (2023) datasets, and also generate passkey dataset, which has been integrated in the code warehouse. More experimental details and results are referred
to Appendix and C
Since our method is completely free plug-in and does not require fine-tuning, we choose methods of this type for comparison, including: model self (Origin). ReRoPE Su (2023)), Leaky-ReRoPE) Su (2023b), Dynamic-NTKI Liu et al. (2033) LM-IIninite Han et al. 2023 y and Streaming-LLLM Xiao al. (2023).
We evaluate Mesa-EExtraollane using three prominent LLM families: LLaMA Touvron et 2023a) Touvron et al. (2023b) (including LLaMA-3B Lopen-LLaMA-33- LLaMA2-7BB Chat, and Vicuna- 13B.VI.3), Tem (2023) (including MPT-7B), and PyThia (Biderman al. 2023) (including PyThia-6.98 and Py PyThia- 12B). Notably, LLaMA and Py Thia incorporate RoPE Su et al. (2023).
whereas MPT employs ALiBi Press al. 2022 two of the most influential PE techniques in recent research. Furthermore, we validated our approach using the Biii---ini-128k-insse model
Microsoft (2024) (refer to Appendix C.9).
We also conduct ablation experiments (refer to Appendix C.6). We use a 2xA800 80GB NVIDIA GPU server the experimental environment and adopt the Py ToTch framework.
5.1 Evaluation on Passkey Retrieval Tasks
We assess the accuracy of Mesa- Extrappoltloon using the generated passkey dataset. This dataset comprises samples of varying lengths, each storing a random password at random position. The sample length initiates at 1024 and increments by 1024. Simultancously. 100 samples randomly generated for each length. The proportion of correct answers found by LLMs is calculated for each input length.
siows the results of 6 LLMs on passkey retrieval task. The LLaMA families can employ various methods, including Origin. ReRoPE, Leaky-ReRoPP Dynamic-NTK, LM-Infiiite Streaming- LLM, and our Extrapotttoo.... Note that these methods are model-specific and may not be universally applicable across all model series. For the MPT model, Origin, Streaming-LL.M, ReRoPE, and Mesa-Extras Desa--xtrapolation can be utilized. Similarly, for the PyThia model, Origin, Streaming- and Mesa-Extn Extrapolation can be applicd.
7

---

LLaKA-33
LLaMAZ-78
8-138
02
0.0
Accuracy
24
3k
8K
11s
14k
17k
Z0K 23k 26x 25k
2k 5K Bk.
1Ik
14k
17%
20k
23k
26k
29K
25
5K
8k
11K
14k
NPT 70
PyThil 6.98
PyTha 120
0.4
0.4
0.2
2K
23K 29k
3k 6k
Origin
Leaky-ReltoPE
Dynamic--TK
Streaming-LLM
Mese-Extrapslatton
Kaeen Lenggh
Figure 3: Passkey Retricval Accuracy for different methods on various LLMs. X-axis represents the input token length, and Y-axis represents the accuracy of password found by LLMs. Different color regions denote the variance value, averaged on 100 samples for each input token length. The black dashed line represent the max training length for LLMs. Some observations: Weave PE-based methods, including ReRoPE, Leaky-ReRoPP ReRoPE, Mesa-MMtraapeeeeeee Alesa-Extrapolatiion consistently demonstrate stable extrapolation capabilities even when the input length surpasses the maximum training length. We claim that "early stopping" phenomenon certain methods is attributed to GPU memory exhaustion under our existing hardware resources.
Analyzing the LLaMA model series reveals that weave PE-based methods, including ReRoPE, Leaky- ReRoPE and desa--xtrapolatiin achieve superior extrapolation capabilities. Additionally, under our existing hardware constraints, Mesa- Extrapolation demonstrates longer extrapolation capabilities.
In the case of MPT model, after surpassing the maximum training length, the extrapolation capabilities of Mesa--xxtapoolation and ReRoPR show decline. We speculate that this may be attributed to approximate ALiBi PE applied on MPT model. This approximate ALiBi would lead to significant disruptions when weaving positions. (refer Appendix C.2 for more details about MPT).
In the PyThia models, an additional observation is that 100% accuracy still not achieved within the training length. We attribute this to the PyTTha model being a pre-trained model without instruction aligmment, resulting in a weakened intrinsic understanding of the task. Results with enhanced prompts referred Appendix C.5
Dynamic-NTK exhibits partial extrapolation capabilities beyond the maximum training length. Streaming-ILLM and IM-Infinite also exhibit poor performance. This is because these methods discard portions of the input token, leading to potential information loss and incorrect answers.
LLaMA.38
LLaMA2-78
Vicura-138
15.0
17.5
10.0
7.5
5.0
2k
5c
8x
11k
14k
2k
5k
8k
11k
14k
2k
Sit
8k
11k
1/k
ReRoPE
Leaicy-
Dynemic
LM W-innniite
Streaming:
Meser Extrapoiietoo
Token Length
Figure 4: Perplexity (PPL.) metrics LLaMA models using the Pile dataset. Some observations: (1) The PPL value of Origin consistently increases when the maximum training length is exceeded. (2) Other methods maintain low PPL values, with Dynamic-NTK exhibiting a slight increase as the input length grows.
5.2 Evaluation on Language Modeling
We further assess the fluency of Desaa-Exrrpolatioo utilizing the perplexity metric. Results evaluated on the Pile dataset are presented in Fig X-axis represents the length of the input token, while the

---

Y-axis corresponds to NLL (Negative Likellioo))))) values. It can be observed that the NLL value of Origin consistently increases when the maximum training length is exceeded. Other methods maintain low NLL values. LM-Infinite performs marginally better on Vicuna-13B: Dynamic-NTK method exhibits slightly weaker performance after 1 11k, and the performance continues drop as the input length increases. In summary, our Mesa--xxtraoolation demonstrates comparable performance to other methods on PPL metric.
5.3 Evaluation on Summary of Tasks
We conduct a summary task using the GovReport dataset and employ ROUGE ROUGE (2004) 1/2/))-1/2/L) as evaluation metrics. ROUGE assess overlapping N-grams by comparing the generated text with reference answers.
For the GovReport dataset, we segment the range from 3* 3*1024 to 11*1024 based sample length, with each interval of 1024 units. A test set created by randomly selecting 8 samples from each interval. We choose LLaMA2-7B- -aChha the evaluated LLM. The experimental results for ROUGE is presented in Tables below:
Table ROUGE metric on LLaMA2-78 Aa-Aah, averaged on 8 samples within each interval using the GovReport dataset. Each cell contains ROUGE- ROUGE-I/ROGE-22 /TT.///OOOUGGGGGAAAAAA The best values are marked in bold. Some observations: (1) Dynamic-NTK shows slightly better performance within 11k. (2) Other methods showcase the ability achieve scores of varying degrees.
Enjut Lengis
36
4
5%
6K
TOK
TIK
DRigi
168847/333
DISTI
ReRaPE
0
35.7/1883333
30.3/9 328.5
30.2111
L6/66.7
36.1226644
31. 1.
35.7113.333.0
346/13.052.5 35.7112,43255
Leaky Leity-Retto::: Restort:
16.314.37335
35 23.776--3 4 4/22.7
25. 47.477422 4/216
S6. KCRUS
30.800 7737
DTT
38.2033.026.11
30.31.606660
35.9/18.4/55
4/5./
32.800.2330.5
36.155334
35 35.211311
39.314.966633
35.4/15.032.77 32.7112.875955
LM-lettiie
14.0111 8
35.2115 1/326
31.5013.6907
31 W716
20.0% 4714
22 37.999 1735.6
719 489.6/55
Smraming-11MM L.M
38.208.7/06.2
8:V1 5776
01000000
Mesa Exiropotution
35.014663344
4137220.437.5
38.77441134.1
33.01283LA
34.0118116
30.711.
33.911423044
20.20101/26.6
In [ we record the average scores of 1 Rouge-2, and Rouge-L. within each interval. It is evident that once the effective input window is exceeded, the performance of Origin and Streaming- LLM declines rapidly, rendering useless. For LM-Infinite, the scores exhibit a slight decrease as the length increases. Dynamic-NTK shows slightly better performance within 11k. However, combined with the Fluency experiment on Fig 4 it seems that the effective extrapolation range of Dynamic-NTK cannot exceed 12k, which is consistent with the threshold observed in Fig Weave PE-based methods, including ReRoPE, Leaky-ReRoll ReRoPE and Mesa- Mesa-Extrapolatin shows slight variability
maintain similar
generation quality as the length increases. Note our Mesa-Extrapolle in performance within mid-length (8k-11k) in the summary task. We speculate that with a fixed extrapolation width param (E- 50), the 7k-11k range may spread the model's 's attention more thinly compared to the 4k-6k range. We hypothesize that optimizing the extrapolation width could alleviate or improve performance in the 7k-11k range.
335
Laity Poturt
baity Peture
225
Sadty Puters
Saivy Potare
C2tal Cr Coamiizonn
Haus SOaEEiii
Has Crotensaiis
2.5
(a) Memory Usage& & Latency for Open- LLaMA-33
(b) Memory Usage Latency for LLaMA2-78
Figure 5: Memory Usage and Decoding Speed Comparison for LLaMA Models: 3B and 7B. The X-axis represents the imput token length, the left Y-axis denotes memory usage, and the right Y-axis indicates speed about decoding time during inference. Some observations: (I) ReRoPE and Leaky-ReRoPE. exhibit the largest memory footprint for the same input length, and their inference speed follows quadratic function trend. (2) Mesa-Extrapolation shows an approximately linear inference speed, boasting the fastest inference speed and the smallest memory usage under the same input conditions.
5.4 Latency & Memory Usage
To compare actual memory consumption and inference speed, we conduct experiments using both the 3B and 7B versions of the LLaMA model. The results presented in Fig 5 In Fig the X-axis

---

represents the input token length, the left Y-axis denotes memory usage, and the right Y-axis indicates decoding time. It is noteworthy that decoding time closely related to memory usage, primarily from the computation of the attention matrix.
Observing Fig both memory usage and decoding time for Origin and Dynamic-NTK exhibit quadratic trend. Similarly, ReRoPE and Leaky-ReRoPE exhibit the highest memory usage and decoding time, showcasing quadratic trend, which aligns with our analysis (refer to Appendix C.7p. Although LM-Infinite demonstrates a linear trend, its increase is substantial. In contrast, Mesa- ressa-xxrraplationn method also exhibits a linear trend but significantly outperforms other methods in terms of memory usage and decoding time. Furthermore, as the input length increases, this trend becomes more pronounced.
Conclusion
Our study addresses the critical challenge faced by Large Language Models (LLMs) when confronted with longer input lengths, commonly referred to as the extrapolation problem. Through thcoretical exploration, we uncover the underlying mechanisms this challenge, shedding light on the reason of extrapolation failure for both NoPE and PE. Furthermore, we present theoretical evidence demon- strating the potential for effective extrapolation using Weave PE. Based on Weave PE, we introduce a practical solution called Mesa-Exee Extrraa-ttta,,,,inn, which strategically organizes input tokens into chunks to achieve competitive performance with minimal resource usage. Empirical validation demonstrates its effectiveness. Our work not only advances the understanding of the extrapolation problem but also offers practical solution, with a complete free plug-in for LLMs.
Limitations. Mesa- desaa-xxtrppllttion is dlug-and-play method that does not require additional fine- tuning. However, previous work, INTK-award 'nt (2023) also shows that applying further fine-tuning to plug-in extrapolation is possible. Therefore exploring fine-tuning based on Mesa-Extte Mesa-Extrapolation can be an interesting next step. Due to limitations of resources, we have not yet validated our method longer lengths.
Broader Impacts We contend that the significance of completely free plug-in extrapolation method lies in two aspects. Firstly, it enables the expansion of the effective window length of already trained LLMS with no additional cost. Secondly, allows for training L.LMs from scratch with short texts and subsequently expanding their effective window length with free plug-in extrapolation method, which can greatly help the industry improve the extrapolation capabilities of diverse LLMs.
Acknowledgement
This work was supported by the National Key R&D Program of China under Grant w..20222D0160500 and Tsinghua AniversityAAIR)-Asiannn Technologies (China) Inc. Joint Re- search Center. We would also like to acknowledge anonymous reviewers and Zengxiang Lu for their valuable feedback and discussions.
References
Ntk-aware scaled rope allows Ilama models to have extended (8k+) context size without any fine-tuning and minimal perplexity degradation, 2023. URL http:: httpps://wwww... http://wwwweddd.coooooo com/ //
have/
Ba, J. L., Kiros, R., and Hinton, G. E. Layer normalization. arXiv preprint arXiv:1607.064500 2016.
Bai, Y., Lv, X., Zhang. J., Lyu. H., Tang, J., Huang. Z., Du, Z., Liu, X., Zeng, A., Hou, L., Dong, Y., Tang, J., and Li, J. Longbench: A bilingual, multitask benchmark for long context understanding. 2023.
arXiv preprint xxiv:2238..1450
Bertsch, A., Alon, U., Neubig, G., and Gormley, M. R. Unlimiformer: Long-range transformers with unlimited length input. arXiv preprint arXiv:2305.0162. 2023.
10

---

Biderman, S., Schoelkopf, H., Anthony, Q. Bradley, H., O' Briien, K., Hallahan, E., Khan, M. A., Puro- hit, S., Prashanth, U. S., Raff, E., Skowron, A., Sutawika, L., and van der Wal, O. Pythia: A suite for analyzing large language models across training and scaling. arXiv preprint arXivxxXXX.XXXX 2023.
BlackSamorez. TensorParallel: A Library for Efficient Model Parallelization in PyTorch. https 2023.
bloc97. Add ntk-aware interpolation "by parts" correction, 2023. URL fqusseelee/saalld-rroo//1////
com/
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P. Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Chen, S., Wong, S., Chen, L.., and Tian, Extending context window of large language models via positional interpolation. arXiv preprint arXiv:2306. 155595 2023.
Delétang, G., Ruoss, A., Grau-Moya, J., Genewein, T., Wenliang, L. K., Catt, E., Cundy, C., Hutter,
M., Legg, S., Veness, J., et al. Neural networks and the chomsky hierarchy. arXiv preprint arXiv:2207.02098 2022.
Elhage, N., Nanda, N., Olsson, C., Henighan, T., Joseph, N., Mann, B., Askell, A., Bai, Y., Chen, A., Conerly, T., DasSarma, N., et A mathematical framework for transformer circuits, 2021. URL fttt::::/btaansfomer--ooot circuits. httb//2///raaeeor///deeee httm Transformer Circuits Thread.
Gao, L., Biderman, S., Black, S., Golding, L.,, Hoppe, T., Foster, C., Phang, J., He, H., Thite, A., Nabeshima, N., et al. The pile: An 800gb dataset of diverse text for language modeling. arXiv preprint arXiv:2 101.1010000 101.10027.... 2020.
Geng, Xinyang and Liu, Hao. Open LLAMA 3B Large Language Model. https://hugginget co/openIn- wwwpa/ooopnnneeeeeee 1aa.aaaamm___ 2023.
Han, C., Wang, Q., Xiong, W. Chen, Y. Ji, H., and Wang, S. Lm-infinite: Simple on-the-fly length generalization for large language models. arXiv preprint arXiv:2308. 2023.
Haviv, A., Ram, O., Press, O., Izsak, P., and Levy, O. Transformer language models without positional encodings still learn positional information. arXiv preprint arXiv:2203.16633 2022.
Hendrycks, D. and Gimpel, K. Gaussian error linear units (gelus). arXiv preprint Xiv: 606.08815 2016.
Hsieh, C.-P., Sun, S., Kriman, S., Acharya, S., Rekesh, D., Jia, F,, and Ginsburg, B. Ruler: What's 's the real context size of your long-context language models? arXiv preprint arXiv:2404.066: 066544, 2024.
Huang, L., Cao, S., Parulian, N., Ji, H., and Wang, L. Efficient attentions for long document summarization. arXiv preprint arXiv:2104.02112, 2021.
Jin, H., Han, X., Yang, J., Jiang, Z., Liu, 7.,, Chang, C.-Y., Chen, H., and Hu, X. Llm maybe longlm: Self-extend Ilm context window without tuning. arXiv preprint 20XX:22401001322 2024.
Kazemnejad, A., Padhi, I., Ramamurthy, K. N., Das, P., and Reddy, S. The impact of positional encoding on length generalization transformers. arXiv preprint arXiv:2305. 19466, 2023.
Krishna, K., Bransom, E., Kuehl, B., Iyyer, M., Dasigi, P., Cohan, A., and Lo, K. Longeval: Guidelines for human evaluation of faithfulness in long-form summarization. arXiv preprint arXiv:2301.1329: 2023.
Langley, P. Crafting papers on machine learning. Langley, (ed.), Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pp. 1207-1216, Stanford, CA. 2000. Morgan Kaufmann.
Lindner, D., Kramár, J., Rahtz, M., McGrath, T., and Mikulik, V. Tracr: Compiled transformers as laboratory for interpretability. arXiv preprint arXiv:2301.05066 2023.
11

---

Liu, X., Yan, H., Zhang, S., An, C., Qiu, X., and Lin, D. Scaling laws of based extrapolation. arXiv preprint arXIv:2310.05209, 2023.
Microsoft.
https://uugiinfffeecccoohitotttt
Phi-3-mini- 128k- instruct 2024.
Mohtashami, A. and Jaggi, M. Random-access infinite context length for transformers. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
Papineni, K., Roukos, S., Ward, T., and Zhu, W.-. Bleu: method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pp. 311-318, 2002.
Peng, B., Quesnelle, J., Fan, H., and Shippole, E. Yam: Efficient context window extension of large language models. arXiv preprint #rXiv:2309.00077 2023.
Press, O., Smith, N. A., and Lewis, M. Train short, test long: Attention with linear biases enables input length extrapolation. arXiv preprint arXiv:2108 00.11.8.24000 12409, 2021.
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. Exploring the limits of transfer learning with unified text-to-text transformer. The Journal of Machine Learning Research, 21(1):5485-555 5551, 2020.
ROUGE, C. A package for automatic evaluation of summaries. In Proceedings of Workshop on Text Summarization of ACL, Spain, volume 5, 2004.
Roziere. B., Gehring, J., Gloeckle, F., Sootla, S., Gat, I., Tan, X. E., Adi, Y., Liu, J., Remez, T., Rapin,
J., al. Code Ilama: Open foundation models for code. arXiv preprint arXiv:2308. 12950. 2023.
Su, J. Understanding the scale operation of attention from the perspective of entropy invariance, Dec 2021. URLhhtts:://eeuu fm www.aa/wae/eaaaaaaeaaeaaaaaaae 88233
Su, The road to transformer upgrade: 7. length extrapolation and local attention, Jan 2023a. URL
https://kexue. ftw wtt.//rrcivve//////
Ju, J. Rectified rotary position embeddings.
2023b.
Su, J., Ahmed, M., Lu, Y., Pan, S., Bo. W., and Liu, Y. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, pp. 127063, 2023.
Team, M. N. Introducing mpt-7b: A new standard for open-source, commercially usable llms. 2023. Accessed: 2023-05-05.
www www.mossicccomm cm..iccl.cccmmmm www.saaccl..coommaia.o wtt.aaamm...oooooooooo////a///
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023a.
Touvron, H., Martin, I.., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288 002888, 2023b.
Tworkowski, S., Staniszewski, K., Pacek, M., Wu, Y., Michalewski, H., and Miloš, P. Focused transformer: Contrastive training for context scaling. arXiv preprint arXivv2307.0311 2023.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L.,, Gomez, A. N., Kaiser, E.,, and Polosukhin, I. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., and Vladymyrov, M. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, pp. 35151-35174, PMLR, 2023.
Weiss, G., Goldberg, Y., and Yahav, E. Thinking like transformers. Meila, M. and Zhang, (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11080-11090. PMLR, 18-24 Jul 2021. URL https://proccedinggs mlr. wttp://ss.......ee1113////////// http1/////wesss2... html
12

---

Xiao, C., Zhang, P. Han, X., Xiao, G., Lin, Y.. Zhang, Z., Liu, Z., Han, S., and Sun, M. Infllm: Unveiling the intrinsic capacity of Ilms for understanding extremely long sequences with training- free memory. arXiv, 2024.
Xiao, G., Tian, Y., Chen, B., Han, S., and Lewis. M. Efficient streaming language models with attention sinks. arXiv preprint arXiv:2309. 17453, 2023.
Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. An explanation of in-context learning as implicit bayesian inference. arXiv preprint arXiv:211 1.. 1.00000 2021.
Zhang, Liu, Z., Xiao, S., Shao, N., Ye, Q.. and Dou. Z. Soaring from 4k to 400k: Extending Ilm's context with activation beacon. arXiv preprint 4cXiv:2401.03466 2024.
Zhang. Y., Backurs, A., Bubeck, S., Eldan, R., Gunasekar, S., and Wagner, T. Unveiling transformers with lego: a synthetic reasoning task, arXiv preprint arXiv:2206.04301 2022.
13

---

A Related Work
Extrapolation for PE A distinct line of research is dedicated to refining PE for enhanced extrapola- tion capabilities. Notable contributions include the introduction of Rotary Position Encoding (RoPE) Su et al. (2023), implementing relative PE through absolute position information. Similarly, Press) al. (2021) proposes novel PE method ALiBi, fusing position information by directly introducing
the relative position distance term in dot multiplication. In addition, there are other PE methods such as absolute position embedding (APE) Vaswani et al. (017)) and T5's Relative PE Raffel et al. (2020).
Another school of research focuses on enhancing the extrapolation performance of existing LLMs, categorized by whether to include further training. The first subcategory involves further fine- tuning, enlarging the effective window length by training LLMs on longer input texts. Chen et al. (2023)
demonstrates that Position Interpolation (PI) method has superior fine-tune effect, resulting in extended extrapolation capabilities with fewer fine-tuning steps. Mohtashami & Jaggi (0033) utilizes new landmark token to represent individual input blocks, and enables model to select relevant blocks by further training, allowing for longer extrapolation. [Zhang et al.] (2024) follows similar idea by training special token. Bertsch al. (2023) proposes Unlimiformer, k-nearest-neighhor (kNN) indexed encoder-decoder Transformer, enhancing efficiency by retrieving top-k keys for each decoder layer. Despite claiming support for decoder-only Transformer, differences in retrieval results across decoder layers may lead to potential failure. [Toorkoskii et al. (2023) introduces Focused Transformer (FOT), utilizing a contrastive
sorming-inspired training process enhance the (key, value) space structure and enable effective context extension. The second subcategory explores methods that require no fine-tuning yet offer improved extrapolation through plug-ins. Su (2023b) introduces Rectified Rotary Position Embeddings (ReRoPE)). method that rectifies extrapolated relative positions based on RoPE within a specified interval to extend the effective window length. In addition, Deaky-ReRoPP offers an alternative by allowing a controlled leakage of position extrapolation within an interval. Both approaches are well-suited for LLaMA model families Touvron et al. (2023b) Touvron et al. (2023a), eliminating the need for fine-tuning. These methods do suffer from some drawbacks, such as twofold increase memory consumption and longer inference time. We refer to this class of methods that achieve extrapolation by weaving the relative positions of PE without fine-tunin sunitttning as Weave PE. We also notice that, recent work, InfLLM Xiao et al. (2024), proposes additional memory units, which lookup ooken-relevant units for attention computation. In addition, it uses a modified encoding scheme similar to ReRoPE to achieve longer extrapolation. It is worth noting that the methods of the weave PE class can be applied seamlessly to these new designs. However, there is still no theory to explain why the methods of weave PE class can work. In different line of inquiry, ntk (2023) proposes the "NTK-aware" method by drawing from the Neural Tangents (NTK) idea, which explores the high-frequency extrapolation and low- www-frequeccy interpolation concept for RoPE, Based on "NTK-aware" recent works bloc97 (023)) Peng al.
(023), Roziere et al. (2023). Liu et al. 2023) perform further fine-tuning for optimal results.
Han et al. (2023) proposes LM-Infinite, which employs a A-shaped mask to prevent surpassing the
effective window length by discarding central tokens. However, this design choice inevitably results in loss of information. Likewise, Streaming- LLM Xiao et al. (2023) adopts similar strategy to avoid surpassing the effective window length by discarding a portion of input tokens.
Extrapolation for NoPE There also exists counter perspective asserting that the position informa- tion of an input sequence can be perceived without utilizing PE. In a comprehensive experimental comparison presented in Kazemnejad et al. (2023), the decoder-only Transformer is shown to exhibit superior extrapolation properties with no position encoding (NoPE). [Hviv et al. (2022) conjectures that causal attention enables the Transformer to infer position information without the help of PE, demonstrating its comparable performance with standard Transformer models through probing exper- iments. These new studies pose a key challenge regarding the choice of whether using PE or not in Transformer architecture.
Theorems for Extrapolation We mainly focus on Transformer architecture. Although the Trans- former architecture is considered as "black box", there are ongoing efforts trying to explain its inner workings. Von Oswald et al. (2023) begins by providing a specific weight construction that elucidates the mechanistic understanding of in-context learning within optimized Transformers. Lindner et al. (2023) introduces interpretability for Transformers through programming, allowing the derivation of a program Transformer architecture tailored for specific tasks. In Han et al, (2023), the authors conclude that long-distance attention logits will explode. However, this does not clarify the
14

---

relationship between the effective window length and the existing supremum. It merely indicates an increase in the supremum, without directly implying an increase in the obtained actual attention logits. In Kazemnejad et al. (203)) inspired by programming Transformers Lindner et al. (2023), the authors construct a specific Transformer with predefined matrix parameters, theoretically demonstrat- ing that NoPE can recover both absolute and relative position information even without the use of PE. However, these results fall short in explaining the underlying reasons for the failure of NoPE extrapolation. Built upon the entropy increase theory, [Han et al. (2023) proves that with the expansion of input length, the entropy of attention experiences corresponding increase. Additionally, [Su (202T) introduces scaling factor, denoted as lo9train-les (n), which serves mitigate entropy increase. Nevertheless, their theorems do not show that extrapolation fails beyond the effective window length.
We observe that extrapolation failure is intricately linked to the max window length. Nevertheless, existing theories on Transformers do not reveal the internal mechanism about extrapolation and the max window length. In light of this, our endeavor is to establish a correlation between these two aspects, aiming to offer theoretical insights that can guide us towards designing applicable extrapolation methodologies.
B Experiments Details
B.1 Passkey Retrieval Dataset
The data used to perform the passkey task is constructed as follows:
TASK-DESCRIPT "There an important info hidden inside lot of irrelevant text. Find it and memorize it. I will quiz you about the important information there."
DEFAULT-CONTEENE "The grass is green. The sky is blue. The sun yellow. Here go. There and back again." "
KEY-CONTENT "The pass key is (KEY). Remember it. (KEY) is the pass key."
The PASK-DESCRIPT is placed at the beginning of the sample. Subsequently, the DEFAULT- CONTENT is repeated multiple times to serve as filler text. A randomly generated password is then created and inserted into the designated KEY-CONTENT section. Finally, a random position selected, and the KEY-CONTENT, containing the generated password, is seamlessly incorporated into the sample.
The LLM is required to find the correct password from the sample.
B.2 Params Setting
Nesa--xxtappllttion We design the DynamicSplit function used in Algorithm I dynamically divide the input sequence into several subsequences according to the input length. The length cach subsequence corresponds to the size of the chunk. Let C denote the length of the each chunk (except the first chunk length JF and the last chunk length L). Define I as input token length and T as max training length.
The DynamicSplit function detailed as follows:
In general, we set F = 100, .Maas 200 and = 512. Based on these criteria, we have devised a method for dynamically segmenting sequence. Leveraging the total length of the input token and the aforementioned requirements, we dynamically determine the length of each individual chunk.
Additionally, Stair PE is primarily employed in the manipulation of the last chunk. We need to concatenate all chunks together. After splicing chunks, the required positons will far exceed the max training length. At this time, we need to rearrange the positions according to Equ generally set the extrapolated position = 512 and set the extrapolated width E
3 In Equ 3 we
50.
Implement Stair PE on RoPE and ALiBi The handling of RoPE, et al. (2023) involves assigning positions to the query vector and key vector. The length the query corresponds to the length the last chunk, while the lengths of the key and value align with the combined lengths of all chunks. We assign position encoding the query vector according the same sequence positions. Regarding the key's 's position encoding, we utilize the extrapolated width E and extrapolated point N. By designing
15

---

Algorithm 2 DynamicSplit function
Require: LLM parameters
Input: $ (input token sequence)
Output: F.CC
1: set the values of F and & respectively as constants
2: set T according the LLM parameters
3: get I according to input sequence 8
.N- - Iー6ー
5: M = (I-L-F) mod (T - F)
6: if M < Mmax then
CTT-7
8: else
9: C= I-C-J
N-1
10: end if
the position encoding of query and key respectively, the relative position scheme defined by Stair PE can be implemented. And, for computational efficiency, we ensure that the relative PE of the last token last chunk completely follows Stair PE. The other tokens of the last chunk are similar to Stair PE.
For ALiBi's Press al 202I)) position processing, we directly transform the relative position of the last chunk into the aforementioned structure within the mask matrix, refer to RoPE.
It is emphasized that the considerations outlined above primarily address the generation mechanism of LLM. The position encoding of the last chunk must align as closely as possible with the original position setting. This consideration is rooted in the belief that the latent concept Xie al. (2021) formation heavily relies on there, with subsequent chunks providing essential information support. Experiments affirm that the last chunk significantly influences the accurate output of LLMs. This serves as the experimental foundation for our Mesa-Extrappee Extrapolation method design.
ReRoPE & Leaky-ReRoPE We follow Su 2023b) for configuring the parameters of ReRoPE and Leaky-ReRoPH The extrapolated position for ReRoPE established at 512, mirroring the setting for Leaky-ReRoPE. Simultaneously, the extrapolated increment for Leaky-ReRoPa is caleulated in relation to the input length, following the formula below:
T - w I
where u is the extrpolated position as 512, T is the maxium training length, and the input token length.
The ReRoPE and Leaky-ReRoPP methods are currently only applied to the LLaMA model series. We implemented ReRoPE based on its ideas on the MPT models.
LM-Infinite & Streaming-LLM LM-Infinite Han al. (2023) introduces two branches for attention masking: a global branch on the left and local branch on the right. The global branch enables each token to attend to the preceding Ryylabo tokens if they appear before the current token. Conversely, the local branch allows each token to attend to preceding tokens within a distance of Titcca- Tokens branches are disregarded during the attention operation. Subsequently, following its setting, set Nosel = I, where I still represents the training length. The choice of ngglobal has minor impact on model performance within the range [10, 100), and thus, we fix N'globet 100 as its code setting. The distance limit entails the "effective distance" d within I. and we set d = I.
outside these
Streaming LLM Xiao al. 2023) adopts similar design to LM-Infinite. It introduces initial token known as Attention Sinss, whose length denoted by æ. It also defines a Rolling KV Cache for retaining the most recent tokens, whose length is denoted by y. It set where T denotes the maximum training length. The central tokens are referred to Evicted Tokens.
and y = T z,
The distinguishing factor between the two approaches lies in the selection of the initial token length, with IM-Infinite opting to splice longer tokens. We speculate that this is also the reason why Infinitit performs better than Streaming- LLM in the experiments.
16

---

Origin & DYnamic-NTK For Origin, it refers to loading the model directly, without using any methods. Dynamic-NTK differs from Origin by only adjusting the angle value of its RoPE component, according to the input length Liu et al. (2023).
The Dynamic-NTK method is currently applied to the LLaMA model series.
B.3 Weave PE-based Schemes
We list the details of the weave PE-based methods, including ReRoPE and Leaky-ReRoPE, follows:
O
0
2
0
2
ReRoPE=
2
1
0
Leaky-ReRoPE:
N
0
1
N
2
0
N+
N
1
N
N
2
1
0
N
N
2
N
N
N
2
1
0
N++ N-
N
where left ReRoPE shows relative position attention matrix. including (1) Numbers marked each cell denote its relative position (t - i) between qu and kG. (2) start to extrapolate position from relative position N. And right Leaky-ReRoPE, shows relative position on attention matrix, including (1) Numbers marked on each cell denote its relative position (t i) between q and k;- (2) It start to extrapolate position from relative position N, with incremental factor -
With Stair PE defined on Equ 3 the extrapolated position after N exhibits a fixed extrapolated width E. resembling stair-like increment. Our Mesa-Extrapolatioon is designed with finer position granularity compared ReRoPE. Simultaneously, unlike Leaky-ReRoPP ours utilizes previously trained positions, ensuring greater stability.
While these weave PE schemes, including ReRoPE, Leaky-ReRoPE, and Stair PE, demonstrate theoretical feasibility, their practical implementation may encounter computational complexities. For instance, both ReRoPE and Leaky-ReRoll are primarily employed in the LLaMA models, which is based on RoPE Su et al. (2023). Due to the distinctive nature of RoPE, these methods necessitate the calculation of the attention matrix more than once, resulting in double the normal memory consumption. Moreover, given the quadratic complexity of the calculations, the input length expands, both inference time memory consumption grow proportionally.
B.4 ALiBi on MPT-7B
is worth noting that the ALiBi implementation of MPT is only an approximation, as follow:
9
9
8
9
8
-7
9
-8
-7 -6
9
-8
-7
-6
-5
9
8
-7
-6
5
-4
9
8
-6
-4
-3
9
-8
-7
6
5
-
-3
-2
9
-8
6
-3
-2
-1
9 -8
-7 6
-5
-3 -2 -1
0
where showcase an input token length for ALiBi PE mask. Based on this approximate implemen- tation of ALiBi, we still use splitting chunk and Stair PE to implement Mesa-Extrapolatinn We speculate that the approximation ALiBi is the reasons for the instability of the extrapolation on Accuracy.
17

---

Table 2: BLEU metric for mean and standard variance LLaMA2-7D 7B-Chat, averaged on samples within each interval using the Gov GovReport dataset. The best values are marked in bold. Some observations: (I) Dynamic-NTK shows slightly better performance within 11k. (2) Weave PE-based methods showcase the ability to achieve
scores of varying degrees.
LIk
Rellae
4 6.03
0:30- +3 1.00
8.67 RUOP
BUSS- 1 66.
833 6.01
0:311 + 3/6
81016-0:0
6403 6-0-1c
0.:6--8 8013
0.678 nAc1
Dreasse NTT
08803 (185
0.90- 1.05
6160--08)
DUmS --03
9J33 -800
8J00 9-101
1.006-0:25
08:39 5/05
B007 L882
0 9.04
0.-000
0.8..8
0200.000 8.00
00--86
(L3 &
C More Experimental Results
C.1 BLEU Results GovReport
We use the GovReport dataset and employ BLEU Papineni et al. (2002) as evaluation metric, with a same setting applied on Table T The experimental result for BLEU presented Table In Table we present the mean and standard variance for each method across various interval lengths. evident that, as the input token length increases, the performance consistently deteriorates for LM-Infinite. Streaming- LLM also experiences extrapolation failure beyond the model's inherent effective window length of 4k.
Dynamic-NTK shows slightly better performance within 11k. Here, the BLEU scores exhibit almost consistent results with those of ROUGE on Table is also noteworthy that additional experiments show performance degradation of Dynamic-NTV beyond 11k, likely suggesting limited effective extrapolation range for Dynamic-NTK.
Weave PE-based methods, including ReRoPE, Leaky-ReRaon and Mesa- Exttrapppplol,,inn, consistently demonstrates competitive results, maintaining similar generation quality the length increases.
Overall, despite the chunking applied to our Mesa-Extrapolation method, it maintains a competitive edge compared to ReRoPE and Leaky- ReeoPE. This is achieved even with the trade-off between losing a certain amount of information and reducing memory consumption and inference time.
The results of Mesa-Extrapolle within 1000 tokens across different input lengths, are detailed in Table
in the summary task, focusing on the generation of summary text
C.2 Perplexity (PPL) metrics on MPT-7b
Following the same metrics setting about LLaMA models on Fig we plot the NLL result about MPT-7B on Fig alas below:
34
Origin
StreamiingLLM
12
Mesa-Extropo ation
10
2k
Token Length
Figure 6: PPL Metric Comparison for MPT-7B using Origin, Streaming-LLMM, and Mxst-Extraoolation. The white dashed line represents MPT-7B's maximum training length at 2k. Some observations: (I) For Origin. after surpassing the maximum training length, extrapolation extends to approximately 3.5k, leading to a rapid escalation in PPL. (2) Both Mesa-Extrapolatics and Streaming-LLM, models exhibit effective negative log- likelihood (NLL) values.
18

---

In Fig 6 both Mesa- Extrapaxttaoooatoonn and Streaming-LLAe LLM demonstrate effective negative log- likeeiihioood (NLL) values. For the original MPT model, after the extrapolation is extended 3.5k, it will cause the perplexity (PPI.) level to rise rapidly.
ALiBi Press et al. (202T) can still effectively extrapolate around 3.5k position after surpassing the maximum training length of 2k. This observation affirms the extrapolation capability of the ALiBi method, especially when compared with RoPE's extrapolation results.
However, it is essential to highlight that while ALiBi achieves extrapolation to 3.5k in above NLL task, its performance in the Passkey and LongEval tasks (refer to C.3) reveals limitations. This discrepancy is attributed to an inherent characteristic of ALiBi. ALiBi's s expression (refer to (.2) indicates constant decrease in the value of its position encoding the relative distance increases. Considering the Soft operation within the attention mechanism, under identical conditions, the attention score obtained becomes smaller. This implies that tokens situated farther away receive less attention, possibly leading to the neglect of these distant tokens. Therefore, despite ALiBi's s apparent success in effectively extrapolating the NLL task to 3.5k, it falls short in attending to tokens beyond the maximum training length in practice. A similar analysis process is as Su (0023)).
It's noted that, Kazemneea et al. (023) claims to possess extrapolation capabilities akin to ALiBi. We hypothesize that the underlying reasons for NoPE's extrapolation performance align with the analysis presented here.
C.3 Evaluation on LongEval
We conduct additional testing on LongEval Krishna et al. (2023) lines task, recently prominent evaluation task for long texts.
0.M0
Origin LM4
igin
Wamirr--MMMM aoolattt
ReRoPE
Accuracy
Looky
Opttemic-NTK
SMM
Mosa Extopotaaion
5k
7k
9k
11k
13k
15k
4k
6k
3ic
10k
12k
4k
6kc
8k
10k
12k
Taken Length
Token Length
Takken Length
(a) Accuracy on LLaMA2-7B-Chat
(b) Accuracy on MPT-7B
(c) Accuracy on PyThia-6.9B
Figure 7: LongEval Lines Task on LLMs using various methods. Some observations: (1) Origin and Streaming- LLM consistently exhibit an inability to extrapolate beyond the effective window length. (2) LM-Infinite shows weak extrapolation ability the LLaMA2-788 7B-Chtt model and fails extrapolate on the MPT-7B model. (3) Weave PD-based methods, including ReRoPE, Leaky-ReRoPE. and Mesap-xttrpolltionn, all exhibit commendable extrapolation capabilities on the LLaMA2-7B-CHI model. (4) For the MPT-7B model, all methods display weak extrapolation performance, with Mesa-Extrapolation slightly outperforming other methods. (5) Mesa--xxtapollation also shows a certain extrapolation ability the PyThia-6.9B model, with decrease in extrapolation performance as the input length increases.
Fig 7 show the accuracy of LongEval Lines Task. Origin and Streaming-LL.M consistently exhibit an inability to extrapolate beyond the effective window length. IM-Infinite shows weak extrapolation ability on the LLaMA2-7B-CNH model and fails to extrapolate on the MPT-7B model. Dynamic-NTK method, shown earlier, almost fails after the input token length exceeds 11k. Weave PE-based methods, including ReRoPE, Ceaky-ReRoPE and Exsaapxxtapolattio, all exhibit commendable extrapolation capabilities on the LLaMA2-7B-CIL display weak extrapolation performance, with Mesa- Mesa--xxtaoolaation slightly outperforming other methods. We analyze that the reason for the failure of extrapolation in the MPT-7B model is attributed to the approximated implementation of ALiBi PE. This approximation makes it susceptible to interference when use weave PE (refer to C.2).
model. For the MPT-7B model, all methods
Mesa- Exstapxtraoootooon also shows a certain extrapolation ability on the PyThia-6.99 6.9B model, with a decrease in extrapolation performance as the input length increases.
19

---

C.4 Evaluation on LongBench
We select LongBench Bai et al. (023) dataset and use 5 major categories of tasks, including Single- Document QA, Multi-Document QA, Few-shot Learning. Synthesis Tasks and Code Completion. Among them, each task selects dataset, namely qasper, hotpotqa, samsum, passage-retrieval-en and repobench-p. Taking into account the varying memory consumption of different methods, we opt to filter out samples with an input length exceeding 10k to prevent discrepancies caused by out-of-memory (OOM) issues. We use the abbreviations in T S-Document (Single Document) QA, M-Document (Multi Document) QA, F-Learning (Few-shot Learning), S-Tasks (Synthesis Tasks), C-Completion (Code Completion).
Table 3: Accuracy LongBench across multiple tasks using LLaMA2-7B 1--AA-----Ca Some observations: (1) Dynamic-NTK shows good performance, especially for Code Completion. (2) LM-Infinite shows slightly weaker performance. (3) desaa-xttappllation shows better performance on most tasks.
Multi-Tasks
S-Document QA
M-Document QA
F-Learning
S-Tasks
C-Completion
Input Token Length
4-8k
8k+
4-8k
8k+
4-8k
8k+
4-8k
8k+
4-8k
8k+
Origin
1.3
1.25
3.03
0
2.33
0
4.72
1.11
Dynamic-NTH -NK
22.22
11.7
35.2
19.4
37.96
38.32
12.4
6,06
34.28
50.14
LM-Infinite
17.39
12.22
32.52
30.55
38.25
36.17
10.85
3,03
33.09
43.89
Streaming LLM
1.22
1.25
3.05
5,68
0.21
Mesa-Extrapolation
24.69
20.24
36.72
42.76
38.63
38.41
14.73
3.03
20.6
22.39
In Table 3 Origin and Streaming-LLLM barely work after exceeding the maximum training length of 4k. IM-IIfiiitte shows slightly weaker performance. Dynamic-NTK shows good performance, especially for Code Completion. Considering the effective scope of Dynamic-NTK, speculate that this is related to the setting within 10k length. Mesa-Extrene Mesa-Extrapolation shows better performance on most tasks.
C,5 Enhanced Prompts for Mesa--xtrrppolation
Considering that Mcsa- drssa-Extrapolatioo involves positional approximation, as the input length increases, attention becomes more dispersed, resulting in increased entropy. One possible approach to mitigate these entropy increases to utilize instruction instruction-aligned prompts. These prompts may represent the strongest latent concepts that the model can follow, while clearly articulating the goals to be achieved. Similarly, may be the reason why PyThia cannot achieve 100% accuracy within its training length on Fig due to lack of instruction alignment.
Based on these considerations, we employ the model's corresponding prompt Geng, Xinyang and Liu, Hao 2023) and augment it with explicit goal statements, referred to an enhanced prompt, like below:
Q: what is the passkey in below text?
Sample An A:
or
Sample An A: the passkey is
Additionally, we leverage model parallel inference technology BlackSamorez (2023) and perform verification concurrently on 2 A800 GPUs.
Fig & show the accuracy 3 LLaMA models with enhanced prompts using Mesa- Mesaa-xtrrppllttion. We declare that the longest input length that these models can currently reach is the limit our existing hardware resources. For LLaMA-3B, the enhanced prompts improve the Accuracy and is extrapolated to 60k. (2) Both of LLaMA2-7P 2B-Cha and Vicuna-133 13B models, show good improvements by the enhanced prompts.
Through this experiment, we hypothesize that by writing prompts more carefully and accurately, we maximize the extrapolation performance of free plug-in.
20

---

Mion Extrandation
Mush Extrapdaaicn
Mesa EoHepsiti
Eatrapa www.arood proinet
Nowa petercenpprorrr
Mosa crapcidton Tww.eR
Takon Longth
TDkin Longon
Tiker Length
Accuracy on LLaMA-3B
Accuracy on LLMMA2-BB-Cha
(c) Accuracy Vicuna- 13B
Figure 8: Accuracy about Passkey Retrieval Tasks using enhanced prompts for Exsappxxtraoolttion The gray line represents the training length 2k, 4k, and 2k, respectively. Some observations: (1) On the LLaMA-3B model, the enhanced prompts significantly improves the Accuracy extrapolated 60k. (2) Both of LLaMA2-7PP 22--BBhhhtt and Vicuna-133 13B models, show good improvements by the enhanced prompts.
C.6 Ablation Experiments
We design ablation experiment about weave PE based methods. We apply the encoding schemes of ReRoPE and Leaky-ReRoPE to chunk-based triangular attention matrices, aligning them with our implemented Mesa-Extrapolation. The entire design the ablation experiment involved controlling only one variable, the weaving PE scheme, applying different weaving PE methods to the processing of the last chunk, while using the same dataset and testing environment. The experimental results follows:
2C4
eetopaatton
Rchart
Bufturt
Lodka
101
13k
20k
25
32k
20%
25k
2010
238
30k
2k
300
12%
34h
16k.
(a) Accuracy on LLaMA-3B
(b) Accuracy on LLaMA2-7B BBChht
(c) Accuracy on Vicuna- 13B
Figure 9: Accuracy about Passkey Retrieval Tasks using chunk-based triangular attention matrix.
Figure demonstrate that both ReRoPE and Leaky-ReRoPE experience certain loss accuracy as the input sequence grows. We speculate that this may be due to ReRoPE repeatedly using the same extrapolation positions, while Leaky-ReRoPE, employing some fractions, may not be as precise as Stair PE in comparison to normal relative positions, resulting in a slight decrease in effectiveness.
C.7 Theoritical Speed & Memory
We assess the computational memory usage and inference time about decoding speed on various methods.
Table 4: Theoretical Memory Usage Based on Attention Matrix for Different Methods. Observations: (I) Origin and Dynamic-NTK exhibit identical quadratic memory consumption. (2) ReRoPE and Peaky-ReRoPE demonstrate 2x the memory consumption of Origin. (3) LM-Infinite, Streaming LLMM, and Mesa- desa-Extrapolation showease linear memory consumption.
Methods Origin
ReRoPE
Leaky-ReRoPE
Dynamic-NIK
LM-Infinite
Streaming
Mesa-Extrapolation
Memory
O(²))
x O(z²)
2 O(n²)
O(x²)
O(11 v2jn)
0((1 + 22m)
O((2 + v2)n)
Table shows the theoretical result about the memory usage. For Origin, the attention matrix calculation requires the current token to compute the attention score with each previous token, resulting a memory footprint of O(12). Dynamic-NTK only alters the angle base, making it different from the Origin but still quadratic. For ReRoPE and Leaky-ReRoPE, as showed in Su (2023b), since the attention matrix needs be calculated twice, their memory footprint 2 x On")). For Mesa- Mesaa-Extrpolattion. its strategy involves splitting chunks while avoiding the
21

---

quadratic term. Accounting for splicing in the last chunk, its total memory usage scales proportional to O((2 + 22) LM-Infinite and Streaming-LLM, adopt similar A-shaped mask, that scales proportional to O((1 + /2)n).
C.8 Generated Summary using Mesa- Resa-Extrapolltion
We present here the results of the summary generation task using GovReport [Huan al. (222T) In this experiment, task is to generate a summary for texts of varying lengths, limited to 1000 tokens. The outcomes yielded by Dieaa-xxtrppolation are outlined below on Table 5
Table 5: Mesa- Exttraxxttoootiooon undertakes summarization tasks and generates text based varying input lengths from the GovReport dataset. Some observations: (1) Mesa Extrapolation adeptly and systematically summarizes key points one by one across various input lengths. It showcases logical coherence and demonstrates commend- able summarization capabilities. (2) Additionally, Mesa--xtrapplaate accurately incorporates punctuation and exhibits automatic stopping mechanism for proper stopping.
Input length
Mesa- dess--Exrraplation generate summary texts within 1000 tokens
5k
The Commercial Crew Program of NASA awarded two contracts in 2014 to Bocing and SpaceX, valued at up to $4.2 billion, to develop and demonstrate crew transportation systems that meet NASA requirements for the International Space Station (ISS). The program is experiencing delays and schedule uncertainty due to technical issues and safety concerns with the contractors' systems. NASA has been working to address these issues and has made progress in testing and evaluating the contractors' systems, but there are still risks and uncertainties associated with the program. The main content of the report includes:
NASA awarded two contracts to Bocing and SpaceX in 2014 develop and demonstrate crew transportation systems for the ISS. The program is experiencing delays and schedule uncertainty due to technical issues and safety concerns with the contractors' systems.
NASA has been working address these issues and has made progress testing and evaluating the contractors' systems, but there are still risks uncertainties associated with the program.
The program's 's ability to process certification paperwork is creating uncertainty about the timing of certification for either contractor, which could result in delays the first operational mission the ISS.
NASA has announced plans to purchase two additional Soyuz seats from Russia to extend U.S. access to the ISS beyond September 2020, if delays to certification of the Commercial Crew Program contractors continue.
The report highlights the need for NASA to maintain contingency plan ensure uninterrupted access the ISS delays with the Commercial Crew Program contractors continue beyond September 2020.
Continued on next page
22

---

Table 5 Continued from previous page
Input length
Mesa- Dessa-xxtrapolation generate summary texts within 1000 tokens
6k
The main content of the report is about the contract financing policies and practices of the Department of Defense (DOD) and their impact on the defense industry. The report highlights the following key points:
DOD has long recognized that contract financing is capital- inteesive and takes long time complete, and therefore provides contract financing help contractors manage their expenses.
DOD provides contract financing through progress payments and performance- based payments. Progress payments are based on the percentage of work com- pleted, while performance-based payments are based on the contractor's 's achieve- ment of specific milestones.
The Federal Acquisition Streamlining Act 1994 requires DOD use performance-bast based payments whenever practicable. However, the use performance-basse payments has decreased since the act was passed.
In 2010, DOD issued a proposed rule amend the Defense Federal Acquisition Regulation Supplement (DFARS) provide performance-bes The proposed rule would have allowed contractors to receive payments based on their performance, but the rule was later withdrawn.
payments.
Despite the decreased use of performance-basee -basd payments, DOD has not conducted comprehensive assessment of the impact of its contract financing policies on the defense industry over years.
GAO recommends that the Acting Secretary of Defense direct the Under Sec- retary of Defense for Acquisition and Sustainment to conduct a comprchensive assessment of the effect of DOD's contract financing policies the defense industry and update the assessment on a recurring basis.
'The report also notes that changes the defense industry, such as the emergence of new entrants and changes in market and economic conditions, have affected the defense industry's 's ability to attract new entrants.
DOD has acknowledged the need assess contract financing policies against market conditions on an ongoing basis, but has not done so comprehensively over 30 years.
The report highlights the need for DOD to update its contract financing policies to reflect changes in the defense industry and to ensure that they are effective in supporting the defense industry.
Continued on next page
23

---

Table 5 Continued from previous page
Input length
Mesa- Mesa-Extrapplation generate summary texts within 1000 tokens
7k
The report summarizes the results of a review of the monitoring and evaluation (M&E) policies of six US govermment agencies that administer foreign assis- tance: the Department of Defense (DOD), the Department of State (State), the Millennium Challenge Corporation (MCC). the US Agency for International De- velopment (USAID), the Department of Health and Human Services (HHS), and the Department of Agriculture (USDA). The review was conducted in response to the Foreign Aid Transparency and Accountability Act of 2016, which requires the Office of Management and Budget (OMB) to issue guidelines for M&E of foreign assistance. The report finds that while the agencies have taken steps to implement the guidelines, there some areas where they could improve. For example:
DOD, HHS, and USDA did not include the requirement to conduct impact evaluations for all pilot programs, which could lead to duplication or scaling up of programs without fully understanding their effectiveness.
State, USAID, and MCC have policies that generally address leading practices for M&F, but some agencies have not incorporated all of the required practices into their policies.
OMB's guidelines do not include leading practices for program evaluation, which could limit the usefulness of foreign assistance program evaluations.
Some agencies have not established roles and responsibilities for evaluation activities when funds are transferred between or among agencies, which could result in a lack of accountability for evaluation activitics.
The guidelines do not require agencies to develop monitoring plans based on risk assessments, which could result in lack of focus on high-risk programs.
The guidelines do not require agencies to provide justifications for not con- ducting impact evaluations, which could result in a lack of transparency and accountability.
The guidelines do not specify requirements for evaluating the effectiveness of pilot programs, which could result a lack understanding of the impact these programs.
The guidelines do not require agencies to develop staff skills in evaluation and use of evidence, which could result in lack of capacity to conduct effective evaluations.
The guidelines not provide specific requirements for evaluating the effec- tiveness of interagency agreements, which could result in a lack of accountability for these agreements.
The guidelines do not require agencies provide timely evaluation results to decision decision-makers, makers, which could result in lack of usefulness of evaluation findings.
The report makes seven recommendations for improvement, including that OMB should update the guidelines to include leading practices for program evalua- tion, and that agencies should establish roles and responsibilities for evaluation activities when funds are transferred between or among agencies. The report also recommends that agencies should develop monitoring plans based on risk assessments, provide justifications for not conducting impact evaluations, and evaluate the effectiveness of pilot programs.
Continued on next page
24

---

Table 5 Continued from previous page
Input length
Mesa- Dessa-xxtrapolation generate summary texts within 1000 tokens
8k
The main content of the report focused on the challenges and limitations faced by dual-eligible beneficiaries in the Medicare and Medicaid programs, particularly in the coordination of care and the alignment of enrollment. The report highlights the following key findings:
1. Difficulty in accessing care: Dual-eligible beneficiaries face challenges in accessing care due the complexity of the Medicare and Medicaid systems, lcading to delays receiving necessary care.
2. Limited information on experiences: There is a lack of quality information on the experiences of dual-eligible beneficiaries who have been default enrolled into D-SNPs, which hinders CMS's ability identify the extent of the challenges faced by these beneficiaries and determine how address them.
3. Limited coordination of care: Dual-eligible beneficiaries may experience limited coordination of care due to the lack of alignment between Medicare and Medicaid systems, leading to fragmented care and confusion among beneficia- ries.
4. Limited provider networks: Dual-eligible heneficiaries may face limited provider networks, which can make it difficult for them to access necessary care. 5. Limited enrollment options: Dual-eligible heneficiaries may have limited enrollment options, which lead to default enrollment into D-SNPs without their knowledge or consent.
6. Limited quality information: There is a lack of quality information on the experiences of dual-cligible beneficiarics who have been default enrolled into D-SNPs, which hinders CMS's 's ability to identify the extent of the challenges faced by these beneficiaries and determine how address them.
7. Limited alignment of enrollment: Dual-eligible beneficiaries may face limited alignment of enrollment between Medicare and Medicaid, leading to confusion and fragmented care.
8. Limited provider networks: Dual-eligible beneficiaries may face limited provider networks, which can make difficult for them to access necessary care. 9. Limited enrollment options: Dual Dual-eligible beneficiaries may have limited enrollment options, which can lead to default enrollment into D-SNPs without their knowledge consent.
10. I. Limited quality information: There is lack of quality information on the experiences of dual-eligible beneficiaries who have been default enrolled into D-SNPs, which hinders CMS's ability to identify the extent of the challenges faced by these beneficiaries and determine how to address them.
The report highlights the need for CMS to take steps to address these chal- lenges and improve the coordination of care and alignment of enrollment for dual-eligible beneficiaries. The report recommends that CMS obtain quality information on the experiences of dual-eligible beneficiaries who have been de- fault enrolled into D-SNPs and take steps improve the alignment of enrollment between Medicare and Medicaid.
Continued on next page
25

---

Table 5 Continued from previous page
Input length
Mesa- Desa--xxrapolation generate summary texts within 1000 tokens
9k
The report summarizes the actions taken by the Army improve its marketing and advertising program response to recommendations from U.S. Army Audit Agency (AAA) in its April 2018 reports. The Army has taken several steps to address the recommendations, including:
1. Revising strategic goals: The Army has revised its strategic goals to focus the activation phase the consumer journey, which includes providing potential recruits with information about the Army's 's opportunities and henefits.
2. Updating and documenting its assessment process: The Army has updated its assessment process to include more detailed information on the effectiveness of its marketing and advertising efforts.
3. Improving data systems: The Army has taken steps to improve data systems, including developing a new resource requirements projection model and updating its marketing and advertising regulation.
4. Integrating national and local marketing and advertising efforts: The Army has established new office, the Army Marketing and Research Group (AMRG), to coordinate and oversee marketing and advertising efforts at the national and local levels.
5. Obtaining new tools to determine required marketing and advertising sources: The Army has contracted with primary advertising agency to develop and implement marketing
advertising program, and has also established a project management office to oversee the development of a new marketing career path for military personnel.
The report also identifies the actions taken by the Army to address the recom- mendations in the AAA report on contract oversight, including revising strategic goals, updating and documenting its assessment process, improving data systems, and integrating national and local marketing and advertising efforts. The report notes that the Army has taken steps to address the recommendations, but it is too early determine the efficctivneess of these efforts. The report concludes by stating
will important for Army continue use commercial best practices for assessing the effectiveness of its marketing and advertising program and to regularly evaluate and improve its program to ensure its success.
Continued on next page
26

---

Table 5 Continued from previous page
Input length
Mesa- Mesa--xxrapplation generate summary texts within 1000 tokens
10k
The report discusses the challenges faced by the US Department of Veterans Affairs (VA) in providing disability compensation to veterans. The VA pays mouthly disability benefits to veterans who have service-connecter conditions, which are conditions that were caused or aggravated by military service. The VA has been facing challenges in determining when to reevaluate these and the report highlights several areas where improvements can he made.
conditions,
Firstly, the report notes that the VA does not have a clear understanding of the health outcomes of veterans with service-connected conditions. Despite the fact that the VA spends billions of dollars each year on disability compensation and health care for veterans, does not have adequate data assess the effectiveness these efforts. The report recommends that the VA should develop a plan to collect and analyze data on the health outcomes of veterans with service- connected conditions.
Secondly, the report highlights the issue of unwarranted recvaluations. Despite the fact that the VA has rating schedule that provides guidelines for evalu- ating the severity of service-connected conditions, claims processors are not always following these guidelines. As result, many veterans are undergo- ing unnecessary reevaluations, which can be time-consuming and costly. The report recommends that the VA should clarify the knowledge, skills, and abil- ities required for claims processors to determine when to reevaluate veterans' service-comnected conditions.
Thirdly, the report notes that the VA'S procedures for reevaluating service- connected conditions are not always consistent. While the VA has a rating schedule that provides guidelines for evaluating the severity service-comneeted conditions, claims processors are not always following these guidelines. As a result, many veterans are undergoing unnecessary reevaluations, which can be time-consuming and costly. The report recommends that the VA should develop and implement a plan to ensure that claims processors have the neces- sary knowledge, skills, and abilities to determine when to reevaluate veterans' service- revvececonnected conditions.
Fourthly, the report highlights the issue of inconsistent application of rating criteria. Despite the fact that the VA has a rating schedule that provides guidelines for evaluating the severity of service-connected conditions, claims processors are not always applying these criteria consistently. As a result, many veterans are receiving inadequate compensation for their service-connected conditions. The report recommends that the VA should clarify the knowledge, skills, and abilities required for claims processors to apply the rating criteria consistently. Fifthly, the report notes that the VA's training program for claims processors not adequate. While the VA provides training on disability compensation and health care for veterans, it does not provide enough training on the reevaluation process. As result, many claims processors are not adequately equipped determine when reevaluate velerans' service-connected conditions. The report recommends that the VA should develop and implement a plan to provide additional training to claims processors on the reevaluation process.
Finally, the report highlights the issue of limited data on the health outcomes of veterans with service-conneeted conditions. Despite the fact that the VA spends billions of dollars each year on disability compensation and health care for veterans, it does not have adequate data to assess the effectiveness of these efforts. The report recommends that the VA should develop a plan to collect and analyze data on the health outcomes of veterans with service-connected conditions.
In summary, the report highlights several areas where the VA can improve its disability compensation program for veterans, including collecting and analyzing data on the health outcomes of veterans with service-connette conditions, clarifying the knowledge, skills, and abilities required for claims processors to determine when to reevaluate veterans' service-connected conditions, developing a plan to provide additional training to claims processors on the reevaluation process, and ensuring that claims processors are applying the rating criteria consistently.
Continued on next page
27

---

Table 5 Continued from previous page
Input length
Mesa- Mesa-Extrapplation generate summary texts within 1000 tokens
11k
The main content of the report the analysis of the fiscal pressures faced by state and local governments the United States. The report highlights several areas of concern, including:
1. Revenue growth:
The report notes that state and local governments have seen a slowdown in revenue growth recent years, which could lead fiscal pressures.
2. Expenditure growth: The report also highlights the growing expenditures areas such as healthcare, education, and infrastructure, which could put pressure state and local government budgets.
3. Federal policy: The report notes that federal policies, such as the Tax Cuts and Jobs Act, could have significant impact on state and local government fiscal pressures.
4. Natural disasters:
The report notes that natural disasters, such as hurricanes and wildfires, can have significant impact on state and local government budgets. particularly in terms of increased spending emergency response and recovery efforts.
5. Debt: The report notes that state and local governments have increased their debt levels in recent years, which could lead to fiscal pressures in the future. 6. Pension obligations: The report highlights the growing pension obligations faced by state and local governments, which could put pressure their budgets in the future.
7. Infrastructure: The report notes that state and local governments face signifi- cant infrastructure needs, particularly in areas such as transportation and water treatment, which could put pressure their budgets.
8. Reonomic uncertainty: The report notes that economic uncertainty, such the impact the COVID-19 pandemic, can have a significant impact on state and local government revenues and expenditures.
The report also provides data the trends in state and local government revenues and expenditures, including the growth of Medicaid spending and the impact of federal policy on state and local government fiscal pressures. It also highlights the challenges faced by state and local governments in terms of natural disasters, debt, pension obligations, and infrastructure needs. Finally, it notes the potential impact of cconomic uncertainty state and local government revenues and expenditures.
Table 5 shows that Mesa- Extrapxxtraoonttion adeptly and systematically summarizes key points one by one across various imput lengths. It showcases logical coherence and demonstrates commendable summarization capabilities. It's worth noting that the initial symbols used for sub-items beneath each summary vary, including symbols such as "*" "first, second,..." "..... or the number "1, 2, ...", etc. We attribute this variability to the inherent content of the input text. LLM follows the expression format of the text itself and generates corresponding output. Additionally, Mesa-Extrin desa-Extrapolation accurately incorporates punctuation and exhibits an automatic stopping mechanism for proper stopping.
C.9 Evaluation of Phi-3-mini-1288: 128k-instruct Model on Ruler Datasets
We further conducted experimental validation on the Ruler datasets Hsieh et al. (2024), focusing on the single-keys NIAH task. The needle-in-a-haystacl (NIAH) test assesses the ability to retrieve specific piece of information (the "needle") from long distractor texts (the "haystack").
In this experiment, we employed the microsoft/Phi---minn- 128--minii--8------ -28k-instruct model, which has practical value real-world applications and is officially claimed to support extrapolation lengths of up to 128k tokens. To evaluate performance, we gradually increased the input length by 32k increments, comparing the original model's 's results with those achieved using our Mesa-Extrapolatin method.
As shown in Figure 10 the original Phi-3-mini- 1iii--18kk-nnttt official limit of 128k tokens, beyond which fails. contrast, when utilizing the Mesa-extrapolation method, the model successfully extrapolates to at least 192k tokens. It's important to note that this 192k limit is due to our current hardware resource constraints attempting to extend beyond this length results in out-of-memooy error.
model can only extrapolate up to its
28

---

10
Accuracy
Origin
00
MisisExtrrppllation
32k
6/x
160k
192K
Token Longth
Figure 10: NIAH Task Phi-3-mini- 128k-instruct model using Origin and Mesa- Mesap-xxtraoolttionn
D Background
D.1 Preliminary
In this section, we lay the groundwork and introduce the notation for below theorem analysis. Bold letters typically denote vectors or matrices, while normal letters represent sealars. We mainly follow Kazemnejad al. (2023) to define these notations.
Let fe decoder-only Transformer model, where denotes the model parameters. fo processes the input sequence [< bos >, ,., Fr) by applying series of layers, where < bos represents the first token Tokenizer transformation.
Each layer 1, consisting of self-attention heads and feed-forward sub-layer, produces the hidden state H' at layer I, after reading the previous hidden state (1-1)
Each head is parameterized by query W key W K value W and output W matrices, where m represents the attention head index, and W WK. W Raxd and W E Rddx model's 's hidden state size and is the attention dimension (h #heads) Note that we drop the attention head index where it is clear from the context.
The Transformer layer TLayer (t-1)) consist of self-attention heads and forw-forward sub-layer, and input the previous hidden state ((I-1), and generate the hidden state H layer is the layer index, and 8 is the set of parameters of the 1-th layer. Each hidden state H (T+((++))
a matrix, and (?) denotes its hidden state at column f, i.c. at position t.
Each feed-fore forward sub-layer FF is parameterized by Wi. W2 Rdxk.d matrices, where k denotes multiplier of the hidden state size in this sub-layer, and is usually set to 4 in common implementations of the Transformer.
The Transformer layer TLayer processes each column ( independently and parallel to generate the output. The computation of the t-th column of H as follows:
h (F()(a; + h ((-1)) + + h (111)
where À is layer normalization, and E Rd is the output of the multi-head self-attention sub-layer at position t. ag is computed as:
a₂ Σ Attn (m) (n) (1 H
(5)
where Attn (m) denotes the m-th attention head. Let o, E Rd denote the output of an attention head position I. Then, o, is computed as:
o, = WW
Σ a
(6)
i5t
29

---

where á = softmax(() E ()(++)), and a is the attention weight vector such that:
a = ko), (qt, k1), ...., (gc. ke))"
where 7r- = Wohe
(1-1) (1-1) E ERA, k; = W ( E IR" and (..)) denotes the dot product operation.
(-1)
The ford-forward sub-layer (.(() E IR is two-layer MLP as below:
FF(x) = xx)
(8)
where a is a non-linear activation function function(usuallly ReLU or Genu/Hendryyks & Gimpel (2016), and a E Rd layer normalization Ba et al. 2016). It's worthy noted that the additive view of attention heads Elhage et al. (2021) in (5 is mathematically equivalent with the view of concatenate and multiple Vaswani et al. (017). The additive view is easier understand and analyze.
The hidden state H (0) is initialized with learned embedding of the input sequence X, i... H WEX, where Wg E R2dV is the embedding matrix and X E gVx(++1 is the one-hot encoded input sequence. V is the vocabulary size.
D.2 NoPE & PE
NoPE We emphasize here that NoPE generally refers to these architectures that do not use position encoding components remove the position encoding schemas, which is reflected in the attention dot product operation and formally expressed as:
(q: k2) = q T k;
For PE, this generally refers to position encoding components, including Alibi, Rope, APE, etc. Their main difference from NoPE can be reflected in the attention dot product operation.
PE
For ALiBi Press al. (2021), takes the form:
(qe. k;) = q. k; (t (t-1) i) C(m+1)
(10)
where m head index and C a constant defined as:
C = 2 2- logg (#hhade+3))
(11)
For example, if the number of heads is 8, we have 2 22
25
For RoPE Su et al. (2023), it's relative PE that applies rotation to the query and key representations based on their absolute positions before dot product attention. We formulate RoPE for model
dimension d 2, and its dot product as below:
(qt, k;) = qe R(i-t)kk;
(12)
where R is a rotation matrix that rotates (i t)0 radians:
coo((1 t)0) sin (i t)Ø)
sin( (i t)0) cos((i t)0)
(13)
For 2, RoPE applies the same approach on every two consecutive dimensions qe and k;, but with different angles.
For other PE methods, we recommend readers to consult the corresponding papers.
E
Proofs
We provide proof about Theorems 3.1
3.2
and Corollary
4. Our proofs are inspired by
Kazemnejad al. (2023) Weiss al. (2021) ) Lindner et al.) (2023) relies on the causal attention
mask in the decoder-only Transformer and the SoftMax function.
Please refer Appendix D for some necessary background knowledge.
Theorem E. (NoPE Extrapolation). Let x. = [< bos >, 41 -1,.... #r) be an input sequence of length T + 1 to the model. Then, there exists Wa. W K, Wy, Wo. W, and W, matrices, such that when T < M, >> H.; and when T > M, or < H.
30

---

dx(T-1) Proof. Our proof only specifies the weights of a single attention head in the first layer. In this parameterization. we only require the first three dimensions of the hidden states and regard the third dimension as the specific dimension. As for the remaining heads, they can be arbitrary as long as they don't override the first three dimensions. This doesn't pose any challenges, considering that Transformers used in practice usually have a very large model dimension d.
First, we construct the word embedding matrix WE gdxV where each column the embedding of token in the vocabulary. We construct WE such that it always sets the first dimension of every
embedding vector be 1, and sets the second dimension to 0 except the token bos >. We always assume < bos > is the first token in the vocabulary, i.e. the first column. Then, we have:
1
1
0
0
0
WE
(14)
64,1
64,2
64,3
C4,V
Cd,1
6,22
Cd
CdV
dxV
where Ed,; E R.
Then, we use the word embedding matrix WE to compute the embedding ())
1
0
0
0
0
0
0
H WEX-
(15)
64,1
64,2
64,3
64,7+1
Ed,1
6d.2
6d,3
Second, for head dimensions h 2 1, we construct the weights WK. Wv. Wo of the first attention head in the first layer. We can be any arbitrary matrix. Specifically,
0
0
M
07
1
0
H
0
-1
W K
Wv
0
0
0
W
hxd
hxd
dxc (16)
WR k reads from the first dimension of the hidden state. Since all word embeddings have 1 in their first dimension, this parameterization will result all key vectors to be the same. Considering
k W Wghh h then:
k
K2
KT+1
(17)
hx1
hx1
hx1
We Wa to compute the query vector qi by applying q: Woh (0),
qe = [qn, 92, 92..... g
(18)
where q E2 can take any arbitrary value.
Next, we compute the attention weight vectors a::
= [gg,, k1), (qr, k2). k.
(19)
= Ja", a" :..., a.."
(20)
31

---

where a" = 91 92 + ..... 9h-
Then, apply SoftMax to compute the attention weight score. Since all a* are the same, have:
á SoftMax (a) = 1 1
(21)
Now, we compute the value vectors by applying 8,
M
0
H
- H
- H
U1
02
12
(22)
hx1
1x1
hx1
Then, we compute the attention value:
Σ a
Σ
M
H H.... . 00T
(23)
Finally, we compute the output of the attention head by applying Wo:
M
O2 Wo
Σ iS!
dr = =,000,
1 1 H.
0,* 0
(24)
From Equ 24 it can be observed that when & < M, the hidden state value on the third dimension greater than indicating a successful extrapolation. Conversely, when & M, the hidden state value the third dimension is less than H. indicating failed extrapolation.
Next, we provide the proof for Theorem 3.2 as below:
Theorem E.2 (PE Extrapolation). Let x = [ bos >, IIT be an input sequence of length T+1 the model. Consider an simple relative PE schema where dot product between query and key k; at positions t and (t 2 i) can be expressed as: (ge, k.) == q k; (t i). Then, there exists Wq. q. WK. K. Wv. Wo. WT. and W₂ matrices, such that when T M, > H: and when T > M, or < H.
specific dimension. And there is threshold in this dimension the second layer. Our proof construct the matrices on the first two layers. The first layer used to extract position information. The second layer will generate significant hidden state value in its third dimension. If the input length exceeds the max training length, the hidden state value will exceed the threshold.
Proof. We regard the third dimension
(1)Consider the first layer operation.
First, following Theorem E. we construct the same word embedding matrix WE.
For head dimensions 3, construct the weights Wx and Wy for the first attention head in the first layer. We still can be any arbitrary matrix. Specifically,
07
0
0
0
WK
W
(25)
Axd
hxd
Since the elements in W all O, by applying k;
Wx (0)
we have:
0
0
k
22
KT
(26)
:
Ax1
Ax1
32

---

We use Wi to compute the query vector q: by applying q. Wohi? (0)
qt [1) 42, ... 9n.]"
(27)
where 4j E I can take any arbitrary value.
Next, we compute the attention weight vectors a. Consider q. k; = 0 and position information and we have:
= (- 1), -(t 0}
(28)
Then, apply SoftMax a, have:
â SoftMax(a) =1- (0-1) (t-1) (t-2)
e i
(29)
S
S
where define S(1) Ej= We adopt its abbreviation S. Now, we compute the value vectors by applying Wvh: (0)
0
01
U2
(30)
Then, we compute the attention value:
(t-1))
(1-1)
Σ
5 01 =
0, .,...,0' 0)"
(31)
i
After that, we compute the output of the attention head by applying Wo (using the same construction as in Theorem E.I.
(-(1-)
o, Wo
Ea.us = =00,, 15t
aiv
S ...., 0
(32)
Then, E -1-1) can be regarded monotonically decreasing function of Then through the ML. feedforward layer, always let the MLP layer recover the value of Therefore, we can get that:
1
1
1
0
1
2
3
T+1
1
H (=1)
(33)
64,1
61,2
61,3
61,7+1
Ed.1
6d.2
64.3
eaT++ dx(T+1)
where position information is embedded in the third dimension of hidden state. (2)Consider the second layer operation.
For head dimension h 2 3, we construct the weights We and Wx for the first attention head in the second layer. Wr follows the Theorem 3.1 setting. Specifically,
0
0
0 0
0
1
0 -1
O
W Q
Q4,1
Q4,2
04.3
q4.d
W
K
0
0
0
(34)
9h.1
4h.2
(h.3
[r.d]
hxd
33

---

Then, by applying q.
W we have:
(0)
0
1
T +
1
Q1
Q4
.2
94
9r+11
94
(35)
[gh_
hx1
[4h
hx1
qh
hx1
where qj can be arbitrary value for j 2 4. By applying
Wxh;
(0)
have:
-1
-2
(T
h1
l0
kr+1
(36)
1x1
1x1
Then, we have:
L k4
Σ
gj + (t
(37)
4<=j<=h
Next, according to the PE definition, apply the position information t and i to the dot production, have:
(q:. k.)
9j 4<=j<=b
Σ
which means (gt, kz) = (gt, ki) for any / + i. Then, we know that,
a = aa a a"..," a''
(38)
where a² EAsise t5-
Then, apply SoftMax to a. we have:
à SoftMMa .1
(39)
Next, follow same process Equ. second layer. It shows the limitation of extraordinary for position encoding.
in Theorem E. we can get same result in the
Next, we provide the proof for Theorem 3.3 as below:
Theorem E.3 (Weave PE Extrapolation). Let N be positive constant. Consider simple weave PE extrapolation schema: when
N, W(t = i; and when N,
Wit - i) = N. Then, the attention dot product is fixed as below:
(q:, ki) = {
q k. (t i)
t-i<N t-i2N
qik: k. -
where N & M. Then, applying WQ. WK. Wv, Wo. W,, and W2 matrices from Theorem we have when M. or H.
3.2
We completely adopt the LLM setting by Theorem 3.2 and only modify the representation of the relative position. The purpose is to illustrate that effective extrapolation beyond the maximum window length can be achieved only by rearranging the relative position.
Proof. Our proof is closely related to Theorem 3.2
Following Theorem E.2
get H (0)
34

---

Then, compute the attention weight vectors a. Consider q: k; and position information t and i.
By applying this Extrapolation schema, we have:
a I-N, -N,-N, ........ -1,0 [- N)). -tt -1,00
(40)
(41)
Follow Eqs 28 and 29 and apply SoftMax to at, we have:
â SoftMax((a) = - (t-((t-)) (t--((-N
1
(42)
S#
S#
S#
where N and define S* there is no confusion.
N 1-11 e + (t N)e Σ==0
We adopt the abbreviation S# where
Then, compute value vector by applying v; = W still have:
0
0
11
(43)
Then, compute the attention value:
(t-r-(t-N)
(t-((tt-N)
Σ
-
U1
.0, .O.....''
07
(44)
S#
S#
After that, compute the output of the attention head by applying Wo:
6 = 10,0, (1-((())
O, = Wo
Σ
0)²
(45)
S#
i
Notice that we set the MLP feed-forward process simulate piecewise function about (t-1)
S(B)
which produce Integer recover the position.
u et- (0-00-M) N))
S(N+1) And the (1-1-N)
(0- (1)
Considering t >> N,, we know
function
S(t)
S#(()
S#(()
((-((N)))
decreases extremely slowly as increases, almost equal to S(N-1)
(1-1)
At the same time, the S(O) function decreases very quickly when is relatively small; As increases, also decreases extremely slowly.
Combining the characteristies of these two functions, we can always choose a relatively small to
c-t--(t-N)) passing through
keep it away from M (that is N & M), that the value recovered after S# -(t-itt-))
MI.P process is around + 1, because S(N+1) can recover N + and (t- almost (((t((e-N) equal to S(N+1) For the sake of simplicity, considering the rounding characteristics of piecewise functions, we might as well set
(=(()
( N))
S*(() to recover + 1.
Therefore, we can get the hidden state like that:
1
1
1
1
0
1
2
N ++
N +1
(1=1)
(46)
C1,1
64,2
64,3
64,4+1
Cd.1
6a.2
6a.3
CaT++
4x(T+1)
Continue the second layer operations.
35

---

By applying Woh (0)
we have:
0
0
1
2
N
+
Q1
Q4
94
[((2N) =
94
(47)
_hh
where qj can be arbitrary value for 4.
By applying k;
wx-h; (0)
we have:
0
0
0
0
-2
-(N+ +1)
k
k2
(((NN)
(48)
Then, consider t >> N, and apply Extrapolation. when f - i< N.
(q. k.) Sraill - -i) Σ
4j -1-11-1 (1-
(49)
45/5h
when f f- i2 N and N.
(gts k.) - St (1-
Σ 0j N
(50)
4SjSh
when - 1 N and <= N,
(q,, k.) frel(t - i)=
Σ
qj (N + 1- N
(51)
45
Let Eisish We can get the attention score:
N. (N 1),
1, 0
(52)
first- ppart
second - part
third part
where third-pari -part represents Equ 49 second-pas represents Equ 50 and first part represents ET
Apply SoftMax to a, we can get that:
á = SoftMax(a) = [di, ...,..,,dd. d,)"
(53)
Since the first element of is the maximum value, di must be greater than 1.
Next, similar process, we compute the value vectors by applying v, = Wyh (0)
M
0
1
H
1 - H
- H
01 =
U/ =
81
(54)
:
0
Then, we compute the attention value:
Σ
a.v; [ái M, H. 0
0
(55)
36

---

Then, we compute the output of the attention head by applying Wo:
Wo
Σ d:v: 1
10,0, M 1,...,0' 0]z
(56)
When >> M, due to di 1. it's possible satisfy di M condition, such that the hidden state value in the third dimension is greater than H.
L
We conjecture that while the attention mechanism in RoPE Su al. 2023 involves multiplying by the rotation matrix of the relative position, it's essential to acknowledg that neural networks possess the capability model any function. This implies the potential to decompose the relative position information into an additive form, as exemplified our extrapolation scheme detailed Theorem
3
Next, we provide the proof for Corollary as below:
Corollary E,4 (Mesa Extrapolation). Let N be a positive constant. Consider simple Stair PE extrupolation schema, and the attention dot product is fixed as:
(g k.) fetairre It, ki, -)) q.
(t it
t-i<N t-i2N
q k.
where N & M, 1 = N - and the extrapolated width F, is constant. Then, Apply Although T M. it still
Wº. WK. Wy. Wo. W1, and W2 matrices from Theorem 3.2
OT H.
Proof. Due to the striking similarity between Stair PE and the positional arrangement scheme
proposed in Theorem 3.3 the proof process largely mirrors Theorem 3.3 Following the proof
structure of Theorem 3.3 the first layer, according to Equ(45 and 46
obtain the hidden state
matrix as follows:
1
1
1
0
1
IN
Ir+1
H
(57)
64,1
64,2
C4,N
64.7+1
6d,1
6d,2
Ed,N
Ea.T+
(x(++1)
where 7 is defined on Stair PE extrapolation schema. In the proof of the second layer, still get the similar result like Equ 52
below:
α 0,
T C.
first part
C,
N -1
second ppart.
repeat-pare -part
(58)
N --
third
1,
fourth-pars
where C is a constant, and each element within repeat-part is smaller than 7
Apply SoftMax to a, we can get that:
â SoftMax((a) = [di, dq . a.,"
(59)
37

---

which also shows that the first element of a is the maximum value and ái must be greater than 1. Consequently, following Equ(56] we reach the same conclusion.
F Probe Experiment Visualization
We hypothesize that when the input length surpasses the effective window length the model, some dimensions' values in the exceeded positions will experience jump as the position changes.
To investigate this jump phenomenon's 's correlation with extrapolation failure, we design the following experiment: we adopt a standardized input by repeating the word "hello" 8000 times, resulting in 8001 tokens (automatically fill in initial token) after tokenization. For more accurate explanation, we take the LLaMA2-7B-Chi model and list the sequences converted by the tokenizer, as follows:
tokens = [1, 11,22122...... 22172]
where 1 denotes the initial token < bos >, and 22172 denotes the word "hello". It's noted that the initial token < bos > is filled in automatically.
F1 Normal Case
We input this token sequence into the model and observe the hidden state. We focus on the hidden states produced by the first 11 layers, specifically selecting the position intervals from 4000 to 5000 and the last 1000 positions. We then concatenated the hidden states from these two intervals. This selection was deliberate, considering that the LLaMA2-7B implying the effective input window is in proximity to this location.
model's training length 4096,
Following this, we created a matrix graph, yielding the following results Fig 11
Origin with normal input token visualization on LLaMAA-7B- BB-hhat model for position regions between (4000-5000, 7000-8000 800-)000) for first 11 layers. X-axis represent positions, which correspond position regions between 4000-5000 and 7000-8000 Y-axis represent Dimentions from first 0-th to first 640-th -h. Some observation: noticeable color jumps in most dimensions position changes.
Figure 11:
In Fig I1 the X-axis denotes the position of the input token, ranging from 0 to 1000, representing tokens at positions 4000 to 5000. The scale of 1000-2000 represents tokens at positions 7001 to 8001. The Y-axis signifies the token dimension, ranging from small to large. The LLaMA2-7BB --aaaat model has a total of 4096 dimensions, and we display the first 640 dimensions in Y-axis. Red color means greater than 0. and blue color means less than O. Fig shows some noticeable jump from 0-th to 640-th dimensions, especially at the 1000 scale for the original model.
F.2 Extrapolation Case
Given the effectiveness of the extrapolation method ReRoPE in extending to lengths of up to 8k, we apply to the LLaMA2-7B-66 Case settings, the results are follows:
model. Employing the same conditions as those in the Normal
In Fig 12 obvious jumping phenomenon successfully suppressed. can be seen that each dimension at different positions
still maintains consistent values. This illustrates that by suppressing sudden changes the values of these dimensions, extrapolation can be made successful even outside the effective window length.
38

---

Figure 12: ReRoPE with normal input tokens visualization a. model for regions between (4000-5000, 7000-8000) for first 11 layers. X-axis represent positions, which correspond position regions hetween 4000-5000 and 7000-8000. Y-axis represent Dimentions from first 0-th to first 640-th. Ohservation: Each dimension stays consistently each position
Overall, comparing Normal Case and Extrapolation Case again, it shows that using the extrapolation method can suppress mutations in dimensions, thereby making the extrapolation successful.
Additionally, for layers 0 and 1, the hidden state values of different positions in each dimension are nearly identical. According our Theorem 3.2, layer 1 may extract position information, while subsequent layers determine distances beyond the effective window, generating a positive or negative jump signal. We speculate that this signal change may not be strictly positive negative, but there is a threshold. When the signal exceeds the threshold, the extrapolation will fail; when the signal does not exceed the threshold, the extrapolation will be successful.
also use the LLaMA-3B model and the Vicuna- 13B model compare and demonstrate effects of using Origin and ReRoPE, follows below Fig 15 and [6
F.3 Validating extrapolation using observed thresholds
We continue our probe experiments using the "hello", and input sequences is up 16000 tokens. These were validated on the LLaMA2-7B-OC model. Given that the hidden state in LLaMA2 has a total of 4096 dimensions, main text, we present the prediction results for the first and 6-th dimensions. The results for the 7-th and 9-th dimensions shown in Figure B
selected the first 20 dimensions search observable thresholds, In the
Layer:1 Dimendon:7
Layen2. Dimerdio:77
Lave:1 Dimenslon:3
Layen2. Dimenciona
0.-
84-
26
34
11K
5x
14k
26
5x
11k
14k
26
11k
14k
Orig
DynamicKTK
Postion
Figure 13: Thresholds for hidden states observed specific dimensions LLaMA2-7B -B-hat, allowing for extrapolative judgments hased on these thresholds. The red dashed denotes the observed threshold, while the green dashed line indicates the position of extrapolation failure for the Dynamic-NTK based on the observed threshold, The black dashed line indicates the maximum training length of the model.
Figure 1 also shows the same results as Figure in the main text. When the length the input sequence around 12k, the hidden state values of Dynamic-NTK in the 7-th and 9-th dimensions surpass the thresholds, implying extrapolation failure. Due to not outside the thresholds, ReRoPE shows successful extrapolation.
Our experiments also reveal that not every dimension exhibits clear threshold. Considering that the Transformer model is type of neural network, we hypothesize that these dimensions with threshold undergo significant signal changes due the characteristics of activation functions. These changes amplified through successive layers, eventually leading to model output failures. We believe
39

---

this internal mechanism explains why observable thresholds can predict the success or failure of extrapolation.
We also validate our findings using the Vicuna-133 model, and the results are shown in Figure
Layer Dinension:
Layer Dinercinn
Liyer1 Dirercion
Layer 4. Dinsersoo 10
2.00
56 11K
14C
28
54
14k
25
25
338
141
36
36
OVion
Tokan Ponkion
Figure 14: Thresholds for hidden states observed specific dimensions Vicuna- allowing for extrapola- tive judgments based on these thresholds. The red dashed line denotes the observed threshold, while the green dashed line indicates the position of extrapolation failure for the Dynamic-NTK based on the observed threshold. The black dashed line indicates the maximum training length of the model.
Figure 14 shows the hidden state value on the specific 4-th and 10-th dimensions. Similar to the observations with LLaMA2-7B-Chal model, we find no significant differences for the hidden state values at the first layer. However, substantial differences are observed at the fourth layer. Based on these observed thresholds, we can predict that Dynamic-NTK will fail extrapolate when the input length approaches around 9k. Conversely, ReRoPE can extrapolate further. These predictions align well with our subsequent experiments, further validating the feasibility of using observed thresholds to determine extrapolation success.
model, we observed threshold phenomena at the fourth layer in the Vicuna- 13B model. We hypothesize that although our theoretical model predicts the threshold to occur the second layer, considering the integration of positional information from preceding layers, this still aligns with our theoretical framework.
In contrast to LLaMA2-7B-CC
G Stair PE and Self-Extend
The formulation of Self-Extend is as follows:
Let t denote the position query, denote the position of key, denote the position of key, W denote the neighbor size and G' denote group size.
According to its equation 3 in Self-Extend (Jin et al. (0044)) P P P// G, and the shifted relative position (W- W // G), we can get the position of query as:
t /// -
and the position of key
i//G
By RoPE, their relative position between and i (consider i), is remapped to:
t/ h//C/N/Ww//6////...//////////
It's worthy noting that only under the necessary and sufficient condition (t mod G >= i mod G), we get that
G/G-ii// (t- //G
Next, when W mod G == 0, the equation of Self-Extend becomes:
40

---

W W-ttD//G-W//G-W--t----
If we adjust this flooring operation to ceiling operation, and replace N with W and E with G, then Stair-PE is equivalent to Self-Extend.
In summary, under conditions mod G > i mod G and W mod G = 0. as well as changing the flooring operation ceiling operartion in Self-Extend, these two formulas are equivalent. Except for this condition, they yield slightly different results.
Note because W and G' constants, the condition W mod G = 0 be met easily. But i and t change with positions, therefore there will always be positions where the condition t mod G > i mod G is not satisfied.
For example, 10, 5, G 2, but 10 //2 5 //2 * (10 5) //2
41

---

(a) Visualization Hidden states with Origin Model for the first 11 layers and the first 640 dimensions. Observation: noticcable color jumps in most dimensions as position changes, especially at a-axis 1000.
100
(b) Visualization Hidden states ReRoPE for the 11 layers and first dimensions. Observation: Each dimension stays consistently at each position
Figure 15: Visualization of Origin and ReRoPE probe on LLaMA-3B model for position regions between (2000-3000, 4000-5000)
(a) Visualization Hidden states with Origin Model the first 11 layers and the first 640 dimensions. Obscrvation: noticeable color jumps in most dimensions as position changes, especially at X-aixs 1000.
(b) Visualization of Hidden states with ReRoPE for the first 11 layers and the first 640 dimensions. Observation: Each dimension stays nearly same without color jump as position changes.
Figure 16: Visualization of Origin and ReRoPE probe the Vicuna- 13B model for position regions between (2000-3000, 4000-5000)
42

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction of our paper accurately reflect its contribution and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations on Section Discussion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
43

---

Answer: [Yes]
Justification:
We give full proof Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We disclose all the needed information.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
44

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We provide code and data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttde//guuddeeeeeSouuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify all the training and test details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We provide detailed explanations about report.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
45

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the hardware and software information about experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///aaaappppcppo/oo//cccaaaa
Answer: [Yes]
Justification:
We follow the NIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification:
We discuss impacts on section Discussion.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
46

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We follow the license and terms.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
47

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We don't release assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
48


Reviews:
[{"review_id": "vMxATPOc3A", "reviewer": "Reviewer_LfLf", "summary": "The authors propose a weave position encoding method to enhance LLMs’ inference performance when the input context window exceeds the training context window. This method can be integrated into existing pretrained LLMs without additional finetuning. To support their findings, the authors conducted theoretical analyses on the failure reasons of various position encoding methods, including those without position encodings. They demonstrate that the significant shift in the hidden state’s value range, when input token positions exceed the maximum context length, is the cause of this phenomenon.", "questions": "The caption for Figure 1 is not sufficiently informative.\n\nAdditionally, it is unclear how the failure of an LLM is measured in Section 3.4 and Figure 2. \n\nThe experiments visualizing hidden state values in Figure 2 would have been more effective if conducted on the same task and with the same setup as Figure 3. This alignment would allow for a clearer connection between the findings in Figures 2 and 3.\n\nminor typos:\n\nTheorem 3.2: an simple -> a simple\n\nLine 161: defer to -> refer to\n\nLine 242-243: a significant disruptions", "limitations": "The authors have included a limitations section; however, it reads more like a discussion of future work rather than addressing the actual limitations of the current study.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "One of the strengths of the proposed method is that it can be integrated into existing pretrained LLMs without requiring any additional finetuning. This makes the method highly practical and easy to implement, saving both time and computational resources.\n\nThe method has demonstrated excellent performance in pass key retrieval tasks, showcasing its effectiveness in real-world applications. This indicates that the proposed approach not only works in theory but also delivers tangible improvements in practical scenarios.\n\nThe authors have conducted comprehensive theoretical analyses to understand the failure reasons of various position encoding methods, including those without position encodings. This thorough investigation provides a solid foundation for the proposed method and enhances its credibility", "weaknesses": "The proposed position encoding method, while promising, does not consistently improve performance across different tasks. This inconsistency suggests that the method may not be universally applicable or reliable in every context, potentially limiting its overall utility. \n\nAdditionally, the main narrative of the paper emphasizes the method’s ability to handle extrapolation beyond the training context window. However, given the observed variability in improvements, it would be more accurate to adjust the claims to better reflect the method’s performance, providing a more balanced and realistic presentation of the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your work.\n\n## weakness\nThank you for your suggestions. Our method shows good extrapolation performance on accuracy-related tasks, but we observe slight variability in extrapolation performance within mid-length (8k-11k) in the summary task. We will adjust our claims accordingly in the final version.\n\n## Q1\nIllustration of Mesa-Extrapolation. The left figure shows the Chunk-based triangular attention matrix (before SoftMax operation) of Mesa-Extrapolation while a sequence of length 13 is fed into an LLM. The right figure shows an example of PE and Stair PE. The Stair PE is used to weave the relative position equipped by Mesa-Extrapolation.\n\n\n## Q2\nIn sec 3.4, we designed a probe experiment by repeating a word (e.g. “hello”) N times as input to the model, where N is the input length (the details are provided in Appendix, line 1206-1209). The reason for designing the probe this way is to eliminate the influence of different tokens since both of the input token and its position affect the hidden state values.\n \nIn Figure 2, we use a vertical black dashed line to indicate the position of maximum training length of the model. In this case, it is 4k for llama2-7b-chat model. The hidden state value at this position is designated as the observed threshold and marked with a horizontal red dashed line. When the hidden state value exceeds the red dashed line as the position changes, it signifies that the hidden state value has surpassed the threshold, **suggesting a failure in extrapolation** after that position. We will add these explanations to the final version.\n\n## Q3\nWe used a different experimental setup primarily for the following reasons:\nFigure 2 examines extrapolation failures, which primarily occur when input length surpasses the maximum limit, irrespective of the underlying task. Using the \"hello\" probe can clearly help us analyze the relationship between position and the corresponding thresholds. We then verify these predictions with other tasks, such as those depicted in Figure 3 or language modeling tasks shown in Figure 4. The results indicate that the threshold observed aligns with the results from the passkey task and language modeling task, demonstrating the effectiveness of the theory we developed.\n\nNevertheless, we added additional results visualizing hidden state values using the same task and with the same setup as Figure 3 (see Fig 8 in attached PDF ).\n\n## Q4\nThanks. We fixed these typos.\n\n\n## Limitations\nDue to limitations of resources, we have not yet validated our method at longer lengths. For instance, we have verified that phi3-mini-128k model can be extrapolated to at least 192k with our method. Beyond this length, memory crashes occur.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n2N3eksheo", "reviewer": "Reviewer_hjGM", "summary": "This paper introduces a new LLM length extrapolation method, called Mesa-extrapolation, which utilizes a chunk-based triangular attention matrix and applies stair PE. The proposed method is based on theoretical analysis. The paper conducts extensive experiments on passkey, PPL, summarization to demonstrate the effectiveness.", "questions": "1. Length extrapolation is a necessary technique, but the current extrapolation length is very limited. Considering that there are already many models that have undergone long context window extension, such as phi3-mini-128k, can your proposed method continue to perform length extrapolation on these long context LLMs? If so, it will significantly enhance the impact of your method\n\n2. If I understand correctly, the proposed method is mainly for those with PE. Why is there a need to prove NoPE? Is NoPE your baseline?\n\n3. The proposed Mesa-extrapolation is somehow similar as a variant of \"sliding window attention + attention sinks\". Could the author explain why mesa-extrapolation is theoretically superior compared to sliding window attention and attention sinks?", "limitations": "See the weakness and question sections.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a theoretical analysis to prove the effectiveness of meticulous weave position with PE for length extrapolation.\n2. The proposed method is efficient and is proved to be effective through extensive experiments.", "weaknesses": "1. The passkey retrieval experiment is simple, good performance on the passkey is far from a real usable context window. Please consider to add evaluations on Ruler[1] and RepoQA[2]\n\n2. The achieved context window is limited. \n\n\n\n[1] https://arxiv.org/abs/2404.06654\n\n[2] https://evalplus.github.io/repoqa.html", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your work.\n\n## Weakness 1:\n\nWe add evaluations on Ruler, and the results are available in the uploaded PDF (see Fig 1, 2 and 4). These results indicate that our method also performs well.\n\n## Q1 & weakness 2:\nWe perform experiments on long context window \"microsoft/Phi-3-mini-128k-instruct\" model using Ruler dataset. The results show that our method can further extrapolate to 192k, indicating the effectiveness of our method. We show it in the uploaded PDF (see Fig 4).\n\nDue to the inherent limitations of the phi3-mini-128k-instruct model itself when handling this task, even within a 128k window, the phi-3 model does not achieve 100% accuracy as shown in the right-side of Fig 4. Our method effectively extends its window based on the original model's capabilities, rather than improving its capability.\n\n## Q2\nAlthough existing LLMs typically incorporate positional encoding (PE) components in their architecture, recent studies have shown that the NoPE (no positional encoding) method may better facilitate the extrapolation capabilities of LLMs. The choice of including or excluding the PE component in a LLM is critical, as it cannot be altered once the model is trained. We believe it is essential to theoretically model the extrapolation performance of both NoPE and PE. We discuss this part in our related work.\n\nDue to a lack of suitable candidates, NoPE was excluded from our baseline. Aside from the 1B-size pre-trained model (Kazemnejad, Amirhossein, et al. \"The impact of positional encoding on length generalization in transformers.\" Advances in Neural Information Processing Systems 36 (2024).), we did not find any other suitable candidates. However, this pre-trained 1B model’s capabilities are very limited, making it difficult for evaluating basic NLP tasks. \n\nAdditionally, by simply incorporating training-free weave PE into a PE-type LLM, we can achieve longer extrapolation. Through these efforts, we hope to demonstrate that choosing weave PE offers more advantages compared to NoPE.\n\n\n\n\n## Q3\n\nMesa-Extrapolation appends all previous tokens at the bottom of its attention matrix, allowing the last token to attend to all preceding tokens. When the input length significantly exceeds the model's maximum training window, it uses Stair PE to reuse positions and reduce errors further. The attention sliding window approach, on the other hand, discards tokens in the middle section. This method restricts the last token's attention to only the head and tail tokens, keeping the total attended token length within the maximum training window and directly using trained positions. This approach sacrifices the information from the middle tokens. In context-based tasks, the middle tokens often contain important information, and losing these tokens can prevent the model from providing accurate responses to user queries.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oDAQcreLt8", "reviewer": "Reviewer_PZAX", "summary": "The paper proposes a positional embedding scheme to address the extrapolation issue: train on short sequences, evaluate on longer sequences. Authors propose a theoretical framing of the positional embeddings contribution to attention. They apply their analysis to NoPE (No Positional Embedding) and to standard PE, and RoPE. They propose the Mesa-Extrapolation idea where input tokens are organized so that attention is paid to nearby tokens and those at other key positions. Authors validate their findings with empirical evidence on several benchmarks and applications.", "questions": "1. Can authors explain the threshold definition: \"When o > H, LLM extrapolates successfully. Once o < H, LLM extrapolation\nfails.\" Is there a typo and inequalities are reversed?\n\n2. In Fig 2, why dim 1 & 6 are of interest?", "limitations": "--", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper is about a very relevant topic which has attracted a lot of attention lately. The paper proposes a simple approach to solve the problem which seems to be easy to adapt to different positional embedding models. Some of the numerical experiments are encouraging.", "weaknesses": "The theory part of the paper is hard to read and I am not sure about its usefulness. Result appear hand-wave-y and vaguely stated. For example the definition of the threshold H in the Assumption is surprising (see questions). Numerically, experiments on language modeling and Summary of Tasks do not seem to show the method's claims.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your work.\n\n## Weakness 1 & question 1: “Theory is hard to read and unclear definition of the threshold H”\n\n**Definition of the extrapolation success or failure:**  When a large model continuously produces valid next-tokens for a given long input sequence, we define this as successful extrapolation. Conversely, if it outputs invalid next-tokens, we refer to this as failed extrapolation. Therefore, the key to extrapolation failure is the output of invalid next-tokens, which is caused by anomalies in the model's output. We speculate that these anomalies arise because certain parts of the model receive input values that exceed their acceptable range.\n\n\n**Definition of the threshold H:**  For convenience in our analysis, we consider the outputs of the preceding layer In a multi-layer neural network, which serves as the input for the next. To ensure normal subsequent outputs, the values from the preceding layer need to remain within a reasonable range. This implies that there must be a bound on these values. We **refer this observable boundary as the threshold H**. This threshold can be either an upper bound or a lower bound. In our work, for the sake of theoretical analysis, we chose the lower bound as our threshold.\n\n\n**Definition of hidden state values o**: the output of each layer in an LLM, which also serve as the input for the next layer. \n\n\nNote that in our assumption, we assume that for specific dimensions in specific layers, there exists an acceptable range of input values (i.e., hidden state values o). The lower bound of this acceptable range serves as our threshold H. By observing whether the hidden state value o in this dimension exceed the threshold H, we can predict whether the large model's extrapolation has failed.\n\n\nWe apologize if it wasn't clear enough. We will add these refined definitions in the final version of the paper.\n\n\n## weakness 2:\n\n\n\nDespite observing minor performance degradation in the 8k-11k token range for summarization tasks, our method consistently exhibits strong extrapolation capabilities across a diverse set of tasks, including passkey retrieval, language modeling, and summarization, as corroborated by Reviewers LfLf and bJoG. \n\nWe also noted that the performance in the 4k-6k range is good. We speculate that with a fixed extrapolation width param (E = 50), the 7k-11k range may spread the model's attention more thinly compared to the 4k-6k range. For the summary task, the model needs to pay closer attention to the dispersed information within the context, which requires a finer extrapolation width to minimize errors. We hypothesize that optimizing the extrapolation width could improve performance in the 7k-11k range. \n\n## Q1\n\nThe inequalities in our Assumption are not reversed since we consider H as the lower bound.\n\nWe will add clear definitions and explanations in the final version.\n\n\n## Q2\n\nDimensions 1 and 6, as well as dimensions 7 and 9 in the appendix (line 1246), were selected from the first 20 dimensions to showcase whether the extrapolation would fail using the observed threshold for NTK and Rerope. Note that different inputs activate different parts. Figure 2 used 'hello' as the probe word. Additionally, we demonstrated that dimensions 14 and 19 can be used to predict extrapolation failures using 'good' as the probe word (please refer to the uploaded PDF in Fig 7 and 8 for more detailed diagrams).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sV1kiiL1Hx", "reviewer": "Reviewer_bJoG", "summary": "This paper studies the length extrapolation of LLMs.\n1. It provides a theoretical analysis of why NoPE and PE fail to extrapolate beyond a certain length. Previous work has shown that this failure is related to the explosion of hidden states as positions increase. This paper demonstrates that both NoPE and PE suffer from this hidden state explosion, using a constructive approach to illustrate the existence of Transformer weights.\n2. It proposes weave PE, a simple adaptation of PE that theoretically addresses the extrapolation issue. It also provides a simple implementation of weave PE, using a chunk-based triangular attention matrix. Then, it demonstrates that the proposed extrapolation scheme matches the performance of prior length extrapolation methods, such as Dynamic-NTK.", "questions": "See Weaknesses.", "limitations": "Well discussed. Extending this approach to fine-tuning would be an interesting next step.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- Great theory explains the failure of NoPE and PE in length extrapolation.\n- Proposes weave PE, derived from the theoretical analysis, which also works well in practice.\n- Shows good empirical results in passkey retrieval, language modeling, and summarization.", "weaknesses": "1. Methodological comparison with $\\Lambda$-Attention\n\nThe proposed Stair PE resembles the $\\Lambda$-attention of LM-Infinite & Streaming-LLM, yet with differences in 1) the additional attention at the bottom, and 2) a different length extrapolation scheme, Meta-Extrapolation. In the experiments, Meta-Extrapolation significantly outperforms LM-Infinite & Streaming-LLM. Could the authors provide the intuition behind these empirical gains?\n\n---\n2. Empirical comparison with Dynamic-NTK\n\nDynamic-NTK outperforms Meta-Extrapolation on the summarization task for mid-lengths of 7-11k, while Meta-Extrapolation shows better performance on summarization for shorter lengths of 4-6k and better language modeling fluency for lengths greater than 11k. Could the authors provide the intuition behind these results?\n\n---\n3. Relation between input sequence length $T$ and effective length $M$\n\nThe theorems only show the existence of an effective length $M$, but do not provide intuition on the scale of $M$, such as the ratio over the input length $M / T$. Could the authors provide some intuition on this? If I understand correctly, $M$ is set from the construction of the Transformer weights, so can it be controlled to an arbitrarily large number?\n\n---\nEditorial comments\n\n- The fonts of the figures and tables are too small. Please make them more readable.\n- Some parts of the writing are mechanical. For example, lines 116-120 do not provide meaningful information. It would be great to discuss the implications of the theorems in natural language. For instance, both theorems state the failure of length extrapolation in NoPE and PE, rather than just \"revealing the internal mechanism of extrapolation.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for recognizing our work and providing your suggestions.\n\n## weakness 1\n\nFor decoder-only architectures, the model's output is based on the next-token prediction. The last token in the input is crucial, as it generates the next token. For the last token to output the correct next token, it must attend to all previous tokens (principle of self-attention mechanism), especially those with critical information.\n\nThe attention matrices used by Streaming-LLM and LM-Infinite both discard middle tokens, inevitably resulting in loss of information from these tokens. This problem becomes severe when the middle tokens carry important information. \n\nOur approach appends all tokens at the bottom, ensuring that information is not lost. For overly long inputs, we use Stair PE to reorganize relative position encoding, maintaining the integrity of the information.\n\n\n\n## weakness 2\n\nWe believe that the inherent capabilities of LLMs set the upper limit for these methods. As the input length increases, especially beyond the maximum training window, errors are bound to accumulate regardless of the method used, which will affect the model's performance.\n\nThe NTK method scales the rotation angle of RoPE positional encoding. We hypothesize that within an 11k input length, the errors introduced by adjusting the rotation angle are acceptable for large models. \n\nFor mesa-extrapolation, we reuse previous trained positions to minimize errors as much as possible. We speculate that with a fixed extrapolation width param (E = 50), the 7k-11k range may spread the model's attention more thinly compared to the 4k-6k range. For the summary task, the model needs to pay closer attention to the dispersed information within the context, which requires a finer extrapolation width to minimize errors. We hypothesize that optimizing the extrapolation width could alleviate or improve performance in the 7k-11k range. \n\n\n## weakness 3\n\nYes, M is set within the Transformer weights we constructed. This M is typically related to the maximum training window length of the model. For example, if the maximum window length for Llama is 2k, then M can be considered as 2k.\n\nTherefore, we think that M can't be controlled to an arbitrarily large number.\n\n\n\n## Editorial comments\nThank you for the modification suggestions. We made corresponding adjustments according to the comments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UzSBA20dDB", "reviewer": "Reviewer_vMAr", "summary": "The paper conducts a theoretical analysis to help understand the No Position Encoding. Also, the paper proposes weave position encoding to achieve improved extrapolation performance without additional cost. Also, the paper introduces the weave PE method, Mesa-Extrapotion, which recalculates the position ID to reduce the gap between training and inference. Finally, the paper conducts experiments to prove the effectiveness of Mesa-Extropoation.", "questions": "Please see the above question and concerns in weakness.", "limitations": "Yes, the authors have addressed the limitations. We may further discuss and analyze the Mesa-Extropolation in other areas.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The presentation of wave PE, Star PE, and Mesa-Extrapolation is clear. The author also provides the details of wave PE, Star PE and Mesa-Extrapolation to help understand the concepts\n* The author conducts experiments to prove the effectiveness of the proposed Mesa-Extrapolation.\n* The author also further analyzes the Latency & Memory Usage of the proposed Mesa-Extropoaltion.\n* The paper discusses the limitations for further discussion.", "weaknesses": "**Major Concerns**: It seems that the proposed method Star PE is the same as Self-Extend LLM [1]. If possible, I sincerely hope that the author can address the following concerns:\n* **Concern 1**: The Figure 1 Star PE implementation result does not match the Equation proposed in Section 4.1 Page 5. In Figure 5, when t-i is 5, the implementation result of Star PE is 4. However, according to the Equation proposed in Section 4.1 Page 5, the implementation result should be N+ $\\lceil (t-i-N)/E \\rceil$=4+$\\lceil (5-4)/2 \\rceil$=5. Hence, to match the implementation result of Figure 1, the Star PE calculation equation should be N+ $\\lfloor (t-i-N)/2 \\rfloor$.\n\n* **Concern 2**: The Equation of Star PE is almost the same as Self-Extend LLM. When t-i is small than N, both Star PE and Self-Extend LLM employ normal relative distance. When t-i is larger or equal to N, we discuss it below.\n   * The Equation of Star PE is N+ $\\lfloor (t-i-N)/E \\rfloor$ (as shown in Figure 1), while N is called the extrapolated position and E is called the extrapolated width, and t-i is the relative distance. \n   * The Equation of Self-Extend LLM is $(t-i)//W + (W- W//G)$=$W+ (t-i)//G - W//G$, while W is called neighbor window size and G is called group size. Apparently, when W%G==0, the Equation of Self-Exntend LLM becomes $W+ (t-i)//G - W//G$=$W+ (t-i-W)//G$= $W+\\lfloor (t-i-W)/G \\rfloor$. Then, we change the notation W to N and the notation G to E, we have N+ $\\lfloor (t-i-N)/E \\rfloor$, which is the same as Star PE.\n* **Concern 3**: If possible, could the author compare the performance between Mesa-Extropolation and Self-Extend LLM?\n* **Concern 4**: when the output sequence length $L_{generate} \\gg L_{input}$, will the time cost also becomes O($L_{generate}^2$)?\n\nBased on the above concerns, the paper may need to rethink the major contribution. The proposed Mesa-Extrapolation seems to make sense and may benefit society, while the paper should clarify its original contribution.\n\n\nReference:\n\n[1] Jin, H., Han, X., Yang, J., Jiang, Z., Liu, Z., Chang, C. Y., ... & Hu, X. (2024). Llm maybe longlm: Self-extend llm context window without tuning. arXiv preprint arXiv:2401.01325.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your work.\n\n\n## major concern\n\nThank you very much for your suggestions. The differences between our method and Self-Extend can be categorized into three aspects:\n\nFirstly, from a **methodological** perspective, our designed Stair PE is not only applicable to RoPE but also to other positional encoding methods, such as ALiBi. Self-Extend is only applied to RoPE. Additionally, Stair PE differs from the self-extend design approach, which involves implementing group attention and standard attention and then merging them through masking. This implies that it requires calculating the attention matrix twice, resulting in higher memory and time overhead. In contrast, our approach uses a chunk-based triangular attention matrix that significantly reduces computational and memory costs. We utilize Stair PE at the base of this chunk-based triangular attention matrix, and for practical applications, approximate methods can be employed to further save memory and reduce time costs.\n\nSecondly, **theoretically**, we provide a theoretical proof for the Weave PE approach, demonstrating that it can achieve extrapolation. In contrast, the self-extend approach only provides experimental evidence without a theoretical explanation.\n\nFinally, from an experimental standpoint, we further conducted comparisons of the two approaches and demonstrated that our method shows comparable advantages with lower memory consumption and inference latency (see attached PDF in Fig 5).\n \n\n\n## concern 1\nWe apologize for not checking it carefully. However, there is no need to modify the formula. We can simply change it to N=3.\n\n\n## concern 2\nWhen we set the Stair PE formula as your derivation on # concern 1, your derivation is correct and aligns with Self-Extend LLM formulation. However, there is a crucial mismatch: **self-extend derives the positional encoding according this formulation just for its query vectors** (please refer to its pseudocode on algorithm 1 on its page 12). \n\nwe briefly list below:\n\n```\ng_pos = pos // g_size # the floor operation\nshift = w_size - w_size // g_size\ns_g_pos = g_pos + shift\ng_q = apply_pos_emcode (q , s_g_pos )\ng_k = apply_pos_emcode (k , g_pos )\n```\n\nIn its code, s_g_pos is correspond to your formula, but it’s not relative position encoding.\n\nNote that Self-Extend is only applied to RoPE positional encoding. Thus, with RoPE, the relative positional encoding is obtained by subtracting the key's positional encoding from the query's positional encoding. In contrast, our defined Stair PE **directly targets the relative positional encoding**. This is also why our Stair PE is more broadly applicable, not only to RoPE but also to other methods like ALiBi, whereas Self-Extend is only applicable to RoPE.\n\nAccording to these formulations, the relative positional encoding implemented by self-extend is different from that implemented by Stair PE. We have provided a clear comparison in the uploaded PDF (see Fig 6 ).   \n\n\n\n## concern 3\n\nThe comparative results are provided in the uploaded PDF(see Fig 1, 2, 3, and 5). \nIn both the NIAH and Passkey tasks (corresponding to Figure 3 in our paper), our method demonstrates comparable advantages. Additionally, our method performs well in terms of memory consumption and inference latency.\n\n\n\n\n\n## concern 4\nThe output of large models is divided into the prefill stage and the decoding stage. The time savings from mesa-extrapolation primarily occur in the prefill stage, which involves processing the N^2 matrix corresponding to the input sequence. During the subsequent token-by-token output process, the time complexity is O(L_generate + L_input ). This mainly concerns the last token and its computation with all preceding tokens, and this complexity is linear with respect to the sequence length.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear reviewers,
  Thank you very much for your review. 
  We have provided additional experimental supplements in the uploaded PDF. 
  Please check it out.

Meta-review: The paper investigates position encoding techniques aimed at addressing the challenge of length extrapolation in Large Language Models (LLMs). The authors present a theoretical analysis of various extrapolation strategies, identifying the limitations of existing methods such as No Position Encoding (NoPE) and simple relative Position Encoding (PE) in extrapolation scenarios. To address these limitations, they propose a novel approach, the weave PE, which is designed to improve extrapolation performance. The theoretical contributions are well-supported by extensive empirical evaluations, offering significant insights and practical methods for improving LLMs.

During the review process, it was noted that the method referred to as "Stair PE" in Section 4.1 is analogous to a prior method known as Self-Extend PE (https://arxiv.org/abs/2401.01325). This issue was thoroughly discussed during the author-reviewer and reviewer-AC interactions. Despite this similarity, the consensus among the reviewers and the AC was that the paper provides substantial value to the research community, even without considering Section 4.1 as a novel approach. Therefore, the paper has been accepted for publication. The authors have been advised to explicitly acknowledge the connection between Stair PE and Self-Extend PE in the final manuscript to ensure clarity and transparency for the readers.

Additionally, the authors are requested to make the following edits: (1) Correct the usage of punctuation. For example, "i.e." in Line 37 should be "i.e.," the period should be placed within quotation marks in Line 52, and each equation should end with appropriate punctuation. (2) Increase the font sizes in some figures, as they are currently too small.
Decision: Accept (poster)