Mamba Hits a Hard Ceiling and Only Interleaved Thinking Breaks It
New theory pins down exactly how depth, precision, and chain-of-thought shape what state-space models like Mamba can and cannot compute.
Takeaways
- New paper proves L-layer SSMs need d²p = Ω(N/L³) to solve (L+3)-function composition, via communication complexity reduction.
- Constant-gap depth hierarchy: (L+4) layers solve the task with dp = O(log N), but L layers provably cannot.
- Offline chain-of-thought (thinking after input) does not circumvent the lower bound; it is just local post-processing.
- Online chain-of-thought (interleaved thought tokens) makes SSMs equivalent to one-pass streaming algorithms in both directions.
- Width and precision are not interchangeable in the base model; matrix transitions are strictly richer than scalar ones with equal bits.
- Under online CoT the non-interchangeability vanishes and total persistent memory Lwp becomes the only relevant invariant.
State-space models have become the leading efficient alternative to transformers, with architectures like Mamba matching transformer quality on language modeling while offering linear-time inference. A new theoretical paper draws hard limits around what stacking these layers can actually compute, and shows that breaking those limits depends less on depth than on where in the input stream the model is allowed to think.
The paper, On the Expressive Power and Limitations of Multi-Layer SSMs, gives a unified picture of how three resources interact in modern SSMs: layer depth, finite numerical precision, and chain-of-thought (CoT). The authors organize the analysis around compositional lower bounds, the role of CoT, and width-precision tradeoffs.
Putting a number on the state-tracking ceiling
Prior work already knew SSMs had a ceiling. Merrill, Petty and Sabharwal showed that these models cannot express computation outside the complexity class TC0, meaning they fail on simple state-tracking problems like permutation composition. That result placed Mamba and S4 on similar footing to transformers, but it was mostly asymptotic and said little about how big the model needs to be to solve a task of a given size.
This new work is quantitative. The benchmark task is K-function composition: given a starting value a and K functions f_1,...,f_K encoded in the input stream, output f_K(...f_1(a)...). It is the natural sequential-depth stress test.
The main lower bound: any L-layer SSM solving the (L+3)-function composition problem must satisfy d²p = Ω(N/L³), where d is the state dimension, p is the per-scalar precision, and N is the problem size. To compose just three more functions than you have layers, either state or precision has to grow polynomially in the domain size.