WorksComputer Science
Optimal Autoregressive Chain-of-Thought Learning via Bagging
Abstract
We study how to learn an autoregressive next-token generator from a class , given chain-of-thought (CoT) demonstrations of length generated by . 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 , independent of the CoT length , where is the VC dimension of . For finite token sets , the VC dimension is replaced by a multiclass analogue, the Graph dimension , and the sample complexity is optimal up to a factor. The number of generators in the majority-vote ensemble is , and we show that the ensemble can be distilled into a single generator in at the expense of 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 from a class , where is a set of tokens. On a prompt , the generator produces the token , then , and so on; after steps it has produced the chain-of-thought , 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 be a distribution over that is realizable by some , in the sense that . The learner observes i.i.d. samples and outputs a predictor , which is then run autoregressively. Its performance is measured by the CoT risk, where the predictor must reproduce the entire chain-of-thought, and a single incorrect token renders the output incorrect.1
The goal is to determine the sample complexity of this problem as a function of the accuracy , the confidence , the CoT length , and the complexity of the class . Moreover, this sample complexity should be attained with simple and efficient learning algorithms. When , the problem is precisely multiclass learning of with label set . 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 , where is the VC dimension of . Then, Hanneke, Mehalel, and Moran [34] showed that this factor can be removed, with a majority-vote compression scheme [52], but at the price of a factor of the dual VC dimension , which may be exponentially larger than [A83; KS23]. Afterwards, Doron-Arad, Mehalel, and Mossel [DMM26b] obtained another -independent bound through online learning, but in terms of the Littlestone dimension , which can be infinite even for simple classes (e.g., thresholds on the line).
| Reference | Sample Complexity | Alphabet | Learner |
| [40] | binary | CoT-consistent learner | |
| [34] | binary | sample-compression majority-vote | |
| [DMM26b] | arbitrary | online-to-batch conversion | |
| [46] | arbitrary | one-inclusion hypergraphs | |
| This work (Theorem 1) | arbitrary | Bagging CoT-consistent predictors | |
| Lower bound [46] | arbitrary | any learner, already for |
Table 1. Sample complexity of realizable learning with chain-of-thought supervision. Here , , , and are the VC, Graph, Littlestone, and DS dimensions of , and 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 is learnable with sample complexity , independently of , where is the Daniely–Shalev-Shwartz (DS) dimension of [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 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 , the learner builds the one-inclusion graph, whose vertices are all the chains-of-thought that functions in can generate on the training prompts and on , 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 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 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 with sample complexity , independent of the CoT length , where is the Graph dimension of (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 . The output of Algorithm 1 is an ensemble of generators, which multiplies the inference cost per token by . We further show that the ensemble can be distilled into a single generator in using unlabeled prompts while retaining the labeled sample complexity (see Proposition 1).
Algorithm 1: Bagging CoT-Consistent Predictors
Input: Training set , confidence , and a oracle (4).
Set , and .
For each :
Sample uniformly from .
Sample a bootstrap of samples uniformly with replacement from .
Run the oracle on , and let be the returned predictor.
Output: The majority-vote predictor over , defined as follows (with fixed tie-breaking):
Theorem 1. For any autoregressive class with Graph dimension , any oracle, and any distribution over such that for some , for every and every , letting , with probability at least over the random draw of a training dataset and over the bootstrap samples drawn as in Algorithm 1,
Remark 1 (Optimality). The sample complexity in Theorem 1 compares with known lower bounds as follows.
Binary alphabets. The bound is optimal since is exactly the VC dimension of , and this matches the classical lower bound for PAC learning [27], which holds already for .
Finite alphabets. The bound is optimal up to a factor of : the Graph dimension satisfies , where is the Natarajan dimension of [53, 15 DSB S15], while multiclass learning, and hence our problem, requires samples [53, 24].
Remark 2. The same guarantee holds with bootstrap samples (and oracle calls), where is the dual VC dimension of (see Lemma 6). Hence suffices.
Algorithm 1 is simple and efficient. It accesses the class only through a oracle, which it calls times, and its output is itself a next-token generator: each token is obtained by evaluating the base predictors on the current prefix and returning the most frequent prediction, so a chain-of-thought of length costs only evaluations of predictors in . We also remark that, like bagging in general [8], both training and inference in Algorithm 1 can be parallelized across the base predictors. Moreover, the ensemble can be distilled into a single generator in after training, removing the factor of 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 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 , can attain the optimal sample complexity . The answer is unfortunately no. The obstruction is inherited from multiclass learning, and therefore arises already for , where our problem reduces to multiclass learning of . In our context, recent impossibility results for aggregations of proper learners [AHV25] have two consequences. First, there are classes on which majorities of consistent learners require samples, so the dependence on the Graph dimension in Theorem 1 is tight for Algorithm 1. Second, there is a class 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 . Hanneke, Mehalel, and Moran [34] proceed with an analysis based on sample compression schemes, which removes the dependence on but incurs a factor of the dual VC dimension . 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 be a class with Graph dimension , fix an arbitrary CONSCoT oracle, and let 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 obtained from random training samples . 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:
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 . For a single CoT-consistent predictor, Li [46 Theorem 6.2] shows that a dependence on is unavoidable: for a suitable binary class and CONSCoT oracle,
The proof of (2) rests on a simple observation. For each test example, we fix in advance the step at which a random predictor is most likely to err; this choice depends on , , 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 , 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 .
Bagging Leave-One-Out Analysis. Bound (2) concerns predictors trained on fresh samples from , whereas Algorithm 1 trains predictors on bootstraps of a single sample . To connect the two, we consider an idealized bagging predictor, which aggregates the CoT-consistent predictors trained on all ordered bootstraps of . For and , its bagging score is the fraction of these predictors that predict on :
We bound its leave-one-out error. The key observation is that a bootstrap of of size omits the -th example with probability , and is then a bootstrap of the sample 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 are samples from its empirical distribution , the observation reduces the leave-one-out error to the quantity bounded in (2), for in place of (Lemma 3):
By (2), the right-hand side is . Finally, by exchangeability (Remark 3), (3) also bounds by 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 as well, independently of .
High-probability Bound and Sparsification. To obtain a high-probability bound with the optimal dependence on , 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 of the sample, and whose squared worst-step error is 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 , each requiring a call to the oracle. A key idea in Algorithm 1 is to randomly sample 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 samples suffice, independently of (Lemma 5). The reason is that only the votes on the target prefixes of each example matter: at each of them, the sampled majority errs with probability exponentially small in and proportional to the squared error controlled by Lemma 4, and a union bound over the 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 . Alternatively, the classical sparsification argument of Moran and Yehudayoff [52] gives , independently of (Lemma 6), but the dual VC dimension can be exponentially larger than [A83; KS23].
Technical Definitions
Autoregressive Learning. We recall the setting of § 1 and fix notation. Let be a set of tokens, finite or infinite, let be the set of finite strings over , and write for each positive integer . For a generator and a prompt , the generated tokens are defined recursively by
where is concatenation, and . The learner receives from a distribution over realizable by , and is evaluated by its CoT risk (1).
CoT-Consistent Oracle. Our algorithms access only through a CONSCoT oracle: a deterministic rule that, given a sample realizable by , returns reproducing every chain-of-thought in :
We call such a generator CoT-consistent with . Equivalently, it correctly predicts every next token along the chains-of-thought in : for all and .
Complexity Measures. We briefly review four standard combinatorial dimensions of , viewed as a class of next-token predictors from to : the VC, Graph, Natarajan, and DS dimensions. For prompts , write for the set of next-token patterns that realizes on them. Each dimension below is the largest for which some prompts are shattered in the corresponding sense, or if no largest exists.
VC dimension [66], for : are shattered if .
Graph dimension [53]: are G-shattered if there are tokens such that, for every , some satisfies exactly for . Equivalently, is the VC dimension of the 0-1 loss class over .
Natarajan dimension [53]: are N-shattered if there are tokens , for , such that, for every , some satisfies for and for .
DS dimension [23, 14]: are DS-shattered if contains a -dimensional pseudo-cube, that is, a nonempty finite set in which every pattern has, for each , a neighbor with and for all .
When the class is clear from context, we simply write , , , and . For binary alphabets, all four notions coincide: . For finite alphabets, they are related by
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 and 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 with Graph dimension , any CONSCoT oracle, and any distribution over such that for some , for every and every , letting , with probability at least over the random draw of a training dataset and over the bootstrap samples drawn as in Algorithm 1,
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 , the probability over the training sample that errs on the prefix 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 with Graph dimension , any oracle, and any distribution over such that for some ,
where 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 factor.
Lemma 2 [5, 60]. There is a universal constant such that the following holds. Let be a distribution on , and let be a class of subsets of with VC dimension . Let be a deterministic selector such that for every and . Then,
Proof of Lemma 1. The quantity is the error probability of 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 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 , let be the smallest index attaining the maximum in the definition of , and define the map by
In words, 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 , labeled by the correct token at step . The map depends on , , and the oracle, but not on the sample . Writing , we have by construction
We now verify the conditions of Lemma 2: we exhibit a class of subsets of of VC dimension at most , together with a deterministic selector into this class whose selected set is disjoint from the sample. For each , define the error region relative to , and the class of all such regions, by
We have if and only if , where is the token-level error region of . Hence, if shatters points, then shatters their images under , which are necessarily distinct, and therefore .
Next, consider the selector , which is deterministic and takes values in . By realizability, there exists satisfying . By (4) it follows that is CoT-consistent with the sample ; that is, for all and . In particular, for every , so that with probability $1.
We are now ready to invoke Lemma 2. By (5), , so Lemma 2, applied to and the selector , yields
Bagging
Bagging. We introduce notation for bagging. For a sequence and a bootstrap size , let be a bootstrap of examples returned uniformly at random (with replacement) from , and let be the predictor returned by the oracle (4) on . Equivalently, we can express this as drawing a sequence of indices uniformly at random, and denote the bootstrap sample by .
Define the bagging predictor , which maps each input to a distribution over , whose bagging score is the fraction of the ordered bootstraps of of size on which the returned predictor outputs on input :
Since each predictor outputs exactly one token, , so is indeed a conditional distribution over next tokens; on input , the majority vote of all bootstrapped predictors outputs the mode of this distribution. When the bootstrap size equals the size of its source sample, we use the shorthand .
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 with Graph dimension , any oracle, and any realizable sequence with ,
Remark 3 (Expected Risk). Note that by an exchangeability argument, applying Lemma 3 to a sample of size yields the expected bound
Since the majority vote of all bootstrapped predictors errs on the chain-of-thought of only if the bagging distribution puts at most half of its mass on the correct token at some step, that is, only if for some step , its expected CoT risk (1) is at most .
Proof of Lemma 3. The idea is that a bootstrap of of size omits the -th example with probability at least , and is then simply a bootstrap of . The leave-one-out errors are therefore controlled by the errors of bagging on the full sequence , to which Lemma 1 applies with being the uniform distribution over . This is the observation underlying the out-of-bag estimate of the error of bagging [9].
Let and . Fix and , and write and for the corresponding prefix and its next token. Draw uniformly from . Conditionally on the event , which has probability , the index sequence is uniform over , so is a bootstrap of of size . Hence, by the law of total probability and (6),
In words, CoT-consistent predictors trained on bootstraps of fail to predict on at most times as often as those trained on bootstraps of .
Now observe that, for every ,
is precisely the quantity of Lemma 1, for the distribution and samples of size . Combining this identity with the comparison above, taking the maximum over , and squaring, we obtain, for each ,
Averaging over , and noting that the average of over the examples of is its expectation under , we obtain
where the last inequality follows from Lemma 1, which applies since is realizable because is. The lemma follows since for .
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 with , let
Here is a prefix of length . We introduce next the suffix-bagging predictor which averages the bagging predictors over suffixes and then proceed to bound its risk with high probability. Formally, define, for and ,
As an average of the distributions , is again a distribution over , and is the probability that the CONSCoT oracle, run on a random bootstrap of a randomly chosen prefix, predicts token on input . 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 with Graph dimension , any CONSCoT oracle, any distribution over such that for some , any , and any , with probability at least over ,
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 of the sample; we then pass from this average to the suffix-bagging predictor by Jensen’s inequality.
The bagging predictor is invariant under permutations of , 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 by , uniformly over all realizable sequences, and this loss takes values in . 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 over ,
It remains to pass from the average loss of the bagging predictors to the loss of their average . Fix , and write for . By (7), is the average of over , so Jensen’s inequality gives, for every ,
The right-hand side does not depend on . Taking the maximum over on the left-hand side, then expectations over , 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 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 .
Lemma 5 (Sparsification via binomial tails). Fix a realizable sample of size and a distribution over . Let be the majority vote, with fixed tie-breaking, of the predictors returned by the CONSCoT oracle on independent bootstrap samples drawn as in steps 3–4 of Algorithm 1. For any , if , then, with probability at least over the bootstrap samples,
Proof. Fix . Throughout the proof, probabilities and expectations without a subscript are over the bootstrap samples . Write
for the squared worst-step error of the suffix-bagging predictor on , so that the right-hand side of (9) is . Let be the set of examples with , that is, with for some . Then, for every realization of the bootstrap samples,
Since on , . It suffices to show that, with probability at least , ; adding the two bounds proves (9).
By linearity of expectation,
Now fix . By the definition of , we have , that is, , so the suffix-bagging score of the correct token exceeds at every step. Since follows the target chain-of-thought until its first mistake, it errs on only if for some . Fix a step , and let . We claim that the mistakes of the sampled predictors at this step are independent Bernoulli variables with mean . Indeed, the bootstrap samples are independent, and each is drawn exactly as in (7), by choosing uniformly from and then a uniform bootstrap of . Hence the indicators , for , are independent, and each has mean
If fewer than half of the sampled predictors err, then receives a strict majority of the votes. Hence only if some set of predictors all err, an event of probability for each fixed set by independence. A union bound over the at most such sets gives, using and ,
A union bound over the steps yields for every . Plugging this into the expression for , and (as ), we obtain
Markov’s inequality now implies that, with probability at least ,
where, if this expectation is zero, then 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 but depending on the dual VC dimension of . The following high-probability form follows by uniform convergence for the dual class of .
Lemma 6 (Sparsification via dual VC dimension). Let be a class of functions from to . For each , define the evaluation function by . The dual class of is , and its VC dimension is the dual VC dimension of . Let be any distribution over . For any , with probability at least , independent predictors satisfy
Putting the Pieces Together
Proof of Theorem 1. Let , and let be the output of Algorithm 1. By Lemma 4, with probability at least over ,
For every fixed , our choice allows us to apply Lemma 5 with failure probability . Thus, with conditional probability at least , the CoT risk (1) of is at most 256 times the left-hand side of (10). Combining the two guarantees by a union bound, with probability at least over the training and bootstrap samples,
For , we have , giving the stated bound with constant . When , all functions in agree on every next-token, and the CoT risk (1) is zero. The algorithm makes calls to the CONSCoT oracle, each on a bootstrap of fewer than labeled examples.
Distilling the Ensemble into a Single Generator
Algorithm 1 achieves the optimal, -independent sample complexity of Theorem 1 by aggregating an ensemble of generators in . Although the ensemble is efficient to train, it must store all generators and evaluate each of them at every step of generation, multiplying the computational cost per token and the memory by . 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 grows with the CoT length , 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 per year [26].
We show that the ensemble can be distilled into a single generator in the class after training, using only unlabeled prompts. The procedure draws fresh unlabeled prompts, labels them with the chain-of-thought traces generated by the majority-vote ensemble, and fits a single generator in 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 unlabeled prompts (which are much cheaper to obtain than chain-of-thought demonstrations), the distilled generator retains the CoT risk of Theorem 1.
Setting. Let be the majority-vote ensemble returned by Algorithm 1. Let denote the prompt marginal of the distribution over realizable by . Distillation uses fresh prompts , drawn independently of , whose target chains-of-thought are not observed. Instead, each prompt is labeled by , which acts as the teacher, labeling each prompt with its own chain-of-thought . This gives the teacher-labeled sample , drawn i.i.d. from the distribution of for .
Since the majority-vote ensemble need not be in , the teacher-labeled sample may not be realizable by . Thus, instead of a consistency CONSCoT oracle, we assume an ERMCoT oracle, which returns a generator in that minimizes the empirical CoT risk. The distillation process produces a student by running ERMCoT on :
The following proposition shows that the student , a single generator in , retains the rate of Theorem 1.
Proposition 1 (Distillation to one generator). Let be realizable by , and let be any generator with . Let be the student (11) trained on fresh prompts , drawn independently of and labeled by . For every , with probability at least over the prompts,
Consequently, if is the output of Algorithm 1 run with confidence on with , and is trained on fresh prompts, then with probability at least over , the bootstrap samples, and the unlabeled prompts, we have
The distillation process trades unlabeled data and a one-time computational cost after training for an -fold reduction in inference compute and memory. Proposition 1 retains the labeled sample complexity of Theorem 1, which is optimal and independent of . In Theorem 1, the dependence on appears only in the ensemble size , paid at every inference. Distillation moves the dependence on to the number of unlabeled prompts , paid once. Although the teacher-labeled distribution need not be realizable by , it is nearly realizable, since and disagree only where errs, which by Theorem 1 happens with probability at most . The relative deviation inequalities of Lemma 7 exploit this to give the fast rate in (12), where a worst-case agnostic analysis would give only . 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 rather than .
Proof of Proposition 1
For a generator and a distribution over , write for the CoT risk (1) of under , and for its empirical CoT risk on the teacher-labeled sample , 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 be a class of -valued functions on a set , with growth function . Let be a distribution over , and let . For every , with probability at least , every satisfies
Proof. This is a standard consequence of relative deviation inequalities, and we include its short derivation for completeness. Write , and . By [12 Theorem 5.1], with probability at least , every satisfies . For , the inequality implies , so , where the last step uses .
We apply Lemma 7 to the CoT loss class over , whose growth function is controlled by the Graph dimension of .
Lemma 8. For any autoregressive class with Graph dimension and any , .
Proof. Since a generator follows the target chain-of-thought until its first mistake, for some if and only if for some . Hence, as in [40 Theorem 3.4], the pattern that realizes on is determined by the pattern of token-level errors of on the next-token examples , for and . Recall from § 4 that is the VC dimension of the token-level loss class , so by the Sauer–Shelah lemma [61], it realizes at most patterns on these examples.
Proof of Proposition 1. The student is trained on chains-of-thought generated by the teacher rather than by , so its training distribution need not be realizable by . The idea is that differs from only on prompts where errs, so is nearly consistent with , with empirical CoT risk . The student minimizes the empirical CoT risk, so it inherits this small empirical risk from , and Lemma 7 converts it into a small risk, at the fast rate .
We first relate the two distributions. Since under and under , every generator satisfies and . The two events differ only on prompts where , so
Next, we bound the empirical CoT risk of . Since the prompts are drawn independently of , conditionally on the indicators , for , are independent Bernoulli variables with mean . By Bernstein’s inequality [12 Section 5.1.2], with probability at least ,
where the last step uses for .
We now apply Lemma 7 to , with , the sample , and confidence . By Lemma 8, with probability at least , every satisfies
By a union bound, both bounds hold with probability at least . On this event, applying (14) to , then the last display, then , which holds since minimizes the empirical CoT risk over and , and finally the bound on , we obtain
which implies (12).
For the second statement, by Theorem 1, with probability at least over and the bootstrap samples, . Since the prompts are independent of , the first statement applies conditionally on , and a union bound gives both events with probability at least . Finally, since is decreasing for , the assumption and give
and , so the second term in (12) is .
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 . Later, Joshi et al. [40] introduced the time-invariant framework we adopt, and showed that the dependence on the length is mild: logarithmic in 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 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 can arise. In the online setting, Doron-Arad, Mehalel, and Mossel [DMM26b] obtained bounds independent of , 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 .
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 factor from the number of oracle calls (and consequently number of generators ) in an earlier version of Lemma 5, and Claude helped us polish the writing and presentation.
References
- [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.
- [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.
- [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.
- [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.
- [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
- [8]Leo Breiman. Bagging predictors. Machine Learning, 24(2):123–140, 1996. doi:10.1007/BF00058655.DOI
- [9]Leo Breiman. Out-of-bag estimation. Technical report, Department of Statistics, University of California, Berkeley, 1996.
- [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.
- [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.
- [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
- [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
- [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
- [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.
- [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
- [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
- [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
- [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
- [20]DeepSeek-AI. DeepSeek-V4: towards highly efficient million-token context intelligence. arXiv preprint arXiv:2606.19348, 2026.arxiv.org/abs/2606.19348
- [21]Ilan Doron-Arad, Idan Mehalel, and Elchanan Mossel. Stochastic autoregressive learning. arXiv preprint arXiv:2608.07224, 2026.
- [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
- [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.
- [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
- [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.
- [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
- [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
- [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.
- [31]GLM-5 Team. GLM-5: from vibe coding to agentic engineering. arXiv preprint arXiv:2602.15763, 2026.
- [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
- [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
- [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.
- [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
- [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
- [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
- [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.
- [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
- [41]Kimi Team. Kimi K3: open frontier intelligence. arXiv preprint arXiv:2607.24653, 2026.
- [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
- [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
- [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
- [46]Zhiyuan Li. The optimal sample complexity of learning autoregressive chain-of-thought. arXiv preprint arXiv:2607.07423, 2026.arxiv.org/abs/2607.07423
- [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
- [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
- [49]Omar Montasser. Bagging robustly learns VC classes with linear sample complexity. arXiv preprint arXiv:2608.13514, 2026.arxiv.org/abs/2608.13514
- [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
- [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
- [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
- [53]B. K. Natarajan. On learning sets and functions. Machine Learning, 4:67–97, 1989. doi:10.1007/BF00114804.DOI
- [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
- [57]Qwen Team. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025.
- [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
- [60]Divit Rawal and Nikita Zhivotovskiy. Majority-of-three is optimal. arXiv preprint arXiv:2606.13614, 2026.arxiv.org/abs/2606.13614
- [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
- [62]Robert Tibshirani. Bias, variance and prediction error for classification rules. Technical report, Department of Statistics, University of Toronto, 1996.
- [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.
- [64]Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. doi:10.1145/1968.1972.DOI
- [65]Vladimir Vapnik. Statistical learning theory. Wiley, 1998.
- [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
- [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
- [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
- [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
- [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