读paper23-arxiv代码修复论文组2

https://arxiv.org/abs/2507.01827

MCTS

什么是 MCTS？

蒙特卡洛树搜索是一类树搜索算法的统称，简称 MCTS（ Monte Carlo Tree Search）。它是一种用于某些决策过程的启发式搜索算法，且在搜索空间巨大的游戏中会比较有效。那什么叫做搜索空间巨大呢？比如说，在上世纪90年代，IBM公司推出深蓝这个 AI，击败了当时国际象棋的世界冠军，而这个 AI 也比较简单粗暴，把整个国际象棋的搜索空间全部穷举出来，把整个游戏树全部列举出来，那么不管对手下什么，它都知道下一步怎么下可以把他下赢。而对于围棋这种游戏，围棋棋盘是 19*19 的，也就是说有 361 个落子的位置，那么如果我们想把所有围棋的棋局的可能列举出来，一般来说就是 361！，这个数量是比宇宙的原子数量还要多的，就算是世界上最强的超级计算机也无法把所有的可能性穷举出来，那么我们就需要用到类似于蒙特卡洛树搜索这样的稍微智能一点，更可行的办法去对围棋这个游戏可以进行棋盘式的搜索，然后进行决策，最后下赢人类选手。

从全局来看，蒙塔卡洛树搜索的主要目标是：给定一个游戏状态来选择最佳的下一步。

算法过程

算法过程一般有四步：

  • 选择（Selection）：选择能够最大化 UCB 值的结点

    UCB(Si)=Vi‾+clog⁡Nni,c=2UCB(S_i)=\overline{V_i}+c\sqrt{\frac{\log N}{n_i}},c=2

    其中，Vi‾\overline{V_{i}} 为该节点的平均价值大小；cc 为常数，通常取2；NN 为总探索次数；nin_i 为当前节点的探索次数。选择 UCB 值最大的子节点进行迭代。

  • 扩展（Node Expansion）：如果当前叶子结点不是终止节点（没有达到终止状态），那么就创建一个或者更多的子节点，选择其中一个进行扩展。

  • 仿真（Simulation）：从扩展节点开始，运行一个模拟的输出，直到博弈游戏结束。比如，从该扩展节点出发，模拟了十次，最终胜利九次，那么该扩展节点的得分就会比较高，反之则比较低。

  • 反向传播（Backpropagation）：使用随机搜索的结果来更新整个搜索树

在完成了反向传播这一步，我们就会持续迭代，回到选择这一步，然后再进行扩展仿真，然后再反向传播，再回到选择扩展仿真，不断地迭代下去，直到算法结束并且给出最终决策。

下面我将对算法的四个步骤做进一步的论述。

1. 选择（selection）

下面我对选择中 UCB 公式中的各项做一个解释。

UCB(Si)=Vi‾+clog⁡Nni,c=2UCB(S_i)=\overline{V_i}+c\sqrt{\frac{\log N}{n_i}},c=2

  • ViV_i：该结点下的平均 Value 大小，比如说，好的一步它的 Value 更大一些，差的一步相对来说要小一些
  • cc ：常数，通常可以取 2，相当于是加号两边式子的一个权重
  • NN：总探索次数，就是对所有的结点一共 explore 了多少次
  • nin_i：当前结点的探索次数
2. 扩展（Node Expansion）

下面通过一个例子来说明。

比如我们从根节点出发，它不是叶子节点，之后计算它的两个子节点的 UCB 值，比如说结点 3 的 UCB 值更大，但是它之前已经被访问过了，根据我们之前的流程图，该节点不会直接进行 ROLLOUT，而是枚举出当前节点所有可能的动作并添加到树中，那么我们枚举出了结点 3 可能有两个动作，所以形成了图(2)，然后接下来我们再看我们要采取哪种动作，这就是 Node Expansion。

3. 仿真（Rollout）

接着上面一步，根据我们的流程图，会将第一个新结点（结点 4）作为当前结点，会对它进行一个 Rollout。


那么这个 rollout 怎么做呢？它会进行一个随机检测，下面我用一段伪代码来表示 rollout 过程：

