COVER: Identifiable Evaluation of Coalition Routing

Raghul Sugumar; Amrit Gopinath

cs.AIAug 28, 2026

COVER: Identifiable Evaluation of Coalition Routing

Authors: Raghul Sugumar, Amrit Gopinath

Organizations: Sri Sivasubramaniya Nadar College of Engineering

Abstract

When a multi-agent system changes its team, it also changes the messages and final answer it produces, so an end-to-end accuracy gap does not by itself identify a routing effect. We introduce method, an evaluation contract that fixes a public information boundary, downstream stack G, and finite legal team family before outcomes are generated. Complete coverage identifies exact finite-benchmark oracle regret conditional on that stack. For any finite collection of frozen policies, executing the union of their distinct selected teams is the minimal assumption-free support for every pairwise policy contrast, though not for absolute oracle regret. Two controlled tables with source-ID-disjoint splits test the instrument. On MuSiQue-12, a pre-specified privileged positive control improves regret from 0.532 to 0.402; a later public-interface control reaches 0.424 versus 0.554 but is retrospective. On HotpotQA-4, a pre-specified public direct scorer improves regret from 0.313 to 0.110. In fixed-stack Llama execution, verified route regret improves by 0.190, while the raw-answer gain is 0.010 with an interval crossing zero. A five-family ToolSandbox variant-shift validation exhaustively evaluates 16 declared teams on 14 untouched task variants (224/224 valid rows): the declared-family oracle reaches 0.768 safe-evidence completion, while the prospectively frozen router gets 0.637 (regret 0.131), failing the predeclared 0.10 criterion. A later retrospective comparator reaches 0.655, matching all-workers with 4.57 versus 5.00 workers on average. Thus COVER exposes selection headroom without manufacturing a routing win. A crossed-stack diagnostic shows absolute scores depend on G but finds no detectable router-by-finalizer interaction. COVER is an auditable measurement methodology, not a claim of stack-invariant or universal agent-routing superiority.

Figures & tables

Panel of Figure 1 — Figure 1: COVER changes only the selected coalition. Orange information is unavailable when the route is chosen.

Stage	Available	Deliberately unavailable
Route selection	task text, public cards, declared budget	private evidence, answers, outcome table, required team
Worker execution	selected worker’s private evidence	other workers’ private evidence
Finalization	canonical selected messages	router identity and unselected messages
Offline scoring	frozen table values and route files	any held-out training outcome

Table 1: Information visible at each point in a COVER evaluation.

Coverage regime	Interventions/task	Identified quantity
Complete finite family	all legal teams	exact finite-benchmark oracle regret
Precommitted sampled family	declared sampled teams	sampled-action regret or bounds, not an oracle
Frozen route union	distinct selected teams	all pairwise policy contrasts; inclusion-minimal

Table 2: COVER’s compute/identification regimes. Costs are interventions per task; only the first regime identifies absolute finite-benchmark oracle regret.

Instance	Held-out tasks	Legal teams/task	Construction purpose
MuSiQue-12	500	220 size-three teams	Tests globally coherent components amid distractor components
HotpotQA-4	300	4 size-three teams	Tests direct team scoring without a partition decoder

Table 3: The two intervention-complete controlled instances. A task, rather than a card pair or intervention, is the unit of inference.

Study	Tasks	Result	Interpretation
MuSiQue-12 public	500	0.424 vs 0.554	Deployment-relevant public interface; retrospective control
MuSiQue-12 privileged	500	0.402 vs 0.532	Pre-specified positive control of instrument sensitivity
HotpotQA-4	300	0.110 vs 0.313	Direct set scoring is a useful bias in a four-way decision

Table 4: Controlled findings and their evidential status. Regret is exact over each declared offline family conditional on its frozen stack; exact scoring does not make a privileged policy deployable or a retrospective policy confirmatory.

Panel of Figure 2 — Figure 2: Controlled public-interface comparisons. The MuSiQue pair is retrospective; the HotpotQA pair is pre-specified. Regret is exact within each declared action space; scales are not compared across instances.

Family	Router	Verified evidence complete	Raw answer exact	Raw route regret
Llama	Unified-COVER	81.67%	36.33%	0.050
Llama	leave-one-out	62.67%	35.33%	0.060

Table 5: Frozen genuine execution. Executed-route regret is calculated only on the union of the frozen selected routes, not over all possible teams.

Policy or reference	Completion	Regret	Mean workers
Per-task declared-family oracle	.768	—	—
All workers	.655	.113	5.00
Development-best fixed team	.655	.113	5.00
Learned value router	.655	.113	4.57
ToolBench-style card retriever	.655	.113	5.00
Frozen public capability router	.637	.131	3.00

Table 6: Five-family ToolSandbox variant-shift validation (14 tasks, 16 declared coalitions/task). Completion is the official safe-evidence endpoint; lower regret is better. “Style” rows are interface-level adaptations, not exact published-system reproductions.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Field	Router at selection time	Worker/finalizer after selection
Question and public capability cards	yes	yes
Private passages and evidence units	no	selected worker only
Gold answer, required team, component ID	no	no
Held-out intervention value	no	evaluation only
Finalizer identity and canonical message order	fixed, not routed	fixed

