PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2604.05149v1cs.CL

TL;DR

Existing routing methods leave agent configurations fixed and often impose rigid collaboration sizes. EvolveRouter jointly refines prompts and graph-based routing in a closed loop, then adapts the number of queried agents using router-weighted agreement. Across five QA benchmarks, it consistently improves over strong routing baselines in F1 and EM, with analyses supporting both refinement and adaptive collaboration.

  • Problem

    Prior routing methods optimize over fixed agent behavior and rigid participation schemes, limiting adaptive multi-agent question answering.

  • Method

    EvolveRouter couples graph-based query routing with diagnostic-guided prompt refinement and sequential inference that stops when router-weighted answer agreement is sufficient.

  • Results

    Across five QA benchmarks, EvolveRouter consistently outperforms strong routing baselines in both F1 and EM.

  • Takeaways & Limitations

    Routing-guided agent selection and prompt optimization reinforce one another, while adaptive collaboration improves performance beyond the strongest single agent.

Abstract

from arXiv · show

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.

1 Introduction

Existing routing methods select among fixed agent configurations or use rigid collaboration schemes, while EvolveRouter jointly refines agents and adapts collaboration size per query.

  • Motivation: Agent quality varies substantially with task, backbone, and prompt context, so no single configuration is consistently optimal.Figure 1 evaluates per-agent F1 across six roles and three controlled dimensions.
  • Limitations of Existing Routing: Prior routing methods optimize which agent to invoke while leaving agent behavior fixed, limiting collaboration gains when configurations are suboptimal.Instruction variations can substantially change performance, particularly in moderate- and small-scale agent settings.
  • Limitations of Existing Routing: Existing collaboration schemes either select one agent or aggregate a fixed pool, risking missed expertise, unnecessary computation, or degraded performance from irrelevant agents.These schemes do not adapt which agents participate, how many participate, or their specialization for each query.
  • EvolveRouter: EvolveRouter couples query-aware routing with targeted instruction refinement in a closed-loop process that jointly improves routing and agent quality.Router diagnostics identify weak roles and guide candidate revisions, while refined agents provide cleaner supervision for later router training.
  • EvolveRouter: The method sequentially invokes router-ranked agents and uses router-weighted answer agreement to determine the effective collaboration size for each query.This replaces single-agent selection or fixed-pool aggregation with adaptive collaboration.
  • Results: Across five QA benchmarks, EvolveRouter consistently outperforms strong routing baselines, with analysis supporting both closed-loop refinement and adaptive collaboration.The reported evaluation covers both F1 and exact match.

2 Problem Formulation

EvolveRouter represents queries, agents, and contextual entities as knowledge graphs, learns soft query-dependent routing distributions, and jointly optimizes routing with prompts while adapting inference-time agent budgets.

  • 2.1 Setup and Routing Objective: The agent pool contains 24 agents formed by crossing four backbone LLMs with six prompting roles, each carrying its own prompt.Each agent produces an answer by calling its backbone with its prompt.
  • 2.1 Setup and Routing Objective: The router learns a query-dependent distribution over agent suitability because effective reasoning depends on queries, agents, contextual entities, and their relations.This motivates representing each QA instance as a typed knowledge graph.
  • 2.1 Setup and Routing Objective: The knowledge graph includes query, agent, and entity node sets, with typed edges encoding relations used for routing.The table compares graph statistics across multi-hop, direct, and domain-specific QA benchmarks while fixing agent and query-node counts.
  • 2.1 Setup and Routing Objective: The training target is a soft distribution derived from agents’ token-level F1 scores, and router training minimizes KL divergence to that target.Soft supervision represents graded agent suitability rather than selecting only one best agent.
  • 2.1 Setup and Routing Objective: At test time, router outputs are used to assemble final predictions through weighted majority voting.The router therefore supplies both agent suitability estimates and weights for aggregation.
  • 2.2 Joint Optimization Objective: Unlike the fixed-pool formulation, EvolveRouter jointly optimizes the prompt set and makes the inference-time agent budget query-adaptive.Prompt changes alter agent performance and therefore reshape the router’s supervision.
  • 2.2 Joint Optimization Objective: Because prompts are discrete and agent scores require black-box inference, optimization alternates between router training with fixed prompts and diagnostic-guided refinement of weak prompts.The router is retrained on updated targets after prompt refinement.
  • 2.2 Joint Optimization Objective: The overview combines knowledge-graph routing, diagnostic-guided prompt rewriting, and sequential agent querying until router-weighted agreement exceeds τ.This pipeline implements adaptive collaboration at inference time.

