State space models and Mamba

State space models (SSMs), like RNNs, carry a state forward through the sequence. That gives a completely different cost profile from attention:

	Attention	SSM
Training	O(T²), parallel	O(T log T) or O(T), parallel through a scan
Generation per token	O(T) with a KV cache	O(1) — constant
Memory at generation	grows with T	constant
Exact recall of an arbitrary detail	yes	limited by the size of the state

The last row is the decisive trade-off: attention can go back and look at any token at all; an SSM has to have saved it in its state.

Mamba's contribution (Gu & Dao 2023) is selectivity: the SSM parameters are made dependent on the input, so the model can choose what goes into the state and what is forgotten. Earlier SSMs (S4) had fixed parameters and could not do content-based selection — which was exactly what was missing for language. The price is that the efficient convolutional form disappears, which is solved with a hardware-aware parallel scan.

What the evaluations actually show: pure SSMs match transformers on many language tasks at a comparable scale, but perform worse on tasks requiring exact copying or lookup in the context (induction tasks, «needle in a haystack»). Jelassi et al. (2024) showed this theoretically and empirically: a constant state means an information-theoretic limit on how much can be recalled.

That is why hybrid architectures are the standard in practice — Jamba, Zamba and the like mix a few attention layers in among many Mamba layers. A handful of attention layers is enough to restore the lookup ability, while the bulk of the cost becomes linear.

How to read such claims critically: «matches transformers» holds on which tasks, at which scale, with what tuning of the baseline? Check particularly whether the evaluation contains tasks requiring exact recall — that is where the difference shows, and that is why they are sometimes left out.

A linear SSM in continuous time: $h'(t) = A h(t) + B x(t), \qquad y(t) = C h(t) + D x(t)$

Discretised with a step length $\Delta$ it becomes a recurrence: $h_t = \bar A h_{t-1} + \bar B x_t, \qquad y_t = C h_t$

Since the recurrence is linear in $h$ the whole sequence can be computed with an associative scan at $O(\log T)$ depth — unlike a non-linear RNN, which has to be run sequentially. That is what makes SSMs trainable at scale.

In S4 $\bar A$ is structured (HiPPO initialisation) and the parameters are independent of the input, which gives a global convolution. In Mamba $\bar B$, $C$ and $\Delta$ are made functions of $x_t$ — selectivity — which breaks the convolutional form but keeps the scan parallelisation.