LLM & VLM courseBlog
102Track 5: LLM inference and serving · session 25 of 65

Linformer, Performer and GQA against full attention

In this lab you build full attention, GQA, Linformer and Performer behind one interface in one small GPT, and test them the way an engineer would. You check that no layer reads the future, time one layer from 512 to 16k tokens with and without a fused kernel, time a decode step against a KV cache, and compare validation loss, a copy task and associative recall. For every result you find the formula that explains it.

Time: 4 to 5 hours (mostly hands-on; about 1.5 hours of compute on a laptop)Level: Intermediate · hands-on labBefore this: Sessions 97 to 99 (efficient attention 1, 2 and 3), PyTorch

What you will learn

  • How to put full attention, GQA, Linformer and Performer behind one module and train them under identical conditions
  • Why the original Linformer leaks the future in a causal model, how to detect it with a leak test, and a simple causal block variant
  • How FAVOR+ random features estimate softmax, and why the error grows with sharp attention (the variance formula)
  • How to benchmark one attention layer correctly (warm-up, synchronization, median, traced peak memory) and why a fused exact kernel changes the conclusion
  • Why GQA does not speed up training but cuts decode time with the KV cache it removes, and why copying the cache (repeat_interleave) undoes that
  • Why validation loss and a fixed-offset copy task cannot rank attention methods, and how associative recall exposes methods that summarize the past

Why this matters

Full attention compares every token with every earlier token. For a sequence of \(n\) tokens, that is about \(n^2/2\) dot products per head and layer. In the last sessions you met three ways to make attention cheaper: GQA shares keys and values between query heads, Linformer compresses the sequence of keys and values to a short fixed length, and Performer replaces the softmax with random features so that attention becomes a running sum. Each paper reports that it is faster and almost as good. In this lab you check those claims yourself, on one laptop GPU, with code you can read in one sitting.

You will build the three, plus full attention, behind one interface in one small GPT. Then you measure four things, and for each result you find the formula that predicts it:

  1. Correctness: does the layer see the future? (One of the three does, if you copy the paper.)
  2. Speed and memory of one layer for sequence lengths 512 to 16,384, against a naive full attention and against PyTorch’s fused kernel.
  3. Decoding: the cost of generating one token with a KV cache, where GQA was designed to help.
  4. Quality: validation loss on Tiny Shakespeare, a copy task, and an associative recall task that needs exact recall of one earlier token found by its content.

The short version of what you will find: the approximations save memory against a naive layer, but a fused exact kernel removes most of that advantage; GQA does little for training speed but cuts decode time with the cache it removes (2.6× faster for a 4× smaller cache in our run), unless the kernel copies the cache; and the methods that summarize the past do fine on loss, and even on a simple copy task, but fail when a token must be found by its content. The numbers below are from our runs, and every one of them comes from code on this page.

The ideas come from session 97 (MQA, GQA, MLA), session 98 (Linformer) and session 99 (kernel attention, Performer). Session 101 showed that models with a fixed-size state are weak at copying; here you measure the same effect inside attention itself.

Setup

Everything ran on one Apple M5 Pro laptop (48 GB of unified memory) with PyTorch 2.8.0 and the mps backend (Apple GPU through Metal). You do not need the same machine: the code runs on CUDA if you replace 'mps' by 'cuda' and torch.mps.synchronize() by torch.cuda.synchronize(). Absolute times will differ; the shapes of the curves are what the formulas predict, and those carry over.

pip install torch
curl -O https://raw.githubusercontent.com/karpathy/char-rnn/master/data/tinyshakespeare/input.txt

Tiny Shakespeare is 1,115,394 characters with 65 distinct characters. We use characters as tokens (vocabulary 65), the first 90% for training and the last 10% for validation. The model is small on purpose so that each training run takes a few minutes: embedding size \(d = 128\), 4 layers, 4 heads of size \(d_h = 32\), context 256, batch 32, 3,000 steps of AdamW. All runs use the same seed and the same batches, so the only difference between two runs is the attention layer.

The lab has eight files: lab.py (the model, Step 1), check.py (Step 2), bench.py and bench_cpu.py (Step 4), decode.py (Step 5), train.py (Step 6), copytask.py and recall.py (Step 7). Put them in one folder with input.txt.

Step 1: four attention layers behind one interface

All four layers take the same input \(X \in \R^{n \times d}\) (one row per token) and return an output of the same shape. Inside, each computes queries, keys and values for \(h\) heads, mixes the values, and projects back. They differ only in which keys a query compares with, and how.

Full attention: the baseline

For one head, with \(Q, K, V \in \R^{n \times d_h}\):

\[ O = \softmax\!\Big( \frac{Q K^{\top}}{\sqrt{d_h}} + M \Big)\, V, \qquad M_{ts} = \begin{cases} 0 & s \le t \\ -\infty & s \gt t \end{cases} \tag{102.1} \]
Read the symbols
\(Q, K, V\)
queries, keys and values of one head: one row of size \(d_h\) per token
\(d_h\)
the head size (32 in our GPT, 64 in the benchmark, 128 in Llama 3 8B)
\(M\)
the causal mask: query \(t\) may look at keys \(s \le t\) only
\(O\)
the output of the head, \(n \times d_h\)

The score matrix \(QK^{\top}\) has \(n \times n\) entries. Counting multiply-adds for the two matrix products of all \(h\) heads, and the number of bytes the score matrices take if they are stored:

\[ \text{FLOPs}_{\text{attn}} \approx 4\, n^2 d \;\;(\text{about half with the causal mask}), \qquad \text{Mem}_{\text{scores}} = h\, n^2 \cdot 4 \text{ bytes (fp32)} \tag{102.2} \]
Read the symbols
\(n\)
the sequence length
\(d = h\, d_h\)
the model width (all heads together)
\(4 n^2 d\)
\(2 n^2 d\) for \(QK^{\top}\) and \(2 n^2 d\) for multiplying the weights with \(V\)

Both grow with \(n^2\). But the two terms are different problems. The FLOPs are work the GPU must do. The memory is only needed if the code stores the score matrix. A fused kernel such as FlashAttention (session 124) computes the same result block by block and never stores it, so its memory grows like \(n\). You will see both versions in Step 4: naive writes the formula with tensors, full calls F.scaled_dot_product_attention (SDPA), which picks a fused kernel when the backend has one.

GQA: share keys and values

Grouped-query attention [Ainslie et al., 2023] keeps all \(h\) query heads but only \(h_{kv}\) key/value heads. Query head \(i\) uses K/V head \(\lfloor i / g \rfloor\), with group size \(g = h / h_{kv}\). MQA is the case \(h_{kv} = 1\); MHA is \(h_{kv} = h\). The scores are still exact softmax scores over all earlier tokens, so (102.2) does not change. What changes is the number of keys and values that must be kept for decoding:

\[ \text{KV bytes} = 2 \cdot L \cdot h_{kv} \cdot d_h \cdot n \cdot b, \qquad \text{saving vs MHA} = \frac{h}{h_{kv}} = g \tag{102.3} \]
Read the symbols
\(2\)
one key and one value per token
\(L\)
the number of layers
\(h_{kv}\)
the number of K/V heads (8 in Llama 3 8B, against 32 query heads)
\(b\)
bytes per number: 2 for fp16 or bf16

For Llama 3.1 8B (32 layers, 8 K/V heads of size 128, from its config.json) one token costs \(2 \cdot 32 \cdot 8 \cdot 128 \cdot 2 = 131{,}072\) bytes, so 8,192 tokens take exactly 1 GiB. With 32 K/V heads it would be 4 GiB. [Certain]

Linformer: compress the sequence of keys

Linformer [Wang et al., 2020] observed that the attention matrix is often close to low rank, and multiplies keys and values by learned matrices \(E, F \in \R^{k \times n}\) that compress \(n\) positions into \(k\) slots:

\[ O = \softmax\!\Big( \frac{Q\, (E K)^{\top}}{\sqrt{d_h}} \Big)\, (F V), \qquad \text{cost} \propto n\, k\, d \tag{102.4} \]
Read the symbols
\(E, F\)
learned \(k \times n\) projection matrices, one pair per layer (shared by the heads here)
\(k\)
the projected length: 128 or 256 in the paper’s main experiments [Likely], 256 in our benchmark, 32 in our small GPT
\(EK, FV\)
\(k\) compressed keys and values; each is a weighted sum over all \(n\) positions

Look at the last line of the symbol list. Slot \(j\) of \(EK\) is \(\sum_{s=1}^{n} E_{js} k_s\): it mixes keys from every position, including positions after \(t\). There is no place to put a causal mask, because a slot is not “before” or “after” anything. The paper used Linformer for encoders (BERT-style), where this is fine. In a causal language model it is a leak: query \(t\) can read the token it is asked to predict. Step 2 measures this.

To get a causal version for the comparison, we use the simplest fix that keeps the Linformer idea: cut the sequence into blocks of \(B = n/k\) tokens, compress each finished block into one summary key and one summary value (a learned weighted sum, the block-diagonal part of \(E\) and \(F\)), and let each query also see the exact keys of its own block up to itself:

\[ \text{query } t \text{ in block } j \text{ reads } \underbrace{\{\bar k_1, \dots, \bar k_{j-1}\}}_{\text{summaries}} \cup \underbrace{\{k_s : s \in \text{block } j,\ s \le t\}}_{\text{exact, local}}, \qquad \bar k_i = \sum_{s \in \text{block } i} E_{is}\, k_s \tag{102.5} \]

Each query reads at most \(n/B + B\) keys. This is our own construction for the lab, not a method from the Linformer paper. With \(n = 256\) and \(k = 32\) blocks, \(B = 8\): a query reads at most 31 summaries plus 8 exact keys.

Performer: attention as a running sum

Performer [Choromanski et al., 2020] writes the softmax kernel \(\exp(q^{\top} k)\) as an expected dot product of random features. With \(m\) random directions \(w_1, \dots, w_m\) drawn from a Gaussian (FAVOR+, “fast attention via positive orthogonal random features”):

