Back

The Illusion of State in State-Space Models

William MerrillJackson PettyAshish Sabharwal

article2024ICML208 citations

Proves that popular state-space models like S4 and Mamba share the same fundamental expressive limitations as transformers for sequential state tracking, while identifying a minimal architectural modification to overcome this barrier.

Listen

State-space models, such as S4 and Mamba, have recently gained significant attention as potential alternatives to transformer architectures for foundation models. A central motivation for these architectures is their recurrent structure, which many believed would overcome the inability of transformers to perform sequential reasoning and track state changes over time. Because core capabilities such as tracking entities in long narratives, executing computer code, and tracking game states like chess depend fundamentally on sequential state tracking, determining whether these models genuinely offer superior state-tracking power is a critical question for machine learning system design.

The article evaluates the mathematical expressiveness and empirical capabilities of popular state-space models for state-tracking tasks. Specifically, it demonstrates whether standard state-space architectures can solve inherently sequential problems that standard recurrent neural networks can naturally handle.

To assess these capabilities, the analysis uses circuit complexity theory alongside formal algebraic language theory to classify the computational limits of fixed-depth state-space models using standard floating-point precision. The theoretical findings are evaluated through controlled empirical experiments comparing transformers, classic recurrent neural networks, and several state-space model variants on sequence-tagging tasks involving algebraic permutation composition across varying sequence lengths.

The findings establish that the recurrent "state" in common state-space models is an illusion with respect to computational expressiveness. First, non-gated models such as S4 and selective diagonal models such as Mamba belong to the same complexity class as transformers (L-uniform TC0), meaning they are provably unable to solve inherently sequential state-tracking problems such as permutation composition. Second, empirical tests confirm that both transformers and standard state-space models fail to maintain state across long sequences without scaling the number of layers linearly with sequence length. In contrast, standard recurrent neural networks solve these tasks across arbitrary lengths using a single layer. Third, the article demonstrates that modifying state-space models to use input-dependent, non-diagonal transition matrices restores full state-tracking capabilities, allowing a single layer to solve permutation tasks while preserving efficient parallel training.

These results demonstrate that switching from transformers to current state-space architectures will not resolve fundamental state-tracking limitations in tasks like multi-step reasoning, program execution, or narrative tracking. Deploying current state-space models in domains that require exact sequential state updates carries the operational risk of silent tracking failures unless input sequences are short or model depth is significantly increased. However, the success of input-dependent transition matrices indicates that the architectural design space can be expanded to achieve both expressiveness and computational efficiency.

Organizations evaluating alternative architectures should avoid selecting current state-space models solely under the assumption that they provide superior state tracking over transformers. Research and engineering teams should instead pilot more expressive variants, such as input-dependent state-space architectures, while monitoring training stability and hardware-level parallelism trade-offs before committing to large-scale deployment.

These conclusions assume standard fixed-depth architectures operating with realistic precision constraints and rely on established computational complexity separations. While confidence in the formal proofs and synthetic empirical results is high, further validation on full-scale language pretraining benchmarks is required to determine whether enhanced state-space architectures retain their advantages in broader real-world settings.

Allen Institute for AINew York Universitystate spacestate space modellinear dynamic systemState-space modelsMamba modelslinear SSMs
arXiv: 2404.08819
Cover for The Illusion of State in State-Space Models

Abstract

State-space models (SSMs) have emerged as a potential alternative to transformers. One theoretical weakness of transformers is that they cannot express certain kinds of sequential computation and state tracking (Merrill & Sabharwal, 2023a), which SSMs are explicitly designed to address via their close architectural similarity to recurrent neural networks. But do SSMs truly have an advantage (over transformers) in expressive power for state tracking? Surprisingly, the answer is no. Our analysis reveals that the expressive power of S4, Mamba, and related SSMs is limited very similarly to transformers (within TC⁰), meaning these SSMs cannot solve simple state-tracking problems like permutation composition and consequently are provably unable to accurately track chess moves with certain notation, evaluate code, or track entities in a long narrative. To supplement our formal analysis, we report experiments showing that S4 and Mamba indeed struggle with state tracking. Thus, despite their recurrent formulation, the “state” in common SSMs is an illusion: S4, Mamba, and related models have similar expressiveness limitations to non-recurrent models like transformers, which may fundamentally limit their ability to solve real-world state-tracking problems. Moreover, we show that only a minimal change allows SSMs to express and learn state tracking, motivating the development of new, more expressive SSM architectures.

Topics

state spacestate space modellinear dynamic system

Keywords

