Mesa-Extrapolation: A Weave Position Encoding Method for Enhanced Extrapolation in LLMs

Authors: xin  ma
yang  liu
jingjing  liu
xiaoxu  ma
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 12:36:01

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.

Main paper: 
 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 a serious limitation on applications with long inputs. An naive solution is to 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 of Transformer architecture, to compensate for the overlooking of position information by the attention mechanism. In the realm of extrapolation capability, PE is considered as a key factor influencing the extrapolating ability of LLMs. A few PE approaches, such as the popular RoPE Su et al. (2023) and ALiBi Press et al. (2021) , claim to offer improved extrapolation capabilities and have gained widespread usage in industrial applications. Meanwhile, a counter-narrative 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 a significant role in capturing position information.Inspired by Kazemnejad et al. (2023) , we conduct a 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.e., weave PE), it is feasible to achieve extrapolation beyond the effective window length. We further introduce a novel weave-PE-based method, Mesa-Extrapolation, which demonstrates substantial extrapolation prowess without the need for additional training. Specifically, we use chunk-based triangular attention matrix, aiming at memory-friendly resource consumption (Figure 1 left), and we employ Stair PE to handle the last chunk (Figure 1 right below), effectively making Mesa-Extrapolation a completely free plug-in for LLMs.Our contributions are summarized as follows:1. Theoretical Analysis We provide a comprehensive theoretical analysis on 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 a clear understanding of the extrapolation problem and potential solutions for LLMs utilizing PE. 2. Introduction of Mesa-Extrapolation We introduce a novel extrapolation approach called "Mesa-Extrapolation." Based on triangular attention matrix, this method strategically organizes input tokens into chunks, with the final chunk employing a weave PE method (e.g., Stair PE) to integrate all token states. Mesa-Extrapolation provides a practical and effective solution to the extrapolation problem. 
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, 2, 3, ...) is directly represented, or relative, where the distance between tokens is used as positional information. Absolute Position Embedding (APE) embeds each absolute position i into position vector p i and adds word embeddings to their corresponding p i , before feeding them to the LLMs Vaswani et al. (2017) . However, the extrapolation ability is limited because it cannot generalize to unseen positions. RoPE Su et al. (2023) rotates the query and key vectors with an angle proportional to their absolute positions, so the attention dot production only depends on relative distance between tokens, providing a relative positional encoding. T5's Relative Bias first maps the relative distance (i -j) between tokens at positions i and j to a scalar bias value b = f (i -j), where f is a lookup table. 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 as ReRoPE and Leaky-ReRoPE Su (2023b) achieve effective extrapolation without fine-tuning by meticulously weaving relative positions of 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, it theoretically shows that a specific transformer model can get relative and absolute positional information, even in the absence of PE. Haviv et al. (2022) also demonstrates NoPE achieves comparative performance to standard Transformer models. These new studies pose a key challenge regarding the choice of whether using PE or not in Transformer architecture (refer to Appendix A for more related works).3 Model Extrapolation: NoPE vs. Weave PEQuestion: 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 a 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 well-specification, asymptotic approximations only holding locally). The authors should reflect on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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, a worse outcome might be 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 is an easy plugin and can enhance extrapolation performance of LLMs without any additional resource consumption.We mainly consider relative PE methods and formally define their self-attention dot product as a function f PE , which takes the query q t located on position t, the key k i located on position i, and their relative positions t -i as input parameters, as follows:⟨qt, ki⟩ := fPE(qt, ki, t -i),where f PE denotes a relative PE method such as RoPE or ALiBi.For ALiBi, ⟨q t , k i ⟩ := f ALiBi (q t , k i , t -i) = q T t k i -(t -i) • C m+1 , where m is head index and C = 2 -2 -log 2 (#heads+3) .For NoPE, ⟨q t , k i ⟩ := q T t k i . Based on Equ.1 we formally define weave PE as follows:⟨qt, ki⟩ := fweavePE(qt, ki, t -i) = fPE(qt, ki, W(t -i)),where W is a weave function which takes the relative position t -i as input parameter.For example, ReRoPE Su (2023b) can be considered as an example of weave PE, with its W function defined as follows:W(t -i) := t -i , t -i ≤ N N , t -i > Nwhere N is a constant. ReRoPE's dot-product attention is:⟨q t , k i ⟩ := f ReRoPE (q t , k i , t -i) = f RoPE (q t , k i , W(t -i)) = q T t R W(t-i)θ k i ,where R is a rotation matrix that rotates W(t -i)θ radians. This is based on RoPE's dot-product attention:⟨q t , k i ⟩ := f RoPE (q t , k i , t -i)) = q T t R (t-i)θ k i .Chen et al. ( 2023) explores the evolution of hidden state values and reveals a 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 the alterations in hidden state values across various positions and layers. Results show a significant shift in 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 to independently generate position information. Drawing inspiration from this, we endeavor to construct a Transformer model capable of mirroring this observation.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 a reasonable range. We define this observable boundary as the threshold H. This threshold can be either an upper bound or a lower bound. For our analysis, we focus on the lower bound of this threshold. A successful extrapolation occurs when a large model consistently generates accurate next tokens for a 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 is a lower bound as threshold H for the hidden state value o in specific dimension and specific layer. Let M be the max window length for LLM. Predefine query W Q , key W K , value W V and output W O matrices, and feed-forward sub-layer W 1 , W 2 matrices. When o > H, LLM extrapolates successfully. Once o < H, LLM extrapolation fails.These assumptions indicate that 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. Building upon these assumptions, theoretical results for NoPE exceeding the effective window length are as follows:Theorem 3.1 (NoPE Extrapolation). Let x = [< bos >, x 1 , . . . , x T ] be an input sequence of length T + 1 to the model. Then, there exists W Q , W K , W V , W O , W 1 , and W 2 matrices, such that when T < M , o T > H; and when T > M , o T < H.Full proof is given in Appendix E.1. This theorem reveals the internal mechanism of NoPE extrapolation as the input length changes. The theoretical results for PE are as follows:Theorem 3.2 (PE Extrapolation). Let x = [< bos >, x 1 , . . . , x T ] be an input sequence of length T+1 to the model. Consider a simple relative PE schema where dot product between query q t and key k i at positions t and i (t ≥ i) can be expressed as:⟨q t , k i ⟩ := q T t k i -(t-i). Then, there exists W Q , W K , W V , W O , W 1 , and W 2 matrices, such that when T < M , o T > H; and when T > M , o T < 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 t -i < N , W(t -i) = t -i; and when t -i ≥ N , W(t -i) = N . Then, the attention dot product is fixed as below:⟨qt, ki⟩ := q T t ki -(t -i) , t -i < N q T t ki -N , t -i ≥ N, where N ≪ M . Then, applying W Q , W K , W V , W O , W 1 , and W 2 matrices from Theorem 3.2, we have whenT > M , o T > H.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 on 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 to 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 is 512. More experimental parameters also validate this setting (refer to Appendix B.2). Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
mesa-extrapolation: 
 In this section, we begin by introducing a novel weave position encoding method, termed Stair Position Encoding (Stair PE). Following this, we propose a chunk-based triangular attention matrix.Building on these concepts, we introduce the implementation of Mesa-Extrapolation. Lastly, we discuss the theoretical properties of these innovations.Following the concept of weave PE in Equ.2, we define a novel weave PE method, namely Stair PE as follows:EQUATIONEQUATIONwhereI = N + t-i-N E. 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:⟨q t , k i ⟩ := f StairRoPE (q t , k i , t -i) = f RoPE (q t , k i , W(t -i)) = q T t R W(t-i)θ k i .Taken a sequence of length 10 as an example, the right subplot of Figure 1 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, it has to calculate the attention matrix more than once Su (2023b) . Compared with ReRoPE (detailed on Appendix B.3), Stair PE provides a 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 C.6).While our work was conducted independently, we note that Jin et al. (2024) 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 to Appendix G). Consequently, Self-Extend can be categorized as a Weave PE method. Our proposed Chunk-based Triangular Attention Matrix (detailed in Section 4.2) and its corresponding theoretical properties (Section 4.4) are also applicable to this parallel approach.We design a chunk-based triangular attention matrix as shown in the left subplot of Figure 1 . 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 a 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 a self-attention operation to generate a corresponding chunk. That is, a sub-sequence of length l will generate a corresponding chunk with the size l × l.Algorithm 1 Mesa-Extrapolation Algorithm Notice that regular PE (such as RoPE or ALiBi) is applied to all chunks except for the last chunk, for which Stair PE is applied. For the last chunk, all previous chunks are concatenated, and Stair PE is used to rearrange relative positional encoding to achieve extrapolation beyond the effective window length.Require: DynamicSplit, LLM, StairPE Input: s[0 : T -1] (input tokens with length T) Output: s[T, T + 1, ...] # Prefill Stage 1: f irst_length, chunk_width ← DynamicSplit(s) 2: K_cache, V _cache ← [], [] 3: f irst_K, f irst_V ← LLM(s[0 : f irst_length]) 4: Append f irst_K to K_cache, f irst_V to V _cache 5: i ← f irst_length 6: while i < T -1 -chunk_width do 7: K, V ← LLM(s[i : i + chunk_width], f irst_K, f irst_V ) 8: K_cache append K, V _cache append V 9: i ← i +In summary, the process of Mesa-Extrapolation mainly contains four steps (Algorithm 1): 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.Firstly, DynamicSplit function segments the input sequence, and the first segmented subsequence is fed into LLM to generate the first attention matrix chunk (line 3 in Algo.1). Secondly, subsequential sequences are iteratively processed while simultaneously feeding the key and value pairs of the first chunk into LLM to generate subsequent chunks (line 6-10 in Algo.1). 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 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 Algo.1). We establish the effectiveness of our proposed Mesa-Extrapolation in the next section.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 a positive constant. Consider a simple Stair PE extrapolation schema, and the attention dot product is fixed as:⟨qt, ki⟩ := fstairPE(qt, ki, t -i) = q T t ki -(t -i) , t -i < N q T t ki -I , t -i ≥ NwhereN ≪ M , I = N + t-i-N E, and the extrapolated width E is a constant. Then, ApplyW Q , W K , W V , W O , W 1 , and W 2 matrices from Theorem 3.2. Although T > M , it still o T > H.Full proof is provided in Appendix E.4. We prove that Mesa-Extrapolation can effectively extrapolate outside the max window length. 
