Learn: Linear & Sub-Quadratic Attention (& the SSM Turn)

What you're learning

Sparse attention kept softmax and just skipped entries of the $s\times s$ matrix. This lesson asks a more radical question: can we change the algorithm so the $s\times s$ matrix is never formed at all, buying true $O(s)$ time and — at inference — a constant-size state instead of a growing KV cache? Two families answer yes: (a) linearize attention with the kernel trick + associativity, and (b) replace attention with state-space / recurrent models (S4, Mamba). By the end you’ll be able to derive why associativity gives $O(s)$, write the SSM recurrence and its convolutional dual, explain Mamba’s selectivity, and reason about the recall/quality tax you pay for the constant state.

This closes Tier 2 of the Attention Mechanisms curriculum. It assumes lessons 01–06: you should be fluent in $S=Q{K}^{\top }/\sqrt{d}$, the softmax, the $O(s^2)$ wall, the KV cache, and the sparse/sliding-window tricks that only thin that matrix. Vocabulary follows the attention-glossary.

---

1. Learning map

graph TD
    A["The O(s²) wall<br/>(forms s×s scores)"] --> B["Sparse attn (lesson 06)<br/>keeps softmax,<br/>skips entries"]
    A --> C["Change the ALGORITHM<br/>→ never form s×s"]
    C --> D["(a) Linearize attention<br/>kernel trick + associativity"]
    C --> E["(b) Replace attention<br/>state-space / recurrent"]
    D --> D1["Linear Attention<br/>φ(Q)(φ(K)ᵀV) → O(s)<br/>Katharopoulos 2020"]
    D --> D2["Performers (FAVOR+)<br/>random-feature softmax"]
    D --> D3["Linformer<br/>low-rank K,V projection"]
    E --> E1["S4: structured SSM<br/>conv ⇄ recurrence duality"]
    E1 --> E2["Mamba: SELECTIVE SSM<br/>input-dependent B,C,Δ<br/>→ content-based routing"]
    D1 --> F["Constant state,<br/>linear time"]
    E2 --> F
    F --> G["⚠ recall gap<br/>vs full softmax attention"]
    G --> H["Hybrids: interleave<br/>attention + SSM/linear"]

    style A fill:#a44,color:#fff
    style D1 fill:#44a,color:#fff
    style E2 fill:#483,color:#fff
    style G fill:#a83,color:#fff
    style H fill:#666,color:#fff

---

2. Intuition: don’t skip the matrix — dissolve it

Sparse attention (lesson 06) is a bookkeeping fix. The operation is still softmax attention; you just decide, ahead of time, which query–key pairs are allowed to interact so you compute fewer of the $s^2$ entries. The moment you want a token to potentially see any other token, you’re back to the quadratic.

The deeper move is to notice why attention is quadratic in the first place. The culprit is the softmax nonlinearity sitting between $Q$ and $V$:

$O=\underset{\text{an }s\times s\text{ object}}{\underbrace{\mathrm{softmax}(Q{K}^{\top })}}V.$

Because softmax couples an entire row of scores together (it normalizes across all keys), you must materialize each $s\times s$ row before you can multiply by $V$. That single nonlinearity is the reason you can’t reassociate the product. Kill or replace it and two doors open:

• (a) Linearize. Approximate $\exp (q^{\top }k)$ by a separable similarity $\varphi (q{)}^{\top }\varphi (k)$. Now the score is a plain inner product of features, and matrix multiplication is associative: compute $\varphi (K{)}^{\top }V$ first (a small $d\times d$ object that summarizes the whole past), then multiply by $\varphi (Q)$. The $s\times s$ matrix never exists. This also exposes a recurrent form — attention is an RNN with a matrix-valued hidden state.¹

• (b) Replace. Drop the attention framing entirely and use a linear recurrence: carry a fixed-size hidden state $h_t$ forward one token at a time, $h_t=\bar{A}{h}_{t-1}+\bar{B}{x}_t$. This is a state-space model (SSM). It’s $O(s)$ by construction and, remarkably, when the recurrence is linear time-invariant it can be unrolled into a single long convolution and trained in parallel like a Transformer. S4 made this competitive; Mamba made the dynamics input-dependent and recovered the content-based routing that made attention special in the first place.²³

The unifying picture

Full attention keeps a lossless but growing memory of the past — the KV cache literally stores every token’s K and V. Linear attention and SSMs keep a fixed-size, lossy summary — a $d\times d$ (or $N\times d$) state that every new token updates in place. That is the whole trade in one sentence: unbounded exact recall at $O(s)$ memory vs. bounded compressed recall at $O(1)$ memory.

---

3. The math

3.1 Linear attention: the kernel trick + associativity

Write softmax attention for a single output row $i$ explicitly, exposing the exponential kernel:

$o_i=\frac{{\sum }_j\exp (q_i^{\top }{k}_j)v_j}{{\sum }_j\exp (q_i^{\top }{k}_j)}.$

The generalization is to replace $\exp (q_i^{\top }{k}_j)$ with a kernel $\kappa (q_i,k_j)=\varphi (q_i{)}^{\top }\varphi (k_j)$ for some feature map $\varphi :{\mathbb{R}}^d\to {\mathbb{R}}^r$ with non-negative entries (so the weights stay positive).¹ Katharopoulos et al. use the simple, cheap map $\varphi (x)=\mathrm{elu}(x)+1$. Substituting:

$o_i=\frac{{\sum }_j(\varphi (q_i{)}^{\top }\varphi (k_j))v_j}{{\sum }_j\varphi (q_i{)}^{\top }\varphi (k_j)}=\frac{\varphi (q_i{)}^{\top }{\sum }_j\varphi (k_j)v_j^{\top }}{\varphi (q_i{)}^{\top }{\sum }_j\varphi (k_j)}.$

The last equality is the whole trick: because $\varphi (q_i)$ no longer sits inside a nonlinearity, we pulled it out of the sum. Define the two accumulators that do not depend on $i$:

$S={\sum }_j\varphi (k_j)v_j^{\top }\in {\mathbb{R}}^{r\times d_v},z={\sum }_j\varphi (k_j)\in {\mathbb{R}}^r.$

Then every output is just $o_i=\frac{\varphi (q_i{)}^{\top }S}{\varphi (q_i{)}^{\top }z}$. In matrix form (bidirectional case):

$\boxed{O=(\varphi (Q)(\varphi (K{)}^{\top }V))\oslash (\varphi (Q)(\varphi (K{)}^{\top }1))}$

where $\oslash$ is row-wise division. Read the parenthesization: computing $\varphi (K{)}^{\top }V$ first costs $O(sr{d}_v)$ and produces an $r\times d_v$ matrix; multiplying by $\varphi (Q)$ costs another $O(sr{d}_v)$. Total is linear in $s$ — the $s\times s$ matrix is gone. Contrast with softmax, where the nonlinearity forces the left-to-right order $(\mathrm{softmax}(Q{K}^{\top }))V$ and $O(s^2)$.

The recurrent form (causal case). For autoregressive models, token $t$ may only sum over $j\le t$, so the accumulators become running sums — a linear recurrence with a matrix-valued state:

$S_t=S_{t-1}+\varphi (k_t)v_t^{\top },z_t=z_{t-1}+\varphi (k_t),o_t=\frac{\varphi (q_t{)}^{\top }{S}_t}{\varphi (q_t{)}^{\top }{z}_t}.$

This is exactly why the paper is titled “Transformers are RNNs”: a causal linear-attention layer is an RNN whose hidden state is the fixed $r\times d_v$ matrix $S_t$. At inference it needs constant memory and constant compute per token — no KV cache that grows with $s$.¹

The quality gap is real

$\varphi (q{)}^{\top }\varphi (k)$ with a cheap $\varphi$ is a poor approximation of $\exp (q^{\top }k)$: it can’t produce the sharp, spiky, near-one-hot distributions that softmax attention uses for precise retrieval, and cramming all history into a fixed $r\times d_v$ state is lossy. Vanilla linear attention consistently underperforms softmax attention on language modeling and especially on tasks needing exact recall / copying / in-context lookup. Much follow-up work (feature maps, gating, normalization, delta-rule updates) narrows but has not fully closed this gap. Treat “linear attention = free lunch” as a misconception.

3.2 Two cousins, one line each

• Performers (FAVOR+). Instead of a heuristic $\varphi$, use random features that make $\varphi (q{)}^{\top }\varphi (k)$ an unbiased estimator of the softmax kernel $\exp (q^{\top }k)$, with positive features for stability. This keeps the $O(s)$ associativity trick while provably approximating true softmax attention.⁴
• Linformer. Observe that the attention matrix is empirically low-rank, then project $K$ and $V$ along the sequence dimension down to a small $k\ll s$ before attending: $O(sk)\approx O(s)$. Cheap and effective, but the projection mixes across time, so it’s awkward to make strictly causal.⁵

