GGraphRAG 文献图谱自动同步
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:
    • WebQuestions
  • 2 个 slot filling:
    • T-REx
    • Zero-Shot RE
  • 1 个 fact checking:
    • Creak
  • 对 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 之后开始明显变缓,因此作者把默认设置定在:
    • N = 3
    • Dmax = 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 变多仍会出现。

关联与拓展

研究问题入口

Q2 图构建与表示, Q3 证据检索与集合形成, Q5 动态状态与学习策略, Q6 证据来源与可解释性, Q7 鲁棒性与安全

展开原始论文笔记全文

基本信息

  • 作者: 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:
    • WebQuestions
  • 2 个 slot filling:
    • T-REx
    • Zero-Shot RE
  • 1 个 fact checking:
    • Creak
  • 对 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 之后开始明显变缓,因此作者把默认设置定在:
    • N = 3
    • Dmax = 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 的前提下保住效果。
搜索算法 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 变多仍会出现。

相关主题