Linear Transformers as Fast Weight Programmers

Chapter 1: Attention Without Softmax

Chapter 0 promised a mechanism that reorganizes attention from “compare against everything” into “maintain a running summary.” This chapter does that transformation, in full, using nothing but algebra you already know: matrix multiplication is associative, meaning you can group the terms in a product however you like without changing the answer. That one fact is the entire trick.

A reminder of what associativity means, in the simplest possible setting, before applying it to matrices: for ordinary numbers, (2×3)×4 = 2×(3×4) — both equal 24, regardless of which multiplication happens first. The same freedom to regroup holds for matrix and vector products, as long as the order of the factors left to right doesn't change (matrix multiplication is associative but, unlike ordinary numbers, generally not commutative — swapping the order of two matrices usually changes the answer, only regrouping is free). That distinction — associative but not commutative — will matter again, sharply, in Chapter 6.

Standard attention, written explicitly

Start from the attention every prior session has used. For output position i, with query q_i, and keys/values k₁…k_i, v₁…v_i from every token processed so far:

where κ(k, q) = exp(k·q) is the softmax kernel — a function that turns a raw dot product into a positive number, so that after dividing by their sum, every token's contribution is a proper weight between 0 and 1 that sums to exactly 1 across the row. This is exactly softmax(QK^T)V, just written per-token with the normalization made explicit rather than hidden inside a softmax call.

The one substitution that changes everything

The exponential is what breaks the associativity trick — you cannot factor exp(k·q) into separate functions of k and q multiplied together. So replace it. Pick some function φ that maps vectors into a new space where the dot product there approximates the original kernel:

If this move looks familiar from classical machine learning, that's not an accident. Support Vector Machines made exactly this substitution famous decades earlier under the name the kernel trick: replacing an expensive or infinite-dimensional similarity function with an explicit feature map whose dot product approximates it. The direction is usually the opposite of what's happening here, though — SVMs typically use the kernel trick to avoid ever computing φ explicitly (because φ would map into a huge or infinite space), working entirely through the kernel function instead. Here, the whole point is the reverse: compute φ explicitly, in a modest, finite dimension, specifically because having explicit feature vectors is what unlocks the associativity trick below. Same underlying idea, opposite reason for using it.

Substitute κ′ into the attention formula above. The numerator becomes ∑_j v_j (φ(k_j)^Tφ(q_i)) — and here is the associativity move: because q_i is the same vector multiplying every term in the sum, you can pull it outside the sum entirely and group it with each v_j first instead:

where ⊗ is the outer product — two vectors combined into a matrix, one column per input dimension, rather than collapsed into a single number the way a dot product would. That parenthesized sum no longer depends on q_i at all. It only depends on everything up to position i. Give it a name:

and the whole layer collapses to:

From a sum to a recurrence

S_i is a running sum. Running sums update by adding one new term, which means you never need to recompute the whole sum from scratch — you only need what you had a moment ago, plus the newest piece:

This is a recurrent neural network — a model that carries forward a fixed-size hidden state and updates it one input at a time — except the hidden state S_i here is not a vector, the way an old-school RNN's hidden state was. It's a matrix, exactly d_value × d_dot in size, and it never grows no matter how many tokens have been processed. That is the constant-memory promise from Chapter 0, delivered: S_i costs the same number of bytes at token 10 and at token 10 million.

This matrix-valued generalization is worth pausing on, since it's easy to skim past. Classic RNNs like LSTMs carry forward a hidden state that's a single vector, typically hundreds to a few thousand numbers. Linear attention's state is a full matrix, d_value×d_dot numbers — for a 128-dimensional head, that's already 16,384 numbers, two full orders of magnitude more capacity than a typical LSTM hidden state. That larger, matrix-shaped state is precisely what makes the fast-weight-programmer framing (Chapter 2) the more natural lens than “just another RNN” — a single vector doesn't naturally support the outer-product write-and-read operations this session builds everything else on top of.

The simplification almost everyone actually uses

φ needs to satisfy a technical property (its output must be positive, so the ratio still behaves like an attention weight) if you want the normalization in Chapter 0's formula to mean something. But a large and important slice of practice — including the delta-rule models this lesson is building toward — drops the normalization entirely and sets φ to the identity function, recovering the plainest possible version:

No kernel, no normalization, no query projection needed even — just raw keys, values, and queries, wired through outer products. Every worked numeric example for the rest of this session uses exactly this form, because it's the version that makes the underlying arithmetic checkable by hand, and it's also, as Chapter 2 shows, the version with a startling second identity hiding inside it.

If you do want a φ: why ELU+1, not the simpler ReLU

For readers who do want the general kernelized form (Chapter 0's positivity-preserving version, not the identity simplification above), the most common practical choice is ELU(x)+1 rather than the even simpler ReLU(x). Both satisfy the positivity requirement — ReLU clips negatives to exactly zero, ELU+1 smoothly approaches zero from above. The reason to prefer ELU+1 is about training, not inference: ReLU's gradient is exactly zero for every negative input, meaning any key or query component that lands on the negative side of zero contributes nothing to learning at all — a “dead” direction the model can never recover useful gradient signal through. ELU's gradient stays nonzero (though small) everywhere, including deep into negative territory, so gradient descent can still nudge those components rather than abandoning them entirely. It's a small implementation choice, but it's the kind of choice that differentiates a linear-attention variant that trains reliably from one that quietly loses gradient signal in half of its input space.

Two ways to compute the same output, verified against each other

Chapter 1's callout mentions a “parallel form” without proving it agrees with the recurrent form. Check it by hand on a tiny 3-token example, using the identity-φ simplification from above (raw keys, values, queries, no kernel). Keys and values: k₁=(1,0), v₁=(2,0); k₂=(0,1), v₂=(0,3); k₃=(1,1), v₃=(1,1). Query with q₃=(1,1), asking for the output at position 3.

Recurrent form — build the state step by step, output only what's needed at step 3:

Parallel form — compute the same output directly as a masked attention sum, no running state at all: o₃ = ∑_j=1³ v_j(k_j· q₃). The three dot products: k₁·q₃=1, k₂·q₃=1, k₃·q₃=2.

Identical, exactly. This is not a coincidence — it's the same associativity argument from earlier in this chapter, just run in reverse: the recurrent form built the state up token by token, while the parallel form computed the equivalent masked weighted sum all at once. Training uses the parallel form (one large matmul, GPU-friendly); a deployed model generating token by token uses the recurrent form (cheap, constant-size state). Both are the same function, computed two different ways — and this equivalence is the entire reason linear attention can be fast to train and fast to run simultaneously, a combination the RNN era never had.

python
import torch

k = torch.tensor([[1.,0.],[0.,1.],[1.,1.]])
v = torch.tensor([[2.,0.],[0.,3.],[1.,1.]])
q3 = torch.tensor([1.,1.])

# recurrent form: build S step by step
S = torch.zeros(2,2)
for i in range(3):
    S = S + torch.outer(v[i], k[i])
print(S @ q3)                                   # tensor([4., 5.])

# parallel form: one masked matmul, no state at all
scores = k @ q3                                       # dot products against q3
print((scores.unsqueeze(1) * v).sum(dim=0))  # tensor([4., 5.]) -- identical

Both print the same two numbers. This is the check every production linear-attention implementation relies on implicitly: train with the fast parallel form, deploy with the cheap recurrent form, and never worry that the two paths might disagree, because the associativity argument guarantees they can't.

What φ is actually allowed to be

Chapter 1 asserted φ needs a positive codomain for the normalization to behave like real attention weights, and separately showed that dropping normalization entirely lets φ be the identity. There's a second property worth naming, because Chapter 3 depends on it directly: the dimensionality of φ's output, d_dot, is a free design choice, and it does not have to equal the original key dimension d_key. A φ that maps into a higher-dimensional space than it started in (d_dot > d_key) can, in principle, store more orthogonal directions than the raw keys ever could — a lever for raising the capacity ceiling Chapter 3 is about to run headlong into. The simplest possible φ (identity, or ELU+1 applied elementwise) leaves d_dot = d_key, spending none of that lever. Later chapters revisit what happens when you pull it.

In code, so the shapes are undeniable

python
import torch

def full_attention_step(q, K, V):
    # K, V: (i, d) -- every key/value seen so far. Cost grows with i.
    scores = K @ q                              # (i,) -- i comparisons, more every step
    weights = torch.softmax(scores, dim=0)
    return weights @ V                       # (d,)

def linear_attention_step(q, k, v, S):
    # S: (d_value, d_key) -- fixed size, no matter how many tokens came before.
    S = S + torch.outer(v, k)                   # one outer product, O(d^2) work
    o = S @ q                                    # one matrix-vector multiply, O(d^2) work
    return o, S                              # S is EVERYTHING carried to the next step

Read the two functions side by side. full_attention_step needs the entire history K, V passed in every single call — that's the KV cache Session 08 spent a whole lesson pricing out. linear_attention_step needs only the previous step's S, a single fixed-size matrix. Nothing about token 1 through token i−1 individually survives past that one matrix — and whether that's a feature or a cost is a question this lesson keeps returning to.

The chain of reasoning, compressed to five steps

Before moving on, compress this chapter's whole derivation into a checklist worth being able to reproduce from memory: (1) write softmax attention with its kernel κ(k,q)=exp(k·q) made explicit; (2) replace κ with a factorizable kernel φ(k)^Tφ(q); (3) use associativity to pull the query-dependent factor outside the summation over prior tokens; (4) name what's left inside the sum a running state S; (5) notice that a running sum updates by simple addition of one new term, which is exactly a recurrence. Every one of those five moves is reversible and checkable — there is no step in this derivation that requires taking anything on faith, which is precisely why Chapter 2 can claim the resulting object is identical to a decades-old memory model, not merely similar to one.

Chapter 2: Fast Weight Programmers

The matrix S from Chapter 1 is not a new idea invented for Transformers. It is, almost move for move, a mechanism proposed in 1991 — three decades before “linear Transformer” was a phrase anyone used — by Jürgen Schmidhuber, under a name that sounds almost like science fiction: Fast Weight Programmers. This chapter is the paper this whole session is built around — Linear Transformers Are Secretly Fast Weight Programmers, by Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber, IDSIA (Swiss AI Lab), published at ICML 2021 — and its central claim is exactly what the title says: strip the softmax out of attention, and what's left is, in every mathematical respect, a fast weight programmer.

What a fast weight programmer actually is

In an ordinary neural network, the weights are fixed after training — only the activations change as new inputs arrive. The fast weight idea, going back to von der Malsburg's 1981 work on synaptic modulation, is to let the weights themselves change at test time, dynamically, based on the input stream. A slow net — trained the ordinary way, its own weights frozen after training — learns to continually reprogram the weights of a second, fast net, using a sequence of small, differentiable edits. The slow net's job isn't to answer the question directly; its job is to write a tiny, constantly-updating program (encoded as the fast net's weight matrix) that the fast net then executes.

