mlsanityData to 7 Oct 2026

On Limitations of the Transformer Architecture

arXiv 2402.08164 ↗First posted 13 Feb 2024stat.ML cs.AI cs.LGcited by 63

Not on the map. Why?

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.

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

Builds on

14 of 21 references.

References · 14

  1. 2017Attention Is All You Needcited by 59,932
  2. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  3. 2022Survey of Hallucination in Natural Language Generationcited by 2,056
  4. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  5. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  6. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  7. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  8. 2023Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solvecited by 175
  9. 2023Representational Strengths and Limitations of Transformerscited by 132
  10. 2023Calibrated Language Models Must Hallucinatecited by 114
  11. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  12. 2023Mitigating Large Language Model Hallucinations via Autonomous Knowledge Graph-based Retrofittingcited by 70
2 more
  1. 2020How Can Self-Attention Networks Recognize Dyck-n Languages?cited by 51
  2. 2022Memory Bounds for Continual Learningcited by 18

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 14; 2025: 30; 2026: 19.

63 papers.

Sort:

By area:

  1. 2024GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Modelscited by 533
  2. 2024Mamba-360: Survey of State Space Models as Transformer Alternative for Long Sequence Modelling: Methods, Applications, and Challengescited by 63
  3. 2024DocETL: Agentic Query Rewriting and Evaluation for Complex Document Processingcited by 49
  4. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  5. 2024Theoretical limitations of multi-layer Transformercited by 43
  6. 2024Large Language Models for UAVs: Current State and Pathways to the Futurecited by 33
  7. 2024One-layer transformers fail to solve the induction heads taskcited by 30
  8. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
  9. 2024When Can Transformers Count to n?cited by 22
  10. 2025Density Measures for Language Generationcited by 20
  11. 2025Skip a Layer or Loop it? Test-Time Depth Adaptation of Pretrained LLMscited by 14
  12. 2025Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizationscited by 13
38 more
  1. 2024The Asymptotic Behavior of Attention in Transformerscited by 12
  2. 2025Strassen Attention, Split VC Dimension and Compositionality in Transformerscited by 12
  3. 2025Lost in Cultural Translation: Do LLMs Struggle with Math Across Cultural Contexts?cited by 9
  4. 2025Procedural Memory Is Not All You Need: Bridging Cognitive Gaps in LLM-Based Agentscited by 9
  5. 2025Lost in Transmission: When and Why LLMs Fail to Reason Globallycited by 9
  6. 2025The Role of Sparsity for Length Generalization in Transformerscited by 8
  7. 2025Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformerscited by 8
  8. 2024How language models extrapolate outside the training data: A case study in Textualized Gridworldcited by 7
  9. 2025Comprehension Without Competence: Architectural Limits of LLMs in Symbolic Computation and Reasoningcited by 7
  10. 2025Ehrenfeucht-Haussler Rank and Chain of Thoughtcited by 6
  11. 2025Transformers Meet In-Context Learning: A Universal Approximation Theorycited by 4
  12. 2025Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Trainingcited by 4
  13. 2024Compositional Hardness of Code in Large Language Models -- A Probabilistic Perspectivecited by 3
  14. 2024Lower bounds on transformers with infinite precisioncited by 3
  15. 2025A completely uniform transformer for paritycited by 3
  16. 2025Are Transformers Able to Reason by Connecting Separated Knowledge in Training Data?cited by 3
  17. 2025The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architecturescited by 3
  18. 2025The Narrative Continuity Test: A Conceptual Framework for Evaluating Identity Persistence in AI Systemscited by 3
  19. 2025SMAGDi: Socratic Multi Agent Interaction Graph Distillation for Efficient High Accuracy Reasoningcited by 3
  20. 2026Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidthcited by 3
  21. 2026Expressivity-Efficiency Tradeoffs for Hybrid Sequence Modelscited by 3
  22. 2026How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformerscited by 3
  23. 2025Benchmarking graph construction by large language models for coherence-driven inferencecited by 2
  24. 2025Concise One-Layer Transformers Can Do Function Evaluation (Sometimes)cited by 2
  25. 2025Fast attention mechanisms: a tale of parallelismcited by 2
  26. 2025On the Notion that Language Models Reasoncited by 2
  27. 2024Evaluating and explaining training strategies for zero-shot cross-lingual news sentiment analysiscited by 1
  28. 2025Provably Overwhelming Transformer Models with Designed Inputscited by 1
  29. 2025Three tiers of computation in transformers and in brain architecturescited by 1
  30. 2025DecompSR: A dataset for decomposed analyses of compositional multihop spatial reasoningcited by 1
  31. 2026A model of errors in transformerscited by 1
  32. 2026A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attentioncited by 1
  33. 2026Positional versus Symbolic Attention Heads: Learning Dynamics, RoPE Geometry, and Length Generalizationcited by 1
  34. 2026The Deterministic Horizon: When Extended Reasoning Fails and Tool Delegation Becomes Necessarycited by 1
  35. 2026When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoningcited by 1
  36. 2026Indexing: the Beginning and the Endcited by 1
  37. 2026Attention-based representations for multi-task computationcited by 1
  38. 2024Can adversarial attacks by large language models be attributed?cited by 0

50 most cited of 63 All 63 (JSON)