💬 NLP

EvolveRouter: Co-Evolving Routing and Prompt for Multi-Agent Question Answering

EvolveRouter is a trainable framework that enhances multi-agent question answering by co-evolving agent prompts and routing strategies through a closed-loop refinement process and an adaptive collaboration mechanism, thereby outperforming state-of-the-art baselines in both accuracy and efficiency.

Original authors: Jiatan Huang, Zheyuan Zhang, Kaiwen Shi, Yanfang Ye, Chuxu Zhang

Published 2026-04-08

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jiatan Huang, Zheyuan Zhang, Kaiwen Shi, Yanfang Ye, Chuxu Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a massive, high-stakes trivia team. You have 24 different experts on your roster: some are math geniuses, some are history buffs, some are great at spotting patterns, and others are excellent at debating.

The problem? You don't know who is best at what.

If you ask a question about 19th-century poetry, you don't want to waste time asking your math genius. If you ask a complex logic puzzle, you don't want to rely solely on your history buff. In the past, researchers tried to solve this by building a "manager" (a router) to pick the right expert for each question. But they had two big flaws:

The experts were stuck: If an expert was bad at a task because of how they were instructed, the manager just had to avoid them. The experts themselves never got better.
The team size was rigid: The manager either picked one person or asked all 24 to shout out answers at once. This was either too risky (picking the wrong one) or too expensive (wasting time on 24 people when one would do).

Enter EvolveRouter. Think of it as a super-manager that doesn't just pick players; it trains them while the game is happening.

Here is how it works, broken down into three simple steps:

1. The "Coach's Eye" (Closed-Loop Co-Evolution)

Imagine a coach watching a game. Instead of just benching a player who misses a shot, the coach pulls them aside and says, "Hey, you're missing the shot because you're looking at the wrong hoop. Let's adjust your stance."

EvolveRouter does exactly this.

The Diagnosis: It asks all 24 experts a question. When an expert gets it wrong, the system doesn't just throw the answer away. It analyzes why they failed.
The Fix: It takes the "bad" instructions (prompts) given to that expert and rewrites them. Maybe it adds a rule like, "Always check the date first," or "Don't guess if you aren't sure."
The Loop: Once the expert is "re-trained" with better instructions, they become smarter. The manager then learns from this smarter expert, creating a cycle where the team gets better and the manager gets smarter simultaneously.

2. The "Smart Huddle" (Adaptive Collaboration)

In the old days, the manager had two choices: pick one person (risky!) or ask everyone (slow and expensive!).

EvolveRouter uses a dynamic huddle strategy.

It asks the experts one by one, starting with the one it thinks is most likely to be right.
After the first expert answers, it asks the second. Then the third.
The Magic Stop: It keeps a running tally. As soon as the top experts start agreeing with each other strongly enough, the manager says, "Okay, we have our answer! Stop asking the rest!"
The Result: For easy questions, it might only ask 2 or 3 people (saving huge amounts of time and money). For super-hard questions, it might ask 10 or 15 to be sure. It adapts the team size to the difficulty of the question.

3. The "Knowledge Map" (The Brain)

To make these decisions, EvolveRouter doesn't just look at the question text. It builds a mental map (a Knowledge Graph) connecting the question to facts, entities, and the specific strengths of each expert.

Think of it like a GPS. If you ask, "How do I get to the library?", a standard GPS just looks at the road. EvolveRouter looks at the road, the traffic, the time of day, and your driving habits to decide the best route. It understands the context of the question to know which expert is the "driver" for that specific trip.

Why is this a big deal?

It's Cheaper: By stopping the "huddle" early when the team agrees, it uses far fewer computer resources (which saves money and energy).
It's Smarter: Because it fixes the experts' instructions, the team gets stronger over time, not just the manager.
It's Flexible: It handles easy questions quickly and hard questions thoroughly, rather than using a "one size fits all" approach.

In a nutshell: EvolveRouter is like a self-improving sports team. It doesn't just pick the best player; it coaches the players to be better, and it knows exactly how many players to put on the field for the specific game being played. The result is a team that is faster, cheaper, and smarter than anything we've seen before.

1. Problem Statement

Large Language Model (LLM) agents often exhibit complementary strengths depending on the task, context, and prompt configuration. While multi-agent systems offer a way to leverage these strengths, existing approaches face two critical limitations:

Static Agent Behavior: Current routing methods optimize which agent to select but treat the agents themselves as fixed. They ignore the fact that minor variations in prompt instructions can lead to significant performance differences, leaving underlying agent configurations suboptimal.
Rigid Collaboration Schemes: Existing methods typically route queries to a single agent or aggregate a fixed set of agents. This lacks adaptivity; it either misses complementary expertise (single-agent) or incurs unnecessary computational costs and potential noise (fixed-pool aggregation) by including irrelevant agents for specific queries.

The core challenge is to develop a system that simultaneously optimizes agent quality (via prompt refinement) and collaboration structure (via dynamic routing and adaptive agent selection).

2. Methodology: EvolveRouter

The authors propose EvolveRouter, a trainable framework that addresses these limitations through a closed-loop co-evolution process and an adaptive inference strategy.

A. Closed-Loop Co-Evolution of Routing and Prompts

The framework alternates between training a router and refining agent prompts over $R$ rounds:

Knowledge Graph Construction: Each QA instance is represented as a heterogeneous knowledge graph ( $G$ ) containing query nodes, agent nodes, and entity nodes. Edges encode relationships between queries, entities, and agents.
Router Training (RouterGNN): A Graph Neural Network (GNN) is trained to predict a routing distribution $p_\theta(a|q, G)$ over the agent pool. The training objective minimizes the KL divergence between the router's output and a soft target distribution derived from the agents' actual token-level F1 scores.
Diagnostic Collection: During training, the system collects diagnostic signals, including:
- Agent-level performance summaries.
- A failure archive of incorrect examples with gold answers.
- Router weight statistics (identifying which agents are relied upon).
Targeted Prompt Refinement:
- Selection: Agents are ranked by a priority score: $priority(a) = (1 - F1(a)) \times (\alpha + \bar{w}(a))$ . This prioritizes agents that perform poorly ( $low\ F1$ ) but are heavily relied upon by the router ( $high\ weight$ ), rather than just the worst-performing agents that the router already ignores.
- Rewriting: A rewriter LLM generates candidate prompt revisions based on failure evidence, constrained to preserve the agent's core reasoning strategy while correcting specific failure patterns.
- Validation: Candidates are validated on a targeted subset of failure cases. Only non-regressive, improving prompts are accepted.
Incremental Update: The router is fine-tuned on the updated agent pool (resuming from the previous checkpoint) rather than retrained from scratch, preserving learned routing patterns for unchanged agents.

B. Adaptive Inference via Answer Agreement

During inference, EvolveRouter does not use a fixed number of agents. Instead, it employs a dynamic stopping rule:

Ranking: Agents are queried sequentially based on the router's predicted ranking.
Weighted Agreement: After querying $k$ agents, the system calculates a weighted agreement score $A(k, q)$ , representing the consensus of the top answers weighted by the router's confidence.
Stopping Condition: The process stops as soon as the agreement score exceeds a threshold $\tau$ (after a minimum number of agents $k_{min}$ ).
Final Prediction: The final answer is a router-weighted majority vote of the consulted agents. This allows the system to use fewer agents for easy queries and more for complex ones, optimizing efficiency.

3. Key Contributions

Closed-Loop Co-Evolution: The first framework to jointly optimize routing and agent specialization. It uses router diagnostics to guide prompt refinement and refined agents to provide cleaner supervision for routing, creating a mutually reinforcing cycle.
Adaptive Collaboration: Introduces a dynamic inference mechanism that determines the effective collaboration size ( $K$ ) per query based on answer agreement, moving beyond rigid single-agent or fixed-pool paradigms.
Diagnostic-Girected Optimization: Proposes a priority scoring mechanism that targets agents which are both underperforming and critical to the system's current routing decisions, rather than simply fixing the worst-performing agents.
Comprehensive Empirical Validation: Extensive experiments across five diverse QA benchmarks demonstrate the framework's superiority and provide insights into the interplay between routing and prompt quality.

4. Experimental Results

The framework was evaluated on five benchmarks: 2WikiMultihopQA, HotpotQA, NewsQA, TriviaQA, and NGQA.

Performance: EvolveRouter consistently outperformed all state-of-the-art baselines (including heuristic, training-free, adaptive, and structure-aware routing methods) in both Exact Match (EM) and F1 scores.
- Notable gains were observed on TriviaQA, where EvolveRouter improved over the best baseline (AgentRouter) by +7.08 F1 and +8.67 EM, highlighting the sensitivity of this dataset to prompt-task alignment.
Ablation Studies:
- Prompt Optimization (PO): Contributed the majority of performance gains (e.g., +9.21% F1 on TriviaQA), confirming that improving agent quality is crucial.
- Adaptive K: Provided consistent but smaller gains (+0.70% to +1.53% F1), validating the efficiency of dynamic agent selection.
- Co-evolution Necessity: Retraining the router from scratch after prompt updates resulted in significant performance drops, proving that preserving routing knowledge across rounds is essential.
Efficiency: The Adaptive K strategy reduced the average number of agent calls from 24 (full ensemble) to 2.9–7.4, achieving a 69–88% reduction in computational cost while maintaining or improving accuracy.
Transferability: Routing knowledge learned on one dataset did not transfer well to others, reinforcing the need for per-dataset optimization of both routing and prompts.

5. Significance

EvolveRouter represents a paradigm shift in multi-agent LLM systems by moving from static, pre-defined agent pools to dynamic, self-improving ecosystems.

Systemic Efficiency: It demonstrates that "better agents" and "smarter routing" are not mutually exclusive but are tightly coupled; improving one enhances the other.
Cost-Effectiveness: By dynamically adjusting the number of agents per query, it offers a practical solution for deploying large-scale multi-agent systems in resource-constrained environments.
Generalizability: The framework's success across diverse domains (from general trivia to specialized nutritional health reasoning) suggests it is a robust architecture for future autonomous agent systems.

In summary, EvolveRouter solves the "fixed agent" and "rigid collaboration" bottlenecks by creating a self-correcting loop where the router identifies weaknesses, the system fixes them via prompt engineering, and the improved agents in turn make the router more accurate, all while dynamically scaling computational effort to the difficulty of the query.