An analogy worth holding onto: the slow net is a programmer, the fast net is the computer running whatever program was most recently compiled. Every token that arrives hands the programmer a small edit to make to the running program — not a full rewrite, just one more instruction appended — and the computer immediately executes the updated version to produce its output. Nobody hand-writes the instructions; the programmer (the slow net) learns, through ordinary gradient descent during training, what instructions to generate at each step in order to make the fast net produce useful outputs. This is the picture Chapter 1's matrix S already matches exactly — it just wasn't described in programming terms until now.

Schmidhuber's 1991–1993 formulation gives the slow net one specific, elegant instruction for rewriting the fast weights: an outer product between two self-generated vectors. For an input sequence {x⁽¹⁾…x^(L)}, the slow net produces two vectors per step, a⁽ⁱ⁾ and b⁽ⁱ⁾, and writes them into the fast weight matrix additively:

Compare that to Chapter 1's ending point: S_i = S_i−1 + v_ik_i^T, o_i = S_iq_i. Set σ to the identity function, drop the query projection, and rename a→v, b→k, x→q. The two equations are now identical. Not similar — identical, term for term. Linear attention's running state S is a fast weight matrix; its keys and values are the slow net's self-invented programming instructions; its queries are the fast net's own input. Ba et al. (2016) had already noticed a version of this connection to attention specifically; this paper makes the equivalence with modern linear Transformers precise and complete.

python
import torch

# Schmidhuber 1991-93's Fast Weight Programmer, verbatim (sigma = identity)
def fwp_step(x, Wa, Wb, W):
    a, b = Wa @ x, Wb @ x
    W = W + torch.outer(a, b)      # the "programming instruction"
    y = W @ x
    return y, W

# Chapter 1's linear attention recurrence, same shapes, renamed variables only
def linear_attn_step(q, Wk, Wv, S):
    k, v = Wk @ q, Wv @ q
    S = S + torch.outer(v, k)      # a → v, b → k
    o = S @ q
    return o, S

# same weights, same input -- these two functions compute the same thing
d = 4; Wa = Wk = torch.randn(d,d); Wb = Wv = torch.randn(d,d)
x = torch.randn(d); W = torch.zeros(d,d); S = torch.zeros(d,d)
y, _ = fwp_step(x, Wa, Wb, W)
o, _ = linear_attn_step(x, Wk, Wv, S)
print(torch.allclose(y, o))   # True -- not an analogy, the identical function

One more historical detail worth savoring: Schmidhuber's 1993 paper, describing a recurrent version of exactly this mechanism, uses the phrase “internal spotlights of attention” to describe what the fast net's dynamically-changing weights do — written nearly a quarter-century before “attention” became the field's standard vocabulary for this operation. The word choice wasn't a coincidence in hindsight, and it wasn't borrowed from later Transformer papers either — it's independent evidence that the underlying concept these two vocabularies describe was recognizable as “attention-like” even to the researcher who first built it, decades before the term was standardized.

The longer lineage, because it didn't start or stop in 1991

The fast weight idea has an even older ancestor and a longer afterlife than a single paper suggests, and both ends of that history are instructive. The ancestor: Christoph von der Malsburg's 1981 work on “synaptic modulation” first proposed that a network's effective weights could be a superposition of ordinary, slowly-changing weights and fast, context-dependent ones — the conceptual seed, though not yet a trainable mechanism. Geoffrey Hinton and David Plaut, in 1987, built a network with two literal sets of weights at different learning rates, but for a different purpose (fast retraining after damage), not for processing a sequence. What Schmidhuber's 1991–1993 papers added, and what made this session's equivalence possible, was the missing piece: a mechanism where the slow net learns, by ordinary gradient descent, to generate the programming instructions for the fast net, from the input stream itself — nobody hand-designs what gets written; the network invents it.

