# Non-Asymptotic Length Generalization

arXiv: https://arxiv.org/abs/2506.03085 · HTML: https://mlsanity.com/paper/2506.03085/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2025.

## Built on by (most cited first, 7 of 7)

- [Softmax Transformers are Turing-Complete](https://mlsanity.com/paper/2511.20038/) (2025)
- [Quantitative Bounds for Length Generalization in Transformers](https://mlsanity.com/paper/2510.27015/) (2025)
- [Length Generalization Bounds for Transformers](https://mlsanity.com/paper/2603.02238/) (2026)
- [On the Ability of Transformers to Verify Plans](https://mlsanity.com/paper/2603.19954/) (2026)
- [Barriers to Universal Reasoning With Transformers (And How to Overcome Them)](https://mlsanity.com/paper/2604.25800/) (2026)
- [Hierarchical Domain Generalization](https://mlsanity.com/paper/2607.16528/) (2026)
- [Length Generalization for Transformers via Compression](https://mlsanity.com/paper/2609.08851/) (2026)

## Abstract (arXiv)

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(T2) when the ground-truth function has precision T, and that the length complexity of 2-layer C-RASP functions is O(TO(K)) when the ground-truth function has precision T and K heads.