3.3 State-space models: S4 and the conv ⇄ recurrence duality

A continuous-time linear state-space model maps a 1-D input signal $x(t)$ to output $y(t)$ through a hidden state $h(t)\in {\mathbb{R}}^N$:

$h^{\prime }(t)=Ah(t)+Bx(t),y(t)=Ch(t).$

To use it on a token sequence we discretize with a step size $\Delta$ (zero-order hold), giving matrices $\bar{A},\bar{B}$:

$\bar{A}=\exp (\Delta A),\bar{B}=(\Delta A{)}^{-1}(\exp (\Delta A)-I)\Delta B,$

and a clean linear recurrence:

$\boxed{h_t=\bar{A}{h}_{t-1}+\bar{B}{x}_t,y_t=C{h}_t}$

Here is the magic that made SSMs trainable at scale. When $A,B,C,\Delta$ are constant across time (a linear time-invariant, LTI, system), unrolling the recurrence gives $y_t={\sum }_{j\ge 0}C{\bar{A}}^j\bar{B}{x}_{t-j}$ — i.e. $y$ is a convolution of $x$ with a single (very long) kernel:

$\bar{K}=(C\bar{B},C\bar{A}\bar{B},C{\bar{A}}^2\bar{B},\dots ,C{\bar{A}}^{s-1}\bar{B}),y=x\ast \bar{K}.$

This is the duality: train as a convolution (fully parallel over the sequence, computed in $O(s\log s)$ via FFT), then run inference as a recurrence (one step at a time, $O(1)$ state). The remaining problem was that a naive ${\bar{A}}^j$ either explodes, vanishes, or is too expensive; S4’s contribution was a structured parameterization of $A$ (a diagonal-plus-low-rank / HiPPO form) that makes the long kernel both stable and cheap to compute, letting SSMs finally beat Transformers on very long-range benchmarks like Long Range Arena.²⁶

Why constant state beats a KV cache for long sequences

An SSM’s hidden state $h_t$ has a fixed size $N$ (per channel), no matter how long the sequence. Generation is a fixed-cost matrix–vector update per token, and memory never grows with context — the opposite of attention, whose KV cache grows linearly with $s$ (lesson 05) and dominates long-context inference. That constant-state, linear-time profile is the reason SSMs became the serious challenger to attention for very long sequences.

3.4 Mamba: selectivity recovers content-based routing

S4’s Achilles heel is exactly what made it efficient: LTI means the dynamics are the same at every position, so the model cannot decide, based on the current token’s content, what to remember or ignore. Softmax attention’s superpower is precisely this content-dependent routing. Mamba closes the gap by making the SSM parameters functions of the input — a selective SSM (dubbed S6):³

$B_t=s_B(x_t),C_t=s_C(x_t),{\Delta }_t=\mathrm{softplus}(s_{\Delta }(x_t)),$

with $A$ a learned parameter whose effective discretized form ${\bar{A}}_t=\exp ({\Delta }_{t}A)$ is now input-dependent through ${\Delta }_t$. Intuitively: a large ${\Delta }_t$ makes the model “pay attention” and write the current token strongly into state (and reset old state via the decay), while a small ${\Delta }_t$ makes it “coast,” ignoring an unimportant token. This is content-based gating — a selective forget/keep decision per token — which vanilla linear attention (fixed $\varphi$, no gating) simply does not have.

The cost of selectivity: once $B_t,C_t,{\bar{A}}_t$ vary with $t$, the system is no longer LTI, so the convolutional form is gone. Mamba recovers parallel training with a hardware-aware parallel scan (an associative scan over the recurrence, kept in fast SRAM), giving linear-time training and constant-state, linear-time inference — matching or beating Transformers of similar size on language, audio, and genomics while scaling far better in sequence length.³

Selectivity narrows the recall gap — it doesn't erase it

Mamba is dramatically better than S4/linear attention at content-based tasks, but its state is still a fixed-size compression of the past. On tasks that need verbatim recall of arbitrary earlier tokens (copying, associative recall, long-context retrieval / “needle in a haystack”), pure SSMs still trail full attention, whose KV cache stores every token losslessly. This is the empirical driver behind hybrids. [recent]

3.5 The delta-rule wave: DeltaNet → Gated DeltaNet → KDA

