A major challenge for transformers is generalizing to sequences longer than those observed during training. While previous works have empirically shown that transformers can either succeed or fail at length generalization depending on the task, theoretical understanding of this phenomenon remains limited. In this work, we introduce a rigorous theoretical framework to analyze length generalization in causal transformers with learnable absolute positional encodings. In particular, we characterize those functions that are identifiable in the limit from sufficiently long inputs with absolute positional encodings under an idealized inference scheme using a norm-based regularizer. This enables us to prove the possibility of length generalization for a rich family of problems. We experimentally validate the theory as a predictor of success and failure of length generalization across a range of algorithmic and formal language tasks. Our theory not only explains a broad set of empirical observations but also opens the way to provably predicting length generalization capabilities in transformers.

本研究解决了变换器在处理长于训练序列的输入时的泛化能力不足问题。我们提出了一个严格的理论框架，分析使用可学习绝对位置编码的因果变换器的长度泛化，证明了一类问题的长度泛化可能性。这一理论不仅解释了许多经验观察，还为预测变换器的长度泛化能力提供了可证明的方法。

理解变换器长度泛化的正式框架