PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Songyuan Li, Ahmed M. Abdelmoniem, Shiqiang Wang

arXiv:2608.25992v1cs.AIcs.MA

TL;DR

Multi-agent LLM workflows face high operating costs and one-shot routing methods cannot adapt to evolving, state-dependent multi-step execution. ProgRouter uses progress scoring and online budget-aware routing to select agents step by step, achieving strong quality-cost tradeoffs across four benchmarks while satisfying operating-cost budgets. Its generalization beyond the evaluated domains remains to be empirically verified.

  • Problem

    Multi-agent workflows incur substantial costs, while existing one-shot routing cannot adapt agent selection to evolving progress, remaining difficulty, and workflow state.

  • Method

    ProgRouter combines multi-view task progress scoring, dual-path progress prediction, and online budget-aware routing to estimate candidate-agent progress gains and guide step-wise selection.

  • Results

    Across HumanEval Plus, MBPP, MATH-500, and ASQA, ProgRouter consistently satisfies long-term operating-cost budgets while achieving strong task-solving performance and quality-cost tradeoffs.

  • Takeaways & Limitations

    ProgRouter provides a quality-driven, deadline-aware, and cost-efficient approach to online LLM-agent routing across heterogeneous agentic workflows.

  • Takeaways & Limitations

    The method's generalization to open-ended web navigation and tool-augmented question answering remains empirically unverified, and its progress scorer requires lightweight domain adaptation.

Abstract

from arXiv · show

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.

1 Introduction

Multi-agent LLM workflows support complex, iterative problem solving but incur substantial operating costs and require routing decisions that adapt to evolving workflow states. ProgRouter addresses this gap with online, progress-guided, budget-aware routing across workflow steps.

  • Multi-agent workflows coordinate specialized agents across iterative reasoning steps, but repeated LLM calls and long-horizon contexts increase token, compute, energy, and latency costs.
  • Cascade methods route queries to models of varying capability in one shot, which does not adequately support sequentially coordinated multi-agent workflows.
  • Dynamic routing must account for current task progress, partial solution quality, emergent collaboration needs, and remaining difficulty.
  • Miscalibrated progress estimates can waste budget on unnecessarily strong agents or overuse weak agents, causing irrecoverable quality loss.
  • ProgRouter combines multi-view progress scoring with online step-wise routing that balances progress gain, task time budgets, and long-term operating cost efficiency.

2 Problem Setting

A collaborative workflow combines a coordinator, specialized worker roles, and heterogeneous LLMs over evolving dispatch states. ProgRouter selects the LLM instance for each dispatched role using workflow-state information, task characteristics, and execution history under time and cost considerations.

  • Collaborative Multi-agent LLM Workflow: The workflow w = {C, R, M} executes T agent-dispatch steps, with coordinator C, worker roles R, and available LLMs M.
  • Heterogeneous Agent Selection: Heterogeneous workflows use complementary LLM strengths across code generation, mathematical reasoning, and retrieval-augmented question answering.
  • Collaborative Multi-agent LLM Workflow: The coordinator decomposes objectives into subtasks, dispatches specialized worker roles, and adapts execution while maintaining structured workflow-state ledgers.
  • Progress-Guided LLM Routing: ProgRouter selects an LLM from the role-eligible candidate set using subtask domain, estimated difficulty, and historical execution performance.

3 ProgRouter Methodology

ProgRouter formulates multi-agent LLM orchestration as online, step-wise routing that uses workflow progress and predicted progress gain to balance quality, time, and operating-cost constraints. Its multi-view scorer, dual-path predictor, meta-gating, and budget-aware objective support adaptive routing across heterogeneous workflow states.

  • Online routing control: ProgRouter selects LLM agents at each dispatch step from the current workflow state, jointly considering predicted progress gain, remaining difficulty, and cost-budget constraints.A coordinator observes real-time workflow states while dispatching worker agents.
  • Online routing control: The routing problem is challenging because final task performance is observed only after workflow completion and long-term average costs depend on heterogeneous future tasks and dispatch steps.These properties make real-time attribution of each routing decision and prior estimation of system-level cost difficult.
  • Multi-view progress representation: The multi-view progress scorer maps workflow states to normalized progress using coarse outcome regimes plus signals for subtask completion, progress trends, and workflow-state quality.The hierarchical design combines a reliable coarse anchor with fine-grained signals and produces dense step-wise supervision.
  • Multi-view progress representation: The scorer is a lightweight domain adapter: new task domains require adapting observable milestone definitions and coarse outcome regimes, while downstream online routing remains domain-independent.This separates domain-specific progress interpretation from the online exploration-and-update and budget-aware routing procedures.
  • Progress-gain prediction: A dual-path predictor estimates each candidate LLM’s step-wise progress gain from structured workflow features and semantic state summaries, then meta-gating adaptively combines the two estimates.Structured features include progress, completion, trends, dispatch history, and the candidate model; semantic embeddings capture subtler qualitative cues.
  • Budget-aware decision making: The online routing objective balances predicted progress gain against long-term virtual cost-queue control and task-specific time and operating-cost penalties.As cumulative budget consumption approaches its limits, the cost coefficients increase, encouraging costly models only when their predicted progress gain is sufficiently large.

