APRMCTS: Improving LLM-based Automated Program Repair with Iterative Tree Search

博客贡献人

JokerLin

作者

Haichuan Hu, Congqing He, Hao Zhang, Xiaochen Xie, Quanjun Zhang

标签

MCTS, Automated Program Repair, Tree Search

摘要

自动程序修复（APR）尝试在无需人工干预的情况下修复软件漏洞，这在软件开发和维护中起着关键作用。近年来，随着大型语言模型（LLM）的发展，APR技术的数量迅速增加，且性能显著显著。然而，现有基于LLM的APR技术通常采用试错策略，但存在两个主要缺点：（1）由于本地探索导致补丁效果有限，（2）由于冗余探索导致搜索效率较低。本文提出了APRMCTS，利用迭代树搜索改进基于LLM的APR。APRMCTS通过对已探索的补丁进行全局评估，并选择最有前景的补丁进行后续细化和生成，将蒙特卡洛树搜索（MCTS）纳入补丁搜索。APRMCTS有效解决了陷入局部最优的问题，从而帮助提升补丁搜索的效率。本文对 Defects4J 的835个漏洞进行的实验表明，当与 GPT3.5 集成时，APRMCTS 可修复共201个漏洞，性能超过所有最先进的基线。此外，APRMCTS还帮助GPT-4o-mini、GPT-3.5、Yi-Coder-9B和Qwen2.5-Coder-7B分别修复了30、27、37和28个新的错误。更重要的是，APRMCTS在使用小补丁规模（16和32）时具有显著的性能优势，明显低于之前研究采用的500和10,000补丁。本文还在SWE-bench Lite上进行了初步实验，结果显示APRMCTS能够修复300个缺陷中的164个，展示了其在多种现实缺陷数据集（如SWE-bench）中的潜力。在成本方面，与现有基于LLM的年利率方法相比，APRMCTS所需时间更短，且节省了超过50%的经济成本。本文的广泛研究表明，APRMCTS表现出良好的效果和效率，特别是在处理复杂漏洞方面具有优势。

简介

自动程序修复（APR）尝试通过自动生成补丁来修复有缺陷的程序。典型的APR流程包括两个主要步骤：（1）生成通过所有测试用例的合理补丁，（2）通过人工检查验证这些补丁的正确性。传统的APR技术大致可分为三类：基于模板、基于启发式、和基于约束。其中，基于模板的APR利用设计良好的模板匹配漏洞代码模式，被广泛认为是最先进的。尽管基于模板APR的有效性本质上受限于其对预定义模板的依赖，这限制了其处理此前未见软件漏洞的能力。

近年来，研究人员引入了大量基于学习的方法，利用深度学习从现有代码库中提取修复错误模式来增强修复能力。与传统APR相比，基于学习的APR展现出更优的泛化能力，能够解决训练数据中不存在的错误。近年来，随着大型语言模型（LLM）在软件工程任务中的快速发展（例如单元测试），大量基于LLM的APR技术出现了。Hossain等人全面讨论了各种提示和情境对基于LLM的APR效果的影响。ChatRepair 使用 GPT-3.5 修复了 Defects4J 共 162 个漏洞，是最具代表性的基于大型语言模型的方法之一。其他研究、进一步证明了大型语言模型在不同修复场景中的有效性，如编程问题。

然而，现有最先进的基于LLM的APR技术通常采用串行单路径试错策略，先生成候选补丁，针对测试用例进行验证，然后根据测试结果进行细化。虽然这种策略很直接，但可能存在两个关键局限：效能上的局部最优和效率上的冗余探索。首先，它缺乏利用历史搜索信息的能力，使修复过程容易陷入局部最优解。其次，它以非结构化且无记忆的方式生成补丁，常导致补丁冗余或几乎重复，并降低计算资源的效率。这些限制阻碍了模型探索搜索空间中有潜力区域的能力，并根据先前尝试调整修复策略。因此，现有方法常常难以高效发现高质量补丁，尤其是针对复杂的漏洞。

为解决这些问题，本文提出了APRMCTS，通过结合多轮迭代树搜索方法、CoT和自评估来生成补丁，帮助提升基于LLM的APR。与试错修复模式不同，APRMCTS 采用评估和改进的方法来指导模型朝着正确的修复路径前进。通过有效的全局补丁评估，APRMCTS 能够快速识别错误路径，回溯到早期有潜力的候选路径，并逐步趋向正确的补丁。对于 APRMCTS，每次补丁搜索迭代可分为四个阶段：补丁选择、补丁生成、补丁评估、补丁树更新。在补丁选择阶段，APRMCTS 首先根据 UCT（树的置信上限）值从补丁树中选择已探索的补丁。然后在补丁生成阶段，APRMCTS 通过 CoT 激励 LLM 对所选补丁进行修复，并对生成补丁进行自我反思。在补丁评估阶段，生成的补丁在测试用例中的正确性会被验证。对于测试失败的补丁，APRMCTS 会评估其质量，然后将它们添加到补丁树中。具体来说，本文根据测试案例是否充分，自适应地采用 LLM-as-Judge 和 Test-as-Judge 策略进行评估。在补丁树更新阶段，从选定补丁向上反向传播到补丁树的根节点。经过一定次数的迭代（本文工作中的16次和32次），APRMCTS 会输出所有可能用于补丁验证的补丁。

与以往基于LLM的APR技术相比，APRMCTS具有以下优势。

(1) 多径 + 长轨迹搜索