The afterlife matters just as much for understanding why this framing resurfaced in 2021. Fast weights went quiet for two decades, then reappeared repeatedly under different names as different subfields rediscovered pieces of the same idea: hypernetworks (a network that generates another network's weights), dynamic convolution (a convolution kernel computed fresh from the input rather than fixed after training), and meta-learning approaches that use fast weights to let a model adapt within a single task without a separate fine-tuning step. Schlag and Schmidhuber's own 2018 and 2021 follow-up work specifically extended fast weight memories with mechanisms for replacing outdated associations — work that directly seeded the delta rule this session builds toward in Chapter 4. The point worth carrying forward: this session's “linear Transformers are secretly fast weight programmers” is not a one-off cute observation. It's the moment a three-decade-old, independently-rediscovered-several-times idea and a then-brand- new architecture turned out to be the same mathematical object, which is exactly why the capacity theory (Chapter 3) and the delta-rule fix (Chapter 4) could be imported wholesale instead of invented from scratch.

A second, independent bridge: modern Hopfield networks

Fast weight programmers aren't the only 20th-century memory model attention turns out to resemble. A separate 2021 line of work (Ramsauer et al.) showed that softmax attention itself is mathematically close to a modern Hopfield network — an associative memory model dating to John Hopfield's 1982 paper, updated with a continuous, exponential energy function whose update rule turns out to look almost exactly like softmax attention's retrieval step. That's a genuinely different historical lineage than this chapter's fast-weight-programmer connection — Hopfield networks come from statistical physics and associative memory theory, fast weight programmers come from meta-learning and dynamic connectionism — and yet both independently converge on the same object: attention as some flavor of associative memory retrieval. Two unrelated fields, decades apart, both looking at attention and recognizing the same shape underneath it is a strong signal that “attention is a memory-retrieval operation” isn't a cute reframing, but close to attention's actual mathematical nature.

Why this connection took thirty years to notice

It's worth asking why nobody spotted this identity between 1991 and 2021, given how short the algebraic distance turned out to be. Two practical reasons stand out. First, fast weight programmers were a small, specialized research thread throughout the 2000s and 2010s — interesting to a handful of researchers, not mainstream enough for most of the field working on Transformers to have encountered them at all. Second, and more fundamentally, nobody had strong reason to go looking for the connection until after the Transformer's O(L²) cost became a widely felt practical pain point, which only happened once Transformers themselves became the dominant architecture and people started training them on longer and longer sequences, around 2019–2020. The equivalence this chapter derives was, in a real sense, always true and always derivable — nothing about the 1991 equations changed. What changed was that enough people needed a fix for quadratic attention that someone went looking through the literature for prior work on efficient, associative-memory-flavored alternatives to a growing weight matrix, and found a three-decade-old answer waiting. This is a useful pattern to notice for research generally: a genuinely useful old idea can sit unused for decades, not because it was wrong, but because the problem it solves hadn't become painful enough yet for anyone to go looking for it.

A worked memory: two orthogonal keys, hand-computed

Make this concrete with numbers small enough to verify with pencil and paper: a 2-dimensional key space, two stored associations. Let the two keys be the standard basis vectors, and pick two arbitrary value vectors to associate with them:

Build the fast weight matrix by summing the two outer products, exactly as Chapter 1's recurrence would after two steps. Recall v ⊗ k = vk^T is a d_value × d_key matrix — here 2×2 — built by multiplying each entry of v against each entry of k:

Now retrieve. Query with k₁ itself — o = Wk₁ = W·(1,0), which picks out exactly W's first column:

Query with k₂: W(0,1) = (5·0+3·1, 2·0+7·1) = (3, 7) = v₂, exactly. Perfect recall, both times, with zero interference between the two stored associations. Now try a query that's a 50/50 blend of the two keys, q = (0.5, 0.5):

Exactly the average of the two stored values — a graceful, linear blend, not garbage. This is the fast weight memory working exactly as designed: perfect retrieval on the keys you stored, sensible interpolation on anything in between.

Why orthogonality gives exact retrieval, formally

The two numeric checks above are convincing but it's worth seeing why they had to come out exact, not just observing that they did. For a set of keys {k₁…k_n} that are orthonormal (each unit length, all mutually perpendicular), querying the memory W = ∑_j v_j⊗k_j with any stored key k_i gives:

where δ_ji is the Kronecker delta — 1 when j=i, 0 otherwise — which is exactly what “orthonormal” means in dot-product terms: k_j·k_i is 1 when they're the same vector and 0 whenever they're different. Every term in the sum except j=i vanishes automatically, leaving exactly v_i with nothing added or subtracted. This is the precise condition Chapter 3 violates on purpose: the moment any two stored keys have a nonzero dot product, that clean cancellation breaks, and δ_ji stops being 0 for j≠i — which is exactly the crosstalk term Chapter 3 computes by hand.

Scaling the toy up to a real model's dimensions

This chapter's memory lived in 2 dimensions specifically so the arithmetic could be checked by hand. A real attention head, per Session 08's Llama-2-7B numbers, has d_key = 128 (4,096 hidden size split across 32 heads). Nothing about the mechanism changes at that scale — W is still built by summing outer products, retrieval is still one matrix-vector multiply — only the numbers get too large to track by hand. What does change with scale is exactly the quantity Chapter 3 is about: a 128-dimensional key space has room for 128 mutually orthogonal directions instead of 2, which sounds like a lot of headroom until you remember that a single attention layer processes sequences far longer than 128 tokens, routinely thousands to millions of them. The toy's cliff at 3 stored associations and the real model's cliff somewhere past 128 are the same cliff, just at different heights — Chapter 3 makes that scaling explicit.

In code: the whole memory, four lines

python
import torch

k1, v1 = torch.tensor([1., 0.]), torch.tensor([5., 2.])
k2, v2 = torch.tensor([0., 1.]), torch.tensor([3., 7.])

W = torch.outer(v1, k1) + torch.outer(v2, k2)   # [[5,3],[2,7]]

print(W @ k1)   # tensor([5., 2.])  -- exact v1
print(W @ k2)   # tensor([3., 7.])  -- exact v2
print(W @ torch.tensor([0.5,0.5]))  # tensor([4., 4.5]) -- blend

This is what “attention” reduces to once softmax is gone: not a comparison against a growing list, but a lookup in a matrix that was built by summing self-invented key-value edits. Every worked example for the rest of this session builds on exactly this W = ∑ v⊗k mechanism — the next two chapters ask what happens when you keep writing to it forever, and how to fix what goes wrong.

Notice, too, that torch.outer(v1, k1)'s argument order matches this session's math notation exactly — value first, key second, producing vk^T — which is worth confirming explicitly rather than assuming, since getting the order backwards would silently produce the transpose of the intended matrix and every subsequent retrieval would be wrong in a way that's easy to miss without a worked numeric check like this one to catch it against.

A quick sanity check: does d_value have to equal d_key?

Nothing in this chapter's derivation required the value dimension to match the key dimension — worth confirming, since all this chapter's worked examples happened to use 2 for both. W = ∑ v_j⊗k_j is a d_value×d_key matrix in general, built from d_value-dimensional values and d_key-dimensional keys independently. Try d_value=3, d_key=2: k₁=(1,0), v₁=(5,2,9). The outer product v₁⊗k₁ is a 3×2 matrix, [[5,0],[2,0],[9,0]], and retrieval Wk₁ returns a 3-dimensional vector, exactly matching v₁. The key space (where orthogonality and capacity live, Chapter 3) and the value space (what actually gets retrieved) are two independent design choices — capacity is governed entirely by d_key (or d_dot, once a φ is involved), never by how wide the retrieved values happen to be.

Chapter 3: When Memory Overflows

Chapter 2's two-key memory was perfect because the two keys were orthogonal — at right angles, dot product exactly zero. That wasn't a lucky choice; it was the entire reason retrieval came out clean. This chapter asks the question Chapter 2 sidestepped: what happens once you try to store more associations than the key space has room for orthogonal directions?

The capacity argument, in one sentence

A d-dimensional space contains at most d mutually orthogonal vectors — that's a basic fact of linear algebra, the same one that says a 2D plane has exactly two perpendicular axes and no third one is possible. Every additional key beyond that count is forced to have a nonzero dot product with at least one key already stored. And a nonzero dot product means the retrieval sum ∑_j v_j (k_j·q) picks up unwanted contributions from those other stored values whenever you query with that key — crosstalk, in the paper's own terminology, borrowed from Smolensky's 1990 tensor product representation theory. Beyond d stored associations, in a d_dot-dimensional key space, the memory enters what the paper calls an overcapacity regime, and retrieval quality degrades.

Smolensky's tensor product representation theory, borrowed here, was originally developed for a different question — how connectionist neural networks could represent symbolic, structured information (roles bound to fillers, like a sentence's grammatical structure) using nothing but distributed vector representations, without hand-wiring the structure in. The mathematical object at the center of that theory — a sum of outer products binding “role” vectors to “filler” vectors — turns out to be identical in form to this chapter's fast weight matrix, with keys playing the role of roles and values playing the role of fillers. One difference is worth flagging, since it's a genuine distinction rather than a detail: Smolensky's classical tensor product representations are built with the roles and fillers chosen in advance, by whoever designs the representation. This chapter's fast weight programmers learn both the keys and the values through gradient descent, with nobody specifying in advance what a given key ought to mean. The capacity theorem transfers regardless of that difference — a d-dimensional space still only holds d orthogonal directions whether those directions were chosen by a designer or discovered by training — which is precisely why it was safe for the 2021 paper to import the theorem wholesale rather than re-derive it.

Hand-worked: adding a third key to a 2D memory

Take Chapter 2's exact memory, W = [ [5,3], [2,7] ], built from two orthogonal keys. There is no room for a third orthogonal direction in 2D — so pick a third key that is necessarily non-orthogonal to the first two, say k₃ = (0.6, 0.8) (a unit vector, at roughly 53° from the x-axis), paired with v₃ = (9, 1):

Query with k₃ itself, hoping for v₃ = (9,1) back:

Wrong, by a lot. Here's why, made explicit: because k₁·k₃ = 0.6 and k₂·k₃ = 0.8 (neither is zero — k₃ isn't orthogonal to either earlier key), the retrieval sum pulls in leftover mass from both earlier associations:

Matches, term for term — confirming exactly where the corruption comes from. Now check the damage in the other direction: query with k₁, which used to retrieve a perfect (5, 2):

Also wrong — adding the third association corrupted retrieval of the first one too, even though nothing about k₁ or v₁ changed. This is the overcapacity regime in miniature: past a fixed capacity, every new write degrades every old memory a little, not just the newest one.

How the real experiment behind this chapter was actually run

This chapter's numbers (the S≈60 threshold at d_dot=64, the 128/256/384 DPFP thresholds) come from a controlled synthetic retrieval task designed specifically to isolate capacity, worth understanding in outline. A pool of S unique random key-value pairs is sampled, written into the memory once each (no repeats, unlike Chapter 5's later with-replacement variant), and the model is then queried with one of the stored keys, asked to retrieve its paired value. Every model in the comparison — softmax, plain linear attention, DPFP at three settings, FAVOR+ at three settings — is trained on this exact task, independently, for each value of S from 20 up to 600 in steps of 20, until either the loss falls below a fixed threshold or training visibly stalls. Each is trained fresh at every S, so the reported threshold where a given φ function starts failing is not a single lucky or unlucky run, but the point along an entire swept curve where retrieval quality provably falls apart. That's the same shape of experiment the interactive simulation below approximates in 2D, with random keys instead of a deliberately constructed example.

Is this a toy problem, or does it actually happen in a real deployment?

