Introduction
Chain-of-Thought (CoT) reasoning has become a central mechanism for improving the reasoning ability of Large Language Models (LLMs). By prompting or training models to generate intermediate steps, CoT substantially improves mathematical and logical reasoning [1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] . Recent reasoning-oriented systems further treat step generation as an explicit training signal [9 , 10 , 11 ] , shifting LLM reasoning from direct pattern matching toward structured stepwise computation [12 ] . Despite this empirical success, a fundamental theoretical question remains open: why can CoT-trained models generalize to complex reasoning tasks that are not directly observed during training?
Existing theoretical studies provide important insights into the expressivity and computational role of CoT. Some works show that CoT can increase the effective depth of Transformers or enable serial computation [13 , 14 , 15 ] , while others analyze task decomposition, in-context learning, or localized reasoning settings [16 , 17 , 18 ] . However, most existing analyses are either qualitative, restricted to narrow or two-step settings, or do not provide explicit generalization bounds for the autoregressive Next-Token Prediction (NTP) regime commonly used by modern large-scale LLMs. As a result,
Preprint. the out-of-distribution (OOD) generalization mechanism of multi-step CoT remains theoretically underexplored.
This paper studies the mechanism of CoT through compositional OOD generalization. We consider a target task requiring a complex multi-step mapping from an input state z 0 z_0 z 0 to a final answer Δ z T \Delta z_T Δ z T , while neither complete reasoning trajectories ( z 0 , Δ z 1 , … , Δ z T − 1 , Δ z T ) (z_0, \Delta z_1, \ldots, \Delta z_{T-1}, \Delta z_T) ( z 0 , Δ z 1 , … , Δ z T − 1 , Δ z T ) nor direct input-output pairs ( z 0 , Δ z T ) (z_0, \Delta z_T) ( z 0 , Δ z T ) are available during training. Thus, the target task’s composition is OOD relative to the observed atomic transitions. We refer to this setting as compositional OOD; § 3.2 separately treats mismatched training and target step distributions (Corollary 4). Instead, the model has access to in-distribution (ID) atomic step data: samples ( z i − 1 , Δ z i ) (z_{i-1}, \Delta z_i) ( z i − 1 , Δ z i ) , where z i − 1 z_{i-1} z i − 1 is the reasoning state before step i i i and Δ z i \Delta z_i Δ z i is the next incremental output. Here, T T T denotes the total number of generation steps: the first T − 1 T-1 T − 1 are intermediate reasoning updates, and Δ z T \Delta z_T Δ z T is the final answer.
Under this view, CoT does not require the model to learn the entire OOD mapping at once from scratch. Instead, it repeatedly applies a shared single-step predictor. At each step, the model reads the current state z i − 1 z_{i-1} z i − 1 , generates Δ z i \Delta z_i Δ z i containing k k k new tokens, and updates the state by appending these tokens while keeping a fixed context length m m m . CoT therefore converts a complex target mapping into a composition of reusable ID atomic transitions (Figure 1 ). This motivates our central question:
Figure 1. CoT as compositional OOD generalization. Left: without CoT, the model must learn a direct mapping from input z 0 z_0 z 0 to final answer Δ z T \Delta z_T Δ z T , whose target distribution may be unavailable during training. With CoT, the same predictor is repeatedly applied to in-distribution step distributions, mapping each state z i − 1 z_{i-1} z i − 1 to update Δ z i \Delta z_i Δ z i . Right: a two-hop translation example solves an unseen English-to-German query by composing learned English-to-French and French-to-German steps.
When a model learns only atomic step transitions, can repeated CoT composition generalize to unseen multi-step OOD tasks, and how does the resulting error scale with the reasoning depth T T T ?
Contributions We answer this question by developing a generalization framework for CoT-based task decomposition. First, we prove that the risk of the complex OOD task can be upper-bounded by the sum of risks over ID sub-tasks, scaled by a coefficient of order O ( k ) O(k) O ( k ) that is independent of T T T . The coefficient results from deterministic argmax decoding together with the bounded sequence loss and the local error floor ( log 2 ) / k (\log2)/k ( log 2 ) / k that a hard-decoding (argmax) error induces. CoT thus avoids fitting the unseen composite mapping directly and composes local transitions at test time.
Second, we derive a Rademacher-complexity bound for the multi-step setting. A naive analysis that treats each reasoning step independently would yield a linear dependence on T T T . In contrast, because CoT applies the same predictor across all steps, we can analyze the combined step-level sample set and obtain a sublinear generalization-gap term scaling as O ( T / n ) O(\sqrt{T/n}) O ( T / n ) , where n n n is the number of training samples per atomic step distribution.
Third, we specialize the analysis to the NTP setting of autoregressive LLMs. We directly analyze the final k k k target tokens of each atomic sequence and take the N = n T N=nT N = n T complete sequences as the sampling units. The resulting final-task risk bound keeps the best in-class step-level risk explicit and adds an estimation term of order O ~ ( k T / n ) \widetilde{O}(k\sqrt{T/n}) O ( k T / n ) . Appendix B.10 shows the T / n \sqrt{T/n} T / n dependence cannot be improved for the sub-task empirical risk minimizer: a construction with k = 1 k=1 k = 1 , in which the per-step errors are coupled through the XOR accumulated over the chain, makes this minimizer incur an excess of Ω ( T / n ) \Omega(\sqrt{T/n}) Ω ( T / n ) when T ≤ n T\le n T ≤ n , and carries that excess through to the final task.
We further validate our theory through controlled experiments. We introduce Atom-Task, a symbolic compositional benchmark involving multi-step sequence operations, to isolate the effect of CoT on OOD compositional generalization. Experiments show that CoT-trained models generalize from shorter or constrained training chains to longer unseen compositions, whereas models trained without intermediate reasoning fail to capture the underlying compositional structure. Ablation results further show that explicitly tracking the current reasoning state is crucial, matching our theoretical requirement that each state z i − 1 z_{i-1} z i − 1 contains sufficient information for the next atomic transition. Additional experiments on GSM8K, a benchmark of grade-school math word problems, support the same conclusion in real-world mathematical reasoning.
Preliminaries
Problem Setting We consider an autoregressive predictor with a context window size of m m m . Let V \mathcal{V} V be a vocabulary (a set of tokens), with n v = ∣ V ∣ n_v = |\mathcal{V}| n v = ∣ V ∣ denoting its size, and let V m \mathcal{V}^m V m denote the set of all token sequences of length m m m formed by tokens from V \mathcal{V} V . The predictor ψ : V m → R n v × k \psi: \mathcal{V}^m \to\mathbb{R}^{n_v \times k} ψ : V m → R n v × k (m ≫ k m \gg k m ≫ k ) maps an input sequence to probability distributions over k k k output positions, and belongs to a hypothesis class Ψ \Psi Ψ . Losses are computed on these soft predictions; for autoregressive generation, discrete tokens are obtained via argmax, denoted hard ( ψ ( ⋅ ) ) ∈ V k \operatorname{hard}(\psi(\cdot)) \in\mathcal{V}^k hard ( ψ ( ⋅ )) ∈ V k .
Under the CoT paradigm, the model does not predict the final answer directly via ψ ( z 0 ) \psi(z_0) ψ ( z 0 ) , but generates a chain of T T T reasoning steps. We write ⋅ ^ \hat{\cdot} ⋅ ^ for model-generated quantities and reserve the unhatted symbol for the ground truth. At step i i i , the incremental output is Δ z ^ i = hard ( ψ ( z ^ i − 1 ) ) \Delta\hat{z}_i = \operatorname{hard}(\psi(\hat{z}_{i-1})) Δ z ^ i = hard ( ψ ( z ^ i − 1 )) , and the state updates by appending these k k k tokens while discarding the first k k k (sliding window):
z ^ i = z ^ i − 1 [ k + 1 : m ] ⊕ Δ z ^ i ( ⊕ denotes sequence concatenation ) , Δ z ^ T = hard ( ψ ( z ^ T − 1 ) ) , \hat{z}_i = \hat{z}_{i-1}[k+1:m] \mathbin{\oplus} \Delta\hat{z}_i \qquad(\mathbin{\oplus}\text{ denotes sequence concatenation}), \qquad\Delta\hat{z}_T = \operatorname{hard}(\psi(\hat{z}_{T-1})), z ^ i = z ^ i − 1 [ k + 1 : m ] ⊕ Δ z ^ i ( ⊕ denotes sequence concatenation ) , Δ z ^ T = hard ( ψ ( z ^ T − 1 )) ,
thus maintaining the sequence length m m m for all intermediate states, with z ^ 0 = z 0 \hat{z}_0 = z_0 z ^ 0 = z 0 ; the true state follows the same recursion with Δ z i \Delta z_i Δ z i in place of Δ z ^ i \Delta\hat{z}_i Δ z ^ i , i.e., z i = z i − 1 [ k + 1 : m ] ⊕ Δ z i z_i = z_{i-1}[k+1:m] \mathbin{\oplus} \Delta z_i z i = z i − 1 [ k + 1 : m ] ⊕ Δ z i .
For a given complex task, any instance ( z 0 , Δ z T ) (z_0, \Delta z_T) ( z 0 , Δ z T ) with z 0 ∈ V m z_0 \in\mathcal{V}^m z 0 ∈ V m and Δ z T ∈ V k \Delta z_T \in\mathcal{V}^k Δ z T ∈ V k satisfies ( z 0 , Δ z T ) ∼ D (z_0, \Delta z_T) \sim\mathcal{D} ( z 0 , Δ z T ) ∼ D . There exists a ground-truth mapping ψ ∗ \psi_* ψ ∗ (not necessarily within Ψ \Psi Ψ ) such that hard ( ψ ∗ ( z i − 1 ) ) = Δ z i \operatorname{hard}(\psi_*(z_{i-1})) = \Delta z_i hard ( ψ ∗ ( z i − 1 )) = Δ z i for all i i i , implying ψ ∗ \psi_* ψ ∗ generates the CoT sequence ( Δ z 1 , … , Δ z T ) (\Delta z_1, \ldots, \Delta z_T) ( Δ z 1 , … , Δ z T ) from z 0 z_0 z 0 to yield the target output Δ z T \Delta z_T Δ z T .
Define the state transition ψ ˉ : V m → V m \bar{\psi} : \mathcal{V}^m \to\mathcal{V}^m ψ ˉ : V m → V m as ψ ˉ ( z ) : = z [ k + 1 : m ] ⊕ hard ( ψ ( z ) ) \bar{\psi}(z) := z[k+1:m] \mathbin{\oplus} \operatorname{hard}(\psi(z)) ψ ˉ ( z ) := z [ k + 1 : m ] ⊕ hard ( ψ ( z )) , representing the input state for the next step (note ψ ˉ \bar{\psi} ψ ˉ uses hard predictions for transitions). To distinguish from ψ \psi ψ , let F ψ : V m → R n v × k F_{\psi} : \mathcal{V}^m \to\mathbb{R}^{n_v \times k} F ψ : V m → R n v × k denote the composite CoT mapping F ψ ( z 0 ) : = ψ ( ψ ˉ ( T − 1 ) ( z 0 ) ) F_{\psi}(z_0) := \psi(\bar{\psi}^{(T-1)}(z_0)) F ψ ( z 0 ) := ψ ( ψ ˉ ( T − 1 ) ( z 0 )) , which encapsulates the T T T -step reasoning process (note F ψ F_{\psi} F ψ applies ψ \psi ψ to the final state, outputting soft predictions for loss computation). Our learning goal is to minimize the population risk:
R D ( F ψ ) = ∫ L ( F ψ ( z 0 ) , Δ z T ) d P ( z 0 , Δ z T ) = ∫ L ( ψ ( ψ ˉ ( T − 1 ) ( z 0 ) ) , Δ z T ) d P ( z 0 , Δ z T ) , R_{\mathcal{D}}(F_{\psi}) = \int\mathcal{L}(F_{\psi}(z_0), \Delta z_T)\,dP(z_0,\Delta z_T) = \int\mathcal{L}(\psi(\bar{\psi}^{(T-1)}(z_0)), \Delta z_T)\,dP(z_0,\Delta z_T), R D ( F ψ ) = ∫ L ( F ψ ( z 0 ) , Δ z T ) d P ( z 0 , Δ z T ) = ∫ L ( ψ ( ψ ˉ ( T − 1 ) ( z 0 )) , Δ z T ) d P ( z 0 , Δ z T ) ,
where P P P is the probability measure associated with D \mathcal{D} D and L : R n v × k × R n v × k → R \mathcal{L} : \mathbb{R}^{n_v \times k} \times\mathbb{R}^{n_v \times k} \to\mathbb{R} L : R n v × k × R n v × k → R is the sequence-level loss function that compares the model’s soft predictions (in R n v × k \mathbb{R}^{n_v \times k} R n v × k ) with the ground-truth output Δ z T \Delta z_T Δ z T (converted from discrete tokens to one-hot vectors in R n v × k \mathbb{R}^{n_v \times k} R n v × k ); the formal definition is provided in Section 3. This aims to identify a ψ ∈ Ψ \psi\in\Psi ψ ∈ Ψ approximating ψ ∗ \psi_* ψ ∗ , thereby generating the CoT sequence from z 0 z_0 z 0 to yield Δ z T \Delta z_T Δ z T .
Notations ψ ˉ ( T ) \bar{\psi}^{(T)} ψ ˉ ( T ) denotes the T T T -fold composition ψ ˉ ∘ ⋯ ∘ ψ ˉ \bar{\psi} \circ\cdots\circ\bar{\psi} ψ ˉ ∘ ⋯ ∘ ψ ˉ (T T T times in total). The final prediction is extracted via ψ ( ψ ˉ ( T − 1 ) ( z 0 ) ) \psi(\bar{\psi}^{(T-1)}(z_0)) ψ ( ψ ˉ ( T − 1 ) ( z 0 )) . For a sequence z z z , z [ a : b ] z[a:b] z [ a : b ] denotes the subsequence from index a a a to b b b (inclusive), and z [ i ] z[i] z [ i ] denotes its i i i -th component (or token). The operator ⊕ \oplus ⊕ denotes the concatenation of two sequences. Other key notations are summarized in Table 4 in Appendix B.
Table 4. Summary of Main Notations
Theoretical Analysis: Task Decomposition for OOD Tasks
We analyze the generalization error of CoT reasoning by decomposing the risk of the complex OOD task into per-step risks (Section 3.1) and then bounding the generalization gap (Section 3.2).
Assumption 1 (Bounded and Lipschitz Loss Function). For a single token represented as a probability vector in R n v \mathbb{R}^{n_v} R n v , the token-level loss function ℓ ( ⋅ , ⋅ ) \ell(\cdot,\cdot) ℓ ( ⋅ , ⋅ ) is defined as the ϵ ℓ \epsilon_\ell ϵ ℓ -clipped cross-entropy loss with a fixed clipping threshold ϵ ℓ ∈ ( 0 , 1 / 4 ) \epsilon_{\ell} \in(0,1/4) ϵ ℓ ∈ ( 0 , 1/4 ) , i.e., ℓ ( p , y ) : = − log max { p y , ϵ ℓ } \ell(p,y):=-\log\max\{p_y,\epsilon_{\ell}\} ℓ ( p , y ) := − log max { p y , ϵ ℓ } , where p p p denotes the predicted probability vector and y y y the ground-truth token. It is upper-bounded by B ℓ B_{\ell} B ℓ , i.e., ℓ ( p , y ) ≤ B ℓ \ell(p,y)\le B_{\ell} ℓ ( p , y ) ≤ B ℓ , and is G ℓ G_{\ell} G ℓ -Lipschitz continuous with respect to the ℓ 2 \ell_2 ℓ 2 -norm of the predicted probability vector, i.e., ∣ ℓ ( y ^ 1 , y ) − ℓ ( y ^ 2 , y ) ∣ ≤ G ℓ ∥ y ^ 1 − y ^ 2 ∥ 2 |\ell(\hat{y}_1,y)-\ell(\hat{y}_2,y)|\le G_{\ell}\lVert\hat{y}_1-\hat{y}_2\rVert_2 ∣ ℓ ( y ^ 1 , y ) − ℓ ( y ^ 2 , y ) ∣ ≤ G ℓ ∥ y ^ 1 − y ^ 2 ∥ 2 for all probability vectors y ^ 1 , y ^ 2 ∈ Δ n v − 1 : = { p ∈ [ 0 , 1 ] n v : ∑ a = 1 n v p a = 1 } \hat{y}_1,\hat{y}_2\in\Delta_{n_v-1}:=\{p\in[0,1]^{n_v}:\sum_{a=1}^{n_v}p_a=1\} y ^ 1 , y ^ 2 ∈ Δ n v − 1 := { p ∈ [ 0 , 1 ] n v : ∑ a = 1 n v p a = 1 } and ground-truth token y y y . Without loss of generality, assume G ℓ ≥ 1 G_{\ell}\ge1 G ℓ ≥ 1 .
Remark 1. Assumption 1 is standard in learning theory [19 , 20 , 21 , 22 ] . Both requirements follow directly from clipping, which lower-bounds the probability assigned to the true token by ϵ ℓ \epsilon_{\ell} ϵ ℓ ; both conditions are therefore satisfied by construction.
Definition 1 (Sequence Loss). For a predicted probability distribution y ^ ∈ R n v × k \hat{y}\in\mathbb{R}^{n_v\times k} y ^ ∈ R n v × k and a ground-truth token sequence Δ z \Delta z Δ z (represented as one-hot vectors in R n v × k \mathbb{R}^{n_v\times k} R n v × k ), the sequence loss is defined as the average of the token-wise loss ℓ \ell ℓ over these k k k generated tokens, where y ^ j \hat{y}_j y ^ j denotes the probability vector at output position j j j (the j j j -th column of y ^ \hat{y} y ^ ) [23 ] :
L ( y ^ , Δ z ) : = 1 k ∑ j = 1 k ℓ ( y ^ j , ( Δ z ) j ) \mathcal{L}(\hat{y},\Delta z):=\frac{1}{k}\sum_{j=1}^{k}\ell(\hat{y}_j,(\Delta z)_j) L ( y ^ , Δ z ) := k 1 j = 1 ∑ k ℓ ( y ^ j , ( Δ z ) j )
Generalization Error Decomposition via CoT
For ( z 0 , Δ z T ) ∼ D (z_0,\Delta z_T)\sim D ( z 0 , Δ z T ) ∼ D , let D ′ D' D ′ denote the joint distribution over the reasoning sequence ( z 0 , Δ z 1 , … , Δ z T ) (z_0,\Delta z_1,\ldots,\Delta z_T) ( z 0 , Δ z 1 , … , Δ z T ) , and let D i D_i D i denote the marginal law of ( z i − 1 , Δ z i ) (z_{i-1},\Delta z_i) ( z i − 1 , Δ z i ) under D ′ D' D ′ (a state on the ground-truth trajectory is called an oracle state). Lemma 7 in Appendix B.2 shows that the step-level loss of an erroneous hard-decoded block is at least ( log 2 ) / k (\log2)/k ( log 2 ) / k , a floor that is independent of the reasoning depth T T T .
Theorem 1 (Generalization Error Decomposition). Under Assumption 1, we have:
R D ( F ψ ) ≤ B ℓ k log 2 ∑ i = 1 T ∫ L ( ψ ( z i − 1 ) , Δ z i ) d D i ( z i − 1 , Δ z i ) . R_D(F_{\psi})\le\frac{B_{\ell}k}{\log2}\sum_{i=1}^{T}\int\mathcal{L}(\psi(z_{i-1}),\Delta z_i)dD_i(z_{i-1},\Delta z_i). R D ( F ψ ) ≤ log 2 B ℓ k i = 1 ∑ T ∫ L ( ψ ( z i − 1 ) , Δ z i ) d D i ( z i − 1 , Δ z i ) . where ( log 2 ) / k (\log2)/k ( log 2 ) / k is the local error floor of Lemma 7.
Remark 2 (Implications of Theorem 1). Theorem 1 reveals the fundamental principle underlying CoT’s OOD generalization: the generalization risk of a complex OOD task is dominated by the sum of per-step in-distribution risks, scaled by an O ( k ) O(k) O ( k ) coefficient that is independent of T T T . This is qualitatively different from direct OOD learning, where one would attempt to bound the risk of the composite mapping F ψ F_{\psi} F ψ directly—without decomposition, not only is the mapping F ψ F_{\psi} F ψ inherently more complex, but more critically, we lack the direct samples ( z 0 , Δ z T ) ∼ D (z_0,\Delta z_T)\sim D ( z 0 , Δ z T ) ∼ D , so the composite risk cannot be estimated from target data alone.
Theorem 1 bounds the target risk by the summed step-level risks, and the additive dependence on those risks is unavoidable in general. A step-level error can propagate along the chain through the state update rather than being averaged out, so the per-step risks accumulate in the final answer.
Remark 3 (Tightness of Theorem 1). Appendix B.9 constructs, for k = 1 k=1 k = 1 , a binary sliding-window task with a shared single-step predictor ψ \psi ψ and a bounded sequence loss, for which
R D ( F ψ ) = Ω ( ∑ i = 1 T R D i ( ψ ) ) . R_D(F_{\psi})=\Omega\left(\sum_{i=1}^{T}R_{D_i}(\psi)\right). R D ( F ψ ) = Ω ( i = 1 ∑ T R D i ( ψ ) ) .
Consequently, the additive form of Theorem 1 is tight up to its depth-independent coefficient: when every step-level error reaches the final answer, the linear growth in T T T of the summed risk is attained, and no argument that charges only per-step risks can remove it.
Bounds via Rademacher Complexity
Let S i = { ( z i − 1 ( j ) , Δ z i ( j ) ) } j = 1 n S_i=\{(z_{i-1}^{(j)},\Delta z_i^{(j)})\}_{j=1}^{n} S i = {( z i − 1 ( j ) , Δ z i ( j ) ) } j = 1 n be n n n independent atomic pairs drawn from D i D_i D i , with S 0 = ⋃ i = 1 T S i S_0=\bigcup_{i=1}^{T}S_i S 0 = ⋃ i = 1 T S i . All n T nT n T atomic examples are mutually independent, with the n n n examples in S i S_i S i drawn from D i D_i D i ; each comes from some source realizing the same step-level skill distribution and need not lie on a common trajectory. Define f ψ ( z , Δ z ) : = L ( ψ ( z ) , Δ z ) f_{\psi}(z,\Delta z):=\mathcal{L}(\psi(z),\Delta z) f ψ ( z , Δ z ) := L ( ψ ( z ) , Δ z ) and F : = { f ψ : ψ ∈ Ψ } \mathcal{F}:=\{f_{\psi}: \psi\in\Psi\} F := { f ψ : ψ ∈ Ψ } . To bound the generalization gap we use Rademacher complexity, writing R D i ( ψ ) R_{D_i}(\psi) R D i ( ψ ) and R ^ S i ( ψ ) \widehat{R}_{S_i}(\psi) R S i ( ψ ) for the associated population and empirical risks (Appendix B.4). Applying Rademacher bounds to the T T T steps separately makes the resulting gap grow linearly in T T T . Since the same learner ψ \psi ψ processes samples from all $T distributions, analyzing the combined set S 0 S_0 S 0 under a uniform capacity control makes both the deviation term and the complexity term (from ∑ i = 1 T R ^ S i ( F ) \sum_{i=1}^{T} \widehat{\mathcal{R}}_{S_i}(\mathcal{F}) ∑ i = 1 T R S i ( F ) to T R ^ S 0 ( F ) T\widehat{\mathcal{R}}_{S_0}(\mathcal{F}) T R S 0 ( F ) ) improve from O ( T ) O(T) O ( T ) to O ( T ) O(\sqrt{T}) O ( T ) —analogous to multi-task learning, where sharing a hypothesis across related tasks improves generalization [24 ] . Extending the classical symmetrization lemma [19 ] to multiple distributions (Lemma 8 in Appendix § 10 .§ 4 ) gives:
Theorem 2 (Rademacher Complexity Bound). For any δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , with probability at least 1 − δ 1-\delta 1 − δ , uniformly over ψ ∈ Ψ \psi\in\Psi ψ ∈ Ψ , we have:
∣ ∑ i = 1 T ( R D i ( ψ ) − R ^ S i ( ψ ) ) ∣ ≤ 2 T R ^ S 0 ( F ) + 3 B ℓ 2 T log ( 4 / δ ) n \left|\sum_{i=1}^{T}\left(R_{D_i}(\psi)-\widehat{R}_{S_i}(\psi)\right)\right| \leq2T\widehat{\mathcal{R}}_{S_0}(\mathcal{F})+3B_{\ell}\sqrt{\frac{2T\log(4/\delta)}{n}} i = 1 ∑ T ( R D i ( ψ ) − R S i ( ψ ) ) ≤ 2 T R S 0 ( F ) + 3 B ℓ n 2 T log ( 4/ δ ) where R ^ S 0 ( ⋅ ) \widehat{\mathcal{R}}_{S_0}(\cdot) R S 0 ( ⋅ ) denotes the empirical Rademacher complexity on S 0 S_0 S 0 , F = L ∘ Ψ \mathcal{F}=\mathcal{L}\circ\Psi F = L ∘ Ψ is the induced bounded loss class, and B ℓ B_{\ell} B ℓ is the bound of the sequence loss L \mathcal{L} L according to Assumption 1.
The following corollary records the resulting guarantee, first for a fixed predictor and then, after the ERM comparison, for the empirical risk minimizer; both proofs are in Appendix § 10 .§ 5 .
Corollary 3 (Generalization Bound for Complex OOD Tasks). Under Assumption 1, with probability at least 1 − δ 1-\delta 1 − δ , for every ψ ∈ Ψ \psi\in\Psi ψ ∈ Ψ ,
R D ( F ψ ) ≤ B ℓ κ log 2 [ ∑ i = 1 T R ^ S i ( ψ ) + 2 T R ^ S 0 ( F ) + 3 B ℓ 2 T log ( 4 / δ ) n ] . R_D(F_{\psi}) \leq\frac{B_{\ell}\kappa}{\log2}\left[\sum_{i=1}^{T}\widehat{R}_{S_i}(\psi)+2T\widehat{\mathcal{R}}_{S_0}(\mathcal{F})+3B_{\ell}\sqrt{\frac{2T\log(4/\delta)}{n}}\right]. R D ( F ψ ) ≤ log 2 B ℓ κ [ i = 1 ∑ T R S i ( ψ ) + 2 T R S 0 ( F ) + 3 B ℓ n 2 T log ( 4/ δ ) ] . and for the sub-task ERM ψ ^ ∈ arg min ψ ∈ Ψ ∑ i = 1 T R ^ S i ( ψ ) \widehat{\psi}\in\arg\min_{\psi\in\Psi}\sum_{i=1}^{T}\widehat{R}_{S_i}(\psi) ψ ∈ arg min ψ ∈ Ψ ∑ i = 1 T R S i ( ψ ) , with ψ ⋆ ∈ arg min ψ ∈ Ψ ∑ i = 1 T R D i ( ψ ) \psi^\star\in\arg\min_{\psi\in\Psi}\sum_{i=1}^{T}R_{D_i}(\psi) ψ ⋆ ∈ arg min ψ ∈ Ψ ∑ i = 1 T R D i ( ψ ) ,
R D ( F ψ ^ ) ≤ B ℓ κ log 2 [ ∑ i = 1 T R D i ( ψ ⋆ ) + 4 T R ^ S 0 ( F ) + 6 B ℓ 2 T log ( 4 / δ ) n ] . R_D(F_{\widehat{\psi}}) \leq\frac{B_{\ell}\kappa}{\log2}\left[\sum_{i=1}^{T}R_{D_i}(\psi^\star)+4T\widehat{\mathcal{R}}_{S_0}(\mathcal{F})+6B_{\ell}\sqrt{\frac{2T\log(4/\delta)}{n}}\right]. R D ( F ψ ) ≤ log 2 B ℓ κ [ i = 1 ∑ T R D i ( ψ ⋆ ) + 4 T R S 0 ( F ) + 6 B ℓ n 2 T log ( 4/ δ ) ] .
The preceding analysis addresses compositional OOD generalization: the target task is out of distribution, whereas the step-level distributions D i D_i D i are not. When the step-level data are themselves drawn from shifted distributions Q i Q_i Q i , the decomposition carries over with one additional per-step term.
Corollary 4 (Atomic Distribution Shift). Let Q i Q_i Q i be the training distribution at step i i i , let D i D_i D i be the corresponding target oracle-state marginal, and let S i ∼ Q i S_i\sim Q_i S i ∼ Q i . Define
disc F ( D i , Q i ) : = sup ψ ∈ Ψ ∣ R D i ( ψ ) − R Q i ( ψ ) ∣ . \operatorname{disc}_{\mathcal{F}}(D_i,Q_i):=\sup_{\psi\in\Psi}\left|R_{D_i}(\psi)-R_{Q_i}(\psi)\right|. disc F ( D i , Q i ) := ψ ∈ Ψ sup ∣ R D i ( ψ ) − R Q i ( ψ ) ∣ . Then, with probability at least 1 − δ 1-\delta 1 − δ , for every ψ ∈ Ψ \psi\in\Psi ψ ∈ Ψ ,
R D ( F ψ ) ≤ B ℓ κ log 2 [ ∑ i = 1 T R ^ S i ( ψ ) + 2 T R ^ S 0 ( F ) + 3 B ℓ 2 T log ( 4 / δ ) n + ∑ i = 1 T disc F ( D i , Q i ) ] , R_D(F_{\psi})\leq\frac{B_{\ell}\kappa}{\log2}\left[\sum_{i=1}^{T}\widehat{R}_{S_i}(\psi)+2T\widehat{\mathcal{R}}_{S_0}(\mathcal{F})+3B_{\ell}\sqrt{\frac{2T\log(4/\delta)}{n}}+\sum_{i=1}^{T}\operatorname{disc}_{\mathcal{F}}(D_i,Q_i)\right], R D ( F ψ ) ≤ log 2 B ℓ κ [ i = 1 ∑ T R S i ( ψ ) + 2 T R S 0 ( F ) + 3 B ℓ n 2 T log ( 4/ δ ) + i = 1 ∑ T disc F ( D i , Q i ) ] , and for the sub-task ERM ψ ^ ∈ arg min ψ ∈ Ψ ∑ i = 1 T R ^ S i ( ψ ) \widehat{\psi}\in\arg\min_{\psi\in\Psi}\sum_{i=1}^{T}\widehat{R}_{S_i}(\psi) ψ ∈ arg min ψ ∈ Ψ ∑ i = 1 T R S i ( ψ ) , with ψ ⋆ ∈ arg min ψ ∈ Ψ ∑ i = 1 T R D i ( ψ ) \psi^\star\in\arg\min_{\psi\in\Psi}\sum_{i=1}^{T}R_{D_i}(\psi) ψ ⋆ ∈ arg min ψ ∈ Ψ ∑ i = 1 T R D i ( ψ ) ,
R D ( F ψ ^ ) ≤ B ℓ κ log 2 [ ∑ i = 1 T R D i ( ψ ⋆ ) + 4 T R ^ S 0 ( F ) + 6 B ℓ 2 T log ( 4 / δ ) n + 2 ∑ i = 1 T disc F ( D i , Q i ) ] . R_D(F_{\widehat{\psi}})\leq\frac{B_{\ell}\kappa}{\log2}\left[\sum_{i=1}^{T}R_{D_i}(\psi^\star)+4T\widehat{\mathcal{R}}_{S_0}(\mathcal{F})+6B_{\ell}\sqrt{\frac{2T\log(4/\delta)}{n}}+2\sum_{i=1}^{T}\operatorname{disc}_{\mathcal{F}}(D_i,Q_i)\right]. R D ( F ψ ) ≤ log 2 B ℓ κ [ i = 1 ∑ T R D i ( ψ ⋆ ) + 4 T R S 0 ( F ) + 6 B ℓ n 2 T log ( 4/ δ ) + 2 i = 1 ∑ T disc F ( D i , Q i ) ] .
The proof is given in Appendix § 10 .§ 6 . The corollary thus controls shifts between training and target step distributions; the drift of the model’s own generated trajectory (its rollout) is handled only through the hard-decoding reduction and is not itself a distributional guarantee.
Specific Analysis: Results in the Next-Token Prediction Setting
In the preceding analysis the OOD generalization error of complex compositional tasks is upper-bounded by a sum of per-step in-distribution risks, with the gap governed by the Rademacher complexity of the shared hypothesis class. We now specialize this decomposition to the Next-Token Prediction (NTP) pretraining paradigm [23 ] —the standard training regime for LLMs—and derive a target-token bound with explicit depth, sample-size, and decoder-capacity dependence. Relative to the general analysis of § 3.2 the additional ingredients are (i) a reduction from the final-task risk of free-running generation, in which the model conditions on its own outputs, to target-token risks under teacher forcing, in which every prefix is taken from the ground truth (Lemma 10 , Appendix § 10 .§ 7 ) and (ii) an explicit evaluation of the complexity term for the decoder (Appendix § 9 .§ 2 ); the ERM comparison is the one already used in Corollary 3.
Problem Formulation
The model is a composition L M = g ∘ h \mathrm{LM}=g\circ h LM = g ∘ h (representation learner h h h and token predictor g g g ). Here, the abstract single-step mapping ψ \psi ψ is instantiated by the block predictor ψ g , h \psi_{g,h} ψ g , h induced by k k k successive next-token predictions via g ∘ h g\circ h g ∘ h , and F ψ g , h F_{\psi_{g,h}} F ψ g , h denotes the resulting T T T -step final predictor. For step i = 1 , … , T i=1,\ldots,T i = 1 , … , T , let S i = { X i j } j = 1 n S_i=\{X_{ij}\}_{j=1}^{n} S i = { X ij } j = 1 n , where each X i j = ( t i j , 1 , … , t i j , m ) X_{ij}=(t_{ij,1},\ldots,t_{ij,m}) X ij = ( t ij , 1 , … , t ij , m ) is a complete sequence. We denote the teacher-forced context from X i j X_{ij} X ij before token t t t by X i j , < t X_{ij,<t} X ij , < t and set N = n T N=nT N = n T . Here and in Appendix A, m m m denotes the complete-record length: an ( m − k ) (m-k) ( m − k ) -token state followed by k k k target tokens. Thus the general setup of Section 2 is instantiated with state length m − k m-k m − k . Before each block, both oracle and generated histories retain their most recent m − k m-k m − k tokens; within the block, the corresponding true or generated prefixes are appended autoregressively. The oracle record is therefore X = z i − 1 ⊕ Δ z i X=z_{i-1}\oplus\Delta z_i X = z i − 1 ⊕ Δ z i , and D i D_i D i also denotes its induced distribution. This length convention leaves the general risk bounds unchanged.
For a complete sequence X = ( t 1 , … , t m ) X=(t_1,\ldots,t_m) X = ( t 1 , … , t m ) and its prefix X < t = ( t 1 , … , t t − 1 ) X_{<t}=(t_1,\ldots,t_{t-1}) X < t = ( t 1 , … , t t − 1 ) , define the target-token loss, with g g g applied to the hidden state at the last position of its argument:
q ψ g , h ( X ) : = 1 k ∑ t = m − k + 1 m ℓ ( g ( h ( X < t ) ) , t t ) , (1) q_{\psi_{g,h}}(X):=\frac{1}{k}\sum_{t=m-k+1}^{m}\ell\bigl(g(h(X_{<t})),t_t\bigr), \tag*{(1)} q ψ g , h ( X ) := k 1 t = m − k + 1 ∑ m ℓ ( g ( h ( X < t )) , t t ) , (1)
and let Q k = { q ψ g , h : g ∈ G , h ∈ H } Q_k=\{q_{\psi_{g,h}}:g\in\mathcal{G},\,h\in\mathcal{H}\} Q k = { q ψ g , h : g ∈ G , h ∈ H } , where G , H \mathcal{G},\mathcal{H} G , H are the classes of the token predictor and the representation learner. For S i = { X i j } j = 1 n S_i=\{X_{ij}\}_{j=1}^{n} S i = { X ij } j = 1 n , define
R D i k ( ψ g , h ) : = E X ∼ D i [ q ψ g , h ( X ) ] , R ^ S i k ( ψ g , h ) : = 1 n ∑ j = 1 n q ψ g , h ( X i j ) . R_{D_i}^{k}(\psi_{g,h}):=\mathbb{E}_{X\sim D_i}[q_{\psi_{g,h}}(X)],\qquad\widehat{R}_{S_i}^{k}(\psi_{g,h}):=\frac{1}{n}\sum_{j=1}^{n}q_{\psi_{g,h}}(X_{ij}). R D i k ( ψ g , h ) := E X ∼ D i [ q ψ g , h ( X )] , R S i k ( ψ g , h ) := n 1 j = 1 ∑ n q ψ g , h ( X ij ) .
The N = n T N=nT N = n T complete sequences are the independent sampling units; tokens and prefixes within each sequence may be dependent. We abbreviate R i k : = R D i k R_i^k:=R_{D_i}^k R i k := R D i k and R ^ i k : = R ^ S i k \widehat{R}_i^k:=\widehat{R}_{S_i}^k R i k := R S i k .
Remark 6 (Teacher-Forced NTP and Free-Running Generation). The target-token loss in Eq. (1) is teacher-forced : it uses the true within-step prefixes, whereas F ψ g , h F_{\psi_{g,h}} F ψ g , h runs freely and conditions on its own generated tokens. These block losses need not coincide. Lemma 10 in Appendix § 10 .§ 7 extends the first-error argument of Theorem 1 to individual tokens and gives R D ( F ψ g , h ) ≤ B ε k log 2 ∑ i = 1 T R D i k ( ψ g , h ) R_D(F_{\psi_{g,h}})\le\frac{B\varepsilon k}{\log2}\sum_{i=1}^{T}R_{D_i}^k(\psi_{g,h}) R D ( F ψ g , h ) ≤ l o g 2 B ε k ∑ i = 1 T R D i k ( ψ g , h ) with the same coefficient B ε k / log 2 = O ( k ) B\varepsilon k/\log2=O(k) B ε k / log 2 = O ( k ) .
In this setting we write ( g ^ , h ^ ) (\widehat{g},\widehat{h}) ( g , h ) for the minimizer of ∑ i R ^ i k ( ψ g , h ) \sum_i\widehat{R}_i^k(\psi_{g,h}) ∑ i R i k ( ψ g , h ) and ( g ⋆ , h ⋆ ) (g^\star,h^\star) ( g ⋆ , h ⋆ ) for the minimizer of ∑ i R D i k ( ψ g , h ) \sum_iR_{D_i}^k(\psi_{g,h}) ∑ i R D i k ( ψ g , h ) , with ψ ^ : = ψ g ^ , h ^ \widehat{\psi}:=\psi_{\widehat{g},\widehat{h}} ψ := ψ g , h and ψ ⋆ : = ψ g ⋆ , h ⋆ \psi^\star:=\psi_{g^\star,h^\star} ψ ⋆ := ψ g ⋆ , h ⋆ ; the resulting target-token excess is the NTP analogue of the atomic excess of § 3.2 .
Main Theoretical Results
Let R ^ S 0 ( Q k ) \widehat{\mathfrak{R}}_{S_0}(Q_k) R S 0 ( Q k ) denote the empirical Rademacher complexity of the target-token class on the combined sample S 0 S_0 S 0 of N = n T N=nT N = n T records, i.e., the quantity of Appendix B.1 with F \mathcal{F} F replaced by Q k Q_k Q k and one independent sign per record. Applying Theorem 2 to the target-token class yields the following deviation bound, uniform over the class.
Theorem 5 (Target-Token Risk Bound). Under Assumption 1, with probability at least 1 − δ 1-\delta 1 − δ , uniformly over g ∈ G g \in\mathcal{G} g ∈ G and h ∈ H h \in\mathcal{H} h ∈ H ,
∣ ∑ i = 1 T ( R D i k ( ψ g , h ) − R ^ S i k ( ψ g , h ) ) ∣ ≤ 2 T R ^ S 0 ( Q k ) + 3 B ℓ 2 T log ( 4 / δ ) n . (2) \left\lvert\sum_{i=1}^{T} \left(R_{\mathcal{D}_i}^{k}(\psi_{g,h})-\widehat{R}_{S_i}^{k}(\psi_{g,h})\right) \right\rvert\leq2T\widehat{\mathcal{R}}_{S_0}(\mathcal{Q}_k)+3B_{\ell}\sqrt{\frac{2T\log(4/\delta)}{n}}. \tag*{(2)} i = 1 ∑ T ( R D i k ( ψ g , h ) − R S i k ( ψ g , h ) ) ≤ 2 T R S 0 ( Q k ) + 3 B ℓ n 2 T log ( 4/ δ ) . (2)
The next corollary is the target-token counterpart of the ERM form of Corollary 3: for the empirical risk minimizer the empirical risks in the bound are replaced by the best-in-class population risks, at the price of paying the deviation twice.
Corollary 6 (ERM Final-Task Risk). Let ( g ^ , h ^ ) (\widehat{g},\widehat{h}) ( g , h ) and ( g ⋆ , h ⋆ ) (g^\star,h^\star) ( g ⋆ , h ⋆ ) be defined as above. With probability at least 1 − δ 1-\delta 1 − δ ,
R D ( F ψ g ^ , h ^ ) ≤ B ℓ k log 2 [ ∑ i = 1 T R D i k ( ψ g ⋆ , h ⋆ ) + 4 T R ^ S 0 ( Q k ) + 6 B ℓ 2 T log ( 4 / δ ) n ] . (3) R_{\mathcal{D}}(F_{\psi_{\widehat{g},\widehat{h}}}) \leq\frac{B_{\ell}k}{\log2}\left[\sum_{i=1}^{T}R_{\mathcal{D}_i}^{k}(\psi_{g^\star,h^\star})+4T\widehat{\mathcal{R}}_{S_0}(\mathcal{Q}_k)+6B_{\ell}\sqrt{\frac{2T\log(4/\delta)}{n}}\right]. \tag*{(3)} R D ( F ψ g , h ) ≤ log 2 B ℓ k [ i = 1 ∑ T R D i k ( ψ g ⋆ , h ⋆ ) + 4 T R S 0 ( Q k ) + 6 B ℓ n 2 T log ( 4/ δ ) ] . (3)
Under Assumption 2, the target-token complexity obeys the following bound. Deriving it (Appendix § 9 .§ 2 ) requires two ingredients beyond the general analysis of § 3.2 : the layerwise matrix-covering argument of [23 ] , which we instantiate for our decoder block and then restrict to the final k k k output rows, and a sequence-level loss-covering step of our own that charges one Rademacher sign per complete sequence rather than per generated token; the latter is what produces the 1 / N 1/\sqrt{N} 1/ N normalization with N = n T N=nT N = n T .
R ^ S 0 ( Q k ) ≲ G ℓ Θ d H τ m , N N + G ℓ d n v N , N = n T , (4) \widehat{\mathcal{R}}_{S_0}(\mathcal{Q}_k) \lesssim G_{\ell}\sqrt{\frac{\Theta d H\tau_{m,N}}{N}}+G_{\ell}\sqrt{\frac{d n_v}{N}}, \qquad N=nT, \tag*{(4)} R S 0 ( Q k ) ≲ G ℓ N Θ d H τ m , N + G ℓ N d n v , N = n T , (4)
where Θ \Theta Θ counts trainable parameters, L L L , H H H , d d d are the layer count, head count and model dimension, and τ m , N = log ( 1 + ρ L s L ( m , N ) ) \tau_{m,N}=\log(1+\rho_L s_L(m,N)) τ m , N = log ( 1 + ρ L s L ( m , N )) is the decoder-capacity factor (Appendix § 9 .§ 2 ); below we write τ \tau τ for τ m , N \tau_{m,N} τ m , N .
The resulting final-task bound is, for constants C 1 , C 2 > 0 C_1,C_2>0 C 1 , C 2 > 0 depending only on the fixed norm and normalization bounds of Assumption 2,
R D ( F ψ g ^ , h ^ ) ≤ B ℓ k log 2 [ ∑ i = 1 T R D i k ( ψ ⋆ ) + C 1 G ℓ T Θ d H τ n + C 2 G ℓ T d n v n + 6 B ℓ 2 T log ( 4 / δ ) n ] . (5) R_{\mathcal{D}}(F_{\psi_{\widehat{g},\widehat{h}}}) \leq\frac{B_{\ell}k}{\log2}\left[\sum_{i=1}^{T}R_{\mathcal{D}_i}^{k}(\psi^\star)+C_1G_{\ell}\sqrt{\frac{T\Theta dH\tau}{n}}+C_2G_{\ell}\sqrt{\frac{T d n_v}{n}}+6B_{\ell}\sqrt{\frac{2T\log(4/\delta)}{n}}\right]. \tag*{(5)} R D ( F ψ g , h ) ≤ log 2 B ℓ k [ i = 1 ∑ T R D i k ( ψ ⋆ ) + C 1 G ℓ n T Θ d H τ + C 2 G ℓ n T d n v + 6 B ℓ n 2 T log ( 4/ δ ) ] . (5)
Since B ℓ k / log 2 = O ( k ) B_{\ell}k/\log2=O(k) B ℓ k / log 2 = O ( k ) , for fixed model dimensions, norm bounds and clipping threshold the sample-dependent atomic excess contributes O ~ ( k T / n ) \widetilde{O}(k\sqrt{T/n}) O ( k T / n ) to the bound, where O ~ \widetilde{O} O suppresses the logarithmic factors of τ \tau τ and of the confidence term.
Discussion of the Final Bound
Depth and sample size. The target-token analysis treats the N = n T N=nT N = n T complete sequences as the independent observations while allowing arbitrary dependence among tokens within each sequence. Pooling these observations through one shared predictor under a uniform capacity control on the class yields an atomic excess of order T / n = T ⋅ n − 1 / 2 \sqrt{T/n}=\sqrt{T}\cdot n^{-1/2} T / n = T ⋅ n − 1/2 —a T \sqrt{T} T accumulation across the T T T composed steps, sublinear in place of the naive linear T T T , times the n − 1 / 2 n^{-1/2} n − 1/2 statistical cost of a single atomic step—rather than the T / n T/\sqrt{n} T / n dependence obtained by analyzing the T T T steps separately. We state this with the per-step sample size n n n held fixed, so that the depth dependence is T \sqrt{T} T ; if the total budget N = n T N=nT N = n T is held fixed instead, then n n n shrinks and the per-step sampling factor alone grows like T / N \sqrt{T/N} T / N , giving T / N T/\sqrt{N} T / N —linear behavior that comes from the shrinking per-step budget, not from any loss of the pooling gain. (3) retains the best-in-class step-level risk in the complete final-task risk bound; after the depth-independent factor B ℓ k / log 2 = O ( k ) B_{\ell}k/\log2=O(k) B ℓ k / log 2 = O ( k ) , the sample-dependent atomic excess contributes O ~ ( k T / n ) \widetilde{O}(k\sqrt{T/n}) O ( k T / n ) to the bound.
Context length and decoder capacity. We analyze the final-k k k -token loss directly, which permits dependence among tokens within a sequence; concentration is taken over the N = n T N=nT N = n T independent complete sequences. In the parameterized bound of Eq. (5) , context length enters through τ \tau τ evaluated at N = n T N=nT N = n T and also through Θ \Theta Θ if the trainable positional-embedding parameter count grows with m m m .
Theoretical context Unlike prior work that restricts compositional analysis to 2-step cases without explicit parameter-dependent bounds [25 ] , focuses on sub-task identification sample complexity rather than OOD error decomposition [26 ] , proves that CoT reduces learning difficulty without generalization bounds [16 ] , or addresses only single-distribution pretraining [23 ] , our framework unites CoT error decomposition with a shared-hypothesis structure and directly controls target-token risk with reasoning-depth and decoder-capacity dependence. Maurer et al. [24 ] provide a shared-representation perspective for pooled estimation, whereas Li et al. [23 ] provide decoder covering-number tools for full-sequence NTP. We use the latter only to control the restricted final-k k k output class; the target-token risk bound itself is derived directly at the sequence level.
Experiments
We evaluate compositional generalization on Atom-Task, a task of multi-step operations on sequences; GSM8K experiments, extended setup details, and noise-robustness results are in Appendix § 11 (GSM8K results in Section C.2).
Experimental Setup We introduce Atom-Task to isolate compositional reasoning, requiring sequential execution of atomic operations on symbolic sequences over a six-symbol alphabet ({ α , β , γ , δ , ε , ω } \{\alpha, \beta, \gamma, \delta, \varepsilon, \omega\} { α , β , γ , δ , ε , ω } ). We define five operations: Reverse, Substitute, Duplicate, Deduplicate, and Rotate.
Models and Datasets For the Atom-Task, we use Qwen3-4B. We design four training datasets: (1) Single-Step: 5k uniformly distributed one-step samples; (2) Three-Step: 1.66k three-step samples; (3) Mixed 3+5: 1,333 samples (833 three-step and 500 five-step; the latter use ≤ 2 \le2 ≤ 2 distinct operations, bridging length and combinatorial generalization); (4) Mixed 1-, 3-, and 5-Step: 4,000 one-step, 600 three-step, and 400 five-step samples (for each operation o p op o p , a dedicated 5k-sample dataset excludes o p op o p from all multi-step chains but keeps it in single-step data). For dataset-size accounting, an L L L -step trajectory contributes L L L step-level samples; this convention is used only to control the training-data budget. All models are evaluated on held-out 3-, 5-, 7-, and 9-step test sets (500 samples each). Full implementation details are given in Appendix § 11 .
Main Results and Analysis
Short-to-Long Generalization & CoT vs. No-CoT. Table 1 compares CoT and No-CoT settings. While CoT with single-step data shows some compositionality, its degradation at longer test steps indicates the benefit of short-chain training data. Crucially, models trained on short chains (3-step/3+5 mixed) perform well on longer tasks; since the 5-step chains limit operation types, this implies models generalize stepwise decomposition patterns. In contrast, No-CoT degradation indicates a failure to capture compositional structures without intermediate steps, causing overfitting to spurious correlations.
Table 1. Accuracy (%) by training data and test steps. All entries are means over 3 seeds (42, 2026, 12345); standard deviations are shown as subscripts.
Generalization to Unseen Combinations. Table 2 (a) shows performance when specific operations are excluded from multi-step samples. Even with 9-step test sequences, all experimental groups maintain high accuracy, indicating that models can effectively compose and generalize operations encountered only in single-step data to multi-step tasks, thereby achieving compositional generalization. Table 2 (b) again confirms the necessity of CoT: without it, performance remains consistently poor regardless of the excluded operation.
Table 2. Atom-Task: Accuracy (%) when an operation is excluded from multi-step samples. Entries are means over 3 seeds (42, 2026, 12345); standard deviations are shown as subscripts. Rev: Reverse, Dedup: Deduplicate, Sub: Substitute, Dup: Duplicate, Rot: Rotate.
Effect of State Tracking in CoT. We ablate the CoT format by removing explicit state tracking (remaining tasks and input context) from the intermediate outputs (shown in Figure 2 ), such that the intermediate state z i − 1 z_{i-1} z i − 1 can no longer carry complete information. Table 3 shows this ablation causes a consistent performance degradation (see the drop in average accuracy on the 7-step test set). This demonstrates that when z i − 1 z_{i-1} z i − 1 fails to preserve the full state, multi-step decomposition is impaired. This validates our theoretical requirement that z i − 1 z_{i-1} z i − 1 must carry complete state information.
Figure 2. Comparison of complete vs. incomplete CoT state recordings.
Table 3. Format ablation: Accuracy (%) with vs. without explicit state tracking. Abl.: means over 3 seeds (42, 2026, 12345); Orig.: means over 3 seeds from Table 2.
Scaling Trends of Compositional Generalization We study performance as a function of reasoning depth, training sample size, and the number of inference-time examples, as summarized in Figure 3 . For depth scaling (Figure 3 a), error increases with T T T , with diminishing increments for single-step training. Theorem 2 gives sublinear-in-T T T control of the estimation term at fixed n n n . For sample scaling (Figure 3 b), increasing the sample size consistently reduces the test error rate, particularly for longer reasoning chains, which is qualitatively consistent with a smaller estimation error at larger sample sizes. Figure 3 c varies the number of in-context examples at inference time rather than the theoretical sliding-window length m m m . Detailed data for these scaling experiments are provided in Appendix § 11 .1.3.
Figure 3. Each entry is a mean over 3 seeds (42, 2026, 12345). Atom-Task results when varying (a) test depth, (b) training sample size, and (c) inference-time examples; in (b) the horizontal axis is 1 n \frac{1}{\sqrt{n}} n 1 , where n n n is the sample size in units of the full budget (10%, 20%, 50%, 100%).
Further Related Work
CoT Prompting and Training Chain-of-Thought (CoT) enhances complex problem-solving by generating intermediate reasoning steps [1 ] , improving performance on math benchmarks [27 ] . This led to extensions such as Tree of Thoughts [28 ] , Graph of Thoughts [29 ] , and Program of Thoughts [30 ] , alongside robustness improvements via self-consistency [31 ] , self-refinement [32 ] , and retrieval-augmented generation [33 ] . Decomposition methods like Least-to-Most prompting [34 ] and Automatic CoT [35 ] further automate this process. However, most work focuses on inference-stage prompts, with limited discussion of CoT’s intrinsic training mechanisms [18 ] . Training LLMs with CoT via supervised fine-tuning or reinforcement learning, on the other hand, enhances capability [3 , 5 , 36 ] and improves compositional generalization [25 ] .
CoT Theoretical Analysis. Theoretically, CoT increases Transformers’ effective depth for serial problems [14 , 15 ] , and linear next-token predictors on CoT data can approximate Turing-computable functions [13 ] . Further analyses cover sample/time complexity [37 ] , task decomposition [16 ] , in-context learning bounds [17 ] , and expressive power on arithmetic or gradient descent [38 ] , with structural analysis showing reasoning internalized as combinatorial circuits [39 , 40 ] . However, these studies are often qualitative or limited to localized tasks [11 , 18 ] . More specifically, Joshi et al. [37 ] and Hanneke et al. [41 ] analyze the PAC (probably approximately correct) error of the final symbol under complete-trajectory supervision and realizability, whereas our setting supervises individual atomic steps through a target-token objective and provides explicit depth-dependent bounds. The analysis of [25 ] considers out-of-distribution generalization but is restricted to two-step tasks and lacks LLM-specific analysis. Maurer et al. [24 ] provide a shared-representation perspective for pooled estimation, whereas Li et al. [23 ] provide the decoder covering-number tool used for our restricted final-k k k output class.
Conclusion and Future Work
In this work we asked where the out-of-distribution capability of CoT comes from, and located it in the reuse of one transition model along the chain. The analysis separates a multiplicative price for inference errors, of order O ( k ) O(k) O ( k ) , set by the block length rather than by the number of steps, from a statistical cost that grows only as O ( T / n ) O(\sqrt{T/n}) O ( T / n ) , since a single predictor serves all T T T sub-tasks and can be assessed on a combined sample. In the token-by-token prediction regime this gives an end-to-end bound that is B ℓ k / log 2 B_{\ell}k/\log2 B ℓ k / log 2 times the best-in-class summed step-level risk, plus an estimation term of order O ~ ( k T / n ) \widetilde{O}(k\sqrt{T/n}) O ( k T / n ) ; a matched construction for the sub-task ERM shows that the T / n \sqrt{T/n} T / n dependence is not an artefact of the analysis. The decomposition further indicates how learning reusable transitions can support compositional transfer—consistent with our experiments, where explicit state tracking proves essential. Taken together, the analysis sharpens our picture of how compositional OOD generalization arises under CoT, and that picture is not tied to autoregressive token-by-token output: it may also inform future analyses of agents that maintain and update an external memory.
Limitations & Future Work
Our theory studies explicit CoT under supervised NTP-style training, where intermediate states and step-level transitions are observable; it excludes adaptive paradigms such as reinforcement fine-tuning and test-time search [11 , 42 , 43 , 44 , 45 ] , where trajectories may be selected, refined, or rewarded. Extending our decomposition framework to these settings is a natural future direction, and does not affect the mechanism identified here.
Acknowledgments and Disclosure of Funding
This work was supported by the Special Fund for Key Program of Science and Technology of Jiangsu Province (No. BG2024042); the Gusu Leading Talents Program for Innovation and Entrepreneurship (No. ZXL2025323); the Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (No. JYB2025ZXDM118); and the “111 Center” (No. B26023). This work was also partially supported by the Lee Kong Chian Fellowship awarded to Pan Zhou by Singapore Management University. We thank the NeurIPS reviewers for their valuable feedback and suggestions.
Supplementary Details on NTP Setting
This section supplements Section 4 by defining the decoder architecture and the sampling units used in the target-token analysis. We use the convention of Section 4.1: m m m denotes the complete-record length (and the maximum sequence length used by the decoder), the block-boundary state has length m − k m-k m − k , and V \mathcal{V} V denotes the vocabulary.
Decoder-only Model Architecture
Contemporary Large Language Models (LLMs) predominantly utilize a decoder-only Transformer architecture. As described in Section 4.1, the composite model L M = g ∘ h \mathrm{LM}=g\circ h LM = g ∘ h consists of a representation learner h h h and a token predictor g g g . We formalize the representation learner h h h as an L L L -layer Transformer decoder, following the block description of [23 Eq. (4)] , mapping an input token sequence Z ∈ V m Z\in\mathcal{V}^{m} Z ∈ V m to a hidden representation h ( Z ) ∈ R m × d h(Z)\in\mathbb{R}^{m\times d} h ( Z ) ∈ R m × d . The decoder applies to any prefix Z ∈ V s Z\in\mathcal{V}^{s} Z ∈ V s with s ≤ m s\le m s ≤ m , and the prediction head reads its last hidden state.
The process begins with an Embedding Layer, which converts discrete tokens into continuous vectors Z 0 ∈ R m × d Z_{0}\in\mathbb{R}^{m\times d} Z 0 ∈ R m × d via:
Z 0 = Embedding ( Z ) : = OneHot ( Z ) W e + W p . Z_{0}=\operatorname{Embedding}(Z):=\operatorname{OneHot}(Z)W_{e}+W_{p}. Z 0 = Embedding ( Z ) := OneHot ( Z ) W e + W p .
where OneHot ( Z ) ∈ { 0 , 1 } m × n v \operatorname{OneHot}(Z)\in\{0,1\}^{m\times n_{v}} OneHot ( Z ) ∈ { 0 , 1 } m × n v is the one-hot encoding of the m m m tokens, W e ∈ R n v × d W_{e}\in\mathbb{R}^{n_{v}\times d} W e ∈ R n v × d is the token embedding matrix, and W p ∈ R m × d W_{p}\in\mathbb{R}^{m\times d} W p ∈ R m × d is the position embedding matrix. The core of the architecture consists of L L L stacked Transformer-decoder blocks. For layer l ∈ { 1 , … , L } l\in\{1,\ldots,L\} l ∈ { 1 , … , L } , the output Z l Z_{l} Z l is computed from Z l − 1 Z_{l-1} Z l − 1 via masked self-attention and feed-forward networks (FFN). Specifically, let H H H be the number of attention heads and d k = d / H d_{k}=d/H d k = d / H . The masked self-attention head h ∈ [ H ] h\in[H] h ∈ [ H ] is defined as:
Attn h ( Z l − 1 ) = softmax ( Q h K h ⊤ d k + M ) V h , \operatorname{Attn}_{h}(Z_{l-1})=\operatorname{softmax}\left(\frac{Q_{h}K_{h}^{\top}}{\sqrt{d_{k}}}+M\right)V_{h}, Attn h ( Z l − 1 ) = softmax ( d k Q h K h ⊤ + M ) V h ,
Q h = Z l − 1 W h Q , K h = Z l − 1 W h K , V h = Z l − 1 W h V . Q_{h}=Z_{l-1}W_{h}^{Q},\qquad K_{h}=Z_{l-1}W_{h}^{K},\qquad V_{h}=Z_{l-1}W_{h}^{V}. Q h = Z l − 1 W h Q , K h = Z l − 1 W h K , V h = Z l − 1 W h V .
Here, M ∈ R m × m M\in\mathbb{R}^{m\times m} M ∈ R m × m is a causal mask matrix where M i j = − ∞ M_{ij}=-\infty M ij = − ∞ if j > i j>i j > i and 0 0 0 otherwise. This mask ensures that the hidden state at position t t t attends only to tokens at positions ≤ t \le t ≤ t , so that the token at position t t t is predicted from the state at position t − 1 t-1 t − 1 , thereby implementing the autoregressive property essential for Next-Token Prediction (NTP). The final output of the layer is given by:
Y l : = Norm 1 ( ∑ h = 1 H Attn h ( Z l − 1 ) W h O + Z l − 1 ) , Z l = Norm 2 ( FFN ( Y l ) + Y l ) . Y_{l}:=\operatorname{Norm}_{1}\left(\sum_{h=1}^{H}\operatorname{Attn}_{h}(Z_{l-1})W_{h}^{O}+Z_{l-1}\right),\qquad Z_{l}=\operatorname{Norm}_{2}\left(\operatorname{FFN}(Y_{l})+Y_{l}\right). Y l := Norm 1 ( h = 1 ∑ H Attn h ( Z l − 1 ) W h O + Z l − 1 ) , Z l = Norm 2 ( FFN ( Y l ) + Y l ) .
where Norm 1 , Norm 2 \operatorname{Norm}_{1},\operatorname{Norm}_{2} Norm 1 , Norm 2 denote Layer Normalization and FFN ( Y ) = σ ( Y W F 1 ) W F 2 \operatorname{FFN}(Y)=\sigma(YW_{F1})W_{F2} FFN ( Y ) = σ ( Y W F 1 ) W F 2 is a two-layer feed-forward network with hidden width d f = 4 d d_{f}=4d d f = 4 d . The representation learner thus serializes the input into a deep representation h ( Z ) = Z L h(Z)=Z_{L} h ( Z ) = Z L .
The token predictor g g g applies a linear projection to the hidden state at the last position, g ( h ( Z ) ) = softmax ( ( h ( Z ) ) s , : W P ) g(h(Z))=\operatorname{softmax}((h(Z))_{s,:}W_{P}) g ( h ( Z )) = softmax (( h ( Z ) ) s , : W P ) with s = ∣ Z ∣ s=|Z| s = ∣ Z ∣ and W P ∈ R d × n v W_{P}\in\mathbb{R}^{d\times n_{v}} W P ∈ R d × n v , mapping it to a probability distribution over the vocabulary V \mathcal{V} V .
Explicit Parameterization and Derivation of the Dimension-Dependent Bound
To quantify the Rademacher term in Corollary 6, we use the matrix-covering tools recorded in [23 Lemma C.3] . The statistical argument below is carried out directly for sequence-level losses.
Assumption 2 (Capacity and Regularity Constraints). For the L L L -layer, H H H -head decoder-only Transformer defined in Appendix A.1 (following [23 Eq. (4)] and Assumption 4.14), we assume:
∥ Q l h ( K l h ) ⊤ / d k ∥ ℓ ∞ ≤ C l . \left\|Q_{l}^{h}(K_{l}^{h})^{\top}/\sqrt{d_{k}}\right\|_{\ell_{\infty}}\le C_{l}. Q l h ( K l h ) ⊤ / d k ℓ ∞ ≤ C l .
The embedding matrices and output head also have bounded Frobenius norms. Let B ∗ ≥ 1 B_* \ge1 B ∗ ≥ 1 be a common upper bound for these norms and the B l B_l B l . For the capacity estimate, normalization is a fixed rowwise operator whose output rows have norm at most C π d C_\pi\sqrt{d} C π d , with fixed C π C_\pi C π ; the feed-forward activation is 1-Lipschitz and vanishes at zero, as does ReLU. These are the usual bounded-row normalization and feed-forward conditions. The constants B ∗ , G π , C π B_*, G_\pi, C_\pi B ∗ , G π , C π are fixed independently of the sample size and model dimensions. Let Θ \Theta Θ count all trainable scalar parameters, including token and positional embeddings whenever they are trained, and the output head.
The norm and Lipschitz upper bounds may be enlarged so that B l , G π ≥ 1 B_l, G_\pi\ge1 B l , G π ≥ 1 . Let N = n T N=nT N = n T and ρ L = ∑ l = 1 L B l 2 \rho_L=\sum_{l=1}^{L}B_l^2 ρ L = ∑ l = 1 L B l 2 , and set
s L ( m , N ) = ∏ l = 1 L G π 2 ( B l 2 + 1 ) ( e C l B l 2 H N m d N + 1 ) , s_L(m,N)=\prod_{l=1}^{L}G_\pi^2(B_l^2+1)\left(e^{C_lB_l^2HNmd\sqrt{N}}+1\right), s L ( m , N ) = l = 1 ∏ L G π 2 ( B l 2 + 1 ) ( e C l B l 2 H N m d N + 1 ) ,
τ m , N = log ( 1 + ρ L s L ( m , N ) ) . \tau_{m,N}=\log\left(1+\rho_Ls_L(m,N)\right). τ m , N = log ( 1 + ρ L s L ( m , N ) ) .
Here s L s_L s L collects the per-layer amplification factors that a parameter perturbation of size η \eta η accumulates over the L L L blocks, and τ m , N \tau_{m,N} τ m , N is the logarithm of the resulting covering-number bound; the individual factors are derived in the propagation estimate below.
For fixed norm, attention-score, and normalization bounds, τ m , N = O ( L log ( 2 + N H m d ) + log ( 1 + L ) ) \tau_{m,N}=O\left(L\log(2+NHmd)+\log(1+L)\right) τ m , N = O ( L log ( 2 + N H m d ) + log ( 1 + L ) ) . Below, constants in ≲ \lesssim ≲ may depend on the fixed bounds B ∗ , G π , C π B_*,G_\pi,C_\pi B ∗ , G π , C π , but not on G l , N , m , k , L , d , H , n v G_l,N,m,k,L,d,H,n_v G l , N , m , k , L , d , H , n v .
Derivation of (4) . We first record a coarse output cover, including every trainable matrix. A Frobenius ball of radius B ∗ B_* B ∗ in R a × b \mathbb{R}^{a\times b} R a × b has an η \eta η -net, i.e., a set of points whose η \eta η -neighbourhood covers the ball, of cardinality at most ( 1 + 2 B ∗ / η ) a b (1+2B_*/\eta)^{ab} ( 1 + 2 B ∗ / η ) ab , by vectorization and [23 Lemma C.3] . Taking the product of these nets gives at most ( 1 + 2 B ∗ / η ) Θ (1+2B_*/\eta)^\Theta ( 1 + 2 B ∗ / η ) Θ parameter representatives. Rather than composing the layerwise coverings of [23 Lemma 4.15 and Proposition 4.17] , we propagate the approximation errors through the actual block of Appendix § 9 .§ 1 , which keeps our normalization placement unchanged.
For completeness, write T F l \mathrm{TF}_l TF l for block l l l . A normalized row has norm at most C π d C_\pi\sqrt{d} C π d , and the bounded feed-forward weights and residual therefore give a block-output row norm at most a constant times d \sqrt{d} d . Embedding rows satisfy the same type of bound. The causal softmax has Euclidean Lipschitz constant at most 1, and its attention matrix has operator norm at most m \sqrt{m} m . For two such admissible inputs, if every matrix in the two blocks differs by at most η \eta η , multiplication of the query, key, value, and output matrices, followed by the residual and feed-forward operations, gives
∥ T F l ( Z ) − T F l ′ ( Z ′ ) ∥ F ≤ Γ ( ∥ Z − Z ′ ∥ F + m η ) , Γ = c H m d 2 ≥ 1 , \left\|\mathrm{TF}_l(Z)-\mathrm{TF}'_l(Z')\right\|_F\le\Gamma\left(\left\|Z-Z'\right\|_F+\sqrt{m}\eta\right),\qquad\Gamma=cHm d^2\ge1, TF l ( Z ) − TF l ′ ( Z ′ ) F ≤ Γ ( ∥ Z − Z ′ ∥ F + m η ) , Γ = cH m d 2 ≥ 1 ,
where c c c depends only on B ∗ , G π , C π B_*,G_\pi,C_\pi B ∗ , G π , C π . Indeed, the query-key input perturbation is bounded by a constant times m ∥ Z − Z ′ ∥ F \sqrt{m}\left\|Z-Z'\right\|_F m ∥ Z − Z ′ ∥ F , its parameter perturbation by a constant times m d η m d\eta m d η , and the remaining projections contribute at most a constant times m d η \sqrt{m}d\eta m d η ; the displayed Γ \Gamma Γ bounds all these factors. The embedding approximation error is at most 2 m η 2\sqrt{m}\eta 2 m η . Induction over the L L L blocks and inclusion of the output head thus give, for the concatenated probability outputs on N N N records,
∥ A − A ′ ∥ F ≤ N m Λ η , Λ = ( L + 3 ) Γ L + 1 . \left\|A-A'\right\|_F\le\sqrt{N}m\Lambda\eta,\qquad\Lambda=(L+3)\Gamma^{L+1}. ∥ A − A ′ ∥ F ≤ N m Λ η , Λ = ( L + 3 ) Γ L + 1 .
This argument covers trainable embeddings as part of the parameter vector; fixed embeddings require no net. Covering representatives can be taken in the norm balls, and recentering in the original function class, if necessary, only changes numerical constants.
Let Π k \Pi_k Π k select the final k k k prediction rows, aligned with the target labels as in Eq. (1) . Every such row is computed from its teacher-forced prefix. Since
∥ Π k A − Π k B ∥ F ≤ ∥ A − B ∥ F , \left\|\Pi_kA-\Pi_kB\right\|_F\le\left\|A-B\right\|_F, ∥ Π k A − Π k B ∥ F ≤ ∥ A − B ∥ F ,
a full-output cover also covers the selected rows. For one record, write q ( A ) q(A) q ( A ) for its target-token loss with the labels fixed. The loss Lipschitz condition and Cauchy–Schwarz give
∣ q ( A ) − q ( B ) ∣ ≤ G ℓ k ∑ r = 1 k ∥ A m − k + r − B m − k + r ∥ 2 ≤ G ℓ k ∥ Π k A − Π k B ∥ F . \begin{aligned}
|q(A)-q(B)|\le\frac{G_\ell}{k}\sum_{r=1}^{k}\left\|A_{m-k+r}-B_{m-k+r}\right\|_2 \\
&\le\frac{G_\ell}{\sqrt{k}}\left\|\Pi_kA-\Pi_kB\right\|_F.
\end{aligned} ∣ q ( A ) − q ( B ) ∣ ≤ k G ℓ r = 1 ∑ k ∥ A m − k + r − B m − k + r ∥ 2 ≤ k G ℓ ∥ Π k A − Π k B ∥ F .
Hence the concatenated N N N -dimensional loss vectors are approximated within G ℓ N m / k Λ η G_{\ell}\sqrt{Nm/k}\,\Lambda\eta G ℓ N m / k Λ η (aggregating the N N N records in ℓ 2 \ell_2 ℓ 2 ). Choosing η = ϵ k / ( G ℓ N m Λ ) \eta=\epsilon\sqrt{k}/(G_{\ell}\sqrt{Nm}\Lambda) η = ϵ k / ( G ℓ N m Λ ) , and setting ϵ = G ℓ N u \epsilon=G_{\ell}\sqrt{N}\,u ϵ = G ℓ N u , yields the covering-number bound
log N ( Q k ∣ S 0 , G ℓ N u , ∥ ⋅ ∥ 2 ) ≤ Θ log ( 1 + 2 B ∗ Λ m / k u ) \log\mathcal{N}\left(\mathcal{Q}_k|_{S_0},G_{\ell}\sqrt{N}\,u,\|\cdot\|_2\right)\leq\Theta\log\left(1+\frac{2B_*\Lambda\sqrt{m/k}}{u}\right) log N ( Q k ∣ S 0 , G ℓ N u , ∥ ⋅ ∥ 2 ) ≤ Θ log ( 1 + u 2 B ∗ Λ m / k )
where N ( ⋅ , ⋅ , ∥ ⋅ ∥ 2 ) \mathcal{N}(\cdot,\cdot,\|\cdot\|_2) N ( ⋅ , ⋅ , ∥ ⋅ ∥ 2 ) denotes the covering number, i.e., the smallest cardinality of such a net in the ℓ 2 \ell_2 ℓ 2 norm, and Q k ∣ S 0 \mathcal{Q}_k|_{S_0} Q k ∣ S 0 is the restriction of Q k \mathcal{Q}_k Q k to the sample S 0 S_0 S 0 . Center the loss vectors at any fixed member of Q k ∣ S 0 \mathcal{Q}_k|_{S_0} Q k ∣ S 0 . This leaves their empirical Rademacher complexity unchanged. The probability simplex has diameter 2 \sqrt{2} 2 , so each centered loss vector has norm at most G ℓ 2 N G_{\ell}\sqrt{2N} G ℓ 2 N . Dudley’s entropy integral with the sequence-level normalization 1 / N 1/N 1/ N gives
R ^ S 0 ( Q k ) ≲ G ℓ Θ N ∫ 0 2 log ( 1 + 2 B ∗ Λ m / k u ) d u \widehat{\mathfrak{R}}_{S_0}(\mathcal{Q}_k)\lesssim G_{\ell}\sqrt{\frac{\Theta}{N}}\int_0^{\sqrt{2}}\sqrt{\log\left(1+\frac{2B_*\Lambda\sqrt{m/k}}{u}\right)}\,du R S 0 ( Q k ) ≲ G ℓ N Θ ∫ 0 2 log ( 1 + u 2 B ∗ Λ m / k ) d u
≲ G ℓ Θ N 1 + log ( 1 + 2 B ∗ Λ m / k ) . \lesssim G_{\ell}\sqrt{\frac{\Theta}{N}}\sqrt{1+\log\left(1+2B_*\Lambda\sqrt{m/k}\right)}. ≲ G ℓ N Θ 1 + log ( 1 + 2 B ∗ Λ m / k ) .
The last step uses ∫ 0 2 log ( 1 + a / u ) d u ≲ 1 + log ( 1 + a ) \int_0^{\sqrt{2}}\sqrt{\log(1+a/u)}\,du\lesssim\sqrt{1+\log(1+a)} ∫ 0 2 log ( 1 + a / u ) d u ≲ 1 + log ( 1 + a ) for a ≥ 0 a\geq0 a ≥ 0 . Since k ≥ 1 k\geq1 k ≥ 1 , the logarithmic factor is at most a constant times 1 + log ( L + 3 ) + ( L + 1 ) log ( 2 + H m d ) 1+\log(L+3)+(L+1)\log(2+Hmd) 1 + log ( L + 3 ) + ( L + 1 ) log ( 2 + H m d ) . On the other hand, B l , G π ≥ 1 B_l,G_{\pi}\geq1 B l , G π ≥ 1 and C l ≥ 0 C_l\geq0 C l ≥ 0 give ρ L ≥ L \rho_L\geq L ρ L ≥ L and s L ≥ [ 2 ( 1 + H m d ) ] L s_L\geq[2(1+Hmd)]^L s L ≥ [ 2 ( 1 + H m d ) ] L , hence
τ m , N ≥ log ( 1 + L [ 2 ( 1 + H m d ) ] L ) , \tau_{m,N}\geq\log\left(1+L[2(1+Hmd)]^L\right), τ m , N ≥ log ( 1 + L [ 2 ( 1 + H m d ) ] L ) ,
which dominates this factor. We have therefore obtained
R ^ S 0 ( Q k ) ≲ G ℓ Θ τ m , N N . \widehat{\mathfrak{R}}_{S_0}(\mathcal{Q}_k)\lesssim G_{\ell}\sqrt{\frac{\Theta\tau_{m,N}}{N}}. R S 0 ( Q k ) ≲ G ℓ N Θ τ m , N .
Because d H ≥ 1 d_H\geq1 d H ≥ 1 , this also proves the coarser form used in the main text,
R ^ S 0 ( Q k ) ≲ G ℓ Θ d H τ m , N N + G ℓ d n v N . \widehat{\mathfrak{R}}_{S_0}(\mathcal{Q}_k)\lesssim G_{\ell}\sqrt{\frac{\Theta d_H\tau_{m,N}}{N}}+G_{\ell}\sqrt{\frac{dn_v}{N}}. R S 0 ( Q k ) ≲ G ℓ N Θ d H τ m , N + G ℓ N d n v .
Here Θ \Theta Θ already counts the head and any trainable embeddings, so the first term alone is valid and the second is redundant; the displayed bound is a looser consequence of the preceding estimate. The proof uses one Rademacher sign per sequence and introduces one factor G ℓ G_{\ell} G ℓ ; it never replaces these signs by independent signs for individual tokens.
Finally, N = n T N=nT N = n T gives
T R ^ S 0 ( Q k ) ≲ G ℓ Θ d H τ m , n T T n + G ℓ T d n v n . T\widehat{\mathfrak{R}}_{S_0}(\mathcal{Q}_k)\lesssim G_{\ell}\sqrt{\frac{\Theta d_H\tau_{m,nT}T}{n}}+G_{\ell}\sqrt{\frac{Tdn_v}{n}}. T R S 0 ( Q k ) ≲ G ℓ n Θ d H τ m , n T T + G ℓ n T d n v .
Substituting this in Eq. (3) gives Eq. (5) . The coefficients 4 T 4T 4 T and 6 B ℓ 6B_{\ell} 6 B ℓ in the ERM bound are unchanged, and the reduction factor B ℓ k / log 2 B_{\ell}k/\log2 B ℓ k / log 2 is applied once. Context length enters through τ m , n T \tau_{m,nT} τ m , n T and also through Θ \Theta Θ when the number of trainable positional-embedding parameters grows with m m m .
Sampling Units
For each step i i i , the dataset S i S_i S i contains n n n independently sampled complete sequences from the corresponding step-level skill distribution D i \mathcal{D}_i D i . These sequences need not be extracted from a shared trajectory; each is drawn independently from some real-world instance of the same skill. Dependence among tokens and prefixes within a complete sequence is unrestricted. This independent-record view is the idealization underlying the bounds. The Atom-Task experiments use the one-step and short-chain datasets specified in Section 5, including three- and five-step chains; the L L L -step accounting serves only as a budget convention, not an independence assumption for transitions within a chain.
Technical appendices and supplementary material
Technical Preliminaries
We provide the formal definitions for the theoretical frameworks used in our analysis.
PAC Learning We conduct analysis within the Probably Approximately Correct (PAC) framework, deriving explicit upper bounds for the generalization error that hold with probability at least 1 − δ 1-\delta 1 − δ .
Rademacher Complexity Rademacher complexity measures the richness of a function class F \mathcal{F} F . For a fixed sample S = { x 1 , … , x N } S=\{x_1,\ldots,x_N\} S = { x 1 , … , x N } , the empirical Rademacher complexity and expected Rademacher complexity are defined as
R ^ S ( F ) = E σ [ sup f ∈ F 1 N ∑ i = 1 N σ i f ( x i ) ] , R N ( F ) = E S [ R ^ S ( F ) ] . \widehat{\mathcal{R}}_S(\mathcal{F})=\mathbb{E}_{\sigma}\left[\sup_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^{N}\sigma_i f(x_i)\right],\qquad\mathcal{R}_N(\mathcal{F})=\mathbb{E}_S[\widehat{\mathcal{R}}_S(\mathcal{F})]. R S ( F ) = E σ [ f ∈ F sup N 1 i = 1 ∑ N σ i f ( x i ) ] , R N ( F ) = E S [ R S ( F )] .
where σ i \sigma_i σ i are independent Rademacher random variables taking values ± 1 \pm1 ± 1 with equal probability.
Total Variation Distance For two probability distributions P P P and Q Q Q over the same measurable space X \mathcal{X} X , the total variation distance is defined as
∥ P − Q ∥ T V = sup A ⊆ X ∣ P ( A ) − Q ( A ) ∣ . \lVert P-Q\rVert_{\mathrm{TV}}=\sup_{A\subseteq\mathcal{X}}|P(A)-Q(A)|. ∥ P − Q ∥ TV = A ⊆ X sup ∣ P ( A ) − Q ( A ) ∣.
Since ∣ L ∣ ≤ B ℓ |\mathcal{L}|\leq B_\ell ∣ L ∣ ≤ B ℓ , this distance bounds the discrepancy of Corollary 4: disc F ( D i , Q i ) ≤ 2 B ℓ ∥ D i − Q i ∥ T V \operatorname{disc}_{\mathcal{F}}(\mathcal{D}_i,\mathcal{Q}_i)\leq2B_\ell\lVert\mathcal{D}_i-\mathcal{Q}_i\rVert_{\mathrm{TV}} disc F ( D i , Q i ) ≤ 2 B ℓ ∥ D i − Q i ∥ TV .
Local Error Floor of a Hard-Decoding Error
To derive the generalization error decomposition, we first record the loss incurred by a hard-decoding error at a single step.
Lemma 7. (Local Error Floor of a Hard-Decoding Error.) For the autoregressive predictor ψ \psi ψ , every state s s s and every ground-truth block Δ s \Delta_s Δ s satisfy
L ( ψ ( s ) , Δ s ) ≥ log 2 k 1 { hard ( ψ ( s ) ) ≠ Δ s } . \mathcal{L}(\psi(s),\Delta_s) \ge\frac{\log2}{k}\mathbb{1}\{\operatorname{hard}(\psi(s)) \ne\Delta_s\}. L ( ψ ( s ) , Δ s ) ≥ k log 2 1 { hard ( ψ ( s )) = Δ s } . where ( log 2 ) / k (\log2)/k ( log 2 ) / k is a lower bound on the sequence-level loss L \mathcal{L} L whenever the hard decoding differs from the ground truth.
Proof. Fix a state s s s and a ground-truth block Δ s \Delta_s Δ s , and consider a token whose ground-truth index is p p p and whose argmax index is q ≠ p q \ne p q = p . Then y ^ q ≥ y ^ p \widehat{y}_q \ge\widehat{y}_p y q ≥ y p , and since probabilities are non-negative and sum to at most 1 1 1 :
1 ≥ y ^ p + y ^ q ≥ 2 y ^ p ⟹ y ^ p ≤ 1 / 2. 1 \ge\widehat{y}_p+\widehat{y}_q \ge2\widehat{y}_p \quad\Longrightarrow\quad\widehat{y}_p \le1/2. 1 ≥ y p + y q ≥ 2 y p ⟹ y p ≤ 1/2.
Since max { y ^ p , ϵ ℓ } ≤ 1 / 2 \max\{\widehat{y}_p,\epsilon_\ell\} \le1/2 max { y p , ϵ ℓ } ≤ 1/2 whenever y ^ p ≤ 1 / 2 \widehat{y}_p \le1/2 y p ≤ 1/2 and ϵ ℓ < 1 / 4 \epsilon_\ell< 1/4 ϵ ℓ < 1/4 , the token-level clipped cross-entropy of every mispredicted token satisfies ℓ = − log max { y ^ p , ϵ ℓ } ≥ log 2 \ell=-\log\max\{\widehat{y}_p,\epsilon_\ell\}\ge\log2 ℓ = − log max { y p , ϵ ℓ } ≥ log 2 . A block is hard-decoding-erroneous only if at least one of its k k k tokens is mispredicted, so averaging over the k k k tokens yields L ( ψ ( s ) , Δ s ) ≥ log 2 k > 0 \mathcal{L}(\psi(s),\Delta_s)\ge\frac{\log2}{k}>0 L ( ψ ( s ) , Δ s ) ≥ k l o g 2 > 0 , which is the claim. □
Remark 7. The bound uses deterministic hard predictions: if the hard predictions at a step match the ground truth then no error is recorded, and otherwise the deviation is charged through the lower bound ( log 2 ) / k (\log2)/k ( log 2 ) / k on the local loss. This is the fact used by the risk decomposition of Theorem 1.
Proof of Theorem 1 (Generalization Error Decomposition)
Proof. We aim to bound the generalization error R D ( F ψ ) R_D(F_\psi) R D ( F ψ ) . Let z = ( z 0 , Δ z 1 , … , Δ z T ) ∼ D ′ \mathbf{z}=(z_0,\Delta z_1,\ldots,\Delta z_T)\sim D' z = ( z 0 , Δ z 1 , … , Δ z T ) ∼ D ′ and let p ( z ) p(\mathbf{z}) p ( z ) denote its density. Recall that the oracle state is written z i z_i z i , whereas the free-running (FR) state generated by the model is written with a hat, z ^ 0 = z 0 \widehat{z}_0=z_0 z 0 = z 0 and z ^ i = ψ ‾ ( z ^ i − 1 ) \widehat{z}_i=\overline{\psi}(\widehat{z}_{i-1}) z i = ψ ( z i − 1 ) , so that
R D ( F ψ ) = ∫ L ( ψ ( z ^ T − 1 ) , Δ z T ) d p ( z ) . R_D(F_\psi)=\int\mathcal{L}(\psi(\widehat{z}_{T-1}),\Delta z_T)\,dp(\mathbf{z}). R D ( F ψ ) = ∫ L ( ψ ( z T − 1 ) , Δ z T ) d p ( z ) .
We first record a fact that will be used repeatedly: the FR and oracle trajectories coincide exactly up to the first hard-decoding error. Formally, let
u i : = 1 { hard ( ψ ( z ^ i − 1 ) ) ≠ Δ z i } , I : = inf { i ≥ 1 : u i = 1 } , u_i:=\mathbb{1}\{\operatorname{hard}(\psi(\widehat{z}_{i-1}))\ne\Delta z_i\},\qquad I:=\inf\{i\ge1:u_i=1\}, u i := 1 { hard ( ψ ( z i − 1 )) = Δ z i } , I := inf { i ≥ 1 : u i = 1 } ,
with I = ∞ I=\infty I = ∞ if no error occurs. Then on the event { u 1 = ⋯ = u i − 1 = 0 } \{u_1=\cdots=u_{i-1}=0\} { u 1 = ⋯ = u i − 1 = 0 } the two states agree, z ^ i − 1 = z i − 1 \widehat{z}_{i-1}=z_{i-1} z i − 1 = z i − 1 . Indeed, z ^ 0 = z 0 \widehat{z}_0=z_0 z 0 = z 0 , and if z ^ j − 1 = z j − 1 \widehat{z}_{j-1}=z_{j-1} z j − 1 = z j − 1 while u j = 0 u_j=0 u j = 0 , then
Δ z ^ j = hard ( ψ ( z ^ j − 1 ) ) = hard ( ψ ( z j − 1 ) ) = Δ z j , \widehat{\Delta z}_j=\operatorname{hard}(\psi(\widehat{z}_{j-1}))=\operatorname{hard}(\psi(z_{j-1}))=\Delta z_j, Δ z j = hard ( ψ ( z j − 1 )) = hard ( ψ ( z j − 1 )) = Δ z j ,
so that
z ^ j = z ^ j − 1 [ k + 1 : m ] ⊕ Δ z ^ j = z j − 1 [ k + 1 : m ] ⊕ Δ z j = z j . \widehat{z}_j=\widehat{z}_{j-1}[k+1:m]\mathbin{\oplus}\widehat{\Delta z}_j=z_{j-1}[k+1:m]\mathbin{\oplus}\Delta z_j=z_j. z j = z j − 1 [ k + 1 : m ] ⊕ Δ z j = z j − 1 [ k + 1 : m ] ⊕ Δ z j = z j .
The claim follows by induction. We stress that this is a consequence of hard decoding alone—before the first error the two trajectories are identical rather than merely close—and that no Lipschitz or stability property of ψ \psi ψ is used.
Next, we split the final-step risk at the first error. On { I > T − 1 } \{I>T-1\} { I > T − 1 } the observation above gives z ^ T − 1 = z T − 1 \widehat{z}_{T-1}=z_{T-1} z T − 1 = z T − 1 , so the integrand is exactly the step-T T T oracle loss; on { I ≤ T − 1 } \{I\le T-1\} { I ≤ T − 1 } it is bounded by B ℓ B_\ell B ℓ . Pointwise
L ( ψ ( z ^ T − 1 ) , Δ z T ) ≤ L ( ψ ( z T − 1 ) , Δ z T ) + B ℓ 1 { I ≤ T − 1 } , \mathcal{L}(\psi(\widehat{z}_{T-1}),\Delta z_T)\le\mathcal{L}(\psi(z_{T-1}),\Delta z_T)+B_\ell\mathbb{1}\{I\le T-1\}, L ( ψ ( z T − 1 ) , Δ z T ) ≤ L ( ψ ( z T − 1 ) , Δ z T ) + B ℓ 1 { I ≤ T − 1 } ,
and integrating against p ( z ) p(\mathbf{z}) p ( z ) yields
R D ( F ψ ) ≤ R D T ( ψ ) + B ℓ Pr ( I ≤ T − 1 ) = R D T ( ψ ) + B ℓ ∑ i = 1 T − 1 Pr ( I = i ) , R_D(F_\psi)\le R_{D_T}(\psi)+B_\ell\Pr(I\le T-1)=R_{D_T}(\psi)+B_\ell\sum_{i=1}^{T-1}\Pr(I=i), R D ( F ψ ) ≤ R D T ( ψ ) + B ℓ Pr ( I ≤ T − 1 ) = R D T ( ψ ) + B ℓ i = 1 ∑ T − 1 Pr ( I = i ) ,
where the last step uses that the events { I = i } \{I=i\} { I = i } are disjoint.
It remains to charge each first-error probability to the corresponding atomic risk. Fix i ≤ T − 1 i\le T-1 i ≤ T − 1 . Since { I = i } = { I ≥ i } ∩ { u i = 1 } \{I=i\}=\{I\ge i\}\cap\{u_i=1\} { I = i } = { I ≥ i } ∩ { u i = 1 } , and since on { I ≥ i } \{I\ge i\} { I ≥ i } the observation above gives z ^ i − 1 = z i − 1 \widehat{z}_{i-1}=z_{i-1} z i − 1 = z i − 1 , the event { I = i } \{I=i\} { I = i } coincides with
{ I ≥ i } ∩ { hard ( ψ ( z i − 1 ) ) ≠ Δ z i } . \{I\ge i\}\cap\{\operatorname{hard}(\psi(z_{i-1}))\ne\Delta z_i\}. { I ≥ i } ∩ { hard ( ψ ( z i − 1 )) = Δ z i } .
Dropping the event { I ≥ i } \{I \ge i\} { I ≥ i } , which can only increase the probability, and using that ( z i − 1 , Δ z i ) (z_{i-1}, \Delta z_i) ( z i − 1 , Δ z i ) has law D i \mathcal{D}_i D i , we obtain
Pr D i ( I = i ) ≤ Pr D i ( hard ( ψ ( z i − 1 ) ) ≠ Δ z i ) . \Pr_{\mathcal{D}_i}(I=i) \le\Pr_{\mathcal{D}_i}\left(\operatorname{hard}(\psi(z_{i-1})) \ne\Delta z_i\right). D i Pr ( I = i ) ≤ D i Pr ( hard ( ψ ( z i − 1 )) = Δ z i ) .
Finally, applying the error floor of Lemma 7 pointwise and taking the expectation over D i \mathcal{D}_i D i gives
Pr D i ( hard ( ψ ( z i − 1 ) ) ≠ Δ z i ) ≤ k log 2 E D i [ L ( ψ ( z i − 1 ) , Δ z i ) ] = k R D i ( ψ ) log 2 . \Pr_{\mathcal{D}_i}\left(\operatorname{hard}(\psi(z_{i-1})) \ne\Delta z_i\right) \le\frac{k}{\log2}\mathbb{E}_{\mathcal{D}_i}\left[\mathcal{L}(\psi(z_{i-1}),\Delta z_i)\right] = \frac{kR_{\mathcal{D}_i}(\psi)}{\log2}. D i Pr ( hard ( ψ ( z i − 1 )) = Δ z i ) ≤ log 2 k E D i [ L ( ψ ( z i − 1 ) , Δ z i ) ] = log 2 k R D i ( ψ ) .
Summing over i = 1 , … , T − 1 i=1,\ldots,T-1 i = 1 , … , T − 1 thus gives
Pr ( I ≤ T − 1 ) ≤ k log 2 ∑ i = 1 T − 1 R D i ( ψ ) . \Pr(I\le T-1) \le\frac{k}{\log2}\sum_{i=1}^{T-1}R_{\mathcal{D}_i}(\psi). Pr ( I ≤ T − 1 ) ≤ log 2 k i = 1 ∑ T − 1 R D i ( ψ ) .
Finally, we combine the two estimates. Since ℓ ( p , y ) ≤ log ( 1 / ϵ ℓ ) \ell(p,y)\le\log(1/\epsilon_\ell) ℓ ( p , y ) ≤ log ( 1/ ϵ ℓ ) for all p , y p,y p , y , we may take B ℓ = log ( 1 / ϵ ℓ ) B_\ell=\log(1/\epsilon_\ell) B ℓ = log ( 1/ ϵ ℓ ) ; then ϵ ℓ < 1 / 4 \epsilon_\ell<1/4 ϵ ℓ < 1/4 and k ≥ 1 k\ge1 k ≥ 1 imply
B ℓ k log 2 ≥ 2 > 1 , \frac{B_\ell k}{\log2}\ge2>1, log 2 B ℓ k ≥ 2 > 1 ,
the single term R D T ( ψ ) R_{\mathcal{D}_T}(\psi) R D T ( ψ ) is dominated by B ℓ k log 2 R D T ( ψ ) \frac{B_\ell k}{\log2}R_{\mathcal{D}_T}(\psi) l o g 2 B ℓ k R D T ( ψ ) , and hence
R D ( F ψ ) ≤ B ℓ k log 2 ∑ i = 1 T R D i ( ψ ) . R_{\mathcal{D}}(F_\psi)\le\frac{B_\ell k}{\log2}\sum_{i=1}^{T}R_{\mathcal{D}_i}(\psi). R D ( F ψ ) ≤ log 2 B ℓ k i = 1 ∑ T R D i ( ψ ) .
Because each intermediate state z i − 1 z_{i-1} z i − 1 is deterministically constructed from the prefix ( z 0 , Δ z 1 , … , Δ z i − 1 ) (z_0,\Delta z_1,\ldots,\Delta z_{i-1}) ( z 0 , Δ z 1 , … , Δ z i − 1 ) , the joint law of ( z i − 1 , Δ z i ) (z_{i-1},\Delta z_i) ( z i − 1 , Δ z i ) induced by D ′ \mathcal{D}' D ′ is exactly the sub-task distribution D i \mathcal{D}_i D i ; marginalizing out the remaining variables, the bound becomes
R D ( F ψ ) ≤ B ℓ k log 2 ∑ i = 1 T ∫ L ( ψ ( z i − 1 ) , Δ z i ) d D i ( z i − 1 , Δ z i ) , R_{\mathcal{D}}(F_\psi)\le\frac{B_\ell k}{\log2}\sum_{i=1}^{T}\int\mathcal{L}(\psi(z_{i-1}),\Delta z_i)\,d\mathcal{D}_i(z_{i-1},\Delta z_i), R D ( F ψ ) ≤ log 2 B ℓ k i = 1 ∑ T ∫ L ( ψ ( z i − 1 ) , Δ z i ) d D i ( z i − 1 , Δ z i ) ,
which is the desired decomposition. The coefficient B ℓ k log 2 \frac{B_\ell k}{\log2} l o g 2 B ℓ k is thus depth-independent, with ( log 2 ) / k (\log2)/k ( log 2 ) / k the local error floor of Lemma 7. □
Proof of Theorem 2 (Rademacher Complexity Bound)
We first present the multi-distribution symmetrization lemma used in Section 3.2.
Lemma 8. Define the population risk R D i ( ψ ) : = ∫ L ( ψ ( z i − 1 ) , Δ z i ) d D i ( z i − 1 , Δ z i ) R_{\mathcal{D}_i}(\psi):=\int\mathcal{L}(\psi(z_{i-1}),\Delta z_i)d\mathcal{D}_i(z_{i-1},\Delta z_i) R D i ( ψ ) := ∫ L ( ψ ( z i − 1 ) , Δ z i ) d D i ( z i − 1 , Δ z i ) and empirical risk R ^ S i ( ψ ) : = 1 n ∑ ( z i − 1 , Δ z i ) ∈ S i L ( ψ ( z i − 1 ) , Δ z i ) \widehat{R}_{S_i}(\psi):=\frac{1}{n}\sum_{(z_{i-1},\Delta z_i)\in S_i}\mathcal{L}(\psi(z_{i-1}),\Delta z_i) R S i ( ψ ) := n 1 ∑ ( z i − 1 , Δ z i ) ∈ S i L ( ψ ( z i − 1 ) , Δ z i ) . We have:
E { S j ∼ D j n } j = 1 T [ sup ψ ∈ Ψ ( ∑ i = 1 T ( R D i ( ψ ) − R ^ S i ( ψ ) ) ) ] ≤ 2 T E { S j ∼ D j n } j = 1 T [ R ^ S 0 ( F ) ] , \mathbb{E}_{\{S_j\sim\mathcal{D}_j^n\}_{j=1}^{T}}\left[\sup_{\psi\in\Psi}\left(\sum_{i=1}^{T}\left(R_{\mathcal{D}_i}(\psi)-\widehat{R}_{S_i}(\psi)\right)\right)\right]\le2T\mathbb{E}_{\{S_j\sim\mathcal{D}_j^n\}_{j=1}^{T}}\left[\widehat{\mathfrak{R}}_{S_0}(\mathcal{F})\right], E { S j ∼ D j n } j = 1 T [ ψ ∈ Ψ sup ( i = 1 ∑ T ( R D i ( ψ ) − R S i ( ψ ) ) ) ] ≤ 2 T E { S j ∼ D j n } j = 1 T [ R S 0 ( F ) ] , where F = L ∘ Ψ \mathcal{F}=\mathcal{L}\circ\Psi F = L ∘ Ψ , S 0 = ⋃ i = 1 T S i S_0=\bigcup_{i=1}^{T}S_i S 0 = ⋃ i = 1 T S i , and R ^ S 0 ( F ) \widehat{\mathfrak{R}}_{S_0}(\mathcal{F}) R S 0 ( F ) is the empirical Rademacher complexity of F \mathcal{F} F on S 0 S_0 S 0 .
We now prove Lemma 8.
Proof. Let S 1 ′ , S 2 ′ , … , S T ′ S'_1,S'_2,\ldots,S'_T S 1 ′ , S 2 ′ , … , S T ′ be another set of i.i.d. samples, where S i ′ ∼ D i n S'_i\sim\mathcal{D}_i^n S i ′ ∼ D i n and
S i ′ = { ( x i 1 ′ , y i 1 ′ ) , ( x i 2 ′ , y i 2 ′ ) , … , ( x i n ′ , y i n ′ ) } for i = 1 , 2 , … , T . S'_i=\{(x'_{i1},y'_{i1}),(x'_{i2},y'_{i2}),\ldots,(x'_{in},y'_{in})\}\quad\text{for }i=1,2,\ldots,T. S i ′ = {( x i 1 ′ , y i 1 ′ ) , ( x i 2 ′ , y i 2 ′ ) , … , ( x in ′ , y in ′ )} for i = 1 , 2 , … , T .
Clearly, for all ψ ∈ Ψ \psi\in\Psi ψ ∈ Ψ , the population risk is the expectation of the empirical risk over the ghost sample:
R D i ( ψ ) = E { S j ′ ∼ D j n } j = 1 T [ R ^ S i ′ ( ψ ) ] . R_{\mathcal{D}_i}(\psi)=\mathbb{E}_{\{S'_j\sim\mathcal{D}_j^n\}_{j=1}^{T}}\left[\widehat{R}_{S'_i}(\psi)\right]. R D i ( ψ ) = E { S j ′ ∼ D j n } j = 1 T [ R S i ′ ( ψ ) ] .
Therefore, for every ψ ∈ Ψ \psi\in\Psi ψ ∈ Ψ , we have
R D i ( ψ ) − R ^ S i ( ψ ) = E { S j ′ ∼ D j n } j = 1 T [ R ^ S i ′ ( ψ ) − R ^ S i ( ψ ) ] . R_{\mathcal{D}_i}(\psi)-\widehat{R}_{S_i}(\psi)=\mathbb{E}_{\{S'_j\sim\mathcal{D}_j^n\}_{j=1}^{T}}\left[\widehat{R}_{S'_i}(\psi)-\widehat{R}_{S_i}(\psi)\right]. R D i ( ψ ) − R S i ( ψ ) = E { S j ′ ∼ D j n } j = 1 T [ R S i ′ ( ψ ) − R S i ( ψ ) ] .
Taking the supremum over ψ ∈ Ψ \psi\in\Psi ψ ∈ Ψ on both sides, and using the fact that the supremum of an expectation is upper bounded by the expectation of the supremum (Jensen’s inequality), we obtain
sup ψ ∈ Ψ ( ∑ i = 1 T ( R D i ( ψ ) − R ^ S i ( ψ ) ) ) = sup ψ ∈ Ψ E { S j ′ ∼ D j n j } j = 1 T [ ∑ i = 1 T ( R ^ S i ′ ( ψ ) − R ^ S i ( ψ ) ) ] ≤ E { S j ′ ∼ D j n j } j = 1 T [ sup ψ ∈ Ψ ( ∑ i = 1 T ( R ^ S i ′ ( ψ ) − R ^ S i ( ψ ) ) ) ] . \sup_{\psi\in\Psi}\left(\sum_{i=1}^{T}(R_{\mathcal{D}_i}(\psi)-\widehat{R}_{S_i}(\psi))\right)
= \sup_{\psi\in\Psi}\mathbb{E}_{\{S'_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T}}\left[\sum_{i=1}^{T}(\widehat{R}_{S'_i}(\psi)-\widehat{R}_{S_i}(\psi))\right]
\leq\mathbb{E}_{\{S'_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T}}\left[\sup_{\psi\in\Psi}\left(\sum_{i=1}^{T}(\widehat{R}_{S'_i}(\psi)-\widehat{R}_{S_i}(\psi))\right)\right]. ψ ∈ Ψ sup ( i = 1 ∑ T ( R D i ( ψ ) − R S i ( ψ )) ) = ψ ∈ Ψ sup E { S j ′ ∼ D j n j } j = 1 T [ i = 1 ∑ T ( R S i ′ ( ψ ) − R S i ( ψ )) ] ≤ E { S j ′ ∼ D j n j } j = 1 T [ ψ ∈ Ψ sup ( i = 1 ∑ T ( R S i ′ ( ψ ) − R S i ( ψ )) ) ] .
Taking expectation over { S j ∼ D j n j } j = 1 T \{S_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T} { S j ∼ D j n j } j = 1 T on both sides yields
E { S j ∼ D j n j } j = 1 T [ sup ψ ∈ Ψ ( ∑ i = 1 T ( R D i ( ψ ) − R ^ S i ( ψ ) ) ) ] ≤ E { S j ∼ D j n j } j = 1 T , { S j ′ ∼ D j n j } j = 1 T [ sup ψ ∈ Ψ ( ∑ i = 1 T ( R ^ S i ′ ( ψ ) − R ^ S i ( ψ ) ) ) ] = 1 n E { S j ∼ D j n j } j = 1 T , { S j ′ ∼ D j n j } j = 1 T [ sup ψ ∈ Ψ ( ∑ i = 1 T ∑ k = 1 n ( L ( ψ ( x i k ′ ) , y i k ′ ) − L ( ψ ( x i k ) , y i k ) ) ) ] . \begin{aligned}
\mathbb{E}_{\{S_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T}}\left[\sup_{\psi\in\Psi}\left(\sum_{i=1}^{T}(R_{\mathcal{D}_i}(\psi)-\widehat{R}_{S_i}(\psi))\right)\right]
\leq\mathbb{E}_{\{S_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T},\{S'_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T}}\left[\sup_{\psi\in\Psi}\left(\sum_{i=1}^{T}(\widehat{R}_{S'_i}(\psi)-\widehat{R}_{S_i}(\psi))\right)\right] \\
&=\frac{1}{n}\mathbb{E}_{\{S_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T},\{S'_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T}}\left[\sup_{\psi\in\Psi}\left(\sum_{i=1}^{T}\sum_{k=1}^{n}\bigl(\mathcal{L}(\psi(x'_{ik}),y'_{ik})-\mathcal{L}(\psi(x_{ik}),y_{ik})\bigr)\right)\right].
\end{aligned} E { S j ∼ D j n j } j = 1 T [ ψ ∈ Ψ sup ( i = 1 ∑ T ( R D i ( ψ ) − R S i ( ψ )) ) ] ≤ E { S j ∼ D j n j } j = 1 T , { S j ′ ∼ D j n j } j = 1 T [ ψ ∈ Ψ sup ( i = 1 ∑ T ( R S i ′ ( ψ ) − R S i ( ψ )) ) ] = n 1 E { S j ∼ D j n j } j = 1 T , { S j ′ ∼ D j n j } j = 1 T [ ψ ∈ Ψ sup ( i = 1 ∑ T k = 1 ∑ n ( L ( ψ ( x ik ′ ) , y ik ′ ) − L ( ψ ( x ik ) , y ik ) ) ) ] .
Next, we note that for each i i i and k k k , ( x i k , y i k ) (x_{ik},y_{ik}) ( x ik , y ik ) and ( x i k ′ , y i k ′ ) (x'_{ik},y'_{ik}) ( x ik ′ , y ik ′ ) are i.i.d. variables. Therefore, we can replace them without affecting the expectation. For any specific pair ( i , k ) (i,k) ( i , k ) , let the summation over the remaining indices be denoted by ∑ ( i ′ , k ′ ) ≠ ( i , k ) \sum_{(i',k')\ne(i,k)} ∑ ( i ′ , k ′ ) = ( i , k ) . We have:
E { S j ∼ D j n j } j = 1 T , { S j ′ ∼ D j n j } j = 1 T [ sup ψ ∈ Ψ ( ( L ( ψ ( x i k ′ ) , y i k ′ ) − L ( ψ ( x i k ) , y i k ) ) + ∑ ( i ′ , k ′ ) ≠ ( i , k ) ( L ( ψ ( x i ′ k ′ ′ ) , y i ′ k ′ ′ ) − L ( ψ ( x i ′ k ′ ) , y i ′ k ′ ) ) ) ] = E { S j ∼ D j n j } j = 1 T , { S j ′ ∼ D j n j } j = 1 T [ sup ψ ∈ Ψ ( ( − L ( ψ ( x i k ′ ) , y i k ′ ) + L ( ψ ( x i k ) , y i k ) ) + ∑ ( i ′ , k ′ ) ≠ ( i , k ) ( L ( ψ ( x i ′ k ′ ′ ) , y i ′ k ′ ′ ) − L ( ψ ( x i ′ k ′ ) , y i ′ k ′ ) ) ) ] . \begin{aligned}
&\mathbb{E}_{\{S_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T},\{S'_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T}}\left[\sup_{\psi\in\Psi}\left(\bigl(\mathcal{L}(\psi(x'_{ik}),y'_{ik})-\mathcal{L}(\psi(x_{ik}),y_{ik})\bigr)\right.\right.\\
&\qquad\left.\left.+\sum_{(i',k')\ne(i,k)}\bigl(\mathcal{L}(\psi(x'_{i'k'}),y'_{i'k'})-\mathcal{L}(\psi(x_{i'k'}),y_{i'k'})\bigr)\right)\right]\\
&=\mathbb{E}_{\{S_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T},\{S'_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T}}\left[\sup_{\psi\in\Psi}\left(\bigl(-\mathcal{L}(\psi(x'_{ik}),y'_{ik})+\mathcal{L}(\psi(x_{ik}),y_{ik})\bigr)\right.\right.\\
&\qquad\left.\left.+\sum_{(i',k')\ne(i,k)}\bigl(\mathcal{L}(\psi(x'_{i'k'}),y'_{i'k'})-\mathcal{L}(\psi(x_{i'k'}),y_{i'k'})\bigr)\right)\right].
\end{aligned} E { S j ∼ D j n j } j = 1 T , { S j ′ ∼ D j n j } j = 1 T [ ψ ∈ Ψ sup ( ( L ( ψ ( x ik ′ ) , y ik ′ ) − L ( ψ ( x ik ) , y ik ) ) + ( i ′ , k ′ ) = ( i , k ) ∑ ( L ( ψ ( x i ′ k ′ ′ ) , y i ′ k ′ ′ ) − L ( ψ ( x i ′ k ′ ) , y i ′ k ′ ) ) = E { S j ∼ D j n j } j = 1 T , { S j ′ ∼ D j n j } j = 1 T [ ψ ∈ Ψ sup ( ( − L ( ψ ( x ik ′ ) , y ik ′ ) + L ( ψ ( x ik ) , y ik ) ) + ( i ′ , k ′ ) = ( i , k ) ∑ ( L ( ψ ( x i ′ k ′ ′ ) , y i ′ k ′ ′ ) − L ( ψ ( x i ′ k ′ ) , y i ′ k ′ ) ) .
Let σ i k \sigma_{ik} σ ik be a random variable such that P [ σ i k = 1 ] = P [ σ i k = − 1 ] = 1 2 \mathbb{P}[\sigma_{ik}=1]=\mathbb{P}[\sigma_{ik}=-1]=\frac{1}{2} P [ σ ik = 1 ] = P [ σ ik = − 1 ] = 2 1 . Combining the two equalities above, we obtain:
E { S j ∼ D j n j } j = 1 T , { S j ′ ∼ D j n j } j = 1 T [ sup ψ ∈ Ψ ( ( L ( ψ ( x i k ′ ) , y i k ′ ) − L ( ψ ( x i k ) , y i k ) ) + ∑ ( i ′ , k ′ ) ≠ ( i , k ) ( L ( ψ ( x i ′ k ′ ′ ) , y i ′ k ′ ′ ) − L ( ψ ( x i ′ k ′ ) , y i ′ k ′ ) ) ) ] = E { S j ∼ D j n j } j = 1 T , { S j ′ ∼ D j n j } j = 1 T [ E σ i k sup ψ ∈ Ψ ( σ i k ( L ( ψ ( x i k ′ ) , y i k ′ ) − L ( ψ ( x i k ) , y i k ) ) + ∑ ( i ′ , k ′ ) ≠ ( i , k ) ( L ( ψ ( x i ′ k ′ ′ ) , y i ′ k ′ ′ ) − L ( ψ ( x i ′ k ′ ) , y i ′ k ′ ) ) ) ] . \begin{aligned}
&\mathbb{E}_{\{S_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T},\{S'_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T}}\left[\sup_{\psi\in\Psi}\left(\bigl(\mathcal{L}(\psi(x'_{ik}),y'_{ik})-\mathcal{L}(\psi(x_{ik}),y_{ik})\bigr)\right.\right.\\
&\qquad\left.\left.+\sum_{(i',k')\ne(i,k)}\bigl(\mathcal{L}(\psi(x'_{i'k'}),y'_{i'k'})-\mathcal{L}(\psi(x_{i'k'}),y_{i'k'})\bigr)\right)\right]\\
&=\mathbb{E}_{\{S_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T},\{S'_j\sim\mathcal{D}^{n_j}_j\}_{j=1}^{T}}\left[\mathbb{E}_{\sigma_{ik}}\sup_{\psi\in\Psi}\left(\sigma_{ik}\bigl(\mathcal{L}(\psi(x'_{ik}),y'_{ik})-\mathcal{L}(\psi(x_{ik}),y_{ik})\bigr)\right.\right.\\
&\qquad\left.\left.+\sum_{(i',k')\ne(i,k)}\bigl(\mathcal{L}(\psi(x'_{i'k'}),y'_{i'k'})-\mathcal{L}(\psi(x_{i'k'}),y_{i'k'})\bigr)\right)\right].
\end{aligned} E { S j ∼ D j n j } j = 1 T , { S j ′ ∼ D j n j } j = 1 T [ ψ ∈ Ψ sup ( ( L ( ψ ( x ik ′ ) , y ik ′ ) − L ( ψ ( x ik ) , y ik ) ) + ( i ′ , k ′ ) = ( i , k ) ∑ ( L ( ψ ( x i ′ k ′ ′ ) , y i ′ k ′ ′ ) − L ( ψ ( x i ′ k ′ ) , y i ′ k ′ ) ) = E { S j ∼ D j n j } j = 1 T , { S j ′ ∼ D j n j } j = 1 T [ E σ ik ψ ∈ Ψ sup ( σ ik ( L ( ψ ( x ik ′ ) , y ik ′ ) − L ( ψ ( x ik ) , y ik ) ) + ( i ′ , k ′ ) = ( i , k ) ∑ ( L ( ψ ( x i ′ k ′ ′ ) , y i ′ k ′ ′ ) − L ( ψ ( x i ′ k ′ ) , y i ′ k ′ ) ) .
The inner expectation over σ i k \sigma_{ik} σ ik splits the right-hand side into the two half-terms carrying signs + + + and − - − ; the swap symmetry of the i.i.d. pair ( x i k , y i k ) ↔ ( x i k ′ , y i k ′ ) (x_{ik},y_{ik})\leftrightarrow(x'_{ik},y'_{ik}) ( x ik , y ik ) ↔ ( x ik ′ , y ik ′ ) used in the preceding display shows that these two half-terms are equal, so the identity holds after averaging over σ i k \sigma_{ik} σ ik . Repeating this process for all i = 1 , … , T i = 1, \ldots, T i = 1 , … , T and k = 1 , … , n k = 1, \ldots, n k = 1 , … , n , we have
E { S j ∼ D j n } j = 1 T , { S j ′ ∼ D j n } j = 1 T [ sup ψ ∈ Ψ ( ∑ i = 1 T ∑ k = 1 n ( L ( ψ ( x i k ′ ) , y i k ′ ) − L ( ψ ( x i k ) , y i k ) ) ) ] = E { S j ∼ D j n } j = 1 T , { S j ′ ∼ D j n } j = 1 T , { { σ i k } i = 1 T } k = 1 n [ sup ψ ∈ Ψ ( ∑ i = 1 T ∑ k = 1 n σ i k ( L ( ψ ( x i k ′ ) , y i k ′ ) − L ( ψ ( x i k ) , y i k ) ) ) ] . \begin{aligned}
\mathbb{E}_{\{S_j\sim\mathcal{D}_j^n\}_{j=1}^{T},\{S'_j\sim\mathcal{D}_j^n\}_{j=1}^{T}}\left[\sup_{\psi\in\Psi}\left(\sum_{i=1}^{T}\sum_{k=1}^{n}\left(\mathcal{L}(\psi(x'_{ik}),y'_{ik})-\mathcal{L}(\psi(x_{ik}),y_{ik})\right)\right)\right] \\
=\mathbb{E}_{\{S_j\sim\mathcal{D}_j^n\}_{j=1}^{T},\{S'_j\sim\mathcal{D}_j^n\}_{j=1}^{T},\{\{\sigma_{ik}\}_{i=1}^{T}\}_{k=1}^{n}}\left[\sup_{\psi\in\Psi}\left(\sum_{i=1}^{T}\sum_{k=1}^{n}\sigma_{ik}\left(\mathcal{L}(\psi(x'_{ik}),y'_{ik})-\mathcal{L}(\psi(x_{ik}),y_{ik})\right)\right)\right].
\end{aligned} E { S j ∼ D j n } j = 1 T , { S j ′ ∼ D j n } j = 1 T [ ψ ∈ Ψ sup ( i = 1 ∑ T k = 1 ∑ n ( L ( ψ ( x ik ′ ) , y ik ′ ) − L ( ψ ( x ik ) , y ik ) ) ) ] = E { S j ∼ D j n } j = 1 T , { S j ′ ∼ D j n } j = 1 T , {{ σ ik } i = 1 T } k = 1 n [ ψ ∈ Ψ sup ( i = 1 ∑ T k = 1 ∑ n σ ik ( L ( ψ ( x ik ′ ) , y ik ′ ) − L ( ψ ( x ik ) , y ik ) ) ) ] .
Finally, applying the triangle inequality to the supremum:
sup ψ ∈ Ψ ∑ i = 1 T ∑ k = 1 n σ i k ( L ( ψ ( x i k ′ ) , y i k ′ ) − L ( ψ ( x i k ) , y i k ) ) ≤ sup ψ ∈ Ψ ∑ i = 1 T ∑ k = 1 n σ i k L ( ψ ( x i k ′ ) , y i k ′ ) + sup ψ ∈ Ψ ∑ i = 1 T ∑ k = 1 n − σ i k L ( ψ ( x i k ) , y i k ) . \begin{aligned}
\sup_{\psi\in\Psi}\sum_{i=1}^{T}\sum_{k=1}^{n}\sigma_{ik}\left(\mathcal{L}(\psi(x'_{ik}),y'_{ik})-\mathcal{L}(\psi(x_{ik}),y_{ik})\right)
&\leq\sup_{\psi\in\Psi}\sum_{i=1}^{T}\sum_{k=1}^{n}\sigma_{ik}\mathcal{L}(\psi(x'_{ik}),y'_{ik}) \\
&\quad+\sup_{\psi\in\Psi}\sum_{i=1}^{T}\sum_{k=1}^{n}-\sigma_{ik}\mathcal{L}(\psi(x_{ik}),y_{ik}).
\end{aligned} ψ ∈ Ψ sup i = 1 ∑ T k = 1 ∑ n σ ik ( L ( ψ ( x ik ′ ) , y ik ′ ) − L ( ψ ( x ik ) , y ik ) ) ≤ ψ ∈ Ψ sup i = 1 ∑ T k = 1 ∑ n σ ik L ( ψ ( x ik ′ ) , y ik ′ ) + ψ ∈ Ψ sup i = 1 ∑ T k = 1 ∑ n − σ ik L ( ψ ( x ik ) , y ik ) .
The joint distribution of the Rademacher signs is invariant under sign reversal. Taking expectations in the preceding inequality and using this symmetry for the second term, we get
E { S j ∼ D j n } j = 1 T , { S j ′ ∼ D j n } j = 1 T , { { σ i k } i = 1 T } k = 1 n [ sup ψ ∈ Ψ ∑ i = 1 T ∑ k = 1 n σ i k ( L ( ψ ( x i k ′ ) , y i k ′ ) − L ( ψ ( x i k ) , y i k ) ) ] ≤ E { S j ∼ D j n } j = 1 T , { S j ′ ∼ D j n } j = 1 T , { { σ i k } i = 1 T } k = 1 n [ sup ψ ∈ Ψ ∑ i = 1 T ∑ k = 1 n σ i k L ( ψ ( x i k ′ ) , y i k ′ ) ] + E { S j ∼ D j n } j = 1 T , { S j ′ ∼ D j n } j = 1 T , { { σ i k } i = 1 T } k = 1 n [ sup ψ ∈ Ψ ∑ i = 1 T ∑ k = 1 n σ i k L ( ψ ( x i k ) , y i k ) ] = 2 ⋅ E { S j ∼ D j n } j = 1 T [ n T ⋅ R ^ S 0 ( F ) ] = 2 n T ⋅ E { S j ∼ D j n } j = 1 T [ R ^ S 0 ( F ) ] . \begin{aligned}
&\mathbb{E}_{\{S_j\sim\mathcal{D}_j^n\}_{j=1}^{T},\{S'_j\sim\mathcal{D}_j^n\}_{j=1}^{T},\{\{\sigma_{ik}\}_{i=1}^{T}\}_{k=1}^{n}}\left[\sup_{\psi\in\Psi}\sum_{i=1}^{T}\sum_{k=1}^{n}\sigma_{ik}\left(\mathcal{L}(\psi(x'_{ik}),y'_{ik})-\mathcal{L}(\psi(x_{ik}),y_{ik})\right)\right] \\
&\leq\mathbb{E}_{\{S_j\sim\mathcal{D}_j^n\}_{j=1}^{T},\{S'_j\sim\mathcal{D}_j^n\}_{j=1}^{T},\{\{\sigma_{ik}\}_{i=1}^{T}\}_{k=1}^{n}}\left[\sup_{\psi\in\Psi}\sum_{i=1}^{T}\sum_{k=1}^{n}\sigma_{ik}\mathcal{L}(\psi(x'_{ik}),y'_{ik})\right] \\
&\quad+\mathbb{E}_{\{S_j\sim\mathcal{D}_j^n\}_{j=1}^{T},\{S'_j\sim\mathcal{D}_j^n\}_{j=1}^{T},\{\{\sigma_{ik}\}_{i=1}^{T}\}_{k=1}^{n}}\left[\sup_{\psi\in\Psi}\sum_{i=1}^{T}\sum_{k=1}^{n}\sigma_{ik}\mathcal{L}(\psi(x_{ik}),y_{ik})\right] \\
&=2\cdot\mathbb{E}_{\{S_j\sim\mathcal{D}_j^n\}_{j=1}^{T}}\left[nT\cdot\widehat{\mathfrak{R}}_{S_0}(\mathcal{F})\right]
=2nT\cdot\mathbb{E}_{\{S_j\sim\mathcal{D}_j^n\}_{j=1}^{T}}\left[\widehat{\mathfrak{R}}_{S_0}(\mathcal{F})\right].
\end{aligned} E { S j ∼ D j n } j = 1 T , { S j ′ ∼ D j n } j = 1 T , {{ σ ik } i = 1 T } k = 1 n [ ψ ∈ Ψ sup i = 1 ∑ T k = 1 ∑ n σ ik ( L ( ψ ( x ik ′ ) , y ik ′ ) − L ( ψ ( x ik ) , y ik ) ) ] ≤ E { S j ∼ D j n } j = 1 T , { S j ′ ∼ D j n } j = 1 T , {{ σ ik } i = 1 T } k = 1 n [ ψ ∈ Ψ sup i = 1 ∑ T k = 1 ∑ n σ ik L ( ψ ( x ik ′ ) , y ik ′ ) ] + E { S j ∼ D j n } j = 1 T , { S j ′ ∼ D j n } j = 1 T , {{ σ ik } i = 1 T } k = 1 n [ ψ ∈ Ψ sup i = 1 ∑ T k = 1 ∑ n σ ik L ( ψ ( x ik ) , y ik ) ] = 2 ⋅ E { S j ∼ D j n } j = 1 T [ n T ⋅ R S 0 ( F ) ] = 2 n T ⋅ E { S j ∼ D j n } j = 1 T [ R S 0 ( F ) ] .
Substituting this result into the previous equation involving the 1 / n 1/n 1/ n factor, we obtain the final bound:
E { S j ∼ D j n } j = 1 T [ sup ψ ∈ Ψ ( ∑ i = 1 T ( R D i ( ψ ) − R ^ S i ( ψ ) ) ) ] ≤ 1 n ⋅ 2 n T E { S j ∼ D j n } j = 1 T [ R ^ S 0 ( F ) ] = 2 T E { S j ∼ D j n } j = 1 T [ R ^ S 0 ( F ) ] . \begin{aligned}
\mathbb{E}_{\{S_j\sim\mathcal{D}_j^n\}_{j=1}^{T}}\left[\sup_{\psi\in\Psi}\left(\sum_{i=1}^{T}\left(R_{\mathcal{D}_i}(\psi)-\widehat{R}_{S_i}(\psi)\right)\right)\right]
&\leq\frac{1}{n}\cdot2nT\mathbb{E}_{\{S_j\sim\mathcal{D}_j^n\}_{j=1}^{T}}\left[\widehat{\mathfrak{R}}_{S_0}(\mathcal{F})\right] \\
&=2T\mathbb{E}_{\{S_j\sim\mathcal{D}_j^n\}_{j=1}^{T}}\left[\widehat{\mathfrak{R}}_{S_0}(\mathcal{F})\right].
\end{aligned} E { S j ∼ D j n } j = 1 T [ ψ ∈ Ψ sup ( i = 1 ∑ T ( R D i ( ψ ) − R S i ( ψ ) ) ) ] ≤ n 1 ⋅ 2 n T E { S j ∼ D j n } j = 1 T [ R S 0 ( F ) ] = 2 T E { S j ∼ D j n } j = 1 T [ R S 0 ( F ) ] .
Lemma 9 (McDiarmid’s Inequality[19 ] ). Let V V V be a domain, and let f : V n → R f : V^n \to\mathbb{R} f : V n → R be a function of n n n variables satisfying for some c > 0 c > 0 c > 0 , for all i ∈ [ n ] i \in[n] i ∈ [ n ] and all x 1 , … , x n , x i ′ ∈ V x_1,\ldots,x_n,x'_i \in V x 1 , … , x n , x i ′ ∈ V :
∣ f ( x 1 , … , x i , … , x n ) − f ( x 1 , … , x i ′ , … , x n ) ∣ ≤ c . \left|f(x_1,\ldots,x_i,\ldots,x_n)-f(x_1,\ldots,x'_i,\ldots,x_n)\right|\leq c. ∣ f ( x 1 , … , x i , … , x n ) − f ( x 1 , … , x i ′ , … , x n ) ∣ ≤ c . Let X 1 , X 2 , … , X n X_1,X_2,\ldots,X_n X 1 , X 2 , … , X n be independent random variables taking values in V V V . Then with probability at least 1 − δ 1-\delta 1 − δ :
∣ f ( X 1 , … , X n ) − E [ f ( X 1 , … , X n ) ] ∣ ≤ c n 2 ln ( 2 δ ) . \left|f(X_1,\ldots,X_n)-\mathbb{E}\left[f(X_1,\ldots,X_n)\right]\right|\leq c\sqrt{\frac{n}{2}\ln\left(\frac{2}{\delta}\right)}. ∣ f ( X 1 , … , X n ) − E [ f ( X 1 , … , X n ) ] ∣ ≤ c 2 n ln ( δ 2 ) .
Now we give the proof of Theorem 2.
Theorem 2 (Rademacher Complexity Bound). 1. Under the preceding conditions (where the step-level loss is bounded by B ℓ B_\ell B ℓ ), with probability at least 1 − δ 1-\delta 1 − δ :
∑ i = 1 T ( R D i ( ψ ) − R ^ S i ( ψ ) ) ≤ 2 T E { S j ∼ D j n } j = 1 T [ R ^ S 0 ( F ) ] + B ℓ 2 T log 2 δ n \sum_{i=1}^{T}\left(R_{D_i}(\psi)-\widehat{R}_{S_i}(\psi)\right) \le2T\mathbb{E}_{\{S_j\sim\mathcal{D}^n_j\}_{j=1}^{T}}\left[\widehat{\mathcal{R}}_{S_0}(\mathcal{F})\right]+B_\ell\sqrt{\frac{2T\log\frac{2}{\delta}}{n}} i = 1 ∑ T ( R D i ( ψ ) − R S i ( ψ ) ) ≤ 2 T E { S j ∼ D j n } j = 1 T [ R S 0 ( F ) ] + B ℓ n 2 T log δ 2 Under the preceding conditions (where the step-level loss is bounded by B ℓ B_\ell B ℓ ), with probability at least 1 − δ 1-\delta 1 − δ :
∣ ∑ i = 1 T ( R D i ( ψ ) − R ^ S i ( ψ ) ) ∣ ≤ 2 T R ^ S 0 ( F ) + 3 B ℓ 2 T log 4 δ n \left|\sum_{i=1}^{T}\left(R_{D_i}(\psi)-\widehat{R}_{S_i}(\psi)\right)\right| \le2T\widehat{\mathcal{R}}_{S_0}(\mathcal{F})+3B_\ell\sqrt{\frac{2T\log\frac{4}{\delta}}{n}} i = 1 ∑ T ( R D i ( ψ ) − R S i ( ψ ) ) ≤ 2 T R S 0 ( F ) + 3 B ℓ n 2 T log δ 4
Proof. We first prove the first inequality. Since ∑ i = 1 T ( R D i ( ψ ) − R ^ S i ( ψ ) ) \sum_{i=1}^{T}\left(R_{D_i}(\psi)-\widehat{R}_{S_i}(\psi)\right) ∑ i = 1 T ( R D i ( ψ ) − R S i ( ψ ) ) satisfies the conditions of Lemma 9 with T n Tn T n variables and constant 2 B ℓ / n 2B_\ell/n 2 B ℓ / n , applying Lemma 9 and then Lemma 8 yields that with probability at least 1 − δ 1-\delta 1 − δ :
∑ i = 1 T ( R D i ( ψ ) − R ^ S i ( ψ ) ) ≤ sup ψ ∈ Ψ ( ∑ i = 1 T ( R D i ( ψ ) − R ^ S i ( ψ ) ) ) ≤ E { S j ∼ D j n } j = 1 T [ sup ψ ∈ Ψ ( ∑ i = 1 T ( R D i ( ψ ) − R ^ S i ( ψ ) ) ) ] + B ℓ 2 T log 2 δ n \begin{aligned}
\sum_{i=1}^{T}\left(R_{D_i}(\psi)-\widehat{R}_{S_i}(\psi)\right) \\
&\le\sup_{\psi\in\Psi}\left(\sum_{i=1}^{T}\left(R_{D_i}(\psi)-\widehat{R}_{S_i}(\psi)\right)\right) \\
&\le\mathbb{E}_{\{S_j\sim\mathcal{D}^n_j\}_{j=1}^{T}}\left[\sup_{\psi\in\Psi}\left(\sum_{i=1}^{T}\left(R_{D_i}(\psi)-\widehat{R}_{S_i}(\psi)\right)\right)\right]+B_\ell\sqrt{\frac{2T\log\frac{2}{\delta}}{n}}
\end{aligned} i = 1 ∑ T ( R D i ( ψ ) − R S i ( ψ ) ) ≤ ψ ∈ Ψ sup ( i = 1 ∑ T ( R D i ( ψ ) − R S i ( ψ ) ) ) ≤ E { S j ∼ D j n } j = 1 T [ ψ ∈ Ψ sup ( i = 1 ∑ T ( R D i ( ψ ) − R S i ( ψ ) ) ) ] + B ℓ n 2 T log δ 2
≤ 2 T E { S j ∼ D j n } j = 1 T [ R ^ S 0 ( F ) ] + B ℓ 2 T log 2 δ n . \le2T\mathbb{E}_{\{S_j\sim\mathcal{D}^n_j\}_{j=1}^{T}}\left[\widehat{\mathcal{R}}_{S_0}(\mathcal{F})\right]+B_\ell\sqrt{\frac{2T\log\frac{2}{\delta}}{n}}. ≤ 2 T E { S j ∼ D j n } j = 1 T [ R S 0 ( F ) ] + B ℓ n 2 T log δ 2 .
For the second inequality, based on the first one, since R ^ S 0 ( F ) \widehat{\mathcal{R}}_{S_0}(\mathcal{F}) R S 0 ( F ) also satisfies the conditions of Lemma 9 (with T n Tn T n variables, constant 2 B ℓ / ( T n ) 2B_\ell/(Tn) 2 B ℓ / ( T n ) ), with probability at least 1 − 2 δ 1-2\delta 1 − 2 δ we have:
∑ i = 1 T ( R D i ( ψ ) − R ^ S i ( ψ ) ) \sum_{i=1}^{T}\left(R_{D_i}(\psi)-\widehat{R}_{S_i}(\psi)\right) i = 1 ∑ T ( R D i ( ψ ) − R S i ( ψ ) )
≤ 2 T E { S j ∼ D j n } j = 1 T [ R ^ S 0 ( F ) ] + B ℓ 2 T log 2 δ n \le2T\mathbb{E}_{\{S_j\sim\mathcal{D}^n_j\}_{j=1}^{T}}\left[\widehat{\mathcal{R}}_{S_0}(\mathcal{F})\right]+B_\ell\sqrt{\frac{2T\log\frac{2}{\delta}}{n}} ≤ 2 T E { S j ∼ D j n } j = 1 T [ R S 0 ( F ) ] + B ℓ n 2 T log δ 2
≤ 2 T R ^ S 0 ( F ) + 2 T ( 2 B ℓ n T n T log 2 δ 2 ) + B ℓ 2 T log 2 δ n = 2 T R ^ S 0 ( F ) + 3 B ℓ 2 T log 2 δ n . \begin{aligned}
\le2T\widehat{\mathcal{R}}_{S_0}(\mathcal{F})+2T\left(\frac{2B_\ell}{nT}\sqrt{\frac{nT\log\frac{2}{\delta}}{2}}\right)+B_\ell\sqrt{\frac{2T\log\frac{2}{\delta}}{n}} \\
&=2T\widehat{\mathcal{R}}_{S_0}(\mathcal{F})+3B_\ell\sqrt{\frac{2T\log\frac{2}{\delta}}{n}}.
\end{aligned} ≤ 2 T R S 0 ( F ) + 2 T n T 2 B ℓ 2 n T log δ 2 + B ℓ n 2 T log δ 2 = 2 T R S 0 ( F ) + 3 B ℓ n 2 T log δ 2 .
The reverse deviation follows by the same sign-symmetry argument. Using δ / 2 \delta/2 δ /2 in place of δ \delta δ converts the 1 − 2 δ 1-2\delta 1 − 2 δ event and the log ( 2 / δ ) \log(2/\delta) log ( 2/ δ ) factors above into the 1 − δ 1-\delta 1 − δ event and the log ( 4 / δ ) \log(4/\delta) log ( 4/ δ ) factors of part 2, without changing the coefficients. □
Proof of Corollary 3
Proof. Let U : = 2 T R ^ S 0 ( F ) + 3 B ℓ 2 T log ( 4 / δ ) / n U := 2T\widehat{\mathcal{R}}_{S_0}(\mathcal{F})+3B_\ell\sqrt{2T\log(4/\delta)/n} U := 2 T R S 0 ( F ) + 3 B ℓ 2 T log ( 4/ δ ) / n , so that Theorem 2 bounds ∣ ∑ i ( R D i ( ψ ) − R ^ S i ( ψ ) ) ∣ \left|\sum_i(R_{D_i}(\psi)-\widehat{R}_{S_i}(\psi))\right| ∑ i ( R D i ( ψ ) − R S i ( ψ )) by U U U uniformly over ψ \psi ψ , on an event of probability at least 1 − δ 1-\delta 1 − δ .
First display. Theorem 1 gives R D ( F ψ ) ≤ B ℓ k log 2 ∑ i R D i ( ψ ) R_D(F_\psi)\le\frac{B_\ell k}{\log2}\sum_i R_{D_i}(\psi) R D ( F ψ ) ≤ l o g 2 B ℓ k ∑ i R D i ( ψ ) ; replacing the population risks by their empirical counterparts costs at most U U U , and multiplying by B ℓ k / log 2 B_\ell k/\log2 B ℓ k / log 2 gives the first display. Second display. Let ψ ^ \hat{\psi} ψ ^ be the sub-task ERM and ψ ⋆ \psi^{\star} ψ ⋆ a population minimizer. Empirical optimality gives ∑ i R ^ S i ( ψ ^ ) ≤ ∑ i R ^ S i ( ψ ⋆ ) \sum_i \hat{R}_{S_i}(\hat{\psi}) \le\sum_i \hat{R}_{S_i}(\psi^{\star}) ∑ i R ^ S i ( ψ ^ ) ≤ ∑ i R ^ S i ( ψ ⋆ ) , so the atomic excess of ψ ^ \hat{\psi} ψ ^ obeys
∑ i R D i ( ψ ^ ) − ∑ i R D i ( ψ ⋆ ) = ∑ i ( R D i ( ψ ^ ) − R ^ S i ( ψ ^ ) ) + ∑ i ( R ^ S i ( ψ ^ ) − R ^ S i ( ψ ⋆ ) ) + ∑ i ( R ^ S i ( ψ ⋆ ) − R D i ( ψ ⋆ ) ) ≤ 2 U . \begin{aligned}
\sum_i R_{D_i}(\hat{\psi})-\sum_i R_{D_i}(\psi^{\star})=\sum_i\left(R_{D_i}(\hat{\psi})-\hat{R}_{S_i}(\hat{\psi})\right)+\sum_i\left(\hat{R}_{S_i}(\hat{\psi})-\hat{R}_{S_i}(\psi^{\star})\right) \\
&+\sum_i\left(\hat{R}_{S_i}(\psi^{\star})-R_{D_i}(\psi^{\star})\right)\le2U.
\end{aligned} i ∑ R D i ( ψ ^ ) − i ∑ R D i ( ψ ⋆ ) = i ∑ ( R D i ( ψ ^ ) − R ^ S i ( ψ ^ ) ) + i ∑ ( R ^ S i ( ψ ^ ) − R ^ S i ( ψ ⋆ ) ) + i ∑ ( R ^ S i ( ψ ⋆ ) − R D i ( ψ ⋆ ) ) ≤ 2 U .
Substituting ∑ i R D i ( ψ ^ ) ≤ ∑ i R D i ( ψ ⋆ ) + 2 U \sum_i R_{D_i}(\hat{\psi})\le\sum_i R_{D_i}(\psi^{\star})+2U ∑ i R D i ( ψ ^ ) ≤ ∑ i R D i ( ψ ⋆ ) + 2 U into the bound of Theorem 1 gives the second display. □
Proof of Corollary 4
Proof. By the oracle-prefix reduction of Theorem 1 the final-task risk is bounded by B ε k log 2 ∑ i = 1 T R D i ( ψ ) \frac{B\varepsilon k}{\log2}\sum_{i=1}^{T}R_{D_i}(\psi) l o g 2 B ε k ∑ i = 1 T R D i ( ψ ) ; transferring each term via R D i ( ψ ) ≤ R Q i ( ψ ) + disc F ( D i , Q i ) R_{D_i}(\psi)\le R_{Q_i}(\psi)+\operatorname{disc}_{\mathcal{F}}(D_i,Q_i) R D i ( ψ ) ≤ R Q i ( ψ ) + disc F ( D i , Q i ) and applying Theorem 2 to the Q i Q_i Q i proves the first display. The second follows from the same comparison with the deviation paid once for each of ψ ^ \hat{\psi} ψ ^ and ψ ⋆ \psi^{\star} ψ ⋆ , and the transfer from Q i Q_i Q i to D i D_i D i likewise paid twice. □
Teacher-Forced NTP Reduction
Lemma 10 (Teacher-Forced NTP Reduction). Under Assumption 1, consider the NTP setting of § 4.1 , with deterministic argmax decoding and the same context-window rule for teacher-forced and free-running prefixes. Then
R D ( F ψ g , h ) ≤ B ε k log 2 ∑ i = 1 T R D i k ( ψ g , h ) . R_D(F_{\psi_{g,h}})\le\frac{B\varepsilon k}{\log2}\sum_{i=1}^{T}R_{D_i}^{k}(\psi_{g,h}). R D ( F ψ g , h ) ≤ log 2 B ε k i = 1 ∑ T R D i k ( ψ g , h ) . The risks on the right are the teacher-forced target-token risks defined in Eq. (1) , whereas the risk on the left is evaluated on the free-running final prediction.
Proof. We follow the first-error argument of Theorem 1 , now locating the first erroneous token within the first erroneous block. Fix g g g , h h h , and let ψ : = ψ g , h \psi:=\psi_{g,h} ψ := ψ g , h be the block predictor given by k k k successive free-running next-token predictions via g ∘ h g\circ h g ∘ h . As in Appendix § 10 .§ 3 , let z = ( z 0 , Δ z 1 , … , Δ z T ) ∼ D ′ \mathbf{z}=(z_0,\Delta z_1,\ldots,\Delta z_T)\sim D' z = ( z 0 , Δ z 1 , … , Δ z T ) ∼ D ′ with joint law p ( z ) p(\mathbf{z}) p ( z ) , and write
z ^ 0 = z 0 , Δ z i ^ = hard ( ψ ( z ^ i − 1 ) ) , z ^ i = ψ ˉ ( z ^ i − 1 ) . \hat{z}_0=z_0,\qquad\widehat{\Delta z_i}=\operatorname{hard}(\psi(\hat{z}_{i-1})),\qquad\hat{z}_i=\bar{\psi}(\hat{z}_{i-1}). z ^ 0 = z 0 , Δ z i = hard ( ψ ( z ^ i − 1 )) , z ^ i = ψ ˉ ( z ^ i − 1 ) . For r = 1 , … , k r=1,\ldots,k r = 1 , … , k , let X i , < r X_{i,<r} X i , < r be the oracle context before token ( Δ z i ) r (\Delta z_i)_r ( Δ z i ) r , formed from z i − 1 z_{i-1} z i − 1 and the true within-step prefix ( Δ z i ) < r (\Delta z_i)_{<r} ( Δ z i ) < r . Let X ^ i , < r \hat{X}_{i,<r} X ^ i , < r be its free-running counterpart, formed from z ^ i − 1 \hat{z}_{i-1} z ^ i − 1 and ( Δ z i ^ ) < r (\widehat{\Delta z_i})_{<r} ( Δ z i ) < r . Both contexts use the same context-window rule, including truncation. For each oracle block, abbreviate its teacher-forced target-token loss by
q i : = 1 k ∑ r = 1 k ℓ ( g ( h ( X i , < r ) ) , ( Δ z i ) r ) . q_i:=\frac{1}{k}\sum_{r=1}^{k}\ell\left(g\left(h\left(X_{i,<r}\right)\right),(\Delta z_i)_r\right). q i := k 1 r = 1 ∑ k ℓ ( g ( h ( X i , < r ) ) , ( Δ z i ) r ) . This is Eq. (1) evaluated on the oracle record for step i i i ; consequently, ∫ q i d p ( z ) = R D i k ( ψ g , h ) \int q_i\,dp(\mathbf{z})=R_{D_i}^{k}(\psi_{g,h}) ∫ q i d p ( z ) = R D i k ( ψ g , h ) .
Define, as in the proof of Theorem 1 ,
u i : = 1 { Δ z i ^ ≠ Δ z i } , I : = inf { i ∈ { 1 , … , T } : u i = 1 } , u_i:=\mathbb{1}\left\{\widehat{\Delta z_i}\ne\Delta z_i\right\},\qquad I:=\inf\left\{i\in\{1,\ldots,T\}:u_i=1\right\}, u i := 1 { Δ z i = Δ z i } , I := inf { i ∈ { 1 , … , T } : u i = 1 } , with I = ∞ I=\infty I = ∞ if no error occurs. The same induction gives z ^ i − 1 = z i − 1 \hat{z}_{i-1}=z_{i-1} z ^ i − 1 = z i − 1 on { I ≥ i } \{I\ge i\} { I ≥ i } . On { I = i } \{I=i\} { I = i } , let r r r be the first position in block i i i with ( Δ z i ^ ) r ≠ ( Δ z i ) r (\widehat{\Delta z_i})_r\ne(\Delta z_i)_r ( Δ z i ) r = ( Δ z i ) r . Then
z ^ i − 1 = z i − 1 , ( Δ z i ^ ) < r = ( Δ z i ) < r , X ^ i , < r = X i , < r . \hat{z}_{i-1}=z_{i-1},\qquad(\widehat{\Delta z_i})_{<r}=(\Delta z_i)_{<r},\qquad\hat{X}_{i,<r}=X_{i,<r}. z ^ i − 1 = z i − 1 , ( Δ z i ) < r = ( Δ z i ) < r , X ^ i , < r = X i , < r .
Thus the erroneous hard prediction at this position is the argmax of the same probability vector g ( h ( X i , < r ) ) g(h(X_{i,<r})) g ( h ( X i , < r )) that appears in the teacher-forced loss. The probability assigned to the true token is therefore at most 1 / 2 1/2 1/2 . By the clipped cross-entropy calculation in Lemma 7,
ℓ ( g ( h ( X i , < r ) ) , ( Δ z i ) r ) ≥ log 2 , q i ≥ log 2 k on { I = i } . \ell(g(h(X_{i,<r})),(\Delta z_i)_r) \ge\log2,\qquad q_i \ge\frac{\log2}{k}\quad\text{on }\{I=i\}. ℓ ( g ( h ( X i , < r )) , ( Δ z i ) r ) ≥ log 2 , q i ≥ k log 2 on { I = i } .
This argument includes i = T i=T i = T , so it also accounts for errors within the final output block.
Next, split the final-step loss according to whether any hard error occurs. On { I > T } \{I>T\} { I > T } , all generated tokens agree with their oracle counterparts, including every prefix inside the final block, and hence
L ( ψ ( z ^ T − 1 ) , Δ z T ) = q T . \mathcal{L}(\psi(\widehat{z}_{T-1}),\Delta z_T)=q_T. L ( ψ ( z T − 1 ) , Δ z T ) = q T .
On { I = i } \{I=i\} { I = i } , boundedness gives L ( ψ ( z ^ T − 1 ) , Δ z T ) ≤ B ℓ \mathcal{L}(\psi(\widehat{z}_{T-1}),\Delta z_T)\le B_\ell L ( ψ ( z T − 1 ) , Δ z T ) ≤ B ℓ . Since B ℓ k / log 2 ≥ 1 B_\ell k/\log2\ge1 B ℓ k / log 2 ≥ 1 and the events { I > T } , { I = 1 } , … , { I = T } \{I>T\},\{I=1\},\ldots,\{I=T\} { I > T } , { I = 1 } , … , { I = T } form a partition, pointwise we obtain
L ( ψ ( z ^ T − 1 ) , Δ z T ) ≤ 1 { I > T } q T + B ℓ ∑ i = 1 T 1 { I = i } ≤ B ℓ k log 2 [ 1 { I > T } q T + ∑ i = 1 T 1 { I = i } q i ] ≤ B ℓ k log 2 ∑ i = 1 T q i . \begin{aligned}
\mathcal{L}(\psi(\widehat{z}_{T-1}),\Delta z_T)\le\mathbf{1}\{I>T\}q_T+B_\ell\sum_{i=1}^{T}\mathbf{1}\{I=i\} \\
&\le\frac{B_\ell k}{\log2}\left[\mathbf{1}\{I>T\}q_T+\sum_{i=1}^{T}\mathbf{1}\{I=i\}q_i\right] \\
&\le\frac{B_\ell k}{\log2}\sum_{i=1}^{T}q_i.
\end{aligned} L ( ψ ( z T − 1 ) , Δ z T ) ≤ 1 { I > T } q T + B ℓ i = 1 ∑ T 1 { I = i } ≤ log 2 B ℓ k [ 1 { I > T } q T + i = 1 ∑ T 1 { I = i } q i ] ≤ log 2 B ℓ k i = 1 ∑ T q i .
Finally, integrating against p ( z ) p(z) p ( z ) and using the oracle step marginals D i \mathcal{D}_i D i yields
R D ( F ψ g , h ) ≤ B ℓ k log 2 ∑ i = 1 T ∫ q i d p ( z ) = B ℓ k log 2 ∑ i = 1 T R D i k ( ψ g , h ) , R_{\mathcal{D}}(F_{\psi_{g,h}})\le\frac{B_\ell k}{\log2}\sum_{i=1}^{T}\int q_i\,\mathrm{d}p(z)=\frac{B_\ell k}{\log2}\sum_{i=1}^{T}R_{\mathcal{D}_i}^{k}(\psi_{g,h}), R D ( F ψ g , h ) ≤ log 2 B ℓ k i = 1 ∑ T ∫ q i d p ( z ) = log 2 B ℓ k i = 1 ∑ T R D i k ( ψ g , h ) ,
which proves the claim. The argument uses equality of the two prefixes only before the first hard error; it does not identify the teacher-forced and free-running block losses after that error. □
Proof of Theorem 5
Proof. Apply Theorem 2 to the bounded sequence-level class Q k Q_k Q k and the samples S i ∼ D i n S_i\sim\mathcal{D}_i^n S i ∼ D i n . Uniformly over g ∈ G g\in\mathcal{G} g ∈ G and h ∈ H h\in\mathcal{H} h ∈ H ,
∣ ∑ i = 1 T ( R D i k ( ψ g , h ) − R ^ S i k ( ψ g , h ) ) ∣ ≤ 2 T R ^ S 0 ( Q k ) + 3 B ℓ 2 T log ( 4 / δ ) n , \left|\sum_{i=1}^{T}\left(R_{\mathcal{D}_i}^{k}(\psi_{g,h})-\widehat{R}_{S_i}^{k}(\psi_{g,h})\right)\right|\le2T\widehat{\mathfrak{R}}_{S_0}(Q_k)+3B_\ell\sqrt{\frac{2T\log(4/\delta)}{n}}, i = 1 ∑ T ( R D i k ( ψ g , h ) − R S i k ( ψ g , h ) ) ≤ 2 T R S 0 ( Q k ) + 3 B ℓ n 2 T log ( 4/ δ ) ,
which is (2) .
For the ERM comparison, the three-term decomposition of the proof of Corollary 3 (Appendix B.5) applies verbatim with F \mathcal{F} F replaced by Q k Q_k Q k and R D i R_{\mathcal{D}_i} R D i by R D i k R_{\mathcal{D}_i}^{k} R D i k : writing E k ( ψ ^ ) : = ∑ i R D i k ( ψ ^ ) − ∑ i R D i k ( ψ g ⋆ , h ⋆ ) \mathcal{E}_k(\widehat{\psi}):=\sum_i R_{\mathcal{D}_i}^{k}(\widehat{\psi})-\sum_i R_{\mathcal{D}_i}^{k}(\psi_{g^\star,h^\star}) E k ( ψ ) := ∑ i R D i k ( ψ ) − ∑ i R D i k ( ψ g ⋆ , h ⋆ ) for the target-token atomic excess and U k : = 2 T R ^ S 0 ( Q k ) + 3 B ℓ 2 T log ( 4 / δ ) / n U_k:=2T\widehat{\mathfrak{R}}_{S_0}(Q_k)+3B_\ell\sqrt{2T\log(4/\delta)/n} U k := 2 T R S 0 ( Q k ) + 3 B ℓ 2 T log ( 4/ δ ) / n , empirical optimality and the two directions of the same uniform event give E k ( ψ ^ ) ≤ U k + 0 + U k \mathcal{E}_k(\widehat{\psi})\le U_k+0+U_k E k ( ψ ) ≤ U k + 0 + U k .
Lemma 10 then gives
R D ( F ψ g ^ , h ^ ) ≤ B ℓ k log 2 ∑ i = 1 T R D i k ( ψ ^ ) = B ℓ k log 2 [ ∑ i = 1 T R D i k ( ψ g ⋆ , h ⋆ ) + E k ( ψ ^ ) ] , R_{\mathcal{D}}(F_{\psi_{\widehat{g},\widehat{h}}})\le\frac{B_\ell k}{\log2}\sum_{i=1}^{T}R_{\mathcal{D}_i}^{k}(\widehat{\psi})=\frac{B_\ell k}{\log2}\left[\sum_{i=1}^{T}R_{\mathcal{D}_i}^{k}(\psi_{g^\star,h^\star})+\mathcal{E}_k(\widehat{\psi})\right], R D ( F ψ g , h ) ≤ log 2 B ℓ k i = 1 ∑ T R D i k ( ψ ) = log 2 B ℓ k [ i = 1 ∑ T R D i k ( ψ g ⋆ , h ⋆ ) + E k ( ψ ) ] ,
which is (3) after substituting U k + 0 + U k = 4 T R ^ S 0 ( Q k ) + 6 B ℓ 2 T log ( 4 / δ ) / n U_k+0+U_k=4T\widehat{\mathfrak{R}}_{S_0}(Q_k)+6B_\ell\sqrt{2T\log(4/\delta)/n} U k + 0 + U k = 4 T R S 0 ( Q k ) + 6 B ℓ 2 T log ( 4/ δ ) / n . The projection and loss-cover argument in Appendix A.2 gives (4) . □
Tightness of the Additive Reduction
Proposition 11 (Tightness of the Additive Reduction). For every T ≥ 1 T\ge1 T ≥ 1 and every p ∈ [ 0 , 1 / T ] p\in[0,1/T] p ∈ [ 0 , 1/ T ] there is a task with the following complete description. Let V = { 0 , 1 } V=\{0,1\} V = { 0 , 1 } , k = 1 k=1 k = 1 , m = T + 1 m=T+1 m = T + 1 , and draw
u 1 , … , u T u_1,\ldots,u_T u 1 , … , u T i.i.d. Bernoulli(p p p ). The oracle trajectory is z 0 = ( u 1 , … , u T , 0 ) z_0=(u_1,\ldots,u_T,0) z 0 = ( u 1 , … , u T , 0 ) with Δ z i = 0 \Delta z_i=0 Δ z i = 0 for every i i i , so that the oracle state before step i i i is z i − 1 = ( u i , … , u T , 0 , … , 0 ) z_{i-1}=(u_i,\ldots,u_T,0,\ldots,0) z i − 1 = ( u i , … , u T , 0 , … , 0 ) , whose first token is u i u_i u i and whose last token is 0 0 0 , and the step marginal D i D_i D i is the law of ( z i − 1 , 0 ) (z_{i-1},0) ( z i − 1 , 0 ) induced by ( u i , … , u T ) (u_i,\ldots,u_T) ( u i , … , u T ) . The shared single-step predictor is the deterministic rule hard ( ψ ( z ) ) = max { ( z ) 1 , ( z ) m } \operatorname{hard}(\psi(z))=\max\{(z)_1,(z)_m\} hard ( ψ ( z )) = max {( z ) 1 , ( z ) m } , with ψ ( z ) \psi(z) ψ ( z ) putting probability 1 1 1 on that token, so that the clipped cross-entropy of Assumption 1 charges 0 0 0 when the output is correct and B ℓ = log ( 1 / ϵ ℓ ) B_\ell=\log(1/\epsilon_\ell) B ℓ = log ( 1/ ϵ ℓ ) otherwise. Writing e 0 = 0 e_0=0 e 0 = 0 and e i = e i − 1 ∨ u i e_i=e_{i-1}\lor u_i e i = e i − 1 ∨ u i for the error flag (∨ \lor ∨ is logical OR, and a local error puts the state in an absorbing error mode), this task satisfies
R D ( F ψ ) = B ℓ [ 1 − ( 1 − p ) T ] = Ω ( ∑ i = 1 T R D i ( ψ ) ) , ∑ i = 1 T R D i ( ψ ) = T p B ℓ . R_D(F_\psi)=B_\ell\left[1-(1-p)^T\right]=\Omega\left(\sum_{i=1}^{T}R_{D_i}(\psi)\right),\qquad\sum_{i=1}^{T}R_{D_i}(\psi)=TpB_\ell. R D ( F ψ ) = B ℓ [ 1 − ( 1 − p ) T ] = Ω ( i = 1 ∑ T R D i ( ψ ) ) , i = 1 ∑ T R D i ( ψ ) = T p B ℓ .
Proof. Verify the construction of the statement. On an oracle state the last token is 0 0 0 , so the hard output equals u i u_i u i and the error event is u i = 1 u_i=1 u i = 1 ; hence R D i ( ψ ) = p B ℓ R_{D_i}(\psi)=pB_\ell R D i ( ψ ) = p B ℓ . Once an error occurs, its output 1 1 1 becomes the last token of every later state and the rule keeps emitting 1 1 1 , so the final output is wrong exactly when ⋁ i = 1 T u i = 1 \bigvee_{i=1}^{T}u_i=1 ⋁ i = 1 T u i = 1 , which gives
R D ( F ψ ) = B ℓ Pr ( ⋁ i = 1 T u i = 1 ) = B ℓ [ 1 − ( 1 − p ) T ] . R_D(F_\psi)=B_\ell\Pr\left(\bigvee_{i=1}^{T}u_i=1\right)=B_\ell\left[1-(1-p)^T\right]. R D ( F ψ ) = B ℓ Pr ( i = 1 ⋁ T u i = 1 ) = B ℓ [ 1 − ( 1 − p ) T ] .
The union bound gives 1 − ( 1 − p ) T ≤ T p 1-(1-p)^T\le Tp 1 − ( 1 − p ) T ≤ T p , and for T p ≤ 1 Tp\le1 T p ≤ 1 , 1 − ( 1 − p ) T ≥ T p − ( T 2 ) p 2 ≥ 1 2 T p 1-(1-p)^T\ge Tp-\binom{T}{2}p^2\ge\frac{1}{2}Tp 1 − ( 1 − p ) T ≥ T p − ( 2 T ) p 2 ≥ 2 1 T p . Consequently
1 2 T p B ℓ ≤ R D ( F ψ ) ≤ T p B ℓ = ∑ i = 1 T R D i ( ψ ) , \frac{1}{2}TpB_\ell\le R_D(F_\psi)\le TpB_\ell=\sum_{i=1}^{T}R_{D_i}(\psi), 2 1 T p B ℓ ≤ R D ( F ψ ) ≤ T p B ℓ = i = 1 ∑ T R D i ( ψ ) ,
hence R D ( F ψ ) = Ω ( ∑ i = 1 T R D i ( ψ ) ) R_D(F_\psi)=\Omega\left(\sum_{i=1}^{T}R_{D_i}(\psi)\right) R D ( F ψ ) = Ω ( ∑ i = 1 T R D i ( ψ ) ) , which proves the order-tightness of the additive reduction. □
What the construction shows. The witness combines two features: the local error events are independent across steps, and the state carries an absorbing error flag, so that the final output is wrong exactly when at least one local error has occurred. That event has probability 1 − ( 1 − p ) T = Θ ( T p ) 1-(1-p)^T=\Theta(Tp) 1 − ( 1 − p ) T = Θ ( T p ) for T p ≤ 1 Tp\le1 T p ≤ 1 , of the same order as the sum of the T T T step risks, while the per-step risk itself is R D i ( ψ ) = p B ℓ R_{D_i}(\psi)=pB_\ell R D i ( ψ ) = p B ℓ . The additive form of Theorem 1 is therefore tight up to its depth-independent coefficient, and the linear-in-T T T growth of the bound—here the genuine linear growth of the target risk—cannot be removed by any refinement of the argument.
Tightness of the Atomic Excess
Proposition 12 (Tightness of the Atomic Excess). Fix T = 4 r + 1 T=4r+1 T = 4 r + 1 with r ∈ N r\in\mathbb{N} r ∈ N , r ≥ 1 r\ge1 r ≥ 1 , a sign θ ∈ { − 1 , + 1 } \theta\in\{-1,+1\} θ ∈ { − 1 , + 1 } , and γ ∈ ( 0 , 1 / ( 2 T ) ] \gamma\in(0,1/(2T)] γ ∈ ( 0 , 1/ ( 2 T )] ; the sign θ \theta θ only selects which of the two hypotheses is favoured, and the constants below do not depend on it. Let V = { 0 , 1 } \mathcal{V}=\{0,1\} V = { 0 , 1 } , k = 1 k=1 k = 1 , m = T + 1 m=T+1 m = T + 1 , and let P θ P_\theta P θ be the law on { 0 , 1 } T \{0,1\}^{T} { 0 , 1 } T that assigns weight 1 2 T + θ γ \frac{1}{2T}+\theta\gamma 2 T 1 + θ γ to each vector u ( j ) ∈ { 0 , 1 } T u^{(j)}\in\{0,1\}^{T} u ( j ) ∈ { 0 , 1 } T , j ∈ [ T ] j\in[T] j ∈ [ T ] , whose support is the cyclic block { j , j + 1 , … , j + 2 r } \{j,j+1,\ldots,j+2r\} { j , j + 1 , … , j + 2 r } of 2 r + 1 2r+1 2 r + 1 consecutive coordinates (indices modulo T T T ), and weight 1 2 T − θ γ \frac{1}{2T}-\theta\gamma 2 T 1 − θ γ to u ( j ) u^{(j)} u ( j ) , the same block with its leading coordinate j j j flipped, so that u ( j ) u^{(j)} u ( j ) has ones exactly on { j + 1 , … , j + 2 r } \{j+1,\ldots,j+2r\} { j + 1 , … , j + 2 r } ; these 2 T 2T 2 T weights sum to one. For X ∼ P θ X\sim P_\theta X ∼ P θ , P θ ( X i = 1 ) = 1 2 + θ γ P_\theta(X_i=1)=\frac{1}{2}+\theta\gamma P θ ( X i = 1 ) = 2 1 + θ γ and P θ ( ⨁ i = 1 T X i = 1 ) = 1 2 + θ T γ P_\theta\left(\bigoplus_{i=1}^{T}X_i=1\right)=\frac{1}{2}+\theta T\gamma P θ ( ⨁ i = 1 T X i = 1 ) = 2 1 + θ T γ , where ⊕ \oplus ⊕ denotes bitwise XOR in this construction (not sequence concatenation). The oracle trajectory is z 0 = ( X 1 , … , X T , 0 ) z_0=(X_1,\ldots,X_T,0) z 0 = ( X 1 , … , X T , 0 ) with Δ z i = p i \Delta z_i=p_i Δ z i = p i and p i = p i − 1 ⊕ X i p_i=p_{i-1}\oplus X_i p i = p i − 1 ⊕ X i , p 0 = 0 p_0=0 p 0 = 0 , so that the state before step i i i exposes X i X_i X i as its first token and p i − 1 p_{i-1} p i − 1 as its last token, and D i θ D_i^\theta D i θ is the law of the i i i -th oracle state and its update. The two-element class F = { ψ 0 , ψ 1 } \mathcal{F}=\{\psi_0,\psi_1\} F = { ψ 0 , ψ 1 } , with ψ s ( z ) \psi_s(z) ψ s ( z ) putting probability 3 / 4 3/4 3/4 on token ( z ) m ⊕ s (z)_m\oplus s ( z ) m ⊕ s and 1 / 4 1/4 1/4 on the other token, so that a correct output costs ℓ o k = log ( 4 / 3 ) \ell_{\mathrm{ok}}=\log(4/3) ℓ ok = log ( 4/3 ) and a wrong one ℓ e r r = log 4 \ell_{\mathrm{err}}=\log4 ℓ err = log 4 (clipping is inactive since ϵ ℓ < 1 / 4 \epsilon_\ell<1/4 ϵ ℓ < 1/4 ). With n n n i.i.d. draws from each D i θ D_i^\theta D i θ , the sub-task ERM ψ ^ = arg min ψ ∈ F ∑ i = 1 T R ^ D i ( ψ ) \hat{\psi}=\arg\min_{\psi\in\mathcal{F}}\sum_{i=1}^{T}\widehat{R}_{D_i}(\psi) ψ ^ = arg min ψ ∈ F ∑ i = 1 T R D i ( ψ ) satisfies, for γ = c 0 min { 1 / n T , 1 / T } \gamma=c_0\min\{1/\sqrt{nT},1/T\} γ = c 0 min { 1/ n T , 1/ T } with a universal constant c 0 ≤ 1 / 2 c_0\le1/2 c 0 ≤ 1/2 ,
E S [ ∑ i = 1 T R D i θ ( ψ ^ ) − min ψ ∈ F { ∑ i = 1 T R D i θ ( ψ ) } ] = Ω ( min { 1 , T n } ) . \mathbb{E}_{\mathbb{S}}\left[\sum_{i=1}^{T}R_{D_i}^{\theta}(\hat{\psi})-\min_{\psi\in\mathcal{F}}\left\{\sum_{i=1}^{T}R_{D_i}^{\theta}(\psi)\right\}\right]=\Omega\left(\min\left\{1,\sqrt{\frac{T}{n}}\right\}\right). E S [ i = 1 ∑ T R D i θ ( ψ ^ ) − ψ ∈ F min { i = 1 ∑ T R D i θ ( ψ ) } ] = Ω ( min { 1 , n T } ) . In this construction the atomic excess coincides with the final-task excess, so the same bound holds for E S [ R D θ ( F ψ ^ ) − min ψ ∈ F R D θ ( F ψ ) ] \mathbb{E}_{\mathbb{S}}\left[R_D^\theta(F_{\hat{\psi}})-\min_{\psi\in\mathcal{F}}R_D^\theta(F_\psi)\right] E S [ R D θ ( F ψ ^ ) − min ψ ∈ F R D θ ( F ψ ) ] , and it is Ω ( T / n ) \Omega(\sqrt{T/n}) Ω ( T / n ) when T ≤ n T\le n T ≤ n .
Proof. Verify the construction of the statement. The weights of P θ P_\theta P θ are nonnegative and sum to one; each u ( j ) u^{(j)} u ( j ) has odd parity and each v ( j ) v^{(j)} v ( j ) even parity, and each coordinate lies in exactly 2 r + 1 2r+1 2 r + 1 of the u ( j ) u^{(j)} u ( j ) and 2 r 2r 2 r of the v ( j ) v^{(j)} v ( j ) , so that for every coordinate i i i
P θ ( X i = 1 ) = 1 2 + θ γ , P θ ( ⨁ i = 1 T X i = 1 ) = 1 2 + θ T γ . (6) P_\theta(X_i=1)=\frac{1}{2}+\theta\gamma,\qquad P_\theta\left(\bigoplus_{i=1}^{T}X_i=1\right)=\frac{1}{2}+\theta T\gamma. \tag*{(6)} P θ ( X i = 1 ) = 2 1 + θ γ , P θ ( i = 1 ⨁ T X i = 1 ) = 2 1 + θ T γ . (6)
The oracle performs serial XOR, so the final target is p T = ⨁ i = 1 T X i p_T=\bigoplus_{i=1}^{T}X_i p T = ⨁ i = 1 T X i . At atomic step i i i , ψ s \psi_s ψ s incurs loss ℓ o k \ell_{\mathrm{ok}} ℓ ok when X i = s X_i=s X i = s and ℓ e r r \ell_{\mathrm{err}} ℓ err otherwise; hence
R D i θ ( ψ s ) = ℓ o k + Δ ℓ P θ ( X i ≠ s ) , Δ ℓ = ℓ e r r − ℓ o k = log 3. R_{\mathcal{D}_i}^{\theta}(\psi_s)=\ell_{\mathrm{ok}}+\Delta_\ell P_\theta(X_i\ne s),\qquad\Delta_\ell=\ell_{\mathrm{err}}-\ell_{\mathrm{ok}}=\log3. R D i θ ( ψ s ) = ℓ ok + Δ ℓ P θ ( X i = s ) , Δ ℓ = ℓ err − ℓ ok = log 3.
Writing s θ = ( 1 + θ ) / 2 s_\theta=(1+\theta)/2 s θ = ( 1 + θ ) /2 , Eq. (6) gives
∑ i = 1 T [ R D i θ ( ψ 1 − s θ ) − R D i θ ( ψ s θ ) ] = 2 Δ ℓ T γ . (7) \sum_{i=1}^{T}\left[R_{\mathcal{D}_i}^{\theta}(\psi_{1-s_\theta})-R_{\mathcal{D}_i}^{\theta}(\psi_{s_\theta})\right]=2\Delta_\ell T\gamma. \tag*{(7)} i = 1 ∑ T [ R D i θ ( ψ 1 − s θ ) − R D i θ ( ψ s θ ) ] = 2 Δ ℓ T γ . (7)
The learned rollout uses the same s s s at every step. Since T T T is odd, its final hard output is s s s , so the final loss is ℓ o k \ell_{\mathrm{ok}} ℓ ok when p T = s p_T=s p T = s and ℓ e r r \ell_{\mathrm{err}} ℓ err otherwise, and
R D θ ( F ψ 1 − s θ ) − R D θ ( F ψ s θ ) = 2 Δ ℓ T γ . (8) R_{\mathcal{D}}^{\theta}(F_{\psi_{1-s_\theta}})-R_{\mathcal{D}}^{\theta}(F_{\psi_{s_\theta}})=2\Delta_\ell T\gamma. \tag*{(8)} R D θ ( F ψ 1 − s θ ) − R D θ ( F ψ s θ ) = 2 Δ ℓ T γ . (8)
Equations (7) and (8) show that the atomic excess equals the final excess exactly.
For training, step i i i uses only the i i i -th coordinate of its own draws, written X i 1 , … , X i n X_{i1},\ldots,X_{in} X i 1 , … , X in , so the n T nT n T coordinates X i j X_{ij} X ij used are independent. The sub-task ERM therefore chooses
s ^ = 1 { ∑ i = 1 T ∑ j = 1 n X i j ≥ n T 2 } . \hat{s}=\mathbb{1}\left\{\sum_{i=1}^{T}\sum_{j=1}^{n}X_{ij}\ge\frac{nT}{2}\right\}. s ^ = 1 { i = 1 ∑ T j = 1 ∑ n X ij ≥ 2 n T } .
a majority test on n T nT n T independent Bernoulli variables with mean 1 / 2 + θ γ 1/2+\theta\gamma 1/2 + θ γ . The choice of γ \gamma γ guarantees 0 < γ ≤ 1 / ( 2 T ) 0<\gamma\le1/(2T) 0 < γ ≤ 1/ ( 2 T ) , and standard binomial anti-concentration gives a universal c 1 > 0 c_1>0 c 1 > 0 such that P θ ( s ^ ≠ s θ ) ≥ c 1 P_\theta(\hat{s}\ne s_\theta)\ge c_1 P θ ( s ^ = s θ ) ≥ c 1 . Whenever the wrong hypothesis is selected, Eq. (7) gives atomic excess 2 Δ ℓ T γ 2\Delta_\ell T\gamma 2 Δ ℓ T γ . Therefore
E S [ ∑ i = 1 T R D i θ ( ψ s ^ ) − min ψ ∈ Ψ { ∑ i = 1 T R D i θ ( ψ ) } ] ≥ 2 c 1 Δ ℓ T γ = Ω ( min { 1 , T n } ) . \mathbb{E}_{S}\left[\sum_{i=1}^{T}R_{\mathcal{D}_i}^{\theta}(\psi_{\hat{s}})-\min_{\psi\in\Psi}\left\{\sum_{i=1}^{T}R_{\mathcal{D}_i}^{\theta}(\psi)\right\}\right]\ge2c_1\Delta_\ell T\gamma=\Omega\left(\min\left\{1,\sqrt{\frac{T}{n}}\right\}\right). E S [ i = 1 ∑ T R D i θ ( ψ s ^ ) − ψ ∈ Ψ min { i = 1 ∑ T R D i θ ( ψ ) } ] ≥ 2 c 1 Δ ℓ T γ = Ω ( min { 1 , n T } ) .
By Eq. (8) the atomic excess equals the final-task excess here, so the same bound holds for E S [ R D θ ( F ψ s ^ ) − min ψ ∈ Ψ R D θ ( F ψ ) ] \mathbb{E}_{S}[R_{\mathcal{D}}^{\theta}(F_{\psi_{\hat{s}}})-\min_{\psi\in\Psi}R_{\mathcal{D}}^{\theta}(F_\psi)] E S [ R D θ ( F ψ s ^ ) − min ψ ∈ Ψ R D θ ( F ψ )] ; it is Ω ( T / n ) \Omega(\sqrt{T/n}) Ω ( T / n ) when T ≤ n T\le n T ≤ n .
What the lower bound certifies. The quantity bounded below is exactly the sample-dependent atomic excess of the upper bound—the sub-task ERM’s excess over the best in-class value—and it coincides with the final-task excess. Since the per-step best-in-class loss is Θ ( 1 ) \Theta(1) Θ ( 1 ) (ℓ o k + 1 2 Δ ℓ ≈ 0.837 \ell_{\mathrm{ok}}+\frac{1}{2}\Delta_\ell\approx0.837 ℓ ok + 2 1 Δ ℓ ≈ 0.837 ), the excess is identifiable in this instance. Hence the Ω ( T / n ) \Omega(\sqrt{T/n}) Ω ( T / n ) rate is not an artifact of estimation: it concerns the estimation component only and says nothing about the approximation term.
Full Experiments
In this section, we provide the extended experimental details and additional results that complement the main text.
Atom-Task Experiments
Experimental Setup
Atom-Task Benchmark. To validate compositional reasoning capability, we introduce Atom-Task. This task requires the model to sequentially execute a series of atomic operations on a symbolic sequence multiple times, necessitating multi-step reasoning capabilities.
Symbol System and Atomic Operations. The input consists of sequences formed by 6 Greek letters { α , β , γ , δ , ε , ω } \{\alpha,\beta,\gamma,\delta,\varepsilon,\omega\} { α , β , γ , δ , ε , ω } . We define five basic operations (mapped to IDs t1–t5):
Reverse (t1): Reverses the order of the sequence.
Substitute (t2): Swaps symbols in pairs (α ↔ β \alpha\leftrightarrow\beta α ↔ β , γ ↔ δ \gamma\leftrightarrow\delta γ ↔ δ , ϵ ↔ ω \epsilon\leftrightarrow\omega ϵ ↔ ω ).
Duplicate (t3): Duplicates each symbol consecutively.
Deduplicate (t4): Removes consecutive duplicates.
Rotate (t5): Moves the first element to the end.
Dataset Design and Distribution. A core challenge in compositional generalization is the distribution shift between training and testing. We design specific training datasets to investigate these effects.
Design Principles. Our training sets adhere to two core principles:
Dominance of atomic primitives: In Mixed 1-, 3-, and 5-Step, single-step samples constitute 80% of the training trajectories, supporting the acquisition of basic operations.
Controlled exposure to composition: Three- and five-step training chains provide structural patterns for compositional decomposition; in Mixed 3+5, the five-step chains use ≤ 2 \le2 ≤ 2 distinct operations, as specified in § 5 .
Training Datasets. To evaluate OOD generalization, we design four training datasets:
Single-Step: 5k uniformly distributed one-step samples.
Three-Step: 1.66k three-step samples.
Mixed 3+5: 1,333 samples (833 three-step and 500 five-step; the five-step chains use at most two distinct operations, bridging length and combinatorial generalization).
Mixed 1-, 3-, and 5-Step: For each operation o p op o p , a dedicated 5k-sample dataset excludes o p op o p from all multi-step chains but keeps it in single-step data. Specifically, it contains 4,000 one-step, 600 three-step, and 400 five-step samples (5,000 training trajectories, or 7,800 atomic transitions in total; see Table 5 ).
Table 5. Sample distribution in Ablation Datasets. Each dataset excludes a specific operation from multi-step chains. The 5,000 trajectories comprise 7,800 atomic transitions.
Balanced Supervision: While the sample sizes vary across settings, the number of atomic transitions is held roughly constant: the single-step, three-step and mixed 3+5 datasets each contain about 5,000 transitions (5,000, 1,666 × \times × 3, and 833 × \times × 3 + 500 × \times × 5), while the operation-exclusion dataset contains 7,800 and is compared across excluded operations under that same budget, which controls for confounding variables.
Test Sets. We evaluate on four test sets with increasing chain lengths: 3-step, 5-step, 7-step, and 9-step. Each set contains 500 unseen samples, requiring the model to perform compositional reasoning not explicitly memorized from training.
Implementation Details
For the Atom-Task, we use Qwen3-4B as the base model. Fine-tuning is performed using low-rank adaptation (LoRA; rank 16, alpha 32) for 3 epochs with a learning rate of 5 × 10 − 5 5 \times10^{-5} 5 × 1 0 − 5 . The maximum generation length (max_new_tokens) is set to 2048 to accommodate longer reasoning chains. All experiments are conducted on a single NVIDIA RTX 4090 GPU.
Parameter Efficiency: We employ LoRA with the following configuration:
We employ a Chain-of-Thought training format, where the model is trained to explicitly predict the intermediate output after each atomic operation. For the “No-CoT” baseline, the model is trained to predict only the final output without intermediate states.
Reproducibility: For the main results (Table 1 ), both CoT and No-CoT entries are means across 3 random seeds (42, 2026, 12345), and the same 3 seeds are used for the operation-exclusion study, the format ablation, the noise tests, and the scaling points. For the format ablation (Table 3 ), the ablated CoT entries are means over 3 seeds and the original entries average the three-seed means of Table 2 . Standard deviations are reported as subscripts and the seed setting is stated in each caption; differences of a few points between entries sharing a seed set should be read as indicative rather than as significance statements.
Details on Scaling Laws
To complement Figure 3 , we provide the detailed accuracy numbers for training-sample scaling and inference-example scaling in Table 6 and Table 7 , respectively. All scaling experiments are conducted using the “Three-Step” training dataset and evaluated on held-out test sets, each reported point being a mean over 3 seeds (42, 2026, 12345).
Table 6. Accuracy (%) for Sample Size Scaling (n n n ). Each entry is a mean over 3 seeds (42, 2026, 12345).
Table 7. Accuracy (%) versus Number of Inference-Time Examples. Each entry is a mean over 3 seeds (42, 2026, 12345).
Extended Results and Analysis
Robustness to Noise in Reasoning Steps. To evaluate the robustness of CoT training to data quality, we conduct a noise interference experiment on the Qwen3-4B model. We test: Multi-step (Pure 3-step), Multi-step (Mixed 3+5), and the w/o Substitute ablation setting. (Note: These earlier noise robustness experiments used max_new_tokens=1024, but the conclusions remain consistent).
Noise Injection Strategy. We define the basic unit of noise injection as a single inference step. We select a proportion p ∈ { 0.05 , 0.1 , 0.2 } p \in\{0.05, 0.1, 0.2\} p ∈ { 0.05 , 0.1 , 0.2 } of the total reasoning steps in the training set for interference. A standard reasoning step contains four discrete elements: the operation, the input state, the output state, and the remaining tasks. For each selected step, we randomly choose two of these four elements and perform either Tampering (replacing content with random symbols) or Deletion (emptying the content).
Table 8 presents accuracy for 3-step / 5-step / 7-step test sets respectively. The results indicate strong robustness to noise in reasoning steps. Across all training configurations, increasing the noise ratio does not lead to significant performance degradation; accuracy remains largely consistent with the clean baselines reported in previous tables. In some cases, minor variations are observed but without a clear negative trend, suggesting that the learned compositional reasoning patterns are resilient to localized inconsistencies in the training data.
Table 8. Each entry is a mean over 3 seeds (42, 2026, 12345). Robustness to training noise (Qwen3-4B). Accuracy (%) under varying noise ratios. Each cell shows the result for the 3-step / 5-step / 7-step test sets.
GSM8K Experiments
To validate our findings on real-world, complex reasoning scenarios, we conduct experiments on the GSM8K benchmark using Llama2-7B and Qwen2.5-3B fine-tuned on MetaMathQA, a math instruction-tuning dataset (395K samples in total). This protocol evaluates a controlled within-family distribution shift from MetaMathQA to GSM8K rather than source-disjoint transfer. Due to computational constraints, we use 30,000 training samples for each experiment. For standard experiments (baseline and noise), we randomly sample these 30,000 instances from the full dataset; for distribution shift experiments, we select 30,000 samples according to specific shift criteria.
Experimental Setup
Models and Training. We employ Llama2-7B and Qwen2.5-3B as base models. Models are fine-tuned using LoRA (rank=16, alpha=16) for 1 epoch with a learning rate of 2 × 10 − 5 2 \times10^{-5} 2 × 1 0 − 5 and a maximum sequence length of 512. Training data is drawn from the MetaMathQA dataset. For baseline and noise experiments, we randomly sample 30,000 instances; for distribution shift experiments, we construct 30,000-sample subsets by filtering according to three shift indicators (Topic, Complexity, Answer Scale). All experiments are conducted on a single NVIDIA RTX 4090 GPU, and each experiment is run with three random seeds (42, 2026, 12345); the training data is identical across seeds, so reported standard deviations reflect model-side randomness.
Evaluation. All models are evaluated on the standard GSM8K test set. We report accuracy as the primary metric.
CoT vs. No-CoT & OOD Generalization
Baseline Comparison. As shown in Table 9 , CoT training significantly boosts accuracy over untrained baselines, while No-CoT training yields only marginal improvements or even degradation.
Table 9. GSM8K baseline and comparative results. Each entry is a mean over 3 seeds (42, 2026, 12345).
Distribution Shift Experiments. In contrast to the random sampling used for baseline and noise studies, here we deliberately create distribution gaps by filtering 30,000 samples from MetaMathQA based on the following criteria:
Topic Shift (ood_domain): shift t o p i c = ∣ K s a m p l e ∖ K G S M 8 K ∣ ∣ K s a m p l e ∪ K G S M 8 K ∣ \operatorname{shift}_{\mathrm{topic}} = \frac{\lvert K_{\mathrm{sample}} \setminus K_{\mathrm{GSM8K}} \rvert}{\lvert K_{\mathrm{sample}} \cup K_{\mathrm{GSM8K}} \rvert} shift topic = ∣ K sample ∪ K GSM8K ∣ ∣ K sample ∖ K GSM8K ∣ , where K s a m p l e K_{\mathrm{sample}} K sample is the keyword set of the sample and K G S M 8 K K_{\mathrm{GSM8K}} K GSM8K the top-20 keyword set of GSM8K; this asymmetric keyword-novelty score measures the fraction of sample keywords absent from GSM8K’s set, normalized by the union size.
The results in Table 10 show that performance remains robust across all shifts, with only mild fluctuations. This stability suggests that the compositional patterns learned via CoT can generalize to practical domains like mathematical reasoning.
Table 10. GSM8K accuracy under distribution shifts. Each entry is a mean over 3 seeds (42, 2026, 12345).
Robustness to Reasoning Noise. We further test resilience to imperfect supervision by training on 30,000 randomly sampled CoT instances from MetaMathQA, injected with noise via a controlled strategy: (1) Sample-level probability : Each sample has a probability p p p of being selected; (2) Single-step injection : For selected samples, noise is injected into a single randomly chosen reasoning step; (3) Noise type : ‘delete’ (removing the step content) or “wrong_number” (modifying the numerical result), applied with equal probability (50%). This assesses the model’s ability to handle corrupted intermediate reasoning.
Both models exhibit strong resistance to noise (Table 11 ). Even with up to 50% of samples corrupted, accuracy fluctuates within a narrow band and never collapses. This suggests that the model is relatively insensitive to localized noise in intermediate steps and can still absorb the correct logical patterns.
Table 11. Each entry is a mean over 3 seeds (42, 2026, 12345). GSM8K accuracy under training with different proportions (p p p ) of reasoning noise. All models trained on 30,000 samples.
Summary of Findings
The GSM8K experiments reveal three main patterns: (1) CoT training substantially improves accuracy over untrained and No-CoT baselines, highlighting the benefit of intermediate step supervision; (2) models are robust to significant reasoning noise, maintaining stable performance even when training data contains deleted or incorrect steps, indicating that supervision remains effective even when individual steps are corrupted; (3) models generalize effectively across distribution shifts in topic, complexity, and answer scale, with only mild accuracy fluctuations, indicating that the reasoning patterns acquired via CoT transfer robustly to real-world mathematical domains.