cs.LG · 2607.11760 Copy arXiv ID · Jul 13, 2026 Save From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP Authors: Michael Rizvi-Martel , Satwik Bhattamishra , Guillaume Rabusseau , Michael Hahn
Organizations: Mila & Universit´e de Montr´eal · University of Oxford · 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.
Explore similar work Sep 8, 2026 · Georg Zetzsche, Hongjian Jiang, Andy Yang +4 Transformer Architectures Generalization Bounds
Aug 13, 2026 · Phokion Kolaitis, Rik Sengupta Transformer Architectures Expressivity
Jun 8, 2026 · Chenxiao Yang, Nathan Srebro, Zhiyuan Li Transformer Architectures Sample Complexity
Sep 8, 2026 · cs.LG J/K move · Enter open · S save
Georg Zetzsche, Hongjian Jiang, Andy Yang, Pascal Bergsträßer +3
Max Planck Institute for Software Systems (MPI-SWS) · RPTU Kaiserslautern-Landau · University of Notre Dame
Recent advancements in transformer length generalization theory enable us to reliably predict when a transformer can learn to solve a task. In particular, the C-RASP hypothesis (a formalized version of the so-called RASP-l conjecture) posits that transformers length-generalize on a task if and only if a solution is expressible in the C-RASP language. While this hypothesis has strong empirical validation, theoretical problems arise from the fact that no computable length generalization bounds exist for C-RASP, alongside the discovery of seemingly contradictory experiments. To address these problems, we refine the C-RASP hypothesis utilizing the recently-proposed fragments C-RASP+ and C-RASP1. These fragments have computable length generalization bounds, though in the worst case requiring an extremely large (double exponential) sample size. It is an open question whether these sample size bounds are tight. In this paper, we resolve this open question by providing an exponentially tighter bound. In doing so, we show a polynomial length generalization bound for transformers if we adopt compressed strings, via a novel connection to power words. As an application, we show how this yields a fine-grained analysis of the C-RASP conjecture that resolves contradicting experimental evidence against it.