acceptodds
Under review as a conference paper at ICLR 2027

MIDIAN: Metric-Induced Distributed Agent Networks for Scalable, Adversarially Robust Task Allocation

Abstract

Multi-agent frameworks route tasks by having a supervisor model read the agents' self-descriptions and select one. This suits small, hand-assembled teams but breaks down as agent networks grow large, specialized, or dishonest. From a hundred to a hundred thousand agents, every tested framework performs poorly even with dense retrievers and task-specific retrieval instructions, and it degrades to near-random with standard retrievers. We propose MIDIAN, a hierarchical router that replaces self-description with verified competence. Small cohorts of agents probe one another on tasks with checkable outcomes, each cohort summarizes its best member per task family up the tree, and tasks descend the tree in logarithmically many steps. A small audit of peer reports keeps the estimates accurate under dishonest reporting. We introduce a live execution benchmark of LLM agents with ground-truth skill, and we also evaluate on RouterBench, RouterEval, and LLMRouterBench. Every framework we test improves when given MIDIAN's shortlist in place of its own retrieval, and on large populations MIDIAN on its own matches or outperforms the most widely used frameworks and published routers. Its advantage grows with population size, reaching 0.97 of the oracle at a hundred thousand agents. It also grows with the fraction of dishonest agents, especially when low-skill agents collude. In that regime, every method that trusts descriptions or peer reports collapses. Because MIDIAN makes no model calls at routing time, its cost is a one-time build, repaid within a few thousand tasks; after that, each routing decision costs under a thousandth of a supervisor call.

Primary area:
foundation or frontier models, including LLMs
Keywords:
multi-agent systems, task allocation, LLM routing, hierarchical routing, agent orchestration, adversarial robustness, scalability, distributed systems, peer evaluation, agentic AI

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_UQntOpenReview ↗
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
  1. 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.

  2. 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.

  3. 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
  1. 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.

  2. 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).

  3. 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.

  4. 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
  1. 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?

  2. 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?

  3. 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?

  4. 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 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.

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.

Reviewer_ymt3OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies large-scale agent routing and proposes MIDIAN, which builds a hierarchical tree of empirically estimated agent competence with peer reporting, trimming, auditing, and re-verification.

Critical strengths

the intuition and the problem settings are interesting and meaningful.

Critical weaknesses

when I read this manuscript, I feel awful. It seems that this paper is heavily polished by some AI tools and it contains too many overly defensive sentences, like too many extra explanations, exceptions, numbers, and responses to possible concerns mixed into the main text. This makes it hard to see the main research question, the key idea of the method, and why the method actually works better. I think the paper should be written in a much simpler and clearer way, with more focus on the core idea.

I tried my best to understand their work and to my best knowledge, I think the problem is substantially narrower than presented (for example, routing assumes a known task family and largely reduces to identifying the best agent per family, rather than general prompt-level routing). In addition, MIDIAN mainly combines hierarchical selection, trimmed aggregation, auditing, and re-verification, the empirical advantage is hard to interpret because MIDIAN adaptively reallocates probe budget to promising candidates, while no comparable adaptive best-arm/elimination baseline is included. In addition, the “100K live agents” claim is weakened by heavy memoization and many exact-clone agents.

Questions for authors

none

4 comments

Thank you for the 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. Your comments helped us state this scope clearly, and separate what comes from adaptive allocation and what from the tree structure. We believe the paper is much stronger for it, and we ask you to reconsider it and support its acceptance. Our replies to each point are below, in two comments.

1. “… this paper is heavily polished by some AI tools and it contains too many overly defensive sentences, like too many extra explanations, exceptions, numbers, and responses to possible concerns mixed into the main text. This makes it hard to see the main research question, the key idea of the method, and why the method actually works better.”

Thank you for this honest comment; it is fair. We are now rewriting the paper ourselves. The main text will have the problem, the idea, the mechanism, why it works and the main experiments. Details of the benchmark construction and the caveats go to the appendix.

2. “… the problem is substantially narrower than presented (for example, routing assumes a known task family and largely reduces to identifying the best agent per family, rather than general prompt-level routing).”

