Tree-of-thoughts en graph-reasoning: zoekbomen in promptstructuren

Klassieke autoregressieve taalmodellen genereren tekst van links naar rechts, token voor token. Wanneer een model een complexe puzzel, wiskundig bewijs of strategisch planningsvraagstuk oplost via een standaardprompt, zit het vast aan het lineaire pad dat het zelf begint te schrijven. Maakt het model in stap twee een logische denkfout, dan dwingt het aandachtsmechanisme de volgende tokens om voort te borduren op die eerdere misstap. Het model kan immers niet uit zichzelf 'terugspoelen' of meerdere alternatieve routes parallel verkennen.

Om deze fundamentele beperking van lineaire generatie te doorbreken, zijn zoekboom- en graafstructuren ontwikkeld. In plaats van één aaneengesloten denkketen splitsen methodes zoals Tree-of-Thoughts (ToT) en Graph-of-Thoughts (GoT) het probleem op in discrete deelgedachten (gedachtetoestanden). Door deze toestanden te combineren met klassieke zoekalgoritmen zoals boomzoeken en graaftransformaties ontstaat een vorm van deliberatieve planning. In dit dossier doorlopen we hoe deze architecturen werken, hoe evaluatiestappen functioneren, en hoe je beslist of de rekenkosten van zoekbomen opwegen tegen de betrouwbaarheidswinst.

De lineaire valkuil van Chain-of-Thought

Bij klassieke ketenredeneringen (Chain-of-Thought of CoT) produceert het model een aaneenschakeling van tussenstappen. Dit verbetert de prestaties op rekenkundige en logische taken aanzienlijk ten opzichte van directe vraag-antwoordprompts. Het fundamentele zwakke punt blijft echter de greedy commitment: elke gegenereerde tussenstap wordt direct onderdeel van de vaste context voor alle volgende stappen.

Zodra een model een rekenfout maakt of een doodlopend pad inslaat bij een cryptisch raadsel of puzzel (zoals het bekende Game of 24 of het plannen van een logistieke route met strenge restricties), heeft het binnen CoT geen formeel mechanisme om die fout te detecteren en een alternatieve denkrichting te kiezen. Het model zal in plaats daarvan proberen de gemaakte fout 'glad te strijken' of te hallucineren naar een foutieve conclusie toe. Zelfs technieken als Self-Consistency — waarbij we meerdere onafhankelijke CoT-paden genereren en een meerderheidsstemming toepassen — lossen dit probleem slechts ten dele op. Als de kans klein is dat een model in één rechte lijn naar het juiste antwoord loopt, levert een meerderheidsstemming over tien mislukte lineaire pogingen alsnog een fout antwoord op.

Tree-of-Thoughts: de vier pijlers van zoekbomen

Tree-of-Thoughts formaliseert het redeneerproces als een zoektocht over een gerichte boom. De wortel van de boom is het initiële vraagstuk, elke tussenliggende knoop stelt een partiële oplossing of tussenstap voor (een thought), en de bladeren zijn finale oplossingen. Een ToT-framework rust op vier afgebakende componenten die door een extern orkestratie-script of een agentische lus worden aangestuurd.

Ten eerste is er de probleemdeconstructie: hoe groot is één gedachte? Een gedachte moet betekenisvol genoeg zijn om autonoom geëvalueerd te kunnen worden, maar klein genoeg om alternatieven voor te genereren (bijvoorbeeld één tussenberekening, een alineaplan of een schaakzet). Ten tweede is er de gedachte-generator, die vanuit een bestaande toestand $k$ nieuwe kandidaat-gedachten genereert via prompts. Ten derde evalueert de toestandsbeoordelaar de kwaliteit van elke knoop via scoring of classificatie. Ten vierde bepaalt het zoekalgoritme (zoals Breadth-First Search of Depth-First Search) welke takken verder worden uitgediept, wanneer er gebacktracked wordt en welke paden worden gesnoeid (pruning).

Wortel: Vraagstuk (Starttoestand)
  ├── Gedachte A1 [Score: 0.85] -> Levensvatbaar pad
  │     ├── Gedachte B1 [Score: 0.95] -> Finale Oplossing (Gevalideerd)
  │     └── Gedachte B2 [Score: 0.20] -> Gesnoeid (Pruning)
  └── Gedachte A2 [Score: 0.30] -> Doodlopend pad (Backtracking)

