🤖 AI

GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning

Das Paper stellt GATS vor, ein Planungsframework, das kostspielige LLM-Inferenz durch ein geschichtetes Weltmodell und eine UCB1-basierte Baumsuche ersetzt, um eine Erfolgsquote von 100 % sowie deterministische Planung ohne weitere Aufrufe über diverse komplexe Aufgaben hinweg zu erreichen und dabei bestehende Methoden wie LATS und ReAct signifikant zu übertreffen.

Ursprüngliche Autoren: Maureese Williams, Dymitr Nowicki

Veröffentlicht 2026-07-13

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Maureese Williams, Dymitr Nowicki

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 versuchen, ein riesiges, kniffliges Labyrinth zu lösen. Sie haben einen super-intelligenten Freund (ein Large Language Model, oder LLM), der mit Ihnen sprechen und Ihnen Vorschläge machen kann, in welche Richtung Sie abbiegen sollen. Aber hier ist der Haken: Jedes Mal, wenn Sie Ihren Freund um Rat fragen, muss er ein langes Schläfchen halten, um nachzudenken, und manchmal rät er jedes Mal anders, wenn Sie dieselbe Frage stellen. Wenn das Labyrinth Sackgassen hat oder eine lange Abfolge von Wendungen erfordert, wird es teuer und verwirrend, Ihren Freund bei jedem einzelnen Schritt um Hilfe zu bitten.

Dies ist das Problem, das die Forscher Maureese Williams und Dymitr Nowicki mit ihrem neuen System GATS (Graph-Augmented Tree Search) angegangen sind. Sie haben einen Weg gefunden, das Labyrinth so effizient zu navigieren, dass sie ihren super-intelligenten Freund kaum noch aufwecken müssen.

Die alte Art: Der „Frage-bei-jedem-Schritt“-Ansatz

Frühere Methoden, wie ReAct und LATS, waren ein wenig wie ein Wanderer, der an jeder Weggabelung kurz anhält, um seinen Führer zu fragen: „In welche Richtung soll ich gehen?“

ReAct fragt einfach einmal und geht dann los. Das ist schnell, führt aber oft in Sackgassen. In ihren Tests erreichte diese Methode in den kniffligen Labyrinth-Szenarien nur 64 % Erfolg.
LATS ist klüger; es fragt den Führer, dann fragt es beim nächsten Schritt erneut, und wieder, indem es einen Baum von Möglichkeiten aufbaut. Aber weil es den Führer (das LLM) für jeden einzelnen Zweig dieses Baumes befragt, wird es müde und teuer. In den Tests war LATS zu 92 % erfolgreich, musste den Führer aber etwa 37 Mal pro Aufgabe befragen. Zudem, da der Füher manchmal zufällig rät, kann man bei zwei Durchläufen desselben Labyrinths einen anderen Pfad erhalten.

Die neue Art: GATS (Die „Landkarten-Strategie“)

GATS verändert das Spiel. Anstatt den Führer für jede Abzweigung zu fragen, erstellt GATS seine eigene interne Landkarte unter Verwendung eines geschichteten Weltmodells (Layered World Model). Denken Sie an diese Landkarte als ein System mit drei Wissensebenen:

Ebene 1 (Das exakte Regelwerk): Für Aktionen, die das System bereits perfekt kennt (wie „Wenn ich diesen Knopf drücke, öffnet sich die Tür“), nutzt es eine einfache, sofortige Überprüfung. Kein Nachdenken erforderlich. Es ist wie das Wissen, dass 2+2 immer 4 ergibt.
Ebene 2 (Das Erfahrungsprotokoll): Wenn das System eine Aktion schon einmal erlebt hat, aber keine perfekte Regel dafür hat, prüft es sein Tagebuch vergangener Reisen. „Letztes Mal, als ich dies tat, funktionierte es 9 von 10 Mal.“ Dies wird aus Daten gelernt, nicht geraten.
Ebene 3 (Der Super-Genie-Freund): Nur wenn das System auf etwas völlig Neues und Unbekanntes stößt, weckt es den LLM-Führer auf. Aber hier liegt die Magie: Sobald der Führer antwortet, schreibt GATS die Antwort in die Landkarte. Wenn dieselbe Situation das nächste Mal auftritt, schaut GATS einfach in die Karte. Es fragt den Führer nie wieder für genau diese Sache.

Die Ergebnisse: Geschwindigkeit, Gewissheit und Erfolg

Die Forscher testeten dies an 100 synthetischen Planungsaufgaben, die darauf ausgelegt waren, knifflig zu sein, mit verzweigten Pfaden und Sackgassen.

