💬 NLP

PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs

PathWise ist ein neuartiges Multi-Agenten-Framework, das das automatisierte heuristische Design für kombinatorische Optimierung verbessert, indem es den Prozess als eine zustandsbewusste sequenzielle Entscheidungsfindungsaufgabe über einem Entailment-Graphen formuliert und dadurch kurzsichtiges Trial-and-Error durch strategische Planung und sich selbst weiterentwickelnde Schlussfolgerung ersetzt, um eine schnellere Konvergenz und bessere Generalisierung zu erreichen.

Ursprüngliche Autoren: Oguzhan Gungordu, Siheng Xiong, Faramarz Fekri

Veröffentlicht 2026-05-26

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Oguzhan Gungordu, Siheng Xiong, Faramarz Fekri

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

Das große Ganze: Einen Roboter lehren, bessere Regeln zu erfinden

Stellen Sie sich vor, Sie haben ein riesiges, chaotisches Puzzle (wie das Problem des Handlungsreisenden, bei dem ein Lieferfahrer den kürzesten Weg finden muss, um 100 Städte zu besuchen). Um dies zu lösen, schreiben Menschen normalerweise „Regeln" (Heuristiken), um dem Computer zu sagen, wie er die nächste Stadt auswählen soll.

Lange Zeit haben Computer versucht, diese Regeln automatisch mit Large Language Models (LLMs) zu schreiben – derselben Art von KI, die Aufsätze oder Code verfasst. Doch frühere Methoden waren ein bisschen wie ein Koch, der versucht, ein neues Rezept zu erfinden, indem er Zutaten zufällig in einen Topf wirft, sie probiert und auf das Beste hofft. Oft wiederholten sie Fehler, vergaßen, was zuvor funktionierte, oder blieben stecken, indem sie immer wieder dieselben schlechten Ideen versuchten.

PathWise ist ein neues System, das diesen Prozess verändert. Anstatt zufällig zu raten, agiert es wie ein intelligenter, selbstreflektierender Architekt, der eine Karte seines eigenen Denkprozesses erstellt, um schneller bessere Regeln zu entwerfen.

Das Kernproblem: Die „Amnesie" früherer KIs

Das Papier argumentiert, dass frühere KI-Methoden zum Entwerfen dieser Regeln zwei Hauptmängel hatten:

Sie vergaßen die Vergangenheit: Sie behandelten jeden neuen Versuch so, als wäre es das erste Mal, und ignorierten Lehren aus früheren Fehlern.
Sie waren blind: Sie verstanden nicht, warum eine Regel funktionierte oder scheiterte; sie schauten nur auf die Endpunktzahl.

Dies führte zu „kurzsichtigen" Ergebnissen, bei denen die KI Zeit damit verschwendete, dieselben schlechten Ideen immer wieder neu zu entdecken.