\[ \phi(x) = \frac{1}{\sqrt{m}} \Big[ e^{\,w_1^{\top} x - \lVert x \rVert^2/2}, \dots, e^{\,w_m^{\top} x - \lVert x \rVert^2/2} \Big], \qquad \E_w\big[ \phi(q)^{\top} \phi(k) \big] = e^{\,q^{\top} k} \tag{102.6} \]
Read the symbols
\(w_i\)
random vectors in \(\R^{d_h}\), drawn once; orthogonal in blocks of \(d_h\) to lower the variance
\(m\)
the number of random features (128 in our GPT, 256 in the benchmark)
\(\phi(x)\)
a vector of \(m\) positive numbers; positive so that the attention weights stay positive
\(q, k\)
a query and a key, each first scaled by \(d_h^{-1/4}\), so that \(q^{\top}k\) is the usual \(q^{\top}k / \sqrt{d_h}\)

Once softmax weights are dot products of features, the order of multiplication can change. For causal attention, query \(t\) needs only two running sums:

\[ S_t = S_{t-1} + \phi(k_t)\, v_t^{\top}, \qquad z_t = z_{t-1} + \phi(k_t), \qquad y_t = \frac{S_t^{\top} \phi(q_t)}{z_t^{\top} \phi(q_t)} \tag{102.7} \]
Read the symbols
\(S_t\)
an \(m \times d_h\) state matrix: the sum of \(\phi(k_s) v_s^{\top}\) over all \(s \le t\)
\(z_t\)
an \(m\)-vector: the sum of \(\phi(k_s)\), used to normalize like the softmax denominator
\(y_t\)
the output for query \(t\): an estimate of row \(t\) of (102.1)

The cost is \(O(n\, m\, d_h)\) per head, linear in \(n\), and at decode time the state has a fixed size: \(m d_h + m = 128 \cdot 32 + 128 = 4{,}224\) numbers per head in our GPT, whether the context is 10 tokens or 10 million. That is the promise. The price is that (102.6) holds only on average over the random \(w\). The variance of one feature’s estimate is [Choromanski et al., 2020]:

\[ \operatorname{Var}\big[ \widehat{\mathrm{SM}}(q, k) \big] = \frac{1}{m}\, e^{\,2 q^{\top} k} \big( e^{\lVert q + k \rVert^2} - 1 \big) \tag{102.8} \]

So the relative error falls like \(1/\sqrt{m}\), and grows quickly with \(\lVert q + k \rVert\). Large logits, the ones that make attention sharp, are exactly where the estimate is worst. Step 3 shows this, and Step 7 shows what it does to recall. (We checked (102.8) by expanding \(\E[e^{2w^{\top}(q+k)}] = e^{2\lVert q+k\rVert^2}\) for Gaussian \(w\).)

10
exact keyinside a summary or slotfolded into the statefuture position (leak)
Figure 1. What one query reads, for 16 tokens. Rows are queries, columns are keys. The highlighted row is query \(t\); other rows are faded. Linformer uses \(k = 4\) slots; the causal variant uses blocks of 4 (dashed boxes).
How to read Figure 1

Full attention and GQA draw the same triangle: both are exact. GQA changes only what is stored (the readout counts cached vectors: 80 for full attention at \(t = 10\), 40 for GQA). Switch to “Linformer (paper)”: the row is full width, and the red cells are future tokens mixed into the slots. The causal block version reads 2 summaries and 2 exact keys at \(t = 10\). Performer has no exact keys at all: everything before \(t\) lives in one state matrix. Click any row to move the query.

The code

The whole model is in lab.py. One class Attention holds the five variants (naive is full attention with the score matrix stored). Two details are easy to get wrong. First, the Performer features need a constant subtracted inside the exponent for stability; it must be a constant that cancels between the numerator and the denominator of (102.7): one value per query row, and one value shared by all keys of a head. Second, the causal sums of (102.7) are computed by chunks of 64 tokens: a cumulative sum of per-chunk states for the past, and a small masked matrix inside the chunk. A per-token cumulative sum would store an \(m \times d_h\) matrix for every token.

Algorithm 1: causal Linformer with block summaries (one head)
  1. input: \(Q, K, V \in \R^{n \times d_h}\), block size \(B\), learned weights \(e, f \in \R^{n}\)
  2. split positions into \(n/B\) blocks
  3. for each block \(i\): \(\bar k_i \leftarrow \sum_{s \in i} e_s k_s\),  \(\bar v_i \leftarrow \sum_{s \in i} f_s v_s\)
  4. for each query \(t\) in block \(j\) do // all queries in parallel in the code
  5. \(a \leftarrow [\, q_t^{\top} \bar k_i / \sqrt{d_h} \text{ for } i \lt j \,] \,\Vert\, [\, q_t^{\top} k_s / \sqrt{d_h} \text{ for } s \in j, s \le t \,]\)
  6. \(p \leftarrow \softmax(a)\) // one softmax over summaries and local keys together
  7. \(y_t \leftarrow \sum_{i \lt j} p_i \bar v_i + \sum_{s \in j, s \le t} p_s v_s\)
  8. return \(Y\)
Algorithm 2: causal Performer by chunks (one head)
  1. input: \(Q, K, V\), random directions \(W \in \R^{m \times d_h}\), chunk size \(C\)
  2. \(\Phi_Q \leftarrow \phi(Q d_h^{-1/4})\), \(\Phi_K \leftarrow \phi(K d_h^{-1/4})\) // (102.6), with stabilizing constants
  3. for each chunk \(c\): \(P_c \leftarrow \Phi_{K,c}^{\top} V_c\) (\(m \times d_h\)),  \(\zeta_c \leftarrow \Phi_{K,c}^{\top} \mathbf{1}\)
  4. \(S_c \leftarrow \sum_{c' \lt c} P_{c'}\),  \(Z_c \leftarrow \sum_{c' \lt c} \zeta_{c'}\) // exclusive prefix sums over chunks
  5. \(A_c \leftarrow \operatorname{tril}(\Phi_{Q,c} \Phi_{K,c}^{\top})\) // \(C \times C\), inside the chunk
  6. \(Y_c \leftarrow (\Phi_{Q,c} S_c + A_c V_c) \,/\, (\Phi_{Q,c} Z_c + A_c \mathbf{1})\)
  7. return \(Y\)
# Part 1: four attention layers behind one interface, in one small GPT.
import math, torch, torch.nn as nn, torch.nn.functional as F

def orthogonal_gaussian(m, d, g):
    # m random directions in R^d, orthogonal in blocks of d, with chi(d) lengths (FAVOR+)
    blocks = []
    for _ in range(math.ceil(m / d)):
        q, _ = torch.linalg.qr(torch.randn(d, d, generator=g))
        blocks.append(q.T)
    W = torch.cat(blocks)[:m]
    norms = torch.randn(m, d, generator=g).norm(dim=1, keepdim=True)
    return W * norms                                   # (m, d)

def favor_features(x, W, is_query):
    # positive random features: phi(x) = exp(w.x - |x|^2/2) / sqrt(m), x already scaled by d^-1/4
    proj = x @ W.T                                     # (..., T, m)
    sq = (x * x).sum(-1, keepdim=True) / 2
    if is_query:   # any constant per query row cancels in num/den
        stab = proj.amax(-1, keepdim=True)
    else:          # one constant for all keys of a head cancels too
        stab = proj.amax(dim=(-1, -2), keepdim=True)
    return torch.exp(proj - sq - stab.detach()) / math.sqrt(W.shape[0])

def causal_linear_attention(qf, kf, v, C):
    # chunked prefix sums: state S = sum_{s<chunk} phi(k_s) v_s^T, plus masked intra-chunk part
    B, h, T, m = qf.shape; n = T // C; dv = v.shape[-1]
    qf, kf, v = qf.view(B, h, n, C, m), kf.view(B, h, n, C, m), v.view(B, h, n, C, dv)
    kv = torch.einsum('bhncm,bhncd->bhnmd', kf, v)
    S = kv.cumsum(2) - kv                               # state before each chunk
    z = kf.sum(3); Z = z.cumsum(2) - z
    num = torch.einsum('bhncm,bhnmd->bhncd', qf, S)
    den = torch.einsum('bhncm,bhnm->bhnc', qf, Z)
    A = torch.einsum('bhncm,bhnem->bhnce', qf, kf).tril()
    num = num + A @ v; den = den + A.sum(-1)
    return (num / den.clamp_min(1e-30).unsqueeze(-1)).reshape(B, h, T, dv)

