Inference Scaled GraphRAG: Improving Multi Hop Question Answering on Knowledge Graphs

Travis Thompson, Seung-Hwan Lim, Paul Liu, Ruoying He, Dongkuan XuarXiv 2025 · DOI · arXiv

Introduction

Large Language Models (LLMs) frequently struggle with complex, multi-hop questions that require navigating structured knowledge. While standard Retrieval-Augmented Generation (RAG) provides relevant text snippets, it often fails to connect disparate entities across a network. Inference Scaled GraphRAG addresses this by treating knowledge graph (KG) traversal as a scalable search problem, significantly boosting performance without additional training.

Methodology: Scaling Inference-Time Compute

The framework introduces a Reasoning-Interaction-Execution loop that applies inference-time compute scaling to graph traversal. This approach allows the model more "time to think" during the answering process through two primary mechanisms:

  1. Sequential Scaling: The model is permitted a high budget of sequential steps (up to 50). Using a deep Chain-of-Thought approach, it plans and executes actions such as RetrieveNode, NodeFeature, and NeighborCheck.
  2. Parallel Scaling: To ensure robustness, the system generates multiple candidate actions in parallel at each step. Majority voting is then used to select the most consistent action, effectively filtering out random reasoning errors.
The Inference Scaled GraphRAG architecture featuring an interleaved Reasoning-Interaction-Execution loop.

This architecture-agnostic method works with off-the-shelf models like Llama 3.1, Mixtral, and Qwen, leveraging their inherent reasoning capabilities through agentic interaction with the KG.

Experimental Evaluation

The researchers evaluated the framework using GRBench, a benchmark covering six diverse domains: Academic, Amazon, DBLP, Biomedical, Goodreads, and Legal. The dataset includes questions ranging from "Easy" (1-hop) to "Hard" (inductive or abstract reasoning), providing a rigorous test for multi-hop navigation.

Results and Discussion: The Scaling Power of Compute

The most significant finding is that accuracy scales predictably with increased inference compute. By increasing the budget of steps and votes, the system can trade latency for precision, similar to recent advancements in mathematical reasoning models.

Scaling performance (F1 and ROUGE-L) across different LLM architectures as inference steps increase.

Key performance highlights include:

  • Superior Accuracy: Inference Scaled GraphRAG outperformed standard GraphRAG by 64.7% and surpassed existing traversal methods like Graph-CoT by 30.3%.
  • Multi-Hop Success: On the most difficult questions, performance more than doubled, increasing from a 15.26% success rate to 31.44%.
  • Model-Specific Gains: While all models improved, Qwen3-32B showed the most dramatic gains, suggesting that a model's reasoning ceiling influences how much it can benefit from extra compute.

Conclusion and Future Work

Inference Scaled GraphRAG demonstrates that complex graph reasoning can be solved through search and scaling rather than just model size or fine-tuning. Future research will focus on replacing simple majority voting with external verifiers to improve path selection and using reinforcement learning to optimize traversal strategies. While computationally intensive, the framework provides a clear path toward more reliable and structured RAG systems.

Summary updated

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
BibTeX
@misc{thompson2025inference,
  author = {Travis Thompson and Seung-Hwan Lim and Paul Liu and Ruoying He and Dongkuan Xu},
  title = {{Inference Scaled GraphRAG: Improving Multi Hop Question Answering on Knowledge Graphs}},
  year = {2025},
  eprint = {2506.19967},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.19967},
}
Figure