The Illusion of State in State-Space Models

状态空间模型（SSMs）已经成为与以前普遍使用的Transformer架构相比，用于构建大型语言模型（LLMs）的潜在替代架构。 Transformer的一个理论弱点是它不能表达某些类型的顺序计算和状态跟踪（Merrill和Sabharwal，2023），而SSMs则通过其与递归神经网络（RNNs）的紧密架构相似性来明确解决这个问题。但是，SSMs在状态跟踪方面真的比Transformer具有优势吗？令人惊讶的是，答案是否定的。我们的分析揭示了SSMs的表达能力与Transformer非常相似：SSMs无法表达复杂度类$\mathsf{TC}^0$之外的计算。特别是，这意味着它们无法解决简单的状态跟踪问题，如排列组合。因此，SSMs无法准确地跟踪某些符号的国际象棋走法，评估代码或跟踪长篇故事中的实体。为了补充我们的正式分析，我们报告了实验结果，显示Mamba风格的SSMs确实在状态跟踪方面存在困难。因此，尽管它是递归式的，但SSM中的“状态”是一种幻觉：SSMs的表达能力限制与Transformer等非递归模型非常相似，这可能从根本上限制了它们解决实际状态跟踪问题的能力。

本论文试图比较状态空间模型（SSM）和Transformer模型在状态跟踪方面的表现，验证SSM是否真的比Transformer更具有表达能力。

论文的关键思路是通过分析和实验，发现SSM和Transformer在表达能力上存在类似的限制，都不能超出复杂度类TC0的范围，从而无法解决一些实际的状态跟踪问题。

论文的实验结果表明，SSM在状态跟踪方面表现不如预期。此外，论文还提到了SSM的架构与循环神经网络（RNN）的相似性，以及SSM无法解决一些简单的状态跟踪问题，如棋谱的排列组合、代码评估和长篇叙述中的实体跟踪等。值得进一步研究的是如何提高SSM的表达能力，以及如何在实际应用中解决状态跟踪问题。

最近在这个领域中，还有一些相关的研究，如《Attention Is All You Need》和《Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context》等。