Attention pays for every token it remembers. Recurrent models keep a fixed-size state instead, and this chapter shows how to make that state train in parallel, remember for a long time, choose what to keep, and run fast on a GPU, from linear attention and S4 to Mamba, gated DeltaNet, and the hybrid models that frontier labs ship.

A recurrent model reads a sequence one token at a time and keeps a fixed-size summary of everything it has read, called its state. It updates the state at every step and never looks back at the tokens themselves. Attention does the opposite. It keeps every past token, so the memory it needs, and the time it takes to produce each new token, grow with the length of the context.

This chapter brings recurrence back. The recurrent networks of §3.3 were the standard language models before 2017, and attention replaced them because it trains in parallel over the sequence (§3.6, §4.7). Chapter 20 then showed the price of that choice at serving time. Every cost it measured, the time of a decode step, the users that fit on a GPU, and the dollars per token, grows with the context through the KV cache. The layers of this chapter keep a fixed-size state, so none of those costs grows, and they still train in parallel. Many of the leading open-weight long-context models of 2025 and 2026 use them in most of their layers.

This section measures what attention pays for keeping every token, on real models. It finds the exact reason recurrent networks still lost to attention, and the one change that lets a recurrence train as fast. That change, a state update that is linear in the state, is the base of every layer in this chapter. Then we compute such a recurrence three ways, measure how long it remembers, find where its precision runs out, and list the five properties the rest of the chapter must deliver.

Start with a real cost. When a Transformer generates text, it stores the key and value vectors of every past token so that it never has to recompute them. That store is the KV cache (§6.5). Serve Llama 3.1 8B (Grattafiori et al. 2024) to one user whose conversation has reached 128K tokens, which is 131,072 because K here means 1,024. The model has 32 layers. Each layer caches 8 key vectors and 8 value vectors of 128 numbers for every token. They are stored in bf16, a 16-bit format with 2 bytes per number. So every past token leaves $2\cdot 32\cdot 8\cdot 128\cdot 2 = 131{,}072$ bytes behind, 128 KiB (a KiB is 1,024 bytes).

The whole conversation then holds 16 GiB of cache (a GiB is $2^{30}$ bytes), or 17.2 GB in powers of ten. That is a little more than the model's 16.1 GB of weights. To produce each new token the GPU must read both, and every token it writes adds another 128 KiB.

Now put Mamba-2 2.7B (Dao and Gu 2024), a recurrent language model of the kind this chapter builds, in the same conversation. Everything it remembers about those 131,072 tokens fits in about 86 MB in bf16, or 172 MB in fp32, the 4-byte format. That size is the same at 1,000 tokens and at a million. Each step reads the weights and this small state, and nothing else.

Recurrent networks had a fixed-size state long before attention existed. They lost because they could not be trained in parallel over the sequence. So the question of this section is concrete. How can a model keep a fixed-size summary of an unbounded past and still train as fast as a Transformer?

What attention pays for every token it remembers

Start with training, whose cost §4.7 counted. An attention layer of width $d$ over $T$ tokens costs about $8Td^2 + 4T^2d$ FLOPs (floating-point operations) in the forward pass. The first term is the four $d\times d$ projections that make the queries, keys, values, and output. The second is the attention core, the scores $\mathbf{Q}\mathbf{K}^\top$ and the weighted sum of the values. Only the core grows as $T^2$.

A whole Transformer block adds a feed-forward network, so its weight products cost about $24Td^2$. A causal mask halves the core to $2T^2d$. The two are equal at $T = 12d$, about 49,000 tokens at $d = 4096$. The tiled attention kernel of §12.3, FlashAttention, makes the core fast and keeps its memory linear in $T$. It still does the same quadratic number of FLOPs.

Generation is where the cost hurts most. Each new token attends to every cached key and value. Let $L$ be the number of layers, $n_{kv}$ the number of key-value heads per layer, $d_k$ their width, $T$ the context length, $B$ the number of sequences decoded together (the batch), and $s$ the bytes per number. The cache of §6.5 holds

In plain words, there are two tables, keys and values, with an entry for every layer, key-value head, token, and sequence. Llama 3 already shrinks the cache with grouped-query attention, in which several query heads share one key-value head (§12.5). Its 32 query heads share 8 key-value heads, which cuts $n_{kv}$ from 32 to 8. Even so, one sequence holds 16 GiB at 128K tokens.

