💬 NLP

On Time, Within Budget: Constraint-Driven Online Resource Allocation for Agentic Workflows

本文介绍蒙特卡洛投资组合规划（MCPP），这是一种轻量级闭环规划器，它通过基于模拟结果动态分配模型和并行样本，来优化在明确的预算和截止时间约束下完成代理工作流的概率。

原作者： Xinglin Wang, Zishen Liu, Shaoxiong Feng, Peiwen Yuan, Yiwei Li, Jiayi Shi, Yueqi Zhang, Chuyi Tan, Ji Zhang, Boyuan Pan, Yao Hu, Kan Li

发布于 2026-05-08

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Xinglin Wang, Zishen Liu, Shaoxiong Feng, Peiwen Yuan, Yiwei Li, Jiayi Shi, Yueqi Zhang, Chuyi Tan, Ji Zhang, Boyuan Pan, Yao Hu, Kan Li

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一名建筑工队的经理，负责建造一栋复杂的房屋（即智能体工作流）。你有一条严格的规定：房屋必须在周五下午 5 点前完工（即截止日期），且花费不得超过 10,000 美元（即预算）。

你的工队由不同的专家（即模型）组成：有些速度快但昂贵，有些速度慢但便宜，还有些表现时好时坏。施工计划是一张地图，标明了哪些房间必须比其他房间先建造（即依赖关系）。

旧方法：“优化平均值”

此前，研究人员试图基于平均值为每项工作找到“完美”的专家。他们会问：“哪名工人在速度、成本和质量方面平均表现最佳？”

问题所在： 这就像仅凭简历雇佣工队，然后派他们去现场，却未制定应对下雨或工人离职等突发状况的计划。即使你雇佣了“平均表现最佳”的工人，也可能因为未考虑到这项工作特有的混乱局面，而在周三前耗尽资金，或错过周五的截止日期。

新方法：“约束驱动的在线分配”

本文提出了一种名为**MCPP（蒙特卡洛投资组合规划）**的新方法。MCPP 不再仅仅挑选“最佳”工人，而是扮演一位超级聪明、实时运作的项目经理，根据实际发生的情况不断重新规划。

以下是 MCPP 的工作原理，采用简单的类比说明：

1. “假设”模拟器（蒙特卡洛）

在做出决策之前，MCPP 不只是猜测。它会在脑海中运行数千次剩余施工项目的模拟电影。

情景 A： “如果我雇佣昂贵但快速的工人负责厨房，我是否还有足够的资金按时完工屋顶？”
情景 B： “如果我雇佣便宜但缓慢的工人负责厨房，我们是否会错过截止日期？”

它反复模拟这些结果，以找出哪条路径最有可能在 10,000 美元预算和周五截止日期的限制下完成整栋房屋。

2. 策略“投资组合”

MCPP 不只关注一种做事方式。它准备了一个包含不同策略的投资组合，随时待命：

保守策略： “使用便宜的工人，并祈祷一切顺利。”
激进策略： “现在投入大笔资金以确保速度。”
混合策略： “在困难部分使用快速工人，在简单部分使用便宜工人。”

它将所有可能的策略组合与剩余的时间和资金进行测试。

3. “重新规划”循环（闭环）

这是最重要的部分。MCPP 不会在开始时制定计划后就固守不变。

步骤 1： 基于模拟结果，立即选择当前最佳行动。
步骤 2： 在现实世界中执行该行动。
步骤 3： 观察结果。工人成功了吗？耗时是否超出预期？成本是否更高？
步骤 4： 立即根据新现实重新运行模拟，并为下一步选择新的最佳行动。

这就像 GPS 导航，它不会只给你一次路线，而是在你遇到交通堵塞或改道时重新计算整条路径，确保你仍能带着剩余的资金在下午 5 点前抵达。

为何这很重要

本文在两类“建筑项目”上测试了该方法：

CodeFlow（代码流）： 编写计算机代码，其中某一步骤依赖于前一步骤。
ProofFlow（证明流）： 解决复杂的数学证明，其中步骤必须遵循逻辑链条。

结果：
当预算和时间紧张（即“硬”约束）时，MCPP 比旧方法更能成功完成任务。

旧方法往往因为无法适应具体情况而耗尽资金或时间。
MCPP 通过为“瓶颈”任务（即房屋中最困难的部分）节省资金，并在简单部分减少开支，成功应对了严格的约束。

核心结论

本文认为，在现实世界中，我们需要的不仅仅是一个“通常高效”的智能体。我们需要一个能保证特定结果的智能体：“你能在周五前以低于 100 美元的成本完成这项具体工作吗？”

MCPP 通过不断模拟未来、适应现实，并在过程的每一步在速度、成本和风险之间做出明智的权衡，比之前的方法更频繁地回答“是”。它将僵化的计划转化为灵活、有生命力的策略，从而在现实世界执行的混乱中生存下来。

技术摘要：面向智能体工作流的约束驱动在线资源分配

问题定义

本文解决了智能体系统部署中的一个关键缺口：从优化平均性能 - 成本 - 延迟前沿，转向满足严格的、特定实例的约束。虽然近期工作通过优化性能、成本和延迟之间的权衡来提高智能体效率，但现实世界的部署通常要求特定工作流必须在严格预算（ $B$ ）和固定截止时间（ $D$ ）内完成。

核心问题是约束驱动的在线资源分配。给定一个具有依赖结构的工作流（一个有向无环图，其中节点是子任务，边表示依赖关系），执行器必须动态地为当前可执行的子任务分配资源（基础模型的选择和并行采样宽度）。目标不是最小化平均成本或延迟，而是最大化整个工作流成功完成的概率，使得总成本 $\le B$ 且总时间 $\le D$ 。