experiments: 
 In this section, we validate the performance of Mesa-Extrapolation through experiments measured over multiple metrics. We choose GovReport Huang et al. (2021) , Pile Gao et al. (2020) , LongBench Bai et al. (2023), and LongEval Krishna et al. (2023) datasets, and also generate a passkey dataset, which has been integrated in the code warehouse. More experimental details and results are referred to Appendix B 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 (2023b), Leaky-ReRoPE Su (2023b), Dynamic-NTK Liu et al. (2023) , LM-Infinite Han et al. (2023) , and Streaming-LLM Xiao et al. (2023) .We evaluate Mesa-Extrapolation using three prominent LLM families: LLaMA Touvron et al. (2023a) Touvron et al. (2023b) (including LLaMA-3B (Open-LLaMA-3B), LLaMA2-7B-Chat, and Vicuna-13B-V1.3), MPT Team (2023) (including MPT-7B), and PyThia Biderman et al. (2023) (including PyThia-6.9B and PyThia-12B). Notably, LLaMA and PyThia incorporate RoPE Su et al. (2023) , whereas MPT employs ALiBi Press et al. (2021) -two of the most influential PE techniques in recent research. Furthermore, we validated our approach using the Phi-3-mini-128k-instruct 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 as the experimental environment and adopt the PyTorch framework.We assess the accuracy of Mesa-Extrapolation using the generated passkey dataset. This dataset comprises samples of varying lengths, each storing a random password at a random position. The sample length initiates at 1024 and increments by 1024. Simultaneously, 100 samples are randomly generated for each length. The proportion of correct answers found by LLMs is calculated for each input length. Fig. 3 shows the results of 6 LLMs on passkey retrieval task. The LLaMA families can employ various methods, including Origin, ReRoPE, Leaky-ReRoPE, Dynamic-NTK, LM-Infinite, Streaming-LLM, and our Mesa-Extrapolation. Note that these methods are model-specific and may not be universally applicable across all model series. For the MPT model, Origin, Streaming-LLM, ReRoPE, and Mesa-Extrapolation can be utilized. Similarly, for the PyThia model, Origin, Streaming-LLM, and Mesa-Extrapolation can be applied. Analyzing the LLaMA model series reveals that weave PE-based methods, including ReRoPE, Leaky-ReRoPE and Mesa-Extrapolation, 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-Extrapolation and ReRoPE show a decline. We speculate that this may be attributed to an approximate ALiBi PE applied on MPT model. This approximate ALiBi would lead to significant disruptions when weaving its positions. (refer to Appendix C.2 for more details about MPT).In the PyThia models, an additional observation is that 100% accuracy is still not achieved within the training length. We attribute this to the PyThia model being a pre-trained model without instruction alignment, resulting in a weakened intrinsic understanding of the task. Results with enhanced prompts are referred to Appendix C.5. Dynamic-NTK exhibits partial extrapolation capabilities beyond the maximum training length. Streaming-LLM and LM-Infinite also exhibit poor performance. This is because these methods discard portions of the input token, leading to potential information loss and incorrect answers. We further assess the fluency of Mesa-Extrapolation utilizing the perplexity metric. Results evaluated on the Pile dataset are presented in Fig. 4 . X-axis represents the length of the input token, while the Y-axis corresponds to NLL (Negative Log-Likelihood) 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 11k, and the performance continues to drop as the input length increases. In summary, our Mesa-Extrapolation demonstrates comparable performance to other methods on PPL metric.We conduct a summary task using the GovReport dataset and employ ROUGE ROUGE (2004) (ROUGE-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*1024 to 11*1024 based on sample length, with each interval of 1024 units. A test set is created by randomly selecting 8 samples from each interval. We choose LLaMA2-7B-Chat as the evaluated LLM. The experimental results for ROUGE is presented in Tables 1 below: Table 1 : ROUGE metric on LLaMA2-7B-Chat, averaged on 8 samples within each interval using the GovReport dataset. Each cell contains ROUGE-1/ROUGE-2/ROUGE-L. The best values are marked in bold. Some observations: (1) Dynamic-NTK shows slightly better performance within 11k. (2) Other methods showcase the ability to achieve scores of varying degrees. In Table 1 , we record the average scores of Rouge-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 it 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. 2 . Weave PE-based methods, including ReRoPE, Leaky-ReRoPE and Mesa-Extrapolation maintain similar generation quality as the length increases. Note our Mesa-Extrapolation shows slight variability 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 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. To compare actual memory consumption and inference speed, we conduct experiments using both the 3B and 7B versions of the LLaMA model. The results are presented in Fig. 5 . In Fig. 5 , 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 is closely related to memory usage, primarily from the computation of the attention matrix.Observing Fig. 5 , both memory usage and decoding time for Origin and Dynamic-NTK exhibit a quadratic trend. Similarly, ReRoPE and Leaky-ReRoPE exhibit the highest memory usage and decoding time, showcasing a quadratic trend, which aligns with our analysis (refer to Appendix C.7). Although LM-Infinite demonstrates a linear trend, its increase is substantial. In contrast, Mesa-Extrapolation 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 theoretical exploration, we uncover the underlying mechanisms of this challenge, shedding light on the reason of extrapolation failure for both NoPE and PE. Furthermore, we present theoretical evidence demonstrating the potential for effective extrapolation using Weave PE. Based on Weave PE, we introduce a practical solution called Mesa-Extrapolation, 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 a practical solution, with a complete free plug-in for LLMs.Limitations. Mesa-Extrapolation is a plug-and-play method that does not require additional finetuning. However, previous work, "NTK-aware" ntk ( 2023) also shows that applying further fine-tuning to plug-in extrapolation is possible. Therefore exploring fine-tuning based on Mesa-Extrapolation can be an interesting next step. Due to limitations of resources, we have not yet validated our method at 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, it allows for training LLMs from scratch with short texts and subsequently expanding their effective window length with a free plug-in extrapolation method, which can greatly help the industry improve the extrapolation capabilities of diverse LLMs.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 to identify the extent of the challenges faced by these beneficiaries and determine how to 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 it difficult for them to access necessary care. 9. Limited enrollment options: Dual-eligible beneficiaries may have limited enrollment options, which can lead to default enrollment into D-SNPs without their knowledge or consent. 10. Limited quality information: 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 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 challenges 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 default enrolled into D-SNPs and take steps to improve the alignment of enrollment between Medicare and Medicaid. The report also identifies the actions taken by the Army to address the recommendations 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 to determine the effectiveness of these efforts. The report concludes by stating that it will be important for the Army to continue to 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. The report discusses the challenges faced by the US Department of Veterans Affairs (VA) in providing disability compensation to veterans. The VA pays monthly disability benefits to veterans who have service-connected conditions, which are conditions that were caused or aggravated by military service. The VA has been facing challenges in determining when to reevaluate these conditions, and the report highlights several areas where improvements can be made. 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, 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 serviceconnected conditions. Secondly, the report highlights the issue of unwarranted reevaluations. 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 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 clarify the knowledge, skills, and abilities required for claims processors to determine when to reevaluate veterans' service-connected conditions. Thirdly, the report notes that the VA's procedures for reevaluating serviceconnected conditions are not always consistent. While the VA has a rating schedule that provides guidelines for evaluating the severity of service-connected 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 necessary knowledge, skills, and abilities to determine when to reevaluate veterans' service-connected 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 is 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 a result, many claims processors are not adequately equipped to determine when to reevaluate veterans' 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-connected 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-connected 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. The report also provides data on 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 economic uncertainty on state and local government revenues and expenditures. 
acknowledgement: 
 This work was supported by the National Key R&D Program of China under Grant No.2022ZD0160504 and Tsinghua University(AIR)-Asiainfo Technologies (China) Inc. Joint Research Center. We would also like to acknowledge anonymous reviewers and Zengxiang Lu for their valuable feedback and discussions. 2023a), eliminating the need for fine-tuning. These methods do suffer from some drawbacks, such as twofold increase in 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-tuning as Weave PE. We also notice that, recent work, InfLLM Xiao et al. (2024) , proposes an additional memory units, which lookup token-relevant units for attention computation. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes] Justification: We follow the license and terms.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: 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 a 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-frequency interpolation concept for RoPE. Based on "NTK-aware", recent works bloc97 ( 2023 Extrapolation for NoPE There also exists a counter perspective asserting that the position information 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). Haviv 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 experiments. These new studies pose a key challenge regarding the choice of whether using PE or not in Transformer architecture.We mainly focus on Transformer architecture. Although the Transformer architecture is considered as a "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 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. (2023) , inspired by programming Transformers Lindner et al. (2023) , the authors construct a specific Transformer with predefined matrix parameters, theoretically demonstrating 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 a corresponding increase. Additionally, Su (2021) introduces a scaling factor, denoted as log train-len (n), which serves to 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.The data used to perform the passkey task is constructed as follows:TASK-DESCRIPT = "There is an important info hidden inside a lot of irrelevant text. Find it and memorize it. I will quiz you about the important information there."DEFAULT-CONTENT = "The grass is green. The sky is blue. The sun is yellow. Here we go. There and back again."KEY-CONTENT = "The pass key is {KEY}. Remember it. {KEY} is the pass key."The TASK-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 is 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.Mesa-Extrapolation We design the DynamicSplit function used in Algorithm 1 to dynamically divide the input sequence into several subsequences according to the input length. The length of each subsequence corresponds to the size of the chunk. Let C denote the length of the each chunk (except the first chunk length F and the last chunk length L). Define I as input token length and T as max training length.The DynamicSplit function is detailed as follows:In general, we set F = 100, M max = 200 and L = 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.3. In Equ.3, we generally set the extrapolated position N = 512 and set the extrapolated width E = 50.The handling of RoPE Su et al. (2023) involves assigning positions to the query vector and key vector. The length of the query corresponds to the length of the last chunk, while the lengths of the key and value align with the combined lengths of all chunks. We assign position encoding to the query vector according the same sequence positions. Regarding the key's position encoding, we utilize the extrapolated width E and extrapolated point N . By designing 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 et 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-Extrapolation method design.ReRoPE & Leaky-ReRoPE We follow Su (2023b) for configuring the parameters of ReRoPE and Leaky-ReRoPE. The extrapolated position for ReRoPE is established at 512, mirroring the setting for Leaky-ReRoPE. Simultaneously, the extrapolated increment for Leaky-ReRoPE is calculated in relation to the input length, following the formula below:1 k = T -w I -wwhere w is the extrpolated position as 512, T is the maxium training length, and I is the input token length.The ReRoPE and Leaky-ReRoPE methods are currently only applied to the LLaMA model series.We implemented ReRoPE based on its ideas on the MPT models. The distinguishing factor between the two approaches lies in the selection of the initial token length, with LM-Infinite opting to splice longer tokens. We speculate that this is also the reason why LM-Infinite performs better than Streaming-LLM in the experiments.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.We list the details of the weave PE-based methods, including ReRoPE and Leaky-ReRoPE, as follows:ReRoPE=             0 1 0 2 1 0 ... 2 1 0 N ... 2 1 0 ... N ... 2 1 0 N ... N ... 2 1 0 ... N ... N ... 2 1 0 N ... N ... N ... 2 1 0             , Leaky-ReRoPE =               0 1 0 2 1 0 . . . 2 1 0 N • • • 2 1 0 N + 1 k N • • • 2 1 0 . . . N + 1 k N • • • 2 1 0 N + L k • • • N + 1 k N • • • 2 1 0              where left ReRoPE shows relative position on attention matrix, including (1) Numbers marked on each cell denote its relative position (t -i) between q t and k i .(2) It 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 t and k i .(2) It start to extrapolate position from relative position N , with an incremental factor 1 k . With Stair PE defined on Equ.3, the extrapolated position after N exhibits a fixed extrapolated width E, resembling a stair-like increment. Our Mesa-Extrapolation is designed with a finer position granularity compared to ReRoPE. Simultaneously, unlike Leaky-ReRoPE, 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-ReRoPE 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, as the input length expands, both inference time and memory consumption grow proportionally.It 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 -7 -6 -5 -4 -3 -9 -8 -7 -6 -5 -4 -3 -2 -9 -8 -7 -6 -5 -4 -3 -2 -1 -9 -8 -7 -6 -5 -4 -3 -2 -1 0              where showcase an input token length 10 for ALiBi PE mask. Based on this approximate implementation of ALiBi, we still use splitting chunk and Stair PE to implement Mesa-Extrapolation. We speculate that the approximation of ALiBi is the reasons for the instability of the extrapolation on Accuracy. Weave PE-based methods, including ReRoPE, Leaky-ReRoPE, and Mesa-Extrapolation, consistently demonstrates competitive results, maintaining similar generation quality as the length increases.Overall, despite the chunking applied to our Mesa-Extrapolation method, it maintains a competitive edge compared to ReRoPE and Leaky-ReRoPE. 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-Extrapolation in the summary task, focusing on the generation of summary text within 1000 tokens across different input lengths, are detailed in Table 5 .Following the same metrics setting about LLaMA models on Fig. 4 , we plot the NLL result about MPT-7B on Fig. 6 as below: In Fig. 6 , both Mesa-Extrapolation and Streaming-LLM demonstrate effective negative log-likelihood (NLL) values. For the original MPT model, after the extrapolation is extended 3.5k, it will cause the perplexity (PPL) level to rise rapidly.ALiBi Press et al. (2021) can still effectively extrapolate to 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 expression (refer to D.2) indicates a constant decrease in the value of its position encoding as the relative distance increases.Considering the SoftMax 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 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 (2023a).It's noted that, NoPE Kazemnejad et al. (2023) 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.We conduct additional testing on LongEval Krishna et al. ( 2023) lines task, a recently prominent evaluation task for long texts. Mesa-Extrapolation also shows a certain extrapolation ability on the PyThia-6.9B model, with a decrease in extrapolation performance as the input length increases.We select LongBench Bai et al. (2023) 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 a 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 Table 3: Considering that Mesa-Extrapolation involves positional approximation, as the input length increases, attention becomes more dispersed, resulting in increased entropy. One possible approach to mitigate these entropy increases is to utilize 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, it may be the reason why PyThia cannot achieve 100% accuracy within its training length on Fig. 3 , due to a 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 as an enhanced prompt, like below:Q: what is the passkey in below text? + Sample \n A:or Q: Sample \n A: the passkey isAdditionally, we leverage model parallel inference technology BlackSamorez (2023) and perform verification concurrently on 2 A800 GPUs.Fig. 8 show the accuracy on 3 LLaMA models with enhanced prompts using Mesa-Extrapolation. We declare that the longest input length that these 3 models can currently reach is the limit of our existing hardware resources. For LLaMA-3B, the enhanced prompts improve the Accuracy and is extrapolated to 60k.(2) Both of LLaMA2-7B-Chat and Vicuna-13B models, show good improvements by the enhanced prompts.Through this experiment, we hypothesize that by writing prompts more carefully and accurately, we can maximize the extrapolation performance of free plug-in. 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 of 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 9 are as follows: Figure 9 demonstrate that both ReRoPE and Leaky-ReRoPE experience a certain loss in 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.We assess the computational memory usage and inference time about decoding speed on various methods. O(n 2 ) 2 × O(n 2 ) 2 × O(n 2 ) O(n 2 ) O((1 + √ 2)n) O((1 + √ 2)n) O((2 + √ 2)n)Table 4 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 in a memory footprint of O(n 2 ). 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 to be calculated twice, their memory footprint is 2 × O(n 2 ). For Mesa-Extrapolation, its strategy involves splitting chunks while avoiding the quadratic term. Accounting for splicing in the last chunk, its total memory usage scales proportional to O((2 + √ 2)n). LM-Infinite and Streaming-LLM adopt a similar Λ-shaped mask, that scales proportional to O((1 + √ 2)n).We present here the results of the summary generation task using GovReport Huang et al. (2021) . In this experiment, task is to generate a summary for texts of varying lengths, limited to 1000 tokens. The outcomes yielded by Mesa-Extrapolation are outlined below on Table 5 : 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-intensive and takes a long time to complete, and therefore provides contract financing to help contractors manage their expenses. * DOD provides contract financing through progress payments and performancebased payments. Progress payments are based on the percentage of work completed, while performance-based payments are based on the contractor's achievement of specific milestones. * The Federal Acquisition Streamlining Act of 1994 requires DOD to use performance-based payments whenever practicable. However, the use of performance-based payments has decreased since the act was passed. * In 2010, DOD issued a proposed rule to amend the Defense Federal Acquisition Regulation Supplement (DFARS) to provide for performance-based payments.The proposed rule would have allowed contractors to receive payments based on their performance, but the rule was later withdrawn. * Despite the decreased use of performance-based payments, DOD has not conducted a comprehensive assessment of the impact of its contract financing policies on the defense industry in over 30 years. * GAO recommends that the Acting Secretary of Defense direct the Under Secretary of Defense for Acquisition and Sustainment to conduct a comprehensive assessment of the effect of DOD's contract financing policies on the defense industry and update the assessment on a recurring basis. * The report also notes that changes in the defense industry, such as the emergence of new entrants and changes in market and economic conditions, have affected the defense industry's ability to attract new entrants. * DOD has acknowledged the need to assess contract financing policies against market conditions on an ongoing basis, but has not done so comprehensively in 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. * The guidelines do not require agencies to provide justifications for not conducting 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 in a lack of understanding of the impact of these programs. * The guidelines do not require agencies to develop staff skills in evaluation and use of evidence, which could result in a lack of capacity to conduct effective evaluations. * The guidelines do not provide specific requirements for evaluating the effectiveness of interagency agreements, which could result in a lack of accountability for these agreements. * The guidelines do not require agencies to provide timely evaluation results to decision-makers, which could result in a 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 evaluation, 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. Table 5 shows that Mesa-Extrapolation adeptly and systematically summarizes key points one by one across various input 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-Extrapolation accurately incorporates punctuation and exhibits an automatic stopping mechanism for proper stopping.We further conducted experimental validation on the Ruler datasets Hsieh et al. (2024) , focusing on the single-keys NIAH task. The needle-in-a-haystack (NIAH) test assesses the ability to retrieve a specific piece of information (the "needle") from long distractor texts (the "haystack").In this experiment, we employed the microsoft/Phi-3-mini-128k-instruct model, which has practical value in 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 results with those achieved using our Mesa-Extrapolation method.As shown in Figure 10 , the original Phi-3-mini-128k-instruct model can only extrapolate up to its official limit of 128k tokens, beyond which it fails. In 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 an out-of-memory error. 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 scalars. We mainly follow Kazemnejad et al. (2023) to define these notations.Let f θ be a decoder-only Transformer model, where θ denotes the model parameters. f θ processes the input sequence x = [< bos >, x 1 , . . . , x T ] by applying a series of layers, where < bos > represents the first token Tokenizer transformation.Each layer l, consisting of self-attention heads and a feed-forward sub-layer, produces the hidden state H l at layer l, after reading the previous hidden state H (l-1) .Each head is parameterized by a query W m Q , key W m K , value W m V , and output W m O matrices, where m represents the attention head index, andW m Q , W m K , W m V ∈ R h×d and W m O ∈ R d×h .d is the model's hidden state size and h is the attention dimension (h = d #heads ). Note that we drop the attention head index m where it is clear from the context.The Transformer layer TLayer (l) (H (l-1) ; θ l ) consist of self-attention heads and a feed-forward sub-layer, and input the previous hidden state H (l-1) , and generate the hidden state H (l) at layer l. l is the layer index, and θ l is the set of parameters of the l-th layer. Each hidden state H (l) ∈ R d×(T +1) is a matrix, and h (l) t denotes its hidden state at column t, i.e. at position t. Each feed-forward sub-layer FF is parameterized by W 1 , W 2 ∈ R d×k.d matrices, where k denotes a 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 (l) processes each column of H (l-1) independently and in parallel to generate the output. The computation of the t-th column of H (l) is as follows:EQUATION)where λ is layer normalization, and a t ∈ R d is the output of the multi-head self-attention sub-layer at position t.a t is computed as:EQUATIONwhere Attn (m) denotes the m-th attention head. Let o t ∈ R d denote the output of an attention head at position t. Then, o t is computed as:EQUATIONwhere α = softmax(α) ∈ R (t+1) , and α is the attention weight vector such that:EQUATIONwhereq t = W Q h (l-1) t ∈ R h , k i = W K h (l-1) i∈ R h , and ⟨•, •⟩ denotes the dot product operation.The feed-forward sub-layer FF(•) ∈ R d is a two-layer MLP as below:EQUATIONwhere σ is a non-linear activation function(usually ReLU or GeLU Hendrycks & Gimpel ( 2016)), and σ(•) ∈ R d is layer normalization Ba et al. (2016) . It's worthy noted that the additive view of attention heads Elhage et al. (2021) in Eq.( 5) is mathematically equivalent with the view of concatenate and multiple Vaswani et al. (2017) . The additive view is easier to understand and analyze.The hidden state H (0) is initialized with a learned embedding of the input sequence X, i.e. +1) is the one-hot encoded input sequence. V is the vocabulary size.H (0) = W E X, where W E ∈ R d×V is the embedding matrix and X ∈ R V ×(TWe emphasize here that NoPE generally refers to these architectures that do not use position encoding components or remove the position encoding schemas, which is reflected in the attention dot product operation and is formally expressed as:EQUATIONPE 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.For ALiBi Press et al. (2021) , it takes the form:EQUATIONwhere m is head index and C is a constant defined as:EQUATIONFor example, if the number of heads is 8, we have 1 2 , 1 2 2 , . . . , 1 2 8 . For RoPE Su et al. (2023) , it's a relative PE that applies a 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:EQUATION)where R is a rotation matrix that rotates (i -t)θ radians:EQUATIONFor d > 2, RoPE applies the same approach on every two consecutive dimensions of q t and k i , but with different θ angles.For other PE methods, we recommend readers to consult the corresponding papers.We provide proof about Theorems 3.1, 3. Please refer to Appendix D for some necessary background knowledge.Theorem E.1 (NoPE Extrapolation). Let x = [< bos >, x 1 , . . . , x T ] be an input sequence of length T + 1 to the model. Then, there exists W Q , W K , W V , W O , W 1 , and W 2 matrices, such that when T < M , o T > H; and when T > M , o T < H.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 W E ∈ R d×V , where each column is the embedding of a token in the vocabulary. We construct W E such that it always sets the first dimension of every embedding vector to 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: W E =         1 1 1 . . . 1 1 0 0 . . . 0 0 0 0 . . . 0 e 4,EQUATIONwhere e d,i ∈ R.Then, we use the word embedding matrix W E to compute the embedding H (0) : H (0) = W E X =         1 1 1 . . . 1 1 0 0 . . . 0 0 0 0 . . . 0 e 4,EQUATIONSecond, for head dimensions h ≥ 1, we construct the weights W K , W V , W O of the first attention head in the first layer. W Q can be any arbitrary matrix. Specifically,EQUATIONW 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. ConsideringEQUATIONi , then:EQUATIONWe use W Q to compute the query vector q t by applying q t = W Q h (0) t : q t = [q 1 , q 2 , ..., q h ] T (18) where q j ∈ R can take any arbitrary value.Next, we compute the attention weight vectors α:EQUATIONwhereα * = q 1 + q 2 + • • • + q h .Then, we apply SoftMax to compute the attention weight score. Since all α * are the same, we have:EQUATIONNow, we compute the value vectors by applyingEQUATIONThen, we compute the attention value:EQUATIONFinally, we compute the output of the attention head by applying W O :EQUATIONFrom Equ.24, it can be observed that when t < M , the hidden state value on the third dimension is greater than H, indicating a successful extrapolation. Conversely, when t > M , the hidden state value on the third dimension is less than H, indicating a failed extrapolation.Next, we provide the proof for Theorem 3.2 as below:Theorem E.2 (PE Extrapolation). Let x = [< bos >, x 1 , . . . , x T ] be an input sequence of length T+1 to the model. Consider an simple relative PE schema where dot product between query q t and key k i at positions t and i (t ≥ i) can be expressed as: ⟨q t , k i ⟩ := q T t k i -(t-i). Then, there exists W Q , W K , W V , W O , W 1 , and W 2 matrices, such that when T < M , o T > H; and when T > M , o T < H.Proof. We regard the third dimension as a specific dimension. And there is a threshold in this dimension in the second layer. Our proof construct the matrices on the first two layers. The first layer is used to extract position information. The second layer will generate a 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.(1)Consider the first layer operation.First, following Theorem E.1, we construct the same word embedding matrix W E .For head dimensions h ≥ 3, we construct the weights W K and W V for the first attention head in the first layer. W Q still can be any arbitrary matrix. Specifically, Since the elements in W K is all 0, by applyingEQUATIONk i = W K h (0)i , we have:EQUATIONWe use W Q to compute the query vector q t by applying q t = W Q h (0) t : q t = [q 1 , q 2 , ..., q h ] Twhere q j ∈ R can take any arbitrary value.Next, we compute the attention weight vectors α. Consider q T t k i = 0 and position information t and i, we have:EQUATIONThen, apply SoftMax to α, we have: α = SoftMax(α) = [ e -(twhere define S(t) =t-1 j=0 e -j . We adopt its abbreviation S.Now, we compute the value vectors by applyingEQUATIONi :EQUATIONThen, we compute the attention value:EQUATIONAfter that, we compute the output of the attention head by applying W O (using the same construction as Equ.16 in Theorem E.1):o t = W O   i≤t αi v i   = [0, 0,e -(t-1) S , . . . , 0] T (32)Then, e -(t-1) S can be regarded as a monotonically decreasing function of t. Then through the MLP feedforward layer, we can always let the MLP layer recover the value of t.Therefore, we can get that: H (l=1) =         1 1 1 . . . 1 1 0 0 . . . 0 1 2 3 . . . T + 1 e 4,EQUATIONwhere position information is embedded in the third dimension of hidden state.(2)Consider the second layer operation.For head dimension h ≥ 3, we construct the weights W Q and W K for the first attention head in the second layer. W V follows the Theorem 3.1 setting. Specifically,W Q =         0 0 0 . . . 0 0 0 0 . . . 0 0 0 1 . . . 0 q 4,1 q 4,2 q 4,3 . . . q 4,d . . . . . . . . . . . . . . . EQUATIONEQUATIONThen, by applyingq i = W Q h (0)i , we have:EQUATIONwhere q j can be arbitrary value for j ≥ 4.k i = W K h (0)i , we have:EQUATIONThen, we have:EQUATIONNext, according to the PE definition, apply the position information t and i to the dot production, we have:⟨q t , k i ⟩ = 4<=j<=h q j, which means ⟨q t , k i ⟩ = ⟨q t k l ⟩ for any l ̸ = i.Then, we know that, α = [α * , α * , . . . , α * ] T (38) where α * = 4≤j≤t q j . Then, apply SoftMax to α, we have:EQUATIONNext, follow same process as Equ.( 21 Next, we provide the proof for Theorem 3.3 as below:Theorem E.3 (Weave PE Extrapolation). Let N be a positive constant. Consider a simple weave PE extrapolation schema: when t -i < N , W(t -i) = t -i; and when t -i ≥ N , W(t -i) = N . Then, the attention dot product is fixed as below:⟨qt, ki⟩ := q T t ki -(t -i) , t -i < N q T t ki -N , t -i ≥ N, where N ≪ M . Then, applying W Q , W K , W V , W O , W 1 , and W 2 matrices from Theorem 3.2, we have when T > M , o T > H.Proof. Our proof is closely related to Theorem 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.Following Theorem E.2, we can get H (0) .Then, compute the attention weight vectors α. Consider q T t k i = 0 and position information t and i. By applying this Extrapolation schema, we have:EQUATIONFollow Eqs.28 and 29, and apply SoftMax to α, we have:EQUATIONwhere t > N and define S # (t) =N -1 j=0 e -j + (t -N )e -N . We adopt the abbreviation S # where there is no confusion.Then, compute the value vector by applyingv i = W V h (0)i , still have:v 1 =     1 0 . . . 0     , v 2 =     0 0 . . . 0     , . . . , v t =     0 0 . . . 0     (43)Then, we compute the attention value:EQUATIONAfter that, we compute the output of the attention head by applying W O :EQUATIONNotice that we set the MLP feed-forward process simulate a a piecewise function about e -(t-1) S(t) , which produce a Integer t to recover the position.Considering t > N , we know e -(t-1)S(t) < e -(t-(t-N )) S # (t) < e -(t-(t-N ))S(N +1) . And the e -(t-(t-N ))S # (t) function decreases extremely slowly as t increases, almost equal to e -(t-(t-N )) S(N +1) .At the same time, the e -(t-1)function decreases very quickly when t is relatively small; As t increases, it also decreases extremely slowly.Combining the characteristics of these two functions, we can always choose a relatively small N to keep it away from M (that is N ≪ M ), so that the value recovered after e -(t-(t-N ))S # (t) passing through MLP process is around N + 1, because e -(t-(t-N )) S(N +1) can recover N + 1 and e -(t-(t-N )) S # (t) is almost equal to e -(t-(t-N ))S(N +1) . For the sake of simplicity, considering the rounding characteristics of piecewise functions, we might as well set e -(t-(t-N ))S # (t) to recover N + 1.Therefore, we can get the hidden state like that: EQUATIONContinue the second layer operations.i = W Q h (0)i , we have:EQUATIONwhere q j can be arbitrary value for j ≥ 4.EQUATIONi , we have:EQUATIONThen, consider t > N , and apply Extrapolation.EQUATIONwhen t -i ≥ N and i <= N ,EQUATIONLet τ = 4≤j≤h q j . We can get the attention score:α = [τ -0, τ -1, . . . , τ -(N -1) first-part , τ -N, . . . , τ -N second-part , τ -(N -1), . . . , τ -1, τ -0 third-part ] T (52)where third-part represents Equ.49, second-part represents Equ.50, and first-part represents Equ.51.Apply SoftMax to α, we can get that:EQUATIONSince the first element of α is the maximum value, α1 must be greater than 1 t .Next, similar process, we compute the value vectors by applyingEQUATIONThen, we compute the attention value:EQUATIONThen, we compute the output of the attention head by applying W O :EQUATIONWhen t > M , due to α1 > 1 t , it's possible to satisfy α1 • M -1 > 0 condition, such that the hidden state value o t in the third dimension is greater than H.We conjecture that while the attention mechanism in RoPE Su et al. (2023) involves multiplying by the rotation matrix of the relative position, it's essential to acknowledge that neural networks possess the capability to model any function. This implies the potential to decompose the relative position information into an additive form, as exemplified in our extrapolation scheme detailed in Theorem 3.3.Next, we provide the proof for Corollary 4.1 as below:Corollary E.4 (Mesa Extrapolation). Let N be a positive constant. Consider a simple Stair PE extrapolation schema, and the attention dot product is fixed as:⟨qt, ki⟩ := fstairPE(qt, ki, t -i) = q T t ki -(t -i) , t -i < N q T t ki -I , t -i ≥ N where N ≪ M , I = N + t-i-N E, and the extrapolated width E is a constant. Then, Apply WQ , W K , W V , W O , W 1 , and W 2 matrices from Theorem 3.2. Although T > M , it still o T > 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, in the first layer, according to Equ.45 and .46, we obtain the hidden state matrix as follows: EQUATIONEQUATION)where I is defined on Stair PE extrapolation schema.In the proof of the second layer, we still get the similar result like Equ.52, as below:EQUATIONwhere C is a constant, and each element within repeat-part is smaller than τ -0.Apply SoftMax to α, we can get that:EQUATIONwhich also shows that the first element of α is the maximum value and α1 must be greater than 1 t . Consequently, following Equ.56, we reach the same conclusion.We hypothesize that when the input length surpasses the effective window length of the model, some dimensions' values in the exceeded positions will experience a jump as the position changes.To investigate this jump phenomenon'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 a more accurate explanation, we take the LLaMA2-7B-Chat model and list the sequences converted by the tokenizer, as follows:tokens = [1, 22172, . . . , 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.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-Chat model's training length is 4096, implying the effective input window is in proximity to this location.Following this, we created a matrix graph, yielding the following results Fig. 11 : In Fig. 11 , 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-7B-Chat 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 0. Fig. 11 shows some noticeable jump from 0-th to 640-th dimensions, especially at the 1000 scale for the original model.Given the effectiveness of the extrapolation method ReRoPE in extending to lengths of up to 8k, we apply it to the LLaMA2-7B-Chat model. Employing the same conditions as those in the Normal Case settings, the results are as follows:In Fig. 12 , the obvious jumping phenomenon is successfully suppressed. It can be seen that each dimension at different positions still maintains consistent values. This illustrates that by suppressing sudden changes in the values of these dimensions, extrapolation can be made successful even outside the effective window length. Additionally, for layers 0 and 1, the hidden state values of different positions in each dimension are nearly identical. According to 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 or 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.We also use the LLaMA-3B model and the Vicuna-13B model to compare and demonstrate the effects of using Origin and ReRoPE, as follows on below Fig. 15 and .16.We continue our probe experiments using the "hello", and input sequences is up to 16000 tokens. These were validated on the LLaMA2-7B-Chat model. Given that the hidden state in LLaMA2 has a total of 4096 dimensions, we selected the first 20 dimensions to search observable thresholds. In the main text, we present the prediction results for the first and 6-th dimensions. The results for the 7-th and 9-th dimensions are shown in Figure 13 . Our experiments also reveal that not every dimension exhibits a clear threshold. Considering that the Transformer model is a type of neural network, we hypothesize that these dimensions with threshold undergo significant signal changes due to the characteristics of activation functions. These changes are amplified through successive layers, eventually leading to model output failures. We believe this internal mechanism explains why observable thresholds can predict the success or failure of extrapolation.We also validate our findings using the Vicuna-13B model, and the results are shown in Figure 14 : Figure 14 shows the hidden state value on the specific 4-th and 10-th dimensions. Similar the observations with LLaMA2-7B-Chat 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 to 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.In contrast to LLaMA2-7B-Chat 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 at the second layer, considering the integration of positional information from preceding layers, this still aligns with our theoretical framework.The formulation of Self-Extend is as follows:Let t denote the position of query, i denote the position of key, i 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. (2024) ), P = P // G, and the shifted relative position (W -W // G), we can get the position of query as:t // G + W -W // Gand the position of key as:i // G By RoPE, their relative position between t and i (consider t > i), is remapped to: In summary, under conditions t mod G >= i mod G and W mod G == 0, as well as changing the flooring operation to ceiling in Self-Extend, these two formulas are equivalent. Except for this condition, they yield slightly different results.Note because W and G are constants, the condition W mod G == 0 can 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, t = 10, i = 5, G = 2, but 10 // 2 -5 // 2 ̸ = (10 -5) // 2. 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

