Research map / Learning theory and algorithms / Kernels and regression theory
Non-Asymptotic Length Generalization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formalizes non-asymptotic length generalization, shows Minimum-Complexity Interpolator is optimal, links computable length bounds to decidability of language equivalence, and proves O(T^2) and O(T^{O(K)}) input-length bounds for 1- and 2-layer C-RASP.
Problem
When is length generalization possible, and how long must training inputs be (as a function of ground-truth complexity) for a learner to provably generalize to all lengths, rather than only asymptotically in the limit?
Approach
Defines non-asymptotic length generalization requiring a computable bound on the training input length as a function of ground-truth complexity; shows the Minimum-Complexity Interpolator is optimal for this quantity, and that computable bounds exist iff language equivalence is decidable, yielding concrete bounds for DFAs (2c-2), 1-layer C-RASP (O(T^2)) and 2-layer C-RASP (O(T^{O(K)})).
Key results
- DFAs with c states are identified by inputs of length at most 2c-2 under the MCI learner.
- Computable length-complexity bounds exist if and only if the language equivalence problem is decidable; hence CFGs (linear CFGs) admit only length generalization in the limit.
- 1-layer C-RASP functions with precision T are learned from inputs of length O(T^2); 2-layer C-RASP with K heads and precision T needs O(T^{O(K)}) length.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Minimum-Complexity Interpolator instead of an arbitrary learning algorithm | Function classes with encoding system R and complexity measure C · Functions of complexity at most c | length complexity: N^{R}_{mci}(c) = min_A N^{R}_A(c) = N(F^R_c) | Helped |
| Use the number of states as the DFA complexity measure | Minimum-Complexity Interpolator · DFA | maximum training input length sufficient for length generalization: N^{R_DFA}_A(c) ≤ 2c - 2 | Helped |
| Use CFG description length as the complexity measure | Any learning algorithm · Linear CFGs and CFGs | computable bound on length complexity: not computably bounded | Hurt |
| Restrict the function class to 1-layer C-RASP with parameter precision T | Minimum-Complexity Interpolator · C-RASP^1 | maximum training input length sufficient for length generalization: O(T^2) | Helped |
| Allow 2-layer C-RASP functions with up to K heads and precision T | Minimum-Complexity Interpolator · C-RASP^2 | maximum training input length sufficient for length generalization: O(T^{O(K)}) | Mixed |
| Use complexity measure T(f)^{K(f)} for 2-layer C-RASP | Minimum-Complexity Interpolator · C-RASP^2 | maximum training input length sufficient for length generalization: N_mci(α) ≤ O(α^{O(1)}) | Helped |
Surprising findings
- Linear CFGs and all CFGs admit length generalization in the limit but no computable non-asymptotic bound on training length.
Limitations
- The Minimum-Complexity Interpolator is computationally intractable for general function classes (e.g., minimal DFA is NP-hard).
- No lower bound is known for 2-layer C-RASP length complexity.
- Results are in an idealized setting with infinite computational resources and do not directly address gradient-based training.
Experimental setup
Baselines: Minimum-Complexity Interpolator
Builds on: Gold identification in the limit C-RASP RASP-L conjecture Minimum Description Length
Closest papers by meaning
- Universal Length Generalization with Turing Programs (ICML 2025 · similarity 0.90)
- Length Generalization for Transformers via Compression (NeurIPS 2026 · similarity 0.89)
- A Formal Framework for Understanding Length Generalization in Transformers (ICLR 2025 · similarity 0.87)
- What Algorithms can Transformers Learn? A Study in Length Generalization (ICLR 2024 · similarity 0.87)
- Provable Length Generalization in Sequence Prediction via Spectral Filtering (ICML 2025 · similarity 0.87)
- The Role of Sparsity for Length Generalization in LLMs (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.