💬 NLP

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

Das Papier schlägt Budget-Guided MCTS (BG-MCTS) vor, einen Tree-Search-Decoding-Algorithmus, der Explorations- und Verfeinerungsstrategien dynamisch an das verbleibende Token-Budget anpasst, um budget-agnostische Baselines bei mathematischen und physikalischen Aufgaben übertreffen zu können.

Ursprüngliche Autoren: Sora Miyamoto, Daisuke Oba, Naoaki Okazaki

Veröffentlicht 2026-06-05

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Sora Miyamoto, Daisuke Oba, Naoaki Okazaki

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Detektiv, der versucht, ein sehr kniffliges Rätsel zu lösen, aber Sie haben eine strikte Regel: Sie dürfen nur eine bestimmte Anzahl von Fragen stellen, bevor die Zeit abläuft. Dies ist genau die Herausforderung, deren sich große Sprachmodelle (LLMs) bei der Lösung komplexer Probleme wie Mathematik oder Physik stellen müssen. Sie haben ein „Token-Budget“ – eine Grenze für die Anzahl der Wörter oder Schritte, die sie generieren können.

Das Papier stellt eine neue Methode namens BG-MCTS (Budget-Guided Monte Carlo Tree Search) vor, um diesen KI-Detektiven zu helfen, Probleme innerhalb dieses strengen Zeitlimits besser zu lösen.

So funktioniert es, unter Verwendung einfacher Analogien:

Das Problem: Der „Einheits-Detektiv“

Derzeit agieren die meisten KI-Suchmethoden wie ein Detektiv, der unabhängig davon, wie viel Zeit noch bleibt, einen festen Plan hat.

Der alte Weg: Der Detektiv verbringt die erste Hälfte des Tages damit, 100 verschiedene Personen nach Hinweisen zu fragen (breite Exploration). Dann, in den letzten 10 Minuten, stellt er fest, dass ihm die Zeit ausgegangen ist, um die vielversprechendsten Spuren tatsächlich zu verfolgen. Er beginnt vielleicht erst kurz vor Ablauf der Zeit mit einer neuen Fragestellung und lässt den Fall dadurch ungelöst. Oder er hört zu früh auf und verschwendet so die letzten 10 Minuten seiner Schicht.
Das Problem: Bestehende Methoden betrachten das Zeitlimit (das Token-Budget) nur als „Stoppschild“. Sie ändern ihre Strategie nicht basierend darauf, wie viel Zeit noch verbleibt.

Die Lösung: Der „Schlaue Detektiv“ (BG-MCTS)

Die Autoren schlagen einen Detektiv vor, der ständig auf seine Uhr schaut und seine Strategie basierend auf der verbleibenden Zeit ändert. Dies nennen sie Budget-Guided MCTS.

Betrachten Sie den Suchprozess als einen Baum, der aus einer Wurzel wächst:

Frühe Phase (Viel Zeit übrig): Wenn der Detektiv noch 100 % seiner Zeit hat, agiert er wie ein Fischer, der ein weit gespanntes Netz auswirft. Er wirft ein weites Netz aus, um viele verschiedene flache Pfade zu erkunden, um zu sehen, wo sich die Fische befinden könnten. Er taucht noch nicht tief ein; er möchte nur den ganzen Ozean sehen.
Späte Phase (Zeit läuft ab): Während die Uhr tickt (sagen wir, auf 25 % des Budgets), hört der Detektiv auf, weite Netze auszuwerfen. Stattdessen wählt er die zwei oder drei vielversprechendsten Stellen aus, die er zuvor gefunden hat, und taucht tief ein. Er hört auf, neue Fragestellungen zu beginnen, und konzentriert sich ganz darauf, die Ermittlungen an den besten Spuren abzuschließen.

Wie die KI es macht

Das Papier beschreibt zwei spezifische Tricks, die die KI anwendet, um dies zu bewältigen:

Der „Zeit-Check“-Score: Wenn die KI entscheidet, welchen Pfad sie als Nächstes verfolgt, nutzt sie eine Formel, die betrachtet, wie viel Budget noch übrig ist.
- Wenn viel Budget vorhanden ist, ermutigt die Formel dazu, neue, unerkundete Pfade auszuprobieren.
- Wenn das Budget niedrig ist, bestraft die Formel das Starten neuer Pfade und belohnt das tiefere Vordringen in Pfade, die bereits gut aussehen.
Der „Neue Zweig“-Schalter: Die KI hat einen speziellen Schalter, der entscheidet, ob sie einen neuen Zweig am Baum wachsen lässt oder nur tiefer in einen bestehenden Zweig geht.
- Wenn Zeit im Überfluss vorhanden ist, ist der Schalter auf „Neue Zweige wachsen lassen“ eingestellt.
- Wenn die Zeit knapp wird, schaltet der Schalter auf „Tiefer gehen“, um zu verhindern, dass die KI ihre letzten Sekunden damit verschwendet, einen neuen Zweig zu beginnen, den sie nicht mehr rechtzeitig abschließen kann.

Die Ergebnisse