Additionally, 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.
questions: questions: The caption for Figure 1 is not sufficiently informative.

Additionally, it is unclear how the failure of an LLM is measured in Section 3.4 and Figure 2. 

The 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.

minor typos:

Theorem 3.2: an simple -> a simple

Line 161: defer to -> refer to

Line 242-243: a significant disruptions
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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]

2. The achieved context window is limited. 



[1] https://arxiv.org/abs/2404.06654

[2] https://evalplus.github.io/repoqa.html
questions: 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

2. 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?

3. 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: limitations: See the weakness and question sections.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: 1. Can authors explain the threshold definition: "When o > H, LLM extrapolates successfully. Once o < H, LLM extrapolation
fails." Is there a typo and inequalities are reversed?

2. In Fig 2, why dim 1 & 6 are of interest?
limitations: limitations: --
paper_summary: paper_summary: This paper studies the length extrapolation of LLMs.
1. 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.
2. 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.
strength_weakness: strength_weakness: 1. Methodological comparison with $\Lambda$-Attention

The 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?

---
2. Empirical comparison with Dynamic-NTK

Dynamic-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?

---
3. Relation between input sequence length $T$ and effective length $M$

The 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?

---
Editorial comments

- The fonts of the figures and tables are too small. Please make them more readable.
- 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."
questions: questions: See Weaknesses.
limitations: limitations: Well discussed. Extending this approach to fine-tuning would be an interesting next step.
paper_summary: paper_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.
strength_weakness: strength_weakness: **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:
* **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$.

