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

CREATORYifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-06148

Browse the full library · About the Tower of Babel