DeepETA: How Uber Predicts Arrival Times Using Deep Learning

ArXiv: 2009.14794

🎯 Pitch

Transformers can use regular, full-rank softmax attention at linear time and memory cost—not via sparsity approximations, but through an unbiased estimator that turns the quadratic kernel into a fast linear feature map, shattering the long-held trade-off between accuracy and scalability.

---

1. Executive Summary

This paper introduces Performers, Transformer architectures that estimate regular softmax full-rank attention with provable accuracy while using only linear space and time complexity — a fundamentally different approach from prior methods that rely on sparsity or low-rankness assumptions. The core mechanism is Fast Attention Via positive Orthogonal Random features (FAVOR+) , which decomposes the softmax kernel into a product of positive random feature maps (concretely, replacing the exp(QK^⊤) attention matrix with a low-rank factorization via random projections that can be multiplied in O(Lrd) rather than O(L²d) time), then further reduces estimator variance by enforcing orthogonality among the random projection vectors. The method achieves approximately 4× wall-clock speedup on the backward pass for sequence length L = 2048 and matches regular Transformer accuracy within 0.5% on protein sequence modeling benchmarks, while enabling training at sequence lengths up to L = 8192 that cause regular Transformers to run out of memory even at batch size 1 — establishing that linear-complexity attention can substitute for quadratic attention without performance degradation on problems within the model's capability range, provided that the positive orthogonal random feature mechanism is used rather than conventional trigonometric random features which exhibit catastrophic variance near zero kernel values.

2. Context and Motivation

The Core Problem: Quadratic Scaling Makes Transformer Attention Impractical for Long Sequences

The fundamental obstacle this paper addresses is the quadratic space and time complexity of the standard Transformer attention mechanism with respect to sequence length $L$. For a single attention computation (equation 1), the model must construct an $L \times L$ attention matrix $\mathbf{A} = \exp(\mathbf{Q}\mathbf{K}^\top / \sqrt{d})$, which requires $O(L^2 d)$ time to compute and $O(L^2 + Ld)$ space to store. For context: processing a single protein sequence of length $L=8{,}192$ with a standard Transformer would require roughly $8{,}192^2 \approx 67$ million entries in the attention matrix at each attention head of each layer. With typical architectures using 8 heads and 6+ layers, this becomes infeasible — the paper explicitly reports that a regular Transformer with modest layer counts "overloads memory even at a batch size of 1 per chip, by a wide margin" (Section 4.5) at this sequence length.

This problem is not merely academic. It imposes a hard ceiling on the types of data Transformers can process end-to-end. Any domain requiring context across long sequences — genomic and proteomic analysis, high-resolution images treated as sequences of pixels, document-level text modeling, audio processing at sample rates — is fundamentally constrained by this quadratic bottleneck. The paper emphasizes biological sequence analysis as a particularly motivating use case (Section 6), where proteins routinely have thousands of amino acid residues and understanding their interactions requires modeling entire concatenated protein sequences that can span tens of thousands of tokens.

Why the Quadratic Bottleneck Matters Now

The timing of this work (published at ICLR 2021) reflects a critical juncture in the Transformer architecture's evolution. By 2020, Transformers had become the dominant architecture across NLP (BERT, GPT, T5), computer vision (ViT, iGPT), speech processing, and computational biology — simultaneously, the field was pushing toward ever-longer contexts. But practical deployment faced a harsh reality: even moderate sequence lengths of a few thousand tokens could exhaust GPU memory on expensive hardware accelerators. The paper's Figure 3 demonstrates this starkly: on a V100 GPU with 16GB memory, a standard Transformer becomes unmanageable beyond $L \approx 2{,}048$ for typical model dimensions, while the Performer scales efficiently past $L = 32{,}768$.

The broader implication extends beyond raw computational cost. If Transformers cannot efficiently process long sequences, then:

1. Scientific applications are fundamentally limited. Protein language models (Rives et al., 2019; Madani et al., 2020) showed immense promise for predicting protein structure and function from sequence alone, but were capped at sequence lengths far below what would be needed to model full interaction networks or multi-protein complexes (Cong et al., 2019). The paper cites the need for "proteome scale" modeling as a direct motivation.

2. Context-dependent reasoning remains shallow. In NLP, document-level understanding requires modeling relationships between paragraphs or sections separated by thousands of tokens. Similarly, pixel-level image generation (Parmar et al., 2018) treats images as sequences of pixels, producing attention matrices of dimension $H \times W$ where even modest image sizes create prohibitively large matrices.

3. The pretraining-inference mismatch creates deployment tension. A model trained on truncated sequences learns spurious local patterns that do not generalize to longer contexts at inference time. Most practical systems operate far below the sequence lengths where they would be most useful.

Prior Approaches: A Landscape of Approximations with Hidden Costs

The paper positions itself among a rich ecosystem of prior efficient Transformer variants. Understanding why these fall short is essential to appreciating what FAVOR+ achieves differently.

Sparse Attention Methods: Structural Assumptions That Don't Always Hold

A dominant line of work imposes sparsity patterns on the attention matrix — allowing each token to attend only to a restricted subset of other tokens rather than all $L$ positions. This directly reduces the quadratic to something sub-quadratic (or linear) by construction.

The Sparse Transformer (Child et al., 2019) uses fixed sparse patterns combining strided and local attention — each token attends to a fixed set of predecessors at regular strides, plus its immediate neighbors. The motivation is appealing: decompose attention into local fine-grained patterns plus long-range strided patterns that capture global structure. But the limitation is equally clear: the sparsity pattern is hand-designed and static. If a task requires attending to tokens at irregular positions that fall outside the prescribed pattern, the information is simply unavailable. Moreover, implementing these patterns efficiently requires writing custom CUDA kernels — the paper explicitly notes this forces practitioners into "trial and error by constructing special GPU operations" (Section 1), making the approach fragile and hardware-dependent.

The Reformer (Kitaev et al., 2020) uses Locality-Sensitive Hashing (LSH) to group tokens by similarity before computing attention — only tokens that hash to the same bucket attend to each other. This is more adaptive than fixed sparsity patterns, but introduces its own constraints: it requires identical query and key sets (meaning it only works in specific architectural configurations), and the LSH mechanism has $O(Ld^2 \log L)$ time complexity — the paper notes this is actually worse than FAVOR+'s $O(Ld^2 \log d)$ for large $L$. Furthermore, LSH is inherently stochastic; two tokens that should attend to each other might hash to different buckets, introducing approximation error that is difficult to characterize theoretically.

Longformer (Beltagy et al., 2020) combines sliding window attention with global attention tokens, while Routing Transformer (Roy et al., 2020) uses k-means clustering to learn dynamic sparse attention regions. All these approaches share a common limitation: they trade away the dense, full-rank nature of softmax attention in exchange for efficiency. The paper emphasizes that "there is a lack of rigorous guarantees for the representation power produced by such methods, and sometimes the validity of sparsity patterns can only be verified empirically" (Section 1). In other words, these methods approximate what attention does, but without theoretical bounds on how close that approximation is.

Low-Rank and Kernel-Based Methods: The Ghost of Negative Values

A parallel line of work abandons sparsity in favor of low-rank decompositions of the attention matrix. The key insight is that if the attention matrix $\mathbf{A} \in \mathbb{R}^{L \times L}$ can be approximated by a product of smaller matrices, the $O(L^2)$ bottleneck disappears.

Linformer (Wang et al., 2020) directly projects the key and value matrices to a fixed lower dimension using learned projection matrices. This reduces complexity to $O(Lk)$ for projection dimension $k$, and the authors provide theoretical guarantees showing that the attention matrix is approximately low-rank under certain conditions. However, Linformer is restricted to the bidirectional (non-causal) setting — it cannot be used for autoregressive generation where the attention matrix must be triangular — and the projections introduce bias that is difficult to quantify precisely.

Linear Transformer (Katharopoulos et al., 2020) takes the kernel-based approach further: instead of approximating softmax, it replaces softmax entirely with a kernel that admits an explicit finite feature representation $\phi(x) = \text{elu}(x) + 1$. The resulting attention can be computed in linear time by changing the order of matrix multiplications (the "kernel trick"). This is elegant, but it fundamentally changes the attention function. The paper's experiments (Appendix D.4, Figure 18) show that the Linear Transformer suffers from numerical instability — specifically, "all 3 seeds produced exploding gradients very early on" in the unidirectional protein modeling setting, and another seed exploded "in the middle of training, near 125K steps" in the bidirectional setting. This instability is directly tied to replacing softmax: the elu-based kernel does not have the same normalization properties or variance characteristics.

Kernel methods in general (Tsai et al., 2019; Shen et al., 2018) attempt to express attention as $K(q_i, k_j) = \langle \phi(q_i), \phi(k_j) \rangle$ for some feature map $\phi$, then compute attention by multiplying in the feature space before the kernel. The critical limitation — and this is the gap the paper directly addresses — is that the softmax kernel does not admit an exact finite-dimensional feature representation. Any approach using a finite $r$-dimensional feature map must be an approximation, and prior work had not found approximation schemes that were simultaneously (a) unbiased, (b) low-variance, and (c) guaranteed to produce only non-negative attention weights. The paper demonstrates that standard approximations using trigonometric random features (Rahimi & Recht, 2007) fail catastrophically because $\sin$ and $\cos$ produce negative values, leading to unstable renormalization when diagonal entries of the approximate denominator matrix become negative — a failure mode the paper documents clearly (Figure 5, right; Appendix D.3) where trigonometric features cause "highly unstable" training or even NaN values.

Other Mechanisms: Patches That Don't Solve the Core Problem

Additional efficiency techniques exist but address different aspects. Reversible residual layers (Kitaev et al., 2020) reduce memory consumption during training by not storing activations, but they don't affect the underlying $O(L^2)$ attention cost — the computation is the same, just rematerialized. Shared attention weights (Xiao et al., 2019) reduce the number of attention matrices but still compute them at quadratic cost. Truncated back-propagation (Dai et al., 2019) limits gradients to local windows, but this prevents learning long-range dependencies by construction — the very thing Transformers are supposed to excel at.

The Uniqueness of the FAVOR+ Approach: What Distinguishes This Work

Given this landscape, the paper's positioning is precise. FAVOR+ is introduced as the first mechanism that simultaneously satisfies all of:

1. Provably approximates the exact same softmax attention (not a substitute or relaxation) with theoretical guarantees on the approximation quality (Theorems 2, 3, 4).
2. Achieves genuine linear complexity — $O(Lmd)$ time and $O(Ld + Lm + md)$ space — without relying on sparsity, low-rankness, or any structural priors about which tokens should attend to which.
3. Uses only non-negative feature maps (Lemma 1), avoiding the catastrophic variance and negative-renormalizer problems that plagued prior trigonometric random feature approaches.
4. Employs orthogonal random features to further reduce variance, with the paper providing the first theoretical results showing that ORFs improve softmax kernel estimation for any dimensionality $d > 0$, not just asymptotically (Theorem 2, Theorem 3).
5. Is fully compatible with the regular Transformer — even supporting transfer learning from pretrained Transformer weights with minimal fine-tuning (Figure 5, left).

The paper explicitly frames this as filling a gap that prior work left open. The approaches described above "do not aim to approximate regular attention, but rather propose simpler and more tractable attention mechanisms" (Section 1). In contrast, Performer aims to approximate the actual softmax attention that regular Transformers compute — enabling a direct drop-in replacement rather than a fundamentally different architecture. This distinction is crucial for backward compatibility and for theoretical understanding: if the goal is to understand why (and whether) softmax attention is optimal, one needs methods that can implement it efficiently enough to compare against alternatives at scale.

A Closer Look at the Failure Mode That Motivated Positive Features

The paper's central technical insight — the necessity of positive random features — emerges from a subtle but devastating failure of the obvious approach. The standard way to approximate an RBF kernel like the Gaussian kernel with random features uses $\sin$ and $\cos$ (Rahimi & Recht, 2007). Since the softmax kernel is related to the Gaussian kernel by the identity $\text{SM}(x, y) = \exp(\|x\|^2/2) \, K_{\text{gauss}}(x, y) \, \exp(\|y\|^2/2)$, one might naturally try:

$\widehat{\text{SM}}_{\text{trig}}^m(x, y) = \frac{h(x)}{m} \sum_{i=1}^m \left( \sin(\omega_i^\top x) \sin(\omega_i^\top y) + \cos(\omega_i^\top x) \cos(\omega_i^\top y) \right)$

with $h(x) = \exp(\|x\|^2/2)$ and $\omega_i \sim \mathcal{N}(0, \mathbf{I}_d)$. This is an unbiased estimator and seems natural — until you examine its behavior when the true softmax value is small.

Lemma 2 provides the rigorous explanation. The mean squared error scaling reveals the problem:

$\text{MSE}(\widehat{\text{SM}}_{\text{trig}}^m(x, y)) = \frac{1}{2m} \exp(\|x+y\|^2) \, \text{SM}^{-2}(x, y) \, (1 - \exp(-\|x-y\|^2))^2$

The critical term is $\text{SM}^{-2}(x, y)$: as the true softmax value $\text{SM}(x, y) \to 0$, the MSE blows up — tending to infinity. This is precisely what happens when two tokens are irrelevant to each other (which is most token pairs in a long sequence). The estimator, which is unbiased, achieves this unbiasedness by producing large positive and negative values that cancel on average, but any individual estimate can be wildly off. When these estimates are used in the attention mechanism — particularly in the denominator normalization $\mathbf{D} = \text{diag}(\mathbf{A} \mathbf{1}_L)$ — negative values can cause the normalization factor to become negative or near-zero, leading to training collapse.

In contrast, the positive random features derived from Lemma 1:

$\text{MSE}(\widehat{\text{SM}}_{+}^m(x, y)) = \frac{1}{m} \exp(\|x+y\|^2) \, \text{SM}^2(x, y) \, (1 - \exp(-\|x+y\|^2))$

exhibit the opposite behavior: as $\text{SM}(x, y) \to 0$, the MSE tends to zero. The variance is naturally small precisely where it matters most — in the low-attention regions that dominate the matrix $\mathbf{A}$. Figure 2 in the paper visualizes this advantage: the ratio of trigonometric to positive feature MSEs (their "symmetrized utility function") shows that positive features are "arbitrarily more accurate" for large angles $\phi$ between input vectors, which is exactly where the softmax kernel values are small.

The "Generalized Attention" Perspective: Kernels Beyond Softmax

The paper also positions FAVOR+ as enabling a broader investigation. By decoupling the efficiency mechanism (random feature approximation) from the specific choice of attention kernel, Performers can implement what the paper calls Generalized Attention (Section 2.2): any kernel $\mathcal{K}(q_i^\top, k_j^\top)$ that can be expressed as an expectation $\mathbb{E}[\phi(q_i)^\top \phi(k_j)]$ becomes computationally tractable. This includes ReLU, exponential, absolute value, sigmoid, GELU, and other nonlinearities (explored in Appendix D.3, Figures 16-17).

This is significant because prior work could not fair-compare softmax against alternative attention kernels at scale — the quadratic cost made large-scale comparisons infeasible, and linear-complexity alternatives like the Linear Transformer used different, non-softmax kernels by necessity. FAVOR+ enables the first apples-to-apples comparison: all kernels, including softmax, can be implemented with identical linear complexity, making it possible to ask whether softmax is actually optimal. The protein modeling results in Figure 6 provide an intriguing answer: Performer-ReLU (using $f = \text{ReLU}$ as the feature map in Equation 5) achieves higher accuracy than both the softmax-approximating Performer and the exact-softmax Transformer on the TrEMBL benchmark, suggesting that for this domain at least, alternative kernels may be superior — a finding that could only be discovered because FAVOR+ made the comparison feasible.

Summary of the Positioning

The paper sits at the intersection of three research threads that had previously been disconnected:

1. The practical need for efficient Transformers in long-sequence domains (bioinformatics, high-resolution images, long documents), where existing methods imposed restrictive structural assumptions or suffered from instability.
2. The theoretical framework of kernel methods and random features, which provides provable approximation guarantees but had not been successfully adapted to the softmax kernel's specific challenges (non-negativity requirement, variance near zero).
3. The empirical question of optimal attention kernels, which could not be rigorously studied at scale because no method existed to approximate softmax with both linear complexity and strong approximation guarantees.

The Performer with FAVOR+ is positioned as the synthesis that resolves all three: a drop-in replacement for softmax attention (backward compatible), with linear complexity (practical for long sequences), theoretical guarantees on approximation quality (unbiased or nearly unbiased, with uniform convergence), and the flexibility to explore alternative kernels (through the generalized attention framework).

3. Technical Approach

3.1 Reader Orientation

The paper builds a drop-in replacement for the Transformer attention mechanism called the Performer, which computes approximate softmax attention in linear rather than quadratic time and space with respect to sequence length, while providing formal guarantees on approximation quality. The core idea is to replace the explicit construction of the $L \times L$ attention matrix $\mathbf{A} = \exp(\mathbf{Q}\mathbf{K}^\top / \sqrt{d})$ with a low-rank factorization obtained through random feature maps — essentially, projecting the queries and keys into a higher-dimensional space where the dot-product recovers the softmax kernel in expectation, then exploiting the associativity of matrix multiplication to avoid ever materializing the full attention matrix. The critical innovations that make this work where prior random feature approaches failed are (1) positive random features that produce only non-negative values (avoiding catastrophic variance when approximating near-zero attention weights), and (2) orthogonal random projections that further reduce estimator variance, enabling the use of far fewer random features than would otherwise be necessary.

3.2 Big-Picture Architecture (Diagram in Words)

The Performer modifies only the attention sub-layer of the Transformer; all other components (MLP layers, layer normalization, residual connections, positional encodings) remain identical to the standard architecture. The system has four major components:

1. Query/Key/Value Projection (unchanged from standard Transformer). The input sequence $\mathbf{X} \in \mathbb{R}^{L \times d}$ is linearly projected to produce queries $\mathbf{Q}$, keys $\mathbf{K}$, and values $\mathbf{V}$, each of shape $\mathbb{R}^{L \times d}$. This step is identical to the regular Transformer and carries the same $O(Ld^2)$ cost.

