mlsanityData to 7 Oct 2026

How does Chain of Thought decompose complex tasks?

arXiv 2604.08872 ↗First posted 10 Apr 2026cs.LG cond-mat.dis-nn cond-mat.stat-mechcited by 0

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

Abstract (arXiv)

Many language tasks can be modeled as classification problems where a large language model (LLM) is given a prompt and selects one among many possible answers. We show that the classification error in such problems scales as a power law in the number of classes. This has a dramatic consequence: the prediction error can be reduced substantially by splitting the overall task into a sequence of smaller classification problems, each with the same number of classes ("degree"). This tree-structured decomposition models chain-of-thought (CoT). It has been observed that CoT-based predictors perform better when they "think", i.e., when they develop a deeper tree, thus decomposing the problem into a larger number of steps. We identify a critical threshold for the degree, below which thinking is detrimental, and above which there exists an optimal depth that minimizes the error. It is impossible to surpass this minimal error by increasing the depth of thinking.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 59 of its 84 references that are in the map. First posted on arXiv 10 Apr 2026.

Builds on

59 of 84 references.

Closest ancestors · 12

Same direction, newest first

  1. 2025A Theory of Learning with Autoregressive Chain of Thought11 Mar
  2. 2025Compositional Reasoning with Transformers, RNNs, and Chain of Thought3 Mar
  3. 2025LLMs Can Easily Learn to Reason from Demonstrations Structure, not content, is what matters!11 Feb
  4. 2025When More is Less: Understanding Chain-of-Thought Length in LLMs11 Feb
  5. 2024Training Large Language Models to Reason in a Continuous Latent Space9 Dec
  6. 2024Mind Your Step (by Step): Chain-of-Thought can Reduce Performance on Tasks where Thinking Makes Humans Worse27 Oct
  7. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Models24 Apr
  8. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Models18 Aug
  9. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective24 May
  10. 2023Why think step by step? Reasoning emerges from the locality of experience7 Apr
  11. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Models21 Mar
  12. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 47

  1. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  2. 2023GPT-4 Technical Reportcited by 18,132
  3. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  4. 2025Qwen3 Technical Reportcited by 8,195
  5. 2020Scaling Laws for Neural Language Modelscited by 6,411
  6. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,146
  7. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,203
  8. 2024Qwen2.5 Technical Reportcited by 4,713
  9. 2023Reflexion: Language Agents with Verbal Reinforcement Learningcited by 4,064
  10. 2025Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilitiescited by 3,655
  11. 2023Let's Verify Step by Stepcited by 3,598
  12. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
35 more
  1. 2016Pointer Sentinel Mixture Modelscited by 2,992
  2. 2019The Curious Case of Neural Text Degenerationcited by 2,881
  3. 2022Do As I Can, Not As I Say: Grounding Language in Robotic Affordancescited by 2,302
  4. 2023PaLM-E: An Embodied Multimodal Language Modelcited by 2,037
  5. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,928
  6. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  7. 2022Competition-Level Code Generation with AlphaCodecited by 1,427
  8. 2022Solving Quantitative Reasoning Problems with Language Modelscited by 1,359
  9. 2025s1: Simple test-time scalingcited by 1,311
  10. 2025Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?cited by 948
  11. 2022Transformers learn in-context by gradient descentcited by 714
  12. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  13. 2025SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-trainingcited by 655
  14. 2023The Internal State of an LLM Knows When It's Lyingcited by 644
  15. 2021ImageNet-21K Pretraining for the Massescited by 607
  16. 2021How to train your ViT? Data, Augmentation, and Regularization in Vision Transformerscited by 562
  17. 2017Deep Learning Scaling is Predictable, Empiricallycited by 556
  18. 2025Beyond the 80/20 Rule: High-Entropy Minority Tokens Drive Effective Reinforcement Learning for LLM Reasoningcited by 540
  19. 2025Stop Overthinking: A Survey on Efficient Reasoning for Large Language Modelscited by 456
  20. 2021Explaining Neural Scaling Lawscited by 353
  21. 2021The Intrinsic Dimension of Images and Its Impact on Learningcited by 307
  22. 2025The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexitycited by 298
  23. 2025Reasoning with Exploration: An Entropy Perspectivecited by 277
  24. 2025Logic-RL: Unleashing LLM Reasoning with Rule-Based Reinforcement Learningcited by 260
  25. 2018Estimating the intrinsic dimension of datasets by a minimal neighborhood informationcited by 246
  26. 2022Why Can GPT Learn In-Context? Language Models Implicitly Perform Gradient Descent as Meta-Optimizerscited by 204
  27. 2021A Universal Law of Robustness via Isoperimetrycited by 150
  28. 2018Does data interpolation contradict statistical optimality?cited by 95
  29. 2025Holistic Agent Leaderboard: The Missing Infrastructure for AI Agent Evaluationcited by 83
  30. 2025Making Slow Thinking Faster: Compressing LLM Chain-of-Thought via Step Entropycited by 37
  31. 2023Taming AI Bots: Controllability of Neural States in Large Language Modelscited by 22
  32. 2022Rethinking Optimization with Differentiable Simulation from a Global Perspectivecited by 21
  33. 2023Studying and improving reasoning in humans and machinescited by 14
  34. 2013The Sense of Place: Grid Cells in the Brain and the Transcendental Number ecited by 12
  35. 2025Long Is More Important Than Difficult for Training Reasoning Modelscited by 11

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026An Asymptotic Theory of Chain-of-Thought in In-Context Learning
  2. 2024On the Empirical Complexity of Reasoning and Planning in LLMs
  3. 2024Chain-of-Thought in Large Language Models: Decoding, Projection, and Activation
  4. 2025CoT is Not True Reasoning, It Is Just a Tight Constraint to Imitate: A Theory Perspective
  5. 2025How does Chain of Thought Think? Mechanistic Interpretability of Chain-of-Thought Reasoning with Sparse Autoencoding
  6. 2023Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting
  7. 2025Chain or tree? Re-evaluating complex reasoning from the perspective of a matrix of thought
  8. 2024Tree of Problems: Improving structured problem solving with compositionality