相关链接:

摘要#

大型语言模型（LLM）越来越频繁地被用于问题解决任务。然而，其战略规划能力常常受到质疑。近期研究引入了蒙特卡洛树搜索（MCTS）算法来增强LLM的规划能力。尽管MCTS具有潜力，但它依赖于大量采样模拟来近似真实奖励分布，这带来了两个主要问题。首先，MCTS在围棋等任务中有效，因为模拟结果可以产生客观奖励（例如，胜为1，负为0）。然而，对于问答等任务，模拟的结果是对问题的答案，如果没有真实答案，就无法产生客观奖励。其次，获得统计上显著的奖励估计通常需要超过30次模拟的样本量，导致过高的令牌消耗和时间消耗。为了解决这些挑战，我们提出了“采用大语言模型专用化MCTS进行战术执行与推理的多智能体系统”（MASTER），这是一个新颖的框架，通过LLM专用化的MCTS来协调智能体的招募与通信。该系统根据任务复杂度自主调整智能体数量，并确保智能体之间专注的通信。在多种任务上的全面实验证明了所提框架的有效性。它在HotpotQA上达到76%的准确率，在WebShop上达到80%，在这些数据集上创造了新的最优性能。

1 引言#

LLM代表了人工智能的一个重要里程碑，并越来越多地被用于问题解决任务（Xi et al., 2023）。然而，由于对其规划能力的担忧，它们在复杂问题上的应用常常受限。LLM根据上下文以“下一个词元概率”的方式生成文本（Vaswani et al., 2017; Huang et al., 2023），但有效的推理需要基于逻辑第一原则、扎根于数据和现实的严格演绎（Valmeekam et al., 2023）。

为了增强LLM的规划能力，近期研究引入了MCTS算法（Hao et al., 2023; Zhou et al., 2024; Wang et al., 2024）。MCTS通过模拟来评估行动的长期后果，并将累积奖励反向传播到树中。这允许基于估计的未来潜力回溯到之前的状态，在利用与探索之间取得平衡。然而，现有工作中使用MCTS存在两个显著挑战：

它依赖外部环境的客观标准来获得模拟奖励，但并非总是可用（例如，在问答任务中，没有真实答案就无法判断答案的正确性）；
它需要大量模拟才能获得统计上显著的奖励，这由于时间和令牌成本而难以持续。

为了应对第一个挑战，某些方法将模拟结果与真实答案进行比较以获得客观奖励（Zhou et al., 2024），但这存在缺陷，因为在问题求解过程中揭示真实答案是不合适的。在应对第二个挑战时，他们限制了模拟次数（Hao et al., 2023）或一旦识别出正确答案就终止过程（Zhou et al., 2024）。然而，如果真实答案仍未披露，这种提前终止方法是不可行的。

这些问题凸显了MCTS的一个关键步骤：模拟。由于这些限制，MCTS被限制在狭窄的应用范围内，并且不能完全兼容LLM。因此，我们提出了一种针对LLM场景定制的MCTS改编版本。我们不再用不确定的奖励进行有限的模拟，而是取消了模拟过程，依靠LLM的自我评估能力来分配奖励。此外，我们提出了几种增强奖励客观性的方法：1）引入一个额外步骤，让LLM在自我评估前提供更多上下文；2）将LLM的置信度作为奖励的权重，以调节其影响；3）保留反向传播机制，以便在初始分配错误时更新奖励。传统MCTS将资源集中在模拟上以近似反映现实，而我们的方法将资源分配到多个步骤，共同确保奖励的准确性和客观性。这就是我们将项目命名为MASTER的原因，因为它通过掌握一系列精细设计来取代MCTS的核心过程——模拟。

本文的另一个贡献是引入了一种新颖的多智能体系统。当前的多智能体系统有两个突出的框架：第一个允许智能体独立创建并自由分享想法。虽然灵活，但这种开放通信可能由于幻觉而导致偏离主题的讨论（Lin et al., 2024; Hong et al., 2023; Xi et al., 2023; Zhang et al., 2024a），从而分散对主要任务的注意力并耗尽用于长对话历史的令牌窗口长度。第二种方法涉及人类创建的智能体，其通信是预定义的。虽然更可控，但这种方法缺乏代码可重用性（Chu et al., 2023）。此外，由于过程是固定的，它无法适应不同难度的任务。它一方面难以应对未预见的复杂任务，另一方面在简单任务上花费不必要的资源。

