Exact-Solution Volume and Length Generalization in Transformers

Key points

• 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$.1
• For fixed-width, single-layer transformers with $\log n$-scaled attention, we establish asymptotic bounds on NESV for four tasks: FIRST ($Θ(1)$), MAJORITY ($Θ(1/(n\log n))$), INDEX ($Θ(1/n^3)$), and PARITY ($0$).1
• Consequently, we study a transformer model that would structurally eliminate one of the terms, theoretically improving the NESV bound to $Θ(n^{-1})$, and empirically achieving 85% accuracy when tested at $10\times$ the training length, compared with the 60% accuracy of the original model.1
• 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.1

Sources (1)

• [1]Exact-Solution Volume and Length Generalization in Transformers
  arXiv (AI, ML, NLP, CV, robotics, multi-agent) · Oct 6, 03:11 AM

  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$.

Extractive summary: sentences quoted from the sources.