# FastRPB: a Scalable Relative Positional Encoding for Long Sequence Tasks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 23 references that are in the map.
- First posted on arXiv 23 Feb 2022.

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

- [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)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [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)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (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)
- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [Rethinking Positional Encoding in Language Pre-training](https://mlsanity.com/paper/2006.15595/) (2020)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)
- [Encoding word order in complex embeddings](https://mlsanity.com/paper/1912.12333/) (2019)
- [Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding](https://mlsanity.com/paper/2106.12566/) (2021)
- [Relative Positional Encoding for Transformers with Linear Complexity](https://mlsanity.com/paper/2105.08399/) (2021)
- [Discovering Transforms: A Tutorial on Circulant Matrices, Circular Convolution, and the Discrete Fourier Transform](https://mlsanity.com/paper/1805.05533/) (2018)
- [On Fast Computation of a Circulant Matrix-Vector Product](https://mlsanity.com/paper/2103.02605/) (2021)

## Built on by (most cited first, 1 of 1)

- [PJ-RoPE: A Fourier-Jet-Affine Position Space for Relative Attention](https://mlsanity.com/paper/2606.05345/) (2026)

## Abstract (arXiv)

Transformers achieve remarkable performance in various domains, including NLP, CV, audio processing, and graph analysis. However, they do not scale well on long sequence tasks due to their quadratic complexity w.r.t. the inputs length. Linear Transformers were proposed to address this limitation. However, these models have shown weaker performance on the long sequence tasks comparing to the original one. In this paper, we explore Linear Transformer models, rethinking their two core components. Firstly, we improved Linear Transformer with Shift-Invariant Kernel Function SIKF, which achieve higher accuracy without loss in speed. Secondly, we introduce FastRPB which stands for Fast Relative Positional Bias, which efficiently adds positional information to self-attention using Fast Fourier Transformation. FastRPB is independent of the self-attention mechanism and can be combined with an original self-attention and all its efficient variants. FastRPB has O(N log(N)) computational complexity, requiring O(N) memory w.r.t. input sequence length N.