mlsanityData to 14 Oct 2026

Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective

arXiv 2305.15408 ↗First posted 24 May 2023cs.LG cs.CC cs.CLcited by 294

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

Abstract (arXiv)

Recent studies have discovered that Chain-of-Thought prompting (CoT) can dramatically improve the performance of Large Language Models (LLMs), particularly when dealing with complex tasks involving mathematics or reasoning. Despite the enormous empirical success, the underlying mechanisms behind CoT and how it unlocks the potential of LLMs remain elusive. In this paper, we take a first step towards theoretically answering these questions. Specifically, we examine the expressivity of LLMs with CoT in solving fundamental mathematical and decision-making problems. By using circuit complexity theory, we first give impossibility results showing that bounded-depth Transformers are unable to directly produce correct answers for basic arithmetic/equation tasks unless the model size grows super-polynomially with respect to the input length. In contrast, we then prove by construction that autoregressive Transformers of constant size suffice to solve both tasks by generating CoT derivations using a commonly used math language format. Moreover, we show LLMs with CoT can handle a general class of decision-making problems known as Dynamic Programming, thus justifying its power in tackling complex real-world tasks. Finally, an extensive set of experiments show that, while Transformers always fail to directly predict the answers, they can consistently learn to generate correct solutions step-by-step given sufficient CoT demonstrations.

