💬 NLP

Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs

Het artikel stelt Budget-Guided MCTS (BG-MCTS) voor, een tree-search decoding algoritme dat exploratie- en verfijningsstrategieën dynamisch afstemt op het resterende tokenbudget om budget-agnostische baselines te overtreffen in wiskundige en natuurkundige redeneertaken.

Oorspronkelijke auteurs: Sora Miyamoto, Daisuke Oba, Naoaki Okazaki

Gepubliceerd 2026-06-05

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Sora Miyamoto, Daisuke Oba, Naoaki Okazaki

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 detective bent die probeert een zeer lastig raadsel op te lossen, maar je hebt een strikte regel: je mag slechts een bepaald aantal vragen stellen voordat de klok afloopt. Dit is precies de uitdaging waar Large Language Models (LLM's) voor staan bij het oplossen van complexe problemen zoals wiskunde of natuurkunde. Ze hebben een "token-budget" — een limiet aan hoeveel woorden of stappen ze kunnen genereren.

De paper introduceert een nieuwe methode genaamd BG-MCTS (Budget-Guided Monte Carlo Tree Search) om deze AI-detectives te helpen problemen beter op te lossen binnen die strikte tijdslimiet.

Zo werkt het, met behulp van eenvoudige analogieën:

Het Probleem: De "One-Size-Fits-All" Detective

Huidige AI-zoekmethoden gedragen zich als een detective met een vast plan, ongeacht hoeveel tijd er nog over is.

De Oude Manier: De detective brengt de eerste helft van de dag door met het ondervragen van 100 verschillende mensen voor aanwijzingen (brede exploratie). Dan, in de laatste 10 minuten, realiseert de detective zich dat er geen tijd meer is om daadwerkelijk de meest veelbelovende sporen te volgen. De detective kan vlak voordat de klok op nul staat nog een nieuwe lijn van ondervraging starten, waardoor de zaak onopgelost blijft. Of de detective stopt te vroeg, waardoor de laatste 10 minuten van de dienst verspild worden.
Het Probleem: Bestaande methoden behandelen de tijdslimiet (het token-budget) alleen als een "stopbord". Ze veranderen hun strategie niet op basis van hoeveel tijd er nog over is.

De Oplossing: De "Slimme Detective" (BG-MCTS)

De auteurs stellen een detective voor die constant op zijn horloge kijkt en zijn strategie aanpast op basis van de resterende tijd. Ze noemen dit Budget-Guided MCTS.

Beschouw het zoekproces als een boom die groeit vanuit een wortel:

Vroege Fase (Veel tijd over): Wanneer de detective 100% van zijn tijd heeft, handelt hij als een visser die met een breed net vist. Hij werpt een breed net uit en verkent veel ondiepe paden om te zien waar de vissen zich kunnen bevinden. Hij duikt nog niet diep; hij wil alleen de hele oceaan in kaart brengen.
Late Fase (Tijd loopt op): Naarmate de klok tikt (bijvoorbeeld naar 25% van het budget), stopt de detective met het uitwerpen van brede netten. In plaats daarvan kiest hij de twee of drie meest veelbelovende plekken die hij eerder heeft gevonden en duikt hij daar diep in. Hij stopt met het starten van nieuwe lijnen van ondervraging en focust zich volledig op het afronden van het onderzoek van de beste sporen.

Hoe de AI het doet

De paper beschrijft twee specifieuwe trucs die de AI gebruikt om dit te bewerkstelligen:

De "Tijd-Check" Score: Wanneer de AI beslist welk pad het volgende gevolgd moet worden, gebruikt het een formule die kijkt naar hoeveel budget er nog over is.
- Als er veel budget is, moedigt de formule het aan om nieuwe, onverkende paden te proberen.
- Als het budget laag is, straft de formule het starten van nieuwe paden af en beloont het het dieper gaan in paden die al goed lijken.
De "Nieuwe Tak" Schakelaar: De AI heeft een speciale schakelaar die beslist of er een nieuwe tak op de boom gegroeid wordt of dat er alleen dieper in een bestaande tak wordt gedoken.
- Wanneer er volop tijd is, staat de schakelaar op "Nieuwe Takken Groeien".
- Wanneer de tijd opraakt, klapt de schakelaar om naar "Dieper Gaan", wat voorkomt dat de AI kostbare laatste seconden verspilt aan het starten van een nieuwe tak die hij niet meer zal kunnen afmaken.

De Resultaten

De onderzoekers hebben deze "Slimme Detective" getest tegenover andere methoden op moeilijke wiskunde- en natuurkundeproblemen. Ze ontdekten dat:

Betere Nauwkeurigheid: De AI lost meer problemen correct op binnen dezelfde token-limiet.
Geen Verspilde Tijd: In tegen tegenstelling tot andere methoden die misschien te vroeg stoppen of aan het einde te veel nieuwe paden starten, gebruikte BG-MCTS het volledige budget efficiënt. Het verkende breed aan het begin en eindigde sterk aan het eind.
Consistente Prestaties: Dit werkte goed voor verschillende soorten AI-modellen en verschillende moeilijkheidsgraden van problemen.

De Kern van het Verhaal

De paper beweert dat door de zoekstrategie van de AI "bewust" te maken van het resterende budget, we veel betere antwoorden kunnen krijgen zonder dat er meer rekenkracht nodig is. Het is also$ als een hardloper leren niet alleen om snel te rennen, maar ook om precies te weten wanneer hij moet sprinten en wanneer hij energie moet sparen, zodat hij de finishlijn met de best mogelijke tijd bereikt.

Technische Samenvatting: Afstemming van Tree-Search Policies op Vaste Token-budgetten bij Test-Time Scaling van LLM's

Probleemstelling

Large Language Models (LLM's) kunnen de kwaliteit van antwoorden verbeteren door middel van Test-Time Scaling, waarbij extra rekenkracht tijdens de inferentie wordt toegewezen zonder de modelparameters bij te werken. Hoewel tree-search decoding (bijv. Monte Carlo Tree Search, MCTS) een effectieve vorm van test-time scaling is, leggen real-world implementaties vaak een vast per-query token-budget op.

Bestaande tree-search policies zijn grotendeels budget-agnostisch. Ze behandelen het token-budget doorgaans slechts als een terminatievoorwaarde in plaats van als een dynamische beperking die het zoekgedrag stuurt. Deze mismatch leidt tot twee primaire faalmodi:

Laatstadium overmatige vertakking (Late-stage over-branching): De zoekopdracht blijft oppervlakkige nodes uitbreiden laat in het proces, waardoor het budget uitgeput raakt voordat het veelbelovende kandidaten kan verfijnen of voltooien.
Voortijdige beëindiging (Premature termination): De zoekopdracht stopt te vroeg, waardoor een deel van het toegewezen budget ongebruikt blijft.

Huidige varianten voor vroegtijdige stopzetting richten zich op het besparen van tokens, maar missen een policy om de zoekstrategie dynamisch te verschuiven van brede exploratie naar verfijning naarmate het resterende budget afneemt.

Methodologie: Budget-Guided MCTS (BG-MCTS)

De auteurs stellen Budget-Guided MCTS (BG-MCTS) voor, een tree-search decoding algoritme dat de zoekpolicy expliciet conditioneert op het resterende token-budget. Het kernmechanisme berust op een budget voldoendeheidsratio $\rho \in [0, 1]$ , gedefinieerd als:
$\rho = 1 - \frac{C_{used}}{B}$
waarbij $C_{used}$ de cumulatieve gegenereerde tokens is en $B$ het totale budget. Naarmate $\rho$ afneemt (nadert naar 0), verschuift de policy van exploratie naar exploitatie en voltooiing.

BG-MCTS introduceert twee budget-geconditioneerde controlemechanismen:

1. Budget-Guided Selectie (BG-PUCT)

Standaard PUCT-selectie wordt aangepast om de exploratiebonus te verzwakken (anneal) en een voltooiingsbias te introduceren:
$\text{BG-PUCT}(p, s, \rho) = \frac{\tilde{W}(s, \rho)}{m_s} + \rho \cdot c \cdot P(s|p) \sqrt{\frac{\ln(m_p)}{m_s}}$

Exploratie-verzwakking (Exploration Annealing): De exploratieterm wordt vermenigvuldigd met $\rho$ . Naarmate het budget slinkt ( $\rho \to 0$ ), neemt de prikkel om nieuwe takken te verkennen af.
Voltooiingsbias (Completion Bias): De geaccumuleerde waarde $\tilde{W}(s, \rho)$ wordt gecorrigeerd door een term die proportioneel is aan de node-diepte $d(x)$ en $(1-\rho)$ . Dit stuurt de selectie naar diepere nodes die dichter bij het genereren van een definitief antwoord liggen, zonder nodes die al een voltooid antwoord bevatten kunstmatig te stimuleren.

2. Budget-Guided Tree Widening

Om verspillende vertakking in het laatste stadium te voorkomen, behandelt BG-MCTS "widening" (het genereren van een nieuwe kind-node vanuit een ouder-node) als een selecteerbare actie naast bestaande kinderen. Een virtuele generatieve kind-node $s_{gen}(p)$ wordt toegevoegd aan de selectieset. De score hiervan is:
$E_{gen}(p, \rho) = \mu(p) + \lambda \cdot \rho \cdot \sigma^2(p)$

$\mu(p)$ en $\sigma^2(p)$ vertegenwoordigen het gemiddelde en de variantie van de scores van de bestaande kinderen.
De term wordt geschaald door $\rho$ . Wanneer het budget ruim is, wordt widening aangemoedigd (vooral als kinderen van mening verschillen). Wanneer het budget laag is, wordt de prikkel om te widen onderdrukt, wat de zoekopdracht dwingt om bestaande veelbelovende trajecten te verdiepen.

Uniform Algoritme

Het algoritme volgt een standaard MCTS-loop, maar maakt zowel de selectie- als de widening-beslissingen afhankelijk van $\rho$ . Dit induceert een wide-to-deep schema: brede exploratie vroeg in de zoekopdracht, gevolgd door gefocuste verfijning en antwoordvoltooiing naarmate het budget wordt uitgeput.

Belangrijkste Bijdragen

Budget-bewuste Policy Design: Het artikel introduceert het eerste tree-search decoding framework dat de zoekgedragingen (exploratie vs. exploitatie vs. widening) dynamisch afstemt op het resterende token-budget, in plaats van het budget enkel als een statisch stopteken te behandelen.
Nieuwe Mechanismen: De voorstel van BG-PUCT (met budget-geconditioneerde exploratie en diepte-gebiaste waardecorrectie) en Virtuele Generatieve Kinderen voor budget-bewuste widening.
Empirische Validatie: Uitgebreide evaluatie over wiskundige redeneringsbenchmarks (MATH500, AIME24/25) en een natuurkunde-redeneringsbenchmark (UGPhysics) met open-weight LLM's (Llama-3.1-8B, Qwen2.5-7B, Qwen3-32B).

Experimentele Resultaten

De auteurs evalueerden BG-MCTS tegen budget-agnostische baselines (Standaard MCTS, AB-MCTS-M, LiteSearch) en scaling baselines (Repeated Sampling, Sequential Refinement) onder vaste budgetten van 10k, 20k en 30k tokens.

Prestaties: BG-MCTS presteerde consequent beter dan alle baselines over alle modellen en budgetten heen. Bijvoorbeeld, op MATH500 met Qwen2.5-7B bereikte BG-MCTS 71,1% nauwkeurigheid bij 30k tokens, vergeleken met 65,9% voor de op één na beste tree-search baseline (MCTS).
Budgetbenutting: In tegen tegenstelling tot LiteSearch, dat vaak voortijdig stopt, blijft BG-MCTS de nauwkeurigheid verbeteren naarmate het de uitputting van het budget nadert.
Kwalitatief Gedrag: Analyse van de zoekbomen toonde aan dat BG-MCTS in een vroeg stadium een brede breedte behoudt, maar later in de zoekopdracht overgaat op het verdiepen van specifieke takken. In contrast hiermee blijft standaard MCTS vaak ondiepe nodes verbreden tot het budget is uitgeput, waardoor het niet slaagt in het voltooien van veelbelovende paden.
Natuurkunde Redeneren: De effectiviteit van de methode strekte zich uit tot UGPhysics, wat aantoont dat het budget-afgestemde wide-to-deep gedrag voordelig is buiten pure wiskundige redenering.

Betekenis en Claims

Het artikel claimt dat het conditioneren van tree-search beslissingen op het resterende budget effectiever is dan het budget enkel als een stopvoorwaarde te behandelen.

Voorspelbare Schaling: BG-MCTS biedt een eenvoudige interface voor voorspelbare test-time scaling, waarbij gebruikers een token-budget specificeren en de policy automatisch zijn exploratie-naar-voltooiing schema aanpast binnen die kostenomgeving.
Implicaties voor Datasynthese: De auteurs merken op dat BG-MCTS de neiging heeft om minder beantwoorde nodes per probleeminstantie te produceren, maar met een aanzienlijk hogere precisie (correctheid). Dit "minder-instanties, betere-antwoorden" regime wordt benadrukt als bijzonder waardevol voor datasynthese, waar hoogwaardige redeneersporen belangrijker zijn dan ruwe dekking.
Robuustheid: De methode blijft effectief, zelfs bij het gebruik van imperfecte process reward models (PRMs) die zwakke of verzadigde signalen geven, wat suggereert dat budget-bewuste structurele wijzigingen de ruis in evaluatiesignalen kunnen compenseren.

Het werk concludeert dat het afstemmen van zoekpolicies op vaste token-beperkingen een cruciale stap is voor de inzet van LLM's in hulpbron-beperkte, real-world omgevingen.