State-space modelsMamba modelslinear SSMsdiagonalizable SSMsinput-dependent discretizationformal languagesfinite automatonexpressive powerTC0 computation

Table of Contents

  • 1. Introduction
  • 2. Background
  • 2.1. Architecture of State-Space Models
  • 2.2. Numeric Datatype
  • 2.3. Limits of Transformers via Circuit Complexity
  • 3. State Tracking
  • 3.1. State Tracking as a Monoid Word Problem
  • 3.2. Encoding S5 in Chess State Tracking
  • 4. SSMs Can be Simulated in TC0
  • 4.1. Conditions for Linear SSMs in TC0
  • 4.2. Non-Gated SSMs are in TC0
  • 4.3. Diagonal SSMs are in TC0
  • 4.4. Discussion
  • 5. Extending the Expressive Power of SSMs
  • 5.1. Via Nonlinearities
  • 5.2. Via Input-Dependent Transition Matrices
  • 5.3. Discussion
  • 6. Can SSMs Learn Permutations in Practice?
  • 7. Conclusion
  • Impact Statement
  • Acknowledgments
  • References
  • A. Floating-Point Arithmetic
  • A.1. Complexity of Iterated Scalar Multiplication
  • A.2. Complexity of Matrix Powering
  • A.3. L-Uniformity of Polynomial Division in TC0
  • B. S6 Parameterization
  • C. Diagonalizable SSMs
  • C.1. Diagonalizable S6
  • D. Nonlinearities in L-Uniform TC0