4 Experiments

PROGROUTER is evaluated across code generation, mathematical reasoning, and retrieval-augmented long-form QA using quality, energy, time, and routing-distribution measures. It achieves strong quality-cost tradeoffs by adapting agent selection to workflow progress and remaining difficulty.

  • Dataset and Benchmarks: The evaluation covers HumanEval Plus, MBPP, MATH-500, and ASQA, spanning code generation, mathematical reasoning, and retrieval-augmented long-form QA.ASQA uses citation precision, while the other three benchmarks use task pass rate.
  • Results Analysis: Fixed single-model policies violate the long-term energy-efficiency requirement across all four benchmarks, because weak models trigger recovery calls while strong models incur high per-call energy.On MATH-500, Gemma 4 31B consumes up to 26276 J; on ASQA, fixed policies exceed the 19000 J budget except the smallest configuration, which has lower citation precision.
  • Results Analysis: 93.0% task pass rate on HumanEval Plus places PROGROUTER highest among eE-satisfying methods within the 4800 J budget.This exceeds MasRouter by 2.1% and CASCADIA by 8.2%.
  • Results Analysis: On MATH-500, PROGROUTER records 6112 J and 19.0 s among eE-satisfying methods, while ASQA reaches 92.1% citation precision within 19000 J.The ASQA result improves over MasRouter and CASCADIA, both reported at 89.8%.
  • Results Analysis: Routing distributions concentrate calls on efficient small models while selectively invoking larger models when predicted progress gains justify additional capability.Examples include 84.3% Qwen2.5-Coder 0.5B on HumanEval Plus and 91.0% Granite 4.1 3B on MATH-500.

5 Conclusion

PROGROUTER orchestrates multi-agent LLM workflows by combining progress scoring, progress prediction, and budget-aware routing. Its decisions target marginal progress gains while accounting for quality, deadlines, and operating cost.

  • 5 Conclusion: PROGROUTER estimates each candidate LLM agent’s marginal progress gain using multi-view task progress scoring and dual-path progress prediction.The progress scorer converts observable workflow signals into a unified task-progress representation.
  • 5 Conclusion: The framework guides online agent selection with cost-aware and deadline-aware decisions under quality-cost tradeoffs.It is designed for adaptive orchestration across multi-agent workflow steps.

Limitations

The evaluation covers four agentic benchmarks, but the framework’s generalization beyond these settings remains unverified, and its progress scorer still requires lightweight domain adaptation.

  • Generalization to open-ended web navigation and tool-augmented QA remains empirically unverified beyond the four evaluated benchmarks.The benchmarks cover code generation, mathematical reasoning, and retrieval-augmented long-form question answering.
  • The multi-view task progress scorer requires task-specific specification of observable workflow milestones and coarse outcome regimes.Automatically learning these progress representations end-to-end remains future work.

Ethical Considerations

PROGROUTER targets more sustainable AI serving by reducing workflow energy consumption and operating costs, while deployment still requires model oversight, monitoring, and data protection.

  • PROGROUTER reduces the energy consumption and operating costs of multi-agent LLM workflows, supporting more sustainable AI serving.
  • Output quality, reliability, and potential biases remain dependent on the selected LLMs because routing does not modify their capabilities.The paper recommends model selection, output verification, citation checking, and human oversight.
  • Real-world deployments may store user information in workflow states or coordinator ledgers, requiring access control and data-retention policies.Practitioners should also monitor routing patterns to avoid unintended over-reliance on particular models.

Appendices

The supplementary material expands the paper with notation, benchmark, baseline, experimental, energy-measurement, evaluation, and ablation details.

  • Appendix A: Appendix A lists key notations used throughout the paper.
  • Appendix B: Appendix B describes evaluation datasets and benchmark settings.
  • Appendix C: Appendix C describes state-of-the-art baseline methods.
  • Appendix D: Appendix D provides supplementary experimental configuration, energy measurement methodology, and evaluation protocol details.
  • Appendix E: Appendix E reports ablation analysis results and component-wise evaluations.

B Dataset Details

