LLM & VLM courseBlog
101Track 5: LLM inference and serving · session 24 of 65

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.

Time: 3 to 4 hours (reading 2 hours, exercises 1 to 2 hours)Level: AdvancedBefore this: Sessions 80 (the KV cache), 99 (kernel-based linear attention) and 100 (state space models from HiPPO to S4)

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:

\[ \mathbf{h}_t = \bar{A}\, \mathbf{h}_{t-1} + \bar{B}\, x_t, \qquad y_t = C\, \mathbf{h}_t \tag{101.1} \]

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\):

\[ \Delta_t = \operatorname{softplus}\!\big(\mathbf{p} + W_\Delta\, \mathbf{x}_t\big) \in \R^{D}, \qquad B_t = W_B\, \mathbf{x}_t \in \R^{N}, \qquad C_t = W_C\, \mathbf{x}_t \in \R^{N} \tag{101.2} \]
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\):

\[ \bar{A}_t = \exp(\Delta_t A), \qquad \bar{B}_t = (\Delta_t A)^{-1}\big(\exp(\Delta_t A) - I\big)\, \Delta_t B_t \;\approx\; \Delta_t B_t \tag{101.3} \]

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:

\[ \mathbf{h}_t = \bar{A}_t \odot \mathbf{h}_{t-1} + \bar{B}_t\, x_t, \qquad y_t = C_t^\top \mathbf{h}_t + D\, x_t \tag{101.4} \]

(\(\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

\[ h_t = (1 - g_t)\, h_{t-1} + g_t\, x_t, \qquad g_t = 1 - e^{-\Delta_t} = \sigma(z_t) \tag{101.5} \]

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.

time-invariant (one \(\Delta\))selective (\(\Delta\) depends on the token)
Figure 1. A one-state SSM reads 8 tokens with values \(2, -1, 9, 1, -2, 3, 0, 1\). Token 3 (value 9) is the KEY we want to remember. Each bar is the weight of that token inside the final state \(h_8\): \(g_i \prod_{j \gt i} (1 - g_j)\).
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.

Worked example: the numbers in Figure 1

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\).

\(\bar A\): keep (1 = keep all)\(\bar B_t u_t\): what is writtenstate \(h\) (red if negative)\(C_t\): what is readcurrent token
  1. \(\mathbf{h}_0 \leftarrow \mathbf{0}\); for \(t = 1 \dots L\): // one token per pass
  2.   \(\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)
  3.   \(\bar A_t \leftarrow \exp(\Delta_t A)\); \(\bar B_t \leftarrow \Delta_t B_t\) // discretize (101.3)
  4.   \(\mathbf{h}_t \leftarrow \bar A_t \odot \mathbf{h}_{t-1} + \bar B_t\, u_t\) // keep + write (101.4)
  5.   \(y_t \leftarrow C_t^\top \mathbf{h}_t\) // read (101.4), \(D = 0\)
Figure 2. The selective SSM (101.2)–(101.4) computed step by step for one channel, \(N = 2\), 8 tokens with values \(2, -1, 9, 1, -2, 3, 0, 1\). Token 3 is the KEY and token 8 is the QUERY. Each token takes four steps, one per line of the loop. Columns are tokens; the rows show \(\Delta_t\), the keep factors \(\bar A_t\), the written amounts \(\bar B_t u_t\), the state \(\mathbf{h}_t\), the read vector \(C_t\) and the output \(y_t\).
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:

  1. 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}\).
  2. 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.
  3. 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:

\[ h_t = \sum_{j=1}^{t} \Big( \prod_{i=j+1}^{t} a_i \Big)\, b_j \tag{101.6} \]

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:

\[ (a_1, b_1) \bullet (a_2, b_2) = (a_1 a_2,\; a_2 b_1 + b_2) \tag{101.7} \]

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: one \(h\) per tickcombines of the current roundfinal (equals \(h_t\))cell shown in the formula panel
  1. Recurrent mode (decoding)
  2. \(h_0 \leftarrow 0\); for \(t = 1 \dots L\): \(h_t \leftarrow a_t h_{t-1} + b_t\) // one step per tick
  3. Parallel scan (training), Algorithm 2
  4. \(s \leftarrow 1\); while \(s \lt L\):
  5.   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)
  6.   \(s \leftarrow 2s\)
  7. return \(h_t = b_t\) for all \(t\)
