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

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.