Reproduce “Non-Asymptotic Length Generalization” 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

Thomas Chen, Tengyu Ma, Zhiyuan Li

This research introduces a non-asymptotic theory of length generalization, quantifying the minimum input length required for models to generalize beyond their training data. It establishes bounds for C-RASP, a transformer-like model class, finding that while 1-layer C-RASP generalizes polynomially, 2-layer C-RASP exhibits an exponential dependency on the number of attention heads.

Key insights

  • A function class admits non-asymptotic length generalization if and only if its language equivalence problem is decidable, providing a robust criterion for learnability.
  • Even if a function class is asymptotically learnable (e.g., Context-Free Grammars), it may not allow for non-asymptotic length generalization because the required input length can be non-computable.
  • The complexity of achieving generalization varies significantly with model architecture; 1-layer C-RASP exhibits polynomial length dependency, whereas 2-layer C-RASP shows an exponential dependency on the number of attention heads.

Summary by alphaXiv.

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