Abstract
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.
Introduction
Standard Transformers rely on an attention matrix that grows quadratically ($O(N^2)$) with sequence length, making them impractical for very long inputs. While "Linear Transformers" (e.g., Performer, Linformer) achieve $O(N)$ complexity by approximating the attention matrix using low-rank factorization, they struggle to incorporate Relative Positional Encoding (RPE). RPE is crucial for capturing the distance-based relationships (lags) between tokens, which often matter more than absolute positions. However, RPE typically requires the full $O(N^2)$ matrix, defeating the purpose of linear efficiency. This paper introduces Stochastic Positional Encoding (SPE) to bridge this gap, providing RPE-like benefits within a linear-complexity framework.
Methods: Stochastic Positional Encoding
The core innovation of SPE is treating positional attention as a cross-covariance structure of random processes. Instead of deterministic vectors, SPE draws random samples from a distribution designed so that the expected value of their dot product approximates a desired relative attention pattern.
SPE Variants and Gating
The authors propose two primary variants:
sineSPE(Periodic Attention): Uses sinusoidal components to create non-vanishing patterns, ideal for repeating structures like music.convSPE(Vanishing Attention): Generates encodings by convolving white noise with learned filters, creating localized attention patterns suitable for text or images.
To integrate these, a gating mechanism is used. A learned parameter $\delta$ allows each attention head to dynamically balance positional information against token content, enabling the model to switch between global and position-aware attention as needed.
Key Insights
- Positional Encoding as Covariance: SPE shifts the view of PE from adding coordinates to defining a covariance structure, allowing tools from signal processing to be used in attention design.
- Extrapolation Capability: Unlike Absolute Positional Encoding (APE), which often fails on sequences longer than those seen during training, SPE models degrade gracefully. They learn relative relationships that remain valid regardless of the absolute starting index.
- Regularization via Noise: The stochastic nature of the estimator does not hinder performance; in some cases, it acts as a regularizer that improves generalization.
Results and Performance
The authors evaluated SPE on the Long-Range Arena (LRA) benchmark and music generation tasks. In LRA, sineSPE combined with a Linear Transformer achieved a ~3% accuracy boost on the Retrieval task compared to previous state-of-the-art results.
As shown in the figure above, SPE variants significantly outperform APE in extrapolation. While APE's validation cross-entropy spikes immediately after the training limit, SPE models maintain much lower error rates, demonstrating superior generalization to unseen sequence lengths. In music tasks, this translated to higher style consistency and stability over time compared to the "drift" observed in APE models.
Conclusion
Stochastic Positional Encoding successfully brings the advantages of relative positioning to linear-complexity Transformers. By leveraging the mathematical properties of Gaussian processes, SPE enables efficient modeling of massive sequences with robust extrapolation capabilities. Future work may explore signal-dependent SPE, where positional encodings are conditioned on token content.
Summary updated