遍历树：一种zero-shot推理算法，用于将知识图谱对大语言模型进行增强

摘要

知识图谱（KG）正好能补上大语言模型（LLM）的短板——它提供的是可靠、结构化、领域专属且实时更新的外部知识。但问题是，这两者通常各自独立开发，只能在训练完成后才尝试集成。为了解决这个痛点，我们提出了一种全新的零样本推理算法：遍历树（Tree-of-Tra versals）。它能让一个或多个KG无缝增强任何黑箱LLM，不需要额外训练。算法给LLM装备了一套与KG交互的操作，同时支持在可能的思维和行动上进行树搜索，从而找到最可靠的推理路径。我们在两个主流基准数据集上进行了评估，结果非常明确：遍历树显著提升了问答和KG问答任务的表现。代码已开源，地址在 https://github.com/amazon-science/tree-of-tra versals。

1 引言

大语言模型（LLM）现在已经被广泛用在信息检索、摘要生成、问答这类知识密集型任务上。靠着海量文本训练，它们确实学到了不少东西。但短板也很明显：会瞎编（幻觉）、缺乏深度的领域知识、而且知识截止在训练结束那一刻，没法自动更新。

而知识图谱（KG）恰恰能补上这些弱点。它包含了最新的信息，不论是一般常识还是特定领域知识，都以高度结构化和可解释的方式组织起来。如果把LLM的自然语言推理和生成能力，跟外部KG的最新知识结合起来，我们就有机会得到更可靠、更真实的LLM系统。

随着LLM能力的爆发，把两者结合的想法又热了起来。最近不少综述和立场文章都重点谈了这种结合潜力。现有的做法花样很多：有人把KG数据直接融入预训练、微调或者后续训练阶段。但所有这些方法都有硬伤——训练或微调大规模LLM的成本太高了；有些模型权重压根不公开；而且最大的KG自己就得专门建服务器，根本没法跟LLM塞到同一个内存里。再说了，之前的工作基本都没考虑过同时用好几个KG的情况。

所以，如果能有一种算法，既不需要从头训练或微调模型，又可以让强大的黑箱LLM任意对接内部或外部的多个KG，那价值就太大了。这种零样本算法能解锁一堆新应用场景，比如：客户用着黑箱LLM API的同时，把自己的领域KG加进去；把个性化KG集成到LLM里，还不用冒着用个人数据训练模型的风险；通过一系列能通过API访问的KG（例如MusicBrainz），把深度的领域知识也带进来。

于是我们设计了遍历树（Tree-of-Tra versals）——一种全新的算法，通过零样本的方式，把任意数量的KG增强到任何强大的LLM里。它不需要训练，只要黑箱访问LLM就行，而且对任何能通过API访问的KG都适用。具体贡献包括：

1. 遍历树算法：零样本增强LLM与任意多个KG，并用树搜索实现高级KG推理。
2. 在两个问答任务（2WikiMultiHop和QALD-10）上评估遍历树，并与基线方法对比。
3. 开发了一个新的测试数据集，用于在通用和领域专用KG上进行组合推理，并在此数据集上评估了遍历树。

我们在Amazon Bedrock上对三种不同规模的模型做了详细的实验分析，还进行了消融研究。详细结果见后文。

2 遍历树

遍历树算法会维护一个局部的知识图谱子图，这个子图会不断扩展，直到LLM拿到回答给定查询所需的全部信息。一开始，局部子图只包含原始查询中提到的实体。接着，算法通过树搜索来决定LLM该生成什么动作和思维，再通过KG接口从外部KG里抓取相关知识，一步步把子图撑大。当LLM利用当前局部子图作为上下文已经能回答查询时，算法就停下来。遍历树主要由三个组件构成：(1) 一个KG接口，用来跟一个或多个KG交互；(2) 一个动作状态机（ASM），它是一个有限状态机，定义了LLM在跟KG交互以扩展局部子图时，可以执行哪些动作、处于什么状态，以及使用哪些提示模板；(3) 一个树搜索算法，它决定了LLM的整体搜索轨迹——比如用最佳优先搜索、出错时能回溯，以及找到答案时怎么终止。

2.1 知识图谱接口

KG接口的作用是让遍历树能跟一个或多个KG交互。假设有个KG叫K。实体有标识符、标签和可选描述（例如Q35332，‘克里斯托弗·诺兰’，‘英美电影制作人’）。关系类型也有标识符、标签和可选的逆标签（例如P57，‘导演’，‘是……的导演’）。边（事实）是 (s, r, o) 的三元组，比如 (‘盗梦空间’，‘导演’，‘克里斯托弗·诺兰’)。只要实现了下面三个方法，遍历树就能直接用这个KG：

1. init(q)：输入查询q，从q中提取实体，返回链接后的实体列表。

2. get_relations(E)：输入一组实体E，返回它们在KG K中涉及的所有关系类型。

3. get_edges(E, r)：输入一组实体E和一个选定的关系类型r，返回所有源实体在E中且关系为r的边，同时也返回通过这条边到达的新实体。

如果有条件，这个接口可以用SPARQL实现；否则就改用KG自带的图API。对于多个KG，每个接口各自独立实现。

2.2 动作状态机 (ASM)

设计一个能跟任意KG配合的零样本LLM算法，难点在于：LLM事先不知道图里都有哪些关系类型，也不知道某个实体下哪些关系有效。少样本或上下文学习只能覆盖少数关系（比如Wikidata有超过11,000种关系类型），根本不够用。

怎么解决？我们把扩展局部KG子图这个任务拆成了几个子任务，用一个有限状态机来管，状态包括：思考（Think）、回答（Answer）、扩展KG（ExpandKG）、选择实体（Select_Entities）、选择关系（Select_Relation）；状态有：默认（default）、选择实体（selecting-entities）、选择关系（selecting-relation）和完成（done）。具体状态机如图2所示，我们称它为动作状态机（ASM）。

从默认状态开始，遍历树可以选择思考、回答或扩展KG。一旦选了扩展KG，它先被提示去选一个需要更多信息的实体（比如图1里的“盗梦空间”）。然后，它从KG接口的get_relations方法返回的候选关系列表里挑一个。挑完关系（比如“演员”），所有源实体是所选实体、关系是所选关系的边就会被加入局部KG子图。接着，遍历树又可以选回答、思考或继续扩展。

ASM里的每个状态（除了“完成”状态）都配有一个独特的提示模板。模板在给LLM前，会填上局部KG子图和KG接口的信息。每个状态定制提示，就能给LLM最精确相关的信息，配上具体指令，让任务简单多了。例如，“选择实体”的提示会把局部子图里可选的实体列出来（见图3）。所有状态的提示模板见附录F.1 - F.3。

局部KG子图用一种token高效的YAML格式来表示，避免同一个实体的多条边重复描述。

除了初始化阶段，ASM还需要调用KG接口两次：(1) 在构建选择关系提示时，算法调用get_relations来收集可选关系；(2) 选好关系类型r后，从选择关系状态转到默认状态时，算法调用get_edges，把新边和新实体加入局部子图。

2.3 树搜索算法

我们的方法受到了“思维树”（Tree-of-Thoughts）的启发：同时生成多个思维来增强LLM推理，并在生成的推理链上建搜索树。我们把它扩展了一下——允许生成动作来增强LLM跟KG的结合，并在动作上建搜索树。因为“思维树”本来没有设计动作，也不是针对知识密集型问答的，所以有些新挑战。我们做了几点修改：通过ASM引入动作；调整了搜索过程和停止条件，更好适应问答；还用了一种不同的采样方法来提高多样性。