Knowls

  1. Knowl 1 — Bounded-depth S4 and Mamba-style SSMs are limited to TC0

    theoretical result

    For log-precision generalized linear SSMs with a fixed number of layers, the paper places the convolutional computation of non-gated SSMs and diagonal-transition SSMs in L-uniform TC0. The non-gated case includes S4; the diagonal, input-dependent-transition case includes S6 as used by Mamba. The result also covers simultaneously diagonalizable transition matrices under the paper’s stated conditions. It applies when the convolutional form represents the same function as the recurrent form, up to negligible floating-point discrepancies. Consequently, assuming TC0 ≠ NC1, bounded-depth models in these classes cannot solve the S5 permutation word problem or other NC1-hard problems. This is a worst-case expressivity limitation; it does not assert that every practical state-tracking instance is hard.

  2. Knowl 2 — Generalized linear SSM layer

    definition

    For an input sequence x1,…,xnx_1,\ldots,x_n with xi∈Rkx_i\in\mathbb{R}^k, a generalized linear SSM layer has hidden states hi∈Rdh_i\in\mathbb{R}^d. Its recurrent update and output are

    hi=Aˉihi−1+Bˉixi,yi=Cihi+Dixi,h_i=\bar A_i h_{i-1}+\bar B_i x_i,\qquad y_i=C_i h_i+D_i x_i,

    where Aˉi∈Rd×d\bar A_i\in\mathbb{R}^{d\times d}, Bˉi∈Rd×k\bar B_i\in\mathbb{R}^{d\times k}, Ci∈Rk×dC_i\in\mathbb{R}^{k\times d}, and Di∈Rk×kD_i\in\mathbb{R}^{k\times k}. The matrices may depend on the current input token xix_i; the convolutional expression below assumes h0=0h_0=0 and computes the same states by summing contributions from earlier inputs:

    hi=∑j=1i(AˉiAˉi−1⋯Aˉj+1)Bˉjxj,h_i=\sum_{j=1}^{i}\left(\bar A_i\bar A_{i-1}\cdots\bar A_{j+1}\right)\bar B_jx_j,

    where the matrix product is the identity when j=ij=i. A generalized linear SSM model can stack such layers with linear projections and nonlinearities between layers.

  3. Knowl 3 — Input-dependent S4 can express every regular-language word problem

    theoretical result

    For every regular language L⊆Σ∗L\subseteq\Sigma^*, including the word problem for S5S_5, the paper proves that a one-layer log-precision IDS4 SSM can recognize LL when its input includes a special beginning-of-string symbol $\$ followed by the word. IDS4 can represent the transition function of a deterministic finite automaton (DFA) as a matrix for each token. The hidden state encodes the DFA state, and the product of the token matrices composes the DFA transitions; the final state therefore determines acceptance. This construction gives IDS4 expressive power beyond TC0, unlike the fixed-transition and diagonal-transition SSM classes analyzed in the paper.

  4. Knowl 4 — Circuit-simulation criterion for generalized linear SSMs

    theoretical result

    A log-precision generalized linear SSM layer has an L-uniform TC0 simulation if both of the following computations have L-uniform TC0 circuits: (1) for every input interval [j,k][j,k], the ordered transition product Aˉk⋯Aˉj\bar A_k\cdots\bar A_j, as a function of the matrices in that interval, to the required log precision; and (2) each token-dependent matrix Aˉi,Bˉi,Ci,Di\bar A_i,\bar B_i,C_i,D_i, as a function of xix_i. Given these conditions, the layer’s convolutional form can be computed by forming transition products, applying them to the input contributions, summing those contributions, and computing the outputs. The criterion presumes that the remaining fixed-depth layer operations are also TC0-computable.

  5. Knowl 5 — Permutation composition captures hard finite-state tracking

    theoretical result

    A state-tracking task over a finite set of updates can be represented as a word problem: each update is an element of a finite group or monoid, and the final state is obtained by multiplying the sequence of elements. The word problem for the symmetric group S5S_5—composition of permutations of five objects—is NC1-complete. More generally, the paper uses the result that the word problem of every finite non-solvable group is NC1-complete; the alternating group A5A_5 is a non-solvable group used for the experiments. Thus, solving arbitrary sequences of these updates requires a computation beyond TC0 if TC0 ≠ NC1.

  6. Knowl 6 — IDS4 makes the transition matrix depend on the current token

    model/method

    Input-Dependent S4 (IDS4) is a generalized linear SSM in which an affine map πA:Rk→Rd×d\pi_A:\mathbb{R}^k\to\mathbb{R}^{d\times d} generates a full transition matrix from each token: Aˉi=πA(xi)\bar A_i=\pi_A(x_i). The input and state dimensions are kk and dd, respectively; the input projection is interpreted as a d×dd\times d matrix. The matrices Bˉ\bar B, CC, and DD are fixed across positions. Its hidden state therefore combines token-specific, generally non-diagonal transition matrices through the SSM recurrence, rather than relying only on a fixed transition or diagonal gating.

  7. Knowl 7 — Chess state tracking in UCI notation is NC1-complete

    theoretical result

    The paper defines chess state tracking in UCI notation as taking a board state and a sequence of moves, each given by a source and target square, and returning the board after applying the moves in order; if a move is illegal in the resulting position, the output is a null state. The task is NC1-complete under AC0 reductions. The hardness reduction maps each element of an S5S_5 permutation sequence to a fixed sequence of chess moves that performs the corresponding permutation of pieces. On the constructed board, the final location of a designated rook reveals whether the original first element returns to its initial position. The reduction uses UCI source-target notation and ignores draws; the paper does not establish the same hardness for standard chess notation.

  8. Knowl 8 — A recurrent nonlinearity also enables one-layer regular-language recognition

    model/method

    An RNN-SSM applies a nonlinearity at every recurrent update, rather than only after an SSM layer:

    hi=sgn⁡(Ahi−1+Bxi),h_i=\operatorname{sgn}(A h_{i-1}+B x_i),

    where xix_i is the current input vector, hih_i is the hidden state, AA and BB are learned matrices, and sgn⁡\operatorname{sgn} is applied coordinatewise. For any regular language L⊆Σ∗L\subseteq\Sigma^*, a one-layer log-precision RNN-SSM with input dimension k=∣Σ∣k=|\Sigma| can recognize LL, including the S5S_5 word problem. The token dimension allows distinct symbols to be represented by linearly independent vectors. Unlike the IDS4 construction, this recurrent nonlinearity does not retain the same straightforward parallelization by the SCAN algorithm used for linear SSMs.

  9. Knowl 9 — Permutation-word experiments compare five model families

    experimental setup

    The experiments train token-tagging models on word problems for three groups of size 60: the non-solvable group A5A_5, the non-abelian solvable group A4×Z5A_4\times\mathbb{Z}_5, and the abelian group Z60\mathbb{Z}_{60}. An input is a sequence of group elements, and the label at each position is the product of all elements up to that position. Each group element receives its own token. The models are a transformer, an RNN, S4, Mamba, and IDS4. Training is repeated for successively larger sequence lengths; all 3,600 ordered sequences of length 2 are included in training, along with the training split of sequences at the current length. The reported depth comparison is the minimum number of layers needed to exceed 90% validation accuracy as sequence length increases. IDS4’s affine transition projection is initialized around the identity, α(xi)∼I+N(0,σ2)\alpha(x_i)\sim I+\mathcal{N}(0,\sigma^2), to encourage transitions that initially propagate the previous state.

  10. Knowl 10 — RNN and IDS4 retain constant depth in the tested group tasks

    empirical result

    Across the tested sequence lengths and all three groups, single-layer RNN and IDS4 models attain the reported accuracy threshold. For the non-commutative groups A5A_5 and A4×Z5A_4\times\mathbb{Z}_5, transformer, S4, and Mamba models require increasing depth as sequences get longer. Transformers require at least as much depth as S4 or Mamba, and often more, for these tasks. The result for A4×Z5A_4\times\mathbb{Z}_5 is notable because its word problem is theoretically in TC0: the observed growth in depth could reflect limits of the particular architectures or difficulty learning a constant-depth solution, rather than a complexity-theoretic impossibility. The Z60\mathbb{Z}_{60} task is an easier, commutative comparison; the models generally remain shallower there.

  11. Knowl 11 — Log-precision arithmetic supports the SSM circuit bounds

    assumption

    The expressivity analysis uses log-precision floating-point arithmetic, with precision clog⁡nc\log n bits for a fixed constant cc and input length nn. The circuit arguments require efficient parallel computation of iterated addition, iterated multiplication, and fixed-dimension matrix powering. The paper establishes that these operations are in L-uniform TC0 for the log-precision arithmetic it analyzes; in particular, iterated products of scalars and powers of fixed-size matrices can be computed in this class. These arithmetic properties are what allow transition products and state-contribution sums to be assembled into the stated SSM simulations.

  12. Knowl 12 — Practical viability of the more expressive SSM extensions remains open

    limitation

    The paper establishes expressive power and reports permutation-learning experiments for IDS4, but it does not establish that IDS4 is viable for large-scale language modeling. An iterated product of input-dependent matrices may cause vanishing or exploding gradients; the paper raises this as a possible learning concern, not as an observed experimental result. IDS4’s matrix products could in principle be parallelized to logarithmic depth using a scan algorithm, whereas the paper considers parallelization of recurrent nonlinear updates less clear. The work therefore leaves open whether an architecture can combine practical parallelism with the additional state-tracking capacity.