Connect the synthetic S=20-to-600 sweep to something concrete. A real Llama-2-7B-scale attention head has d_dot=128 (Session 08's 4,096 hidden size, split across 32 heads). Under plain linear attention with φ=identity, that head's memory would enter Chapter 3's overcapacity regime the moment a processed sequence carries more than 128 genuinely distinct key directions worth remembering. A single paragraph of ordinary text easily contains far more than 128 tokens, and while not every token's key points in a fully independent direction, real learned key projections spread out enough in practice that meaningful crosstalk shows up well before every one of a document's tokens has been processed — which is exactly why Chapter 5's real experiment (not a toy) shows plain linear attention's perplexity diverging past 260 on long, untruncated text. This isn't a corner case reserved for adversarially constructed sequences; it's the default behavior of the sum rule on any sufficiently long, sufficiently varied stretch of ordinary language.

python
import torch

k1, v1 = torch.tensor([1.,0.]), torch.tensor([5.,2.])
k2, v2 = torch.tensor([0.,1.]), torch.tensor([3.,7.])
k3, v3 = torch.tensor([0.6,0.8]), torch.tensor([9.,1.])

W = torch.outer(v1,k1) + torch.outer(v2,k2) + torch.outer(v3,k3)
print(W @ k3)   # tensor([14.4, 7.8])  -- should be [9,1], crosstalk from k1 and k2
print(W @ k1)   # tensor([10.4, 2.6]) -- should be [5,2], corrupted by k3's write too

How DPFP actually buys extra capacity

The callout above treats DPFP as a black box that “pushes the ceiling higher.” It's worth seeing how, in miniature, because the trick is genuinely clever and reusable. Take a 2-dimensional key k = (k₁, k₂) and map it into 4 dimensions using the rectifier r(a) = max(0, a) applied to four different sign combinations:

Each of the four output coordinates is the product of two rectified half-plane tests — effectively asking “is this key in quadrant 1? quadrant 2? 3? 4?” Any given 2D key vector falls into exactly one quadrant, so at most one of the four coordinates is nonzero for that key: if k has k₁>0 and k₂>0 (quadrant 1), only φ₁ fires; the other three are forced to zero because they each contain a rectified negative version of a positive coordinate. Two keys landing in different quadrants therefore project to vectors with non-overlapping nonzero entries — automatically orthogonal in the 4D output space, even though they weren't orthogonal in the original 2D space. That's the entire mechanism: trade dimensionality for guaranteed orthogonality, splitting the input space into enough regions that keys landing in different regions can never collide. The general version scales this to any d_key, with a tunable parameter ν controlling exactly how many regions to split into — which is where the 128/256/384 capacity figures in the callout above come from: d_dot = 2d_keyν, so ν=1,2,3 at d_key=64 gives exactly those three numbers.

A second real result: the same story in machine translation

The capacity theory isn't confined to synthetic retrieval toys — the paper checks it on WMT14 English-to-German translation too, comparing BLEU scores (higher is better) for the same architecture with different φ functions, at three different d_dot values:

Read the Performer row across: it needs d_dot=512 — a projection dimension eight times the original key size — before it catches up to a standard softmax Transformer's 27.7 BLEU. DPFP reaches 26.9–27.1 at far more modest dimensions. The mechanism is the same capacity argument this chapter has been making by hand: a small dot-product space starves retrieval quality, and different φ functions buy their way out of that starvation at very different rates.

An honest complication: even softmax attention isn't infinite capacity

It would be tempting to conclude “just use real softmax attention and this whole chapter's problem disappears.” Softmax attention doesn't compress the past into a fixed-size matrix at all — every token's key and value stay separately addressable, so there's no d_dot-sized bottleneck to overflow. But the paper's own Setting 1 experiment (Section 6.1.1, the same one that measured the 60/128/256/384 thresholds) reports that even softmax attention “struggles to fully converge with more than 500 keys” on their synthetic retrieval task. The failure mode is different in kind — not the clean, provable crosstalk this chapter derived by hand, but a harder optimization landscape as the number of associations to juggle grows — and it kicks in at a much higher association count. But “no hard capacity ceiling” is not the same claim as “capacity is never a practical concern,” even for the method Chapter 0 is racing to approximate.

Does raising d_dot to 3 fix the 2D toy? A quick check

One more useful sanity check on the capacity argument: does adding a third dimension to this chapter's toy memory (not a third association — a third axis) let three keys coexist cleanly, the way two did in 2D? Use three mutually orthogonal 3D keys, k₁=(1,0,0), k₂=(0,1,0), k₃=(0,0,1), each with its own value. Every pairwise dot product among these three is exactly 0 — the Kronecker-delta argument from Chapter 2 applies without modification, and all three retrievals come back exact, no crosstalk at all. The lesson isn't “more dimensions never help” — DPFP's entire strategy in this chapter is exactly “buy more dimensions.” The lesson is narrower and sharper: capacity tracks d_dot exactly, one-for-one, with no slack. Three keys need three dimensions, not “a bit more than two.”

Push it one key further to confirm the ceiling is exact, not approximate. Add a fourth key in that same 3D space, necessarily non-orthogonal to at least one of the first three (since 3D allows only 3 mutually orthogonal directions) — say k₄=(0.577,0.577,0.577), a unit vector with equal components along all three axes. Its dot product with each of k₁, k₂, and k₃ is 0.577, not zero — so by the exact same crosstalk formula from earlier in this chapter, querying with k₄ after it's written pulls in a 0.577-weighted contribution from all three earlier values, and querying with any of k₁–k₃ now picks up a 0.577-weighted sliver of v₄ too. The pattern is exact and dimension-independent: the (d+1)-th association in a d-dimensional space always corrupts, by precisely the geometry of how far from orthogonal it necessarily is.

What an overloaded memory should do instead

Look back at what actually broke in the hand-worked example: writing v₃ at k₃ didn't replace anything — it just added a new outer product on top of whatever was already sitting near that direction. An ordinary Transformer's KV cache doesn't have this problem at all, because it stores every (k, v) pair as a separate, immutable slot — concatenation, not summation, so nothing overwrites anything (at the cost, Session 08 showed at length, of the cache growing forever). The fast weight matrix has finite size by design; it has to overwrite. The purely additive update from Chapter 1, S_i = S_i−1 + v_ik_i^T, never subtracts anything — it can add new associations, but it has no notion of deprecating an old one that a new write should replace. That is precisely the gap Chapter 4 closes.

The tradeoff this chapter has been quietly making, named explicitly

Step back and notice what full attention buys by refusing this whole tradeoff: Session 08's KV cache stores every token's key and value as a separate slot, so it never has a capacity ceiling in the sense this chapter means — retrieval quality doesn't degrade as the sequence grows, only the memory bill does (Session 08's entire subject). Linear attention makes the opposite bet: bound the memory bill at a fixed size, and accept that doing so requires actively managing what stays in that bounded space. Chapter 3 has shown what happens when that management is skipped (the sum rule). Chapter 4 is the paper's answer for how to do the managing well. Neither choice is free — one pays in unbounded memory, the other pays in the engineering work of building a memory that knows how to forget correctly.

That framing — unbounded-but-simple versus bounded-but-managed — recurs constantly in systems engineering outside language models too: an unindexed table that never needs maintenance but grows forever, versus a fixed-size cache that stays small but needs an eviction policy to stay correct. Recognizing the capacity problem as an instance of that general pattern, rather than a language-model-specific quirk, is part of what makes Chapter 4's fix easy to accept once you see it: it's the familiar “bounded resource needs an active management policy” story, wearing a delta-rule-shaped costume.

Chapter 4: The Delta Rule

Chapter 3 diagnosed the disease: a purely additive write can never remove what's already there, so an overloaded memory can only ever get muddier, never cleaner. This chapter is the fix the paper proposes — and it borrows its name from a genuinely old idea in machine learning, the error-correcting delta rule of Widrow and Hoff, 1960, the same update rule behind the very first trainable linear classifiers.

The idea, before the algebra

Instead of blindly adding a new association on top of whatever is already stored at that key, first look at what's currently stored there, then write a value that corrects it — erase the old association's contribution and replace it with the new one, rather than piling the new one on top. Three steps, run at every token:

β — a number between 0 and 1, itself produced by a small learned projection of the input, so it's a different value at every token — is a write strength: β = 1 means fully overwrite the old association, β = 0 means leave the memory completely untouched.

Why β is squeezed through a sigmoid

The paper produces β_i as σ(W_βx_i) — a raw linear projection of the input, passed through the sigmoid function σ(x) = 1/(1+e^−x), which squeezes any real number into the open interval (0, 1). This isn't incidental: Chapter 4's interpolation step, v_new = βv_i + (1−β)v̄, is only a well-behaved convex combination — guaranteed to land somewhere between the old and new values, never overshooting past either one — if β is bounded within [0, 1]. Without that bound, a large learned projection value could push β above 1 or below 0, and the “blend toward the target” interpretation would break: β>1 would overshoot past the target value entirely, β<0 would push away from it. The sigmoid is what turns an unconstrained linear projection into a number that's always safe to interpret as a mixing weight, the same role a softmax plays in constraining attention weights to sum to 1 — a different constraint, serving an analogous purpose.

Why "delta rule" — a name older than deep learning itself

Bernard Widrow and Marcian Hoff introduced the delta rule in 1960 for a simple linear classifier called ADALINE (Adaptive Linear Neuron), and the core idea there is worth stating because it's the same idea, wearing different clothes: whenever the model's current prediction disagrees with the target, nudge the weights in the direction that reduces the error, by an amount proportional to how wrong the prediction currently is. That's Δw ∝ (target − prediction) × input — error times input, precisely the shape of Chapter 4's update, β_i(v_i − v̄_i) ⊗ k_i, just applied to an entire fast-weight matrix instead of a single classifier's weight vector, and with a learned per-token step size β_i where ADALINE used one fixed learning rate for every example. This is also, not coincidentally, the same error-times-input shape that shows up at the heart of ordinary gradient descent on a squared-error loss — the delta rule is gradient descent, applied online, one association at a time, to the tiny problem of “make the memory's retrieval at this key equal this value.” A sixty-five-year-old idea for training the simplest possible classifier turns out to be exactly what an overloaded 2021-era memory matrix needed.