Figure 3. Recurrent mode against a parallel scan (Hillis–Steele form) of \(h_t = a_t h_{t-1} + b_t\). Top lane: the loop, one state per clock tick. Below: the scan; each cell holds a pair \((a, b)\), and in round \(r\) cell \(t\) combines with cell \(t - 2^{r-1}\) using (101.7). Both run on the same pairs; click any scan cell to see its combine in the formula panel.
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]

Algorithm 1: one Mamba layer during decoding (one new token)
  1. 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}\)
  2. \(\mathbf{u}, \mathbf{z} \leftarrow W_{\text{in}} \mathbf{x}\) // two vectors of size ED
  3. \(\mathbf{u} \leftarrow \operatorname{SiLU}(\operatorname{conv}(\mathbf{c}, \mathbf{u}))\); shift \(\mathbf{u}\) into \(\mathbf{c}\) // kernel 4, causal
  4. \(\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
  5. \(\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
  6. \(\mathbf{y} \leftarrow \mathbf{h}\, C + D \odot \mathbf{u}\) // size ED
  7. 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
Algorithm 2: parallel scan for training (Hillis–Steele)
  1. input: pairs \((a_t, b_t)\) for \(t = 1..L\) // \(a_t = \bar A_t\), \(b_t = \bar B_t x_t\)
  2. \(s \leftarrow 1\)
  3. while \(s \lt L\):
  4.   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
  5.   \(s \leftarrow 2s\)
  6. 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:

\[ \mathrm{wkv}_t = \frac{\sum_{i=1}^{t-1} e^{-(t-1-i)w + k_i}\, v_i \;+\; e^{u + k_t}\, v_t}{\sum_{i=1}^{t-1} e^{-(t-1-i)w + k_i} \;+\; e^{u + k_t}} \tag{101.8} \]
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:

\[ \mathrm{wkv}_t = \frac{a_{t-1} + e^{u + k_t} v_t}{b_{t-1} + e^{u + k_t}}, \qquad a_t = e^{-w} a_{t-1} + e^{k_t} v_t, \qquad b_t = e^{-w} b_{t-1} + e^{k_t} \tag{101.9} \]

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\):

\[ \operatorname{Retention}(X) = \big(Q K^\top \odot D\big)\, V, \qquad D_{nm} = \begin{cases} \gamma^{\,n-m} & n \ge m \\ 0 & n \lt m \end{cases} \tag{101.10} \]

\(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}\):

\[ S_n = \gamma\, S_{n-1} + K_n^\top V_n, \qquad \operatorname{Retention}(X_n) = Q_n S_n \tag{101.11} \]

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]

Algorithm 3: chunkwise retention (one head, chunk size c)
  1. input: \(Q, K, V\) of length \(L\), decay \(\gamma\), chunk size \(c\); state \(R \leftarrow 0\)
  2. for each chunk \(i\) with rows \(Q_{[i]}, K_{[i]}, V_{[i]}\):
  3.   inner \(\leftarrow (Q_{[i]} K_{[i]}^\top \odot D_{c\times c})\, V_{[i]}\) // (101.10) inside the chunk, parallel
  4.   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
  5.   output rows of chunk \(i\) \(\leftarrow\) inner + cross
  6.   \(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
  7. 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:

\[ S_t = G_t \odot S_{t-1} + \mathbf{k}_t \mathbf{v}_t^\top, \qquad \mathbf{o}_t = S_t^\top \mathbf{q}_t \tag{101.12} \]

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).

ModelDecay \(G_t\)Depends on the input?Parallel trainingState per layer
Linear attention1 (no decay)noattention form, or cumulative sum\(d_k \times d_v\) per head
RetNet\(\gamma\), one scalar per headnoparallel or chunkwise form\(d_k \times d_v\) per head
RWKV-4\(e^{-w}\), one per channelnosums of (101.8)2 numbers per channel (plus the shifted token)
Mamba (S6)\(\exp(\Delta_t A)\), per channel and stateyesparallel scan in SRAM\(ED \times N\)
Mamba-2 (SSD)\(\exp(\Delta_t a)\), one scalar per headyeschunkwise, 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.

