🤖 machine learning

On the Expressiveness of State Space Models via Temporal Logics

This paper analyzes the expressive power of state space models (SSMs) using temporal logics, revealing that their capabilities range from regular languages to non-regular languages depending on gating mechanisms and arithmetic precision, while systematically comparing these findings to transformer architectures.

Original authors: Eric Alsmann, Lowejatan Noori, Martin Lange

Published 2026-01-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Eric Alsmann, Lowejatan Noori, Martin Lange

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to read a story and understand the sequence of events. In the world of Artificial Intelligence, there are two main types of "readers" (architectures) competing for the job: the famous Transformers (like the ones powering current chatbots) and the rising stars called State Space Models (SSMs).

This paper is a theoretical investigation into the "brainpower" of SSMs. The authors aren't asking how well these models perform on a specific test; instead, they are asking: "What is the absolute limit of what these models can understand, no matter how much we train them?"

To answer this, they use a special "logic language" (Temporal Logic) as a measuring stick. Here is a breakdown of their findings using simple analogies.

1. The Two Main Types of SSMs

The paper splits SSMs into two main flavors based on how they handle information:

Diagonal-Gated SSMs (The "Strict Accountants"): These models have a rule where their internal "gates" (switches that control information flow) can change based on the current word they are reading, but they must remain "diagonal." Think of this like a calculator where you can change the numbers you are adding, but you can't mix the columns together.
Time-Invariant SSMs (The "Steady Clocks"): These models have gates that never change, no matter what word they are reading. They are like a metronome or a clock; they tick at the same rate regardless of the story being told.

2. The Precision Problem: Ruler vs. Tape Measure

The authors also looked at how "precise" the math inside these models is.

Fixed-Precision: Imagine using a ruler with only 10 marks. No matter how long the story is, you can't measure anything smaller than those marks. This is like standard computer math (floating-point).
Log-Precision: Imagine using a tape measure that automatically gets longer and more detailed as the story gets longer. If the story is 100 words long, your ruler has 100 marks; if it's 1,000 words, it has 1,000 marks. This allows for much finer counting.

3. What Can They Actually Understand?

The "Strict Accountants" (Diagonal SSMs)

With a simple ruler (Fixed-Precision): They are good at understanding the order of events. They can tell you "A happened before B" or "A happened, then B happened, then C." However, they have a major blind spot: They cannot count in cycles.
- The Analogy: If you ask them to recognize a pattern like "an even number of 'a's" (e.g., aa, aaaa, aaaaaa), they fail. Because their math is monotonic (it only goes up or stays the same), they eventually get "stuck" and can't tell the difference between 2 'a's and 4 'a's.
With a growing tape measure (Log-Precision): If you give them the ability to count precisely, they become much smarter. They can now count exactly how many times something happened in the past. They can understand complex patterns like "The number of 'a's equals the number of 'b's equals the number of 'c's."

The "Steady Clocks" (Time-Invariant SSMs)

With a simple ruler: These models are bad at tracking complex "since" relationships (e.g., "Since the last time we saw a 'b', have we seen an 'a'?"). However, they have a superpower: They can count in circles.
- The Analogy: Because their internal mechanism is a constant cycle, they are excellent at knowing "Is this the 2nd, 4th, or 6th word?" They can easily recognize the "even number of 'a's" pattern that the Strict Accountants failed at.
With a growing tape measure: They can do both: count in circles and count total numbers.

The "Hybrid" (Mixed SSMs)

If you combine both types of layers (some Strict Accountants, some Steady Clocks), you get the best of both worlds. They can understand order, cycles, and counting. The paper shows that these hybrid models can recognize almost any "regular" pattern you can think of, up to a certain complexity limit.

4. How Do They Compare to Transformers?

The authors compared their findings to what we already know about Transformers:

Diagonal SSMs (Fixed-Precision) are roughly equivalent to Transformers without positional cues (they know the order of words but not their exact position).
Time-Invariant SSMs are equivalent to Transformers with Positional Encodings (they know exactly where they are in the sentence).
The Big Difference: Transformers with "global attention" (like the Average Hard-Attention type) can look at the entire story at once to count things forward and backward. SSMs, by their nature, only look at the past (what they have already read). Therefore, SSMs are strictly less powerful than the most advanced Transformers when it comes to counting things that happen later in the sequence.

