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

Jiatan Huang; Zheyuan Zhang; Kaiwen Shi; Yanfang Ye; Chuxu Zhang

cs.CLApr 6, 2026

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

Authors: Jiatan Huang, Zheyuan Zhang, Kaiwen Shi, Yanfang Ye, Chuxu Zhang

Organizations: University of Connecticut, USA · University of Notre Dame, USA

Abstract

Large language model agents often exhibit complementary strengths, making routing a promising approach for multi-agent question answering. However, existing routing methods remain limited in two important ways: they typically optimize over a fixed pool of agents without improving the agents themselves, and they often rely on rigid collaboration schemes that cannot adapt the number of participating agents to the query. We propose EvolveRouter, a trainable framework that addresses both limitations by jointly improving agent quality and collaboration structure. First, EvolveRouter couples graph-based query routing with targeted instruction refinement in a closed-loop co-evolution process, allowing router diagnostics to guide agent improvement while refined agents provide cleaner supervision for routing. Second, it introduces an adaptive inference strategy that dynamically determines the effective collaboration size for each query through router-weighted answer agreement. Together, these designs enable more capable and more efficient multi-agent reasoning. Experiments on five question answering benchmarks show that EvolveRouter consistently outperforms SOTA routing baselines in both F1 and exact match, while further analysis confirms the benefits of closed-loop refinement and adaptive collaboration.

Figures & tables

Panel of Figure 1 — Figure 1: Motivating observation: agent quality is highly context-dependent, and no single agent configuration is consistently optimal. Multi-dimensional analysis of per-agent F1 (%) across six agent roles, evaluated along three controlled dimensions: task variation (a), backbone variation (b), and prompt variation (c).

Avg. # of Nodes
Statistics	HotpotQA	NewsQA	NGQA
Query	1	1	1
Agent	24	24	24
Entity	142.1	60.3	25.0
Avg. # of Edges
Entity–Entity	385.1	109.4	26.75

Table 1: Comparison of knowledge graph statistics between multi-hop, direct and domain-specific QA benchmarks. Agents and query node number are fixed across benchmarks.

Adaptive Routing
Method	System	Routing	Prompt Opt.	Training	Optimization
LLM-Blender ( Jiang et al., 2023a )	Multi-agent	✓	✗	✓	Supervised
RouterDC ( Chen et al., 2024b )	Single-agent	✓	✗	✓	Supervised
HybridLLM ( Ding et al., 2024 )	Single-agent	✓	✗	✓	Supervised
RouteLLM ( Ong et al., 2025 )	Single-agent	✓	✗	✓	Supervised
MasRouter ( Yue et al., 2025 )	Multi-agent	✓	✗	✓	RL

Table 2: Cross-dimensional comparison of agent system optimization methods. EvolveRouter is the first framework to jointly support routing, prompt optimization, and training in a multi-agent setting.

Figure 2: Overview of EvolveRouter . (a) QA instances are converted into knowledge graphs with trainable query–agent edges. (b) RouterGNN learns routing distributions while collecting diagnostics that guide prompt rewriting in a closed-loop co-evolution. (c) Agents are queried by router rank until weighted agreement exceeds $\tau$ .

Heuristic Baselines
Method	2Wiki		HotpotQA		NewsQA		TriviaQA		NGQA
Method	F1	EM	F1	EM	F1	EM	F1	EM	F1	EM
Average	52.15 $\pm$ 2.20	42.73 $\pm$ 1.88	59.52 $\pm$ 1.09	46.63 $\pm$ 0.79	57.97 $\pm$ 1.64	36.10 $\pm$ 0.69	45.69 $\pm$ 2.27	37.32 $\pm$ 1.64	47.50 $\pm$ 0.80	4.04 $\pm$ 0.38
Majority Vote	67.67 $\pm$ 0.52	58.55 $\pm$ 0.55	63.88 $\pm$ 1.24	52.89 $\pm$ 0.92	59.30 $\pm$ 0.64	39.50 $\pm$ 1.29	53.73 $\pm$ 0.72	43.00 $\pm$ 0.80	48.42 $\pm$ 0.38	4.00 $\pm$ 0.44
Best LLM	71.77 $\pm$ 1.71	62.72 $\pm$ 1.32	68.19 $\pm$ 1.37	51.79 $\pm$ 2.09	60.55 $\pm$ 1.45	39.80 $\pm$ 2.05	51.41 $\pm$ 0.65	42.09 $\pm$ 0.59	48.03 $\pm$ 0.74	3.17 $\pm$ 0.58
Best Agent	75.21 $\pm$ 1.11	64.56 $\pm$ 1.91	68.74 $\pm$ 1.39	56.15 $\pm$ 0.87	62.80 $\pm$ 2.15	37.11 $\pm$ 1.15	60.27 $\pm$ 2.52	50.13 $\pm$ 2.01	48.41 $\pm$ 0.71	4.00 $\pm$ 1.00

