Randomized Positional Encodings Boost Length Generalization of Transformers
Open accessAbstract
Transformers have impressive generalization capabilities on tasks with a fixed context length. However, they fail to generalize to sequences of arbitrary length, even for seemingly simple tasks such as duplicating a string. Moreover, simply training on longer sequences is inefficient due to the quadratic computation complexity of the global attention mechanism. In this work, we demonstrate that this failure mode is linked to positional encodings being out-of-distribution for longer sequences (even for relative encodings) and introduce a novel family of positional encodings that can overcome this problem. Concretely, our randomized positional encoding scheme simulates the positions of longer sequences and randomly selects an ordered subset to fit the sequence's length. Our large-scale empirical evaluation of 6000 models across 15 algorithmic reasoning tasks shows that our method allows Transformers to generalize to sequences of unseen length (increasing test accuracy by 12.0% on average).
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Models trained from scratch show little to no length generalization on parity.
“and parity (Bhattamishra et al., 2020;Chiang & Cholak, 2022;Ruoss et al., 2023;Delétang et al., 2023)”
From What Algorithms can Transformers Learn? A Study in Length Generalization (2023) · cites this paper as Ruoss et al., 2023
Positional embeddings greatly affect Transformers' ability to generalize to longer lengths.
“Positional embeddings have been shown to greatly affect Transformers' ability to generalize to longer lengths (Press et al., 2021;Kazemnejad et al., 2024;Ruoss et al., 2023;Su et al., 2024;Li et al., 2023;Cho et al., 2024;Sabbaghi et al., 2024;McLeish et al., 2024;Golovneva et al., 2024).”
From Looped Transformers for Length Generalization (2024) · cites this paper as Ruoss et al., 2023
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Convolutional Sequence to Sequence Learning
Gehring, J., Auli, M., Grangier, D., Yarats, D., & Dauphin, Y. N. (2017) · arXiv · doi:10.48550/arxiv.1705.03122 · Cited by 2,850 · cited 4× · see citing works
“The first approaches simply added a transformation of the tokens’ positions, e.g., scaled si-nusoids (Vaswani et al., 2017) or learned embed-dings (Gehring et al., 2017), to the embeddings of the input sequence.”
BackgroundMethodInfluential
Flagged first, then by citations
Research works printed but not linked: 32
- Joshua Ackerman and George Cybenko. 2020. A survey of neural networks and formal languages. arXiv:2006.01338. · arXiv
- Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing. · DOI · Paper page
- David Chiang and Peter Cholak. 2022. Overcoming a theoretical limitation of self-attention. In Proceed- ings of the 60th Annual Meeting of the Association for Computational Linguistics. · DOI · Paper page
- Noam Chomsky. 1956. Three models for the description of language. IRE Trans. Inf. Theory. · DOI
- Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. 2021. The devil is in the detail: Simple tricks im- prove systematic generalization of transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. · DOI
- Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. 2022. The neural data router: Adaptive control flow in transformers improves systematic generalization. In The Tenth International Conference on Learning Representations.
- Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Car- bonell, Quoc Viet Le, and Ruslan Salakhutdinov. 2019. Transformer-xl: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Conference of the Association for Computa- tional Linguistics. · DOI · Paper page
- Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. 2019. Univer- sal transformers. In 7th International Conference on Learning Representations.
- Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. 2023. Neural networks and the chomsky hierarchy. In The Eleventh International Conference on Learning Representations.
- Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: pre-training of deep bidirectional transformers for language under- standing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,. · DOI · Paper page
- Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. 2021. An image is worth 16x16 words: Transformers for image recognition at scale. In 9th International Conference on Learning Representations.
- Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. 2020. How can self-attention networks recognize dyck-n languages? In Findings of the Association for Com- putational Linguistics. · DOI
- Jeffrey L. Elman. 1990. Finding structure in time. Cogn. Sci. · DOI · Paper page
- Michael Hahn. 2020. Theoretical limitations of self- attention in neural sequence models. Trans. Assoc. Comput. Linguistics. · DOI · Paper page
- Yiding Hao, Dana Angluin, and Robert Frank. 2022. Formal language recognition by hard attention trans- formers: Perspectives from circuit complexity. Trans. Assoc. Comput. Linguistics.
- Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyria- cos Nikiforou, Mehdi Bennani, Róbert Csordás, An- drew Joseph Dudzik, Matko Bosnjak, Alex Vitvitskyi, Yulia Rubanova, Andreea Deac, Beatrice Bevilacqua, Yaroslav Ganin, Charles Blundell, and Petar Velick- ovic. 2022. A generalist neural algorithmic learner. In Learning on Graphs Conference, LoG 2022, 9-12 December 2022, Virtual Event.
- Najoung Kim and Tal Linzen. 2020. COGS: A compo- sitional generalization challenge based on semantic interpretation. In Proceedings of the 2020 Confer- ence on Empirical Methods in Natural Language Processing. · DOI · Paper page
- Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In 3rd Interna- tional Conference on Learning Representations.
- Brenden M. Lake and Marco Baroni. 2018. General- ization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. In Proceedings of the 35th International Conference on Machine Learning.
- Yuxuan Li and James L. McClelland. 2022. Systematic generalization and emergent structures in transform- ers trained on structured tasks. arXiv:2210.00400. · DOI
- Qian Liu, Shengnan An, Jian-Guang Lou, Bei Chen, Zeqi Lin, Yan Gao, Bin Zhou, Nanning Zheng, and Dongmei Zhang. 2020a. Compositional generaliza- tion by learning analytical expressions. In Advances in Neural Information Processing Systems 33.
- Xuanqing Liu, Hsiang-Fu Yu, Inderjit S. Dhillon, and Cho-Jui Hsieh. 2020b. Learning to encode position for transformer with continuous dynamical model. In Proceedings of the 37th International Conference on Machine Learning.
- William Merrill. 2019. Sequential neural networks as automata. arXiv:1906.01615. · arXiv
- William Merrill and Ashish Sabharwal. 2022. Log- precision transformers are constant-depth uniform threshold circuits. arXiv:2207.00729. · DOI
- Santiago Ontañón, Joshua Ainslie, Zachary Fisher, and Vaclav Cvicek. 2022. Making transformers solve compositional tasks. In Proceedings of the 60th An- nual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). · DOI
- Ofir Press, Noah Smith, and Mike Lewis. 2022. Train short, test long: Attention with linear biases enables input length extrapolation. In The Tenth International Conference on Learning Representations.
- Jack W. Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, H. Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susan- nah Young, Eliza Rutherford, Tom Hennigan, Ja- cob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Mari- beth Rauh, Po-Sen Huang, Amelia Glaese, Jo- hannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John Mellor, Irina Higgins, Antonia Creswell, Nat McAleese, Amy Wu, Erich Elsen, Sid- dhant M. Jayakumar, Elena Buchatskaya, David Bud- den, Esme Sutherland, Karen Simonyan, Michela Pa- ganini, Laurent Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean-Baptiste Lespiau, Maria Tsim- poukelli, Nikolai Grigorev, Doug Fritz, Thibault Sot- tiaux, Mantas Pajarskas, Toby Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson d'Autume, Yujia Li, Tayfun Terzi, Vladimir Mikulik, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy, Chris Jones, James Bradbury, Matthew Johnson, Blake A. Hechtman, Laura Weidinger, Iason Gabriel, William S. Isaac, Edward Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem Ayoub, Jeff Stanway, Lorrayne Bennett, Demis Hass- abis, Koray Kavukcuoglu, and Geoffrey Irving. 2021. Scaling language models: Methods, analysis & in- sights from training gopher. arXiv:2112.11446. · arXiv
- Scott E. Reed, Konrad Zolna, Emilio Parisotto, Sergio Gómez Colmenarejo, Alexander Novikov, Gabriel Barth-Maron, Mai Gimenez, Yury Sulsky, Jackie Kay, Jost Tobias Springenberg, Tom Eccles, Jake Bruce, Ali Razavi, Ashley Edwards, Nicolas Heess, Yutian Chen, Raia Hadsell, Oriol Vinyals, Mahyar Bordbar, and Nando de Freitas. 2022. A generalist agent. Trans. Mach. Learn. Res.
- Ryoma Sato, Makoto Yamada, and Hisashi Kashima. 2021. Random features strengthen graph neural net- works. In Proceedings of the 2021 SIAM Interna- tional Conference on Data Mining. · DOI
- Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu. 2021. Roformer: Enhanced transformer with rotary position embedding. arXiv:2104.09864. · arXiv
- Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. 2021. Long range arena : A benchmark for efficient transform- ers. In 9th International Conference on Learning Representations.
- Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Pro- cessing Systems 30. Table 4: Means and standard deviations (computed over random seeds) of the score (accuracy averaged over all test lengths) for the results of the main experiment (see Table 1). The random accuracy is 50%, except for CYCLE NAVIGATION, BUCKET SORT, and the modular arithmetic tasks, where it is 20%. We denote permutation-invariant tasks, which can be solved without positional information, with †. Numbers in bold are the best performers, per task. These results underline the superiority of our method, and especially when applied to relative positional encodings. Randomized (Ours) Level Task None sin / cos Relative ALiBi RoPE Learned sin / cos Relative ALiBi RoPE Learned ⋆ R EVEN PAIRS 50.1 ± 0.1 50.4 ± 0.2 67.6 ± 15.3 59.8 ± 3.2 50.4 ± 0.3 50.4 ± 0.2 99.7 ± 0.3 99.6 ± 0.6 71.4 ± 5.6 100.0 ± 0.0 96.2 ± 0.7 MODULAR ARITHMETIC (SIMPLE) 20.0 ± 0.0 20.2 ± 0.2 20.7 ± 0.5 23.2 ± 0.9 20.8 ± 0.5 20.1 ± 0.1 24.2 ± 1.4 24.9 ± 1.7 20.8 ± 0.3 23.5 ± 1.6 20.2 ± 0.4 PARITY CHECK † 50.4 ± 0.8 50.3 ± 0.2 50.4 ± 0.6 50.5 ± 0.6 50.4 ± 0.4 50.0 ± 0.1 51.1 ± 1.3 51.4 ± 0.5 50.0 ± 0.2 50.4 ± 1.0 50.6 ± 0.9 CYCLE NAVIGATION † 33.9 ± 10.5 23.8 ± 1.4 21.7 ± 0.8 31.1 ± 3.8 22.3 ± 0.9 21.0 ± 1.2 30.3 ± 10.7 45.9 ± 9.9 26.3 ± 2.4 52.9 ± 15.3 31.9 ± 8.2 DCF STACK MANIPULATION 50.2 ± 0.1 47.3 ± 1.9 50.1 ± 3.3 51.0 ± 8.0 49.6 ± 3.0 44.9 ± 3.7 69.2 ± 3.2 71.7 ± 4.7 69.5 ± 1.1 66.0 ± 2.0 66.1 ± 2.5 REVERSE STRING 52.7 ± 0.1 50.4 ± 0.1 54.2 ± 1.5 56.3 ± 2.6 51.2 ± 0.3 50.4 ± 0.2 72.9 ± 1.6 77.1 ± 6.6 75.1 ± 1.3 67.7 ± 1.1 52.7 ± 0.2 MODULAR ARITHMETIC 31.0 ± 0.1 24.3 ± 2.2 26.1 ± 2.0 28.1 ± 3.4 24.0 ± 2.4 22.3 ± 1.5 29.6 ± 4.6 28.8 ± 5.5 29.3 ± 1.6 28.6 ± 3.9 30.3 ± 2.6 SOLVE EQUATION 20.1 ± 0.0 20.9 ± 0.2 21.9 ± 0.7 23.6 ± 1.9 21.9 ± 0.6 20.2 ± 0.2 23.6 ± 0.5 25.4 ± 1.8 21.1 ± 0.7 22.3 ± 1.6 21.1 ± 0.7 CS DUPLICATE STRING 52.7 ± 0.1 50.4 ± 0.2 51.0 ± 0.4 51.0 ± 0.2 50.4 ± 0.2 50.4 ± 0.2 69.0 ± 2.9 73.1 ± 1.5 67.9 ± 1.4 67.1 ± 2.0 52.8 ± 0.1 MISSING DUPLICATE 51.4 ± 1.0 50.1 ± 0.6 51.1 ± 1.1 53.5 ± 0.4 53.9 ± 1.6 50.1 ± 0.4 50.4 ± 1.5 91.4 ± 9.8 75.2 ± 3.4 73.2 ± 1.2 51.2 ± 1.4 ODDS FIRST 52.7 ± 0.1 51.3 ± 0.2 51.5 ± 0.5 51.1 ± 0.2 50.8 ± 0.2 50.5 ± 0.1 62.5 ± 2.0 65.9 ± 1.6 62.2 ± 1.4 62.9 ± 1.3 52.7 ± 0.1 BINARY ADDITION 49.4 ± 0.3 47.3 ± 3.8 51.7 ± 1.3 48.5 ± 3.6 47.8 ± 5.4 48.9 ± 0.8 61.2 ± 1.7 62.0 ± 1.1 54.3 ± 1.5 57.4 ± 1.2 59.9 ± 1.3 BINARY MULTIPLICATION 49.8 ± 0.0 48.8 ± 1.0 50.2 ± 3.5 49.9 ± 2.3 49.6 ± 0.6 48.7 ± 1.7 51.8 ± 0.2 39.1 ± 7.1 49.2 ± 1.2 45.7 ± 6.6 51.6 ± 0.2 COMPUTE SQRT 50.2 ± 0.0 50.1 ± 0.0 51.5 ± 0.4 50.5 ± 0.2 50.3 ± 0.1 50.1 ± 0.1 51.9 ± 0.5 52.4 ± 0.6 51.1 ± 0.1 51.8 ± 0.3 51.0 ± 0.8 BUCKET SORT † 23.7 ± 0.0 25.6 ± 2.6 83.4 ± 6.6 29.3 ± 6.7 23.6 ± 3.8 20.7 ± 2.9 99.3 ± 0.4 99.4 ± 0.3 98.8 ± 0.7 99.3 ± 0.3 98.9
Cited by
Sorted by citations
What Algorithms can Transformers Learn? A Study in Length Generalization
Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J., Bengio, S., & Nakkiran, P. (2023) · arXiv · doi:10.48550/arxiv.2310.16028 · Cited by 10 · see citing works
Language models need inductive biases to count inductively
Chang, Y., & Bisk, Y. (2024) · arXiv · doi:10.48550/arxiv.2405.20131
“…into hierarchies, with a notion of complexity informed by formal languages (Del’etang et al., 2022; Zhou et al., 2023; Hao et al., 2022; Liu et al., 2022; Kazemnejad et al., 2024; Ebrahimi et al., 2020; Ruoss et al., 2023) or boolean functions (Bhattamishra et al., 2022; Abbe et al., 2023).”
BackgroundLooped Transformers for Length Generalization
Fan, Y., Du, Y., Ramchandran, K., & Lee, K. (2024) · arXiv · doi:10.48550/arxiv.2409.15647
- Authors
- Ruoss, A., Delétang, G., Genewein, T., Grau-Moya, J., Csordás, R., Bennani, M., Legg, S., & Veness, J.
- Affiliations
- University of Applied Sciences and Arts of Southern Switzerland (CH)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2023
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2305.16843
- OpenAlex
- W4378718138
- Cited by
- 1
- References
- 1
- Citations by year
- 2023: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- arXiv (Cornell University) (submittedVersion, cc-by)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Explainable Artificial Intelligence (XAI)
- Keywords
- positional encoding, length generalization, transformer models, out-of-distribution generalization, relative position encoding, algorithmic reasoning, global attention
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
