State Space Models (S4 & Mamba)
RNNs process sequences step by step but can't be parallelized over time (and forget long contexts); transformers parallelize beautifully but cost in sequence length. State space models (SSMs) — the S4 and Mamba family — aim for the best of both: a recurrent model with long memory that nevertheless trains in parallel, at sub-quadratic cost. They're the most serious recent challenger to attention for long-sequence modeling.
Real-world examples: long-document and genomics modeling (S4 on million-length sequences), Mamba and hybrid Mamba-transformer language models, and efficient on-device sequence models where the attention bill is prohibitive.
The linear recurrence
An SSM maps an input sequence to an output through a hidden state , with a linear recurrence:
This looks like an RNN, but the transition is linear (no nonlinearity inside the recurrence). controls how the state evolves and remembers; writes the input into the state; reads the output out. The recurrent unrolling is the same picture as an RNN:
RNN unrolled over 5 timesteps
The same weight matrix $W_h$ connects every hidden state to the next — this is weight sharing. Step through the sequence to see the hidden state evolve, carrying context forward.
The key trick: recurrence ⟺ convolution
Because the recurrence is linear, you can unroll it in closed form. Substituting repeatedly, is a convolution of the entire input history with a fixed kernel:
This duality is the whole point:
- Training: compute the kernel once, then apply it as a single (FFT-based) convolution over the whole sequence in parallel — no step-by-step loop, like a CNN.
- Inference: roll the recurrence forward one step at a time with an state update per token — like an RNN, with no growing KV-cache.
One model, two modes
A linear SSM is the same computation expressed two ways: a parallel convolution for fast training, and a constant-memory recurrence for fast autoregressive generation. Attention can't do the convolution-mode parallel training and O(1) per-token inference — it pays O(L) per token from the growing KV-cache.
S4: making it actually work
A naive linear recurrence forgets quickly ( shrinks) or blows up. S4 (Structured State Space) makes long memory practical with a special structured initialization of (the HiPPO matrix), designed so the state optimally compresses the input history — letting S4 capture dependencies over tens of thousands of steps where LSTMs and even transformers struggle. The "structured" also keeps the math efficient.
Mamba: selectivity
S4's are fixed — the same for every token (it's a Linear Time-Invariant system). That's what allows the convolution view, but it means the model can't choose what to remember based on content, the way attention can. Mamba adds selectivity: it makes (and the timestep) functions of the input, so the model dynamically decides what to keep and what to ignore per token.
Selectivity breaks the convolution — so Mamba uses a parallel scan
Once depend on the input, the system is time-varying and the fixed-kernel convolution no longer applies. Mamba recovers parallel training with a hardware-aware parallel scan (an associative scan over the linear recurrence) that runs efficiently on GPUs. It keeps the scaling while regaining content-based selection.
SSM vs. attention
| Attention | SSM (S4 / Mamba) | |
|---|---|---|
| Cost in length | (or ) | |
| Training | parallel | parallel (convolution / scan) |
| Inference / token | (KV-cache grows) | (fixed-size state) |
| Memory of full context | exact (attends to all) | compressed into the state |
| Content-based selection | yes (native) | S4 no; Mamba yes |
The trade-off: attention keeps an exact record of every token (and can look any of them up), while an SSM compresses history into a fixed-size state — cheaper, but lossy. Mamba narrows the quality gap enough that hybrid models (mostly SSM layers with a few attention layers) are an active, promising direction.
Exercise
A state space model uses the recurrence h_t = A·h_{t-1} + B·u_t, y_t = C·h_t. What single property distinguishes it from a vanilla RNN, and why does it matter?
Need a hint?
Is there a nonlinearity inside the recurrence?
Exercise
S4-style SSMs are described as 'recurrent for inference, convolutional for training.' What does this duality buy you?
Need a hint?
Which mode is parallel, and which is O(1) per token?
Exercise
Mamba adds 'selectivity' to S4 by making the B and C matrices depend on the input. What does this gain, and what does it cost?
Need a hint?
Content-based selection — but is the system still time-invariant?
Common mistakes
- Calling an SSM "just an RNN." The recurrence is linear, which is exactly what unlocks parallel (convolutional/scan) training that RNNs lack.
- Expecting S4 to do content-based selection. S4 is time-invariant (fixed ); that capability is Mamba's selectivity.
- Assuming SSMs store the full context like attention. They compress it into a fixed-size state — efficient but lossy, the core quality trade-off.
- Thinking SSMs make attention obsolete. They excel at long sequences and cheap inference, but hybrids (and attention) remain strong; it's a trade-off, not a strict replacement.
Key takeaways
- An SSM is a linear recurrence — recurrent like an RNN but linear.
- Linearity gives a recurrence ⟺ convolution duality: train as a parallel convolution, generate as an -per-token recurrence.
- S4 uses structured (HiPPO) initialization for very long memory; Mamba adds input-dependent selectivity, recovered in parallel via a hardware-aware scan.
- Versus attention, SSMs are sub-quadratic with inference but compress context (lossy); hybrids combine both.
Related concepts
- Recurrent Neural Networks: the recurrent computation SSMs make linear and parallelizable
- BPTT & Vanishing Gradient: the long-memory problem S4's structured state addresses
- Modern Attention: the mechanism SSMs offer a sub-quadratic alternative to