💻 computer science

Reinforced Graph of Thoughts: RL-Driven Adaptive Prompting for LLMs

Dieser Artikel stellt den Reinforced Graph of Thoughts (RGoT) vor, ein automatisiertes Framework, das Reinforcement Learning nutzt, um den Graphen von Operationen im Graph-of-Thoughts-Prompting dynamisch anzupassen und damit die Starrheit manuell definierter Strukturen zu überwinden, um komplexere Problemlösungsaufgaben besser zu bewältigen.

Ursprüngliche Autoren: Manuel Noah Riesen, Peter Alfred von Niederhäusern

Veröffentlicht 2026-05-22

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Manuel Noah Riesen, Peter Alfred von Niederhäusern

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 haben einen sehr klugen, aber manchmal zerstreuten Assistenten (ein Large Language Model, oder LLM), der hervorragend Geschichten schreibt, aber bei komplexer Mathematik oder der Organisation unübersichtlicher Daten Schwierigkeiten hat. Wenn Sie ihn einfach bitten, dies zu „lösen", könnte er verwirrt sein oder Fehler machen, insbesondere wenn das Problem riesig ist.

Um ihm zu helfen, geben Forscher ihm normalerweise ein „Rezept" oder einen schrittweisen Plan.

Chain of Thought (Gedankenkette): Wie eine gerade Linie von Anweisungen: „Machen Sie A, dann B, dann C."
Tree of Thoughts (Gedankenbaum): Wie ein Stammbaum, bei dem der Assistent verschiedene Äste versucht, sieht, welcher gut aussieht, und zurückgeht, wenn er auf eine Sackgasse stößt.
Graph of Thoughts (GoT, Gedankengraph): Die fortschrittlichste Version. Stellen Sie sich ein U-Bahn-Netz vor. Der Assistent kann ein Problem in verschiedene Linien aufteilen, sie separat lösen und die Ergebnisse dann wieder zusammenführen. Das ist großartig für große Probleme, aber es ist schwer zu verwenden. Sie, der Mensch, müssen den gesamten U-Bahn-Plan selbst zeichnen, bevor der Assistent mit der Arbeit beginnt. Wenn Sie den falschen Plan zeichnen, scheitert der Assistent.

Das Problem: Die „statische Karte"

Der ursprüngliche „Graph of Thoughts" ist wie eine starre, im Voraus gezeichnete U-Bahn-Karte. Sie funktioniert perfekt, wenn das Problem genau dem entspricht, was Sie erwartet haben. Aber wenn das Problem größer oder komplizierter wird (wie eine Liste von Zahlen, die doppelt so lang ist wie gedacht), bricht Ihre feste Karte zusammen. Der Assistent verirrt sich, weil die Karte die neue Größe nicht berücksichtigt hat.

Die Lösung: Reinforced Graph of Thoughts (RGoT)

Die Autoren dieses Papiers, Manuel Noah Riesen und Peter Alfred von Niederhäusern, haben ein System namens RGoT entwickelt. Anstatt dass Sie die Karte zeichnen, haben sie dem Assistenten ein GPS gegeben, das während der Fahrt lernt.

So funktioniert es, mit einer einfachen Analogie:

Das „Summierungs"-Spiel
Stellen Sie sich vor, die Aufgabe besteht darin, eine sehr lange Liste von Zahlen aufzusummieren.

Der alte Weg: Sie sagen dem Assistenten: „Addieren Sie diese Zahlen." Wenn die Liste 5 Zahlen hat, erledigt er es. Wenn sie 50 hat, gerät er in Verwirrung und gibt eine falsche Antwort.
Der RGoT-Weg: Das System verfügt über einen Werkzeugkasten mit grundlegenden Aktionen:
- Teilen: Schneiden Sie die große Liste in zwei kleinere Listen.
- Summieren: Addieren Sie eine kleine Liste auf.
- Zusammenführen: Kombinieren Sie zwei kleine Ergebnisse zu einem großen Ergebnis.

Anstatt dass Sie entscheiden, wann geteilt oder zusammengeführt wird, verwendet das System einen Reinforcement-Learning-(RL)-Agenten. Stellen Sie sich diesen Agenten als Videospiel-Charakter vor, der versucht, ein Level zu bestehen.

