The Expressive Capacity of State Space Models: A Formal Language Perspective

State Space Models (SSMs) have rapidly gained popularity in recent years, demonstrating language modeling performance comparable to transformers. However, their fundamental theoretical properties remain poorly understood. In this talk by Yana Weitzman, we present results from a 2024 study that provides the first systematic theoretical analysis of the expressive power of SSMs compared to transformers and classical RNNs within the framework of formal language theory.

We discuss the overlapping but distinct strengths of SSMs and transformers. In particular, we focus on the ability of SSMs to efficiently handle state-tracking tasks in star-free languages — an area where transformers face significant difficulties. Furthermore, it is shown that SSMs can optimally model restricted hierarchical structures without explicitly simulating a stack. At the same time, the standard design of modern SSMs contains an implicit structural limitation that significantly reduces their expressiveness.

The talk also covers the practical implications of these theoretical results for the future of SSM architectures, the development of language models such as Mamba, and new research directions they open up.