# Parallelizing Linear Transformers with the Delta Rule
over Sequence Length

Songlin Yang⋄ Bailin Wang⋄ Yu Zhang† Yikang Shen‡ Yoon Kim⋄
⋄Massachusetts Institute of Technology †Soochow University ‡MIT-IBM Watson AI
Lab
<EMAIL_ADDRESS>
###### Abstract

Transformers with linear attention (i.e., linear transformers) and state-space
models have recently been suggested as a viable linear-time alternative to
transformers with softmax attention. However, these models still underperform
transformers especially on tasks that require in-context retrieval. While more
expressive variants of linear transformers which replace the additive outer-
product update in linear transformers with the delta rule [DeltaNet; ] have
been found to be more effective at associative recall, existing algorithms for
training such models do not parallelize over sequence length and are thus
inefficient to train on modern hardware. This work describes a hardware-
efficient algorithm for training linear transformers with the delta rule,
which exploits a memory-efficient representation for computing products of
Householder matrices []. This algorithm allows us to scale up DeltaNet to
standard language modeling settings. We train a 1.3B model for 100B tokens and
find that it outperforms recent linear-time baselines such as Mamba [] and GLA
[] in terms of perplexity and zero-shot performance on downstream tasks
(including on tasks that focus on recall). We also experiment with two hybrid
models which combine DeltaNet layers with (1) sliding-window attention layers
every other layer or (2) two global attention layers, and find that these
hybrid models outperform strong transformer baselines.†† The parallel DeltaNet
layer is made available as part of the FlashLinearAttention library [, ]:
https://github.com/sustcsonglin/flash-linear-attention

##  1 Introduction

The attention mechanism [, ] has been shown to be an important primitive for
accurate sequence modeling. Attention is moreover efficient during training as
it is rich in matrix multiplications and can thus take advantage of highly
parallel processing capabilities and specialized accelerators on modern GPUs.
However, the complexity of attention is quadratic in sequence length, and
hence it is a fundamentally expensive primitive. And while recent techniques
have made it possible to scale attention to longer sequences through hardware-
aware restructuring of the intermediate computations [, , , ], these methods
still require storing the key/value vectors of previous elements, and this “KV
cache” can be unwieldy to manage for long sequences.

Linear attention transformers [] replace the exponential kernel in softmax
attention with a dot-product over (possibly transformed) key and query
vectors. This makes it possible to formulate linear attention as a linear RNN
with matrix-valued hidden states, thus obviating the need for a KV cache and
enabling constant-memory inference. While initial variants of linear attention
generally underperformed softmax attention on language modeling, gated
variants of linear attention which incorporate a data-dependent gating factor
have recently been shown to be competitive against strong transformer
baselines [, , , ]. These gated linear transformers, along with time-varying
state space models such as Mamba [] (which can be reparameterized as a gated
linear transformer), have been suggested as a potential alternative to
ordinary transformers. However, despite the competitive language modeling
performance, these models have been shown to underperform transformers on
recall-intensive tasks [], which is important for many practical downstream
tasks of interest (e.g., in retrieval-augmented generation []).

To enhance associative recall over long contexts, [] propose DeltaNet, a
variant of a linear transformer which uses a delta rule-like update [] to
retrieve and update a value vector that is associated with the current key.
DeltaNet was found to be effective on synthetic tasks and small scale language
modeling/machine translation. However, the original work used a sequential
algorithm that did not parallelize across sequence length, thus resulting in
hardware-inefficient training, and it has not been clear how to scale DeltaNet
to larger models and datasets.

This work describes a hardware-efficient training algorithm for DeltaNets
which parallelizes the forward/backward passes across sequence length. We
reparameterize the DeltaNet as a matrix-valued RNN whose recurrence is given
by a generalized Householder transformation. This reparameterization enables
the use of the memory-efficient WY representation [] for products of
Householder matrices, eliminating the need to materialize the matrix-sized
hidden states (which would incur high I/O cost). The memory-efficient
representation makes it possible to straightforwardly extend the chunkwise
parallel strategy for training linear attention models [, , ] to the DeltaNet
case. We scale DeltaNets to moderate-scale language modeling benchmarks (1.3B
models trained on 100B tokens), where DeltaNet is found to obtain better
language modeling and zero-shot downstream task performance than strong linear
recurrent models such as Mamba [] and GLA []. For in-context retrieval and
learning evaluation, we evaluate DeltaNet on synthetic benchmarks such as MQAR
[], RegBench [], MAD [], as well as real data benchmarks tested in [], where
it is again found to perform well against linear recurrent baselines. Finally,
we experiment with a hybrid approach where we combine DeltaNet layers with
sliding attention layers or global attention layers, and find that these
hybrid models can improve upon ordinary transformers, as well as the pure
DeltaNet transformer.

##  2 Background

###  2.1 Linear Transformer: Transformers with Linear Attention

Given a sequence of $d$-dimensional input vectors
${\bm{x}}_{1},\dots,{\bm{x}}_{L}$, transformers use the softmax attention
mechanism to attend over the entire past,

$\displaystyle{\bm{q}}_{t},\ {\bm{k}}_{t},\ {\bm{v}}_{t}$
$\displaystyle={\bm{W}}_{Q}{\bm{x}}_{t},{\bm{W}}_{K}{\bm{x}}_{t},{\bm{W}}_{V}{\bm{x}}_{t},$
$\displaystyle{\bm{o}}_{t}=\sum_{i=1}^{t}\frac{\exp({\bm{k}}_{i}^{{\cramped{{}^{\mathsf{T}}}}}{\bm{q}}_{t})}{\sum_{j=1}^{t}\exp({\bm{k}}_{j}^{\cramped{{}^{\mathsf{T}}}}{\bm{q}}_{t})}{\bm{v}}_{i},$

where
${\mathbf{W}}_{Q},{\mathbf{W}}_{K},{\mathbf{W}}_{V}\in\mathbb{R}^{d\times
d},{\bm{q}}_{t},{\bm{k}}_{t},{\bm{v}}_{t},{\bm{o}}_{t}\in\mathbb{R}^{d}$.
(Here we assume a single attention head). Linear attention [] replaces the
exponential kernel
$\exp({\bm{k}}_{i}^{\cramped{{}^{\mathsf{T}}}}{\bm{q}}_{t})$ with the dot-
product $\phi({\bm{k}}_{i})^{\cramped{{}^{\mathsf{T}}}}\phi({\bm{q}}_{t})$
where $\phi:\mathbb{R}^{d}\to\mathbb{R}^{n}$ is a feature map. This makes it
possible to rearrange computations to represent linear attention as a linear
RNN with matrix-valued hidden states,

