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

📄 arXiv: 2507.08945v1 📥 PDF

作者: Savini Kashmira, Jayanaka L. Dantanarayana, Krisztián Flautner, Lingjia Tang, Jason Mars

分类: cs.IR, cs.AI

发布日期: 2025-07-11

💡 一句话要点

GraphRunner：一种高效准确的图检索多阶段框架，解决LLM推理错误和幻觉问题。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 图检索 知识图谱 大型语言模型 检索增强生成 多阶段框架

📋 核心要点

  1. 现有图检索方法依赖LLM引导的迭代单跳遍历，易受LLM推理错误和幻觉的影响，导致检索不准确。
  2. GraphRunner框架通过规划、验证和执行三个阶段，引入多跳探索和全局验证机制，减少LLM的推理错误和幻觉。
  3. 实验表明，GraphRunner在GRBench数据集上优于现有方法，性能提升10-50%，推理成本降低3.0-12.9倍。

📝 摘要（中文）

传统检索增强生成（RAG）方法在基于文本的应用中很常见。然而，它们在知识图谱等结构化、互连的数据集中表现不佳，因为理解底层关系对于准确检索至关重要。一种常见的图检索方法采用由大型语言模型（LLM）引导的迭代、基于规则的遍历。这种现有的迭代方法通常在每个步骤中将推理与单跳遍历相结合，容易受到LLM推理错误和幻觉的影响，最终阻碍相关信息的检索。为了解决这些限制，我们提出了GraphRunner，这是一种新颖的基于图的检索框架，它在三个不同的阶段运行：规划、验证和执行。这引入了高级遍历动作，可以在单个步骤中实现多跳探索。它还生成一个整体遍历计划，该计划根据图结构和预定义的遍历动作进行验证，从而减少推理错误并在执行前检测到幻觉。GraphRunner通过验证显著减少了LLM推理错误并检测到幻觉。我们使用GRBench数据集进行的评估表明，GraphRunner始终优于现有方法，在最强的基线上实现了10-50%的性能提升，同时将推理成本降低了3.0-12.9倍，响应生成时间降低了2.5-7.1倍，使其对于基于图的检索任务更加稳健和高效。

🔬 方法详解

问题定义：现有基于图的检索方法，特别是那些依赖于大型语言模型（LLM）进行迭代遍历的方法，容易受到LLM推理错误和幻觉的影响。这些方法通常在每一步执行单跳遍历，并将推理与遍历紧密结合，使得LLM的错误判断会直接影响检索路径，最终导致检索结果不准确。因此，如何减少LLM在图检索过程中的推理错误和幻觉，是本文要解决的核心问题。

核心思路：GraphRunner的核心思路是将图检索过程分解为三个独立的阶段：规划、验证和执行。规划阶段生成一个全局的遍历计划，验证阶段对该计划进行结构化验证，执行阶段则按照验证后的计划进行多跳遍历。这种分离的设计允许在执行前检测和纠正LLM的错误，从而提高检索的准确性和鲁棒性。

技术框架：GraphRunner框架包含三个主要阶段： 1. 规划阶段：利用LLM生成一个高层次的遍历计划，该计划描述了从起始节点到目标节点的完整路径，包括需要访问的节点类型和关系类型。 2. 验证阶段：将规划阶段生成的遍历计划与实际的图结构进行比对，检查计划的可行性和一致性。如果发现错误或不一致，则对计划进行修正或重新生成。 3. 执行阶段：按照验证后的遍历计划，执行多跳遍历，从图中检索相关信息。

关键创新：GraphRunner的关键创新在于其多阶段的设计和验证机制。与传统的单步推理和遍历方法不同，GraphRunner将推理和执行分离，并通过验证阶段来减少LLM的推理错误和幻觉。此外，GraphRunner引入了高级遍历动作，支持多跳探索，从而提高了检索效率。

关键设计：GraphRunner的关键设计包括： 1. 高级遍历动作：定义了一组高级的遍历动作，例如“查找与当前节点具有特定关系的节点”或“查找满足特定属性的节点”。这些动作允许在单个步骤中执行多跳遍历。 2. 验证规则：定义了一组验证规则，用于检查遍历计划的可行性和一致性。这些规则基于图的结构和预定义的约束条件。 3. 错误处理机制：设计了一套错误处理机制，用于在验证阶段发现错误时进行修正或重新生成遍历计划。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

GraphRunner在GRBench数据集上进行了评估，实验结果表明，GraphRunner consistently outperforms existing approaches, achieving 10-50% performance improvements over the strongest baseline while reducing inference cost by 3.0-12.9x and response generation time by 2.5-7.1x。这些结果表明，GraphRunner在提高图检索的准确性和效率方面具有显著优势。

🎯 应用场景

GraphRunner可应用于各种需要从知识图谱中检索信息的场景，例如问答系统、推荐系统、智能助手等。通过提高图检索的准确性和效率，GraphRunner可以帮助用户更有效地获取所需信息，并提升相关应用的性能和用户体验。未来，GraphRunner可以进一步扩展到更复杂的图结构和更广泛的应用领域。

📄 摘要（原文）

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. GraphRunner significantly reduces LLM reasoning errors and detects hallucinations through validation. 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.9x and response generation time by 2.5-7.1x, making it significantly more robust and efficient for graph-based retrieval tasks.