摘要

知识图谱（KGs）通过提供可靠、结构化、特定领域和最新的外部知识来补充大型语言模型（LLMs）。然而，KGs和LLMs通常是分开开发的，必须在训练后进行集成。我们引入了遍历树（Tree-of-Traversals），这是一种新颖的零-shot推理算法，能够将一个或多个KGs增强到黑箱LLMs中。该算法为LLM提供了与KG接口的操作，并使LLM能够对可能的思维和行动进行树搜索，以找到高置信度的推理路径。我们在两个流行的基准数据集上进行了评估。我们的结果表明，遍历树显著提高了问答和KG问答任务的性能。代码可在 https://github.com/amazon-science/tree-of-traversals 获取。

1 引言

大型语言模型（LLMs）被用于一系列知识密集型任务，如信息检索、摘要生成和问答。经过大量文本数据的训练，这些模型学习了广泛的信息。然而，LLMs存在几个局限性——它们会产生虚构的信息，缺乏深层次的领域特定知识，并且在训练结束时具有静态的知识截止点。

知识图谱（KGs）自然地补充了LLMs的弱点。KGs包含最新的信息，涵盖一般和/或领域特定的主题，以高度结构化和可解释的格式呈现。通过将LLM的推理和自然语言响应能力与外部KG的最新知识相结合，提供了一条通向可靠和真实的LLM的路径。

强大的LLMs的崛起以及新能力的出现重新激发了将LLMs与KGs结合的兴趣。最近，许多调查和立场论文强调了它们的结合潜力。现有的工作通过多种方式增强了LLMs与KGs的结合，例如集成到预训练、微调或后续训练组件的适应中。所有这些方法都有一些局限性。特别是，训练或微调大规模LLMs的计算成本很高。在某些情况下，模型权重并未公开可用。最后，最大的KGs需要自己的服务器，无法与LLMs在内存中集成。此外，以前的工作没有考虑与多个KGs结合的情况。

一种允许将强大的黑箱LLM与任意数量的内部或外部KGs结合，而无需从头开始训练或微调模型的算法是非常有价值的。这种零-shot算法将使多个创新用例成为可能，例如（1）客户在使用黑箱LLM API的同时结合内部领域特定KG，（2）将个性化KG集成到LLM中，而不必承担使用此类个人数据训练模型的风险，（3）通过一系列可访问API的KGs（例如，，MusicBrainz 2）集成深层领域知识。

我们介绍了Tree-of-Traversals，这是一种新颖的算法，通过允许以零-shot方式将任意数量的KGs增强任何强大的LLM，从而解决上述问题。它不需要训练，能够与LLM进行黑箱访问，并且可以与任何可访问的KG API一起使用。我们的贡献包括：

1. Tree of traversals：一种新颖的零-shot算法，用于增强任何强大的LLM与任意数量的KGs，并通过树搜索实现高级KG推理。
2. 在两个问答任务上评估Tree-of-Traversals：2WikiMultiHop和QALD-10，并与基线进行比较。
3. 开发一个新的数据集，以测试在一般和领域特定KG上进行组合推理，并在该数据集上评估Tree-of-Traversals。

我们在Amazon Bedrock上对三种不同规模的模型进行了详细实验，并呈现了详细的消融研究。

2 遍历树

遍历树算法维护一个局部知识图谱子图，该子图会不断扩展，直到包含大型语言模型（LLM）回答给定查询所需的所有信息。开始时，局部知识图谱子图被初始化为包含原始查询中存在的实体。然后，它使用树搜索算法进行扩展，以选择LLM生成的动作和思维，从而通过知识图谱接口从知识图谱中获取相关知识。当LLM能够使用局部知识图谱子图作为上下文来回答原始查询时，算法停止。遍历树由三个主要组件组成。(1) 一个知识图谱接口，用于与一个或多个所需的知识图谱进行交互。(2) 一个动作状态机（ASM），这是一个有限状态机，定义了LLM与知识图谱交互以扩展局部知识图谱子图时的可行动作、状态和提示模板的空间。(3) 一个树搜索算法，定义了整体LLM搜索轨迹，例如最佳优先搜索、在犯错时回溯，以及找到答案时的终止条件。