* **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.
   * 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. 
   * 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.
* **Concern 3**: If possible, could the author compare the performance between Mesa-Extropolation and Self-Extend LLM?
* **Concern 4**: when the output sequence length $L_{generate} \gg L_{input}$, will the time cost also becomes O($L_{generate}^2$)?

Based 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.


Reference:

[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.
questions: questions: Please see the above question and concerns in weakness.
limitations: limitations: Yes, the authors have addressed the limitations. We may further discuss and analyze the Mesa-Extropolation in other areas.

Comments: title: Gently Reminder as the discussion deadline approaches
Thank you for your rebuttal
Response to the Rebuttal
Response to Author
Part 2
Part 1
Response to Author
comment: Dear Reviewer PZAX,

We suspect that you might not be familiar with this type of observation and assumption. Similar observations also can be found in some related work, such as LM-Infinite (the attention logit bound in its Figure 1(a) ).

We hope this is helpful.
Dear reviewer PZAX, 

your feedback is essential to us, if you think that our response addressed your concerns, we kindly ask you to consider raising your score. Please let us know if you have any questions or require further assistance.
The assumption and notations are a lot more clear for me now. Observing / assuming that entry-wide hidden vector values matter is pretty interesting and surprising to me. Thanks for the explanation.
Dear Reviewer LfLf,

Thank you very much for raising your score, and we deeply appreciate the valuable suggestions you have provided. We will express our sincere gratitude to you in the Acknowledgments section of our paper.

Once again, thank you very much.
Dear Reviewer PZAX,

Thanks for providing your further concerns. 

## About Assumption 1
We suspect there is a misunderstanding on the definition of o. In our assumption, "o" represents the hidden state value, not the sequence length of the input. Please refer to our first response for the definitions of "o" and "H".
For example, consider an input sequence of length I with tokens denoted as below:

input_tokens = $[x_0, x_1, x_2, …, x_I]$,
where $x_i \in \mathbb{R}$

After transformation by the Transformer matrix, we obtain the query vector, key vector, and value vector as below:

Q = $[q_0, q_1, q_2…., q_I]$

K = $[k0, k1, k2…., k_I]$

V = $[v0, v1, v2, …v_I]$

where $q_i, k_i, v_i \in \mathbb{R}^{d}$, e.g d =4096 for Llama2.

Passing them to the Self-Attention part, we obtain that:

P = $Q^T K \in \mathbb{R}^{I \times I}$

O = $V \cdot Softmax(P)$ = $[O_0, O_1, O_2, ….., O_I]$

where $O_i \in \mathbb{R}^{d}$, and let $O_i = [o_1, o_2, ..., o_{d}]^T$.

Please note that $O_i$ corresponds to the hidden state values at position i. **We used $o$ to represent the hidden state value at a specific dimension**, that is,  **$o_j$ is the j-th element of $O_i$**. 

We assume that at a specific dimension (e.g. $o_j$ or dim j), there is a reasonable and acceptable range for this value. For simplicity, we have assumed a lower bound. If the value in this dimension falls below this lower bound, it could cause abnormal outputs in subsequent layers, ultimately leading to abnormal model behavior. This construction is intended to demonstrate that threshold-based criteria can be used to assess whether extrapolation is successful. 

## About dimensions

We suspect that there might be some confusion about dimensions in our context and canonical basis vectors.

In our context, we use “dimension j” to describe the j-th element of the output vector $O_i$, as stated above . Therefore the concept of canonical basis vectors e_1 and e_{20} is not relevant in our context.

Here we only chose specific examples of dimensions to illustrate the phenomenon of extrapolation failures. We observed that **this behavior is consistent** across different inputs and tasks (passkey, language modeling etc.). By observing the corresponding threshold, we can predict the extrapolation capability of the LLM, which is limited by its maximum pre-training window, regardless of the input.  Given the consistent results across various experimental conditions, we believe our findings have broad implications and are not data-specific.



## About the design of the chunk-based triangular attention

First, our assumption that the beginning tokens and surrounding tokens are important is well-established and has been used in many of the previous works, such as Streaming-LLM and LM-Infinite. And the reasoning is below:

 **Beginning of the sequence:**  1) people often place instructions, task descriptions, etc., at the start of a sentence, which is related to the way prompts are structured. 2) a start token is typically added by default, which is an important position holder. For instance, Llama2 automatically adds a <bos> token at the beginning. We’ve also explained this in detail in the appendix (line 1206-1209).

