mlsanityData to 7 Oct 2026

On The Computational Complexity of Self-Attention

arXiv 2209.04881 ↗First posted 11 Sep 2022cs.LG cs.CCcited by 137

Not on the map. Why?

Abstract (arXiv)

Transformer architectures have led to remarkable progress in many state-of-art applications. However, despite their successes, modern transformers rely on the self-attention mechanism, whose time- and space-complexity is quadratic in the length of the input. Several approaches have been proposed to speed up self-attention mechanisms to achieve sub-quadratic running time; however, the large majority of these works are not accompanied by rigorous error guarantees. In this work, we establish lower bounds on the computational complexity of self-attention in a number of scenarios. We prove that the time complexity of self-attention is necessarily quadratic in the input length, unless the Strong Exponential Time Hypothesis (SETH) is false. This argument holds even if the attention computation is performed only approximately, and for a variety of attention mechanisms. As a complement to our lower bounds, we show that it is indeed possible to approximate dot-product self-attention using finite Taylor series in linear-time, at the cost of having an exponential dependence on the polynomial order.

Key facts. Cited by 137 papers in the map (data through 7 Oct 2026). Builds on 33 of its 48 references that are in the map. First posted on arXiv 11 Sep 2022.

Builds on

33 of 48 references.

References · 33

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,456
  4. 2020Language Models are Few-Shot Learnerscited by 32,199
  5. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  6. 2021Swin Transformer: Hierarchical Vision Transformer using Shifted Windowscited by 12,082
  7. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  8. 2022Flamingo: a Visual Language Model for Few-Shot Learningcited by 4,337
  9. 2020Longformer: The Long-Document Transformercited by 3,362
  10. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 1,979
  11. 2020Big Bird: Transformers for Longer Sequencescited by 1,673
  12. 2020Reformer: The Efficient Transformercited by 1,658
21 more
  1. 2020Rethinking Attention with Performerscited by 1,584
  2. 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
  3. 2021Transformers in Vision: A Surveycited by 1,009
  4. 2020Efficient Content-Based Sparse Attention with Routing Transformerscited by 469
  5. 2021Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attentioncited by 468
  6. 2021Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depthcited by 411
  7. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  8. 2021Random Feature Attentioncited by 350
  9. 2020The Lipschitz Constant of Self-Attentioncited by 171
  10. 2021SOFT: Softmax-free Transformer with Linear Complexitycited by 128
  11. 2021Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Methodcited by 61
  12. 2021Leveraging redundancy in attention with Reuse Transformerscited by 33
  13. 2018Hardness of Approximate Nearest Neighbor Searchcited by 19
  14. 2014Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)cited by 18
  15. 2020Sub-Linear Memory: How to Make Performers SLiMcited by 18
  16. 2017On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networkscited by 16
  17. 2014Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH failscited by 6
  18. 2015Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warpingcited by 6
  19. 2015If the Current Clique Algorithms are Optimal, so is Valiant's Parsercited by 4
  20. 2021Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometrycited by 3
  21. 2021Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translationcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 13; 2024: 49; 2025: 42; 2026: 31.

137 papers.

Sort:

By area:

  1. 2022Hungry Hungry Hippos: Towards Language Modeling with State Space Modelscited by 495
  2. 2023Language Model Tokenizers Introduce Unfairness Between Languagescited by 207
  3. 2023Efficient Large Language Models: A Surveycited by 183
  4. 2024The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicrycited by 119
  5. 2023Fast Attention Requires Bounded Entriescited by 102
  6. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  7. 2024ThunderKittens: Simple, Fast, and Adorable AI Kernelscited by 34
  8. 2024The Fine-Grained Complexity of Gradient Computation for Training Large Language Modelscited by 30
  9. 2025PolaFormer: Polarity-aware Linear Attention for Vision Transformerscited by 30
  10. 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 29
  11. 2024A Canonicalization Perspective on Invariant and Equivariant Learningcited by 25
  12. 2024LoLCATs: On Low-Rank Linearizing of Large Language Modelscited by 25
