Transformer alternatives 2: Mamba, RWKV, RetNet, Hyena and hybrids
S4 gave us a sequence layer with a fixed-size memory, but it treats every token the same, so it cannot decide what to keep. This session shows four ways to fix that while keeping training parallel and decoding cheap: Mamba (selective state spaces with a parallel scan), RWKV and RetNet (attention-like training, RNN-like decoding), and Hyena (long convolutions with gates). Then it shows their shared weakness, exact recall from a fixed-size state, and why hybrids such as Jamba keep a few attention layers.
What you will learn
- Why a time-invariant SSM such as S4 cannot do selective copying, and how Mamba makes Δ, B and C depend on the input
- How the selective recurrence reduces to a classic RNN gate, and how a parallel scan trains it in O(log L) depth
- RWKV's WKV operator and RetNet's retention: one formula with a parallel form for training and a recurrent form for decoding
- One view of all three: a matrix-valued state with a decay, updated by an outer product k v^T
- Hyena: implicit long filters, gating, and O(L log L) training with the FFT
- Why a fixed-size state fails at exact recall (Zoology, copying tasks), with a small simulation
- Hybrids: how Jamba's 1 attention layer per 8 cuts the KV cache from 32 GB to 4 GB at 256K tokens
Why this matters
A transformer must keep the keys and values of every earlier token (the KV cache) to write the next one. The cache grows with the context. For Llama 2 7B at 256K tokens it is 128 GB in 16-bit, more than the GPU that holds the model. The models in this session replace that growing cache with a state of fixed size: a few megabytes, whatever the context length.
Session 100 built the base: the linear state space model (SSM) and S4. S4 has two views of one model, a recurrence for fast decoding and a convolution for parallel training. But S4 has a deep problem for language: it is time-invariant. It uses the same matrices \(A, B, C\) for every token, so it treats “the” and a phone number in exactly the same way. It cannot decide to remember one token and ignore the next. This session is about four answers to that problem, and about the price they all pay.
- Mamba makes the SSM matrices depend on the current token (“selection”) and trains with a parallel scan instead of a convolution.
- RWKV and RetNet start from attention instead. They write a form of linear attention with a decay that can be computed in parallel for training and as an RNN for decoding.
- Hyena keeps convolutions, but makes them very long and wraps them in input-dependent gates.
- Hybrids such as Jamba keep a few attention layers, because a fixed-size state cannot store everything. Exact recall (copying, “what was the code in line 3?”) is where pure recurrent models are weak.
The efficient-inference survey groups these models as transformer alternates (its Section 5.1.3): designs with sub-quadratic cost in the sequence length, whose recurrent decoding makes the cost per new token independent of the context length and removes the need to load the features of all earlier tokens. [Certain, survey Section 5.1.3] That last point is the inference win: decode is limited by memory traffic (session 82), and a fixed state means fixed traffic.
The problem with S4: it cannot choose
Recall the discretized SSM from the previous session. For one input channel, a hidden state \(\mathbf{h}_t \in \R^N\) is updated at every token:
In S4, \(\bar A\), \(\bar B\) and \(C\) are the same at every step. This is what makes the convolution view possible: the output is \(y = \bar K * x\) with one fixed kernel \(\bar K = (C\bar B, C\bar A\bar B, C\bar A^2\bar B, \dots)\). But a fixed kernel means a fixed rule for forgetting. Token 5 is always weighted by \(C\bar A^{t-5}\bar B\), no matter what token 5 was.
The Mamba paper shows the problem with the selective copying task: a few content tokens are placed at random positions among filler tokens, and the model must output only the content tokens, in order. A time-invariant model knows where to look only if the spacing is fixed. In the paper’s results, S4 without gating solves 18.3% of it, while the selective version (S6) solves 97.0%; inside the full Mamba block, S6 reaches 99.8%. [Certain, Mamba paper] The only change is that the parameters now depend on the input.
Mamba: selective state spaces
Mamba keeps a diagonal SSM with \(N\) states for each of \(D\) channels, as in S4D (the diagonal version from the previous session). The new idea: three of the parameters become functions of the current input \(\mathbf{x}_t \in \R^D\):
- Read the symbols
- \(\Delta_t\)
- the step size, one positive number per channel. Large \(\Delta\) means “this token matters, focus on it”; small \(\Delta\) means “skip it”
- \(\operatorname{softplus}(z)\)
- \(\log(1 + e^z)\), a smooth function that is always positive
- \(\mathbf{p}\)
- a learned bias; \(W_\Delta\) is a low-rank projection (rank 160 in Mamba-2.8B)
- \(B_t, C_t\)
- the input and output vectors of the SSM, now computed from the token, shared by all channels
- \(A\)
- stays a learned parameter: a diagonal matrix with negative real entries, one per channel and state (shape \(D \times N\))
Then the model is discretized with the current \(\Delta_t\), separately for every token. Mamba uses the zero-order hold rule from the previous session for \(A\):
The simple form \(\Delta_t B_t\) on the right is what the reference code uses for \(\bar B\). [Likely] Because \(A\) is diagonal, \(\exp(\Delta_t A)\) is just the exponential of each entry. The recurrence is the same as before, but now every matrix carries a time index:
(\(\odot\) is the element-wise product; \(D\, x_t\) is a skip connection.) The price: the model is no longer time-invariant, so the convolution trick of S4 is gone. We need another way to train it in parallel. That comes in the next section.
Selection is a gate
Take the smallest case: one state (\(N = 1\)), \(A = -1\), \(B = 1\), and \(\Delta_t = \operatorname{softplus}(z_t)\). Then \(\bar A_t = e^{-\Delta_t}\) and \(\bar B_t = 1 - e^{-\Delta_t}\) (exact zero-order hold). Since \(e^{-\operatorname{softplus}(z)} = 1/(1 + e^{z})\), we get
This is the gate of a classic gated RNN. The Mamba paper states it as Theorem 1. [Certain] So \(\Delta_t\) controls a gate: \(\Delta_t \to \infty\) gives \(g_t \to 1\), which resets the state and stores the current token; \(\Delta_t \to 0\) gives \(g_t \to 0\), which ignores the token and keeps the state. S4 has one fixed \(\Delta\), so every token gets the same gate. Try it in Figure 1.
How to read Figure 1
The grey bars use one \(\Delta\) for every token. Whatever value you choose, the newest tokens win, and the KEY at position 3 fades: you can only choose how fast everything fades. The orange bars use a large \(\Delta\) for the KEY and a small \(\Delta\) for the others. The state then holds almost only the KEY, and \(h_8\) is close to 9. Make the ordinary \(\Delta\) larger and the later tokens start to overwrite the KEY.
Time-invariant with \(\Delta = 1\): every gate is \(g = 1 - e^{-1} = 0.632\). The KEY’s weight in \(h_8\) is \(0.632 \times 0.368^5 = 0.004\), and \(h_8 = 0.875\). The model has nearly forgotten the 9.
Selective with \(\Delta_{\text{KEY}} = 4\) and \(\Delta = 0.02\) elsewhere: the KEY’s gate is \(1 - e^{-4} = 0.982\), the other gates are \(1 - e^{-0.02} = 0.020\). The KEY’s weight is \(0.982 \times 0.980^5 = 0.888\), and \(h_8 = 8.053\). The tokens before the KEY have weight 0.0003: the large \(\Delta\) also cleared the old state.
The selective scan, token by token
Figure 1 used one state. A real Mamba channel has \(N\) states, each with its own \(A_n\), and \(B_t, C_t\) are vectors. Figure 2 runs (101.2)–(101.4) in your browser for one channel with \(N = 2\) states. State 1 is slow (\(A_1 = -0.1\)) and state 2 is fast (\(A_2 = -2\)). Each token has a value \(u_t\) (the channel input) and two flags: \(m_t = 1\) for the KEY token and \(r_t = 1\) for the last token, the QUERY. The projections are small hand-picked weights on these flags: \(\Delta_t = \operatorname{softplus}(p + w\, m_t)\), \(B_t = (0.2\, m_t,\ 1.5\,(1 - m_t))\) and \(C_t = (r_t,\ 1 - r_t)\). So the KEY writes into the slow state, the other tokens write into the fast state, and only the QUERY reads the slow state. As in Algorithm 1 below, \(\bar B_t = \Delta_t B_t\) and \(D = 0\).
- \(\mathbf{h}_0 \leftarrow \mathbf{0}\); for \(t = 1 \dots L\): // one token per pass
- \(\Delta_t \leftarrow \operatorname{softplus}(p + w\, m_t)\); \(B_t \leftarrow W_B \mathbf{x}_t\); \(C_t \leftarrow W_C \mathbf{x}_t\) // selection (101.2)
- \(\bar A_t \leftarrow \exp(\Delta_t A)\); \(\bar B_t \leftarrow \Delta_t B_t\) // discretize (101.3)
- \(\mathbf{h}_t \leftarrow \bar A_t \odot \mathbf{h}_{t-1} + \bar B_t\, u_t\) // keep + write (101.4)
- \(y_t \leftarrow C_t^\top \mathbf{h}_t\) // read (101.4), \(D = 0\)
How to read Figure 2
Press Play, or Step through one line at a time. The highlighted code line and the panel next to it show the formula with the live numbers. With the defaults, ordinary tokens get \(\Delta = \operatorname{softplus}(-1) = 0.313\): the slow state keeps \(e^{-0.0313} = 0.969\) of itself and the fast state only \(e^{-0.627} = 0.534\), so the fast state follows the recent values. The KEY gets \(\Delta = \operatorname{softplus}(5) = 5.007\). Its \(\bar A_2 = e^{-10.01} \approx 0\) erases the fast state, and \(\bar B_1 u_3 = 1.001 \times 9 = 9.012\) writes the KEY into the slow state. Five tokens later the slow state still holds \(9.012 \times 0.969^5 = 7.706\), and the QUERY, whose \(C = (1, 0)\), reads exactly that: \(y_8 = 7.706\). Switch to time-invariant: \(\Delta\), \(B = (0.2, 1.5)\) and \(C = (0.5, 0.5)\) are the same for every token, and \(y_8\) falls to 0.832. Set \(w = 0\) in the selective model to see that \(B\) alone is not enough: the KEY is written with \(\bar B_1 = 0.2 \times 0.313\) only.
The Mamba block
A Mamba layer is not only the SSM. It merges the SSM and the gated MLP into one block, and the network is a stack of identical blocks with no separate attention or FFN:
- Project the input \(\mathbf{x} \in \R^{D}\) up to two vectors of size \(E D\) (expansion \(E = 2\)): a main branch and a gate branch \(\mathbf{z}\).
- Main branch: a short causal convolution over time (kernel 4), then SiLU, then the selective SSM (101.2–101.4), run independently for each of the \(ED\) channels.
- Multiply by \(\operatorname{SiLU}(\mathbf{z})\), then project back down to \(D\).
Most parameters are in the three projections: about \(3ED^2 = 6D^2\) per block, so two Mamba blocks have about the \(12D^2\) of one transformer layer (attention plus MLP). [Certain, Mamba paper] Check it on the real Mamba-2.8B config (\(D = 2560\), 64 layers, \(E = 2\), \(N = 16\), \(\Delta\) rank 160, vocabulary 50,280): each layer has 41.2M parameters (39.3M from the projections), and the whole model 2.77B. [Certain, computed from config.json]
The state per layer is \(ED \times N = 5120 \times 16 = 81{,}920\) numbers, plus 3 past inputs per channel for the short convolution (15,360). Over 64 layers that is 6.2M numbers, about 12 MB in 16-bit, for any context length. The KV cache of a 7B transformer passes 12 MB after about 24 tokens (512 KB per token for Llama 2 7B).
Training a recurrence in parallel: the scan
For each channel and state, (101.4) has the form \(h_t = a_t h_{t-1} + b_t\), with \(a_t = \bar A_t\) and \(b_t = \bar B_t x_t\). Unroll it:
This looks like attention with a special mask: output \(t\) is a weighted sum over all earlier tokens \(j\), with weight \(\prod_{i=j+1}^{t} a_i\). Computing it directly costs \(O(L^2)\). Running the loop costs \(O(L)\) but takes \(L\) steps one after another, which leaves a GPU idle. The trick is to see that the step “apply \((a, b)\)” can be combined. Applying \((a_1, b_1)\) and then \((a_2, b_2)\) maps \(h\) to \(a_2(a_1 h + b_1) + b_2\), which is one step of the same kind:
This operator is associative: \((u \bullet v) \bullet w = u \bullet (v \bullet w)\). Any associative operator can be run as a parallel scan (prefix sum): combine neighbors, then pairs of pairs, and so on. After \(\lceil \log_2 L \rceil\) rounds, position \(t\) holds the combination of steps 1 to \(t\), and its second number is \(h_t\) (starting from \(h_0 = 0\)). Figure 3 runs it next to the plain loop (the “recurrent mode” used for decoding), on the same numbers, one clock tick at a time.
- Recurrent mode (decoding)
- \(h_0 \leftarrow 0\); for \(t = 1 \dots L\): \(h_t \leftarrow a_t h_{t-1} + b_t\) // one step per tick
- Parallel scan (training), Algorithm 2
- \(s \leftarrow 1\); while \(s \lt L\):
- for all \(t \gt s\) in parallel: \((a_t, b_t) \leftarrow (a_{t-s}, b_{t-s}) \bullet (a_t, b_t)\) // (101.7)
- \(s \leftarrow 2s\)
- return \(h_t = b_t\) for all \(t\)
How to read Figure 3
One tick is one parallel step on a GPU: all orange arrows of a round run at the same time. With the simple numbers (\(L = 8\)), the loop gives \(h = 1, 2.9, 3.29, 2.632, 3.632, 0.816, 2.163, 2.947\). After tick 3 the scan has the same 8 numbers in its last row, while the loop is only at \(h_3\). For example, in round 1 the last cell computes \((0.2, 2) \bullet (0.9, 1) = (0.18,\ 0.9 \times 2 + 1) = (0.18, 2.8)\). With \(L = 16\) the scan needs 4 rounds against 16 loop steps, and 20 rounds would cover a million tokens. The price is extra work: the scan does \(7 + 6 + 4 = 17\) combines for \(L = 8\) and 49 for \(L = 16\), against \(L - 1\) for the loop. This simple form does \(O(L \log L)\) work; the Blelloch form does \(O(L)\) work with about twice the depth. Mamba’s kernel uses a work-efficient scan. [Likely] The third button feeds the scan the fast state of Figure 2 (\(a_t = \bar A_{t,2}\), \(b_t = \bar B_{t,2} u_t\)); it follows the sliders there.
Hardware-aware: never write the big state to memory
The scan solves the parallelism problem, but not the memory problem. The expanded states \(\bar A_t, \bar B_t, \mathbf{h}_t\) have shape (batch, \(L\), \(ED\), \(N\)): \(N = 16\) times larger than the input. Writing them to GPU main memory (HBM) and reading them back would make the layer memory-bound. Mamba’s kernel loads \(\Delta, A, B, C\) into fast on-chip memory (SRAM), does the discretization and the scan there, and writes only the outputs \(y\) (size \(B \times L \times ED\)). In the backward pass it recomputes the states instead of storing them, the same idea as FlashAttention (session 124, session 42). The paper reports that this fused scan is faster than FlashAttention-2 beyond 2K tokens, up to 20–40× faster than a plain PyTorch scan, and uses about the same memory as an optimized transformer with FlashAttention. [Certain, Mamba paper]
- input: token vector \(\mathbf{x} \in \R^D\); state \(\mathbf{h} \in \R^{ED \times N}\); last 3 conv inputs \(\mathbf{c} \in \R^{ED \times 3}\)
- \(\mathbf{u}, \mathbf{z} \leftarrow W_{\text{in}} \mathbf{x}\) // two vectors of size ED
- \(\mathbf{u} \leftarrow \operatorname{SiLU}(\operatorname{conv}(\mathbf{c}, \mathbf{u}))\); shift \(\mathbf{u}\) into \(\mathbf{c}\) // kernel 4, causal
- \(\Delta \leftarrow \operatorname{softplus}(\mathbf{p} + W_\Delta \mathbf{u})\); \(B \leftarrow W_B \mathbf{u}\); \(C \leftarrow W_C \mathbf{u}\) // (101.2), the selection
- \(\mathbf{h} \leftarrow \exp(\Delta \otimes A) \odot \mathbf{h} + (\Delta \otimes B) \odot \mathbf{u}\) // (101.3)–(101.4), all ED·N entries at once
- \(\mathbf{y} \leftarrow \mathbf{h}\, C + D \odot \mathbf{u}\) // size ED
- return \(W_{\text{out}}\,(\mathbf{y} \odot \operatorname{SiLU}(\mathbf{z}))\), and the new \(\mathbf{h}, \mathbf{c}\) // cost and memory do not depend on the position t
- input: pairs \((a_t, b_t)\) for \(t = 1..L\) // \(a_t = \bar A_t\), \(b_t = \bar B_t x_t\)
- \(s \leftarrow 1\)
- while \(s \lt L\):
- for all \(t \ge s + 1\) in parallel: \((a_t, b_t) \leftarrow (a_{t-s}, b_{t-s}) \bullet (a_t, b_t)\) // (101.7), read old values
- \(s \leftarrow 2s\)
- return \(h_t = b_t\) for all \(t\) // \(\lceil\log_2 L\rceil\) rounds
With these two pieces, Mamba is fast on both sides. The paper reports that Mamba-3B beats transformers of the same size and matches transformers twice its size, in pretraining and downstream evaluation, and that inference throughput is about 5× higher than a transformer’s, because without a KV cache it can use much larger batches. [Certain, Mamba paper] The throughput comparison is for a 6.9B Mamba against a 1.3B transformer, so the gap at equal size is larger. Mamba-2 later restricted \(A\) to a scalar per head, which lets most of the work run as matrix multiplications; its core layer is reported 2–8× faster than Mamba’s. [Certain, Mamba-2 paper]
RWKV and RetNet: attention that can run as an RNN
RWKV and RetNet come from the other side. In session 99 we saw that linear attention, \(\mathbf{o}_t = \sum_{j \le t} (\mathbf{q}_t^\top \mathbf{k}_j)\, \mathbf{v}_j\), can be computed with a running state \(S_t = S_{t-1} + \mathbf{k}_t \mathbf{v}_t^\top\). Its weakness: the state never forgets, so old and new tokens count the same. Both models add a decay.
RWKV: a weighted average with per-channel decay
RWKV (the name comes from its four vectors: receptance \(r\), weight decay \(w\), key \(k\), value \(v\)) works channel by channel. For each channel it computes a weighted average of past values, where token \(i\) gets weight \(e^{k_i}\) times a decay \(e^{-(t-1-i)w}\). The current token gets a separate bonus \(u\). In RWKV-4:
- Read the symbols
- \(w \ge 0\)
- a learned decay per channel: large \(w\) forgets fast, small \(w\) remembers long. It does not depend on the input in RWKV-4
- \(u\)
- a learned bonus per channel for the current token
- \(k_i, v_i\)
- key and value of token \(i\) in this channel (numbers, not vectors: everything is per channel)
- \(r_t\)
- receptance: the output is \(\mathbf{o}_t = W_o(\sigma(\mathbf{r}_t) \odot \mathbf{wkv}_t)\), so \(\sigma(r)\) gates how much of the average is used
The keys, values and receptance are computed from a token shift: a learned mix of the current and the previous token, for example \(\mathbf{k}_t = W_k(\mu_k \odot \mathbf{x}_t + (1 - \mu_k) \odot \mathbf{x}_{t-1})\), where \(\mu_k\) is a learned vector of mixing weights. [Certain, RWKV paper] The sums in (101.8) can be computed in parallel over the sequence for training. For decoding, two running numbers per channel are enough:
The RWKV paper trained models from 169M to 14B parameters on 330B tokens of the Pile and reports quality similar to transformers of the same size. [Certain, RWKV paper] Its own limitations section says the design “funnels” information through one vector, which limits recall of fine details over very long contexts, and that the model is sensitive to the order of information in the prompt. [Certain, RWKV paper] Later versions (RWKV-5, RWKV-6) use matrix-valued states and make the decay depend on the input, moving closer to Mamba. [Likely]
RetNet: retention with three forms
RetNet (Retentive Network) writes its layer, retention, exactly like attention without the softmax, with a decay mask \(D\):
\(D\) is a causal mask and a decay in one: token \(m\) seen from position \(n\) is scaled by \(\gamma^{n-m}\), with \(0 \lt \gamma \lt 1\). The same output can be computed as a recurrence with a matrix state \(S_n \in \R^{d_k \times d_v}\):
This gives RetNet its three forms. [Certain, RetNet paper] The parallel form (101.10) trains like attention, with matrix multiplications. The recurrent form (101.11) decodes with \(O(1)\) cost per token. The chunkwise form, for long sequences, uses the parallel form inside chunks (512 tokens in the paper’s experiments) and passes the state \(S\) from chunk to chunk.
Each head has its own \(\gamma\). The paper defines \(\gamma = 1 - 2^{-5 - h}\) for head \(h = 0, 1, \dots\), so the heads have memory lengths \(1/(1-\gamma) = 32, 64, 128, \dots\) tokens: some heads look at the near past, others far back. [Certain, RetNet paper] (The experiments use a slightly different spacing, from \(1/32\) to \(1/512\).) Queries and keys are also rotated by position, in the style of RoPE and xPos, and the outputs pass through GroupNorm and a swish gate. RetNet reports that a 6.7B model at 8K tokens decodes 8.4× faster and uses 70% less memory than a transformer with a KV cache. [Certain, RetNet paper]
- input: \(Q, K, V\) of length \(L\), decay \(\gamma\), chunk size \(c\); state \(R \leftarrow 0\)
- for each chunk \(i\) with rows \(Q_{[i]}, K_{[i]}, V_{[i]}\):
- inner \(\leftarrow (Q_{[i]} K_{[i]}^\top \odot D_{c\times c})\, V_{[i]}\) // (101.10) inside the chunk, parallel
- cross \(\leftarrow (Q_{[i]} R) \odot \xi\), with \(\xi_n = \gamma^{n+1}\) for row \(n = 0..c-1\) // what earlier chunks left in the state
- output rows of chunk \(i\) \(\leftarrow\) inner + cross
- \(R \leftarrow \gamma^{c} R + K_{[i]}^\top (V_{[i]} \odot \zeta)\), with \(\zeta_n = \gamma^{c-1-n}\) // (101.11) for c steps at once
- return all outputs // cost \(O(L \cdot c \cdot d)\) instead of \(O(L^2 \cdot d)\)
One view of all three
Look at the three recurrences side by side. Each keeps a state, multiplies it by a decay, and adds an outer product of a key and a value. Each reads the state with a query:
Only the decay \(G_t\) and the names change. For Mamba, write \(\mathbf{k}_t = B_t\) (size \(N\)), \(\mathbf{v}_t = \Delta_t \odot \mathbf{x}_t\) (size \(ED\)) and \(\mathbf{q}_t = C_t\): the state is an \(N \times ED\) matrix, the same as \(\mathbf{h}\) in (101.4).
| Model | Decay \(G_t\) | Depends on the input? | Parallel training | State per layer |
|---|---|---|---|---|
| Linear attention | 1 (no decay) | no | attention form, or cumulative sum | \(d_k \times d_v\) per head |
| RetNet | \(\gamma\), one scalar per head | no | parallel or chunkwise form | \(d_k \times d_v\) per head |
| RWKV-4 | \(e^{-w}\), one per channel | no | sums of (101.8) | 2 numbers per channel (plus the shifted token) |
| Mamba (S6) | \(\exp(\Delta_t A)\), per channel and state | yes | parallel scan in SRAM | \(ED \times N\) |
| Mamba-2 (SSD) | \(\exp(\Delta_t a)\), one scalar per head | yes | chunkwise, mostly matrix multiplications | \(N \times P\) per head |
(101.6) is the parallel form of all of them: output \(t\) mixes the inputs \(j \le t\) with a weight equal to the product of the decays between \(j\) and \(t\). The Mamba-2 paper builds a full theory on this, showing that such models and masked attention are two ways to compute with the same structured matrix (“state space duality”). [Certain, Mamba-2 paper] Figure 4 draws that decay matrix for the three models.
How to read Figure 4
RetNet: every diagonal band has the same color, because the weight depends only on the distance \(t - j\). The slider sets \(\gamma\). RWKV-4: the same banded shape with decay \(e^{-w}\), plus a separate bonus \(e^{u}\) (\(u = 0.5\)) on the diagonal for the current token. Mamba: the ordinary tokens have \(\Delta = 0.1\), and token 7 has the \(\Delta\) from the slider. A large \(\Delta\) at token 7 cuts the matrix in two: tokens 1–6 almost vanish for all later steps. Only an input-dependent decay can do this.
Hyena: long convolutions with gates
H3 (“Hungry Hungry Hippos”) was an earlier step. Its authors used synthetic tasks to show that SSMs struggle to recall earlier tokens and to compare tokens across the sequence. [Certain, H3 paper] H3 fixed part of this with two SSMs and multiplicative gates, roughly \(\mathbf{q} \odot \mathrm{SSM}_{\text{diag}}(\mathrm{SSM}_{\text{shift}}(\mathbf{k}) \odot \mathbf{v})\), and found that a 125M hybrid with just two attention layers beat a transformer by 1.0 perplexity on OpenWebText. [Certain, H3 paper] Hyena generalizes the H3 pattern. An order-\(N\) Hyena operator takes \(N+1\) linear projections of the input, \(\mathbf{v}, \mathbf{x}^1, \dots, \mathbf{x}^N\), and alternates long convolutions with element-wise gates:
- Read the symbols
- \(\mathbf{h}^n * \mathbf{z}^n\)
- a causal convolution along the sequence, separately per channel, with a filter as long as the whole input
- \(\mathbf{x}^n \odot\)
- a gate: element-wise product with a projection of the input. This is where the data dependence comes from
- \(N\)
- the order; most Hyena experiments use 2, the WikiText-103 language models use 3 [Certain]
The filters cannot be stored as free parameters (one number per position would be too many and would fix the length). Hyena makes them implicit: a small FFN maps a positional encoding of \(t\) to the filter value, and a decaying window shapes it:
The decay rate \(\alpha\) differs across channels, so some channels look far back and some look near. Is the kernel “data-dependent”? The filters themselves are not: they depend only on the position. But the whole operator is: written as a matrix, \(\mathbf{y} = \operatorname{diag}(\mathbf{x}^N) T_{h^N} \cdots \operatorname{diag}(\mathbf{x}^1) T_{h^1} \mathbf{v}\), where each \(T_h\) is a fixed lower-triangular (Toeplitz) matrix and each \(\operatorname{diag}(\mathbf{x}^n)\) changes with the input. So the effective mixing matrix is built from the data, like an attention matrix, but without ever forming it.
Training cost: a convolution of length \(L\) costs \(O(L^2)\) directly, but \(O(L \log L)\) with the FFT (pad to \(2L\), multiply the spectra, transform back). The paper reports Hyena at 2× the speed of optimized attention at 8K tokens and 100× at 64K, and transformer quality with 20% less training compute at 2K tokens on the Pile at 355M parameters. [Certain, Hyena paper] On associative recall with 30 symbols, Hyena reached 100% at 30K and 64K tokens, where FlashAttention transformers reached 32.4% and 26.7%. [Certain, Hyena paper]
The price: exact recall from a fixed state
Every model in this session squeezes the whole past into a state of fixed size. Attention does not squeeze: its KV cache keeps every key and value. A simple count shows what this means. A state of \(S\) numbers cannot store \(L\) arbitrary facts once \(L\) facts need more than \(S\) numbers. A model that must later answer “what came after the key ID-4471?” for any key it saw needs room for every pair. No choice of gates can fix that; gates only choose which facts to drop.
Figure 5 runs a small test of this. A linear-attention state \(S = \sum_i \mathbf{k}_i \mathbf{v}_i^\top\) (the core of (101.12), \(d \times d\) numbers) stores \(n\) random key–value pairs. Then we query with each key and check if the nearest stored value is the right one. Attention, which keeps all \(n\) keys, finds the right one every time.
How to read Figure 5
Reading the state with key \(\mathbf{k}_j\) gives \(\mathbf{v}_j\) plus “crosstalk” \(\sum_{i \ne j} (\mathbf{k}_i^\top \mathbf{k}_j)\, \mathbf{v}_i\) from all other pairs. Random keys in \(d\) dimensions overlap by about \(1/\sqrt{d}\), so the crosstalk grows with \(n\). With \(d = 16\) the accuracy is 100% for 8 pairs, 65.6% for 32 and 31.3% for 64. Doubling \(d\) roughly doubles the number of pairs that fit. Attention stays at 100% but its memory, \(2nd\) numbers, grows with every pair.
Real models show the same pattern. [Certain for each of these papers]
- Zoology trained 17 attention and gated-convolution language models. The best gated-convolution models were up to 2.1 perplexity behind attention on the Pile, and about 82% of that gap came from associative recall. A 70M attention model beat a 1.4B gated-convolution model on recall. They introduced the harder multi-query associative recall (MQAR) task.
- Repeat After Me proves that a two-layer transformer can copy strings of exponential length, while models with a fixed-size state are limited by that state, and finds that pretrained transformers copy and retrieve from context far better than pretrained SSMs.
- Jamba compared 1.3B models trained on 250B tokens. On IMDB (few-shot classification), pure Mamba scored 48.8, pure attention 84.1 and the hybrid 90.9. Pure Mamba often ignored the answer format in the prompt (“Very Good” instead of “Positive”).
Hybrids: a few attention layers are enough
If a fixed state is lossy and a KV cache is expensive, mix them: most layers are recurrent, a few are attention. The few attention layers give exact lookup; the KV cache shrinks in proportion to how few they are. For a model with \(\ell_a\) attention layers among \(\ell\) layers, the decode memory per sequence is
- Read the symbols
- \(n_{kv}, d_h\)
- number of key–value heads and head size of the attention layers
- \(b\)
- bytes per number (2 for 16-bit)
- \(s\)
- numbers in one recurrent layer’s state (for a Mamba layer: \(ED \times N\) plus the short-convolution buffer)
Jamba (AI21) is the best-known example. [Certain, Jamba paper and config.json] It has 32 layers in 4 blocks of 8. Each block has 1 attention layer and 7 Mamba layers (ratio 1:7), and every second layer uses a mixture-of-experts MLP with 16 experts and top-2 routing (session 29). That gives 52B total and 12B active parameters, fits on one 80 GB GPU, and supports 256K tokens. The attention layers use GQA with 8 KV heads of size 128, and the model needs no positional encoding: the Mamba layers already know the order.
Llama 2 7B (32 layers, 32 KV heads of 128): \(2 \times 32 \times 32 \times 128 \times 2 = 512\) KB per token, so \(512 \text{ KB} \times 262{,}144 = 128\) GB.
Mixtral (32 layers, 8 KV heads): 128 KB per token, 32 GB.
Jamba (4 attention layers, 8 KV heads): \(2 \times 4 \times 8 \times 128 \times 2 = 16\) KB per token, 4 GB. Its 28 Mamba layers add \(28 \times 8192 \times (16 + 3) \times 2\) bytes = 8.3 MB of state, fixed. These are the 128 / 32 / 4 GB in Table 1 of the Jamba paper. (GB here means \(2^{30}\) bytes.)
How to read Figure 6
The bar of pure Mamba-2.8B does not move with the context length: 11.9 MB per sequence. The transformer bars grow linearly; at 1M tokens even the GQA model needs 128 GB per sequence. Move the attention-layer slider: memory falls almost in proportion to the number of attention layers, until the fixed Mamba states (about 9.5 MB) are all that is left. Raise the batch to see why fixed states give Mamba its higher throughput: many more sequences fit next to the weights.
Other hybrids follow the same idea. H3 already used two attention layers. Griffin (Google DeepMind) mixes gated linear recurrences with local (sliding-window) attention, matches Llama 2 with over 6 times fewer training tokens, and was scaled to 14B parameters; RecurrentGemma is built on it. [Certain for Griffin; Likely for RecurrentGemma] Zoology’s own fix was a convolution model with a little input-dependent sparse attention, which closed 97.4% of the gap. [Certain] The common lesson: keep the recurrent layers for cheap, smooth context, and spend a small amount of attention on exact lookup.
Code: check that the fast forms equal the slow ones
Each model in this session has two ways to compute the same thing, one for training and one for decoding. The code below checks four of these identities on random inputs: Mamba’s sequential scan against its matrix form (101.6), RetNet’s parallel form against its recurrent form, RWKV’s direct sum (101.8) against its state (101.9), and Hyena’s FFT convolution against a direct one. Each line should print a difference near \(10^{-5}\) or smaller (float32 rounding).
import torch, torch.nn.functional as F torch.manual_seed(0) B, L, D, N = 2, 64, 8, 4 # batch, length, channels, state size per channel # ---------- 1) Mamba's selective scan: sequential (decode) vs matrix form (101.6) ---------- x = torch.randn(B, L, D) A = -torch.exp(torch.randn(D, N)) # negative real diagonal A, shape (D, N) dt = F.softplus(torch.randn(B, L, D) - 1.0) # Delta_t, one per token and channel Bt = torch.randn(B, L, N) # B_t = Linear_N(x_t) Ct = torch.randn(B, L, N) # C_t = Linear_N(x_t) def scan_sequential(x, dt, A, Bt, Ct): h = torch.zeros(B, D, N); ys = [] for t in range(L): Abar = torch.exp(dt[:, t, :, None] * A) # (B, D, N) Bbar_x = dt[:, t, :, None] * Bt[:, t, None, :] * x[:, t, :, None] h = Abar * h + Bbar_x # h_t = Abar_t h_{t-1} + Bbar_t x_t ys.append((h * Ct[:, t, None, :]).sum(-1)) # y_t = C_t h_t return torch.stack(ys, 1) # (B, L, D) def scan_matrix(x, dt, A, Bt, Ct): logA = dt[..., None] * A # (B, L, D, N): log of Abar_t cs = torch.cumsum(logA, 1) # sum of log Abar_i for i up to t seg = cs[:, :, None] - cs[:, None, :] # (B, t, j, D, N): sum over j < i <= t mask = torch.tril(torch.ones(L, L, dtype=torch.bool))[None, :, :, None, None] decay = torch.exp(seg.masked_fill(~mask, float("-inf"))) u = dt[..., None] * Bt[:, :, None, :] * x[..., None] # Bbar_j x_j, (B, L, D, N) h = (decay * u[:, None]).sum(2) # all states at once return (h * Ct[:, :, None, :]).sum(-1) y1, y2 = scan_sequential(x, dt, A, Bt, Ct), scan_matrix(x, dt, A, Bt, Ct) print("selective scan max diff:", (y1 - y2).abs().max().item()) # ---------- 2) RetNet retention: parallel form (101.10) vs recurrent form (101.11) ---------- dk = 16; gamma = 1 - 2 ** -5 Q, K, V = torch.randn(3, L, dk).unbind(0) n = torch.arange(L) Dm = (gamma ** (n[:, None] - n[None, :]).clamp(min=0)) * (n[:, None] >= n[None, :]) par = (Q @ K.T * Dm) @ V # (Q K^T ⊙ D) V Sst = torch.zeros(dk, dk); rec = [] for t in range(L): Sst = gamma * Sst + K[t, :, None] * V[t, None, :] # S_n = gamma S_{n-1} + K_n^T V_n rec.append(Q[t] @ Sst) print("retention max diff:", (par - torch.stack(rec)).abs().max().item()) # ---------- 3) RWKV-4 WKV: recurrent state (a, b) vs direct sum ---------- w = torch.rand(D) * 0.5; u = torch.randn(D) * 0.1 k, v = torch.randn(L, D) * 0.5, torch.randn(L, D) a_s = torch.zeros(D); b_s = torch.zeros(D); wkv_rec = [] for t in range(L): e = torch.exp(u + k[t]) wkv_rec.append((a_s + e * v[t]) / (b_s + e)) # (101.9) a_s = torch.exp(-w) * a_s + torch.exp(k[t]) * v[t] b_s = torch.exp(-w) * b_s + torch.exp(k[t]) wkv_dir = [] for t in range(L): i = torch.arange(t) wt = torch.exp(-(t - 1 - i)[:, None] * w + k[:t]) # e^{-(t-1-i)w + k_i} num = (wt * v[:t]).sum(0) + torch.exp(u + k[t]) * v[t] den = wt.sum(0) + torch.exp(u + k[t]) wkv_dir.append(num / den) # (101.8) print("rwkv wkv max diff:", (torch.stack(wkv_rec) - torch.stack(wkv_dir)).abs().max().item()) # ---------- 4) Hyena's long convolution: FFT, O(L log L), vs direct, O(L^2) ---------- z = torch.randn(D, L); h = torch.randn(D, L) * torch.exp(-0.05 * torch.arange(L)) # decaying filter (101.14) direct = torch.stack([torch.stack([(h[c, :t + 1].flip(0) * z[c, :t + 1]).sum() for t in range(L)]) for c in range(D)]) fftc = torch.fft.irfft(torch.fft.rfft(z, n=2 * L) * torch.fft.rfft(h, n=2 * L), n=2 * L)[:, :L] gate = torch.randn(D, L) print("fft long conv max diff:", (direct - fftc).abs().max().item()) print("order-1 Hyena output shape:", tuple((gate * fftc).shape)) # y = x1 ⊙ (h * v), (101.13)
On a CPU with PyTorch 2 this prints differences of about \(8 \times 10^{-6}\), \(2 \times 10^{-5}\), \(2 \times 10^{-7}\) and \(2 \times 10^{-6}\). [Certain, run for this page] Note the cost of scan_matrix: it builds an \(L \times L\) tensor per channel and state. That is the quadratic “attention form”; it is fine for chunks, which is exactly how Mamba-2 and chunkwise RetNet use it.
Where this is used
| Setting | Typical choice | Why |
|---|---|---|
| Long-context LLM serving (256K tokens) | Hybrid: Jamba (1 attention per 8 layers, MoE) | 4 GB KV cache instead of 32 GB; attention layers keep in-context learning and recall |
| Pure-SSM language models | Mamba-family models such as Falcon Mamba 7B (64 layers, state size 16) and Codestral Mamba [Likely] | Constant memory per sequence, high throughput at large batch |
| Recurrent LLMs for long or streaming text | RWKV (up to 14B in the paper), Griffin / RecurrentGemma [Likely] | Fixed state, cost per token independent of the position |
| On-device and edge generation | Small recurrent or hybrid models [Likely] | No KV cache growth, so memory is predictable on a phone |
| Video classification and action recognition | VideoMamba (Mamba over spatio-temporal patches); Vision Mamba (Vim) for images | Linear cost in the number of patches, so long, high-resolution clips fit (session 202) |
| Streaming key-moment detection, live video | Recurrent layer over frame features, one update per frame [Speculation] | The state summarizes the stream so far at fixed cost; add attention if exact matching to earlier frames is needed |
| Long video QA and Video-RAG | Hybrid: recurrent layers for the long frame sequence plus attention or retrieval for exact lookup [Speculation] | Pure recurrent memory forgets details; retrieval or attention gives exact access (session 206, session 210) |
| DNA and audio modeling | Mamba and Hyena (both papers report genomics results) | Very long sequences with local structure |
Common mistakes
- “Linear cost” means linear in training, not free in decoding for every model. Mamba, RWKV and RetNet decode at constant cost per token. Hyena does not, unless the filters are turned into a recurrence.
- Saying Mamba is “just S4 with gates”. The key change is that \(\Delta, B, C\) depend on the input. That kills the convolution view and needs a scan; gates alone (as in H3) do not give the selection.
- Computing the scan in low precision. Products of many decays (101.6) underflow quickly. Implementations keep \(A\) as \(-\exp(A_{\log})\), work with sums of logs, and keep the state in FP32. [Likely]
- Forgetting the short convolution and conv state in decoding. A Mamba layer’s decode state is the SSM state and the last 3 inputs of the kernel-4 convolution. Dropping the second gives wrong outputs.
- Comparing memory without fixing the context. A fixed state wins only when the KV cache would be large. At 1K tokens, a 7B transformer’s KV cache is 512 MB, often small next to the weights.
- Judging only by perplexity. Recurrent models can match perplexity and still fail at copying, retrieval and few-shot formats (Zoology, Jamba’s IMDB result). Test recall tasks too.
- Running RetNet’s parallel form at long lengths. It builds an \(L \times L\) matrix like attention. Use the chunkwise form for long training sequences.
- Expecting pure SSMs to extrapolate everything. Mamba extrapolated an induction-head task from 256 to about 1M tokens in the paper, but that is one synthetic task; general long-context quality still needs testing. [Certain for the induction result]
Interview questions
What does “selective” mean in Mamba, and why does it matter?basic
How does \(\Delta\) act like the gate of an RNN?core
Mamba is a recurrence. How is it trained in parallel?core
Why does RetNet have three forms? When do you use each?core
Write RWKV’s WKV in recurrent form. What state does a layer keep?core
Put linear attention, RetNet, RWKV and Mamba in one formula. What is the real difference?advanced
In what sense is Hyena’s kernel data-dependent? What is its decode cost?advanced
Why are SSMs and linear-attention models weak at copying and exact recall?core
Compute the KV cache of Jamba vs Mixtral at 256K tokens. Why does Jamba still keep attention?core
Why is Mamba’s decode throughput higher than a transformer’s, if both are memory-bound?advanced
You must serve a 128K-context assistant that cites exact passages. Pure SSM, transformer, or hybrid?advanced
Exercises
- A Mamba channel has \(z_t = 0\), so \(\Delta_t = \operatorname{softplus}(0)\). Compute \(\Delta_t\) and the gate \(g_t\) of (101.5).
- Combine \((0.5, 1) \bullet (0.9, 2)\) with (101.7). Check that it equals running \(h_t = a_t h_{t-1} + b_t\) twice from \(h_0 = 0\).
- A RetNet head has \(\gamma = 1 - 2^{-7}\). What is its memory length \(1/(1 - \gamma)\)? What weight does a token 128 steps back get?
- How many numbers are in the SSM state of one Mamba-2.8B layer? Of the whole model, including the convolution buffers?
- Using (101.15), what is the KV cache at 1M (\(2^{20}\)) tokens for Jamba’s shapes, and for Mixtral?
- For \(L = 65{,}536\), roughly how many times fewer operations does an FFT convolution need than a direct one (use \(L^2\) vs \(L \log_2 L\))?
- In Figure 5, set \(d = 32\). How many pairs can you store before accuracy drops below about 80%? What does that say about the size of the state compared with what it stores?
Answerscheck
Key takeaways
- S4 is time-invariant and cannot choose what to remember. Mamba makes \(\Delta, B, C\) functions of the token (101.2); \(\Delta\) then acts as an RNN gate (101.5) that can store, skip or reset.
- Without time invariance there is no convolution view. Mamba trains with an associative parallel scan (101.7) fused in SRAM, and decodes with a fixed state of about 12 MB for the 2.8B model.
- RWKV (101.8–101.9) and RetNet (101.10–101.11) are linear attention with a decay: a parallel form for training, a recurrent form for decoding, and (RetNet) a chunkwise form for long sequences.
- All three fit \(S_t = G_t \odot S_{t-1} + \mathbf{k}_t\mathbf{v}_t^\top\) (101.12). The decisive difference is whether the decay \(G_t\) depends on the input.
- Hyena (101.13–101.14) uses implicit long filters and gates, trains in \(O(L \log L)\), but does not decode at constant cost.
- A fixed state is lossy: exact recall and copying suffer (Zoology, Repeat After Me, Jamba’s IMDB result). Hybrids such as Jamba (1 attention layer per 8) keep recall and cut the KV cache to 4 GB at 256K tokens (101.15).
Key formulas
References for this session
- Gu & Dao (2023). Mamba: Linear-Time Sequence Modeling with Selective State Spaces
- Peng et al. (2023). RWKV: Reinventing RNNs for the Transformer Era
- Sun et al. (2023). Retentive Network: A Successor to Transformer for Large Language Models
- Poli et al. (2023). Hyena Hierarchy: Towards Larger Convolutional Language Models
- Fu et al. (2022). Hungry Hungry Hippos: Towards Language Modeling with State Space Models
- Lieber et al. (2024). Jamba: A Hybrid Transformer-Mamba Language Model
- Gu & Dao (2023). Mamba: Linear-Time Sequence Modeling with Selective State Spaces
- Peng et al. (2023). RWKV: Reinventing RNNs for the Transformer Era
- Sun et al. (2023). Retentive Network: A Successor to Transformer for Large Language Models
- Poli et al. (2023). Hyena Hierarchy: Towards Larger Convolutional Language Models
- Fu et al. (2022). Hungry Hungry Hippos: Towards Language Modeling with State Space Models
- Lieber et al. (2024). Jamba: A Hybrid Transformer-Mamba Language Model
- Gu et al. (2021). Efficiently Modeling Long Sequences with Structured State Spaces
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Dao & Gu (2024). Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality
- Arora et al. (2023). Zoology: Measuring and Improving Recall in Efficient Language Models
- Jelassi et al. (2024). Repeat After Me: Transformers are Better than State Space Models at Copying
- De et al. (2024). Griffin: Mixing Gated Linear Recurrences with Local Attention for Efficient Language Models
- Li et al. (2024). VideoMamba: State Space Model for Efficient Video Understanding
- Zhu et al. (2024). Vision Mamba: Efficient Visual Representation Learning with Bidirectional State Space Model