🤖 AI

GRASP: Graph Agentic Search over Propositions for Multi-hop Question Answering

GRASP ist ein effizientes agentices Abrufsystem, das die Genauigkeit von mehrstufigen Frage-Antwort-Aufgaben und die Token-Nutzung optimiert, indem es komplexe Anfragen in dynamische Teilaufgaben zerlegt und ein neuartiges dreischichtiges hierarchisches Graphenmodell aus Entitäten, Propositionen und Passagen für gezielte Traversierung und Abruf mit hoher Recall-Rate nutzt.

Ursprüngliche Autoren: Stockton Jenkins, Ramya Korlakai Vinayak, Junjie Hu

Veröffentlicht 2026-05-19

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Stockton Jenkins, Ramya Korlakai Vinayak, Junjie Hu

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 sind ein Detektiv, der versucht, ein komplexes Rätsel zu lösen, wie etwa: „Wer hat den Song geschrieben, den der Sänger von „Too Late for Goodbyes" vorgetragen hat?" Um dies zu lösen, können Sie nicht nur eine Frage stellen; Sie müssen einer Spur von Hinweisen folgen. Zuerst finden Sie den Sänger. Dann finden Sie den Song, den er vorgetragen hat. Schließlich finden Sie den Komponisten.

Genau das ist Multi-Hop-Fragebeantwortung: eine Denkfolge, bei der jeder Schritt von der Antwort auf den vorherigen abhängt.

Die Arbeit stellt ein neues Detektivsystem namens GRASP (Graph Agentic Search over Propositions) vor. So funktioniert es, unter Verwendung einfacher Analogien:

Das Problem: Der alte Weg war zu teuer

