Stochastic Autoregressive Learning

Stochastic Autoregressive Learning Ilan Doron-Arad1 , Idan Mehalel2 , and Elchanan Mossel1 1

2

MIT The Hebrew University

arXiv:2608.07224v1 [cs.LG] 7 Aug 2026

Abstract Motivated by large language models (LLMs), which generate outputs by iteratively sampling from next-token distributions, we introduce a PAC-learning model for binary stochastic autoregressive learning. This generalizes the deterministic autoregressive learning framework of Joshi et al., COLT 2025. In our model, one fixed generator assigns a Bernoulli next-token distribution to every prompt string. Starting from an input prompt, a token is sampled and appended to the prompt; the same generator is then applied again to this expanded prompt; this procedure is repeated for M steps. Three forms of supervision are considered: base one-step samples, chain-of-thought (CoT) samples that reveal full random trajectories of length M , and end-to-end (e2e) samples that reveal only the final token of length M trajectories. For a generator class, we study the minimum number of samples mbase (ε), mCoT (ε), me2e (ε), respectively, required to learn the one-step probabilities in the base model, and the final-token probability in the CoT and e2e models, under squared loss error ε. We show that stochastic autoregressive learning fundamentally differs from the deterministic theory. At scale ε, there is no universal comparison between the three learning tasks: both mCoT /mbase and me2e /mCoT can be made simultaneously arbitrarily larger than M/ε, the natural analogue for the existing deterministic results. Nevertheless, after altering scales, for every class, CoT learning at scale ε is upper bounded by base learning at scale ε/M 2 , whereas e2e learning at scale ε is upper bounded,

