💻 computer science

GraphPO: Graph-based Policy Optimization for Reasoning Models

GraphPO führt ein neuartiges graphbasiertes Reinforcement-Learning-Framework ein, das Reasoning-Rollouts als gerichtete azyklische Graphen darstellt, um semantisch äquivalente Pfade zu verschmelzen und Informationen über Zweige hinweg zu teilen, wodurch redundante Exploration und die Varianz der Advantage-Schätzung reduziert werden, während es bestehende Ketten- und Baum-basierte Methoden bei Reasoning-Benchmarks übertrifft.

Ursprüngliche Autoren: Yuliang Zhan, Xinyu Tang, Jian Li, Dandan Zheng, Weilong Chai, Jingdong Chen, Jun Zhou, Ge Wu, Wenyue Tang, Hao Sun

Veröffentlicht 2026-06-19

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Yuliang Zhan, Xinyu Tang, Jian Li, Dandan Zheng, Weilong Chai, Jingdong Chen, Jun Zhou, Ge Wu, Wenyue Tang, Hao Sun

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 unterrichten einen sehr klugen, aber etwas repetitiven Schüler, wie man ein komplexes mathematisches Problem löst oder ein Stück Code schreibt. Sie geben ihm keine Schritt-für-Schritt-Anleitungen; stattdessen lassen Sie ihn verschiedene Ansätze ausprobieren und sagen ihm erst ganz am Ende: „Richtig!“ oder „Falsch!“.

So lernen aktuelle KI-Modelle (genannt Large Reasoning Models). Sie raten, raten und raten weiter, bis sie die richtige Antwort finden. Aber es gibt zwei große Probleme mit dieser Methode, die das Paper namens GraphPO zu lösen versucht.

Das Problem: Der „einsame Entdecker“ und die „verzweigende Baumstruktur“

1. Die verschwendete Anstrengung (Chain-Methode)
Stellen Sie sich vor, Sie schicken 100 Schüler in ein Labyrinth. Jeder Schüler geht einen völlig separaten Weg.

Das Problem: Selbst wenn sie auf unterschiedlichen Pfaden sind, landen 50 von ihnen vielleicht in genau derselben Sackgasse oder laufen durch denselben verwirrenden Flur. Sie verschwenden Zeit und Energie, indem sie immer wieder exakt dasselbe tun. In der Welt der KI nennt man das „redundante Exploration“.

2. Die „Baum“-Methode (Die Verbesserung, aber nicht perfekt)
Um diese Verschwendung zu beheben, versuchten Forscher eine „Baum“-Methode. Stellen Sie sich vor, die Schüler starten gemeinsam, und an der ersten Weggabelung teilen sie sich auf. Wenn zwei Schüler die gleiche erste Abzweigung nehmen, gehen sie ein Stück weit gemeinsam weiter.

Das Problem: Das hilft ein wenig, aber sobald sie sich an einer zweiten Weggabelung trennen, sind sie wieder auf sich allein gestellt. Wenn zwei verschiedene Zweige des Baumes schließlich zum selben verwirrenden Flur führen (selbst wenn sie über unterschiedliche Routen dorthin gelangt sind), wissen die Schüler nicht, dass sie am selben Ort sind. Sie erkunden diesen Flur weiterhin separat, was wiederum Zeit verschwendet. Zudem können sie die „guten Nachrichten“ nicht teilen: Wenn ein Schüler den Ausgang aus diesem Flur findet, müssen die anderen weiter raten.

Die Lösung: Die „Intelligente Karte“ (GraphPO)

Die Autoren schlagen GraphPO vor, was so etwas ist wie eine lebendige, gemeinsame Karte anstelle eines bloßen Baums.

So funktioniert es:

Die Karte (Der Graph): Anstatt nur Linien (Zweige) zu zeichigen, erstellt die KI eine Karte, in der jeder „Raum“ (ein Schritt im Denkprozess) ein Knotenpunkt ist.
Zwillinge erkennen (Semantisches Verschmelzen): Während die KI exploriert, betrachtet sie die „Räume“, die verschiedene Pfade erreicht haben. Wenn zwei verschiedene Pfade in einem Raum ankommen, der sich gleich anfühlt (selbst wenn die Worte, die dorthin geführt haben, leicht unterschiedlich waren), sagt die KI: „Hey, ihr zwei seid am selben Ort!“ und führt sie zu einem einzigen Punkt auf der Karte zusammen.
Die guten Nachrichten teilen (Suffix-Sharing): Sobald zwei Pfade verschmolzen sind, teilen sie alles, was danach kommt. Wenn ein Pfad von diesem verschmolzenen Punkt aus die richtige Antwort findet, erhält der andere Pfad sofort die Anerkennung für diesen Erfolg, ohne den Rest des Weges erneut gehen zu müssen.
Der „Effizienz“-Bonus: Die KI lernt auch, den kürzesten Pfad zu einem bestimmten „Raum“ zu bevorzugen. Wenn Pfad A 10 Schritte braucht, um zu einem guten Punkt zu gelangen, und Pfad B 15 Schritte zum selben Punkt benötigt, lernt die KI, Pfad A zu bevorzugen. Es ist, als würde man den Schüler belohnen, der die Abkürzung nimmt.

Das Ergebnis: Schlauer, schneller und weniger verschwenderisch

Durch die Verwendung dieses „Intelligenten Karten“-Ansatzes erreicht GraphPO drei Hauptziele:

Keine verschwendeten Schritte mehr: Es verhindert, dass die KI dieselben Sackgassen doppelt erkundet. Es lenkt das „Budget“ (die Rechenleistung) um, um neue Bereiche zu erforschen, anstatt alte zu wiederholen.
Besseres Lernen aus Fehlern: Da es ähnliche Pfade zusammenführt, kann es der KI viel früher sagen: „Dieser spezifische Schritt war gut“, selbst wenn das Endergebnis noch nicht perfekt ist. Es verwandelt ein vages „Du hattest am Ende recht“ in ein klares „Dieser spezifische Zug war klug“.
Kürzere Antworten: Da es den kürzesten Weg zu einer Lösung belohnt, lernt die KI, präziser und effizienter zu werden, indem sie unnötiges Gerede weglässt.

Das Fazit

Das Paper hat dies an drei verschiedenen KI-Modellen bei mathematischen Problemen, Programmieraufgaben und Suchaufgaben getestet. Die Ergebnisse zeigten, dass GraphPO die alten Methoden konsequent geschlagen hat (sowohl die einsamen Entdecker als auch die verzweigenden Bäume). Es löste mehr Probleme, verbrauchte weniger Wörter dafür und lernte schneller – und das alles bei gleicher Rechenleistung.

Kurz gesagt: GraphPO lehrt die KI, nicht mehr im Kreis zu laufen, sondern eine Karte zu teilen, wodurch der Lernprozess wesentlich intelligenter und weniger verschwenderisch wird.

Technisches Resümee: GraphPO – Graphbasierte Policy-Optimierung für Reasoning-Modelle

1. Problemstellung

Reinforcement Learning mit verifizierbaren Belohnungen (RLVR) ist zum Standardparadigma für die Verbesserung von Large Reasoning Models (LRMs) geworden. Aktuelle RLVR-Methoden stehen jedoch vor zwei primären Einschränkungen:

Redundante Exploration: Die unabhängige Stichprobenentnahme von Antworten führt oft dazu, dass verschiedene Trajektorien ähnliche Zwischenschritte im Reasoning enthalten. Dies führt zu verschwendeter Rechenleistung und begrenzt die Diversität der Exploration.
Spärliche Belohnungssignale: RLVR stützt sich typischerweise auf binäre Belohnungen für die Endantwort. Diese Spärlichkeit macht es schwierig, die Kreditwürdigkeit (Credit Assignment) spezifischer Zwischenschritte im Reasoning zuzuweisen, die zur endgültigen Antwort beitragen.

Obwohl baumbasierte Methoden (z. B. TreeRL, PROS) einige Redundanzen durch das Teilen von Präfixen und die Bereitstellung feingranularer Signale an Verzweigungspunkten adressieren, behandeln sie divergierende Zweige dennoch als unabhängige Pfade. Folglich können Informationen nicht geteilt werden, wenn verschiedene Zweige semantisch ähnliche Zwischenzustände erreichen, was zu wiederholter Exploration und einer höheren Varianz bei der Schätzung des Vorteils (Advantage Estimation) führt.