**Surrounding tokens**: According to the principles of the attention mechanism, attention decreases as the distance increases, meaning the nearby tokens generally receive higher attention scores.

Focusing on the initial tokens and their neighbors has been validated by other previous works (e.g,. LLM-Streaming and LM-Infinite). When designing the chunk-based triangular attention, we also experimented it and found this design to be the most effective. 

Note that Mesa-Extrapolation appends all previous tokens at the bottom of its attention matrix, allowing the last token to attend to all preceding tokens. In contrast, Streaming-LLM and LM-Infinite also discard middle tokens at the bottom of their attention matrix, inevitably resulting in loss of information from these tokens, leading to inferior performance.

If you still have any questions regarding the explanation above, please let us know so that we can provide further clarification.

Once again, thank you very much.
Dear Reviewer hjGM,

Thank you very much for increasing your score. We will express our gratitude for your valuable suggestions in the Acknowledgments section of our paper. 

Additionally, regarding the performance decrease observed in the 32k-128k range, we would like to clarify further:

First, our method can be applied only after 128k, not in the 32k-128k range, because it is inherently a free plug-in approach, and the effective input window of phi3-mini-128k itself can reach up to 128k. 
In practical scenarios, we would adopt our method only when the input exceeds 128k.

Second, we have observed that the phi3-mini-128k model itself experienced a performance drop within the 32k-128k range, as shown on the right of Fig 4 (uploaded PDF), indicating its insufficiency in handling multi-key task within this range. Since our method is designed to assist the model in handling inputs beyond its effective 128k limit, not to enhance the model’s inherent capability, the performance issues beyond 128k are likely due to the inherent limitations of model for the multikey task, not to our method. In contrast, the Fig 4 left (uploaded PDF) shows that the phi3-mini-128k model itself successfully handles the singlekey task within the 128k range. Consequently, our method can extend its maximum effective input window beyond 128k, up to 192k.

