揭示了对角状态空间模型在追踪非阿贝尔群状态时的表达极限。
The Expressive Limits of Diagonal SSMs for State-Tracking
- 通过代数结构分析，证明单层模型无法表达有限精度下的非阿贝尔群状态追踪
- 多层模型仅能表达具有长度≤k的可解列的群，且因子均为阿贝尔群
- 实验显示多层模型难以学习非阿贝尔群状态，暴露表达能力与可学习性差距
状态空间模型（SSMs）在长序列建模任务中表现出色，同时保持高效与高度并行性。然而，其表达能力的理论理解仍不充分。本文研究输入依赖的复数对角（DCD）SSMs在序列状态追踪任务中的表达能力。我们证明：单层DCD SSM无法在有限精度下表达任何非阿贝尔群的状态追踪。更一般地，k层DCD SSM可表达某群的状态追踪，当且仅当该群存在长度为k的子正规列，且各因子均为阿贝尔群。即，我们精确刻画了k层DCD SSM在可解群中的表达范围。实验发现，多层模型常难以学习非阿贝尔群的状态追踪，凸显表达能力与可学习性之间的差距。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。