Algebraic Decomposition Theory for Transformer Length Generalization
AuthorsAndy Yang, Blerta Veseli, Corentin Barloy, Michaël Cadilhac, Andreas Krebs, Charles Paperman, Howard Straubing, Michael Hahn
Resources
This paper develops a mathematical theory explaining exactly when transformers can recognize patterns longer than those seen during training.
Key results
Number of regular languages used to evaluate the C-RASP characterization.
GPT-2 training examples sampled for each language.
Longest string length used in the main length-generalization evaluation.
Evaluation reaches 10x the maximum training length of 50.
Number of integer wreath-product factors used to decompose the depth-1 Dyck language.
What the paper found
This paper gives the first complete characterization of when transformers can length-generalize on regular languages, focusing on state prediction rather than broad language-model behavior. Its central result identifies the relevant class as C-RASP, whose regular-language fragment is exactly the closure of bounded-depth Dyck languages under typed wreath products, written C-RASP ∩ REG = wpc(Dy). Unlike classical Krohn–Rhodes theory, which uses finite semigroups, the analysis introduces typed infinite monoids based on integer addition, derived categories, and bounded Dyck approximations; it then yields a membership algorithm running in polynomial time in the syntactic monoid size. For example, the depth-1 Dyck language decomposes into 3 wreath-product factors of the integers. Experiments train GPT-2 models on automaton-state tracking across 125 regular languages, using 10,000 training words with lengths up to 50, and test lengths up to 500, or 10x the maximum training length. Languages classified as C-RASP retain near-perfect accuracy far beyond training, while non-C-RASP languages typically collapse shortly after the training range, a separation that existing classifications fail to explain. The study deliberately does not evaluate ChatGPT or Claude, because it aims to isolate architectural length generalization from pretraining and prompting effects.
Original abstract
Transformer-based language models are known to sometimes generalize to sequences longer than seen during training, but we lack a precise characterization of which tasks admit length generalization. It is not even known which regular languages transformers length-generalize on -- and this is a foundational class of languages. Our contributions are to establish the first complete characterization of which regular languages transformers length-generalize on and provide a decision algorithm running in polynomial time in the size of the language's syntactic monoid. These results rely on an effective characterization of the regular languages in C-RASP, a recently-established formalism that expresses which languages transformers length-generalize on. This characterization is challenging because classical tools like Krohn-Rhodes decomposition theory for finite semigroups are insufficient for C-RASP. Firstly, the basic building blocks of Krohn-Rhodes theory -- flip-flop and simple groups -- are not expressible in C-RASP. Secondly, the basic building block of C-RASP (unbounded counting) is not expressible by the finite semigroups of Krohn-Rhodes theory. Thus, length generalization on regular languages is controlled by an algebraic property that is invisible to classical finite decomposition theory. We generalize classical decomposition theory from finite semigroups to the infinite additive group on the integers, allowing us to characterize C-RASP in terms of iterated wreath products of the integers and derive a provable polynomial-time decision algorithm for regular language membership. Experiments across a broad test suite of regular languages confirm that our theory captures transformers' length-generalization behavior more accurately than existing classifications.
Read the original paperMore in Transformers
Browse all 42 papers →Pretraining Latent Information Feedback Transformers with Teacher Supervision
Dor Tirosh, Ido Amos, Mor Geva
LIFT teaches Transformers to pass rich hidden-state information across steps, potentially making language models more efficient and capable than standard feed-forward designs.
The Geometry of Inference in Transformer Residual Streams
Timur Mudarisov, Mikhail Burtsev, Radu State
This paper shows how Transformer hidden states gradually geometrically converge toward the correct prediction while eliminating competing possible outcomes.
Transformers Stop Thinking Too Early, and a Tiny LoRA Fixes It
Zehao Jin, Ruixuan Deng, Junran Wang
A small LoRA update appears to make transformers carry information through many more layers, dramatically extending their ability to follow long chains without retraining the full model.