# Randomized Positional Encodings Boost Length Generalization of Transformers

arXiv: https://arxiv.org/abs/2305.16843 · HTML: https://mlsanity.com/paper/2305.16843/

## Key facts

- Cited by 117 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 36 references that are in the map.
- First posted on arXiv 26 May 2023.

## Builds on (most cited first, 29 of 29)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Scaling Language Models: Methods, Analysis & Insights from Training Gopher](https://mlsanity.com/paper/2112.11446/) (2021)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [A Generalist Agent](https://mlsanity.com/paper/2205.06175/) (2022)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Convolutional Sequence to Sequence Learning](https://mlsanity.com/paper/1705.03122/) (2017)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers](https://mlsanity.com/paper/2108.12284/) (2021)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Making Transformers Solve Compositional Tasks](https://mlsanity.com/paper/2108.04378/) (2021)
- [The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization](https://mlsanity.com/paper/2110.07732/) (2021)
- [Learning to Encode Position for Transformer with Continuous Dynamical Model](https://mlsanity.com/paper/2003.09229/) (2020)
- [A Generalist Neural Algorithmic Learner](https://mlsanity.com/paper/2209.11142/) (2022)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [Compositional Generalization by Learning Analytical Expressions](https://mlsanity.com/paper/2006.10627/) (2020)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [Systematic Generalization and Emergent Structures in Transformers Trained on Structured Tasks](https://mlsanity.com/paper/2210.00400/) (2022)
- [A Survey of Neural Networks and Formal Languages](https://mlsanity.com/paper/2006.01338/) (2020)

## Built on by (most cited first, 30 of 117)

- [Language Modeling Is Compression](https://mlsanity.com/paper/2309.10668/) (2023)
- [Repeat After Me: Transformers are Better than State Space Models at Copying](https://mlsanity.com/paper/2402.01032/) (2024)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Round and Round We Go! What makes Rotary Positional Encodings useful?](https://mlsanity.com/paper/2410.06205/) (2024)
- [PoSE: Efficient Context Window Extension of LLMs via Positional Skip-wise Training](https://mlsanity.com/paper/2309.10400/) (2023)
- [HiAgent: Hierarchical Working Memory Management for Solving Long-Horizon Agent Tasks with Large Language Model](https://mlsanity.com/paper/2408.09559/) (2024)
- [Transformers Can Achieve Length Generalization But Not Robustly](https://mlsanity.com/paper/2402.09371/) (2024)
- [FiT: Flexible Vision Transformer for Diffusion Model](https://mlsanity.com/paper/2402.12376/) (2024)
- [Transformers Can Do Arithmetic with the Right Embeddings](https://mlsanity.com/paper/2405.17399/) (2024)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Survey](https://mlsanity.com/paper/2311.12351/) (2023)
- [Positional Description Matters for Transformers Arithmetic](https://mlsanity.com/paper/2311.14737/) (2023)
- [LongEmbed: Extending Embedding Models for Long Context Retrieval](https://mlsanity.com/paper/2404.12096/) (2024)
- [CLEX: Continuous Length Extrapolation for Large Language Models](https://mlsanity.com/paper/2310.16450/) (2023)
- [DreamX-World 1.0: A General-Purpose Interactive World Model](https://mlsanity.com/paper/2606.16993/) (2026)
- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [Giraffe: Adventures in Expanding Context Lengths in LLMs](https://mlsanity.com/paper/2308.10882/) (2023)
- [DAPE: Data-Adaptive Positional Encoding for Length Extrapolation](https://mlsanity.com/paper/2405.14722/) (2024)
- [Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges](https://mlsanity.com/paper/2502.01612/) (2025)
- [A phase transition between positional and semantic learning in a solvable model of dot-product attention](https://mlsanity.com/paper/2402.03902/) (2024)
- [The CLRS-Text Algorithmic Reasoning Language Benchmark](https://mlsanity.com/paper/2406.04229/) (2024)
- [Resonance RoPE: Improving Context Length Generalization of Large Language Models](https://mlsanity.com/paper/2403.00071/) (2024)
- [The Efficiency Spectrum of Large Language Models: An Algorithmic Survey](https://mlsanity.com/paper/2312.00678/) (2023)
- [Dataset Decomposition: Faster LLM Training with Variable Sequence Length Curriculum](https://mlsanity.com/paper/2405.13226/) (2024)
- [ALR2: A Retrieve-then-Reason Framework for Long-context Question Answering](https://mlsanity.com/paper/2410.03227/) (2024)
- [ViTAR: Vision Transformer with Any Resolution](https://mlsanity.com/paper/2403.18361/) (2024)
- [Language Models Need Inductive Biases to Count Inductively](https://mlsanity.com/paper/2405.20131/) (2024)
- [Universal Length Generalization with Turing Programs](https://mlsanity.com/paper/2407.03310/) (2024)
- [DGR-MIL: Exploring Diverse Global Representation in Multiple Instance Learning for Whole Slide Image Classification](https://mlsanity.com/paper/2407.03575/) (2024)
- [Two Stones Hit One Bird: Bilevel Positional Encoding for Better Length Extrapolation](https://mlsanity.com/paper/2401.16421/) (2024)

## Abstract (arXiv)

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).