3.1 Coding Task-Specific Agents#

我们首先介绍三个单元 LLM 智能体，分别针对代码生成过程的不同部分：策略思考、代码实现和代码调试。

使用思考者（Thinker）智能体生成策略
传统方法如（Chen et al., 2021; Austin et al., 2021; Hendrycks et al., 2021）根据问题描述直接生成输出代码候选。然而，这些方法并未充分利用 LLM 在生成更具表达力的文本输出方面的优势。Wei et al. (2022) 表明，允许 LLM 生成自然语言的分步思考可以在下游 NLP 任务中带来显著的性能提升。遵循 Yao et al. (2024) 的设置，请求 LLM 生成一系列不同的自然语言思想可以增强解决方案的多样性。我们建议采用这种技术，允许一个 LLM $θ_T​$（称为“思考者”智能体）根据输入编码问题顺序生成一组高层次策略。每个策略 $\widehat{S}_i​$ 是根据先前生成的策略自回归生成的，遵循：

$\widehat{S}_i​∼p_{θ_T}(.∣\widehat{S}_{1​:i−1},D)$

通过允许模型首先生成编码策略，我们使 LLM 能够利用从文本领域学到的推理能力来处理编码问题。生成的策略在自然语言中的表达能力可以潜在地引导代码生成过程走向更多样化的探索路径。值得注意的是，我们让思考者智能体动态决定生成的编码策略的数量，考虑到不同的编码问题可能有不同数量的可行策略。

使用求解者（Solver）智能体生成解决方案
给定一个完整的生成策略 $\widehat{S}_i​$，我们让一个 LLM $θ_S$​（称为“求解者”智能体）生成一组初始代码解决方案。由于 LLM 通常经过微调以遵循自然语言中的任意指令，这些模型可以在测试时理解新颖的未见任务（Ouyang et al., 2022; Touvron et al., 2023b; Wang et al., 2023）。因此，通过将策略作为输入指令的一部分，我们可以条件化求解者智能体以产生特定于策略的代码候选。对于每个候选，生成目标定义为：

$\widehat{W}_i​∼p_{θ_S}(\widehat{S}_i​,D)$

使用思考者和调试者（Debugger）智能体改进解决方案
先前的方法如（Chen et al., 2023a,d; Shinn et al., 2023; Madaan et al., 2023）发现，生成代码中的语法错误甚至逻辑缺陷可以通过允许 LLM 迭代地改进和重新生成代码来修复。这种自我改进能力通常通过某种形式的关于代码质量的反馈（例如执行结果、编译器信号）来加强：

$F_{exe,i}=\widehat{W}_i​(\{(i_j,o_j)_v\})$ $F_{cri,i}=θ_C(\widehat{W}_i​,\widehat{S}_i​,F_{exe,i},D)$

其中 $θ_C$​ 是评判者（Critic）智能体。将集体反馈表示为 $F_i=\{F_{exe,i},F_{cri,i}\}$，思考者智能体会生成一组关于代码候选的反思 $R_i​$。

$\widehat{R}_{i,j}∼p_{θ_T}(.∣\widehat{R}_{1:j-1},F_i,\widehat{W}_i,\widehat{S}_i,D)$ $\widehat{W}_{i,j}∼p_{θ_D}(.∣\widehat{R}_{i,j},Fi,\widehat{W}_i,\widehat{S}_i,D)$

$\widehat{R}_{i,j}$​ 表示“思考者”为 $\widehat{W}_i$​ 生成的第 $j$ 个反思。一个 LLM $θ_D$​（“调试者”智能体）将参考此反思修改 $\widehat{W}_i$​，相应地生成一个新程序。

3.2 Tree Expanding with Critic Agent#

CodeTree 为每个问题构建一个异构树，其中树根代表问题规范 $(D,\{(i_j,o_j)\})$，每个后续树节点代表一个生成的代码解决方案 $\widehat{W}_i$​。每个节点都有相关属性，包括其集体代码反馈 $F_i$​ 及其对应的策略和反思：$S_i$​ 和 $R_i$​。通常，添加树节点是一个两步过程：1）根据相应的策略生成代码解决方案（公式 2 或公式 6），2）评估生成的解决方案 $\widehat{W}_i$​ 并获得环境反馈（公式 4）。

与之前的树结构搜索方法（Yao et al., 2024; Islam et al., 2024）不同，我们不在开始时构建整个树。相反，我们引入了一个评判者智能体，根据潜在策略动态扩展树。它将指导树的扩展和生成，根据其对当前节点的评估采取行动。