The algebra collapses to something simpler

Substitute step 2 into step 3 and the write and remove terms combine (Appendix A.1 of the paper works this out formally):

This is the delta rule: write the difference between what you want and what's currently there, scaled by how strongly you want to write it. When v_i = v̄_i (the memory already holds the right value), the update term is exactly zero — nothing changes, correctly. When they disagree, the update nudges the memory toward the target, by exactly β_i of the gap.

Hand-worked: overwriting an association, cleanly

Return to Chapter 2's clean 2-key memory, W = [ [5,3], [2,7] ], built from k₁=(1,0), v₁=(5,2) and k₂=(0,1), v₂=(3,7). Suppose the model now wants to update what's stored at k₁ to a new target value, (11,4), with write strength β=0.8.

Step 1 — retrieve. With only two orthogonal keys stored so far, this is exact:

Step 2 — interpolate:

Step 3 — write the correction:

Verify by re-querying. With k₁:

And with k₂, which was never touched — because it's orthogonal to k₁, the update to k₁'s slot should leave it entirely alone:

A clean, selective, verified overwrite: the target association updated exactly as intended, the unrelated one left completely alone.

What the sum rule would have done instead

Now run the naive, purely-additive Chapter-1 update on the same request — no retrieval, no subtraction, just add the new outer product on top:

Query with k₁:

(16, 6) is exactly (5,2) + (11,4) — the old and new values summed together, an answer that means nothing to whatever reads it next. Put the two outcomes side by side and the entire chapter is one comparison:

python
def delta_rule_step(k, v, beta, W):
    v_bar = W @ k                                # step 1: retrieve current value
    v_new = beta * v + (1 - beta) * v_bar         # step 2: interpolate toward target
    W = W + beta * torch.outer(v - v_bar, k)     # step 3: write the correction (collapsed form)
    return W

# sanity check against the hand-worked numbers above
W = torch.tensor([[5.,3.],[2.,7.]])
W = delta_rule_step(torch.tensor([1.,0.]), torch.tensor([11.,4.]), 0.8, W)
print(W)   # tensor([[9.8, 3.], [3.6, 7.]])  -- matches Step 3 exactly

An honest limit: repairing one key doesn't repair its neighbors

It would be easy to walk away from this chapter thinking the delta rule solves Chapter 3's capacity problem outright. It doesn't — it gives the model a mechanism to selectively correct one association at a time, which is different from raising the ceiling. Prove this with one more hand-worked step, picking up exactly where Chapter 3 left off: the corrupted three-key memory, W_new = [ [10.4,10.2], [2.6,7.8] ], where k₃'s addition had corrupted retrieval of both earlier keys.

Use the delta rule, β=1 (full overwrite), to repair k₁'s association back to its true target (5,2). Retrieve first: v̄ = W_new(1,0) = (10.4, 2.6) — the corrupted value from Chapter 3. Write the correction:

Check k₁: W_repaired(1,0) = (5, 2) — exactly repaired, as guaranteed. Now check k₂, which was also corrupted by k₃'s addition but was never targeted by this repair:

Untouched, still corrupted. The delta rule repaired exactly the one key it was asked to retrieve-and-correct — it has no way of knowing k₂ was collateral damage unless a token specifically retrieves and rewrites k₂ too. This is the honest boundary of what Chapter 4 buys: not a cure for overcapacity, but a mechanism that lets the model actively manage a finite memory — deciding, per token, what to overwrite — rather than being stuck with a memory that can only ever accumulate. Chapter 3's hard ceiling (at most d_dot genuinely independent associations) doesn't move; what moves is whether the model can behave sensibly within that ceiling instead of degrading uncontrollably past it.

One coping strategy is worth naming, even though this lesson can't verify from the paper alone how strongly a trained model actually relies on it: a model with the delta rule available could, in principle, learn to periodically re-write (retrieve and rewrite with β near 1) an association it predicts will be needed again soon, refreshing it before newer writes have a chance to corrupt it through crosstalk. Nothing forces this behavior — it would have to emerge from training, the way most useful behaviors in a large model do, rather than being hand-coded. Whether real trained DeltaNets actually learn something like this strategy is an interpretability question neither paper in this session directly answers, but it's a natural hypothesis the mechanism makes available, worth flagging as an open question rather than a settled fact either way.

Why not a simpler-looking gated update rule?

A different, superficially similar fix might occur to you: instead of retrieving and subtracting, just gate the whole matrix — shrink the old state by (1−β) and add the new association on top, W′ = (1−β)W + βv⊗k. This is, in fact, exactly the update rule a concurrent 2021 paper (Peng et al.) proposed, and it's the same family of mechanism GLA (Chapter 8) is built around. It looks like it should behave similarly to the delta rule — both use a β to control how much writing happens. The paper's own appendix proves it doesn't, with a worked example this lesson can reuse directly.

Take Chapter 2's exact memory again, W = [ [5,3], [2,7] ], from orthonormal k₁=(1,0), v₁=(5,2) and k₂=(0,1), v₂=(3,7). Now write a third association at the same key as the second — k₃=k₂=(0,1), v₃=(11,4), β=0.8 — the cleanest possible test, since a good update rule should only touch k₂'s slot and leave k₁'s alone entirely.

The gated rule:

Query k₂: W′(0,1) = (9.4, 4.6) = 0.2v₂+0.8v₃, the correct blend. But query k₁, which was never touched:

The delta rule, same scenario: retrieve v̄ = Wk₂ = (3,7) = v₂ exactly (orthogonal to k₁, so retrieval is clean); write the correction:

Query k₂: W′(0,1) = (9.4, 4.6) — same correct blend. Query k₁:

Both rules get k₂'s update right. Only the delta rule leaves k₁ alone. The gated rule's (1−β) factor multiplies the entire matrix — every association currently stored, whether or not it has anything to do with the key being written — while the delta rule's correction term is scaled by k, meaning it only lands on directions the incoming key actually points in. This is precisely why GLA (Chapter 8), built on this gated family, forgets on a schedule that touches everything a little, while DeltaNet forgets conditionally, touching only what a given write's key actually collides with.

Neither rule is strictly better in every situation — the gated rule's uniform, scheduled decay is simpler to implement and, in cases where everything in the state should genuinely fade over time (recency matters more than exact correction), can be exactly the right prior to build in. The delta rule's more surgical, key-conditioned edit is the better choice specifically when the task calls for correcting a particular stale fact without disturbing unrelated ones — which is exactly the recall-heavy setting Chapter 8's benchmarks probe.

Chapter 5: DeltaNet

Chapter 4 built the delta rule from first principles as a fix for the capacity problem. The paper calls a linear Transformer built around exactly this update rule a Delta Network — the model this entire lesson's second half is about, and the name the follow-up paper (Chapter 6 onward) shortens to DeltaNet. This chapter checks the fix against real numbers, not just a 2×2 toy.

Normalization: a detail that turns out to matter

One loose end from Chapters 1–4: none of the hand-worked examples normalized the key vectors, but real key projections aren't guaranteed to have unit-length components summing usefully. The paper tests a straightforward fix — sum normalization — dividing the projected key and query vectors by the sum of their own components before using them, so retrieval behaves like a proper weighted average rather than an unbounded blend. They find this normalization is necessary for their update rule to train stably at all (models diverge without it), but that an additional normalization scheme on top — dividing by an accumulator z, the way Chapter 1's general kernel form does — actually hurts perplexity slightly once sum normalization is already in place. More normalization is not always better; the paper's own ablation (Table 3) shows the best configuration uses sum normalization alone, with neither absolute positional encoding nor the extra attention-normalization term.

Deriving sum normalization, not just naming it

Sum normalization means dividing a projected key vector by the sum of its own components before using it anywhere:

Why this specific normalization, and not some other one? The paper's own appendix derives it from a genuine requirement, not a guess: rewrite the delta rule's update in terms of W's individual columns rather than the whole matrix at once, and the update to column i turns out to have a “write” term weighted by k_i and a “remove” (crosstalk-correcting) term weighted by ∑_jk_ik_j. For the write and remove pieces to be properly balanced — so the remove term doesn't over- or under-correct relative to the write it's paired with — those two weights need to match, which forces ∑_jk_j = 1: the key's own components must sum to exactly 1. Sum normalization is precisely the operation that enforces that condition on every key, which is why skipping it specifically breaks the delta rule (rather than merely hurting linear attention in general the way skipping normalization on the sum rule would): the delta rule's write/remove balance is a hard requirement the sum rule never had to satisfy in the first place, because the sum rule has no remove term to balance against.

