ProgRouter: Online Progress-Guided Orchestration fo...

ProgRouter: Online Progress-Guided Orchestration fo... | AI Research

Key Takeaways

ProgRouter is an online framework designed to manage multi-agent LLM workflows by dynamically selecting the most appropriate LLM for each step of a task.
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.

Paper AbstractExpand

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.

ProgRouter is an online framework designed to manage multi-agent LLM workflows by dynamically selecting the most appropriate LLM for each step of a task. It aims to balance the need for high-quality results with the constraints of time and operating costs, which are often high in complex, multi-step workflows.

The Challenge of Multi-Agent Workflows

Multi-agent workflows involve multiple specialized LLMs working together to solve complex tasks. Existing routing methods typically make a single, one-shot decision at the start of a query. However, these workflows are dynamic and state-dependent, meaning the "right" model changes as the task progresses. If a system always uses the most powerful (and expensive) models, it exhausts its budget; if it uses only weak models, it risks failure. ProgRouter addresses this by making step-by-step routing decisions based on real-time task progress and remaining budget.

How ProgRouter Works

The framework uses three primary components to make its routing decisions:

Multi-View Task Progress Scorer: This component evaluates the current state of a workflow by combining four signals: the overall outcome regime (e.g., whether the task is recoverable or complete), the percentage of subtasks finished, the trend of progress over recent steps, and the quality of the current workflow state. This provides a unified score representing how close the system is to success.
Dual-Path Task Progress Predictor: To decide which LLM to use next, the system predicts the "progress gain" of each candidate model. It uses a "structured path" for explicit data (like subtask status) and a "semantic path" for qualitative summaries of the workflow state. A meta-gating mechanism then weighs these two paths to provide a final prediction.
Online Decision-Making: Using the progress prediction, the system selects an LLM by calculating a score that balances the expected progress gain against the remaining time and cost budgets. It uses "virtual cost queues" to track system-level budget violations and applies penalties to expensive models as the workflow nears its budget limits.

Performance and Results

The researchers tested ProgRouter on several benchmarks, including HumanEval Plus, MBPP, MATH-500, and ASQA. These tasks covered code generation, mathematical reasoning, and retrieval-augmented long-form question answering. According to the paper, ProgRouter reduced operating costs compared to key baselines while maintaining task-solving performance.

Considerations for Implementation

The authors note that while the core routing algorithm is domain-independent, the multi-view task progress scorer requires adaptation for new domains. Specifically, users must define the observable milestones and coarse outcome regimes relevant to their specific task. The system is designed to learn and refine its routing strategy as it executes, using an exploration-and-update procedure where it occasionally selects models randomly to collect unbiased training data for its progress predictor.