Die Forscher haben diesen „schlauen Detektiven“ gegen andere Methoden bei schwierigen Mathematik- und Physikproblemen getestet. Sie fanden heraus:

Bessere Genauigkeit: Die KI löste mehr Probleme korrekt innerhalb desselben Token-Limits.
Keine Zeitverschwendung: Im Gegensatz zu anderen Methoden, die zu früh aufhören oder am Ende zu viele neue Pfade starten könnten, nutzte BG-MCTS das gesamte Budget effizient. Es explorierte zu Beginn breit und schloss am Ende stark ab.
Konsistente Leistung: Dies funktionierte gut über verschiedene Arten von KI-Modellen und unterschiedliche Schwierigkeitsgrade der Probleme hinweg.

Das Fazit

Das Papier behauptet, dass wir durch die Anpassung der Suchstrategie einer KI an das verbleibende Budget wesentlich bessere Antworten erhalten können, ohne mehr Rechenleistung zu benötigen. Es ist, als würde man einem Läufer nicht nur beibringen, schnell zu laufen, sondern auch genau zu wissen, wann er sprinten und wann er Energie sparen muss, um die Ziellinie mit der bestmöglichen Zeit zu überqueren.

Technisches Resümee: Abstimmung von Baum-Such-Policies auf feste Token-Budgets beim Test-Time Scaling von LLMs

Problemstellung

Große Sprachmodelle (LLMs) können die Antwortqualität durch Test-Time Scaling verbessern, bei dem zusätzliche Rechenleistung während der Inferenz zugewiesen wird, ohne die Modellparameter zu aktualisieren. Während Baum-Such-Dekodierung (z. B. Monte Carlo Tree Search, MCTS) eine effektive Form des Test-Time Scalings darstellt, unterliegen reale Anwendungen oft einem festen pro Abfrage festgelegten Token-Budget.

Bestehende Baum-Such-Policies sind weitgehend budget-agnostisch. Sie behandeln das Token-Budget typischerweise lediglich als Abbruchbedingung und nicht als dynamische Constraint, die das Suchverhalten steuert. Diese Diskrepanz führt zu zwei primären Fehlermodi:

Spätphasen-Überbreitung (Late-stage over-branching): Die Suche setzt die Expansion flacher Knoten spät im Prozess fort und erschöpft dadurch das Budget, bevor sie vielversprechende Kandidaten verfeinern oder abschließen kann.
Vorzeitiger Abbruch (Premature termination): Die Suche stoppt zu früh und lässt einen Teil des zugewiesenen Budgets ungenutzt.

Aktuelle Early-Stopping-Varianten konzentrieren sich auf das Einsparen von Tokens, verfügen jedoch nicht über eine Policy, die die Suchstrategie dynamisch von breiter Exploration zur Verfeinerung verschiebt, wenn das verbleibende Budget abnimmt.

Methodik: Budget-Guided MCTS (BG-MCTS)

Die Autoren schlagen Budget-Guided MCTS (BG-MCTS) vor, einen Baum-Such-Dekodierungsalgorithmus, der seine Suchpolicy explizit in Abhängigkeit vom verbleibenden Token-Budget konditioniert. Der Kernmechanismus basiert auf einem Budget-Suffizienz-Verhältnis $\rho \in [0, 1]$ , definiert als:
$\rho = 1 - \frac{C_{used}}{B}$
wobei $C_{used}$ die kumulierten generierten Tokens und $B$ das Gesamtbudget ist. Wenn $\rho$ sinkt (sich 0 nähert), verschiebt sich die Policy von Exploration hin zu Exploitation und Vervollständigung.

BG-MCTS führt zwei budget-konditionierte Kontrollmechanismen ein:

1. Budget-Guided Selection (BG-PUCT)

Die Standard-PUCT-Selektion wird modifiziert, um den Explorations-Bonus zu dämpfen (Annealing) und einen Vervollständigungs-Bias einzuführen:
$\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}}$

Explorations-Dämpfung (Exploration Annealing): Der Explorations-Term wird mit $\rho$ multipliziert. Wenn das Budget schwindet ( $\rho \to 0$ ), nimmt der Anreiz, neue Zweige zu explorieren, ab.
Vervollständigungs-Bias (Completion Bias): Der akkumulierte Wert $\tilde{W}(s, \rho)$ wird durch einen Term korrigiert, der proportional zur Knotentiefe $d(x)$ und $(1-\rho)$ ist. Dies begünstigt die Selektion tieferer Knoten, die näher an der Generierung einer finalen Antwort liegen, ohne Knoten künstlich zu fördern, die bereits eine abgeschlossene Antwort enthalten.

2. Budget-Guided Tree Widening

Um eine verschwendete Breitensuche in der Spätphase zu verhindern, behandelt BG-MCTS das „Widening“ (Generierung eines neuen Kindknotens aus einem Elternknoten) als eine wählbare Aktion neben den bestehenden Kindern. Ein virtuelles generatives Kind $s_{gen}(p)$ wird zum Selektionssatz hinzugefügt. Dessen Score ist:
$E_{gen}(p, \rho) = \mu(p) + \lambda \cdot \rho \cdot \sigma^2(p)$