Vanilla linear attention has a fatal flaw: its state update is purely additive, $S_t=S_{t-1}+\varphi (k_t)v_t^{\top }$. Write two similar keys and their values superimpose in $S$ — there’s no way to overwrite or forget, so the fixed-size state saturates and recall collapses. The delta rule fixes this and is the engine behind the strongest 2024–2026 linear-attention models.⁷

DeltaNet treats the state as a fast weight and applies one step of online gradient descent per token: before writing $v_t$, subtract the value the state currently associates with $k_t$:

$S_t=S_{t-1}+{\beta }_t{k}_t(v_t-S_{t-1}^{\top }{k}_t{)}^{\top }=(I-{\beta }_t{k}_t{k}_t^{\top })S_{t-1}+{\beta }_t{k}_t{v}_t^{\top }$

The $(I-{\beta }_t{k}_t{k}_t^{\top })$ factor erases the old association before writing the new one — error-correcting associative memory that additive linear attention lacks.⁷

Gated DeltaNet (GDN) adds Mamba-2-style data-dependent forgetting — a scalar decay ${\alpha }_t\in (0,1)$ — on top of the delta rule:⁸

$S_t={\alpha }_t(I-{\beta }_t{k}_t{k}_t^{\top })S_{t-1}+{\beta }_t{k}_t{v}_t^{\top }$

so the state both forgets (via ${\alpha }_t$) and corrects (via the delta term). GDN is the linear layer in Qwen3.8-Next’s hybrid (3 GDN : 1 full attention).⁹

Kimi Delta Attention (KDA) — the frontier variant, used in Kimi K3 (2026) — makes the forget gate channel-wise: ${\alpha }_t\in (0,1{)}^{d_k}$ is a vector, one decay per key channel, so different feature dimensions retain memory over different timescales:¹⁰

$S_t=(I-{\beta }_t{k}_t{k}_t^{\top })\mathrm{Diag}({\alpha }_t)S_{t-1}+{\beta }_t{k}_t{v}_t^{\top },{\tilde{o}}_t=S_t^{\top }{q}_t$

K3 adds two practical tweaks: a lower-bounded decay ${\alpha }_t=\exp (g_{\min }\sigma (e^A{z}_t))$ with $g_{\min }=-5$ (keeps the chunkwise rescaling factor $1/\Gamma$ inside BF16 range so all tiles run as dense Tensor-Core matmuls), and a full-rank data-dependent output gate $y_t=W_o[\sigma (W_g{x}_t)\odot \mathrm{RMSNorm}({\tilde{o}}_t)]$.¹⁰ Like all these methods it keeps a constant-size state $S\in {\mathbb{R}}^{d_k\times d_v}$ per head (not a growing KV cache) and trains via a chunkwise-parallel form. Details: delta-rule, gated-deltanet, kda.

Why the delta rule matters now

Additive linear attention traded recall for efficiency and lost. The delta rule + gating recovered enough recall that these are no longer toy alternatives — they’re the linear half of the hybrid models frontier labs actually ship (§3.6). The state is still constant-size, so inference is $O(1)$ memory per step — the property softmax attention can never have.

3.6 Hybrids: get recall and efficiency

Since attention excels at exact recall and SSM/linear layers excel at cheap long-range mixing, the pragmatic answer is to interleave them: mostly linear/delta layers for throughput and constant-state efficiency, with a few full-attention layers to restore precise retrieval. This is now the frontier default, not a research curiosity:

• Kimi K3 (2026): a 3 KDA : 1 Gated-MLA block repeated through 93 layers (69 KDA + 24 MLA), with NoPE on the MLA layers — KDA’s gating supplies position implicitly — trained natively at 1M context.¹⁰ Only the 24 MLA layers keep a growing (latent-compressed) cache; the 69 KDA layers keep fixed-size states.
• Qwen3.8-Next (2026): a 3 GDN : 1 full-attention hybrid; the full-attention layers are further sparsified by QSA (qwen-sparse-attention).⁹
• Earlier/other lines: Jamba interleaves Transformer + Mamba blocks with MoE [verify]; DeepMind’s Griffin/Hawk mix gated linear recurrences with local attention [verify].¹¹

The recurring finding: a small fraction of full-attention layers recovers most of the recall a linear-only model loses, at a large efficiency win. The 2026 frontier converged on ~1 full-attention layer per 3–4 linear/delta layers.