Figure 4. The decay part of (101.6) for 12 tokens: cell \((t, j)\) is how strongly token \(j\) is still present at step \(t\). Darker means larger. Click a cell to read its value. The query–key product (RetNet) or \(e^{k_j}\) (RWKV) multiplies these numbers in the real model.
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:

\[ \mathbf{z}^1 = \mathbf{v}, \qquad \mathbf{z}^{n+1} = \mathbf{x}^n \odot \big(\mathbf{h}^n * \mathbf{z}^n\big) \ \ (n = 1..N), \qquad \mathbf{y} = \mathbf{z}^{N+1} \tag{101.13} \]
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:

\[ h_t = \operatorname{Window}(t) \cdot \operatorname{FFN}\big(\operatorname{PositionalEncoding}(t)\big), \qquad \operatorname{Window}(t) = e^{-\alpha t} \ (\text{plus a bias}) \tag{101.14} \]

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.

fixed state \(S = \sum \mathbf{k}\mathbf{v}^\top\)attention over all keys
Figure 5. Associative recall with random unit keys and values (seeded, so the result is always the same). The curve shows the accuracy of the fixed state for the chosen \(d\) at \(n = 4, 8, 16, 32, 64, 128, 256\); the dot is the chosen \(n\).
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

\[ M(L) = \underbrace{2\, \ell_a\, n_{kv}\, d_h\, b \cdot L}_{\text{KV cache, grows with } L} \;+\; \underbrace{(\ell - \ell_a)\, s\, b}_{\text{recurrent states, fixed}} \tag{101.15} \]
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.

Worked example: KV cache at 256K tokens, 16-bit

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.)

Figure 6. Decode memory from formula (101.15), log scale, 16-bit, weights not included. The hybrid uses Jamba’s shapes (attention: 8 KV heads of 128; Mamba: \(ED = 8192\), \(N = 16\)); with 4 attention layers it is Jamba. The dashed line is one 80 GB GPU.
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

