🤖 AI

On the Ability of Transformers to Verify Plans

Dit paper introduceert C*-RASP om aan te tonen dat decoder-only transformers voor een grote klasse van klassieke planningsdomeinen wiskundig bewezen lange plannen kunnen verifiëren, zelfs wanneer zowel de sequentielengte als het vocabularium tijdens het testen groeien.

Oorspronkelijke auteurs: Yash Sarrof, Yupei Du, Katharina Stein, Alexander Koller, Sylvie Thiébaux, Michael Hahn

Gepubliceerd 2026-03-23

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yash Sarrof, Yupei Du, Katharina Stein, Alexander Koller, Sylvie Thiébaux, 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

Titel: Kunnen AI's plannen maken? Nee, maar ze kunnen wel controleren of een plan klopt (als het plan netjes is)

Stel je voor dat je een enorme, ingewikkelde legpuzzel hebt. Een kunstmatige intelligentie (een 'Transformer', zoals de technologie achter ChatGPT) probeert de puzzel op te lossen. Vaak lukt het hen om een stukje te leggen, maar als de puzzel heel groot wordt, raken ze in de war. Ze vergeten waar ze waren, doen dingen die niet mogen, of stoppen te vroeg. De wetenschap heeft lang geprobeerd uit te leggen waarom dit gebeurt.

Dit paper doet iets anders. In plaats van de AI te vragen om de puzzel op te lossen, vragen we haar: "Kijk eens naar dit plan. Klopt het?"

De onderzoekers ontdekten dat AI's hierin veel beter zijn, maar alleen als het plan een bepaald soort "netheid" heeft. Hier is de uitleg in simpele taal:

1. Het Probleem: De "Grote Boek" en de "Kleine Boek"

Stel je voor dat je een AI traint met een boek van 10 pagina's. Als je diezelfde AI dan een boek van 100 pagina's geeft, faalt hij vaak. Hij heeft de regels niet echt geleerd; hij heeft ze alleen uit het hoofd geleerd voor de kleine versie.

In de wereld van planning (zoals het plannen van een robot die ballen verplaatst) wordt het nog moeilijker. Niet alleen wordt het plan langer, maar er komen ook steeds meer objecten bij.

Vaste Wereld: Je traint met 5 ballen en test met 5 ballen (maar een langere route).
Variabele Wereld: Je traint met 5 ballen, maar test met 500 ballen.

De onderzoekers wilden weten: Kan een AI leren om te controleren of een plan klopt, zelfs als het plan langer is en er veel meer ballen in zitten dan tijdens het leren?

2. De Oplossing: De "C*-RASP" Regelspelletjes

Om dit te begrijpen, hebben de onderzoekers een nieuw soort "regelspel" bedacht, genaamd C-RASP*. Denk hierbij aan een setje wiskundige regels die beschrijven hoe een AI in zijn hoofd moet denken om een taak goed te kunnen doen.

Ze ontdekten dat er twee soorten plannen zijn:

Soort A: De "Netjes" Plannen (Well-Formed & Delete-Free)
- De Analogie: Stel je voor dat je een wasmachine gebruikt. Als je een shirt in de wasmachine doet, is het eruit. Als je het eruit haalt, is het er niet meer. Er is geen verwarring. Elke actie verandert de situatie op een voorspelbare manier.
- Het Resultaat: AI's kunnen deze plannen perfect controleren, zelfs als het plan 100 keer langer is dan waar ze voor getraind zijn en er 1000 ballen bij komen. Ze hebben de "logica" begrepen, niet alleen de voorbeelden.
Soort B: De "Chaos" Plannen (STRIPS met Voorwaardelijke Effecten)
- De Analogie: Stel je voor dat je een knop indrukt, maar wat er gebeurt, hangt af van een geheim dat niemand kent. Soms verandert de knop de lichten, soms niet, en soms verandert hij de temperatuur. Het is een "Flip-Flop" situatie: je moet precies weten wat er laatst is gebeurd om te weten wat er nu is.
- Het Resultaat: AI's falen hier volledig. Zelfs als ze veel oefenen, raken ze in de war bij langere plannen. De structuur van dit soort plannen is te ingewikkeld voor de manier waarop deze AI's nu werken.

3. De Grootte van de Objecten (Het "Alfabet")

Een belangrijk deel van dit onderzoek is dat ze een nieuwe manier hebben bedacht om te kijken naar AI's die met steeds meer objecten werken.

