mlsanityData to 14 Oct 2026

A Theory of Learning with Autoregressive Chain of Thought

arXiv 2503.07932 ↗First posted 11 Mar 2025stat.ML cs.AI cs.CCcited by 23

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

Abstract (arXiv)

For a given base class of sequence-to-next-token generators, we consider learning prompt-to-answer mappings obtained by iterating a fixed, time-invariant generator for multiple steps, thus generating a chain-of-thought, and then taking the final token as the answer. We formalize the learning problems both when the chain-of-thought is observed and when training only on prompt-answer pairs, with the chain-of-thought latent. We analyze the sample and computational complexity both in terms of general properties of the base class (e.g. its VC dimension) and for specific base classes such as linear thresholds. We present a simple base class that allows for universal representability and computationally tractable chain-of-thought learning. Central to our development is that time invariance allows for sample complexity that is independent of the length of the chain-of-thought. Attention arises naturally in our construction.

Key facts. Cited by 23 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 24 of its 46 references that are in the map. First posted on arXiv 11 Mar 2025.

Builds on

24 of 46 references.

Closest ancestors · 1

Same direction, newest first

  1. 2023ThoughtSource: A central hub for large language model reasoning data27 Jan

Other references · 23

  1. 2017Attention Is All You Needcited by 60,361
  2. 2023GPT-4 Technical Reportcited by 18,396
  3. 2022Training language models to follow instructions with human feedbackcited by 15,971
  4. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,330
  5. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,371
  6. 2022Scaling Instruction-Finetuned Language Modelscited by 3,024
  7. 2020The Pile: An 800GB Dataset of Diverse Text for Language Modelingcited by 2,411
  8. 2022Solving Quantitative Reasoning Problems with Language Modelscited by 1,392
  9. 2022STaR: Bootstrapping Reasoning With Reasoningcited by 940
  10. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  11. 2014Neural Turing Machinescited by 644
  12. 2023Textbooks Are All You Need II: phi-1.5 technical reportcited by 565
11 more
  1. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  2. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  3. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  4. 2024Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learningcited by 74
  5. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 67
  6. 2020An Equivalence Between Private Classification and Online Predictioncited by 64
  7. 2023Learning to Generate Better Than Your LLMcited by 49
  8. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38
  9. 2023Provable Guarantees for Generative Behavior Cloning: Bridging Low-Level Stability and High-Level Behaviorcited by 33
  10. 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
  11. 2014Complexity theoretic limitations on learning DNF'scited by 21

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 10; 2026: 13.

23 papers.

Sort:

By area:

  1. 2025Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalizationcited by 14
  2. 2025Sample Complexity and Representation Ability of Test-time Scaling Paradigmscited by 12
  3. 2025From Reasoning to Super-Intelligence: A Search-Theoretic Perspectivecited by 9
  4. 2025CoT Information: Improved Sample Complexity under Chain-of-Thought Supervisioncited by 6
  5. 2025On Learning Verifiers and Implications to Chain-of-Thought Reasoningcited by 6
  6. 2026Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Datacited by 6
  7. 2025Online Learning of Neural Networkscited by 5
  8. 2025DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMscited by 5
  9. 2026Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-Endcited by 5
  10. 2026Learning to Reason with Curriculum I: Provable Benefits of Autocurriculumcited by 4
  11. 2025Mistake-bounded online learning with operation capscited by 3
  12. 2026A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoningcited by 3
11 more
  1. 2026Learning to Reason with Curriculum II: Compositional Generalizationcited by 3
  2. 2026When does Chain-of-Thought Help: A Markovian Perspectivecited by 2
  3. 2026When Is Compositional Reasoning Learnable from Verifiable Rewards?cited by 1
  4. 2026Learning through Internalizationcited by 1
  5. 2025Learning to Choose or Choosing to Learn: Best-of-N vs. Supervised Fine-Tuning for Bit String Generationcited by 0
  6. 2025Can Language Models Compose Skills In-Context?cited by 0
  7. 2026How does Chain of Thought decompose complex tasks?cited by 0
  8. 2026A Hierarchical Language Model with Predictable Scaling Laws and Provable Benefits of Reasoningcited by 0
  9. 2026Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexitycited by 0
  10. 2026The Dichotomy Between Pattern Recognition and Step-by-Step Reasoningcited by 0
  11. 2026The Surprising Expressivity of a Single Neuron with Autoregressive Chain-of-Thoughtcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026From Chain-of-Thought to Loops: Non-Autoregressive Latent Reasoning via Looped Transformers
  2. 2025How does Chain of Thought Think? Mechanistic Interpretability of Chain-of-Thought Reasoning with Sparse Autoencoding
  3. 2026On the Cost and Benefit of Chain of Thought: A Learning-Theoretic Perspective
  4. 2026Thinking Without Words: Efficient Latent Reasoning with Abstract Chain-of-Thought
  5. 2023Symbolic Chain-of-Thought Distillation: Small Models Can Also "Think" Step-by-Step
  6. 2026Structural Chain-of-Thought: Reasoning with Executable Computational Graphs
  7. 2024Chain-of-Thought in Large Language Models: Decoding, Projection, and Activation
  8. 2024Generating Chain-of-Thoughts with a Pairwise-Comparison Approach to Searching for the Most Promising Intermediate Thought