Algebraic Decomposition Theory for Transformer Length Generalization

TL;DR - This paper gives the first complete characterization of regular languages on which transformers can generalize beyond their training sequence lengths. It also provides a polynomial-time decision algorithm based on a new algebraic decomposition theory.

• Characterizes transformer length generalization through the C-RASP formalism.
• Extends classical finite-semigroup decomposition theory using iterated wreath products of the additive integer group.
• Decides regular-language membership in polynomial time relative to the syntactic monoid’s size.
• Experiments show the theory predicts transformer length-generalization behavior better than existing classifications.