Recently, recurrent models based on linear state space models (SSMs) have shown promising performance in language modeling (LM), competititve with transformers. However, there is little understanding of the in-principle abilities of such models, which could provide useful guidance to the search for better LM architectures. We present a comprehensive theoretical study of the capacity of such SSMs as it compares to that of transformers and traditional RNNs. We find that SSMs and transformers have overlapping but distinct strengths. In star-free state tracking, SSMs implement straightforward and exact solutions to problems that transformers struggle to represent exactly. They can also model bounded hierarchical structure with optimal memory even without simulating a stack. On the other hand, we identify a design choice in current SSMs that limits their expressive power. We discuss implications for SSM and LM research, and verify results empirically on a recent SSM, Mamba.

基于线性状态空间模型的循环模型在语言建模方面表现出色，与变压器竞争力强，但对此类模型的原理能力了解甚少，因此我们提出了一项理论研究，比较了这种模型与变压器和传统循环神经网络的能力，发现它们有重叠但有区别的优势。

状态空间模型的表达能力：形式语言视角