Table 3: Performance results with baseline methods on the five QA benchmarks. We report the mean and standard deviation for all results. Best results (excluding Oracle) are in bold , second best are underlined .

Table 4: Ablation study of prompt optimization and adaptive K across five benchmarks.

Figure 4: Cross-dataset transfer of the router trained on HotpotQA.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmark	Agent	Raw	CoT	SC	React Reflect	MAD	Summary
NewsQA	Qwen2.5-7B	60.51 $\pm$ 0.52	59.51 $\pm$ 0.96	58.84 $\pm$ 0.21	59.74 $\pm$ 0.63	59.80 $\pm$ 0.42	60.43 $\pm$ 0.48
	gpt-oss-20B	60.55 $\pm$ 1.45	61.29 $\pm$ 0.66	58.91 $\pm$ 1.35	59.89 $\pm$ 1.02	62.80 $\pm$ 2.15	61.43 $\pm$ 0.78
	Mixtral-8x7B	53.79 $\pm$ 0.99	54.03 $\pm$ 0.84	55.69 $\pm$ 1.23	54.46 $\pm$ 0.66	55.13 $\pm$ 0.51	55.16 $\pm$ 1.05
	Llama-3-8B	55.50 $\pm$ 0.78	56.24 $\pm$ 0.54	57.97 $\pm$ 0.87	56.55 $\pm$ 0.81	57.07 $\pm$ 0.93	55.97 $\pm$ 0.72
HotpotQA	Qwen2.5-7B	59.38 $\pm$ 1.21	58.04 $\pm$ 1.81	58.09 $\pm$ 1.04	56.89 $\pm$ 1.42	56.12 $\pm$ 1.37	57.24 $\pm$ 1.53
	gpt-oss-20B	68.19 $\pm$ 1.37	68.74 $\pm$ 1.39	67.04 $\pm$ 1.02	68.39 $\pm$ 1.26	67.74 $\pm$ 0.98	66.63 $\pm$ 1.14

Appendix

Table 5: F1 scores across five benchmarks for different agents under various prompting strategies. We report mean and standard deviation.

Benchmark	Agent	Raw	CoT	SC	React Reflect	MAD	Summary
NewsQA	Qwen2.5-7B	41.33 $\pm$ 0.58	39.00 $\pm$ 0.00	42.00 $\pm$ 0.00	42.33 $\pm$ 0.58	41.33 $\pm$ 0.58	42.00 $\pm$ 0.00
	gpt-oss-20B	39.80 $\pm$ 2.05	37.33 $\pm$ 1.73	35.00 $\pm$ 2.00	35.67 $\pm$ 1.53	37.11 $\pm$ 1.15	37.67 $\pm$ 1.53
	Mixtral-8x7B	28.33 $\pm$ 0.58	28.00 $\pm$ 1.00	28.67 $\pm$ 0.58	29.00 $\pm$ 0.00	28.00 $\pm$ 1.00	27.33 $\pm$ 0.58
	Llama-3-8B	37.33 $\pm$ 1.15	38.00 $\pm$ 1.00	39.67 $\pm$ 0.58	37.33 $\pm$ 1.15	39.00 $\pm$ 0.00	38.00 $\pm$ 1.00
HotpotQA	Qwen2.5-7B	47.33 $\pm$ 0.58	46.33 $\pm$ 0.58	46.00 $\pm$ 1.00	44.00 $\pm$ 0.00	42.67 $\pm$ 1.15	44.00 $\pm$ 1.00
	gpt-oss-20B	51.79 $\pm$ 2.09	56.15 $\pm$ 0.87	54.00 $\pm$ 1.00	54.67 $\pm$ 1.15	55.67 $\pm$ 1.15	53.00 $\pm$ 1.00

Appendix

Table 6: Exact Match (EM) scores across benchmarks for different agents under various prompting strategies.

