On the Expressiveness of State Space Models via Temporal Logics

• URL: http://arxiv.org/abs/2601.19467v1
• Date: Tue, 27 Jan 2026 10:49:24 GMT
• Title: On the Expressiveness of State Space Models via Temporal Logics
• Authors: Eric Alsmann, Lowejatan Noori, Martin Lange,
• Abstract summary: We investigate the expressive power of state space models (SSM)<n>SSM has emerged as a potential alternative to transformer architectures in large language models.<n>Our results show that the expressive capabilities of SSM vary substantially depending on the underlying gating mechanism.
• Score: 4.0782474409194736
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the expressive power of state space models (SSM), which have recently emerged as a potential alternative to transformer architectures in large language models. Building on recent work, we analyse SSM expressiveness through fragments and extensions of linear temporal logic over finite traces. Our results show that the expressive capabilities of SSM vary substantially depending on the underlying gating mechanism. We further distinguish between SSM operating over fixed-width arithmetic (quantised models), whose expressive power remains within regular languages, and SSM with unbounded precision, which can capture counting properties and non-regular languages. In addition, we provide a systematic comparison between these different SSM variants and known results on transformers, thereby clarifying how the two architectures relate in terms of expressive power.

Related papers

• Towards Understanding What State Space Models Learn About Code [5.605881212882263]
  State Space Models (SSMs) have emerged as an efficient alternative to the transformer architecture.<n>Recent studies show that SSMs can match or surpass Transformers on code understanding tasks, such as code retrieval, when trained under similar conditions.<n>We present the first systematic analysis of what SSM-based code models actually learn and perform the first comparative analysis of SSM and Transformer-based code models.
  arXiv  Detail & Related papers  (2026-02-06T15:29:46Z)
• MS-SSM: A Multi-Scale State Space Model for Efficient Sequence Modeling [60.648359990090846]
  State-space models (SSMs) have recently attention as an efficient alternative to computationally expensive attention-based models for sequence modeling.<n>This paper introduces a multi-scale SSM framework that represents sequence dynamics across multiple resolution and processing each resolution with specialized state-space dynamics.
  arXiv  Detail & Related papers  (2025-12-29T19:36:28Z)
• A Comparative Analysis of Contextual Representation Flow in State-Space and Transformer Architectures [27.45316137669387]
  State Space Models (SSMs) have emerged as efficient alternatives to Transformer-Based Models (TBMs) for long-sequence processing.<n>We present the first unified, token- and layer-level analysis of representation propagation in SSMs and TBMs.<n>We find a key divergence: TBMs rapidly homogenize token representations, with diversity reemerging only in later layers, while SSMs preserve token uniqueness early but converge to homogenization deeper.
  arXiv  Detail & Related papers  (2025-10-08T04:46:11Z)
• Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling [19.10832920407789]
  We introduce a new perspective by embedding the key principles of modern SSM directly into the Message-Passing Neural Network framework.<n>Our approach, MP-SSM, enables efficient, permutation-equivariant, and long-range information propagation while preserving the architectural simplicity of message passing.
  arXiv  Detail & Related papers  (2025-05-24T14:53:07Z)
• Understanding and Mitigating Bottlenecks of State Space Models through the Lens of Recency and Over-smoothing [56.66469232740998]
  We show that Structured State Space Models (SSMs) are inherently limited by strong recency bias.<n>This bias impairs the models' ability to recall distant information and introduces robustness issues.<n>We propose to polarize two channels of the state transition matrices in SSMs, setting them to zero and one, respectively, simultaneously addressing recency bias and over-smoothing.
  arXiv  Detail & Related papers  (2024-12-31T22:06:39Z)
• On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages [56.22289522687125]
  Selective state-space models (SSMs) are an emerging alternative to the Transformer.<n>We analyze their expressiveness and length generalization performance on regular language tasks.<n>We introduce the Selective Dense State-Space Model (SD-SSM), the first selective SSM that exhibits perfect length generalization.
  arXiv  Detail & Related papers  (2024-12-26T20:53:04Z)
• Provable Benefits of Complex Parameterizations for Structured State Space Models [51.90574950170374]
  Structured state space models (SSMs) are linear dynamical systems adhering to a specified structure. In contrast to typical neural network modules, whose parameterizations are real, SSMs often use complex parameterizations. This paper takes a step towards explaining the benefits of complex parameterizations for SSMs by establishing formal gaps between real and complex diagonal SSMs.
  arXiv  Detail & Related papers  (2024-10-17T22:35:50Z)
• The Expressive Capacity of State Space Models: A Formal Language Perspective [0.8948475969696075]
  recurrent models based on linear state space models (SSMs) have shown promising performance in language modeling (LM), competititve with transformers. We present a comprehensive theoretical study of the capacity of such SSMs as it compares to that of transformers and traditional RNNs.
  arXiv  Detail & Related papers  (2024-05-27T17:46:57Z)
• Theoretical Foundations of Deep Selective State-Space Models [13.971499161967083]
  Deep SSMs demonstrate outstanding performance across a diverse set of domains.<n>Recent developments show that if the linear recurrence powering SSMs allows for multiplicative interactions between inputs and hidden states.<n>We show that when random linear recurrences are equipped with simple input-controlled transitions, then the hidden state is provably a low-dimensional projection of a powerful mathematical object.
  arXiv  Detail & Related papers  (2024-02-29T11:20:16Z)
• State space models can express n-gram languages [51.823427608117626]
  We build state space language models that can solve the next-word prediction task for languages generated from n-gram rules.<n>Our proof shows how SSMs can encode n-gram rules using new theoretical results on their capacity.<n>We conduct experiments with a small dataset generated from n-gram rules to show how our framework can be applied to SSMs and RNNs obtained through gradient-based optimization.
  arXiv  Detail & Related papers  (2023-06-20T10:41:23Z)
• Disentangling Structured Components: Towards Adaptive, Interpretable and Scalable Time Series Forecasting [52.47493322446537]
  We develop a adaptive, interpretable and scalable forecasting framework, which seeks to individually model each component of the spatial-temporal patterns. SCNN works with a pre-defined generative process of MTS, which arithmetically characterizes the latent structure of the spatial-temporal patterns. Extensive experiments are conducted to demonstrate that SCNN can achieve superior performance over state-of-the-art models on three real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T13:39:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.