这被表述为一个有限时域随机在线分配问题。状态由已完成的子任务集合、剩余预算和剩余时间定义。挑战在于可能执行路径的组合爆炸、随机结果（子任务的成功/失败）以及工作流中资源消耗的相互依赖性。静态分配模型或采样策略是不够的，因为最优决策取决于不断演变的状态、剩余约束以及观测到的随机事件。

方法论：蒙特卡洛组合规划（MCPP）

为了解决这一难以处理的优化问题，作者提出了蒙特卡洛组合规划（MCPP），这是一种轻量级的闭环规划器。

1. 问题表述

工作流被建模为 $I = (G, M, \Phi, B, D)$ ，其中 $G$ 是子任务图， $M$ 是可用的模型集合， $\Phi$ 包含每个子任务 - 模型对的估计成功概率（ $p_{v,m}$ ）和预期生成长度（ $\ell_{v,m}$ ）。
目标是找到策略 $\pi$ 以最大化：
$J(\pi) = \Pr_{\pi} (T_{solve} \le D, C_{\pi} \le B)$
精确的动态规划在理论上是可行的，但由于状态空间（已完成子任务的组合）和动作空间（所有就绪节点的模型和采样宽度选择）呈指数级增长，计算上不可行。

2. MCPP 算法

MCPP 使用单步组合展开备份来近似最优决策规则：

候选动作集：在每个状态下，规划器构建一组候选动作 $\tilde{A}(s)$ 。该集合包含针对就绪节点的具体分配，并通过简单延续策略的组合 $\Pi_0$ 进行增强。组合中的每个策略都是一个“重试- $k$ "策略，它将特定的模型 $m$ 和采样宽度 $k$ 分配给所有未来的可执行子任务。
蒙特卡洛估计：对于每个候选当前动作 $a$ ，规划器通过模拟工作流执行来估计其价值。它应用 $a$ ，采样随机结果（哪些子任务成功），更新状态，然后遵循组合中的每个延续策略 $\mu \in \Pi_0$ ，直到工作流结束或违反约束。
选择：动作 $a$ 的价值被估计为组合中所有延续策略的最大成功概率： $\hat{Q}_{\Pi_0}(s, a) = \max_{\mu \in \Pi_0} \hat{Q}_{\mu}(s, a)$ 。选择估计价值最高的动作进行执行。
闭环重规划：在执行选定动作并观察实际结果后，规划器更新状态（剩余预算、时间和已完成的子任务）并重新规划。这使得系统能够实时适应随机失败和资源消耗。

3. 理论保证

本文提供了“安全改进”分析。它证明，在有限的蒙特卡洛采样误差、候选集近似误差以及成功率/长度估计误差范围内，MCPP 策略产生的约束完成概率至少与组合中最佳基础策略一样高。这确保了规划器的表现永远不会差于简单的静态策略（例如始终使用相同的模型和采样宽度），同时通过前向展望提供显著增益的潜力。

主要贡献

问题表述：作者引入了约束驱动的在线资源分配场景，将目标从优化平均效率前沿转变为最大化满足特定工作流实例的严格预算和截止时间约束的概率。
算法提出：他们提出了MCPP，这是一种闭环规划器，通过模拟展开直接估计约束完成概率，并根据观测结果进行重规划。它通过使用简单延续策略的组合来近似未来值，从而避免了穷尽的动态规划。
实证验证：该方法在两个依赖结构基准上进行了评估：CodeFlow（代码生成和验证）和ProofFlow（形式推理和证明生成）。
鲁棒性分析：本文证明，即使输入估计（成功率和生成长度）存在噪声（现实部署中的常见情况），MCPP 仍然有效。

实验结果

实验在 CodeFlow 和 ProofFlow 基准上进行，使用了各种预算（ $B$ ）和截止时间（ $D$ ）约束。

性能：MCPP 始终优于强大的基线，包括Uniform（在子任务间静态分配预算）和Retry（无下游规划的在线局部重试）。
严格约束：在严格约束下（例如 $B = \$ 0.05$），改进最为显著。一旦截止时间变得适度可行，MCPP 就能迅速实现高成功率，而基线则保持在较低水平。
动作多样性：消融研究表明，随着模型组合（使用多种模型）和更丰富的展开宽度组合（变化采样宽度）的增大，性能得到提升。这突出了为特定节点和状态选择正确模型和计算强度的重要性，而不是使用单一的全局策略。
鲁棒性：在成功率估计存在噪声（高斯噪声， $\sigma=0.3$ ）的情况下，MCPP 仅下降了约 6 个百分点，展示了对不完美配置估计的韧性。
可扩展性：该方法有效地扩展到更大的工作流（更多子任务），保持了相对于基线的优势，特别是在静态分配无法适应中间结果的受限场景中。
效率：在线规划开销适中（标准配置下通常低于 5 秒），使其适用于实时执行。

意义与主张

本文声称其主要意义在于解决了现实世界智能体部署中的特定实例成功条件。虽然以往的工作侧重于改善“性能 - 成本 - 延迟前沿”（平均效率），但这项工作将预算和时间视为定义成功或失败的硬约束。

作者认为，更好的前沿并不自动转化为特定约束下的更优动作策略。MCPP 通过直接优化满足用户特定 $B$ 和 $D$ 要求的概率来弥合这一差距。本文谦逊地声称，MCPP 提供了相对于基础策略的安全改进，并在受限环境中展示了持续的增益，同时并未声称达到全局最优或解决工作流生成的通用问题（这被视为一个独立的上游任务）。该工作被定位为智能体系统执行阶段的实用求解器，假设工作流结构和统计配置已可用。