AI Research

COVER: Identifiable Evaluation of Coalition Routing | AI Research

Key Takeaways

COVER: Identifiable Evaluation of Coalition Routing introduces a methodology to measure the performance of multi-agent systems when they select different tea...
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.

Paper AbstractExpand

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.

COVER: Identifiable Evaluation of Coalition Routing introduces a methodology to measure the performance of multi-agent systems when they select different teams of workers to solve a task. The authors, Raghul Sugumar and Amrit Gopinath, argue that current end-to-end accuracy metrics are insufficient because changing a team also changes the messages and final answers produced, making it difficult to isolate the effect of the routing decision itself.

The Evaluation Contract

The authors propose an "evaluation contract" called COVER to fix the variables that typically confound routing experiments. To use this method, researchers must declare a finite set of legal teams before generating outcomes, define a public information boundary for the router, and keep the downstream stack—including workers, communication protocols, and finalizers—identical across all tested routes. By executing every legal team within this fixed environment, researchers can calculate exact oracle regret, which represents the gap between the chosen route and the best possible team for a given task.

Minimal Support for Comparison

When full enumeration of all possible teams is too expensive, the paper provides a theorem for "minimal support." It establishes that for comparing a finite collection of frozen routing policies, researchers only need to execute the union of the teams those specific policies select. This approach identifies pairwise differences between routers without requiring a model for unobserved teams. However, the authors note that this minimal approach does not provide the absolute oracle regret that complete enumeration offers.

Experimental Findings

The researchers tested COVER using controlled tables in multi-hop question answering and a ToolSandbox environment. In the ToolSandbox study, which evaluated 16 declared teams across 14 task variants, a prospectively frozen router achieved a completion score of 0.637, failing to meet the authors' pre-declared regret criterion of 0.10. The study showed that while some retrospective comparators could match the performance of using all available workers, they did so by selecting larger teams, suggesting that the "headroom" for better routing is often smaller than it appears in less controlled settings.

Limitations and Scope

The authors emphasize that COVER is an auditable measurement methodology rather than a claim of universal routing superiority. It is designed to identify the quality of coalition selection under a specific, declared protocol. The paper explicitly warns that absolute scores depend on the downstream stack (G) and that the methodology does not account for stochastic deployment utility, which would require repeated executions that are not identified by a single provider call. Furthermore, the authors clarify that their results are specific to the constructed environments tested and do not serve as a general-purpose architecture for all multi-agent systems.

Comments (0)

No comments yet

Be the first to share your thoughts!