Prompt Optimization Ablation
Method	GLEN-Bench		NGQA
Method	F1	EM	F1	EM
KG Router (base)	49.39 $\pm$ 0.81	11.00 $\pm$ 1.00	49.95 $\pm$ 1.29	8.67 $\pm$ 1.53
+PO (Round 1)	50.97 $\pm$ 0.46	11.33 $\pm$ 0.58	50.31 $\pm$ 0.88	9.00 $\pm$ 0.00
+PO (Round 2)	51.74 $\pm$ 0.38	12.00 $\pm$ 1.00	52.99 $\pm$ 1.19	9.33 $\pm$ 0.58
+PO (Round 3)	52.28 $\pm$ 0.86	14.33 $\pm$ 0.58	53.28 $\pm$ 0.16	9.67 $\pm$ 0.58

Appendix

Table 7: Ablation on GLEN-Bench and NGQA. Both benchmarks target nutritional QA but differ in graph density and contextual richness.

Method	HotpotQA $\rightarrow$ 2Wiki		HotpotQA $\rightarrow$ NewsQA		HotpotQA $\rightarrow$ NGQA
Method	F1	EM	F1	EM	F1	EM
EvolveRouter (in-domain)	77.70 $\pm$ 0.13	70.33 $\pm$ 0.58	64.74 $\pm$ 0.77	41.67 $\pm$ 0.47	54.04 $\pm$ 0.60	9.67 $\pm$ 0.58
PO + PO router	57.44 $\pm$ 0.75	47.00 $\pm$ 1.00	59.87 $\pm$ 0.83	40.33 $\pm$ 0.58	45.13 $\pm$ 1.47	4.33 $\pm$ 0.58
$\Delta$ vs. base (%)	$\downarrow$ 26.08%	$\downarrow$ 33.18%	$\downarrow$ 7.53%	$\downarrow$ 3.22%	$\downarrow$ 16.49%	$\downarrow$ 55.23%
PO router	56.28 $\pm$ 0.96	46.33 $\pm$ 0.58	55.05 $\pm$ 0.66	38.33 $\pm$ 0.58	38.43 $\pm$ 1.64	4.33 $\pm$ 1.15
$\Delta$ vs. base (%)	$\downarrow$ 27.57%	$\downarrow$ 34.13%	$\downarrow$ 14.97%	$\downarrow$ 8.02%	$\downarrow$ 28.89%	$\downarrow$ 55.23%

Appendix

Table 8: Cross-dataset transferability of routing and prompt optimization. The router is trained on HotpotQA and evaluated on 2Wiki, NewsQA and NGQA.

Adaptive K Ablation
Method	2Wiki		HotpotQA		NewsQA		TriviaQA		NGQA
Method	F1	EM	F1	EM	F1	EM	F1	EM	F1	EM
KG Router (base)	75.54 $\pm$ 0.44	67.67 $\pm$ 0.58	69.35 $\pm$ 0.56	56.33 $\pm$ 0.58	63.02 $\pm$ 2.44	41.33 $\pm$ 0.58	62.75 $\pm$ 3.69	51.33 $\pm$ 2.51	49.95 $\pm$ 1.29	8.67 $\pm$ 1.53
Fixed K=3	75.49 $\pm$ 0.59	66.67 $\pm$ 0.58	67.08 $\pm$ 1.17	54.00 $\pm$ 1.00	60.92 $\pm$ 0.68	40.67 $\pm$ 0.58	61.60 $\pm$ 0.86	51.00 $\pm$ 1.00	49.76 $\pm$ 0.49	8.67 $\pm$ 0.58
Fixed K=5	76.22 $\pm$ 1.46	67.00 $\pm$ 1.00	69.83 $\pm$ 1.36	56.67 $\pm$ 0.58	62.83 $\pm$ 0.46	41.00 $\pm$ 1.00	62.60 $\pm$ 0.81	52.33 $\pm$ 0.58	48.94 $\pm$ 0.59	7.33 $\pm$ 0.58
Fixed K=10	76.16 $\pm$ 0.81	67.00 $\pm$ 1.00	69.40 $\pm$ 0.88	56.00 $\pm$ 1.00	61.08 $\pm$ 1.38	41.00 $\pm$ 1.00	61.18 $\pm$ 0.76	49.67 $\pm$ 1.15	48.34 $\pm$ 0.31	7.00 $\pm$ 0.00

Appendix

Table 9: Ablation study of adaptive K across five benchmarks. Adaptive K exceeds the best fixed-K setting on every dataset.

Method	2Wiki	HotpotQA	NewsQA	TriviaQA	NGQA
Full ensemble	24	24	24	24	24
Adaptive Avg. K	2.9	2.9	4.2	7.4	3.3
Savings (%)	88%	88%	83%	69%	86%

Appendix