$\displaystyle{\bm{o}}_{t}$
$\displaystyle=\sum_{i=1}^{t}\frac{\phi({\bm{k}}_{i})^{{\cramped{{}^{\mathsf{T}}}}}\phi({\bm{q}}_{t})}{\sum_{j=1}^{t}\phi({\bm{k}}_{j})^{{\cramped{{}^{\mathsf{T}}}}}\phi({\bm{q}}_{t})}{\bm{v}}_{i}=\frac{\left(\sum_{i=1}^{t}{\bm{v}}_{i}\phi({\bm{k}}_{i})^{\cramped{{}^{\mathsf{T}}}}\right)\phi({\bm{q}}_{t})}{\left(\sum_{j=1}^{t}\phi({\bm{k}}_{j})^{{\cramped{{}^{\mathsf{T}}}}}\right)\phi({\bm{q}}_{t})}=\frac{{\mathbf{S}}_{t}\phi({\bm{q}}_{t})}{\mathbf{z}^{\cramped{{}^{\mathsf{T}}}}_{t}\phi({\bm{q}}_{t})},$

where
${\mathbf{S}}_{t}=\sum_{i=1}^{t}{\bm{v}}_{i}\phi({\bm{k}}_{i})^{\cramped{{}^{\mathsf{T}}}}\in\mathbb{R}^{d\times
n}$ and $\mathbf{z}_{t}=\sum_{i=1}^{t}\phi({\bm{k}}_{i})\in\mathbb{R}^{n}$. If
we allow $n$ to go to infinity, linear attention can use feature maps
associated with polynomial kernels to compute a polynomial approximation to
the exponential kernel as a dot product, and can thus approximate softmax
attention arbitrarily well []. The denominator
$\mathbf{z}_{t}^{\cramped{{}^{\mathsf{T}}}}\phi({\bm{q}}_{t})\in\mathbb{R}$
can result in numerical instabilities [] and is removed in many recent works
[, , , ]. It is also common to use the identity mapping for $\phi$ [, ], which
results in the following simplified linear transformer:
${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}+{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$,
${\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t}$.

#### Efficient training.

Let ${\mathbf{Q}},{\mathbf{K}},{\mathbf{V}}\in\mathbb{R}^{L\times d}$ be the
stacked query, key, value vectors, e.g., ${\mathbf{Q}}_{i}={\bm{q}}_{i}$. We
can then compute the output ${\mathbf{O}}\in\mathbb{R}^{L\times d}$ in
parallel via
${\mathbf{O}}=\left({\mathbf{Q}}{\mathbf{K}}^{\cramped{{}^{\mathsf{T}}}}\odot{\mathbf{M}}_{L}\right){\mathbf{V}}$,
where ${\mathbf{M}}_{L}\in\mathbb{R}^{L\times L}$ is the causal mask. This
fully “parallel form” and the above “recurrent form” have different FLOPs and
memory cost tradeoffs. The parallel form takes $O(L^{2}d+Ld^{2})$ and thus
requires more FLOPs than the recurrent form, which takes $O(Ld^{2})$. However,
the parallel form can often be faster in practice for moderate-length
sequences as it can be fully parallelized and done in $O(1)$ steps. This
sequence-level parallellism also enables high GPU occupancy. While the
recurrent form requires fewer FLOPs ($O(Ld^{2})$), the elementwise operations
involved in recurrence have low arithmetic intensity, unlike the matmul
operations in the parallel form which can make use of specialized compute
units (e.g., tensor cores). Thus the recurrent form is often slower in
practice.111It is possible in theory to use parallel scan [] to parallelize
the recurrent form, which would enable the computations to be performed in
$O(\log L)$ steps and $O(Ld^{2})$ FLOPs. However, this approach requires
materializing the 2D hidden state for each time step, which would incur
significant memory I/O cost unless the hidden state size is small enough that
the materialization can happen in faster memory (which is the strategy adopted
by Mamba []).

#### Chunkwise parallel form.

The chunkwise parallel form [, ] strikes a balance between the parallel and
recurrent forms, allowing for fewer FLOPs than the parallel form and more
sequence-level parallelism than the recurrent form. Concretely, suppose the
query/key/value vectors are split into $\frac{L}{C}$ chunks where each chunk
is of length $C$. Let ${\mathbf{Q}}_{[t]}\in\mathbb{R}^{Cd}$ be all the query
vectors for chunk $t$, and let ${\bm{q}}_{[t]}^{i}={\bm{q}}_{tC+i}$ be the
$i$-th query vector within the $t$’th chunk; the key/value chunks are defined
similarly. Note that $t\in[0,L/C)$, $i\in[1,C]$. The state matrices are also
re-indexed such that ${\mathbf{S}}_{[t]}^{i}={\mathbf{S}}_{tC+i}$, and we
additionally define ${\mathbf{S}}_{[t]}^{0}={\mathbf{S}}_{[t-1]}^{C}$, i.e.,
the initial state of a chunk is the last state of the previous chunk. We can
then obtain the following identity for the hidden state and output vector for
the $r$-th element within the $t$-th chunk,

$\displaystyle{\mathbf{S}}_{[t]}^{r}$
$\displaystyle={\mathbf{S}}_{[t]}^{0}+\sum_{i=1}^{r}{\bm{v}}_{[t]}^{i}{\bm{k}}_{[t]}^{i{\cramped{{}^{\mathsf{T}}}}},\qquad{\bm{o}}_{[t]}^{r}={\mathbf{S}}_{[t]}^{0}{\bm{q}}_{[t]}^{r}+\sum_{i=1}^{r}{\bm{v}}_{[t]}^{i}\left({\bm{k}}_{[t]}^{i{\cramped{{}^{\mathsf{T}}}}}{\bm{q}}_{[t]}^{r}\right).$

By further rewriting the intra-chunk computation based on the parallel form,
we obtain following “chunkwise parallel form”,

$\displaystyle{\mathbf{S}}_{[t+1]}$
$\displaystyle={\mathbf{S}}_{[t]}+{\mathbf{V}}_{[t+1]}^{\cramped{{}^{\mathsf{T}}}}{\mathbf{K}}_{[t+1]}\qquad\qquad\qquad\qquad\qquad\in\mathbb{R}^{d\times
d},$ (1) $\displaystyle{\mathbf{O}}_{[t+1]}$
$\displaystyle={\mathbf{Q}}_{[t+1]}{\mathbf{S}}_{[t]}^{{\cramped{{}^{\mathsf{T}}}}}+\left({\mathbf{Q}}_{[t+1]}{\mathbf{K}}_{[t+1]}^{\cramped{{}^{\mathsf{T}}}}\odot{\mathbf{M}}_{C}\right){\mathbf{V}}_{[t+1]}\quad\in\mathbb{R}^{C\times
d},$ (2)

where we let ${\mathbf{S}}_{[t]}={\mathbf{S}}_{[t]}^{0}$ to reduce notational
clutter. With this form, information is propagated chunk-to-chunk through
${\mathbf{S}}_{[t]}$, and the intra-chunk states ${\mathbf{S}}^{i}_{[t]}$ for
$i\in[1,C]$ need not be materialized, thus saving memory.

The complexity of the chunkwise parallel form is $O(LCd+Ld^{2})$, and the
number of steps (without parallel scan) is $O(\frac{L}{C})$. Hence, $C=L$
recovers the fully parallel form and $C=1$ recovers the recurrent form. The
chunkwise parallel form allows us to interpolate between the two forms, in
essence trading off the number of sequential computations against sequence-
level parallelism. In practice $C$ is set to a small constant (usually 64 or
128), allowing for subquadratic training. This chunkwise form enables
practical speed-ups against parallel-form-only softmax attention even on
moderate-length sequences, as demonstrated by FlashLinearAttention [, ]

###  2.2 DeltaNet: Linear Transformers with the Delta Update Rule

The above linear transformer employs a simple linear recurrence:
${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}+{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$.
This can be seen as additively updating the memory ${\mathbf{S}}_{t-1}$ with
new key-value associations at each time step. However, a purely additive
update rule makes it difficult to deallocate past key-value associations,
eventually leading to key “collisions” when $L>d$, as pointed out by []. A
model should ideally learn to remove less important key-value associations to
make room for new ones, and this removal should depend on the interaction
between the new key and the memory content.

DeltaNet uses the delta update rule [] to operationalize this mechanism.
Specifically, it first retrieves the old value using the current key,
${\bm{v}}_{t}^{\text{old}}={\mathbf{S}}_{t-1}{\bm{k}}_{t}$. It then obtains a
new value ${\bm{v}}_{t}^{\text{new}}$ by interpolating between the old value
and the current value ${\bm{v}}_{t}$,

$\displaystyle{\bm{v}}_{t}^{\text{new}}=\beta_{t}{\bm{v}}_{t}+\left(1-\beta_{t}\right){\bm{v}}_{t}^{\text{old}},$

where $\beta_{t}=\sigma({\mathbf{W}}_{\beta}{\bm{x}}_{t})\in(0,1)$. This new
value is added to the memory, resulting in the following update:

$\displaystyle{\mathbf{S}}_{t}$
$\displaystyle={\mathbf{S}}_{t-1}\underbrace{-{\bm{v}}_{t}^{\text{old}}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}}_{\text{remove}}\underbrace{+{\bm{v}}_{t}^{\text{new}}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}}_{\text{write}}.$

