💬 NLP

Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling

Die Arbeit stellt „Explore-on-Graph" (EoG) vor, ein neuartiges Framework, das Large Language Models durch verstärkendes Lernen mit pfadverfeinerten Belohnungssignalen dazu anregt, autonom diverse und effektive Schlussfolgerungspfade in Wissensgraphen zu erkunden, um Halluzinationen zu reduzieren und den State-of-the-Art in Wissensgraphen-Frageantwortungssystemen zu erreichen.

Ursprüngliche Autoren: Shiqi Yan, Yubo Chen, Ruiqi Zhou, Zhengxi Yao, Shuai Chen, Tianyi Zhang, Shijie Zhang, Wei Qiang Zhang, Yongfeng Huang, Haixin Duan, Yunqi Zhang

Veröffentlicht 2026-02-26

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Shiqi Yan, Yubo Chen, Ruiqi Zhou, Zhengxi Yao, Shuai Chen, Tianyi Zhang, Shijie Zhang, Wei Qiang Zhang, Yongfeng Huang, Haixin Duan, Yunqi Zhang

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

Titel: „Entdecke auf dem Graphen" – Wie KI lernt, selbstständig neue Wege zu finden

Stell dir vor, du hast einen riesigen, unendlichen Stadtplanausdruck vor dir. Das ist ein Wissensgraph (Knowledge Graph). Jeder Punkt auf dem Plan ist ein Ort (eine Person, eine Stadt, ein Unternehmen), und die Linien dazwischen sind Straßen, die zeigen, wie diese Orte miteinander verbunden sind.

Früher waren große KI-Modelle (LLMs) wie Touristen, die nur die bekannten Reiserouten kannten. Wenn sie eine Frage bekamen wie: „Welche Google-Mitarbeiter leben in London?", schauten sie auf ihren alten Reiseführer. Wenn dort stand: „Google → Mitarbeiter → Carol → lebt in London", dann war die Antwort gefunden.

Aber was passiert, wenn die Antwort nicht auf dem bekannten Pfad liegt? Was, wenn die Antwort über einen Umweg führt, den niemand vorher gezeichnet hat? Zum Beispiel: „Google → Tochterfirma (Youtube) → Mitarbeiter → Alice → lebt in London"? Oder noch komplizierter: „Google → Kollege → John → wohnt in London"?

Hier scheiterten die alten KIs oft. Sie halluzinierten (erfanden Fakten) oder gaben auf, weil sie nur das wiederholen konnten, was sie beim Training gelernt hatten. Sie wagten sich nicht aus dem Komfortbereich.

Die Lösung: EoG – Der abenteuerlustige Entdecker

Die Forscher haben eine neue Methode namens EoG (Explore-on-Graph) entwickelt. Man kann sich das wie einen Abenteurer mit einem magischen Kompass vorstellen.

1. Der Trainingsplan (Supervised Fine-Tuning)

Zuerst wird dem Abenteurer beigebracht, wie man überhaupt auf dem Plan läuft. Man gibt ihm eine Menge an Beispielen, wie man von A nach B kommt. Er lernt die Grundregeln: „Wenn du von einem Punkt zu einem anderen willst, musst du die Linien folgen." Das ist wie das Lernen des Alphabets, bevor man Romane schreibt.

2. Der eigentliche Durchbruch: Belohnung für Entdeckungen (Reinforcement Learning)

Hier wird es spannend. Die Forscher sagen dem Abenteurer: „Du darfst jetzt selbst entscheiden, wohin du gehst! Aber ich belohne dich nur, wenn du das richtige Ziel erreichst."

Das ist wie ein Videospiel, bei dem du nicht nur den Weg abläufst, den der Entwickler vorgeschrieben hat, sondern selbst neue Pfade erkundest.

Die Belohnung (Reward): Wenn der KI am Ende die richtige Antwort gibt, bekommt sie einen Punkt.
Das Problem: Manchmal läuft die KI in Sackgassen oder sucht endlos herum, bevor sie zufällig das Ziel findet. Das ist ineffizient.

3. Der geheime Trick: Der „Pfad-Belohnungs-Verfeinerer"

Um die KI nicht nur auf das Ergebnis, sondern auch auf den Weg zu fokussieren, haben die Forscher einen zweiten Belohnungstyp eingeführt.
Stell dir vor, du suchst einen Schatz.

Früher: Du bekommst Gold, wenn du den Schatz findest (egal wie lange du im Dschungel herumgelaufen bist).
Mit EoG: Du bekommst Gold, wenn du den Schatz findest UND wenn du auf deinem Weg die richtigen Landmarken (Bäume, Flüsse) erwähnt hast, die auf der Landkarte stehen.

