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

arXiv: https://arxiv.org/abs/2607.07423 · HTML: https://mlsanity.com/paper/2607.07423/

## Key facts

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

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 11 of 11)

- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)
- [PENCIL: Long Thoughts with Short Memory](https://mlsanity.com/paper/2503.14337/) (2025)
- [The Optimal Sample Complexity of Multiclass and List Learning](https://mlsanity.com/paper/2604.24749/) (2026)
- [Recursive Models for Long-Horizon Reasoning](https://mlsanity.com/paper/2603.02112/) (2026)
- [Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End](https://mlsanity.com/paper/2604.12013/) (2026)
- [An Optimal Sauer Lemma Over k-ary Alphabets](https://mlsanity.com/paper/2604.12952/) (2026)
- [Verify to Amplify: Improving Reasoning via Learned Chain-of-Thought Verification](https://mlsanity.com/paper/2603.03538/) (2026)
- [A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning](https://mlsanity.com/paper/2605.06819/) (2026)

## Built on by (most cited first, 2 of 2)

- [Stochastic Autoregressive Learning](https://mlsanity.com/paper/2608.07224/) (2026)
- [The Surprising Expressivity of a Single Neuron with Autoregressive Chain-of-Thought](https://mlsanity.com/paper/2610.17283/) (2026)

## 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.