🤖 machine learning

On the Expressiveness of State Space Models via Temporal Logics

本文利用时序逻辑分析了状态空间模型（SSMs）的表达能力，揭示了其能力如何根据门控机制和算术精度在正则语言到非正则语言之间变化，并系统地将这些发现与 Transformer 架构进行了比较。

原作者： Eric Alsmann, Lowejatan Noori, Martin Lange

发布于 2026-01-28

📖 1 分钟阅读☕ 轻松阅读

原作者： Eric Alsmann, Lowejatan Noori, Martin Lange

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图教一个机器人阅读一个故事并理解事件的顺序。在人工智能的世界里，有两种主要的“读者”（架构）正在竞争这个职位：著名的 Transformer（驱动当前聊天机器人的那种）和被称为 状态空间模型（SSM） 的后起之秀。

这篇论文是对 SSM “脑力”的一项理论研究。作者们并不是在询问这些模型在特定测试中的表现有多好；他们问的是：“无论我们如何训练，这些模型的理解能力绝对极限在哪里？”

为了回答这个问题，他们使用了一种特殊的“逻辑语言”（时序逻辑）作为衡量标准。以下是使用简单类比对他们发现的详细解读。

1. 两类主要的 SSM

论文根据这些模型处理信息的方式，将 SSM 分为两种主要类型：

对角门控 SSM（“严谨的会计师”）： 这些模型的规则是其内部的“门”（控制信息流的开关）可以根据当前正在阅读的词进行变化，但必须保持“对角线”特征。这就像一个计算器，你可以改变相加的数字，但不能把列与列之间混在一起。
时不变 SSM（“稳定的时钟”）： 这些模型的门无论在阅读什么词时都不会改变。它们就像节拍器或时钟一样；无论讲述什么故事，它们的滴答频率都是恒定的。

2. 精度的难题：尺子 vs 卷尺

作者还观察了这些模型内部数学运算的“精确度”。

定点精度（Fixed-Precision）： 想象使用一把只有 10 个刻度的尺子。无论故事有多长，你都无法测量比这些刻度更小的东西。这就像标准的计算机数学（浮点运算）。
对数精度（Log-Precision）： 想象使用一把会随着故事变长而自动变长且变得更精细的卷尺。如果故事长 100 个词，你的尺子就有 100 个刻度；如果故事长 1,000 个词，它就有 1,000 个刻度。这允许进行更精细的计数。

3. 它们究竟能理解什么？

“严谨的会计师”（对角线 SSM）

使用简单的尺子（定点精度）： 它们擅长理解事件的顺序。它们可以告诉你“A 发生在 B 之前”或者“A 发生了，然后 B 发生了，然后 C 发生了”。然而，它们有一个严重的盲点：它们无法进行循环计数。
- 类比： 如果你要求它们识别某种模式，比如“偶数个 'a'”（例如 aa, aaaa, aaaaaa），它们会失败。因为它们的数学是单调的（只会增加或保持不变），它们最终会“卡住”，无法区分 2 个 'a' 和 4 个 'a'。
使用增长的卷尺（对数精度）： 如果你赋予它们精确计数的能力，它们会变得聪明得多。它们现在可以精确计算过去发生了多少次。它们可以理解复杂的模式，比如“'a' 的数量等于 'b' 的数量等于 'c' 的数量”。

“稳定的时钟”（时不变 SSM）

使用简单的尺子： 这些模型在追踪复杂的“自从……”关系方面表现较差（例如，“自从上次看到 'b' 以来，是否看到了 'a'？”）。但是，它们有一个超能力：它们可以进行循环计数。
- 类比： 由于其内部机制是一个恒定的循环，它们非常擅长知道“这是第 2、第 4 还是第 6 个词？”它们可以轻松识别出“会计师”失败的“偶数个 'a'”模式。
使用增长的卷尺： 它们既可以进行循环计数，也可以进行总量计数。

“混合型”（混合 SSM）

如果将这两种类型的层结合起来（一些严谨的会计师，一些稳定的时钟），你就能获得两者的优点。它们可以理解顺序、循环和计数。论文表明，这些混合模型可以识别几乎任何你能想到的“正则”模式，直到达到一定的复杂度限制。

4. 它们如何与 Transformer 进行比较？

作者将他们的发现与我们已知的 Transformer 进行了对比：

