On the Expressiveness of State Space Models via Temporal Logics

Eric Alsmann, Lowejatan Noori & Martin Lange · 2026

Read On the Expressiveness of State Space Models via Temporal Logics by Eric Alsmann, Lowejatan Noori & Martin Lange (2026) 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-2601-19467.txt.

Introduction

Eric Alsmann, Lowejatan Noori, and Martin Lange measure what state space models can and cannot say. State space models have risen as a rival to transformers for language tasks. To grade their power, the team reads them through temporal logic, a formal language for patterns over time.

They study fragments and extensions of linear temporal logic over finite traces. If a model class matches a logic fragment, then tasks past that fragment are beyond it by proof, not by hunch. Such maps help builders pick architectures with open eyes about what each can express.

Catalog record

CREATOREric Alsmann, Lowejatan Noori & Martin Lange
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-19467

Browse the full library · About the Tower of Babel

Full text

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

On the Expressiveness of State Space Models via Temporal Logics Eric Alsmann, Lowejatan Noori & Martin Lange 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. 1 Introduction State Space Models (SSM) have emerged as a potential alternative to traditional sequence modelling architectures such as the popular transformer architecture. In this paper, we investigate the expressive capabilities of SSM by establishing lower bounds on their computational power. The analysis focuses on two key dimensions that influence expressiveness: the type of SSM layers used and the arithmetic precision employed in computations. We specifically examine diagonal-gated SSM like S6, cf. 10 , where gate matrices can depend on the input but must maintain a diagonal structure, and time-invariant SSM like S4, cf. 11 , where gate matrices remain constant regardless of input. For each model variant, we consider both fixed-width arithmetic, with a constant number of bits for all computations, and log-precision arithmetic, where precision scales logarithmically with input length. While empirical studies drive much of the progress in sequence modelling, foundational analysis provides complementary insights by establishing what architectures can and cannot represent in principle, independent of training dynamics. Motivated by the recent success of such analyses for transformers ( 22 ), we investigate SSMs using the same logical and complexity-theoretic framework. This allows for a precise relative comparison: we map SSM variants to the exact same logic fragments recently used to characterise transformer variants (e.g., UHAT, AHAT). We structure our analysis around three conceptual levels of expressiveness. The most fundamental level is pattern matching (linear temporal logic / first order logic), which captures the ability to detect sequences of events based on their relative order without counting. Extending this, we consider modular predicates, which enable the tracking of periodic positions similar to what positional embeddings in transformer architectures do. Finally, we analyse global counting, which allows for comparing quantities over the entire sequence and strictly necessitates log-precision arithmetic. By mapping SSMs to these levels, we provide structural guarantees on which patterns are theoretically learnable or provably impossible for a given architecture. We show that diagonal-gated SSM can recognise languages defined by pure-past Linear Temporal Logic on finite traces ( \textsc{pLTL}_{f} ) with counting capabilities, while time-invariant SSM capture languages expressible in fragments with unary temporal operators plus modular predicates. Furthermore, we show that global counting strictly requires log-precision arithmetic. The lower bounds established in this paper contribute to a growing body of research on the theoretical foundations of neural network architectures for sequence modelling, complementing empirical observations about their practical performance. Crucially, the resulting impossibility proofs identify fundamental architectural bottlenecks, such as the inability of diagonal fixed-precision SSMs to represent non-monotonic patterns like (aa)^{*} , which hold independently of the training data or optimization procedure. In this sense, our foundational characterisation complements empirical benchmarks by delineating which tasks are structurally out of reach for specific SSM variants. Related Work. Recent work on the theoretical foundations of SSM has been related to circuit complexity, cf. 17 , automata theory, cf. 20 , and communication complexity, cf. 29 . 1 investigated the computational complexity of verifying SSM. To the best of our knowledge, this is the first paper connecting the expressive power of SSM to formal logic. The work on the formal expressiveness of SSM started with 17 who provided upper bounds via circuit complexity. They showed that diagonal gated as well as time-invariant SSM working over \log -precision as well as models working over fixed-precision (e.g. floating-point) are contained in \text{TC}^{0} . This is the class of functions definable with boolean circuits of polynomial size, constant depth and using threshold gates. They also showed that SSM with arbitrary gates, meaning that the gate can be an arbitrary input-dependent matrix, can recognise all regular languages including \text{NC}^{1} -complete languages. This implies a strict increase in expressiveness unless \text{TC}^{0}=\text{NC}^{1} . Further work by 20 provided a lower bound for diagonal gated SSM, proving that they can recognise all star-free languages. They also showed that under certain restrictions this lower bound is tight in the sense that these SSM recognise a regular language if and only if it is star-free. Our work significantly extends the lower bound provided by Sarrof et al. (2024). While they proved that diagonal SSMs (with a specific output function) can recognise star-free languages, our Theorem 1 recovers this as a special case within a broader hierarchy. Crucially, we extend the analysis along three new axes: (1) We characterise time-invariant and mixed SSMs, relating them to modular predicates ( \textsc{pLTL}_{f}[\mathtt{MOD}] ); (2) we analyse the impact of arithmetic precision, showing that log-precision is strictly necessary for non-regular counting languages (like a^{n}b^{n}c^{n} ); and (3) we integrate these findings into the existing transformer landscape (UHAT/AHAT), enabling a direct architectural comparison. 29 showed that SSM working over fixed-precision can only recognise regular languages. Parallel to the work on the expressiveness of SSM there has been a lot of research on the expressiveness of transformer architectures via connections to logics (see 22 for a survey on these results). The most important work regarding this paper are 26 , who proved connections between unique hard-attention transformers and first-order logic as well as 3 and 25 , who investigate the counting abilities of several transformer architectures via extensions of linear temporal logic. 2 Fundamentals State Space Models. We explore SSM in a generalised setting as presented in 17 . For a structured analysis of this model, we will formalise its architecture following similar approaches as in 20 and 17 . An SSM layer l is defined as a tuple (\bm{h}_{0},\mathit{gate},\mathit{inc},\phi) , where \bm{h}_{0}\in\mathbb{R}^{d} . The function \mathit{gate} is a mapping \mathbb{R}^{d}\rightarrow\mathbb{R}^{d\times d} , \mathit{inc} is a mapping \mathbb{R}^{d}\rightarrow\mathbb{R}^{d} , and \phi is a mapping \mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{d} . An SSM layer transforms an input sequence of vectors \bm{x}_{1}\cdots\bm{x}_{k}\in(\mathbb{R}^{d})^{*} into an output sequence \bm{z}_{1}\cdots\bm{z}_{k}\in(\mathbb{R}^{d})^{*} through the following process: it computes an intermediate sequence \bm{h}_{1}\cdots\bm{h}_{k}\in(\mathbb{R}^{d})^{+} via the linear recurrence \bm{h}_{t}=\mathit{gate}(\bm{x}_{t})\cdot\bm{h}_{t-1}+\mathit{inc}(\bm{x_{t}})\quad\text{for }1\leq t\leq k and subsequently generates the output via \bm{z}_{t}=\phi(\bm{h}_{t},\bm{x}_{t}) . An SSM S comprising L layers processes sequences over a finite alphabet \Sigma . It is expressed as a tuple S=(\mathit{emb},l_{1},\cdots,l_{L},\mathit{out}) . Each l_{i} refers to a layer as defined above, while \mathit{emb} is a function \Sigma\rightarrow\mathbb{R}^{d} , and \mathit{out} is a function \mathbb{R}^{d}\rightarrow\mathbb{R}^{d} . The SSM computes a function \Sigma^{*}\rightarrow\mathbb{R} as follows: let \sigma=\sigma_{1}\cdots\sigma_{k}\in\Sigma^{*} be a word. Initially, the SSM computes the embedding \bm{x}_{1}^{0}\cdots\bm{x}_{k}^{0} of the word by setting \bm{x}_{i}^{0}=\mathit{emb}(\sigma_{i}) . Subsequently, for each layer 1\leq j\leq L : compute \bm{z}_{1}^{j}\cdots\bm{z}_{k}^{j}=l_{j}(\bm{x}_{1}^{j-1}\cdots\bm{x}_{k}^{j-1}) . Each layer’s output serves as the input for the succeeding layer, meaning

Read the complete text