mlsanityData to 7 Oct 2026

The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity

arXiv 2412.06148 ↗First posted 9 Dec 2024cs.CC cs.AI cs.CLcited by 21

On the map: State-space sequence models (S4, Mamba) → Core SSM architectures for language

Abstract (arXiv)

In this paper, we analyze the computational limitations of Mamba and State-space Models (SSMs) by using the circuit complexity framework. Despite Mamba's stateful design and recent attention as a strong candidate to outperform Transformers, we have demonstrated that both Mamba and SSMs with poly(n)-precision and constant-depth layers reside within the mathsfDLOGTIME-uniform mathsfTC0 complexity class. This result indicates Mamba has the same computational capabilities as Transformer theoretically, and it cannot solve problems like arithmetic formula problems, boolean formula value problems, and permutation composition problems if mathsfTC0 neq mathsfNC1. Therefore, it challenges the assumption Mamba is more computationally expressive than Transformers. Our contributions include rigorous proofs showing that Selective SSM and Mamba architectures can be simulated by mathsfDLOGTIME-uniform mathsfTC0 circuits, and they cannot solve problems outside mathsfTC0.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Placed in Core SSM architectures for language, one of 10 directions in State-space sequence models (S4, Mamba). Builds on 82 of its 122 references that are in the map. First posted on arXiv 9 Dec 2024.

Builds on

82 of 122 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality31 May
  2. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spaces1 Dec
  3. 2021Efficiently Modeling Long Sequences with Structured State Spaces31 Oct

Other references · 79

  1. 2017Attention Is All You Needcited by 59,932
  2. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,016
  3. 2014Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modelingcited by 2,341
  4. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  5. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  6. 2022Transformers Learn Shortcuts to Automatacited by 260
  7. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  8. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  9. 2024The Illusion of State in State-Space Modelscited by 181
  10. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  11. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  12. 2024Is A Picture Worth A Thousand Words? Delving Into Spatial Reasoning for Vision Language Modelscited by 111
38 more
  1. 2023Fast Attention Requires Bounded Entriescited by 102
  2. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  3. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65
  4. 2023An Over-parameterized Exponential Regressioncited by 45
  5. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  6. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  7. 2023On Sparse Modern Hopfield Modelcited by 41
  8. 2024On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysiscited by 41
  9. 2024On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)cited by 39
  10. 2024Discovering the Gems in Early Layers: Accelerating Long-Context LLMs with 1000x Input Token Reductioncited by 39
  11. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  12. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  13. 2023STanHop: Sparse Tandem Hopfield Model for Memory-Enhanced Time Series Predictioncited by 35
  14. 2023In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trickcited by 32
  15. 2024Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformerscited by 32
  16. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  17. 2024Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscited by 31
  18. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  19. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  20. 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 29
  21. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  22. 2024Transformers in Uniform TC0cited by 25
  23. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  24. 2024Mamba4Rec: Towards Efficient Sequential Recommendation with Selective State Space Modelscited by 23
  25. 2024Fourier Circuits in Neural Networks and Transformers: A Case Study of Modular Arithmetic with Multiple Inputscited by 22
  26. 2024Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Timecited by 22
  27. 2024BiSHop: Bi-Directional Cellular Learning for Tabular Data with Generalized Sparse Modern Hopfield Modelcited by 21
  28. 2024Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descentcited by 21
  29. 2024On Statistical Rates of Conditional Diffusion Transformers: Approximation, Estimation and Minimax Optimalitycited by 21
  30. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  31. 2024Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrixcited by 20
  32. 2022Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimationcited by 19
  33. 2024Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theorycited by 19
  34. 2024A Tighter Complexity Analysis of SparseGPTcited by 19
  35. 2024Looped ReLU MLPs May Be All You Need as Practical Programmable Computerscited by 19
  36. 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
  37. 2023Zero-th Order Algorithm for Softmax Attention Optimizationcited by 16
  38. 2021Sample Complexity of Learning Parametric Quantum Circuitscited by 15

50 most cited of 79 All 79 (JSON)

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 20.

21 papers.

Sort:

By area:

  1. 2025Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Countingcited by 17
  2. 2025High-Order Matching for One-Step Shortcut Diffusion Modelscited by 15
  3. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  4. 2025The Serial Scaling Hypothesiscited by 11
  5. 2025Circuit Complexity Bounds for Visual Autoregressive Modelcited by 10
  6. 2025On Computational Limits of FlowAR Models: Expressivity and Efficiencycited by 10
  7. 2025Theoretical Guarantees for High Order Trajectory Refinement in Generative Flowscited by 9
  8. 2025T2VTextBench: A Human Evaluation Benchmark for Textual Control in Video Generation Modelscited by 9
  9. 2025Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descentcited by 8
  10. 2025Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretrainingcited by 6
  11. 2025Automating Structural Engineering Workflows with Large Language Model Agentscited by 6
  12. 2025Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteriacited by 5
9 more
  1. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  2. 2025Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questionscited by 4
  3. 2025Neural Algorithmic Reasoning for Hypergraphs with Looped Transformerscited by 3
  4. 2025CoVE: Compressed Vocabulary Expansion Makes Better LLM-based Recommender Systemscited by 3
  5. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  6. 2025Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiencycited by 2
  7. 2025Reasoning Like an Economist: Post-Training on Economic Problems Induces Strategic Generalization in LLMscited by 2
  8. 2025ETT: Expanding the Long Context Understanding Capability of LLMs at Test-Timecited by 1
  9. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Attention to Mamba: A Recipe for Cross-Architecture Distillation
  2. 2025Constant Bit-size Transformers Are Turing Complete
  3. 2024MambaPEFT: Exploring Parameter-Efficient Fine-Tuning for Mamba
  4. 2025PerfMamba: Performance Analysis and Pruning of Selective State Space Models
  5. 2024Transformers to SSMs: Distilling Quadratic Knowledge to Subquadratic Models
  6. 2026Bilinear Input Modulation for Mamba: Koopman Bilinear Forms for Memory Retention and Multiplicative Computation
  7. 2025Efficient Turing Machine Simulation with Transformers
  8. 2026Learning Rate Transfer for Hybrid Transformer-SSM Architectures