Tree of Thoughts: Doelgericht problemen oplossen met LLM-zoekalgoritmen

Nadat ik de afgelopen twee bijdragen heb besteed aan agents die zichzelf corrigeren via reflectie (Reflexion) en tool-interactieve kritiek (CRITIC), wilde ik een stap terug doen en kijken naar een meer structurele aanpak: wat als de agent zich in de eerste plaats nooit vastlegt op een enkel redeneringspad? Tree of Thoughts (ToT) van Yao et al. (NeurIPS 2023) stelt precies dat voor — een zoekraamwerk waarin de LLM een vertakkende ruimte van tussenstappen in het redeneren verkent in plaats van één lineaire keten. Ik lees het nu omdat het de duidelijkste formulering is van doelgericht zoeken voor LLM-redenering, en doelgericht zoeken is wat je nodig hebt wanneer een enkele foutieve tussenstap in een financiële berekening stilletjes alles verderop in de keten kan corrumperen.

Het artikel

Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao en Karthik Narasimhan introduceren Tree of Thoughts als een generalisatie van chain-of-thought prompting. De belangrijkste stap is om tussenstappen in het redeneren te behandelen als "gedachten" — coherente teksteenheden die onafhankelijk kunnen worden geëvalueerd — en deze te organiseren in een boom in plaats van een keten. Bij elk knooppunt genereert het model meerdere kandidaat-gedachten, evalueert elke gedachte (via een aparte LLM-aanroep die toestanden scoort als "zeker / misschien / onmogelijk") en past vervolgens een standaard zoekalgoritme toe (BFS of DFS) om de boom te doorkruisen. Als een tak doodloopt, kan het model deze snoeien (pruning) of teruggaan (backtracking) — iets wat noch CoT noch CoT-SC kan doen.

Het artikel evalueert op drie taken: Game of 24 (combineer vier getallen om tot 24 te komen met behulp van rekenkunde), Creative Writing (produceer een coherente passage met vier willekeurige zinseinden) en Mini Crosswords (los een 5×5 kruiswoordpuzzel op). Alle drie vereisen redeneringen die baat kunnen hebben bij verkenning en backtracking, wat precies de setting is waarvoor de auteurs het hebben ontworpen.

Belangrijkste ideeën

• Bij Game of 24 behaalt ToT met een beam width van b=5 een succespercentage van 74%, tegenover 4% voor GPT-4 met standaard CoT en 9% voor CoT-SC met 100 samples. Dat gat is opvallend.
• GPT-3.5 + ToT bereikt slechts 19% op dezelfde taak; het voordeel van de methode is sterk modelafhankelijk. De kwaliteit van de generatie van gedachten door GPT-4 is de drijvende kracht achter het grootste deel van de winst — GPT-4 generatie + GPT-3.5 evaluatie behaalt 64%, terwijl GPT-3.5 generatie + GPT-4 evaluatie slechts 31% behaalt.
• Voor Creative Writing scoort ToT 7,56 versus de 6,93 van CoT op een GPT-4 coherentieschaal, en menselijke beoordelaars verkiezen de outputs van ToT 41/100 keer boven de 21/100 voor CoT.
• Mini Crosswords: ToT behaalt een nauwkeurigheid op woordniveau van 60% (CoT: 40,6%, IO: 15,6%), maar lost slechts 4 van de 20 volledige spellen op (20%). Het gat tussen succes op woordniveau en op spelniveau laat zien dat zelfs met backtracking, het voldoen aan globale restricties (constraints) moeilijk blijft.
• De evaluatiestap is zelf een LLM-aanroep. Bij kruiswoordpuzzels merken de auteurs op dat evaluatoren soms correcte gedeeltelijke toestanden als "onmogelijk" bestempelen vanwege onbekend vocabulaire — een cumulatieve foutmodus waarbij de fouten van de evaluator de zoektocht vergiftigen.
• Berekeningskosten: ToT kost ongeveer $0,74 per casus bij Game of 24, tegenover $0,47 voor best-of-100 CoT. De auteurs geven zelf aan dat voor taken die GPT-4 al goed beheerst, de overhead het niet waard is.

Wat standhoudt — en wat niet

Het kernresultaat — dat tree search over tussentijdse gedachten aanzienlijk beter presteert dan sequentiële CoT bij taken die backtracking vereisen — is reëel en reproduceerbaar. Het gat van 74% vs 4% bij Game of 24 is geen ruis. De verklaring is mechanisch solide: een enkele slechte tussenvergelijking in CoT stuurt de rest van de keten de afgrond in, terwijl ToT die tak kan snoeien en een andere ontbinding kan proberen.

Wat ik minder overtuigend vind, is de claim over de algemene toepasbaarheid. Alle drie de evaluatietaken zijn relatief synthetisch: een wiskundepuzzel, een creatieve schrijfopdracht met structurele beperkingen en een woordspel. Geen van deze lijkt op de open, ambigue problemen die voorkomen in productie-financiële workflows. De auteurs evalueren bovendien alleen op GPT-4 (en GPT-3.5 als ablatie), dus we weten niet hoe ToT presteert met kleinere of gefinetunede modellen — en het cijfer van 19% voor GPT-3.5 suggereert dat het antwoord "niet goed" is.

