mlsanityData to 7 Oct 2026

The Expressive Power of Transformers with Chain of Thought

arXiv 2310.07923 ↗First posted 11 Oct 2023cs.LG cs.CC cs.CLcited by 47

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

Abstract (arXiv)

Recent theoretical work has identified surprisingly simple reasoning problems, such as checking if two nodes in a graph are connected or simulating finite-state machines, that are provably unsolvable by standard transformers that answer immediately after reading their input. However, in practice, transformers' reasoning can be improved by allowing them to use a "chain of thought" or "scratchpad", i.e., generate and condition on a sequence of intermediate tokens before answering. Motivated by this, we ask: Does such intermediate generation fundamentally extend the computational power of a decoder-only transformer? We show that the answer is yes, but the amount of increase depends crucially on the amount of intermediate generation. For instance, we find that transformer decoders with a logarithmic number of decoding steps (w.r.t. the input length) push the limits of standard transformers only slightly, while a linear number of decoding steps, assuming projected pre-norm (a slight generalization of standard pre-norm), adds a clear new ability (under standard complexity conjectures): recognizing all regular languages. Our results also imply that linear steps keep transformer decoders within context-sensitive languages, and polynomial steps with generalized pre-norm make them recognize exactly the class of polynomial-time solvable problems -- the first exact characterization of a type of transformers in terms of standard complexity classes. Together, this provides a nuanced framework for understanding how the length of a transformer's chain of thought or scratchpad impacts its reasoning power.

Key facts. Cited by 47 papers in the map (data through 7 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 19 of its 27 references that are in the map. First posted on arXiv 11 Oct 2023.

Builds on

19 of 27 references.

Closest ancestors · 3

Same direction, newest first

  1. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective24 May
  2. 2022A Logic for Expressing Log-Precision Transformers6 Oct
  3. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 16

  1. 2019Root Mean Square Layer Normalizationcited by 1,425
  2. 2020On Layer Normalization in the Transformer Architecturecited by 906
  3. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  4. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  5. 2022Transformers Learn Shortcuts to Automatacited by 260
  6. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  7. 2021Thinking Like Transformerscited by 182
  8. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  9. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  10. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  11. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  12. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65
4 more
  1. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 65
  2. 2023Memory Augmented Large Language Models are Computationally Universalcited by 45
  3. 2020Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descentcited by 40
  4. 2020On the Linguistic Capacity of Real-Time Counter Automatacited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 12; 2025: 18; 2026: 17.

47 papers.

Sort:

By area:

  1. 2024CRUXEval: A Benchmark for Code Reasoning, Understanding and Executioncited by 294
  2. 2025Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thoughtcited by 108
  3. 2024Transformers, parallel computation, and logarithmic depthcited by 75
  4. 2025Efficient Reasoning with Hidden Thinkingcited by 72
  5. 2025Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thoughtcited by 32
  6. 2025PENCIL: Long Thoughts with Short Memorycited by 31
  7. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 28
  8. 2024Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methodscited by 27
  9. 2024On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoningcited by 26
  10. 2024Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modelingcited by 25
  11. 2024Instance-adaptive Zero-shot Chain-of-Thought Promptingcited by 25
  12. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
35 more
  1. 2025On the Emergence of Thinking in LLMs I: Searching for the Right Intuitioncited by 22
  2. 2025Emergence of Superposition: Unveiling the Training Dynamics of Chain of Continuous Thoughtcited by 16
  3. 2024A Hopfieldian View-based Interpretation for Chain-of-Thought Reasoningcited by 15
  4. 2024Lessons from Studying Two-Hop Latent Reasoningcited by 15
  5. 2025Generative AI Act II: Test Time Scaling Drives Cognition Engineeringcited by 14
  6. 2025Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalizationcited by 12
  7. 2026Do Latent-CoT Models Think Step-by-Step? A Mechanistic Study on Sequential Reasoning Taskscited by 10
  8. 2025Revisiting Test-Time Scaling: A Survey and a Diversity-Aware Method for Efficient Reasoningcited by 8
  9. 2025Benefits and Limitations of Communication in Multi-Agent Reasoningcited by 7
  10. 2024Exploring the Limitations of Mamba in COPY and CoT Reasoningcited by 6
  11. 2025Reasoning Efficiently Through Adaptive Chain-of-Thought Compression: A Self-Optimizing Frameworkcited by 6
  12. 2026Are Latent Reasoning Models Easily Interpretable?cited by 6
  13. 2026Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Datacited by 5
  14. 2026Not All LLM Reasoning is Visible in the Chain-of-Thoughtcited by 5
  15. 2024BBA: Bi-Modal Behavioral Alignment for Reasoning with Large Vision-Language Modelscited by 4
  16. 2024On the Benefits of Rank in Attention Layerscited by 4
  17. 2025DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMscited by 4
  18. 2025Typed Chain-of-Thought: A Curry-Howard Framework for Verifying LLM Reasoningcited by 3
  19. 2025Reasoning-Intensive Regressioncited by 2
  20. 2025ORION: Teaching Language Models to Reason Efficiently in the Language of Thoughtcited by 1
  21. 2026Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Tracescited by 1
  22. 2026The Library Theorem: How External Organization Governs Agentic Reasoning Capacitycited by 1
  23. 2026Measuring AI Reasoning: A Guide for Researcherscited by 1
  24. 2026A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoningcited by 1
  25. 2026When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoningcited by 1
  26. 2026Can Video World Models Track Unobserved World States?cited by 1
  27. 2025On the Thinking-Language Modeling Gap in Large Language Modelscited by 0
  28. 2025The Kinetics of Reasoning: How Chain-of-Thought Shapes Learning in Transformers?cited by 0
  29. 2026Beyond Accuracy: Diagnosing Algebraic Reasoning Failures in LLMs Across Nine Complexity Dimensionscited by 0
  30. 2026Is Code Better Than Language for Algorithmic Reasoningcited by 0
  31. 2026The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thoughtcited by 0
  32. 2026The Disconnect Between Better Descriptive Reasoning Trace Quality and Recommendation Effectivenesscited by 0
  33. 2026Counting on Thinking: Tracing Evidence Integration in Language Modelscited by 0
  34. 2026Why Do Conventional World Models Fail to Learn Cellular Automata?cited by 0
  35. 2026Verification with Transfer: Exact Information Frontiers and Their Price in Callscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
  2. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
  3. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
  4. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
  5. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Models
  6. 2025Exact Expressive Power of Transformers with Padding
  7. 2025To CoT or To Loop? A Formal Comparison Between Chain-of-Thought and Looped Transformers
  8. 2026Protoreasoning in Tiny Transformers