🤖 AI

GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning

Het artikel introduceert GATS, een planningsframework dat kostbare LLM-inferentie vervangt door een gelaagd wereldmodel en een op UCB1 gebaseerde boomzoekopdracht om een succespercentage van 100% en deterministische planning met nul aanroepen te bereiken over diverse complexe taken, waarbij het bestaande methoden zoals LATS en ReAct aanzienlijk overtreft.

Oorspronkelijke auteurs: Maureese Williams, Dymitr Nowicki

Gepubliceerd 2026-07-13

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Maureese Williams, Dymitr Nowicki

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

Stel je voor dat je een gigantisch, ingewikkeld doolhof probeert op te lossen. Je hebt een superintelligente vriend (een Large Language Model, of LLM) die met je kan praten en kan suggereren welke kant je op moet draaien. Maar hier komt de adder onder het gras: elke keer als je je vriend om advies vraagt, moet hij een lang dutje doen om na te denken, en soms geeft hij telkens een ander antwoord als je dezelfde vraag stelt. Als het doolhof doodlopende wegen heeft of een lange reeks bochten vereist, wordt het duur en verwarrend om je vriend bij elke stap om hulp te vragen.

Dit is het probleem waar onderzoekers Maureese Williams en Dymitr Nowicki hun nieuwe systeem, GATS (Graph-Augmented Tree Search), mee aanpakten. Ze vonden een manier om het doolhof zo efficiënt te navigeren dat ze hun superintelligente vriend nauwelijks hoeven wakker te maken.

De oude manier: De "vraag-bij-elke-stap"-aanpak

Eerdere methoden, zoals ReAct en LATS, waren een beetje als een wandelaar die bij elke splitsing in de weg stopt om een gids te vragen: "Welke kant moet ik op?"

ReAct vraagt slechts één keer en gaat dan door. Het is snel, maar loopt vaak in doodlopende wegen. In hun tests slaagde deze methode slechts in 64% van de lastige doolhofscenario's.
LATS is slimmer; het vraagt de gids, en vraagt dan weer naar de volgende stap, en nog een keer, waardoor er een boom van mogelijkheden ontstaat. Maar omdat LATS de gids (de LLM) voor elke tak van die boom om hulp vraagt, wordt hij moe en kostbaar. In de tests slaagde LATS 92% van de tijd, maar moest het de gids wel ongeveer 37 keer per taak om hulp vragen. Bovendien, omdat de gids soms willekeurig gokt, krijg je misschien een andere route als je hetzelfde doolhof twee keer probeert.

De nieuwe manier: GATS (De "Kaartmaker"-strategie)

GATS verandert het spel. In plaats van de gids voor elke bocht om hulp te vragen, bouwt GATS zijn eigen interne kaart met behulp van een Layered World Model (Gelaagd Wereldmodel). Denk aan deze kaart als een systeem met drie lagen kennis:

Laag 1 (Het exacte regelboek): Voor acties die het systeem al perfect kent (zoals "als ik op deze knop druk, gaat de deur open"), gebruikt het een eenvoudige, directe controle. Geen nadenken nodig. Het is alsof je weet dat 2+2 altijd 4 is.
Laag 2 (Het ervaringenlogboek): Als het systeem een actie eerder heeft gezien maar er geen perfecte regel voor heeft, controleert het zijn dagboek van eerdere reizen. "Vorige keer dat ik dit deed, werkte het 9 van de 10 keer." Dit is geleerd van data, niet gegokt.
Laag 3 (De supergeniale vriend): Alleen wanneer het systeem iets volkomen nieuws en onbekends tegenkomt, wordt de LLM-gids wakker gemaakt. Maar hier is de magie: zodra de gids antwoordt, schrijft GATS het antwoord op in de kaart. De volgende keer dat diezelfde situatie voorkomt, kijkt GATS gewoon op de kaart. Het vraagt de gids nooit meer om hulp voor die specifieke gebeurtenis.

De resultaten: Snelheid, Zekerheid en Succes

De onderzoekers testten dit op 100 synthetische plannings-taken die ontworpen waren om lastig te zijn, met vertakkende paden en doodlopende wegen.

