REVIEW 25 cited by
The Illusion of State in State-Space Models
Not yet reviewed by Pith; the record is open.
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
The Illusion of State in State-Space Models
read the original 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.
Forward citations
Cited by 25 Pith papers
-
On the Emergence of Implicit Curriculum in RLVR Learning Dynamics
For a stylized transformer, outcome-only RL learns short compositions, and mixed-difficulty training produces an implicit easy-to-hard curriculum: smooth difficulty spectra relay progress, abrupt spectra grok.
-
Indexing: the Beginning and the End
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.
-
When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers
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.
-
Space-Efficient Language Generation in the Limit
A poly(s,k)-space streaming algorithm achieves generation gap O(k^{2s-2}) for DFA languages with s states over k symbols and captures all strings of length at least 2s-1, with a near-matching lower bound via communica...
-
A Verifiable Search Is Not a Learnable Chain-of-Thought
Verifiable search procedures cannot be learned as forward chain-of-thought by language models; they instead learn memorization, verification, or require precomputed catalogs.
-
A Held-Out Transition-Pair Falsifier for Long-Horizon Non-Abelian State Tracking
Held-out transition-pair falsifier on S3 x S3 shows projected recurrent state model achieves perfect final-state prediction up to 1M+ tokens while matched baselines fail.
-
Preconditioned DeltaNet: Curvature-aware Sequence Modeling for Linear Recurrences
Preconditioned delta-rule models with a diagonal curvature approximation improve upon standard DeltaNet, GDN, and KDA by better approximating the test-time regression objective.
-
The UNDO Flip-Flop: A Controlled Probe for Reversible Semantic State Management in State Space Model
Mamba-2 models fail to learn reversible state retrieval in the UNDO Flip-Flop task, defaulting to a toggle heuristic and achieving only 41% accuracy under adversarial conditions.
-
Hierarchical Domain Generalization
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.
-
The Capability Convergence Hypothesis: Capability from Access Structure, Not Scale
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.
-
The Capability Convergence Hypothesis: Capability from Access Structure, Not Scale
Capability, unlike representation, converges to access-complete hybrid architectures, and a witness task separates pure from hybrid families under fixed budgets.
-
SPDM: Geometry-Modulated State Space Modeling with Manifold Constraints for Time Series Forecasting
SPDM is a geometry-aware state-space model that projects covariance matrices onto the SPD manifold tangent space and uses geometric gating to modulate SSM parameters for improved multivariate time series forecasting.
-
Pretraining Recurrent Networks without Recurrence
SMT reduces RNN training to supervised learning on memory transitions (m_t, x_{t+1}) to m_{t+1} obtained from a Transformer encoder, enabling time-parallel training with O(1) gradient paths.
-
UniMamba: A Unified Spatial-Temporal Modeling Framework with State-Space and Attention Integration
UniMamba integrates Mamba state-space dynamics with attention layers and transforms like FFT-Laplace to outperform prior models on multivariate time series forecasting benchmarks.
-
On the Emergence of Implicit Curriculum in RLVR Learning Dynamics
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.
-
Kalman Linear Attention: Parallel Bayesian Filtering For Efficient Language Modelling and State Tracking
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.
-
Next-Latent Prediction Transformers Learn Compact World Models
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 ...
-
Next-Latent Prediction Transformers Learn Compact World Models
Adding a next-latent prediction loss to next-token training makes transformer hidden states more predictive of future tokens and improves planning/reasoning on small benchmarks.
-
Kimi Linear: An Expressive, Efficient Attention Architecture
Kimi Linear hybridizes linear attention with a new KDA module to beat full attention on tasks while slashing KV cache by 75% and speeding decoding up to 6x.
-
Adaptive Memory Decay for Log-Linear Attention
Making memory decay input-dependent via a lightweight MLP improves log-linear attention performance on associative recall, selective copying, and language modeling, especially for long sequences.
-
The Serial Scaling Hypothesis
The serial scaling hypothesis formalizes inherently serial problems in complexity theory and demonstrates that diffusion models cannot solve them.
-
Pretraining Recurrent Networks without Recurrence
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.
-
Measuring AI Reasoning: A Guide for Researchers
Reasoning in language models should be measured by the faithfulness and validity of their multi-step search processes and intermediate traces, not final-answer accuracy.
-
UniMamba: A Unified Spatial-Temporal Modeling Framework with State-Space and Attention Integration
A Mamba-plus-attention hybrid with FFT-Laplace and TCN encoding claims state-of-the-art accuracy and efficiency on eight multivariate time-series forecasting benchmarks.
-
A Survey of Mamba
The paper consolidates existing research on Mamba models, their architecture variants, adaptations to different data modalities, and applications across domains.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.