Technical Summary: Constraint-Driven Online Resource Allocation for Agentic Workflows

Problem Definition

The paper addresses a critical gap in the deployment of agentic systems: the transition from optimizing average performance–cost–latency frontiers to satisfying hard, instance-specific constraints. While recent work improves agent efficiency by optimizing the trade-off between performance, cost, and latency, real-world deployments often require that a specific workflow completes within a strict budget ($B$) and a fixed deadline ($D$).

The core problem is constraint-driven online resource allocation. Given a dependency-structured workflow (a Directed Acyclic Graph where nodes are subtasks and edges represent dependencies), an executor must dynamically allocate resources (choice of base models and parallel sampling widths) to currently executable subtasks. The objective is not to minimize average cost or latency, but to maximize the probability that the entire workflow completes successfully such that total cost $\le B$ and total time $\le D$.

This is formulated as a finite-horizon stochastic online allocation problem. The state is defined by the set of completed subtasks, remaining budget, and remaining time. The challenge lies in the combinatorial explosion of possible execution paths, stochastic outcomes (success/failure of subtasks), and the interdependence of resource consumption across the workflow. A static assignment of models or sampling strategies is insufficient because the optimal decision depends on the evolving state, remaining constraints, and observed stochastic events.

Methodology: Monte Carlo Portfolio Planning (MCPP)

To solve this intractable optimization problem, the authors propose Monte Carlo Portfolio Planning (MCPP), a lightweight, closed-loop planner.

1. Problem Formulation

The workflow is modeled as $I = (G, M, \Phi, B, D)$, where $G$ is the subtask graph, $M$ is the set of available models, and $\Phi$ contains estimated success probabilities ($p_{v,m}$) and expected generation lengths ($\ell_{v,m}$) for each subtask-model pair.
The goal is to find a policy $\pi$ that maximizes:
$$J(\pi) = \Pr_{\pi} (T_{solve} \le D, C_{\pi} \le B)$$
Exact dynamic programming is theoretically possible but computationally intractable due to the exponential state space (combinations of completed subtasks) and action space (model and sampling width choices for all ready nodes).

2. The MCPP Algorithm

MCPP approximates the optimal decision rule using a one-step portfolio rollout backup:

• Candidate Action Set: At each state, the planner constructs a set of candidate actions $\tilde{A}(s)$. This set includes specific allocations for ready nodes and is augmented by a portfolio of simple continuation policies $\Pi_0$. Each policy in the portfolio is a "Retry-$k$" strategy that assigns a specific model $m$ and sampling width $k$ to all future executable subtasks.
• Monte Carlo Estimation: For each candidate current action $a$, the planner estimates its value by simulating the workflow execution. It applies $a$, samples the stochastic outcome (which subtasks succeed), updates the state, and then follows each continuation policy $\mu \in \Pi_0$ until the workflow finishes or constraints are violated.
• Selection: The value of action $a$ is estimated as the maximum success probability over all continuation policies in the portfolio: $\hat{Q}_{\Pi_0}(s, a) = \max_{\mu \in \Pi_0} \hat{Q}_{\mu}(s, a)$. The action with the highest estimated value is selected for execution.
• Closed-Loop Replanning: After executing the selected action and observing the actual outcomes, the planner updates the state (remaining budget, time, and completed subtasks) and replans. This allows the system to adapt to stochastic failures and resource consumption in real-time.

3. Theoretical Guarantees

The paper provides a "safe-improvement" analysis. It proves that, up to finite-sample Monte Carlo error, candidate-set approximation error, and estimation errors in success rates/lengths, the MCPP policy yields a constrained completion probability that is at least as high as the best base policy in the portfolio. This ensures that the planner never performs worse than a simple, static strategy (like always using the same model and sampling width) while offering the potential for significant gains through lookahead.

Key Contributions

1. Problem Formulation: The authors introduce the setting of constraint-driven online resource allocation, shifting the objective from optimizing average efficiency frontiers to maximizing the probability of meeting hard budget and deadline constraints for specific workflow instances.
2. Algorithm Proposal: They propose MCPP, a closed-loop planner that directly estimates constrained completion probability via simulated rollouts and replans based on observed outcomes. It avoids exhaustive dynamic programming by using a portfolio of simple continuation policies to approximate future values.
3. Empirical Validation: The method is evaluated on two dependency-structured benchmarks: CodeFlow (code generation and verification) and ProofFlow (formal reasoning and proof generation).
4. Robustness Analysis: The paper demonstrates that MCPP remains effective even when the input estimates (success rates and generation lengths) are noisy, a common scenario in real-world deployments.

Experimental Results

Experiments were conducted on CodeFlow and ProofFlow benchmarks using various budget ($B$) and deadline ($D$) constraints.

• Performance: MCPP consistently outperformed strong baselines, including Uniform (static allocation of budget across subtasks) and Retry (online local retrying without downstream planning).
• Tight Constraints: The improvement was most significant under tight constraints (e.g., B = \0.05$). MCPP could rapidly achieve high success rates once the deadline became moderately feasible, whereas baselines remained substantially lower.
• Action Diversity: Ablation studies showed that performance improves with larger model portfolios (using multiple models) and richer rollout-width portfolios (varying sampling widths). This highlights the importance of selecting the right model and compute intensity for specific nodes and states rather than using a single global strategy.
• Robustness: Under noisy estimates of success rates (Gaussian noise with $\sigma=0.3$), MCPP showed a degradation of only ~6 percentage points, demonstrating resilience to imperfect profile estimation.
• Scalability: The method scales effectively to larger workflows (more subtasks), maintaining its advantage over baselines, particularly in constrained scenarios where static allocation fails to adapt to intermediate outcomes.
• Efficiency: The online planning overhead is moderate (typically under 5 seconds for standard configurations), making it practical for real-time execution.

Significance and Claims

The paper claims that its primary significance lies in addressing the instance-specific success condition of real-world agentic deployments. While previous work focused on improving the "performance–cost–latency frontier" (average efficiency), this work treats budget and time as hard constraints that define success or failure.

The authors argue that a better frontier does not automatically translate to a better action policy under specific constraints. MCPP bridges this gap by directly optimizing for the probability of meeting the user's specific $B$ and $D$ requirements. The paper modestly claims that MCPP provides a safe improvement over base policies and demonstrates consistent gains in constrained environments, without claiming global optimality or solving the general problem of workflow generation (which is treated as a separate upstream task). The work is positioned as a practical solver for the execution phase of agentic systems, assuming the workflow structure and statistical profiles are available.