arXiv cs.AI· Nikola Zubi\'c, Qian Li, Yuyi Wang, Davide Scaramuzza·· 13 小时前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-函数复合，给出该形式问题族的最坏情况深度层级。研究进一步区分输入后推理与输入交错推理：前者无法绕开基于通信的下界，后者在持久内存粒度上可与通用确定性单遍流式算法双向模拟。
正文 · 原文
Abstract: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.
| Comments: | 29 pages |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC) |
| Cite as: | arXiv:2604.14501 [cs.LG] |
| (or arXiv:2604.14501v3 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2604.14501 arXiv-issued DOI via DataCite |
|
| Journal reference: | Transactions on Machine Learning Research (TMLR) and NeurIPS, 2026 |
Submission history
From: Nikola Zubić [view email]
[v1]
Thu, 16 Apr 2026 00:30:45 UTC (46 KB)
[v2]
Wed, 2 Sep 2026 17:30:53 UTC (53 KB)
[v3]
Wed, 21 Oct 2026 16:15:07 UTC (54 KB)
来源：arXiv cs.AI · arxiv.org