Coverage note — Detailed proofs of the log-precision arithmetic and the S6 parameterization checks are omitted as proof-level support; their conclusions are captured in the simulation and arithmetic knowls.

References

  1. 1.Angluin, D., Chiang, D., and Yang, A. Masked hard-attention transformers and Boolean RASP recognize exactly the star-free languages, 2023. arXiv:2310.13897.
  2. 2.Barrington, D. A. Bounded-width polynomial-size branching programs recognize exactly those languages in nc1. Journal of Computer and System Sciences, 38(1):150–164, 1989. URL https://www.sciencedirect.com/science/article/pii/0022000089900378.
  3. 3.Blelloch, G. E. Prefix sums and their applications. Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University, November 1990.
  4. 4.Chiang, D., Cholak, P., and Pillay, A. Tighter bounds on the expressivity of transformer encoders. In ICML, 2023.
  5. 5.Feng, G., Zhang, B., Gu, Y., Ye, H., He, D., and Wang, L. Towards revealing the mystery behind chain of thought: A theoretical perspective. In NeurIPS, 2023.
  6. 6.Fu, D. Y., Dao, T., Saab, K. K., Thomas, A. W., Rudra, A., and Re, C. Hungry hungry hippos: Towards language modeling with state space models. In ICLR, 2023.
  7. 7.Gu, A. and Dao, T. Mamba: Linear-time sequence modeling with selective state spaces, 2023. arXiv:2312.00752.
  8. 8.Gu, A., Johnson, I., Goel, K., Saab, K. K., Dao, T., Rudra, A., and Re, C. Combining recurrent, convolutional, and continuous-time models with linear state space layers. In NeurIPS, 2021.
  9. 9.Gu, A., Goel, K., and Re, C. Efficiently modeling long sequences with structured state spaces. In ICLR, 2022a.
  10. 10.Gu, A., Goel, K., Saab, K., and Re, C. Structured state spaces: Combining continuous-time, recurrent, and convolutional models, January 2022b. URL https://hazyresearch.stanford.edu/blog/2022-01-14-s4-3. Blog post accessed January 31, 2024.
  11. 11.Hao, S., Angluin, D., and Frank, R. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. TACL, 10:800–810, 2022.
  12. 12.Hasani, R., Lechner, M., Wang, T.-H., Chahine, M., Amini, A., and Rus, D. Liquid structural state-space models. In ICLR, 2023.
  13. 13.Heim, I. File change semantics and the familiarity theory of definiteness. Semantics Critical Concepts in Linguistics, pp. 108–135, 1983.
  14. 14.Hesse, W. Division is in uniform T C0. In International Colloquium on Automata, Languages, and Programming, pp. 104–114, 2001.
  15. 15.Hesse, W., Allender, E., and Barrington, D. A. M. Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci., 65:695–716, 2002.
  16. 16.Hopcroft, J. E., Motwani, R., and Ullman, J. D. Introduction to automata theory, languages, and computation. ACM SIGACT News, 32(1):60–65, 2001.
  17. 17.Immerman, N. and Landau, S. The complexity of iterated multiplication. In [1989] Proceedings. Structure in Complexity Theory Fourth Annual Conference, pp. 104–111, 1989. doi: 10.1109/SCT.1989.41816.
  18. 18.Kim, N. and Schuster, S. Entity tracking in language models. In Rogers, A., Boyd-Graber, J., and Okazaki, N. (eds.), ACL, July 2023.
  19. 19.Krohn, K. and Rhodes, J. Algebraic theory of machines. i. prime decomposition theorem for finite semigroups and machines. Transactions of the American Mathematical Society, 116:450–464, 1965.
  20. 20.Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers learn shortcuts to automata. In ICLR, 2023.
  21. 21.Mereghetti, C. and Palano, B. Threshold circuits for iterated matrix product and powering. RAIRO-Theor. Inf. Appl., 34(1):39–46, 2000. doi: 10.1051/ita:2000105. URL https://doi.org/10.1051/ita:2000105.
  22. 22.Merrill, W. Sequential neural networks as automata. In Eisner, J., Galle, M., Heinz, J., Quattoni, A., and Rabusseau, G. (eds.), Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, Florence, August 2019. ACL.
  23. 23.Merrill, W. and Sabharwal, A. The parallelism tradeoff: Limitations of log-precision transformers. TACL, 11, 2023a.
  24. 24.Merrill, W. and Sabharwal, A. A logic for expressing log-precision transformers. In NeurIPS, 2023b.
  25. 25.Merrill, W. and Sabharwal, A. The expressive power of transformers with chain of thought. In ICLR, 2024.
  26. 26.Minsky, M. Neural nets and the brain-model problem. Unpublished doctoral dissertation, Princeton University, NJ, 1954.
  27. 27.Mohri, M. Weighted Automata Algorithms, pp. 213–254. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. ISBN 978-3-642-01492-5. doi: 10.1007/978-3-642-01492-5 6. URL https://doi.org/10.1007/978-3-642-01492-5_6.
  28. 28.Reif, J. H. and Tate, S. R. On threshold circuits and polynomial computation. SIAM Journal on Computing, 21(5):896–908, 1992. doi: 10.1137/0221053. URL https://doi.org/10.1137/0221053.
  29. 29.Rush, S. and Karamcheti, S. The annotated S4. In Blog Track at ICLR 2022, 2022. URL https://openreview.net/forum?id=xDaLPsMBZv-.
  30. 30.Strobl, L., Merrill, W., Weiss, G., Chiang, D., and Angluin, D. What formal languages can transformers express? A survey. TACL, 12, 2024.
  31. 31.Toshniwal, S., Wiseman, S., Livescu, K., and Gimpel, K. Chess as a testbed for language model state tracking. In AAAI, 2021.
  32. 32.Wang, J., Gangavarapu, T., Yan, J. N., and Rush, A. M. Mambabyte: Token-free selective state space model, 2024. arXiv:2401.13660.

Citation

MLA
Merrill, W., et al. “The Illusion of State in State-Space Models”. arXiv, 2024, http://arxiv.org/abs/2404.08819v3.
APA
Merrill, W., Petty, J., & Sabharwal, A. (2024). The Illusion of State in State-Space Models. arXiv. http://arxiv.org/abs/2404.08819v3
Chicago
Merrill, W., J. Petty, and A. Sabharwal. 2024. “The Illusion of State in State-Space Models”. arXiv. http://arxiv.org/abs/2404.08819v3.
Harvard
Merrill, W., Petty, J. and Sabharwal, A. (2024) “The Illusion of State in State-Space Models”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2404.08819v3.
Vancouver
1. Merrill W, Petty J, Sabharwal A (2024) The Illusion of State in State-Space Models. arXiv

BibTeX

@article{merrill2024the,
  title = {The Illusion of State in State-Space Models},
  author = {Merrill, William and Petty, Jackson and Sabharwal, Ashish},
  year = {2024},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2404.08819v3},
  eprint = {2404.08819}
}
Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/