The delta rule: linear attention for a million-token context

A million tokens of context sounds like a storage problem. It arrives as an arithmetic one.

In a transformer reads everything at once we let every token read every other token in a single parallel step, and that one trick carried the whole architecture. The price of it is easy to write down: for $n$ tokens of context, full self-attention scores every query against every key, $n^2$ pairs per layer, per head. At 128K tokens, already a long context by most standards, that works out to roughly $1.6 \times 10^{10}$ pair scores. At the 1M-token context Kimi K3 advertises, the bill is $10^{12}$: a trillion pairs, per layer per head, before the model has produced a single token of its own. And as we worked through in the KV-cache post, the compute has a twin: the key–value (KV) cache grows one slab per token, without bound, until it caps how many requests you can batch.

Both curves are straight lines on log–log axes; only the slopes differ. Stretching the context from 128K to 1M makes the sequence 7.8× longer, so the linear bill grows 7.8× while the quadratic one grows about 61×, and at 1M tokens the two curves sit six orders of magnitude apart.¹ You don't cross a gap like that with a faster kernel. You cross it by computing something else. Linear attention is that something else, and the delta rule, the real subject of this post, is what makes it work well enough to matter. It's also the family Kimi says K3's Kimi Delta Attention (KDA) belongs to, which is how a 2021 idea ended up carrying a production flagship in 2026.

Dropping the softmax

Write full attention for one output position $i$ and stare at it for a second:

The exponential does two jobs: it makes every score positive, and it sharpens the distribution so a good match wins decisively over a mediocre one. The denominator keeps the weights summing to one. Both are nice to have. But notice the shape of the computation: every pair $(i, j)$ shows up explicitly, and that explicitness is exactly where the $n^2$ comes from. There's no way to share work between query positions, because each one re-touches every key.

The kernel trick asks a cheeky question: what if we swapped the exponential for a similarity that factorises? Suppose we had a feature map $\phi$ with $\text{sim}(q, k) = \phi(q)^{\top} \phi(k)$. Then equation (1) becomes:

Look at what the regrouping buys. The numerator sums one outer product $\phi(k_j) v_j^{\top}$ per token over all $j$; the denominator sums the $\phi(k_j)$. Neither sum depends on $i$, so instead of recomputing them per query, we carry them forward as running accumulators, updated once per token. The work per token stops depending on how much past there is: linear in $n$ overall, with a fixed-size state instead of a growing cache. Katharopoulos et al. ran exactly this experiment in 2020 and showed a transformer still trains when you do it. Their paper's title, "Transformers are RNNs", tells you what they thought they'd found.

Drop the normaliser for a moment and watch the numerator's accumulator tick forward on its own. Written as a recurrence:

Read it as a little machine. $M$ is a matrix memory; each token writes its value $v_t$ under its key $k_t$ as an outer product; retrieval reads the memory with a key. No softmax, no per-token cache, just a $d \times d$ state carried forward. If writing outer products into a matrix smells like Hebbian learning, it should: Schmidhuber's fast-weight programmers did essentially this in the early nineties, and the paper we'll meet in a moment wears that lineage in its title. Some food for thought: the recurrent loop that attention replaced keeps turning up inside the mechanisms built to replace attention.

Collisions, smear, and the delta rule

A fixed-size memory with an additive write has an obvious failure mode, and it's the same one a hash table has: two keys land in the same slot. With equation (3), a second write to a key doesn't replace the first, it adds to it, so retrieval returns the sum of everything ever written there: a smear that matches no single value you actually stored. Let's make that concrete with the smallest memory worth playing with:

Step the script through in additive mode. "moon" is written to slot K2, then re-written with a new value; the slot now holds the sum of the two, and a query for "moon" returns a blur. Then "mars" collides into K2 as well, and the punchline row turns into nonsense: the memory thinks "moon" is the pile-up of three unrelated writes. Additive writes are order-dependent sludge, and every collision makes the sludge thicker.

The delta rule changes one thing. Before writing, read what the memory currently holds for this key, and write only the error:

This is the update Schlag, Irie and Schmidhuber proposed in 2021 in "Linear Transformers Are Secretly Fast Weight Programmers", and the model built on it is DeltaNet. The term $M_{t-1} k_t$ is the memory's current guess for this key; $v_t$ minus that guess is the surprise; the write stores only the surprise, scaled by a learning rate $\beta$. With $\beta = 1$ and well-separated keys the update is an exact replacement, which you can watch in the demo: flip to the delta rule and the same script leaves K2 holding precisely the latest write. A delta memory still can't hold two values under one key (nothing this size can), but it fails cleanly, with the newest write winning, instead of returning sludge. Probably the easiest way to feel the difference is to step to write 5 and flip the toggle back and forth.