“遍历树”会为每个节点计算一个值，表示它的效用。这个值由LLM用评估提示来生成（算法1中的evaluate步骤）。值在0到1之间，1代表效用最高。我们用了两种评估提示：一种用于中间状态，另一种用于答案状态。提示包含原始查询、局部KG子图、之前动作的轨迹，再加上评估节点的指令（见附录F.4和F.5）。这些值用来引导动作空间的探索——choose_node会返回未探索节点中值最高的（最佳优先）；如果多个节点值相同，就用深度优先搜索。

在某些情况下，通过ASM和KG接口，只用一条思维-动作序列就能找到答案。这相当于分支因子b=1的“遍历树”，我们叫它“遍历链”（Chain-of-Tra versals）。拿它来做对比实验，结果也证实了多分支的好处。

2.4 多知识图谱的遍历树

给LLM增强多个KG，主要就是给每个额外KG都搭一个KG接口。算法还有几处变化：(1) 初始化时从查询q中提取的实体，需要跟每个KG接口做匹配；(2) 展示关系选项时，对每个KG接口都调用get_relations；(3) 当新实体加入局部KG子图时，对其他KG接口也调用一次实体链接函数。这个实体链接函数可以在KG接口里单独实现，也可以回退到init(o)（其中o是新实体的文本标签）。这样一来，如果不同KG之间有显式链接就能用上，没有的话也不影响基本功能。

3 实验

我们用三种模型来评估遍历树：Claude-Instant (claude-instant-v1)、Llama2 70b (llama2-70b-chat-v1) 和 Llama2 13b (llama2-13b-chat-v1)。AWS Bedrock通过一个API就能按需访问各种基础模型，包括开源和黑箱模型——这正是遍历树设计要应对的场景。

3.1 任务和数据集

我们先用两个常用的LLM知识评测任务来评估遍历树：2WikiMultiHop和QALD-10。为了测试需要从多个KG推理的复杂问题，我们还自己建了一个新数据集。

数据集是从HotPotQA里提取多跳模板生成的，把模板组合起来能产生复杂的推理问题，再生成与Wikidata相关的候选问题，最后确认每个边上的实体在维基百科段落里都出现过。答案可以从维基百科和Wikidata推出。我们从测试集中按ReAct的方法抽了500个问题（采样种子值233）。

是一个多语言KGQA数据集，包含395个人工问题，翻译成其他语言后再转换成对Wikidata的SPARQL查询。这些问题在推理结构上比2WikiMultiHop的更多样（比如要求多个答案或聚合操作）。我们用的是英文版本。

是遍历树的一个新用例：需要合成和推理多个KG源。目前还没有现成的数据集要求从多个KG合成信息来回答一个问题。所以我们自己建了一个——MusicBrainz-x-Wikidata，包含109个需要同时用MusicBrainz和Wikidata推理的问题。跟包含通用知识的Wikidata不同，MusicBrainz是音乐领域的深度专业数据库，大部分内容LLM不太可能知道。我们跟人工标注者一起构建了这个数据集，给出了如何在两个KG间找推理路径的指示、关注的问题类型和一些示例。经过审核的问题都检查了模糊性和合理性。每个问题都设计成必须从两个KG提取信息才能成功回答。另外，除了2WikiMultiHop中的推理类型，这个数据集还包含聚合、聚合比较、资格限定以及这些类型的复杂组合。示例见图3.1。详细指示、问题类型和示例见附录A。

在2WikiMultiHop数据集上的EM-in。*表示在没有答案时回退到链式思维。*表示此类情况的数量。

3.2 评估指标

我们使用精确匹配包含（EM-in）作为评估指标：如果真实答案以完全匹配的形式出现在模型输出中，就算1分，否则0分。这考虑到了LLM可能用不同语法输出答案的情况。这个指标很常用，有时也叫精确匹配（EM）。当答案有多个时，我们计算所有标签的平均EM-in。

3.3 比较基准

