A Formal Framework for Understanding Length Generalization in Transformers
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908343431331840 |
|---|---|
| author | Huang, Xinting Yang, Andy Bhattamishra, Satwik Sarrof, Yash Krebs, Andreas Zhou, Hattie Nakkiran, Preetum Hahn, Michael |
| author_facet | Huang, Xinting Yang, Andy Bhattamishra, Satwik Sarrof, Yash Krebs, Andreas Zhou, Hattie Nakkiran, Preetum Hahn, Michael |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_02140 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Formal Framework for Understanding Length Generalization in Transformers Huang, Xinting Yang, Andy Bhattamishra, Satwik Sarrof, Yash Krebs, Andreas Zhou, Hattie Nakkiran, Preetum Hahn, Michael Machine Learning 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. |
| title | A Formal Framework for Understanding Length Generalization in Transformers |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2410.02140 |