In decoding, the bytes a step moves matter more than the FLOPs it does. A GPU keeps the weights and the cache in its main memory, called HBM (high-bandwidth memory). Every number must travel from there to the arithmetic units before it is used (§11.2). The arithmetic intensity of a computation is the number of FLOPs it does per byte it moves. A GPU's ridge point is its peak FLOP rate divided by its memory bandwidth. For an H100 that is 989 TFLOP/s of bf16 against 3.35 TB/s, about 295 FLOPs per byte.

A computation below the ridge point is memory-bound. Its time is about its bytes divided by the bandwidth, and the arithmetic units sit waiting. Decode attention sits far below the ridge. Each cached number, 2 bytes in bf16, is used by the $h/n_{kv}$ query heads that share it, where $h$ is the number of query heads. Each use is one multiply and one add, so attention does $h/n_{kv}$ FLOPs per byte of cache (§12.5). For Llama 3.1 8B that is $32/8 = 4$, about 70 times below the ridge.

Batching does not help attention, because each sequence reads its own cache. The weight products are memory-bound too at small batch. Each weight is read once per step and used once per sequence, so $B$ times in all. A decode step therefore takes about as long as streaming the weights and every sequence's cache out of HBM once. §20.1 treats the anatomy of inference in full.

For a Transformer, $M_{\text{cache}}$ grows linearly in $T$, so at long context the second term takes over. For a model whose memory of the past is a fixed-size state, $M_{\text{cache}}$ is a constant, and the step time does not depend on $T$ at all. The cell below plots both for real shapes.

The cell prints two crossovers. Llama's cache passes the entire Mamba-2 state at only 656 tokens, a short paragraph. It passes Llama's own weights at about 122,500 tokens. Beyond that point a long conversation costs more to remember than the model costs to store.

def crossover_length(n_layers, n_kv, d_k, budget_bytes, batch=1, bytes_per=2):
    raise NotImplementedError

def cache_share(n_layers, n_kv, d_k, weight_bytes, T, batch=1, bytes_per=2):
    raise NotImplementedError

The batch changes the picture. At batch 32, Llama 3.1 8B's caches outweigh its weights from 3,830 tokens on, a few pages of text. The 122,500-token crossover holds only for one sequence, and servers run at large batches.

Here is the full picture at real scale. The next cell applies the bandwidth model to both models on one H100, which has 80 GB of HBM at 3.35 TB/s. It does so at three context lengths, for one user and for 32.

The widget below runs the same arithmetic for any context and number of users. It covers Llama 3.1 8B and 70B, Mamba-2 2.7B, and a hypothetical hybrid that keeps attention in 4 of its 32 layers. Eight GPUs count as one pool with eight times the memory and bandwidth, the best case for splitting a model across them.

In practice this is the whole case for recurrent layers in serving. An interviewer who asks why long-context serving is expensive wants three facts. Decoding is memory-bound. The cache is read in full at every step. And it grows with $T$, so both the step time and the batch that fits get worse with every token. A fixed-size state removes the dependence on $T$ entirely.

A fixed-size state, and why RNNs lost anyway

The recurrent networks of §3.3 had exactly the property we want. A plain RNN reads one token at a time and keeps a state vector $\mathbf{h}_t\in\R^{d_h}$ of $d_h$ numbers. At each step it mixes the old state with the new input $\mathbf{x}_t$ and squashes each entry with a tanh,

Here $\mathbf{W}_{hh}\in\R^{d_h\times d_h}$ acts on the old state, $\mathbf{W}_{xh}$ acts on the input, and $\mathbf{b}_h$ is a bias. Decoding costs the same at every step, and memory never grows.

Yet attention replaced recurrence, and the reason was training. Vaswani et al. (2017) compared the two layers in a table that §3.6 reproduced and §4.7 discussed. Over a sequence of $T$ tokens, a recurrent layer needs $T$ operations in a row, while self-attention needs a constant number. A GPU runs tens of thousands of threads at once, and $T$ steps that must wait for each other leave almost all of them idle. Training an RNN on a 4,096-token sequence means 4,096 small matrix-vector products, one after another.

Why must the steps be sequential? "Because $\mathbf{h}_t$ depends on $\mathbf{h}_{t-1}$" is not the reason. A running sum also depends on the previous sum, yet §11.4 computed all the running sums of $T$ numbers in about $\log_2 T$ rounds with a scan. A scan computes every prefix result of a sequence, $x_1$, then $x_1\circ x_2$, then $x_1\circ x_2\circ x_3$, and so on, for some way $\circ$ of combining two items.

