Parallelizing Linear Transformers with the Delta Rule over Sequence Length [arXiv:2406.06484]
Softmax Attention
Softmax attention enables efficient training by leveraging GPU-friendly matrix operations to compute attention outputs across all timesteps in parallel, but it incurs a quadratic inference complexity and additional KV-cache memory overhead, as new query must attend to all preceding keys and compute a weighted sum over their corresponding values. In contrast, recurrent form enables efficient autoregressive inference by maintaining a compact recurrent state that is incrementally updated at each time step, but it is less efficient for training because the recurrent dependencies require sequential computation across time steps (i.e., the hidden state St cannot be computed until the preceding state St-1 has been computed).
Chunkwise Parallel Form
The recurrent form can be viewed as a prefix-sum problem, which theoretically allows parallel scan algorithms to reduce the sequential computation depth from O(L) to O(log L), where L is the sequence length. However, this approach can be memory-intensive because it requires materializing the recurrent states at every time step. The chunkwise parallel form splits a sequence into chunks of consecutive tokens and updating the recurrent state chunk by chunk rather than step by step. As a result, only the recurrent states at chunk boundaries need to be materialized.
Parallelizing DeltaNet
The purely additive update rule of linear attention makes it difficult to deallocate outdated key-value associations, as new associations are continuously accumulated in the memory state. DeltaNet instead formulates memory updates as an optimization process, in which the memory “learns” how to selectively erase less important information while incorporating new information. Similar to the associative update rule in vanilla linear attention, the update rule (Mi, Ni) ⨂ (Mj, Nj) = (MiMj, NiMj+Nj) of DeltaNet is also associative. Therefore, parallel scan can be applied to compute the recurrent states in parallel, while chunkwise partition can further reduce memory consumption. However, unlike the VK matrix multiplications in linear attention, the intra-chunk computations of the P and H matrices in DeltaNet involve recursive dependencies. But this computational overhead is mitigated by leveraging the WY representation for products of Householder matrices and the UT transformation.
DeltaNet Layer
The DeltaNet layer is visualized in the figure above. Given a sequence of token embeddings, the layer begins by projecting them into qkv vectors. It then applies a causal convolution with a small kernel size as small as 4 to compute a weighted sum over the current token and its three preceding tokens. The resulting vectors are subsequently non-linearly transformed through a SiLU activation and finally L2 normalized. The transition matrix I - βtktktT has eigenvalue 1-βt||kt||2 for direction kt and eigenvalues 1 for the remaining d-1 directions perpendicular to kt. In other words, I - βtktktT scales St-1 along the kt direction by 1-βt||kt||2, while leaving all other directions unchanged. Since kt is L2 normalized, ||kt||2=1, ensuring that the scaling factor 1-βt lies within [0, 1], which helps stabilizing training. In particular, when βt=1, information in the kt subspace is completed erased while the other d-1 subspaces remain unchanged.
BibTeX citation
@misc{jiajun2026gdn,
title = {Gated Delta Networks},
author = {Hu, Jiajun},
year = {2026},
month = {November},
journal = {richardhooooo.github.io},
url = {https://richardhooooo.github.io/blog/2026/11/02/notes/}
}