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

• URL: http://arxiv.org/abs/2605.06819v1
• Date: Thu, 07 May 2026 18:21:05 GMT
• Title: A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning
• Abstract summary: [Joshi et al., 2025] proposed a PAC model for studying the learnability of the input-output maps arising from this process.<n>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.<n>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.
• Score: 14.292982828097465
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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].

Related papers

• Self-Attention as a Covariance Readout: A Unified View of In-Context Learning and Repetition [8.250374560598495]
  Large language models (LLMs) exhibit two behaviours: in-context learning (ICL) and repetitive generation.<n>In both, the model behaves as though it had summarised the context into a population-level statistic and discarded token-level detail.<n>We ask whether this summarisation and forgetting' can be derived from the attention mechanism itself, and answer in the affirmative.
  arXiv  Detail & Related papers  (2026-05-11T12:33:15Z)
• Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End [48.8146191570092]
  Modern large language models generate text autoregressively, producing tokens one at a time.<n>To study the learnability of such systems, Joshi et al. introduced a PAC-learning framework for next-token generators.<n>We give a nearly complete answer to two questions by uncovering a taxonomy of how the sample complexity scales with $T.
  arXiv  Detail & Related papers  (2026-04-13T20:00:13Z)
• Thinking into the Future: Latent Lookahead Training for Transformers [34.73973224120233]
  Autoregressive language models trained with next-token prediction generate text by sampling one discrete token at a time.<n>We introduce latent lookahead, a training strategy that enables models to "think" before generating.<n>We show that latent lookahead substantially outperforms both autoregressive and non-autoregressive baselines on planning tasks such as maze solving, Sudoku, and ProsQA.
  arXiv  Detail & Related papers  (2026-03-03T17:15:42Z)
• Continuous Autoregressive Language Models [56.49239051750678]
  We introduce Continuous Autoregressive Language Models (CALM)<n>CALM uses a high-fidelity autoencoder to compress a chunk of K tokens into a single continuous vector.<n>We develop a comprehensive likelihood-free framework that enables robust training, evaluation, and controllable sampling.
  arXiv  Detail & Related papers  (2025-10-31T17:58:11Z)
• Catch Your Breath: Adaptive Computation for Self-Paced Sequence Production [55.76222360698305]
  We explore a class of supervised training objectives that allow a language model to dynamically and autonomously scale the number of compute steps used for each input token.<n>For any token, the model can request additional compute steps by emitting a don't know> output.<n>We find that the CYB model requests additional steps when doing so improves accuracy, and the model adapts its processing time to token-level complexity and context.
  arXiv  Detail & Related papers  (2025-10-13T21:07:05Z)
• Why Can't Transformers Learn Multiplication? Reverse-Engineering Reveals Long-Range Dependency Pitfalls [54.57326125204404]
  Language models are increasingly capable, yet still fail at a seemingly simple task of multi-digit multiplication.<n>We study why, by reverse-engineering a model that successfully learns multiplication via emphimplicit chain-of-thought'
  arXiv  Detail & Related papers  (2025-09-30T19:03:26Z)
• Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification [50.717692060500696]
  Next-token prediction with the logarithmic loss is a cornerstone of autoregressive sequence modeling.<n>Next-token prediction can be made robust so as to achieve $C=tilde O(H)$, representing moderate error amplification.<n>No computationally efficient algorithm can achieve sub-polynomial approximation factor $C=e(log H)1-Omega(1)$.
  arXiv  Detail & Related papers  (2025-02-18T02:52:00Z)
• Promises and Pitfalls of Generative Masked Language Modeling: Theoretical Framework and Practical Guidelines [74.42485647685272]
  We focus on Generative Masked Language Models (GMLMs) We train a model to fit conditional probabilities of the data distribution via masking, which are subsequently used as inputs to a Markov Chain to draw samples from the model. We adapt the T5 model for iteratively-refined parallel decoding, achieving 2-3x speedup in machine translation with minimal sacrifice in quality.
  arXiv  Detail & Related papers  (2024-07-22T18:00:00Z)
• Toward a Theory of Tokenization in LLMs [26.516041872337887]
  We study tokenization from a theoretical point of view by studying the behavior of transformers on simple data generating processes.<n>We show that even the simplest unigram models (over tokens) learnt by transformers are able to model the probability of sequences drawn from $ktextth$-order Markov sources near optimally.
  arXiv  Detail & Related papers  (2024-04-12T09:01:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.