Algebraic Decomposition Theory for Transformer Length Generalization

TL;DR. Transformers sometimes generalize to sequences far longer than anything they were trained on, and sometimes fall off a cliff right past the training length — even on regular languages, the simplest possible state-tracking tasks. This paper gives the first complete answer for regular languages: a transformer length-generalizes on a regular language exactly when its automaton's state can be reconstructed by a cascade of loop-balanced integer counters, and this is decidable in polynomial time. Getting there required building a new algebraic decomposition theory, because the classical one (Krohn–Rhodes) is provably blind to the property that matters. The empirical validation across 175 languages is the cleanest separation I've seen in this literature.

The puzzle

Take two regular languages: (ab+bbaa)^* and (ab+aabb)^*. Their DFAs are nearly identical in size and shape. Train a small transformer to track the automaton state on strings of length up to 50, then test on strings up to length 150. On the first language, accuracy stays near-perfect. On the second, it collapses immediately past the training range. Nothing in the existing theory of transformer expressivity — \mathsf{TC}^0 bounds, star-free characterizations, \mathcal{R}-trivial characterizations — explains this difference. Expressivity results tell you what a transformer could represent at a fixed length; length generalization is evidence the model learned the actual algorithm, and that turns out to be governed by something else entirely.

Prior work (Huang et al. 2025, and follow-ups) converged on a strong empirical and partial theoretical claim: transformers length-generalize on precisely the languages expressible in C-RASP, a counting-based programming language that captures what fixed-precision transformers compute stably at any length. Provable length generalization holds for everything in C-RASP; failures outside it are consistent empirically. The problem: nobody knew which regular languages are in C-RASP. There was no membership test, so the theory couldn't actually be used as a predictor, and couldn't even be systematically tested. This paper supplies the characterization and the algorithm.

What C-RASP is, in one picture

A C-RASP program is a stack of layers. Each layer computes, at every position, Boolean features of the form: take a weighted sum of prefix counts of features from earlier layers, and compare against a threshold — \sum_m \lambda_m \cdot \#[\phi_m] \geq C. Counting is the only way to aggregate over the sequence. This matches what an attention layer does robustly at any length: uniform attention computes averages, which (with the position count) gives you counts; thresholds come from the MLP. Yang et al. (2025) showed a form of fixed-precision transformer is exactly equivalent to C-RASP.

Why the classical toolbox is useless here