2.1 知识图谱接口

知识图谱接口允许树遍历与一个或多个知识图谱（KG）进行交互。设 为单个知识图谱。 是实体的集合，每个实体由一个标识符、一个标签和一个可选描述组成（例如，Q35332，‘克里斯托弗·诺兰’，‘英美电影制作人’）。 是关系类型的集合，每个关系类型由一个标识符、一个标签和一个可选的逆标签组成（P57，‘导演’，‘是……的导演’）。  是知识图谱中的边或事实的集合，其中每个 s 的形式为 ，其中 且 ，例如， (‘盗梦空间’，‘导演’，‘克里斯托弗·诺兰’)。只要实现以下接口，树遍历就可以用于知识图谱 K：

1. ：它以查询 为输入，从 中提取实体，并返回链接的实体 ，其中 是在 中引用的实体。

2. get_relations ：它接受一组实体 ，并返回关系类型 ，这些关系是 在知识图谱 K 中的关系：

3. get_edges ：它接受一组实体和一个选定的关系类型，并返回所有与关系类型 相关的边，源实体在 中：。它还返回通过 到达的新实体 。

当可用时，此接口通过 SPARQL 查询实现；否则，我们使用可用于知识图谱的图形 API。对于多个知识图谱，每个接口单独实现。

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）。

从默认状态开始，遍历树（Tree-of-Traversals）可以选择思考、回答或选择扩展 KG。在遍历树选择扩展 KG 后，它首先被提示选择需要更多信息的实体（例如，图 1 中的“盗梦空间”）。然后，它被提示从 KG 接口的 get_relations 方法提供的候选关系列表中选择关系。在选择关系后（例如，图 1 中的“演员”），所有包含所选实体作为源和所选关系作为关系的边都被添加到本地 KG 子图中。遍历树随后能够再次回答、思考或扩展 KG。

提示模板。ASM 中每个状态（除了“完成”状态）都与一个独特的提示模板相关联。提示模板在呈现给 LLM 之前，会填充来自本地 KG 子图和 KG 接口的信息。为每个状态定制的提示使我们能够向 LLM 提供精确和相关的信息，以及每个状态的具体指令，从而简化 LLM 的任务。例如，“选择实体”的提示展示了可供选择的实体选项，这些选项在本地 KG 子图中（见图 3）。所有状态的提示模板在附录 F.1 - F.3 中。

本地 KG 子图使用一种令牌高效的 YAML 格式表示，以最小化对同一实体的多个边的重复。

调用 KG 接口。在初始化之外，ASM 需要调用 KG 接口的两次情况：（1）在构建选择关系提示时，算法调用 get_relations 以收集可用的关系选择。（2）在选择关系类型 后，从选择关系到默认状态的转换中，算法调用 ，以便将新的边和实体添加到本地子图中。

2.3 树搜索算法

我们的方法受到“思维树”方法的启发，在该方法中，通过允许同时生成多个思维，增强了大型语言模型（LLM）的推理能力，并在生成的推理链上构建搜索树。我们扩展了这种方法，通过允许生成动作来增强LLM与知识图谱（KG）的结合，并在它们上构建搜索树。由于“思维树”并未设计为包含动作，也未针对知识密集型问答任务，因此出现了一些挑战。因此，我们引入了一些修改：通过ASM引入动作，稍微不同的搜索过程和停止条件，以更好地处理问答，以及在进行约束采样时改进多样性的不同采样过程。

值函数引导。“遍历树”计算节点的值以确定其效用。该值由LLM使用评估提示生成（算法1中的步骤evaluate）。值可以在0到1之间，其中1表示最高效用。我们使用两种类型的评估提示：一种用于中间状态，另一种用于答案状态。提示包括原始查询、局部知识图谱子图、先前动作的轨迹，后跟评估节点的指令（见附录F.4和F.5）。这些值随后用于引导动作空间的探索。具体而言，choose_node返回具有最高值的未探索节点（最佳优先）。如果存在具有相同值的节点，则使用深度优先搜索。

遍历链。在某些情况下，我们可以使用ASM和KG接口通过单一的思维和动作序列找到查询的答案。这相当于分支因子为的“遍历树”。我们将其称为“遍历链”。虽然有助于比较，但实验表明考虑多个分支的好处。