我们的系统MASTER通过采用LLM专用化的MCTS来引导智能体的创建和交互，从而解决了这些限制。在这个系统中，子智能体响应并基于父智能体的输出进行构建，使得招募和通信更加可控和高效。该系统根据任务复杂度动态调整智能体的数量，确保灵活性。尽管智能体具有相似的配置文件，但它们通过采取不同的行动来扮演不同的角色。与LATS（Zhou et al., 2024）和RAP（Hao et al., 2023）中的节点（代表推理树上的状态且与特定任务紧密相关）不同，我们的智能体与任务无关，当任务改变时不需要重新配置。总之，我们的主要贡献是：

我们提出了一种新颖的“采用大语言模型专用化MCTS进行战术执行与推理的多智能体系统”（MASTER），这是一个新颖的多智能体框架，采用了基于MCTS算法的智能体招募流程和通信协议。该系统根据任务复杂度自主调整智能体数量，并减轻了智能体通信过程中的干扰和令牌窗口不足问题。
我们引入了一种针对LLM定制的修改版MCTS。这种改编适用于环境不提供客观反馈的任务，解决了原始MCTS的一个局限性。这个修订后的MCTS在我们的MASTER框架中实现。
我们在多种任务上进行了全面实验，包括问答（HotpotQA）、决策制定（WebShop）和编程（MBPP）。它在HotpotQA上达到76%的准确率，在WebShop上达到80%，在这些数据集上创造了新的最优性能。

2 相关工作#

许多研究已经致力于增强LLM的规划能力。在这些努力中，智能体出现了两种主要的规划方法：单路径规划和基于树的规划。在多智能体系统中，当前框架主要根据其智能体通信模式采用预定义框架或开放框架。我们在本节讨论一些相关工作。

2.1 规划过程#

2.1.1 单路径规划#

在单路径规划中，LLM一次只沿一条轨迹前进，不分支到多种可能性。早期例子包括少样本提示（Brown et al., 2020），其中LLM通过已完成任务的示例进行引导，以及思维链方法（Wei et al., 2022; Kojima et al., 2023; Ning et al., 2024），这些方法要求LLM逐步推理，在整个过程中保持线性轨迹。Zhang等人引入了一种结构化的元提示，其中包含供LLM完成的占位符（Zhang et al., 2024c），而Suzgun和Kalai提供任务相关信息来引导模型的路径（Suzgun and Kalai, 2024）。单路径规划也从外部反馈中获益，以改进解决方案。ReAct（Yao et al., 2023b）整合了来自环境的反馈，Reflexion（Shinn et al., 2023）则基于接收到的反馈补充了言语推理。Chen等人使用代码解释器的输出和错误信息来帮助LLM调试（Chen et al., 2024c），而Qiu等人利用符号解释器的输出来增强LLM的归纳推理能力（Qiu et al., 2024）。

图1：MASTER的推理树。从智能体开始，第一次扩展中创建了智能体A、B和C。然后系统首先选择智能体B进行扩展，因为其UCT更高。它的子智能体D是一个终端智能体，评估失败，触发了反向传播并降低了智能体B的UCT。现在智能体C具有最高的UCT，被选中进行下一次扩展。它的子智能体E是一个终端智能体，通过了评估。其中的答案就是最终答案。

2.1.2 基于树的规划#

在复杂问题求解中，探索多个思维轨迹并根据需要回溯通常是有益的。基于树的规划将这些思维组织成树结构，并在其上应用搜索算法。例如，在思维树（Yao et al., 2023a）中采用了BFS/DFS。RAP（Hao et al., 2023）和LATS（Zhou et al., 2024）利用MCTS来近似现实并支持LLM的推理过程。然而，由于引言部分提到的两个问题，模拟过程对其成功的贡献程度尚不确定。为了解决第一个挑战，RAP用“这个推理步骤正确吗？”提示LLM，并使用“是”的下一个词元概率作为奖励，从而在不依赖外部标准的情况下利用LLM的评估能力。对于第二个挑战，RAP通过只进行一次模拟来降低成本。从数学角度来看，一次模拟能否准确近似真实奖励是值得怀疑的。有些方法一旦找到正确答案就停止模拟。然而，如果不揭示真实答案，这种提前终止机制是不可用的。

