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

Ilan Doron-Arad; Idan Mehalel; Elchanan Mossel

cs.LGMay 7, 2026

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

Authors: Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel

Organizations: 1MIT · 2The Hebrew University

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

Explore similar work

Aug 7, 2026cs.LG

Stochastic Autoregressive Learning

Motivated by LLMs, which generate outputs by iteratively sampling from next-token distributions, we introduce a PAC-learning model for binary stochastic autoregressive learning. This generalizes the deterministic autoregressive learning framework of Joshi et al., COLT 2025. In our model, one fixed generator assigns a Bernoulli next-token distribution to every prompt string. Starting from an input prompt, a token is sampled and appended to the prompt; the same generator is then applied again to this expanded prompt; this procedure is repeated for

M

steps. Three forms of supervision are considered: base one-step samples, chain-of-thought (CoT) samples that reveal full random trajectories of length

M

, and end-to-end (e2e) samples that reveal only the final token of length

M

trajectories. For a generator class, we study the minimum number of samples

m_{base}(\varepsilon),m_{CoT}(\varepsilon), m_{e2e}(\varepsilon)

, resp., required to learn the one-step probabilities in the base model, and the final-token probability in the CoT and e2e models, under squared loss error~

\varepsilon

. We show that stochastic autoregressive learning fundamentally differs from the deterministic theory. At scale

\varepsilon

, there is no universal comparison between the three learning tasks: both

m_{CoT}/m_{base}

and

m_{e2e}/m_{CoT}

can be made simultaneously arbitrarily larger than

M/\varepsilon

, the natural analogue for the existing deterministic results. Nevertheless, after altering scales, for every class, CoT learning at scale

\varepsilon

is upper-bounded by base learning at scale

\varepsilon/M^2

, whereas e2e learning at scale

\varepsilon

is upper-bounded, up to logarithmic factors, by

(M/\varepsilon) m_{CoT}(Θ(\varepsilon))

. These dependencies and scales are essentially tight. We complement these bounds by studying dimension

d

logistic functions in our model.

Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel

Autoregressive Model Token-Level Uncertainty Deterministic

Ask PDF

Jul 8, 2026cs.LG

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

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

\mathtt{halt}

and every pointwise

\mathtt{halt}

-halting local class

\mathrm{H}

n_{\mathrm{PAC}}^{\varepsilon,δ}(\operatorname{Roll}_{\mathtt{halt}}(\mathrm{H}))=O((\operatorname{DSdim}(\mathrm{H})+\log(1/δ))/\varepsilon)

, with no dependence on rollout length. The dependence on

\operatorname{DSdim}(\mathrm{H})

is worst-case optimal, since one-step stopping recovers ordinary multiclass learning of

\mathrm{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.

Zhiyuan Li

Optimal Sample Complexity Sample Complexity Autoregressive Rollout

Ask PDF

May 11, 2026cs.LG

Mistake-Bounded Language Generation

We investigate the learning task of language generation in the limit, but shift focus from the traditional time-of-last-mistake metric of a generator's success to a new notion of "mistake-bounded generation." While existing results for language generation in the limit focus on guaranteeing eventual consistency, they are blind to the cumulative error incurred during the learning process. We address this by shifting the goal to minimizing the total number of invalid elements output by a generation algorithm. We establish a formal reduction to the Learning from Correct Demonstrations framework of Joshi et al. (2025), enabling a general recipe for deriving mistake bounds via weighted update rules. For finite classes, we provide an algorithm that simultaneously achieves an optimal last-mistake time of

\mathsf{Cdim}(L)

and a mistake bound of

\lfloor \log_2 |L| \rfloor

, whereas for the non-uniform setting of countably infinite streams of languages, we prove a fundamental trade-off: achieving logarithmic mistakes

O(\log i)

necessarily precludes convergence guarantees established in prior work. Finally, we show that our framework can be extended to accommodate noisy adversaries and guarantee mistake bounds that scale with the adversary's suboptimality.

Jon Kleinberg, Charlotte Peale, Omer Reingold

X-Logsmask

Ask PDF