2.4 多知识图谱的遍历树

增强一个大型语言模型（LLM）与多个知识图谱（KG）主要涉及为每个添加的知识图谱构建知识图谱接口。算法还有一些其他的变化。(1) 在初始化（q）中提取的实体与每个知识图谱接口进行匹配。(2) 在选择关系时展示关系选项时，get_relations 在每个知识图谱接口上被调用。(3) 当将一个新实体添加到本地知识图谱子图时，我们为其他知识图谱接口调用一个实体链接函数。我们允许实体链接函数在知识图谱接口中作为一个单独的函数，或者回退到初始化（o），其中 是刚刚添加的实体的文本标签。这使得在可用的情况下可以使用常见知识图谱之间的显式链接，同时仍然能够在没有链接的情况下正常工作。

3 实验

我们使用三种不同的模型评估遍历树：Claude-Instant (claude-instant-v1)、Llama2 70b (llama2-70b-chat-v1) 和 Llama2 13b (llama2-13b-chat-v1)。AWS Bedrock通过单一API提供对各种基础模型的按需访问，包括开源模型和黑箱模型。这正是遍历树所设计的用例。

3.1 任务和数据集

我们首先在两个常用的任务上评估Tree-of-Traversals算法，这些任务用于评估大型语言模型（LLM）的知识：2WikiMultiHop和QALD-10。为了允许对需要来自多个知识图谱（KG）的复杂问题进行测试，我们创建了一个新的数据集，该数据集需要来自多个KG的知识。

2WikiMultiHop数据集是通过从HotPotQA中提取多跳模板构建的，结合模板以获得复杂推理问题，生成与Wikidata相关的候选问题，然后确认每个边的实体提及出现在维基百科段落中。这些问题的答案可以从维基百科和Wikidata中推导出来。我们从测试集中按照ReAct中使用的方法抽样500个问题，包括采样种子值233。

QALD-10数据集是一个多语言知识图谱问答（KGQA）数据集，包含395个由人类创建的问题，翻译成其他语言，然后构建为对Wikidata的SPARQL查询。这些问题在推理结构上比2WikiMultiHop中的问题更为多样（例如，要求多个答案或聚合）。我们使用了英文的问题。

MusicBrainz- -Wikidata数据集是Tree-of-Traversals的一个新颖用例，涉及合成和推理多个知识图谱源。当前没有现有的数据集需要从多个KG中合成信息以回答单个问题。因此，为了测试使用多个KG的推理能力，我们创建了一个新的数据集，MusicBrainz-x-Wikidata，包含109个需要使用来自MusicBrainz和Wikidata的信息进行推理的问题。与包含一般知识的Wikidata不同，MusicBrainz是一个关于音乐产业的深度领域特定数据库。这些信息的大多数内容不太可能被大型语言模型所知。我们与人类注释者一起构建了MusicBrainz-x-Wikidata数据集，提供了寻找这两个KG之间推理路径的指示、关注的问题类型以及一些示例问题。经过策划的问题经过了模糊性和合理性的检查。根据设计，每个问题都需要从两个知识图谱中提取信息，以便成功回答。此外，除了2WikiMultiHop中的推理类型外，该数据集还包含涉及聚合、聚合比较、资格和这些的复杂组合的问题。示例见图3.1。有关指示、问题类型和示例的详细信息请参见附录A。

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

3.2 评估指标

我们使用精确匹配包含（EM-in）作为评估指标。如果真实答案在答案中以完全匹配的方式出现，则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。我们在两种设置中测试我们的方法：（1）分支因子为 的情况，称为遍历链（Chain-of-Traversals）；（2）分支因子为 的情况，称为遍历树（Tree-of-Traversals）。在这两种设置中，我们将最大深度设置为7，这意味着在达到深度7之后的默认动作状态时，唯一可用的动作是回答问题。对于遍历树，我们将最大总扩展设置为20。答案阈值 设置为0.8，这对应于根据评估提示（附录 F.5）由知识图谱支持的高置信度答案。