Gating, and where KDA fits

Two refinements turn this toy into something you can train at frontier scale, and both are about controlled forgetting. Gated DeltaNet (Yang et al., 2024) multiplies the whole memory by a learned per-step gate $\alpha_t \in (0, 1)$ before each write, so old contents decay unless the model keeps refreshing them, and the retrieval inside the delta term reads from that already-decayed memory: $M_t = \alpha_t M_{t-1} + \beta_t \left( v_t - \alpha_t M_{t-1} k_t \right) k_t^{\top}$. The gate hands the model a dial between "keep everything" and "forget quickly", tuned per head, per token. If that dial sounds like the selectivity trick in Mamba's state-space model (SSM) update, it is very much the same idea in a different costume; the Mamba post tours that side of the family, so I won't repeat it here.

Which brings us to K3. Kimi's quickstart describes Kimi Delta Attention as "a hybrid linear attention mechanism", and the name plus the family resemblance points squarely at gated delta-rule linear attention of the kind we've just built up. The same blog post's architecture diagram places KDA blocks alongside something called Gated MLA, so "hybrid" presumably means the two interleaved: cheap linear-attention layers doing the long-range carrying, a few full-quality attention layers keeping exact recall honest. I say "presumably" deliberately.

Even at the family level, though, one thing is already clear: this is no longer a niche research lineage. Whatever the exact internals, a member of the linear-attention family is carrying the first open model in the 3-trillion-parameter class, at a 1M-token context. That alone makes the delta rule worth an afternoon. For the rest of the K3 story: the architecture tour takes the whole model apart (AttnRes, LatentMoE, the systems layer), and our launch-week benchmark shows what it actually does when you point real tasks at it.

The cache consequence

Back to systems, where this post started. The KV-cache post ended by calling linear attention the radical option: not a compression but a different computation. Here's what that difference buys at serving time. With full attention, decode step $t$ reads a cache of $t$ entries, so per-token cost and memory both grow with the context. With a linear-attention layer, decode reads and updates a fixed-size state: constant per-token cost, constant memory, no matter how long the context runs. Prefill still has to touch every prompt token once, and that's where caching re-enters the story: if the long prefix is unchanged between requests, you'd rather reuse its processed state than recompute a million tokens of it.

Conventional prefix caching stores per-token KV slabs and replays them. A recurrent state isn't shaped like that, and the K3 blog is blunt about the consequence: KDA "poses new challenges for conventional prefix caching", so Kimi contributed a matching implementation to the vLLM community, with "KDA with prefill cache" making reuse work anyway. The effort was clearly worth it to them, and the price list shows why. Cache-hit input is billed at $0.30 per million tokens (MTok) against $3.00 for a cache miss, a 10× gap, with output at $15.00 per MTok; Kimi reports a cache hit rate above 90% in coding workloads. A fixed state is what makes a million-token prefix cheap enough to reuse, and Kimi's own claim is the careful one: "KDA with prefill cache" lets them serve K3 at what they call "a highly competitive token price". Read the 10:1 spread as their pricing, enabled by that design, rather than a proven consequence of the fixed state alone.

Reading further

• Linear Transformers Are Secretly Fast Weight Programmers. Schlag, Irie & Schmidhuber, ICML 2021. The DeltaNet paper: the delta rule as an error-correcting write for linear attention, with the fast-weight lineage made explicit.
• Gated Delta Networks: Improving Mamba2 with Delta Rule. Yang, Kautz & Hatamizadeh, 2024. Adds the learned forget gate and shows the delta rule and Mamba2 are closer cousins than either community admitted.
• Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention. Katharopoulos et al., ICML 2020. The kernel-trick regrouping from equation (2), shown to still train.
• Mamba: Linear-Time Sequence Modeling with Selective State Spaces. Gu & Dao, 2023. The other branch of the family; our loop that beats attention post walks through it interactively.
• Kimi K3 and the K3 quickstart. The production instance: KDA, AttnRes, 1M context, and the pricing that makes the serving section concrete.

When the K3 technical report lands (the weights are due by 27 July), the first thing I'll be checking is how much of this family tree made it into KDA verbatim, and what the "hybrid" split looks like in practice. Watch this space.