mlsanityData to 7 Oct 2026

RoPE Attention Can Be Trained in Almost Linear Time

arXiv 2412.17316 ↗First posted 23 Dec 2024cs.LG cs.AI cs.CCcited by 13

Not on the map. Why?

Abstract (arXiv)

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 n1+o(1) where 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.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 13 of its 26 references that are in the map. First posted on arXiv 23 Dec 2024.

Builds on

13 of 26 references.

References · 13

  1. 2017Attention Is All You Needcited by 59,932
  2. 2023GPT-4 Technical Reportcited by 18,132
  3. 2024The Llama 3 Herd of Modelscited by 14,192
  4. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  5. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  6. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,581
  7. 2024MM1: Methods, Analysis & Insights from Multimodal LLM Pre-trainingcited by 230
  8. 2023Fast Attention Requires Bounded Entriescited by 102
  9. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  10. 2024On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)cited by 39
  11. 2024Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformerscited by 32
  12. 2024The Fine-Grained Complexity of Gradient Computation for Training Large Language Modelscited by 30
1 more
  1. 2024Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Timecited by 22

Built on by

Cited by year

Citing papers per year: 2025: 13.

13 papers.

Sort:

By area:

  1. 2025Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Countingcited by 17
  2. 2025High-Order Matching for One-Step Shortcut Diffusion Modelscited by 15
  3. 2025On Computational Limits of FlowAR Models: Expressivity and Efficiencycited by 10
  4. 2025Theoretical Guarantees for High Order Trajectory Refinement in Generative Flowscited by 9
  5. 2025Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transformcited by 9
  6. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  7. 2025Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretrainingcited by 6
  8. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  9. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
  10. 2025CoVE: Compressed Vocabulary Expansion Makes Better LLM-based Recommender Systemscited by 3
  11. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  12. 2025Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiencycited by 2
1 more
  1. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0