Frühere Detektivsysteme versuchten, diese Rätsel zu lösen, indem sie vor Beginn eine massive, starre Faktenkarte (ein „Wissensgraph") erstellten.

Die Kosten: Der Bau dieser Karte war wie die Anstellung einer Armee von Schreibern, die jedes Buch in der Bibliothek in winzige, unverbundene Faktenkarten (Triples wie „Subjekt-Relation-Objekt") umschreiben. Dies kostete viel Zeit und Geld (Tokens).
Die Ineffizienz: Als der Detektiv mit der Suche begann, musste er oft zu viel irrelevante Information lesen oder zu viele Telefonate (LLM-Abfragen) führen, um die Punkte zu verbinden, und verbrauchte dabei schnell sein Budget.

Die Lösung: GRASPs dreischichtige Bibliothek

GRASP verändert das Spiel, indem es eine intelligentere, flexiblere Bibliothek aufbaut. Anstelle starrer Faktenkarten organisiert es Informationen in drei Schichten, wie ein gut organisiertes Ablagesystem:

Die Entitätsschicht (Die Indexkarten): Dies sind die Hauptcharaktere oder Dinge (z. B. „Paul McCartney", „Deutschland"). Sie fungieren als „Türen" oder Eingänge in die Bibliothek.
Die Propositionsschicht (Die atomaren Fakten): Dies ist das Geheimnis. Anstatt Sätze in starre „Subjekt-Verb-Objekt"-Triples zu zerlegen, zerlegt GRASP sie in atomare Propositionen – kleine, in sich geschlossene, natürliche Sätze (z. B. „Der Osterhase wurde 1678 in Deutschland aufgenommen").
- Warum das wichtig ist: Denken Sie an ein Triple als einen zerbrochenen Satz, der seine Bedeutung verliert. Eine Proposition ist ein vollständiger, klarer Gedanke. Es ist für die KI einfacher, sie zu verstehen und mit einer Frage abzugleichen.
Die Passage-Schicht (Die ganzen Bücher): Dies sind die originalen Quelldokumente. Sobald der Detektiv die richtige „Proposition" (den Hinweis) findet, holt er die vollständige „Passage" (das Buchkapitel), um den vollständigen Kontext für die endgültige Antwort zu erhalten.

Wie GRASP ein Rätsel löst (Der Arbeitsablauf)

1. Der Planer (Der Strateg)
Anstatt blind zu suchen, verfügt GRASP über einen „Planer"-Agenten. Wenn Sie eine komplexe Frage stellen, zerlegt der Planer sie in eine schrittweise To-do-Liste.

Analogie: Wenn Sie fragen: „Wer ist die Mutter der Person, die die Glühbirne erfunden hat?", sagt der Planer: „Schritt 1: Finden Sie heraus, wer die Glühbirne erfunden hat. Schritt 2: Finden Sie die Mutter dieser Person." Er erstellt eine Abhängigkeitskarte, damit der Detektiv genau weiß, wonach er als Nächstes suchen muss.

2. Die Sub-Agenten (Die Feldagenten)
GRASP schickt nicht einen einzigen riesigen Verstand, um die ganze Arbeit zu erledigen. Es schickt für jeden Schritt des Plans kleine, spezialisierte Sub-Agenten aus.

Effizienz: Wenn ein Schritt einfach ist, wird ein Agent verwendet. Wenn ein Schritt komplex ist, skaliert es hoch. Entscheidend ist, dass jeder Agent nur ein „kompaktes Gedächtnis" von dem behält, was er gerade gefunden hat. Er trägt nicht das Gewicht der gesamten Gesprächshistorie, was ein enormes „Token"-Budget (Geld/Rechenleistung) spart.

3. Die Suche (Die Detektivarbeit)
Wenn ein Sub-Agent einen Hinweis benötigt:

Er betrachtet zuerst die Propositionsschicht. Da dies klare, natürliche Sätze sind, kann die KI die richtigen Hinweise sehr schnell mithilfe einer „Hybridsuche" (Suche nach exakten Wörtern und ähnlichen Bedeutungen) finden.
Er verwendet ein „RankVote"-System. Stellen Sie sich vor, der Agent findet 50 Hinweise. Anstatt alle 50 Bücher zu lesen, betrachtet er, welche Hinweise am relevantesten sind, und „stimmt" für die spezifischen Buchkapitel (Passagen), die diese Hinweise enthalten. Dies stellt sicher, dass er nur die wichtigsten Seiten liest.

4. Die Synthese (Der Abschlussbericht)
Sobald alle Sub-Agenten ihre Schritte abgeschlossen haben, fügt ein finales Modul alle Antworten zu einer kohärenten Geschichte zusammen.

Die Ergebnisse: Schneller, günstiger, intelligenter

Die Autoren testeten GRASP an drei großen „Rätsel-Datensätzen" (MuSiQue, 2Wiki und HotpotQA).

Genauigkeit: GRASP löste die Rätsel genauer als frühere Spitzensysteme.
Effizienz: Es verwendete 30 % bis 50 % weniger Tokens (Rechenressourcen) als die nächstbesten Methoden.
- Analogie: Wenn das alte System 100 Dollar ausgab, um ein Rätsel zu lösen, löste GRASP es für 50 Dollar und erzielte gleichzeitig ein besseres Ergebnis.

Ein neuer Weg, Erfolg zu messen: „Success Economy"

Die Arbeit führt eine neue Metrik namens Success Economy ein.

Das Konzept: Es reicht nicht aus, nur die richtige Antwort zu erhalten; man muss fragen: „Wie viel hat es gekostet, diese Antwort zu erhalten?"
Die Wendung: Sie gewichtet die Kosten danach, wie schwierig die Frage war. Ein schwieriges Rätsel günstig zu lösen, ist mehr wert als ein einfaches Rätsel günstig zu lösen. GRASP gewinnt diese Metrik, weil es die schwierigen Antworten richtig löst, ohne Ressourcen zu verschwenden.

Zusammenfassung

GRASP ist ein Detektivsystem, das:

Plant, bevor es sich bewegt.
Atomare, natürliche Fakten (Propositionen) anstelle starrer, zerbrochener Datenstrukturen verwendet.
Kleine, fokussierte Agenten aussendet, die kein schweres Gepäck mit sich tragen.
Für die besten Beweise stimmt, um das Lesen unnötiger Texte zu vermeiden.

Das Ergebnis ist ein System, das nicht nur intelligenter darin ist, komplexe, mehrstufige Rätsel zu lösen, sondern auch erheblich günstiger und effizienter im Betrieb ist.

Technische Zusammenfassung: GRASP (Graph Agentic Search over Propositions)

Problemstellung

Multi-Hop-Fragebeantwortung (QA) erfordert, dass Modelle Beweise iterativ sammeln, um Abhängigkeiten aufzulösen, die allein durch semantische Ähnlichkeit nicht gelöst werden können. Während neuere agentische Retrieval-Systeme die Genauigkeit verbessern, indem sie Sprachmodellen (LLMs) die Autonomie zum Suchen und Schlussfolgern gewähren, stehen sie vor einem kritischen Engpass: Token-Effizienz.

Bestehende graphenbasierte Ansätze, wie HippoRAG und GeAR, nutzen Wissensgraphen (KGs), die aus relationalen Tripeln (Subjekt-Relation-Objekt) konstruiert sind, um eine strukturierte Traversierung zu ermöglichen. Dies führt jedoch zu erheblichen Kosten:

Indexierungskosten: Das Extrahieren und Konstruieren tripelbasierter KGs ist rechenintensiv und oft unzuverlässig, was die Retrieval-Qualität manchmal sogar unter die von naivem RAG absinken lässt.
Inferenzkosten: Agentische Systeme leiden häufig unter einer kumulativen Token-Nutzung aufgrund wiederholter LLM-Aufrufe, sich erweiternder Kontextfenster und redundanter Traversierung durch parallele Agenten.

Aktuelle Methoden versagen darin, sowohl hohe Genauigkeit als auch minimale Token-Nutzung über die Phasen der Indexierung und Inferenz hinweg gemeinsam zu optimieren.

Methodik: GRASP

Die Autoren schlagen GRASP (Graph Agentic Search over Propositions) vor, ein agentisches Retrieval-System, das darauf ausgelegt ist, sowohl die QA-Genauigkeit als auch die Token-Effizienz zu optimieren. GRASP arbeitet durch drei Kernkomponenten:

1. Hierarchischer Graphaufbau mit drei Schichten

Im Gegensatz zu tripelbasierten KGs konstruiert GRASP einen Graphen $G = (V_E, V_P, V_D, E)$ mit drei distincten Schichten:

Entitätsschicht ( $V_E$ ): Getypte Entitäten (z. B. „Person", „Ort"), die aus Text extrahiert werden. Diese dienen als gezielte Einstiegspunkte für die Traversierung.
Propositionsschicht ( $V_P$ ): Die zentrale Retrieval-Einheit. Anstelle atomarer Tripel extrahiert das System atomare, in sich geschlossene natürliche Sprachpropositionen (z. B. „Der Osterhase wurde 1678 in Südwestdeutschland verzeichnet").
Passage-Schicht ( $V_D$ ): Die ursprünglichen Quelldokumente, die mit ihren konstituierenden Propositionen verknüpft sind.

Extraktionsprozess: Entitäten und Propositionen werden gemeinsam in einem einzigen LLM-Aufruf extrahiert. Entitäten werden über Indexreferenzen mit ihren Quellpropositionen verknüpft, wodurch die Graphkanten entstehen. Dies vermeidet den verlustbehafteten Komprimierungsprozess von Kontext in relationale Tripel.

2. Planbasierte Inferenzpipeline

GRASP zerlegt komplexe Multi-Hop-Fragen in abhängigkeitsbewusste Pläne:

Planer: Ein Modul generiert einen natürlichen Sprach-Schlussfolgerungs-Entwurf und eine geordnete Sequenz von Teilfragen. Entscheidend ist, dass es numerische Platzhalter (z. B. #1) verwendet, um Antworten aus vorherigen Teilfragen explizit zu referenzieren, was die Abhängigkeitsstruktur von Datensätzen wie MuSiQue widerspiegelt.
Sub-Agent-Ausführung: Jede Teilfrage wird von einem unabhängigen Sub-Agenten bearbeitet. Der Agent führt einen kompakten Beobachtungszustand ( $O_i$ $O_{i}$ ) statt eines vollständigen Gesprächsverlaufs, um das Kontextwachstum zu begrenzen.
- Hybride Suche: Der Agent formuliert die Teilfrage in eine deklariative Suchaussage und eine Liste von Schlüsselwörtern um. Er führt eine hybride Suche (dichte Vektoren + BM25) über die Propositionsschicht durch, um Kandidatenentitäten zu ermitteln.
- RankVote-Bewertung: Die ermittelten Propositionen werden zu Kandidatenentitäten aggregiert. Für das Passage-Retrieval verwendet das System RankVote, einen reziproken Rang-Stimmmechanismus, der Passagen basierend auf den Rängen ihrer konstituierenden Propositionen bewertet und hochrelevante Kontexte priorisiert.
- Iterative Verfeinerung: Der Agent bewertet, ob die Beweise ausreichend sind. Falls nicht, schreibt er die Suchaussage um und startet die Traversierung erneut (bis zu einem Limit), um redundantes erneutes Lesen von Beweisen zu vermeiden.

3. Metrik der Erfolgswirtschaft

Die Arbeit führt die Erfolgswirtschaft ( $C_w$ ) ein, eine von der Informationstheorie inspirierte Metrik zur Bewertung der Effizienz. Sie amortisiert die gesamten Token-Kosten über gewichtete korrekte Antworten:
$C_w = \frac{\sum T_i}{\sum w_i \cdot \mathbb{1}[EM_i = 1]}$
wobei $w_i = -\log_2(r_i)$ die Überraschung (Selbstinformation) einer korrekten Antwort ist, geschätzt durch mehrfaches Auffordern des Basis-LLMs. Dies bestraft Token-Verschwendung und belohnt die effiziente Lösung schwieriger Fragen.

Hauptbeiträge

GRASP-System: Ein graphenverbessertes, agentisches Retrieval-System, das Genauigkeit und Token-Effizienz gemeinsam optimiert und sowohl im Open-Retrieval- als auch im Extended-Context-Setting wettbewerbsfähig bewertet wird.
Propositionsbasierte Indexierung: Ein neuartiger dreischichtiger hierarchischer Graph, der Propositionen als zentrale Retrieval-Einheit verwendet. Die Autoren zeigen, dass dies eine höhere Passage-Recall-Rate als tripelbasierte Graphen (HippoRAG2) erreicht, während 69 % weniger Indexierungs-Token verwendet werden.
Kompartimentierte Inferenz: Eine planbasierte Pipeline mit isolierten Sub-Agenten, die den Kontext sowohl über Hops hinweg als auch innerhalb der einzelnen Agentenausführung kompartimentieren, um ein ungebundenes Kontextwachstum zu verhindern.
Erfolgswirtschaft: Eine neue Evaluierungsmetrik, die eine effizienzorientierte Bewertung in der agentischen QA befürwortet und sich über reine Genauigkeits-Benchmarks hinaus bewegt.

Experimentelle Ergebnisse

GRASP wurde unter zwei Settings auf MuSiQue, 2WikiMultihopQA und HotpotQA evaluiert:

Open-Corpus-Retrieval-Setting

Leistung: GRASP erzielte die höchsten Exact Match (EM), F1- und Judge-Scores auf MuSiQue und 2Wiki und übertraf IRCoT+HippoRAG2.
Effizienz: Es verwendete 40–50 % weniger Token als IRCoT+HippoRAG2 und erreichte gleichzeitig eine überlegene Genauigkeit. Auf HotpotQA erzielte IRCoT+HippoRAG2 zwar eine leicht höhere Genauigkeit, jedoch zu mehr als dem doppelten Token-Aufwand.
Retrieval-Qualität: Im simulierten agentischen Retrieval erreichte GRASP eine Recall-Rate von 0,904 im Vergleich zu 0,817 bei HippoRAG2, was Propositionen als überlegene Retrieval-Einheit validiert.

Extended-Context (LongBench)-Setting

Leistung: GRASP führte bei EM und F1 über alle drei Datensätze hinweg. Auf 2Wiki verbesserte es den EM um 12 Punkte gegenüber GraphReader, bei Verwendung von ungefähr 70 % der Token-Kosten.
Effizienz: GRASP verwendete 30 % weniger Token als die nächstgenaueste Methode (GraphReader) und behielt dabei wettbewerbsfähige oder überlegene Judge-Scores bei.
Ablation: Das Entfernen des Propositionsgraphen oder der Entitätsauswahlschicht verschlechterte die Leistung erheblich oder erhöhte den Token-Verbrauch, was die Notwendigkeit der dreischichtigen Struktur bestätigt.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass GRASP auf der Pareto-Grenze für die Genauigkeits-Kosten-Abwägung in Multi-Hop-QA liegt. Indem Token-Effizienz als gleichrangiges Designziel neben der Genauigkeit behandelt wird, adressiert GRASP die fundamentale Spannung in agentischen Systemen, bei der die Tiefe des Schlussfolgerns typischerweise zu einem exponentiellen Token-Wachstum führt.

Die Autoren betonen, dass:

Propositionen Tripeln überlegen sind: Sie bewahren semantische Nuancen, die bei der Tripel-Extraktion verloren gehen, und dienen als diskriminierendere Einheiten für embeddings-basiertes Retrieval.
Strukturierte Dekomposition entscheidend ist: Eine planbasierte Dekomposition in Kombination mit strukturiertem Retrieval (dem Graphen) ist effektiver als die reine Verflechtung von Retrieval mit Chain-of-Thought.
Effizienz eine Standardanforderung ist: Die Einführung der „Erfolgswirtschaft" befürwortet, dass die Gemeinschaft die effizienzorientierte Evaluierung als Standardpraxis übernimmt, wobei anerkannt wird, dass die Inferenzkosten direkt mit der Komplexität des Schlussfolgerns skalieren.

Die Arbeit legt nahe, dass zukünftige Verbesserungen darauf abzielen könnten, die Dekompositionsgenauigkeit des Planers (der derzeit ein Engpass für 3- und 4-Hop-Fragen ist) durch überwachtes Fine-Tuning oder Reinforcement Learning zu verfeinern, aber die aktuelle Architektur bereits einen bedeutenden Sprung beim Ausgleich von Leistung und Kosten demonstriert.