🤖 machine learning

The Expressive Limits of Diagonal SSMs for State-Tracking

Dit artikel stelt vast dat de expressiviteit van $k$ -laagse diagonale complexe State-Space Models (SSM's) voor toestandstracking precies beperkt is tot oplosbare groepen met een subnormale reeks van lengte $k$ , wat een fundamentele theoretische barrière onthult voor niet-Abelse groepen en een empirische kloof tussen expressiviteit en leerbaarheid.

Oorspronkelijke auteurs: Mehran Shakerinava, Behnoush Khavari, Siamak Ravanbakhsh, Sarath Chandar

Gepubliceerd 2026-08-17

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Mehran Shakerinava, Behnoush Khavari, Siamak Ravanbakhsh, Sarath Chandar

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 om een reeks instructies te volgen die zijn interne stemming of positie veranderen. In de wereld van kunstmatige intelligentie wordt dit "sequence modeling" genoemd. De robot leest een verhaal woord voor woord, en met elk nieuw woord werkt hij zijn begrip bij van waar het verhaal naartoe gaat. Lange tijd waren de beroemdste robots (genaamd Transformers) hier erg goed in, maar ze waren ook ongelooflijk hongerig naar computerkracht. Dus hebben wetenschappers een nieuw, slanker type robot uitgevonden, een State-Space Model, of SSM. Denk aan een SSM als een robot met een kleine, efficiënte geheugenbank die zichzelf direct bijwerkt terwijl hij leest, in plaats van telkens het hele verhaal opnieuw te lezen.

Maar hier komt het lastige deel: alleen omdat een robot efficiënt is, betekent dat niet dat hij slim genoeg is om alles te doen. Sommige taken zijn als simpele wiskunde (getallen optellen), terwijl andere complexe puzzels zijn waarbij items in een specifieke volgorde geruild moeten worden. In de wiskunde worden deze puzzels vaak beschreven met behulp van "groepen", wat simpelweg chique regels zijn voor hoe dingen gecombineerd of geruild kunnen worden. Als de regels simpel en voorspelbaar zijn (zoals het optellen van getallen), kan de robot ze gemakkelijk aan. Maar als de regels rommelig zijn en afhangen van de volgorde van operaties (zoals het wisselen van drie verschillende gekleurde ballen, waarbij het wisselen van rood naar blauw iets anders is dan blauw naar rood), kan de robot in de war raken. Wetenschappers willen weten: wat is de absolute grens van wat deze efficiënte robots daadwerkelijk kunnen begrijpen? Kunnen ze de rommelige puzzels leren oplossen, of blijven ze steken bij de simpele?

Dit artikel duikt diep in die vraag door een specifieke, zeer efficiënte soort robot te testen, genaamd een "Diagonal SSM". De onderzoekers wilden zien of deze robots complexe statusveranderingen konden leren volgen, specifelijk die met betrekking tot niet-Abelse groepen (de rommelige, volgorde-afhankelijke puzzels). Ze ontdekten een harde wiskundige muur: een enkele laag diagonale robot kan deze rommelige puzzels simpelweg niet oplossen, hoe hard je ook probeert. Echter, als je twee of meer van deze robots op elkaar stapelt, krijgen ze theoretisch de kracht om ze op te lossen, maar alleen als de puzzel een specifieke, gelaagde structuur heeft (een "oplosbare groep").

Hier is de wending die het verhaal interessant maakt: zelfs al zouden de gestapelde robots deze puzzels in theorie kunnen oplossen, de onderzoekers ontdekten dat ze in de praktijk vaak falen. Het is also[t] een auto met een motor die krachtig genoeg is om een berg te beklimmen, maar de bestuurder (het trainingsalgoritme) blijft steeds in een berm vastlopen en vindt het pad omhoog niet. Het artikel bewijst dat de kracht aanwezig is in de architectuur, maar dat standaard trainingsmethoden moeite hebben om deze te ontsluiten, vooral voor de complexere, niet-Abelse taken.

De geheugenbank van de robot

Om te begrijpen wat de auteurs hebben gevonden, moeten we eerst kijken naar hoe deze "Diagonal SSMs" werken. Stel je een robot voor met een rij lichtschakelaars. Wanneer de robot een nieuw woord leest, bedient hij deze schakelaars op basis van een simpele regel. In een "Diagonal" SSM hangt de regel voor het bedienen van één schakelaar niet af van de andere schakelaars; elke schakelaar werkt onafhankelijk. Dit maakt de robot ongelooflijk snel en gemakkelijk te trainen, zoals een team van werkers die elk hun eigen taak uitvoeren zonder met elkaar te hoeven praten.

De onderzoekers testten deze robots op een spel genaamd "state-tracking". In dit spel krijgt de robot een reeks commando's (zoals "wissel de rode bal", "draai de blauwe bal") en moet hij de uiteindelijke opstelling van de ballen onthouden. Als de commando's simpel zijn en commuteren (wat betekent dat de volgorde niet uitmaakt, zoals 2 + 3 hetzelfde is als 3 + 2), is de robot een topper. Maar als de commando's niet commuteren (zoals sokken aantrekken vóór schoenen versus schoenen aantrekken vóór sokken), staat de robot voor een veel grotere uitdaging.

De theoretische muur: één laag versus vele lagen

Het artikel begint met een sterk wiskundig bewijs over wat een enkele laag robot kan doen. De auteurs lieten zien dat een enkele laag diagonale SSM fundamenteel beperkt is tot het oplossen van alleen "Abelse" puzzels — die waarbij de volgorde van operaties er niet toe doet. Hoe je de robot ook afstelt, als hij slechts één laag van deze onafhankelijke schakelaars heeft, kan hij de status van een complexe, niet-Abelse groep (zoals de permutaties van drie objecten, bekend als de groep $S_3$ ) niet bijhouden.

Het verhaal wordt echter spannender wanneer je lagen stapelt. De auteurs bewezen dat als je $k$ lagen van deze diagonale robots op elkaar stapelt, het team een puzzel kan oplossen als en slechts als de puzzel kan worden afgebroken in een keten van $k$ simpelere, Abelse stappen. Denk aan een estafette. Als de puzzel te complex is voor één hardloper, kun je het stokje overhandigen aan een tweede hardloper, die het weer doorgeeft aan een derde. Zolang de puzzel kan worden opgesplitst in een specifiek aantal eenvoudige, geordende stappen, kan een team van dat aantal robots de puzzel theoretisch oplossen. Dit betekent dat diepte (het toevoegen van meer lagen) de sleutel is tot het ontsluiten van complexere intelligentie, maar dat dit gepaard gaat met een strikte regel: je hebt precies evenveel lagen nodig als de puzzel "lagen" van complexiteit heeft.

De leergap: Theorie versus Realiteit

Dit is waar het plot dikker wordt. De auteurs stopten niet alleen bij de w математика; ze bouwden deze robots en probeerden ze te trainen. Ze testten enkelvoudige en dubbellaagse modellen op diverse taken, inclusief simpele optelling (Abels) en de lastige $S_3$ permutatiepuzzel (niet-Abels).

De resultaten waren een mix van succes en frustratie. Voor de simpele taken leerden de robots snel en konden ze zeer lange sequenties aan. Maar voor de complexe $S_3$ -taak, ook al zou de dubbellaagse robot volgens hun wiskunde krachtig genoeg moeten zijn om het op te lossen, faalde hij grotendeels. De robot kon het juiste patroon simpelweg niet leren, zelfs niet na duizenden pogingen.

De onderzoekers ontdekten dat het probleem niet was dat de robot het niet kon; de oplossing bestond daadwerkelijk binnen het ontwerp van de robot. Het was meer alsof de robot op zoek was naar een speld in een hooiberg, en de standaard trainingsmethode (gradient descent) de speld steeds miste. In één experiment probeerden ze de robot te "helpen" door hem heel dicht bij het juiste antwoord te laten starten. Toen ze dit deden, leerde de robot de taak plotseling razendsnel en kon hij sequenties aan die veel langer waren dan hij eerder had gezien. Dit suggereert dat de oplossing aanwezig is, verborgen in de "weight space" van de robot, maar dat de weg om die te vinden extreem smal en moeilijk te navigeren is met standaard training.

De Conclusie

Het artikel concludeert dat hoewel diagonale SSM's efficiënt zijn en theoretisch in staat zijn om complexe state-tracking problemen op te lossen als je genoeg lagen stapelt, er een enorme kloof bestaat tussen wat ze kunnen doen en wat ze daadwerkelijk leren. De wiskunde zegt dat een dubbellaagse robot de $S_3$ -puzzel kan oplossen, maar in de praktijk faalt hij meestal. Dit benadrukt een cruciale les voor AI-onderzoek: alleen omdat een model het potentieel heeft om slim te zijn, betekent dat nog niet dat het ook gemakkelijk zal leren om slim te zijn. De auteurs suggereren dat we, om deze kloof te overbruggen, misschien de manier waarop we deze modellen trainen moeten veranderen of wellicht hun architectuur licht moeten aanpassen (zoals het toestaan van iets meer interactie tussen de schakelaars) om het pad naar de oplossing minder glad te maken.

Kortom, deze efficiënte robots zijn als briljante studenten die de tekstuele kennis hebben om een moeilijk probleem op te lossen, maar telkens zakken voor het examen omdat ze niet weten hoe ze die kennis moeten toepassen. Het artikel brengt nauwkeurig in kaart wat ze in staat zijn, maar waarschuwt ons ook dat het daadwerkelijk laten presteren een veel grotere uitdaging is dan de wiskunde doet vermoeden.

Technische Samenvatting: De Expressieve Limieten van Diagonale SSM's voor State-Tracking

Probleemstelling

State-Space Models (SSM's) zijn opgekomen als efficiënte, paralleliseerbare alternatieven voor Transformers voor langetermijn-sequentiemodellering. Hun theoretische expressieve kracht blijft echter slecht begrepen, met name wat betreft hun vermogen om state-tracking taken uit te voeren. Deze taken, die het bijhouden en bijwerken van een verborgen toestand op basis van een sequentie van inputs omvatten (bijv. pariteitscontroles, modulaire optelling of permutatie-tracking), zijn nauw verwant aan reguliere talen en zijn cruciaal voor toepassingen zoals code-executie en programma-analyse.

Hoewel Transformers bekend staan om hun moeite met bepaalde state-tracking taken (specifiek die welke niet-oplosbare groepsoperaties vereisen), werd aanvankelijk verondersteld dat SSM's hierin zouden excelleren vanwege hun recurrente aard. Recent werk heeft aangetoond dat standaard SSM's (inclusclusief tijd-invariante en diagonale varianten) falen op zelfs eenvoudige oplosbare taken zoals pariteit. Dit artikel onderzoekt de precieze expressieve limieten van Input-Afhankelijke Complexe Diagonale (DCD) SSM's op sequentiële state-tracking taken, waarbij specifiek wordt gefocust op het volgen van eindige groepen. De kernvraag is: Welke klassen van groepen kan een $k$ -laagse DCD SSM theoretisch representeren, en kunnen standaard leeralgoritmen deze representaties betrouwbaar vinden?

Methodologie

De auteurs maken gebruik van een combinatie van groepstheoretische analyse en empirische evaluatie.

Theoretisch Kader

Modeldefinitie: De studie richt zich op DCD SSM's, waarbij de transitiematrix $A(x_t)$ diagonaal en complex-gewaard is, en afhankelijk is van de input $x_t$ . De toestand-update volgt een affine recursie: $h_t = A(x_t)h_{t-1} + b(x_t)$ .
Verbinding met Groepentheorie: De auteurs mappen state-tracking taken naar de simulatie van eindige groepen. Een model volgt een groep $G$ als het het cumulatieve product van een sequentie van groepelementen kan berekenen.
Single-Layer Analyse: De auteurs bewijzen dat een enkele-laagse DCD SSM geen enkele niet-Abelse groep kan volgen bij eindige precisie. Ze demonstreren dat zelfs met een input-afhankelijke bias-term $b(x_t)$ en een decoder, de commutatieve aard van diagonale matrices het model beperkt tot Abelse groepen.
Multi-Layer Analyse: Het artikel breidt dit uit naar $k$ $k$ -laagse DCD SSM's. Ze stellen een noodzakelijke en voldoende voorwaarde vast voor expressiviteit: Een $k$ $k$ -laagse DCD SSM kan een groep $G$ $G$ volgen als en slechts als $G$ $G$ een subnormale reeks van lengte $k$ met Abelse factoren bezit.
- Wiskundig betekent dit $G = G_k \trianglerighteq G_{k-1} \trianglerighteq \dots \trianglerighteq G_1 \trianglerighteq \{e\}$ , waarbij elke quotient $G_{i+1}/G_i$ Abel is.
- Dit resultaat identificeert het exacte expressieve bereik van $k$ -laagse DCD SSM's als de klasse van oplosbare groepen met een specifieke structurele diepte.
Constructieve Bewijsvoering: De auteurs bieden een concrete constructie voor een 2-laagse DCL SSM die de symmetrische groep $S_3$ (de kleinste niet-Abelse oplosbare groep) volgt door deze te deconstrueren in een cascade van twee Abelse automaten ( $C_2$ en $C_3$ ).

Empirische Evaluatie

De auteurs evalueren single- en twee-laagse varianten van verschillende SSM-architecturen (Mamba, Negative Mamba, AUSSM, en vereenvoudigde AUSSM) naast RNN's.

Taken: State-tracking op diverse groepen, waaronder Abelse groepen ( $C_2, C_6, C_{24}, C_{60}$ ), producten van cyclische groepen ( $C_2 \times C_4, C_3 \times C_6$ ) en oplosbare niet-Abelse groepen ( $S_3, A_4$ ). De niet-oplosbare groep $A_5$ is opgenomen als controlegroep.
Protocol: Modellen worden getraind op sequenties tot lengte 60 met behulp van curriculum learning en getest op generalisatie op sequenties tot lengte 1000.

Belangrijkste Bijdragen

Theoretische Karakterisering: Het artikel biedt de eerste precieze karakterisering van de expressieve kracht van diagonale SSM's. Het bewijst dat:
- Single-layer DCD SSM's beperkt zijn tot Abelse groepen.
- $k$ -laagse DCD SSM's beperkt zijn tot oplosbare groepen met een subnormale reeks van lengte $k$ .
- Dit stelt een strikt theoretisch voordeel van diepte vast voor het modelleren van niet-Abelse dynamiek binnen de diagonale restrictie.
Identificatie van de Leerbaarheidskloof: Hoewel de theorie bewijst dat 2-laagse DCD SSM's niet-Abelse groepen zoals $S_3$ kunnen representeren, laten de empirische resultaten zien dat standaard gradiëntgebaseerde optimalisatie faalt om deze oplossingen te leren. Modellen falen consistent in het generaliseren naar lange sequenties voor $S_3$ en $A_4$ , ondanks de theoretische capaciteit om dit wel te kunnen.
Inzicht in Initialisatie: De auteurs demonstreren dat het initialiseren van een model nabij de analytische oplossing (afgeleid van hun theoretische constructie) het model in staat stelt om te leren en te generaliseren. Dit suggereert dat de oorzaak van het falen niet ligt in een gebrek aan capaciteit in de gewichtsruimte, maar in de moeilijkheid van het optimalisatie-landschap om deze specifieke coderingen te vinden zonder begeleiding.

Resultaten

Abelse Groepen: Single-layer modellen (specifiek Negative Mamba en AUSSM) leren en generaliseren succesvol op Abelse taken (bijv. pariteit, modulair tellen).
Niet-Abelse Oplosbare Groepen: Multi-layer modellen (2-laags) die theoretisch in staat zijn om $S_3$ en $A_4$ te volgen, falen in de praktijk om te generaliseren. Ze behalen een hoge nauwkeurigheid op trainingslengtes, maar storten in bij langere testsequenties.
Niet-Oplosbare Groepen: Zoals verwacht, leert geen enkel model (inclusief multi-layer DCD SSM's) de niet-oplosbare groep $A_5$ .
Vergelijking met RNN's: RNN's, die geen theoretische expressiviteitsbarrière hebben voor deze taken, slagen over het algemeen in het leren en generaliseren, wat benadrukt dat het falen van SSM's specifiek is voor hun architecturale restricties en optimalisatiedynamiek, en niet enkel voor de moeilijkheid van de taak zelf.

Betekenis en Claims

Het artikel claimt een scherp onderscheid vast te stellen tussen expressiviteit en leerbaarheid in diagonale SSM's.

Expressiviteit: Diepte biedt een gedisciplineerd, theoretisch bewijsbaar pad om de expressieve kracht van diagonale SSM's te vergroten van Abelse naar oplosbare groepen. De auteurs definiëren de exacte grens van deze capaciteit met behulp van groepentheorie.
Leerbaarheid: De auteurs beargumenteren dat hoewel deze modellen de theoretische capaciteit bezitten om complexe state-tracking taken op te lossen, standaard trainingsalgoritmen moeite hebben met het ontdekken van de vereiste gewichtconfiguraties. Dit suggereert dat de "inductieve bias" van diagonaliteit, hoewel efficiënt, de ontdekking van niet-Abelse structuren actief kan hinderen.
Implicaties: Het werk suggereert dat het simpelweg stapelen van diagonale lagen onvoldoende is voor betrouwbare prestaties op niet-Abelse taken zonder betere optimalisatiestrategieën of architecturale aanpassingen (bijv. blok-diagonale structuren). Het roept op tot een scheiding van verantwoordelijkheden bij het evalueren van nieuwe sequentie-architecturen: de theoretische capaciteit van een model garandeert niet de praktische bruikbaarheid.

De auteurs concluderen dat toekomstige vooruitgang niet alleen vereist dat de expressieve horizon wordt uitgebreid (bijv. via blok-diagonale transities), maar ook dat er trainingsmethoden worden ontwikkeld die in staat zijn om betrouwbaar door het verlieslandschap te navigeren om oplossingen te vinden die in principe gegarandeerd bestaan.