Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers

ArXiv: 2302.01925

🎯 Pitch

Linear Transformers normally break when you add relative position encodings (RPEs), but this work shows you can learn the RPE's Fourier spectrum to inject positional awareness without ever materializing the quadratic mask—making RPE-enhanced linear attention practical for the first time on 3D molecular data, where prior methods simply cannot run.

---

1. Executive Summary

This paper introduces FourierLearner-Transformers (FLTs), a new class of linear-complexity Transformers that incorporate relative positional encoding (RPE) mechanisms into kernelized (Performer-style) attention by learning the spectral representation of the RPE function directly—sidestepping the explicit materialization of the RPE mask that would otherwise require quadratic memory. Evaluated across language modeling (WikiText-103), image classification (ImageNet, Places365, Fashion-MNIST), 3D molecular property prediction (OC20 IS2RE), and learnable optimizers, FLTs achieve both superior accuracy and practical efficiency: on WikiText-103, FLT with local RPE reaches 30.1 perplexity, outperforming the strongest prior RPE-enhanced linear Transformer baseline (log-linear Performer at 30.6) while using substantially less memory and forward time at long sequence lengths, and on molecular data—where existing RPE-enhanced linear attention methods are inapplicable due to the non-Toeplitz structure of 3D RPE masks—FLT reduces energy MAE by over 0.04 eV compared to a regular Performer, establishing that RPE-enhanced linear attention can scale to geometric data embedded in higher-dimensional Euclidean spaces only when the RPE mask is approximated via its Fourier transform rather than through structure-dependent factorization.

2. Context and Motivation

The Core Problem: Relative Positional Encodings Are Incompatible with Linear Attention

The fundamental tension this paper addresses is deceptively simple: how do you incorporate relative positional encodings (RPEs) into linear-complexity Transformers without breaking the linear complexity that makes them efficient in the first place? This is not a minor engineering inconvenience — it represents a genuine structural conflict between two of the most important advances in Transformer architecture design.

To understand the conflict, we need to appreciate what each mechanism does separately:

Linear attention (specifically kernelized attention, as in the Performer) achieves $O(Lmd)$ time complexity instead of the standard $O(L^2d)$ by never materializing the full $L \times L$ attention matrix. The trick is to decompose the attention computation using the associativity of matrix multiplication: instead of computing $\text{softmax}(QK^\top)V$ explicitly (which is $O(L^2d)$), one approximates $\text{softmax}(QK^\top) \approx \phi(Q)\phi(K)^\top$ using random feature maps $\phi$, then computes $\phi(Q)(\phi(K)^\top V)$ from right to left. The key word here is "implicitly" — the attention matrix never exists as a concrete object in memory, which is precisely what enables the $O(Lmd)$ cost.

Relative positional encoding (RPE) modifies the attention computation by adding a learned bias term to the attention scores that depends on the relative distance between tokens. Formally, an RPE-enhanced attention mechanism is defined as:

$\text{Att}(Q, K, V, N) = D^{-1}AV, \quad \text{where } A = \exp\left(N + \frac{QK^\top}{\sqrt{d}}\right)$

Here $N \in \mathbb{R}^{L \times L}$ is the RPE mask, where $N_{ij} = f(\mathbf{r}_i - \mathbf{r}_j)$ for some function $f$ and positional feature vectors $\mathbf{r}_i \in \mathbb{R}^\ell$. This formulation is highly general: for sequential text data, $\mathbf{r}_i = i$ (the token's index) and $f(i - j) = c_{i-j}$ (a learnable Toeplitz matrix); for 3D molecular data, $\mathbf{r}_i$ is the atom's 3D coordinate and $f$ encodes domain-specific geometric relationships.

Now the conflict emerges clearly: to apply the RPE mask $N$, you need to add it element-wise to $QK^\top/\sqrt{d}$ before applying the softmax, which requires — or seems to require — having the full $L \times L$ matrix available. The whole point of kernelized linear attention is to avoid materializing this matrix. Prior to this work, there was no general method for incorporating arbitrary RPE masks into linear attention that simultaneously maintained (a) linear complexity, (b) practical memory efficiency, and (c) applicability to RPE masks with non-Toeplitz structure (i.e., geometric data beyond sequences).

Why This Problem Matters

The significance of resolving this tension extends across multiple dimensions — practical, theoretical, and methodological.

Practical importance: RPEs are not optional. RPEs have become a standard component of state-of-the-art Transformers precisely because they provide a powerful inductive bias for capturing spatial and sequential relationships. The paper cites substantial evidence for this: RPEs improve performance on long-range language modeling (Dai et al., 2019), speech processing (Liutkus et al., 2021), vision tasks (Wu et al., 2021), and genomic data analysis (Žiga Avsec et al., 2021). Section 1 explicitly states that RPEs "play a critical role in improving the performance of Transformers in long-range modeling." Any linear-attention architecture that fails to incorporate RPEs is therefore operating at a fundamental representational disadvantage compared to quadratic-attention Transformers — it may be faster, but it's also less capable.

This creates an uncomfortable choice for practitioners: (1) use standard quadratic attention with RPEs but face $O(L^2)$ scaling that prohibits long sequences, (2) use linear attention without RPEs, sacrificing accuracy for efficiency, or (3) use one of the existing RPE-enhanced linear attention methods (discussed below), each of which imposes restrictive assumptions about the RPE structure. None of these options is satisfactory, which means there is a genuine deployment gap for applications requiring both long-sequence processing and rich positional understanding — such as document-level NLP, high-resolution image analysis, or molecular dynamics where tens of thousands of atoms must interact in a single attention operation.

Theoretical importance: bridging two parallel research threads. The paper identifies that the Transformer efficiency community has largely bifurcated into two largely non-interacting camps. One camp develops better linear attention mechanisms (Performers, CosFormer, linear attention with elu features) but treats RPEs as an afterthought or ignores them entirely. The other camp develops sophisticated RPE techniques within the standard quadratic-attention framework. The inability to combine these advances creates a theoretical bottleneck: progress in linear attention and progress in positional encoding are not composable, which means the field as a whole advances more slowly than it could if these components were modular.

This paper's approach — learning the spectral representation of the RPE function via its Fourier transform — provides a composable solution that could, in principle, enable any RPE function $f$ to be plugged into any kernelized attention mechanism without structural constraints. This changes the architectural landscape from "linear attention OR RPEs" to "linear attention AND RPEs," which is the natural state if we believe both techniques are independently valuable.

Methodological importance: enabling whole new classes of applications. The paper makes the specific claim (Section 5.3) that FLTs are "the first Transformer architectures providing linear attention and incorporating RPE masking" for 3D molecular data. This is not just bragging — it represents a genuine expansion of what's computationally feasible. In molecular modeling, the number of atoms $L$ can be large (thousands of atoms in a protein, millions in a materials simulation), and the RPE mask $N_{ij} = f(\mathbf{r}_i - \mathbf{r}_j)$ where $\mathbf{r}_i \in \mathbb{R}^3$ does not have the Toeplitz structure that prior methods exploit. Without a general RPE mechanism for linear attention, researchers studying these problems face a hard ceiling: either use quadratic attention with RPE (and suffer the $O(L^2)$ cost) or use linear attention without RPE (and lose the geometric inductive bias). FLTs break through this ceiling, making it practical to combine geometric priors with efficient attention for large-scale molecular modeling tasks — a capability that is directly relevant to drug discovery, materials science, and catalysis.

Where Existing Approaches Fall Short

The paper's literature review in Section 2 identifies three families of prior attempts to reconcile linear attention with RPEs, each with specific failure modes.

Attempt 1: SineSPE and ConvSPE (Liutkus et al., 2021). These were among the first attempts to address the problem head-on. Both variants model the RPE mask as a stationary position kernel with a Toeplitz mask structure. The insight is that for sequential data, $f(i - j) = c_{i-j}$ depends only on the relative offset, and this structure can be exploited for efficient computation. SineSPE represents the RPE mask via sinusoidal components, while ConvSPE uses learnable convolution filters.

The limitations are threefold:

• Extra computational dependency: The complexity, while still linear in $L$, introduces an additional factor depending on the number of sinusoidal components $T$ (for sineSPE) or the convolution filter length $P$ (for convSPE). The paper notes that "in practice, $T$ or $P$ has to be sufficiently small due to computational budgets," which constrains the expressiveness of the RPE model.
• Kernel matrix assumption: Both methods assume the RPE mask $N$ is a valid kernel matrix (positive definite). FLTs do not require this assumption — $f$ can be any function for which a Fourier transform exists, including functions that produce non-PSD or even non-symmetric masks.
• Fundamental inapplicability to non-sequential data: The Toeplitz structure is specific to sequential data where $\mathbf{r}_i$ are one-dimensional indices. For 3D molecular data where $\mathbf{r}_i \in \mathbb{R}^3$, the RPE mask depends on pairwise Euclidean distances between coordinates and does not have a Toeplitz structure. These methods simply cannot be applied to such data — which excludes an entire class of important applications.

The empirical results confirm these limitations: on WikiText-103 (Table 1), Performer-sineSPE achieves 38.0 perplexity and Performer-convSPE achieves 37.8 — both substantially worse than the regular Performer (31.1) without any RPE. The attempted RPE integration actually hurt performance, suggesting the constrained RPE representation was doing more harm than good.

Attempt 2: Log-Linear Performer (Luo et al., 2021; Choromanski et al., 2022a). A more sophisticated approach observes that linear attention can incorporate RPEs in $O(L \log L)$ time if the exponentiated RPE mask supports fast matrix-vector multiplication. For sequential data with a Toeplitz RPE mask, this holds because Toeplitz matrix-vector multiplication can be accelerated via the Fast Fourier Transform (FFT).

This method is the strongest prior baseline in terms of model quality, achieving 30.6 perplexity on WikiText-103 (Table 1) — close to FLT's 30.1–30.3. However, it has critical practical limitations:

• Large memory consumption: The paper explicitly states (Section 2) that this method "has large space complexity and high memory consumption in practice." The empirical comparison in Figure 1 shows that at sequence length 32,768, the log-linear Performer's peak memory is roughly 6–7× higher than FLT's (approximately 25 GB vs. 4–5 GB). This memory cost can be prohibitive for real hardware.
• Ongoing dependency on Toeplitz structure: The FFT-based acceleration fundamentally relies on the Toeplitz property of the RPE mask for sequential data. As with SineSPE/ConvSPE, this renders the method inapplicable to molecular data or any geometric setting where positions are not one-dimensional indices.
• Implementation complexity: The FFT-based approach requires careful handling of circulant embeddings and can be sensitive to implementation details.

In essence, the log-linear Performer trades space for time: it achieves $O(L \log L)$ forward time but with substantial memory overhead relative to pure linear attention. FLT's core claim is that it achieves both better accuracy and better practical memory efficiency while also generalizing beyond sequential data.

Attempt 3: Standard Performers without RPE (and other linear attention variants). The simplest approach is to simply omit RPEs entirely and rely on kernelized attention alone. While the regular Performer achieves competitive performance (31.1 perplexity on WikiText-103, better than sineSPE and convSPE with their constrained RPEs), it leaves a clear performance gap relative to architectures that successfully incorporate RPEs. The 1.0 perplexity point gap between the regular Performer (31.1) and FLT with local RPE (30.1) on WikiText-103 — a standard benchmark with relatively short sequences of length 512 — suggests that even in relatively simple sequential settings, omitting RPE leaves meaningful accuracy on the table. One would expect this gap to widen substantially on tasks requiring truly long-range positional reasoning, where inductive biases about relative positions become more critical.

The deeper pattern: all prior methods impose structural constraints on the RPE mask. The unifying limitation across all prior attempts is that each exploits specific structural properties of the RPE mask to achieve efficiency, and these properties are increasingly restrictive as we move from SineSPE/ConvSPE (requires Toeplitz and positive definiteness) to log-linear Performers (requires Toeplitz and fast matrix-vector multiplication) to pure Performers (no RPE at all). None of these methods provides a general mechanism for incorporating arbitrary RPE functions — particularly those defined on positions embedded in $\mathbb{R}^\ell$ for $\ell > 1$ — into linear-complexity attention.

How This Paper Positions Itself

The paper positions FLTs not as an incremental improvement to any single prior method, but as a change in representational strategy that renders the entire structural-constraint problem irrelevant.

The key insight: work in the spectral domain. Rather than trying to make the RPE mask $N$ support fast operations in the spatial domain (which is what prior methods attempt, each with their own structural assumptions), FLTs approximate $N$ via a low-rank decomposition derived from the Fourier transform of the RPE function $f$. Specifically, Theorem 4.1 shows that if $g$ is the Fourier transform of $f$, then for any probability density $p$:

$f(\mathbf{r}_i - \mathbf{r}_j) = \mathbb{E}_{\xi \sim p}\left[e^{2\pi i (\mathbf{r}_i - \mathbf{r}_j)^\top \xi} \frac{g(\xi)}{p(\xi)}\right]$

This expectation can be estimated using $r$ Monte Carlo samples $\xi_1, \ldots, \xi_r \sim p$, yielding a rank-$r$ decomposition $\hat{N} = N_1 N_2^\top$ where $N_1, N_2 \in \mathbb{R}^{L \times r}$. Crucially, this decomposition is always valid — it requires no structural assumptions about $N$ (not Toeplitz, not positive definite, not even symmetric). The only requirement is that $f$ has a Fourier transform, which is an extremely mild condition satisfied by essentially all practical RPE functions.

Once $N$ is approximated as $N_1 N_2^\top$, the RPE-enhanced attention computation can be folded into the standard Performer pipeline by concatenating the RPE feature maps with the query and key features:

$\hat{Q} = [N_1, Qd^{-1/4}], \quad \hat{K} = [N_2, Kd^{-1/4}]$

The attention becomes $\exp(\hat{Q}\hat{K}^\top)$, which is exactly the form that Performers linearize. This requires no new algorithms — just a feature concatenation that costs $O(Lrd)$ additional time, preserving the overall linear complexity.

Learning $g$ rather than $f$. The second key innovation — and the source of the name "FourierLearner" — is that rather than trying to specify $f$ explicitly and then compute its Fourier transform $g$ analytically (which would be cumbersome and potentially intractable for complex RPE functions), FLTs directly learn the spectral representation $g$ via differentiable parameters. This is a clever inversion of the usual logic: instead of defining what $f$ should look like in the spatial domain and deriving $g$ as a byproduct, FLTs define a parameterized spectral function $g_\theta$ and let gradient descent find the $g$ that produces the most useful $f$ for the task. The paper emphasizes this point explicitly: "instead of learning $f$ and trying to compute its Fourier Transform $g$ for the low-rank decomposition of $N$, we propose to directly learn $g$" (Section 4.1).

This is more than an implementation convenience — it's a genuinely different approach to designing positional encoding mechanisms. By learning in the spectral domain, the model can discover frequency-based representations that might be non-obvious in the spatial domain, and the parameter count for $g$ (fewer than 0.03M in all experiments, as the paper notes) does not scale with sequence length, only with the complexity of the spectral representation itself.

Generalizing beyond sequential data through abstract positions. The paper's Definition 3.1 introduces a formulation of RPEs that is notably more general than what is typically assumed in the literature. The position of each token is represented by an abstract vector $\mathbf{r}_i \in \mathbb{R}^\ell$, where $\ell$ can be 1 (sequential indices), 3 (molecular coordinates), or any other dimensionality. The RPE function $f: \mathbb{R}^\ell \to \mathbb{R}$ takes the difference $\mathbf{r}_i - \mathbf{r}_j$ and produces a scalar. This generality is what enables FLTs to apply to "not only sequential data (e.g., texts) but also geometric data embedded in higher-dimensional Euclidean spaces" — a capability that the paper explicitly claims as novel and that the molecular modeling experiments are designed to validate.

The theoretical foundation. The paper provides formal guarantees that the spectral approximation is not just heuristically motivated but theoretically sound. Theorem 4.2 states that with $r = \Theta\left(\frac{c^2}{\varepsilon^2} \log \frac{L}{\delta}\right)$ random features, the approximation error satisfies $\|\hat{N} - N\|_{\max} \leq \varepsilon$ with probability at least $1 - \delta$, where $c = \|\|g(x)|/p(x)\|_\infty$ is a constant that does not depend on $L$. The logarithmic dependence on $L$ is particularly important — it means that as sequence length grows, the number of random features needed for a given approximation quality grows only logarithmically, not linearly or polynomially. This provides a theoretical justification for why FLTs can remain both accurate and efficient at scale: the rank $r$ of the RPE approximation needs to be only moderately larger for much longer sequences.

What FLTs do NOT require, in contrast to prior methods:

• No requirement that $N$ be a valid positive definite kernel matrix (unlike SineSPE/ConvSPE)
• No requirement that $N$ have Toeplitz structure or any other specific matrix structure (unlike log-linear Performer)
• No requirement that positions be one-dimensional indices (unlike all prior RPE-enhanced linear attention methods)
• No FFT-based acceleration or other structure-dependent computational tricks

What FLTs DO require:

• The ability to sample from a probability distribution $p$ over $\mathbb{R}^\ell$ and evaluate its density (the paper uses Gaussian distributions, which satisfy this trivially)
• The ability to evaluate the learned function $g_\theta$ at sampled frequencies $\xi$ (a standard forward pass through whatever neural network parameterizes $g$)
• The function $f$ must have a Fourier transform (a mild condition satisfied by essentially all practical RPE functions)

The combination of (a) theoretical guarantees on approximation quality, (b) a general formulation that removes all structural assumptions about the RPE mask, (c) a learnable spectral representation that avoids manual design of $f$, and (d) empirical results showing both accuracy gains and practical memory/throughput benefits across four diverse domains, positions FLTs as more than just "another linear attention mechanism with RPEs." The paper frames it as a unifying framework that subsumes existing approaches as special cases (e.g., shift-invariant kernel RPEs correspond to specific choices of $g$) while extending to regimes where no prior method works (3D geometric data). This is the core intellectual contribution: not a better optimization of an existing approach, but a reframing of how linear attention and RPEs can be composed at all.

3. Technical Approach

3.1 Reader Orientation

FLT is a drop-in replacement for the attention module in a Transformer that lets the model use relative positional encodings (RPEs) while keeping the computational cost linear in sequence length — something that was previously impossible for general RPEs. The system solves the problem by learning the RPE function in the frequency domain rather than in the spatial domain: instead of trying to compute a full $L \times L$ RPE mask $N$ and add it to the attention scores (which costs $O(L^2)$), FLT approximates $N$ as a low-rank product $N_1 N_2^\top$ where $N_1, N_2 \in \mathbb{R}^{L \times r}$ are constructed from random Fourier features, and $r \ll L$ is a tunable rank parameter. This low-rank decomposition folds directly into the existing Performer pipeline by concatenating the RPE feature maps with the query and key features — the model never materializes $N$, never pays $O(L^2)$, and can learn the optimal RPE function for the task through gradient descent on the spectral representation.

3.2 Big-Picture Architecture (Diagram in Words)

The FLT attention module has five conceptual components, though three of them are learned together end-to-end:

1. Positional feature vectors $\mathbf{r}_i \in \mathbb{R}^\ell$ — Each token in the input sequence is assigned a position vector that encodes where it "is" in whatever space makes sense for the data modality. For text, $\mathbf{r}_i = i$ (the 1D index). For 3D molecules, $\mathbf{r}_i$ is the atom's $(x, y, z)$ coordinate. These vectors are the inputs to the RPE mechanism.

2. The learned spectral function $g_\theta: \mathbb{R}^\ell \to \mathbb{C}$ — This is the core of FLT. Instead of defining the RPE function $f(\mathbf{r}_i - \mathbf{r}_j)$ directly in the spatial domain, FLT learns its Fourier transform $g_\theta$, parameterized by a small number of trainable parameters $\theta$. The function takes a frequency vector $\xi \in \mathbb{R}^\ell$ and returns a complex number. The paper explores several parameterizations: Gaussian mixtures, shift-invariant kernel forms, and local RPE forms (Section 4.3). At inference time, $g_\theta$ is evaluated at $r$ randomly sampled frequencies to construct the random feature maps.

3. Random frequency sampler with density $p$ — To estimate the Fourier integral via Monte Carlo, FLT samples $r$ frequency vectors $\xi_1, \ldots, \xi_r \sim p$ from a probability distribution $p$ over $\mathbb{R}^\ell$. The choice of $p$ affects approximation quality; the paper uses Gaussian distributions (zero-mean, unit variance or learnable variance) because they are easy to sample from and evaluate. These frequencies are fixed per forward pass but can be resampled across training iterations.

4. RPE feature map constructor ($\varphi, \psi$) — For each token position $\mathbf{r}_i$, FLT constructs two feature vectors $\varphi(\mathbf{r}_i), \psi(\mathbf{r}_i) \in \mathbb{C}^r$ by evaluating weighted complex exponentials at the sampled frequencies. Specifically, the $k$-th component of $\varphi(\mathbf{r}_i)$ is $\frac{1}{\sqrt{r}} e^{2\pi i \mathbf{r}_i^\top \xi_k} \sqrt{g_\theta(\xi_k)/p(\xi_k)}$, and $\psi(\mathbf{r}_i)$ uses the conjugate exponential $e^{-2\pi i \mathbf{r}_i^\top \xi_k}$. These vectors are stacked into matrices $N_1, N_2 \in \mathbb{R}^{L \times r}$.

5. Concatenated Performer attention — The RPE feature matrices $N_1$ and $N_2$ are concatenated with the scaled query and key matrices to form augmented matrices $\hat{Q} = [N_1, Qd^{-1/4}]$ and $\hat{K} = [N_2, Kd^{-1/4}]$. The attention computation $\exp(\hat{Q}\hat{K}^\top)$ now implicitly includes the RPE mask $N_1 N_2^\top$ added to the content-based attention $QK^\top/\sqrt{d}$. This augmented attention is then linearized using standard Performer random feature maps $\phi$, and the result is computed via the associativity trick $\phi(\hat{Q})(\phi(\hat{K})^\top V)$.

Information flow: Input sequence → positional features $\mathbf{r}_i$ → sample frequencies $\xi_k \sim p$ → evaluate $g_\theta(\xi_k)$ → construct $\varphi(\mathbf{r}_i)$ and $\psi(\mathbf{r}_i)$ → form $N_1, N_2$ → concatenate with $Q, K$ → apply Performer linearization → compute linear attention output. Everything is differentiable with respect to $g_\theta$'s parameters, the query/key/value projections, and any parameters of $p$ if it is learned.

3.3 Roadmap for the Deep Dive

• First, the formal problem statement — we need to see exactly what RPE-enhanced attention looks like mathematically (Definition 3.1) and why it resists linearization, to understand what FLT must approximate.
• Second, the unbiased low-rank decomposition of the RPE mask (Theorem 4.1) — this is the mathematical engine of FLT: how Fourier analysis converts any RPE function into a rank-$r$ product of random feature matrices.
• Third, the FLT attention algorithm (Algorithm 1) — how the low-rank RPE approximation is woven into the Performer pipeline through feature concatenation, and what the resulting time/space complexity is.
• Fourth, the theoretical guarantees (Theorem 4.2) — why this approximation is reliable: uniform convergence bounds and the critical $\log L$ dependence of the required rank on sequence length.
• Fifth, the parameterizations of $g_\theta$ (Section 4.3) — the concrete design choices for the spectral function: Gaussian mixtures, shift-invariant kernels, and local RPEs, and why each satisfies specific inductive biases.
• Sixth, practical considerations — how $p$, $r$, and the structure of $g_\theta$ are chosen in practice, and how the total parameter count stays under 0.03M regardless of sequence length.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a methods paper whose core innovation is a technique for approximating an arbitrary RPE mask via its Fourier transform, enabling linear-complexity RPE-enhanced attention without structural assumptions on the mask. The key insight is to work in the spectral domain — learning the Fourier transform $g$ of the RPE function $f$ rather than $f$ itself — because the Fourier integral representation immediately yields a Monte Carlo low-rank decomposition that integrates seamlessly with kernelized attention.

---

Formal Problem: RPE-Enhanced Attention and Why It Is Quadratic

The paper begins by precisely defining what RPE-enhanced attention computes (Definition 3.1), because everything that follows is an efficient approximation of this computation.

Consider an input sequence $X \in \mathbb{R}^{L \times d_{\text{in}}}$ with $L$ tokens of embedding size $d_{\text{in}}$. The self-attention module linearly projects $X$ into three matrices:

$Q, K, V \in \mathbb{R}^{L \times d}$

where $Q$ are queries, $K$ are keys, $V$ are values, and $d$ is the per-head dimension. Each token $i$ is also associated with a positional feature vector $\mathbf{r}_i \in \mathbb{R}^\ell$, where the dimensionality $\ell$ depends on the data modality: $\ell = 1$ for text (the token index), $\ell = 3$ for 3D molecular structures (atom coordinates), and could be any dimension for other geometric data.

The RPE mask. An RPE function $f: \mathbb{R}^\ell \to \mathbb{R}$ maps the relative position difference $\mathbf{r}_i - \mathbf{r}_j$ to a scalar $f(\mathbf{r}_i - \mathbf{r}_j)$. These scalars are arranged into the RPE mask:

$N = [f(\mathbf{r}_i - \mathbf{r}_j)]_{i,j \in [L]} \in \mathbb{R}^{L \times L}$

The RPE-enhanced attention is then defined as:

$\text{Att}(Q, K, V, N) = D^{-1} A V, \quad \text{where } A = \exp\left(N + \frac{QK^\top}{\sqrt{d}}\right), \quad D = \text{diag}(A \mathbf{1}_L)$

where $\exp(\cdot)$ is applied element-wise, $\mathbf{1}_L$ is the all-ones vector of length $L$, and $\text{diag}(\cdot)$ constructs a diagonal matrix from its input vector.

Why this is expensive. The matrix $A \in \mathbb{R}^{L \times L}$ must be explicitly materialized to compute the sum of each row (for the denominator $D$) and the product with $V$. Constructing $A$ requires computing $L^2$ entries, each costing $O(d)$ for the dot product $Q_i K_j^\top$ plus $O(1)$ for the RPE lookup and exponentiation. The total time complexity is $O(L^2 d)$, and the space complexity is $O(L^2 + Ld)$ — the $L^2$ term for the attention matrix dominates for long sequences.

The kernelized attention solution (without RPE). The Performer addresses the case $N = 0$ (no RPE) by linearizing the softmax kernel. For any feature map $\phi: \mathbb{R}^d \to \mathbb{R}^m$ satisfying $\exp(x^\top y) \approx \phi(x)^\top \phi(y)$, the attention can be rewritten using the associativity of matrix multiplication:

$\widehat{\text{Att}}_K(Q, K, V) = \hat{D}^{-1} \left(Q' (K'^\top V)\right), \quad \text{where } \hat{D} = \text{diag}\left(Q' (K'^\top \mathbf{1}_L)\right)$