Oude manier: AI's zien woorden als vaste blokken. Als je ze leert met "Hond" en "Kat", weten ze niet wat ze met "Paard" moeten doen als ze dat nooit hebben gezien.
Nieuwe manier (C-RASP):* De onderzoekers laten zien dat als een AI leert om te kijken naar relaties (bijvoorbeeld: "Is dit object hetzelfde als dat object?") in plaats van de namen van de objecten zelf, het wel kan generaliseren. Het is alsof je leert de regels van het voetbal te begrijpen, in plaats van de namen van de spelers te onthouden. Als je de regels kent, kun je een wedstrijd spelen met een heel nieuw team.

4. Wat betekent dit voor de toekomst?

De onderzoekers zeggen: "Het probleem is niet dat AI's dom zijn, maar dat we de problemen verkeerd formuleren."

Als je een probleem oplost door het te "versimpelen" (bijvoorbeeld door te zorgen dat elke actie duidelijk is en niets onvoorspelbaars doet), dan kunnen AI's het perfect doen.
Als je een probleem laat zoals het echt is (met alle complexe, voorwaardelijke regels uit de echte wereld), dan zakken AI's in elkaar.

Conclusie in één zin:
AI's zijn uitstekende "controleurs" van lange plannen, zolang die plannen maar een duidelijke, logische structuur hebben; zodra het te veel op een raadsel lijkt, raken ze de draad kwijt. De kunst is dus om problemen zo te ontwerpen dat ze voor de AI "netjes" zijn.

Titel: Over het vermogen van Transformers om plannen te verifiëren

Auteurs: Yash Sarrof, Yupei Du, Katharina Stein, Alexander Koller, Sylvie Thiébaux, Michael Hahn.

1. Het Probleem

Hoewel Large Language Models (LLMs) gebaseerd op Transformers indrukwekkende prestaties leveren in veel domeinen, is hun succes in het domein van AI-planning (het berekenen van een reeks acties om een doelsituatie te bereiken) inconsistent. Bestaande benchmarks tonen aan dat Transformers vaak de wereldtoestand kwijtraken, onuitvoerbare acties voorstellen of stoppen voordat het doel is bereikt, vooral naarmate plannen langer worden.

De huidige literatuur analyseert deze falen voornamelijk empirisch, maar er ontbreekt een heldere theoretische onderbouwing voor wanneer generalisatie (het kunnen hanteren van langere plannen dan tijdens het trainen) te verwachten is. Een specifiek probleem is dat bestaande theorieën over lengte-generalisatie vaak aannemen dat het vocabularij (de set objecten) tijdens het testen hetzelfde blijft als tijdens het trainen. In realistische planningsscenario's kan het aantal objecten echter toenemen, wat de effectieve grootte van het invoeralphabet vergroot.

2. Methodologie

De auteurs analyseren het vermogen van decoder-only Transformers om te verifiëren of een gegeven plan correct een specifiek planningsprobleem oplost. Ze richten zich op de vraag: Kan een transformer leren om lange plannen te verifiëren als het alleen is getraind op korte plannen?

Om dit te beantwoorden, introduceren ze een nieuw theoretisch raamwerk:

C-RASP:* Dit is een uitbreiding van het bestaande C-RASP (Counting RASP) formalisme. Waar C-RASP alleen lengte-generalisatie kan garanderen bij een vast vocabularij, is C*-RASP ontworpen om generalisatie te garanderen onder gelijktijdige groei van de sequentielengte (aantal acties) en de vocabulairegrootte (aantal objecten).
Symbolic Limit Transformer: De auteurs definiëren een theoretisch grensmodel (een "Symbolic Limit Transformer") dat voldoet aan strakke beperkingen:
- Translatie-invariantie: Interacties tussen tokens mogen alleen afhangen van relatieve afstanden, niet van absolute posities of specifieke object-ID's.
- Lokaal: Interacties verdwijnen als de relatieve afstand groter is dan een bepaalde bandbreedte.
Match Predicate: Een kerncomponent van C*-RASP is de "Match Predicate" ( $\chi$ ). Deze stelt het model in staat om te controleren of twee tokens (bijvoorbeeld een actie en een voorwaarde) verwijzen naar dezelfde objecten, zonder de absolute namen van die objecten te hoeven memoriseren. Dit is cruciaal voor generalisatie naar nieuwe objecten.
Theoretische Analyse: De auteurs analyseren verschillende klassen van planningsdomeinen (STRIPS, Delete-Free, Well-Formed, Conditional Effects) om te bepalen of deze binnen C*-RASP vallen.
Empirische Validatie: Ze trainen GPT-2-achtige modellen op drie aangepaste domeinen: Heavy Grippers, Colors, en Lights Out. Voor elk domein maken ze varianten die vallen onder de theoretische categorieën (bijv. een "Well-Formed" variant vs. een standaard "STRIPS" variant).

