Transformer Theory Moves From Can Represent to Can Learn

Expressivity was never the whole story

A lot of transformer theory has lived in a clean but limited world: prove that attention can represent some task, or prove that it cannot. That work matters. It gives us boundaries. It tells us that the architecture is not magic dust.

But representation is not training.

The same function can be expressible in a transformer and still be hard to find with gradient descent, data, initialization, noise, and all the other machinery of actual model building. That gap is where the new arXiv preprint, “From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP,” is pointing.

The authors frame the problem plainly. Prior work has often used handcrafted weights or computational complexity arguments to characterize tasks inside or outside the transformer hypothesis class. Their move is to ask a more operational question: if a transformer-compatible construction exists, how many samples might be needed to learn it?

That is a better question for builders.

Not because sample complexity bounds will tell OpenAI, Anthropic, Google, or Meta how many tokens to buy next week. They will not. These are preliminary theoretical bounds, not a procurement spreadsheet. But they move the conversation from “a transformer could do this” toward “training has a plausible path to this.”

That distinction matters more as models become systems. Agents, tool-use loops, code models, long-context workflows, memory layers, retrieval stacks. We keep asking whether the model can support some behavior. The next question should be whether the behavior is learnable under sane conditions, or whether we are depending on luck, scale, and benchmark overfitting.

C-RASP as a bridge, not a product manual

The authors use C-RASP constructions as the teacher side of the setup. RASP-style languages are useful because they let researchers describe transformer-like algorithms in a structured way. They are not production frameworks. Nobody is going to write their customer support agent in C-RASP.

The value is that these constructions make the target behavior crisp enough to analyze.

“Narrow teachers” is the phrase that stuck with me. The teacher is not a giant model distilling vibes into another giant model. It is a constrained construction that captures a behavior the student transformer is supposed to learn. That narrowness is the point. If the teacher is too broad, the theory gets foggy. If it is narrow enough, you can start asking about sample complexity without pretending you have solved all of deep learning.

This is where the work feels honest. The authors are not claiming a full theory of LLM training. They describe the bounds as preliminary. Good. The field needs more of that tone.

The important shift is methodological: stop treating expressivity proofs as if they settle practical capability. They settle one layer of the question. Learnability is another. Generalization is another. Distribution shift is another. Deployment reliability is another still.

For applied AI, those layers blur together. A model that passes a benchmark may still fail in a workflow because the learned behavior is brittle. A model that can execute a pattern in-context may still need too many examples, too specific a prompt, or too much scaffolding. Theory that separates these pieces is useful, even when it is not immediately actionable.

The practical lesson is about target behaviors

I would not read this preprint as a direct guide to training LLMs. Read it as pressure on a lazy habit: equating possible with learnable.

In product work, that habit shows up constantly. “The model can do multi-step reasoning.” Sometimes. “The model can use tools.” With the right harness. “The model can follow policy.” Until the context gets weird. The more precise version is always about the target behavior, the data regime, the training or prompting path, and the failure modes.

This is where theory papers like this can influence practice indirectly. They encourage narrower claims. Instead of “our agent can manage email,” ask which subroutines are actually learnable and testable: classify intent, extract commitments, detect ambiguity, draft a response, ask for clarification, refuse risky actions. Each one is a narrower teacher, even if you never formalize it that way.

The catch is that narrow tasks compose badly. A collection of learnable behaviors does not automatically become a reliable system. The glue matters. State matters. Evaluation matters. So does the distribution your users create after launch.

For a builder, the move is simple: pick one behavior your model “can” do, then define the smallest teacher for it. Build a dataset around that behavior. Measure how many examples, prompts, or traces it takes before performance stops being random. Then test the same behavior under mild distribution shift. The missed catch is that capability demos usually test expressivity. Products need learnability plus stability.