The Delta Rule in Linear Attention: Memory Updates as Online Gradient Descent
Softmax attention scales quadratically with sequence length, while linear attention restores linear complexity by maintaining a fixed-size recurrent state. However, its additive update can only accumulate information and cannot overwrite existing associations, which limits associative recall and key-value retrieval. This article shows how the Delta Rule closes that gap with an erase-then-write update, demonstrates that a single Delta update is mathematically identical to one step of online gradient descent on an instantaneous reconstruction loss, and interprets the coefficient matrix (I − β k kᵀ) as an orthogonal projection onto the complement of the key direction. It also frames the state matrix as an online least-squares solver, a rewritable key-value store, and a set of fast weights, and covers practical engineering concerns such as chunked parallelism, numerical stability, and key normalization.
Background: Why Linear Attention Needs a “Forgetting” Memory
The computation and memory cost of standard Softmax attention grow quadratically with sequence length, which is a hard bottleneck for modeling long documents and long contexts. The core idea behind linear attention is to replace the exponential kernel with a decomposable kernel, rewriting “weighting every historical token one by one” as “maintaining a fixed-size state and updating it recurrently.” This reduces the time complexity of sequence processing from quadratic to linear.
Let the state be a matrix S ∈ R^{d_k × d_v}. Traversing the sequence performs an additive update:
S_t = S_{t-1} + k_t · v_tᵀ # state accumulationo_t = q_tᵀ · S_t # read the output with the current query
The problem is that this update “only adds, never subtracts.” Every new token stacks the outer product k_t · v_tᵀ onto the state, and old associations are never overwritten or erased. When the same key reappears in the sequence but its corresponding value has changed, the memory can only blend the old and new signals together and cannot perform a “rewrite.” This lack of forgetting and rewriting is the fundamental reason pure additive linear attention underperforms on associative recall and key-value retrieval tasks. The Delta Rule is introduced precisely to fill this gap.
From Additive Updates to the Delta Rule
The core idea of the Delta Rule is “erase first, then write”: before writing a new key-value association, first subtract the old association already stored in memory for that key, then write in the new content according to the error. Its update takes the form:
S_t = (I − β_t · k_t · k_tᵀ) · S_{t-1} + β_t · k_t · v_tᵀ
Here β_t is the write strength (which can also be understood as a learning rate). Rewriting it in an “error-driven” form makes the essence clearer:
S_t = S_{t-1} + β_t · k_t · (v_t − S_{t-1}ᵀ · k_t)ᵀ
The term (v_t − S_{t-1}ᵀ · k_t) inside the parentheses is the error e_t between “using the current memory to predict the value for the key” and the “true value.” In other words, a large correction is produced only when the old memory’s prediction is wrong; if the old association is already correct, the error approaches zero and the state barely moves. This contrasts sharply with the “unconditional stacking” of the additive update—one makes selective corrections, the other accumulates indiscriminately.
A schematic implementation is shown below:
import torchdef delta_rule_step(S, k, v, beta):"""S: [d_k, d_v] current memory statek: [d_k] current key (typically L2-normalized in practice)v: [d_v] current valuebeta: scalar write strength / learning rate"""v_pred = k @ S # predict the value for the current key using the old memoryerr = v - v_pred # prediction errorS = S + beta * torch.outer(k, err) # rewrite the state according to the errorreturn S
Appendix 1: The Memory Update Is Equivalent to Online Gradient Descent
This “erase-then-write” update is not cobbled together from heuristics; it is exactly the result of one step of online gradient descent.
Suppose our goal is to make the state S act as a “linear map” that can reconstruct, as accurately as possible, the value v bound to any key k. For each arriving token, define an instantaneous reconstruction loss:
L_t(S) = ½ · ‖ Sᵀ · k_t − v_t ‖²
Take the gradient with respect to S:
∇_S L_t = k_t · (Sᵀ k_t − v_t)ᵀ = k_t k_tᵀ S − k_t v_tᵀ
Taking one gradient-descent step with step size β_t:
S_t = S_{t-1} − β_t · ∇_S L_t= (I − β_t k_t k_tᵀ) · S_{t-1} + β_t k_t v_tᵀ
The result is word-for-word identical to the Delta Rule given above. This tells us that:
- A “memory” is essentially a set of learnable parameters that are continuously optimized online;
- A “key-value association” is fitting
Sas a linear-regression / least-squares solver that mapsk → v; - At every step of the sequence, a “single-sample online learning step with forgetting” is performed.
This view unifies “attention” and “learning”: reading the output o_t = q_tᵀ S_t is inference over a new query using the map that has been trained online, while the state update continuously fits the latest sample. This is also why such mechanisms are often categorized under the “test-time training / fast weights” paradigm.
Appendix 2: Projection onto the Orthogonal Complement
Now consider the geometric meaning of the coefficient matrix (I − β_t k_t k_tᵀ). When the key is unit-normalized (‖k_t‖ = 1) and β_t = 1, let P = I − k_t k_tᵀ. It satisfies:
- Symmetry:
Pᵀ = P - Idempotency:
P² = P, andP · k_t = k_t − k_t(k_tᵀk_t) = 0
Being symmetric and idempotent is precisely the definition of an orthogonal projection matrix. Its effect is to remove the component of any vector “along the k_t direction,” keeping only the part perpendicular to k_t. Therefore, the meaning of (I − β_t k_t k_tᵀ) S_{t-1} is very intuitive: first erase the entire old association stored in the key direction (project onto the orthogonal complement of k_t), and then + β_t k_t v_tᵀ writes the new value back into that direction.
More generally:
- When
β_t = 1 / (k_tᵀ k_t), you get a strict orthogonal projection, achieving a “complete erase and rewrite” of the old association; - When
β_tis smaller, it performs only a “partial erase, partial accumulation,” sitting between pure additive updating and full rewriting.
As a result, β_t is no longer an obscure hyperparameter; it has a clear meaning: it controls the strength of forgetting / rewriting the old association. The larger β_t is, the more the memory tends toward “overwrite-style” behavior; the smaller it is, the more it tends toward “accumulate-style” behavior. This provides a theoretical basis for adaptively tuning memory behavior according to the data distribution.
Appendix 3: What Exactly Is This State?
Combining the previous two sections, the state S can be understood as an overlay of three equivalent views:
- An online least-squares solver: It continuously fits
(k, v)samples into a linear mapk → v, and the output layerq_tᵀ S_tis the prediction for a new query. - A rewritable key-value association store: Unlike additive memory, which can only accumulate, it can erase old values along the key direction and write new values, so it naturally supports scenarios where “the same slot is repeatedly updated.”
- A set of fast weights: The sequence-processing procedure itself updates this set of weights, which is equivalent to internalizing “part of the learning” into the forward computation—this is also where it connects to the test-time training paradigm.
Understanding it at this level explains why such mechanisms often outperform pure additive linear attention on long-range retrieval, state tracking, and tasks that require repeatedly modifying information: they possess a genuine “write / overwrite” capability, rather than piling up history indiscriminately.
Engineering Practice: Chunked Parallelism and Stability
Although the recurrent form is intuitive, updating token by token serially sacrifices parallelism. In practice, a chunk-wise parallel strategy is usually adopted: split the sequence into blocks of moderate length, perform the computation within each block with parallel tensor operations, and pass the state S between blocks. This preserves linear complexity while fully exploiting hardware parallelism, significantly shortening training time for long sequences.
Three points deserve attention in practice:
- Numerical stability: A
β_tthat is too large, or repeated erase/write cycles, can cause state drift. A common approach is to combine normalization and gating to constrain the write strength within a reasonable range. - Key normalization: Because the projection/erase logic is sensitive to the key’s magnitude,
k_tis typically L2-normalized, which makes the semantics ofβ_tmore stable and more interpretable. - Observability at inference time: In online serving, this kind of stateful recurrent model is well suited to using a logging service to record state evolution, and to tracking inference latency and resource utilization together with monitoring alerts. Model files and checkpoints can be centrally managed with object storage, making canary releases and rollbacks easier.
It should be emphasized that the above are general engineering practices. Specific parameters (chunk size, write-strength values, etc.) should be determined through experimentation based on data scale, sequence distribution, and hardware conditions, and should not be copied blindly.
Summary
The additive update of linear attention “only adds, never subtracts” and lacks a rewriting capability; Delta-rule-based memory updates fill this gap through an “erase first, then write” mechanism. This article analyzed its essence from three angles:
- Optimization view: One Delta update is equivalent to one step of online gradient descent on the instantaneous reconstruction loss;
- Geometric view: The coefficient matrix
(I − β k kᵀ)is an orthogonal projection that projects the memory onto the orthogonal complement of the key, erasing first and then writing; - Paradigm view: The state matrix
Scan be understood as an online least-squares solver, a rewritable association store, or a set of fast weights.
Unifying attention and online learning within the same recurrence provides a clearer mathematical explanation and a solid methodological foundation for efficient long-sequence modeling with tunable write strength and chunk-wise parallelism.
