# Relative Positional Encoding for Transformers with Linear Complexity

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 71 references that are in the map.
- First posted on arXiv 18 May 2021.

## Builds on (most cited first, 30 of 46)

- [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)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [DeBERTa: Decoding-enhanced BERT with Disentangled Attention](https://mlsanity.com/paper/2006.03654/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [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)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Efficient Attention: Attention with Linear Complexities](https://mlsanity.com/paper/1812.01243/) (2018)
- [Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernel](https://mlsanity.com/paper/1908.11775/) (2019)
- [Rethinking Positional Encoding in Language Pre-training](https://mlsanity.com/paper/2006.15595/) (2020)
- [DDSP: Differentiable Digital Signal Processing](https://mlsanity.com/paper/2001.04643/) (2020)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)
- [Compound Word Transformer: Learning to Compose Full-Song Music over Dynamic Directed Hypergraphs](https://mlsanity.com/paper/2101.02402/) (2021)
- [LambdaNetworks: Modeling Long-Range Interactions Without Attention](https://mlsanity.com/paper/2102.08602/) (2021)
- [The Best of Both Worlds: Combining Recent Advances in Neural Machine Translation](https://mlsanity.com/paper/1804.09849/) (2018)
- [Language Modeling with Deep Transformers](https://mlsanity.com/paper/1905.04226/) (2019)
- [Onsets and Frames: Dual-Objective Piano Transcription](https://mlsanity.com/paper/1710.11153/) (2017)

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

- [cosFormer: Rethinking Softmax in Attention](https://mlsanity.com/paper/2202.08791/) (2022)
- [Learnable Fourier Features for Multi-Dimensional Spatial Positional Encoding](https://mlsanity.com/paper/2106.02795/) (2021)
- [Edit Flows: Flow Matching with Edit Operations](https://mlsanity.com/paper/2506.09018/) (2025)
- [From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers](https://mlsanity.com/paper/2107.07999/) (2021)
- [A Text Attention Network for Spatial Deformation Robust Scene Text Image Super-resolution](https://mlsanity.com/paper/2203.09388/) (2022)
- [PaTH Attention: Position Encoding via Accumulating Householder Transformations](https://mlsanity.com/paper/2505.16381/) (2025)
- [ActionFlow: Equivariant, Accurate, and Efficient Policies with Spatially Symmetric Flow Matching](https://mlsanity.com/paper/2409.04576/) (2024)
- [Efficient Attention via Control Variates](https://mlsanity.com/paper/2302.04542/) (2023)
- [ComRoPE: Scalable and Robust Rotary Position Embedding Parameterized by Trainable Commuting Angle Matrices](https://mlsanity.com/paper/2506.03737/) (2025)
- [Linearized Relative Positional Encoding](https://mlsanity.com/paper/2307.09270/) (2023)
- [Variable-Length Music Score Infilling via XLNet and Musically Specialized Positional Encoding](https://mlsanity.com/paper/2108.05064/) (2021)
- [Positional Encoding in Transformer-Based Time Series Models: A Survey](https://mlsanity.com/paper/2502.12370/) (2025)
- [BERT-like Pre-training for Symbolic Piano Music Classification Tasks](https://mlsanity.com/paper/2107.05223/) (2021)
- [Stochastic positional embeddings improve masked image modeling](https://mlsanity.com/paper/2308.00566/) (2023)
- [Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers](https://mlsanity.com/paper/2302.01925/) (2023)
- [Natural Language Processing Methods for Symbolic Music Generation and Information Retrieval: a Survey](https://mlsanity.com/paper/2402.17467/) (2024)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Softmax Transformers are Turing-Complete](https://mlsanity.com/paper/2511.20038/) (2025)
- [Exploring Transformer Extrapolation](https://mlsanity.com/paper/2307.10156/) (2023)
- [Linear Transformer Topological Masking with Graph Random Features](https://mlsanity.com/paper/2410.03462/) (2024)
- [Transformers as Graph-to-Graph Models](https://mlsanity.com/paper/2310.17936/) (2023)
- [Structure-informed Positional Encoding for Music Generation](https://mlsanity.com/paper/2402.13301/) (2024)
- [Melody Infilling with User-Provided Structural Context](https://mlsanity.com/paper/2210.02829/) (2022)
- [Moonbeam: A MIDI Foundation Model Using Both Absolute and Relative Music Attributes](https://mlsanity.com/paper/2505.15559/) (2025)
- [Ripple Attention for Visual Perception with Sub-quadratic Complexity](https://mlsanity.com/paper/2110.02453/) (2021)
- [LeaPformer: Enabling Linear Transformers for Autoregressive and Simultaneous Tasks via Learned Proportions](https://mlsanity.com/paper/2405.13046/) (2024)
- [F-StrIPE: Fast Structure-Informed Positional Encoding for Symbolic Music Generation](https://mlsanity.com/paper/2502.10491/) (2025)
- [Finding Strong Gravitational Lenses Through Self-Attention](https://mlsanity.com/paper/2110.09202/) (2021)
- [FastRPB: a Scalable Relative Positional Encoding for Long Sequence Tasks](https://mlsanity.com/paper/2202.11364/) (2022)
- [Lightweight Structure-Aware Attention for Visual Understanding](https://mlsanity.com/paper/2211.16289/) (2022)

## Abstract (arXiv)

Recent advances in Transformer models allow for unprecedented sequence lengths, due to linear space and time complexity. In the meantime, relative positional encoding (RPE) was proposed as beneficial for classical Transformers and consists in exploiting lags instead of absolute positions for inference. Still, RPE is not available for the recent linear-variants of the Transformer, because it requires the explicit computation of the attention matrix, which is precisely what is avoided by such methods. In this paper, we bridge this gap and present Stochastic Positional Encoding as a way to generate PE that can be used as a replacement to the classical additive (sinusoidal) PE and provably behaves like RPE. The main theoretical contribution is to make a connection between positional encoding and cross-covariance structures of correlated Gaussian processes. We illustrate the performance of our approach on the Long-Range Arena benchmark and on music generation.