2. Methodik: GraphPO

Die Autoren schlagen GraphPO vor, ein neuartiges RL-Framework, das Reasoning-Rollouts als gerichteten azyklischen Graphen (DAG) modelliert, anstatt als Kette oder Baum.

2.1 Graphkonstruktion und Zusammenführung

Struktur: In GraphPO werden die Reasoning-Schritte als Kanten und die semantischen Zwischenzustände (zusammengefasst aus dem Reasoning-Pfad ausgehend vom Prompt) als Knoten dargestellt.
Äquivalenzklassen: Das Framework konstruiert den Graphen inkrementell, indem es semantisch ähnliche Zustände über verschiedene Pfade hinweg mittels Knoten-Embeddings (via Kosinus-Ähnlichkeit) erkennt. Wenn die Ähnlichkeit einen Schwellenwert $\kappa$ überschreitet, werden die Knoten zu Äquivalenzklassen zusammengeführt.
Budget-Reallokation: Wenn ein Pfad eine bestehende Äquivalenzklasse erreicht, wird eine weitere Expansion als wahrscheinlich redundant eingestuft. GraphPO halbiert das Budget für die nächste Ebene dieses Pfades (behält mindestens eine Fortsetzung bei) und reallokiert die eingesparten Rechenressourcen auf neuartige Frontier-Zustände, wodurch eine breitere Exploration gefördert wird.

2.2 Graph-Belohnung (Prozess-Supervision aus Ergebnissen)

GraphPO konvertiert spärliche Ergebnisbelohnungen in dichte Schritt-Belohnungen, ohne dass annotierte Prozess-Labels erforderlich sind:

Zustandsbewertung (State Scoring): Jedem Knoten wird ein Score zugewiesen, der auf den von ihm aus erreichbaren verifizierten Antworten basiert. Wenn ein Knoten zu einer Äquivalenzklasse gehört, wird sein Score mit den Scores anderer Knoten in dieser Klasse unter Verwendung eines Pooling-Koeffizienten $w$ zusammengeführt.
Schritt-Belohnungen: Die Belohnung für eine spezifische Kante (Schritt) wird als Differenz der Zustands-Scores zwischen dem Ziel- und dem Quellknoten berechnet, diskontiert durch die Ähnlichkeit zwischen den Endpunkten. Dies ermöglicht es frühzeitig gestoppten Zweigen, die Anerkennung (Credit) von äquivalenten Partnern zu erhalten, die erfolgreich eine korrekte Antwort erreicht haben.

2.3 Dual-Group Graph Advantage

Um sowohl die Effizienz des Reasonings als auch das Credit Assignment zu verbessern, führt GraphPO eine Dual-Group-Vorteilsabschätzung ein:

Korrektheits-Gruppe ( $A_{cor}$ ): Vergleicht ausgehende Schritte aus demselben semantischen Zustand. Sie berechnet den Vorteil eines spezifischen Schritts relativ zu anderen Schritten, die denselben Zustand verlassen, und bietet so ein feingranulares Credit Assignment.
Effizienz-Gruppe ( $A_{eff}$ ): Vergleicht eingehende Pfade, die denselben zusammengeführten Zustand erreichen. Sie belohnt kürzere Pfade (weniger Token/Schritte), die einen nützlichen semantischen Zustand erreichen, und ermutigt die Policy dazu, effizientere Reasoning-Trajektorien zu finden.

2.4 Policy-Optimierung

Die Policy wird unter Verwendung eines PPO-ähnlichen Objekts optimiert, das den Dual-Group-Vorteil ( $A_{dual} = A_{cor} + \lambda_{eff} A_{eff}$ ) kombiniert. Die Zielfunktion maximiert den erwarteten Ertrag unter Einhaltung einer KL-Divergenz-Beschränkung relativ zu einer Referenz-Policy.

3. Kernbeiträge