def Rollout(S_i): # S_i：当前状态
	loop forever: # 无限循环
		if S_i a terimal state: # 如果当前状态是个终止状态，比如说你赢了或者他赢了
			return value(S_i)   # 返回对 S_i 这个状态的价值，比如说你赢了，这个价值可能就会相对比较高
		
		# 假设还没到终止状态
		A_i = random(available_action(S_i)) # 随机选取当前状态下能够采取的一个动作
		S_i = simulate(A_i, S_i)   # 通过当前状态 S_i 与随机选取的动作 A_i 来计算出下一步的状态并赋值给 S_i

下面我再用图示进行说明。

来看下面这张图，假设我们从黄色节点 1 进行 Rollout，它随机决策到结点 2，然后再随即决策到结点 3，然后在随机决策一直到最后红色结点 7，该节点的状态是 terminal state，然后得到一个 value，然后再将 value 返回给黄色节点 1。

这一步其实也是蒙克卡罗树搜索的非常重要的一关，因为这一步很像是在用随机的方法去逼近整体的一个分布，你想，如果黄色节点 1 代表的是更好的一个动作的话，那么赢的概率就会更大一点。经过很多次的仿真，都会得到一个比较大的概率值，如果它是一个不好的策略，那么经过很多次的仿真，大概率是不会得到一个很好的概率。

4. 反向传播（Backpropagation）

在完成了 Selection，Expansion 和 Rollout 之后，我们再进行 Backpropagation。它是做什么的呢？

在 Rollout 中我们计算出了 value 之后，我们需要返回这个 value，那么对于它所有的父节点（下图黑线上的所有的结点），它们的探索次数全部 +1，它们的 value 也会进行一个累加，然后我们整个算法会 repeate 很多次，直到蒙特卡洛树能够给出当前状态下最好的一个解答，就是我到底应该怎么走。

那么四个步骤到此就结束了，但是之前提到过这个算法会一直进行迭代，那么这个算法到底什么时候结束？

算法何时终结？

一般的方法比如说游戏内棋手的限制时间，比如说，像围棋，国际象棋，在比赛当中每个棋手的时间都是有限制的，但是如果你用电脑肯定就有无限的时间，你可以将其全部穷举出来，但是这样是没有意义的。所以我觉得一个 AI 能够在规定时间内，尤其是时间越少越好，能够在更少的时间内做出更好的决策说明这个机器才更加的智能。如果给你无限的时间来做出一个决策，你可以暴力穷举出所有的可能性，其实就说明这个 AI 没有那么智能。所以一般来说我们会在规定时间范围内终结算法的迭代，然后给出最优的一个解答，下一步应该怎么走，然后再让对面去下棋，对面下完之后，你再进行一个搜索在规定时间内给出一个最优的。

还有一种就是固定迭代的次数。比如说，第一个 AI 迭代了 5000 次得到了一个比较好的结果，另一个 AI 用了 50 次就迭代出了一个比较好的结果，那么就基本认定第二个 AI 相对来说是比较智能的。所以我们也可以给出一个固定的迭代次数，比如说你算到 5000 次迭代就让蒙特卡洛树搜索停下来给出一个决策。

至于怎么给出一个决策呢？很简单，在迭代完成后，选择 value 更大的结点即可完成决策。

Approach

与MCTS近似的四个阶段，在补丁选择阶段，系统从补丁树中选取一个局部补丁，旨在将其优化为合理的候选补丁。在补丁生成阶段，基于选定的局部补丁生成新补丁，运用思维链推理和自反思技术来提升生成补丁的质量。在补丁评估阶段，通过两种评估策略（LLM-as-Judge和Test-as-Judge）对生成的补丁进行评分。在补丁树更新阶段，更新整个补丁树以反映所有补丁的最新状态。

补丁选择基于UCB的计算。

补丁生成从选定的局部补丁中解析当前缺陷状态，并对存在错误的代码行及测试用例报错信息进行全面分析。基于该分析结果，系统会修改并优化局部补丁，进而生成新的候选补丁。这里有一个问题，这些新生成的补丁可能重复先前探索过的局部补丁错误，也可能陷入新的错误模式，从而更新缺陷的状态，该研究通过COT和Self-Reflection进行缓解。

补丁评估阶段，通过两种评估策略（LLM-as-Judge和Test-as-Judge）对生成的补丁进行评分。

