Transformers' ability to generalize to longer sequences depends on specific algebraic properties of the language being learned—properties that classical finite algebra misses but can be captured by extending decomposition theory to infinite groups.
This paper characterizes which regular languages transformers can generalize to longer sequences than they've seen during training. The authors develop new algebraic theory extending classical decomposition methods to handle transformers' unbounded counting abilities, providing a polynomial-time algorithm to predict length generalization on any regular language.