对于2WikiMultiHop和QALD-10，我们使用Wikidata作为知识图谱。对于MusicBrainz- -Wikidata，我们在Wikidata的基础上使用MusicBrainz。我们使用Wikidata SPARQL查询实现Wikidata的知识图谱接口，并使用MusicBrainz API实现MusicBrainz知识图谱的接口。

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

4 结果与讨论

表1展示了我们在2WikiMultiHop和QALD-10上的实验结果。对于所有模型，Tree-of-Traversals在2WikiMultiHop上优于基线模型，在零-shot设置下为这些任务设定了最先进的结果。我们假设，这一增益很大程度上归因于Tree-of-Traversals通过提出的KG接口访问知识库，以及其由ASM引导的思维-行动过程。这一点是显而易见的，因为即使是没有进行树遍历的Chain-of-Traversals（包括多个思维/行动、回溯和节点值计算），在2WikiMultiHop上也显著优于ReAct的知识基础：在所有模型的平均值中，准确率比ReA 高出。与Chain-of-Traversals相比，Tree-of-Traversals进一步提高了性能。它在2WikiMultiHop上平均提高了的绝对准确率，在QALD-10上提高了的绝对准确率。我们注意到，模型表现越好，从Tree-of-Traversals中获得的收益就越大，这一点在Llama-70b和Llama-13b之间的差异中得到了体现。

在MusicBrainz- -Wikidata（表2）中，包含需要访问两个KG的具有挑战性的推理问题，Tree-of-Traversals相对于Chain-of-Traversals的平均相对提升为，如表2所示。Chain-of-Traversals和Tree-of-Traversals在该数据集上均优于Chain-of-Thoughts。我们仅与Chain-of-Thoughts进行比较，因为其他检索方法在MusicBrainz知识库上的覆盖率较低。

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

4.1 价值函数的影响

Tree-of-Traversals依赖于价值函数的信号来选择最终的树轨迹。如果这些值是任意的，那么Tree-of-Traversals的表现不会优于Chain-of-Traversals。图5显示了所有模型的价值函数都有一个有意义的信号。对于被评估为1.0与0.0的答案，其准确率之间的平均性能差异为。这代表在选择被评估为1.0的答案时，相较于选择被评估为0.0的答案，平均相对改善为。有关每个模型价值函数的个体特征，请参见附录C。

4.2 回溯的影响

为了确定回溯在遍历树中的影响，我们提出一个反事实问题：如果模型无法回溯，它的表现会如何（图6）。我们将分析限制在2WikiMultiHop问题上，其中遍历树在一个子树上生成答案，并且模型最终在该子树上进行回溯（即我们有反事实的情况）。因此，这些问题通常比整体问题分布更具挑战性。在这些情况下，我们比较如果从第一次搜索的子树中获取最高价值的答案与回溯后最终答案的结果。我们发现，回溯的能力使遍历树的准确性显著提高，范围从 到 。

4.3 在 MusicBrainz-x-Wikidata 上的表现

对于 MusicBrainz--Wikidata 数据集，我们仅与 Chain-of-Thought 进行比较，因为其他基线算法的实现无法访问类似的音乐特定知识库。尽管如此，我们观察到了一些有趣的结果。Chain-of-Thought 在 MusicBrainz--Wikidata 上的表现远不如在完全基于 Wikipedia/Wikidata 的更一般数据集上的表现 对比 。这可能是因为大型语言模型（LLMs）是在大量一般知识（如 Wikipedia 中的知识）上进行训练的，但它们在特定领域（如音乐）上的数据训练相对较少。除了知识图谱接口和带有遍历树的 ASM 之外，这可能是遍历树在 MusicBrainz- -Wikidata 上的表现是 Chain-of-Thought 的 2.2 倍的另一个原因。这表明了用特定领域的知识图谱和/或多个知识图谱增强大型语言模型的重要性，而所提出的遍历树正是能够做到这一点。

4.4 基线分析

在大多数情况下，ReAct的表现不如Chain-of-Thought。这个现象在原始的ReAct论文中被提到，指出他们的方法显著减少了幻觉现象，尽管准确性较低。因此，回归Chain-of-Thought导致Llama2-70b和Claude-Instant的准确性有所提高。我们注意到，claude-instant在ReAct上的表现远远低于Llama2-70b。主要原因是claude-instant拒绝“搜索”人，并在执行无效操作后道歉。尽管如此， CoT在2WikiMultiHop和QALD-10上仍然优于CoT。FLARe在2WikiMultiHop上提高了模型性能，但在QALD-10上没有。这可能是由于2WikiMultiHop的文本知识库之间有更好的重叠。

