FastRPB: a Scalable Relative Positional Encoding for Long Sequence Tasks

Maksim Zubkov, Daniil Gavrilov

TL;DR

Standard Transformers struggle on long sequences due to quadratic memory and computation costs, while efficient "Linear Transformers" often sacrifice accuracy—partly because existing relative positional encodings are too slow or memory-intensive. This paper introduces FastRPB, an FFT-accelerated relative positional bias that runs in $\mathcal{O}(N \log N)$ time and $\mathcal{O}(N)$ memory, alongside SIKF, a shift-invariant exponential kernel for linear attention. Together, they allow Linear Transformers to match or beat standard Transformers on long-context tasks with up to $10\times$ lower memory consumption and $30\times$ faster training than competing methods.

What Problem Does This Paper Address?

Standard self-attention scales quadratically ($\mathcal{O}(N^2)$) with sequence length $N$, creating a severe computational bottleneck for long documents and high-resolution images. Linear Transformers alleviate this by replacing softmax attention with kernel feature maps, achieving linear $\mathcal{O}(N)$ complexity.

However, Linear Transformers typically lag behind standard Transformers in accuracy. A primary cause is their inability to efficiently encode relative positional information (how far apart two tokens are). While relative positional encodings (RPE) significantly boost standard Transformers, traditional RPE techniques re-introduce quadratic complexity. The only existing linear alternative—Stochastic Positional Encoding (SPE)—relies on Monte Carlo sampling, making training extremely slow while providing inconsistent gains.

Methods

The authors target the two core limitations of Linear Transformers:

  1. Shift-Invariant Kernel Function (SIKF): Softmax in standard attention is naturally shift-invariant ($\text{softmax}(x + c) = \text{softmax}(x)$). Most linear kernels (such as $\text{ELU} + 1$ or DPFP) break this property. The authors propose using $\phi(x) = \exp(x)$ as a kernel, which mathematically guarantees shift-invariance across query and key shifts without adding computational overhead.
  2. Fast Relative Positional Bias (FastRPB): Instead of calculating pairwise positional scores inside the attention matrix, FastRPB introduces an additive bias term directly to the attention output: $$Y = \text{AttentionVariant}(Q, K, V) + WV$$ Here, $W$ is a matrix of learnable weights corresponding to token-to-token relative distances.

  3. 1D Sequences (Text): $W$ forms a Toeplitz matrix (constant diagonals). By embedding $W$ into an extended circulant matrix, the matrix-vector multiplication $W V$ can be computed via the Fast Fourier Transform (FFT) in $\mathcal{O}(DN \log N)$ time and $\mathcal{O}(N)$ memory.

  4. 2D Sequences (Images): The 2D distance between pixels decomposes into separable horizontal and vertical Toeplitz components, retaining $\mathcal{O}(DN \log N)$ complexity without storing full $N^2 \times N^2$ matrices.

Because FastRPB is additive and decoupled from attention calculation, it is universally plug-and-play across both vanilla and linear attention architectures.

Datasets

  • Long Range Arena (LRA): Evaluated across four long-sequence tasks:
  • ListOps: Parsing hierarchical mathematical expressions (sequence lengths up to 2K).
  • Text Classification (TC): Sentiment analysis on byte-level IMDb movie reviews (up to 4K tokens).
  • All About NLP (AAN): Long-document scientific paper retrieval and matching (up to 4K tokens).
  • CIFAR-10: Pixel-by-pixel image classification (sequence length 1024).
    (Note: The synthetic Pathfinder task was omitted due to baseline reproducibility issues.)
  • MNIST: Image classification using an 8-layer Transformer to test FastRPB 2D on deeper networks.

Key Insights and Ideas

  • Toeplitz Structures Bridge Position and FFT: Because 1D and 2D relative distance matrices depend only on coordinate differences $(m - n)$, they are inherently Toeplitz. Embedding them into circulant matrices allows circular convolutions via FFT, circumventing the quadratic bottleneck entirely.
  • Independence from Attention Formulation: Decoupling positional bias from the query-key dot product avoids modifying the attention denominator, making it easy to drop into any existing linear or sparse Transformer.
  • Text Hierarchies vs. Positional Bias: Learned weights reveal task-specific structures—for example, on scientific texts (AAN), FastRPB learns to focus heavily on document ends (conclusions). Conversely, relative positional encodings actually degrade performance on tree-structured syntax tasks like ListOps, where structural hierarchy matters more than raw linear token distance.

Key Results

  • Speed & Memory Footprint:
  • FastRPB trains up to $30\times$ faster than convSPE and up to $3\times$ faster than sinSPE on LRA tasks.
  • On image tasks (MNIST), Linear Transformers with FastRPB consumed up to $10\times$ less memory and achieved $5\times$ faster evaluation speed compared to vanilla Transformers.
  • Accuracy Gains:
  • On LRA AAN, Linear SIKF + FastRPB achieved 67.19% accuracy, outperforming all linear baselines (~59–64%) and standard Transformers (which failed with Out-of-Memory errors).
  • On MNIST, adding FastRPB consistently improved all models: vanilla Transformer improved from 97.34% to 98.27%, and Linear SIKF improved from 96.49% to 97.37%.

Limitations and Future Work

  • Performance Drop on Single-Layer CIFAR-10: FastRPB underperformed convSPE on the LRA 1D flattened CIFAR-10 task, which authors hypothesize is due to the single-layer architecture specified by the LRA benchmark.
  • Hierarchical Tasks: As observed in ListOps, flat relative distance does not capture nested or tree-like syntax well. Future work could extend fast Fourier-based biases to hierarchical or tree-structured positional embeddings.

Summary updated

Abstract

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 input’s 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 $\textbf{S}$hift-$\textbf{I}$nvariant $\textbf{K}$ernel $\textbf{F}$unction $\textbf{SIKF}$, which achieve higher accuracy without loss in speed. Secondly, we introduce $\textbf{FastRPB}$ which stands for $\textbf{Fast}$ $\textbf{R}$elative $\textbf{P}$ositional $\textbf{B}$ias, 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 $\mathcal{O}(N\log{N})$ computational complexity, requiring $\mathcal{O}(N)$ memory w.r.t. input sequence length $N$. We compared introduced modifications with recent Linear Transformers in different settings: text classification, document retrieval, and image classification. Extensive experiments with FastRPB and SIKF demonstrate that our model significantly outperforms another efficient positional encodings method in accuracy, having up to x1.5 times higher speed and requiring up to x10 times less memory than the original Transformer.
BibTeX
@inproceedings{zubkov2022fastrpb,
  author = {Maksim Zubkov and Daniil Gavrilov},
  title = {{FastRPB: a Scalable Relative Positional Encoding for Long Sequence Tasks}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=N2nJzgb_ldR},
}

Loading related content...

Figure