Dieser zweite Belohnungstyp zwingt die KI, sinnvolle Pfade zu wählen. Sie lernt: „Aha, wenn ich diesen Umweg nehme, führe ich mich in eine Sackgasse. Aber wenn ich diese spezielle Verbindung benutze, komme ich schneller zum Ziel."

Warum ist das so genial?

Stell dir vor, du bist in einer fremden Stadt und suchst ein Restaurant.

Die alte KI würde nur die Restaurants aufsuchen, die in ihrem Reiseführer stehen. Wenn das Restaurant, das du suchst, in einer kleinen Gasse liegt, die nicht im Buch steht, findet sie es nicht.
Die EoG-KI ist wie ein lokaler Entdecker. Sie läuft nicht nur die Hauptstraßen ab. Sie wagt sich in die kleinen Gassen, testet neue Verbindungen und lernt aus jedem Schritt. Wenn sie feststellt, dass eine Gasse zu einer Sackgasse führt, merkt sie sich das für das nächste Mal.

Das Ergebnis

Die Forscher haben diese Methode an fünf verschiedenen „Prüfungen" getestet (verschiedene Wissensdatenbanken). Das Ergebnis ist beeindruckend:

Die EoG-KI hat nicht nur alle anderen offenen KI-Modelle geschlagen.
Sie hat sogar teure, geschlossene Super-KIs (wie die neuesten Versionen von GPT oder Gemini) übertroffen, obwohl sie auf kleineren, offenen Modellen läuft.

Zusammenfassend:
EoG ist wie ein KI-Abenteurer, der nicht mehr stur den Lehrbuchweg abläuft, sondern mutig neue Pfade erkundet. Durch eine kluge Belohnungsstrategie lernt sie, nicht nur das Ziel zu finden, sondern den besten Weg dorthin zu entdecken. Sie wird dadurch flexibler, intelligenter und macht weniger Fehler, wenn sie mit völlig neuen Situationen konfrontiert wird.

1. Problemstellung

Large Language Models (LLMs) leiden bei Aufgaben des Beantwortens von Fragen (Question Answering, QA) oft unter Halluzinationen und dem Fehlen von Faktenwissen. Ein vielversprechender Ansatz zur Lösung besteht darin, die Antworten der LLMs auf verifizierbare externe Wissensquellen wie Wissensgraphen (Knowledge Graphs, KGs) zu stützen.

Bisherige Methoden zur Verbesserung des KG-basierten Reasonings lassen sich in zwei Kategorien einteilen:

Regelbasierte Methoden: Erzwingen logische Konsistenz durch vordefinierte Regeln.
Imitationsbasierte Methoden: Trainieren LLMs, um Reasoning-Pfade aus einem festen Satz von Demonstrationen nachzuahmen.

Das zentrale Problem: Beide Ansätze schränken das Reasoning der LLMs auf bekannte Muster ein, die in den Trainingsdaten oder den vordefinierten Regeln enthalten sind. Sie versagen häufig bei komplexen Graphen oder bei Reasoning-Mustern, die außerhalb der Trainingsverteilung liegen (Out-of-Distribution, O.O.D.). Die Modelle können keine neuen, unkonventionellen Pfade im Wissensgraphen erkunden, um Antworten zu finden, die nicht den häufigsten Mustern entsprechen.

2. Methodik: Explore-on-Graph (EoG)

Das Papier stellt Explore-on-Graph (EoG) vor, ein Framework, das LLMs ermutigt, autonom einen diverseren Reasoning-Raum auf Wissensgraphen zu erkunden. Der Ansatz besteht aus zwei Hauptphasen:

Phase 1: Supervised Fine-Tuning (SFT)

Um eine solide Grundlage für das Erkunden zu schaffen, wird zunächst ein Long Chain-of-Thought (CoT) Dataset konstruiert.

Ein leistungsstarkes Modell (hier Gemini 2.5 Flash) generiert strukturierte, logische Reasoning-Pfade und Antworten basierend auf dem Wissensgraphen.
Das Ziel-LLM wird auf diesem Datensatz feinabgestimmt (SFT), um die Fähigkeit zu erlangen, strukturierte Reasoning-Pfade zu generieren, die mit dem Graphen übereinstimmen. Dies dient als „Cold Start" für die anschließende Exploration.

Phase 2: Reinforcement Learning (RL) mit Pfad-verfeinerter Belohnung

Dies ist der Kerninnovation des Papiers. Um die Exploration über die Trainingsverteilung hinaus zu fördern, wird Reinforcement Learning eingesetzt. Der Prozess ist in zwei Teilphasen unterteilt:

Outcome Reward (Ergebnis-Belohnung):
- Basierend auf der Group Relative Policy Optimization (GRPO) wird die Politik optimiert.
- Die primäre Belohnung basiert auf der Korrektheit der finalen Antwort (gemessen durch den Entity-Level F1-Score). Das Modell lernt, Pfade zu bevorzugen, die zu korrekten Antworten führen.
Path-Refined Reward (Pfad-verfeinerte Belohnung):
- Um die Effizienz und semantische Bedeutung der Exploration zu erhöhen, wird eine zusätzliche Belohnungssignal eingeführt.
- Anstatt nur das Endergebnis zu bewerten, wird geprüft, wie viele korrekte Triplets (Subjekt, Relation, Objekt) aus dem Ground-Truth-Reasoning-Pfad im generierten Denkprozess des Modells vorkommen.
- Dies wird durch eine „Search-and-Verify"-Pipeline ermittelt, die potenzielle Pfade im Graphen sucht und durch ein LLM semantisch verifiziert.
- Die Gesamtbelohnung $R_{joint}$ setzt sich zusammen aus: $R_{outcome} + \alpha \cdot R_{path}$ .

Dieser Ansatz verhindert, dass das Modell zufällige oder sinnlose Pfade erkundet, und lenkt die Suche gezielt zu effizienten und logisch kohärenten Wegen im Graphen.

3. Schlüsselbeiträge

Autonome Exploration: EoG überwindet die Limitationen von Imitationslernen, indem es LLMs befähigt, aktiv neue Reasoning-Muster zu entdecken, die außerhalb der Trainingsverteilung liegen (O.O.D.).
Path-Refined Reward Modeling: Die Einführung von Pfad-Informationen als zusätzliche Belohnungssignale verbessert die Effizienz der Exploration erheblich, indem sie das Modell dazu anleitet, nicht nur das richtige Ergebnis, sondern auch den korrekten logischen Weg zu finden.
Zweistufiges Training: Die Kombination aus SFT (für strukturierte Grundlagen) und RL (für Diversifizierung und Optimierung) ermöglicht eine robuste Anpassung an komplexe Graphen-Reasoning-Aufgaben.
Überlegenheit gegenüber Closed-Source-Modellen: Das Framework wurde so entwickelt, dass es auch mit Open-Source-Modellen (Qwen2.5-7B, Llama-3.1-8B) State-of-the-Art-Ergebnisse erzielt, die sogar stärkere geschlossene Modelle übertreffen.

4. Ergebnisse

Die Autoren führten umfangreiche Experimente auf fünf KGQA-Benchmark-Datensätzen durch (WebQSP, CWQ, GrailQA, QALD10-en, 2WikiMultihopQA).

State-of-the-Art Performance: EoG erzielt auf allen fünf Datensätzen die besten Ergebnisse, sowohl bei Open-Source-Modellen als auch im Vergleich zu geschlossenen Modellen wie Gemini 2.5 Pro und GPT-5.
Robustheit bei O.O.D.: Das Modell zeigt eine signifikant höhere Generalisierungsfähigkeit auf Out-of-Distribution-Daten im Vergleich zu reinen SFT-Modellen oder anderen Baselines. Die O.O.D.-zu-I.I.D.-Raten sind deutlich höher.
Effizienz der Exploration: Durch den Pfad-verfeinerten Reward wird die „Exploration Efficiency" verbessert (weniger unnötige Triplets werden erkundet, um eine korrekte Antwort zu finden) und die „Coverage" des Reasoning-Raums erhöht.
Ablationsstudien: Die Studien bestätigen, dass sowohl der Outcome-RL als auch der Path-RL essenziell sind. Ohne SFT ist die Leistung suboptimal, und ohne den Pfad-Reward sinkt die Effizienz und Qualität der Reasoning-Pfade.

5. Bedeutung und Ausblick

Die Arbeit demonstriert, dass die reine Nachahmung von Reasoning-Mustern nicht ausreicht, um komplexe Fragen auf Wissensgraphen zu beantworten. Die Fähigkeit zur autonomen Exploration ist entscheidend für die Generalisierung.

Paradigmenwechsel: Der Ansatz verschiebt den Fokus von „Regel-basiertem" oder „Imitations-basiertem" Reasoning hin zu einem explorativen, belohnungsgesteuerten Lernen.
Praktische Anwendbarkeit: Da EoG auch mit kleineren, offenen Modellen funktioniert und diese geschlossene Modelle übertreffen kann, bietet es eine kosteneffiziente und skalierbare Lösung für vertrauenswürdige KI-Systeme in realen Anwendungen.
Zukünftige Forschung: Die Autoren schlagen vor, zukünftig noch ausgefeiltere Belohnungsstrategien zu erforschen, die die Struktur von Wissensgraphen noch tiefer integrieren, um die Effizienz und Bedeutung des Reasonings weiter zu steigern.

Zusammenfassend stellt EoG einen bedeutenden Fortschritt im Bereich des KG-basierten Reasonings dar, indem es die inhärenten Grenzen von LLMs durch gezielte, belohnungsgesteuerte Exploration überwindet.