2. Random Feature Map $\phi: \mathbb{R}^d \to \mathbb{R}^r_+$ (the core innovation). Each query row $\mathbf{q}_i$ and key row $\mathbf{k}_j$ is mapped through a randomized function $\phi$ that produces an $r$-dimensional vector of strictly non-negative entries. The function is constructed so that the expected dot product $\mathbb{E}[\phi(\mathbf{q}_i)^\top \phi(\mathbf{k}_j)]$ equals the softmax kernel value $\exp(\mathbf{q}_i^\top \mathbf{k}_j)$ (up to a normalization factor). Concretely, $\phi$ involves multiplying the input vector by a matrix of random projections $\boldsymbol{\omega}_1, \ldots, \boldsymbol{\omega}_r$, then applying a non-linear function (exponential for softmax, ReLU for generalized attention), and finally scaling by a norm-dependent factor. The resulting matrices $\mathbf{Q}' \in \mathbb{R}^{L \times r}$ and $\mathbf{K}' \in \mathbb{R}^{L \times r}$ contain the random features for all tokens, with $r$ chosen much smaller than $L$ (typically $r = 256$).

3. Associative Attention Computation (the linear-complexity trick). Instead of computing the $L \times L$ kernel matrix $\mathbf{Q}'(\mathbf{K}')^\top$ explicitly, the algorithm exploits the associative property of matrix multiplication. For bidirectional attention, it first computes $\mathbf{K}'^\top \mathbf{V} \in \mathbb{R}^{r \times d}$ (a "context summary" that aggregates all value vectors weighted by their key features), then multiplies by $\mathbf{Q}'$ to produce the $L \times d$ output: $\mathbf{Q}'(\mathbf{K}'^\top \mathbf{V})$. The normalization factor $\mathbf{D} = \text{diag}(\mathbf{Q}'(\mathbf{K}')^\top \mathbf{1}_L)$ is similarly computed as $\mathbf{Q}'(\mathbf{K}'^\top \mathbf{1}_L)$. For unidirectional (causal) attention, a prefix-sum mechanism achieves the same complexity by maintaining a running sum of outer products, ensuring that query $i$ only attends to keys $j \leq i$.

4. Renormalization and Output (unchanged from standard Transformer). The approximate attention output $\widehat{\mathbf{D}}^{-1} \mathbf{Q}'(\mathbf{K}'^\top \mathbf{V})$ is computed and fed into the subsequent MLP layer, exactly as in a standard Transformer. The only difference is that $\mathbf{Q}'$ and $\mathbf{K}'$ replace the original $\mathbf{Q}$ and $\mathbf{K}$ in the attention computation, and the approximate denominator $\widehat{\mathbf{D}}$ replaces the exact $\mathbf{D}$.

Information flows as follows: input embeddings → linear projections to $\mathbf{Q}, \mathbf{K}, \mathbf{V}$ → random feature mapping to $\mathbf{Q}', \mathbf{K}'$ → associative matrix multiply to compute attention output and normalization → downstream MLP layers → output. The random projection matrix $\boldsymbol{\Omega} \in \mathbb{R}^{r \times d}$ (containing the $\boldsymbol{\omega}_i$ vectors) is periodically re-drawn during training to average over approximation errors.

3.3 Roadmap for the Deep Dive

• First, the formal definition of regular (softmax) attention (Section 2.1), establishing the exact computation that FAVOR+ aims to approximate — this is essential because the entire method is built around matching this specific function, not replacing it with a different attention mechanism.
• Second, the generalized kernelizable attention framework (Section 2.2), which shows how any kernel that admits a random feature decomposition can be computed in linear time via the associative multiplication trick — this is the abstract template that FAVOR+ instantiates for the softmax kernel specifically.
• Third, the positive random feature (PRF) mechanism for the softmax kernel (Section 2.3, Lemma 1), which is the core mathematical contribution enabling unbiased, non-negative estimation — understanding why trigonometric features fail (Lemma 2) and why positive features succeed is the central insight of the paper.
• Fourth, the orthogonal random feature (ORF) enhancement (Section 2.4), which reduces estimator variance by enforcing exact orthogonality among the random projection vectors — this provides the theoretical and empirical justification for using far fewer features ($r$) than would otherwise be required.
• Fifth, the complete FAVOR+ algorithm (Algorithm 1 in Appendix B), including the bidirectional case (direct associative multiplication) and the unidirectional case (prefix-sum mechanism) — this ties together PRFs and ORFs into a concrete implementation.
• Sixth, the generalized attention extension (Equation 5), which shows that the same FAVOR+ framework can implement arbitrary kernel functions $\mathcal{K}(\mathbf{q}_i^\top, \mathbf{k}_j)$ beyond softmax, enabling the paper's empirical comparisons between attention-kernel choices at scale.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a methodological paper whose central contribution is a technique for computing approximate softmax attention in linear time. The core idea is that the softmax kernel can be expressed as an expectation over random features, and that by carefully choosing those features to be positive and orthogonal, the approximation is both practical (stable training, small $r$) and theoretically sound (unbiased estimation, uniform convergence, low variance).

---

3.4.1 Regular Attention: The Computation Being Approximated

The paper begins by formally restating the standard Transformer attention mechanism (Vaswani et al., 2017), establishing the exact function that FAVOR+ targets. Understanding this baseline is essential because FAVOR+'s goal is not to propose a new attention mechanism, but to approximate this specific one with provable guarantees.

Bidirectional (full) attention. Given query matrix $\mathbf{Q} \in \mathbb{R}^{L \times d}$, key matrix $\mathbf{K} \in \mathbb{R}^{L \times d}$, and value matrix $\mathbf{V} \in \mathbb{R}^{L \times d}$, the standard bidirectional dot-product attention is:

$\text{Att}_{\leftrightarrow}(\mathbf{Q}, \mathbf{K}, \mathbf{V}) = \mathbf{D}^{-1} \mathbf{A} \mathbf{V}$

where the attention matrix $\mathbf{A} \in \mathbb{R}^{L \times L}$ and its row-wise normalization $\mathbf{D}$ are defined as:

$\mathbf{A} = \exp\left(\frac{\mathbf{Q}\mathbf{K}^\top}{\sqrt{d}}\right)$

$\mathbf{D} = \text{diag}(\mathbf{A} \mathbf{1}_L)$

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

What these equations compute. For each pair of tokens $i$ and $j$, the unnormalized attention score is $\exp(\mathbf{q}_i^\top \mathbf{k}_j / \sqrt{d})$ — the exponentiated dot product of their query and key vectors, scaled by $1/\sqrt{d}$ to prevent the dot products from growing too large with dimensionality. The matrix $\mathbf{A}$ collects all $L \times L$ such scores. The denominator $\mathbf{D}$ normalizes each row of $\mathbf{A}$ to sum to 1 (since each row of the final $\mathbf{D}^{-1}\mathbf{A}$ is a probability distribution over the $L$ tokens). The attention output is then a weighted average of the value vectors $\mathbf{V}$, where the weights are the normalized attention scores.

Why this form (and why it's expensive). The softmax function $\exp(\mathbf{q}_i^\top \mathbf{k}_j) / \sum_k \exp(\mathbf{q}_i^\top \mathbf{k}_k)$ has properties that make it effective for attention: it's always positive (so attention weights are valid probabilities), it's monotonic in the dot product (so more similar query-key pairs get higher weight), and it's differentiable everywhere (enabling gradient-based training). But computing it requires materializing the full $L \times L$ matrix $\mathbf{A}$, which costs $O(L^2 d)$ time (for the matrix multiply $\mathbf{Q}\mathbf{K}^\top$) and $O(L^2 + Ld)$ space (for storing $\mathbf{A}$ plus the inputs and outputs). This is the quadratic bottleneck the paper seeks to eliminate.

Unidirectional (causal) attention. For autoregressive models where token $i$ can only attend to tokens $j \leq i$, the attention matrix is masked to be lower-triangular:

$\text{Att}_{\rightarrow}(\mathbf{Q}, \mathbf{K}, \mathbf{V}) = \widetilde{\mathbf{D}}^{-1} \widetilde{\mathbf{A}} \mathbf{V}$

where $\widetilde{\mathbf{A}} = \text{tril}(\mathbf{A})$ extracts the lower-triangular part (including the diagonal) and $\widetilde{\mathbf{D}} = \text{diag}(\widetilde{\mathbf{A}} \mathbf{1}_L)$ renormalizes the masked rows. The computational cost is the same $O(L^2 d)$ — the masking is a cheap elementwise operation on top of the already-expensive matrix multiplication.

A crucial practical distinction: the paper notes that the $\sqrt{d}$ scaling can be absorbed into the query and key representations (by renormalizing the input vectors), so in the subsequent analysis the softmax kernel is written without it: $\text{SM}(\mathbf{x}, \mathbf{y}) = \exp(\mathbf{x}^\top \mathbf{y})$. This simplifies the math without loss of generality.

---

3.4.2 Generalized Kernelizable Attention: The Abstract Template

Before tackling the softmax kernel specifically, the paper sets up a more general framework. The key insight is that any attention mechanism where the similarity between query $\mathbf{q}_i$ and key $\mathbf{k}_j$ is computed by a kernel function $\mathcal{K}(\mathbf{q}_i^\top, \mathbf{k}_j^\top)$ that can be expressed as an expectation of a dot product in some feature space can be computed in linear time.

The kernel decomposition assumption. The paper assumes the existence of a (possibly randomized) mapping $\phi: \mathbb{R}^d \to \mathbb{R}^r_+$ (where $r > 0$ is the feature dimension and the subscript $+$ indicates elementwise non-negativity) such that for any query $\mathbf{x}$ and key $\mathbf{y}$:

$\mathcal{K}(\mathbf{x}, \mathbf{y}) = \mathbb{E}_{\boldsymbol{\omega}}[\phi(\mathbf{x})^\top \phi(\mathbf{y})]$

where $\boldsymbol{\omega}$ denotes the random variables that parameterize $\phi$ (typically, $\phi$ involves multiplying by random projection vectors and then applying a nonlinearity). The expectation is taken over the random draws of these projection vectors.

What the equation means operationally. If we can find a feature map $\phi$ such that the expected dot product of the feature vectors equals the desired kernel value, then we can approximate the kernel by sampling finitely many random feature maps and averaging. Concretely, if we draw $m$ independent random projection vectors $\boldsymbol{\omega}_1, \ldots, \boldsymbol{\omega}_m$, define $\phi_i$ as the feature map using $\boldsymbol{\omega}_i$, and stack them as $\phi(\mathbf{x}) = \frac{1}{\sqrt{m}}[\phi_1(\mathbf{x}); \ldots; \phi_m(\mathbf{x})]$, then $\phi(\mathbf{x})^\top \phi(\mathbf{y})$ is an unbiased estimator of the kernel. The total feature dimension is $r = m \cdot l$ where $l$ is the output dimension of each individual $\phi_i$ (e.g., $l = 1$ or $l = 2$ depending on the construction).

The linear-complexity attention computation (the FA-part of FAVOR+). Given feature matrices $\mathbf{Q}' \in \mathbb{R}^{L \times r}$ and $\mathbf{K}' \in \mathbb{R}^{L \times r}$ where the $i$-th row of $\mathbf{Q}'$ is $\phi(\mathbf{q}_i^\top)^\top$ and similarly for $\mathbf{K}'$, the approximate attention becomes:

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

$\widehat{\mathbf{D}} = \text{diag} \left( \mathbf{Q}' \left( (\mathbf{K}')^\top \mathbf{1}_L \right) \right)$

where the brackets indicate the order of computation.

What this computes — the associativity trick. The critical property is that matrix multiplication is associative: $(\mathbf{Q}'(\mathbf{K}')^\top)\mathbf{V} = \mathbf{Q}'((\mathbf{K}')^\top\mathbf{V})$. The left side would require forming the $L \times L$ matrix $\mathbf{Q}'(\mathbf{K}')^\top$ first, costing $O(L^2 r)$ — no better than the original quadratic attention. The right side instead first computes $(\mathbf{K}')^\top \mathbf{V}$, which is an $r \times d$ matrix (size independent of $L$), costing $O(Lrd)$, then multiplies by $\mathbf{Q}'$, costing another $O(Lrd)$. The total time is $O(Lrd)$ rather than $O(L^2 r)$ or $O(L^2 d)$. Similarly, the normalization term $\widehat{\mathbf{D}}$ is computed as $\mathbf{Q}'((\mathbf{K}')^\top \mathbf{1}_L)$, where $(\mathbf{K}')^\top \mathbf{1}_L$ is an $r$-dimensional vector representing the sum of all key features.

The space complexity drops from $O(L^2 + Ld)$ to $O(Lr + Ld + rd)$ because the $L \times L$ attention matrix is never stored — only the intermediate $r \times d$ and $r \times 1$ aggregates need to be kept. Figure 1 in the paper illustrates this flow visually: the dashed blocks show that the computation proceeds left-to-right, first multiplying $\mathbf{K}'^\top$ with $\mathbf{V}$ (an $r \times d$ matrix) and then multiplying the result by $\mathbf{Q}'$.

Why this is the core efficiency mechanism. By reordering the matrix multiplications, the $L \times L$ bottleneck disappears entirely — but this only works if the attention kernel decomposes as a dot product of feature vectors. The remaining challenge (which occupies the rest of the paper) is to find a feature map $\phi$ for the softmax kernel specifically that satisfies: (1) the dot product $\phi(\mathbf{x})^\top \phi(\mathbf{y})$ is an unbiased estimator of $\exp(\mathbf{x}^\top \mathbf{y})$, (2) the entries of $\phi(\mathbf{x})$ are always non-negative (so the renormalization $\widehat{\mathbf{D}}$ is well-behaved), and (3) the variance of the estimator is low enough that a small $r$ (much less than $L$) suffices for accurate approximation.

A subtle but important point about the normalization. In the standard attention, $\mathbf{D} = \text{diag}(\mathbf{A} \mathbf{1}_L)$ normalizes each row to sum to 1. In the approximate version, $\widehat{\mathbf{D}}$ is itself an approximation — it is the diagonal of $\mathbf{Q}'(\mathbf{K}')^\top \mathbf{1}_L$, which is the approximate version of $\mathbf{A} \mathbf{1}_L$. The paper includes a renormalize_attention flag (set to True by default, as noted in Appendix A.3) that controls whether this normalization is applied. When disabled, the output is simply $\mathbf{Q}'(\mathbf{K}')^\top \mathbf{V}$ without row-wise normalization, which the paper notes "does not necessarily hurt accuracy" in some settings (Appendix D.3).

---

3.4.3 The Softmax Kernel Approximation: From Trigonometric Failure to Positive Success

This section is the mathematical heart of the paper. The challenge is to construct a feature map $\phi$ such that $\mathbb{E}[\phi(\mathbf{x})^\top \phi(\mathbf{y})]$ equals $\exp(\mathbf{x}^\top \mathbf{y})$, while ensuring that all components of $\phi$ are non-negative and the estimator has low variance.

The general random feature construction (Equation 5). The paper first presents a general template for constructing random feature maps. For functions $f_1, \ldots, f_l: \mathbb{R} \to \mathbb{R}$, a scaling function $h: \mathbb{R}^d \to \mathbb{R}$, and random vectors $\boldsymbol{\omega}_1, \ldots, \boldsymbol{\omega}_m \overset{\text{iid}}{\sim} \mathcal{D}$ drawn from some isotropic distribution $\mathcal{D}$ (meaning its probability density depends only on the norm of the vector, i.e., is constant on spheres):

$\phi(\mathbf{x}) = \frac{h(\mathbf{x})}{\sqrt{m}} \left( f_1(\boldsymbol{\omega}_1^\top \mathbf{x}), \ldots, f_1(\boldsymbol{\omega}_m^\top \mathbf{x}), \ldots, f_l(\boldsymbol{\omega}_1^\top \mathbf{x}), \ldots, f_l(\boldsymbol{\omega}_m^\top \mathbf{x}) \right)$

The total feature dimension is $r = m \cdot l$. The $\boldsymbol{\omega}_i$ are the random projection vectors, and each $f_j$ is a univariate nonlinearity applied to the projection.

How this template covers known kernels. With $h(\mathbf{x}) = 1$, $l = 1$, $f_1 = \text{sgn}$, the model approximates the angular kernel. With $h(\mathbf{x}) = 1$, $l = 2$, $f_1 = \sin$, $f_2 = \cos$, and $\mathcal{D} = \mathcal{N}(0, \mathbf{I}_d)$, the model approximates the Gaussian kernel $K_{\text{gauss}}(\mathbf{x}, \mathbf{y}) = \exp(-\|\mathbf{x} - \mathbf{y}\|^2 / 2)$ — this is the classic Random Fourier Features method of Rahimi & Recht (2007). The softmax kernel is related to the Gaussian kernel by the identity:

$\text{SM}(\mathbf{x}, \mathbf{y}) = \exp(\mathbf{x}^\top \mathbf{y}) = \exp\left(\frac{\|\mathbf{x}\|^2}{2}\right) \cdot \exp\left(-\frac{\|\mathbf{x} - \mathbf{y}\|^2}{2}\right) \cdot \exp\left(\frac{\|\mathbf{y}\|^2}{2}\right)$

So in principle, one could approximate the Gaussian kernel with $\sin$/$\cos$ features and multiply by the norm-dependent scaling factors to get a softmax approximation. This yields the estimator:

$\widehat{\text{SM}}_{\text{trig}}^m(\mathbf{x}, \mathbf{y}) = \exp\left(\frac{\|\mathbf{x}\|^2 + \|\mathbf{y}\|^2}{2}\right) \cdot \frac{1}{m} \sum_{i=1}^m \left( \sin(\boldsymbol{\omega}_i^\top \mathbf{x}) \sin(\boldsymbol{\omega}_i^\top \mathbf{y}) + \cos(\boldsymbol{\omega}_i^\top \mathbf{x}) \cos(\boldsymbol{\omega}_i^\top \mathbf{y}) \right)$

with $\boldsymbol{\omega}_i \sim \mathcal{N}(0, \mathbf{I}_d)$.

Why this fails: the negative-value and variance problems. The $\sin$ and $\cos$ functions produce both positive and negative values. An individual estimate $\widehat{\text{SM}}_{\text{trig}}^m(\mathbf{x}, \mathbf{y})$ can therefore be negative, even though the true softmax value is always positive. This is catastrophic in the attention mechanism because the normalization denominator $\widehat{\mathbf{D}}$ is computed by summing these estimates: if enough entries are negative, the denominator can become negative or near-zero, producing either invalid probability distributions or division-by-zero errors. The paper documents this failure empirically: trigonometric softmax features cause "highly unstable training" and even NaN values (Figure 5, right; Appendix D.3).

But there is a deeper theoretical reason for the failure, captured in Lemma 2. The mean squared error of the trigonometric estimator is:

$\text{MSE}(\widehat{\text{SM}}_{\text{trig}}^m(\mathbf{x}, \mathbf{y})) = \frac{1}{2m} \exp(\|\mathbf{x} + \mathbf{y}\|^2) \cdot \text{SM}^{-2}(\mathbf{x}, \mathbf{y}) \cdot (1 - \exp(-\|\mathbf{x} - \mathbf{y}\|^2))^2$

What this equation means — the inverse relationship with kernel value. The critical term is $\text{SM}^{-2}(\mathbf{x}, \mathbf{y})$. The Mean Squared Error is inversely proportional to the square of the softmax kernel value. As $\text{SM}(\mathbf{x}, \mathbf{y}) \to 0$ (which happens when $\mathbf{x}^\top \mathbf{y}$ is very negative — tokens are dissimilar), the MSE blows up to infinity. This is exactly the regime that dominates attention matrices for long sequences: most token pairs are irrelevant to each other, so most entries of $\mathbf{A}$ are very small. The estimator, while unbiased, achieves this unbiasedness by producing large positive and negative values that cancel on average — but any individual estimate can be wildly wrong, and these individual errors accumulate in the attention computation. The paper's Figure 2 (right) visualizes this: for angles $\phi$ near $\pm\pi$ (where cosine is near $-1$ and softmax is near zero), the MSE ratio between trigonometric and positive features diverges.

The positive random feature solution (Lemma 1). The paper derives an alternative decomposition that produces only non-negative estimates. The key algebraic identity is:

$\text{SM}(\mathbf{x}, \mathbf{y}) = \exp(\mathbf{x}^\top \mathbf{y}) = \exp\left(-\frac{\|\mathbf{x}\|^2 + \|\mathbf{y}\|^2}{2}\right) \cdot \mathbb{E}_{\boldsymbol{\omega} \sim \mathcal{N}(0, \mathbf{I}_d)}\left[ \exp(\boldsymbol{\omega}^\top (\mathbf{x} + \mathbf{y})) \right]$

This identity is proven by completing the square: $\exp(\mathbf{x}^\top \mathbf{y}) = \exp(-\|\mathbf{x}\|^2/2) \cdot \exp(\|\mathbf{x} + \mathbf{y}\|^2/2) \cdot \exp(-\|\mathbf{y}\|^2/2)$, and then using the Gaussian integral $\exp(\|\mathbf{z}\|^2/2) = \mathbb{E}_{\boldsymbol{\omega} \sim \mathcal{N}(0,\mathbf{I}_d)}[\exp(\boldsymbol{\omega}^\top \mathbf{z})]$ for $\mathbf{z} = \mathbf{x} + \mathbf{y}$.

What this yields operationally. The identity naturally suggests a feature map of the form:

$\phi_+(\mathbf{x}) = \exp\left(-\frac{\|\mathbf{x}\|^2}{2}\right) \cdot \exp(\boldsymbol{\omega}^\top \mathbf{x})$

where $\boldsymbol{\omega} \sim \mathcal{N}(0, \mathbf{I}_d)$. Then $\mathbb{E}[\phi_+(\mathbf{x}) \cdot \phi_+(\mathbf{y})] = \text{SM}(\mathbf{x}, \mathbf{y})$. The crucial property is that $\exp(\boldsymbol{\omega}^\top \mathbf{x})$ is always positive, regardless of the sign of $\boldsymbol{\omega}^\top \mathbf{x}$. The factor $\exp(-\|\mathbf{x}\|^2/2)$ is also always positive. So every entry of $\phi_+(\mathbf{x})$ is strictly non-negative — there are no negative values that could destabilize the normalization.

The resulting estimator using $m$ independent samples $\boldsymbol{\omega}_1, \ldots, \boldsymbol{\omega}_m$ is:

$\widehat{\text{SM}}_{+}^m(\mathbf{x}, \mathbf{y}) = \frac{1}{m} \exp\left(-\frac{\|\mathbf{x}\|^2 + \|\mathbf{y}\|^2}{2}\right) \sum_{i=1}^m \exp(\boldsymbol{\omega}_i^\top \mathbf{x}) \exp(\boldsymbol{\omega}_i^\top \mathbf{y})$

which corresponds to the general template with $h(\mathbf{x}) = \exp(-\|\mathbf{x}\|^2/2)$, $l = 1$, $f_1 = \exp$, and $\mathcal{D} = \mathcal{N}(0, \mathbf{I}_d)$.

The alternative hyperbolic cosine formulation for variance reduction. Lemma 1 also provides a second formulation using the identity $\mathbb{E}[\exp(\boldsymbol{\omega}^\top \mathbf{z})] = \mathbb{E}[\cosh(\boldsymbol{\omega}^\top \mathbf{z})]$ (because the odd moments of an isotropic Gaussian vanish, as shown in Equation 12). This leads to:

$\widehat{\text{SM}}_{\text{hyp}+}^m(\mathbf{x}, \mathbf{y}) = \frac{1}{\sqrt{2}} \exp\left(-\frac{\|\mathbf{x}\|^2 + \|\mathbf{y}\|^2}{2}\right) \cdot \frac{1}{m} \sum_{i=1}^m \left( \exp(\boldsymbol{\omega}_i^\top (\mathbf{x} + \mathbf{y})) + \exp(-\boldsymbol{\omega}_i^\top (\mathbf{x} + \mathbf{y})) \right)$

This uses $l = 2$ with $f_1(u) = \exp(u)/\sqrt{2}$ and $f_2(u) = \exp(-u)/\sqrt{2}$, and provides additional variance reduction beyond the basic positive estimator — specifically, Lemma 2 shows that $\text{MSE}(\widehat{\text{SM}}_{\text{hyp}+}^m) = \frac{1}{2}(1 - \exp(-\|\mathbf{x} + \mathbf{y}\|^2)) \cdot \text{MSE}(\widehat{\text{SM}}_{+}^m)$, meaning the hyperbolic estimator's MSE is always at most half that of the basic positive estimator.

Why the variance behavior matters (Lemma 2, continued). The mean squared error of the positive estimator scales as:

$\text{MSE}(\widehat{\text{SM}}_{+}^m(\mathbf{x}, \mathbf{y})) = \frac{1}{m} \exp(\|\mathbf{x} + \mathbf{y}\|^2) \cdot \text{SM}^2(\mathbf{x}, \mathbf{y}) \cdot (1 - \exp(-\|\mathbf{x} + \mathbf{y}\|^2))$

Contrast with trigonometric features. Here the MSE contains $\text{SM}^2(\mathbf{x}, \mathbf{y})$ in the numerator (not the denominator), so as $\text{SM}(\mathbf{x}, \mathbf{y}) \to 0$, the MSE tends to zero. This is the exact opposite of the trigonometric estimator's behavior. In the critical regime where most attention weights are near zero, the positive estimator is naturally precise — its variance is small precisely where it needs to be small. The paper summarizes this succinctly: "for $\text{SM}(x, y) \to 0$ we have: $\text{MSE}(\widehat{\text{SM}}_{\text{trig}}^m(x, y)) \to \infty$ and $\text{MSE}(\widehat{\text{SM}}_{+}^m(x, y)) \to 0$" (Lemma 2 statement).

The regularized softmax kernel (Theorem 1). The paper also introduces a variant where the Gaussian distribution $\mathcal{N}(0, \mathbf{I}_d)$ is replaced with the uniform distribution on the sphere of radius $\sqrt{d}$, denoted $\text{Unif}(\sqrt{d} \, \mathbb{S}^{d-1})$. This produces the regularized softmax kernel $\text{SMREG}$, which Theorem 1 proves is a universal lower bound for the standard softmax kernel (i.e., $\text{SMREG}(\mathbf{x}, \mathbf{y}) \leq \text{SM}(\mathbf{x}, \mathbf{y})$ for all $\mathbf{x}, \mathbf{y}$) and satisfies:

$\inf_{i, j} \frac{\text{SMREG}(i, j)}{\text{SM}(i, j)} \geq 1 - \frac{2}{d^{1/3}} + o\left(\frac{1}{d^{1/3}}\right)$

What this bound means. For typical hidden dimensions $d = 512$ or $d = 256$, the ratio is very close to 1 (e.g., for $d = 512$, $1 - 2/512^{1/3} \approx 1 - 2/8 = 0.75$, and the higher-order terms make it tighter). So the regularized kernel is an excellent approximation to the standard softmax, and the positive random features for $\text{SMREG}$ inherit the same nice variance properties. Experimentally, Figure 5 (right) shows that $\text{SMREG}$ allows "faster convergence" than the standard positive softmax approximation.

---

3.4.4 Orthogonal Random Features: Variance Reduction Through Structured Projections

Even with positive features, the estimator's variance might still require a large number of random features $m$ to achieve acceptable approximation quality. The paper's second major innovation is to enforce exact orthogonality among the random projection vectors, a technique that provably reduces variance for any dimensionality $d > 0$.

What orthogonal random features (ORFs) are. Instead of sampling $\boldsymbol{\omega}_1, \ldots, \boldsymbol{\omega}_m \overset{\text{iid}}{\sim} \mathcal{D}$ independently, the ORF method generates $\boldsymbol{\omega}_1, \ldots, \boldsymbol{\omega}_m$ that are simultaneously (1) marginally distributed as $\mathcal{D}$ (i.e., each individual vector follows the correct distribution) and (2) pairwise orthogonal: $\boldsymbol{\omega}_i^\top \boldsymbol{\omega}_j = 0$ for all $i \neq j$. This can be achieved by first sampling $m$ independent vectors from $\mathcal{D}$, then applying the Gram-Schmidt orthogonalization procedure, and finally rescaling to restore the correct marginal norms (the paper cites Yu et al., 2016 and Choromanski et al., 2017 for the detailed construction). The constraint $m \leq d$ is required since you cannot have more than $d$ mutually orthogonal vectors in $\mathbb{R}^d$ — but this is satisfied in all the paper's experiments where $m = 256$ (the default) and $d = 512$.

Why orthogonality helps — the theoretical guarantee (Theorem 2). For the positive random feature estimator $\widehat{\text{SM}}_{+}^m$, Theorem 2 states that the orthogonal variant $\widehat{\text{SM}}_{\text{ort}+}^m$ satisfies, for any $d > 0$ and $m \leq d$:

$\text{MSE}(\widehat{\text{SM}}_{\text{ort}+}^m(\mathbf{x}, \mathbf{y})) \leq \text{MSE}(\widehat{\text{SM}}_{+}^m(\mathbf{x}, \mathbf{y})) - \frac{2(m - 1)}{m(d + 2)} \left( \text{SM}(\mathbf{x}, \mathbf{y}) - \exp\left(-\frac{\|\mathbf{x}\|^2 + \|\mathbf{y}\|^2}{2}\right) \right)^2$

What this equation says. The orthogonal estimator's MSE is strictly less than the independent estimator's MSE, and the improvement is explicitly quantified. The subtracted term depends on (1) the degree of orthogonality (larger $m$ gives a larger factor $(m-1)/m$, approaching 1), (2) the dimensionality $d$ (the improvement is larger in lower dimensions since the $1/(d+2)$ factor), and (3) the squared difference between the kernel value and the baseline $\exp(-(\|\mathbf{x}\|^2 + \|\mathbf{y}\|^2)/2)$.

Why this result is novel. The paper emphasizes that prior work on ORFs for kernel approximation (Yu et al., 2016; Choromanski et al., 2018b) provided variance reduction guarantees only asymptotically for $d \to \infty$. Theorem 2 is the first result showing that ORFs reduce variance for any finite $d > 0$, which is crucial for practical Transformer applications where $d$ is typically 256–1024. The proof (in Appendix F.4) relies on a novel decomposition of the variance gap in terms of "beautiful functions" (Definition 1 in Appendix F.4) — functions that can be expressed as expectations of entire functions with non-negative power series coefficients under isotropic distributions.

Sharper tail bounds via orthogonality (Theorem 3). For the regularized softmax kernel, orthogonality provides an even stronger guarantee: exponentially small bounds on the probability that the estimator exceeds any threshold, and these bounds are strictly tighter than for independent features for every $d > 0$. The paper calls these "the first exponentially small bounds for probabilities of estimators' tails that are strictly better than for non-orthogonal variants for every $d > 0$."

Practical ORF variants (Appendix B.2). The paper describes three concrete implementations with different time-space tradeoffs:

• Regular ORFs (R-ORFs): Use Gaussian orthogonal matrices. Require $O(md)$ space to encode the projection matrix and $O(md)$ time per forward pass, plus a one-time $O(md^2)$ preprocessing cost for Gram-Schmidt orthogonalization. Provide unbiased estimation.

• Hadamard ORFs (H-ORFs): Use random Hadamard matrices (Choromanski et al., 2017). Encode the matrix in only $O(m)$ space and compute $\mathbf{W}\mathbf{x}$ in $O(m \log d)$ time. The tradeoff is a small bias that tends to zero as $d \to \infty$.

• Givens ORFs (G-ORFs): Use random Givens rotation matrices (Choromanski et al., 2019b). Encode in $O(m \log d)$ space, compute in $O(m \log d)$ time, with similar asymptotic unbiasedness.

The default configuration (Appendix A.3) uses ortho_features = True with ortho_scaling = 0.0 (the R-ORF variant), and the number of random features is set to number of features = 256.

Empirical validation of ORFs + PRFs (Figure 4). The paper demonstrates the combined effect: Figure 4 (left) shows that orthogonal features consistently produce lower MSE than independent (IID) features for the same number of random samples $m$, and Figure 4 (right) shows that positive features (both with and without orthogonality) produce far lower MSE than trigonometric features. The combination — positive orthogonal random features (PORF) — achieves the best of both: low variance from positivity and further variance reduction from orthogonality.

---

3.4.5 The Complete FAVOR+ Algorithm

Putting together the positive random features (R+) and orthogonal random features (O) yields the complete FAVOR+ mechanism (Fast Attention Via positive Orthogonal Random features). Algorithm 1 in Appendix B provides the pseudocode.

Inputs and setup. The algorithm takes as input the query, key, and value matrices $\mathbf{Q}, \mathbf{K}, \mathbf{V} \in \mathbb{R}^{L \times d}$ and a boolean flag isBidirectional. The first step is to compute the feature matrices $\mathbf{Q}'$ and $\mathbf{K}'$:

$\mathbf{Q}' = \phi(\mathbf{Q}), \quad \mathbf{K}' = \phi(\mathbf{K})$

where $\phi$ is constructed according to the desired kernel (typically the positive softmax map from Lemma 1, with $m$ orthogonal projection vectors). The feature dimension $r$ equals $m \cdot l$ where $l$ is the number of nonlinearities (e.g., $l = 1$ for basic positive features, $l = 2$ for hyperbolic features, $l = 1$ for the ReLU generalized kernel).

Bidirectional case (the simple path). For bidirectional attention (encoder self-attention, encoder-decoder attention), the algorithm performs two matrix multiplications:

1. Compute the key-value aggregate: $\mathbf{B}_1 = (\mathbf{K}')^\top \mathbf{C} \in \mathbb{R}^{r \times (d+1)}$, where $\mathbf{C} = [\mathbf{V} \; \mathbf{1}_L] \in \mathbb{R}^{L \times (d+1)}$ is the value matrix augmented with an extra column of all ones. This step costs $O(Lrd)$ — linear in $L$ because $\mathbf{K}'$ is $L \times r$ and $\mathbf{C}$ is $L \times (d+1)$.

2. Compute the output: $\mathbf{B}_2 = \mathbf{Q}' \mathbf{B}_1 \in \mathbb{R}^{L \times (d+1)}$. This also costs $O(Lrd)$.

The resulting matrix $\mathbf{B}_2$ contains the unnormalized attention output in the first $d$ columns (call this $\mathbf{B}_3 \in \mathbb{R}^{L \times d}$) and the approximate row sums in the last column (call this $\mathbf{b}_4 \in \mathbb{R}^L$). The final output is $\text{diag}(\mathbf{b}_4)^{-1} \mathbf{B}_3$ — each row is divided by its corresponding approximate row sum, exactly mirroring the $\mathbf{D}^{-1}\mathbf{A}\mathbf{V}$ normalization of standard attention.

Why augmenting with ones works. The product $\mathbf{Q}'(\mathbf{K}')^\top \mathbf{1}_L$ computes the vector of row sums of the approximate kernel matrix. By including $\mathbf{1}_L$ as an extra column of $\mathbf{C}$, this computation is done simultaneously with the value-weighted computation $\mathbf{Q}'(\mathbf{K}')^\top \mathbf{V}$ in a single matrix multiplication, avoiding a separate pass. The cost is negligible — increasing the inner dimension from $d$ to $d+1$.

Unidirectional case (the prefix-sum path). For causal attention (autoregressive generation), the lower-triangular masking complicates matters because the associative trick only works cleanly for full matrix multiplication. The solution uses prefix sums (also called cumulative sums or parallel scans). For each position $i$, the output should be:

$[\text{tril}(\mathbf{Q}'(\mathbf{K}')^\top) \mathbf{C}]_i = \left( \sum_{j=1}^i \mathbf{K}'_j \mathbf{C}_j^\top \right) \mathbf{Q}'_i$

where $\mathbf{K}'_j$ is the $j$-th row of $\mathbf{K}'$ (as a column vector), $\mathbf{C}_j$ is the $j$-th row of $\mathbf{C}$, and $\mathbf{Q}'_i$ is the $i$-th row of $\mathbf{Q}'$. The outer product $\mathbf{K}'_j \mathbf{C}_j^\top$ is an $r \times (d+1)$ matrix, and summing these over $j=1,\ldots,i$ gives the cumulative key-value aggregate up to position $i$.

The prefix-sum tensor. Define a 3-dimensional tensor $\mathbf{G} \in \mathbb{R}^{L \times r \times (d+1)}$ where the $j$-th slice is $\mathbf{G}_{j,:,:} = \mathbf{K}'_j \mathbf{C}_j^\top \in \mathbb{R}^{r \times (d+1)}$. Then the prefix-sum tensor $\mathbf{G}^{\text{PS}} \in \mathbb{R}^{L \times r \times (d+1)}$ is defined elementwise as:

$\mathbf{G}^{\text{PS}}_{i, \ell, p} = \sum_{j=1}^i \mathbf{G}_{j, \ell, p}$

for each feature index $\ell \in \{1, \ldots, r\}$ and each value/ones index $p \in \{1, \ldots, d+1\}$. Computing this prefix sum for all $L$ positions takes $O(L)$ total steps and $O(\log L)$ time when parallelized (the standard parallel prefix-sum algorithm, Ladner & Fischer, 1980). The output is then:

\mathbf{B}_2 = \left[ \mathbf{G}^{\text{PS}}_{1,:,:} \mathbf{Q}'_1^\top, \ldots, \mathbf{G}^{\text{PS}}_{L,:,:} \mathbf{Q}'_L^\top \right]^\top \in \mathbb{R}^{L \times (d+1)}

where each row is the product of the corresponding query feature vector with the cumulative aggregate for that position. The final normalization proceeds identically to the bidirectional case.

Space complexity of the unidirectional variant. Storing the full prefix-sum tensor $\mathbf{G}^{\text{PS}}$ requires $O(Lrd)$ space (specifically $L \cdot r \cdot (d+1)$), which is larger than the bidirectional variant's $O(Lr + Ld + rd)$. However, the paper notes that this can be reduced to $O(Lr + Ld + rd)$ by computing the prefix sum "without storing the whole tensor $\mathbf{G}^{\text{PS}}$ in memory" — essentially streaming the computation and aggregating on the fly. The cost is that this sequential version is not parallel in $L$, trading parallelism for memory.

Total time and space complexity. The dominant cost is constructing $\mathbf{Q}'$ and $\mathbf{K}'$, which requires multiplying the input matrices by the random projection matrix $\boldsymbol{\Omega} \in \mathbb{R}^{r \times d}$, costing $O(Lrd)$. The subsequent associative multiplication costs another $O(Lrd)$. With orthogonal random features using R-ORFs, there is an additional one-time $O(rd^2)$ preprocessing cost (Gram-Schmidt), which is negligible compared to the $O(Lrd)$ term when $L \gg d$. If H-ORFs or G-ORFs are used instead, the preprocessing cost is eliminated and the per-token cost drops to $O(L \log(r) d)$ rather than $O(Lrd)$ — a constant-factor improvement that "might play an important role in training very large models" (Appendix B.3).

Key default hyperparameters (Appendix A.3). For approximate softmax attention, the defaults are: renormalize_attention = True, numerical_stabilizer = 10^{-6}, number_of_features = 256, ortho_features = True, ortho_scaling = 0.0. The numerical stabilizer is a small constant added to the denominator to prevent division by zero in edge cases.

---

3.4.6 Generalized Attention: Kernels Beyond Softmax

While the softmax approximation is the primary theoretical contribution, the paper emphasizes that FAVOR+ is applicable to a much broader class of attention functions. The general template from Equation 5 can be instantiated with any univariate function $f$ to produce a kernel:

$\mathcal{K}(\mathbf{x}, \mathbf{y}) = \mathbb{E}_{\boldsymbol{\omega}}[f(\boldsymbol{\omega}^\top \mathbf{x}) f(\boldsymbol{\omega}^\top \mathbf{y})]$

By choosing different $f$ and different distributions $\mathcal{D}$ for $\boldsymbol{\omega}$, the Performer can implement attention mechanisms with different inductive biases — all with the same $O(Lrd)$ complexity.

The ReLU kernel and its empirical success. The paper's experiments (Section 4.4, Figure 6) show that on protein sequence modeling with the TrEMBL dataset, a Performer using $f = \text{ReLU}$ (rectified linear unit) as the feature map actually outperforms both the softmax-approximating Performer and the exact-softmax Transformer. Specifically, "Performer-RELU (taking $f = \text{ReLU}$ in Equation 5) achiev[es] the highest accuracy in both (U) and (B) cases" (Section 4.4). On the test set, Performer-ReLU achieves 31.58% accuracy (unidirectional) and 36.09% (bidirectional), compared to Transformer's 30.80% and 33.32% respectively (Table 2).

Why this is significant. This finding challenges the assumption that softmax attention is optimal. It suggests that for certain data distributions — particularly protein sequences with their specific amino acid interaction patterns — a ReLU-based kernel may be more appropriate. The paper's framework makes this kind of comparison feasible for the first time because both softmax and ReLU attention can be implemented with identical linear complexity, allowing fair head-to-head comparisons at scale that were impossible with quadratic softmax attention.

Additional kernels explored (Appendix D.3, Figures 16–17). The paper systematically sweeps over kernel functions including sigmoid, exponential, ReLU, absolute value ($|x|$), GELU, cosine (the softmax approximation), tanh, and identity. The experimental results on TrEMBL show:

• Several kernels produce NaN errors during training (sigmoid, exponential, tanh, identity), causing runs to "stop early" (Figure 16, log-scale axes).
• The ReLU kernel with renormalization enabled achieves the best training accuracy among all tested kernels.
• Disabling renormalization (i.e., not applying $\mathbf{D}^{-1}$) "does not necessarily hurt accuracy" and in some configurations performs comparably to the renormalized version (Figure 17).

Generalized attention default hyperparameters (Appendix A.4). The default configuration for generalized attention is: renormalize_attention = True, numerical_stabilizer = 0.0 (contrast with $10^{-6}$ for softmax), number_of_features = 256, kernel = ReLU, kernel_epsilon = 10^{-3}. The kernel_epsilon is a small constant added inside the ReLU: $f(x) = \max(0, x) + \epsilon$, ensuring that the feature map always produces strictly positive outputs even when $\boldsymbol{\omega}^\top \mathbf{x} \leq 0$. This prevents degenerate cases where a token's entire feature vector is zero.

Connecting generalized attention to the kernel framework. Any choice of $f$ corresponds to a specific kernel $\mathcal{K}$ implicitly defined by the expectation $\mathbb{E}[f(\boldsymbol{\omega}^\top \mathbf{x}) f(\boldsymbol{\omega}^\top \mathbf{y})]$. For the ReLU kernel with Gaussian $\boldsymbol{\omega}$, this kernel can be computed in closed form (see Cho & Saul, 2009 for the "arc-cosine kernel"), but the paper does not need the explicit form — the FAVOR+ mechanism works directly with the feature map, never computing the kernel matrix explicitly. This is a key advantage: the kernel only needs to be implicitly representable via a random feature map, not analytically tractable.

---

3.4.7 Feature Redrawing: Averaging Over Approximation Errors

A practical consideration that the paper addresses is the need to periodically redraw the random projection vectors during training. Since any particular draw of $\boldsymbol{\omega}_1, \ldots, \boldsymbol{\omega}_m$ induces a specific approximation error at each attention computation, using the same random features throughout training can lead to systematic biases that accumulate across layers and optimization steps.

The redrawing mechanism. Periodically (the paper does not specify an exact schedule, but Figure 15, left, shows redrawing at a specific training step marked by a vertical line), the random projection matrix $\boldsymbol{\Omega}$ is resampled. This means that the feature maps $\phi$ change, and consequently the approximate attention output changes even for the same input embeddings. The effect is to average the approximation errors over the course of training — different random draws will over-approximate or under-approximate different token pairs, and the model learns to be robust to this variability.

Empirical necessity. Figure 5 (right) demonstrates this dramatically on the PG-19 dataset: "Positive softmax with feature redrawing is necessary to match the Transformer." Without redrawing, even positive features plateau at a suboptimal perplexity. Figure 15 (left) provides further evidence: two different fixed random seeds produce divergent training trajectories — one stalls early, while the other trains normally. Redrawing effectively prevents the model from being stuck with an "unlucky" set of random features that systematically degrade attention quality for important token pairs.

Cost of redrawing. The paper notes that redrawing is a "cheap procedure" — it only requires generating a new random matrix and (if using R-ORFs) running Gram-Schmidt, which is $O(rd^2)$ and amortized over many training steps. The orthogonal projection matrix can be pre-computed and cached.

---

3.4.8 Backward Compatibility: Transfer Learning from Regular Transformers

One of the paper's claimed advantages is that Performers are "fully compatible" with regular Transformers, enabling transfer learning from pretrained Transformer weights with minimal fine-tuning. This is demonstrated in Figure 5 (left) on the LM1B dataset.

The mechanism of compatibility. Because the Performer only modifies the attention sub-layer — and does so in a way that produces output tensors of the same shape ($L \times d$) as standard attention — the weights of all other components (linear projections, MLP layers, layer normalization parameters, embeddings) can be directly copied from a pretrained Transformer to a Performer. Only the attention computation itself changes: instead of computing $\mathbf{D}^{-1}\mathbf{A}\mathbf{V}$ explicitly, it computes $\widehat{\mathbf{D}}^{-1} \mathbf{Q}'((\mathbf{K}')^\top \mathbf{V})$ using random features.

