On the Expressive Power and Limitations of Multi-Layer SSMs

Nikola Zubić, Qian Li, Yuyi Wang +1

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$-f…