Research map / Large language models / Reasoning and chain of thought

On the Expressive Power and Limitations of Multi-Layer SSMs

NeurIPS 2026 · Large language models › Reasoning and chain of thought · approach: Theory of autoregressive reasoning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves a communication-based lower bound d^2p=Omega(N/L^3) for L-layer SSMs on (L+3)-function composition, an O(log N)-memory construction for K-fold composition with K+1 layers, and analyzes how CoT timing and width/precision trade off.

Problem

Expressive power of multi-layer state-space models: how depth, finite precision, state dimension and chain-of-thought affect solving K-function composition and width/precision tradeoffs.

Approach

Reduces L-layer SSM computation to an L-round forward communication protocol (affine block summaries of size O(d^2 p)) and applies pointer-chasing lower bounds; distinguishes offline (post-input) from online (input-interleaved) CoT, showing online CoT makes generalized SSMs equivalent to one-pass streaming with persistent memory.

Key results

• Any L-layer SSM solving (L+3)-function composition must satisfy d^2 p = Omega(N/L^3) under the blockwise explicit-table encoding.
• K-function composition is solved exactly by a (K+1)-layer generalized SSM with d=1 and p=Theta(log N), so dp=O(log N).
• Width and precision are not interchangeable in the base affine-state model (counting and order-8 affine permutation arguments), but online CoT makes total persistent memory the invariant.

Surprising findings

• Post-input CoT provides no benefit against the communication lower bound pipeline.
• Single-layer online-CoT generalized SSM solves arbitrary-length function composition with dp=O(log N) using one thought token per input token.

Limitations

• Results are worst-case expressiveness for explicit-table encoded problems and generalized SSMs, not learnability.
• Upper-bound constructions use hand-designed, non-structured transition and readout maps not realizable by S4/Mamba.
• Lower bound may not transfer to other compositional tasks without resource-preserving reductions.

Experimental setup

Metrics: theoretical bounds

Builds on: pointer chasing lower bound Mamba S4 chain-of-thought

Closest papers by meaning

• Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory (ICLR 2025 · similarity 0.87)
• The Expressive Capacity of State Space Models: A Formal Language Perspective (NeurIPS 2024 · similarity 0.86)
• On the Expressiveness and Length Generalization of Selective State Space Models on Regular Languages (AAAI 2025 · similarity 0.86)
• Transformers Provably Solve Parity Efficiently with Chain of Thought (ICLR 2025 · similarity 0.86)
• Lost in Transmission: When and Why LLMs Fail to Reason Globally (NeurIPS 2025 · similarity 0.86)
• Theoretical Foundations of Deep Selective State-Space Models (NeurIPS 2024 · similarity 0.86)