Sixty years of algebra says finite state tracking decomposes via the Krohn–Rhodes theorem: every finite automaton is a cascade (wreath product) of two primitives — the flip-flop (a one-bit memory: "which of a, b came last?") and finite simple groups (e.g., parity). The bombshell in this paper's framing is that both primitives fall outside what transformers length-generalize on: the flip-flop is not in C-RASP (counts can tell you how many b's you've seen, never which symbol was most recent — this is why \Sigma^*b, tested with neutral symbols, defeats length generalization), and groups like parity (aa)^* aren't either. Meanwhile C-RASP's own primitive — the unbounded counter, the infinite monoid \mathbb{Z} — doesn't exist in the finite-semigroup world at all (MAJORITY isn't regular). Length generalization is controlled by an algebraic property that is literally invisible to classical decomposition theory. The authors rebuild the theory around \mathbb{Z}.

Taming infinity: typed monoids

There's an immediate landmine. The naive wreath product \mathbb{Z} \circ \mathbb{Z} — a counter whose increments depend on another counter — recognizes every language: let the outer counter add \sigma \cdot 2^{|x|} where |x| is the inner counter's position count, and you've encoded the entire string as one integer. Infinite-precision counters are a tape, not a counter.

The fix, adapted from Krebs's typed monoids: a counter's value is only observable through a finite Boolean algebra of types — threshold sets like [1,\infty) — and any function of a counter in a cascade must factor through those types. That's exactly the C-RASP restriction: you can only branch on threshold tests. With this in place, the paper proves the exact correspondence (Theorem 11):

where M(L) is the syntactic monoid of L (the canonical algebraic fingerprint of a regular language) and \mathrm{wpc}(\mathbb{Z}) is the closure under iterated typed wreath products of the integers. Transformers' state-tracking primitive is the threshold-observed counter, full stop.

The aha: balanced counters on strongly connected components

The abstract theorem becomes concrete in the automaton view (Appendix J), which is where I'd start reading. Ask: when can a cascade of counters reconstruct a DFA's state?

Within a strongly connected component (SCC) of the DFA, assign an integer weight to each symbol (more generally, to each event definable by earlier counters). Call the assignment balanced if every loop in the SCC sums to zero. Balance is exactly what makes a counter usable: the counter's value then depends only on the current state, not on the path — one fixed integer per state, forever, at any string length. If the balanced counters (iterated: counters counting threshold-events of previous counters) separate every pair of states in every SCC, the language is in C-RASP.

And if not? Any unbalanced counter has a loop with nonzero sum. Pump that loop and the counter's value runs off to \pm\infty, saturating every finite threshold — on long enough strings the counter carries no information at all. The completeness proof formalizes this: replace unbounded terms by their limit \pm\infty, and two states the balanced counters couldn't separate become provably indistinguishable to any C-RASP program. That is the algebraic shape of a length-generalization failure.

This finally explains the opening puzzle. Both languages are aperiodic, but the syntactic monoid of (ab+aabb)^* has two idempotents inside one \mathcal{R}-class — a structural signature that no counter cascade can separate its states — while (ab+bbaa)^* passes. The paper distills a cheap necessary test out of this (a profinite equation, (xy^\omega)^\omega x = (xy^\omega)^\omega, equivalent to "aperiodic and at most one idempotent per \mathcal{R}-class"), though it's provably not sufficient: (ab+bba)^* satisfies the equation yet is not in C-RASP.

From criterion to algorithm

The full decision procedure works on the syntactic monoid directly. The idea: check if M(L) divides an iterated wreath product of \mathbb{Z} by repeatedly "dividing out" one \mathbb{Z} factor. Monoids lack inverses, so there's no clean quotient; the right tool is Tilson's derived category, which records exactly the information a homomorphism loses. The algorithm walks the \mathcal{R}-classes of M(L) in order, at each step searching for a counter-valued relational morphism that separates more structure. Two things make this decidable where such problems are often not (division problems can be undecidable even for finite targets): the usable morphisms form a finitely generated \mathbb{Z}-module, so each productive step adds a linearly independent generator and the loop must terminate; and the completeness argument shows that if the search stalls, no decomposition of any depth exists. Total cost: polynomial in |M(L)| (Theorem 15). As a byproduct, Theorem 14 nails the landscape: \text{C-RASP} \cap \mathbf{REG} = \mathrm{wpc}(\mathbf{Dy}) — the wreath closure of bounded-depth Dyck monoids — sitting strictly between known classes:

Does the theory match real transformers?

The selection question for this paper is whether C-RASP is a tight predictor or a tidy approximation. The experiments are unusually broad: 125 regular languages (Table 1) sampled to populate every ring of the hierarchy — possible for the first time, since membership is now decidable — plus 50 more complex, deeper-nesting ones (Table 2). Task: predict the DFA state after every prefix. Models: GPT-2, no positional encodings (NoPE), separator tokens between symbols so the model can't shortcut via the last input token, trained on 10K strings of length [l_{\min}, 50], evaluated in bins out to [451, 500] — a 10\times extrapolation.

The result (Figure 3 and Appendix B) is a near-binary split: every C-RASP language holds near-perfect accuracy across the full 10\times range; every non-C-RASP language collapses shortly after length 50 — including languages in \mathbf{R}^\omega \setminus \text{C-RASP}, i.e., ones the cheap necessary test admits but the full procedure rejects. The pattern survives 10\times more training data (100K), aggregation over the 5 best seeds, and the harder suite trained on lengths up to 200. It also resolves a live discrepancy: Li & Cotterell (2025) had concluded \mathbf{R} was the boundary, but they tested only 3 languages in the crucial region \text{C-RASP}\setminus\mathbf{R}; with a systematic sample, that region cleanly generalizes.

Caveats, and they matter. The protocol reports the best configuration from a sizable hyperparameter sweep and the best of up to 1,000 random initializations that hit 100% in-distribution accuracy — so this measures learnability under favorable selection, not typical training behavior (though the 5-seed averages look similar). The theory is for NoPE transformers; with absolute positional encodings the relevant class changes (C-RASP with periodic/local predicates) and no decision procedure exists yet — so this doesn't directly transfer to production LLMs. The "transformers fail outside C-RASP" direction remains empirical, not proven. And the separator-token design deliberately enforces neutral-symbol invariance; without it, some non-C-RASP languages (\Sigma^*b) are trivially solvable via the last token.

Why this matters

Three things change if this holds up. First, there is now an efficiently checkable predictor of whether a transformer will learn a genuinely length-invariant algorithm for a state-tracking task — useful for benchmark design, curriculum construction, and for reasoning about when constrained decoding or agentic state tracking will silently break on long contexts. Second, the conceptual reframing: the transformer's native state-tracking primitive is neither the flip-flop nor the group of automata theory but the threshold-observed counter, and its compositional theory had to be built from scratch — a genuine extension of Krohn–Rhodes-style decomposition to an infinite building block. Third, the negative results are sharp: no amount of data (they tried 10\times) rescues languages outside the class; the failure is structural, which strengthens the case for recurrence or chain-of-thought on tasks whose automata contain unbalanced loops.

If you read two things: the worked decomposition of Dyck-1 in Section 4.2 (the "divide by \mathbb{Z}" mechanics, with pictures), and Appendix J, where the whole theory collapses into the balanced-counter criterion on DFAs — the version you could reimplement in an afternoon. The FAQ (Appendix A) is also unusually candid about scope, positional encodings, and the discrepancies with prior empirical work.