mlsanityData to 7 Oct 2026

On the Expressive Power and Limitations of Multi-Layer SSMs

arXiv 2604.14501 ↗First posted 16 Apr 2026cs.LG cs.AI cs.CCcited by 1

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

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-function-composition problem, a canonical benchmark for sequential information propagation, we prove that any L-layer SSM solving (L+3)-function composition must satisfy d2p=Omega(N/L3), where d is the state dimension and p is the per-scalar precision. Conversely, K-function composition is solved exactly by a (K+1)-layer generalized SSM with d=1 and p=Theta(log N). This gives a worst-case depth hierarchy for this formal problem family. We then distinguish post-input reasoning, in which all thought tokens are generated after the input, from input-interleaved reasoning, in which thought tokens may be inserted while the input stream is being read. Post-input reasoning does not circumvent our communication-based lower-bound pipeline, whereas input-interleaved reasoning admits bidirectional simulations with general deterministic one-pass streaming algorithms at the granularity of persistent memory. Finally, width and precision are not interchangeable under exact step-preserving simulation in the base affine-state model, but become interchangeable through the streaming-memory characterization once input-interleaved reasoning is allowed.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 31 of its 47 references that are in the map. First posted on arXiv 16 Apr 2026.

Builds on

31 of 47 references.

Closest ancestors · 1

Same direction, newest first

  1. 2023Think before you speak: Training Language Models With Pause Tokens3 Oct

Other references · 30

  1. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  2. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
  3. 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,424
  4. 2024Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Dualitycited by 1,283
  5. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  6. 2023RWKV: Reinventing RNNs for the Transformer Eracited by 814
  7. 2022Simplified State Space Layers for Sequence Modelingcited by 776
  8. 2023Resurrecting Recurrent Neural Networks for Long Sequencescited by 397
  9. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  10. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  11. 2016Benefits of depth in neural networkscited by 248
  12. 2022Neural Networks and the Chomsky Hierarchycited by 214
18 more
  1. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 208
  2. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  3. 2023Zoology: Measuring and Improving Recall in Efficient Language Modelscited by 188
  4. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 184
  5. 2024The Illusion of State in State-Space Modelscited by 181
  6. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  7. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  8. 2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
  9. 2024Theoretical Foundations of Deep Selective State-Space Modelscited by 73
  10. 2024RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrievalcited by 62
  11. 2020A Formal Hierarchy of RNN Architecturescited by 61
  12. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  13. 2024Theoretical limitations of multi-layer Transformercited by 43
  14. 2024Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theorycited by 19
  15. 2024S7: Selective and Simplified State Space Layers for Sequence Modelingcited by 17
  16. 2025Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalizationcited by 12
  17. 2024GG-SSMs: Graph-Generating State Space Modelscited by 3
  18. 2025Regularity and Stability Properties of Selective SSMs with Discontinuous Gatingcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?cited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026On the Expressiveness of State Space Models via Temporal Logics
  2. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
  3. 2026The Expressive Limits of Diagonal SSMs for State-Tracking
  4. 2026The Complexity Ceiling Benchmark: A Multi-Domain Evaluation of Sequential Reasoning Under Depth Scaling
  5. 2024Transformers Provably Solve Parity Efficiently with Chain of Thought
  6. 2026Grounding LLM Reasoning under Incomplete Graph Evidence
  7. 2025The Computational Complexity of Satisfiability in State Space Models
  8. 2024On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages