State space models and Mamba: reading long sequences without attention

Why it was needed: existing models stall on long sequences

Most of today's LLMs run on Transformers. Attention, the core of the Transformer, compares every token in the context with every other token and exchanges information densely. The Mamba paper paper summarizes two costs that come with this strength. One is that it cannot handle anything outside its fixed window (the context window) at all; the other is that computation grows with the square of the window length. Many efficient attention variants have been proposed to reduce this cost. But the same paper points out that these variants often lose the very properties that make attention effective.

RNNs (recurrent neural networks), which read in order, have a cost that grows linearly with length. However, gradients vanish during training, so they struggled to remember the distant past. According to the S4 paper paper, RNNs, CNNs and Transformers all had specialized variants for handling long dependencies, but still had difficulty scaling to sequences beyond 10,000 steps. On the Path-X task (length 16,384) of Long Range Arena, a long-sequence benchmark, none of the previous models did better than random guessing (50%).

So what was needed was a model that trains quickly in parallel, costs a constant amount per token during generation, and can still hold on to information from the distant past. State space models (SSMs) emerged as candidates aiming at these requirements.

Core idea: one notepad page instead of full meeting minutes

Let's start with an analogy. A Transformer is like someone who writes down everything said in a meeting without dropping a single line, then rereads the whole record every time a question comes up. It is accurate, but the longer the meeting runs, the longer both the record and the time spent searching it become. An SSM is closer to someone who holds just one fixed-size notepad page and rewrites the notes each time they hear a new remark. Because the page has a fixed size, each rewrite costs the same no matter how long the meeting goes on.

This 'notepad' is the state. As the S4 paper paper explains, SSMs are mathematical models originally used in fields such as control theory and computational neuroscience. An input signal passes through a hidden state to the output, and matrices A, B, C and D determine how the state changes and what is emitted. The key is the state matrix A. With a well-chosen A, signals from the distant past can be preserved mathematically for a long time.

The question is what to write on the notepad. Early SSMs updated their notes by the same rule regardless of the input. This worked well for continuous signals such as audio, but was weak for text, where the meaning of each individual word matters. Mamba paper fixed exactly this point: it lets the model look at each new token and decide on the spot whether 'this is worth writing down' or 'this can be let go.'

How it works: state updates, two ways to compute, and selection

The operation of a single SSM layer is easiest to understand step by step. First, when a token comes in, it is combined with the current state to form a new state (A determines how much of the previous state to keep, and B how much of the new input to add). Second, C reads the output from the new state. Third, the same process repeats for the next token. As the Mamba paper paper describes, each channel of the input passes through a higher-dimensional hidden state to the output.

The advantage of SSMs emphasized by S4 paper is that the same computation can be viewed in two ways. During generation, the model can run in recurrence mode, updating the state one step at a time. During training, because the parameters do not change over time, the whole sequence can be computed at once as a single long convolution. In effect, it does inference like an RNN and trains in parallel like a CNN.

Mamba added 'selection' to this. It changed the step size Δ, which determines how much to update the state, along with B and C, from fixed values into values computed from the current token. This lets the model selectively pass along or forget information as it moves through the sequence. There is a cost: since the parameters now change over time, the convolution method above can no longer be used. Mamba solved this with a hardware-aware parallel scan algorithm. By never actually materializing the large expanded state in the GPU's slow memory, it avoids data movement between levels of the GPU memory hierarchy. The paper reported that this implementation is up to 3x faster than previous methods on an A100 GPU.

Finally, Mamba merged this selective SSM with the Transformer's MLP block into a single simple block. The architecture just stacks this block, with no attention and no separate MLP block. During generation, no cache of previous tokens is needed, so each token takes a constant amount of time. This is the biggest difference from Transformers, which carry an ever-growing KV cache.

How it developed: from S4 to Mamba and Mamba-2

S4 paper solved a problem left by earlier work. According to the paper, its immediate predecessor, LSSL (Linear State-Space Layer), showed that deep SSMs can handle long-range dependencies when they use a special state matrix A. However, it required O(N²L) computation and O(NL) memory for state size N and length L, which made it hard to use in practice. S4 split A into a 'low-rank term + normal term' so that it could be diagonalized stably. As a result, the computation reduced to a well-studied Cauchy kernel computation, and computation and memory became nearly proportional to N+L. It is up to 30 times faster than LSSL and uses 400 times less memory. S4 was the first to solve Path-X, reaching 88% accuracy, and outperformed existing models by more than 20 points on the overall LRA average. It recorded 91% accuracy on sequential CIFAR-10, and its generation was 60 times faster.

