By 苏剑林 | July 21, 2026
In the article "Taylor Expansion of LogSumExp and Softmax", we introduced the approximate expansions of LogSumExp and Softmax, and derived a simple scheme for linearizing Softmax Attention. However, in that article, the resulting linear attention was merely in the form of Vanilla Linear Attention.
In this article, we go a step further and attempt to linearize Softmax Attention into a linear attention variant with the Delta Rule. Surprisingly, the final result is not the basic DeltaNet, but directly leads to Gated DeltaNet (GDN).
Problem Background
Consider the patterns of Attention output change with respect to Key and Value, given a Query $\boldsymbol{q}$. We introduce the notation:
\begin{equation}\boldsymbol{o}_t = \sum_{i=1}^t \alpha_{t, i} \boldsymbol{v}_i, \qquad \alpha_{t,i} = \frac{e^{\boldsymbol{q}\cdot \boldsymbol{k}_i}}{Z_t},\qquad Z_t = \sum_{i=1}^t e^{\boldsymbol{q}\cdot \boldsymbol{k}_i}\end{equation}
Using the Softmax expansion derived in "Taylor Expansion of LogSumExp and Softmax", we get $\alpha_{t,i} \approx \frac{1}{t}(1 + \boldsymbol{q}\cdot(\boldsymbol{k}_i - \bar{\boldsymbol{k}}_t))$. Substituting this into the above equation yields:
\begin{equation}\boldsymbol{o}_t \approx \frac{1}{t}\sum_{i=1}^t (1 + \boldsymbol{q}\cdot(\boldsymbol{k}_i - \bar{\boldsymbol{k}}_t))\boldsymbol{v}_i = \bar{\boldsymbol{v}}_t + \left(\frac{1}{t}\sum_{i=1}^t \boldsymbol{v}_i \boldsymbol{k}_i^{\top} - \bar{\boldsymbol{v}}_t\bar{\boldsymbol{k}}_t^{\top}\right)\boldsymbol{q}\label{eq:va-la}\end{equation}
where $\bar{\boldsymbol{k}}_t$ and $\bar{\boldsymbol{v}}_t$ are the mean vectors of the first $t$ Keys and Values, respectively. It can be seen that the final expression is a form of linear attention, specifically a variant of the earliest Vanilla Linear Attention (hereinafter referred to as "VaLA").
From "A Brief History of Linear Attention: From Imitation, Innovation to Feedback", we know that after VaLA came the Delta Rule and the corresponding DeltaNet, as well as subsequent extensions like GDN and KDA. Theoretically, these are all stronger linear attention mechanisms than VaLA. Therefore, can we directly linearize Softmax Attention into DeltaNet or GDN to obtain a better approximation?
Recursive Form
In fact, Softmax Attention itself can be written in the form of an RNN, which we discussed in "Spacetime Chapter: Viewing Attention as an RNN with Squared Complexity". This transformation is not difficult to understand:
\begin{equation}\boldsymbol{o}_t = \sum_{i=1}^t \alpha_{t, i} \boldsymbol{v}_i = \frac{\sum_{i=1}^t e^{\boldsymbol{q}\cdot \boldsymbol{k}_i} \boldsymbol{v}_i}{Z_t} = \frac{(\sum_{i=1}^{t-1} e^{\boldsymbol{q}\cdot \boldsymbol{k}_i} \boldsymbol{v}_i) + e^{\boldsymbol{q}\cdot \boldsymbol{k}_t} \boldsymbol{v}_t}{Z_t} = \frac{Z_{t-1} \boldsymbol{o}_{t-1} + e^{\boldsymbol{q}\cdot \boldsymbol{k}_t} \boldsymbol{v}_t}{Z_t}\end{equation}
Rearranging gives:
\begin{equation}\boldsymbol{o}_t = \boldsymbol{o}_{t-1} + \alpha_{t,t}(\boldsymbol{v}_t - \boldsymbol{o}_{t-1})\label{eq:attn-rnn}\end{equation}
Sharp-eyed readers might notice that the increment on the right side is in the form of $\boldsymbol{v}_t - \boldsymbol{o}_{t-1}$, which is "the difference between the new observation and the old prediction." This already hints at the Delta Rule. Note that so far we have not made any approximations; this formula is exact, suggesting that Softmax Attention has a natural connection with the Delta Rule.
It should also be pointed out that Equation \eqref{eq:attn-rnn} represents the RNN for a fixed $\boldsymbol{q}$. In reality, each position has different $\boldsymbol{q}_1, \boldsymbol{q}_2, \dots, \boldsymbol{q}_t$. These $t$ different $\boldsymbol{q}$'s must be substituted individually, running $1, 2, \dots, t$ steps respectively to get their outputs. The total complexity is $1+2+\dots+t=\mathcal{O}(t^2)$, which is the meaning of "squared complexity RNN."
The reason is that for different $\boldsymbol{q}$, the iteration process is independent; thus, each $\boldsymbol{q}$ must run a complete cycle, resulting in quadratic complexity. To achieve linearization, we must find a way to separate the calculation of $\boldsymbol{q}$, allowing the iteration to proceed solely within $\boldsymbol{k}$ and $\boldsymbol{v}$, and then use the state variables from the iteration process as output in conjunction with the $\boldsymbol{q}$ operation. In this way, the iteration process does not depend on $\boldsymbol{q}$, requiring only one pass, and the complexity is reduced to linear.
Linear Approximation
Next, we apply a first-order approximation to the Softmax for $\alpha_{t,t}$, obtaining:
\begin{equation}\begin{aligned}
\boldsymbol{o}_t \approx&\, \boldsymbol{o}_{t-1} + \frac{1}{t}(1 + \boldsymbol{q}\cdot(\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t))(\boldsymbol{v}_t - \boldsymbol{o}_{t-1}) \\
=&\, \left(1 - \frac{1}{t}\right)\boldsymbol{o}_{t-1} + \frac{1}{t}\boldsymbol{v}_t + \frac{1}{t}(\boldsymbol{v}_t - \boldsymbol{o}_{t-1})(\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t)^{\top}\boldsymbol{q}
\end{aligned}\end{equation}
Some readers might wonder: didn't we just express dissatisfaction with the accuracy of VaLA derived from the first-order approximation? Why use it again? The difference lies in the fact that previously we needed to approximate $\alpha_{t,i}$ for all pairs of $(t,i)$. Now, we only need to approximate $\alpha_{t,t}$—essentially only the diagonal part. The approximation burden is significantly reduced, and the accuracy increases accordingly.
Another perspective helps us understand this better. First rewrite $\alpha_{t,i}$ as:
\begin{equation}\alpha_{t,i} = \frac{e^{\boldsymbol{q}\cdot \boldsymbol{k}_i}}{Z_t} = \frac{e^{\boldsymbol{q}\cdot \boldsymbol{k}_i}}{Z_i} \frac{Z_i}{Z_{i+1}}\cdots\frac{Z_{t-1}}{Z_t} = \alpha_{i,i}(1-\alpha_{i+1,i+1})\cdots (1-\alpha_{t,t})\end{equation}
This identity tells us that for $t > i$, $\alpha_{t,i}$ can be decomposed into the product of $\alpha_{i,i}$ and a series of $(1-\alpha_{j,j})$. Directly performing a first-order approximation on $\alpha_{t,i}$ versus approximating $\alpha_{i,i}$ and $\alpha_{j,j}$ separately is like the difference between $e^{a+b}\approx 1 + a + b$ and $e^a e^b \approx (1+a)(1+b)=1+a+b+ab$. The latter introduces cross-terms, achieving higher precision.
Separating Iteration
However, even with the approximation, the recursion remains quadratic. We haven't yet reached the goal of separating $\boldsymbol{q}$. To move closer, we seek a solution of the following form:
\begin{equation}\boldsymbol{o}_t \approx \boldsymbol{A}_t \boldsymbol{q} + \boldsymbol{b}_t\end{equation}
where $\boldsymbol{A}_t$ and $\boldsymbol{b}_t$ are independent of $\boldsymbol{q}$, with the convention $\boldsymbol{A}_0=\boldsymbol{0}, \boldsymbol{b}_0=\boldsymbol{0}$. Of course, the exact solution doesn't look like this; we are purposefully seeking a solution in this form to serve as an approximation. Substituting this into the previous recursive form gives:
\begin{equation}\begin{aligned}
\boldsymbol{A}_t \boldsymbol{q} + \boldsymbol{b}_t \approx&\, \left(1-\frac{1}{t}\right)(\boldsymbol{A}_{t-1} \boldsymbol{q} + \boldsymbol{b}_{t-1}) + \frac{1}{t}\boldsymbol{v}_t + \frac{1}{t}(\boldsymbol{v}_t - \boldsymbol{b}_{t-1} - \boldsymbol{A}_{t-1} \boldsymbol{q})(\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t)^{\top}\boldsymbol{q}
\end{aligned}\end{equation}
An intuitive idea is to separate the iterations of $\boldsymbol{A}_t$ and $\boldsymbol{b}_t$ according to the order of $\boldsymbol{q}$, thus obtaining recursive formulas for $\boldsymbol{A}_t$ and $\boldsymbol{b}_t$. However, while the left side has at most a first-order term of $\boldsymbol{q}$, the right side contains a second-order term $\boldsymbol{A}_{t-1} \boldsymbol{q}(\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t)^{\top}\boldsymbol{q}$. Complete separation is not possible. For now, we can only get:
\begin{align}
\boldsymbol{b}_t =&\, \left(1-\frac{1}{t}\right)\boldsymbol{b}_{t-1} + \frac{1}{t}\boldsymbol{v}_t \\
\boldsymbol{A}_t =&\, \left(1-\frac{1}{t}\right)\boldsymbol{A}_{t-1} + \frac{1}{t}(\boldsymbol{v}_t - \boldsymbol{b}_{t-1} - \boldsymbol{A}_{t-1} \boldsymbol{q})(\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t)^{\top} \label{eq:A-t}
\end{align}
Clearly, the iteration of $\boldsymbol{b}_t$ is essentially calculating the cumulative mean of $\boldsymbol{v}_t$, so we can directly write $\boldsymbol{b}_t = \bar{\boldsymbol{v}}_t$. The problem is that $\boldsymbol{q}$ appears on the right side of Equation \eqref{eq:A-t}, so the assumption that $\boldsymbol{A}_t$ is independent of $\boldsymbol{q}$ does not hold.
Simple Omission
One simple approach is to treat $\boldsymbol{q}$ as a small quantity and omit it directly, leading to:
\begin{equation}\boldsymbol{A}_t = \left(1-\frac{1}{t}\right)\boldsymbol{A}_{t-1} + \frac{1}{t}(\boldsymbol{v}_t - \bar{\boldsymbol{v}}_{t-1})(\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t)^{\top}\end{equation}
This also takes the form of a cumulative mean, which solves to:
\begin{equation}\boldsymbol{A}_t = \frac{1}{t}\sum_{i=1}^t (\boldsymbol{v}_i - \bar{\boldsymbol{v}}_{i-1})(\boldsymbol{k}_i - \bar{\boldsymbol{k}}_i)^{\top}\quad\Rightarrow\quad\boldsymbol{o}_t \approx \bar{\boldsymbol{v}}_t + \left(\frac{1}{t}\sum_{i=1}^t (\boldsymbol{v}_i - \bar{\boldsymbol{v}}_{i-1})(\boldsymbol{k}_i - \bar{\boldsymbol{k}}_i)^{\top}\right)\boldsymbol{q}\label{eq:va-la-2}\end{equation}
This looks like a new variant of VaLA, but it is actually mathematically equivalent to Equation \eqref{eq:va-la}! To prove this, one only needs to verify:
\begin{equation}\begin{aligned}
t \bar{\boldsymbol{v}}_t \bar{\boldsymbol{k}}_t^{\top} - (t-1) \bar{\boldsymbol{v}}_{t-1} \bar{\boldsymbol{k}}_{t-1}^{\top} =&\, \underbrace{((t-1)\bar{\boldsymbol{v}}_{t-1} + \boldsymbol{v}_t)}_{t \bar{\boldsymbol{v}}_t}\bar{\boldsymbol{k}}_t^{\top} - \bar{\boldsymbol{v}}_{t-1} \underbrace{(t \bar{\boldsymbol{k}}_t - \boldsymbol{k}_t)}_{(t-1)\bar{\boldsymbol{k}}_{t-1}}{}^{\top} = -\bar{\boldsymbol{v}}_{t-1}\bar{\boldsymbol{k}}_t^{\top} + \boldsymbol{v}_t\bar{\boldsymbol{k}}_t^{\top} + \bar{\boldsymbol{v}}_{t-1}\boldsymbol{k}_t^{\top}
\end{aligned}\end{equation}
Thus:
\begin{equation}\sum_{i=1}^t \boldsymbol{v}_i \boldsymbol{k}_i^{\top} - t\bar{\boldsymbol{v}}_t\bar{\boldsymbol{k}}_t^{\top} = \sum_{i=1}^t \boldsymbol{v}_i \boldsymbol{k}_i^{\top} - \sum_{i=1}^t (-\bar{\boldsymbol{v}}_{i-1}\bar{\boldsymbol{k}}_i^{\top} + \boldsymbol{v}_i\bar{\boldsymbol{k}}_i^{\top} + \bar{\boldsymbol{v}}_{i-1}\boldsymbol{k}_t^{\top}) = \sum_{i=1}^t (\boldsymbol{v}_i - \bar{\boldsymbol{v}}_{i-1})(\boldsymbol{k}_i - \bar{\boldsymbol{k}}_i)^{\top}\end{equation}
This proves that Equation \eqref{eq:va-la} can be transformed identically into Equation \eqref{eq:va-la-2}.
Error Principle
A more precise approach is to replace $\boldsymbol{q}$ with a suitable quantity $\boldsymbol{c}$. Intuitively, replacing $\boldsymbol{q}$ with $\boldsymbol{q}_t$ might seem like a natural and better choice, but that is not the case. Let's return to Equation \eqref{eq:attn-rnn}, writing $\boldsymbol{q}$ explicitly:
\begin{equation}\boldsymbol{o}_t(\boldsymbol{q}) = \boldsymbol{o}_{t-1}(\boldsymbol{q}) + \alpha_{t,t}(\boldsymbol{q})\cdot(\boldsymbol{v}_t - \boldsymbol{o}_{t-1}(\boldsymbol{q}))\end{equation}
Our goal is to replace the last $\boldsymbol{o}_{t-1}(\boldsymbol{q})$ with some $\boldsymbol{o}_{t-1}(\boldsymbol{c})$, so that the second-order term of $\boldsymbol{q}$ does not appear during the approximation expansion. The error resulting from this is:
\begin{equation}\alpha_{t,t}(\boldsymbol{q})\cdot(\boldsymbol{o}_{t-1}(\boldsymbol{q}) - \boldsymbol{o}_{t-1}(\boldsymbol{c}))\end{equation}
Why is $\boldsymbol{c}=\boldsymbol{q}_t$ not necessarily good? Because it only ensures the error is minimized for the single position $\boldsymbol{q}=\boldsymbol{q}_t$. However, the state variable at this moment must also serve subsequent $\boldsymbol{q}_{t+1}, \boldsymbol{q}_{t+2}, \dots$. Therefore, the ideal goal is to "make the error as small as possible for any possible $\boldsymbol{q}$," which is the "Minimum Error Principle" we use to find $\boldsymbol{c}$.
This error term has a multiplicative form: if $\alpha_{t,t}(\boldsymbol{q})$ is already small, the product will not be large; conversely, if $\alpha_{t,t}(\boldsymbol{q})$ is very large, then $\boldsymbol{o}_{t-1}(\boldsymbol{q}) - \boldsymbol{o}_{t-1}(\boldsymbol{c})$ must be small to reduce the error. From this, we obtain a "Maximin Strategy": first find the $\boldsymbol{q}^*$ that maximizes $\alpha_{t,t}(\boldsymbol{q})$, and then set $\boldsymbol{c}=\boldsymbol{q}^*$ to make the error zero at that point (i.e., $\boldsymbol{o}_{t-1}(\boldsymbol{q}) - \boldsymbol{o}_{t-1}(\boldsymbol{c})=\boldsymbol{0}$). This balances the errors on both sides of large and small $\alpha_{t,t}(\boldsymbol{q})$.
The Grand Finale
According to the linear approximation $\alpha_{t,t} \approx \frac{1}{t}(1 + \boldsymbol{q}\cdot(\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t))$, the direction of $\boldsymbol{q}$ that maximizes it is $\frac{\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t}{\Vert\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t\Vert}$. However, since the magnitude can be arbitrarily large, $\alpha_{t,t}$ technically has no maximum. To get a finite result, we need to constrain the magnitude of $\boldsymbol{q}$. For simplicity, assuming the magnitudes of $\boldsymbol{q}$ and $\boldsymbol{k}$ are comparable, we can directly take:
\begin{equation}\boldsymbol{q}^* = \boldsymbol{k}_t - \bar{\boldsymbol{k}}_t\end{equation}
Substituting this minimalist form into Equation \eqref{eq:A-t} yields:
\begin{equation}\begin{aligned}
\boldsymbol{A}_t =&\, \left(1-\frac{1}{t}\right)\boldsymbol{A}_{t-1} + \frac{1}{t}\big(\boldsymbol{v}_t - \bar{\boldsymbol{v}}_{t-1} - \boldsymbol{A}_{t-1} (\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t)\big)(\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t)^{\top} \\
=&\, \boldsymbol{A}_{t-1}\left(\left(1-\frac{1}{t}\right)\boldsymbol{I} - \frac{1}{t} (email_t - \bar{\boldsymbol{k}}_t)(\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t)^{\top}\right) + \frac{1}{t}(\boldsymbol{v}_t - \bar{\boldsymbol{v}}_{t-1})(\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t)^{\top}
\end{aligned}\end{equation}
This is exactly the form of Gated DeltaNet (GDN)! The standard form of GDN is:
\begin{equation}\boldsymbol{S}_t = \boldsymbol{S}_{t-1} (\alpha_t (\boldsymbol{I} - \beta_t\boldsymbol{k}_t\boldsymbol{k}_t^{\top})) + \beta_t\boldsymbol{v}_t\boldsymbol{k}_t^{\top}\end{equation}
The difference is whether $\alpha_t$ is multiplied by $(\boldsymbol{I} - \beta_t\boldsymbol{k}_t\boldsymbol{k}_t^{\top})$ or just by $\boldsymbol{I}$, but this difference is not essential, and the two can be converted into each other. Thus, we have completed the approximate transformation of Softmax Attention into Delta Rule-based attention, with the final output being:
\begin{equation}\boldsymbol{o}_t = \boldsymbol{A}_t \boldsymbol{q}_t + \bar{\boldsymbol{v}}_t\end{equation}
Summary
Starting from the premise that "Softmax Attention is an RNN with squared complexity," this article first discovered that its recursive increment naturally takes a Delta Rule form. By applying a first-order approximation to the Softmax diagonal elements and then using the "Minimum Error Principle" to find a substitute for the residual $\boldsymbol{q}$, we successfully linearized Softmax Attention into the form of Gated DeltaNet.
(Note: This article was completed under the guidance of Kimi K3.)