Avsnittsbeskrivning
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…

