Length Generalization Bounds for Transformers

Andy Yang, Pascal Bergsträßer, Georg Zetzsche, David Chiang, Anthony Widjaja Lin
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:144227-144248, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-yang26c, title = {Length Generalization Bounds for Transformers}, author = {Yang, Andy and Bergstr\"{a}{\ss}er, Pascal and Zetzsche, Georg and Chiang, David and Lin, Anthony Widjaja}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {144227--144248}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/yang26c/yang26c.pdf}, url = {https://proceedings.mlr.press/v306/yang26c.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Length Generalization Bounds for Transformers %A Andy Yang %A Pascal Bergsträßer %A Georg Zetzsche %A David Chiang %A Anthony Widjaja Lin %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-yang26c %I PMLR %P 144227--144248 %U https://proceedings.mlr.press/v306/yang26c.html %V 306 %X 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.
APA
Yang, A., Bergsträßer, P., Zetzsche, G., Chiang, D. & Lin, A.W.. (2026). Length Generalization Bounds for Transformers. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:144227-144248 Available from https://proceedings.mlr.press/v306/yang26c.html.

Related Material