GATS erreichte eine Erfolgsquote von 100 %.
LATS erreichte 92 %.
ReAct erreichte 64 %.

Aber der eigentliche Clou? GATS machte während der eigentlichen Planung dieser Aufgaben null Aufrufe an das LLM. Es erledigte das gesamte Denken mithilfe seiner eigenen Karte und Regeln. Da es sich nicht auf das zufällige Raten des LLMs verließ, erzeugte GATS jedes Mal exakt denselben perfekten Plan. Es gab null Varianz.

Sie führten auch einen massiven „Stresstest“ mit 120 Aufgaben in 12 schwierigen Kategorien durch, wie z. B. Coding-Workflows, Flugbuchungen und das Navigieren in komplexen Labyrinthen.

GATS erreichte immer noch 100 % Erfolg.
LATS sank auf 88,9 %.
ReAct brach auf 23,9 % ein.

Warum es funktioniert (Das Geheimrezept)

Das Paper legt nahe, dass GATS gewinnt, weil es eine systematische Suche (genannt UCB1) verwendet anstatt des zufälligen Ratens. Stellen Sie sich einen Detektiv vor, der jeden Hinweis methodisch prüft, anstatt einfach nur einer Intuition zu folgen.

Systematisch vs. Zufällig: LATS verlässt sich darauf, dass das LLM errät, welcher Pfad gut aussieht. Wenn die „Ahnung“ des LLM falsch ist, scheitert der gesamte Plan. GATS prüft alle Optionen systematisch und stellt so sicher, dass es nicht den richtigen Pfad übersieht, nur weil der Führer einen schlechten Tag hatte.
Deterministisch vs. Stochastisch: Da GATS für die meisten Schritte seine eigene Karte verwendet, ist das Ergebnis immer gleich. LATS kann Ihnen, da es sich auf das LLM verlässt, eine andere Antwort geben, wenn Sie dieselbe Aufgabe zweimal ausführen.

Was dies bedeutet (Und was es nicht bedeutet)

Die Autoren sind sich der Grenzen ihres Erfolgs sehr bewusst. Diese Ergebnisse basieren auf Simulationen und synthetischen Aufgaben, bei denen die Regeln des Spiels (die „Aktionsspezifikationen“) im Voraus bekannt waren. In diesen kontrollierten Umgebungen ist GATS ein Champion.

Das Paper schließt jedoch explizit die Idee aus, dass GATS momentan ein Allheilmittel für alles ist. Wenn man GATS in eine völlig wilde, offene Welt wirft, in der es keine Regeln und keine vergangenen Protokolle zum Lernen hat, müsste es stärker auf das LLM zurückgreifen (Ebene 3), was es langsamer und weniger effizient machen würde. Die Autoren schlagen vor, dass wir für GATS, um in der realen Welt glänzen zu können, zuerst bessere Karten (Weltmodelle) bauen müssen, beispielsweise indem wir aus Protokollen lernen, wie Menschen tatsächlich Werkzeuge benutzen.

Kurz gesagt zeigt das Paper, dass wir für Planungsaufgaben, bei denen wir die Regeln definieren können, nicht bei jedem einzelnen Schritt einen super-intelligenten KI-Freund um Hilfe bitten müssen. Wir können eine intelligente, sich selbst aktualisierende Karte erstellen, die es uns ermöglicht, komplexe Probleme mit 100 % Erfolg, null Kosten und null Verwirrung zu lösen.

Technisches Resümee: GATS (Graph-Augmented Tree Search mit geschichteten Weltmodellen)

Problemstellung

Large Language Model (LLM) Agenten haben ihr Potenzial bei der mehrstufigen Planung und Werkzeugnutzung unter Beweis gestellt, doch aktuelle Ansätze wie ReAct und LATS (Language Agent Tree Search) stehen vor zwei kritischen Einschränkungen:

Rechenaufwand: Bestehende Methoden verlassen sich bei jedem Planungsschritt oder Suchknoten auf teure LLM-Inferenz, was zu hoher Latenz und Ressourcenverbrauch führt.
Stochastizität: Das LLM-Sampling führt zu Varianz, was nicht reproduzierbare Pläne und inkonsistente Leistungen über verschiedene Durchläufe hinweg zur Folge hat.

Die zentrale Herausforderung besteht darin, ein Planungsframework zu entwickeln, das die Denkfähigkeiten von LLMs beibehält, aber gleichzeitig die LLM-Aufrufe für die Zustandsprädiktion eliminiert, um so eine deterministische, effiziente und skalierbare Agentenplanung zu erreichen.

