On the Expressive Power and Limitations of Multi-Layer SSMs

arXiv cs.LG / 4/17/2026

📰 NewsIdeas & Deep AnalysisModels & Research

共有:

Key Points

The paper studies how multi-layer state-space models (SSMs) differ from streaming models in compositional tasks, identifying a fundamental expressiveness gap.
It analyzes the effect of chain-of-thought (CoT), finding that offline CoT does not fundamentally increase expressiveness, while online CoT can substantially boost it.
With online CoT, multi-layer SSMs are shown to be equivalent in power to streaming algorithms for the considered setting.
The authors explore the width–precision tradeoff, concluding that width and precision are not interchangeable in the base model but become cleanly equivalent when online CoT is permitted.
The work provides a unified framework describing how depth, finite precision, and CoT collectively determine what SSMs can and cannot do.

Abstract

We study the expressive power and limitations of multi-layer state-space models (SSMs). First, we show that multi-layer SSMs face fundamental limitations in compositional tasks, revealing an inherent gap between SSMs and streaming models. Then, we examine the role of chain-of-thought (CoT), showing that offline CoT does not fundamentally increase the expressiveness, while online CoT can substantially increase its power. Indeed, with online CoT, multi-layer SSMs become equivalent in power to streaming algorithms. Finally, we investigate the tradeoff between width and precision, showing that these resources are not interchangeable in the base model, but admit a clean equivalence once online CoT is allowed. Overall, our results offer a unified perspective on how depth, finite precision, and CoT shape the power and limits of SSMs.