💻 computer science

GraphPlanner: Graph Memory-Augmented Agentic Routing for Multi-Agent LLMs

Der Paper stellt GraphPlanner vor, einen heterogenen graph-basierten Speicher-Router für Multi-Agenten-LLMs, der durch die Formulierung von Workflow-Generierung als Markov-Entscheidungsprozess und den Einsatz von Bestärkendem Lernen sowohl die Genauigkeit als auch die Recheneffizienz bei der Aufgabenplanung und -ausführung signifikant verbessert.

Ursprüngliche Autoren: Tao Feng, Haozhen Zhang, Zijie Lei, Peixuan Han, Jiaxuan You

Veröffentlicht 2026-04-28

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Tao Feng, Haozhen Zhang, Zijie Lei, Peixuan Han, Jiaxuan You

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 ein riesiges Team von Spezialisten, die alle unterschiedliche Fähigkeiten haben: Ein paar sind schnelle Rechner, andere sind brillante Programmierer, wieder andere sind Meister im Zusammenfassen von Texten. Aber sie sind auch unterschiedlich teuer und manchmal machen sie Fehler.

Das Problem: Wenn Sie eine komplexe Frage stellen (z. B. „Löse dieses schwierige Mathe-Problem und schreibe dazu einen Code"), wissen Sie nicht sofort, welcher Spezialist genau das Richtige tut.

Die Forscher von der University of Illinois haben eine Lösung namens GraphPlanner entwickelt. Hier ist eine einfache Erklärung, wie es funktioniert, ohne technische Fachbegriffe:

1. Der alte Weg: Der „Einmal-Wurf" vs. der „Schleifen-Weg"

Der alte Weg (Single-Round): Stellen Sie sich einen Kellner vor, der Ihre Bestellung hört und sofort entscheidet: „Das ist eine Mathe-Frage, also bringe ich sie zum Mathematiker." Er macht das nur einmal. Wenn der Mathematiker scheitert, ist das Essen verbrannt.
Der etwas bessere Weg (Multi-Round): Ein Kellner, der sagt: „Ich frage erst den Mathematiker, dann den Physiker, dann nochmal den Mathematiker." Das ist besser, aber der Kellner plant nicht wirklich wie die Zusammenarbeit aussehen soll. Er ruft einfach nacheinander Leute an, was oft zu Verwirrung oder doppelten Fragen führt.

2. Der neue Weg: GraphPlanner als „Regisseur mit Gedächtnis"

GraphPlanner ist wie ein erfahrener Filmregisseur, der für jede neue Frage ein ganz neues Skript schreibt. Er tut drei Dinge gleichzeitig:

Wer macht was? Er entscheidet, ob gerade ein „Planer" (der die Aufgabe zerlegt), ein „Ausführer" (der die Arbeit macht) oder ein „Zusammenfasser" (der das Ergebnis poliert) an der Reihe ist.
Wer ist der beste Spezialist? Er wählt aus, welches KI-Modell (z. B. ein kleines, schnelles oder ein großes, teures) für diese spezifische Rolle am besten passt.
Er nutzt ein Gedächtnis: Das ist der wichtigste Teil. Der Regisseur hat ein riesiges Notizbuch (ein Graph), in dem steht: „Als wir letztes Mal eine ähnliche Frage hatten, hat der kleine Spezialist bei Schritt 2 versagt, aber der große Spezialist hat es perfekt gelöst."

3. Wie das „Gedächtnis" funktioniert (Der Graph)

Stellen Sie sich das Gedächtnis nicht als eine lange Liste vor, sondern als ein lebendiges Netz aus Knoten und Verbindungen:

Es verbindet Fragen, Antworten und die verschiedenen KI-Modelle miteinander.
Wenn GraphPlanner eine neue Aufgabe bekommt, schaut er in dieses Netz. Er sieht nicht nur die aktuelle Frage, sondern auch, wie sich ähnliche Fragen in der Vergangenheit entwickelt haben.
Er lernt daraus: „Aha, bei diesem Typ von Frage müssen wir zuerst planen, dann zwei Leute gleichzeitig arbeiten lassen und am Ende zusammenfassen."

4. Das Training: Lernen durch Versuch und Irrtum

Der Regisseur (GraphPlanner) wird nicht einfach mit Regeln belehrt. Er spielt ein Videospiele-ähnliches Training:

Er bekommt eine Aufgabe.
Er trifft Entscheidungen (Welcher Spezialist? Welche Rolle?).
Am Ende bekommt er Punkte: Hohe Punkte für eine richtige Antwort, aber Abzug für zu viele teure Spezialisten oder zu lange Wartezeiten.
Durch tausende von Spielen lernt er, den perfekten Weg zu finden, der sowohl billig als auch genau ist.

Was haben die Forscher herausgefunden?

Die Studie zeigt, dass dieser Ansatz zwei große Vorteile hat:

Er ist viel genauer: Bei schwierigen Aufgaben (wie Mathe oder Programmieren) finden sie die richtige Lösung deutlich öfter als die alten Methoden.
Er ist viel billiger: Indem er genau weiß, wann er einen teuren Spezialisten braucht und wann ein günstiger reicht, spart er enorme Mengen an Rechenleistung (Grafikkarten-Kosten). Die Forscher berichten, dass die Kosten von fast 186 GiB auf nur noch 1,04 GiB pro Aufgabe gesunken sind – eine riesige Ersparnis!
Er ist flexibel: Selbst wenn er eine völlig neue Art von Aufgabe sieht oder einen KI-Spezialisten benutzt, den er noch nie gesehen hat, kann er trotzdem gut arbeiten, weil er die Struktur des Problems versteht, nicht nur das Auswendiggelernte.

Zusammenfassend: GraphPlanner ist wie ein super-intelligenter Teamleiter, der nicht nur weiß, wer was kann, sondern sich auch an alle vergangenen Projekte erinnert, um für jede neue Aufgabe das perfekte, kostengünstige Team zusammenzustellen und den besten Arbeitsablauf zu planen.

1. Problemstellung

Das Routing von Anfragen an Large Language Models (LLMs) hat sich als effektive Methode erwiesen, um die Stärken verschiedener Modelle zu kombinieren und dabei Effizienz und Leistung auszubalancieren. Bisherige Ansätze lassen sich jedoch in zwei Kategorien einteilen, die für komplexe, reale Anwendungen unzureichend sind:

Single-Round Router: Treffen eine einmalige Zuweisung basierend auf Query-Embeddings. Ihnen fehlt die Fähigkeit zur mehrstufigen Reasoning, zur Zerlegung von Aufgaben oder zur Koordination zwischen verschiedenen Modellen.
Multi-Round Router: Treffen sequenzielle Entscheidungen unter Berücksichtigung des Kontexts, behandeln aber jeden Aufruf oft als isoliert, ohne explizite Modellierung der Zusammenarbeit (Kollaboration) zwischen Agenten. Dies führt zu redundanten Aufrufen und Kontextkonflikten.

Die zentrale Herausforderung besteht darin, das Routing auf agente LLM-Umgebungen zu erweitern. In solchen Szenarien muss der Router nicht nur entscheiden, welches LLM-Backbone verwendet wird, sondern auch, welche Agenten-Rolle (z. B. Planer, Ausführer, Zusammenfasser) in jedem Schritt aktiviert werden soll. Dies erfordert die Bewältigung komplexer Abhängigkeiten, verzögerter Belohnungen (da frühe Entscheidungen langfristige Auswirkungen haben) und die effektive Nutzung historischer Interaktionsdaten.

2. Methodik: GraphPlanner

GraphPlanner ist ein heterogenes, graph-basiertes Routing-Framework, das die Generierung von Agenten-Workflows als Markov-Entscheidungsprozess (MDP) formuliert.

A. Formulierung als MDP

Zustand ( $S_t$ ): Der aktuelle Zustand ist die zu lösende Query ( $q_t$ ), wobei der Kontext implizit durch die sich entwickelnde Workflow-Struktur erfasst wird.
Aktion ( $A_t$ ): In jedem Schritt wählt der Router ein Paar $(\alpha_t, m_t)$ $(α_{t}, m_{t})$ , bestehend aus einer Agenten-Rolle ( $\alpha_t \in \{\text{Planner, Executor, Summarizer}\}$ $α_{t} \in {Planner, Executor, Summarizer}$ ) und einem LLM-Backbone ( $m_t$ $m_{t}$ ).
- Planner: Zerlegt komplexe Queries in Sub-Queries.
- Executor: Generiert Antworten auf Sub-Queries.
- Summarizer: Fasst Ergebnisse zusammen.
- Es gibt dynamische Masken, um semantisch ungültige Aktionen zu verhindern (z. B. kein Summarizer am Anfang).
Übergang ( $T$ ): Basierend auf der Aktion wird die Workflow-Speicherstruktur aktualisiert (neue Sub-Queries, Antworten oder Zusammenfassungen).
Belohnung ( $R_t$ ): Ein Kompromiss zwischen der Aufgabenleistung (z. B. Genauigkeit) und den Rechenkosten (Token-Nutzung, GPU-Kosten).

B. Heterogener Graph (GARNet)

Das Kernstück von GraphPlanner ist GARNet (Graph-Augmented Routing Network), ein heterogener Graph, der zwei Arten von Speicher integriert:

Workflow-Speicher-Graph ( $G_{workflow}$ ): Repräsentiert den aktuellen Interaktionsverlauf der aktuellen Query (Queries, Antworten, Rollen).
Historischer Speicher-Graph ( $G_{history}$ ): Enthält Informationen aus vergangenen Interaktionen und erfolgreichen Workflows.

Architektur-Details:

Knoten: Es gibt Knoten für Queries, Antworten und eine spezielle Klasse von „Rollen-Hub-Knoten" (LLM-Rolle-Paare).
Shared Role Hubs: Ein entscheidendes Designmerkmal ist die Verwendung gemeinsamer Rollen-Hub-Knoten, die sowohl im aktuellen Workflow als auch im historischen Speicher verwendet werden. Dies ermöglicht einen effizienten Informationsaustausch und verhindert redundante Knotenerstellung.
Nachrichtenweitergabe: Ein heterogener Graph-Neural-Netzwerk (GNN) aggregiert Nachrichten von Nachbarn, um reichhaltige Zustandsrepräsentationen zu erzeugen, die sowohl lokale als auch historische Muster kodieren.
Dual-Graph-Encoding: Zuerst wird der historische Graph kodiert, um die Embeddings der Rollen-Hubs zu aktualisieren. Diese werden dann in den Workflow-Graphen injiziert, um kontextsensitive Entscheidungen zu treffen.

C. Training

Das gesamte System wird mit Proximal Policy Optimization (PPO), einem Reinforcement-Learning-Algorithmus, trainiert. Dies ermöglicht es dem Router, langfristige Belohnungen zu maximieren und den Trade-off zwischen Genauigkeit und Kosten zu optimieren, anstatt nur auf sofortige Feedback-Signale zu reagieren.

3. Wichtige Beiträge

Agentic Routing Framework: Erstmalige Formulierung des LLM-Routings als mehrstufiger Koordinationsprozess, der sowohl die Auswahl des Modells als auch die Rolle des Agenten dynamisch bestimmt.
Heterogener Graph-Speicher (GARNet): Einführung eines Mechanismus, der historische Interaktionsmuster und aktuelle Workflow-Zustände in einem einzigen Graphen vereint, um reichhaltigere Zustandsrepräsentationen für das Routing zu schaffen.
Induktives und Transduktives Inferenz: Das System unterstützt zwei Modi:
- Induktiv: Leichtgewichtig, keine Nutzung historischer Daten zur Laufzeit.
- Transduktiv: Nutzt gespeicherte historische Interaktionen für bessere Leistung (zu höheren Kosten).
Reinforcement Learning Optimierung: Gemeinsame Optimierung von Aufgabenleistung und Rechenkosten durch PPO.

4. Ergebnisse

Das Paper evaluiert GraphPlanner über 14 verschiedene Aufgaben in 6 Domänen (Mathematik, Code, Common Sense, Weltwissen, etc.) und vergleicht es mit starken Single-Round- und Multi-Round-Baselines.

Leistungsgewinn:
- In Phase 1 (Optimierung innerhalb definierter Workflows) verbesserte GraphPlanner die Genauigkeit um +3,8 % gegenüber den besten Baselines.
- In Phase 2 (Generierung optimaler Workflows) stieg die Verbesserung auf +9,3 %.
- Die GPU-Kosten wurden drastisch reduziert: von 186,26 GiB (bei Baselines wie Router-R1) auf nur 1,04 GiB bei GraphPlanner.
Generalisierung:
- Das Modell zeigte starke Zero-Shot-Fähigkeiten auf nicht gesehenen Aufgaben (Durchschnittsgenauigkeit von 78 %, was 20–40 % höher ist als bei vorherigen Routern).
- Es generalisierte robust auf ungesehene LLM-Backbones ohne zusätzliches Fine-Tuning.
Effizienz: GraphPlanner bildet die Pareto-Frontier zwischen Genauigkeit und Kosten, bietet also bei gleicher Genauigkeit niedrigere Kosten oder bei gleichen Kosten höhere Genauigkeit als alle Vergleichssysteme.
Ablationsstudien: Die Entfernung des historischen Speichers führte zu einem signifikanten Leistungsabfall, was die Notwendigkeit der Graph-basierten Gedächtnisnutzung unterstreicht.

5. Bedeutung und Ausblick

GraphPlanner stellt einen Paradigmenwechsel im Bereich des LLM-Routings dar. Statt statischer oder rein sequenzieller Zuweisungen ermöglicht es dynamische, kollaborative Workflows, die die spezifischen Stärken heterogener LLMs nutzen. Durch die Integration von Graph-Memory und Reinforcement Learning adressiert es die Komplexität realer Agentensysteme, in denen Aufgabenzerlegung und Rollenverteilung entscheidend sind.

Die Arbeit zeigt, dass die Kombination aus strukturiertem Gedächtnis (Graph) und adaptiver Entscheidungsfindung (RL) nicht nur die Genauigkeit bei komplexen Aufgaben (wie Mathematik und Code) signifikant steigert, sondern auch die Rechenkosten massiv senkt. Dies ebnet den Weg für skalierbare, kooperative Multi-Agenten-Systeme, die effizient und kostengünstig komplexe Probleme lösen können. Zukünftige Arbeiten planen die Erweiterung um weitere Agenten-Rollen (z. B. „Thinker", „Verifier"), um die Flexibilität weiter zu erhöhen.