mlsanityData to 7 Oct 2026

Faith and Fate: Limits of Transformers on Compositionality

arXiv 2305.18654 ↗First posted 29 May 2023cs.CL cs.AI cs.LGcited by 496

Not on the map. Why?

Cited by 135 in LLM reasoning, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Transformer large language models (LLMs) have sparked admiration for their exceptional performance on tasks that demand intricate multi-step reasoning. Yet, these models simultaneously show failures on surprisingly trivial problems. This begs the question: Are these errors incidental, or do they signal more substantial limitations? In an attempt to demystify transformer LLMs, we investigate the limits of these models across three representative compositional tasks -- multi-digit multiplication, logic grid puzzles, and a classic dynamic programming problem. These tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer. We formulate compositional tasks as computation graphs to systematically quantify the level of complexity, and break down reasoning steps into intermediate sub-procedures. Our empirical findings suggest that transformer LLMs solve compositional tasks by reducing multi-step compositional reasoning into linearized subgraph matching, without necessarily developing systematic problem-solving skills. To round off our empirical study, we provide theoretical arguments on abstract multi-step reasoning problems that highlight how autoregressive generations' performance can rapidly decay with,increased,task,complexity.

Key facts. Cited by 496 papers in the map (data through 7 Oct 2026). Builds on 55 of its 82 references that are in the map. First posted on arXiv 29 May 2023.

Builds on

55 of 82 references.

References · 55

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  3. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  4. 2020Scaling Laws for Neural Language Modelscited by 6,411
  5. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,304
  6. 2023Self-Refine: Iterative Refinement with Self-Feedbackcited by 3,317
  7. 2022Scaling Instruction-Finetuned Language Modelscited by 2,997
  8. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,579
  9. 2022Emergent Abilities of Large Language Modelscited by 2,483
  10. 2022Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language modelscited by 1,970
  11. 2020Shortcut Learning in Deep Neural Networkscited by 1,928
  12. 2022LaMDA: Language Models for Dialog Applicationscited by 1,218
38 more
  1. 2021Scaling Language Models: Methods, Analysis & Insights from Training Gophercited by 1,199
  2. 2021Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolationcited by 1,085
  3. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  4. 2022Galactica: A Large Language Model for Sciencecited by 736
  5. 2017Program Induction by Rationale Generation : Learning to Solve and Explain Algebraic Word Problemscited by 642
  6. 2022Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasetscited by 599
  7. 2020Scaling Laws for Autoregressive Generative Modelingcited by 510
  8. 2023Is ChatGPT a General-Purpose Natural Language Processing Task Solver?cited by 486
  9. 2022PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Changecited by 372
  10. 2022Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thoughtcited by 334
  11. 2022Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoningcited by 331
  12. 2020ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Languagecited by 309
  13. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  14. 2022Draft, Sketch, and Prove: Guiding Formal Theorem Provers with Informal Proofscited by 278
  15. 2022Generating Sequences by Learning to Self-Correctcited by 271
  16. 2020Transformers as Soft Reasoners over Languagecited by 265
  17. 2022Transformers Learn Shortcuts to Automatacited by 260
  18. 2022Towards Understanding Grokking: An Effective Theory of Representation Learningcited by 229
  19. 2022Neural Theory-of-Mind? On the Limits of Social Intelligence in Large LMscited by 220
  20. 2022Exploring Length Generalization in Large Language Modelscited by 204
  21. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  22. 2022Diverse Demonstrations Improve In-context Compositional Generalizationcited by 136
  23. 2023Scaling Laws for Generative Mixed-Modal Language Modelscited by 131
  24. 2022Faithful Reasoning Using Large Language Modelscited by 130
  25. 2022Teaching Algorithmic Reasoning via In-context Learningcited by 111
  26. 2021Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networkscited by 108
  27. 2022Unveiling Transformers with LEGO: a synthetic reasoning taskcited by 105
  28. 2021Neural Algorithmic Reasoningcited by 92
  29. 2023A Tale of Two Circuits: Grokking as Competition of Sparse and Dense Subnetworkscited by 78
  30. 2022NaturalProver: Grounded Mathematical Proof Generation with Language Modelscited by 72
  31. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  32. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65
  33. 2023ChatGPT is a Knowledgeable but Inexperienced Solver: An Investigation of Commonsense Problem in Large Language Modelscited by 63
  34. 2020Limitations of Autoregressive Models and Their Alternativescited by 54
  35. 2020The EOS Decision and Length Extrapolationcited by 46
  36. 2019Location Attention for Extrapolation to Longer Sequencescited by 33
  37. 2020Critical Thinking for Language Modelscited by 31
  38. 2022Unobserved Local Structures Make Compositional Generalization Hardcited by 29

