- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper studies how to route a task to one competent AI agent when there are many candidate agents, some of which may exaggerate their abilities. It estimates agent competence from peer-observed, verifier-checked test tasks rather than self-descriptions. It aggregates the estimates in a hierarchy of small cohorts, periodically audits potentially dishonest reports, and uses the hierarchy to select an agent for each task family.
Critical strengths
-
The paper identifies a relevant challenge for future agent ecosystems. Agent descriptions are not necessarily reliable indicators of competence, especially when agents have incentives to exaggerate their capabilities. Using experimentally verified task outcomes is a sensible direction for improving task allocation.
-
The proposed design is simple and operationally appealing. Cohort-based skill estimates, hierarchical aggregation, selective re-verification, and report auditing form a concrete mechanism for efficient task routing.
-
The experiments cover many comparison methods and settings. The paper tests ten agent frameworks and a broad set of routing algorithms across live executions, recorded benchmarks, and simulations.
Critical weaknesses
-
The claimed evaluation at 100,000 live agents is a bit misleading as evidence of agent diversity. Appendix A explains that the live population is built from only seven base models and artificially assigned specializations. For any task family, there are at most fourteen distinct agent behaviors, regardless of population size. Agents with the same signature are exact clones, and their outputs are memoized.
-
The agent specializations are artificially engineered rather than naturally emerging. To make an agent weaker outside its specialties, the benchmark withholds a worked example, the family description, and a Python tool on those tasks. This imposes competence differences by construction and may make the skill matrix easier to learn than those of real independently developed agents with overlapping, context-dependent capabilities. The results do not establish that MIDIAN would work equally well when specialization arises from differences in actual knowledge, tools, policies, and performance (Section 4.1, Appendix A).
-
The benchmark supplies the task family, bypassing an essential part of agent discovery. MIDIAN assumes that every incoming task already belongs to one of sixteen known families, and agents are routed using a precomputed competence score for that family. In an open agent ecosystem, translating an unseen, ambiguous, or compositional user request into the appropriate capabilities is itself a major challenge. The paper does not evaluate task-family inference, unseen families, or routing below the family level, so its setting is substantially simpler than the proposed application.
-
The method relies on cheap and trustworthy outcome verification, which is a strong assumption. The live experiments use generated arithmetic and reasoning tasks with exact programmatic verifiers. In many real-world agent tasks, outcomes are delayed, ambiguous, subjective, expensive to verify, or not independently observable. Moreover, audits re-run tasks and compare reports with the new outcome, which can differ from the original for stochastic agents. The paper does not establish robustness when the verification process is noisy, incomplete, or costly.
Questions for authors
-
Can the authors compare MIDIAN with baselines using exactly the same probe and verification budget? How much of MIDIAN's improvement comes from allocating additional probes to finalists rather than from its hierarchical structure?
-
Why must the correct task family be known before routing? How would the system handle a new request that spans multiple families, an unseen capability, or an ambiguous task description?
-
How would MIDIAN operate when task success cannot be checked by an exact programmatic verifier, or when the same agent produces different outcomes on repeated trials? How are incorrect audit strikes prevented in such cases?
-
Can the authors compare against a flat router that caches the best agent per family and maintains rankings with a heap or balanced tree, rather than rescanning the entire population for every request?
5 comments
Thank you again. This second part covers outcome verification (W4) and the comparison at equal budget (Q1).
W4. “The method relies on cheap and trustworthy outcome verification, which is a strong assumption … audits re-run tasks and compare reports with the new outcome, which can differ from the original for stochastic agents. The paper does not establish robustness when the verification process is noisy, incomplete, or costly.”
Thank you for raising this point. Following it, we now ran a new experiment in which an audit's re-run disagrees with the original outcome with probability q. At q=0.1 about 6% of honest reporters are wrongly excluded, and at q=0.25 about 25%. With honest agents this has no effect on accuracy, because the remaining honest reporters report the same outcomes. With a colluding cartel MIDIAN's accuracy is 0.80 up to q=0.25, 0.78 at q=0.5 and 0.65 at q=1, and it is always above MIDIAN without audits (0.58). Liars are still excluded at 97-99%. We agree that checkable outcomes are an assumption. We argue that it is weaker than what the alternatives assume: the frameworks trust the self-descriptions, and bandit routers assume the router observes every outcome itself. Colluding reporters are the classical threat in reputation systems (EigenTrust, 2003). For LLM agents, lying or colluding raters have been tested at 50-500 agents (Ev-Trust, 2025; TrustFlow, 2026). We have not seen a coordinated cartel tested on live LLM agents at 10k-100k under a fixed probe budget.
Q1. “Can the authors compare MIDIAN with baselines using exactly the same probe and verification budget? How much of MIDIAN's improvement comes from allocating additional probes to finalists rather than from its hierarchical structure?”
Yes. Following your question, we now ran Sequential Halving (SH) at the same budget, counting verification and audit probes, and under the same peer reports as MIDIAN, with and without our notion of audit. Here b is the number of probes each agent is given per task family, and b=3 below. At 100k live agents, accuracy is 0.76 for flat probing, 0.76 for MIDIAN with verification and audits turned off, 0.82 for MIDIAN and 0.86 for SH. With a colluding cartel the same four are 0.76, 0.74, 0.82 and 0.81, and SH with our audit gets 0.86. At 10k agents without clones under the cartel, SH without the audit drops to 0.37 (MIDIAN: 0.79); SH with our audit reaches 0.83.
Both SH and MIDIAN allocate additional probes to the promising candidates. When all agents are honest, this is what matters most: SH is about 0.03-0.07 more accurate than MIDIAN (0.16 on RouterEval). To your second question: the hierarchical structure with no verification is only 0-0.04 better than flat probing, and re-probing the promoted candidates adds another 0.01-0.07. To compare at exactly the same probe and verification budget, we now include a new version of MIDIAN that pays for its audits out of the same budget. It remains within 0.005 of its accuracy.
Coordinating and resilience: SH requires a coordinator that receives every report. At 100k agents this is about 40M reports (each of the roughly 4.5M probes is reported by 9 peers), over 17 synchronized rounds. In MIDIAN a report never leaves its cohort of 10 agents and cohorts are built in parallel, so there is no party that sees everything and no single point of failure. Agents joining and leaving: a new agent costs MIDIAN about 90 probes inside its own cohort. In comparison, SH has to run its elimination again, which costs about 450 probes per new agent when 10% of the agents are replaced. Small budgets: with b=1 (one probe per agent per family) SH has to spread that single probe over all its elimination rounds, and at 1,000 agents its accuracy falls to 0.43, where MIDIAN stays at 0.69. The need for audits: plain SH with no audit is not robust to collusion at all, as the 0.37 above shows. We thus include both plain SH and SH with our audit within the updated paper.
This third part covers your remaining questions (Q2 to Q4).
Q2. “Why must the correct task family be known before routing? How would the system handle a new request that spans multiple families, an unseen capability, or an ambiguous task description?”
The family does not have to be exact. With families inferred by clustering (see W3) MIDIAN's accuracy is about the same as with the true labels, 0.69-0.73 vs 0.72, and this covers ambiguous descriptions to some extent. A request that spans several families has to be split by the orchestrator first, and each part is then routed by its family. A new capability means one more family, which requires one round of probes for that family and does not affect the others. We have not run experiments on splitting requests or on discovering new capabilities, and the revision says that these are outside its scope.
Q3. “How would MIDIAN operate when task success cannot be checked by an exact programmatic verifier, or when the same agent produces different outcomes on repeated trials? How are incorrect audit strikes prevented in such cases?”
For agents that give different outcomes on repeated trials, see the new experiment under W4. Incorrect strikes are not prevented. When re-runs disagree 25% of the time, about a quarter of honest reporters get excluded, but accuracy does not change, since the honest reporters that remain agree with each other. Beyond that it starts to hurt (0.78 at 50% disagreement). A threshold on the strike rate instead of a count of two strikes would tolerate more noise, and we will mention it as future work. MIDIAN does require outcomes that can be checked (code with tests, math, retrieval or extraction with ground truth). Tasks with subjective or delayed outcomes are outside the scope of the paper.
Q4. “Can the authors compare against a flat router that caches the best agent per family and maintains rankings with a heap or balanced tree, rather than rescanning the entire population for every request?”
Thank you for suggesting this baseline. Following your question, we implemented it; it is new. It picks the same agents as flat probing and requires 11, 18 and 25 comparisons per routed task at 1k, 100k and 10M agents. In comparison, MIDIAN requires 31, 51 and 71. So MIDIAN is not cheaper per request than a flat router with an index, and we will add this baseline to the cost figure and correct the text. The difference between the two is that the flat index is held by one party that stores the estimates of all agents and receives every update. MIDIAN has no such party, and its build and repairs are local.
We believe the paper has greatly improved with these results. We request that you reconsider our paper and support its acceptance.
Thank you for the thorough review. Before the details, a word on what the paper is after: we study routing when there are very many agents (up to 100k), when some of them lie about each other and may do so as a coordinated cartel, when agents join and leave, and when no single party can be relied on to collect every report. Most of the numbers below are from new experiments that we ran following your comments. We believe the paper is much stronger for them, and we ask you to reconsider it and support its acceptance. We answer the weaknesses (W1 to W4) first and then the questions (Q1 to Q4), over three comments.
W1. “The claimed evaluation at 100,000 live agents is a bit misleading as evidence of agent diversity … only seven base models and artificially assigned specializations … at most fourteen distinct agent behaviors … exact clones, and their outputs are memoized.”
We now built new populations without clones: every agent has its own persona, reasoning style, temperature and sampling seed, so no two agents ever return the same stored model output. The specialist population now has 504 distinct behaviors per task family (180 and 72 in the other two populations, which draw on fewer base models). At 1k and 10k agents, MIDIAN's accuracy reaches 0.93-0.95 of the oracle, with a bit larger margin over bandits and learned routers than on the original populations. The 100k run without clones is in progress. There are still only seven base models. We argue that this is close to practice, where most agents are built on models from a few vendors and differ in prompts, tools and settings, but we will list it as a limitation.
W2. “The agent specializations are artificially engineered rather than naturally emerging … This imposes competence differences by construction and may make the skill matrix easier to learn than those of real independently developed agents.”
We used engineered specializations because we need the true skill of every agent, and no existing pool gives that for 100k agents. The paper also evaluates on pools where nothing is engineered. On RouterEval (5,000 independently developed LLMs) MIDIAN's accuracy is 0.73, against 0.65 for flat probing and 0.68 for the warm-start bandit. On RouterBench with 1M agents (specialist population) MIDIAN's accuracy is 0.78, against 0.66-0.70 for flat probing and the bandits. SH (0.88) and LinUCB (0.82) are more accurate than MIDIAN on RouterEval, as SH is on our live benchmark, so the picture is the same with natural skills.
W3. “The benchmark supplies the task family, bypassing an essential part of agent discovery … The paper does not evaluate task-family inference, unseen families, or routing below the family level.”
MIDIAN starts after the task has been classified, and the revision says this at the start. Following your comment, we now evaluated inferred families; this experiment is new. We clustered the prompt embeddings into 4 to 64 clusters and used the clusters as families, on the 5,000 LLMs of RouterEval. MIDIAN's accuracy is 0.69-0.73 with the inferred families, compared with 0.72 with the true labels. Multi-family and unseen requests are discussed under Q2.