我们选了三种跟任何黑箱LLM都能配合的方法做对比：(1) 思维链（Chain-of-Thought, CoT）提示；(2) ReAct——在生成思维和从文本知识库（如维基百科）搜索、检索之间迭代；(3) 前瞻性主动检索（Forward Looking Active Retrieval, FLARe）——在生成思维和从知识库检索以纠正不准确信息之间迭代。

3.4 实现细节

所有模型，不需要多样本时用采样温度0.0，需要多样本时用温度1.0。我们在两种设置下测试：分支因子b=1（遍历链）和b=3（遍历树）。两种设置最大深度都是7——深度7之后默认动作状态只能选回答问题。遍历树的最大总扩展次数设为20。答案阈值τ设为0.8——对应评估提示（附录F.5）中由KG支持的高置信度答案。

对于2WikiMultiHop和QALD-10，我们使用Wikidata作为KG。对于MusicBrainz-x-Wikidata，除了Wikidata还用了MusicBrainz。Wikidata的KG接口通过SPARQL实现，MusicBrainz的通过其API实现。

图5：模型分配值为0.0或1.0的答案的EM-in准确性及其对应的真实EM-in得分。这包括所有提出的答案，而不仅仅是模型返回的最终答案。

4 结果与讨论

表1展示了我们在2WikiMultiHop和QALD-10上的实验结果。对于所有模型，遍历树在2WikiMultiHop上都优于基线，在零样本设置下刷新了这些任务的最好成绩。我们推测，这个提升主要来自遍历树通过KG接口访问知识库，以及由ASM引导的思维-行动过程。这一点很明显——即使不做树遍历（遍历链，包含多个思维/动作、回溯和节点值计算），它在2WikiMultiHop上也明显优于ReAct的知识基础：所有模型平均准确率高出ReAct约xx%。跟遍历链相比，遍历树进一步提升了性能：在2WikiMultiHop上平均提高了约xx%的绝对准确率，在QALD-10上提高了约xx%。值得注意的是，模型本身越强，从树遍历中获益也越多——Llama-70b和Llama-13b的差异就说明了这一点。

在MusicBrainz-x-Wikidata（表2）上，问题需要访问两个KG，推理挑战很大。遍历树相对于遍历链的平均相对提升约为xx%，如表2所示。遍历链和遍历树在该数据集上都优于思维链。我们只跟思维链比较，因为其他检索方法在MusicBrainz知识库上的覆盖率太低。

图6：在需要回溯的2WikiMultiHop问题上，有回溯和没有回溯的结果比较。如果不允许回溯，性能会大幅下降。

4.1 价值函数的影响

遍历树依赖价值函数的信号来选择最终的树轨迹。如果这些值是随便给的，那遍历树不会比遍历链更好。图5显示所有模型的价值函数都传递出了有意义的信号：对于评分为1.0与0.0的答案，准确率之间的平均性能差异约为xx%。这意味着选评分为1.0的答案比选0.0的答案平均好约xx%。每个模型价值函数的个体特征见附录C。

4.2 回溯的影响

要弄清回溯在遍历树中的作用，我们可以问一个反事实问题：如果模型不能回溯，表现会怎样（图6）？我们把分析限制在2WikiMultiHop中那些遍历树在某个子树上生成了答案、但模型最终又回溯到之前的子树的题目（即我们有反事实情况）。因此这类问题通常比整体分布更难。在这些情况下，我们比较了两种结果：如果直接从第一次搜索的子树上取最高价值的答案，跟回溯后最终答案的对比。结果发现，回溯的能力让遍历树的准确率显著提升，范围从xx%到xx%。

4.3 在 MusicBrainz-x-Wikidata 上的表现

对于MusicBrainz-x-Wikidata数据集，我们只跟思维链比较，因为其他基线方法没法访问类似音乐领域的知识库。即便如此，观察到的结果很有意思：思维链在MusicBrainz-x-Wikidata上的表现远不如在完全基于Wikipedia/Wikidata的通用数据集（2WikiMultiHop上约xx% vs 这里约xx%）。原因可能是LLM在大量通用知识（如Wikipedia）上训练过，但在音乐这种专业领域上数据很少。除了KG接口和带ASM的遍历树，这也能解释为什么遍历树在MusicBrainz-x-Wikidata上的表现是思维链的2.2倍。这凸显了用领域专用KG和/或多个KG增强LLM的重要性——而遍历树恰好能做到这一点。

