2025-11-20T17:34:15.321910

ReMindRAG: Low-Cost LLM-Guided Knowledge Graph Traversal for Efficient RAG

Hu, Zhu, Tang et al.
Knowledge graphs (KGs), with their structured representation capabilities, offer promising avenue for enhancing Retrieval Augmented Generation (RAG) systems, leading to the development of KG-RAG systems. Nevertheless, existing methods often struggle to achieve effective synergy between system effectiveness and cost efficiency, leading to neither unsatisfying performance nor excessive LLM prompt tokens and inference time. To this end, this paper proposes REMINDRAG, which employs an LLM-guided graph traversal featuring node exploration, node exploitation, and, most notably, memory replay, to improve both system effectiveness and cost efficiency. Specifically, REMINDRAG memorizes traversal experience within KG edge embeddings, mirroring the way LLMs "memorize" world knowledge within their parameters, but in a train-free manner. We theoretically and experimentally confirm the effectiveness of REMINDRAG, demonstrating its superiority over existing baselines across various benchmark datasets and LLM backbones. Our code is available at https://github.com/kilgrims/ReMindRAG.
academic

ReMindRAG: Low-Cost LLM-Guided Knowledge Graph Traversal for Efficient RAG

基本信息

  • 论文ID: 2510.13193
  • 标题: ReMindRAG: Low-Cost LLM-Guided Knowledge Graph Traversal for Efficient RAG
  • 作者: Yikuan Hu, Jifeng Zhu, Lanrui Tang, Chen Huang
  • 分类: cs.IR (Information Retrieval)
  • 发表会议: 39th Conference on Neural Information Processing Systems (NeurIPS 2025)
  • 论文链接: https://arxiv.org/abs/2510.13193
  • 代码链接: https://github.com/kilgrims/ReMindRAG

摘要

知识图谱(KG)凭借其结构化表示能力，为增强检索增强生成(RAG)系统提供了有前途的途径，促进了KG-RAG系统的发展。然而，现有方法往往难以在系统有效性和成本效率之间实现有效协同，导致性能不佳或LLM提示令牌和推理时间过多。为此，本文提出了REMINDRAG，采用LLM引导的图遍历，包含节点探索、节点利用，以及最重要的记忆重放机制，以提高系统有效性和成本效率。具体而言，REMINDRAG在KG边嵌入中记忆遍历经验，类似于LLM在其参数中"记忆"世界知识，但采用无训练方式。我们从理论和实验两方面确认了REMINDRAG的有效性，证明其在各种基准数据集和LLM骨干网络上优于现有基线。

研究背景与动机

问题定义

传统RAG方法主要依赖密集向量检索来识别相关文本段落，但在需要多跳推理或捕获长程依赖的复杂任务中表现有限。知识图谱以其结构化的实体和关系表示，为解决这一问题提供了新途径。

现有方法的局限性

  1. 传统图搜索算法：如PageRank和GNN方法，难以捕获图中的细致语义关系，导致系统有效性不足
  2. LLM引导的图遍历方法：虽然表现出色，但需要大量LLM调用，显著增加了成本和推理时间
  3. 效率与效果的权衡：现有KG-RAG系统难以在系统有效性和成本效率之间找到有效平衡

研究动机

本文旨在解决KG-RAG系统中系统有效性与成本效率的协同优化问题，这是实际部署和可扩展性的主要挑战。

核心贡献

  1. 识别关键挑战：明确指出了KG-RAG系统中系统有效性与成本效率协同优化的挑战
  2. 提出REMINDRAG框架：采用LLM引导的KG遍历，包含节点探索、节点利用和记忆重放机制
  3. 理论分析：从理论上证明了图遍历记忆重放的有效性
  4. 实验验证：在多个基准数据集和LLM骨干网络上验证了REMINDRAG的优越性

方法详解

任务定义

给定非结构化文本文档和用户查询，目标是构建知识图谱并通过高效的图遍历机制检索相关信息，生成准确的答案，同时最小化LLM调用成本。

模型架构

1. 知识图谱构建

REMINDRAG构建异构知识图谱，包含：

  • 实体节点：从文本中提取的命名实体
  • 锚点节点：存储文本块标题
  • 文本块集合：分割后的原始文档
  • 关系连接：实体-关系-实体三元组和上下文骨架网络

2. LLM引导的知识图谱遍历

节点探索策略：

  • 优先探索可能导向答案的潜在节点
  • 在每次迭代中，LLM评估子图S中的所有节点，选择最可能导向答案的目标节点a

节点利用策略：

  • 专注于利用先前探索的节点，沿这些节点扩展路径
  • 给定选定节点a，LLM从其邻接节点集合Sa中选择最优扩展节点p

3. 记忆重放机制

记忆内容：

  • 有效路径：导向正确答案的路径（正强化）
  • 无效路径：未导向答案的路径（负强化）

记忆方法： 使用闭式方程更新边嵌入：

权重函数：δ(x) = (2/π)cos(π||x||₂/2)
增强有效路径：v̂ = v + δ(v) · q/||q||₂
惩罚无效路径：v̂ = v - δ(v·q/||q||₂) · v·q/||q||₂

快速唤醒与阻尼更新：

  • 快速唤醒：当边嵌入v的范数较小时，δ函数产生大幅方向更新
  • 阻尼更新：当边嵌入v范数较大时，δ函数仅产生小幅更新，保持稳定性

技术创新点

  1. 无训练记忆机制：通过边嵌入记忆遍历经验，无需额外训练
  2. 平衡探索与利用：结合节点探索和利用策略，实现全局和局部最优搜索
  3. 自适应权重更新：基于向量范数的自适应更新策略，兼顾快速学习和长期稳定性

实验设置

