LLM & VLM courseBlog
99Track 5: LLM inference and serving · session 22 of 65

Efficient attention 3: kernel-based attention (Linear Transformer, Performer, RFA)

Softmax attention builds an n × n table because the exponential ties every query to every key. This session replaces exp(q·k) with a dot product of feature vectors φ(q)·φ(k), so the order of the matrix products can change and the cost becomes linear in n. You will see the Linear Transformer (elu + 1), the random-feature methods Performer (FAVOR+) and RFA that try to copy softmax, the RNN form that decodes with a fixed-size state, and why these models lose the sharp, peaked attention that exact recall needs.

Time: 2.5 to 3.5 hours (reading 1.5 to 2 hours, exercises 1 to 1.5 hours)Level: IntermediateBefore this: Sessions 17 to 20 (attention, masks, multi-head), 80 (the KV cache), 98 (low-rank attention)

What you will learn

  • Write attention as a kernel smoother and see that softmax uses the kernel exp(q·k/√d), which has no finite feature map
  • Use associativity: compute φ(K)ᵀV once (an r × d matrix) and get cost 4nrd instead of 2n²(r + d)
  • Turn causal linear attention into an RNN with a state S and a normalizer z, and train it with the parallel or the chunked form
  • Approximate softmax with random features: sin/cos (Rahimi–Recht, RFA) and positive orthogonal features (Performer, FAVOR+), and read their error formulas
  • Explain why quality drops: rank at most r, a fixed-size state, flat weights, and no exact recall; and how gates, decay and hybrids answer this
  • Know where kernel attention lives today: hybrid long-context LLMs, encoders over long inputs, and the next sessions on state space models

Why this matters

Softmax attention builds, for every head, a table with one score for every pair of tokens. At \(n = 4096\) tokens that is 16.8 million scores per head; at \(n = 131{,}072\) it is 17.2 billion. During generation, the KV cache that feeds this table grows by one row per token and never shrinks. This session asks a simple question: can we change the similarity function so that the table is never needed?

The answer is yes, if the similarity between a query and a key can be written as a dot product of two feature vectors, \(\phi(\mathbf q)^\top \phi(\mathbf k)\). Then we can multiply the matrices in a different order. We first add up all keys and values into one small \(r \times d\) matrix, and then every query reads from it. The cost becomes linear in \(n\), and causal decoding becomes a recurrent neural network (RNN) with a fixed-size state: the memory per head is the same at token 10 and at token 10 million.

The efficient-inference survey of Zhou et al. lists this family as kernel-based attention in its section on efficient attention (5.1.2), next to the low-rank methods of session 98. Its members there are the Linear Transformer, Performer, RFA and PolySketchFormer. [Certain] We study the first three in depth:

  • Linear Transformer (Katharopoulos et al., 2020): a simple feature map, \(\phi(x) = \operatorname{elu}(x) + 1\), and the observation that causal linear attention is an RNN. The paper reports up to 4000× faster autoregressive prediction on very long sequences. [Certain]
  • Performer (Choromanski et al., 2020): random features that give an unbiased estimate of the softmax kernel itself, with positive and orthogonal features (the method is called FAVOR+).
  • RFA, Random Feature Attention (Peng et al., 2021): random Fourier features (sin and cos) for the same goal, plus a learned gate that adds a bias toward recent tokens.

The price is quality. These models cannot put almost all of their weight on one token the way softmax can, and a fixed-size state cannot store an unlimited number of facts. That trade-off is the main lesson. It explains why pure linear-attention LLMs are rare, why newer designs add gates and decay, and why the largest model built on this idea, MiniMax-01, still keeps one softmax layer after every seven linear ones. [Certain] It also leads straight into the next sessions on state space models (session 100).

Attention as a kernel smoother

Start from one head of scaled dot-product attention (session 17). Row \(i\) of the output is a weighted average of value vectors, and the weights come from a similarity function. Write that function as \(\kappa\), a kernel (a function that measures how similar two vectors are):

\[ \mathbf o_i = \frac{\sum_{j} \kappa(\mathbf q_i, \mathbf k_j)\, \mathbf v_j}{\sum_{j} \kappa(\mathbf q_i, \mathbf k_j)}, \qquad \kappa_{\text{soft}}(\mathbf q, \mathbf k) = \exp\!\left(\frac{\mathbf q^\top \mathbf k}{\sqrt d}\right) \tag{99.1} \]
Read the symbols
\(\mathbf q_i, \mathbf k_j, \mathbf v_j\)
the query of token \(i\), the key and value of token \(j\); each has \(d\) numbers (the head size)
\(\kappa(\mathbf q, \mathbf k)\)
a non-negative similarity score; dividing by the sum turns the scores into weights that add up to 1
\(\kappa_{\text{soft}}\)
the kernel hidden inside softmax attention; with it, (99.1) is exactly \(\softmax(QK^\top/\sqrt d)\,V\)
sums over \(j\)
over all tokens (bidirectional) or over \(j \le i\) (causal)

Formula (99.1) is the classic Nadaraya–Watson kernel smoother from statistics: predict at a point by averaging nearby examples, weighted by a kernel. Seen this way, softmax is just one choice of kernel, and nothing forces us to keep it.

Why does the exponential cost \(n^2\)? Because \(\exp(\mathbf q^\top \mathbf k)\) cannot be split into “a part that depends only on \(\mathbf q\)” times “a part that depends only on \(\mathbf k\)” with finitely many terms. Its Taylor series \(\sum_p (\mathbf q^\top \mathbf k)^p / p!\) has terms of every degree, so an exact feature map would need infinitely many dimensions. [Certain] So we must compute every pair \((i, j)\) separately.

Kernels that factor

Now pick a kernel that does factor. Let \(\phi: \R^d \to \R^r\) be a feature map, a function that turns a vector into \(r\) non-negative numbers, and set \(\kappa(\mathbf q, \mathbf k) = \phi(\mathbf q)^\top \phi(\mathbf k)\). Put this into (99.1). The query part does not depend on \(j\), so it moves out of both sums:

\[ \mathbf o_i^\top = \frac{\phi(\mathbf q_i)^\top \sum_{j} \phi(\mathbf k_j)\, \mathbf v_j^\top}{\phi(\mathbf q_i)^\top \sum_{j} \phi(\mathbf k_j)} \tag{99.2} \]

The two sums are the same for every query. In matrix form, with \(\phi\) applied to every row and \(\mathbf 1\) the vector of ones:

\[ O = \frac{\phi(Q)\,\big(\phi(K)^\top V\big)}{\phi(Q)\,\big(\phi(K)^\top \mathbf 1\big)} \qquad \text{instead of} \qquad O = \frac{\big(\phi(Q)\phi(K)^\top\big)\,V}{\big(\phi(Q)\phi(K)^\top\big)\,\mathbf 1} \tag{99.3} \]
Read the symbols
\(\phi(Q), \phi(K)\)
\(n \times r\) matrices: row \(i\) is \(\phi(\mathbf q_i)\) or \(\phi(\mathbf k_i)\)
\(\phi(K)^\top V\)
an \(r \times d\) matrix: the sum of the outer products \(\phi(\mathbf k_j)\mathbf v_j^\top\); it does not depend on \(n\) in size
\(\phi(K)^\top \mathbf 1\)
an \(r\)-vector, the sum of all key features; it gives the normalizer
division
row by row: each output row is divided by its own scalar normalizer

Both sides of (99.3) are the same numbers. Matrix multiplication is associative: \((AB)C = A(BC)\). The left side never builds an \(n \times n\) matrix.

What associativity buys

Count FLOPs (a multiply plus an add counts as 2) for one head, bidirectional case, with feature size \(r\) and value size \(d\):

\[ \underbrace{2n^2 r + 2n^2 d}_{(\phi(Q)\phi(K)^\top)V} = 2n^2(r + d) \qquad \text{vs.} \qquad \underbrace{2nrd + 2nrd}_{\phi(Q)(\phi(K)^\top V)} = 4nrd \tag{99.4} \]

The ratio is \(n(r + d)/(2rd)\). With \(r = d\) it is simply \(n/d\): the linear order wins once the sequence is longer than the head size. Memory changes even more: the quadratic order stores an \(n \times n\) matrix, the linear order an \(r \times d\) matrix.

Worked example: \(n = 4096\), \(r = d = 128\), one head, bidirectional

