How do state-space models like Mamba differ from attention, and when would you use one?

How to think about it

Attention lets each token directly weight information from earlier positions, so full causal attention, where a token can see itself and the past but not the future, has quadratic cost as sequence length grows and a KV cache, the saved key and value vectors, that grows with context during generation. Mamba uses a selective state-space recurrence, a fixed-size memory update whose rules depend on the current input, in linear time; it trades arbitrary exact lookup for bounded memory and cheaper long-stream serving.

Why attention behaves this way

At position i, self-attention creates three vectors: a query, meaning what the current token is looking for; keys, meaning what each candidate token represents; and values, meaning the information that can be retrieved. The query is compared with the keys for earlier positions, and the resulting weights are used to mix their values.

That is content-addressable memory. If the current token asks, in effect, “What database host did we mention earlier?”, attention can give a high weight to the earlier token containing db-17. The route from the current position to that earlier position is direct.

For a sequence of N tokens, causal attention considers about N(N + 1) / 2 query-key pairs. The constant is smaller than full bidirectional attention, but the scaling is still O(N²). Optimisations such as FlashAttention reduce memory traffic and avoid materialising the entire attention matrix. They do not remove the underlying all-pairs interaction.

Generation has a second cost. When a language model produces token number 10,001, it must compare that token’s query with the keys and values for the previous 10,000 tokens. Those past vectors are stored in the KV cache so the model does not recompute them. The cache is useful, but it grows linearly with context. Generating a whole sequence one token at a time gives quadratic total attention work, even though each individual decoding step is linear in the current context length.

How Mamba carries history

A state-space model represents the past with a hidden state rather than a separate memory slot for every token. A simplified update is:

h_t = A_t h_{t-1} + B_t x_t

y_t = C_t h_t

Here, x_t is the current input, h_t is the carried state, and y_t is the output. The state has a fixed shape chosen by the model. It is updated when a new token arrives, so the model does not search through every previous token.

Mamba makes this recurrence selective. Learned functions of the current input control the effective step size and the input and output projections. In plain English, the model can learn that one token should be written strongly into its state, another should be mostly ignored, and a third should cause old information to be overwritten. This is content sensitivity, but it is not the same as attention’s direct address lookup.

For fixed model width, one state update per token gives O(N) sequence cost. During training, Mamba uses a parallel scan so many recurrence updates can be evaluated efficiently on a GPU. During autoregressive generation, the computation is naturally recurrent: one new token updates one existing state. The state cache remains fixed with respect to N; it still scales with the number of layers, streams, and state dimensions. Mamba also has a short convolutional state, but that state is fixed-size too. There is no context-length KV cache.

A concrete 100,000-token example

Imagine an incident assistant reading a 100,000-token stream of deployment logs. At token 2,000, the logs say that requests began timing out on host db-17. At token 99,800, an engineer asks, “Which host first showed the timeout?”

Attention has a natural answer path: the query at token 99,800 can assign weight to the key at token 2,000 and retrieve its value. Mamba must have preserved db-17 in its state while processing the intervening 97,800 tokens. A well-trained selective model may do that. The architecture does not guarantee it, because the state is a compressed representation rather than an addressable record.

The memory difference can be made concrete. Suppose a decoder has 32 layers, 8 KV heads, a head size of 128, and stores keys and values in 16-bit floating point:

32 layers × 100,000 tokens × 8 heads × 128 values
× 2 tensors for key and value × 2 bytes
= 13,107,200,000 bytes

That is roughly 13.1 GB, or 12.2 GiB, just for the KV cache. It excludes weights, activations, allocator overhead, and other runtime memory. At one million tokens, the same cache would be about 131 GB.

Now use an illustrative fixed state: 32 layers, each storing 4,096 channels by 16 state values in 16-bit precision:

32 × 4,096 × 16 × 2 bytes = 4,194,304 bytes

That is about 4.2 MB for the SSM state alone, independent of whether the stream has 100,000 or one million tokens. This is an example, not a promise that every Mamba model uses that exact state size. Larger inner dimensions and convolution buffers change the number. The important property is that the number does not grow with the sequence.

The trade-off a strong answer should mention

Mamba does not remember nothing. It remembers a learned, finite summary. That works well for trends, running structure, selected facts, and signals where the past can be compressed. It is weaker when the task requires arbitrary associative recall: copying an exact identifier, comparing two distant pieces of code, or answering a question about one obscure line buried in a long document.

A useful failure test is a “needle in a haystack” prompt. Put a unique order ID at token 80,000, surround it with thousands of similar IDs, and ask for the exact one near the end. If the model returns a plausible but incorrect ID, the problem is not necessarily ordinary hallucination. The state may have overwritten or blended the relevant detail.

The reverse misconception is also common: attention’s direct access does not guarantee perfect recall. A model can assign poor weights, suffer from positional limitations, or lose information in the middle of a long context. Attention also has a finite context window and an expensive cache. Its advantage is architectural access, not an automatic accuracy certificate.

Nor does O(N) mean Mamba is always faster. At 2,000 or 8,000 tokens, highly optimised attention kernels may beat a recurrent scan because matrix operations use GPU hardware extremely well. Mamba’s advantage becomes more compelling when context is very long, many streams must run concurrently, or memory and tail latency are hard limits. Benchmark the actual model, hardware, batch shape, and context distribution. Big-O notation is not a speedometer.

Hybrid models are often the practical compromise. Most layers can use an SSM for efficient sequence processing, while selected global-attention layers provide direct token-to-token access. Jamba is a named example of this general design. If those attention layers are global, the system is not strictly linear in sequence length; it has fewer quadratic layers, not zero quadratic work. Local or sparse attention can reduce that cost further.

When I would choose each

I would choose Mamba or a similar SSM for streaming sensor data, audio, logs, or very long sequences where each stream needs predictable memory. It is especially attractive when a service may hold thousands of active streams and cannot afford a context-growing cache for every one.

I would choose full attention for retrieval-heavy language tasks, code with many cross-references, and moderate contexts where exact access to arbitrary earlier tokens is more valuable than bounded state. I would choose a hybrid when the product needs both long-context efficiency and reliable long-range recall.

In production, state management becomes part of correctness. Each conversation or incident stream needs its own state. The state must be reset at a real boundary and preserved across chunks. A common failure is accidentally reusing one customer’s state for the next request. The first symptom is often a confident answer containing a name, host, or fact from the previous conversation. Another is losing state between chunks, which makes a long stream behave as if it repeatedly starts from an empty context.

What they’ll ask next

Does linear-time Mamba always beat quadratic attention?
No. Linear scaling wins as sequences become large, but attention often has better hardware utilisation at shorter lengths. Compare end-to-end throughput, p99 latency, memory, and quality at the context lengths that matter.

Does Mamba have no cache?
It has a cache, but it is a fixed recurrent state, plus small convolutional state, rather than one key and value representation per past token. Memory is constant with respect to context length, not zero.

Why not just use a standard RNN?
Mamba combines recurrent state updates with structured state-space dynamics, input-dependent selectivity, and a hardware-aware parallel scan for training. It is designed to retain useful long-range information while avoiding the training and serving costs of a plain token-by-token recurrence. That makes it a different efficiency and optimisation trade-off, not merely a new name for an RNN.

Say this in the interview: “Attention gives every token direct access to every past token but pays quadratic interaction cost and a growing KV cache; Mamba compresses history into a selective fixed-size state, so I would use it for very long or streaming workloads and prefer attention or a hybrid when exact long-range retrieval is critical.”