The Computational Complexity of Satisfiability in State Space Models

• URL: http://arxiv.org/abs/2508.18162v1
• Date: Mon, 25 Aug 2025 16:12:47 GMT
• Title: The Computational Complexity of Satisfiability in State Space Models
• Authors: Eric Alsmann, Martin Lange,
• Abstract summary: We find that ssmSAT is undecidable in general, reflecting the computational power of SSM.<n>Motivated by practical settings, we identify two natural restrictions under which ssmSAT becomes decidable.
• Score: 4.5835414225547195
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We analyse the complexity of the satisfiability problem ssmSAT for State Space Models (SSM), which asks whether an input sequence can lead the model to an accepting configuration. We find that ssmSAT is undecidable in general, reflecting the computational power of SSM. Motivated by practical settings, we identify two natural restrictions under which ssmSAT becomes decidable and establish corresponding complexity bounds. First, for SSM with bounded context length, ssmSAT is NP-complete when the input length is given in unary and in NEXPTIME (and PSPACE-hard) when the input length is given in binary. Second, for quantised SSM operating over fixed-width arithmetic, ssmSAT is PSPACE-complete resp. in EXPSPACE depending on the bit-width encoding. While these results hold for diagonal gated SSM we also establish complexity bounds for time-invariant SSM. Our results establish a first complexity landscape for formal reasoning in SSM and highlight fundamental limits and opportunities for the verification of SSM-based language models.

Related papers

• RegexPSPACE: A Benchmark for Evaluating LLM Reasoning on PSPACE-complete Regex Problems [9.63813674229442]
  Large language models (LLMs) show strong performance across natural language processing (NLP), mathematical reasoning, and programming.<n>We introduce a novel benchmark grounded in two PSPACE-complete regular expression (regex) problems: equivalence decision (RegexEQ) and minimization (RegexMin)<n>We conduct extensive evaluations on 6 LLMs and 5 LRMs of varying scales, revealing common failure patterns such as verbosity and repetition.
  arXiv  Detail & Related papers  (2025-10-10T10:13:47Z)
• On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach [59.589793281734636]
  We show that Statistical Query hardness can be established when both the alphabet size and input length are in the number of states.<n>Our result is derived solely from the internal state-transition structure of semiautomata.
  arXiv  Detail & Related papers  (2025-10-05T09:35:35Z)
• Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models [68.31088463716269]
  We propose a structured sparse parametrization of transition matrices in state-space models (SSMs)<n>Our method, PD-SSM, parametrizes the transition matrix as the product of a column one-hot matrix ($P$) and a complex-valued diagonal matrix ($D$)<n>The model significantly outperforms a wide collection of modern SSM variants on various FSA state tracking tasks.
  arXiv  Detail & Related papers  (2025-09-26T12:46:30Z)
• Bridging Expressivity and Scalability with Adaptive Unitary SSMs [15.244653633181303]
  We introduce the Adaptive Unitary State Space Model (AUSSM), a novel class of SSMs that skew-symmetric, input-dependent recurrence.<n>We show that AUSSM and its hybrid variant Mambaoutperform prior SSMs on formal tasks such as parity and modular arithmetic.<n>Our results demonstrate that unitary recurrence provides a powerful and efficient inductive bias for both symbolic and continuous sequence modeling.
  arXiv  Detail & Related papers  (2025-07-07T17:47:16Z)
• Overcoming Long-Context Limitations of State-Space Models via Context-Dependent Sparse Attention [17.498728107106817]
  We focus on analyzing and improving the long-context modeling capabilities of state-space models (SSMs)<n>We show that the widely used synthetic task, associative recall, insufficiently represents the complexities of real-world long-context modeling.<n>To bridge the gap between theoretical analysis and real-world applications, we propose locality-sensitive Hashing Attention with sparse Key Selection.
  arXiv  Detail & Related papers  (2025-07-01T06:03:50Z)
• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  Recent developments have given rise to various models, such as Gated Linear Attention (GLA) and Mamba.<n>This raises a natural question: can we characterize the full class of neural sequence models that support near-constant-time parallel evaluation and linear-time, constant-space sequential inference?
  arXiv  Detail & Related papers  (2025-06-12T17:32:02Z)
• SparseSSM: Efficient Selective Structured State Space Models Can Be Pruned in One-Shot [8.080568103779893]
  State-space language models such as Mamba match Transformer quality while permitting linear complexity inference.<n>Existing one-shot pruning methods are tailored to attention blocks and fail to account for the time-shared and discretized state-transition matrix.<n>We introduce SparseSSM, the first training-free pruning framework that extends the classic optimal brain surgeon (OBS) framework to state space architectures.
  arXiv  Detail & Related papers  (2025-06-11T11:14:57Z)
• 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)

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.