class Attention(nn.Module):
    def __init__(s, d, h, T, kind, h_kv=None, k=32, m=128, chunk=64, seed=0):
        super().__init__()
        s.d, s.h, s.dh, s.kind, s.T = d, h, d // h, kind, T
        s.h_kv = h_kv if kind == 'gqa' else h
        s.q = nn.Linear(d, d, bias=False)
        s.kv = nn.Linear(d, 2 * s.h_kv * s.dh, bias=False)
        s.o = nn.Linear(d, d, bias=False)
        if kind in ('linformer', 'linformer_causal'):
            s.kp = k                                    # projected length
            s.E = nn.Parameter(torch.randn(k, T) / math.sqrt(T))   # keys:   n -> k
            s.Fp = nn.Parameter(torch.randn(k, T) / math.sqrt(T))  # values: n -> k
        if kind == 'performer':
            g = torch.Generator().manual_seed(seed)
            s.register_buffer('W', orthogonal_gaussian(m, s.dh, g))
            s.chunk = chunk

    def forward(s, x):
        B, T, _ = x.shape
        q = s.q(x).view(B, T, s.h, s.dh).transpose(1, 2)              # (B, h, T, dh)
        k, v = s.kv(x).view(B, T, 2, s.h_kv, s.dh).permute(2, 0, 3, 1, 4)
        if s.kind == 'full':
            y = F.scaled_dot_product_attention(q, k, v, is_causal=True)
        elif s.kind == 'naive':                                        # full attention, T x T matrix stored
            att = (q @ k.transpose(-1, -2)) / math.sqrt(s.dh)
            att = att.masked_fill(torch.ones(T, T, dtype=torch.bool, device=x.device).triu(1), float('-inf'))
            y = att.softmax(-1) @ v
        elif s.kind == 'gqa':                                          # share K, V in groups
            g = s.h // s.h_kv
            y = F.scaled_dot_product_attention(q, k.repeat_interleave(g, 1),
                                               v.repeat_interleave(g, 1), is_causal=True)
        elif s.kind == 'linformer':                                    # as in the paper: no mask
            kp = torch.einsum('kt,bhtd->bhkd', s.E[:, :T], k)
            vp = torch.einsum('kt,bhtd->bhkd', s.Fp[:, :T], v)
            y = F.scaled_dot_product_attention(q, kp, vp)
        elif s.kind == 'linformer_causal':                             # block-diagonal E + local block
            b = T // s.kp                                              # tokens per block
            E = s.E[:, :T].view(s.kp, s.kp, b).diagonal(dim1=0, dim2=1).T  # (k blocks, b) weights
            Fv = s.Fp[:, :T].view(s.kp, s.kp, b).diagonal(dim1=0, dim2=1).T
            kb, vb = k.view(B, s.h, s.kp, b, s.dh), v.view(B, s.h, s.kp, b, s.dh)
            kc = torch.einsum('jt,bhjtd->bhjd', E, kb)                 # one summary key per block
            vc = torch.einsum('jt,bhjtd->bhjd', Fv, vb)
            nb, sc = s.kp, s.dh ** -0.5
            s_past = (q @ kc.transpose(-1, -2) * sc).view(B, s.h, nb, b, nb)   # scores vs block summaries
            j = torch.arange(nb, device=x.device)
            s_past = s_past.masked_fill(~(j[None, :] < j[:, None])[:, None, :], float('-inf'))  # earlier blocks only
            qb = q.view(B, s.h, nb, b, s.dh)
            s_loc = qb @ kb.transpose(-1, -2) * sc                                # (B, h, nb, b, b)
            s_loc = s_loc.masked_fill(torch.ones(b, b, dtype=torch.bool, device=x.device).triu(1), float('-inf'))
            p = torch.cat([s_past, s_loc], -1).softmax(-1)                        # one softmax over nb + b
            y = (p[..., :nb].reshape(B, s.h, T, nb) @ vc).view(B, s.h, nb, b, s.dh) + p[..., nb:] @ vb
            y = y.reshape(B, s.h, T, s.dh)
        elif s.kind == 'performer':
            sc = s.dh ** -0.25
            qf = favor_features(q * sc, s.W, True)
            kf = favor_features(k * sc, s.W, False)
            y = causal_linear_attention(qf, kf, v, min(s.chunk, T))
        return s.o(y.transpose(1, 2).reshape(B, T, s.d))

class Block(nn.Module):
    def __init__(s, d, h, T, kind, **kw):
        super().__init__()
        s.n1, s.n2 = nn.LayerNorm(d), nn.LayerNorm(d)
        s.att = Attention(d, h, T, kind, **kw)
        s.mlp = nn.Sequential(nn.Linear(d, 4 * d), nn.GELU(), nn.Linear(4 * d, d))
    def forward(s, x):
        x = x + s.att(s.n1(x))
        return x + s.mlp(s.n2(x))

class GPT(nn.Module):
    def __init__(s, V, d, L, h, T, kind, **kw):
        super().__init__()
        s.tok, s.pos = nn.Embedding(V, d), nn.Embedding(T, d)
        s.blocks = nn.ModuleList([Block(d, h, T, kind, seed=i, **kw) for i in range(L)])
        s.nf, s.head = nn.LayerNorm(d), nn.Linear(d, V, bias=False)
    def forward(s, idx):
        x = s.tok(idx) + s.pos(torch.arange(idx.shape[1], device=idx.device))
        for b in s.blocks: x = b(x)
        return s.head(s.nf(x))

Parameter counts: full attention 840,704; GQA with 2 K/V heads 775,168 and MQA 742,400 (the K/V projection shrinks from \(2 \cdot 128 \cdot 128\) to \(2 \cdot h_{kv} \cdot 32 \cdot 128\) per layer); Performer 840,704 (its random directions are a fixed buffer, not parameters). The causal Linformer stores full \(k \times n\) matrices \(E, F\) (906,240 parameters in total) but uses only their block-diagonal part, 2,048 numbers in all: in effect 842,752.

Step 2: check correctness first, including the leak test

Before timing anything, check that each layer computes what you think. check.py runs three tests in float64 on the CPU, so rounding does not hide bugs.

  1. Chunked equals quadratic. The chunked Performer sums of Algorithm 2 must equal the plain formula \(\operatorname{tril}(\Phi_Q \Phi_K^{\top}) V\) divided by its row sums.
  2. The leak test. Build a random 2-layer model, feed a sequence, then change only tokens 40 to 63 and feed it again. In a causal model the outputs at positions 0 to 39 cannot change. Any change means that some position reads the future.
  3. Approximation error. Compare causal Performer attention with exact causal softmax attention on random inputs, for several \(m\).
# Part 1b: three correctness checks before any benchmark (float64, CPU)
import torch, torch.nn.functional as F
from lab import GPT, orthogonal_gaussian, favor_features, causal_linear_attention
torch.manual_seed(0)
# (a) the chunked prefix-sum form equals the quadratic form of causal linear attention
qf, kf = torch.rand(1, 2, 64, 16, dtype=torch.float64), torch.rand(1, 2, 64, 16, dtype=torch.float64)
v = torch.randn(1, 2, 64, 8, dtype=torch.float64)
A = (qf @ kf.transpose(-1, -2)).tril()
ref = (A @ v) / A.sum(-1, keepdim=True)
print('chunked vs quadratic:', (causal_linear_attention(qf, kf, v, 16) - ref).abs().max().item())
# (b) the leak test: change tokens 40..63, outputs at positions 0..39 must not move
for kind in ['full', 'gqa', 'linformer', 'linformer_causal', 'performer']:
    torch.manual_seed(0)
    M = GPT(65, 64, 2, 4, 64, kind, h_kv=2, k=8, m=32, chunk=16).double()
    x = torch.randint(0, 65, (1, 64)); x2 = x.clone(); x2[0, 40:] = torch.randint(0, 65, (24,))
    print(f'{kind:17s} max change at positions 0..39: {(M(x)[0, :40] - M(x2)[0, :40]).abs().max().item():.3g}')
# (c) how well FAVOR+ approximates causal softmax attention, as a function of m
q, k = 0.5 * torch.randn(2, 1, 1, 256, 32, dtype=torch.float64)
v = torch.randn(1, 1, 256, 32, dtype=torch.float64)
exact = F.scaled_dot_product_attention(q, k, v, is_causal=True)
for m in [16, 64, 256, 1024]:
    W = orthogonal_gaussian(m, 32, torch.Generator().manual_seed(1)).double()
    s = 32 ** -0.25
    y = causal_linear_attention(favor_features(q * s, W, True), favor_features(k * s, W, False), v, 64)
    print(f'm = {m:4d}  relative error {((y - exact).norm() / exact.norm()).item():.3f}')

Output:

chunked vs quadratic: 2.7755575615628914e-16 full max change at positions 0..39: 0 gqa max change at positions 0..39: 0 linformer max change at positions 0..39: 0.198 linformer_causal max change at positions 0..39: 0 performer max change at positions 0..39: 8.88e-16 m = 16 relative error 0.618 m = 64 relative error 0.300 m = 256 relative error 0.183 m = 1024 relative error 0.103

The paper version of Linformer fails the leak test: changing the future moves the past outputs by up to 0.198. The others pass (the Performer’s \(10^{-15}\) is float64 rounding: its key constant is a maximum over all keys of the head, which cancels exactly in (102.7) but is computed from future keys). If you train the leaky Linformer as a language model, its loss falls far below every honest model, because it can copy the answer. The worked example below shows this. From here on, “Linformer” in a causal comparison means the block version of (102.5).

The error of the Performer estimate falls from 0.618 at \(m = 16\) to 0.103 at \(m = 1024\): a factor of 6.0 for 64 times more features, close to the \(\sqrt{64} = 8\) that (102.8) predicts. Even at \(m = 1024\) (32 times the head size) the output is 10% off.

A worked example: is the leak large?

A value of 0.198 sounds small. But it is a change in the logits of a random, untrained model, caused only by future tokens. A trained model will use any path that lowers the loss, and the most useful path in language modeling is “read the next token”. In our 3,000-step training run of the leaky Linformer (Step 6), the validation loss reached 0.1685 nats per character, against 1.6725 for full attention. A loss far below what an honest model of this size reaches is the sign of a leak, not of a better model.

You can measure what happens when the future is not there, as during generation. Look only at the last position of each 256-token window: its next character is outside the window, so nothing can leak. On the same 40 validation batches, full attention has a loss of 1.7088 at the last position; the leaky Linformer has 2.5444. The model learned to read the answer, and without it, it is much worse than an honest model. (lastpos.py: load each checkpoint and compute the cross-entropy of logits[:, -1] only.)

Step 3: how good is the Performer estimate?

Figure 2 takes one query and 24 keys of size 16 and compares the exact softmax weights with the FAVOR+ estimate. You can change the number of features \(m\), the random draw of the features, and a scale \(\beta\) on the logits (\(\beta = 4\) multiplies every logit by 4, which makes the attention sharper).

Logit scale \(\beta\)
64 1
exact softmax weightPerformer (FAVOR+) estimate
Figure 2. Exact attention weights of one query over 24 keys (left bar of each pair) and the FAVOR+ estimate from \(m\) orthogonal random features (right bar). The readout gives the total variation distance between the two distributions, for this draw and on average over 20 draws. Computed live in your browser with a seeded random generator.
How to read Figure 2

At \(\beta = 1\) and \(m = 64\), the largest true weight is 0.1007 (key 16) and the estimate is 0.1282; the average distance over 20 draws is 0.2925. Raise \(m\) to 512: it drops to 0.173. With soft logits (\(\beta = 0.25\)) the average distance falls from 0.1691 at \(m = 8\) to 0.0255 at \(m = 512\), close to the \(1/\sqrt{m}\) rate. With sharp logits (\(\beta = 4\)) it stays above 0.5 even at \(m = 512\): this is the \(e^{\lVert q+k \rVert^2}\) term of (102.8). Move the draw slider: with few features, the bars jump around from draw to draw. That randomness is the variance.