50 most cited of 55 All 55 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 61; 2024: 152; 2025: 136; 2026: 147.

496 papers.

Sort:

By area:

  1. 2025Dream 7B: Diffusion Large Language Modelscited by 515
  2. 2024AgentBoard: An Analytical Evaluation Board of Multi-turn LLM Agentscited by 319
  3. 2025The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexitycited by 298
  4. 2024CRUXEval: A Benchmark for Code Reasoning, Understanding and Executioncited by 294
  5. 2024To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoningcited by 257
  6. 2023Challenges and Applications of Large Language Modelscited by 251
  7. 2023Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Taskscited by 243
  8. 2024From Explicit CoT to Implicit CoT: Learning to Internalize CoT Step by Stepcited by 225
  9. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
  10. 2025ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoningcited by 186
  11. 2024LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworkscited by 178
  12. 2023Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solvecited by 175
38 more
  1. 2023ADaPT: As-Needed Decomposition and Planning with Language Modelscited by 172
  2. 2024Do Large Language Models Latently Perform Multi-Hop Reasoning?cited by 165
  3. 2023LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Proverscited by 161
  4. 2024The pitfalls of next-token predictioncited by 156
  5. 2023Evaluating Correctness and Faithfulness of Instruction-Following Models for Question Answeringcited by 150
  6. 2024On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Taskscited by 137
  7. 2024From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Modelscited by 136
  8. 2023Looped Transformers are Better at Learning Learning Algorithmscited by 135
  9. 2024Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planningcited by 135
  10. 2023AutoMix: Automatically Mixing Language Modelscited by 116
  11. 2024On Memorization of Large Language Models in Logical Reasoningcited by 114
  12. 2023Can Large Language Models Really Improve by Self-critiquing Their Own Plans?cited by 107
  13. 2025Does Math Reasoning Improve General LLM Capabilities? Understanding Transferability of LLM Reasoningcited by 101
  14. 2023DyVal: Dynamic Evaluation of Large Language Models for Reasoning Taskscited by 100
  15. 2024Chain of Thoughtlessness? An Analysis of CoT in Planningcited by 100
  16. 2024RL on Incorrect Synthetic Data Scales the Efficiency of LLM Math Reasoning by Eight-Foldcited by 99
  17. 2023The Generative AI Paradox: "What It Can Create, It May Not Understand"cited by 97
  18. 2023Amortizing intractable inference in large language modelscited by 94
  19. 2023Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinementcited by 89
  20. 2023GPT-4 Doesn't Know It's Wrong: An Analysis of Iterative Prompting for Reasoning Problemscited by 88
  21. 2025Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoningcited by 87
  22. 2024Position: Graph Foundation Models are Already Herecited by 84
  23. 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 82
  24. 2024Beyond Accuracy: Evaluating the Reasoning Behavior of Large Language Models -- A Surveycited by 82
  25. 2024Language Models Still Struggle to Zero-shot Reason about Time Seriescited by 81
  26. 2024Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalizationcited by 78
  27. 2024Hopping Too Late: Exploring the Limitations of Large Language Models on Multi-Hop Queriescited by 78
  28. 2024Transformers Can Do Arithmetic with the Right Embeddingscited by 77
  29. 2024E.T. Bench: Towards Open-Ended Event-Level Video-Language Understandingcited by 68
  30. 2024Alice in Wonderland: Simple Tasks Showing Complete Reasoning Breakdown in State-Of-the-Art Large Language Modelscited by 67
  31. 2023Visual Programming for Zero-shot Open-Vocabulary 3D Visual Groundingcited by 64
  32. 2024On Limitations of the Transformer Architecturecited by 63
  33. 2023Language Models, Agent Models, and World Models: The LAW for Machine Reasoning and Planningcited by 59
  34. 2024Can Language Models Learn to Skip Steps?cited by 59
  35. 2023MR-GSM8K: A Meta-Reasoning Benchmark for Large Language Model Evaluationcited by 57
  36. 2023Positional Description Matters for Transformers Arithmeticcited by 56
  37. 2024Learning to Use Tools via Cooperative and Interactive Agentscited by 54
  38. 2024Self-Consistency Preference Optimizationcited by 50

50 most cited of 496 All 496 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025CryptoX : Compositional Reasoning Evaluation of Large Language Models
  2. 2024How Numerical Precision Affects Arithmetical Reasoning Capabilities of LLMs
  3. 2025Three tiers of computation in transformers and in brain architectures
  4. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Models
  5. 2024Do Efficient Transformers Really Save Computation?
  6. 2025A Survey on Large Language Models with some Insights on their Capabilities and Limitations
  7. 2026Protoreasoning in Tiny Transformers
  8. 2025Large Language and Reasoning Models are Shallow Disjunctive Reasoners