Yes, MIDIAN routes by task family, and the revision says this at the start. This is the setting of agent registries and marketplaces, where agents are listed by capability. Following your comment, we now tested how much depends on having the labels; this experiment is new. We clustered the prompt embeddings into 4 to 64 clusters and used the clusters as families, on a pool of 5,000 real LLMs (RouterEval). MIDIAN's accuracy is 0.69-0.73 with the inferred families, compared with 0.72 with the true labels, and from 8 clusters on the ranking of methods is the same as with labels. We also compare with the prompt-level routers kNN and MLP, which we now ran at 10k agents. MIDIAN's accuracy is at least 0.05 higher than both on all three populations (specialists: every agent is strong on 3 of the 16 task families; heavy-tailed: one agent in ten is a large model that is strong everywhere; bimodal: 20% strong agents, 80% weak ones).

Thank you again. This second part covers the elimination baseline and the populations without clones.

3. “… the empirical advantage is hard to interpret because MIDIAN adaptively reallocates probe budget to promising candidates, while no comparable adaptive best-arm/elimination baseline is included.”

Following your comment, we now ran Sequential Halving (SH) as the elimination baseline, running it under the same peer reports and same budget 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 reallocate probes adaptively 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). The tree 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 fairly at an equal 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.

4. “In addition, the ‘100K live agents’ claim is weakened by heavy memoization and many exact-clone agents.”

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, and its margin over bandits and learned routers is a bit larger than on the original populations (+0.05 instead of +0.03 on specialists at 10k). It turned out that the clones were helping the rival methods, since their estimates saturate when many agents are identical. The 100k run without clones is in progress and will be in the revision.

We believe the paper has greatly improved with the SH comparison, the populations without clones and the clearer scope. We request that you reconsider our paper and support its acceptance.

Thank you again for your constructive feedback. As the discussion period is approaching its end, we would be grateful if you could let us know whether our responses and additional experiments have addressed your main concerns, or if any points still require clarification. We would be happy to provide further clarification promptly.

thanks for the response. I will maintain my score.

Reviewer_3cqdOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

MIDIAN routes tasks through a hierarchy of agents using peer-reported performance, promotion-time verification, and random audits. The paper evaluates routing accuracy, robustness to collusion.

Critical strengths

Combining verified performance with auditing addresses a relevant vulnerability of description-based routing.

Critical weaknesses
  1. The comparisons do not clearly explain why MIDIAN performs better. MIDIAN gives additional tests to promising candidates, while the baselines distribute their initial tests non-adaptively. The improvement may therefore come from how the testing budget is allocated, rather than from the proposed tree structure. A comparison with methods that also concentrate tests on promising candidates, such as Sequential Halving, is missing. Moreover, the MLP baseline is tested only up to 1,000 agents, so the results do not establish superiority over this baseline at larger scales.

  2. The experiments provide limited evidence for practical scalability and long-term performance. The 100,000-agent experiment has at most fourteen distinct behavior configurations per task type, with outputs reused across identical configurations. Its cost estimate still counts approximately 4.96 million initial tests, raising questions about deployment costs when such reuse is unavailable. During operation, mainly the selected agents receive new feedback; it is unclear how initially underestimated agents get another chance. With equally frequent task types and only 300 routed tasks per large-scale run, the experiments do not adequately test performance on rare tasks, recovery from early selection errors, or whether the initial testing cost pays off as agents and tasks change.

Questions for authors

What evidence separates the benefit of the hierarchy from adaptive probe allocation under an equal total budget, including audits?

4 comments

Thank you for the detailed 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. We compare a wide set of routing methods under these conditions. Your request for Sequential Halving, with and without audits, let us separate two things the first version mixed together. Adaptive allocation of tests is what buys accuracy. The tree is what removes the central coordinator and makes repair local when agents change. The audits are what make either one survive a cartel. We believe the paper is much stronger for it, and we ask you to reconsider it and support its acceptance.

