知识卡片：从表达性到样本复杂度：通过 C-RASP 为 Transformer 提供窄教师

英文标题：From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP
英文关键词：Transformers, expressivity, sample complexity, C-RASP, learnability

一句话结论

本文通过引入 C-RASP 构造，首次为 Transformer 模型的学习能力（learnability）提供了初步的样本复杂度（sample complexity）界限，将理论分析从表达性（expressivity）推进到可学习性。

事件概述或研究问题

大量已有理论工作通过设计人工权重或计算复杂性论证，刻画了哪些任务在 Transformer 的假设类中、哪些不在，但这些分析局限于模型的表达性，极少研究这些最优解是否可被学习（即从数据中高效获得）。本文致力于弥合这一差距，探索学习 Transformer 构造所需的样本量。

方法/产品要点

受近期损失景观（loss landscape）分析工作的启发，本文提出针对 C-RASP 构造的样本复杂度界限。
C-RASP 是一种用于描述 Transformer 行为的形式语言或构造方法（具体定义待核实），本文假定存在一个“窄教师”（narrow teacher）——即能够输出正确标签的 C-RASP 程序，然后分析从该教师的标注样本中学习所需的最少样本数。

主要结果或产业意义

给出了学习特定 C-RASP 构造的初步样本复杂度上界（具体数值待核实）。
该结果为理解 Transformer 在何种条件下能够从有限数据中泛化到未见任务提供了理论基础，对设计更高效的语言模型预训练策略具有潜在指导意义。

为什么重要

既有工作多关注 Transformer 能做什么（表达性），而本文首次系统探究它如何学会做（可学习性），填补了理论空白。
样本复杂度界限是连接理论与实践的桥梁：若能证明某些复杂任务只需多项式样本即可学习，则有助于解释深度学习的实际成功；反之则提示需要更多样本或新的架构。
与已有相关卡片（如测试时迭代优化框架、BioASQ 问答流水线、STRACE 智能体优化）均无重复，本卡片为 Transformer 理论研究的新方向。

局限与不确定性

本文仅提供初步界限，尚未给出紧界（tight bound）或实验验证（待核实）。
C-RASP 构造的具体定义和适用范围需查阅原始论文或后续工作确认。
样本复杂度分析基于特定教师模型，对实际训练中无教师（纯自监督）场景的适用性需进一步探讨。
论文尚未提供可复现的代码或详细推导（待核实）。

可用于图书/PPT/简报的角度

作为“Transformer 理论前沿”章节的案例，说明从表达性到可学习性的研究演进。
在讨论大语言模型为什么需要大量数据时，引用本文对样本复杂度的分析作为理论支撑。
制作信息图：展示表达性（已解决）与学习性（待突破）的对比，并用 C-RASP 作为关键概念连接两者。

原始材料

标题：From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP
arXiv ID：2607.11760v1
作者：Michael Rizvi-Martel, Satwik Bhattamishra, Guillaume Rabusseau, Michael Hahn
发布/更新日期：2026-07-13
摘要原文：

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.

PDF 链接：https://arxiv.org/pdf/2607.11760v1
摘要页面：https://arxiv.org/abs/2607.11760v1