Behnoush Khavari

The Expressive Limits of Diagonal SSMs for State-Tracking

State-Space Models (SSMs) have recently been shown to achieve strong empirical performance on a variety of long-range sequence modeling task… (see more)s while remaining efficient and highly-parallelizable. However, the theoretical understanding of their expressive power remains limited. In this work, we study the expressivity of input-Dependent Complex-valued Diagonal (DCD) State-Space Models (SSMs) on sequential state-tracking tasks for abstract groups. It is easy to show that a single DCD SSM layer with a universal decoder can track any Abelian group at finite precision by decomposing it into a product of cyclic groups. We show that this is tight by proving that such a model cannot track any non-Abelian group at finite precision. We further establish the expressivity of multi-layer DCD SSMs. We show that a

2025-12-31

International Conference on Learning Representations (Accept (Poster))

doi.org

openreview.net

Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMs

Jayesh Khullar

Franccois Rivest

A. Chandar