betaFeedback

WorksComputer Science

Optimal Autoregressive Chain-of-Thought Learning via Bagging

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.

Introduction

Large language models have become one of the most important technologies of recent years, yet the mechanism at their core is strikingly simple: a single next-token predictor is applied repeatedly, and each token the model produces is appended to the context of the next prediction. Such models are most successful when they do not answer immediately, but first generate a sequence of intermediate steps, a chain-of-thought, from which the answer follows [54, 68]. Training on demonstrations of such step-by-step reasoning has become a central ingredient of modern training pipelines. This success raises questions that empirical progress alone cannot settle. How many demonstrations are needed to learn to reason correctly? Does a longer reasoning process make learning harder? And which learning algorithms make the best use of the available data? Addressing these questions calls for a theory of learning tailored to autoregressive generation.

An Autoregressive Learning Model. In the spirit of classical PAC learning theory [66, 64, 17, 65], Joshi et al. [40] introduced an elegant PAC-style framework for studying autoregressive learning, which we adopt throughout. Here, a language model is abstracted as an autoregressive next-token generator f:Σ⋆→Σf : \Sigma^\star\to\Sigma from a class F\mathcal{F}, where Σ\Sigma is a set of tokens. On a prompt x∈Σ⋆x \in\Sigma^\star, the generator produces the token f(1)(x)=f(x)f^{(1)}(x) = f(x), then f(2)(x)=f(x∘f(1)(x))f^{(2)}(x) = f(x \circ f^{(1)}(x)), and so on; after TT steps it has produced the chain-of-thought f(1:T)(x)=(f(1)(x)∘⋯∘f(T)(x))∈ΣTf^{(1:T)}(x) = (f^{(1)}(x) \circ\cdots\circ f^{(T)}(x)) \in\Sigma^T, whose last token is interpreted as the answer. The same generator is used at every step, exactly as a language model applies the same weights to every prefix. Two forms of supervision arise naturally. Under end-to-end supervision, the learner observes prompts with their final answers, while the reasoning that produced them remains hidden. Under chain-of-thought supervision, the subject of this paper, the learner observes the entire chain-of-thought.

Let PP be a distribution over Σ⋆×ΣT\Sigma^\star\times\Sigma^T that is realizable by some f⋆∈Ff_\star\in\mathcal{F}, in the sense that Pr⁡[f⋆(1:T)(x)=y]=1\Pr[f_\star^{(1:T)}(x) = y] = 1. The learner observes nn i.i.d. samples S=((xj,yj))j=1n∼PnS = ((x_j,y_j))_{j=1}^n \sim P^n and outputs a predictor f^:Σ⋆→Σ\hat{f} : \Sigma^\star\to\Sigma, which is then run autoregressively. Its performance is measured by the CoT risk, where the predictor f^\hat{f} must reproduce the entire chain-of-thought, and a single incorrect token renders the output incorrect.1

Pr⁡(x,y)∼P[∃t∈[T]:f^(t)(x)≠yt].(1)\Pr_{(x,y)\sim P}\left[\exists t \in[T] : \hat{f}^{(t)}(x) \ne y_t\right]. \tag*{(1)}

The goal is to determine the sample complexity of this problem as a function of the accuracy ε\varepsilon, the confidence δ\delta, the CoT length TT, and the complexity of the class F\mathcal{F}. Moreover, this sample complexity should be attained with simple and efficient learning algorithms. When T=1T=1, the problem is precisely multiclass learning of F\mathcal{F} with label set Σ\Sigma. Learning with chain-of-thought supervision is therefore at least as hard as multiclass learning; a central question is whether learning to produce a long chain-of-thought is harder than learning to predict a single token.

Prior Work. For context, we summarize existing sample complexity bounds for autoregressive learning under chain-of-thought supervision. These bounds are summarized in Table 1, and complexity measures are reviewed in § 4; a broader discussion of related work is deferred to § 8. The story begins with Joshi et al. [40], who showed that a single call to a CONSCoT oracle, which returns a generator that is CoT-consistent with the training data, achieves a sample complexity of order dlog⁡Td\log T, where dd is the VC dimension of F\mathcal{F}. Then, Hanneke, Mehalel, and Moran [34] showed that this log⁡T\log T factor can be removed, with a majority-vote compression scheme [52], but at the price of a factor of the dual VC dimension d⋆d^\star, which may be exponentially larger than dd [A83; KS23]. Afterwards, Doron-Arad, Mehalel, and Mossel [DMM26b] obtained another TT-independent bound through online learning, but in terms of the Littlestone dimension dLd_L, which can be infinite even for simple classes (e.g., thresholds on the line).

ReferenceSample ComplexityAlphabetLearner
[40]O((dlog⁡(2T)log⁡(2/ε)+log⁡(1/δ))/ε)O((d\log(2T)\log(2/\varepsilon)+\log(1/\delta))/\varepsilon)binaryCoT-consistent learner
[34]O((dd⋆log⁡(2dd⋆)log⁡(2/ε)+log⁡(1/δ))/ε)O((d d^\star\log(2d d^\star)\log(2/\varepsilon)+\log(1/\delta))/\varepsilon)binarysample-compression majority-vote
[DMM26b]O((dL+log⁡(1/δ))/ε)O((d_L+\log(1/\delta))/\varepsilon)arbitraryonline-to-batch conversion
[46]O((dDS+log⁡(1/δ))/ε)O((d_{\mathrm{DS}}+\log(1/\delta))/\varepsilon)arbitraryone-inclusion hypergraphs
This work (Theorem 1)O((dG+log⁡(1/δ))/ε)O((d_G+\log(1/\delta))/\varepsilon)arbitraryBagging CoT-consistent predictors
Lower bound [46]Ω((dDS+log⁡(1/δ))/ε)\Omega((d_{\mathrm{DS}}+\log(1/\delta))/\varepsilon)arbitraryany learner, already for T=1T=1

Table 1. Sample complexity of realizable learning with chain-of-thought supervision. Here dd, dGd_G, dLd_L, and dDSd_{\mathrm{DS}} are the VC, Graph, Littlestone, and DS dimensions of F\mathcal{F}, and d⋆d^\star is its dual VC dimension. We refer the reader to § 4 for definitions and background on these complexity measures.

Most recently, Li [46] settled the optimal sample complexity of the problem: every autoregressive class F\mathcal{F} is learnable with sample complexity O((dDS+log⁡(1/δ))/ε)O((d_{\mathrm{DS}}+\log(1/\delta))/\varepsilon), independently of TT, where dDSd_{\mathrm{DS}} is the Daniely–Shalev-Shwartz (DS) dimension of F\mathcal{F} [23], which characterizes multiclass learnability [14] (see § 4 for definitions). This result builds on recent progress in multiclass learning, which established that the DS dimension also governs the optimal sample complexity of multiclass learning [HMMS26; P26]. As the case T=1T=1 is itself multiclass learning, this bound cannot be improved in general. Thus, information-theoretically, generating a long chain-of-thought is no harder than generating a single token. The learner achieving this sample complexity, however, is far from practical. It is based on the one-inclusion graph [33]. Given a test prompt xx, the learner builds the one-inclusion graph, whose vertices are all the chains-of-thought that functions in F\mathcal{F} can generate on the training prompts and on xx, orients its edges, and reads off its prediction from the orientation. This graph is typically enormous, and it must be rebuilt and reoriented for every new test prompt, making the learner computationally intractable, and in sharp contrast to how language models are trained and deployed in practice. This raises a natural question that we study in this paper:

Is there a simple and efficient algorithm for autoregressive learning that attains the optimal sample complexity?

Our Contributions

We answer this question affirmatively for binary alphabets, and up to a factor of log⁡∣Σ∣\log|\Sigma| for finite alphabets, with one of the oldest and simplest ideas in machine learning: bagging. Introduced by Breiman [8], bagging trains a base learner on bootstrap samples, drawn with replacement from the training set, and combines the resulting predictors by a majority vote. Our algorithm, bagging CoT-consistent predictors (Algorithm 1), carries this idea over to autoregressive learning: it trains N=O(log⁡(T/δ))N = O(\log(T/\delta)) CoT-consistent predictors on bootstrap samples, and generates each token of the chain-of-thought by a majority vote of their next-token predictions. We show that it learns every autoregressive class F\mathcal{F} with sample complexity O((dG+log⁡(1/δ))/ε)O((d_{\mathrm{G}}+\log(1/\delta))/\varepsilon), independent of the CoT length TT, where dGd_{\mathrm{G}} is the Graph dimension of F\mathcal{F} (Theorem 1). For binary alphabets, the Graph and DS dimensions both coincide with the VC dimension, so our bound matches the optimal sample complexity of [46]. For finite alphabets, our bound is optimal up to a factor of log⁡∣Σ∣\log|\Sigma|. The output of Algorithm 1 is an ensemble of NN generators, which multiplies the inference cost per token by NN. We further show that the ensemble can be distilled into a single generator in F\mathcal{F} using O(nlog⁡(nT))O(n\log(nT)) unlabeled prompts while retaining the labeled sample complexity (see Proposition 1).

Algorithm 1: Bagging CoT-Consistent Predictors

