一句话理解

很多 GraphRAG 的失败不是“不会推理”,而是 搜索在有限预算下过早承诺给局部高分分支,导致真正支持答案的路径还没展开就被剪掉了。

为什么这是一个核心理论问题

  • GraphRAG 常常面对组合爆炸:
    • 节点多
    • 路径多
    • 扩展动作多
  • 所以系统几乎不可能做完备搜索,只能做近似搜索。

一旦采用 beam search、top-k expansion、dynamic pruning,就必须面对:

  • 会漏掉什么
  • 为什么会漏掉
  • 这些漏掉是否系统性偏向某类问题

什么叫“完备性”

在这里,完备性不是指数学上的绝对穷尽,而是一个更实用的问题:

  • 如果答案所需证据链存在于图中;
  • 当前搜索策略是否有合理机会把它保留下来。

所以完备性更接近:

  • evidence path completeness
  • search coverage
  • reachable support preservation

Beam Search 的偏差从哪里来

1. 局部分数偏差

  • beam search 往往按当前步分数保留少量候选;
  • 但多跳问答需要的是全链路价值,而不是当前一步看起来最像。

2. 短路径偏差

  • 短、直接、表面相关的路径更容易早期得高分;
  • 但真正答案可能在更长、更绕的桥接路径上。

3. 高度节点偏差

  • hub nodes 容易因为连接多、语义泛而被过度保留;
  • 结果是真正稀有但关键的桥接节点被淹没。

4. 种子误差放大

  • 一旦 seed entity 有偏差;
  • beam search 会在错误局部区域越来越“自信”。

5. 过早剪枝偏差

  • dynamic pruning 能控成本;
  • 但阈值稍高就可能把后续才会显现价值的路径剪掉。

当前知识库里最能说明问题的例子

Think-on-Graph-ToG

  • 这篇直接给了非常强的信号: naive beam search 远弱于 ToG。

关键不只是“用了 LLM”; 而是 ToG 保留了:

  • 多路径集合
  • sufficiency judgment
  • 多轮探索

这比“每轮只保一条最像的路径”更接近对完备性的保护。

GeAR 与 Graph-R1

  • 这些方法的价值之一,就是允许 replanning;
  • 当当前轨迹不够时,系统还能改搜法,而不是被第一次 beam 决策锁死。

HippoRAG

  • 以 PPR 为代表的 soft search 路线,也可以被看作对 hard beam bias 的一种替代: 不急着只保少数离散路径,而是先保留更分布式的相关性传播。

为什么这和 GraphRAG 的理论路线直接相关

1. 它连接了“搜索”与“推理”

  • 很多看似 reasoning failure 的错误;
  • 本质上是 search incompleteness。

2. 它连接了“效率”与“正确性”

  • beam 更窄,成本更低;
  • 但漏证据风险更高。

3. 它连接了“规划”与“校准”

  • 如果路径分数不校准;
  • beam search 的早期决策就更容易偏。

这也说明它和 GraphRAG中的Retrieval Calibration 是强相关问题。

可以把当前 GraphRAG 的搜索路线粗分成三类

2. Soft graph propagation

  • 代表:HippoRAG、LinearRAG
  • 特点: 不急着离散决定单一路径,而是先传播相关性。
  • 代表:GeAR、Graph-R1、Relink
  • 特点: 搜索不是一次定死,而是允许根据中间状态重规划。

常见误区

误区 1:beam search 只是实现细节

  • 不是。
  • 它在定义系统允许保留多少潜在证据链。

误区 2:更深的搜索一定更完整

  • 不一定。
  • 如果评分函数本身有偏差,搜得更深只会更深地走错。

误区 3:只要最终答案对了,搜索偏差就不重要

  • 错。
  • 对理论分析而言,搜索偏差决定了方法是否可泛化、是否稳定、是否可解释。

更深的问题

  1. GraphRAG 能否定义 practical completeness 的统一指标?
  2. beam width、路径长度、seed quality 三者如何共同决定漏检概率?
  3. soft search 与 hard search 的最优分工在哪里?
  4. replanning 是否能系统性修复 beam bias,还是只是增加算力换收益?

相关笔记


这是一篇概念笔记,用于解释 GraphRAG 中搜索预算、剪枝策略与最终证据完整性之间的关系。