节点评分与评估
对于给定的解决方案和相应的 $F_{exe​}$，评判者智能体执行评估，通过公式 4 衡量其潜力，从而得到 $F_{cri}​$。我们分别评估：1) 可见测试用例上的执行输出与预期输出的匹配程度；以及 2) 解决方案在解决问题方面是否稳健地实现了其对应策略。对于一个程序 $\widehat{W}_i$​ 及其相应的反馈 $F_i$​，评判者智能体将评估当前解决方案是否值得改进，或者不应再探索，在改进和中止之间做出决定。评判分数按照以下公式计算：

$Score(\widehat{W}_i)=Score(F_{exe,i})+Score(F_{cri,i})$

解决方案验证
对于一个通过了所有可见测试用例的 $\widehat{W}_i$，它可能过拟合可见测试用例，并可能在隐藏测试用例上失败。因此，评判者智能体 $θ_C$​ 将验证此解决方案是否稳健且可推广到未见过的测试用例。

评判者智能体的决策制定
从初始的 $S_i,W_i,F_i$​ 开始，评判者智能体引导搜索正确的解决方案。在每个节点，它有一个包含三个动作的动作空间：

• 改进（Refine）：通过为当前节点生成多个反思，继续从当前节点进行探索；
• 中止（Abort）：由于评估分数低而剪枝此节点，并将探索回溯到其兄弟节点；
• 接受（Accept）：接受当前节点作为最终解决方案并提前终止搜索。

3.3 Multi-agent Collaboration#

在树的扩展过程中，任务特定智能体与评判者智能体协作，利用其反馈，并遵循其指导进行探索。树扩展和搜索的灵活性由 LLM 智能体的决策决定，例如确定策略数量并决定搜索路径。在推理期间，实际上，我们限制探索步骤的数量以避免大量的计算开销。当找到终止信号（即接受代码解决方案）或达到最大探索步骤数时，将根据其评估分数 Score $(\widehat{W}_i)$ 选择一个代码候选。我们 LLM 智能体的所有示例指令提示请参见附录 A。

4.1 Experimental Setup#

我们采用 pass@1（Chen et al., 2021）作为评估指标：每个编码任务只能选择一个代码候选提交用于隐藏测试用例的最终评估。我们将生成预算设置为每个编码任务 20 个样本。为了公平地将我们的方法与其他基线进行比较，我们在所有方法中采用了相同的生成预算。对于不使用评判者智能体的消融实验，我们遵循（Shinn et al., 2023; Chen et al., 2023d）的类似策略：我们选择一个通过所有可见测试用例的解决方案作为最终解决方案，用于隐藏测试用例的评估。

Benchmarks

我们在两类代码生成任务上进行了实验：

1. 函数实现（Function implementation）：编码任务是按照特定的函数签名完成单个函数：HumanEval（Chen et al., 2021）、MBPP（Austin et al., 2021）以及来自（Liu et al., 2023）的 EvalPlus 变体，记为 HumanEval+ 和 MBPP+；

2. 程序实现（Program implementation）：编码任务是解决一个算法问题：CodeContests（Li et al., 2022）和 APPS（Hendrycks et al., 2021）。
   HumanEval(+)、MBPP(+) 和 CodeContests 的测试集大小分别为 164、378 和 165。对于 APPS，我们从测试集中随机抽取了 150 个样本（每个难度级别 50 个）。

Baselines

我们引入以下基线：

• 直接（Direct）：指示模型直接从输入问题生成代码；
• CoT（Wei et al., 2022）：指示模型在给出解决方案程序之前提供思维链推理；
• Reflexion（Shinn et al., 2023）：利用解决方案的执行反馈生成自我反思。这些反思用于迭代改进解决方案；
• MapCoder（Islam et al., 2024）：提出了一个智能体协作系统来规划、解决、测试和改进解决方案。我们设置 #plans=4, #debug-round=5，生成预算=20；
• 重采样（Resample）：遵循与 Li et al. (2022) 类似的原则：重复采样解决方案并使用可见测试用例进行过滤。

Models

我们在三个具有不同模型大小和能力的模型上研究我们的方法。我们使用来自 GPT 和 Llama 3.1 家族的大型语言模型进行实验。具体来说，我们使用了 GPT-4o-mini、GPT-4o² 和 Llama-3.1-8B³。

4.2 Main Result#