Methodik: GATS-Framework

Die Autoren schlagen GATS (Graph-Augmented Tree Search) vor, eine Planungsarchitektur, die das Weltmodell vom LLM entkoppelt. GATS kombiniert systematische UCB1-basierte Baumsuche mit einem geschichteten Weltmodell (Layered World Model) und einem persistenten Zustandsübergangsgraphen.

1. Geschachtetes Weltmodell ( $W$ )

Das Weltmodell sagt den nächsten Zustand ( $s'$ ) und die Konfidenz ( $p$ ) gegeben einen aktuellen Zustand ( $s$ ) und eine Aktion ( $a$ ) voraus. Es fragt drei Schichten in der Reihenfolge steigender Allgemeingültigkeit und Rechenkosten ab:

L1 (Symbolisch): Exaktes Abgleichen von Vorbedingungen und Effekten für Aktionen mit bekannten STRIPS-artigen Spezifikationen. Diese Schicht liefert deterministische Vorhersagen ( $p=1.0$ ) bei minimalem Rechenaufwand (symbolischer Lookup).
L2 (Gelernte Statistik): Statistische Vorhersagen, die aus Ausführungsprotokollen abgeleitet werden. Für Aktionen, die während der Ausführung beobachtet wurden, aber keine formalen Spezifikationen besitzen, liefert sie den häufigsten Effekt mit einer Konfidenz von $p = \min(\text{count}(a)/10, 1.0)$ .
L3 (Generativ/LLM): LLM-basierte Vorhersage für genuin neue oder mehrdeutige Aktionen. Entscheidend ist, dass Vorhersagen aus L3 zwischengespeichert (gecached) werden, um wiederholte Inferenzaufrufe für dieselbe Transition zu vermeiden.

Das System priorisiert L1 und L2, um die Abdeckung zu maximieren, und ruft L3 nur bei Bedarf auf. Dies „amortisiert“ die LLM-Kosten, indem es die LLM-Inferenz von einer pro-Schritt-Anforderung in eine einmalige Bootstrapping-Kostenstruktur transformiert.

2. Persistenter Zustandsübergangsgraph

Im Gegensatz zur traditionellen Baumsuche, die Knoten unabhängig expandiert, unterhält GATS einen expliziten Graphen $G = (V, E)$ , wobei Knoten kanonische Zustands-Keys $k(s)$ repräsentieren.

Zustandszusammenführung (State Merging): Wenn verschiedene Aktionssequenzen denselben Zustand erreichen, werden sie in einem einzigen Knoten zusammengeführt. Dies ermöglicht die Wiederverwendung von Transitionsvorhersagen, Besuchszahlen und Wertschätzungen über Pfade hinweg.
Persistenz: Der Graph bleibt über die Planungsschritte hinweg bestehen. Nachdem eine Aktion ausgeführt wurde, setzt die Planung am entsprechenden Graphenknoten fort, anstatt die Suche neu zu starten, wodurch die Wertschätzung und die Suchstatistiken über die gesamte Episode amortisiert werden.
Dead-End-Erkennung: Knoten, die keinen Pfad zum Ziel haben, werden als Sackgassen (Dead Ends) markiert, was es dem Planer ermöglicht, Aktionen, die in diese Regionen führen, niedrige Werte zuzuweisen.

3. UCB1-basierte Suche

GATS verwendet eine UCB1-Selektionsstrategie (Upper Confidence Bound) über die Kanten des Graphen.

Aktionsauswahl: In jedem Zustand wählt der Algorithmus die Aktion $a$ , die $Q(s, a) + c\sqrt{\frac{2 \ln N(s)}{N(s, a)}}$ maximiert. Dies gewährleistet eine systematische Exploration aller anwendbaren Aktionen, bevor ein Pfad mit hohem Wert gewählt wird.
Wertschätzung (Value Estimation): Der Wert eines Zustands wird aus der kürzesten vorhergesagten Distanz zum Ziel ( $d_G$ ) mittels einer BFS-basierten Heuristik abgeleitet: $StateValue(s) = \frac{\alpha}{d_G(s, G) + 1}$ .
Integration der Konfidenz: Der Backup-Wert bezieht die Konfidenz des Weltmodells ein: $v = p \cdot StateValue(s') - \lambda(1-p)$ , wodurch unsichere Vorhersagen sanktioniert werden.

Zentrale Beiträge

Geschichtete Weltmodell-Architektur: Eine neuartige Integration von symbolischen, gelernten und generativen Komponenten, die eine effiziente Zustandsprädiktion ermöglicht und gleichzeitig die LLM-Abhängigkeit minimiert.
Systematische UCB1-Suche mit Graph-Speicher: Ein Planungsalgorithmus, der durch die Nutzung eines persistenten Graphen zur Wiederverwendung von Suchbeweisen und zur Gewährleistung deterministischer Ergebnisse die LLM-gesteuerte Exploration übertrifft.
Umfassende Evaluierung: Extensive Tests auf 100 synthetischen Planungsaufgaben und einem 12-Kategorien-Stresstest (120 Aufgaben), der Coding, Web-Navigation und Langzeit-Horizon-Szenarien abdeckt.
Null LLM-Aufrufe während der Planung: GATS demonstrierte eine Erfolgsquote von 100 % mit null LLM-Aufrufen während der Planungsphase, im starken Kontrast zu Baselines, die Dutzende Aufrufe pro Aufgabe benötigen.

Experimentelle Ergebnisse

Synthetische Planungsaufgaben (100 Aufgaben)

Erfolgsquote: GATS erreichte 100 % Erfolg (bei Budget $b=10$ ) und übertraf damit LATS (92 %) und ReAct (64 %).
Effizienz: GATS benötigte 0 LLM-Aufrufe pro Aufgabe während der Planung, während LATS ca. 37 Aufrufe benötigte.
Determinismus: GATS erzeugte Pläne mit 0 % Varianz über verschiedene Random Seeds hinweg, während LATS und ReAct aufgrund der LLM-Stochastizität eine Varianz von 1–5 % aufwiesen.
Optimalität: GATS erreichte eine Optimalitätsrate von 1,00, was dem Oracle entspricht.

Stresstest (12 Kategorien, 120 Aufgaben)

Der Stresstest beinhaltete anspruchsvolle Szenarien wie Coding-Workflows, Web-Navigation, Deep-Horizon-Aufgaben und irreversible Entscheidungsfindung (Dead-Ends).

Gesamtleistung: GATS hielt eine Erfolgsquote von 100 % über alle Kategorien hinweg.
Vergleichbare Leistung: LATS fiel auf 88,9 % insgesamt zurück, mit signifikanten Schwierigkeiten in den Bereichen Coding (63,3 %), Web-Navigation (63,3 %) und Deep-Horizon (63,3 %). ReAct scheiterte katastrophal mit 23,9 %.
Spezifische Gewinne: GATS zeigte die größten Verbesserungen (+36,7 %) in den Bereichen Coding, Web-Navigation und Deep-Horizon im Vergleich zu LATS.

Ablationsstudien

Suchbudget: Die Leistung sättigte bei einem Budget von $b=10$ ; eine weitere Erhöhung lieferte abnehmende Grenzerträge.
Weltmodell-Schichten: Das Entfernen von L1 oder L3 einzeln hatte keinen Einfluss auf die Erfolgsraten bei synthetischen Aufgaben, bei denen L2 eine ausreichende Abdeckung bot, was die graduelle Leistungsabnahme des Systems validiert. In Open-Domain-Projektionen wird erwartet, dass L3 (LLM) etwa 10 % der neuartigen Aktionen übernimmt.

Bedeutung und Ansprüche

Das Paper argumentiert, dass systematische Suche mit gelernten Weltmodellen die LLM-gesteuerte Exploration erheblich übertreffen kann. Die primäre Bedeutung von GATS liegt in der Fähigkeit:

Inferenzkosten für LLMs zu eliminieren: Durch das Caching von Vorhersagen und die Nutzung von symbolischen/gelernten Schichten eliminiert GATS den Rechenengpass wiederholter LLM-Aufrufe.
Reproduzierbarkeit zu gewährleisten: Die deterministische Natur des geschichteten Weltmodells und der UCB1-Suche eliminiert die inhärente stochastische Varianz des LLM-Samplings.
Komplexe Planung zu bewältigen: Das Framework navigiert erfolgreich durch verzweigte Pfade, Sackgassen und langfristige Abhängigkeiten, bei denen rein LLM-basierte Methoden (ReAct) und LLM-lastige Baumsuche (LATS) versagen oder unterperformen.

Die Autoren positionieren GATS als optimierte Lösung für Domänen, in denen die Aktionssemantik formalisierbar ist (z. B. APIs, strukturierte Werkzeugnutzung), und bieten damit einen Weg zu effizienteren und zuverlässigeren autonomen Agenten. Sie räumen ein, dass in offenen Domänen mit unbekannten Aktionsfolgen die Abhängigkeit von der L3-Schicht zunehmen würde, was den Effizienzvorteil gegenüber LATS zwar verringern, aber nicht aufheben würde.