The fine-tuning requirement. Despite the structural compatibility, the paper notes that "small finetuning [is] required due to error propagation" (Section 4.3). Figure 14 (Appendix D.1) shows that the output approximation error between a Performer and a Transformer accumulates with the number of layers — even when each individual attention block is well-approximated, the MLP layers, residual connections, and layer normalization can amplify small differences, causing the final-layer representations to diverge significantly. The LM1B result shows that a Performer initialized from Transformer weights starts at approximately 0.07 accuracy (compared to the Transformer's trained accuracy) but "quickly recovers accuracy in a small fraction of the original number of gradient steps" — the recovery is rapid because most of the model's knowledge is in the non-attention weights, and the attention approximation error is small enough that a brief fine-tuning period suffices to adapt.

Contrast with other efficient Transformers. This backward compatibility is not available for sparse attention methods (which change the attention mask structure, making weight transfer nontrivial) or kernel-substitution methods like the Linear Transformer (which replace softmax entirely with a different function). The paper explicitly highlights this as "a very important additional feature of the presented techniques that might be particularly attractive for practitioners" (Section 6).

---

3.4.9 Design Choices: Why This Specific Combination?

The FAVOR+ mechanism represents a carefully chosen combination of design elements, each motivated by a specific failure mode of alternatives:

Why positive features instead of trigonometric? Trigonometric features ($\sin$/$\cos$) are the "obvious" approach because they're standard in the random features literature and provide unbiased softmax estimation. But they fail in attention because the renormalization step $\mathbf{D}^{-1}$ is sensitive to negative estimates — a single negative denominator entry can destroy training stability. Positive features, obtained through the exponential identity in Lemma 1, guarantee non-negativity and have the additional benefit of low variance precisely where softmax values are small (Lemma 2), which is the dominant regime for long sequences.

Why orthogonal features instead of independent? Independent random features are simpler to implement and don't require the $m \leq d$ constraint. But Theorem 2 proves that orthogonality strictly reduces variance for any $d > 0$, and the empirical results in Figure 4 confirm this translates to lower approximation error. The reduced variance allows using a smaller $m$ (the paper uses $m = 256$ as the default), which directly reduces computational cost since time complexity scales as $O(Lmd)$. The theoretical results are particularly strong because they hold for finite $d$ (not just asymptotically), making them relevant for realistic Transformer dimensions.

Why regularized softmax (SMREG)? Standard softmax attention uses $\boldsymbol{\omega} \sim \mathcal{N}(0, \mathbf{I}_d)$, which means the random projection vectors can have arbitrary norms. The regularized variant constrains them to the sphere of radius $\sqrt{d}$, which Theorem 1 proves is an excellent approximation to standard softmax for typical $d$. The practical benefit, shown in Figure 5 (right), is faster convergence — likely because the bounded projection norms reduce estimator variance further.

Why the ReLU kernel for generalized attention? Among the tested alternatives, ReLU provides the best empirical performance on protein data (Figure 6), doesn't suffer from NaN issues (unlike sigmoid, tanh, exponential), and has a simple implementation with the $\epsilon$ offset for positivity. The paper doesn't provide a theoretical explanation for ReLU's superiority — this remains an empirical finding — but the framework's value is precisely that it enables discovering such domain-specific optimal kernels.

Why feature redrawing? Figure 5 (right) and Figure 15 show that without redrawing, even positive features can produce suboptimal results because a particular random draw may systematically mis-approximate certain attention patterns. Redrawing ensures that over the course of training, the model sees many different approximations and learns representations robust to the inherent stochasticity of the random feature method. This is analogous to dropout or data augmentation, where noise injection during training improves generalization.

Why $m = 256$? The paper doesn't provide an explicit ablation over $m$ for end-to-end training (Figure 4 shows MSE for different $m$ but only on the attention approximation, not on downstream task performance). The choice of 256 appears to be an empirical sweet spot: large enough to provide good approximation quality (Theorem 4 suggests $m = \Theta(d \log d)$, which for $d = 512$ would be around $512 \cdot \ln(512) \approx 3200$ — but this is a theoretical bound for worst-case approximation, and the practical requirement is much lower thanks to positivity and orthogonality), yet small enough to keep the complexity $O(L \cdot 256 \cdot 512)$ manageable.

4. Key Insights and Innovations

Innovation 1: Diagnosing and Solving the Catastrophic Variance of Trigonometric Random Features for Softmax Attention

The paper’s most conceptually distinctive contribution is not the use of random features for attention per se—that idea existed in kernel methods literature (Rahimi & Recht, 2007) and had been explored for Transformers (Tsai et al., 2019). Rather, it is the precise diagnosis of why the obvious trigonometric random feature approach fails for attention specifically, and the derivation of an alternative that inverts the failure mode.

The field’s default assumption when approximating kernels with random features had been to use sin/cos features for shift-invariant kernels—the standard Random Fourier Features recipe. Applied to the Gaussian kernel, and by the identity SM(x, y) = exp(‖x‖²/2) · K_gauss(x, y) · exp(‖y‖²/2), to softmax, this seems natural. The paper’s critical move is to examine the variance scaling behavior in the regime that matters for attention: when the true kernel value is close to zero. Lemma 2 reveals that the trigonometric estimator’s MSE scales as SM⁻²(x, y)—it diverges as the softmax value goes to zero. This is precisely where most attention weights live in long sequences (most token pairs are irrelevant to each other). The estimator achieves unbiasedness through cancellation of large positive and negative values, producing individual estimates that can be wildly wrong even though they average correctly—a classic case of the bias-variance tradeoff where low bias comes at the cost of unusably high variance in the relevant regime.

The positive random feature solution (Lemma 1) inverts this: the MSE scales as SM²(x, y), tending to zero as the kernel value shrinks. This is not an incremental improvement—it flips the qualitative behavior. The trigonometric estimator is least reliable where it’s most needed (the sea of near-zero attention weights that dominate normalization), while the positive estimator is most reliable precisely there. Figure 2 visualizes this: the ratio of trigonometric to positive MSE diverges as the angle between vectors increases (softmax → 0). This diagnostic framing—identifying that the failure is regime-specific, not universal—is what elevates the contribution beyond “we tried a different feature map.” It explains why prior attempts to use random features for softmax attention failed, and it provides a principled criterion (MSE → 0 as kernel → 0) for what a working feature map must satisfy.

The significance extends beyond this paper: any future work attempting to approximate softmax or similar kernels in attention-like settings must grapple with the small-value regime, not just average-case accuracy. The paper establishes that unbiasedness alone is insufficient when the estimator’s variance explodes in the most common case.

Innovation 2: Proving That Orthogonality Reduces Variance for Any Finite Dimensionality—Not Just Asymptotically

Orthogonal random features (ORFs) were known before this work as a variance reduction technique for kernel approximation (Yu et al., 2016; Choromanski et al., 2017, 2018b). The standard theoretical results, however, established benefits only asymptotically as dimensionality d → ∞. This left an uncomfortable gap: Transformer models operate at finite d (typically 256–1024), and it was unclear whether ORFs actually helped at these scales or whether the asymptotic guarantees were misleading.

The paper’s second conceptual contribution is Theorem 2, which proves that ORFs strictly reduce MSE compared to IID features for any d > 0, with an explicit formula for the gap. The proof technique—introducing “beautiful functions” (Appendix F.4, Definition 1) as functions expressible as expectations of entire functions with non-negative power series coefficients under isotropic distributions—is itself a novel theoretical tool. It enables decomposing the variance gap into components that can be bounded universally, without asymptotic assumptions.

This matters because it converts ORFs from an empirical trick to a principled choice. Before this result, a practitioner deciding whether to use orthogonal or IID features had to rely on experiments or hope that d was “large enough.” After Theorem 2, the choice is theoretically justified for any Transformer configuration. The result is particularly strong for softmax attention because positivity of the features plays a key role in the proof: orthogonal features provide exponentially tighter tail bounds (Theorem 3) that are strictly better than IID for every d > 0, not just in the limit.

Combined with Innovation 1, this creates a two-part recipe with theoretical backing at each step: (1) use positive features to eliminate catastrophic variance in the small-kernel regime, (2) enforce orthogonality to further reduce variance by an explicit, dimension-dependent amount. The empirical payoff is that the default m = 256 random features suffices for high-quality approximation—without both innovations, substantially more features would be needed (as Theorem 4 bounds suggest, m = Θ(d log d) for trigonometric features to achieve uniform convergence, which for d = 512 would be thousands).

Innovation 3: Reframing the Attention Efficiency Problem from “Approximating the Matrix” to “Directly Computing the Output”

All prior efficient Transformer variants—sparse attention (Child et al., 2019; Beltagy et al., 2020), LSH-based grouping (Kitaev et al., 2020), low-rank projection (Wang et al., 2020)—share a common conceptual framing: first construct (an approximation to) the attention matrix, then multiply by the values. Even when the matrix isn’t stored explicitly (e.g., computing values on the fly for local windows), the computational plan is organized around the L × L interaction structure.

FAVOR+ represents a fundamentally different conceptual move: skip the attention matrix entirely. By constructing feature maps φ such that φ(q_i)ᵀφ(k_j) approximates the kernel in expectation, and exploiting associativity of matrix multiplication, the algorithm computes the attention output directly—never forming, storing, or reasoning about individual pairwise interactions. The computation flows as (K′)ᵀV first (summarizing all values into an r × d aggregate), then Q′ multiplies this summary to produce per-query outputs. The L × L matrix exists only implicitly, as a mathematical expectation, never as an explicit object in memory or computation.

This shift from pairwise-interaction-first to aggregate-then-query is what enables genuine linear complexity without structural assumptions (sparsity patterns, locality, low-rankness of the original matrix). It’s the difference between saying “we’ll approximate which tokens attend to which” (prior work) and “we don’t need to know which tokens attend to which, we just need the weighted average output.” The associative trick is mathematically trivial—(AB)C = A(BC)—but its application to attention requires the kernel decomposition framework, which in turn requires solving the positivity and variance problems (Innovations 1 and 2). The conceptual leap is recognizing that the entire pipeline—kernel decomposition, positive features, orthogonality, reordering of multiplies—can be unified into a drop-in replacement that never instantiates the attention matrix.

The evidence for this shift’s practical impact is Figure 3: the Performer’s speed and memory scale nearly linearly with L, approaching the “X” line that represents the theoretical optimum where attention simply returns the V matrix. At L = 4096, the Performer achieves ~4× speedup on the backward pass and uses a fraction of the memory. This isn’t just a constant-factor improvement over sparse methods; it’s a qualitative change in how attention computation scales with sequence length.

Innovation 4: Enabling the First Fair Large-Scale Comparison of Attention Kernels, Including the Discovery That Softmax Is Not Always Optimal

Before Performers, comparing different attention kernel functions at scale was fundamentally confounded by computational constraints. Researchers could either (a) use exact softmax attention, limiting experiments to short sequences, or (b) use a linear-complexity alternative like the Linear Transformer (Katharopoulos et al., 2020), which replaced softmax with a different kernel (e.g., elu-based) but could not approximate softmax itself. There was no way to ask: “Is softmax actually better than ReLU for this task, or is softmax just what we can afford for short sequences while ReLU is what we use for long ones?”

FAVOR+ breaks this confound by providing a single mechanism that can implement any kernel with identical linear complexity. The generalized attention framework (Equation 5) uses the same random projection and associative multiply infrastructure regardless of whether the kernel is softmax, ReLU, GELU, absolute value, or sigmoid. This means that for the first time, softmax and non-softmax attention can be compared head-to-head at sequence lengths that would be impossible for exact softmax—a comparison that is fair because both methods have the same computational budget.

The empirical result from this comparison is striking and challenges a core assumption of the Transformer literature. On the TrEMBL protein sequence modeling task (Figure 6), Performer-ReLU achieves higher accuracy than both the exact-softmax Transformer and the softmax-approximating Performer—31.58% vs. 30.80% (unidirectional) and 36.09% vs. 33.32% (bidirectional) on the test set (Table 2). The softmax kernel, which has been the default attention function since Vaswani et al. (2017) and is often treated as essential to the Transformer’s success, is not optimal for this domain.

This finding has implications beyond protein modeling. It suggests that the choice of attention kernel is a design dimension that should be optimized per-task, not a fixed architectural constant. The paper’s systematic kernel sweep (Appendix D.3, Figures 16–17) shows substantial variation across kernels: some cause NaN failures (sigmoid, tanh), others train stably but underperform, and ReLU emerges as the empirical winner for this dataset. The Performer framework enables this kind of systematic comparison, and the result—that softmax is not universally optimal—is a genuinely new insight that could only emerge because FAVOR+ made the comparison possible.

5. Experimental Analysis

Evaluation Methodology

Dataset. The paper evaluates on a diverse set of benchmarks spanning multiple modalities. For text, the primary datasets are PG-19 (Rae et al., 2020), a collection of out-of-copyright Project Gutenberg books published before 1919, used for bidirectional masked language modeling pretraining; and LM1B (One Billion Word Benchmark; Chelba et al., 2014), used for unidirectional language modeling and the backward-compatibility transfer learning experiment. For protein sequence modeling, the paper uses the TrEMBL dataset (Consortium, 2019), specifically the Jan. 2019 release containing approximately 139 million sequences (106 million unique), with sequences clipped to L = 1024 for the standard task and concatenated to L = 8192 for the long-sequence task; the dataset includes a held-out OOD test set consisting of 20 Pfam families excluded from training (29,696 sequences). For image generation, the paper uses ImageNet64 (Parmar et al., 2018), where images are represented as sequences of pixels of length L = 12,288 (64 × 64 × 3 color channels). The PG-19 dataset is tokenized using a unigram SentencePiece vocabulary with 32,768 tokens, and perplexities are computed with a correction factor (ratio of SentencePiece tokens to original dataset tokens: train = 1.5634, valid = 1.5487, test = 1.5359) to account for tokenization granularity differences. For the Long Range Arena benchmark cited in Appendix D.5, tasks include ListOps (Nangia & Bowman, 2018), byte-level text classification, byte-level document retrieval, image classification on pixel sequences, and the Pathfinder spatial dependency task.

Base model. All experiments use Transformer architectures with standard components (multi-head attention, MLP layers, layer normalization, residual connections, positional encodings). The Performer modifies only the attention sub-layer, leaving all other components identical. For the main protein modeling experiments (Section 4.4), the architecture is (nheads, nlayers, d_ff, d) = (8, 36, 1024, 512), matching the ProGen configuration from Madani et al. (2020) — this choice enables direct comparison with published protein language model results. For the computational cost benchmarks (Section 4.1, Figure 3), the architecture is (8, 6, 2048, 512). For the ImageNet64 experiments (Section 4.5), the architecture uses the standard (nheads, d_ff, d) = (8, 2048, 512) with varying nlayers. For the concatenated TrEMBL experiments, the baseline Transformer must be reduced to (8, {1,2,3}, 256, 256) because the standard configuration "overloads memory even at a batch size of 1 per chip, by a wide margin" (Section 4.5). The paper also compares against a Linear Transformer (Katharopoulos et al., 2020) using feature map φ(x) = elu(x) + 1, but with ReLU MLPs rather than GeLU to ensure fair comparison.

Metrics. For unidirectional (causal) models, the primary metric is next-token prediction accuracy, averaged across all sequence positions in the evaluation dataset. For bidirectional (masked) models, masked token prediction accuracy is measured on the 15% of tokens randomly masked during evaluation (matching BERT's protocol from Devlin et al., 2018). Perplexity is reported for both settings, computed as exp(average log-likelihood). For image generation, bits per dimension (BPD) is computed as the loss divided by ln(2). All metrics are evaluated on the held-out test set for each dataset; for large datasets with extensive evaluation splits (ImageNet64, PG-19), results are computed on "random batches (>2048 samples) for plotting curves" (Appendix A.1).

Baselines. The paper compares against multiple efficient Transformer variants:

• Reformer (Kitaev et al., 2020): Uses Locality-Sensitive Hashing (LSH) attention with default LSH parameters. Evaluated on protein modeling (both unidirectional and bidirectional) and ImageNet64, but restricted to the unidirectional setting (as noted in Section 4). The Reformer uses learning rate decay for ImageNet64 per its default configuration.
• Linformer (Wang et al., 2020): Uses low-rank projection of keys and values with projection dimension k = 600 (more than twice the default k = 256 from the original paper) and δ = 10⁻⁶ for the renormalization procedure. The paper notes that these hyperparameters are "even stronger than the defaults" and that redrawing of projections is used "which avoids 'unlucky' projections on Q and K" (Appendix A.6). Restricted to the bidirectional setting.
• Linear Transformer (Katharopoulos et al., 2020): Uses feature map φ(x) = elu(x) + 1 with the same training hyperparameters as Performer-ReLU on the ProGen setting. Evaluated on TrEMBL but found to produce "exploding gradients very early on" in the unidirectional setting (all 3 seeds) and "an exploding gradient in the middle of training, near 125K steps" in the bidirectional setting (Appendix D.4, Figure 18).
• Transformer (Vaswani et al., 2017): The exact-softmax baseline, trained with the same hyperparameters as Performers when sequence length permits. On concatenated TrEMBL (L = 8192), the Transformer must be "significantly smaller" — reduced to (8, {1,2,3}, 256, 256) — because the standard configuration causes out-of-memory errors at batch size 1.
• Empirical baseline (for protein tasks): A model that predicts amino acids with probabilities proportional to their empirical frequencies in the training set, achieving 9.92% accuracy and 17.80 perplexity on the TrEMBL test set (Table 2).

Generation budget / compute accounting. The paper measures computational cost in wall-clock time (forward and backward pass speed), memory consumption (GPU memory usage), and maximum feasible sequence length on fixed hardware (V100 GPU with 16GB for speed benchmarks, TPU-v2 pods with 8GB per chip for training experiments). For the speed benchmarks in Figure 3, models use a vocabulary size of 256 and are evaluated up to the point of out-of-memory error. For the Long Range Arena comparison (Appendix D.5), efficiency is reported as examples per second and per-device memory usage on 4×4 TPU-v3 chips with a consistent batch size of 32. The paper does not use an abstract "generation budget" in the sense of number of samples (as would be common in inference-time compute papers); instead, it measures the real computational cost of training at scale, with batch sizes "maximized for each separate run given the compute constraints" (Appendix A.2). All 36-layer protein experiments use identical compute: 16×16 TPU-v2 pods. For concatenated TrEMBL, the Performer uses 16×16 TPU-v2's while the smaller Transformer models use 8×8 TPU-v2's (with the paper noting that "using 16×16 did not make a difference in accuracy").

Cross-validation / statistical protocol. There is no formal cross-validation reported in the paper. For protein experiments, results are reported on a fixed held-out test set (both IID and OOD splits as described in Appendix C.1). For the PG-19 and ImageNet64 experiments, results are evaluated on standard dataset splits. The paper does report variability across random seeds in some experiments: for the Linear Transformer comparison, "3 seeds" were run and all produced exploding gradients (Appendix D.4); for the feature redrawing experiment, "Seed 1" and "Seed 2" produced divergent training trajectories (Figure 15, left). For the orthogonal vs. IID feature comparison (Figure 4), standard deviations are reported "across 15 samples of appropriately normalized random matrix input data." No statistical significance tests or confidence intervals are reported for the main experimental results.

---

Main Quantitative Results

Computational Cost and Scaling Behavior

Headline result: The Performer achieves near-linear time and sub-quadratic memory scaling with sequence length L, approaching the theoretical optimum. Figure 3 (left) demonstrates this on a V100 GPU (16GB) with the standard architecture (nheads=8, nlayers=6, d_ff=2048, d=512). At L = 1024, the Transformer and Performer have comparable backward pass speeds. By L = 2048, the Performer achieves roughly a 4× speedup on the backward pass compared to the Transformer. At L = 4096, the gap widens further — the Performer's backward pass time grows approximately linearly with L, while the Transformer's grows quadratically. The "X (OPT)" line represents the maximum theoretical speedup achievable when attention is replaced with an identity function that simply returns the V matrix — the Performer's curve approaches this line, indicating that attention computation is no longer the dominant bottleneck.

Maximum sequence length. For the "Regular" architecture (nheads=8, nlayers=6, d_ff=2048, d=512), the Transformer hits out-of-memory on a V100 16GB GPU at approximately L = 2048, while the Performer scales beyond L = 32,768 (2¹⁵). For the "Small" architecture (nheads=1, nlayers=6, d_ff=64, d=64), where attention is the dominant computational cost (since the MLP layers are tiny), the Transformer reaches out-of-memory around L = 8192 while the Performer again extends past L = 32,768 (Figure 3, right subfigure; extended results in Appendix E, Figure 20-21).

Scaling with number of layers. Appendix E (Figure 20, subfigure 1) shows that the Performer maintains efficient scaling up to at least 20 layers — the forward and backward pass times increase roughly linearly with nlayers, with no super-linear growth that would indicate the attention cost dominating.

Memory efficiency. Figure 3 (right subfigure) shows that for both the feed-forward and attention components, the Transformer's memory consumption grows much faster than the Performer's as L increases. The Transformer's attention memory grows quadratically (storing the L × L attention matrix), while the Performer's grows roughly linearly (storing only the r × d and r × 1 intermediate aggregates). The Performer achieves memory usage close to the "OPT" line — the theoretical minimum where only the input and output tensors are stored.

Architecture size sweep. Appendix E (Figure 20, subfigure 3; Figure 21) compares Transformer and Performer models across both "Regular" and "Small" configurations on forward pass, backward pass, and total training time. For the Regular configuration at L = 2048, the Performer achieves approximately 1.5–2× overall training speedup. For the Small configuration at L = 4096, the speedup is even larger — roughly 3–4× — because attention constitutes a larger fraction of total computation when the MLP layers are small.

---

Softmax Attention Approximation Error

Headline result: Positive orthogonal random features (PORF) produce substantially lower approximation error than either trigonometric or IID features, with orthogonal features providing additional variance reduction beyond positivity alone. Figure 4 quantifies this using the mean squared error (MSE) of the attention approximation output, measured at L = 4096, d = 16, across varying numbers of random features m (ranging from 2 to 128). Results are averaged over 15 samples of randomly generated input data with standard deviations shown as error bars.

Orthogonal vs. IID features (Figure 4, left). For the same number of random features m, orthogonal features consistently produce lower MSE than IID (independent) features. The gap is largest at small m — at m = 8, orthogonal features reduce MSE by roughly 30–40% compared to IID features. As m increases, both methods' MSE decreases (as expected from the 1/m scaling in the variance formulas), but the orthogonal advantage persists across all m values tested. This confirms Theorem 2's prediction that ORFs reduce variance for any finite d (here d = 16).

Positive vs. trigonometric features (Figure 4, right). The performance gap is dramatic. Trigonometric (sin/cos) features produce MSE roughly two orders of magnitude higher than positive features across all m values. At m = 32, positive features achieve an MSE of approximately 10⁻⁸, while trigonometric features remain around 10⁻⁶ — a ~100× difference. At m = 128, positive features reach approximately 10⁻¹⁰ while trigonometric features are still around 10⁻⁷ — a ~1000× difference. This empirically validates Lemma 2: the trigonometric estimator's variance explodes in the small-kernel-value regime that dominates random input data, while the positive estimator's variance naturally shrinks there.

Combined effect (PORF). The combination of positive features with orthogonal projections (the full FAVOR+ mechanism) achieves the lowest MSE at every m tested. The variance reduction from orthogonality compounds with the fundamental advantage of positivity — at m = 32, PORF achieves an MSE nearly as low as IID-positive features at m = 64, representing roughly a 2× reduction in required features for equivalent accuracy.

---

Softmax Approximation on Full Transformers (End-to-End Training)

Headline result: Positive softmax features with redrawing are necessary to match regular Transformer performance at scale, while trigonometric features cause unstable training and plateau at higher perplexity. These experiments test whether the attention approximation quality demonstrated in Figure 4 translates to successful end-to-end training of full Transformer models.

Backward compatibility and fine-tuning (Figure 5, left). On the LM1B dataset, a Performer initialized with pretrained Transformer weights starts at only 0.07 accuracy (the dotted orange line) — "small errors can easily propagate throughout multiple Transformer layers" as the paper notes (Section 4.3), and Figure 14 confirms that the output approximation error between a Performer and Transformer grows with the number of layers. However, the Performer "quickly recovers accuracy in a small fraction of the original number of gradient steps" — within approximately 10–20% of the original training steps, the Performer matches the Transformer's final accuracy. This demonstrates that the noise introduced by random feature approximation can be fine-tuned away rapidly, making weight transfer from pretrained Transformers practical. The paper claims this backward compatibility is a unique advantage over other efficient Transformer variants that "cannot be used on the top of a regular pre-trained Transformer."

Trigonometric features fail at scale (Figure 5, right). On the larger PG-19 dataset (which has much longer sequences and a 32,768-token vocabulary), the failure of trigonometric softmax features becomes catastrophic. The full training curve (shown in Appendix D.2, Figure 15, right) reveals that trigonometric softmax "causes very unstable training behaviors." Even with feature redrawing, trigonometric features plateau at a substantially higher perplexity than positive features. The paper states that "Trigonometric (TRIG) softmax approximation becomes highly unstable" and that the Linformer — which also approximates softmax — similarly "plateau[s] at the same perplexity" as trigonometric features.

Positive features with redrawing are essential. On PG-19, "Positive softmax with feature redrawing is necessary to match the Transformer." Without redrawing, even positive features plateau at suboptimal perplexity (as shown in Figure 5, right, and Figure 15, left). The paper explains this through the redrawing mechanism: without periodically resampling the random projections, a particular "unlucky" set of features can systematically mis-approximate certain attention patterns, and the model cannot recover because the approximation error is fixed. Redrawing ensures the model sees many different approximations over the course of training, averaging out the errors.

SMREG convergence speed. The regularized softmax kernel (SMREG, using uniform spherical rather than Gaussian random vectors) allows "faster convergence" than the standard positive softmax approximation (Figure 5, right), reaching the same final perplexity as the Transformer in fewer training steps. This aligns with Theorem 1's guarantee that SMREG is a universal lower bound for softmax and closely approximates it for typical d.

Extended properties (Figure 15). Appendix D.2 provides additional results on approximate softmax. The left subfigure demonstrates the importance of redrawing: two different fixed random seeds produce divergent training trajectories — Seed 1 causes "training degradation" and early stopping, while Seed 2 trains normally. When redrawing is enabled (vertical black line), the training recovers from the unlucky Seed 1 draw. The middle subfigure shows that on ImageNet64 (unidirectional, 6-layer model, 8×8 TPU-v2), "approximate softmax with positive features achieves the same result as generalized ReLU attention" — both reaching approximately 3.67–3.69 BPD after 100K steps.

---

Generalized Attention on Protein Sequences (TrEMBL)

Headline result: FAVOR+ with a ReLU kernel outperforms exact softmax attention on protein sequence modeling, while the Reformer and Linformer significantly drop in accuracy on the same task. Figure 6 presents results from training 36-layer models on the TrEMBL dataset (L = 1024) with all models using exactly the same architecture (nheads=8, nlayers=36, d_ff=1024, d=512) and 16×16 TPU-v2 compute.

Performer-ReLU vs. Transformer (softmax). In the unidirectional (U) setting, Performer-ReLU achieves higher validation accuracy than the exact-softmax Transformer throughout training, with the gap widening as training progresses. In the bidirectional (B) setting, Performer-ReLU shows an even larger advantage, reaching plateau accuracy visibly above the Transformer. Quantitative results in Table 2 confirm this:

• Unidirectional, Test: Performer-ReLU (generalized) achieves 31.58% accuracy and 9.17 perplexity, compared to Transformer's 30.80% and 9.37 — an improvement of 0.78 percentage points.
• Bidirectional, Test: Performer-ReLU (generalized) achieves 36.09% accuracy and 8.36 perplexity, compared to Transformer's 33.32% and 9.22 — an improvement of 2.77 percentage points.

On the OOD test set, the Transformer actually slightly outperforms Performer-ReLU in the unidirectional case (Transformer: 19.70%, Performer: 18.44%), while in the bidirectional case Performer-ReLU trails slightly (Transformer: 25.07%, Performer: 24.10%). The paper does not discuss whether these OOD differences are significant.

Performer softmax approximation quality. The Performer with softmax approximation achieves accuracy nearly identical to the exact-softmax Transformer: in the bidirectional test set, Performer-softmax achieves 33.00% vs. Transformer's 33.32% (Table 2) — a difference of only 0.32 percentage points, well within what might be expected from approximation noise. This "confirms our theoretical claims from Section 3" that FAVOR+ provides a tight approximation of the true softmax attention.

Reformer and Linformer comparison. Figure 6 shows that both the Reformer and Linformer "significantly drop in accuracy" compared to the Performer and Transformer on this task. The training curves for both baselines are visibly below the Performer curves, with the gap growing over the course of training. The paper does not provide exact final accuracy numbers for Reformer and Linformer on TrEMBL in the main text, but the visual gap in Figure 6 is substantial — roughly 5–10 accuracy points below the Transformer and Performer.

Performer softmax (positive) approximates exact softmax well. The softmax-approximating Performer's curve is nearly indistinguishable from the exact-softmax Transformer's curve in Figure 6, consistent with the theoretical guarantees from Section 3. Table 2 quantifies this as 33.00% (Performer-softmax) vs. 33.32% (Transformer).

Linear Transformer instability. Appendix D.4 (Figure 18) demonstrates that the Linear Transformer (Katharopoulos et al., 2020) fails to train on this task. In the unidirectional setting, "all 3 seeds produced exploding gradients very early on, stopping the training run." In the bidirectional setting, a seed "produced an exploding gradient in the middle of training, near 125K steps," visible as "the sharp drop in train accuracy right before a NaN error" (Figure 18, right). The paper attributes this to numerical instability of the elu-based feature map compared to FAVOR+'s carefully designed positive features.

Kernel sweep results (Appendix D.3, Figures 16–17). A systematic comparison of attention kernels on TrEMBL (L = 512) reveals instability with several choices. On 2×2 TPU-v2's, sigmoid, exponential, tanh, and identity kernels produce NaN errors that cause runs to stop early (Figure 16, log-scale axes emphasize the highest-accuracy runs while making NaN-caused early stops visible). ReLU, absolute value, GELU, and cosine (softmax approximation) train stably. The ReLU kernel achieves the best training accuracy among all tested kernels. On 4×4 TPU-v2's (Figure 17), the ranking is similar but "the effective batch size slightly affects the rankings" — the paper notes that the optimal kernel may depend on batch size, and defaults to ReLU "as we observed that they are empirically optimal for large batch size runs (i.e. 8×8 or 16×16 TPU's)."

---

Large-Length Training: ImageNet64 and Concatenated Proteins

Headline result: Performers train efficiently at sequence lengths that are completely infeasible for regular Transformers, matching or exceeding the performance of much larger models. These experiments push to sequence lengths that would cause out-of-memory errors even at batch size 1 for standard Transformers.

ImageNet64 (L = 12,288) — Figure 7, left. All models use the standard (nheads, d_ff, d) = (8, 2048, 512). The x-axis shows training steps (up to ~150K for the longest runs).

• Performer/6-layers matches Reformer/12-layers. With only 6 layers, the Performer achieves approximately the same validation BPD as the Reformer with 12 layers — roughly matching the Reformer's performance while using half the depth.
• Performer/12-layers matches Reformer/24-layers. Extending the Performer to 12 layers achieves parity with the Reformer at 24 layers. This suggests that the Performer's attention mechanism is more parameter-efficient — each layer extracts more useful signal from the long-range context because it can attend to all positions (via dense softmax approximation) rather than only the LSH-selected subset.
• Speed comparison. The paper notes that "Depending on hardware (TPU or GPU), we also found that the Performer can be 2× faster than the Reformer via Jax optimizations for the (U) setting." This is a hardware-dependent claim but highlights that the Performer's simpler computational pattern (standard matrix multiplies vs. LSH bucketing and sorting) can be more efficiently compiled.
• Softmax vs. ReLU on ImageNet64. After 100K steps, Performer-ReLU, Performer-Softmax, and Performer-Softmax (SMREG) achieve 3.67, 3.69, and 3.67 BPD respectively (Appendix D.2) — essentially identical performance, showing that for this task, the kernel choice is less critical than for proteins.

Concatenated TrEMBL (L = 8,192) — Figure 7, right. This task concatenates protein sequences with end-of-sequence tokens to form fixed-length segments of 8,192 tokens. The goal is to model interactions among groups of proteins — a setting relevant to "predicting interactions among groups of proteins by concatenating protein sequences to length L = 8192 from TrEMBL, long enough to model protein interaction networks without the large sequence alignments required by existing methods" (Section 4.5).

• Transformer baseline (severely constrained). A regular Transformer with the standard (8, 6, 2048, 512) architecture "overloads memory even at a batch size of 1 per chip, by a wide margin." The baseline Transformer must be reduced to (nheads=8, nlayers={1,2,3}, d_ff=256, d=256) — a dramatically smaller model. This Transformer baseline trains on 8×8 TPU-v2's while the Performer uses 16×16 TPU-v2's (though "using 16×16 did not make a difference in accuracy" for the Transformer).
• Transformer/1-layer reaches approximately 17.5% validation accuracy and plateaus.
• Transformer/3-layers reaches approximately 19% and plateaus — the paper states it "is quickly bounded at ≈19%."
• Performer (standard architecture, 16×16 TPU-v2) trains continuously to approximately 24% validation accuracy, continuing to improve at the end of training. The Performer uses the full (8, 6, 2048, 512) architecture — 6 layers vs. the Transformer's maximum of 3, with hidden dimension 512 vs. 256 — and trains at batch size 8 per chip vs. the Transformer's likely smaller batch.
• Key takeaway. The Performer achieves ~24% accuracy vs. the Transformer/3-layer's ~19% — a 5 percentage point improvement (roughly 26% relative improvement). However, this comparison confounds sequence length capability with model capacity: the Transformer is restricted to a smaller architecture to fit in memory, so the accuracy gap reflects both the Performer's ability to handle longer sequences and its ability to use a larger model within the same memory budget.

---

Long Range Arena Benchmark (Appendix D.5)

Headline result: Performers achieve the highest score among all tested scalable Transformer methods on the Long Range Arena benchmark, with strong performance across diverse long-context tasks. Results are reproduced from Tay et al. (2021) in Figure 19.

Accuracy results (Figure 19, upper table). Performers achieve top or near-top performance on four of five tasks:

• ListOps (L = 2,048): 36.00% (2nd overall, behind only the full Transformer at 37.10%).
• Text (byte-level classification): 64.71% (3rd overall; top performer is Local Attention at 65.25%).
• Retrieval (byte-level document retrieval): 80.46% (2nd overall, behind Local Attention at 80.94%).
• Image (pixel sequence classification): 42.67% (tied for best among scalable methods with Sparse Transformer at 43.50%; Big Bird slightly higher at 43.67%).
• Pathfinder (L = 1,024): 75.65% (5th overall, but the top performers — Transformer at 75.81%, Sparse Transformer at 76.37% — are non-scalable).

Largest LRA score among scalable methods. The paper defines "scalable" as achieving speed > 100 examples/sec. Among methods meeting this criterion, the Performer obtains the highest overall LRA score. Notably, the Performer also handles Path-X (L = 16,384) — a task where "all models do not learn anything" (marked FAIL for all other methods).

Speed and memory (Figure 19, lower table). Benchmarked on 4×4 TPU-v3 chips with batch size 32:

• Performer: 0.37 steps/sec (4.9× slower than Transformer baseline), 8.15 GB per-device memory.
• Reformer: 0.10 steps/sec (20.2× slower), 8.36 GB memory.
• Linformer: 0.26 steps/sec (7.7× slower), 15.62 GB memory.
• Big Bird: 0.28 steps/sec (7.0× slower), 8.61 GB memory.
• Linear Transformer: 0.31 steps/sec (6.4× slower), 12.06 GB memory.

The Performer is the fastest among scalable methods (0.37 steps/sec, memory 8.15 GB) while the Reformer is the slowest (0.10 steps/sec). The right subfigure of Figure 19 plots accuracy vs. speed vs. memory, showing the Performer in the favorable region of high accuracy and moderate speed.

---

Ablation Studies and Robustness Checks

Feature redrawing frequency (Figure 5, right; Figure 15, left). Without periodic redrawing of random features, training trajectories become dependent on the specific random seed, with some seeds causing degradation that prevents reaching Transformer-matching performance. With redrawing enabled (vertical line in Figure 15, left), training recovers from unlucky initializations. On PG-19, the paper states that "Positive softmax with feature redrawing is necessary to match the Transformer" — without it, even positive features plateau at a higher perplexity. This establishes redrawing as a critical practical component, not just a theoretical nicety.

Orthogonal vs. IID features on end-to-end training. The paper demonstrates this in the approximation error domain (Figure 4) but does not provide a dedicated ablation on downstream task performance comparing orthogonal vs. IID features. The default configuration for all experiments uses ortho_features = True (Appendix A.3), so the choice is based on the approximation error advantage. The paper claims in Appendix B.3 that orthogonal features "do indeed lead to more accurate approximations and substantially better downstream results," but the downstream results showing orthogonal vs. IID specifically are not separated from the positive-vs-trigonometric comparison in the main experiments.

Positive vs. trigonometric features on end-to-end training (Figure 5, right; Figure 15, right). This is the most critical ablation for the paper's central claim. Trigonometric features cause "highly unstable training behaviors" and plateau at higher perplexity than positive features on PG-19. The full curve (Figure 15, right) shows that trigonometric features produce erratic loss trajectories, while positive features train stably. This empirically validates Lemma 2's theoretical prediction that trigonometric features' exploding variance in the small-kernel regime is catastrophic for training.

Renormalization on/off (Appendix D.3, Figures 16–17). The paper tests whether the attention renormalization (applying D⁻¹) is necessary. On 4×4 TPU-v2's with ReLU kernel (Figure 17), disabling renormalization produces training accuracy comparable to the renormalized version for some configurations. The paper states "we noticed that disabling it does not necessarily hurt accuracy" (Appendix D.3). This is a surprising result because renormalization (making attention weights sum to 1) is considered fundamental to the Transformer's operation — it suggests that for some kernels, the raw feature dot-products serve as adequate attention weights without row-wise normalization. The default configuration keeps renormalization enabled.

Number of random features (m). Figure 4 shows MSE as a function of m for L = 4096, d = 16, but no end-to-end ablation over m is provided for downstream tasks. The default m = 256 is fixed across all experiments. Theorem 4 suggests that m should scale as Θ(d log(d)) for uniform convergence guarantees, which for d = 512 would be much larger (~3200), so the practical empirical requirement is substantially lower than the theoretical bound — likely due to the combined effects of positivity, orthogonality, and feature redrawing.

Kernel function sweep (Figures 16–17). Systematic comparison across kernel functions (sigmoid, exponential, ReLU, absolute value, GELU, cosine, tanh, identity) on TrEMBL with L = 512. Key findings: sigmoid, exponential, tanh, and identity kernels produce NaN errors (training stops early); ReLU achieves the best training accuracy among all stable kernels; the effective batch size (2×2 vs. 4×4 TPU) slightly affects kernel rankings (the paper notes that for large batch sizes — 8×8 or 16×16 — ReLU is optimal). This sweep provides empirical justification for the default kernel = ReLU choice in the generalized attention configuration.

PRM (process reward model) aggregation strategy. Not applicable to this paper (this is a standard classification from the reference example, not present in the Performer paper).

Numerical stabilizer (epsilon). The softmax configuration uses numerical_stabilizer = 10^{-6} while the generalized attention configuration uses numerical_stabilizer = 0.0 (Appendices A.3, A.4). For generalized attention with ReLU kernel, a separate kernel_epsilon = 10^{-3} is added inside the ReLU to prevent zero feature vectors: f(x) = max(0, x) + ε. No ablation over these values is provided.

Hadamard/Givens ORFs vs. Regular ORFs. The paper describes H-ORFs and G-ORFs as alternatives to R-ORFs with better computational characteristics (O(m log d) time vs. O(md) for multiplying by the projection matrix), but all experiments use the default R-ORF variant (Appendix B.2). No empirical comparison between ORF variants is provided, so the claimed efficiency benefits of H/G-ORFs remain theoretical.

ReST^EM revision model. Not applicable to this paper (this is from the reference example about inference-time compute; the Performer paper does not involve revision models or reinforcement learning for refinement).

---

Critical Assessment

The experimental evaluation successfully demonstrates several core claims but leaves important gaps in the evidence for others. Here I examine each major claim against what was actually tested.

Claim: Performers achieve linear (as opposed to quadratic) space and time complexity. The computational cost experiments in Figure 3 and Appendix E strongly support this. The Performer's backward pass time grows roughly linearly with L — visually tracking the "X (OPT)" line that represents the theoretical optimum — while the Transformer's grows noticeably super-linearly. At L = 4096, the ~4× speedup is substantial and practically meaningful. Similarly, memory consumption grows roughly linearly for the Performer vs. quadratically for the Transformer. The extended results in Appendix E (Figures 20–21) show this holds across architecture sizes and for models up to 20 layers. However, the benchmarks are run on a single V100 GPU (16GB) with a vocabulary size of 256 — this is a relatively constrained setting, and it would strengthen the claim to see scaling curves on larger hardware (e.g., 32GB or 80GB GPUs) or with larger vocabulary sizes where the MLP layers' contribution to total cost is different. The paper also doesn't benchmark at extreme sequence lengths (> 32K) where the O(Lrd) term might start to dominate in absolute terms even if it scales linearly.

Claim: FAVOR+ provides provably accurate estimation of softmax attention, with theoretical guarantees. The approximation error measurements (Figure 4) convincingly demonstrate that positive orthogonal random features drastically reduce MSE compared to trigonometric or IID features. The ~100–1000× MSE reduction at comparable m is a large effect. However, there is a gap between component-level approximation quality and system-level performance. Figure 14 (Appendix D.1) shows that attention output approximation error accumulates across layers — even when individual attention blocks are well-approximated, the final layer's output can diverge significantly. The paper addresses this by showing that fine-tuning recovers Transformer-matching performance (Figure 5, left), but this means the theoretical "provable accuracy" guarantees apply to the attention computation in isolation, not to the full multi-layer model. A reader might reasonably ask: if the approximation is so good, why is fine-tuning needed at all? The answer (error propagation through MLPs and layer norm) is discussed but not bounded theoretically.

Claim: Performers are the first linear architectures fully compatible with regular Transformers, providing strong theoretical guarantees. The backward compatibility experiment (Figure 5, left) on LM1B supports feasibility: a Performer initialized from Transformer weights recovers accuracy quickly. But this is shown only on one dataset (LM1B), with one model size, and the initial accuracy drop to 0.07 is severe — the model essentially loses all its knowledge upon conversion. The "small fraction of original gradient steps" for recovery is qualitative (the x-axis shows steps, but the "original number of gradient steps" isn't specified). A stronger demonstration would show that the recovered model matches the original Transformer's accuracy exactly (not approximately), and on multiple tasks. The paper also doesn't test whether the fine-tuned Performer generalizes identically to the original Transformer on downstream tasks — only perplexity/accuracy on the same dataset is measured.

Claim: Performers enable the first fair large-scale comparison of attention kernels, including discovering that softmax is not always optimal. This is the paper's most intriguing empirical contribution, and the evidence is mixed. On TrEMBL, Performer-ReLU clearly outperforms Performer-softmax and Transformer-softmax on the IID test set (Table 2: 36.09% vs. 33.32% bidirectional). However, on the OOD test set (held-out protein families), the Transformer actually outperforms Performer-ReLU (25.07% vs. 24.10% bidirectional), and Performer-softmax trails both (23.48%). This reversal is not discussed in the paper — it raises the possibility that the ReLU advantage is specific to in-distribution sequences and doesn't generalize to novel protein families, which would substantially weaken the claim that "softmax is not optimal." The kernel sweep (Figures 16–17) only measures training accuracy on a subset of the data (2×2 and 4×4 TPU runs at L = 512, not the full 16×16 L = 1024 setting), so the generalization of these findings to the full-scale experiments is unverified.

Claim: The Performer outperforms Reformer and Linformer on protein modeling. Figure 6 shows Performer curves above both Reformer and Linformer, but this comparison is not fully controlled. The Reformer and Linformer use their own hyperparameter configurations (LSH attention parameters for Reformer, projection dimension k = 600 for Linformer), while the Performer uses its default m = 256. It's possible that hyperparameter tuning could close the gap. More importantly, the Reformer default is designed for NLP tasks — its LSH bucketing might be poorly suited to protein sequences with different similarity structures. The paper can legitimately claim that the Performer as configured outperforms these baselines, but claiming the Performer is better in an absolute sense would require demonstrating that the baselines were given a fair hyperparameter optimization budget.

Missing comparisons and analyses. Several experiments that would strengthen the paper are absent:

• Comparison with sparse attention at matched FLOPs, not matched layer count. The ImageNet64 comparison (Figure 7, left) shows Performer/6-layers matching Reformer/12-layers, but total FLOPs are not reported. A Performer with 2× layers might use more total compute than a Reformer with fewer layers — reporting FLOPs-normalized accuracy would clarify whether the Performer is genuinely more efficient or simply using more compute per layer.

• Ablation over m (number of random features) on downstream task performance. Figure 4 shows the effect of m on attention approximation MSE, but no experiment varies m and measures end-to-end accuracy or perplexity. This is the most important missing ablation: it would tell users how to choose m for their application and reveal whether m = 256 is near-optimal or whether performance continues improving with larger m.

• Ablation over the orthogonality choice on downstream tasks. Orthogonal features are shown to reduce attention MSE (Figure 4, left) but are never ablated against IID features in a full training run. The claim that ORFs "substantially [improve] downstream results" (Appendix B.3) is not directly supported.

• Experiments on standard NLP benchmarks. All text experiments are on LM1B (for backward compatibility) and PG-19 (for pretraining). There are no results on common benchmarks like GLUE, SQuAD, or translation tasks. Given that the Transformer's original success was on machine translation and NLP, the absence of these benchmarks limits confidence that Performers work well for the tasks most practitioners care about.

• Statistical significance. No confidence intervals, standard errors (except for Figure 4), or significance tests are reported for the main training experiments. With a 500-question test set or similar, 1–2 percentage point differences between methods may not be statistically reliable, and the paper provides no way to assess this.

Strengths of the experimental design. Despite these limitations, several aspects of the evaluation are well-designed:

• The multi-domain testing (text, proteins, images) demonstrates that the Performer's advantages are not task-specific, covering three qualitatively different data modalities.
• The matched-compute protein experiments (all models use 16×16 TPU-v2, same architecture, same number of training steps) provide a fair comparison between the Performer variants and the exact Transformer.
• The extreme-length experiments (L = 8,192 concatenated proteins, L = 12,288 ImageNet64) test the method at scales where the regular Transformer cannot run at all, providing strong evidence that the Performer expands the feasible range of applications.
• The negative results with the Linear Transformer (Appendix D.4) show that the authors tested a natural competing approach and documented its failure, rather than cherry-picking only favorable comparisons.

Overall assessment. The experiments convincingly establish that FAVOR+ enables training Transformers at sequence lengths that are infeasible for standard attention, and that the approximation quality is sufficient to match or approach exact-softmax performance with the right configuration (positive features, orthogonality, redrawing). The claim that alternative kernels can outperform softmax is intriguing but rests primarily on a single dataset (TrEMBL) with an IID/OOD discrepancy that needs investigation. The comparison with other efficient Transformer methods shows Performer dominance under the tested configurations, but leaves open the question of whether hyperparameter optimization could close the gap.

6. Limitations and Trade-offs

The Difficulty Estimation Cost Is Unaccounted For and Overwhelms the Headline Efficiency Gains

The assumption or constraint. The FAVOR+ mechanism uses random feature maps whose quality depends on the number of features $m$. The paper's default $m = 256$ is chosen empirically, but there is no principled method for selecting $m$ per-task — the user must either rely on the default (which may be suboptimal for their domain) or run their own ablation experiments. More critically, the paper provides no way to estimate, before training, how large $m$ needs to be for a given sequence length, data distribution, and desired approximation quality. Theorem 4 provides a theoretical bound of $m = \Theta(d \log d)$, which for the paper's default $d = 512$ would be approximately $512 \cdot \ln(512) \approx 3200$ — over $12\times$ larger than the default $m = 256$ used in all experiments. The paper acknowledges this gap between theory and practice only implicitly, noting in Appendix F.6 that "this limitation does not manifest itself in practice at the lengths we experimented with" — but offers no guidance on why $m = 256$ works or when it might stop working.

The consequence. A practitioner deploying Performers faces an unquantified risk: the default $m = 256$ may be insufficient for their sequence lengths, data modality, or accuracy requirements, but they cannot determine this without running full training experiments at multiple values of $m$. If $m$ is too small, the attention approximation degrades, and the error compounds across layers (as Figure 14 demonstrates). If $m$ is larger than necessary, the $O(Lmd)$ time complexity grows linearly with $m$, wasting compute that could have been allocated elsewhere. The absence of a principled selection criterion — even an empirical heuristic — means that Performer deployment requires expensive trial-and-error, undercutting one of the paper's core value propositions (that the method is a reliable drop-in replacement).

What evidence exists in the paper. Figure 4 shows MSE as a function of $m$ for the attention approximation in isolation at $L = 4096, d = 16$, demonstrating that error decreases with $m$ and that positive orthogonal features achieve a given MSE with roughly $2\times$ fewer features than IID-positive features. However, this is measured on randomly generated input data ($d = 16$), not on actual Transformer embeddings ($d = 512$), and it measures only the attention output approximation error — not downstream task performance. There is no end-to-end ablation over $m$ for any of the main experimental results (TrEMBL, PG-19, ImageNet64). The paper never answers: does accuracy continue improving with $m > 256$? Does it saturate? Could $m = 128$ have sufficed for PG-19? Could $m = 512$ have closed the remaining gap between Performer-softmax and Transformer-softmax? None of these questions are addressed.

Mitigation status. Not at all. The paper does not mention the lack of $m$ selection guidance as a limitation. The theoretical bound (Theorem 4) is provided but is acknowledged to be loose (Appendix F.6). No empirical heuristic (e.g., "$m \approx 0.5d$ works well in practice") is offered. The default $m = 256$ is presented as a fixed constant in Appendices A.3–A.4 without discussion of how it was chosen or when it should be changed. This is a significant practical gap because $m$ directly controls the speed-accuracy tradeoff, and users have no tools to navigate it.

---

The Method Has Not Been Demonstrated on Standard NLP Benchmarks Where Transformers Dominate

The assumption or constraint. All text experiments in the paper are on LM1B (a language modeling dataset used for the backward compatibility demonstration) and PG-19 (a long-document modeling dataset). Conspicuously absent are results on the tasks that established Transformers as the dominant architecture: machine translation (WMT), natural language understanding (GLUE/SuperGLUE), question answering (SQuAD), or summarization. The paper's protein and image experiments demonstrate generality across modalities, but they do not address the question most NLP practitioners would ask: "If I replace the attention in my BERT or T5 model with FAVOR+, will my GLUE score or BLEU score change?"

This is not a minor omission. The Transformer's defining breakthrough was on WMT translation (Vaswani et al., 2017), and BERT's masked language modeling + fine-tuning paradigm (Devlin et al., 2018) is the foundation of most production NLP systems. The paper positions Performers as drop-in replacements for regular Transformers, but never tests this on the tasks where regular Transformers are actually deployed. PG-19, while useful for stress-testing long-context capabilities, is a niche benchmark — it tests language modeling perplexity on century-old books, which is a very different task from the structured prediction problems (classification, span extraction, generation with constraints) that dominate NLP applications.

The consequence. A practitioner considering Performer for an NLP deployment has no evidence that it preserves accuracy on the tasks they care about. The PG-19 results show that positive softmax features with redrawing can match Transformer perplexity — but perplexity on long-form text is a weak proxy for downstream task performance. The error propagation analysis (Figure 14) shows that attention approximation errors compound across layers, and it is entirely possible that these accumulated errors, while invisible in language modeling loss, would degrade performance on tasks requiring precise token-level predictions (e.g., named entity recognition, coreference resolution) or tasks where attention patterns are interpretable and structured (e.g., syntactic parsing, where specific heads attend to specific syntactic relations; Vig & Belinkov, 2019). The protein experiments provide some evidence that the approximation is tight enough for masked token prediction (Performer-softmax achieves 33.00% vs. Transformer's 33.32% in Table 2), but protein sequences have very different statistical structure from natural language — amino acid vocabularies are tiny (25 tokens vs. 32K+ for text), and the dependencies are governed by physico-chemical constraints rather than hierarchical syntax and semantics.

What evidence exists in the paper. The Long Range Arena results (Appendix D.5, Figure 19) partially address this gap — they include byte-level text classification and document retrieval, which are NLP tasks. The Performer achieves strong scores here (64.71% on text classification, 80.46% on retrieval), but these are relatively small-scale benchmarks compared to GLUE or WMT, and they are specifically designed to test long-range dependency handling rather than the full range of linguistic phenomena. The paper's own comparison table in Figure 19 shows that for ListOps (a task requiring hierarchical structure understanding), the Performer (36.00%) trails the vanilla Transformer (37.10%) and several non-scalable methods. No results are provided for machine translation, natural language inference, extractive QA, or any generation task with structured output constraints.

Mitigation status. The paper does not acknowledge this as a limitation. Section 1 states that Transformers "have become SOTA in several areas of machine learning including natural language processing (e.g. speech recognition, neural machine translation, document generation/summarization)" but then evaluates none of these NLP tasks. The absence of standard NLP benchmarks is not discussed or justified. A reader could reasonably conclude that the authors either (a) tried these tasks and obtained unfavorable results, (b) deemed NLP less important than protein modeling and image generation (which would be an unusual priority given the Transformer's origins), or (c) simply did not prioritize closing this evaluation gap.

---

The Theoretical Guarantees Govern the Attention Layer in Isolation, Not the Full Multi-Layer Model

The assumption or constraint. The paper's theoretical results — unbiased estimation (Lemma 1), variance reduction from positivity (Lemma 2) and orthogonality (Theorems 2–3), uniform convergence (Theorem 4) — all apply to the attention mechanism as a standalone function. They bound the error between the approximate attention output $\widehat{\text{Att}}(\mathbf{Q}, \mathbf{K}, \mathbf{V})$ and the exact output $\text{Att}(\mathbf{Q}, \mathbf{K}, \mathbf{V})$ for a fixed set of query, key, and value matrices. However, in a multi-layer Transformer, the output of one attention layer becomes the input to the next (after MLP transformation, layer normalization, and residual addition). Small per-layer approximation errors can be amplified by subsequent nonlinear transformations, and the paper provides evidence that this amplification is substantial in practice.

Figure 14 (Appendix D.1) directly quantifies this effect: the output approximation error between a Performer and an identical Transformer grows with the number of layers. The paper states that "error propagation due to non-attention components of the Transformer is one of the primary reasons that pretrained Transformer weights cannot be immediately used for inference on the corresponding Performer" — the initial accuracy of 0.07 when transferring Transformer weights to a Performer (Figure 5, left) demonstrates that error accumulation can be catastrophic even when each individual attention block is well-approximated. This means the theoretical guarantees, while mathematically rigorous, do not bound the behavior that matters most: the end-to-end model output disparity for a given input.

The consequence. The paper's strongest selling point — "provably accurate estimation of regular (softmax) full-rank attention" — applies at a level of abstraction (single attention layer, fixed inputs) that does not translate into guarantees about trained model behavior. A practitioner cannot look at Theorem 4's uniform convergence bound and conclude that their 12-layer Performer will achieve accuracy within $\epsilon$ of a 12-layer Transformer on a downstream task. The error propagation through subsequent layers depends on the Lipschitz constants of the MLP, layer normalization, and residual connections, which are trained and therefore data-dependent. In the worst case, if the network learns to amplify certain attention patterns (e.g., by having large MLP weights for tokens that receive high attention), small per-layer errors could compound exponentially. The paper provides no theoretical or empirical bound on this propagation.

Furthermore, the backward compatibility experiment shows that even with the best attention approximation, fine-tuning is required — the Performer cannot simply be plugged into a pretrained Transformer and used immediately. This directly contradicts the claim in Section 6 that "FAVOR+ can still be used for fast inference with no loss of accuracy" without up-training. In practice, some amount of adaptation is necessary, and the paper does not characterize how much (in terms of training steps, data volume, or final accuracy gap) is required across different tasks.

What evidence exists in the paper. Figure 14 is the only direct measurement of error propagation across layers. It shows that the output divergence between Transformer and Performer increases monotonically with layer depth, but provides no quantitative bounds (the y-axis scale is not specified, and it's unclear whether the error is measured in absolute difference, relative difference, or cosine distance). Figure 5 (left) demonstrates the practical consequence: 0.07 initial accuracy on LM1B when transferring weights. The recovery is shown to be rapid, but only for this specific dataset and model configuration. There is no experiment testing whether the required fine-tuning budget scales with model depth, task complexity, or sequence length.

Mitigation status. The paper acknowledges error propagation as the reason fine-tuning is needed (Section 4.3: "small errors can easily propagate throughout multiple Transformer layers") and provides Figure 14 as evidence. However, it does not treat this as a formal limitation of the theoretical framework. The gap between layer-level guarantees and model-level behavior is never explicitly discussed as a limitation, and no attempt is made to bound the propagation analytically (e.g., by analyzing the Lipschitz constants of Transformer components). The paper suggests future work on "pretraining or finetuning models to directly predict difficulty" (Section 8, from the main text), but this refers to a different issue. The error propagation problem is left unresolved — the solution is simply to fine-tune the Performer, which is a practical workaround but undermines the strength of the theoretical claims.

---

The Orthogonal Random Feature Constraint $m \leq d$ Limits Scaling to Large Feature Counts and High-Dimensional Heads

The assumption or constraint. The orthogonal random feature mechanism (both R-ORFs with Gram-Schmidt and the H/G-ORF variants) requires $m \leq d$, where $m$ is the number of random features and $d$ is the per-head dimension of queries and keys. This constraint is intrinsic: you cannot have more than $d$ mutually orthogonal vectors in $\mathbb{R}^d$. The paper states this explicitly ("The ORF mechanism requires $m \leq d$") and notes that "this will be the case in all our experiments" (Section 2.4). In the paper's default configuration, $m = 256$ and $d = 512$, so the constraint is satisfied with $m = d/2$.

The consequence. The $m \leq d$ constraint creates two problems that the paper does not address. First, it prevents users from arbitrarily increasing $m$ to improve approximation quality. If a practitioner finds that $m = 256$ is insufficient for their task (e.g., very long sequences where the attention approximation error becomes noticeable), they cannot simply increase $m$ to 512 or 1024 while maintaining orthogonality — they would be capped at $m = d$. To increase $m$ beyond $d$, they would need to either (a) increase $d$ (which changes the model architecture and requires retraining from scratch, not just fine-tuning), (b) use IID features instead of orthogonal ones (sacrificing the variance reduction from Theorem 2), or (c) use the block-orthogonal approach mentioned briefly in Appendix B.2 ("ORFs still can be used locally within each $d \times d$ block"), which provides only partial orthogonality and whose variance properties are not analyzed in the paper.

Second, the constraint becomes binding in architectures with many attention heads, each having small per-head dimension. Multi-head attention splits the $d_{model}$-dimensional queries, keys, and values into $h$ heads of dimension $d_k = d_{model} / h$. For large models, $h$ can be substantial — e.g., GPT-3 uses $h = 96$ or $h = 128$ heads, with $d_k = 128$ or $d_k = 96$. In such configurations, the maximum $m$ under orthogonality would be $m \leq d_k = 96$–$128$, less than half the paper's default $m = 256$. The paper provides no results or guidance for such architectures. A user with a many-head, small-per-head-dimension model would need to either reduce the number of heads (potentially degrading the model's ability to capture diverse attention patterns) or forgo orthogonality (sacrificing variance reduction).

What evidence exists in the paper. The paper never tests configurations where $m$ approaches or exceeds $d$. All experiments use $d = 512$ (for the standard architecture) or $d = 256$ (for the concatenated TrEMBL Transformer baseline), with $m = 256$, so $m/d$ ranges from 0.5 to 1.0. The approximation error experiments in Figure 4 use $d = 16$, with $m$ ranging from 2 to 128 — when $m > 16$, the orthogonal variant must use a method different from what the paper's theorems cover (since Theorem 2 assumes the standard ORF mechanism with $m \leq d$), but this is not discussed. The paper mentions block-orthogonal approaches in Appendix B.2 as an extension for $m > d$, but provides no theoretical analysis (no variance bounds for block-orthogonal vs. fully orthogonal) and no empirical results.

Mitigation status. The paper acknowledges the constraint ("The ORF mechanism requires $m \leq d$") but treats it as benign because it holds for the specific experiments conducted. The block-orthogonal extension is mentioned as possible but not analyzed. The $m > d$ case is essentially unaddressed — a user who needs more features for better approximation or who uses an architecture with small per-head dimension receives no guidance. This is a practical limitation for scaling Performers to the large-model, many-head regime that dominates modern NLP (GPT-3, PaLM, LLaMA).

---

The ReLU Kernel Advantage Over Softmax Is Ambiguous and May Be an Artifact of the Specific Protein Benchmark

The assumption or constraint. One of the paper's headline findings — that ReLU-based attention (generalized attention) outperforms both approximate and exact softmax attention — is based primarily on the TrEMBL protein sequence modeling benchmark (Figure 6, Table 2). The paper presents this as evidence that "the usefulness of generalized attention" is demonstrated, and that softmax may not be the optimal attention kernel. This finding is featured prominently in the abstract ("This representational power is crucial to accurately compare softmax with other kernels for the first time on large-scale tasks... and investigate optimal attention-kernels") and Section 4.4.

The consequence. The claim that ReLU outperforms softmax is not consistently supported across evaluation settings within the same task. Table 2 reveals an important asymmetry: on the IID test set (protein sequences drawn from the same distribution as training), Performer-ReLU achieves 36.09% bidirectional accuracy vs. Transformer-softmax's 33.32% — a 2.77 percentage point advantage. However, on the OOD test set (held-out Pfam families not seen during training), the Transformer-softmax achieves 25.07% vs. Performer-ReLU's 24.10% — softmax outperforms ReLU by 0.97 points. This reversal is not discussed anywhere in the paper. It suggests that the ReLU kernel may overfit to in-distribution sequence patterns while softmax provides better generalization to novel protein families — precisely the opposite of what a practitioner would conclude from reading only the abstract and Figure 6.

Furthermore, the paper's own kernel sweep (Appendix D.3, Figures 16–17) was conducted at $L = 512$ on smaller TPU configurations (2×2 and 4×4), not at the full experimental scale ($L = 1024$, 16×16 TPU-v2). The paper acknowledges that "the effective batch size slightly affects the rankings (as shown by the difference between 2×2 and 4×4 TPU runs)" — meaning the optimal kernel choice is not stable across compute configurations. The claim that ReLU is "empirically optimal for large batch size runs (i.e. 8×8 or 16×16 TPU's)" is stated in Appendix D.3 but never actually demonstrated — no kernel sweep at 8×8 or 16×16 scale is presented. The ImageNet64 results (Appendix D.2) further complicate the picture: Performer-ReLU, Performer-Softmax, and Performer-Softmax (SMREG) achieve nearly identical BPD (3.67, 3.69, 3.67), showing no ReLU advantage.

What evidence exists in the paper. The IID/OOD discrepancy is visible in Table 2 but is not commented on. The kernel sweep figures (16–17) show training accuracy curves for different kernels but no validation or test set results, and the curves are truncated when kernels produce NaN errors — making it difficult to assess whether the ranking is robust. The only task where ReLU shows a clear advantage over softmax is TrEMBL IID bidirectional — on TrEMBL IID unidirectional, the gap is smaller (31.58% vs. 30.80%), and on OOD both directions show softmax superiority. On ImageNet64, the kernels are tied. No text experiments compare ReLU to softmax.

Mitigation status. The paper does not acknowledge the IID/OOD reversal, the limited scale of the kernel sweep, or the task-specificity of the ReLU advantage as limitations. The claim that softmax is not necessarily optimal is presented as a general insight, but the evidence base for this claim is narrow (one dataset, one split) and contradicted by the OOD results within the same dataset. A fair characterization would be: "On in-distribution protein sequences, ReLU attention outperforms softmax; on out-of-distribution protein families, softmax is superior; on images, the kernels perform equally; on text, no comparison is available." The paper instead presents a simplified narrative that may mislead practitioners into adopting ReLU attention for domains where softmax would perform better.

---

Feature Redrawing Is Necessary but Poorly Characterized — No Schedule, No Cost Analysis, No Ablation

The assumption or constraint. The paper identifies feature redrawing (periodically resampling the random projection matrix $\boldsymbol{\Omega}$) as essential for matching Transformer performance: "Positive softmax with feature redrawing is necessary to match the Transformer" (Section 4.3), and Figure 5 (right) and Figure 15 (left) demonstrate that without redrawing, training can degrade or plateau. The explanation — that redrawing averages approximation errors over the course of training — is intuitive, but the paper provides no guidance on how frequently to redraw, no analysis of the computational cost of redrawing relative to training, and no ablation comparing different redrawing schedules.

The consequence. A practitioner implementing FAVOR+ faces an underspecified component that the paper identifies as critical. Should features be redrawn every training step? Every epoch? Only when the loss plateaus? The paper's Figure 15 (left) shows redrawing at a single vertical line (step not specified), after which the unlucky Seed 1 training recovers — but this tells us nothing about the optimal frequency. If features are redrawn too frequently, the model sees constantly changing attention approximations and may struggle to converge (the attention landscape shifts under it). If too infrequently, the model may overfit to a particular approximation, as Seed 1 does. The computational cost of redrawing — generating new random vectors and, for R-ORFs, running Gram-Schmidt orthogonalization — is described as "cheap" (Section 4.2) but never quantified. Gram-Schmidt on a matrix of size $m \times d$ costs $O(md^2)$, which for $m = 256, d = 512$ is approximately $256 \cdot 512^2 \approx 67$ million operations — negligible compared to a full training step's $O(Lmd)$ forward pass cost when $L$ is large, but potentially non-trivial if redrawing occurs every few steps.

What evidence exists in the paper. Figure 15 (left) shows exactly one redrawing event for one seed. Figure 5 (right) states that redrawing is used for the positive features curve that matches the Transformer, but does not specify the schedule. The defaults in Appendices A.3–A.4 list ortho_features = True and number_of_features = 256 but contain no parameter controlling redrawing frequency. The paper notes that redrawing "can be further optimized" (Section 4.2) without elaboration. The Long Range Arena results (Appendix D.5) use the Performer with an unspecified redrawing schedule. The Linformer comparison is run "with redrawn projections" (Appendix A.6), suggesting awareness that redrawing matters, but the Performer's own redrawing protocol remains undocumented.

Mitigation status. Not at all. Redrawing is treated as a practical trick whose details do not merit specification, despite being described as "necessary" for the method to work. There is no ablation comparing redrawing frequencies, no recommendation (e.g., "redraw every 1000 steps worked well in our experiments"), and no analysis of whether the optimal frequency depends on sequence length, model size, or task. This makes the paper's recipe incomplete — a practitioner cannot reproduce the reported results without guessing the redrawing schedule used in the experiments.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper shifts the conversation around efficient Transformers from "what structural assumptions can we impose to make attention cheaper?" to "can we directly approximate the exact softmax attention with linear complexity and strong guarantees?" Before Performers, the field had largely accepted that efficient attention required tradeoffs: you could have sparsity (Sparse Transformer, Longformer), locality-sensitive hashing (Reformer), learned low-rank projections (Linformer), or kernel substitution (Linear Transformer), but you could not have the original softmax attention itself at linear cost. Each alternative came with implicit costs — assumptions about which tokens should attend to which, hardware-specific implementation complexity, absence of approximation guarantees, or training instability.

FAVOR+ demonstrates that these tradeoffs are not fundamental. The exact softmax kernel — the same function that defines regular Transformer attention — can be approximated with unbiased estimation, provable convergence, and practical stability, using only matrix multiplications that run efficiently on standard hardware. This is a reframing of the problem rather than a paradigm shift: the attention efficiency challenge is recast from "find a cheaper attention-like function" to "find a low-variance random feature decomposition of the softmax kernel." The key insight — that positivity of the random features is the critical property, not just unbiasedness — resolves the contradiction between the theoretical appeal of random Fourier features and their practical failure in attention. Prior attempts at random feature attention (Tsai et al., 2019) produced unstable training not because random features are inherently too noisy, but because the specific feature map ($\sin$/$\cos$) has variance that diverges in the regime that dominates long-sequence attention matrices. FAVOR+ fixes this with a feature map whose variance tends to zero in that same regime.

The paper also reframes the attention kernel itself as a design choice, not a fixed architectural constant. By providing a single mechanism that implements any kernel (softmax, ReLU, GELU, absolute value) with identical $O(Lmd)$ complexity, Performers enable the first fair large-scale comparisons between attention kernels. The finding that ReLU attention outperforms softmax on in-distribution protein sequences (Table 2: 36.09% vs. 33.32% bidirectional) — even if the OOD results complicate the picture — opens the door to treating kernel selection as a per-task hyperparameter rather than a settled architectural decision. This is a concrete methodological shift: future Transformer research should not assume softmax is optimal without testing alternatives, and FAVOR+ provides the tool to do so at scale.

Three research directions become more attractive as a direct consequence. First, verifier and reward model design for long sequences benefits because FAVOR+ provides a way to apply softmax attention to contexts that were previously too long for exact computation — entire documents, multi-protein complexes, high-resolution images — without the uncontrolled approximation error of sparse methods. Second, random feature theory for attention specifically becomes viable as a subfield: the paper's analysis of variance scaling in the small-kernel regime (Lemma 2) and the role of orthogonality for finite $d$ (Theorem 2, the "beautiful functions" framework in Appendix F.4) provide theoretical tools that were not previously developed for the attention setting. Third, efficient Transformers for scientific domains (protein modeling, genomics, materials science) become more promising because the paper demonstrates that the Performer's efficiency gains are largest precisely where standard Transformers are most constrained — long sequences where the data has inherent structure that dense softmax attention can capture but sparse approximations might miss.

Conversely, certain directions become less attractive. The paper provides strong evidence that purely sparse attention methods (fixed patterns, LSH-based grouping) face fundamental limitations: on the TrEMBL protein benchmark, both the Reformer and Linformer "significantly drop in accuracy" compared to the Performer and exact Transformer (Figure 6). While these methods may still be suitable for tasks where sparsity patterns align with task structure (e.g., local context in text), the paper suggests that for domains where dense, long-range interactions matter — such as protein folding, where amino acids far apart in sequence can be adjacent in 3D structure — methods that approximate the full attention matrix rather than restricting it have an inherent advantage. Similarly, the Linear Transformer's repeated training instability (Appendix D.4: all 3 unidirectional seeds and 1 bidirectional seed produced exploding gradients) suggests that kernel substitution without careful variance control is a risky strategy, and future work should prioritize mechanisms (like FAVOR+'s positive features) that guarantee well-behaved training dynamics.

Follow-Up Research This Work Enables

Rigorous characterization of the ReLU vs. softmax kernel tradeoff across domains and distribution shifts. The paper's most intriguing empirical finding — that ReLU attention outperforms softmax on in-distribution protein sequences but underperforms on out-of-distribution families (Table 2: bidirectional test accuracy 36.09% ReLU vs. 33.32% softmax IID, but 24.10% ReLU vs. 25.07% softmax OOD) — is presented without discussion or hypothesis. A strong follow-up would systematically test whether this pattern generalizes: do non-softmax kernels consistently show higher IID performance but worse OOD generalization across domains (text, images, proteins, audio)? A concrete experiment would train Performer-ReLU and Performer-softmax on multiple datasets with natural distribution shifts (e.g., different protein families, different text domains from the GLUE benchmark, different image categories) and measure whether the kernel ranking reverses under distribution shift. If this pattern holds broadly, it would suggest that softmax's normalization properties (row-wise probability distributions that sum to 1) provide an implicit regularization that improves generalization — a property that task-optimized kernels like ReLU sacrifice for better in-distribution fit. This would fundamentally reframe kernel selection as a bias-variance tradeoff (softmax = higher bias, better generalization; ReLU = lower bias, potential overfitting) rather than a simple accuracy comparison.

End-to-end learning of the attention kernel function via meta-learning or architecture search. The paper's generalized attention framework (Equation 5) parameterizes the kernel through a univariate function $f: \mathbb{R} \to \mathbb{R}$ applied to random projections. Currently, $f$ is chosen from a fixed set (ReLU, exp, GELU, etc.) based on manual sweeps. A natural extension is to make $f$ itself learnable — either by parameterizing it as a small neural network, or by using hypernetwork-style conditioning where $f$ is predicted from the input data. The specific architecture could be: instead of a fixed nonlinearity, use $f(x; \theta) = \text{MLP}_\theta(x)$ where $\theta$ is trained jointly with the Transformer. This would allow the kernel to adapt to the specific statistics of the data distribution, potentially discovering kernel shapes that outperform both softmax and hand-chosen alternatives. The experiment would compare learned-kernel Performers against fixed-kernel Performers and exact-softmax Transformers on multiple benchmarks (proteins, text, images), measuring whether the learned kernel consistently matches or exceeds the best hand-chosen kernel for each task, and whether the learned kernel converges to different shapes for different data modalities. The computational overhead would be modest because $f$ operates elementwise on projected scalars ($\boldsymbol{\omega}_i^\top \mathbf{x}$) rather than on high-dimensional vectors, so a small MLP with 2-3 hidden layers would add negligible FLOPs compared to the $O(Lmd)$ attention cost.

Scaling $m$ to the theoretical bound and measuring the accuracy-compute Pareto frontier. The paper uses $m = 256$ random features for all experiments, but Theorem 4 suggests $m = \Theta(d \log d) \approx 3200$ for $d = 512$, and the approximation error experiments (Figure 4) show MSE continuing to decrease with $m$ up to the maximum tested ($m = 128$ at $d = 16$). A critical open question is: where is the optimal accuracy-compute operating point, and how does it scale with sequence length and task difficulty? A follow-up study would train Performer models at multiple values of $m$ (e.g., 64, 128, 256, 512, 1024) on a fixed task (e.g., PG-19 language modeling or TrEMBL protein prediction) and measure both downstream accuracy/perplexity and total training wall-clock time. The resulting Pareto frontier would tell practitioners exactly how much they gain from increasing $m$ and at what point diminishing returns set in. This experiment would also stress-test the orthogonal random feature constraint $m \leq d$: for $m = 512$ at $d = 512$, the orthogonal matrix is square (a full rotation), while for $m = 1024$, orthogonality is impossible without block-orthogonal constructions. Comparing full-orthogonal ($m \leq d$) against block-orthogonal ($m > d$) and IID features at the same $m$ would quantify how much of the orthogonal advantage (Theorem 2's variance reduction) is preserved under block-orthogonal approximations, providing practical guidance for high-$m$ regimes.

FAVOR+ combined with retrieval-augmented generation for extremely long contexts. The paper demonstrates training at $L = 8192$ (concatenated proteins) and $L = 12,288$ (ImageNet64), but many real-world applications require contexts orders of magnitude longer — entire books ($10^5$–$10^6$ tokens), full proteomes ($10^6$+ amino acids), or video sequences. FAVOR+ scales linearly with $L$, so in principle it can handle such lengths, but the $O(Lmd)$ time and $O(Lr + Ld + rd)$ space would become the bottleneck for $L$ in the millions. A natural extension is to combine FAVOR+ with retrieval: instead of attending over all $L$ tokens, first retrieve a subset of $k \ll L$ relevant tokens (using maximum inner product search on the random feature vectors, since $\phi(\mathbf{q})^\top \phi(\mathbf{k})$ approximates the softmax score), then compute exact softmax attention only over the retrieved subset. The FAVOR+ random features serve double duty: they enable efficient attention approximation for the initial coarse filtering, and the same feature vectors can be used for the retrieval step. A concrete experiment would benchmark Performer-Retrieval against Performer-Full and standard sparse-attention Transformer on a long-document QA task (e.g., NarrativeQA or a custom benchmark with sequences of $10^5$+ tokens) to measure whether retrieval-augmented FAVOR+ maintains accuracy while achieving sub-linear scaling in $L$.

Systematic stress-test of backward compatibility across diverse pretrained models and tasks. The paper's backward compatibility demonstration (Figure 5, left) is limited to a single dataset (LM1B) with one model configuration. A rigorous stress-test would measure the fine-tuning budget required for Performer conversion across: (a) different pretrained model families (BERT-base, BERT-large, T5, GPT-2), (b) different downstream tasks (GLUE classification, SQuAD span extraction, summarization), and (c) different conversion strategies (direct weight copy vs. attention distillation where the Performer is trained to match the original model's attention outputs layer-by-layer before task fine-tuning). The key metric would be: what fraction of the original pretraining steps is needed to recover within $\epsilon$ of the original model's task performance? If the fraction is consistently small (<10%) across diverse settings, Performers become a practical drop-in acceleration tool for existing pretrained models. If the fraction varies substantially (e.g., 5% for classification but 50% for generation), it would reveal task-specific sensitivity to attention approximation error that practitioners need to account for. This experiment would also directly address the gap between the paper's theoretical guarantees (which apply to the attention layer in isolation) and the practical reality of error propagation through multi-layer networks (Figure 14).

Practical Applications and Downstream Use Cases

Protein language modeling at proteome scale for interaction prediction. The most directly motivated application from the paper is scaling protein Transformers to model entire interaction networks. Current methods for predicting protein-protein interactions require large evolutionary sequence alignments as input, which is "a bottleneck for applications to mammalian genomes" (Section 6). The concatenated TrEMBL experiment (Figure 7, right) provides a proof of concept: a Performer with the standard (8, 6, 2048, 512) architecture trains at $L = 8192$ and batch size 8 per chip, reaching ~24% accuracy and still improving, while a regular Transformer must be shrunk to (8, {1,2,3}, 256, 256) and plateaus at ~19%. The practical benefit is clear: protein interaction networks involve groups of proteins whose concatenated sequences can span tens of thousands of residues. Transformers that can process these sequences end-to-end — without the quadratic bottleneck forcing truncation or alignment-based preprocessing — could directly learn interaction patterns from raw sequence data, enabling faster and more scalable prediction of protein complex formation, drug-target interactions, or the effects of mutations on protein binding. The Performer's ability to train at batch size 8 per chip where the Transformer cannot even run at batch size 1 (Section 4.5) converts an infeasible computation into a practical one on available hardware (16×16 TPU-v2 pods).

Long-document processing for legal, scientific, and medical text. The PG-19 experiments (Figure 5, right) demonstrate that Performers with positive softmax features and redrawing can match Transformer perplexity on book-length text. For applications like legal document review (contracts can run to hundreds of pages), scientific literature synthesis (full papers with references spanning thousands of tokens), or medical record analysis (patient histories with years of notes), the $O(L^2)$ attention cost makes standard Transformers impractical for processing complete documents in a single pass. The Performer's linear scaling means a single forward pass over a 10,000-token document costs roughly the same as a 2,048-token pass in a standard Transformer, enabling models that can directly attend across entire documents rather than chunking them into overlapping segments (which breaks cross-chunk dependencies). The practical benefit is not just speed — it is the ability to capture long-range dependencies (a key term defined on page 3 and referenced on page 25) that chunking destroys, such as a contract's definitions section governing the interpretation of clauses 50 pages later, or a patient's early symptoms explaining a diagnosis recorded months afterwards.

High-resolution image generation without architectural compromises. The ImageNet64 experiment (Figure 7, left) shows Performers matching Reformer performance at half the model depth (Performer/6-layers ~ Reformer/12-layers; Performer/12-layers ~ Reformer/24-layers). In production image generation systems, this efficiency translates directly to either (a) generating higher-resolution images at the same computational budget, or (b) reducing serving costs for a given resolution. The Performer's dense softmax approximation attends to all $L = 12,288$ pixels simultaneously, while sparse methods attend to subsets — the paper's finding that the Performer achieves equivalent performance with fewer layers suggests that dense attention extracts more information per layer, reducing total model depth requirements. A deployed image generation pipeline could replace a 24-layer Reformer with a 12-layer Performer, approximately halving inference latency while maintaining generation quality (both achieve ~3.67 BPD on ImageNet64 after 100K steps).

When to Prefer This Method

The paper explicitly positions FAVOR+ against specific alternative efficient attention mechanisms, and the experimental results provide clear decision boundaries. The following guidance is grounded in which comparisons were made and where the advantages were demonstrated:

• Prefer FAVOR+ (Performer) over exact-softmax Transformers when sequence lengths exceed the memory capacity of available hardware for the desired model size. The paper's computational cost benchmarks (Figure 3) show that on a 16GB V100 GPU with the standard (8, 6, 2048, 512) architecture, the Transformer hits out-of-memory at approximately $L = 2048$ while the Performer scales past $L = 32{,}768$. The crossover point will vary with hardware, but the principle is clear: if your target sequence length cannot fit in memory with exact attention, FAVOR+ enables training where the alternative is not a slower Transformer but no Transformer at all. The concatenated TrEMBL experiment (Section 4.5) provides the concrete failure case: the standard Transformer "overloads memory even at a batch size of 1 per chip, by a wide margin" at $L = 8192$, forcing a drastic model size reduction to (8, {1,2,3}, 256, 256).

• Prefer FAVOR+ over sparse attention methods (Reformer, Linformer) when the task requires dense, potentially long-range interactions without strong locality structure. The TrEMBL protein experiment (Figure 6) shows Reformer and Linformer accuracy dropping "significantly" below both the Transformer and Performer, while the Performer matches or exceeds the Transformer. For protein sequences, where amino acids distant in the primary sequence are often adjacent in folded 3D structure, restrictive sparsity patterns miss functionally critical interactions. The ImageNet64 results (Figure 7, left) similarly show that dense softmax approximation (Performer) extracts more signal per layer than LSH-based sparsity (Reformer), requiring half the depth for equivalent performance.

• Prefer the generalized ReLU kernel over softmax approximation (within FAVOR+) when the task involves data with different statistical properties than natural language, and you have a representative validation set for kernel selection. The TrEMBL IID results (Table 2: 36.09% ReLU vs. 33.32% softmax bidirectional) demonstrate meaningful gains for protein sequences. The kernel sweep (Figures 16–17) provides a template: train small-scale runs with multiple kernels, select the best performer on validation data, then scale up. However, the OOD reversal (softmax outperforms ReLU on held-out protein families: 25.07% vs. 24.10%) means that if generalization to out-of-distribution samples is critical, softmax's implicit regularization may be safer than a kernel optimized for in-distribution fit.

• Do not prefer FAVOR+ (or prefer it only with the softmax approximation kernel) when backward compatibility with existing pretrained models is essential and fine-tuning budget is extremely limited. The paper shows that weight transfer requires fine-tuning (Figure 5, left): the Performer starts at 0.07 accuracy on LM1B after weight transfer from a trained Transformer, recovering only after "a small fraction of the original number of gradient steps." If the use case demands immediate deployment without any retraining (e.g., a frozen pretrained model serving inferences in production), the approximation error propagation (Figure 14) prevents zero-shot transfer. The Linformer shares this limitation; Reformer and sparse methods are not backward-compatible at all. Among efficient Transformers, only FAVOR+ offers backward compatibility with fine-tuning — but it is not a zero-cost property.