GraphRunner: A Multi-Stage Framework for Efficient and Accurate Graph-Based Retrieval

Savini Kashmira, Jayanaka L. Dantanarayana, Krisztián Flautner, Lingjia Tang, Jason Mars · 2025

Read GraphRunner: A Multi-Stage Framework for Efficient and Accurate Graph-Based Retrieval by Savini Kashmira, Jayanaka L. Dantanarayana, Krisztián Flautner, Lingjia Tang, Jason Mars (2025) 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-2507-08945.txt.

Introduction

Kashmira and co-authors present in 2025 a new way to search linked data, such as knowledge graphs, for answers to a query. Plain text search tools cope poorly when facts are tied by links, and step by step search led by a large language model can go astray. Their system, GraphRunner, works in three clear stages.

First it drafts a full search plan, then it checks that plan against the graph before it runs. The check catches false steps early, before they can spoil the result. Broad moves let it cross many links in one step. On a shared test set, the system beat past methods by wide margins while using less effort.

Catalog record

CREATORSavini Kashmira, Jayanaka L. Dantanarayana, Krisztián Flautner, Lingjia Tang, Jason Mars
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-08945

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

GraphRunner: A Multi-Stage Framework for Efficient and Accurate Graph-Based Retrieval Savini Kashmira, Jayanaka L. Dantanarayana, Krisztián Flautner, Lingjia Tang, Jason Mars Abstract Conventional Retrieval Augmented Generation (RAG) approaches are common in text-based applications. However, they struggle with structured, interconnected datasets like knowledge graphs, where understanding underlying relationships is crucial for accurate retrieval. A common direction in graph-based retrieval employs iterative, rule-based traversal guided by Large Language Models (LLMs). Such existing iterative methods typically combine reasoning with single hop traversal at each step, making them vulnerable to LLM reasoning errors and hallucinations that ultimately hinder the retrieval of relevant information. To address these limitations, we propose GraphRunner , a novel graph-based retrieval framework that operates in three distinct stages: planning, verification, and execution. This introduces high-level traversal actions that enable multi-hop exploration in a single step. It also generates a holistic traversal plan, which is verified against the graph structure and pre-defined traversal actions, reducing reasoning errors and detecting hallucinations before execution. Our evaluation using the GRBENCH dataset shows that GraphRunner consistently outperforms existing approaches, achieving 10-50% performance improvements over the strongest baseline while reducing inference cost by 3.0-12.9× and response generation time by 2.5-7.1×, making it significantly more robust and efficient for graph-based retrieval tasks. 1 Introduction Large Language Models (LLMs) excel at understanding context and generating coherent text Petroni et al. 2019 but are prone to hallucinations, especially when lacking relevant information Perković et al. 2024 . To enhance the factuality and reliability of LLM outputs, Retrieval Augmented Generation (RAG) has emerged as state-of-the-art technique for external knowledge integration, substantially improving LLM performance Lewis et al. 2020 ; Gao et al. 2024 . It stores chunked documents in a vector database and retrieves the most relevant chunks based on query-chunk semantic similarity. While RAG excels with unstructured text, it faces challenges with structured, interconnected datasets common in real-world scenarios. For instance, medical knowledge is inherently interlinked, diseases are associated with symptoms, drugs have side effects and treatments depend on anatomical factors. These relationships can be formally represented as knowledge graphs, where nodes encapsulate rich textual content and edges denote meaningful relationships. In such graph-based contexts, traditional RAG approaches fail to utilize structural connections effectively. These methods typically embed individual nodes and retrieve based only on vector similarity with the query, overlooking valuable relational information inherent in graphs which contain crucial context for answering complex queries. To improve the retrieval from structured datasets, one of the prior approaches Ye et al. 2024 leverages knowledge graphs by retrieving relevant nodes and fetching their single or multi-hop neighbors to form a subgraph, which is then linearized into a text sequence and passed to the LLM as context. While increasing the hop count can capture more relational context needed for complex queries, it can also lead to exponentially growing subgraphs that exceed the LLM’s context window and include irrelevant information, consequently degrading performance Liu et al. 2024a . To achieve better retrieval performance, rule-based graph traversal techniques are better suited than feeding entire subgraphs as context to LLMs. Existing frameworks Jiang et al. 2023a ; Jin et al. 2024 define traversal rules and leverage reasoning capabilities of LLMs to iteratively explore the graph. At each step, LLMs reason over the context, select the appropriate rule, and apply it. However, these existing rule-based traversal techniques have several limitations. 1. Inefficient Graph Traversal Capabilities: Since each iteration step only considers the immediate neighbors of the nodes retrieved in previous step, traversal is limited to single-hop exploration. Also, when identifying shared neighbors among multiple nodes, these frameworks retrieves all neighbors in one step and computes their intersection using LLMs in the next. As a result, they require multiple iteration steps for tasks that could be efficiently resolved using the graph structure effectively in fewer steps, leading to inefficiency. Relying on LLMs for such intermediate computations also increases the risk of LLM reasoning errors, reducing overall accuracy. 2. Step-by-Step Reasoning: These frameworks combine traversal action planning and its execution into a single iterative step, requiring multiple reasoning steps to reach the final answer. Since each subsequent step is determined by LLMs based on previous reasoning steps and outputs, the amount of accumulated information grows with each step. This leads to higher token usage, reducing overall efficiency. Additionally, there is a risk of exceeding the model’s context window, hindering its ability to produce a final answer. 3. Undetected Hallucinations Before Execution: LLMs hallucinate incorrect reasoning steps, such as suggesting traversal actions incompatible with pre-defined rules or referencing non-existent node/ edge types. While we can sometimes identify them in the next reasoning step based on the previous execution feedback, the system often fails to detect them, leading to incorrect answers. Even when identified, corrections require longer traversals. Such hallucinations cannot be detected before execution in these frameworks. To address these limitations, we propose GraphRunner , a novel three-stage graph-based retrieval framework that leverages LLMs for planning traversal steps based on pre-defined traversal actions, followed by verification and execution when the graph structure is defined. GraphRunner introduces high-level traversal actions that perform complex operations such as multi hop traversal and shared neighbor identification in a single step, reducing LLM reasoning errors by eliminating LLM reliance, improving efficiency and accuracy. Additionally, unlike iterative approaches, GraphRunner separates planning and execution into distinct stages, avoiding dependence on previous outputs to plan the next traversal action. Planning stage generates a holistic traversal plan in a single LLM inference, followed by verification of the plan’s compatibility with the graph structure and defined traversal actions before execution. This detects hallucinations beforehand and avoids unnecessary long traversals, improving accuracy and efficiency. We conduct experiments on GRBENCH Jin et al. 2024 dataset to demonstrate the effectiveness of GraphRunner, analyzing its performance against several baselines. Our evaluation results demonstrate that GraphRunner significantly outperforms existing approaches in accuracy when answering diverse query types with varying levels of complexity, while also achieving lower inference cost and response generation speedup. The main contributions of our paper are as follows. 1. A novel non-iterative framework, GraphRunner, that separates planning from execution through verified traversal strategies. It introduces high-level traversal actions enabling complex operations in a single step, and holistic traversal planning with pre-execution verification against the graph structure and pre-defined actions. 2. A comprehensive evaluation against several baselines, using the GRBENCH multi-domain benchmark dataset. Results show that GraphRunner consistently outperforms all baselines across all domains, achieving 10-50% improvements in GPT4Score over the strongest baseline, while simultaneously reducing inference costs by 3.0-12.9× and response generation time by 2.5-7.1×, demonstrating higher accuracy and efficiency for graph-based retrieval tasks. Figure 1: GraphRunner Framework - Given a question, a holistic traversal plan is generated by the Traversal Planning module and verified against the graph and possible traversal actions in the Traversal Plan Verification Module. Once verified, the plan is executed to extract relevant information from the graph by the GraphRunner Agent, which is then used as context to answer the question. 2 Preliminaries This section formally introduces knowledge graphs and the mathematical representations underlying our implementations. 2.1 Knowledge Graphs A knowledge graph is a structured representation of information that captures entities, their attributes, and the relationships between them. In our context, the knowledge graph is constructed with

Read the complete text