38 more
  1. 2024MVGamba: Unify 3D Content Generation as State Space Sequence Modelingcited by 23
  2. 2024Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Timecited by 22
  3. 2024Do Efficient Transformers Really Save Computation?cited by 20
  4. 2024SpeechPrune: Context-aware Token Pruning for Speech Information Retrievalcited by 20
  5. 2025Cache What Lasts: Token Retention for Memory-Bounded KV Cache in LLMscited by 18
  6. 2023Recurrent Action Transformer with Memorycited by 17
  7. 2024Nonparametric Modern Hopfield Modelscited by 16
  8. 2024TrafficGPT: Breaking the Token Barrier for Efficient Long Traffic Analysis and Generationcited by 15
  9. 2024MLPerf Power: Benchmarking the Energy Efficiency of Machine Learning Systems from Microwatts to Megawatts for Sustainable AIcited by 15
  10. 2024DyGMamba: Efficiently Modeling Long-Term Temporal Dependency on Continuous-Time Dynamic Graphs with State Space Modelscited by 14
  11. 2024Accelerating Retrieval-Augmented Generationcited by 14
  12. 2025CacheClip: Accelerating RAG with Effective KV Cache Reusecited by 14
  13. 2025TrimTokenator-LC: Towards Adaptive Visual Token Pruning for Large Multimodal Models with Long Contextscited by 14
  14. 2024Exploring the Synergies of Hybrid CNNs and ViTs Architectures for Computer Vision: A surveycited by 13
  15. 2024Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusterscited by 13
  16. 2025The Token Tax: Systematic Bias in Multilingual Tokenizationcited by 13
  17. 2024MamMIL: Multiple Instance Learning for Whole Slide Images with State Space Modelscited by 12
  18. 2023Transformers in Reinforcement Learning: A Surveycited by 11
  19. 2025Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolationcited by 11
  20. 2024Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learningcited by 10
  21. 2024Snakes and Ladders: Two Steps Up for VideoMambacited by 10
  22. 2024SIGMA: Selective Gated Mamba for Sequential Recommendationcited by 10
  23. 2026Make Each Token Count: Towards Improving Long-Context Performance with KV Cache Evictioncited by 10
  24. 2024Fundamental Limitations on Subquadratic Alternatives to Transformerscited by 9
  25. 2025Hadamard product in deep learning: Introduction, Advances and Challengescited by 9
  26. 2025Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transformcited by 9
  27. 2025TrimTokenator: Towards Adaptive Visual Token Pruning for Large Multimodal Modelscited by 9
  28. 2024EchoMamba4Rec: Harmonizing Bidirectional State Space Models with Spectral Filtering for Advanced Sequential Recommendationcited by 7
  29. 2024Discrete Diffusion Language Model for Efficient Text Summarizationcited by 7
  30. 2024MambaRecon: MRI Reconstruction with Structured State Space Modelscited by 7
  31. 2024Chimera: A Lossless Decoding Method for Accelerating Large Language Models Inference by Fusing all Tokenscited by 6
  32. 2024TaylorShift: Shifting the Complexity of Self-Attention from Squared to Linear (and Back) using Taylor-Softmaxcited by 6
  33. 2024KuaiFormer: Transformer-Based Retrieval at Kuaishoucited by 6
  34. 2025DeepSeek-Inspired Exploration of RL-based LLMs and Synergy with Wireless Networks: A Surveycited by 6
  35. 2025Scaling Self-Supervised and Cross-Modal Pretraining for Volumetric CT Transformerscited by 6
  36. 2025Everything is Context: Agentic File System Abstraction for Context Engineeringcited by 6
  37. 2026WildCat: Near-Linear Attention in Theory and Practicecited by 6
  38. 2022MiniALBERT: Model Distillation via Parameter-Efficient Recursive Transformerscited by 5

50 most cited of 137 All 137 (JSON)