SettingTypical choiceWhy
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 modelsMamba-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 textRWKV (up to 14B in the paper), Griffin / RecurrentGemma [Likely]Fixed state, cost per token independent of the position
On-device and edge generationSmall recurrent or hybrid models [Likely]No KV cache growth, so memory is predictable on a phone
Video classification and action recognitionVideoMamba (Mamba over spatio-temporal patches); Vision Mamba (Vim) for imagesLinear cost in the number of patches, so long, high-resolution clips fit (session 202)
Streaming key-moment detection, live videoRecurrent 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-RAGHybrid: 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 modelingMamba 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
The step size \(\Delta_t\) and the vectors \(B_t, C_t\) are computed from the current token (101.2), so the model can decide per token how much to write into the state and how much to forget. S4 uses the same parameters for every token, so it forgets on a fixed schedule and cannot ignore filler or keep one important token. On selective copying, S4 without gating solves 18.3% and S6 97.0%.
How does \(\Delta\) act like the gate of an RNN?core
With \(N = 1\), \(A = -1\), \(B = 1\), zero-order hold gives \(h_t = e^{-\Delta_t} h_{t-1} + (1 - e^{-\Delta_t}) x_t\). With \(\Delta_t = \operatorname{softplus}(z_t)\), \(1 - e^{-\Delta_t} = \sigma(z_t)\), so this is \(h_t = (1 - g_t) h_{t-1} + g_t x_t\) with \(g_t = \sigma(z_t)\). Large \(\Delta\) resets the state to the current token; small \(\Delta\) keeps the state and ignores the token.
Mamba is a recurrence. How is it trained in parallel?core
The step \(h \mapsto a_t h + b_t\) composes associatively: \((a_1, b_1) \bullet (a_2, b_2) = (a_1 a_2, a_2 b_1 + b_2)\). So a parallel prefix scan computes all \(h_t\) in \(O(\log L)\) depth with \(O(L)\) work (Blelloch). Mamba fuses discretization and scan in one kernel in SRAM, never writes the \(N\)-times-larger state to HBM, and recomputes it in the backward pass. The convolution trick of S4 no longer works because the parameters change over time.
Why does RetNet have three forms? When do you use each?core
All three compute the same retention output. Parallel \((QK^\top \odot D)V\): training on normal lengths, full GPU parallelism, \(O(L^2)\). Recurrent \(S_n = \gamma S_{n-1} + K_n^\top V_n\): decoding, \(O(1)\) per token and fixed memory. Chunkwise: long-sequence training, parallel inside chunks and recurrent across them, linear in \(L\). The decay \(\gamma\) per head (memory about \(1/(1 - \gamma)\) tokens) is what makes the recurrent form possible without a softmax.
Write RWKV’s WKV in recurrent form. What state does a layer keep?core
\(\mathrm{wkv}_t = (a_{t-1} + e^{u + k_t} v_t)/(b_{t-1} + e^{u + k_t})\), with \(a_t = e^{-w} a_{t-1} + e^{k_t} v_t\) and \(b_t = e^{-w} b_{t-1} + e^{k_t}\), per channel. So the state is two numbers per channel for the WKV (plus a running maximum for numerical stability in practice), plus the previous token’s vector for the token shift. It is a decayed, softmax-like weighted average of past values, with a bonus \(u\) for the current token.
Put linear attention, RetNet, RWKV and Mamba in one formula. What is the real difference?advanced
\(S_t = G_t \odot S_{t-1} + \mathbf{k}_t \mathbf{v}_t^\top\), \(\mathbf{o}_t = S_t^\top \mathbf{q}_t\). Linear attention: \(G = 1\). RetNet: \(G = \gamma\), fixed per head. RWKV-4: fixed per channel \(e^{-w}\). Mamba: \(G_t = \exp(\Delta_t A)\), depends on the input. The difference that matters most is whether the decay depends on the input: only then can the model clear its state or hold one token (Figure 4). The unrolled form is masked “attention” with a matrix of decay products, which is the state space duality of Mamba-2.
In what sense is Hyena’s kernel data-dependent? What is its decode cost?advanced
The long filters \(h^n\) come from an FFN over positional encodings times a decaying window, so they depend on position only. The data dependence comes from the gates: \(\mathbf{y} = \operatorname{diag}(\mathbf{x}^N) T_{h^N} \cdots \operatorname{diag}(\mathbf{x}^1) T_{h^1}\mathbf{v}\), so the overall mixing matrix changes with the input. Training uses FFT convolutions at \(O(L \log L)\). Decoding is not constant: each token needs a convolution over all earlier inputs, unless the filters are distilled into a recurrence.
Why are SSMs and linear-attention models weak at copying and exact recall?core
They compress the whole context into a state of fixed size, while exact recall of \(L\) arbitrary items needs memory that grows with \(L\). For a linear state \(\sum \mathbf{k}\mathbf{v}^\top\), reading with one key adds crosstalk from all other keys, so accuracy falls once the number of pairs passes roughly the key dimension (Figure 5). Evidence: Zoology attributes about 82% of the perplexity gap of gated convolutions to associative recall; Repeat After Me shows transformers copy far better; pure Mamba scored 48.8 vs 84.1 for attention on IMDB few-shot in the Jamba study.
Compute the KV cache of Jamba vs Mixtral at 256K tokens. Why does Jamba still keep attention?core
Jamba: 4 attention layers × 8 KV heads × 128 × 2 (K and V) × 2 bytes = 16 KB per token, × 262,144 = 4 GB (plus about 8 MB of Mamba state). Mixtral: 32 layers → 128 KB per token, 32 GB. Jamba keeps 1 attention layer in 8 because pure Mamba lost in-context learning and format following; the hybrid matched or beat pure attention on those tests while keeping most of the memory savings.
Why is Mamba’s decode throughput higher than a transformer’s, if both are memory-bound?advanced
Decode reads the weights once per step for the whole batch, plus per-sequence memory: the KV cache for a transformer, the state for Mamba. The KV cache grows with context and limits the batch size that fits in GPU memory; Mamba’s state is about 12 MB per sequence (2.8B model) regardless of length. Larger batches reuse each weight read for more tokens, raising arithmetic intensity and throughput. The paper reports about 5× higher throughput, mainly from larger batches.
You must serve a 128K-context assistant that cites exact passages. Pure SSM, transformer, or hybrid?advanced
Hybrid, or a transformer with GQA if memory allows. Exact citation is an exact-recall task, where pure SSMs are weak. A hybrid with a few attention layers keeps exact lookup while cutting the KV cache by the ratio of attention layers (8× for Jamba’s 1:7). Check recall with needle-style and multi-key retrieval tests, not only perplexity, and size memory with formula (101.15) at the target batch.