We hope our analysis effectively addresses your concerns and contributes to improved score. Please let us know if you have any further questions.

Once again, thank you very much.
Dear Reviewer bJoG,

We greatly appreciate you for recognizing our work.

## the interpretation of Theorem
Thank you for your valuable suggestions to improve the interpretation of the theorems of our paper. We will incorporate your suggestions into the final version of the paper.

## Enhancing Streaming-LLM / LM-Infinite
We believe the question you proposed is very valuable.
To address it, we suggest drawing our Mesa-Extrapolation design to add bottom-level attention for Streaming-LLM and LM-Infinite. Here’s how to add it:

Input Tokens: |--------------------- Context Tokens ---------------------|---------- Last Tokens -------|

#Operations : |<-----------Streaming-LLM / LM-Infinite----------->| <--- Bottom Attention-->| 


The diagram above illustrates how input tokens can be processed by dividing them into two parts: **context tokens** and **last tokens**. 

The context tokens are processed normally using Streaming-LLM or LM-Infinite, with the resulting key/value pairs being cached. When processing the last tokens, the last tokens’ key/value pairs can be appended with the cached key/value pairs(context tokens) to compute the attention using context forwarding (many operators, like Flash Attention, have already implemented this). During this context forwarding, if the keys are too long, the positions can be handled using the Weave PE methods (such as StairPE, ReRoPE, or Leaky-ReRoPE).
We believe this approach can further enhance the capabilities of Streaming-LLM and LM-Infinite.