5 相关工作

知识库问答 过去有大量研究关注使用知识图谱回答问题。研究方法大致可以分为两类：一类是尝试将问题解析为逻辑形式，另一类是信息检索方法。

知识增强。最近，研究人员开始研究如何利用知识图谱增强预训练语言模型和大型语言模型（LLMs）。许多研究集中在通过训练将知识图谱数据纳入LLMs，通常伴随着模型架构的变化。一些研究成功地使用了专门的图编码层。有些研究则试图将这一过程与语言模型的预训练相结合。在LLM训练过程中包含知识图谱的局限性包括：模型无法在不重新训练的情况下纳入知识图谱的更新，无法更改知识图谱来源（例如，特定领域的知识图谱），并且可能由于在模型权重中学习知识而导致低可解释性。此外，这些方法增加了训练过程的复杂性，提高了成本，并且在没有访问模型权重的情况下无法与LLM配合使用。因此，扩展这些方法通常被视为风险过大。

其他方法将知识图谱视为更完整的真实来源，并使用LLM生成针对知识图谱的结构化查询。相关研究教会LLM生成逻辑知识图谱查询，从而返回与知识图谱匹配的实体。这些方法与前面提到的基于语义解析的方法有相似之处。然而，通过返回知识图谱的逻辑查询，这些方法失去了LLM的推理和常识能力。

一些方法研究了将知识图谱或知识库数据注入LLM提示中。许多方法基于查询进行单轮检索，使用检索机制，例如密集段落检索。这些方法无法回答更复杂的多跳问题，因为初始检索不太可能包含最终所需的二级或三级信息。后来的方法使检索过程变得迭代。例如，FLARe使用即将到来的句子的预测来检索相关文档，并在句子包含高置信度标记之前不断再生。在多轮问答格式中使用了多轮检索。ReAct进行多轮思考和行动以查询基于文本的知识库。另一项研究则与知识图谱进行重复交互。在其他平行工作中，探索了使用路径和邻域搜索方法为LLMs构建知识图谱上下文的方法。上述方法没有结合树搜索或超出LLM固有能力的高级推理形式。它们无法探索多个推理路径或解决方案，并且在犯错时无法回溯。这导致能力降低。此外，上述方法均未探索对多个知识图谱的推理。

多知识库问答。一些研究探讨了来自不同领域的问题的问答。这些研究学习在不同领域特定的问答模型之间进行选择，每个模型都在单一知识库上进行训练。除了需要训练，这类系统无法回答需要从不同领域综合信息的问题。

6 结论

遍历树是一种强大的算法，使得大型语言模型能够在没有示例、没有模式依赖和不需要训练的情况下利用知识图谱推理。我们在多个大型语言模型和数据集上实验性地展示了其有效性。我们希望遍历树能够继续发展，并认为研究与个性化用户知识图谱以及其他特定领域数据集的集成具有重要价值。

7 限制

遍历树的速度比简单的检索替代方案慢。改善价值函数将通过避免沿树探索的错误路径来减少 LLM 和 KG API 调用的数量。可以实施其他工程解决方案，例如托管图形服务器，以加速 LLM 和 KG 的访问。在令牌成本方面，KG 的文本表示相比于许多使用非结构化知识库的检索方法是令牌高效的，因为后者往往会最大化 LLM 上下文窗口的使用。然而，与非检索基线相比，令牌使用成本显著增加。

可以回答的 KG 问题类型受到上下文窗口、搜索深度和 LLM 推理能力的限制。例如，一个非常大的聚合（‘有多少座山的海拔超过 3500 米？’）将需要比 LLM 上下文所能容纳的更多实体。未来的工作可以考虑向 ASM 添加其他操作，例如聚合，这可以将本地 KG 提炼成更相关的信息。

EM-in 也是一个不完美的指标。由于日期和数字格式、文本格式以及别名的差异，可能会出现假阴性。在模型没有明确回答但在其响应中包含正确答案的情况下，可能会出现假阳性。

