# Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 53 references that are in the map.
- First posted on arXiv 23 Jun 2021.

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

- [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)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [End-to-End Object Detection with Transformers](https://mlsanity.com/paper/2005.12872/) (2020)
- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Training data-efficient image transformers & distillation through attention](https://mlsanity.com/paper/2012.12877/) (2020)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (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)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [Conformer: Convolution-augmented Transformer for Speech Recognition](https://mlsanity.com/paper/2005.08100/) (2020)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [fairseq: A Fast, Extensible Toolkit for Sequence Modeling](https://mlsanity.com/paper/1904.01038/) (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)
- [Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Books](https://mlsanity.com/paper/1506.06724/) (2015)
- [What Does BERT Look At? An Analysis of BERT's Attention](https://mlsanity.com/paper/1906.04341/) (2019)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Image Transformer](https://mlsanity.com/paper/1802.05751/) (2018)
- [Maximum Likelihood Training of Score-Based Diffusion Models](https://mlsanity.com/paper/2101.09258/) (2021)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)

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

- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [What Makes Convolutional Models Great on Long Sequence Modeling?](https://mlsanity.com/paper/2210.09298/) (2022)
- [KERPLE: Kernelized Relative Positional Embedding for Length Extrapolation](https://mlsanity.com/paper/2205.09921/) (2022)
- [Flowformer: Linearizing Transformers with Conservation Flows](https://mlsanity.com/paper/2202.06258/) (2022)
- [RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrieval](https://mlsanity.com/paper/2402.18510/) (2024)
- [Your Transformer May Not be as Powerful as You Expect](https://mlsanity.com/paper/2205.13401/) (2022)
- [From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers](https://mlsanity.com/paper/2107.07999/) (2021)
- [DAPE: Data-Adaptive Positional Encoding for Length Extrapolation](https://mlsanity.com/paper/2405.14722/) (2024)
- [Attention Mechanism in Neural Networks: Where it Comes and Where it Goes](https://mlsanity.com/paper/2204.13154/) (2022)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Efficient Attention via Control Variates](https://mlsanity.com/paper/2302.04542/) (2023)
- [ESSAformer: Efficient Transformer for Hyperspectral Image Super-resolution](https://mlsanity.com/paper/2307.14010/) (2023)
- [Do Efficient Transformers Really Save Computation?](https://mlsanity.com/paper/2402.13934/) (2024)
- [Learning the RoPEs: Better 2D and 3D Position Encodings with STRING](https://mlsanity.com/paper/2502.02562/) (2025)
- [Can Vision Transformers Perform Convolution?](https://mlsanity.com/paper/2111.01353/) (2021)
- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)
- [Locality-Sensitive Hashing-Based Efficient Point Transformer with Applications in High-Energy Physics](https://mlsanity.com/paper/2402.12535/) (2024)
- [A Quality Index Metric and Method for Online Self-Assessment of Autonomous Vehicles Sensory Perception](https://mlsanity.com/paper/2203.02588/) (2022)
- [Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers](https://mlsanity.com/paper/2302.01925/) (2023)
- [Let the Code LLM Edit Itself When You Edit the Code](https://mlsanity.com/paper/2407.03157/) (2024)
- [DAPE V2: Process Attention Score as Feature Map for Length Extrapolation](https://mlsanity.com/paper/2410.04798/) (2024)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Mnemosyne: Learning to Train Transformers with Transformers](https://mlsanity.com/paper/2302.01128/) (2023)
- [Monotonic Location Attention for Length Generalization](https://mlsanity.com/paper/2305.20019/) (2023)
- [Single Cells Are Spatial Tokens: Transformers for Spatial Transcriptomic Data Imputation](https://mlsanity.com/paper/2302.03038/) (2023)
- [Linear Transformer Topological Masking with Graph Random Features](https://mlsanity.com/paper/2410.03462/) (2024)
- [Statistical Advantage of Softmax Attention: Insights from Single-Location Regression](https://mlsanity.com/paper/2509.21936/) (2025)
- [Improving Sample Efficiency of Value Based Models Using Attention and Vision Transformers](https://mlsanity.com/paper/2202.00710/) (2022)
- [Self-explaining Hierarchical Model for Intraoperative Time Series](https://mlsanity.com/paper/2210.04417/) (2022)
- [DBA: Efficient Transformer with Dynamic Bilinear Low-Rank Attention](https://mlsanity.com/paper/2211.16368/) (2022)

## Abstract (arXiv)

The attention module, which is a crucial component in Transformer, cannot scale efficiently to long sequences due to its quadratic complexity. Many works focus on approximating the dot-then-exponentiate softmax function in the original attention, leading to sub-quadratic or even linear-complexity Transformer architectures. However, we show that these methods cannot be applied to more powerful attention modules that go beyond the dot-then-exponentiate style, e.g., Transformers with relative positional encoding (RPE). Since in many state-of-the-art models, relative positional encoding is used as default, designing efficient Transformers that can incorporate RPE is appealing. In this paper, we propose a novel way to accelerate attention calculation for Transformers with RPE on top of the kernelized attention. Based upon the observation that relative positional encoding forms a Toeplitz matrix, we mathematically show that kernelized attention with RPE can be calculated efficiently using Fast Fourier Transform (FFT). With FFT, our method achieves O(nlog n) time complexity. Interestingly, we further demonstrate that properly using relative positional encoding can mitigate the training instability problem of vanilla kernelized attention. On a wide range of tasks, we empirically show that our models can be trained from scratch without any optimization issues. The learned model performs better than many efficient Transformer variants and is faster than standard Transformer in the long-sequence regime.