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

2026-05-19 · Source: cs.MA updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Natural Language Processing · Depth: Expert, extended

Summary

GRASP (Graph Agentic Search over Propositions) is a novel agentic retrieval system designed for multi-hop question answering that prioritizes both high accuracy and minimal token usage. It addresses the high cost and token consumption of existing graph-augmented LLM systems by decomposing complex queries into dependency-aware plans, dynamically scaling sub-agents based on problem complexity. Each sub-agent navigates a three-layer hierarchical graph of entities, propositions, and passages, using entities for targeted traversal and propositions for high-recall passage retrieval via reciprocal-rank voting. Evaluated on MuSiQue, 2WikiMultihopQA, and HotpotQA, GRASP achieves superior QA accuracy in open retrieval settings on MuSiQue and 2Wiki, using 40–50% fewer tokens than IRCoT+HippoRAG2. In extended context reasoning (LongBench), GRASP leads on EM and F1 across all three datasets, consuming 30% fewer tokens than the next most accurate method. The system also introduces "success economy" as an efficiency-aware evaluation metric.

Key takeaway

For AI Architects and Research Scientists developing multi-hop QA systems, GRASP offers a compelling blueprint for achieving high accuracy while significantly reducing operational costs. Your teams should consider adopting a hierarchical proposition-based graph structure and a planning-based agentic inference pipeline to manage token usage effectively. This approach can lead to more efficient and scalable deployments, especially for complex reasoning tasks, by minimizing redundant LLM calls and context growth.

Key insights

GRASP optimizes multi-hop QA by combining a hierarchical proposition-based graph with dependency-aware agentic planning for efficiency and accuracy.

Principles

• Propositions are superior retrieval units to relational triples.
• Decomposition-based planning improves multi-hop QA accuracy.
• Context compartmentalization reduces token usage in agentic systems.

Method

GRASP constructs a three-layer graph (entities, propositions, passages) via joint extraction, then uses a planner to decompose multi-hop questions into sub-questions for independent sub-agents that perform hybrid search and RankVote-based passage retrieval.

In practice

• Use proposition-level indexing for improved recall and efficiency.
• Implement dependency-aware planning for complex multi-hop queries.
• Adopt "success economy" to evaluate agentic QA systems for cost-effectiveness.

Topics

• Multi-hop Question Answering
• Agentic Retrieval Systems
• Proposition-based Graphs
• Token Efficiency
• Hierarchical Graph Structures

Best for: Research Scientist, AI Architect, AI Engineer, AI Scientist, Machine Learning Engineer, NLP Engineer

Related on AIssential

• AgREE: Agentic Reasoning for Knowledge Graph Completion on Emerging Entities — AgREE uses agent-based reasoning and iterative retrieval to complete knowledge graphs for emerging entities without training.
• Retrieval is Cheap, Show Me the Code: Executable Multi-Hop Reasoning for Retrieval-Augmented Generation — Reformulating multi-hop RAG as program synthesis and execution enhances verifiability and performance.
• SING: Synthetic Intention Graph for Scalable Active Tool Discovery in LLM Agents — Intention-aware graph structures enable accurate, context-efficient tool discovery for LLM agents in large ecosystems.
• TopBench: A Benchmark for Implicit Predictive Reasoning in Tabular Question Answering — LLMs struggle with implicit predictive reasoning in tabular data, often misinterpreting intent as simple retrieval.
• Quantifying the Accuracy and Cost Impact of Design Decisions in Budget-Constrained Agentic LLM Search — Budgeting search depth and retrieval quality offers more accuracy gains than expanding token limits for agentic RAG.
• AI Dev 25 x NYC | Nyah Macklin: How to Structure Context to Make Your Agents Smarter — Knowledge graphs provide structured, relational context for AI agents, enabling multi-hop reasoning and superior accuracy.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.MA updates on arXiv.org.