Input: Training set S=((xj,yj))j=1nS=((x_j,y_j))_{j=1}^{n}, confidence δ\delta, and a CONS⁡CoT\operatorname{CONS}_{\mathrm{CoT}} oracle (4).

  1. Set N=max⁡{4,⌈log⁡2(2T/δ)⌉}N=\max\{4,\lceil\log_2(2T/\delta)\rceil\}, and Jn={⌈n/4⌉,…,n−1}J_n=\{\lceil n/4\rceil,\ldots,n-1\}.

  2. For each i=1,…,Ni=1,\ldots,N:

    1. Sample kk uniformly from JnJ_n.

    2. Sample a bootstrap Si′S'_i of kk samples uniformly with replacement from S≤k=((xj,yj))j=1kS_{\leq k}=((x_j,y_j))_{j=1}^{k}.

    3. Run the CONS⁡CoT\operatorname{CONS}_{\mathrm{CoT}} oracle on Si′S'_i, and let f^Si′=CONS⁡CoT(Si′)\widehat{f}_{S'_i}=\operatorname{CONS}_{\mathrm{CoT}}(S'_i) be the returned predictor.

Output: The majority-vote predictor over f^S1′,…,f^SN′\widehat{f}_{S'_1},\ldots,\widehat{f}_{S'_N}, defined as follows (with fixed tie-breaking):

y^1=MAJ⁡(f^S1′,…,f^SN′)(x)=arg max⁡y∈Σ∑i=1N1{f^Si′(x)=y},\widehat{y}_1=\operatorname{MAJ}(\widehat{f}_{S'_1},\ldots,\widehat{f}_{S'_N})(x)=\underset{y\in\Sigma}{\operatorname{arg\,max}}\sum_{i=1}^{N}\mathbf{1}\{\widehat{f}_{S'_i}(x)=y\},
y^t=MAJ⁡(f^S1′,…,f^SN′)(x∘y^1:t−1),2≤t≤T.\widehat{y}_t=\operatorname{MAJ}(\widehat{f}_{S'_1},\ldots,\widehat{f}_{S'_N})(x\circ\widehat{y}_{1:t-1}),\qquad2\leq t\leq T.

Theorem 1. For any autoregressive class F\mathcal{F} with Graph dimension dGd_{\mathrm{G}}, any CONS⁡CoT\operatorname{CONS}_{\mathrm{CoT}} oracle, and any distribution PP over Σ⋆×ΣT\Sigma^\star\times\Sigma^T such that P[f⋆(1:T)(x)=y]=1P\left[f_\star^{(1:T)}(x)=y\right]=1 for some f⋆∈Ff_\star\in\mathcal{F}, for every n≥4n\geq4 and every δ∈(0,1)\delta\in(0,1), letting N=max⁡{4,⌈log⁡2(2T/δ)⌉}N=\max\{4,\lceil\log_2(2T/\delta)\rceil\}, with probability at least 1−δ1-\delta over the random draw of a training dataset S=((xj,yj))j=1n∼PnS=((x_j,y_j))_{j=1}^{n}\sim P^n and over the NN bootstrap samples S1′,…,SN′S'_1,\ldots,S'_N drawn as in Algorithm 1,

Pr⁡(x,y)∼P[∃t∈[T]:MAJ⁡(f^S1′,…,f^SN′)(t)(x)≠yt]=O(dGn+1nlog⁡(1δ)).\Pr_{(x,y)\sim P}\left[\exists t\in[T]:\operatorname{MAJ}(\widehat{f}_{S'_1},\ldots,\widehat{f}_{S'_N})^{(t)}(x)\ne y_t\right]=O\left(\frac{d_{\mathrm{G}}}{n}+\frac{1}{n}\log\left(\frac{1}{\delta}\right)\right).

Remark 1 (Optimality). The sample complexity in Theorem 1 compares with known lower bounds as follows.

  • Binary alphabets. The bound is optimal since dGd_{\mathrm{G}} is exactly the VC dimension of F\mathcal{F}, and this matches the classical lower bound Ω((dG+log⁡(1/δ))/ε)\Omega((d_{\mathrm{G}}+\log(1/\delta))/\varepsilon) for PAC learning [27], which holds already for T=1T=1.

  • Finite alphabets. The bound is optimal up to a factor of log⁡∣Σ∣\log|\Sigma|: the Graph dimension satisfies dG≤4.67dNlog⁡2∣Σ∣d_{\mathrm{G}}\leq4.67d_{\mathrm{N}}\log_2|\Sigma|, where dNd_{\mathrm{N}} is the Natarajan dimension of F\mathcal{F} [53, 15 DSB S15], while multiclass learning, and hence our problem, requires Ω((dN+log⁡(1/δ))/ε)\Omega((d_{\mathrm{N}}+\log(1/\delta))/\varepsilon) samples [53, 24].

Remark 2. The same guarantee holds with N=O(d⋆+log⁡(1/δ))N=O(d^\star+\log(1/\delta)) bootstrap samples (and oracle calls), where d⋆d^\star is the dual VC dimension of F\mathcal{F} (see Lemma 6). Hence N=O(log⁡(1/δ)+min⁡{d⋆,log⁡T})N=O(\log(1/\delta)+\min\{d^\star,\log T\}) suffices.

Algorithm 1 is simple and efficient. It accesses the class only through a CONS⁡CoT\operatorname{CONS}_{\mathrm{CoT}} oracle, which it calls N=O(log⁡(T/δ))N=O(\log(T/\delta)) times, and its output is itself a next-token generator: each token is obtained by evaluating the NN base predictors on the current prefix and returning the most frequent prediction, so a chain-of-thought of length TT costs only NTNT evaluations of predictors in F\mathcal{F}. We also remark that, like bagging in general [8], both training and inference in Algorithm 1 can be parallelized across the NN base predictors. Moreover, the ensemble can be distilled into a single generator in F\mathcal{F} after training, removing the factor of NN in the cost per token (see § 7). By contrast, the optimal learner of Li [46] predicts by building and orienting a one-inclusion graph over all chains-of-thought that F\mathcal{F} can generate on the training prompts and the test prompt, a construction that must be repeated for every new test prompt and is computationally intractable.

For very large (and infinite) alphabets, a natural question is whether a simple algorithm such as Algorithm 1, which aggregates predictors in F\mathcal{F}, can attain the optimal sample complexity O((dDS+log⁡(1/δ))/ε)O((d_{\mathrm{DS}}+\log(1/\delta))/\varepsilon). The answer is unfortunately no. The obstruction is inherited from multiclass learning, and therefore arises already for T=1T=1, where our problem reduces to multiclass learning of F\mathcal{F}. In our context, recent impossibility results for aggregations of proper learners [AHV25] have two consequences. First, there are classes F\mathcal{F} on which majorities of consistent learners require Ω((dG+log⁡(1/δ))/ε)\Omega((d_{\mathrm{G}}+\log(1/\delta))/\varepsilon) samples, so the dependence on the Graph dimension in Theorem 1 is tight for Algorithm 1. Second, there is a class F\mathcal{F} of finite DS dimension that cannot be learned to constant error by any algorithm that aggregates finitely many predictors from the class, so for infinite alphabets, no such algorithm can attain the optimal sample complexity. This perhaps suggests a fundamental tension between the simplicity of a learning algorithm and the optimality of its sample complexity, in line with recent work on the limits of simple learning principles for multiclass learning [4].

Overview of Proof Ideas

We highlight the main ideas behind the proof of Theorem 1, after briefly describing the prior approaches. Joshi et al. [40] analyze a CoT-consistent predictor through the VC dimension of the class of chain-of-thought errors, which incurs a factor of log⁡T\log T. Hanneke, Mehalel, and Moran [34] proceed with an analysis based on sample compression schemes, which removes the dependence on TT but incurs a factor of the dual VC dimension d∗d^*. Li [46] predicts by orienting one-inclusion graphs of the class of chains-of-thought, which attains the optimal sample complexity but is computationally intractable. We take a different route, inspired by the recent analysis of bagging for adversarially robust learning in [49]: rather than analyzing a single predictor, we analyze the distribution over CoT-consistent predictors trained on random samples, and aggregate them by bagging. Throughout, let F\mathcal{F} be a class with Graph dimension dGd_{\mathrm{G}}, fix an arbitrary CONSCoT oracle, and let PP be a realizable distribution. The analysis has three main parts.

Distribution of CoT-Consistent Predictors. The key idea is to analyze the distribution of the CoT-consistent predictors f^S\hat{f}_S obtained from random training samples S∼PnS \sim P^n. Lemma 1 shows that, for a random test example, the fraction of these predictors that err at the worst step along the target chain-of-thought is small:

E(x,y)∼P[max⁡t∈[T]Pr⁡S∼Pn[f^S(x∘y1:t−1)≠yt]]2=O(dGn).(2)\mathbb{E}_{(x,y)\sim P}\left[\max_{t\in[T]}\Pr_{S\sim P^n}\left[\hat{f}_S(x\circ y_{1:t-1})\ne y_t\right]\right]^2=O\left(\frac{d_{\mathrm{G}}}{n}\right). \tag*{(2)}

In words: on most test examples, at every step of the target chain-of-thought, the correct token is predicted by most CoT-consistent predictors, even though the predictors that err may change from one step to the next. This is a weaker requirement than asking a single predictor to be correct at all steps at once, and it is the reason the bound does not depend on TT. For a single CoT-consistent predictor, Li [46 Theorem 6.2] shows that a dependence on TT is unavoidable: for a suitable binary class and CONSCoT oracle,

E(x,y)∼PES∼Pn[max⁡t∈[T]{f^S(x∘y1:t−1)≠yt}]=Ω(dGlog⁡Tn).\mathbb{E}_{(x,y)\sim P}\mathbb{E}_{S\sim P^n}\left[\max_{t\in[T]}\left\{\hat{f}_S(x\circ y_{1:t-1})\ne y_t\right\}\right]=\Omega\left(\frac{d_{\mathrm{G}}\log T}{n}\right).

The proof of (2) rests on a simple observation. For each test example, we fix in advance the step at which a random predictor f^S\hat{f}_S is most likely to err; this choice depends on PP, nn, and the CONSCoT oracle, but not on the sample. Every CoT-consistent predictor is correct at every step of every training chain-of-thought, and in particular at the chosen step of each training example. Bounding (2) thus amounts to bounding the expected number of mistakes of a consistent learner on a fixed next-token prediction problem, over a class of error regions of VC dimension at most dGd_G, a standard analysis. To avoid logarithmic factors, we bound the second moment in (2) directly, relying on recent second-moment bounds for consistent learners [5, 60]; bounding only the first moment, as in [17], would incur an extra multiplicative factor of log⁡(n/dG)\log(n/d_G).

Bagging Leave-One-Out Analysis. Bound (2) concerns predictors trained on fresh samples from PP, whereas Algorithm 1 trains predictors on bootstraps of a single sample SS. To connect the two, we consider an idealized bagging predictor, which aggregates the CoT-consistent predictors trained on all ordered bootstraps of SS. For x′∈Σ∗x' \in\Sigma^* and y′∈Σy' \in\Sigma, its bagging score is the fraction of these predictors that predict y′y' on x′x':

B^S(y′∣x′):=Pr⁡S′∼Unif⁡(S)∣S∣[f^S′(x′)=y′].\widehat{B}_S(y' \mid x') := \Pr_{S' \sim\operatorname{Unif}(S)^{|S|}} \left[\widehat{f}_{S'}(x') = y'\right].

We bound its leave-one-out error. The key observation is that a bootstrap of SS of size n−1n-1 omits the ii-th example with probability (1−1/n)n−1≥1/e(1-1/n)^{n-1} \ge1/e, and is then a bootstrap of the sample S−iS_{-i} without it. This observation underlies the out-of-bag estimate of the error of bagging [9, 67, 62] and, more broadly, leave-one-out bootstrap estimates [25, 28]; here, we use it to bound the leave-one-out error rather than to estimate it. Since bootstraps of SS are samples from its empirical distribution D:=Unif⁡(S)D := \operatorname{Unif}(S), the observation reduces the leave-one-out error to the quantity bounded in (2), for DD in place of PP (Lemma 3):

1n∑i=1nmax⁡1≤t≤T(1−B^S−i(yi,t∣xi∘yi,1:t−1))2≤e2 E(x,y)∼D[max⁡1≤t≤TPr⁡S′∼Dn−1[f^S′(x∘y1:t−1)≠yt]2].(3)\frac{1}{n}\sum_{i=1}^{n}\max_{1\le t\le T}\left(1-\widehat{B}_{S_{-i}}(y_{i,t}\mid x_i\circ y_{i,1:t-1})\right)^2 \le e^2\,\mathbb{E}_{(x,y)\sim D}\left[\max_{1\le t\le T}\Pr_{S'\sim D^{n-1}}\left[\widehat{f}_{S'}(x\circ y_{1:t-1})\ne y_t\right]^2\right]. \tag*{(3)}

By (2), the right-hand side is O(dG/n)O(d_G/n). Finally, by exchangeability (Remark 3), (3) also bounds by O(dG/n)O(d_G/n) the expected squared worst-step error of the idealized bagging predictor on a fresh example. Since its majority vote errs on a chain-of-thought only if the correct token receives at most half of the votes at some step, its expected CoT risk is O(dG/n)O(d_G/n) as well, independently of TT.

High-probability Bound and Sparsification. To obtain a high-probability bound with the optimal dependence on log⁡(1/δ)\log(1/\delta), we employ the suffix-averaging technique of Aden-Ali et al. [3], which converts leave-one-out bounds for permutation-invariant predictors into high-probability bounds. This leads to the suffix-bagging predictor, which averages the bagging predictors of the prefixes S≤kS_{\le k} of the sample, and whose squared worst-step error is O((dG+log⁡(1/δ))/n)O((d_G+\log(1/\delta))/n) with high probability (Lemma 4).

The main challenge is that the suffix-bagging predictor is intractable: it aggregates the predictors trained on all ordered bootstraps of every prefix, exponentially many in nn, each requiring a call to the Cons⁡CoT\operatorname{Cons}_{\mathrm{CoT}} oracle. A key idea in Algorithm 1 is to randomly sample NN of these predictors and take their majority vote, which can be thought of as a Monte Carlo approximation of the suffix-bagging predictor. In the spirit of [45 Lemma 3], we show that N=O(log⁡(T/δ))N=O(\log(T/\delta)) samples suffice, independently of nn (Lemma 5). The reason is that only the votes on the TT target prefixes of each example matter: at each of them, the sampled majority errs with probability exponentially small in NN and proportional to the squared error controlled by Lemma 4, and a union bound over the TT steps concludes. This is the only place where the CoT length appears, and it is the reason we measure errors by the squared worst-step error throughout: a thresholded loss would only yield an additive approximation error, and thus a number of oracle calls growing logarithmically with nn. Alternatively, the classical sparsification argument of Moran and Yehudayoff [52] gives N=O(d∗+log⁡(1/δ))N=O(d^*+\log(1/\delta)), independently of TT (Lemma 6), but the dual VC dimension d∗d^* can be exponentially larger than dGd_G [A83; KS23].

Technical Definitions

Autoregressive Learning. We recall the setting of § 1 and fix notation. Let Σ\Sigma be a set of tokens, finite or infinite, let Σ∗\Sigma^* be the set of finite strings over Σ\Sigma, and write [r]={1,…,r}[r]=\{1,\ldots,r\} for each positive integer rr. For a generator f:Σ∗→Σf:\Sigma^*\to\Sigma and a prompt x∈Σ∗x\in\Sigma^*, the generated tokens are defined recursively by

f(1)(x)=f(x)andf(t)(x)=f(x∘f(1)(x)∘⋯∘f(t−1)(x))for t≥2,f^{(1)}(x)=f(x) \qquad\text{and} \qquad f^{(t)}(x)=f\left(x\circ f^{(1)}(x)\circ\cdots\circ f^{(t-1)}(x)\right)\quad\text{for }t\ge2,

where ∘\circ is concatenation, and f(1:T)(x)=f(1)(x)∘⋯∘f(T)(x)∈ΣTf^{(1:T)}(x)=f^{(1)}(x)\circ\cdots\circ f^{(T)}(x)\in\Sigma^T. The learner receives S=((xj,yj))j=1n∼PnS=((x_j,y_j))_{j=1}^n\sim P^n from a distribution PP over Σ⋆×ΣT\Sigma^\star\times\Sigma^T realizable by F\mathcal{F}, and is evaluated by its CoT risk (1).

CoT-Consistent Oracle. Our algorithms access F\mathcal{F} only through a CONSCoT oracle: a deterministic rule that, given a sample SS realizable by F\mathcal{F}, returns f^S:=CONSCoT(S)∈F\hat{f}_S:=\mathrm{CONS}_{\mathrm{CoT}}(S)\in\mathcal{F} reproducing every chain-of-thought in SS:

f^S:=CONSCoT(S)∈{f∈F:f(t)(xj)=yj,t for all j∈[n] and t∈[T]}.(4)\hat{f}_S:=\mathrm{CONS}_{\mathrm{CoT}}(S)\in\left\{f\in\mathcal{F}:f^{(t)}(x_j)=y_{j,t}\text{ for all }j\in[n]\text{ and }t\in[T]\right\}. \tag*{(4)}

We call such a generator CoT-consistent with SS. Equivalently, it correctly predicts every next token along the chains-of-thought in SS: f^S(xj∘yj,1:t−1)=yj,t\hat{f}_S(x_j\circ y_{j,1:t-1})=y_{j,t} for all j∈[n]j\in[n] and t∈[T]t\in[T].

Complexity Measures. We briefly review four standard combinatorial dimensions of F\mathcal{F}, viewed as a class of next-token predictors from Σ⋆\Sigma^\star to Σ\Sigma: the VC, Graph, Natarajan, and DS dimensions. For prompts x1,…,xk∈Σ⋆x_1,\ldots,x_k\in\Sigma^\star, write F∣(x1,…,xk)={(f(x1),…,f(xk)):f∈F}⊆Σk\mathcal{F}|_{(x_1,\ldots,x_k)}=\{(f(x_1),\ldots,f(x_k)):f\in\mathcal{F}\}\subseteq\Sigma^k for the set of next-token patterns that F\mathcal{F} realizes on them. Each dimension below is the largest kk for which some prompts x1,…,xkx_1,\ldots,x_k are shattered in the corresponding sense, or ∞\infty if no largest kk exists.

  • VC dimension dVC(F)d_{\mathrm{VC}}(\mathcal{F}) [66], for ∣Σ∣=2|\Sigma|=2: x1,…,xkx_1,\ldots,x_k are shattered if F∣(x1,…,xk)=Σk\mathcal{F}|_{(x_1,\ldots,x_k)}=\Sigma^k.

  • Graph dimension dG(F)d_{\mathrm{G}}(\mathcal{F}) [53]: x1,…,xkx_1,\ldots,x_k are G-shattered if there are tokens s1,…,sk∈Σs_1,\ldots,s_k\in\Sigma such that, for every B⊆[k]B\subseteq[k], some f∈Ff\in\mathcal{F} satisfies f(xi)=sif(x_i)=s_i exactly for i∈Bi\in B. Equivalently, dG(F)d_{\mathrm{G}}(\mathcal{F}) is the VC dimension of the 0-1 loss class {(x,y)↦1{f(x)≠y}:f∈F}\{(x,y)\mapsto\mathbb{1}\{f(x)\ne y\}:f\in\mathcal{F}\} over Σ⋆×Σ\Sigma^\star\times\Sigma.

  • Natarajan dimension dN(F)d_{\mathrm{N}}(\mathcal{F}) [53]: x1,…,xkx_1,\ldots,x_k are N-shattered if there are tokens si≠si′s_i\ne s_i', for i∈[k]i\in[k], such that, for every B⊆[k]B\subseteq[k], some f∈Ff\in\mathcal{F} satisfies f(xi)=sif(x_i)=s_i for i∈Bi\in B and f(xi)=si′f(x_i)=s_i' for i∉Bi\notin B.

  • DS dimension dDS(F)d_{\mathrm{DS}}(\mathcal{F}) [23, 14]: x1,…,xkx_1,\ldots,x_k are DS-shattered if F∣(x1,…,xk)\mathcal{F}|_{(x_1,\ldots,x_k)} contains a kk-dimensional pseudo-cube, that is, a nonempty finite set H⊆ΣkH\subseteq\Sigma^k in which every pattern h∈Hh\in H has, for each i∈[k]i\in[k], a neighbor h′∈Hh'\in H with hi′≠hih_i'\ne h_i and hj′=hjh_j'=h_j for all j≠ij\ne i.

When the class is clear from context, we simply write dVCd_{\mathrm{VC}}, dGd_{\mathrm{G}}, dNd_{\mathrm{N}}, and dDSd_{\mathrm{DS}}. For binary alphabets, all four notions coincide: dG=dN=dDS=dVCd_{\mathrm{G}}=d_{\mathrm{N}}=d_{\mathrm{DS}}=d_{\mathrm{VC}}. For finite alphabets, they are related by

dN≤dDS≤dG≤4.67 dNlog⁡2∣Σ∣.d_{\mathrm{N}}\le d_{\mathrm{DS}}\le d_{\mathrm{G}}\le4.67\,d_{\mathrm{N}}\log_2|\Sigma|.

[15, 24, 14]

In particular, the three dimensions are finite simultaneously, and both the Natarajan and the DS dimensions characterize learnability for finite alphabets [24, 14]. For infinite alphabets, the inequalities dN≤dDSd_{\mathrm{N}}\le d_{\mathrm{DS}} and dN≤dGd_{\mathrm{N}}\le d_{\mathrm{G}} persist, but the dimensions may differ drastically: the Graph dimension may be infinite while the DS dimension is finite [23 AHV25], and the DS dimension may be infinite while the Natarajan dimension equals one; only the DS dimension characterizes learnability in general [14].

Proof of Theorem 1

In this section, we provide a complete proof of Theorem 1, which we restate below.

Theorem 1. For any autoregressive class F\mathcal{F} with Graph dimension dGd_{\mathrm{G}}, any CONSCoT oracle, and any distribution PP over Σ⋆×ΣT\Sigma^\star\times\Sigma^T such that P[f⋆(1:T)(x)=y]=1P\left[f_\star^{(1:T)}(x)=y\right]=1 for some f⋆∈Ff_\star\in\mathcal{F}, for every n≥4n\ge4 and every δ∈(0,1)\delta\in(0,1), letting N=max⁡{4,⌈log⁡2(2T/δ)⌉}N=\max\{4,\lceil\log_2(2T/\delta)\rceil\}, with probability at least 1−δ1-\delta over the random draw of a training dataset S=((xj,yj))j=1n∼PnS=((x_j,y_j))_{j=1}^n\sim P^n and over the NN bootstrap samples S1′,…,SN′S'_1,\ldots,S'_N drawn as in Algorithm 1,

Pr⁡(x,y)∼P[∃t∈[T]:MAJ⁡(f^S1′,…,f^SN′)(t)(x)≠yt]=O(dGn+1nlog⁡(1δ)).\Pr_{(x,y)\sim P}\left[\exists t\in[T]:\operatorname{MAJ}(\hat{f}_{S'_1},\ldots,\hat{f}_{S'_N})^{(t)}(x)\ne y_t\right]=O\left(\frac{d_{\mathrm{G}}}{n}+\frac{1}{n}\log\left(\frac{1}{\delta}\right)\right).

Leave-One-Out Analysis of Bagging

We first show that, on most test examples, every step along the target chain-of-thought is predicted correctly by most CoT-consistent predictors: for each t∈[T]t \in[T], the probability over the training sample S∼PnS \sim P^n that f^S\hat{f}_S errs on the prefix x∘y1:t−1x \circ y_{1:t-1} is small. This guarantee is per step, and the predictors that err may differ across steps; it is the majority vote that later combines these per-step guarantees into a correct chain-of-thought.

Lemma 1. For any autoregressive class F\mathcal{F} with Graph dimension dGd_{\mathrm{G}}, any CONSCoT\mathrm{CONS}_{\mathrm{CoT}} oracle, and any distribution PP over Σ⋆×ΣT\Sigma^\star\times\Sigma^T such that Pr⁡(x,y)∼P[f⋆(1:T)(x)=y]=1\Pr_{(x,y)\sim P}[f_\star^{(1:T)}(x)=y]=1 for some f⋆∈Ff_\star\in\mathcal{F},

E(x,y)∼P[a(x,y)2]≤C⋅dGn,a(x,y):=max⁡1≤t≤TPr⁡S∼Pn[f^S(x∘y1:t−1)≠yt].\mathbb{E}_{(x,y)\sim P}[a(x,y)^2] \le C \cdot\frac{d_{\mathrm{G}}}{n}, \qquad a(x,y):=\max_{1\le t\le T}\Pr_{S\sim P^n}\left[\hat{f}_S(x\circ y_{1:t-1})\ne y_t\right].

where C≥1C\ge1 is the universal constant of Lemma 2.

The proof relies on the following second-moment bound for consistent learning rules over VC classes. Classical first-moment bounds [17] would also suffice, at the cost of a multiplicative log⁡(n/dG)\log(n/d_{\mathrm{G}}) factor.

Lemma 2 [5, 60]. There is a universal constant C≥1C\ge1 such that the following holds. Let PP be a distribution on X×Y\mathcal{X}\times\mathcal{Y}, and let E\mathcal{E} be a class of subsets of X×Y\mathcal{X}\times\mathcal{Y} with VC dimension dd. Let EE be a deterministic selector such that E(S)∈EE(S)\in\mathcal{E} for every S∈(X×Y)nS\in(\mathcal{X}\times\mathcal{Y})^n and Pr⁡S∼Pn[E(S)∩S=∅]=1\Pr_{S\sim P^n}[E(S)\cap S=\varnothing]=1. Then,

E(x,y)∼P[Pr⁡S∼Pn[(x,y)∈E(S)]2]≤C⋅dn.\mathbb{E}_{(x,y)\sim P}\left[\Pr_{S\sim P^n}[(x,y)\in E(S)]^2\right]\le C\cdot\frac{d}{n}.

Proof of Lemma 1. The quantity a(x,y)a(x,y) is the error probability of f^S\hat{f}_S at the worst step along the target chain-of-thought. The idea is to fix this worst step for each example in advance, which reduces a(x,y)a(x,y) to the error probability on a single next-token example, and then to apply Lemma 2 to the resulting class of error regions.

We first fix, for each example, the prefix on which this predictor is most likely to err. For (x,y)∈Σ⋆×ΣT(x,y)\in\Sigma^\star\times\Sigma^T, let t(x,y)∈[T]t(x,y)\in[T] be the smallest index attaining the maximum in the definition of a(x,y)a(x,y), and define the map ϕ:Σ⋆×ΣT→Σ⋆×Σ\phi:\Sigma^\star\times\Sigma^T\to\Sigma^\star\times\Sigma by

ϕ(x,y):=(x∘y1:t(x,y)−1,yt(x,y)).\phi(x,y):=\left(x\circ y_{1:t(x,y)-1},y_{t(x,y)}\right).

In words, ϕ\phi maps a prompt and its target chain-of-thought to a single next-token example: the prefix of the chain-of-thought up to step t(x,y)−1t(x,y)-1, labeled by the correct token at step t(x,y)t(x,y). The map ϕ\phi depends on PP, nn, and the CONSCoT\mathrm{CONS}_{\mathrm{CoT}} oracle, but not on the sample SS. Writing ϕ=(ϕ1,ϕ2)\phi=(\phi_1,\phi_2), we have by construction

a(x,y)=Pr⁡S∼Pn[f^S(ϕ1(x,y))≠ϕ2(x,y)].(5)a(x,y)=\Pr_{S\sim P^n}\left[\hat{f}_S(\phi_1(x,y))\ne\phi_2(x,y)\right]. \tag*{(5)}

We now verify the conditions of Lemma 2: we exhibit a class of subsets of Σ⋆×ΣT\Sigma^\star\times\Sigma^T of VC dimension at most dGd_{\mathrm{G}}, together with a deterministic selector into this class whose selected set is disjoint from the sample. For each f∈Ff\in\mathcal{F}, define the error region relative to ϕ\phi, and the class of all such regions, by

Ef:={(x,y)∈Σ⋆×ΣT:f(ϕ1(x,y))≠ϕ2(x,y)},E:={Ef:f∈F}.E_f:=\{(x,y)\in\Sigma^\star\times\Sigma^T:f(\phi_1(x,y))\ne\phi_2(x,y)\},\qquad\mathcal{E}:=\{E_f:f\in\mathcal{F}\}.

We have (x,y)∈Ef(x,y)\in E_f if and only if ϕ(x,y)∈Gf\phi(x,y)\in G_f, where Gf:={(x′,y′)∈Σ⋆×Σ:f(x′)≠y′}G_f:=\{(x',y')\in\Sigma^\star\times\Sigma:f(x')\ne y'\} is the token-level error region of ff. Hence, if E\mathcal{E} shatters kk points, then {Gf:f∈F}\{G_f:f\in\mathcal{F}\} shatters their kk images under ϕ\phi, which are necessarily distinct, and therefore VCdim⁡(E)≤VCdim⁡({Gf:f∈F})=dG\operatorname{VCdim}(\mathcal{E})\le\operatorname{VCdim}(\{G_f:f\in\mathcal{F}\})=d_{\mathrm{G}}.

Next, consider the selector E(S):=Ef^SE(S):=E_{\hat{f}_S}, which is deterministic and takes values in E\mathcal{E}. By realizability, there exists f⋆∈Ff_\star\in\mathcal{F} satisfying Pr⁡(x,y)∼P[f⋆(1:T)(x)=y]=1\Pr_{(x,y)\sim P}[f_\star^{(1:T)}(x)=y]=1. By (4) it follows that f^S\hat{f}_S is CoT-consistent with the sample SS; that is, f^S(xj∘yj,1:t−1)=yj,t\hat{f}_S(x_j\circ y_{j,1:t-1})=y_{j,t} for all (xj,yj)∈S(x_j,y_j)\in S and t∈[T]t\in[T]. In particular, f^S(ϕ1(xj,yj))=ϕ2(xj,yj)\hat{f}_S(\phi_1(x_j,y_j))=\phi_2(x_j,y_j) for every jj, so that E(S)∩S=∅E(S)\cap S=\varnothing with probability $1.

We are now ready to invoke Lemma 2. By (5), a(x,y)=Pr⁡S∼Pn[(x,y)∈E(S)]a(x,y)=\Pr_{S\sim P^n}[(x,y)\in E(S)], so Lemma 2, applied to E\mathcal{E} and the selector EE, yields

E(x,y)∼P[a(x,y)2]=E(x,y)∼P[Pr⁡S∼Pn[(x,y)∈E(S)]2]≤C⋅dGn.\mathbb{E}_{(x,y)\sim P}[a(x,y)^2]=\mathbb{E}_{(x,y)\sim P}\left[\Pr_{S\sim P^n}[(x,y)\in E(S)]^2\right]\le C\cdot\frac{d_G}{n}.

Bagging

Bagging. We introduce notation for bagging. For a sequence S=((x1,y1),…,(xn,yn))S=((x_1,y_1),\ldots,(x_n,y_n)) and a bootstrap size m≥1m\ge1, let S′∼Unif⁡(S)mS'\sim\operatorname{Unif}(S)^m be a bootstrap of mm examples returned uniformly at random (with replacement) from SS, and let f^S′=CONS⁡CoT(S′)\widehat{f}_{S'}=\operatorname{CONS}_{\mathrm{CoT}}(S') be the predictor returned by the CONSCoT\mathrm{CONS}_{\mathrm{CoT}} oracle (4) on S′S'. Equivalently, we can express this as drawing a sequence of indices I=(i1,…,im)∈[n]mI=(i_1,\ldots,i_m)\in[n]^m uniformly at random, and denote the bootstrap sample by S(I)=((xi1,yi1),…,(xim,yim))S(I)=((x_{i_1},y_{i_1}),\ldots,(x_{i_m},y_{i_m})).

Define the bagging predictor B^Sm\widehat{B}^{m}_{S}, which maps each input x∈Σ∗x\in\Sigma^* to a distribution B^Sm(⋅∣x)\widehat{B}^{m}_{S}(\cdot\mid x) over Σ\Sigma, whose bagging score B^Sm(y∣x)\widehat{B}^{m}_{S}(y\mid x) is the fraction of the nmn^m ordered bootstraps of SS of size mm on which the returned predictor outputs yy on input xx:

B^Sm(y∣x):=Pr⁡S′∼Unif⁡(S)m[f^S′(x)=y]=1nm∑I∈[n]m1{f^S(I)(x)=y}.(6)\widehat{B}^{m}_{S}(y\mid x):=\Pr_{S'\sim\operatorname{Unif}(S)^m}\left[\widehat{f}_{S'}(x)=y\right]=\frac{1}{n^m}\sum_{I\in[n]^m}\mathbf{1}\{\widehat{f}_{S(I)}(x)=y\}. \tag*{(6)}

Since each predictor outputs exactly one token, ∑y∈ΣB^Sm(y∣x)=1\sum_{y\in\Sigma}\widehat{B}^{m}_{S}(y\mid x)=1, so B^Sm(⋅∣x)\widehat{B}^{m}_{S}(\cdot\mid x) is indeed a conditional distribution over next tokens; on input xx, the majority vote of all bootstrapped predictors outputs the mode arg⁡max⁡y∈ΣB^Sm(y∣x)\arg\max_{y\in\Sigma}\widehat{B}^{m}_{S}(y\mid x) of this distribution. When the bootstrap size equals the size of its source sample, we use the shorthand B^S:=B^S∣S∣\widehat{B}_{S}:=\widehat{B}^{|S|}_{S}.

We now proceed to bound the leave-one-out risk of the bagging predictor (6).

Lemma 3 (Leave-One-Out Error). For any autoregressive class F\mathcal{F} with Graph dimension dGd_G, any CONSCoT\mathrm{CONS}_{\mathrm{CoT}} oracle, and any realizable sequence S=((x1,y1),…,(xn,yn))S=((x_1,y_1),\ldots,(x_n,y_n)) with n≥2n\ge2,

1n∑i=1nmax⁡t∈[T](1−B^S−i(yi,t∣xi∘yi,1:t−1))2≤2e2C⋅dGn.\frac{1}{n}\sum_{i=1}^{n}\max_{t\in[T]}\left(1-\widehat{B}_{S-i}(y_{i,t}\mid x_i\circ y_{i,1:t-1})\right)^2\le2e^2C\cdot\frac{d_G}{n}.

Remark 3 (Expected Risk). Note that by an exchangeability argument, applying Lemma 3 to a sample of size n+1n+1 yields the expected bound

ES∼PnE(x,y)∼P[max⁡t∈[T](1−B^S(yt∣x∘y1:t−1))2]≤2e2C⋅dGn+1.\mathbb{E}_{S\sim P^n}\mathbb{E}_{(x,y)\sim P}\left[\max_{t\in[T]}\left(1-\widehat{B}_{S}(y_t\mid x\circ y_{1:t-1})\right)^2\right]\le2e^2C\cdot\frac{d_G}{n+1}.

Since the majority vote of all bootstrapped predictors errs on the chain-of-thought of (x,y)(x,y) only if the bagging distribution puts at most half of its mass on the correct token at some step, that is, only if B^S(yt∣x∘y1:t−1)≤1/2\widehat{B}_{S}(y_t\mid x\circ y_{1:t-1})\le1/2 for some step t∈[T]t\in[T], its expected CoT risk (1) is at most 8e2CdG/(n+1)8e^2Cd_G/(n+1).

Proof of Lemma 3. The idea is that a bootstrap of SS of size n−1n-1 omits the ii-th example with probability at least 1/e1/e, and is then simply a bootstrap of S−iS_{-i}. The leave-one-out errors are therefore controlled by the errors of bagging on the full sequence SS, to which Lemma 1 applies with PP being the uniform distribution over SS. This is the observation underlying the out-of-bag estimate of the error of bagging [9].

Let m=n−1m=n-1 and P=Unif⁡(S)P=\operatorname{Unif}(S). Fix i∈[n]i\in[n] and t∈[T]t\in[T], and write x′=xi∘yi,1:t−1x'=x_i\circ y_{i,1:t-1} and y′=yi,ty'=y_{i,t} for the corresponding prefix and its next token. Draw II uniformly from [n]m[n]^m. Conditionally on the event i∉Ii\notin I, which has probability (1−1/n)n−1≥1/e(1-1/n)^{n-1}\ge1/e, the index sequence II is uniform over ([n]∖{i})m([n]\setminus\{i\})^m, so S(I)S(I) is a bootstrap of S−iS_{-i} of size m=∣S−i∣m=|S_{-i}|. Hence, by the law of total probability and (6),

1−B^Sm(y′∣x′)=Pr⁡I[f^S(I)(x′)≠y′]≥Pr⁡I[i∉I]⋅Pr⁡I[f^S(I)(x′)≠y′∣i∉I]≥1e(1−B^S−i(y′∣x′)).1-\widehat{B}^{m}_{S}(y'\mid x')=\Pr_I[\widehat{f}_{S(I)}(x')\ne y']\ge\Pr_I[i\notin I]\cdot\Pr_I[\widehat{f}_{S(I)}(x')\ne y'\mid i\notin I]\ge\frac{1}{e}\left(1-\widehat{B}_{S_{-i}}(y'\mid x')\right).

In words, CoT-consistent predictors trained on bootstraps of S−iS_{-i} fail to predict y′y' on x′x' at most ee times as often as those trained on bootstraps of SS.

Now observe that, for every (x,y)∈Σ⋆×ΣT(x,y) \in\Sigma^\star\times\Sigma^T,

max⁡t∈[T](1−B^Sm(yt∣x∘y1:t−1))=max⁡t∈[T]Pr⁡S′∼Pm[f^S′(x∘y1:t−1)≠yt]=a(x,y)\max_{t \in[T]} \left(1-\widehat{B}^{m}_{S}(y_t \mid x \circ y_{1:t-1})\right)=\max_{t \in[T]} \Pr_{S' \sim P^m}\left[\widehat{f}_{S'}(x \circ y_{1:t-1}) \ne y_t\right]=a(x,y)

is precisely the quantity of Lemma 1, for the distribution PP and samples of size mm. Combining this identity with the comparison above, taking the maximum over t∈[T]t \in[T], and squaring, we obtain, for each i∈[n]i \in[n],

max⁡t∈[T](1−B^S−i(yi,t∣xi∘yi,1:t−1))2≤e2a(xi,yi)2.\max_{t \in[T]} \left(1-\widehat{B}_{S_{-i}}(y_{i,t} \mid x_i \circ y_{i,1:t-1})\right)^2 \le e^2 a(x_i,y_i)^2.

Averaging over i∈[n]i \in[n], and noting that the average of a(xi,yi)2a(x_i,y_i)^2 over the nn examples of SS is its expectation under P=Unif⁡(S)P=\operatorname{Unif}(S), we obtain

1n∑i=1nmax⁡t∈[T](1−B^S−i(yi,t∣xi∘yi,1:t−1))2≤e2E(x,y)∼P[a(x,y)2]≤e2C⋅dGm.\frac{1}{n}\sum_{i=1}^{n}\max_{t \in[T]}\left(1-\widehat{B}_{S_{-i}}(y_{i,t} \mid x_i \circ y_{i,1:t-1})\right)^2 \le e^2 \mathop{\mathbb{E}}_{(x,y)\sim P}\left[a(x,y)^2\right] \le e^2 C \cdot\frac{d_G}{m}.

where the last inequality follows from Lemma 1, which applies since P=Unif⁡(S)P=\operatorname{Unif}(S) is realizable because SS is. The lemma follows since m=n−1≥n/2m=n-1\ge n/2 for n≥2n\ge2. □\square

High-Probability Bound and Sparsification

Our goal here is to convert the leave-one-out error bound of Lemma 3 into a high-probability bound, and then approximate the resulting suffix-bagging predictor using finitely many calls to the CONSCoT oracle.

Suffix Averaging and the Suffix Bagging Predictor. Our first step is to apply the suffix averaging technique of Aden-Ali et al. [3] to bagging (6). For a sequence S=((xj,yj))j=1nS=((x_j,y_j))_{j=1}^{n} with n≥4n\ge4, let

Jn={⌈n/4⌉,…,n−1},S≤k=((xj,yj))j=1k for k∈Jn.J_n=\{\lceil n/4\rceil,\ldots,n-1\}, \qquad S_{\le k}=((x_j,y_j))_{j=1}^{k}\text{ for }k\in J_n.

Here S≤kS_{\le k} is a prefix of length kk. We introduce next the suffix-bagging predictor which averages the bagging predictors B^S≤k\widehat{B}_{S_{\le k}} over suffixes k∈Jnk\in J_n and then proceed to bound its risk with high probability. Formally, define, for x∈Σ⋆x\in\Sigma^\star and y∈Σy\in\Sigma,

g^S(y∣x):=1∣Jn∣∑k∈JnB^S≤k(y∣x)=Ek∼Unif⁡(Jn)[Pr⁡S′∼Unif⁡(S≤k)k[f^S′(x)=y]]=1∣Jn∣∑k∈Jn1kk∑I∈[k]k1{f^S(I)(x)=y}.(7)\begin{aligned} \widehat{g}_S(y\mid x):=\frac{1}{|J_n|}\sum_{k\in J_n}\widehat{B}_{S_{\le k}}(y\mid x)=\underset{k\sim\operatorname{Unif}(J_n)}{\mathbb{E}}\left[\underset{S'\sim\operatorname{Unif}(S_{\le k})^k}{\Pr}\left[\widehat{f}_{S'}(x)=y\right]\right] \\ &=\frac{1}{|J_n|}\sum_{k\in J_n}\frac{1}{k^k}\sum_{I\in[k]^k}\mathbf{1}\{\widehat{f}_{S(I)}(x)=y\}. \tag*{(7)} \end{aligned}

As an average of the distributions B^S≤k(⋅∣x)\widehat{B}_{S_{\le k}}(\cdot\mid x), g^S(⋅∣x)\widehat{g}_S(\cdot\mid x) is again a distribution over Σ\Sigma, and g^S(y∣x)\widehat{g}_S(y\mid x) is the probability that the CONSCoT oracle, run on a random bootstrap of a randomly chosen prefix, predicts token yy on input xx. The next lemma shows that, with high probability over the sample, the squared error of the suffix-bagging vote at the worst step along the target chain-of-thought is small on average over test examples.

Lemma 4 (High-probability bound). For any autoregressive class FF with Graph dimension dGd_G, any CONSCoT oracle, any distribution PP over Σ⋆×ΣT\Sigma^\star\times\Sigma^T such that P[f⋆(1:T)(x)=y]=1P\left[f_\star^{(1:T)}(x)=y\right]=1 for some f⋆∈Ff_\star\in F, any n≥4n\ge4, and any δ∈(0,1)\delta\in(0,1), with probability at least 1−δ1-\delta over S∼PnS\sim P^n,

E(x,y)∼P[max⁡t∈[T](1−g^S(yt∣x∘y1:t−1))2]≤19.28e2C(dGn+1nlog⁡2δ).\mathop{\mathbb{E}}_{(x,y)\sim P}\left[\max_{t\in[T]}\left(1-\widehat{g}_S(y_t\mid x\circ y_{1:t-1})\right)^2\right]\le19.28e^2C\left(\frac{d_G}{n}+\frac{1}{n}\log\frac{2}{\delta}\right).

Proof. The proof has two steps. We first convert the leave-one-out guarantee of Lemma 3 into a high-probability bound on the loss of the bagging predictors, averaged over prefixes S≤kS_{\le k} of the sample; we then pass from this average to the suffix-bagging predictor g^S\hat{g}_S by Jensen’s inequality.

The bagging predictor B^S\hat{B}_S is invariant under permutations of SS, because it averages over all ordered bootstraps, even when the CONSCoT oracle depends on the order of its input. Moreover, Lemma 3 bounds the average leave-one-out loss 1n∑i=1nmax⁡t∈[T](1−B^S−i(yi,t∣xi∘yi,1:t−1))2\frac{1}{n}\sum_{i=1}^{n}\max_{t\in[T]}(1-\hat{B}_{S-i}(y_{i,t}\mid x_i\circ y_{i,1:t-1}))^2 by 2e2CdG/n2e^2C d_G/n, uniformly over all realizable sequences, and this loss takes values in [0,1][0,1]. We may therefore invoke the suffix-averaging bound of Aden-Ali et al. [3 Theorem 2.1] for this loss:2 with probability at least 1−δ1-\delta over S∼PnS\sim P^n,

1∣Jn∣∑k∈JnE(x,y)∼P[max⁡t∈[T](1−B^S≤k(yt∣x∘y1:t−1))2]≤19.28e2C⋅dG+log⁡(2/δ)n.(8)\frac{1}{|J_n|}\sum_{k\in J_n}\mathop{\mathbb{E}}_{(x,y)\sim P}\left[\max_{t\in[T]}\left(1-\hat{B}_{S_{\le k}}(y_t\mid x\circ y_{1:t-1})\right)^2\right]\le19.28e^2C\cdot\frac{d_G+\log(2/\delta)}{n}. \tag*{(8)}

It remains to pass from the average loss of the bagging predictors B^S≤k\hat{B}_{S_{\le k}} to the loss of their average g^S\hat{g}_S. Fix (x,y)∈Σ⋆×ΣT(x,y)\in\Sigma^\star\times\Sigma^T, and write xt=x∘y1:t−1x_t=x\circ y_{1:t-1} for t∈[T]t\in[T]. By (7), g^S(yt∣xt)\hat{g}_S(y_t\mid x_t) is the average of B^S≤k(yt∣xt)\hat{B}_{S_{\le k}}(y_t\mid x_t) over k∈Jnk\in J_n, so Jensen’s inequality gives, for every t∈[T]t\in[T],

(1−g^S(yt∣xt))2≤1∣Jn∣∑k∈Jn(1−B^S≤k(yt∣xt))2≤1∣Jn∣∑k∈Jnmax⁡s∈[T](1−B^S≤k(ys∣xs))2.\left(1-\hat{g}_S(y_t\mid x_t)\right)^2\le\frac{1}{|J_n|}\sum_{k\in J_n}\left(1-\hat{B}_{S_{\le k}}(y_t\mid x_t)\right)^2\le\frac{1}{|J_n|}\sum_{k\in J_n}\max_{s\in[T]}\left(1-\hat{B}_{S_{\le k}}(y_s\mid x_s)\right)^2.

The right-hand side does not depend on tt. Taking the maximum over t∈[T]t\in[T] on the left-hand side, then expectations over (x,y)∼P(x,y)\sim P, and applying (8) proves the claim.

The suffix-bagging predictor (7) averages over all ordered bootstraps and is therefore intractable. We approximate its token votes by sampling finitely many predictors, as in Algorithm 1. The following sparsification bound controls the CoT risk (1) directly, in the spirit of [45 Lemma 3]. The idea is simple: the sampled majority errs at a target prefix only if at least half of the sampled predictors err there, an event whose probability decays exponentially in NN and is at most proportional to the squared error of the vote, controlled by Lemma 4. Since this quantity appears both in the bound on the expected error and in the threshold of Markov’s inequality, it cancels from the failure probability, and the number of oracle calls does not depend on nn.

Lemma 5 (Sparsification via binomial tails). Fix a realizable sample SS of size n≥4n\ge4 and a distribution PP over Σ⋆×ΣT\Sigma^\star\times\Sigma^T. Let h^=MAJ⁡(f^S1′,…,f^SN′)\hat{h}=\operatorname{MAJ}(\hat{f}_{S'_1},\ldots,\hat{f}_{S'_N}) be the majority vote, with fixed tie-breaking, of the predictors returned by the CONSCoT oracle on NN independent bootstrap samples drawn as in steps 3–4 of Algorithm 1. For any δ∈(0,1)\delta\in(0,1), if N≥max⁡{4,log⁡2(T/δ)}N\ge\max\{4,\log_2(T/\delta)\}, then, with probability at least 1−δ1-\delta over the bootstrap samples,

Pr⁡(x,y)∼P[∃t∈[T]:h^(t)(x)≠yt]≤256E(x,y)∼P[max⁡t∈[T](1−g^S(yt∣x∘y1:t−1))2].(9)\Pr_{(x,y)\sim P}\left[\exists t\in[T]:\hat{h}^{(t)}(x)\ne y_t\right]\le256\mathop{\mathbb{E}}_{(x,y)\sim P}\left[\max_{t\in[T]}\left(1-\hat{g}_S(y_t\mid x\circ y_{1:t-1})\right)^2\right]. \tag*{(9)}

Proof. Fix SS. Throughout the proof, probabilities and expectations without a subscript are over the bootstrap samples S1′,…,SN′S'_1,\ldots,S'_N. Write

r(x,y):=max⁡t∈[T](1−g^S(yt∣x∘y1:t−1))2r(x,y):=\max_{t\in[T]}\left(1-\hat{g}_S(y_t\mid x\circ y_{1:t-1})\right)^2

for the squared worst-step error of the suffix-bagging predictor on (x,y)∈Σ⋆×ΣT(x,y)\in\Sigma^\star\times\Sigma^T, so that the right-hand side of (9) is 256E(x,y)∼P[r(x,y)]256\mathop{\mathbb{E}}_{(x,y)\sim P}[r(x,y)]. Let EE be the set of examples with r(x,y)≥1/256r(x,y)\ge1/256, that is, with g^S(yt∣x∘y1:t−1)≤15/16\hat{g}_S(y_t\mid x\circ y_{1:t-1})\le15/16 for some t∈[T]t\in[T]. Then, for every realization of the bootstrap samples,

Pr⁡(x,y)∼P[∃t∈[T]:h^(t)(x)≠yt]≤P(E)+Z,Z:=Pr⁡(x,y)∼P[(x,y)∉E, ∃t∈[T]:h^(t)(x)≠yt].\Pr_{(x,y)\sim P}\left[\exists t\in[T]:\hat{h}^{(t)}(x)\ne y_t\right]\le P(E)+Z,\qquad Z:=\Pr_{(x,y)\sim P}\left[(x,y)\notin E,\ \exists t\in[T]:\hat{h}^{(t)}(x)\ne y_t\right].

Since r(x,y)≥1/256r(x,y) \ge1/256 on EE, P(E)≤256E(x,y)∼P[1{(x,y)∈E}r(x,y)]P(E) \le256\mathbb{E}_{(x,y)\sim P}[1\{(x,y) \in E\}r(x,y)]. It suffices to show that, with probability at least 1−δ1-\delta, Z≤256E(x,y)∼P[1{(x,y)∉E}r(x,y)]Z \le256\mathbb{E}_{(x,y)\sim P}[1\{(x,y) \notin E\}r(x,y)]; adding the two bounds proves (9).

By linearity of expectation,

E[Z]=E(x,y)∼P[1{(x,y)∉E}Pr⁡[∃t∈[T]:h^(t)(x)≠yt]].\mathbb{E}[Z] = \mathbb{E}_{(x,y)\sim P}\left[1\{(x,y)\notin E\}\Pr\left[\exists t\in[T]:\hat{h}^{(t)}(x)\ne y_t\right]\right].

Now fix (x,y)∉E(x,y)\notin E. By the definition of EE, we have r(x,y)<1/256r(x,y)<1/256, that is, max⁡t∈[T](1−g^S(yt∣x∘y1:t−1))<1/16\max_{t\in[T]}(1-\widehat{g}_S(y_t\mid x\circ y_{1:t-1}))<1/16, so the suffix-bagging score of the correct token exceeds 15/1615/16 at every step. Since h^\hat{h} follows the target chain-of-thought until its first mistake, it errs on (x,y)(x,y) only if h^(x∘y1:t−1)≠yt\hat{h}(x\circ y_{1:t-1})\ne y_t for some t∈[T]t\in[T]. Fix a step tt, and let p=1−g^S(yt∣x∘y1:t−1)<1/16p=1-\widehat{g}_S(y_t\mid x\circ y_{1:t-1})<1/16. We claim that the mistakes of the sampled predictors at this step are independent Bernoulli variables with mean pp. Indeed, the bootstrap samples S1′,…,SN′S'_1,\ldots,S'_N are independent, and each Sj′S'_j is drawn exactly as in (7), by choosing kk uniformly from JnJ_n and then a uniform bootstrap of S≤kS_{\le k}. Hence the indicators 1{f^Sj′(x∘y1:t−1)≠yt}1\{\widehat{f}_{S'_j}(x\circ y_{1:t-1})\ne y_t\}, for j∈[N]j\in[N], are independent, and each has mean