This figure explains a lot of what follows. A language model needs sharp attention when it must find one specific earlier token: one weight close to 1, the others close to 0. That requires a large logit, and a large logit is where FAVOR+ is least accurate. Performer can be good on average and still bad at the one thing a copy needs.

Step 4: speed and memory of one layer, 512 to 16k tokens

Now time one attention layer of the size used in small real models: \(d = 512\), 8 heads of size 64, batch 1, float32, forward plus backward (training cost). Linformer uses \(k = 256\) and Performer \(m = 256\), sizes in the range the papers use [Likely]. Three rules make a timing honest:

  1. Warm up first. The first calls compile kernels and allocate memory.
  2. Synchronize before you stop the clock. A GPU call returns at once; the work runs later. Without torch.mps.synchronize() you time the launch, not the work.
  3. Report the median of several runs. On a shared machine some runs are slow for reasons that have nothing to do with your code.

For memory, we do not trust the process size. We trace every allocation with PyTorch’s MemTracker under FakeTensorMode: the layer runs on “fake” tensors that have shapes but no data, so even the 26 GB case can be counted on a laptop. The tracer follows the same kernel choice as the real backend. We checked the MPS numbers once with real tensors: after the forward pass of exact attention at \(n = 4{,}096\), 579 MB stay allocated, close to one \(8 \times 4096 \times 4096\) float32 matrix (537 MB).

# Part 3: time (Apple GPU) and peak memory (MemTracker, fake tensors) of one attention layer, forward + backward
import torch, time, json, sys
from torch._subclasses.fake_tensor import FakeTensorMode
from torch.distributed._tools.mem_tracker import MemTracker
from lab import Attention
D, H = 512, 8
KINDS = {'naive': dict(kind='naive'), 'full': dict(kind='full'), 'gqa': dict(kind='gqa', h_kv=2),
         'linformer': dict(kind='linformer', k=256), 'linformer_causal': dict(kind='linformer_causal', k=256),
         'performer': dict(kind='performer', m=256, chunk=128)}
def make(name, n, dev):
    torch.manual_seed(0); return Attention(D, H, n, **KINDS[name]).to(dev)
def peak_bytes(name, n, dev):
    with FakeTensorMode():
        a = make(name, n, dev); x = torch.randn(1, n, D, device=dev, requires_grad=True)
        mt = MemTracker(); mt.track_external(a)
        with mt:
            a(x).sum().backward()
        snap = mt.get_tracker_snapshot('peak'); return list(snap.values())[0]['Total']
