Reproduce “Length Generalization Bounds for 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
Andy Yang, Pascal Bergsträßer, Georg Zetzsche, David Chiang, Anthony W. Lin
This research investigates length generalization in transformers, demonstrating that non-asymptotic length generalization is uncomputable for general C-RASP programs and (1, log n)-precision transformers, including models of depth two. The study also establishes computable, exponential length generalization bounds for the more restricted class of positive C-RASP and (1, 1)-precision transformers, which align with real-world fixed-precision models.
Key insights
- The fundamental ability of transformers to achieve non-asymptotic length generalization is contingent on the decidability of the language emptiness problem for their corresponding formalisms (C-RASP).
- Perfect length generalization for general C-RASP and (1, log n)-precision transformers is uncomputable, even under ideal learning conditions, implying that no algorithm can universally guarantee it for arbitrary depths.
- Restricting precision, as in (1, 1)-precision transformers (equivalent to C-RASP+), transforms the problem from uncomputable to computable, yielding exponential length generalization bounds that match real-world fixed-precision models.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.