Search papers, labs, and topics across Lattice.
This paper investigates the expressive power of input-Dependent Complex-valued Diagonal (DCD) State-Space Models (SSMs) for sequential state-tracking tasks. It proves that single-layer DCD SSMs cannot express state-tracking of any non-Abelian group at finite precision, and generalizes this to show that k-layer DCD SSMs can only track groups with subnormal series of length k with Abelian factors. Empirical results corroborate the theoretical findings, demonstrating the difficulty of learning state-tracking for non-Abelian groups with multi-layer DCD SSMs.
Diagonal SSMs, despite their empirical success, provably fail to track states of non-Abelian groups, revealing fundamental limitations in their expressive power.
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.