$\mu(p)$ und $\sigma^2(p)$ repräsentieren den Mittelwert und die Varianz der Scores der bestehenden Kinder.
Der Term wird durch $\rho$ skaliert. Wenn das Budget reichlich vorhanden ist, wird Widening gefördert (insbesondere wenn die Kinder uneinig sind). Wenn das Budget knapp wird, wird der Anreiz zum Widening unterdrückt, was die Suche dazu zwingt, bestehende vielversprechende Trajektorien zu vertiefen.

Vereinheitlichter Algorithmus

Der Algorithmus folgt einer Standard-MCTS-Schleife, macht jedoch sowohl die Selektions- als auch die Widening-Entscheidungen von $\rho$ abhängig. Dies induziert einen Wide-to-Deep-Schedule: eine breite Exploration zu Beginn der Suche, gefolgt von fokussierter Verfeinerung und Antwort-Vervollständigung, wenn das Budget erschöpft wird.

Zentrale Beiträge

Budget-bewusste Policy-Gestaltung: Das Paper stellt das erste Baum-Such-Dekodierungs-Framework vor, das sein Suchverhalten (Exploration vs. Exploitation vs. Widening) dynamisch an das verbleibende Token-Budget anpasst, anstatt das Budget lediglich als statisches Stoppsignal zu behandeln.
Neuartige Mechanismen: Der Vorschlag von BG-PUCT (mit budget-konditionierter Exploration und tiefen-biassierter Wertkorrektur) und Virtuellen Generativen Kindern für ein budget-bewusstes Widening.
Empirische Validierung: Umfassende Evaluierung über mathematische Reasoning-Benchmarks (MATH500, AIME24/25) und einen Physik-Reasoning-Benchmark (UGPhysics) unter Verwendung von Open-Weight-LLMs (Llama-3.1-8B, Qwen2.5-7B, Qwen3-32B).

Experimentelle Ergebnisse

Die Autoren evaluierten BG-MCTS gegen budget-agnostische Baselines (Standard MCTS, AB-MCTS-M, LiteSearch) und Scaling-Baselines (Repeated Sampling, Sequential Refinement) unter festen Budgets von 10k, 20k und 30k Tokens.

Performance: BG-MCTS übertraf konsistent alle Baselines über alle Modelle und Budgets hinweg. Beispielsweise erreichte BG-MCTS auf MATH500 mit Qwen2.5-7B eine Genauigkeit von 71,1 % bei 30k Tokens, verglichen mit 65,9 % der nächstbesten Baum-Such-Baseline (MCTS).
Budget-Ausnutzung: Im Gegensatz zu LiteSearch, das oft vorzeitig stoppt, verbessert BG-MCTS die Genauigkeit kontinuierlich, während es sich dem Budget-Ende nähert.
Qualitatives Verhalten: Eine Analyse der Suchbäume ergab, dass BG-MCTS früh in der Suche eine breite Breite beibehält, aber spät in der Suche zu einer Vertiefung spezifischer Zweige übergeht. Im Gegensatz dazu führt Standard-MCTS oft eine Breitensuche flacher Knoten fort, bis das Budget erschöpft ist, wodurch es versäumt, vielversprechende Pfade abzuschließen.
Physik-Reasoning: Die Effektivität der Methode erstreckte sich auch auf UGPhysics, was zeigt, dass das budget-ausgerichtete Wide-to-Deep-Verhalten über reines mathematisches Reasoning hinaus von Nutzen ist.

Bedeutung und Behauptungen

Das Paper behauptet, dass die Konditionierung von Baum-Such-Entscheidungen auf das verbleibende Budget effektiver ist, als das Budget lediglich als Stoppbedingung zu behandeln.

Vorhersehbares Scaling-Verhalten: BG-MCTS bietet eine einfache Schnittstelle für vorhersehbares Test-Time Scaling, bei dem Nutzer ein Token-Budget spezifizieren und die Policy ihren Exploration-zu-Completion-Plan innerhalb dieses Kostenrahmens automatisch anpasst.
Implikationen für die Datensynthese: Die Autoren merken an, dass BG-MCTS dazu neigt, weniger beantwortete Knoten pro Probleminstanz zu produzieren, aber mit signifikant höherer Präzision (Korrektheit). Dieses „weniger Instanzen, bessere Antworten“-Regime wird als besonders wertvoll für die Datensynthese hervorgehoben, bei der hochwertige Reasoning-Trajektorien kritischer sind als die reine Abdeckung.
Robustheit: Die Methode bleibt auch bei der Verwendung unvollkommener Process Reward Models (PRMs) effektiv, die schwache oder gesättigte Signale liefern, was darauf hindeutet, dass budget-bewusste strukturelle Änderungen verrauschte Evaluationssignale kompensieren können.

Die Arbeit kommt zu dem Schluss, dass die Abstimmung von Suchpolicies auf feste Token-Beschränkungen ein entscheidender Schritt für den Einsatz von LLMs in ressourcenbeschränkten, realen Umgebungen ist.