🤖 AI

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

GRASP is an efficient agentic retrieval system that optimizes multi-hop question answering accuracy and token usage by decomposing complex queries into dynamic sub-tasks and leveraging a novel three-layer hierarchical graph of entities, propositions, and passages for targeted traversal and high-recall retrieval.

Original authors: Stockton Jenkins, Ramya Korlakai Vinayak, Junjie Hu

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Stockton Jenkins, Ramya Korlakai Vinayak, Junjie Hu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a complex mystery, like "Who wrote the song that the singer of 'Too Late for Goodbyes' performed?" To solve this, you can't just ask one question; you have to follow a trail of clues. First, you find the singer. Then, you find the song they performed. Finally, you find the writer.

This is what Multi-hop Question Answering is: a chain of reasoning where each step depends on the answer to the previous one.

The paper introduces a new detective system called GRASP (Graph Agentic Search over Propositions). Here is how it works, using simple analogies:

The Problem: The Old Way Was Too Expensive

Previous detective systems tried to solve these mysteries by building a massive, rigid map of facts (a "Knowledge Graph") before they even started.

The Cost: Building this map was like hiring an army of scribes to rewrite every book in the library into tiny, disconnected fact cards (triples like "Subject-Relation-Object"). This took a lot of time and money (tokens).
The Inefficiency: When the detective started searching, they often had to read too much irrelevant information or make too many phone calls (LLM queries) to connect the dots, burning through their budget quickly.

The Solution: GRASP's Three-Layer Library

GRASP changes the game by building a smarter, more flexible library. Instead of rigid fact cards, it organizes information into three layers, like a well-organized filing system:

The Entity Layer (The Index Cards): These are the main characters or things (e.g., "Paul McCartney," "Germany"). They act as the "doors" or gateways into the library.
The Proposition Layer (The Atomic Facts): This is the secret sauce. Instead of breaking sentences into rigid "Subject-Verb-Object" triples, GRASP breaks them into atomic propositions—small, self-contained, natural-language sentences (e.g., "The Easter Hare was recorded in Germany in 1678").
- Why this matters: Think of a triple as a broken sentence that loses meaning. A proposition is a complete, clear thought. It's easier for the AI to understand and match with a question.
The Passage Layer (The Full Books): These are the original source documents. Once the detective finds the right "Proposition" (clue), they pull the full "Passage" (the book chapter) to get the full context for the final answer.

How GRASP Solves a Mystery (The Workflow)

1. The Planner (The Strategist)
Instead of blindly searching, GRASP has a "Planner" agent. When you ask a complex question, the Planner breaks it down into a step-by-step to-do list.

Analogy: If you ask, "Who is the mother of the person who invented the lightbulb?", the Planner says: "Step 1: Find who invented the lightbulb. Step 2: Find the mother of that person." It creates a dependency map so the detective knows exactly what to look for next.

2. The Sub-Agents (The Field Agents)
GRASP doesn't send one giant brain to do all the work. It sends out small, specialized Sub-Agents for each step of the plan.

Efficiency: If a step is simple, it uses one agent. If a step is complex, it scales up. Crucially, each agent only keeps a "compact memory" of what it just found. It doesn't carry the weight of the entire conversation history, which saves a massive amount of "token" budget (money/compute).

3. The Search (The Detective Work)
When a Sub-Agent needs a clue:

It looks at the Proposition Layer first. Because these are clear, natural sentences, the AI can find the right clues very quickly using a "hybrid search" (looking for both exact words and similar meanings).
It uses a "RankVote" system. Imagine the agent finds 50 clues. Instead of reading all 50 books, it looks at which clues are most relevant and "votes" for the specific book chapters (Passages) that contain those clues. This ensures it only reads the most important pages.

4. The Synthesis (The Final Report)
Once all the Sub-Agents finish their steps, a final module stitches all the answers together into one coherent story.

The Results: Faster, Cheaper, Smarter

The authors tested GRASP on three major "mystery datasets" (MuSiQue, 2Wiki, and HotpotQA).

Accuracy: GRASP solved the mysteries more accurately than previous top-tier systems.
Efficiency: It used 30% to 50% fewer tokens (computational resources) than the next best methods.
- Analogy: If the old system spent $100 to solve a mystery, GRASP solved it for $50 while getting a better result.

A New Way to Measure Success: "Success Economy"

The paper introduces a new metric called Success Economy.

The Concept: It's not enough to just get the right answer; you have to ask, "How much did it cost to get that answer?"
The Twist: It weighs the cost by how hard the question was. Solving a hard question for cheap is worth more than solving an easy question for cheap. GRASP wins this metric because it gets the hard answers right without wasting resources.

Summary

GRASP is a detective system that:

Plans its route before moving.
Uses atomic, natural-language facts (propositions) instead of rigid, broken data structures.
Sends out small, focused agents that don't carry heavy baggage.
Votes for the best evidence to avoid reading unnecessary text.

The result is a system that is not only smarter at solving complex, multi-step puzzles but also significantly cheaper and more efficient to run.

Technical Summary: GRASP (Graph Agentic Search over Propositions)

Problem Statement

Multi-hop question answering (QA) requires models to iteratively gather evidence to resolve dependencies that semantic similarity alone cannot address. While recent agentic retrieval systems improve accuracy by granting language models (LLMs) autonomy to search and reason, they face a critical bottleneck: token efficiency.

Existing graph-based approaches, such as HippoRAG and GeAR, utilize knowledge graphs (KGs) constructed from relational triples (subject-relation-object) to enable structured traversal. However, this introduces significant costs:

Indexing Cost: Extracting and constructing triple-based KGs is computationally expensive and often unreliable, sometimes degrading retrieval quality below naive RAG.
Inference Cost: Agentic systems often suffer from compounding token usage due to repeated LLM calls, expanding context windows, and redundant traversal by parallel agents.

