Tight Sample Complexity of Transformers

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Tight Sample Complexity of Transformers

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Proceedings of Machine Learning Research vol :1–36, 2026

39th Annual Conference on Learning Theory

Tight Sample Complexity of Transformers Chenxiao Yang Nathan Srebro Zhiyuan Li

CHENXIAO @ TTIC . EDU NATI @ TTIC . EDU ZHIYUANLI @ TTIC . EDU

arXiv:2606.09731v1 [cs.LG] 8 Jun 2026

Toyota Technological Institute at Chicago (TTIC)

Abstract We tightly characterize the VC dimension of depth-L Transformers with a total of W parameters, mapping an input sequence of length T to a single output, establishing an upper bound of O(LW log(T W )) and a nearly matching lower bound of Ω(LW log(T W/L)). We further tightly characterize the sample complexity of chain-of-thought learning using such a Transformer, showing teacher forcing (i.e. selecting a predictor consistent with the entire chain-of-thought on training data) learns with sample complexity O (LW log ((T + T ′ ) W )) and that any learning rule that uses chain-of-thought data requires at least Ω (LW log ((T + T ′ ) W/L)) examples, where T is the input length and T ′ is the number of autoregressive steps. Keywords: Transformers, VC-dimension, Learning Theory

1. Introduction Transformers (Vaswani et al., 2017) are a class of models that operate on sequences of arbitrary length, where the architecture and the number of parameters are independent of the input sequence length T . A significant advantage one might then expect is that the sample complexity of learning is independent of the sequence length. However, we do not yet have a rigorous and precise understanding of this sample complexity, and its dependence on the input sequence length and other aspects of the architecture. Tightly characterizing the sample complexity is important both for understanding the length dependence (or lack thereof), as well as for translating results on the representational power of Transformers and their required size (e.g. Yun et al., 2019; Bhattamishra et al., 2020; Hahn, 2020; Pérez et al., 2021; Wei et al., 2021; Liu et al., 2023; Feng et al., 2023; Li et al., 2024; Merrill and Sabharwal, 2023) to actual learning guarantees and understanding the inductive bias of Transformers. We emphasize that in ‘learning’ here, we are referring to statistical learning by, e.g. empirical risk minimization, and are ignoring the important computational issue of finding such a risk minimizer. Prior work analyzed the scale-sensitive sample complexity of Transformers, i.e. in terms of norm restrictions on the weights (and under margin assumptions or for scale sensitive loss). In particular, Trauger and Tewari (2023) obtained sample complexity that depends polynomially on the norms of weight matrices (and thus polynomially on the number of parameters under standard scaling), and exponentially on the depth, but as desired is independent of input sequence length1 . Similarly, Zhang et al. (2022) also established sequence-length independent sample complexity, again by relying on norm bounds, but with only a logarithmic norm dependence, and a suboptimal quadratic dependence on the number of parameters (times a linear dependence on depth). 1. In this regard, these improve over a previous bound (Edelman et al., 2022), that has better polynomial dependency on the norms, but does depend logarithmically on sequence length

YANG S REBRO L I

In this paper, instead of relying on the magnitudes of the weights and the scale of the outputs, we investigate the parametric capacity of Transformers, i.e. in terms of the number of weights, allowing the weights to be arbitrary real numbers. As the VC dimension tightly captures the sample complexity of PAC-learning Vapnik and Chervonenkis (1971); Blumer et al. (1989), this corresponds to characterizing the VC dimension (or its multiclass generalization) of the class of functions implementable by Transformers, with any real valued weights. This is a basic question about parametric classes and is fundamental in learning theory, with well-understood answers for many classical classes (e.g., linear predictors, polynomials). Even for understanding scale-sensitive or regularization-driven generalization, this serves as an important baseline. The VC dimension of feed-forward networks has been extensively studied over a span of fifty years (e.g. Cover, 1965; Baum and Haussler, 1989; Maass, 1994; Koiran and Sontag, 1994; Karpinski and Macintyre, 1997; Bartlett et al., 2019), and is now well understood. In particular, we understand that for deep feed-forward networks, the VC dimension can be much larger than the number of parameters and that this greatly depends on the activation function: with hard-threshold activations there is no depth dependence, and the VC dimension is Θ(W log W ), where W is the total number of weights. With ReLU (or other piecewise linear) activations, the depth comes in linearly and the VC dimension is Ω(W L log(W/L)) ≤ VCdim ≤ O(W L log W ). But with sigmoidal activations it significantly worsens (Koiran and Sontag, 1994; Karpinski and Macintyre, 1997). How about the VC dimension of Transformers? How does it depend on the total number of parameters W , the depth L, the input sequence length T , and perhaps other parameters such as the number of attention heads per layer. Based on our experience with feed-forward networks, we would expect Transformer’s VC dimension to also depend on the activation functions used. ReLU activations are common for feedforward layers in practice, and we consider such units here. Attention layer is usually based on a softmax operation. But, a softmax operation hides a logistic activation and can be easily used to simulate it, and so if we allow softmax operations, we encounter the same difficulties and bad scaling as for sigmoidal feed-forward networks discussed above. Instead, we consider hard-attention, which is commonly studied in the theoretical literature on Transformers (e.g. Hahn, 2020; Merrill et al., 2022; Merrill and Sabharwal, 2023; Yang et al., 2025), and avoids sigmoidal, exponential and logarithmic functions. Transformer VC-Dimension. Accordingly, what we study are Transformers that map T input tokens from some finite-size alphabet Σ to a single output token in Σ (or an embedding sequence to {0, 1} as classifiers), and consist of token embedding layer, ReLU feed-forward layers, hardattention layers (average, leftmost or rightmost hard attention, and any number of attention heads), and greedy decoding. We allow arbitrary, but fixed (i.e. not learned) additive positional encoding, including no positional encoding (NOPE, Kazemnejad et al. (2023)). We allow skip connections, but no layerwise-normalization. See precise description in Section 2. We show (in Section 3) that for any such Transformers as classifiers, the VC dimension and thus the sample complexity of learning, is O(LW log(W T )), where W is the total number of weights, and L is the depth (number of feed-forward and attention layers). The dependence on O(LW log W ) is tight, even just due to the feed-forward sublayers. We further show that the multiplicative dependence on log T is also tight by providing a nearly matching lower bound of Ω(LW log(W T /L)). Edelman et al. (2022) previously establishes a lower bound of Ω(log T ) even when the number of parameters is fixed, but 2

this left open the possibility of an additive log T term—we improve this to show the necessity of the interaction. Autoregressive CoT with Transformers. In Section 4, we turn to using a Transformer autoregressively to generate a final answer after a chain-of-thought of length T ′ . Following Joshi et al. (2025), we study the sample complexity of learning to map the input of length T to a single-token output obtained after T ′ steps, given training data consisting of m i.i.d. inputs and their entire T ′ -step chain-of-thought. Unlike standard supervised learning where a single measure of VC-dimension governs learnability, we show that two complexity measures govern sample complexity in CoT learning: TSdim (trace shattering dimension), measuring the capacity to shatter entire reasoning traces, governs the upper bound; ASdim (answer shattering dimension), measuring the capacity to shatter only the final answer, governs the CoT lower bound. While combining our single-step VC bound above with the generic result of Joshi et al. (2025) yields a sample complexity upper bound of O(W L log(W (T + T ′ )) log T ′ /ϵ), directly bounding TSdim improves it to O(W L log(W (T + T ′ ))/ϵ), avoiding the extra log T ′ factor. For lower bounds, answer shattering gives the CoT term Ω(W L log(T + T ′ )/ϵ); combined with the ordinary supervised ReLU-network lower bound, this implies the worst-case lower bound Ω(W L log((T + T ′ )W/L)/ϵ). Importantly, the upper bound is obtained by the obvious “teacher forcing” Williams and Zipser (1989) learning rule, i.e. selecting any Transformer in the class that is consistent with all the steps in CoT (as in also Joshi et al., 2025), and the lower bound holds for any learning rule, thus establishing the optimality of teacher forcing for training Transformers with CoT supervision. Our upper bounds are based on combining proofs about general computation circuits (Bartlett et al., 1998), with more recent refinements for piecewise linear neural nets (Bartlett et al., 2019), and then carefully expressing the attention operation using a poly-sized constant-depth computation. The lower bounds use novel explicit constructions.

2. Preliminaries: Transformers and Autoregressive CoT Throughout this paper, let Σ denote a vocabulary with |Σ| = K. We write token sequences as X = (x0 , . . . , xT −1 ) ∈ ΣT and embedding sequences as H ∈ RT ×d , where T is the sequence length and d is the embedding dimension. We adopt Python-style indexing: X[:t] denotes the first t elements, and X[−t:] the last t elements; X ∥ Z denotes sequence concatenation. We use Transformers in two roles. The fixed-length VC-dimension results use binary classifiers f 01 : RT ×d → {0, 1}. The autoregressive CoT results use next-token generators with input length T , generation length T ′ , and maximum context length Tctx = T + T ′ . 2.1. Transformers We first define the Transformer architecture. Our formulation follows the standard decoder-only Transformer (Vaswani et al., 2017), but replaces softmax attention with hard attention, a discrete variant that has been central to recent theoretical studies of Transformers (Hahn, 2020; Merrill et al., 2022). As is standard in VC-dimension analysis, we assume exact arithmetic over the reals. Transformer Layers. A Transformer of depth L has L Transformer blocks. It transforms an input embedding sequence H (0) = H ∈ RT ×d through these blocks. We allow layer-dependent hidden (ℓ) (ℓ) (ℓ) dimensions d(0) , d(1) , . . . , d(L) with d(0) = d, so H (ℓ) ∈ RT ×d . Each row Hi ∈ Rd represents the embedding of position i. Each block applies two sublayers: an attention mechanism followed 3

YANG S REBRO L I

by a feed-forward network. H̃ (ℓ) = Attn(ℓ) (H (ℓ−1) ),

H (ℓ) = FFN(ℓ) (H̃ (ℓ) ).

(1)

We state attention-before-FFN blocks; residuals and other fixed orderings only change depth by constants. Hard Attention. The key component distinguishing Transformers from feed-forward networks is the attention mechanism, which enables data-dependent routing of information across positions. For each attention head, queries, keys, and values are computed via affine transformations: Qi = WQ Hi + bQ ,

Ki = WK Hi + bK ,

Vi = WV Hi + bV ,

(2)

where WQ , WK , WV are projection matrices and bQ , bK , bV are bias vectors (suppressing the layer index ℓ). We use causal masking: position i can only attend to positions j ≤ i. We analyze Hard Attention (Hahn, 2020; Merrill et al., 2022; Merrill and Sabharwal, 2023), the low-temperature limit of softmax attention where weights concentrate on score-maximizing positions. Let Mi = {j ≤ i : ⟨Qi , Kj ⟩ = maxk≤i ⟨Qi , Kk ⟩} denote the set of causally-visible positions achieving the maximum score, P and define attention weights αi,j = 1[j ∈ Mi ]/|Mi |. The attention output is Attn(H)i = j αi,j Vj . Our analysis does not rely on the specific tie-breaking rule and generalizes to variants such as leftmost-hard or rightmost-hard attention (Hahn, 2020). Multi-Head Attention. A multi-head attention layer at layer ℓ with h(ℓ) heads computes h(ℓ) attention outputs in parallel. Each head i ∈ {1, . . . , h(ℓ) } computes queries, keys, and values via (ℓ,i) (ℓ,i) (ℓ,i) its own projection matrices WQ , WK , WV , then applies hard attention as defined above to produce Attn(ℓ,i) (H), with value/output dimension matching the FFN input dimension. The outputs Ph(ℓ) (ℓ,i) (H). For simplicity we sum head outputs; the usual are summed: Attn(ℓ) (H) = i=1 Attn concatenate-and-project formulation is covered by allowing head-specific output dimensions and projections. Feed-Forward Network. The FFN sublayer at layer ℓ is a position-wise MLP with ReLU acti(ℓ−1) (ℓ) vations, mapping Rd → Rd . It has at most D0 internal affine/ReLU layers, for an absolute constant D0 , with arbitrary hidden widths collected in d¯(ℓ) . Our results can be extended to any piecewise-linear activation, following Bartlett et al. (1998). Input Layer. For next-token generators operating on token sequences, we first embed tokens into vectors. The token embedding TE : Σ → Rd , parametrized by WTE ∈ Rd×K , maps each token to a d-dimensional vector. For a context-length-T architecture, we use a fixed, non-learned positional embedding PE : {0, . . . , T −1} → Rd . In autoregressive results, T = Tctx , and the same parameters are run on each prefix using the corresponding initial segment of PE. The input embedding sequence is: H = TE(x0 ) + PE(0), . . . , TE(xT −1 ) + PE(T − 1) ∈ RT ×d . (3) The positional embedding may be arbitrary, but it is fixed and not counted as a trainable parameter. (L)