4.4 基线分析

大多数情况下，ReAct表现不如思维链。原ReAct论文也提到过，他们的方法显著减少了幻觉，但准确率稍低。因此回归思维链反而让Llama2-70b和Claude-Instant的准确率提高了。我们发现claude-instant在ReAct上的表现远低于Llama2-70b，主要原因是claude-instant会拒绝“搜索”人，并在执行无效操作后道歉。尽管如此，FLARe在2WikiMultiHop上提升了模型性能，但在QALD-10上没有。这可能是因为2WikiMultiHop的文本知识库之间有更好的重叠。

5 相关工作

过去大量研究关注用知识图谱回答问题，大致分两类：把问题解析成逻辑形式的方法，和信息检索方法。

最近，研究人员开始探索如何用知识图谱增强预训练语言模型和LLM。很多工作通过训练把KG数据融入LLM，通常会改模型架构。一些成功地用了专门的图编码层。有些试图把这个过程跟语言模型预训练结合在一起。但这种在LLM训练过程中加入KG的做法有几个局限：模型无法在不重新训练的情况下纳入KG更新，无法更换KG源（比如换成领域专用KG），而且可能因为把知识学到权重里导致可解释性差。另外，这些方法增加了训练复杂度、提高了成本，而且没有模型权重就不能用。所以扩展这些方法风险很大。

其他方法把KG当作更完整的真实来源，让LLM生成针对KG的结构化查询。相关工作教会LLM生成逻辑KG查询，返回匹配的实体。这些方法跟前面说的语义解析法有相似之处。但通过返回逻辑查询，失去了LLM的推理和常识能力。

也有一些方法研究把KG或知识库数据直接注入LLM提示中。很多是一次性检索，采用密集段落检索等机制。这些方法回答不了复杂的多跳问题，因为第一次检索很可能不包含后面需要的二三级信息。后来有了迭代检索的方法：例如FLARe用即将生成的句子的预测来检索相关文档，并在句子出现高置信度token之前不断重写。多轮问答格式中也用了多轮检索。ReAct做多轮思考和行动来查询基于文本的知识库。还有研究跟KG进行重复交互。另一些平行工作探索了用路径和邻域搜索方法为LLMs构建KG上下文。这些方法都没有结合树搜索或超出LLM固有能力的高级推理形式，没法探索多个推理路径或方案，犯错时也不能回溯。所以能力受限。而且，上述方法都没有探索对多个KG的推理。

一些研究探讨了来自不同领域的问题的问答——学习在不同领域专用的问答模型之间做选择，每个模型只在一个知识库上训练。除了需要训练，这类系统还无法回答需要从不同领域综合信息的问题。

6 结论

遍历树是一种强大的算法，它让LLM在无需示例、无需依赖图模式、也无需训练的条件下，就能利用知识图谱进行推理。我们在多个LLM和数据集上通过实验展示了它的有效性。希望遍历树能继续演进，我们认为研究与个性化用户知识图谱以及其他领域专用数据集的集成非常有价值。

7 限制

遍历树比简单的检索方法要慢。改善价值函数能通过避免探索错误路径来减少LLM和KG API的调用次数。也可以考虑工程优化，比如托管图服务器来加速LLM和KG访问。在token成本上，KG的文本表示比很多使用非结构化知识库的检索方法更省token（后者往往用满上下文窗口）。不过跟非检索基线比，token使用成本确实明显增加了。

能回答的KG问题类型受限于上下文窗口、搜索深度和LLM自身的推理能力。比如一个非常大的聚合问题（“有多少座山海拔超过3500米？”）需要的实体数量会超过LLM上下文能容纳的。未来可以考虑往ASM里加其他操作，比如聚合，这样就能把局部KG浓缩成更相关的信息。