5. The "Impossible" Tasks

The most important takeaway is the list of things these models cannot do, no matter how much you train them:

A Fixed-Precision Diagonal SSM can never learn to distinguish between an even and an odd number of repeated items (like aa vs aaa). This is a hard architectural limit, not a training failure.
To break this limit, you must either change the architecture (add time-invariant layers) or increase the math precision (use the growing tape measure).

Summary

Think of these models as different types of librarians:

Diagonal (Fixed): Good at reading a book in order, but gets confused if asked to count specific patterns.
Time-Invariant: Good at counting pages (even/odd), but struggles with complex "since then" stories.
Hybrid: The ultimate librarian who can do both, but still can't look ahead to the next chapter to count things.

The paper proves that these limitations are built into the DNA of the architecture. You can't train a "Fixed-Precision Diagonal" librarian to become a "Counting" librarian; you have to give them a better tool (log-precision) or a different brain structure (mixed layers) to achieve that.

Technical Summary: On the Expressiveness of State Space Models via Temporal Logics

Problem Statement

State Space Models (SSMs) have emerged as a competitive alternative to Transformer architectures for sequence modeling, particularly in large language models. However, while empirical progress is rapid, the theoretical foundations regarding the expressive power of SSMs remain underexplored compared to Transformers. The central problem addressed is determining what classes of languages and patterns different SSM variants can theoretically represent, independent of training dynamics. Specifically, the paper investigates how two key architectural dimensions influence expressiveness:

Gating Mechanisms: The distinction between time-invariant gates (constant matrices, e.g., S4), diagonal-gated mechanisms (input-dependent diagonal matrices, e.g., S6), and arbitrary gates.
Arithmetic Precision: The distinction between fixed-width arithmetic (constant bits, e.g., standard floating-point) and log-precision arithmetic (precision scaling logarithmically with input length).

The authors aim to map these variants to formal logic fragments and complexity classes to establish rigorous lower bounds and identify fundamental architectural bottlenecks.

Methodology

The authors employ a logical and complexity-theoretic framework to analyze SSM expressiveness, mirroring recent foundational work on Transformers (e.g., Strobl et al., 2024; Yang et al., 2024a).

