From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 7 of its 9 references that are in the map. First posted on arXiv 13 Jul 2026.
Builds on
7 of 9 references.
References · 7
- 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
- 2021Thinking Like Transformerscited by 184
- 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
- 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
- 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
- 2024How Uniform Random Weights Induce Non-uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teacherscited by 18
- 2024Simulating Weighted Automata over Sequences and Trees with Transformerscited by 4
Built on by
Not cited yet.