# On The Computational Complexity of Self-Attention

arXiv: https://arxiv.org/abs/2209.04881 · HTML: https://mlsanity.com/paper/2209.04881/

## Key facts

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

## Builds on (most cited first, 30 of 33)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Flamingo: a Visual Language Model for Few-Shot Learning](https://mlsanity.com/paper/2204.14198/) (2022)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Transformers in Vision: A Survey](https://mlsanity.com/paper/2101.01169/) (2021)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth](https://mlsanity.com/paper/2103.03404/) (2021)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [The Lipschitz Constant of Self-Attention](https://mlsanity.com/paper/2006.04710/) (2020)
- [SOFT: Softmax-free Transformer with Linear Complexity](https://mlsanity.com/paper/2110.11945/) (2021)
- [Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Method](https://mlsanity.com/paper/2111.00035/) (2021)
- [Leveraging redundancy in attention with Reuse Transformers](https://mlsanity.com/paper/2110.06821/) (2021)
- [Hardness of Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1803.00904/) (2018)
- [Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)](https://mlsanity.com/paper/1412.0348/) (2014)
- [Sub-Linear Memory: How to Make Performers SLiM](https://mlsanity.com/paper/2012.11346/) (2020)
- [On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks](https://mlsanity.com/paper/1704.02958/) (2017)
- [Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails](https://mlsanity.com/paper/1404.1448/) (2014)
- [Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping](https://mlsanity.com/paper/1502.01063/) (2015)

## Built on by (most cited first, 30 of 139)

- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [Language Model Tokenizers Introduce Unfairness Between Languages](https://mlsanity.com/paper/2305.15425/) (2023)
- [Efficient Large Language Models: A Survey](https://mlsanity.com/paper/2312.03863/) (2023)
- [The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicry](https://mlsanity.com/paper/2402.04347/) (2024)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [ThunderKittens: Simple, Fast, and Adorable AI Kernels](https://mlsanity.com/paper/2410.20399/) (2024)
- [PolaFormer: Polarity-aware Linear Attention for Vision Transformers](https://mlsanity.com/paper/2501.15061/) (2025)
- [The Fine-Grained Complexity of Gradient Computation for Training Large Language Models](https://mlsanity.com/paper/2402.04497/) (2024)
- [Training Tensor Attention Efficiently: From Cubic to Almost Linear Time](https://mlsanity.com/paper/2405.16411/) (2024)
- [A Canonicalization Perspective on Invariant and Equivariant Learning](https://mlsanity.com/paper/2405.18378/) (2024)
- [LoLCATs: On Low-Rank Linearizing of Large Language Models](https://mlsanity.com/paper/2410.10254/) (2024)
- [MVGamba: Unify 3D Content Generation as State Space Sequence Modeling](https://mlsanity.com/paper/2406.06367/) (2024)
- [Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time](https://mlsanity.com/paper/2408.13233/) (2024)
- [SpeechPrune: Context-aware Token Pruning for Speech Information Retrieval](https://mlsanity.com/paper/2412.12009/) (2024)
- [Do Efficient Transformers Really Save Computation?](https://mlsanity.com/paper/2402.13934/) (2024)
- [Cache What Lasts: Token Retention for Memory-Bounded KV Cache in LLMs](https://mlsanity.com/paper/2512.03324/) (2025)
- [Recurrent Action Transformer with Memory](https://mlsanity.com/paper/2306.09459/) (2023)
- [Nonparametric Modern Hopfield Models](https://mlsanity.com/paper/2404.03900/) (2024)
- [MLPerf Power: Benchmarking the Energy Efficiency of Machine Learning Systems from Microwatts to Megawatts for Sustainable AI](https://mlsanity.com/paper/2410.12032/) (2024)
- [CacheClip: Accelerating RAG with Effective KV Cache Reuse](https://mlsanity.com/paper/2510.10129/) (2025)
- [TrafficGPT: Breaking the Token Barrier for Efficient Long Traffic Analysis and Generation](https://mlsanity.com/paper/2403.05822/) (2024)
- [DyGMamba: Efficiently Modeling Long-Term Temporal Dependency on Continuous-Time Dynamic Graphs with State Space Models](https://mlsanity.com/paper/2408.04713/) (2024)
- [Accelerating Retrieval-Augmented Generation](https://mlsanity.com/paper/2412.15246/) (2024)
- [The Token Tax: Systematic Bias in Multilingual Tokenization](https://mlsanity.com/paper/2509.05486/) (2025)
- [TrimTokenator-LC: Towards Adaptive Visual Token Pruning for Large Multimodal Models with Long Contexts](https://mlsanity.com/paper/2512.22748/) (2025)
- [Exploring the Synergies of Hybrid CNNs and ViTs Architectures for Computer Vision: A survey](https://mlsanity.com/paper/2402.02941/) (2024)
- [Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters](https://mlsanity.com/paper/2408.04093/) (2024)
- [Transformers in Reinforcement Learning: A Survey](https://mlsanity.com/paper/2307.05979/) (2023)
- [MamMIL: Multiple Instance Learning for Whole Slide Images with State Space Models](https://mlsanity.com/paper/2403.05160/) (2024)

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