State Capacity and Associative Recall

Give a model a list of two hundred key-value pairs and then ask for the value belonging to the fortieth key. Attention does this by construction: the query matches the key, the value is read straight out of the cache, and nothing was ever compressed. A recurrent model has to have decided, at the moment it read pair forty, that it might be asked about it later, and to have found room in a fixed state to keep it alongside the other 199. The gap between those two situations is not an engineering detail that better kernels will close. It is a capacity argument.

The counting argument

A model with state \(h \in \mathbb{R}^{D \times N}\) carries \(DN\) real numbers, which at \(b\) bits of usable precision each is at most \(bDN\) bits of information about everything it has read. A task that requires reproducing \(K\) key-value pairs drawn from a vocabulary of size \(V\) requires roughly \(K \log_2 V\) bits. Once \(K \log_2 V\) exceeds the state budget, some pair is unrecoverable, and no amount of training fixes it because the information is not present.

Jelassi and colleagues turned this into a theorem and its converse: a two-layer transformer can copy strings whose length grows exponentially in the model's width, while a generalised state space model is bounded by its fixed latent state, and the separation shows up empirically both in trained-from-scratch synthetic experiments and in pretrained models at scale (Jelassi, Brandfonbrener, Kakade and Malach, 2024, Repeat After Me: Transformers are Better than State Space Models at Copying, arXiv:2402.01032). The mechanism attention uses is cheap and uninteresting, which is the point: a positional induction head that says "emit whatever followed the last occurrence of this token" costs two layers and no state at all.

What MQAR measures that perplexity does not

The useful benchmark here is multi-query associative recall. A single-query recall task is easy for almost any architecture, because the model can learn to hold one thing. MQAR asks for many lookups interleaved through one sequence, which is a far better proxy for what language modelling actually demands, since a real document is full of entities that must stay retrievable until they are mentioned again.

Arora and colleagues pretrained seventeen attention and gated-convolution architectures and found that the gated-convolution models trailed attention by up to 2.1 perplexity points on the Pile, and that essentially all of the remaining gap was concentrated in tokens requiring associative recall (Arora et al., 2023, Zoology: Measuring and Improving Recall in Efficient Language Models, arXiv:2312.04927). The same work showed the gated-convolution models needed model dimension to grow with sequence length to solve MQAR at all, while attention solved it at constant width, and that adding input-dependent sparse attention recovered 97.4% of the gap while keeping subquadratic scaling. That last figure is the intellectual justification for every hybrid architecture shipped since.

Two things follow. First, aggregate perplexity is a bad instrument here: a 2.1-point gap distributed unevenly across token types looks like a small number and behaves like a missing capability. Second, the fix is not more state, it is different state. Attention over a small recent window is a qualitatively different memory from a compressed summary, which is why a handful of full attention layers buys more than doubling \(N\).

The trade the state dimension actually makes

Raising \(N\) raises capacity linearly and raises both the memory traffic of the scan and the pressure on SRAM. Mamba-2 pushed \(N\) from Mamba's 16 up by more than an order of magnitude, and it could only do so because the structured state space duality reformulation let the state update run as matrix multiplications on tensor cores instead of an elementwise scan. Capacity and kernel design are the same conversation.

When it breaks

Retrieval-heavy application code is the failure surface. In-context learning with many exemplars, long-document question answering with a needle far from the query, structured extraction from a long form, agent traces that must quote a tool result from thirty steps ago: all of these are MQAR wearing a suit. A pure linear-time model can score respectably on summarisation and conversational benchmarks and still fail these.

The failure is quiet. A model that has lost a key-value pair does not abstain; it produces a fluent, plausible, wrong value. There is no cache miss to log and no latency spike to alert on, so the regression shows up as a slow drift in user-reported quality.

Length generalisation hides the problem during evaluation. Capacity pressure scales with how much has to be retained, so a model evaluated at 4k tokens can look equivalent to attention and degrade badly at 64k. Evaluate at the context length you intend to serve, with a recall-shaped task, or the number you report is about the wrong regime.