Algebraic Decomposition Theory for Transformer Length Generalization
The paper claims a complete test for which regular languages transformers can length-generalize on.
The authors tie that behavior to C-RASP, a formalism for languages transformers length-generalize on. They argue classical finite semigroup decomposition cannot see the key property, because C-RASP’s counting block falls outside that framework. Their replacement uses iterated wreath products of the integers and yields a polynomial-time decision algorithm over a language’s syntactic monoid. Experiments on regular-language benchmarks are reported as matching transformer length-generalization better than existing classifications. ArXiv · AI/CL/LG's note
The authors tie that behavior to C-RASP, a formalism for languages transformers length-generalize on. They argue classical finite semigroup decomposition cannot see the key property, because C-RASP’s counting block falls outside that framework. Their replacement uses iterated wreath products of the integers and yields a polynomial-time decision algorithm over a language’s syntactic monoid. Experiments on regular-language benchmarks are reported as matching transformer length-generalization better than existing classifications. ArXiv · AI/CL/LG's note
score 6