MCPP：面向智能体工作流的预算-截止时间约束资源分配

针对智能体工作流在预算和截止时间双重约束下的资源分配问题，本文提出蒙特卡洛组合规划（MCPP）方法。该方法通过模拟工作流执行估计约束满足概率，并在观测结果后重新规划，在CodeFlow和ProofFlow基准上显著提升了约束满足率。本文将围绕MCPP的背景、方法、实验及应用展开讨论。

智能体系统通过编排多个专用模型/工具以工作流形式解决复杂请求，但实际部署面临预算（模型调用成本）、截止时间（用户响应期望）、成功概率（资源浪费与用户体验）三重约束。现有研究多关注平均效率优化（如性能-成本-延迟帕累托前沿），但实际需求是当前请求能否在具体约束下成功完成，这一差距催生了MCPP的研究。

MCPP将智能体工作流执行建模为有限时域随机过程：

• 工作流结构：有向无环图（DAG）表示子任务及依赖关系，支持并行执行无依赖子任务；
• 状态空间：包括剩余预算、剩余时间、已完成/失败/进行中子任务等；
• 动作空间：模型分配、并行度选择、执行顺序优先级；
• 目标函数：最大化工作流在预算和截止时间约束下的成功完成概率（全有或全无特性，非线性）。

MCPP的核心机制包括三部分：

1. 蒙特卡洛估计：通过快速前向模拟候选分配策略，估计约束满足概率；
2. 组合优化搜索：贪心初始化+局部改进+早停机制，搜索最优分配策略；
3. 闭环重规划：子任务完成后更新状态，重新规划后续步骤，自适应调整资源分配（如资源紧张时选择更便宜模型，进展顺利时投资困难子任务）。

研究团队在两个基准上评估MCPP：

• CodeFlow：代码生成工作流（需求理解→代码生成→测试→执行→修复→验证）；
• ProofFlow：数学证明工作流（问题分析→策略选择→引理生成→步骤验证→回溯）。 结果显示，MCPP在相同约束下的约束满足概率显著高于基线（固定策略、贪婪启发式、静态规划等），资源利用效率更高，且闭环机制能更好应对执行中的意外情况。

MCPP对智能体系统部署的启示包括：

• SLA驱动设计：契合商业应用的服务等级协议需求；
• 模型路由策略：基于全局成功概率的最优模型分配；
• 动态扩缩容：根据负载和约束调整并行采样数量；
• 失败恢复：子任务失败后重新优化后续计划。

MCPP存在以下局限：

1. 模拟成本：蒙特卡洛模拟计算量大；
2. 模型假设：依赖子任务成功率和生成长度的已知估计；
3. 非平稳性：未考虑动态环境（如模型API性能波动）；
4. 多目标权衡：未处理多约束（如质量、安全性）的复杂权衡。 未来方向包括开发高效估计方法、处理估计不确定性、适应动态环境、支持多目标约束。

MCPP为智能体工作流资源分配提供了principled解决方案，通过将问题形式化为有限时域随机在线分配，采用蒙特卡洛模拟优化约束满足概率。该方法提醒我们，智能体系统优化应与实际部署需求对齐（约束满足优先于平均效率），为智能体系统的实际落地提供了有价值的工具。