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

arXiv: https://arxiv.org/abs/2605.06110 · HTML: https://mlsanity.com/paper/2605.06110/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Software engineering coding agents, one of 16 directions in LLM agents and tool use.
- Builds on 34 of its 45 references that are in the map.
- First posted on arXiv 7 May 2026.

## Placed in

- LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/)

## Builds on (most cited first, 30 of 34)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [Gorilla: Large Language Model Connected with Massive APIs](https://mlsanity.com/paper/2305.15334/) (2023)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [GAIA: a benchmark for General AI Assistants](https://mlsanity.com/paper/2311.12983/) (2023)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [Kimi K2.5: Visual Agentic Intelligence](https://mlsanity.com/paper/2602.02276/) (2026)
- [Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing](https://mlsanity.com/paper/2404.14618/) (2024)
- [Plan-and-Act: Improving Planning of Agents for Long-Horizon Tasks](https://mlsanity.com/paper/2503.09572/) (2025)
- [Kimina-Prover Preview: Towards Large Formal Reasoning Models with Reinforcement Learning](https://mlsanity.com/paper/2504.11354/) (2025)
- [Multi-agent Architecture Search via Agentic Supernet](https://mlsanity.com/paper/2502.04180/) (2025)
- [Goedel-Prover-V2: Scaling Formal Theorem Proving with Scaffolded Data Synthesis and Self-Correction](https://mlsanity.com/paper/2508.03613/) (2025)
- [BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute](https://mlsanity.com/paper/2506.22716/) (2025)
- [ScoreFlow: Mastering LLM Agent Workflows via Score-based Preference Optimization](https://mlsanity.com/paper/2502.04306/) (2025)
- [EvoAgentX: An Automated Framework for Evolving Agentic Workflows](https://mlsanity.com/paper/2507.03616/) (2025)
- [Budget-Aware Tool Use Enables Effective Agent Scaling](https://mlsanity.com/paper/2511.17006/) (2025)
- [ClawBench: Can AI Agents Complete Everyday Online Tasks?](https://mlsanity.com/paper/2604.08523/) (2026)
- [100 instances is all you need: predicting the success of a new LLM on unseen data by testing on a few instances](https://mlsanity.com/paper/2409.03563/) (2024)
- [Route to Reason: Adaptive Routing for LLM and Reasoning Strategy Selection](https://mlsanity.com/paper/2505.19435/) (2025)
- [ProofFlow: A Dependency Graph Approach to Faithful Proof Autoformalization](https://mlsanity.com/paper/2510.15981/) (2025)
- [CodeFlowBench: A Multi-turn, Iterative Benchmark for Complex Code Generation](https://mlsanity.com/paper/2504.21751/) (2025)
- [AgentTTS: Large Language Model Agent for Test-time Compute-optimal Scaling Strategy in Complex Tasks](https://mlsanity.com/paper/2508.00890/) (2025)
- [EvoRoute: Experience-Driven Self-Routing LLM Agent Systems](https://mlsanity.com/paper/2601.02695/) (2026)
- [Budget-Aware Agentic Routing via Boundary-Guided Training](https://mlsanity.com/paper/2602.21227/) (2026)
- [Faster and Better LLMs via Latency-Aware Test-Time Scaling](https://mlsanity.com/paper/2505.19634/) (2025)
- [MegaFlow: Large-Scale Distributed Orchestration System for the Agentic Era](https://mlsanity.com/paper/2601.07526/) (2026)
- [Latency and Token-Aware Test-Time Compute](https://mlsanity.com/paper/2509.09864/) (2025)

## Built on by (most cited first, 3 of 3)

- [Small RL Controller, Large Language Model: RL-Guided Adaptive Sampling for Test-Time Scaling](https://mlsanity.com/paper/2606.03102/) (2026)
- [AllocBench: Measuring Online Tool Allocation Capability in LLM Agents](https://mlsanity.com/paper/2607.23332/) (2026)
- [From Pareto to Preference: Personalized Test-Time Scaling via Amortized Agentic Policy Discovery](https://mlsanity.com/paper/2610.09684/) (2026)

## Abstract (arXiv)

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 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 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.