Zoekalgoritmen in actie: BFS, DFS en Monte Carlo Tree Search

Het kiezen van het zoekalgoritme bepaalt het gedrag en het geheugengebruik van de redeneerlus. Bij Breadth-First Search (BFS) verkent het systeem alle mogelijke gedachten op een bepaalde diepte tegelijk. Dit is met name effectief wanneer de totale diepte van de redeneerboom beperkt is (bijvoorbeeld 3 tot 4 stappen) en we op elk niveau alleen de $b$ best scorende kandidaten willen bewaren (een beam search over gedachten). BFS voorkomt dat het model diep verdwaalt in één foutieve redeneertak, maar vraagt veel parallelle calls per laag.

Bij Depth-First Search (DFS) duikt het model direct zo diep mogelijk een tak in totdat een eindoplossing is bereikt of totdat de toestandsbeoordelaar vaststelt dat de tak onbegaanbaar is geworden (een score onder de drempelwaarde). Zodra een tak faalt, keert het algoritme terug naar de vorige knoop (backtracking) en kiest het de volgende kandidaat. Dit bootst nauwkeurig menselijk probleemoplossend gedrag na bij taken zoals sudoku's oplossen of software debuggen. Voor extreem grote zoekruimtes kan Monte Carlo Tree Search (MCTS) worden ingezet, waarbij via rollouts en statistische upper confidence bounds (UCT) een balans wordt gezocht tussen het uitdiepen van bewezen sterke takken en het verkennen van onzekere vertakkingen.

De Toestandsbeoordelaar: hoe evalueert een LLM tussenstappen?

Het meest kritieke onderdeel van boom- en graafredenering is de evaluatiefunctie. Zonder een betrouwbare methode om te bepalen of een tussenstap dichter bij het doel komt, verwordt de zoektocht tot een willekeurige enumeratie. In de praktijk worden drie primaire evaluatiestrategieën gebruikt.

De eerste methode is waarde-classificatie via prompts. Hierbij krijgt het model een prompt met de huidige partiële oplossing en wordt gevraagd deze te classificeren als zeker haalbaar, misschien haalbaar of onmogelijk. De tweede methode is numerieke scoring (value scoring), waarbij het model een score tussen 1 en 10 toekent aan de tussenstap op basis van expliciete criteria. De derde en meest robuuste methode is programmatische validatie: wanneer de domeinregels formeel zijn (zoals bij SQL-queries, syntaxvalidatie van code of wiskundige rekenregels), evalueert een deterministische compiler of runtime-omgeving de knoop. Hierdoor worden hallucinaties in de evaluatiefase volledig uitgesloten.

Graph-of-Thoughts: voorbij de hiërarchische boom

Hoewel Tree-of-Thoughts een aanzienlijke stap voorwaarts is ten opzichte van lineaire ketens, dwingt een boomstructuur een strikte hiërarchie af: takken kunnen splitsen, maar ze komen nooit meer samen. In complexe redeneerprocessen is het echter vaak wenselijk om inzichten uit twee onafhankelijke denkrichtingen samen te voegen (synthese), of een eerdere gedachte iteratief bij te schaven zonder een compleet nieuwe tak te starten.

Graph-of-Thoughts (GoT) modelleert het denkproces als een gerichte graaf (Directed Acyclic Graph of DAG). Dit maakt operaties mogelijk die in een standaardboom onuitvoerbaar zijn. We onderscheiden drie specifieke graaftransformaties: aggregatie (het combineren van knoop A en knoop B tot een nieuwe syntheseknoop C), verfijning (het cyclisch updaten van de toestand van een knoop op basis van feedback) en splitsing (het parallel ontbinden van een taak in subproblemen). GoT blijkt bijzonder krachtig bij taken zoals het schrijven van complexe documenten op basis van meerdere bronnen of het ontwerpen van systeemarchitecturen waar verschillende randvoorwaarden tegelijk moeten samenkomen.

Praktijkvoorbeeld: een logistieke planning met Tree-of-Thoughts