GATS behaalde een perfect score van 100% succes.
LATS behaalde 92%.
ReAct behaalde 64%.

Maar het echte wonder? GATS deed nul oproepen naar de LLM tijdens het daadwerkelijke plannen van deze taken. Het deed al het denkwerk met behulp van de eigen kaart en regels. Omdat het niet afhankelijk was van de willekeurige gokken van de LLM, produceerde GATS elke keer exact hetzelfde perfecte plan. Er was nul variantie.

Ze voerden ook een enorme "stress-test" uit met 120 taken verspreid over 12 moeilijke categorieën, zoals workflows voor coderen, het boeken van vluchten en het navigeren door complexe doolhoven.

GATS behaalde nog steeds 100% succes.
LATS zakte naar 88,9%.
ReAct stortte in naar 23,9%.

Waarom het werkt (Het geheime ingrediënt)

Het paper suggereert dat GATS wint omdat het een systematische zoektocht gebruikt (genaamd UCB1) in plaats van willekeurig te gokken. Stel je een detective voor die elk spoor methodisch controleert in plaats van alleen maar een intuïtie te volgen.

Systematisch versus Willekeurig: LATS vertrouwt erop dat de LLM raadt welke route er goed lijkt. Als de "hunch" (het gevoel) van de LLM fout is, mislukt het hele plan. GATS controleert alle opties systematisch, waardoor het de juiste weg niet mist, simpelweg omdat de gids een slechte dag had.
Deterministisch versus Stochastisch: Omdat GATS voor de meeste stappen zijn eigen kaart gebruikt, is het resultaat altijd hetzelfde. LATS, dat afhankelijk is van de LLM, kan je een ander antwoord geven als je dezelfde taak twee keer uitvoert.

Wat dit betekent (En wat het niet betekent)

De auteurs zijn zeer duidelijk over de beperkingen van hun succes. Deze resultaten zijn gebaseerd op simulaties en synthetische taken waarbij de regels van het spel (de "actie-specificaties") vooraf bekend waren. In deze gecontroleerde omgevingen is GATS een kampioen.

De auteurs sluiten echter expliciet de mogelijkheid uit dat GATS op dit moment een wondermiddel is voor alles. Als je GATS in een volkomen wilde, open wereld zou werpen waar het geen regels en geen eerdere logs heeft om van te leren, zou het de LLM zwaarder moeten gebruiken (Laag 3), wat het trager en minder efficiënt zou maken. De auteurs suggereren dat voor GATS om in de echte wereld te kunnen schitteren, we eerst betere kaarten (wereldmodellen) moeten bouwen, bijvoorbeeld door te leren van logs over hoe mensen daadwerkelijk tools gebruiken.

Kortom, het paper laat zien dat we voor plannings-taken waarbij we de regels kunnen definiëren, de superintelligente AI niet bij elke stap om hulp hoeven te vragen. We kunnen een slimme, zelf-updatende kaart bouwen waarmee we complexe problemen kunnen navigeren met 100% succes, nul kosten en geen verwarring.

Technische Samenvatting: GATS (Graph-Augmented Tree Search met Gelaagde Wereldmodellen)

Probleemstelling

Large Language Model (LLM) agenten hebben potentieel getoond in meerstapsplanning en toolgebruik, maar huidige benaderingen zoals ReAct en LATS (Language Agent Tree Search) kampen met twee kritieke beperkingen:

Computationele Kosten: Bestaande methoden vertrouwen op dure LLM-inferentie bij elke planningsstap of zoekknooppunt, wat leidt tot hoge latentie en een hoog resourceverbruik.
Stochastiek: LLM-sampling introduceert variantie, wat resulteert in niet-reproduceerbare plannen en inconsistente prestaties over verschillende runs heen.

De kernuitdaging is het ontwikkelen van een planningsframework dat de redeneervaardigheden van LLM's behoudt, terwijl het inferentie-gebaseerde LLM-aanroepen voor staatvoorspelling elimineert, om zo deterministische, efficiënte en schaalbare agent-planning te bereiken.

Methodologie: GATS Framework