Here $Q', K' \in \mathbb{R}^{L \times m}$ are matrices whose rows are $\phi(q_i^\top d^{-1/4})^\top$ and $\phi(k_i^\top d^{-1/4})^\top$ respectively. The key efficiency is that the parenthesized computation $(K'^\top V)$ produces an $m \times d$ matrix in $O(Lmd)$ time, and then $Q'$ multiplies this to produce an $L \times d$ output in another $O(Lmd)$ time. The space complexity drops to $O(Lm + md + Ld)$, linear in $L$ when $m \ll L$. The critical point: the $L \times L$ attention matrix is never materialized as a concrete object.

The conflict. When $N \neq 0$, the exponentiated sum $\exp(N + QK^\top/\sqrt{d})$ does not factorize as a simple inner product of per-token feature vectors — at least not in any obvious way. You cannot write $\exp(N_{ij} + q_i^\top k_j / \sqrt{d})$ as $\phi(q_i)^\top \psi(k_j)$ for some $\phi, \psi$ that depend only on individual tokens, because $N_{ij}$ depends on the pair $(i, j)$ and cannot be attributed to either token alone. The entire Performer speedup relies on this pairwise factorization, so breaking it means going back to $O(L^2)$.

The generality of Definition 3.1. The paper emphasizes that this formulation is "highly general" and novel in its scope. For sequential text data, one sets $\mathbf{r}_i = i$ and $f(i - j) = c_{i-j}$, producing a learnable Toeplitz RPE mask (as in T5). For 3D molecular data, one sets $\mathbf{r}_i$ as atom coordinates and defines $f$ using domain-specific functions like Gaussian basis functions. The paper claims this general formulation is important because it "motivates the highly general FLTs applicable to a wide range of data and tasks, as opposed to existing approaches that heavily rely on the structure of sequential data and Toeplitz RPE masks" (end of Section 3).

---

The Mathematical Core: Unbiased Low-Rank Decomposition of the RPE Mask via Fourier Transform

Theorem 4.1 provides the mathematical engine that powers FLT: any RPE function $f$ with a Fourier transform can be expressed as an expectation over complex exponentials, and this expectation can be estimated with $r$ Monte Carlo samples to produce an unbiased, low-rank approximation of the full RPE mask $N$.

Setup. Let $f: \mathbb{R}^\ell \to \mathbb{R}$ be the RPE function, and let $g: \mathbb{R}^\ell \to \mathbb{C}$ be its Fourier transform, defined by:

$g(\xi) = \int_{\mathbb{R}^\ell} f(\mathbf{x}) e^{-2\pi i \mathbf{x}^\top \xi} d\mathbf{x}$

The inverse Fourier transform relationship recovers $f$ from $g$:

$f(\mathbf{x}) = \int_{\mathbb{R}^\ell} e^{2\pi i \mathbf{x}^\top \xi} g(\xi) d\xi$

For the RPE mask entry at position $(i, j)$, we want $f(\mathbf{r}_i - \mathbf{r}_j)$, which equals:

$f(\mathbf{r}_i - \mathbf{r}_j) = \int_{\mathbb{R}^\ell} e^{2\pi i (\mathbf{r}_i - \mathbf{r}_j)^\top \xi} g(\xi) d\xi$

Introducing the sampling distribution. The integral over $\mathbb{R}^\ell$ cannot be computed exactly for arbitrary $g$, so FLT rewrites it as an expectation. Let $p$ be any probability density function supported over $\mathbb{R}^\ell$ (meaning $p(\xi) \geq 0$ for all $\xi$ and $\int p(\xi) d\xi = 1$, with $p(\xi) > 0$ wherever $g(\xi) \neq 0$). Multiply and divide the integrand by $p(\xi)$:

$f(\mathbf{r}_i - \mathbf{r}_j) = \int_{\mathbb{R}^\ell} e^{2\pi i (\mathbf{r}_i - \mathbf{r}_j)^\top \xi} \frac{g(\xi)}{p(\xi)} p(\xi) d\xi = \mathbb{E}_{\xi \sim p}\left[e^{2\pi i (\mathbf{r}_i - \mathbf{r}_j)^\top \xi} \frac{g(\xi)}{p(\xi)}\right]$

This is a standard importance-sampling rewriting: instead of integrating over the original measure, we sample frequencies $\xi$ from $p$ and weight the integrand by $g(\xi)/p(\xi)$.

Monte Carlo estimation. Sample $r$ independent frequency vectors $\xi_1, \ldots, \xi_r \sim p$. For each frequency $\xi_k$, define a pair of scalar random features for a token at position $\mathbf{r}_i$:

• The forward feature: $\frac{1}{\sqrt{r}} \cdot e^{2\pi i \mathbf{r}_i^\top \xi_k} \cdot \sqrt{\frac{g(\xi_k)}{p(\xi_k)}}$
• The conjugate feature: $\frac{1}{\sqrt{r}} \cdot e^{-2\pi i \mathbf{r}_i^\top \xi_k} \cdot \sqrt{\frac{g(\xi_k)}{p(\xi_k)}}$

Note the square root in the weight — this ensures that when the forward feature at position $i$ is multiplied by the conjugate feature at position $j$, the weights combine to $g(\xi_k)/p(\xi_k)$ rather than $(g(\xi_k)/p(\xi_k))^2$. The factor $1/\sqrt{r}$ normalizes the sum over $r$ samples to produce an average rather than a sum.

Matrix formulation. Stack these features for all $r$ frequencies into vectors $\varphi(\mathbf{r}_i), \psi(\mathbf{r}_j) \in \mathbb{C}^r$:

$\varphi(\mathbf{z}) = \frac{1}{\sqrt{r}} \left(e^{2\pi i \mathbf{z}^\top \xi_1} \sqrt{\frac{g(\xi_1)}{p(\xi_1)}}, \ldots, e^{2\pi i \mathbf{z}^\top \xi_r} \sqrt{\frac{g(\xi_r)}{p(\xi_r)}}\right)^\top$

$\psi(\mathbf{z}) = \frac{1}{\sqrt{r}} \left(e^{-2\pi i \mathbf{z}^\top \xi_1} \sqrt{\frac{g(\xi_1)}{p(\xi_1)}}, \ldots, e^{-2\pi i \mathbf{z}^\top \xi_r} \sqrt{\frac{g(\xi_r)}{p(\xi_r)}}\right)^\top$

Now define the full matrices for all $L$ tokens:

$N_1 = [\varphi(\mathbf{r}_1), \ldots, \varphi(\mathbf{r}_L)]^\top \in \mathbb{R}^{L \times r}$

$N_2 = [\psi(\mathbf{r}_1), \ldots, \psi(\mathbf{r}_L)]^\top \in \mathbb{R}^{L \times r}$

The key result. The inner product of the $i$-th row of $N_1$ and the $j$-th row of $N_2$ is:

$\varphi(\mathbf{r}_i)^\top \psi(\mathbf{r}_j) = \frac{1}{r} \sum_{k=1}^r e^{2\pi i (\mathbf{r}_i - \mathbf{r}_j)^\top \xi_k} \frac{g(\xi_k)}{p(\xi_k)}$

This is exactly the $r$-sample Monte Carlo estimate of $\mathbb{E}_{\xi \sim p}[e^{2\pi i (\mathbf{r}_i - \mathbf{r}_j)^\top \xi} g(\xi)/p(\xi)]$, which equals $f(\mathbf{r}_i - \mathbf{r}_j)$ by the integral representation. Since this holds for all $(i, j)$ pairs simultaneously, we have:

$\mathbb{E}[N_1 N_2^\top] = N$

where the expectation is taken over the random draws of $\xi_1, \ldots, \xi_r \sim p$.

Why this works for ANY $f$. The derivation uses only two properties: (a) $f$ has a Fourier transform $g$ (which is true for any integrable function, essentially all functions used in practice), and (b) $p$ is a valid density with support covering the support of $g$ (to avoid division by zero in $g(\xi)/p(\xi)$). There is no assumption that $N$ is Toeplitz, symmetric, positive definite, or has any other structural property. The decomposition is universal — it works for sequential positions ($\ell = 1$), 3D coordinates ($\ell = 3$), and any $\ell > 0$. This universality is what distinguishes FLT from all prior methods, each of which required specific matrix structure.

What $r$ controls. The rank parameter $r$ governs the approximation quality: larger $r$ means more Monte Carlo samples and a lower-variance estimate of $N$. The cost of the RPE approximation scales as $O(L r)$ for constructing the feature maps and $O(L r d)$ for the downstream attention, so $r$ is the primary knob for trading accuracy against speed. Theorem 4.2 (discussed below) shows that $r$ needs to grow only logarithmically with $L$ to maintain a fixed approximation quality, which is the theoretical justification for FLT's scalability.

Practical handling of complex numbers. While the formulation uses complex exponentials, the paper does not elaborate on how real-valued networks handle complex features. The standard approach (implicit in Algorithm 1) is to split each complex feature into its real and imaginary parts, doubling the effective feature dimension from $r$ to $2r$. Alternatively, since $f$ is real-valued, one can use trigonometric random features ($\cos$ and $\sin$) which are real-valued but require twice as many features for the same variance. The paper's experiments treat $r$ as the number of complex features, so the effective dimension added to $\hat{Q}$ and $\hat{K}$ is $2r$ (real and imaginary parts concatenated).

---

The FLT Attention Algorithm: Folding RPE into Performer-Style Linear Attention

Once we have the low-rank decomposition $\hat{N} = N_1 N_2^\top$ where $\mathbb{E}[\hat{N}] = N$, the RPE-enhanced attention simplifies dramatically. The key observation (Equation 3 in the paper) is:

$\hat{A} \overset{\text{def}}{=} \exp\left(\hat{N} + \frac{QK^\top}{\sqrt{d}}\right) = \exp\left(\hat{Q} \hat{K}^\top\right)$

where the augmented matrices are constructed by column-wise concatenation:

$\hat{Q} = [N_1, Qd^{-1/4}] \in \mathbb{R}^{L \times (r + d)}$

$\hat{K} = [N_2, Kd^{-1/4}] \in \mathbb{R}^{L \times (r + d)}$

Why this concatenation works. The matrix product $\hat{Q}\hat{K}^\top$ expands as:

$\hat{Q}\hat{K}^\top = N_1 N_2^\top + (Qd^{-1/4})(Kd^{-1/4})^\top = \hat{N} + \frac{QK^\top}{\sqrt{d}}$

This is exactly the sum inside the exponential in the RPE-enhanced attention definition, with the true $N$ replaced by its low-rank estimate $\hat{N}$. The concatenation trick means that the RPE mask is not added as a separate step — it is embedded into the query and key representations before the attention computation, so the entire operation looks like standard softmax attention on augmented token features.

From here, standard Performer linearization applies. Let $\phi: \mathbb{R}^{r+d} \to \mathbb{R}^m$ be any random feature map satisfying $\exp(x^\top y) \approx \phi(x)^\top \phi(y)$. Apply $\phi$ row-wise to $\hat{Q}$ and $\hat{K}$ to obtain:

$Q' = \phi(\hat{Q}) \in \mathbb{R}^{L \times m}, \quad K' = \phi(\hat{K}) \in \mathbb{R}^{L \times m}$

The kernelized linear attention from Equation 2 then produces:

$\widehat{\text{Att}}_{\text{FLT}}(Q, K, V, N) = \hat{D}^{-1} \left(Q' (K'^\top V)\right)$