对角线 SSM（定点精度） 大致等同于没有位置提示的 Transformer（它们知道词的顺序，但不知道它们的精确位置）。
时不变 SSM 等同于带有位置编码的 Transformer（它们知道自己在句子中的确切位置）。
重大区别： 拥有“全局注意力”（如平均硬注意力类型）的 Transformer 可以查看整个故事，从而向前和向后进行计数。而 SSM 由于其本质，只能看向过去（已经阅读的内容）。因此，在处理计数发生在序列之后的事情时，SSM 的能力严格弱于最先进的 Transformer。

5. “不可能完成的任务”

最重要的启示是这些模型无法做的事情清单，无论你如何训练它们：

一个定点精度的对角线 SSM 永远无法学会区分重复项目的奇数和偶数（如 aa 与 aaa）。这是一个架构上的硬性限制，而不是训练失败。
要打破这个限制，你必须要么改变架构（添加时不变层），要么提高数学精度（使用增长的卷尺）。

总结

把这些模型想象成不同的图书管理员：

对角线（定点）： 擅长按顺序读书，但如果被要求计数特定模式，就会感到困惑。
时不变： 擅长数页数（奇偶数），但在处理复杂的“自从那时起”的故事时表现挣扎。
混合型： 终极图书管理员，两者兼顾，但仍然无法通过“预读”下一章来计数。

论文证明了这些局限性是内置于架构的 DNA 之中的。你无法通过训练让一个“定点精度对角线”图书管理员变成一个“计数型”图书管理员；你必须给他们更好的工具（对数精度）或不同的脑结构（混合层）来实现目标。

技术摘要：论状态空间模型在时序逻辑下的表达能力

问题陈述

状态空间模型（SSMs）已成为序列建模领域中具有竞争力的 Transformer 架构替代方案，尤其是在大型语言模型中。然而，尽管经验性的进展非常迅速，但关于 SSMs 表达能力的理论基础与 Transformer 相比仍未得到充分探索。本文解决的核心问题是：在独立于训练动态的情况下，不同的 SSM 变体在理论上能表示哪些类别的语言和模式。具体而言，本文研究了两个关键的架构维度如何影响表达能力：

门控机制（Gating Mechanisms）： 区分了时不变门（常数矩阵，如 S4）、对角门控机制（输入依赖的对角矩阵，如 S6）以及任意门。
算术精度（Arithmetic Precision）： 区分了固定宽度算术（恒定比特数，如标准浮点数）与对数精度算术（精度随输入长度对数级缩放）。

作者旨在将这些变体映射到形式逻辑片段和复杂度类，以建立严格的下界并识别根本性的架构瓶颈。

研究方法

作者采用了一种逻辑与复杂度理论框架来分析 SSM 的表达能力，这借鉴了近期关于 Transformer 的基础性工作（例如，Strobl 等，2024；Yang 等，2024a）。