We hope our responses addresses your questions. We will do our best to answer any further questions you may have before the final discussion deadline arrives.

Once again, thank you very much.
Thank you for the rebuttal. The additional experiments addressed some of my concerns. However, I saw some performance drop between 32k-128k when extending phi3-128k. Therefore, I will increase my rating score to 6 accordingly.
I appreciate the authors’ thorough rebuttal.

The authors have effectively addressed all of my concerns and questions. Additionally, I have reviewed the other reviewers’ comments and the authors’ responses to those as well. Taking all these materials into account, I am increasing my final rating from 5 to 6. I believe the paper meets the criteria for acceptance as a poster presentation.
Thanks, I have read the rebuttal. 

I am still having trouble understanding Assumption 1's "If o > H extrapolation succeeds, if o < H, it fails": so in particular, take H = 100; we are talking about a model which for a sequence of length 10 < H = 100, extrapolation will fail, but with a long sequence of length (say) 100000000000000 > H, extrapolation succeeds. I have a hard time understanding what the assumption means here. 


I am still feeling uncomfortable with the choice of dimensions 1 & 6 out of the top 20 dimensions. I do not see any reason why embedding vectors would be aligned with canonical basis vectors e_1 and e_{20}. I fear that the choices made here are very data specific and hard to reproduce in other setups. 

Another question: in the design of the chunk-based triangular attention, a strong assumption is made that tokens in the middle of the context are related to surrounding tokens and those at the beginning of the sequence. How did we validate this assumption?
Thank you for the rebuttal. I believe the paper is strong and will maintain my positive rating. However, I am not a strong expert in this area, so I will keep my original weak confidence.

