💬 NLP

Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs

该论文提出了图上搜索（Search-on-Graph, SoG），这是一个迭代式的“观察-思考-导航”框架，它使大语言模型能够基于完整的推理历史，直接在知识图谱中选择并遍历推理路径，从而在无需针对特定任务进行微调的情况下，在知识图谱问答（KGQA）基准测试上超越了现有方法。

原作者： Jia Ao Sun, Hao Yu, Fabrizio Gotti, Fengran Mo, Yihong Wu, Yuchen Hui, Zhan Su, Lingfeng Xiao, Jian-Yun Nie

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Jia Ao Sun, Hao Yu, Fabrizio Gotti, Fengran Mo, Yihong Wu, Yuchen Hui, Zhan Su, Lingfeng Xiao, Jian-Yun Nie

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

以下是使用简单语言和创意类比对《Search-on-Graph》论文进行的解释。

核心问题：会“幻觉”的图书管理员

想象你有一位超级聪明的图书管理员（大语言模型，简称 LLM），他读过世界上几乎所有的书。这位管理员非常擅长写故事和回答一般性问题。但是，当你问一个需要核实特定事实的棘手问题时——比如“梵高出生国家的首都城市是什么？”——这位管理员有时会表现得非常自信，但给出的答案却是错误的。他们可能会凭空捏造一个国家或首都，因为他们是在根据模式进行猜测，而不是基于事实。这被称为“幻觉”。

为了解决这个问题，研究人员给了这位图书管理员一张巨大的、结构化的事实地图，称为知识图谱 (Knowledge Graph, KG)。你可以把这张地图想象成一个巨大的地铁系统，其中每一个站点都是一个事实（例如“梵高”），而每一条轨道都是一种连接（例如“出生地”）。

旧方法：“猜谜式”导游

在此篇论文发表之前，大多数方法试图通过一个独立的“导游”模块来帮助图书管理员在地铁地图中导航。

缺陷： 这个导游会观察问题和地图，然后根据单词听起来有多相似来尝试猜测应该走哪条轨道。
错误： 如果导游听到“梵高”和“国家”，他们可能会跳到一条标签为“国籍”的轨道上，仅仅是因为这两个词听起来很像，即使地图上实际存在的轨道是“出生地”。
结果： 图书管理员会被送到错误的路径上，过早地剪枝（切断）正确的路径，或者迷失在无关轨道的迷宫中。这就像是仅通过观察与目的地听起来相似的街道名称来导航城市，而不是观察实际的地图。

新方法：“图上搜索”（Search-on-Graph, SoG）

作者提出了一种名为 Search-on-Graph (SoG) 的新方法。他们不再雇佣一个单独的导游，而是让图书管理员亲自开车，但必须遵循一套非常具体的规则。

“观察-思考-导航”策略

SoG 通过在每一个地铁站都执行一个简单的三步程序，改变了游戏规则：

观察 (Observe)： 图书管理员停在一个站点（例如“梵高”），并查看站牌。站牌列出了从该站点出发的所有轨道（例如“职业”、“出生日期”、“出生地”）。
思考 (Think)： 图书管理员查看原始问题（“他是在哪里出生的？”）以及之前的行进历史。他会对自己说：“我知道我在‘梵高’站。我需要找到他的出生国家。看着站牌，‘出生地’是目前唯一合理的轨道。”
导航 (Navigate)： 图书管理员选择这条特定的轨道，并移动到下一个站点（例如“曾德特”）。

神奇之处在于： 图书管理员不会基于词汇相似度进行猜测。他们观察眼前实际存在的连接，并利用其推理能力来做出选择。

处理“拥挤的车站”

这些地图的一个大问题是，有些车站极其拥挤。例如，“荷兰”这个车站可能有 10,000 条轨道通向四面八方（出生于此的人、境内的城市、使用的语言等）。如果你一次性向图书管理员展示 10,000 条轨道，他们的脑子（计算机内存）就会爆炸。

解决方案： SoG 系统使用了一个聪明的过滤器。

第一步： 它不再向图书管理员展示 10,000 条轨道，而是先向他们展示一份仅包含可用轨道“类型”的列表（例如：“首都”、“语言”、“人口”）。
第二步： 图书管理员会说：“我需要的是‘首都’。”
第三步： 系统随后仅展示与“首都”相关的轨道。
这把一个混乱、令人崩溃的人群变成了一支有序、可控的队伍。

为什么它效果更好

论文在六个不同的“迷宫”（数据集）上测试了这种方法，使用的是 Freebase 和 Wikidata 等真实世界的知识图谱。

结果： SoG 击败了几乎所有其他方法，包括那些使用更强大计算机或复杂规划的方法。
原因： 通过让 LLM 查看实际的地图并对其旅程历史进行推理，它避免了“语义漂移”（即因为单词听起来相似而迷失方向）。它始终保持在逻辑路径上。
效率： 它也更快，且消耗更少的计算资源，因为它不会浪费时间去探索死胡同，也不会维持多个并行的猜测（比如旧有的“束搜索/beam search”方法）。

总结

将 Search-on-Graph 理解为教会一个聪明的 AI 成为一名侦探，他在每一步都会检查证据，而不是一个依赖直觉进行猜测的人。它不需要针对每个新谜题进行重新训练；它只需要被告知如何利用提供的地图进行“观察、思考并移动”。这种简单的迭代方法被证明是解决复杂事实型问题最可靠的方式。

技术摘要：图上搜索 (Search-on-Graph, SoG)

问题陈述

