Exact-Solution Volume and Length Generalization in Transformers

arXiv:2610.07676v1 Announce Type: cross Abstract: Research on transformer expressivity shows whether a transformer is capable of solving a given task, but gives little indication of whether the solution, if learned, is generalizable to longer input lengths. We study this question through normalized exact-solution volume (NESV): the fraction of a bounded parameter region that achieves an exact solution on every input of length n. For fixed-width, single-layer transformers with log n-scaled attention, we establish asymptotic bounds on NESV for four tasks: FIRST (Theta(1)), MAJORITY (Theta(1/(nlog n))), INDEX (Theta(1/n^3)), and PARITY (0). These results are consistent with previous empirical results: the faster the exact-solution volume decays with input length, the harder it is to length-generalize on that task. Looking deeper into INDEX, our volume analysis reveals two error sources that grow with n. Consequently, we study a transformer model that would structurally eliminate one of the terms, theoretically improving the NESV bound to Theta(n^{-1}), and empirically achieving 85% accuracy when tested at 10imes the training length, compared with the 60% accuracy of the original model. We conclude that volume analysis may be a useful approach to identify concrete sources of length sensitivity and thus provide insights into task-specific model refinements.

Related

• To See the Unseen: on the Generalization Ability of Transformers in Symbolic Reasoning
• PAC-Bayes Beyond Parameter Space: Behavioral Equivalence, Z-Information, and Exact Complexity Decomposition
• ArGEnT: Arbitrary Geometry-encoded Transformer for Operator Learning
• When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers
• Exact Attention Sensitivity and the Geometry of Transformer Stability

Source: arXiv cs.AI | 2026-10-07