The Computational Complexity of Satisfiability in State Space Models

Eric Alsmann, Martin Lange · 2025

Read The Computational Complexity of Satisfiability in State Space Models by Eric Alsmann, Martin Lange (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-18162.txt.

Introduction

State space models now rival attention-based models for language, but can their behavior be checked by proof? Eric Alsmann and Martin Lange ask whether any input can drive such a model to accept, in a 2025 paper. In full generality, that question has no answer method at all, a sign of the models' raw power. Two natural limits restore decidability, and the paper grades each one.

With a capped context length, the task is hard in one standard class when length is written plainly, and harder when written in binary code. With fixed-width number rounding, the task lands in space-based classes that shift with the code form. Results cover both gated and time-invariant model types. The work draws a first map for verifying these models.

Catalog record

CREATOREric Alsmann, Martin Lange
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-18162

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Computational Complexity of Satisfiability in State Space Models Eric Alsmann, Martin Lange 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. † † paperid: 8903 1 Introduction State Space Models (SSM) [ Gu and Dao(2024) , Gu et al.(2022)Gu, Goel, and Re , De et al.(2024)De, Smith, Fernando, Botev, Cristian-Muraru, Gu, Haroun, Berrada, Chen, Srinivasan, Desjardins, Doucet, Budden, Teh, Pascanu, Freitas, and Gulcehre , Yang et al.(2024)Yang, Wang, Shen, Panda, and Kim , Mehta et al.(2023)Mehta, Gupta, Cutkosky, and Neyshabur , Sun et al.(2023)Sun, Dong, Huang, Ma, Xia, Xue, Wang, and Wei , Orvieto et al.(2023)Orvieto, Smith, Gu, Fernando, Gulcehre, Pascanu, and De ] have recently emerged as a promising alternative to transformer-based architectures for sequence modelling tasks. By relying on linear recurrences and pointwise transformations, SSM are able to capture long-range dependencies while maintaining computational simplicity. This structural difference compared to transformers raises new questions about computational properties of SSM, in particular with regards to formal verification. While the empirical performance of SSM has been studied extensively, formal verification remains largely unexplored. In particular, understanding the complexity of basic reasoning tasks such as is there an input the SSM accepts (satisfiability) or does the SSM produce a specific output if the input satisfies some property (reachability) [ Huang et al.(2024)Huang, Ruan, Huang, Jin, Dong, Wu, Bensalem, Mu, Qi, Zhao, Cai, Zhang, Wu, Xu, Wu, Freitas, and Mustafa ] , is essential for assessing the reliability and robustness of models deployed in safety-critical applications. Satisfiability serves as a baseline for investigating formal reasoning and formal verification due to its foundational role in capturing the core computational challenges inherent in these tasks. As detailed by Sälzer et al. [ Sälzer et al.(2024)Sälzer, Alsmann, and Lange ] , satisfiability abstracts a wide class of formal reasoning problems—including verification of safety properties and formal interpretability—by focusing on the existence of inputs that lead a model to exhibit a specific behavior. This abstraction removes dependency on domain-specific properties while preserving the essential computational characteristics. Take for instance a robustness property of an SSM like: given some set of suspicious symbols E\subseteq\Sigma , will every input containing some symbols of E be rejected? This can be reduced to checking the satisfiability of the negated condition, i.e., whether there exists an input containing symbols from E that is still accepted. A more general introduction to the different verification problems, in particular for language models, can be found in [ Huang et al.(2024)Huang, Ruan, Huang, Jin, Dong, Wu, Bensalem, Mu, Qi, Zhao, Cai, Zhang, Wu, Xu, Wu, Freitas, and Mustafa ] . In this way, the satisfiability problem provides a unifying and theoretically robust framework for analysing the decidability and complexity of formal reasoning across a variety of verification and interpretability scenarios. In this paper, we initiate a systematic investigation of the satisfiability problem for SSM. The satisfiability problem asks whether there exists an input sequence that causes the model to reach an accepting configuration. We first show that, in full generality, the problem is undecidable by a reduction from the halting problem for Minsky machines. Motivated by practical settings, we then consider two natural restrictions that make the problem decidable. First, we study SSM under bounded context length, a common assumption in deployed language models. Second, we investigate SSM operating over fixed-width arithmetic, reflecting the use of quantised computation in practical implementations. We investigate these problems for different practically motivated classes of SSM. These results establish a first complexity landscape for formal reasoning in SSM. They provide a foundation for future work on verification techniques and a better theoretical understanding of the strengths and limitations of SSM. Related Work. There is only limited work on formal properties of State Space Models. Recent theoretical work [ Terzic et al.(2025)Terzic, Hersche, Camposampiero, Hofmann, Sebastian, and Rahimi , Sarrof et al.(2024)Sarrof, Veitsman, and Hahn , Merrill et al.(2024)Merrill, Petty, and Sabharwal ] has exclusively dealt with the expressive power of SSM. Sarrof et al. [ Sarrof et al.(2024)Sarrof, Veitsman, and Hahn ] showed that SSM can express all star-free languages and that a specific class of SSM exactly characterises the star-free languages. Furthermore, Merrill et al. [ Merrill et al.(2024)Merrill, Petty, and Sabharwal ] proved that quantised SSM can recognise only languages contained in the class \text{TC}^{0} . Complexity questions regarding the satisfiability problem have also been investigated for transformer architectures: Sälzer et al. [ Sälzer et al.(2024)Sälzer, Alsmann, and Lange ] studied the satisfiability problem for transformer encoders, establishing complexity results similar to ours. 2 Preliminaries Notation. We denote the set of natural numbers as \mathbb{N} and the set of real numbers as \mathbb{R} . For a vector \boldsymbol{v} , we denote its i -th component as v_{i} . We use \boldsymbol{0} to denote the zero vector, and \boldsymbol{1} to denote the vector with all components set to 1 . We write \boldsymbol{0}_{d} and \boldsymbol{1}_{d} to denote the zero and one vectors of dimension d , respectively. For a finite set M , we fix an arbitrary but fixed ordering of its elements. We define the one-hot encoding \mathbf{e}_{M}\colon 2^{M}\to\{0,1\}^{|M|} such that for any subset S\subseteq M , the vector \mathbf{e}_{M}(S) has 1 in each position corresponding to an element of S , and 0 elsewhere. In particular, for any single element a\in M , we write \mathbf{e}_{M}(a):=\mathbf{e}_{M}(\{a\}) . We denote the i -th standard basis vector by \boldsymbol{e}_{i} , with its dimension being clear from the context in which it is used. When convenient, we define large vectors by writing them as tuples of smaller vectors. For example, (\boldsymbol{u},\boldsymbol{v}) denotes the vector obtained by concatenating the entries of \boldsymbol{u} and \boldsymbol{v} . Feedforward Neural Networks. An (FNN-)node is a function v\colon\mathbb{R}^{k}\to\mathbb{R} with v(\boldsymbol{x})=\mathit{relu}(\sum_{i=1}^{k}c_{i}x_{i}+b) , where k is the input dimension , the c_{i}\in\mathbb{R} are called weights , b\in\mathbb{R} is the bias and \mathit{relu}:\mathbb{R}\to\mathbb{R} with \mathit{relu}(x)=\max(0,x) is the activation function of v . An (FNN-)layer l is a tuple of some n nodes (v_{1},\dotsc,v_{n}) where each node has the same input dimension m . It computes the function l\colon\mathbb{R}^{m}\to\mathbb{R}^{n} via l(\boldsymbol{x})=(v_{1}(\boldsymbol{x}),\dotsc,v_{n}(\boldsymbol{x})) . We call m the input and n the output dimension of l . A Feedforward Neural Network (FNN) N consists of k layers l_{1},\dotsc,l_{k} , where l_{1} has input dimension m , the output dimension of l_{i} is equal to the input dimension of l_{i+1} for i<k and the output dimension

Read the complete text