PR_docs/algorithm.md

Token-Aware MCTS 数据收集算法设计

本文是 method_zh.md 的算法细化版本。method_zh.md 说明整体方法为什么这样设计；本文说明实际数据收集时每一步应该怎样执行。

当前版本只确定第一部分：从一个 Student snapshot 出发，如何执行 MCTS 式探索。Snapshot 选择权重、以及探索结束后的 root-to-leaf 轨迹选择，将在后续章节继续补充。

1. MCTS 探索算法

给定一个 Student snapshot，我们把它作为一棵探索树的 root。root 继承 snapshot 中的代码状态和共享知识库状态，但不继承 Student 的 OpenCode 历史上下文。Teacher 从 root 启动多个并行新的 OpenCode session（即Agent实例）。之后，树中任意一条 root-to-leaf 路径都保留自己的 Teacher session 上下文；当需要从某个节点扩展多个方向时，从该节点 fork 出新的代码状态、共享知识库状态和 OpenCode session 状态，然后分别继续探索。

树上的有效节点只包括成功完成评测并拥有数值 score 的状态。失败的扩展不会生成树节点，也不会作为“坏子节点”挂到树上；它只会增加父节点的失败扩展计数。也就是说，children 表示真实存在的有效子节点数量，invalid_children 或者说是 failed_expansions 只是父节点的一个计数性质，两者不会重合。

1.1 逻辑边：两个 Rollout Turn 合并为一个探索单元

为了控制总开销，MCTS 中的一条逻辑边不再只包含一次 Rollout Turn，而是包含连续两次 Rollout Turn。也就是说，从父节点出发后，Teacher 连续执行两轮：

work -> coral eval -m -> receive score/feedback
work -> coral eval -m -> receive score/feedback

这两次 Rollout Turn 共享同一个 fork 出来的 OpenCode session。只有第二次 Rollout Turn 结束后的状态会成为树上的子节点；中间状态只作为该边内部的过程记录，不单独成为树节点。

这样做的目的很直接：把树的最大深度从“8 个 Rollout Turn”压缩成“4 条逻辑边”，同时仍然保留最多 8 轮 eval 的连续自我改进行为。

合并后的逻辑边按下面规则聚合指标：

• 该子节点的 score 取两次 Rollout Turn 中的最大 score。
• 该逻辑边的 Step Turn 数量取两次 Rollout Turn 的总和。
• 工具错误率按两次 Rollout Turn 的整体工具调用统计计算。
• 只要任意一次 coral eval -m 没有返回数值 score（即评测命令超时或由于提交代码原因报错），这条逻辑边失败。
• token 长度使用这条逻辑边结束时的 session 上下文长度；直观上可以理解为两次 Rollout Turn 消耗后的累计上下文。
• outcome 判断使用两次 score 的最大值，与父节点 score 比较。
• knowledge 判断把两次 Rollout Turn 合并看：必须要两次中都发生了共享知识读取或写入（可以只读或只写），就认为该边有 knowledge 行为。

1.2 树形结构与默认超参数

root 节点比较特殊，它一次性扩展 3 个子方向，用来在最开始制造足够不同的探索路线。除 root 外，每个节点最多扩展 2 个有效子节点。

v0 默认参数如下：

root_children = 3
max_children_per_non_root_node = 2
max_depth = 4                  # 4 条逻辑边 = 最多 8 个 Rollout Turn
hard_token_limit = 100000
target_good_leaf_count = 12
max_logical_edges = 40          # 预算上限
parallel_width = 按可用 SGLang 并发设置

在上述分支结构下，如果完全展开到 depth 4，最多产生：

3 + 6 + 12 + 24 = 45

条有效逻辑边。而 max_logical_edges = 40 作为预算上限。实际探索也会由 target_good_leaf_count = 12、active nodes 耗尽、或 depth/token 限制终止。

1.3 每一轮如何选择扩展节点

每一轮从所有 active 节点中选择一批节点并发扩展。一个节点只有满足下面条件，才是 active candidate：

node.depth < 4 # root节点的深度是0
node.max_token_total < 100000
node.valid_children < child_limit(node)
node.failed_expansions < 2

其中：

child_limit(root) = 3
child_limit(non_root) = 2