Das Spiel: Das „Level" ist die Liste der Zahlen.
Die Züge: Der Charakter kann wählen zwischen „Teilen", „Summieren", „Zusammenführen" oder „Stoppen".
Die Belohnung: Wenn die endgültige Antwort korrekt ist, erhält der Charakter Punkte. Wenn er scheitert, verliert er Punkte.

Die Magie des Lernens
Zunächst ist der Agent ahnungslos. Er versucht vielleicht, eine Liste von 100 Zahlen auf einmal zu summieren und scheitert. Aber da er ein „Spiel" spielt (unter Verwendung von Reinforcement Learning), lernt er aus seinen Fehlern.

Er erkennt: „Hey, wenn die Liste riesig ist, bekomme ich eine Strafe, wenn ich versuche, sie auf einmal zu summieren. Aber wenn ich sie zuerst teile, dann die kleinen Teile summieren und schließlich zusammenführe, erhalte ich eine riesige Belohnung!"
Im Laufe der Zeit lernt der Agent, seine eigene „U-Bahn-Karte" (den Operationsgraphen) im laufenden Betrieb zu erstellen, perfekt angepasst an die Größe des Problems.

Was sie tatsächlich getan haben

Die Forscher testeten dies an mehreren Aufgaben:

Listen summieren: Zahlen addieren.
Listen sortieren: Zahlen in die richtige Reihenfolge bringen.
Schlüsselwörter zählen: Herausfinden, wie oft ein Wort in einem Text vorkommt.
Dokumente zusammenführen: Mehrere Texte zu einem zusammenfügen, ohne Informationen zu wiederholen.

Sie verwendeten nicht einfach die echten KI-Modelle zum Training (was zu teuer und langsam wäre). Stattdessen schufen sie eine Simulation. Sie ermittelten, wie wahrscheinlich es für die KI war, bei einer Liste mit 10, 20, 50 usw. Elementen einen Fehler zu machen, und programmierten dies in das Spiel ein. Der Agent lernte in dieser Simulation, und dann testeten sie ihn am echten KI-Modell.

Die Ergebnisse

Das Papier behauptet Folgendes:

Anpassungsfähigkeit: Der Agent lernte, seine Strategie automatisch basierend auf der Schwierigkeit des Problems anzupassen. Wenn die Liste kurz war, führte er eine einfache Summierung durch. Wenn die Liste riesig war, entschied er automatisch, sie zuerst zu teilen.
Besser als das Basisverfahren: Der Agent löste komplexe Probleme viel zuverlässiger, als man die KI einfach bat, es „auf einen Schlag" zu tun (die „Input-Output"-Methode).
Generalisierung: Selbst wenn sie dem Agenten eine Listenlänge gaben, die er während des Trainings niemals gesehen hatte (wie eine Liste mit 60 Elementen, obwohl er nur Listen bis 30 geübt hatte), fand er dennoch eine gute Strategie.

Das Fazit

Das Papier stellt eine Methode vor, um die Problemlösung durch fortschrittliche KI automatisch zu machen. Anstatt dass ein menschlicher Experte genau wissen muss, wie man eine komplexe Aufgabe strukturiert, verwendet das System einen „lernenden Agenten", um den besten schrittweisen Plan (den Graphen) für jede gegebene Problemgröße zu ermitteln. Es verwandelt einen starren, manuellen Prozess in einen flexiblen, sich selbst anpassenden.

Hinweis: Das Papier konzentriert sich ausschließlich auf diese spezifischen Aufgaben (Mathematik, Sortieren, Zählen, Zusammenführen) und behauptet nicht, dass diese Methode für medizinische Diagnosen, Rechtsberatung oder andere reale Anwendungen außerhalb dieser definierten logischen Probleme funktioniert.

Technische Zusammenfassung: Verstärkter Graph of Thoughts (RGoT)

Problemstellung

Large Language Models (LLMs) haben durch Prompting-Paradigmen wie Chain of Thought (CoT), Tree of Thoughts (ToT) und Graph of Thoughts (GoT) signifikante Fähigkeiten im gezielten Problemlösen unter Beweis gestellt. Während GoT einen generalisierten Rahmen bietet, in dem Gedanken als beliebige Graphen strukturiert sind, um Aggregation und komplexes Schlussfolgern zu ermöglichen, stützt sich die bestehende Implementierung auf einen statischen, manuell definierten Graphen von Operationen.

Diese manuelle Definition bringt zwei primäre Einschränkungen mit sich:

Zugänglichkeit: Der Aufbau eines GoT-Graphen erfordert tiefgehende Kenntnisse der Problemlösung und der spezifischen Reihenfolge von Operationen, was eine hohe Eintrittsbarriere für Nutzer schafft.
Anpassungsfähigkeit: Statische Graphen sind starr. Sie können sich nicht an die variierende Komplexität von Eingabeinstanzen oder die nicht-deterministische, entropische Natur von LLM-Ausgaben anpassen. Folglich kann ein Graph, der für ein bestimmtes Komplexitätsniveau entworfen wurde, versagen, wenn er auf Eingaben mit anderen Eigenschaften angewendet wird.

Während frühere Arbeiten (Ha et al., 2024) versucht haben, GoT zu automatisieren, verlassen sie sich dabei auf die logischen Fähigkeiten des zugrunde liegenden LLM, um den Graphen zu konstruieren. Diese Arbeit adressiert die Notwendigkeit eines Ansatzes, der nicht von den Planungsfähigkeiten des LLM abhängt, um die Denktopologie selbst zu generieren.

Methodik

Die Autoren schlagen Reinforced Graph of Thoughts (RGoT) vor, einen automatisierten Ansatz, der Reinforcement Learning (RL) nutzt, um adaptiv einen Graphen von Operationen aus einem vom Menschen definierten Satz verfügbarer Operationen zu generieren.

Kernkomponenten des Rahmens

Das System entkoppelt den Graphen von Operationen (GoO) vom Graphen von Gedanken (GoT):

Graphen von Operationen (GoO): Ein gerichteter azyklischer Graph (DAG), der die Sequenz und Struktur von Operationen definiert. Er ist durch maximale Tiefe ( $d_{max}$ ) und Breite ( $b_{max}$ ) beschränkt. Um Konvergenz sicherzustellen, wird eine Divergenz-Abschnittstiefe ( $d_{\neg div}$ ) erzwungen, nach der der Graph auf einen einzigen Senkpunkt zulaufen muss.
Graphen von Gedanken (GoT): Der tatsächliche Ausführungsverlauf, bei dem LLM-Gedanken generiert werden. Jeder Gedanke verweist auf die Operation, die ihn erzeugt hat.
Operationen: Definiert als entweder Prompt-Operationen (LLM-Aufrufe) oder Ausführungsoperationen (programmierte Funktionen). Eine Score-Operation bewertet die Qualität eines Gedankens und gibt eine numerische Punktzahl zurück.

Formulierung des Reinforcement Learning

Der RGoT-Agent operiert innerhalb einer benutzerdefinierten RL-Umgebung, um die GoO-Schicht für Schicht zu konstruieren.

Zustandsraum ( $S$ ): Eine Zusammensetzung diskreter Räume, einschließlich aktueller Graphentiefe, -breite, Aufgabenkomplexität, lokaler Komplexität, der Sequenz von Operationen im aktuellen Graphen, vorheriger Aktionen und der vorherigen Punktzahl.
Aktionsraum ( $A$ ): Diskrete Aktionen, einschließlich stop (Beendigung des Graphaufbaus), backtrack (Entfernung der Senkenschicht) und append(o) (Hinzufügen einer neuen Schicht mit Operation $o$ ).
Belohnungsfunktion: Durch Reward Shaping gestaltet, um übermäßige Tiefe zu bestrafen, gültige Operationen zu belohnen und eine signifikante positive Belohnung für die erfolgreiche Lösung der Aufgabe (Endzustand) zu gewähren.
Simulation: Um die hohen Kosten des Trainings mit echten LLM-Aufrufen zu mindern, wird das Verhalten des LLM simuliert. Die Erfolgswahrscheinlichkeit einer Operation bei gegebener Komplexität $c$ wird als Bernoulli-Experiment mit der Wahrscheinlichkeit $P(c)$ modelliert, die empirisch geschätzt wird, indem das Ziel-LLM (z. B. gpt-3.5-turbo-0125) pro Komplexitätsniveau 100-mal promptet wird.

Experimenteller Aufbau

Die Autoren bewerteten RGoT an fünf Aufgaben:

Liste summieren: Summieren einer Liste ganzer Zahlen (Hauptbeispiel).
Liste sortieren: Sortieren ganzer Zahlen.
Menge schneiden: Finden von Schnittmengen von Mengen.
Schlüsselwörter zählen: Zählen des Vorkommens von Schlüsselwörtern in Texten.
Dokumente zusammenführen: Zusammenführen von Dokumenten unter Maximierung des Erhalts und Minimierung von Redundanz.

Die Experimente nutzten den Proximal Policy Optimization (PPO)-Algorithmus mit einer 2-Schichten-Netzwerkarchitektur (64 Einheiten). Die Agenten wurden auf einem spezifischen Bereich von Komplexitäten trainiert und anschließend sowohl an in-distribution- als auch an out-of-distribution-Instanzen (höhere Komplexität) evaluiert.

Wichtige Ergebnisse

Adaptiver Aufbau: Die RL-Agenten lernten erfolgreich, Graphen von Operationen zu konstruieren, die sich an die Aufgabenkomplexität anpassen. Mit zunehmender Komplexität erhöhten die Agenten automatisch die Verzweigung (Divergenz) und Tiefe des Graphen, um das Problem zu zerlegen – ein Verhalten, das nicht explizit programmiert, sondern durch das Belohnungssignal gelernt wurde.
Leistung im Vergleich zur Baseline: RGoT-Agenten schnitten deutlich besser ab als die Standard-Input-Output (IO)-Prompting-Baseline. Während IO-Strategien versagten, sobald die Komplexität die direkte Fähigkeit des LLM überstieg, behielten RGoT-Agenten durch die Zerlegung von Aufgaben hohe Erfolgsquoten bei.
Generalisierung: Die Agenten zeigten die Fähigkeit, out-of-distribution-Komplexitäten (Komplexitäten höher als die während des Trainings gesehenen) zu lösen und erreichten eine durchschnittliche Gesamt-Lösungsrate von $0.7512 \pm 0.1089$ .
Varianz: Die Autoren beobachteten eine Varianz in der Agentenleistung über verschiedene Zufallssamen hinweg, insbesondere in out-of-distribution-Bereichen. Dies wird auf das spärliche Belohnungssignal bei hohen Komplexitäten und den on-policy-Charakter von PPO zurückgeführt, was die Fähigkeit des Agenten einschränkt, sich von frühen suboptimalen Trajektorien-Verpflichtungen zu erholen.

Bedeutung und Behauptungen

Die Arbeit behauptet, die erste Arbeit zu sein, die einen automatisierten Ansatz zur Konstruktion eines Graph of Thoughts vorstellt, indem ein Graph von Operationen generiert und durchlaufen wird, ohne sich auf die Fähigkeit des Sprachmodells zu verlassen, die Eigenschaften der Aufgabe zu planen oder zu verstehen.

Wichtige Beiträge umfassen:

Automatisierung von GoT: Die Notwendigkeit manueller Graphdefinition wird beseitigt, wodurch das GoT-Paradigma für Nutzer zugänglicher wird, die lediglich den Satz verfügbarer Operationen definieren müssen.
Anpassungsfähigkeit: Es wird demonstriert, dass ein automatisierter Agent die Denktopologie dynamisch an die Eingabekomplexität anpassen kann und so die Starrheit statischer Graphen überwindet.
Modellagnostizismus: Der Rahmen ist unabhängig vom verwendeten spezifischen LLM. Durch die Simulation der Erfolgswahrscheinlichkeiten des LLM kann das System kosteneffektiv trainiert und auf verschiedene Modelle angewendet werden, einschließlich solcher mit unterschiedlichen Fähigkeitsbereichen.
Komplementarität: Die Autoren stellen fest, dass RGoT (Strukturierung der Denktopologie) komplementär zum Knowledge Graph of Thoughts (KGoT) ist, der extern abgerufenes Wissen strukturiert, was Potenzial für kombinierte zukünftige Anwendungen suggeriert.

Die Autoren bewahren einen bescheidenen Ton und erkennen an, dass der Ansatz zwar unter spezifischen Einschränkungen und für definierte Aufgaben vielversprechend ist, die Varianz in der Leistung und die Abhängigkeit von Simulationen für das Training jedoch Bereiche bleiben, die zu berücksichtigen sind. Sie behaupten keine universelle Überlegenheit gegenüber allen Prompting-Methoden, sondern heben den spezifischen Nutzen adaptiver, automatisierter Graphkonstruktion für komplexe, zerlegbare Aufgaben hervor.