💬 NLP

DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Monte Carlo Tree Search

Das Paper stellt DeepSearch vor, ein Framework, das Monte-Carlo-Baumsuche direkt in den Reinforcement-Learning-Training mit verifizierbaren Belohnungen integriert, um das Problem der unzureichenden Exploration zu überwinden und mathematische Schlussfolgerungen effizienter als herkömmliche Methoden zu verbessern.

Ursprüngliche Autoren: Fang Wu, Weihao Xuan, Heli Qi, Ximing Lu, Aaron Tu, Li Erran Li, Yejin Choi

Veröffentlicht 2026-04-08

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Fang Wu, Weihao Xuan, Heli Qi, Ximing Lu, Aaron Tu, Li Erran Li, Yejin Choi

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

DeepSearch: Wie man KI beim Denken lernt, statt sie nur länger arbeiten zu lassen

Stellen Sie sich vor, Sie versuchen, einem sehr intelligenten, aber etwas verunsicherten Schüler beizubringen, komplexe Matheaufgaben zu lösen.

Bisher gab es zwei Hauptmethoden, wie Forscher dies taten:

Die "Brute-Force"-Methode: Man ließ den Schüler stundenlang hunderte von Aufgaben lösen, in der Hoffnung, dass er irgendwann durch pure Wiederholung den Durchblick bekommt. Das Problem: Irgendwann stößt er an eine Wand. Er arbeitet immer härter, wird aber nicht klüger. Es ist, als würde man einen Marathonläufer bitten, einfach weiterzulaufen, obwohl er eigentlich eine neue Route lernen müsste.
Die "Inferenz"-Methode: Der Schüler lernt nur die Aufgaben, aber wenn er eine neue Aufgabe bekommt, darf er erst einmal lange nachdenken, verschiedene Wege ausprobieren und sich selbst korrigieren, bevor er die Antwort gibt. Das funktioniert gut, aber der Schüler hat diese Fähigkeit nicht gelernt, er nutzt sie nur als Trick beim Test.

DeepSearch ist eine revolutionäre neue Methode, die diese beiden Welten verbindet. Sie sagt: "Lass uns dem Schüler beibringen, während des Trainings strategisch zu suchen, statt nur blind zu raten."

Hier ist die Erklärung mit ein paar einfachen Analogien:

1. Das Problem: Der blinde Spaziergang

Stellen Sie sich vor, der KI-Modell-Schüler muss durch einen riesigen, dunklen Wald (die Welt der möglichen Lösungen) navigieren, um einen Schatz (die richtige Antwort) zu finden.

Die alte Methode (RLVR): Der Schüler läuft einfach geradeaus. Wenn er auf einen Baum stößt, dreht er sich um und läuft wieder los. Er trifft oft auf Sackgassen, weil er nicht systematisch den Wald erkundet. Er verpasst wichtige Pfade, die zum Schatz führen.
Das Ergebnis: Der Schüler wird müde (Rechenzeit), aber er findet den Schatz nicht schneller. Er bleibt stecken.

2. Die Lösung: DeepSearch als "Kartenzeichner"

DeepSearch gibt dem Schüler eine Landkarte und einen Kompass (einen Algorithmus namens Monte Carlo Tree Search, kurz MCTS), den er während des Trainings benutzt.

Statt blind loszulaufen, macht der Schüler Folgendes:

Er zeichnet einen Baum: Er stellt sich vor, er könnte an jeder Kreuzung mehrere Wege gehen. Er zeichnet diese Wege auf (wie Äste an einem Baum).
Er sucht strategisch: Er ignoriert nicht einfach alle Wege. Er schaut sich an: "Welcher Ast sieht vielversprechend aus?" oder "Wo bin ich mir unsicher?"
Der Clou: Früher nutzte man solche Landkarten nur während der Prüfung (Inferenz). DeepSearch nutzt sie beim Lernen. Der Schüler lernt also nicht nur die richtige Antwort, sondern lernt, wie man den Wald durchsucht.

3. Die drei genialen Tricks von DeepSearch

Die Autoren haben drei spezielle Werkzeuge entwickelt, um diesen Lernprozess zu optimieren:

Trick 1: Der "Blick über den ganzen Wald" (Global Frontier Selection)
- Die alte Methode: Der Schüler schaut sich nur den nächsten Ast an und entscheidet dann. Das ist wie ein Tunnelblick.
- DeepSearch: Der Schüler schaut sich alle offenen Wege im gesamten Wald gleichzeitig an. Er wählt den Weg aus, der am vielversprechendsten aussieht, auch wenn er weit weg ist. So verpasst er keine versteckten Abkürzungen.
Trick 2: Lernen aus den "sichersten Fehlern"
- Das Problem: Manchmal findet der Schüler keine richtige Antwort.
- Die alte Methode: Er wirft alle falschen Antworten weg oder wählt zufällig eine aus.
- DeepSearch: Der Schüler sucht sich den falschen Weg aus, bei dem er sich am sichersten war, dass er richtig liegt (niedrige Unsicherheit). Warum? Weil dieser Fehler am "tückischsten" ist. Wenn er lernt, warum dieser spezifische, selbstbewusste Weg falsch ist, lernt er am meisten. Es ist wie ein Lehrer, der sagt: "Du warst dir zu 100% sicher, dass 2+2=5 ist. Das müssen wir dringend korrigieren!"
Trick 3: Die "Spickzettel-Mappe" (Adaptive Replay Buffer)
- Das Problem: Es ist Verschwendung, immer wieder dieselben Aufgaben zu lösen, die der Schüler schon kann.
- DeepSearch: Sobald der Schüler eine schwierige Aufgabe gelöst hat, legt er die Lösung in eine Mappe (Replay Buffer). Beim nächsten Training schaut er in die Mappe, statt die Aufgabe neu zu lösen. Er konzentriert seine Energie nur noch auf die Aufgaben, die er noch nicht kann. Das spart enorm viel Zeit und Energie.

4. Das Ergebnis: Schneller und schlauer

Das Paper zeigt, dass DeepSearch mit einem sehr kleinen Modell (nur 1,5 Milliarden Parameter – für KI-Verhältnisse winzig) Ergebnisse erzielt, die besser sind als riesige Modelle, die stundenlang trainiert wurden.

Die Metapher: Stellen Sie sich vor, ein alter, müder Ochse (das alte Modell) zieht einen Pflug durch das Feld. Er braucht 10 Stunden für ein Feld. Ein junger, gut trainierter Bauer mit einem modernen Traktor (DeepSearch) braucht nur 2 Stunden für dasselbe Feld und pflügt es tiefer und sauberer.
Die Zahlen: DeepSearch erreichte einen neuen Rekord in Mathe-Aufgaben (62,95% Genauigkeit) und nutzte dabei 5,7-mal weniger Rechenzeit als die bisherigen besten Methoden.

Fazit

DeepSearch beweist, dass wir KI nicht einfach nur "länger arbeiten" lassen müssen, um sie schlauer zu machen. Stattdessen müssen wir ihr beibringen, strategisch zu denken.

Es ist der Unterschied zwischen jemandem, der blind durch einen Labyrinth rennt, bis er zufällig den Ausgang findet, und jemandem, der lernt, die Wände zu analysieren, Karten zu zeichnen und den kürzesten Weg zu finden. DeepSearch bringt der KI bei, wie man den Weg plant, bevor man ihn geht.

1. Problemstellung

Das Paper adressiert ein fundamentales Limit bei der Anwendung von Reinforcement Learning mit verifizierbaren Belohnungen (RLVR) für das Training von Sprachmodellen (LLMs) in komplexen reasoning-Aufgaben (z. B. Mathematik).

