mlsanityData to 7 Oct 2026

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems

arXiv 2402.12875 ↗First posted 20 Feb 2024cs.LG cs.CC stat.MLcited by 256

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

Abstract (arXiv)

Instructing the model to generate a sequence of intermediate steps, a.k.a., a chain of thought (CoT), is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. However, the mechanism behind CoT remains unclear. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness. Conceptually, CoT empowers the model with the ability to perform inherently serial computation, which is otherwise lacking in transformers, especially when depth is low. Given input length n, previous works have shown that constant-depth transformers with finite precision mathsfpoly(n) embedding size can only solve problems in mathsfTC0 without CoT. We first show an even tighter expressiveness upper bound for constant-depth transformers with constant-bit precision, which can only solve problems in mathsfAC0, a proper subset of mathsfTC0. However, with T steps of CoT, constant-depth transformers using constant-bit precision and O(log n) embedding size can solve any problem solvable by boolean circuits of size T. Empirically, enabling CoT dramatically improves the accuracy for tasks that are hard for parallel computation, including the composition of permutation groups, iterated squaring, and circuit value problems, especially for low-depth transformers.

Key facts. Cited by 256 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 45 of its 75 references that are in the map. First posted on arXiv 20 Feb 2024.

Builds on

45 of 75 references.

Closest ancestors · 10

Same direction, newest first

  1. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective24 May
  2. 2022Towards Understanding Chain-of-Thought Prompting: An Empirical Study of What Matters20 Dec
  3. 2022Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks22 Nov
  4. 2022Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them17 Oct
  5. 2022A Logic for Expressing Log-Precision Transformers6 Oct
  6. 2022Text and Patterns: For Effective Chain of Thought, It Takes Two to Tango16 Sep
  7. 2022Large Language Models are Zero-Shot Reasoners24 May
  8. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Models21 May
  9. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Models21 Mar
  10. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 35

  1. 2023GPT-4 Technical Reportcited by 18,132
  2. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  3. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  4. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,355
  5. 2016Layer Normalizationcited by 5,579
  6. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,304
  7. 2022Scaling Instruction-Finetuned Language Modelscited by 2,997
  8. 2022Solving Quantitative Reasoning Problems with Language Modelscited by 1,359
  9. 2023PaLM 2 Technical Reportcited by 1,154
  10. 2022Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 smallcited by 1,130
  11. 2019BERT Rediscovers the Classical NLP Pipelinecited by 1,046
  12. 2019What Does BERT Look At? An Analysis of BERT's Attentioncited by 994
23 more
  1. 2020On Layer Normalization in the Transformer Architecturecited by 906
  2. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  3. 2023Multimodal Chain-of-Thought Reasoning in Language Modelscited by 740
  4. 2022Large Language Models Can Self-Improvecited by 656
  5. 2017Program Induction by Rationale Generation : Learning to Solve and Explain Algebraic Word Problemscited by 642
  6. 2022PAL: Program-aided Language Modelscited by 635
  7. 2021Prompt Programming for Large Language Models: Beyond the Few-Shot Paradigmcited by 599
  8. 2022Language Models are Multilingual Chain-of-Thought Reasonerscited by 518
  9. 2023MM-REACT: Prompting ChatGPT for Multimodal Reasoning and Actioncited by 511
  10. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  11. 2022Transformers Learn Shortcuts to Automatacited by 260
  12. 2022Can language models learn from explanations in context?cited by 248
  13. 2023Looped Transformers as Programmable Computerscited by 224
  14. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  15. 2021Thinking Like Transformerscited by 182
  16. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  17. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  18. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  19. 2022Towards Efficient and Scalable Sharpness-Aware Minimizationcited by 129
  20. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  21. 2022Compositional Semantic Parsing with Large Language Modelscited by 95
  22. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  23. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 54; 2025: 127; 2026: 75.

256 papers.

Sort:

