A polynomial length generalization bound for transformers if the authors adopt compressed strings, via a novel connection to power words is shown, which yields a fine-grained analysis of the C-RASP conjecture that resolves contradicting experimental evidence against it.
Abstract
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.
Though the construction provably evaluates Boolean expressions -- a universal symbolic computation -- of arbitrary length perfectly, in other experiments it is demonstrated that the transformer variant can learn and generalize perfectly on other common length generalization benchmarks, including modular arithmetic and...
Takuya Ito, Ruchir Puri, Murray Campbell et al.· 0 citations
This work studies whether one masked transformer can approximate causal token-to-token maps uniformly over sequences of arbitrary length sampling a fixed normalized horizon, and characterizes the causal families admitting uniform approximation on these compact input classes by a single transformer with length-independe...
Takashi Furuya, Maarten V. de Hoop, Gabriel Peyré· 0 citations
Research on transformer expressivity shows whether a transformer is capable of solving a given task, but gives little indication of whether the solution, if learned, is generalizable to longer input lengths. We study this question through normalized exact-solution volume (NESV): the fraction of a bounded parameter regi...
Recently, Large Language Models (LLMs) have been increasingly able to solve advanced mathematical problems, including many that have been open for decades. This opens the door to expansion of mathematical knowledge at unprecedented scale. Yet, while LLMs may be able to conjecture and prove more and more theorems, it re...
Niket Patel, Ahmad Rammal, Amaury Hayat et al.· arXiv.org· 0 citations
OEIS-derived benchmarks substantially measure memorisation, and MDL supplies a cheap, contamination-free difficulty signal they currently lack, according to an exactly computable reference learner.
It is shown that the state-of-the-art bound for preferent compressions is provably tight and an explicit construction based on the uniform distribution and order statistics that attains the bound in the limit is established.
Dario Paccagnan, Marius A. Tirlea· 0 citations
Related blog posts
MIT News · Artificial Intelligence· news.mit.eduNov 17, 2026
By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.
Microsoft Research Blog· microsoft.comNov 16, 2026
AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.
MIT News · Artificial Intelligence· news.mit.eduNov 13, 2026