arXiv cs.AI· Nikola Zubi\'c, Qian Li, Yuyi Wang, Davide Scaramuzza·· 12 小时前AI 评分31
多层 SSM 的表达能力与局限研究
On the Expressive Power and Limitations of Multi-Layer SSMs
AI 导读
研究证明，任意 L 层 SSM 求解 (L+3)-函数复合必须满足 d²p=Ω(N/L³)，其中 d 为状态维度、p 为单标量精度；而 (K+1) 层广义 SSM 在 d=1、p=Θ(log N) 时可精确求解 K-函数复合，给出该形式问题族的最坏情况深度层级。研究进一步区分输入后推理与输入交错推理：前者无法绕开基于通信的下界，后者在持久内存粒度上可与通用确定性单遍流式算法双向模拟。
正文 · AI 翻译
摘要：我们研究深度、有限精度、状态维度与思维链（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 精确求解。这为该形式问题族给出了最坏情况下的深度层级。随后我们区分了输入后推理与输入交错推理：前者所有思维 token 均在输入之后生成，后者允许在读取输入流的过程中插入思维 token。输入后推理无法绕过我们基于通信的下界论证流程，而输入交错推理在持久内存粒度上允许与一般确定性单遍流式算法进行双向模拟。最后，在基础仿射状态模型下，宽度与精度在精确保步模拟下不可互换，但一旦允许输入交错推理，通过流式内存刻画二者便可互换。
| 评论： | 29 页 |
| 主题： | 机器学习（cs.LG）；人工智能（cs.AI）；计算复杂性（cs.CC） |
| 引用为： | arXiv:2604.14501 [cs.LG] |
| （或 arXiv:2604.14501v3 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2604.14501 由 DataCite 颁发的 arXiv DOI |
|
| 期刊 参考： | Transactions on Machine Learning Research (TMLR) and NeurIPS, 2026 |
提交历史
来自：Nikola Zubić [查看邮箱]
[v1]
2026 年 4 月 16 日星期四 00:30:45 UTC（46 KB）
[v2]
2026 年 9 月 2 日星期三 17:30:53 UTC（53 KB）
[v3]
2026 年 10 月 21 日星期三 16:15:07 UTC（54 KB）
来源：arXiv cs.AI · arxiv.org