mlsanityData to 7 Oct 2026

The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought

arXiv 2607.07423 ↗First posted 8 Jul 2026cs.LG stat.MLcited by 0

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

Abstract (arXiv)

We prove that, in the realizable PAC setting, the sample complexity of exact-trace learning for full autoregressive Chain-of-Thought traces is upper bounded by the standard multiclass rate of the local next-token class, where this rate is governed by the Daniely--Shalev-Shwartz dimension. Under exact-trace loss, one wrong action makes the whole trace incorrect; nevertheless, for every stopping rule mathtthalt and every pointwise mathtthalt-halting local class H, nPACvarepsilon,δ(operatornameRoll_mathtthalt(H))=O((operatornameDSdim(H)+log(1/δ))/varepsilon), with no dependence on rollout length. The dependence on operatornameDSdim(H) is worst-case optimal, since one-step stopping recovers ordinary multiclass learning of H. The proof introduces parity dimension, a rollout-stable refinement of DS dimension based on even pseudo-cubes. It controls one-inclusion density via a low-coordinate spanning theorem on finite restrictions and, unlike DS dimension itself, does not increase under autoregressive rollout. We also show why this detour is necessary: DS dimension can increase under rollout.

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 11 of its 23 references that are in the map. First posted on arXiv 8 Jul 2026.

Builds on

11 of 23 references.

Closest ancestors · 6

Same direction, newest first

  1. 2026A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning7 May
  2. 2026Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End13 Apr
  3. 2025PENCIL: Long Thoughts with Short Memory18 Mar
  4. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems20 Feb
  5. 2023The Expressive Power of Transformers with Chain of Thought11 Oct
  6. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Models21 Mar

Other references · 5

  1. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  2. 2026Recursive Models for Long-Horizon Reasoningcited by 9
  3. 2026The Optimal Sample Complexity of Multiclass and List Learningcited by 8
  4. 2026An Optimal Sauer Lemma Over k-ary Alphabetscited by 4
  5. 2026Verify to Amplify: Improving Reasoning via Learned Chain-of-Thought Verificationcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Tight Sample Complexity of Transformers
  2. 2026Stochastic Autoregressive Learning
  3. 2025A Theory of Learning with Autoregressive Chain of Thought
  4. 2026Sample complexity bounds for categorical Markov random fields via Discrete Diffusions
  5. 2026PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structure
  6. 2025Discrete State Diffusion Models: A Sample Complexity Perspective
  7. 2026Diffusion Models Are Statistically Optimal for Learning Low-Dimensional Multi-Modal Distributions
  8. 2026Recursively Trained Diffusion Models: Limiting Collapse Distribution and Spectral Characterization