How do state-space models like Mamba differ from attention, and when would you use one?
A state-space model carries a fixed-size hidden state forward through the sequence like a selective recurrence, giving O(N) time and constant per-step memory with no KV cache that grows with context. Attention instead compares every token to every other, which is O(N^2) but allows exact lookup of any past token. Mamba's gates are input-dependent, recovering much of attention's content-awareness; the trade-off is that a fixed state can't recall arbitrary far-back tokens as precisely. In practice, hybrids that interleave Mamba layers with a few attention layers give near-linear cost with near-attention quality.
How to think about it
The two mix sequence information in fundamentally different ways.
Attention compares every query to every key — O(N²) compute and, at inference, a KV cache that grows linearly with context. Its superpower is exact lookup: any token can directly retrieve any other, however far back.
State-space models (Mamba) treat the sequence as a selective linear recurrence: a fixed-size hidden state is carried forward and updated with input-dependent gates that decide what to keep or forget.
| Attention | SSM (Mamba) | |
|---|---|---|
| Time | O(N²) | O(N) |
| Inference memory | KV cache grows with N | fixed-size state |
| Long-range recall | exact lookup | compressed into state |
When to reach for an SSM: streaming or very long sequences where throughput and constant memory matter more than perfect recall — the absence of a growing KV cache is a major serving win.