By area:

  1. 2024Training Large Language Models to Reason in a Continuous Latent Spacecited by 763
  2. 2024GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Modelscited by 533
  3. 2025Reasoning with Latent Thoughts: On the Power of Looped Transformerscited by 223
  4. 2025Chain of Thought Monitorability: A New and Fragile Opportunity for AI Safetycited by 222
  5. 2025CODI: Compressing Chain-of-Thought into Continuous Space via Self-Distillationcited by 216
  6. 2025A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?cited by 215
  7. 2025When More is Less: Understanding Chain-of-Thought Length in LLMscited by 182
  8. 2024Distilling System 2 into System 1cited by 152
  9. 2025RM-R1: Reward Modeling as Reasoningcited by 149
  10. 2024O1 Replication Journey: A Strategic Progress Report -- Part 1cited by 140
  11. 2025LLM Post-Training: A Deep Dive into Reasoning Large Language Modelscited by 129
  12. 2025Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thoughtcited by 108
38 more
  1. 2024Self-Improvement in Language Models: The Sharpening Mechanismcited by 102
  2. 2024MMSearch: Benchmarking the Potential of Large Models as Multi-modal Search Enginescited by 98
  3. 2025Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignmentcited by 91
  4. 2025Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoningcited by 87
  5. 2025When Chain of Thought is Necessary, Language Models Struggle to Evade Monitorscited by 81
  6. 2024Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalizationcited by 78
  7. 2025Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thoughtcited by 73
  8. 2025A Survey on Latent Reasoningcited by 71
  9. 2025On the Emergence of Position Bias in Transformerscited by 57
  10. 2024Unlocking the Capabilities of Thought: A Reasoning Boundary Framework to Quantify and Optimize Chain-of-Thoughtcited by 56
  11. 2025QuestBench: Can LLMs ask the right question to acquire information in reasoning tasks?cited by 56
  12. 2025Training Strategies for Efficient Embodied Reasoningcited by 53
  13. 2025A Survey on Large Language Models for Mathematical Reasoningcited by 52
  14. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 49
  15. 2025Crosslingual Reasoning through Test-Time Scalingcited by 46
  16. 2024Theoretical limitations of multi-layer Transformercited by 43
  17. 2025A Survey of Test-Time Compute: From Intuitive Inference to Deliberate Reasoningcited by 40
  18. 2025Long-Short Chain-of-Thought Mixture Supervised Fine-Tuning Eliciting Efficient Reasoning in Large Language Modelscited by 37
  19. 2025MesaNet: Sequence Modeling by Locally Optimal Test-Time Trainingcited by 37
  20. 2024Understanding Chain-of-Thought in LLMs through Information Theorycited by 36
  21. 2025Much Ado About Noising: Dispelling the Myths of Generative Robotic Controlcited by 35
  22. 2025OctoNav: Towards Generalist Embodied Navigationcited by 33
  23. 2025Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thoughtcited by 32
  24. 2024How Much Can RAG Help the Reasoning of LLM?cited by 31
  25. 2025PENCIL: Long Thoughts with Short Memorycited by 31
  26. 2024How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehensioncited by 30
  27. 2025The Curse of CoT: On the Limitations of Chain-of-Thought in In-Context Learningcited by 30
  28. 2024Counting Ability of Large Language Models and Impact of Tokenizationcited by 29
  29. 2025Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMscited by 29
  30. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 28
  31. 2025Entropy-based Exploration Conduction for Multi-step Reasoningcited by 28
  32. 2024Critic-CoT: Boosting the reasoning abilities of large language model via Chain-of-thoughts Criticcited by 27
  33. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  34. 2024Non-myopic Generation of Language Models for Reasoning and Planningcited by 25
  35. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  36. 2025Back Attention: Understanding and Enhancing Multi-Hop Reasoning in Large Language Modelscited by 23
  37. 2025Encode, Think, Decode: Scaling test-time reasoning with recursive latent thoughtscited by 23
  38. 2025On the Emergence of Thinking in LLMs I: Searching for the Right Intuitioncited by 22

50 most cited of 256 All 256 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2023The Expressive Power of Transformers with Chain of Thought
  2. 2025Latent Chain-of-Thought? Decoding the Depth-Recurrent Transformer
  3. 2025Softmax Transformers are Turing-Complete
  4. 2026The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
  5. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
  6. 2026Quantifying the Necessity of Chain of Thought through Opaque Serial Depth
  7. 2026Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity
  8. 2024Understanding Hidden Computations in Chain-of-Thought Reasoning