Abstract
Large language models exhibit surprising emergent generalization properties,yet also struggle on many simple reasoning tasks such as arithmetic and parity.This raises the question of if and when Transformer models can learn the truealgorithm for solving a task. We study the scope of Transformers' abilities inthe specific setting of length generalization on algorithmic tasks. Here, wepropose a unifying framework to understand when and how Transformers canexhibit strong length generalization on a given task. Specifically, we leverageRASP (Weiss et al., 2021) -- a programming language designed for thecomputational model of a Transformer -- and introduce the RASP-GeneralizationConjecture: Transformers tend to length generalize on a task if the task can besolved by a short RASP program which works for all input lengths. This simpleconjecture remarkably captures most known instances of length generalization onalgorithmic tasks. Moreover, we leverage our insights to drastically improvegeneralization performance on traditionally hard tasks (such as parity andaddition). On the theoretical side, we give a simple example where the"min-degree-interpolator" model of learning from Abbe et al. (2023) does notcorrectly predict Transformers' out-of-distribution behavior, but ourconjecture does. Overall, our work provides a novel perspective on themechanisms of compositional generalization and the algorithmic capabilities ofTransformers.