如果某个节点的 max_token_total >= 100000，它不再进入候选集合，但它不是坏节点；它是一个正常结束的 leaf，后续可以进入 root-to-leaf 轨迹选择。

候选节点用下面的 selection score 排序：

Select(n) = Q(n) + alpha * T(n)

这里不再单独设计风险惩罚项。工具错误、无效行为等过程质量已经进入 Q(n) 中的 process 部分；严重失败则直接由 hard prune 处理。

Q(n)：节点质量

Q(n) 由三部分组成：

Q(n) = 0.40 * score_rank(n)
     + 0.30 * best_rank(n)
     + 0.30 * process(n)

score_rank(n) 是节点自身 score 在当前树所有有效节点中的百分位排名，范围是 [0, 1]。对于 maximize task，score 越大排名越高；对于 minimize task，先取反再排名。

best_rank(n) 衡量这条路径曾经达到过的最好结果。具体来说，对每个节点，都计算从 root 到该节点路径上的最高 score，记为 path_best_score(n)；然后把所有有效节点的 path_best_score 做百分位排名，得到 best_rank(n)。这个指标很重要：即使当前节点 regressed，只要它所在路径曾经到达过一个高点，就说明这条路径可能仍然有恢复和继续探索的价值。

process(n) 是从 root 到当前节点路径上所有有效逻辑边的 soft verifier score 平均值。它表示这条路径的过程质量，而不是最终结果质量。

T(n)：短上下文奖励

token 压力使用节点所在路径当前 OpenCode session 的上下文长度，记为：

tok(n) = node.max_token_total

把所有 active 节点的 tok(n) 按越短越好的方向做百分位排名：

T(n) = percentile_rank(tok(n), active_token_counts, direction=minimize)
alpha = 0.50

最短 active 节点得到接近 1 的奖励，最长节点接近 0，并列使用 mid-rank。Q(n) 理论范围为 [0, 1]，因此默认取其完整波动范围的一半 alpha=0.50。如果 tok(n) >= 100000，节点仍直接停止扩展。

1.4 如何扩展一个被选中的节点

扩展节点时，从该节点 fork 一个新的执行分支。这个分支从父节点的代码状态、共享知识状态和 OpenCode session 状态继续运行。

Teacher 在该分支上连续执行两个 Rollout Turn。每个 Rollout Turn 都以一次 coral eval -m 作为结束边界。Rollout 的执行方式与 Coral 中 Agent 的工作方式一致：Teacher 自主读取代码和共享知识，修改代码，运行本地测试，必要时读写 notes 或 skills，最后提交 coral eval -m。

如果两次 Rollout Turn 都成功拿到数值 score，则这条逻辑边有效，并用两次中的最大 score 生成子节点。如果任意一次没有拿到数值 score，则这条逻辑边失败。

1.5 Hard prune：什么时候剪掉一条边

v0 的 hard prune 只保留两个标准：

1. 任意一次 coral eval -m 没有返回数值 score
2. 该逻辑边整体工具错误率 > 30%

第一条覆盖所有 eval 失败情况，包括超时、代码错误、Nothing to commit、grader 崩溃、评测无结果等。只要最终没有数值 score，就不进入树。

第二条用于过滤工具调用明显不干净的轨迹。工具错误率定义为：

tool_error_rate = failed_tool_calls / total_tool_calls

如果 tool_error_rate > 0.30，这条逻辑边直接剪掉。

失败边不会生成子节点，只会使父节点的 failed_expansions 增加。一个节点如果已经产生 2 次失败扩展，就不再继续从该节点扩展。这里的含义不是“树上挂了两个 invalid child”，而是“这个父状态已经被尝试过两次都没有产生可用子分支，继续消耗预算不划算”。

1.6 第一层 fallback 和第二层豁免

早期剪枝会显著影响最终 leaf 数量，因此 root 的第一层扩展使用一次 fallback。

对 root 的每一个子方向，先尝试生成一条逻辑边。如果这条逻辑边通过 hard prune，则正常生成第一层子节点。如果失败，则从 root 的同一状态重新 fork，再尝试一次完整的两-Rollout-Turn 逻辑边。

第二次尝试如果成功，则生成子节点；如果失败了也没关系，仍然保留该子节点。

然后是第二层，这一层默认不做剪枝，享受豁免权，即便有问题也没关系

其他层照原样做剪枝