3 Methodology

EvolveRouter combines graph-based routing, diagnostic-driven prompt refinement, and router-weighted answer agreement to adapt both agent quality and collaboration size during inference.

  • Router Training and Diagnostics: RouterGNN represents each QA instance as a heterogeneous graph and produces query-dependent routing scores over agents.The graph uses query, agent, and entity nodes, with type-aware message passing and a final distribution pθ(a | q, G).
  • Router Training and Diagnostics: Training executes all agents, converts their F1 scores into soft supervision targets, and collects failures, routing weights, performance summaries, and cache information for refinement.These diagnostics identify agent weaknesses and provide evidence for later prompt updates.
  • Closed-Loop Prompt Refinement: Prompt refinement targets roles that underperform across multiple backbones, prioritizing agents with poor F1 but substantial router weight.The priority score combines severity, defined as 1 − F1, with average learned routing weight, while a base coefficient prevents vanishing priority.
  • Closed-Loop Prompt Refinement: Candidate rewrites preserve the role’s reasoning strategy and output format, then undergo targeted validation and conservative acceptance checks.Candidates are evaluated on failure-centered validation subsets; accepted rewrites must avoid significant regression and non-negative net sample-level degradation.
  • Router Update: After accepted prompt changes, the router is fine-tuned from the previous checkpoint, preserving accumulated routing knowledge while reusing cached outputs for unchanged agents.This update adapts routing to modified agents without retraining from scratch.
  • Adaptive Inference via Answer Agreement: At inference, agents are queried in router-ranked order and weighted answer agreement determines when to stop, producing a query-specific collaboration size.The method stops once agreement exceeds τ after at least kmin agents, subject to kmax; easy cases terminate early and harder cases receive a larger budget.

4 Experiments

Experiments across five QA benchmarks evaluate EvolveRouter’s routing, prompt refinement, adaptive collaboration, transfer, and efficiency. EvolveRouter consistently outperforms practical routing baselines while reducing agent calls and benefiting from targeted prompt optimization.

  • Main Results: EvolveRouter improves over the best structure-aware baseline on all five benchmarks in both F1 and EM.The largest gain is on TriviaQA: +7.08 F1 and +8.67 EM over AgentRouter.
  • Main Results: EvolveRouter outperforms the Best Agent baseline on every benchmark, indicating that routed collaboration contributes complementary information after prompt refinement.Prompt optimization and multi-agent routing are reported as reinforcing components.
  • Ablation Studies: Prompt optimization yields cumulative gains of +1.31% F1 on 2Wiki, +3.75% on HotpotQA, +9.21% on TriviaQA, and +6.67% on NGQA.Each refinement round improves performance on most datasets, with the largest gains on TriviaQA and NGQA.
  • Ablation Studies: Adaptive K improves F1 by +1.52% on 2Wiki, +1.53% on HotpotQA, +1.25% on NewsQA, and +0.70% on NGQA relative to the base.Its effect is smaller than prompt optimization on every dataset, but the components are complementary through improved answer agreement.
  • Ablation Studies: No single global K is best across datasets, while Adaptive K exceeds the best fixed-K setting on every benchmark by determining K per query through answer agreement.Cross-dataset router transfer is weak, although optimized source-task prompts can partially mitigate degradation.
  • Analysis: Accepted prompt rewrites preserve each role’s core strategy while adding best-guess answering, entity tracking, numbered steps, or domain-specific formatting.Diagnostic-guided selection prioritizes agents using both poor performance and router reliance rather than lowest F1 alone.
  • Analysis: Checkpoint resuming outperforms retraining the router from scratch, with F1 gaps of +0.75 on 2Wiki, +1.88 on HotpotQA, +0.92 on NewsQA, and +4.92 on NGQA.Resuming preserves routing patterns for unchanged agents while adapting to modified ones.
  • Efficiency: Adaptive K reduces average agent calls from 24 to 2.9–7.4 across benchmarks, a 69–88% reduction while maintaining or improving F1.GNN training takes under five minutes on one GPU, and refinement rounds re-query only the 2–3 modified agents.

