Turning Softmax Attention into Gated DeltaNet
In Taylor Expansions of LogSumExp and Softmax we introduced approximate expansions of LogSumExp and Softmax, and from them derived a simple scheme for linearizing Softmax Attention. In that post, however, the resulting linear attention was just an instance of Vanilla Linear Attention.
In this post we go a step further, and try to linearize Softmax Attention into a linear-attention variant equipped with a Delta Rule. Surprisingly, what we end up with is not the basic DeltaNet, but directly Gated DeltaNet (GDN).
Background
Consider how the attention output changes with the Keys and Values, for a fixed Query $\boldsymbol{q}$. 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}more
Using the Softmax expansion introduced in Taylor Expansions of LogSumExp and Softmax, we get $\alpha_{t,i} \approx \frac{1}{t}(1 + \boldsymbol{q}\cdot(\boldsymbol{k}_i - \bar{\boldsymbol{k}}_t))$, which substituted into the above gives
\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,\bar{\boldsymbol{v}}_t$ are respectively the means of the first $t$ Key and Value vectors. We can see that the final expression is a linear attention — in fact a variant of the earliest Vanilla Linear Attention (abbreviated "VaLA" below).
From A Brief History of Linear Attention: From Imitation and Innovation to Feeding Back we know that after VaLA came the Delta Rule and the corresponding DeltaNet, along with later extensions such as GDN and KDA, all of which are theoretically stronger linear attention mechanisms than VaLA. So can we linearize Softmax Attention directly into DeltaNet, GDN, and the like, in order to get a better approximation?
Recursive form
In fact, Softmax Attention itself can be written as an RNN, something we already discussed in The Chapter of Space and Time: Viewing Attention as a Quadratic-Complexity RNN, and the conversion is not hard 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 may already have noticed that the increment on the right-hand side has the form $\boldsymbol{v}_t - \boldsymbol{o}_{t-1}$, i.e. "new observation minus old prediction," which already faintly resembles a Delta Rule. Note that so far we have made no approximation at all — this expression is exact — which hints that Softmax Attention and the Delta Rule share some natural connection.
It should also be pointed out that equation $\eqref{eq:attn-rnn}$ is an RNN with $\boldsymbol{q}$ fixed, whereas in reality each position has a different $\boldsymbol{q}_1,\boldsymbol{q}_2,\cdots,\boldsymbol{q}_t$; all $t$ different values of $\boldsymbol{q}$ must be plugged in, each run through $1,2,\cdots,t$ steps to get its own output, giving a total complexity of $1+2+\cdots+t=\mathcal{O}(t^2)$. This is the meaning of "quadratic-complexity RNN."
The reason for this is that for different values of $\boldsymbol{q}$, the iteration process is independent, so each $\boldsymbol{q}$ must be run through a full cycle, giving overall quadratic complexity. To linearize this, we need to find a way to separate out the computation involving $\boldsymbol{q}$, so that the iteration proceeds purely within $\boldsymbol{k},\boldsymbol{v}$, and then combine the state variable from the iteration process with the $\boldsymbol{q}$ computation as the output. In this way, the iteration process no longer depends on $\boldsymbol{q}$, needs to be run only once, and the complexity drops to linear.
Linear approximation
Next, we apply the first-order Softmax approximation to $\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 may object: didn't we just criticize the first-order Softmax approximation for giving the insufficiently accurate VaLA? Why use a first-order approximation again now? The difference is that before we needed to approximate $\alpha_{t,i}$, with the subscript ranging over all pairs $(t,i)$, whereas now we only need to approximate $\alpha_{t,t}$, i.e. only the diagonal part — the approximation burden is greatly reduced, and the accuracy correspondingly increases.
There is another perspective that 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 a product of $\alpha_{i,i}$ and a series of $1-\alpha_{j,j}$ terms. Applying the first-order approximation directly to $\alpha_{t,i}$, versus approximating $\alpha_{i,i}$ and $\alpha_{j,j}$ separately, is analogous to 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 can introduce cross terms, achieving higher accuracy.
Separating the iteration
However, even after this approximation, the recursion is still quadratic — we have not yet achieved the goal of separating out $\boldsymbol{q}$. To get closer to that goal, we look for 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,\boldsymbol{b}_t$ is independent of $\boldsymbol{q}$, with the convention $\boldsymbol{A}_0=\boldsymbol{0}, \boldsymbol{b}_0=\boldsymbol{0}$. Of course, the exact solution certainly does not look like this — we are deliberately searching for a solution of this form to serve as an approximation to the exact one. Substituting it into the aforementioned recursion 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 iteration for $\boldsymbol{A}_t,\boldsymbol{b}_t$ by order in $\boldsymbol{q}$, which would let us obtain a recursion for $\boldsymbol{A}_t,\boldsymbol{b}_t$. However, the left-hand side has at most a first-order term in $\boldsymbol{q}$, while the right-hand side contains a second-order term like $\boldsymbol{A}_{t-1} \boldsymbol{q}(\boldsymbol{k}_t - \bar{\boldsymbol{k}}_t)^{\top}\boldsymbol{q}$, so the separation cannot be carried out cleanly. For now we can only obtain
\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 for $\boldsymbol{b}_t$ is actually computing a cumulative average of $\boldsymbol{v}_t$, so we can directly write down $\boldsymbol{b}_t = \bar{\boldsymbol{v}}_t$. The problem is that $\boldsymbol{q}$ appears on the right-hand side of equation $\eqref{eq:A-t}$, so the assumption that $\boldsymbol{A}_t$ is independent of $\boldsymbol{q}$ cannot hold.
A naive omission
One simple approach is to treat $\boldsymbol{q}$ as a small quantity and simply drop it, giving
\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 again has the form of a cumulative average, and solving it gives
\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 VaLA variant, but in fact it is completely equivalent to equation $\eqref{eq:va-la}$! To prove this, we only need 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}
hence
\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}_i^{\top}) = \sum_{i=1}^t (\boldsymbol{v}_i - \bar{\boldsymbol{v}}_{i-1})(\boldsymbol{k}_i - \bar{\boldsymbol{k}}_i)^{\top}\end{equation}
This is an identity transformation from equation $\eqref{eq:va-la}$ to equation $\eqref{eq:va-la-2}$.
A minimum-error principle
A more precise approach is to replace $\boldsymbol{q}$ with some suitable quantity $\boldsymbol{c}$. Intuitively, replacing $\boldsymbol{q}$ with $\boldsymbol{q}_t$ might seem like a natural and reasonably good choice, but this turns out not to be the case. Let's go back to equation $\eqref{eq:attn-rnn}$ and write $\boldsymbol{q}$ out explicitly as
\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 final $\boldsymbol{o}_{t-1}(\boldsymbol{q})$ with some $\boldsymbol{o}_{t-1}(\boldsymbol{c})$, so that when we later perform the approximate expansion, no second-order term in $\boldsymbol{q}$ appears. The error this produces is
\begin{equation}\alpha_{t,t}(\boldsymbol{q})\cdot(\boldsymbol{o}_{t-1}(\boldsymbol{q}) - \boldsymbol{o}_{t-1}(\boldsymbol{c}))\end{equation}
Why might $\boldsymbol{c}=\boldsymbol{q}_t$ not be a good choice? Because it only guarantees the smallest error at this single position $\boldsymbol{q}=\boldsymbol{q}_t$, but the current state variable actually also needs to serve the subsequent $\boldsymbol{q}_{t+1},\boldsymbol{q}_{t+2},\cdots$. So the ideal target is "for any possible $\boldsymbol{q}$ that may arise, the error should be as small as possible" — this is the "minimum-error principle" by which we search for $\boldsymbol{c}$.
This error term has a multiplicative form: if $\alpha_{t,t}(\boldsymbol{q})$ is already small, then the product will not be large either; conversely, if $\alpha_{t,t}(\boldsymbol{q})$ is large, then $\boldsymbol{o}_{t-1}(\boldsymbol{q}) - \boldsymbol{o}_{t-1}(\boldsymbol{c})$ must be small in order to keep the error down. From this, we obtain a "minimax strategy": first find the $\boldsymbol{q}^*$ that maximizes $\alpha_{t,t}(\boldsymbol{q})$, then choose $\boldsymbol{c}=\boldsymbol{q}^*$ such that the error there is zero, i.e. $\boldsymbol{o}_{t-1}(\boldsymbol{q}) - \boldsymbol{o}_{t-1}(\boldsymbol{c})=\boldsymbol{0}$, thereby balancing the error on both the large-$\alpha_{t,t}(\boldsymbol{q})$ side and the small-$\alpha_{t,t}(\boldsymbol{q})$ side.
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}$, but since the norm can be arbitrarily large, $\alpha_{t,t}$ actually has no maximum. To get a finite result, we need to constrain the norm of $\boldsymbol{q}$; for simplicity, we assume the norms of $\boldsymbol{q},\boldsymbol{k}$ are comparable, so that we can directly take
\begin{equation}\boldsymbol{q}^* = \boldsymbol{k}_t - \bar{\boldsymbol{k}}_t\end{equation}
this extremely simple form, and substitute it into equation $\eqref{eq:A-t}$ to get
\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} (\boldsymbol{k}_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 shape 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 onto $\boldsymbol{I} - \beta_t\boldsymbol{k}_t\boldsymbol{k}_t^{\top}$ or only onto $\boldsymbol{I}$, but this difference is not essential, and the two forms can be converted into each other. With this, we have completed the approximate transformation from Softmax Attention to Delta-Rule-family attention, with the final output
\begin{equation}\boldsymbol{o}_t = \boldsymbol{A}_t \boldsymbol{q}_t + \bar{\boldsymbol{v}}_t\end{equation}
Summary
Starting from the observation that "Softmax Attention is a quadratic-complexity RNN," this post first found that its recursive increment naturally has the form of a Delta Rule, then applied a first-order approximation to the diagonal elements of Softmax, and finally, following the "minimum-error principle," found a substitute for the residual $\boldsymbol{q}$ — successfully linearizing Softmax Attention into the form of Gated DeltaNet.
(Note: this post was completed with the guidance of Kimi K3.)
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.