(L)

Output Layer. For a length-T input, the output is extracted from the final position HT −1 ∈ Rd of the last layer. For an autoregressive prefix of length s, the same rule reads position s − 1. For (L) binary classifiers, a linear projection wout ∈ Rd followed by a threshold yields the binary label. 4

(L)

For next-token generators, a decoding matrix WDE ∈ RK×d maps the final representation to logits over the vocabulary. For a fixed architecture A and trainable parameter vector θ, ⊤ (L) (L) 01 fA,θ (H) = 1 wout HT −1 > 0 ∈ {0, 1}, fA,θ (X) = arg max WDE HT −1 x ∈ Σ. (4) x∈Σ

The argmax uses a fixed deterministic tie-breaking rule. In practice, WDE often shares weights with the token embedding WTE (weight tying); our analysis permits both tied and untied configurations. Hypothesis Classes. We distinguish a fixed architecture from a family of possible architectures. A generic Transformer architecture A is specified by the choices introduced above: (ℓ) L ¯(ℓ) L A = K, L, {d(i) }L (5) i=0 , {h }ℓ=1 , {d }ℓ=1 , PE, Res , where these entries record the architectural choices above. Here Res records a residual/no-residual flag for each attention and FFN sublayer. A residual adds the sublayer input to its output; if dimensions differ, the residual path may use an affine projection, counted in W (A). Let W (A) and L(A) denote the total parameter count and depth. Varying the trainable parameters gives fixed-architecture hypothesis classes; collecting these over all architectures within a budget gives architecture families: 01 01 FA := {fA,θ : θ ∈ RW (A) }, FA := {fA,θ : θ ∈ RW (A) }, 01 FL,W := {FA : L(A) ≤ L, W (A) ≤ W }, F01 L,W := {FA : L(A) ≤ L, W (A) ≤ W }.

(6)

When A is fixed, we often suppress it and write fθ or fθ01 . Thus FL,W and F01 L,W are families of fixed-architecture hypothesis classes, not single hypothesis classes. 2.2. Autoregressive Next-Token Generation Next-Token Generator. A next-token generator maps a token context to the next token. We write f : Σ∗ → Σ for convenience, but in our results f is only evaluated on contexts of length at most Tctx . At each step, the model uses the same f to predict a new token and appends it to the current sequence; we denote this apply-and-append operation by f¯ : Σ∗ → Σ∗ , where f¯(X) := X ∥ f (X). Starting from an initial prompt X ∈ ΣT of input length T , the model iteratively applies f¯ to generate T ′ new tokens (the generation length): ′ ′ f (T ) (X) := f¯ ◦ f¯ ◦ · · · ◦ f¯(X) ∈ ΣT +T . | {z }

(7)

T ′ times

′

The generated suffix f (T ) (X)[−T ′ :] is the CoT trace, and its last token is the final answer. Teacher Forced Training. In practice, autoregressive models are trained using teacher forcing (Williams and Zipser, 1989): at each step, the model predicts the next token conditioned on the ground-truth prefix rather than its own previous predictions. Concretely, consider a distribution D ′ over input-output pairs (X, Z), where X ∈ ΣT is an input prompt and Z = (z0 , . . . , zT ′ −1 ) ∈ ΣT is the target sequence. Given m i.i.d. samples S = {(Xi , Zi )}m i=1 from D and a hypothesis class F of next-token generators, the learning objective is to find f ∈ F minimizing the empirical nexttoken prediction loss: ′

