From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP Michael Rizvi-Martel1∗ Satwik Bhattamishra2 1
Mila & Université de Montréal
2
Guillaume Rabusseau1
University of Oxford
4
Michael Hahn4
Saarland University
arXiv:2607.11760v1 [cs.LG] 13 Jul 2026
Abstract A theoretical understanding of Transformers is crucial to better understand the capacities and limitations of large language models (LLMs). There is much work analyzing the expressivity of attention-based models. By proposing handcrafted weights or using computational complexity arguments, a large amount of past theoretical works have sought to characterize which tasks are and which are not in the hypothesis class of Transformer models. However, little work investigates the learnability of such solutions. In this work, we make progress towards this goal. Inspired by recent loss landscape analysis work, we propose preliminary sample complexity bounds for learning C-RASP constructions with Transformers.
1
Introduction
Theoretical understanding of Transformer models is crucial to better understanding the capacities and limitations of modern large language models (LLMs). Current theoretical analyses of transformers focus primarily on expressivity, characterizing what these models can or cannot encode in their weights, and situating them in known complexity classes [2, 5, 7, 6]. Notably, RASP [8] and C-RASP [9, 10] established an equivalence between transformers and handcrafted programming languages with specific features. However, much of this work is largely detached from learnability, leaving open the question of how such expressive capabilities can actually be acquired in training. Recent work by [4] suggests that generalization in deep learning can be largely attributed to the volume of ”good” solutions in the loss landscape. This idea is formalized by [3], who show that, within a PAC learning framework, a randomly initialized network generalizes well if there exists a “narrow teacher” network consistent with the labels. They derive a sample complexity bound based on the probability of sampling such a narrow teacher. Building on this framework, we demonstrate how C-RASP Transformers, which define a large class of constructions, can yield sample complexity bounds. These results shed light on how constant-size constructions such as Dyck-1 and an bn are easily learned by Transformers. Our main contributions are as follows: (i) We extend the framework of Buzaglo et al. to Transformers and provide a constraint-counting argument showing how wide student networks can implement narrow teachers. (ii) To the best of our knowledge, our work is among the first to bridge expressivity and learnability by transforming a class of expressivity results into sample complexity results. Background: A Brief Introduction to C-RASP RASP is a programming language introduced by [8] characterizing the expressivity of Transformers. C-RASP [9] is a variant allowing compilation in future-masked soft-attention Transformers with no restrictions on the input length. C-RASP operations are either boolean (e.g., comparison or logical AND) or pertain to counting (e.g., counting the number of tokens up to position i). Algorithm 1 gives an example program for recognizing Dyck-1 [9, 1], the language of well-balanced parentheses with 1 parenthesis type. ∗
Corresponding author. Contact: [email protected]
Preprint.
2
Theoretical Contribution
Problem Setup We assume that N sequences of length at most T are sampled i.i.d. from some N ≤T distribution D s.t. S := {xn }N and V = {1, . . . , |V|} is a vocabn=1 ∼ D , where xn ∈ V ulary of discrete tokens. We also assume the existence of a teacher model h∗ : V ≤T → {±1}. The true risk of a predictor h : V ≤T → {±1} is LD := Px∼D (h(x) ̸= h∗ (x)) i.e. the probability of having an example for which h and the teacher disagree. The empirical risk of h is PN LS (h) := N1 n=1 I[h(xn ) ̸= h∗ (xn )]. We consider the hypothesis class of Transformer models, with T Fθ denoting a Transformer with parameters θ. We consider the usual Transformer definition with softmax attention. We use width to denote max(d, dk ). For more details, refer to Appendix A.3. We consider fixed precision models, which we make precise through the following: Definition 2.1 (Q-quantized Networks). Let Q ⊂ R be a finite set such that 0 ∈ Q and |Q| ≤ Q for some integer Q ∈ N. A neural network is Q-quantized if all its parameters are restricted to lie in Q. Learning Algorithm As in [4, 3], we assume a Guess and Check (G&C) learning procedure which operates in the following way: (i) Sample the weights for a predictor h uniformly at random (ii) Compute LS (h); if LS (h) = 0, stop. Note that the rate of success of this learning algorithm is closely tied to the volume of generalizing solutions in the loss landscape, thus connecting our approach to general learning (see Chiang et al. [4], Buzaglo et al. [3] for details). Definition 2.2. We say that a predictor h is teacher-equivalent (TE) w.r.t. a data distribution D, noted h ≡ h⋆ , if Px∼D (h(x) = h⋆ (x)) = 1. Our main theoretical result gives an upper bound on the sample complexity of learning a narrow teacher Transformer implementing an arbitrary C-RASP program: Theorem 2.1. Fix ε ∈ (0, 1) and δ ∈ (0, 51 ). Let P be a C-RASP program of depth n with m variables, and suppose there exists a depth-n, single–head teacher T Fθ⋆ of constant width 2m + c (for an absolute constant c) implementing P with Q–quantized parameters. Let T Fθ be any depthL ≥ n single-head student of width d ≥ 2m + c, also Q–quantized, and let PS be the posterior obtained by conditioning a uniform prior on zero training error on an i.i.d. sample S ∼ DN . For MC-RASP := (1 + 2n)(d − 2m − c) + n (2m + c)2 + 5(2m + c)d + 2(2m + c) + (L − n)(2m + c)(2d + 1), if
1 1 MC-RASP log Q + 3 log(2/δ) = O Ld log Q N ≥ ε ε
then PS∼DN , T Fθ ∼PS (LD (T Fθ ) < ε) ≥ 1 − δ. We illustrate the applicability of this theorem through the following example: Example 1 (Learning a C-RASP program for Dyck-1). Consider the C-RASP program in Algorithm 1. This program has n = 7 operations and m = 9 variables. Thus, a single-head student with L ≥ 7 layers and width d could learn this program with Ld N ≥O (1) ε samples. We note that this gives us a better bound than Occam’s razor-like arguments which would yield O(Ld2 ).
3
Conclusion and Future Work
In conclusion, we present a simple yet principled framework for deriving sample complexity bounds for Transformer models by leveraging existing results on expressivity. Given a candidate C-RASP program, our analysis characterizes its learnability by a larger model. To the best of our knowledge, this is the first work to study the learnability of C-RASP in Transformers through sample complexity. Looking forward, several extensions are possible. First, there has been no empirical validation, analogous to [4], of how loss landscape impacts length generalization in Transformers/State Space Models. Moreover, the bound on the probability of sampling a TE model could be tightened, since the current approach only accounts for a single encoding of the teacher within the student. 2
References [1] Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the Ability and Limitations of Transformers to Recognize Formal Languages. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7096–7116, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/v1/2020.emnlp-main.576. URL https://aclanthology.org/2020.emnlp-main.576/. [2] Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the representational capabilities of transformers and recurrent architectures. Advances in Neural Information Processing Systems, 37:36002–36045, 2024. [3] Gon Buzaglo, Itamar Harel, Mor Shpigel Nacson, Alon Brutzkus, Nathan Srebro, and Daniel Soudry. How uniform random weights induce non-uniform bias: Typical interpolating neural networks generalize with narrow teachers. arXiv preprint arXiv:2402.06323, 2024. [4] Ping-yeh Chiang, Renkun Ni, David Yu Miller, Arpit Bansal, Jonas Geiping, Micah Goldblum, and Tom Goldstein. Loss landscapes are all you need: Neural network generalization can be explained without the implicit bias of gradient descent. In The Eleventh International Conference on Learning Representations, 2022. [5] Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171, 2020. [6] William Merrill, Ashish Sabharwal, and Noah A Smith. Saturated transformers are constantdepth threshold circuits. Transactions of the Association for Computational Linguistics, 10: 843–856, 2022. [7] Michael Rizvi, Maude Lizaire, Clara Lacroce, and Guillaume Rabusseau. Simulating weighted automata over sequences and trees with transformers. arXiv preprint arXiv:2403.09728, 2024. [8] Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In International Conference on Machine Learning, pages 11080–11090. PMLR, 2021. [9] Andy Yang and David Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. arXiv preprint arXiv:2404.04393, 2024. [10] Andy Yang, Michaël Cadilhac, and David Chiang. Knee-deep in c-rasp: A transformer depth hierarchy. arXiv preprint arXiv:2506.16055, 2025.
A
Preliminaries
A.1
Notation
We denote with N, Z and R the set of natural, integers and real numbers, respectively. We use bold letters for vectors (e.g. v ∈ Rd1 ), bold uppercase letters for matrices (e.g. M ∈ Rd1 ×d2 ). All vectors considered are column vectors unless otherwise specified. We denote with I the identity matrix and 0 as the matrix full of zeros. The size of such matrices is typically made apparent by the context. The i-th row and the j-th column of a matrix M are denoted by Mi,: and M:,j . Let Σ be a fixed finite alphabet of symbols, Σ∗ the set of all finite strings (words) with symbols in Σ and Σn the set of all finite strings of length n. We use ε to denote the empty string. Given p, s ∈ Σ∗ , we denote with ps their concatenation. A.2
A More Detailed Introduction to C-RASP
In this section, we formally define C-RASP and give an overview of C-RASP operations. Definition A.1 (C-RASP). A C-RASP program P is defined as a sequence P1 , . . . , Pn of C-RASP operations. There are two types of operations: 3
Count-Valued Operations Boolean-Valued Operations
Counting
C(i) := #[j ≤ i] P (j)
Conditional
C(i) := P (i) ? C1 (i) : C2 (i)
Initial
P (i) := Qa (i) for a ∈ Σ
Boolean
P (i) := ¬P1 (i) P (i) := P1 (i) ∧ P2 (i)
Addition
C(i) := C1 (i) + C2 (i)
Subtraction
C(i) := C1 (i) − C2 (i)
Comparison
P (i) := C1 (i) ≤ C2 (i)
Min/Max
Constant
P (i) := 1
C(i) min(C1 (i), C2 (i)) C(i) max(C1 (i), C2 (i))
Constant
:= :=
C(i) := 1
Counting operations compute the number of positions j ≤ i where P (j) holds, returning their total. By convention, when using a C-RASP program to recognize languages, acceptance is determined by the value of the final operation (required to be Boolean) at the final position. Concretely, if the program runs on input w of length n and the last operation is D, then w is accepted if and only if D(n) evaluates to true. Algorithm 1 gives an example C-RASP program recognizing Dyck-1: Algorithm 1 C-RASP program recognizing Dyck-1 Require: A string of parentheses S. 1: Cl (i) := #[j ≤ i]Ql (j) 2: Cr (i) := #[j ≤ i]Qr (j) 3: V (i) := Cr (i) > Cl (i) 4: Cv (i) := #[j ≤ i]V (j) 5: M (i) := Cv (i) = 0 6: B(i) := Cr (i) = Cl (i) 7: D(i) := M (i) ∧ B(i)
▷ The number of ’(’ up to position i ▷ The number of ’)’ up to position i ▷ Violation: there are more ’)’ than ’(’ ▷ The number of Violations ▷ Matched: zero Violations ▷ Balanced: same number of ’(’ and ’)’ ▷ String is Matched and Balanced
C-RASP Program Size vs. Transformer Size Next, we give an overview of the equivalence results between the size of C-RASP programs and the size of the Transformer models implementing them. We begin with the relationship between model depth and program depth, shown by Theorem 3.1 of [10]: Theorem A.1 (simplified). A language L is defined by a C-RASP program of depth k if and only if it is recognized by a fixed-precision transformer of depth k. The original statement makes the equivalence with the underlying temporal logic class, which is itself stated in [10] to have equivalence of depth with C-RASP statements. The following is also true about the width of Transformers implementing C-RASP programs: Fact A.1. Let |P|Q represent the number of subformulas, or variables, of a C-RASP program P. A Transformer implementing P must have width 2|P|Q + O(1). This fact follows from the construction accompanying Definition 5.6 in [9]. Note, however, that this is an upper bound. Using other methods, e.g., nearly-orthogonal encoding, it may be possible to do better.
A.3
Transformer Architecture
In this section, we detail the architecture of the Transformer we consider for our theoretical results 4
Definition A.2 (L-Layer Transformer). Let X ∈ RT ×d be an input sequence of length T . Define multi-head self-attention with h heads and the MLP sublayer as: fattn (X) = Concat(H(1) , . . . , H(h) )WO + X, ! (i) (i) (XWQ )(XWK )⊤ (i) (i) √ H = softmax XWV , dk
(2) i = 1, . . . , h,
fmlp (Z) = ϕ(ZW1 + b1 )W2 + b2 + Z.
(3) (4)
(i) (i) (i) where WQ , WK , WV
∈ Rd×dk for each head i, WO ∈ Rhdk ×d projects the concatenated heads back to model dimension. We assume d = hdk . We assume a 2-layer MLP block with parameters W1 ∈ Rd×dff , W2 ∈ Rdff ×d , b1 ∈ Rdff , and b2 ∈ Rd . Here, ϕ is a nonlinearity. In this work, we will assume ReLU nonlinearities unless stated otherwise. This is in line both with many practical implementations of Transformers as well as with the implementation for C-RASP compiled Transformers [9]. The L-layer Transformer is defined recursively as: H(0) = X, (ℓ)
(5) (ℓ−1)
H = fmlp (fattn (H )), for ℓ = 1, . . . , L, (6) We will use T Fθ to denote a transformer model with parameters θ and use width to denote max(d, dk ). We assume that at each of the L layers, the number of heads as well as the dimensions of the parameters are the same. Let Θ denote the set of all parameters in the model. We denote the parameter count of an L-layer h-head transformer as M (Θ) =1 + d +
L X
h (3ddk ) + d(hdk ) + ddff + dff d + dff + d.
ℓ=1
For instance, for a 1-layer 1-head Transformer, we would have M (Θ) = 3ddk + 2ddff + dff + 2d + 1.
B
Theoretical Results
B.1
Previous Results
We start by recalling the main lemma from [3]. Lemma B.1 (G&C (i.e. Posterior Sampling) Generalization). Let ε ∈ (0, 1) and δ ∈ 0, 51 , and assume that p̃ < 12 . For any N larger than − log(p̃) + 3 log 2δ , ε we have that PS∼DN , h∼PS (LD (h) < ε) ≥ 1 − δ. This lemma will be used in conjunction with the following bounds on the probability of sampling a TE model in order to derive the main theorem in this work. B.2
Novel Results
In this section, we restate our main theoretical results and provide proofs for all theoretical statements. The following lemma provides a bound on the probability of sampling a narrow 1-layer Transformer within a larger student Transformer: Lemma B.2. Let T Fθ∗ be a “narrow” 1-layer, h∗ -head transformer teacher with dimensions d∗ , d∗k , d∗ff and Q-quantized parameters, and let T Fθ be any 1-layer Q-quantized wider network with d ≥ d∗ , dk ≥ d∗k , dff ≥ d∗ff , h ≥ h∗ . The teacher network can be embedded in the student with M = (d − d∗ ) + h∗ (d∗ d∗k + 2d∗ dk ) + h̃d∗ dk + dd∗ + dd∗ff + d∗ dff + d + dff (7) constraints. 5
Proof. The key idea of the proof, similar to that of [3], is to use the weight matrix from the first layer to zero-out the weight values that interfere with the teacher’s activations. This thus gives us activations a = [a∗ , ã], where a∗ are the activations of the teacher network and ã are the remaining activations from the student. We will use the same convention throughout, using the star to denote teacher parameters and tilde to denote the “left over” dimensions. We start by setting the embeddings. Embeddings. Let Σ be an alphabet with symbols σ ∈ Σ. Consider x(σ) to be the d-dimensional student embedding, we set x(σ) = [x∗ (σ)
0] ,
(8)
With a slight abuse of notation, we will typically refer to the embedding vector simply as x throughout as the nature of the symbol is not relevant to the key argument of the proof. This gives us d − d∗ constraints on the embeddings. Attention mechanism
For the first h∗ heads (those corresponding to the teacher), we set ∗ WQ 0 WQ = (21) (22) WQ WQ # " (12) ∗ WK WK WK = (21) (22) WK WK 0 WV∗ WV = (21) (22) WV WV
(9) (10) (11) (12)
Thus for some embedding vector x, the computation of the attention weights would give ∗ ∗⊤ WQ 0 [x∗ 0] 0 (21) (22) = q WQ WQ # " (12) ∗ ∗⊤ W W K K [x∗ 0] k̃⊤ , (21) (22) = k WK WK
(13) (14)
where k̃ is the result of the computation with the two rightmost matrices. Computing dot product attention, we obtain ∗⊤ k∗ = q∗⊤ k∗ (15) q 0 k̃ which is the attention computation of the student network. Since attention weights are scalars, we must zero out the remaining activations for either the keys or the queries. For the value matrix, we have ∗⊤ WV∗ 0 [x∗ 0] (16) 0 . (21) (22) = v WV WV Letting a represent the output of some attention head, we would have a = [a∗ 0] for the teacher heads. This gives us a total amount of constrained parameters h∗ (d∗ d∗k + 2d∗ dk ). For the h − h∗ remaining heads, we set no constraints on WQ and WK . We only set constraints on WV as follows: 0 0 WV = (17) (21) (22) . WV WV This gives us [x
∗
0 0] (21) WV
0 (22) = 0. WV
(18)
In essence the key idea is to zero out the outputs of the heads which do not contribute to the teacher computation. This gives us (h − h∗ )d∗ dk constraints, or letting h̃ = h − h∗ , h̃d∗ dk constraints. 6
Letting h denote the concatenation of the output of all heads, we would have h = [a∗1 0 . . . a∗h∗ 0 0] , (19) ∗ Where we take 0 to be the zero vector of the appropriate size given the context. The first h subvectors correspond to the outputs of the teacher heads. The last 0 subvector corresponds to the output of the unused student heads. For the projection layer, we set " # (12) (12) (12) (1) (1) ⊤ ∗ ∗ ∗ WO,1 WO,1 WO,2 WO,2 . . . WO,h WO,h∗ WO,h∗ +1 . . . WO,h ∗ O , W = (22) (22) (22) (2) (2) 0 WO,1 0 WO,2 . . . 0 WO,h∗ WO,h∗ +1 . . . WO,h (20) Projection layer
This gives us an output of the form [o∗ 0]. After applying the skip connections, we obtain [x∗ + o∗ 0], where the upper dimensions correspond exactly to the residual stream of the teacher. This sets h∗ dd∗k = dd∗ constraints on the output projection. MLP
Finally, for the MLP, we set " # (12) W1∗ W1 W1 = (22) 0 W1
(21)
as well as ∗ b b1 = 1 0
"
and
W2∗ = 0
W2
(12)
W2 (22) W2
# (22)
as well as ∗ b b2 = 2 0
(23)
Letting o⊤ = [o∗ , 0] be the output of the attention layer, we can verify this computation for the first layer. " # ∗ ∗ ∗ (12) ∗ o b1 W1 o + b∗1 W1∗ W1 + = (24) (22) 0 0 0 0 W1 As the nonlinearity in the MLP is applied position-wise, it does not affect the separation between teacher dimensions and unused student dimensions. A similar argument can be made for the second layer as well. Letting a represent the activations at the output of the MLP, we obtain after both layers and the skip connections [a∗ + o∗ 0], where the upper dimensions exactly correspond to the residual stream of the teacher. Thus, the final count of constrained parameters is M = (d − d∗ ) + h∗ (d∗ d∗k + 2d∗ dk ) + h̃d∗ dk + dd∗ + dd∗ff + d∗ dff + d + dff , which concludes the proof. Theorem B.1. Let T Fθ∗ be a “narrow” L∗ -layer, h∗ -head transformer teacher with dimensions d∗ , d∗k , d∗ff and Q-quantized parameters, and let T Fθ be any L-layer Q-quantized wider network with d ≥ d∗ , dk ≥ d∗k , dff ≥ d∗ff , h ≥ h∗ , L ≥ L∗ . The probability of randomly sampling a TE model satisfies p̃ ≥ Q−M , (25) where M = (d − d∗ ) + L∗ h∗ (d∗ d∗k + 2d∗ dk ) + h̃d∗ dk + dd∗ + dd∗ff + d∗ dff + d + dff + (L − L∗ ) hdk + dff + 1 d∗ . Proof. The construction proceeds in two parts. We first use the L∗ initial layers to implement the teacher network, via repeated application of Lemma B.2. We then use the remaining L − L∗ layers to preserve the teacher block in the top d∗ coordinates of the residual stream, allowing the bottom d − d∗ coordinates to take arbitrary “garbage” values r̃. Intuitively, the only requirement at the end of the computation is that the teacher activations be cleanly separated from the unused dimensions of the student; the bottom coordinates do not need to be preserved across these last layers. 7
Teacher layers
We proceed by induction over the first L∗ layers.
Base case. For ℓ = 1, the claim follows directly from Lemma B.2: the input embedding takes the form [x∗ , 0], and the layer output is [r∗(1) , 0]. Induction step. Assume that the input to attention layer ℓ + 1 is r(ℓ) = r∗(ℓ) 0 .
(26)
By Lemma B.2, if the input has the form [r∗(ℓ) , 0], then so does the output, giving us r(ℓ+1) = ∗ ∗ [r∗(ℓ+1) , 0]. After L∗ such layers, the residual stream is [r∗(L ) , 0], where r∗(L ) is the output of the teacher network. Weak identity layers The remaining L − L∗ layers need only preserve the top d∗ coordinates of the residual stream; the bottom d − d∗ coordinates are free to take arbitrary values. More precisely, we maintain the invariant r = [r∗
r̃] ,
(27)
where r∗ is the teacher’s output and r̃ is unconstrained. For the attention block, we leave WQ , WK , WV entirely free and set the first d∗ columns of WO to zero: WO = 0 W̃O , (28) where the left block has shape hdk × d∗ and the right block W̃O has shape hdk × (d − d∗ ) and is free. Letting h = Concat(H(1) , . . . , H(h) ), the attention output becomes hWO = 0 hW̃O , (29) so the top d∗ entries are identically zero regardless of h. After the skip connection, the residual stream is [r∗ r̃] + 0 hW̃O = r∗ r̃ + hW̃O , (30) preserving the teacher block. This fixes hdk d∗ parameters per layer. For the MLP block, we leave W1 , b1 entirely free and set the first d∗ columns of W2 and the first d∗ entries of b2 to zero: W2 = 0 W̃2 , b2 = 0 b̃2 , (31) where the left blocks have shapes dff × d∗ and d∗ respectively, and the right blocks are free. Letting z = ϕ(ZW1 + b1 ), the MLP output becomes zW2 + b2 = 0 zW̃2 + b̃2 , (32) again with the top d∗ entries identically zero. After the skip connection, the teacher block is preserved as before. This fixes (dff + 1)d∗ parameters per layer. Note that the bottom d − d∗ coordinates may accumulate arbitrary values across these layers; this does not affect the teacher block, as the zeroing argument above does not depend on the contents of the input. The total number of constraints per weak identity layer is therefore (hdk + dff + 1)d∗ . Total constraint count Combining the embedding constraints, the L∗ teacher layers (Lemma B.2), and the L − L∗ weak identity layers, we obtain M = (d − d∗ ) + L∗ h∗ (d∗ d∗k + 2d∗ dk ) + h̃d∗ dk + dd∗ + dd∗ff + d∗ dff + d + dff + (L − L∗ ) hdk + dff + 1 d∗ . 8
Computation of the bound Let E be the event corresponding to sampling parameters of the Llayer h-head Transformer described above. We directly have that P(E) ≤ P(T Fθ∗ ≡ T Fθ ). Assuming a uniform prior P over parameters, we get p̃ ≥ P(E) = Q−M , concluding the proof. Combining Theorem B.1 with Lemma B.1 immediately yields a sample complexity bound for embedding a narrow teacher into any wider and deeper student. Corollary B.1 (General sample complexity). Fix ε ∈ (0, 1) and δ ∈ (0, 15 ). Let T Fθ∗ be a narrow L∗ -layer, h∗ -head teacher with dimensions d∗ , d∗k , d∗ff and Q-quantized parameters, and let T Fθ be any L-layer, h-head student with dimensions d ≥ d∗ , dk ≥ d∗k , dff ≥ d∗ff , h ≥ h∗ , L ≥ L∗ and Q-quantized parameters. Let PS be the posterior obtained by conditioning a uniform prior on zero training error on an i.i.d. sample S ∼ DN . If 1 N ≥ M log Q + 3 log(2/δ) , ε with M as defined in Theorem B.1, then PS∼DN , T Fθ ∼PS (LD (T Fθ ) < ε) ≥ 1 − δ. Proof. By Theorem B.1, p̃ ≥ Q−M , so − log p̃ ≤ M log Q. Substituting into Lemma B.1 yields the stated sample complexity. Next, we relate this bound to the size of a Transformer implementing an arbitrary C-RASP program. Corollary B.2. Let P be a C-RASP program of depth n with m subformulas, and consider a singlehead student (h = 1) of depth L ≥ n with dk = dff = d, together with a single-head teacher with d∗k = d∗ff = d∗ . The probability of sampling a Transformer T Fθ∗ implementing P is bounded by p̃ ≥ Q−MC-RASP
(33)
with MC-RASP := (1 + 2n)(d − 2m − c) + n (2m + c)2 + 5(2m + c)d + 2(2m + c) + (L − n)(2m + c)(2d + 1), where c is an absolute constant. Proof. The proof for this statement directly follows from the analysis of the size required to implement a C-RASP program P given in Section A.2. One can easily show this fact by simplifying the value of M given in Theorem B.1. We let h∗ = h = 1, which is in line with [9], as the constructions they provide for C-RASP operations typically use only one attention head; this also keeps the simplification dk = d consistent with the standard convention d = hdk used in Section A.3. We obtain the main theorem for this work by combining Corollary B.2 and Lemma B.1: Theorem B.2. Fix ε ∈ (0, 1) and δ ∈ (0, 15 ). Let P be a C-RASP program of depth n with m variables, and suppose there exists a depth-n, single–head teacher T Fθ⋆ of width 2m + c (for an absolute constant c) implementing P with Q–quantized parameters. Let T Fθ be any depth-L ≥ n single-head student of width d ≥ 2m + c, also Q–quantized, and let PS be the posterior obtained by conditioning a uniform prior on zero training error on an i.i.d. sample S ∼ DN . For MC-RASP := (1 + 2n)(d − 2m − c) + n (2m + c)2 + 5(2m + c)d + 2(2m + c) + (L − n)(2m + c)(2d + 1), if N ≥
1 1 MC-RASP log Q + 3 log(2/δ) = O Ld log Q ε ε
then PS∼DN , T Fθ ∼PS (LD (T Fθ ) < ε) ≥ 1 − δ.
9