1.7 Soft verifier score

通过 hard prune 的逻辑边会得到一个 soft verifier score。它用于计算后续节点选择中的 process(n)，也会作为最终 root-to-leaf 轨迹选择的参考信号。

v0 定义为：

soft(edge) = 0.30 * outcome
           + 0.20 * cleanliness
           + 0.20 * knowledge
           + 0.30 * regression_stability

outcome

outcome 判断这条逻辑边中两次 Rollout Turn 的最好 score 是否超过父节点 score：

edge_best_score = max(score_rollout_1, score_rollout_2)

然后：

outcome = 1.0   if edge_best_score improves over parent score
outcome = 0.7   otherwise

这里不把 regressed 直接打成很低分，因为一条路径即使当前没有提升，也可能仍然有有效诊断或后续恢复潜力。

注意！这里的父节点 parent score 也是取父节点里面两次 rollout turn 的最大值

cleanliness

cleanliness 只看工具错误率。只要有 tool error 就扣分，错误率越高扣得越多；到 30% 时已经接近 hard prune。

cleanliness = 1.0                         if tool_error_rate == 0
cleanliness = 0.8 - 0.5 * (tool_error_rate / 0.30)

然后裁剪到 [0.3, 1.0]：

cleanliness = max(0.3, cleanliness)

如果 tool_error_rate > 0.30，这条边已经被 hard prune，不会进入 soft score。

knowledge

knowledge 只看两个信号：这条逻辑边是否 improved，以及两次 Rollout Turn 中是否发生过共享知识读取或写入。

knowledge = 1.0   if improved and has_knowledge_action
knowledge = 0.8   if improved and not has_knowledge_action
knowledge = 0.6   if not improved and has_knowledge_action
knowledge = 0.4   if not improved and not has_knowledge_action

has_knowledge_action 表示两次 Rollout Turn 中都读取或写入了 notes / skills / attempts / roles 等共享知识文件。（可以只读也可以只写，注意这里读的方式可能通过coral cli提供的bash命令进行）

1.8 子节点如何进入后续探索

通过 hard prune 的逻辑边会生成一个子节点。子节点的 score 是两次 Rollout Turn 中的最大 score；子节点的 OpenCode session 状态是第二次 Rollout Turn 结束后的状态；后续如果继续从该节点扩展，就从这个最终状态 fork。

生成子节点后立即判断它是否还能继续探索：

if child.max_token_total >= 100000:
    child becomes a normal leaf
elif child.depth >= 4:
    child becomes a normal leaf
else:
    child enters active candidate set

正常 leaf 不是“好数据”的同义词，只表示它是一条完整且没有 hard failure 的候选路径。最终是否进入训练集，要等 root-to-leaf 轨迹选择阶段再判断。

1.9 一棵 root 树什么时候停止

对单个 root snapshot，探索满足任一条件即停止：

1. good_leaf_count >= 12
2. total_valid_logical_edges > 40
3. active candidate nodes is empty

good_leaf_count 指正常结束的 leaf 数量。正常结束包括：

1. token 达到 100K
2. depth 达到 4
3. 节点没有继续扩展空间，但路径本身有效

考虑到当前分支结构满展开只有 45 条有效逻辑边。实际更重要的停止条件是获得 12 个正常 leaf，或者 active candidate nodes 被耗尽。

1.10 完整流程总结

对一个 Student snapshot，v0 MCTS 执行如下：

1. 将 Student snapshot 作为 root。root 继承代码状态和共享知识库状态，
   但不继承 Student 的 OpenCode 历史上下文。

2. 从 root 启动多个并行的 Teacher fresh OpenCode session。root 第一层
   一次性扩展 3 个方向，每个方向都是一条逻辑边。

3. 每条逻辑边由连续 2 个 Rollout Turn 组成。两个 Rollout Turn 共享
   同一个 fork 出来的 OpenCode session；每个 Rollout Turn 都以一次
   coral eval -m 为结束边界。

4. 对每条逻辑边，子节点 score 取两次 Rollout Turn 中的最大 score；
   Step Turn 数取两次总和；工具错误率按两次整体统计；token 长度取
   第二次 Rollout Turn 结束后的 session 上下文长度。

