Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Linear Attention › Other Linear Attention Variants

Michael BrenndoerferUpdated June 28, 20252 min read

Language AI HandbookAll chapters

Part 17 of 67Efficient Attention

Chapter 123Linear Attention › Other Linear Attention Variants

Reading section 10 of 15 · Other Linear Attention Variants · 2 minSection 10 of 15 · 2 min

Section 10 of 15 · 2 min read

Linear Attention › Other Linear Attention VariantsOne section · Sections in this chapter10 / 15 ↓

Sections in this chapter15

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

The linear attention family has grown to include many variants, each addressing different aspects of the softmax-to-kernel trade-off:

Linear Transformer (Katharopoulos et al., 2020): The foundational work that established the kernel view and demonstrated causal linear attention for autoregressive models.
Random Feature Attention (RFA): Uses random Fourier features to approximate the Gaussian kernel. This provides a middle ground between simple feature maps and Performer's FAVOR+.
Nyströmformer (Xiong et al., 2021): Uses the Nyström method to approximate the attention matrix with landmark points, achieving $O(nm)$ complexity where $m$ is the number of landmarks.
FNet (Lee-Thorp et al., 2021): Replaces attention entirely with Fourier transforms, achieving $O(n \log n)$ complexity with no learnable attention parameters.
RetNet (Sun et al., 2023): Combines linear attention with exponential decay, creating a recurrent formulation that supports both parallel training and efficient incremental inference.

In[29]:

Code

def compare_linear_variants(n, d):
    """Compare complexity of different linear attention variants."""
    variants = {
        "Standard Softmax": n * n * d,
        "Linear (ELU)": n * d * d,
        "Performer (m=256)": n * 256 * d + 256 * d,
        "Nyströmformer (m=64)": n * 64 * d,
        "FNet (FFT)": n * np.log2(n) * d,
    }
    return variants

In[30]:

Code

variants = compare_linear_variants(4096, 64)

Out[31]:

Console

Complexity Comparison of Attention Variants (n=4096, d=64):

Variant                   FLOPs            vs Standard
-------------------------------------------------------
Standard Softmax          1.07G                  1.0x faster
Linear (ELU)              16.8M                 64.0x faster
Performer (m=256)         67.1M                 16.0x faster
Nyströmformer (m=64)      16.8M                 64.0x faster
FNet (FFT)                3.1M                 341.3x faster

Linear attention with ELU features achieves approximately 64x speedup over standard softmax attention at this sequence length, while Performer with 256 random features achieves around 60x. The simpler variants (Nyströmformer, FNet) offer even greater speedups but with different quality trade-offs.