Inference Scaled GraphRAG: Improving Multi Hop Question Answering on Knowledge Graphs
Travis Thompson, Seung-Hwan Lim, Paul Liu, Ruoying He, Dongkuan (DK) Xu · 2025
Read Inference Scaled GraphRAG: Improving Multi Hop Question Answering on Knowledge Graphs by Travis Thompson, Seung-Hwan Lim, Paul Liu, Ruoying He, Dongkuan (DK) Xu (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-2506-19967.txt.
Introduction
Travis Thompson and co-authors improve question answering over knowledge graphs in a 2025 paper. Language models reason well but lack direct access to structured facts. Standard retrieval hands them text passages, yet multi-step questions need chains of linked facts that flat retrieval misses. Graph-based retrieval helps, but often loses the links between nodes.
Their method, Inference-Scaled GraphRAG, spends more computing at answer time. One route deepens the step-by-step walk across the graph. Another runs several walks in parallel and takes a majority vote. Reasoning and graph calls alternate in a loop. On a standard benchmark, the method beat both plain graph retrieval and earlier traversal systems by wide margins. The authors present inference-time scaling as a practical, model-free upgrade.
Catalog record
| CREATOR | Travis Thompson, Seung-Hwan Lim, Paul Liu, Ruoying He, Dongkuan (DK) Xu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-19967
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Inference Scaled GraphRAG: Improving Multi Hop Question Answering on Knowledge Graphs Travis Thompson, Seung-Hwan Lim, Paul Liu, Ruoying He, Dongkuan (DK) Xu Abstract Large Language Models (LLMs) have achieved impressive capabilities in language understanding and generation, yet they continue to underperform on knowledge-intensive reasoning tasks due to limited access to structured context and multi-hop information. Retrieval-Augmented Generation (RAG) partially mitigates this by grounding generation in retrieved context, but conventional RAG and GraphRAG methods often fail to capture relational structure across nodes in knowledge graphs. We introduce Inference-Scaled GraphRAG , a novel framework that enhances LLM-based graph reasoning by applying inference-time compute scaling. Our method combines sequential scaling with deep chain-of-thought graph traversal, and parallel scaling with majority voting over sampled trajectories within an interleaved reasoning-execution loop. Experiments on the GRBench benchmark demonstrate that our approach significantly improves multi-hop question answering performance, achieving substantial gains over both traditional GraphRAG and prior graph traversal baselines. These findings suggest that inference-time scaling is a practical and architecture-agnostic solution for structured knowledge reasoning with LLMs. 1 Introduction Large Language Models (LLMs) [ 9 , 13 , 36 ] have shown remarkable capabilities in natural language understanding and generation, with performance gains primarily driven by scaling self-supervised pretraining [ 43 ] . However, despite these advances, LLMs continue to face challenges on knowledge-intensive reasoning tasks [ 44 ] , such as answering scientific or domain-specific questions [ 28 ] . These tasks require not only general reasoning abilities but also access to external sources of structured and unstructured information. To address this, Retrieval-Augmented Generation (RAG) [ 20 , 8 ] has emerged as a widely adopted framework that augments LLMs with access to external text corpora. By retrieving relevant passages and incorporating them as context, RAG improves factual grounding [ 19 ] and the quality of generated responses. Nonetheless, RAG suffers from a significant limitation: relevant information is often distributed across multiple text units, and flat retrieval methods struggle to identify and combine information effectively. GraphRAG [ 6 , 25 , 42 ] is a recent extension of RAG that introduces a knowledge graph as the retrieval backbone. Knowledge graphs provide a structured representation of entities and their relationships, enabling retrieval mechanisms to exploit relational dependencies and improve coherence in the retrieved context. By integrating graph-structured data, GraphRAG enhances recall of relevant information and enables more interpretable knowledge augmentation. Current GraphRAG implementations [ 15 , 8 , 32 ] often neglect structure context , treating graph nodes as individual context units ignoring the structural relationships between nodes and their local subgraph. This severely limits performance on tasks requiring synthesis of information across nodes. Effective utilization of knowledge graphs in RAG requires not only retrieval of relevant nodes but explicit traversal of the graph structure to reason across multiple hops. This is non-trivial for LLMs due to the graph size explosion problem , where the number of candidate nodes grows exponentially with traversal depth, overwhelming the context window [ 22 ] and degrading performance. To address this, we propose a method that applies inference scaling [ 33 , 37 , 40 , 26 ] to the problem of graph traversal. Inference scaling, popularized by recent models such as OpenAI o1 [ 24 ] and DeepSeek R1 [ 3 ] , refers to allocating more computational effort at inference time to improve response quality. Our approach leverages both sequential scaling [ 23 ] , where LLMs reason step-by-step in a chain-of-thought [ 31 ] manner, and parallel scaling [ 1 , 30 ] , where multiple candidate traversals are generated and aggregated via majority voting or best-of- N selection [ 16 ] . Concretely, we enable LLMs to perform structured reasoning over knowledge graphs via interleaved thought-action execution based on the structure of Graph-CoT [ 15 ] . Traversal is decomposed into three stages: (1) Reasoning , where the LLM plans the next step based on the current and previous thoughts; (2) Interaction , where the LLM formulates graph queries (e.g., neighbor lookups); and (3) Execution , where these queries are performed and results are fed back into the model. This loop enables the model to progressively gather and synthesize multi-hop evidence from the graph. We empirically evaluate our method on the GRBench [ 15 ] dataset and observe consistent improvements across multiple model architectures and scales. Our approach surpasses traditional GraphRAG by 64.7% , and exceeds prior graph traversal methods by 30.3% . Furthermore, our method is able to correctly answer 31.44% of difficult multi-hop questions, compared to just 15.26% for baselines. These results demonstrate that Inference-Scaled GraphRAG not only enhances retrieval and reasoning over structured knowledge but also offers a general and architecture-agnostic framework for improving LLM performance on knowledge-intensive tasks. (a) F1 Scores (b) RougeL Scores Figure 1 : Performance of Inference Scaled GraphRAG under varying inference step counts and model backbones including Llama3.1-8B-Instruct, Mixtral-8x7B-Instruct, and Qwen3-32b. (a) F1 score increases consistently with more inference steps across all model configurations. (b) RougeL scores show a similar trend, reflecting improvements in both symbolic and semantic alignment with ground-truth answers. 2 Preliminaries 2.1 Knowledge graphs We denote a knowledge graph as G=(V,E) , where V is the set of nodes (entities) and E the set of edges (relations). Each node v_{i}\in V is associated with feature information X_{v_{i}} , that may include textual content or metadata. For instance, in an academic domain-specific graph, nodes might represent research papers, with features including authorship, publication venue, or abstract text, while edges capture relationships such as co-authorship or citation links. 2.2 Retrieval-augmented generation (RAG) Large Language Models (LLMs) demonstrate strong generative capabilities but often struggle with reasoning over factual knowledge, especially in specialized domains. Retrieval Augmented Generation (RAG) [ 20 ] addresses this limitation by incorporating external information retrieval into the generation pipeline. Rather than relying solely on parametric memory, RAG retrieves relevant documents from an external knowledge source and conditions the model’s generation on this context. RAG implementations typically use dense vector similarity [ 7 , 4 ] to retrieve semantically related documents. While this is effective for recalling isolated facts, it struggles with structured or multi-hop reasoning, particularly when relevant information is distributed across multiple sources [ 27 ] . GraphRAG [ 6 ] extends RAG by using a knowledge graph as the retrieval backbone, allowing the model to leverage the explicit relational structure among entities to guide retrieval and enhance coherence in reasoning. 2.3 Inference-time scaling Traditionally, model performance improvements have been achieved by scaling pretraining [ 2 , 12 ] . Recent studies have shown that allocating additional compute at test time [ 29 , 21 ] can significantly improve performance on complex reasoning tasks. Inference-time scaling provides an orthogonal axis for performance improvement without modifying the model architecture. Two primary paradigms of inference scaling are employed: • Sequential Scaling: The model performs step by step reasoning, with each inference step conditioned on the outputs from previous steps [ 23 ] . This enables the accumulation of intermediate insights, supporting deeper reasoning and iterative refinement. • Parallel Scaling: Multiple responses are generated independently [ 1 ] in parallel, and a final output is selected using aggregation strategies such as majority voting or best-of-N. This method