FastRPB: a Scalable Relative Positional Encoding for Long Sequence Tasks

Maksim Zubkov, Daniil Gavrilov

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 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.

Introduction

The self-attention mechanism, the cornerstone of the Transformer architecture, suffers from a quadratic $O(N^2)$ bottleneck in both computation and memory. This makes processing long sequences—such as high-resolution images or lengthy documents—prohibitively expensive. While "Linear Transformers" aim to reduce this complexity to $O(N)$ via kernel approximations, they often suffer from a significant drop in accuracy. This performance gap is largely attributed to poor kernel choices that fail to preserve the shift-invariance of softmax attention and the difficulty of incorporating relative positional information without re-introducing quadratic costs.

Methods

This work introduces two primary enhancements to the Linear Transformer framework:

Shift-Invariant Kernel Function (SIKF)

The authors propose using a simple exponential function, $\phi(x) = \exp(x)$, as the kernel for linear attention. This choice preserves the shift-invariance property of the original softmax attention—where adding a constant to inputs does not change the output distribution—without the computational overhead of complex random feature sampling methods like those used in Performer models.

Fast Relative Positional Bias (FastRPB)

FastRPB injects relative positional information by adding a bias matrix directly to the attention layer's output: $Y = \text{Attention}(Q, K, V) + WV$. To maintain efficiency, the authors exploit the Toeplitz structure of relative distance matrices. By utilizing the properties of circulant matrices and the Fast Fourier Transform (FFT), the matrix multiplication $WV$ is computed in $O(N \log N)$ time and $O(N)$ memory. This approach is orthogonal to the attention mechanism and can be applied to both standard and efficient Transformer variants.

Evaluation and Results

The proposed methods were evaluated on the Long Range Arena (LRA) benchmark, which includes tasks like ListOps, Text Classification (TC), All About NLP (AAN), and CIFAR10.

Performance and Scalability

FastRPB demonstrates superior scalability compared to standard Transformers and other linear positional encoding methods. As shown in the evaluation below, FastRPB maintains significantly lower memory consumption and higher throughput as sequence length increases.

Evaluation of memory consumption and time efficiency (samples per second) across different models and sequence lengths.

Task Accuracy

On the LRA benchmark, the combination of SIKF and FastRPB allows Linear Transformers to achieve accuracies comparable to or exceeding the original $O(N^2)$ Transformer, particularly on text-based tasks.

Comparison of accuracy across LRA tasks for various Transformer models and positional encoding schemes. Bold values indicate best performance.

Key results include:

  • Efficiency: FastRPB is up to 30x faster to train than previous linear positional encodings like convSPE and requires 1.5x less memory.
  • Accuracy: On AAN and TC tasks, Linear Transformers with FastRPB outperformed other efficient variants. While it underperformed on the single-layer CIFAR10 task in LRA, experiments on multi-layer MNIST architectures showed that FastRPB excels in deeper networks, achieving higher F1 scores with 10x less memory than the original Transformer.

Conclusion

FastRPB and SIKF provide a scalable and effective way to enhance Linear Transformers for long-sequence tasks. By leveraging FFT for $O(N \log N)$ relative positional encoding and a shift-invariant kernel, this approach bridges the gap between efficiency and accuracy in Transformer models.

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 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.
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},
}
Figure