BRIGADE: Bayesian Runtime Inference Guiding Agentic DAG Execution under Budget Constraints

Decomposing a complex task into a workflow of subtasks lets large language model (LLM) agents work on focused contexts instead of one long context that hurts understanding or exceeds the context window. However, multi-agent workflows are rarely cost-effective: they consume much more budget without a matching gain in performance, because the execution path is unclear, outputs are verified repeatedly, and no principled rule says when to stop. Effective orchestration therefore requires deciding not only which subtask to execute, but also when to acquire verification evidence or stop. To this end, we introduce BRIGADE, a Bayesian decision-theoretic framework for budget-constrained orchestration over a fixed task directed acyclic graph. BRIGADE combines prior knowledge of the model's ability with posterior beliefs over artifact correctness updated by evidence obtained at runtime, and controls the workflow by solving the constrained optimization problem. To make this problem tractable, we derive a lightweight two-step lookahead controller that selects execution, verification, and submission actions online under the budget, without calling an LLM planner at each round. By conditioning the second decision on possible observations, the controller values verification for guiding later actions, even when verification does not directly improve an artifact. Controlled simulations show gains from two-step lookahead when budgets permit additional decisions beyond the cheapest completion. On AppWorld with Doubao executors, BRIGADE shows favorable task-success-cost trade-offs at low and intermediate operating points.