3. Belangrijkste Bijdragen

Introductie van C-RASP:* Een nieuw formalisme dat lengte-generalisatie garandeert voor Transformers wanneer het aantal objecten (het alfabet) toeneemt tijdens het testen. Dit vult een belangrijke lacune in de theoretische literatuur op.
Theoretische Grenzen van Generalisatie:
- Positieve Resultaten: Planverificatie is in C*-RASP (en dus generaliseerbaar) voor Delete-Free domeinen (acties hebben alleen positieve effecten) en Well-Formed domeinen (elk effect verandert de toestand noodzakelijkerwijs).
- Negatieve Resultaten: Planverificatie voor algemene STRIPS-domeinen en domeinen met Conditionele Effecten valt niet in C*-RASP. Deze problemen vereisen het oplossen van taken die equivalent zijn aan de "Flip-Flop" of "Parity" talen, die bewezen niet generaliseren voor Transformers.
Structuur bepaalt Leerbaarheid: De paper toont aan dat de structuur van het planningsprobleem (de dynamiek van acties en toestanden) de bepalende factor is voor generalisatie, niet alleen de complexiteit of het aantal acties.
Empirische Bevestiging: Experimenten bevestigen de theorie: modellen generaliseren perfect naar langere plannen en meer objecten in Well-Formed en Delete-Free domeinen, maar falen (op willekeurig niveau) in STRIPS en Conditional Effects domeinen, zelfs bij een vast aantal objecten.

4. Resultaten

Theoretisch:
- Voor Delete-Free en Well-Formed domeinen kan een Transformer een algoritme leren dat werkt voor willekeurig lange plannen en willekeurig veel objecten, mits getraind op kortere voorbeelden.
- Voor STRIPS (zonder extra beperkingen) en Conditionele Effecten is lengte-generalisatie onmogelijk voor Transformers, omdat het vereist dat het model de "laatste" actie die een toestand veranderde onthoudt (een Flip-Flop probleem) of een pariteitsberekening uitvoert.
Empirisch:
- Heavy Grippers & Colors: De "Well-Formed" en "Delete-Free" varianten bereikten bijna 100% nauwkeurigheid op Out-of-Distribution (OOD) data (langere plannen, meer objecten).
- STRIPS (Colors): De standaard STRIPS variant liet een daling in prestaties zien naarmate de planlengte toenam.
- Lights Out: De variant met conditionele effecten presteerde op willekeurig niveau (chance level), terwijl de "Well-Formed" variant (met een exponentieel groter aantal actieschema's) perfect generaliseerde. Dit onderstreept dat een betere formulering van het probleem (well-formedness) de leerbaarheid drastisch verbetert.

5. Betekenis en Impact

Verklaring van Inconsistentie: De paper biedt een theoretische verklaring waarom LLMs inconsistent presteren in planning: het hangt af van of het specifieke probleemformulering valt binnen de expressiviteit van C*-RASP.
Praktische Richtlijnen: Het resultaat suggereert dat planners en onderzoekers planningsproblemen kunnen "herformuleren" naar Well-Formed of Delete-Free varianten om het succes van Transformer-modellen te maximaliseren. Bijvoorbeeld, het omzetten van een probleem met conditionele effecten naar een verzameling van specifieke acties (well-formed) kan de generalisatiecapaciteit van het model redden.
Brede Toepassbaarheid: Het C*-RASP raamwerk en het concept van de "Symbolic Limit Transformer" gaan verder dan alleen planning; ze bieden een manier om te redeneren over de generalisatiecapaciteit van Transformers in elk domein waar het vocabularij tijdens het testen kan groeien (bijv. met index-hints of variabele entiteiten).
Beperkingen: De theorie geldt voor standaard Transformers zonder "Chain of Thought" (scratchpads). Het toepassen van deze inzichten op plan-generatie (in plaats van alleen verificatie) blijft een uitdaging vanwege de hogere computationele complexiteit van generatie.

Conclusie:
De auteurs tonen aan dat Transformers wel degelijk in staat zijn om te generaliseren naar langere plannen en meer objecten, maar alleen als de onderliggende structuur van het planningsdomein bepaalde eigenschappen bezit (zoals well-formedness). Door deze structurele beperkingen te begrijpen en te benutten, kan de betrouwbaarheid van AI in planningstaken aanzienlijk worden verbeterd.