EM-in指标也不完美。日期、数字格式、文本格式和别名的差异可能导致假阴性；如果模型没有明确回答但响应里包含了正确答案，又可能出现假阳性。

8 伦理影响

我们不预期遍历树会引入全新的风险领域，但它可能对现有LLM或KG的风险产生尚未研究的影响。强调以下几点：(i) 遍历树在训练后为LLM提供了新能力，在准确性上是正面的，但我们还没评估它对更广泛安全指标的影响。(ii) 我们的评估只限于英文版本的KG和数据集，应该在更多语言中评估以确保公平。(iii) 我们还没在误导性或欺骗性KG下做分析。使用可公开修改的KG，确实存在信息被欺骗性篡改的风险。

在积极方面，公开这项研究让知识增强的LLM变得更加民主化——因为这种方法不需要大量的训练投入或自己掌握语言模型。

MusicBrainz x Wiki

关于MusicBrainz x Wiki数据集创建的附加信息。

A.1 创建步骤

该数据集由标注者以半自动方式创建。我们开发了一个自动化工具来支持以下过程：

• 查找在MusicBrainz和Wikidata中都存在的各种类型的链接实体（艺术家、标签、地点、事件等）
• 查找可用于问题中完美识别上述实体的相关实体（例如，底特律老虎队拥有的地方 → 老虎体育场）
• 查找可用于问题中模糊识别链接实体的相关实体，以便添加限定词来消歧
• 计算每个关系类型在Wikidata或MusicBrainz中的边数

我们用这些工具创建了一组初始的多跳问题，属于特定推理类别。然后让人工标注者检查每个问题的合理性（语法正确且可明确理解）和模糊性（只有一个正确答案）。如果可能，问题会被重新措辞或修正以避免歧义。最终得到109个问题。

A.2 问题的组成

Musicbrainz x Wiki的问题组成见表3。

A.3 标注者

标注者由大约10名研究科学家和工程师组成，均为英语母语者，均位于美国。

B 实现细节

B.1 多样性过采样

思维树有个问题：当可选选项受限时，LLM会变得重复，无法产生多样化的输出。他们的解决方案是用“提议提示”加上额外指示来生成多个不同想法，但这样只为完成相关任务就增加了不少复杂度。我们用一个更简单的办法：通过过采样来生成多样化的动作。具体来说，如果分支因子是b，我们就从LLM采样k>b个可能的动作，然后提取前b个独特的动作来用。我们只在选择实体和选择关系时用这个方法，因为动作选择有限又需要多样性。这个改动不会明显增加计算成本——同一个提示采样多个动作，而平均提示输入大小（几百到几千token）通常远大于这些动作的平均生成长度（~10 token）。因为多个动作是并行采样的，延迟也差不多。通过这种方式，我们总能在选实体或选关系时得到多样化的选项。

B.2 超参数

遍历树的超参数不多。大部分是通过分析选择的，少数基于初步实验。分享一下选择依据：

τ通过分析评估完成状态的提示（附录F.5）选中0.8，这样遍历树只在确信答案得到KG支持时才停。

温度选1.0以促进多样性。如果跟其他能调温度的模型一起用，建议做超参数调优，或者每种类型用样本提示并分析温度，使输出多样但合理。

分支因子b=3基于小规模实验。b太大会增加搜索时间和成本；太小又缺乏多样性。值得注意的是，即使b=3且用了多样性采样，有时实际唯一的输出数量也少于3。

最大深度通过分析选定，在能回答大多数问题的同时尽量小。有些QALD-10和MusicBrainz-x-Wikidata的问题需要更大深度才能回答。

最大扩展截止纯粹为了防止模型在单个问题上停留太久，实际值有些随意，对准确性影响很小。

B.3 KG 接口

提供一些KG接口的额外细节。