• 多路径 APRMCTS利用蒙特卡洛树搜索（MCTS），使模型能够同时调查多条路径，而不是将全部预算花费在一条可能无效的路径上。这种广度避免了搜索被局限于局部最优——这在修复复杂漏洞时尤为常见。
• 长轨迹 APRMCTS进行深入、渐进的探索，稳步收敛到正确的补丁，而不是在第一次失误后停滞不前。这种延长的路径对于需要多次试错才能找出和解决根本原因的漏洞来说是不可或缺的。

在结果方面，APRMCTS 修复了 Defects4J 上835个漏洞中的201个，超过了所有10个最先进基线。

(2) 灵活性和通用性

APRMCTS灵活，能无缝兼容任何大型语言模型。APRMCTS也可推广到不同的搜索算法。虽然本文采用代表性的 MCTS 来展示 APRMCTS 的有效性，但它也可以被其他搜索算法替代，比如VI-A节提到的束搜索。

(3) 高效率

APRMCTS采用严格的补丁评估模块，提前剔除低质量候选补丁，因此有限的搜索预算集中于最有前景的补丁，提升修复效率和成功率。例如，APRMCTS采用的补丁规模（16和32）比以往研究中使用的更小。

本文作出以下贡献：

• 本文提出了APRMCTS，利用树搜索优化基于LLM的APR流程，代表APR领域的一项新技术尝试。APRMCTS具有多重优势，如架构灵活、高效性和高效性。本文的代码和结果可以在 github 仓库中找到。
• 本文结合10个最先进的基线（包括基于学习、基于模板和基于LLM的APR技术）及13个代表性LLM进行了评估。实验结果显示，APRMCTS优于现有基线，分别修复了Defects4J-v1.2和Defects4J-v2上的108个和93个错误。
• 本文采用了七个表现最好的大型语言模型实现APRMCTS。结果显示，APRMCTS平均能修复比普通LLM多20%的错误，展示了其在增强多种LLMAPR能力方面的模型无关性。
• 本文验证了 APRMCTS 在 ConDefects 上的多语言（Python/Java）和多类型（仓库/竞赛）漏洞修复能力。与 ChatRepair 相比，本文发现 APRMCTS 更快，且节省了超过50%的经济成本。

背景和动机

自动程序修复

自动程序修复（APR）旨在帮助开发者自动本地化和修复程序错误。传统的APR技术可以分为基于启发式、基于约束和基于模板。现代APR方法主要基于深度学习，改进了以往APR方法的不足。基于学习的方法在性能与效能之间取得了平衡，同时提供了更强的泛化能力。作为基于学习的方法的一部分，神经机器翻译（NMT）技术近年来被广泛研究，它们共同认识到APR可以被视为一种旨在将错误代码转换为正确代码的NMT问题。基于LLM的方法进一步利用LLM的代码相关能力，通过零样本或少数样本方法修复错误，减少对高质量训练数据集的依赖。Xia 等人对基于各种大型语言模型（如Codex 、GPT-NeoX 、CodeT5 、InCoder ）的APR技术进行了广泛研究，证明了基于LLM的APR的优越性。最近，ChatRepair 利用 GPT-3.5 修复错误，并获得了最先进的结果。本文的研究深入研究了各种类型的现代大型语言模型，并全面评估它们修复漏洞的能力。

在此基础上，本文借鉴了以往的研究，采用迭代算法优化大型语言模型在APR上的表现。本文采用基于搜索的方法，将LLM与MCTS算法集成。本文提出的方法APRMCTS，可以作为一种适用于可变LLM的APR框架。

蒙特卡洛树搜索

蒙特卡洛树搜索（MCTS）用于增强复杂场景中的决策能力，并在围棋等策略游戏中取得显著效果。MCTS 是一种多轮迭代算法，每一轮通常包含四个关键阶段：基于UCT策略的选择，以确定潜在的探索起点；扩展，新增节点；评估，用于评估新扩展的节点；以及反向传播，基于评估结果更新节点值。与其他搜索方法相比，如深度优先搜索（DFS）和广度优先搜索（BFS），后者往往存在局域错误和庞大搜索空间等缺点，MCTS能够在效率与效能之间取得平衡。之前的研究（MathBlackBox ）利用 MCTS 指导 GPT-4 解决奥运级别的数学问题。最近，研究人员发现MCTS有助于提高代码生成、测试生成和程序调试等代码相关任务的效率。虽然本文的工作涵盖不同的搜索算法，但本文采用交互式树搜索算法MCTS实现。这种方法使大型语言模型能够迭代选择、搜索和评估补丁，从而以更低的成本生成更多正确的补丁。

动机示例

为了更好地说明现有基于LLM的APR方法的局限性，本节还举了一个动机示例。如图1所示，本文使用了Defects4J 的真实错误 $Jsou{p}_{54}$，并对其评估了三种典型的基于 LLM 的 APR 方法（如单路径搜索、遗传算法、采样）。本文发现这三种方法都没有有效效果。由于函数调用参数的顺序不正确，且参数可能的值众多，在有限的样本量内通过直接抽样找到正确解是不可行的。对于单路径搜索，这种方法会不断尝试修复生成的第一个错误补丁，忽略其他潜在的解决方案。对于遗传算法，它同样因缺乏有效的补丁维护高质量补丁池的评估机制而失败。