Das Plateau-Problem: Aktuelle Studien zeigen, dass RLVR-Modelle nach einigen tausend Optimierungsschritten ein Leistungsplateau erreichen. Trotz weiterer Recheninvestitionen (längeres Training) nehmen die Leistungsgewinne ab.
Ursache – Spärliche Exploration: Herkömmliche RLVR-Ansätze verlassen sich auf begrenzte „Rollouts" (direkte Generierung von Lösungen durch das Modell). Diese Muster der Exploration sind zu spärlich, um kritische Denkpfade zu finden oder den Lösungsraum systematisch abzudecken. Modelle lernen oft nur aus den wenigen generierten Lösungen, verpassen aber wichtige Zwischenstufen oder alternative Pfade.
Trennung von Training und Inferenz: Bisherige Methoden nutzen strukturierte Suchalgorithmen (wie Baum-Suche) meist nur zur Inferenzzeit (Testzeit), lassen diese aber im Trainingsprozess außen vor. Dies verhindert, dass das Modell aus dem Suchprozess selbst lernt.

2. Methodik: DeepSearch

DeepSearch ist ein Framework, das Monte-Carlo-Baumsuche (MCTS) direkt in den RLVR-Trainingszyklus integriert. Statt die Trainingsdauer nur zu verlängern („Scaling by Depth"), wird die Breite der Exploration während des Trainings skaliert.

Die Architektur besteht aus drei Hauptkomponenten:

A. MCTS-Integration mit globaler Frontier-Selektion

Anstatt traditionelle, rein lokale UCT-Selektionen (Upper Confidence Bound for Trees) von der Wurzel bis zum Blatt zu verwenden, führt DeepSearch eine globale Frontier-Selektion ein:

Expansion: Das Modell generiert Kandidaten für den nächsten Denk-Schritt.
Globale Priorisierung: Statt nur den nächsten Pfad lokal zu wählen, werden alle aktuellen Blattknoten (Frontier) des Suchbaums gleichzeitig bewertet.
Bewertungsfunktion (Frontier Priority Score): Die Auswahl des nächsten Knotens zur Expansion basiert auf einer Formel, die drei Faktoren kombiniert:
1. Qualitätspotenzial: Basierend auf dem Q-Wert des Elternknotens.
2. Unsicherheits-Bonus: Basierend auf der Entropie der Policy (fördert die Exploration von Pfaden, bei denen das Modell unsicher ist).
3. Tiefen-Bonus: Begünstigt tiefere Pfade, um komplexe Denkketten zu erreichen.
Entropie-basierte Selektion bei Fehlern: Wenn kein korrekter Lösungsweg gefunden wird, wird der „selbstsicherste falsche Pfad" (der Pfad mit der niedrigsten Entropie/Unsicherheit) ausgewählt, um gezieltes Feedback für systematische Denkfehler zu geben.

B. Asymmetrische Q-Wert-Backup-Strategie

DeepSearch verwendet eine modifizierte Rückpropagierung von Belohnungen (Q-Werte) entlang der ausgewählten Pfade:

Q-Wert-Initialisierung: Startet bei 0.
Asymmetrische Update-Regel:
- Wenn ein Knoten auf einem korrekten Pfad liegt, wird sein Q-Wert positiv aktualisiert und behält diesen Wert, selbst wenn er später auf falschen Pfaden erscheint.
- Negative Updates werden nur für Knoten erlaubt, die niemals auf einem korrekten Pfad gesehen wurden.
- Dies verhindert, dass wertvolle Zwischenstufen durch nachfolgende Fehlversuche „vergiftet" werden.
Q-Wert-Soft-Clipping: Um Explosionen der Q-Werte zu verhindern, werden diese mittels einer Tanh-Funktion weich begrenzt, während die Gradienten erhalten bleiben.

C. Adaptive Trainingsstrategie mit Replay-Buffer

Um die Rechenkosten zu senken und Katastrophales Vergessen zu vermeiden:

Iteratives Filtern: Nur Probleme, bei denen das Modell eine niedrige Erfolgsrate hat (unter einem Schwellenwert $\delta$ ), werden für das MCTS-Training ausgewählt.
Replay-Buffer & Caching: Korrekte Lösungen, die einmal durch MCTS gefunden wurden, werden zwischengespeichert. Bei zukünftigen Trainingsiterationen werden diese Probleme nicht erneut durch die volle MCTS-Suche geschickt, sondern die gespeicherte Lösung wird direkt genutzt (plus einige direkte Rollouts).
Effizienz: Dies konzentriert die Rechenleistung auf die wirklich schwierigen, noch ungelösten Probleme.

D. Tree-GRPO Trainingsziel

Das Modell wird mit einer angepassten Version von GRPO (Grouped Relative Policy Optimization) trainiert, die die Q-Werte der einzelnen Knoten im Baum als Advantage-Signale nutzt, anstatt nur das Endergebnis zu belohnen. Dies ermöglicht ein feinkörnigeres Credit Assignment für jeden Denk-Schritt.

3. Hauptbeiträge

Global Frontier Selection: Eine neue Suchstrategie, die den gesamten Baum betrachtet und vielversprechende Knoten priorisiert, anstatt sich in lokalen Subbäumen zu verlieren.
Entropie-gesteuerte negative Selektion: Die systematische Identifizierung von „selbstsicheren Fehlern" (niedrige Entropie, aber falsche Lösung) als Lehrmaterial.
Adaptives Replay-Buffer-Training: Ein Mechanismus, der Rechenressourcen dynamisch auf schwierige Probleme lenkt und bereits gelöste Probleme durch Caching effizient wiederverwendet.
Tree-GRPO: Ein Trainingsziel, das Q-Werte auf Knotenebene nutzt, um die Lernsignale zu verfeinern.

4. Ergebnisse

Die Experimente wurden auf mathematischen Reasoning-Benchmarks (AIME 2024/2025, AMC2023, MATH500, Minerva, Olympiad) mit einem 1.5B-Parameter-Modell (basierend auf Nemotron-Research-Reasoning-Qwen-1.5B v2) durchgeführt.

Leistung: DeepSearch erreicht eine durchschnittliche Genauigkeit von 62,95 %. Dies stellt einen neuen State-of-the-Art für Modelle dieser Größe dar und übertrifft den vorherigen Bestwert (61,70 %) signifikant.
Effizienz: DeepSearch erreicht diese Ergebnisse mit 5,7-mal weniger GPU-Stunden als herkömmliche Extended-Training-Ansätze, die versuchen, die Leistung durch bloßes Verlängern der Trainingszeit zu steigern.
- Beispiel: Während Extended Training bei 1.883 GPU-Stunden bei 62,02 % stagniert, erreicht DeepSearch 62,95 % in nur 330 GPU-Stunden.
Ablationsstudien:
- Die globale Frontier-Selektion reduziert die Anzahl der benötigten Iterationen im Vergleich zu Vanilla UCT um ca. 10 %.
- Die Selektion des „selbstsichersten falschen Pfades" (niedrigste Entropie) erweist sich als überlegen gegenüber zufälliger oder „unsicherster" Fehlauswahl.
- Die Kombination aus Q-Wert-Updates und feinkörniger Normalisierung ist entscheidend für die Stabilität.

5. Bedeutung und Fazit

DeepSearch demonstriert, dass das Skalieren von Reasoning-Fähigkeiten nicht primär durch mehr Rechenleistung oder längere Trainingszeiten („Brute-Force") erreicht werden muss, sondern durch algorithmische Innovation und strategische Exploration.

Paradigmenwechsel: Der Ansatz verschiebt den Fokus von „Inferenzzeit-Suche" hin zu „Trainingszeit-Suche". Das Modell lernt nicht nur aus dem Endergebnis, sondern aus dem systematischen Suchprozess selbst.
Skalierbarkeit: Die Ergebnisse deuten darauf hin, dass die Grenzen aktueller RLVR-Methoden durch unzureichende Exploration entstehen, nicht durch mangelnde Rechenkapazität.
Zukunft: DeepSearch legt den Grundstein für eine neue Generation von Reasoning-Modellen, die strukturierte Suchalgorithmen nutzen, um komplexe Probleme effizienter und robuster zu lösen, und bietet einen Weg, um das Plateau des aktuellen RLVR-Trainings zu überwinden.

Zusammenfassend zeigt das Paper, dass die Integration von MCTS in den Trainingsloop eine qualitative Verbesserung der Lernkurve ermöglicht und eine effizientere Alternative zum reinen „Scaling by Compute" darstellt.