init函数分三步：先用LLM调用和提示提取命名实体；然后对每个提取的实体用KG API搜索候选项；最后用另一个LLM调用把提取的实体与最佳候选项匹配。

get_relations和get_edges完全通过各自的KG API实现。对于Wikidata，通常是一个或两个SPARQL查询（正向和反向边）。对于MusicBrainz，需要多个API调用，因为不同类型实体有不同端点（例如艺术家和录音是分开的）。

C 值函数特征

我们对每个模型的价值函数进行了分析。图7展示了各模型在2WikiMultiHop上个体答案价值与准确性的关系。所有模型的答案价值与答案准确性之间都有正相关。但如预期，Llama2-13b的相关性最低，Claude-Instant最高。

答案按是否被评正确分开。我们预期导致正确答案的行为价值高于导致错误答案的行为。可以清楚看到正确分布的峰值在错误分布的右侧，在Llama2-13b上最不明显——这也合理。我们还注意到Llama2模型与Claude-Instant的分布形状不同。

这些结果表明，更大更强的模型在价值函数上可能会有更多改进空间，从而从遍历树中获得更大收益。

D 提示工程

我们的方法和ReAct在切换模型时，都需要稍微重新设计提示。主要是调整输出格式。比如，Llama2会以“所以下一个动作应该是”开头，而我们要求动作以“THINK”、“EXPAND_KG”或“ANSWER”开头。所以我们把“所以下一个动作应该是:”直接写进提示，让输出直接以所选动作开始。对于选择实体，我们加了“您已选择以下实体进行扩展:”；对于选择属性，加了“我建议选择属性:”。这些问题也可以通过修改解析代码解决。

E Fallback to Chain-of-Thought

当深度7之后没有提供答案，或者答案中间出现了以下短语之一：’determine’, ’unable’, ’cannot’, ’unknown’, ’unsure’, 或 ’not possible’，我们会回退到思维链作为ReAct基线。虽然这些短语有时也出现在有意的答案里，但我们发现它们在非答案风格的响应中间出现更一致、更专一。

图7只看了最终答案状态的价值函数，因为只有这些状态才直接跟准确性评分相关。虽然准确评估答案状态更重要，但我们也希望中间状态的值传递一些有用信号。图8显示了搜索路径上节点的平均值。

(c) claude-instant

图7：所有Tree-of-Tra versals答案在2Wiki上的EM-in准确性与价值函数的关系。点的分布经过抖动处理。趋势线显示了相关性和p值。

图8：沿着到每个答案路径的中间步骤的平均价值函数，按答案是否被评分为正确或错误进行分离。对于模型提出的每个答案，路径上的评分被平均，结果分布被绘制。数据来自2WikiMultiHop结果。

F Prompts

以下页面包含在遍历树中使用的提示。根据查询、知识图谱状态和行动历史而变化的动态组件以颜色显示。

F.1 默认动作状态的提示

F.2 选择实体的动作状态提示

F.4 一般提示用于评估

原始查询：鲍勃·迪伦的外祖母是谁？知识图谱实体：Q392：鲍勃·迪伦 - 美国歌手兼词曲创作人 Q62519478：比阿特丽斯·斯通 Q62519478：弗洛伦斯·萨拉·斯通 知识图谱边缘：鲍勃·迪伦：母亲：比阿特丽斯·斯通 比阿特丽斯·斯通：母亲：弗洛伦斯·萨拉·斯通 提供的答案：答案是弗洛伦斯·萨拉·斯通。你的任务是根据原始查询和知识图谱对提供的答案的正确性进行评分。给出一个从0.0到1.0的悲观评分，表示答案正确的可能性。

0.0 如果绝对错误

0.0 如果无法根据知识图谱回答

0.5 如果不确定

0.7 如果可能正确但在知识图谱中未确认

1.0 如果绝对正确并在知识图谱中确认。给出推理以得出正确答案。然后提供一个评分。例如，推理...因此提供的答案的评分应该是..."