Current methods fail to jointly optimize for high accuracy and minimal token usage across both indexing and inference phases.

Methodology: GRASP

The authors propose GRASP (Graph Agentic Search over Propositions), an agentic retrieval system designed to optimize both QA accuracy and token efficiency. GRASP operates through three core components:

1. Three-Layer Hierarchical Graph Construction

Unlike triple-based KGs, GRASP constructs a graph $G = (V_E, V_P, V_D, E)$ with three distinct layers:

Entity Layer ( $V_E$ ): Typed entities (e.g., "Person," "Location") extracted from text. These serve as targeted gateways for traversal.
Proposition Layer ( $V_P$ ): The core retrieval unit. Instead of atomic triples, the system extracts atomic, self-contained natural language propositions (e.g., "The Easter Hare was recorded in south-west Germany in 1678").
Passage Layer ( $V_D$ ): The original source documents linked to their constituent propositions.

Extraction Process: Entities and propositions are extracted jointly in a single LLM call. Entities are linked to their source propositions via index references, forming the graph edges. This avoids the lossy compression of context into relational triples.

2. Planning-Based Inference Pipeline

GRASP decomposes complex multi-hop questions into dependency-aware plans:

Planner: A module generates a natural language reasoning outline and an ordered sequence of sub-questions. Crucially, it uses numeric placeholders (e.g., #1) to explicitly reference answers from prior sub-questions, mirroring the dependency structure of datasets like MuSiQue.
Sub-Agent Execution: Each sub-question is handled by an independent sub-agent. The agent maintains a compact observation state ( $O_i$ $O_{i}$ ) rather than a full conversation history, bounding context growth.
- Hybrid Search: The agent reformulates the sub-question into a declarative search statement and a keyword list. It performs hybrid search (dense vector + BM25) over the proposition layer to retrieve candidate entities.
- RankVote Scoring: Retrieved propositions are aggregated to candidate entities. For passage retrieval, the system uses RankVote, a reciprocal-rank voting mechanism that scores passages based on the ranks of their constituent propositions, prioritizing highly relevant context.
- Iterative Refinement: The agent evaluates if evidence is sufficient. If not, it rewrites the search statement and restarts traversal (up to a limit), avoiding redundant re-reading of evidence.

3. Success Economy Metric

The paper introduces Success Economy ( $C_w$ ), a metric inspired by information theory to evaluate efficiency. It amortizes the total token cost over difficulty-weighted correct answers:
$C_w = \frac{\sum T_i}{\sum w_i \cdot \mathbb{1}[EM_i = 1]}$
where $w_i = -\log_2(r_i)$ is the surprisal (self-information) of a correct answer, estimated by prompting the base LLM multiple times. This penalizes token waste and rewards solving difficult questions efficiently.

Key Contributions

GRASP System: A graph-enhanced agentic retrieval system that jointly optimizes accuracy and token efficiency, evaluated competitively across both open-retrieval and extended-context settings.
Proposition-Based Indexing: A novel three-layer hierarchical graph using propositions as the core retrieval unit. The authors demonstrate this achieves higher passage recall than triple-based graphs (HippoRAG2) while using 69% fewer indexing tokens.
Compartmentalized Inference: A planning-based pipeline with isolated sub-agents that compartmentalize context both across hops and within individual agent execution, preventing unbounded context growth.
Success Economy: A new evaluation metric that advocates for efficiency-aware assessment in agentic QA, moving beyond accuracy-only benchmarks.

Experimental Results

GRASP was evaluated on MuSiQue, 2WikiMultihopQA, and HotpotQA under two settings:

Open-Corpus Retrieval Setting

Performance: GRASP achieved the highest Exact Match (EM), F1, and Judge scores on MuSiQue and 2Wiki, outperforming IRCoT+HippoRAG2.
Efficiency: It used 40–50% fewer tokens than IRCoT+HippoRAG2 while achieving superior accuracy. On HotpotQA, while IRCoT+HippoRAG2 had slightly higher accuracy, it did so at more than 2x the token cost.
Retrieval Quality: In simulated agentic retrieval, GRASP achieved a recall of 0.904 compared to HippoRAG2's 0.817, validating propositions as a superior retrieval unit.

Extended Context (LongBench) Setting

Performance: GRASP led in EM and F1 across all three datasets. On 2Wiki, it improved EM by 12 points over GraphReader while using roughly 70% of the token cost.
Efficiency: GRASP used 30% fewer tokens than the next most accurate method (GraphReader) while maintaining competitive or superior Judge scores.
Ablation: Removing the proposition graph or the entity selection layer significantly degraded performance or increased token usage, confirming the necessity of the three-layer structure.

Significance and Claims

The paper claims that GRASP sits on the Pareto frontier for accuracy-to-cost tradeoffs in multi-hop QA. By treating token efficiency as a first-class design objective alongside accuracy, GRASP addresses the fundamental tension in agentic systems where reasoning depth typically leads to exponential token growth.

The authors emphasize that:

Propositions are superior to triples: They preserve semantic nuance lost in triple extraction and serve as more discriminative units for embedding-based retrieval.
Structured decomposition is vital: Planning-based decomposition paired with structured retrieval (the graph) is more effective than interleaving retrieval with chain-of-thought alone.
Efficiency is a standard requirement: The introduction of "Success Economy" advocates for the community to adopt efficiency-aware evaluation as a standard practice, acknowledging that inference cost scales directly with reasoning complexity.

The work suggests that future improvements could focus on refining the planner's decomposition accuracy (currently a bottleneck for 3- and 4-hop questions) via supervised fine-tuning or reinforcement learning, but the current architecture already demonstrates a significant leap in balancing performance and cost.