RoPE Attention Can Be Trained in Almost Linear Time
Yang Cao and Jiayan Huo and Yingyu Liang and Zhenmei Shi and Zhao Song · 2024
Read RoPE Attention Can Be Trained in Almost Linear Time by Yang Cao and Jiayan Huo and Yingyu Liang and Zhenmei Shi and Zhao Song (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17316.txt.
Introduction
Yang Cao and co-authors give an almost linear time algorithm for training attention with rotary position embeddings, in a 2024 paper. The rotary method, called RoPE, helps transformers encode where each token sits. It also makes attention sums harder to compute fast. Earlier work found fast algorithms for the forward pass under bounded entries, but the backward pass used in training was left open.
Their algorithm is the first to handle the backward pass in almost linear time under the same conditions. It blends the polynomial method with the fast Fourier transform in a new way. They also derive lower bounds from a standard complexity hypothesis. Those bounds show where the speed-up must stop. The result matters for training large models with long inputs.
Catalog record
| CREATOR | Yang Cao and Jiayan Huo and Yingyu Liang and Zhenmei Shi and Zhao Song |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-17316
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
RoPE Attention Can Be Trained in Almost Linear Time Yang Cao and Jiayan Huo and Yingyu Liang and Zhenmei Shi and Zhao Song Abstract The Rotary Position Embedding (RoPE) mechanism has become a powerful enhancement to the Transformer architecture, which enables models to capture token relationships when encoding positional information. However, the RoPE mechanisms make the computations of attention mechanisms more complicated, which makes efficient algorithms challenging. Earlier research introduced almost linear time algorithms for the forward computation under specific parameter settings of bounded entries (i.e., in time n 1 + o ( 1 ) n^{1+o(1)} where n n is the number of input tokens), but has not addressed backward computation. In this work, we develop the first almost linear time algorithm for backward computations in the RoPE-based attention under bounded entries. Our approach builds on recent advancements in fast RoPE attention computations, utilizing a novel combination of the polynomial method and the Fast Fourier Transform. Furthermore, we show that with lower bounds derived from the Strong Exponential Time Hypothesis (SETH), the bounded entry condition is necessary for subquadratic performance. 1 Introduction The GPT-o3 [ 22 ] , Llama 3.3 [ 20 , 3 ] , Claude 3.5 [ 9 ] are transformed-based Large Language Models (LLMs), have become important tools in natural language processing, which enables applications from machine translation to sentiment analysis. In the Transformer architecture, attention mechanisms, computationally intensive operations, compute token correlations within the sequence [ 26 ] . The efficiency of attention computations, both in forward computations and backward gradient computations, directly influenced the scalability and feasibility of training LLMs, especially when the size and input context length of these LLMs continue to grow [ 6 , 4 ] . In recent research, Rotating Position Embedding (RoPE) [ 23 ] has become a popular modification to the attention mechanism, and it has enabled models to capture positional relationships between tokens with better expressiveness. The RoPE mechanism has been adopted in state-of-the-art models, such as Llama [ 24 , 25 , 20 ] , Claude [ 9 ] , Apple’s LLMs [ 14 , 21 ] , and many others, but the implementation of RoPE complicates attention computation due to the additional structure imposed by position-dependent rotations [ 23 ] . In recent work, [ 5 ] demonstrated an efficient algorithm for forward computation of RoPE attention in the bounded entry regime. However, backward computation, the process of calculating gradients for model optimization, has been explored less. Backward computation introduces additional complexity because it requires the evaluation of gradients that involve non-linear transformations of the attention matrix and positional embeddings. In [ 4 ] , they present their algorithm to approximate forward computations of fast attention with bounded entries using the polynomial methods and low-rank approximation. In [ 7 ] , they propose almost linear time, i.e., n^{1+o(1)} where n is the number of input tokens, an algorithm to compute backward gradients for fast attention with bounded entries. In recent work, [ 5 ] proposes an efficient algorithm to perform the forward computation of RoPE-based attention using the polynomial methods and Fast Fourier Transform. Therefore, it is natural to raise the key question: Can backward computations for the RoPE attention match the efficiency of their forward computations in the bounded entry regime? In this work, we aim to address the question by presenting the first efficient algorithm for backward computation in RoPE attention under the bounded entry. Our main result shows that the backward gradient computations for the RoPE attention match their forward version’s efficiency. Therefore, by leveraging our algorithm in approximating backward computations in the RoPE attention with the forward algorithm from [ 5 ] , we will improve the overall time complexity of RoPE attention to almost linear time with bounded entries. To the best of our knowledge, this is the first work to characterize the fine-grained complexity of backward computations in RoPE attentions, extending prior results on forward computations in RoPE attention [ 5 ] . Our contribution can be described as follows. • We formulated the closed-form gradient for the RoPE attention (see Lemma 4.1 ) along with its exact time complexity (see Theorem 4.2 ). • We derive the almost linear time backward approximation (see Theorem 5.7 ) for RoPE attention based on the closed-form gradient. • We show that with lower bounds derived from the SETH, the bounded entry condition is necessary for subquadratic performance (see Theorem 6.1 ). Roadmap. In Section 2 , we present some relevant papers. In Section 3 , we show essential components for the RoPE attention. Section 4 gives the closed form of the RoPE Attention gradient and discusses the exact time complexity to compute it. Section 5 shows the fast computation of the RoPE Attention gradient in almost linear time. Section 6 details the lower bounds of hardness. Finally, Section 7 provides conclusions and avenues for future work. 2 Related Work Rotary Position Embedding. At a high level, RoPE gives more expressive power to the model in exchange for making the computational problem more complicated. In particular, many prior algorithms, such as the algorithm of [ 4 ] , no longer apply to RoPE for fundamental reasons we will discuss. RoPE was proposed by [ 23 ] and has been used extensively in large-scale industrial models. Examples which are known to use RoPE include the open-source models released by Meta such as Llama [ 24 ] (see page 3), Llama 2 [ 25 ] (see page 5), Llama 3 [ 20 ] (see page 7), and the close-source LLM Claude 3.5 [ 9 ] released by Anthropic. Apple also incorporates RoPE into their LLM architecture (see [ 21 ] , and page 3 of [ 14 ] ). Fast Attention Computation. The attention mechanism has often been criticized for its quadratic computational complexity concerning context length, a challenge that becomes more pronounced as the sequence length grows in today’s LLMs [ 1 , 22 , 20 , 3 , 8 , 9 ] . However, this issue can be addressed using polynomial kernel approximation methods [ 2 ] , which facilitate constructing the approximated attention matrix using low-rank approximations. Such techniques enable substantial improvements in computation speed, allowing a single attention layer to perform both training and inference nearly as fast as linear time [ 4 , 7 ] . [ 18 ] further extends this efficiency to support multi-layer transformer architectures for both training and inference. In addition, these techniques can generalize to advanced attention mechanisms, such as tensor attention, while preserving the almost linear time complexity in both training and evaluation phases [ 6 , 19 ] . Beyond this, alternative theoretical methods also exist. For example, the conv-basis approach introduced in [ 17 ] offers another avenue for speeding up attention computation. Gradient Approximation. Using low-rank approximation to approximate the gradient is a common approach for optimizing the training of transformers by reducing the complexity in the computations, such as [ 18 , 19 , 7 , 15 ] . Specifically, [ 7 ] extends the low-rank approximation technique developed in [ 4 ] , which studies the forward computation of attention to approximate the gradient of the attention computation.