5. 第一层使用 fallback：root 的每个方向先尝试一次；如果失败，则从
   root 同一状态重新 fork 再尝试一次。第二次无论是否失败，都保留
   该第一层方向，避免早期剪枝导致探索路线过少。

6. 第二层不做 hard prune，享受豁免权。即使该层逻辑边出现 eval 问题
   或工具错误问题，也继续保留该方向。第三层及以后恢复正常 hard prune。

7. 第三层及以后，逻辑边满足任一条件则剪掉：
   - 任意一次 coral eval -m 没有返回数值 score；
   - 整条逻辑边工具错误率 > 30%。

8. 对通过保留规则的逻辑边计算 soft verifier score：

   soft(edge) = 0.30 * outcome
              + 0.20 * cleanliness
              + 0.20 * knowledge
              + 0.30 * regression_stability

   其中 outcome 看两次 Rollout Turn 的最大 score 是否超过父节点 score；
   cleanliness 只由工具错误率决定；knowledge 要求两个 Rollout Turn
   都发生过共享知识读取或写入；regression_stability 为
   `1 - regressed_rate`。

9. 生成子节点后，如果 child.max_token_total >= 100000，或 child.depth >= 4，
   则该节点成为正常 leaf；否则进入 active candidate set。

10. 对所有 active candidate nodes 计算：

    Select(n) = Q(n) + alpha * T(n)

    其中：

    Q(n) = 0.40 * score_rank(n)
         + 0.30 * best_rank(n)
         + 0.30 * process(n)

    T(n) = active 节点中 session token 长度的反向百分位排名
    alpha = 0.50

11. 每轮选择 Select 分数最高的一批节点并发扩展。扩展时从该节点 fork
    代码状态、共享知识状态和 OpenCode session 状态，再执行一条新的
    两-Rollout-Turn 逻辑边。

12. 对单个 root snapshot，满足任一条件即停止探索：
    - good_leaf_count >= 12；
    - total_valid_logical_edges > 40；
    - active candidate nodes is empty。

13. 输出该 root 下所有有效 root-to-leaf 路径，交给最终轨迹选择模块。

2. Snapshot 选择算法

本节确定从 Student Coral 运行中如何选择 snapshot 作为 MCTS root。目标不是只选择最高分状态，而是覆盖 Student 真实优化过程中的前期、中期和后期状态，并且更偏向中期。中期状态通常已经积累了一定 attempts / notes / skills，但仍然保留较大的可改进空间，适合 Teacher 展示如何利用共享知识继续推进。

2.1 候选 snapshot 收集

首先把某个 task 下所有 snapshot 集中起来。每个 snapshot 至少包含：

code/
shared/
metadata.json

候选集的第一步过滤只看 metadata.json 是否包含 eval_ok 字段：

keep snapshot if "eval_ok" in metadata
drop snapshot if "eval_ok" not in metadata

这里不要求 eval_ok == true。eval_ok=false 的 snapshot 也先保留，因为它已经完成了评测回写，只是本次 attempt 没有得到正常数值分数。这类 snapshot 参与前期 / 中期 / 后期的阶段分布估计，但最终不会被选为 MCTS root。

没有 eval_ok 字段的 snapshot 通常表示它还处在 pending 状态，grader 尚未完成回写。这类 snapshot 不进入候选池，因为其 attempt 状态不完整。

2.2 读取 snapshot 的 score 和时间位次

对每个保留下来的 snapshot，先从 metadata.json 中读取：

commit_hash
eval_count
agent_id
eval_ok

然后进入该 snapshot 的：

shared/attempts/

找到文件名或内容对应 commit_hash 的 attempt JSON，并读取其中的：

score
status
feedback

这里的 score 是该 snapshot 当前提交对应的原始分数。对于 eval_ok=false 的 snapshot，score 可能不存在或为 null；这种情况不丢弃 snapshot，但需要额外定义一个仅用于阶段划分的分数：

score_for_stage(snapshot)
  = score                         if score is numeric
  = nearest previous numeric score if score is missing/null

如果某个 failed snapshot 之前没有任何有效数值 score，则使用之后最近的有效 score。（这里的参数细节由你决定）注意，eval_ok=false 的 snapshot 只用于帮助估计 Student run 的时间阶段，不进入最终 root 列表。

还需要读取 snapshot 的储存位次。位次直接来自目录名中的全局 eval 序号，例如：

