Explore-on-Graph: Incentivizing Autonomous Exploration of LLMs on Knowledge Graphs¶
会议: ICLR 2026
arXiv: 2602.21728
代码: 有
领域: 图学习
关键词: 知识图谱问答, 自主探索, 强化学习, 路径精炼奖励, GRPO
一句话总结¶
提出 Explore-on-Graph（EoG），通过 SFT + 两阶段强化学习（结果奖励 + 路径精炼奖励），激励 LLM 在知识图谱上自主探索超出训练分布的推理路径，在五个 KGQA 基准上超越 GPT-5 和 Gemini 2.5 Pro。
研究背景与动机¶
- LLM 在 QA 中容易产生幻觉和知识缺失，知识图谱（KG）是接地验证的理想来源
- 现有方法分为两类，均有泛化局限：
- 规则方法（如 ToG、DoG）：预定义规则约束推理，训练无关但无法处理分布外模式
- 模仿方法（如 RoG、KG-Agent）：模仿训练数据中的推理模式，泛化到新路径困难
- 关键洞察：实际 KG 推理涉及非典型路径（如经过 colleague 或 subsidiary 间接关系），需要自主探索
- 示例：常见路径 "Google→employee→Carol→lives_in→London"，非典型路径 "Google→employee→Bob→colleague→John→resides_at→London"
方法详解¶
整体框架¶
两阶段训练： 1. SFT 阶段：用长 CoT 数据教会 LLM 结构化图推理能力（冷启动） 2. RL 阶段： - Phase 1：GRPO + 结果奖励（答案 F1 分数）激励发现正确路径 - Phase 2：GRPO + 联合奖励（结果+路径精炼）提高探索效率和语义质量
关键设计¶
长 CoT 数据集构建： - 精心设计 prompt 要求推理结构化、逻辑严谨、与 KG 对齐 - 使用 Gemini 2.5 Flash 进行知识蒸馏，生成推理路径（think 标签）和最终答案（answer 标签） - 额外规则过滤不合格的推理过程，确保结构和事实正确性 - 直接让 LLM 探索 KG 面临巨大动作空间和极端奖励稀疏性，SFT 冷启动不可或缺
Phase 1：结果奖励（Outcome Reward）： - 使用 GRPO 算法，每个问题采样 S 条探索路径 - 奖励 = 实体级 F1 分数（而非简单 Hit@1），更适合多答案场景 - 未生成正确格式答案标签的路径自动获得 0 奖励，隐式鼓励正确格式 - 通过 GRPO 的组内相对优势归一化驱动策略优化
Phase 2：路径精炼奖励（Path-refined Reward）：
真实路径获取（Search-and-Verify Pipeline）： 1. 识别问题中的主题实体和 KG 中的答案实体 2. BFS 搜索所有连接路径（最大跳数约束），确保高召回 3. LLM（Gemini-2.5-Flash）语义验证路径是否与问题意图匹配，过滤虚假拓扑连接
路径奖励计算：检查真实路径中每个三元组 (s,r,o) 是否全部作为子串出现在生成的思维文本中，取匹配比例作为路径奖励分数。
联合奖励：R_joint = R_outcome + α * R_path，α 控制路径奖励权重。
两阶段 RL 设计动机：先用结果奖励建立基本探索能力，再用路径奖励精炼探索质量和效率。
损失函数 / 训练策略¶
- SFT 阶段：标准语言建模损失（交叉熵），在长 CoT 数据上训练
- RL 阶段：GRPO 目标函数，含重要性采样比率、clipping、KL 散度正则
- 基座模型：Qwen2.5-7B-Instruct 和 Llama-3.1-8B-Instruct
- SFT 数据由 Gemini-2.5-Flash 蒸馏，RL 用 verl 框架实现 GRPO
实验关键数据¶
主实验（五个 KGQA 基准）¶
| 方法 | 模型 | WebQSP Hit@1 | CWQ Hit@1 | GrailQA Hit@1 | QALD10 Hit@1 | 2WikiMH Hit@1 |
|---|---|---|---|---|---|---|
| DoG | Llama-3.1-8B | 91.4 | 76.2 | - | - | 84.1 |
| GCR | Llama-3.1-8B | 92.2 | 75.8 | - | - | - |
| GPT-5 | - | 86.1 | 74.1 | 90.5 | 59.2 | 84.2 |
| Gemini-2.5-Pro | - | 92.1 | 71.9 | 91.6 | 58.6 | 85.1 |
| EoG | Qwen2.5-7B | 90.7 | 82.7 | 91.7 | 67.3 | 83.9 |
| EoG | Llama-3.1-8B | 92.8 | 86.6 | 92.1 | 70.6 | 85.3 |
EoG (Llama-3.1-8B) 在 CWQ 上以 86.6 Hit@1 大幅超越 GPT-5 (74.1) 和 Gemini-2.5-Pro (71.9)。
| 复杂推理场景 (CWQ F1) | Conjunction | Superlative | 1-hop | ≥4-hop |
|---|---|---|---|---|
| GCR | 63.7 | 52.6 | 66.3 | 45.8 |
| DoG | 53.3 | 45.9 | 50.3 | 46.7 |
| EoG | 70.2 | 64.7 | 76.2 | 69.6 |
EoG 在最困难的 ≥4-hop 推理中优势最大（69.6 vs 45.8/46.7）。
消融实验¶
| 变体 | CWQ Hit@1 | CWQ F1 | WebQSP Hit@1 | WebQSP F1 |
|---|---|---|---|---|
| EoG 完整 | 82.6 | 73.9 | 92.8 | 81.3 |
| 去除路径奖励 | 81.5 | 70.8 | 90.2 | 77.3 |
| 去除结果奖励 | 62.7 | 51.4 | 65.5 | 56.2 |
| 去除 SFT | 70.3 | 63.1 | 75.9 | 65.8 |
| 去除 SFT + 用 ICL | 70.7 | 63.8 | 77.2 | 66.5 |
关键发现¶
- 结果奖励是最核心组件（去除后 CWQ Hit@1 从 82.6 降到 62.7）
- 路径奖励提升探索效率：降低输出长度（CWQ: 2067→1528 词），提升综合性和相关性
- SFT 冷启动不可或缺，纯 RL（无 SFT）性能大幅下降，ICL 也无法弥补
- α 过小导致生成错误/无意义路径，过大导致忽略答案正确性
- 路径奖励使模型在 ≥4-hop 上提升最显著，说明路径信号对深层推理最关键
- EoG 在六维推理质量评估中全面领先，尤其在推理深度和探索性上
亮点与洞察¶
- 开源 7-8B 模型通过 RL 探索超越闭源 GPT-5 和 Gemini-2.5-Pro，展示自主探索的威力
- 路径精炼奖励设计巧妙：通过 BFS + LLM 语义验证获取真实路径，基于三元组子串匹配计算奖励
- "探索"能力与"模仿"能力的对比令人信服：模仿受限于训练分布，探索能发现分布外路径
- 两阶段 RL（先结果奖励再联合奖励）的课程设计值得借鉴
- 在最具挑战性的 ≥4-hop 和 superlative 场景中提升最大，验证了探索对复杂推理的价值
局限与展望¶
- 真实路径获取依赖 BFS + LLM 验证，对于超大规模 KG 可能计算代价高
- 路径奖励基于子串匹配，可能受同一实体不同名称的表述差异影响
- 仅在 Freebase 和 Wikidata 上验证，领域特定 KG（如生物医学）待测试
- 训练数据由 Gemini-2.5-Flash 蒸馏生成，数据质量受限于教师模型
- 未探讨动态 KG（知识随时间变化）的适应性
相关工作与启发¶
- 与 DeepSeek-R1 的 RL 推理范式一致，但将其扩展到图结构化推理领域
- 规则方法（ToG、DoG）提供结构保证但缺乏灵活性，EoG 通过 RL 隐式学习结构约束
- 路径精炼奖励与 process reward model（PRM）思路类似，但更直接（基于事实匹配而非模型判断）
- 对 KG-enhanced RAG 有启发：可将探索策略引入知识增强检索
评分¶
- 新颖性: 4/5 （RL 探索 KG 的思路新颖，路径精炼奖励设计独到）
- 实验充分度: 5/5 （五个数据集、多个基线含闭源模型、详尽消融和复杂场景分析）
- 写作质量: 4/5 （框架清晰，示例图解有效）
- 价值: 5/5 （8B 模型超越 GPT-5 的结果极具说服力，实用价值高）