2.2 多智能体系统#

2.2.1 预定义框架#

在预定义框架中，智能体的招募和通信是预先结构化的。例如，专门针对软件开发的ChatDev（Qian et al., 2023）和MetaGPT（Hong et al., 2023）依赖于预定义的工作流。类似地，AutoAgents（Chen et al., 2024a）是一个为自动智能体生成而设计的框架，也遵循预定义结构。这些框架因过度依赖前期规划以及应对变化需求的灵活性不足而受到批评（Pargaonkar, 2023）。

2.2.2 开放框架#

相反，开放框架提供了更大的灵活性，允许智能体更动态地交互。例如，AgentVerse（Chen et al., 2024b）……

3 方法论#

3.1 智能体设计#

在我们的框架中，每个智能体都是一个LLM实例，配备了一组指令，指导其行为。智能体接收一个提示，其中包含：任务描述、到当前状态为止的完整轨迹（包括先前智能体的思考、行动、观察和验证）、以及当前智能体需要执行的具体指令。智能体的输出被解析为三个部分：思考（Thought）、行动（Action）和观察（Observation）。思考是智能体对当前状态的推理；行动是智能体决定执行的操作（例如，搜索、点击、完成等）；观察是执行行动后从环境（或模拟环境）返回的反馈。此外，每个智能体还有一个评估（Assessment）步骤，由其父智能体（或根智能体自身）执行，用于评估该智能体解决方案的质量，并给出一个分数（score）和置信度（confidence）。此外，还有一个验证（Validation）步骤，在评估之前进行，用于检查智能体的思考、行动和观察之间的一致性，以及它们与原始问题的对齐程度。这些设计细节将在第3.4节中进一步阐述。

智能体可以是中间智能体或终端智能体。终端智能体是指其行动指示任务完成（例如，在HotpotQA中行动为Finish[answer]）的智能体。只有终端智能体才会被评估（Evaluation）：LLM判断其答案是否正确。如果正确，任务成功结束；如果错误，则触发反向传播。

3.2 推理树的构建#

我们的系统构建一棵推理树，其中每个节点代表一个智能体。树的根节点是初始智能体，它接收原始问题。从根节点开始，通过扩展（Expansion）创建子智能体：给定一个父智能体，系统多次调用LLM（使用相同的提示模板但不同的随机种子）来生成多个子智能体，每个子智能体都尝试从同一状态出发探索不同的推理路径。子智能体的数量是一个超参数，称为分支数（Number of Branches），根据任务而变化。这些子智能体的创建称为从父智能体的扩展。

可以从任何现有智能体继续使用相同过程进行进一步扩展。计算每个智能体的UCT，并选择UCT最高的智能体进行进一步扩展。另一个超参数，最大扩展深度（Maximum of Expansion），表示解决问题所需的大致步数，允许用户根据对任务的理解来设置。如果达到此限制仍未找到满意解，则提交具有最高奖励的终端智能体的解作为最终答案。

在推理树的扩展过程中，那些在其解决方案（Solution）中生成最终答案而非中间步骤的智能体，称为终端智能体（Terminal Agents）。例如，在HotpotQA任务中，如果智能体的行动是Finish[]，则被识别为终端智能体，因为该行动表示最终答案。其他任务的解决方案中也有类似指示。在评估（Evaluation）阶段（仅适用于终端智能体），LLM评估解决方案的正确性。如果解被认为是正确的，则作为最终答案提交，任务结束。如果不正确，则触发反向传播（Backpropagation），使用该终端智能体的奖励来更新路径上直到根智能体的所有智能体的奖励。伪代码见附录A。

3.3 修改后的UCT公式#

近期工作RAP和LATS直接应用了原始UCT公式。为了更好地适应我们的设计，我们提出了一种修改后的UCT公式。

原始UCT公式源自Hoeffding不等式（Lattimore T, 2020），可在附录B中找到。它通常应用于以下场景：给定一个表示状态（称为节点 $h$ ）的节点，有多个后续动作可供选择（例如 $a_i, a_j, a_k$ ）。为了确定这些动作的Q值，会进行多次模拟，并使用UCT来决定应该模拟哪个动作。UCT不是简单地选择具有最高Q值的节点（纯利用，公式1中的第一项），而是通过加入一个探索项（公式1中的第二项）来平衡利用与探索，该探索项倾向于选择模拟次数较少的节点。