Pr⁡[f^Sj′(x∘y1:t−1)≠yt]=1−g^S(yt∣x∘y1:t−1)=p.\Pr\left[\widehat{f}_{S'_j}(x\circ y_{1:t-1})\ne y_t\right]=1-\widehat{g}_S(y_t\mid x\circ y_{1:t-1})=p.

If fewer than half of the sampled predictors err, then yty_t receives a strict majority of the votes. Hence h^(x∘y1:t−1)≠yt\hat{h}(x\circ y_{1:t-1})\ne y_t only if some set of ⌈N/2⌉\lceil N/2\rceil predictors all err, an event of probability p⌈N/2⌉≤pN/2p^{\lceil N/2\rceil}\le p^{N/2} for each fixed set by independence. A union bound over the at most 2N2^N such sets gives, using 4p≤1/44p\le1/4 and N≥4N\ge4,

Pr⁡[h^(x∘y1:t−1)≠yt]≤2NpN/2=(4p)2(4p)N/2−2≤16p2⋅4−N/2=256p22−N.\Pr\left[\hat{h}(x\circ y_{1:t-1})\ne y_t\right]\le2^N p^{N/2}=(4p)^2(4p)^{N/2-2}\le16p^2\cdot4^{-N/2}=256p^2 2^{-N}.

A union bound over the TT steps yields Pr⁡[∃t∈[T]:h^(t)(x)≠yt]≤256T2−Nr(x,y)\Pr[\exists t\in[T]:\hat{h}^{(t)}(x)\ne y_t]\le256T2^{-N}r(x,y) for every (x,y)∉E(x,y)\notin E. Plugging this into the expression for E[Z]\mathbb{E}[Z], and T2−N≤δT2^{-N}\le\delta (as N≥log⁡2(T/δ)N\ge\log_2(T/\delta)), we obtain

E[Z]≤256δE(x,y)∼P[1{(x,y)∉E}r(x,y)].\mathbb{E}[Z]\le256\delta\mathbb{E}_{(x,y)\sim P}[1\{(x,y)\notin E\}r(x,y)].

Markov’s inequality now implies that, with probability at least 1−δ1-\delta,

Z≤256E(x,y)∼P[1{(x,y)∉E}r(x,y)],Z\le256\mathbb{E}_{(x,y)\sim P}[1\{(x,y)\notin E\}r(x,y)],

where, if this expectation is zero, then Z=0Z=0 almost surely. This completes the proof.

Alternatively, the sparsification argument of Moran and Yehudayoff [52] approximates all suffix-bagging scores simultaneously, with a number of samples independent of TT but depending on the dual VC dimension of F\mathcal{F}. The following high-probability form follows by uniform convergence for the dual class of F\mathcal{F}.

Lemma 6 (Sparsification via dual VC dimension). Let F\mathcal{F} be a class of functions from Σ⋆\Sigma^{\star} to Σ\Sigma. For each (x,y)∈Σ⋆×Σ(x,y)\in\Sigma^{\star}\times\Sigma, define the evaluation function g(x,y):F→{0,1}g_{(x,y)}:\mathcal{F}\to\{0,1\} by g(x,y)(f):=1{f(x)=y}g_{(x,y)}(f):=1\{f(x)=y\}. The dual class of F\mathcal{F} is G:={g(x,y):(x,y)∈Σ⋆×Σ}\mathcal{G}:=\{g_{(x,y)}:(x,y)\in\Sigma^{\star}\times\Sigma\}, and its VC dimension d∗:=VCdim⁡(G)d^{\ast}:=\operatorname{VCdim}(\mathcal{G}) is the dual VC dimension of F\mathcal{F}. Let QQ be any distribution over F\mathcal{F}. For any ε,δ∈(0,1)\varepsilon,\delta\in(0,1), with probability at least 1−δ1-\delta, N=O((d∗+log⁡(1/δ))/ε2)N=O((d^{\ast}+\log(1/\delta))/\varepsilon^2) independent predictors f1,…,fN∼Qf_1,\ldots,f_N\sim Q satisfy

sup⁡(x,y)∈Σ⋆×Σ∣1N∑j=1Ng(x,y)(fj)−Ef∼Q[g(x,y)(f)]∣≤ε.\sup_{(x,y)\in\Sigma^{\star}\times\Sigma}\left|\frac{1}{N}\sum_{j=1}^{N}g_{(x,y)}(f_j)-\mathbb{E}_{f\sim Q}[g_{(x,y)}(f)]\right|\le\varepsilon.

Putting the Pieces Together

Proof of Theorem 1. Let S∼PnS \sim P^n, and let h^=MAJ⁡(f^S1,…,f^SN)\hat{h} = \operatorname{MAJ}(\hat{f}_{S_1}, \ldots, \hat{f}_{S_N}) be the output of Algorithm 1. By Lemma 4, with probability at least 1−δ/21-\delta/2 over SS,

E(x,y)∼P[max⁡t∈[T](1−g^S(yt∣x∘y1:t−1))2]≤19.28e2C(dGn+1nlog⁡4δ).(10)\mathbb{E}_{(x,y)\sim P}\left[\max_{t\in[T]}(1-\hat{g}_S(y_t\mid x\circ y_{1:t-1}))^2\right] \le19.28e^{2C}\left(\frac{d_G}{n}+\frac{1}{n}\log\frac{4}{\delta}\right). \tag*{(10)}

For every fixed SS, our choice N=max⁡{4,⌈log⁡2(2T/δ)⌉}N=\max\{4,\lceil\log_2(2T/\delta)\rceil\} allows us to apply Lemma 5 with failure probability δ/2\delta/2. Thus, with conditional probability at least 1−δ/21-\delta/2, the CoT risk (1) of h^\hat{h} is at most 256 times the left-hand side of (10). Combining the two guarantees by a union bound, with probability at least 1−δ1-\delta over the training and bootstrap samples,

Pr⁡(x,y)∼P[∃t∈[T]:h^(t)(x)≠yt]≤256⋅19.28e2C(dGn+1nlog⁡4δ).\Pr_{(x,y)\sim P}\left[\exists t\in[T]:\hat{h}^{(t)}(x)\ne y_t\right]\le256\cdot19.28e^{2C}\left(\frac{d_G}{n}+\frac{1}{n}\log\frac{4}{\delta}\right).

For dG≥1d_G\ge1, we have dG+log⁡(4/δ)≤(1+log⁡4)(dG+log⁡(1/δ))d_G+\log(4/\delta)\le(1+\log4)(d_G+\log(1/\delta)), giving the stated bound with constant 256⋅19.28(1+log⁡4)e2C256\cdot19.28(1+\log4)e^{2C}. When dG=0d_G=0, all functions in F\mathcal{F} agree on every next-token, and the CoT risk (1) is zero. The algorithm makes N=O(log⁡(T/δ))N=O(\log(T/\delta)) calls to the CONSCoT oracle, each on a bootstrap of fewer than nn labeled examples.

Distilling the Ensemble into a Single Generator

Algorithm 1 achieves the optimal, TT-independent sample complexity of Theorem 1 by aggregating an ensemble of N=max⁡{4,⌈log⁡2(2T/δ)⌉}N=\max\{4,\lceil\log_2(2T/\delta)\rceil\} generators in F\mathcal{F}. Although the ensemble is efficient to train, it must store all NN generators and evaluate each of them at every step of generation, multiplying the computational cost per token and the memory by NN. This becomes costly when the generators are frontier-scale language models. Current frontier open-weight models have hundreds of billions to trillions of parameters [31, 20, 41], so a single copy requires terabytes of memory to store and must be sharded across many GPUs to run. Moreover, the ensemble size NN grows with the CoT length TT, which is large and growing rapidly in practice. Context windows now reach millions of tokens [10], and the length of reasoning traces is estimated to increase by about 5×5\times per year [26].

We show that the ensemble can be distilled into a single generator in the class F\mathcal{F} after training, using only unlabeled prompts. The procedure draws nun_u fresh unlabeled prompts, labels them with the chain-of-thought traces generated by the majority-vote ensemble, and fits a single generator in F\mathcal{F} to those traces via empirical risk minimization. This is an instance of sequence-level distillation [42]. Distillation is a standard technique for compressing a large model or an ensemble into a smaller one [16, 36], and it is now widely used in language model training, where smaller models are trained on chains-of-thought generated by a large reasoning model [e.g., [57, 19]]. With nu≥nlog⁡(nT)n_u\ge n\log(nT) unlabeled prompts (which are much cheaper to obtain than chain-of-thought demonstrations), the distilled generator retains the O((dG+log⁡(1/δ))/n)O((d_G+\log(1/\delta))/n) CoT risk of Theorem 1.

Setting. Let h^=MAJ⁡(f^S1,…,f^SN)\hat{h}=\operatorname{MAJ}(\hat{f}_{S_1},\ldots,\hat{f}_{S_N}) be the majority-vote ensemble returned by Algorithm 1. Let PXP_X denote the prompt marginal of the distribution PP over Σ∗×ΣT\Sigma^*\times\Sigma^T realizable by f⋆∈Ff_\star\in\mathcal{F}. Distillation uses nun_u fresh prompts x1′,…,xnu′∼PXx'_1,\ldots,x'_{n_u}\sim P_X, drawn independently of h^\hat{h}, whose target chains-of-thought are not observed. Instead, each prompt is labeled by h^\hat{h}, which acts as the teacher, labeling each prompt with its own chain-of-thought yi′=h^(1:T)(xi′)y'_i=\hat{h}^{(1:T)}(x'_i). This gives the teacher-labeled sample Sˉ=((xi′,yi′))i=1nu\bar{S}=((x'_i,y'_i))_{i=1}^{n_u}, drawn i.i.d. from the distribution Ph^P_{\hat{h}} of (x,h^(1:T)(x))(x,\hat{h}^{(1:T)}(x)) for x∼PXx\sim P_X.

Since the majority-vote ensemble h^\hat{h} need not be in F\mathcal{F}, the teacher-labeled sample Sˉ\bar{S} may not be realizable by F\mathcal{F}. Thus, instead of a consistency CONSCoT oracle, we assume an ERMCoT oracle, which returns a generator in F\mathcal{F} that minimizes the empirical CoT risk. The distillation process produces a student fˉ\bar{f} by running ERMCoT on Sˉ\bar{S}:

fˉ=ERM⁡CoT(Sˉ)∈arg⁡min⁡f∈F 1nu∑i=1nu1{∃t∈[T]:f(t)(xi′)≠y^i,t′}.(11)\bar{f}=\operatorname{ERM}_{\mathrm{CoT}}(\bar{S})\in\underset{f\in\mathcal{F}}{\arg\min}\ \frac{1}{n_u}\sum_{i=1}^{n_u}\mathbf{1}\left\{\exists t\in[T]:f^{(t)}(x'_i)\ne\hat{y}'_{i,t}\right\}. \tag*{(11)}

The following proposition shows that the student fˉ\bar{f}, a single generator in F\mathcal{F}, retains the rate of Theorem 1.

Proposition 1 (Distillation to one generator). Let PP be realizable by f⋆∈Ff_\star\in\mathcal{F}, and let h^\hat{h} be any generator with Pr⁡(x,y)∼P[∃t∈[T]:h^(t)(x)≠yt]≤ε^\Pr_{(x,y)\sim P}[\exists t\in[T]:\hat{h}^{(t)}(x)\ne y_t]\le\hat{\varepsilon}. Let fˉ\bar{f} be the student (11) trained on nun_u fresh prompts x1′,…,xnu′∼PXx'_1,\ldots,x'_{n_u}\sim P_X, drawn independently of h^\hat{h} and labeled by h^\hat{h}. For every δ∈(0,1)\delta\in(0,1), with probability at least 1−δ1-\delta over the prompts,

Pr⁡(x,y)∼P[∃t∈[T]:fˉ(t)(x)≠yt]≤5ε^+9nu(dGlog⁡(2nuT+1)+log⁡8δ).(12)\Pr_{(x,y)\sim P}\left[\exists t\in[T]:\bar{f}^{(t)}(x)\ne y_t\right]\le5\hat{\varepsilon}+\frac{9}{n_u}\left(d_{\mathcal{G}}\log(2n_uT+1)+\log\frac{8}{\delta}\right). \tag*{(12)}

Consequently, if h^=MAJ⁡(f^S1′,…,f^SN′)\hat{h}=\operatorname{MAJ}(\hat{f}_{S'_1},\ldots,\hat{f}_{S'_N}) is the output of Algorithm 1 run with confidence δ\delta on S∼PnS\sim P^n with n≥4n\ge4, and fˉ\bar{f} is trained on nu≥nlog⁡(nT)n_u\ge n\log(nT) fresh prompts, then with probability at least 1−2δ1-2\delta over SS, the bootstrap samples, and the unlabeled prompts, we have

Pr⁡(x,y)∼P[∃t∈[T]:fˉ(t)(x)≠yt]=O(dG+log⁡(1/δ)n).(13)\Pr_{(x,y)\sim P}\left[\exists t\in[T]:\bar{f}^{(t)}(x)\ne y_t\right]=O\left(\frac{d_{\mathcal{G}}+\log(1/\delta)}{n}\right). \tag*{(13)}

The distillation process trades unlabeled data and a one-time computational cost after training for an NN-fold reduction in inference compute and memory. Proposition 1 retains the labeled sample complexity of Theorem 1, which is optimal and independent of TT. In Theorem 1, the dependence on TT appears only in the ensemble size NN, paid at every inference. Distillation moves the dependence on TT to the number of unlabeled prompts nu≥nlog⁡(nT)n_u\ge n\log(nT), paid once. Although the teacher-labeled distribution Ph^P_{\hat{h}} need not be realizable by F\mathcal{F}, it is nearly realizable, since f⋆f_\star and h^\hat{h} disagree only where h^\hat{h} errs, which by Theorem 1 happens with probability at most O((dG+log⁡(1/δ))/n)O((d_{\mathcal{G}}+\log(1/\delta))/n). The relative deviation inequalities of Lemma 7 exploit this to give the fast 1/nu1/n_u rate in (12), where a worst-case agnostic analysis would give only 1/nu1/\sqrt{n_u}. A similar compression-via-distillation procedure appears in [63], where unlabeled inputs, labeled by an accurate but expensive predictor, are used to train a predictor from a cheaper class. Their analysis is agnostic because their student class may have approximation error, so their bound on the number of unlabeled samples scales as 1/ε21/\varepsilon^2 rather than 1/ε1/\varepsilon.

Proof of Proposition 1

For a generator ff and a distribution DD over Σ⋆×ΣT\Sigma^\star\times\Sigma^T, write err⁡D(f):=Pr⁡(x,y)∼D[∃t∈[T]:f(t)(x)≠yt]\operatorname{err}_D(f):=\Pr_{(x,y)\sim D}[\exists t\in[T]:f^{(t)}(x)\ne y_t] for the CoT risk (1) of ff under DD, and err⁡^(f):=1nu∑i=1nu1{∃t∈[T]:f(t)(xi′)≠y^i,t′}\widehat{\operatorname{err}}(f):=\frac{1}{n_u}\sum_{i=1}^{n_u}\mathbf{1}\{\exists t\in[T]:f^{(t)}(x'_i)\ne\hat{y}'_{i,t}\} for its empirical CoT risk on the teacher-labeled sample Sˉ\bar{S}, which the student minimizes in (11). The proof relies on the following relative deviation bound for classes of binary functions, stated in terms of the growth function.

Lemma 7 ([12 Theorem 5.1 and Section 5.1.2]). Let L\mathcal{L} be a class of {0,1}\{0,1\}-valued functions on a set Z\mathcal{Z}, with growth function ΓL(k):=max⁡z1,…,zk∈Z∣{(ℓ(z1),…,ℓ(zk)):ℓ∈L}∣\Gamma_{\mathcal{L}}(k):=\max_{z_1,\ldots,z_k\in\mathcal{Z}}|\{(\ell(z_1),\ldots,\ell(z_k)):\ell\in\mathcal{L}\}|. Let DD be a distribution over Z\mathcal{Z}, and let z1,…,zm∼Dmz_1,\ldots,z_m\sim D^m. For every δ∈(0,1)\delta\in(0,1), with probability at least 1−δ1-\delta, every ℓ∈L\ell\in\mathcal{L} satisfies

Ez∼D[ℓ(z)]≤2m∑i=1mℓ(zi)+5⋅log⁡ΓL(2m)+log⁡(4/δ)m.\mathbb{E}_{z\sim D}[\ell(z)]\le\frac{2}{m}\sum_{i=1}^{m}\ell(z_i)+5\cdot\frac{\log\Gamma_{\mathcal{L}}(2m)+\log(4/\delta)}{m}.

Proof. This is a standard consequence of relative deviation inequalities, and we include its short derivation for completeness. Write γ:=(log⁡ΓL(2m)+log⁡(4/δ))/m\gamma:=(\log\Gamma_{\mathcal{L}}(2m)+\log(4/\delta))/m, A:=Ez∼D[ℓ(z)]A:=\mathbb{E}_{z\sim D}[\ell(z)] and B:=1m∑i=1mℓ(zi)B:=\frac{1}{m}\sum_{i=1}^{m}\ell(z_i). By [12 Theorem 5.1], with probability at least 1−δ1-\delta, every ℓ∈L\ell\in\mathcal{L} satisfies A≤B+2AγA\le B+2\sqrt{A\gamma}. For A,B,C≥0A,B,C\ge0, the inequality A≤B+CAA\le B+C\sqrt{A} implies A≤B+C2+CBA\le B+C^2+C\sqrt{B}, so A≤B+4γ+2Bγ≤2B+5γA\le B+4\gamma+2\sqrt{B}\gamma\le2B+5\gamma, where the last step uses 2Bγ≤B+γ2\sqrt{B\gamma}\le B+\gamma. □\square

We apply Lemma 7 to the CoT loss class L:={(x,y)↦1{∃t∈[T]:f(t)(x)≠yt}:f∈F}\mathcal{L} := \{(x,y) \mapsto1\{\exists t \in[T] : f^{(t)}(x) \ne y_t\} : f \in\mathcal{F}\} over Σ⋆×ΣT\Sigma^\star\times\Sigma^T, whose growth function is controlled by the Graph dimension of F\mathcal{F}.

Lemma 8. For any autoregressive class F\mathcal{F} with Graph dimension dGd_{\mathrm{G}} and any k≥1k \ge1, ΓL(k)≤(kT+1)dG\Gamma_{\mathcal{L}}(k) \le(kT+1)^{d_{\mathrm{G}}}.

Proof. Since a generator follows the target chain-of-thought until its first mistake, f(t)(x)≠ytf^{(t)}(x) \ne y_t for some t∈[T]t \in[T] if and only if f(x∘y1:t−1)≠ytf(x \mathbin{\circ} y_{1:t-1}) \ne y_t for some t∈[T]t \in[T]. Hence, as in [40 Theorem 3.4], the pattern that L\mathcal{L} realizes on (x1,y1),…,(xk,yk)(x_1,y_1),\ldots,(x_k,y_k) is determined by the pattern of token-level errors of ff on the kTkT next-token examples (xi∘yi,1:t−1,yi,t)(x_i \mathbin{\circ} y_{i,1:t-1},y_{i,t}), for i∈[k]i \in[k] and t∈[T]t \in[T]. Recall from § 4 that dGd_{\mathrm{G}} is the VC dimension of the token-level loss class {(x′,y′)↦1{f(x′)≠y′}:f∈F}\{(x',y') \mapsto1\{f(x') \ne y'\}: f \in\mathcal{F}\}, so by the Sauer–Shelah lemma [61], it realizes at most ∑i=0dG(kTi)≤(kT+1)dG\sum_{i=0}^{d_{\mathrm{G}}} \binom{kT}{i} \le(kT+1)^{d_{\mathrm{G}}} patterns on these kTkT examples.

Proof of Proposition 1. The student is trained on chains-of-thought generated by the teacher h^\hat{h} rather than by f⋆f_\star, so its training distribution Ph^P_{\hat{h}} need not be realizable by F\mathcal{F}. The idea is that Ph^P_{\hat{h}} differs from PP only on prompts where h^\hat{h} errs, so f⋆f_\star is nearly consistent with Sˉ\bar{S}, with empirical CoT risk O(ε^)O(\hat{\varepsilon}). The student fˉ\bar{f} minimizes the empirical CoT risk, so it inherits this small empirical risk from f⋆f_\star, and Lemma 7 converts it into a small risk, at the fast rate 1/nu1/n_u.

We first relate the two distributions. Since y=f⋆(1:T)(x)y = f_\star^{(1:T)}(x) under PP and y=h^(1:T)(x)y = \hat{h}^{(1:T)}(x) under Ph^P_{\hat{h}}, every generator ff satisfies err⁡P(f)=Pr⁡x∼PX[f(1:T)(x)≠f⋆(1:T)(x)]\operatorname{err}_{P}(f) = \Pr_{x \sim P_X}[f^{(1:T)}(x) \ne f_\star^{(1:T)}(x)] and err⁡Ph^(f)=Pr⁡x∼PX[f(1:T)(x)≠h^(1:T)(x)]\operatorname{err}_{P_{\hat{h}}}(f) = \Pr_{x \sim P_X}[f^{(1:T)}(x) \ne\hat{h}^{(1:T)}(x)]. The two events differ only on prompts where h^(1:T)(x)≠f⋆(1:T)(x)\hat{h}^{(1:T)}(x) \ne f_\star^{(1:T)}(x), so

∣err⁡P(f)−err⁡Ph^(f)∣≤err⁡P(h^)≤ε^,and in particularerr⁡Ph^(f⋆)=err⁡P(h^)≤ε^.(14)\left|\operatorname{err}_{P}(f)-\operatorname{err}_{P_{\hat{h}}}(f)\right| \le\operatorname{err}_{P}(\hat{h}) \le\hat{\varepsilon}, \qquad\text{and in particular} \qquad\operatorname{err}_{P_{\hat{h}}}(f_\star)=\operatorname{err}_{P}(\hat{h})\le\hat{\varepsilon}. \tag*{(14)}

Next, we bound the empirical CoT risk of f⋆f_\star. Since the prompts are drawn independently of h^\hat{h}, conditionally on h^\hat{h} the indicators 1{∃t∈[T]:f⋆(t)(xi′)≠yi′}1\{\exists t \in[T]: f_\star^{(t)}(x_i') \ne y_i'\}, for i∈[nu]i \in[n_u], are independent Bernoulli variables with mean p:=err⁡Ph^(f⋆)≤ε^p := \operatorname{err}_{P_{\hat{h}}}(f_\star) \le\hat{\varepsilon}. By Bernstein’s inequality [12 Section 5.1.2], with probability at least 1−δ/21-\delta/2,

err⁡^(f⋆)≤p+2plog⁡(2/δ)nu+2log⁡(2/δ)3nu≤2ε^+2log⁡(2/δ)nu,\widehat{\operatorname{err}}(f_\star) \le p + \sqrt{\frac{2p\log(2/\delta)}{n_u}}+\frac{2\log(2/\delta)}{3n_u}\le2\hat{\varepsilon}+\frac{2\log(2/\delta)}{n_u},

where the last step uses 2pL≤p+L/2\sqrt{2pL}\le p+L/2 for L=log⁡(2/δ)/nuL=\log(2/\delta)/n_u.

We now apply Lemma 7 to L\mathcal{L}, with D=Ph^D=P_{\hat{h}}, the sample Sˉ\bar{S}, and confidence δ/2\delta/2. By Lemma 8, with probability at least 1−δ/21-\delta/2, every f∈Ff \in\mathcal{F} satisfies

err⁡Ph^(f)≤2err⁡^(f)+5γ,γ:=dGlog⁡(2nuT+1)+log⁡(8/δ)nu.\operatorname{err}_{P_{\hat{h}}}(f) \le2\widehat{\operatorname{err}}(f)+5\gamma,\qquad\gamma:=\frac{d_{\mathrm{G}}\log(2n_uT+1)+\log(8/\delta)}{n_u}.

By a union bound, both bounds hold with probability at least 1−δ1-\delta. On this event, applying (14) to fˉ\bar{f}, then the last display, then err⁡^(fˉ)≤err⁡^(f⋆)\widehat{\operatorname{err}}(\bar{f})\le\widehat{\operatorname{err}}(f_\star), which holds since fˉ\bar{f} minimizes the empirical CoT risk over F\mathcal{F} and f⋆∈Ff_\star\in\mathcal{F}, and finally the bound on err⁡^(f⋆)\widehat{\operatorname{err}}(f_\star), we obtain

err⁡P(fˉ)≤err⁡Ph^(fˉ)+ε^≤2err⁡(f⋆)+5γ+ε^≤5ε^+4log⁡(2/δ)nu+5γ≤5ε^+9nu(dGlog⁡(2nuT+1)+log⁡8δ),\begin{aligned} \operatorname{err}_{P}(\bar{f}) &\le\operatorname{err}_{P_{\hat{h}}}(\bar{f})+\hat{\varepsilon} \le2\operatorname{err}(f_\star)+5\gamma+\hat{\varepsilon}\\ &\le5\hat{\varepsilon}+\frac{4\log(2/\delta)}{n_u}+5\gamma\le5\hat{\varepsilon}+\frac{9}{n_u}\left(d_{\mathrm{G}}\log(2n_uT+1)+\log\frac{8}{\delta}\right), \end{aligned}

which implies (12).

For the second statement, by Theorem 1, with probability at least 1−δ1-\delta over SS and the bootstrap samples, ε^=O((dG+log⁡(1/δ))/n)\hat{\varepsilon}=O((d_{\mathrm{G}}+\log(1/\delta))/n). Since the prompts are independent of h^\hat{h}, the first statement applies conditionally on h^\hat{h}, and a union bound gives both events with probability at least 1−2δ1 - 2\delta. Finally, since x↦log⁡(3xT)/xx \mapsto\log(3xT)/x is decreasing for x≥1x \ge1, the assumption νu≥nlog⁡(nT)\nu_u \ge n\log(nT) and log⁡(nT)≥log⁡4\log(nT) \ge\log4 give

log⁡(2νuT+1)νu≤log⁡(3νuT)νu≤log⁡3+log⁡(nT)+log⁡log⁡(nT)nlog⁡(nT)≤3n.\frac{\log(2\nu_u T + 1)}{\nu_u} \le\frac{\log(3\nu_u T)}{\nu_u} \le\frac{\log3 + \log(nT) + \log\log(nT)}{n\log(nT)} \le\frac{3}{n}.

and log⁡(8/δ)/νu≤log⁡(8/δ)/n\log(8/\delta)/\nu_u \le\log(8/\delta)/n, so the second term in (12) is O((dG+log⁡(1/δ))/n)O((d_{\mathcal{G}} + \log(1/\delta))/n).

Additional Related Work

Learning Theory of Autoregressive Chain-of-Thought. An early framework for learning from chain-of-thought data was proposed by [48], in which each time step is learned separately, with guarantees growing linearly in the CoT length TT. Later, Joshi et al. [40] introduced the time-invariant framework we adopt, and showed that the dependence on the length is mild: logarithmic in TT under chain-of-thought supervision, and in general linear under end-to-end supervision, where only the final answer is observed. In related work, Altabaa, Montasser, and Lafferty [7] introduced the CoT information, which measures the discriminative power gained by observing the chain-of-thought. More recently, Hanneke, Mehalel, and Moran [34] removed the dependence on TT under chain-of-thought supervision, at the cost of a factor of the dual VC dimension, and showed that under end-to-end supervision essentially any growth rate between constant and linear in TT can arise. In the online setting, Doron-Arad, Mehalel, and Mossel [DMM26b] obtained bounds independent of TT, in terms of the Littlestone dimension. Finally, Li [46] determined the optimal sample complexity, which scales with the DS dimension. In addition, Yang, Srebro, and Li [70] gave tight bounds on the VC dimension of transformers.

Stochastic Autoregressive Chain-of-Thought. A parallel line of work studies stochastic generators learned by next-token prediction with the logarithmic loss, and asks how the sequence-level error scales with length. In imitation learning, Foster, Block, and Misra [29] showed that behavior cloning with the logarithmic loss can achieve horizon-independent sample complexity. Under misspecification, the error of next-token prediction relative to the best model must grow with the sequence length for a broad family of objectives [58], although measuring error in the joint KL divergence avoids this growth in the approximation factor [69]. Doron-Arad, Mehalel, and Mossel [21] extended the framework of Joshi et al. [40] to binary stochastic generators under the squared loss. In contrast, we study deterministic generators in the realizable setting, where the target CoT must be reproduced exactly.

Verifiers, Rewards, and Curricula. Beyond learning from demonstrations, Balcan et al. [13] introduced a PAC framework for learning verifiers of chains-of-thought, later extended to an online setting by Balcan et al. [11]. In reinforcement learning, Jia, Rakhlin, and Xie [39] showed that outcome supervision is not statistically harder than process supervision, up to polynomial factors in the horizon. Recently, Rajaraman et al. [RDHS+26] showed that an autocurriculum, which focuses supervision on prompts the learner gets wrong, can require exponentially fewer demonstrations.

Expressivity of Chain-of-Thought. Intermediate generation increases the expressive power of transformers: they become Turing-complete [PBN21], can solve arithmetic and dynamic-programming tasks that bounded-depth transformers cannot solve directly [FZGY+23], and gain the serial computation that constant-depth transformers otherwise lack, in proportion to the number of intermediate steps [51, 47]. Even a single autoregressive neuron can simulate any feedforward circuit with the same activation, while remaining efficiently learnable from chain-of-thought supervision [50]. These results concern what can be represented, and complement the statistical question of how many demonstrations are needed to learn it.

Gradient-Based Learning and Length Generalization. Intermediate supervision can also make problems tractable for gradient-based training: suitable scratchpads overcome a globality barrier for transformers [2], and transformers trained with intermediate steps probably learn parity [44] and state-tracking tasks [37] efficiently. Conversely, training by next-token prediction with teacher forcing can fail to learn an accurate predictor on simple planning tasks [18]. A related question is length generalization, the ability to extrapolate to inputs or chains-of-thought longer than those seen in training [38, 32, 37]; in our setting, training and test chains-of-thought have the same length TT.

AI Disclosure

At a technical level, the main idea of this paper is to study the problem of autoregressive learning by adapting and extending the techniques of Montasser [49] devised for adversarially robust learning. This was conceived by the authors without the use of AI tools. Along the way, ChatGPT helped us remove a log⁡n\log n factor from the number of oracle calls (and consequently number of generators NN) in an earlier version of Lemma 5, and Claude helped us polish the writing and presentation.

References

  1. [2]Emmanuel Abbe, Samy Bengio, Aryo Lotfi, Colin Sandon, and Omid Saremi. How far can transformers reason? The globality barrier and inductive scratchpad. In Advances in Neural Information Processing Systems, 2024. URL: https://proceedings.neurips.cc/paper_files/paper/2024/hash/3107e4bdb658c79053d7ef59cbc804dd-Abstract-Conference.html.
  2. [3]Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. Optimal PAC bounds without uniform convergence. In IEEE Annual Symposium on Foundations of Computer Science, 2023. doi:10.1109/FOCS57990.2023.00071.
  3. [4]Julian Asilis, Shaddin Dughmi, Vatsal Sharan, Alec Sun, Shang-Hua Teng, and Chang Wang. Algorithmic principles for multiclass learning are hard to come by: Limits of regularization and proper learning. arXiv preprint arXiv:2608.26516, 2026.
  4. [5]Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen, and Nikita Zhivotovskiy. Majority-of-three: The simplest optimal learner? In Conference on Learning Theory, 2024. URL: https://proceedings.mlr.press/v247/aden-ali24a.html.
  5. [7]Awni Altabaa, Omar Montasser, and John D. Lafferty. CoT information: Improved sample complexity under chain-of-thought supervision. In Advances in Neural Information Processing Systems, 2025. URL: https://proceedings.neurips.cc/paper_files/paper/2025/hash/235a9abbb6303fac26f205367fe08c0b-Abstract-Conference.html.arxiv.org/abs/2505.15927
  6. [8]Leo Breiman. Bagging predictors. Machine Learning, 24(2):123–140, 1996. doi:10.1007/BF00058655.DOI
  7. [9]Leo Breiman. Out-of-bag estimation. Technical report, Department of Statistics, University of California, Berkeley, 1996.
  8. [10]Greg Burnham and Tom Adamczewski. LLMs now accept longer inputs, and the best models can use them more effectively. Epoch AI Data Insight, 2025. Accessed October 23, 2026. URL: https://epoch.ai/data-insights/context-windows.
  9. [11]Maria-Florina Balcan, Avrim Blum, Kiriaki Fragkia, Zhiyuan Li, and Dravyansh Sharma. Online learnability of chain-of-thought verifiers: Soundness and completeness trade-offs. arXiv preprint arXiv:2603.03538, 2026.
  10. [12]Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: a survey of some recent advances. ESAIM: Probability and Statistics, 9:323–375, 2005. doi:10.1051/ps:2005018.DOI
  11. [13]Maria-Florina Balcan, Avrim Blum, Zhiyuan Li, and Dravyansh Sharma. On learning verifiers and implications to chain-of-thought reasoning. In Advances in Neural Information Processing Systems, 2025. URL: https://proceedings.neurips.cc/paper_files/paper/2025/hash/e33b9cc87d3833f6769279e03011cdc1-Abstract-Conference.html.arxiv.org/abs/2505.22650
  12. [14]Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In IEEE Annual Symposium on Foundations of Computer Science, 2022. doi:10.1109/FOCS54457.2022.00093.DOI
  13. [15]Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler, and Philip M. Long. Characterizations of learnability for classes of {0, . . . ,n}-valued functions. Journal of Computer and System Sciences, 50(1):74–86, 1995. doi:10.1006/jcss.1995.1008.
  14. [16]Cristian Buciluă, Rich Caruana, and Alexandru Niculescu-Mizil. Model compression. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006. doi:10.1145/1150402.1150464.DOI
  15. [17]Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929–965, 1989. doi:10.1145/76359.76371.DOI
  16. [18]Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction. In International Conference on Machine Learning, 2024. URL: https://proceedings.mlr.press/v235/bachmann24a.html.arxiv.org/abs/2403.06963
  17. [19]DeepSeek-AI. DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning. Nature, 645(8081):633–638, 2025. doi:10.1038/S41586-025-09422-Z.DOI
  18. [20]DeepSeek-AI. DeepSeek-V4: towards highly efficient million-token context intelligence. arXiv preprint arXiv:2606.19348, 2026.arxiv.org/abs/2606.19348
  19. [21]Ilan Doron-Arad, Idan Mehalel, and Elchanan Mossel. Stochastic autoregressive learning. arXiv preprint arXiv:2608.07224, 2026.
  20. [23]Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Conference on Learning Theory, 2014. URL: https://proceedings.mlr.press/v35/daniely14b.html.arxiv.org/abs/1405.2420
  21. [24]Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the ERM principle. Journal of Machine Learning Research, 16:2377–2404, 2015. URL: https://jmlr.org/papers/v16/daniely15a.html.
  22. [25]Bradley Efron. Estimating the error rate of a prediction rule: Improvement on cross-validation. Journal of the American Statistical Association, 78(382):316–331, 1983. doi:10.1080/01621459.1983.10477973.DOI
  23. [26]Luke Emberson, Ben Cottier, Josh You, Tom Adamczewski, and Jean-Stanislas Denain. LLM responses to benchmark questions are getting longer over time. Epoch AI Data Insight, 2025. Accessed October 23, 2026. URL: https://epoch.ai/data-insights/output-length.
  24. [27]Andrzej Ehrenfeucht, David Haussler, Michael J. Kearns, and Leslie G. Valiant. A general lower bound on the number of examples needed for learning. Information and Computation, 82(3):247–261, 1989. doi:10.1016/0890-5401(89)90002-3.DOI
  25. [28]Bradley Efron and Robert Tibshirani. Improvements on cross-validation: The .632+ bootstrap method. Journal of the American Statistical Association, 92(438):548–560, 1997. doi: 10.1080/01621459.1997.10474007.DOI
  26. [29]Dylan J. Foster, Adam Block, and Dipendra Misra. Is behavior cloning all you need? Understanding horizon in imitation learning. In Advances in Neural Information Processing Systems, 2024. URL: https://proceedings.neurips.cc/paper_files/paper/2024/hash/da84e39ae51fd26bb5110d9659c06e13-Abstract-Conference.html.
  27. [31]GLM-5 Team. GLM-5: from vibe coding to agentic engineering. arXiv preprint arXiv:2602.15763, 2026.
  28. [32]Noah Golowich, Samy Jelassi, David Brandfonbrener, Sham M. Kakade, and Eran Malach. The role of sparsity for length generalization in LLMs. In International Conference on Machine Learning, 2025. URL: https://proceedings.mlr.press/v267/golowich25a.html.arxiv.org/abs/2502.16792
  29. [33]David Haussler, Nick Littlestone, and Manfred K. Warmuth. Predicting {0,1}-functions on randomly drawn points. Information and Computation, 115(2):248–292, 1994. doi: 10.1006/INCO.1994.1097.DOI
  30. [34]Steve Hanneke, Idan Mehalel, and Shay Moran. Sample complexity of autoregressive reasoning: Chain-of-thought vs. end-to-end. In IEEE Annual Symposium on Foundations of Computer Science, 2026. URL: https://arxiv.org/abs/2604.12013.
  31. [36]Geoffrey E. Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531, 2015.arxiv.org/abs/1503.02531
  32. [37]Yu Huang, Zixin Wen, Aarti Singh, Yuejie Chi, and Yuxin Chen. Transformers provably learn chain-of-thought reasoning with length generalization. In Advances in Neural Information Processing Systems, 2025. URL: https://proceedings.neurips.cc/paper_files/paper/2025/hash/b86a195e70f27017c514fa0e5f80595f-Abstract-Conference.html.arxiv.org/abs/2511.07378
  33. [38]Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Raj Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, and Michael Hahn. A formal framework for understanding length generalization in transformers. In International Conference on Learning Representations, 2025. URL: https://openreview.net/forum?id=U49N5V51rU.arxiv.org/abs/2410.02140
  34. [39]Zeyu Jia, Alexander Rakhlin, and Tengyang Xie. Do we need to verify step by step? Rethinking process supervision from a theoretical perspective. In International Conference on Machine Learning, 2025. URL: https://proceedings.mlr.press/v267/jia25f.html.
  35. [40]Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, and Nathan Srebro. A theory of learning with autoregressive chain of thought. In Conference on Learning Theory, 2025. URL: https://proceedings.mlr.press/v291/joshi25a.html.arxiv.org/abs/2503.07932
  36. [41]Kimi Team. Kimi K3: open frontier intelligence. arXiv preprint arXiv:2607.24653, 2026.
  37. [42]Yoon Kim and Alexander M. Rush. Sequence-level knowledge distillation. In Conference on Empirical Methods in Natural Language Processing, 2016. doi:10.18653/v1/D16-1139.DOI
  38. [44]Juno Kim and Taiji Suzuki. Transformers provably solve parity efficiently with chain of thought. In International Conference on Learning Representations, 2025. URL: https://openreview.net/forum?id=n2NidsYDop.arxiv.org/abs/2410.08633
  39. [45]Kasper Green Larsen. Bagging is an optimal PAC learner. In Conference on Learning Theory, 2023. URL: https://proceedings.mlr.press/v195/larsen23a.html.arxiv.org/abs/2212.02264
  40. [46]Zhiyuan Li. The optimal sample complexity of learning autoregressive chain-of-thought. arXiv preprint arXiv:2607.07423, 2026.arxiv.org/abs/2607.07423
  41. [47]Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. In International Conference on Learning Representations, 2024. URL: https://openreview.net/forum?id=3EWTeY9MTM.arxiv.org/abs/2402.12875
  42. [48]Eran Malach. Auto-regressive next-token predictors are universal learners. In International Conference on Machine Learning, 2024. URL: https://proceedings.mlr.press/v235/malach24a.html.arxiv.org/abs/2309.06979
  43. [49]Omar Montasser. Bagging robustly learns VC classes with linear sample complexity. arXiv preprint arXiv:2608.13514, 2026.arxiv.org/abs/2608.13514
  44. [50]Roey Magen, Nirmit Joshi, and Gal Vardi. The surprising expressivity of a single neuron with autoregressive chain-of-thought. arXiv preprint arXiv:2610.17283, 2026.arxiv.org/abs/2610.17283
  45. [51]William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In International Conference on Learning Representations, 2024. URL: https://openreview.net/forum?id=NjNgLPh8Wh.arxiv.org/abs/2310.07923
  46. [52]Shay Moran and Amir Yehudayoff. Sample compression schemes for VC classes. Journal of the ACM, 63(3):21:1–21:10, 2016. doi:10.1145/2890490.DOI
  47. [53]B. K. Natarajan. On learning sets and functions. Machine Learning, 4:67–97, 1989. doi:10.1007/BF00114804.DOI
  48. [54]Maxwell I. Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114, 2021.arxiv.org/abs/2112.00114
  49. [57]Qwen Team. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025.
  50. [58]Dhruv Rohatgi, Adam Block, Audrey Huang, Akshay Krishnamurthy, and Dylan J. Foster. Computational-statistical tradeoffs at the next-token prediction barrier: Autoregressive and imitation learning under misspecification (extended abstract). In Conference on Learning Theory, 2025. URL: https://proceedings.mlr.press/v291/rohatgi25a.html.DOI
  51. [60]Divit Rawal and Nikita Zhivotovskiy. Majority-of-three is optimal. arXiv preprint arXiv:2606.13614, 2026.arxiv.org/abs/2606.13614
  52. [61]Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972. doi:10.1016/0097-3165(72)90019-2.DOI
  53. [62]Robert Tibshirani. Bias, variance and prediction error for classification rules. Technical report, Department of Statistics, University of Toronto, 1996.
  54. [63]Ruth Urner, Shai Shalev-Shwartz, and Shai Ben-David. Access to unlabeled data can speed up prediction time. In International Conference on Machine Learning, 2011. URL: https://icml.cc/2011/papers/378_icmlpaper.pdf.
  55. [64]Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. doi:10.1145/1968.1972.DOI
  56. [65]Vladimir Vapnik. Statistical learning theory. Wiley, 1998.
  57. [66]V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971. doi:10.1137/1116025.DOI
  58. [67]David H. Wolpert and William G. Macready. An efficient method to estimate bagging’s generalization error. Machine Learning, 35(1):41–55, 1999. doi:10.1023/A:1007519102914.DOI
  59. [68][WWSB+22] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, 2022. URL: https://proceedings.neurips.cc/paper_files/paper/2022/hash/9d5609613524ecf4f15af0f7b31abca4-Abstract-Conference.html.arxiv.org/abs/2201.11903
  60. [69][XYZ26] Yunbei Xu, Yuzhe Yuan, and Ruohan Zhan. Autoregressive learning in joint KL: sharp oracle bounds and lower bounds. In Advances in Neural Information Processing Systems, 2026. URL: https://openreview.net/forum?id=DpKPNTCMWW.arxiv.org/abs/2605.12316
  61. [70][YSL26] Chenxiao Yang, Nathan Srebro, and Zhiyuan Li. Tight sample complexity of transformers. In Conference on Learning Theory, 2026. URL: https://proceedings.mlr.press/v336/yang26a.html.arxiv.org/abs/2606.09731

Paper details

vlnc:W_bqmqb7nj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT, Claude

View statement
Looking for related papers…
Contents