LIT-3A8CD1E4 · 2024
Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph
ToG 把 LLM 从“被动读取检索结果的回答器”变成“主动在 KG 上做 beam search 的 agent”,让模型边探索关系路径、边判断何时停止,再基于路径证据回答问题。
PDF 级阅读卡优先级 P1Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel M. Ni, Heung-Yeung Shum, Jian GuoICLR 2024
内容状态:PDF 级阅读卡。结构化摘录继承当前知识库的来源等级;具体 claim 应回到一手论文核验。
研究问题与动机
- 仅靠 LLM 内部参数知识,容易过时、幻觉重。
- 传统
LLM + KG 往往只是让 LLM 生成 SPARQL 或读取一次性检索结果,推理深度有限。
- 复杂 KGQA 需要的不只是事实查找,而是沿图结构逐步探索多跳证据链。
方法与机制
1. LLM ⊗ KG:不是“读事实”,而是“在图上探索”
- ToG 的核心范式不是传统的
LLM + KG,而是作者称为 LLM ⊗ KG 的协同模式。
- 重点不在于把 KG 三元组拼到 prompt 里,而在于让 LLM 直接承担图上搜索与剪枝的角色。
- 因此 ToG 真正改变的是 LLM 的职责:
- 不再只是基于取回证据回答
- 而是让 LLM 亲自决定下一步该看哪条关系、哪个实体、何时停止
2. 三阶段流程
初始化
- 给定问题后,先让 LLM 自动抽取 topic entities,并得到 top-N 初始实体集合
E^0。
- 这一步本质上是在 KG 上为 beam search 选起点。
探索
- ToG 会持续维护 top-N reasoning paths
P = {p1, ..., pN}。
- 每一轮探索都分成两个子过程:
- Relation exploration
- Entity exploration
推理
- 每轮探索后,LLM 会判断当前 top-N paths 是否已经包含足够证据。
- 如果足够,就基于这些路径回答问题。
- 如果不够,就继续下一轮探索,直到达到最大深度
Dmax。
- 若达到
Dmax 仍无法解决,ToG 会退回只依赖 LLM 内部知识作答。
3. Relation exploration:先决定“往哪种关系走”
- 给定当前路径尾实体集合
E^(D-1),先把每个尾实体连出去的 candidate relations 搜出来。
- 这一步通过固定的 formal queries 完成,不需要为不同 KG 额外训练。
- 然后让 LLM 结合问题文本,对 candidate relations 打分并保留 top-N。
- 作者的直觉是:直接面对大量候选实体过于复杂,所以先让 LLM 在关系层面筛一遍,降低后续搜索难度。
4. Entity exploration:再决定“沿这些关系走到哪个实体”
- 在筛出的关系基础上,再查询出相应的 tail entities,得到 candidate entity sets。
- 由于这些候选实体都已经是自然语言形式,LLM 可以继续基于问题做 prune。
- 经过 relation prune 和 entity prune 后,就得到一组新的 top-N reasoning paths,其长度比上一轮多 1。
- 每个 prune step 最多需要
N 次 LLM 调用。
5. ToG-R:更便宜但信息更少的 relation-only 变体
- 作者还提出 ToG-R,只显式维护 relation chains,而不是完整三元组路径。
- 它和 ToG 的主要差别在于:
- 不再用 LLM 对实体做 prune
- 而是采用 random prune
- 这么做的理由是:同一 relation 下的候选实体往往属于相似类别,实体 prune 对下一轮 relation search 的帮助可能有限。
- 复杂度上:
- ToG 最多需要
2ND + D + 1 次 LLM 调用
- ToG-R 最多需要
ND + D + 1 次
- 所以 ToG-R 更像一个“省调用”的近似版本。
证据与结果
- 论文总共评测了 9 个数据集。
- 5 个 KGQA:
CWQ
WebQSP
GrailQA
QALD10-en
Simple Questions
- 1 个开放域 QA:
- 2 个 slot filling:
- 1 个 fact checking:
- 对 GrailQA 和 Simple Questions,作者各只随机抽
1,000 个测试样本,以控制成本。
- 统一指标是 exact match accuracy /
Hits@1。
- 默认实验细节:
- backbone 试了
Llama-2-70B-Chat、ChatGPT、GPT-4
N = 3
Dmax = 3
- 所有数据集 reasoning prompt 默认用
5-shot
- KG 选择:
Freebase 用于 CWQ、WebQSP、GrailQA、Simple Questions、WebQuestions
Wikidata 用于 QALD10-en、T-REx、Zero-Shot RE、Creak
1. 主表结果:training-free,但覆盖面很广
| 方法 |
CWQ |
WebQSP |
GrailQA |
QALD10-en |
Simple Questions |
WebQuestions |
T-REx |
Zero-Shot RE |
Creak |
| ToG-R w/ChatGPT |
58.9 |
75.8 |
56.4 |
48.6 |
45.4 |
53.2 |
75.3 |
86.5 |
93.8 |
| ToG w/ChatGPT |
57.1 |
76.2 |
68.7 |
50.2 |
53.6 |
54.5 |
76.8 |
88.0 |
91.2 |
| ToG-R w/GPT-4 |
69.5 |
81.9 |
80.3 |
54.7 |
58.6 |
57.1 |
75.5 |
86.9 |
95.4 |
| ToG w/GPT-4 |
67.6 |
82.6 |
81.4 |
53.8 |
66.7 |
57.9 |
77.1 |
88.3 |
95.6 |
- 作者总结为:9 个数据集里有 6 个达到总体 SOTA。
- 文中明确点名的 SOTA 数据集包括:
- WebQSP
- GrailQA
- QALD10-en
- WebQuestions
- Zero-Shot RE
- Creak
- 在 CWQ 上,ToG 虽未超过 fine-tuned SOTA
70.4,但 69.5 已非常接近。
- 这点很关键,因为 ToG 是完全不训练的方法,而很多 prior SOTA 都依赖 task-specific fine-tuning。
2. ToG 相对 ToG-R:更贵,但通常更强
- ToG 在大多数数据集上优于 ToG-R,作者解释是:
- ToG 使用完整 triple-based reasoning paths
- 中间实体信息能给 LLM 更多推理锚点
- 不过也有例外:
CWQ 上 ToG-R with GPT-4 69.5 高于 ToG 67.6
QALD10-en 上 ToG-R with GPT-4 54.7 也略高于 ToG 53.8
- 所以 ToG-R 不是简单的“降级版”,而是在某些 relation-driven 任务上也可能更合适。
3. 不同 backbone:更强的 LLM 能把 KG 搜索价值挖得更充分
| Backbone |
CWQ CoT |
CWQ ToG / ToG-R |
WebQSP CoT |
WebQSP ToG / ToG-R |
| Llama-2-70B |
39.1 |
53.6 / 57.6 |
57.4 |
63.7 / 68.9 |
| ChatGPT |
38.8 |
58.9 / 57.1 |
62.2 |
76.2 / 75.8 |
| GPT-4 |
46.0 |
67.6 / 69.5 |
67.3 |
82.6 / 81.9 |
- 论文特别强调两个结论:
- ToG 对 stronger backbone 的收益更大
- 小模型 + ToG 在一些设置下也能超过 大模型 + 纯 CoT
- 例如:
Llama-2-70B + ToG-R 在 CWQ 上是 57.6
- 已高于
GPT-4 + CoT 的 46.0
- 作者把这当成一个很现实的部署结论:
- 与其无脑上更贵的大模型
- 不如让较小模型配合 KG 搜索
4. 搜索深度与宽度确实重要,但 3 已经是成本/收益折中点
- ablation 显示,ToG 的效果会随着 search depth
Dmax 和 beam width N 提升而上升。
- 但收益在
3 之后开始明显变缓,因此作者把默认设置定在:
- 这也和附录中的问题深度分析一致:大多数测试问题并不需要超过 3 的推理深度。
5. KG 来源确实影响效果
| 方法 |
CWQ |
WebQSP |
| CoT |
37.6 |
62.0 |
| ToG w/ Freebase |
58.8 |
76.2 |
| ToG w/ Wikidata |
54.9 |
68.6 |
| ToG-R w/ Freebase |
59.2 |
75.1 |
| ToG-R w/ Wikidata |
51.9 |
66.7 |
- 因为 CWQ 和 WebQSP 本来就是基于 Freebase 构建,所以 Freebase 作为 source KG 更合适。
- 这说明 ToG 不是“接任何 KG 都一样”,KG 的 schema、规模和覆盖都会影响搜索难度。
6. Prompt 设计与 prune 工具也会改结果
Prompt 表示
| 方法 |
CWQ |
WebQSP |
| ToG w/ Triples |
58.8 |
76.2 |
| ToG w/ Sequences |
57.2 |
73.2 |
| ToG w/ Sentences |
58.6 |
73.0 |
| ToG-R w/ Sequences |
59.2 |
75.1 |
| ToG-R w/ Sentences |
50.1 |
67.3 |
- 对 ToG 来说,triples 形式最好。
- 对 ToG-R 来说,把 relation chains 翻译成自然语言句子会显著拉低效果。
Prune 工具
原始笔记摘录已截断;请打开来源笔记阅读完整内容。
局限与开放问题
- LLM 调用次数很多。按照论文给出的上界:
- ToG 最多需要
2ND + D + 1
- ToG-R 最多需要
ND + D + 1
在默认 N = D = 3 时,这并不便宜。
- 对实体链接和 KG 覆盖率敏感;如果起点实体错了,后续搜索基本都会偏。
- 搜索宽度和深度需要权衡,太浅会漏证据,太深会引入噪声和更高成本。
- 单跳任务上的优势不如多跳任务明显,例如 Simple Questions 上仍远低于 fine-tuned SOTA。
- 作者自己的证据分析也表明,ToG 还不是完全 grounded:仍有约
20% 的正确答案主要依赖模型参数知识。
- format error 虽然占比低,但随着路径变长、token 变多仍会出现。
展开原始论文笔记全文
基本信息
- 作者: Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel M. Ni, Heung-Yeung Shum, Jian Guo
- 机构: IDEA Research, Xiamen University, USC, HKUST, HKUST(GZ), Microsoft Research Asia
- 会议/期刊: ICLR 2024
- arXiv: 2307.07697
一句话理解
ToG 把 LLM 从“被动读取检索结果的回答器”变成“主动在 KG 上做 beam search 的 agent”,让模型边探索关系路径、边判断何时停止,再基于路径证据回答问题。
论文要解决什么问题
- 仅靠 LLM 内部参数知识,容易过时、幻觉重。
- 传统
LLM + KG 往往只是让 LLM 生成 SPARQL 或读取一次性检索结果,推理深度有限。
- 复杂 KGQA 需要的不只是事实查找,而是沿图结构逐步探索多跳证据链。
方法机制
1. LLM ⊗ KG:不是“读事实”,而是“在图上探索”
- ToG 的核心范式不是传统的
LLM + KG,而是作者称为 LLM ⊗ KG 的协同模式。
- 重点不在于把 KG 三元组拼到 prompt 里,而在于让 LLM 直接承担图上搜索与剪枝的角色。
- 因此 ToG 真正改变的是 LLM 的职责:
- 不再只是基于取回证据回答
- 而是让 LLM 亲自决定下一步该看哪条关系、哪个实体、何时停止
2. 三阶段流程
初始化
- 给定问题后,先让 LLM 自动抽取 topic entities,并得到 top-N 初始实体集合
E^0。
- 这一步本质上是在 KG 上为 beam search 选起点。
探索
- ToG 会持续维护 top-N reasoning paths
P = {p1, ..., pN}。
- 每一轮探索都分成两个子过程:
- Relation exploration
- Entity exploration
推理
- 每轮探索后,LLM 会判断当前 top-N paths 是否已经包含足够证据。
- 如果足够,就基于这些路径回答问题。
- 如果不够,就继续下一轮探索,直到达到最大深度
Dmax。
- 若达到
Dmax 仍无法解决,ToG 会退回只依赖 LLM 内部知识作答。
3. Relation exploration:先决定“往哪种关系走”
- 给定当前路径尾实体集合
E^(D-1),先把每个尾实体连出去的 candidate relations 搜出来。
- 这一步通过固定的 formal queries 完成,不需要为不同 KG 额外训练。
- 然后让 LLM 结合问题文本,对 candidate relations 打分并保留 top-N。
- 作者的直觉是:直接面对大量候选实体过于复杂,所以先让 LLM 在关系层面筛一遍,降低后续搜索难度。
4. Entity exploration:再决定“沿这些关系走到哪个实体”
- 在筛出的关系基础上,再查询出相应的 tail entities,得到 candidate entity sets。
- 由于这些候选实体都已经是自然语言形式,LLM 可以继续基于问题做 prune。
- 经过 relation prune 和 entity prune 后,就得到一组新的 top-N reasoning paths,其长度比上一轮多 1。
- 每个 prune step 最多需要
N 次 LLM 调用。
5. ToG-R:更便宜但信息更少的 relation-only 变体
- 作者还提出 ToG-R,只显式维护 relation chains,而不是完整三元组路径。
- 它和 ToG 的主要差别在于:
- 不再用 LLM 对实体做 prune
- 而是采用 random prune
- 这么做的理由是:同一 relation 下的候选实体往往属于相似类别,实体 prune 对下一轮 relation search 的帮助可能有限。
- 复杂度上:
- ToG 最多需要
2ND + D + 1 次 LLM 调用
- ToG-R 最多需要
ND + D + 1 次
- 所以 ToG-R 更像一个“省调用”的近似版本。
实验设置
- 论文总共评测了 9 个数据集。
- 5 个 KGQA:
CWQ
WebQSP
GrailQA
QALD10-en
Simple Questions
- 1 个开放域 QA:
- 2 个 slot filling:
- 1 个 fact checking:
- 对 GrailQA 和 Simple Questions,作者各只随机抽
1,000 个测试样本,以控制成本。
- 统一指标是 exact match accuracy /
Hits@1。
- 默认实验细节:
- backbone 试了
Llama-2-70B-Chat、ChatGPT、GPT-4
N = 3
Dmax = 3
- 所有数据集 reasoning prompt 默认用
5-shot
- KG 选择:
Freebase 用于 CWQ、WebQSP、GrailQA、Simple Questions、WebQuestions
Wikidata 用于 QALD10-en、T-REx、Zero-Shot RE、Creak
主要结果
1. 主表结果:training-free,但覆盖面很广
| 方法 |
CWQ |
WebQSP |
GrailQA |
QALD10-en |
Simple Questions |
WebQuestions |
T-REx |
Zero-Shot RE |
Creak |
| ToG-R w/ChatGPT |
58.9 |
75.8 |
56.4 |
48.6 |
45.4 |
53.2 |
75.3 |
86.5 |
93.8 |
| ToG w/ChatGPT |
57.1 |
76.2 |
68.7 |
50.2 |
53.6 |
54.5 |
76.8 |
88.0 |
91.2 |
| ToG-R w/GPT-4 |
69.5 |
81.9 |
80.3 |
54.7 |
58.6 |
57.1 |
75.5 |
86.9 |
95.4 |
| ToG w/GPT-4 |
67.6 |
82.6 |
81.4 |
53.8 |
66.7 |
57.9 |
77.1 |
88.3 |
95.6 |
- 作者总结为:9 个数据集里有 6 个达到总体 SOTA。
- 文中明确点名的 SOTA 数据集包括:
- WebQSP
- GrailQA
- QALD10-en
- WebQuestions
- Zero-Shot RE
- Creak
- 在 CWQ 上,ToG 虽未超过 fine-tuned SOTA
70.4,但 69.5 已非常接近。
- 这点很关键,因为 ToG 是完全不训练的方法,而很多 prior SOTA 都依赖 task-specific fine-tuning。
2. ToG 相对 ToG-R:更贵,但通常更强
- ToG 在大多数数据集上优于 ToG-R,作者解释是:
- ToG 使用完整 triple-based reasoning paths
- 中间实体信息能给 LLM 更多推理锚点
- 不过也有例外:
CWQ 上 ToG-R with GPT-4 69.5 高于 ToG 67.6
QALD10-en 上 ToG-R with GPT-4 54.7 也略高于 ToG 53.8
- 所以 ToG-R 不是简单的“降级版”,而是在某些 relation-driven 任务上也可能更合适。
3. 不同 backbone:更强的 LLM 能把 KG 搜索价值挖得更充分
| Backbone |
CWQ CoT |
CWQ ToG / ToG-R |
WebQSP CoT |
WebQSP ToG / ToG-R |
| Llama-2-70B |
39.1 |
53.6 / 57.6 |
57.4 |
63.7 / 68.9 |
| ChatGPT |
38.8 |
58.9 / 57.1 |
62.2 |
76.2 / 75.8 |
| GPT-4 |
46.0 |
67.6 / 69.5 |
67.3 |
82.6 / 81.9 |
- 论文特别强调两个结论:
- ToG 对 stronger backbone 的收益更大
- 小模型 + ToG 在一些设置下也能超过 大模型 + 纯 CoT
- 例如:
Llama-2-70B + ToG-R 在 CWQ 上是 57.6
- 已高于
GPT-4 + CoT 的 46.0
- 作者把这当成一个很现实的部署结论:
- 与其无脑上更贵的大模型
- 不如让较小模型配合 KG 搜索
4. 搜索深度与宽度确实重要,但 3 已经是成本/收益折中点
- ablation 显示,ToG 的效果会随着 search depth
Dmax 和 beam width N 提升而上升。
- 但收益在
3 之后开始明显变缓,因此作者把默认设置定在:
- 这也和附录中的问题深度分析一致:大多数测试问题并不需要超过 3 的推理深度。
5. KG 来源确实影响效果
| 方法 |
CWQ |
WebQSP |
| CoT |
37.6 |
62.0 |
| ToG w/ Freebase |
58.8 |
76.2 |
| ToG w/ Wikidata |
54.9 |
68.6 |
| ToG-R w/ Freebase |
59.2 |
75.1 |
| ToG-R w/ Wikidata |
51.9 |
66.7 |
- 因为 CWQ 和 WebQSP 本来就是基于 Freebase 构建,所以 Freebase 作为 source KG 更合适。
- 这说明 ToG 不是“接任何 KG 都一样”,KG 的 schema、规模和覆盖都会影响搜索难度。
6. Prompt 设计与 prune 工具也会改结果
Prompt 表示
| 方法 |
CWQ |
WebQSP |
| ToG w/ Triples |
58.8 |
76.2 |
| ToG w/ Sequences |
57.2 |
73.2 |
| ToG w/ Sentences |
58.6 |
73.0 |
| ToG-R w/ Sequences |
59.2 |
75.1 |
| ToG-R w/ Sentences |
50.1 |
67.3 |
- 对 ToG 来说,triples 形式最好。
- 对 ToG-R 来说,把 relation chains 翻译成自然语言句子会显著拉低效果。
Prune 工具
| 方法 |
CWQ |
WebQSP |
| ToG w/ BM25 |
51.4 |
58.7 |
| ToG w/ SentenceBERT |
51.7 |
66.3 |
| ToG w/ ChatGPT |
58.8 |
76.2 |
| ToG-R w/ BM25 |
49.4 |
57.3 |
| ToG-R w/ SentenceBERT |
50.1 |
60.1 |
| ToG-R w/ ChatGPT |
59.2 |
75.1 |
- 用 BM25 / SentenceBERT 代替 LLM 做 prune,CWQ 平均掉约
8.4%,WebQSP 平均掉约 15.1%。
- 但代价也更低:
- 这时只需
D + 1 次 LLM 调用
- 而不是 ToG 的
2ND + D + 1
- 所以这里其实已经显出后续工作的一个主题:如何在不完全依赖 LLM prune 的前提下保住效果。
7. ToG 不是 naive beam search
| 搜索算法 |
CWQ |
WebQSP |
| Naive Beam Search |
30.1 |
46.1 |
| ToG-R |
59.2 |
75.1 |
| ToG |
58.8 |
76.2 |
- 这张对比很重要,因为它说明 ToG 的关键不只是“beam search”四个字。
- 真正起作用的是:
- top-N 多路径维护
- 每轮 sufficiency judgment
- 基于路径集合而不是单一路径回答
- 单纯挑“当前最 plausible 的一路”会让 calibration error 累积,性能远低于 ToG。
8. 误差与证据分析
- 作者把错误分成三类:
- hallucination
- refusal to answer
- format error
- 在 GrailQA 上,ToG 对 hallucination / refusal 分别降低约 50% / 60%。
- format error 会略有增加,但作者说总体比例 低于 3%。
- 对正确答案的证据来源分析显示:
- 大部分答案来自 ToG 探索到的路径
- 约 20% 只依赖 LLM 参数知识
- 约 7% 需要“路径证据 + LLM 内部知识”联合完成
- 这说明 ToG 实际上是一种 hybrid reasoning:
- 不是纯 KG reasoning
- 也不是纯 parametric reasoning
我的理解
- ToG 的关键贡献不是“beam search”本身,而是它重新定义了 LLM 在 KGQA 里的角色:
- 不再是看完证据再回答
- 而是把探索行为本身交给 LLM
- 它与 RoG---Reasoning-on-Graphs 的差别在于:
- RoG 更像先规划/检索出路径,再做 reasoning
- ToG 更强调在线交互式探索
- 它和 Graph-Constrained-Reasoning 也形成鲜明对比:
- ToG 是“让 LLM 主动搜图”
- GCR 是“让图约束 LLM 怎么生成”
- 后续很多 GraphRAG/KG-RAG 方法,其实都可以看成是在回答 ToG 的两个问题:
局限
- LLM 调用次数很多。按照论文给出的上界:
- ToG 最多需要
2ND + D + 1
- ToG-R 最多需要
ND + D + 1
在默认 N = D = 3 时,这并不便宜。
- 对实体链接和 KG 覆盖率敏感;如果起点实体错了,后续搜索基本都会偏。
- 搜索宽度和深度需要权衡,太浅会漏证据,太深会引入噪声和更高成本。
- 单跳任务上的优势不如多跳任务明显,例如 Simple Questions 上仍远低于 fine-tuned SOTA。
- 作者自己的证据分析也表明,ToG 还不是完全 grounded:仍有约
20% 的正确答案主要依赖模型参数知识。
- format error 虽然占比低,但随着路径变长、token 变多仍会出现。
相关主题
原始笔记论文/GraphRAG/Think-on-Graph-ToG.md