ProgRouter: Online Progress-Guided Orchestration for Multi-Agent LLM Workflows under Quality-Cost Tradeoffs

AI summary

Overview

Research area: Multi-agent large language model (LLM) orchestration, LLM cascade routing, and cost-aware inference serving.

Technical level: Advanced. The paper assumes familiarity with constrained online optimization (Lyapunov drift-plus-penalty), cascade LLM serving, agentic workflow design, and tree-based regression.

Scope: A framework, ProgRouter, that makes step-by-step online decisions about which LLM should instantiate which worker agent role inside a multi-agent workflow, trading predicted task progress against per-task time and operating cost budgets.

What This Paper Is About

Multi-agent LLM workflows solve hard, open-ended tasks by having a coordinator agent dispatch specialised worker agents across many steps, but repeated LLM calls and long accumulated contexts make them expensive to run. Existing routing methods such as cascade routing make one-shot, query-level choices before a workflow starts, so they cannot adapt to an evolving workflow state where the right model at each step depends on how much progress has been made and how much difficulty remains. ProgRouter addresses this by scoring task progress continuously during execution and picking, at every dispatch step, the LLM that offers the best predicted progress gain relative to its time and cost.

Key Contributions

1. A multi-view task progress scorer. The scorer maps an intermediate workflow state into a normalised progress score in [0, 1] by combining a coarse overall-outcome regime (invalid, recoverable, partial success, complete) with three fine-grained views: subtask completion, short-term progress trend, and state quality based on semantic similarity between consecutive state summaries plus structural state differences.

2. A dual-path task progress predictor with adaptive meta-gating. Progress gain from each candidate LLM is estimated by two complementary paths — a structured path over tabular features (tree-based regressor such as random forest or XGBoost) and a semantic path over a natural-language workflow summary encoded by a lightweight sentence encoder such as MiniLM — combined by a tree-based meta-gated learner.

3. An online, budget-aware routing algorithm. The routing score combines the predicted progress gain (weighted by the remaining progress gap), a virtual cost queue tracking violation of the long-term average energy budget, and exponential penalties for consumption of per-task time and cost budgets.

4. Online predictor learning without offline data. The predictor is trained during deployment via an exploration-and-update loop: with probability epsilon a random candidate LLM is selected to collect an unbiased sample, the realised progress gain is computed as g(s_{t+1}) − g(s_t), and epsilon decays as samples accumulate, shifting from exploration to exploitation.

Main Findings

• ProgRouter leads on HumanEval Plus. With a budget of 4,800 J, ProgRouter reaches a 93.0% pass rate at 4,796 J and 13.7 s, exceeding MasRouter (90.9%) by +2.1% and CASCADIA (84.8%) by +8.2%. Educated Guessing achieves 91.5% but exceeds the budget at 4,916 J.

• ProgRouter dominates on MBPP. It records the best pass rate (79.4%), the lowest energy (3,376 J), and the shortest execution time (10.3 s) of all compared methods, against a 4,500 J budget.

• On MATH-500 it is the cheapest budget-satisfying method. With a 7,000 J budget, ProgRouter delivers 84.3% pass rate at 6,112 J and 19.0 s, the lowest energy and shortest time among budget-satisfying methods. CASCADIA scores higher (87.8%) but at a higher cost (6,875 J, 24.6 s) — ProgRouter is 3.5 percentage points below it. MasRouter (8,294 J) and Educated Guessing (7,023 J) both violate the budget.

• It generalises to open-ended retrieval-augmented QA. On ASQA, under a 19,000 J budget, ProgRouter achieves the highest citation precision (92.1%) at 18,373 J and 61.6 s, improving by 2.3% over MasRouter (89.8%) and CASCADIA (89.8%).

• Fixed single-model policies offer an unfavourable trade-off. Small models such as Qwen2.5-Coder 0.5B and Granite 4.1 3B incur high cumulative energy because weak task-solving triggers repeated dispatch steps; large models such as Gemma 4 31B exceed the budget, consuming up to 26,276 J on MATH-500. On ASQA, fixed single-model Qwen 3.5 and Qwen 3.6 policies exceed 19,000 J except the smallest configuration, which satisfies the budget with lower citation precision.

• Baselines show consistent failure modes. Educated Guessing converges to task-agnostic historically strong choices (98.8% Granite 4.1 8B on MATH-500), violating the MATH-500 budget. CASCADIA's reactive escalation wastes small-model calls, lowering HumanEval Plus pass rate to 84.8%. MasRouter does not adapt to evolving states and budgets, violating energy on MATH-500 (8,294 J) and scoring a weak 67.8% on MBPP; on ASQA it routes 88.3% of calls to Qwen 3.5 2B for lower precision (89.8%) than ProgRouter (92.1%).

• Routing is adaptively specialised. ProgRouter concentrates most dispatch steps on small models in the dominant family — 84.3% on Qwen2.5-Coder 0.5B for HumanEval Plus and 91.0% on Granite 4.1 3B for MATH-500 — invoking larger models only when the predictor expects substantial gain.

• ProgRouter sits near the Pareto frontier across all four benchmarks, which the authors attribute to the progress-aware routing score combined with virtual-queue-based budget tracking.

Methodology in Plain English

The authors frame the problem as an online constrained optimisation: maximise average task-solving performance across a stream of user tasks subject to per-task time and energy budgets and a long-term average energy constraint.

