Length Generalization Bounds for Transformers

Deze paper bewijst dat er geen berekenbare lengte-generalisatiegrenzen bestaan voor CRASP (en dus ook niet voor transformers) met twee lagen, maar levert wel een optimale, berekenbare grens voor het positieve fragment van CRASP en fixed-precision transformers.

De kern

Stel je voor dat je een superintelligente robot (een Transformer, het type AI dat achter modellen als ChatGPT zit) traint om een spelletje te spelen. Je geeft de robot duizenden voorbeelden van korte zinnen, zoals "a b a" of "a a b b". De robot leert het patroon.

De grote vraag is: Kan deze robot het spel ook spelen als we hem een heel lange zin geven, bijvoorbeeld met 10.000 letters, terwijl hij alleen korte zinnen heeft gezien? Dit noemen onderzoekers "lengte-generalisatie".

In dit paper onderzoeken de auteurs of we theoretisch kunnen garanderen dat zo'n robot dit altijd kan doen, en hoeveel voorbeelden hij daarvoor nodig heeft. Hier is wat ze hebben ontdekt, vertaald in simpele taal:

1. Het Grote Geheim: De "Onmogelijke" Robot

De auteurs hebben ontdekt dat voor de meeste moderne, krachtige AI-modellen (die we "Transformers" noemen) er geen garantie bestaat dat ze lengte-generalisatie kunnen leren.

De Analogie:
Stel je voor dat je een sleutelbos hebt om een reeks deuren te openen.

• Bij een simpele robot (met één laag) kun je zeggen: "Als je de eerste 100 deuren hebt geopend, weet je zeker dat je de 101e ook kunt openen."
• Maar bij een slimme robot (met twee lagen of meer) is het alsof de deuren naar een onbekend land leiden. De auteurs bewijzen dat er geen enkele formule of rekenregel bestaat die kan voorspellen hoeveel deuren je moet openen voordat je zeker weet dat je het land kunt betreden.

Het is alsof je probeert te voorspellen of een willekeurige wiskundige vergelijking een oplossing heeft. Soms is het antwoord "nee", en soms is het antwoord "ja", maar je kunt nooit van tevoren zeggen hoeveel tijd of hoeveel getallen je moet checken om het zeker te weten. Voor deze robots betekent dit: Je kunt nooit zeker weten of je genoeg trainingdata hebt gehad. Je kunt 100.000 voorbeelden geven, en de robot faalt nog steeds bij een iets langere zin.

2. De Uitzondering: De "Beperkte" Robot

Gelukkig is er een goed nieuws. De auteurs kijken naar een speciale, iets minder krachtige versie van de robot: de "Fixed-Precision Transformer". Dit is een robot die niet oneindig nauwkeurig kan rekenen, maar werkt met een vast aantal decimalen (zoals een rekenmachine met beperkte precisie).

De Analogie:
Stel je voor dat deze robot een rekenmachine is in plaats van een wiskundige genie. Hij kan niet tot in het oneindige tellen, maar wel tot een heel groot getal.

• Voor deze rekenmachine-robot kunnen we wel een garantie geven.
• Ze hebben bewezen dat als je deze robot traint, je hem wel kunt laten slagen voor langere zinnen, maar er is een prijs: je moet hem oefenen met zinnen die exponentieel langer zijn dan de zinnen die hij moet leren.

Wat betekent "exponentieel"?
Stel je voor dat je een robot traint om een woord van 10 letters te herkennen.

• Een normale robot zou misschien 20 of 30 letters nodig hebben om het te leren.
• Deze "Fixed-Precision" robot heeft echter misschien 1.000.000 letters nodig om hetzelfde te leren.
• Als je het woord verdubbelt naar 20 letters, moet hij misschien 1.000.000.000.000 letters zien.

Het is alsof je een kind leert tellen. Als je het leert tellen tot 10, moet je het misschien 100 keer oefenen. Maar als je het leert tellen tot 100, moet je het misschien een biljoen keer oefenen. Het is mogelijk, maar het kost enorm veel tijd en ruimte.

3. Waarom is dit belangrijk?

Vandaag de dag zien we dat AI-modellen soms heel goed zijn in het uitbreiden van hun kennis (bijvoorbeeld van korte zinnen naar lange zinnen), maar soms ook volledig falen. Dit hangt vaak af van toevalligheden, zoals hoe de robot is opgestart of welke leerinstellingen je kiest.

Dit paper legt uit waarom dit zo lastig is:

• Voor de krachtige modellen is het probleem fundamenteel onoplosbaar. Er is geen "magische formule" die zegt: "Als je 1000 voorbeelden ziet, werkt het altijd." Soms moet je oneindig veel voorbeelden zien, en dat is onmogelijk.
• Voor de beperkte modellen is het wel oplosbaar, maar de kosten (de hoeveelheid data die je nodig hebt) exploderen zo snel dat het in de praktijk vaak onhaalbaar wordt.