A scan needs two things. The combine must be associative, meaning $(x\circ y)\circ z = x\circ(y\circ z)$. That lets the scan combine neighboring stretches of the sequence in any grouping, many at once. And a combined result must be as small as a single item, so it can be passed around cheaply. So the real question is whether two steps of an RNN combine into one step of the same kind. For a tanh RNN they do not.

In plain words, two steps of a tanh RNN make a function of a new shape, and $k$ steps make a nest of $k$ tanh functions. The only exact summary of steps 1 to $k$ is the list of all $k$ pairs $(w_i, p_i)$, which grows with $k$. So a scan has nothing small to pass around, and step $k$ has to wait for the actual number $h_{k-1}$. The LSTM and the GRU fail the same way, because their gates are themselves functions of $\mathbf{h}_{t-1}$.

Now remove the nonlinearity from the path that carries the state, and only from that path. Write one step as

where $a_t$ and $b_t$ may be any functions of the input $x_t$, even very nonlinear ones, but not of $h_{t-1}$. Each step is the affine map $h\mapsto a_th + b_t$, "multiply by $a_t$, then add $b_t$". Two such maps compose into another one.

In plain words, the summary of any stretch of steps is one "multiply by this, then add that" rule, two numbers however long the stretch. For example, the steps $(0.5, 1)$ and $(0.5, 0)$ combine into $(0.25, 0.5)$. Starting from $h = 0$ that gives $0.5$. Running the two steps one after the other gives the same, $0.5\cdot 0 + 1 = 1$ and then $0.5\cdot 1 + 0 = 0.5$. So the scan of §11.4 can combine stretches in $\log_2 T$ rounds. That section ended with this very operator, as the scan that parallelizes a linear recurrence. This is the whole difference between a tanh RNN, which must wait for every step, and a recurrence that trains as fast as attention.

An interviewer who asks "why can't you parallelize an RNN over time?" wants the composition argument, not "each step depends on the last". Affine steps compose into affine steps of the same size, and tanh steps do not.

A linear recurrence is a lower-triangular matrix

We now fix the object the rest of the section studies. Look at one channel of a sequence layer, so the input at step $t$ is one number $x_t$ and the output is one number $y_t$. A real layer runs many such channels side by side, and we return to vector states below. The state $h_t$ is one number too. Write the added term as an input weight times the input, $b_t = u_tx_t$, and read the output through a readout weight, $y_t = c_th_t$.

Entry $(t, s)$ of the matrix is the weight with which input $s$ reaches output $t$. Here it is $0.5^{t-s}$, the same along each diagonal, because the decay is the same at every step. With a different decay at every step, the entry is the product of the decays applied between step $s$ and step $t$. That product gets its own name.

Notice which decays appear. Input $s$ enters the state at step $s$, after the decay $a_s$ has already acted on the old state, so $a_s$ never touches it. The first decay that acts on input $s$ is $a_{s+1}$. And $a_1$ never matters at all, because $h_0 = 0$. Getting this index wrong by one is a common bug, and Exercise 21.1b tests for it.

In plain words, each output is a weighted sum of all past inputs. The weight on input $s$ is how strongly it was written ($u_s$), times how much of it survived the decays since ($a_{t:s}$), times how strongly it is read now ($c_t$).

A decay of zero is a reset. It wipes the state, and the matrix shows the effect plainly.

A model that learns to set $a_t\approx 0$ at a document boundary or a change of topic gets exactly this behavior, and §21.4 shows Mamba doing it. In the widget below, each decay's bar sits above the matrix column of its own step. Drag the decays and watch the matrix change. Click a cell to see its segment product.

Attention has a mixing matrix too

Softmax attention fits the same mold. Call any layer that mixes information across positions a token mixer. Every mixer in this chapter, and attention too, works in two stages. First it computes mixing weights from the layer's input, from queries and keys for attention, or from decays and input and readout weights for a recurrence. Then it applies those weights to the channel being mixed. Once the weights are fixed, each output is a weighted sum of that channel's inputs. This view organizes the whole chapter.

Not every causal layer has this form. A tanh RNN, an LSTM, or a GRU passes its state through a nonlinearity at every step, so there is no separate weight path. The influence of $x_s$ on $y_t$ depends on the values the state takes along the way, and so on $x_s$ itself and on every input since. That is the same nonlinearity in the state path that defeated the scan. When a parallel weight path computes $\mathbf{M}$ from the input, as in every layer of this chapter, the layer can be evaluated in parallel by forming $\mathbf{M}$ and multiplying.

Seen this way, attention and a recurrence differ in three precise ways.

• What the entries depend on. Attention's $\mathbf{M}_{ts}$ depends on the content of the pair of tokens $t$ and $s$. A recurrence's entry factors into a part that depends only on $t$ ($c_t$), a part that depends only on $s$ ($u_s$), and a product of decays in between.
• Rank. Both matrices usually have full rank, since they are lower triangular with nonzero diagonals. The difference lies below the diagonal. Attention's blocks below the diagonal can have any rank up to their size. The recurrence's blocks below the diagonal have rank at most the state size, as the theorem below shows.
• How it must be computed. Attention has to be computed as a matrix. The recurrence can also be computed by a loop with constant memory, which is the entire point.

In plain words, everything the past $J$ passes to the future $I$ goes through the single number $h_k$, so the block can carry only one direction of information. With a state of $N$ numbers the same argument gives rank at most $N$, the structure that §21.6 calls semiseparable. The rank is the size of the state that a block's past must pass through to reach its future. An interviewer may ask how a recurrence's matrix differs from attention's, and this is the precise answer.

Three ways to compute one recurrence

The unrolled theorem gives two algorithms for the same outputs, and the composition operator gives a third. Two measures compare them. The work is the total number of operations. The depth is the length of the longest chain of operations that must wait for each other, which bounds the time on unlimited processors.

The recurrent mode runs the loop, $T$ steps of one multiply-add each. Its work is $O(T)$ and its depth is $T$, since every step waits for the last. It keeps only the current state in memory. It is the natural mode for decoding, where the tokens arrive one at a time anyway.

The matrix mode builds $\mathbf{M}$ and computes $\mathbf{M}\mathbf{x}$. That is $O(T^2)$ work and $O(T^2)$ memory with depth $O(\log T)$. For one channel it is a matrix-vector product, which is memory-bound. When many channels share one $\mathbf{M}$, as the channels of one Mamba-2 head, a group of channels that share their decays, do (§21.6), it becomes a matrix product. That runs at full speed on the tensor cores, the GPU's matrix-multiply units. The matrix mode is wasteful for long sequences and ideal for short blocks.

The scan mode runs a parallel scan over the pairs $(a_t, u_tx_t)$ with the operator $\bullet$. The work-efficient scan of §11.4 combines pairs up a binary tree and then passes the results back down (it is often called the Blelloch scan). It does $O(T)$ work in $O(\log T)$ depth and stores $O(T)$ intermediate results. That section also proved a scheduling bound, Brent's theorem. It says $p$ processors finish a computation of work $W$ and depth $D$ in about $W/p + D$ steps, here on the order of $T/p + \log_2 T$. The scan is the natural mode for training and for prefill.

With a state of $N$ numbers and one decay per number, the work and memory columns gain a factor of $N$. The depth does not change, because the $N$ recurrences run side by side. §21.5 adds a fourth mode, the chunked algorithm. It uses the matrix mode inside blocks of 64 to 256 tokens and the recurrent mode across blocks, and it is what production kernels run.

The cell below implements all three. It builds the matrix from cumulative sums of $\log a_t$, since $\log a_{t:s} = \sum_{r=s+1}^{t}\log a_r = S_t - S_s$ with $S_t = \sum_{r\le t}\log a_r$. The upper triangle is set to $-\infty$ before exponentiating, so it becomes exactly zero and nothing overflows. The scan is the simpler doubling scan of §11.4 (the Hillis-Steele scan), in which every position combines with the one $k$ places back, for $k = 1, 2, 4, \dots$. It has the same $O(\log T)$ depth as the work-efficient scan but does about $T\log_2 T$ work.

Now a small simulation. Draw decays between 0.8 and 1, a typical range for a forget gate, with random input and readout weights over 1,000 steps, and check that the three modes agree.

import numpy as np

def recurrence_loop(a, u, c, x):
    raise NotImplementedError

def mixing_matrix(a, u, c):
    T = len(a)
    return np.tril(np.ones((T, T)))      # placeholder: a running sum, every decay treated as 1

How long a linear recurrence remembers