A. “The comparisons do not clearly explain why MIDIAN performs better. MIDIAN gives additional tests to promising candidates, while the baselines distribute their initial tests non-adaptively. The improvement may therefore come from how the testing budget is allocated, rather than from the proposed tree structure. A comparison with methods that also concentrate tests on promising candidates, such as Sequential Halving, is missing.” “What evidence separates the benefit of the hierarchy from adaptive probe allocation under an equal total budget, including audits?”

We now ran Sequential Halving (SH), running it under the same peer reports and same budget as MIDIAN, and also separating runs with and without our notion of audit to capture the cartel attack surface we consider here. The results are summarized below:

(1) Accuracy with a budget of three tests per agent per task type (b=3): 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 tests adaptively: they spend more tests on the candidates that look best. 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). The tree with no verification is only 0-0.04 better than flat probing, and re-testing the promoted candidates adds another 0.01-0.07. To compare fairly at an equal budget, we now include a new version of MIDIAN that pays for its audits out of the same budget (MIDIAN re-runs 5% of the tests to audit the reports, which put it about 3% over the budget). It remains within 0.005 of its accuracy.

(2) 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 tests is reported by 9 peers), over 17 synchronized rounds, since 100k agents must be halved 17 times. 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 party whose failure or overload stops the build. These are two separate gains: less traffic through one point, and no single point of failure.

(3) Agents joining and leaving: When a new agent joins, MIDIAN tests only that agent, inside its own cohort: about 90 tests, whatever the population size. SH has no local repair. Its ranking comes from rounds of elimination over the whole population, so a new agent can only be placed by running the elimination again, which costs about 450 tests per new agent when 10% of the agents are replaced, 5 times more. If SH is not rebuilt, its accuracy falls to 0.65 when 30% of the agents are replaced, where MIDIAN keeps 0.75.

(4) Small budgets: With b=1 every agent can be tested only once per task type. SH has to spread that single test over all its elimination rounds, so its first cuts are made on almost no evidence. At 1,000 agents its accuracy falls to 0.43, where MIDIAN stays at 0.69.

(5) The need for audits: Plain SH with no audit is not robust to collusion at all, receiving an accuracy of 0.37 at 10k agents under the cartel, against 0.79 for MIDIAN and 0.83 for SH with our audit. We thus include both plain SH and SH with our audit within the updated paper.

Thank you again. This second part covers the MLP baseline, the populations without clones and the cost.

B. “Moreover, the MLP baseline is tested only up to 1,000 agents, so the results do not establish superiority over this baseline at larger scales.”

As you say, the submitted paper had MLP only up to 1,000 agents. We now ran the MLP router at 10k agents, 10 seeds on each of the three populations (specialists: every agent is strong on 3 of the 16 task types; heavy-tailed: one agent in ten is a large model that is strong everywhere; bimodal: 20% strong agents, 80% weak ones), and include it in the paper. MIDIAN’s accuracy is 0.05-0.09 higher than MLP and wins on all 10 seeds. Against kNN, MIDIAN wins on 9 of the 10 seeds in some populations and on all 10 in the others. We also tried MLP at 100k. Its training time grows about 22x from 1k to 10k agents (4.5 hours per run), and at 100k a run did not finish in 18 hours; we estimate about 12 days per run, so we cannot report it. kNN at 100k is running now. On all 20 models of LLMRouterBench, MLP has better accuracy than MIDIAN, 0.68 vs 0.65. However, LLMRouterBench has only 20 models, all honest, which is the setting learned routers are built for. This is now included in our paper revision.

1. “The 100,000-agent experiment has at most fourteen distinct behavior configurations per task type, with outputs reused across identical configurations.”

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 type (180 and 72 in the other two populations). The specialist population draws on all seven base models, the other two on fewer, so they have fewer distinct combinations. At 1k and 10k agents, MIDIAN’s accuracy reaches 0.93-0.95 of the oracle. Its margin over the best bandit or learned router is a bit larger than before, e.g. +0.05 instead of +0.03 on specialists at 10k, and +0.06 instead of -0.02 on the heavy-tailed population at 1k. The 100k run without clones is in progress and will be in the revision. Regarding the clones in our original runs: first, clones were not asked the same questions, since test questions were drawn per agent. Second, it turned out that the clones were helping the rival methods, since their estimates saturate when many agents are identical. So removing the clones, as you asked, slightly widens MIDIAN's margin.

