An online progress-guided router for multi-agent LLM workflows cuts operating energy and runtime by adaptively selecting models at each step, maintaining task success on code, math and QA benchmarks while respecting time and cost budgets.

Main Finding

PROGROUTER is an online, progress-guided routing framework for multi‑agent LLM workflows that dynamically selects which LLM instance to call at each workflow step. By estimating stepwise progress gains and balancing them against per-task and long‑term cost/time budgets, PROGROUTER substantially lowers operating cost (energy/time) versus strong baselines while preserving or improving task success across diverse agentic domains (agentic code generation, mathematical reasoning, retrieval‑augmented QA).

Key Points

• Problem framed: online constrained orchestration of heterogeneous LLMs across multi‑step, stateful workflows to maximize task success under per‑task time/cost budgets and a long‑run average operating‑cost constraint.
• Coordinator + ledger: a reasoning-oriented coordinator LLM maintains structured workflow ledgers (state, traces, subtasks) and decides which agent role to dispatch; PROGROUTER decides which LLM instance should instantiate the chosen role.
• Multi‑view task progress scorer: maps workflow state s_t to a normalized progress score g(s_t) in [0,1] by combining four views:
  • overall outcome regime (coarse anchor: invalid / recoverable / partial / complete),
  • subtask completion fraction,
  • short‑term progress trend (delta),
  • workflow state quality (semantic/structural signals). These are aggregated hierarchically to produce dense intermediate supervision.
• Dual‑path progress predictor:
  • structured path: tabular features (progress, subtasks, history, candidate model) → tree regressor;
  • semantic path: coordinator-produced textual summary → sentence embedding → tree regressor;
  • meta‑gating: tree‑based combiner adaptively weights the two path outputs to estimate predicted progress gain ˆy_t(m) for each candidate LLM m.
• Online decision rule:
  • score(m) = V·(1−g(s_t))·ˆy_t(m) − Q·(E(m)−eE) − c_Γ·Γ(m) − c_E·E(m)
  • Q is a virtual cost queue (Lyapunov‑style) tracking long‑run budget violation; c_Γ and c_E are budget‑aware exponential penalties based on fraction of consumed per‑task time/cost budgets.
  • At each step, select m that maximizes score(m). Exploration via ε‑greedy sampling collects labeled progress deltas for online predictor updates; ε decays over time.
• Practical design choices emphasize low overhead: lightweight encoders (e.g., MiniLM), tree regressors (XGBoost/RF) and inexpensive gating so prediction of all candidates is feasible at each step.

Data & Methods

• Workflow model: multi‑agent workflows w = {C, R, M} with a coordinator C and worker roles R; each role can be instantiated by models from a model zoo M (various sizes/capacities).
• Objective: maximize average task success subject to per‑task time Γ_w and energy/cost E_w constraints and a long‑run average energy constraint eE.
• Datasets / task domains:
  • HumanEval Plus and MBPP (agentic code generation),
  • MATH‑500 (mathematical reasoning),
  • ASQA (retrieval‑augmented long‑form QA).
• Baselines compared include cascade routing approaches, MasRouter, and simple heuristics (e.g., single‑model or static cascades).
• Metrics reported: task success (pass/precision), operating cost measured as energy consumption (Joule), and execution time (seconds). Experiments show PROGROUTER reduces operating cost relative to baselines while maintaining strong task performance and respecting the long‑term cost constraint eE.
• Training/online learning: predictor trained online from exploration samples (realized g(s_{t+1})−g(s_t) as label); periodic model updates; ε‑decay to shift from exploration to exploitation.

Implications for AI Economics

• Lower operating cost per task: adaptive routing that invokes stronger (costlier) models only when expected marginal progress warrants it reduces energy and compute billed per workflow — directly lowering operational expenditure for service providers and deployers.
• Better utilization of model heterogeneity: quantitative, online valuation of marginal progress encourages maintaining a model zoo (small/medium/large) and allocating calls dynamically — enabling cost‑efficient capacity planning and investment across model sizes.
• Pricing and SLAs: with predictable long‑run average cost guarantees (virtual queue control), providers can design service tiers or dynamic pricing that trade latency/quality against cost, and craft SLAs that incorporate adaptive routing policies.
• Market effects: reduced marginal cost for complex tasks might lower end‑user prices or enable more frequent/longer agentic workflows; conversely, improved cost efficiency could shift demand toward more agentic, multi‑step applications.
• Sustainability and regulation: energy reductions at the workflow level contribute to lower carbon footprints; regulators and buyers may prefer providers that adopt progress‑guided orchestration for greener AI services.
• Incentive & allocation design: the method highlights the economic value of improved progress estimation (better predictors) — investments in instrumentation (ledgers, progress features) and online learning can yield direct operating‑cost returns.
• Operational caveats: PROGROUTER requires exploration (which has short‑term costs), accurate progress scorer design, coordinator-led state instrumentation, and reliable per‑model cost/time accounting. These implementation costs and potential miscalibration risks must be factored into economic evaluations.

Takeaway: PROGROUTER shows that combining dense, multi‑view progress signals with an online, queue‑aware routing objective enables economically meaningful reductions in the operating cost of agentic LLM workflows while preserving quality — a promising approach for providers and deployers seeking scalable, cost‑aware AI services.