The unrolled form answers the question that sank the plain RNN, which is how gradients travel back through time. Differentiate $h_T = \sum_{s\le T}a_{T:s}u_sx_s$.

In plain words, the gradient that reaches $k$ steps back is exactly the product of the $k$ decays in between. Compare the tanh RNN of §3.3. There the same sensitivity was a product of Jacobians $\operatorname{diag}(1 - \mathbf{h}_t^2)\mathbf{W}_{hh}$. Each factor squashes by the tanh's slope at a point that depends on the data, so the product shrinks in ways the model cannot control.

Here there is no squashing, and the model controls the product directly by choosing the decays. If the decays sit near 1, gradients from far back survive. The theorem covers the path through the state. When the decays and input weights are computed from the input, the gradient also flows into them. §21.5 computes those gradients with a scan run backward.

So how far back does a decay reach? Take a constant decay $a$, and set the input weight to $1 - a$ so that a constant input produces the same constant state. This is the exponential moving average.

The half-life is a good definition of memory length for a second reason. Once $t$ is large, the total weight on inputs at least $k$ steps old is $\sum_{j\ge k}(1-a)a^j = a^k$. So half of the state's content is younger than $t_{1/2}$ and half is older. The time constant $1/(1-a)$, the usual scale of a forget gate in §3.3, is the same scale up to the factor $\ln 2$.

In practice this is the number to compute when someone asks whether a layer can use a fact from 2,000 tokens back. A decay of 0.99 keeps $0.99^{2000}\approx 2\times10^{-9}$ of it, effectively nothing, while 0.9999 keeps 82%.

Vector states, and why the eigenvalues set the memory

A real layer carries a state vector $\mathbf{h}_t\in\R^N$. A recurrence is time-invariant when its matrices are the same at every step. The general time-invariant linear recurrence is $\mathbf{h}_t = \mathbf{A}\mathbf{h}_{t-1} + \mathbf{b}x_t$, with a state matrix $\mathbf{A}\in\R^{N\times N}$ and an input vector $\mathbf{b}\in\R^N$, read out by $y_t = \mathbf{c}^\top\mathbf{h}_t$ with $\mathbf{c}\in\R^N$. §21.3 writes $\mathbf{b}$ and $\mathbf{c}^\top$ as the matrices $\mathbf{B}$ and $\mathbf{C}$ of a state-space model.

Unrolling gives $y_t = \sum_{s\le t}\mathbf{c}^\top\mathbf{A}^{t-s}\mathbf{b}\,x_s$, so the memory is set by the powers of $\mathbf{A}$. §0.10 showed that the eigenvalues govern those powers. If $\mathbf{A}\mathbf{v} = \lambda\mathbf{v}$, then $\mathbf{A}^k\mathbf{v} = \lambda^k\mathbf{v}$.

Each independent scalar recurrence is called a mode. Mode $n$ forgets with half-life $\ln 2/(-\ln|\lambda_n|)$. If $\lambda_n$ is complex, the mode also rotates by the angle $\arg\lambda_n$ at every step, so it is a decaying oscillation. The spectral radius $\rho(\mathbf{A}) = \max_n|\lambda_n|$ is the largest eigenvalue magnitude. The state stays bounded for every bounded input and every input vector $\mathbf{b}$ exactly when $\rho(\mathbf{A}) < 1$, the stability condition of §3.3.

This is why modern layers use diagonal decays. Almost every real matrix is diagonalizable over the complex numbers. So a dense time-invariant $\mathbf{A}$ can express nothing that a complex diagonal one cannot, once the change of basis is absorbed into $\mathbf{b}$ and $\mathbf{c}$. And the diagonal recurrence costs $O(N)$ per step instead of $O(N^2)$, and scans entry by entry. Orvieto et al. 2023 made this argument explicit in their linear recurrent unit. The diagonal state-space models of §21.3, that unit, and Mamba all use diagonal decays from the start, complex in the first two and real and positive in Mamba.

import numpy as np

def diagonalize(A, b, c):
    lam, V = np.linalg.eig(A)
    return lam, b.astype(complex), c.astype(complex)      # placeholder: forgot the change of basis

def run_diagonal(lam, b_t, c_t, x):
    raise NotImplementedError

Decays live in log space and in fp32

Most layers keep each decay between 0 and 1, so that the state neither grows nor flips sign (§21.6 shows what that costs). A model also needs decays spread over many timescales, from half-lives of a few tokens for syntax to thousands for a document's topic. Both needs point to the same parameterization. Learn an unconstrained real number $w$ and set