8 伦理影响

我们不预期遍历树会引入新的风险领域，但它可能对现有的LLM或知识图谱的风险产生未研究的影响。我们强调以下几个方面。(i) 遍历树在训练后为LLM提供了新的能力。虽然在准确性方面是积极的，但我们尚未评估其对更广泛安全指标的影响。(ii) 我们的评估仅限于英语版本的知识图谱和数据集。遍历树应在其他语言中进行评估，以确保一致和公平的体验。(iii) 我们尚未在误导性或欺骗性的知识图谱下进行分析。使用一个可公开修改的知识图谱确实存在信息可能被欺骗性更改的风险。

在积极的伦理影响方面，公开这项研究使得知识增强的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 多样性过采样

Tree-of-Thoughts 的一个问题是，当可选择的选项受到限制时，LLM 会变得重复，并且无法产生多样化的输出。它们的解决方案使用了一个“提议提示”，并附加了提出多个不同想法的额外指示。然而，这为仅与完成的任务相关的目的增加了显著的复杂性。我们采用的一个更简单的方法是通过过采样生成多样化的动作。具体来说，如果分支因子为 ，我们从 LLM 中采样 个可能的动作，然后提取前 个独特的动作进行使用。我们仅在选择实体和选择关系时使用此方法，因为动作选择有限且需要多样性。此更改不会明显影响 Tree-of-Traversals 的计算成本，因为对于同一提示采样了多个动作，并且平均提示输入大小（100s-1000s 个标记）通常远大于这些动作的平均生成长度（ 个标记）。延迟保持相似，因为多个动作是并行采样的。通过这种方式，我们在选择实体或选择关系时始终生成多样化的选项。

B.2 超参数

遍历树的超参数数量并不多。大多数超参数是通过分析选择的，尽管有些是基于初步实验选择的。我们分享一些选择它们的信息。

是通过与评估完成状态的提示一起分析选择的（附录 F.5）。选择为 0.8，以便遍历树仅在确信答案得到知识图谱支持时停止。

温度选择为 1.0，以促进多样性。如果与其他可以有温度 的模型一起实现，我们建议进行超参数调优，或使用每种类型的样本提示，并分析选择温度，以便输出多样但合理的动作。

分支因子 是基于小规模实验选择的。较大的 会使模型花费更长时间进行搜索，增加时间和费用。较小的 则不会产生太多的多样性和选项。值得注意的是，即使在 和多样性采样的情况下，有时实际的唯一输出数量也少于 3。

最大深度是通过分析选择的，以便在能够回答大多数问题的同时保持最小。一些 QALD-10 和 MusicBrainz-x-Wikidata 中的问题需要更大的深度才能回答。

最大扩展截止是纯粹为了确保模型不会在单个问题上停留太长时间。实际值有些任意，对准确性的影响很小。

B.3 KG 接口

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

初始化函数是一个三步过程。首先，使用 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 Prompt Engineering

在我们的方法和ReAct之间切换模型时，需要进行一些提示重新设计。这种设计主要限于响应的格式。例如，Llama2会以“所以下一个动作应该是”开始响应，而我们要求动作以“THINK”、“EXPAND_KG”或“ANSWER”开头。相反，我们将“所以下一个动作应该是:”纳入提示中，以便输出以所选动作开始。对于选择实体，我们添加了“您已选择以下实体进行扩展:”。对于选择属性，我们添加了“我建议选择属性:”。这些问题也可以通过更改所呈现提示的解析来解决。

E Fallback to Chain-of-Thought  

当在深度7之后未提供答案，或者当答案中出现以下短语之一时：’determine’，’unable’，’cannot’，’unknown’，’unsure’，或’not possible’，我们将回退到链式思维（Chain-of-Thought）作为ReAct基线。虽然这些短语确实可能出现在有意的答案中，但我们发现它们在非答案风格的响应中出现得更为一致和专一。

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

(c) claude-instant

图7：所有Tree-of-Traversals答案在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 如果绝对正确并在知识图谱中确认。给出推理以得出正确答案。然后提供一个评分。例如，推理...因此提供的答案的评分应该是..."