2. “Its cost estimate still counts approximately 4.96 million initial tests, raising questions about deployment costs when such reuse is unavailable.”

We should have been clearer about this. The cost estimate does not assume any reuse. All 4.96M tests are charged as full model calls. That is, 48 calls per agent, paid once. Compared with a framework that calls a supervisor model for every task, the build pays for itself after 1 to 10 routed tasks per agent, and after that a routed task costs less than 1/1000 of a supervisor call. The revision gives this break-even point for each population size: about 1,000 to 10,000 routed tasks at 1k agents, and about 90,000 to 970,000 at 100k agents.

This third part covers underestimated agents, rare tasks and agents that join and leave. We ran new experiments for most of your points and hope they allow you to support acceptance.

3. “During operation, mainly the selected agents receive new feedback; it is unclear how initially underestimated agents get another chance.”

You are right that MIDIAN does not go back and re-test agents on its own. An agent that was underestimated in the build gets another chance in three cases. First, if the agent currently chosen starts failing user tasks and its running accuracy drops below that of a cohort-mate, the cohort-mate takes over. Second, when agents join or leave, the affected cohort is tested again. Third, when the audit excludes a lying reporter, the estimates of its cohort are recomputed without it. Outside these cases an underestimated agent waits for the next build, and the revision says so.

We chose not to explore on user tasks, because every exploratory task is a real user's task sent to an agent we believe is worse. Methods that do explore are a useful check. On the heavy-tailed population, UCB reaches an accuracy of 0.44 and Thompson sampling 0.51 over the same sequence of user tasks, against 0.73 for MIDIAN. With 1,000 or more agents and 16 task types there are far more agent and task-type pairs to try than there are tasks, so the sequence ends before what these methods learn makes up for the tasks they lost while trying.

4. “With equally frequent task types and only 300 routed tasks per large-scale run, the experiments do not adequately test performance on rare tasks, recovery from early selection errors, or whether the initial testing cost pays off as agents and tasks change.”

Thank you for raising this interesting point.

This experiment is new. Following your comment, we made task types unequally frequent (a Zipf distribution over the 16 task types, so that the 8 rarest together receive about 20% of the tasks). We ran it on the synthetic benchmark with 10k agents. The overall accuracy does not drop compared with equally frequent task types: 0.90 against 0.89 on specialists and 0.82 against 0.81 on the heavy-tailed population. On specialists the accuracy on the 8 rarest task types is within 0.01 (one percentage point) of the 3 most common ones. On the heavy-tailed population it is 0.01 to 0.05 lower. The reason is that the build tests every agent on every task type equally before any user task arrives, so a rare task type starts with the same quality. It only receives fewer corrections afterwards, because corrections come from user tasks.

For agents leaving and new agents joining, the submitted paper already has the churn experiment, which replaces 10% or 30% of the agents every 200 tasks. While preparing this reply we found a bug in the repair step that made MIDIAN look worse under churn than it is. With the fix, on the synthetic benchmark, MIDIAN with 10% churn gets 0.88 vs 0.90 with no churn (specialists) and 0.72 vs 0.73 (heavy-tailed). The repair uses about 90 tests per new agent; rebuilding SH uses about 450. We will rerun the live version with the fix for the camera-ready version.

The 300 tasks apply to the live runs with 10k agents or more. The replay and synthetic benchmarks use 1,000-2,000 tasks and up to 1,000 seeds, and the ranking of methods is the same there.

We believe the paper has greatly improved following your comments, in particular with the SH comparison at equal budget. We request that you reconsider our paper and support its acceptance.

Thank you again for your constructive feedback. As the discussion period is approaching its end, we would be grateful if you could let us know whether our responses and additional experiments have addressed your main concerns, or if any points still require clarification. We would be happy to provide further clarification promptly.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.