Exact-Solution Volume and Length Generalization in Transformers

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/n3)), 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 10× 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.