The delta rule: read before you write

Linear attention writes by adding. Once the state is full, adding is the same as corrupting. The fix is one extra line: before writing at a key, look up what is already there and subtract it. That line turns out to be a projection, a Householder transform, and one step of gradient descent — all the same object seen from three directions.

Schlag, Irie and Schmidhuber named this the overcapacity regime, and argued the point directly: a model operating past its storage limit must be able to interact with its own memory — to decide which key–value associations to keep and which to delete. Adding new associations forever to a memory of fixed size will, they observed, inevitably hit a wall. Which is a precise description of chapter 2's ending.

The mechanism, in three lines

Linear attention's write was one line: S = S + k.T @ v. The delta rule makes it three.

v_old = k @ S                     # 1. what is currently stored at this key?
u     = beta * (v - v_old)        # 2. the delta — only what is actually new
S     = S + k.transpose(-1,-2) @ u  # 3. same outer-product write as before

Line 3 is unchanged from chapter 2. The entire difference is that the thing being written is no longer \(v\), but the discrepancy between \(v\) and what the memory already believes about this key. If the memory already says the right thing, \(u \approx 0\) and nothing is written. If it says something wrong, the wrong part gets cancelled out on the way in.

What that update really is

Substitute the three lines into one another and the whole step collapses:

β_t = σ(x W_β) ∈ (0,1) is a per-token, data-dependent write strength; k_t is normalised to unit length.

So this is still a linear recurrence — but the state is no longer just accumulated, it is multiplied by a transition matrix \(M_t\) first. And \(M_t\) is not an arbitrary matrix. It is the identity plus a rank-one correction, which makes its behaviour completely transparent.

Take any vector \(s\) and split it into the part along \(k_t\) and the part orthogonal to it. Since \(\|k_t\| = 1\):

Three readings of the same matrix, all useful:

Geometrically

At \(\beta = 1\), \(M_t = I - k^{\top}k\) is the orthogonal projection onto the hyperplane perpendicular to \(k\). It deletes the key's slot and nothing else. At \(\beta = 0\) it is the identity — no write. Between them it interpolates.

Algebraically

\(I - \beta k^{\top}k\) is a generalized Householder transform. The classical Householder reflection is the \(\beta = 2\) case. The whole family for \(\beta \in [0,2]\) is non-expansive, which is why this recurrence is stable: every eigenvalue lies in \([-1, 1]\), so the state cannot blow up over a long sequence. Restricting \(\beta\) to \((0,1)\) with a sigmoid keeps everything in \([0,1]\) — a strict contraction along \(k\), identity elsewhere.

Statistically

See the box below. It is one step of gradient descent.

Checking that it works

Read the state back at the key you just wrote, using \(\|k_t\|=1\):

A convex blend of what was stored and what you are storing, controlled entirely by \(\beta_t\). At \(\beta_t = 1\) the readback is \(v_t\) exactly — the old value is gone with no residue. That is the property linear attention could not offer at any capacity.

Note where the unit-norm assumption earned its place. Without it, \(k S = \|k\|^2 v\), so readback is scaled by the key's squared norm and the effective learning rate becomes \(\beta\|k\|^2\), which can exceed the stability bound. Hence the two lines you always see:

q = F.normalize(F.silu(q), dim=-1)   # unit length, so read-back is unscaled
k = F.normalize(F.silu(k), dim=-1)   # unit length, so β is the true step size
beta = torch.sigmoid(self.w_beta(x))  # per-token write strength in (0,1)

A worked example, small enough to check by hand

Two dimensions. Two tokens that use the same key with different values — the exact situation that breaks additive writes.

The last row is the point people miss. The delta rule does not merely overwrite — it overwrites locally. Facts stored in orthogonal directions are provably untouched, because \(M_t\) has eigenvalue exactly 1 there.

The query as a learned pointer

Nothing so far explains how a later token knows which key to ask for. The answer is that \(W_q\) and \(W_k\) read the same residual stream. If the phrase that established a fact produced a key in some direction, the model can learn to make a later phrase that needs that fact produce a query in the same direction. The keys are not addresses assigned by the architecture; they are content-derived, and matching them is a learned behaviour on both sides.

The read is a plain linear map, \(o_t = q_t S_t\), with no denominator at all — the running normaliser \(z\) from chapter 2 is gone, replaced by unit-normalised \(q,k\) and an RMSNorm on the output. A query pointing exactly at one stored key returns that value; a query between two keys returns a blend, weighted by the cosine with each. Soft retrieval is still available; it just is not forced.

What it costs

Fifty percent more arithmetic, identical memory, and the capacity ceiling from chapter 2 is no longer a hard wall — the state now reclaims a slot every time a key is rewritten. For the price of one matvec.