II · THE IDEA · ARTIFICIAL INTELLIGENCE
Alternatives to Attention
▶ Listen · narrated
A transformer reading a million-token document must compare each new token against all the tokens before it. The cost scales with the square of the length, and that square eventually wins.
At a glance
- Attention cost
- Quadratic in sequence length — O(n²) memory and compute
- State-space cost
- Linear in sequence length — O(n) for the same operations
- Core mechanism
- Compress history into a fixed-size hidden state, updated recurrently
- Mamba innovation
- Input-dependent state transition, allowing selective attention to history
Imagine you are reading a very long book and taking notes. A transformer's method is to keep the entire book open in front of you, so you can flip back to any page whenever you need to check a detail. This is powerful but expensive: the bigger the book, the more desk space you need, and looking things up takes longer because there are more pages to search through. The cost grows with the square of the book's length.
A state-space model like Mamba takes a different approach. Instead of keeping the whole book open, you maintain a summary that you update as you read each new page. The summary is a fixed size — say, one notebook page — and you continuously revise it to reflect what seems important. When you need to answer a question, you consult the summary, not the original book. This is much cheaper: the cost grows linearly with the book's length, because you only process each page once. The trade-off is that your summary might not contain every detail. If you decided fifty pages ago that a character's middle name was unimportant, you may have overwritten it, and now it is gone. Mamba's innovation is that the summary is adaptive: what you choose to remember depends on what you are currently reading, not on a fixed rule. But it is still a summary, not the full text.
A transformer layer computes attention by taking the dot product of each query vector with every key vector in the sequence, applying a softmax, and using the resulting weights to form a weighted sum of value vectors. For a sequence of length n, this requires O(n²) operations and O(n²) memory to store the attention matrix. This quadratic cost is the dominant term for long sequences.
A state-space model avoids this by maintaining a hidden state h(t) that evolves recurrently: h(t) = A h(t-1) + B x(t), where x(t) is the input at step t. The output is y(t) = C h(t). The matrices A, B, C define the dynamics. For a sequence of length n, this requires O(n) operations because each step is computed in constant time. The entire history is compressed into h(t), which has fixed dimensionality regardless of sequence length.
Structured state-space models, such as S4, use specific initialisations of A (often diagonal or low-rank) that allow efficient computation and preserve long-range dependencies better than naive recurrence. The key constraint is that A, B, C are input-independent: the same dynamics apply to every token.
Mamba introduces selectivity by making B and C functions of the input: B(t) = B(x(t)), C(t) = C(x(t)). The state transition is now h(t) = A h(t-1) + B(x(t)) x(t), and the output is y(t) = C(x(t)) h(t). This allows the model to modulate which parts of the input are written into the state and which parts of the state are read out, conditioned on the current token. The cost remains O(n), but the model gains a form of content-based gating similar to the forget and output gates in an LSTM.
The trade-off is fundamental: a transformer can attend to any earlier token with equal ease, because the full sequence is available. A state-space model can only access information that survived compression into h(t). If a fact from early in the sequence was not preserved by the selective transitions at each intervening step, it is not recoverable. The fixed-size state is a bottleneck. Whether Mamba's selectivity is sufficient to approximate the expressiveness of full attention is an empirical question, and current results are mixed.
Look closer
The quadratic wall is real
In a transformer, every token attends to every earlier token in the sequence. A 1,000-token sequence requires roughly a million comparisons; a 10,000-token sequence requires a hundred million. Memory and compute both grow with the square of the length. This is why context windows, despite growing steadily, remain capped in the tens or low hundreds of thousands of tokens. The cost becomes prohibitive before the window becomes infinite, and tricks like sparse attention or sliding windows trade coverage for speed.
State-space models keep a summary, not the full tape
A state-space model maintains a fixed-size hidden state vector that is updated as each token arrives. The new token and the old state together produce the next state, and the output depends only on the current state — not on re-examining the entire history. This is a recurrent structure, closer in spirit to an LSTM than to a transformer. The cost per token is constant, so total cost scales linearly with sequence length. The catch is that everything the model needs to remember must fit into that fixed-size state, and early information can be overwritten or diluted as new tokens arrive.
Mamba makes the state transition selective
Earlier structured state-space models used fixed, input-independent transition rules: the same linear transformation applied regardless of what token arrived. Mamba introduced input-dependent transitions, where the parameters that update the state depend on the content of the current token. This allows the model to decide, in effect, which parts of history to preserve and which to let fade. The authors describe this as selective attention, though it remains a compression into a fixed state rather than the full random access that transformer attention provides. Whether this selectivity closes the quality gap is an open empirical question.
The story
Transformers won the architecture wars of the late 2010s in part because attention let them look anywhere in the input without the forgetting problems that plagued recurrent networks. But that victory came with a price: the cost of attention grows with the square of the sequence length. Double the length and you quadruple the memory and compute. This was tolerable when sequences were a few hundred tokens, but as context windows stretched into tens of thousands, the quadratic term became the dominant cost.
State-space models offer a different bargain. Instead of maintaining the full sequence and comparing each new token against all earlier ones, they compress history into a fixed-size hidden state. Each new token updates this state, and the output depends only on the current state, not on re-reading the past. The cost per step is constant, so total cost scales linearly with sequence length. This is the same recurrent structure that transformers were meant to have superseded.
The difficulty has always been what to keep and what to discard. Early recurrent networks forgot too readily; important information from many steps back would fade before it was needed. Structured state-space models, introduced by Gu and others in the early 2020s, applied ideas from control theory to make the forgetting more principled. They modelled the hidden state as evolving according to a linear dynamical system, with carefully initialised parameters that let certain frequencies of information persist longer than others. This worked surprisingly well on tasks involving long-range dependencies, but the state transitions were fixed: the same linear transformation applied to every token, regardless of content.
Mamba, published in late 2023, made the transitions input-dependent. The parameters governing how the state updates now vary with the token being processed. In effect, the model can choose what to remember and what to let go, conditioned on what it is currently reading. The authors call this selective state-space modelling. It is not attention in the transformer sense — the model still cannot look back at arbitrary earlier tokens — but it is no longer blind recurrence either. The state becomes a learned, adaptive summary rather than a passive accumulation.
The empirical results are promising but not yet definitive. Mamba matches transformer performance on some benchmarks while using far less memory on long sequences, but other tasks still favour attention. The architecture is young, and the training recipes are less mature than those for transformers. It is also unclear whether the fixed-size state, however cleverly updated, can truly substitute for the full random access that attention provides. Transformers can, in principle, retrieve a single fact from 50,000 tokens ago without that fact having survived a long chain of lossy updates. Whether Mamba's selective compression is sufficient for all the things we ask of models remains an open question.
Why it mattered then
The immediate motivation was practical: the quadratic cost of attention had become the bottleneck for processing long documents, genomic sequences, audio waveforms and other data where length matters. Sparse attention and other approximations helped, but they sacrificed the completeness that made transformers powerful in the first place. State-space models promised linear scaling without abandoning the idea of long-range reasoning. The structured state-space work from 2021 and 2022 showed that recurrence could be competitive again if the dynamics were designed carefully, and Mamba extended that line by making the dynamics adaptive. It arrived at a moment when the costs of scaling transformers to longer contexts were becoming prohibitive even for well-resourced labs, and alternative architectures were being taken seriously again.
Why it matters now
The question of whether transformers are the final architecture or merely the current one is unresolved. Mamba and related models represent a credible alternative path, and they are being incorporated into production systems where sequence length is a limiting factor. Hybrid architectures that combine attention layers with state-space layers are also being explored, attempting to get the best of both. The broader point is that the trade-off between expressiveness and cost is not fixed. Attention bought us random access to history at quadratic expense; state-space models buy us linear cost at the expense of compression. Which trade-off is correct depends on the task, and it may be that no single architecture dominates across all of them. The fact that this is still an open competition, rather than a settled matter, is itself significant.
The surprising detail
Mamba's selective mechanism uses a gating structure that resembles the forget gates in LSTMs, the recurrent architecture that transformers displaced. The irony is noted in the literature: the solution to transformers' scaling problem borrows from the architecture transformers were meant to have made obsolete. The difference is that LSTMs applied gating within a simple recurrent loop, while Mamba applies it within a structured state-space framework that has better theoretical properties for long-range dependencies. It is not a return to LSTMs, but it is a rehabilitation of ideas that were written off as dead ends five years ago.
What is disputed
Whether Mamba and similar models can match transformer quality across the full range of tasks is not yet settled. The architecture is recent, training methods are still being refined, and many benchmarks were designed with transformers in mind. Some results show parity, others show transformers still ahead. The linear scaling advantage is clear; the capability trade-off is not.
Remember this
Attention is not the only way to let a model use its history. Linear-cost alternatives exist, but they compress rather than preserve, and the trade-offs are still being measured.
Test yourself
A state-space model and a transformer both process a 100,000-token document. The state-space model uses far less memory. Name one specific thing the transformer can do that the state-space model cannot, and explain why the architectural difference makes it impossible.
The transformer can attend directly to a single token from 90,000 steps ago — say, a name mentioned once at the start of the document — without that information having survived a long chain of state updates. In a state-space model, information from 90,000 steps ago exists only in whatever trace it left in the current hidden state. If that information was not deemed important by the selective gating at each of the 90,000 intervening steps, it may have been overwritten or diluted beyond recovery. The transformer pays quadratic cost to keep the entire history accessible; the state-space model pays linear cost but must compress history into a fixed-size vector, and that compression is lossy. Random access versus adaptive summary: different architectures, different capabilities.
Go deeper
- Mamba: Linear-Time Sequence Modeling with Selective State Spaces · arXiv · Albert Gu et al. · 2023-12-01
- Efficiently Modeling Long Sequences with Structured State Spaces · arXiv · Albert Gu et al. · 2021-10-31
Image: Original diagram, The Daily Triptych. Licence: Original work. Source.