Mamba paper targeted a limitation of the S4 family: it is strong on continuous signals such as audio and vision but weak on discrete, information-dense data such as text. With the selection mechanism and hardware-aware scan described earlier, it achieved 5 times higher generation throughput than Transformers of similar size. The paper reported that performance improved on real data with sequences up to 1 million in length. In language modeling, Mamba-3B outperformed Transformers of the same size and matched Transformers twice its size. For example, it scored 4 points higher than Pythia-3B on the common-sense reasoning average and also surpassed Pythia-7B. However, the scaling law experiments shown in the paper only go up to 1 billion (1B) parameters.

The Mamba-2 paper paper showed that the two families are closer than they seem. Decomposing a structured matrix called a semiseparable matrix in different ways connects SSMs and attention variants to each other. This is called State Space Duality (SSD). Building on this framework, the authors designed Mamba-2, a refinement of Mamba's selective SSM; its core layer is 2–8 times faster while remaining competitive with Transformers in language modeling.

Where it is heading: why it struggles with retrieval, and how it copes with long context

The biggest open issue is in-context retrieval: accurately finding and bringing back specific content from a long text. Mamba is weaker than Transformers here. The usual explanation has been that the fixed-size state loses information. A retrieval bottleneck analysis study paper challenged this explanation. In a setting where the question is given before the context, the model can know in advance what to remember, so state size should not be the decisive constraint. Yet even in this setting, Mamba fell far behind. The gate was powerful enough: manipulating only the selection gate could swing accuracy between extremes. The researchers located the problem elsewhere. The signal within token Representations that something is 'relevant to the question' emerges gradually as it passes through deeper layers, and the gate reflects that signal only several layers later. The gates in the layers critical for retrieval were not yet aligned with relevance. This means the selection mechanism is strong enough, but it often operates before the signal it needs for its decisions has arrived.

The second direction is an attempt to close the performance drop on long contexts without training. SuPER-Mamba paper computes, at each position, how 'surprised' an already-trained Mamba model is by the next token (Surprisal). It then uses this score to decide which positions' information to prioritize in the global state update. It requires neither additional training nor question-specific scoring. The authors reported that the average LongBench-E score across three SSM models rose from 8.06 to 15.69.

The third direction revisits the state update itself. According to a study of oscillatory dynamics in Mamba-3 paper, Mamba-3 added an input-dependent rotation to the state update. This study interpreted that rotation as 'underdamped oscillation.' In controlled comparisons, oscillating dynamics did better than non-oscillating decay on state-tracking tasks, and in language model pretraining they helped long-context prediction and length generalization. The researchers' interpretation is that the rotation appears to act as a mechanism that controls how already-stored information and newly arriving updates are combined.

Limitations and open issues

First, the cost of compression. The advantage of having only a single notepad is also a weakness. A Transformer keeps the original text in the KV cache and can look at it again when needed, but an SSM cannot retrieve and re-read past content. The retrieval study above paper showed that there are causes beyond state size, but it confirmed that retrieval is a weakness of Mamba. The SuPER-Mamba study paper also starts from the observation that SSM performance often drops as context grows longer.

Second, dependence on implementation. Once the selection mechanism was added, the fast convolution computation of the S4 era could no longer be used. Mamba made up for this with a dedicated scan kernel that carefully handles the GPU memory hierarchy paper. This means that for theoretical linearity to translate into real-world speed, a hardware-aware implementation is essential.

Third, evidence on scale. The Mamba-2 paper paper described Mamba as matching or outperforming Transformers at 'small to medium scale,' and the scaling experiments in the Mamba paper also go only up to 1 billion parameters. Whether the same conclusion holds at much larger scales cannot be determined from the sources for this article alone. It is best not to read the benchmark numbers as 'replaces Transformers at every scale.'

Further study

Chronological order works best. First, read the introduction and Figure 1 of S4 paper to grasp the idea that an SSM can be computed in two ways: recurrently and as a convolution. If the math feels heavy, you can treat the low-rank correction and Cauchy kernel parts simply as 'techniques that make computation cheap' and move on.

Next is Mamba paper. Focus on why the selection mechanism is needed (synthetic tasks such as selective copying and induction heads) and what the hardware-aware scan avoids. Reading Mamba-2 paper after that shows why SSMs and attention are not entirely separate worlds.

For recent work, start with the retrieval bottleneck analysis paper. It keeps you from seeing Mamba's weakness only as 'the state is too small.' Then read SuPER-Mamba paper, which compensates for long context without training, followed by the Mamba-3 study paper, which interprets the dynamics of the state update.