b ; S) = 1 L(f m

m T −1 X 1 X 1 f (Xi ∥ Zi [:t]) ̸= Zi [t] . ′ T i=1

t=0

(8)

YANG S REBRO L I

End-to-End Evaluation. At test time, however, we ultimately care only about the correctness of the final token Z[−1], treating the intermediate tokens Z[:−1] as auxiliary computation. This is captured by the population end-to-end loss: h ′ i Le2e (f ) = E(X,Z)∼D 1 f (T ) (X)[−1] ̸= Z[−1] , (9) ′

where f (T ) (X)[−1] denotes the final token after T ′ steps of autoregressive generation. Thus training checks predictions on ground-truth prefixes, while end-to-end evaluation rolls out the model on its own prefixes and keeps only the final token.

3. VC-Dimension of Transformers For VC-dimension analysis, we focus on the binary classifier family F01 L,W with context length T , depth L, and W parameters. The upper bound is uniform over every fixed class in this family, while the lower bound is witnessed by one fixed class. The extension to multi-class settings is standard. 3.1. Upper Bound We first establish an upper bound. The main idea is that hard attention acts as a discrete switch: once the attention rankings and ReLU activation patterns are fixed, the network output is polynomial in the parameters. We can then extend the piecewise-polynomial framework for ReLU networks (Bartlett et al., 1998) to account for these additional switches. Theorem 1 (VC Dimension Upper Bound) For any depth L ≥ 1, parameter budget W ≥ L, and context length T ≥ 1, let F01 L,W be the binary Transformer family defined in Section 2.1. Then, for , every F 01 ∈ F01 L,W VCdim(F 01 ) = O(W L log(T W )). (10) Proof Sketch. We proceed in two steps: first partition the parameter space by discrete branching patterns, then bound the number of output sign patterns inside each region. Step 1: Piecewise-Polynomial Framework. We bound the growth function ΠF 01 (H1:N ), which counts the number of distinct output patterns achievable over N embedding sequences; if these N sequences are shattered, this number is 2N . We partition the parameter space RW into regions where all discrete branching decisions are fixed. Within each region, the network output is polynomial in θ, so ΠF 01 (H1:N ) ≤ |P| · maxC ΠC , where |P| is the number of regions and ΠC is the number of output patterns within region C. Warren’s theorem bounds ΠC : for m polynomials of degree D in W variables, the number of distinct sign vectors is at most (O(mD/W ))W . Step 2: Counting Branching Polynomials. At each layer, we identify the branching polynomials whose signs determine all discrete choices. For the FFN, these are all internal ReLU pre-activations (ℓ) (O(N T W ) polynomials). For attention, these are the pairwise score differences gn,i,p,q (θ) := ⟨qn,i (θ), kn,p (θ) − kn,q (θ)⟩, whose signs determine the relative ranking of positions p and q. A W parameter architecture has at most O(W ) nontrivial heads; with T positions, each head and each query requires T2 = O(T 2 ) comparisons, yielding O(N W T 3 ) additional branching polynomials per layer. Applying Warren’s bound and taking logarithms, the T 3 term contributes W L log T to the exponent, yielding the stated bound. The complete derivation appears in Appendix B. 6

t=0 FFN(0) :

t=1

···

t = t∗1

···

H (0)

Context · · · t = t∗L · · · t = T −2 Match: t∗1 = arg mint (t − r0 )2 ··· ···

Attn(1) :

H̃ (1)

···

FFN(1) :

H (1)

···

.. .

FFN(L−1) : H (L−1)

···

Attn(L) :

H̃ (L)

···

FFN(L) :

H (L)

···

Query t = T −1

Read: b

1 = bit · · · i (t1∗)

···

.. .. .. . . . ∗ Match: tL = arg mint (t − rL−1 )2 ··· ··· Read : bL ··· · · · = biti (t ∗ ) L ···

···

Embed: r0 ← wj Retrieval Shift: r1 =2T (r0 −t∗1 )

Shift: rL−1 =2T (rL−2 −t∗L−1 )

Retrieval Output: ŷ = bℓ

Figure 1: Recursive retrieval gadget for sample (j, ℓ, i). The context positions enumerate all B-bit label configurations, while the query register r0 stores an encoded list of target addresses (sj,1 , . . . , sj,L ). At layer k, hard attention selects the context position t∗k nearest to the current register, the value head reads its i-th bit, and the FFN shifts the register to expose the next address. A gate outputs the bit read at the target layer ℓ. The appendix proves a slightly sharper fixed-architecture statement with logarithmic factor log(T W (A)L(A)); using L(A) ≤ L ≤ W and W (A) ≤ W gives the displayed form. ■ 3.2. Lower Bound We now construct a Transformer that simulates a Recursive Retrieval Machine (Figure 1). The context stores all 2B possible B-bit label configurations, where B = ⌊log2 (T − 1)⌋. For each group-layer pair, the parameters specify which configuration to retrieve. One attention lookup then selects one of T positions, realizing B = Θ(log T ) labels across the corresponding bit-indexed samples. Chaining this lookup across L layers and n = Θ(W ) groups gives the Ω(W L log T ) term. Our bound improves the Ω(log T ) bound from Edelman et al. (2022). Theorem 2 (VC Dimension Lower Bound) There exists an absolute constant C0 > 0 such that for any depth L ≥ 1, context length T ≥ 3, and parameter budget W ≥ C0 L, let F01 L,W be the 01 01 binary Transformer family defined in Section 2.1. Then there exists F ∈ FL,W such that VCdim(F 01 ) ≥ c · W L (log T + log(W/L)) ,

(11)

where c > 0 is an absolute constant. Proof Sketch. We construct a set of N = nLB samples that can be shattered, where n = Θ(W ) is the number of sample groups, L is the depth, and B = ⌊log2 (T − 1)⌋. Each sample is indexed by a triple (j, ℓ, i) with j ∈ [n], ℓ ∈ [L], i ∈ [B]. The construction below gives the W L log T term; the W L log(W/L) term comes from the standard ReLU-network lower bound, since Transformers contain ordinary position-wise ReLU networks as a subclass. We describe the retrieval construction in three steps: (1) how the context encodes labels, (2) how parameters specify retrieval targets, and (3) how attention and FFN perform recursive retrieval. Step 1: Context as Label Repository. For each fixed pair (j, ℓ), the B = ⌊log2 (T − 1)⌋ labels indexed by i ∈ [B] are encoded by one retrieved context position. Position t ∈ {0, . . . , T −2} stores B the t-th labeling by encoding biti (t), so the context enumerates all − 1 label configurations. P2 ≤ T i−1 ∗ For target labels Yj,ℓ,1 , . . . , Yj,ℓ,B , the matching position is t = i Yj,ℓ,i 2 . 7

YANG S REBRO L I

Step 2: Parameters as Target Addresses. For each group-layer pair, store the P the parameters k−1 . A trainable lookup position. The labels {Yj,ℓ,i }B are aggregated into s = Y 2 j,ℓ i=1 k j,ℓ,k affine compression maps each group identifier j to an encoded pointer containing all L addresses (sj,1 , . . . , sj,L ). Step 3: Recursive Retrieval via Attention + FFN. Given a register r encoding target address s, attention selects the context position t∗ = s: keys extract (2t, −t2 ), the query extracts (r, 1), and the score 2rt − t2 is maximized at the integer nearest to r. The value projection reads biti (t∗ ). The base-2T encoding keeps |r − s| < 1/2, nearest integer. P so s is the unique m−1 . After retrieval step k, the FFN performs To chain L retrievals, set r0 := L s /(2T ) m m=1 the left-shift rk = 2T (rk−1 − t∗ ), exposing the next address. A gate records the retrieved bit only when k = ℓ. Putting It Together. This affine compression uses Θ(n) parameters to store n address sequences; the backbone requires only O(L) parameters. For a sufficiently large absolute constant C0 , the regime W ≥ C0 L lets us choose n = Θ(W ). We therefore shatter nLB samples, yielding Ω(W L log T ). Together with the ReLU-subclass lower bound Ω(W L log(W/L)), this proves Theorem 2. The complete construction appears in Appendix C. ■

4. Auto-Regressive CoT with Transformers We now turn to the autoregressive setting, where next-token generators f : Σ∗ → Σ iteratively produce variable-length token sequences. This raises a natural question: how does the availability of full CoT traces during training affect learnability? We first formalize CoT learnability, then introduce the two dimensions governing the generic upper and lower bounds, and finally instantiate both for Transformers. 4.1. Chain-of-Thought Learnability We begin by formalizing the CoT learning problem. Fix an input domain X ⊆ ΣT . The base class F of next-token generators induces the trace and end-to-end hypothesis classes: n o n o ′ ′ ′ (T ′ ) F (T ) = X 7→ f (T ) (X)[−T ′ :] : f ∈ F , Fe2e = X 7→ f (T ) (X)[−1] : f ∈ F . (12) (T ′ )

Our goal is to learn the end-to-end class Fe2e . We consider the realizable setting: there exists a ground-truth generator f∗ ∈ F. Given an input distribution D over X , we label each input ′ X ∼ D with the full CoT trace Z = f∗ (T ) (X)[−T ′ :], and seek to output a final-token predictor with small end-to-end error. Realizability means f∗ predicts every token in the trace correctly: f∗ (X ∥ Z[:t]) = Z[t] for all t ∈ {0, . . . , T ′ − 1}. Formally, adopting the definition from Joshi et al. (2025): (T ′ )

Definition 3 (Realizable Chain-of-Thought Learnability) We say Fe2e is CoT-learnable with ′ sample complexity m(ε, δ) if there exists a learning rule A : (X × ΣT )∗ → ΣX such that for every distribution D over X and f∗ ∈ F, given m ≥ m(ε, δ) samples S = {(Xi , Zi )}m i=1 with Xi ∼ D (T ′ ) ′ and Zi = f∗ (Xi )[−T :], with probability at least 1 − δ, h i ′ Pr A(S)(X) ̸= f∗ (T ) (X)[−1] ≤ ε. (13) X∼D

Learning Algorithm. When full CoT traces are available, a natural approach is to train the model to match them step by step. This leads to teacher forced training (Section 2.2) as introduced in Section 2. In the realizable setting, it reduces to finding any generator consistent with all observed CoT traces. Formally, we define the learner as ConsCoT (S) :

Return fˆ ∈ F such that fˆ(Xi ∥ Zi [:t]) = Zi [t] for all (Xi , Zi ) ∈ S, t ∈ {0, . . . , T ′ − 1}.

(14)

This is a proper learner: it returns a generator fˆ ∈ F, whose induced final-token predictor is ′ X 7→ fˆ(T ) (X)[−1]. In standard PAC learning, training and test objectives coincide, so ERM is universal, achieving optimal distribution-free sample complexity. For CoT learning, however, there is a fundamental asymmetry: the learner is trained on full traces but evaluated only on the final token. The intermediate tokens carry information that could guide learning, but a learning algorithm might exploit them without matching every step, and at test time, a different reasoning path could still lead to the correct final answer. This raises a natural question: is teacher forcing the universal approach for CoT learning? A direct generic bound would lose an extra logarithmic factor in T ′ . The next two subsections remove this loss for Transformers and show that the resulting rate is optimal. 4.2. Dual Complexity Measures To characterize CoT sample complexity, we introduce two measures that capture the two sides of the train-test asymmetry: the trace shattering dimension TSdim for the upper bound, and the answer shattering dimension ASdim for the CoT lower bound. The first measure captures the complexity of predicting the entire trace correctly, which requires that every token along the reasoning path match the target. Equivalently, it is the VC dimension of the binary loss class that asks whether a generated trace matches a reference trace. Definition 4 (Trace Shattering Dimension) A set S = {X1 , . . . , Xn } ⊆ X is trace shattered by ′ F if there exists a trace assignment RS : S → ΣT such that for every b ∈ {0, 1}n , some fb ∈ F satisfies for all i ∈ [n]: (T ′ )

bi = 1 =⇒ fb

(T ′ )

(Xi )[−T ′ :] = RS (Xi ),

bi = 0 =⇒ fb

(Xi )[−T ′ :] ̸= RS (Xi ).

(15)

The trace shattering dimension TSdim(F; X , T ′ ) is the size of the largest such set. The second measure captures the complexity of predicting only the final answer, namely the last token of the trace. The key constraint is that all generators share the same trace prefix, so the intermediate tokens provide no information about the final answer. Definition 5 (Answer Shattering Dimension) Assume 0, 1 ∈ Σ. A set S = {X1 , . . . , Xn } ⊆ X is ′ answer shattered if there exists a prefix assignment RS : S → ΣT −1 such that for every b ∈ {0, 1}n , some fb ∈ F makes the first T ′ − 1 generated tokens equal to this prefix and sets the final token to bi : ′ ′ fb (T ) (Xi )[−T ′ : − 1] = RS (Xi ), fb (T ) (Xi )[−1] = bi . (16) The answer shattering dimension ASdim(F; X , T ′ ) is the size of the largest such set.

YANG S REBRO L I

b=1

TSdim:

✓

input

✓

b=0 ✓

answer

thoughts

✓

input

b=1

ASdim:

✓

input

✓

thoughts

✓

answer

thoughts b=0

✓

answer

✓

input

✓

thoughts

✓

answer

Figure 2: Top (Trace Shattering Dimension TSdim): for b = 1 the entire trace matches the groundtruth; otherwise some tokens differ. Bottom (Answer Shattering Dimension ASdim): for each input, all generators share the same thought prefix and differ only in the final answer. Main Result. Since answer shattering is a stronger requirement (varying the final token while keeping the prefix fixed necessarily varies the full trace), we have ASdim ≤ TSdim. Unlike standard PAC learning, where the VC-dimension governs both bounds, here the upper bound scales with TSdim while the lower bound scales with ASdim; the gap between them determines how tight this generic characterization is. Theorem 6 (Generic Sample Complexity Bounds for CoT) Fix any (F, X , T ′ ). There exist universal constants C, c, δ0 > 0 such that: (T ′ )

(i) For all ε, δ ∈ (0, 1), Fe2e is CoT-learnable (using the learning rule ConsCoT ) with sample complexity TSdim(F; X , T ′ ) · log(1/ε) + log(1/δ) m(ε, δ) ≤ C · . (17) ε (ii) Let dAS := ASdim(F; X , T ′ ). If dAS ≥ 2, then for all ε ∈ (0, 1/8) and all δ ≤ δ0 , any CoT-learnability guarantee requires m(ε, δ) ≥ c · dAS /ε. The proof is deferred to Appendix D. For the upper bound, we reduce TSdim to the CoT trace loss class and apply standard VC theory. For the lower bound, we construct a hard distribution on an answer shattered set; since the trace prefix is fixed, each observed trace reveals only its own final token, leaving unseen points unpredictable. 4.3. Universality of Teacher Forcing for Transformers We now instantiate Theorem 6 for Transformer-based next-token generators. The proof follows the same partition-based analysis as Section 3, applied to each intermediate step of the CoT trace. See Appendix E for details. Theorem 7 (CoT Trace-Shattering Upper Bound) For any L ≥ 1, W ≥ L, finite alphabet |Σ| = K, and F ∈ FL,W , fix X ⊆ ΣT , lengths T, T ′ , and Tctx := T + T ′ . Then TSdim(F; X , T ′ ) = O (W L log(Tctx W LK)) . In particular, this is O(W L log(Tctx W )) whenever K ≤ poly(W ). 10

(18)

A Scratchpad Lower Bound. The upper bound shows that ConsCoT suffices. But is it necessary? Could a smarter algorithm achieve lower sample complexity by exploiting the structure of CoT traces? We show that the answer is no: any algorithm requires Ω(W L log Tctx /ε) samples for Transformers. The key idea is that CoT traces can act as a label-invariant scratchpad. The generator writes intermediate tokens that depend on the input but not on the labeling, so observing the trace prefix reveals no information about the final token. Nevertheless, the model can use this scratchpad internally, for example as a lookup table, to shatter Ω(log Tctx ) final answers. We formalize this intuition: Theorem 8 (CoT Answer-Shattering Lower Bound via Scratchpad) For any N ≥ 2, there exists a constant-size alphabet Σ, an input length T = O(log log N ), a generation length T ′ = Θ(N log N ), and a class F of constant-depth, constant-width hard-attention Transformers such that, with Tctx := T + T ′ , ASdim(F; ΣT , T ′ ) = Ω(log Tctx ).

(19)

Proof Sketch. We shatter m := ⌊log2 N ⌋ inputs. The generator writes an input-dependent but label-independent scratchpad, then uses one final readout to recover the requested label bit from a universal table. Let M := 2m = Θ(N ) and ℓ := ⌈log2 m⌉. For readability, write the scratchpad using the symbols {0, 1, #, END0, END1}, where # is a row separator and END0, END1 are anchor tokens. The formal proof uses constantly many decorated copies of these tokens to store finite-state carry/borrow information. As in Theorem 2, we use positional features containing τ and τ 2. Concretely, each INPUT Xi := binℓ (i)# ∈ Σℓ+1 encodes the index i in LSB-first binary. The generated scratchpad has two segments: • DECODE: binℓ (i−1)# → · · · → binℓ (0)# → END0. Counts down from i − 1 to 0. The anchor token END0 is placed at position p0 (i) = (i + 1)(ℓ + 1); the integer i is encoded into END0’s positional encoding. • TABLE: binm (0)# → binm (1)# → · · · → binm (M −1)# → END1. Enumerates all M = 2m binary strings in order, serving as a universal lookup table identical for all inputs and all labelings. P Final readout. The labeling y ∈ {0, 1}m is encoded into parameter s := j yj 2j , but s is gated to have no effect until the final step, so the scratchpad is label-invariant. Let Lin := ℓ + 1 and Lout := m + 1 be the row lengths in the input/decode and table segments. At the final step, Attn retrieves anchor position p0 (i) from END0; since p0 (i) = (i + 1)Lin , the FFN recovers i and computes r = p0 (i) + 1 + sLout + i, the position of the i-th bit in the s-th table row. A final attention lookup fetches that bit. Since the s-th row stores binm (s) and y = binm (s), this bit equals yi . Since different labelings produce identical traces except for the final token, this achieves answer shattering of m samples. The total generation length is T ′ = |DECODE| + |TABLE| + c = O(m · ℓ) + Θ(M · m) + c = Θ(N log N ). Thus m = Ω(log T ′ ). Since T = O(log log N ), we have Tctx = T + T ′ = Θ(T ′ ) and hence m = Ω(log Tctx ), giving ASdim ≥ Ω(log Tctx ). ■ 11

YANG S REBRO L I

Recursive Amplification. Amplifying the scratchpad construction by the recursive retrieval idea of Theorem 2 gives the following CoT lower bound. The amplification uses Θ(W ) independent prompt groups and Θ(L) retrieval rounds; each round contributes one scratchpad-style answershattering copy. Corollary 9 (CoT Lower Bounds for Transformers) There exist constants C0 , L0 , c, δ0 > 0 such that for every L ≥ L0 , W ≥ C0 L, and sufficiently large T ′ , there exist a finite alphabet Σ with K := |Σ| ≤ poly(W ), an input length T = O(log log T ′ ), a prompt domain X ⊆ ΣT , and a class F ∈ FL,W such that, with Tctx = T + T ′ , ASdim(F; X , T ′ ) ≥ c W L log Tctx .

(20)

Moreover, taking the worst case over token-prompt Transformer classes in FL,W , for all ε ∈ (0, 1/8), the CoT-learning sample complexity satisfies m(ε, δ0 ) ≥ c W L log(Tctx W/L)/ε. Here “sufficiently large” includes T ′ ≥ CW L log(W/L), which is needed only for the token-prompt ReLU witness. Universality of Teacher-Forcing / ConsCoT . Theorems 6 and 7 show that ConsCoT learns every F ∈ FL,W with sample complexity on the order of W L log(Tctx W LK)/ε, up to the standard log(1/ε) and confidence terms. Conversely, the lower bound has two independent token-prompt sources. The scratchpad construction in Corollary 9, together with Theorem 6, gives the CoT term W L log Tctx /ε. The remaining W L log(W/L)/ε term is an ordinary supervised obstruction, implemented with token prompts: a marker token selects one fixed positional encoding, after which the Transformer simulates a ReLU MLP. Taking the larger of the two witnesses gives the lower bound in Corollary 9. Thus teacher forcing is optimal in sample complexity for Transformers. In other words, despite the train-test asymmetry, matching every intermediate token is the right approach; exploiting the CoT traces in any other way cannot reduce sample complexity.

5. Discussion Other Activations. Our main result Theorem 1 extends to piecewise-polynomial activations, e.g. gated ReLU ((x, y) 7→ x · [y]+ ) (Shazeer, 2020). The same Warren-based analysis applies, except that the depth dependence becomes Õ(W L2 log T ) instead of Õ(W L log T ): the final output can have degree exponential in L as a piecewise polynomial of the parameters, and taking its logarithm yields an extra factor of L. Softmax Attention. Our approach for O(log T ) VC dimension does not extend to softmax attention because of the exponential function. To our knowledge, the best upper bound for VC dimension of softmax Transformers is poly(T ), by applying results such as Theorem 8.14 in (Anthony and Bartlett, 2009). Open Problems. Our results show that teacher forcing is optimal in sample complexity for learning Transformers with CoT supervision. Two questions remain open: (1) Is teacher forcing universally optimal for general hypothesis classes? In other words, can the gap between the trace shattering dimension and the answer shattering dimension be closed? (2) What is the sample complexity when learning the end-to-end mapping without access to intermediate reasoning traces? This setting is discussed by Joshi et al. (2025) and may exhibit fundamentally different scaling. 12

References Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. cambridge university press, 2009. Peter L Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear vc dimension bounds for piecewise polynomial networks. Neural computation, 10(8):2159–2173, 1998. Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1–17, 2019. Eric B Baum and David Haussler. What size net gives valid generalization? Neural computation, 1 (1):151–160, 1989. Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020. Anselm Blumer, André Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik–Chervonenkis dimension. Journal of the Association for Computing Machinery, 36 (4):929–965, 1989. doi: 10.1145/76359.76371. Thomas M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE transactions on electronic computers, EC-14(3):326– 334, 1965. Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. In International Conference on Machine Learning, pages 5793–5831. PMLR, 2022. Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in Neural Information Processing Systems, 36, 2023. Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171, 2020. Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, and Nathan Srebro. A theory of learning with autoregressive chain of thought, 2025. Marek Karpinski and Angus Macintyre. Polynomial bounds for VC dimension of sigmoidal and general pfaffian neural networks. Journal of Computer and System Sciences, 54(1):169–176, 1997. doi: 10.1006/jcss.1997.1477. Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in Transformers. In Advances in Neural Information Processing Systems (NeurIPS), 2023. Pascal Koiran and Eduardo D Sontag. Vc dimension in circuit complexity. In Proceedings of the 7th Annual Conference on Computational Learning Theory, pages 1–10, 1994. 13

YANG S REBRO L I

Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. In The Twelfth International Conference on Learning Representations (ICLR), 2024. Binbing Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representations (ICLR), 2023. Wolfgang Maass. Neural nets with superlinear vc-dimension. Neural Computation, 6(5):877–884, 1994. William Merrill and Ashish Sabharwal. The expresssive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923, 2023. William Merrill, Ashish Sabharwal, and Noah A Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843–856, 2022. Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 22(75):1–35, 2021. Noam Shazeer. Glu variants improve transformer. arXiv preprint arXiv:2002.05202, 2020. Jacob Trauger and Ambuj Tewari. Sequence length independent norm-based generalization bounds for transformers. arXiv preprint arXiv:2310.13088, 2023. Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, volume 30, 2017. Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: A case study on Approximating Transformers. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021. Ronald J Williams and David Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural computation, 1(2):270–280, 1989. Chenxiao Yang, Nathan Srebro, David McAllester, and Zhiyuan Li. Pencil: Long thoughts with short memory. arXiv preprint arXiv:2503.14337, 2025. Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? In Advances in Neural Information Processing Systems (NeurIPS), 2019. Yufeng Zhang, Boyi Liu, Qi Cai, Lingxiao Wang, and Zhaoran Wang. An analysis of attention via the lens of exchangeability and latent variable models. arXiv preprint arXiv:2212.14852, 2022. 14

Contents 1

Introduction

Preliminaries: Transformers and Autoregressive CoT 2.1 Transformers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Autoregressive Next-Token Generation . . . . . . . . . . . . . . . . . . . . . . . .

3 3 5

VC-Dimension of Transformers 3.1 Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 6 7

Auto-Regressive CoT with Transformers 4.1 Chain-of-Thought Learnability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Dual Complexity Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Universality of Teacher Forcing for Transformers . . . . . . . . . . . . . . . . . .

8 8 9 10

Discussion

A Technical Preliminaries A.1 PAC Learning Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 VC-Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16 16 16

B Proof of VC Dimension Upper Bound (Theorem 1) B.1 Recursive Parameter Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Final Bound Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17 17 19

C Proof of VC Dimension Lower Bound (Theorem 2) C.1 Recursive Retrieval Machine Lower Bound Ω(W L log T ) . . . . . . . . . . . . . . C.2 ReLU-Network Subclass and Combined Lower Bound . . . . . . . . . . . . . . .

20 20 23

D Proof of Generic Sample Complexity Bounds for CoT (Theorem 6) D.1 Auxiliary Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.2 Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.3 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24 24 25 25

E Proof of CoT Sample Complexity Upper Bound (Theorem 7)

F Proof of CoT Sample Complexity Lower Bound F.1 Logarithmic Shattering via Scratchpad (Theorem 8) . . . . . . . . . . . . . . . . . F.2 CoT Lower Bounds for Transformers (Corollary 9) . . . . . . . . . . . . . . . . .

29 29 33

YANG S REBRO L I

Appendix A. Technical Preliminaries This appendix provides the formal definitions of PAC learnability and VC-dimension used throughout the paper. A.1. PAC Learning Framework We begin with the standard framework of probably approximately correct (PAC) learning (Valiant, 1984). Binary Classification. Let X be a domain and F 01 ⊆ {0, 1}X be a hypothesis class of binary classifiers. A learning algorithm A receives m labeled samples S = {(xi , yi )}m i=1 drawn i.i.d. from b a distribution D over X × {0, 1}, and outputs a hypothesis f = A(S). The population risk of a hypothesis f under distribution D is LD (f ) := P(x,y)∼D [f (x) ̸= y].

(21)

A distribution D is realizable by F 01 if there exists f∗ ∈ F 01 such that LD (f∗ ) = 0. Definition 10 (PAC Learnability) A hypothesis class F 01 is PAC learnable if there exists an algorithm A and a function m : (0, 1) × (0, 1) → N such that for every ε, δ ∈ (0, 1) and every distribution D over X × {0, 1} that is realizable by F 01 , given m(ε, δ) i.i.d. samples S ∼ Dm(ε,δ) , the algorithm outputs fb = A(S) satisfying PS∼Dm(ε,δ) LD (fb) ≤ ε ≥ 1 − δ, (22) where the probability is over the random samples and the algorithm’s internal randomness (if any). The function m(ε, δ) is called the sample complexity. A.2. VC-Dimension The VC-dimension characterizes the sample complexity of PAC learning binary classifiers in the realizable setting. Definition 11 (Shattering) A hypothesis class F 01 shatters a finite set S = {x1 , . . . , xn } ⊆ X if for every labeling b ∈ {0, 1}n , there exists f ∈ F 01 such that f (xi ) = bi for all i ∈ [n]. Definition 12 (VC-Dimension) The VC dimension of F 01 , denoted VCdim(F 01 ), is the size of the largest set that can be shattered by F 01 . If arbitrarily large sets can be shattered, we set VCdim(F 01 ) = ∞. The fundamental theorem of statistical learning (Vapnik and Chervonenkis, 1971; Blumer et al., 1989) establishes that a class is PAC learnable if and only if it has finite VC-dimension. Moreover, the sample complexity is characterized by the VC-dimension: Theorem 13 (Fundamental Theorem of Statistical Learning) A hypothesis class F 01 is PAC learnable over all distributions if and only if VCdim(F 01 ) < ∞. Furthermore, the sample complexity satisfies: VCdim(F 01 ) + log(1/δ) VCdim(F 01 ) log(1/ε) + log(1/δ) Ω ≤ m(ε, δ) ≤ O . (23) ε ε

Appendix B. Proof of VC Dimension Upper Bound (Theorem 1) We establish the upper bound using the recursive partitioning framework for piecewise-polynomial networks (Bartlett et al., 1998), extended to handle the data-dependent routing of Average-Hard Attention. The proof proceeds in two steps. First, in Section B.1, we construct a partition of parameter space RW into regions where all discrete branching decisions (ReLU activations and attention routing) are fixed. Second, in Section B.2, we count the total number of sign patterns by combining Warren’s bound on the number of regions with a local polynomial argument. B.1. Recursive Parameter Partitioning Fix any Hard-Attention Transformer architecture A (as defined in Section 2.1) with depth L := L(A) and parameter count W := W (A). Let F denote the corresponding binary classifier class 01 F := FA = {H 7→ fθ01 (H) : θ ∈ RW }.

For any inputs H1:N := (H1 , . . . , HN ), define ΠF (H1:N ) := {(fθ01 (H1 ), . . . , fθ01 (HN )) : θ ∈ RW } .

(24)

The growth function is ΠF (N ) := maxH1:N ΠF (H1:N ). Assume VCdim(F ) ≥ N . Then there are N embedding sequences H1 , . . . , HN ∈ RT ×d with ΠF (H1:N ) = 2N . We will upper bound ΠF (H1:N ) as a function of N, W, L, T ; requiring 2N ≤ ΠF (H1:N ) then yields an upper bound on VCdim(F). Partition Decomposition. Let P be any partition of RW into regions. For each region C ∈ P, define (25) ΠC := {(fθ01 (H1 ), . . . , fθ01 (HN )) : θ ∈ C} as the number of distinct sign patterns realized by parameters in C. Then trivially ΠF (H1:N ) ≤

ΠC .

(26)

C∈P

We construct a partition PL (built layer-by-layer) such that: (i) on each C ∈ PL , all discrete branching decisions are fixed for H1:N , so the pre-threshold output becomes a polynomial in θ; (ii) |PL | is controlled by Warren’s bound. Lemma 14 (Warren’s Bound, (Bartlett et al., 1998, Lemma 2.1)) Let g1 , . . . , gm be polynomials in W variables, each of degree at most D. If m ≥ W , the number of distinct sign vectors (sgn(g1 (θ)), . . . , sgn(gm (θ))) ∈ {−1, 0, 1}m as θ varies in RW is at most 2(2emD/W )W . (ℓ)

Layerwise Refinement. Let Hn,t (θ) denote the layer-ℓ hidden representation for input Hn at token position t, viewed as a function of the parameters θ. We define partitions P0 , P1 , . . . , PL of RW , where Pℓ freezes all branching choices in the first ℓ layers. For ℓ ∈ {0, . . . , L}, we maintain (ℓ) that for every region C ∈ Pℓ , every sample n ∈ [N ], and every token t ∈ {0, . . . , T − 1}, Hn,t (θ) coincides on C with a polynomial of degree at most degℓ . 17

YANG S REBRO L I

Base case. Set P0 := {RW }. In our VC analysis, the inputs Hn ∈ RT ×d are fixed embedding (0) sequences, so Hn,t (θ) = Hn,t is constant in θ (degree 0). (The same argument also covers learnable embeddings, in which case H (0) is affine in θ.) Thus the inductive property holds with deg0 ≤ 1. Inductive step. Fix a layer ℓ ∈ [L] and consider a parent region C ∈ Pℓ−1 . By the inductive hypothesis, the inputs to layer ℓ (denoted H (ℓ−1) (θ)) are fixed polynomials on C. We refine C into sub-regions by fixing the outcomes of all discrete branching operations at layer ℓ. Since the layer applies attention before the FFN (Section 2.1), we do this in two stages: first freeze the discrete routing/tie structure of attention to make H̃ (ℓ) := Attn(ℓ) (H (ℓ−1) ) polynomial, then freeze the ReLU activation pattern of the FFN(ℓ) on H̃ (ℓ) . If residual connections are present, they only add previous polynomial representations, possibly after an affine projection, to sublayer outputs; this preserves the polynomial invariant and introduces no additional branching polynomials, so the same partition argument applies. 1. Attn routing (BAttn ). The Average-Hard Attention mechanism routes information based on the relative order of attention scores. To determine the set of maximizers, it suffices to determine the sign of the difference between any pair of scores. For each head h, sample n, query position i ∈ {0, . . . , T − 1}, and ordered key pair 0 ≤ p < q ≤ i (due to causal masking), we define the pairwise difference polynomial: D E (ℓ,h) (ℓ,h) (ℓ,h) (ℓ,h) gn,i,p,q (θ) := qn,i (θ), kn,p (θ) − kn,q (θ) . (27) Since queries q and keys k are affine transformations of the previous layer’s polynomial representations, g is a polynomial on C. We partition C based on the ternary signs (σ ∈ {+1, 0, −1}) of these difference polynomials. This fine-grained partition is crucial for handling the Average-Hard mechanism: fixing the ternary signs uniquely determines the strict ordering and equality relations among all allowed keys, which freezes the set of maximizers Mn,i := {j ≤ i | scorej = maxk≤i scorek } for every query. Once Mn,i is fixed, its cardinality becomes a constant integer, and the attention weights αi,j = 1[j ∈ Mn,i ]/|Mn,i | become fixed rational constants. Thus, within any refined sub-region, P (ℓ,h) the attention output Attn(H)n,i = j∈Mn,i |M1n,i | Vn,j (θ) collapses to a fixed linear combination of the polynomial value vectors. Since the values V are affine transformations of H (ℓ−1) , this preserves the polynomial property. The set BAttn collects all such pairwise differences. Accounting for causal masking, for each query position i there are i+1 key pairs, so each head contributes 2 PT −1 i+1 3 = O(T ) polynomials. Under a W -parameter budget, there are at most O(W ) heads, i=0 2 hence |BAttn | = O(N W T 3 ). 2. ReLU activations in the FFN (BFFN ). Fix any region where the attention routing decisions (ℓ) above are frozen. On such a region, every intermediate representation H̃n,t (θ) is polynomial in θ (as argued above). We refine sequentially through the internal affine/ReLU layers of the layer-ℓ FFN. For each sample n, token t, internal FFN layer r, and ReLU hidden unit u in that internal layer, (ℓ) let an,t,r,u (θ) denote the corresponding pre-activation, computed after the previous internal ReLU masks have been fixed. Since the input to each internal layer is polynomial on the current region, (ℓ) each an,t,r,u is polynomial there. We refine by the signs of all these pre-activations; after all internal masks are fixed, the FFN is a mask-fixed affine network, so its outputs remain polynomial in θ. The set BFFN collects all such pre-activations across all ReLU units in the FFN. Since D(ℓ) ≤ D0 = O(1), under a W -parameter budget, there are at most O(W ) ReLU units, so |BFFN | = O(N T W ). 18

Remark (sum vs. product). The quantities |BAttn | and |BFFN | count polynomials, so they add. The sequential composition (Attn then FFN) manifests instead in a product bound on the number of refined regions, since we refine first by BAttn and then by BFFN . Refinement Procedure. Let ∆Attn be the maximum number of child regions obtained by refining ℓ a parent region in Pℓ−1 using the ternary sign patterns of BAttn (padding with constant polynomials if |BAttn | < W ). By Lemma 14, 2e|B Attn |Dℓ W ∆Attn ≤ 2 . ℓ W

(28)

Next, within any attention-frozen region, let ∆FFN be the maximum number of child regions ℓ obtained by refining using the (binary) sign patterns of BFFN (again padding with constants if needed). The constant number of sequential internal refinements is absorbed into constants. Applying Lemma 14 gives 2e|B |D W FFN ℓ ≤ 2 ∆FFN . (29) ℓ W Let ∆ℓ := maxC∈Pℓ−1 |{C ′ ∈ Pℓ : C ′ ⊆ C}| denote the maximum number of child regions produced by refining any parent region. Since we refine sequentially, each parent region produces QL FFN Attn at most ∆ℓ ≤ ∆ℓ · ∆ℓ children in Pℓ , hence |PL | ≤ ℓ=1 ∆ℓ . Degree Bounds.

We have the crude parameter-counting bounds |BAttn | = O(N W T 3 ),

|BFFN | = O(N T W ).

For degrees: within any region where routing decisions and ReLU masks are fixed, a Transformer layer applies an attention sublayer and an FFN with at most D0 = O(1) internal affine/ReLU layers, hence only a constant number of affine maps (degree 1 in θ) to polynomial inputs (degree degℓ−1 ). Hence degℓ ≤ degℓ−1 +O(1) = O(ℓ) for representations. For branching polynomials, attention score differences are inner products of queries and keys (each degree ≤ degℓ−1 +O(1)), yielding Dℓ ≤ 2 degℓ−1 +O(1) = O(ℓ). B.2. Final Bound Derivation Total Number of Regions. |PL | ≤

L Y ℓ=1

∆ℓ ≤

Combining (28) and (29) across layers: L Y ℓ=1

∆Attn · ∆FFN ≤ ℓ ℓ

L Y 2e|BAttn |Dℓ W 2e|BFFN |Dℓ W 4 . W W

(30)

ℓ=1

Patterns within a Final Region. Fix a final region C ∈ PL . By construction, all branching deci(L) sions are fixed, so each output logit zn (θ) := ⟨wout , Hn,T −1 (θ)⟩ is a polynomial in θ. Since wout is included in θ, degout ≤ degL +1 = O(L). If N < W , the desired VC upper bound is immediate after increasing constants, so assume N ≥ W . Applying Lemma 14 to the N polynomials {zn }N n=1 yields 2eN deg W out ΠC ≤ 2 . (31) W 19

YANG S REBRO L I

Putting it Together. with (30) and (31):

From (26), ΠF (H1:N ) ≤

ΠF (H1:N ) ≤ |PL | · max ΠC ≤ C

C∈PL ΠC ≤ |PL | · maxC∈PL ΠC . Combining

L Y 2e|BAttn |Dℓ W 2e|BFFN |Dℓ W 4 W W

! ·2

2eN deg

ℓ=1

out

(32) If H1:N is shattered, then ΠF (H1:N ) = 2N . Taking logarithms: N ≤ O(W L) +

L X ℓ=1

W log

C |B

Attn |Dℓ

L X ℓ=1

W log

C |B

FFN |Dℓ

+ W log

C N deg W

out

(35)

Inverting the Inequality. We use the standard implication: if A ≥ 2, B ≥ 0, and N ≤ A log N + B, then N = O(A log A + B). Applying this to (35) with A = O(W L) and B = O(W L(log T + log L)) gives N ≤ O(W L log(W L) + W L log T + W L log L) = O(W L log(T W L)).

(36)

Hence VCdim(F) = O(W L log(T W L)). When L ≤ W , this simplifies to VCdim(F) = O(W L log(T W )).

Appendix C. Proof of VC Dimension Lower Bound (Theorem 2) We provide a constructive proof. Throughout this section, W denotes the total number of trainable parameters. We work at a fixed sequence length T (the same T in all parts). We index positions by t ∈ {0, . . . , T − 1}, where the last token (t = T − 1) plays the role of the query/output token. For the Recursive Retrieval Machine construction, we use residual connections, which are allowed in our architecture class. The proof has two components. First, in Section C.1, we present a Recursive Retrieval Machine 01 construction that yields a class FRRM ∈ F01 L,W with VC-dimension Ω(W L log T ). Second, in Section C.2, we demonstrate that the same Transformer setup contains a standard deep ReLU01 network subclass FReLU ∈ F01 L,W with VC-dimension Ω(W L log(W/L)). One of these two classes witnesses the final lower bound. C.1. Recursive Retrieval Machine Lower Bound Ω(W L log T ) Goal and Setup. Let B = ⌊log2 (T − 1)⌋, so that 2B ≤ T − 1. Note that B = Θ(log T ) for T ≥ 3, so we freely write log T in asymptotic bounds. Define a sample set S of size N := n · L · B, indexed by (j, ℓ, i) with j ∈ [n], ℓ ∈ [L], i ∈ [B]. Fix an arbitrary labeling Y ∈ {0, 1}N , written as Yj,ℓ,i . Our goal is to construct weights θ so that fθ01 (H (j,ℓ,i) ) = Yj,ℓ,i for all points in S. 20

Input Construction. Since our classifiers take embedding sequences as input, we directly specify (0) inputs H (j,ℓ,i) ∈ RT ×d of length T , consisting of T embedding vectors: (j,ℓ,i) (j,ℓ,i) (j,ℓ,i) (j,ℓ,i) ⊤ H (j,ℓ,i) = h0 , h1 , . . . , hT −2 , hT −1 .

(37)

We append two scalar coordinates to every embedding: (i) a constant coordinate c ≡ 1 (present in all positions), and (ii) an indicator coordinate η (equal to 1 on context positions and 0 on the query position). (i) Context sequence. For each t ∈ {0, . . . , T − 2}, define the context embedding (j,ℓ,i)

⊤ = t, −t2 , biti (t), c = 1, η = 1, 0 .

(38)

The component biti (t) ∈ {0, 1} is the i-th bit of integer t (in any fixed convention). Thus position t ∈ {0, . . . , T − 2} stores the bit pattern of integer t ∈ {0, . . . , T − 2}. (ii) Query token. Let ej ∈ Rn and eℓ ∈ RL be one-hot vectors. The query token activates the memory address j and the target layer ℓ: ⊤ (j,ℓ,i) ⊤ hT −1 = 0, 0, 0, c = 1, η = 0, e⊤ j , eℓ , 0 .

(39)

Parameter Encoding. layer ℓ, aggregate the B labels into an integer PB−1 For eachk address j and B − 1} ⊆ {0, . . . , T − 2}, which corresponds to Y 2 ∈ {0, . . . , 2 address sj,ℓ := k=0 j,ℓ,k+1 context position sj,ℓ ∈ {0, . . . , T − 2}. Then compress (sj,1 , . . . , sj,L ) into a single real number via base-2T encoding: L X sj,m aj := ∈ [0, 0.5). (40) (2T )m m=1

We designate a specific scalar dimension in the hidden state to act as an address register r. The value aj is not part of the input; it is stored in the trainable weights. The one-hot vector ej only tells the first block which stored number to use. Reading the identifiers once. The one-hot coordinates ej and eℓ are used only in the first Transformer block. In that block, trainable linear maps read them once: the query map uses ej to produce the scalar address r0 = 2T aj in the first attention score, and the FFN/residual part records the few scalars needed later, such as the updated address register, the target-layer number g = ℓ, and the accumulator. The context features (t, −t2 , biti (t), c, η) already have constant dimension and are carried forward by residual connections. After the first block, the network no longer carries ej or eℓ ; all later layers operate on a constant number of coordinates. This first read costs Θ(n) parameters for choosing aj from ej and O(L) parameters for choosing g from eℓ . Layer Dynamics. We analyze execution through an inductive invariant. We reserve disjoint coordinate subspaces: (1) a context subspace that stores (embedded versions of) the context features t, −t2 , biti (t), c, η and is never overwritten; (2) a query work subspace that stores the scalar register rk , the selected index t∗ , the extracted bit bk , and an accumulator z. The residual path carries the context coordinates unchanged from layer to layer. The attention and FFN updates may read these coordinates, but they write only to the query work coordinates. In particular, the computations that update the query work subspace never overwrite the context features needed for later retrievals. 21

YANG S REBRO L I

Lemma 15 (Inductive Extraction) Suppose that at retrieval step k (1 ≤ k ≤ L) the scalar adP sj,m dress available to the query projection equals rk−1 = L m=k (2T )m−k . For k = 1, this value is produced directly from ej by the first block’s query map; for k ≥ 2, it is the register value left by the previous block. Then: 1. The attention mechanism uniquely attends to the context token t∗ = sj,k . P sj,m 2. The FFN updates the register to rk = L m=k+1 (2T )m−(k+1) . Proof Attention step (Nearest-Neighbor Retrieval). We configure the query/key projections so that the attention score at the query position for a context token t equals ⟨q, kt ⟩ = 2rk−1 · t − t2 + M ηt ,

(41)

where M > 0 is a sufficiently large constant. Concretely, this is achieved by choosing kt = [ t, −t2 , ηt ] and q = [ 2rk−1 , 1, M ]. Observe that maximizing the term 2rk−1 t − t2 is equivalent to minimizing the squared Euclidean distance between the register and t: argmax(2rk−1 t − t2 ) = argmin |t − rk−1 |2 . t

(42)

The term M ηt simply acts as a mask to exclude the query token itself (where ηT −1 = 0). Thus, the attention mechanism effectively searches for the position t ∈ {0, . . . , T − 2} such that t is closest to rk−1 . Now write rk−1 = sj,k + δk , where δk :=

L X m=k+1

sj,m . (2T )m−k

Using 0 ≤ sj,m ≤ T − 2, we have 0 ≤ δk ≤ (T − 2)

∞ X

(2T )−p =

p=1

T −2 < 0.5. 2T − 1

(43)

Since |δk | < 0.5, the integer sj,k is strictly closer to rk−1 than any other integer. Thus t = sj,k is the unique minimizer, i.e., t∗ = sj,k is the selected position. Since the maximizer is unique, Average-Hard Attention reduces to standard deterministic selection. Update step (Left-Shift Operation). We choose the value projection so that the attention output retrieves two quantities: (i) the value t∗ = sj,k (read from the first coordinate in (38)), and (ii) the payload bit bk = biti (sj,k ) (read from the third coordinate). The FFN then computes the next register value using t∗ = sj,k : rk := 2T (rk−1 − sj,k ) = 2T δk .

(44)

This is the base-2T left shift. It is affine on the bounded relevant domain, so a two-layer ReLU FFN implements it exactly. Substituting the definition of δk confirms that rk =

L X

sj,m , (2T )m−(k+1) m=k+1

satisfying the inductive hypothesis.

Output Gating via Scalar Addressing. To select the output of the target layer ℓ without violating the constant-width constraint (i.e., avoiding an L-dimensional state), we employ a scalar addressing mechanism. As described above, the first block maps the target index eℓ to the scalar g := ℓ, which is stored in a protected coordinate. At each layer k, we implement a localized indicator function using a ReLU “hat” construction: 1 1 gatek (g) := 2 ReLU g − k − − 2 ReLU(g − k) + ReLU g − k + . (45) 2 2 One verifies that for integer g ∈ {1, . . . , L}, gatek (g) = 1{g = k}. We then maintain an accumulator z (initialized to 0) via the conditional update: z ← z + ReLU (bk + gatek (g) − 1) .

(46)

Since bk ∈ {0, 1}, the update term ReLU(bk + gatek (g) − 1) simplifies to bk if k = ℓ (where gatek (g) = 1) and vanishes otherwise. Thus, the final state satisfies z = bℓ = Yj,ℓ,i . Finally, choosing wout such that the output logit equals z − 12 ensures that the sign activation outputs the correct label. Parameter Budget Analysis. The construction utilizes an asymmetric parameter allocation. The only parameters that scale with n or L are the first-block weights that read ej and eℓ : Θ(n) weights choose the encoded value aj , and O(L) weights choose g = ℓ. In contrast, the Transformer backbone requires only O(L) parameters, as the Attn and FFN weights at each layer implement fixed algebraic operations on a constant-dimensional subspace, independent of n and T . Thus, the total parameter count is W = Θ(n) + O(L). For a sufficiently large absolute constant C0 , the regime 01 W ≥ C0 L lets us choose n = Θ(W ). Let FRRM ∈ F01 L,W denote the fixed architecture class used in this construction. Since each sample shatters Ω(L log T ) bits (specifically, B bits across L layers), 01 VCdim(FRRM ) ≥ n · L · B = Ω(W L log T ).

(47)

C.2. ReLU-Network Subclass and Combined Lower Bound We complement the Recursive Retrieval Machine construction with a depth-dependent lower bound by identifying a standard ReLU network subclass within the Transformer architecture. Lemma 16 (ReLU Subclass Containment) For any T ≥ 2, L ≥ 1, and W ≥ L, there exists a 01 class FReLU ∈ F01 L,W that contains, as a subclass, standard ReLU networks with Θ(L) layers and Θ(W ) trainable parameters acting on the query position. Proof We restrict to inputs where all context tokens are fixed, and only the query token varies. By choosing attention parameters so that, at the query position, the unique score-maximizing key is the query token itself (e.g., using a marker coordinate that equals 1 only on the query token), hard attention acts as an identity map on the query token. Hence, on this subclass, the residual-free Transformer reduces to iterated application of the position-wise FFN(ℓ) on the query token, i.e., a deep ReLU MLP (up to constant-factor depth) with Θ(W ) parameters. It is a standard result that depth-L′ ReLU networks with W ′ parameters have VC-dimension Ω(W ′ L′ log(W ′ /L′ )) (Bartlett et al., 2019). Applying this to our subclass with L′ = Θ(L) and W ′ = Θ(W ) yields a lower bound of Ω(W L log(W/L)). 23

YANG S REBRO L I

Combined Lower Bound. sum up to constants:

Combining the two regimes, one of the two fixed classes witnesses the

∃ F 01 ∈ F01 L,W

s.t. TW W = Ω W L log . VCdim(F 01 ) ≥ Ω W L log T + W L log L L

(48)

Appendix D. Proof of Generic Sample Complexity Bounds for CoT (Theorem 6) In this appendix, we provide the detailed proofs for Theorem 6. We first establish two auxiliary lemmas, then prove the upper and lower bounds. Full statement (for reference). Fix (F, X , T ′ ) and let dTS := TSdim(F; X , T ′ ) and dAS := ASdim(F; X , T ′ ). For every realizable pair (D, f∗ ) and every ε, δ ∈ (0, 1), if m≥C·

dTS log(1/ε) + log(1/δ) , ε

(49)

then with probability at least 1 − δ over an i.i.d. sample SCoT ∼ Dm labeled by traces Zi = ′ f∗ (T ) (Xi )[−T ′ :], the output fˆ = ConsCoT (SCoT ) satisfies Le2e (fˆ) ≤ ε. Moreover, if dAS ≥ 2, ′ there exist universal constants c0 , c1 > 0 such that for any learning rule A : (X × ΣT )∗ → ΣX and any ε ∈ (0, 1/8), if m < c0 · dAS /ε, then there exist a realizable distribution D over X and a target ′ f∗ ∈ F such that for SCoT ∼ Dm labeled by traces Zi = f∗ (T ) (Xi )[−T ′ :], (T ′ ) Pr Pr A(SCoT )(X) ̸= f∗ (X)[−1] ≥ ε ≥ c1 . (50) X∼D

CoT loss class. loss

′

For any generator f ∈ F and any pair (X, Z) ∈ X × ΣT , define the binary CoT ′ ℓf (X, Z) := 1 f (T ) (X)[−T ′ :] ̸= Z .

(51)

Let LCoT := {ℓf : f ∈ F}. D.1. Auxiliary Lemmas Lemma 17 (End-to-end error is dominated by CoT loss) For every f ∈ F and every realizable pair (D, f∗ ), ′ (52) Le2e (f ) ≤ EX∼D ℓf X, f∗ (T ) (X)[−T ′ :] . ′

′

Proof Fix X ∈ X and write Z := f∗ (T ) (X)[−T ′ :] ∈ ΣT . If f (T ) (X)[−T ′ :] = Z, then in ′ particular f (T ) (X)[−1] = Z[−1], so ′ ′ ′ ′ 1 f (T ) (X)[−1] ̸= f∗ (T ) (X)[−1] ≤ 1 f (T ) (X)[−T ′ :] ̸= f∗ (T ) (X)[−T ′ :] = ℓf (X, Z) (53) pointwise. Taking expectation over X ∼ D proves the claim.

Lemma 18 (TSdim equals the VC-dimension of the CoT loss class) TSdim(F; X , T ′ ) = VCdim(LCoT ),

(54)

(T ′ )

where LCoT = {ℓf : f ∈ F} with ℓf (X, Z) = 1[f (X)[−T ′ :] ̸= Z]. ′ Proof (≥) Suppose S = {X1 , . . . , Xn } is trace shattered with witness RS : S → ΣT . Consider the n labeled examples in the loss domain: {(Xi , RS (Xi ))}ni=1 . For any b ∈ {0, 1}n , by definition there exists fb ∈ F such that ℓfb (Xi , RS (Xi )) = 0 when bi = 1 and = 1 when bi = 0. Thus LCoT shatters these n points, so VCdim(LCoT ) ≥ n. ′ (i) (≤) Conversely, suppose VCdim(LCoT ) ≥ n. Then there exist (Xi , y0:T ′ −1 ) ∈ X × ΣT for i ∈ (i)

[n] such that for every label vector a ∈ {0, 1}n there exists fa ∈ F with ℓfa (Xi , y0:T ′ −1 ) = ai . We (i)

(j)

may assume the inputs Xi are distinct. Indeed, if Xi = Xj but y0:T ′ −1 ̸= y0:T ′ −1 , no deterministic generator can realize loss 0 on both points; if the two traces are equal, the two loss-domain points are identical and cannot both belong to a shattered set of distinct points. Let S = {X1 , . . . , Xn } (i) and define RS (Xi ) := y0:T ′ −1 . For any b ∈ {0, 1}n , apply shattering with ai := 1 − bi . Then ′ ℓfa (Xi , RS (Xi )) = 0 when bi = 1 and = 1 when bi = 0, which means fa (T ) (Xi )[−T ′ :] = RS (Xi ) if bi = 1 and differs if bi = 0. So S is trace shattered and TSdim(F ; X , T ′ ) ≥ n. D.2. Upper Bound Proof [Proof of the upper bound in Theorem 6] By Lemma 18, VCdim(LCoT ) = dTS . In the realizable setting, ConsCoT can output some fˆ with zero empirical loss on the sample (i.e., ℓfˆ(Xi , Zi ) = ′

0 for all i), where Zi = f∗ (T ) (Xi )[−T ′ :]. It remains to show that any hypothesis in a VC class that is consistent on m samples has small true error. A standard VC generalization bound (realizable case) states that there exists a universal constant C > 0 such that if dTS log(1/ε) + log(1/δ) m≥C· , (55) ε then with probability at least 1 − δ, ′ EX∼D ℓfˆ X, f∗ (T ) (X)[−T ′ :] ≤ ε. (56) Finally, Lemma 17 gives Le2e (fˆ) ≤ ε. D.3. Lower Bound Proof [Proof of the lower bound in Theorem 6] Let d := dAS and assume d ≥ 2 (otherwise the claim is trivial). By Definition 5, there exist a set S = {X1 , . . . , Xd } ⊆ X , a prefix assignment ′ RS : S → ΣT −1 , such that for every b ∈ {0, 1}d there exists fb ∈ F with ′

′

fb (T ) (Xi )[−T ′ : − 1] = RS (Xi ),

fb (T ) (Xi )[−1] = bi

∀i ∈ [d],

(57)

so the first T ′ − 1 generated tokens are fixed while the final token equals bi . Fix ε ∈ (0, 1/8). We define a hard distribution D supported on S: put a large mass on X1 and spread the remaining mass over X2 , . . . , Xd : 4ε D(X1 ) = 1 − 4ε, D(Xi ) = for i = 2, . . . , d. (58) d−1 25

YANG S REBRO L I

Random target choice. Let B = (B1 , . . . , Bd ) ∈ {0, 1}d be uniformly random, and choose the corresponding target generator fB ∈ F guaranteed above. We analyze the performance of an arbitrary learning rule A under the joint randomness of B and the sample SCoT ∼ Dm labeled by full traces of fB . Let gb := A(SCoT ) ∈ ΣX be the final-token predictor returned by the learner. Define the rarepoints risk d X Lrare := D(Xi ) · 1 gb(Xi ) ̸= Bi . (59) i=2

Note that 0 ≤ Lrare ≤

i=2 D(Xi ) = 4ε.

Key observation: if a point is unseen, its label is unpredictable. Fix i ∈ {2, . . . , d} and let Ei be the event that Xi does not appear in the sample SCoT . On the event Ei , the entire observed sample (inputs and traces) is independent of the bit Bi : indeed, the sample contains traces only for points Xj that were drawn, and for every such point Xj ∈ S the trace prefix is the fixed value RS (Xj ) (independent of B), while the final token reveals only Bj for those drawn indices j. Formally, conditioned on Ei , the sample is a function of {Bj : Xj appears in SCoT } and is therefore independent of Bi . Since Xi never appears under Ei , the bit Bi is never revealed in the data and remains uniform {0, 1} even conditioned on the realized sample. Therefore, 1 P gb(Xi ) ̸= Bi | Ei ≥ . 2

(60)

Taking expectation, P gb(Xi ) ̸= Bi ≥ P(Ei ) · 12 . Compute P(Ei ).

4ε Each draw hits Xi with probability 4ε/(d − 1), hence P(Ei ) = 1 − d−1

Lower bound the expected risk. E[Lrare ] =

d X i=2

By linearity of expectation and symmetry over i = 2, . . . , d,

d X 4ε 1 4ε m 4ε m D(Xi )·P gb(Xi ) ̸= Bi ≥ · · 1− = 2ε 1− . (61) d−1 2 d−1 d−1 i=2

4ε m 3 Using Bernoulli’s inequality (1 − u)m ≥ 1 − mu for u ∈ [0, 1], if m ≤ d−1 16ε , then (1 − d−1 ) ≥ 4 , 3 3 so E[Lrare ] ≥ 2ε · 4 = 2 ε. Since d ≥ 2, the assumption m < d/(32ε) implies m ≤ (d − 1)/(16ε), so this condition is satisfied after adjusting constants.

From expectation to probability.

Let p := PB,SCoT (Lrare ≥ ε).

Since Lrare ≤ 4ε, we have E[Lrare ] ≤ ε · (1 − p) + 4ε · p = ε + 3εp. Thus E[Lrare ] ≥ 23 ε implies p ≥ 16 . In other words, PB,SCoT (Lrare ≥ ε) ≥ 61 . Fix a hard target. f∗ := fb∗ ,

By averaging over B, there exists a particular b∗ ∈ {0, 1}d such that, letting

PSCoT ∼Dm

d X

D(Xi ) · 1 A(SCoT )(Xi ) ̸= f∗

i=2

(T ′ )

! 1 (Xi )[−1] ≥ ε ≥ . 6

(62)

Since the full end-to-end risk dominates the rare-points risk Lrare , the same lower bound holds for ′ P PX∼D [A(SCoT )(X) ̸= f∗ (T ) (X)[−1]] ≥ ε . Setting c0 = 1/32 (absorbing constants) and c1 = 1/6 proves the theorem.

Appendix E. Proof of CoT Sample Complexity Upper Bound (Theorem 7) Proof [Proof of Theorem 7] Throughout this proof, we use the notation from Theorem 7: T ′ denotes the generation length, and Tctx = T + T ′ denotes the total context length. Fix any F ∈ FL,W . We prove the TSdim bound for this fixed class by upper bounding the VC-dimension of the CoT loss class. Recall the CoT loss class: ′ ℓf (X, Z) := 1 f (T ) (X)[−T ′ :] ̸= Z , LCoT := {ℓf : f ∈ F}. (63) Equivalently (since f is deterministic), ℓf (X, Z) = 0 iff f (X ∥Z[:t]) = Z[t] for all t ∈ {0, . . . , T ′ − 1}. Let K := |Σ|. By Lemma 18 (with T ← T ′ ), TSdim(F; X , T ′ ) = VCdim(LCoT ).

(64)

Hence it suffices to show VCdim(LCoT ) = O(W L log(Tctx W LK)). Step 1: Unroll teacher-forcing prefixes and reduce to a growth bound for F . Fix n ≥ 1 and ′ consider any n labeled examples {(Xi , Zi )}ni=1 ⊆ X × ΣT . For each (i, t) ∈ [n] × {0, . . . , T ′ − 1}, define the teacher-forcing prefix context ci,t := Xi ∥ Zi [:t].

(65)

Each ci,t has length at most T + t ≤ Tctx − 1. Let M := nT ′ and enumerate these contexts as {cj }M j=1 := {ci,t }(i,t)∈[n]×{0,...,T ′ −1} . Define the multi-class growth function for next-token generators: ΠF (M ) := max ΠF (c1:M ). ΠF (c1:M ) := (f (c1 ), . . . , f (cM )) ∈ ΣM : f ∈ F , c 1:M

|cm |≤Tctx ∀m

(66) Now observe: for a fixed f , the loss vector (ℓf (X1 , Z1 ), . . . , ℓf (Xn , Zn )) ∈ {0, 1}n is a deterministic function of the prediction vector (f (c1 ), . . . , f (cM )) ∈ ΣM , since ℓf (Xi , Zi ) = 0 iff f (ci,t ) = Zi [t] for all t ∈ {0, . . . , T ′ − 1}. Therefore, the number of distinct {0, 1}n labelings realized by LCoT on {(Xi , Zi )}ni=1 is at most ΠF (c1:M ) ≤ ΠF (M ). In particular, if LCoT shatters these n examples, then 2n distinct loss vectors occur, so 2n ≤ ΠF (nT ′ ). (67) Step 2: A growth bound for multi-class Transformer next-token generators. exist universal constants C, C ′ > 0 such that for all M ≥ 1, log ΠF (M ) ≤ C · W L · log(C ′ M Tctx W LK).

We claim there

(68)

Proof [Proof of (68)] Fix arbitrary contexts c1:M , each of length at most Tctx , and write τm := |cm | − 1 for the last position of context cm . Consider the parameter vector θ ∈ RW . We apply 27

YANG S REBRO L I

the same recursive partitioning construction as in the VC upper bound proof (Appendix B), with N ← M and context length Tctx . Concretely, at each layer we first refine by the attention scoredifference polynomials (freezing Average-Hard routing/ties), and then refine by all internal FFN ReLU pre-activations (freezing ReLU masks), exactly as in Appendix B. Note that since the token embedding matrix WTE is included in θ, the layer-0 representations are affine in θ; this is already accounted for in the base case of Appendix B. Thus we obtain a final partition PL of RW such that: (i) For every cell C ∈ PL , all branching decisions are fixed on c1:M ; (L)

(ii) On each C ∈ PL , every hidden representation Hm,t (θ) is polynomial in θ with degree degout = O(L); (iii) The number of cells satisfies (by the same Warren bound calculation as the VC upper bound proof): log |PL | ≤ O(W L log(M Tctx W L)). (69) It remains to bound, for a fixed final cell C ∈ PL , how many distinct next-token prediction vectors (fθ (c1 ), . . . , fθ (cM )) can arise as θ ranges over C. For each input m ∈ [M ] and token x ∈ Σ, define the output logit (L) zm,x (θ) := WDE [x, :], Hm,τ (θ) . m

(70)

(L)

On a fixed cell C, Hm,τm (θ) is polynomial in θ of degree O(L), so the logit zm,x (θ) is polynomial in θ of degree at most O(L) + 1 = O(L) (since the decoding matrix WDE is a coordinate projection of θ). The predicted token is fθ (cm ) = arg maxx∈Σ zm,x (θ), with any fixed tie-breaking rule. For multi-class argmax outputs, it suffices to control the ternary sign pattern of all pairwise logit differences: ∆m,x,x′ (θ) := zm,x (θ) − zm,x′ (θ), m ∈ [M ], x < x′ ∈ Σ. (71) There are mout = M K2 = O(M K 2 ) such polynomials, each of degree at most Dout = O(L). On any region where all these ternary signs are fixed, the induced ordering (with ties) of the logits is fixed for every m, hence the argmax output fθ (cm ) is fixed as well. Therefore, the number of distinct prediction vectors realized within C is at most the number of distinct ternary sign patterns of {∆m,x,x′ }. Applying Warren’s bound (Lemma 14) to these mout polynomials (padding with constant polynomials if mout < W ) gives log ΠC ≤ O(W log(M KL)), (72) where ΠC denotes the number of distinct prediction vectors realized by parameters in cell C. Finally, summing over cells, X ΠF (c1:M ) ≤ ΠC ≤ |PL | · max ΠC . (73) C∈PL

C∈PL

Combining (69) and (72), absorbing the within-cell term into O(W L log(M Tctx W LK)), yields (68).

Step 3: Conclude the VC bound for LCoT .

Combine (67) with (68) at M = nT ′ :

n ≤ log ΠF (nT ′ ) ≤ C · W L · log(C ′ nT ′ Tctx W LK).

(74)

Using log(nT ′ Tctx W LK) ≤ log n + log(T ′ Tctx W LK) and T ′ ≤ Tctx , we get n ≤ C · W L · log n + C · W L · log(Tctx W LK) + O(W L).

(75)

Applying the standard inversion (if n ≤ a log n + b then n = O(a log a + b)), with a = Θ(W L) and b = Θ(W L log(Tctx W LK)), yields VCdim(LCoT ) = O(W L log(Tctx W LK)).

(76)

When K ≤ poly(W ), this simplifies to O(W L log(Tctx W )). By (64), this proves the TSdim bound. Step 4: Consequence for sample complexity. Plugging dTS = TSdim(F; X , T ′ ) into Theorem 6 gives dTS log(1/ε) + log(1/δ) m(ε, δ) = O , (77) ε and substituting dTS = O(W L log(Tctx W LK)) yields the corresponding sample-complexity upper bound. Since F ∈ FL,W was arbitrary, the TSdim bound holds for every class in the family.

Appendix F. Proof of CoT Sample Complexity Lower Bound In this appendix, we prove the lower bounds for CoT sample complexity. We first establish that the answer shattering dimension can grow logarithmically with the generation length (Theorem 8), then prove the Transformer scratchpad ASdim lower bound and combine it with the ordinary supervised obstruction (Corollary 9). F.1. Logarithmic Shattering via Scratchpad (Theorem 8) Proof [Proof of Theorem 8] We construct a constant-depth, constant-width autoregressive Transformer whose first T ′ − 1 generated tokens are independent of the labeling, while the final token realizes an arbitrary labeling of Ω(log Tctx ) inputs. Next-position convention. At the step that generates the token in absolute position τ , the visible prefix occupies positions 0, . . . , τ − 1, and the Transformer output is read from the last visible position τ − 1, as in Section 2.2. Since the positional encoding contains the scalar position, the representation at the last visible position can compute the next-position scalar τ = (τ − 1) + 1. Below, when we say that the current step uses τ , we mean this computed next-position scalar; no extra query token is introduced. Assume first that N is larger than a universal constant; smaller N are absorbed by constants. Let m := ⌊log2 N ⌋, M := 2m , (78) so M = Θ(N ). We answer-shatter m inputs. Set ℓ := ⌈log2 m⌉,

Lin := ℓ + 1,

Lout := m + 1, 29

T := Lin .

(79)

YANG S REBRO L I

Decorated constant-size alphabet. The main text displays the scratchpad using the symbols {0, 1, #, END0, END1}. Formally, we use constantly many decorated copies of these tokens. These are still ordinary tokens in a constant-size alphabet; the decorations simply store the finitestate information, such as carry and borrow bits, in the generated prefix itself. Let Σ = {0, 1, END0, END1, PAD} ∪ Γsep ∪ Γdec ∪ Γtab ,

(80)

Γsep = {#zin , #zdec : z ∈ {0, 1}} ∪ {#tab },

(81)

where Γdec = {Db,ρ,z : b, ρ, z ∈ {0, 1}},

Γtab = {Tb,ρ : b, ρ ∈ {0, 1}}.

(82)

Here b is the visible bit. In Db,ρ,z , ρ is the outgoing borrow for the decrement rule and z records whether all bits generated so far in the current decode row are zero. In Tb,ρ , ρ is the outgoing carry for the increment rule. The superscript on #zin and #zdec records whether the preceding row is all zero. These decorations are deterministic functions of the input and the already generated prefix, and are never label-dependent. For each integer a, let binr (a) be the r-bit binary representation of a in least-significant-bit first order. Define 1[i=0] xi := binℓ (i)#in ∈ ΣT , i = 0, . . . , m − 1, (83) and let S := {x0 , . . . , xm−1 }. Addressing and finite-state primitives. We use fixed quadratic positional features: the token at absolute position p contains positional coordinates (p, −p2 , 1). Thus a hard-attention head can retrieve any visible integer position r: with query q(r) = (2r, 1, 0) and keys kp = (p, −p2 , 1), the score is ⟨q(r), kp ⟩ = 2rp − p2 = r2 − (p − r)2 , (84) whose unique visible maximizer is p = r. We also use constant-size ReLU equality gates. For integer a, define 1 1 − 2ReLU(u − a) + ReLU u − a − . eqa (u) := 2 ReLU u − a + 2 2

(85)

For every integer u, eqa (u) = 1[u = a]. Any Boolean function of constantly many token-type indicators, state bits, and such equality gates can be implemented by a constant-size ReLU FFN. All constants such as m, M and the final position are fixed as part of the architecture for this value of N . The label-invariant scratchpad. encode it as s = s(y) :=

m−1 X

Fix an arbitrary labeling y = (y0 , . . . , ym−1 ) ∈ {0, 1}m and

yi 2i ∈ {0, . . . , M − 1},

so that

biti (s) = yi .

(86)

i=0

The only label-dependent trainable scalar is βs := sLout . 30

(87)

It is gated off until the final generation step. Set T ′ := mLin + M Lout + 3.

(88)

For input xi , the first T ′ − 1 generated tokens form a prefix RS (xi ) independent of s. If decorations are ignored, this prefix is binℓ (i − 1)#, binℓ (i − 2)#, . . . , binℓ (0)#, END0

(89)

(empty before END0 when i = 0), followed by binm (0)#, binm (1)#, . . . , binm (M − 1)#, END1,

(90)

followed by PAD tokens until the prefix length is exactly T ′ − 1. Generating the scratchpad. We describe the next-token rule. A constant number of heads retrieve: (i) the latest boundary token among the decorated separators, END0, and END1, using a score with a large type bonus plus the position coordinate; (ii) the unique END0 token if it has appeared; (iii) the unique END1 token if it has appeared; (iv) the same-column predecessor at position τ − Lin ; and (v) the same-column predecessor at position τ − Lout . The quadratic addressing primitive implements the constant-offset predecessor retrievals. When such a predecessor position is not visible, the corresponding value is ignored by the FFN. If END1 has already appeared and the current step is not the final step, the model outputs PAD. If END0 has appeared but END1 has not, the model is in the table phase. Let p0 be the position of END0. The table ends when eqM Lout τ − (p0 + 1) = 1, (91) at which point the model outputs END1. Otherwise, write k = τ − b − 1, where b is the latest boundary position. If k = m, the model outputs #tab . If 0 ≤ k < m, it outputs the next bit of the current table row. The first row after END0 is all zeros. Later rows are obtained by incrementing the previous row by one in LSB-first order: vk = qk ⊕ ck ,

ck+1 = qk ∧ ck ,

(92)

where qk is the bit retrieved from position τ − Lout , and ck is 1 for k = 0 and otherwise the carry bit stored in the previous generated table token. The emitted token is Tvk ,ck+1 . If END0 has not appeared, the model is in the decode phase. If the latest separator is #1in or #1dec , then the preceding row is all zero and the model outputs END0. Otherwise let k = τ − b − 1. If k = ℓ, the model has completed a decode row; it reads the zero-so-far flag z from the previous generated decode token and outputs #zdec . If 0 ≤ k < ℓ, the model decrements the previous row by one in LSB-first order: vk = qk ⊕ ρk , ρk+1 = (1 − qk ) ∧ ρk , (93) where qk is the bit retrieved from position τ − Lin , and ρk is 1 for k = 0 and otherwise the borrow bit stored in the previous generated decode token. The zero-so-far flag is updated as ( 1[v0 = 0], k = 0, zk+1 = (94) zk ∧ 1[vk = 0], k > 0. 31

YANG S REBRO L I

The emitted token is Dvk ,ρk+1 ,zk+1 . All these rules are Boolean functions of constantly many retrieved symbols, state bits, and equality gates, and hence are implemented exactly by a constant-size FFN. They generate the desired decode segment, then the universal table, then padding. In particular, END0 appears at absolute position p0 (i) = (i + 1)Lin . (95) The entire generated prefix is independent of s. Gating the label-dependent scalar.

Let τ⋆ := T + T ′ − 1

(96)

be the absolute position of the final generated token, and set Gfin := eqτ⋆ (τ ). Since 0 ≤ βs ≤ M Lout , choose a hard-wired constant B > M Lout . The product of the label-dependent scalar with the final-step gate is implemented by βsgated := ReLU βs − B(1 − Gfin ) .

(97)

This equals 0 before the final step and equals βs at the final step. The output logits are gated similarly, so the scratchpad rule is used before the final step and the readout rule below is used at the final step. Final readout. At the final step, the visible prefix contains END0, the full table, END1, and padding. The readout uses two consecutive attention sublayers. The first attention sublayer retrieves the unique END0 token and writes its position v = p0 (i) into a work coordinate. The following FFN computes 1 r = 1+ v + βsgated . (98) Lin At the final step, βsgated = βs = sLout . Since v = p0 (i) = (i + 1)Lin , r = p0 (i) + i + 1 + sLout .

(99)

The table starts at position p0 (i) + 1, and row s starts at p0 (i) + 1 + sLout . Thus the position of the i-th bit of row s is p⋆ = p0 (i) + 1 + sLout + i = r. (100) The second attention sublayer uses query q(r) = (2r, 1, 0) and retrieves the token at p⋆ . Its visible bit is biti (s) = yi , and the output layer maps visible bit 0/1 to the answer token 0/1. Therefore, for every labeling y ∈ {0, 1}m , choosing βs = sLout gives a generator fs such that, for every i ∈ {0, . . . , m − 1}, ′

fs(T ) (xi )[−T ′ : − 1] = RS (xi ),

′

fs(T ) (xi )[−1] = yi .

(101)

Hence S is answer shattered, and ASdim(F; ΣT , T ′ ) ≥ |S| = m. 32

(102)

Size and length. The construction uses a constant number of heads, a constant number of layers, and constant hidden dimension: the only work coordinates are constantly many positions, Boolean flags, and token-type indicators. Residual connections or identity sublayers copy these work coordinates between the two readout hops. Finally, T = Lin = O(log m) = O(log log N ), (103) and T ′ = mLin + M Lout + 3 = Θ(M m) = Θ(N log N ).

(104)

Tctx = T + T ′ = Θ(T ′ ) = Θ(N log N ),

(105)

Thus and so m = Θ(log N ) = Ω(log Tctx ). This proves the theorem.

F.2. CoT Lower Bounds for Transformers (Corollary 9) Proof [Proof of Corollary 9] We prove the scratchpad amplification lower bound. Scratchpad amplification.

Let Camp be a sufficiently large universal constant and set L R := . Camp

(106)

The constant Camp accounts for one recursive retrieval round, the constant-depth scratchpad transducer of Theorem 8, and the constant-depth final readout. Choose L0 ≥ 2Camp ; since L ≥ L0 , we have R ≥ 1. Choose m as the largest integer such that, with M := 2m , M (m + 1) ≤ T ′ /C

(107)

for a sufficiently large universal constant C. Then m = Θ(log T ′ ) and M ≤ T ′ . Let ℓ := ⌈log2 m⌉,

Lin := ℓ + 1,

Lout := m + 1.

(108)

Alphabet and inputs. Let Γ be the constant-size decorated alphabet used in the proof of Theorem 8. Enlarge it by identifier and round tokens: Σ := Γ ∪ {ID1 , . . . , IDn } ∪ {LYR1 , . . . , LYRR }.

(109)

Here n will be chosen as Θ(W ), so |Σ| = O(W + L). For each triple (j, k, i) ∈ [n] × [R] × {0, . . . , m − 1}, define 1[i=0]

Xj,k,i := IDj ∥ LYRk ∥ binℓ (i) ∥ #in

∈ ΣT ,

T := 2 + Lin .

(110)

Let S := {Xj,k,i } and X := S. Then |S| = nRm. Common prefix. For each Xj,k,i , the generator runs the scratchpad construction of Theorem 8 1[i=0] on the suffix binℓ (i) ∥ #in and ignores the two-token header while generating the first T ′ − 1 tokens. The header only shifts absolute scratchpad positions by H := 2. 33

(111)

YANG S REBRO L I

′

Thus all parameter settings share the same prefix assignment RS : S → ΣT −1 : the DECODE segment, the universal TABLE segment, and PAD tokens, exactly as in Theorem 8. This prefix depends on i but not on the labeling. Encoding labels. Fix any labeling b ∈ {0, 1}S , written as bj,k,i . For each (j, k) ∈ [n] × [R], encode the m labels into sj,k :=

m−1 X

bj,k,i 2i ∈ {0, . . . , M − 1},

biti (sj,k ) = bj,k,i .

(112)

i=0

Multiplexing row indices. The embedding of IDj stores the packed scalar (0) rj :=

R X u=1

sj,u , (2T ′ )u−1

(113)

and the embedding of LYRk stores g := k. At the final generation step, a constant number of heads (0) copies (rj , g) from the two header tokens into protected work coordinates. These coordinates are ignored before the final step, so they cannot affect RS . The recursive retrieval then proceeds for R rounds. At the beginning of round u, the register has the form R X sj,v 1 r(u−1) = = sj,u + δu , 0 ≤ δu < . (114) ′ v−u (2T ) 2 v=u Using quadratic positional features, a hard-attention head with query q = (2r(u−1) , 1, 0) selects the unique visible position t⋆ = sj,u . The FFN performs the base-2T ′ left shift r(u) := 2T ′ (r(u−1) − t⋆ ).

(115)

To keep only the selected digit, use the usual ReLU hat gate gateu (g) = 1[g = u] on integer g ∈ [R] and update a protected accumulator by ŝ ← ŝ + ReLU(t⋆ + M0 (gateu (g) − 1)) − ReLU(M0 (gateu (g) − 1)) , (116) where M0 > T ′ is fixed. This adds t⋆ iff u = k and adds zero otherwise. Hence after R rounds, ŝ = sj,k . Set β := Lout ŝ. Final readout. At the final step, the prefix contains the complete scratchpad. Let v be the absolute position of the unique END0 token. Because of the header, v = H + (i + 1)Lin .

(117)

A first readout attention sublayer retrieves this token and writes v into a work coordinate. The next FFN computes r := v + β +

v−H = H + (i + 1)Lin + sj,k Lout + (i + 1). Lin

(118)

This is exactly the absolute position of the i-th bit in row sj,k of the TABLE segment. A second readout attention sublayer retrieves that token, whose visible bit is biti (sj,k ) = bj,k,i . The output layer maps visible bit 0/1 to two answer tokens. 34

Shattering and parameter budget. The scratchpad subspace never reads the multiplexing registers, and the output rule for the first T ′ − 1 generated tokens depends only on the scratchpad subspace. Therefore every labeling produces the same prefix assignment RS , and only the final token depends on sj,k . Thus S is answer shattered and ASdim(F⋆ ; X , T ′ ) ≥ |S| = nRm = Ω(W L log Tctx ),

(119)

where m = Θ(log T ′ ) = Θ(log Tctx ) because T = O(log log T ′ ). The labeling-dependent parameters are the n packed ID embeddings, costing O(n) parameters; the round-token embeddings and backbone cost O(R) ⊆ O(L). Choosing n = Θ(W ) and W ≥ C0 L gives total parameter count at most W . Sample-complexity lower bound. give

Scratchpad witness. The ASdim bound above and Theorem 6 Ω

W L log Tctx ε

(120)

samples. Supervised ReLU witness via token prompts. We use the same fixed-prefix reduction, but realize the supervised inputs as token prompts rather than embedding-valued prompts. By the ReLU subclass from Lemma 16, after adjusting constants the Transformer family contains a ReLU-network subclass H with VCdim(H) = Ω(W L log(W/L)). (121) Let D := ⌊cR W L log(W/L)⌋ and choose shattered points a1 , . . . , aD for H. The “sufficiently large T ′ ” condition includes T ′ ≥ CR D, so the prompt length below is at most a constant fraction of the total context length. Let ΣR = {blank, mark, query, #, 0, 1}. For each i ∈ [D], define a token prompt Xi ∈ ΣD+1 R with mark at position i, query at the last prompt position, and blank elsewhere. The positional encoding is fixed and non-learned; we set its first coordinates at position i to be the ReLU input ai . Thus the inputs ai are supplied by the fixed positional encoding and do not consume the W trainable parameters. At the final generation step, a constant-size attention wrapper retrieves the unique mark token and copies these positional-encoding coordinates to the current output position. The remaining layers simulate the ReLU network h ∈ H on the copied vector. Before the final step, a positional gate forces the output to be the fixed dummy token #; at the final step, the dummy branch is disabled and the classifier branch outputs 0 or 1. Hence each h ∈ H gives a token-prompt generator fh satisfying ′ (T ′ ) (T ′ ) fh (Xi )[−T ′ : − 1] = #T −1 , fh (Xi )[−1] = h(ai ). (122) The prefix is independent of h, so any CoT learner for this token-prompt subclass is also a supervised ′ learner for H: given labeled examples (ai , h(ai )), feed the learner the CoT examples (Xi , #T −1 ∥ h(ai )) and read off its final-token predictor. The VC lower bound in Theorem 13 gives W L log(W/L) Ω (123) ε samples. 35

YANG S REBRO L I

Taking the harder of these two witnesses, W L log Tctx W L log(W/L) W L log(Tctx W/L) max Ω ,Ω =Ω , ε ε ε after adjusting constants.

(124)

Record · ID 267650 · SHA-256 2aa8683cd8f47884
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.