It would be helpful if the authors clarified answers to my questions in the revised paper. Specifically, the statement "M is typically related to the maximum training window length of the model" and thus "M can't be controlled to an arbitrarily large number" should be emphasized, as this significantly impacts the interpretation of the theorems.

It's also interesting to observe how adding bottom attention enhances Streaming-LLM and LM-Infinite, especially when middle tokens contain critical information. Analyzing passkey retrieval based on its location could provide valuable insights, particularly if the improvement is most pronounced when the passkey is in the middle.
Dear Reviewer bJoG,

We sincerely appreciate your positive feedback, and it is incredibly gratifying to have our work highly recognized by you.

As the discussion progresses, if you have additional questions, please let us know, and we will be happy to provide further clarification.

We will express our deep gratitude to you in the Acknowledgments section of our paper.

Once again, thank you very much.
Dear Reviewer hjGM,

Thank you for your valuable suggestions and the time you’ve dedicated to our paper.

As the discussion period draws to a close, we would like to know if our responses have addressed your concerns.

Following your suggestion, we have conducted verification on phi3-mini-128k, which significantly enhance the impact of our approach.

If our responses have resolved your concerns, we would greatly appreciate it if you could raise your score to a clear "accept".

Once again, thank you very much.
Dear Reviewer LfLf,

As the discussion time goes by, we would like to know if our responses have addressed your concerns.

If our responses have resolved your concerns, do you think our paper should now be a clear "accept"?

We are very grateful for your valuable suggestions. If you have additional concerns, please let us know so that we can address them and further improve the quality of our paper.

Once again, thank you very much.
Dear Reviewer PZAX,

As Discussion Period progresses, we would like to know if our responses have addressed your concerns. 

We believe our responses address all of your main concerns; if they do, we would very appreciate it if you raised your score accordingly. 

If not, please let us know so that we can address any serious concerns that you might still have.

Once again, thank you very much.
Dear Reviewer vMAr,

Thank you very much for raising your score. We will express our gratitude for your valuable suggestions in the Acknowledgments Section of our paper.

If you have additional concerns, please let us know.

Once again, we thank you very sincerely.
Dear Authors,

Thank you very much for your reply. As the authors do not claim star pe as their contribution so that my concern of plagiarism is partially solved. Therefore, I increase the score from 4 to 5 and the confidence from 4 to 5.
## The detailed comparison of the formulas on Stair PE and Self-Extend

The formulation of Self-Extend is as follows:

let `t` denote the position of query, `i` denote the position of key, `W` denote the neighbor size and `G` denote group size.

According to their paper’s equation (3) , `P = P // G`, and the shifted relative position (`W - W // G`), we can get the position of query as:

`t // G + W - W // G                                                      (Equ.1)`

and the position of key as:

`i // G                                                                  (Equ.2)`

By RoPE, their relative position between `t` and `i` (consider `t > i`), is remapped to:

`t // G + W - W // G  -  i // G  =  W + t // G -  i // G - W // G                (Equ.3)`

**Note this equation is slightly different from your equation in Concern 2**, which is `W + (t-i) // G - W // G`. **We would like to clarify that only under** `t % G >= i % G` **(necessary and sufficient conditions)**, we get `t // G - i // G` is equal to `(t-i) // G`. 


Next, when `W % G == 0`, the equation of self-extend becomes:

`W + (t-i) // G - W //G = W + (t-i-W) // G `

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 `t % G >= i % G` and `W % G == 0`, as well as changing the flooring operation to ceiling operartion in Self-Extend, these two formulas are equivalent. 
Except for this condition, they yield slightly different results.

Note because `W` and `G` are constants, the condition `W % G == 0` can be met easily. But **`i` and `t` change with positions**, therefore there will always be positions where the condition **`t % G >= i % G`** is not satisfied.

For example, `t = 10, i = 5, G = 2`, `10 // 2 - 5 // 2 != (10-5)//2`.

This is why, as shown in the uploaded PDF(see fig 6), the relative positions differ between Self-Extend and Stair PE at certain positions (when `t % G < i % G` ).  Specifically, in Stair PE, the relative positions on the diagonal of the matrix always remain the same. In contrast, the diagonal values of the attention matrix in self-extend are not always the same.

We will add discussions to the final version of our paper in appendix. 

Despite these subtle differences, we agree with your point that their core idea are the same.

We are very grateful for your valuable suggestions and insightful observations, which have helped us think more deeply about their relationship. If you believe there are any issues with our analysis or have other concerns that haven't been addressed, please let us know, and we will make further improvements to enhance the quality of our work. 

Once again, thank you very much.
Dear Reviewer  vMAr,

Thank you very much for your valuable suggestions, which have been immensely helpful in improving the quality of our paper.
We apologize for not fully addressing your concerns, and provide further explanations in hope of clarifying a few details as mentioned.

## Rethink the relation between Star PE and Self-Extend
Based on careful examination of the respective resulting PEs, we conclude that the two methods yield similar outcomes. For example, under specific conditions (`t % G >= i % G`), your equations in concern 2 are valid and the resulting PEs are indeed equivalent. However, slight discrepancies between the resulting PEs emerge when such conditions are not met. We provide a detailed comparison at the end of this response. 

SelfExtend is a very recent work (published in July 2024), after our paper submission and current review process. And despite the striking similarities in the final PE results, our independent thought process was entirely different: We directly defined relative positions in Stair PE; while Self-Extend is defined by the original positions of query and key through group attention and neighbor attention. 

Furthermore, our theoretical contribution, as well as the novelty and effect of the Chunk-based Triangular Attention Matrix are valid and we believe add value to this field of study on LLM extrapolation. 

We will diligently articulate and clarify the relationship between Stair PE and Self-Extend in the revised version of the paper.


## Rewrite the part of Stair PE 
As advised, we will rewrite the Stair PE part (Section 4.1) in the final version, drafted as follows:

“While our work was conducted independently, we note that Jin et al. 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 (See appendix). Consequently, Self-Extend can be categorized as a Weave PE method. Our proposed Chunk-based Triangular Attention Matrix (detailed in Section 4.2) and its corresponding theoretical properties (Section 4.4) are also applicable to this parallel approach. ”




## Our Contribution

Following your suggestions, we will not specifically claim Stair PE as our main contribution in the paper. **Note in our introduction (line 45-60), we did not specifically claim Stair PE as our contribution either**. To further clarify, we will rewrite our claims as the following:

1.Theoretical Analysis: We provide a theoretical framework that explains extrapolation.

2.Introduction of Mesa-Extrapolation: which seamlessly integrates chunk-based triangular attention matrix and a Weave PE method (e.g. Stair PE). 

3.Experimental Validation to showcase the effectiveness of Mesa-Extrapolation on a broad range of tasks.
Dear Authors,

Thank you very much for your rebuttal. After reading the author's rebuttal, I still have questions about the contribution of Self-Extend and Star PE.

* After the author's rebuttal, I confirm that the Star PE is equivalent to Self-Extend PE.
   * First, their formulation is equivement, after adjusting floor and ceiling operations. **The core part is the same: increase 1 position number after $E$ steps and begin the operation at the $N^{th}$ step**.
   * Then, the author claims that the Self-Extend PE cannot work on relative positional encoding. However, this is not correct
      * The author may check Figure 2 in the Self-Extend LLM arxiv paper. This paper Figure 2 presents how they process the relative distances between queries and keys. Self-Extend can be directly applied to Alibi, as Alibi only needs to know the relative distance between queries and keys.

* I appreciate the comparison between Mesa-Extropolation between Self-Extend. The result suggests the effectiveness of the Chunk-based Triangular Attention Matrix.

To increase the score, I need the author to 
* Rethink the relation between Star PE and Self-Extend
* Rewrite the part of Star PE.
* Correctly claim the contribution of the paper, while I now have relatively high confidence to say that the Star PE and Self-Extend are equivalent. Therefore, the paper cannot claim that the Star PE is its contribution, while the theoretical analysis can be kept as part of contribution.

Overall, I have to keep the current score and increase my confidence, as the paper contribution Star PE is equivalent to Self-Extend.