GRASP: Graph Agentic Search over Propositions for Multi-hop Question Answering
Stockton Jenkins, Ramya Korlakai Vinayak, Junjie Hu · 2026
Read GRASP: Graph Agentic Search over Propositions for Multi-hop Question Answering by Stockton Jenkins, Ramya Korlakai Vinayak, Junjie Hu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16598.txt.
Introduction
Jenkins, Vinayak and Hu present GRASP, an agent system for questions that need several linked facts. It breaks a hard question into planned steps, scales up sub-agents with difficulty, and searches a three-layer graph of entities, claims, and passages. On three multi-hop benchmarks it tops accuracy in open retrieval while using far fewer tokens than rival systems, and it also leads in an extended-context setting.
Catalog record
| CREATOR | Stockton Jenkins, Ramya Korlakai Vinayak, Junjie Hu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73426 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.16598
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
GRASP: Graph Agentic Search over Propositions for Multi-hop Question Answering Stockton Jenkins, Ramya Korlakai Vinayak, Junjie Hu Abstract Agentic retrieval improves multi-hop question answering by giving language models autonomy to iteratively gather evidence. Recent work augments these systems with knowledge graphs for structured traversal, but this combination introduces significant cost: expensive graph construction at index time and compounding token usage at inference time. We introduce Gr aph A gentic S earch over P ropositions (GRASP), an agentic system that simultaneously optimizes for high accuracy and minimal token usage in multi-hop question answering. Rather than executing a rigid, singular query, GRASP actively coordinates its retrieval strategy by decomposing multi-hop queries into dependency-aware plans. This enables GRASP to dynamically scale the number of sub-agents according to the complexity of the problem. Each sub-agent resolves its single-hop query by exploring a novel three-layer hierarchical graph of entities, propositions, and passages, using the entity layer for targeted traversal and the proposition layer for high-recall passage retrieval via reciprocal-rank voting. We evaluate GRASP on MuSiQue, 2WikiMultihopQA, and HotpotQA under two settings: open-corpus retrieval and extended context reasoning (LongBench). GRASP achieves the highest QA accuracy in the open retrieval setting on MuSiQue and 2Wiki while using 40–50% fewer tokens than IRCoT+HippoRAG2. Furthermore, GRASP leads on EM and F1 across all three datasets in the LongBench setting while using 30% fewer tokens than the next most accurate method. Finally, we introduce success economy—the amortized token cost per correct answer, weighted by difficulty—and advocate for efficiency-aware evaluation as a standard practice for agentic QA. 1 Introduction Large language models encode vast world knowledge, yet retrieval-augmented generation remains essential for grounding their outputs in verifiable, up-to-date evidence ( 8 ; 21 ) . Single-shot retrieval is insufficient for multi-hop questions, as each hop introduces dependencies that semantic similarity alone cannot resolve ( 37 ; 28 ; 34 ) . Agentic retrieval addresses this by giving models autonomy to iteratively search, reason, and accumulate evidence. Recent work augments these agents with knowledge graphs for structured multi-hop traversal ( 22 ; 33 ) . However, this capability introduces a fundamental tension: as questions become more complex, token usage grows rapidly , driven by repeated LLM calls and expanding context across steps. This creates a key bottleneck for deploying agentic systems in practice. Figure 1: A comparison of graph structures for multi-hop QA. ❶ Relational knowledge graphs : HippoRAG extracts (subject, relation, object) triples into a flat knowledge graph and retrieves passages via Personalized PageRank. ❷ Factual graphs : GraphReader organizes atomic facts under key-element nodes into a highly connected graph, deployed by N parallel agents for traversal. ❸ Proposition graph (ours) : GRASP builds a hierarchical graph with three layers: typed entities for agentic traversal, propositions for retrieval, and source passages for post-retrieval context. Existing graph-based approaches to multi-hop QA fall along two tracks to optimize accuracy. First, retrieval-augmented methods such as HippoRAG ( 12 ) and GeAR ( 33 ) build triple-based knowledge graphs for structured traversal. However, recent work shows that triple extraction is both expensive and unreliable and often degrade retrieval quality below naive RAG ( 43 ; 13 ) . We build upon this work and further show in § A.1.3 that KG triples are sub-optimal retrieval units, motivating our exploration of an alternative indexing strategy. Second, extended-context methods such as GraphReader ( 22 ) organize long texts into navigable graphs explored by multiple parallel agents that process redundant information. Across both tracks, no existing work optimizes for total token usage across both indexing and inference in the agentic setting. In this paper, we propose GRASP: Gr aph A gentic S earch over P ropositions, an agentic retrieval system that jointly optimizes accuracy and token efficiency for multi-hop question answering. Rather than executing a singular retrieval query, GRASP decomposes multi-hop questions into dependency-aware plans, scaling the number of sub-agents to question complexity. Each sub-agent independently explores a three-layer hierarchical graph of entities, propositions, and passages constructed via joint extraction that avoids relational triples. Shared entities provide targeted gateways for traversal, propositions are a semantically rich retrieval unit for decomposed sub-questions, and passages supply full context for answering generation. Within each sub-agent, a compact observation state replaces growing message histories, bounding context growth over the life cycle of the agent. In summary, our contributions are as follows: 1. We propose GRASP, a graph-enhanced agentic retrieval system that optimizes for both token efficiency and accuracy. We evaluate on MuSiQue, 2Wiki, and HotpotQA across the retrieval and extended context setting, reporting token usage for all methods. To our knowledge, GRASP is the first system evaluated competitively across both settings. 2. We introduce a novel three-layer hierarchical graph using propositions as the core retrieval unit, which achieves higher passage recall than HippoRAG2’s triple-based graph at 69% fewer indexing tokens. 3. We design a planning-based inference pipeline with isolated sub-agents that compartmentalize context both across hops and within each sub-agent’s execution. 4. We introduce success economy : a metric inspired by information theory that amortizes token cost over difficulty-weighted correct answers. Furthermore, we encourage the community to adopt efficiency-aware evaluation for agentic QA systems. 2 Related Work Graph structures for retrieval. Graph-based retrieval captures inter-document relationships that flat indexing misses. HippoRAG ( 11 ) and HippoRAG2 ( 12 ) extract relational triples via OpenIE and retrieve passages through personalized PageRank (Figure 1 ). GeAR ( 33 ) adds LLM-guided beam search over a similar triple graph. LightRAG ( 10 ) proposes dual-level entity-and-relationship indexing, though it still relies on relation extraction. However, recent work ( 43 ; 13 ) demonstrates that triple extraction is lossy—relations are context-dependent and difficult to compress into atomic triples without losing semantic nuance. GraphRAG ( 7 ) and RAPTOR ( 31 ) take summarization-based approaches, building hierarchical indices via community detection or recursive abstraction. Agentic question answering. 42 ; 27 established the paradigm of interleaving reflection, tool use, and memory in LLM agents. IRCoT ( 38 ) interleaves chain-of-thought with retrieval; Self-Ask ( 28 ) decomposes questions into sequential sub-questions, a strategy we adopt in our planning module. Self-RAG ( 1 ) and Corrective RAG ( 40 ) introduce judges that control when to retrieve or re-retrieve, while FLARE ( 15 ) uses generation confidence to trigger retrieval. Several methods couple agents with knowledge graph traversal: Think-on-Graph ( 35 ) and Reasoning on Graphs ( 24 ) prompt LLMs to explore existing KGs, while KGP ( 39 ) constructs a graph from document collections. In the extended-context setting, GraphReader ( 22 ) links key elements through shared atomic facts (Figure 1 ) and deploys N parallel agents, but duplicates facts across nodes and lacks inter-agent coordination, resulting in redundant traversal and wasteful token consumption. ReadAgent ( 20 ) uses a gist memory index for selective recall without graph structure. Proposition-based representations. FActScore ( 25 ) introduced atomic fact decomposition for evaluating factual precision. PropSegmEnt ( 4 ) provides a corpus for proposition segmentation and entailment, WiCE ( 18 ) extends claim-level entailment to Wikipedia verification, and 5 train sub-sentence encoders for proposition-level embeddings. 6 adapted propositions to retrieval, showing that proposition-level indexing outperforms passage and sentence granularity for open-domain QA. 3 Method GRASP is built on two