The Illusion of State in State-Space Models
Free while signed in. Answers cite the passages they came from.
This paper proves that modern state-space models (Mamba, S4, etc.) share the same expressive ceiling as transformers: they cannot compute anything outside the TC^0 complexity class, despite the RNN-like "state" vocabulary they borrow.
Expressive-power result: SSMs with typical parameterizations are provably confined to TC^0, which means the "state" that accumulates through the recurrence cannot simulate general sequential computation.
Tasks they cannot solve: Permutation composition, code evaluation with branches, and entity tracking across long narratives all require state beyond TC^0 and therefore cannot be learned reliably by these SSMs.
Transformer parity: The result places SSMs on the same theoretical footing as transformers rather than above them, pushing back against the intuition that recurrence automatically grants richer state.
Practical implication: If you need genuine state tracking (interpreters, stateful agents, long-horizon planning), architectural changes beyond current SSMs are required - a clean "state is an illusion" framing for the field.
Get next week’s papers.
The same picks and the same summaries, in your inbox. Free, and 176 issues deep.
Subscribe on Substack