# On Limitations of the Transformer Architecture

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 21 references that are in the map.
- First posted on arXiv 13 Feb 2024.

## Builds on (most cited first, 14 of 14)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solve](https://mlsanity.com/paper/2309.13638/) (2023)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Calibrated Language Models Must Hallucinate](https://mlsanity.com/paper/2311.14648/) (2023)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Mitigating Large Language Model Hallucinations via Autonomous Knowledge Graph-based Retrofitting](https://mlsanity.com/paper/2311.13314/) (2023)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [Memory Bounds for Continual Learning](https://mlsanity.com/paper/2204.10830/) (2022)

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

- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [Mamba-360: Survey of State Space Models as Transformer Alternative for Long Sequence Modelling: Methods, Applications, and Challenges](https://mlsanity.com/paper/2404.16112/) (2024)
- [DocETL: Agentic Query Rewriting and Evaluation for Complex Document Processing](https://mlsanity.com/paper/2410.12189/) (2024)
- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Large Language Models for UAVs: Current State and Pathways to the Future](https://mlsanity.com/paper/2405.01745/) (2024)
- [One-layer transformers fail to solve the induction heads task](https://mlsanity.com/paper/2408.14332/) (2024)
- [Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers](https://mlsanity.com/paper/2502.02393/) (2025)
- [When Can Transformers Count to n?](https://mlsanity.com/paper/2407.15160/) (2024)
- [Density Measures for Language Generation](https://mlsanity.com/paper/2504.14370/) (2025)
- [The Asymptotic Behavior of Attention in Transformers](https://mlsanity.com/paper/2412.02682/) (2024)
- [Skip a Layer or Loop it? Test-Time Depth Adaptation of Pretrained LLMs](https://mlsanity.com/paper/2507.07996/) (2025)
- [Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations](https://mlsanity.com/paper/2511.05295/) (2025)
- [Strassen Attention, Split VC Dimension and Compositionality in Transformers](https://mlsanity.com/paper/2501.19215/) (2025)
- [Lost in Cultural Translation: Do LLMs Struggle with Math Across Cultural Contexts?](https://mlsanity.com/paper/2503.18018/) (2025)
- [Procedural Memory Is Not All You Need: Bridging Cognitive Gaps in LLM-Based Agents](https://mlsanity.com/paper/2505.03434/) (2025)
- [Lost in Transmission: When and Why LLMs Fail to Reason Globally](https://mlsanity.com/paper/2505.08140/) (2025)
- [Comprehension Without Competence: Architectural Limits of LLMs in Symbolic Computation and Reasoning](https://mlsanity.com/paper/2507.10624/) (2025)
- [The Role of Sparsity for Length Generalization in Transformers](https://mlsanity.com/paper/2502.16792/) (2025)
- [Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers](https://mlsanity.com/paper/2505.21024/) (2025)
- [How language models extrapolate outside the training data: A case study in Textualized Gridworld](https://mlsanity.com/paper/2406.15275/) (2024)
- [Ehrenfeucht-Haussler Rank and Chain of Thought](https://mlsanity.com/paper/2501.12997/) (2025)
- [Transformers Meet In-Context Learning: A Universal Approximation Theory](https://mlsanity.com/paper/2506.05200/) (2025)
- [The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures](https://mlsanity.com/paper/2510.05364/) (2025)
- [SMAGDi: Socratic Multi Agent Interaction Graph Distillation for Efficient High Accuracy Reasoning](https://mlsanity.com/paper/2511.05528/) (2025)
- [Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training](https://mlsanity.com/paper/2511.07372/) (2025)
- [Expressivity-Efficiency Tradeoffs for Hybrid Sequence Models](https://mlsanity.com/paper/2603.08859/) (2026)
- [Compositional Hardness of Code in Large Language Models -- A Probabilistic Perspective](https://mlsanity.com/paper/2409.18028/) (2024)
- [Lower bounds on transformers with infinite precision](https://mlsanity.com/paper/2412.20195/) (2024)
- [A completely uniform transformer for parity](https://mlsanity.com/paper/2501.02535/) (2025)

## Abstract (arXiv)

What are the root causes of hallucinations in large language models (LLMs)? We use Communication Complexity to prove that the Transformer layer is incapable of composing functions (e.g., identify a grandparent of a person in a genealogy) if the domains of the functions are large enough; we show through examples that this inability is already empirically present when the domains are quite small. We also point out that several mathematical tasks that are at the core of the so-called compositional tasks thought to be hard for LLMs are unlikely to be solvable by Transformers, for large enough instances and assuming that certain well accepted conjectures in the field of Computational Complexity are true.