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/(n\log 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 i