mlsanityData to 14 Oct 2026

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform

arXiv 2505.11892 ↗First posted 17 May 2025cs.LG cs.DScited by 9

Not on the map. Why?

Abstract (arXiv)

The transformer architecture has been widely applied to many machine learning tasks. A main bottleneck in the time to perform transformer computations is a task called attention computation. [Alman and Song, NeurIPS 2023] have shown that in the bounded entry regime, there is an almost linear time algorithm to approximate the attention computation. They also proved that the bounded entry assumption is necessary for a fast algorithm assuming the popular Strong Exponential Time Hypothesis. A new version of transformer which uses position embeddings has recently been very successful. At a high level, position embedding enables the model to capture the correlations between tokens while taking into account their position in the sequence. Perhaps the most popular and effective version is Rotary Position Embedding (RoPE), which was proposed by [Su, Lu, Pan, Murtadha, Wen, and Liu, Neurocomputing 2024]. A main downside of RoPE is that it complicates the attention computation problem, so that previous techniques for designing almost linear time algorithms no longer seem to work. In this paper, we show how to overcome this issue, and give a new algorithm to compute the RoPE attention in almost linear time in the bounded entry regime. (Again, known lower bounds imply that bounded entries are necessary.) Our new algorithm combines two techniques in a novel way: the polynomial method, which was used in prior fast attention algorithms, and the Fast Fourier Transform.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 134 of its 198 references that are in the map. First posted on arXiv 17 May 2025.

Builds on

134 of 198 references.

References · 134

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2023GPT-4 Technical Reportcited by 18,396
  5. 2022Training language models to follow instructions with human feedbackcited by 15,971
  6. 2024The Llama 3 Herd of Modelscited by 14,715
  7. 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,380
  8. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  9. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 13,028
  10. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  11. 2020Score-Based Generative Modeling through Stochastic Differential Equationscited by 9,122
  12. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,326
38 more
  1. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,703
  2. 2021Prefix-Tuning: Optimizing Continuous Prompts for Generationcited by 3,915
  3. 2021The Power of Scale for Parameter-Efficient Prompt Tuningcited by 3,795
  4. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,673
  5. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,512
  6. 2020Longformer: The Long-Document Transformercited by 3,413
  7. 2024Gemini 1.5: Unlocking multimodal understanding across millions of tokens of contextcited by 3,224
  8. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,211
  9. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,598
  10. 2023Stable Video Diffusion: Scaling Latent Video Diffusion Models to Large Datasetscited by 2,581
  11. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  12. 2020Big Bird: Transformers for Longer Sequencescited by 1,684
  13. 2019Generating Long Sequences with Sparse Transformerscited by 1,546
  14. 2019Simplifying Graph Convolutional Networkscited by 1,477
  15. 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
  16. 2021Calibrate Before Use: Improving Few-Shot Performance of Language Modelscited by 1,392
  17. 2020Making Pre-trained Language Models Better Few-shot Learnerscited by 1,256
  18. 2020LightGCN: Simplifying and Powering Graph Convolution Network for Recommendationcited by 1,139
  19. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  20. 2023SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shotcited by 1,121
  21. 2023LIMA: Less Is More for Alignmentcited by 1,100
  22. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  23. 2023LLaMA-Adapter: Efficient Fine-tuning of Language Models with Zero-init Attentioncited by 781
  24. 2022Transformers learn in-context by gradient descentcited by 732
  25. 2019Graph Neural Networks for Social Recommendationcited by 714
  26. 2021Cross-Task Generalization via Natural Language Crowdsourcing Instructionscited by 699
  27. 2023Retentive Network: A Successor to Transformer for Large Language Modelscited by 613
  28. 2023LLaMA-Adapter V2: Parameter-Efficient Visual Instruction Modelcited by 602
  29. 2021CSDI: Conditional Score-based Diffusion Models for Probabilistic Time Series Imputationcited by 582
  30. 2014Convex Optimization: Algorithms and Complexitycited by 575
  31. 2021Linear Transformers Are Secretly Fast Weight Programmerscited by 502
  32. 2024One Step Diffusion via Shortcut Modelscited by 391
  33. 2023Trained Transformers Learn Linear Models In-Contextcited by 337
  34. 2022Demonstrate-Search-Predict: Composing retrieval and language models for knowledge-intensive NLPcited by 318
  35. 2022Black-Box Tuning for Language-Model-as-a-Servicecited by 256
  36. 2024MM1: Methods, Analysis & Insights from Multimodal LLM Pre-trainingcited by 232
  37. 2019Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernelcited by 213
  38. 2023Geometric Latent Diffusion Models for 3D Molecule Generationcited by 186

50 most cited of 134 All 134 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 8; 2026: 1.

9 papers.

  1. 2025T2VWorldBench: A Benchmark for Evaluating World Knowledge in Text-to-Video Generationcited by 19
  2. 2025Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Countingcited by 18
  3. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  4. 2025Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteriacited by 5
  5. 2025Minimalist Softmax Attention Provably Learns Constrained Boolean Functionscited by 4
  6. 2025Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questionscited by 4
  7. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  8. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0
  9. 2026Tracking High-order Evolutions via Cascading Low-rank Fittingcited by 0