From Gated DeltaNet to Kaczmarz

Many linear attention variants can be viewed as maintaining a matrix $S_t$ that linearly maps keys to values. Gated DeltaNet [1] is special in that it does not write $K_t^\top V_t$ directly, but instead writes the prediction residual, and uses gating to control forgetting and write strength.

1. Update formula of Gated DeltaNet

At time $t$, we are given $K_t \in \mathbb{R}^{1\times d_k}$ and $V_t \in \mathbb{R}^{1\times d_v}$ as row vectors, together with the memory matrix $S_t \in \mathbb{R}^{d_k\times d_v}$.

The core recurrence of Gated DeltaNet is:

The gating is usually produced from the input $X$:

• $\beta_t = \sigma(\mathrm{Linear}_\beta(X))$ represents the write strength.
• $\alpha_t \in (0,1]$ is the forgetting/decay coefficient, controlling what fraction of the old memory $S_{t-1}$ is retained.

2. Online learning perspective

We can view $S$ as the weights of a multi-output linear regression: $\hat V_t = K_t S$. The single-sample online ridge regression loss is:

Its gradient is:

If we take one step of gradient descent (with learning rate $\beta_t$):

Comparing with the form of Gated DeltaNet:

We obtain the exact correspondence: $\alpha_t = 1-\beta_t\lambda_t$. In practice, implementations often use $\alpha_t=\exp(g_t)$ for numerical stability.

3. Introducing the Kaczmarz algorithm

From the constraint perspective, SGD is not the only optimization method. Once we put more weight on the geometry of constraint satisfaction, each token can be viewed as a linear constraint $K_tS = V_t$.

One step of Kaczmarz can be defined as follows: among the set of $S$ satisfying the current constraint, find the one closest to the previous solution, i.e., the minimal-change projection:

We can solve this using the Lagrange multiplier method. Construct the Lagrangian:

Take the derivative with respect to $S$ and set it to zero:

Substitute $S$ back into the constraint $K_tS=V_t$:

Solving gives:

Thus we obtain the Kaczmarz recurrence:

4. Geometric interpretation

The Kaczmarz algorithm has a clear geometric interpretation:

1. Projection interpretation: The Kaczmarz update step projects $S_{t-1}$ onto the hyperplane ${S:K_tS=V_t}$.
2. Error elimination: When using hard projection, the updated $S_t$ satisfies the current constraint, i.e., $K_tS_t=V_t$.
3. Optimal step size: It can be viewed as a single gradient step with the optimal step size. If we perform an exact line search along the gradient direction for the instantaneous squared error, the optimal step size is $1/|K_t|^2$.
4. QK Norm perspective: This normalization factor also explains QK Norm, a trick added at the implementation level in today’s Attention / Linear Attention; here we introduce it explicitly.

5. Generalization to inconsistent constraints

In practice, constraints are often inconsistent or noisy, and no single $S$ can satisfy all of them simultaneously. Hard projection may make the model oscillate or overfit the current sample.

Therefore, Relaxed Kaczmarz (or Damped Kaczmarz) is commonly used, introducing a relaxation coefficient $\rho_t$ in the numerator and adding a numerical stability term $\varepsilon$ in the denominator:

This update formula satisfies the following property:

That is, the new prediction is a linear interpolation between the old prediction and the target value.

Combined with the forgetting mechanism of Gated DeltaNet, this gives an update that first forgets and then projects:

6. Connection with Longhorn

Longhorn [2] adopts a smoother update strategy, replacing the hard constraint projection with a proximal objective:

Its closed-form solution is:

This coefficient can be rewritten as:

Setting $\varepsilon_t = 1/\gamma_t$ then shows that Longhorn is similar to Kaczmarz.

7. Method comparison table

8. Experiments

We trained on the SlimPajama dataset for 100 million tokens and plotted validation perplexity (ppl) and loss as a function of token horizon. In the figure, @1x and @2x correspond to evaluation results with sequence lengths 2048 and 4096, respectively.

If Longhorn can be viewed as a form of Kaczmarz, then Relaxed Kaczmarz should be better, which the experiments confirm. Gated DeltaNet also uses the QK Norm trick; once we add the Q Norm trick as well, Relaxed Kaczmarz + Q Norm becomes comparable to Gated DeltaNet.

References

[1] Yang, S., Kautz, J., & Hatamizadeh, A. (2025). Gated Delta Networks: Improving Mamba2 with Delta Rule. arXiv preprint arXiv:2412.06464.

[2] Liu, B., Wang, R., Wu, L., Feng, Y., Stone, P., & Liu, Q. (2024). Longhorn: State Space Models are Amortized Online Learners. arXiv preprint arXiv:2407.14207.

Citation

If you need to cite this article, please refer to:

@article{zou2026kaczmarz,
  title={从 Gated DeltaNet 到 Kaczmarz},
  author={Zou, Jiaxuan},
  journal={Jiaxuan's Blog},
  year={2026},
  url={https://jiaxuanzou0714.github.io/blog/2026/kaczmarz/}
}