本文进一步尝试使用 MCTS 进行补丁搜索，发现它成功修复了 $Jsou{p}_{54}$。这是因为 MCTS 使模型能够选择并优先排序搜索路径。尽管模型最初探索的是错误路径，MCTS算法利用补丁评估机制迅速终止沿错误路径的搜索，扩大搜索范围，最终识别出正确的补丁。基于这个例子，本文可以观察到，尽管现有的APR方法可以利用LLM提升修复效果，但它们仍然缺乏高效的补丁搜索策略来处理复杂漏洞。本文结合MCTS与设计良好的补丁评估策略，指导大型语言模型高效地进行补丁搜索。

方法

本文进一步尝试使用 MCTS 进行补丁搜索，发现它成功修复了 $Jsou{p}_{54}$。这是因为 MCTS 使模型能够选择并优先排序搜索路径。尽管模型最初探索的是错误路径，MCTS算法利用补丁评估机制迅速终止沿错误路径的搜索，扩大搜索范围，最终识别出正确的补丁。基于这个例子，本文可以观察到，尽管现有的 APR 方法可以利用 LLM 提升修复效果，但它们仍然缺乏高效的补丁搜索策略来处理复杂漏洞。本文结合 MCTS 与设计良好的补丁评估策略，指导大型语言模型高效地进行补丁搜索。本节介绍 APRMCTS 中使用的概念、APRMCTS的整体工作流程以及流程中的每个阶段。图 2 展示了 APRMCTS 的工作流程，该流程由四个阶段组成。在补丁选择阶段，详见 III-B1 节，从补丁树中选出部分补丁，目标是将其精炼成一个可行的候选补丁。在补丁生成阶段，详见 III-B2，基于选定的部分补丁生成新补丁，利用思维链（CoT）推理和自我反思技术，提升生成补丁的质量。在补丁评估阶段，详见 III-B3，生成的补丁采用两种评估策略评分： LLM-as-Judge 和 Test-as-Judge 。在补丁树更新阶段，详见 III-B4，整个补丁树会更新以反映所有补丁的状态。

概念

在介绍之前，首先本文解释了APRMCTS中使用的概念。

• 补丁树（Patch Tree） APRMCTS以补丁树的形式组织探索补丁。树的根节点是原始的错误，可以视为一个特殊补丁。新发现的补丁作为子节点被添加到补丁树中。
• 父补丁（Parent Patch） 如果补丁 A 是补丁 B 的父补丁，则意味着基于 a 生成 b。
• 子补丁（Son Patch） 如果补丁 A 是补丁 B 的子补丁，则意味着基于 b 生成 a。
• 补丁规模（Patch Size） 针对某个漏洞应用的候选补丁数量。

阶段与模块

给定一个有漏洞的程序，修复过程首先将原始有缺陷的代码视为一种特殊形式的补丁，该补丁被初始化为补丁树的根节点。随着修复的进行，新生成的补丁会作为子节点逐步添加到树中的父补丁中。

补丁选择

在补丁选择阶段，APRMCTS 旨在从补丁树中识别出最有前景的补丁，随后在后续阶段将其精炼成新的候选补丁。在本研究中，本文将树的上置信度界限（UCT）作为选择准则。UCT 同时考虑子补丁的平均质量和探索程度，从而提供更全面的补丁潜在正确性评估。越高的 UCT 表示从对应的补丁开始搜索更有可能找到合理的补丁。在一般标准 MCTS 流程中，UCT 的定义如下：
$$UC{T}_j={\bar{X}}_j+C\sqrt{\frac{2\ln N_C}{N_j}}\text{\hspace{1em}(1)}$$
其中 ${\bar{X}}_j$ 是所有可能动作的平均奖励，$N_C$ 是父节点的总访问时间，$N_j$ 是子节点 j 被访问的次数，C 是平衡利用与探索的常数。在补丁选择阶段，APRMCTS 为每个补丁计算 UCT 值，并从现有补丁树中选择 UCT 最高的补丁。

补丁生成

在补丁生成阶段，APRMCTS 旨在基于补丁选择阶段返回的部分补丁生成新的候选补丁。为此，APRMCTS 采用了整合 CoT 和自我反思的自我精炼策略，从而提升模型输出的质量。具体来说，APRMCTS 解析所选部分补丁中漏洞当前状态，并对错误线路及测试用例报告的错误进行全面分析。基于该分析，它对部分补丁进行修改和优化，生成新的候选补丁。这些新生成的补丁可能会重复之前探索过的部分补丁的错误，或者陷入新的错误，从而更新漏洞的状态。对于给定的LLM的 $\pi$，从先前探索的部分部分补丁 $a$ 生成新补丁 $a^{\prime }$ 的条件概率分布形式化如下：
$$\pi (a^{\prime }|a)=\prod _{k=1}^K\pi (a_k^{\prime }|a_{<k}^{\prime },a)\text{\hspace{1em}(2)}$$
其中 $k$ 表示 $a^{\prime }$ 的第 $k$ 个符号。

APR-specific CoT 本文设计了一个专门针对漏洞修复任务的提示，引导模型表达对漏洞及其修复方法的理解。通过利用CoT，APRMCTS 试图通过逐步流程实现 “补丁$a^{\prime }$”，促进透明度和结构化思维。该过程使模型能够根据对错误行为的解释识别并制定修复动作。此外，通过将失败测试用例的反馈纳入CoT，模型可以相应地调整或调整修复策略。

