关于多层 SSM 的表达能力和局限性

我们研究深度、有限精度、状态维度和思想链 (CoT) 如何影响多层状态空间模型 (SSM) 的表达能力。对于显式表 $K$ 函数组合问题（顺序信息传播的规范基准），我们证明任何求解 $(L+3)$ 函数组合的 $L$ 层 SSM 必须满足 $d^2p=Ω(N/L^3)$，其中 $d$ 是状态维度，$p$ 是每标量精度。相反，$K$ 函数组合可以通过 $d=1$ 和 $p=θ(\log N)$ 的 $(K+1)$ 层广义 SSM 精确求解。这给出了该正式问题族的最坏情况深度层次结构。然后，我们将输入后推理与输入交错推理区分开来，在输入后推理中，所有思想标记都是在输入之后生成的，在输入交错推理中，思想标记可以在读取输入流时插入。输入后推理不会绕过我们基于通信的下界管道，而输入交错推理允许在持久内存的粒度上使用通用确定性单通道流算法进行双向模拟。最后，在基本仿射状态模型中的精确保步模拟下，宽度和精度不可互换，但一旦允许输入交错推理，则通过流内存表征可以互换。