Length Generalization for Transformers via Compression

Recent advancements in the length generalization theory have provided us with the ability to reliably predict learnability by transformers. 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, as well as the discovery of seemingly contradictory empirical results. To address this, we refine the C-RASP hypothesis utilizing the recently-proposed fragments of the language, CRASP+ and CRASP1. These fragment have computable length generalization bounds, though in the worst case requiring an extremely large (double exponential) sample size. It is an open question whether this 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 C-RASP conjecture that resolves contradicting experimental evidence against it.