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

arXiv: https://arxiv.org/abs/2605.16598 · HTML: https://mlsanity.com/paper/2605.16598/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Web, search, and research agents, one of 16 directions in LLM agents and tool use.
- Builds on 30 of its 39 references that are in the map.
- First posted on arXiv 15 May 2026.

## Placed in

- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

## Builds on (most cited first, 30 of 30)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Retrieval-Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2312.10997/) (2023)
- [Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection](https://mlsanity.com/paper/2310.11511/) (2023)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [PubMedQA: A Dataset for Biomedical Research Question Answering](https://mlsanity.com/paper/1909.06146/) (2019)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [FActScore: Fine-grained Atomic Evaluation of Factual Precision in Long Form Text Generation](https://mlsanity.com/paper/2305.14251/) (2023)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions](https://mlsanity.com/paper/2212.10509/) (2022)
- [MuSiQue: Multihop Questions via Single-hop Question Composition](https://mlsanity.com/paper/2108.00573/) (2021)
- [RAPTOR: Recursive Abstractive Processing for Tree-Organized Retrieval](https://mlsanity.com/paper/2401.18059/) (2024)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [Agentic Retrieval-Augmented Generation: A Survey on Agentic RAG](https://mlsanity.com/paper/2501.09136/) (2025)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [From RAG to Memory: Non-Parametric Continual Learning for Large Language Models](https://mlsanity.com/paper/2502.14802/) (2025)
- [Knowledge Graph Prompting for Multi-Document Question Answering](https://mlsanity.com/paper/2308.11730/) (2023)
- [A Human-Inspired Reading Agent with Gist Memory of Very Long Contexts](https://mlsanity.com/paper/2402.09727/) (2024)
- [Compositional Questions Do Not Necessitate Multi-hop Reasoning](https://mlsanity.com/paper/1906.02900/) (2019)
- [Dense X Retrieval: What Retrieval Granularity Should We Use?](https://mlsanity.com/paper/2312.06648/) (2023)
- [Understanding Dataset Design Choices for Multi-hop Reasoning](https://mlsanity.com/paper/1904.12106/) (2019)
- [LinearRAG: Linear Graph Retrieval Augmented Generation on Large-scale Corpora](https://mlsanity.com/paper/2510.10114/) (2025)
- [GraphReader: Building Graph-based Agent to Enhance Long-Context Abilities of Large Language Models](https://mlsanity.com/paper/2406.14550/) (2024)
- [PropSegmEnt: A Large-Scale Corpus for Proposition-Level Segmentation and Entailment Recognition](https://mlsanity.com/paper/2212.10750/) (2022)
- [Efficient Context Selection for Long-Context QA: No Tuning, No Iteration, Just Adaptive-k](https://mlsanity.com/paper/2506.08479/) (2025)
- [Sub-Sentence Encoder: Contrastive Learning of Propositional Semantic Representations](https://mlsanity.com/paper/2311.04335/) (2023)
- [Towards flexible perception with visual memory](https://mlsanity.com/paper/2408.08172/) (2024)

## Abstract (arXiv)

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 Graph Agentic Search over Propositions (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 percent fewer tokens than IRCoT+HippoRAG2. Furthermore, GRASP leads on EM and F1 across all three datasets in the LongBench setting while using 30 percent 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.