up to logarithmic factors, by (M/ε) · mCoT (Θ(ε)). In other words, mCoT (ε) ≲ mbase Θ ε/M 2 and me2e (ε) ≲ (M/ε) · mCoT (Θ(ε)). We also prove that these dependencies and scale changes are essentially necessary. We complement these bounds by studying dimension d logistic functions in our model. First, we prove an improper e2e e 2 log M/ε) samples. Second, we show that an efficient proper CoT learner upper bound of O(d achieves the same asymptotic bound. Finally, we separate CoT from e2e learning on this class by ruling out such an efficient proper learner for e2e under the learning parity with noise (LPN) assumption.

Contents 1 Introduction 1.1 The model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 3 7

2 Proof sketches

8

3 Preliminaries

13

4 Simultaneous exact-scale lower bound

16

5 Base-to-CoT comparison

23

6 Upper bound on e2e via CoT 26 6.1 Tightness of the shifted-scale comparison . . . . . . . . . . . . . . . . . . . . . . . . 28 6.2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 7 Fat-shattering bounds for end-to-end learning

33

8 Case study: stochastic logistic autoregressive learning 8.1 An explicit non-efficient statistical e2e learner . . . . . . . . . . . . . . . . . . . . . . 8.2 An efficient proper CoT learner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 An efficient-proper-learning hardness result . . . . . . . . . . . . . . . . . . . . . . .

40 40 42 47

9 Pathologies of other dimensions 51 9.1 Pathology of pseudo-dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 9.2 VC pathology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 10 The KL Loss and Sampling Trajectories 10.1 A KL loss for one-token prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2 The KL chain rule and sampling (margin-free) . . . . . . . . . . . . . . . . . . . . . 10.3 The margin assumption: one side is free, the other is not . . . . . . . . . . . . . . . . 10.4 Upper bounds for squared loss transfer to sampling . . . . . . . . . . . . . . . . . . . 10.5 End-to-end supervision cannot sample (margin-free) . . . . . . . . . . . . . . . . . . 10.6 Lower bounds for KL-sampling (margin-free) . . . . . . . . . . . . . . . . . . . . . .

54 54 55 57 59 65 67

11 Discussion and future work

70

A Proofs of auxiliary preliminary tools

70

1

Introduction

Large language models (LLMs) are, on an abstract level, stochastic autoregressive generators: given a prompt (input string), they assign a next-token distribution depending on the context, sample a token from this distribution, append it to the context, and repeat with the expanded context. Thus, even when the task is not inherently iterative, the output is produced by an iterated next-token process. This viewpoint is central to modern LLMs [40, 42, 43]. A recent line of theoretical work abstracts this process through autoregressive chain-of-thought learning. This model was introduced in the pioneering work of Joshi, Vardi, Block, Goel, Li, Misiakiewicz, and Srebro [12], where a deterministic next-token function is iterated for M steps. The model introduces two supervision settings: in the chain-of-thought (CoT) model, the learner observes the whole autoregressive trajectory, while in the end-to-end (e2e) model, the learner observes only the final output token. In both models, the goal is to predict the final output token in a PAC-learning setting. The picture by now is well understood: at a high level, CoT samples reduce the autoregressive task to a problem comparable to the base learning problem of the same function class, whereas e2e samples can be substantially harder. Recent works give a near complete sample complexity taxonomy relating the base, CoT, and e2e learning problems [12, 9, 25, 54]. This abstraction misses a fundamental feature of modern language models: randomness is essential for language generation. In practice, an LLM does not deterministically choose the next token given the prompt; rather, it specifies a next-token probability distribution. This is not a minor technicality: likelihood training learns probabilities over tokens, sampling turns these probabilities into diverse plausible continuations, and self-consistency aggregates multiple sampled trajectories from the same prompt [42, 44, 36]. This also changes the nature of chain-of-thought samples: in the deterministic model, observing a trajectory reveals exact intermediate labels; in a stochastic model, even a full trajectory reveals only one noisy sample from the intermediate probabilities. Motivated by this, we study a stochastic regression analogue of autoregressive chain-of-thought learning. A generator assigns a probability distribution over the next token at every prompt. Iterating this rule for multiple steps gives a distribution over trajectories. Under squared loss, the target is learning the final-token probability: the stochastic analogue of the deterministic final token.

1.1

The model

This section defines the stochastic autoregressive learning model, the two supervision models CoT and e2e, as well as the preliminary tools needed to state our results. Stochastic autoregressive generators. Let Σ = {0, 1} be the binary token alphabet, and fix a generation length M ≥ 1. A stochastic next-token generator is a map g : Σ⋆ → ∆(Σ), and a ⋆ stochastic generator class is a set F ⊆ ∆(Σ)Σ , where ∆(Σ) is the set of all distributions over Σ. Given a prompt x ∈ Σ⋆ , the M -step stochastic chain of thought Z1 , . . . , ZM is generated by iteratively sampling the next token Zt from the distribution specified by g(xZ1 . . . Zt−1 ), i.e., the corresponding distribution of the original prompt concatenated by the trajectory prefix obtained so far. Formally, Z1 ∼ g(x),

Zt | Z1 , . . . , Zt−1 ∼ g(xZ1 · · · Zt−1 )

2 ≤ t ≤ M.

The M -step end-to-end output probability is the probability that the last generated token is 1: qge2e−M (x) := Pr(ZM = 1 | X = x). g

1

For M = 1, let pg (s) := qge2e−1 (s) = g(s)(1) be the one-step probability of output 1 at state s. Namely, pg (s) is the one-step probability at state s, while qge2e−M (x) is the global final-token probability from prompt x. For example, when M = 2, it holds that qge2e−2 (x) = pg (x)pg (x1) + (1 − pg (x))pg (x0). Supervision models.

Fix a distribution P on prompts Σ⋆ .

• end-to-end e2e: the learner receives i.i.d. samples (Xi , Zi,M )ni=1 , where Xi ∼ P , and Zi,1 , . . . , Zi,M are generated autoregressively from an unknown g⋆ ∈ F. Thus, only the final bit Zi,M of each sample i is given to the learner. • chain-of-thoughts CoT: the learner receives the full i.i.d. trajectories (Xi , Zi,1 , . . . , Zi,M )ni=1 . In both models, at test time the learner receives only a fresh X ∼ P . Thus, CoT and e2e differ only in the supervision available during training: a full autoregressive trajectory versus only the final Bernoulli sample. under square loss. This is the stochastic analogue of the deterThe goal is to estimate qge2e−M ⋆ ministic final label [12], with the natural regression target for the observed final bit. Note that for M = 1, both supervision models reduce to the base one-step regression problem. We give below the general PAC-learning regression formulation stated according to our setting. ⋆

Regression. Let G ⊆ [0, 1]Σ . For a specified supervision model and sample size n, a learner based on the corresponding n i.i.d. training examples (ε, δ)-learns a target q⋆ ∈ G under squared loss if, for every distribution P on Σ⋆ , with probability at least 1 − δ over those training examples and the learner’s randomness, it outputs qb : Σ⋆ → [0, 1] satisfying h i q (X) − q⋆ (X))2 ≤ ε. EX∼P (b We say that a single learner (ε, δ)-learns G if this holds uniformly for every q⋆ ∈ G and every P . The following makes precise the sample complexity for each supervision model. Sample complexity.

For 0 < δ < 1, define, uniformly over any distribution P on Σ⋆ and g⋆ ∈ F:

mF base (ε, δ): the least n for which n i.i.d. samples (Xi , Yi ) with Xi ∼ P and Yi | Xi ∼ Bern(pg⋆ (Xi )) suffice to (ε, δ)-learn pg⋆ . ,M e2e−M . mF CoT (ε, δ): the least n for which n i.i.d. full CoTs (Xi , Zi,1 , . . . , Zi,M ) suffice to (ε, δ)-learn qg⋆ ,M e2e−M . mF e2e (ε, δ): the least n for which n i.i.d. e2e samples (Xi , Zi,M ) suffice to (ε, δ)-learn qg⋆

By convention, zero-sample learners are allowed. If no finite n satisfies the requirement, the samF ,M F ,M ple complexity is +∞. When δ = 1/3, we omit it and simply write mF base (ε), mCoT (ε), and me2e (ε). We assume henceforth that all function classes satisfy the standard pointwise-measurability convention [39, 16]: Whenever a proof optimizes over an arbitrary real-valued class using the training sample, the same optimization is assumed to be approximable arbitrarily well by optimizing over a countable subcollection. In particular, exact empirical risk minimizers may be replaced by measurable almost-minimizers. This only excludes nonmeasurable pathologies and is automatic for finite and parametric classes.1 For example, for pathological uncountable classes, supf ∈F |n−1 probability statements about it may not be well-defined. 1

2

Pn

i=1 f (Xi ) − Ef (X)| need not be measurable, so

1.2

Our results

Our main motivation is to understand the sample complexity of stochastic autoregressive e2e learning, both compared to CoT learning and compared to the base one-step class. This is analogous to the deterministic line of work [12, 9, 25], where sample complexity is governed by the VC dimension [45]. Showing that both CoT, e2e learning can sometimes be much easier than learning the base class is trivial, as there are classes for which one-step probabilities are complex yet every trajectory of M steps always yields the same token.2 In addition, for every class F , M ≥ 1, and 0 < ε, δ < 1, ,M F ,M it holds that mF CoT (ε, δ) ≤ me2e (ε, δ), since a CoT learner can ignore the intermediate tokens and use only the final-token observations. Nevertheless, except for these trivial bounds, not much is known. In particular, can learning CoT be as easy as learning the base class, like in the deterministic setting? How much harder can e2e learning be with respect to CoT learning and the base class? We give answers to these questions below. Then, we study the class of logistic generators in the stochastic autoregressive model and show what can be done for each of the supervision models CoT and e2e.

general sample-complexity comparisons In the deterministic case, the sample complexity of learning with CoT-supervision is independent of M for any VC-class [9], while the analog quantity without CoT-supervision can grow linearly with M [12]. One might have expected to see similar behavior for the stochastic model. Our first result shows that, unlike in the deterministic setting, the exact-accuracy stochastic model has no universal comparison between base, CoT, and e2e learning. For the same class, we show that both ratios mCoT /mbase and me2e /mCoT can be made arbitrarily larger than the factor M/ε, which is the natural analogue for the results in the deterministic setting. Theorem 4.1 (informal). For all sufficiently large M , all sufficiently small ε > 0, and every A ≥ 1 there is a finite stochastic autoregressive class F such that 0 < mF base (ε) < ∞ and ,M mF M CoT (ε) >A , F ε mbase (ε)

,M mF e2e (ε) ,M mF CoT (ε)

>A

M . ε

Thus, at the exact same accuracy scale, neither one-step learning controls chain-of-thought learning, nor chain-of-thought learning controls end-to-end learning. As a consequence, meaningful comparisons of the three learning tasks require different scales. In the next results, we give effectively tight comparisons between the three tasks. A summary is given in Table 1. We note that Section 2 gives the proof sketches of the main results, and full proofs are given in later sections. We state the results below informally and simplistically. Formal statements including (the standard) logarithmic dependence on the confidence parameter δ are given in the paper body. We first upper bound the sample complexity of CoT (at scale ε) by the base class sample complexity at the scale ε/M 2 . This upper bound holds for general stochastic classes and is nearly tight in two different aspects: (i) it can be realized by a specific class at the used scale, and (ii) any qualitatively larger scale in the base class cannot control (to any ratio) CoT learning. Theorem 5.1 (informal). For every class F, every M ≥ 1, and every 0 < ε < 1,  ε  ,M F mF (ε) ≤ m . base CoT M2 Moreover, this upper bound is nearly tight: 2

For example, take a complex class H on length-L inputs. Let gf (x)(1) = f (x) on length-L prompts, and let gf (s)(1) = 0 after any token is appended. The base problem sees H, but for every M ≥ 2 the final token is always 0.

3

Results mCoT me2e (ε), (ε) = ω mbase mCoT



M ε



mCoT (ε) ≲ mbase (ε/M 2 ) me2e (ε) ≲

M · mCoT (cε) ε

Table 1: Informal summary of our general sample complexity results. 1. There is a constant κ > 0 such that for every integer L ≥ 1, every M ≥ 2, and  all sufficiently
F ,M ε LM 2 F small ε > 0, there is a finite class F such that mCoT (ε), mbase κ M 2 = Θ . ε 2. For every 0 < β < 1 and every K ≥ 1, there is a finite class F with mF base
F ,M K the same time mCoT (ε) = Ω ε .

 1−β  ε M2

= 0 but at

Interestingly, for comparing CoT and e2e, all that is needed is a constant change in the scale. Specifically, we show that e2e sample complexity is bounded by at most M ε -times the sample complexity of CoT learning, assuming the latter is strictly positive; this result is realized by some class, and the scale naturally cannot be improved by more than a constant to the exact same scale e to suppress logarithmic factors and use ∨ for max. by Theorem 4.1. We use O Theorem 6.3 (informal). There is a constant c such that, for every class F, M ≥ 2, and 0 < ε < 1,    ,M (cε) M 1 ∨ mF CoT ,M e . mF e2e (ε) ≤ O ε In addition, there is a constant ρ > 0 such that for every N ≥ 1, every M ≥  2, and all
sufficiently F ,M M F ,M small ε > 0, there is a finite class F satisfying me2e (ε) = Θ ε mCoT (ρε) = Θ N ε·M . As a corollary of the above two theorems, we can bound me2e by an expression of mbase . Corollary 6.4 (informal). There isc > 0 such that for  every class F , every M ≥ 2, and every F 2 ,M e M (1∨mbase (cε/M )) , 0 < ε < 1 it holds that mF e2e (ε) ≤ O ε Fat-shattering upper bound for e2e learning. The results for the deterministic autoregressive model [12, 9, 25] focus primarily on learning dimensions. While we show above that this cannot be imitated precisely for the stochastic model, we do show a result connecting the sample complexity of any e2e class to the fat shattering dimension of the base class.3 The reason we focus on fat shattering rather than pseudo-dimension is that the right analogue for the stochastic setting must depend on the accuracy parameter ε. Namely, we show that accuracy-free analogues, such as pseudo-dimension of the base class or majority over the final token, behave pathologically and do 3

For completeness, we give the relevant definition of learning dimensions in Section 3.

4

not give a meaningful theory for stochastic autoregressive learning; see Section 9. In the following result, we show a nearly tight upper bound on me2e in terms of fat-shattering of the base class. Theorem 7.6 (informal). For every fixed 0 < α ≤ 1, there is cα > 0 such that  1+α  √ M fatF (cα ε/M ) F ,M e . me2e (ε) ≤ Oα ε Moreover, this upper bound is nearly tight: 1. For every d ≥ 1, every M ≥ 1, and all sufficiently small ε > 0, there is a finite class F with
√ ,M dM fatF (c ε/M ) = Θ(d) and mF (ε) = Ω . e2e ε 2. For every 0 < β < 1/2, every M ≥ 2, and
every K ≥ 1, there is a finite class F such that ,M K fatF (cε1/2−β /M ) = 0 but mF e2e (ε) = Ω ε . For e2e, the fat-shattering upper bound is tight up to logarithmic factors and the arbitrarily small M α slack. The last part shows that the margin scale itself is also optimal: a coarser margin can miss classes with arbitrarily large e2e sample complexity. Whether a better upper bound can be shown for CoT is left for future work (see Section 11).

Logistic case study The above results give a detailed picture on general worst-case classes. We choose one canonical class whose base class sample complexity is well-known, and study its stochastic autoregressive sample complexity under CoT and e2e supervision. For s ∈ {0, 1}⋆ , let taild (s) ∈ {0, 1}d be the last d bits of s, padded by zeros on the left if |s| < d, and let σ(a) = 1/(1 + e−a ) be the sigmoid, or logistic, function. Define Fσ (d) as the class of all generators whose prediction rule at every input s is taken by applying the logistic function over the inner product of taild (s) and some d-dimensional vector w: n o Fσ (d) := gw | w ∈ Rd , pgw (s) = σ(⟨w, taild (s)⟩) . That is, the same logistic rule is reused at every step, depending only on the last d tokens and the hidden vector w. This class is a finite-memory simplification of the next-token mechanism used by modern autoregressive language models [40, 42, 43]. For comparison, the base problem for this Fσ (d) e class satisfies mbase (ε, δ) ≤ O((d + log(1/δ))/ε), by the pseudo-dimension bound for generalized linear classes and the standard bounded squared-loss regression guarantee [2, 10]. We show a polynomial sample complexity for e2e learning of the class Fσ (d) and show that with CoT supervision, an efficient proper algorithm achieves a similar bound. Finally, we rule out such an efficient proper algorithm for e2e learning under the standard learning parity with noise (LPN) assumption [19]. A summary of our results for this class is given in Table 2. A learner is called proper if it always outputs a generator in the class, and improper otherwise. For computational statements about Fσ (d), a proper learner outputs a rational vector w b with polynomially many bits, representing the generator gwb . Its running time includes evaluating and approximately sampling from this generator to polynomially small error. We present below our result for e2e learners, using an information-theoretic (inefficient) and improper learner. Theorem 8.1 (informal). For every d ≥ 1, M ≥ 2, 0 < ε < 1, and 0 < δ < 1, it holds that  2  d log M + log(1/δ) Fσ (d),M e . me2e (ε, δ) ≤ O ε 5

Supervision

Learner type

Efficiency

improper

Sample complexity in d, M e 2 log M/ε) O(d

e2e CoT

proper

e 2 log M/ε) O(d

efficient

e2e

proper

ruled out under LPN

efficient

non-efficient

Table 2: A qualitative summary of our results for the logistic class. Conversely, the following result shows that for CoT this polynomial dependence on d and logarithmic on M can be achieved efficiently and with a proper learner given full CoT supervision. Theorem 8.2 (informal). There is a randomized polynomial-time proper  2 learner that for every e d ≥ 1, M ≥ 2, 0 < ε < 1, and 0 < δ < 1 learns Fσ (d) using O d log M +log(1/δ) full CoT ε trajectories. Finally, we separate CoT from e2e by showing that e2e cannot admit such a proper efficient learning algorithm under the standard learning parity with noise (LPN) [19]: no polynomial-time algorithm can predict well a hidden parity rule from examples whose labels have been randomly corrupted. Theorem 8.3 (informal). Assume the LPN prediction assumption holds. Then no proper randomized polynomial-time algorithm can learn Fσ (d) with e2e supervision for all horizons M ≤ d. Thus, autoregressive logistic regression gives a concrete statistical and computational separation between chain-of-thought and proper end-to-end learning. Learning objectives beyond square loss. Our main objective is squared-loss estimation of the final-token probability, the standard boundedregression analogue of predicting the final label in the deterministic model. However, we believe that analogous results hold under L1 loss, and we also study KL-based trajectory sampling as explained below. L1 loss. We believe that our techniques can generally be adapted to obtain the following analogous results under L1 loss, although we do not prove these adaptations here. Write mbase,1 , mCoT,1 , and me2e,1 for the corresponding L1 sample complexities. Since one-step errors accumulate linearly along a stochastic trajectory, average one-step L1 error ε/M should yield, on average over the random prompt, total-variation distance at most ε between the true and learned length-M trajectory distributions. More specifically, the L1 analogue of Theorem 4.1 should give exact-scale separations arbitrarily larger than M/ε2 ; the analogue of Theorem 5.1 should give mCoT,1 (ε) ≤ mbase,1 (ε/M ), with matching complexity Θ(LM 2 /ε2 ) and optimal base accuracy scale ε/M ; and the analogue e of Theorem 6.3 should give me2e,1 (ε) ≤ O(M (1 ∨ mCoT,1 (cε))/ε2 ), with a matching lower bound eα (M 1+α fatF (cα ε/M )/ε2 ) up to logarithmic factors. The analogue of Theorem 7.6 should give O samples, together with a lower bound matching up to logarithmic factors and a factor of M α . The e L1 analogue of Corollary 6.4 should be me2e,1 (ε) ≤ O(M (1 ∨ mbase,1 (cε/M ))/ε2 ). The analogues 2 e of Theorems 8.1 and 8.2 should use O((d log M + log(1/δ))/ε2 ) samples, while the proper-learning hardness in Theorem 8.3 should be unchanged. We focus on squared loss because it is the standard objective for regression.

6

KL objective. In practice, an LLM works by repeatedly sampling according to approximate onestep conditional probabilities. Thus, learning the one-step probabilities pg⋆ exactly enables sampling an answer to a prompt from the correct autoregressive distribution. For LLMs, it is more common to use KL divergence rather than L1 or L22 distance. In Section 10, we discuss the implications of our results for estimating one-step probabilities in KL divergence and for sampling trajectories with small KL divergence, along with the necessary definitions. The KL-sampling consequence of Theorem 5.1, the corresponding one-step fat-shattering upper bound, and the KL consequence of the proper logistic learner in Theorem 8.2 require the one-step probabilities to be bounded away from 0 and 1. In contrast, the KL chain rule, the faithful-sampling consequence of one-step KL control, and all our KL lower bounds are margin-free; the proper-learning hardness in Theorem 8.3 is also unchanged. Moreover, no general trajectory-KL analogue of Theorem 6.3 or Corollary 6.4 is possible, since end-to-end supervision may reveal no information about the trajectory distribution. The margin requirement for the squared-loss-to-KL upper bounds is unavoidable: without a margin, small squared error does not imply small, or even finite, KL divergence. See Section 10 for more details.

1.3

Related work

The closest prior work is the deterministic autoregressive PAC model of Joshi et al. [12] as discussed in the introduction. Hanneke et al. [9] gave a near-complete deterministic sample-complexity taxonomy for this model, and the model was recently generalized to online learning [25] and multiple thinkers [48] (with potentially different CoTs but the same final output). Our work differs from all of the above works by studying the stochastic variant of the autoregressive CoT model. A different statistical theory of CoT supervision was developed by Altabaa, Montasser, and Lafferty [22]. Their model treats CoT as an abstract auxiliary supervision signal, rather than as a trajectory generated by an autoregressive next-token process. Chain-of-thought supervision is also conceptually related to learning using privileged information [35], since intermediate states are observed during training but not at test time. Foster et al. [41] study a more general model called imitation learning that includes autoregressive generation as a special case. Corollary C.4 in [41] has better dependence on d than Theorem 8.2 for logistic generators with bounded weights and feature norms. Theorem 8.2 instead applies to unrestricted weights. Other recent works [52, 11] study learning the full autoregressive sequence distribution from complete trajectories when the true generator does not necessarily belong to the model class. In contrast, we study realizable learning of final-token probabilities under base, CoT, and e2e supervision. Intermediate reasoning traces have been studied extensively in empirical work [34, 37, 29, 38, 36, 49, 50, 32]. A separate theoretical line studies their computational role in concrete models, especially transformers and simple linear predictors trained on chain-of-thought data [33, 31, 51, 53, 30]. The one-step base class learning problem in our model is learning a Bernoulli conditional mean under squared loss: given samples Y | X = x ∼ Bern(p(x)), learn p(x) distribution-free. This problem was studied in probabilistic concept learning [27] and is covered by decision-theoretic PAC learning [10]. In addition, our dimension upper bound uses the standard scale-sensitive theory of real-valued learning through fat-shattering [3, 1, 2]. PAC and generalization guarantees have also been studied for probabilistic and weighted automata [24, 23]. These works learn automaton-based distributions or string functions. Finally, our computational lower bound for proper end-to-end learning is based on noisy parity, in line with standard statistical query and cryptographic hardness tools in PAC learning [26, 19, 28].

7

Organization. Section 2 gives proof sketches for the main results. Section 3 collects the preliminaries. Section 4 proves the exact-scale lower bound. Section 5 proves the base-to-CoT comparison. Section 6 proves the CoT-to-e2e comparison. Section 7 proves the fat-shattering bounds for e2e learning. Section 8 proves the results for stochastic logistic autoregressive learning. Section 9 explains why several alternative dimension measures are insufficient. Section 10 discusses KL loss and trajectory sampling. Section 11 discusses open problems. Appendix A contains auxiliary preliminary proofs.

2

Proof sketches

We give below the main ideas behind the proofs. The sketches suppress constants and logarithmic factors, but keep the high level constructions and the reason each sample-complexity scale appears, while avoiding mathematical technicalities and heavy preliminary machinery. Full proofs are given in later sections. We use a few simple terms throughout: a prompt is an input string; a root is a specially chosen prompt where the construction may depend on a hidden bit or sign; a state below a root r is any extension rz with z ∈ Σ⋆ ; and a block is a set of roots together with the states below them. Proof sketch of Theorem 4.1. The proof builds a finite class as a union of two subfamilies. The first subfamily is based on a class GN , which separates base learning from CoT learning. The second subfamily is based on a class HB , which separates CoT learning from e2e learning. Each class has an associated prompt block, disjoint from the other class’s block. In this construction, each root has the form w1 for some prefix w. For every generator in the class, we set pg (w) = 0 at each such prefix. Thus, a trajectory that reaches w cannot move next to the root w1, so trajectories starting outside a block cannot accidentally enter one of its roots. The associated block of GN contains the roots r1 , . . . , rN . A generator in GN is indexed by signs σ = (σ1 , . . . , σN ) ∈ {−1, 1}N . The transitions below rj are chosen so that qge2e−M (rj ) = σ

√ 1 + β ε σj , 2

where β > 1 is a fixed sufficiently large universal constant. All non-root prompts have M -step values independent of σ. The class GN also contains a fixed generator g0 . The class HB depends on a parameter B, chosen at the end. Its associated block contains the roots x0 , x1 , . . . , xd . The class HB contains a fixed baseline generator h0 , and the other generators are indexed by a bit b ∈ {0, 1} and a sign vector s ∈ {−1, 1}d , where d ≫ BM/ε. For every generator h ̸= h0 , the first two generated tokens from each root x0 , . . . , xd are 1 and then b, so one full trajectory for M ≥ 2 from any such root reveals b to a CoT learner. In addition, at x0 , the finaltoken probability is b, and at x1 , . . . , xd , the final-token probabilities are weakly sign-dependent. Namely, for h = hb,s ̸= h0 , it holds that qhe2e−M (x0 ) = b,

qhe2e−M (xj ) =

1 √ + ε sj 2

j = 1, . . . , d.

Again, all non-root prompts have M -step values independent of the hidden signs. The final class is F = {fg : g ∈ GN } ∪ {fh : h ∈ HB }, where fg agrees with g on the GN prompt block and with the fixed generator h0 on the HB prompt block, while fh agrees with the fixed generator g0 on the GN prompt block and with h on the HB prompt block. 8

We now explain the sample complexity bounds. The base problem is easy because the weak √ signs change one-step probabilities only by order ε. Thus, at squared-loss accuracy ε, the learner can ignore these signs. Hence, mF base (ε) = O(1/ε). GN ,M We now explain why mCoT (ε) = Θ(N/ε). We use the uniform prompt distribution on r1 , . . . , rN . Then, a sample gives useful information about σj only if it starts at rj , which happens √ with probability 1/N , and even then the observation is only weakly biased, by order ε. Therefore, each sign needs order 1/ε samples to learn effectively, and there are N signs. Thus, fewer than order N/ε samples leave many signs unknown. Since each wrong sign gives squared loss of order β 2 ε, N ,M and β is a large constant, the loss exceeds ε with constant probability. Hence mGCoT (ε) = Ω(N/ε). Conversely, O(N/ε) samples suffice by estimating each sign from the trajectories that start at its root. For HB , learning with CoT is easier. For every generator h ̸= h0 , a full trajectory from any root reveals the bit b deterministically. If the probability that the prompt X is one of x0 , . . . , xd is less than a constant multiple of ε, the learner can ignore these roots. Otherwise, O(1/ε) samples see one of these roots with constant probability, and a full trajectory reveals b. The learner then predicts b at x0 and predicts 1/2 at x1 , . . . , xd . The loss on x1 , . . . , xd is only order ε, since their √ B ,M final-token probabilities are 1/2 ± ε. Therefore mH CoT (ε) = O(1/ε). The e2e lower bound for HB uses x0 to hide the bit b and x1 , . . . , xd to hide many weak signs. Put probability η ≍ ε/(BM ) on x0 , and spread the remaining probability equally over x1 , . . . , xd . With fewer than BM/ε samples, with constant probability no sample starts at x0 , so b remains unknown and x0 creates unavoidable loss. Since d ≫ BM/ε, most roots x1 , . . . , xd are unseen, so their signs remain unknown and contribute about ε loss. Together, these two losses exceed ε with B ,M (ε) > BM/ε. probability greater than 1/3. Hence, mH e2e Thus, overall we have the following scales: part mbase mCoT me2e GN O(1/ε) Θ(N/ε) not used HB O(1/ε) O(1/ε) > BM/ε. In the union, the GN block gives mCoT /mbase of order N , while the HB block gives me2e /mCoT of order (BM/ε)/(N/ε) = BM/N . Choosing N ≍ AM/ε and B ≍ AN/ε makes both ratios larger than AM/ε for arbitrarily large A, while keeping 0 < mF base (ε) < ∞. Proof sketch of Theorem 5.1. The upper bound is a reduction from a full trajectory to a onestep sample. Given a trajectory (X, Z1 , . . . , ZM ), set St = XZ1 · · · Zt−1 for every t ∈ {1, . . . , M }. Choose a random index T uniformly from {1, . . . , M }, and set S = ST and Y = ZT . Then Y | S ∼ Bern(pg⋆ (S)), so these are valid base samples. Assume a base learner estimates pg⋆ with squared loss at most ε/M 2 on this random state distribution. Let pb be this estimate, and define the generator gb by gb(s)(1) = pb(s) and gb(s)(0) = 1 − pb(s). Comparing the true and learned trajectories using the same random variables at each step and applying a union bound over the M possible split times gives # "M X e2e−M e2e−M |qg⋆ (x) − qgb (x)| ≤ E |pg⋆ (St ) − pb(St )| X = x . t=1

Squaring the last display, using Jensen for the outer expectation and Cauchy–Schwarz for the sum over times, gives

9



qge2e−M (x) − qgbe2e−M (x) ⋆

2

≤M ·E

"M X

# 2

(pg⋆ (St ) − pb(St ))

X=x .

t=1

hP i M 2 is M times the squared loss of p (p (S ) − p b (S )) Now average over X. The term E b on g t t ⋆ t=1 the random state ST , as T is uniform on {1, . . . , M }. Since the last display already has an outside factor M , the final squared loss is at most M 2 times this one-step squared loss. Thus, one-step accuracy ε/M 2 is enough for CoT accuracy ε. Lower bounds. The tightness construction has two disjoint blocks. The first block has K = LM 2 roots u1 , . . . , uK and each root uk has a sign σk ∈ {±1}. From uk , each step has probability p0 +σk ∆ √ of producing the first 1, where p0 ≍ 1/M and ∆ ≍ ε/M . Once the token 1 appears, the remaining transitions are fixed and no longer depend on σk . Over M steps these small one-step changes add √ up to a final-token separation of order ε between the two possible different signs of a root. Under ,M the uniform distribution on the uk ’s, we have mF roots CoT (ε) = Ω(K/ε). The second block has L √ v1 , . . . , vL and signs τℓ ∈ {±1}. At vℓ , the one-step probability is 1/2 + τℓ θ, where θ ≍ ε/M , but after the first bit, all later bits are forced to 0. Hence, this block is invisible to the final-token target but hard for the base problem at scale ε/M 2 . To learn this block a learner of the base class requires Θ(LM 2 /ε) samples. Thus, the base and CoT complexities match up to constants. For scale optimality, use only the first block u1 , . . . , uk introduced above. At the one-step √ level, every sign changes probabilities by only ∆ ≍ ε/M , so predicting always the midpoint p0 has squared error O(ε/M 2 ) pointwise, hence, zero-sample learning at every coarser scale such as √ ε1−β /M 2 . But the M small changes accumulate into final-token separation of order ε, so CoT learning still requires Ω(K/ε) trajectories. Proof sketch of Theorem 6.3. The main idea in the proof is to construct an e2e learner based on the existence of a CoT learner. Note that the resulting e2e learner still uses only final-token samples. For a fixed prompt distribution P , the construction starts from a family of final-token predictors q1 , . . . , qL ∈ {qge2e−M : g ∈ F} such that, for every i ̸= j, EX∼P [(qi (X) − qj (X))2 ] ≥ Cε for a sufficiently large constant C > 1. For each qi , choose a generator gi ∈ F such that qi = qge2e−M . i If a CoT learner succeeds at accuracy cε, for sufficiently small 0 < c < 1, then trajectories generated from gi identify qi : the learner’s output is close to qi , while the output of every other qj is far from qi under P . Now choose a uniformly random index i ∈ {1, . . . , L} and generate the training data from gi . The only information about i is carried by the generated tokens. With m trajectories of length M , there are only m · M such bits. Therefore, by Fano’s inequality, the number L of separated predictors cannot be too large: roughly, ,M log L ≲ M · mF CoT (cε).

Thus, CoT learnability limits how many well-separated e2e predictors the class can induce. From here, a standard regression argument over a finite list of representative e2e predictors then gives the claimed e2e upper bound of the theorem. The constant shift in accuracy is what lets the learner identify the correct qi .

10

1

2

···

M

1 2 ···

σj,i

N Figure 1: Illustration of the lower bound construction in Theorem 6.3 CoT trajectories reveal all coordinates in a row, so accuracy ρε costs order N samples. e2e samples reveal only one weak final bit from one cell, so recovering the N M signs costs order N M/ε. The number of columns is just for an illustration and is only ≍ M . Lower bound. The construction here is a grid of roots. There are N rows and ≍ M columns. Each cell xji contains one weak sign σj,i , and the prompt distribution is uniform over all cells. The √ local transitions are chosen so that the final-token probability at input prompt xji is 1/2 ± ε according to the sign of σj,i . A CoT trajectory from row j reveals the intermediate tokens that encode all signs in that row. Therefore, learning at the shifted accuracy ρε costs order N samples: one needs to see the rows, but not separately learn all cells. In contrast, an e2e sample reveals only the final noisy bit at its starting cell. Thus, the e2e learner must essentially learn all ≍ N M weak signs, and each sign needs order 1/ε samples. This gives   M F ,M F ,M me2e (ε) = Θ (ρε) . m ε CoT for a constant 0 < ρ < 1. Hence, the M/ε factor in Theorem 6.1 is unavoidable. Proof sketch of Theorem 7.6. For the upper bound, Suppose x1 , . . . , xn are γ-fat-shattered by F e2e−M := {qge2e−M | g ∈ F} for some class F . Then, there exist 2n witnesses in F e2e−M that are 2γ-separated in the ℓ∞ metric. Therefore, the γ/2-covering number of F e2e−M on x1 , . . . , xn is at least 2n . To upper-bound this covering number, we cover the one-step class on the finite tree U = {xi z : i ∈ [n], z ∈ {0, 1}<M } at scale η = γ/(2M ). If two generators in F differ by at most η on every state in U , then a step-bystep coupling shows that their length-M trajectories split with probability at most M η = γ/2 by a union bound. Hence, their end-to-end probabilities differ by at most γ/2. Thus, the end-to-end covering number is controlled by the one-step covering number on U . Let N∞ := N∞ (η, {pg : g ∈ F}, U ) be the minimum number of functions needed to approximate every one-step probability function pg within ℓ∞ error η on all points in U . The fat-shattering lower bound and the coupling upper bound together give 2n ≤ N∞ . We then use the Rudelson–Vershynin estimate [14] to upper bound log N∞ using fatF (cα η), up to logarithmic factors in |U | and 1/η. Since |U | ≤ n2M , this gives an inequality in n, and solving it gives the stated bound. We now explain why the upper bound can nearly be realized by a specific class. Fix a target dimension parameter d. The construction has d disjoint blocks. In block j, a parameter θj encodes 11

an M -bit sign vector σj = (σj,1 , . . . , σj,M ). At the one-step level, every state in block j is just a threshold test of θj : for a state u with threshold tu , the local probability is pg (u) = 1/2+a if θj ≥ tu and pg (u) = 1/2 − a otherwise. Thus, the positive one-step states inside one block are nested, so a √ fat-shattered set can contain at most one state from each block. This gives fatF (c ε/M ) = Θ(d). The end-to-end behavior is different. Block j contains roots xj,1 , . . . , xj,M , and the autoregressive tree below xj,i is arranged so that the final-token probability reads the i-th encoded sign: √ qge2e−M (xj,i ) = 1/2 + Θ( ε)σj,i . Hence, the induced e2e problem contains dM independent weak signs. Overall, this gives ,M mF e2e (ε) = Ω(dM/ε). √ Finally, we show that the margin ε/M cannot be replaced by any slightly larger margin ε1/2−β /M . For arbitrarily large K, take K roots r1 , . . . , rK , each with an independent sign σk . Along the all-zero path below rk (i.e., rk 0 . . . 0), set the transition probabilities to be ≈ 1/2 + √ σk ε/M at each of the M steps; outside this path, the generator is fixed. Therefore, at every √ one-step state, the possible probabilities differ by only O( ε/M ). For a sufficiently small ε, this is too small to shatter even one point at scale ε1/2−β /M . Although each one-step change is only √ of order ε/M , the final-token probability depends on all M steps. Therefore, the total change √ √ at root rk is of order ε, so the two possible final-token probabilities are separated by Θ( ε). Thus, the K roots form K independent weak signs and learning them to loss ε requires Ω(K/ε) e2e samples. Proof sketch of Theorem 8.1. An important property of the logistic class, is that the nexttoken probability depends only on the last d bits: pw (s) = σ(⟨w, taild (s)⟩). Thus, the autoregressive process can be viewed as a finite Markov chain on the possible last-d-bit states. The key point we use is description complexity. For a fixed prompt x, the final-token probability qge2e−M (x) can w be written, after a change of variables uj = ewj , as a rational function in u1 , . . . , ud : for a state Q y ∈ {0, 1}d , set Uy = dℓ=1 uyℓ ℓ , where uℓ = ewℓ . Then the probability of emitting b ∈ {0, 1} from state y is Uyb Pr(Z = b | y) = . w 1 + Uy Thus, for a fixed prompt x, the M -step final-token probability qge2e−M (x) is a sum over lengthw M paths of products of such terms, and is therefore a rational function of u1 , . . . , ud . After the change of variables uj = ewj , the quantity qge2e−M (x) is a ratio Nx (u)/Dx (u) of two polynomials, w with Dx (u) > 0 on the domain uj > 0. Hence the threshold test qge2e−M (x) ≥ a is equivalent to w the single polynomial inequality Nx (u) − aDx (u) ≥ 0. The path expansion gives degree at most M d2d−1 . Applying a result of Goldberg and Jerrum [47] shows that the the pseudo-dimension of the end-to-end class is at most O(d2 log M ). Applying the standard bounded-regression sample bound to the end-to-end class gives the desired bound. This learner is improper and not computationally efficient. It is improper because it learns the induced final-token predictor qge2e−M directly, rather w than outputting a generator in the class. It is inefficient because the proof only gives an existence argument for a good predictor. Proof sketch of Theorem 8.2. In contrast to e2e learning, in CoT learning, the full trajectory reveals the state at every generated bit: Yt = taild (XZ1 · · · Zt−1 ),

Zt | Yt ∼ Bern(σ(⟨w, Yt ⟩)). 12

Thus, given n full trajectories, the learner can treat the nM observed transitions as logisticregression examples. Writing Yi,t = taild (Xi Zi,1 · · · Zi,t−1 ), it minimizes n

M

XX b n (w) = 1 L [log (1 + exp(⟨w, Yi,t ⟩)) − Zi,t ⟨w, Yi,t ⟩] . nM i=1 t=1

The optimization is over a polynomially bounded box and can be solved to the required additive b n (w) is convex in w. The proof rounds the true vector w⋆ to accuracy in polynomial time, since L a finite-precision vector v⋆ so that the two generators produce almost the same full trajectories. It is therefore enough to analyze learning in a finite grid of parameters. On this grid, the empirical likelihood minimizer is close to v⋆ in trajectory distribution by a standard finite-class likelihood argument. If two generators produce nearly the same full trajectories, then their last-token probabilities are also close. The finite grid has logarithmic size O(d2 log(CdM/(εδ))) after compression, e 2 log M/ε) trajectory bound. The learner is so the finite-class likelihood argument gives the O(d proper because it outputs a generator gwb . It is efficient because the likelihood is convex and the compressed parameters have polynomial bit complexity. Proof sketch of Theorem 8.3. The reduction starts from LPN examples (x, y), where x ∈ Fm 2 and y = ⟨a, x⟩F2 ⊕ ξ for an unknown a ∈ Fm 2 and noise ξ ∼ Bern(η), with fixed 0 < η < 1/2 bounded away from 1/2. The LPN prediction assumption is that no algorithm can learn the function f (x) = ⟨a, x⟩F2 from these noisy samples . The reduction maps each x to a binary prompt ϕm (x) ∈ {0, 1}⋆ , and the hidden vector a determines a weight vector wa ∈ Rd , where d is polynomial in m. The generator gwa is constructed so that, for M = m + 1, qge2e−M (ϕm (x)) ≈ η + (1 − 2η)⟨a, x⟩F2 . wa Specifically, during the first m autoregressive steps, the generator produces bits that behave like the products ai xi : each such bit is produced by a logistic transition that outputs the desired value with probability very close to 1. The XOR of these bits is ⟨a, x⟩F2 . The last step then reads this parity: the final-token probability is close to η if ⟨a, x⟩F2 = 0, and close to 1 − η if ⟨a, x⟩F2 = 1. The weights have polynomial bit complexity, so gwa is polynomial-time constructible. Now assume an efficient proper e2e learner exists. On the transformed LPN samples, it outputs a generator gwb with final-token probabilities close to those of gwa . Because the output is a generator, we can run it many times from a fresh prompt ϕm (x) and estimate Prgwb (ZM = 1 | ϕm (x)). If this estimate is above 1/2, predict ⟨a, x⟩F2 = 1; otherwise predict 0. Since the true final-token probability is near η in the parity-0 case and near 1 − η in the parity-1 case, thresholding at 1/2 predicts ⟨a, x⟩F2 with nontrivial advantage, contradicting the LPN prediction assumption.

3

Preliminaries ⋆

Given a stochastic generator class F ⊆ ∆(Σ)Σ , the one-step class induced by F is F e2e−1 := {qge2e−1 : g ∈ F} and let F e2e−M := {qge2e−M : g ∈ F} be its end-to-end class. This section provides preliminary definitions and known preliminary results used in our proofs.

Learning Dimensions We give below fundamental learning dimensions. 13

VC dimension. For A ⊆ {0, 1}X , a set x1 , . . . , xd ∈ X is shattered by A if every labeling of the set is realized by some h ∈ A. The VC dimension VC(A) is the largest such d, or infinity. Fat-shattering dimension. For A ⊆ [0, 1]X and γ > 0, a set x1 , . . . , xd is γ-fat-shattered by A if there are thresholds r1 , . . . , rd such that for every b ∈ {−1, 1}d there is fb ∈ A satisfying fb (xi ) ≥ ri + γ

fb (xi ) ≤ ri − γ

if bi = 1,

if bi = −1.

The largest such d is called the fat-shattering dimension of A at scale γ and is denoted by fatA (γ). This is the standard scale-sensitive dimension for real-valued distribution-free learning [3, 1, 2]. Pseudo-dimension. The pseudo-dimension Pdim(A) is the same notion without a margin: x1 , . . . , xd are pseudo-shattered if there are thresholds r1 , . . . , rd such that every strict pattern above or below these thresholds is realized by a function in A.

Preliminary Results The auxiliary lemmas below are used throughout. Proofs of the auxiliary lemmas that are not quoted directly are collected in Appendix A. We use the following standard finite-class fast-rate bound. Lemma 1. There is a constant C > 0 such that the following holds. Let (X, Y ) be a joint distribution with Y ∈ [0, 1], let A ⊆ [0, 1]X be finite and nonempty, and let f⋆ : X → [0, 1] be f⋆ (x) := E[Y | X = x]. Let α ≥ 0. If f ◦ ∈ A satisfies E[(f ◦ (X) − f⋆ (X))2 ] ≤ α, then, for every 0 < ε < 1 and 0 < δ < 1/2, C log |A|+log(1/δ) samples suffice to output fb with E[(fb(X) − f⋆ (X))2 ] ≤ α + ε with ε probability at least 1 − δ. The following standard fat-shattering regression bound follows from a distribution-free empirical-net construction, the finite-class aggregation bound above, and the L2 entropy theorem of Mendelson and Vershynin [13, Theorem 1]. Lemma 2. There are universal constants c, C > 0 such that the following holds. Let A ⊆ [0, 1]X , and let (X, Y ) be a joint distribution on X × [0, 1] with regression function f⋆ : X → [0, 1] defined by f⋆ (x) := E[Y | X = x]. Assume f⋆ ∈ A. Then, for every 0 < ε < 1 and every 0 < δ < 1/2, √ fatA (c ε) logC (C/ε)+log(1/δ) there is a learner that uses C samples and outputs fb : X → [0, 1] satisfying ε 2 E[(fb(X) − f⋆ (X)) ] ≤ ε with probability at least 1 − δ. KL divergence and total variation. Let P, Q be probability measures on the same measurable space (Ω, G). We write P ≪ Q if P is absolutely continuous with respect to Q, meaning that Q(A) = 0 implies P (A) = 0 for every A ∈ G. If P ≪ Q, then dP/dQ denotes the Radon– R dP Nikodym derivative: a G-measurable function satisfying P (A) = A dQ dQ for every A ∈ G. The KL divergence is   Z dP KL(P ∥Q) := dP log dQ Ω when P ≪ Q, and KL(P ∥Q) := ∞ otherwise. If ν is any measure on (Ω, G) dominating both P and Q, The total variation distance is Z 1 dP dQ dTV (P, Q) := sup |P (A) − Q(A)| = − dν. 2 Ω dν dν A∈G 14

If ν dominates both P and Q, we use the following convention for squared Hellinger distance: h2 (P, Q) :=

Z Ω

r

dP − dν

r

dQ dν

!2 dν.

This definition is independent of the choice of ν. Thus, if p = dP/dν and q = dQ/dν, then Z √ pq dν = 1 − h2 (P, Q)/2. We use the following lemma to summarize known properties of KL divergence of Bernoulli distributions. Lemma 3. There is a universal constant C > 0 such that, for every real numbers u, v satisfying |u|, |v| ≤ 1/4, then KL(Bern(1/2 + u)∥ Bern(1/2 + v)) ≤ C(u − v)2 . Moreover, for every κ ∈ (0, 1/2) there is Cκ > 0 such that, whenever p, q ∈ [κ, 1 − κ], then KL(Bern(p)∥ Bern(q)) ≤ Cκ (p − q)2 . If M ≥ 2 and p, q ∈ [3/(4M ), 5/(4M )], then KL(Bern(p)∥ Bern(q)) ≤ CM (p − q)2 . If M ≥ 2 and 1 − p, 1 − q ∈ [3/(4M ), 5/(4M )], then KL(Bern(p)∥ Bern(q)) ≤ CM (p − q)2 . The lower bounds below use standard testing reductions based on Assouad’s lemma and Pinsker’s inequality; see, for example, Yu [20] and Tsybakov [15] for background on these methods. We use the exact elementary forms below. Randomized estimators are allowed throughout; their private randomness is treated as an additional observation independent of the unknown parameter. Lemma 4. Let d ≥ 1, let θ be uniform on {−1, 1}d , and let Pθ be the law of the data under θ. Assume, for every coordinate r and every θ, if θ(r) is obtained by flipping only θr , then, 1 KL(Pθ ∥Pθ(r) ) ≤ 50 . Then, every estimator θb has expected Hamming error |{r : θbr ̸= θr }| at least 9d/20. The Assouad lemma gives an expected Hamming lower bound. The next elementary lemma converts such an expectation bound into a probability bound. Lemma 5. Let H be a random variable with 0 ≤ H ≤ d. If EH ≥ 9d/20, then Pr[H ≥ d/16] > 1/3. The preceding two lemmas imply the following probability-form version of Assouad’s method. Lemma 6. Let D ≥ 1. Let {Pσ : σ ∈ {−1, 1}D } be a family of distributions. For k ∈ [D], let σ ⊕k denote σ with only its k-th coordinate flipped. Assume KL(Pσ ∥Pσ⊕k ) ≤ 1/50 for every σ ∈ {−1, 1}D and k ∈ [D]. Then, for every estimator σ b it holds that Prσ,W (dH (b σ (W ), σ) ≥ D/16) ≥ 31/80, where σ is uniform on {−1, 1}D , W ∼ Pσ , and dH is Hamming distance. Roots and blockers. In the proofs below, we often specify a family of generators {gθ : θ ∈ Θ} for some set Θ. Here θ is only an index selecting one generator from the family. A root is a prompt r where the generator is allowed to depend on this index θ. The blocker of r is the prefix br such that r = br 1. By setting pgθ (br ) = 0 for every θ ∈ Θ, a trajectory that reaches br is forced to output 0, and therefore cannot accidentally enter the root r = br 1. If α : Θ → A is any map, saying that a quantity Bθ depends on θ only through α(θ) means that if α(θ) = α(θ′ ) then Bθ = Bθ′ for θ, θ′ ∈ Θ. When α is constant, this means that Bθ is independent of θ. The next lemma formalizes a useful property: under some conditions, the blockers prevent trajectories from entering a root unless they start at the root.

15

Lemma 7. Let M ≥ 2, let {gθ : θ ∈ Θ} be stochastic generators, for some set Θ. Let R be a finite set of roots. For every r ∈ R, let br be the blocker of r (satisfying r = br 1). Assume that the roots have the same length and are distinct, and that pgθ (br ) = 0 for every r ∈ R and every θ. Let α : Θ → A be any map. Assume also that the following three conditions hold. 1. If a prompt is not a root, not a strict prefix of a root, and not a strict descendant of a root, then, for every 1 ≤ t ≤ M , the value qge2e−t (x) depends on θ only through α(θ). θ 2. If a prompt is a strict prefix of a root, then its one-step probability pgθ (x) depends on θ only through α(θ). 3. For every r ∈ R and every nonempty suffix u, the M -step final-token probability qge2e−M (ru) θ depends on θ only through α(θ). Then, for every prompt x ∈ / R, the value qge2e−M (x) depends on θ only through α(θ). θ

4

Simultaneous exact-scale lower bound

We first fix constants used throughout this section. For odd L, define ϕL (θ) := Pr{Bin(L, 1/2 + θ) ≥ (L + 1)/2}. Since L is odd, ϕL (−θ) = 1−ϕL (θ) whenever 1/2±θ ∈ [0, 1]. Then ϕL (0) = 1/2, ϕL is differentiable at 0, and   L−1 ′ ϕL (0) = L 2−(L−1) . (L − 1)/2 This derivative tends to infinity with L. Choose universal constants a, α, β > 0 such that a2 < 1, α > 1, equivalently α2 > 1 for the zero-sample lower bound below, and β > 4, so that β 2 /16 > 1. Choose one fixed odd integer L large enough and then choose ε0 > 0 small enough so that, for (1) (β) every 0 < ε ≤ ε0 , there are numbers θε and θε satisfying ϕL (θε(1) ) = and in addition

1 √ + ε, 2

ϕL (θε(β) ) =

√ 1 + β ε, 2

√ √ c ε ≤ |θε(1) |, |θε(β) | ≤ a ε

for a universal constant c > 0. This follows from the inverse function theorem at 0, after fixing L, because ϕ′L (0) can be made arbitrarily large. Decrease ε0 , if necessary, so that all transition probabilities below lie in [0, 1], and also so that ε0 ≤ 1/32. Put M0 := L + 3. Lemma 8. There are universal constants c, C > 0 such that, for every integer N ≥ 1, every M ≥ M0 , and every 0 < ε ≤ ε0 , there is a finite stochastic generator class GN , with a distinguished fixed element g0 ∈ GN , such that N mGbase (ε) ≤ C/ε,

N ,M mGCoT (ε) ≤ CN/ε,

N ,M mGCoT (ε) ≥ cN/ε

Proof. The construction is as follows. Choose distinct binary strings u, v1 , . . . , vN , all of the same length, and set r0 := u1 and rj := vj 1 for every 1 ≤ j ≤ N . The strings u, v1 , . . . , vN are blockers for the roots r0 , r1 , . . . , rN . A generator is indexed by τ ∈ {−1, 1} and σ ∈ {−1, 1}N . Set pgτ,σ (u) = 0,

pgτ,σ (vj ) = 0 16

1 ≤ j ≤ N.

√ At the base root set pgτ,σ (r0 ) = 12 + α ε τ, and set pgτ,σ (r0 z) = 1/2 for every nonempty suffix z. For each j ∈ [N ], set 1 pgτ,σ (rj z) = + θε(β) σj 2 for every suffix z with 0 ≤ |z| < L. Set pgτ,σ (rj z) = 1/2 for L ≤ |z| < M − 1. For every suffix z with |z| = M − 1, set " L # X pgτ,σ (rj z) = 1 zℓ ≥ (L + 1)/2 . ℓ=1

For |z| ≥ M , set pgτ,σ (rj z) = 1/2. On all remaining states, set the transition probability to 1/2. Let GN := {gτ,σ : τ ∈ {−1, 1}, σ ∈ {−1, 1}N }. Let g0 be any fixed element of GN . Starting from rj , the first L generated bits are independent Bernoulli variables with mean (β) 1/2 + θε σj , and the M -th transition is their majority. The displayed value follows from the (β) definition of θε when σj = 1 and from ϕL (−θ) = 1 − ϕL (θ) when σj = −1. Therefore qge2e−M (rj ) = τ,σ

√ 1 + β ε σj . 2

By Lemma 7, applied to the root set {r0 , r1 , . . . , rN } with the same fixed value at every root, every non-root prompt has M -step value independent of (τ, σ). Indeed, the roots are blocked; strict-prefix transitions are fixed; outside rooted subtrees all transitions are fixed; and from any strict descendant rz, z ̸= ∅, of a root r ∈ {r0 , r1 , . . . , rN }, the final transition after M additional steps occurs at suffix length at least M , where the transition is fixed to 1/2. Also qge2e−M (r0 ) = 1/2, because after the τ,σ first transition from r0 all descendant transitions are 1/2. Thus the only parameter-dependent M -step values are at r1 , . . . , rN . We prove the base upper bound. For each τb ∈ {−1, 1}, use the one-step predictor that predicts √ 1/2 + α ε τb at r0 , predicts 1/2 at all weak states rj z with 0 ≤ |z| < L, predicts the displayed majority value at rj z with |z| = M − 1, predicts 0 on the blockers, and predicts the fixed transition probability elsewhere. For τb = τ , the only possible errors are at weak states, and each has squared (β) error at most (θε )2 ≤ a2 ε. Thus, under every one-step input distribution, one of these two predictors has squared loss at most a2 ε. Since a2 < 1, apply Lemma 1 with excess accuracy N (1 − a2 )ε to get mGbase (ε) ≤ C/ε. We prove the CoT upper bound. The learner predicts the fixed M -step value outside r1 , . . . , rN . For each j, it estimates σj from the trajectories whose prompt is rj . If Nj is the number of such trajectories, then, conditional on Nj , the learner observes LNj independent Bernoulli samples with (β) (β) mean 1/2 + θε σj . Since (θε )2 ≥ cε, Hoeffding’s inequality gives Pr[b σj ̸= σj | Nj ] ≤ exp(−cεNj ). √

The learner predicts 1/2+β ε σ bj at rj . Let S denote the training sample, and let qb be the learner’s output. Then, for every prompt distribution P ,  ES EX∼P

qb(X) − qge2e−M (X) τ,σ

2 

≤ Cε

N X

P (rj )E[exp(−cεNj )].

j=1

Since Nj ∼ Bin(n, P (rj )),

E[exp(−cεNj )] ≤ exp(−c′ εnP (rj )). 17

Therefore,  ES EX∼P

qb(X) − qge2e−M (X) τ,σ

2 

≤ Cε

N X

P (rj ) exp(−c′ εnP (rj )).

j=1

Using xe−λx ≤ 1/(eλ), with x = P (rj ) and λ = c′ εn, gives  2  CN e2e−M ≤ . ES EX∼P qb(X) − qgτ,σ (X) n Taking n = CN/ε, and increasing C, makes this expectation at most ε/3. Markov’s inequality N ,M gives squared loss at most ε with probability at least 2/3. Hence mGCoT (ε) ≤ CN/ε. We prove the CoT lower bound. Put the prompt distribution uniformly on r1 , . . . , rN , draw σ uniformly from {−1, 1}N , and fix τ . Flipping σj changes one full trajectory only when X = rj , an event of probability 1/N . Conditional on X = rj , the only changed conditional laws are the first L Bernoulli transitions. By the chain rule for KL and Lemma 3, one trajectory has adjacent KL at most Cε/N . Therefore n trajectories have adjacent KL at most Cnε/N . If n ≤ cN/ε, this is at most the constant required in Lemma 4. Lemmas 4 and 5 imply that, with probability larger than 1/3, every estimator makes at least N/16 sign errors after decreasing c, if necessary. Decode a regression estimate by setting σ bj = 1 iff qb(rj ) ≥ 1/2. Each wrong sign contributes at least β 2 ε to the squared loss at its root. Under the uniform prompt distribution, on the event of at least N/16 sign errors, the squared loss is at least β 2 ε/16. Since β 2 /16 > 1, this is larger than ε. Therefore the average failure probability over the random signs, the sample, and the learner randomness is greater than 1/3, so there exists at least one fixed sign vector for which the learner fails with probability greater than 1/3. Hence no learner with n ≤ cN/ε can satisfy the uniform N ,M PAC guarantee, and mGCoT (ε) ≥ cN/ε. The second block keeps the base and CoT problems small while making the e2e problem large. Lemma 9. There are universal constants c, C > 0 such that, for every B ≥ 1, every M ≥ M0 , and every 0 < ε ≤ ε0 , there is a finite stochastic generator class HB and a distinguished inactive generator h0 ∈ HB such that B mH base (ε) ≤ C/ε,

B ,M mH CoT (ε) ≤ C/ε,

B ,M mH (ε) > BM/ε e2e

Proof. The construction is as follows. Choose universal constants ρ0 , cη , Cd > 0 as follows. First choose ρ0 ∈ (0, 1/10) so that (1 − ρ0 )2 /2 > 1/3. Then choose cη > 0 so small that 2cη ≤ ρ0 . Finally choose Cd large enough for the estimates below, and also so that Cd ≥ 32. Define η := cη ε/(BM ) and n0 := ⌈BM/ε⌉. Choose an integer d satisfying d ≥ Cd εn0 /η and d ≥ Cd ε/η 2 . Choose distinct binary strings w0 , w1 , . . . , wd , all of the same length, and set x0 := w0 1,

xj := wj 1

1 ≤ j ≤ d.

The strings w0 , w1 , . . . , wd are blockers for the roots x0 , x1 , . . . , xd . For b ∈ {0, 1} and s ∈ {±1}d , define an active generator hb,s as follows. Set phb,s (wj ) = 0

0 ≤ j ≤ d,

phb,s (xj ) = 1

0 ≤ j ≤ d.

Thus every active root first emits the selector bit 1. For every root r and every suffix z with |z| = 1, set phb,s (rz) = b. Thus, one full trajectory from any active root reveals b to a CoT learner. For the anchor root x0 , set all nonterminal transitions after the deterministic b-transition to 1/2, except 18

that for every suffix z with |z| = M −1, set phb,s (x0 z) = b. For every suffix z below x0 with |z| ≥ M , set phb,s (x0 z) = 1/2. Then qhe2e−M (x0 ) = b. b,s For each hidden root xj , 1 ≤ j ≤ d, set phb,s (xj z) =

1 + θε(1) sj 2

for every suffix z with 2 ≤ |z| < L + 2. Set all other nonterminal transitions below xj to 1/2, except that for every suffix z with |z| = M − 1, set "L+2 # X phb,s (xj z) = 1 zℓ ≥ (L + 1)/2 . ℓ=3 (1)

For |z| ≥ M , set phb,s (xj z) = 1/2. By the definition of θε , qhe2e−M (xj ) = b,s

1 √ + ε sj . 2

On every remaining state, except the blockers, set the transition probability to 1/2. Define the inactive generator h0 by ph0 (xj ) = 0

0 ≤ j ≤ d,

ph0 (wj ) = 0

0 ≤ j ≤ d,

and ph0 (y) = 1/2 on every remaining state. Thus, for h0 , the selector transition at every root is inactive. Let HB := {h0 } ∪ {hb,s : b ∈ {0, 1}, s ∈ {±1}d }. We record the fixed non-root property. For every non-root prompt y ∈ / {x0 , x1 , . . . , xd }, the e2e−M (y) is the same for all h ∈ HB . This follows from Lemma 7, applied with the same value qh fixed value at every root. The roots are blocked. If a prompt is outside the rooted subtrees and is not a strict prefix of a root, all future transitions are fixed. Strict-prefix one-step transitions are fixed: they are 0 at blockers and 1/2 at other strict prefixes. Finally, from a strict descendant rz, z ̸= ∅, the final transition after M additional steps occurs at suffix length at least M , where every transition is fixed to 1/2. We prove the base upper bound. Use three one-step predictors: one exact predictor for h0 , and one active predictor for each b ∈ {0, 1}. The active b-predictor matches all active selector states, deterministic b-states, fixed states, blockers, and terminal majority states; at weak hidden-sign states it predicts 1/2. If the truth is hb,s , this predictor makes errors only at weak hidden-sign (1) states, each of squared size (θε )2 ≤ a2 ε. Thus, under every one-step input distribution, some predictor in this three-element class has squared loss at most a2 ε. Since a2 < 1, apply Lemma 1 B with excess accuracy (1 − a2 )ε to get mH base (ε) ≤ C/ε. We prove the CoT upper bound. Let R := {x0 , x1 , . . . , xd }. The learner uses n = C/ε trajectories. If it sees a trajectory with prompt in R and first token 1, it declares the block active, reads the deterministic second token b, predicts b at x0 , predicts 1/2 at each hidden root xj , and predicts the common fixed M -step value at every non-root prompt. If it never sees an active selector, it predicts the inactive values of h0 . If the truth is h0 , the active selector never appears and the learner is exact. If the truth is hb,s , let p := P (R). If an active selector is observed, the only possible loss is at hidden roots, where the learner predicts 1/2, and this loss is d X ε P (xj ) ≤ ε. j=1

19

If no active selector is observed, the learner predicts the inactive values of h0 . Since all non-root M -step values are common across HB , the learner may be wrong only on roots, so the loss is at most p. If p ≤ ε, this is at most ε. Let Esel be the event that no sample contains an active selector. If p > ε, then Pr[Esel ] = (1 − p)n ≤ exp(−np) ≤ exp(−C). B ,M Increasing C makes this probability at most 1/3. Hence mH CoT (ε) ≤ C/ε. We prove the e2e lower bound. It is enough to condition on an arbitrary value of the learner’s private random seed, because the argument below is uniform in that value. Let P be supported on x0 , x1 , . . . , xd , with P (x0 ) = η, P (xj ) = (1 − η)/d 1 ≤ j ≤ d.

Draw b uniformly from {0, 1} and s uniformly from {±1}d . In the e2e model, a sample from x0 is Bern(b), and a sample from xj is   1 √ Bern + ε sj . 2 Fix n ≤ n0 . Let E be the event that no sample has prompt x0 . Since n0 ≤ 2BM/ε and η = cη ε/(BM ), Pr(E) = (1 − η)n ≥ 1 − nη ≥ 1 − ρ0 . Condition on E, on the sampled hidden indices, and on the observed hidden tokens. Let U ⊆ [d] be the set of hidden indices that were not sampled. Since n ≤ n0 and d ≥ Cd εn0 /η, |U | n η ≥1− ≥1− . d d Cd ε For j ∈ U , the sign sj is still an independent Rademacher variable. If qj ∈ [0, 1] is the learner’s fixed prediction at xj under the conditioning, then "  2 #   1 √ 1 2 Esj qj − = qj − + ε sj + ε ≥ ε. 2 2 Thus the conditional expected hidden loss over unsampled coordinates is at least   η 1−η |U |ε ≥ (1 − η) 1 − ε. d Cd ε Expanding the right-hand side gives 

η (1 − η) 1 − Cd ε

 ε ≥ ε − ηε −

η . Cd

Since 0 < ε ≤ ε0 ≤ 1/32 and Cd ≥ 32, the last display is at least ε − η/16. For each unsampled coordinate j, define its hidden-loss contribution and its centered version by 1−η Lj := d

2   1 √ qj − + ε sj , 2

∆j := Lj − Esj Lj .

For fixed qj ∈ [0, 1], |Lj (+1) − Lj (−1)| =

√ √ 1−η 2(1 − η) ε 4|qj − 1/2| ε ≤ . d d

20

Therefore √ |∆j | ≤ C(1 − η) ε/d,

X

Var(∆j ) ≤

j∈U

X

E∆2j ≤ C|U |ε/d2 ≤ Cε/d.

j∈U

Let Luns denote the contribution to the loss from unsampled hidden roots, and let Dsamp denote the sampled hidden data. Since d ≥ Cd ε/η 2 , increasing Cd gives Pr [Luns < ε − η/8 | E, Dsamp ] ≤ ρ0 by Chebyshev’s inequality. On E, the data are independent of b. Hence, conditional on E and the hidden data, the learner’s prediction q0 ∈ [0, 1] at x0 is fixed before the uniform bit b is drawn. For every q0 ∈ [0, 1], with probability at least 1/2 over b, (q0 − b)2 ≥ 1/4. On this event the anchor contribution to squared loss is at least η/4. Therefore, with probability at least (1 − ρ0 )2 /2 > 1/3, the hidden loss is at least ε − η/8 and the anchor loss is at least η/4, so the total loss is larger than ε. This probability is averaged over the random parameter (b, s), the sample, and the learner randomness. Hence there exists at least one fixed parameter value for which the learner fails with probability greater than 1/3, so no e2e learner with n ≤ n0 samples can satisfy the uniform PAC guarantee. Since n0 = ⌈BM/ε⌉, this HB ,M proves me2e (ε) > BM/ε. We now combine the two blocks into a single class. Theorem 4.1. There is a universal integer M0 and a universal constant ε0 > 0 such that the following holds. For every A ≥ 1, every M ≥ M0 , and every 0 < ε ≤ ε0 , there is a finite binarytoken stochastic autoregressive class F such that 0 < mF base (ε) < ∞ and ,M mF M CoT (ε) >A , F ε mbase (ε)

,M mF e2e (ε) ,M mF CoT (ε)

>A

M . ε

Proof. Choose a sufficiently large universal constant C∗ . Set N := ⌈C∗ AM/ε⌉ , T := N/ε, and B := ⌈C∗ AT ⌉. Construct GN and HB on disjoint rooted subtrees. Let SG be the union of all blockers and all depth-M rooted subtrees used in the construction of GN , and define SH similarly for HB . Choose the underlying binary strings so that SG ∩ SH = ∅. Let g0 ∈ GN and h0 ∈ HB be their distinguished elements. For g ∈ GN and h ∈ HB , let g ⊕ h be the generator that agrees with g on SG , agrees with h on SH , and uses the fixed default transition probability 1/2 on all remaining states. Define F := {g ⊕ h0 : g ∈ GN } ∪ {g0 ⊕ h : h ∈ HB }. This is a union of alternatives. The one-step upper bounds for GN and HB give at most five improper one-step predictors for F with approximation error at most a2 ε: the two predictors from the GN block combined with the fixed one-step predictor for h0 , and the three predictors from the HB block combined with the fixed one-step predictor for g0 . Since a2 < 1, applying Lemma 1 with excess accuracy (1 − a2 )ε gives mF Also mF base (ε) ≤ C/ε. base (ε)√> 0: in the GN -alternative, two generators have one-step √ probabilities 1/2 + α ε and 1/2 − α ε at r0 . Since α > 1, no zero-sample learner can be within squared error ε of both with probability 2/3. We prove the CoT upper bound. Use n = CN/ε samples. The learner first checks whether some trajectory in the HB -root set has first token 1. If so, it declares the HB -alternative active, 21

reads the deterministic second token b, predicts g0 on the GN -subtree, predicts b at the anchor x0 , predicts 1/2 at each hidden root xj , and predicts the common fixed M -step value at every non-root prompt in the HB -subtree. If no active HB -selector is observed, it runs the explicit GN estimator from Lemma 8 on the original sample and predicts h0 on the HB -subtree. We record the direct risk bound for the GN estimator under the original prompt distribution. Let Pj := P (rj ), and let Nj be the number of sampled trajectories with prompt rj . Conditional on (β) Nj , the learner observes LNj independent Bernoulli samples with mean 1/2 + θε σj . Hence Pr[b σj ̸= σj | Nj ] ≤ exp(−cεNj ). Since Nj ∼ Bin(n, Pj ),

E[exp(−cεNj )] ≤ exp(−c′ εnPj ).

If LG denotes the squared-loss contribution from the GN -roots, then ELG ≤ Cε

N X

Pj exp(−c′ εnPj ) ≤ CN/n,

j=1

where the last inequality uses xe−λx ≤ 1/(eλ). Increasing the universal constant in n = CN/ε, Markov’s inequality gives Pr[LG > ε/2] ≤ 1/3. If the truth is g ⊕ h0 , then an active HB -selector is never observed. The learner uses the GN estimator, the HB -part is predicted exactly, and the total loss is LG . Thus the learner succeeds with probability at least 2/3. If the truth is g0 ⊕ hb,s , let p be the prompt mass of the HB -root set. If p ≤ ε/2, then on the event LG ≤ ε/2, the no-selector branch has total loss at most ε: the GN -root loss is at most ε/2, the possible HB -root loss is at most p ≤ ε/2, and all non-root HB -values are common and predicted correctly. If an active selector is observed instead, the active branch has zero loss on the GN -subtree, zero loss at the anchor, zero loss on non-root prompts, and hidden-root loss at most ε

d X

P (xj ) ≤ ε.

j=1

Therefore, when p ≤ ε/2, the learner succeeds with probability at least 2/3. It remains to consider p > ε/2. Under hb,s , every prompt in the HB -root set produces first token 1 deterministically, so an active selector is missed only if no training prompt lies in that root set. Let E ′ be the event that no active HB selector is observed. Hence,   Pr E ′ ≤ (1 − p)n ≤ exp(−np) ≤ exp(−CN/2). Since N ≥ 1, increasing C makes this probability at most 1/3. On the complementary event, the active branch has loss at most ε, as shown above. Therefore the learner succeeds with probability ,M at least 2/3 also in this case. Hence mF CoT (ε) ≤ CN/ε. For the CoT lower bound, restrict to the subclass {g ⊕ h0 : g ∈ GN } and to prompt distributions ,M supported on the GN -subtree. Lemma 8 gives mF CoT (ε) ≥ cN/ε. For the e2e lower bound, restrict to the subclass {g0 ⊕ h : h ∈ HB } and to prompt distributions supported on the HB -subtree. ,M Lemma 9 gives mF e2e (ε) > BM/ε. By the choice of N and by taking C∗ large enough, ,M mF cN/ε M CoT (ε) ≥ >A . F C/ε ε mbase (ε)

22

By the choice of B and by taking C∗ large enough, ,M mF e2e (ε) ,M mF CoT (ε)

>

BM/ε BM M = >A . CN/ε CN ε

The theorem follows.

5

Base-to-CoT comparison

This section proves the sharp comparison from one-step learning to chain-of-thought learning. The learners are improper under the regression convention in Section 1.2: they may output arbitrary predictors with values in [0, 1]. Theorem 5.1 (Base-to-CoT: upper bound, tightness, and scale optimality). The following statements hold. 1. For every stochastic generator class F, every M ≥ 1, every 0 < ε < 1, and every 0 < δ < 1,  ε  ,M F mF (ε, δ) ≤ m , δ . base CoT M2 2. There are universal constants κ, c, C > 0 such that for every integer L ≥ 1, every M ≥ 2, and all sufficiently small ε > 0, there is a finite binary-token stochastic generator class F satisfying c

LM 2 LM 2 ,M (ε) ≤ C ≤ mF , CoT ε ε

c

 ε  LM 2 LM 2 κ ≤ mF ≤ C . base ε M2 ε

3. Fix 0 < β < 1. There is a universal constant c0 > 0 such that for every K ≥ 1, every M ≥ 2, and all sufficiently small  1−β  ε > 0, there is a finite binary-token stochastic generator class F ,M ε K F such that mbase M 2 = 0 but mF CoT (ε) ≥ c0 ε . Proof. We prove the three statements in order. Upper bound. Fix a prompt distribution P and a target generator g⋆ ∈ F. Given one full trajectory (X, Z1 , . . . , ZM ), choose T uniformly from {1, . . . , M }, independently of the trajectory, and set S = XZ1 · · · ZT −1 and Y = ZT . Conditional on S, the bit Y has law Bern(pg⋆ (S)). Across independent trajectories, the pairs (S, Y ) are i.i.d. from some distribution on states. Hence a base learner can be applied to these pairs. Let pb be the output of a base learner at accuracy ε/M 2 . If necessary, replace pb by its clipping to [0, 1]; this cannot increase squared loss against a target in [0, 1]. Define gb by gb(s)(1) = pb(s), and set qb = qgbe2e−M . We show that if pb has one-step squared loss at most ε/M 2 , then qb has final-token squared loss at most ε. Fix a prompt x. Couple the g⋆ -trajectory and the gb-trajectory step by step. As long as the two trajectories are at the same state St , the probability that they split at step t is at most |pg⋆ (St ) − pb(St )|. Therefore |qge2e−M (x) − qgbe2e−M (x)| ≤ E ⋆

"M X t=1

23

# |pg⋆ (St ) − pb(St )| X = x .

By Jensen’s inequality and Cauchy–Schwarz, "M # X |qge2e−M (x) − qgbe2e−M (x)|2 ≤ M E (pg⋆ (St ) − pb(St ))2 X = x . ⋆ t=1

Averaging over X ∼ P gives h i   e2e−M 2 EX∼P (qge2e−M (X) − q (X)) ≤ M 2 ES (pg⋆ (S) − pb(S))2 , ⋆ g b where S is the state obtained by choosing a random time from a random g⋆ -trajectory. Thus onestep squared loss at most ε/M 2 implies final-token squared loss at most ε, with the same confidence. This proves the first statement. Tightness. Fix an integer L ≥ 1 and M ≥ 2. Let K = LM 2 . We choose two prefix-disjoint root families u1 , . . . , uK and v1 , . . . , vL , and we block all strict prefixes so that no root can be reached from outside its own block. A generator is indexed by two sign vectors σ ∈ {−1, 1}K and τ ∈ {−1, 1}L . Choose universal constants a, κ, b > 0 in the following order. First set p0 := 1/M . Then choose a large enough for the CoT loss lower bound below. Then choose κ > 2a2 . Finally choose b large √ √ enough for the base loss lower bound below. Set ∆ = a ε/M and θ = b ε/M . For all sufficiently small ε, p0 ± ∆ ∈ [3/(4M ), 5/(4M )] and 1/2 ± θ ∈ [0, 1]. On the first block, starting from root uk , as long as all previous generated bits are 0, the next bit is 1 with probability p0 + σk ∆. Once a 1 has appeared, all later bits are 1 deterministically. Hence qge2e−M (uk ) = 1 − (1 − p0 − σk ∆)M . σ,τ The derivative of p 7→ 1 − (1 − p)M is M (1 − p)M −1 . Since p0 = 1/M and ∆ = o(1/M ), there is a universal constant c1 > 0 such that this derivative is at least c1 M on [p0 − ∆, p0 + ∆]. By the √ mean-value theorem, the two possible values of qge2e−M (uk ) are separated by at least 2c1 a ε. σ,τ On the second block, set pgσ,τ (vℓ ) = 1/2 + τℓ θ. After the first generated bit from vℓ , all later generated bits are 0 deterministically. Thus qge2e−M (vℓ ) = 0 for every ℓ and every sign vector. All σ,τ states outside the two blocks are fixed independently of σ and τ . We first prove the lower bound for CoT. Put the prompt distribution uniformly on u1 , . . . , uK . The signs τ are irrelevant under this distribution. Changing one coordinate σk changes the trajectory law only when the prompt is uk , which has probability 1/K. Conditional on X = uk , the two trajectory laws differ only through transitions with probabilities p0 + ∆ and p0 − ∆ before the first success. By the chain rule for KL divergence and Lemma 3, each changed transition contributes at most C1 M ∆2 to the KL divergence, and there are at most M such transitions. Hence this condi√ tional KL divergence is at most C1 M 2 ∆2 . Since ∆ = a ε/M , this is at most C2 ε. Therefore the one-sample adjacent KL divergence is at most C2 ε/K. For n < cK/ε, the n-sample adjacent KL is bounded by the constant needed in Lemma 4. Hence every estimator of σ1 , . . . , σK has Hamming error at least a constant fraction of K with probability greater than 1/3, by Lemma 4 and Lemma 5. Given any final-token predictor qb, estimate σk by thresholding qb(uk ) halfway between the two possible values of qge2e−M (uk ). If this estimated sign is wrong, then the squared error at uk is at σ,τ least c3 a2 ε for a universal constant c3 > 0. Since the prompt distribution is uniform on the K roots, a constant fraction of wrong signs gives squared loss at least a constant multiple of a2 ε. By ,M 2 the choice of a, this is larger than ε. Therefore mF CoT (ε) ≥ cK/ε = cLM /ε.

24

For the upper bound on CoT, the induced final-token class depends only on σ1 , . . . , σK , and therefore has at most 2K distinct functions. Applying Lemma 1 to this finite final-token class gives ,M 2 mF CoT (ε) ≤ CK/ε = CLM /ε. We now prove the base lower bound at scale κε/M 2 . Put the state distribution uniformly on v1 , . . . , vL . Under this distribution, the base problem is exactly the problem of learning the L signs τ1 , . . . , τL from Bernoulli observations with means 1/2 + τℓ θ. Changing one coordinate changes √ the one-sample KL divergence by at most C4 θ2 /L, by Lemma 3. Since θ = b ε/M , this is at most C5 ε/(LM 2 ). For n < cLM 2 /ε, the n-sample adjacent KL is bounded by the constant needed in Lemma 4. Thus every estimator of τ1 , . . . , τL makes a constant fraction of sign mistakes with probability greater than 1/3. Given any base predictor pb, estimate τℓ by thresholding pb(vℓ ) at 1/2. If this estimated sign is wrong, then |b p(vℓ ) − pgσ,τ (vℓ )| ≥ θ, so the squared error at vℓ is at least θ2 . Under the uniform distribution on the vℓ ’s, a constant fraction of wrong signs gives base squared loss at least a constant 2 2 multiple of b2 ε/M 2 . By the choice of b, this is larger than κε/M 2 . Hence mF base (κε/M ) ≥ cLM /ε. It remains to prove the base upper bound. Fix an arbitrary state distribution. Consider the finite class of one-step predictors that use the midpoint value p0 on every sign-dependent state in the first block, use the correct fixed values outside the two blocks, and choose arbitrary signs on the second block. This finite class has size at most 2L . For the true generator gσ,τ , the member with the correct τ has squared error at most ∆2 = a2 ε/M 2 at every sign-dependent state in the first block and zero error elsewhere. Since κ > 2a2 , this approximation error is at most κε/(2M 2 ). Applying Lemma 1 to this finite class, with target excess risk κε/(2M 2 ) and confidence 2/3, gives a base learner using at most CLM 2 /ε samples and achieving total base squared loss at most 2 2 κε/M 2 . Therefore mF base (κε/M ) ≤ CLM /ε. This proves the tightness statement. Scale optimality. Fix 0 < β < 1. Choose roots r1 , . . . , rK with distinct blockers b1 , . . . , bK , √ where rk = bk 1. A generator is indexed by σ ∈ {−1, 1}K . Let ∆ = a ε/M and p0 = 1/M , where a is the universal constant used above. For all sufficiently small ε, p0 ± ∆ ∈ [3/(4M ), 5/(4M )]. Starting from root rk , as long as all previous generated bits are 0, the next bit is 1 with probability p0 + σk ∆. Once a 1 has appeared, all later bits are 1 deterministically. All states outside these root blocks are fixed independently of σ. As above, qge2e−M (rk ) = 1 − (1 − p0 − σk ∆)M , σ √ (rk ) are separated by at least a universal constant times a ε. and the two possible values of qge2e−M σ At the one-step level, every sign-dependent probability differs from its midpoint by at most ∆. The zero-sample base predictor that uses these midpoint values has pointwise squared error at most ∆2 = a2 ε/M 2 . Since a2 ε/M 2 < ε1−β /M 2 for all sufficiently small ε, the base problem at scale ε1−β /M 2 has sample complexity zero. For the CoT lower bound, put the prompt distribution uniformly on r1 , . . . , rK . The same KL calculation and Assouad argument used in the first block of the tightness construction imply that fewer than cK/ε trajectories leave a constant fraction of signs wrong with probability greater than 1/3. Thresholding any final-token predictor at the midpoint of the two possible values converts prediction into sign estimation. A wrong sign causes squared error of order a2 ε at its root. By the choice of a, a constant fraction of wrong signs forces final-token squared loss larger than ε. ,M Therefore mF CoT (ε) ≥ c0 K/ε.

25

6

Upper bound on e2e via CoT

This section proves a universal upper comparison between CoT and e2e sample complexities and then gives a shifted-scale construction showing that the comparison is tight up to logarithmic factors. We use the following decoding form of Fano’s inequality. For random variables U, W , write I(U ; W ) for their mutual information, defined by I(U ; W ) := KL(L(U, W ) ∥ L(U ) ⊗ L(W )), where L(U ) and L(W ) denote the marginal laws. For discrete W , conditional Shannon entropy is H(W | U ) := E[− log Pr(W | U )]. Lemma 10. See Yu [20] and Tsybakov [15]. Let V be uniform on [L], let Y be any observation, and let Vb (Y ) ∈ [L]. If the decoder is randomized, include its private random seed in Y . If Pr[Vb = V ] ≥ 2/3, then I(V ; Y ) ≥ 23 log L − log 2. Theorem 6.1. There are universal constants c, C > 0 such that, for every stochastic generator class F, every M ≥ 2, every 0 < ε < 1, and every 0 < δ < 1/2,   ,M M 1 ∨ mF (cε, 1/3) logC (C/ε) + log(1/δ) CoT ,M (ε, δ) ≤ C mF . e2e ε Proof. All universal constants below are fixed as they are introduced. The argument is only needed in the nontrivial case in which the CoT-sample complexity term ultimately appearing on the righthand side is finite; if that term is infinite, the desired inequality is immediate. Thus, whenever a ,M displayed bound below contains mF CoT (·), we may assume that the particular sample-complexity term in that bound is finite. We first prove a packing consequence of CoT-learnability. Claim 1. There are universal constants c0 , C0 > 0 such that the following holds. Let 0 < r < 1, let P be any probability measure on prompts, and let q1 , . . . , qL ∈ F e2e−M satisfy EX∼P [(qi (X) − qj (X))2 ] > r for every i ̸= j. Then   ,M (c r) . log L ≤ C0 M 1 ∨ mF 0 CoT ,M Proof. For each i ∈ [L], choose gi ∈ F such that qge2e−M = qi . Let m := mF CoT (c0 r). If m = ∞, the i displayed bound is immediate. Hence assume m < ∞. Let V be uniform on [L]. Conditional on V = i, draw m full trajectories from gi , with prompts distributed according to P . Write X1:m for the m sampled prompts and Z1:m,1:M for the corresponding m × M token array. If the CoT-learner is randomized, let U be its private random seed; if it is deterministic, let U be constant. In both cases U is independent of V and of the sampled trajectories. ,M Choose c0 > 0 small enough. By the definition of mF b CoT (c0 r), the CoT-learner outputs q 2 satisfying EX∼P [(b q (X) − qV (X)) ] ≤ c0 r with probability at least 2/3. On this event, qV is the unique packing element within squared L2 (P )-distance c0 r of qb. Indeed, for every j ̸= V ,

(qV (X) − qj (X))2 ≤ 2(b q (X) − qj (X))2 + 2(b q (X) − qV (X))2 . Taking expectation and rearranging gives 1 E[(b q (X) − qj (X)) ] ≥ E[(qV (X) − qj (X))2 ] − E[(b q (X) − qV (X))2 ] > 2 2

26



 1 − c0 r. 2

Since c0 is chosen small enough, the last quantity is larger than c0 r. Thus V can be decoded from (X1:m , Z1:m,1:M , U ) with success probability at least 2/3: run the CoT-learner and choose the unique packing element within squared L2 (P )-distance c0 r of its output. The hypotheses of Lemma 10 hold because V is uniform on [L], and the decoder is a function of the displayed observation, including the private seed U . This decoder is only an information-theoretic device; it may use the packing elements and the population L2 (P )-distances. By Lemma 10, 2 log L − log 2 ≤ I(V ; X1:m , Z1:m,1:M , U ). 3 Since U is independent of V and of the trajectory data, I(V ; X1:m , Z1:m,1:M , U ) = I(V ; X1:m , Z1:m,1:M ). The prompts are drawn from P independently of V , so I(V ; X1:m , Z1:m,1:M ) = I(V ; Z1:m,1:M | X1:m ). Conditional on the prompts, the token array contains M m binary random variables. Therefore I(V ; Z1:m,1:M | X1:m ) ≤ H(Z1:m,1:M | X1:m ) ≤ M m log 2. The first inequality is the general bound I(A; B | C) ≤ H(B | C), and the second uses that a binary array of size M m has entropy at most M m log 2. Combining the preceding displays gives log L ≤ C0 M (1 ∨ m), after increasing the universal constant C0 . This proves the claim. We next convert the packing bound into a fat-shattering bound. Claim 2. There are universal constants c1 , c2 , C1 > 0 such that for every class F, every M ≥ 2, and every 0 < ε < 1,   √ ,M (c ε) . fatF e2e−M (c1 ε) ≤ C1 M 1 ∨ mF 2 CoT √ Proof. We first prove that every finite set fat-shattered by F e2e−M at scale c1 ε has the claimed √ size. Let x1 , . . . , xd be c1 ε-fat-shattered by F e2e−M . If d = 0, there is nothing to prove. There are thresholds r1 , . . . , rd such that for every B ⊆ [d], there is qB ∈ F e2e−M satisfying √ √ i ∈ B ⇒ qB (xi ) ≥ ri + c1 ε, i∈ / B ⇒ qB (xi ) ≤ ri − c1 ε. By the classical Gilbert packing bound [8], there is a set B ⊆ 2[d] with |B| ≥ exp(cd) and |B△B ′ | ≥ cd for all distinct B, B ′ ∈ B, where c > 0 is universal. This follows by the greedy algorithm: a Hamming ball with Hamming distance at most cd has size at most exp(Cc log(1/c)d), and choosing c > 0 sufficiently small makes this at most exp((log 2)d/2). Choose c1 > 0 small enough that cc21 < 1. Since 0 < ε < 1, this ensures that the packing scale used below is in (0, 1), as required by Claim 1. Let P be the uniform distribution on x1 , . . . , xd . If √ B, B ′ ∈ B are distinct, then for every i ∈ B△B ′ , |qB (xi ) − qB ′ (xi )| ≥ 2c1 ε. Therefore EX∼P [(qB (X) − qB ′ (X))2 ] ≥

27

|B△B ′ | · 4c21 ε ≥ cc21 ε. d

Thus {qB : B ∈ B} is an L2 (P )-packing at squared scale cc21 ε. Applying Claim 1 with r = cc21 ε gives   ,M 2 log |B| ≤ C0 M 1 ∨ mF CoT (c0 cc1 ε) . ,M Put c2 := c0 cc21 . If mF CoT (c2 ε) = ∞, the claim is immediate. Otherwise, using log |B| ≥ cd, we obtain   ,M d ≤ C1 M 1 ∨ mF (c ε) , 2 CoT

where C1 is universal. √ This holds for every finite c1 ε-fat-shattered set. Since the right-hand side is finite in the √ remaining case, an infinite fatF e2e−M (c1 ε) would give arbitrarily large finite shattered sets with √ sizes bounded by the same finite quantity, a contradiction. Thus fatF e2e−M (c1 ε) is finite and satisfies the same bound. This proves the claim. Now apply Lemma 2 to the class F e2e−M . In the e2e model, the observed final token satisfies E[ZM | X = x] = qge2e−M (x), so this is a well-specified bounded squared-loss regression problem ⋆ with target in F e2e−M . Therefore √ fatF e2e−M (c ε) logC (C/ε) + log(1/δ) F ,M . me2e (ε, δ) ≤ C ε Choose c1 ≤ c, where c is the constant in Lemma 2. By monotonicity of fat-shattering in the scale, √ √ fatF e2e−M (c ε) ≤ fatF e2e−M (c1 ε). Claim 2 gives

  √ ,M (c ε) . fatF e2e−M (c ε) ≤ C1 M 1 ∨ mF 2 CoT

Substituting this into the regression bound gives   ,M M 1 ∨ mF (c ε) logC (C/ε) + log(1/δ) 2 CoT F ,M me2e (ε, δ) ≤ C . ε Renaming c2 as c, and increasing C if necessary, proves the first display. Taking δ = 1/3 and absorbing the constant log 3 proves the constant-confidence display.

6.1

Tightness of the shifted-scale comparison

We next show that the comparison is tight at the shifted scale. Theorem 6.2. There are universal constants ρ, c, C > 0, with ρ < 1, and ε0 > 0 such that the following holds. For every N ≥ 1, every M ≥ 2, and every 0 < ε ≤ ε0 , there is a finite binary-token stochastic autoregressive class F such that ,M cN ≤ mF CoT (ρε) ≤ CN

and c

NM NM ,M ≤ mF . e2e (ε) ≤ C ε ε

28

Proof. We first record the consequence of Lemmas 4 and 5 used below. There is a universal constant aHam > 0 such that the following holds. If a hypercube family has D signs and every adjacent pair has KL divergence at most 1/50, then every estimator of the signs has Hamming error at least aHam D with probability greater than 1/3. Fix a universal number γ ∈ (0, 1/2). Choose a universal number b > 0 large enough so that aHam b2 > 1. Fix a universal number ρ ∈ (0, 1) such that ρ < aHam b2 . Then choose ε0 > 0 small √ √ enough so that, for every 0 < ε ≤ ε0 , b ε ≤ 1/4 and b ε/(2γ) ≤ 1/2. Since the construction uses √ one hidden sign for each nonfinal transition, write d := M − 1 and put ηε := b ε/(2γ). Then d ≥ 1, ηε ≤ 1/2, and all transition probabilities defined below belong to [0, 1]. The construction is as follows. Choose distinct binary strings wj,i , for j ∈ [N ] and i ∈ [d], all of the same length. Set xj,i := wj,i 1. The strings wj,i are blocking states and the strings xj,i are roots. All roots have the same length and are distinct, so their rooted descendant subtrees are pairwise disjoint. A generator is indexed by σ ∈ {−1, 1}N ×d . Define gσ as follows. First set pgσ (wj,i ) = 0 for every j ∈ [N ] and i ∈ [d]. For every root xj,i and every suffix z with 0 ≤ |z| ≤ d − 1, set pgσ (xj,i z) =

1 + γσj,|z|+1 . 2

For every root xj,i and every suffix z with |z| = d, set pgσ (xj,i z) =

1 + ηε (2zi − 1). 2

On every remaining state, set pgσ (s) = 1/2. Let F := {gσ : σ ∈ {−1, 1}N ×d }. We first compute the M -step end-to-end values. √ Claim 3. For every j ∈ [N ] and i ∈ [d], qge2e−M (xj,i ) = 1/2 + b ε σj,i . For every prompt outside σ the roots xj,i , the value qge2e−M (x) is independent of σ. σ Proof. Fix j ∈ [N ] and i ∈ [d]. Starting from xj,i , for each t ∈ [d], the t-th generated token satisfies Zt ∼ Bern(1/2 + γσj,t ). Indeed, before time t, the current suffix has length t − 1, and the transition rule at suffix length t − 1 uses the sign σj,t . At time M = d + 1, the current suffix has length d. Therefore 1 Pr(ZM = 1 | Z1 , . . . , Zd ) = + ηε (2Zi − 1). 2 Taking expectation gives   1 1 e2e−M qg σ (xj,i ) = E + ηε (2Zi − 1) = + ηε (2EZi − 1). 2 2 Since EZi = 1/2 + γσj,i , this gives qge2e−M (xj,i ) = σ

√ 1 1 + ηε · 2γσj,i = + b ε σj,i , 2 2

by the definition of ηε . It remains to prove the non-root statement. We apply Lemma 7 to the roots xj,i , with blockers wj,i , and with no retained parameter. The strict-prefix transitions are fixed: the blocker wj,i has transition probability 0, and every other strict prefix has transition probability 1/2. If a prompt is not a root, not a strict prefix of a root, and not a strict descendant of a root, then it cannot enter any root by appending future tokens, because entering a root by appending tokens would require 29

the current prompt to be a strict prefix of that root. Hence all transitions seen during the next M steps are fixed, and every t-step value with t ≤ M is independent of σ. Now consider a strict descendant xj,i u, where u ̸= ∅. If |u| ≤ d, then the special transition at suffix length d occurs before the M -th generated token, because the process starts with a nonempty suffix and M = d + 1. After that special transition, every later transition is fixed to 1/2. Thus the M -th generated token has probability 1/2. If |u| > d, then all transitions are fixed to 1/2 from the start. Therefore every strict descendant of a root has parameter-independent M -step value. Lemma 7 gives the claim for every non-root prompt. We next prove the CoT upper bound. ,M Claim 4. There is a universal constant C > 0 such that mF CoT (ρε) ≤ CN .

Proof. Let P be any prompt distribution and let gσ ∈ F be the true generator. For j ∈ [N ], write Rj := {xj,i : i ∈ [d]}. The learner does the following. On every non-root prompt, it outputs the fixed value from Claim 3. For each j, it collects all training trajectories whose prompt lies in Rj . Let Nj be the number of such trajectories. From each such trajectory, the learner observes, for every t ∈ [d], one Bernoulli sample with mean 1/2 + γσj,t . These observations are independent across training trajectories. Therefore, for every t ∈ [d], the learner estimates σj,t by majority vote over √ these Nj observations, and guesses arbitrarily if Nj = 0. It then outputs qb(xj,i ) = 1/2 + b ε σ bj,i on every root xj,i . By Hoeffding’s inequality, there is a universal constant κ > 0, depending only on γ, such that Pr(b σj,i ̸= σj,i | Nj ) ≤ exp(−κNj ) for every j and i. Since Nj ∼ Bin(n, P (Rj )), E[exp(−κNj )] = (1 − P (Rj ) + P (Rj )e−κ )n ≤ exp(−κ′ nP (Rj )) for a universal constant κ′ > 0. The last inequality follows from 1 − u ≤ e−u , with u = P (Rj )(1 − e−κ ). The squared error is zero on non-root prompts. On a root xj,i , a wrong sign gives squared error √ 2 (2b ε) , and a correct sign gives squared error 0. Therefore the expected risk is at most 4b2 ε

N X d X

P (xj,i ) exp(−κ′ nP (Rj )) = 4b2 ε

j=1 i=1

N X

P (Rj ) exp(−κ′ nP (Rj )).

j=1

′

For every u ≥ 0, ue−κ nu ≤ C0 /n, where C0 is universal. Hence E[risk] ≤ C1 b2 εN/n. Choose n = C2 N , with C2 universal and large enough, so that the last display is at most ρε/3. Markov’s inequality gives risk at most ρε with probability at least 2/3. This proves the claim. We now prove the matching CoT lower bound. ,M Claim 5. There is a universal constant c > 0 such that mF CoT (ρε) ≥ cN .

Proof. Let P be the uniform distribution on x1,1 , . . . , xN,1 . Draw the signs σ1,1 , . . . , σN,1 independently and uniformly from {−1, 1}, and fix all other signs. Consider two parameters that differ only in the sign σj,1 . One full trajectory has different law only when X = xj,1 , an event of probability 1/N . Conditional on this event, the only conditional transition that depends on the changed sign is the first generated bit, whose law changes between Bern(1/2 + γ) and Bern(1/2 − γ). All later conditional laws are identical once the generated 30

prefix is fixed. This includes the last transition, which may depend on the realized first bit but is the same function of the realized prefix under both parameters. Therefore, by the chain rule for KL divergence, one trajectory has adjacent KL at most C0 /N , where C0 is universal. Hence n trajectories have adjacent KL at most C0 n/N . If n ≤ c0 N , with c0 > 0 universal and small enough, the adjacent KL is at most 1/50 for every edge. By the Assouad consequence stated at the beginning of the proof, every estimator of the signs σ1,1 , . . . , σN,1 has Hamming error at least aHam N with probability greater than 1/3. Given any regression estimate qb, decode σ bj,1 = 1 iff qb(xj,1 ) ≥ 1/2. If σ bj,1 ̸= σj,1 , then Claim 3 implies
2 qb(xj,1 ) − qge2e−M (xj,1 ) ≥ b2 ε. σ Thus, on the event that the Hamming error is at least aHam N , the squared-loss risk under P is at least aHam b2 ε. Since ρ < aHam b2 , the average failure probability over the random signs, the sample, and the learner randomness is greater than 1/3. Therefore there exists at least one fixed value of the signs for which the learner fails with probability greater than 1/3. Hence no learner using n ≤ c0 N samples can satisfy the uniform PAC guarantee at accuracy ρε, and the claim follows. ,M Claims 4 and 5 give mF CoT (ρε) = Θ(N ). We next prove the end-to-end lower bound. ,M Claim 6. There is a universal constant c > 0 such that mF e2e (ε) ≥ cN M/ε.

Proof. Let P be the uniform distribution on all roots xj,i , where j ∈ [N ] and i ∈ [d]. Draw all signs σj,i independently and uniformly from {−1, 1}. In the e2e model, Claim 3 shows that, conditional on X = xj,i , the observed final token has √ law Bern(1/2 + b ε σj,i ). Consider two parameters that differ only in the sign σj,i . One sample has different law only when X = xj,i , an event of probability 1/(N d). Conditional on this event, √ √ √ the Bernoulli parameter changes from 1/2 + b ε to 1/2 − b ε. Since b ε ≤ 1/4, Lemma 3 gives conditional KL at most C0 b2 ε. Therefore one sample has adjacent KL at most C0 b2 ε/(N d). For n samples, the adjacent KL is at most C0 b2 nε/(N d). If n ≤ c1 N d/ε, with c1 > 0 universal and small enough, the adjacent KL is at most 1/50 for every edge. By the Assouad consequence stated at the beginning of the proof, every estimator of the N d signs has Hamming error at least aHam N d with probability greater than 1/3. Given any regression estimate qb, decode σ bj,i = 1 iff qb(xj,i ) ≥ 1/2. If σ bj,i ̸= σj,i , then Claim 3 gives
2 qb(xj,i ) − qge2e−M (x ) ≥ b2 ε. j,i σ Thus, on the event that the Hamming error is at least aHam N d, the squared-loss risk under P is at least aHam b2 ε. Since aHam b2 > 1, this risk is larger than ε. Therefore the average failure probability over the random signs, the sample, and the learner randomness is greater than 1/3, so there exists at least one fixed value of the signs for which the learner fails with probability greater than 1/3. Hence no learner using n ≤ c1 N d/ε samples can satisfy the uniform PAC guarantee at accuracy ε. ,M Since d = M − 1 and M ≥ 2, we have d ≥ M/2. Hence mF e2e (ε) ≥ cN M/ε for a universal constant c > 0. Finally we prove the end-to-end upper bound. ,M Claim 7. There is a universal constant C > 0 such that mF e2e (ε) ≤ CN M/ε.

31

Proof. By Claim 3, the end-to-end class F e2e−M has at most 2N d distinct functions. Indeed, the only parameter-dependent M -step values occur on the roots, and these values are indexed by the N d signs σj,i . Applying Lemma 1 to the finite class F e2e−M , with approximation error α = 0, gives an end-to-end learner using at most C0

log |F e2e−M | + 1 Nd + 1 ≤ C1 ε ε

,M samples. Since N ≥ 1, M ≥ 2, and d = M − 1, we have N d + 1 ≤ 2N M . Therefore mF e2e (ε) ≤ CN M/ε. F ,M Combining Claims 6 and 7 gives mF,M e2e (ε) = Θ(N M/ε). Combining this with mCoT (ρε) = Θ(N ) gives   M F ,M F ,M me2e (ε) = Θ m (ρε) . ε CoT

This completes the proof.

6.2

Summary

By Theorem 6.1 and Theorem 6.2, we immediately obtain the following theorem, presented informally in the introduction: Theorem 6.3. There are universal constants c, C > 0 such that, for every stochastic generator class F, every M ≥ 2, every 0 < ε < 1, and every 0 < δ < 1/2,   ,M (cε, 1/3) logC (C/ε) + log(1/δ) M 1 ∨ mF CoT F ,M me2e (ε, δ) ≤ C . ε Moreover, there are universal constants ρ, c, C > 0, with ρ < 1, and ε0 > 0 such that the following holds. For every N ≥ 1, every M ≥ 2, and every 0 < ε ≤ ε0 , there is a finite binary-token stochastic ,M F ,M NM NM autoregressive class F such that cN ≤ mF CoT (ρε) ≤ CN and c ε ≤ me2e (ε) ≤ C ε As a corollary of Theorem 5.1 and Theorem 6.1, we have the following. Corollary 6.4 (Base-to-e2e comparison). There are universal constants c, C > 0 such that, for every stochastic generator class F, every M ≥ 2, every 0 < ε < 1, and every 0 < δ < 1/2,

C 2 M 1 ∨ mF F ,M base cε/M , 1/3 log (C/ε) + log(1/δ) me2e (ε, δ) ≤ C . ε Proof. By Theorem 6.1, ,M mF e2e (ε, δ) ≤ C

  ,M M 1 ∨ mF (cε, 1/3) logC (C/ε) + log(1/δ) CoT ε

By Theorem 5.1,
,M F 2 mF CoT (cε, 1/3) ≤ mbase cε/M , 1/3 , after changing the constant c if needed. Combined, the proof follows.

32

.

7

Fat-shattering bounds for end-to-end learning

Write pg (s) := g(s)(1), and write fatF (ρ) := fat{pg :g∈F } (ρ). This section proves the ordinary fat-shattering theory for end-to-end learning. The main point is that the M -step end-to-end probability is Lipschitz, with constant M , in the one-step transition probabilities along the depth-M autoregressive tree. We use the following finite-domain L∞ entropy consequence of Rudelson and Vershynin [14, Theorem 4.4]. The statement below is written in the present paper’s normalization of fat-shattering: their possible constant-factor choices in the shattering margin and in the covering scale are absorbed into cα and Cα . For a class A ⊆ [0, 1]X , a finite set S ⊆ X , and η > 0, let N∞ (η, A, S) denote the smallest number of ℓ∞ (S)-balls of scale η needed to cover the restrictions {f |S : f ∈ A}. Theorem 7.1. This is Theorem 4.4 of Rudelson and Vershynin [14], in the present normalization. For every 0 < α ≤ 1, there are constants Cα > 0 and 0 < cα ≤ 1/2 such that, for every A ⊆ [0, 1]X , finite S ⊆ X with |S| = N , and 0 < η ≤ 1/2,     2eN 2eN log N∞ (η, A, S) ≤ Cα fatA (cα η) log logα , fatA (cα η)η fatA (cα η) whenever 1 ≤ fatA (cα η) ≤ N . If fatA (cα η) = 0, then N∞ (η, A, S) ≤ 1. The following result bounds the fat shattering of the end-to-end class by the fat shattering dimension of the base class, with a finer scale. Theorem 7.2. For every 0 < α ≤ 1, there are constants Cα , cα > 0 such that, for every stochastic generator class F , every M ≥ 1, and every 0 < γ ≤ 1,   c γ     c γ 1+α 16M α α fatF e2e−M (γ) ≤ Cα fatF M + log + log 1 + fatF . 2M γ 2M Proof. Fix 0 < α ≤ 1, M ≥ 1, and 0 < γ ≤ 1. Let A := {pg : g ∈ F}, and let ∆ := fatA (cα γ/(2M )), where cα is the constant from Theorem 7.1. Thus ∆ = fatF (cα γ/(2M )). If ∆ = ∞, there is nothing to prove, so assume ∆ < ∞. It suffices to show that every finite set that is γ-fat-shattered by F e2e−M has size at most the claimed upper bound. Let x1 , . . . , xn ∈ {0, 1}⋆ be γ-fat-shattered by F e2e−M . If n = 0, there is nothing to prove. Otherwise, there exist thresholds r1 , . . . , rn ∈ R such that for every B ⊆ [n], there is a generator gB ∈ F satisfying qge2e−M (xi ) ≥ ri + γ for i ∈ B, and qge2e−M (xi ) ≤ ri − γ for i ∈ / B. Thus, for B B ′ distinct B, B ⊆ [n], the two vectors  
e2e−M e2e−M e2e−M qge2e−M (x ), . . . , q (x ) and q (x ), . . . , q (x ) 1 n 1 n gB gB ′ gB ′ B are 2γ-separated in ℓ∞ . Therefore 2n ≤ N∞

γ 2

 , F e2e−M , {x1 , . . . , xn } .

We now upper-bound this covering number by covering the one-step probability class on the finite autoregressive trees rooted at x1 , . . . , xn . Define U := {xi z : i ∈ [n], z ∈ {0, 1}<M }. Then n ≤ |U | ≤ n(2M − 1) ≤ n2M . Set η := γ/(2M ). Let V be a minimal η-cover of the one-step probability class A on U . Thus each v ∈ V is a function v : U → [0, 1], and for every g ∈ F, there is v ∈ V such that supu∈U |pg (u) − v(u)| ≤ η. 33

For each v ∈ V, define Qv = (Qv (x1 ), . . . , Qv (xn )) ∈ [0, 1]n as follows. Starting from each xi , run the same autoregressive process as before, but use the transition probability v(xi z) whenever the current generated prefix is z ∈ {0, 1}<M . Let Qv (xi ) be the probability that this finite-tree process outputs 1 at time M . We claim that {Qv : v ∈ V} is a γ/2-cover of F e2e−M on {x1 , . . . , xn }. Indeed, fix g ∈ F, and choose v ∈ V such that supu∈U |pg (u) − v(u)| ≤ η. For each i ∈ [n], couple the true autoregressive process generated by g from xi with the finite-tree process generated by v. As long as the two generated prefixes agree, the next-token Bernoulli parameters differ by at most η, so the probability that the coupled processes split at that step is at most η. By the union bound over the M steps, the probability that the two trajectories ever split is at most M η. Hence their final bits differ with probability at most M η, and therefore qge2e−M (xi ) − Qv (xi ) ≤ M η =

γ . 2

Since this holds for every i ∈ [n], the claim follows. Therefore  γ , F e2e−M , {x1 , . . . , xn } ≤ |V| = N∞ (η, A, U ). N∞ 2 Combining this with the lower bound above gives 2n ≤ N∞ (η, A, U ). Now apply Theorem 7.1 to the one-step probability class A on the finite set U . Since cα η = cα γ/(2M ), the relevant fat-shattering dimension is exactly ∆. If ∆ = 0, then Theorem 7.1 gives N∞ (η, A, U ) ≤ 1. Thus 2n ≤ 1, so n = 0, a contradiction to the assumption that n ≥ 1. Hence no nonempty finite set can be γ-fat-shattered by F e2e−M , and the claimed bound holds. It remains to consider the case ∆ ≥ 1. If ∆ > |U |, then n ≤ |U | < ∆, and the claimed bound follows immediately after increasing the constant Cα . Hence we may assume 1 ≤ ∆ ≤ |U |. By Theorem 7.1,     2e|U | α 2e|U | log N∞ (η, A, U ) ≤ Cα ∆ log log . ∆η ∆ Since 2n ≤ N∞ (η, A, U ), |U | ≤ n2M , and η = γ/(2M ), we get 



n ≤ Cα ∆ log n + M + log

16M γ

1+α .

Let A := M + log(16M/γ). Then n ≤ Cα ∆(log n + A)1+α . We use the following technical claim. Claim 8. For every p ≥ 1, there is a constant Cp > 0 such that the following holds. If a ≥ 1, A ≥ 1, and n ≥ 1 satisfy n ≤ a(log n + A)p , then n ≤ Cp a(A + log a)p . Proof. Put B := A + log a. Write n = aB p y. Since B ≥ 1,   p log n + A = B + p log B + log y ≤ B 1 + + log y , e where we used log B ≤ B/e. Choose Cp so large that 1 + p/e + log y < y 1/p for every y > Cp . If y > Cp , then a(log n + A)p < aB p y = n, contradicting n ≤ a(log n + A)p . Hence y ≤ Cp , which is exactly n ≤ Cp a(A + log a)p .

34

Applying Claim 8 with p = 1 + α and a = Cα ∆, and absorbing constants into Cα , gives  1+α   16M + log(1 + ∆) n ≤ Cα ∆ M + log . γ Since this holds for every finite γ-fat-shattered set x1 , . . . , xn , the result follows. We have the following as an immediate corollary. Corollary 7.3. For every 0 < α ≤ 1, there are constants cα , Cα > 0 such that, for every M ≥ 1, every stochastic generator class F, every 0 < ε < 1, and every 0 < δ < 1/2,   √ fatF (cα ε/M ) M 1+α + log(1/δ) F ,M e me2e (ε, δ) ≤ Oα , ε eα hides factors polylogarithmic in M , 1/ε, and 1+fatF (cα √ε/M ), with constants depending where O on α. √ Proof. Apply Lemma 2 to the class A = F e2e−M . Theorem 7.2, with γ = Θ( ε), gives
√ √ eα fatF (cα ε/M ) M 1+α . fatF e2e−M (c ε) ≤ O Substituting this into Lemma 2 gives the claim. We now prove the matching lower bound and the optimality of the

√

ε/M margin scale.

Theorem 7.4 (Tight e2e lower bound from ordinary fat-shattering). There are universal constants c, c′ > 0 and ε0 > 0 such that the following holds for every d ≥ 1, every M ≥ 1, and every √ 0 < ε ≤ ε0 . There is a stochastic generator class Fe2e such that fatFe2e (c ε/M ) = Θ(d) and e2e ,M mF (ε) ≥ c′ e2e

dM . ε

Proof. Choose a universal constant a > 0 so large that a2 /16 > 1. Choose ε0 > 0 small enough so √ √ that 1/2 + a ε ≤ 1 and 1/2 − a ε ≥ 0 for every 0 < ε ≤ ε0 . Choose prefix-free roots {xj,t : j ∈ [d], t ∈ [M ]} ⊆ {0, 1}⋆ so that their full descendant subtrees are pairwise disjoint. For σ = (σj,t )j∈[d],t∈[M ] ∈ {−1, 1}dM , write σ̄j,<r ∈ {0, 1}r−1 for the word obtained from σj,1 , . . . , σj,r−1 by sending 1 to 1 and −1 to 0. Define gσ below xj,t as follows. If |u| < t − 1, set pgσ (xj,t u) = 1{σj,|u|+1 = 1} when u = σ̄j,<|u|+1 , and set pgσ (xj,t u) = 0 otherwise. √ If |u| = t − 1, set pgσ (xj,t u) = 1/2 + a ε σj,t when u = σ̄j,<t , and set pgσ (xj,t u) = 0 otherwise. If |u| ≥ t, set pgσ (xj,t u) equal to the last bit of u. On all remaining states set the probability to zero. Let Fe2e := {gσ : σ ∈ {−1, 1}dM }. Starting from xj,t , the first t − 1 tokens are deterministically σ̄j,<t . This follows by induction on the time index: before time r < t, the current prefix is σ̄j,<r , and the next-token probability is 1{σj,r = 1}. Thus the next bit is exactly the binary encoding of σj,r . At time t, the state is √ xj,t σ̄j,<t , so the generated bit has mean 1/2 + a ε σj,t . After time t, the transition probability is the last generated bit, so all later tokens copy the time-t token. Hence the final token equals the time-t token, and therefore √ qge2e−M (xj,t ) = 1/2 + a ε σj,t . σ We next compute the ordinary fat dimension. Fix j. Call the union of the subtrees rooted at xj,1 , . . . , xj,M the j-th block. For a state s in this block and a threshold r, define A+ s (r, ρ) to be the 35

set of σj ∈ {−1, 1}M for which pgσ (s) ≥ r + ρ. Suppose that s belongs to a fat-shattered set at scale ρ with threshold r. Since both labels must be realizable at s, there is some σj with pgσ (s) ≤ r − ρ. Because pgσ (s) ≥ 0, this implies r ≥ ρ. Hence if pgσ (s) = 0, then pgσ (s) < r + ρ, so such a σj is not in A+ s (r, ρ). Now inspect the definition of gσ . A positive value at a pre-time state forces a fixed hidden prefix and possibly the next hidden sign. A positive value at the time-t state forces the prefix σ̄j,<t , and, depending on the threshold, may also force σj,t = 1. A post-time copy state has value determined by the last bit of the state, so its positive set is either empty or all of {−1, 1}M . Therefore A+ s (r, ρ) is either empty, all of {−1, 1}M , or a prefix cylinder {σj : w ⪯ σj }. M If s belongs to a fat-shattered set, then A+ s (r, ρ) is neither empty nor all of {−1, 1} , because otherwise one of the two labels at s could not be realized. Thus every state from the j-th block that belongs to a fat-shattered set has a nonempty proper prefix-cylinder positive set. Prefix cylinders are laminar: for any two such cylinders A and B, either A ∩ B = ∅, A ⊆ B, or B ⊆ A. If A ∩ B = ∅, then no σj can make both states positive. Thus the labeling in which both states are positive is impossible. If A ⊆ B, then every σj that makes the state with positive set A positive also makes the state with positive set B positive. Thus the labeling in which the first state is positive and the second state is negative is impossible. The case B ⊆ A is symmetric. Hence no two states from the same block can both belong to a fat-shattered set. Every state outside these blocks has parameter-independent one-step value 0, so no such state can belong to a nonempty fat-shattered set at any positive scale. Since there are d blocks, fatFe2e (ρ) ≤ d for every ρ > 0. √ For the reverse inequality, the d states xj,1 , j ∈ [d], are shattered at every scale ρ ≤ a ε, using threshold 1/2. Indeed, for any labels b ∈ {−1, 1}d , set σj,1 = bj for all j, and choose the remaining coordinates of σ arbitrarily. Then √ bj = 1 ⇒ pgσ (xj,1 ) = 1/2 + a ε ≥ 1/2 + ρ and

√ bj = −1 ⇒ pgσ (xj,1 ) = 1/2 − a ε ≤ 1/2 − ρ.

√ √ √ Since c ε/M ≤ a ε after decreasing c and using M ≥ 1, we get fatFe2e (c ε/M ) ≥ d. Together √ with the upper bound fatFe2e (ρ) ≤ d, this gives fatFe2e (c ε/M ) = d. Let P be uniform on the dM prompts xj,t , and draw σ uniformly from {−1, 1}dM . In the e2e √ model, a sample from xj,t is one Bernoulli observation with mean 1/2 + a ε σj,t . If σ ′ differs from σ only at coordinate (j, t), then one e2e sample differs only when the prompt is xj,t . Therefore KL(Pσ ∥Pσ′ ) =

√ √ 1 ε KL Bern(1/2 + a ε σj,t ) Bern(1/2 − a ε σj,t ) ≤ Ca . dM dM

For n i.i.d. samples, KL(Pσ⊗n ∥Pσ⊗n ′ ) = n KL(Pσ ∥Pσ ′ ) ≤ Ca nε/(dM ). Choose ce2e > 0 so small that Ca ce2e ≤ 1/50. If n ≤ ce2e dM/ε, then the adjacent KL condition in Lemma 6 holds with D = dM . For any predictor qb, define the induced sign estimator by σ bj,t = 1 if qb(xj,t ) ≥ 1/2, and σ bj,t = −1 otherwise. If σ bj,t ̸= σj,t , then (b q (xj,t ) − qge2e−M (xj,t ))2 ≥ a2 ε. σ If dH (b σ , σ) ≥ dM/16, then, since P is uniform on the dM prompts, d

EX∼P (b q (X) − qge2e−M (X))2 = σ

M

1 XX (b q (xj,t ) − qge2e−M (xj,t ))2 ≥ a2 ε/16 > ε. σ dM j=1 t=1

36

By Lemma 6, this event has probability at least 31/80 > 1/3 whenever n ≤ ce2e dM/ε. Therefore, for every learner using at most ce2e dM/ε samples, the average over σ of the failure probability is larger than 1/3. Hence there exists some σ for which the failure probability is larger than 1/3, so no such learner can guarantee squared risk at most ε with probability at least 2/3 uniformly over e2e ,M Fe2e . This proves mF (ε) ≥ ce2e dM/ε. Taking c′ = ce2e completes the proof. e2e Theorem 7.5 (Scale optimality of the e2e fat-shattering margin). Fix 0 < β < 1/2 and c > 0. There is a universal constant c0 > 0 such that the following holds. For every M ≥ 2, every K ≥ 1, and all sufficiently small ε > 0, there is a finite binary-token stochastic generator class F such that ! ε1/2−β fatF c =0 M and

K . ε √ Consequently, the scale ε/M in Corollary 7.3 cannot be replaced, in general, by the coarser scale ε1/2−β /M . ,M mF e2e (ε) ≥ c0

Proof. Fix M ≥ 2 and K ≥ 1. Choose prefix-free roots x1 , . . . , xK ∈ {0, 1}⋆ so that their full descendant subtrees are pairwise disjoint. Let √ 1 a ε θ= and λ= , 4M M where a > 0 is a sufficiently large universal constant, fixed below. We assume throughout that ε is sufficiently small so that λ ≤ θ/4. For each sign vector σ ∈ {−1, 1}K , define a generator gσ as follows. For every j ∈ [K] and every t = 0, . . . , M − 1, set pgσ (xj 0t ) = θ + σj λ. If a trajectory starting from xj emits a 1 before time M , then it enters a sign-independent absorbing region in which all one-step probabilities are equal to 1. On all remaining states, set the one-step probability to 0. Let F = {gσ : σ ∈ {−1, 1}K }. This is a finite stochastic generator class. We first show that the one-step class has zero fat-shattering dimension at the coarser scale. For every state s, the set {pgσ (s) : σ ∈ {−1, 1}K } is either a singleton or is contained in an interval of length 2λ. Since λ a = εβ , 1/2−β c cε /M we have λ < cε1/2−β /M for all sufficiently small ε. Thus the pointwise diameter of the one-step class is strictly smaller than 2cε1/2−β /M . Hence no single point is cε1/2−β /M -fat-shattered, and therefore ! ε1/2−β fatF c = 0. M We now prove the end-to-end lower bound. Starting from xj , the final token is 1 if and only if at least one of the M trials on the all-zero chain emits 1. Hence qge2e−M (xj ) = 1 − (1 − θ − σj λ)M . σ 37

Let q+ = 1 − (1 − θ − λ)M ,

q− = 1 − (1 − θ + λ)M ,

∆=

q+ − q − . 2

By the mean value theorem, q+ − q− = 2M λ(1 − θ − ξ)M −1 for some |ξ| ≤ λ. Since λ ≤ θ/4 and θ = 1/(4M ), the term (1 − θ − ξ)M −1 is bounded below by a universal positive constant. Thus, after choosing the universal constant a large enough, we have √ ∆ ≥ 10 ε. Also, for all sufficiently small ε, both q+ and q− are bounded away from 0 and 1 by universal constants. Let P be the uniform distribution on {x1 , . . . , xK }. We prove a lower bound under this fixed prompt distribution. Draw σ uniformly from {−1, 1}K , and generate the end-to-end sample from gσ . Conditional on X = xj , the final bit satisfies ( Ber(q+ ), σj = 1, ZM ∼ Ber(q− ), σj = −1. Each sample carries only O(ε) information about σ. Indeed, X is independent of σ, and conditional on X = xj the observation depends only on the single bit σj . Since q+ and q− are bounded away √ from 0 and 1 and |q+ − q− | = 2∆ = O( ε), there is a universal constant C > 0 such that I(σ; X, ZM ) ≤ Cε. Writing Sn := ((Xi , Zi,M ))ni=1 , conditional independence given σ and entropy subadditivity give I(σ; Sn ) ≤ nI(σ; X, ZM ) ≤ Cnε. The learner’s private randomness is independent of σ, so including it cannot increase the information about σ beyond this bound. Suppose a learner succeeds with probability at least 2/3 using n samples. From its output qb, define an estimator σ b by thresholding at the midpoint (q+ + q− )/2: ( 1, qb(xj ) ≥ (q+ + q− )/2, σ bj = −1, qb(xj ) < (q+ + q− )/2. If σ bj ̸= σj , then

|b q (xj ) − qge2e−M (xj )| ≥ ∆. σ

Hence, on the event that the squared loss under P is at most ε, K

1 X ε 1 1{b σj ̸= σj } ≤ 2 ≤ . K ∆ 100 j=1

Thus, with probability at least 2/3, the estimator σ b has Hamming error at most K/100. We use the following standard Fano rate-distortion bound on the uniform hypercube. Lemma 11 (Hypercube rate-distortion). Let σ be uniform on {−1, 1}K , let S be any observation, and let σ b=σ b(S) be any estimator. If Pr [dH (b σ , σ) ≤ K/100] ≥ 2/3, then I(σ; S) ≥ cK for a universal constant c > 0. 38

Proof. Let h(t) = −t log t−(1−t) log(1−t) be the binary entropy function, with natural logarithms, and let E = {dH (b σ , σ) ≤ K/100}. Assume first that K ≥ 100. By the entropy decomposition, H(σ | S) ≤ H(E | S) + Pr(E)H(σ | S, E) + Pr(E c )H(σ | S, E c ). For every fixed value of S, on the event E the vector σ belongs to a Hamming ball of radius K/100 around σ b(S). The size of such a ball is at most exp(h(1/100)K). Also, H(E | S) ≤ log 2 and H(σ | S, E c ) ≤ K log 2. Since Pr(E c ) ≤ 1/3, we get 1 H(σ | S) ≤ log 2 + h(1/100)K + K log 2. 3 Therefore

 I(σ; S) = H(σ) − H(σ | S) ≥

 2 log 2 − h(1/100) K − log 2. 3

Since 32 log 2 > h(1/100), the last display is at least c1 K for all K ≥ 100, after choosing a sufficiently small universal constant c1 > 0. It remains to handle 1 ≤ K < 100. In this case K/100 < 1, so the event dH (b σ , σ) ≤ K/100 implies σ b = σ. Hence Pr(b σ = σ) ≥ 2/3. By the ordinary Fano inequality, I(σ; S) ≥ K log 2 − h(1/3) −

1 log(2K − 1). 3

For each fixed 1 ≤ K < 100, this lower bound is positive. Since there are only finitely many such K, it is at least c2 K for a universal constant c2 > 0. Taking c = min{c1 , c2 } completes the proof. By the above lemma, any estimator of σ ∈ {−1, 1}K that has Hamming error at most K/100 with probability at least 2/3 must satisfy I(σ; Sn ) ≥ c1 K for a universal constant c1 > 0. Combining this with I(σ; Sn ) ≤ Cnε gives n ≥ c0

K ε

for a universal constant c0 > 0. Since the lower bound holds for the fixed prompt distribution P , it holds for the distribution-free e2e sample complexity. This proves the theorem. Theorem 7.6 (Ordinary fat-shattering theory for e2e learning). For end-to-end learning, ordinary fat-shattering gives the following three statements. 1. For every fixed 0 < α ≤ 1, there is a constant cα > 0 such that for every class F, every M ≥ 1, every 0 < ε < 1, and every 0 < δ < 1/2,   1+α √ M fatF (cα ε/M ) + log(1/δ) F ,M e me2e (ε, δ) ≤ Oα . ε 2. There are universal constants c, c′ > 0 such that for every d ≥ 1, every M ≥ 1, and all √ sufficiently small ε > 0, there is a finite class F with fatF (c ε/M ) = Θ(d) and ,M ′ mF e2e (ε) ≥ c

39

dM . ε

3. There is a universal constant c0 > 0 such that for every 0 < β < 1/2 and every c > 0, √ the scale ε/M cannot be replaced by ε1/2−β /M : for every M ≥ 2, every K ≥ 1, and all sufficiently small ε > 0, there is a finite class F with ! ε1/2−β =0 fatF c M and ,M mF e2e (ε) ≥ c0

K . ε

Proof. The upper bound is Corollary 7.3. The matching lower bound is Theorem 7.4. The scaleoptimality statement is Theorem 7.5.

8

Case study: stochastic logistic autoregressive learning

We now study a dimension-d autoregressive logistic regression family. The same logistic rule is reused at every autoregressive step, and the target weights are unrestricted. Autoregressive logistic regression class. For d ≥ 1 and s ∈ {0, 1}⋆ , let taild (s) ∈ {0, 1}d be the vector of the last d bits of s, padded by zeros on the left if |s| < d. Let Fσ (d) be the class of stochastic generators {gw : w ∈ Rd } defined by pgw (s) = gw (s)(1) = σ(⟨w, taild (s)⟩),

σ(a) :=

1 . 1 + e−a

Thus the log-odds of the next token are a linear function of the last d bits of the current autoregressive state. This is the binary softmax, equivalently logistic or sigmoid, case.

8.1

An explicit non-efficient statistical e2e learner

The first positive result is a distribution-free end-to-end sample-complexity bound. It is not meant to be computationally efficient; it learns the induced final-token predictor directly. Let ⋆ Qd,M := {qge2e−M : w ∈ Rd } ⊆ [0, 1]{0,1} . w The following lemma is the structural reason the e2e statistical complexity is only logarithmic in the horizon. Lemma 12. There is a universal constant C > 0 such that, for every d ≥ 1 and M ≥ 1, Pdim(Qd,M ) ≤ Cd2 log(C(M + 2)). Q Proof. Write uj = ewj and uy = j:yj =1 uj for y ∈ {0, 1}d . Then, for every y ∈ {0, 1}d , σ(⟨w, y⟩) =

uy , 1 + uy

1 − σ(⟨w, y⟩) =

1 . 1 + uy

Fix a prompt x. The value qge2e−M (x) is the sum, over all continuations z1 , . . . , zM ∈ {0, 1} with w zM = 1, of the probability of that continuation. Along such a continuation, the state before step t is yt = taild (xz1 · · · zt−1 ), and the factor contributed by step t is (uyt )zt /(1 + uyt ). Therefore every 40

continuation term is a rational function whose denominator is a product of M factors of the form 1 + uy . Use the positive common denominator Y (1 + uy )M . D(u) = y∈{0,1}d

This denominator clears every continuation term, because no state y can be visited more than M times in a length-M continuation. Its degree is X |y| = M d2d−1 , deg D = M y∈{0,1}d

since each coordinate is equal to 1 in exactly 2d−1 vectors in {0, 1}d . We next check the degree after clearing denominators. Fix one continuation. For each y ∈ {0, 1}d , let my be the number of times this continuation visits state y, and let ℓy be the number of those visits at which the emitted P token is 1. Then 0 ≤ ℓy ≤ my ≤ M . The numerator of the continuation term has degree y ℓy |y|. After multiplying by D(u), the remaining factor from P Q clearing denominators is y (1 + uy )M −my , which has degree y (M − my )|y|. Hence the cleared continuation term has degree at most X X X ℓy |y| + (M − my )|y| ≤ M |y| = M d2d−1 . y

y

y

Summing over continuations does not increase degree. Thus D(u)qge2e−M (x) is a polynomial of w d−1 degree at most M d2 . Now fix a threshold a ∈ R. Since D(u) > 0 for every u1 , . . . , ud > 0, the inequality qge2e−M (x) > a w is equivalent, on the parameter domain u1 , . . . , ud > 0, to D(u)qge2e−M (x) − aD(u) > 0. w The left-hand side is a polynomial in u1 , . . . , ud of degree at most M d2d−1 . The pseudo-dimension of Qd,M is the VC dimension of its subgraph class. The preceding paragraph shows that every subgraph membership test for Qd,M is represented, after the change of variables uj = ewj , by one polynomial inequality in d real parameters, of degree at most M d2d−1 . Restricting the parameter domain to u1 , . . . , ud > 0 cannot increase the number of labelings. Therefore the Goldberg–Jerrum bound for semialgebraic classes defined by polynomial inequalities implies Pdim(Qd,M ) ≤ Cd log(CM d2d ), for a universal constant C; see Goldberg and Jerrum [47]. It remains only to simplify this expression. Since d ≥ 1 and M ≥ 1,
d log(CM d2d ) ≤ Cd log(M + 2) + log(d + 1) + d ≤ Cd2 log(C(M + 2)), after increasing the universal constant C. Hence Pdim(Qd,M ) ≤ Cd2 log(C(M + 2)).

41

Theorem 8.1. There is a universal constant C > 0 such that, for every d ≥ 1, M ≥ 1, 0 < ε < 1, and 0 < δ < 1/2, F (d),M

σ me2e

(ε, δ) ≤ C

d2 log(C(M + 2)) logC (C/ε) + log(1/δ) . ε

The learner is improper and need not run in polynomial time. Proof. By Lemma 12, Pdim(Qd,M ) ≤ Cd2 log(C(M + 2)). For every scale γ > 0, fatQd,M (γ) ≤ Pdim(Qd,M ). Applying Lemma 2 to the real-valued class Qd,M gives the displayed sample bound. The learner returned by that lemma is a bounded regression predictor for the final-token probability, not necessarily a generator from Fσ (d).

8.2

An efficient proper CoT learner

We next give an efficient proper chain-of-thought learner for the same logistic regression class. Unlike the preceding e2e learner, this learner outputs a generator from the original logistic class and runs in polynomial time. Lemma 13. There is a universal constant C > 0 such that the following holds. For every d ≥ 1, every 0 < η < 1/2, and every w ∈ Rd , there is a rational vector v ∈ Rd whose coordinates have binary descriptions of length at most Cd log(Cd/η) and such that, for every y ∈ {0, 1}d , |σ(⟨w, y⟩) − σ(⟨v, y⟩)| ≤ η and h2 (Bern(σ(⟨w, y⟩)), Bern(σ(⟨v, y⟩))) ≤ η. M Moreover, for every prompt x and every horizon M ≥ 1, if PM w,x and Pv,x are the laws of the length-M continuations generated from x by gw and gv , then M h2 (PM w,x , Pv,x ) ≤ M η.

Proof. Choose T and α so that T is a positive integer, e−T ≤ η/C, and α ≤ η/C, where C is a sufficiently large universal constant. It is enough to take T ≤ C log(C/η) and α rational with binary description length at most C log(C/η). Define A+ = {y ∈ {0, 1}d : ⟨w, y⟩ ≥ T }, A− = {y ∈ {0, 1}d : ⟨w, y⟩ ≤ −T }, A0 = {y ∈ {0, 1}d : |⟨w, y⟩| < T }. For each y ∈ A0 , choose a rational number ry on the grid αZ such that |⟨w, y⟩ − ry | ≤ α. Since |⟨w, y⟩| < T , each ry has binary description length at most C log(C/η). Consider the following linear system in the unknown vector v ∈ Rd : ⟨v, y⟩ ≥ T

(y ∈ A+ ),

⟨v, y⟩ ≤ −T

(y ∈ A− ),

|⟨v, y⟩ − ry | ≤ α

(y ∈ A0 ).

This system is feasible. Indeed, the original vector w satisfies the first two families of inequalities by the definitions of A+ and A− , and it satisfies the last family because |⟨w, y⟩ − ry | ≤ α for every y ∈ A0 . The coefficients of this system belong to {−1, 0, 1}, and all right-hand sides have binary descriptions of length at most C log(C/η). By the standard bit-complexity bound for feasible rational 42

linear systems in d variables, there is a rational feasible solution v whose coordinates have binary descriptions of length at most
Cd log(C/η) + log(Cd) ≤ Cd log(Cd/η); see Schrijver [46, Chapter 10]. We now prove the probability and Hellinger bounds. Fix y ∈ {0, 1}d and write p = σ(⟨w, y⟩) and q = σ(⟨v, y⟩). First suppose y ∈ A+ . Then ⟨w, y⟩ ≥ T and ⟨v, y⟩ ≥ T . Hence p ≥ 1 − e−T and q ≥ 1 − e−T . Therefore |p − q| ≤ e−T ≤ η/C. Also, for Bernoulli laws, h2 (Bern(p), Bern(q)) ≤ 2|p − q|, so h2 (Bern(p), Bern(q)) ≤ η after increasing C. The case y ∈ A− is identical. Indeed, ⟨w, y⟩ ≤ −T and ⟨v, y⟩ ≤ −T , so p ≤ e−T and q ≤ e−T . Hence |p − q| ≤ e−T ≤ η/C, and again h2 (Bern(p), Bern(q)) ≤ η. It remains to consider y ∈ A0 . By the constraints and by the choice of ry , |⟨v, y⟩ − ⟨w, y⟩| ≤ |⟨v, y⟩ − ry | + |ry − ⟨w, y⟩| ≤ 2α. The logistic map is 1-Lipschitz, so |p − q| ≤ 2α ≤ η/C. Since h2 (Bern(p), Bern(q)) ≤ 2|p − q|, increasing C gives |p − q| ≤ η and h2 (Bern(p), Bern(q)) ≤ η. Finally fix a prompt x and a horizon M . At every history xz1 · · · zt−1 , the two next-token Bernoulli laws under gw and gv have squared Hellinger distance at most η, because their covariate is some y ∈ {0, 1}d . Therefore the Hellinger affinity of each conditional transition is at least 1−η/2. Multiplying these conditional affinities along the trajectory gives affinity at least (1 − η/2)M for the two length-M trajectory laws. Hence
M M h2 (PM ≤ M η. w,x , Pv,x ) ≤ 2 1 − (1 − η/2) This proves the lemma. Lemma 14. Fix n ≥ 1, 0 < δ < 1, and γ ≥ 0. Let V be a finite set. For each v ∈ V, let Pv be a probability distribution with density pv with respect to a common measure. Assume that P⋆ = Pv⋆ for some v⋆ ∈ V, and let Y1 , . . . , Yn be i.i.d. from P⋆ . Suppose that vb ∈ V satisfies n

n

i=1

i=1

1X 1X − log pvb(Yi ) ≤ inf − log pu (Yi ) + γ. u∈V n n Then, with probability at least 1 − δ, 

log |V| + log(1/δ) h (Pvb, P⋆ ) ≤ C γ + n 2

 ,

where C > 0 is a universal constant. Proof. Since P⋆ = Pv⋆ and v⋆ ∈ V, the assumed empirical inequality implies n

n

i=1

i=1

1X 1X − log pvb(Yi ) ≤ − log p⋆ (Yi ) + γ. n n Equivalently,

n X i=1

log

pvb(Yi ) ≥ −nγ. p⋆ (Yi ) 43

Q Fix v ∈ V and define Lv = ni=1 pv (Yi )/p⋆ (Yi ), with any Pnvalue assigned to the ratio on the set where p⋆ = 0. This choice is irrelevant under P⋆ . If i=1 log(pv (Yi )/p⋆ (Yi )) ≥ −nγ, then Lv ≥ e−nγ . Therefore, by Markov’s inequality, p P⋆⊗n (Lv ≥ e−nγ ) ≤ enγ/2 EP⋆⊗n Lv . The expectation factorizes, and n  Z n p 1 2 √ = 1 − h (Pv , P⋆ ) . EP⋆⊗n Lv = pv p⋆ 2 Using 1 − t ≤ e−t gives  nγ

 n 2 h (Pv , P⋆ ) . 2 2 2 Set a = log |V| + log(1/δ). If h (Pv , P⋆ ) > 4(γ + a/n), then nγ n 2 − h (Pv , P⋆ ) < −a. 2 2 Hence, for each such v, δ . P⋆⊗n (Lv ≥ e−nγ ) ≤ e−a = |V| P⋆⊗n (Lv ≥ e−nγ ) ≤ exp

−

By a union bound, with probability at least 1 − δ, no v ∈ V with h2 (Pv , P⋆ ) > 4(γ + a/n) satisfies P n i=1 log(pv (Yi )/p⋆ (Yi )) ≥ −nγ. On this event, vb cannot have h2 (Pvb, P⋆ ) > 4(γ + a/n), because we already proved that vb satisfies the displayed likelihood-ratio inequality. Therefore   log |V| + log(1/δ) 2 h (Pvb, P⋆ ) ≤ 4 γ + . n This proves the lemma after replacing 4 by the universal constant C. CoT likelihood learner. In this theorem the generated tokens are encoded as 0 and 1. For every w ∈ Rd , every prompt x, and every history z1 , . . . , zt−1 ∈ {0, 1}, the conditional law is Pr(Zt = 1 | X = x, Z1 = z1 , . . . , Zt−1 = zt−1 ) = σ(⟨w, taild (xz1 · · · zt−1 )⟩). w √ Thus, if Yi,t := taild (Xi Zi,1 · · · Zi,t−1 ), then Yi,t ∈ {0, 1}d and ∥Yi,t ∥2 ≤ d. Given full trajectories (Xi , Zi,1 , . . . , Zi,M )N i=1 , define b N (w) := 1 L N

N X M X

[log(1 + exp(⟨w, Yi,t ⟩)) − Zi,t ⟨w, Yi,t ⟩] .

i=1 t=1

The learner is defined as follows. Input: d, M, ε, l δ, full trajectories. 1:

m 2 N := C d log(CdM/(εδ))+log(1/δ) . ε

2: 3: 4: 5: 6: 7: 8: Output:

Use only the first N trajectories. η0 := cδ 2 /(M N ). B := ⌈Cd log(CdM N/(εδ))⌉ , R := 2B . ρ := cε/(M d), k := ⌈log2 (1/ρ)⌉ , ρ0 := 2−k . W := {w ∈ Rd : |wj | ≤ R for all j}. b N (w) over W. Compute an additive cε-minimizer w̄ of L Round each coordinate of w̄ to a nearest point of ρ0 Z ∩ [−R, R]. gwb , where w b is the rounded vector. 44

Here c > 0 is a sufficiently small universal constant and C > 0 is a sufficiently large universal constant. Since k = ⌈log2 (1/ρ)⌉, we have ρ/2 ≤ ρ0 ≤ ρ. Theorem 8.2. There is a randomized algorithm with running time polynomial in the input size, d, M , 1/ε, and log(1/δ) such that the following holds. For every d ≥ 1, M ≥ 1, 0 < ε < 1, 0 < δ < 1/2, prompt distribution P , and target w⋆ ∈ Rd , the algorithm outputs a generator gwb ∈ Fσ (d), where w b is a rational vector of polynomial bit complexity, whose induced M -step end-to-end predictor satisfies h i e2e−M 2 EX∼P (qge2e−M (X) − q (X)) ≤ε gw⋆ w b 2

with probability at least 1 − δ. It suffices to take C d log(CdM/(εδ))+log(1/δ) full trajectories. ε Proof. If the learner receives more than N trajectories, it discards all but the first N . Thus it is enough to analyze the case of exactly N trajectories. Let the unknown generator be gw⋆ . For w ∈ Rd , let Pw denote the joint law of one CoT sample (X, Z1 , . . . , ZM ), where X ∼ P and the trajectory is generated by gw . By Lemma 13, applied with accuracy η0 , there is a rational vector v⋆ whose coordinates have binary descriptions of length at most Cd log(Cd/η0 ). Since η0 = cδ 2 /(M N ), 0 < ε < 1, and 0 < δ < 1/2, the quantity log(Cd/η0 ) = log(CdM N/δ 2 ) is bounded by C log(CdM N/(εδ)) after increasing C. Hence the bit length of v⋆ is at most B. The same lemma gives, for every prompt x, M h2 (PM w⋆ ,x , Pv⋆ ,x ) ≤ CM η0 .

The prompt marginal is the same under Pw⋆ and Pv⋆ , so integrating over X ∼ P gives h2 (Pw⋆ , Pv⋆ ) ≤ CM η0 . Therefore, for the N -sample laws, h2 (Pw⊗N , Pv⊗N ) ≤ CN M η0 ≤ cδ 2 . ⋆ ⋆ Since total variation is bounded by a universal constant times Hellinger distance, decreasing c if necessary gives dTV (Pw⊗N , Pv⊗N ) ≤ δ/4. ⋆ ⋆ Now analyze the algorithm under the compressed, well-specified law Pv⋆ . Let V be the finite set of all rational vectors in [−R, R]d whose coordinates have binary descriptions of length at most CB. Then v⋆ ∈ V. A rounded coordinate has denominator 2k and numerator magnitude at most 2B+k , so its binary description length is O(B + k). Since k = ⌈log2 (1/ρ)⌉ ≤ CB after increasing C, we have w b ∈ V. Hence log |V| ≤ CdB. b N (w) is convex in w. Each summand log(1 + exp(⟨w, Yi,t ⟩)) − For fixed observed trajectories, L √ √ b N (w) is M d-Lipschitz. By Zi,t ⟨w, Yi,t ⟩ is ∥Yi,t ∥2 -Lipschitz in w, and ∥Yi,t ∥2 ≤ d. Hence L construction of the coordinate rounding, √ √ ∥w b − w̄∥2 ≤ d ρ0 ≤ d ρ. Therefore b N (w) b N (w̄) + M dρ ≤ L b N (w̄) + cε. L b ≤L 45

Since w̄ is an additive cε-minimizer over W and V ⊆ W, b N (u) + cε. b N (w) + cε ≤ inf L b N (w̄) ≤ inf L L u∈V

w∈W

Combining the last two displays gives b N (w) b N (u) + Cε. L b ≤ inf L u∈V

b N (w) plus the The negative log-likelihood of the full trajectories under gw , divided by N , is L prompt-marginal contribution, which is independent of w with respect to any common dominating measure. Therefore it cancels in all empirical likelihood comparisons. Thus, under Pv⋆ , the preceding display is exactly the approximate empirical likelihood inequality required by Lemma 14, with γ = Cε, for the finite family {Pu : u ∈ V}. Under Pv⋆ this family is well specified, because Pv⋆ ∈ {Pu : u ∈ V}. Applying Lemma 14, with failure probability δ/2, gives   log |V| + log(1/δ) 2 h (Pwb , Pv⋆ ) ≤ C ε + N . Since log |V| ≤ CdB and with probability at least 1 − δ/2 under Pv⊗N ⋆ B ≤ Cd log(CdM N/(εδ)), we now bound the logarithmic dependence on N . Put A := CdM/(εδ). By the definition of N , after increasing C, N≤

C 2 d log A + log(1/δ) . ε

Since d ≥ 1, M ≥ 1, 0 < ε < 1, and 0 < δ < 1/2, this implies log(CdM N/(εδ)) ≤ C log A after increasing the universal constant C. Hence log |V| ≤ CdB ≤ Cd2 log A. On the other hand, the definition of N also gives, after increasing C, N≥

C 2 d log A + log(1/δ) . ε

Therefore, log |V| + log(1/δ) ≤ cε N after choosing the constants so that the universal constant in the numerator is dominated by the universal constant in the definition of N . Therefore, after choosing the universal constant c > 0 sufficiently small, h2 (Pwb , Pv⋆ ) ≤ cε 46

with probability at least 1 − δ/2 under Pv⊗N . ⋆ If the convex optimizer is randomized, include its random seed as an additional independent variable. The seed has the same law under Pw⊗N and Pv⊗N , so the total variation distance between ⋆ ⋆ the joint laws of samples and seed is still at most δ/4. Therefore the same event holds with probability at least 1 − δ under the true samples from Pw⊗N . ⋆ On this event, h2 (Pwb , Pw⋆ ) ≤ Ch2 (Pwb , Pv⋆ ) + Ch2 (Pv⋆ , Pw⋆ ) ≤ Ccε. The first inequality follows from the triangle inequality for Hellinger distance together with (a+b)2 ≤ 2a2 + 2b2 : for any laws P, Q, R, h2 (P, R) ≤ 2h2 (P, Q) + 2h2 (Q, R). The second inequality uses the previous display and h2 (Pv⋆ , Pw⋆ ) ≤ CM η0 ≤ cε, where the last inequality follows from N ≥ C/ε and δ < 1. We choose the universal constant c > 0 small enough that Ccε ≤ ε/C for the universal constant needed below. It remains to pass from trajectory law to final-token squared loss. Let Qwb and Q⋆ be the joint laws of (X, ZM ) induced by gwb and gw⋆ . By data processing for Hellinger distance, h2 (Qwb , Q⋆ ) ≤ h2 (Pwb , Pw⋆ ). Since the two laws have the same marginal distribution P on X, i h  e2e−M (X)), Bern(q (X)) . h2 (Qwb , Q⋆ ) = EX∼P h2 Bern(qge2e−M g w⋆ w b For Bernoulli distributions, (p − q)2 ≤ Ch2 (Bern(p), Bern(q)). Therefore, by the choice of c in the previous paragraph, h i e2e−M 2 ≤ Ch2 (Qwb , Q⋆ ) ≤ ε. (X) − q (X)) EX∼P (qge2e−M gw⋆ w b Finally, the running time is polynomial. The feasible set W = [−R, R]d is a rational box with description length O(dB), contains a Euclidean ball of radius 1, and is contained in a Euclidean ball √ B of radius 2 d. The empirical objective admits polynomial-time weak evaluation and subgradient oracles to any required polynomial precision. Indeed, log(1 + exp(a)) and σ(a) can be evaluated to polynomial accuracy in time polynomial in the bit length of a and the requested precision by using the stable identities log(1 + exp(a)) = max{a, 0} + log(1 + exp(−|a|)) and σ(a) = 1/(1 + exp(−a)). Therefore the ellipsoid method, equivalently the standard weak convex optimization theorem, computes an additive cε-minimizer in time polynomial in the input size, d, M , B, and log(1/ε); see Nesterov [21]. Since B ≤ Cd log(CdM N/(εδ)) and N is polynomial in d, M , 1/ε, and log(1/δ), this is polynomial in the claimed parameters. The rounding step is polynomial-time. The output is the explicit rational vector w, b so evaluating the next-token probabilities, and sampling from them to any desired polynomial precision, takes polynomial time.

8.3

An efficient-proper-learning hardness result

The LPN prediction assumption. We use the standard prediction-hardness form of learning parity with noise. Fix a constant noise rate η ∈ (0, 1/2). The assumption says that there is a constant ρ ∈ (0, 1/2) such that no randomized polynomial-time algorithm has the following guarantee. Given polynomially many samples X ∼ Unif({0, 1}m ),

Y = ⟨a, X⟩F2 ⊕ N,

47

N ∼ Ber(η),

where a ∈ {0, 1}m is unknown, the algorithm outputs a randomized polynomial-time evaluable classifier h : {0, 1}m → {0, 1} satisfying Pr [h(X) ̸= ⟨a, X⟩F2 ] ≤

X,h

1 −ρ 2

with probability at least 2/3, uniformly over a. This is the standard LPN prediction-hardness assumption; see Blum, Kalai and Wasserman [19]. End-to-end learning guarantee. An algorithm properly end-to-end learns Fσ (d) at horizon M with squared loss ε and confidence 1 − δ if the following holds. For every distribution D over prompts and every target generator gw⋆ ∈ Fσ (d), given independent samples S ∼ D,

(S)), Y | S ∼ Bern(qge2e−M w⋆

the algorithm outputs gwb ∈ Fσ (d) such that, with probability at least 1 − δ,  2  e2e−M e2e−M ES∼D qgwb (S) − qgw⋆ (S) ≤ ε. In this subsection, we call such a learner efficient if its sample use, training running time, and time to approximately sample one generated trajectory from the output generator to inverse-polynomial total-variation precision are all bounded by a polynomial in d, M , 1/ε, and log(1/δ). Lemma 15. For the fixed noise rate η ∈ (0, 1/2), there are constants c0 , C > 0, depending at most on η, such that the following holds. For every m ≥ 1, every a ∈ {0, 1}m , and every 0 < ζ < 1/2 satisfying log(1/ζ) ≤ mC , there are integers d ≤ mC ,

M = m + 1,

a polynomial-time computable prompt map ϕm : {0, 1}m → {0, 1}⋆ which is independent of a, and a vector wa ∈ Rd , such that d ≥ M and, for every x ∈ {0, 1}m , (ϕm (x)) − (η + (1 − 2η)⟨a, x⟩F2 ) ≤ ζ. qge2e−M wa Proof. We use lag notation, always relative to the current generation step. Index the coordinates of taild (s) from oldest to newest as 1, . . . , d. A weight placed on lag ℓ is placed on coordinate d − ℓ + 1 of taild . Equivalently, at generation step t, before Zt is sampled, this coordinate reads the bit at absolute time t − ℓ: it is Zt−ℓ if 1 ≤ ℓ < t, and it is an initial-prompt bit if ℓ ≥ t. We number the last bit of the initial prompt by absolute time 0 and earlier prompt bits by negative absolute times. Thus specifying the prompt bit at absolute time r ≤ 0 specifies the unique initial-prompt position read at step t by any lag ℓ with t − ℓ = r. This is only a re-indexing of taild . We take the prompt long enough to include all reserved positions below, and then shift all absolute-time indices into ordinary prompt positions. Set M := m + 1. The first m generated tokens will be threshold bits " m # X Tk (x) := 1 2 ai xi − (2k − 1) ≥ 0 , 1 ≤ k ≤ m. i=1

P

P Since i ai xi is an integer, the quantity 2 i ai xi − (2k − 1) is an oddP integer. Therefore it is never zero and has absolute value at least 1. Also Tk (x) = 1 exactly when i ai xi ≥ k. 48

For every pair (k, i) ∈ [m] × [m], choose a lag Lk,i > M and for every k ∈ [m] choose a lag Bk > M . Choose all these lags so far apart that the sets {t − Lk,i : 1 ≤ t ≤ M },

{t − Bk : 1 ≤ t ≤ M }

are pairwise disjoint over all k, i. This is possible with d ≤ Cm3 , after increasing C, and we also choose d ≥ M . All reserved lags are chosen at most d, so every reserved coordinate lies inside taild at each generation step in which it is used. The prompt map ϕm sets the prompt bit at absolute time k − Lk,i equal to xi , sets the prompt bit at absolute time k − Bk equal to 1, and sets all other prompt bits in the above reserved locations equal to 0. We also reserve one lag Bout > M , disjoint from all previous reserved windows, and set the prompt bit at absolute time M − Bout equal to 1, while all other bits in its reserved window are 0. This is the constant-one coordinate used for the final bias. All non-reserved prompt bits among the last d prompt positions are set to 0. Thus ϕm is computable in polynomial time and is independent of a. Let λ := log 1−η η . Then σ(λ) = 1 − η and σ(−λ) = η. Choose A := 2 + 4m|λ|, and choose Λ := C log(M/ζ) with C large enough so that M e−Λ ≤ ζ. The coordinates of wa are defined as follows. For every k, i, put weight 2AΛai on lag Lk,i . For every k, put weight −AΛ(2k − 1) on lag Bk . For the final readout, put weight 2λ(−1)k+1 on lag M − k, for each 1 ≤ k ≤ m, and put weight −λ on lag Bout . All other coordinates have weight 0. We now check the logits. At a threshold step k ≤ m, all threshold-reserved coordinates except the intended coordinates for this step read 0, by the disjointness of the reserved windows and by the definition of the prompt. The intended threshold contribution is ! m X AΛ 2 ai xi − (2k − 1) , i=1

whose absolute value is at least AΛ and whose sign is the desired threshold sign. The final-readout weights are reused at every step, so they may also contribute during the threshold-writing steps. Their total absolute contribution is at most 2m|λ|, and the final-bias coordinate Bout contributes 0 before the final step. Since A = 2 + 4m|λ| and Λ ≥ 1, the full threshold logit has the desired sign and absolute value at least AΛ − 2m|λ| ≥ Λ. Hence, whenever the previous stochastic outputs agree with the deterministic outputs, the token at step k disagrees with Tk (x) with probability at most e−Λ . By the union bound, the probability that any of the first m stochastic tokens differs from its deterministic value is at most M e−Λ ≤ ζ. Condition on no such deviation. Before the final step, the generated tokens are T1 (x), . . . , Tm (x). At the final step, the threshold-reserved coordinates all read 0, again by disjointness of the reserved windows. The lag M − k reads Zk = Tk (x), and the coordinate Bout reads the constant prompt bit 1. Therefore the final logit is m X 2λ (−1)k+1 Tk (x) − λ. k=1

P k+1 T (x) equals If s := i ai xi , then Tk (x) = 1 for k ≤ s and Tk (x) = 0 for k > s, so m k k=1 (−1) ⟨a, x⟩F2 . Hence, on the no-deviation event, the final output probability is η + (1 − 2η)⟨a, x⟩F2 . If a deviation occurred earlier, the final output probability can change by at most 1, proving the displayed approximation. The reduction uses only the computable prompt map ϕm and never needs to compute or represent the target vector wa . P

49

We now use the direct implementation to prove the computational lower bound. Here a proper end-to-end learner must output a generator gwb ∈ Fσ (d), rather than an arbitrary predictor for the final-token regression function. The running-time requirement below includes polynomial training time and polynomial time to approximately sample from the output generator to inverse-polynomial precision. Theorem 8.3. Assume the LPN prediction assumption. No randomized algorithm whose sample use, training time, and output approximate-sampling time to inverse-polynomial total-variation precision are polynomial in d, M , 1/ε, and log(1/δ) can, for every d ≥ 1, every horizon M ≤ d, every 0 < ε < 1, and every 0 < δ < 1/2, properly end-to-end learn Fσ (d) at horizon M with squared loss ε and confidence 1 − δ. Proof. Assume, toward a contradiction, that there is an algorithm A with the guarantee ruled out in the theorem statement. Thus A is a proper end-to-end learner for Fσ (d) whose running time, sample use, and output approximate-sampling time to inverse-polynomial precision are polynomial in d, M , 1/ε, and log(1/δ), uniformly over all d, all horizons M ≤ d, and all requested accuracies and confidences. We use A to violate LPN. Fix the LPN dimension m, the unknown parity vector a ∈ {0, 1}m , and the LPN distribution X ∼ Unif({0, 1}m ),

Y = ⟨a, X⟩F2 ⊕ N,

N ∼ Ber(η).

Let ρ ∈ (0, 1/2) be the advantage constant in the LPN assumption, and set ∆ := 1/2 − η. Choose a constant β ∈ (0, 1/2). Choose fixed constants   1 ε0 := c1 β 2 ∆2 −ρ , δ0 := c1 , 2 where c1 > 0 is sufficiently small. Since A has polynomial sample use and Lemma 15 gives d ≤ mC and M = m + 1, there is a constant RA > 0 such that, for all sufficiently large m, the number of samples used by A at accuracy ε0 and confidence 1 − δ0 is at most mRA . Set ζ := e−m . For all sufficiently large m, mRA ζ ≤ δ0 . Apply Lemma 15 with this choice of ζ. Since log(1/ζ) = m, the lemma applies. We obtain d, M = m + 1, a prompt map ϕm , and gwa ∈ Fσ (d) such that (ϕm (x)) − (η + (1 − 2η)⟨a, x⟩F2 ) ≤ ζ qge2e−M wa for every x ∈ {0, 1}m . The map ϕm is computable without knowing a. Also M ≤ d, so the learner A applies. For a fixed x, the LPN label satisfies Pr[Y = 1 | X = x] = η + (1 − 2η)⟨a, x⟩F2 . Therefore the total variation distance between one transformed LPN sample (ϕm (X), Y ) and one genuine end-to-end sample (ϕm (X), ZM ) from gwa is at most ζ. Coupling the samples one by one, the probability that any sample seen by A differs from a genuine end-to-end sample is at most mRA ζ ≤ δ0 . Run A on the transformed LPN samples (ϕm (Xi ), Yi ), with prompt distribution equal to the law of ϕm (X). On genuine end-to-end samples from gwa , the guarantee of A says that, with probability at least 1 − δ0 , it outputs a proper generator gwb ∈ Fσ (d) satisfying  2  e2e−M e2e−M EX∼Unif({0,1}m ) qgwb (ϕm (X)) − qgwa (ϕm (X)) ≤ ε0 . 50

By the coupling above, the same event occurs when A is run on transformed LPN samples with probability at least 1 − 2δ0 . We now turn gwb into a parity predictor. On input x, invoke the output sampler independently K0 times at total-variation accuracy τ := m−2 to obtain approximate M -step trajectories from gwb starting at ϕm (x), where K0 is a sufficiently large constant depending only on η, ρ, and β. Let qb(x) be the empirical average of the final bits, and output h(x) := 1[b q (x) ≥ 1/2]. This is a randomized polynomial-time evaluable classifier because gwb is a proper generator, M = m + 1, K0 is constant, and τ is inverse-polynomial. Let b(x) := ⟨a, x⟩F2 . If qge2e−M (ϕm (x)) − qge2e−M (ϕm (x)) < β∆ wa w b and if the Monte Carlo estimate qb(x) is within β∆ of qge2e−M (ϕm (x)), then h(x) = b(x) for all w b −m sufficiently large m. Indeed, since ζ = e → 0, for all sufficiently large m, ζ < (1 − 2β)∆. The two cases b(x) = 0 and b(x) = 1 then lie on opposite sides of 1/2 after the two β∆ errors. By Markov’s inequality, h i ε0 e2e−M Pr qge2e−M (ϕ (X)) ≥ β∆ ≤ 2 2. (ϕ (X)) − q m m gwa w b X β ∆ Couple each approximate trajectory with an exact trajectory; the probability that any of the K0 pairs differs is at most K0 τ . Hence, by Hoeffding’s inequality, after choosing the constant K0 large enough and then taking m sufficiently large,   1/2 − ρ Pr |b q (X) − qge2e−M (ϕ (X))| ≥ β∆ ≤ , m w b 2 where the probability is over X and the private randomness of the approximate sampler. Choose c1 > 0 so that ε0 /(β 2 ∆2 ) ≤ (1/2 − ρ)/2 and 1 − 2δ0 ≥ 2/3. Then, with probability at least 2/3, the reduction outputs a randomized polynomial-time classifier whose error is at most 1/2 − ρ for the unknown parity. The finitely many smaller values of m can be ignored in the asymptotic LPN contradiction, or hardcoded into the reduction. This contradicts the LPN prediction assumption. Hence, no such learner A exists.

9

Pathologies of other dimensions

This section records two obstructions showing that pseudo-dimension and VC dimension do not provide the right one-step control for stochastic autoregressive iteration.

9.1

Pathology of pseudo-dimension

One might hope to control the pseudo-dimension of the end-to-end probability class F e2e−M directly by the pseudo-dimension of the one-step class F e2e−1 . Pseudo-dimension is not stable under stochastic autoregressive iteration. This is why the results above use the scale-sensitive fat-shattering dimension. Theorem 9.1. For every n ≥ 1, there is a stochastic generator class F such that Pdim(F e2e−1 ) ≤ 1 but Pdim(F e2e−2 ) ≥ n. Consequently, there is no universal upper bound of the form Pdim(F e2e−M ) ≤ CM Pdim(F e2e−1 ).

51

Proof. Let K := 2n , list all subsets of [n] as B1 , . . . , BK , and set D := K + 2, r := 1/D. Choose prompts x1 , . . . , xn so that the sets {xi , xi 0, xi 1}, i ∈ [n], are pairwise disjoint; for instance, take all xi ’s to have the same length and be distinct. Define generators g1 , . . . , gK . For every m ∈ [K], set gm (xi )(1) := 1 − 1/(m + 1) and gm (xi 1)(1) := 0. For each i, set ci,0 := 0, and recursively define ( m+1 1 D + 3D , i ∈ Bm , ci,m := ci,m−1 , i∈ / Bm . Set gm (xi 0)(1) := ci,m , and set gm (s)(1) = 0 on all remaining states. All values lie in [0, 1], since ci,m ≤ (K + 1)/D + 1/(3D) < 1. Let F := {g1 , . . . , gK }. For every state s, the sequence gm (s)(1) is nondecreasing in m. Thus, for any thresholds and any finite set of states, the realized threshold patterns form a chain under inclusion. In particular, no two points can be pseudo-shattered, since the two incomparable patterns (1, 0) and (0, 1) cannot both occur. Hence Pdim(F e2e−1 ) ≤ 1. Now consider the two-step probabilities. Starting from xi , the first bit is 0 with probability 1/(m + 1); if this happens, the second bit has probability ci,m , while if the first bit is 1, the second bit has probability 0. Hence qge2e−2 (xi ) = ci,m /(m + 1). If i ∈ Bm , then m   1 m+1 1 1 e2e−2 qgm (xi ) = + > = r. m+1 D 3D D If i ∈ / Bm , then ci,m = ci,m−1 ≤ m/D + 1/(3D) < (m + 1)/D, and therefore qge2e−2 (xi ) < r. Thus m e2e−2 qgm (xi ) > r if and only if i ∈ Bm . Since B1 , . . . , BK list all subsets of [n], the prompts x1 , . . . , xn are pseudo-shattered by F e2e−2 , using the common threshold r. Therefore Pdim(F e2e−2 ) ≥ n. The second obstruction concerns majority classifiers: even a trivial one-step majority class can become arbitrarily rich after autoregressive iteration.

9.2

VC pathology

In the theorem below, we show that, unlike the case of deterministic functions, for stochastic next-token generators, the VC dimension of the one-step majority class is essentially useless for measuring the richness of the autoregressive majority class. We define this majority class as follows. Majority classification. For g ∈ F , define the end-to-end majority classifier he2e−M (x) := g ⋆ e2e−M e2e−1 Σ 1[qg (x) ≥ 1/2], and for M = 1, define hg (s) := 1[g(s)(1) ≥ 1/2]. For A ⊆ [0, 1] , write maj(A) := {x 7→ 1[f (x) ≥ 1/2] : f ∈ A}. A majority-classification learner has error ε and confidence 1 − δ if, uniformly over P and g⋆ ∈ F, its output b h : Σ⋆ → {0, 1} satisfies Pr [b h(X) ̸= he2e−M (X)] ≤ ε g⋆

X∼P

with probability at least 1 − δ. Theorem 9.2. There is a single stochastic generator class F such that VC(maj(F e2e−1 )) = 0, but for every generation length M ≥ 3, VC(maj(F e2e−M )) = ∞. Moreover, for every M ≥ 3 and every d ≥ 1, even in the CoT model, any distribution-free PAC learner for the M -step end-to-end majority prediction problem with error 1/16 and confidence 2/3 requires more than d/8 samples. Consequently, the same lower bound also holds in the e2e model. 52

Proof. Choose an injective map N : {(ℓ, i) : ℓ ≥ 3, i ∈ N} → N, and set xℓ,i := 1N (ℓ,i) 0. Then the sets {xℓ,i z : z ∈ {0, 1}<ℓ } are pairwise disjoint over all pairs (ℓ, i). Indeed, if xℓ,i z = xℓ′ ,i′ z ′ , then the first 0 occurs in the same position on both sides, so N (ℓ, i) = N (ℓ′ , i′ ). Since N is injective, (ℓ, i) = (ℓ′ , i′ ), and hence also z = z ′ . Thus, every string of the form xℓ,i z, with z ∈ {0, 1}<ℓ , has a unique representation. A generator in the class will be indexed by a sequence A = (Aℓ )ℓ≥3 , where each Aℓ ⊆ N. For each such sequence A, define a stochastic generator gA as follows. For strings s not of the form xℓ,i z with ℓ ≥ 3, i ∈ N, and z ∈ {0, 1}<ℓ , set gA (s)(1) = 0. For strings of the form xℓ,i z, define the transition probabilities as follows. If |z| < ℓ − 1, set ( 0.49, i ∈ Aℓ , gA (xℓ,i z)(1) = 0.01/ℓ, i ∈ / Aℓ . If |z| = ℓ − 1, set gA (xℓ,i z)(1) = 0.9 when z contains at least one 1, and set gA (xℓ,i z)(1) = 0.1 otherwise. Let F := {gA : A = (Aℓ )ℓ≥3 , Aℓ ⊆ N}. First, consider the one-step majority class. For every A, all transition probabilities that depend on A are strictly smaller than 1/2. The only states at which the one-step majority is 1 are the strings xℓ,i z with |z| = ℓ − 1 and z containing at least one 1. This set is independent of A. Hence all generators gA induce the same one-step majority classifier, so maj(F e2e−1 ) contains a single function and VC(maj(F e2e−1 )) = 0. We next show that VC(maj(F e2e−M )) = ∞ for every fixed M ≥ 3. Fix M ≥ 3 and d ≥ 1. We show that maj(F e2e−M ) shatters xM,1 , . . . , xM,d . Let B ⊆ [d] be arbitrary. Choose a sequence A = (Aℓ )ℓ≥3 such that AM ∩ [d] = B. We claim that he2e−M (xM,i ) = 1 if and only if i ∈ B. gA Fix i ∈ [d]. During the first M − 1 steps, each transition outputs 1 with probability p, where p = 0.49 if i ∈ AM , and p = 0.01/M if i ∈ / AM . Let E be the event that at least one 1 appears among the first M − 1 generated bits. Then PrgA (E | X = xM,i ) = 1 − (1 − p)M −1 . Conditioned on E, the length-(M −1) prefix contains at least one 1, so the final transition outputs 1 with probability 0.9. Conditioned on E c , the prefix is 0M −1 , so the final transition outputs 1 with probability 0.1. Therefore, by the law of total probability, Pr(ZM = 1 | X = xM,i ) = 0.9 Pr(E | X = xM,i ) + 0.1 Pr(E c | X = xM,i ) gA

gA

gA

= 0.9 Pr(E | X = xM,i ) + 0.1 1 − Pr(E | X = xM,i ) gA

gA

= 0.1 + 0.8 Pr(E | X = xM,i ) gA
= 0.1 + 0.8 1 − (1 − p)M −1 . If i ∈ AM , then p = 0.49, so since M ≥ 3, we have 1 − (1 − p)M −1 ≥ 1 − 0.512 > 1/2. Thus PrgA (ZM = 1 | X = xM,i ) > 1/2. If i ∈ / AM , then p = 0.01/M , so by the union bound, M −1 1 − (1 − p) ≤ (M − 1)0.01/M < 0.01 < 1/2. Thus PrgA (ZM = 1 | X = xM,i ) < 1/2. Hence he2e−M (x ) = 1 iff i ∈ AM , and therefore iff i ∈ B. Since B ⊆ [d] was arbitrary, maj(F e2e−M ) M,i gA shatters xM,1 , . . . , xM,d . Since d was arbitrary, VC(maj(F e2e−M )) = ∞. It remains to prove the CoT-sample lower bound. Fix M ≥ 3 and d ≥ 1. Let P be the uniform distribution on xM,1 , . . . , xM,d . Choose AM ∩ [d] uniformly at random from all subsets of [d], and fix all other coordinates of A arbitrarily. Consider any learner receiving m ≤ d/8 full CoT samples. Let U be the number of prompts among xM,1 , . . . , xM,d that do not appear in the training sample. For any unobserved prompt xM,i , 53

the training data is independent of whether i ∈ AM . Therefore, even after seeing the full CoT training sample, the learner’s prediction on xM,i has probability at least 1/2 of disagreeing with the true final majority label he2e−M (xM,i ), averaged over the random choice of AM ∩ [d] and the gA learner’s internal randomness. Hence the expected test error is at least E[U ]/(2d). Since E[U ] = d(1 − 1/d)m ≥ d(1 − m/d) ≥ 7d/8, the expected test error, averaged over the random choice of AM ∩ [d] and the training sample, is at least 7/16. Now suppose, toward a contradiction, that there were a CoT PAC learner with m ≤ d/8 samples, error 1/16, and confidence 2/3, for every gA ∈ F. Then the same averaged expected test error would be at most (2/3)(1/16) + (1/3) · 1 = 3/8 < 7/16, a contradiction. Therefore m > d/8. Since e2e samples contain no more information than CoT samples, the same lower bound also holds in the e2e model.

10

The KL Loss and Sampling Trajectories

The objective studied so far targets the final-token probability qge2e−M under squared loss: a single ⋆ scalar per prompt. In this section we change the objective. Instead of predicting one number, we ask when a learner can output a generator gb whose generated distribution over trajectories is close to that of the target g⋆ , so that continuations sampled from gb are statistically faithful to those of g⋆ . This is the relevant goal whenever one cares about sampling plausible continuations, running self-consistency, or scoring likelihoods, rather than predicting only a final answer. The natural yardstick for this sampling objective is not squared loss but Kullback–Leibler (KL) divergence, the quantity minimized by maximum-likelihood (log-loss) training. Our treatment has three parts. First, in Section 10.1, we introduce a KL loss for one-token prediction: the log-loss analogue of the one-step squared risk that has driven the paper so far. Second, in Section 10.2, we recall the chain rule for relative entropy and use it to show that controlling this one-step loss along the target’s trajectories certifies faithful sampling of whole length-T sequences, with the horizon entering only linearly. Third, in Sections 10.3–10.6, we compare the sampling objective to the paper’s squared-loss theory. Which results use the margin assumption. The κ-margin assumption, defined formally in Section 10.3, requires all one-step probabilities to lie in [κ, 1−κ]. It is used only to transfer squaredloss upper bounds to the KL objective. All structural identities, faithful-sampling consequences from one-step KL, e2e impossibility results, and lower bounds are margin-free, with divergences interpreted in [0, ∞]. The only results that require the κ-margin assumption are the upper bridge from squared loss to KL (Lemma 18) and the resulting transfers of squared-loss upper bounds to KL-sampling (Proposition 10.6, Corollary 10.9, Proposition 10.10). Proposition 10.5 shows that this requirement is not merely an artifact of the proofs. For the logistic class, we also isolate a margin-free positive result in total variation (Corollary 10.8); only its KL-valued restatement needs the margin.

10.1

A KL loss for one-token prediction

The base learning problem of Section 1.2 measures the one-step predictor pgb against the truth pg⋆ in squared loss, (pg⋆ (s) − pgb(s))2 . For the sampling objective the right one-step discrepancy is instead the KL divergence between the two Bernoulli next-token laws. We record it as a loss in its own right.

54

One-step KL loss. loss

For a target g⋆ , a hypothesis gb, and a state s ∈ Σ⋆ , define the one-step KL

ℓKL g ; s) := KL Bern(pg⋆ (s)) Bern pgb(s) . g⋆ (b

This is exactly the excess log-loss (cross-entropy) of gb at s: if Y ∼ Bern(pg⋆ (s)) is the next bit, then     ℓKL g ; s) = EY − log pgb(s)Y (1 − pgb(s))1−Y − EY − log pg⋆ (s)Y (1 − pg⋆ (s))1−Y , g⋆ (b so a learner minimizing empirical log-loss (the standard likelihood objective) is minimizing an empirical version of ℓKL . Given a distribution µ over states, the one-step KL risk of gb is   RµKL (b g ) := ES∼µ ℓKL g ; S) . g⋆ (b KL,F By analogy with mF base , let mbase (ε, δ) denote the least n for which n i.i.d. one-step samples (Si , Yi ) with Si ∼ P and Yi | Si ∼ Bern(pg⋆ (Si )) suffice to output gb with RPKL (b g ) ≤ ε with probability at least 1 − δ, uniformly over P and g⋆ ∈ F. Throughout this section, T denotes a generic sampling horizon; when comparing to the M -step final-token learning problems above, take T = M .

Remark 10.1 (Direction of the divergence). The loss ℓKL g ; s) orders its arguments as KL(g⋆ ∥b g ): g⋆ (b “truth relative to model”. This is the population version of the excess cross-entropy of gb, the quantity controlled by maximum-likelihood learners, and it is the correct direction for sampling: a small value certifies that bits drawn from g⋆ are typical under gb. The reverse loss KL(b g ∥g⋆ ) instead controls pgb on states visited by gb; it is an off-policy quantity not implied by the on-policy guarantees below (see Remark 10.11). Remark 10.2 (The margin). Unlike squared loss, which never exceeds 1, the one-step KL loss is unbounded: ℓKL g ; s) → ∞ as pgb(s) → 0 while pg⋆ (s) > 0. This unboundedness is exactly why the g⋆ (b sampling objective can be strictly harder than squared-loss prediction, and it is what the margin assumption of Section 10.3 controls. Everything that does not involve converting a squared-loss guarantee into a KL guarantee — the chain rule, the sampling reduction, the lower bounds, and the e2e impossibility — is insensitive to this unboundedness and holds without a margin. Only the upper-bound transfers are affected, and Proposition 10.5 shows they genuinely fail without it.

10.2

The KL chain rule and sampling (margin-free)

We now connect the one-step KL loss to the trajectory-level sampling objective. Nothing in this subsection uses a margin assumption; all divergences are interpreted as elements of [0, ∞]. Fix a prompt x ∈ Σ⋆ and a horizon T ≥ 1. For a generator g, let PTg,x denote the law of the length-T trajectory (Z1 , . . . , ZT ) generated autoregressively from x by g, as in Section 3. Given a target g⋆ and a hypothesis gb, the sampling error at x and its average under a prompt distribution P are   KLT (g⋆ ∥ gb ; x) := KL PTg⋆ ,x PTgb,x , KLT (g⋆ ∥ gb) := EX∼P [KLT (g⋆ ∥ gb ; X)] . T denote the visitation measure: the law of the state For a generator g and a prompt x, let νg,x S = xZ1 · · · ZΘ−1 obtained by drawing a length-T trajectory Z1 , . . . , ZT from g started at x and an independent time Θ uniform on {1, . . . , T }. When x is itself drawn from P , write µTg,P for the resulting mixture over states. This is exactly the state distribution used in the base-to-CoT reduction in the proof of Theorem 5.1, and it is the distribution against which we measure the one-step KL risk of Section 10.1.

55

The starting point is the exact chain rule for relative entropy [5, Theorem 2.5.3]: for joint laws that factor into a marginal and a sequence of conditionals, the KL divergence decomposes as the KL of the marginals plus the expected KL of the conditionals, the expectation taken under the first (reference) argument. Because both PTg⋆ ,x and PTgb,x factor as products of their one-step Bernoulli conditionals, iterating this identity yields the following. It replaces the coupling and union-bound arguments used for the final-token target (as in Theorem 5.1 and Theorem 7.2) by an identity, and it is the reason the horizon dependence improves from M 2 to M . Lemma 16. For every pair of generators g⋆ , gb, every prompt x, and every T ≥ 1, with both sides interpreted in [0, ∞],

    KLT (g⋆ ∥ gb ; x) = T · ES∼νgT ,x ℓKL g ; S) = T · ES∼νgT ,x KL Bern(pg⋆ (S)) Bern pgb(S) . g⋆ (b ⋆

⋆

Consequently, for every prompt distribution P , by averaging over X ∼ P ,  KL  KLT (g⋆ ∥ gb) = T · ES∼µT ℓg⋆ (b g ; S) = T · RµKL (b g ). T g⋆ ,P

g⋆ ,P

Proof. Write Z<t = (Z1 , . . . , Zt−1 ) and St = xZ<t . Both laws factor over steps as products of the conditional next-token laws Bern(pg⋆ (St )) and Bern(pgb(St )). By the chain rule for relative entropy [5, Theorem 2.5.3], applied inductively over the T steps, T  X  

 EZ<t ∼g⋆ KL Bern(pg⋆ (St )) Bern pgb(St ) , KL PTg⋆ ,x PTgb,x = t=1

where the outer expectation is taken under the true generator g⋆ , since the chain rule expands the divergence along the reference (first) argument. The identity holds in [0, ∞] with no restriction on the probabilities: if any one-step term is +∞ on a set of positive g⋆ -measure, both sides are +∞. Introducing a uniform time Θ ∈ {1, . . . , T } independent of the trajectory turns the sum into T times an expectation over S = SΘ ∼ νgT⋆ ,x , which is the first display. Taking the expectation over X ∼ P and using the definition of µTg⋆ ,P gives the second. The chain rule says that the trajectory-KL objective is exactly T times the one-step KL risk of Section 10.1, evaluated on the target’s own visitation measure. Two consequences follow immediately, both margin-free. First, sampling a longer sequence is no harder than controlling a single step, up to the linear factor T : it suffices to drive the one-step KL risk below ε/T . Second, a small trajectory KL certifies faithful sampling in total variation, which is what makes the generated sequences usable. Proposition 10.3. Fix a prompt distribution P , generators g⋆ , gb, T ≥ 1, and ε > 0, and suppose gb has one-step KL risk RµKL (b g ) ≤ ε/T . Then the length-T sampling error satisfies T g⋆ ,P

KLT (g⋆ ∥ gb) ≤ ε,

  p EX∼P dTV PTg⋆ ,X , PTgb,X ≤ ε/2.

In particular, for any trajectory statistic φ taking values in [0, 1], EX∼P EPT [φ] − EX∼P EPT

g⋆ ,X

g b,X

p [φ] ≤ 2 ε/2.

Note that no margin assumption is used; the statement is a conditional guarantee that applies whenever a learner attains the hypothesized one-step KL risk. 56

Proof. The first inequality is Lemma 16. For the second, Pinsker’s inequality gives pointwise q dTV (PTg⋆ ,x , PTgb,x ) ≤ 12 KLT (g⋆ ∥b g ; x). Taking EX∼P and applying Jensen’s inequality (concavity of the square root) yields q p EX dTV ≤ 12 KLT ≤ ε/2 The last display is the standard bound |EP φ − EQ φ| ≤ 2∥φ∥∞ dTV (P, Q) averaged over X. Thus a learner that attains one-step KL risk ε/T can bep sampled at horizon T to produce trajectories whose entire distribution is within total variation ε/2 of the target’s, so any downstream quantity computed from the samples — a final answer, a self-consistency vote, a likelihood √ score — is reproduced up to O( ε). The horizon enters only through the scale ε/T . This is the structural payoff of the chain rule: KL divergence adds over steps, so one bounds a sum of per-step divergences, whereas the final-token squared-loss argument of Theorem 5.1 bounds the square of a sum of per-step errors and pays an extra factor of M through Cauchy–Schwarz. The remaining question, taken up next, is when a learner can actually attain small one-step KL risk — and this is where the margin enters.

10.3

The margin assumption: one side is free, the other is not

To attain the hypothesis of Proposition 10.3 from the paper’s squared-loss learners we compare Bernoulli KL and squared distance. The comparison is genuinely one-sided: the lower bound on KL by squared distance is unconditional, whereas the upper bound requires a margin. Margin assumption. We say that a stochastic generator class F satisfies the κ-margin assumption for some κ ∈ (0, 1/2) if pg (s) ∈ [κ, 1 − κ] for every g ∈ F and every state s ∈ Σ⋆ . Lemma 17. For all p, q ∈ [0, 1], KL(Bern(p)∥ Bern(q)) ≥ 2(p−q)2 . Consequently, for all generators g⋆ , gb, every P , and every T ≥ 1,   KLT (g⋆ ∥ gb) ≥ 2T · ES∼µT (pg⋆ (S) − pgb(S))2 . g⋆ ,P

Proof. Pinsker’s inequality gives KL(Bern(p)∥ Bern(q)) ≥ 2dTV (Bern(p), Bern(q))2 = 2(p − q)2 , valid for all p, q ∈ [0, 1]. Substitute into the chain rule (Lemma 16) and take expectations. Lemma 18. For every 0 < κ < 1/2, there is a constant Cκ = Θ(1/κ) such that for any generators g⋆ , gb satisfying pg⋆ (s), pgb(s) ∈ [κ, 1 − κ] for every state s ∈ Σ⋆ , and every state s, ℓKL g ; s) ≤ g⋆ (b 2 Cκ (pg⋆ (s) − pgb(s)) , and hence, for every T ≥ 1 and every prompt distribution P ,   KLT (g⋆ ∥ gb) ≤ Cκ T · ES∼µT (pg⋆ (S) − pgb(S))2 . g⋆ ,P

In particular, if gb has one-step squared risk at most η under µTg⋆ ,P , then KLT (g⋆ ∥b g ) ≤ Cκ T η. Note that the margin cannot be dropped: as q → 0 with p fixed, KL(Bern(p)∥ Bern(q)) → ∞ while (p − q)2 stays bounded, so no finite constant works without it. Proof. The second bound of Lemma 3 gives, for p, q ∈ [κ, 1−κ], KL(Bern(p)∥ Bern(q)) ≤ Cκ (p−q)2 with Cκ = Θ(1/κ). Substitute into the chain rule (Lemma 16) and take expectations. The final claim is the displayed limit. 57

Together the two halves say that, under the margin, the one-step KL and squared losses are equivalent up to Θ(1/κ); without it, only the lower half survives. Translated to sample complexity, one direction of the base-learning equivalence is unconditional and the other needs the margin. Corollary 10.4 (Base equivalence: one direction free, one conditional). For every class F, every 0 < ε < 1, and every 0 < δ < 1, KL,F mF base (ε, δ) ≤ mbase (2ε, δ)

(no margin assumption).

If in addition F satisfies the κ-margin assumption, then also F mKL,F base (ε, δ) ≤ mbase (ε/Cκ , δ)

(requires the margin),

with Cκ = Θ(1/κ). Proof. For the first inequality, run a KL base learner to risk 2ε; by Lemma 17 at T = 1 its squared risk is at most 12 · 2ε = ε. For the second, run a squared-loss base learner to risk ε/Cκ and clip its output into [κ, 1 − κ] (which does not increase squared error against a target in that range); by Lemma 18 at T = 1 its KL risk is at most Cκ · ε/Cκ = ε. The next proposition shows that the second, margin-dependent direction is not merely a limitation of our argument. Without a margin, squared-loss control cannot be converted into KL control at the same scale. Proposition 10.5. There is no universal constant C < ∞ such that, for all p, q ∈ (0, 1), KL(Bern(p)∥ Bern(q)) ≤ C(p − q)2 . Moreover, the failure is quantitatively sharp near the boundary: there is a universal constant η0 > 0 such that for every 0 < η ≤ η0 , there exist p, q ∈ (0, 1) such that (p − q)2 ≤ η

but

√ KL(Bern(p)∥ Bern(q)) ≥ c η,

where c > 0 is a universal constant. If hypotheses are allowed to put zero mass on outcomes to which the target assigns positive mass, the KL can even be infinite. Consequently, without a lower margin on the hypothesis probabilities, a squared-loss guarantee at scale η cannot be converted into a KL guarantee at the same scale. Any KL upper bound obtained by first learning one-step probabilities in squared loss and then transferring to trajectory KL must either impose a margin condition, clip the output away from 0 and 1, or lose additional scale-dependent factors. 2

Proof. Take t ∈ (0, 1/2) and set p = t and q = t/2. Then (p − q)2 = t4 . On the other hand, KL(Bern(t)∥ Bern(t/2)) = t log 2 + (1 − t) log As t ↓ 0, (1 − t) log Therefore

1−t . 1 − t/2

1−t t = − + O(t2 ). 1 − t/2 2

  1 KL(Bern(t)∥ Bern(t/2)) = t log 2 − + O(t2 ). 2 58

Since log 2 > 1/2, there is a universal constant c > 0 such that, for all sufficiently small t, KL(Bern(t)∥ Bern(t/2)) ≥ ct. Hence

ct 4c KL(Bern(t)∥ Bern(t/2)) ≥ 2 = →∞ 2 (p − q) t /4 t

as t ↓ 0.

Thus no universal quadratic upper bound can hold without a margin. √ Now set t = 2 η, so that (p − q)2 = t2 /4 = η. The same computation gives √ KL(Bern(p)∥ Bern(q)) ≥ ct = 2c η. After adjusting the universal constant, this proves the quantitative lower bound. Finally, if p > 0 and q = 0, then KL(Bern(p)∥ Bern(0)) = +∞, even though (p − q)2 = p2 can be arbitrarily small. The same one-step example embeds into the autoregressive trajectory setting by taking a one-state, one-step process. Hence a rate-preserving squared-loss-to-KL transfer requires a margin assumption, or else clipping with constants depending on the clipping level. We now record the consequences of the bridge for each of the paper’s one-step bounds, writing g) ≤ ε msamp-CoT (ε, δ) for the least number of CoT trajectories that suffice to output gb with KLT (g⋆ ∥b T with probability at least 1 − δ, and analogously for base and e2e supervision. By Proposition 10.5 these upper bounds must invoke the margin.

10.4

Upper bounds for squared loss transfer to sampling

Base-to-sampling. The base-to-CoT upper bound (Theorem 5.1, part 1) is proved by running a base learner on the state distribution µM g⋆ ,P and controlling the resulting one-step squared risk. The same base learner, targeted at the finer scale dictated by the upper half of the bridge, controls trajectory KL. Proposition 10.6. Assume F satisfies the κ-margin assumption. There is a universal constant C > 0 such that for every M ≥ 1, every 1 ≤ T ≤ M , every 0 < ε < 1, and every 0 < δ < 1,  κε  F msamp-CoT (ε, δ) ≤ m , δ . base T CT Consequently, a learner that observes CoT trajectories (equivalently, one-step samples drawn along g⋆ -trajectories) can output a generator whose length-T samples have averaged KL at most ε, using no more samples than are required to base-learn the one-step class at squared-loss scale Θ(κε/T ). Proof. Given a full CoT trajectory (X, Z1 , . . . , ZM ), form a one-step example (S, Y ) by choosing a uniform time Θ ∈ {1, . . . , T }, setting S = XZ1 · · · ZΘ−1 and Y = ZΘ . As in the proof of Theorem 5.1, the pairs (S, Y ) are i.i.d. with S ∼ µTg⋆ ,P and Y | S ∼ Bern(pg⋆ (S)). Run the base learner at squared-loss scale η := κε/(CT ) to obtain pb with ES∼µT [(pg⋆ (S) − pb(S))2 ] ≤ η g⋆ ,P with probability 1 − δ. If the squared-loss learner outputs pb : Σ⋆ → [0, 1], replace it by pbκ (s) = min{1−κ, max{κ, pb(s)}} and define gbκ (s)(1) = pbκ (s), gbκ (s)(0) = 1− pbκ (s). Since pg⋆ (s) ∈ [κ, 1 − κ], this clipping can only decrease the pointwise squared error. By Lemma 18, KLT (g⋆ ∥b gκ ) ≤ Cκ T η ≤ ε for a suitable universal C absorbing Cκ = Θ(1/κ). 59

Remark 10.7 (Horizon dependence). The scale in Proposition 10.6 is ε/T , linear in the horizon, rather than the ε/M 2 appearing in the final-token bound of Theorem 5.1. The improvement is the structural one already noted after Proposition 10.3: KL chain-rules additively over steps (Lemma 16), so one bounds a sum of per-step divergences directly, whereas the final-token argument bounds the square of a sum and loses a factor of M to Cauchy–Schwarz. Efficient proper CoT sampling for the logistic class. For chain-of-thought supervision this is not merely a re-derivation: the efficient proper learner of Theorem 8.2 already targets the traM jectory law. Its analysis (Lemma 14) controls the squared Hellinger distance h2 (PM w b , Pw⋆ ) of the full trajectory laws via an empirical negative-log-likelihood objective, i.e. empirical trajectory KL. Since dTV ≤ h, this already yields faithful sampling in total variation, with no margin assumption. Corollary 10.8. For every d ≥ 1, M ≥ 1, 0 < ε < 1, 0 < δ < 1/2, prompt distribution P , and target w⋆ ∈ Rd , for the logistic class Fσ (d) with no restriction on the weights, the learner of M ) ≤ ε, with probability at least 1 − δ, using Theorem 8.2 outputs gwb with EX∼P dTV (PM w⋆ ,X , Pw,X b
2 2 e O (d log M + log(1/δ))/ε full CoT trajectories. M ) ≤ ε2 , at the stated sample Proof. The learner controls trajectory Hellinger, EX h2 (PM w⋆ ,X , Pw,X b 2 size by Lemma 14 and the compression argument of p Theorem 8.2 (run at Hellinger accuracy ε ). Since dTV ≤ h pointwise, Jensen gives EX dTV ≤ EX h2 ≤ ε. No boundedness of the one-step probabilities is used.

Only the KL-valued restatement needs the margin. There the margin is used locally, at the one-step log-likelihood level, together with the KL chain rule; we do not use any bound on the full trajectory density ratio. Lemma 19 (Finite energy of generated tail blocks). Fix W > 0, put κ = σ(−dW ), and let a trajectory be generated by some w⋆ ∈ [−W, W ]d . For every t > d, with Yt = (Zt−d , . . . , Zt−1 ) ∈ {0, 1}d , one has vκ E[Yt Yt⊤ ] ⪰ Id , d where vκ > 0 depends only on κ. Proof. Set B = dW = log((1−κ)/κ). Fix a generated token Zs and condition on the prompt and on all the other generated tokens. Flipping Zs changes its own log-likelihood contribution by at most B. It can also change at most the next d log-likelihood contributions. In each of them it changes the logit by at most W , and the Bernoulli logistic log-likelihood of a fixed label is 1-Lipschitz in the logit. Since the margin makes every finite trajectory have positive probability, these conditional probabilities are well-defined, and log

Pr(Zs = 1 | X, (Zr )r̸=s ) ≤ B + dW = 2B. Pr(Zs = 0 | X, (Zr )r̸=s )

Consequently,
Var(Zs | X, (Zr )r̸=s ) ≥ vκ := σ(−2B) 1 − σ(−2B) . Now fix a ∈ Rd , and choose j with |aj | = ∥a∥∞ . Conditional on X and on all generated tokens except Zt−d+j−1 , the random variable ⟨a, Yt ⟩ is an affine function of this token with slope aj . Therefore, vκ E⟨a, Yt ⟩2 ≥ E Var(⟨a, Yt ⟩ | X, (Zr )r̸=t−d+j−1 ) ≥ vκ a2j ≥ ∥a∥22 . d This is the claimed matrix inequality. 60

Lemma 20 (Bounded logistic trajectory likelihood). Fix W > 0, let κ = σ(−dW ), and let P be any prompt distribution. For w ∈ [−W, W ]d , let " T #  X ⟨w,Yt ⟩ L(w) := E log(1 + e ) − Zt ⟨w, Yt ⟩ , t=1

bn where the trajectory is generated by a target w⋆ ∈ [−W, W ]d and Yt = taild (XZ1 · · · Zt−1 ). Let L be the corresponding empirical average over n independent full trajectories. There is Cκ > 0 such that the following holds. For every 0 < η < 1 and 0 < δ < 1/2, if n ≥ Cκ

d2 log(CdT /(ηδ)) + log(1/δ) , η

then every w̄ ∈ [−W, W ]d satisfying b n (w̄) ≤ L

inf

w∈[−W,W ]d

b n (w) + cκ η L

satisfies, with probability at least 1 − δ, KLT (gw⋆ ∥gw̄ ) = L(w̄) − L(w⋆ ) ≤ η. Proof. For one trajectory U = (X, Z1 , . . . , ZT ), write T h i X log(1 + e⟨w,Yt ⟩ ) − Zt ⟨w, Yt ⟩ , ℓw (U ) =

D(w) := L(w) − L(w⋆ ).

t=1

The likelihood identity and the KL chain rule give
D(w) = EX∼P KL PTw⋆ ,X PTw,X . We treat short and long horizons separately. Short horizons: T ≤ 2d. For fixed w, put Qw (U ) = ℓw (U ) − ℓw⋆ (U ). If p, q ∈ [κ, 1 − κ] and Z ∼ Ber(p), then compactness of [κ, 1 − κ]2 and the second-order behavior at p = q imply   Ber(p)(Z) Ber(p)(Z) E log2 ≤ Cκ . ≤ Cκ KL(Ber(p)∥ Ber(q)), log Ber(q)(Z) Ber(q)(Z) Applying the first inequality conditionally at every step, and using ( EQw (U )2 ≤ Cκ T D(w),

PT

2 t=1 at ) ≤ T

PT

2 t=1 at , yields

|Qw (U )| ≤ Cκ T.

Bernstein’s inequality therefore gives, whenever D(w) ≥ 3η/4, ! n  1X η nη  Pr Qw (Ui ) ≤ ≤ exp −cκ . n 4 T i=1

Let N be an ℓ∞ -grid of [−W, W ]d with mesh ρ = η/(32T d). Since the logistic negative log-likelihood is 1-Lipschitz in the logit, |ℓu (U ) − ℓw (U )| ≤ T d∥u − w∥∞ . 61

Moreover, log |N | ≤ d log(Cκ T d/η). A union bound in (10.4) shows that, with probability at least 1 − δ, every u ∈ N with D(u) ≥ 3η/4 has empirical excess larger than η/4. Round w̄ to a nearest u ∈ N . By (10.4) and the approximateminimization assumption, if cκ is sufficiently small, b n (u) − L b n (w⋆ ) ≤ cκ η + T dρ < η/4. L Hence D(u) < 3η/4, and another application of (10.4) gives D(w̄) < η. The displayed sample-size assumption implies the union-bound requirement because T ≤ 2d. Long horizons: T > 2d. For one trajectory define A(U ) := ∇2 ℓw⋆ (U ) =

T X

pt (1 − pt )Yt Yt⊤ ,

H := EA(U ),

t=1

where pt = σ(⟨w⋆ , Yt ⟩). By Lemma 19, H ⪰ κ(1 − κ)

T X t=d+1

T E[Yt Yt⊤ ] ⪰ cκ Id . d

Also 0 ⪯ A(U ) ⪯ (T d/4)Id , and therefore 0 ⪯ H −1/2 A(U )H −1/2 ⪯ Cκ d2 Id . These whitened matrices are independent across trajectories and have expectation Id . The matrix Chernoff inequality [7] therefore implies that, with probability at least 1 − δ/2, n

X 3 1 b ⋆ := 1 H⪯H A(Ui ) ⪯ H, 2 n 2 i=1

provided n ≥ Cκ d2 log(Cd/δ). At w⋆ , the score of trajectory i is Gi := ∇ℓw⋆ (Ui ) =

T X (pi,t − Zi,t )Yi,t . t=1

After ordering the nT transitions trajectory by trajectory, the summands are martingale differences Pn and their predictable quadratic-variation matrix is i=1 A(Ui ). On the event (10.4), for every unit vector a, the scalar martingale obtained by projecting with a⊤ H −1/2 has predictable quadratic variation at most 3n/2. By (10.4), each increment is bounded by √ d ∥H −1/2 Yi,t ∥2 ≤ Cκ √ ≤ Cκ d. T For each vector in a fixed 1/2-net of the unit sphere, apply Freedman’s inequality [6] in its event form, intersected with the upper inequality in (10.4), and then take a union bound over the net. Together with (10.4), this gives b n (w⋆ ) H −1/2 ∇L

2 2

≤ Cκ

62

d + log(1/δ) n

with probability at least 1 − δ. Here the linear term in Freedman’s bound is absorbed because the displayed sample-size assumption implies n ≥ Cκ d(d + log(1/δ)). For every w ∈ [−W, W ]d , all logistic curvatures lie in [κ(1 − κ), 1/4]. Consequently, along the segment from w⋆ to w̄, b n (w) ⪰ 4κ(1 − κ)H b⋆, ∇2 L Put h = w̄ − w⋆ and r = and (10.4)– (10.4) give

√

∇2 L(w) ⪯

1 H. 4κ(1 − κ)

h⊤ Hh. Taylor’s theorem, the approximate-minimization assumption, b n (w⋆ ) aκ r2 ≤ H −1/2 ∇L

2

r + cκ η,

where aκ > 0 depends only on κ. Hence, after choosing the tolerance constant in the lemma sufficiently small, d + log(1/δ) r2 ≤ Cκ + cκ η. n Finally, ∇L(w⋆ ) = 0, and the second inequality in (10.4) gives D(w̄) = L(w̄) − L(w⋆ ) ≤ Cκ r2 ≤ η under the displayed sample-size condition, after increasing Cκ and decreasing cκ if necessary. This proves the claim. Corollary 10.9. Fix a positive rational W . Suppose the logistic class Fσ (d) is restricted to weight vectors with ∥w∥∞ ≤ W , so that the κ-margin assumption holds with κ = σ(−dW ). Then there is a randomized polynomial-time proper learner that, for every d ≥ 1, M ≥ 2, 0 < ε < 1, 0 < δ < 1/2, prompt distribution P , and target w⋆ with ∥w⋆ ∥∞ ≤ W , outputs gwb ∈ Fσ (d) with KLM (gw⋆ ∥ gwb ) ≤ ε with probability at least 1 − δ, using   2 d log M + log(1/δ) e O κ′ ε full CoT trajectories, where κ′ > 0 depends only on κ. Proof. Here “polynomial-time” refers to time polynomial in the total encoded training input, d, M , the bit length of the fixed rational W , and the requested numerical precision. The displayed sample bound itself may be exponential in d when W is fixed, because κ = σ(−dW ); this corollary does not claim polynomial sample complexity uniformly in d. The stronger efficiency convention introduced in the LPN subsection is used only for the learners considered there. Run the same empirical full-trajectory log-likelihood learner as in Theorem 8.2, but optimize over the box [−W, W ]d . Let w̄ be an additive cκ ε minimizer of the empirical trajectory negative log-likelihood on this box. By Lemma 20, after changing constants depending only on κ, KLM (gw⋆ ∥gw̄ ) ≤ ε/2 with probability at least 1 − δ, provided N ≥ Cκ

d2 log(CdM/(εδ)) + log(1/δ) . ε

It remains only to make the output rational while keeping it in the restricted class. Set ρ := 2−⌈log2 (2M d/ε)⌉ and round each coordinate of w̄ to a nearest point of the finite grid
Gρ := ρZ ∩ [−W, W ] ∪ {−W, W }. 63

Denote the rounded vector by w. b Then w b ∈ [−W, W ]d and ∥w b − w̄∥∞ ≤ ρ. For every observed state s and label z, the Bernoulli logistic negative log-likelihood is 1-Lipschitz in the logit, and therefore |− log gwb (s)(z) + log gw̄ (s)(z)| ≤ dρ. Summing over the M steps and taking expectation under the target law gives KLM (gw⋆ ∥gwb ) ≤ KLM (gw⋆ ∥gw̄ ) + M dρ ≤ ε. The grid has polynomial bit complexity, the box-constrained empirical objective is convex, and an additive polynomial-accuracy minimizer can be computed in randomized polynomial time exactly as in Theorem 8.2. Thus the learner is proper and has the stated running time and sample complexity.

General classes via fat-shattering. For KL-sampling, the fat-shattering theory can be used directly at the one-step level. By the KL chain rule, the trajectory objective is exactly T times the one-step KL risk under the true visitation measure. Thus, under a margin assumption, it suffices to learn the one-step probability class in squared loss at scale Θ(κε/T ) under this visitation measure. Applying the standard fat-shattering regression bound directly to the one-step class gives the following sharper bound. Proposition 10.10. Assume F satisfies the κ-margin assumption. There are universal constants c, C > 0 such that for every M ≥ 1, every 1 ≤ T ≤ M , every 0 < ε < 1, every 0 < δ < 1/2, every prompt distribution P , and every target g⋆ ∈ F, a possibly improper learner observing CoT trajectories from g⋆ outputs a generator gb satisfying KLT (g⋆ ∥b g ) ≤ ε with probability at least 1 − δ, using  p  fatF c κε/T logC (CT /(κε)) + log(1/δ) C κε/T CoT trajectories. Proof. Given a full CoT trajectory (X, Z1 , . . . , ZM ), choose a uniform time Θ ∈ {1, . . . , T }, set S = XZ1 · · · ZΘ−1 ,

Y = ZΘ .

For independent input trajectories, the resulting pairs (S, Y ) are i.i.d. and satisfy S ∼ µTg⋆ ,P ,

Y | S ∼ Bern(pg⋆ (S)).

Thus these are valid base samples for the one-step probability class {pg : g ∈ F} under the distribution µTg⋆ ,P . Let Cκ be the constant from Lemma 18, and set η :=

ε . 2Cκ T

Applying Lemma 2 to the one-step probability class gives, with probability at least 1−δ, a predictor pb : Σ⋆ → [0, 1] such that i h ES∼µT (pg⋆ (S) − pb(S))2 ≤ η g⋆ ,P

using

√
fatF c η logC (C/η) + log(1/δ) C η 64

samples. Clip pb to the interval [κ, 1 − κ] and define the generator gb by pgb(s) = min{1 − κ, max{κ, pb(s)}}. Since pg⋆ (s) ∈ [κ, 1 − κ], clipping cannot increase the pointwise squared error. Therefore h
2 i ≤ η. ES∼µT pg⋆ (S) − pgb(S) g⋆ ,P

By Lemma 18, KLT (g⋆ ∥b g ) ≤ Cκ T ES∼µT

g⋆ ,P

h

2 i pg⋆ (S) − pgb(S) ≤ Cκ T η ≤ ε.

Finally, since Cκ = Θ(1/κ), substituting η = ε/(2Cκ T ) = Θ(κε/T ) into the sample bound and absorbing universal constants gives   p fatF c κε/T logC (CT /(κε)) + log(1/δ) . C κε/T This proves the proposition. Remark 10.11 (On-policy versus off-policy). All positive results above control the divergence KL(g⋆ ∥b g ), whose one-step decomposition (Lemma 16) is weighted by the true visitation measure µTg⋆ ,P . This is exactly the distribution from which base and CoT samples are drawn, so the empirical objective is well specified and the guarantees are on-policy. Controlling the reverse divergence KL(b g ∥g⋆ ) (Remark 10.1), or sampling at a horizon T > M beyond the training visitation, requires accuracy of pgb on states that g⋆ visits rarely or not at all; this off-policy control does not follow from one-step closeness under µTg⋆ ,P and is left to future work.

10.5

End-to-end supervision cannot sample (margin-free)

The positive results above use base or CoT supervision. We now show that no analogous statement holds for e2e supervision. End-to-end samples reveal only the final token, hence only the scalar qge2e−M , which does not determine the trajectory law. The obstruction does not rely on a margin; ⋆ we state it under a margin only to stress that it is not caused by degenerate probabilities. Proposition 10.12. Fix any κ ∈ (0, 1/4] and any M ≥ 2. There is a finite stochastic generator class F under the κ-margin assumption, a prompt distribution P , and a universal constant c0 > 0 such that: ,M 1. every g ∈ F induces the same final-token predictor, so in particular mF e2e (ε) = 0 for every ε>0.

2. for every e2e learner, regardless of sample size, there exists g⋆ ∈ F such that   1 Pr KL2 (g⋆ ∥b g ) > c0 ≥ . 2 Since the witnessing class satisfies the margin, dropping the margin assumption only enlarges the family of admissible classes and preserves the impossibility; the margin makes the statement stronger, not weaker. 65

Proof. Fix a single prompt x and let P be the point mass at x. Only the first two transitions from x matter. All other transition probabilities are fixed to 1/2, independently of the class index. Define two generators by gA :

p(x) = 21 ,

p(x1) = 1 − κ,

gB :

p(x) = 12 ,

p(x1) = κ,

p(x0) = κ,

and p(x0) = 1 − κ.

All transition probabilities lie in [κ, 1 − κ], so F := {gA , gB } satisfies the κ-margin assumption. The two-step final-token probabilities coincide: qge2e−2 (x) = 12 (1 − κ) + 21 κ = 12 = 12 κ + 12 (1 − κ) = qge2e−2 (x). A B In fact, a direct check gives qge2e−2 (s) = qge2e−2 (s) = 1/2 for every prompt s; the recursion for q e2e−t A B then gives the same equality for every t ≥ 2. Hence every e2e sample has the same law under the two targets. It remains to show that the trajectory laws are separated. The length-2 trajectory law under gA is P2gA ,x (1, 0) = 12 κ, P2gA ,x (1, 1) = 12 (1 − κ), P2gA ,x (0, 1) = 12 κ,

P2gA ,x (0, 0) = 21 (1 − κ),

whereas under gB the two diagonal probabilities and the two off-diagonal probabilities are swapped: P2gB ,x (1, 1) = 21 κ,

P2gB ,x (1, 0) = 12 (1 − κ),

P2gB ,x (0, 1) = 12 (1 − κ),

P2gB ,x (0, 0) = 12 κ.

Thus both laws have full support. Their total variation distance is dTV (P2gA ,x , P2gB ,x ) = 1 − 2κ ≥ 12 . Fix any possible learner output gb, and let Q = P2gb,x . If both KL(P2gA ,x ∥Q) < η

and

KL(P2gB ,x ∥Q) < η,

then Pinsker’s inequality gives dTV (P2gA ,x , Q) ≤

p η/2,

dTV (P2gB ,x , Q) ≤

p η/2.

By the triangle inequality, dTV (P2gA ,x , P2gB ,x ) ≤ 2

p η/2.

Taking any universal η < 1/8 contradicts dTV (P2gA ,x , P2gB ,x ) ≥ 1/2. Therefore, for every possible output gb, at least one of the two targets satisfies KL2 (g⋆ ∥b g ) = KL(P2g⋆ ,x ∥P2gb,x ) ≥ η. Since the learner has the same output distribution under gA and gB , the two failure probabilities sum to at least 1. Hence at least one of the two targets has failure probability at least 1/2. Taking c0 = η/2 proves the claim. Remark 10.13. The class in Proposition 10.12 is trivial for every squared-loss objective of the paper: base, CoT, and e2e final-token learning all have sample complexity O(1) or 0. The separation is created entirely by the change of objective from the final-token scalar to the trajectory law, and it is information-theoretic rather than a matter of rate: e2e supervision provides no information about the generative path. Thus the ability to sample with small KL is a genuine feature of base and CoT supervision. 66

10.6

Lower bounds for KL-sampling (margin-free)

The upper bounds of Section 10.4 were obtained by instantiating the paper’s squared-loss upper bounds through the (margin-dependent) upper half of the bridge. The lower bounds are different: they cannot be inherited from the squared-loss theory, because the classes that make KL-sampling hard are often trivial for every scalar objective of the paper, and they need no margin, because their hard instances live at transition probabilities near 12 , where KL and squared loss are comparable regardless of any margin. We imitate the Assouad-type technique used for the paper’s lower bounds (Lemma 6), replacing only its final, loss-specific step: instead of “a wrong sign costs squared loss Θ(ε)” we use “a wrong sign costs trajectory-KL Θ(ε)”, quantified through the chain rule of Lemma 16. The key device is a decoupled root: a state at which a hidden sign is placed symmetrically about the final token, so that the induced final-token probability is independent of the sign, while the trajectory law is not. On such a root the scalar targets carry no signal, but the sampling objective does. Lemma 21. Let 0 < ∆ ≤ 1/2. Consider a root r with pgσ (r) = 12 ,

pgσ (r1) = 12 + σ∆,

pgσ (r0) = 21 − σ∆,

σ ∈ {−1, 1},

and pgσ (rz) = 21 for every longer suffix z. Then, for every horizon M ≥ 2, the final-token probability is sign-independent, qge2e−M (r) = 12 , σ whereas the length-2 trajectory laws from r satisfy, for the two signs,   KL P2g+1 ,r P2g−1 ,r ≥ 2∆2 . If one additionally wishes the enclosing class to satisfy the κ-margin assumption, it suffices to take ∆ ≤ 12 − κ; the identities above do not otherwise depend on any margin. Proof. For the final token, conditioning on the first step gives qge2e−2 (r) = 12 ( 21 +σ∆)+ 12 ( 12 −σ∆) = 12 ; σ for M > 2 all subsequent transitions are 12 , which preserves the value 21 . For the trajectory KL, apply the chain rule of Lemma 16 at T = 2: the first step is identical (p = 21 ) under both signs and contributes 0, and the second step contributes 12 KL(Bern( 12 + ∆)∥ Bern( 12 − ∆)) + 12 KL(Bern( 12 − ∆)∥ Bern( 12 + ∆)), since the first bit is 1 or 0 each with probability 12 . By the elementary bound KL(Bern(p)∥ Bern(q)) ≥ 2(p − q)2 (Pinsker together with dTV (Bern(p), Bern(q)) = |p − q|), each of these two Bernoulli KL terms is at least 2(2∆)2 = 8∆2 , so their average is at least 8∆2 ≥ 2∆2 . This gives the stated inequality. Theorem 10.14 (KL-sampling lower bound under CoT supervision; margin-free). There is a universal constant c > 0 such that for every integer K ≥ 1, every horizon M ≥ 2, and every fixed 0 < κ ≤ 1/4, there is ε0 > 0 such that for every 0 < ε ≤ ε0 , there is a finite stochastic generator class F (which may be taken to satisfy the κ-margin assumption, but need not) for which ,M F ,M mF e2e (ε) = mCoT (ε) = 0

(scalar final-token targets),

g ) ≤ ε uniformly over g⋆ ∈ F requires yet any CoT-supervised learner that outputs gb with KL2 (g⋆ ∥b at least cK/ε trajectories.

67

Proof. Choose K distinct roots r1 , . . . , rK of one common length, so their descendant subtrees are disjoint. For each σ ∈ {−1, 1}K , define gσ by placing the decoupled-root gadget of Lemma 21 at rj with sign σj , and set every other one-step probability to 1/2. Let √ ∆ = A ε, where A > 0 is a sufficiently large universal constant. For all sufficiently small ε, we have ∆ ≤ 1/2; if the margin form is desired for a fixed κ ≤ 1/4, take ε small enough that ∆ ≤ 1/2 − κ. Then every one-step probability of every generator lies in [κ, 1 − κ]. We claim that, for every prompt x and every horizon M ≥ 2, qge2e−M (x) = 12 σ independently of σ. A trajectory can visit at most one of the equal-length roots. If it visits no root, all of its transitions have probability 1/2. If it visits a root, then either the final token is generated before the sign-dependent second transition, in which case its probability is 1/2; it is generated at that transition, in which case the two children cancel exactly as in Lemma 21; or it is generated later, in which case all subsequent transitions again have probability 1/2. Thus the scalar final-token class is a singleton, and ,M F ,M mF e2e (ε) = mCoT (ε) = 0

for the scalar final-token targets. For the KL-sampling lower bound, put the prompt distribution uniform on r1 , . . . , rK and draw σ uniformly from {−1, 1}K . Flipping σj changes the trajectory law only when the prompt is rj , an event of probability 1/K. Conditional on that event, the two length-M trajectory laws differ only at the sign-dependent second step. Since both Bernoulli parameters are 21 ± ∆, the adjacent one-sample KL is at most ∆2 A2 ε C =C K K for a universal constant C. Hence, if K n≤c 2 , A ε with c > 0 sufficiently small, the total adjacent KL is below the constant required by Lemma 6. Therefore every estimator of the sign vector leaves a constant fraction of signs wrong with probability greater than 1/3. It remains to convert sign errors into trajectory-KL loss. Fix any output gb. For each root rj , compare the length-2 law generated by gb from rj to the two candidate laws corresponding to σj = +1 and σj = −1, and estimate σj by choosing the nearer candidate in total variation. If this estimate is wrong, then the law generated by gb is closer to the wrong candidate than to the true one. Since the two candidate laws are separated in total variation by at least c∆, the triangle inequality implies that dTV (P2gσ ,rj , P2gb,rj ) ≥ c′ ∆ for a universal constant c′ > 0. Pinsker’s inequality in the form KL(P ∥Q) ≥ 2dTV (P, Q)2 gives KL(P2gσ ,rj ∥P2gb,rj ) ≥ c′′ ∆2 = c′′ A2 ε. Under the uniform prompt distribution, a constant fraction of wrong signs therefore forces KL2 (gσ ∥b g ) ≥ c′′′ A2 ε. 68

Choose the universal constant A large enough that c′′′ A2 > 1. Then the loss exceeds ε. Averaging over the random signs yields a fixed sign vector σ on which the learner fails with probability greater than 1/3. Thus any CoT-supervised learner that achieves KL2 (g⋆ ∥b g ) ≤ ε uniformly requires n ≥ c′

K , ε

after absorbing the fixed factor A2 into the universal constant. Since every scalar sample complexity in Theorem 10.14 is zero, the bound Ω(K/ε) is not a consequence of any squared-loss result in the paper; it is obtained only by imitating the lower-bound technique with the trajectory-KL loss conversion, and it uses no margin. The same construction gives the sharpest form of the e2e impossibility. Theorem 10.15. For the classes F constructed in Theorem 10.14, under the uniform prompt distribution on their roots, there is a universal constant c′0 > 0 such that the e2e observation law is Bern( 12 ) from every root under every sign. Hence the adjacent KL between neighboring e2e data laws is exactly 0, and no e2e-supervised learner—using any finite number of samples—can output g ) ≤ c′0 ε uniformly over g⋆ ∈ F. gb with KL2 (g⋆ ∥b Proof. Use the class and the uniform prompt distribution on the roots r1 , . . . , rK from Theorem 10.14. For every root rj , Lemma 21 gives qge2e−2 (rj ) = 12 σ for both values of σj . Therefore an e2e sample from rj has law Bern( 21 ), independently of σj . Since this holds at every root, the joint law of any finite number of e2e samples is identical for all sign vectors σ ∈ {−1, 1}K . Thus the learner’s output distribution is independent of the hidden sign vector. We now show that the sampling objective still determines the signs up to constant error. Fix a root rj and keep all signs except σj fixed. Let Pj,+ and Pj,− be the two length-2 trajectory laws from rj corresponding to σj = +1 and σj = −1. In the construction of Theorem 10.14, these two laws are √ separated in total variation by at least c∆, where ∆ = A ε. Hence, for any candidate trajectory law Q, at least one of dTV (Pj,+ , Q) and dTV (Pj,− , Q) is at least c∆. By Pinsker’s inequality, for every Q, max{KL(Pj,+ ∥Q), KL(Pj,− ∥Q)} ≥ c′ ∆2 = c′ A2 ε. Condition on any possible learner output gb. For each root rj , at least one of the two signs gives rootwise trajectory KL at least c′ A2 ε. If the hidden sign vector is drawn uniformly from {−1, 1}K , then, conditional on the learner output, these bad sign choices occur independently across j, each with probability at least 1/2. Therefore, with constant probability over the random sign vector, at least a constant fraction of roots contribute at least c′ A2 ε to the rootwise trajectory KL. Under the uniform prompt distribution on the roots, this implies KL2 (gσ ∥b g ) ≥ c′′ A2 ε with constant probability. Choose the universal constant c′0 > 0 smaller than c′′ A2 . Then the guarantee KL2 (gσ ∥b g ) ≤ c′0 ε fails with constant probability under a uniformly random sign vector. Hence there exists a fixed sign vector σ on which the learner fails with probability greater than 1/3. Since the e2e observation law is identical for all signs, this holds for every finite sample size. 69

Remark 10.16. The lower bound of Theorem 10.14 is Ω(K/ε), with no horizon factor. A horizonamplified bound Ω(KT /ε) is obtainable, but only in a supervision model that decouples the observed trajectory length from the evaluation length. Concretely, suppose the hidden sign acts on every step of an unabsorbed chain, so that the length-T trajectory KL of a wrong sign is Θ(T ∆2 ), while the learner observes only length-m0 prefixes (“truncated CoT”). Then the observed adjacent KL is Θ(m0 ∆2 /K) but the objective
at evaluation length T is Θ(T ∆2 ); setting T ∆2 = Θ(ε) gives an Assouad bound of Ω KT /(m0 ε) , i.e. Ω(KT /ε) for m0 = O(1). Under standard CoT supervision one has m0 = T and the horizon cancels, recovering Ω(K/ε). Thus the extra factor T is a statement about a genuinely different (truncated-supervision) model and is not implied by the results above; we record it as a direction rather than a theorem.

11

Discussion and future work

This paper introduces a stochastic PAC model for autoregressive learning that generalizes the deterministic model of Joshi et al. [12]. Our results show that the stochastic setting fundamentally changes the deterministic picture: exact-scale comparisons between the three supervision models base, CoT, e2e can fail in the worst case. Nevertheless, we give nearly tight comparisons with the right accuracy shifts. Finally, we study the class of logistic functions autoregressively and show that natural classes can still be learned much better in the stochastic model compared to the worst-case behavior, and show that for this class the higher quality of CoT samples enables efficient and proper learners, which we rule out for e2e samples. Several questions remain open. First, what is the correct fat-shattering upper bound for CoT √ learning? For e2e learning, we show that ordinary fat-shattering at scale ε/M gives a general upper bound and our lower bounds show that this scale is essentially necessary. For CoT learning, the right scale is less clear: full trajectories reveal intermediate samples, so one may hope for a √ better scale than ε/M or losing the extra dependence on M , though this appears challenging to prove. Second, for the logistic class Fσ (d), can the autoregressive sample complexity be reduced to the e natural d-dimensional rate for arbitrary horizons M ? The base problem has a O(d/ε) sample com2 plexity bound, while our current CoT and e2e upper bounds have a roughly d log M dependence. There are also future directions that are not fully resolved even in the deterministic setting of [12]. One notable example is to generalize the model to the more realistic case where |Σ| > 2, and when the e2e output is not just a single token.

A

Proofs of auxiliary preliminary tools

This appendix gives short proofs of the auxiliary lemmas used in the paper. Proof of Lemma 1. Apply the high-probability Q-aggregation oracle inequality of Lecué and Rigollet [18, Theorem A] to the finite dictionary A, with the uniform prior and squared loss. Since Y and every f (X) lie in [0, 1], the boundedness, Lipschitzness, and strong-convexity assumptions of that theorem hold with universal constants. The resulting aggregate fb ∈ conv(A) satisfies, with probability at least 1 − δ, E[(fb(X) − Y )2 ] ≤ min E[(f (X) − Y )2 ] + C f ∈A

70

log |A| + log(1/δ) . n

For every measurable f : X → [0, 1], the conditional-expectation identity gives E[(f (X) − Y )2 ] = E[(f⋆ (X) − Y )2 ] + E[(f (X) − f⋆ (X))2 ]. Using this identity for fb and for the assumed f ◦ ∈ A yields E[(fb(X) − f⋆ (X))2 ] ≤ α + C

log |A| + log(1/δ) . n

The claimed sample size now follows after increasing the universal constant C. Proof of Lemma 2. For a probability measure Q on X , write dQ (f, g)2 := EQ [(f − g)2 ], and let N2 (u, A, Q) be the corresponding covering number. The entropy theorem of Mendelson and Vershynin [13, Theorem 1], after rescaling from [−1, 1] to [0, 1], gives universal constants c, C > 0 such that for every 0 < u < 1, sup log N2 (u, A, Q) ≤ C fatA (cu) logC (C/u),

(1)

Q

where it is enough to take the supremum over finitely supported Q. We first record the empirical-to-population net consequence needed below. There are universal constants c0 , C0 > 0 such that, for every 0 < r < 1, if m ≥ C0

fatA (c0 r) logC0 (C0 /r) + log(2/δ) , r2

(2)

then, with probability at least 1 − δ/2 over S = (X1 , . . . , Xm ) ∼ P m , dS (f, g) ≤ r/4

=⇒

dP (f, g) ≤ r

for all f, g ∈ A.

(3)

Here and below, the standing pointwise-measurability convention permits working with measurable almost-maximal nets. For completeness, we prove this consequence. Let S ′ be an independent ghost sample of size m. If dP (f, g) > r, then for H = (f − g)2 ∈ [0, 1] one has P H > r2 . The multiplicative Bernstein inequality implies PS ′ H > r2 /2 with conditional probability at least 1/2, after increasing the constant in (2). Hence the probability that (3) fails is at most twice the probability that, for some f, g ∈ A, √ dS (f, g) ≤ r/4, dS ′ (f, g) > r/ 2. (4) Condition on the pooled 2m observations and randomize which member of each pair is assigned to S by independent swaps. Let Q = (PS + PS ′ )/2, and take an L2 (Q) cover of A at radius r/128. By (1), its logarithmic cardinality is at most C fatA (cr) logC (C/r). If (4) holds and u, v are cover points for f, g, respectively, then the triangle inequality on each half of the pooled sample gives dS (u, v) < r/3,

dS ′ (u, v) > 2r/3.

For a fixed pair u, v, put G = (u − v)2 . Under the independent swaps, PS G is the average of independent [0, 1]-valued variables with conditional mean (PS G+PS ′ G)/2. The last display implies that this mean is larger than 2r2 /9 while PS G is less than one half of the mean. Multiplicative 71

Bernstein therefore bounds this event by exp(−cmr2 ). A union bound over all ordered pairs of cover points, followed by (1), proves (3) under (2). √ We now construct the learner. Put r = ε/2 and split the available sample into two independent blocks of equal size m. Using only the inputs in the first block, choose a maximal r/4-separated subset V ⊆ A in the empirical metric dS . Maximality and (3) imply that V is an r-net of A in L2 (P ). Moreover, every r/8 empirical L2 ball contains at most one point of V, so (1) gives log |V| ≤ C fatA (cr) logC (C/r). Since f⋆ ∈ A, on the event above there is v ◦ ∈ V with E[(v ◦ (X)−f⋆ (X))2 ] ≤ r2 = ε/4. Conditionally on the first block, apply Lemma 1 to the finite dictionary V, using the second sample block, confidence 1 − δ/2, and excess accuracy 3ε/4. The resulting aggregate satisfies E[(fb(X) − f⋆ (X))2 ] ≤ ε with probability at least 1 − δ. Combining the two block sizes and absorbing constants and the √ substitution r = ε/2 into the polylogarithmic factor proves the lemma. Proof of Lemma 4. Fix a coordinate r and the remaining signs η ∈ {−1, 1}d−1 . Let P+ and P− be the two laws obtained by setting θr = 1 and θr = −1, respectively, with the other signs equal to η. Any estimate of θr is a test between P+ and P− , so its average error under these two equiprobable alternatives is at p least (1 − dTV (P+ , P− ))/2. Pinsker’s inequality and the KL assumption give dTV (P+ , P− ) ≤ (1/50)/2 = 1/10. Hence the average error in coordinate r, after averaging over η, is at least 9/20. Summing this bound over all coordinates gives expected Hamming error at least 9d/20. Proof of Lemma 6. Take α = 1/50. Lemma 4 gives EdH (b σ , σ) ≥ 9D/20. Let H = dH (b σ , σ) and set τ = 1/16. Since 0 ≤ H ≤ D, 9D D D ≤ EH ≤ Pr[H < D/16] + D Pr[H ≥ D/16] ≤ + D Pr[H ≥ D/16]. 20 16 16 Thus Pr[H ≥ D/16] ≥ 31/80. The lemma follows with ζ = 31/80. Proof of Lemma 7. Let ℓ be the common length of the roots. First fix a prompt x ∈ / R which is not a strict prefix of a root. If x is a strict descendant of a root, then x = ru for some r ∈ R and nonempty suffix u, and condition 3 gives the claim. If x is neither a strict prefix nor a strict descendant of any root, condition 1 with t = M gives the claim. It remains to consider strict prefixes of roots. We prove that, for every strict prefix y of a root and every 1 ≤ t ≤ M , the value qge2e−t (y) depends on θ only through α(θ). The proof is by θ induction on t. For t = 1, this is condition 2, because qge2e−1 (y) = pgθ (y). Assume the claim holds θ for t − 1, where 2 ≤ t ≤ M , and let y be a strict prefix of a root. By conditioning on the first generated bit, qge2e−t (y) = (1 − pgθ (y))qge2e−(t−1) (y0) + pgθ (y)qge2e−(t−1) (y1). θ θ θ The coefficient pgθ (y) depends on θ only through α(θ) by condition 2. Consider each child yc, where e2e−(t−1) c ∈ {0, 1}. If yc is a strict prefix of a root, then qgθ (yc) depends on θ only through α(θ) by the induction hypothesis. If yc is not a root, not a strict prefix of a root, and not a strict descendant e2e−(t−1) of a root, then qgθ (yc) depends on θ only through α(θ) by condition 1. The only remaining possibility is that yc ∈ R. Since y is a strict prefix and all roots have length ℓ, this can happen only when |y| = ℓ − 1. Then y = byc and c = 1, so pgθ (y) = 0. Hence the term involving the root yc 72

is multiplied by zero and contributes nothing. Thus each nonzero term in the displayed recursion depends on θ only through α(θ), so qge2e−t (y) also depends on θ only through α(θ). This completes θ the induction. Taking t = M proves the lemma for strict prefixes, and the proof is complete. Proof of Lemma 3 (Bernoulli KL bounds). For p, q ∈ (0, 1), use log x ≤ x−1. Writing P = Bern(p) and Q = Bern(q),   X X X (P (y) − Q(y))2 P (y) P (y) P (y) log P (y) KL(P ∥Q) = ≤ −1 = . Q(y) Q(y) Q(y) y∈{0,1}

y∈{0,1}

y∈{0,1}

For Bernoulli laws this last expression equals (p − q)2 (p − q)2 ((1 − p) − (1 − q))2 + = . q 1−q q(1 − q) The four displayed bounds follow by substituting the corresponding lower bounds on q(1 − q). Proof of Lemma 5 (From expected to likely Hamming error). Since H < d/16 on the event {H < d/16} and H ≤ d always, EH ≤

d d Pr[H < d/16] + d Pr[H ≥ d/16] ≤ + d Pr[H ≥ d/16]. 16 16

If Pr[H ≥ d/16] ≤ 1/3, then EH ≤ d/16 + d/3 = 19d/48 < 9d/20, contradicting the hypothesis. Hence Pr[H ≥ d/16] > 1/3.

Acknowledgments Idan Mehalel is supported by the European Research Council (ERC) under the European Union’s Horizon 2022 research and innovation program (grant agreement No. 101041711), the Israel Science Foundation (grant number 2258/19), and the Simons Foundation (as part of the Collaboration on the Mathematical and Scientific Foundations of Deep Learning). Ilan Doron-Arad is supported by grant NSF DMS-2031883 and Vannevar Bush Faculty Fellowship ONR-N00014-20-1-2826 (PI Mossel). Elchanan Mossel is partially supported by NSF DMS-2031883, Vannevar Bush Faculty Fellowship ONR-N00014-20-1-2826, MURI N000142412742, and a Simons Investigator Award.

73

References [1] Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM, 44(4):615–631, 1997. [2] Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999. [3] Peter L. Bartlett, Philip M. Long, and Robert C. Williamson. Fat-shattering and the learnability of real-valued functions. Journal of Computer and System Sciences, 52(3):434–452, 1996. [4] Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006. [5] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, 2nd edition, 2006. [6] David A. Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100– 118, 1975. [7] Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389–434, 2012. [8] Edgar N. Gilbert. A comparison of signalling alphabets. Bell System Technical Journal, 31(3):504–522, 1952. [9] Steve Hanneke, Idan Mehalel, and Shay Moran. Sample complexity of autoregressive reasoning: chain-of-thought vs. end-to-end. Preprint, arXiv:2604.12013, 2026. [10] David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78–150, 1992. [11] Yunbei Xu, Yuzhe Yuan, and Ruohan Zhan. Autoregressive learning in joint KL: Sharp oracle bounds and lower bounds. Preprint, arXiv:2605.12316, 2026. [12] 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 Proceedings of the Thirty Eighth Conference on Learning Theory, Proceedings of Machine Learning Research, volume 291, pages 3161–3212, 2025. [13] Shahar Mendelson and Roman Vershynin. Entropy and the combinatorial dimension. Inventiones Mathematicae, 152(1):37–55, 2003. [14] Mark Rudelson and Roman Vershynin. Combinatorics of random processes and sections of convex bodies. Annals of Mathematics, 164(2):603–648, 2006. [15] Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, 2009. [16] Sara A. van de Geer. Empirical Processes in M-Estimation. Cambridge University Press, 2000. [17] Vladimir Vovk. A game of prediction with expert advice. Journal of Computer and System Sciences, 56(2):153–173, 1998. 74

[18] Guillaume Lecué and Philippe Rigollet. Optimal learning with Q-aggregation. The Annals of Statistics, 42(1):211–224, 2014. [19] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM, 50(4):506–519, 2003. [20] Bin Yu. Assouad, Fano, and Le Cam. In David Pollard, Erik Torgersen, and Grace L. Yang, editors, Festschrift for Lucien Le Cam, pages 423–435. Springer, 1997. [21] Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer, 2004. [22] Awni Altabaa, Omar Montasser, and John Lafferty. CoT information: Improved sample complexity under chain-of-thought supervision. In Advances in Neural Information Processing Systems, 2025. [23] Borja Balle, Jorge Castro, and Ricard Gavaldà. Learning probabilistic automata: A study in state distinguishability. Theoretical Computer Science, 473:46–60, 2013. [24] Alexander Clark and Franck Thollard. PAC-learnability of probabilistic deterministic finite state automata. Journal of Machine Learning Research, 5:473–497, 2004. [25] Ilan Doron-Arad, Idan Mehalel, and Elchanan Mossel. A theory of online learning with autoregressive chain-of-thought reasoning. Preprint, arXiv:2605.06819, 2026. [26] Michael Kearns. Efficient noise-tolerant learning from statistical queries. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pages 392–401, 1993. [27] Michael J. Kearns and Robert E. Schapire. Efficient distribution-free learning of probabilistic concepts. Journal of Computer and System Sciences, 48(3):464–497, 1994. [28] Michael J. Kearns and Leslie G. Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. Journal of the ACM, 41(1):67–95, 1994. [29] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Advances in Neural Information Processing Systems, 2022. [30] Chenxiao Yang, Nathan Srebro, and Zhiyuan Li. Tight sample complexity of transformers. In Proceedings of Thirty Ninth Conference on Learning Theory, volume 336 of Proceedings of Machine Learning Research, pages 6887–6923, 2026. [31] 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. [32] Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step. Preprint, arXiv:2305.20050, 2023. [33] William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. Preprint, arXiv:2310.07923, 2023.

75

[34] Maxwell 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. Preprint, arXiv:2112.00114, 2021. [35] Vladimir Vapnik and Akshay Vashist. A new learning paradigm: Learning using privileged information. Neural Networks, 22(5–6):544–557, 2009. [36] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. Preprint, arXiv:2203.11171, 2022. [37] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed 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. [38] Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah D. Goodman. STaR: Bootstrapping reasoning with reasoning. In Advances in Neural Information Processing Systems, 2022. [39] Aad W. van der Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes. Springer, 1996. [40] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, 2017. [41] 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, volume 37, pages 120602–120666, 2024. [42] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, 2020. [43] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, 2022. [44] Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference on Learning Representations, 2020. [45] 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. [46] Alexander Schrijver. Theory of Linear and Integer Programming. Wiley, 1986. 76

[47] P. W. Goldberg and M. R. Jerrum. Bounding the Vapnik–Chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning, 18:131–148, 1995. [48] Nirmit Joshi, Roey Magen, Nathan Srebro, Nikolaos Tsilivis, and Gal Vardi. Learning to think from multiple thinkers. Preprint, arXiv:2604.24737, 2026. [49] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Advances in Neural Information Processing Systems, 2023. [50] Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with processand outcome-based feedback. Preprint, arXiv:2211.14275, 2022. [51] Kaiyue Wen, Huaqing Zhang, Hongzhou Lin, and Jingzhao Zhang. From sparse dependence to sparse attention: Unveiling how chain-of-thought enhances transformer sample efficiency. In International Conference on Learning Representations, 2025. [52] 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 Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 4831–4837, 2025. [53] Eran Malach. Auto-regressive next-token predictors are universal learners. In Proceedings of the 41st International Conference on Machine Learning, PMLR 235:34417–34431, 2024. [54] Zhiyuan Li. The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought. Preprint, arXiv:2607.07423, 2026.

77

Related documents

• A Simple Note on Augmented Autoregressive Distributed Lag Model (A-ARDL)#246258
• Nonlinear Filtering of Asymmetric Stochastic Volatility Models#482372
• Ensemble learning for stochastic volatility jump diffusion models#1068159
• Stochastic Thermodynamics for Autoregressive Generative Models: A Non-Markovian Perspective#1084179
• PAC-Bayesian Reconstruction Guarantees for Time Series Variational Autoencoders#660813