Analysis of Optimality of Large Language Models on Planning Problems

Titel: Analyse van de Optimaliteit van Large Language Models op Planningsproblemen

Auteurs: Bernd Bohnet, Michael C. Mozer, et al. (Google DeepMind)
Datum: April 2026

---

1. Probleemstelling

Traditionele AI-planningsproblemen, zoals het Blocksworld-domein (het verplaatsen van gestapelde blokken van een start- naar een doelformatie), zijn recentelijk herbeoordeeld in het tijdperk van Large Language Models (LLM's). Eerdere studies suggereerden dat LLM's fundamenteel tekortschoten in redeneren en generalisatie voor planningsopgaven. Echter, nieuwere benchmarks tonen aan dat frontier-modellen (zoals GPT-5 en Gemini 2.5 Pro) in staat zijn om complexe plannen te genereren.

Het centrale probleem van dit onderzoek is echter niet alleen of een model een oplossing kan vinden, maar hoe het redeneert en of het optimale oplossingen produceert. Bestaande benchmarks meten vaak alleen succes/falen (binair), wat de kwaliteit van het plan en de structurele complexiteit verbergt. De auteurs willen onderzoeken of LLM's werkelijk systematisch redeneren of dat ze vertrouwen op heuristieken en semantische priors (voorafgaande kennis) die inefficiënt kunnen zijn.

2. Methodologie

Topologische Framing: De $P^*$-Graph

De kern van de methodologie is het vertalen van het Blocksworld-probleem naar een generaliseerde $P^*$- ("Path-Star") grafiek.

• Structuur: De "Tafel" fungeert als een centrale wortelknooppunt. Elke verticale stapel blokken vormt een disjuncte tak (vertakking).
• Isomorfisme: Het plannen in Blocksworld is structureel isomorf aan het traverseren van deze $P^*$-grafiek. Om een doelblok te bereiken, moet het model de juiste tak identificeren en de afhankelijkheidsketen (de blokken erboven) systematisch ontmantelen.
• Doel: Door deze mapping te gebruiken, kunnen de auteurs testen of LLM's de globale topologie begrijpen of lokaal heuristisch redeneren.

Dataset en Curricula

De auteurs hebben een synthetische dataset gegenereerd met vier specifieke curricula om verschillende complexiteitsassen te isoleren:

1. High Towers (Diepte): Een vaste breedte (12 torens) met toenemende torenhoogte (tot 1000 blokken). Test lang-horizon redeneren.
2. Harvest (Breedte/Compositie): Een vast aantal doelblokken per toren, maar toenemend aantal torens (tot 207). Test het sequentiëren van meerdere subdoelen.
3. Interleaved Harvest: Elke toren bevat twee verweven doelblokken, wat onafhankelijke subproblemen onmogelijk maakt en kruis-toren afhankelijkheden vereist.
4. Grand Challenge: Gelijktijdige schaling van diepte, breedte en aantal doelblokken.

Abstract Graph-Rewriting (Isomorfisme)

Om te voorkomen dat modellen vertrouwen op semantische priors (zoals het concept van "zwaartekracht" of "stapelen"), werd een geabstraheerde grafiek-herformulering ontwikkeld. Hierin worden blokken vervangen door abstracte knooppunten en acties door grafiek-herschrijfregels (bijv. DETACH_NODE, ATTACH_NODE). Dit dwingt het model om puur topologisch te redeneren zonder domain-specifieke hints.

Evaluatie en Vergelijking

• Modellen: Gebruik van Gemini 3.0 Pro (met "reasoning tokens" of chain-of-thought) vergeleken met klassieke planners zoals LAMA-2011 (een "satisficing" planner die snelheid verkiest boven optimaliteit) en A/LM-Cut* (garandeert optimaliteit maar is computationeel duur).
• Metrics: Succespercentage en Optimaliteitskloof (het verschil tussen de gegenereerde planlengte en de theoretisch optimale kosten $C_{opt}$).

3. Belangrijkste Resultaten

1. Omkering van Optimaliteit

• Klassieke Planners: LAMA en A* bereiken snel een "computationele muur". Zodra de zoekruimte groeit (bijv. bij meer dan 25 doelblokken of hoge torens), faalt A* volledig door geheugenoverbelasting, en LAMA produceert steeds suboptimale plannen of faalt.
• LLM's (Gemini 3.0 Pro): Deze modellen volgen de theoretische optimaliteitsgrens met bijna perfecte precisie, zelfs bij extreme complexiteit (bijv. >100 doelblokken of torens van >500 blokken). Ze vertonen geen geleidelijke degradatie in plankwaliteit, maar een binair overgang van perfecte optimaliteit naar volledig falen.

2. Robuustheid zonder Semantiek

Zelfs in de geabstraheerde grafiek-herformulering (zonder fysieke hints), behoudt het model zijn vermogen om optimale plannen te genereren. Hoewel het falen iets eerder optreedt dan in de standaard Blocksworld-versie, blijft het model de $P^*$-topologie navigeren. Dit bewijst dat het succes niet puur gebaseerd is op het onthouden van Blocksworld-patronen uit de trainingsdata.

3. Inference-Time Compute en Lineaire Schaling

• Er werd een sterke lineaire correlatie gevonden tussen het aantal redeneertokens (thinking tokens) en de lengte van het optimale plan.
• Het model gebruikt ongeveer 47 tokens per planstap. Dit suggereert dat het model een seriële algoritmesimulatie uitvoert: het traverseert de afhankelijkheidsketen stap voor stap in zijn "werkgeheugen" (chain-of-thought).
• Wanneer het model faalt, gebeurt dit vaak wanneer het benodigde aantal tokens de limiet van de generatie overschrijdt, wat wijst op een vast computercapaciteitslimiet in plaats van een kwaliteitsverlies.

4. Interleaved Harvest

Bij het "Interleaved Harvest"-scenario (waarbij doelblokken uit verschillende torens verweven moeten worden), daalt de optimaliteit van het LLM iets (van ~100% naar ~10% perfect optimaal, maar wel met geldige plannen), terwijl klassieke planners volledig falen. Dit suggereert dat het model een fallback-strategie gebruikt als de eenvoudige "clear-and-stack" decompositie niet meer werkt, maar nog steeds beter presteert dan klassieke zoekalgoritmen.

4. Belangrijkste Bijdragen

1. Multi-Scenario $P^*$-Probleemruimte: Introductie van een systematische taxonomie voor planningsproblemen gebaseerd op $P^*$-structuren, die complexiteit isoleert in diepte, breedte en compositie.
2. Structurele Analyse: Framing van planningsuitdagingen via $P^*$-topologieën, wat inzicht geeft in hoe LLM's afhankelijkheden ophalen en ordenen.
3. Optimaliteitsomkering: Het aantonen dat frontier-LLM's in bepaalde regimes (hoge complexiteit) superieur zijn aan zowel optimale als satisficing klassieke planners, doordat ze de zoekruimte effectief decomponeren in lineaire sequenties.
4. Falen-Modi Karakterisering: Onderscheid maken tussen de "harde muur" van klassieke planners (zoekruimte-explosie) en de "instabiliteitszones" van LLM's (binair falen na het bereiken van een compute-limiet).

5. Significatie en Conclusie

Dit onderzoek daalt de traditionele dominantie van symbolische planners in complexe planningsdomeinen. De bevindingen suggereren dat moderne, redeneringsversterkte LLM's niet slechts probabilistische patronen herhalen, maar een actieve algoritmesimulatie uitvoeren.

• Mechanisme: Het model lijkt de $P^*$-grafiek te decomponeren in onafhankelijke subproblemen en deze serieel op te lossen via chain-of-thought redeneren.
• Efficiëntie: Door de exponentiële gezamenlijke zoekruimte te reduceren tot een lineaire reeks van meervoudige hops, omzeilen deze modellen de "curse of dimensionality" waar klassieke zoekalgoritmen aan vastlopen.
• Toekomst: Hoewel het model een seriële simulatie lijkt uit te voeren, suggereert de hoge ophaalefficiëntie (zonder $O(N)$ scans) dat er mogelijk ook een geometrische navigatie (latent space representatie) plaatsvindt die de zoektocht versnelt.

Kortom, frontier-LLM's hebben de drempel voor planningsproblemen verschoven: ze kunnen niet alleen plannen, maar doen dit met een optimaliteit en schaalbaarheid die klassieke methoden in extreme scenario's niet kunnen evenaren.