🤖 machine learning

On the Expressiveness of State Space Models via Temporal Logics

Diese Arbeit analysiert die Ausdrucksstärke von Zustandsraummodellen (State Space Models, SSMs) unter Verwendung temporaler Logiken und zeigt auf, dass ihre Fähigkeiten je nach Gating-Mechanismen und arithmetischer Präzision von regulären zu nicht-regulären Sprachen reichen, während sie diese Ergebnisse systematisch mit Transformer-Architekturen vergleicht.

Ursprüngliche Autoren: Eric Alsmann, Lowejatan Noori, Martin Lange

Veröffentlicht 2026-01-28

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Eric Alsmann, Lowejatan Noori, Martin Lange

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, einem Roboter beizubringen, eine Geschichte zu lesen und die Abfolge von Ereignissen zu verstehen. In der Welt der Künstlichen Intelligenz konkurrieren zwei Haupttypen von „Lesern“ (Architekturen) um diesen Job: die berühmten Transformer (wie jene, die heutige Chatbots antreiben) und die aufstrebenden Stars namens State Space Models (SSMs).

Diese Arbeit ist eine theoretische Untersuchung der „Denkkraft“ von SSMs. Die Autoren fragen nicht, wie gut diese Modelle bei einem bestimmten Test abschneiden; stattdessen fragen sie: „Was ist das absolute Limit dessen, was diese Modelle verstehen können, egal wie sehr wir sie trainieren?“

Um dies zu beantworten, verwenden sie eine spezielle „Logiksprache“ (Temporale Logik) als Maßstab. Hier ist eine Aufschlüsselung ihrer Ergebnisse unter Verwendung einfacher Analogien.

1. Die zwei Haupttypen von SSMs

Das Paper unterteilt SSMs in zwei Hauptgeschmacksrichtungen, basierend darauf, wie sie Informationen verarbeiten:

Diagonal-Gated SSMs (Die „strengen Buchhalter“): Diese Modelle haben eine Regel, nach der ihre internen „Gates“ (Schalter, die den Informationsfluss steuern) sich zwar ändern können, während sie das aktuelle Wort lesen, aber sie müssen „diagonal“ bleiben. Denken Sie an einen Taschenrechner, bei dem Sie zwar die Zahlen ändern können, die Sie addieren, aber die Spalten nicht miteinander vermischen dürfen.
Time-Invariant SSMs (Die „beständigen Uhren“): Diese Modelle haben Gates, die sich niemals ändern, egal welches Wort sie gerade lesen. Sie sind wie ein Metronom oder eine Uhr; sie ticken in der gleichen Geschwindigkeit, unabhängig davon, welche Geschichte erzählt wird.

2. Das Präzisionsproblem: Lineal vs. Maßband

Die Autoren untersuchten auch, wie „präzise“ die Mathematik innerhalb dieser Modelle ist.

Fixed-Precision (Feste Präzision): Stellen Sie sich vor, Sie benutzen ein Lineal mit nur 10 Markierungen. Egal wie lang die Geschichte ist, Sie können nichts Kleineres als diese Markierungen messen. Dies entspricht der Standard-Computermathematik (Floating-Point).
Log-Precision (Logarithmische Präzision): Stellen Sie sich ein Maßband vor, das automatisch länger und detaillierter wird, je länger die Geschichte wird. Wenn die Geschichte 100 Wörter lang ist, hat Ihr Lineal 100 Markierungen; wenn sie 1.000 Wörter lang ist, hat es 1.000 Markierungen. Dies ermöglicht ein viel feineres Zählen.

3. Was können sie tatsächlich verstehen?

Die „strengen Buchhalter“ (Diagonal SSMs)

Mit einem einfachen Lineal (Fixed-Precision): Sie sind gut darin, die Reihenfolge von Ereignissen zu verstehen. Sie können sagen: „A geschah vor B“ oder „A geschah, dann B, dann C“. Sie haben jedoch eine große Schwachstelle: Sie können nicht in Zyklen zählen.
- Die Analogie: Wenn man sie fragt, ein Muster wie „eine gerade Anzahl von 'a's“ zu erkennen (z. B. aa, aaaa, aaaaaa), scheitern sie. Da ihre Mathematik monoton ist (sie steigt nur oder bleibt gleich), geraten sie irgendwann „fest“ und können nicht mehr zwischen 2 'a's und 4 'a's unterscheiden.
Mit einem wachsenden Maßband (Log-Precision): Wenn Sie ihnen die Fähigkeit geben, präzise zu zählen, werden sie viel klüger. Sie können nun genau zählen, wie oft etwas in der Vergangenheit passiert ist. Sie können komplexe Muster verstehen wie „Die Anzahl der 'a's ist gleich der Anzahl der 'b's gleich der Anzahl der 'c's“.