形式化模型： 将 SSMs 正式定义为通过线性递归（ $h_t = \text{gate}(x_t) \cdot h_{t-1} + \text{inc}(x_t)$ ）转换输入序列，随后进行非线性输出函数（建模为带有 ReLU 激活的馈送前向神经网络）的层。
逻辑框架： 分析利用了有限迹上的线性时序逻辑（LTLf），特别是纯过去片段（PLTLf）。该逻辑捕捉基于事件顺序而非计数的属性。
- 扩展： 该逻辑通过引入模运算谓词（用于追踪周期性位置）和后向计数算子（ $\overleftarrow{\#}$ ，用于分析计数发生次数的能力）进行了扩展。
构造性证明： 作者提供了构造性证明，展示如何将逻辑公式转化为 SSM 架构。他们展示了特定的时序算子（例如，昨天、先前、自从）和计数机制如何通过特定的门控结构和算术设置来实现。
不可能证明： 相反，本文利用单调性等属性，通过固定精度对角 SSMs 建立了不可表达性结果，证明了某些非星自由语言（例如 $(aa)^*$ ）无法被识别。

核心贡献

1. SSM 变体的表达能力层级

本文根据门控和精度建立了详细的 SSM 能力层级：

对角门控 SSM（固定精度）：
- 能力： 识别所有由 PLTLf 定义的语言（等价于星自由语言以及带序一阶逻辑，$FO[<]$）。
- 局限性： 无法识别非星自由语言（如 $(aa)^*$ ），因为其具有单调性属性，即重复的相同输入会导致状态趋于稳定。
对角门控 SSM（对数精度）：
- 能力： 识别 PLTLf[ $\overleftarrow{\#}$ ] 中的语言，通过后向计数将表达能力扩展到包括非正则甚至非上下文无关语言（例如 $\{a^n b^n c^n\}$ ）。
时不变 SSM（固定精度）：
- 能力： 识别 UN-PLTLf[MOD] 中的语言（带模运算谓词的一元 PLTLf）。它们可以使用循环置换矩阵来追踪周期性位置（例如，区分奇偶索引），从而能够识别 $(aa)^*$ 。
- 局限性： 推测无法识别需要 Since 算子的语言（例如 $L(a \mathcal{S} b)$ ），因为它们缺乏输入依赖型门控来动态结合当前信息与过去信息。
混合 SSM（对角 + 时不变）：
- 能力： 识别 PLTLf[MOD]，有效地捕捉了对角和时不变能力的并集。这对应于 $AC^0$ 中的正则语言类。
- 对数精度扩展： 结合对数精度，它们可以识别 PLTLf[ $\overleftarrow{\#}$ , MOD]。

2. 算术精度是关键决定因素

本文严谨地证明了对数精度对于识别非正则计数语言是严格必要的。固定宽度算术将 SSMs 限制在正则（或星自由）语言内，而对数精度则使得累积计数成为可能，从而能够处理如 $a^n b^n c^n$ 之类的语言。

3. 与 Transformer 的系统性比较

作者将 SSM 变体直接映射到已知的 Transformer 表达能力结果：

对角 SSM (固定精度) $\approx$ 无位置编码的唯一硬注意力 Transformer (UHAT)（两者均捕捉 $FO[<]$）。
时不变 SSM $\approx$ 带位置编码的 UHAT (UHAT+PE)（两者均捕捉 $FO[<, MOD]$）。
混合 SSM (对数精度) $\approx$ 平均硬注意力 Transformer (AHAT)（两者均捕捉计数能力，尽管 SSMs 仅限于后向计数）。
任意门控： 具有任意门控的 SSMs 可以识别所有正则语言，达到了更复杂 Transformer 变体的上限。

关键结果

定理 1： 固定精度的对角 SSMs 识别所有 PLTLf 中的语言。
定理 3： 固定精度的对角 SSMs 无法识别 $(aa)^*$ ，证明了其在这一方面与时不变 SSMs 存在严格分离。
定理 4： 对数精度的对角 SSMs 识别所有 PLTLf[ $\overleftarrow{\#}$ ] 中的语言。
定理 7： 固定精度的时不变 SSMs 识别所有 UN-PLTLf[MOD] 中的语言。
推论 8： 固定精度的混合 SSMs 识别所有 $AC^0$ 中的正则语言。
不可能结论： 本文提供的不可行性证明表明，特定的架构选择（例如，对角固定精度）会产生根本性的瓶颈，这是任何训练数据或优化都无法克服的。

意义与主张

本文声称提供了连接 SSM 表达能力与形式逻辑的首次联系，为特定 SSM 变体能够学习哪些模式或哪些模式在理论上是不可学习的提供了结构性保证。

基础洞察： 通过划定“不可能”的任务（例如，固定精度对角 SSMs 的非单调模式），这项工作通过识别独立于训练动态的架构极限，补充了经验基准测试。
架构清晰度： 结果阐明了 SSMs 与 Transformer 之间的关系，表明 SSMs 通过递归本质上编码了位置信息（类似于 Transformer 中的位置编码），但在计数机制上有所不同（后向计数 vs 全局注意力）。
复杂度对齐： 研究结果表明，受限的 SSMs（对角/时不变且固定精度）很可能运行在 $AC^0$ 内，这是 Merrill 等人 (2024) 之前确立的 $TC^0$ 上界的一个真子集。这意味着如果没有特定的修改，这些架构可能无法识别奇偶校验（parity）或其他超出 $AC^0$ 范围的语言。

作者总结道，他们的工作建立了一个严谨的理论基准，揭示了门控机制和算术精度的选择从根本上决定了 SSM 所能建模的语言类别，而无论使用何种具体的训练程序。