The Illusion of State in State-Space Models
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.
Ask this paper
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.