eval-000003-agent-3-e248a487ce3d/

表示这是本次 Student Coral run 中保存下来的第 3 个 snapshot，来源 agent 是 agent-3。这里的 000003 是所有 Agent 合并后的全局保存顺序，不是 agent-3 自己的第三次提交。

因此，每个候选 snapshot 至少得到：

global_index
agent_id
commit_hash
eval_ok
score
score_for_stage

后续阶段划分只使用按 global_index 排序后的 score_for_stage 序列。

2.3 平滑得分序列

把候选 snapshot 按 global_index 从小到大排序，得到序列：

(x_1, x_2, ..., x_N)

其中：

s_i = score_for_stage(x_i)

为了降低单次 eval 波动对阶段划分的影响，先对得分序列做移动平均平滑。v0 使用窗口大小：

smooth_window = 5

得到平滑后的序列：

smooth_s_i = moving_average(s_i, window=5)

如果 task 是 minimize 方向，先把 score 转成统一的 maximize 方向：

oriented_score = raw_score      # maximize
oriented_score = -raw_score     # minimize

后续所有阶段划分都使用 oriented score。

2.4 前期 / 中期 / 后期划分

定义初始水平 S0 和最终水平 S_inf：

S0    = 前 5% snapshot 的 smooth score 均值
S_inf = 后 20% snapshot 的 smooth score 均值

然后对每个 snapshot 计算累计增益比例：

c_i = (smooth_s_i - S0) / (S_inf - S0)

为了避免异常值导致阶段越界，c_i 裁剪到合理范围：

c_i = clip(c_i, 0, 1)

如果 S_inf <= S0，说明 Student run 没有形成明显上升趋势。此时不再使用累计增益比例，而是退化为按时间位次划分：

前期：前 10%
中期：中间 40%
后期：后 50%

正常情况下，按累计增益比例划分：

early  if c_i < 0.5
middle if 0.5 <= c_i < 0.9
late   if c_i >= 0.9

这里的含义是：前期表示 Student 还没有完成主要提升；中期表示已经跨过一半累计收益但尚未接近最终平台；后期表示接近本次 Student run 的最终水平。

2.5 名额分配与阶段内取点

每个 task 默认选择 30 个 snapshot 作为 root：

num_roots_per_task = 30

阶段名额采用 1 : 3 : 2 的比例：

early_quota  = 5
middle_quota = 15
late_quota   = 10

各阶段内部不按 score 排序选最高分，而是随机取点。也就是说，在 early / middle / late 各自的 snapshot 列表中，先过滤出 eval_ok=true 的 snapshot，再按照 global_index 排序，然后均匀选取对应 quota 个点。

这样做的原因是：snapshot 选择的目标是覆盖状态分布，而不是在 root 阶段提前做 reward maximization。真正的高质量行为由后续 Teacher MCTS 产生，snapshot 这里只负责提供多样、真实、on-policy 的起点。

如果某个阶段中 eval_ok=true 的 snapshot 数量不足，则该阶段全部选入，不足名额交给其他阶段补齐。补齐时同样只从 eval_ok=true 的 snapshot 中选择。补齐顺序为：

middle -> late -> early

也就是说，中期始终是优先补齐对象；如果中期也不足，再补后期；最后才补前期。补齐时仍然按对应阶段内的时间等间隔策略选点。

2.6 输出

假设我们的输入是一个文件路径 all_snapshots/；其中包含我们所收集的多个 snapshot，例如eval-000001-agent-1-2f5815ca427c/, eval-000002-agent-2-9665f8a2424f/等等。那么输出只需要在输出文件路径下，简单的将所选择的snapshot文件夹复制进入即可。

同时为每个snapshot的metadata.json添加这些选择过程中的元信息：

score
stage: early | middle | late
selection_reason

其中 selection_reason 记录它是阶段 quota 内选中的，还是由其他阶段不足后补齐选中的。后续 MCTS 不直接使用这些字段进行搜索，但最终分析数据覆盖性时需要保留它们。

最终 root 列表中的每个 snapshot 都必须满足：

eval_ok == true

3. Root-to-Leaf 轨迹选择算法