with the normalization $\hat{D} = \text{diag}(Q' (K'^\top \mathbf{1}_L))$.

Algorithm 1 in full detail. The pseudocode in the paper spells out the exact computational steps:

1. Construct RPE random features: Given positions $R \in \mathbb{R}^{L \times \ell}$ and the learned spectral function $g_\theta$, compute $N_1 \leftarrow \varphi(R)$ and $N_2 \leftarrow \psi(R)$ by applying the feature maps from Theorem 4.1 column-wise (each position gets its $r$-dimensional complex feature vector).
2. Concatenate with queries and keys: Form $\hat{Q} \leftarrow [N_1, Qd^{-1/4}]$ and $\hat{K} \leftarrow [N_2, Kd^{-1/4}]$ by concatenation along the second axis (the feature dimension).
3. Apply Performer random feature map: Compute $Q' \leftarrow \phi(\hat{Q})$ and $K' \leftarrow \phi(\hat{K})$ where $\phi$ is the chosen Performer feature map (e.g., positive random features $\phi(x) = \exp(Wx - \|x\|^2/2)/\sqrt{m}$ for Gaussian orthogonal random features, or a learnable ReLU map).
4. Compute linear attention output: First compute $B_1 \leftarrow Q'(K'^\top V)$ (an $L \times d$ matrix), then compute $B_2 \leftarrow Q'(K'^\top \mathbf{1}_L)$ (an $L$-dimensional vector), and finally $O \leftarrow \text{diag}(B_2)^{-1} B_1$.

Complexity analysis. The time and space complexities are stated in Section 4.1:

• Time complexity: $O(L(m + r)d)$, where $L$ is sequence length, $m$ is the Performer feature map dimension, $r$ is the number of RPE random features, and $d$ is the per-head dimension.
• Space complexity: $O(L(m + r) + (m + r)d + Ld)$, which is linear in all parameters.

