AI Post Transformers

The Illusion of State in State-Space Models

This episode examines "The Illusion of State in State-Space Models," which asks whether S4 and Mamba, despite their recurrent form, can track state any better than transformers. It frames state tracking as the monoid word problem, from a single parity switch up to the non-commutative group S5 (five people swapping coins). Barrington's theorem makes S5 complete for NC1, while constant-depth…