Die Lösung: PathWise (Der „Weltmodell"-Ansatz)

PathWise löst dies, indem es den Gestaltungsprozess wie ein Videospiele mit einer Speicherdatei behandelt. Es verwendet eine spezielle Struktur namens Entailment Graph (Implikationsgraph).

Stellen Sie sich den Entailment Graphen als einen Stammbaum von Ideen vor:

Die Knoten (Die Personen): Jeder Knoten ist eine spezifische Regel (Heuristik), die die KI erstellt hat.
Die Kanten (Die Beziehungen): Die Linien, die sie verbinden, zeigen, wie eine Regel aus einer anderen entstanden ist. Hat die KI zwei Ideen kombiniert? Hat sie eine angepasst?
Das Gedächtnis: Dieser Graph merkt sich die gesamte Geschichte. Er weiß, dass „Regel B" eine leichte Verbesserung von „Regel A" war und dass „Regel C" scheiterte, weil sie Verkehrsströme ignorierte.

Wie es funktioniert: Das Drei-Agenten-Team

PathWise verwendet nicht nur eine KI; es nutzt ein Team aus drei spezialisierten Agenten, die zusammenarbeiten, ähnlich wie ein Filmproduktionscrew:

1. Der Regisseur (Policy Agent)

Rolle: Dieser Agent betrachtet den „Stammbaum" (den Graphen) und entscheidet den nächsten Schritt.
Aktion: Er wählt aus, welche früheren Regeln als Eltern dienen sollen, und schreibt ein „Skript" (eine Direktive), das dem nächsten Agenten sagt, wie man sie mischt.
Analogie: Stellen Sie sich einen Regisseur vor, der sich ein Storyboard ansieht und sagt: „Nehmen wir das Licht aus Szene 3 und den Kamerawinkel aus Szene 5, aber machen Sie es dunkler."

2. Der Schauspieler (World Model Agent)

Rolle: Dieser Agent nimmt das Skript des Regisseurs und schreibt tatsächlich den Code (die neue Regel).
Aktion: Er generiert das eigentliche Computerprogramm basierend auf den Anweisungen.
Analogie: Dies ist der Schauspieler, der das Skript liest und die Szene aufführt. Er versucht, die Vision des Regisseurs zum Leben zu erwecken.

3. Der Kritiker (Critic Agents)

Rolle: Diese Agenten beobachten die Aufführung und geben Feedback.
Aktion: Sie vergleichen die neue Regel mit alten. Wenn die neue Regel besser ist, sagen sie dem Regisseur: „Gute Arbeit, machen Sie weiter so!" Wenn sie schlechter ist, sagen sie: „Das Licht war zu dunkel; versuchen Sie etwas anderes."
Analogie: Dies sind die Filmkritiker und der Assistent des Regisseurs. Sie sagen nicht nur „gut" oder „schlecht"; sie erklären, warum, damit der Regisseur das nächste Skript verbessern kann.

Das Geheimnis: „Zustandsbewusste" Planung

Die Magie von PathWise besteht darin, dass es nicht nur auf die aktuelle Punktzahl schaut. Es betrachtet die gesamte Reise.

Alter Weg: „Ich habe das versucht, es ist gescheitert. Lassen Sie uns etwas völlig anderes versuchen."
PathWise-Weg: „Ich habe das versucht, es ist gescheitert, weil ich die Entfernung zur nächsten Stadt ignoriert habe. Ich habe auch das versucht, und es hat gut funktioniert. Lassen Sie uns die Entfernungslogik aus dem zweiten Versuch mit der Geschwindigkeitslogik aus dem ersten kombinieren."

Durch die Beibehaltung dieses „zustandsbehafteten Gedächtnisses" vermeidet PathWise die Wiederholung von Fehlern und baut auf Erfolgen auf, was zu einer schnelleren Konvergenz führt (schnelleres Erreichen der besten Lösung).

Die Ergebnisse: Schneller und intelligenter

Das Papier testete PathWise an verschiedenen komplexen Puzzles (wie dem Routenplanen von LKWs, dem Packen von Kartons und dem Lösen des Problems des Handlungsreisenden).

Geschwindigkeit: PathWise fand mit weniger Versuchen bessere Lösungen als andere Methoden. Es erreichte die „Ziellinie" schneller.
Qualität: Die von ihm erfundenen Regeln waren besser als die von Menschen oder anderen KI-Methoden erstellten.
Vielseitigkeit: Es funktionierte gut mit verschiedenen Arten von KI-Modellen (den „Rückgraten") und bei Problemen unterschiedlicher Größenordnung.

Zusammenfassende Analogie

Stellen Sie sich vor, Sie versuchen, das perfekte Sandwich zu erfinden.

Alte KI: Sie machen ein Sandwich, essen es, und wenn es schlecht ist, werfen Sie es weg und machen ein völlig zufälliges neues ohne Erinnerung daran, was Sie hinzugefügt haben.
PathWise: Sie führen ein Rezeptjournal. Wenn Sie ein Sandwich machen, schreiben Sie genau auf, was Sie getan haben. Wenn es schlecht schmeckt, lesen Sie das Journal, merken, dass Sie zu viel Salz hinzugefügt haben, und notieren dies. Beim nächsten Mal bitten Sie einen „Kritiker", Ihr Journal zu überprüfen, und er sagt Ihnen: „Raten Sie nicht einfach; verwenden Sie das salzarme Rezept von Dienstag, aber fügen Sie den Käse von Montag hinzu."

PathWise ist dieses intelligente Rezeptjournal-System, das es der KI ermöglicht, aus ihrer eigenen Geschichte zu lernen, um bessere Lösungen für komplexe Probleme zu erfinden.

Technische Zusammenfassung: PathWise

Problemstellung

Das automatisierte heuristische Design (AHD) zielt darauf ab, heuristische Algorithmen für kombinatorische Optimierungsprobleme (COPs) automatisch zu generieren und so die Abhängigkeit von manuellen, von Experten entworfenen Designs zu verringern. Obwohl Large Language Models (LLMs) AHD kürzlich ermöglicht haben, indem sie in evolutionäre Suchprozesse integriert wurden, leiden bestehende Rahmenwerke unter erheblichen Einschränkungen. Populationsbasierte Methoden verlassen sich häufig auf feste evolutionäre Regeln und statische Prompt-Vorlagen, was zu kurzsichtiger Heuristik-Generierung, redundanten Auswertungen und vorzeitiger Konvergenz führt. Baum-basierte Methoden, wie solche, die Monte-Carlo-Baumsuche (MCTS) verwenden, erzwingen hierarchische Strukturen, die von Leistungsstatistiken angetrieben werden, statt von einem semantischen Verständnis der Suchlandschaft. Entscheidend ist, dass aktuelle Ansätze eine zustandsbehaftete, semantische Repräsentation dessen vermissen, wie Heuristiken abgeleitet werden, wie Änderungen über Generationen hinweg propagieren oder warum Modifikationen erfolgreich sind oder scheitern. Dies führt zu einer ineffizienten Nutzung von LLM-Aufrufen und einem Versagen, vergangene Entscheidungen effektiv weiterzuführen.

Methodik

Die Autoren schlagen PathWise (Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs) vor, ein neuartiges Multi-Agenten-Verarbeitungsrahmenwerk, das die Heuristik-Generierung als sequenziellen Entscheidungsprozess über einen Entailment-Graphen (Ableitungsgraph) formuliert. Dieser Graph dient als kompakter, zustandsbehafteter Speicher der Suchbahn.

Kernkomponenten

Entailment-Graph ( $G = (V, E)$ ):
- Im Gegensatz zu Standard-Evolutionären Bäumen oder Populationen kodiert der Entailment-Graph die Ableitungsgeschichte.
- Knoten ( $v$ ): Repräsentieren Tupel, die heuristischen Code ( $h$ ), eine natürliche Sprachbegründung der Ableitung ( $\kappa$ ), eine algorithmische Beschreibung ( $d$ ), Leistungsmetriken ( $P(h; D)$ ) und Metadaten der Eltern ($PM$) enthalten.
- Kanten ( $E$ ): Verbinden Elternteilmengen mit Kindknoten und kodieren die spezifische Begründung, die verwendet wurde, um das Kind von seinen Eltern abzuleiten.
- Diese Struktur ermöglicht es dem System, zukünftige Entscheidungen auf der Ableitungsgeschichte zu basieren, anstatt Schritte als isolierte Stichprobenevents zu behandeln.
Multi-Agenten-System:
Das Rahmenwerk arbeitet über einen koordinierten Zyklus aus Planung, Ausführung und Reflexion über zwei Zeitskalen hinweg (äußere Populationsupdates und innere Entailment-Schritte):
- Policy-Agent ( $\pi_p$ ): Tritt als hochrangiger Planer auf. Er beobachtet den aktuellen Zustand (die Entailment-Graph-Frontier) und schlägt Aktionen vor, die durch ein Tupel aus ausgewählten Elternknoten ( $S$ ) und einer natürlichen Sprachbegründung der Ableitung ( $\kappa$ ) definiert sind. Dies ermöglicht es der Policy, dynamisch neue Operator-Typen zu erfinden, anstatt sich auf feste Vorlagen zu verlassen.
- World-Model-Agent ( $\pi_{wm}$ ): Tritt als niedrigrangiger Ausführer auf. Er übersetzt die hochrangigen Aktionen der Policy in ausführbaren heuristischen Code (Rollouts), konditioniert auf die ausgewählten Eltern und die Direktive.
- Kritiker-Agenten:
  - Policy-Kritiker ( $\pi_{p\_critic}$ ): Analysiert die Ergebnisse von Policy-Aktionen (Elternauswahlen und Direktiven), um gelenkte Reflexionen bereitzustellen, die zukünftige evolutionäre Strategien leiten.
  - World-Model-Kritiker ( $\pi_{wm\_critic}$ ): Vergleicht die am besten und am schlechtesten performenden heuristischen Rollouts, um Feedback zur Code-Synthesequalität zu geben und das World-Model anzuweisen, die algorithmische Struktur und Effizienz zu verfeinern.
Suchprozess:
- Äußere Schleife: Unterhält eine Population von Wurzelknoten.
- Innere Schleife: Baut inkrementell einen Entailment-Graphen auf, der an der aktuellen Population verwurzelt ist. In jedem Schritt sampelt das System mehrere Aktionen und Rollouts, wählt den besten resultierenden Knoten aus und aktualisiert den Graphen.
- Diversitätsmechanismen: Um Outputs mit geringer Diversität zu verhindern, setzt PathWise Prompt-Level-Diversität (Störung von Prompts mit explorativen Phrasen) und State-Shuffling (Randomisierung der Knotenreihenfolge zur Minderung von Positionsverzerrungen) ein.

Hauptbeiträge

Hybride Graph-Populations-Formulierung: Die Autoren führen eine Formulierung ein, bei der ein Entailment-Graph Ableitungsbegründung und Leistungsgeschichte kodiert und als gemeinsamer Zustand für die Interaktion von Policy und World-Model dient.
Koordiniertes Multi-Agenten-Rahmenwerk: Ein System, bei dem ein Policy-Agent die evolutionäre Strategie steuert, ein World-Model die Code-Generierung ausführt und Kritiker-Agenten gelenkte Reflexionen bereitstellen, was eine selbst-evolvierende, zustandsbewusste Heuristik-Generierung ohne Aktualisierung von LLM-Parametern ermöglicht.
Prompt-Level-Diversität: Mechanismen, um Vielfalt bei der Elternauswahl und bei heuristischen Rollouts sicherzustellen, was eine breitere Exploration über den Entailment-Graphen hinweg ermöglicht.
Empirische Validierung: Umfangreiche Experimente zeigen, dass PathWise stärkere Heuristiken mit weniger Auswertungen entdeckt, eine schnellere Konvergenz erreicht und sich effektiv auf größere Problemgrößen über diverse COPs hinweg skalieren lässt.

Experimentelle Ergebnisse

PathWise wurde an mehreren NP-schweren COPs evaluiert, darunter das Traveling Salesman Problem (TSP), das Rucksackproblem (KP), das Capacitated Vehicle Routing Problem (CVRP), das Multiple Knapsack Problem (MKP), das Orienteering Problem (OP) und das Bin Packing Problem (BPP). Das Rahmenwerk wurde über drei Suchparadigmen getestet: Schritt-für-Schritt-Konstruktion, Ameisenkolonie-Optimierung (ACO) und Geführte Lokale Suche (GLS).

Leistung: PathWise übertraf konsistent die State-of-the-Art-LLM-basierten AHD-Baselines (FunSearch, EoH, ReEvo, HSEvo, MCTS-AHD) und manuell entworfene Heuristiken. Es erzielte geringere Optimalitätslücken sowohl über In-Domain- als auch Out-of-Domain-Testsets hinweg.
Effizienz: PathWise konvergierte schneller zu besseren Heuristiken. In mehreren Experimenten erreichte PathWise mit nur 500 Auswertungen überlegene Leistung, während Baselines 1000 Auswertungen erlaubt waren.
Skalierbarkeit: Die Methode zeigte starke Generalisierung auf größere Problemgrößen (z. B. TSP mit $N=200$ , KP mit $N=500$ ) und verschiedene LLM-Backbones (GPT-4o-mini, GPT-5-nano mit variierenden Reasoning-Leveln).
Ablationsstudien: Das Entfernen von Kritiker-Agenten oder Diversitätsmechanismen verschlechterte die Leistung erheblich und bestätigte die Notwendigkeit von zustandsbewusstem Feedback und Exploration.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass PathWise einen Wandel von der „Versuchs-und-Irrtum-Evolution" hin zur „zustandsbewussten Planung durch Reasoning" darstellt. Indem die Heuristik-Entdeckung als sequenzieller Entscheidungsprozess über einen Entailment-Graphen behandelt wird, kann das System vergangene Entscheidungen weiterführen und Ableitungsinformationen über Generationen hinweg wiederverwenden oder vermeiden.

Die Autoren betonen, dass PathWise training-frei ist in dem Sinne, dass es keine LLM-Parameter aktualisiert; stattdessen nutzt es das vortrainierte Wissen von LLMs, das durch natürliche Sprachreflexionen verstärkt wird. Die Bedeutung liegt in seiner Fähigkeit, die Kurzsichtigkeit bestehender AHD-Methoden zu überwinden, indem es einen strukturierten Speicher des Suchprozesses bereitstellt, wodurch redundante Auswertungen reduziert und eine effektivere Entdeckung hochwertiger Heuristiken für komplexe kombinatorische Probleme ermöglicht wird. Die Arbeit legt nahe, dass strukturiertes Reasoning über die Ableitungsgeschichte ein kritischer Bestandteil für die Skalierung von LLM-basiertem automatischem Algorithmendesign ist.