De auteurs stellen GATS (Graph-Augmented Tree Search) voor, een planningsarchitectuur die het wereldmodel ontkoppelt van de LLM. GATS combineert systematische UCB1-gebaseerde boomzoekopdrachten met een Gelaagd Wereldmodel en een persistente Toestands-transitie-graaf.

1. Gelaagd Wereldmodel ( $W$ )

Het wereldmodel voorspelt de volgende staat ( $s'$ ) en betrouwbaarheid ( $p$ ) gegeven een huidige staat ( $s$ ) en actie ( $a$ ). Het bevraagt drie lagen in volgorde van toenemende algemeenheid en computationele kosten:

L1 (Symbolisch): Exacte matching van precondities en effecten voor acties met bekende STRIPS-stijl specificaties. Deze laag biedt deterministische voorspellingen ( $p=1.0$ ) met minimale computationele kosten (symbolische lookup).
L2 (Geleerde Statistiek): Statistische voorspellingen afgeleid van executielogs. Voor acties die tijdens uitvoering zijn waargenomen maar geen formele specificaties missen, geeft het het meest frequente effect terug met een betrouwbaarheid van $p = \min(\text{count}(a)/10, 1.0)$ .
L3 (Generatief/LLM): LLM-gebaseerde voorspelling voor werkelijk nieuwe of ambigue acties. Cruciaal is dat voorspellingen uit L3 worden gecached om herhaalde inferentie-aanroepen voor dezelfde transitie te vermijden.

Het systeem geeft prioriteit aan L1 en L2 om de dekking te maximaliseren, en roept L3 alleen aan wanneer dat noodzakelijk is. Dit "amortiseert" de LLM-kosten, waardoor de kosten worden getransformeerd van een per-stap vereiste inferentie naar een eenmalige bootstrapping-kost.

2. Persistente Toestands-transitie-graaf

In tegenstelling tot traditionele boomzoekopdrachten die knooppunten onafhankelijk uitbreiden, onderhoudt GATS een expliciete graaf $G = (V, E)$ waarbij knooppunten canonieke staatssleutels $k(s)$ vertegenwoordigen.

State Merging: Als verschillende actiesequenties dezelfde staat bereiken, fuseren ze tot één knooppunt. Dit maakt het mogelijk om transitievoorspellingen, bezoekfrequenties en waardeschattingen over paden heen te hergebruiken.
Persistentie: De graaf persisteert over planningsstappen heen. Nadat een actie is uitgevoerd, wordt de planning hervat vanaf het overeenkomstige graafknooppunt in plaats van de zoekopdracht opnieuw te starten, waardoor waardeschatting en zoekstatistieken over de gehele episode worden geamortiseerd.
Dead-End Detectie: Knooppunten zonder pad naar een doel worden gemarkeerd als 'dead ends', waardoor de planner lage waarden kan toekennen aan acties die naar deze regio's leiden.

3. UCB1-gebaseerde Zoekopdracht

GATS gebruikt een UCB1 (Upper Confidence Bound) selectiestrategie over de graafranden.

Actie Selectie: Bij elke staat selecteert het algoritme de actie $a$ die $Q(s, a) + c\sqrt{\frac{2 \ln N(s)}{N(s, a)}}$ maximaliseert. Dit zorgt voor een systematische exploratie van alle toepasbare acties voordat er wordt vastgelegd op hoogwaardige paden.
Waardeschatting: De waarde van een staat wordt afgeleid van de kortste voorspelde afstand tot het doel ( $d_G$ ) met behulp van een BFS-gebaseerde heuristiek: $StateValue(s) = \frac{\alpha}{d_G(s, G) + 1}$ .
Betrouwbaarheid Integratie: De backup-waarde incorporeert de betrouwbaarheid van het wereldmodel: $v = p \cdot StateValue(s') - \lambda(1-p)$ , wat onzekere voorspellingen bestraft.

Belangrijkste Bijdragen

Gelaagde Wereldmodel Architectuur: Een nieuwe integratie van symbolische, geleerde en generatieve componenten die efficiënte staatvoorspelling mogelijk maakt terwijl de afhankelijkheid van de LLM wordt geminimaliseerd.
Systematische UCB1 Zoekopdracht met Graafgeheugen: Een planningsalgoritme dat de random LLM-gestuurde exploratie overtreft door een persistente graaf te gebruiken om zoekbewijs te hergebruiken en deterministische resultaten te garanderen.
Uitgebreide Evaluatie: Uitgebreide testen op 100 synthetische planningsopdrachten en een 12-categorie stress-test (120 taken) die coderen, webnavigatie en lang-horizon scenario's beslaat.
Nul LLM-aanroepen Tijdens Planning: Getoond dat GATS een succespercentage van 100% kan bereiken met nul LLM-aanroepen tijdens de planningsfase, wat scherp contrasteert met baselines die tientallen aanroepen per taak vereisen.

Experimentele Resultaten

Synthetische Planningsopdrachten (100 Taken)

Succespercentage: GATS bereikte 100% succes (met budget $b=10$ ), waarmee het LATS (92%) en ReAct (64%) overtrof.
Efficiëntie: GATS vereiste 0 LLM-aanroepen per taak tijdens de planning, terwijl LATS ~37 aanroepen vereiste.
Determinisme: GATS produceerde plannen met 0% variantie over random seeds heen, terwijl LATS en ReAct 1–5% variantie vertoonden door de stochastiek van de LLM.
Optimaliteit: GATS bereikte een optimaliteitsratio van 1.00, gelijk aan de Oracle.

Stress Test (12 Categorieën, 120 Taken)

De stress test omvatte uitdagende scenario's zoals coding workflows, webnavigatie, diepe horizon taken en onomkeerbare besluitvorming (dead-ends).

Algemene Prestaties: GATS behield een succespercentage van 100% over alle categorieën.
Vergelijkende Prestaties: LATS daalde naar 88.9% totaal, met significante problemen in coding (63.3%), webnavigatie (63.3%) en deep horizon (63.3%) taken. ReAct faalde catastrofaal met 23.9%.
Specifieke Winsten: GATS toonde de grootste verbeteringen (+36.7%) in coding, webnavigatie en deep horizon taken vergeleken met LATS.

Ablatie Studies

Zoekbudget: Prestaties verzadigden bij een budget van $b=10$ ; verdere verhoging leverde afnemende meeropbrengsten op.
Wereldmodel Lagen: Het individueel verwijderen van L1 of L3 had geen invloed op de succespercentages op synthetische taken waar L2 voldoende dekking bood, wat de gracieuze degradatie van het systeem valideert. In open-domein projecties wordt verwacht dat L3 (LLM) ongeveer 10% van de nieuwe acties zal afhandelen.

Betekenis en Claims

Het artikel betoogt dat systematische zoekopdrachten met geleerde wereldmodellen aanzienlijk beter kunnen presteren dan LLM-gestuurde exploratie voor agent-planning. De primaire betekenis van GATS ligt in het vermogen om:

Inference-Time LLM-kosten te Elimineren: Door voorspellingen te cachen en te vertrouwen op symbolische/geleerde lagen, verwijdert GATS de computationele bottleneck van herhaalde LLM-aanroepen.
Reproduceerbaarheid te Garanderen: De deterministische aard van het gelaagde wereldmodel en de UCB1-zoekopdracht elimineert de stochastische variantie die inherent is aan LLM-sampling.
Complexe Planning aan te Pakken: Het framework navigeert succesvol door vertakkende paden, dead-ends en lang-horizon afhankelijkheden waar puur LLM-gebaseerde methoden (ReAct) en LLM-zware boomzoekopdrachten (LATS) falen of onderpresteren.

De auteurs positioneren GATS als een geoptimaliseerde oplossing voor domeinen waar actie-semantiek geformaliseerd kan worden (bijv. API's, gestructureerd toolgebruik), wat een pad biedt naar efficiëntere en betrouwbaardere autonome agenten. Ze erkennen dat in open-ended domeinen met onbekende actie-effecten, de afhankelijkheid van de L3-laag zou toenemen, wat het efficiëntievoordeel ten opzichte van LATS weliswaar vermindert, maar niet volledig elimineert.