Here $\beta_{t}$ is a “writing strength”: when $\beta_{t}=1$, the old value is
completely removed and ${\bm{v}}_{t}^{\text{new}}={\bm{v}}_{t}$; when
$\beta_{t}=0$, the memory remains unmodified and we have
${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}$. The output computation is the same as
vanilla linear attention, i.e., ${\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t}$.
The complexity of this recurrent form is the same as that of vanilla linear
attention, i.e., $O(Ld^{2})$. This DeltaNet is a special case of _fast weight
programmers_ [], and [] and [] show that this type of linear transformer
outperforms ordinary linear transformers on small-scale language modeling and
synthetic retrieval tasks.

##  3 Parallelizing DeltaNet Across Sequence Length

In the same spirit as the chunkwise form of linear attention, we derive a
chunkwise form for DeltaNet that enables hardware-efficient training through
parallelizing across sequence length.

###  3.1 A Memory-efficient Reparameterization

We first observe that ${\mathbf{S}}_{t}$ admits a purely additive
representation of the form
${\mathbf{S}}_{t}=\sum_{i=1}^{t}{\bm{u}}_{i}{\bm{k}}_{i}^{\cramped{{}^{\mathsf{T}}}}$
for ${\bm{u}}_{i},{\bm{k}}_{i}\in\mathbb{R}^{d}$, since we can simply set
${\bm{u}}_{i}={\bm{v}}_{i}^{\text{new}}-{\bm{v}}_{i}^{\text{old}}=\beta_{i}({\bm{v}}_{i}-{\bm{v}}_{i}^{\text{old}})$.
Recall from §2.1 that simple linear attention has the form
${\mathbf{S}}_{t}=\sum_{i=1}^{t}{\bm{v}}_{i}{\bm{k}}_{i}^{\cramped{{}^{\mathsf{T}}}}$.
Thus, DeltaNet simply replaces the value vector ${\bm{v}}_{i}$ in linear
attention with the “pseudo” value vector ${\bm{u}}_{i}$. Once the
${\bm{u}}_{i}$’s have been constructed, the rest of computation can proceed as
in ordinary linear attention, i.e.,
${\mathbf{O}}=\left({\mathbf{Q}}{\mathbf{K}}^{\cramped{{}^{\mathsf{T}}}}\odot{\mathbf{M}}\
\right){\mathbf{U}}$ where ${\mathbf{U}}\in\mathbb{R}^{L\times d}$ is the row-
wise concatenation of the ${\bm{u}}_{i}$ vectors.

However, computing ${\bm{u}}_{t}$ naïvely requires explicitly materializing
${\mathbf{S}}_{t-1}$ to compute ${\bm{v}}_{t}^{\text{old}}$, which would
require $O(d^{2})$ memory. We now show that we can obtain the ${\bm{u}}_{t}$’s
_without_ explicitly materializing ${\mathbf{S}}_{t-1}$ in $O(d)$ memory. Our
simple proof (by induction) relies on an application of the WY representation
for products of Householder matrices []. The base case is clear since we have
${\mathbf{S}}_{1}=\beta_{1}{\bm{v}}_{1}{\bm{k}}_{1}^{\cramped{{}^{\mathsf{T}}}}$,
so ${\bm{u}}_{1}=\beta_{1}{\bm{v}}_{1}$. For the inductive step, we first
observe that the DeltaNet update is given by,

$\displaystyle{\mathbf{S}}_{t}$
$\displaystyle={\mathbf{S}}_{t-1}-{\bm{v}}_{t}^{\text{old}}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}+{\bm{v}}_{t}^{\text{new}}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}={\mathbf{S}}_{t-1}-\beta_{t}\left({\mathbf{S}}_{t-1}{\bm{k}}_{t}\right){\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}+\beta_{t}{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}={\mathbf{S}}_{t-1}({\mathbf{I}}-\beta_{t}{\bm{k}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}})+\beta_{t}{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}},$

which can be seen as applying a generalized Householder transformation (i.e.,
matmul with an identity plus rank-one matrix) to the previous state. The
inductive step is then given by,

$\displaystyle{\mathbf{S}}_{t}$
$\displaystyle={\mathbf{S}}_{t-1}({\mathbf{I}}-\beta_{t}{\bm{k}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}})+\beta_{t}{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}=\sum_{i=1}^{t-1}{\bm{u}}_{i}{\bm{k}}_{i}^{\cramped{{}^{\mathsf{T}}}}+\underbrace{\left(\beta_{t}{\bm{v}}_{t}-\beta_{t}\sum_{i=1}^{t-1}{\bm{u}}_{i}\left({\bm{k}}_{i}^{{\cramped{{}^{\mathsf{T}}}}}{\bm{k}}_{t}\right)\right)}_{{\bm{u}}_{t}}{\bm{k}}_{t}^{{\cramped{{}^{\mathsf{T}}}}}=\sum_{i=1}^{t}{\bm{u}}_{i}{\bm{k}}_{i}^{\cramped{{}^{\mathsf{T}}}}.$

Note that ${\bm{u}}_{t}$ does not require materializing any of the hidden
states and requires $O(d)$ memory to compute, thus completing the proof. While
we have successfully avoided materializing the ${\mathbf{S}}_{t}$’s, computing
the ${\bm{u}}_{t}$’s for all $L$ (i.e., ${\mathbf{U}}$) takes $O(L^{2}d)$ and
moreover cannot be fully parallelized, unlike in linear attention where we can
calculate all the value vectors ${\mathbf{V}}$ in parallel in $O(1)$ steps. We
thus seek more a efficient chunkwise strategy for parallelizing DeltaNet,
which similarly exploits memory-efficient representations of products of
Householder matrices.