节点 $i$ 表示由动作 $a_i$ 产生的状态，是节点 $h$ 的子节点之一。节点 $i$ 的UCT公式为：

UCT = Q_{i} + \sqrt{\frac{\ln(N_{i})}{2n_{i}}} \quad (1)

Q_{i} = \frac{\sum_{n = 1}^{n_{i}}r_{n}}{n_{i}} \quad (2)

其中 $n_i$ 是应用于该节点的反向传播次数。 $r_n$ 是第 $n$ 次反向传播的奖励。 $Q_i$ 是通过公式2计算的Q值估计。它代表来自模拟的平均奖励。 $N_i$ 是当前节点 $i$ 的父节点（即节点 $h$ ）的总模拟次数。换句话说， $N_i$ 是 $n_i$ 、 $n_j$ 和 $n_k$ 的总和（尽管 $n_j$ 和 $n_k$ 未在UCT公式中明确显示）。

在我们的系统中， $Q_i$ 作为Q值的估计，由两个部分组成：初始奖励（Initial Reward）是从该智能体生成时的评估（Assessment）中提取的。更新奖励（Updating Reward）是来自反向传播的奖励的平均值，类似于公式2中的 $Q_i$ 。受关于以控制变量形式提供奖励辅助信息的研究启发（Verma and Hanawal, 2021），我们修改了系统中的奖励估计，如公式3所示：

Q_{i} = c_{0}\cdot r_{0} + (1 - c_{0})\cdot \frac{\sum_{n = 1}^{n_{i}}r_{n}}{n_{i}} \quad (3)

其中 $r_0$ 是LLM给出的初始奖励。 $c_0$ 是LLM对该初始奖励的置信度。 $r_n$ 和 $n_i$ 与公式2相同。

原始MCTS严重依赖大量模拟来使该估计准确。因此，当 $n_i$ 较小时，它变得不可靠。另一方面，我们的Q值有一个额外分量（初始奖励），因为我们的Q值是初始奖励和更新奖励的加权和，权重为置信度。当LLM对其分配的初始奖励有高置信度时，来自反向传播的奖励（更新奖励）的影响因其较低的权重 $(1 - c_0)$ 而减小。相反，当LLM置信度较低时，更新奖励需要主导Q值估计，同时更新奖励的权重 $(1 - c_0)$ 更高。值得注意的是，反向传播次数 $n_i$ 会根据每个问题自动调整，而不是由用户手动设置。对于复杂任务，模型需要更多尝试来获得可接受的答案，每次失败尝试都会触发一次反向传播。对于简单问题，模型可能在第一次尝试中就产生可接受的结果，从而无需反向传播。这种提前终止机制在完成任务的同时减少了令牌消耗。

在RAP和LATS使用的公式中，一个探索常数 $\lambda$ 取代了固定的 $1/\sqrt{2}$ 作为探索项的权重，如下所示：

UCT = Q_{i} + \lambda \cdot \sqrt{\frac{\ln(N_{i})}{n_{i}}} \quad (4)

在我们的方法中，我们使用 $1/(10\sqrt{2} c_{0})$ 作为探索权重。这一调整的意义有两方面：1）探索项反映了与该智能体相关的不确定性。当LLM对初始奖励的置信度较低时，智能体的不确定性相对较高，需要更多探索。在这种情况下，较高的探索权重会增加UCT，引导算法选择该智能体进行进一步探索；2）我们系统中的反向传播次数显著低于原始MCTS，而对数函数在变量较小时斜率较陡，因此探索项的值往往起主导作用。因此，应使用此探索权重来控制该项的影响。此外，当使用最小置信度0.1时，探索权重等于 $1/\sqrt{2}$ ，与公式1中的权重相同。

总之，我们系统中的修订公式为：

