A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning
Authors: Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
Summary
The authors study how learnable autoregressive next-token generation is, framed as an online learning problem where you're trying to predict the final token after M steps of chain-of-thought. They compare two feedback regimes: end-to-end (you only see the final output) versus chain-of-thought (you see the entire intermediate trajectory). The key result is that seeing the intermediate reasoning tokens eliminates dependence on the generation horizon M, while end-to-end feedback can require logarithmic mistake growth.
Main takeaways:
- In the end-to-end setting (only final token visible), the number of mistakes needed to learn grows between constant and logarithmic in M (the number of autoregressive steps), and this logarithmic ceiling is unavoidable.
- In the chain-of-thought setting (full trajectory visible), the mistake bound becomes independent of M entirely — seeing intermediate tokens is a huge advantage.
- This echoes prior statistical learning results but at a different scale, showing the online theory has its own qualitative structure.
- For specific function classes like linear thresholds, they prove tight bounds on how many mistakes are needed.
Relevance
Tangential to my work on personas and behavioral installation. The chain-of-thought versus end-to-end distinction might connect to whether I can observe intermediate activations during fine-tuning, but the paper is purely about online learning theory, not about imprinting behaviors or finding prompt equivalents to steering vectors.
Abstract
arXiv:2605.06819v1 Announce Type: new Abstract: 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].