###  3.2 Chunkwise Parallel Form for DeltaNet

To derive the chunkwise parallel form, we first unroll the recurrence,

$\displaystyle{\mathbf{S}}_{t}={\mathbf{S}}_{t-1}({\mathbf{I}}-\beta_{t}{\bm{k}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}})+\beta_{t}{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}=\sum_{i=1}^{t}\beta_{i}({\bm{v}}_{i}{\bm{k}}_{i}^{\cramped{{}^{\mathsf{T}}}})\left(\prod_{j=i+1}^{t}({\mathbf{I}}-\beta_{j}{\bm{k}}_{j}{\bm{k}}_{j}^{\cramped{{}^{\mathsf{T}}}})\right).$

We then define the following variables:
${\mathbf{P}}_{i}^{j}=\prod_{t=i}^{j}({\mathbf{I}}-\beta_{t}{\bm{k}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}})\in\mathbb{R}^{d\times
d}$,
${\mathbf{H}}_{i}^{j}=\sum_{t=i}^{j}\beta_{t}({\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}){\mathbf{P}}_{t+1}^{j}\in\mathbb{R}^{d\times
d}$, where we let ${\mathbf{P}}_{i}^{j}={\mathbf{I}}$ whenever $i>j$.
Intuitively, ${\mathbf{P}}_{i}^{j}$ is the “decay factor” to be applied to
${\mathbf{S}}_{i}$ for obtaining ${\mathbf{S}}_{j}$, and
${\mathbf{H}}_{i}^{j}$ represents the contributions to ${\mathbf{S}}_{j}$
starting from token $i$. (Hence ${\mathbf{S}}_{t}={\mathbf{H}}_{1}^{t}$). The
chunkwise recurrence can then be written as,

$\displaystyle{\mathbf{S}}_{[t]}^{r}={\mathbf{S}}_{[t]}^{0}{\mathbf{P}}_{[t]}^{r}+{\mathbf{H}}_{[t]}^{r}$
(3)

where we define the chunkwise variables
${\mathbf{S}}_{[t]}^{i}={\mathbf{S}}_{tC+i}$,
${\mathbf{P}}_{[t]}^{r}={\mathbf{P}}_{tC+1}^{tC+r}$,
${\mathbf{H}}_{[t]}^{r}={\mathbf{H}}_{tC+1}^{tC+r}$. Here we have
$\frac{L}{C}$ chunks of size $C$. The trick is to now efficiently represent
the ${\mathbf{P}}_{[t]}^{r},{\mathbf{H}}_{[t]}^{r}\in\mathbb{R}^{d\times d}$
matrices using a similar approach described in §3.1, so that these matrices
can be stored in $O(d)$ memory. This is given by,

$\displaystyle{\mathbf{P}}_{[t]}^{r}$
$\displaystyle={\mathbf{I}}-\sum_{i=1}^{r}{\bm{w}}_{[t]}^{i}{\bm{k}}_{[t]}^{i{\cramped{{}^{\mathsf{T}}}}},\qquad{\mathbf{H}}_{[t]}^{r}=\sum_{t=1}^{r}{\bm{u}}_{[t]}^{i}{\bm{k}}_{[t]}^{i{\cramped{{}^{\mathsf{T}}}}}$
$\displaystyle\in\mathbb{R}^{d\times d}$ (4) $\displaystyle{\bm{w}}_{[t]}^{r}$
$\displaystyle=\beta_{[t]}^{r}\left({\bm{k}}_{[t]}^{r}-\sum_{i=1}^{r-1}\left({\bm{w}}_{[t]}^{i}({\bm{k}}_{[t]}^{i{\cramped{{}^{\mathsf{T}}}}}{\bm{k}}_{[t]}^{r})\right)\right)$
$\displaystyle\in\mathbb{R}^{d}$ (5) $\displaystyle{\bm{u}}_{[t]}^{r}$
$\displaystyle=\beta_{[t]}^{r}\left({\bm{v}}_{[t]}^{r}-\sum_{i=1}^{r-1}\left({\bm{u}}_{[t]}^{i}({\bm{k}}_{[t]}^{i{\cramped{{}^{\mathsf{T}}}}}{\bm{k}}_{[t]}^{r})\right)\right)$
$\displaystyle\in\mathbb{R}^{d}$ (6)

The derivations for the above can be found in the appendix. Subsequently,
based on Eq. 3, we can obtain the chunk-level recurrence for hidden states and
outputs as,

$\displaystyle{\mathbf{S}}_{[t]}^{r}$
$\displaystyle={\mathbf{S}}_{[t]}^{0}-\left({\mathbf{S}}_{[t]}^{0}\sum_{i=1}^{r}{\bm{w}}_{[t]}^{i}{\bm{k}}_{[t]}^{i{\cramped{{}^{\mathsf{T}}}}}\right)+\sum_{i=1}^{r}{\bm{u}}_{[t]}^{i}{\bm{k}}_{[t]}^{i{\cramped{{}^{\mathsf{T}}}}}={\mathbf{S}}_{[t]}^{0}+\sum_{i=1}^{r}\left({\bm{u}}_{[t]}^{i}-{\mathbf{S}}_{[t]}^{0}{\bm{w}}_{[t]}^{i}\right){\bm{k}}_{[t]}^{i{\cramped{{}^{\mathsf{T}}}}},$
$\displaystyle{\bm{o}}_{[t]}^{r}$
$\displaystyle={\mathbf{S}}_{[t]}^{r}{\bm{q}}_{[t]}^{r}={\mathbf{S}}_{[t]}^{0}{\bm{q}}_{[t]}^{r}+\sum_{i=1}^{r}\left({\bm{u}}_{[t]}^{i}-{\mathbf{S}}_{[t]}^{0}{\bm{w}}_{[t]}^{i}\right)\left({\bm{k}}_{[t]}^{i{\cramped{{}^{\mathsf{T}}}}}{\bm{q}}_{[t]}^{i}\right).$

Letting ${\mathbf{S}}_{[t]}={\mathbf{S}}_{[t]}^{0}$, the above can be
simplified to matrix notations similarly to Eq.1-2,

$\displaystyle{\mathbf{S}}_{[t+1]}$
$\displaystyle={\mathbf{S}}_{[t]}+\left({\mathbf{U}}_{[t+1]}-{\mathbf{W}}_{[t+1]}{\mathbf{S}}_{[t]}^{{\cramped{{}^{\mathsf{T}}}}}\right)^{\cramped{{}^{\mathsf{T}}}}{\mathbf{K}}_{[t+1]}$
(7) $\displaystyle{\mathbf{O}}_{[t+1]}$
$\displaystyle={\mathbf{Q}}_{[t+1]}{\mathbf{S}}_{[t]}^{\cramped{{}^{\mathsf{T}}}}+({\mathbf{Q}}_{[t+1]}{\mathbf{K}}_{[t+1]}^{{\cramped{{}^{\mathsf{T}}}}}\odot{\mathbf{M}})\left({\mathbf{U}}_{[t+1]}-{\mathbf{W}}_{[t+1]}{\mathbf{S}}_{[t]}^{\cramped{{}^{\mathsf{T}}}}\right)$
(8)

