Reproduce “A Formal Framework for Understanding Length Generalization in Transformers” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, Michael Hahn

This research introduces a formal framework using 'Limit Transformers' and extended C-RASP to theoretically characterize length generalization in transformers with absolute positional encodings. The framework accurately predicts which algorithmic tasks will generalize to unseen lengths based on their definability within the C-RASP framework and their communication complexity, aligning with observed empirical success and failure patterns.

Key insights

  • Length generalization in transformers with absolute positional encodings (APE) is theoretically guaranteed for functions expressible by 'Periodic' and 'Local' Limit Transformers, a formal model of idealized transformer computation.
  • Functions requiring high communication complexity (e.g., arbitrary string copying) cannot be expressed by these generalizing Limit Transformers, providing a theoretical explanation for their empirical failure to generalize.
  • The inherent inductive biases conducive to length generalization in APE transformers appear to involve approximate translation-invariance in attention computations, aligning with the 'local' property.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.