# A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning

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

## Key facts

- Cited by 3 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 15 of its 43 references that are in the map.
- First posted on arXiv 7 May 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, 15 of 15)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)
- [Transformers Provably Solve Parity Efficiently with Chain of Thought](https://mlsanity.com/paper/2410.08633/) (2024)
- [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)
- [CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision](https://mlsanity.com/paper/2505.15927/) (2025)
- [Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End](https://mlsanity.com/paper/2604.12013/) (2026)
- [Deterministic Apple Tasting](https://mlsanity.com/paper/2410.10404/) (2024)
- [The Probably Approximately Correct Learning Model in Computational Learning Theory](https://mlsanity.com/paper/2511.08791/) (2025)
- [Learning to Think from Multiple Thinkers](https://mlsanity.com/paper/2604.24737/) (2026)

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

- [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)

Autoregressive generation lies at the heart of the mechanism of large language models. It can be viewed as the repeated application of a next-token generator: starting from an input string (prompt), the generator is applied for M steps, and the last generated token is taken as the final output. [Joshi et al., 2025] proposed a PAC model for studying the learnability of the input-output maps arising from this process. We develop an online analogue of this framework, focusing on the mistake bound of learning the final output induced by an unknown next-token generator. We distinguish between two forms of feedback. In the End-to-End model, after each round the learner observes only the final token produced after M autoregressive steps. In the Chain-of-Thought model, the learner is additionally shown the entire M-step trajectory. Our goal is to understand how the optimal mistake bound depends on the generation horizon M, and to what extent observing intermediate tokens can reduce this dependence. Our main results show that the online theory of autoregressive learning exhibits a qualitative picture analogous to the statistical one found by [Hanneke et al., 2026], but with a different scale of dependence on the generation horizon. In the End-to-End model, we prove a taxonomy of possible mistake-bound growth rates in the generation horizon M: essentially any rate between constant and logarithmic can arise. We further show that this logarithmic ceiling is unavoidable. In the Chain-of-Thought model, we show that access to the full generated trajectory eliminates the dependence on M altogether. We also analyze autoregressive linear threshold classes, and prove optimal mistake bounds, as well as a new lower bound for the statistical setting. Along the way, our results resolve several questions left open by [Joshi et al., 2025].