MCPP: Budget-Deadline Constrained Resource Allocation for Agent Workflows

To address the resource allocation problem for agent workflows under dual constraints of budget and deadline, this paper proposes the Monte Carlo Combinatorial Planning (MCPP) method. This method estimates the constraint satisfaction probability by simulating workflow execution and replans after observing results, significantly improving the constraint satisfaction rate on the CodeFlow and ProofFlow benchmarks. This article will discuss MCPP's background, methodology, experiments, and applications.

Agent systems solve complex requests through orchestrating multiple specialized models/tools in a workflow, but practical deployment faces three constraints: budget (model call cost), deadline (user response expectation), and success probability (resource waste and user experience). Existing studies mostly focus on average efficiency optimization (e.g., performance-cost-latency Pareto frontier), but the actual demand is whether the current request can be successfully completed under specific constraints. This gap has spurred the research on MCPP.

MCPP models agent workflow execution as a finite-horizon stochastic process:

• Workflow Structure: Directed Acyclic Graph (DAG) represents subtasks and dependencies, supporting parallel execution of independent subtasks;
• State Space: Includes remaining budget, remaining time, completed/failed/ongoing subtasks, etc.;
• Action Space: Model allocation, parallelism selection, execution order priority;
• Objective Function: Maximize the probability of successful completion of the workflow under budget and deadline constraints (all-or-nothing property, non-linear).

The core mechanism of MCPP includes three parts:

1. Monte Carlo Estimation: Estimate constraint satisfaction probability by fast forward simulation of candidate allocation strategies;
2. Combinatorial Optimization Search: Greedy initialization + local improvement + early stopping mechanism to search for the optimal allocation strategy;
3. Closed-Loop Replanning: Update the state after subtask completion, replan subsequent steps, and adaptively adjust resource allocation (e.g., choose cheaper models when resources are tight, invest in difficult subtasks when progress is smooth).

The research team evaluated MCPP on two benchmarks:

• CodeFlow: Code generation workflow (requirement understanding → code generation → testing → execution → repair → verification);
• ProofFlow: Mathematical proof workflow (problem analysis → strategy selection → lemma generation → step verification → backtracking). Results show that MCPP's constraint satisfaction probability under the same constraints is significantly higher than baselines (fixed strategy, greedy heuristic, static planning, etc.), with higher resource utilization efficiency, and the closed-loop mechanism can better handle unexpected situations during execution.

The implications of MCPP for agent system deployment include:

• SLA-Driven Design: Aligns with the service level agreement (SLA) requirements of commercial applications;
• Model Routing Strategy: Optimal model allocation based on global success probability;
• Dynamic Scaling: Adjust the number of parallel samples according to load and constraints;
• Failure Recovery: Re-optimize subsequent plans after subtask failure.

MCPP has the following limitations:

1. Simulation Cost: Monte Carlo simulation has high computational cost;
2. Model Assumptions: Relies on known estimates of subtask success rates and generation lengths;
3. Non-Stationarity: Does not consider dynamic environments (e.g., model API performance fluctuations);
4. Multi-Objective Trade-off: Does not handle complex trade-offs between multiple constraints (e.g., quality, security). Future directions include developing efficient estimation methods, handling estimation uncertainty, adapting to dynamic environments, and supporting multi-objective constraints.

MCPP provides a principled solution for resource allocation in agent workflows. By formalizing the problem as finite-horizon stochastic online allocation and using Monte Carlo simulation to optimize constraint satisfaction probability, this method reminds us that agent system optimization should align with practical deployment needs (constraint satisfaction takes priority over average efficiency), providing a valuable tool for the practical deployment of agent systems.