# Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End

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

## Key facts

- Cited by 5 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 9 of its 29 references that are in the map.
- First posted on arXiv 13 Apr 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, 9 of 9)

- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [A Theory of Learning with Autoregressive Chain of Thought](https://mlsanity.com/paper/2503.07932/) (2025)
- [Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization](https://mlsanity.com/paper/2511.07378/) (2025)
- [How Reinforcement Learning After Next-Token Prediction Facilitates Learning](https://mlsanity.com/paper/2510.11495/) (2025)
- [From Reasoning to Super-Intelligence: A Search-Theoretic Perspective](https://mlsanity.com/paper/2507.15865/) (2025)
- [CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision](https://mlsanity.com/paper/2505.15927/) (2025)
- [On Learning Verifiers and Implications to Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.22650/) (2025)
- [Online Learning of Neural Networks](https://mlsanity.com/paper/2505.09167/) (2025)
- [Mistake-bounded online learning with operation caps](https://mlsanity.com/paper/2509.03892/) (2025)

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

- [Learning to Think from Multiple Thinkers](https://mlsanity.com/paper/2604.24737/) (2026)
- [A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning](https://mlsanity.com/paper/2605.06819/) (2026)
- [The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought](https://mlsanity.com/paper/2607.07423/) (2026)
- [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)

Modern large language models generate text autoregressively, producing tokens one at a time. To study the learnability of such systems, Joshi et al. (COLT 2025) introduced a PAC-learning framework for next-token generators, the primitive underlying autoregressive models. In this framework, an unknown next-token generator maps a sequence of tokens to the next token and is iteratively applied for T steps, producing a chain of tokens whose final token constitutes the model's output. The learning task is to learn the input-output mapping induced by this autoregressive process. Depending on the available supervision, training examples may reveal only the final output (End-to-End supervision) or the entire generated chain (Chain-of-Thought supervision). This raises two natural questions: how the sample complexity depends on the generation length T, and how much Chain-of-Thought supervision can reduce this dependence. In this work we give a nearly complete answer to both questions by uncovering a taxonomy of how the sample complexity scales with T. For End-to-End learning, we show that the landscape is remarkably rich: subject to mild conditions, essentially any growth rate r(T) between constant and linear can arise as the sample complexity, and combined with the linear upper bound of Joshi et al., this yields an essentially complete characterization. In contrast, under Chain-of-Thought supervision we show that the sample complexity is independent of T, demonstrating that access to intermediate reasoning steps can eliminate the dependence on the generation length altogether. Our analysis introduces new combinatorial tools, and as corollaries we resolve several open questions posed by Joshi et al. regarding the dependence of learnability on the generation length and the role of Chain-of-Thought supervision.