The Illusion of State in State-Space Models

Conceptual map of complexity classes. Click a chip. Toggle the conjecture.

All dimes except Carl's coin (orange). Swap neighbours and track the odd coin. Final state is one of 120 arrangements: S5.

Same two swaps, opposite order, different arrangement (computed live from the identity).

Group orders are exact. Barrington: word problem of non-solvable groups (smallest: S5) is NC1-complete.

h_i = A_i·h_i-1 + B_i·x_i: no nonlinearity inside, so the combine step is associative. Step through 8 tokens.

Sequential steps (n−1) vs. a balanced tree (⌈log₂ n⌉). Exact arithmetic, not measurements.

Click any box. Theorem numbers follow the episode.

Structure only: S4 reuses one matrix, Mamba varies a diagonal, IDS4 varies a full matrix.

Each symbol becomes a matrix; multiplying composes state maps. Shown: parity automaton from a one-hot start vector set by the beginning-of-string symbol.

Reported: RNN and IDS4 need 1 layer for lengths 5–20 on all three groups. Transformer, S4, Mamba climb from ≈1 to ≈4 (read off the plot; no exact counts, no variance). Dashed lines join those two readings only.