UCT = \left\{ \begin{array}{ll}r_0 & \mathrm{if}\ n_i = 0 \\ c_0\cdot r_0 + (1 - c_0)\cdot \frac{\sum_{n = 1}^{n_i}r_n}{n_i} +\frac{1}{10\sqrt{2}c_0}\cdot \sqrt{\frac{\ln N_i}{n_i}} & \mathrm{otherwise} \end{array} \right. \quad (5)

当 $n_i$ 为0时，表示没有反向传播应用于该节点，该节点的UCT设为其初始奖励 $r_0$ 。

3.4 奖励分配策略#

总结来说，我们在框架中为确保奖励可靠性而实施的三种特殊机制是：

在评估（Assessment）阶段分配奖励之前，会先执行一个额外的验证（Validation）步骤，LLM对当前解决方案中事实的正确性进行评注。这些评注被添加到评估步骤的提示中，引导LLM给出更可靠的奖励。这种设计基于观察：当LLM被要求一次处理一个问题时，它表现更好。分开验证正确性和进展可以产生稳定可靠的评分。
在评估阶段，LLM被要求同时提供分数及其置信度，而不仅仅是分数。置信度值在我们修改后的UCT公式中扮演两个角色，详见修改后UCT公式小节。如果LLM对其提供的分数置信度较低，则该分数的影响力降低，并且选择该智能体进行进一步探索的可能性增加。
反向传播在原始MCTS中每次模拟后发生。尽管我们移除了模拟，但在我们的框架中保留了反向传播。每当一个终端智能体生成的解决方案未能通过评估时，就会触发反向传播。失败的评估表明导致该终端智能体的推理步骤可能有缺陷，其Q值应相应降低。这种机制允许在初始奖励不准确时进行调整。

4 实验设置#

为了证明我们框架的通用性，我们在多种任务上进行了实验，包括问答（HotpotQA）、决策制定（WebShop）和编程（MBPP）。这些数据集是其各自领域广泛认可的基准。

除了评估有效性和效率外，我们还进行了消融研究和参数研究，以探究我们框架中每个机制的贡献以及超参数的影响。

4.1 数据集#

HotpotQA：（Yang et al., 2018）测试LLM中的多跳推理，要求模型解析和推理多个段落。我们使用了Distractor设置，任务是在混合了相关和不相关段落的上下文中回答问题。

WebShop：（Yao et al., 2022）模拟电子商务环境以测试决策能力。任务涉及在虚拟商店中导航，找到最符合给定指令的产品，成功与否通过所选产品与要求的匹配程度来衡量。

MBPP：（Austin et al., 2021）评估编码能力。每个任务包括问题描述和用于验证的测试用例。在我们的系统中，智能体生成并测试完整代码，子智能体根据父智能体识别出的错误迭代改进。当生成的代码通过所有测试用例时，任务被视为解决。

4.2 基线模型#

由于我们使用GPT-4（一个高性能LLM）作为基础模型，我们将没有任何智能体的GPT-4本身作为一个基线。它通过单次调用（少样本思维链）接收任务描述和与我们框架相同的示例来解决问题。值得注意的是，在这种设置下，GPT-4无法解决HotpotQA和WebShop问题，因为这些任务需要与环境进行多次交互。对于HotpotQA，模型必须生成搜索关键词，从环境接收检索到的上下文，并决定是搜索更多上下文还是回答问题。对于WebShop，模型必须通过多次搜索和点击操作在模拟网站上购买目标商品。期望GPT-4在没有环境反馈的单次调用中执行这些操作是不现实的。当引入外部环境反馈以实现多轮交互时，该设置变得与ReAct的实验条件相同。换句话说，表1中ReAct的性能可作为基础模型在这两项任务中能力的指标。

ReAct和Reflexion是规划领域中众所周知的方法，我们的工作整合了它们的一些思想。LATS与我们方法一样是基于树的方法，并展示了强大的性能。因此，我们在所有三个数据集上将这些方法作为基线进行比较。MetaGPT和AgentVerse是两个代表性的多智能体系统，作为我们多智能体设置中的基准。我们仅在MBPP上评估它们，因为MetaGPT是专门为编程任务设计的，而AgentVerse需要执行工具，只有编程任务的工具可用。

此外，我们将我们的框架与每个数据集的当前最优（SOTA）方法进行基准测试：HotpotQA上的Beam Retrieval、WebShop上的AgentKit、MBPP上的AgentCoder。然而，AgentKit在其原始论文中是在两个数据集（Crafter和WebShop）上评估的，但其GitHub仓库仅提供了Crafter的代码。此外，Crafter的可用代码由于实现细节不足而无法适配到WebShop。因此，我们依赖于其论文中声称的原始性能。尽管如此，鉴于我们的结果与他们的结果之间存在显著的性能差距，我们相信我们的SOTA声明仍然是高度合理的。

4.3 实现细节#

鉴于GPT-4的高成本，我们从每个数据集中随机选择100个问题的样本，遵循Reflexion（Shinn et al., 2023）和LATS（Zhou et al., 2024）中使用的方法。为确保公平性，在所有三个数据集上使用相同的随机种子来选择这100个问题。

为了减轻LLM随机性对准确率的影响，我们在相同的样本上将每个实验重复三次，并在表1中报告平均准确率。我们的框架通过方法论部分概述的策略有效控制了LLM的随机性，其中多个步骤相互支持和验证。

5 结果与分析#

5.1 有效性分析#

我们复现了所有基线方法（AgentKit因信息不足除外），使用GPT-4作为基础模型，在相同的100个问题上进行测试并记录结果。此外，我们将这些结果与各自论文中报告的结果进行比较。较好的结果被用作表1中每个基线的最终值。这种方法有利于基线方法，并确保我们的框架在各种标准下都展现出优越的性能。

MASTER在多个任务上创造了新的SOTA性能：1）在HotpotQA上达到76.0%的精确匹配准确率，超过了Beam Retrieval的73.3%（Zhang et al., 2024b）；2）在WebShop上达到80.0%的准确率，超过了AgentKit的70.2%（Wu et al., 2024）。在MBPP上，它以91.0%的准确率接近AgentCoder的91.8% pass@1准确率（Huang et al., 2024），在编程任务中显示出有竞争力的性能。

表1：有效性比较（准确率）

方法	HotpotQA	WebShop	MBPP
GPT-4 (CoT)	-	-	0.683
ReAct	0.420	0.320	0.710
Reflexion	0.510	0.350	0.771
LATS	0.710	0.380	0.811
MetaGPT	-	-	0.877
AgentVerse	-	-	0.890
Beam Retrieval	0.733	-	-
AgentKit	-	0.702	-
AgentCoder	-	-	0.918
Ours	0.760	0.800	0.910

5.2 效率分析#

作为一种基于树的方法，令牌消耗因多样化的推理轨迹而成为一个问题。然而，通过移除模拟步骤并引入提前终止机制，与其他使用MCTS的基于树的方法相比，我们的框架实现了更高的效率。我们针对LATS进行效率基准测试，原因如下：1）LATS是一种典型的基于树的方法，与类似框架相比具有优越的性能；2）LATS在其论文中报告了与ToT（Yao et al., 2023a）和RAP（Hao et al., 2023）相比最低的令牌消耗。

我们在相同的100个HotpotQA问题上测量了LATS（ $n=5, k=50$ ）和MASTER（分支数=2，最大扩展深度=3）的令牌消耗，使用与有效性分析实验中相同的超参数设置。LATS每问题平均成本为185,392个令牌，而MASTER为10,937个令牌。我们的方法仅使用LATS约6%的令牌，同时实现了更好的性能（表1）。

LATS（Zhou et al., 2024）报告的平均成本为每问题173,290个令牌，低于我们复现的结果。这种差异可能是由于他们的测试是在正确回答的问题上进行的，而我们的测试包含了一些错误回答的问题，这些问题往往会消耗更多令牌，因为算法会继续运行直到达到最大尝试限制。

5.3 消融研究#

5.3.1 UCT修改#

在MCTS中，UCT公式平衡探索与利用。我们的主要贡献之一是将此公式改编以更好地适应LLM。我们评估了移除修改后UCT公式的各个组成部分的影响，考虑以下情况（表2）：

我们完整的修改公式，包含初始奖励和更新奖励的加权和，以及受LLM置信度影响的探索权重（公式5）。
一个变体，使用奖励的加权和以及固定的探索权重（公式6）。这与完整公式的区别在于没有在探索项中纳入LLM的置信度。

UCT = c_0\cdot r_0 + (1 - c_0)\cdot \frac{\sum_{n = 1}^{n_i}r_n}{n_i} + \sqrt{\frac{\ln{(N_i)}}{n_i}} \quad (6)

一个仅使用奖励加权和的变体（公式7），移除了整个探索项。

UCT = c_0\cdot r_0 + (1 - c_0)\cdot \frac{\sum_{n = 1}^{n_i}r_n}{n_i} \quad (7)

一个仅使用初始奖励进行利用的变体（公式8），排除了探索项和来自反向传播的更新奖励。

UCT = r_0 \quad (8)

当使用固定探索权重的UCT（情况2）时，在三个数据集中的两个上性能下降，甚至比完全移除探索项的变体还要差。正如方法论部分所讨论的，探索项起着主导作用，应该由探索权重来调节。这一结果支持了该假设，因为当使用此公式时，系统有时会过度探索而无法向任务完成进展。省略基于置信度的动态探索权重对系统有害。

使用初始奖励和更新奖励的加权和（情况3）比单独使用初始奖励（情况4）表现更好，这可能是因为更新奖励整合了来自推理树更深层的额外信息。

MBPP的结果表明，不同的UCT变体对该数据集没有显著影响。这一结果可能是因为观察（Observation）——即测试用例的结果——是客观的。观察被附加到评估的提示中，使得LLM能够以高置信度分配奖励。当 $c_0$ 为1时，所有UCT变体都退化到情况4或非常接近它。因此，所有设置产生相同或几乎相同的结果。

表2：移除修改后UCT公式不同组成部分的消融研究

UCT变体	HotpotQA	WebShop	MBPP
完整修改UCT	0.760	0.800	0.910
固定探索权重	0.700	0.677	0.910
无探索项	0.737	0.750	0.910
仅初始奖励	0.723	0.703	0.910

5.3.2 智能体设计#

评估前的验证步骤是我们框架的另一个关键特征。我们进行了额外的消融研究，单独移除验证和评估步骤。由于初始奖励来自评估，并且算法无法在没有它的情况下运行，当评估步骤被移除时，我们分配随机初始奖励（表3）。

当移除验证或评估步骤时，性能显著下降，即使在MBPP数据集上也是如此，因为验证极大地影响了奖励分配——MCTS的核心组成部分。此外，当评估步骤被移除且分配随机奖励时，性能基本上仅依赖于LLM本身，甚至更差。

表3：移除验证或评估的消融研究

设置	HotpotQA	WebShop	MBPP
完整设置	0.760	0.800	0.910
无验证	0.623	0.563	0.863
无评估	0.233	0.157	0.743

5.4 参数研究#

我们对两个关键超参数进行了参数研究：分支数（表4）和最大扩展深度（表5），涵盖所有三个数据集。

分支数对WebShop和MBPP的性能影响很小。然而，在HotpotQA上，当从2减少到1时，性能下降了近3%。这种减少可能会阻碍系统，因为多个推理轨迹有助于防止陷入错误状态。尽管WebShop面临类似的挑战，但智能体可以使用数据集中内置的‘prev’行动来缓解（但不能完全避免）这个问题。为了平衡性能和成本，我们在所有数据集上使用2。

表4：分支数的参数研究

分支数	HotpotQA	WebShop	MBPP
1	0.733	0.797	0.903
2（所有数据集使用）	0.760	0.800	0.910
3	0.763	0.797	0.910

我们在此处选择了1、3、8作为最大扩展深度，因为在我们的其他实验中，HotpotQA和MBPP使用3，而WebShop使用8。通常，HotpotQA和WebShop中的问题需要多步解决，因此当最大扩展深度低于解决问题所需步数时，它们的性能急剧下降，因为它们被迫在获得答案之前停止。

表5：最大扩展深度的参数研究

最大扩展深度	HotpotQA	WebShop	MBPP
1	0.000	0.000	0.747
3（HotpotQA和MBPP）	0.760	0.013	0.910
8（WebShop）	0.770	0.800	0.910

6 结论#

本文介绍了MASTER，一个新颖的多智能体系统框架，它利用专用化的MCTS来增强LLM的规划能力。我们针对LLM优化的MCTS将MCTS的适用性扩展到更广泛的任务范围，并降低了成本。此外，我们采用该算法来指导智能体的招募和通信协议，从而引入了一种创新形式的多智能体系统。在多个数据集上的广泛实验证明了MASTER相对于现有框架的有效性和效率。

7 局限性#

我们的框架存在一些局限性。首先，它严重依赖LLM提供当前推理状态的准确分数和置信度评估的能力。虽然GPT-4能有效执行此任务，但较小的开源模型可能在此步骤遇到挑战。此外，用户必须为系统配置某些超参数，包括最大扩展深度和分支数。这些参数的最优值可能因具体任务而异。