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 𝖳𝖢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.
more »
« less
Chemical activation of oxygen molecule by quantum electronic state selected vanadium cation: observation of spin–orbit state effects
- Award ID(s):
- 1763319
- PAR ID:
- 10227209
- Date Published:
- Journal Name:
- Molecular Physics
- Volume:
- 119
- Issue:
- 1-2
- ISSN:
- 0026-8976
- Page Range / eLocation ID:
- e1767309
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Steady-state modeling plays an important role in the design of advanced power converters. Typically, steady-state modeling is completed by time-stepping simulators, which may be slow to converge to steady-state, or by dedicated analysis, which is time-consuming to develop across multiple topologies. Discrete time state-space modeling is a uniform approach to rapidly simulate arbitrary power converter designs. However, the approach requires modification to capture state-dependent switching, such as diode switching or current programmed modulation. This work provides a framework to identify and correct state-dependent switching within discrete time state-space modeling and shows the utility of the proposed method within the power converter design process.more » « less