where $\square_{[t]}=\square_{[t]}^{1:C}\in\mathbb{R}^{C\times d}$ for
$\square\in\\{{\mathbf{Q}},{\mathbf{K}},{\mathbf{V}},{\mathbf{O}},{\mathbf{U}},{\mathbf{W}}\\}$
defines the chunkwise matrices that are formed from stacking the
${\bm{q}}_{t},{\bm{k}}_{t},{\bm{v}}_{t},{\bm{o}}_{t},{\bm{u}}_{t},{\bm{w}}_{t}$
vectors.

#### Training speed.

The sequential computations needed for constructing the chunkwise matrices
${\mathbf{U}}_{[t]}$’s and ${\mathbf{W}}_{[t]}$’s takes $O(Ld)$ work but can
be parallelized across chunks, reducing the number of sequential steps from
$L$ to $C$. Once these are obtained, the chunkwise hidden state updates (Eq.
7) and the output computations (Eq. 8) are largely the same as in linear
attention, and thus take $O(LCd+Ld^{2})$ work and $O(\frac{L}{C})$ sequential
steps.

$L$ | $d_{\text{head}}$ | Speed-up
---|---|---
2048 | 64 | 5.5x
4096 | 64 | 7.6x
8192 | 64 | 11.5x
2048 | 128 | 8.9x
4096 | 128 | 13.2x
2048 | 256 | 13.7x
Table 1: Speed comparison between the recurrent and chunkwise algorithms for
DeltaNet on a single H100 GPU.

In order to save even more memory, we discard the chunk-level hidden states
${\mathbf{S}}_{[t]}$’s (which would take $O(\frac{L}{C}d^{2})$ space) after
the forward pass and recompute them during the backward pass; the
${\mathbf{U}}$ and ${\mathbf{W}}$ matrices, which take up $O(Ld)$ space, are
kept in memory.

We implement both the pure recurrent form and the chunkwise parallel form in
Triton [] and show the speed-ups for various sequence lengths (L) and head
dimensions ($d_{\text{head}}$) in Table 1, where the model dimension $d$ is
2048.222So far we have been assuming a single head ($d_{\text{head}}=d$) for
easier exposition. In practice we use multiple heads where the head dimension
$d_{\text{head}}$ is smaller than the model dimension $d$. In this case we
have ${\mathbf{S}}_{t}\in\mathbb{R}^{d\times d_{\text{head}}}$. Note that our
recurrent form kernel333Our recurrent form kernel as well as the kernel of the
original DeltaNet paper does not use parallel scan, as this would be
impractical. See footnote 1. is already 2x faster than the CUDA recurrent form
kernel provided in the original DeltaNet
paper.444https://github.com/IDSIA/recurrent-
fwp/blob/master/algorithmic/fast_transformers/causal_product_cuda.cu. Our
chunkwise algorithm enjoys greater speed-ups as the length $L$ and head
dimension $d_{\text{head}}$ increases.

###  3.3 DeltaNet Transformer

We describe how the DeltaNet layer primitive is used to build up a
transformer-like model using standard modules. We largely follow the LLaMA-
architecture transformer [Transformer++, ] and just replace the self-attention
layer with the DeltaNet layer. We also apply normalization before output
projection to stable training [, ]. As the additional parameters for computing
scalar $\beta_{t}$ terms are negligible, parameter allocation is roughly the
same as in Transformer++: $4d^{2}$ for the DeltaNet layer and $8d^{2}$ for the
SwiGLU FFN layer [].

#### Feature map and normalization.

