A cheap swarm of unreliable agents can be steered to a correct consensus by a few strong, expensive 'oracle' correctors. This work explores the cost and optimal placement of these oracles. We model the swarm as a consensus on a graph where each oracle pins one node toward the truth at a cost-coupled, concave strength, measuring quality by $H(R)=\operatorname{tr} M(R)^{-1}$.
Our first result shows that $H$ remains submodular even when oracles differ in strength, allowing a cost-benefit greedy algorithm to achieve within $1-1/e$ of the optimal placement at any given budget. Inverting the budget leads to the budget-correctness frontier $B^*(\operatorname{eps})$, representing the least spend required for an $\operatorname{eps}$-correct consensus: available in closed form on the complete graph, and with a minimal oracle count $k^*$ when costs are uniform. Whether a budget buys a few strong or many medium-strength oracles is influenced by the curvature of the cost-quality law: diminishing returns are sharply evident. Based on measurements from the Qwen3 ladder (0.6-32B), the law is concave for mathematical verification but convex for emergent code tracing, indicating a genuine task dependency.
For more information, see the GitHub project.
Blogger's Review: This paper provides deep insights into effectively deploying strong correctors within multi-agent systems under budget constraints to achieve consensus. The approach not only offers a fresh perspective for theoretical studies but also guides resource allocation in practical applications, especially in complex systems where cost-benefit balance is crucial. The observation of diminishing returns and its task dependency points to promising directions for future research.