The evaluation spans code generation, mathematical reasoning, and retrieval-augmented long-form question answering, comparing adaptive routing with established and fixed-model baselines under operating-cost constraints.

  • Datasets: PROGROUTER is evaluated on four benchmarks spanning code generation, mathematical reasoning, and retrieval-augmented long-form question answering.The benchmarks are HumanEval Plus, MBPP, MATH-500, and ASQA.
  • HumanEval Plus: HumanEval Plus uses 164 programming tasks with hidden tests, measuring task pass rate when generated implementations pass all associated tests.
  • MBPP: MBPP evaluates basic Python programming across a random sample of 200 tasks using automated-test pass rate.
  • MATH-500: MATH-500 samples 200 competition-style problems and evaluates generated solutions by exact-answer task pass rate.
  • ASQA: ASQA evaluates iterative evidence retrieval, information synthesis, and citation-supported answer generation for ambiguous open-domain questions.
  • Baselines and measurement: The comparison includes multi-agent, cascade-based, online experience-based, and fixed single-model routing baselines under quality and operating-cost constraints.Energy measurement uses physical GPU power readings, while the reported boundary includes worker and coordinator inference but excludes CPU-side orchestration and host-system energy.

D.3 Online Evaluation Protocol

PROGROUTER evaluates online adaptation through sequential, single-pass task streams, beginning from cold initialization and learning routing from realized progress feedback. Main results are reported after adaptive stabilization on the remaining stream.

  • Evaluation setup: Each benchmark is randomly shuffled with a fixed seed and processed once as a sequential task stream without replay.This setup evaluates online adaptation during execution rather than repeated offline training on the same tasks.
  • Online adaptation: Cold-start evaluation uses ϵ-greedy exploration to collect routing trajectories and realized progress signals as predictor training targets.The progress scorer evaluates each resulting workflow state after a worker LLM executes a selected step.
  • Online adaptation: The training buffer, learned parameters, and virtual queue persist throughout the task stream and are periodically updated as new trajectories arrive.These persistent states support continued adaptation across tasks.
  • Evaluation protocol: Stabilization occurs when the buffer contains sufficient realized-progress samples and exploration falls below a predefined threshold.The reported main results evaluate the adapted policy in steady state on the remaining task stream.
  • Ablation setup: The ablations use HumanEval Plus and separately examine predictor design and online routing components under shared model-zoo and workflow settings.The predictor study covers structured, semantic, and adaptive meta-learning paths; routing studies cover the scorer, budget objective, and virtual queue.

E.1 Ablation of Progress Prediction Components

The progress predictor combines structured execution features with semantic workflow states. Ablations show that both paths contribute complementary information, while adaptive combination produces the most accurate progress estimates.

  • Predictor design: The dual-path predictor uses complementary structured execution features and semantic workflow-state representations.Table 3 evaluates prediction-error variants, with lower MAE indicating more accurate prediction.
  • Predictor ablation: Removing either prediction path increases error, indicating that structured workflow signals and semantic state representations capture different aspects of task evolution.The two views therefore provide nonredundant information for progress estimation.
  • Predictor ablation: The semantic path outperforms the structured path alone because intermediate workflow descriptions contain information beyond explicit execution statistics.This result highlights the value of semantic state representations for estimating evolving task progress.
  • Predictor ablation: Simply averaging the two paths performs worse than the adaptive meta-learner.The meta-learner dynamically adjusts each path’s contribution across workflow states and achieves the best progress-estimation accuracy.

E.2 Ablation of Online Routing Components

Online routing ablations show that progress prediction, multi-view state assessment, and budget-aware optimization jointly support effective agent selection. A naive progress-per-cost strategy performs poorly because it favors inexpensive but insufficiently capable models.

  • Progress prediction: 93.0% pass rate falls to 89.0% when the progress predictor is removed, showing that future progress-gain estimation supports agent selection.Using only one prediction path also decreases end-to-end performance.
  • Progress scoring: 90.2% pass rate results when the multi-view scorer is replaced by test-pass rate alone.Subtask completion, progress trends, and workflow-state quality provide information beyond final-outcome estimation.
  • Budget-aware routing: 87.8% performance follows removal of the budget-aware penalty, despite reduced energy consumption.Without this penalty, routing cannot effectively account for heterogeneous model operating costs.
  • Budget-aware routing: 92.7% versus 93.0% shows the virtual queue has a smaller effect on this finite evaluation stream.Its intended role is controlling long-term budget deviation rather than improving individual-task performance.
  • Complete routing objective: 17.7% pass rate and 7797 J consumption under naive progress-per-cost routing contrast with 93.0% and 4796 J for full PROGROUTER.Greedy immediate progress-per-cost selection favors inexpensive but insufficiently capable LLMs, causing workflow stalls and recovery attempts.
  • Overall findings: The ablations attribute PROGROUTER’s gains to interaction among accurate prediction, workflow-evolution scoring, and budget-aware online selection.The routing objective converts progress signals into effective LLM agent decisions.
Loading 2608.25992v1…