Algorithmic Capture, Computational Complexity, and Inductive Bias of Infinite Transformers

Dit artikel definieert 'algorithmic capture' en toont aan dat onbeperkte transformers, ondanks hun universele expressiviteit, een inductieve bias vertonen die hen beperkt tot het leren van algoritmen met lage computationele complexiteit binnen de EPTHS-klasse, waardoor ze succesvol zijn bij eenvoudige taken maar falen bij complexere algoritmen.

De kern

Stel je voor dat je een superintelligente robot (een "Large Language Model" of LLM) hebt die je vraagt om een taak uit te voeren. Soms lijkt deze robot de taak perfect te begrijpen en kan hij hem oplossen, zelfs als de taak veel groter wordt dan wat hij ooit heeft geoefend. Maar soms faalt hij, ook al heeft hij de regels van de taak uit zijn hoofd geleerd.

Deze paper van Orit Davidovich en Zohar Ringel probeert het antwoord te vinden op de vraag: Wanneer heeft de robot de taak echt "begrepen" en wanneer heeft hij het gewoon geraden?

Hier is de uitleg in simpele taal, met een paar leuke vergelijkingen.

1. Het Verschil tussen "Gokken" en "Begrijpen" (Algorithmic Capture)

Stel je voor dat je een kind leert tellen.

• Statistisch raden: Het kind ziet dat je altijd "1, 2, 3" zegt. Als je vraagt "wat komt na 3?", zegt het "4" omdat het dat vaak heeft gehoord. Maar als je vraagt "wat komt na 100?", raakt het in paniek. Het heeft de patronen geleerd, niet de logica.
• Echt begrijpen (Algorithmic Capture): Het kind begrijpt het concept van "plus één". Het kan nu tellen tot 1 miljoen, of zelfs 1 biljoen, zonder dat het dat ooit heeft geoefend.

De auteurs noemen dit "Algorithmic Capture". Een model heeft een algoritme echt "gevangen" als het de logica zo goed heeft geleerd dat het het probleem kan oplossen, hoe groot het ook wordt, met slechts een heel klein beetje extra oefening.

2. De Robot heeft een "Voorkeur" (Inductive Bias)

De paper onderzoekt of de architectuur van deze robots (de "Transformers") hen helpt om complexe logica te leren, of juist in de weg zit.

De auteurs ontdekken dat deze robots een ingebouwde voorkeur hebben voor simpele taken.

• Wat kunnen ze wel? Taken die lijken op het zoeken in een lijst of het sorteren van kaarten. Dit is als het vinden van een specifieke speld in een hooiberg of het in orde zetten van speelkaarten. Dit is "goedkoop" voor de robot om te doen.
• Wat kunnen ze niet? Taken die erg complex zijn, zoals het vinden van de kortste route tussen twee punten in een enorm labyrint (Shortest Path) of het optimaliseren van een stroomnetwerk.

Het is alsof je een robot geeft die gewend is om snel te rennen op een vlakke weg. Als je hem vraagt om een berg op te klimmen (een complex probleem), faalt hij, zelfs als hij theoretisch sterk genoeg zou moeten zijn. Zijn "ontwerp" is niet gemaakt voor die zware klim.

3. De Rekenkracht-Limiet (Computational Complexity)

Dit is het meest fascinerende deel. De auteurs kijken naar wat er gebeurt als je de robot oneindig groot maakt (oneindig veel hersencellen). Je zou denken: "Hoe groter, hoe slimmer, dus hij kan alles!"

Maar ze ontdekken iets verrassends: Zelfs een oneindig grote robot heeft een snelheidslimiet.

• De Analogie van de Bibliotheek:
  Stel je voor dat de robot een bibliotheek moet doorzoeken om een boek te vinden.
  • Voor een simpele taak (zoals zoeken in een lijst) moet hij misschien 100 boeken controleren. Als de bibliotheek groter wordt, moet hij 10.000 boeken controleren. Dit is een lineaire of kwadratische groei. De robot kan dit aan.
  • Voor een complexe taak (zoals het kortste pad vinden) moet hij elke mogelijke route uitrekenen. Als de bibliotheek groter wordt, moet hij niet 10.000, maar 100.000.000 routes controleren. De tijd die hij nodig heeft, explodeert.

De paper bewijst dat de "rekenkosten" (hoeveel tijd en energie het kost om een antwoord te geven) voor deze robots te snel groeien voor complexe problemen. Zelfs als ze theoretisch alles kunnen uitrekenen, is de tijd die ze nodig hebben om het te doen zo enorm dat het in de praktijk onmogelijk is. Ze zijn dus "ingebouwd" om alleen simpele algoritmen te leren.

