cs.LGNov 16, 2026

Optimal Autoregressive Chain-of-Thought Learning via Bagging

Authors: Awni Altabaa, John Lafferty, Omar Montasser

Organizations: Department of Statistics and Data Science, Yale University

Abstract

We study how to learn an autoregressive next-token generator f ⁣:Σ⋆→Σf\colonΣ^\star\toΣ from a class F\mathcal{F}, given chain-of-thought (CoT) demonstrations of length TT generated by ff. We present a simple algorithm based on bagging, which outputs a majority vote of generators that are trained to be CoT-consistent on bootstrap samples of the training data. For binary token sets, it achieves the optimal sample complexity of O((dVC+log⁡(1/δ))/ε)O((d_{\mathrm{VC}}+\log(1/δ))/ε), independent of the CoT length TT, where dVCd_{\mathrm{VC}} is the VC dimension of F\mathcal{F}. For finite token sets ΣΣ, the VC dimension is replaced by a multiclass analogue, the Graph dimension dGd_{\mathrm{G}}, and the sample complexity is optimal up to a log⁡∣Σ∣\log|Σ| factor. The number of generators in the majority-vote ensemble is O(log⁡(T/δ))O(\log(T/δ)), and we show that the ensemble can be distilled into a single generator in F\mathcal{F} at the expense of nlog⁡(nT)n\log(nT) unlabeled prompts.

Figures & tables

Explore similar work

Apr 13, 2026

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

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 TT 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 TT, 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 TT. For End-to-End learning, we show that the landscape is remarkably rich: subject to mild conditions, essentially any growth rate r(T)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 TT, 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.
Aug 7, 2026

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 MM steps. Three forms of supervision are considered: base one-step samples, chain-of-thought (CoT) samples that reveal full random trajectories of length MM, and end-to-end (e2e) samples that reveal only the final token of length MM trajectories. For a generator class, we study the minimum number of samples mbase(ε),mCoT(ε),me2e(ε)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 KL divergence. 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 mCoT/mbasem_{CoT}/m_{base} and me2e/mCoTm_{e2e}/m_{CoT} can be made simultaneously arbitrarily larger than M/ε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 ε/M2\varepsilon/M^2, whereas e2e learning at scale ε\varepsilon is upper-bounded, up to logarithmic factors, by (M/ε)mCoT(Θ(ε))(M/\varepsilon) m_{CoT}(Θ(\varepsilon)). These dependencies and scales are essentially tight. We complement these bounds by studying dimension dd logistic functions in our model.
Jul 8, 2026

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 halt\mathtt{halt} and every pointwise halt\mathtt{halt}-halting local class H\mathrm{H}, nPACε,δ(Roll⁡halt(H))=O((DSdim⁡(H)+log⁡(1/δ))/ε)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 DSdim⁡(H)\operatorname{DSdim}(\mathrm{H}) is worst-case optimal, since one-step stopping recovers ordinary multiclass learning of H\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.