William Merrill, Jackson Petty, Ashish Sabharwal
2024 · arXiv
State-space models (SSMs) have emerged as a potential alternative architecture for building large language models (LLMs) compared to the previously ubiquitous transformer architecture. One theoretical weakness of transformers is that they cannot express certain kinds of sequential computation and state tracking (Merrill & Sabharwal, 2023), which SSMs are explicitly designed to address via their close architectural similarity to recurrent neural networks (RNNs). But do SSMs truly have an advantage (over transformers) in expressive power for state tracking? Surprisingly, the answer is no. Our analysis reveals that the expressive power of SSMs is limited very similarly to transformers: SSMs cannot express computation outside the complexity class $\mathsf{TC}^0$. In particular, this means they cannot solve simple state-tracking problems like permutation composition. It follows that SSMs are provably unable to accurately track chess moves with certain notation, evaluate code, or track entities in a long narrative. To supplement our formal analysis, we report experiments showing that Mamba-style SSMs indeed struggle with state tracking. Thus, despite its recurrent formulation, the "state" in an SSM is an illusion: SSMs have similar expressiveness limitations to non-recurrent models like transformers, which may fundamentally limit their ability to solve real-world state-tracking problems.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
4 selected excerpts · 4 total mentions
The formulations in attention as rnn have similar issues as rwkv. Fundamentally it's a question of what we call an RNN. Personally I think it's important not to call some of these recent architectures RNNs because they have theoretical properties that do not match (read: they're worse) what we've "classically" called RNNs. Ref: https://arxiv.org/abs/2404.08819 As a rule of thumb: you generally don't get parallelism for free, you pay for it with poorer expressivity.
The model in the paper isn't a "real" RNN due making it parallelizable, for same the reasons described in https://arxiv.org/abs/2404.08819 , and hence is theoretically less powerful than a "real" RNN (struggles at some classes of problems that RNNs traditionally excel at). On the other hand, https://arxiv.org/abs/2405.04517 contains a "real" RNN component, which demonstrates a significant improvement on the kind of state-tracking problems that transformers struggle with.
Recent example of a proof regarding theoretical limitations of Transformers: https://aclanthology.org/2023.tacl-1.31.pdf (also extended to cover SSMs https://arxiv.org/pdf/2404.08819)
Quadratic transformers outperform weaker forms of attention on recall tasks, but recurrent models are strictly more powerful than transformers (when they don't use chain of thought) at state tracking problems. Mamba 2 likely has the same limitations with state tracking as a full transformer due to being parallelizable: https://arxiv.org/abs/2404.08819 .
More from the same topics.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan +11
Artificial intelligence (AI) researchers have been developing and refining large language models (LLMs) that exhibit remarkable capabilities across a variety of domains and tasks, challenging our understanding of learning and cognition.
Tom B. Brown, Benjamin Mann, Nick Ryder +28
Recent work has demonstrated substantial gains on many NLP tasks and benchmarks by pre-training on a large corpus of text followed by fine-tuning on a specific task.
Chiyuan Zhang, Samy Bengio, Moritz Hardt +2
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.