The Expressive Limits of Diagonal SSMs for State-Tracking

📄 arXiv: 2603.01959v1 📥 PDF

作者: Mehran Shakerinava, Behnoush Khavari, Siamak Ravanbakhsh, Sarath Chandar

分类: cs.LG

发布日期: 2026-03-02

备注: 18 pages, 5 figures, 4 tables. Accepted at ICLR 2026

💡 一句话要点

揭示对角SSM在状态跟踪任务中表达能力的局限性

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 状态空间模型 序列建模 表达能力 状态跟踪 非阿贝尔群

📋 核心要点

  1. 状态空间模型(SSM)在长程序列建模任务中表现出色，但对其表达能力的理论理解仍然有限。
  2. 本文通过分析DCD SSM对非阿贝尔群的状态跟踪能力，揭示了其表达能力的局限性。
  3. 实验表明，多层DCD SSM在学习非阿贝尔群的状态跟踪时表现不佳，验证了理论分析结果。

📝 摘要（中文）

本文研究了输入相关的复值对角(DCD)状态空间模型(SSM)在序列状态跟踪任务中的表达能力。研究表明，单层DCD SSM无法以有限精度表达任何非阿贝尔群的状态跟踪。更一般地，k层DCD SSM能够表达一个群的状态跟踪，当且仅当该群具有长度为k且因子为阿贝尔群的次正规列。即，我们确定了k层DCD SSM在可解群中的精确表达范围。实验结果表明，多层模型通常无法学习非阿贝尔群的状态跟踪，突出了表达能力和可学习性之间的差距。

🔬 方法详解

问题定义：论文旨在研究对角状态空间模型（Diagonal SSMs）在状态跟踪任务中的表达能力。现有方法在理解SSM的理论表达能力方面存在不足，尤其是在处理非阿贝尔群的状态跟踪时，其能力边界尚不明确。

核心思路：论文的核心思路是通过数学推导，证明k层DCD SSM能够表达一个群的状态跟踪，当且仅当该群具有长度为k且因子为阿贝尔群的次正规列。这意味着DCD SSM的表达能力与群的代数结构密切相关，特别是其是否为可解群以及可解群的结构。

技术框架：论文主要采用数学分析的方法，没有涉及具体的模型训练或推理流程。其核心在于建立DCD SSM的层数与其能够表达的群的代数结构之间的联系。具体来说，论文证明了k层DCD SSM的表达能力与群的次正规列的长度k以及因子是否为阿贝尔群有关。

关键创新：论文最重要的技术创新在于精确地刻画了k层DCD SSM在状态跟踪任务中的表达能力范围。通过将SSM的表达能力与群论中的次正规列概念联系起来，论文提供了一个全新的视角来理解SSM的理论性质。

关键设计：论文的关键设计在于选择了输入相关的复值对角(DCD) SSM作为研究对象，并针对状态跟踪任务进行分析。DCD SSM的对角结构简化了数学分析的难度，同时保留了SSM的核心特性。此外，论文还关注了状态跟踪任务，该任务能够清晰地反映SSM对序列信息的处理能力。

📊 实验亮点

实验结果表明，多层DCD SSM在学习非阿贝尔群的状态跟踪时表现不佳，这与理论分析结果相符。这一发现突出了表达能力和可学习性之间的差距，表明即使模型具有足够的表达能力，也可能难以通过训练学习到正确的状态转移关系。

🎯 应用场景

该研究成果有助于更好地理解状态空间模型的理论性质，并指导模型设计。在需要处理复杂状态转移关系的序列建模任务中，例如机器人控制、自然语言处理等领域，该研究可以帮助选择合适的模型结构，并避免使用表达能力不足的模型。

📄 摘要（原文）

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.