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 transformers and SSMs both land in TC0. The argument rests on the unproven conjecture that TC0 ≠ NC1, and it assumes log-precision numbers and worst-case inputs. The discussion explains why linear, nonlinearity-free recurrences can be computed with a parallel scan, and why that same property caps their expressive power. It then walks through the proof that S4's fixed matrix powers and Mamba's input-dependent diagonal matrices both stay within TC0. Listeners get a clear account of why "has a recurrent form" does not imply "has recurrent power." Sources: 1. The Illusion of State in State-Space Models — William Merrill, Jackson Petty, Ashish Sabharwal, 2024 http://arxiv.org/abs/2404.08819 2. Transformers Learn Shortcuts to Automata — Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, Cyril Zhang, 2023 https://scholar.google.com/scholar?q=Transformers+Learn+Shortcuts+to+Automata 3. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1 — David A. Barrington, 1986 (conference 1985) https://scholar.google.com/scholar?q=Bounded-width+polynomial-size+branching+programs+recognize+exactly+those+languages+in+NC1 4. The Parallelism Tradeoff: Limitations of Log-Precision Transformers — William Merrill, Ashish Sabharwal, 2023 https://scholar.google.com/scholar?q=The+Parallelism+Tradeoff%3A+Limitations+of+Log-Precision+Transformers 5. The Illusion of State in State-Space Models — William Merrill, Jackson Petty, Ashish Sabharwal, 2024 https://scholar.google.com/scholar?q=The+Illusion+of+State+in+State-Space+Models 6. The Expressive Power of Transformers with Chain of Thought — William Merrill, Ashish Sabharwal, 2024 https://scholar.google.com/scholar?q=The+Expressive+Power+of+Transformers+with+Chain+of+Thought 7. Mamba: Linear-Time Sequence Modeling with Selective State Spaces — Albert Gu, Tri Dao, 2023 https://scholar.google.com/scholar?q=Mamba%3A+Linear-Time+Sequence+Modeling+with+Selective+State+Spaces 8. Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality (Mamba-2) — Tri Dao, Albert Gu, 2024 https://scholar.google.com/scholar?q=Transformers+are+SSMs%3A+Generalized+Models+and+Efficient+Algorithms+Through+Structured+State+Space+Duality+%28Mamba-2%29 9. Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues — Riccardo Grazzi, Julien Siems, Arber Zela, Jörg K.H. Franke, Frank Hutter, Massimiliano Pontil, 2024 https://scholar.google.com/scholar?q=Unlocking+State-Tracking+in+Linear+RNNs+Through+Negative+Eigenvalues 10. Combining Recurrent, Convolutional, and Continuous-time Models with Linear State Space Layers (LSSL) — Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, Christopher Ré, 2021 https://scholar.google.com/scholar?q=Combining+Recurrent%2C+Convolutional%2C+and+Continuous-time+Models+with+Linear+State+Space+Layers+%28LSSL%29 11. Liquid Structural State-Space Models — Ramin Hasani, Mathias Lechner, Tsun-Hsuan Wang, Makram Chahine, Alexander Amini, Daniela Rus, 2023 https://scholar.google.com/scholar?q=Liquid+Structural+State-Space+Models 12. Chess as a Testbed for Language Model State Tracking — Shubham Toshniwal, Sam Wiseman, Karen Livescu, Kevin Gimpel, 2021 https://scholar.google.com/scholar?q=Chess+as+a+Testbed+for+Language+Model+State+Tracking 13. Entity Tracking in Language Models — Najoung Kim, Sebastian Schuster, 2023 https://scholar.google.com/scholar?q=Entity+Tracking+in+Language+Models 14. Parallelizing Linear Transformers with the Delta Rule over Sequence Length (DeltaNet) — Songlin Yang, Bailin Wang, Yu Zhang, Yikang Shen, Yoon Kim, 2024 https://scholar.google.com/scholar?q=Parallelizing+Linear+Transformers+with+the+Delta+Rule+over+Sequence+Length+%28DeltaNet%29 15. The Expressive Capacity of State Space Models: A Formal Language Perspective — Yash Sarrof, Yana Veitsman, Michael Hahn, 2024 https://scholar.google.com/scholar?q=The+Expressive+Capacity+of+State+Space+Models%3A+A+Formal+Language+Perspective 16. The Illusion of Thought / Transformers, parallel computation, and logarithmic depth — Clayton Sanford, Daniel Hsu, Matus Telgarsky, 2024 https://scholar.google.com/scholar?q=The+Illusion+of+Thought+%2F+Transformers%2C+parallel+computation%2C+and+logarithmic+depth 17. Barrington's theorem: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1 — David A. Barrington, 1989 https://scholar.google.com/scholar?q=Barrington%27s+theorem%3A+Bounded-width+polynomial-size+branching+programs+recognize+exactly+those+languages+in+NC1 Interactive Visualization: The Illusion of State in State-Space Models