Algebraic Decomposition Theory for Transformer Length Generalization
Andy Yang, Blerta Veseli, Corentin Barloy, Michaël Cadilhac, Andreas Krebs, Charles Paperman, Howard Straubing, Michael Hahn
cs.FL, cs.AI
2026-08-14
Poly-time check decides which regular languages sit in C-RASP via typed Z wreath products. On 125 languages, GPT-2 stays near-perfect to 10x train length inside, collapses outside.
Transformers sometimes handle strings longer than anything seen in training. Even for regular languages, the simplest infinite class with a complete algebraic theory, nobody had a decision procedure for when that happens. C-RASP, a counting-restricted programming language from Huang et al. 2025, tracks the empirical pattern: transformers length-generalize on languages inside it and fail outside. What was missing is a check. Given a regular language, is it in C-RASP or not.
The opening pair makes the gap concrete. (ab+bbaa) and (ab+aabb) have near-identical DFAs. Train both up to length 50, test to 150. One extrapolates, the other does not. Star-free, R-trivial, and solvable-group classifications all treat them as similar, and all fail to predict the split.
Krohn-Rhodes decomposition builds every finite monoid from flip-flops (U2) and simple groups. Both sides of that toolkit miss C-RASP. C-RASP cannot express U2. Its own primitive is unbounded counting, the additive group of integers, which no finite semigroup can express. Length generalization on regular languages is controlled by an algebraic property that finite decomposition theory cannot see.
The paper extends wreath-product decomposition from finite semigroups to Z. The classical wreath product is too strong: Z wr Z can recognize essentially every language. Typed monoids fix this by attaching a finite Boolean algebra of allowed accepting sets. Under that restriction, a language is in C-RASP exactly when its syntactic monoid sits in the typed wreath-product closure of Z. On the regular side, that class equals the wreath-product closure of bounded-depth Dyck languages.
The decision procedure divides by Z. Tilson's derived category extracts the kernel of a relational morphism. The algorithm walks R-classes from left to right, at each step searching for a bounded, linearly independent relational morphism into Z. Success builds an explicit division into an iterated wreath product of Z. Failure proves no shorter such product exists. Runtime is polynomial in the size of the monoid.
A cheaper necessary condition is the profinite equation (xy^ω)^ω x = (xy^ω)^ω: the monoid is aperiodic and every R-class has at most one idempotent. That condition is not sufficient. The containments R ⊂ C-RASP ∩ REG ⊂ R^ω ⊂ A ⊂ REG are all strict.
The test suite has 125 regular languages, some from prior work, some sampled from a PCFG tuned for class diversity. The task is state prediction: read a prefix, emit the DFA state. GPT-2 models train on 10,000 strings per language, lengths from the shortest legal word to 50, and test on nine bins up to [451, 500] with 1,000 strings each. Positional embeddings are zeroed out (NoPE). Separator tokens sit between symbols so the model cannot cheat by reading the last character off the residual stream.
A run counts as successful length generalization only if in-distribution accuracy hits 100% and stays near that level past 2× the max training length. Up to 1,000 random seeds per language, stopping at five in-distribution-perfect runs. Languages inside C-RASP stay near ceiling far past the training cutoff. Languages outside collapse shortly after. Scaling the training set to 100,000 strings does not change the split. A second suite of 50 deeper-nested languages, trained up to length 200, repeats the same pattern.
Li and Cotterell 2025 reported a bleaker picture, but they only tested three languages in C-RASP minus R, from N to 12N. Here, languages in that same slice still extrapolate from N to 10N. C-RASP membership separates length-generalizing languages more cleanly than R-triviality or R∘G.
For any finite-state tracking job such as bounded-depth bracket matching, restricted JSON, or a workflow automaton, there is now a runnable test: compute the syntactic monoid and ask whether it divides an iterated wreath product of Z. This is not another expressivity paper. Constant-depth poly-precision transformers already sit in TC0 and can express the solvable regular languages. Length generalization cuts a strictly smaller class.
On the engineering side this is a hard boundary. Extra layers and extra data do not rescue languages outside the class. Absolute positional encodings are still out of scope. The APE analogue is C-RASP[periodic, local]; the algebraic decision procedure for that variant is future work.
Every experiment uses small GPT-2 models with positional embeddings stripped. That is not a RoPE-pretrained LLM. The task is synthetic state prediction, and the setup deliberately blocks last-token residual shortcuts that real decoding would have. Main figures report the best successful seed; the appendix averages five successful seeds, and the out-of-class collapse remains, but within-class variance is only in plots. R^ω minus C-RASP has few samples, so the cheap equation is not a useful empirical filter. The theory covers regular languages only. Context-free matching and natural language sit outside it.