Appendix

Table 7: Public/private boundary used in both controlled instances.

Study	Comparator	COVER	Improvement	Status
MuSiQue-12 binary	calibrated graph 0.5320	0.4020	0.1300	positive control
HotpotQA-4 binary	leave-one-out 0.3133	0.1100	0.2033	primary
Llama verified route regret	leave-one-out 0.2900	0.1000	0.1900	primary

Appendix

Table 8: Originally specified offline comparisons. Lower regret is better. Holm correction applies to these three tests; the MuSiQue row is a privileged positive control, not deployment evidence.

Check	Result	Interpretation
Same local score, no partition	0.4660 vs 0.4020; gap 0.0640, CI [0.0400,0.0880]	global completion contributes beyond fixed local scores
Graded evidence coverage	both offline advantages remain positive	conclusion is not only a proof-gate effect
Outcome-supervised public interface	partition 0.4240 vs graph 0.5540; no-partition 0.4540	train outcomes and public text suffice; retrospective, no latent membership labels
Zero-shot Llama public router	MuSiQue regret 0.4860 (500 tasks)	external practitioner comparator; between public partition and public graph
GPT-OSS strict 300-task rerun	raw gain 0.0433, CI [0.0133,0.0733]	secondary matched family support
GPT-OSS source-disjoint 1k	raw gain 0.0870, CI [0.0640,0.1110]	late prospective provider-pipeline confirmation

Appendix

Table 9: Attribution and robustness checks. All rows are secondary and unadjusted.

Worker messages	Finalizer	Leave-one-out	Unified-COVER	Gain [95% CI]
Llama	Llama	.4833	.5000	.0167 [ $-.0067$ ,.0400]
Llama	GPT-OSS	.5767	.6000	.0233 [ $-.0067$ ,.0533]
GPT-OSS	Llama	.4833	.5267	.0433 [.0133,.0733]
GPT-OSS	GPT-OSS	.5533	.5900	.0367 [.0033,.0700]

Appendix

Table 10: Completed 300-task

2\times 2

worker-message/finalizer diagnostic. Values are raw exact accuracy; gain is Unified-COVER minus leave-one-out with a task-bootstrap 95% interval.

Pool / teams	Graph	Pairwise	Local	Same-18D HGB	Same-18D Ridge	COVER	Gain/local
8 / 56	.2133	.2108	.1908	.3300	.3375	.1750	.0158
10 / 120	.2833	.2700	.2367	.3783	.3792	.2200	.0167
12 / 220	.3283	.3100	.2867	.4133	.3933	.2508	.0358

Appendix

Table 11: Frozen partition-free secondary reanalysis (400 existing-target tasks; lower linear-coverage regret is better).

Activity	Tasks	Raw gain	Status
Original-answer MuSiQue, Llama	300	0.1133 [0.0700,0.1567]	secondary, different construction/comparator
Original-answer MuSiQue, GPT-OSS	140	0.0786 [0.0143,0.1500]	outcome-blind quota checkpoint
Strict HotpotQA GPT-OSS rerun	300	0.0433 [0.0133,0.0733]	secondary same-task replication
Source-disjoint HotpotQA GPT-OSS	1,000	0.0870 [0.0640,0.1110]	late prospective confirmation
Repeated GPT-OSS subset	120 $\times$ 2 repeats	0.0694 [0.0139,0.1278]	secondary stability check

Appendix

Table 12: Retained post-Llama raw-output provenance. All

p

values are unadjusted.

#	Paper	Code	Object
1	DyLAN	T	Task-conditioned agent team followed by dynamic collaboration
2	GPTSwarm / Language Agents as Optimizable Graphs	I	Graph connectivity, with separate node/prompt optimization
3	MacNet	I	Communication topology and agent scale
4	AgentPrune	I	Spatial/temporal communication-message graph
5	AgentDropout	J	Agents and communication edges jointly
6	MasRouter	J	Collaboration mode, agent roles, and LLM choice

Appendix

Table 13: Frozen 30-paper targeted audit. “Object” names the main selected or optimized object used for coding.

AI Agent Evaluation

AI agent evaluation measures whether tool-using systems complete tasks reliably, safely, and efficiently across interactive settings.

See all 521 papers

Aug 5, 2026

RouteGuard: Certifying Routing Gain in LLM Multi-Agent Systems When Complementarity Is Not Enough

Multi-agent LLM systems route among model-backed advisors, yet a deployer rarely knows before shipping whether routing will help at all. Prevailing routers optimize a gate's AUC and presume that advisor complementarity suffices. We show that neither determines the deployable gain. We introduce RouteGuard, a deployment-certification framework. Routing gain decomposes as

G = πΔ_E

, and the achievable gain is governed by a conditional-regret functional

Φ