Quiz (retrieval): Why does the associativity $(\varphi (Q)(\varphi (K{)}^{\top }V))$ give $O(s)$ time, while softmax attention is stuck at $O(s^2)$?

Answer

Matrix multiplication is associative, so we can multiply $\varphi (K{)}^{\top }V$ first. That contracts the sequence dimension immediately, producing an $r\times d_v$ summary of the entire past whose size is independent of $s$; multiplying by $\varphi (Q)$ then costs $O(sr{d}_v)$ — linear in $s$. The $s\times s$ matrix is never materialized. Softmax attention can’t do this because the softmax nonlinearity sits between $Q$ and $K$: you must form and normalize each full score row before multiplying by $V$, forcing the order $(\mathrm{softmax}(Q{K}^{\top }))V$ and $O(s^2)$ work + memory.

Quiz (retrieval): What does Mamba's selectivity add over vanilla linear attention, and what does it cost algorithmically?

Answer

Vanilla linear attention uses a fixed feature map $\varphi$ and a fixed additive state update — the dynamics are the same regardless of token content, so it can’t decide what to remember or forget. Mamba makes $B_t,C_t,{\Delta }_t$ (and hence the effective ${\bar{A}}_t=\exp ({\Delta }_{t}A)$) functions of the input, giving per-token content-based gating: large ${\Delta }_t$ writes/keeps, small ${\Delta }_t$ ignores. That recovers attention-like content routing. The cost: input-dependent parameters make the system non-LTI, so the parallel convolutional form is lost; Mamba instead trains via a hardware-aware parallel (associative) scan.

---

4. Illustration: three ways to move information

The contrast is entirely about what object you form and how big your state is.

flowchart TB
    subgraph SM["Softmax attention — O(s²), forms s×s"]
        direction LR
        Q1["Q (s×d)"] --> M1["QKᵀ<br/>(s×s) MATERIALIZED"]
        K1["K (s×d)"] --> M1
        M1 -->|"softmax"| A1["A (s×s)"]
        A1 --> O1["A·V (s×d)"]
        V1["V (s×d)"] --> O1
    end
    subgraph LA["Linear attention — O(s), associativity"]
        direction LR
        K2["φ(K) (s×r)"] --> S2["φ(K)ᵀV<br/>(r×d) tiny state"]
        V2["V (s×d)"] --> S2
        S2 --> O2["φ(Q)·(φ(K)ᵀV)<br/>(s×d)"]
        Q2["φ(Q) (s×r)"] --> O2
    end
    subgraph SSM["SSM recurrence — O(s), constant state"]
        direction LR
        X3["x₁"] --> H1["h₁ = Āh₀+B̄x₁"]
        H1 --> H2["h₂ = Āh₁+B̄x₂"]
        H2 --> H3["h₃ = Āh₂+B̄x₃"]
        H1 --> Y1["y₁=Ch₁"]
        H2 --> Y2["y₂=Ch₂"]
        H3 --> Y3["y₃=Ch₃"]
    end

    style M1 fill:#a44,color:#fff
    style S2 fill:#44a,color:#fff
    style H2 fill:#483,color:#fff

The red block is the quadratic object you’re trying to avoid. Linear attention replaces it with a tiny $r\times d$ summary matrix computed once; the SSM replaces it with a hidden state $h_t$ threaded through the sequence — no per-pair object exists at all. In both alternatives, inference carries only a fixed-size state forward.

Figure: at generation time, attention’s KV cache grows linearly with context while an SSM’s (or linear-attention’s) recurrent state stays constant — the crux of why sub-quadratic models win on very long sequences.

---

5. FLOPs & memory

Take batch $b$, sequence $s$, model dim $d$; for linear attention let the feature dim be $r$, and for an SSM let the state size be $N$ (per channel). Count a multiply-add as 2 FLOPs.

Model	Train/prefill time	Materialized memory	Inference state (per layer)	Per-token decode cost
Softmax attention	$O(b{s}^{2}d)$	$O(b{s}^2)$ scores (or $O(bs)$ w/ FlashAttention, still $O(s^2)$ compute)	$O(sd)$ KV cache — grows with $s$	$O(sd)$ (attends to all past)
Linear attention	$O(bsrd)$	$O(brd)$ state	$O(rd)$ — constant in $s$	$O(rd)$
S4 (LTI SSM)	$O(bsNd)$ scan, or $O(bds\log s)$ FFT-conv	$O(bNd)$	$O(Nd)$ — constant in $s$	$O(Nd)$
Mamba (selective)	$O(bsNd)$ parallel scan	$O(bNd)$	$O(Nd)$ — constant in $s$	$O(Nd)$