Die „beständigen Uhren“ (Time-Invariant SSMs)

Mit einem einfachen Lineal: Diese Modelle sind schlecht darin, komplexe „Seitdem“-Beziehungen zu verfolgen (z. B. „Seit dem letzten Mal, als wir ein 'b' gesehen haben, haben wir ein 'a' gesehen?“). Sie haben jedoch eine Superkraft: Sie können im Kreis zählen.
- Die Analogie: Da ihr interner Mechanismus ein ständiger Zyklus ist, sind sie exzellent darin zu wissen: „Ist dies das 2., 4. oder 6. Wort?“ Sie können leicht das Muster „eine gerade Anzahl von 'a's“ erkennen, an dem die strengen Buchhalter gescheitert sind.
Mit einem wachsenden Maßband (Log-Precision): Sie können beides tun: im Kreis zählen und Gesamtzahlen zählen.

Der „Hybrid“ (Mixed SSMs)

Wenn Sie beide Arten von Layern kombinieren (einige strenge Buchhalter, einige beständige Uhren), erhalten Sie das Beste aus beiden Welten. Sie können Ordnung, Zyklen und das Zählen verstehen. Das Paper zeigt, dass diese Hybrid-Modelle fast jedes „reguläre“ Muster erkennen können, das man sich vorstellen kann, bis zu einer gewissen Komplexitätsgrenze.

4. Wie schneiden sie im Vergleich zu Transformern ab?

Die Autoren haben ihre Ergebnisse mit dem verglichen, was wir bereits über Transformer wissen:

Diagonal SSMs (Fixed-Precision) sind in etwa äquivalent zu Transformern ohne Positionshinweise (sie kennen die Reihenfolge der Wörter, aber nicht deren exakte Position).
Time-Invariant SSMs sind äquivalent zu Transformern mit Positional Encodings (sie wissen genau, wo sie sich im Satz befinden).
Der große Unterschied: Transformer mit „Global Attention“ (wie der Typ des Average Hard-Attention) können die gesamte Geschichte auf einmal betrachten, um Dinge vorwärts und rückwärts zu zählen. SSMs hingegen schauen ihrer Natur nach nur in die Vergangenheit (auf das, was sie bereits gelesen haben). Daher sind SSMs im Vergleich zu den fortschrittlichsten Transformern weniger leistungsfähig, wenn es darum geht, Dinge zu zählen, die später in der Sequenz passieren.

5. Die „unmöglichen“ Aufgaben

Das wichtigste Fazit ist die Liste der Dinge, die diese Modelle nicht tun können, egal wie sehr man sie trainiert:

Ein Fixed-Precision Diagonal SSM kann niemals lernen, zwischen einer geraden und einer ungeraden Anzahl von wiederholten Elementen (wie aa vs. aaa) zu unterscheiden. Dies ist ein hartes architektonisches Limit, kein Trainingsfehler.
Um dieses Limit zu durchbrechen, müssen Sie entweder die Architektur ändern (Time-Invariant Layer hinzufügen) oder die mathematische Präzision erhöhen (das wachsende Maßband verwenden).

Zusammenfassung

Betrachten Sie diese Modelle als verschiedene Arten von Bibliothekaren:

Diagonal (Fixed): Gut darin, ein Buch der Reihe nach zu lesen, aber verwirrt, wenn man sie bittet, spezifische Muster zu zählen.
Time-Invariant: Gut darin, Seiten zu zählen (gerade/ungerade), aber kämpft mit komplexen „Seitdem“-Geschichten.
Hybrid: Der ultimative Bibliothekar, der beides kann, aber immer noch nicht vorausblicken kann, um Dinge im nächsten Kapitel zu zählen.

Das Paper beweist, dass diese Einschränkungen in der DNA der Architektur eingebaut sind. Man kann einen „Fixed-Precision Diagonal“-Bibliothekar nicht trainieren, damit er ein „Zähl“-Bibliothekar wird; man muss ihm entweder ein besseres Werkzeug geben (Log-Precision) oder eine andere Gehirnstruktur (Mixed Layers), um dies zu erreichen.

Technisches Resümee: Zur Expressivität von State Space Models mittels temporaler Logiken

Problemstellung

State Space Models (SSMs) haben sich als wettbewerbsfähige Alternative zu Transformer-Architekturen für die Sequenzmodellierung etabliert, insbesondere bei großen Sprachmodellen. Während der empirische Fortschritt jedoch rasant voranschreitet, bleibt die theoretische Fundierung hinsichtlich der Expressivität von SSMs im Vergleich zu Transformern untererforscht. Das zentrale Problem, das hier adressiert wird, ist die Bestimmung, welche Klassen von Sprachen und Mustern verschiedene SSM-Varianten theoretisch repräsentieren können, unabhängig von der Trainingsdynamik. Speziell untersucht das Paper, wie zwei zentrale architektonische Dimensionen die Expressivität beeinflussen:

Gating-Mechanismen: Die Unterscheidung zwischen zeitinvarianten Gates (konstante Matrizen, z. B. S4), diagonal-gated Mechanismen (eingabebedingte diagonale Matrizen, z. B. S6) und beliebigen Gates.
Arithmetische Präzision: Die Unterscheidung zwischen festbreitiger Arithmetik (konstante Bitbreite, z. B. Standard-Fließkommazahlen) und Log-Präzisions-Arithmetik (Präzisionsskalierung logarithmisch mit der Eingabelänge).

Die Autoren zielen darauf ab, diese Varianten auf formale Logikfragmente und Komplexitätsklassen abzubilden, um rigorose untere Schranken festzulegen und fundamentale architektonische Engpässe zu identifizieren.

Methodik

Die Autoren verwenden einen logischen und komplexitätstheoretischen Rahmen, um die Expressivität von SSMs zu analysieren, was an jüngere grundlegende Arbeiten zu Transformern angelehnt ist (z. B. Strobl et al., 2024; Yang et al., 2024a).

Formales Modell: SSMs werden als Schichten formalisiert, die Eingabesequenzen über lineare Rekurrenzen ( $h_t = \text{gate}(x_t) \cdot h_{t-1} + \text{inc}(x_t)$ ) transformieren, gefolgt von nichtlinearen Ausgabefunktionen (modelliert als ReLU-aktivierte Feedforward Neural Networks).
Logischer Rahmen: Die Analyse nutzt die Lineare Temporale Logik über endliche Spuren (LTLf), spezifisch das Pure-Past-Fragment (PLTLf). Diese Logik erfasst Eigenschaften basierend auf Ereignisordnungen ohne Zählvorgänge.
- Erweiterungen: Die Logik wird durch modulare Prädikate (zur Verfolgung periodischer Positionen) und rückwärtsgerichtete Zähloperatoren ( $\overleftarrow{\#}$ ) erweitert, um die Fähigkeit zum Zählen von Vorkommen zu analysieren.
Konstruktive Beweise: Die Autoren liefern konstruktive Beweise, die zeigen, wie sich logische Formeln in SSM-Architekturen übersetzen lassen. Sie zeigen, wie spezifische temporale Operatoren (z. B. Yesterday, Previously, Since) und Zählmechanismen über spezifische Gate-Strukturen und Arithmetik-Einstellungen implementiert werden können.
Impossibility-Beweise: Umgekehrt etabliert das Paper Nicht-Expressibilitätsresultate unter Verwendung von Eigenschaften wie Monotonie in festpräzisen diagonalen SSMs, um zu beweisen, dass bestimmte nicht-star-freie Sprachen (z. B. $(aa)^*$ ) nicht erkannt werden können.

Zentrale Beiträge

1. Expressivitäts-Hierarchie von SSM-Varianten

Das Paper etabliert eine detaillierte Hierarchie der SSM-Fähigkeiten basierend auf Gating und Präzision:

Diagonal-Gated SSM (Fixed Precision):
- Fähigkeit: Erkennt alle Sprachen, die in PLTLf definierbar sind (äquivalent zu star-freien Sprachen und First-Order Logic with order, $FO[<]$).
- Limitierung: Kann keine nicht-star-freien Sprachen wie $(aa)^*$ erkennen, aufgrund einer Monotonie-Eigenschaft, bei der wiederholte identische Eingaben den Zustand stabilisieren lassen.
Diagonal-Gated SSM (Log-Precision):
- Fähigkeit: Erkennt Sprachen in PLTLf[ $\overleftarrow{\#}$ ], was die Expressivität durch rückwärtsgerichtendes Zählen auf nicht-reguläre und sogar nicht-kontextfreie Sprachen (z. B. $\{a^n b^n c^n\}$ ) erweitert.
Time-Invariant SSM (Fixed Precision):
- Fähigkeit: Erkennt Sprachen in UN-PLTLf[MOD] (Unäre PLTLf mit modularen Prädikaten). Sie können periodische Positionen verfolgen (z. B. Unterscheidung von geraden/ungeraden Indizes) mittels zyklischer Permutationsmatrizen, was es ihnen ermöglicht, $(aa)^*$ zu erkennen.
- Limitierung: Es wird vermutet, dass sie nicht in der Lage sind, Sprachen zu erkennen, die den Since-Operator erfordern (z. B. $L(a \mathcal{S} b)$ ), da ihnen eingabebedingte Gates fehlen, um aktuelle und vergangene Informationen dynamisch zu kombinieren.
Mixed SSM (Diagonal + Time-Invariant):
- Fähigkeit: Erkennt PLTLf[MOD] und bildet effektiv die Vereinigung der Diagonal- und Time-Invariant-Fähigkeiten ab. Dies entspricht der Klasse der regulären Sprachen in $AC^0$ .
- Log-Precision Erweiterung: Mit Log-Präzision erkennen sie PLTLf[ $\overleftarrow{\#}$ , MOD].

2. Arithmetische Präzision als entscheidender Faktor

Das Paper demonstriert rigoros, dass Log-Präzision strikt notwendig ist, um nicht-reguläre Zähl-Sprachen zu erkennen. Festbreitige Arithmetik beschränkt SSMs auf reguläre (oder star-freie) Sprachen, während Log-Präzision die Akkumulation von Zählungen ermöglicht, die für Sprachen wie $a^n b^n c^n$ erforderlich ist.

3. Systematischer Vergleich mit Transformern

Die Autoren bilden SSM-Varianten direkt auf bekannte Transformer-Expressivitätsresultate ab:

Diagonal SSM (Fixed Precision) $\approx$ Unique Hard-Attention Transformers (UHAT) ohne Positional Encodings (beide erfassen $FO[<]$).
Time-Invariant SSM $\approx$ UHAT mit Positional Encodings (UHAT+PE) (beide erfassen $FO[<, MOD]$).
Mixed SSM (Log-Precision) $\approx$ Average Hard-Attention Transformers (AHAT) (beide erfassen Zähl-Fähigkeiten, wobei SSMs auf rückwärtsgerichtendes Zählen beschränkt sind).
Arbitrary Gates: SSMs mit beliebigen Gates können alle regulären Sprachen erkennen, was den oberen Schranken komplexerer Transformer-Varianten entspricht.

Zentrale Ergebnisse

Theorem 1: Diagonale SSMs mit Fixed-Precision erkennen alle Sprachen in PLTLf.
Theorem 3: Diagonale SSMs mit Fixed-Precision können $(aa)^*$ nicht erkennen, was eine strikte Trennung von Time-Invariant SSMs in diesem Punkt beweist.
Theorem 4: Diagonale SSMs mit Log-Precision erkennen alle Sprachen in PLTLf[ $\overleftarrow{\#}$ ].
Theorem 7: Time-Invariant SSMs mit Fixed-Precision erkennen alle Sprachen in UN-PLTLf[MOD].
Korollar 8: Mixed SSMs mit Fixed-Precision erkennen alle regulären Sprachen in $AC^0$ .
Impossibility: Das Paper liefert Impossibility-Beweise, die zeigen, dass spezifische architektonische Entscheidungen (z. B. die Diagonal Fixed-Precision) fundamentale Engpässe schaffen, die durch keine Menge an Trainingsdaten oder Optimierung überwunden werden können.

Bedeutung und Behauptungen

Das Paper beansprucht, die erste Verbindung zwischen der Ausdrucksstärke von SSMs und formaler Logik hergestellt zu haben, was strukturelle Garantien darüber bietet, welche Muster theoretisch lernbar oder für spezifische SSM-Varianten bewweisbar unmöglich sind.

Fundamentale Erkenntnisse: Durch die Abgrenzung der "unmöglichen" Aufgaben (z. B. nicht-monotone Muster für Fixed-Precision Diagonal SSMs) ergänzt die Arbeit empirische Benchmarks, indem sie architektonische Grenzen unabhängig von der Trainingsdynamik identifiziert.
Architektonische Klarheit: Die Ergebnisse klären die Beziehung zwischen SSMs und Transformern und zeigen, dass SSMs durch Rekurrenz inhärent Positionsinformationen kodieren (analog zu Positional Encodings in Transformern), sich aber in ihren Zählmechanismen unterscheiden (rückwärtsgerichtendes Zählen vs. globale Attention).
Komplexitäts-Alignment: Die Befunde legen nahe, dass eingeschränkte SSMs (Diagonal/Time-Invariant mit Fixed Precision) wahrscheinlich innerhalb von $AC^0$ operieren, einer echten Teilmenge der zuvor von Merrill et al. (2024) etablierten $TC^0$ -Obergrenze. Dies impliziert, dass diese Architekturen möglicherweise nicht in der Lage sind, Paritäts-Sprachen oder andere Sprachen außerhalb von $AC^0$ ohne spezifische Modifikationen zu erkennen.

Die Autoren schließen, dass ihre Arbeit eine rigorose theoretische Basis schafft, die aufzeigt, dass die Wahl des Gating-Mechanismus und der arithmetischen Präzision fundamental bestimmt, welche Klasse von Sprachen ein SSM modellieren kann, unabhängig vom spezifischen verwendeten Trainingsverfahren.