我们在表 2 中将 CodeTree 与其他基线进行了比较。我们注意到，在相同的解决方案生成预算下，Reflexion 和重采样在 HumanEval 和 MBPP 数据集上是强大的基线，与 CodeTree-BFS/DFS 相当。带有评判者智能体的 CodeTree 在 GPT-4o-mini 和 GPT-4o 的 5 个基准测试中的 4 个上优于所有其他基线。例如，CodeTree 在 Codecontests 基准（即竞赛级编码任务）上达到了 pass@1 = 43.0%（比重采样基线性能提升了 22.4%），显示了其在解决难题方面的优势。

我们发现 CodeTree-BFS 的性能几乎总是优于 CodeTree-DFS，这表明探索多样化的策略比从一个解决方案进行迭代改进更有效。有趣的是，在 Llama-3.1-8B 模型上，重采样在 4 个基准上取得了最佳结果。这一观察表明，小型语言模型可能不适合像 CodeTree 这样的多智能体框架，因为该框架要求模型遵循特定任务的角色和指令，并以合理的准确性执行不同的任务。

表 2：在 HumanEval、MBPP、EvalPlus 和 CodeContests 上 pass@1 的实验结果：

• 方法是仅生成一次程序解决方案的基线方法，

• 是像我们的方法一样具有 20 个样本解决方案生成预算的方法，

• 是带有或不带评判者智能体引导树搜索的 CodeTree 变体。

• 注意，MapCoder 不适用于 Llama-3.1-8B，如 Islam et al. (2024) 所述。

4.3 Analysis of Search Strategies#

鉴于 CodeTree-BFS 和 DFS 之间的性能差距，我们进行了额外的实验来分析没有评判者智能体的这些树搜索策略。我们在表 3 中报告了使用 GPT-4o-mini 在 HumanEval/HumanEval+ 上以及使用 GPT-4o 在 Codecontests 上的结果。与 $d=3$ 和 $w=3$ 的 DFS/BFS 策略相比，我们观察到，强制模型在 BFS 中搜索更广（即使用 $w>3$ 的更多样化策略）并且仅调试到 1 次迭代（即 $d=2$）提高了 pass@1 的性能。然而，对于 DFS，优先考虑更深的搜索（即 $d>3$ 的更多次迭代改进）并不会显著提升性能。最后，我们注意到 $w=4$ 在 HumanEval 上效果更好，而 $w=5$ 在 CodeContests 上效果更好，这表明更复杂的问题可以从探索更多数量的编码策略中受益。这一发现支持了我们提出的 CodeTree，其中评判者智能体可以根据上下文动态确定要探索的子节点数量。

表 3：CodeTree-BFS/DFS 在 HumanEval、HumanEval+ 和 CodeContests 上的 pass@1 结果：
dd 表示最大搜索深度，bb 表示最大搜索宽度。
(表格内容省略)

4.4 Analysis by Problem Difficulty#

我们进一步针对不同难度级别的编码问题评估了 CodeTree。我们从 APPS 基准的测试拆分中每个难度级别（“入门（introductory）”、“面试（interview）”和“竞赛（competition）”）随机抽取了 50 个问题，总共创建了 150 个问题的测试集。结果如图 3 所示。

结果表明，CodeTree 对于更简单的问题表现更好（GPT4o-mini 的入门级问题；GPT-4o 的入门级和面试级问题），但在解决非常困难的问题（例如竞赛级）方面仍然存在困难。我们假设，虽然 CodeTree 提高了搜索正确解决方案的效率，但对于高度复杂的问题，生成预算 = 20 仍然有限。

图 3：在 APPS 测试子集上的 pass@1 结果。我们分别从入门、面试和竞赛中随机选择 50 个样本。我们对 GPT-4o、GPT-4o-mini、Llama-3.1-8B 应用了重采样和我们的方法。

4.5 Ablation Study#

表 2 中的结果表明，与 BFS/DFS 等朴素搜索方法相比，评判者智能体在 CodeTree 中起着至关重要的作用。我们进一步分析了第 3.2 节中哪项任务对评判者智能体最为关键。具体来说，我们进行了以下消融实验：
(1) 无解决方案验证（w/o Solution Verification）：排除了对任何通过可见测试的解决方案的验证任务；
(2) 无节点中止评估（w/o Node Abort Evaluation）：让智能体持续探索，直到达到最大深度或找到可接受的解决方案；
(3) 无节点评分（w/o Node Scoring）：环境反馈仅基于执行输出，没有评判者智能体的评估。

表 4 中的结果表明，所有提出的任务对评判者智能体引导树扩展和解决方案搜索都至关重要。在这些任务中，节点中止和解决方案验证任务最为有效，对最终性能有显著影响。我们在附录 A 中包含了一个真实案例的定性研究。

