---
title: "From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2607.11760v1"
permalink: "https://feed.astralor.com/items/itm_8eb391d1d7892aba1bf2cca9"
published: "2026-07-13T16:22:36.000Z"
score: 67
channel: "ai"
tags: ["C-RASP","Transformer","Large Language Models","Loss Landscape","Sample Complexity","Expressivity"]
---

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

## AI commentary

> This paper is worth watching as it merges two theoretical threads—expressivity and sample complexity—for the first time, especially important for LLM theory researchers. Though preliminary, it provides a clear mathematical framework that could drive breakthroughs in deep learning theory.

## At a glance

This paper investigates the expressivity and sample complexity of Transformers through the C-RASP framework. The authors note that while extensive work has analyzed the expressivity of attention-based models, little research addresses the learnability of such solutions. Inspired by loss landscape analysis, they propose preliminary sample complexity bounds for learning C-RASP constructions. This provides theoretical insights into the capacities and limitations of large language models.

## Key points

- Proposes preliminary sample complexity bounds for learning Transformers under the C-RASP framework
- Bridges the gap between expressivity and learnability via loss landscape analysis
- Offers new theoretical tools for understanding the capacity limits of large language models

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_8eb391d1d7892aba1bf2cca9