def ms(name, n, reps):
    a = make(name, n, 'mps'); x = torch.randn(1, n, D, device='mps', requires_grad=True)
    for _ in range(2): a(x).sum().backward()
    torch.mps.synchronize(); t = []
    for _ in range(reps):
        t0 = time.perf_counter(); a(x).sum().backward(); torch.mps.synchronize(); t.append(time.perf_counter() - t0)
    t.sort(); return round(1000 * t[len(t) // 2], 3)
if __name__ == '__main__':
    NS = [512, 1024, 2048, 4096, 8192, 16384]; out = {}
    do_time = sys.argv[1] == 'time'
    for name in KINDS:
        out[name] = {}
        for n in NS:
            pc = peak_bytes(name, n, 'cpu'); pm = peak_bytes(name, n, 'mps')
            r = dict(mem_cpu=pc, mem_mps=pm)
            if do_time and pm < 24e9: r['ms'] = ms(name, n, 7 if n <= 4096 else 3)
            out[name][n] = r; print(name, n, r, flush=True)
    json.dump(out, open('bench.json' if do_time else 'bench_mem.json', 'w'))

The timing on the CPU uses the same layers (bench_cpu.py, in the same folder, calls make from bench.py and times on 'cpu' without synchronization, which the CPU does not need):

# Part 3b: the same timing on the CPU, where PyTorch has a fused (FlashAttention-style) SDPA kernel
import torch, time, json
from bench import make, KINDS
def ms_cpu(name, n, reps):
    a = make(name, n, 'cpu'); x = torch.randn(1, n, 512, requires_grad=True)
    a(x).sum().backward(); t = []
    for _ in range(reps):
        t0 = time.perf_counter(); a(x).sum().backward(); t.append(time.perf_counter() - t0)
    t.sort(); return round(1000 * t[len(t) // 2], 3)
if __name__ == '__main__':
    out = {}
    for name in KINDS:
        out[name] = {}
        for n in [512, 1024, 2048, 4096, 8192, 16384]:
            if name == 'naive' and n > 8192: continue
            out[name][n] = ms_cpu(name, n, 5 if n <= 4096 else 3); print(name, n, out[name][n], flush=True)
    json.dump(out, open('bench_cpu.json', 'w'))

Why time on the CPU at all? Because PyTorch 2.8 has a fused attention kernel for training on the CPU, but on the Apple GPU the backward pass of scaled_dot_product_attention falls back to the plain formula, which stores the \(n \times n\) matrix. So the GPU shows what happens without FlashAttention, and the CPU shows what happens with a fused exact kernel. [Certain for our setup: measured, see the memory check above]

8,192
Figure 3. One attention layer, forward plus backward, measured on our laptop (Apple M5 Pro, PyTorch 2.8.0). Both axes are logarithmic, so a line with slope 2 grows like \(n^2\) and a line with slope 1 like \(n\). Missing points were not run: the naive layer and GPU full attention need about 26 GB at 16k. Click a legend entry to hide or show a line.
How to read Figure 3

Start with “Memory, GPU”: naive and full attention lie on top of each other and grow 4× per doubling of \(n\) (26.2 GB at 16k for naive), while Linformer and Performer grow 2× per doubling. Switch to “Memory, CPU (fused)”: full attention drops to 307.8 MB at 16k, now below the causal Linformer (945.9 MB) and Performer (1.35 GB). The fused kernel removed the \(n^2\) memory. Now compare the two time views at \(n = 16{,}384\): on the CPU full attention takes 1,108 ms and Performer 279 ms. The \(n^2\) work is still there, only the memory is gone. Move the slider to 2,048: on the CPU full attention (29.8 ms) still beats Performer (36.5 ms).

Each result has a formula behind it.

Naive memory is three \(n \times n\) matrices. The naive layer keeps the scores, the softmax probabilities, and, during the backward pass, a gradient of the same size. One float32 score matrix for 8 heads is \(8 n^2 \cdot 4\) bytes:

\[ \text{Mem}_{\text{naive}} \approx 3 \cdot h\, n^2 \cdot 4 \text{ bytes}, \qquad n = 16{,}384:\; 3 \times 8.59 \text{ GB} = 25.8 \text{ GB} \tag{102.9} \]
Read the symbols
\(3\)
three tensors of size \(n \times n\) per head are alive at the peak: scores, probabilities, and one gradient
\(h n^2 \cdot 4\)
one float32 matrix for all \(h = 8\) heads: 8.59 GB at \(n = 16{,}384\)

The tracer measured 26.2 GB, which is 3.05 matrices; the rest is the linear part (activations and weights). At 4,096 and 8,192 the ratio is 3.12 and 3.07. [Certain: measured]

The fused kernel keeps the \(n^2\) work. On the CPU, full attention grows 3.75× from 8,192 to 16,384 tokens (the \(n^2\) of (102.2) predicts 4×), and Performer grows 2.00× (linear). At 16k, Performer is 4.0× faster than fused full attention, the causal Linformer 6.9×, and the leaky paper Linformer 9.3×.

The crossover comes later than the FLOP count says. Counting multiply-adds, Performer with \(m = 256\) should match exact causal attention near \(n \approx 2m\) to \(4m\), that is 512 to 1,024 tokens (Interview question 6). On the GPU without a fused kernel, Performer passes full attention between 1,024 and 2,048 tokens. Against the fused CPU kernel, it passes between 2,048 and 4,096. The causal Linformer ties fused full attention at 2,048 (29.9 ms against 29.8 ms) and wins after. The approximation runs many small operations (feature maps, chunk sums, prefix sums); the exact kernel is one tuned operation. Below a few thousand tokens, exact attention is the fastest choice even before you look at quality. [Certain for this machine; the exact crossover differs on other hardware]

GQA does not help here. On the CPU it takes 0.80 to 0.92 of the time of full attention: a little faster, because its K/V projection is 4 times smaller, but its score work is the same \(n^2\). On the GPU our GQA layer was even slower than full attention at most lengths, because it copies K and V to all 8 heads with repeat_interleave before calling the kernel. GQA is a decode-time optimization. The next step measures it there.

Step 5: decoding with a KV cache, where GQA pays off

When a model generates text, it produces one token per step. The new token’s query must attend to the keys and values of all earlier tokens, which are kept in the KV cache (session 80). There is very little arithmetic per step (one query row), but the whole cache must be read from memory. So a decode step is memory-bound: its time is set by bytes, not by FLOPs:

\[ t_{\text{step}} \approx t_0 + \frac{\text{KV bytes}}{\text{bandwidth}}, \qquad \text{KV bytes per layer} = 2\, B\, h_{kv}\, d_h\, n\, b \tag{102.10} \]
Read the symbols
\(t_0\)
a fixed cost per step: launching the kernel, reading the query, writing the output
\(B\)
the batch: the number of sequences decoded together (8 here)
\(n\)
the number of tokens already in the cache
bandwidth
bytes per second the memory delivers in practice

With (102.3), GQA divides the bytes by \(g = h / h_{kv}\). So (102.10) predicts that GQA with 8 K/V heads instead of 32 should make a long-context decode step up to 4 times faster, and MQA up to 32 times, until \(t_0\) dominates. decode.py measures one layer with the attention shape of Llama 3.1 8B (32 query heads of size 128) in float16.

The important line is the one marked fold. A GQA kernel must not copy the cache. The trick: reshape the 32 query heads into 8 groups of 4, and treat the 4 query heads of a group as 4 queries against one K/V head. Each K/V head is then read once. During decoding the new token may see the whole cache, so no mask is needed.

# Part 5 (decode.py): one decode step of attention against a KV cache (Llama-3-8B attention shape: 32 query heads, head size 128)
import torch, time, json, sys, torch.nn.functional as F
B, H, DH, dev, dt = 8, 32, 128, 'mps', torch.float16
def step_ms(n, h_kv, mode, reps=20):
    torch.manual_seed(0); g = H // h_kv
    q = torch.randn(B, H, 1, DH, device=dev, dtype=dt)
    k = torch.randn(B, h_kv, n, DH, device=dev, dtype=dt); v = torch.randn_like(k)
    def f():
        if mode == 'repeat':      # copies the cache to 32 heads first
            return F.scaled_dot_product_attention(q, k.repeat_interleave(g, 1), v.repeat_interleave(g, 1))
        if mode == 'enable_gqa':  # PyTorch flag (>= 2.5); which kernel runs depends on the backend
            return F.scaled_dot_product_attention(q, k, v, enable_gqa=True)
        if mode == 'fold':        # the g query heads of a group become g queries of one K/V head
            y = F.scaled_dot_product_attention(q.view(B, h_kv, g, DH), k, v)   # no mask: 1 new token sees all
            return y.view(B, H, 1, DH)
        return F.scaled_dot_product_attention(q, k, v)
    for _ in range(3): f()
    torch.mps.synchronize(); t = []
    for _ in range(reps):
        t0 = time.perf_counter(); f(); torch.mps.synchronize(); t.append(time.perf_counter() - t0)
    t.sort(); return round(1000 * t[len(t) // 2], 4)
if __name__ == '__main__':
    out = {}
    for n in [512, 1024, 2048, 4096, 8192, 16384]:
        r = {'mha': step_ms(n, 32, 'mha'), 'gqa8': step_ms(n, 8, 'fold'), 'mqa': step_ms(n, 1, 'fold'),
             'gqa8_repeat': step_ms(n, 8, 'repeat'), 'gqa8_flag': step_ms(n, 8, 'enable_gqa')}
        r['kv_mb_mha'] = 2 * B * 32 * DH * n * 2 / 1e6
        out[n] = r; print(n, r, flush=True)
    json.dump(out, open('decode.json', 'w'))
16,384
Figure 4. Time of one decode step of one attention layer (median of 20), batch 8, 32 query heads of size 128, float16, on the laptop GPU. “Folded” is the no-copy kernel of decode.py. Both axes are logarithmic.
How to read Figure 4

At 16,384 cached tokens, MHA reads a 2,147 MB cache in 7.75 ms, about 277 GB/s. GQA-8 folded reads a quarter of that and takes 2.93 ms (2.64× faster); MQA takes 0.73 ms (10.7×). Both copying versions take about 66 to 67 ms: 8.6 times slower than MHA. Move the slider down to 512: MHA, GQA-8 folded and MQA come together between 0.26 and 0.76 ms, because the fixed cost \(t_0\) dominates when the cache is small. The copying versions still take about 2.3 ms.

The measured speed-ups are smaller than the byte ratio, 2.64× instead of 4× for GQA-8 at 16k, and 10.7× instead of 32× for MQA. Two reasons, both visible in (102.10): the fixed cost \(t_0\) (MQA’s 67 MB cache would take a quarter of a millisecond at 277 GB/s, but the step takes 0.73 ms), and lower effective bandwidth for the smaller, folded reads (183 GB/s for GQA-8 against 277 GB/s for MHA). [Likely: the second reason is our reading of the numbers; we did not profile the kernel]

The two copying versions are the real lesson. repeat_interleave reads the 8-head cache and writes a 32-head copy at every step, and only then runs attention on the copy: more memory traffic than MHA itself. And the enable_gqa=True flag of PyTorch 2.8 gave the same time as the copy on this backend, so on MPS it does not avoid the copy. [Certain for PyTorch 2.8.0 on MPS: measured. On CUDA, fused kernels such as FlashAttention index the shared head directly] A model can “use GQA” and still pay MHA’s decode cost, or more, if the kernel copies.

16,384 8
Figure 5. KV-cache size of four open models in bf16, from (102.3), with the shapes in their config.json files. The bars compare the shipped GQA cache with what multi-head K/V (one K/V head per query head) and MQA would need.
How to read Figure 5

Llama 3.1 8B costs 131,072 bytes per token, so 8 sequences of 16,384 tokens need 17.18 GB of cache with GQA; with 32 K/V heads it would be 68.72 GB, more than the 16 GB of the bf16 weights. Pick Qwen2.5-0.5B: 2 K/V heads for 14 query heads, a 7× saving. Push the context to 131,072 tokens and watch the MHA bar: this is why every model in the list ships with GQA.

Step 6: quality, part 1: validation loss

Now train the small GPT of Step 1 with each attention layer for 3,000 steps and measure the validation loss (cross-entropy in nats per character on the held-out 10% of Tiny Shakespeare, averaged over 40 fixed batches). Everything except the attention layer is identical: initialization seed, batch order, learning-rate schedule (warm-up for 200 steps to \(10^{-3}\), cosine decay to \(10^{-4}\)), AdamW with weight decay 0.1, gradient clipping at 1.0.

# Part 2: train each variant on Tiny Shakespeare, same data order, same seed
import torch, math, time, json, sys
from lab import GPT
torch.manual_seed(0)
text = open('input.txt').read(); chars = sorted(set(text)); stoi = {c: i for i, c in enumerate(chars)}
data = torch.tensor([stoi[c] for c in text]); n = int(0.9 * len(data)); tr, va = data[:n], data[n:]
T, B, STEPS = 256, 32, int(sys.argv[2]) if len(sys.argv) > 2 else 3000
dev = 'mps'
def batch(split, g):
    d = tr if split == 'train' else va
    ix = torch.randint(len(d) - T - 1, (B,), generator=g)
    x = torch.stack([d[i:i + T] for i in ix]); y = torch.stack([d[i + 1:i + T + 1] for i in ix])
    return x.to(dev), y.to(dev)
gv = torch.Generator().manual_seed(123); VAL = [batch('val', gv) for _ in range(40)]
@torch.no_grad()
def evaluate(model):
    model.eval(); L = [torch.nn.functional.cross_entropy(model(x).flatten(0, 1), y.flatten()).item() for x, y in VAL]
    model.train(); return sum(L) / len(L)
def lr_at(s, peak=1e-3, warm=200, low=1e-4):
    if s < warm: return peak * (s + 1) / warm
    p = (s - warm) / max(1, STEPS - warm); return low + 0.5 * (peak - low) * (1 + math.cos(math.pi * p))
CFG = {'full': dict(kind='full'), 'gqa': dict(kind='gqa', h_kv=2), 'mqa': dict(kind='gqa', h_kv=1),
       'linformer': dict(kind='linformer', k=32), 'linformer_causal': dict(kind='linformer_causal', k=32),
       'performer': dict(kind='performer', m=128, chunk=64)}
def run(name):
    torch.manual_seed(0)
    model = GPT(len(chars), 128, 4, 4, T, **CFG[name]).to(dev)
    npar = sum(p.numel() for p in model.parameters())
    opt = torch.optim.AdamW(model.parameters(), lr=1e-3, weight_decay=0.1, betas=(0.9, 0.95))
    g = torch.Generator().manual_seed(1); hist = []; t0 = time.time()
    for s in range(STEPS + 1):
        if s % 250 == 0 or s == STEPS:
            hist.append([s, round(evaluate(model), 4)]); print(name, hist[-1], round(time.time() - t0), flush=True)
        if s == STEPS: break
        for pg in opt.param_groups: pg['lr'] = lr_at(s)
        x, y = batch('train', g)
        loss = torch.nn.functional.cross_entropy(model(x).flatten(0, 1), y.flatten())
        opt.zero_grad(set_to_none=True); loss.backward()
        torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0); opt.step()
    torch.mps.synchronize()
    out = dict(name=name, params=npar, hist=hist, train_last=round(loss.item(), 4), sec=round(time.time() - t0, 1))
    torch.save(model.state_dict(), f'ck_{name}.pt'); return out
if __name__ == '__main__':
    r = run(sys.argv[1]); json.dump(r, open(f'res_{sys.argv[1]}.json', 'w')); print(r)

Each run took 4 to 9 minutes on the laptop GPU (Performer was the slowest at 533 s, because the chunked sums are many small operations at this short length).

Step 7: quality, part 2: copying and recall

Validation loss averages over all characters, and most characters of English are predictable from the last few. A method can be bad at reading one exact token far back and still have a good loss. So we test that ability directly, with two synthetic tasks on a 2-layer version of the same GPT (context 128, trained 3,000 steps, loss and accuracy only on the answer tokens, 1,000 test sequences):

  • Copy: 64 random symbols from 16, a separator, then the same 64 symbols again. To predict symbol \(i\) of the copy, the model reads position \(i\) of the first half, always 65 positions back. This is the task in the session plan.
  • Associative recall (as in Zoology [Arora et al., 2023]): 32 pairs (key, value) with distinct keys, a separator, then the 32 keys again in a new random order, each followed by its value. To answer, the model must find the earlier position that holds the same key, wherever it is, and read the token after it.
# Part 4: the copy task. Input: 64 random symbols, a separator, then the same 64 symbols again.
# The loss and the accuracy count only the second copy: the model must find and repeat the exact earlier token.
import torch, json, sys, os, torch.nn.functional as F
from lab import GPT
V, S, T, B, STEPS = 16, 64, 128, 64, 3000
SEP, dev = V, os.environ.get('DEV', 'mps')
def make(n, g):
    s = torch.randint(0, V, (n, S), generator=g)
    seq = torch.cat([s, torch.full((n, 1), SEP), s], 1)          # 129 tokens
    return seq[:, :-1].to(dev), seq[:, 1:].to(dev)                # targets 64..127 are the copy
TEST = make(1000, torch.Generator().manual_seed(7))
CFG = {'full': dict(kind='full'), 'gqa': dict(kind='gqa', h_kv=2), 'mqa': dict(kind='gqa', h_kv=1),
       'linformer': dict(kind='linformer', k=32), 'linformer_causal': dict(kind='linformer_causal', k=32),
       'performer': dict(kind='performer', m=128, chunk=64)}
@torch.no_grad()
def acc(model):
    model.eval(); x, y = TEST; p = model(x).argmax(-1)[:, S:]; ok = (p == y[:, S:]).float()
    model.train(); return ok.mean().item(), ok.mean(0).tolist(), p[:4].tolist()
def run(name):
    torch.manual_seed(0); model = GPT(V + 1, 128, 2, 4, T, **CFG[name]).to(dev)
    opt = torch.optim.AdamW(model.parameters(), lr=1e-3, weight_decay=0.1, betas=(0.9, 0.95))
    g = torch.Generator().manual_seed(1); hist = []
    for s in range(STEPS + 1):
        if s % 250 == 0:
            a = acc(model)[0]; hist.append([s, round(a, 4)]); print(name, s, round(a, 4), flush=True)
        if s == STEPS: break
        x, y = make(B, g)
        loss = F.cross_entropy(model(x)[:, S:].flatten(0, 1), y[:, S:].flatten())
        opt.zero_grad(set_to_none=True); loss.backward()
        torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0); opt.step()
    a, per_pos, demo = acc(model)
    return dict(name=name, acc=round(a, 4), hist=hist, per_pos=[round(v, 3) for v in per_pos], demo=demo, loss=round(loss.item(), 4))
if __name__ == '__main__':
    if os.path.exists(f'copy_{sys.argv[1]}.json'): sys.exit(0)
    r = run(sys.argv[1]); json.dump(r, open(f'copy_{sys.argv[1]}.json', 'w')); print(r['acc'], r['loss'])

recall.py is the same program with this data generator (and 129 tokens: 64 for the pairs, the separator, 64 for the questions and answers):

# Part 4b: associative recall. Input: 32 (key, value) pairs, a separator, then the 32 keys again in a new order,
# each followed by its value. The loss and the accuracy count only the answers: the model must find the earlier
# position that holds the same key, by content, and read the token after it.
import torch, json, sys, os, torch.nn.functional as F
from lab import GPT
NK, P, T, B = 64, 32, 128, 64                       # 64 possible keys, 32 pairs, context 128
STEPS = int(os.environ.get('STEPS', 3000))
SEP, dev = 2 * NK, os.environ.get('DEV', 'mps')      # keys 0..63, values 64..127, separator 128
def make(n, g):
    keys = torch.rand(n, NK, generator=g).argsort(1)[:, :P]               # 32 distinct keys per sequence
    vals = NK + torch.randint(0, NK, (n, P), generator=g)
    order = torch.rand(n, P, generator=g).argsort(1)                       # ask them in a new order
    qk, qv = keys.gather(1, order), vals.gather(1, order)
    ctx = torch.stack([keys, vals], 2).flatten(1); ask = torch.stack([qk, qv], 2).flatten(1)
    seq = torch.cat([ctx, torch.full((n, 1), SEP), ask], 1)               # 129 tokens
    return seq[:, :-1].to(dev), seq[:, 1:].to(dev)
ANS = torch.arange(2 * P + 1, T, 2)                                        # positions whose target is a value
TEST = make(1000, torch.Generator().manual_seed(7))
CFG = {'full': dict(kind='full'), 'gqa': dict(kind='gqa', h_kv=2), 'mqa': dict(kind='gqa', h_kv=1),
       'linformer': dict(kind='linformer', k=32), 'linformer_causal': dict(kind='linformer_causal', k=32),
       'performer': dict(kind='performer', m=128, chunk=64)}
@torch.no_grad()
def acc(model):
    model.eval(); x, y = TEST; ok = (model(x).argmax(-1)[:, ANS] == y[:, ANS]).float()
    model.train(); return ok.mean().item()
def run(name):
    torch.manual_seed(0); model = GPT(2 * NK + 1, 128, 2, 4, T, **CFG[name]).to(dev)
    opt = torch.optim.AdamW(model.parameters(), lr=1e-3, weight_decay=0.1, betas=(0.9, 0.95))
    g = torch.Generator().manual_seed(1); hist = []
    for s in range(STEPS + 1):
        if s % 250 == 0:
            a = acc(model); hist.append([s, round(a, 4)]); print(name, s, round(a, 4), flush=True)
        if s == STEPS: break
        x, y = make(B, g)
        loss = F.cross_entropy(model(x)[:, ANS].flatten(0, 1), y[:, ANS].flatten())
        opt.zero_grad(set_to_none=True); loss.backward()
        torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0); opt.step()
    return dict(name=name, acc=round(acc(model), 4), hist=hist, loss=round(loss.item(), 4))
if __name__ == '__main__':
    out = f'recall_{sys.argv[1]}' + ('' if STEPS == 3000 else f'_{STEPS}') + '.json'
    if os.path.exists(out): sys.exit(0)
    r = run(sys.argv[1]); json.dump(r, open(out, 'w')); print(r['acc'], r['loss'])
Figure 6. Quality of the six variants, from our runs (one seed each). Validation loss: the 4-layer character GPT on Tiny Shakespeare. Copy and recall: the 2-layer GPT on the synthetic tasks, accuracy on the test set every 250 steps. The leaky Linformer’s loss falls below the chart (to 0.1685); its value is in the table.
How to read Figure 6

In “Validation loss” the honest models end between 1.6521 and 1.8272, and the causal Linformer is the best of them. In “Copy task” every line is at or near 100% by step 250, except the causal Linformer, which needs about 500 steps (99.96% at the end). In “Associative recall” full attention jumps from 9% to 94.7% between steps 1,000 and 1,250, and GQA from 9.7% to 99.96% between steps 1,500 and 1,750; the causal Linformer stops near 74%; Performer and MQA stay near 14% and 9%. Click legend entries to hide lines.

Read the results one at a time.

Loss does not rank the methods. Full attention reached 1.6725, GQA 1.7139, MQA 1.7219, the causal Linformer 1.6521 (the best) and Performer 1.8272 (the worst). GQA and MQA are slightly behind full attention: fewer K/V parameters and less K/V capacity, at the same number of steps. The leaky Linformer reached 0.1685: it reads the answer, as Step 2 predicted.

The copy task does not separate them either. Every variant copies perfectly, including Performer and the causal Linformer. The reason is in the task: the answer is always exactly 65 positions back. With learned position embeddings, a query can find its source by position alone, a fixed offset that every layer type can learn. For the causal Linformer, the source is inside one block summary whose weights \(E\) are learned per position, so the summary can keep each of its 4 tokens in a separate direction. This is an honest negative result: a copy task with a fixed offset is too easy to test recall. [Certain: measured. The explanation is ours, Likely]

Associative recall separates them. Now the source must be found by content: the query token must match one key among 32 at an unknown position. Full attention and GQA reach 99.99%. (The leaky Linformer reaches 100%, by reading the answer that follows each question.) At step 3,000 the causal Linformer reaches 73.6%: each block summary of (102.5) averages 4 tokens, that is 2 pairs, so a key that matches a summary also brings the other pair’s value; a model that could only guess between the two would get about 50%, and the trained one untangles part of the mix. Performer reaches 13.7%, a little above the 1.6% of chance. To answer, one weight must be close to 1 and the 63 others close to 0, the sharp attention where (102.8) says the random-feature estimate is worst; and all 64 earlier tokens are folded into one state \(S_t\), so a weak match is buried under the sum of the others.

MQA is the surprise. MQA (one K/V head shared by all 4 query heads) stayed at 9.4% after 3,000 steps, while GQA with 2 K/V heads solved the task. Full attention and GQA did not improve smoothly: they sat below 10% for 1,000 steps (full) and 1,500 steps (GQA) and then jumped within 250 steps. Fewer K/V heads, later jump. This kind of sudden jump is typical when a model learns a two-step lookup (match the key, then read the next token) [Likely]. So the question is whether MQA cannot learn the lookup or only learns it later. We trained the four variants that were below 90% for 9,000 steps to find out:

recall accuracy, training continued past 3,000 steps (STEPS=9000 python recall.py mqa) step 3,000 4,000 4,500 6,000 9,000 MQA 9.35% 9.83% 10.60% 16.03% 16.82% Linformer, causal 73.71% 79.49% 99.96% 99.98% at 5,750 (run stopped there)

The causal Linformer was only slow: it jumped from 79.5% to 99.4% between steps 4,000 and 4,250. So the mixed summaries can be untangled, because the block weights \(E\) are learned per position and each summary can keep its 4 tokens in separate directions (the same reason it passed the copy task); learning to do it takes longer. (The GPU runs are not bit-exact: this run gave 73.71% at step 3,000, the first one 73.62%.) MQA rose only to 16.8% in 9,000 steps, while GQA with 2 K/V heads solved the task by step 1,750. We did not extend the Performer run, the slowest to train; at step 3,000 its accuracy was still rising slowly (9.7% at step 1,000, 13.7% at step 3,000), so we cannot say whether it would jump later (Exercise 8). Two lessons. A fixed training budget ranks methods partly by how fast they learn, not only by what they can represent, so report the curve, not one number. And sharing one K/V head across all query heads cost recall in this tiny model (2 layers, 4 heads of size 32), while 2 K/V heads did not. This is one seed and one tiny model: a warning to test your own setting, not a law. [Certain: measured, one seed. Why MQA is slow here is Speculation: a two-step lookup needs, in the first layer, a head that copies each key into the position of its value, and in the second a head that matches the question with those keys; with one shared K/V head per layer, all query heads must read the same keys and values.]

A worked example: what each method must store to answer one recall query

Take the last question of a recall sequence, at position 127. Full attention keeps 127 keys and values per head and layer: with \(d_h = 32\), that is \(2 \times 127 \times 32 = 8{,}128\) numbers per head, and it grows with the context. GQA with 2 K/V heads for 4 query heads keeps half of that per query head, but every key is still exact. Performer keeps \(m d_h + m = 4{,}224\) numbers per head (Step 1), whatever the length; for this short context that is about half of what full attention keeps, yet it answers only 13.7% of questions, because the problem is not the size of the state but that it is a smoothed sum of noisy kernel estimates. The causal Linformer with \(k = 32\) blocks of 4 keeps at most 31 summary pairs and 4 exact local pairs: \(2 \times 35 \times 32 = 2{,}240\) numbers per head.

Step 8: every result, with the formula that explains it

Result (our runs)FormulaWhy
Paper Linformer moves past outputs by 0.198 when the future changes; its loss reaches 0.1685(102.4)Each slot \(\sum_s E_{js} k_s\) sums over all positions, including future ones. No mask can be applied to a slot.
Performer error 0.618 at \(m = 16\), 0.103 at \(m = 1024\)(102.8)Variance falls like \(1/m\), so the error like \(1/\sqrt{m}\): 64× more features gave 6.0× less error (8× predicted).
Sharp logits (\(\beta = 4\)): Figure 2 distance stays above 0.5(102.8)The factor \(e^{\lVert q+k\rVert^2}\) explodes for large \(q, k\).
Naive attention: 26.2 GB at 16k, 4× per doubling(102.9)Three \(h n^2\) float32 matrices.
Fused full attention: 307.8 MB at 16k on the CPU, but 3.75× time per doubling(102.2)The fused kernel removes the stored \(n^2\) matrix, not the \(n^2\) FLOPs.
Performer beats fused exact attention only after 2,048 to 4,096 tokens(102.2), (102.7)FLOPs \(2 n^2 d\) against roughly \(4 n m d\) cross near \(2m\) to \(4m\); many small operations push the real crossover later.
GQA: 0.80 to 0.92 of full attention’s training time(102.2)Same \(n^2\) score work; only the K/V projection is smaller.
GQA-8 decode 2.64× faster, MQA 10.7×, at 16k(102.3), (102.10)Decode is memory-bound; bytes fall 4× and 32×; the fixed cost \(t_0\) and lower bandwidth eat part of the gain.
Copying the cache (repeat_interleave, enable_gqa on MPS): 8.6× slower than MHA(102.10)Each step writes and reads a 32-head copy: more bytes than MHA.
Loss: causal Linformer best (1.6521), Performer worst (1.8272)(102.5)Exact local window plus summaries is a strong bias for next-character prediction.
Recall at 3,000 steps: full and GQA 99.99%, causal Linformer 73.6% (99.99% after 5,000 steps), Performer 13.7%, MQA 9.4%(102.5), (102.7), (102.8)Content lookup needs one sharp weight on one exact key; summaries mix 2 pairs, and the Performer state blurs all of them.

Where this is used

SettingWhat is usedWhy, in terms of this lab
Open decoder LLMs (Llama 3, Qwen 2.5, SmolLM2, Mistral)GQA with exact softmax and a fused kernelQwen2.5-0.5B has 14 query heads and 2 K/V heads, SmolLM2-135M 9 and 3, Llama 3.2 1B 32 and 8 (from their config.json files). [Certain] Decoding reads the cache (Step 5); recall must stay exact (Step 7).
Long-context serving (128k tokens and more)GQA or MLA, FlashAttention for prefill, paged KV cacheThe \(n^2\) memory problem is solved by the kernel (Figure 3, CPU view), so the remaining cost is cache bytes (102.3).
Encoders on long inputs (documents, proteins)Linformer-style projections, PerformerNo causal mask is needed, so the leak of Step 2 does not exist; Performer was shown on protein sequences in its paper. [Certain]
Hybrid and recurrent models (Mamba, RWKV, Jamba)linear attention or state space layers plus a few full attention layersThe fixed-size state of (102.7) is cheap but weak at recall (Step 7), so hybrids keep some exact attention layers (session 101).
Video classification and action recognitionfull attention over space-time tokens, often factorized; linear attention in some long-video modelsA clip of 16 frames with 196 patches each is 3,136 tokens: in the range where Figure 3 shows the naive \(n^2\) memory becoming large. Labels depend on the whole clip, not on one exact token, so approximate attention hurts less.
Key-moment detection and Video-RAGexact attention (or retrieval) over frame featuresFinding the one frame that answers a question is a recall task, like the copy task: a blurred summary of the past (Linformer blocks, Performer state) loses it.
Video fingerprinting and retrievalpooled embeddings, not long attentionA fingerprint is a compressed summary by design; the low-rank idea behind Linformer is the right tool when you want a summary.

Common mistakes

  • Using Linformer’s \(E\) in a causal model. The compressed slots mix all positions, so the model reads the future. The loss looks great and generation is useless. Always run the leak test of Step 2: our leaky run reached a loss of 0.1685, far below every honest model, and 2.5444 at the one position where it could not read the future.
  • Benchmarking without synchronizing. GPU calls return before the work is done. Call torch.mps.synchronize() (or torch.cuda.synchronize()) before you stop the clock, warm up first, and report a median.
  • Comparing against a naive full attention. Your “linear” method beats a version that stores the \(n \times n\) matrix, but not a fused kernel. Compare against scaled_dot_product_attention on a backend with a fused kernel, and say which kernel ran.
  • Expecting GQA to speed up training. GQA does not change the \(n^2\) score work (102.2); it saves cache bytes and K/V projections. Measure it at decode time.
  • Expanding the cache with repeat_interleave at decode time. It copies the shared keys and values back to all query heads, so you read and write as many bytes as MHA, and more. Use a kernel that indexes the shared head (FlashAttention’s GQA support on CUDA, or the fold trick of decode.py), and check it by timing: on MPS in PyTorch 2.8, enable_gqa=True was as slow as the copy.
  • Stabilizing Performer features with a constant that does not cancel. Subtracting a separate maximum for each key, or adding a small epsilon to each feature, changes the weights, so the output no longer approaches softmax attention. A constant shared by all keys cancels in (102.7), but if it is a maximum over the whole sequence, as in our training code, it uses future keys: harmless in exact math (the leak test gives \(10^{-15}\)), but a very large later key can push early features to underflow, and it is not available during step-by-step generation. For decoding, use a fixed constant or a running maximum with rescaling of the state.
  • Too few random features, or features that are never redrawn. The error falls only like \(1/\sqrt{m}\) (Figure 2). The paper redraws features during training; we kept them fixed for determinism, which is a simplification.
  • Judging quality by validation loss, or by a fixed-offset copy. The honest variants reached losses from 1.6521 to 1.8272 on Shakespeare and all copied perfectly, but associative recall ranged from 13.7% to 99.99%. A copy at a fixed offset can be solved by position alone; test recall by content.

Interview questions

What does GQA save, and what does it not save?basic
It saves K/V heads: the K and V projections shrink by \(h / h_{kv}\), and so does the KV cache (102.3), and with it the bytes read per decode step. It does not save score computation: every query head still computes exact softmax scores against all earlier tokens, \(\approx 4 n^2 d\) FLOPs per layer (102.2). So GQA barely changes training or prefill time (on the CPU it took 0.80 to 0.92 of the time of full attention), but a decode step at 16k cached tokens was 2.64× faster with 8 instead of 32 K/V heads, with a kernel that does not copy the cache.
Why is the original Linformer not usable for a causal language model?basic
Its compressed keys \(EK\) are weighted sums over all \(n\) positions, so every slot contains information from tokens after the query. There is no causal mask you can apply to a slot. A model trained this way reads the future: in our leak test, changing tokens 40 to 63 moved outputs at positions 0 to 39 by up to 0.198, and its training loss fell far below an honest model. The paper evaluated it on encoder tasks, where this is allowed. Also, \(E\) has a fixed width \(n\), so it fixes the maximum length.
Explain FAVOR+ in three sentences. Why positive features?core
FAVOR+ writes \(\exp(q^{\top} k)\) as the expected dot product of random feature maps \(\phi(x) = m^{-1/2}\exp(Wx - \lVert x \rVert^2/2)\) with Gaussian \(W\) (102.6). Then attention can be computed as \(\phi(Q)(\phi(K)^{\top} V)\), which is linear in \(n\), and causally as running sums (102.7). Positive features keep every estimated weight and the normalizer positive; trigonometric (sin/cos) features can give negative or near-zero denominators, which makes training unstable, especially where true weights are small. Orthogonal directions reduce the variance further.
Your Performer GPT reaches a reasonable loss and passes a copy task, but fails associative recall. Explain with a formula.core
Validation loss on text is dominated by local, soft patterns, which a smooth kernel approximates well. A copy at a fixed offset can be found by position alone. Recall by content needs one attention weight near 1 on one exact earlier position, which needs a large logit \(q^{\top}k\). The variance of the FAVOR+ estimate is \(\frac{1}{m} e^{2q^{\top}k}(e^{\lVert q+k \rVert^2} - 1)\) (102.8): for large logits the relative error explodes, so the weight cannot be made sharp. In addition, all of the past lives in a fixed \(m \times d_h\) state (102.7); a fixed state cannot hold an arbitrary long sequence exactly. In our runs: Performer loss 1.8272 against 1.6725, copy accuracy 100% for both, recall accuracy 13.7% against 99.99%.
Every attention variant in this lab copied a 64-symbol string perfectly. Does that prove they can all recall exactly?core
No. In the copy task the source of every answer is exactly 65 positions back, so the model can find it by position: with learned position embeddings, “look 65 back” is a fixed pattern that a Performer kernel or a block summary with per-position weights can represent. Recall by content is different: the position of the matching key changes in every sequence, so the layer must compare the query with each key and put almost all weight on one. That is where the variants split at 3,000 steps: 99.99% for full attention and GQA, 73.6% for the causal Linformer, 13.7% for Performer, 9.4% for MQA. A good recall test varies where the answer is (associative recall, needle in a haystack at many depths).
A colleague shows Performer is 10× faster than “attention” at 16k tokens. What do you ask?core
Which attention: a naive layer that stores \(n \times n\) scores, or a fused kernel (FlashAttention, SDPA with a fused backend)? Was the GPU synchronized before stopping the clock, after a warm-up, with a median of several runs? Forward only or forward and backward? Causal or not (causal halves the exact cost but complicates linear attention)? Which \(m\), and at which \(n\) is the crossover? And what is the quality on a recall task, not only on loss? In our lab the answer to “faster than what” changed the conclusion: at 8k tokens on the GPU, Performer was 6.7× faster than the naive layer; against the fused CPU kernel it was 4.0× faster at 16k, but slower up to 2,048 tokens, and it used 4.4× more memory than fused exact attention at 16k.
Where is the crossover length at which Linformer or Performer becomes cheaper than exact attention?core
Compare FLOPs per layer: exact causal attention costs about \(2 n^2 d\), Linformer about \(8 n k d\) (two projections, scores and output), Performer about \(4 n m d\) to \(8 n m d\) depending on how the features and the intra-chunk part are counted. Setting them equal gives \(n^* \approx 4k\) for Linformer and \(n^* \approx 2m\) to \(4m\) for Performer: about 1,000 tokens for \(k = m = 256\). In practice the crossover is later, because the exact kernel is one highly tuned fused operation, while the approximations run many small operations with less efficient memory traffic. Measure it: in our benchmark the crossover against the fused CPU kernel was between 2,048 and 4,096 tokens for Performer, and about 2,048 for the causal Linformer.
Why does expanding K/V with repeat_interleave make GQA decode slow?core
Decoding is memory-bound: its time is roughly the bytes of the cache divided by the memory bandwidth. repeat_interleave materializes a full 32-head copy of the 8-head cache at every step: it reads the small cache, writes a cache as large as MHA’s, then the attention reads that again. So you pay more traffic than MHA itself. A GQA-aware kernel instead lets each query head index its shared K/V head. In our run at 16k tokens, one layer, batch 8: MHA 7.75 ms, GQA-8 with repeat_interleave 66.3 ms, GQA-8 with the fold trick of decode.py 2.93 ms. On MPS, enable_gqa=True was as slow as the copy (67.4 ms).
How would you turn a trained MHA model into a GQA model?core
The GQA paper “uptrains”: group the K/V heads, initialize each shared head with the mean of the K and V projection weights of the heads in its group, then continue pretraining for a small fraction of the original compute (they used 5%). Mean pooling worked better than picking one head or random initialization in their ablation. Without uptraining the model loses quality, because the query heads were trained against their own keys. [Certain: from the GQA paper]
The causal block Linformer got a lower validation loss than full attention in this lab. Does that make it better?advanced
No, it means character-level Shakespeare at 3,000 steps rewards a good local bias. The block version sees the last up to 8 characters exactly and the rest as smoothed summaries; for predicting the next character of English, the most useful information is local, and the summaries act like a cheap n-gram context that is easy to learn. Full attention can learn the same, but needs more steps. On associative recall, where the key must be found by content among 32 pairs, the block summaries reach only 73.6% at step 3,000, against 99.99% for full attention: each summary mixes two pairs. It catches up only after about 4,250 steps, so it learns the lookup much later. One benchmark that rewards locality cannot rank attention methods.
Why do production LLMs use GQA plus FlashAttention instead of linear attention, while some new models are hybrids?advanced
FlashAttention removed the \(n^2\) memory of exact attention, so the main remaining costs are \(n^2\) FLOPs in prefill and the KV cache in decode. GQA (or MLA) attacks the cache with almost no quality loss, while linear attention and low-rank projections lose exact recall, which users notice (retrieval in long documents, copying code, following references). Hybrid models (Jamba, and models mixing linear or state-space layers with a few full attention layers) keep a small number of exact layers for recall and use cheap layers elsewhere, which keeps most of the savings. [Likely: the reasons are the common explanation; the companies rarely publish the ablations]
How would you design a fair benchmark of attention variants?advanced
Same model size, data order, seed, optimizer and number of steps; report parameter counts. Time with warm-up, device synchronization and a median; report forward plus backward for training and a separate decode benchmark with a KV cache. Measure peak memory with a tool that sees the real allocations (or a fake-tensor tracer, and say so). Compare against the best exact kernel available on the hardware, and name it. Measure quality on loss and on tasks that need recall (copying, associative recall, needle in a haystack), across several lengths. Run the leak test. Report variance across seeds if differences are small.

Exercises

  1. Using (102.3), compute the KV cache of Qwen2.5-0.5B (24 layers, 2 K/V heads of size 64) for 32 sequences of 4,096 tokens in bf16. How much would MHA with 14 K/V heads need?
  2. Our causal Linformer uses blocks of \(B = n/k\). For \(n = 16{,}384\), which \(B\) minimizes the number of keys a query reads, \(n/B + B\)? How many keys is that?
  3. Run check.py with the Performer key constant computed per key (amax(-1) for keys too). Does the leak test still pass? Does the output still match exact attention as \(m\) grows? Explain.
  4. Train the Performer GPT with \(m = 32\) and \(m = 512\) on associative recall. Predict from (102.8) which one is closer to full attention, then check.
  5. Give the causal Linformer blocks of 2 tokens (\(k = 64\) for \(n = 128\)), so that each summary holds exactly one (key, value) pair. Predict what happens to its recall accuracy, and to the number of keys a query reads.
  6. Fit (102.10) to the MHA times of Figure 4 at 4,096, 8,192 and 16,384 tokens: find \(t_0\) and the bandwidth. Use them to predict the GQA-8 and MQA times at 16k, and compare with the measurements.
  7. Replace the learned block weights of the causal Linformer by a plain mean. Does the validation loss change? What does that say about what \(E\) learned?
  8. Continue the Performer recall run to 9,000 steps (STEPS=9000 python recall.py performer). Does it jump like the causal Linformer did, or stay low like MQA?
Answerscheck
1. \(2 \cdot 24 \cdot 2 \cdot 64 \cdot 2 = 12{,}288\) bytes per token; \(\times 4{,}096 \times 32 = 1{,}610{,}612{,}736\) bytes, about 1.61 GB. With 14 K/V heads: 7 times more, about 11.3 GB. 2. \(n/B + B\) is smallest at \(B = \sqrt{n} = 128\), giving \(128 + 128 = 256\) keys instead of up to 16,384. 3. A per-key constant does not cancel: each key’s features are scaled differently, so the weights change and the output no longer converges to exact attention. The leak test still passes, because each key’s constant uses only that key. 4. (102.8) says the error falls like \(1/\sqrt{m}\), so \(m = 512\) should recall better, but the sharpness problem remains; expect a gain, not 99%. (We did not run this; it is a prediction.) 5. A summary no longer mixes two pairs, so the model no longer has to untangle them: expect recall to rise toward full attention (a prediction, not measured). The price: a query now reads up to \(63 + 2\) keys instead of \(31 + 4\), and the cost moves toward full attention at this short length. 6. A line through the three points gives a slope of 0.003497 ms per MB, that is about 286 GB/s, and \(t_0 \approx 0.22\) ms. Prediction at 16k: GQA-8 \(0.22 + 536.9 \times 0.003497 \approx 2.09\) ms (measured 2.93), MQA \(\approx 0.45\) ms (measured 0.73). The model gets the order right; the folded kernel reads small caches at a lower bandwidth than the line assumes. 7. If the loss barely changes, \(E\) learned roughly uniform weights: the summaries are block averages. 8. We did not run this, so there is no answer from our data. If it stays low, that fits (102.8): sharp weights are what FAVOR+ estimates worst. If it jumps, the 3,000-step number measured learning speed, not capacity. Either way, report the whole curve.

Key takeaways

  • Put all variants behind one interface and change nothing else: same data order, seed, optimizer and steps. Then run the leak test before trusting any loss.
  • The original Linformer reads the future in a causal model (102.4); a causal version needs block summaries plus an exact local window (102.5).
  • FAVOR+ is unbiased (102.6) but its variance grows like \(e^{\lVert q+k \rVert^2}/m\) (102.8): fine for soft attention, poor for the sharp attention that recall needs.
  • Against a naive layer the approximations win memory by orders of magnitude; against a fused exact kernel most of that gap disappears (102.2). Always name the baseline kernel.
  • GQA keeps exact attention and cuts the KV cache by \(h/h_{kv}\) (102.3). It saves decode time, not training time, and only with a kernel that does not copy the cache.
  • Validation loss can look the same, or even better, while exact recall collapses. Test recall by content (associative recall), not only a fixed-offset copy.

Key formulas

\[ \text{FLOPs}_{\text{attn}} \approx 4 n^2 d, \qquad \text{KV bytes} = 2 L\, h_{kv}\, d_h\, n\, b, \qquad O_{\text{Lin}} = \softmax\!\Big(\tfrac{Q (EK)^{\top}}{\sqrt{d_h}}\Big) FV \]
\[ \text{Mem}_{\text{naive}} \approx 3 h n^2 \cdot 4 \text{ B}, \qquad t_{\text{step}} \approx t_0 + \frac{\text{KV bytes}}{\text{bandwidth}} \]
\[ \E\big[\phi(q)^{\top}\phi(k)\big] = e^{q^{\top}k}, \qquad y_t = \frac{S_t^{\top}\phi(q_t)}{z_t^{\top}\phi(q_t)}, \qquad \operatorname{Var} = \tfrac{1}{m} e^{2q^{\top}k}\big(e^{\lVert q+k\rVert^2} - 1\big) \]

References for this session

  1. Wang et al. (2020). Linformer: Self-Attention with Linear Complexity
  2. Choromanski et al. (2020). Rethinking Attention with Performers
  3. Ainslie et al. (2023). GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints
  4. Shazeer (2019). Fast Transformer Decoding: One Write-Head is All You Need
  5. Katharopoulos et al. (2020). Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
  6. Dao et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
  7. Dao (2023). FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning
  8. Jelassi et al. (2024). Repeat After Me: Transformers are Better than State Space Models at Copying
  9. Arora et al. (2023). Zoology: Measuring and Improving Recall in Efficient Language Models
  10. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  11. Karpathy (2023). nanoGPT (code)
  12. Llama Team, Meta (2024). The Llama 3 Herd of Models
  13. Karpathy (2015). Tiny Shakespeare dataset (char-rnn repository)
  14. PyTorch (2024). PyTorch documentation: scaled dot product attention (SDPA)