Think-on-Graph： Deep and Responsible Reasoning of Large Language Model on Knowledge Graph
（ICLR 2024）
提出了一种新的 LLM-KG 整合范式”$LLM\otimes KG$”，将 LLM 视为代理，交互式探索 KG（知识图谱） 上的相关实体和关系，并基于检索到的知识进行推理。
motivation
LLM面临幻觉或者推理能力受限的问题。因此有些方法接入外部知识 (KG or 数据库) 来作为 LLM 的一个补充。
然而目前现有的结合方法通常是 比较简单的模式（作者称为$LLM\oplus KG$，例如用 LLM 生成 SPARQL 查询语句），这种“松耦合”模式中，LLM 仅作为翻译器，不直接参与推理过程。如果生成的查询语句有误或 KG 缺失特定关系，推理就会失败 。
方法
LLM 被视为一个智能体（Agent），它利用**波束搜索（Beam Search）**算法在知识图谱上一步步地“行走”和“思考”，动态地探索推理路径 。
ToG 的推理流程（三个阶段） ：
- 初始化（Initialization）：
给定一个问题，LLM 首先识别并提取问题中的“主题实体”（Topic Entities），作为图搜索的起点 。
- 探索（Exploration）：
这是基于波束搜索的迭代过程。在每一跳（Hop）中，包含两个步骤：
关系探索（Relation Exploration）： 搜索与当前实体相连的关系，LLM 对这些关系与问题的相关性进行打分（Prune），保留 Top-N 个最相关的关系 。
实体探索（Entity Exploration）： 根据保留的关系查找对应的尾实体，LLM 再次根据问题对这些实体进行打分和剪枝，保留最有希望的路径 。
- 推理（Reasoning）：
在每次迭代后，LLM 会评估当前收集到的路径信息是否足以回答问题。如果足够，则生成答案；如果不足，则继续下一轮深度的探索，直到达到最大搜索深度 。
变体-基于关系的 ToG（ToG-R）
它主要基于“关系链”进行搜索，在实体剪枝阶段采用随机采样而非 LLM 打分。这种方法减少了 LLM 的调用次数，同时保留了关系层面的推理能力 。
