# Fundamental Limitations on Subquadratic Alternatives to Transformers arXiv: https://arxiv.org/abs/2410.04271 ยท HTML: https://mlsanity.com/paper/2410.04271/ ## Key facts - Cited by 9 papers in the map (data through 14 Oct 2026). - Placed in Core SSM architectures for language, one of 10 directions in State-space sequence models (S4, Mamba). - Builds on 51 of its 80 references that are in the map. - First posted on arXiv 5 Oct 2024. ## Placed in - State-space sequence models (S4, Mamba) / [Core SSM architectures for language](https://mlsanity.com/ssm/core-ssm-architectures-for-language/) ## Builds on (most cited first, 30 of 51) - [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) - [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) - [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023) - [End-to-End Object Detection with Transformers](https://mlsanity.com/paper/2005.12872/) (2020) - [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023) - [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020) - [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019) - [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018) - [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (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) - [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017) - [Distributed Representations of Sentences and Documents](https://mlsanity.com/paper/1405.4053/) (2014) - [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020) - [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014) - [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019) - [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022) - [Synthesizer: Rethinking Self-Attention in Transformer Models](https://mlsanity.com/paper/2005.00743/) (2020) - [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021) - [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022) - [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023) - [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023) - [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022) - [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021) - [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021) - [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023) - [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022) - [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023) ## Built on by (most cited first, 9 of 9) - [KV Shifting Attention Enhances Language Modeling](https://mlsanity.com/paper/2411.19574/) (2024) - [Compression Barriers for Autoregressive Transformers](https://mlsanity.com/paper/2502.15955/) (2025) - [Subquadratic Algorithms and Hardness for Attention with Any Temperature](https://mlsanity.com/paper/2505.14840/) (2025) - [The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures](https://mlsanity.com/paper/2510.05364/) (2025) - [Fast attention mechanisms: a tale of parallelism](https://mlsanity.com/paper/2509.09001/) (2025) - [Two Heads Are Better than One: Simulating Large Transformers with Small Ones](https://mlsanity.com/paper/2506.12220/) (2025) - [Block Sparse Flash Attention](https://mlsanity.com/paper/2512.07011/) (2025) - [On the Computational Hardness of Transformers](https://mlsanity.com/paper/2603.11332/) (2026) - [Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention](https://mlsanity.com/paper/2608.11427/) (2026) ## Abstract (arXiv) The Transformer architecture is widely deployed in many popular and impactful Large Language Models. At its core is the attention mechanism for calculating correlations between pairs of tokens. Performing an attention computation takes quadratic time in the input size, and had become the time bottleneck for transformer operations. In order to circumvent this, researchers have used a variety of approaches, including designing heuristic algorithms for performing attention computations faster, and proposing alternatives to the attention mechanism which can be computed more quickly. For instance, state space models such as Mamba were designed to replace attention with an almost linear time alternative. In this paper, we prove that any such approach cannot perform important tasks that Transformer is able to perform (assuming a popular conjecture from fine-grained complexity theory). We focus on document similarity tasks, where one is given as input many documents and would like to find a pair which is (approximately) the most similar. We prove that Transformer is able to perform this task, and we prove that this task cannot be performed in truly subquadratic time by any algorithm. Thus, any model which can be evaluated in subquadratic time - whether because of subquadratic-time heuristics for attention, faster attention replacements like Mamba, or any other reason - cannot perform this task. In other words, in order to perform tasks that (implicitly or explicitly) involve document similarity, one may as well use Transformer and cannot avoid its quadratic running time.