Quality-Aware Online Budget Control for LLM-based Multi-Agent Systems

Cost-efficient language-model multi-agent systems (MAS) often target average cost reduction, whereas deployment under user quotas requires maximizing quality within a hard per-request budget. We propose Quality-Aware Online Budget Control (QOBC), a unified controller for single-round MAS with explicit dependencies and enforceable output limits. QOBC learns agent budget–quality curves through single-agent interventions, selects a feasible execution graph, and reallocates output budgets during execution. A shared solver accounts for generation and downstream input costs. Actual usage drives replanning; joint batch reservations enforce safety under explicit accounting assumptions. On 50 held-out MATH questions per controlled workflow, QOBC improves normalized budget–accuracy AUC over online equal allocation by 0.220 and 0.230 in sequential and parallel structures. On 100 new held-out inputs per native application, MoA AUC rises from 0.538 with static quality allocation to 0.618. On Screenplay, AUC rises from at most 0.292 with online equal allocation to at least 0.469, with the best quality at the 100% reference-budget level. No request-budget violation is observed across 6,000 native conditions.