🤖 machine learning

Barriers to Universal Reasoning With Transformers (And How to Overcome Them)

Dit artikel toont aan dat, hoewel standaard Chain-of-Thought Transformers vanwege inherente beperkingen in kopiëren en ophalen niet generaliseren naar langere redeneersporen, ze lengte-generaliseerbare Turing-compleetheid kunnen bereiken door gebruik te maken van een groeiende vocabulaire met unieke signaaltokens en waardeveranderingscoderingen om deze barrières te overwinnen.

Oorspronkelijke auteurs: Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn

Gepubliceerd 2026-04-29

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn

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

Het Grote Plaatje: De "Slimme Student" die Vergeet

Stel je een zeer slimme student (de Transformer) voor die leert complexe puzzels op te lossen. Om hen te helpen, geven docenten hen een "schraapblad" waar ze hun gedachten stap voor stap kunnen opschrijven. Dit heet Chain-of-Thought (CoT).

Vorig onderzoek toonde aan dat deze student met dit schraapblad theoretisch elke puzzel kon oplossen, hoe moeilijk ook. Het was alsof ze een superkracht kregen.

Echter, de auteurs van dit paper ontdekten een groot gebrek: De student is geweldig in het oplossen van puzzels waar ze op geoefend hebben, maar faalt klakkeloos wanneer de puzzels langer worden. Als je hen traint op een puzzel van 10 stappen, kunnen ze er geen van 20 stappen oplossen, zelfs niet als de logica hetzelfde is. Ze lijken een "plafond" te bereiken waar hun redenering bezwijkt.

Dit paper vraagt zich af: Waarom gebeurt dit, en kunnen we het oplossen?

De Twee Grote Wegversperringen

De auteurs ontdekten dat de hersenen van de student (de Transformer) twee specifieke "glitches" hebben die hen beletten om te generaliseren naar langere taken.

1. De "Fotokopieer"-Glitch (Herhaald Kopiëren)

Stel je voor dat de student een lange lijst met instructies uit een boek naar hun schraapblad moet kopiëren.

Het Probleem: Als de lijst kort is, kunnen ze het makkelijk kopiëren. Maar als de lijst lang is, raken ze in de war. Ze kunnen niet betrouwbaar de exacte regel vinden die ze moeten kopiëren uit het midden van een lange pagina zonder hun plaats te verliezen.
De Claim van het Paper: Standaard Transformers worstelen met het "kopiëren" van willekeurige reeksen informatie wanneer de lengte verandert. Ze raken verdwaald in het midden van de tekst.

2. De "Laatst Gezien"-Glitch (Retrieval)

Stel je voor dat de student een variabele bijhoudt, zoals "De waarde van X".

Het Probleem: Als de student schrijft "X = 5", later "X = 7" en daarna weer "X = 5", moeten ze weten wat de huidige waarde is. In een lange keten van gedachten vergeet de student vaak welke "5" de meest recente was. Ze kunnen een oude "5" van het begin van de pagina oppakken in plaats van de nieuwe.
De Claim van het Paper: Het model worstelt met het vinden van de laatste update in een lange geschiedenis van wijzigingen. Het is alsof je probeert te vinden wanneer je voor het laatst een appel at in een dagboek met 1.000 pagina's vol vermeldingen.

De Oplossing: Een Nieuwe Manier om het Schraapblad te Schrijven

De auteurs stellen twee slimme trucs voor om deze glitches te verhelpen. Ze veranderen niet de hersenen van de student; ze veranderen alleen hoe de instructies op het schraapblad worden geschreven.

Truc #1: De "Naamkaartjes" (Signpost Tokens)

Om de Fotokopieer-Glitch op te lossen, suggereren de auteurs om elk item in de puzzel een uniek ID-kaartje of "Naamkaartje" te geven.

Hoe het werkt: In plaats van te zeggen "Ga naar regel 50", zegt de instructie "Ga naar het item met Naamkaartje #42".
Waarom het helpt: Zelfs als de lijst langer wordt, hoeft de student niet te tellen om regel 50 te vinden. Ze zoeken gewoon naar het specifieke Naamkaartje. Het is alsof je een bibliotheek hebt waar elk boek een unieke barcode heeft, zodat je niet de hele plank hoeft te scannen om degene te vinden die je nodig hebt.

Truc #2: Het "Wijzigingslogboek" (Value-Change Encoding)

Om de Laatst Gezien-Glitch op te lossen, suggereren de auteurs om te veranderen wat de student opschrijft.

Oude Manier: De student schrijft elke keer de volledige huidige staat op (bijv. "X is 5", dan "X is 7", dan "X is 5"). Dit creëert veel ruis en maakt het moeilijk om te weten welke de nieuwste is.
Nieuwe Manier: De student schrijft alleen wat veranderde op.
- In plaats van "X is 7" te schrijven, schrijven ze "X veranderde van 5 naar 7".
- In plaats van weer "X is 5" te schrijven, schrijven ze "X veranderde van 7 naar 5".
Waarom het helpt: Om de huidige waarde te vinden, telt de student gewoon de wijzigingen. Als ze "5 naar 7" zien en daarna "7 naar 5", weten ze dat de huidige waarde 5 is. Het is alsof je een grootboek van transacties bijhoudt in plaats van je volledige banksaldo elke keer opnieuw te schrijven wanneer je een dollar uitgeeft.

De Resultaten: Theorie versus Realiteit

Het paper test deze ideeën op twee manieren:

Het Wiskundig Bewijs (Theorie):
- Slecht nieuws: Als je vasthoudt aan een vaste set woorden (een eindig alfabet) en standaard schrijfstijlen, kan de student niet leren puzzels op te lossen die langer zijn dan een bepaalde complexiteit (specifiek, ze kunnen niet verder gaan dan een klasse van problemen die TC0 wordt genoemd). Ze zitten wiskundig vast.
- Goed nieuws: Als je de student toestaat een oneindig aanbod unieke Naamkaartjes (Signposts) te gebruiken en de "Wijzigingslogboek"-methode toepast, kunnen ze theoretisch elke puzzel oplossen, hoe lang ook.
De Experimenten (Realiteit):
- De auteurs trainden kleine computermodellen vanaf nul op drie moeilijke taken:
  - Pariteit: Tellen of een reeks getallen een oneven of even aantal 1-en heeft.
  - Booleaanse Evaluatie: Complexe logische puzzels oplossen (Waar/Niet-waar).
  - S5 Permutatie: Het bijhouden van de beweging van 5 objecten die worden omgewisseld.
- Het Resultaat:
  - Modellen getraind met de standaard methode faalden wanneer de puzzels langer werden.
  - Modellen getraind met Naamkaartjes en Wijzigingslogboeken waren veel beter in het oplossen van langere puzzels die ze nooit eerder hadden gezien.
- Ze testten dit ook op gigantische, vooraf getrainde AI-modellen (zoals Llama en Mistral). Zelfs zonder ze opnieuw te trainen, maakte het simpelweg prompten om Naamkaartjes en Wijzigingslogboeken in hun antwoorden te gebruiken ze aanzienlijk slimmer in het oplossen van lange, moeilijke problemen.

De Conclusie

Het paper concludeert dat Chain-of-Thought geen magie is. Gewoon een AI vertellen om "stap voor stap na te denken" is niet genoeg als de manier waarop het denkt vatbaar is voor verdwalen in lange lijsten.

Om AI echt betrouwbaar te maken in langetermijnredenering, moeten we de "gedachten" zo formatteren dat de twee belangrijkste valkuilen worden vermeden:

Geef elke stap een uniek Naamkaartje zodat niets verloren gaat.
Noteer alleen Wijzigingen zodat het model niet in de war raakt door oude informatie.

Door de opmaak van de redenering te verhelpen, kunnen we AI-modellen helpen hun huidige limieten te doorbreken en veel moeilijkere problemen op te lossen.

1. Probleemstelling

Hoewel Chain-of-Thought (CoT)-prompting empirisch de prestaties van Transformers heeft verbeterd en theoretisch is aangetoond dat het hun expressiviteit verhoogt tot Turing-compleetheid, blijft er een kritieke kloof bestaan: Kunnen Transformers leren om CoT-redenering te generaliseren naar lengtes die langer zijn dan die tijdens het training werden gezien?

Bestaande empirische bewijzen suggereren dat de nauwkeurigheid van Transformers scherp afneemt naarmate de lengte van de CoT-trace toeneemt, zelfs bij algoritmische en logische taken. Het artikel onderzoekt of de theoretische claim van Turing-compleetheid standhoudt onder de strengere eis van lengte-generaliseerbare leerbaarheid. Specifiek wordt de volgende vraag gesteld:

Staand standaard CoT-formaten Transformers toe om problemen buiten de complexiteitsklasse $\text{TC}^0$ (threshold-circuits met constante diepte) op te lossen bij generalisatie naar langere sequenties?
Welke specifieke structurele barrières voorkomen deze generalisatie?
Kunnen deze barrières worden overwonnen door specifieke formatteerstrategieën?

2. Methodologie

De auteurs maken gebruik van een combinatie van theoretisch formalisme en empirische validatie:

Theoretisch Kader

De studie maakt gebruik van recente theoretische kaders voor lengtegeneralisatie van Transformers:

C-RASP: Een formalisme voor redeneren over Transformers met eindige alfabetten en positionele encoding. Lidmaatschap impliceert garanties voor lengtegeneralisatie.
C-RASP:* Een uitbreiding van C-RASP die een oneindig alfabet toestaat (specifiek, onbegrensde signaal-tokens) en lokale match-predicaten.
Leermodel: De auteurs hanteren een geïdealiseerd leermodel waarbij een reeks Transformers, getraind op toenemende invoerlengtes, convergeert naar één onderliggend algoritme. Generalisatie is gegarandeerd als de taak binnen deze formalismen kan worden uitgedrukt.

Empirische Opzet

Taken: Drie algoritmische redeneertaken werden geselecteerd:
1. Pariteit: Bepalen of het aantal 1-en in een binaire string even of oneven is.
2. Booleaanse Evaluatie: Het evalueren van de waarheidswaarde van geneste logische formules.
3. S5 Permutatie: Het bijhouden van de staat van 5 objecten na een reeks wisselbewerkingen.
Modellen:
- Vanaf Nul: GPT-2-modellen (25M parameters) getraind op CoT-traces met en zonder specifieke formatteering.
- Voorgeladen LLM's: Zero-shot en few-shot prompting-experimenten op Qwen2.5-7B, Mistral-Small-24B en Llama-3.3-70B.
Formatteervarianten:
- Naive CoT: Standaard sequentiële redenering.
- Signaal-tokens: Toewijzen van unieke identificatoren (bijv. <34>) aan specifieke posities of bewerkingen om willekeurige adressering mogelijk te maken.
- Waarde-wijzigingsencoding: In plaats van de volledige staat bij elke stap te loggen, logt het model alleen wijzigingen in waarden (bijv. 1 -> 0) of registreert het expliciet wanneer een waarde onveranderd blijft.

3. Belangrijkste Bijdragen & Theoretische Resultaten

Bijdrage 1: De Limiet van Eindige Alfabetten (Het Negatieve Resultaat)

De auteurs bewijzen dat onder standaard positionele encoding en een eindig alfabet, Transformers met CoT niet kunnen generaliseren naar lengtes om problemen buiten $\text{TC}^0$ op te lossen.

Stelling 3.4: Als een taal $L$ een CoT-trace heeft die uitdrukbaar is in C-RASP (met positionele primitieven), dan is $L$ definieerbaar in $\text{TC}^0$ .
Implicatie: Hoewel CoT theoretisch Turing-compleetheid toestaat, wordt de leerbaarheid van dergelijke simulaties begrensd door $\text{TC}^0$ als het vocabulaire vaststaat. De voordelen in expressiviteit vertalen zich niet naar lengte-generaliseerbare leerbaarheid.

Bijdrage 2: Barrières Overwinnen met Oneindige Alfabetten (Het Positieve Resultaat)

Het artikel identificeert twee kernbarrières voor lengtegeneralisatie:

Herhaald Kopiëren: De moeilijkheid om willekeurige strings naar nieuwe posities te kopiëren.
Ophalen van Laatste Voorkomen: De moeilijkheid om de meest recente waarde van een variabele op te halen wanneer meerdere updates plaatsvinden (niet-uniek ophalen).

Om deze te overwinnen, stellen de auteurs een constructie voor met gebruik van C-RASP*:

Signaal-tokens: Toewijzen van een unieke, onbegrensde token (uit een oneindig alfabet) aan elke tapepositie of bewerkingstap. Dit lost de kopieerbarrière op door willekeurige indexering mogelijk te maken zonder absolute identiteiten te hoeven onthouden.
Waarde-wijzigingsencoding: In plaats van de volledige staat te loggen, logt de CoT alleen transities (bijv. "waarde veranderde van $x$ naar $y$ "). De huidige staat wordt hersteld door de netto-wijzigingen te tellen ten opzichte van de beginsituatie. Dit lost de ophaalbarrière op door de huidige waarde een functie te maken van tellingen in plaats van een zoektocht naar het "laatste" voorkomen.
Stelling 3.8: Transformers met CoT kunnen lengte-generaliseren om elke Turing-machine te simuleren als ze een oneindig alfabet van signaal-tokens gebruiken en berekeningen coderen via waarde-wijzigingen. De lengte van de CoT-trace blijft lineair in de gesimuleerde runtime.

4. Empirische Resultaten

Training vanaf Nul

Pariteit: Standaard CoT faalde in generalisatie buiten de trainingslengtes. Waarde-wijzigingsencoding maakte robuuste generalisatie mogelijk tot $2\times$ de trainingslengte.
Booleaanse Evaluatie & S5 Permutatie: Deze moeilijkere taken (buiten $\text{TC}^0$ ) faalden met naive CoT. Het toevoegen van signaal-tokens verbeterde de lengtegeneralisatie aanzienlijk, hoewel S5 uitdagend bleef vanwege potentiële "shortcuts" (heuristieken) die het model kon benutten.
Binaire Permutatie: Een variant van S5 met hoge herhaling. Naive en alleen Signaal-tokens CoT's faalden door fouten in "niet-uniek ophalen". Het combineren van Signaal-tokens + Waarde-wijziging leverde de beste resultaten op, wat de theoretische noodzaak van beide mechanismen bevestigt.

Prompting van Voorgeladen LLM's

Signaal-tokens: Het gebruik van natuurlijke getallen als signaal-hints in few-shot prompts verbeterde de prestaties op Booleaanse en S5-taken voor alle geteste LLM's (7B tot 70B), vooral bij langere sequentielengtes.
Waarde-wijziging: Bij een code-uitvoeringstaak (bijhouden van variabele toewijzingen) verbeterde het verstrekken van inline commentaar dat expliciet waarde-wijzigingen logde (bijv. # node a: 9 -> 0) de nauwkeurigheid van het eindantwoord aanzienlijk ten opzichte van standaard code-formatteering, zelfs zonder tussenliggende redeneerstappen.

5. Betekenis en Conclusie

Hedefherdefiniëring van CoT-succes: Het artikel stelt dat het succes van CoT niet inherent is aan het "denkproces" zelf, maar zwaar afhankelijk is van de formatteering van de trace. Standaard CoT-formaten falen vaak in generalisatie omdat ze de beperkingen schenden die nodig zijn voor leerbaarheid (localiteit en translatie-invariantie).
Theoretische Grenzen: Het verduidelijkt dat Turing-compleetheid voor Transformers conditioneel is. Het geldt voor expressiviteit (het hard-coden van een oplossing) maar niet voor leerbaarheid (het trainen van een model om te generaliseren), tenzij specifieke structurele hulpmiddelen (oneindige alfabetten/signaal-tokens) worden geboden.
Praktische Richtlijnen: De bevindingen bieden actiegerichte principes voor het verbeteren van LLM-prestaties bij moeilijke redeneertaken:
1. Gebruik Index-hints: Markeer posities of stappen expliciet met unieke identificatoren om ophalen te ondersteunen.
2. Log Wijzigingen, Geen Staten: Formatteer redeneertraces om staatsovergangen te benadrukken in plaats van volledige staat-dumps om ophaal-ambiguïteit te voorkomen.
Toekomstige Richtingen: Het werk suggereert dat toekomstige pretraining-data en CoT-schema's met deze theoretische beperkingen in gedachten moeten worden ontworpen om het volledige computationele potentieel van Transformers op redeneertaken met een lange horizon te ontsluiten.

Samenvattend demonstreert het artikel dat hoewel Transformers theoretisch in staat zijn tot universeel redeneren, het realiseren van deze capaciteit op een lengte-generaliseerbare manier specifieke architecturale en formatteerbarrières vereist om te overwinnen door het gebruik van signaal-tokens en waarde-wijzigingsencoding.