自我反思 生成一个 $a^{\prime }$ 补丁后，本文进一步提示模型通过自反思机制反思其输出。这一过程鼓励模型批判性地评估生成的补丁，识别潜在错误，并据此修正其解。通过启用这一自我修正步骤，模型能够生成更高质量、更可靠的补丁。

补丁评估

在补丁评估阶段，APRMCTS 旨在评估前一阶段返回补丁的正确性和质量，从而引导大型语言模型识别潜在正确的补丁。补丁生成阶段后，本文执行测试用例以验证生成补丁 $a^{\prime }$ 的正确性。如果补丁通过所有测试案例，则标记为合理补丁，并保留供进一步人工检查。如果任何测试用例失败，将被视为需要后续细化的部分补丁，并作为新补丁节点添加到现有补丁树中，供继续探索。随后，APRMCTS 使用两种评估策略对生成的补丁进行质量评估：LLMas-Judge 和 Test-as-Judge。

LLM-as-Judge 该策略利用大型语言模型（LLM）在测试覆盖有限的场景中对生成补丁的质量进行评分。例如，Defects4J 数据集中相当一部分的错误仅与单一故障触发测试案例相关。在这种情况下，仅依赖测试结果可能导致奖励信号稀疏，降低评估的准确性和修复过程的有效性。为解决这个问题，APRMCTS 采用 LLM 作为评判工具，基于语义和上下文信息评估补丁质量，而非仅凭测试结果。评估模型的输入包括测试用例、测试结果、有漏洞的代码、候选补丁、周围代码上下文、CoT的推理轨迹以及反射输出。LLM生成的原始得分在定义约束下进一步归一化，以确保奖励计算的一致性和公平性。最终奖励R（a）定义如下：
$$R(a)=\{\begin{array}{ll}0,& \text{if }Score(a)\le 0\\ 1,& \text{if }Score(a)\ge 100\\ \frac{Score(a)}{100},& \text{otherwise}\end{array}\text{\hspace{1em}(3)}$$

$$\mathbb{E}[R]=\frac{1}{N}\sum _{i=1}^N{R}_i\text{\hspace{1em}(4)}$$

为了处理边缘情况，本文设计了多种调整策略。对于未能编译的补丁，奖励设置为-1。对于与父补丁相同的补丁，原始奖励会被施加 0.5 的惩罚系数。由于 LLM 提供的分数会波动，本文还需要计算 R 的期望值。如方程4所示，R 的期望值是通过抽样 N 次（本研究中为5）次的奖励 R 并计算平均值得到，有助于平衡最坏情况和平均结果。补丁 $a^{\prime }$ 随后被封装到树节点中，并加入补丁树。此外，采用自评估策略，即在补丁生成和评估中使用相同的 LLM。这一设计选择降低了树搜索过程中的计算开销，本文的实验结果表明自我评估对修复策略的整体有效性有积极贡献。

Test-as-Judge 该策略旨在修复具有足够测试用例的漏洞修复数据集（例如 ConDefects），每个 bug 关联十多个涵盖广泛场景和边界条件的测试用例。在此情况下，结合先前研究的支持，本文认为依赖测试执行结果为评估补丁质量提供了高度可靠的依据。具体来说，如方程 5 所示，奖励 R 被计算为通过测试案例的比例，代表候选补丁的测试通过率：
$$R(a)=\frac{|T_{passed}|}{|T_{total}|}\text{\hspace{1em}(5)}$$

$$\mathbb{E}[R]=R\text{\hspace{1em}(6)}$$

补丁树更新

除了在每代后立即使用 R 评估补丁质量外，本文还利用 MCTS 的知识，利用 Q 值在整个搜索过程中评估补丁质量。Q 值不仅取决于补丁自身的质量 R，还取决于其子补丁的质量。在计算出生成补丁的奖励 R 后，本文使用以下方程 7 更新其父补丁的 Q 值：
$$Q^{\prime }(a)=\beta \frac{{\sum }_{j=1}^n(Q_j\cdot N_j)}{{\sum }_{j=1}^n{N}_j}+(1-\beta )Q(a)\text{\hspace{1em}(7)}$$
其中 $\beta$ 是一个遗忘因子，范围从0到1，N 代表子女数量。当 $\beta$ 更接近1时，表明新 Q 值受旧值影响较小。在本文的工作中，本文将 $\beta$ 设置为0.8。

在每次迭代中，APRMCTS 都会经过上述四个阶段，搜索和评估新补丁，然后根据发现的补丁和评估结果启动下一轮搜索。完成所有搜索迭代后，本文会对记录的合理补丁进行人工验证。如果它们与开发者补丁匹配或语法等效，本文就视为正确的补丁；否则，它们就被视为错误的补丁。

实验设置

研究问题

本文根据以下研究问题评估APRMCTS：

• RQ1 APRMCTS与最先进的APR技术相比如何？
• RQ2 APRMCTS 与使用基础大型语言模型相比如何？
• RQ3 APRMCTS的每个组成部分对整体效果有多大影响？
• RQ4 APRMCTS在修复跨语言和多种类型的错误方面有多有效？
• RQ5 APRMCTS 能通过大补丁规模修复更多漏洞吗？
• RQ6 APRMCTS的成本与现有方法相比如何？

数据集

本文基于三个广泛采用的基准测试来评估APRMCTS：QuixBugs、Defects4J和ConDefects。这些数据集常用于APR文献，涵盖多种编程语言和漏洞类型。QuixBugs 是一个规模较小但颇受欢迎的缺陷数据集，包含 40 个 Java 和 Python 版本的函数级程序错误，本文只使用 Java 部分。Defects4J 是来自真实 Java 开源项目的 bug 集合，包括 Defects4J-v1.2 的 395 个漏洞和 Defects4Jv2 的 440 个 bug。ConDefects 是一个竞赛错误数据集，包含526个Python漏洞和477个Java漏洞。本文选择Python子集来评估APRMCTS的多语言和多类型错误修复能力。

基准

本文将APRMCTS与来自不同类别的十个最先进的APR基线进行比较，其中包括五个基于学习的基线（如SelfAPR 、ITER 、CURE 、RewardRepair 、Recoder ）、两种基于模板的基线（即Repatt和GAMMA ）以及四个基于LLM的基线（如RAPGen 、GAMMA 、ChatRepair 、RepairAgent ）。具体来说，ITER通过迭代扰动正确程序生成正确的样本对，并通过自我监督培训学习维修经验。RAPGen 结合了检索增强生成（RAG）和 APR，从已修复的类似错误中学习修复错误模式。RepairAgent 采用基于大型语言模型（LLM）的代理技术进一步提升修复效果。GAMMA 修订了基于模板的 APR 技术的多种固定模板，并将其转化为掩码模式。此外，本文选择了13个参数大小不同的大型语言模型作为基线，包括5个3B模型、6个7–9B模型和两个API可访问模型。

评价指标

本文考虑了三种广泛使用的指标，以评估APRMCTS和基线的有效性，以及生成贴片的质量。度量的定义如下。

• 正确修复（CF）定义为正确修复的错误数量，这些漏洞能通过所有测试，并需人工检查以确保与开发者补丁在语义或语法上等价。
• 合理修复（PF）定义为修复后能通过所有测试且不进行进一步检查的漏洞数量。
• 精确匹配（EM）定义为与开发者补丁完全匹配的修复数量。

实验其他细节

为了实现APRMCTS，本文使用OpenAI提供的API和 Hugging Face 上的模型进行初始化。本文用 tiktoken 来统计 API 调用中消耗的代币数量并计算成本。温度设置为 0.9，最大 token 设置为 8000，补丁规模设置为16。对于主要模型（GPT-3.5），本文进行了额外的实验，将补丁规模设置为32。探索常数设为0.7，阿尔法设为0.8，分支和最大扩展分别设为1和3。本文基于PyTorch和Transformers框架实现APRMCTS。所有实验均在一台 Ubuntu 20.04 服务器上使用两块 NVIDIA Tesla V100 GPU。

评估与结果

问题1 与最先进技术的比较

实验设计 在RQ1中，本文旨在评估APRMCTS的性能。本文以10种先前的APR方法和13种大型语言模型为基线。为消除模型规模引起的潜在干扰，本文选择7个不同规模和类型的表现最佳模型作为后续实验中APRMCTS的基础模型。

整体表现 表I展示了APRMCTS与Defects4J和QuixBugs基准基线的比较结果。在 Defects4J 数据集中，APRMCTS 获得了最高的 201 个错误修复，修复比第二名 RepairAgent 多 37 个，且表现优于其他基于搜索的方法（如 ITER）。特别是，APRMCTS修复了On Defects4J-v1.2和Defects4J-v2的108个和93个错误，分别排名第二和第一。虽然APRMCTS修复的bug比Defects4J-v1.2上的ChatRepair少6个，但考虑到补丁规模设置的不同，这是可以接受的。ChatRepair 平均每个漏洞生成并测试 500 个候选补丁，而 APRMCTS 每个漏洞仅生成 32 个候选补丁。此外，APRMCTS能够提供比以往研究更合理的解决方案。具体来说，APRMCTS共获得280个合理的修复，比RepairAgent多94个合理的修复。本文在表II中列出了项目级的bug修复数量。当本文将APRMCTS与RepairAgent和ChatRepair进行比较时，发现三种方法之间的bug-fix分布相当一致。APRMCTS在Compress、JacksonDataBind和Jsoup上的表现显著优于另外两个基线。本文还在 QuixBugs 数据集上评估APRMCTS。结果显示，APRMCTS能够修复QuixBugs中的所有漏洞。

重叠分析 图3展示了RapGen 、RewardRepair 、SelfAPR 、CURE 和APRMCTS在Defects4J-v1.2和Defects4Jv2上修复的漏洞的维恩图。提到RAP-Gen在Defects4J-v1.2和Defects4J-v2上有13个和6个重复补丁，因此RAP-Gen实际修复的bug数量应为106（59+47）。图3显示APRMCTS具备出色的修复能力，分别修复了DefectsJ-v1.2和v2上的48个和52个独特bug，相较于其他4个基线。此外，本文还分别取用两个表现最好的基于LLM的基线RepairAgent 和ChatRepair ，与APRMCTS进行重叠分析。图4（a）和图4（b）显示，Defects4J-v1.2和v2上分别有54,25个bug可通过三种方法修复，表明这三种方法都非常有效且具有相当显著的相似性。这是因为这三种方法采用了相同的骨干模型。尽管如此，APRMCTS仍能分别修复Defects4J-v1.2和Defects4J-v2上的18个和25个独特错误，这在三种方法中排名第二和第一，显示出APRMCTS的优越性。

个案研究 为了更好地说明APRMCTS的发展，本文提供了几个值得注意的修复方法。APRMCTS 可以修复ChartRepair 提到的 $Gso{n}_{15}$ 和 $Lan{g}_{16}$ 作为独特修复。本文还进一步展示了APRMCTS结果中的独特修复方法，如图5所示。$Cl{i}_{19}$ 是 Defects4J-v2 中一个功能级错误，无法仅通过替换一两条有漏洞的行来修复。相反，修复这个漏洞需要在多个地方修改函数，这给APR带来了很大困难，没有基线能解决。解决 $Cl{i}_{19}$ 的关键在于理解在所有条件分支下 $Tokens.add(token)$ 动作都是必不可少的。如图5所示，APRMCTS得到的是一个与开发者补丁不同但语义等价的正确补丁。

RQ1 结果 APRMCTS在合理/正确修复方面显著优于以往所有APR方法，Defects4J-v1.2修复了108个，Defects4J-v2修复了93个，QuixBugs修复了40个。

问题2 与大型语言模型的比较

实验设计 本文已证明APRMCTS在多种APR技术和大型语言模型中都能实现令人印象深刻的性能。本节进一步探讨APRMCTS在不同底层大型语言模型上提升性能的程度，以及这些提升是否归因于本文提出的框架，而非模型本身的固有能力。为此，本文在RQ1中从每个模型尺度类别中挑选了七个表现最好的大型语言模型，并应用本文的框架。

整体表现 表 III 展示了 APRMCTS 在不同底层模型中实现的性能提升。结果显示，应用APRMCTS后，七个LLM的修复能力通常有所提升。其中，Yi-Coder-9B、Qwen2.5-Coder-7B、GPT-4o-mini 和 GPT-3.5 分别带来了最显著的改进，分别增加了 37、28、30 和 27 个漏洞修复。此外，将补丁规模设置为32时，GPT-3.5（APRMCTS）可修复201个漏洞，比原版GPT-3.5多69个修复。Llama-3.1-8B 和 Qwen2.5-Coder-3B 都有一定改进，且都修复了 9 个漏洞。

就bug类型而言，修复单线（SL）和单块（SH）bug的成功率明显高于单功能（SF）bug。对于前两种类型的漏洞，LLM可以精确定位有缺陷的路径，且漏洞程序的逻辑相对简单，相比SF漏洞需要更少的修改。因此，LLM修复SF的bug更难。与原版大型语言模型相比，本文注意到APRMCTS显著提升了大型语言模型修复SF漏洞的效果，GPT-4o-mini修复了12个SF漏洞，GPT-3.5修复了8个SF漏洞，YiCoder-9B修复了14个SF漏洞，Qwen2.5-Coder-7B修复了8个SF漏洞，Qwen2.5-Coder-3B修复了4个SF漏洞。这表明APRMCTS在修复复杂错误方面具有特别优势。

RQ2 结果 APRMCTS与原版LLM的比较结果显示，在相同补丁规模（例如16）和骨干模型下，APRMCTS在Defects4J 上的修复效果可提升超过20%，例如提升GPT-3.5 20.45%（132 → 159），提升GPT-4o-mini 23.43%（128 → 158）。

问题3 各组成部分的有效性

实验设计 在RQ3中，本文进行消融研究以验证每个组成部分的有效性，包括测试信息、CoT提示和搜索/评估。本文逐步将每个组成部分纳入方法，以观察其对性能的影响。

• RQ3.1 测试信息的有效性：如表IV所示，测试信息对所有LLM的修复效果都有积极影响，GPT-4o-mini和GPT-3.5分别修复了21个和18个bug，取得了显著改进。

• RQ3.2 CoT的有效性：本文采用基于原版大型语言模型的CoT，以指导LLM生成补丁之前提供思考过程。本文将CoT与另一种流行的推理策略——思维树（Tree of Thought (ToT)）以及原版大型语言模型（LLM）进行比较。如表 V 所示，大多数LLM在CoT方面相较于普通LLM表现出显著提升。Yi-Coder9B和GPT-3.5进步最大，CF分别增加了31和7，PF增加了32和10。使用 ToT 时，GPT-4omini、Llama-3.1-8B 和 Stable-Code-3B 分别在 CF 中减少了 7、19 和 2。相比之下，CoT在7个大型语言模型中表现通常优于ToT。

  EM评估LLM匹配开发者地面真实补丁的能力，而低EM可能导致过拟合问题。可以看出，CoT在EM上的提升相对稳定，GPT-4o-mini提升了2.83%，GPT-3.5提升了2.86%，Qwen2.5-Coder7B提升了3.03%，Qwen2.5-Coder-3B提升了3.59%，Llama-3.1-8B提升了3.98%，Stable-Code3B提升了3.7%。

• RQ3.3 搜索与评估的有效性：为评估搜索和评估组件对APRMCTS整体效果的影响，本文将其性能与CoT增强和普通LLM基线进行比较。如表VI所示，所有七个LLMs在APRMCTS下相较于仅使用CoT和原版LLMs的有效性有所提升。特别是，GPT-3.5（APRMCTS）修复的bug比GPT-3.5（CoT）多20个。GPT-4o-mini（APRMCTS）修复的bug比GPT-4o-mini（CoT）多27个，Yi-Coder-9B（APRMCTS）修复的bug比YiCoder-9B（CoT）多6个。此外，随着补丁规模增加到 32，配备 APRMCTS 的 GPT-3.5 可以修复 42 个额外漏洞。

在比较不同规模的大型语言模型性能时，本文发现像GPT-4o-mini、GPT-3.5、Yi-Coder-9B和Qwen2.5-Coder-7B这样的大型模型，相比之下，Qwen2.5-Coder-3B和Stable-Code-3B等小型模型的提升更为显著。对于GPT-4o-mini和GPT-3.5，在比较APRMCTS与原版LLM时，90%（27/30）和74%（20/27）的bug修复提升分别归功于搜索和评估。对于Yi-Coder-9B、Qwen2.5-Coder-7B、Qwen2.5-Coder-3B和Stable-Code-3B，这一比例分别为16%（6/37）、28.5%（8/28）、36%（4/11）和50%（2/4）。研究表明，大尺度模型相比小尺度模型从搜索中获益更大。这是因为大尺度模型在补片评估上更为准确，而准确的评估有助于引导搜索方向。

本文还观察到，随着贴片规模的增加，搜索和评估开始发挥更重要的作用。对于 Llama 3.1-8B，当补丁规模在 8 到 12 之间时，APRMCTS 修复的 bug 数量略少于 CoT。然而，随着补丁规模的增加，APRMCTS的性能逐渐追平CoT（当补丁规模=14时），随后在补丁规模>14时超越CoT。Qwen2.5-Coder3B也表现出同样的趋势，当贴片长度超过14时，APRMCTS表现优于CoT。这表明，随着补丁规模的增加，APRMCTS能够解决其他方法无法解决的更复杂错误。

RQ3 结果 所有组成部分，包括测试信息、CoT、搜索和评估，都对APRMCTS产生积极影响。其中，测试信息对所有大型语言模型都有效（例如，帮助GPT-4o-mini修复了另外21个漏洞）。CoT对6/7个大型语言模型有效（例如，帮助Yi-Coder9B修复了31个额外漏洞）。搜索和评估对所有大型语言模型都有效（例如，帮助GPT-4o-mini修复了另外30个漏洞）。此外，大型模型能更准确地评估补丁质量，从而带来更好的搜索结果（例如，GPT-3.5修复了27个bug，而Qwen2.5-Coder3B只修复了8个）。

问题4 多语言和多类型漏洞的有效性

实验设计 在RQ 1-3中，本文验证了APRMCTS对项目级Java漏洞（如Defects4J）的有效性。为了进一步验证APRMCTS对不同类型和不同语言错误的修复能力，本文在ConDefects-Python数据集上进行了额外实验。本文将APRMCTS与ChatRepair、GPT-3.5和AlphaRepair进行比较。为了确保公平，本文遵循ChatRepair，并采用GPT-3.5作为实验性LLM。

结果分析 如表 VII 所示，当补丁规模=48（16次迭代，每次迭代3个补丁）时，APRMCTS获得了211个合理的修复和204个正确修复，比ChatRepair多40个合理修正和39个正确修复。由于ChatRepair的补丁规模设置为500，可以看出即使补丁规模不到十分之一，APRMCTS仍然显著提升了LLM的补丁搜索性能。当本文将搜索迭代增加到32次并将补丁规模设置为96时，APRMCTS的性能进一步提升，包含287个合理修复和264个正确修复，比ChatRepair多出23个/38个正确/合理修复。此外，本文发现测试作为法官使大型语言模型能够快速生成满足简单测试用例的补丁，然后通过复杂的测试用例迭代细化补丁细节，直到满足所有边界条件。与允许模型在无评估的情况下搜索补丁相比，测试作为法官引导LLM朝正确修复方向前进，提高了补丁搜索的效率。

上述实验结果表明，APRMCTS在修复跨多种语言（Java/Python）和多种类型（Repository/Competition）的错误方面，相比以往方法和原版LLM具有显著优势。

RQ4 结果 APRMCTS在多语言和多类型错误修复方面表现出色，成功修复了仓库级Java缺陷数据集Defects4J中的201个错误，并在竞赛级Python缺陷数据集ConDefects中修复了264个错误，比第二好的ChatRepair多23个。

问题5 大补丁规模的有效性

实验设计 RQ 1-4已证明APRMCTS在小补丁规模（如16、32）下有效。为了进一步探讨大补丁规模的影响，本文选择了GPT-3.5进行极端测试。本文将补丁规模从 32 增加到 500（50 次迭代，每次迭代 10 个补丁），以符合 ChatRepair 的配置。

结果分析 本文在表VIII中列出了新修复的漏洞，其中✓表示正确的修复，×表示合理但不完全正确的修复。可以观察到，较大的补丁规模（500）会带来更合理的修复（16）和正确的修正（11）。然而，随着补丁规模的增加，新修复的漏洞数量显著减少。这表明APRMCTS已接近上限。

RQ5 结果 更大补丁规模（32→500）帮助APRMCTS修复了11个漏洞，表明增加的搜索预算进一步提升了修复效果。

问题6 成本分析

实验设计 在RQ6中，本文旨在分析APRMCTS与现有APR工具在补丁规模、时间、代币消耗和成本上的差异。具体来说，本文选择了 ChatRepair 和 RepairAgent 作为基线，并以 Defects4J 上的价格进行比较。

结果分析 比较结果见表IX。补丁规模设置为32，是三个基线中最小的，APRMCTS平均每个漏洞持续50分钟，比ChatRepair短。此外，APRMCTS在平均代币消耗和每个漏洞的货币成本方面也具有显著优势，ChatRepair报告的21万代币仅占19%，占RepairAgent报告的27万代币的14.8%。在定价方面，本文基于当前的API价格计算。APRMCTS 的每个 bug 成本为 0.06 美元，占 ChatRepair（0.14 美元）和 RepairAgent（0.14 美元）的 43%。

RQ6 结果 APRMCTS证明了其低成本和高性能效率，平均每个bug耗时50分钟，成本为0.06美元，仅占基线的16.7%和43%。

讨论

与其他搜索算法实现APRMCTS

为了展示APRMCTS的灵活性，本文用其他搜索算法（例如束搜索）替代了MCTS。具体来说，本文初始化了一个大小为4的补丁池。在每次迭代中，本文应用束流搜索算法，细化补丁池中的每个补丁，评估新生成的补丁，并保留得分最高的4个补丁以备下一次迭代。波束宽度设置为5，迭代次数设置为3。本文使用Qwen2.5-Coder-7B进行比较实验。结果显示，Beam Search 实现了 149 个合理的修复和 88 个正确修复，比原版多修复了 9 个 bug，比 MCTS 少了 19 个。这展示了APRMCTS在多种搜索算法中的可扩展性和有效性，也表明MCTS搜索算法在错误修复场景中优于束搜索。

数据泄漏分析

由于GPT只能通过API访问，本文无法确定其训练数据，这存在数据泄露风险。为解决此问题，本文采取了以下措施。对于开源模型（如Qwen），本文仔细检查了它们的预训练数据集，并确认与基准测试没有重叠。对于黑箱模型（如GPT），本文遵循先前研究，并在评估中包含ConDefects数据集，以降低数据泄露风险。本文还会参考之前的工作、，并比较GPT生成的补丁与开发者修复的参考。在 Defects4J 上，本文发现 GPT-3.5 生成了 61 个与开发者补丁相同的补丁。即使移除了与开发者补丁重叠的61个补丁，APRMCTS仍然正确修复了49个（55→49个）RepairAgent和ChatRepair无法触及的独特漏洞。此外，本文还在Condefects-Python上使用另一款开源模型Qwen2.5-Coder-32B进行补充实验。本文将开发者编写的补丁与模型生成的补丁进行比较，发现Qwen2.5-Coder-32B和GPT-3.5分别实现了29和32个精确匹配，差距非常小。因此，本文得出结论，数据泄露的影响较小。

APRMCTS在SWE-Bench上的潜力

除了 Defects4J，本文还在 SWE-Bench 上评估 APRMCTS，这是一个由 GitHub 问题组成的缺陷数据集。本文使用开源的 Qwen3-Coder-480B 作为基础模型。本文使用与 Defects4J 相同的配置，将补丁规模设置为 16，并根据测试报告和补丁内容对补丁进行评分。本文直接使用数据集中提供的测试用例和完美本地化，以便评估APRMCTS的补丁搜索能力。如表X所示，与原版LLM相比，APRMCTS帮助Qwen3-Coder480B修复了51个bug。与ChatRepair相比，APRMCTS修复了35个bug。此外，APRMCTS的表现优于近期方法如KGCompass 和OpenHands。未来工作中，APRMCTS可与先进的故障定位和测试生成工具、、集成，形成具有强大修复能力的基于代理的框架。

对有效性的威胁

内部威胁 主要的内部威胁是APRMCTS中数据泄露的可能性。为此，在VI-A节，本文通过三种方法评估数据泄露的影响：分析开源模型的训练数据（包括更多基准测试），以及考察大型语言模型与开发者补丁生成的重叠补丁数量。此外，本文还使用Qwen2.5-Coder-32B对ConDefects进行了额外的实验。因此，本文有信心数据泄露不会对本文发现的有效性构成重大威胁。

外部威胁 有效性的主要外部威胁在于基准的采纳。APRMCTS的性能可能无法推广到其他数据集。为缓解这一问题，本文对仓库级的漏洞（如 Defects4J）和竞争级别的漏洞（如 ConDefects）进行了评估。此外，APRMCTS对错误类型和编程语言具有中立性，使其能够直接集成到各种数据集中。因此，本文认为这一威胁对本文的结论影响极小，APRMCTS有潜力处理更复杂和多样化的漏洞。

总结

本文介绍了APRMCTS，采用迭代树搜索以改进基于LLM的APR。APRMCTS采用以下策略：（1）将MCTS纳入补丁搜索流程，以提高效率和效果。（2）对已探索的斑块进行全局评估，以避免陷入局部最优。本文对Defects4J 的835个漏洞进行的实验表明，APRMCTS能够修复共201个漏洞，优于其他十个最先进的基线。本文还在ConDefects-Python上进一步展示了APRMCTS的多语言、多类型错误修复能力。与现有基于LLM的年利率工具相比，APRMCTS更快，且降低了超过50%的货币成本。

启发

APRMCTS 提出的 MCTS 树搜索结合思维链（CoT）与自我反思机制，其中搜索树结构记录了多种修复路径，可提供修复分步指导，同时搜索树结构利用模型在 CoT 和反思阶段生成的中间推理文本（如错误原因分析、修复策略），是可帮助引导学生的自然语言提示。

相关知识链接

• 论文链接
• BibTex

@misc{hu2025tsaprtreesearchframework,
      title={TSAPR: A Tree Search Framework For Automated Program Repair}, 
      author={Haichuan Hu and Ye Shang and Weifeng Sun and Quanjun Zhang},
      year={2025},
      eprint={2507.01827},
      archivePrefix={arXiv},
      primaryClass={cs.SE},
      url={https://arxiv.org/abs/2507.01827}, 
}