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. And that line is not a heuristic anyone chose: two independent requirements force it, a third derives it as gradient descent, and Widrow and Hoff published it in 1960.

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 += kᵀv. The delta rule makes it three.

from einops import einsum
# S : b h dk dv — the state is a linear map from keys to values, one per head

k_t         = F.normalize(k[:, :, t], dim=-1)                # b h dk   unit length, see below
v_t, beta_t = v[:, :, t], beta[:, :, t]                    # b h dv , b h

v_old = einsum(k_t, S,   'b h dk, b h dk dv -> b h dv')    # 1. read: contract dk away
u     = einsum(beta_t, v_t - v_old, 'b h, b h dv -> b h dv')# 2. the delta, scaled by β
S     = S + einsum(k_t, u, 'b h dk, b h dv -> b h dk dv')  # 3. rank-one outer-product write

The einsum strings are the whole explanation. Line 1 contracts the dk axis and leaves dv — a read, entering on the key side and exiting on the value side. Line 3 contracts nothing and produces both axes — an outer product, the only shape of write this state accepts.

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.

Where this update comes from

Written cold, \(u = \beta\,(v - kS)\) looks like a heuristic somebody tried and kept. It is neither arbitrary nor new. Two independent requirements force exactly this expression, a third derives it as gradient descent, and the rule itself dates to 1960.

The genealogy

The name is literal: \(\delta\) is the discrepancy between what you wanted and what you got, and the update is proportional to it. The 2021 contribution was an identification, not an invention — which is what makes the lineage worth knowing. If your state is a correlation matrix memory, every pathology and every remedy from the 1970s associative-memory literature transfers unchanged.

Route 1 — exact readback forces it

Start from what the hardware allows. The recurrence adds one outer product per token, so whatever gets written has the shape \(k^{\top}a\) — the key is fixed by the token, and the only free choice is the vector \(a\):

Now demand the property you actually want, which is that reading this key returns this value:

Substitute and solve. With \(\|k\| = 1\), so that \(k k^{\top} = 1\):

\(a\) is not chosen. It is solved for. Given a rank-one write at key \(k\) and a demand for exact readback, the delta is the only vector you can write. There is no design freedom left to exercise.

Route 2 — minimum disruption forces it too

Now drop the rank-one restriction entirely and ask a different question. Among all matrices \(S'\) that satisfy the new constraint, which one is closest to the memory you already have? This is the least-change principle, and it is the natural formalisation of "install this fact without breaking anything else":

Write \(\Delta = S' - S\) and \(r = v - kS\). The constraint becomes \(k\Delta = r\): an underdetermined linear system, whose minimum-norm solution is given by the pseudo-inverse of \(k\):

The same expression again, from a requirement that shares no vocabulary with the first one. And this route explains the property the worked example demonstrates below: the delta rule does not damage neighbouring memories because it is, by construction, the smallest possible change to \(S\) that installs the association. Not empirically gentle — provably minimal in Frobenius norm.

Route 3 — it is one step of gradient descent

Pose the same demand as a loss instead of a constraint. Map this key to this value, scored by squared error:

Take one gradient step with step size \(\beta\):

Which is the update, with \(\beta\) revealed as a learning rate. Route 1 gets it by solving the constraint exactly; route 3 gets it by taking one step toward the constraint. They agree because for a single linear constraint, one step of size 1 lands on the solution.

So why β at all?

If exactness forces \(a = v - kS\), scaling it by anything less than 1 makes the readback inexact on purpose. That is the point:

β = 1 — full overwrite

The token's assertion is trusted completely. Readback returns \(v\) exactly and the previous contents of the slot are gone.

β = 0 — no write

\(M_t = I\), the state passes through untouched, the token contributes nothing to memory. This is a learned write gate, and it is the reason β must be data-dependent rather than a constant.

0 < β < 1 — partial update

Readback becomes a convex blend of old and new. The memory accumulates evidence about a key rather than replacing it, which is the right behaviour when a token is weak evidence rather than a definition.

And there is a stability reason, taken up immediately below: constraining \(\beta\) to \((0,1)\) with a sigmoid bounds every eigenvalue of the transition matrix, which is what keeps the recurrence from diverging over a hundred thousand steps.

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

One step of gradient descent on the read error, as derived above — with \(\beta_t\) as the learning rate.

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)   # b h n dk — unit length, so read-back is unscaled
k    = F.normalize(F.silu(k), dim=-1)   # b h n dk — unit length, so β is the true step size
beta = torch.sigmoid(self.w_beta(x))    # b h n    — 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.