State-Space Models (Mamba)

TL;DR. A state-space model (SSM) processes a sequence by carrying a small fixed-size "memory" vector forward one step at a time, like an RNN — but with the math chosen so it can also be computed in parallel like a CNN/Transformer during training. S4 (2021) made this work for long sequences. Mamba (2023) added selectivity — letting the model decide, per-token, what to remember and what to forget — and a GPU-friendly selective scan to keep it fast. The payoff: linear time in sequence length (vs. the Transformer's quadratic), and a constant-size state at inference (no growing KV-cache). The catch: that fixed-size state caps how much it can precisely recall, so the field has largely converged on hybrids (Mamba + a few attention layers) rather than a clean "Transformer killer."

What it is (intuition first)

Imagine reading a book one word at a time while only allowed to keep a single index card of notes. After each word you update the card, then throw the word away. To answer a question at the end, you can only look at the card — never re-read the book. That index card is the state h, and the rule for updating it after each word is a state-space model.

Compare the two dominant ways to model sequences:

• A Transformer keeps every past word around and, for each new word, looks back over all of them via attention. Perfect recall, but the work grows like O(L²) in sequence length L, and at generation time it stores a KV-cache that grows with every token. ([[attention-and-transformers]])
• An RNN keeps only a fixed-size hidden state — O(L) work, constant memory — but classic RNNs (LSTM/GRU) were hard to train on long sequences and couldn't be parallelized over time.

SSMs are the modern attempt to get the best of both: an RNN's constant inference memory and linear time, with a CNN/Transformer's parallel-over-time training. The trick is that, if you keep the update rule linear, the same model has two mathematically identical faces — a slow sequential recurrence (great for inference) and a parallelizable form (great for training).

This article builds up: continuous SSM → discretization → S4's structured A → Mamba's selection → Mamba-2's duality with attention → honest limits → hybrids.

Why it matters

1. Long context is expensive under attention. Quadratic cost and a linearly-growing KV-cache are the practical wall for 100k–1M-token contexts. SSMs scale linearly and keep a constant-size state — Mamba reports up to 5× higher generation throughput than a same-size Transformer and improving quality on real data "up to million-length sequences" (Gu & Dao, 2312.00752↗).
2. It reopened the architecture question. From ~2017 to ~2022 "attention is all you need" was nearly unchallenged. S4 winning the Long Range Arena — including the 16k-length Path-X task that every prior model failed (Gu et al., 2111.00396↗) — proved a non-attention primitive could beat Transformers at long-range modeling.
3. It's modality-general. The same selective-SSM core hit state-of-the-art on language, audio, and genomics (Mamba), and SSM variants have spread to vision, time-series, and RL.
4. It changed deployed models, not just papers. Hybrids like Jamba (52B params, 256k context, SSM+attention+MoE) shipped to production, and the Mamba-2 / State Space Duality result mathematically unified SSMs with attention — making this a foundational idea, not a fad.

How it works (the real mechanics)

1. The continuous state-space model

SSMs come from control theory. A continuous linear system maps an input signal x(t) to an output y(t) through a hidden state h(t):

h'(t) = A·h(t) + B·x(t)      (state evolves)
y(t)  = C·h(t)               (read out the state)

(Some formulations add + D·x(t), a skip connection, to the output.) Here h ∈ ℝ^N is the state (the "index card", size N), A ∈ ℝ^{N×N} governs how the state decays/mixes over time, B injects the input, and C projects the state to the output. The whole game is choosing A so the state remembers the right things.

2. Discretization (continuous → discrete steps)

Text isn't continuous; it arrives token by token. We discretize with a step size `Δ` (think: how much "time" passes per token) using the zero-order hold (ZOH) rule:

Ā = exp(Δ·A)
B̄ = (Δ·A)^{-1} · (exp(Δ·A) − I) · Δ·B

(cross-checked against the visual guide↗). This turns the ODE into a clean discrete recurrence:

h_t = Ā·h_{t-1} + B̄·x_t       (RNN-like update)
y_t = C·h_t

Intuitively Δ is a resolution / forget knob: large Δ weights the current token heavily and forgets faster; small Δ lets state persist (the model "stays still"). This single recurrence is the inference-time view: O(1) work and O(N) memory per token, forever.

3. The convolutional view (why training is parallel)

Because the recurrence is linear and time-invariant (in S4, Ā, B̄, C don't depend on the token), you can unroll it. The output is a convolution of the input with a fixed kernel:

K̄ = (C·B̄,  C·Ā·B̄,  C·Ā²·B̄,  …,  C·Ā^{L-1}·B̄)
y  = x * K̄

So an SSM has a dual identity: a recurrence (cheap, sequential — use at inference) and a convolution (parallel over the whole sequence — use at training). Same math, two algorithms. This is the structural reason SSMs can train fast like CNNs/Transformers yet generate cheaply like RNNs. ([[attention-and-transformers]] gets parallel training too, but pays O(L²); the SSM convolution is the secret to getting it without attention.)

4. S4: making A actually work for long range (HiPPO + structure)

A naive A either forgets too fast (vanishing memory) or is too expensive (a dense N×N matrix powered L times). S4 fixed both:

• HiPPO initialization. Initialize A from HiPPO (High-order Polynomial Projection Operators), which derives a specific A that makes the state optimally compress the history of the signal onto Legendre-polynomial coefficients. This is why S4 handles long-range dependencies: the state is mathematically built to retain a decaying summary of everything seen so far, instead of relying on luck or gradient flow (2111.00396↗).
• Structured `A` (DPLR). Computing the kernel K̄ with a dense A is prohibitive. S4 parameterizes A as diagonal-plus-low-rank, which can be stably diagonalized, reducing kernel computation to a well-studied Cauchy kernel. Later work (S4D, DSS) showed a purely diagonal `A` is nearly as good and much simpler — the parameterization Mamba inherits.

5. Mamba: the selection mechanism

S4's strength — being linear and time-invariant, hence convolution-able — is also its weakness: the same kernel is applied to every token regardless of content. It can't say "this token is important, remember it" or "this is filler, skip it." That's content-blind. Transformers are content-aware (attention weights depend on the tokens).

Mamba's core idea: make the SSM parameters functions of the input. Specifically B, C, and Δ become input-dependent — computed by linear projections of the current token x_t (2312.00752↗):

B_t, C_t, Δ_t  = Linear_B(x_t), Linear_C(x_t), softplus(Linear_Δ(x_t))

Now the model can selectively propagate or forget information per token — content-based reasoning, the thing pure SSMs lacked. Δ_t acts as a learned, per-token gate: it controls how much the current token updates the state vs. how much the past persists (closely related to the forget/input gates of an LSTM, but derived from the SSM discretization).

The cost of selection. The moment B, C, Δ depend on the input, the system is no longer time-invariant — the kernel K̄ is different at every position, so the convolution view (§3) collapses. You can't precompute one kernel anymore. Without a fix, you're back to a slow sequential RNN with no parallel training.

6. The selective scan (hardware-aware parallel algorithm)

Mamba recovers parallel training with a selective scan built on a classic trick: the linear recurrence h_t = Ā_t·h_{t-1} + B̄_t·x_t is an associative operation, so it can be computed by a parallel prefix scan (Blelloch scan) in O(log L) depth instead of O(L) sequential steps. Crucially, Mamba's scan is hardware-aware ("kernel fusion"): it keeps the large expanded state in fast GPU SRAM rather than materializing it in slow HBM, and recomputes intermediates in the backward pass instead of storing them — analogous in spirit to [[flash-attention]]. Result: input-dependent selectivity and linear-time, parallel training.

The full Mamba block wraps this selective SSM with input/output projections, a depthwise causal conv, and a gated (SiLU) branch — and notably drops attention and even the MLP block, stacking these homogeneous blocks instead.

7. Mamba-2 and State Space Duality (SSD)

The follow-up, Mamba-2 (Dao & Gu, 2405.21060↗), proved something deep: a structured SSM (with a scalar-times-identity A per step) is mathematically equivalent to masked attention with a special "1-semiseparable" causal mask. The bridge is the theory of structured semiseparable matrices — the same sequence transform can be realized as either a linear-time recurrence or a quadratic-time attention-like matmul.

This State Space Duality (SSD) is both theory and engineering:

• Theory: "Transformers are SSMs" — attention and SSMs are two decompositions of one matrix-mixing operation, unifying two camps that looked unrelated. (Conceptually adjacent to linear attention — see [[flash-attention]] and [[attention-and-transformers]].)
• Practice: the matmul form lets Mamba-2 exploit GPU tensor cores (built for matmuls), giving 2–8× faster training than Mamba-1 while staying competitive with Transformers — with a larger state size to boot.

Key ideas & tradeoffs

The central tradeoff in one line: a fixed-size state is what makes SSMs cheap (constant memory) and is exactly what limits them (you cannot losslessly compress an arbitrarily long history into N numbers). Attention's growing KV-cache is the price of perfect recall; the SSM's bounded state is the price of efficiency. Everything else flows from this.

Honest caveats & open questions

• Recall / copying is a real, theoretical weakness. SSMs with a fixed state have fundamentally limited copying capacity. They struggle on multi-query associative recall (MQAR) and exact-copy tasks where Transformers trivially succeed — and this is provably tied to state size, not just an optimization artifact ("Can Mamba Always Enjoy the Free Lunch?", 2410.03810↗). For retrieval-heavy, in-context-learning, and long-CoT tasks, attention still has an edge. Mitigations (mimetic init, reward-driven objectives) help but don't erase the gap.
• "Transformer killer" was overhyped. The honest 2026 consensus: SSMs did not replace attention. They became a complementary primitive. Most strong long-context models are hybrids.
• Hybrids won in practice. Jamba (AI21, 2403.19887↗) interleaves Mamba + a few attention layers + MoE — 52B total / ~12B active, 256k context — and is the first production-grade SSM-attention hybrid past 7B/250B-tokens. The recurring finding: a small number of attention layers restores the recall the SSM lacks, while the SSM majority handles long-range cheaply. Lieber et al. frame the future as "sophisticated hybridization," not a single killer architecture. (Related composition ideas: [[mixture-of-experts]], [[deepseek-architecture]].)
• Tooling & ecosystem maturity. Attention has years of kernels, quantization recipes, serving stacks, and interpretability tools. SSM tooling is younger; quantization and serving for the recurrent state are less battle-tested ([[quantization]]).
• Interpretability. Attention maps give a (debatable but usable) lens on what the model attends to. The compressed SSM state is harder to introspect — what's in that fixed-size vector is opaque.
• Open questions. Optimal hybrid ratio (how many attention layers, and where)? Best state size vs. recall tradeoff per task? Do SSMs need attention at all if state is large enough, or is some explicit retrieval always necessary? How well does selectivity scale to 100B+ params? These are unsettled.

How it connects to OpenAlice

Be skeptical: OpenAlice's core models are Transformer LLMs accessed via providers (Codex/GPT-class), so SSMs are not currently in the serving path. The honest ties are conceptual and forward-looking:

• Long-context memory. Alice's [[agent-memory-systems]], [[mempalace]], and [[graphrag]] exist because attention's context window and KV-cache are bounded and costly. SSMs attack the same problem at the architecture level — a constant-size, linear-time recurrent state is conceptually the same "compress history into a bounded working memory" move that Alice's memory layer does at the application level. The SSM state-size ↔ recall tradeoff is a clean mental model for why a memory system needs explicit retrieval (the "attention" half) on top of a compressed running summary (the "SSM" half).
• The hybrid lesson generalizes. "SSM bulk + a little attention for recall" rhymes with OpenAlice's own composition patterns — [[model-routing]], [[mixture-of-agents]], [[fusion-and-llm-councils]] — where cheap broad coverage is paired with a small amount of expensive precise work. The architecture-level result is evidence that heterogeneous primitives chosen for their strengths beats one monolith.
• Learning resource, not a dependency. For the OpenAlice Academy, this is a foundational "what's after the Transformer?" topic. It pairs naturally with [[attention-and-transformers]], [[flash-attention]], and [[scaling-laws]]. If OpenAlice ever needs ultra-long-context streaming on commodity (no-GPU-at-inference-friendly) hardware, a Mamba-style hybrid is the architecture to evaluate — but today that's a watch-this-space, not a plan.

See also

[[attention-and-transformers]] · [[flash-attention]] · [[mixture-of-experts]] · [[deepseek-architecture]] · [[scaling-laws]] · [[agent-memory-systems]] · [[graphrag]] · [[mempalace]] · [[model-routing]] · [[mixture-of-agents]] · [[positional-encoding]] · [[test-time-compute-reasoning]]

References

1. Gu & Dao (2023), Mamba: Linear-Time Sequence Modeling with Selective State Spaces — arXiv:2312.00752↗
2. Gu, Goel & Ré (2021), Efficiently Modeling Long Sequences with Structured State Spaces (S4) — arXiv:2111.00396↗
3. Dao & Gu (2024), Transformers are SSMs: ... Structured State Space Duality (Mamba-2) — arXiv:2405.21060↗
4. Lieber et al. (2024), Jamba: A Hybrid Transformer-Mamba Language Model — arXiv:2403.19887↗
5. Can Mamba Always Enjoy the "Free Lunch"? (2024) — arXiv:2410.03810↗
6. Grootendorst, A Visual Guide to Mamba and State Space Models — newsletter↗