Key facts. Cited by 294 papers in the map (data through 14 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 42 of its 69 references that are in the map. First posted on arXiv 24 May 2023.

Builds on

42 of 69 references.

Closest ancestors · 4

Same direction, newest first

  1. 2022Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them17 Oct
  2. 2022Automatic Chain of Thought Prompting in Large Language Models7 Oct
  3. 2022Large Language Models are Zero-Shot Reasoners24 May
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 38

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  5. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,326
  6. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,512
  7. 2016Gaussian Error Linear Units (GELUs)cited by 3,502
  8. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,592
  9. 2021Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processingcited by 2,234
  10. 2022BLOOM: A 176B-Parameter Open-Access Multilingual Language Modelcited by 1,984
  11. 2017Decoupled Weight Decay Regularizationcited by 1,831
  12. 2021Scaling Language Models: Methods, Analysis & Insights from Training Gophercited by 1,202
26 more
  1. 2021Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolationcited by 1,103
  2. 2022In-context Learning and Induction Headscited by 964
  3. 2019How Can We Know What Language Models Know?cited by 959
  4. 2021An Explanation of In-context Learning as Implicit Bayesian Inferencecited by 938
  5. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  6. 2022Discovering Latent Knowledge in Language Models Without Supervisioncited by 767
  7. 2022Transformers learn in-context by gradient descentcited by 732
  8. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 715
  9. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 684
  10. 2018Universal Transformerscited by 647
  11. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  12. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 320
  13. 2022Data Distributional Properties Drive Emergent In-Context Learning in Transformerscited by 309
  14. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  15. 2022Transformers Learn Shortcuts to Automatacited by 268
  16. 2023Looped Transformers as Programmable Computerscited by 237
  17. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  18. 2021Thinking Like Transformerscited by 184
  19. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  20. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  21. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  22. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
  23. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  24. 2020O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformerscited by 83
  25. 2022Your Transformer May Not be as Powerful as You Expectcited by 55
  26. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 23; 2024: 105; 2025: 109; 2026: 57.

294 papers.

Sort:

By area:

  1. 2023The Rise and Potential of Large Language Model Based Agents: A Surveycited by 1,439
  2. 2024Training Large Language Models to Reason in a Continuous Latent Spacecited by 797
  3. 2023Think before you speak: Training Language Models With Pause Tokenscited by 264
  4. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  5. 2024Token-Budget-Aware LLM Reasoningcited by 247
  6. 2025Reasoning with Latent Thoughts: On the Power of Looped Transformerscited by 240
  7. 2024Chain-of-Thought Reasoning Without Promptingcited by 210
  8. 2024DeepSeek-Prover-V1.5: Harnessing Proof Assistant Feedback for Reinforcement Learning and Monte-Carlo Tree Searchcited by 197
  9. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Modelscited by 191
  10. 2024The Illusion of State in State-Space Modelscited by 187
  11. 2023Navigate through Enigmatic Labyrinth A Survey of Chain of Thought Reasoning: Advances, Frontiers and Futurecited by 184
  12. 2025When More is Less: Understanding Chain-of-Thought Length in LLMscited by 183
38 more
  1. 2024The pitfalls of next-token predictioncited by 160
  2. 2024O1 Replication Journey: A Strategic Progress Report -- Part 1cited by 143
  3. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  4. 2025Machine Mental Imagery: Empower Multimodal Reasoning with Latent Visual Tokenscited by 124
  5. 2023What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalizationcited by 118
  6. 2025Soft Thinking: Unlocking the Reasoning Potential of LLMs in Continuous Concept Spacecited by 117
  7. 2023Mechanistically analyzing the effects of fine-tuning on procedurally defined taskscited by 115
  8. 2024Chain of Thoughtlessness? An Analysis of CoT in Planningcited by 103
  9. 2023Cumulative Reasoning with Large Language Modelscited by 94
  10. 2025Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoningcited by 91
  11. 2024Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalizationcited by 79
  12. 2025Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thoughtcited by 77
  13. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  14. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 67
  15. 2024RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrievalcited by 64
  16. 2025Reasoning-Augmented Conversation for Multi-Turn Jailbreak Attacks on Large Language Modelscited by 64
  17. 2024On Limitations of the Transformer Architecturecited by 63
  18. 2023Unifying the Perspectives of NLP and Software Engineering: A Survey on Language Models for Codecited by 62
  19. 2024SG-Bench: Evaluating LLM Safety Generalization Across Diverse Tasks and Prompt Typescited by 60
  20. 2023Max-Margin Token Selection in Attention Mechanismcited by 58
  21. 2023Guiding Language Model Reasoning with Planning Tokenscited by 58
  22. 2024Unlocking the Capabilities of Thought: A Reasoning Boundary Framework to Quantify and Optimize Chain-of-Thoughtcited by 56
  23. 2025Training Strategies for Efficient Embodied Reasoningcited by 55
  24. 2024How to think step-by-step: A mechanistic understanding of chain-of-thought reasoningcited by 53
  25. 2023Data-Juicer: A One-Stop Data Processing System for Large Language Modelscited by 52
  26. 2025A Survey on Large Language Models for Mathematical Reasoningcited by 52
  27. 2025Think Before Recommend: Unleashing the Latent Reasoning Power for Sequential Recommendationcited by 51
  28. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 50
  29. 2024GraphArena: Evaluating and Exploring Large Language Models on Graph Computationcited by 49
  30. 2025UAVs Meet LLMs: Overviews and Perspectives Toward Agentic Low-Altitude Mobilitycited by 49
  31. 2024DreamStory: Open-Domain Story Visualization by LLM-Guided Multi-Subject Consistent Diffusioncited by 47
  32. 2024Large Language Models have Intrinsic Self-Correction Abilitycited by 46
  33. 2024Theoretical limitations of multi-layer Transformercited by 45
  34. 2024Disentangling Memory and Reasoning Ability in Large Language Modelscited by 44
  35. 2024Can Graph Learning Improve Planning in LLM-based Agents?cited by 43
  36. 2024Number Cookbook: Number Understanding of Language Models and How to Improve Itcited by 42
  37. 2024RATT: A Thought Structure for Coherent and Correct LLM Reasoningcited by 41
  38. 2025A Survey of Test-Time Compute: From Intuitive Inference to Deliberate Reasoningcited by 40

50 most cited of 294 All 294 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2026Fragile Thoughts: How Large Language Models Handle Chain-of-Thought Perturbations
  2. 2024To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoning
  3. 2026The Potential of CoT for Reasoning: A Closer Look at Trace Dynamics
  4. 2025Teaching LLMs to Think Mathematically: A Critical Study of Decision-Making via Optimization
  5. 2025Chain-of-Thought Tokens are Computer Program Variables
  6. 2024Deciphering the Factors Influencing the Efficacy of Chain-of-Thought: Probability, Memorization, and Noisy Reasoning
  7. 2025Revisiting Chain-of-Thought Prompting: Zero-shot Can Be Stronger than Few-shot
  8. 2022Towards Understanding Chain-of-Thought Prompting: An Empirical Study of What Matters