Verify the normalization itself is trivial arithmetic, so it's clear no mystery is hiding in it: take a raw projected key k=(3,1) (components don't need to sum to 1 before normalizing). Sum of components: 3+1=4. Normalized: φ′(k) = (3,1)/4 = (0.75, 0.25). Check: 0.75+0.25=1, exactly the condition the derivation above requires. This is the entire operation — not a learned transformation, not a different kernel, just a division by a scalar computed from the vector's own entries, applied fresh to every key and query at every token.

The full ablation, all four combinations, real numbers

Don't just take “more normalization isn't always better” as an assertion — the paper tests all four combinations of two independent design choices (absolute positional encoding: yes/no; extra attention normalization on top of sum normalization: yes/no) on the medium WikiText-103 configuration, and the full grid is worth seeing:

The best row drops both extras — no positional encoding, no extra normalization — and it's not a close call; removing positional encoding alone buys more than removing the extra normalization alone does (29.2 vs 29.7 test-adjacent valid numbers), and dropping both compounds the gain rather than cancelling it. The positional-encoding result in particular confirms something Chapter 1 didn't dwell on: DeltaNet's update rule is inherently order-sensitive already — every token's write depends on the exact sequence of retrievals and corrections that came before it, so a recurrence built this way doesn't need an explicit position signal bolted on top the way a permutation-invariant softmax attention layer does.

Real numbers: WikiText-103 language modeling

Why WikiText-103 specifically, and not some shorter benchmark? Its articles run to roughly 3,600 words on average, deliberately chosen (the paper notes) because a benchmark of short, disconnected sentences would never put enough pressure on a memory mechanism to reveal a capacity problem at all — Chapter 3's crosstalk needs enough distinct associations flowing through the state before it becomes visible in the aggregate loss. A dataset of long, internally-coherent documents is exactly the setting where a model that starts corrupting distant associations would show it, and where one that doesn't would earn its perplexity advantage honestly.

Train small Transformer-style models (16 layers, two sizes — “small” at 40M parameters, “medium” at 90M) on WikiText-103, a standard large-vocabulary word-level benchmark, and compare three update rules under an identical architecture and parameter budget. Lower perplexity is better (recall Session 08: perplexity is roughly “how surprised was the model,” and the gap between two perplexity numbers is exponential in the underlying loss difference, not additive):

Same architecture, same parameter count, same training budget — the only variable is the update rule, and switching from sum to delta closes roughly half the gap between plain linear attention and full softmax attention, in both model sizes. Both configurations are deliberately run in what the paper calls an “overcapacity regime” — the sequence length exceeds the key dimension — exactly the condition Chapter 3 showed breaks the sum rule.

Just how far over capacity, worked from the paper's own architecture numbers

“Overcapacity” is worth quantifying, not just naming, using Chapter 3's exact framework. The small configuration sets total model dimension D=128 split across H=8 attention heads, so each head's key/dot dimension is d_dot = D/H = 16. Training context length is L=256:

The medium configuration: D=256, H=8, so d_dot=32, trained at L=384:

Both configurations aren't marginally past the crosstalk cliff Chapter 3 derived — they're an order of magnitude past it. This is precisely why Table 2's gap between the sum rule and the delta rule is as large as it is: at 16× or 12× overcapacity, Chapter 3's crosstalk isn't a subtle effect, it's the dominant failure mode, which is exactly the regime where a mechanism that can correct associations (the delta rule) should outperform one that can only pile them up (the sum rule) by the widest margin. A comparison run well inside capacity would have shown a much smaller gap, because the sum rule's flaw only bites once the shelf is actually full.