Quadratic order: \(2 \times 4096^2 \times 256 = 8.59 \times 10^9\) FLOPs and an \(n \times n\) matrix of \(16{,}777{,}216\) numbers.

Linear order: \(4 \times 4096 \times 128 \times 128 = 2.68 \times 10^8\) FLOPs and a state of \(128 \times 128 = 16{,}384\) numbers.

The FLOP ratio is \(4096/128 = 32\). Break-even is at \(n = 2rd/(r+d) = 128\). Below that, the linear order does more work. At \(n = 131{,}072\) the ratio is 1024.

Figure 1 shows both curves. Switch to “one new token” to see the decoding view, which matters most for serving.

quadratic order (softmax-like)linear order \(\phi(Q)(\phi(K)^\top V)\)
Figure 1. FLOPs per head for the two orders of formula (99.3), on a log-log scale. In “whole sequence” mode the curves are (99.4) with \(r = d\). In “one new token” mode the quadratic curve is softmax decoding with a KV cache (\(4nd\) FLOPs, \(2nd\) cached numbers) and the linear curve is one step of the RNN form (99.6), which costs \(4d^2\) whatever \(n\) is.
How to read Figure 1

Move \(n\) and watch the dots on the dashed line. The readout gives both FLOP counts, the memory of each order and the ratio \(n/d\). Set \(n = 128\) with \(d = 128\): the ratio is exactly 1. Set \(d = 256\) and \(n = 128\): the ratio is 0.5, so the linear order is slower for short inputs with large heads. In decode mode the linear curve is flat: this is the property that makes linear attention attractive for long generation.

Curves hide the mechanism. Figure 2 runs both orders on a few real 2-D tokens, one unit of work per step and both orders on the same clock. In the first half, the quadratic order fills one row of the \(n \times n\) table while the linear order writes one token into its small state \(M = \phi(K)^\top V\) and \(\mathbf s = \phi(K)^\top \mathbf 1\). In the second half, both produce one output row. The outputs agree to rounding error, but the counters do not. Switch the kernel to softmax to see why the trick needs a factorized kernel.

scores \(A_{ij}\) (\(n \times n\))\(\phi(\mathbf k)\)\(\phi(\mathbf q)\)values \(\mathbf v\)state \(M, \mathbf s\)output \(\mathbf o\)
  1. quadraticfor \(i, j = 1..n\): \(A_{ij} \leftarrow \phi(\mathbf q_i)^\top\phi(\mathbf k_j)\) // \(2n^2 r\) FLOPs, \(n^2\) numbers stored
  2. quadraticfor \(i = 1..n\): \(\mathbf o_i \leftarrow \sum_j A_{ij}\mathbf v_j \,/\, \sum_j A_{ij}\) // \(2n^2 d\) FLOPs
  3. linearfor \(j = 1..n\): \(M \leftarrow M + \phi(\mathbf k_j)\mathbf v_j^\top\), \(\;\mathbf s \leftarrow \mathbf s + \phi(\mathbf k_j)\) // \(2nrd\) FLOPs, \(rd + r\) numbers
  4. linearfor \(i = 1..n\): \(\mathbf o_i \leftarrow \phi(\mathbf q_i)^\top M \,/\, \phi(\mathbf q_i)^\top \mathbf s\) // \(2nrd\) FLOPs
  5. compare: \(\max |O_{\text{quad}} - O_{\text{lin}}|\), FLOPs and memory
Figure 2. Formula (99.3) computed in both orders, bidirectional, with \(d = r = 2\). Top: the quadratic order builds the table \(A = \phi(Q)\phi(K)^\top\) row by row, then multiplies it by \(V\) and divides by the row sums. Bottom: the linear order adds one outer product \(\phi(\mathbf k_j)\mathbf v_j^\top\) per step into \(M\), then every query reads from \(M\) and \(\mathbf s\). The FLOP counters count only the terms of (99.4); the feature maps and the normalizers are left out. In softmax mode the table holds \(\exp(\mathbf q_i^\top\mathbf k_j)\) (no \(1/\sqrt d\), to keep the numbers simple) and the linear order does not exist.
How to read Figure 2

Press Play, or Step through it. The highlighted lines in the algorithm box are the ones that run in this step, and the box next to it shows the same formulas with the real numbers. With \(n = 6\), the quadratic order ends at 288 FLOPs and 36 stored scores, the linear order at 96 FLOPs and 6 stored numbers (\(M\) has 4, \(\mathbf s\) has 2). The ratio is \(n/d = 3\). The two output columns are equal; the readout prints the largest difference (about \(10^{-16}\), float rounding). Try \(n = 8\): the quadratic counters grow like \(n^2\), the linear ones like \(n\). With \(n = 4\) the final \(M\) is exactly the state \(S_4\) that Figure 3 reaches token by token. In softmax mode, compare the output column with the elu + 1 one: the softmax outputs differ much more from row to row, because softmax weights are sharper.

The Linear Transformer: elu + 1 and the RNN view

A simple feature map

The weights in (99.2) must be non-negative, or the “average” can divide by a number near zero. Katharopoulos et al. use the simplest map that keeps every feature positive and keeps a gradient everywhere:

\[ \phi(x) = \operatorname{elu}(x) + 1 = \begin{cases} x + 1 & x \gt 0 \\ e^{x} & x \le 0 \end{cases} \qquad \text{(applied to each entry, so } r = d\text{)} \tag{99.5} \]

The exponential linear unit (elu) is preferred over ReLU because ReLU sets the gradient to zero for negative inputs. [Certain] This map does not try to copy softmax. It is a new kernel, \(\kappa(\mathbf q, \mathbf k) = (\operatorname{elu}(\mathbf q) + 1)^\top(\operatorname{elu}(\mathbf k) + 1)\), and the model learns to work with it.

Causal attention is an RNN

In a decoder the sums in (99.2) run only over \(j \le i\). That looks like a problem: each query has a different set of keys, so there is no single \(\phi(K)^\top V\). The fix is to notice that the prefix sums grow by one term per token. Call them the state \(S_i\) and the normalizer \(\mathbf z_i\):

\[ S_i = S_{i-1} + \phi(\mathbf k_i)\, \mathbf v_i^\top, \qquad \mathbf z_i = \mathbf z_{i-1} + \phi(\mathbf k_i), \qquad S_0 = 0,\ \mathbf z_0 = 0 \tag{99.6} \]
\[ \mathbf o_i^\top = \frac{\phi(\mathbf q_i)^\top S_i}{\phi(\mathbf q_i)^\top \mathbf z_i} \tag{99.7} \]
Read the symbols
\(S_i\)
an \(r \times d\) matrix: the sum of \(\phi(\mathbf k_j)\mathbf v_j^\top\) over \(j \le i\). It is the hidden state of an RNN and replaces the whole KV cache
\(\mathbf z_i\)
an \(r\)-vector: the sum of key features so far
\(\phi(\mathbf k_i)\mathbf v_i^\top\)
an outer product (an \(r \times d\) rank-1 matrix): the “write” of token \(i\) into memory
\(\phi(\mathbf q_i)^\top S_i\)
the “read”: a weighted combination of the rows of \(S_i\)

This is the claim in the paper’s title, “Transformers are RNNs”. Each decode step costs about \(4rd\) FLOPs and keeps \(rd + r\) numbers per head, whatever the position. The state \(S\) is also called a fast weight memory: a matrix that is written by outer products at run time, an idea Schmidhuber described in 1992. [Certain]

Algorithm 1: causal linear attention, decoding one token (one head)
  1. input: state \(S \in \R^{r \times d}\), normalizer \(\mathbf z \in \R^{r}\), new token’s \(\mathbf q, \mathbf k, \mathbf v\)
  2. \(\mathbf f_k \leftarrow \phi(\mathbf k)\), \(\;\mathbf f_q \leftarrow \phi(\mathbf q)\) // \(r\) numbers each
  3. \(S \leftarrow S + \mathbf f_k \mathbf v^\top\) // write: \(2rd\) FLOPs
  4. \(\mathbf z \leftarrow \mathbf z + \mathbf f_k\)
  5. \(\mathbf o \leftarrow (\mathbf f_q^\top S) / (\mathbf f_q^\top \mathbf z)\) // read: \(2rd\) FLOPs; nothing depends on the position
  6. return \(\mathbf o\), and keep \(S, \mathbf z\) for the next token // no KV cache