表 4：针对评判者智能体不同任务的消融研究。我们使用 GPT-4o-mini 评估相应设置，并报告了 HumanEval 和 HumanEval+ 基准上的 pass@1。
(表格内容省略)

4.6 Search Efficiency#

虽然 CodeTree 在 20 个样本的生成预算下表现非常强劲，但了解我们的树搜索策略相比其他相关方法如何更高效是很重要的。具体来说，我们在将解决方案生成预算限制在 1 到 20 个样本之间时进行了实验。在图 4 中，我们绘制了 pass@1 相对于采样解决方案数量的曲线：(a) 显示了使用 GPT-4o 在 CodeContests 上的结果；(b) 显示了使用 GPT-4o-mini 在 HumanEval+ 上的结果。在两个图中，我们提出的 CodeTree 不仅比其他方法表现更好，而且即使在生成预算较小时（例如 < 9 个样本）也达到了相对较高的 pass@1。在 CodeContests 上，即使 CodeTree 在生成预算有限（即 < 5 个样本）时以较低的性能开始，其性能在后续的树探索中很快显著提高。这一观察表明，给定更大的解决方案生成预算，CodeTree 有潜力继续解决更多问题。

图 4：在预算 = 20 内生成新解决方案时的累积 pass@1 曲线

4.7 Results on SWEBench#

最近，Jimenez et al. (2024) 引入了一种新颖的编码任务，即根据输入的 GitHub 仓库和相应的拉取请求生成代码补丁。我们尝试通过两个主要修改将 CodeTree 应用于此基准：首先，我们将问题规范替换为输入拉取请求的文本描述；其次，我们将策略生成阶段调整为检索阶段，指示思考者智能体从输入的 GitHub 仓库中探索相关的代码上下文（通过代码文件、方法或代码行）。我们扩展了 Xia et al. (2024) 的检索和代码补丁生成阶段的实现，并将我们的 CodeTree 框架集成到不同轨迹（从上下文检索到代码补丁生成和排序）的探索中。从表 5 中，我们观察到，与 CoT（Wei et al., 2022）和 Reflexion（Shinn et al., 2023）等相关方法相比，CodeTree 可以带来显著的性能提升。结果还证明了我们的方法在复杂编码任务（如仓库级代码生成）上的多功能性，这类任务通常需要极大的搜索空间才能找到最优解。

表 5：SWEBench 基准上的结果：所有方法均使用 GPT4o-mini 作为基础模型。与 CoT 和 Reflexion 相比，CodeTree 可以带来更显著的性能提升。
(表格内容省略)

A.1 定性结果#

这里我们展示一个使用 GPT-4o-mini 解决 HumanEval-36 问题的真实例子。我们在图 5、6 和 7 中保留了实际的提示和模型的响应。我们发现，初始解决方案 $W_1$​ 生成了，它通过了所有可见测试用例，但被评判者智能体拒绝，评判者智能体还提出了改进建议。调试者遵循评判者智能体的建议并实现了 $W_2$​。我们在隐藏测试用例上评估了 $W_1$​ 和 $W_2$，结果 $W_2$​ 通过而 $W_1$​​ 失败。这表明评判者智能体对假阳性解决方案（即通过可见测试但未通过隐藏测试用例）做出了正确判断，并有效地引导找到了正确的解决方案。

在图 5 中，思考者智能体决定生成 5 种可能是解决方案的策略。为了开始树搜索，第一个策略 $S_1$​ 被发送给求解者智能体进行实现。生成一个解决方案后，它被发送给求解者进行实现。$W_1$​ 立即在可见测试用例上执行并观察输出。

在图 6 中，对于通过了所有可见测试用例的 $W_1$​，它将由评判者智能体进一步验证，看 $W_1$​ 是否适用于更通用的测试用例。评判者智能体给出了负面评价，并建议通过考虑更多情况（如零和负整数）来改进此解决方案。我们使用 oracle 隐藏测试用例评估 $W_1​$，它确实是不正确的，这支持了评判者智能体的决定。

在图 7 中，调试者智能体将来自评判者智能体的判断和推理视为额外的环境反馈，然后根据以下条件实现新的解决方案：1. 问题本身，2. 要改进的解决方案，3. 环境反馈。调试者智能体将 $W_1$​ 改进为 $W_2$​，并被评判者智能体接受。我们在隐藏测试用例上评估 $W_2$​，它是正确的。