On the Expressiveness of State Space Models via Temporal Logics
This work clarifies the theoretical capabilities of SSMs for researchers in machine learning and formal methods, though it is incremental as it builds on existing analyses.
The paper investigates the expressive power of state space models (SSMs) as alternatives to transformers in large language models, showing that SSMs with unbounded precision can capture non-regular languages while quantised models are limited to regular languages, and it systematically compares these variants to transformers.
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.