Formal Model: SSMs are formalized as layers transforming input sequences via linear recurrences ( $h_t = \text{gate}(x_t) \cdot h_{t-1} + \text{inc}(x_t)$ ) followed by non-linear output functions (modeled as ReLU-activated Feedforward Neural Networks).
Logical Framework: The analysis utilizes Linear Temporal Logic over finite traces (LTLf), specifically the pure-past fragment (PLTLf). This logic captures properties based on event ordering without counting.
- Extensions: The logic is extended with modular predicates (to track periodic positions) and backward-looking counting operators ( $\overleftarrow{\#}$ ) to analyze the ability to count occurrences.
Constructive Proofs: The authors provide constructive proofs demonstrating how to translate logical formulas into SSM architectures. They show how specific temporal operators (e.g., Yesterday, Previously, Since) and counting mechanisms can be implemented via specific gate structures and arithmetic settings.
Impossibility Proofs: Conversely, the paper establishes non-expressibility results using properties like monotonicity in fixed-precision diagonal SSMs to prove that certain non-star-free languages (e.g., $(aa)^*$ ) cannot be recognized.

Key Contributions

1. Expressiveness Hierarchy of SSM Variants

The paper establishes a detailed hierarchy of SSM capabilities based on gating and precision:

Diagonal-Gated SSM (Fixed Precision):
- Capability: Recognize all languages definable in PLTLf (equivalent to star-free languages and First-Order Logic with order, $FO[<]$).
- Limitation: Cannot recognize non-star-free languages like $(aa)^*$ due to a monotonicity property where repeated identical inputs cause the state to stabilize.
Diagonal-Gated SSM (Log-Precision):
- Capability: Recognize languages in PLTLf[ $\overleftarrow{\#}$ ], extending expressiveness to include non-regular and even non-context-free languages (e.g., $\{a^n b^n c^n\}$ ) via backward-looking counting.
Time-Invariant SSM (Fixed Precision):
- Capability: Recognize languages in UN-PLTLf[MOD] (Unary PLTLf with modular predicates). They can track periodic positions (e.g., distinguishing even/odd indices) using cyclic permutation matrices, allowing them to recognize $(aa)^*$ .
- Limitation: Conjectured to be unable to recognize languages requiring the Since operator (e.g., $L(a \mathcal{S} b)$ ) because they lack input-dependent gates to combine current and past information dynamically.
Mixed SSM (Diagonal + Time-Invariant):
- Capability: Recognize PLTLf[MOD], effectively capturing the union of diagonal and time-invariant capabilities. This corresponds to the class of regular languages in $AC^0$ .
- Log-Precision Extension: With log-precision, they recognize PLTLf[ $\overleftarrow{\#}$ , MOD].

2. Arithmetic Precision as a Critical Determinant

The paper rigorously demonstrates that log-precision is strictly necessary for recognizing non-regular counting languages. Fixed-width arithmetic restricts SSMs to regular (or star-free) languages, whereas log-precision enables the accumulation of counts necessary for languages like $a^n b^n c^n$ .

3. Systematic Comparison with Transformers

The authors map SSM variants directly to known Transformer expressiveness results:

Diagonal SSM (Fixed Precision) $\approx$ Unique Hard-Attention Transformers (UHAT) without positional encodings (both capture $FO[<]$).
Time-Invariant SSM $\approx$ UHAT with Positional Encodings (UHAT+PE) (both capture $FO[<, MOD]$).
Mixed SSM (Log-Precision) $\approx$ Average Hard-Attention Transformers (AHAT) (both capture counting capabilities, though SSMs are limited to backward-looking counting).
Arbitrary Gates: SSMs with arbitrary gates can recognize all regular languages, matching the upper bounds of more complex Transformer variants.

Key Results

Theorem 1: Diagonal SSMs with fixed-precision recognize all languages in PLTLf.
Theorem 3: Diagonal SSMs with fixed-precision cannot recognize $(aa)^*$ , proving a strict separation from time-invariant SSMs in this regard.
Theorem 4: Diagonal SSMs with log-precision recognize all languages in PLTLf[ $\overleftarrow{\#}$ ].
Theorem 7: Time-invariant SSMs with fixed-precision recognize all languages in UN-PLTLf[MOD].
Corollary 8: Mixed SSMs with fixed-precision recognize all regular languages in $AC^0$ .
Impossibility: The paper provides impossibility proofs showing that specific architectural choices (e.g., diagonal fixed-precision) create fundamental bottlenecks that no amount of training data or optimization can overcome.

Significance and Claims

The paper claims to provide the first connection between the expressive power of SSMs and formal logic, offering structural guarantees on what patterns are theoretically learnable or provably impossible for specific SSM variants.

Foundational Insights: By delineating the "impossible" tasks (e.g., non-monotonic patterns for fixed-precision diagonal SSMs), the work complements empirical benchmarks by identifying architectural limits independent of training dynamics.
Architectural Clarity: The results clarify the relationship between SSMs and Transformers, showing that SSMs inherently encode positional information through recurrence (analogous to positional encodings in Transformers) but differ in their counting mechanisms (backward-looking vs. global attention).
Complexity Alignment: The findings suggest that restricted SSMs (diagonal/time-invariant with fixed precision) likely operate within $AC^0$ , a proper subset of the $TC^0$ upper bound previously established by Merrill et al. (2024). This implies that these architectures may not be capable of recognizing parity or other languages outside $AC^0$ without specific modifications.

The authors conclude that their work establishes a rigorous theoretical baseline, revealing that the choice of gating mechanism and arithmetic precision fundamentally dictates the class of languages an SSM can model, regardless of the specific training procedure used.