ProgRouter: Online Progress-Guided Orchestration of Multi-Agent Workflows Under Quality-Cost Trade-offs

Background and Context

Multi-agent large language model (LLM) workflows have emerged as a leading paradigm for solving complex, open-ended tasks, relying on collaborative reasoning between specialized LLM agents. This approach typically involves repeated LLM invocations and accumulating long-context windows, which drive up operational costs substantially. The central tension the paper addresses is how to maintain or even improve task-solving quality while controlling time and cost budgets. Existing cascade routing methods make single-shot, query-level decisions, treating routing as a one-time judgment applied to the entire workflow. This static approach cannot accommodate the dynamic, state-dependent nature of multi-step workflows, where the choice of LLM at each step depends on evolving task progress, remaining difficulty, and shifting cost-efficiency requirements that change as the workflow advances.

Deep Analysis

The authors propose ProgRouter, an online progress-guided routing framework that adaptively selects the most suitable LLM agent at each workflow step, transforming routing from a static one-time judgment into a dynamic orchestration process that continuously adjusts as task state evolves. The method centers on perceiving and predicting task progress. A multi-view task progress scorer combines coarse-grained workflow outcome state with fine-grained signals covering subtask completion, progress trends, and workflow state quality, producing a more nuanced representation of where the task currently stands. After obtaining this progress representation, the framework employs a dual-path task progress predictor paired with an adaptive meta-gating mechanism to estimate the progress gain each candidate LLM would deliver. The dual-path design means prediction draws on multiple signals rather than a single one, while the adaptive gating dynamically weights candidate paths according to real-time state.

ProgRouter makes routing decisions in a step-by-step, online manner, trading off progress gain against task time budget and long-run cost efficiency rather than pursuing single-step optimality. This unification of short-term progress gains with long-term cost efficiency is precisely what distinguishes it from one-shot routing methods. The experimental setup spans multiple representative benchmarks covering diverse task types: HumanEval Plus and MBPP evaluate agent code generation, MATH-500 tests mathematical reasoning, and ASQA targets retrieval-augmented long-form question answering. This cross-task selection ensures the conclusions reflect ProgRouter's generality across different reasoning modes. Experiments show ProgRouter significantly reduces operational cost relative to key baselines while preserving strong task performance, demonstrating that online, progress-guided routing can achieve cost savings without sacrificing quality rather than trading effectiveness for lower overhead. Because the abstract discloses no specific numerical metrics, the paper emphasizes overall quality-cost trade-off performance relative to baselines rather than absolute gains on any single dataset.

Industry Impact

The online progress-guided routing approach offers a practical path toward low-cost deployment of multi-agent LLM workflows. As agent systems become widespread in real applications, operational cost and time budgets often become bottlenecks to deployment, and this method shows that fine-grained task progress perception combined with dynamic routing can substantially compress overhead without significant quality loss. For the open-source community, it provides a transferable framework design paradigm that upgrades routing from static judgment to online orchestration driven by evolving state. For industrial deployment, this quality-and-cost-balancing approach helps deploy more complex, long-horizon multi-step tasks in real-world scenarios. For subsequent research, the design of multi-view progress scoring, dual-path prediction, and adaptive gating opens new directions for modeling task state more granularly and trading off short-term gains against long-term cost online.

Outlook

Overall, this work shifts multi-agent system focus from pure performance improvement toward engineering thinking that weighs performance and cost equally, carrying notable heuristic value. The paper's emphasis on relative trade-off performance across multiple tasks rather than overfitting to a specific dataset signals a design philosophy aimed at generality. As agent workflows grow more complex and longer-horizon in production, frameworks like ProgRouter that make routing decisions adaptively over time may become increasingly important for keeping deployment economically viable. The distinction between coarse-grained workflow state and fine-grained subtask signals suggests future systems could refine progress estimation even further, while the adaptive meta-gating mechanism points toward more flexible path selection as candidate LLM pools expand.