Discovery and Reinforcement of Tool-Integrated Reasoning Chains via Rollout Trees

Idea

DART 在 RL 训练期间对现有 long CoT 轨迹构建 rollout tree，在高不确定且适合工具使用的位置插入提示并分叉，探索 Python 调用能否改善解答。随后用树中后代答案的成功率估计子轨迹价值，把有效工具分支的收益定位到中间过程；测试时恢复普通单路径生成。

Research Problem

已有 reasoning model 的工具使用与 long CoT 行为可能在不同 post-training 数据中学得，单靠工具提示或终局奖励很少触发 thinking 内部调用。新收集的短 CoT 工具轨迹做 SFT 成本高，也可能干扰原有长推理能力。主要缺口是如何发现并强化已有模型分布中低概率但有用的 tool-integrated continuations。

Insight

相同 reasoning prefix 后的自然语言与工具分支提供局部对照：若工具分支更常得到正确答案，便可用终局可验证结果为该段过程赋予相对优势，而不需要人工标注每个步骤。entropy 确定值得探索的分叉点，hint likelihood 再判断工具衔接是否自然，两者共同提高探索有效率。

Method

1. 每题先采样 M 条原始轨迹形成树，在 clause 结束位置计算 vocabulary entropy，取最高的 K 个候选并排除末尾 20%；从候选位置与工具 hints 的组合中按条件概率采样，避免反复选择同一组合。
2. 在选定 prefix 后加入以 Python code block 开头结束的 hint，继续生成代码，交给 sandbox 执行，将反馈写入 context 后完成推理；每轮产生 M 个分支，扩展 N 轮得到 M×(N+1) 个叶子。
3. 以答案 verifier 给叶子二值 reward，非叶节点取后代叶子的均值。节点 advantage 为相对 root 的 global advantage 加相对 parent 的 local advantage，同一子轨迹的 tokens 共享该值，用无 KL 的 REINFORCE 型目标更新并 mask interpreter feedback。
4. 在筛选出的 2,795 道困难 DAPO 数学题上训练 Qwen3 reasoning models，比较相同 backbone/data 下的 direct RL、SFT→RL 与 rejection sampling。推理不构建树、不强制 hint，仅与 Python interpreter 交互，评估 AIME 与 GPQA-Diamond。