数据集

  1. 长依赖QA：LooGLE数据集，测试长程语义检索能力
  2. 多跳QA：HotpotQA数据集，评估多步推理能力
  3. 简单QA：LooGLE短依赖QA，测试直接关联信息提取能力

评价指标

  1. 有效性评估：使用GPT-4o作为LLM判断器，评估答案准确性
  2. 成本效率评估：遍历过程中每个查询平均消耗的LLM令牌数

对比方法

  1. 传统检索方法：BM25、NaiveRAG
  2. 使用图搜索算法的KG-RAG系统：GraphRAG、LightRAG、HippoRAG2
  3. LLM引导的KG-RAG系统：Plan-on-Graph

实现细节

  • LLM骨干：GPT-4o-mini、Deepseek-V3
  • 嵌入模型：nomic-ai/nomic-embed-text-v2-moe
  • 文本分块：750令牌长度
  • 关键参数：α=0.1（节点相关权重），λ=0.55（强连接阈值）

实验结果

主要结果

QA类型GPT-4o-miniDeepseek-V3
长依赖QA57.04%59.73%
多跳QA74.22%79.38%
简单QA76.67%77.01%

REMINDRAG在所有任务上均显著优于基线方法：

  • 长依赖QA：平均提升12.08%
  • 多跳QA：平均提升10.31%
  • 简单QA：平均提升4.66%

成本效率分析

设置类型准确率令牌消耗成本降低
无记忆57.04%14.91K-
1轮记忆56.48%9.68K35.1%
2轮记忆58.01%7.55K49.4%
3轮记忆60.31%6.71K55.0%

多轮记忆后，REMINDRAG实现平均58.8%的令牌消耗减少。

消融实验

上下文骨架网络的影响：

  • 移除上下文骨架网络后，长依赖QA性能从57.04%降至51.01%
  • 验证了上下文信息捕获的重要性

跳数设置的影响：

  • 随着最大跳数增加，系统性能单调递增
  • 更大跳数使节点能访问更广泛的邻域信息

案例分析

自我纠错能力：

  • 初次错误答案后，系统能基于记忆规则惩罚无关节点
  • 后续查询中切换到记忆优化的子图，实现错误自我纠正

记忆稳定性：

  • 在复杂多轮记忆设置下保持稳定性能
  • 交替处理异构数据集时展现鲁棒性

理论分析

记忆容量定理

对于具有一定语义相似性的查询集合，当嵌入维度d足够大时，边嵌入能够有效记忆查询信息，条件为：

θ ≤ lim[d→∞] [2 arcsin(√(1/2 sin(arccos(λ))))]

其中θ是查询嵌入对之间的最大角度，λ是强连接阈值。

理论保证

  • λ的理论上界为0.775，与现有语义相似性阈值0.6的研究一致
  • 当嵌入维度超过100时，理论近似在实践中具有显著实用性

相关工作

KG-RAG系统发展

  1. 传统图搜索方法：PageRank、Random Walk、GNN等，难以捕获细致语义关系
  2. LLM引导方法：利用LLM的语义理解能力，但成本高昂
  3. 图剪枝与路径规划：现有优化方法效果有限

记忆重放机制

  • 借鉴强化学习中的记忆重放概念
  • 创新性地将记忆嵌入为图中的权重，而非显式样本回放

结论与讨论

主要结论

  1. REMINDRAG成功实现了系统有效性与成本效率的协同优化
  2. 记忆重放机制显著提升了后续查询的效率
  3. 自我纠错能力增强了系统的鲁棒性

局限性

  1. 初始图遍历成本：首次遍历仍需要多次LLM调用
  2. 大规模文档处理：构建知识图谱需要大量时间和计算资源
  3. 记忆容量限制：理论分析基于无限维度假设，实际应用中可能受限

未来方向

  1. 预训练记忆初始化：使用领域特定的FAQ预初始化模型记忆
  2. 分布式图构建：优化大规模文档的图构建效率
  3. 动态记忆管理：研究长期记忆的遗忘和更新机制

深度评价

优点

  1. 创新性强：首次提出无训练的图遍历记忆机制
  2. 理论扎实：提供了记忆容量的理论分析和保证
  3. 实验充分：多数据集、多骨干网络的全面评估
  4. 实用价值高：显著的性能提升和成本降低

不足

  1. 参数敏感性：多个超参数的设置可能影响性能
  2. 可扩展性问题：对于超大规模知识图谱的适用性未充分验证
  3. 记忆更新策略：简单的线性更新可能不适用于所有场景

影响力

  1. 学术贡献：为KG-RAG领域提供了新的优化思路
  2. 实际应用：在问答系统、信息检索等领域具有广泛应用前景
  3. 可复现性：提供开源代码，便于研究社区验证和扩展

适用场景

  1. 多轮对话系统：能够记忆历史交互，提升响应效率
  2. 领域特定问答：在特定领域内能够积累和利用遍历经验
  3. 成本敏感应用：对LLM调用成本有严格要求的场景

参考文献

本文引用了RAG、知识图谱、图神经网络等多个领域的重要工作，包括：

  • Lewis et al. (2020): Retrieval-augmented generation for knowledge-intensive NLP tasks
  • Edge et al. (2024): GraphRAG approach to query-focused summarization
  • Guo et al. (2024): LightRAG simple and fast retrieval-augmented generation
  • 等55篇相关文献

总体评价：REMINDRAG是一项高质量的研究工作，在KG-RAG领域提出了创新性的解决方案。该方法不仅在技术上有所突破，更重要的是解决了实际应用中的关键问题——效果与效率的平衡。理论分析严谨，实验设计合理，结果令人信服。虽然存在一些局限性，但其贡献显著，对推动KG-RAG技术的实用化具有重要意义。