Bootstrap Flow-Map Tree 采样实现在线反馈驱动搜索

# 自举流图树采样实现在线反馈驱动搜索 来源：https://arxiv.org/html/2607.02915 Binglin Ji¹，Anindya Sarkar¹¹¹ 脚注 1，Hengchang Lu¹，Jens Sjölund²，Yevgeniy Vorobeychik¹ \{binglin\.j, anindya, yvorobeychik\}@wustl\.edu，¹华盛顿大学计算机科学与工程系，美国 ²乌普萨拉大学信息技术系，瑞典 ###### 摘要 在许多科学与工程领域，在有限采样预算内最大化发现成果需要基于观测的、战略性探索指导。虽然生成模型已实现免训练奖励对齐，但当前方法通常擅长在基础分布的狭窄区域内进行局部搜索。这些方法在偏好未知且仅能通过顺序反馈揭示时难以奏效——这种场景要求广泛探索以发现高回报区域。为此，我们提出 **自举流图树**（Bootstrap Flow-Map Tree，简称 BFMT），一种新颖的计算高效采样框架，专为采样预算约束下的历史感知全局搜索与对齐而设计。BFMT 能够通过单次函数评估从任意树深度构建完整树路径，大幅降低计算开销，同时为顺序采样提供关键的前瞻能力。通过支持动态过渡时间步调度，BFMT 高效分配采样预算，从广泛的全局探索平滑过渡到对探索发现的高回报模式进行精细局部优化。在多种搜索与对齐任务上的广泛实验和消融研究证明，BFMT 显著优于基线方法。 ## 1 引言 在许多科学与工程领域，发现过程从根本上受限于评估成本。这催生了普遍存在的挑战：**在线反馈驱动搜索**。例如，在个性化医疗中，为罕见病发现最优治疗方案需要顺序提出药物并根据患者反馈进行调整。由于这些现实世界的查询依赖于昂贵的湿实验，总体目标是在最少迭代次数内发现最优目标。从发现拯救生命的治疗方案到优化交互式视觉推荐系统，掌握这种预算受限的交互式搜索对于加速现实世界的突破至关重要。应对这一挑战需要一个强大的采样框架，能够在复杂高维空间（如图像）中进行战略性**全局探索**。关键在于，它必须无缝利用顺序反馈，在严格采样预算约束下优化搜索过程。 当前方法从根本上难以胜任这一挑战。例如，uehara2024feedback（https://arxiv.org/html/2607.02915#bib.bib1）依赖于扩散模型的在线 RL 微调，以近似最小化与目标分布的 KL 散度。这种固有的模态追求目标无法捕捉目标分布中多样化的高回报区域。此外，这些方法依赖于在线训练的奖励模型，其早期阶段的偏差可能误导微调过程并降低样本质量。最近的基于顺序蒙特卡洛的推理时缩放方法（singhal2025general，(https://arxiv.org/html/2607.02915#bib.bib2)；skreta2025feynman，(https://arxiv.org/html/2607.02915#bib.bib3)；kim2025test，(https://arxiv.org/html/2607.02915#bib.bib4)）通过在固定生成先验上操作来规避直接模型微调。然而，这些方法表现出严重的权重退化，有效坍缩了提议并抑制了样本多样性（lee2025debiasing，(https://arxiv.org/html/2607.02915#bib.bib5)）。此外，这些方法在每一步重采样时依赖奖励值或梯度；在实践中，这些信号不可获得，必须进行近似，从而向采样器引入系统性偏差并降低样本质量，特别是在奖励模型在线训练且在早期阶段高度有偏时。 为缓解这些问题，引入了基于树的推理时采样器（guo2025training，(https://arxiv.org/html/2607.02915#bib.bib6)；jain2025diffusion，(https://arxiv.org/html/2607.02915#bib.bib7)），它们仅反向传播终端奖励，消除了在每个中间去噪步骤评估奖励的需要。尽管有潜力，现有的基于树的采样器 jain2025diffusion（https://arxiv.org/html/2607.02915#bib.bib7）从根本上受限于节点评估所需的大量函数评估（NFEs），这削弱了它们在以探索为主的任务中的实用性。此外，它们依赖每一步深度的微小均匀过渡，无法实现动态自适应搜索能力。这些低效问题进一步加剧，当前采样器中的探索策略本质上是预算无关的，使它们在资源受限的应用中不切实际。 为克服这些瓶颈，我们引入了一个原则性的采样框架，直接解决以下问题：我们如何推导出一个原则性的、免训练的采样器，使其能够使用数量级更少的 NFEs 实现历史感知、动态、全局的在线反馈驱动搜索，并且在严格的采样预算约束下仍然有效？为此，我们提出了自举流图树（BFMT），一种新颖的采样框架，协同了历史感知树搜索与高效的流图动态。虽然标准树搜索需要计算昂贵的 rollout 来估计中间节点值，BFMT 利用流图将此评估压缩为单次 NFE。尽管流图的确定性 ODE 特性通常阻碍了子节点采样所需的随机 DDPM 式过渡，我们通过部署自举充分统计量方案绕过了这一问题。该机制使得能够**在不产生任何额外 NFE 的情况下构建整条随机树路径**。此外，由于流图允许跨任意时间间隔的状态估计，BFMT 轻松适应非均匀过渡步长。打破僵化的扩散调度解锁了对搜索过程以及探索-利用权衡的动态精细控制。本质上，BFMT 执行平滑的分层搜索：靠近根的早期阶段优先进行广泛的全局探索以发现多样化的模式，而更深层则逐步利用已发现高回报区域的局部邻域——由顺序反馈和贝尔曼备份引导——以最大化整体发现率。最后，我们为 BFMT 增添了一种新颖的预算感知节点选择策略，在资源受限环境中优于标准 UCT。我们在图1（https://arxiv.org/html/2607.02915#S1.F1）中提供了 BFMT 框架的概念性描述。 我们将主要贡献总结如下： **贡献** • **基于流的树采样器**：我们提出了自举流图树，一个用于在线反馈驱动搜索的原则性、基于树的采样框架。 • **单次 NFE 的随机路径构建**：我们公式化了一个自举充分统计量方案，能够仅使用单次 NFE 从确定性 ODE 合成完整的 DDPM 式随机树轨迹。 • **动态分层搜索**：通过利用流图进行非均匀时间过渡，BFMT 解锁了自适应搜索能力，从广泛的全局模式发现无缝过渡到细粒度的局部优化。 • **预算感知节点选择**：我们提出了一种专为资源受限环境设计的自定义预算感知树搜索策略。 • **严格的经验验证**：通过全面的定量和定性消融研究，我们验证了 BFMT 每个组件的有效性。 ## 2 方法论：BFMT 框架 **背景**：有效的在线反馈驱动搜索取决于战略性导航目标景观的探索策略。因此，最优策略必须高效地从目标分布中采样： \[ \pi^{*}(x)=\frac{1}{Z} p_{\theta}^{\text{pre}}(x)\exp(\beta\, r(x)) \tag{1} \] 在此公式中，\(p_{\theta}^{\text{pre}}(x)\) 表示预训练生成先验，\(r(x)\) 代表奖励函数，\(\beta\) 是逆温度参数，\(Z\) 是归一化常数。目标分布可以看作是以下目标的最优策略： \[ \pi^{*}(x):=\arg\max_{\pi} \mathbb{E}_{x\sim\pi(\cdot)}[r(x)]-\frac{1}{\beta} D_{\text{KL}}(\pi\parallel p_{\theta}^{\text{pre}}) \tag{2} \] 高效优化 \(\pi^{*}(x)\) 需要估计时刻 \(t\) 的软值函数，定义为： \[ V_{t}(x_{t}):=\frac{1}{\beta}\log \mathbb{E}_{p_{\theta}(x_{0:t-1}|x_{t})}\left[\exp\left(\beta r(x_{0})\right)\right] \tag{3} \] 通过方程3（https://arxiv.org/html/2607.02915#S2.E3）估计 \(x_{t}\) 的值引入了一个计算瓶颈，因为它需要模拟从 \(x_{t}\) 开始的整个去噪轨迹，消耗大量 NFEs。标准的 Tweedie 式终端估计器不足，因为它们在噪声水平高时存在的显著不准确性严重削弱了准确的值估计。此外，存在一个基本矛盾：虽然 ODE 采样非常高效，但严格搜索需要随机过渡。由于这些随机步长必须无限小以最小化离散化误差，它们需要难以承受的大量过渡步数。 为解决这一冲突，我们旨在获得一个基于 ODE 的流模型，能够单步从 \(x_{0}\sim p(x_{0}|x_{t})\) 采样。从理论上讲，给定 \(x_{t}\)，存在一个 ODE 将先验 \(p_{1}\) 传输到条件后验 \(p_{0|t}(\cdot|x_{t})\)。该流的相关漂移 \(b_{s}(\cdot;x_{t})\) 可以定义为标准流匹配问题 lipman2022flow（https://arxiv.org/html/2607.02915#bib.bib8）的解，**目标为条件后验 \(p_{0|t}(\cdot|x_{t})\) 而非边缘数据分布 \(p_{0}\)**： \[ b_{s}(x;x_{t})=\mathbb{E}\left[\dot{\alpha}_{s} I_{1}+\dot{\beta}_{s} I_{0}\mid I_{s}=x\right],\quad I_{s}=\alpha_{s} I_{1}+\beta_{s} I_{0},\quad I_{1}\sim\mathcal{N}(0,I_{d}),\quad I_{0}\sim p_{0|t}(\cdot|x_{t}) \tag{4} \] 因此，与 \(b_{s}(\cdot;x_{t})\) 相关的概率流满足： \[ \frac{d}{ds}x_{s}=b_{s}(x_{s};x_{t}),\quad x_{1}\sim\mathcal{N}(0,I_{d}) \implies \text{Law}(x_{0})=p_{0|t}(\cdot|x_{t}) \tag{5} \] 这里 \(\alpha_{t},\beta_{t}\) 是依赖于时间的系数，满足 \(\alpha_{0}=\beta_{1}=0\) 和 \(\alpha_{1}=\beta_{0}=1\)。假设高斯先验 \(p_{1}\)，条件漂移 \(b_{s}\) 可以解析推导（holderrieth2025glass，(https://arxiv.org/html/2607.02915#bib.bib9)）。这通过无条件漂移 \(b_{t}\) 的重参数化实现： \[ b_{s}(x_{s};x_{t})=w_{1}x_{s}+w_{2}b_{t^{*}}(S(x_{s},x_{t}))+w_{3}x_{t} \] 其中，\(w_{1},w_{2},\) 和 \(w_{3}\) 是标量权重。\(S\) 是一个线性**充分统计量**，\(t^{*}\) 表示重新参数化的时间参数： \[ S_{s,t}(x_{s},x_{t})=\frac{\alpha_{s}\sigma_{t}^{2}x_{s}+\alpha_{t}\sigma_{s}^{2}x_{t}}{\sigma_{t}^{2}\alpha_{s}^{2}+\alpha_{t}^{2}\sigma_{s}^{2}},\qquad t^{*}(s,t)=g^{-1}\left(\frac{\sigma_{t}^{2}\sigma_{s}^{2}}{\sigma_{t}^{2}\alpha_{s}^{2}+\alpha_{t}^{2}\sigma_{s}^{2}}\right),\quad g(t)=\frac{\sigma_{t}^{2}}{\alpha_{t}^{2}} \tag{6} \] 尽管这种重参数化确保了 \(b_{s}\) 的可访问性，但通过积分 ODE 轨迹从 \(p_{0|t}(\cdot|x_{t})\) 生成后验样本的过程仍然计算密集。一个解决此问题的标准方法是**教师蒸馏**，其中精确分析场 \(b_{s}(x_{s};x_{t})\) 作为蒸馏过程的教师。学生模型的速度 \(\hat{v}\) 使用组合目标进行优化，其中**瞬时损失**直接最小化学生瞬时速度 \(\hat{v}_{s,s}\) 与分析教师场之间的均方误差： \[ \mathcal{L}_{\text{inst}}^{\text{distill}}(\hat{v}):=\int_{0}^{1}\int_{0}^{1}\mathbb{E}\|\hat{v}_{s,s}(x;x_{t})-b_{s}(x;x_{t})\|^{2}\,ds\,dt \tag{7} \] 结合**一致性损失** boffi2025build（https://arxiv.org/html/2607.02915#bib.bib10）\((\mathcal{L}_{\text{cons}}^{\text{distill}})\) 确保学生准确地在不同时间间隔上积分该速度。\(\mathcal{L}_{\text{cons}}^{\text{distill}}(\hat{v})\) 定义如下： \[ \int_{0}^{1}\int_{0}^{u}\mathbb{E}\left\|\hat{v}_{s,u}(I_{s};I_{t}')-\text{sg}\left(b_{u}(\hat{X}_{s,u}(I_{s};I_{t}'));I_{t}'\right)-(u-s)\partial_{u}\hat{v}_{s,u}(I_{s};I_{t}')\right\|^{2}ds\,du \] 这里，\(X_{s,u}(\cdot\,;x_{t}):\mathbb{R}^{d}\to\mathbb{R}^{d}\) 作为方程5（https://arxiv.org/html/2607.02915#S2.E5）中上下文依赖 ODE 的解算子。蒸馏将迭代多步 ODE 压缩为单个摊销映射，**实现了直接从条件后验 \(p_{0|t}(\cdot|x_{t})\) 进行单步计算高效采样**。 **步骤 1：通过流图从 \(x_{t}\) 采样 \(x_{0}\)**  
**步骤 2：自举充分统计量**  
**步骤 3：节点选择机制**  
\[ x_{T} \quad x_{t} \quad x_{j} \quad x_{k} \quad x_{0} \quad x_{0} \quad x_{0} \quad x_{0} \]  
\[ t=T \quad t \quad t \quad 0 \]  
局部树上下文  
\[ x_{t} \quad \varepsilon \]  
流图 \(\hat{v}(\varepsilon;x_{t})\)  
\[ x_{0} \]  
上下文 1 NFE  
\[ p(x_{0}\mid x_{t}) \]  
样本 1  
\[ r^{*}=g(a,b) \]  
通过充分统计量  
2 计算  
\[ x_{r^{*}}=\bar{\alpha}_{r^{*}}x_{0}+\bar{\sigma}_{r^{*}}\varepsilon_{1} \]