In plain words, $w$ is the logarithm of the decay rate $-\ln a$. Every real $w$ gives a valid decay. Equal steps in $w$ multiply the half-life by equal factors, so spreading $w$ evenly covers timescales evenly on a log scale. Variants of this appear throughout the chapter. The linear recurrent unit writes a complex decay $\lambda = \exp(-e^{\nu} + i\theta)$. Mamba writes $a = \exp(\Delta\cdot\lambda)$ with $\lambda = -e^{w}$ and a step size $\Delta > 0$, and §21.3 derives where that form comes from. The gated recurrence of De et al. 2024 raises a sigmoid to a power that depends on the input.

There is a second, more practical reason to store the logarithm. A decay near 1 carries all its information in its distance from 1, and 16-bit formats cannot resolve that distance. The bf16 format has 8 exponent bits and 7 stored mantissa bits (§8.5). Its numbers in $[\tfrac12, 1)$ are spaced $2^{-8}$ apart, so the largest bf16 number below 1 is $1 - 2^{-8} = 0.99609375$.

The cell below rounds to bf16 with NumPy alone. It keeps the upper 16 bits of the float32 bit pattern, rounding to the nearest value with ties to even, the method of §8.5. It shows that the log-space parameter survives bf16 storage while the decay itself does not.

The same arithmetic applies to the long products $a_{t:s}$. Computed in bf16 they would snap to the coarse grid at every multiplication, so kernels form them in fp32, or as sums of logarithms in fp32 within a chunk (§21.5). An interviewer who hands you $a = 0.999$ and asks what goes wrong in bf16 wants this table.

import numpy as np

def half_life(a):
    return 1.0 / (1.0 - a)            # placeholder: the time constant, not the half-life

def decay_for_half_life(t_half):
    raise NotImplementedError

Decoding with a state, end to end

Back to serving, now with every piece in hand. A decode step of a recurrent layer reads the state, applies one update per state number, and writes the state back. That is a few FLOPs per number, an arithmetic intensity as low as decode attention's, so it too is memory-bound. The difference is that its bytes are a constant. Mamba-2's state per layer, $5120\times128$ numbers, is about 1.3 MB in bf16, read and written once per step. For comparison, one attention layer of Llama 3.1 8B holds 4 KiB per token, 512 MiB at 128K tokens.

A hybrid model mixes the two kinds of layer, with a few attention layers in a mostly recurrent stack. A server that runs it must budget for both kinds of memory per sequence. Here is that budget for one concrete design.

The next exercise does this arithmetic the way a capacity planner would, for any mix of attention and recurrent layers.

def cache_bytes(model, T):
    raise NotImplementedError

def step_time(model, T, batch, bandwidth):
    raise NotImplementedError

def tokens_per_second(model, T, batch, bandwidth):
    raise NotImplementedError

The same arithmetic drives the hybrids of §21.6. Keeping attention in one layer of eight cuts the cache eightfold, while the recurrent layers add a constant state of about a hundred megabytes (120 MB in fp32 for the hybrid above). Whether those few attention layers are enough to keep the model's recall is the question that section answers.

What a fixed state cannot do

A fixed-size state means something must be forgotten. A state of $S$ numbers of 16 bits each can take at most $2^{16S}$ distinct values, whatever the update rule. The number of possible prompts grows exponentially with their length, so long enough prompts outnumber the states. The pigeonhole principle says that when there are more items than boxes, two items share a box. So two different prompts leave the model in the same state. Any later question whose answer differs between them is answered wrongly for at least one of them. Attention has no such ceiling within its context, because it keeps every token.

In practice the trouble starts far below that ceiling. Mamba-2 2.7B's state is 688 million bits. Storing 131,072 token ids verbatim takes only about 2 million bits, at 16 bits each, enough for its vocabulary of about 50,000. The binding limits are elsewhere.

• Each layer's state is split into heads that store their associations separately. One head of Mamba-2 holds $64\times128 = 8{,}192$ numbers, and that, not the whole model's 688 million bits, bounds what one head can recall.
• The update rule is a fixed, simple function, not an optimal compressor.
• The layer must decide what to keep before it knows what will be asked.

