knowledge base · entry 13
Sequence modeling without the quadratic bill
A read-through of the paper that dropped attention altogether — trading its quadratic cost for a compact running state, and matching the Transformer anyway.
every figure zooms — click it, scroll to magnify, drag to pan
part one
The idea, before any jargon
figure 1 · the whole idea
Two ways to remember a sequence
A Transformer remembers by re-reading. To produce each new token, attention looks back at every token before it — and to do that, it keeps them all around. That's powerful, and it's why Transformers work; it's also why they get expensive as sequences grow.
Mamba remembers differently. It keeps a single, fixed-size state — a running summary of everything seen so far — and each new token just updates it. The past is never re-read; it's compressed into that state. One glance per token, not a look back at all of them.
click any figure to zoom · scroll to magnify · drag to pan
This is the boldest move yet: where DeepSeek-R1 changed the training signal, Mamba changes the architecture underneath everything — the first serious challenge to attention's dominance since the Transformer arrived.
figure 2 · the cost
Attention hits a quadratic wall
The reason the difference matters is arithmetic. Because attention compares every token with every other, its cost grows with the square of the sequence length, and its memory grows linearly as the cache of past tokens piles up. Double the length and the work quadruples.
Mamba's cost grows only linearly, and its state is a fixed size that never grows at all, no matter how long the input. For a paragraph the gap is small; for a book, a genome, or a year of filings, it's the difference between feasible and not.
part two · the mechanism
The compact state, and the one new idea
figure 3 · state space models
A state space model: the past, compressed
Underneath, Mamba is a state space model — an old idea from control theory. The state h is a small fixed-size vector; each step folds in one new input and carries the state forward. Read the output off the state. Linear in length, constant in memory.
The neat trick is that this same computation has two faces. As a step-by-step recurrence it's ideal for generation — constant work per token. Unrolled, it becomes a convolution that trains in parallel across the whole sequence at once. You get the RNN's cheap inference and the Transformer's parallel training from one object.
figure 4 · selection
The one idea: let the model choose
Earlier state space models had a fatal weakness against attention: their update rules were fixed, so they compressed every token the same way and couldn't focus on what mattered. Attention could zero in on a relevant token; they couldn't.
Mamba's contribution is a single change: make the update depend on the input. Now the model decides, token by token, what to write into the state and what to ignore — content-based selection, at linear cost. The price is that a selective scan is no longer a plain convolution, so it needs a custom, hardware-aware parallel kernel — a good chunk of the paper's engineering.
part three · the result
Does giving up attention cost anything?
figure 5 · the result
Linear — and it keeps up
The surprise is the answer to that question: no. At equal size, Mamba matches or beats a Transformer's language-modelling quality — and a smaller Mamba can rival a Transformer twice its size.
All of that while generating several times faster and scaling to sequences of a million tokens, where attention simply runs out of memory. The lesson that made people look up: all-to-all attention, long assumed essential, turned out to be one option rather than the only one.
the math · in the paper's notation
The recurrence, and the selection
The paper's equations (1)–(4) define the state space model; its Algorithm 2 makes three of the constants input-dependent. Both decoded here — after this, the notation wall in section 2 of the PDF is review.
the equations · worked
Four small equations, one crucial edit
§2, eqs. (1)–(2) · the state space model, continuous and discrete
continuous: h′(t) = A h(t) + B x(t), y(t) = C h(t)
discrete: ht = Ā ht−1 + B̄ xt, yt = C ht, Ā = exp(ΔA)
read aloud: the state decays a little (A), absorbs a little of the new input (B), and the output is read off the state (C). The discrete line is the same statement per token: bar means "discretized", and the step size Δ controls how much each token counts. That one recurrence is the whole memory — no cache of past tokens anywhere.
- htthe state: a small fixed-size vector (N ≈ 16 per channel) — the compressed past
- A, Āthe decay: how the old state carries forward — exp(ΔA) is the paper's zero-order-hold discretization
- B, B̄the write: how much of token xt enters the state
- Cthe read: how the output is extracted from the state
- Δthe step size — the "how long to dwell on this token" dial, about to become the star
§3.2, algorithm 2 · selection — the paper's one new idea
Bt = LinearB(xt), Ct = LinearC(xt), Δt = softplus( LinearΔ(xt) )
read aloud: make the write, the read, and the step size functions of the current token. Older SSMs kept B, C, Δ fixed, so every token was compressed identically — that was their fatal weakness. Subscript t is the entire edit: now Δt → large means "dwell — reset toward this token, write it firmly"; Δt → 0 means "skip — let it pass untouched". Content-based focus, at linear cost.
- Linear(·)a learned linear projection of the token — cheap, per-token
- softpluslog(1+ex) — a smooth "make it positive", since a step size can't be negative
part four · what we take from it
When a specialist reads long
applied · our reading
Built for long documents
For a domain specialist, the deciding factor is input length. A tax or legal assistant often has to read a full contract, a year of filings, or a several-hundred-page ruling. There, linear time and constant memory aren't a nicety — they're what makes reading the whole thing at once affordable at all.
the caveat we would flag Attention still owns the ecosystem — tooling, kernels, fine-tuning recipes are all built around it — and Mamba's selective scan needs custom kernels to run well. On short inputs the advantage is small, and in practice hybrids that keep a few attention layers alongside SSM ones often win. This is a serious new option, not a settled replacement.
the arc continues
The curriculum's core, complete
The curriculum's core in four movements: routing to spend inference wisely, making models smaller, the data & scaling laws that size a training run, and the frontiers that question the recipe itself. Each was read the same way — plain idea first, then the construction, then the one bit of arithmetic — and each ends where it actually lands for us: a sovereign, domain-specific system you can own and afford to run. And the frontier keeps moving: entry 20, HOPE, takes aim at the wall between training and inference itself.
← back to the knowledge base — the full index, searchable by tag.
source
Albert Gu, Tri Dao — CMU / Princeton (2023). Mamba: Linear-Time Sequence Modeling with Selective State Spaces. arXiv:2312.00752. The linear/quadratic scaling and the ~5x throughput are the paper's; the state diagram, the selection sketch, and the toy sequence are our own illustration.
← back to the knowledge base · ⚙ the illustrated decoder · ▶ run the forward pass
attention.sh — a division of Jinacode Systems. Transformers,
fine-tuning, and sovereign LLMs.
we're hiring the curious — hello@attention.sh