The paper is explicit that this is a deliberate experimental choice, not an accident, and it also reports (in an appendix, for a non-overcapacity setting using DPFP's higher-dimensional feature map) that the delta rule's advantage shrinks — unsurprising, given the mechanism this whole chapter has been deriving. When a memory never gets full enough to need active correction in the first place, there's less for a correction mechanism to correct. The headline gap in Table 2 is real, but it's specifically the gap measured under conditions engineered to stress-test the exact failure mode Chapter 3 diagnosed — worth remembering before treating these particular numbers as a universal “delta rule beats sum rule by this much” constant.

The number that matters most: unbounded context

Table 2 caps the context length during evaluation. A more honest test of “constant memory forever” removes that cap entirely and lets the model run over arbitrarily long, untruncated text — exactly Session 08's day-long-chat scenario, but for a fundamentally different architecture than StreamingLLM patches.

Read the top two rows first: the sum-rule Linear Transformer collapses without truncation — a perplexity above 260 is close to broken — exactly Chapter 3's overcapacity prediction playing out at full scale, not a toy. The Delta Network, with the identical 0.13-million-parameter fixed state, stays coherent at 29.4, roughly on par with a full Transformer. Then look at the bottom two rows: Transformer-XL, which keeps a literal window of past hidden states rather than a fixed-size matrix, needs roughly 48× more state (6.29M vs 0.13M) than DeltaNet just to edge past it, at 25.5 vs 29.4. DeltaNet doesn't win outright — but it gets close to a model paying dozens of times more memory, using a state size that never grows no matter how long the text runs.

A detail worth being precise about: which normalization broke which model

This unbounded-context experiment drops the extra attention-normalization term entirely (Chapter 5's own ablation recommended this), but the paper is explicit that the two update rules break for different reasons when normalization choices change, and the asymmetry is instructive. For the Delta Network, keeping the extra normalization term was actively harmful without truncation, because its accumulator z grows without bound as the sequence lengthens — removing it was necessary specifically to avoid that blow-up. For the plain sum-rule Linear Transformer, the paper reports that removing the same term made things worse, not better — perplexity above 1,600, even further broken than the >260 figure in the table above under a different normalization setting. Two different mechanisms, two different failure modes, responding to the same knob in opposite directions. This is precisely why Chapter 5's ablation table earlier in this chapter isn't a universal recipe — “drop the extra normalization” is the right call for the delta rule specifically, for a reason tied to its own accumulator dynamics, not a general-purpose rule that happens to also apply to the sum rule.

Interestingly, the delta rule is even slightly faster in words/sec than the sum rule here (66K vs 63K), despite doing strictly more arithmetic per step (an extra retrieval and subtraction). The likely explanation is that this comparison measures the sum rule's own separately-implemented CUDA kernel, and small implementation differences between two independently-optimized kernels can easily produce noise of this size — a reminder that a few-percent difference in a wall-clock benchmark is rarely worth over-interpreting, compared to the order-of-magnitude differences (state size, perplexity collapse) this session has spent most of its numeric arguments on.

Checking Chapter 0's crossover against this chapter's own training setup

Chapter 0 derived a crossover at L = d. Chapter 2's “small” configuration here trains at context length L=256 with model dimension D=128. Plug into Chapter 0's ratio:

That's a real but modest saving — nowhere near the ~977× figure Chapter 0 computed at Session 08's 4-million-token scale, because this training setup sits barely past the crossover point, not deep into linear-attention's favorable regime. This is worth noticing precisely because it's easy to read Chapter 2's perplexity table and assume the compute savings were dramatic too; at this particular context length, they mostly weren't. The efficiency case strengthens as context length grows, which is exactly why Table 4's unbounded-context experiment (next) is the more compelling evidence for why this approach matters, not the bounded 256-token comparison that produced Chapter 2's perplexity numbers.

The synthetic test built specifically to isolate the update rule

Table 2's language-modeling numbers mix together many effects at once — architecture, dataset, capacity regime. The paper also runs a synthetic task built to isolate just the update rule, echoing this lesson's own hand-worked overwrite example from Chapter 4, but at scale and under training. Keys and values are sampled with replacement from a pool of 20 unique key-value pairs, over a sequence of 40 tokens — meaning the same key gets reassigned to a new value multiple times within one sequence, and the correct thing to retrieve is always the most recent value bound to a given key. This is Chapter 4's overwrite scenario, generated automatically and repeated thousands of times during training rather than computed once by hand.

Four update rules are compared under an identical architecture: the plain sum rule (Chapter 1), this paper's delta rule with sum normalization (Chapter 4), and two earlier variants from Schlag and Schmidhuber's own prior work (one using a tanh nonlinearity for keys instead of a φ function, one hybrid combining that variant with DPFP). The result: the sum rule fails to learn the task at all — expected, since Chapter 3's crosstalk argument applies just as much to a memory that keeps getting reassigned as one that keeps growing. This paper's delta rule with sum normalization outperforms every other variant tested, including the authors' own earlier attempts at the same problem. The specific combination — delta rule plus sum normalization, no more, no less — isn't an arbitrary choice; it's the configuration that survived a genuine comparison against real alternatives.

Converting Table 2's gap into bits, the way Session 08 did

Session 08 converted a perplexity gap into bits-per-token to make it viscerally comparable. Do the same here for the medium-config gap between the sum rule (33.0) and the delta rule (31.5). Recall PPL = e^loss, loss in nats:

A fraction of a bit per token — a real, measurable, but modest improvement, nothing like the thousand-times “PPL 5,158 → 5.4” collapse Session 08's window-attention fix addressed. That scale difference is worth sitting with: Session 08 was fixing a catastrophic failure (attention sinks evicted, model breaks completely); this chapter is describing a genuine but incremental quality improvement (delta rule vs sum rule, both functioning, one somewhat better). Both are real, worthwhile fixes — but conflating their magnitudes would be a mistake this lesson has tried to avoid throughout.

One thread not yet pulled

Table 2 and the state-size table above both share something worth flagging before moving on: every number in this chapter came from a model trained the ordinary way — token by token, sequentially, exactly the recurrent form Chapter 1 wrote down. That's fine for evaluating a trained model, but it says nothing yet about how expensive it was to train it. Chapter 6 asks that question directly, and the answer is less comfortable than this chapter's perplexity numbers suggest.

Chapter 6: Why It Resists Parallelism

Chapter 1 ended with a callout worth returning to now: the plain sum-rule recurrence is fully parallelizable during training, because it's just a running sum, and sums can be reorganized into one big parallel matrix multiply, O = (QK^T ⋅ M)V. This chapter is about why that trick quietly stops working the instant you switch to the delta rule — and it's the entire motivation for the second paper this session covers: Parallelizing Linear Transformers with the Delta Rule over Sequence Length, by Songlin Yang, Bailin Wang, Yu Zhang, Yikang Shen, and Yoon Kim, MIT and the MIT-IBM Watson AI Lab, 2024.

Three years separate the two papers this session is built around, and it's worth being clear about what changed in that gap. Chapters 2 through 5 covered the 2021 paper's contribution: the fast-weight-programmer framing, the capacity theory, and the delta rule itself, verified at a scale (40–90M parameters) that a single research group could train in days. This chapter and the next cover what the 2021 paper explicitly flagged as unsolved — the training-parallelism problem — and the 2024 paper's answer to it, which is what unlocks Chapter 8's 1.3B-parameter results. The two papers are not competitors describing different ideas; the second is a direct continuation that made the first paper's idea trainable at a scale worth taking seriously.

A sum versus a product

Write the delta rule's update (Chapter 4) in a slightly different, equivalent form. Starting from W_i = W_i−1 + β_i(v_i − W_i−1k_i) ⊗ k_i, distribute the outer product across the subtraction inside the parentheses (v̄_i = W_i−1k_i, Chapter 4's retrieval step, substituted back in):

The last term is W_i−1 multiplied by k_ik_i^T (a d×d matrix), which lets W_i−1 factor out of both surviving terms that contain it:

Notice the shape: this is W_i−1 multiplied by a matrix, not added to one. The matrix (I − β_ik_ik_i^T) is a generalized Householder transformation — a well-known object from numerical linear algebra (it's the building block of the QR decomposition algorithm) that reflects vectors through a hyperplane. Unroll the recurrence back to the start of the sequence and W_t becomes a sum of terms, each one multiplied by a product of every Householder matrix that came after it:

Compare that to the plain sum rule's S_t = ∑_iv_i⊗ k_i: no products anywhere, just a sum whose terms can be added up in any order — which is exactly what makes it parallelizable. The delta rule's version has a genuine matrix product tangled through it, and matrix products of different matrices generally don't commute — you can't reorder them the way you can reorder addition. That non-commuting product is precisely what a naive implementation would need to materialize, and doing so is expensive.

What a Householder matrix actually does, in one worked reflection

The name “Householder transformation” sounds intimidating; the operation is simple enough to see in 2D. Take a unit vector k = (1, 0) and β = 1 (a full-strength write). The matrix I − kk^T:

Apply it to an arbitrary vector, say (3, 5): [ [0,0],[0,1] ](3,5) = (0, 5). The component along k (the x-component, 3) is annihilated; the component perpendicular to k (the y-component, 5) survives untouched. That's the entire geometric content of a Householder-style projection: it zeroes out exactly the direction the key points in, and leaves everything orthogonal to that direction alone — the same “erase along one direction, preserve the rest” behavior Chapter 4's hand-worked repair demonstrated numerically (repairing k₁ left the orthogonal k₂ untouched). Chapter 6's algebra is what makes that connection precise: the delta rule's per-step update is, literally, one of these directional erase-and-write operations, chained token after token.

python
import torch
k = torch.tensor([1.,0.])
H = torch.eye(2) - torch.outer(k,k)
print(H @ torch.tensor([3.,5.]))   # tensor([0., 5.]) -- x-component erased, y untouched

Proving the non-commuting claim, not just asserting it

Chapter 6's central claim is that these Householder-style matrices generally don't commute — order matters. Check it directly with two different keys, k₁=(1,0) and k₂=(0.6,0.8), both at β=1: H₁ = I − k₁k₁^T = [ [0,0],[0,1] ], and H₂ = I − k₂k₂^T = [ [1,0],[0,1] ] − [ [0.36,0.48],[0.48,0.64] ] = [ [0.64,−0.48],[−0.48,0.36] ].

Different matrices — H₁H₂ ≠ H₂H₁, confirmed entry by entry, not just asserted. This is exactly why the order tokens arrive in cannot be shuffled when computing the delta rule's accumulated state — unlike the plain sum rule, where v₁k₁^T+v₂k₂^T equals v₂k₂^T+v₁k₁^T always, by ordinary commutativity of addition.

Just how expensive, naively

The straightforward way to get each token's contribution right is to actually compute W_i−1k_i at every single step, sequentially, because W_i−1 depends on everything before it and there's no shortcut around that dependency without more work. That's an O(d) operation if you already have W_i−1 in hand — but getting to the point where every step's contribution is expressible without ever materializing the full d×d matrix at each step, for all L tokens up front, costs O(L ²d) using the direct approach, and worse, it cannot be parallelized across the sequence at all — step i genuinely needs step i−1's result before it can proceed. This is exactly the recurrent form's bottleneck Chapter 0 wanted linear attention to escape, reappearing from a different direction.

Every complexity number from this session, side by side

This is a good moment to collect every complexity figure derived so far into one table, because the pattern across rows is the whole story of Chapters 0 and 6 together:

Read the last row against the fourth: WY chunking doesn't reduce DeltaNet's total work below the naive recurrent form by much (both are close to O(Ld²) for reasonable chunk sizes) — the win is entirely in the sequential steps column, from O(L) down to O(L/C). That's the precise, narrow claim Chapter 7 makes, and it's worth being exact about it: chunking doesn't make DeltaNet do less arithmetic, it makes DeltaNet's arithmetic parallelizable, which on GPU hardware is very often the more important axis, exactly per the arithmetic-intensity argument below.

Why not just run the recurrence on the GPU as-is?

It's worth being specific about why a step-by-step recurrence is slow on a GPU, rather than just asserting it. GPUs get their speed from doing enormous numbers of arithmetic operations per byte moved between memory and compute units — arithmetic intensity, in the field's terminology — and specialized hardware (tensor cores) is built specifically to accelerate large, regular matrix multiplications. A token-by-token recurrence does the opposite: each step is a small, elementwise-flavored update, touching a comparatively large state matrix for a comparatively tiny amount of arithmetic, and it must happen strictly after the previous step finishes. Low arithmetic intensity plus forced serialization is close to the worst-case access pattern for this kind of hardware, which is why the recurrent form, despite doing fewer total FLOPs than the parallel form, routinely runs slower in practice — exactly the seeming paradox Chapter 0's crossover table hinted at but didn't fully explain.

Put a rough number on the intensity gap. A single delta-rule step touches a d×d state matrix (reads it once for retrieval, writes it once for the update) while doing on the order of d² FLOPs of actual arithmetic — a FLOPs-to-bytes ratio close to 1. A well-formed matrix multiply, by contrast, can reuse each loaded value many times across many output elements, routinely reaching FLOPs-to-bytes ratios in the hundreds on modern GPUs. Tensor cores are built to reward that second regime specifically; a workload that spends most of its time near ratio≈1, the way a token-by-token recurrence does, simply can't make use of the hardware that's actually sitting on the chip, regardless of how few total FLOPs it needs.

There's a classical trick for parallelizing recurrences in general, called a parallel scan, that can in principle compute a linear recurrence in O(log L) sequential steps instead of O(L) — and this is exactly the technique Mamba uses internally for its own state-space recurrence (Chapter 8 returns to Mamba). Why doesn't DeltaNet just do the same thing? Because a parallel scan still needs to materialize the state at every one of the L intermediate steps to combine them, and DeltaNet's state is a full d×d matrix, not a modest vector the way Mamba's per-channel state is kept small enough to be. Materializing a dense d×d matrix at every one of L positions is exactly the memory I/O cost this whole chapter is trying to avoid. Chapter 7's WY-representation trick sidesteps that cost a different way — not by scanning faster, but by never materializing the d×d matrix at all until it's genuinely needed.

What "chunkwise" already means for the easy case

Before tackling DeltaNet specifically, it's worth seeing how ordinary sum-rule linear attention gets its parallel training speed in practice, because the fix in Chapter 7 is a direct extension of it. Split the sequence into chunks of size C. Because the sum rule really is just addition, the state at the end of chunk t+1 is simply the state at the end of chunk t, plus everything written during chunk t+1 — and that “everything written during the chunk” term can be computed as one ordinary matrix multiply over the whole chunk at once, no per-token sequential loop required inside the chunk:

This is called the chunkwise parallel form: only L/C sequential steps (one per chunk, carrying the state forward), each one doing a cheap parallel matmul over C tokens at once. Set C = L and you recover the fully parallel form; set C = 1 and you recover the purely sequential recurrence.

Confirm the sum rule's chunkwise identity holds on a tiny case before trusting it: 4 tokens, chunk size 2, using this chapter's earlier 2D keys/values (k₁=(1,0),v₁=(2,0); k₂=(0,1),v₂=(0,3); k₃=(1,1),v₃=(1,1); k₄=(1,0),v₄=(2,2)). Sequential sum-rule state after all 4: S₄ = ∑v_i⊗k_i = [ [2,0],[0,0] ]+[ [0,0],[0,3] ]+[ [1,1],[1,1] ]+[ [2,0],[2,0] ] = [ [5,1],[3,4] ]. Chunkwise: chunk 1 (tokens 1–2) gives S_[0]=[ [2,0],[0,3] ]; chunk 2 (tokens 3–4) contributes V_[1]^TK_[1] = [ [1,1],[1,1] ]+[ [2,0],[2,0] ] = [ [3,1],[3,1] ]; total S_[1] = [ [2,0],[0,3] ]+[ [3,1],[3,1] ] = [ [5,1],[3,4] ]. Identical to the sequential result, confirming the chunkwise identity for the easy (sum-rule) case before Chapter 7 tackles the much harder delta-rule version of exactly this same equivalence.

It works cleanly for the sum rule specifically because addition inside a chunk can be computed all at once, independent of the incoming state — the delta rule's per-token matrix product can't, at least not without one more idea.

An axis that was never the problem: batching across sequences

Session 08 Chapter 1 was careful to separate two axes that get conflated: seq_len (the axis this whole lesson is about) and batch_size (how many independent conversations are processed side by side on the same GPU). It's worth being equally careful here. Everything Chapter 6 has diagnosed as “hard to parallelize” is specifically about the dependency within one sequence — token i needing token i−1's state. Nothing about the delta rule creates any dependency between separate sequences in a batch; a GPU can process 256 independent conversations' worth of DeltaNet recurrences fully in parallel with each other, exactly as it would for any other model. The bottleneck this chapter cares about is real, but it's narrower than “DeltaNet doesn't parallelize” might suggest at a glance — it doesn't parallelize within a sequence without Chapter 7's fix; it parallelizes across sequences exactly as well as anything else does, for free, with no fix required at all.

One more scope note: this chapter is entirely about training

Everything diagnosed in this chapter is a training-time problem specifically. At inference — generating one token at a time from an already-trained model — the plain sequential recurrence from Chapter 1 is exactly what you want to run regardless of update rule: one retrieve, one write, one output, per token, O(d²) work, no chunking needed at all. Chunking exists purely to make training tractable, where the entire sequence is available up front and the goal is maximizing GPU throughput across it. It would be a mistake to read this chapter as saying DeltaNet is slow to run — Chapter 5's own wall-clock numbers (66K words/sec, competitive with the sum rule) already showed inference-shaped throughput is fine. The problem this chapter and the next one solve is specifically about getting from “an untrained model” to “a trained one” without paying an unreasonable compute bill along the way.

Training needs more than a forward pass: the backward pass matters too

One more piece of the training-cost picture worth naming, since it's easy to forget: training doesn't just run this recurrence forward once, it needs to run backpropagation through it as well, computing gradients by walking the same dependency chain in reverse. If every chunk's intermediate state were kept in GPU memory to make that backward pass easy, memory cost would scale with L/C × d² — defeating much of the memory benefit chunking was supposed to provide. The production implementation handles this with a standard trick from deep learning generally, called gradient checkpointing: discard the intermediate chunk states after the forward pass finishes, and recompute them on the fly during the backward pass instead, trading a modest amount of extra compute (re-running the cheap forward chunk math a second time) for a large reduction in peak memory. This is exactly the kind of implementation detail Chapter 7's clean C=2 example glosses over for pedagogical clarity, but it's real engineering the actual training system has to handle to make Chapter 8's 1.3B-parameter run fit on available hardware at all.

Chapter 7: The WY Trick (showcase)

Chapter 6 left DeltaNet with a real problem: training requires either a full sequential pass (slow, one step at a time) or materializing a growing product of Householder matrices (expensive, and it still doesn't parallelize). The 2024 paper's fix borrows a fifty-year-old piece of numerical linear algebra called the WY representation (Bischof and Van Loan, 1987), originally developed for an entirely different problem — computing QR decompositions efficiently on parallel hardware. It turns out to solve DeltaNet's problem too.

Its original purpose is worth a sentence, because the reuse here is a genuinely elegant piece of cross-pollination. QR decomposition — a standard numerical linear algebra routine that factors a matrix into an orthogonal part and a triangular part — is classically computed by applying a sequence of Householder reflections, one per column, each zeroing out the entries below a pivot. Bischof and Van Loan's 1987 contribution was recognizing that this sequence of reflections, needed for early parallel computers, could be represented compactly enough to apply many of them at once instead of one at a time. Nothing in that 1987 paper has anything to do with attention, language models, or memory — it's a numerical-computing paper about matrix factorization. What makes it useful here is purely structural: DeltaNet's per-token update is a Householder reflection (Chapter 6 derived this), so a trick for combining many Householder reflections efficiently transfers over unchanged, thirty-seven years later, to a problem its original authors never imagined.

The trick, in plain words first

A product of many Householder matrices is, in general, a dense d×d matrix that looks like it has no special structure — expensive to build, expensive to store. The WY representation's insight is that this is an illusion: a product of C Householder reflections can always be written compactly as I minus a sum of just C outer products, using two skinny d×C matrices instead of ever forming the full dense d×d product. Concretely for DeltaNet: instead of multiplying together C separate (I − βkk^T) matrices one at a time, you compute two small matrices, call them W and U (one row per token in the chunk), and the entire chunk's net effect on the running state can be read off from those two skinny matrices directly — no d×d matrix ever gets materialized at all.

Building W and U: a within-chunk recursion, but a cheap one

Here is the part worth being honest about: computing the rows of W and U for a chunk still has a sequential dependency — row r depends on rows 1 through r−1 — because each new token's correction has to account for how the earlier tokens in the same chunk already modified things:

The crucial difference from Chapter 6's problem: this recursion runs over only C tokens — the chunk size, typically 64 or 128 — and it involves only the small intra-chunk dot products k_i·k_r, never the full incoming state S_[t] at all. It is exactly the kind of small, cheap forward-substitution that GPUs handle well, and because it doesn't touch the incoming state, every chunk's W and U can be computed in parallel with every other chunk's. Only the final carry — combining each chunk's local result with the state handed down from the previous chunk — has to happen in sequence, and that's only L/C steps, not L.

There's a cleaner way to see why this recursion is cheap, for readers comfortable with linear systems: the w_r equations above are exactly what you get from a lower-triangular C×C system of equations, built entirely from the chunk's own intra-chunk key dot products k_i·k_r. Solving a triangular system is a textbook operation — forward substitution, exactly the row-by-row process shown above, or equivalently a single explicit matrix inversion of a C×C matrix. Either way, the size of the problem being solved is C×C, not d×d — and since C (64 or 128) is typically much smaller than d can be for a wide model, this is a genuinely small linear-algebra problem, cheap enough to solve per chunk without becoming a bottleneck of its own.

Hand-worked: a full C=2 chunk, verified against pure sequential DeltaNet

Verify the trick actually reproduces the sequential answer, using small numbers. Take a fresh chunk (starting state S_[t] = 0, i.e. the very first chunk of a sequence), with two tokens:

WY construction, row by row. Row 1 has no earlier rows to correct for:

Row 2 corrects for row 1, using k₁·k₂ = 0.6:

python
import torch

k = torch.tensor([[1.,0.],[0.6,0.8]])
v = torch.tensor([[11.,4.],[9.,1.]])
beta = torch.tensor([0.8, 1.0])
C = 2

# WY construction: build w_r, u_r row by row (sequential, but only over C rows)
w = torch.zeros(C, 2); u = torch.zeros(C, 2)
for r in range(C):
    corr_k = sum(w[i] * (k[i] @ k[r]) for i in range(r))
    corr_v = sum(u[i] * (k[i] @ k[r]) for i in range(r))
    w[r] = beta[r] * (k[r] - corr_k)
    u[r] = beta[r] * (v[r] - corr_v)

# chunk-end state, starting state = 0 (first chunk of the sequence)
S = torch.zeros(2,2)
for r in range(C):
    S = S + torch.outer(u[r], k[r])
print(S)   # tensor([[11.032, 2.976],[2.648, -0.736]]) -- matches both hand derivations

# sequential check, same two tokens, one state update at a time
Sseq = torch.zeros(2,2)
for r in range(C):
    v_bar = Sseq @ k[r]
    Sseq = Sseq + beta[r] * torch.outer(v[r] - v_bar, k[r])
print(Sseq)  # tensor([[11.032, 2.976],[2.648, -0.736]]) -- identical to S above