Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
To resolve theoretical roadblocks and empirical contradictions facing the C-RASP hypothesis of transformer length generalization, this work analyzes the expressivity and sample complexity of the C-RASP+ and C-RASP1 language fragments. By establishing a novel connection between string compression and formal power words, the authors prove an exponentially tighter, polynomial length generalization bound for transformers operating on compressed inputs. This fine-grained theoretical framework successfully reconciles previously unexplained experimental counterexamples, proving computable guarantees for when transformers can generalize to longer sequences.
Length generalization in transformers does not require double-exponential sample sizes: viewing inputs as compressed strings via power words slashes worst-case sample complexity down to polynomial.
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.