, not by AUC. A finite-sample certification bracket comes with a matching Le Cam lower bound, constant-sharp over the fixed-activity class, and a robustness phase transition. On two benchmarks the framework acts as a guardrail. On RouterBench (11 cross-family models) the verdict depends on the sampling unit: the protocol certifies a gain over GPT-4 under prompt-level sampling and withholds it under workload-cluster resampling, because the gain rests on 3 of 86 workload cells. On OpenRCA (three Gemini advisors) the advisors are statistically redundant: the realized oracle sits at or below the independence baseline in all pools we tested (221 RouterBench pools and three OpenRCA distributions), so the protocol correctly refuses to certify. A pre-registered semi-synthetic control confirms calibration: the protocol certifies a genuine gain once

m \ge m^\star

and does not certify a true null. Code and frozen artifacts will be released with the published version.

Anchen Sun, Kaiqi Yang

Department of Electrical and Computer Engineering, University of Miami, Coral Gables, FL 33146 USA · Department of Mathematics, University of Miami, Coral Gables, FL 33146 USA

Multi-Agent LLM Systems AI Agent Benchmarks LLM Routing LLM Agent Routing

Ask PDF

Jun 27, 2026

Multi-Agent Routing as Set-Valued Prediction: A WildChat Benchmark and Cost-Aware Evaluation

Tool and agent routing from natural-language prompts is naturally a set-valued prediction problem: a single query may require multiple agents, while over-selection increases execution cost. The benchmark introduced here is derived from WildChat and contains 3,000 prompts over a fixed 12-agent catalog, with AI-assisted heuristic labels under a fixed schema and controlled rebalancing for multi-label evaluation. The evaluation protocol combines set-level metrics (Precision, Recall, F1, Jaccard, and Exact Match), latency, an execution-oriented capability-coverage simulation, and a constrained weighted-routing setting based on ordinal agent-cost tiers. Compared methods include nearest-neighbor matching, linear multilabel classification, dependency-aware baselines, a fine-tuned encoder, deterministic weighted post-scoring via Weighted Agent Routing (WAR), and a zero-shot LLM baseline. Results show that supervised routers substantially outperform nearest-neighbor and zero-shot LLM routing. The fine-tuned encoder achieves the strongest unconstrained set accuracy, while the linear multilabel model provides the strongest practical baseline. In the constrained setting, the weighted routing layer improves utility when applied on top of strong supervised scorers, with the largest gain observed for Encoder+WAR. Overall, the benchmark and evaluation protocol support reproducible study of accuracy-cost trade-offs in fixed-catalog multi-agent routing.

Ananto Nayan Bala, Faisal Muhammad Shah

Ahsanullah University of Science and Technology Dhaka, Bangladesh

Multi-Label Classification AI Agent Benchmarks Set-Valued Prediction LLM Agent Routing

Ask PDF

Aug 14, 2026

LLMs Can Predict Failure Risk, But Struggle to Predict Which Collaboration Protocol Pays Off: Cost-Aware Protocol Routing Across Reasoning Tasks

Multi-agent large language model (LLM) systems can improve reasoning by spending more computation, but deployment requires deciding when extra collaboration is worth its cost. We isolate this decision by running every problem under four protocols while holding the solver fixed within each setting: direct solving (Baseline), iterative self-correction (Single), planner-executor-reviewer collaboration (PER), and multi-agent deliberation (Broadcast). The primary benchmark comprises 4,181 competition-level math problems; paired robustness checks cover four benchmarks spanning competition math, biology, and broader science with two solver families. Across fixed policies, trained routers, and frozen LLM routers, conservative policies under-escalate, whereas higher-solve frozen routers often over-escalate. A post-answer, pre-collaboration gpt-oss-120b probe ranks Baseline failures with 0.8847 AUROC (4,151 parseable cases; 95% CI [0.8732, 0.8955]). The same score remains informative for predicting whether any collaboration helps (0.7683 AUPRC), but is much weaker for identifying PER- or Broadcast-specific value (0.1674 and 0.1041 AUPRC). Separately, the pre-answer self-confidence gate reaches 78.0% solve at 45K tokens, compared with 73.8% at 71.3K for a frozen gpt-oss-120b router and 92.4% for a retrospective fixed-order oracle. Across 10 paired model-condition settings, the oracle adds 23.2-58.3 points of retrospective coverage over Baseline, but protocol profiles vary by task. In the six settings with held-out router evaluations, oracle gaps remain 18.5-28.9 points. Confidence can therefore support initial escalation, while protocol-specific cost-aware routing remains unresolved.

Chih-Hsuan Yang, Jingyan Jiang, Cheng-Hau Yang +4

Argonne National Laboratory, Lemont, IL, USA · Oregon State University, Corvallis, OR, USA

LLM Agent Routing Efficient Language Model Reasoning Multi-Agent Collaboration Multi-Agent Systems

Ask PDF

Abstract

AI Agent Evaluation

Explore similar work

RouteGuard: Certifying Routing Gain in LLM Multi-Agent Systems When Complementarity Is Not Enough

Multi-Agent Routing as Set-Valued Prediction: A WildChat Benchmark and Cost-Aware Evaluation

LLMs Can Predict Failure Risk, But Struggle to Predict Which Collaboration Protocol Pays Off: Cost-Aware Protocol Routing Across Reasoning Tasks