💬 NLP

From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP

This paper advances the theoretical understanding of Transformer learnability by proposing preliminary sample complexity bounds for learning C-RASP constructions, addressing the gap between existing expressivity analyses and the practical feasibility of learning such solutions.

Original authors: Michael Rizvi-Martel, Satwik Bhattamishra, Guillaume Rabusseau, Michael Hahn

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Michael Rizvi-Martel, Satwik Bhattamishra, Guillaume Rabusseau, Michael Hahn

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, super-smart robot brain called a Transformer. For a long time, scientists have been asking: "What kind of puzzles can this robot solve?" They found that if you hand-craft the robot's brain with very specific, tiny instructions (like a secret code called C-RASP), it can solve tricky logic games, like checking if parentheses are balanced or counting things in a sentence.

But here's the big mystery the paper tackles: Just because the robot can solve the puzzle with the right code, does that mean it can actually learn that code by studying examples? Or is it like finding a needle in a haystack?

The "Narrow Teacher" Secret

The authors suggest a clever way to answer this. They imagine a scenario where a tiny, super-efficient robot (a "Narrow Teacher") already knows the secret code to solve a puzzle perfectly. Now, imagine a much bigger, clumsier robot (the "Student") that is trying to learn from scratch.

The paper argues that if the Student is big enough, it can accidentally "stumble" into the exact same brain structure as the tiny Teacher. Think of it like this: If you have a massive, empty warehouse (the Student) and a tiny, perfect toy car (the Teacher), and you randomly fill the warehouse with millions of random toy parts, there's a chance that somewhere in that mess, the parts just happen to fit together to build that exact tiny car.

The paper proves that for these specific C-RASP puzzles, the "warehouse" (the Student) doesn't need to be infinitely huge to find the "toy car" (the Teacher). In fact, the math shows that the bigger the Student is compared to the Teacher, the easier it is to find that perfect solution just by random chance.

The "Guess and Check" Game

How does the learning happen? The authors describe a simple, almost silly method called "Guess and Check."

