On Time, Within Budget: Constraint-Driven Online Resource Allocation for Agentic Workflows
- URL: http://arxiv.org/abs/2605.06110v2
- Date: Fri, 08 May 2026 14:07:34 GMT
- Title: On Time, Within Budget: Constraint-Driven Online Resource Allocation for Agentic Workflows
- Abstract summary: Agentic systems increasingly solve complex user requests by executing orchestrated executables, where subtasks are assigned to specialized models or tools and coordinated according to their dependencies.<n>Real deployments often impose concrete requirements: a workflow must be completed within a specified budget and before a specified deadline.<n>This shifts the goal from average efficiency optimization to maximizing the probability that the entire workflow completes successfully under explicit budget and deadline constraints.
- Score: 37.22092976146466
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Agentic systems increasingly solve complex user requests by executing orchestrated workflows, where subtasks are assigned to specialized models or tools and coordinated according to their dependencies. While recent work improves agent efficiency by optimizing the performance--cost--latency frontier, real deployments often impose concrete requirements: a workflow must be completed within a specified budget and before a specified deadline. This shifts the goal from average efficiency optimization to maximizing the probability that the entire workflow completes successfully under explicit budget and deadline constraints. We study \emph{constraint-driven online resource allocation for agentic workflows}. Given a dependency-structured workflow and estimates of success rates and generation lengths for each subtask--model pair, the executor dynamically allocates models and parallel samples across simultaneously executable subtasks while managing the remaining budget and time. We formulate this setting as a finite-horizon stochastic online allocation problem and propose \emph{Monte Carlo Portfolio Planning} (MCPP), a lightweight closed-loop planner that directly estimates constrained completion probability through simulated workflow executions and replans after observed outcomes. Experiments on CodeFlow and ProofFlow demonstrate that MCPP consistently improves constrained completion probability over strong baselines across a wide range of budget--deadline constraints.
Related papers
- EASy: Towards Efficient LLM-Based Agentic System [54.10819421625103]
We propose EASy, a trainable agentic framework that jointly optimize task performance and computational efficiency through reinforcement learning.<n> EASy equips an LLM-based orchestrator with explicit knowledge of the capability and cost profiles of heterogeneous executors, enabling context-sensitive coordination beyond performance-only routing.<n>It further introduces a milestone-plan-act workflow that decomposes complex tasks into manageable milestones, constructs dependency-aware execution graphs, assigns suitable executors, and parallelizes independent steps while adapting subsequent decisions to intermediate outcomes.
arXiv Detail & Related papers (2026-08-05T08:50:36Z) - HeraSys: Collaborative Serving of Multiple LLM Workflows via Fine-Grained End-to-End Optimization [11.533835891575565]
HeraSys is a serving system designed to optimize the end-to-end performance of concurrent processing.<n>HeraSys reduces P99 latency by up to 2.17$timestimes serving throughput by up to 1.85timestimes under strict latency guarantees.
arXiv Detail & Related papers (2026-06-07T03:14:57Z) - VineLM: Trie-Based Fine-Grained Control for Agentic Workflows [4.984467399543813]
VineLM represents feasible executions as an annotated trie of model-choice prefixes.<n>VineLM represents feasible executions as an annotated trie of model-choice prefixes.
arXiv Detail & Related papers (2026-04-09T15:31:22Z) - Do We Always Need Query-Level Workflows? Rethinking Agentic Workflow Generation for Multi-Agent Systems [72.3575737073235]
Multi-Agent Systems (MAS) solve complex tasks by coordinating multiple agents through.<n>Existing approaches generates either at task level or query level, but their relative costs and benefits remain unclear.<n>We show that query-level workflow generation is not always necessary, since a small set of top-K best task-level together already covers equivalent or even more queries.
arXiv Detail & Related papers (2026-01-16T10:05:51Z) - Flow: Modularized Agentic Workflow Automation [53.073598156915615]
Multi-agent frameworks powered by large language models (LLMs) have demonstrated great success in automated planning and task execution.<n>However, the effective adjustment of agentic during execution has not been well studied.<n>In this paper, we define an activity-on-vertex (AOV) graph, which allows continuous workflow refinement by agents.<n>Our proposed multi-agent framework achieves efficient concurrent execution of subtasks, effective goal achievement, and enhanced error tolerance.
arXiv Detail & Related papers (2025-01-14T04:35:37Z) - Benchmarking Agentic Workflow Generation [80.74757493266057]
We introduce WorfBench, a unified workflow generation benchmark with multi-faceted scenarios and intricate graph workflow structures.<n>We also present WorfEval, a systemic evaluation protocol utilizing subsequence and subgraph matching algorithms.<n>We observe that the generated can enhance downstream tasks, enabling them to achieve superior performance with less time during inference.
arXiv Detail & Related papers (2024-10-10T12:41:19Z) - Multi-objective Optimization of Clustering-based Scheduling for
Multi-workflow On Clouds Considering Fairness [4.021507306414546]
This paper defines a new multi-objective optimization model based on makespan, cost, and fairness, and then proposes a global clustering-based multi-workflow scheduling strategy for resource allocation.
Experimental results show that the proposed approach performs better than the compared algorithms without significant compromise of the overall makespan and cost as well as individual fairness.
arXiv Detail & Related papers (2022-05-23T10:25:16Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination.
We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
arXiv Detail & Related papers (2020-05-27T01:10:41Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.