Figure 3 runs Algorithm 1 on four tokens, one line at a time, with the live numbers in the formulas. You can also switch on a constant forgetting gate \(g\), the simplest form of the gate (99.11) we meet later in the RFA section.

Gate:
    Figure 3. Causal linear attention with \(\phi = \operatorname{elu} + 1\), \(d = r = 2\), four tokens, computed in the browser. Each token takes four steps: features, write into \(S\), update \(\mathbf z\), read the output, which are lines 2 to 5 of the algorithm box and formulas (99.6) and (99.7). Bottom left: the attention weights that the state implies for the current token, \(\phi(\mathbf q_i)^\top\phi(\mathbf k_j)/\phi(\mathbf q_i)^\top\mathbf z_i\) (times \(g^{i-j}\) with a gate). Bottom right: the memory of a softmax KV cache (\(2id\) numbers after \(i\) tokens) against the fixed state (\(rd + r = 6\) numbers). The last step compares the full masked weight matrix with softmax of the raw dot products \(\mathbf q_i^\top\mathbf k_j\) (no \(1/\sqrt d\) scaling, to keep the numbers simple).
    How to read Figure 3

    The table lists the inputs; the current token is highlighted and its features \(\phi(\mathbf k)\), \(\phi(\mathbf q)\) appear when line 2 runs. During a write, the small matrix under \(S\) is the outer product being added. The output column fills one row per token. Check the worked example below against the screen: after token 2, \(S_2 = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}\), \(\mathbf z_2 = (3, 3)\) and \(\mathbf o_2 = (0.4444, 0.5556)\). In the last step, darker cells mean larger weights: row 4 of the linear matrix is spread out, softmax puts most of its weight on token 3. Now choose \(g = 0.5\): old tokens fade by half at each step, and the weights of token 4 become \((0.0737, 0.2220, 0.4133, 0.2910)\), a recency bias. The state is still 6 numbers.

    Worked example: the first two steps of Figure 3

    Token 1 has \(\mathbf q_1 = \mathbf k_1 = (1, 0)\), \(\mathbf v_1 = (1, 0)\). Then \(\phi(\mathbf k_1) = (1 + 1, e^0) = (2, 1)\), so \(S_1 = (2, 1)^\top (1, 0) = \begin{pmatrix} 2 & 0 \\ 1 & 0 \end{pmatrix}\) and \(\mathbf z_1 = (2, 1)\). The read: \(\phi(\mathbf q_1)^\top S_1 = (5, 0)\), \(\phi(\mathbf q_1)^\top \mathbf z_1 = 5\), so \(\mathbf o_1 = (1, 0) = \mathbf v_1\), as it must be with only one token.

    Token 2 has \(\mathbf q_2 = \mathbf k_2 = (0, 1)\), \(\mathbf v_2 = (0, 1)\), so \(\phi(\mathbf k_2) = (1, 2)\). Now \(S_2 = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}\), \(\mathbf z_2 = (3, 3)\). The read: numerator \((1, 2) S_2 = (4, 5)\), denominator \((1,2)\cdot(3,3) = 9\), so \(\mathbf o_2 = (0.4444, 0.5556)\). The weights on tokens 1 and 2 are \(4/9\) and \(5/9\). Softmax of the raw scores \((0, 1)\) gives \(0.2689\) and \(0.7311\): sharper.

    After all four tokens the last row of weights is \((0.2272, 0.3422, 0.3185, 0.1121)\) with elu + 1 and \((0.0536, 0.2401, 0.6527, 0.0536)\) with softmax. The largest weight is 0.3422 against 0.6527.

    Training: parallel, recurrent, and chunked

    For training we have all tokens at once. There are three ways to compute the same causal output:

    • Parallel (masked) form: build \(\phi(Q)\phi(K)^\top\), zero the upper triangle, normalize. Fast on GPUs for short sequences, but \(O(n^2)\) again.
    • Recurrent form: run (99.6) token by token. \(O(n)\) work, but sequential, which uses a GPU poorly. Storing every \(S_i\) for the backward pass would also cost \(n r d\) memory; the Linear Transformer paper derives a backward pass that recomputes the prefix sums instead. [Certain]
    • Chunked form: split the sequence into chunks of \(C\) tokens. Inside a chunk, use the masked form; between chunks, carry the state. This is how modern linear-attention kernels train (for example the “lightning attention” of MiniMax-01). [Likely]

    For chunk \(c\) with rows \(Q_c, K_c, V_c\) (after \(\phi\)) and the state \(S\), \(\mathbf z\) from all earlier chunks:

    \[ O_c = \frac{Q_c S + \operatorname{tril}(Q_c K_c^\top)\, V_c}{Q_c \mathbf z + \operatorname{tril}(Q_c K_c^\top)\,\mathbf 1}, \qquad S \leftarrow S + K_c^\top V_c, \qquad \mathbf z \leftarrow \mathbf z + K_c^\top \mathbf 1 \tag{99.8} \]

    Here \(\operatorname{tril}\) keeps the lower triangle (including the diagonal). The cost is about \(n C (r + d)\) for the in-chunk part and \(n r d\) for the state part: linear in \(n\), and made of matrix multiplications that tensor cores like.

    Copying softmax with random features

    The elu + 1 kernel is a different similarity from softmax. A pretrained Transformer uses softmax, so a natural wish is: find \(\phi\) with \(\phi(\mathbf q)^\top\phi(\mathbf k) \approx \exp(\mathbf q^\top \mathbf k/\sqrt d)\). Then we could approximate the same attention, not a new one. An exact finite \(\phi\) does not exist, but a random one can be right on average.

    First absorb the scaling: set \(\mathbf x = \mathbf q / d^{1/4}\) and \(\mathbf y = \mathbf k / d^{1/4}\), so \(\mathbf x^\top \mathbf y = \mathbf q^\top \mathbf k / \sqrt d\). Call \(\operatorname{SM}(\mathbf x, \mathbf y) = \exp(\mathbf x^\top \mathbf y)\) the softmax kernel. It is a Gaussian kernel times two terms that each depend on one vector only:

    \[ \exp(\mathbf x^\top \mathbf y) = \exp\!\left(\tfrac{\lVert \mathbf x\rVert^2}{2}\right)\, \exp\!\left(-\tfrac{\lVert \mathbf x - \mathbf y\rVert^2}{2}\right)\, \exp\!\left(\tfrac{\lVert \mathbf y\rVert^2}{2}\right) \tag{99.9} \]

    (Expand \(\lVert \mathbf x - \mathbf y\rVert^2 = \lVert\mathbf x\rVert^2 - 2\mathbf x^\top\mathbf y + \lVert\mathbf y\rVert^2\) to check.) The outer terms already factor. So it is enough to approximate the Gaussian kernel in the middle.

    Random Fourier features (Rahimi and Recht; RFA)

    Rahimi and Recht (2007) showed that a shift-invariant kernel is an expectation over random frequencies (by Bochner’s theorem). For the Gaussian kernel, draw \(\mathbf w_1, \dots, \mathbf w_m\) from the standard normal distribution \(\mathcal N(0, I_d)\) and use sines and cosines:

    \[ \phi_{\text{trig}}(\mathbf x) = \frac{e^{\lVert\mathbf x\rVert^2/2}}{\sqrt m}\big[\sin(\mathbf w_1^\top \mathbf x), \dots, \sin(\mathbf w_m^\top \mathbf x), \cos(\mathbf w_1^\top \mathbf x), \dots, \cos(\mathbf w_m^\top \mathbf x)\big] \tag{99.10} \]

    Because \(\sin a \sin b + \cos a \cos b = \cos(a - b)\) and \(\E_{\mathbf w}[\cos(\mathbf w^\top(\mathbf x - \mathbf y))] = e^{-\lVert \mathbf x - \mathbf y\rVert^2/2}\), we get \(\E[\phi_{\text{trig}}(\mathbf x)^\top\phi_{\text{trig}}(\mathbf y)] = \exp(\mathbf x^\top\mathbf y)\) exactly. [Certain] The feature size is \(r = 2m\).

    RFA builds on this. It assumes queries and keys are unit vectors (so the factor \(e^{\lVert\mathbf x\rVert^2/2}\) is the same for all of them and cancels in the normalization), uses a learned temperature, and adds an optional gate that lets the model forget: [Certain]

    \[ g_t = \sigma(\mathbf w_g^\top \mathbf x_t + b_g), \qquad S_t = g_t\, S_{t-1} + (1 - g_t)\,\phi(\mathbf k_t)\mathbf v_t^\top, \qquad \mathbf z_t = g_t\, \mathbf z_{t-1} + (1 - g_t)\,\phi(\mathbf k_t) \tag{99.11} \]

    Here \(\sigma\) is the sigmoid, \(\mathbf x_t\) is the token’s input representation, and \(0 \lt g_t \lt 1\). Old memories shrink by \(g_t\) at every step: a recency bias. This gate is the direct ancestor of the decay in RetNet and the selective gates in Mamba (session 101). RFA reports decoding about 2× faster than a Transformer baseline on machine translation without accuracy loss, and about 12× faster at length 2048 with under 10% of the memory in a speed benchmark. [Certain]

    The weakness of sin/cos features: their products can be negative. For a key that should get a tiny weight, the estimate can come out below zero, and the sum in the denominator of (99.2) can come close to zero or change sign. The Performer paper reports that this leads to unstable training, especially where the true kernel values are close to 0. [Certain]

    Positive random features (Performer, FAVOR+)

    Performer uses a different identity. For \(\mathbf w \sim \mathcal N(0, I_d)\), \(\E[e^{\mathbf w^\top \mathbf u}] = e^{\lVert\mathbf u\rVert^2/2}\). Take \(\mathbf u = \mathbf x + \mathbf y\) and divide by the right constants:

    \[ \exp(\mathbf x^\top \mathbf y) = \E_{\mathbf w}\!\left[e^{\mathbf w^\top \mathbf x - \lVert\mathbf x\rVert^2/2}\; e^{\mathbf w^\top \mathbf y - \lVert\mathbf y\rVert^2/2}\right], \qquad \phi_{+}(\mathbf x) = \frac{e^{-\lVert\mathbf x\rVert^2/2}}{\sqrt m}\big[e^{\mathbf w_1^\top\mathbf x}, \dots, e^{\mathbf w_m^\top\mathbf x}\big] \tag{99.12} \]
    Read the symbols
    \(\mathbf w_1, \dots, \mathbf w_m\)
    random directions, drawn once (and redrawn from time to time in training)
    \(m\)
    the number of random features, so \(r = m\)
    \(\phi_+(\mathbf x)\)
    every entry is an exponential, so it is strictly positive: no negative weights, no near-zero denominators from cancellation
    \(\E_{\mathbf w}\)
    average over the random draw: the estimate is unbiased, \(\E[\phi_+(\mathbf x)^\top\phi_+(\mathbf y)] = \exp(\mathbf x^\top\mathbf y)\)

    “Right on average” is easy to say. Figure 4 shows what it means in practice. It estimates one kernel value \(\operatorname{SM}(\mathbf x, \mathbf y) = \exp(\mathbf x^\top\mathbf y)\) in 2-D by adding random features one by one, with the positive features of (99.12) and the sin/cos features of (99.10) using the same random directions. After \(m\) features the two estimates are running means:

    \[ \widehat{\operatorname{SM}}_{+} = \frac1m \sum_{i=1}^{m} e^{\mathbf w_i^\top \mathbf x - \lVert\mathbf x\rVert^2/2}\, e^{\mathbf w_i^\top \mathbf y - \lVert\mathbf y\rVert^2/2}, \qquad \widehat{\operatorname{SM}}_{\text{trig}} = \frac1m \sum_{i=1}^{m} e^{(\lVert\mathbf x\rVert^2 + \lVert\mathbf y\rVert^2)/2} \cos\!\big(\mathbf w_i^\top(\mathbf x - \mathbf y)\big) \]

    The first is exactly \(\phi_+(\mathbf x)^\top\phi_+(\mathbf y)\), the second is \(\phi_{\text{trig}}(\mathbf x)^\top\phi_{\text{trig}}(\mathbf y)\) after \(\sin a \sin b + \cos a \cos b = \cos(a - b)\). Every term of the first sum is positive; a term of the second sum is negative whenever the cosine is.

    \(\mathbf x\) (query side)\(\mathbf y\) (key side)random directions \(\mathbf w_i\) (dot size \(\propto\) positive term)positive estimatesin/cos estimatenegative sin/cos term
    1. draw \(\mathbf w_i \sim \mathcal N(0, I_2)\) // the same \(\mathbf w\) for both estimators
    2. positive\(a_i = e^{\mathbf w_i^\top\mathbf x - \ell/2}\), \(\;b_i = e^{\mathbf w_i^\top\mathbf y - \ell/2}\), term \(a_i b_i \gt 0\) // (99.12)
    3. sin/costerm \(c_i = e^{\ell}\cos(\mathbf w_i^\top(\mathbf x - \mathbf y))\) // (99.10), can be negative
    4. running means: \(\widehat{\operatorname{SM}}_+ = \tfrac1m\sum a_i b_i\), \(\;\widehat{\operatorname{SM}}_{\text{trig}} = \tfrac1m\sum c_i\)
    Figure 4. A Monte Carlo estimate of one softmax-kernel value, computed in the browser with seeded random numbers. Left: the fixed vectors \(\mathbf x\) and \(\mathbf y\) and every random direction drawn so far; the size of each dot grows with its positive term \(a_i b_i\). Right: both running estimates divided by the true value (1 means exact) against the number of features \(m\), up to 128. The thin dashed curves are \(1 \pm\) the relative error of positive features from (99.13). The first three features run line by line; after that, one step adds one feature.
    How to read Figure 4

    Press Play. With the defaults (\(\theta = 60°\), \(\ell = 1\), first draw) the true value is \(e^{0.5} = 1.6487\). After 16 features the positive estimate is 1.3533 and the sin/cos estimate 1.6438; after 128 they are 2.1242 and 1.6046. The positive curve moves in jumps: a few directions that point between \(\mathbf x\) and \(\mathbf y\) give very large terms (big dots) and pull the mean up. That is the heavy tail behind (99.13). Now set \(\theta = 120°\) (a small kernel value, 0.6065): 39 of the 128 sin/cos terms are negative (red), and after 2 features the sin/cos estimate is already below zero (−0.1256), a negative “attention weight”. The positive estimate can never go below zero. Set \(\theta = 0°\) and \(\ell = 2\): sin/cos is exact (every cosine is 1), while the positive estimate is at 0.15 of the true value after 16 features and jumps to 0.87 at 64, carried by a few huge terms. This is the angle where the theory says positive features are worst (relative error 4.83 at \(m = 128\)).

    Two further tricks give the name FAVOR+ (Fast Attention Via positive Orthogonal Random features): [Certain]

    • Orthogonal features: inside each block of \(d\) directions, make the \(\mathbf w_i\) exactly orthogonal (Gram–Schmidt), then give each one a random length like a Gaussian vector would have. The estimate stays unbiased, and the variance gets smaller because the directions do not repeat each other.
    • Redrawing: sample new \(\mathbf w\) periodically during training. The paper found positive features with redrawing crucial to match a regular Transformer on PG-19, after transferring pretrained weights. [Certain]

    The paper also gives a hyperbolic version that uses both \(e^{\mathbf w^\top \mathbf x}\) and \(e^{-\mathbf w^\top \mathbf x}\) (so \(r = 2m\)); it has a slightly smaller error, shown dashed in Figure 5.

    Algorithm 2: FAVOR+ attention, bidirectional (one head)
    1. input: \(Q, K \in \R^{n \times d}\), \(V \in \R^{n \times d}\), number of features \(m\), a random seed
    2. draw \(W \in \R^{m \times d}\): orthogonal blocks of \(d\) rows, each row rescaled to the length of a Gaussian vector // redraw every few hundred steps in training
    3. \(X \leftarrow Q / d^{1/4}\), \(\;Y \leftarrow K / d^{1/4}\)
    4. \(\Phi_Q \leftarrow \exp(X W^\top - \tfrac12\lVert X\rVert^2_{\text{row}}) / \sqrt m\), \(\;\Phi_K\) the same with \(Y\) // \(n \times m\), all positive
    5. \(M \leftarrow \Phi_K^\top V\), \(\;\mathbf s \leftarrow \Phi_K^\top \mathbf 1\) // \(m \times d\) and \(m\): one pass over the keys
    6. return \((\Phi_Q M) \oslash (\Phi_Q \mathbf s)\) // row-wise division; cost \(4nmd + 2nmd\) for the features

    For causal use, replace steps 5 and 6 with the prefix-sum recurrence (99.6) or the chunked form (99.8). In practice the exponents are stabilized by subtracting a maximum, like in a safe softmax.

    How large is the error?

    Performer’s Lemma 2 gives the mean squared error (MSE) of one kernel estimate with \(m\) independent features. Write \(\operatorname{SM} = \exp(\mathbf x^\top\mathbf y)\): [Certain]

    \[ \operatorname{MSE}_{\text{trig}} = \frac{1}{2m}\, e^{\lVert\mathbf x + \mathbf y\rVert^2}\, \operatorname{SM}^{-2}\big(1 - e^{-\lVert\mathbf x - \mathbf y\rVert^2}\big)^2, \qquad \operatorname{MSE}_{+} = \frac{1}{m}\, e^{\lVert\mathbf x + \mathbf y\rVert^2}\, \operatorname{SM}^{2}\big(1 - e^{-\lVert\mathbf x + \mathbf y\rVert^2}\big) \tag{99.13} \]

    Divide by \(\operatorname{SM}^2\) to get the relative error. When \(\lVert\mathbf x\rVert^2 = \lVert\mathbf y\rVert^2 = \ell\) and the angle between them is \(\theta\), this becomes

    \[ \frac{\sqrt{\operatorname{MSE}_{\text{trig}}}}{\operatorname{SM}} = \sqrt{\tfrac{2}{m}}\,\big|\sinh\!\big(\ell(1 - \cos\theta)\big)\big|, \qquad \frac{\sqrt{\operatorname{MSE}_{+}}}{\operatorname{SM}} = \sqrt{\frac{e^{2\ell(1 + \cos\theta)} - 1}{m}} \]

    Read it carefully. Positive features are exact when \(\mathbf x = -\mathbf y\) (smallest kernel value), and sin/cos are exact when \(\mathbf x = \mathbf y\) (largest kernel value). So positive features are best for the many small weights, which is where sin/cos goes negative. But both errors grow exponentially with the norms, through \(\ell\). Large logits, which is exactly what sharp attention needs, are expensive to approximate. We verified both formulas against a Monte Carlo average of 40,000 draws (for example at \(\theta = \pi/2\), \(\ell = 1\), \(m = 16\): MSE 0.399 measured against 0.399 from the formula for positive features, and 0.170 against 0.173 for sin/cos).

    sin/cos (trigonometric)positivehyperbolic positive (dashed)
    Figure 5. Relative error \(\sqrt{\operatorname{MSE}}/\operatorname{SM}\) of one estimate of \(\exp(\mathbf x^\top\mathbf y)\) from formula (99.13), for vectors with equal squared norm \(\ell\) at angle \(\theta\). Small angles mean large kernel values (the key the query should attend to); large angles mean small values (keys it should ignore).
    How to read Figure 5

    The curves are exact formulas, not samples. Move \(\theta\) and read the two errors at the dashed line. Then raise \(\ell\) from 1 to 2 at \(\theta = 0°\): the positive-feature error jumps from 0.915 to 6.82 at \(m = 64\). Doubling \(m\) only divides the error by \(\sqrt 2\), while doubling \(\ell\) multiplies the exponent by 2. That is the cost of sharp attention.

    Figure 6 puts these features into a real attention row: one query, 32 keys, \(d = 16\), and the true softmax weights as horizontal marks.

    random-feature weightnegative estimatetrue softmax weight (mark)
    Figure 6. One attention row approximated with random features. The bars are the normalized estimates \(\phi(\mathbf x)^\top\phi(\mathbf y_j) / \sum_l \phi(\mathbf x)^\top\phi(\mathbf y_l)\); the marks are the exact softmax weights. The logit scale multiplies the query, so larger values make the true softmax row sharper. The error is the total variation distance, \(\tfrac12\sum_j |\hat a_j - a_j|\), which is 0 for a perfect copy and 1 for rows with no overlap. All random numbers are seeded.
    How to read Figure 6

    Start with “positive” at scale 1 and \(m = 64\), and press “Redraw” a few times: the bars move, the marks do not. The readout gives this draw’s distance and the mean over 20 seeded draws (0.451 here). Raise \(m\) to 256 and 1024: the mean falls only to 0.387 and 0.360, much slower than \(1/\sqrt m\), because a few very large features dominate each estimate (the heavy tail behind (99.13)). Orthogonal features give 0.468 at \(m = 64\): in this small case they do not help. Now raise the scale to 3: the true row gets a clear peak (largest weight 0.617) and the mean distance grows to 0.799. Switch to sin/cos at scale 3: 25 of 32 estimates are negative (red bars) and the mean distance is 2.69, which is only possible with negative “weights”.

    Why quality drops: no sharp, peaked attention

    Linear attention is cheaper, but models trained with it have usually been weaker at the same size, and the gap is largest on tasks that need exact lookup in the context. Four reasons, each one measurable:

    1. The attention matrix has rank at most \(r\)

    In linear attention the implied \(n \times n\) weight matrix (before row normalization) is \(\phi(Q)\phi(K)^\top\), a product of \(n \times r\) and \(r \times n\) matrices. Its rank is at most \(r\). Softmax applies \(\exp\) to each entry, which can make the matrix full rank: an identity-like pattern (“each token looks at exactly one other token”) is easy for softmax and impossible for a rank-\(r\) matrix when \(n \gt r\). This is the same limit as low-rank attention in session 98, now reached through the kernel.

    2. The weights are flat

    Softmax is spiky: a logit gap of 5 gives a ratio of \(e^5 \approx 148\) between two weights. With elu + 1, the kernel grows only like a product of linear terms, so similar and dissimilar keys get weights of the same order. In Figure 3 the largest weight of token 4 was 0.342 against 0.653 for softmax. Zhang et al. (Hedgehog, 2024) name two properties that earlier linear attentions lack: low-entropy (“spiky”) weights and dot-product monotonicity (a larger \(\mathbf q^\top\mathbf k\) should always give a larger weight). [Certain] Random features approximate softmax on average, but formula (99.13) says the error explodes for exactly the large logits that make attention spiky.

    3. A fixed-size state must forget

    The state \(S\) has \(rd\) numbers. Every token adds a rank-1 term. After more than about \(r\) tokens, the key features cannot all be orthogonal any more, so reading with one key also returns pieces of other values. This is interference, the classic limit of an associative memory. A KV cache, in contrast, grows with \(n\) and keeps everything exactly.

    4. Exact recall suffers

    Arora et al. (Zoology, 2023) studied this with multi-query associative recall (MQAR): the context holds key-value pairs, and later the model must return the value for a key it saw. They found that 82% of the quality gap between gated-convolution models and attention on the Pile is explained by this recall ability, and that a 70M-parameter attention model beats a 1.4B-parameter gated-convolution model on associative recall. [Certain] Their follow-up (Based, 2024) shows a recall–throughput trade-off: models with a smaller recurrent state are faster but recall less. [Certain]

    Figure 7 is a tiny version of this experiment without any training. We store \(n\) random key-value pairs, query with the exact keys, and check whether the output is closest to the right value.

    softmaxlinear \(\phi(\mathbf x) = \mathbf x\), unit keysFAVOR+ (\(m = 2d\))linear \(\operatorname{elu} + 1\)
    Figure 7. Associative recall with no learning. Keys and values are random Gaussian vectors of size \(d\); query \(i\) equals key \(i\). A pair counts as recalled if the output has the largest cosine similarity with value \(i\) among all \(n\) values. Accuracy is averaged over 3 seeded trials. “φ(x) = x, unit keys” is the plain fast-weight memory \(S = \sum_j \mathbf k_j \mathbf v_j^\top\) without normalization.
    How to read Figure 7

    Move \(n\) from 4 to 256. Softmax keeps all pairs and stays near perfect (0.987 at \(n = 256\) with \(d = 32\)). The plain fast-weight memory is perfect up to \(n = 16\) and then falls (0.833 at 64, 0.150 at 256) once \(n\) passes its \(d \times d\) capacity; the dashed line marks \(n = d\). FAVOR+ is never perfect, because its weights are not sharp enough, and elu + 1 fails already at \(n = 16\) (0.083): its weights are almost uniform. The readout also gives the mean weight each method puts on the correct pair: compare it with the uniform value \(1/n\). Switch \(d\): a bigger state moves the drop to larger \(n\), which is the recall–throughput trade-off in one picture.

    Fixes: better kernels, decay, and hybrids

    Work after 2021 kept the linear cost and attacked the four problems above:

    • Sharper kernels. PolySketchFormer uses polynomial kernels \((\mathbf q^\top\mathbf k)^p\), which are non-negative for even \(p\) and peak faster than elu + 1, and uses sketching to keep the feature size manageable. [Certain] Based uses a second-order Taylor approximation, \(\phi(\mathbf q)^\top\phi(\mathbf k) = 1 + \mathbf q^\top\mathbf k + (\mathbf q^\top\mathbf k)^2/2\), on queries and keys projected to 16 dimensions, so \(r = 1 + 16 + 256 = 273\) if all products are kept. [Certain for the kernel; the exact feature count depends on the implementation, Likely]
    • Learned feature maps. Hedgehog trains a small MLP \(\phi\) so that linear attention copies the softmax weights of a given model. It reports recovering over 99% of Transformer quality and converting pretrained models such as GPT-2 and Llama-2 7B. [Certain]
    • Decay and gates. RFA’s gate (99.11), RetNet’s fixed decay \(S_t = \gamma S_{t-1} + \mathbf k_t\mathbf v_t^\top\), and the input-dependent gates of Mamba and gated linear attention let the model forget on purpose, so the state is spent on recent or important tokens. [Certain] These are the topic of session 101.
    • Local exact attention. Based adds sliding-window softmax attention (windows of 64 to 128 tokens) to the linear part; the window handles sharp local patterns. Based reports 24× higher generation throughput than FlashAttention-2 at 1.3B parameters. [Certain]
    • Hybrids. MiniMax-01 has 80 layers; after every 7 lightning-attention (linear) layers comes 1 softmax layer. It is a mixture-of-experts model with 456B total and 45.9B active parameters, trained with up to 1M tokens of context and extrapolating to 4M at inference. [Certain]

    The common pattern: keep most layers linear for cheap long context, and keep a few exact softmax layers (or a window) for the sharp lookups.

    Runnable code

    The script below checks that the three causal forms (parallel, recurrent, chunked) give the same output, and measures how well random features copy a softmax attention matrix at three logit scales. It is deterministic (fixed seeds, float64). It runs in about 3 seconds on a laptop CPU.

    import torch
    torch.manual_seed(0)
    torch.set_default_dtype(torch.float64)
    
    def phi_elu(x):                                   # Linear Transformer feature map (99.5)
        return torch.nn.functional.elu(x) + 1
    
    def causal_parallel(fq, fk, v):                   # O(T^2): mask the T x T kernel matrix
        A = torch.tril(fq @ fk.T)
        return (A @ v) / A.sum(1, keepdim=True)
    
    def causal_recurrent(fq, fk, v):                  # O(T): an RNN with state S (r x d_v) and z (r), (99.6)-(99.7)
        S = torch.zeros(fk.shape[1], v.shape[1]); z = torch.zeros(fk.shape[1]); out = []
        for i in range(len(v)):
            S += torch.outer(fk[i], v[i]); z += fk[i]
            out.append((fq[i] @ S) / (fq[i] @ z))
        return torch.stack(out)
    
    def causal_chunked(fq, fk, v, C=64):              # training form (99.8): quadratic inside a chunk, state between
        S = torch.zeros(fk.shape[1], v.shape[1]); z = torch.zeros(fk.shape[1]); out = []
        for s in range(0, len(v), C):
            q, k, vv = fq[s:s+C], fk[s:s+C], v[s:s+C]
            A = torch.tril(q @ k.T)
            out.append((q @ S + A @ vv) / (q @ z + A.sum(1))[:, None])
            S = S + k.T @ vv; z = z + k.sum(0)
        return torch.cat(out)
    
    T, d = 512, 64
    q, k, v = torch.randn(T, d), torch.randn(T, d), torch.randn(T, d)
    fq, fk = phi_elu(q), phi_elu(k)
    o1, o2, o3 = causal_parallel(fq, fk, v), causal_recurrent(fq, fk, v), causal_chunked(fq, fk, v)
    print(f"recurrent vs parallel {(o1-o2).abs().max():.1e}   chunked vs parallel {(o1-o3).abs().max():.1e}")
    
    def gaussian_W(m, d, orthogonal):
        if not orthogonal: return torch.randn(m, d)
        blocks = [torch.linalg.qr(torch.randn(d, d))[0].T for _ in range((m + d - 1) // d)]
        W = torch.cat(blocks)[:m]                     # rows orthogonal inside each block of d
        return W * torch.randn(m, d).norm(dim=1, keepdim=True)  # row norms like Gaussian rows
    
    def features(x, W, kind):                         # x already scaled by d**-0.25
        m, sq = W.shape[0], (x * x).sum(-1, keepdim=True) / 2
        if kind == "trig":                            # random Fourier features (99.10)
            return torch.exp(sq) * torch.cat([torch.sin(x @ W.T), torch.cos(x @ W.T)], -1) / m**0.5
        return torch.exp(x @ W.T - sq) / m**0.5       # FAVOR+ positive features (99.11)
    
    def favor_attn(q, k, v, W, kind):                 # bidirectional, linear time: phi(Q) (phi(K)^T V)
        s = q.shape[1] ** -0.25
        fq, fk = features(q * s, W, kind), features(k * s, W, kind)
        out = (fq @ (fk.T @ v)) / (fq @ fk.sum(0))[:, None]
        A_hat = fq @ fk.T; A_hat = A_hat / A_hat.sum(1, keepdim=True)   # T x T, built only to measure
        return out, A_hat
    
    for scale in [0.25, 0.5, 1.0]:                    # larger scale = larger logits = sharper softmax
        qs, ks = q * scale, k * scale
        A = torch.softmax(qs @ ks.T / d**0.5, -1)
        print(f"scale {scale}: logit std {(qs @ ks.T / d**0.5).std():.2f}, mean largest weight {A.max(1).values.mean():.3f}")
        for m in [64, 256, 1024]:
            row = []
            for kind, orth in [("trig", False), ("pos", False), ("pos", True)]:
                torch.manual_seed(1); tv = 0.0
                for _ in range(5):                    # average over 5 draws of the random features
                    out, A_hat = favor_attn(qs, ks, v, gaussian_W(m, d, orth), kind)
                    tv += 0.5 * (A_hat - A).abs().sum(1).mean().item() / 5
                row.append(tv)
            print(f"   m={m:5d}  TV distance  trig {row[0]:7.3f}   positive {row[1]:6.3f}   positive+orthogonal {row[2]:6.3f}")

    Output with PyTorch 2.8 (CPU):

    recurrent vs parallel 4.4e-16   chunked vs parallel 2.8e-16
    scale 0.25: logit std 0.06, mean largest weight 0.002
       m=   64  TV distance  trig   0.033   positive  0.050   positive+orthogonal  0.042
       m=  256  TV distance  trig   0.016   positive  0.026   positive+orthogonal  0.022
       m= 1024  TV distance  trig   0.008   positive  0.013   positive+orthogonal  0.011
    scale 0.5: logit std 0.25, mean largest weight 0.004
       m=   64  TV distance  trig   0.264   positive  0.190   positive+orthogonal  0.175
       m=  256  TV distance  trig   0.124   positive  0.120   positive+orthogonal  0.109
       m= 1024  TV distance  trig   0.061   positive  0.070   positive+orthogonal  0.066
    scale 1.0: logit std 1.01, mean largest weight 0.027
       m=   64  TV distance  trig  38.961   positive  0.640   positive+orthogonal  0.650
       m=  256  TV distance  trig  30.954   positive  0.572   positive+orthogonal  0.572
       m= 1024  TV distance  trig  33.293   positive  0.495   positive+orthogonal  0.507

    Read the output. The three causal forms agree to rounding error (about \(10^{-16}\)). For nearly flat attention (scale 0.25) all features are good, and sin/cos is even the best. At scale 0.5, positive features win and orthogonality helps a little. At scale 1.0 (logits with standard deviation 1, still a soft row with a largest weight of only 0.027 over 512 keys), sin/cos breaks completely: a distance of 39 is only possible because the normalizer comes close to zero. Positive features stay finite but remain far from softmax even with 1024 features. Larger logits make all of this worse, as (99.13) predicts. [Certain for these runs]

    Where this is used

    SettingWhich ideaWhy it fits
    Hybrid long-context LLMs (MiniMax-01)Linear (lightning) attention in 7 of every 8 layers, softmax in the restLinear cost and small state for most layers; the softmax layers keep exact recall [Certain]
    Fast decoding with a fixed memoryRNN form (99.6) with decay or gates (RFA-Gate, RetNet, gated linear attention)Each token costs the same at any position; no KV cache to grow or page [Certain]
    Recall-aware small LMs (Based)Taylor feature map plus a short sliding windowThe state size sets the speed-recall trade-off directly [Certain]
    Converting a pretrained Transformer (Hedgehog, Performer weight transfer)Learned or random feature maps that copy softmaxReuse trained weights, then fine-tune briefly [Certain]
    Long biological sequences (Performer on proteins)FAVOR+, bidirectionalVery long inputs, an encoder, no causal mask [Certain]
    Long-document and high-resolution image encodersBidirectional linear attention (99.3)One pass builds \(\phi(K)^\top V\); all queries read it in parallel [Likely]
    Video classification and action recognitionLinear attention over many frame-patch tokensToken count grows with frames; the label needs a global summary, not exact lookup [Likely]
    Streaming video: key-moment detection and segmentationCausal RNN form with decayOne state per stream, constant cost per new frame, recent frames weigh more [Speculation]
    Video retrieval, fingerprinting, Video-RAGUsually not linear attention aloneThese need exact matching of specific moments; keep softmax or a hybrid, or store the clips in an index [Likely]

    Common mistakes

    • Thinking linear attention is always faster. The ratio is \(n(r+d)/(2rd)\). For \(n\) below the head size, or with a large feature size \(r\) (random features often use \(r \gg d\)), the quadratic order with FlashAttention can be faster in wall-clock time.
    • Forgetting the normalizer. Dropping \(\phi(\mathbf q)^\top\mathbf z\) turns the output into an unnormalized sum whose size grows with \(n\). Some later models remove it on purpose and add a normalization layer instead; you must do one or the other.
    • Using a feature map that can go negative without care. With sin/cos or plain \(\phi(x) = x\), the denominator can be near zero or negative. Use positive features, or drop the normalizer and normalize the output.
    • Applying the causal mask after the reordering. Once you compute \(\phi(K)^\top V\) over all tokens, future tokens are already mixed in. Causal models need prefix sums (99.6) or the chunked form (99.8).
    • Forgetting the \(d^{1/4}\) scaling when approximating softmax. The kernel is \(\exp(\mathbf q^\top\mathbf k/\sqrt d)\), so both \(\mathbf q\) and \(\mathbf k\) are divided by \(d^{1/4}\) before the features.
    • Ignoring overflow. \(e^{\mathbf w^\top\mathbf x}\) and \(e^{\lVert\mathbf x\rVert^2/2}\) overflow in FP16 for large inputs. Subtract a per-row maximum in the exponent; it cancels in the normalization.
    • Expecting a long context to mean good recall. A linear-attention model can read a million tokens at fixed cost, but its state holds only \(rd\) numbers per head. Test needle-in-a-haystack and associative recall, not just perplexity.

    Interview questions

    How does linear attention reach \(O(n)\) cost?basic
    Replace \(\exp(\mathbf q^\top\mathbf k)\) with \(\phi(\mathbf q)^\top\phi(\mathbf k)\). Then the output is \(\phi(Q)(\phi(K)^\top V)\) divided by \(\phi(Q)(\phi(K)^\top\mathbf 1)\). Computing \(\phi(K)^\top V\) first (an \(r \times d\) matrix) costs \(2nrd\), and multiplying by \(\phi(Q)\) costs another \(2nrd\): \(4nrd\) in total, against \(2n^2(r+d)\) for the other order. No \(n \times n\) matrix is built. It works because matrix multiplication is associative.
    Why can’t you apply the same trick directly to softmax?basic
    Because \(\exp(\mathbf q^\top\mathbf k)\) does not factor into a finite dot product of a function of \(\mathbf q\) and a function of \(\mathbf k\). Its Taylor series has terms of every degree, so an exact feature map is infinite-dimensional. Also, the softmax normalizer is a sum of exponentials per query, which ties every query to every key. You can only approximate it, with random features (Performer, RFA) or truncated series (Based).
    Explain “Transformers are RNNs”.core
    With a factorized kernel and a causal mask, the output of token \(i\) needs only the prefix sums \(S_i = \sum_{j \le i}\phi(\mathbf k_j)\mathbf v_j^\top\) and \(\mathbf z_i = \sum_{j \le i}\phi(\mathbf k_j)\). These update as \(S_i = S_{i-1} + \phi(\mathbf k_i)\mathbf v_i^\top\), which is an RNN with a matrix-valued hidden state. Decoding costs \(O(rd)\) per token and \(O(rd)\) memory per head, independent of the position, instead of a KV cache that grows with \(n\).
    How do you train causal linear attention efficiently on a GPU?core
    The pure recurrence is sequential and slow on GPUs; the masked parallel form is \(O(n^2)\). The standard answer is the chunked form: split into chunks of size \(C\), compute attention inside each chunk with a masked \(C \times C\) matmul, and pass the state \(S, \mathbf z\) between chunks. The cost is linear in \(n\), the work is mostly dense matmuls, and you only store one state per chunk for the backward pass.
    What is FAVOR+? Explain each part of the name.core
    Fast Attention Via positive Orthogonal Random features. “Fast attention”: the linear order of (99.3). “Random features”: \(\phi(\mathbf x) = e^{-\lVert\mathbf x\rVert^2/2}[e^{\mathbf w_i^\top\mathbf x}]/\sqrt m\) with Gaussian \(\mathbf w_i\), which gives an unbiased estimate of \(\exp(\mathbf x^\top\mathbf y)\). “Positive”: every feature is positive, so the weights are never negative and the normalizer is stable. “Orthogonal”: the \(\mathbf w_i\) are made orthogonal within blocks, which keeps the estimate unbiased and lowers its variance.
    Why are positive random features better than sin/cos for attention?core
    Attention rows contain many small kernel values (keys to ignore). For sin/cos the relative error is largest exactly there: by (99.13) it is \(\sqrt{2/m}\,|\sinh(\ell(1-\cos\theta))|\), which grows for large angles, and the estimate can go negative, which makes the normalizer unstable. The positive estimator’s relative error is \(\sqrt{(e^{2\ell(1+\cos\theta)}-1)/m}\), which goes to 0 for the smallest kernel values. Sin/cos is better only for the largest values. Both errors grow exponentially with the norms.
    Why do linear-attention models do worse on recall tasks?core
    Three linked reasons. (1) The state has \(rd\) numbers per head no matter how many tokens were written, so after about \(r\) key-value pairs the keys interfere and a read returns a mixture. (2) The implied attention matrix \(\phi(Q)\phi(K)^\top\) has rank at most \(r\), so it cannot represent “each query looks at one specific key” for \(n \gt r\). (3) Simple kernels like elu + 1 are flat, so even the right key gets a small share of the weight. Zoology found that 82% of the gap between gated convolutions and attention on the Pile is explained by associative recall.
    Linear attention has \(O(n)\) cost. Why do we still use FlashAttention with softmax in most LLMs?core
    FlashAttention makes exact softmax attention fast and memory-light (no \(n \times n\) matrix in HBM), so at common lengths (a few thousand to tens of thousands of tokens) the quadratic FLOPs are affordable and quality is better. Linear attention also often uses \(r \gg d\) or extra feature computation, so the break-even length can be large. Its benefits are real mainly for very long contexts or decode memory, which is why recent use is in hybrids rather than pure models.
    What does the gate in RFA add, and how does it relate to later models?advanced
    RFA-Gate updates \(S_t = g_t S_{t-1} + (1-g_t)\phi(\mathbf k_t)\mathbf v_t^\top\) with a learned sigmoid gate \(g_t\) that depends on the input. Old memories decay, giving a recency bias and freeing state capacity. RetNet uses a fixed decay \(\gamma\) per head; Mamba, GLA and similar models make the decay input-dependent and per channel. All of these are linear attention with forgetting, which is why linear attention is the bridge to state space models.
    A hybrid model has 1 softmax layer in every 8. Estimate its decode memory against a pure softmax model.advanced
    Only the softmax layers keep a KV cache, so the cache is 1/8 of the pure model’s at the same length. Each linear layer keeps a fixed state of \(rd + r\) numbers per head: with 8 heads and \(r = d = 128\) that is \(8 \times 16{,}512 = 132{,}096\) numbers per layer, at any length. One softmax layer with 8 KV heads of size 128 caches \(2 \times 8 \times 128 \times n = 2048n\) numbers, which passes the linear state at about 65 tokens. So at long context the softmax layers dominate and the total saving approaches 8×. To go further you must shrink those layers too (GQA, MLA, a sliding window).
    Is \(\phi(\mathbf q)^\top\phi(\mathbf k)\) with elu + 1 an approximation of softmax?basic
    No. It is a different, valid similarity function chosen because it is positive and cheap. The model is trained with it from the start (or fine-tuned into it). Only random-feature methods (Performer, RFA) and learned mimics (Hedgehog) aim to approximate the softmax kernel itself.

    Exercises

    1. For \(n = 32{,}768\), \(r = d = 128\), compute the bidirectional FLOPs per head of both orders in (99.4) and their ratio.
    2. Find the break-even length for \(r = 256\) random features and \(d = 64\).
    3. A model has 32 layers and 8 KV heads of size 128. Compare its BF16 KV cache at 32,768 and 131,072 tokens with the FP32 linear-attention state (\(r = d = 128\), state \(rd + r\) per head) for the same layer and head counts.
    4. Continue Figure 3 by hand: compute \(S_3\), \(\mathbf z_3\) and \(\mathbf o_3\) for \(\mathbf q_3 = (1, 1)\), \(\mathbf k_3 = (-1, 1)\), \(\mathbf v_3 = (1, 1)\).
    5. Using (99.13), compute the relative error of positive features and of sin/cos at \(\ell = 1\), \(m = 64\), for \(\theta = 90°\) and \(\theta = 120°\). Which is better at each angle?
    6. Show that \(\E_{\mathbf w}[e^{\mathbf w^\top\mathbf x - \lVert\mathbf x\rVert^2/2} e^{\mathbf w^\top\mathbf y - \lVert\mathbf y\rVert^2/2}] = e^{\mathbf x^\top\mathbf y}\) for \(\mathbf w \sim \mathcal N(0, I)\).
    7. In Figure 7 with \(d = 32\), read the recall of FAVOR+ and of softmax at \(n = 16\) and \(n = 256\). Explain the change in one sentence.
    Answerscheck
    1. Quadratic: \(2 \times 32768^2 \times 256 = 5.50 \times 10^{11}\). Linear: \(4 \times 32768 \times 128^2 = 2.15 \times 10^9\). Ratio \(n/d = 256\). 2. \(n = 2rd/(r+d) = 2 \cdot 256 \cdot 64 / 320 = 102.4\); above about 103 tokens the linear order uses fewer FLOPs. 3. KV cache: \(2 \times 32 \times 8 \times 128 \times n \times 2\) bytes, which is 4 GiB at 32,768 and 16 GiB at 131,072 tokens. State: \(32 \times 8 \times (128^2 + 128) \times 4\) bytes \(= 16{,}908{,}288\) bytes, about 16.1 MiB, at any length. 4. \(\phi(\mathbf k_3) = (e^{-1}, 2) = (0.3679, 2)\), so \(S_3 = S_2 + (0.3679, 2)^\top(1, 1) = \begin{pmatrix} 2.3679 & 1.3679 \\ 3 & 4\end{pmatrix}\), \(\mathbf z_3 = (3.3679, 5)\). \(\phi(\mathbf q_3) = (2, 2)\): numerator \((10.7358, 10.7358)\), denominator \(16.7358\), so \(\mathbf o_3 = (0.6415, 0.6415)\). 5. At \(90°\): positive \(\sqrt{(e^2 - 1)/64} = 0.316\), sin/cos \(\sqrt{2/64}\sinh 1 = 0.208\): sin/cos is better. At \(120°\): positive \(\sqrt{(e^1 - 1)/64} = 0.164\), sin/cos \(\sqrt{2/64}\sinh 1.5 = 0.376\): positive is better. 6. \(\E[e^{\mathbf w^\top(\mathbf x+\mathbf y)}] = e^{\lVert\mathbf x+\mathbf y\rVert^2/2}\) (the moment generating function of a Gaussian). Multiply by \(e^{-\lVert\mathbf x\rVert^2/2 - \lVert\mathbf y\rVert^2/2}\): the exponent becomes \((\lVert\mathbf x+\mathbf y\rVert^2 - \lVert\mathbf x\rVert^2 - \lVert\mathbf y\rVert^2)/2 = \mathbf x^\top\mathbf y\). 7. At \(n = 16\): FAVOR+ 0.708, softmax 1.000. At \(n = 256\): FAVOR+ 0.138, softmax 0.987. Softmax keeps every pair, while FAVOR+ must squeeze 256 pairs into a fixed state of \(m \times d = 64 \times 32\) numbers, so the keys interfere and its flat weights (0.055 on the right pair, against 0.429 for softmax) blur the read.

    Key takeaways

    • Attention is a kernel smoother (99.1). Softmax uses \(\exp(\mathbf q^\top\mathbf k/\sqrt d)\), which has no finite feature map, so it needs all \(n^2\) pairs.
    • With \(\kappa = \phi(\mathbf q)^\top\phi(\mathbf k)\), associativity gives \(\phi(Q)(\phi(K)^\top V)\): \(4nrd\) FLOPs instead of \(2n^2(r+d)\), and an \(r \times d\) state instead of an \(n \times n\) matrix (99.3, 99.4).
    • Causal linear attention is an RNN: \(S_i = S_{i-1} + \phi(\mathbf k_i)\mathbf v_i^\top\) (99.6). Decoding has constant cost and memory per token; training uses the chunked form (99.8).
    • Performer (positive orthogonal random features) and RFA (sin/cos features, plus a gate) estimate the softmax kernel without bias; positive features avoid negative weights, but every estimator’s error grows exponentially with the logit size (99.13).
    • Quality drops because the implied matrix has rank at most \(r\), the weights are flat, the fixed state interferes, and exact recall fails. Sharper kernels, decay and gates, sliding windows and hybrids with a few softmax layers are the fixes in use.

    Key formulas

    \[ O = \frac{\phi(Q)\big(\phi(K)^\top V\big)}{\phi(Q)\big(\phi(K)^\top\mathbf 1\big)}, \qquad \frac{2n^2(r+d)}{4nrd} = \frac{n(r+d)}{2rd} \]
    \[ S_i = S_{i-1} + \phi(\mathbf k_i)\mathbf v_i^\top, \qquad \mathbf z_i = \mathbf z_{i-1} + \phi(\mathbf k_i), \qquad \mathbf o_i^\top = \frac{\phi(\mathbf q_i)^\top S_i}{\phi(\mathbf q_i)^\top\mathbf z_i} \]
    \[ \phi_+(\mathbf x) = \frac{e^{-\lVert\mathbf x\rVert^2/2}}{\sqrt m}\big[e^{\mathbf w_i^\top\mathbf x}\big]_{i=1}^{m}, \qquad \E\big[\phi_+(\mathbf x)^\top\phi_+(\mathbf y)\big] = e^{\mathbf x^\top\mathbf y} \]

    References for this session

    1. Katharopoulos et al. (2020). Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
    2. Choromanski et al. (2020). Rethinking Attention with Performers
    3. Peng et al. (2021). Random Feature Attention
    4. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
    5. Katharopoulos et al. (2020). Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
    6. Choromanski et al. (2020). Rethinking Attention with Performers
    7. Peng et al. (2021). Random Feature Attention
    8. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
    9. Wang et al. (2020). Linformer: Self-Attention with Linear Complexity
    10. Dao et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
    11. Sun et al. (2023). Retentive Network: A Successor to Transformer for Large Language Models
    12. Gu & Dao (2023). Mamba: Linear-Time Sequence Modeling with Selective State Spaces
    13. Zhang, Bhatia, Kumbong, Ré (2024). The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicry
    14. Arora et al. (2024). Simple linear attention language models balance the recall-throughput tradeoff
    15. Kacham, Mirrokni, Zhong (2023). PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels
    16. MiniMax et al. (2025). MiniMax-01: Scaling Foundation Models with Lightning Attention
    17. Rahimi & Recht (2007). Random Features for Large-Scale Kernel Machines
    18. Arora et al. (2023). Zoology: Measuring and Improving Recall in Efficient Language Models