The Expressive Limits of Diagonal SSMs for State-Tracking
Abstract
State-Space Models (SSMs) have recently been shown to achieve strong empirical performance on a variety of long-range sequence modeling tasks 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) SSMs on sequential state-tracking tasks. We show that single-layer DCD SSMs cannot express state-tracking of any non-Abelian group at finite precision. More generally, we show that $k$-layer DCD SSMs can express state-tracking of a group if and only if that group has a subnormal series of length $k$, with Abelian factors. That is, we identify the precise expressivity range of $k$-layer DCD SSMs within the solvable groups. Empirically, we find that multi-layer models often fail to learn state-tracking for non-Abelian groups, highlighting a gap between expressivity and learnability.
Cite
Text
Shakerinava et al. "The Expressive Limits of Diagonal SSMs for State-Tracking." International Conference on Learning Representations, 2026.Markdown
[Shakerinava et al. "The Expressive Limits of Diagonal SSMs for State-Tracking." International Conference on Learning Representations, 2026.](https://mlanthology.org/iclr/2026/shakerinava2026iclr-expressive/)BibTeX
@inproceedings{shakerinava2026iclr-expressive,
title = {{The Expressive Limits of Diagonal SSMs for State-Tracking}},
author = {Shakerinava, Mehran and Khavari, Behnoush and Ravanbakhsh, Siamak and Chandar, Sarath},
booktitle = {International Conference on Learning Representations},
year = {2026},
url = {https://mlanthology.org/iclr/2026/shakerinava2026iclr-expressive/}
}