Non-Asymptotic Length Generalization
Open accessAbstract
Length generalization is the ability of a learning algorithm to learn a hypothesis which generalizes to longer inputs than the inputs in the training set. In this paper, we provide provable guarantees of length generalization for various classes of functions in an idealized setting. First, we formalize the framework of non-asymptotic length generalization, which requires a computable upper bound for the minimum input length that guarantees length generalization, as a function of the complexity of ground-truth function under some given complexity measure. We refer to this minimum input length to length generalize as length complexity. We show the Minimum-Complexity Interpolator learning algorithm achieves optimal length complexity. We further show that whether a function class admits non-asymptotic length generalization is equivalent to the decidability of its language equivalence problem, which implies that there is no computable upper bound for the length complexity of Context-Free Grammars. On the positive side, we show that the length complexity of Deterministic Finite Automata is $2n - 2$ where $n$ is the number of states of the ground-truth automaton. Our main results are upper bounds of length complexity for a subset of a transformer-related function class called C-RASP (Yang & Chiang, 2024). We show that the length complexity of 1-layer C-RASP functions is $O(T^2)$ when the ground-truth function has precision $T$, and that the length complexity of 2-layer C-RASP functions is $O(T^{O(K)})$ when the ground-truth function has precision $T$ and $K$ heads.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Non-asymptotic length generalization is equivalent to the decidability of the language equivalence problem for any finite class of languages.
“we use the fact that non-asymptotic length generalization is equivalent to the decidability of the language equivalence problem for any finite class of languages (Chen et al., 2025, Lemma 3.4,Theorem 3.2).”
From Length Generalization Bounds for Transformers (2026) · cites this paper as Chen et al., 2025, Lemma 3.4,Theorem 3.2
Section 4.2 (Lemma 4.5; page unavailable) states that decidability of language equivalence is equivalent to non-asymptotic length generalization for the full class represented by an encoding system, provided the complexity measure satisfies Assumption 3.7. It does not state this equivalence for any arbitrary finite class of languages; the cited lemma and theorem numbers also do not match those in our copy. (LLM, conf=0.87)
Experimental — accuracy not yet measuredChen et al. consider a restricted subset of programs, notated C-RASP 2,K,T.
“However, this is because they consider a restricted subset of programs, which they notate as C-RASP 2,K,T .”
From Length Generalization Bounds for Transformers (2026) · cites this paper as Chen et al. (2025)
The depth 1 C-RASP fragment studied by Chen et al. (2025) has quadratic length complexity.
“This accounts for why it is non-contradictory that the depth 1 C-RASP fragment they study has quadratic length complexity, while we show an exponential lower bound for C-RASP of depth 1.”
From Length Generalization Bounds for Transformers (2026) · cites this paper as Chen et al. (2025)
Chen et al. (2025) use the absolute size of the constants T as precision, while this paper uses the bit-precision p of the constants, which is exponentially smaller than the absolute size.
“As a final note, we observe that Chen et al. (2025) use the absolute size of the constants T as precision, while we use the bit-precision p of the constants (exponentially smaller than the absolute size).”
From Length Generalization Bounds for Transformers (2026) · cites this paper as Chen et al. (2025)
C-RASP_{2,K,T} has length complexity O(T^{O(K)}).
“While Chen et al. (2025) C-RASP 2,K,T has a length complexity of O(T O (K)), we show that C-RASP 2 has uncomputable length complexity.”
From Length Generalization Bounds for Transformers (2026) · cites this paper as Chen et al. (2025)
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
The citation lists haven’t been fetched yet
Research works printed but not linked: 24
- Abbe, E., Bengio, S., Lotfi, A., and Rizk, K. Generalization on the unseen, logic reasoning and degree curriculum, 2024. URL https://arxiv.org/abs/2301.13105. · arXiv
- Anil, C., Wu, Y., Andreassen, A., Lewkowycz, A., Misra, V., Ramasesh, V., Slone, A., Gur-Ari, G., Dyer, E., and Neyshabur, B. Exploring length generalization in large language models, 2022. URL https://arxiv.org/abs/2207.04901. · arXiv
- Baker, B. S. and Book, R. V. Reversal-bounded multipushdown machines, 1974. URL https://doi.org/10. 1016/S0022-0000(74)80027-9. · DOI
- Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners, 2020. URL https://arxiv.org/abs/2005.14165. · arXiv
- Delétang, G., Ruoss, A., Grau-Moya, J., Genewein, T., Wenliang, L. K., Catt, E., Cundy, C., Hutter, M., Legg, S., Veness, J., and Ortega, P. A. Neural networks and the chomsky hierarchy, 2023. URL https://arxiv.org/abs/2207.02098. · arXiv
- Gold, E. M. Language identification in the limit, 1967. URL https://www.sciencedirect.com/science/ article/pii/S0019995867911655.
- Huang, X., Yang, A., Bhattamishra, S., Sarrof, Y., Krebs, A., Zhou, H., Nakkiran, P., and Hahn, M. A formal framework for understanding length generalization in transformers, 2024. URL https://arxiv. org/abs/2410.02140.
- Jelassi, S., d'Ascoli, S., Domingo-Enrich, C., Wu, Y., Li, Y., and Charton, F. Length generalization in arithmetic transformers, 2023. URL https://arxiv.org/abs/2306.15400. · arXiv
- Li, M. and Vitányi, P. An introduction to kolmogorov complexity and its applications, 2008. URL https://link.springer.com/book/10.1007/978-0-387-49820-1. · DOI · Paper page
- Mahankali, A., Haochen, J. Z., Dong, K., Glasgow, M., and Ma, T. Beyond ntk with vanilla gradient descent: A mean-field analysis of neural networks with polynomial width, samples, and time, 2023. URL https://arxiv.org/abs/2306.16361. · arXiv
- Marsden, A., Dogariu, E., Agarwal, N., Chen, X., Suo, D., and Hazan, E. Provable length generalization in sequence prediction via spectral filtering, 2024. URL https://arxiv.org/abs/2411.01035. · arXiv
- Nogueira, R., Jiang, Z., and Lin, J. Investigating the limitations of transformers with simple arithmetic tasks, 2021. URL https://arxiv.org/abs/2102.13019. · arXiv
- Nye, M., Andreassen, A. J., Gur-Ari, G., Michalewski, H., Austin, J., Bieber, D., Dohan, D., Lewkowycz, A., Bosma, M., Luan, D., Sutton, C., and Odena, A. Show your work: Scratchpads for intermediate computation with language models, 2021. URL https://arxiv.org/abs/2112.00114. · arXiv
- Pitt, L. and Warmuth, M. K. The minimum consistent df a problem cannot be approximated within any polynomial, 1993. URL https://dl.acm.org/doi/pdf/10.1145/138027.138042. · DOI
- Rissanen, J. Modeling by shortest data description*. Autom., 14:465-471, 1978. URL https://api. semanticscholar.org/CorpusID:30140639.
- Ruoss, A., Delétang, G., Genewein, T., Grau-Moya, J., Csordás, R., Bennani, M., Legg, S., and Veness, J. Randomized positional encodings boost length generalization of transformers, 2023. URL https: //arxiv.org/abs/2305.16843.
- Shaw, P., Chang, M.-W., Pasupat, P., and Toutanova, K. Compositional generalization and natural language variation: Can a semantic parsing approach handle both?, 2021. URL https://arxiv.org/abs/2010. 12725.
- Shaw, P., Cohan, J., Eisenstein, J., Lee, K., Berant, J., and Toutanova, K. Alta: Compiler-based analysis of transformers, 2024. URL https://arxiv.org/abs/2410.18077. · arXiv
- Solomonoff, R. J. A formal theory of inductive inference. part i, 1964. URL https://www.sciencedirect. com/science/article/pii/S0019995867911655.
- Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need, 2017. URL https://arxiv.org/abs/1706.03762. · arXiv
- Weiss, G., Goldberg, Y., and Yahav, E. Thinking like transformers, 2021. URL https://arxiv.org/abs/ 2106.06981.
- Yang, A. and Chiang, D. Counting like transformers: Compiling temporal counting logic into softmax transformers, 2024. URL https://arxiv.org/abs/2404.04393. · arXiv
- Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J., Bengio, S., and Nakkiran, P. What algorithms can transformers learn? a study in length generalization, 2023. URL https://arxiv.org/abs/ 2310.16028.
- Zhou, Y., Alon, U., Chen, X., Wang, X., Agarwal, R., and Zhou, D. Transformers can achieve length generalization but not robustly, 2024. URL https://arxiv.org/abs/2402.09371. · arXiv
- Authors
- Chen, T., Ma, T., & Li, Z.
- Affiliations
- Stanford University (US)
- Toyota Technological Institute at Chicago (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2025
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2506.03085
- OpenAlex
- W4417095623
- Cited by
- 0
- References
- 0
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (2211780)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Keywords
- length generalization, context-free grammars, deterministic finite automata
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