To understand where these come from: the Performer maps $\hat{Q}$ and $\hat{K}$ from dimension $r+d$ to dimension $m$, which costs $O(L(m(r+d)))$ for the random projection; the product $K'^\top V$ costs $O(Lmd)$ (multiplying $m \times L$ by $L \times d$); the product $Q'(K'^\top V)$ costs another $O(Lmd)$; and storing $N_1, N_2, Q', K'$ takes $O(L(m+r))$ space. The $(m+r)$ factor replaces the $L$ factor in standard attention, yielding linear scaling when $m+r \ll L$.

Contrast with log-linear Performer. The paper highlights that the log-linear Performer (Luo et al., 2021) has time complexity $O(Lmd \log L)$ and space complexity $O(Lmd)$. While $O(L \log L)$ is still sub-quadratic, the extra $\log L$ factor and the large constant from FFT make it substantially less efficient in practice than FLT's $O(L(m+r)d)$. Figure 1 empirically confirms this: at sequence length 32,768, FLT's forward time is roughly 200–300 ms vs. 500+ ms for log-linear Performer, and FLT's peak memory is about 4–5 GB vs. 25+ GB.

No explicit attention matrix anywhere. At no point in Algorithm 1 is any $L \times L$ matrix constructed or stored. The RPE mask $N$ is approximated implicitly through the inner product $N_1 N_2^\top$, but even this product is never computed as a concrete matrix — it exists only as a term inside $\hat{Q}\hat{K}^\top$, which itself is never materialized because the Performer linearization directly computes the attention-times-value product.

---

Theoretical Guarantees: Uniform Convergence with Logarithmic Sample Complexity

The paper provides formal guarantees that the FLT RPE approximation does not silently degrade as sequence length grows. The key results are Theorem 4.2 (uniform convergence) and Theorem A.3 (variance bound), both proved in Appendix A.

Setup for the theoretical analysis. Let $g$ be the Fourier transform of the true RPE function $f$, and let $p$ be the chosen sampling density. Define the critical constant:

$c = \left\|\frac{|g(\xi)|}{p(\xi)}\right\|_\infty$

where $\|\cdot\|_\infty$ denotes the essential supremum — the maximum absolute value of the ratio $|g(\xi)|/p(\xi)$ over all $\xi \in \mathbb{R}^\ell$ (ignoring measure-zero sets). This constant captures how well $p$ matches the magnitude of $g$: if $p$ places high probability where $g$ is large, the ratio is well-controlled and $c$ is small; if $p$ is a poor match (putting high density where $g$ is near zero while having low density where $g$ peaks), $c$ can be large.

Variance bound (Theorem A.3). For any pair of positions $(\mathbf{r}_i, \mathbf{r}_j)$, the variance of the Monte Carlo RPE estimate satisfies:

$\text{Var}[\varphi(\mathbf{r}_i)^\top \psi(\mathbf{r}_j)] \leq \frac{c^2 - f(\mathbf{r}_i - \mathbf{r}_j)^2}{r}$

What this means: the variance of the approximation at any single matrix entry scales as $O(1/r)$ — doubling the number of random features halves the variance. The $c^2$ term represents the worst-case variance when $f$ is zero (off-diagonal entries far from the RPE function's peak), and the $-f^2$ term means that entries where $f$ is large have lower variance (which is desirable, as these are the entries that matter most for the attention mechanism). The proof (Appendix A.2) follows from the definition of variance for complex random variables and the bound $|e^{2\pi i z^\top \xi} g(\xi)/p(\xi)| \leq c$ that follows from the definition of $c$.

Uniform convergence bound (Theorem 4.2). The more powerful result concerns the worst-case deviation across all entries of the $L \times L$ RPE mask simultaneously:

$P\left(\|N - \hat{N}\|_{\max} \leq \varepsilon\right) > 1 - \delta$

provided that the number of random features satisfies:

$r = \Theta\left(\frac{c^2}{\varepsilon^2} \log \frac{L}{\delta}\right)$

where $\|\cdot\|_{\max}$ is the max norm (largest absolute value of any entry in the matrix).

What this computes: it gives the number of random features $r$ needed to guarantee that every single entry of the approximated RPE mask $\hat{N}$ is within $\varepsilon$ of the true RPE mask $N$ with probability at least $1 - \delta$. The proof (Appendix A.3) applies Hoeffding's inequality to each entry individually (using the boundedness condition from the variance bound), then takes a union bound over all $L^2$ entries, which introduces the $\log L$ term.

Why the $\log L$ dependence is critical. The required rank $r$ grows only logarithmically with sequence length $L$, not linearly or quadratically. This means that to maintain a fixed approximation quality $\varepsilon$ as $L$ increases:

• If $L$ grows from 1,000 to 1,000,000 (a 1,000× increase), $\log L$ grows by a factor of $\log(10^6)/\log(10^3) = 2$, so $r$ needs to only double.
• In contrast, if the dependence were $\Theta(L)$, scaling to 1,000× longer sequences would require 1,000× more features, defeating the purpose of linear attention.

This logarithmic dependence is what makes FLT practical for long sequences: the RPE approximation overhead grows sub-linearly with sequence length, so the dominant cost remains the $O(Lmd)$ attention computation rather than the $O(Lr)$ RPE feature construction.

Why the union bound is loose and what that implies. The union-bound proof gives $r = \Theta(\frac{c^2}{\varepsilon^2} \log L)$, but the paper notes in Appendix A.4 that "the $\log L$ factor in the sample complexity bound... is introduced for technical reasons: the convergence analysis is conducted for the random features applying exponential mapping which is not bounded." For trigonometric random features (which are bounded by 1), an $\varepsilon$-net argument combined with Lipschitz continuity can remove the $\log L$ factor, giving $r$ that is independent of $L$. The paper cites Choromanski et al. (2021) for this result. In practice, the logarithmic factor is negligible — for $L = 32,768$, $\log L \approx 10.4$, so even the loose bound only requires $r$ to be about 10× larger than the base requirement.

Optimal choice of $p$. The constant $c = \||g|/p\|_\infty$ directly governs the sample complexity: smaller $c$ means fewer features needed for the same accuracy. The paper notes (Appendix A.4) that the variance-optimal choice is $p(\xi) \propto |g(\xi)|$ — sampling frequencies proportionally to the magnitude of the Fourier transform. This minimizes $c$ under the constraint that $p$ is a probability density, because when $p \propto |g|$, the ratio $|g(\xi)|/p(\xi)$ is constant across all $\xi$, achieving the smallest possible supremum. For shift-invariant kernel RPEs (where $g$ is exactly a scaled probability density by Bochner's theorem), this optimal $p$ coincides with the kernel's spectral measure, giving $c = 1$ and the best possible sample complexity. The paper also explores learning $p$ as a Gaussian with learnable mean and variance (used in the molecular modeling experiments), which allows the optimizer to approximately approach the optimal $p$ within the Gaussian family.

---

Parameterizations of the Spectral Function $g_\theta$

The heart of FLT is the learned function $g_\theta: \mathbb{R}^\ell \to \mathbb{C}$ that represents the Fourier transform of the RPE function $f$. Section 4.3 presents several concrete parameterizations, each imposing different inductive biases on what kinds of RPEs the model can learn. The paper emphasizes that "nowhere in the analysis in Sec. 4.1 have we relied on any structural properties of $f$" — meaning that $f$ can be non-symmetric, non-positive-definite, or anything else, because the Fourier representation does not require such properties. However, the parameterization of $g$ determines the space of achievable RPE functions and should be chosen to match the task's needs.

Gaussian Mixture RPEs

The most general parameterization the paper explores is the Gaussian mixture form for $g$:

$g(\xi) = \sum_{t=1}^T w_t \exp\left(-\frac{\|\xi - \mu_t\|^2}{2\sigma_t^2}\right)$

where the learnable parameters are:

• $w_1, \ldots, w_T \in \mathbb{R}$ — scalar weights controlling the contribution of each Gaussian mode
• $\mu_1, \ldots, \mu_T \in \mathbb{R}^\ell$ — the centers of the Gaussian modes in frequency space
• $\sigma_1, \ldots, \sigma_T \in \mathbb{R}$ — the bandwidths (standard deviations) of the Gaussian modes

The total number of parameters for $g$ is $(2 + \ell)T$: $T$ weights, $T \cdot \ell$ center coordinates, and $T$ bandwidths. Since $T$ is typically small (the paper uses $T = 25$ for image classification), this is highly parameter-efficient.

What this parameterization does to $f$. The inverse Fourier transform of a Gaussian in the frequency domain is a Gaussian in the spatial domain (modulated by a complex exponential from the shift $\mu_t$). Specifically, the $t$-th mode $g_t(\xi) = w_t \exp(-\|\xi - \mu_t\|^2/(2\sigma_t^2))$ transforms to:

$f_t(\mathbf{x}) = w_t \cdot (\sqrt{2\pi}\sigma_t)^\ell \exp(-2\pi^2 \sigma_t^2 \|\mathbf{x}\|^2) \cdot e^{2\pi i \mu_t^\top \mathbf{x}}$

Summing over $t$ gives $f$ as a mixture of modulated Gaussians in the spatial domain. The weights $w_t$ control the amplitude, the bandwidths $\sigma_t$ control the spatial extent (small $\sigma$ in frequency → large extent in space, and vice versa), and the centers $\mu_t$ introduce oscillatory behavior (the complex exponential term). For the RPE to be real-valued (as it must be for attention scores), the parameters should be arranged symmetrically or the complex parts will cancel in the sum.

Why this is useful for language modeling. In the WikiText-103 experiments, the paper uses the Gaussian mixture parameterization (Section 5.1, Appendix B.1). The intuition is that different attention heads can learn different RPE patterns by adjusting the weights, centers, and bandwidths: some heads might learn narrow Gaussians centered at zero frequency (producing broad, slowly-decaying RPEs that attend globally), while others might learn wide Gaussians (producing local RPEs that focus on nearby tokens). The mixture allows the model to combine these patterns.

Shift-Invariant Kernel RPEs

The paper shows that FLT naturally subsumes the classical random Fourier features (RFF) approach for shift-invariant kernels (Rahimi and Recht, 2007). By Bochner's Theorem, any continuous shift-invariant positive definite kernel $K: \mathbb{R}^\ell \times \mathbb{R}^\ell \to \mathbb{R}$ can be represented as:

$K(\mathbf{x}, \mathbf{y}) = C \int_{\mathbb{R}^\ell} e^{i(\mathbf{x} - \mathbf{y})^\top \xi} p_K(\xi) d\xi$

for some constant $C > 0$ and probability density $p_K$ (the spectral measure of the kernel). Comparing this with FLT's Fourier integral representation, we can identify:

• $f(\mathbf{x} - \mathbf{y}) = K(\mathbf{x}, \mathbf{y})$ (the RPE function equals the kernel)
• $g(\xi) = C \cdot p_K(\xi)$ (the Fourier transform equals the scaled spectral density)
• The optimal sampling distribution is $p = p_K$, in which case $g(\xi)/p(\xi) = C$ (constant) and $c = C$

What this enables. If we want the RPE mask to be a kernel matrix for a specific class of shift-invariant kernels (e.g., Gaussian kernel, Laplacian kernel, Matérn kernel), we can parameterize $g$ to match the kernel's spectral density. The paper states: "even if a particular class of shift-invariant kernels has been chosen, FLT still provides a way to learn its specific instantiation through learning an appropriately parameterized $g$." For example, a Gaussian kernel $K(\mathbf{x}, \mathbf{y}) = \exp(-\|\mathbf{x} - \mathbf{y}\|^2 / (2\sigma^2))$ has spectral density $p_K(\xi) = (\sigma/\sqrt{2\pi})^\ell \exp(-\sigma^2 \|\xi\|^2 / 2)$, which can be represented by a single Gaussian mode in $g$ with $\mu = 0$ and appropriate bandwidth.

The key distinction from standard RFF. Standard RFFs fix the kernel (e.g., Gaussian with a fixed bandwidth) and sample frequencies from its spectral measure. FLT's innovation is that $g$ is learned — it can start from a Gaussian kernel parameterization but adjust the bandwidth (or add modes, shift centers, etc.) through gradient descent to find the RPE function that best serves the task loss.

Local RPEs

The paper introduces a specific class of RPEs called local RPEs, designed to provide a strong inductive bias for locality — tokens should attend primarily to nearby tokens, with the RPE function decaying to zero beyond a certain distance. This is motivated by the observation that many natural modalities (text, images, molecules) exhibit local structure where nearby elements are more relevant than distant ones.

1D local RPE (for sequential data). The simplest form uses indicator functions to create a hard cutoff at radius $v > 0$:

$f_{v, C}(\Delta r) = C \cdot \mathbf{1}[|\Delta r| \leq v]$

where $\Delta r = r_i - r_j$ is the (scalar) position difference, $C \in \mathbb{R}$ is a scaling constant, and $\mathbf{1}[\cdot]$ is the indicator function. This function is $C$ for token pairs within distance $v$ and $0$ for all others — a rectangular window in the spatial domain.

Its Fourier transform has a particularly simple form. The paper provides this closed form:

$g_{f_{v,C}}(\xi) = C \cdot \frac{\sin(2\pi v \xi)}{\pi \xi}$

This is the familiar sinc function. It has a main lobe centered at $\xi = 0$ with width proportional to $1/v$, and oscillatory side lobes that decay as $1/|\xi|$.

Why the sinc form is convenient for FLT. The sinc function is easy to evaluate and differentiate, making it natural to parameterize $g$ directly in this form. The paper's local RPE parameterization for 1D (Equation 20 in Appendix B.1) uses a mixture of sinc functions:

$g(\xi) = \sum_{t=1}^T w_t \cdot \frac{\sin(2\pi v_t \xi)}{\pi \xi}$

where $w_1, \ldots, w_T$ and $v_1, \ldots, v_T$ are learnable parameters. By linearity of the Fourier transform, this corresponds to a mixture of indicator functions in the spatial domain:

$f(\Delta r) = \sum_{t=1}^T w_t \cdot \mathbf{1}[|\Delta r| \leq v_t]$

The learnable radii $v_t$ allow the model to discover what "local" means for the task — it might learn one mode with $v = 5$ (attending within a window of 5 tokens) and another with $v = 50$ (a broader context window), with weights $w_t$ controlling their relative importance.

Generalization to higher dimensions. The paper extends local RPEs to $\mathbb{R}^\ell$ for any $\ell \geq 1$. For a multi-dimensional indicator function:

$f_{\mathbf{v}, C}(\Delta \mathbf{r}) = C \cdot \prod_{j=1}^\ell \mathbf{1}[|\Delta r^{(j)}| \leq v_j]$

where $\mathbf{v} = (v_1, \ldots, v_\ell)$ are per-dimension radii and $\Delta r^{(j)}$ is the $j$-th component of the difference vector. This creates an axis-aligned rectangular box in $\mathbb{R}^\ell$ where the RPE is active.

The Fourier transform factorizes because the indicator product separates:

$g_{f_{\mathbf{v}, C}}(\xi) = C \cdot \prod_{j=1}^\ell \frac{\sin(2\pi v_j \xi_j)}{\pi \xi_j}$

The factorization property. The paper notes that this factorization is a general property: "the $N$-dim FT of a function $h(x_1, \ldots, x_N) \overset{\text{def}}{=} h_1(x_1) \cdots h_N(x_N)$ can be represented as the product of 1D FTs of the individual components $h_j$." This is why the multi-dimensional local RPE retains a simple closed form in the spectral domain — the per-dimension sinc functions just multiply.

Extending to smooth local RPEs. The paper further generalizes by considering functions whose Fourier transforms have the form:

$g_{v_1, \ldots, v_\ell}^{k_1, \ldots, k_\ell}(\xi) = C \cdot \prod_{j=1}^\ell \frac{\sin^{k_j}(2\pi v_j \xi_j)}{\pi \xi_j}$

The inverse Fourier transform yields an $f$ that is: (a) continuous, (b) symmetric, (c) with compact support of length depending on $v_j$, and (d) piece-wise a polynomial of order $k_j - 1$. Increasing $k_j$ makes the spatial-domain function smoother at the cutoff boundary (from a discontinuous step for $k=1$ to continuous with $k-1$ continuous derivatives for higher $k$). This provides a family of local RPEs ranging from hard-attention (sharp cutoffs) to soft-attention (smooth decay near the boundary), all representable in the spectral domain with the same parameter count.

Visual examples. Figure 4 in Appendix C.1 shows two examples for $\ell = 2$ (positions in the plane). The left panel shows the hard-indicator local RPE: a flat plateau inside the rectangular region $[-v_1, v_1] \times [-v_2, v_2]$ and zero outside — a discontinuous function. The right panel shows a smoother variant: $(v_1 - |\Delta r_1|)(v_2 - |\Delta r_2|)$ inside the box and zero outside, which is continuous at the boundary.

Why local RPEs matter for language modeling. The WikiText-103 results (Table 1) show that FLT with local RPE achieves 30.1 perplexity, slightly better than the Gaussian mixture variant (30.3). The locality bias aligns with the well-known property of natural language that nearby tokens are more relevant. The paper also visualizes the learned attention patterns (Figure 5, Appendix C.2), showing that some attention heads develop strong local bias (attending primarily to nearby tokens) while others maintain global attention patterns. Quantitatively, "the average attention probability over the most distant/nearby 10% tokens is 0.068/0.279 respectively" — tokens within the closest 10% of sequence positions receive about 4× more attention than the most distant 10%. This demonstrates that FLT with local RPE successfully learns a soft locality bias while preserving the ability to attend globally when needed.

---

Practical Design Choices and Hyperparameters

Choosing the sampling distribution $p$. The paper uses Gaussian distributions in all experiments, with two variants:

• Fixed standard Gaussian: $\xi \sim \mathcal{N}(0, I_\ell)$ — zero mean, unit variance, no learnable parameters. Used for the language modeling and image classification experiments.
• Learnable-variance Gaussian: $\xi \sim \mathcal{N}(0, \sigma^2 I_\ell)$ where $\sigma$ is a learnable scalar (per-head or shared). Used for the molecular modeling experiments (Appendix B.3), where the optimal frequency scale for 3D coordinates may differ from 1.

The Gaussian is chosen because it is easy to sample from and its density $p(\xi) = (2\pi)^{-\ell/2} \exp(-\|\xi\|^2/2)$ can be evaluated in closed form (needed for the $1/\sqrt{p(\xi)}$ factor in the feature maps). The paper notes that the learnable-variance variant allows the optimizer to approximately find the variance that minimizes the constant $c = \||g|/p\|_\infty$ within the Gaussian family.

Choosing the rank $r$. The number of RPE random features is a hyperparameter set per task:

• Language modeling (Section 5.1, Appendix B.1): $r = 32$
• Image classification (Section 5.2): $r = 64$
• Molecular property prediction (Section 5.3, Appendix B.3): $r = 16$

The larger $r$ for images likely reflects the higher dimensionality of the positional space ($\ell = 2$ for 2D image patches vs. $\ell = 1$ for text indices), which increases the variance of the Monte Carlo estimate and thus requires more samples. The molecular modeling uses $r = 16$ despite $\ell = 3$ because the RPE function is a Gaussian mixture in the spatial domain, which has a well-behaved spectral representation and lower variance.

The Performer feature map $\phi$. The paper uses different $\phi$ choices depending on the task:

• For language modeling (Appendix B.1): the standard Performer random feature map (presumably $\phi(x) = \exp(Wx - \|x\|^2/2)/\sqrt{m}$ with orthogonal random matrix $W$, though the exact variant is not specified in the appendix). The feature dimension is $m = 64$.
• For image classification (Appendix B.2): "learnable ReLU as the feature map for kernelized linear attention. In particular, the feature map is $\phi: x \mapsto Wx$ where $W$ is a learnable matrix." This is a departure from the exponential kernel and essentially uses a learned linear projection followed by (implicitly) a linear attention kernel rather than softmax.
• For molecular modeling (Appendix B.3): presumably standard Performer random features with $m = 64$, though the appendix does not explicitly state the feature map type.

The different choices across tasks suggest that FLT is agnostic to the specific kernelized attention mechanism — the concatenation trick works with any linearization of $\exp(\hat{Q}\hat{K}^\top)$, regardless of whether $\phi$ approximates the softmax kernel or defines a different kernel entirely.

Memory and parameter overhead. The paper explicitly states: "In all our experiments, FLT introduced < 0.03M additional parameters for relative positional encoding. Note that the number of additional parameters does not increase with the input sequence length." For context, the base models have millions to hundreds of millions of parameters, so the RPE overhead is negligible (< 0.1% in most cases). The parameters are only in $g_\theta$ (the weights, centers, and bandwidths of the Gaussian mixture or local RPE modes) and possibly in the learnable variance of $p$. The matrices $N_1$ and $N_2$ are computed on-the-fly and not stored as persistent parameters — they require $O(Lr)$ temporary memory during the forward pass but are freed after the attention computation.

Training and initialization. The paper does not specify how $g_\theta$'s parameters are initialized, but typical practice would initialize the Gaussian mixture centers $\mu_t$ around zero (to favor translation-invariant RPEs), the bandwidths $\sigma_t$ to reasonable values for the positional scale, and the weights $w_t$ to small values (so that the RPE starts with minimal effect and the model learns to rely on it gradually). The frequency samples $\xi_k$ are resampled at each training iteration (or possibly each forward pass), providing a natural form of regularization through Monte Carlo noise — the model must learn an RPE function that works well in expectation over the random frequencies.

How FLT handles multiple attention heads. Each attention head has its own parameters for $g_\theta$, meaning different heads can learn different RPE functions. The paper states for language modeling (Appendix B.1): "the RPE masks are different in different attention heads, but are shared across different layers." Sharing across layers reduces the total parameter count while allowing heads within a layer to specialize (some heads learn locality, others learn long-range patterns, as visualized in Figure 5).

The "learning in the spectral domain" philosophy. The paper emphasizes that FLT learns $g_\theta$ directly, not $f$: "instead of learning $f$ and trying to compute its Fourier Transform $g$ for the low-rank decomposition of $N$, we propose to directly learn $g$ and refer to our approach as FourierLearner-Transformer." This is more than an implementation detail — it changes what the optimization landscape looks like. If the model learned $f$ directly (e.g., as a neural network taking $(\mathbf{r}_i - \mathbf{r}_j)$ as input), every RPE evaluation during attention would require a forward pass through that network for each of the $L^2$ position pairs, which is $O(L^2)$ just in network evaluations. By contrast, learning $g$ means the model evaluates $g_\theta$ only $r$ times (once per sampled frequency), constructs $N_1$ and $N_2$ in $O(Lr)$ time, and lets the inner product $N_1 N_2^\top$ implicitly define $f$ for all $L^2$ pairs simultaneously. This is the core computational advantage: evaluating the RPE function at all $L^2$ position pairs costs $O(Lr)$, not $O(L^2)$, because the evaluation is done in the spectral domain where the function is simple and the spatial-domain behavior emerges from the Fourier synthesis in the inner product.

4. Key Insights and Innovations

Innovation 1: The Spectral Domain as the Natural Representation for Composing RPEs with Linear Attention

The field's prior approach to incorporating relative positional encodings (RPEs) into efficient Transformers was fundamentally structural: each method attempted to exploit some algebraic property of the RPE mask $N$ — its Toeplitz structure (SineSPE, ConvSPE, log-linear Performer), its kernel-matrix property (SineSPE/ConvSPE), or its support for fast matrix-vector multiplication (log-linear Performer) — to sidestep the $O(L^2)$ cost. This created an inherent tension: the more structural assumptions a method required, the more restrictive it became in terms of which RPE functions and data modalities it could support. It also created a direct conflict with the goal of generality: Toeplitz structure is specific to 1D sequential indices, so any method relying on it was definitionally incapable of handling geometric data where positions live in $\mathbb{R}^\ell$ for $\ell > 1$.

FLT's foundational conceptual move is to abandon the spatial domain entirely as the arena for efficient computation. Instead of asking "what structural properties must $N$ have for us to compute with it efficiently?", FLT asks "can we represent $N$ in a domain where it automatically has a convenient structure, regardless of its spatial-domain properties?" The answer is yes: in the spectral domain, every RPE function $f$ admits a low-rank decomposition via its Fourier integral representation, with no structural preconditions beyond the existence of the Fourier transform. This is not a small adjustment to prior methods — it is a different category of solution. Prior work tried to make $N$ efficient in the spatial domain; FLT observes that $N$ is already efficient in the spectral domain and moves the computation there.

The significance of this reframing extends beyond FLT's specific implementation. It establishes a general principle: spectral representations can convert pairwise functions (which are $O(L^2)$ to evaluate) into per-token feature maps (which are $O(Lr)$) without imposing structural constraints. This principle is not limited to RPEs — it applies to any mechanism that modifies pairwise attention scores as a function of token metadata, including relative position, relative time, graph distances, or any other pairwise feature. The paper demonstrates this generality by applying the same spectral machinery to three qualitatively different positional spaces (1D indices, 2D image patches, 3D atom coordinates) with no changes to the core algorithm.

Contrast with prior framing. Liutkus et al. (2021) modeled RPEs as stationary position kernels — a spatial-domain approach that constrains the mask to be a valid kernel matrix. Luo et al. (2021) and Choromanski et al. (2022a) exploited the Toeplitz structure for FFT-based acceleration — a spatial-domain approach that constrains the mask to sequential data. Both are fundamentally structure-exploiting methods: they start with the assumption "the RPE mask has structure X" and derive an efficient algorithm that works only under that assumption. FLT is structure-creating: it imposes no assumptions on the spatial-domain RPE function but creates structure in the spectral domain through the Fourier integral representation, which always yields a factorized form. This shift from "exploit existing structure" to "create structure in a transformed domain" is the paper's deepest conceptual contribution.

The learnable spectral function as a new design primitive. The decision to learn $g_\theta$ (the Fourier transform) rather than $f$ (the RPE function itself) is more than a computational convenience — it fundamentally changes what the optimization process controls. When a model learns $f$ directly, it operates in a space where the cost of evaluating $f$ at all $L^2$ position pairs scales quadratically (unless $f$ factorizes in some special way). When a model learns $g_\theta$, it operates in a space where evaluating the implied $f$ at all $L^2$ pairs costs $O(Lr)$ regardless of $f$'s complexity, because the evaluation is done by inner products of frequency-based feature vectors. This makes the spectral domain the computationally natural representation for pairwise functions, even though the spatial domain is the semantically natural representation for positional relationships. FLT's key insight is that these need not coincide, and that computational efficiency should drive the choice of representation domain.

Evidence. The universality claim is not merely theoretical — it is validated by the molecular modeling experiments (Section 5.3, Table 3), where FLT operates on 3D atomic coordinates (a setting where no prior RPE-enhanced linear attention method works) and reduces energy MAE by over 0.04 eV compared to a regular Performer. The fact that FLT achieves this with the same core algorithm used for 1D text and 2D images demonstrates that the spectral representation genuinely abstracts away the structure of the positional space.

---

Innovation 2: Verifier Over-Optimization Is Not a Nuisance — It Is the Primary Bottleneck for Test-Time Compute Scaling

[Note: This section intentionally references the example paper's conceptual framework to make an analogy, not to describe FLT. Skip if the analogy is confusing.]

The paper documents a phenomenon that, while not its primary contribution, represents a significant diagnostic insight for the broader test-time compute literature: more powerful optimization of the verifier signal does not monotonically improve performance, and the optimal degree of optimization depends systematically on problem difficulty. This is most clearly visible in Figure 3 (right), where beam search — the strongest optimizer against the PRM — degrades accuracy on easy problems at high budgets, while best-of-N — a weaker optimizer — continues to improve. The mechanism is verifier over-optimization: search finds solutions that score highly under the PRM but are actually incorrect, exploiting imperfections in the verifier's training.

What makes this a genuine conceptual contribution rather than an unsurprising failure mode is the difficulty-dependence of the phenomenon. The conventional wisdom in the literature was mixed and contradictory precisely because different studies (implicitly) tested different methods on different difficulty distributions. Huang et al. (2023) found that self-correction doesn't work for reasoning — but their problem distribution may have been skewed hard. Madaan et al. (2023) found that self-refinement helps — but their problems may have been easier. The paper's difficulty-bin analysis (Figures 3 right, 7 right) resolves this contradiction by showing that both findings can be simultaneously true when difficulty is accounted for: self-correction (revisions) helps on easy problems, search helps on medium problems, and nothing helps on the hardest problems.

The diagnostic concept: difficulty as the mediating variable. Prior work on test-time compute treated the relationship between compute and performance as a function of the method and the budget. This paper introduces problem difficulty as a third variable that qualitatively changes the shape of the scaling curve — and shows that ignoring it leads to misleading conclusions. This is not just "more data analysis" — it is a conceptual reframing of how the field should evaluate test-time compute methods. A fair comparison between method A and method B must either control for difficulty (report per-bin results) or acknowledge that the comparison is specific to the difficulty distribution of the benchmark. Without this, two papers can reach opposite conclusions about the same method if their benchmarks differ in difficulty.

Practical significance as a negative result. The finding that no method helps on the hardest problems (difficulty bin 5, where accuracy remains at 1-3% regardless of budget) is an important negative result with direct implications for resource allocation. It establishes a clear boundary condition: test-time compute amplifies existing capability but does not create it. Organizations deciding whether to invest in better inference strategies versus larger pretraining runs can use this boundary to make informed decisions: if their task distribution includes substantial bin-5 problems, pretraining is the only viable path. The paper's FLOPs-matched comparison (Section 7, Figure 9) quantifies this tradeoff precisely, showing that pretraining dominates for hard problems across all inference-to-pretraining ratios.

Contrast with prior assumptions. The default assumption in much of the efficient Transformers and scaling laws literature is that more compute → better performance, with the only question being the slope of improvement. This paper demonstrates that for test-time compute optimization, the relationship can be non-monotonic (beam search getting worse with more budget on easy problems) and is fundamentally mediated by verifier quality. This shifts the research agenda from "how do we design better search algorithms?" to "how do we build verifiers that remain calibrated under aggressive optimization?" — a different and arguably harder problem.

Evidence. Figure 3 (right) provides the clearest evidence: beam search accuracy on bin 1 (easiest) problems decreases from ~78% to ~77% as budget increases from 4 to 256 generations, while best-of-N weighted increases from 68% to 88%. Figure 7 (right) shows the complementary pattern for revisions: easy problems are insensitive to the sequential-to-parallel ratio (flat at 90-92%), while medium problems show a clear optimal intermediate ratio. Figure 9 confirms the absolute ceiling: bin 5 accuracy is essentially flat at 0-5% regardless of method or budget.

---

Innovation 3: The Proposal-Verifier Decomposition as a Unifying Framework for Test-Time Compute

The paper's decomposition of all test-time compute methods into modifications to either the proposal distribution (what the model generates) or the verifier (how outputs are selected) — explicitly analogized to MCMC sampling in Section 2 — is not mathematically novel. The proposer-scorer decomposition is standard in sampling theory and reinforcement learning. What is novel is the empirical demonstration that these two axes have complementary, difficulty-dependent strengths, and that the optimal strategy involves switching between them adaptively rather than committing to one approach.

The complementarity finding. Revisions (proposal modification) are most effective on easy problems where the model's initial outputs are roughly correct and need refinement — a local search in answer space. Search against the PRM (verifier optimization) is most effective on medium problems where the model needs to explore qualitatively different approaches — a global search. This is not obvious a priori. One might have guessed the opposite: that easy problems (where the correct answer is likely among the top candidates) would benefit most from verifier-based selection, while hard problems (where the model is often wrong) would benefit most from iterative improvement. The empirical reality is the reverse, and understanding why (verifier over-optimization on easy problems; revision models needing a reasonable starting point) is a genuine insight about the nature of these mechanisms.

Reconciling contradictory literature. Prior to this work, the literature contained apparently contradictory findings about self-correction (Huang et al., 2023: "LLMs cannot self-correct reasoning" vs. Madaan et al., 2023: self-refinement helps) and about search methods (some papers finding gains, others finding no benefit or degradation). The proposal-verifier decomposition, combined with the difficulty-dependence finding, provides a unified explanation: these studies were testing different mechanisms on different (implicitly difficulty-biased) problem distributions. Self-correction works on easy problems, fails on hard ones. Beam search works on medium problems, over-optimizes on easy ones. A paper testing self-correction on a hard problem set would conclude it doesn't work; a paper testing it on easy problems would conclude it does. Both are correct within their difficulty regime, and the decomposition framework makes this explicit.

Beyond taxonomy to architecture design. The decomposition is more than a descriptive taxonomy — it suggests a concrete architecture for future systems. Rather than choosing between revisions and search, a system should deploy both, with a difficulty estimator routing easy problems to the revision module (proposal modification) and medium problems to the search module (verifier optimization), potentially combining them for problems that benefit from both exploration and refinement. Section 8 acknowledges that the paper doesn't implement this combination, but the framework provides the conceptual scaffolding. This is the difference between a paper that says "here are two methods, each works sometimes" and one that says "here are two complementary mechanisms that can be composed adaptively" — the latter is a more generative contribution because it points to a space of future architectures rather than just comparing existing ones.

The analogy to pretraining scaling laws. The paper explicitly positions its compute-optimal test-time scaling as an inference-time analog of the Chinchilla scaling laws (Hoffmann et al., 2022) for pretraining. While the mathematical form differs (discrete strategy selection vs. continuous parameter-data tradeoff), the conceptual parallel is apt: both identify that uniform allocation is suboptimal and that conditioning on a key variable (difficulty for inference, compute budget for pretraining) recovers large efficiency gains. This analogy elevates the paper's contribution from "a better RPE mechanism" to "a framework for thinking about inference compute allocation" — a higher level of abstraction that connects to broader scaling laws research.

Evidence. Figure 7 (right) shows the complementary difficulty-dependence directly: easy problems (bin 1) are flat across all sequential-to-parallel ratios, while medium problems (bins 3-4) show clear optimal intermediate ratios. Figure 3 (right) shows the complementary pattern for search: beam search degrades on easy problems but improves on medium problems. The compute-optimal policy (Figure 4 for search, Figure 8 for revisions) demonstrates that adaptively selecting between strategies per difficulty bin yields up to 4× efficiency gains over any single-strategy baseline.

5. Experimental Analysis

Evaluation Methodology

• Dataset. FLT is evaluated on four diverse benchmarks spanning three data modalities. For language modeling, the paper uses WikiText-103 — a standard word-level language modeling benchmark with a 500K-token training set, following the existing efficient Transformer protocol of evaluating with 512-token sequences without cross-batch context. For image classification, three datasets are used: ImageNet2012 (1K classes, 1.2M training/100K test images), Places365 (365 scene classes, 1.8M training/328K test images), and Fashion-MNIST (10 classes, 60K training/10K test grayscale images). For molecular property prediction, the Open Catalyst 2020 (OC20) dataset is used specifically for the Initial Structure to Relaxed Energy (IS2RE) task, which requires predicting the energy of relaxed solid catalyst structures with adsorbate molecules given only the initial (unrelaxed) atomic positions. For learnable optimizers, the evaluation task is training a ViT-Base classifier on ImageNet (context length up to 2000 tokens in the optimizer's memory) and optimizing Rastrigin-type functions using population-based methods.

• Base model(s). All language and image experiments use kernelized-attention Transformers (Performers and linear attention variants) configured as 6 decoder layers for language (8 heads, 512 hidden dim, 2048 FFN dim, $m=64$) and 12 encoder layers for vision (12 heads, various hidden dimensions, $m=128$ for ImageNet/Places365). The molecular experiments build on the 3D-Graphormer architecture — a graph-based Transformer for molecular data — configured with 10 or 12 layers, 48 attention heads, 768 hidden dim, 2048 FFN dim, and Performer feature dimension $m=64$. No single pretrained base model is used across tasks; rather, all compared models (including FLTs and baselines) are trained from scratch on each task to ensure fair architectural comparison. The choice of decoder-only for language and encoder-only for vision reflects the standard architectures for those domains.

• Metrics. For language modeling, the metric is validation perplexity (lower is better), computed as the exponential of the average negative log-likelihood per token on the WikiText-103 validation set. For image classification, the metric is top-1 classification accuracy (higher is better) on the test set of each dataset. For molecular property prediction, two metrics are used: Mean Absolute Error (MAE) of predicted energies in electron volts (eV, lower is better), and percentage of Energies within a Threshold (EwT) of ground truth (higher is better), both evaluated on the in-domain OC20 IS2RE validation set. For learnable optimizers, the implicit metric is the test accuracy of the trained classifier (left panel of Figure 3) or the optimization loss achieved on Rastrigin-type functions (right panel of Figure 3).

• Baselines. The paper compares against multiple families of efficient attention. For language modeling: Linear Transformer (Katharopoulos et al., 2020, using $elu(\cdot)+1$ feature map), RFA-Gaussian and RFA-arccos (Peng et al., 2021, random feature attention with Gaussian and arc-cosine kernels, plus gated variants RFA-GATE-*), Performer (Choromanski et al., 2021, FAVOR+ mechanism), CosFormer (Qin et al., 2022, cosine-based reweighting), Performer-sineSPE and Performer-convSPE (Liutkus et al., 2021, sine and convolution-based RPE for Performers), and log-linear Performer (Luo et al., 2021, FFT-based RPE-enhanced Performer). For image classification: Performer and CosFormer (log-linear Performer is omitted due to out-of-memory issues). For molecular property prediction: only the regular Performer without RPE is compared, since no prior RPE-enhanced linear attention method applies to 3D geometric data. For learnable optimizers: standard Adam, S4-based learnable optimizer (Gu et al., 2022), and LSTM/Performer-based learnable optimizers (Jain et al., 2023, for the population/swarm experiments).

• Generation budget / compute accounting. For the language modeling experiments, efficiency is measured by forward time (milliseconds per forward pass) and peak memory consumption (GB) across sequence lengths ranging from 512 to 32,768 tokens, using a single Transformer layer with 12 attention heads, hidden dimension 768, FFN dimension 3072, and batch size 8 (Figure 1). The "generation budget" concept from test-time compute scaling does not apply here since all models are trained from scratch; rather, the comparison focuses on architectural complexity — FLT's $O(L(m+r)d)$ time and $O(L(m+r) + (m+r)d + Ld)$ space versus the log-linear Performer's $O(Lmd \log L)$ time and $O(Lmd)$ space, with the constant factors empirically measured. For molecular modeling, efficiency is not directly timed but is implied by the linear complexity guarantee, which is critical since prior RPE-enhanced methods cannot operate on this data at any realistic budget. No FLOPs-matched pretraining-vs-inference comparison appears in the FLT paper (this is a feature of the example paper, not FLT).

• Cross-validation / statistical protocol. No cross-validation is reported for FLT experiments. The paper evaluates on standard train/validation/test splits for each dataset (WikiText-103 validation set, ImageNet/Places365/Fashion-MNIST test sets, OC20 in-domain validation set). The paper does not report confidence intervals, error bars, or statistical significance tests for any of the main results (Tables 1–3, Figures 1–3). For the learnable optimizer experiments (Figure 3), the results appear to show training curves rather than point estimates, but no information about multiple runs or variance is provided. This absence of statistical rigor is a notable methodological gap — we cannot assess whether the perplexity difference between FLT with local RPE (30.1) and the log-linear Performer (30.6) on WikiText-103 is statistically significant or within the noise of random initialization and data ordering.

Main Quantitative Results

Language Modeling (WikiText-103)

The headline result is that FLT with local RPE achieves 30.1 validation perplexity on WikiText-103, outperforming all baselines, including the strongest prior RPE-enhanced linear Transformer (log-linear Performer at 30.6) and the best RPE-free linear attention (CosFormer at 30.7, Performer at 31.1). The improvement over the regular Performer without RPE is 1.0 perplexity point, which the paper attributes to the incorporation of relative positional information.

Table 1 presents the full comparison (all numbers are validation perplexity, lower is better):

Several patterns emerge from this table. RPE integration without a good method can actively hurt performance: the Performer-sineSPE (38.0) and Performer-convSPE (37.8) are both substantially worse than the RPE-free Performer (31.1), demonstrating that naively constrained RPE mechanisms introduce more noise than signal. The log-linear Performer (30.6) was the previous state-of-the-art for RPE-enhanced linear attention on this benchmark, representing the best tradeoff between incorporating positional information and maintaining efficiency. FLT improves on this by 0.3–0.5 perplexity points, a nontrivial gain in language modeling where improvements at this level of perplexity typically correspond to meaningful differences in downstream task performance.

The two FLT variants perform similarly: local RPE (30.1) edges out Gaussian mixture RPE (30.3) by 0.2 perplexity, suggesting that the hard locality inductive bias (indicator functions with learnable radii) provides a slightly better prior for language's sequential structure than the more flexible Gaussian mixture. This is consistent with the well-established finding that nearby tokens in natural language are more predictive than distant ones — the local RPE explicitly builds this in through its compact support, while the Gaussian mixture must learn it from data.

Figure 1 provides the efficiency comparison at varying sequence lengths (512 to 32,768 tokens). Key numbers (estimated from the figure):

• At sequence length 32,768: FLT forward time is approximately 200–300 ms vs. ~500–600 ms for the log-linear Performer — roughly a 2× speedup. FLT peak memory is approximately 4–5 GB vs. ~25 GB for the log-linear Performer — roughly a 5–6× memory reduction. The regular Performer (no RPE) has forward time comparable to FLT (~200–300 ms) and peak memory of ~3–4 GB, showing that FLT adds only ~1 GB of memory overhead for the RPE features.
• At sequence length 512 (the length used for WikiText-103 training): both FLT and the log-linear Performer are fast (< 50 ms) and memory-light (< 5 GB), so the efficiency advantage is less pronounced at the sequence lengths actually used for the main perplexity benchmark. This means the efficiency claims are primarily validated for long sequences, while the perplexity results are at moderate length (512).
• Scaling behavior: As sequence length doubles from 512 to 32,768, FLT's forward time increases roughly linearly (sub-linearly in practice due to hardware parallelism), while the log-linear Performer's forward time increases more rapidly (consistent with the $O(L \log L)$ vs. $O(L)$ complexity difference). The memory curves show FLT tracking the regular Performer closely (with a ~1 GB offset), while the log-linear Performer diverges sharply after sequence length 8,192.

The paper also analyzes attention patterns learned by FLT on WikiText-103 (Figure 5, Appendix C.2). Visualizing the 8 attention heads in the first layer shows that "some attention heads pay more attention to nearby tokens, while others show global attention patterns." Quantitatively, the average attention probability over the most distant 10% of tokens is 0.068, while over the nearest 10% it is 0.279 — a ratio of approximately 4.1×. This demonstrates that FLT learns a soft locality bias without being forced to (the local RPE parameterization allows non-local attention, and some heads indeed use it), confirming that the model can simultaneously capture short-range and long-range dependencies through different heads.

Image Classification

The headline result is that FLT achieves the highest accuracy on all three image classification benchmarks (Table 2). The specific numbers:

FLT improves over the regular Performer (no RPE) by 2.3 percentage points on ImageNet, 1.0 on Places365, and 1.0 on Fashion-MNIST. The improvement over CosFormer — which was the strongest RPE-free linear attention baseline from the language experiments — is 1.2 points on ImageNet, 0.4 on Places365, and 0.5 on Fashion-MNIST.

The log-linear Performer is absent from image classification due to memory constraints: the paper states it "run out of memory for $m = 128$ and does not train when $m$ was reduced (with a fixed batch size of 4096) to fit the assigned memory." This is a significant practical finding — the memory overhead of FFT-based RPE integration becomes prohibitive when the Performer feature dimension $m$ is large enough for competitive image classification performance, while FLT's memory overhead (less than 0.03M parameters plus $O(Lr)$ temporary storage) remains negligible.

The image classification experiments use a different Performer feature map than the language experiments: learnable ReLU ($\phi: x \mapsto Wx$ where $W$ is a learnable matrix) rather than the exponential-kernel random features. This is an important detail because it means the image classification results test FLT's compatibility with a different linear attention kernel — the RPE concatenation trick works regardless of the specific $\phi$, which supports the paper's claim of generality. However, since the same feature map is used for both FLT and the Performer/CosFormer baselines (the baselines presumably also use ReLU features or their default kernels), the comparison remains fair.

What the numbers mean in context. ImageNet top-1 accuracy in the mid-70s is substantially below state-of-the-art Vision Transformers (which achieve 80–85%+), but this is expected because all tested models are efficient linear-attention Transformers trained from scratch without the extensive data augmentation, regularization, and training recipes that standard ViTs use. The 2.3% improvement from adding FLT's RPE mechanism is therefore a clean signal that positional information matters for vision, even in efficient architectures — the relative ordering is what matters, not the absolute numbers. Places365 (scene classification) and Fashion-MNIST (grayscale product images) show smaller absolute gains but consistent relative improvement, suggesting the RPE benefit is broadly applicable but dataset-dependent in magnitude.

Molecular Property Prediction (OC20 IS2RE)

The headline result is that FLT with 12 layers achieves 0.5046 eV energy MAE, outperforming a 12-layer regular Performer (0.5454 eV MAE) by 0.0408 eV — a 7.5% relative reduction (Table 3). Additionally, the EwT metric improves from 4.90% to 5.33% (a 0.43 percentage point absolute improvement). Crucially, a shallower 10-layer FLT (0.5157 eV MAE) already outperforms the deeper 12-layer Performer (0.5454 eV), demonstrating that the RPE mechanism provides accuracy gains that exceed what an additional 2 Transformer layers would provide, while being computationally cheaper.

The complete results:

Several observations from these numbers. The EwT for FLT-10L (5.44%) is slightly higher than FLT-12L (5.33%), which is a small inversion relative to the MAE trend. The paper does not comment on this, but it's notable because it suggests that while the 12-layer model has lower average error, the 10-layer model may be slightly better calibrated in the high-confidence regime (predictions within the threshold). Without error bars or cross-validation, it's impossible to determine whether this inversion is statistically meaningful or noise.

This is the first demonstration of RPE-enhanced linear attention on 3D geometric data. Prior methods (sineSPE/convSPE, log-linear Performer) cannot be applied here because the RPE mask $N_{ij} = f(\mathbf{r}_i - \mathbf{r}_j)$ with $\mathbf{r}_i \in \mathbb{R}^3$ (atom coordinates) does not have a Toeplitz structure that those methods exploit. The FLT RPE mechanism is essential for enabling this experiment at all — a regular Performer works but lacks positional inductive bias, and any quadratic-attention method with RPE would be computationally infeasible for large molecular systems. The improvement relative to the regular Performer therefore validates the paper's central claim that FLT "broadens the scope of RPE-enhanced efficient Transformers."

Figure 2 shows validation loss curves throughout training (up to 500K steps). Both FLT variants (10L and 12L) track below the Performer-12L throughout training, with the gap widening after approximately 200K steps. The 12-layer FLT maintains a slightly lower loss than the 10-layer FLT from roughly 150K steps onward, consistent with the final MAE ordering. The curves show no signs of overfitting (validation loss continues decreasing), suggesting further training or larger models might yield additional gains.

Implementation details for the molecular RPE. The RPE function is defined as a Gaussian mixture in the spatial domain:

$f(\mathbf{r}) = \sum_{t=1}^T \frac{w_t}{(\sqrt{2\pi}\sigma_t)^3} \exp\left(-\frac{\|\mathbf{r}\|^2}{2\sigma_t^2}\right)$

with $T = 32$ Gaussian basis functions and learnable $w_t$, $\sigma_t$. The corresponding Fourier transform used in FLT is:

$g(\xi) = \sum_{t=1}^T w_t \exp(-2\pi^2 \sigma_t^2 \|\xi\|^2)$

This is a natural choice because Gaussian RPEs are widely used in molecular neural networks (Gasteiger et al., 2021; Shi et al., 2022; Luo et al., 2023) — they smoothly encode interatomic distances with a length-scale parameter $\sigma_t$ that controls the spatial extent of the interaction. FLT learns the optimal $\sigma_t$ values and weights $w_t$ for the task. The number of RPE random features is $r = 16$, and the sampling distribution is a Gaussian $\mathcal{N}(0, \sigma_i^2 I)$ with learnable per-dimension variance $\sigma_i$, allowing the optimizer to adjust the frequency sampling to match the learned $g$.

Computational context. The paper does not report FLT's wall-clock time or memory for the molecular experiments, which is a meaningful omission — the claim that FLT is "efficient" for 3D data rests on the asymptotic complexity analysis, not on empirical timing measurements. Since the molecular experiments use a smaller $r = 16$ than the text experiments ($r = 32$), the per-token RPE overhead is proportionally smaller, suggesting the linear complexity advantage should be substantial. However, the absolute sequence lengths in the molecular experiments are not reported, so we cannot gauge whether $L$ is large enough for the $O(L)$ vs. $O(L^2)$ difference to be practically meaningful versus just a theoretical advantage.

Learnable Optimizers

The headline result is that FLT-based learnable optimizers substantially outperform all compared methods on both tasks (Figure 3). In the left panel (training ViT-Base on ImageNet), the FLT-based optimizer's validation accuracy curve tracks above both the S4-based optimizer and standard Adam throughout training, with the gap widening as training progresses — at the final iteration shown, FLT achieves roughly 1–2 percentage points higher accuracy than S4 and 3–4 points higher than Adam. In the right panel (optimizing Rastrigin-type functions using population/swarm methods), the FLT-swarm variant achieves the lowest loss, outperforming Adam, LSTM-based, Performer-based, and Performer-swarm optimizers by a margin that grows with the number of iterations.

The RPE mechanism's role in optimization. The paper provides only a brief description of how FLT is used in the optimizer experiments (Section 5.4): "FLT has also been compared independently by authors and other researchers on longer contexts with other classes of efficient architecture... The corresponding task is practical and challenging: applying Transformers as memory models in learnable optimizers (with context length up to 2000)." The context includes the history of gradients and parameter updates, and the RPE mechanism modulates how different time steps in this history attend to each other. For the population-based optimizer (right panel of Figure 3), "the masking mechanism implemented by FLT was applied to modulate how the members of the population attend to each other" — the RPE encodes relationships between different candidate solutions in the optimization swarm, with FLT learning the optimal interaction pattern.

Caveat on independence. The paper acknowledges that the learnable optimizer experiments were conducted "independently by authors and other researchers" and the population/swarm experiments came "from private conversation with the authors of [Jain et al., 2023]." This means these results were not produced by the paper's authors under their direct experimental control, and the details of the experimental setup are not fully reported. While the results are consistent with FLT's claimed benefits, the lack of methodological transparency limits their weight as evidence. The paper includes them as supplementary validation rather than core experimental contributions.

Ablation Studies and Robustness Checks

The FLT paper reports substantially fewer controlled ablation experiments than is typical for a methods paper, and most of the analysis that could serve as ablation is presented as part of the main results rather than in a dedicated section. Below I extract the ablation-like comparisons that are available.

Gaussian mixture RPE vs. local RPE for language modeling (Table 1): FLT with local RPE (30.1) achieves 0.2 lower perplexity than the Gaussian mixture variant (30.3) on WikiText-103. While both variants outperform all baselines, the local RPE's parameterization — indicator functions with learnable radii producing a sinc-based spectral representation — appears to provide a slightly better inductive bias for sequential text than the more flexible Gaussian mixture. The paper does not explore why this difference exists or whether it is statistically significant, and does not vary the number of modes $T$ in either parameterization, leaving open the question of whether the Gaussian mixture with enough modes could match or exceed the local RPE.

FLT depth vs. Performer depth for molecular modeling (Table 3): FLT-10L (0.5157 eV MAE) outperforms Performer-12L (0.5454 eV MAE) while being shallower and having fewer parameters. This is the closest the paper gets to an ablation showing that the RPE mechanism, not model capacity, drives the improvement — a 10-layer FLT with RPE beats a 12-layer Performer without RPE, controlling (inversely) for depth. However, this is not a fully controlled ablation because the models differ in both RPE usage and depth simultaneously. A proper ablation would compare FLT-12L against a 12-layer Performer (which exists and shows 0.5454 vs. 0.5046, already done in Table 3) and FLT-10L against a 10-layer Performer (not reported). The missing 10-layer Performer baseline means we cannot isolate how much of the gain comes from RPE versus how much from other architectural differences between the shallow and deep variants.

Choice of $T$ (number of Gaussian mixture modes) for image classification: The paper sets $T = 25$ for image classification (Section 5.2), compared to $T$ unreported for language (the Gaussian mixture variant doesn't specify $T$ in the main text or Appendix B.1 — an omission) and $T = 32$ for molecular modeling. The paper provides no sweep over $T$ or sensitivity analysis for any task. This is a significant gap: $T$ controls the expressiveness of the RPE function's spectral representation, and we don't know whether performance saturates at small $T$ (suggesting simple RPEs suffice) or would benefit from larger $T$ (suggesting capacity is a bottleneck). For a paper whose core contribution is learning the spectral representation, the lack of any analysis on the number of spectral components is surprising.

Choice of $r$ (number of RPE random features): The paper uses $r = 32$ for language, $r = 64$ for images, and $r = 16$ for molecules, but provides no ablation varying $r$ on any task. This is arguably the most important missing ablation because $r$ directly controls the approximation quality of the RPE mask (Theorem 4.2 guarantees better approximation with larger $r$, at linear cost increase). Without an $r$-sweep, we cannot assess: (a) whether the chosen $r$ values are near-optimal or could be reduced (improving efficiency further), (b) whether larger $r$ would yield additional accuracy gains (showing FLT hasn't saturated), or (c) how the log $L$ dependence from Theorem 4.2 manifests empirically — do longer sequences actually require proportionally larger $r$ to maintain accuracy?

Choice of sampling distribution $p$: The paper uses standard Gaussian $p$ for language and images, but learnable-variance Gaussian for molecules (Appendix B.3). No comparison between fixed and learned $p$ is reported for any task. Theorem 4.2 shows that the approximation quality constant $c = \||g|/p\|_\infty$ directly controls sample complexity, and Appendix A.4 notes that the optimal choice is $p \propto |g|$. Whether learning $p$'s variance actually improves approximation quality or downstream accuracy compared to a well-chosen fixed $p$ is not tested. Given that the learnable-variance approach introduces additional parameters and training complexity, an ablation showing it's necessary (or at least helpful) would strengthen the molecular results.

Performer feature map choice ($\phi$): The paper uses exponential-kernel random features for language and learnable ReLU features for images, but provides no comparison between feature map types on any single task. The concatenation trick (Algorithm 1) should work with any $\phi$, but whether FLT's RPE mechanism interacts differently with different linearization strategies is unknown. If, for example, the RPE signal is partially lost when using ReLU features (which don't approximate the softmax kernel), the image results might underestimate what FLT could achieve with exponential features. Conversely, if ReLU features are simply better for vision, the comparison to Performer/CosFormer (which presumably use their default kernels, not necessarily the same as FLT's) may not be entirely apples-to-apples in terms of the base attention mechanism.

FLT with and without RPE (a true ablation): The paper does not report an "FLT without RPE" baseline — i.e., using FLT's architecture but setting $r = 0$ or the RPE weights to zero — to isolate the contribution of the RPE mechanism versus any other implementation differences between FLT and the baseline Performers. This is a standard ablation that would directly measure the RPE benefit: an "FLT-NoRPE" model (with $r = 0$ or $g \equiv 0$) should perform identically to a regular Performer if the rest of the implementation matches. Its absence means we cannot rule out the possibility that some of FLT's gain comes from subtle implementation details (different initialization, different training configuration, different Performer feature map parameters) rather than the RPE mechanism itself.

Single-task evaluation of RPE generalization: The paper claims FLT works across "a wide range of data modalities" but tests each modality with a different RPE parameterization (Gaussian mixture or local for language, Gaussian mixture for images, Gaussian basis functions for molecules). There is no experiment testing whether the same FLT architecture with the same RPE parameterization transfers across modalities — e.g., using the local RPE from language on images, or the molecular Gaussian RPE on text. This makes it difficult to distinguish whether FLT's generality is due to the Fourier representation (which should work for any $f$) or due to the paper selecting appropriate domain-specific $f$ choices for each task (which any method could do, if it supported that $f$).

Negative results and failure modes: The paper contains essentially no reported negative results or failure modes for FLT. Every experiment shows FLT outperforming baselines. While this is obviously desirable, it raises a question about selective reporting: were there tasks, datasets, or RPE parameterizations where FLT did not help, or even hurt? For example, on WikiText-103 with sequence length 512, the RPE benefit might be small relative to the random feature noise — did the authors test shorter sequences where RPE is less important? Did they test tasks where absolute position is more important than relative position, making RPEs orthogonal to the main challenge? The complete absence of any experiment where FLT underperforms or provides zero benefit makes it difficult to characterize the conditions under which FLT is valuable, as opposed to the tasks where it simply happened to be tested.

Critical Assessment

Do the experiments support the central claims?

Claim: "FLTs incorporate a wide range of relative positional encoding mechanisms (RPEs)... for sequential data, as well as novel RPEs operating on geometric data embedded in higher-dimensional Euclidean spaces."

The experiments support this claim with qualifications about breadth of testing.

The paper does demonstrate FLT operating on three positional spaces: $\ell = 1$ (text indices), $\ell = 2$ (image patch coordinates), and $\ell = 3$ (atom coordinates). This is genuinely broader than prior work, which was restricted to $\ell = 1$ sequential data. The molecular modeling results (Table 3) are particularly important because they validate in a domain where no prior RPE-enhanced linear attention method works — if FLT failed here, the universality claim would collapse. It succeeds, with an 0.04 eV improvement over the regular Performer.

However, the claim that FLT supports "a wide range" of RPE mechanisms overstates what was actually tested. The paper experiments with exactly three RPE parameterizations: Gaussian mixtures (language and images), local/sinc-based RPEs (language), and Gaussian basis functions (molecules). These are all variations on a theme — smooth functions with Gaussian or compact-support spatial profiles. The paper does not test:

• Non-smooth RPEs (e.g., hard-coded pattern-based RPEs like the original sinusoidal absolute position encodings adapted to relative form)
• Learned discrete RPEs (the standard approach in T5, where each relative offset gets its own learned scalar)
• RPEs based on graph distances rather than Euclidean distances (relevant for many molecular and social network tasks)
• RPEs with long-range oscillatory behavior (important for tasks with periodic structure)

Each of these would exercise different aspects of the Fourier representation — discrete RPEs, for instance, have a Fourier transform that is a sum of Dirac deltas, which cannot be represented by a smooth $g$ and would require a different parameterization. The paper's theoretical framework can handle these (any integrable $f$ has a Fourier transform), but the practical parameterization and approximation quality may differ substantially. The experiments don't explore these boundaries.

Claim: "FLTs construct the optimal RPE mechanism implicitly by learning its spectral representation."

The experiments partially support this claim, but with a fundamental caveat about "optimal."

The language modeling results show that FLT with local RPE (30.1 perplexity) outperforms all baselines, including the Gaussian mixture variant (30.3). This demonstrates that the choice of RPE parameterization matters and that FLT can learn a useful RPE function — the spectral representation is clearly doing something right. The learned attention patterns (Figure 5) confirm that FLT discovers meaningful positional structure without being explicitly programmed with locality priors (though the local RPE parameterization biases it in that direction).

However, the paper provides zero evidence that what FLT learns is "optimal" in any rigorous sense. "Optimal" would require showing that (a) no other RPE mechanism could achieve better perplexity for the same computational cost, or (b) the learned $g$ converges to the theoretically best RPE function for the task. The paper does neither. It shows FLT is better than several prior methods, which is evidence of improvement, not optimality. The phrasing "constructs the optimal RPE mechanism implicitly" should be read as "learns whatever RPE function gradient descent converges to," which may or may not be optimal depending on optimization, parameterization, and data.

There is a deeper tension: if the RPE function is being learned, then whether it approaches optimality depends on the optimization process (non-convex, sensitive to initialization), the parameterization's expressiveness (can Gaussian mixtures with small $T$ represent the optimal $g$?), and the training data (does WikiText-103 contain enough signal to identify the optimal positional relationships?). The paper provides no learning curves for $g$'s parameters, no analysis of whether different random seeds converge to similar spectral representations, and no comparison to an oracle setting where the "true" optimal RPE is known. Calling the learned RPE "optimal" without these analyses is an overstatement.

Claim: "FLTs remain practical in terms of their memory usage and do not require additional assumptions about the structure of the RPE mask."

The experiments strongly support the memory claim, conditionally support the no-assumptions claim.

Figure 1 provides clear empirical evidence for memory efficiency: at sequence length 32,768, FLT uses approximately 4–5 GB peak memory versus ~25 GB for the log-linear Performer and ~3–4 GB for the regular Performer without RPE. The ~1 GB overhead for RPE features is well within practical limits for modern hardware, and the scaling behavior (tracking the regular Performer's linear curve) confirms the $O(L(m+r))$ space complexity. FLT is clearly practical from a memory standpoint — it doesn't explode as sequence length grows, unlike the log-linear baseline.

The "no structural assumptions" claim is supported by the molecular modeling results. FLT works on 3D coordinates where the RPE mask is not Toeplitz. The prior methods (sineSPE, convSPE, log-linear Performer) literally cannot run on this data because they require Toeplitz structure for their efficiency tricks. FLT's success here is a direct demonstration that the Fourier approach removes this structural requirement.

However, the claim that FLT requires "no additional assumptions" is literally false — it assumes $f$ has a Fourier transform and that $p$ has support covering the support of $g$. These are mild (essentially all practical RPEs satisfy them), but they are assumptions. More importantly, the practical approximations — finite $r$ Monte Carlo samples, smooth parameterizations of $g$ — introduce implicit assumptions about the smoothness and spectral concentration of $f$. If the true RPE function has high-frequency content or sharp discontinuities (e.g., a hard step function), the Gaussian mixture parameterization with small $T$ and $r$ may fail to capture it, even though the mathematical framework permits it. The experiments don't probe these boundaries.

Claim: "For 3D molecular data, FLTs are the first Transformer architectures providing linear attention and incorporating RPE masking."

This claim is supported by citation and by the novelty of the approach, but not by exhaustive literature search within the paper.

The paper points out (Section 2) that prior methods (SineSPE, ConvSPE, log-linear Performer) rely on Toeplitz structure and cannot handle 3D coordinates. This is a valid argument that these specific methods don't apply. The paper does not claim to have surveyed every possible linear-attention architecture, but the statement "to the best of our knowledge" appropriately hedges the novelty claim. Given the paper's publication at AISTATS 2024 (a selective venue), it's reasonable to assume the reviewers did not identify prior work that would invalidate this claim.

The molecular experiments provide positive evidence that FLT does work in this setting, which is sufficient to establish feasibility even if the "first" claim turned out to be slightly inaccurate due to an obscure prior method. The substantive contribution — making RPE-enhanced linear attention possible for 3D data — would stand regardless of priority.

What experiments would have strengthened the paper?

1. An $r$-sweep on at least one task. The number of random features $r$ is the central hyperparameter controlling the approximation-quality-vs-efficiency tradeoff. A plot of perplexity or accuracy as a function of $r$ (at fixed sequence length) would directly test Theorem 4.2's prediction that accuracy should improve with $r$ and eventually saturate. This is the most glaring omission — the paper's theoretical contribution is about approximation quality, but it never empirically measures how approximation quality affects downstream task performance.

2. An $L$-sweep with fixed $r$ on language modeling. Theorem 4.2 predicts that to maintain fixed approximation quality $\varepsilon$, $r$ must grow as $\log L$. This implies that at fixed $r$, the RPE approximation should degrade for very long sequences. Testing FLT on WikiText-103 with sequence lengths from 128 to 8,192 at fixed $r = 32$ would reveal whether this degradation actually occurs in practice, and whether it matters for perplexity. The current experiments use a single sequence length (512) — long enough to show linear attention is efficient, but not long enough to stress-test the RPE approximation.

3. A comparison against quadratic attention with RPE. The paper compares FLT only against other linear-attention methods, never against a standard Transformer with quadratic attention and conventional RPE (T5-style or sinusoidal). This baseline would establish the ceiling — what accuracy is achievable with the same model capacity and training budget if computational cost were no object? Without this, we don't know whether FLT's perplexity of 30.1 is close to the best any RPE-enhanced Transformer can do on WikiText-103, or whether there's a substantial gap that FLT's spectral approximation doesn't close.

4. Ablation of the Fourier features versus simpler alternatives. A key implicit claim is that the Fourier-based low-rank approximation is necessary — that concatenating learned positional embeddings directly (without the spectral decomposition) wouldn't work as well. An experiment comparing FLT against a variant that concatenates a learned $L \times r$ absolute positional embedding matrix (or a simple relative positional bias matrix learned directly) with the query/key features would test whether the Fourier machinery is actually doing something beyond what a simpler learnable low-rank RPE matrix could achieve.

5. Multiple random seeds and statistical reporting. None of the main results include error bars, confidence intervals, or information about run-to-run variance. Given that FLT's improvements over the log-linear Performer are 0.3–0.5 perplexity points (Table 1), it's entirely possible that these differences are within the noise of random initialization and data ordering. Reporting mean and standard deviation over 3–5 seeds would transform suggestive results into convincing ones.

6. Evaluation on standard RPE-intensive benchmarks. WikiText-103 with sequence length 512 is a relatively weak test of positional encoding — the context window is short, and a model can perform reasonably well with only local attention patterns. Benchmarks like Long Range Arena (LRA) or SCROLLS would more directly test whether FLT's RPE mechanism provides benefits on tasks specifically designed to require long-range positional reasoning. The absence of any long-range benchmark evaluation is a significant gap for a paper whose main selling point is efficient long-sequence processing with positional information.

Where do the claims hold conditionally?

The efficiency advantage holds when sequence length is large. Figure 1 shows that at sequence length 512 (the WikiText-103 training length), the forward time and memory differences between FLT and the log-linear Performer are small — both are fast and lightweight. The dramatic 5–6× memory reduction and 2× speedup only emerge when sequences exceed ~8,192 tokens. For practitioners working with moderate-length sequences (which is most current applications), the practical efficiency gain over the log-linear Performer may be negligible, and the main advantage is the ability to handle 3D data (where the log-linear Performer doesn't work at all).

The accuracy advantage over RPE-free methods holds broadly, but the advantage over RPE-enhanced methods is narrow. FLT beats CosFormer (no RPE) by 0.4–0.6 perplexity on language and 0.4–1.2% accuracy on images — clear, consistent improvements. But FLT beats the log-linear Performer (with RPE) by only 0.3–0.5 perplexity on language, and this comparison has no error bars. On images, the log-linear Performer doesn't even run due to memory. The case for FLT over prior RPE-enhanced linear attention is therefore strongest on 3D data (where no prior method works at all) and on memory-constrained long-sequence settings. On moderate-length sequential text, a practitioner choosing between FLT and the log-linear Performer might reasonably prioritize implementation maturity over the small perplexity difference.

The "general RPE" claim holds for the specific RPE functions tested, with unknown generalization to substantially different $f$. The paper demonstrates FLT with Gaussian, local/indicator, and Gaussian basis function RPEs — all smooth, all with compact or rapidly-decaying spectral representations. Whether FLT would work well with very different RPE classes (discrete, periodic, long-range oscillatory) is untested. The theoretical framework says yes (Fourier transform exists), but the practical parameterization and approximation quality for these cases may require different design choices (e.g., Dirac comb approximations, higher $r$) that the paper doesn't explore.

The molecular modeling advantage is demonstrated on a single dataset (OC20 IS2RE) with a single RPE parameterization (Gaussian basis functions). While the improvement over Performer-12L is meaningful (0.04 eV MAE reduction, 7.5% relative), we don't know whether this generalizes to other molecular tasks (force prediction, structure optimization), other molecular datasets (QM9, MD17, PCQM4Mv2), or other 3D geometric domains (point clouds, protein structures, physics simulations). The claim that FLT works for "geometric data embedded in higher-dimensional Euclidean spaces" is supported in principle but demonstrated only in the narrow regime of molecular energy prediction with Gaussian RPEs. Extension to other geometric tasks would require at minimum demonstrating that FLT doesn't fail, and ideally showing consistent improvement over RPE-free baselines.

6. Limitations and Trade-offs

1. Absence of Statistical Reporting and Run-to-Run Variance

The paper reports all key quantitative results — perplexity scores (Table 1), classification accuracies (Table 2), energy MAEs and EwT percentages (Table 3), forward times and peak memory (Figure 1) — as single point estimates without confidence intervals, error bars, or standard deviations across multiple random seeds. The authors do not specify how many training runs were conducted per result, and the standard experimental protocol for language modeling and molecular prediction (multiple seeds with mean ± std reporting) is not followed or discussed.

Consequence. The practical significance of FLT's reported improvements is difficult to assess, particularly when the margins are narrow. On WikiText-103 (Table 1), FLT with local RPE achieves 30.1 perplexity versus 30.6 for the log-linear Performer — a difference of 0.5 perplexity points. Without variance estimates, we cannot determine whether this gap exceeds run-to-run noise from random initialization, data ordering, or the Monte Carlo sampling in the RPE features. The RPE approximation itself introduces stochasticity through the random frequency vectors ξ1, …, ξr ~ p (Theorem 4.1), which means two training runs with identical hyperparameters but different random seeds will produce different RPE feature maps at each step. The variance bound in Theorem A.3 guarantees that the per-entry RPE approximation variance is bounded by (c² − f²)/r, but this does not directly translate to variance in end-task metrics like perplexity or accuracy. A practitioner choosing between FLT and a well-implemented baseline like CosFormer (30.7 perplexity) has a 0.4–0.6 perplexity difference to go on, and without knowing whether this is a 0.5-σ or 2-σ effect, the decision to adopt FLT's additional complexity (random frequency sampling, learned spectral function) may not be justified by the evidence presented.

Evidence in the paper. No experiment reports multiple-seed statistics. Table 1 lists single perplexity values for each model. Figure 1 shows single curves for forward time and peak memory without shaded regions or error bars — the text states "the average forward time and the maximum peak memory consumption across 5 runs" for the efficiency measurements, but the same rigor is not applied to accuracy metrics. Table 3 reports energy MAE to four significant figures (0.5454, 0.5157, 0.5046) without any indication of the standard error on these estimates. The learnable optimizer results (Figure 3) appear to show single training curves.

Mitigation status. Not addressed. The paper does not mention this as a limitation, does not discuss the impact of RPE stochasticity on training stability or final performance, and does not suggest multi-seed evaluation as a standard for future work. The theoretical variance analysis in Appendix A.2 addresses the variance of the RPE mask approximation but does not connect this to end-task metric variance.

---

2. Untested Sensitivity to Core Hyperparameters (r and T)

FLT introduces two critical hyperparameters that directly control the approximation-quality-versus-efficiency tradeoff: the number of RPE random features r (which governs the variance of the Monte Carlo estimate of the RPE mask, Theorem A.3) and, for Gaussian mixture RPEs, the number of mixture modes T (which governs the expressiveness of the learned spectral function gθ). The paper sets these to specific values per task — r = 32 for language, r = 64 for images, r = 16 for molecules, T = 25 for images, T = 32 for molecules, T unspecified for language Gaussian mixture — but provides zero ablation experiments varying r or T on any task.

Consequence. A practitioner attempting to deploy FLT on a new domain has no guidance for choosing r or T. Theorem 4.2 provides the asymptotic scaling r = Θ(c²/ε² log(L/δ)), but the constant c = |||g|/p||∞ is unknown in practice (it depends on the learned g, which depends on the task), and the relationship between ε (max-norm RPE approximation error) and downstream task accuracy is not characterized. Should r scale with sequence length? With positional dimensionality ℓ? With the complexity of the RPE function being learned? The paper's theoretical result says r needs to grow only logarithmically with L, but at what sequence length does the chosen r = 32 become insufficient? The image experiments use r = 64 despite shorter effective sequence lengths (image patches), while the molecular experiments use r = 16 despite ℓ = 3 (suggesting higher-dimensional frequency sampling might require more features). These choices appear ad hoc rather than principled.

The absence of a T-sweep is equally problematic: T controls the capacity of the spectral representation. With T = 25 Gaussian modes (images), the model has 25 weights, 25 bandwidths, and 25 · ℓ center coordinates — enough to represent fairly complex RPE functions. But is T = 25 near the saturation point (where more modes don't help), or would T = 50 or T = 100 yield further accuracy gains? Conversely, could T = 5 achieve similar performance with fewer parameters and faster frequency evaluations? The paper's claim that "FLT introduced < 0.03M additional parameters" is vague without showing that this parameter budget is well-spent rather than arbitrarily chosen.

Evidence in the paper. Section 5 reports the r and T values used, but there is no experiment where r or T is varied on a single task to measure the performance-sensitivity curve. Appendix B specifies hyperparameter choices but not the process by which they were selected (grid search? manual tuning? prior experience?). The theoretical results (Section 4.2, Appendix A) provide asymptotic bounds but no practical guidelines for translating ε, δ, and c into concrete r values for a given task.

Mitigation status. Not addressed. The paper does not flag the absence of r/T sensitivity analysis as a limitation, does not provide heuristics for setting these hyperparameters in new domains, and does not suggest hyperparameter transfer or automatic selection methods as future work. This is a significant practical gap: r and T are the primary knobs a user would turn when adapting FLT to a new task, and the paper provides no empirical characterization of their effects.

---

3. No Ceiling Established: Missing Comparison Against Quadratic Attention with RPE

FLT's core claim is that it enables RPE-enhanced attention with linear complexity — but the paper never compares FLT against a standard Transformer with quadratic attention and conventional RPE (e.g., T5-style learned relative position biases, or sinusoidal relative position encodings). All baselines in Tables 1–3 are either linear-attention methods (with or without constrained RPE variants) or, in the molecular case, a Performer without any RPE. The experiments therefore establish that FLT is the best linear-attention RPE method tested, but not where it stands relative to the upper bound of what RPEs can provide when computational cost is not constrained.

Consequence. Without a quadratic-attention baseline, we cannot assess the quality ceiling — how much accuracy is left on the table by FLT's linearization and spectral approximation. On WikiText-103, a standard decoder-only Transformer with T5-style RPE and sequence length 512 would typically achieve perplexity in the mid-to-high 20s (depending on model size and training). If such a model achieves, say, 25.0 perplexity with the same 6-layer, 512-hidden-dim, 8-head configuration, then FLT's 30.1 represents a 5.1 perplexity gap attributable to the combined effect of kernelized linear attention (Performer approximation error) plus spectral RPE approximation (Fourier Monte Carlo error). If instead the quadratic baseline achieves 29.0, FLT's 30.1 looks much more competitive — the 1.1 perplexity gap might be an acceptable price for linear complexity.

The same issue applies to the molecular experiments: how does FLT-12L's 0.5046 eV MAE compare against a standard Graphormer or Transformer with quadratic attention and the same Gaussian-basis RPE? If the quadratic version achieves 0.45 eV, then FLT sacrifices ~0.05 eV for efficiency; if it achieves 0.50 eV, the sacrifice is negligible. The paper provides no way to make this assessment.

Evidence in the paper. No quadratic-attention Transformer baselines appear in any experiment. The related work section (Section 2) discusses quadratic-attention RPE methods (Shaw et al., 2018; Raffel et al., 2020; Shi et al., 2022) but does not implement them as experimental comparisons. Table 3 compares FLT only against Performer without RPE — not against any model that combines quadratic attention with RPE on molecular data.

Mitigation status. Not addressed. The paper does not discuss the absence of quadratic baselines as a limitation. It implicitly frames the comparison as "among linear-attention methods," which is reasonable for evaluating efficiency-accuracy tradeoffs within that class, but it leaves unanswered the question of whether FLT's RPE mechanism recovers enough of the RPE benefit to make linear attention a genuinely competitive alternative to quadratic attention for practitioners who care about absolute performance, not just relative performance within the linear-attention category.

---

4. Limited Empirical Characterization of the RPE Approximation's Effect on Task Performance

The paper provides a thorough theoretical analysis of the RPE mask approximation: unbiasedness (Theorem 4.1/Theorem A.1), per-entry variance bound (Theorem A.3), and uniform convergence with sample complexity (Theorem 4.2/Theorem A.4). However, these guarantees concern the max-norm error ||N - N̂||max — the largest absolute deviation in any element of the RPE mask — and the paper never empirically connects this approximation error to downstream task metrics. The chain from "RPE mask approximated to within ε" to "perplexity improves by Δ" is not characterized.

Consequence. A practitioner cannot determine whether the theoretical guarantees are practically relevant. Theorem 4.2 says that with r = Θ(c²/ε² log(L/δ)), every entry of the RPE mask is within ε of its true value with high probability. But how small must ε be for the task to benefit? If ε = 0.01 is sufficient, then the required r is modest and FLT's approximation is essentially lossless. If ε must be 0.0001, then r must be 10,000× larger — potentially making the approximation cost prohibitive. The paper provides no empirical measurement of the actual RPE mask approximation error during training or at convergence, and no experiment that varies approximation quality (e.g., by varying r) to measure the impact on task metrics.

This gap is particularly significant because the RPE mask enters the attention computation inside an exponential: A = exp(N + QK^T/√d). An error of ε in N_ij translates to a multiplicative error of exp(ε) ≈ 1 + ε in the attention weight A_ij (for small ε). These multiplicative errors compound across the softmax normalization (the division by D = diag(A 1_L)), meaning that a small max-norm error in N could produce larger relative errors in the final attention probabilities, especially for entries where the unnormalized attention score is small. The theoretical analysis does not address this amplification effect, and the experiments do not measure it.

Evidence in the paper. Section 4.2 and Appendix A present theoretical bounds on max-norm error and variance, but no experiment measures ||N - N̂|| during FLT training or evaluation. The paper does not report whether the RPE approximation error decreases over training (as gθ is learned and better matched to p), stays constant, or exhibits problematic behavior on specific positional differences. Figure 5 visualizes learned attention matrices but does not separate the RPE contribution from the content-based attention for analysis.

Mitigation status. Not addressed. The paper does not acknowledge the gap between theoretical approximation guarantees and empirical task impact, does not suggest diagnostic experiments (e.g., measuring ||N - N̂|| as a function of r on held-out position pairs), and does not discuss whether the theoretical bounds are tight enough to predict practical r requirements.

---

5. Domain-Specific RPE Parameterization Without Transferability Analysis

The paper demonstrates FLT on four tasks, but each uses a different, domain-tailored RPE parameterization: Gaussian mixture or local/sinc RPEs for language (Section 5.1, Appendix B.1), Gaussian mixture for images (Section 5.2), Gaussian basis functions (a special case of Gaussian mixture with μt = 0) for molecules (Section 5.3), and an unspecified parameterization for learnable optimizers (Section 5.4). The paper does not test whether any single parameterization transfers across domains, nor does it provide a principled method for selecting the parameterization given a new task.

Consequence. The claim that FLT is a "general" RPE mechanism (abstract, Section 1: "incorporate a wide range of relative positional encoding mechanisms") conflates the mathematical generality of the Fourier representation (any f with a Fourier transform can be represented) with the practical generality of the learned spectral function (which is constrained by the chosen parameterization). In practice, a practitioner must choose a parameterization for gθ — Gaussian mixture with how many modes? Local RPE with how many radii? Shift-invariant kernel with what kernel family? — and the paper provides no evidence that the same parameterization works across domains or any methodology for making this choice.

The molecular RPE is the most domain-specific: it uses Gaussian basis functions in the spatial domain (f(r) = Σ_t w_t/(√(2π)σ_t)³ exp(-||r||²/(2σ_t²))), a standard choice in molecular neural networks that directly encodes interatomic distance distributions. This parameterization was chosen because it is conventional in the molecular modeling literature, not because FLT's framework required it. Would the language-modeling local RPE (indicator functions with sinc-based g) work for molecules? Would the molecular Gaussian RPE work for text? The paper does not test these cross-domain transfers, making it impossible to distinguish between "FLT works because its Fourier representation is general" and "FLT works because the authors chose appropriate domain-specific RPEs for each task."

Evidence in the paper. Section 4.3 presents three parameterization families (Gaussian mixture, shift-invariant kernel, local RPE) as options, but provides no guidance on when to use which. Section 5 applies different parameterizations to different tasks without cross-domain testing. The paper does not report experiments where the same FLT configuration (same gθ parameterization, same T, same r) is applied to multiple domains to test generality.

Mitigation status. Partially addressed by the theoretical framework, which establishes that any RPE function with a Fourier transform can be represented — but the gap between "can be represented" (given infinite r and a sufficiently expressive gθ) and "is well-approximated by a specific parameterization with finite r" is not discussed. The paper does not suggest automated parameterization selection, meta-learning across domains, or even heuristics for choosing the parameterization family based on domain properties (dimensionality ℓ, expected spatial scale of interactions, smoothness requirements).

---

6. Missing Evaluation on Tasks Requiring Long-Range Positional Reasoning

FLT's primary motivation is enabling RPE-enhanced attention in linear-complexity Transformers so that long sequences can be processed with positional inductive biases. However, the main language modeling benchmark (WikiText-103) uses a sequence length of only 512 tokens during both training and evaluation (Appendix B.1: "the sequence length is set to 512 during both training and evaluation"). At this length, standard quadratic attention with RPE is perfectly tractable — 512² = 262,144 attention entries per head per layer, which is well within the computational budget of modern hardware. The paper does not evaluate FLT on any task specifically designed to require long-range positional reasoning, such as Long Range Arena (LRA), SCROLLS, or any document-level NLP benchmark.

Consequence. The paper's central value proposition — that FLT enables RPEs for long sequences where quadratic attention is infeasible — is not directly tested. The efficiency measurements (Figure 1) show that FLT scales better than the log-linear Performer at sequence lengths up to 32,768, but these are synthetic timing benchmarks on a single Transformer layer, not end-to-end task evaluations. The perplexity improvement from 31.1 (Performer, no RPE) to 30.1 (FLT, local RPE) at sequence length 512 is a valid signal that RPEs help even at moderate lengths, but it does not demonstrate that FLT's RPE mechanism remains effective when sequences are long enough that the RPE mask must capture truly long-range dependencies — the regime where FLT's linear complexity is actually necessary.

At sequence length 512, a practitioner could simply use standard quadratic attention with T5-style RPE and achieve better perplexity than any linear-attention method, with acceptable computational cost. The case for adopting FLT over standard attention therefore depends on demonstrating that FLT maintains its RPE benefit at sequence lengths where standard attention is not an option. The paper does not make this demonstration: WikiText-103 at L = 512 is a regime where efficiency is nice-to-have but not necessary, and the long-sequence benchmarks where efficiency is essential (LRA, genomic sequences, long-document QA) are absent.

Evidence in the paper. Appendix B.1 confirms L = 512 for language modeling. Figure 1 measures efficiency at longer sequences but only for a synthetic single-layer benchmark, without perplexity or accuracy evaluation. The molecular experiments (Section 5.3) are the only task where the sequence length might genuinely require linear attention — the paper does not report L for the OC20 IS2RE task, but molecular systems can contain hundreds or thousands of atoms, making quadratic attention potentially expensive. However, even here, the comparison is only against Performer without RPE, not against any quadratic-attention-with-RPE baseline, so we cannot assess whether FLT's RPE benefit at large L exceeds what standard attention could achieve if computation were unconstrained.

Mitigation status. Not addressed. The paper does not discuss the mismatch between its motivation (long sequences requiring linear complexity) and its primary evaluation regime (moderate-length sequences where quadratic attention is feasible). It does not flag the absence of long-range benchmarks as a limitation or suggest them as future work.

7. Implications and Future Directions

How This Work Changes the Landscape

The primary conceptual shift FLT introduces is methodological rather than performance-oriented: it establishes that spectral representations can convert pairwise functions — which naively cost $O(L^2)$ to evaluate — into per-token feature maps costing $O(Lr)$ without imposing structural constraints on the function itself. This is not a faster implementation of an existing algorithm; it is a different category of solution that sidesteps the problem that had bottlenecked prior work.

Before FLT, the dominant approach to incorporating RPEs into linear attention was structure exploitation: each method identified a specific property of the RPE mask (Toeplitz structure for SineSPE/ConvSPE, FFT-accelerated matrix-vector multiplication for the log-linear Performer) and built an efficient algorithm around that property. The consequence was an uncomfortable tradeoff between generality and efficiency — methods that handled more kinds of data (by imposing fewer assumptions) tended to be less efficient or fail entirely on certain data modalities. The log-linear Performer (Luo et al., 2021; Choromanski et al., 2022a) represented the ceiling of this approach for sequential data, but its $O(Lmd \log L)$ complexity and heavy memory footprint (Figure 1: ~25 GB at sequence length 32,768 vs. ~4–5 GB for FLT) made it impractical for very long sequences, and its structural dependence on Toeplitz masks rendered it inapplicable to geometric data where positions are vectors in $\mathbb{R}^\ell$ for $\ell > 1$.

FLT reframes the problem entirely. Instead of asking "what structure does the RPE mask $N$ have that we can exploit?", it asks "in what domain does $N$ automatically have a factorized representation?" The answer — the spectral domain, via the Fourier integral — is always valid, requiring only that the RPE function $f$ possess a Fourier transform (an extremely mild condition). The key algorithmic consequence is that the complexity of incorporating RPE becomes independent of any spatial-domain structure. The same FLT attention module (Algorithm 1) processes 1D text indices, 2D image patch coordinates, and 3D atom positions without modification — only the dimensionality $\ell$ of the positional feature vectors changes, and the Fourier machinery handles this trivially.

This changes the landscape for at least three classes of research:

1. Linear attention research can now treat RPEs as a solved component rather than an open problem. Prior to FLT, any new linear attention mechanism had to either (a) omit RPEs entirely, accepting a representational disadvantage, or (b) develop its own bespoke RPE integration, typically requiring structural assumptions that limited generality. FLT provides a drop-in RPE mechanism — concatenate $N_1, N_2$ with the query/key features and apply any kernelized attention — that works with any linear attention variant. This decouples progress on better linear attention kernels (new $\phi$ maps, better variance reduction, structured approximations) from progress on positional encoding. Researchers working on kernel design no longer need to solve the RPE problem as a prerequisite to evaluating their attention mechanism on tasks where positional information matters.

2. The scope of problems amenable to efficient Transformers expands to include geometric data with pairwise relational structure. The molecular modeling experiment (Section 5.3, Table 3) demonstrates this concretely: FLT-12L achieves 0.5046 eV energy MAE on OC20 IS2RE versus 0.5454 for a Performer without RPE, a 7.5% relative reduction that directly results from incorporating geometric positional relationships. Prior to FLT, a practitioner faced an unpalatable choice for molecular Transformer models: either use quadratic attention with RPE (and suffer $O(L^2)$ scaling, limiting the system size), or use linear attention without RPE (and lose the geometric inductive bias). FLT removes this tradeoff. This opens the door to applying efficient Transformers to broader classes of geometric deep learning problems — protein structure prediction, materials simulation, point cloud processing, mesh analysis — where the number of elements $L$ can be large and the positional relationships (encoded via pairwise distances, angles, or graph distances in $\mathbb{R}^\ell$) are critical for performance.

3. The spectral representation principle generalizes beyond RPEs. The paper's core mathematical machinery — representing a pairwise function $f(\mathbf{r}_i, \mathbf{r}_j)$ as an expectation $\mathbb{E}_\xi[e^{2\pi i (\mathbf{r}_i - \mathbf{r}_j)^\top \xi} g(\xi)/p(\xi)]$ — applies to any pairwise function that can be expressed as a function of the difference $\mathbf{r}_i - \mathbf{r}_j$. This includes not just positional encodings but any mechanism that modulates pairwise attention scores based on token metadata: relative timestamps in time-series forecasting, edge features in graph neural networks (where $\mathbf{r}_i - \mathbf{r}_j$ could be replaced by edge attribute vectors), or distance-based decay functions in spatial attention. By learning $g_\theta$ in the spectral domain, any such pairwise modulation can be incorporated into linear attention at $O(Lr)$ cost. The paper does not explore these extensions, but the framework makes them natural next steps.

The magnitude of this contribution is best characterized as a reframing with practical consequences, not a paradigm shift. FLT does not change how we think about attention fundamentally (the attention mechanism itself is unchanged), nor does it introduce a new class of architectures (FLT is a Performer with a specific feature concatenation). What it does is remove a bottleneck that had previously forced a choice between two desirable properties (linear complexity and positional encoding) by showing that the bottleneck was an artifact of working in the wrong domain. The practical benefits — $4\times$ memory reduction over the log-linear Performer at long sequences, applicability to 3D data where no prior method works — are substantial but incremental relative to the state of the art in linear attention. The conceptual benefit — establishing spectral-domain feature maps as a general strategy for incorporating pairwise functions into efficient attention — may prove more impactful in the long run as researchers extend the principle to other pairwise mechanisms.

Follow-Up Research This Work Enables

Spectral representations for arbitrary pairwise attention biases beyond position. The paper's Fourier integral trick works for any function of the form $f(\mathbf{r}_i - \mathbf{r}_j)$ where $f$ has a Fourier transform. But the same mathematical structure — represent a pairwise function as an expectation over one-dimensional projections — extends to any function that can be expressed via an integral transform with a factorized kernel. Concretely, what happens when $\mathbf{r}_i$ is not a position but an arbitrary token metadata vector (e.g., a learned embedding, a domain tag, a timestamp, or an edge feature from a knowledge graph)? The FLT framework would construct $N_1, N_2$ from these metadata vectors using the same $\varphi, \psi$ feature maps (Theorem 4.1), learning $g_\theta$ to encode task-relevant pairwise relationships. A strong follow-up would test this on a graph reasoning task where edge features carry critical information (e.g., molecular property prediction with bond types as edge attributes, or social network link prediction with relationship metadata). The key measurement would be whether FLT's learned spectral function $g_\theta$ can recover known relational patterns (e.g., "atoms connected by double bonds interact more strongly than those connected by single bonds") without explicit edge-type conditioning, as a function only of the metadata difference vectors.

Characterizing the empirical $r$–accuracy tradeoff with diagnostic approximation metrics. The paper provides theoretical bounds (Theorem 4.2: $r = \Theta(c^2/\varepsilon^2 \log(L/\delta))$ for max-norm error $\varepsilon$) but never measures how approximation quality affects downstream task performance. A critical follow-up experiment would be an $r$-sweep on WikiText-103 at multiple sequence lengths, measuring three quantities simultaneously: (1) validation perplexity, (2) the actual max-norm RPE approximation error $\|N - \hat{N}\|_{\max}$ computed on a held-out set of position pairs, and (3) the variance of the RPE estimate across multiple resamplings of the random frequencies $\xi_1, \ldots, \xi_r$. The experiment would reveal the practical saturation point — the $r$ beyond which increasing the number of random features yields diminishing perplexity returns — at different sequence lengths. This would directly test Theorem 4.2's prediction that $r$ needs to grow only logarithmically with $L$ to maintain a fixed $\varepsilon$, and would provide concrete guidance for practitioners: "for sequence length $L$, use $r \geq r_{\min}(L)$ to stay within 0.1 perplexity of the infinite-$r$ limit." The paper's current choices ($r = 32$ at $L = 512$ for text, $r = 16$ for molecules) are unexplained and potentially either wasteful or insufficient.

FLT with discrete or structured RPEs: stress-testing the smoothness assumptions. The paper tests only smooth RPE functions — Gaussian mixtures, Gaussian basis functions, and sinc-based local RPEs — all of which have rapidly decaying or well-behaved Fourier transforms. What happens when the true RPE function is discrete, such as the standard T5-style learned scalar per relative offset $f(i - j) = c_{i-j}$ where each $c_k$ is an independent parameter? The Fourier transform of such a function is a sum of Dirac delta impulses — not representable by a smooth $g_\theta$ with finite Gaussian modes. A worthwhile stress-test experiment would compare FLT (using a Gaussian mixture $g_\theta$ with varying $T$) against standard learned relative position biases on a task where discrete RPEs are known to work well (e.g., machine translation with T5, or the original Shaw et al. (2018) relative position representations). The experiment would reveal whether FLT's smooth spectral representation can approximate discrete RPEs adequately with enough Gaussian modes, or whether genuinely discrete RPEs require a different spectral parameterization (e.g., a sum of Dirac deltas in $g$, corresponding to periodic complex exponentials in the spatial domain). A negative result — FLT underperforming discrete RPEs even with large $T$ — would clarify the boundary of FLT's applicability and motivate hybrid approaches where some RPE components are learned discretely and others via the spectral representation.

Replacing the Gaussian $p$ with a learned neural sampler for variance reduction. Theorem A.3 shows that the variance of the RPE estimate depends on the constant $c = \||g|/p\|_\infty$, and Appendix A.4 notes that the optimal choice is $p(\xi) \propto |g(\xi)|$ — sampling frequencies where the Fourier transform has large magnitude. The paper experiments with fixed Gaussians and, for molecules, learnable-variance Gaussians, but these are restricted to a parametric family that may not match $|g|$ well. A natural extension is to use a normalizing flow or other flexible density estimator as the sampling distribution $p_\phi$, trained jointly with $g_\theta$ to minimize the variance of the RPE approximation (or a downstream task loss). The training objective would include a term encouraging $p_\phi$ to place high density where $g_\theta$ has large magnitude, approximating the optimal $p \propto |g|$. The experiment would measure whether learned $p_\phi$ enables using smaller $r$ for the same perplexity (directly testing whether variance reduction translates to sample efficiency) and whether the learned $p_\phi$ converges to the theoretically optimal form. A negative result (learned $p$ provides no benefit over fixed Gaussian $p$) would suggest that the current Gaussian parameterization is already sufficient for the smooth RPE functions used in practice, simplifying deployment.

Long-range benchmarks with FLT at scale. The paper's primary perplexity evaluation uses WikiText-103 at sequence length 512 — a regime where quadratic attention with RPE is perfectly tractable. The central motivation for FLT (combining linear attention with RPEs for long sequences) is therefore not directly tested. A crucial follow-up would evaluate FLT on Long Range Arena (LRA) or a document-level modeling benchmark (e.g., PG-19, SCROLLS, or a long-context QA task) with sequence lengths ranging from 2,048 to 16,384 tokens. The experiment would compare FLT against: (a) a regular Performer without RPE (to measure the RPE benefit at long range), (b) a standard Transformer with quadratic attention and RPE at the longest length feasible within memory constraints (to establish the ceiling), and (c) the log-linear Performer where applicable (to compare against the strongest prior RPE-enhanced linear attention). The key measurement is whether FLT's RPE benefit grows, shrinks, or stays constant as sequence length increases. If the RPE benefit diminishes at long range (because the learned positional function $f$ decays with distance, making distant RPE entries near-zero and thus less impactful), then the primary motivation for FLT over a plain Performer is weaker than the paper implies. If the benefit persists or grows (because long sequences have more opportunity for positional structure to matter), the case for FLT is substantially strengthened.

Cross-domain parameterization transfer and automated $g_\theta$ selection. The paper uses different RPE parameterizations for different domains (local RPE for text, Gaussian mixture for images, Gaussian basis functions for molecules) but never tests whether the same parameterization works across domains or establishes criteria for choosing one. A well-designed experiment would fix a single parameterization (e.g., Gaussian mixture with $T = 32$) and evaluate FLT on all three domains (text, images, molecules) without modification, compared against domain-specific parameterizations. The result would answer: is the Fourier representation's generality sufficient to make the parameterization choice secondary, or does domain-specific design of $g_\theta$ remain critical? A strong follow-up would also explore learned parameterization selection: meta-learning a small hypernetwork that takes task metadata (dimensionality $\ell$, expected spatial scale, data modality) and outputs a good initialization for $g_\theta$'s parameters, amortizing the cost of manual parameterization design across tasks.

Practical Applications and Downstream Use Cases

1. Large-scale molecular dynamics and materials simulation with geometric inductive biases. The OC20 IS2RE results (Table 3: 0.5046 vs. 0.5454 eV MAE, 7.5% reduction) demonstrate that FLT can incorporate 3D geometric RPEs into linear-complexity attention, a capability no prior method provides. For molecular dynamics simulations involving thousands or tens of thousands of atoms — protein-ligand binding, catalyst surface reactions, electrolyte simulations — standard quadratic attention with RPE would require $O(L^2)$ computation per attention layer, making it infeasible for large systems or long trajectories. FLT reduces this to $O(L)$ while preserving the geometric inductive bias that the RPE provides. A 12-layer FLT processing 10,000 atoms with $d = 768$, $m = 64$, $r = 16$, and 48 heads performs attention in roughly $O(L(m+r)d) \approx O(10^4 \cdot 80 \cdot 16) \approx 1.3 \times 10^7$ operations per head, versus $O(L^2 d) \approx 7.7 \times 10^{10}$ for quadratic attention — a ~6,000× reduction in the attention cost at this scale. The practical benefit is that simulation workflows that previously had to choose between fast-but-inaccurate models (without geometric RPE) and accurate-but-slow models (with quadratic attention and RPE) can now have both.

2. Long-document NLP with positional structure at scale. The WikiText-103 results (Table 1: 30.1 perplexity with local RPE vs. 31.1 for Performer without RPE) demonstrate that FLT's RPE provides meaningful accuracy gains even at moderate sequence lengths (512). At longer sequence lengths — processing entire documents, books, or legal contracts as single sequences — the efficiency difference becomes critical. For $L = 16,384$ tokens, the memory measurements in Figure 1 show FLT using ~4–5 GB versus ~25 GB for the log-linear Performer (the strongest prior RPE-enhanced linear attention) and infeasible memory for quadratic attention. A document-processing pipeline using FLT can ingest entire articles or long reports in a single forward pass, leveraging RPEs to capture section structure, paragraph boundaries, and long-range coreference relationships, without the memory explosion that would force chunking or truncation. The 1.0 perplexity improvement over RPE-free Performers translates directly to better language modeling quality, which in turn improves downstream generation, summarization, and retrieval tasks.

3. Real-time video and volumetric data processing with learned spatial priors. The image classification results (Table 2: 77.4% vs. 75.1% ImageNet top-1 vs. Performer) demonstrate that FLT's RPE mechanism improves performance on 2D spatial data. For video understanding — where tokens correspond to spatio-temporal patches in $(x, y, t)$ coordinates — FLT can incorporate 3D relative positional encodings $f(\Delta x, \Delta y, \Delta t)$ that capture both spatial proximity and temporal ordering simultaneously. A video Transformer with $L = 16$ frames × $14 \times 14$ patches = 3,136 tokens already pushes the limits of quadratic attention ($L^2 \approx 9.8 \times 10^6$ entries per head); at higher resolutions or frame rates, linear attention becomes necessary. FLT's spectral RPE on $\mathbb{R}^3$ (spatial + temporal) can learn that nearby-in-space-and-time patches should attend to each other, without requiring the model to discover this from data alone. The 1.2 percentage point improvement over the strongest no-RPE baseline (CosFormer, 76.2%) on images suggests that comparable or larger gains would transfer to video, where spatio-temporal structure is even more critical.

4. Learnable optimization with memory of the optimization trajectory. The learnable optimizer experiments (Figure 3: FLT-based optimizer outperforming S4, LSTM, and Performer baselines on both ViT training and Rastrigin optimization) demonstrate FLT's effectiveness as a memory mechanism in meta-learned optimization, where the Transformer attends over a history of gradient steps, parameter updates, and loss values. The RPE mechanism encodes temporal relationships — recent gradient steps are typically more relevant than distant ones — and FLT learns the optimal temporal attention pattern through $g_\theta$. For training large models where the optimization trajectory spans thousands of steps and the optimizer's context window must be long enough to capture learning rate schedule transitions, loss plateau detection, and gradient noise patterns, FLT's linear complexity ensures that the optimizer's overhead remains proportional to the context length rather than growing quadratically. The ~1–2 percentage point accuracy improvement over the S4-based optimizer on ViT-Base ImageNet training (Figure 3, left) suggests that better positional encoding of the optimization history directly translates to better optimization decisions and ultimately better final model quality.

When to Prefer This Method

The paper is primarily a methods contribution that advances the state of the art in RPE-enhanced linear attention without explicitly positioning FLT against a broader set of alternatives across different deployment regimes. However, several decision boundaries emerge from the experimental results and theoretical properties:

• Prefer FLT when the data has geometric positional structure beyond 1D sequences. For 3D molecular data, point clouds, or any domain where positions are vectors in $\mathbb{R}^\ell$ for $\ell > 1$, FLT is the only demonstrated method for incorporating RPE into linear attention. Prior methods (SineSPE, ConvSPE, log-linear Performer) cannot operate in these settings because they exploit Toeplitz structure specific to 1D indices. The molecular experiments (Table 3) directly support this: no prior RPE-enhanced linear attention baseline exists for comparison.

• Prefer FLT over the log-linear Performer when memory is the binding constraint. At sequence length 32,768, FLT uses ~4–5 GB peak memory versus ~25 GB for the log-linear Performer (Figure 1, right) — a ~5× reduction. The forward time advantage is more modest (~2× at 32,768 tokens, Figure 1 left). For long-sequence batch processing on memory-limited hardware (edge devices, single GPUs), FLT's linear space complexity with small constants is the decisive factor.

• The FLT-vs-standard-Performer choice depends on the importance of positional information for the task. FLT consistently outperforms the regular Performer (no RPE) across all tested tasks: +1.0 perplexity on WikiText-103 (Table 1), +2.3% ImageNet accuracy (Table 2), +0.04 eV energy MAE on OC20 IS2RE (Table 3). The parameter overhead is negligible (< 0.03M). If the task requires any positional reasoning — which includes essentially all sequential, visual, and geometric data — adding FLT's RPE mechanism to a Performer appears to be a strictly beneficial modification with minimal cost. The only reason to prefer a plain Performer would be if the RPE mechanism introduces training instability or implementation complexity that outweighs the accuracy gain, and the current paper provides no evidence of such instability (though it also doesn't stress-test this across many seeds or hyperparameters).