Scaling Transformer models to handle very long sequences is a persistent challenge in machine learning. While recent advances have introduced "linear-complexity" Transformers, these models often sacrifice a crucial component for high performance: Relative Positional Encoding (RPE).
This paper introduces Stochastic Positional Encoding (SPE), a novel method that successfully integrates RPE into linear-complexity Transformers. By framing positional kernels as cross-covariance structures of Gaussian processes, SPE allows models to capture the relative distances between tokens without ever explicitly computing the computationally expensive $O(N^2)$ attention matrix.
The Bottleneck: Linear Complexity vs. Relative Position
Standard Transformers suffer from quadratic complexity. As the sequence length $N$ grows, the memory and time required to compute the attention matrix grow by $N^2$. "Linear Transformers" (such as the Performer or Linformer) bypass this bottleneck by using kernel tricks to approximate attention in $O(N)$ time.
However, these linear variants struggle to incorporate Relative Positional Encoding. RPE is generally superior to Absolute Positional Encoding (APE) because it focuses on the relative distance between tokens (e.g., "the word three places ago") rather than their fixed, absolute index in a sequence. In standard Transformers, RPE is simply added directly to the $N \times N$ attention matrix. Because linear Transformers avoid computing that matrix entirely, they have historically been stuck using less effective absolute encodings. SPE bridges this exact gap.
Methods: Positional Attention as Covariance
The core breakthrough of the paper is treating the desired positional attention pattern as a covariance function.
- Mathematical Framing: The authors define a positional kernel $P(m, n)$ that represents how much position $m$ should attend to position $n$. They demonstrate that this can be represented as the expected value of the dot product of two random processes: $P(m, n) = \mathbb{E}[Q(m)K(n)]$.
- Stochastic Approximation: Instead of computing the full kernel, the model draws $R$ independent samples (replicas) from these random processes. Following the Law of Large Numbers, the average dot product of these samples approximates the desired relative positional kernel.
- Gated Integration: The authors include a learnable "gate" parameter. This allows the model to dynamically decide—for each head and layer—how much it should rely on positional information versus the actual semantic content of the tokens.
Crucially, because these encodings are applied directly to the Keys and Queries before the attention mechanism, the overall complexity remains strictly $O(N)$.
Two Variants of SPE
The authors propose two distinct ways to generate these stochastic processes, catering to different types of data:
- sineSPE: Uses sinusoidal components to create periodic attention patterns. This is highly effective for data with repeating structures, such as music or seasonal time series.
- convSPE: Uses convolutions on white noise to create "vanishing" attention, where tokens primarily attend to their immediate local neighborhood.
Key Results and Extrapolation
The authors evaluated SPE across diverse domains, including the Long-Range Arena (LRA) benchmark for efficient Transformers, Pop Piano Music Generation, and Groove Continuation.
- State-of-the-Art on LRA: SPE (specifically
sineSPE) achieved state-of-the-art results on the LRA "Retrieval" task, improving accuracy by ~3% over previous bests. It generally matched or slightly outperformed APE across other tasks. - Plug-and-Play Flexibility: The method proved compatible with different linear attention mechanisms, including the Softmax-based Performer and the ReLU-based Linear Transformer.
Extrapolation is the Killer App
One of the most significant weaknesses of Absolute Positional Encoding is its failure to generalize to sequences longer than those seen during training. Because SPE is relative and stochastic, it extrapolates remarkably well.
In piano music generation, models were trained on sequences of length 2,048. At inference time, APE models saw their performance (measured by cross-entropy) degrade immediately and catastrophically past the 2,048 mark. In contrast, SPE models maintained stable performance and preserved musical style even when generating sequences twice as long as their training data.
Limitations and Future Directions
While highly effective, SPE does have limitations. Because it relies on a Monte Carlo estimator, using too few replicas ($R$) can introduce noise that hinders performance. Additionally, while SPE was a clear winner in music generation, its advantages in some LRA benchmark tasks were more modest, suggesting that not all tasks require strong relative positioning.
Looking forward, the authors propose exploring "Signal-dependent PE," where the positional encoding dynamically adapts based on the input content, paving the way for even more complex and evolving attention patterns in linear time.
Summary updated