How Much Does Correctness Cost? Budgeted Placement of Strong Correctors in a Weak Multi-Agent Swarm

Jul 16, 2026

Upload by Hazel

A swarm of cheap, unreliable agents can reach a correct consensus when a small number of costly “oracle” correctors are placed well. The work models consensus on a graph where each oracle pins one node toward truth with concave strength tied to its cost, and evaluates quality via coherence. Results show the coherence remains submodular, enabling cost-benefit greedy to achieve within 1−1/e of the budget-optimal placement and yielding a budget–correctness frontier with closed forms in special cases.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages30

Reading Time1 h 16 min

Introduction

Contributions

Related work

arXiv :2607 .09765v 1 [ cs .AI ] 7 Jul 2026 How Much Does Correctness Cost? Budgeted Placement of Strong Correctors in a Weak Multi-Agent Swarm Igor Itkin Independent Researcher, Tel Aviv, Israel [ig. itkin@gmail. com](ig. itkin@gmail. com) ORCID 0009-0004-9513-8463 July 2026 Abstract A cheap swarm of unreliable agents can be steered to a correct consensus by a few strong, expensive “oracle” correctors. We ask how much one must spend, and where to place the oracles. We model the swarm as a consensus on a graph in which each oracle pins one node toward the truth at a cost-coupled, concave strength, and measure quality by the coherence H (R) = trM(R)−1 . Our first result is that H stays submodular (each added oracle helps less than the last) even when the oracles differ in strength, so a cost-benefit greedy comes within 1 − 1/e of the best placement at any budget. Inverting the budget gives the budget–correctness frontier B ⋆ (ε), the least spend that guarantees an ε-correct consensus: closed-form on the complete graph, and a minimal oracle count k⋆ when oracles cost the same. Whether a budget then buys a few strong oracles or many medium ones is decided by one scalar, the curvature of the cost–quality law: diminishing returns favour spreading, sharply increasing returns favour concentration. Measured on the Qwen3 ladder (0 .6–32B), the law is concave for factual and math verification (replicatedon Gemma-4) but convex for emergent code tracing, so the verdict is genuinely task-dependent. Code and data: [https://github.com/YehudaItkin/budgeted-oracle-placement](https://github.com/YehudaItkin/budgeted-oracle-placement). 1 Introduction Deployed multi-agent large language model (LLM) systems increasingly pair two kinds of agent: a large pool of cheap, individually unreliable workers, and a few strong, expensive models used as verifiers or correctors. The strong models cost more but also correct harder. This raises a budgeting question that the consensus literature has not asked: given a fixed budget, how many strong correctors should one buy, and where should they be placed, to guarantee that the swarm reaches a correct answer? Practice already treats agent assembly as budgeted selection: Yuan et al. cast the choice of tools and sub-agents as a knapsack over heterogeneous-cost, heterogeneous-quality components and solve it online [4] . That work optimizes an empirically measured success rate with a generic online-knapsack competitive ratio, over a static set with no interaction structure. We supply the dynamical foundation that line of work omits. The agents form a consensus loop on a graph, not a static pool, and the objective is the provable tracking error of that loop, not a measured success rate. The decision is where on the graph each oracle sits, because a node’s worth depends on its position. Finally, the oracle’s cost is coupled to its pinning strength through a law w (c), so buying more correction costs more. This coupling is what turns placement into a budgeting problem. It yields a (1 − 1/e) submodular guarantee and a budget–correctness frontier B⋆(ε), closed-form on the complete graph and greedy-computable elsewhere. Its equal-cost limit is the minimal oracle count k⋆ . The model and the placement machinery extend our companion analysis of delayed verification [1], whose homogeneous, cardinality-constrained corrector placement is the special case ci ≡ 1, wi ≡ w recovered in Corollary 1 . This paper makes five contributions. • A cost-coupled corrector model (Section 3): a grounded-Laplacian swarm in which an oracle of cost c pins toward truth with concave strength w (c); correctness is the coherence bound H (R) ≤ ε, and the object of interest is the minimal budget B⋆(ε) . • Submodularity under cost-coupled pins (Theorem 1): the coherence objective [10] is a classically submodular leader-selection criterion [9]; we show the error reduction ρ (R) = H (∅) − H(R) stays monotone submodular u

FAQs

What problem does the paper address about multi-agent swarms?

It studies how to budget for a few strong, expensive correctors so that a weak swarm of many unreliable agents still reaches a correct consensus.

How is the swarm modeled and how is “correctness” measured?

The swarm forms a consensus loop on a graph where oracle correctors pin nodes toward the truth with cost-coupled concave strength. Correctness is evaluated using a coherence objective that bounds the tracking error.

What optimization guarantee does the paper provide for choosing oracle placements under a budget?

Because the coherence objective stays submodular even with heterogeneous oracle strengths, a cost-benefit greedy strategy achieves a placement within 1−1/e of the best budget-feasible solution.

Jul 16, 2026

Upload by Hazel