Progress is measured during execution rather than only at the end. A coordinator LLM agent maintains structured "ledgers" of task objectives, progress, reasoning traces, and prior worker outputs. From these, the multi-view scorer produces a single progress number by starting with a base score for the coarse outcome regime and adding weighted contributions from subtask completion, recent progress trend, and state quality. The weights are non-negative and regime-specific, so the scorer is a lightweight domain adapter: only the observable milestones and outcome regimes need adapting to a new domain.

Because progress alone is backward-looking, a predictor estimates how much progress a candidate LLM would add if invoked next. It runs two parallel estimates — one from explicit tabular features (including the progress score, its components, dispatch history, and the candidate model), one from an embedded natural-language summary of the state and the decision — and a meta-gated tree-based learner decides how much to trust each path based on context.

Routing then converts prediction into action. A virtual queue accumulates any overshoot of the long-term average energy budget across completed tasks. The score for each candidate model combines: progress gain weighted by the remaining progress gap (1 − g(s_t)), so that stronger models are favoured only when there is real room to improve; a queue-weighted cost term; and two exponential penalty coefficients that grow as cumulative time or energy approaches the per-task budget, discouraging late-stage selection of expensive models unless the predicted gain justifies it. The highest-scoring model is selected immediately and irrevocably.

Experiments cover four benchmarks — 164 HumanEval Plus tasks, 200 MBPP tasks, 200 MATH-500 problems, and 100 ASQA tasks — with pass rate as the completion metric for the first three and citation precision for ASQA. Model zoos differ per benchmark: nine Qwen 2.5-Coder and Qwen 3.5 models for coding, seven Granite 4.1 and Gemma 4 models for MATH-500, and seven Qwen 3.5 and Qwen 3.6 models for ASQA. Operating cost is reported as energy consumption in joules.

Why This Matters

Impact on research. The work argues that one-shot cascade routing is structurally mismatched to stateful, multi-step agentic workflows, and proposes step-wise, progress-conditioned routing as the alternative. It also shows that dense intermediate supervision derived from workflow states can substitute for the sparse end-of-workflow outcome signal, and that a router can be learned online without offline training data — a template that transfers to other sequential decision problems under budget constraints.

Real-world applications:

• Cost- and energy-aware serving platforms that host multi-agent coding assistants, where teams need strong pass rates without uncontrolled token or GPU spend.
• Retrieval-augmented question answering services that must produce citation-supported answers under latency budgets, where no unit-test-style correctness signal exists.
• Mathematical and analytical reasoning assistants, where invoking a very large model on every step is prohibitively expensive.
• Sustainable AI deployment planning, since the framework explicitly targets reductions in energy consumption and operating cost.

Industry relevance. Providers running agentic products pay per LLM call and per joule; ProgRouter's routing score is designed to be evaluated with negligible overhead because both prediction paths use a lightweight encoder or moderate tree-based regressors, making it plausible to deploy as a routing layer in front of an existing model zoo, and it also offers a concrete way to report and enforce service-level energy budgets.

Future Directions

• Broaden the agentic domains tested. The evaluation covers code generation, mathematical reasoning, and retrieval-augmented long-form QA; the authors state that generalisation to settings such as open-ended web navigation and tool-augmented QA remains to be empirically verified.
• Automate the domain adapter. The multi-view progress scorer currently requires a human to specify observable workflow milestones and coarse outcome regimes for each new task domain; learning these representations fully end-to-end is named as an open direction.
• Clarify the ablation evidence. Component-wise evaluations and ablation analysis are listed for Appendix E, but the results themselves are not reported in the paper content available here, so the individual contribution of each component is not quantified in the main text.
• Assess robustness of the quality-cost calibration. Because routing follows predicted progress regardless of model capability, questions remain about how stable routing patterns are across task types and how sensitive results are to the trade-off coefficient V, the exploration probability epsilon, and the progress scoring weights — none of which are analysed with reported sensitivity results in the content provided.

Target Audience

Researchers and engineers working on LLM serving, cascade routing, and multi-agent agentic systems; systems practitioners building cost- or energy-constrained LLM products; and graduate students interested in online constrained optimisation applied to language model orchestration. Readers need some background in agentic workflow design and budget-constrained decision making to follow the routing formulation, though the high-level motivation and benchmark comparisons are accessible to a broader technical audience.

Authors’ abstract

Multi-agent large language model (LLM) workflows have emerged as a powerful paradigm for solving complex, open-ended tasks through collaborative reasoning among specialized LLM agents, but they incur substantial operating costs due to repeated LLM invocations and long-horizon context accumulation. Existing cascade routing methods make one-shot, query-level decisions and cannot adapt to the dynamic, state-dependent nature of multi-step workflows, in which the right LLM at each step depends on evolving task progress, remaining task difficulty, and cost-efficiency requirements. We present ProgRouter, an online progress-guided routing framework that adaptively selects LLM agents across workflow steps to preserve task-solving quality while adhering to time and cost budgets. ProgRouter introduces a multi-view task progress scorer that combines coarse workflow outcome regimes with fine-grained signals on subtask completion, progress trends, and workflow state quality. Then, a dual-path task progress predictor and an adaptive meta-gating mechanism estimate the progress gain for each candidate routed LLM. ProgRouter makes online step-wise routing decisions that balance progress gain, task time budgets, and long-term operating cost efficiency. Experiments on HumanEval Plus, MBPP, MATH-500, and ASQA, spanning agentic code generation, mathematical reasoning, and retrieval-augmented long-form question answering, demonstrate that ProgRouter reduces the operating cost relative to key baselines while maintaining strong task-solving performance.