Length Generalization Bounds for Transformers

Length generalization is a key property of a learning algorithm that enables it to make correct predictions on inputs of any length, given finite training data. To provide such a guarantee, one needs to be able to compute a length generalization bound, beyond which the model is guaranteed to generalize. This paper concerns the open problem of the computability of such generalization bounds for $\mathsf{C}$-$\mathsf{RASP}$, a class of languages which is closely linked to transformers. A positive partial result was recently shown by Chen et al. for $\mathsf{C}$-$\mathsf{RASP}$ with only one layer and, under some restrictions, also with two layers. We provide complete answers to the above open problem. Our main result is the non-existence of computable length generalization bounds for $\mathsf{C}$-$\mathsf{RASP}$ (already with two layers) and hence for transformers. To complement this, we provide a computable bound for the positive fragment of $\mathsf{C}$-$\mathsf{RASP}$, which we show equivalent to fixed-precision transformers. For both positive $\mathsf{C}$-$\mathsf{RASP}$ and fixed-precision transformers, we show that the length complexity is exponential, and prove optimality of the bounds.

We prove bounds on how long the strings in the training data need to be in order for a transformer to generalize to arbitrary lengths. We show that for transformers in general, such a bound is not computable (no learning algorithm can guarantee generalization to arbitrary lengths). For finite-precision transformers, we find that training on strings of exponential length is needed to length generalize.