Table 10: Average number of agents queried by Adaptive K compared to the full ensemble (K=24). Savings indicate the percentage reduction in agent calls.

Panel of Figure 5 — Figure 5: Agent role prompts (Part I) for multi-hop QA

Panel of Figure 6 — Figure 6: Agent role prompts (Part II) for multi-hop QA

Panel of Figure 7 — Figure 7: System-level wrapper and output constraints applied to every agent call. The role prompt from Figures 5 – 6 is injected into the <role_prompt> slot.

Panel of Figure 8 — Figure 8: Input template for the rewriter LLM. The template provides the current prompt, aggregated error patterns from router diagnostics, and representative failure cases with their F1 scores to guide targeted prompt refinement.

Panel of Figure 9 — Figure 9: Per-question agent routing snapshots for three examples. Each case shows the question, gold answer, model prediction, and the four highest- and lowest-probability agents with their generated answers.

Panel of Figure 10 — Figure 10: PO case study 1: entity–attribute confusion.

Panel of Figure 11 — Figure 11: PO case study 2: question type misidentification.

Panel of Figure 12 — Figure 12: PO case study 3: distractor entity selection.

LLM Agent Routing

LLM agent routing selects models, tools, skills, or collaboration workflows for each task or step to balance capability, cost, latency, and reliability.

See all 99 papers

EvoRouter: Cost-Efficient Multi-Agent Routing via Insight-Guided On-Policy Distillation
Oct 26, 2026Yitao Xiao, Xu Zhang, Ye Cheng +6LLM Agent Routing Adaptive Model Routing
Beijing University of Posts and Telecommunications, Beijing, China · Fudan University, Shanghai Innovation Institute, Shanghai, China · Nanyang Technological University, Singapore
Experience as a Compass: Multi-agent RAG with Evolving Orchestration and Agent Prompts
Apr 1, 2026Sha Li, Naren RamakrishnanRetrieval-Augmented Generation Multi-Agent Orchestration
Virginia Tech
CERA-MoA: Co-Evolving Routing Mechanisms with Continually Learning LLM Agents
Sep 16, 2026Jiaxuan Jiang, Liyuan He, Zhixuan FangContinual Learning for LLM Agents Multi-Agent Systems
IIIS, Tsinghua University, Beijing, China · Shanghai Qi Zhi Institute, Shanghai, China · School of Artificial Intelligence, Shanghai Jiao Tong University, Shanghai, China

Oct 26, 2026J/K move · Enter open · S save

EvoRouter: Cost-Efficient Multi-Agent Routing via Insight-Guided On-Policy Distillation

Yitao Xiao, Xu Zhang, Ye Cheng, Shaoyong Guo+5

Beijing University of Posts and Telecommunications, Beijing, China · Fudan University, Shanghai Innovation Institute, Shanghai, China · Nanyang Technological University, Singapore

LLM Agent Routing Adaptive Model Routing Cost-Aware Inference

Open paper AskPDF arXiv

Serving web queries at scale with multi-agent systems requires jointly configuring large language models, collaboration modes, agent counts, interaction rounds, and skills. However, the resulting configuration space grows combinatorially, while sparse execution rewards provide limited fine-grained supervision for interdependent planning decisions. We propose EvoRouter, a self-evolving multi-agent routing framework driven by insight-guided on-policy distillation. A dedicated expert periodically synthesizes performance-cost feedback from configuration trajectories across tasks into reusable conditional routing insights about capability requirements, returns from resource scaling, and interactions among configuration choices. A privileged teacher combines these evolving insights with current execution feedback to provide dense token-level supervision for the router's own planning trajectories through on-policy distillation. Cost-aware reinforcement learning jointly optimizes task performance and computational cost. Together, these training signals internalize execution insights into the routing policy. The updated policy generates new trajectories that support subsequent insight extraction, forming an execution-driven self-improvement loop. We evaluate EvoRouter on 19 in-domain datasets spanning five domains and two out-of-domain benchmarks. EvoRouter achieves an average in-domain accuracy of 68.69%, outperforming the strongest routing baseline by 7.23 percentage points while reducing inference compute cost by 50.95%. Our code is open-sourced at https://github.com/CenYangtze/EvoRouter.

Abstract

LLM Agent Routing

Explore similar work

EvoRouter: Cost-Efficient Multi-Agent Routing via Insight-Guided On-Policy Distillation

Experience as a Compass: Multi-agent RAG with Evolving Orchestration and Agent Prompts

CERA-MoA: Co-Evolving Routing Mechanisms with Continually Learning LLM Agents