LLM-as-Judge利用LLM在测试覆盖率有限的情况下对生成补丁的质量进行评分。例如，Defects4J 数据集中相当比例的缺陷仅与单个触发失败的测试用例相关。在此类情况下，若仅依赖测试结果作为评判标准，可能产生稀疏的奖励信号，从而降低评估准确性并削弱修复效果。为解决这一问题，APRMCTS 采用 LLM-as-Judge 评估机制，其评判依据不仅包含测试结果，更注重补丁的语义相关性和上下文契合度。评估模型的输入包含：测试用例及其执行结果、存在缺陷的代码、候选补丁、周边代码上下文、思维链的推理过程以及自反思输出结果。

有一个疑问，这里能够给出存在缺陷的代码，相对于进行了缺陷定位，但论文没有提到定位相关的内容。按照overview中给出的例子，应该是用单元测试的报错行定位缺陷代码，但如果存在多个方法嵌套（比如比较极端的assert(f1(f2(),f3())==0)，该如何定位，还是说将涉及的所有函数都归为缺陷代码）

Test-as-Judge专为具有充分测试用例的错误修复数据集（如ConDefects）设计，奖励值R的计算公式为：通过测试用例的比例，即候选补丁的测试通过率。

补丁树更新除了使用奖励值R在每次生成后即时评估补丁质量外，借鉴蒙特卡洛树搜索（MCTS）的思想，引入Q值来评估补丁在整个搜索过程中的综合质量。Q值的计算不仅取决于补丁自身的质量R，还与其子补丁的质量相关。当生成补丁的奖励值R计算完成后，根据以下公式递归更新其父补丁的Q值。

Q′(a)=β∑j=1n(Qj⋅Nj)∑j=1nNj+(1−β)Q(a).Q^{\prime}(a)=\beta\frac{\sum_{j=1}^n(Q_j\cdot N_j)}{\sum_{j=1}^nN_j}+(1-\beta)Q(a).

其中，ββ 为取值0到1的遗忘因子，N表示子节点数量。当 ββ 越接近1时，表明Q值的新结果受旧值影响越小。

APRMCTS在每轮迭代中都会经历上述四个阶段，通过搜索和评估新补丁后，基于发现的补丁和评估结果启动下一轮搜索。完成所有搜索迭代后，我们将对记录的可信补丁进行人工验证：若与开发者补丁相匹配或语法等价，则判定为正确补丁；反之则视为错误补丁。

评估维度计算依据作用场景
即时评估R当前补丁测试结果单次生成的质量反馈
综合评估Q历史+子节点质量全局搜索路径优化

Q′(a)=β⏟新值权重⋅∑j=1n(Qj⋅Nj)∑j=1nNj⏟子节点加权平均+(1−β)⏟旧值权重⋅Q(a)Q^{\prime}(a)=\underbrace{\beta}_{\text{新值权重}} \cdot \underbrace{\frac{\sum_{j=1}^n(Q_j\cdot N_j)}{\sum_{j=1}^nN_j}}_{\text{子节点加权平均}} + \underbrace{(1-\beta)}_{\text{旧值权重}} \cdot Q(a)

  1. 参数含义

    • ββ：遗忘因子（0.8）
      • β→1β→1：倾向新观测值（取0.8）
      • β→0β→0：保留历史数据
    • NjN_j：子节点访问次数（反映探索深度）
    • QjQ_j：子节点Q值（反映子树质量）

  2. 更新逻辑

    • 递归更新：子节点质量反向传播至父节点
    • 动态平衡：
      • 分子 ∑(Qj⋅Nj)\sum(Q_j·N_j) 体现质量与探索频次的加权
      • 分母 ∑Nj\sum N_j 实现归一化处理
    • 权重分配：新子节点数据占80%权重，历史Q值占20%
1
2
3
4
5
6
graph LR
A[补丁选择] --> B[补丁生成]
B --> C[双轨评估]
C -->|更新R值| D[补丁树更新]
D -->|更新Q值| A
C -->|Test-as-Judge/LLM-as-Judge| C

Bug Fixing with Broader Context: Enhancing LLM-Based Program Repair via Layered Knowledge Injection

https://arxiv.org/abs/2506.24015

核心还是将缺陷相关的信息进行按照相关性分类（分层），逐层注入prompt，相当于一种变相的上下文压缩或者说summary

ICSE接收 https://arxiv.org/abs/2506.23100

EXPEREPAIR: Dual-Memory Enhanced LLM-based Repository-Level Program Repair

https://arxiv.org/abs/2506.10484

https://github.com/ExpeRepair/ExpeRepair