5 Conclusion

The paper concludes that EvolveRouter co-evolves routing and agent quality through diagnostic-guided prompt revision and answer-agreement stopping. Across five QA benchmarks, it reports consistent gains over routing baselines while identifying preserved routing knowledge as important for refinement.

  • Conclusion: EvolveRouter uses router diagnostics to guide targeted prompt revisions, while improved agents provide cleaner supervision for subsequent router training.An answer-agreement stopping rule adapts the number of queried agents per query.
  • Conclusion: Experiments on five QA benchmarks show consistent gains over strong routing baselines in both F1 and EM.The conclusion also reports advantages for routing-guided agent selection over naive lowest-F1 heuristics.
  • Conclusion: Routing knowledge must be preserved across refinement rounds rather than relearned from scratch.The paper identifies dynamic agent-pool expansion and automated agent design as future directions.
  • Motivation: Prior routing methods generally assume a fixed agent pool, motivating a framework that jointly improves routing and agent quality.The paper builds on graph-based routing while addressing prompt sensitivity and collaboration structure.

B Additional Method Details

Prompt refinement targets consistently weak agent roles, validates constrained rewrites, and updates routing iteratively while preserving useful knowledge.

  • Target selection: Role-level filtering retains agents that underperform across multiple backbones, reducing attention to isolated backbone-specific failures.The filter starts at three backbones and relaxes to two or one if necessary.
  • Target selection: Priority combines agent severity with router weight, prioritizing agents that both underperform and remain important to routing.The score uses severity(a) · (α + w̄(a)), with α = 0.3 in the implementation.
  • Prompt rewriting: The refinement loop generates constrained candidate rewrites from failure evidence, evaluates them on targeted validation data, and retains the best-performing candidate.Rewrites preserve the role’s core reasoning strategy and output format while addressing diagnosed weaknesses.
  • Validation and acceptance: A rewrite passes when it avoids excessive mean-F1 regression, changes at least one sample, and produces no net degradation.The gate permits small mean drops when broader sample-level improvements offset them.
  • Router updates: Accepted prompt revisions update the router from the preceding checkpoint, with seeded caches and regression checks supporting chained multi-round optimization.Updates are reverted when validation F1 falls more than 0.03 below the previous checkpoint, and improvement usually saturates after 2–3 rounds.

C.1 Benchmarks

The evaluation spans multi-hop, long-context, noisy-evidence, health-domain, and agent-routing settings, using established heuristic, training-free, adaptive, and structure-aware baselines.

  • Benchmarks: HotpotQA and 2WikiMultihopQA test multi-hop evidence aggregation, with the latter requiring compositional reasoning across distinct Wikipedia articles.HotpotQA includes annotated supporting facts, while 2Wiki covers comparison, bridge, and inference patterns.
  • Benchmarks: NewsQA and TriviaQA stress routing under long, scattered, noisy, or weakly overlapping evidence.NewsQA includes unanswerable and ambiguous items, while TriviaQA pairs independently authored questions and evidence documents.
  • Benchmarks: NGQA evaluates health-domain reasoning over nutrition, medical conditions, dietary constraints, and three contextual-complexity tiers.Its setting tests whether routing can handle specialized and varied user profiles.
  • Baselines: The study compares heuristic, training-free, adaptive, and structure-aware routing methods, alongside six prompting strategies and an Oracle upper bound.The adaptive group includes LLM-Blender, HybridLLM, KNN Router, and MLP Router; structure-aware methods include GraphRouter and AgentRouter.

C.3 Training Details