Samenvattend

De auteurs zeggen eigenlijk:

"We dachten dat we misschien een regel konden vinden die zegt: 'Als je AI maar lang genoeg traint, kan hij alles doen, ook met heel lange zinnen.' Maar dat is niet waar. Voor de slimste modellen is het een onoplosbaar raadsel. Voor de iets slimmere, maar beperkte modellen is het wel oplosbaar, maar dan moet je ze oefenen met zinnen die zo lang zijn dat ze de hele wereld vullen."

Dit verklaart waarom het zo moeilijk is om AI-modellen betrouwbaar te maken voor taken met zeer lange teksten (zoals het samenvatten van een heel boek), en waarom het soms lijkt alsof de AI "zomaar" faalt, zelfs als je denkt dat je hem goed hebt getraind.

Technische samenvatting

Probleemstelling

De kernvraag van dit onderzoek is of het mogelijk is om kwantitatieve garanties te geven voor lengte-generalisatie (length generalization) bij Transformers. Lengte-generalisatie verwijst naar het vermogen van een model om correct te voorspellen op invoer van willekeurige lengte, gegeven slechts een eindige trainingsset met invoer van beperkte lengte.

Hoewel empirisch onderzoek heeft aangetoond dat Transformers soms lengte-generalisatie vertonen, is dit fenomeen vaak onvoorspelbaar en afhankelijk van specifieke hyperparameters (zoals gewichtsinitialisatie en positiële encoding). Bestaande theoretische werken (zoals Huang et al., 2025) hebben aangetoond dat Transformers taal kunnen generaliseren in de limiet (asymptotisch), maar ze leveren geen niet-asymptotische grenzen op. Dat wil zeggen: ze geven geen berekenbare bovengrens $N$ aan voor de trainingslengte die nodig is om te garanderen dat het model ook op langere testen (lengte $> N$) correct presteert.

Het paper richt zich op de berekenbaarheid (computability) van dergelijke grenzen voor C-RASP (Counting RASP), een programmeertaal die expressief equivalent is aan Transformers met vaste precisie (buiten de attention-mechanismen om).

Methodologie

De auteurs gebruiken een combinatie van formele talentheorie, berekenbaarheidstheorie en computatieleertheorie om de probleemstelling aan te pakken:

1. Formalisatie via C-RASP:
   De auteurs analyseren Transformers via C-RASP, een logica die telpredicaten ($\# \phi$) en tijdsoperatoren gebruikt. Ze onderscheiden tussen de algemene klasse C-RASP en een positieve fragment, C-RASP+, waarbij alleen niet-negatieve coëfficiënten en vergelijkingen van de vorm $\sum \alpha_i \cdot \# \phi_i \sim c$ worden toegestaan.

2. Relatie met Leertheorie:
   Ze maken gebruik van een fundamenteel resultaat van Chen et al. (2025): het bestaan van een berekenbare lengte-generalisatiegrens is equivalent aan de beslisbaarheid van taal-equivalentie binnen een klasse van hypothesen. Als het onmogelijk is om te beslissen of twee programma's dezelfde taal accepteren, dan is er geen berekenbare grens voor lengte-generalisatie.

3. Reducties voor Onbeslisbaarheid:
   Om de onberekenbaarheid te bewijzen voor de algemene C-RASP, reduceren ze het probleem van het controleren op leegte van een C-RASP-taal naar het Hilbert's Tiende Probleem (het oplossen van Diophantische vergelijkingen in natuurlijke getallen). Omdat het Hilbert-probleem onbeslisbaar is, volgt hieruit dat het controleren op leegte (en dus equivalentie) voor C-RASP ook onbeslisbaar is.

4. Constructie voor Positieve Fragmenten:
   Voor het beperkte geval van C-RASP+ (en daarmee vaste precisie Transformers) reduceren ze de logica naar unary tijdslogica TL[-3] (met alleen strikt verleden operatoren). Ze analyseren de complexiteit van deze vertaling om een expliciete bovengrens voor de lengte-generalisatie af te leiden.

Belangrijkste Bijdragen en Resultaten

1. Onberekenbaarheid voor Algemene Transformers (Hoofdstuk 3)

De belangrijkste bevinding is een negatief resultaat: er bestaat geen algoritme dat een berekenbare lengte-generalisatiegrens kan bepalen voor Transformers, zelfs niet voor modellen met slechts twee lagen.

• Stelling 1.1 (Informeel): Er is geen algoritme om een C-RASP-programma (en dus een Transformer) perfect te leren, zelfs niet als het programma slechts twee lagen diep is.
• Redenering: De auteurs bewijzen dat het probleem van het bepalen of een C-RASP-taal leeg is, onbeslisbaar is door een reductie vanuit het Hilbert-probleem. Omdat taal-equivalentie onbeslisbaar is, is de lengtecomplexiteit (de maximale lengte van trainingsdata die nodig is om onderscheid te maken tussen hypothesen) niet berekenbaar.
• Gevolg: De benodigde trainingslengte moet sneller groeien dan elke berekenbare functie (zelfs sneller dan de Ackermann-functie). Dit betekent dat er geen theoretisch garantie bestaat dat een Transformer, getraind op een eindige dataset, lengte-generalisatie zal vertonen voor de algemene klasse.

2. Berekenbare Exponentiële Grens voor C-RASP+ (Hoofdstuk 4)

Als tegenhanger bieden ze een positief resultaat voor een beperkte subklasse: C-RASP+. Deze klasse komt overeen met fixed-precision Transformers (waarbij ook de attention-mechanismen tot een vaste precisie worden afgerond).

• Stelling 1.2 (Informeel): Om een C-RASP+-programma perfect te leren, is het noodzakelijk en voldoende om trainingsstrings te zien met een lengte die exponentieel is in de grootte van het programma.
• Methode: Ze tonen aan dat C-RASP+ kan worden gereduceerd tot de logica TL[-3]. Voor TL[-3] is bewezen dat als een formule vervulbaar is, er een bewijsstring bestaat met een lengte die polynomiëel is in de grootte van de formule. Omdat de vertaling van C-RASP+ naar TL[-3] een exponentiële "blow-up" veroorzaakt, is de uiteindelijke lengtegrens exponentieel.
• Optimaliteit: Ze bewijzen dat deze exponentiële grens scherp (tight) is in het slechtste geval. Er bestaan voorbeelden waarbij een string van exponentiële lengte daadwerkelijk nodig is om de taal te onderscheiden.

3. Implicaties voor Transformers (Hoofdstuk 5)

De resultaten worden direct gekoppeld aan Transformer-architecturen:

• Algemene Transformers: Omdat deze expressief equivalent zijn aan C-RASP, geldt de onberekenbaarheid. Geen enkel leeralgoritme kan garanderen dat het genoeg data heeft gezien om lengte-generalisatie te bereiken.
• Fixed-Precision Transformers: Deze corresponderen met C-RASP+. Voor hen geldt dat lengte-generalisatie wel mogelijk is, maar dat de trainingsdata tot een exponentieel lange lengte moet reiken om het model te garanderen.

Significantie en Discussie

De resultaten van dit paper hebben diepgaande theoretische en praktische implicaties:

1. Fundamentele Beperking: Het paper legt een fundamentele theoretische barrière bloot voor het trainen van Transformers voor lengte-generalisatie. Het verklaart waarom empirisch onderzoek vaak faalt om consistente generalisatie te garanderen: het probleem is in het algemeen onberekenbaar.
2. Verklaring voor Empirische Observaties: De auteurs speculeren dat de gevoeligheid van lengte-generalisatie voor initialisatie en hyperparameters een direct gevolg is van deze onberekenbaarheid. Omdat de vereiste trainingslengte onvoorspelbaar groot kan zijn (binnen de onberekenbare grenzen), kunnen kleine veranderingen in het trainingsproces leiden tot het al dan niet bereiken van de "kritieke lengte" die nodig is voor generalisatie.
3. Rol van Precision: Het paper benadrukt het cruciale onderscheid tussen "normale" Transformers (die theoretisch oneindige precisie kunnen simuleren via attention) en "fixed-precision" Transformers. Alleen door de precisie te beperken (wat in de praktijk vaak gebeurt door hardware-beperkingen) wordt het probleem beheersbaar (exponentieel in plaats van onberekenbaar), zij het met een hoge kostprijs in termen van benodigde data.
4. Richting voor Toekomstig Onderzoek: De bevindingen suggereren dat het zoeken naar algemene schaalwetten (scaling laws) voor lengte-generalisatie misschien een onmogelijke opgave is. In plaats daarvan moet de focus liggen op het beperken van de expressiviteit van modellen (bijv. via fixed-precision) of het ontwikkelen van specifieke trainingsstrategieën voor specifieke taakklassen.

Samenvattend biedt dit paper een rigoureuze theoretische onderbouwing voor de moeilijkheid van lengte-generalisatie bij Transformers en maakt een scherp onderscheid tussen de onberekenbaarheid van het algemene geval en de exponentiële complexiteit van het beperkte, maar praktisch relevante, geval.