Exercises

  1. A Mamba channel has \(z_t = 0\), so \(\Delta_t = \operatorname{softplus}(0)\). Compute \(\Delta_t\) and the gate \(g_t\) of (101.5).
  2. 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\).
  3. 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?
  4. How many numbers are in the SSM state of one Mamba-2.8B layer? Of the whole model, including the convolution buffers?
  5. Using (101.15), what is the KV cache at 1M (\(2^{20}\)) tokens for Jamba’s shapes, and for Mixtral?
  6. 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\))?
  7. 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
1. \(\Delta = \log 2 = 0.693\); \(g = 1 - e^{-0.693} = 0.5 = \sigma(0)\): half old state, half new token. 2. \((0.5 \times 0.9,\ 0.9 \times 1 + 2) = (0.45, 2.9)\). Step by step: \(h_1 = 1\), \(h_2 = 0.9 \times 1 + 2 = 2.9\). Same. 3. \(1/(1 - \gamma) = 128\) tokens; \(\gamma^{128} = 0.366\), close to \(e^{-1} = 0.368\). 4. \(5120 \times 16 = 81{,}920\) per layer; with \(5120 \times 3 = 15{,}360\) conv numbers, \(64 \times 97{,}280 = 6{,}225{,}920\), about 12 MB in 16-bit. 5. Jamba: 16 KB per token × \(2^{20}\) = 16 GB; Mixtral: 128 KB × \(2^{20}\) = 128 GB. 6. \(L / \log_2 L = 65{,}536/16 = 4{,}096\) times (ignoring constants). 7. With \(d = 32\): 64 pairs give 81%, 128 pairs give 50%. The state has \(32 \times 32 = 1{,}024\) numbers, but it reliably holds only about \(d\) to \(2d\) pairs (each pair is 64 numbers), so a fixed state is far less efficient than a cache for exact lookup.

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

\[ \bar A_t = e^{\Delta_t A},\ \ \mathbf{h}_t = \bar A_t \odot \mathbf{h}_{t-1} + \Delta_t B_t x_t,\ \ (a_1, b_1)\bullet(a_2, b_2) = (a_1 a_2, a_2 b_1 + b_2) \]
\[ S_t = G_t \odot S_{t-1} + \mathbf{k}_t \mathbf{v}_t^\top,\ \ \operatorname{Retention}(X) = (QK^\top \odot D)V,\ \ M(L) = 2\ell_a n_{kv} d_h b L + (\ell - \ell_a) s b \]

References for this session

  1. Gu & Dao (2023). Mamba: Linear-Time Sequence Modeling with Selective State Spaces
  2. Peng et al. (2023). RWKV: Reinventing RNNs for the Transformer Era
  3. Sun et al. (2023). Retentive Network: A Successor to Transformer for Large Language Models
  4. Poli et al. (2023). Hyena Hierarchy: Towards Larger Convolutional Language Models
  5. Fu et al. (2022). Hungry Hungry Hippos: Towards Language Modeling with State Space Models
  6. Lieber et al. (2024). Jamba: A Hybrid Transformer-Mamba Language Model
  7. Gu & Dao (2023). Mamba: Linear-Time Sequence Modeling with Selective State Spaces
  8. Peng et al. (2023). RWKV: Reinventing RNNs for the Transformer Era
  9. Sun et al. (2023). Retentive Network: A Successor to Transformer for Large Language Models
  10. Poli et al. (2023). Hyena Hierarchy: Towards Larger Convolutional Language Models
  11. Fu et al. (2022). Hungry Hungry Hippos: Towards Language Modeling with State Space Models
  12. Lieber et al. (2024). Jamba: A Hybrid Transformer-Mamba Language Model
  13. Gu et al. (2021). Efficiently Modeling Long Sequences with Structured State Spaces
  14. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  15. Dao & Gu (2024). Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality
  16. Arora et al. (2023). Zoology: Measuring and Improving Recall in Efficient Language Models
  17. Jelassi et al. (2024). Repeat After Me: Transformers are Better than State Space Models at Copying
  18. De et al. (2024). Griffin: Mixing Gated Linear Recurrences with Local Attention for Efficient Language Models
  19. Li et al. (2024). VideoMamba: State Space Model for Efficient Video Understanding
  20. Zhu et al. (2024). Vision Mamba: Efficient Visual Representation Learning with Bidirectional State Space Model