🤖 machine learning

On the Expressiveness of State Space Models via Temporal Logics

Dit artikel analyseert de expressieve kracht van state space models (SSM's) met behulp van temporele logica, waarbij wordt aangetoond dat hun capaciteiten variëren van reguliere talen tot niet-reguliere talen afhankelijk van gating-mechanismen en rekenkundige precisie, terwijl deze bevindingen systematisch worden vergeleken met transformer-architecturen.

Oorspronkelijke auteurs: Eric Alsmann, Lowejatan Noori, Martin Lange

Gepubliceerd 2026-01-28

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Eric Alsmann, Lowejatan Noori, Martin Lange

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een robot probeert te leren een verhaal te lezen en de volgorde van gebeurtenissen te begrijpen. In de wereld van Kunstmatige Intelligentie zijn er twee belangrijke soorten "lezers" (architecturen) die om de baan concurreren: de beroemde Transformers (zoals de modellen die de huidige chatbots aansturen) en de opkomende sterren genaamd State Space Models (SSM's).

Dit paper is een theoretisch onderzoek naar de "denkkracht" van SSM's. De auteurs vragen niet hoe goed deze modellen presteren op een specifieke test; in plaats daarvan vragen ze: "Wat is de absolute grens van wat deze modellen kunnen begrijpen, ongeacht hoeveel we ze trainen?"

Om dit te beantwoorden, gebruiken ze een speciale "logische taal" (Temporal Logic) als meetlat. Hier is een uitsplitsing van hun bevindingen met behulp van eenvoudige analogieën.

1. De twee belangrijkste soorten SSM's

Het paper verdeelt SSM's in twee hoofdvormen op basis van hoe ze informatie verwerken:

Diagonal-Gated SSM's (De "Strikte Boekhouders"): Deze modellen hebben een regel waarbij hun interne "poorten" (schakelaars die de informatiestroom regelen) kunnen veranderen op basis van het huidige woord dat ze lezen, maar ze moeten "diagonaal" blijven. Denk hierbij aan een rekenmachine waarbij je de getallen die je optelt kunt veranderen, maar waarbij je de kolommen niet met elkaar kunt mengen.
Time-Invariant SSM's (De "Constante Klokken"): Deze modellen hebben poorten die nooit veranderen, ongeacht welk woord ze lezen. Ze zijn als een metronoom of een klok; ze tikken met dezelfde snelheid, ongeacht het verhaal dat wordt verteld.

2. Het Precisieprobleem: Liniaal versus Rolmaat

De auteurs keken ook naar hoe "precies" de wiskunde binnen deze modellen is.

Fixed-Precision (Vaste precisie): Stel je een liniaal voor met slechts 10 streepjes. Hoe lang het verhaal ook is, je kunt niets kleiner meten dan die streepjes. Dit is vergelijkbaar met standaard computerwiskunde (floating-point).
Log-Precision (Logaritmische precisie): Stel je een rolmaat voor die automatisch langer en gedetailleerder wordt naarmate het verhaal langer wordt. Als het verhaal 100 woorden lang is, heeft je liniaal 100 streepjes; als het 1.000 woorden is, heeft het 1.000 streepjes. Dit maakt het mogelijk om veel nauwkeuriger te tellen.

3. Wat kunnen ze daadwerkelijk begrijpen?

De "Strikte Boekhouders" (Diagonal SSM's)

Met een simpele liniaal (Fixed-Precision): Ze zijn goed in het begrijpen van de volgorde van gebeurtenissen. Ze kunnen zeggen: "A gebeurde vóór B" of "A gebeurde, toen B, en toen C". Echter, ze hebben een grote blinde vlek: Ze kunnen niet tellen in cycli.
- De Analogie: Als je hen vraagt een patroon te herkennen zoals "een even aantal 'a's" (bijv. aa, aaaa, aaaaaa), falen ze. Omdat hun wiskunde monotoon is (het gaat alleen maar omhoog of blijft gelijk), raken ze uiteindelijk "gestrikt" en kunnen ze het verschil niet meer zien tussen 2 'a's en 4 'a's.
Met een groeiende rolmaat (Log-Precision): Als je hen het vermogen geeft om precies te tellen, worden ze veel slimmer. Ze kunnen nu exact tellen hoe vaak er in het verleden iets is gebeurd. Ze kunnen complexe patronen begrijpen zoals "Het aantal 'a's is gelijk aan het aantal 'b's is gelijk aan het aantal 'c's."

De "Constante Klokken" (Time-Invariant SSM's)

Met een simpele liniaal: Deze modellen zijn slecht in het bijhouden van complexe "sinds toen"-relaties (bijv. "Sinds de laatste keer dat we een 'b' zagen, hebben we dan een 'a' gezien?"). Maar ze hebben een superkracht: Ze kunnen tellen in cirkels.
- De Analogie: Omdat hun interne mechanisme een constante cyclus is, zijn ze uitstekend in het weten: "Is dit het 2e, 4e of 6e woord?" Ze kunnen gemakkelijk het "even aantal 'a's"-patroon herkennen waar de Strikte Boekhouders bij faalden.
Met een groeiende rolmaat: Ze kunnen beide: zowel in cirkels tellen als totale aantallen tellen.

De "Hybride" (Mixed SSM's)

Als je beide soorten lagen combineert (sommige Strikte Boekhouders, sommige Constante Klokken), krijg je het beste van twee werelden. Ze kunnen zowel de volgorde, cycli als het tellen begrijpen. Het paper laat zien dat deze hybride modellen bijna elk "regulier" patroon kunnen herkennen dat je kunt bedenken, tot aan een bepaalde complexiteitsgrens.

4. Hoe vergelijken ze zich met Transformers?

De auteurs vergeleken hun bevindingen met wat we al weten over Transformers:

Diagonal SSM's (Fixed-Precision) zijn ongeveer gelijkwaardig aan Transformers zonder positionele aanwijzingen (ze kennen de volgorde van woorden, maar niet hun exacte positie).
Time-Invariant SSM's zijn gelijkwaardig aan Transformers met Positional Encodings (ze weten precies waar ze zich in de zin bevinden).
Het Grote Verschil: Transformers met "global attention" (zoals het type Average Hard-Attention) kunnen het gehele verhaal in één keer bekijken om dingen vooruit en achteruit te tellen. SSM's kijken door hun aard echter alleen naar het verleden (wat ze al gelezen hebben). Daarom zijn SSM's strikt minder krachtig dan de meest geavanceerde Transformers als het gaat om het tellen van zaken die later in de sequentie gebeuren.

5. De "Onmogelijke" Taken

Het belangrijkste punt is de lijst met dingen die deze modellen niet kunnen, ongeacht hoeveel je ze traint:

Een Fixed-Precision Diagonal SSM kan nooit leren om het verschil te zien tussen een even en een oneven aantal herhaalde items (zoals aa vs aaa). Dit is een harde architecturale limiet, geen trainingsfout.
Om deze limiet te doorbreken, moet je ofwel de architectuur veranderen (time-invariant lagen toevoegen) of de wiskundige precisie verhogen (de groeiende rolmaat gebruiken).

Samenvatting

Beschouw deze modellen als verschillende soorten bibliothecarissen:

Diagonal (Fixed): Goed in het lezen van een boek in volgorde, maar raakt in de war als er gevraagd wordt om specifieke patronen te tellen.
Time-Invariant: Goed in het tellen van pagina's (even/oneven), maar heeft moeite met complexe "sinds toen"-verhalen.
Hybride: De ultieme bibliothecaris die beide kan, maar nog steeds niet vooruit kan kijken naar het volgende hoofdstuk om dingen te tellen.

Het paper bewijst dat deze beperkingen in het DNA van de architectuur zitten. Je kunt een "Fixed-Precision Diagonal" bibliothecaris niet trainen om een "Tellende" bibliothecaris te worden; je moet ze een beter hulpmiddel geven (log-precisie) of een andere hersenstructuur (gemengde lagen) om dat te bereiken.

Technische Samenvatting: Over de Expressiviteit van State Space Models via Temporele Logica

Probleemstelling

State Space Models (SSM's) zijn naar voren gekomen als een concurrerend alternatief voor Transformer-architecturen voor sequentiemodellering, met name voor grote taalmodellen. Hoewel de empirische vooruitgang echter snel gaat, blijft het theoretische fundament met betrekking tot de expressieve kracht van SSM's onderbelicht vergeleken met Transformers. Het centrale probleem dat wordt aangepakt, is het bepalen van welke klassen talen en patronen verschillende SSM-varianten theoretisch kunnen representeren, onafhankelijk van de trainingsdynamiek. Specifiek onderzoekt het artikel hoe twee belangrijke architecturale dimensies de expressiviteit beïnvloeden:

Gating-mechanismen: Het onderscheid tussen tijd-invariante gates (constante matrices, bijv. S4), diagonaal-gated mechanismen (input-afhankelijke diagonale matrices, bijv. S6), en arbitraire gates.
Arithmetische Precisie: Het onderscheid tussen fixed-width arithmetic (constante bits, bijv. standaard floating-point) en log-precision arithmetic (precisie die logaritmisch schaalt met de inputlengte).

De auteurs beogen deze varianten te mappen naar formele logische fragmenten en complexiteitsklassen om rigoureuze ondergrenzen vast te stellen en fundamentele architecturale knelpunten te identificeren.

Methodologie

De auteurs hanteren een logisch en complexiteitstheoretisch kader om de expressiviteit van SSM's te analyseren, wat aansluit bij recent fundamenteel werk over Transformers (bijv. Strobl et al., 2024; Yang et al., 2024a).

Formeel Model: SSM's worden geformaliseerd als lagen die inputsequenties transformeren via lineaire recurrences ( $h_t = \text{gate}(x_t) \cdot h_{t-1} + \text{inc}(x_t)$ ), gevolgd door niet-lineaire outputfuncties (gemodelleerd als ReLU-geactiveerde Feedforward Neural Networks).
Logisch Kader: De analyse maakt gebruik van Linear Temporal Logic over finite traces (LTLf), specifiek het pure-past fragment (PLTLf). Deze logica legt eigenschappen vast op basis van gebeurtenisvolgorde zonder te tellen.
- Extensies: De logica wordt uitgebreid met modulaire predicaten (om periodieke posities bij te houden) en backward-looking counting operators ( $\overleftarrow{\#}$ ) om het vermogen om het aantal voorkomens te tellen te analyseren.
Constructieve Bewijzen: De auteurs leveren constructieve bewijzen waarmee zij aantonen hoe logische formules naar SSM-architecturen vertaald kunnen worden. Ze laten zien hoe specifieke temporele operatoren (bijv. Yesterday, Previously, Since) en telmechanismen geïmplementeerd kunnen worden via specifieke gate-structuren en arithmetische instellingen.
Onmogelijkheidsbewijzen: Omgekeerd stelt het artikel onmogelijkheidsresultaten vast met behulp van eigenschappen zoals monotoniciteit in fixed-precision diagonale SSM's om aan te tonen dat bepaalde niet-star-vrije talen (bijv. $(aa)^*$ ) niet herkend kunnen worden.

Belangrijkste Bijdragen

1. Expressiviteitshierarchie van SSM-varianten

Het artikel stelt een gedetailleerde hiërarchie vast van de capaciteiten van SSM's op basis van gating en precisie:

Diagonal-Gated SSM (Fixed Precision):
- Capaciteit: Herkent alle talen die definieerbaar zijn in PLTLf (equivalent aan star-free languages en First-Order Logic with order, $FO[<]$).
- Beperking: Kan geen niet-star-vrije talen zoals $(aa)^*$ herkennen vanwege een monotoniciteitseigenschap waarbij herhaalde identieke inputs de staat laten stabiliseren.
Diagonal-Gated SSM (Log-Precision):
- Capaciteit: Herkent talen in PLTLf[ $\overleftarrow{\#}$ ], wat de expressiviteit uitbreidt naar het includeren van niet-reguliere en zelfs niet-context-vrije talen (bijv. $\{a^n b^n c^n\}$ ) via backward-looking counting.
Time-Invariant SSM (Fixed Precision):
- Capaciteit: Herkent talen in UN-PLTLf[MOD] (Unary PLTLf met modulaire predicaten). Ze kunnen periodieke posities bijhouden (bijv. het onderscheiden van even/oneven indices) met behulp van cyclische permutatiematrices, waardoor ze $(aa)^*$ kunnen herkennen.
- Beperking: Er wordt vermoed dat ze niet in staat zijn om talen te herkennen die de Since-operator vereisen (bijv. $L(a \mathcal{S} b)$ ) omdat ze geen input-afhankelijke gates hebben om huidige en verleden informatie dynamisch te combineren.
Mixed SSM (Diagonal + Time-Invariant):
- Capaciteit: Herkent PLTLf[MOD], wat effectief de unie vormt van de diagonal en time-invariant capaciteiten. Dit komt overeen met de klasse van reguliere talen in $AC^0$ .
- Log-Precision Extensie: Met log-precision herkennen ze PLTLf[ $\overleftarrow{\#}$ , MOD].

2. Arithmetische Precisie als Cruciale Bepaler

Het artikel demonstreert rigoureus dat log-precision strikt noodzakelijk is voor het herkennen van niet-reguliere tel-talen. Fixed-width arithmetic beperkt SSM's tot reguliere (of star-vrije) talen, terwijl log-precision de accumulatie mogelijk maakt die nodig is voor talen zoals $a^n b^n c^n$ .

3. Systematische Vergelijking met Transformers

De auteurs mappen SSM-varianten direct naar bekende Transformer-expressiviteitsresultaten:

Diagonal SSM (Fixed Precision) $\approx$ Unique Hard-Attention Transformers (UHAT) zonder positional encodings (beiden vatten $FO[<]$).
Time-Invariant SSM $\approx$ UHAT met Positional Encodings (UHAT+PE) (beiden vatten $FO[<, MOD]$).
Mixed SSM (Log-Precision) $\approx$ Average Hard-Attention Transformers (AHAT) (beiden vatten tel-capaciteiten, hoewel SSM's beperkt zijn tot backward-looking counting).
Arbitrary Gates: SSM's met arbitraire gates kunnen alle reguliere talen herkennen, wat overeenkomt met de bovengrenzen van complexere Transformer-varianten.

Belangrijkste Resultaten

Theorem 1: Diagonale SSM's met fixed-precision herkennen alle talen in PLTLf.
Theorem 3: Diagonale SSM's met fixed-precision kunnen $(aa)^*$ niet herkennen, wat een strikte scheiding aantoont van time-invariant SSM's op dit punt.
Theorem 4: Diagonale SSM's met log-precision herkennen alle talen in PLTLf[ $\overleftarrow{\#}$ ].
Theorem 7: Time-invariant SSM's met fixed-precision herkennen alle talen in UN-PLTLf[MOD].
Corollary 8: Mixed SSM's met fixed-precision herkennen alle reguliere talen in $AC^0$ .
Onmogelijkheid: Het artikel biedt onmogelijkheidsbewijzen die aantonen dat specifieke architecturale keuzes (bijv. diagonal fixed-precision) fundamentele knelpunten creëren die geen enkele hoeveelheid trainingsdata of optimalisatie kan overwinnen.

Betekenis en Claims

Het artikel claimt de eerste verbinding te bieden tussen de expressieve kracht van SSM's en formele logica, waarbij structurele garanties worden geboden over welke patronen theoretisch leerbaar of bewezen onmogelijk zijn voor specifieke SSM-varianten.

Fundamentele Inzichten: Door de "onmogelijke" taken te definiëren (bijv. niet-monotone patronen voor fixed-precision diagonal SSM's), vult het werk empirische benchmarks aan door architecturale limieten te identificeren die onafhankelijk zijn van de trainingsdynamiek.
Architecturale Helderheid: De resultaten verhelderen de relatie tussen SSM's en Transformers, waarbij wordt aangetoond dat SSM's positionele informatie inherent coderen via recurrente structuren (analoog aan positional encodings in Transformers), maar verschillen in hun telmechanismen (backward-looking versus globale aandacht).
Complexiteitsafstemming: De bevindingen suggereren dat beperkte SSM's (diagonal/time-invariant met fixed precision) waarschijnlijk binnen $AC^0$ opereren, een strikte deelverzameling van de $TC^0$ bovengrens die eerder door Merrill et al. (2024) is vastgesteld. Dit impliceert dat deze architecturen mogelijk niet in staat zijn om pariteit of andere talen buiten $AC^0$ te herkennen zonder specifieke modificaties.

De auteurs concluderen dat hun werk een rigoureuze theoretische baseline vaststelt, die laat zien dat de keuze van het gating-mechanisme en de arithmetische precisie fundamenteel bepaalt voor welke klasse van talen een SSM in staat is om te modelleren, ongeacht de specifieke trainingsprocedure die wordt gebruikt.