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

Jul 16, 2026

Upload by Ophelia

The document presents theoretical progress on understanding Transformers by connecting expressivity with learnability. It derives preliminary sample complexity bounds for learning C-RASP constructions using Transformers, inspired by loss-landscape analyses of “narrow teacher” models under a PAC learning framework. Building on a guess-and-check learning view, it shows how C-RASP Transformers can yield bounds, clarifying why constant-size constructions such as Dyck-1 and specific counting languages are learnable.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages9

Reading Time23 min

Abstract

Introduction

Background: A Brief Introduction to C-RASP

Theoretical Contribution

Problem Setup

Learning Algorithm

Teacher-Equivalence and Main Result

arXiv :2607 . 1 1760v 1 [ cs .LG] 13 Jul 2026 From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP Michael Rizvi-Martel 1 ∗ Satwik Bhattamishra2 Guillaume Rabusseau 1 Michael Hahn4 1Mila & Universit de Montral 2University of Oxford 4 Saarland University 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: [michael.rizvi-martel@mila.quebec](michael.rizvi-martel@mila.quebec) [Preprint.](Preprint.) 2 Theoretical Contribution Problem Setup We assume that N sequences of length at most T are sampled i.i.d. from some distribution D s.t. S := {xn }Nn=1 ∼ DN , where xn ∈ V ≤T and V = {1, ... , |V|} is a vocabulary 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

FAQs

What is the central goal of the work on C-RASP and Transformers?

To connect Transformer expressivity results to learnability by deriving sample complexity bounds for learning C-RASP constructions with Transformers.

What framework is used to motivate narrow teacher learnability?

A PAC-learning perspective where generalization is explained by the presence of a consistent “narrow teacher” network, and sample complexity is tied to the probability of sampling such solutions.

How do the results explain learning of constant-size constructions like Dyck-1?

They show that C-RASP Transformers can provide sample complexity guarantees, implying that constant-size constructions such as Dyck-1 and certain counting languages are easily learned.

Jul 16, 2026

Upload by Ophelia