The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song · 2024
Read The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity by Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-06148.txt.
Description
Yifang Chen and co-authors prove, in a 2024 paper, hard limits on what a popular alternative to the Transformer can compute. Mamba and its state-space relatives process sequences with a compact memory state, and some hoped they were stronger than Transformers. The authors test that hope using circuit complexity, a framework that sorts problems by the hardware depth needed to solve them. They ask which class these models fall into when their precision and depth are bounded.
The proof shows both model families sit in the same low complexity class as Transformers. That means some problems lie beyond them all, unless a long-standing gap in complexity theory closes. Examples include certain formula and ordering problems. The authors conclude that Mamba's real edge is speed and memory use, not greater computing power.
Catalog record
| CREATOR | Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-06148