Graphbasiertes Rollout-Framework: GraphPO ist das erste RL-Framework, das Reasoning-Rollouts als DAG darstellt und explizit äquivalente Reasoning-Zustände aggregiert, um Suffix-Sharing und Budget-Reallokation zu ermöglichen.
Dual-Group Advantage Estimation: Das Paper schlägt eine Methode vor, die gleichzeitig für Reasoning-Korrektheit (durch Vergleich ausgehender Schritte) und Reasoning-Effizienz (durch Vergleich eingehender Pfade) optimiert und so die Varianz der Vorteilsschätzung reduziert.
Prozess-Supervision ohne Annotationen: Die Methode leitet dichte Schritt-Level-Supervision aus spärlichen Ergebnisbelohnungen ab, indem sie die Graphstruktur und Äquivalenzklassen nutzt, wodurch die Notwendigkeit kostspieliger Process Reward Model (PRM)-Annotationen entfällt.

4. Experimentelle Ergebnisse

Experimente wurden mit drei LLMs (Qwen2.5-7B-Math, Qwen3-8B-Base, Deepseek-R1-Distill-Qwen-7B) über mathematische Reasoning-Benchmarks (AIME24/25, MATH500, GPQA, LiveCodeBench) und agentische Suchaufgaben durchgeführt.

Leistung: GraphPO übertraf konsistent kettenbasierte (GRPO, DAPO) und baumbasierte Baselines (TreeRL, SPO, PROS, TreePO) über alle Modelle und Datensätze hinweg unter identischen Token- und Antwort-Budgets. Beispielsweise erreichte GraphPO beim Qwen2.5-7B-Math Modell eine durchschnittliche Genauigkeit von 40,9 % und übertraf damit die beste baumbasierte Baseline (PROS mit 37,7 %).
Explorations-Effizienz: GraphPO demonstrierte eine höhere Explorations-Effizienz, was bedeutet, dass ein größerer Anteil der Rechenleistung in nützlichen Reasoning-Fortschritt statt in redundante Expansionen investiert wurde. Es hielt während des Trainings eine höhere Entropie im Vergleich zu baumbasierten Methoden, die dazu neigen, schneller in spezifische Reasoning-Muster zu kollabieren.
Antwortlänge: GraphPO produzierte kürzere Antworten als baumbasierte Methoden, indem es äquivalente Zustände zusammenführte und kürzere Pfade belohnte, wodurch die Inferenz-Effizienz verbessert wurde.
Agentische Aufgaben: Die Methode zeigte eine überlegene Leistung in tiefen Such- und agentischen Aufgaben (General AI Assistant, WebWalker, BrowseComp, XBench), was ihre Anwendbarkeit auf sequentielle Entscheidungsprozesse validiert.
Vergleich mit PRMs: GraphPO übertraf PRM-basierte Methoden (ReasonFlux-PRM), ohne zusätzliche annotierte Prozessdaten zu verwenden.

5. Bedeutung und Behauptungen

Das Paper behauptet, dass GraphPO einen praktischen Mechanismus bietet, um selbst-emergente Prozess-Supervision allein aus Ergebnisbelohnungen zu gewinnen. Durch die Modellierung von Rollouts als Graph adressiert es die strukturellen Limitationen von Bäumen, die keine äquivalenten Zustände darstellen können, die durch unterschiedliche Pfade erreicht werden.

Die Autoren behaupten, dass GraphPO:

Varianz reduziert: Das Zusammenführen äquivalenter Zustände und das Pooling nachgeschalteter Evidenz senkt die Varianz der Vorteilsschätzung.
Effizienz steigert: Es reallokiert Rechenbudgets weg von redundanter Expansion hin zu diverser Exploration und belohnt kürzere Reasoning-Pfade.
Auslastung verbessert: Es stabilisiert Policy-Updates, indem es frühzeitig gestoppten Zweigen ermöglicht, die Anerkennung von äquivalenten erfolgreichen Partnern zu erhalten, was die Ausnutzung des Rollout-Budgets verbessert.

Die Arbeit legt nahe, dass graphstrukturierte Rollouts eine robuste Alternative zu baumbasierten Methoden bieten, um die Reasoning-Fähigkeiten großer Sprachmodelle unter Bedingungen verifizierbarer Belohnungen zu skalieren.