[] originally follow [] and apply a “$\text{ELU}+1$” [] to nonlineary
transform the key/query vectors. We instead use the SiLU activation [], which
was found to perform better (as reported by []). [] also normalize the
key/query vectors with the $L_{1}$ norm. We use the $L_{2}$ norm instead.
Normalization has two effects: ignoring $\beta_{t}$, both $L_{1}$\- and
$L_{2}$-normalization would ensure that
${\mathbf{I}}-{\bm{k}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$ has
eigenvalues $\leq 1$, making training stable; moreover,
${\mathbf{I}}-{\bm{k}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$ is a
projection matrix with $L_{2}$-normalization, and only erases information in
one subspace while keeping the other $d-1$ subspace intact, which is
beneficial for retaining information while still enabling some forgetting.
Thus our key/query vectors are given by
${\bm{k}}_{t}=\frac{\text{SiLU}({\mathbf{W}}_{K}{\bm{x}}_{t})}{\|\text{SiLU}({\mathbf{W}}_{K}{\bm{x}}_{t})\|_{2}}$,
${\bm{q}}_{t}=\frac{\text{SiLU}({\mathbf{W}}_{Q}{\bm{x}}_{t})}{\|\text{SiLU}({\mathbf{W}}_{Q}{\bm{x}}_{t})\|_{2}}$.
We ablate on these choices in our empirical study.

###  3.4 Hybrid Models

Following recent work on combining subquadratic token-mixing layers with
existing neural network primitives [, , ], we also experiment with hybridizing
DeltaNet models.

#### Convolutional layers.

Recent linear recurrent models typically incorporate a lightweight depthwise-
separable convolution layer after the query/key/value projections [, , ]. This
“short convolution” layer [] generalizes the shift SSM [], and is efficient in
both number of parameters and computational cost. We also add a short
convolution layer after the query/key/value projections.

#### Local sliding window and global attention.

Linear attention largely uses a content-based addressing mechanism [] and
lacks positional information []. [] also argue that linear attention lacks the
ability to perform precise local token shifts and comparisons, thus facing
difficulties on retrieval-intensive tasks. Motivated by this, we experiment
with two different hybrid architectures that incorporate softmax attention. We
first explore local sliding window attention which attends over a sliding
window and morever has been shown to significantly improve linear attention [,
, , ]; we follow Griffin [] and interleave DeltaNet layers and sliding multi-
query local attention (SMQA) layers. We also experiment with global attention,
which has been found to be helpful [, ] even if only few of the recurrent
layers are replaced with full global attention []; we follow [] to replace
only two layers with global attention: the second layer and the
$(\frac{N}{2}+1)$-th layer, where $N$ is total number of layers.

##  4 Empirical Study

We compare the DeltaNet against strong baselines in both synthetic and real-
world language modeling settings. Our main baselines include: LLaMA-
architecture Transformer++ []; RetNet [], a linear attention Transformer with
non-data-dependent exponential decay and large head dimension; GLA [], a
linear attention Transformer with data-dependent decay; and Mamba [], a
selective state-space model with data-dependent decay. The number of
parameters is kept (roughly) the same between all models.

###  4.1 Synthetic Benchmarks

641282565120255075100Model dimensionAccuracy (%)Sequence Length: 512, Key-
Value Pairs: 64DeltaNetMambaGLARetNetRWKV4Hyena

Figure 1: Accuracy (%) on MQAR.

We evaluate on three synthetic benchmarks: Multi-query associative recall
[MQAR; ], in-context language learning [RegBench; ], and Mechanistic
Architecture Design [MAD; ].

MQAR evaluates language models’ ability to (in-context) recall information
within a context when faced with multiple recall queries. [] show that the
accuracy of MQAR has a strong correlation with the language modeling
performance. We use []’s training setting and for DeltaNet we use 2 heads. We
do not use convolutions for these experiments. Table 1 shows that DeltaNet
performs perfectly (even without convolution) in the hardest setting of MQAR
[], outperforming Mamba (which uses convolution) in low dimension settings.

$5$$10$$15$$20$5075100Training examples (K)Accuracy
($\%$)Transformer++DeltaNet (w. conv)DeltaNet (w/o. conv)GLA (w. conv)GLA
(w/o. conv)Mamba (w. conv)Mamba (w/o. conv)

Figure 2: Accuracy (%) on RegBench.

We next consider consider RegBench [], which is a synthetic dataset designed
to assess in-context learning capability of different model architectures.
Each input sequence in this benchmark consists of 10 to 20 strings drawn from
a probabilistic finite automaton (PFA), where each example is separated by a
special separator token. Each sequence is designed to be sampled from a
distinct language defined by the PFA so that a model needs to infer the
underlying language from the context on the fly. During testing, a model is
evaluated on predicting the next token of testing sequences generated from
held-out PFAs. We follow [] and perform a hyperparameter sweep for each model
architecture and use the best result. Here again we find that DeltaNet
performs strongly compared to baselines.

Finally, we conside the MAD benchmark [], a suite of synthetic token
manipulation tasks designed to probe capabilities of model architectures. The
results are shown in Table 2. Compared with other architectures, including
MHA, DeltaNet is better at recalling tasks, especially on Fuzzy Recall,
although it struggles on the Memorize task.

Model | Compress | Fuzzy Recall | In-Context Recall | Memorize | Noisy Recall | Selective Copy | Average
---|---|---|---|---|---|---|---
Transformer | 51.6 | 29.8 | 94.1 | 85.2 | 86.8 | 99.6 | 74.5
Hyena [] | 45.2 | 7.9 | 81.7 | 89.5 | 78.8 | 93.1 | 66.0
Multihead Hyena [] | 44.8 | 14.4 | 99.0 | 89.4 | 98.6 | 93.0 | 73.2
Mamba [] | 52.7 | 6.7 | 90.4 | 89.5 | 90.1 | 86.3 | 69.3
GLA [] | 38.8 | 6.9 | 80.8 | 63.3 | 81.6 | 88.6 | 60.0
DeltaNet | 42.2 | 35.7 | 100 | 52.8 | 100 | 100 | 71.8
Table 2: Results on MAD. Results other than DeltaNet are directly borrowed
from []. (Multihead) Hyena, DeltaNet and Mamba make use of convolutions,
whereas GLA does not.

###  4.2 Language Modeling

#### Experimental setup.

Following prior work [, ], we evaluate on Wikitext perplexity and zero-shot
common sense reasoning tasks, including LAMBADA [LMB.; ], PiQA [], HellaSwag
[Hella.; ], WinoGrande [Wino.; ], ARC-easy (ARC-e) and ARC-challenge (Arc-c)
[]. Following [], we also evaluate the models real-world recall-intensive
tasks, including FDA [], SWDE [], and SQUAD []. Both SWDE and FDA focus on
extracting structured information: SWDE from raw HTML to identify semi-
structured relationships, and FDA from PDFs to retrieve key-value pairs. SQUAD
evaluates language models on reading comprehension by providing a text passage
and a related question.

#### Hyperparameters.

We train all models from scratch in two configurations: 340M and 1.3B
parameters. Each model uses AdamW for optimization, with a peak learning rate
of 3e-4. The 340M models are trained using 15 billion tokens and a batch size
of 0.5M tokens, while the 1.3B models are trained with 100 billion tokens and
a batch size of 2M tokens. We use a cosine learning rate schedule, starting
with a warm-up phase of 0.5 billion tokens for the 340M models and 1 billion
tokens for the 1.3B models. Both configurations have initial and final
learning rates set at 3e-5. We apply a weight decay of 0.01 and use gradient
clipping at a maximum of 1.0. The head dimension of DeltaNet is set to 128,
and the kernel size for convolution layers is set at 4.

Model | Wiki. | LMB. | LMB. | PIQA | Hella. | Wino. | ARC-e | ARC-c | Avg. | SWDE | SQUAD | FDA
---|---|---|---|---|---|---|---|---|---|---|---|---
|  ppl $\downarrow$ |  ppl $\downarrow$ |  acc $\uparrow$ |  acc $\uparrow$ |  acc_n $\uparrow$ |  acc $\uparrow$ |  acc $\uparrow$ |  acc_n $\uparrow$ |  |  cont. $\uparrow$ |  cont. $\uparrow$ |  cont. $\uparrow$
340M params / 15B tokens |  |  |  |  |  |  |  |  |  |  |  |
Transformer++ | 28.39 | 42.69 | 31.0 | 63.3 | 34.0 | 50.4 | 44.5 | 24.2 | 41.2 | 42.2 | 22.1 | 21.4
RetNet (w/o. conv) | 32.33 | 49.19 | 28.6 | 63.5 | 33.5 | 52.5 | 44.5 | 23.4 | 41.0 | 13.3 | 27.6 | 2.9
Mamba (w. conv) | 28.39 | 39.66 | 30.6 | 65.0 | 35.4 | 50.1 | 46.3 | 23.6 | 41.8 | 12.4 | 23.0 | 2.1
GLA (w/o. conv) | 28.65 | 43.35 | 30.3 | 64.8 | 34.5 | 51.4 | 45.1 | 22.7 | 41.5 | 18.6 | 27.2 | 8.1
(w. conv) | 29.47 | 45.53 | 31.3 | 65.1 | 33.8 | 51.6 | 44.4 | 24.6 | 41.8 | 24.0 | 24.7 | 7.3
DeltaNet (w/o. conv) | 29.08 | 50.87 | 30.0 | 63.6 | 33.6 | 51.7 | 46.0 | 23.0 | 41.3 | 24.6 | 26.9 | 4.5
DeltaNet (w. conv) | 28.24 | 37.37 | 32.1 | 64.8 | 34.3 | 52.2 | 45.8 | 23.5 | 42.1 | 26.4 | 28.9 | 12.8
\+ Sliding Attn | 27.06 | 38.17 | 33.4 | 64.0 | 35.3 | 50.9 | 45.9 | 23.2 | 42.1 | 39.3 | 32.5 | 18.8
\+ Global Attn (2 layers) | 27.51 | 35.04 | 33.5 | 64.0 | 34.5 | 51.7 | 46.0 | 23.3 | 42.1 | 42.9 | 32.1 | 23.1
1.3B params / 100B tokens |  |  |  |  |  |  |  |  |  |  |  |
Transformer++ | 16.85 | 13.44 | 48.9 | 70.8 | 49.6 | 53.6 | 56.0 | 26.5 | 50.9 | 66.6 | 31.5 | 27.4
RetNet (w/o. conv) | 18.64 | 17.27 | 43.3 | 70.0 | 47.3 | 52.5 | 54.8 | 25.6 | 48.9 | 42.8 | 34.7 | 14.3
Mamba (w. conv) | 17.06 | 13.89 | 46.2 | 72.2 | 40.1 | 54.1 | 59.0 | 28.2 | 50.0 | 41.4 | 35.2 | 6.2
GLA (w/o. conv) | 17.22 | 14.47 | 46.9 | 71.8 | 49.8 | 53.9 | 57.2 | 26.6 | 51.0 | 50.6 | 42.6 | 19.9
(w. conv) | 17.25 | 14.92 | 46.2 | 70.6 | 49.9 | 53.0 | 55.3 | 27.0 | 50.4 | 52.4 | 37.4 | 22.3
DeltaNet (w. conv) | 16.87 | 12.21 | 48.9 | 71.2 | 50.2 | 53.6 | 57.2 | 28.3 | 51.6 | 49.5 | 37.4 | 17.2
\+ Sliding Attn | 16.56 | 11.74 | 49.2 | 71.8 | 51.1 | 52.8 | 58.9 | 28.8 | 52.1 | 53.3 | 43.3 | 22.3
\+ Global Attn (2 layers) | 16.55 | 12.40 | 48.8 | 70.8 | 50.7 | 54.2 | 58.4 | 28.1 | 51.8 | 71.0 | 43.0 | 29.8
DeltaNet Ablations (340M) |  |  |  |  |  |  |  |  |  |  |  |
w. $L_{1}$-norm & 1+ELU | 31.12 | 55.96 | 26.3 | 63.9 | 33.0 | 50.9 | 44.3 | 21.8 | 40.1 | 14.5 | 23.9 | 6.2
w. $L_{2}$-norm & 1+ELU | 28.03 | 37.62 | 32.2 | 65.7 | 34.7 | 51.8 | 45.4 | 22.5 | 42.1 | 23.8 | 28.6 | 13.1
w. $L_{2}$-norm & ReLU | 28.75 | 43.53 | 30.2 | 64.0 | 33.9 | 48.9 | 45.6 | 22.8 | 40.9 | 27.2 | 26.7 | 9.0
Table 3: Main language modeling results against Transformer++, RetNet [],
Mamba [], and GLA []. All models are trained on the same subset of the
SlimPajama dataset with the Mistral tokenizer. The Transformer++, RetNet,
Mamba, GLA (w/o. conv) results are taking from []. For hybrid models, “Sliding
Attn” interleaves a sliding window attention every other layer, and “Global
Attn” uses full global attention on two layers. The 340M/1.3B models are
trained for 15B/100B tokens respectively. All results are obtained through lm-
evaluation-harness [].

#### Results.

Our main language modeling results are shown in Table 3. In the original
works, Mamba uses convolutions by default, while GLA does not. For fair
comparison, we retrain the GLA with convolution, and also train DeltaNet
without convolution. For the 1.3B setting we only train the DeltaNet with
convolution due to limited compute resources.

In general we find that DeltaNet outperforms the strong Mamba/GLA baselines in
terms of both perplexity and downstream task performance. Improvements upon
Mamba are particularly pronounced for the recall intensive tasks (i.e., SWDE,
SQUAD, FDA). We also confirm the benefits of hybrid architectures [, ]. Both
the sliding window attention hybrid and the global attention hybrid work well,
outperforming the Transformer++ in terms of perplexity. The hybrid DeltaNet
that just replaces two DeltaNet layers with global attention outperforms a
Transformer++ even on recall-intensive benchmarks.

#### Ablation study.

In Table 3 (bottom) we ablate the choice of feature map and normalization. The
original DeltaNet uses $L_{1}$-norm and the ELU feature map. We find that
simply replacing the $L_{1}$-norm with the $L_{2}$-norm greatly increases
peerformance. As for feature map, we experiment with
$\\{\mathtt{ReLU},\mathtt{1+ELU},\mathtt{SiLU}\\}$ and find that
$\mathtt{SiLU}$ performs the best.

####

4.2

##

###

${\mathbf{S}}_{t}\in\mathbb{R}^{d\times n}$${\bm{x}}_{t}\in\mathbb{R}^{d}$

$\displaystyle{\mathbf{S}}_{t}={\mathbf{S}}_{t-1}\bullet{\mathbf{M}}_{t}+{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}},$
$\displaystyle{\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t},$

$\bullet$${\mathbf{M}}_{t}$${\bm{v}}_{t}$${\bm{k}}_{t}$${\bm{q}}_{t}$${\bm{x}}_{t}$

, ${\mathbf{S}}_{1},\dots,{\mathbf{S}}_{L}$$O(\log
L)$$O(L)$${\bm{x}}_{1},\dots,{\bm{x}}_{L}$1, , , , $\bullet=\odot$4.2

|  |
---|---|---
,  | ${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}+{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$ | ${\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t}$
| ${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}+{\bm{v}}_{t}\phi({\bm{k}}_{t})^{\cramped{{}^{\mathsf{T}}}}$ | ${\bm{o}}_{t}={\mathbf{S}}_{t}\phi({\bm{q}}_{t})$
| ${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}+{\bm{v}}_{t}\phi({\bm{k}}_{t})^{\cramped{{}^{\mathsf{T}}}},\,\,\,{\bm{z}}_{t}={\bm{z}}_{t-1}+\phi({\bm{k}}_{t})$ | ${\bm{o}}_{t}={\mathbf{S}}_{t}\phi({\bm{q}}_{t})/({\bm{z}}_{t}^{\cramped{{}^{\mathsf{T}}}}\phi({\bm{q}}_{t}))$
| ${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}(\mathbf{I}-\beta_{t}{\bm{k}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}})+\beta_{t}{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$ | ${\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t}$
| ${\mathbf{S}}_{t}=g_{t}{\mathbf{S}}_{t-1}+(1-g_{t}){\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}},\,\,\,{\bm{z}}_{t}=g_{t}{\bm{z}}_{t-1}+(1-g_{t}){\bm{k}}_{t}$ | ${\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t}/({\bm{z}}_{t}^{\cramped{{}^{\mathsf{T}}}}{\bm{q}}_{t})$
| ${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}\odot\exp(-({\bm{\alpha}}\mathbf{1}^{\cramped{{}^{\mathsf{T}}}})\odot\exp({\bm{A}}))+{\bm{B}}\odot({\bm{v}}_{t}\mathbf{1}^{\cramped{{}^{\mathsf{T}}}})$ | ${\bm{o}}_{t}=({\mathbf{S}}_{t}\odot{\bm{C}})\mathbf{1}+{\bm{d}}\odot{\bm{v}}_{t}$
,  | ${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}\odot({\bm{\beta}}_{t}{\bm{\alpha}}_{t}^{\cramped{{}^{\mathsf{T}}}})+{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$ | ${\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t}$
,  | ${\mathbf{S}}_{t}=\gamma{\mathbf{S}}_{t-1}+{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$ | ${\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t}$
| ${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}\odot\exp(-({\bm{\alpha}}_{t}\mathbf{1}^{\cramped{{}^{\mathsf{T}}}})\odot\exp({\bm{A}}))+({\bm{\alpha}}_{t}\odot{\bm{v}}_{t}){\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$ | ${\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t}+{\bm{d}}\odot{\bm{v}}_{t}$
| ${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}\odot(\mathbf{1}{\bm{\alpha}}_{t}^{\cramped{{}^{\mathsf{T}}}})+{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}={\mathbf{S}}_{t-1}\text{Diag}({\bm{\alpha}}_{t})+{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$ | ${\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t}$
| ${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}\text{Diag}({\bm{\alpha}}_{t})+{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$ | ${\bm{o}}_{t}=({\mathbf{S}}_{t-1}+({\bm{d}}\odot{\bm{v}}_{t}){\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}){\bm{q}}_{t}$
| ${\mathbf{S}}_{t}={\mathbf{S}}_{t-1}\text{Diag}({\bm{\alpha}}_{t})+{\bm{v}}_{t}(\mathbf{1}-{\bm{\alpha}}_{t})^{\cramped{{}^{\mathsf{T}}}}$ | ${\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t}$
| ${\mathbf{S}}_{t}=f_{t}{\mathbf{S}}_{t-1}+i_{t}{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}},\,\,\,{\bm{z}}_{t}=f_{t}{\bm{z}}_{t-1}+i_{t}{\bm{k}}_{t}$ | ${\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t}/\max\\{1,|{\bm{z}}_{t}^{\cramped{{}^{\mathsf{T}}}}{\bm{q}}_{t}|\\}$
| ${\mathbf{S}}_{t}=\gamma_{t}{\mathbf{S}}_{t-1}+{\bm{v}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$ | ${\bm{o}}_{t}={\mathbf{S}}_{t}{\bm{q}}_{t}$

${\mathbf{S}}_{t}\in\mathbb{R}^{d\times
n}$$\odot$${\bm{z}}_{t}$${\bm{q}}_{t}$$t$${\bm{v}}_{t},{\bm{\alpha}}_{t},f_{t},\gamma_{t}$${\bm{x}}_{t}$${\bm{A}},{\bm{d}},\gamma$$\phi$,
,

${\mathbf{S}}_{t-1}\bullet{\mathbf{M}}_{t}={\mathbf{S}}_{t-1}{\mathbf{M}}_{t}$${\mathbf{M}}_{t}$$O(dn^{2})$$O(dn)$${\mathbf{M}}_{t}={\mathbf{I}}-\beta_{t}{\bm{k}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}$${\mathbf{M}}_{t}={\mathbf{I}}-{\bm{a}}_{t}{\bm{b}}_{t}^{\cramped{{}^{\mathsf{T}}}}$

###

$\\{{\bm{x}}_{t}\\}_{t=1}^{L}\mapsto\\{{\bm{o}}_{t}\\}_{t=1}^{L}$${\bm{o}}_{t}$${\bm{x}}_{j}$$j>t$,
, , , , , , , , ,

4.24.2, , , , , , 23

###

${\mathbf{M}}_{t}=\gamma_{t}({\mathbf{I}}-{\bm{k}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}})$$\gamma_{t}\in(0,1)$55However
we found the DeltaNet + local sliding-window attention hybrid to generalize
well, which could provide an appealing middle ground.

##

####

__,,

####

, , , , , , ,

####

, , , , , ,

, , ,

####

, , , , , , , , , , , ,

##

##

##

  *   *   * __
  *   * __
  * __
  * __
  *   * __
  * __
  *   * __
  * __
  *   * __
  * __
  * __
  *   * __
  *   * __
  * __
  *   *   *   *   * __
  * __
  * ____
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  *   * __
  * __
  *   * __
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  * __
  *   *   * __
  *   * __
  *   * __
  * __
  *   * __
  * __
  * ____
  *   * __
  * __
  * __
  * __
  *   *   *   * __
  * __
  *   * __
  * __
  * ____
  * ____
  *   * __
  * __
  * __
  * __
  * __
  * __
  * __
  *   * __
  * __
  * __
  * __
  *   * __
  * __
  * __
  *   *   * __

##

${\mathbf{P}}_{n}={\mathbf{I}}-\sum_{t=1}^{n}{\bm{w}}_{t}{\bm{k}}_{t}^{{\cramped{{}^{\mathsf{T}}}}}$

$\displaystyle{\mathbf{P}}_{n}$
$\displaystyle=\prod_{t=1}^{n}({\mathbf{I}}-\beta_{t}{\bm{k}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}})$
$\displaystyle={\mathbf{P}}_{n-1}({\mathbf{I}}-\beta_{n}{\bm{k}}_{n}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}})$
$\displaystyle=({\mathbf{I}}-\sum_{t=1}^{n-1}{\bm{w}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}})({\mathbf{I}}-\beta_{n}{\bm{k}}_{n}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}})$
$\displaystyle={\mathbf{I}}-\sum_{t=1}^{n-1}{\bm{w}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}-\beta_{n}{\bm{k}}_{n}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}}+(\sum_{t=1}^{n-1}{\bm{w}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}})\beta_{n}{\bm{k}}_{n}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}}$
$\displaystyle={\mathbf{I}}-\sum_{t=1}^{n-1}{\bm{w}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}-\underbrace{\left(\beta_{n}{\bm{k}}_{n}-\beta_{n}\sum_{t=1}^{n-1}\left({\bm{w}}_{t}({\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}{\bm{k}}_{n})\right)\right)}_{{\bm{w}}_{n}}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}}$
$\displaystyle={\mathbf{I}}-\sum_{t=1}^{n}{\bm{w}}_{t}{\bm{k}}_{t}^{{\cramped{{}^{\mathsf{T}}}}}$