Training uses heterogeneous query-agent graphs, multiple agent backbones and roles, prompt refinement from prior checkpoints, and adaptive inference to reduce calls.

  • Data and evaluation: Each benchmark contributes 500 training, 100 validation, and 100 test instances, evaluated with token-level F1 and Exact Match over three seeds.Instances are transformed into heterogeneous knowledge graphs with query, entity, relation, and agent information.
  • Router: RouterGNN uses two HGTConv layers, 256-dimensional hidden states, dropout, normalization, and an MLP routing head with an auxiliary question-type predictor.The architecture operates on query and agent representations after heterogeneous message passing.
  • Optimization: The router is optimized with Adam at learning rate 10^-4 and early stopping after five validation epochs without F1 improvement.Training runs for at most 20 epochs and includes soft-target, label-smoothing, and entropy regularization.
  • Prompt and agent setup: The 24-agent pool combines four backbones with six roles, while prompt-aware caching preserves unchanged outputs and invalidates modified prompts.Each refinement round samples three candidate rewrites, and agents with three consecutive failed rewrites are frozen.
  • Computational cost: Adaptive K reduces inference calls from 24 agents to 2.9–7.4 on average, yielding a 69–88% reduction while maintaining or improving F1.Stage 1 requires 12,000 LLM calls, while each refinement round modifies only 2–3 agents.

D Additional Experiments

Additional experiments show strong ablation gains on nutritional QA, task-specific routing transfer, and partial cross-task benefits from prompt optimization.

  • Ablation: NGQA uses a denser heterogeneous graph incorporating food prices, socioeconomic indicators, and dietary profiles across nine node types and eleven relation types.This setting provides a distinct test of routing under richer contextual information.
  • Ablation: PO yields cumulative gains of ↑5.85% F1 on GLEN-Bench and ↑6.67% on NGQA after three rounds, while full EvolveRouter achieves the best result on both datasets.Adaptive K contributes ↑8.24% on GLEN-Bench but only ↑0.70% on NGQA.
  • Transferability: Routing transferred from HotpotQA to 2Wiki, NewsQA, and NGQA underperforms in-domain training by −27.6%, −15.0%, and −28.9% F1, respectively.The degradation is especially severe on NGQA, where domain-specific reasoning patterns diverge most from HotpotQA.
  • Transferability: HotpotQA prompt optimization partially recovers transferred-router performance on NewsQA and NGQA, but yields only marginal improvement on 2Wiki.F1 rises from 55.05 to 59.87 on NewsQA and from 38.43 to 45.13 on NGQA.

D.3 Ablation study of adaptive K

The ablation shows that a query-dependent collaboration size outperforms any single fixed K across benchmarks while substantially reducing agent calls relative to the full ensemble.

  • Adaptive K exceeds the best fixed-K setting on every dataset, confirming that collaboration size should vary across queries and benchmarks.No single fixed K is best everywhere: K=5 leads on 2Wiki and HotpotQA, while K=3 leads on NewsQA and NGQA.
  • +1.52% F1 on 2Wiki, +1.53% on HotpotQA, +1.25% on NewsQA, and +0.70% on NGQA versus the KG Router base.
  • +6.51% EM on TriviaQA versus the KG Router base, a larger gain than the reported F1 improvements on the other benchmarks.
  • Adaptive K queries 2.9–7.4 agents on average, reducing agent calls by 69–88% compared with the full ensemble of K=24.Savings are largest on 2Wiki and HotpotQA and smallest on TriviaQA because answer diversity requires more agents before consensus.

F Case Study

The case studies show how routing and targeted prompt refinement operate in practice: the router prioritizes agents producing correct answers, while refined prompts correct distinct reasoning failures without changing core strategies.

  • Agent routing examples: Routing snapshots show high router weights for agents producing correct answers and lower weights for agents generating incorrect or noisy outputs.Each example displays the question, gold answer, prediction, and the four highest- and lowest-probability agents with their answers.
  • Prompt optimization case studies: Prompt refinement corrected three failure modes: entity–attribute confusion, question-type misidentification, and distractor-entity selection.The revised prompts added targeted instructions such as explicit entity tracing and answer-precision checks.
  • Agent role prompts: The framework uses six role-specific prompts spanning Raw, CoT, Self-Consistency, Multi-Agent Debate, ReAct-Reflection, and Multi-Agent Summary strategies.
  • System wrapper and output constraints: A shared system wrapper standardizes agent outputs and applies answer constraints, with each role prompt inserted into the wrapper’s role-prompt slot.
  • Prompt optimization case studies: The rewriter receives the current prompt, router-derived error patterns, and representative failure cases with F1 scores to produce targeted refinements.
Loading 2604.05149v1…