跳转至

多层状态空间模型（SSM）的表达能力与局限性

文章背景与核心概要

本文深入探讨了架构深度、有限精度、状态维度以及思维链（CoT）推理机制如何影响多层状态空间模型（SSM）的表达能力。以显式表 \(K\) 函数复合问题作为规范基准，作者建立了模型容量相对于深度的下界，并展示了不同的推理范式（如输入后推理与输入交织推理）如何改变模型的性能和内存模拟极限。

这项研究对于理解现代序列建模架构（尤其是状态空间模型）的理论边界具有重要意义。通过对计算复杂度、精度与模型深度的精细化数学分析，该论文为未来更高效、更具表达能力的架构设计提供了重要的理论指导。

论文元数据 (Paper Metadata)

  • arXiv ID: arXiv:2604.14501 [cs.LG]
  • 期刊参考: Transactions on Machine Learning Research (TMLR), 2026
  • 作者:
  • Nikola Zubić
  • Qian Li
  • Yuyi Wang
  • Davide Scaramuzza
  • 提交历史:
  • 提交于 2026年4月16日
  • 最后修订于 2026年9月2日 (v2)

摘要 (Abstract)

我们研究了深度、有限精度、状态维度和思维链（CoT）如何影响多层状态空间模型（SSM）的表达能力。对于作为序列信息传播规范基准的显式表 \(K\) 函数复合问题，我们证明了任何求解 \((L+3)\) 函数复合的 \(L\) 层 SSM 必须满足 \(d^2p=\Omega(N/L^3)\)，其中 \(d\) 是状态维度， \(p\) 是每个标量的精度。相反， \(K\) 函数复合可以通过一个具有 \(d=1\) 和 \(p=\Theta(\log N)\) 的 \((K+1)\) 层广义 SSM 精确求解。这为该形式化问题族提供了最坏情况下的深度层级。接着，我们区分了输入后推理（所有思考词元都在输入之后生成）与输入交织推理（在读取输入流的同时可以插入思考词元）。输入后推理无法绕过我们基于通信的下界证明流程，而输入交织推理则允许以持久内存的粒度与一般的确定性单遍流算法进行双向模拟。最后，在基础仿射状态模型中，宽度和精度在精确保持步数的模拟下是不可互换的，但一旦允许输入交织推理，它们就可以通过流式内存特征进行互换。

We study how depth, finite precision, state dimension, and chain-of-thought (CoT) affect the expressive power of multi-layer state-space models (SSMs). For the explicit-table \(K\)-function-composition problem, a canonical benchmark for sequential information propagation, we prove that any \(L\)-layer SSM solving \((L+3)\)-function composition must satisfy \(d^2p=\Omega(N/L^3)\), where \(d\) is the state dimension and \(p\) is the per-scalar precision. Conversely, \(K\)-function composition is solved exactly by a \((K+1)\)-layer generalized SSM with \(d=1\) and \(p=\Theta(\log N)\). This gives a worst-case depth hierarchy for this formal problem family. We then distinguish post-input reasoning, in which all thought tokens are generated after the input, from input-interleaved reasoning, in which thought tokens may be inserted while the input stream is being read. Post-input reasoning does not circumvent our communication-based lower-bound pipeline, whereas input-interleaved reasoning admits bidirectional simulations with general deterministic one-pass streaming algorithms at the granularity of persistent memory. Finally, width and precision are not interchangeable under exact step-preserving simulation in the base affine-state model, but become interchangeable through the streaming-memory characterization once input-interleaved reasoning is allowed.

核心发现与亮点 (Key Findings & Highlights)

  1. 深度层级与复杂度边界： 对于 \(K\) 函数复合问题， \(L\) 层 SSM 需要在状态维度 \(d\) 和精度 \(p\) 之间进行权衡，其特征为 \(d^2p=\Omega(N/L^3)\)。

    Depth Hierarchy & Complexity Bounds: For the \(K\)-function-composition problem, an \(L\)-layer SSM requires a trade-off between state dimension \(d\) and precision \(p\) characterized by \(d^2p=\Omega(N/L^3)\).

  2. 广义 SSM 的效率： 使用具有最小状态维度（\(d=1\)）和对数精度（\(p=\Theta(\log N)\)）的 \((K+1)\) 层广义 SSM，可以实现对 \(K\) 函数复合的精确求解。

    Generalized SSM Efficiency: Exact solutions to \(K\)-function composition are achievable using a \((K+1)\)-layer generalized SSM with minimal state dimension (\(d=1\)) and logarithmic precision (\(p=\Theta(\log N)\)).

  3. 推理范式：

  4. 输入后推理（严格在输入之后生成思考词元）仍然受到基于通信的下界限制。

  5. 输入交织推理（在输入摄入过程中动态插入思考词元）支持与一般的确定性单遍流算法进行双向模拟。

    Reasoning Paradigms: * Post-input reasoning (generating thought tokens strictly after the input) remains bounded by communication-based lower bounds. * Input-interleaved reasoning (inserting thought tokens dynamically during input ingestion) enables bidirectional simulations with general deterministic one-pass streaming algorithms.

  6. 宽度与精度的对比： 尽管在基础仿射状态模型中，宽度和精度在精确保持步数的模拟下是不可互换的，但当允许输入交织推理时，它们在流式内存特征下变得可互换。

    Width vs. Precision: While width and precision are not interchangeable under exact step-preserving simulations in base affine-state models, they become interchangeable under streaming-memory characterizations when input-interleaved reasoning is permitted.