Two headlines:

1. Time. Every sub-quadratic model is linear in $s$ for training/prefill (Mamba via parallel scan, S4 via FFT convolution or scan), versus attention’s $O(s^2)$. Double the context, double — not quadruple — the compute.
2. Inference memory is the bigger prize. Attention’s KV cache grows as $O(sd)$ and is the binding constraint for long-context serving (lesson 05, 12-llm-inference-systems). Linear attention and SSMs carry a fixed-size state ($O(rd)$ or $O(Nd)$), independent of how much context has streamed by — constant memory and constant per-token latency during generation.

The tax you pay for the constant state

That fixed-size state is a lossy compression of unbounded history. Empirically this shows up as a recall gap: pure linear-attention and SSM models underperform full attention on exact-copy, associative-recall, and long-context retrieval tasks, precisely because they cannot store every past token losslessly the way a KV cache does. [verify] the exact magnitude — it’s task- and scale-dependent and actively researched — but the direction is robust. This is why frontier long-context systems increasingly go hybrid rather than pure-SSM. [recent]

Problem: KV cache vs. SSM state at long context

A model serves a single stream ($b=1$) with $d=4096$, 32 layers, fp16 (2 bytes). Compare the per-token state of (a) full attention at $s=128\text{k}$ context vs. (b) a Mamba layer with state size $N=16$.

Solution. (a) KV cache stores one K and one V of size $d$ per token per layer: $2\cdot s\cdot d\cdot \text{layers}\cdot 2\text{B}=2\cdot 128,000\cdot 4096\cdot 32\cdot 2\approx 6.7\times 10^{10}$ B $\approx$ 67 GB — and it grows with every generated token. (b) A Mamba state is $N\cdot d$ per layer (roughly): $16\cdot 4096\cdot 32\cdot 2\approx 1.7\times 10^8$ B $\approx$ 0.17 GB, and it is constant regardless of context length. Two-plus orders of magnitude, and the gap widens as $s$ grows — the whole economic case for sub-quadratic models at long context.

Problem: when is linear attention actually cheaper than softmax?

Ignoring the projections, softmax attention’s core is $\approx 4b{s}^{2}d$ FLOPs (lesson 01); linear attention’s is $\approx 4bsrd$. At what sequence length does linear attention win, and what’s the catch?

Solution. Set $4b{s}^{2}d>4bsrd\Rightarrow s>r$. So linear attention is cheaper once the sequence is longer than the feature dimension $r$ — which is essentially always for long context (typically $r\sim d$ or smaller). The catch is quality, not FLOPs: at the same parameter count, the fixed $r\times d$ state loses the exact-recall ability of softmax’s $O(s^2)$ interactions, so the FLOP win is only free if your task tolerates the recall gap. This asymmetry — cheap but lossy — is exactly why the field moved toward selective SSMs (Mamba) and hybrids rather than plain linear attention.

---

6. Read next / primary sources

• Linear attention: Katharopoulos, Vyas, Pappas, Fleuret, “Transformers are RNNs” (2020)¹ — read §3 for the kernel formulation and §3.2–3.3 for the recurrent form. This is the cleanest derivation of the associativity trick.
• State-space models: Gu, Goel, Ré, “Efficiently Modeling Long Sequences with Structured State Spaces” (S4) (2021)² for the conv⇄recurrence duality and the structured $A$; then Gu & Dao, “Mamba” (2023)³ §3 for selectivity (S6) and §3.3 for the hardware-aware scan.
• Approximation cousins: skim Performer⁴ (§2, FAVOR+) and Linformer⁵ (§3, low-rank) — one section each is enough to place them.

Ask your teacher

Want the delta-rule / gated-linear-attention lineage (that unifies linear attention and modern RNNs like RWKV, RetNet, GLA), the associative-scan math in full, or a worked Mamba forward pass? Ask — I’m your teacher for this course and can go as deep as you like, or build you a harder problem set.

7. What’s next

• 08-attention-in-vits-and-vlms — Tier 3 opens: how attention adapts to images and multimodal inputs (ViTs, patchification, cross-attention, vision–language models).
• Back to 06-sparse-and-sliding-window — the “keep softmax, thin the matrix” approach this lesson contrasts against. Holding both in mind (skip entries vs. dissolve the matrix) is the right mental model for the efficiency frontier.