由知识图谱 (KG) 增强的大语言模型 (LLM) 为知识密集型推理提供了一条充满前景的途径。然而，现有在知识图谱中选择推理路径的方法面临一个关键限制：选择过程往往与推理需求脱节。目前的方法通常依赖于独立的模块或独立的标准（例如与原始问题的语义相似度）来进行剪枝或选择关系。这种脱节导致了两个主要的失效模式：

语义漂移 (Semantic Drift)： 由于选择是基于表层相似度而非推理历史，探索过程会偏离回答问题所需的逻辑链。
过早剪枝 (Premature Pruning)： 逻辑正确但词法上不相似的关系被过早剔除，导致推理过程失败。

此外，许多现有的智能体方法采用复杂的组件架构（包括独立的规划、检索和推理模块），或通过束搜索 (beam search) 维持并行的探索路径，这引入了显著的内存开销和计算复杂度，却无法保证推理的有效性。

方法论：图上搜索 (SoG)

作者提出了 图上搜索 (Search-on-Graph, SoG)，这是一个将路径选择与推理统一在单个 LLM 之内的框架。SoG 基于 观察-思考-导航 (observe-think-navigate) 范式运行，LLM 通过根据完整的推理历史和当前的局部图结构做出明智决策，迭代地遍历知识图谱。

核心组件

迭代式 1-Hop 搜索：
SoG 使用一个经过精心设计的单一 Search 函数作为 LLM 探索知识图谱的唯一接口。该函数检索给定实体在指定方向（出向或入向）上的 1-hop 邻居。
- 输入： 实体 ID、方向以及可选的过滤属性。
- 输出： 一个包含属性 ID、标签、数值 ID 和数值标签的高效 Markdown 表格。
处理高度数节点：
为了应对具有数千个连接的实体（如国家、名人）带来的挑战，SoG 采用了两阶段过滤机制：
- 属性发现： 如果一个节点的邻居数量超过 $k$ 个（默认 $k=50$ ）且未请求特定属性，系统仅返回唯一的属性类型，而非所有实例。
- 定向检索： LLM 分析可用的属性，并进行第二次针对性的 Search 调用，使用特定属性仅检索相关的邻居。
- 截断： 如果结果仍然超过阈值 $p$ （默认 $p=1000$ ），则进行截断以符合上下文限制。
上下文感知导航：
与维护多个并行路径的束搜索方法不同，SoG 引导 LLM 根据 完整的推理历史 在每一步选择单个关系。LLM 观察当前实体的邻居，思考哪条路径能推进答案（例如，“我目前在 Zundert，来自 Van Gogh，需要知道国家，所以我寻找‘被包含于’关系”），并据此进行导航。这确保了逻辑连贯性，避免了并行探索带来的噪声累积。
提示策略：
系统使用一个定义了智能体角色及一组少样本示例（通常为 5 个）的系统提示词，这些示例展示了三个阶段：初始探索、迭代遍历和答案提取。LLM 自主决定何时收集到了足够的信息以停止工具调用并提供最终答案。

核心贡献

统一的框架： SoG 提出了一个简单而有效的 KGQA 框架，其中单个 LLM 编排迭代式的 KG 遍历，消除了对独立规划或检索模块的需求。
上下文感知导航： 该方法基于实际的推理需求和完整上下文进行导航，避免了像 Think-on-Graph (ToG) 这种无上下文剪枝方法中常见的语义漂移问题。
模式无关性 (Schema Agnosticism)： 该方法无需修改或针对特定任务进行微调，即可推广到不同的知识图谱模式（Freebase 和 Wikidata）。
高效性： 通过每跳选择单个关系而非维持并行路径，与束搜索基准方法相比，SoG 显著减少了 LLM 调用次数和输出 Token 数。

实验结果

作者在涵盖 Freebase (SimpleQA, WebQSP, CWWQ, GrailQA) 和 Wikidata (QALD-9, QALD-10) 的六个 KGQA 基准测试集上对 SoG 进行了评估。

性能： SoG 在 六个数据集中的五个 上取得了最先进 (SOTA) 的结果，且无需任何特定任务的微调。
- 在 Wikidata 基准测试中，相比之前的最优方法，其增益超过了 11.3%。
- 在 Freebase 数据集中，它超越了先前的系统，仅在 CWQ 上以 0.1% 的差距落后于 Generate-on-Graph。
骨干模型鲁棒性： 该框架兼容多种 LLM 骨干模型。它使用 GPT-4o 达到了 SOTA 性能，并在开源模型（Qwen3 系列）上也表现出了强大的结果。值得注意的是，即使是紧凑型的 Qwen3-4B 模型也超越了以往的方法在 Wikidata 基准测试中的表现，证明了该方法在不同模型规模下的有效性。
效率： 与 Think-on-Graph 基准相比，SoG 减少了至少 46.4% 的 LLM 调用和 69.9% 的输出 Token，尽管它需要更多的输入 Token 来维持完整的推理上下文。
消融研究：
- 少样本学习： 仅使用一个导航示例时性能就有显著提升，并在 3-5 个 shot 时达到平台期。
- 模型类型： “思考型”（经过推理优化）模型始终优于标准的指令微调模型，尤其是在多跳任务中。
- 输出格式： 提出的“Markdown + 属性过滤器”格式在准确性和 Token 效率之间达到了最佳平衡。

意义与主张

论文声称，图上搜索 (Search-on-Graph) 验证了一种新的范式，即 LLM 驱动的导航 比依赖于单独的选择模块或预先规划的方法在知识图谱推理方面更具优势。

作者认为，基于实际推理需求和完整上下文，由单个 LLM 在每一步选择相关关系的假设是成立的。这种方法简化了架构，降低了计算开销，并能有效地推广到不同的知识图谱模式和模型规模。结果表明，结合了仔细的上下文管理的架构简洁性，可以超越更为复杂的、多组件的系统。