${\mathbf{S}}_{n}=\sum_{t=1}^{n}{\bm{u}}_{t}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}}$

$\displaystyle{\mathbf{S}}_{n}$
$\displaystyle={\mathbf{S}}_{n-1}({\mathbf{I}}-\beta_{n}{\bm{k}}_{n}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}})+\beta_{n}{\bm{v}}_{n}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}}$
$\displaystyle=\left(\sum_{t=1}^{n-1}{\bm{u}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}\right)({\mathbf{I}}-\beta_{n}{\bm{k}}_{n}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}})+\beta_{n}{\bm{v}}_{n}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}}$
$\displaystyle=\sum_{t=1}^{n-1}{\bm{u}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}-\left(\sum_{t=1}^{n-1}{\bm{u}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}\right)\beta_{n}{\bm{k}}_{n}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}}+\beta_{n}{\bm{v}}_{n}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}}$
$\displaystyle=\sum_{t=1}^{n-1}{\bm{u}}_{t}{\bm{k}}_{t}^{\cramped{{}^{\mathsf{T}}}}+\underbrace{\left(\beta_{n}{\bm{v}}_{n}-\beta_{n}\sum_{t=1}^{n-1}{\bm{u}}_{t}\left({\bm{k}}_{t}^{{\cramped{{}^{\mathsf{T}}}}}{\bm{k}}_{n}\right)\right)}_{{\bm{u}}_{n}}{\bm{k}}_{n}^{{\cramped{{}^{\mathsf{T}}}}}$
$\displaystyle=\sum_{t=1}^{n}{\bm{u}}_{t}{\bm{k}}_{n}^{\cramped{{}^{\mathsf{T}}}}$