---

References

Reference: attention-glossary | Topic: attention-mechanisms | Filed: 2026-09-10

Footnotes

1. Katharopoulos, Vyas, Pappas, Fleuret, “Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention” — arXiv:2006.16236 (2020). Introduces the kernel-feature-map linearization $\varphi (q{)}^{\top }\varphi (k)$, the associativity trick for $O(s)$ attention, the feature map $\varphi (x)=\mathrm{elu}(x)+1$, and the causal recurrent (RNN) form with matrix-valued state. [established] ↩ ↩² ↩³ ↩⁴

2. Gu, Goel, Ré, “Efficiently Modeling Long Sequences with Structured State Spaces (S4)” — arXiv:2111.00396 (2021). Structured (diagonal-plus-low-rank / HiPPO) SSM parameterization; the convolution⇄recurrence duality; strong Long Range Arena results. [established] ↩ ↩² ↩³

3. Gu & Dao, “Mamba: Linear-Time Sequence Modeling with Selective State Spaces” — arXiv:2312.00752 (2023). Selective SSM (S6) with input-dependent $B,C,\Delta$; hardware-aware parallel scan; linear-time training and constant-state inference matching/beating Transformers at similar scale. [recent] ↩ ↩² ↩³ ↩⁴

4. Choromanski et al., “Rethinking Attention with Performers” — arXiv:2009.14794 (2020). FAVOR+ uses positive random features to give an unbiased, low-variance estimate of the softmax kernel, retaining linear time/space. [established] ↩ ↩²

5. Wang, Li, Khabsa, Fang, Ma, “Linformer: Self-Attention with Linear Complexity” — arXiv:2006.04768 (2020). Projects K and V along the sequence dimension to a small $k$, exploiting the empirical low-rank structure of the attention matrix for $O(s)$ cost. [established] ↩ ↩²

6. Gu, Dao, Ermon, Rudra, Ré, “HiPPO: Recurrent Memory with Optimal Polynomial Projections” — arXiv:2008.07669 (2020). The initialization theory behind S4’s $A$ matrix (optimal online function approximation / long-range memory). [established] ↩

7. The delta rule as a linear-attention update: Schlag, Irie, Schmidhuber, “Linear Transformers Are Secretly Fast Weight Programmers” — arXiv:2102.11174 (2021); parallel/chunkwise training in Yang et al., “Parallelizing Linear Transformers with the Delta Rule over Sequence Length” — arXiv:2406.06484 (2024). See delta-rule. [established] ↩ ↩²

8. Yang, Kautz, Hatamizadeh, “Gated Delta Networks: Improving Mamba2 with Delta Rule” (GDN) — arXiv:2412.06464 (2024) [verify id]. Data-dependent scalar decay ${\alpha }_t$ combined with the delta rule. See gated-deltanet. [recent] ↩

9. Qwen Team (Alibaba), “On the Design of Qwen3.8-Next Architecture” — arXiv:2608.30320 (2026). 3 Gated-DeltaNet : 1 full-attention hybrid; full-attention layers sparsified by QSA. Transcribed from the primary PDF (§2.1). See qwen-sparse-attention, 2026-09-12-qwen3.8-next. [recent] ↩ ↩²

10. Kimi Team (Moonshot AI), “Kimi K3: Open Frontier Intelligence” — arXiv:2607.24653 (2026); KDA originates in “Kimi Linear: An Expressive, Efficient Attention Architecture” — arXiv:2510.26692 (2025). Channel-wise-gated delta-rule linear attention; K3’s bounded-sigmoid decay ($g_{\min }=-5$) and full-rank output gate; 3 KDA : 1 Gated-MLA hybrid with NoPE at 1M context. Transcribed from the primary PDF (§2.1). See kda, 2026-09-12-kimi-k3. [recent] ↩ ↩² ↩³

11. Jamba (AI21 Labs), “Jamba: A Hybrid Transformer-Mamba Language Model” — arXiv:2403.19887 (2024). Interleaves Transformer and Mamba layers with MoE for long context at reduced KV-cache cost. Exact layer ratios/benchmarks [verify]. DeepMind’s Griffin/Hawk (arXiv:2402.19427) similarly mix gated linear recurrences with local attention [verify]. [recent] ↩