On tasks that require recalling many key-value pairs from the context, models with fixed-size states trade recall against state size along a clear frontier, while attention recalls nearly perfectly (Arora et al. 2024). This is an empirical finding. §21.2 computes how many associations a matrix-valued state can hold. §21.6 states the theorems that make these limits precise, for copying, associative recall, and tracking a state such as the parity of a bit string.

A second question is about expressiveness. With fixed decays, a linear recurrence is a linear function of its input, and a stack of linear maps is a linear map. So where do these models get their power? Part of it comes from the position-wise MLPs between the recurrences, exactly as a Transformer gets it from the MLPs between its attention layers. The rest comes from decays and input weights computed from the input, which make each layer nonlinear in $\mathbf{x}$ while it stays linear in the state.

What we want from a sequence layer

We can now say precisely what the rest of the chapter is looking for. A sequence layer for a frontier model should have five properties.

1. Parallel training. All positions of a training sequence are computed with low depth, so the GPU's parallelism is used.
2. Constant-cost decoding. Each new token costs the same time and memory, whatever the context length.
3. Long memory. Information and gradients survive across thousands of steps.
4. Content-based selection and recall. The layer decides from the content of each token what to store, what to forget, and what to retrieve.
5. Matmul-friendly. Most of its FLOPs run as dense matrix products. An H100's tensor cores run dense bf16 products at about 989 TFLOP/s, against 67 TFLOP/s for ordinary float32 arithmetic (§11.1), roughly 15 times more.

No purely recurrent row gets everything, and the gap is always in recall, the one thing a fixed state cannot do for free. The chapter climbs this table row by row.

• §21.2 rewrites softmax attention as a recurrence whose state is a matrix. It reaches parallel training and constant decoding with almost no effort, then shows what goes wrong with a state that only adds.
• §21.3 derives recurrences from continuous-time systems, with a long memory built in by design.
• §21.4 makes the decays depend on the input, so the layer selects what to keep.
• §21.5 makes all of them fast with chunked scans.
• §21.6 unifies them, proves their limits, and explains why many of the leading open-weight long-context models of 2025 and 2026 mix a few attention layers into a mostly recurrent stack.

In PyTorch

The block below checks the three modes against each other in PyTorch. It uses autograd to confirm the gradient theorem, since the gradient of $y_T$ with respect to the inputs is row $T$ of $\mathbf{M}$. And it shows the bf16 decay problem with real tensors.

The scan builds new tensors with torch.cat instead of assigning into slices. In-place updates of tensors that autograd still needs would raise an error. In production you never write this scan yourself. The CUDA and Triton kernels of Mamba and Mamba-2, and the chunked kernels of libraries such as flash-linear-attention, fuse it with the rest of the layer (§21.5).

Read more

• Martin & Cundy (2018). Parallelizing Linear Recurrent Neural Nets Over Sequence Length. The paper that recognized linear recurrences as scans, with a CUDA kernel, the GILR-LSTM, and a dependency a million steps long.
• De et al. (2024). Griffin: Mixing Gated Linear Recurrences with Local Attention for Efficient Language Models. Section 5.1 gives the bandwidth model of a decode step used here, and Appendix F compares KV cache and recurrent state sizes.
• Orvieto et al. (2023). Resurrecting Recurrent Neural Networks for Long Sequences. Linearize, diagonalize, parameterize in log space, and normalize, and a plain RNN matches deep state-space models. This is the linear recurrent unit.
• Orvieto et al. (2023). Universality of Linear Recurrences Followed by Non-linear Projections: Finite-Width Guarantees and Benefits of Complex Eigenvalues. The approximation theorem for a linear recurrence followed by an MLP, and why complex eigenvalues help.
• Arora et al. (2024). Simple linear attention language models balance the recall-throughput tradeoff. Measures how recall falls with state size across recurrent and linear-attention models, the frontier this section describes.
• Gu (2023). Modeling Sequences with Structured State Spaces. Albert Gu's thesis, the clearest statement of the recurrent, convolutional, and continuous views of one model and when to compute each.
• Gu (2025). On the Tradeoffs of SSMs and Transformers. A blog post on state size, state expressivity, and training efficiency as the three ingredients of modern recurrent models, and on what a compressed state gives up.
• Danieli et al. (2025). ParaRNN: Unlocking Parallel Training of Nonlinear RNNs for Large Language Models. Newton iterations that reduce a nonlinear RNN to repeated linear scans, trained at 7 billion parameters.

Watch next

▶

▶