Pith. sign in

REVIEW 16 cited by

The Illusion of State in State-Space Models

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2404.08819 v3 pith:IQLY2LWV submitted 2024-04-12 cs.LG cs.CCcs.CLcs.FL

William Merrill , Jackson Petty , Ashish Sabharwal This is my paper · ORCID
classification cs.LGcs.CCcs.CLcs.FL
keywords ssmsstatemodelstransformerscannottrackinganalysisarchitecture
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

State-space models (SSMs) have emerged as a potential alternative architecture for building large language models (LLMs) compared to the previously ubiquitous transformer architecture. One theoretical weakness of transformers is that they cannot express certain kinds of sequential computation and state tracking (Merrill & Sabharwal, 2023), which SSMs are explicitly designed to address via their close architectural similarity to recurrent neural networks (RNNs). 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 SSMs is limited very similarly to transformers: SSMs cannot express computation outside the complexity class $\mathsf{TC}^0$. In particular, this means they cannot solve simple state-tracking problems like permutation composition. It follows that SSMs 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 Mamba-style SSMs indeed struggle with state tracking. Thus, despite its recurrent formulation, the "state" in an SSM is an illusion: SSMs have similar expressiveness limitations to non-recurrent models like transformers, which may fundamentally limit their ability to solve real-world state-tracking problems.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 16 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. On the Emergence of Implicit Curriculum in RLVR Learning Dynamics

    cs.LG 2026-02 unverdicted novelty 8.0 of 10

    RLVR training on transformers for compositional tasks follows an implicit curriculum from easy to hard problems, with difficulty spectrum smoothness determining steady relay progress or grokking phase transitions.

  2. Indexing: the Beginning and the End

    cs.LG 2026-07 conditional novelty 7.0 of 10

    Causal-complexity bounds show RNNs, SSMs, and masked linear attention need ω(1) layers for right-hand indexing, while a one-layer softmax transformer solves it; when the index is first, a one-layer RNN suffices.

  3. When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers

    cs.LG 2026-07 conditional novelty 7.0 of 10

    Weight-tied looped transformers on group prefix products implement a linear computation frontier whose speed matches the training loop budget, and a new convergence-time instrument reveals it.

  4. pLSTM: parallelizable Linear Source Transition Mark networks

    cs.LG 2025-06 conditional novelty 7.0 of 10

    pLSTM extends linear recurrent networks to general directed acyclic graphs with a parallelizable scheme and two stabilization modes for long-range propagation.

  5. MesaNet: Sequence Modeling by Locally Optimal Test-Time Training

    cs.LG 2025-06 conditional novelty 7.0 of 10

    MesaNet uses conjugate-gradient-optimal test-time regression in a chunkwise-parallelizable recurrent layer, achieving strong language modeling and benchmark performance at up to 1B scale.

  6. Hierarchical Domain Generalization

    cs.LG 2026-07 conditional novelty 6.0 of 10

    Over infinite domains, hierarchy-uniform domain generalization is impossible for every nontrivial hypothesis class; a length-generalization bound is a property of the length hierarchy, not a hierarchy-free guarantee.

  7. The Capability Convergence Hypothesis: Capability from Access Structure, Not Scale

    cs.AI 2026-07 conditional novelty 6.0 of 10

    Long-context capability converges to hybrid architectures pairing O(1) state with a scalable index; pure scaling of SSMs or Transformers alone hits information, horizon, or circuit walls.

  8. Pretraining Recurrent Networks without Recurrence

    cs.LG 2026-06 unverdicted novelty 6.0 of 10

    SMT trains nonlinear RNNs by imitating one-step memory-transition labels generated by a Transformer, replacing BPTT's unrolled credit assignment with time-parallel supervised learning.

  9. Kalman Linear Attention: Parallel Bayesian Filtering For Efficient Language Modelling and State Tracking

    cs.LG 2026-02 conditional novelty 6.0 of 10

    KLA reparameterises information-form Kalman filtering as an associative Möbius scan, giving a parallelisable nonlinear state-space mixer that tracks A5 permutations with one or two layers.

  10. Next-Latent Prediction Transformers Learn Compact World Models

    cs.LG 2025-11 unverdicted novelty 6.0 of 10

    NextLat augments next-token prediction with latent next-state prediction, theoretically converging latents to belief states and showing empirical gains in world modeling, reasoning, planning, and faster inference via ...

  11. Systolic Array-based Accelerator for Structured State-Space Models

    cs.LG 2025-07 reject novelty 6.0 of 10

    A specialized systolic-array accelerator with a reconfigurable processing element and diagonal dataflow claims 2000x inference speedup over GPUs for S4 and Liquid-S4 state-space models.

  12. Why Neural Network Can Discover Symbolic Structures with Gradient-based Training: An Algebraic and Geometric Foundation for Neurosymbolic Reasoning

    cs.LG 2025-06 conditional novelty 6.0 of 10

    This paper proves that under O(d)-equivariant gradient flow, neural network training on reasoning tasks decouples into independent monomial potentials and reduces effective dimensionality, yielding algebraic compositi...

  13. Agent Identity Evals: Measuring Agentic Identity

    cs.AI 2025-07 conditional novelty 5.0 of 10

    Introduces Agent Identity Evals (AIE), five similarity-based metrics for LMA identity stability, with pilot experiments showing identifiability always at zero and no statistical support.

  14. Time-Scaling State-Space Models for Dense Video Captioning

    cs.CV 2025-09 conditional novelty 4.0 of 10

    A state-space model with transfer state processes videos chunk by chunk, carries the hidden state forward, and performs online dense video captioning with the same state as full-sequence processing.

  15. Self-supervised learning predicts plant growth trajectories from multi-modal industrial greenhouse data

    q-bio.QM 2025-07 conditional novelty 4.0 of 10

    HINTS, an LSTM that maps partial growth and environmental observations to parameters of a softplus growth curve, forecasts harvest height and mass up to five days ahead with lower mean absolute error than rolling-aver...

  16. TPTT: Transforming Pretrained Transformers into Titans

    cs.CL 2025-06 reject novelty 4.0 of 10

    TPTT claims to convert pretrained transformers into memory-augmented linear-attention models with LoRA fine-tuning, but the reported MMLU results are marred by implausibly low baseline scores.

Pith tools