Het falen op spelniveau bij kruiswoordpuzzels (20% ondanks 60% woordnauwkeurigheid) wijst op een dieper liggend probleem: ToT is een lokale zoekopdracht die wordt geleid door een lokale evaluator. Het onderhoudt geen globaal constraint-model, wat precies is wat je nodig hebt voor problemen waarbij interacties tussen suboplossingen intensief zijn. De vervolgpaper Graph of Thoughts (Besta et al., AAAI 2024) maakt deze kritiek expliciet en toont een kwaliteitsverbetering van 62% aan ten opzichte van ToT bij sorteertaken, terwijl de kosten met meer dan 31% worden verlaagd — door gedachten toe te staan samen te smelten en cycli te vormen in plaats van beperkt te blijven tot een boomstructuur.

Ten slotte zijn de kosten in de praktijk van belang. Met b=5 en herhaalde evaluator-aanroepen is ToT ruwweg 15–20× duurder in API-aanroepen dan een enkele CoT-sessie. Voor latentiegevoelige of kostengevoelige toepassingen is dit niet zomaar acceptabel.

Waarom dit van belang is voor financiële AI

Het eerlijke antwoord is: ToT is vooral van belang voor een specifiek deel van het Beancount-probleemveld, maar dat deel is reëel.

De canonieke financiële taak waarbij ik backtracking wil, is meerstaps rekeningclassificatie met ambigue transacties. Wanneer een LLM een geïmporteerd bankafschrift koppelt aan een rekeningschema (chart of accounts), kan een enkele verkeerde toewijzing vroeg in de keten (bijvoorbeeld het behandelen van een leninguitbetaling als inkomen) leiden tot een mislukte balanscontrole enkele stappen later. In een CoT-agent heeft het model, tegen de tijd dat de balanscontrole faalt, geen mechanisme om de oorspronkelijke classificatie te herzien. Een ToT-agent zou terug kunnen gaan naar dat knooppunt en in plaats daarvan Passiva:Leningen kunnen proberen.

Op vergelijkbare wijze is belastingoptimalisatie over een volledig fiscaal jaar een echt boomzoekprobleem: itemiseren versus de standaardaftrek nemen, de timing van het realiseren van vermogenswinsten, het bundelen van giften. Deze beslissingen hebben een niet-lineaire interactie en je moet meerdere takken evalueren voordat je een keuze maakt. Het BFS/DFS-raamwerk van ToT sluit natuurlijk aan bij die structuur.

Waar ToT niet bij helpt, is het dominante geval in Beancount: routineuze transactie-invoer en reconciliatie. Voor een transactie die een duidelijke tegenhanger in het grootboek heeft, is CoT + PAL (rekenwerk uitbesteden aan een code-interpreter) sneller, goedkoper en al nauwkeurig genoeg. ToT inzetten voor de classificatie van uitgaven:boodschappen is als met een voorhamer op een punaise slaan.

De urgentere zorg voor de veiligheid van terugschrijven (write-back safety) is het probleem van de betrouwbaarheid van de evaluator. Als de toestandsevaluator ook een LLM is, kan deze ernaast zitten — en foutieve evaluaties vertragen de zoektocht niet alleen, ze snoeien ook correcte paden weg. Elke financiële agent in productie die ToT gebruikt, zou een extern orakel nodig hebben (een balanscontrole, een schema-validator, een regel-engine) om als evaluator te fungeren, in plaats van een nieuwe LLM-aanroep.

Wat je hierna kunt lezen

• Graph of Thoughts: Solving Elaborate Problems with Large Language Models (Besta et al., AAAI 2024) — arXiv:2308.09687. Breidt ToT uit van bomen naar willekeurige grafen, wat het samenvoegen van gedachten en feedbackloops mogelijk maakt. De claim over kostenverlaging (>31%) is direct relevant als je zoekgebaseerd redeneren wilt zonder de overhead van ToT.
• Large Language Models Cannot Self-Correct Reasoning Yet (Huang et al., ICLR 2024) — arXiv:2310.01798. Een kritisch tegenpunt: zonder externe feedback verslechtert intrinsieke zelfcorrectie de redeneerprestaties. Dit stelt de aanname ter discussie dat de op LLM gebaseerde evaluator van ToT betrouwbaar genoeg is om de zoektocht te leiden.
• RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation (arXiv:2409.09584) — past MCTS toe in plaats van BFS/DFS voor het zoeken naar gedachten, met uitvoeringsfeedback als extern orakel. De setting van codegeneratie is structureel vergelijkbaar met het schrijven naar een grootboek: je hebt een verifieerbare bron van waarheid (draait de code? slaagt de balanscontrole?), wat precies de plek is waar Monte Carlo rollouts waarde toevoegen.