arXiv:2412.06148v2 通知类型: replace-cross 摘要: 在本文中，我们通过使用电路复杂性框架来分析 Mamba 和状态空间模型（SSMs）的计算限制。尽管 Mamba 具有状态设计，并且近期被认为是超越变换器的强大候选者，但我们已经证明，无论是具有 $\mathrm{poly}(n)$ 精度和常数深度层的 Mamba 还是 SSMs，都局限于 $\mathsf{DLOGTIME}$-统一的 $\mathsf{TC}^0$ 复杂性类。这个结果表明，从理论上讲，Mamba 与变换器具有相同的计算能力，并且如果 $\mathsf{TC}^0 \neq \mathsf{NC}^1$，Mamba 无法解决算术公式问题、布尔公式值问题和排列合成问题。因此，这挑战了 Mamba 在计算表达能力上优于变换器的假设。我们的贡献包括严格的证明，表明选择性 SSM 和 Mamba 架构可以由 $\mathsf{DLOGTIME}$-统一的 $\mathsf{TC}^0$ 电路模拟，并且它们无法解决 $\mathsf{TC}^0$ 之外的问题。