mlsanityData to 14 Oct 2026

Relative Positional Encoding for Transformers with Linear Complexity

arXiv 2105.08399 ↗First posted 18 May 2021cs.LG cs.CL cs.SDcited by 37

Not on the map. Why?

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.

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

46 of 71 references.

References · 46

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  4. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,364
  5. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,599
  6. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,372
  7. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,548
  8. 2019The Curious Case of Neural Text Degenerationcited by 2,916
  9. 2019ALBERT: A Lite BERT for Self-supervised Learning of Language Representationscited by 2,790
  10. 2020DeBERTa: Decoding-enhanced BERT with Disentangled Attentioncited by 2,181
  11. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  12. 2019Transformer-XL: Attentive Language Models Beyond a Fixed-Length Contextcited by 1,850
34 more
  1. 2020Rethinking Attention with Performerscited by 1,601
  2. 2019Generating Long Sequences with Sparse Transformerscited by 1,546
  3. 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
  4. 2018Self-Attention with Relative Position Representationscited by 1,120
  5. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 700
  6. 2018Universal Transformerscited by 647
  7. 2017Convolutional Sequence to Sequence Learningcited by 552
  8. 2020Efficient Content-Based Sparse Attention with Routing Transformerscited by 471
  9. 2018Efficient Attention: Attention with Linear Complexitiescited by 368
  10. 2019Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernelcited by 213
  11. 2020Rethinking Positional Encoding in Language Pre-trainingcited by 197
  12. 2020DDSP: Differentiable Digital Signal Processingcited by 178
  13. 2018ListOps: A Diagnostic Dataset for Latent Tree Learningcited by 129
  14. 2021Compound Word Transformer: Learning to Compose Full-Song Music over Dynamic Directed Hypergraphscited by 110
  15. 2021LambdaNetworks: Modeling Long-Range Interactions Without Attentioncited by 107
  16. 2018The Best of Both Worlds: Combining Recent Advances in Neural Machine Translationcited by 102
  17. 2019Language Modeling with Deep Transformerscited by 96
  18. 2017Onsets and Frames: Dual-Objective Piano Transcriptioncited by 94
  19. 2020Improve Transformer Models with Better Relative Position Embeddingscited by 73
  20. 2020Positional Encoding as Spatial Inductive Bias in GANscited by 69
  21. 2016madmom: a new Python Audio and Music Signal Processing Librarycited by 64
  22. 2020Learning to Encode Position for Transformer with Continuous Dynamical Modelcited by 61
  23. 2019LakhNES: Improving multi-instrumental music generation with cross-domain pre-trainingcited by 54
  24. 2019Encoding word order in complex embeddingscited by 53
  25. 2020What Do Position Embeddings Learn? An Empirical Study of Pre-Trained Language Model Positional Encodingcited by 52
  26. 2019Transformers with convolutional context for ASRcited by 44
  27. 2019T-GSA: Transformer with Gaussian-weighted self-attention for speech enhancementcited by 34
  28. 2020Relative Positional Encoding for Speech Recognition and Direct Translationcited by 23
  29. 2020Local Self-Attention over Long Text for Efficient Document Retrievalcited by 18
  30. 2020Pop Music Transformer: Beat-based Modeling and Generation of Expressive Pop Piano Compositionscited by 16
  31. 2019Improving Generalization of Transformer for Speech Recognition with Parallel Schedule Sampling and Relative Positional Embeddingcited by 12
  32. 2015Cross-Covariance Functions for Multivariate Geostatisticscited by 8
  33. 2019Lattice-Based Transformer Encoder for Neural Machine Translationcited by 5
  34. 2019Positional Encoding by Robots with Non-Rigid Movementscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 5; 2023: 9; 2024: 5; 2025: 10; 2026: 2.

37 papers.

Sort:

By area:

  1. 2022cosFormer: Rethinking Softmax in Attentioncited by 213
  2. 2021Learnable Fourier Features for Multi-Dimensional Spatial Positional Encodingcited by 93
  3. 2025Edit Flows: Flow Matching with Edit Operationscited by 55
  4. 2021From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformerscited by 38
  5. 2022A Text Attention Network for Spatial Deformation Robust Scene Text Image Super-resolutioncited by 35
  6. 2025PaTH Attention: Position Encoding via Accumulating Householder Transformationscited by 34
  7. 2024ActionFlow: Equivariant, Accurate, and Efficient Policies with Spatially Symmetric Flow Matchingcited by 26
  8. 2023Efficient Attention via Control Variatescited by 23
  9. 2025ComRoPE: Scalable and Robust Rotary Position Embedding Parameterized by Trainable Commuting Angle Matricescited by 18
  10. 2023Linearized Relative Positional Encodingcited by 17
  11. 2021Variable-Length Music Score Infilling via XLNet and Musically Specialized Positional Encodingcited by 14
  12. 2025Positional Encoding in Transformer-Based Time Series Models: A Surveycited by 14
25 more
  1. 2021BERT-like Pre-training for Symbolic Piano Music Classification Taskscited by 12
  2. 2023Stochastic positional embeddings improve masked image modelingcited by 12
  3. 2023Learning a Fourier Transform for Linear Relative Positional Encodings in Transformerscited by 10
  4. 2024Natural Language Processing Methods for Symbolic Music Generation and Information Retrieval: a Surveycited by 10
  5. 2023Simplex Random Featurescited by 9
  6. 2025Softmax Transformers are Turing-Completecited by 9
  7. 2023Exploring Transformer Extrapolationcited by 8
  8. 2024Linear Transformer Topological Masking with Graph Random Featurescited by 7
  9. 2023Transformers as Graph-to-Graph Modelscited by 5
  10. 2024Structure-informed Positional Encoding for Music Generationcited by 5
  11. 2022Melody Infilling with User-Provided Structural Contextcited by 4
  12. 2025Moonbeam: A MIDI Foundation Model Using Both Absolute and Relative Music Attributescited by 4
  13. 2021Ripple Attention for Visual Perception with Sub-quadratic Complexitycited by 2
  14. 2024LeaPformer: Enabling Linear Transformers for Autoregressive and Simultaneous Tasks via Learned Proportionscited by 2
  15. 2025F-StrIPE: Fast Structure-Informed Positional Encoding for Symbolic Music Generationcited by 2
  16. 2021Finding Strong Gravitational Lenses Through Self-Attentioncited by 1
  17. 2022FastRPB: a Scalable Relative Positional Encoding for Long Sequence Taskscited by 1
  18. 2022Lightweight Structure-Aware Attention for Visual Understandingcited by 1
  19. 2023Enhancing Multivariate Time Series Classifiers through Self-Attention and Relative Positioning Infusioncited by 1
  20. 2023Deep Multiple Instance Learning with Distance-Aware Self-Attentioncited by 1
  21. 2025CoPE: A Lightweight Complex Positional Encodingcited by 1
  22. 2025Of All StrIPEs: Investigating Structure-informed Positional Encoding for Efficient Music Generationcited by 0
  23. 2025Evaluation of Coding Schemes for Transformer-based Gene Sequence Modelingcited by 0
  24. 2026BSAT: B-Spline Adaptive Tokenizer for Long-Term Time Series Forecastingcited by 0
  25. 2026Beyond Static Positional Encoding: Bayesian Time-aware Attention for Non-Stationary Long-term Time Series Forecastingcited by 0