Laten we een concrete Nederlandse casus bekijken: het plannen van een bezorgroute voor een transportbedrijf met drie elektrische bestelwagens vanuit een distributiecentrum in Utrecht naar vijf steden (Alkmaar, Arnhem, Breda, Groningen en Maastricht), rekening houdend met actieradius, laadtijden en venstertijden voor levering.

Bij een standaard Chain-of-Thought zal een model direct een volgorde uitschrijven. Wanneer het bij de vierde stad ontdekt dat de actieradius van wagen 1 wordt overschreden, kan het de eerdere steden niet meer verplaatsen en ontstaat een ongeldig plan. Binnen een Tree-of-Thoughts structuur deelt het orchestratie-script de taak op in lagen. Laag 1 genereert drie mogelijke voertuig-stad toewijzingen. Een deterministisch script valideert direct de kilometerstanden. Tak 1 overschrijdt de actieradius en krijgt het label onmogelijk (pruning). Tak 2 en 3 zijn haalbaar en worden uitgebreid naar laag 2 (laadtijdplanning). Het model verkent vervolgens alleen de levensvatbare routes verder, waardoor het uiteindelijke gecombineerde routeplan gegarandeerd voldoet aan alle harde restricties.

// Vereenvoudigde JSON-representatie van een ToT-stap
{
  "node_id": "route_utrecht_alkmaar_v1",
  "parent_id": "root_dc_utrecht",
  "thought_content": "Voertuig 1 vertrekt 08:00 naar Alkmaar (afstand: 78km, acculading rest: 74%)",
  "state_evaluation": {
    "deterministic_check": "PASS",
    "battery_feasible": true,
    "time_window_feasible": true,
    "score": 0.92
  },
  "status": "EXPAND"
}

Rekenkracht en de trade-off: wanneer loont zoekboom-prompting?

Het gebruik van Tree-of-Thoughts en Graph-of-Thoughts brengt aanzienlijke rekenkosten met zich mee. Waar een standaard prompt één LLM-aanroep vereist en Chain-of-Thought één langere generatie vraagt, kan een ToT-zoektocht met vertakkingsfactor $b=3$ en diepte $d=4$ tientallen tot honderden afzonderlijke calls veroorzaken. Dit leidt tot een navenante stijging in tokenconsumptie en verwerkingstijd (latentie).

Om te bepalen of een zoekstructuur gerechtvaardigd is, kijken we naar de complexiteit en de fouttolerantie van de taak. Voor routinematige teksttransformaties, eenvoudige samenvattingen of open conversaties is ToT zware overkill. Bij taken met een combinatorische zoekruimte, harde randvoorwaarden of een asymmetrische verificatiekost (waarbij een tussenoplossing moeilijk te bedenken is, maar razendsnel te controleren) levert ToT daarentegen een betrouwbaarheidswinst die met lineaire prompting onbereikbaar is.

ToT versus native test-time compute redeneermodellen

Sinds de introductie van gespecialiseerde redeneermodellen (zoals OpenAI o1, o3 en vergelijkbare open-weights architecturen) is het landschap rondom redeneerstructuren sterk veranderd. Deze modellen voeren intern al een vorm van zoekgedrag, zelfcorrectie en ketenverkenning uit tijdens de generatiefase (test-time compute). Raadpleeg voor de werking van deze interne mechanismen het artikel over hoe redeneermodellen denken als aparte stap inrichten.

De vraag rijst dan ook: maakt native test-time compute externe ToT-frameworks overbodig? Het antwoord is genuanceerd. Interne redeneermodellen zijn compacter, sneller en vereisen geen complexe externe orchestratiesoftware. Externe ToT- en GoT-frameworks behouden echter twee doorslaggevende voordelen. Ten eerste bieden ze volledige controle over de zoekboom: ontwikkelaars kunnen eigen deterministische evaluatoren en externe databases direct in de knooppunten injecteren. Ten tweede leveren externe frameworks volledige auditability: elke afzonderlijke gedachte en evaluatiescore is transparant inzichtelijk en kan worden gelogd voor kwaliteitsbewaking.

Wanneer we dergelijke systemen in productie evalueren, volstaan traditionele tekstbenchmarks niet meer; zie hiervoor ook het dossier over hoe je agentische systemen en complexe beslissingstrajecten evalueert op betrouwbaarheid en taaksucces.