4. De Experimenten: Wat werkt en wat niet?

De auteurs hebben dit getest met echte experimenten:

• Succes: De robot leerde perfect om een lijst te sorteren (zoals het sorteren van nummers van klein naar groot) en om een patroon te herkennen (een "trigger" vinden en het volgende woord kopiëren). Dit zijn taken die binnen hun snelheidslimiet vallen.
• Mislukking: De robot faalde volledig bij het vinden van de kortste weg in een netwerk (Shortest Path) of het oplossen van een stroomprobleem (MinCut). Zelfs als ze de robot heel diep maakten (veel lagen), lukte het niet. Het probleem was te complex voor de "rekenmotor" van de robot.

Conclusie: Waarom is dit belangrijk?

Deze paper zegt ons iets heel belangrijks over de toekomst van AI:

Het is niet genoeg om alleen maar grotere modellen te bouwen. Als een taak te complex is voor de manier waarop deze modellen "denken" (hun inductieve bias), zullen ze die taak nooit echt leren, hoe veel data je ze ook geeft. Ze blijven dan hangen in het raden van patronen in plaats van het echt begrijpen van de logica.

Kort samengevat:
Deze robots zijn slimme "snelle renners" die uitstekend zijn in simpele, rechte lijnen (zoals sorteren). Maar als je ze vraagt om een complexe berg te beklimmen (zoals het oplossen van ingewikkelde netwerken), zullen ze falen, niet omdat ze niet slim genoeg zijn, maar omdat hun "schoenen" (hun architectuur) niet geschikt zijn voor die zware klim. Ze zijn gebouwd voor snelheid, niet voor zware, complexe logica.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Algorithmic Capture, Computational Complexity, and Inductive Bias of Infinite Transformers" van Davidovich en Ringel, in het Nederlands.

1. Probleemstelling

Het centrale vraagstuk in de studie van Large Language Models (LLMs) is of deze modellen echte "begrip" of algoritmisch redeneren vertonen, of dat ze slechts statistische correlaties exploiteren om domeinen te interpoleren. Bestaande benchmarks (zoals GSM-Symbolic) tonen aan dat prestaties vaak instabiel zijn bij veranderingen in symbolische templates, wat wijst op een gebrek aan robuuste algoritmische uitvoering.

Echter, het definiëren van "begrip" is vaak filosofisch en vaag. Dit artikel probeert dit probleem aan te pakken door te focussen op algoritmisch leren: het vermogen van een model om te generaliseren naar willekeurige probleemgroottes ($T$) met minimale aanpassing. De auteurs willen vaststellen of de inductieve bias van Transformers (de kernarchitectuur van LLMs) hen toestaat om complexe algoritmen te "grokken" (volledig leren) of dat ze beperkt zijn tot statistische benaderingen.

2. Methodologie

De auteurs analyseren oneindig breed (infinite-width) Transformers in twee regimes:

• Het "Lazy" Regime: Waar het netwerk convergeren naar een Neural Tangent Kernel (NTK) of Neural Network Gaussian Process (NNGP). Hier worden de parameters niet significant aangepast tijdens training; het gedrag wordt bepaald door de kernel.
• Het "Rich" Regime: Waar feature learning optreedt en de parameters zich aanzienlijk ontwikkelen, maar nog steeds geanalyseerd worden via oneindige limieten.

Kernconcept: Algorithmic Capture
De auteurs definiëren "Algorithmic Capture" formeel als het vermogen van een netwerk om een algoritme te generaliseren naar willekeurige probleemgroottes $T$ met een gecontroleerde foutmarge en een minimale steekproefaanpassing. Specifiek vereist dit:

1. Training op een budget $P_0$ voor kleine probleemgroottes tot $T_0$.
2. Een fijne afstemming (fine-tuning) op grotere groottes $T > T_0$ met slechts een logaritmisch budget ($O(\log(T/T_0))$).
3. Als het netwerk meer dan logaritmische data nodig heeft om te generaliseren, heeft het het algoritme niet echt "gevangen" (gegrokt), maar slechts geïnterpoleerd.

De analyse focust op de inference-time computatiecomplexiteit (het aantal FLOPs nodig om een voorspelling te maken) van deze oneindige netwerken en vergelijkt dit met de theoretische complexiteit van de doelalgoritmen (binnen de klasse EPTHS: Efficient Polynomial Time Heuristic Schemes).

3. Belangrijkste Bijdragen