You randomly pick a set of weights (the robot's brain settings).
You test it on a few examples.
If it gets everything right, you stop! You found the solution.

The paper suggests that because there are so many ways to build a "good" solution inside a big network, you don't need to be a genius to find one; you just need to try enough random guesses. The more examples you have (the sample complexity), the more likely you are to hit the jackpot.

The Magic Numbers

The authors did the math to tell us exactly how many examples are needed to make this work. They found that if you want to be very sure (with a probability of at least $1 - \delta$ ) that your robot learns the puzzle with an error rate less than $\epsilon$ , you need a specific number of training examples, $N$ .

The formula they derived is roughly:
$N \ge \frac{1}{\epsilon} \left( MC\text{-}RASP \cdot \log Q + 3 \log(2/\delta) \right)$

Don't let the letters scare you! Here is what they mean in plain English:

$N$ : The number of practice examples you need.
$\epsilon$ : How close to perfect you want the robot to be (smaller is better).
$Q$ : How precise the robot's brain settings are (like how many decimal places it can use).
$MC\text{-}RASP$ : This is a big number that depends on how complicated the puzzle is (how many steps or variables, $n$ and $m$ ) and how big your Student robot is (width $d$ and depth $L$ ).

The paper shows that for simple puzzles like Dyck-1 (checking balanced parentheses), which has 7 steps and 9 variables, a student robot with at least 7 layers and a width of $d$ can learn it with roughly $O(\frac{Ld}{\epsilon})$ examples. This is actually better (fewer examples needed) than older theories that suggested you'd need $O(Ld^2)$ examples.

What This Doesn't Say

It's important to know what this paper doesn't claim. The authors are very careful to say they haven't actually run these experiments on real computers yet. They haven't shown a robot learning this in a lab. They have only done the mathematical proof to show that it should work in theory.

They also don't claim this works for every possible task a Transformer can do. They are specifically talking about tasks that can be written in the C-RASP language. If a task is too messy or doesn't fit this specific "counting and logic" style, this math might not apply.

The Bottom Line

So, what's the takeaway? The paper suggests that the reason Transformers are so good at learning is that they are so big and flexible that they can easily "hide" a perfect, tiny solution inside their massive brain. If you give them enough examples to practice on, they are likely to stumble upon that perfect solution just by guessing. It's a bit like finding a perfect snowflake in a blizzard: if the blizzard is big enough and you wait long enough, you'll eventually find one that fits your hand perfectly.

The authors propose this as a new way to understand why these models learn so well, moving beyond just asking "what can they do?" to asking "how hard is it to teach them to do it?" And the answer, according to their math, is: "Not as hard as we thought, as long as the student is big enough."

Technical Summary: From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP

Problem Statement
While theoretical research has extensively characterized the expressivity of Transformer models—specifically what tasks they can encode in their weights using frameworks like RASP and C-RASP—there is a significant gap in understanding the learnability of these capabilities. Existing work largely determines which tasks are within the hypothesis class of Transformers but leaves open the question of how such expressive solutions are acquired during training. This paper addresses the challenge of bridging the gap between expressivity results and sample complexity bounds, specifically investigating how Transformers learn to implement C-RASP constructions.

Methodology
The authors build upon recent loss landscape analysis, specifically the framework proposed by Buzaglo et al. [3] and Chiang et al. [4], which posits that generalization in deep learning is driven by the volume of "good" solutions in the loss landscape. The core methodology involves:

Teacher-Student Framework: The authors define a "narrow teacher" network ( $h^*$ ) that implements a specific C-RASP program perfectly. They then consider a "wide student" network ( $h$ ) with larger dimensions (width and depth) than the teacher.
Constraint Counting: The central technical contribution is a constraint-counting argument. The authors demonstrate that a wide student network can implement a narrow teacher by imposing specific constraints on its parameters to zero out "interfering" activations while preserving the teacher's logic in a subset of its dimensions.
Q-Quantized Assumption: The analysis assumes fixed-precision models where all parameters are restricted to a finite set $Q$ (Q-quantized). This allows for the calculation of the probability of randomly sampling a "teacher-equivalent" (TE) model from a uniform prior.
C-RASP Integration: The paper utilizes C-RASP (Counting-RASP), a variant of the RASP language capable of compiling temporal counting logic into softmax Transformers without input length restrictions. The authors map the structural complexity of a C-RASP program (depth $n$ , number of variables $m$ ) to the required dimensions of a Transformer to implement it.

Key Contributions
The paper makes two primary contributions:

Extension of the Buzaglo Framework to Transformers: The authors extend the "narrow teacher" framework to Transformer architectures. They provide a rigorous derivation showing how wide student networks can embed narrow teachers, calculating the exact number of parameter constraints ( $M$ ) required to ensure the student behaves identically to the teacher on the data distribution.
Bridging Expressivity and Learnability: This work is among the first to transform expressivity results (what Transformers can do) into sample complexity results (how many samples are needed to learn what they can do). By deriving bounds based on the probability of sampling a TE model, the authors establish that if a C-RASP program can be implemented by a narrow Transformer, a wider Transformer can learn it with a specific sample complexity.

Results
The main theoretical result (Theorem 2.1) provides an upper bound on the sample complexity $N$ required to learn a C-RASP program with high probability.

Sample Complexity Bound: For a C-RASP program of depth $n$ with $m$ variables, implemented by a single-head teacher of width $2m + c$ , a student Transformer of depth $L \ge n$ and width $d \ge 2m + c$ requires:
$N \ge O\left(\frac{1}{\varepsilon} L d \log Q\right)$
samples to achieve a true risk of less than $\varepsilon$ with probability $1-\delta$ .
Comparison to Occam's Razor: The authors note that this bound ($O(Ld)$) is tighter than bounds derived from Occam's razor-like arguments, which would typically yield $O(Ld^2)$ .
Example Application: The paper illustrates the theorem using the Dyck-1 language (balanced parentheses). For a program with $n=7$ operations and $m=9$ variables, the derived sample complexity is $O(Ld/\varepsilon)$ , demonstrating that constant-size constructions are theoretically learnable by Transformers.

Significance and Claims
The paper claims to provide a "simple yet principled framework" for deriving sample complexity bounds for Transformers by leveraging existing expressivity results. Its significance lies in:

Theoretical Advancement: It is the first work to study the learnability of C-RASP in Transformers through the lens of sample complexity, moving beyond static expressivity analysis.
Explanation of Learnability: The results shed light on why certain constant-size constructions (like Dyck-1 and $a^nb^n$ ) are easily learned by Transformers, attributing this to the existence of "narrow teachers" within the loss landscape that wide networks can randomly sample.
Modesty and Limitations: The authors explicitly state that the work is preliminary. They acknowledge a lack of empirical validation regarding how loss landscape volume impacts length generalization in Transformers or State Space Models. Furthermore, they note that the current probability bounds for sampling a TE model could potentially be tightened, as the current approach accounts for only a single encoding of the teacher within the student.

The paper concludes that while it establishes a theoretical pathway from expressivity to learnability, future work is needed to validate these landscape-based hypotheses empirically and to refine the probability bounds.