MCTS 探索结束后，每个 root snapshot 会得到一棵探索树。训练数据选择的基本单位不是单条边，也不是某一次单独的 coral eval -m，而是一条完整的 root-to-leaf 轨迹。这里的 root-to-leaf 轨迹由若干逻辑节点和逻辑边组成；每条逻辑边包含两个 Rollout Turn，每个逻辑节点的 score 是对应逻辑边中两次 Rollout Turn 的最大 score。

本阶段的目标是从该 root 的所有候选 root-to-leaf 轨迹中，选出最适合作为 SFT 数据来源的 Top-6 条路径。v0 不再额外设置复杂门槛，也不再引入 LLM judge；只使用 MCTS 阶段已经计算好的过程指标和 score 指标。

3.1 候选轨迹集合

候选集合由该 root 下所有正常结束的 root-to-leaf 轨迹组成。正常结束包括：

1. token 达到 100K
2. depth 达到 4
3. 节点没有继续扩展空间，但路径本身有效

一条轨迹只有在四个最终指标都可以计算时，才进入排序集合。也就是说，路径上的逻辑节点需要有可用 score，路径上的逻辑边需要有可用 cleanliness 和 knowledge。如果某条路径因为早期豁免或异常状态导致这些指标无法计算，则不参与最终 Top-6 排序。

3.2 四个轨迹指标

对每条候选轨迹 p，计算四个指标。

第一，平均 cleanliness：

avg_cleanliness(p) = mean(cleanliness(e) for e in p.edges)

这里的 cleanliness(e) 是第 1.7 节中定义的逻辑边 cleanliness，只由该逻辑边的整体工具错误率决定。

第二，平均 knowledge：

avg_knowledge(p) = mean(knowledge(e) for e in p.edges)

这里的 knowledge(e) 是第 1.7 节中定义的逻辑边 knowledge。注意，一条逻辑边由两个 Rollout Turn 组成，只有两个 Rollout Turn 都发生过共享知识读取或写入时，才认为该边有 knowledge 行为。

第三，平均节点得分的百分位排名。先计算该轨迹上所有逻辑节点的平均得分：

avg_score(p) = mean(score(v) for v in p.nodes)

然后在同一个 root 下所有候选轨迹的 avg_score 中做百分位排名：

avg_score_rank(p) = percentile_rank(avg_score(p))

对于 maximize task，score 越高排名越高；对于 minimize task，先转换成统一的 oriented score 后再排名。

第四，最大节点得分的百分位排名。先计算该轨迹上所有逻辑节点的最大得分：

max_score(p) = max(score(v) for v in p.nodes)

然后在同一个 root 下所有候选轨迹的 max_score 中做百分位排名：

max_score_rank(p) = percentile_rank(max_score(p))

avg_score_rank 衡量整条路径的稳定质量，max_score_rank 衡量这条路径是否曾经到达过高分状态。两者都保留，因为有些轨迹整体稳定但没有明显突破，有些轨迹中间波动较大但曾经找到很强的解。

3.3 PathScore

最终轨迹分数定义为：

PathScore(p)
  = 0.35 * max_score_rank(p)
  + 0.25 * avg_score_rank(p)
  + 0.20 * avg_cleanliness(p)
  + 0.20 * avg_knowledge(p)

这里 max_score_rank 权重最高，因为我们希望训练数据中包含真正到达过高质量解的路径；avg_score_rank 次之，用来避免只因为偶然高点而选择整体较差的轨迹；avg_cleanliness 和 avg_knowledge 各占 0.20，用来保留工具调用干净和共享知识行为充分的路径。

最终选择阶段不再额外加入 token penalty。token 长度已经在 MCTS 阶段通过短上下文奖励 T(n) 和 hard_token_limit = 100000 控制；最终再次惩罚可能会过度偏向短路径。

3.4 Top-6 选择

对同一个 root 下的所有候选 root-to-leaf 轨迹，按 PathScore 从高到低排序，直接选择前 6 条：

SelectedPaths(root) = top_6_by_PathScore(candidate_paths(root))

如果候选轨迹不足 6 条，则全部保留。

每条被选中的轨迹需要保留如下原数据：

avg_cleanliness
avg_knowledge
avg_score
avg_score_rank
max_score
max_score_rank
PathScore

这些字段用于后续导出 OpenCode SFT 样本、做数据审计，以及分析不同 root / task / stage 的数据覆盖情况。