1. Formele Definitie van Algoritmisch Leren:
   De auteurs bieden een verifieerbare definitie voor wat het betekent dat een neurale netwerk een algoritme "vangt". Dit onderscheidt echt algoritmisch leren van statistische interpolatie door de eis te stellen dat generalisatie naar grotere $T$ slechts een logaritmische toename in trainingsdata vereist.

2. Bovenste Grenzen voor Complexiteit:
   Ze leiden bovenste grenzen af voor de inference-complexiteit van oneindig brede Transformers:

   • In het lazy regime (NTK) is de complexiteit van het evalueren van de predictor $O(P \cdot N_{MC} \cdot T^3)$, wat resulteert in een heuristische complexiteit van $O(T^{3+\epsilon})$.
   • In het rich regime (feature learning), onder de aanname dat de discrepantie tussen het oneindige en eindige netwerk schaalt als $P^\gamma/N$, daalt de complexiteit naar $O(T^{2+\epsilon})$.
   • Conclusie: Transformers hebben een inductieve bias naar algoritmen met lage complexiteit (binnen $O(T^{2+\epsilon})$ of $O(T^{3+\epsilon})$).

3. Empirische Validatie van Gevangen vs. Niet-Gevangen Algoritmen:

   • Gevangen: Transformers slagen erin om taken zoals Induction Heads (zoekpatronen vinden en kopiëren) en Sorteren te generaliseren. De kosten voor fine-tuning op grotere $T$ groeien logaritmisch, wat wijst op succesvol algoritmisch leren.
   • Niet-Gevangen: Transformers falen om taken zoals het Kortste Pad Probleem (SPP) en Max Flow / Min Cut te vangen, zelfs bij zeer diepe netwerken (tot 40 lagen). De kosten voor fine-tuning groeien superlineair (meer dan logaritmisch), wat aantoont dat ze deze complexere algoritmen niet hebben "gegrokt".

4. Resultaten

• Inductieve Bias: Ondanks dat oneindig brede Transformers universeel expressief zijn (ze kunnen willekeurig complexe functies theoretisch representeren), zijn ze in de praktijk beperkt door hun inductieve bias. Ze kunnen alleen algoritmen leren die binnen hun inferentie-complexiteitsgrenzen vallen.
• Complexiteitsgrenzen:
  • Taken met lage complexiteit (zoals sorteren, $O(T \log T)$ of $O(T^2)$) worden succesvol geleerd.
  • Taken met hogere complexiteit (zoals MinCut, theoretisch $O(T^3)$ in de context van hun grafen, of SPP met specifieke moeilijkheden) worden niet geleerd.
  • De paper toont aan dat feature learning (rich regime) wel de steekproefcomplexiteit (sample complexity) kan verbeteren, maar niet de inference-complexiteit verlaagt onder de fundamentele grenzen van de kernel-architectuur.
• Tabel 1 Samenvatting: De paper presenteert een overzicht (Tabel 1) dat de inference-complexiteit koppelt aan het regime (Lazy vs. Rich) en de resulterende maximale heuristische complexiteit die het netwerk kan vangen ($O(T^{3+\epsilon})$ vs $O(T^{2+\epsilon})$).

5. Betekenis en Conclusie

Deze studie biedt een scherp theoretisch raamwerk om te onderscheiden tussen statistische memorisatie en echt algoritmisch redeneren in LLMs.

• Fundamentele Beperking: Het resultaat suggereert dat Transformers, zelfs in hun oneindig brede en diepste vorm, inherent beperkt zijn tot het leren van algoritmen binnen een bepaalde complexiteitsklasse (EPTHS). Ze kunnen geen complexe algoritmen "grokken" die meer rekenkracht vereisen dan wat hun inferentiemechanisme toelaat.
• Implicaties voor LLM-onderzoek: Het verklaart waarom LLMs goed presteren op simpele patronen en zoekopdrachten, maar worstelen met complexe wiskundige of grafische redeneringen die diepere algoritmische structuren vereisen.
• Toekomstig Onderzoek: De auteurs wijzen erop dat verdere verfijning nodig is om te begrijpen waarom sommige taken binnen de theoretische grenzen (zoals SPP) toch falen, wat suggereert dat de inductieve bias nog complexer is dan alleen de globale complexiteitsgrens.

Kortom, de paper concludeert dat "grokking" niet zomaar een kwestie is van meer data of diepere netwerken, maar dat er een fundamentele barrière bestaat in de inference-computational complexity van de Transformer-architectuur die bepaalt welke algoritmen überhaupt leersbaar zijn.