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

# How Much Does Correctness Cost? Budgeted Placement of Strong Correctors in a Weak Multi-Agent Swarm
Source: [https://arxiv.org/html/2607.09765](https://arxiv.org/html/2607.09765)
\(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\)=tr⁡M​\(R\)−1H\(R\)=\\operatorname\{tr\}M\(R\)^\{\-1\}\. Our first result is thatHHstays*submodular*\(each added oracle helps less than the last\) even when the oracles differ in strength, so a cost\-benefit greedy comes within1−1/e1\-1/eof the best placement at any budget\. Inverting the budget gives the*budget–correctness frontier*B⋆​\(ε\)B^\{\\star\}\(\\varepsilon\), the least spend that guarantees anε\\varepsilon\-correct consensus: closed\-form on the complete graph, and a minimal oracle countk⋆k^\{\\star\}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\.60\.6–3232B\), the law is concave for factual and math verification \(replicated on 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)\.

## 1Introduction

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](https://arxiv.org/html/2607.09765#bib.bib4)\]\. 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 laww​\(c\)w\(c\), so buying more correction costs more\. This coupling is what turns placement into a budgeting problem\. It yields a\(1−1/e\)\(1\-1/e\)submodular guarantee and a budget–correctness frontierB⋆​\(ε\)B^\{\\star\}\(\\varepsilon\), closed\-form on the complete graph and greedy\-computable elsewhere\. Its equal\-cost limit is the minimal oracle countk⋆k^\{\\star\}\.

The model and the placement machinery extend our companion analysis of delayed verification\[[1](https://arxiv.org/html/2607.09765#bib.bib1)\], whose homogeneous, cardinality\-constrained corrector placement is the special caseci≡1c\_\{i\}\\equiv 1,wi≡ww\_\{i\}\\equiv wrecovered in Corollary[1](https://arxiv.org/html/2607.09765#Thmcorollary1)\.

This paper makes five contributions\.

- •A cost\-coupled corrector model\(Section[3](https://arxiv.org/html/2607.09765#S3)\): a grounded\-Laplacian swarm in which an oracle of costccpins toward truth with concave strengthw​\(c\)w\(c\); correctness is the coherence boundH​\(R\)≤εH\(R\)\\leq\\varepsilon, and the object of interest is the minimal budgetB⋆​\(ε\)B^\{\\star\}\(\\varepsilon\)\.
- •Submodularity under cost\-coupled pins\(Theorem[1](https://arxiv.org/html/2607.09765#Thmtheorem1)\): the coherence objective\[[10](https://arxiv.org/html/2607.09765#bib.bib10)\]is a classically submodular leader\-selection criterion\[[9](https://arxiv.org/html/2607.09765#bib.bib9)\]; we show the error reductionρ​\(R\)=H​\(∅\)−H​\(R\)\\rho\(R\)=H\(\\varnothing\)\-H\(R\)stays monotone submodular under heterogeneous, cost\-coupled diagonal pins \(not identical leaders\), via the M\-matrix / entrywise\-nonnegative\-inverse argument, which is what turns selection into a budgeted knapsack\.
- •A budgeted\(1−1/e\)\(1\-1/e\)placement\(Theorem[2](https://arxiv.org/html/2607.09765#Thmtheorem2)\): cost\-benefit greedy buys an error reduction within1−1/e1\-1/eof the budget\-optimal, concentrating spend on the*resolvent centrality per dollar*of each node\.
- •The budget–correctness frontier\(Proposition[1](https://arxiv.org/html/2607.09765#Thmproposition1), Theorem[3](https://arxiv.org/html/2607.09765#Thmtheorem3), Corollary[1](https://arxiv.org/html/2607.09765#Thmcorollary1)\): a closed\-form coherence and frontierB⋆B^\{\\star\}on the complete graph; its homogeneous\-cost limit is a minimal oracle countk⋆k^\{\\star\}; and the curvature of the cost–quality law as the scalar that decides few\-strong versus many\-medium oracles\.
- •A high\-probability \(Stage\-B\) threshold\(Section[8](https://arxiv.org/html/2607.09765#S8)\): the same budgeting question on a nonlinear majority cascade has a sharp phase transition whose threshold is a degree\-weighted influence balance, exact on the complete graph, rigorous on dense random graphs \(Theorem[4](https://arxiv.org/html/2607.09765#Thmtheorem4)\), and hysteretic on sparse ones\. The threshold is extended to fallible correctors \(Proposition[2](https://arxiv.org/html/2607.09765#Thmproposition2)\), unified with Stage A as its near\-consensus linearization \(Remark[6](https://arxiv.org/html/2607.09765#Thmremark6)\), and demonstrated on a real LLM swarm\.

## 2Related work

Budgeted corrector placement sits between three literatures; none gives the cost\-coupled, consensus\-correctness object we study\.

*Leader and pinning placement on consensus\.*The spectral backbone is the grounded Laplacian, whose smallest eigenvalue governs convergence to pinned nodes\[[11](https://arxiv.org/html/2607.09765#bib.bib11)\]\. Leader selection minimizes a consensus error by choosing a fixed number of leaders\[[14](https://arxiv.org/html/2607.09765#bib.bib14)\], and supermodular structure gives greedy\(1−1/e\)\(1\-1/e\)guarantees\[[8](https://arxiv.org/html/2607.09765#bib.bib8)\]; the coherence \(total steady\-state variance\) objective\[[10](https://arxiv.org/html/2607.09765#bib.bib10)\]we use is itself a classically submodular leader\-selection criterion\[[9](https://arxiv.org/html/2607.09765#bib.bib9)\], and maximizing the smallest grounded\-Laplacian eigenvalue is the closest spectral objective to ours\[[12](https://arxiv.org/html/2607.09765#bib.bib12)\]\. All fix a count of identical agents\. Our increment is to couple pin strength to cost through a quality laww​\(c\)w\(c\), turning selection into a budgeted knapsack, and to show submodularity survives that cost\-coupled heterogeneity\.

*Budgeted submodular maximization\.*The greedy\(1−1/e\)\(1\-1/e\)bound\[[6](https://arxiv.org/html/2607.09765#bib.bib6)\], its single\-knapsack extension\[[5](https://arxiv.org/html/2607.09765#bib.bib5)\], and scalable cost\-aware variants\[[7](https://arxiv.org/html/2607.09765#bib.bib7),[15](https://arxiv.org/html/2607.09765#bib.bib15)\]are off\-the\-shelf\. We supply the missing piece, a consensus value whose cost\-coupled heterogeneous form is submodular, so the knapsack machinery applies and yields the budget–correctness frontier\.

*Resilient consensus and trusted nodes\.*A few strong nodes can relax the robustness a network needs to tolerate faults\[[16](https://arxiv.org/html/2607.09765#bib.bib16)\], building onrr\-robustness and the W\-MSR filtering rule\[[17](https://arxiv.org/html/2607.09765#bib.bib17)\]\. These give a robustness relaxation rather than a sharp budget threshold, a placement guarantee, or a cost model\. Our Stage\-B threshold and Stage\-A frontier supply all three\.

*Budgeted agent selection in LLM systems\.*Practice already budgets agent assembly: a composer agent picks tools and sub\-agents by online knapsack\[[4](https://arxiv.org/html/2607.09765#bib.bib4)\], model cascades escalate to a strong model on low confidence\[[18](https://arxiv.org/html/2607.09765#bib.bib18)\], and a recent analysis finds a continuous\-gain synergy phase transition with closed\-form compute\-allocation rules\[[13](https://arxiv.org/html/2607.09765#bib.bib13)\]\. That last is the closest: it shares budgeted allocation and a sharp threshold, but over per\-agent compute on correlated inputs, with no graph or placement\. None of these models a consensus on a graph, a corrector placement, a cost\-coupled quality law, or a provable correctness frontier; our threshold is set by graph position \(an influence balance over node degrees\), not by count or per\-agent compute alone\.

## 3Model

*Swarm and correctors\.*LetG=\(V,E\)G=\(V,E\)be a connected graph onNNagents, with LaplacianL=D−AL=D\-A\(AAthe adjacency matrix,DDthe diagonal degree matrix\)\. The agents run a linear consensus toward a truth valueb⋆b^\{\\star\}: at each step an agent moves toward the average of its neighbours, while a common anchor of strengthκ\>0\\kappa\>0holds the loop in place\. An unknown subset of agents instead injects a bounded bias\. Stacking those biases into a vectorg∈ℝNg\\in\\mathbb\{R\}^\{N\}, the swarm settles at an equilibrium that we want to sit as close tob⋆b^\{\\star\}as possible\.

A corrector, or*oracle*, placed at nodeiipins that node towardb⋆b^\{\\star\}with strengthwi\>0w\_\{i\}\>0\(a largerwiw\_\{i\}pulls harder\)\. Leteie\_\{i\}be theiith standard basis vector, soei​ei⊤e\_\{i\}e\_\{i\}^\{\\top\}is the matrix that acts only on nodeii\. A placementR⊆𝒪R\\subseteq\\mathcal\{O\}, chosen from a candidate set𝒪⊆V\\mathcal\{O\}\\subseteq V, adds one such pin per oracle:

M​\(R\)=L\+κ​I\+∑i∈Rwi​ei​ei⊤=M0\+WR,WR=diag⁡\(wi​1​\[i∈R\]\)\.M\(R\)=L\+\\kappa I\+\\sum\_\{i\\in R\}w\_\{i\}\\,e\_\{i\}e\_\{i\}^\{\\top\}=M\_\{0\}\+W\_\{R\},\\qquad W\_\{R\}=\\operatorname\{diag\}\\\!\\big\(w\_\{i\}\\,\\mathds\{1\}\[i\\in R\]\\big\)\.\(1\)HereM0=L\+κ​IM\_\{0\}=L\+\\kappa Iis the uncorrected operator andWRW\_\{R\}collects the pins; both are positive definite forκ\>0\\kappa\>0\. The equilibrium error is thene∞=M​\(R\)−1​ge\_\{\\infty\}=M\(R\)^\{\-1\}g\. Averaging over where the fault lands \(ggzero\-mean with covarianceσ2​I\\sigma^\{2\}I\) gives an expected squared error ofσ2​tr⁡M​\(R\)−2\\sigma^\{2\}\\operatorname\{tr\}M\(R\)^\{\-2\}\. We work instead with the closely related and standard*coherence*

H​\(R\)=tr⁡M​\(R\)−1,H\(R\)=\\operatorname\{tr\}M\(R\)^\{\-1\},\(2\)which also falls each time an oracle is added\. We call the loop*ε\\varepsilon\-correct*whenH​\(R\)≤εH\(R\)\\leq\\varepsilon: the smallerHH, the better the swarm tracks the truth\.

*Cost coupled to quality\.*The new ingredient is that a stronger oracle is more expensive\. Each candidateiicarries a costci\>0c\_\{i\}\>0, and its pinning strength is set by a single law of the cost\.

###### Assumption 1\(diminishing\-returns cost–quality law\)\.

There is a strictly increasing, concavew:ℝ\>0→ℝ\>0w:\\mathbb\{R\}\_\{\>0\}\\to\\mathbb\{R\}\_\{\>0\}withwi=w​\(ci\)w\_\{i\}=w\(c\_\{i\}\); e\.g\.w​\(c\)=w¯​\(1−e−c/c0\)w\(c\)=\\bar\{w\}\\,\(1\-e^\{\-c/c\_\{0\}\}\)\. Concavity encodes that the marginal pinning strength bought per dollar decreases with spend\.

Assumption[1](https://arxiv.org/html/2607.09765#Thmassumption1)is what makes “buy a few strong or many medium oracles” a genuine question: under a budget, concavity ofwwtrades off against the diminishing returns of placement itself\.

*The budgeting problems\.*With a budgetB\>0B\>0and the error reductionρ​\(R\)=H​\(∅\)−H​\(R\)≥0\\rho\(R\)=H\(\\varnothing\)\-H\(R\)\\geq 0, we study the primal and its inverse:

###### Problem 1\(budgeted error reduction\)\.

maxR⊆𝒪⁡ρ​\(R\)\\max\_\{R\\subseteq\\mathcal\{O\}\}\\rho\(R\)subject to∑i∈Rci≤B\\sum\_\{i\\in R\}c\_\{i\}\\leq B\.

###### Problem 2\(budget–correctness frontier\)\.

B⋆​\(ε\)=minR⊆𝒪​∑i∈RciB^\{\\star\}\(\\varepsilon\)=\\min\_\{R\\subseteq\\mathcal\{O\}\}\\sum\_\{i\\in R\}c\_\{i\}subject toH​\(R\)≤εH\(R\)\\leq\\varepsilon\.

Problem[2](https://arxiv.org/html/2607.09765#Thmproblem2)is the headline object: the least one must spend to guarantee anε\\varepsilon\-correct swarm\.

## 4Submodular structure

Adding oracleiito a placementRRlowers the coherence by a*marginal gain*Δi​\(R\)\\Delta\_\{i\}\(R\), which the Sherman–Morrison identity puts in closed form:

Δi​\(R\):=H​\(R\)−H​\(R∪\{i\}\)=wi​‖M​\(R\)−1​ei‖21\+wi​ei⊤​M​\(R\)−1​ei≥0,\\Delta\_\{i\}\(R\):=H\(R\)\-H\(R\\cup\\\{i\\\}\)=\\frac\{w\_\{i\}\\,\\\|M\(R\)^\{\-1\}e\_\{i\}\\\|^\{2\}\}\{1\+w\_\{i\}\\,e\_\{i\}^\{\\top\}M\(R\)^\{\-1\}e\_\{i\}\}\\ \\geq\\ 0,\(3\)This gain is a centrality score read off the resolventM​\(R\)−1M\(R\)^\{\-1\}: it is largest at high\-leverage nodes, the amplifiers and bridges, where a single pin removes the most error\. The reductionρ\\rhois*submodular*when these marginal gains only shrink as the placement grows: each added oracle removes less error than it would have earlier, the set\-level analogue of diminishing returns\. That is what lets a greedy come within a constant factor of optimal, and our first result is that letting the oracles differ in strengthwiw\_\{i\}does not break it\.

###### Theorem 1\(submodularity under heterogeneous pins\)\.

Letwi\>0w\_\{i\}\>0for everyii\. Thenρ​\(R\)=H​\(∅\)−H​\(R\)\\rho\(R\)=H\(\\varnothing\)\-H\(R\)is monotone non\-decreasing and submodular, withρ​\(∅\)=0\\rho\(\\varnothing\)=0; equivalentlyΔi​\(R\)≥Δi​\(S\)≥0\\Delta\_\{i\}\(R\)\\geq\\Delta\_\{i\}\(S\)\\geq 0for allR⊆S⊆𝒪R\\subseteq S\\subseteq\\mathcal\{O\}andi∉Si\\notin S\.

###### Proof idea\.

Both properties reduce to the sign of the resolventM​\(R\)−1M\(R\)^\{\-1\}\. Monotonicity is the Loewner ordering: adding a pin givesM​\(R∪\{i\}\)⪰M​\(R\)M\(R\\cup\\\{i\\\}\)\\succeq M\(R\), henceH​\(R∪\{i\}\)≤H​\(R\)H\(R\\cup\\\{i\\\}\)\\leq H\(R\)\. Submodularity holds becauseM​\(R\)M\(R\)is a symmetric M\-matrix, so its inverse is entrywise nonnegative; this keeps the mixed pin\-derivatives ofHHnonnegative at every strength, which is why heterogeneous, cost\-coupled pins behave like identical leaders\. The computation is carried out in[Appendix A](https://arxiv.org/html/2607.09765#A1)\. ∎

## 5Budgeted placement

Becauseρ\\rhois monotone submodular withρ​\(∅\)=0\\rho\(\\varnothing\)=0and the cost∑i∈Rci\\sum\_\{i\\in R\}c\_\{i\}is modular, Problem[1](https://arxiv.org/html/2607.09765#Thmproblem1)is a submodular knapsack\. Call*cost\-benefit greedy*the following procedure of\[[5](https://arxiv.org/html/2607.09765#bib.bib5),[7](https://arxiv.org/html/2607.09765#bib.bib7)\]\. Enumerate every seed set of at most three oracles; extend each seed by repeatedly adding the unpinned node of largest ratioΔi​\(R\)/ci\\Delta\_\{i\}\(R\)/c\_\{i\}while the budget allows; return the best placement found\. Algorithm[1](https://arxiv.org/html/2607.09765#algorithm1)states it, and the lazy evaluation of\[[7](https://arxiv.org/html/2607.09765#bib.bib7)\]makes the inner loop efficient\.

###### Theorem 2\(\(1−1/e\)\(1\-1/e\)budgeted placement\)\.

LetRB⋆R^\{\\star\}\_\{B\}be an optimal solution of Problem[1](https://arxiv.org/html/2607.09765#Thmproblem1), and letRgR\_\{g\}be the placement returned by cost\-benefit greedy\. Then

ρ​\(Rg\)≥\(1−1/e\)​ρ​\(RB⋆\)\.\\rho\(R\_\{g\}\)\\ \\geq\\ \\big\(1\-1/e\\big\)\\,\\rho\(R^\{\\star\}\_\{B\}\)\.\(4\)

###### Proof\.

Immediate from Theorem[1](https://arxiv.org/html/2607.09765#Thmtheorem1)and the single\-knapsack guarantee for monotone submodular maximization\[[5](https://arxiv.org/html/2607.09765#bib.bib5)\]\. See[Appendix B](https://arxiv.org/html/2607.09765#A2)\. ∎

The selection rule of Theorem[2](https://arxiv.org/html/2607.09765#Thmtheorem2)is interpretable: greedy spends on the node of largest*resolvent centrality per dollar*,

Δi​\(R\)ci=1ci⋅w​\(ci\)​‖M​\(R\)−1​ei‖21\+w​\(ci\)​ei⊤​M​\(R\)−1​ei,\\frac\{\\Delta\_\{i\}\(R\)\}\{c\_\{i\}\}=\\frac\{1\}\{c\_\{i\}\}\\cdot\\frac\{w\(c\_\{i\}\)\\,\\\|M\(R\)^\{\-1\}e\_\{i\}\\\|^\{2\}\}\{1\+w\(c\_\{i\}\)\\,e\_\{i\}^\{\\top\}M\(R\)^\{\-1\}e\_\{i\}\},\(5\)which couples two quantities: the node’s graph leverage‖M​\(R\)−1​ei‖2\\\|M\(R\)^\{\-1\}e\_\{i\}\\\|^\{2\}, and the cost\-efficiency of strengthw​\(ci\)/ciw\(c\_\{i\}\)/c\_\{i\}\. The few\-strong\-versus\-many\-medium tradeoff lives in that product\.

The same loop also traces the frontier: with the stopping ruleH​\(R\)≤εH\(R\)\\leq\\varepsilonin place of the budget, cost\-benefit greedy returnsB⋆​\(ε\)=∑i∈RciB^\{\\star\}\(\\varepsilon\)=\\sum\_\{i\\in R\}c\_\{i\}, the least spend that certifiesε\\varepsilon\-correctness\.

Input:grounded operator

M0=L\+κ​IM\_\{0\}=L\+\\kappa I; candidates

𝒪\\mathcal\{O\}; costs

\{ci\}\\\{c\_\{i\}\\\}; quality law

ww; either budget

BB\(primal\) or target

ε\\varepsilon\(frontier\)\.

Output:placement

RR; for the frontier,

B⋆​\(ε\)=∑i∈RciB^\{\\star\}\(\\varepsilon\)=\\sum\_\{i\\in R\}c\_\{i\}\.

1

R←∅R\\leftarrow\\varnothing; maintain the resolvent

M​\(R\)−1M\(R\)^\{\-1\}\(initialised at

M0−1M\_\{0\}^\{\-1\}\)

2while*𝒪∖R≠∅\\mathcal\{O\}\\setminus R\\neq\\varnothing*do

3foreach*i∈𝒪∖Ri\\in\\mathcal\{O\}\\setminus R*do

Δi←w​\(ci\)​‖M​\(R\)−1​ei‖21\+w​\(ci\)​ei⊤​M​\(R\)−1​ei\\Delta\_\{i\}\\leftarrow\\dfrac\{w\(c\_\{i\}\)\\,\\\|M\(R\)^\{\-1\}e\_\{i\}\\\|^\{2\}\}\{1\+w\(c\_\{i\}\)\\,e\_\{i\}^\{\\top\}M\(R\)^\{\-1\}e\_\{i\}\}
//marginal gain, Eq\. \([3](https://arxiv.org/html/2607.09765#S4.E3)\)

4

i⋆←arg​maxi⁡Δi/cii^\{\\star\}\\leftarrow\\operatorname\*\{arg\\,max\}\_\{\\,i\}\\ \\Delta\_\{i\}/c\_\{i\}
//resolvent centrality per dollar, Eq\. \([5](https://arxiv.org/html/2607.09765#S5.E5)\)

5if*primaland∑j∈Rcj\+ci⋆\>B\\sum\_\{j\\in R\}c\_\{j\}\+c\_\{i^\{\\star\}\}\>B*thenreturn

RR
6

R←R∪\{i⋆\}R\\leftarrow R\\cup\\\{i^\{\\star\}\\\}; rank\-1 update of

M​\(R\)−1M\(R\)^\{\-1\}\(Sherman–Morrison\)

7if*frontierandH​\(R\)≤εH\(R\)\\leq\\varepsilon*thenreturn

RR
8

9return

RR

Algorithm 1Cost\-benefit greedy placement / budget–correctness frontier\. Prepend the Sviridenko seed\-enumeration of size≤3\{\\leq\}3for the\(1−1/e\)\(1\-1/e\)guarantee of Theorem[2](https://arxiv.org/html/2607.09765#Thmtheorem2); use lazy evaluation\[[7](https://arxiv.org/html/2607.09765#bib.bib7)\]for the inner loop\.
## 6The budget–correctness frontier

Inverting the greedy bound gives the central object, the least spend that certifies correctness:B⋆​\(ε\)B^\{\\star\}\(\\varepsilon\)from Problem[2](https://arxiv.org/html/2607.09765#Thmproblem2)\. On the complete graph it is exactly solvable in closed form; the same cost\-benefit greedy computes it on any other graph\.

###### Proposition 1\(exact coherence on the complete graph\)\.

OnKNK\_\{N\}, writeM​\(R\)=Λ−𝟏𝟏⊤M\(R\)=\\Lambda\-\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}withΛ=diag⁡\(δi\)\\Lambda=\\operatorname\{diag\}\(\\delta\_\{i\}\)andδi=N\+κ\+wi​1​\[i∈R\]\\delta\_\{i\}=N\+\\kappa\+w\_\{i\}\\,\\mathds\{1\}\[i\\in R\]\. Then the coherence has the closed form

H​\(R\)=S1\+S21−S1,S1=∑i1δi,S2=∑i1δi2\.H\(R\)=S\_\{1\}\+\\frac\{S\_\{2\}\}\{1\-S\_\{1\}\},\\qquad S\_\{1\}=\\sum\_\{i\}\\frac\{1\}\{\\delta\_\{i\}\},\\quad S\_\{2\}=\\sum\_\{i\}\\frac\{1\}\{\\delta\_\{i\}^\{2\}\}\.\(6\)HereM​\(R\)M\(R\)is positive definite forκ\>0\\kappa\>0, soS1<1S\_\{1\}<1andHHis strictly decreasing in eachwiw\_\{i\}\. Inverting \([6](https://arxiv.org/html/2607.09765#S6.E6)\) yields both the homogeneous minimal countk⋆​\(ε\)=min⁡\{k:H​\(k\)≤ε\}k^\{\\star\}\(\\varepsilon\)=\\min\\\{k:H\(k\)\\leq\\varepsilon\\\}, defined for anyε\\varepsilonabove the floorH​\(N\)H\(N\), and the frontierB⋆B^\{\\star\}over the cost\-coupled weights\. The formula is exact, matching the direct inverse to machine precision \(proof in[Appendix C](https://arxiv.org/html/2607.09765#A3)\)\.

Should a fixed budget buy a few strong oracles or many medium ones? On the complete graph the whole answer is a sharp dichotomy, decided by one scalar of the cost–quality lawww: its curvature\.

###### Theorem 3\(curvature dichotomy: spread versus concentrate\)\.

Let a budgetB\>0B\>0be allocated onKNK\_\{N\}over oracles of costsci≥0c\_\{i\}\\geq 0with∑ici=B\\sum\_\{i\}c\_\{i\}=Band strengthswi=w​\(ci\)w\_\{i\}=w\(c\_\{i\}\), and let the placement minimize the coherence \([6](https://arxiv.org/html/2607.09765#S6.E6)\)\. Then the optimum is decided by the sign of\(N\+κ\+w\)​w′′−3​\(w′\)2\(N\+\\kappa\+w\)\\,w^\{\\prime\\prime\}\-3\(w^\{\\prime\}\)^\{2\}on\[0,B\]\[0,B\]\.

- \(i\)Ifwwis concave, this quantity is negative, and the minimizer is unique and uniform,ci⋆=B/Nc\_\{i\}^\{\\star\}=B/N\. In this case the equal\-split coherenceH​\(m\)H\(m\)overmmoracles of costB/mB/mis strictly decreasing inmm, so the budget optimally buysNNmedium correctors\.
- \(ii\)If instead \(N\+κ\+w​\(c\)\)​w′′​\(c\)≥3​\(w′​\(c\)\)2for all​c∈\[0,B\],\(N\+\\kappa\+w\(c\)\)\\,w^\{\\prime\\prime\}\(c\)\\ \\geq\\ 3\\,\(w^\{\\prime\}\(c\)\)^\{2\}\\qquad\\text\{for all \}c\\in\[0,B\],\(7\)then the minimizer places the entire budget on a single oracle\.

In both cases the\(1−1/e\)\(1\-1/e\)guarantee of Theorem[2](https://arxiv.org/html/2607.09765#Thmtheorem2)and the frontierB⋆​\(ε\)B^\{\\star\}\(\\varepsilon\)are unchanged; only the location of the optimum moves\.

###### Proof\.

Writeg​\(c\)=1/\(N\+κ\+w​\(c\)\)g\(c\)=1/\(N\+\\kappa\+w\(c\)\), so \([6](https://arxiv.org/html/2607.09765#S6.E6)\) readsH=S1\+S2/\(1−S1\)H=S\_\{1\}\+S\_\{2\}/\(1\-S\_\{1\}\)withS1=∑ig​\(ci\)S\_\{1\}=\\sum\_\{i\}g\(c\_\{i\}\)andS2=∑ig​\(ci\)2S\_\{2\}=\\sum\_\{i\}g\(c\_\{i\}\)^\{2\}\. Case \(i\) is Theorem[5](https://arxiv.org/html/2607.09765#Thmtheorem5)\. Under Assumption[1](https://arxiv.org/html/2607.09765#Thmassumption1)bothggandg2g^\{2\}are convex, so a pairwise\-balancing exchange strictly lowersHHoff the equal point and the unique minimizer is constant; strict monotonicity inmmis Theorem[6](https://arxiv.org/html/2607.09765#Thmtheorem6)\. Case \(ii\) is Remark[7](https://arxiv.org/html/2607.09765#Thmremark7), where the factor33is shown to be sharp: it is the curvature at whichg2g^\{2\}turns concave\. Plain convexity ofwwis not enough, because the leverage term\(w′\)2\(w^\{\\prime\}\)^\{2\}keeps the spread optimal below that threshold\. The full argument is in[Appendix D](https://arxiv.org/html/2607.09765#A4)\. ∎

###### Corollary 1\(minimal oracle count\)\.

Under homogeneous costsci≡1c\_\{i\}\\equiv 1and strengthswi≡ww\_\{i\}\\equiv w, Problem[2](https://arxiv.org/html/2607.09765#Thmproblem2)is a pure cardinality problem andB⋆​\(ε\)=k⋆​\(ε\)B^\{\\star\}\(\\varepsilon\)=k^\{\\star\}\(\\varepsilon\)\. On the complete graph symmetry makes greedy exact, sok⋆​\(ε\)k^\{\\star\}\(\\varepsilon\)is read off the strictly decreasingH​\(k\)H\(k\)of Proposition[1](https://arxiv.org/html/2607.09765#Thmproposition1)directly\. This recovers the homogeneous corrector placement of\[[1](https://arxiv.org/html/2607.09765#bib.bib1)\]as the unit\-cost limit\.

Figure[1](https://arxiv.org/html/2607.09765#S6.F1)shows both halves on a random graph: at a fixed budget the concave \(real\-LLM\) law is minimized by spreading over many medium correctors while a sharply convex law \(Eq\. \([7](https://arxiv.org/html/2607.09765#S6.E7)\)\) concentrates on a few strong ones, and the cost\-benefit greedy reaches a lower error per unit budget than degree\-based or random placement\.

![Refer to caption](https://arxiv.org/html/2607.09765v1/figures/stageA.png)Figure 1:Stage A on a random graph\.\(a\) at a fixed budget the truth\-tracking errorH/H0H/H\_\{0\}is minimized by spreading over many medium correctors whenwwis concave \(the regime we measure for Qwen3 in Section[7](https://arxiv.org/html/2607.09765#S7)\) and by concentrating on a few strong ones whenwwis sharply convex \(Eq\. \([7](https://arxiv.org/html/2607.09765#S6.E7)\); Theorem[3](https://arxiv.org/html/2607.09765#Thmtheorem3)\)\. \(b\) cost\-benefit greedy placement reaches a lower error per unit budget than degree\-based or random placement \(Theorem[2](https://arxiv.org/html/2607.09765#Thmtheorem2)\)\.The frontier itself is shown in Fig\.[2](https://arxiv.org/html/2607.09765#S6.F2): greedy reaches a target error at a smaller budget than random \(Bgreedy⋆<Brand⋆B^\{\\star\}\_\{\\mathrm\{greedy\}\}<B^\{\\star\}\_\{\\mathrm\{rand\}\}\), and for the coherence criterion the minimal budget is a constant fraction ofNN, above the worst\-case∼1/d\\sim\\\!1/d\.

![Refer to caption](https://arxiv.org/html/2607.09765v1/figures/frontier.png)Figure 2:The budget–correctness frontier\.\(a\) greedy placement reaches a target errorε\\varepsilonat a smaller budget than random, soBgreedy⋆<Brand⋆B^\{\\star\}\_\{\\mathrm\{greedy\}\}<B^\{\\star\}\_\{\\mathrm\{rand\}\}\. \(b\) for the coherence objective the minimal budgetk⋆k^\{\\star\}is a constant fraction ofNN\(here≈0\.3\{\\approx\}0\.3at mean degreed=6d\{=\}6\), well above the worst\-caseλmin\\lambda\_\{\\min\}scaling∼1/d\\sim\\\!1/d\.
## 7Measuring the cost–quality law

Theorem[3](https://arxiv.org/html/2607.09765#Thmtheorem3)makes the deployment answer hinge on one empirical property: the curvature of the real cost–quality laww​\(c\)w\(c\)\. Measuring it cleanly means controlling three things that defeat a naive attempt\. We sweep a single model family \(five Qwen3 models\[[20](https://arxiv.org/html/2607.09765#bib.bib20)\]from0\.60\.6to1414B, plus a3232B top\-end check\) so size is not confounded with family\. We calibrate task difficulty: each verifier is shown the evidence and two candidate answers, the gold one and a plausible same\-topic hallucination drawn from PsiloQA\[[19](https://arxiv.org/html/2607.09765#bib.bib19)\], and must choose which the evidence supports \(a two\-alternative forced choice, 2\-AFC;n=200n\{=\}200, both answer orders to cancel position bias\); an easier variant with blatantly contradictory distractors saturated the larger models near0\.970\.97and revealed nothing\. And we score by the model’s log\-probability of the gold choice rather than by parsing its free text, which otherwise penalizes models that do not follow the answer format\. The resulting strengthww\(the position\-averaged probability of the gold choice\) is a proxy for the abstract pin strengthwiw\_\{i\}, a link we do not otherwise validate\.

The measured law is concave\. Strength rises steeply from0\.860\.86at0\.60\.6B to0\.940\.94at1\.71\.7B, then saturates near0\.950\.95; a3232B top\-end point lands on the same∼0\.96\{\\sim\}0\.96plateau, and the88–3232B change\-of\-slope confidence interval \(CI\) straddles zero, so the law does not re\-accelerate at the top \(Fig\.[4](https://arxiv.org/html/2607.09765#S7.F4)\)\. A bootstrap test on the change of slope confirms the diminishing returns: the0\.60\.6–44B change\-of\-slope confidence interval lies entirely below zero, while the later segments are flat at the plateau\. This concavity is not an artifact of the bounded probability scale: it survives mapping the strength through a logit transform into an unbounded range, where the change\-of\-slope confidence interval stays entirely negative\. On this task corrector strength therefore saturates by about22B; past that point extra parameters buy almost no extra correction\. This is exactly the concave regime of Theorem[3](https://arxiv.org/html/2607.09765#Thmtheorem3), and it makes the deployment reading concrete: a fixed budget buys far more average correctness as many small\-but\-adequate correctors than as a few large ones\. The verdict is robust to measurement noise: resampling the per\-item scores, refitting the law, and recomputing the budget\-optimal placement onKNK\_\{N\}, the optimum spreads in100%100\\%of40004000bootstrap resamples\. The one scope caveat is the plateau location, not the sign: it is task\-dependent, which we now measure directly rather than leave to conjecture\.

To test the location claim instead of asserting it, we grade PsiloQA difficulty by the natural\-language\-inference \(NLI\) contradiction between the gold answer and its hallucinated twin and rerun the0\.60\.6–1414B ladder on three disjoint bands: blatant distractors \(easy, contradiction≥0\.5\{\\geq\}0\.5\), subtle ones \(hard,\[0\.10,0\.45\)\[0\.10,0\.45\)\), and the subtlest \(very hard,\[0\.02,0\.10\)\[0\.02,0\.10\), sharing no items with the hard band\)\. The plateau forms later as the distractors get subtler\. Between1\.71\.7and44B the easy and hard curves are flat \(paired\-bootstrap slope CIs\[−0\.002,\+0\.008\]\[\-0\.002,\+0\.008\]and\[−0\.004,\+0\.011\]\[\-0\.004,\+0\.011\]\), whereas the very\-hard curve is still rising there \(paired CI\[\+0\.005,\+0\.021\]\[\+0\.005,\+0\.021\], excluding zero; Fig\.[3](https://arxiv.org/html/2607.09765#S7.F3)\)\. Fittingw​\(c\)=w¯​\(1−e−c/c0\)w\(c\)=\\bar\{w\}\(1\-e^\{\-c/c\_\{0\}\}\)to each band gives a characteristic saturation scalec0c\_\{0\}that grows monotonically with difficulty,0\.20→0\.25→0\.310\.20\\to 0\.25\\to 0\.31B\. The curvature stays concave on all three bands\. We use a paired bootstrap because the two model sizes score the same items \(per\-item correlation≈0\.73\{\\approx\}0\.73on this band\); under the more conservative independent bootstrap the very\-hard slope is only marginal \(CI\[−0\.002,\+0\.028\]\[\-0\.002,\+0\.028\]\), so we read the difficulty\-dependence of the plateau location as suggestive, not decisive\. The concave sign is what the deployment verdict needs, and that is robust across all three bands\.

![Refer to caption](https://arxiv.org/html/2607.09765v1/figures/difficulty_sweep.png)Figure 3:The saturation scale grows as the task gets harder\.The same Qwen3 ladder \(0\.60\.6–1414B, logprob 2\-AFC,n=200n\{=\}200\) on three disjoint PsiloQA difficulty bands, graded by the gold–hallucination NLI contradiction\. Easy and hard distractors are flat between1\.71\.7and44B; the subtlest band is still rising there \(paired\-bootstrap slope CI excludes zero; marginal under an independent bootstrap\)\. The fitted scalec0c\_\{0\}inw=w¯​\(1−e−c/c0\)w=\\bar\{w\}\(1\-e^\{\-c/c\_\{0\}\}\)grows0\.20→0\.25→0\.310\.20\\to 0\.25\\to 0\.31B\. Error bars are95%95\\%bootstrap CIs\. The curvature is concave in every band, so spreading stays optimal; only where the plateau sets in shifts\.![Refer to caption](https://arxiv.org/html/2607.09765v1/figures/w_of_c.png)Figure 4:The measured cost–quality law is concave \(Qwen3,0\.60\.6–3232B,n=200n\{=\}200\)\.Each model chooses, from the evidence, between the gold answer and a plausible hallucination \(PsiloQA\);wwis the model’s probability of the gold choice \(scored from token log\-probabilities\), position\-averaged over both answer orders \(solid: continuous,95%95\\%bootstrap CI; dashed: robust pick in both orders\)\. Strength rises steeply to∼1\.7\{\\sim\}1\.7B then saturates; the0\.60\.6–44B change\-of\-slope CI is below zero \(significant diminishing returns\) and the later segments are flat\. The single family removes the model\-family confound and the linear axis does not flatter the curvature\. By Theorem[3](https://arxiv.org/html/2607.09765#Thmtheorem3)this concavity makes spreading the budget optimal\.*A second family\.*The concave saturation is not a Qwen idiosyncrasy\. Rerunning the identical22\-AFC protocol on the same PsiloQA hard band with the architecturally distinct Gemma\-4 ladder\[[21](https://arxiv.org/html/2607.09765#bib.bib21)\]\(E2B/E4B/1212B, plus a3131B top\-end check\) reproduces it: strength plateaus near∼0\.95\{\\sim\}0\.95, flat from22to3131B \(Fig\.[5](https://arxiv.org/html/2607.09765#S7.F5)\)\. If anything the newer family saturates earlier, already at the ceiling by22B, so extra parameters buy even less correction than on Qwen3 and the deployment verdict \(spread over many medium correctors\) holds a fortiori\. This meets the single\-family caveat with a second vendor and architecture\.

*A different task\.*Family and difficulty are not the only axes; the task type moves the plateau too\. On a math\-reasoning22\-AFC built from GSM8K \(the worked solution as evidence, a plausible arithmetic\-slip distractor\) the Qwen3 ladder is again concave, with the1\.71\.7–44–88B change\-of\-slope CI entirely negative \(\[−0\.038,−0\.012\]\[\-0\.038,\-0\.012\]\)\. It saturates later and higher than factual recall: the significant gains run through44B and the plateau sits near∼0\.98\{\\sim\}0\.98rather than∼0\.95\{\\sim\}0\.95\. The concave sign, and with it the spreading verdict, survives the task change; only where the plateau sets in shifts, consistent with the difficulty sweep\. A code\-tracing22\-AFC \(predict a program’s printed output\), a task needing a capability that emerges only with scale, realizes the other, convex branch: on demanding programs the whole ladder stays at chance \(0\.490\.49to0\.570\.57over0\.60\.6–3232B, no usable verifier\), while on tractable programs the law is sigmoidal: flat at chance through1\.71\.7B, then a convex emergent rise \(0\.49→0\.56→0\.60→0\.720\.49\\to 0\.56\\to 0\.60\\to 0\.72from1\.71\.7to1414B, robust both\-order accuracy climbing0\.04→0\.550\.04\\to 0\.55\) before saturating at∼0\.72\{\\sim\}0\.72\. So the concave \(spread\) and convex \(concentrate\) regimes of Theorem[3](https://arxiv.org/html/2607.09765#Thmtheorem3)are both empirically instantiated, and the curvature, and with it the deployment verdict, is genuinely task\-dependent: factual and math verification saturate concavely \(spread\), while emergent code tracing rises convexly \(concentrate up to the knee\)\.

![Refer to caption](https://arxiv.org/html/2607.09765v1/figures/crossfamily.png)Figure 5:The concave law replicates across families\.The Qwen3 \(0\.60\.6–3232B\) and Gemma\-4 \(E2B/E4B/1212/3131B\) ladders on the same PsiloQA hard band, same22\-AFC logprob protocol \(n=200n\{=\}200\)\. Both rise then plateau near∼0\.95\{\\sim\}0\.95; the newer Gemma\-4 saturates earlier\. Error bars are95%95\\%bootstrap CIs;xx\-axis is nominal size \(log\)\.The full budget–correctness sweep \(greedy versus random placement againstB⋆​\(ε\)B^\{\\star\}\(\\varepsilon\), and the Stage\-B phase transition of Section[8](https://arxiv.org/html/2607.09765#S8)\) calibrates onlyκ\\kappaand the measuredw​\(c\)w\(c\); the theory remains the primary deliverable\.

## 8Stage B: the high\-probability frontier

Stage A studied a linear consensus and its average error\. Stage B asks the same budgeting question \(how many oracles, and where\) of a nonlinear majority dynamics, and asks it in a stronger form: not whether the average error is small, but whether truth wins with high probability\. The two stages model one deployment problem from two angles\. They are in fact one dynamical system: Stage A is the linearization of Stage B about the truth\-consensus, so the same grounded operatorM​\(R\)M\(R\)governs both \(Remark[6](https://arxiv.org/html/2607.09765#Thmremark6)\); far from consensus, though, the nonlinear threshold studied here is a genuinely sharper, non\-spectral object\.

The model is a majority cascade\. Each agentjjholds a±1\\pm 1beliefxjx\_\{j\}and, at each step, copies the majority vote of its neighbours, correctly with reliabilitypr∈\(0,1\)p\_\{\\mathrm\{r\}\}\\in\(0,1\)and at random otherwise\. A setRRofkkoracles is pinned to\+1\+1\(truth\), a setFFofffseeds is pinned to−1\-1\(a planted falsehood\), and the remaining agents are free; writeρR=k/N\\rho\_\{R\}=k/NandρF=f/N\\rho\_\{F\}=f/Nfor the oracle and seed fractions\. We study two initial conditions for the free agents: a*balanced start*, where each free agent is±1\\pm 1independently with equal probability \(initial magnetizationO​\(1/N\)O\(1/\\sqrt\{N\}\), so no starting majority\), and an*established\-falsehood start*, where every free agent begins at−1\-1\. Throughout, “with high probability” means with probability1−o​\(1\)1\-o\(1\)asN→∞N\\to\\infty\. The question is whether truth wins the final consensus\. Simulation shows a sharp*phase transition*in the oracle count \(Fig\.[8](https://arxiv.org/html/2607.09765#S8.F8)\): the probability that truth wins jumps from near0to near11at a critical count\. That critical fractionk⋆/Nk^\{\\star\}/Nbarely depends onNN, and the jump sharpens asNNgrows, a genuine thermodynamic threshold rather than a smooth crossover\. Concentrating the oracles on high\-leverage nodes roughly halves the number needed\.

On the complete graph the threshold is the count balancek\>fk\>f, sharp in the fraction \(a margink−f≫Nk\-f\\gg\\sqrt\{N\}; Proposition[3](https://arxiv.org/html/2607.09765#Thmproposition3)\)\. On a general graph it becomes a degree\-weighted*influence balance*,DR\>DFD\_\{R\}\>D\_\{F\}, whereDR=∑i∈RdiD\_\{R\}=\\sum\_\{i\\in R\}d\_\{i\}andDF=∑j∈FdjD\_\{F\}=\\sum\_\{j\\in F\}d\_\{j\}are the total degrees of the oracle and seed sets anddid\_\{i\}is the degree of nodeii: what counts is not the number of oracles but their total degree\. Random placement therefore needsk⋆k^\{\\star\}just aboveff, while placing them on the highest\-degree nodes needs onlyk⋆≈f​d¯/dmaxk^\{\\star\}\\approx f\\,\\bar\{d\}/d\_\{\\max\}, withd¯\\bar\{d\}the mean degree anddmaxd\_\{\\max\}the largest \(Fig\.[8](https://arxiv.org/html/2607.09765#S8.F8), within≈5%\{\\approx\}5\\%\)\. This is the placement counterpart of the continuous\-gain synergy threshold of\[[13](https://arxiv.org/html/2607.09765#bib.bib13)\]\.

*Real agents confirm it\.*The leverage advantage is not only a feature of the idealized dynamics\. In a content\-free opinion\-consensus swarm of real LLM agents \(Qwen3\-1\.7B,N=25N\{=\}25on a heavy\-tailed Barabási–Albert graph withd¯/dmax=0\.26\\bar\{d\}/d\_\{\\max\}=0\.26,4040trials\), correctors placed on the highest\-degree nodes reach truth\-consensus atk⋆≈1\.7k^\{\\star\}\{\\approx\}1\.7, while random placement needsk⋆≈7k^\{\\star\}\{\\approx\}7\(Fig\.[6](https://arxiv.org/html/2607.09765#S8.F6)\), a4×4\\timessaving that matches the predicted ratiod¯/dmax\\bar\{d\}/d\_\{\\max\}\. Isolating the dynamics is what makes the effect visible: on factual questions a grounded agent leans on its own evidence rather than its neighbours, washing the placement effect out; the content\-free vote exposes the majority\-copy mechanism the threshold describes\.

*The correctors can be real reasoning agents, not stubborn pins\.*The swarm above fixes each corrector to the truth by fiat\. We can instead let every corrector be an actual reasoning agent: a Qwen3\-4B model that reads the question with its grounding evidence, thinks in a chain of thought, and commits to an answer\. Its reliability is then whatever the model achieves, an emergentq¯=0\.893\\bar\{q\}=0\.893on the hard hallucination band rather than a knob \(swarm\_llm\_correctors\.py;N=25N\{=\}25,f=6f\{=\}6,3030question draws from a200200\-item pool, truth balanced across A and B within each corrector’s ten\-sample batch so position is not a confound\)\. That reliability is bimodal:2323of the3030items are answered unanimously and the rest fall between0\.30\.3and0\.90\.9\. Seating these real correctors on the high\-degree nodes reaches theP=1/2P\{=\}1/2majority\-crossing with much less budget than random placement:k⋆=3\.8k^\{\\star\}\{=\}3\.8under leverage versusk⋆=10k^\{\\star\}\{=\}10under random\. The separation is significant even at this size \(leverage over random,z=2\.98z\{=\}2\.98atk=4k\{=\}4andz=2\.36z\{=\}2\.36atk=6k\{=\}6; Wilson95%95\\%intervals in Fig\.[6](https://arxiv.org/html/2607.09765#S8.F6)\)\. The leverage curve reaches the coin\-flip level rather than certainty, so we readk⋆k^\{\\star\}as the budget to parity, not to truth\. Against an i\.i\.d\. Bernoulli\(q¯\)\(\\bar\{q\}\)pin, the synthetic fallible corrector of Fig\.[7](https://arxiv.org/html/2607.09765#S8.F7)a, the real agents match under random placement \(both cross only at the boundaryk=10k\{=\}10\)\. Their reasoning errors are, however, correlated by question difficulty rather than independent, as documented for LLMs more broadly\[[3](https://arxiv.org/html/2607.09765#bib.bib3)\]; the per\-trial correctness variance is4\.7×4\.7\\timesthe i\.i\.d\. value \(intraclass correlationρ≈0\.41\\rho\\approx 0\.41\), so on an easy item every corrector agrees and the hubs carry the truth together\. Atn=30n\{=\}30this correlation does not resolve a significant advantage over the i\.i\.d\. proxy under leverage, so we claim only that real reasoning correctors reproduce the leverage effect, not that they beat the synthetic model\.

![Refer to caption](https://arxiv.org/html/2607.09765v1/figures/placement.png)Figure 6:Leverage placement in a real LLM swarm\.P​\(truth wins\)P\(\\text\{truth wins\}\)versus corrector countkkfor high\-degree \(leverage\) and random placement in a content\-free opinion\-consensus swarm \(Qwen3\-1\.7B,N=25N\{=\}25,f=6f\{=\}6false seeds,4040trials; Wilson95%95\\%intervals\)\. Leverage crossesP=1/2P\{=\}1/2atk⋆≈1\.7k^\{\\star\}\{\\approx\}1\.7versus≈7\{\\approx\}7for random, matching the predictedd¯/dmax\\bar\{d\}/d\_\{\\max\}\.*Spread, or concentrate?*The two stages advise along orthogonal axes, and “concentrate” means different things in each\. Stage A sets the granularity of spend: under a concave cost–quality law, split the budget into many medium oracles rather than a few strong ones\. Stage B sets the position: seat whatever oracles one buys on the highest\-leverage \(highest\-degree\) nodes\. Stage A’s “concentrate” \(few strong oracles, under convexww\) is a claim about strength per oracle; Stage B’s “concentrate on high\-degree” is a claim about which nodes to occupy, so the two recommendations are not in direct conflict\. They compose under a precise condition, which we can now state because the fallible generalization below \(Proposition[2](https://arxiv.org/html/2607.09765#Thmproposition2)\) supplies the missing ingredient: Stage\-B oracles with a cost\-coupled reliability rather than infallible hard pins\. By Corollary[2](https://arxiv.org/html/2607.09765#Thmcorollary2), a Stage\-A placement wins the Stage\-B cascade with fallible correctors of reliabilityqiq\_\{i\}\(their measured accuracy\) exactly when the reliability\-weighted balance holds and no single fallible corrector’s degree exceeds the residual truth margin it leaves\. Spreading the budget over many medium correctors keeps that safety margin satisfied, so “many medium correctors on high\-degree nodes” is composition\-safe; concentrating a medium\-reliability corrector on one dominant hub is not: it broadcasts its own error rate to the whole swarm\.

###### Proposition 2\(fallible, strength\-weighted correctors\)\.

Let each correctori∈Ri\\in Rhold the truth with reliabilityqi∈\(12,1\]q\_\{i\}\\in\(\\tfrac\{1\}\{2\},1\]and each seedj∈Fj\\in Fhold the falsehood with reliabilityqseedq\_\{\\mathrm\{seed\}\}, so a pinned node emits mean spin2​q−12q\-1\. In the dense\-graph regime of Theorem[4](https://arxiv.org/html/2607.09765#Thmtheorem4)\(p​N≥C​log⁡NpN\\geq C\\log N\), the free population reaches the truth\-consensus if and only if the reliability\-weighted influence balance

∑i∈Rdi​\(2​qi−1\)\>∑j∈Fdj​\(2​qseed−1\)\\sum\_\{i\\in R\}d\_\{i\}\\,\(2q\_\{i\}\-1\)\\ \>\\ \\sum\_\{j\\in F\}d\_\{j\}\\,\(2q\_\{\\mathrm\{seed\}\}\-1\)\(8\)holds and no single corrector dominates the free agents it feeds:difree≤μ−id\_\{i\}^\{\\mathrm\{free\}\}\\leq\\mu\_\{\-i\}, wheredifreed\_\{i\}^\{\\mathrm\{free\}\}is the number of free agents correctoriifeeds andμ−i\\mu\_\{\-i\}is the net signed margin those agents receive from all other pins\.

We identifyqiq\_\{i\}with the measured22\-AFC accuracy of Section[7](https://arxiv.org/html/2607.09765#S7)\. The balance has three readings\. OnKNK\_\{N\}it reduces to a sum\-of\-margins test,∑i∈R\(2​qi−1\)\>∑j∈F\(2​qseed−1\)\\sum\_\{i\\in R\}\(2q\_\{i\}\-1\)\>\\sum\_\{j\\in F\}\(2q\_\{\\mathrm\{seed\}\}\-1\), so extra correctors help only when their reliability margins beat the seeds’\. Asqi→1q\_\{i\}\\to 1it factorizes to the infallible balanceDR\>DFD\_\{R\}\>D\_\{F\}\([Appendix E](https://arxiv.org/html/2607.09765#A5)\)\. The dominance condition is what makes composition safe: if it fails, a corrector that draws wrong flips the whole free population, so the consensus tracks that corrector’s reliability rather than the truth\.

###### Corollary 2\(when the two stages compose\)\.

A Stage\-A budgeted placementRRalso wins the Stage\-B cascade iff \([8](https://arxiv.org/html/2607.09765#S8.E8)\) holds anddifree≤μ−id\_\{i\}^\{\\mathrm\{free\}\}\\leq\\mu\_\{\-i\}for every fallible corrector\. The concave\-ww“spread” prescription of Theorem[3](https://arxiv.org/html/2607.09765#Thmtheorem3)keeps the second condition satisfied; a high\-degree node given only medium reliability violates it and can invert the balance\.

*Real agents confirm the mechanism\.*Two checks in a real weak\-LLM swarm bear out Proposition[2](https://arxiv.org/html/2607.09765#Thmproposition2)\(Fig\.[7](https://arxiv.org/html/2607.09765#S8.F7)\)\. \(a\) When the correctors are made fallible at a tunable reliabilityqq\(free agents Qwen3\-1\.7B copying neighbours\), the truth\-win probability rises linearly in the effective strength2​q−12q\-1\(r=0\.98r=0\.98, crossing12\\tfrac\{1\}\{2\}nearq≈0\.7q\\approx 0\.7\): the measured reliability enters the swarm exactly as the2​q−12q\-1weight of \([8](https://arxiv.org/html/2607.09765#S8.E8)\), closing the accuracy\-to\-pin\-strength proxy gap empirically\. Feeding in the actual measured hard\-band strengths rather than a synthetic knob reproduces this end to end: truth\-win probability climbs with the ladder value \(0\.700\.70for a0\.60\.6B corrector atw=0\.86w\{=\}0\.86up to∼0\.9\{\\sim\}0\.9at1414B,w=0\.96w\{=\}0\.96; correlation0\.940\.94\), so the measuredw​\(c\)w\(c\)predicts the real swarm outcome\. \(b\) The leverage\-placement advantage is present only when agents actually copy their neighbours: as grounding rises from a content\-free vote to full evidence, the gap between high\-degree and random placement collapses from\+0\.75\+0\.75to0, since grounded agents self\-correct and graph position stops mattering\.

![Refer to caption](https://arxiv.org/html/2607.09765v1/figures/swarm_mech.png)Figure 7:Two mechanism checks in a real LLM swarm\.\(a\) With fallible correctors,P​\(truth wins\)P\(\\text\{truth wins\}\)is linear in the effective strength2​q−12q\-1\(qq=reliability,r=0\.98r\{=\}0\.98\), so measured reliability is the effective pin weight of \([8](https://arxiv.org/html/2607.09765#S8.E8)\)\. \(b\) The leverage−\-random placement gap vanishes as agents become more grounded \(content\-free→\\topartial→\\tofull evidence\), confirming that placement matters only in the majority\-copy regime\. Swarms ofN=25N\{=\}25on a Barabási–Albert graph; panel \(a\)k=f=6k\{=\}f\{=\}6,4040trials; panel \(b\)k=4k\{=\}4,f=6f\{=\}6,1212questions\.![Refer to caption](https://arxiv.org/html/2607.09765v1/figures/phase_transition.png)Figure 8:The budget–correctness phase transition \(Stage B\)\.Majority\-cascade model:fffalse\-pinned seeds versuskktruth\-pinned oracles on an Erdős–Rényi swarm\. \(a\)P​\(truth wins\)\\mathrm\{P\}\(\\text\{truth wins\}\)jumps sharply with the oracle count, and leverage placement reaches certainty at roughly half the oracles random placement needs \(k⋆≈f​d¯/dmaxk^\{\\star\}\\approx f\\bar\{d\}/d\_\{\\max\}versusff\)\. \(b\) against the oracle fractionk/Nk/Nthe curves steepen withNNat anNN\-independent critical fraction, a genuine thermodynamic\-limit threshold, not a smooth crossover\. Estimated over400400trials with common random numbers acrosskk\(each scenario’s graph, seeds, and start reused, only the corrector set varying\), so every point is unbiased and the curves are smooth\.###### Proposition 3\(exact correctness threshold on the complete graph\)\.

ConsiderKNK\_\{N\}withkkagents pinned to truth\(\+1\)\(\+1\),ffpinned to a falsehood\(−1\)\(\-1\), and the rest free, each free agent updating synchronously to the sign of its neighbour\-sum with reliabilitypr∈\(0,1\)p\_\{\\mathrm\{r\}\}\\in\(0,1\)from a balanced start\. Then truth wins the final consensus with high probability whenk−f≫Nk\-f\\gg\\sqrt\{N\}and loses whenf−k≫Nf\-k\\gg\\sqrt\{N\}\. The transition has widthO​\(N\)O\(\\sqrt\{N\}\)in the count, so the critical fractionρR=ρF\\rho\_\{R\}=\\rho\_\{F\}, that isk\>fk\>f, is sharp asN→∞N\\to\\infty\(Fig\.[8](https://arxiv.org/html/2607.09765#S8.F8)b\)\. On a general graph, weighting each pin by its degree extends the balance to∑i∈Rdi\>∑j∈Fdj\\sum\_\{i\\in R\}d\_\{i\}\>\\sum\_\{j\\in F\}d\_\{j\}\.

###### Proof\.

Every free agent sees essentially the same neighbour\-sum, equal to the global signed totalS=∑jxjS=\\sum\_\{j\}x\_\{j\}\(the “field”\) up to anO​\(1\)O\(1\)correction, so all free agents flip the same way, tosign⁡\(S\)\\operatorname\{sign\}\(S\), and the system reduces to a single scalar update\. From the balanced start the initial field isS0=\(k−f\)\+O​\(N\)S\_\{0\}=\(k\-f\)\+O\(\\sqrt\{N\}\), theO​\(N\)O\(\\sqrt\{N\}\)coming from the free spins and the reliability glitches, and the update locks tosign⁡\(S0\)\\operatorname\{sign\}\(S\_\{0\}\)\. The stated thresholds follow\. ∎

Beyond the complete graph, the same threshold holds rigorously once the swarm mixes well\.

###### Theorem 4\(threshold on dense random graphs\)\.

Run the majority cascade of Proposition[3](https://arxiv.org/html/2607.09765#Thmproposition3)on the Erdős–Rényi graphG​\(N,p\)G\(N,p\)withp​N≥C​log⁡NpN\\geq C\\log N, at reliabilitypr∈\(0,1\)p\_\{\\mathrm\{r\}\}\\in\(0,1\)from a balanced start, withC,C′C,C^\{\\prime\}below absolute constants\. Then truth wins the consensus with high probability once the oracles beat the seeds by a vanishing margin,

k−f≥C′​N​log⁡N/p,k\-f\\ \\geq\\ C^\{\\prime\}\\sqrt\{N\\log N/p\},and the falsehood wins when the margin has the opposite sign\. Whenp​N=ω​\(log⁡N\)pN=\\omega\(\\log N\)this margin iso​\(N\)o\(N\), so the critical fraction is simplyρR=ρF\\rho\_\{R\}=\\rho\_\{F\}: any fixed surplus of oracles over seeds wins asN→∞N\\to\\infty, with transition widthO​\(N\)O\(\\sqrt\{N\}\)in the count\. At the sparse boundaryp​N=Θ​\(log⁡N\)pN=\\Theta\(\\log N\)the margin isΘ​\(N\)\\Theta\(N\), so there the balance is sharp only up to a constant\. On a graph with heterogeneous degrees the same balance holds by degree,DR\>DFD\_\{R\}\>D\_\{F\}\.

Sparsity alone does not break the threshold \(a sparse expander still mixes\); modularity does\. When false seeds cluster in one part of the network, the cascade is confined and resolves locally\.

###### Proposition 4\(community threshold on modular graphs\)\.

Partition the graph into internally dense communitiesC1,…,CKC\_\{1\},\\dots,C\_\{K\}and take the decoupling limit of vanishing inter\-community coupling\. Then each communityCℓC\_\{\\ell\}reaches truth with high probability if and only if its internal influence balance holds,

∑i∈R∩Cℓdi\>∑j∈F∩Cℓdj,\\sum\_\{i\\in R\\cap C\_\{\\ell\}\}d\_\{i\}\\ \>\\ \\sum\_\{j\\in F\\cap C\_\{\\ell\}\}d\_\{j\},and the global consensus is the size\-weighted majority of the communities\.

EachCℓC\_\{\\ell\}is itself dense and ER\-like, so this is Theorem[4](https://arxiv.org/html/2607.09765#Thmtheorem4)applied community by community\. Its consequence for placement is a covering requirement: the budget must win every seeded community on its own, rather than maximize one global influence score, so the simple dense\-graph ruleDR\>DFD\_\{R\}\>D\_\{F\}no longer suffices under clustered seeding\. For weak but nonzero coupling this per\-community resolution is observed in simulation on a stochastic block model\.

###### Proposition 5\(hysteresis on sparse random\-regular graphs\)\.

On a sparse randomdd\-regular graph there is a thresholdρR⋆​\(ρF\)\>ρF\\rho\_\{R\}^\{\\star\}\(\\rho\_\{F\}\)\>\\rho\_\{F\}such that the truth\-consensus is reached with high probability

- \(i\)from a balanced start, if and only ifρR\>ρF\\rho\_\{R\}\>\\rho\_\{F\}; and
- \(ii\)from an established\-falsehood start, if and only ifρR\>ρR⋆​\(ρF\)\\rho\_\{R\}\>\\rho\_\{R\}^\{\\star\}\(\\rho\_\{F\}\)\.

SinceρR⋆​\(ρF\)\>ρF\\rho\_\{R\}^\{\\star\}\(\\rho\_\{F\}\)\>\\rho\_\{F\}, forρR∈\(ρF,ρR⋆​\(ρF\)\)\\rho\_\{R\}\\in\(\\rho\_\{F\},\\rho\_\{R\}^\{\\star\}\(\\rho\_\{F\}\)\)the outcome depends on the initial configuration; this gap is the hysteresis\.

On a sparse graph the field no longer concentrates, so the two starts have distinct mechanisms\. Prevention is tracked by a*cavity recursion*for the fractionqqof free agents that settle at\+1\+1,

q=ρR\+\(1−ρR−ρF\)​\[pr​Pr⁡\(Bin​\(d−1,q\)\>d−12\)\+1−pr2\]\.q=\\rho\_\{R\}\+\(1\-\\rho\_\{R\}\-\\rho\_\{F\}\)\\big\[p\_\{\\mathrm\{r\}\}\\Pr\(\\mathrm\{Bin\}\(d\-1,q\)\>\\tfrac\{d\-1\}\{2\}\)\+\\tfrac\{1\-p\_\{\\mathrm\{r\}\}\}\{2\}\\big\]\.NearρR=ρF\\rho\_\{R\}=\\rho\_\{F\}and for reliable agents \(prp\_\{\\mathrm\{r\}\}near11\) it has three fixed points, so the dynamics are bistable and the outcome depends on the starting majority; glitches erode the metastable middle branch, and the bistable window survives only forρ≲0\.005\\rho\\lesssim 0\.005atpr=0\.9p\_\{\\mathrm\{r\}\}=0\.9\.

Dislodging is instead a monotone*bootstrap percolation*: a free node flips to\+1\+1once at least⌈d/2⌉\\lceil d/2\\rceilof its neighbours are\+1\+1, and stays\. The activated fractionzzobeys

z=ρR\+\(1−ρR−ρF\)​Pr⁡\(Bin​\(d−1,z\)≥⌈d/2⌉\),z=\\rho\_\{R\}\+\(1\-\\rho\_\{R\}\-\\rho\_\{F\}\)\\,\\Pr\\\!\\big\(\\mathrm\{Bin\}\(d\-1,z\)\\geq\\lceil d/2\\rceil\\big\),whose saddle\-node is the first\-order thresholdρR⋆\\rho\_\{R\}^\{\\star\}: atd=5d=5it is≈0\.28\\approx 0\.28asρF→0\\rho\_\{F\}\\to 0, rising to≈0\.32\\approx 0\.32atρF=0\.1\\rho\_\{F\}=0\.1, several timesρF\\rho\_\{F\}throughout\. The saddle\-node is rigorous\[[23](https://arxiv.org/html/2607.09765#bib.bib23)\], and simulation confirms it within about two percentage points ford=4,…,8d=4,\\dots,8\. This prevent\-versus\-dislodge hysteresis is the reversible bootstrap percolation of fake\-news spreading and fact\-checking\[[22](https://arxiv.org/html/2607.09765#bib.bib22)\], here specialized to a costed grounded\-Laplacian swarm with a placement objective\.

Adding the verification delay of\[[1](https://arxiv.org/html/2607.09765#bib.bib1)\]couples this budget axis to the dose–delay stability axis; both extensions are deferred to keep the present frontier closed\-form\.

## 9Conclusion

We framed multi\-agent correctness as a budgeting problem: how much to spend on strong correctors, and where to place them, so a weak swarm reaches truth\. Modelling the corrected swarm as a grounded\-Laplacian consensus, we showed the truth\-tracking error stays submodular under heterogeneous cost\-coupled pins\. A cost\-benefit greedy is therefore within1−1/e1\-1/eof optimal and yields a closed\-form budget–correctness frontierB⋆B^\{\\star\}, with a minimal oracle countk⋆k^\{\\star\}as its unit\-cost limit\. Whether that budget is best spent on a few strong correctors or many medium ones is decided by a single scalar, the curvature of the cost–quality law\. Measuring it on the Qwen3 ladder \(replicated on a second family\) finds the law concave for factual and math verification, saturating by about22–44B, so spreading wins and the “escalate to one strong model” default is suboptimal there; an emergent code\-tracing task instead rises convexly, so the verdict is genuinely task\-dependent and both regimes occur\. A high\-probability variant turns the frontier into a sharp phase transition whose threshold is an influence balance, exact on the complete graph\.

## 10Limitations

The analysis is linear, a grounded\-Laplacian consensus, and the verifier is an oracle\-but\-costly pin, so content\-level effects such as claim provenance and partial corrections are out of scope\. The frontierB⋆B^\{\\star\}is known beyond the complete graph, but only in the mean\. It is closed\-form on the complete graph\. On randomdd\-regular graphs it is the cavity fixed point of[Appendix F](https://arxiv.org/html/2607.09765#A6), exact in the replica\-symmetric limit and validated numerically\. On stochastic\-block\-model graphs it is the block cavity of[Appendix G](https://arxiv.org/html/2607.09765#A7), for arbitraryK×KK\\times Kmixing\. On directed swarms it is the reciprocated\-feedback cavity of[Appendix H](https://arxiv.org/html/2607.09765#A8), in which only mutual trust carries feedback\. The submodular placement guarantee does not extend to the directed case, since its proof uses the symmetry ofMM\. The Stage\-B threshold is exact on the complete graph, rigorous on dense expanders \(Theorem[4](https://arxiv.org/html/2607.09765#Thmtheorem4)\), and per\-community on modular graphs \(Proposition[4](https://arxiv.org/html/2607.09765#Thmproposition4)\); on unstructured sparse graphs it is hysteretic, the dislodge threshold being a first\-order bootstrap\-percolation transition \(Proposition[5](https://arxiv.org/html/2607.09765#Thmproposition5)\)\.

The single\-family measurement establishes the sign of the curvature \(concave\) atn=200n\{=\}200, but its scope is limited: one model family, parameter count as the cost proxy, and a strength that is itself a proxy for the abstract pin\. The concave sign is at least robust to the accuracy\-to\-strength link: it survives the identity and logit transforms, and because the saturation is per\-item \(not only in the mean\) it does not invert under any monotone increasing reparametrization of the quality axis we tested, including adversarial ones\. The saturation location is not fixed: a difficulty sweep \(Section[7](https://arxiv.org/html/2607.09765#S7)\) moves it from∼1\.7\{\\sim\}1\.7B on easy distractors to∼4\{\\sim\}4B on the subtlest, so we report it as task\-dependent rather than universal\. A sweep past1414B would pin the high end, and a dollar or latency cost axis changes nothing in the affine regime, where it agrees with parameter count \(Remark[4](https://arxiv.org/html/2607.09765#Thmremark4)\)\. The verification delay of\[[1](https://arxiv.org/html/2607.09765#bib.bib1)\]is left out to keep the frontier closed\-form\.

The real\-reasoning\-corrector confirmation \(Section[7](https://arxiv.org/html/2607.09765#S7)\) is a single configuration: one corrector model \(Qwen3\-4B\), one hallucination\-hardness band,3030question draws, oneN=25N\{=\}25Barabási–Albert realization\. It shows the leverage\-placement advantage survives emergent, difficulty\-correlated corrector errors, but does not sweep corrector strength, task difficulty, or graph ensemble, and its leverage curve reaches parity rather than certainty\.

### Reproducibility\.

All code and data are released at[https://github\.com/YehudaItkin/budgeted\-oracle\-placement](https://github.com/YehudaItkin/budgeted-oracle-placement)and seeded\. This covers the measurement, statistics, and figure scripts\. It covers the per\-item22\-AFC scores for the Qwen3 ladder \(factual, math, and code tasks\) and the Gemma\-4 ladder \(factual\)\. It covers the real\-swarm placement, fallible\-corrector, grounding\-sweep, and real\-reasoning\-corrector runs\. And it covers the placement, Stage\-B, and sparse\-graph, SBM, and directed\-graph cavity simulations\.

## References

- \[1\]I\. Itkin\. Delayed verification destabilizes multi\-agent LLM belief: instability thresholds and optimal corrector placement\. arXiv:2606\.27409 \(2026\)\.
- \[2\]I\. Neri, F\. L\. Metz\. Spectra of sparse non\-Hermitian random matrices: an analytical solution\.*Phys\. Rev\. Lett\.*109, 030602 \(2012\)\. arXiv:1205\.0702\.
- \[3\]E\. Kim, A\. Garg, K\. Peng, N\. Garg\. Correlated errors in large language models\.*ICML*\(2025\)\. arXiv:2506\.07962\.
- \[4\]M\. Yuan, K\. Pahwa, S\. Chang, et al\. Automated composition of agents: a knapsack approach for agentic component selection\.*NeurIPS*\(2025\)\. arXiv:2510\.16499\.
- \[5\]M\. Sviridenko\. A note on maximizing a submodular set function subject to a knapsack constraint\.*Oper\. Res\. Lett\.*32\(1\):41–43 \(2004\)\.
- \[6\]G\. L\. Nemhauser, L\. A\. Wolsey, M\. L\. Fisher\. An analysis of approximations for maximizing submodular set functions—I\.*Math\. Program\.*14:265–294 \(1978\)\.
- \[7\]J\. Leskovec, A\. Krause, C\. Guestrin, et al\. Cost\-effective outbreak detection in networks\.*KDD*\(2007\)\.
- \[8\]A\. Clark, B\. Alomair, L\. Bushnell, R\. Poovendran\.*Submodularity in Dynamics and Control of Networked Systems\.*Springer \(2016\)\.
- \[9\]E\. Mackin, S\. Patterson\. Submodular optimization for consensus networks with noise\-corrupted leaders\. arXiv:1712\.08212 \(2017\)\.
- \[10\]B\. Bamieh, M\. R\. Jovanović, P\. Mitra, S\. Patterson\. Coherence in large\-scale networks: dimension\-dependent limitations of local feedback\.*IEEE Trans\. Autom\. Control*57\(9\):2235–2249 \(2012\)\.
- \[11\]M\. Pirani, S\. Sundaram\. On the smallest eigenvalue of grounded Laplacian matrices\.*IEEE TAC*61\(2\):509–514 \(2016\)\. arXiv:1406\.2271\.
- \[12\]X\. Zhou, R\. Wang, W\. Li, Z\. Zhang\. Maximizing the smallest eigenvalue of the grounded Laplacian matrix\.*J\. Glob\. Optim\.*\(2025\)\. arXiv:2110\.12576\.
- \[13\]B\. Liu, L\. Kong, J\. Pei\. Phase transition for budgeted multi\-agent synergy\. arXiv:2601\.17311 \(2026\)\.
- \[14\]F\. Lin, M\. Fardad, M\. R\. Jovanović\. Algorithms for leader selection in stochastically forced consensus networks\.*IEEE TAC*59\(7\):1789–1802 \(2014\)\. arXiv:1302\.0450\.
- \[15\]A\. Krause, A\. Singh, C\. Guestrin\. Near\-optimal sensor placements in Gaussian processes\.*JMLR*9:235–284 \(2008\)\.
- \[16\]W\. Abbas, A\. Laszka, X\. Koutsoukos\. Improving network connectivity and robustness using trusted nodes with application to resilient consensus\.*IEEE TCNS*5\(4\):2036–2048 \(2018\)\.
- \[17\]H\. J\. LeBlanc, H\. Zhang, X\. Koutsoukos, S\. Sundaram\. Resilient asymptotic consensus in robust networks\.*IEEE JSAC*31\(4\):766–781 \(2013\)\.
- \[18\]L\. Chen, M\. Zaharia, J\. Zou\. FrugalGPT: how to use large language models while reducing cost and improving performance\. arXiv:2305\.05176 \(2023\)\.
- \[19\]E\. Rykov, et al\. When models lie, we learn: multilingual span\-level hallucination detection with PsiloQA\.*Findings of EMNLP*\(2025\)\. arXiv:2510\.04849\. Dataset:[https://huggingface\.co/datasets/s\-nlp/PsiloQA](https://huggingface.co/datasets/s-nlp/PsiloQA)\.
- \[20\]A\. Yang, et al\. \(Qwen Team\)\. Qwen3 technical report\. arXiv:2505\.09388 \(2025\)\.
- \[21\]Gemma Team, Google DeepMind\. Gemma 4\.[https://huggingface\.co/google/gemma\-4\-12B\-it](https://huggingface.co/google/gemma-4-12B-it)\(2026\)\.
- \[22\]M\. A\. Di Muro, S\. V\. Buldyrev, L\. A\. Braunstein\. Reversible bootstrap percolation: fake news and fact checking\.*Phys\. Rev\. E*101, 042307 \(2020\)\. arXiv:1910\.09516\.
- \[23\]J\. Balogh, B\. G\. Pittel\. Bootstrap percolation on the random regular graph\.*Random Struct\. Alg\.*30\(1–2\):257–286 \(2007\)\.

## Appendix Appendix AProof of Theorem[1](https://arxiv.org/html/2607.09765#Thmtheorem1)\(submodularity under heterogeneous pins\)

Throughout, fixκ\>0\\kappa\>0and write

M​\(R\)=L\+κ​I\+∑i∈Rwi​ei​ei⊤,H​\(R\)=tr⁡M​\(R\)−1,M\(R\)=L\+\\kappa I\+\\sum\_\{i\\in R\}w\_\{i\}\\,e\_\{i\}e\_\{i\}^\{\\top\},\\qquad H\(R\)=\\operatorname\{tr\}M\(R\)^\{\-1\},whereeie\_\{i\}is theii\-th standard basis vector, so thatei​ei⊤e\_\{i\}e\_\{i\}^\{\\top\}has a single nonzero entry, a11in position\(i,i\)\(i,i\)\. SinceL⪰0L\\succeq 0andκ\>0\\kappa\>0, the matrixM​\(R\)M\(R\)is symmetric positive definite andH​\(R\)H\(R\)is well defined\. We prove the three claims of the theorem in turn: the marginal\-gain formula, then monotonicity, then submodularity\.

*Marginal gain\.*Placing an oracle at nodeiiaddswi​ei​ei⊤w\_\{i\}e\_\{i\}e\_\{i\}^\{\\top\}toM​\(R\)M\(R\), a rank\-one update\. AbbreviateM=M​\(R\)M=M\(R\)\. The Sherman–Morrison identity inverts such an update in closed form,

\(M\+wi​ei​ei⊤\)−1=M−1−wi​M−1​ei​ei⊤​M−11\+wi​ei⊤​M−1​ei\.\\big\(M\+w\_\{i\}\\,e\_\{i\}e\_\{i\}^\{\\top\}\\big\)^\{\-1\}=M^\{\-1\}\-\\frac\{w\_\{i\}\\,M^\{\-1\}e\_\{i\}e\_\{i\}^\{\\top\}M^\{\-1\}\}\{1\+w\_\{i\}\\,e\_\{i\}^\{\\top\}M^\{\-1\}e\_\{i\}\}\.Take the trace of both sides\. The trace of the correction istr⁡\(M−1​ei​ei⊤​M−1\)=ei⊤​M−2​ei=‖M−1​ei‖2\\operatorname\{tr\}\\\!\\big\(M^\{\-1\}e\_\{i\}e\_\{i\}^\{\\top\}M^\{\-1\}\\big\)=e\_\{i\}^\{\\top\}M^\{\-2\}e\_\{i\}=\\\|M^\{\-1\}e\_\{i\}\\\|^\{2\}, so the reduction in coherence from adding the oracle is

Δi​\(R\)=H​\(R\)−H​\(R∪\{i\}\)=wi​‖M−1​ei‖21\+wi​ei⊤​M−1​ei≥0,\\Delta\_\{i\}\(R\)=H\(R\)\-H\(R\\cup\\\{i\\\}\)=\\frac\{w\_\{i\}\\,\\\|M^\{\-1\}e\_\{i\}\\\|^\{2\}\}\{1\+w\_\{i\}\\,e\_\{i\}^\{\\top\}M^\{\-1\}e\_\{i\}\}\\ \\geq\\ 0,which is \([3](https://arxiv.org/html/2607.09765#S4.E3)\)\. Numerator and denominator are both positive, so every oracle strictly lowersHH: the gain is the squared norm of theii\-th column ofM−1M^\{\-1\}, damped by the local diagonalei⊤​M−1​eie\_\{i\}^\{\\top\}M^\{\-1\}e\_\{i\}\.

*Monotonicity\.*Adding an oracle only increasesMMin the Loewner order,

M​\(R∪\{i\}\)=M​\(R\)\+wi​ei​ei⊤⪰M​\(R\),M\(R\\cup\\\{i\\\}\)=M\(R\)\+w\_\{i\}\\,e\_\{i\}e\_\{i\}^\{\\top\}\\ \\succeq\\ M\(R\),becausewi​ei​ei⊤⪰0w\_\{i\}e\_\{i\}e\_\{i\}^\{\\top\}\\succeq 0\. Inversion is order\-reversing on positive definite matrices, soM​\(R∪\{i\}\)−1⪯M​\(R\)−1M\(R\\cup\\\{i\\\}\)^\{\-1\}\\preceq M\(R\)^\{\-1\}, and taking traces givesH​\(R∪\{i\}\)≤H​\(R\)H\(R\\cup\\\{i\\\}\)\\leq H\(R\)\. Henceρ​\(R\)=H​\(∅\)−H​\(R\)\\rho\(R\)=H\(\\varnothing\)\-H\(R\)is non\-decreasing inRR, withρ​\(∅\)=0\\rho\(\\varnothing\)=0\.

*Submodularity\.*RegardHHas a smooth function of the strength vectorw=\(w1,…,wN\)≥0w=\(w\_\{1\},\\dots,w\_\{N\}\)\\geq 0, an oracle being present atiiexactly whenwi\>0w\_\{i\}\>0\. The derivative of a matrix inverse is

∂M−1∂wj=−M−1​∂M∂wj​M−1=−M−1​ej​ej⊤​M−1\.\\frac\{\\partial M^\{\-1\}\}\{\\partial w\_\{j\}\}=\-M^\{\-1\}\\frac\{\\partial M\}\{\\partial w\_\{j\}\}M^\{\-1\}=\-M^\{\-1\}e\_\{j\}e\_\{j\}^\{\\top\}M^\{\-1\}\.DifferentiateH=tr⁡M−1H=\\operatorname\{tr\}M^\{\-1\}once, usingtr⁡\(M−1​ei​ei⊤​M−1\)=\(M−2\)i​i\\operatorname\{tr\}\(M^\{\-1\}e\_\{i\}e\_\{i\}^\{\\top\}M^\{\-1\}\)=\(M^\{\-2\}\)\_\{ii\}:

∂H∂wi=tr⁡\(∂M−1∂wi\)=−\(M−2\)i​i\.\\frac\{\\partial H\}\{\\partial w\_\{i\}\}=\\operatorname\{tr\}\\\!\\Big\(\\frac\{\\partial M^\{\-1\}\}\{\\partial w\_\{i\}\}\\Big\)=\-\(M^\{\-2\}\)\_\{ii\}\.Differentiate a second time inwjw\_\{j\}\. The factorM−2=M−1​M−1M^\{\-2\}=M^\{\-1\}M^\{\-1\}has two copies ofM−1M^\{\-1\}andwjw\_\{j\}acts on each; the two contributions are equal by symmetry, so

∂2H∂wi​∂wj=−∂\(M−2\)i​i∂wj=2​\(M−1\)i​j​\(M−2\)i​j\.\\frac\{\\partial^\{2\}H\}\{\\partial w\_\{i\}\\,\\partial w\_\{j\}\}=\-\\frac\{\\partial\(M^\{\-2\}\)\_\{ii\}\}\{\\partial w\_\{j\}\}=2\\,\(M^\{\-1\}\)\_\{ij\}\\,\(M^\{\-2\}\)\_\{ij\}\.The sign of this cross\-derivative is fixed by one structural fact aboutMM\. Its off\-diagonal entries are−Ai​j≤0\-A\_\{ij\}\\leq 0, and it is positive definite, soM​\(R\)M\(R\)is a symmetric*M\-matrix*\. The inverse of an M\-matrix is entrywise nonnegative,M−1≥0M^\{\-1\}\\geq 0, and thereforeM−2=M−1​M−1≥0M^\{\-2\}=M^\{\-1\}M^\{\-1\}\\geq 0as well\. Both factors in2​\(M−1\)i​j​\(M−2\)i​j2\\,\(M^\{\-1\}\)\_\{ij\}\\,\(M^\{\-2\}\)\_\{ij\}are then nonnegative, so

∂2H∂wi​∂wj≥0for all​i,j​and all​w≥0\.\\frac\{\\partial^\{2\}H\}\{\\partial w\_\{i\}\\,\\partial w\_\{j\}\}\\ \\geq\\ 0\\qquad\\text\{for all \}i,j\\text\{ and all \}w\\geq 0\.Nonnegative mixed second derivatives are exactly the statement that each marginal gain shrinks as the other strengths grow\. Write the gain atiias the line integral

Δi​\(R\)=∫0wi\(−∂H∂wi\)​dwi=∫0wi\(M−2\)i​i​dwi\.\\Delta\_\{i\}\(R\)=\\int\_\{0\}^\{w\_\{i\}\}\\Big\(\-\\frac\{\\partial H\}\{\\partial w\_\{i\}\}\\Big\)\\,\\mathrm\{d\}w\_\{i\}=\\int\_\{0\}^\{w\_\{i\}\}\(M^\{\-2\}\)\_\{ii\}\\,\\mathrm\{d\}w\_\{i\}\.The integrand\(M−2\)i​i\(M^\{\-2\}\)\_\{ii\}is non\-increasing in every otherwjw\_\{j\}, soΔi​\(R\)≥Δi​\(S\)\\Delta\_\{i\}\(R\)\\geq\\Delta\_\{i\}\(S\)wheneverR⊆SR\\subseteq S\. This is submodularity ofρ=−H\\rho=\-H\.

The Loewner order alone does not deliver this last step\. Monotonicity ofM↦M−1M\\mapsto M^\{\-1\}in the Loewner sense does not control the*entrywise*signs ofM−1M^\{\-1\}for a general positive definiteMM, and it is those signs that make the cross\-derivative nonnegative\. A numerical sweep confirms both monotonicity and submodularity across the diminishing\-returns, linear, and uniform weight laws\.

## Appendix Appendix BProof of Theorem[2](https://arxiv.org/html/2607.09765#Thmtheorem2)

By Theorem[1](https://arxiv.org/html/2607.09765#Thmtheorem1)the reductionρ\\rhois monotone submodular withρ​\(∅\)=0\\rho\(\\varnothing\)=0, and the cost∑i∈Rci\\sum\_\{i\\in R\}c\_\{i\}is additive in the chosen oracles\. Maximizing a monotone submodular function under a single budget constraint is exactly the setting of\[[5](https://arxiv.org/html/2607.09765#bib.bib5)\]\. Its algorithm enumerates every seed set of at most three oracles, extends each seed by repeatedly adding the oracle of largest gain\-to\-cost ratio within budget, and returns the best placement found; the guarantee is attained on the branch whose seed is the three highest\-value oracles of the optimum\. Call its outputRgR\_\{g\}and letRB⋆R^\{\\star\}\_\{B\}be the optimum within budgetBB\. Then

ρ​\(Rg\)≥\(1−1/e\)​ρ​\(RB⋆\)\.\\rho\(R\_\{g\}\)\\ \\geq\\ \(1\-1/e\)\\,\\rho\(R^\{\\star\}\_\{B\}\)\.
The cost\-benefit greedy of Algorithm[1](https://arxiv.org/html/2607.09765#algorithm1)is this procedure run with the CELF lazy\-evaluation rule\[[7](https://arxiv.org/html/2607.09765#bib.bib7)\]\. Lazy evaluation changes only how the inner greedy step is computed, not which oracle it selects, so the\(1−1/e\)\(1\-1/e\)bound is untouched\. It uses submodularity \(marginal gains only shrink asRRgrows\) to skip recomputing gains that cannot be the current maximum, so a greedy step recomputes at mostO​\(\|𝒪\|\)O\(\|\\mathcal\{O\}\|\)gains, and typically far fewer, each anO​\(N\)O\(N\)read of one column of the maintained resolventM​\(R\)−1M\(R\)^\{\-1\}, withO​\(log⁡\|𝒪\|\)O\(\\log\|\\mathcal\{O\}\|\)priority\-queue overhead per recomputation\. Once the winner is committed,M​\(R\)−1M\(R\)^\{\-1\}is advanced by a single Sherman–Morrison rank\-one update, since adding one oracle changesM​\(R\)M\(R\)in a single diagonal entry\.

## Appendix Appendix CThe complete\-graph frontier and the curvature criterion

*Closed form \([6](https://arxiv.org/html/2607.09765#S6.E6)\)\.*On the complete graphKNK\_\{N\}the Laplacian isL=N​I−𝟏𝟏⊤L=NI\-\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}, where𝟏\\mathbf\{1\}is the all\-ones vector, so a placementRRgives

M​\(R\)=\(N\+κ\)​I−𝟏𝟏⊤\+diag⁡\(wi​1​\[i∈R\]\)=Λ−𝟏𝟏⊤,M\(R\)=\(N\+\\kappa\)I\-\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\+\\operatorname\{diag\}\\\!\\big\(w\_\{i\}\\,\\mathds\{1\}\[i\\in R\]\\big\)=\\Lambda\-\\mathbf\{1\}\\mathbf\{1\}^\{\\top\},withΛ=diag⁡\(δi\)\\Lambda=\\operatorname\{diag\}\(\\delta\_\{i\}\)diagonal andδi=N\+κ\+wi​1​\[i∈R\]\\delta\_\{i\}=N\+\\kappa\+w\_\{i\}\\,\\mathds\{1\}\[i\\in R\], matching Proposition[1](https://arxiv.org/html/2607.09765#Thmproposition1)\. This is a rank\-one downdate of the diagonalΛ\\Lambda, so Sherman–Morrison inverts it in closed form,

M​\(R\)−1=Λ−1\+Λ−1​𝟏𝟏⊤​Λ−11−𝟏⊤​Λ−1​𝟏\.M\(R\)^\{\-1\}=\\Lambda^\{\-1\}\+\\frac\{\\Lambda^\{\-1\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\Lambda^\{\-1\}\}\{1\-\\mathbf\{1\}^\{\\top\}\\Lambda^\{\-1\}\\mathbf\{1\}\}\.Take the trace and setS1=𝟏⊤​Λ−1​𝟏=∑iδi−1S\_\{1\}=\\mathbf\{1\}^\{\\top\}\\Lambda^\{\-1\}\\mathbf\{1\}=\\sum\_\{i\}\\delta\_\{i\}^\{\-1\}andS2=𝟏⊤​Λ−2​𝟏=∑iδi−2S\_\{2\}=\\mathbf\{1\}^\{\\top\}\\Lambda^\{\-2\}\\mathbf\{1\}=\\sum\_\{i\}\\delta\_\{i\}^\{\-2\}; usingtr⁡\(Λ−1​𝟏𝟏⊤​Λ−1\)=𝟏⊤​Λ−2​𝟏=S2\\operatorname\{tr\}\(\\Lambda^\{\-1\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\Lambda^\{\-1\}\)=\\mathbf\{1\}^\{\\top\}\\Lambda^\{\-2\}\\mathbf\{1\}=S\_\{2\}gives

H​\(R\)=tr⁡M​\(R\)−1=S1\+S21−S1,H\(R\)=\\operatorname\{tr\}M\(R\)^\{\-1\}=S\_\{1\}\+\\frac\{S\_\{2\}\}\{1\-S\_\{1\}\},which is \([6](https://arxiv.org/html/2607.09765#S6.E6)\)\. The matrix is positive definite exactly when1−S1\>01\-S\_\{1\}\>0, andκ\>0\\kappa\>0secures this, sinceδi≥N\+κ\\delta\_\{i\}\\geq N\+\\kappaforcesS1≤N/\(N\+κ\)<1S\_\{1\}\\leq N/\(N\+\\kappa\)<1\. The closed form matches the direct inverse to machine precision \(relative error∼10−15\{\\sim\}10^\{\-15\}over random heterogeneous placements\)\. In the homogeneous caseH​\(k\)H\(k\), withkkequal pins, is strictly decreasing inkk, so the minimal countk⋆​\(ε\)k^\{\\star\}\(\\varepsilon\)is obtained by invertingH​\(k\)=εH\(k\)=\\varepsilon\.

*Curvature criterion\.**Equal split at fixedmm\.*Writeθ:=N\+κ\\theta:=N\+\\kappaand, for an oracle of costcc, let

g​\(c\)=1θ\+w​\(c\)g\(c\)=\\frac\{1\}\{\\theta\+w\(c\)\}be the diagonal entry it contributes toΛ−1\\Lambda^\{\-1\}\. Fix the number of oracles atmmand let them carry costsc1,…,cmc\_\{1\},\\dots,c\_\{m\}with∑ici=B\\sum\_\{i\}c\_\{i\}=B\. TheN−mN\-munpinned nodes each contribute1/θ1/\\thetatoS1S\_\{1\}and1/θ21/\\theta^\{2\}toS2S\_\{2\}, constants at fixedmm, so the split entersHHonly through the oracle sums

S1=N−mθ\+∑i=1mg​\(ci\),S2=N−mθ2\+∑i=1mg​\(ci\)2\.S\_\{1\}=\\frac\{N\-m\}\{\\theta\}\+\\sum\_\{i=1\}^\{m\}g\(c\_\{i\}\),\\qquad S\_\{2\}=\\frac\{N\-m\}\{\\theta^\{2\}\}\+\\sum\_\{i=1\}^\{m\}g\(c\_\{i\}\)^\{2\}\.Two facts make the equal split optimal\. First,ggandg2g^\{2\}are convex incc: the outer maps↦1/\(θ\+s\)s\\mapsto 1/\(\\theta\+s\)is convex and decreasing,wwis concave by Assumption[1](https://arxiv.org/html/2607.09765#Thmassumption1), so the compositionggis convex, and\(g2\)′′=2​\(g′\)2\+2​g​g′′≥0\(g^\{2\}\)^\{\\prime\\prime\}=2\(g^\{\\prime\}\)^\{2\}\+2g\\,g^\{\\prime\\prime\}\\geq 0makesg2g^\{2\}convex as well\. Second,H=S1\+S2/\(1−S1\)H=S\_\{1\}\+S\_\{2\}/\(1\-S\_\{1\}\)is increasing in each ofS1,S2S\_\{1\},S\_\{2\}, since

∂H∂S1=1\+S2\(1−S1\)2\>0,∂H∂S2=11−S1\>0\.\\frac\{\\partial H\}\{\\partial S\_\{1\}\}=1\+\\frac\{S\_\{2\}\}\{\(1\-S\_\{1\}\)^\{2\}\}\>0,\\qquad\\frac\{\\partial H\}\{\\partial S\_\{2\}\}=\\frac\{1\}\{1\-S\_\{1\}\}\>0\.By convexity and Jensen’s inequality, at fixed budget∑ici=B\\sum\_\{i\}c\_\{i\}=B,

∑i=1mg​\(ci\)≥m​g​\(Bm\),∑i=1mg​\(ci\)2≥m​g​\(Bm\)2,\\sum\_\{i=1\}^\{m\}g\(c\_\{i\}\)\\ \\geq\\ m\\,g\\\!\\Big\(\\frac\{B\}\{m\}\\Big\),\\qquad\\sum\_\{i=1\}^\{m\}g\(c\_\{i\}\)^\{2\}\\ \\geq\\ m\\,g\\\!\\Big\(\\frac\{B\}\{m\}\\Big\)^\{2\},with equality only when allcic\_\{i\}equalB/mB/m\. The equal split thus minimizes bothS1S\_\{1\}andS2S\_\{2\}, and sinceHHincreases in each, it minimizesHH\. Every unequal split is strictly worse\.

*Choice ofmm\.*Now vary the number of oracles, each at equal costc=B/mc=B/m\. The leading\-order totalm​v​\(B/m\)m\\,v\(B/m\)has derivative with the sign ofv​\(c\)−c​v′​\(c\)=−c2​dd​c​\(v​\(c\)/c\)v\(c\)\-c\\,v^\{\\prime\}\(c\)=\-c^\{2\}\\,\\tfrac\{\\mathrm\{d\}\}\{\\mathrm\{d\}c\}\(v\(c\)/c\)atc=B/mc=B/m\. The marginal gainΔ\\Deltais increasing and concave in strength \(its derivative‖M−1​ei‖2/\(1\+w​ei⊤​M−1​ei\)2\\\|M^\{\-1\}e\_\{i\}\\\|^\{2\}/\(1\+w\\,e\_\{i\}^\{\\top\}M^\{\-1\}e\_\{i\}\)^\{2\}is positive and decreasing\), sov=Δ∘wv=\\Delta\\circ winherits concavity fromww\. Thenv​\(c\)/cv\(c\)/cdecreases and spreading \(largemm\) is favoured\. This leading\-order heuristic agrees with the exactHHof \([6](https://arxiv.org/html/2607.09765#S6.E6)\): the equal\-splitH​\(m\)H\(m\)strictly decreases inmmunder concaveww, and increases only wherewwis convex strongly enough to satisfy \([7](https://arxiv.org/html/2607.09765#S6.E7)\)\. Plain convexity keeps spreading optimal\. The exact statement is Theorem[6](https://arxiv.org/html/2607.09765#Thmtheorem6)and Remark[7](https://arxiv.org/html/2607.09765#Thmremark7)\.

*Graph leverage\.*On non\-vertex\-transitive graphs the optimum equalizes the per\-dollar ratios \([5](https://arxiv.org/html/2607.09765#S5.E5)\)\. Equivalent nodes still receive equal strength; non\-equivalent nodes receive leverage\-weighted amounts\. Graph leverage thus shifts which nodes enter and how much each gets, but not the concave/sharply\-convex dichotomy\. A numerical sweep confirms this\. On a star the continuous optimum spreads equally over the symmetric leaves under concaveww\. Over Erdős–Rényi graphs concavewwspreads across≈80%\{\\approx\}80\\%of nodes, while a sharply convex law \(w​\(c\)=c2w\(c\)=c^\{2\}, satisfying \([7](https://arxiv.org/html/2607.09765#S6.E7)\)\) concentrates on the few highest\-leverage ones\. Throughout,k⋆​\(ε\)k^\{\\star\}\(\\varepsilon\)stays monotone\.

*Minimal count\.*For the coherence criterion the minimal count scales as a constant*fraction*ofNN, not as the worst\-caseΘ​\(N/d\)\\Theta\(N/d\)ofλmin\\lambda\_\{\\min\}\[[11](https://arxiv.org/html/2607.09765#bib.bib11)\]\. This fraction isNN\-independent \(≈0\.3\{\\approx\}0\.3atd=6d\{=\}6, well above1/d1/d; Fig\.[2](https://arxiv.org/html/2607.09765#S6.F2)b\), and its exact value is left open\.

## Appendix Appendix DGlobal optimality of the equal spread \(Theorem[3](https://arxiv.org/html/2607.09765#Thmtheorem3)\)

Throughout, setθ:=N\+κ\>0\\theta:=N\+\\kappa\>0, and for a costc≥0c\\geq 0write

g​\(c\):=1θ\+w​\(c\),ψ​\(c\):=g​\(c\)2\.g\(c\):=\\frac\{1\}\{\\theta\+w\(c\)\},\\qquad\\psi\(c\):=g\(c\)^\{2\}\.OnKNK\_\{N\}the exact coherence \([6](https://arxiv.org/html/2607.09765#S6.E6)\) is thenH=S1\+S2/\(1−S1\)H=S\_\{1\}\+S\_\{2\}/\(1\-S\_\{1\}\)withS1=∑ig​\(ci\)S\_\{1\}=\\sum\_\{i\}g\(c\_\{i\}\)andS2=∑iψ​\(ci\)S\_\{2\}=\\sum\_\{i\}\\psi\(c\_\{i\}\)\. We minimiseHHover the budget simplexΔB=\{c∈ℝ≥0N:∑ici=B\}\\Delta\_\{B\}=\\\{c\\in\\mathbb\{R\}\_\{\\geq 0\}^\{N\}:\\sum\_\{i\}c\_\{i\}=B\\\}\. Sinceθ\>N\\theta\>N, eachg​\(ci\)≤1/θg\(c\_\{i\}\)\\leq 1/\\theta, soS1<1S\_\{1\}<1on all ofΔB\\Delta\_\{B\}and the denominator1−S11\-S\_\{1\}stays positive\.

###### Lemma 1\(convexity of the cost–coherence primitives\)\.

Under Assumption[1](https://arxiv.org/html/2607.09765#Thmassumption1),ggandψ\\psiare strictly decreasing and convex on\[0,∞\)\[0,\\infty\), with

g′′​\(c\)=−w′′​\(c\)​\(θ\+w​\(c\)\)\+2​w′​\(c\)2\(θ\+w​\(c\)\)3,ψ′′​\(c\)=−2​w′′​\(c\)​\(θ\+w​\(c\)\)\+6​w′​\(c\)2\(θ\+w​\(c\)\)4\.g^\{\\prime\\prime\}\(c\)=\\frac\{\-w^\{\\prime\\prime\}\(c\)\(\\theta\+w\(c\)\)\+2w^\{\\prime\}\(c\)^\{2\}\}\{\(\\theta\+w\(c\)\)^\{3\}\},\\qquad\\psi^\{\\prime\\prime\}\(c\)=\\frac\{\-2w^\{\\prime\\prime\}\(c\)\(\\theta\+w\(c\)\)\+6w^\{\\prime\}\(c\)^\{2\}\}\{\(\\theta\+w\(c\)\)^\{4\}\}\.\(9\)

###### Proof\.

Differentiateg​\(c\)=\(θ\+w​\(c\)\)−1g\(c\)=\(\\theta\+w\(c\)\)^\{\-1\}by the chain rule:

g′​\(c\)=−w′​\(c\)\(θ\+w​\(c\)\)2,g′′​\(c\)=−w′′​\(c\)\(θ\+w​\(c\)\)2\+2​w′​\(c\)2\(θ\+w​\(c\)\)3,g^\{\\prime\}\(c\)=\-\\frac\{w^\{\\prime\}\(c\)\}\{\(\\theta\+w\(c\)\)^\{2\}\},\\qquad g^\{\\prime\\prime\}\(c\)=\-\\frac\{w^\{\\prime\\prime\}\(c\)\}\{\(\\theta\+w\(c\)\)^\{2\}\}\+\\frac\{2w^\{\\prime\}\(c\)^\{2\}\}\{\(\\theta\+w\(c\)\)^\{3\}\},and collecting over the common denominator gives the statedg′′g^\{\\prime\\prime\}\. Forψ=g2\\psi=g^\{2\},ψ′=2​g​g′=−2​w′/\(θ\+w\)3\\psi^\{\\prime\}=2g\\,g^\{\\prime\}=\-2w^\{\\prime\}/\(\\theta\+w\)^\{3\}, and one more differentiation gives the statedψ′′\\psi^\{\\prime\\prime\}\. Now read off the signs\. Sincew′≥0w^\{\\prime\}\\geq 0, bothg′≤0g^\{\\prime\}\\leq 0andψ′≤0\\psi^\{\\prime\}\\leq 0, soggandψ\\psiare decreasing\. In each second\-derivative numerator in \([9](https://arxiv.org/html/2607.09765#A4.E9)\) the term−w′′​\(θ\+w\)\-w^\{\\prime\\prime\}\(\\theta\+w\)is≥0\\geq 0\(becausew′′≤0w^\{\\prime\\prime\}\\leq 0andθ\+w\>0\\theta\+w\>0\) and thew′⁣2w^\{\\prime 2\}term is≥0\\geq 0, sog′′≥0g^\{\\prime\\prime\}\\geq 0andψ′′≥0\\psi^\{\\prime\\prime\}\\geq 0, i\.e\. both are convex\. ∎

###### Lemma 2\(pairwise balancing\)\.

Fix all agents except a pair\{a,b\}\\\{a,b\\\}sharing a budgets=ca\+cbs=c\_\{a\}\+c\_\{b\}, and letr:=∑i≠a,bg​\(ci\)<1r:=\\sum\_\{i\\neq a,b\}g\(c\_\{i\}\)<1,q:=∑i≠a,bψ​\(ci\)q:=\\sum\_\{i\\neq a,b\}\\psi\(c\_\{i\}\)be the frozen contributions\. Writingca=s2\+tc\_\{a\}=\\tfrac\{s\}\{2\}\+t,cb=s2−tc\_\{b\}=\\tfrac\{s\}\{2\}\-t, the mapF​\(t\):=HF\(t\):=His even, convex, and uniquely minimised att=0t=0; andS1S\_\{1\}is non\-increasing ast→0t\\to 0, so admissibility is preserved\.

###### Proof\.

Letu​\(t\)=g​\(s2\+t\)\+g​\(s2−t\)u\(t\)=g\(\\tfrac\{s\}\{2\}\+t\)\+g\(\\tfrac\{s\}\{2\}\-t\)andv​\(t\)=ψ​\(s2\+t\)\+ψ​\(s2−t\)v\(t\)=\\psi\(\\tfrac\{s\}\{2\}\+t\)\+\\psi\(\\tfrac\{s\}\{2\}\-t\), so that

H=\(u\+r\)\+v\+q1−\(u\+r\)=:Φ\(u,v\)\.H=\(u\+r\)\+\\frac\{v\+q\}\{1\-\(u\+r\)\}=:\\Phi\(u,v\)\.WithD:=1−\(u\+r\)\>0D:=1\-\(u\+r\)\>0, the partial derivatives ofΦ\\Phiare

Φu=1\+q\+vD2\>0,Φv=1D\>0,Φu​u=2​\(q\+v\)D3≥0,Φv​v=0,Φu​v=1D2\>0\.\\Phi\_\{u\}=1\+\\frac\{q\+v\}\{D^\{2\}\}\>0,\\qquad\\Phi\_\{v\}=\\frac\{1\}\{D\}\>0,\\qquad\\Phi\_\{uu\}=\\frac\{2\(q\+v\)\}\{D^\{3\}\}\\geq 0,\\qquad\\Phi\_\{vv\}=0,\\qquad\\Phi\_\{uv\}=\\frac\{1\}\{D^\{2\}\}\>0\.By Lemma[1](https://arxiv.org/html/2607.09765#Thmlemma1),uuandvvare even and convex, sou​\(0\)=min⁡uu\(0\)=\\min u,v​\(0\)=min⁡vv\(0\)=\\min v, andF′​\(0\)=0F^\{\\prime\}\(0\)=0\. Fort\>0t\>0, the monotonicity ofg′,ψ′g^\{\\prime\},\\psi^\{\\prime\}givesu′​\(t\),v′​\(t\)\>0u^\{\\prime\}\(t\),v^\{\\prime\}\(t\)\>0, henceu′​v′≥0u^\{\\prime\}v^\{\\prime\}\\geq 0\. By the second\-order chain rule for the compositionF​\(t\)=Φ​\(u​\(t\),v​\(t\)\)F\(t\)=\\Phi\(u\(t\),v\(t\)\),

F′′​\(t\)=Φu​u​\(u′\)2\+2​Φu​v​u′​v′\+Φv​v​\(v′\)2\+Φu​u′′\+Φv​v′′\.F^\{\\prime\\prime\}\(t\)=\\Phi\_\{uu\}\\,\(u^\{\\prime\}\)^\{2\}\+2\\,\\Phi\_\{uv\}\\,u^\{\\prime\}v^\{\\prime\}\+\\Phi\_\{vv\}\\,\(v^\{\\prime\}\)^\{2\}\+\\Phi\_\{u\}\\,u^\{\\prime\\prime\}\+\\Phi\_\{v\}\\,v^\{\\prime\\prime\}\.Every term on the right is nonnegative:Φu,Φv,Φu​u,Φu​v≥0\\Phi\_\{u\},\\Phi\_\{v\},\\Phi\_\{uu\},\\Phi\_\{uv\}\\geq 0from the partials above,u′′,v′′≥0u^\{\\prime\\prime\},v^\{\\prime\\prime\}\\geq 0by convexity \(Lemma[1](https://arxiv.org/html/2607.09765#Thmlemma1)\), and\(u′\)2,\(v′\)2,u′​v′≥0\(u^\{\\prime\}\)^\{2\},\(v^\{\\prime\}\)^\{2\},u^\{\\prime\}v^\{\\prime\}\\geq 0\. ThusF′′​\(t\)≥0F^\{\\prime\\prime\}\(t\)\\geq 0, soFFis convex with a critical point att=0t=0, andt=0t=0is its unique minimiser\. Convexity ofggmakesS1=u\+rS\_\{1\}=u\+rsmallest there as well\. ∎

###### Theorem 5\(exact global spreading verdict\)\.

Under Assumption[1](https://arxiv.org/html/2607.09765#Thmassumption1), the exact coherenceHHof \([6](https://arxiv.org/html/2607.09765#S6.E6)\) attains its unique minimum overΔB\\Delta\_\{B\}at the maximal equal spreadci⋆=B/Nc\_\{i\}^\{\\star\}=B/Nfor allii; henceρ​\(R\)=H​\(∅\)−H​\(R\)\\rho\(R\)=H\(\\varnothing\)\-H\(R\)is globally maximised there\.

###### Proof\.

HHis continuous on the compactΔB\\Delta\_\{B\}, so it attains a minimum at somec⋆c^\{\\star\}\. If two coordinates ofc⋆c^\{\\star\}differed, Lemma[2](https://arxiv.org/html/2607.09765#Thmlemma2)would strictly decreaseHHinsideΔB\\Delta\_\{B\}, contradicting minimality; hencec⋆c^\{\\star\}is constant,ci⋆=B/Nc\_\{i\}^\{\\star\}=B/N, and strict convexity of each balancing step gives uniqueness\. ∎

###### Theorem 6\(exactmm\-monotonicity\)\.

Formmoracles of costc=B/mc=B/m\(others at0\), withg0:=g​\(0\)=1/θg\_\{0\}:=g\(0\)=1/\\theta\(usingw​\(0\)=0w\(0\)=0: a zero\-cost oracle adds no strength\),

d​Hd​m=α​\(g​\(c\)−c​g′​\(c\)−g0\)\+β​\(ψ​\(c\)−c​ψ′​\(c\)−ψ​\(0\)\),α=1\+S2\(1−S1\)2\>0,β=11−S1\>0\.\\frac\{\\mathrm\{d\}H\}\{\\mathrm\{d\}m\}=\\alpha\\big\(g\(c\)\-c\\,g^\{\\prime\}\(c\)\-g\_\{0\}\\big\)\+\\beta\\big\(\\psi\(c\)\-c\\,\\psi^\{\\prime\}\(c\)\-\\psi\(0\)\\big\),\\quad\\alpha=1\+\\tfrac\{S\_\{2\}\}\{\(1\-S\_\{1\}\)^\{2\}\}\>0,\\ \\beta=\\tfrac\{1\}\{1\-S\_\{1\}\}\>0\.\(10\)Under Assumption[1](https://arxiv.org/html/2607.09765#Thmassumption1)the two bracketed terms are≤0\\leq 0\(they vanish atc=0c=0and havecc\-derivatives−c​g′′≤0\-c\\,g^\{\\prime\\prime\}\\leq 0,−c​ψ′′≤0\-c\\,\\psi^\{\\prime\\prime\}\\leq 0\), sod​H/d​m≤0\\mathrm\{d\}H/\\mathrm\{d\}m\\leq 0, strictly for strictly concaveww:H​\(m\)H\(m\)is strictly decreasing and the optimum is the maximal spreadm⋆=Nm^\{\\star\}=N, consistent with Theorem[5](https://arxiv.org/html/2607.09765#Thmtheorem5)\.

###### Proof\.

Treatmmas continuous and putc=B/mc=B/m\. Separate each sum into theNN\-node baseline and the oracle correction, usingg0=g​\(0\)=1/θg\_\{0\}=g\(0\)=1/\\thetaandψ​\(0\)=g02\\psi\(0\)=g\_\{0\}^\{2\}:

S1=N​g0\+\(P​\(m\)−m​g0\),S2=N​g02\+\(Q​\(m\)−m​g02\),S\_\{1\}=Ng\_\{0\}\+\\big\(P\(m\)\-mg\_\{0\}\\big\),\\qquad S\_\{2\}=Ng\_\{0\}^\{2\}\+\\big\(Q\(m\)\-mg\_\{0\}^\{2\}\\big\),whereP​\(m\)=m​g​\(B/m\)P\(m\)=m\\,g\(B/m\)andQ​\(m\)=m​ψ​\(B/m\)Q\(m\)=m\\,\\psi\(B/m\)carry themmoracles\. Sinced​c/d​m=−B/m2=−c/m\\mathrm\{d\}c/\\mathrm\{d\}m=\-B/m^\{2\}=\-c/m,

P′​\(m\)=g​\(c\)\+m​g′​\(c\)​d​cd​m=g​\(c\)−c​g′​\(c\),Q′​\(m\)=ψ​\(c\)−c​ψ′​\(c\)\.P^\{\\prime\}\(m\)=g\(c\)\+m\\,g^\{\\prime\}\(c\)\\,\\frac\{\\mathrm\{d\}c\}\{\\mathrm\{d\}m\}=g\(c\)\-c\\,g^\{\\prime\}\(c\),\\qquad Q^\{\\prime\}\(m\)=\\psi\(c\)\-c\\,\\psi^\{\\prime\}\(c\)\.DifferentiatingH=S1\+S2/\(1−S1\)H=S\_\{1\}\+S\_\{2\}/\(1\-S\_\{1\}\)givesd​H/d​m=α​d​S1/d​m\+β​d​S2/d​m\\mathrm\{d\}H/\\mathrm\{d\}m=\\alpha\\,\\mathrm\{d\}S\_\{1\}/\\mathrm\{d\}m\+\\beta\\,\\mathrm\{d\}S\_\{2\}/\\mathrm\{d\}mwithα,β\\alpha,\\betaas in \([10](https://arxiv.org/html/2607.09765#A4.E10)\), andd​S1/d​m=P′​\(m\)−g0\\mathrm\{d\}S\_\{1\}/\\mathrm\{d\}m=P^\{\\prime\}\(m\)\-g\_\{0\},d​S2/d​m=Q′​\(m\)−g02\\mathrm\{d\}S\_\{2\}/\\mathrm\{d\}m=Q^\{\\prime\}\(m\)\-g\_\{0\}^\{2\}; substituting yields \([10](https://arxiv.org/html/2607.09765#A4.E10)\)\. Each bracket vanishes atc=0c=0and hascc\-derivative

dd​c​\(g​\(c\)−c​g′​\(c\)\)=−c​g′′​\(c\)≤0\\frac\{\\mathrm\{d\}\}\{\\mathrm\{d\}c\}\\big\(g\(c\)\-c\\,g^\{\\prime\}\(c\)\\big\)=\-c\\,g^\{\\prime\\prime\}\(c\)\\leq 0\(and−c​ψ′′≤0\-c\\,\\psi^\{\\prime\\prime\}\\leq 0likewise\), byg′′,ψ′′≥0g^\{\\prime\\prime\},\\psi^\{\\prime\\prime\}\\geq 0from Lemma[1](https://arxiv.org/html/2607.09765#Thmlemma1)\. So both brackets are≤0\\leq 0forc≥0c\\geq 0, givingd​H/d​m≤0\\mathrm\{d\}H/\\mathrm\{d\}m\\leq 0\. Under strictly concaveww,g′′\>0g^\{\\prime\\prime\}\>0on a set of positive measure, so the inequality is strict\. ∎

## Appendix Appendix EProof of Theorem[4](https://arxiv.org/html/2607.09765#Thmtheorem4)\(threshold on dense random graphs\)

Letmt=1N​∑jxj​\(t\)m\_\{t\}=\\frac\{1\}\{N\}\\sum\_\{j\}x\_\{j\}\(t\)be the magnetization\. OnG​\(N,p\)G\(N,p\)withp​N≥C​log⁡NpN\\geq C\\log Nthe degrees concentrate,di=p​N​\(1\+o​\(1\)\)d\_\{i\}=pN\\,\(1\+o\(1\)\)uniformly\. Fix a free nodeii; conditioned on the current state its neighbours are a uniformpp\-random subset, so the neighbour\-sumSi=∑j∼ixjS\_\{i\}=\\sum\_\{j\\sim i\}x\_\{j\}has𝔼​\[Si\]=p​N​mt\+O​\(1\)\\mathbb\{E\}\[S\_\{i\}\]=pN\\,m\_\{t\}\+O\(1\)and, by Hoeffding,Pr⁡\(\|Si−𝔼​Si\|≥t\)≤2​e−t2/\(2​di\)\\Pr\\\!\\big\(\|S\_\{i\}\-\\mathbb\{E\}S\_\{i\}\|\\geq t\\big\)\\leq 2e^\{\-t^\{2\}/\(2d\_\{i\}\)\}\. Takingt=12​\|𝔼​Si\|t=\\tfrac\{1\}\{2\}\|\\mathbb\{E\}S\_\{i\}\|and a union bound over the≤N\\leq Nfree nodes, if

\|mt\|≥C0​log⁡Np​N\|m\_\{t\}\|\\ \\geq\\ C\_\{0\}\\sqrt\{\\frac\{\\log N\}\{pN\}\}then with probability1−o​\(1\)1\-o\(1\)*every*free node hassign⁡\(Si\)=sign⁡\(mt\)\\operatorname\{sign\}\(S\_\{i\}\)=\\operatorname\{sign\}\(m\_\{t\}\), so all free nodes \(bar the glitching1−pr1\-p\_\{\\mathrm\{r\}\}minority\) update tosign⁡\(mt\)\\operatorname\{sign\}\(m\_\{t\}\)\.

At the balanced start the free spins sum toO​\(N\)O\(\\sqrt\{N\}\), som0=\(k−f\)/N\+O​\(1/N\)m\_\{0\}=\(k\-f\)/N\+O\(1/\\sqrt\{N\}\); because the degrees concentrate this is the degree\-weighted balance,sign⁡\(m0\)=sign⁡\(k−f\)=sign⁡\(DR−DF\)\\operatorname\{sign\}\(m\_\{0\}\)=\\operatorname\{sign\}\(k\-f\)=\\operatorname\{sign\}\(D\_\{R\}\-D\_\{F\}\)withDR−DF=p​N​\(k−f\)​\(1\+o​\(1\)\)D\_\{R\}\-D\_\{F\}=pN\\,\(k\-f\)\\,\(1\+o\(1\)\)\. When the count margin satisfiesk−f≥C′​N​log⁡N/pk\-f\\geq C^\{\\prime\}\\sqrt\{N\\log N/p\}\(which both exceeds theO​\(N\)O\(\\sqrt\{N\}\)start fluctuation and clears the alignment threshold above\),\|m0\|\|m\_\{0\}\|lies aboveC0​log⁡N/\(p​N\)C\_\{0\}\\sqrt\{\\log N/\(pN\)\}, so one step drives the free majority tosign⁡\(k−f\)\\operatorname\{sign\}\(k\-f\); the configuration in which every free agent agrees with the pinned majority is a fixed point, because each free neighbour\-sum then keeps that sign\. Hence truth wins whenk−f≥C′​N​log⁡N/pk\-f\\geq C^\{\\prime\}\\sqrt\{N\\log N/p\}\(and fails symmetrically\)\. Whenp​N=ω​\(log⁡N\)pN=\\omega\(\\log N\)this margin iso​\(N\)o\(N\), so the critical fractionρR=ρF\\rho\_\{R\}=\\rho\_\{F\}is sharp; at the boundaryp​N=Θ​\(log⁡N\)pN=\\Theta\(\\log N\)it isΘ​\(N\)\\Theta\(N\)and the fraction is sharp only up to constants\. The glitches flip aBin​\(N−k−f,1−pr\)\\mathrm\{Bin\}\(N\-k\-f,\\,1\-p\_\{\\mathrm\{r\}\}\)set of free nodes, anO​\(N\)O\(\\sqrt\{N\}\)fluctuation of the count margin that, with the balanced\-start fluctuation, sets theO​\(N\)O\(\\sqrt\{N\}\)transition width seen in simulation\. The complete graph is the deterministicpr→1p\_\{\\mathrm\{r\}\}\\to 1,p=1p=1limit, recovering Proposition[3](https://arxiv.org/html/2607.09765#Thmproposition3)\.

## Appendix Appendix FThe sparse\-graph frontier via the cavity method

On a randomdd\-regular graphM=\(d\+κ\)​I−A\+diag⁡\(wi​𝟙​\[i∈R\]\)M=\(d\+\\kappa\)I\-A\+\\operatorname\{diag\}\(w\_\{i\}\\mathds\{1\}\[i\\in R\]\)is not covered by the complete\-graph closed form \([6](https://arxiv.org/html/2607.09765#S6.E6)\), but the local tree structure makes the coherence exact in the replica\-symmetric limit\. The diagonal resolventgi=\(M−1\)i​ig\_\{i\}=\(M^\{\-1\}\)\_\{ii\}obeys a cavity recursion: writinggi→jg\_\{i\\to j\}for the resolvent on the graph with edge\(i,j\)\(i,j\)deleted andai=d\+κ\+wia\_\{i\}=d\+\\kappa\+w\_\{i\},

gi→j=1ai−∑k∈∂i∖jgk→i,g\_\{i\\to j\}=\\frac\{1\}\{a\_\{i\}\-\\sum\_\{k\\in\\partial i\\setminus j\}g\_\{k\\to i\}\},the off\-diagonal−1\-1entries squaring to\+1\+1in the Schur complement\. For a fractionρ=k/N\\rho=k/Nof nodes pinned at strengthww, the cavity resolvent converges to the distributional fixed point

g=d1a−∑l=1d−1gl,a=\{d\+κ\+ww\.p\.​ρ,d\+κw\.p\.​1−ρ,g\\ \\stackrel\{\{\\scriptstyle d\}\}\{\{=\}\}\\ \\frac\{1\}\{a\-\\sum\_\{l=1\}^\{d\-1\}g\_\{l\}\},\\qquad a=\\begin\{cases\}d\+\\kappa\+w&\\text\{w\.p\. \}\\rho,\\\\\[2\.0pt\] d\+\\kappa&\\text\{w\.p\. \}1\-\\rho,\\end\{cases\}withglg\_\{l\}i\.i\.d\. copies, and the per\-node coherence ish​\(ρ\)=H/N=𝔼​\[\(a−∑l=1dgl\)−1\]h\(\\rho\)=H/N=\\mathbb\{E\}\\big\[\(a\-\\sum\_\{l=1\}^\{d\}g\_\{l\}\)^\{\-1\}\\big\]\. Solved by population dynamics,h​\(ρ\)h\(\\rho\)matches the directtr⁡M−1/N\\operatorname\{tr\}M^\{\-1\}/Non finite randomdd\-regular graphs to under0\.5%0\.5\\%\(atd=6d=6,κ=1\\kappa=1,w=8w=8:h​\(0\)=0\.166h\(0\)=0\.166,h​\(0\.3\)=0\.134h\(0\.3\)=0\.134\)\. Invertingh​\(ρ\)=ε/Nh\(\\rho\)=\\varepsilon/Ngives the minimal pinned fractionρ⋆\\rho^\{\\star\}, hence the frontierB⋆=ρ⋆​N​cB^\{\\star\}=\\rho^\{\\star\}N\\,c\. It isNN\-independent: the exact replica\-symmetric sparse\-graph analogue of \([6](https://arxiv.org/html/2607.09765#S6.E6)\)\.

## Appendix Appendix GStructured sparse graphs: the stochastic block model cavity

[Appendix F](https://arxiv.org/html/2607.09765#A6)gives the exact coherence on the randomdd\-regular ensemble\. Real agent topologies cluster into communities \(teams, tool groups, debate sub\-panels\) wired densely inside and sparsely across\. We extend the cavity to the*stochastic block model*\(SBM\)\. FixKKcommunities of sizesNℓN\_\{\\ell\}; every node in communityℓ\\ellhasdi​nd\_\{in\}intra\-community anddo​u​td\_\{out\}inter\-community neighbours \(di​n,do​u​t=O​\(1\)d\_\{in\},d\_\{out\}=O\(1\), symmetric mixing\), total degreed=di​n\+do​u​td=d\_\{in\}\+d\_\{out\}, and a fractionρℓ\\rho\_\{\\ell\}of pinned oracles of strengthww, soM​\(R\)i​i=d\+κ\+w​1​\[i∈R\]M\(R\)\_\{ii\}=d\+\\kappa\+w\\,\\mathds\{1\}\[i\\in R\]\.

A cavity message must remember both its source community and whether it crosses a boundary\. Letgℓi​ng^\{in\}\_\{\\ell\},gℓo​u​tg^\{out\}\_\{\\ell\}be the cavity variances on intra\- and inter\-community directed edges with source inℓ\\ell, andaℓ=d\+κ\+w​Bℓa\_\{\\ell\}=d\+\\kappa\+w\\,B\_\{\\ell\}withBℓ∼Bernoulli​\(ρℓ\)B\_\{\\ell\}\\sim\\mathrm\{Bernoulli\}\(\\rho\_\{\\ell\}\)\. The leave\-one\-out elimination gives the coupled fixed point

gℓi​n​=𝑑​\(aℓ−∑r=1di​n−1gℓ,ri​n−∑s=1do​u​tgℓs′,so​u​t\)−1,gℓo​u​t​=𝑑​\(aℓ−∑r=1di​ngℓ,ri​n−∑s=1do​u​t−1gℓs′,so​u​t\)−1,g^\{in\}\_\{\\ell\}\\overset\{d\}\{=\}\\Big\(a\_\{\\ell\}\-\\\!\\sum\_\{r=1\}^\{d\_\{in\}\-1\}g^\{in\}\_\{\\ell,r\}\-\\\!\\sum\_\{s=1\}^\{d\_\{out\}\}g^\{out\}\_\{\\ell^\{\\prime\}\_\{s\},s\}\\Big\)^\{\-1\},\\quad g^\{out\}\_\{\\ell\}\\overset\{d\}\{=\}\\Big\(a\_\{\\ell\}\-\\\!\\sum\_\{r=1\}^\{d\_\{in\}\}g^\{in\}\_\{\\ell,r\}\-\\\!\\sum\_\{s=1\}^\{d\_\{out\}\-1\}g^\{out\}\_\{\\ell^\{\\prime\}\_\{s\},s\}\\Big\)^\{\-1\},\(11\)with i\.i\.d\. copies, eachℓs′\\ell^\{\\prime\}\_\{s\}drawn uniformly from the other communities\. The block coherence is the node marginalhℓ​\(ρℓ\)=𝔼​\[\(aℓ−∑r=1di​ngℓ,ri​n−∑s=1do​u​tgℓs′,so​u​t\)−1\]h\_\{\\ell\}\(\\rho\_\{\\ell\}\)=\\mathbb\{E\}\\big\[\(a\_\{\\ell\}\-\\sum\_\{r=1\}^\{d\_\{in\}\}g^\{in\}\_\{\\ell,r\}\-\\sum\_\{s=1\}^\{d\_\{out\}\}g^\{out\}\_\{\\ell^\{\\prime\}\_\{s\},s\}\)^\{\-1\}\\big\], and since the trace splits over communities,

H​\(R\)N=tr⁡M​\(R\)−1N=∑ℓ=1KNℓN​hℓ​\(ρℓ\)\.\\frac\{H\(R\)\}\{N\}=\\frac\{\\operatorname\{tr\}M\(R\)^\{\-1\}\}\{N\}=\\sum\_\{\\ell=1\}^\{K\}\\frac\{N\_\{\\ell\}\}\{N\}\\,h\_\{\\ell\}\(\\rho\_\{\\ell\}\)\.\(12\)Two limits check out\. Whendo​u​t=di​nd\_\{out\}=d\_\{in\}\(orK=1K=1\) both populations coincide and \([11](https://arxiv.org/html/2607.09765#A7.E11)\) collapses to the scalar random\-dd\-regular cavity of[Appendix F](https://arxiv.org/html/2607.09765#A6)\. Asdo​u​t→0d\_\{out\}\\to 0the blocks decouple and \([12](https://arxiv.org/html/2607.09765#A7.E12)\) reduces to the additive per\-community covering picture of Proposition[4](https://arxiv.org/html/2607.09765#Thmproposition4), with the concave\-wwspreading law of Theorem[3](https://arxiv.org/html/2607.09765#Thmtheorem3)applied*within*each block;do​u​td\_\{out\}interpolates between one homogeneous swarm andKKindependent ones\.

We solve \([11](https://arxiv.org/html/2607.09765#A7.E11)\) by population dynamics and compare against the direct block average of\(M​\(R\)−1\)i​i\(M\(R\)^\{\-1\}\)\_\{ii\}on finite SBMs \(N=900N=900–12001200,55–66realizations\)\. The agreement is below1%1\\%\. ForK=3K\{=\}3,di​n=6d\_\{in\}\{=\}6,do​u​t=2d\_\{out\}\{=\}2,ρ=\(0\.1,0\.4,0\.7\)\\rho=\(0\.1,0\.4,0\.7\),w=3w\{=\}3,κ=0\.5\\kappa\{=\}0\.5, the blockhhis\(0\.130,0\.117,0\.105\)\(0\.130,0\.117,0\.105\)direct versus\(0\.129,0\.117,0\.105\)\(0\.129,0\.117,0\.105\)cavity, and the totalH/NH/Nis0\.11770\.1177versus0\.11720\.1172\(0\.4%0\.4\\%\)\. The gap halves asNNdoubles \(0\.83%,0\.42%,0\.23%0\.83\\%,0\.42\\%,0\.23\\%atN=450,900,1500N=450,900,1500\), so the finite graph converges to the cavity value\. The frontier thus extends exactly, in the replica\-symmetric locally\-tree\-like regime, from the homogeneous ensemble to community\-structured sparse graphs\.

### General asymmetric mixing\.

The symmetric ensemble above is the casedℓ​ℓ=dind\_\{\\ell\\ell\}=d\_\{\\mathrm\{in\}\},dℓ​ℓ′=dout/\(K−1\)d\_\{\\ell\\ell^\{\\prime\}\}=d\_\{\\mathrm\{out\}\}/\(K\-1\)of a general*degree matrix*dℓ​ℓ′≥0d\_\{\\ell\\ell^\{\\prime\}\}\\geq 0, the mean number of neighbours a block\-ℓ\\ellnode has in blockℓ′\\ell^\{\\prime\}; blocks may also carry distinctρℓ\\rho\_\{\\ell\}and strengthswℓw\_\{\\ell\}\. A cavity message must now remember its*ordered*endpoints: letgℓ→ℓ′g\_\{\\ell\\to\\ell^\{\\prime\}\}be the cavity resolvent on a directed edge from a block\-ℓ\\ellnode toward a block\-ℓ′\\ell^\{\\prime\}node \(one population per ordered pair,K2K^\{2\}in all\)\. With

aℓ=κ\+∑ℓ′=1Kdℓ​ℓ′\+wℓ​Bℓ,Bℓ∼Bernoulli​\(ρℓ\),a\_\{\\ell\}=\\kappa\+\\sum\_\{\\ell^\{\\prime\}=1\}^\{K\}d\_\{\\ell\\ell^\{\\prime\}\}\+w\_\{\\ell\}\\,B\_\{\\ell\},\\qquad B\_\{\\ell\}\\sim\\mathrm\{Bernoulli\}\(\\rho\_\{\\ell\}\),\(13\)the leave\-one\-out elimination \(the messageℓ→ℓ′\\ell\\to\\ell^\{\\prime\}keeps every incoming neighbour of its source node except the singleℓ′\\ell^\{\\prime\}\-neighbour it answers\) gives

gℓ→ℓ′​=𝑑​\(aℓ−∑p=1K∑r=1dℓ​p−δp​ℓ′gp→ℓ\(r\)\)−1,g\_\{\\ell\\to\\ell^\{\\prime\}\}\\overset\{d\}\{=\}\\Big\(a\_\{\\ell\}\-\\sum\_\{p=1\}^\{K\}\\ \\sum\_\{r=1\}^\{\\,d\_\{\\ell p\}\-\\delta\_\{p\\ell^\{\\prime\}\}\}g^\{\(r\)\}\_\{p\\to\\ell\}\\Big\)^\{\-1\},\(14\)with independent copies from populationgp→ℓg\_\{p\\to\\ell\}\. The block coherence sums over all incoming neighbours,

hℓ=𝔼​\[\(aℓ−∑p=1K∑r=1dℓ​pgp→ℓ\(r\)\)−1\],H​\(R\)N=∑ℓ=1KNℓN​hℓ\.h\_\{\\ell\}=\\mathbb\{E\}\\Big\[\\Big\(a\_\{\\ell\}\-\\sum\_\{p=1\}^\{K\}\\ \\sum\_\{r=1\}^\{\\,d\_\{\\ell p\}\}g^\{\(r\)\}\_\{p\\to\\ell\}\\Big\)^\{\-1\}\\Big\],\\qquad\\frac\{H\(R\)\}\{N\}=\\sum\_\{\\ell=1\}^\{K\}\\frac\{N\_\{\\ell\}\}\{N\}\\,h\_\{\\ell\}\.\(15\)Settingdℓ​ℓ=dind\_\{\\ell\\ell\}=d\_\{\\mathrm\{in\}\},dℓ​ℓ′=dout/\(K−1\)d\_\{\\ell\\ell^\{\\prime\}\}=d\_\{\\mathrm\{out\}\}/\(K\-1\)collapses theK−1K\-1cross\-populations with a common target into a singlegℓoutg^\{\\mathrm\{out\}\}\_\{\\ell\}and recovers \([11](https://arxiv.org/html/2607.09765#A7.E11)\)–\([12](https://arxiv.org/html/2607.09765#A7.E12)\) exactly\. \(These block equations sum a node’s feedback over all of its incoming neighbours, which is exact precisely because the support is symmetric; the genuinely directed case is treated in[Appendix H](https://arxiv.org/html/2607.09765#A8)\.\) Population dynamics on theK2K^\{2\}populations again matches the direct block average below1%1\\%: for the genuinely asymmetricd=\(621453237\)d=\\big\(\\begin\{smallmatrix\}6&2&1\\\\ 4&5&3\\\\ 2&3&7\\end\{smallmatrix\}\\big\)withNℓ=\(600,300,300\)N\_\{\\ell\}=\(600,300,300\),ρ=\(0\.2,0\.5,0\.3\)\\rho=\(0\.2,0\.5,0\.3\),w=\(3,2,5\)w=\(3,2,5\),κ=0\.4\\kappa=0\.4, the cavity givesH/N=0\.096H/N=0\.096versus0\.0970\.097direct \(0\.6%0\.6\\%\)\. The frontier is thus exact, replica\-symmetric, for arbitraryK×KK\\times Kcommunity mixing\.

Equations \([14](https://arxiv.org/html/2607.09765#A7.E14)\)–\([15](https://arxiv.org/html/2607.09765#A7.E15)\) are stated for the*symmetric\-support*ensemble, where every edge carries influence in both directions \(the weights may differ, butiifeedsjjiffjjfeedsii\)\. A message then sums its source’s incoming neighbours and every incoming neighbour is also an outgoing one\. A genuinely*directed*swarm, where influence can be one\-way, is a different object:MMbecomes non\-symmetric and, as[Appendix H](https://arxiv.org/html/2607.09765#A8)shows, the feedback must be restricted to reciprocated edges rather than all incoming ones\.

## Appendix Appendix HDirected swarms: only reciprocated trust carries feedback

So far every edge has been two\-way\. Real influence is often one\-way: an agent may read a tool’s output without the tool reading it back, or a junior agent may copy a senior one it never affects\. Model this with a directed influence graph,Ai​j=1A\_\{ij\}=1when agentjjfeeds agentii\(j→ij\\to i\), and the grounded*row*\-Laplacian

M=Din−A\+κ​I\+WR,Mi​i=κ\+diin\+w​1​\[i∈R\],Mi​j=−Ai​j​\(i≠j\),M\\;=\\;D\_\{\\mathrm\{in\}\}\-A\+\\kappa I\+W\_\{R\},\\qquad M\_\{ii\}=\\kappa\+d^\{\\mathrm\{in\}\}\_\{i\}\+w\\,\\mathds\{1\}\[i\\in R\],\\quad M\_\{ij\}=\-A\_\{ij\}\\ \(i\\neq j\),\(16\)withDin=diag⁡\(diin\)D\_\{\\mathrm\{in\}\}=\\operatorname\{diag\}\(d^\{\\mathrm\{in\}\}\_\{i\}\)the in\-degree\.MMis non\-symmetric as soon as some edge is one\-way, so the M\-matrix symmetry of Section[4](https://arxiv.org/html/2607.09765#S4)is lost; butMMis still strictly diagonally dominant \(Mi​i−∑j≠i\|Mi​j\|=κ\+w​1​\[i∈R\]≥κ\>0M\_\{ii\}\-\\sum\_\{j\\neq i\}\|M\_\{ij\}\|=\\kappa\+w\\,\\mathds\{1\}\[i\\in R\]\\geq\\kappa\>0\), hence nonsingular with a well\-defined coherenceH=tr⁡M−1H=\\operatorname\{tr\}M^\{\-1\}\. Writerecip​\(i\)=\{j:Ai​j​Aj​i=1\}\\mathrm\{recip\}\(i\)=\\\{j:A\_\{ij\}A\_\{ji\}=1\\\}for the neighboursiiboth feeds and is fed by\.

###### Proposition 6\(Directed cavity\)\.

On a locally tree\-like directed graph the diagonal resolvent obeys, in the replica\-symmetric limit, the scalar cavity recursion

gi=\(ai−∑j∈recip​\(i\)Ai​j​Aj​i​gj\(i\)\)−1,ai=κ\+diin\+w​1​\[i∈R\],HN=𝔼​gi,g\_\{i\}\\;=\\;\\Big\(a\_\{i\}\-\\\!\\\!\\sum\_\{j\\in\\mathrm\{recip\}\(i\)\}\\\!\\\!A\_\{ij\}A\_\{ji\}\\,g^\{\(i\)\}\_\{j\}\\Big\)^\{\-1\},\\qquad a\_\{i\}=\\kappa\+d^\{\\mathrm\{in\}\}\_\{i\}\+w\\,\\mathds\{1\}\[i\\in R\],\\qquad\\frac\{H\}\{N\}=\\mathbb\{E\}\\,g\_\{i\},\(17\)wheregj\(i\)g^\{\(i\)\}\_\{j\}is the cavity resolvent atjjwithiiremoved\. The feedback runs over*reciprocated*edges only: a one\-way edgej→ij\\to ienters exclusively through the in\-degree inaia\_\{i\}and contributes nothing to the off\-diagonal feedback\.

###### Proof\.

By the Schur complement,\[M−1\]i​i=\(Mi​i−ri⊤​\(M\(i\)\)−1​ci\)−1\[M^\{\-1\}\]\_\{ii\}=\\big\(M\_\{ii\}\-r\_\{i\}^\{\\\!\\top\}\(M^\{\(i\)\}\)^\{\-1\}c\_\{i\}\\big\)^\{\-1\}\. HereM\(i\)M^\{\(i\)\}is the minor with row and columniideleted,rir\_\{i\}is the off\-diagonal row ofMM\(its entriesMi​jM\_\{ij\}are the feedersj→ij\\to i\), andcic\_\{i\}is the off\-diagonal column \(its entriesMj​iM\_\{ji\}are the targetsi→ji\\to j\)\. The bilinear term is∑j,k≠iMi​j​\[\(M\(i\)\)−1\]j​k​Mk​i\\sum\_\{j,k\\neq i\}M\_\{ij\}\\,\[\(M^\{\(i\)\}\)^\{\-1\}\]\_\{jk\}\\,M\_\{ki\}\. On a graph whose underlying undirected support is locally a tree,iiis a cut vertex, so two distinct neighboursj≠kj\\neq klie in different components ofM\(i\)M^\{\(i\)\}and\[\(M\(i\)\)−1\]j​k=0\[\(M^\{\(i\)\}\)^\{\-1\}\]\_\{jk\}=0; onlyj=kj=ksurvives, giving∑jMi​j​Mj​i​\[\(M\(i\)\)−1\]j​j\\sum\_\{j\}M\_\{ij\}M\_\{ji\}\\,\[\(M^\{\(i\)\}\)^\{\-1\}\]\_\{jj\}\. The coefficientMi​j​Mj​i=Ai​j​Aj​iM\_\{ij\}M\_\{ji\}=A\_\{ij\}A\_\{ji\}is nonzero exactly whenj∈recip​\(i\)j\\in\\mathrm\{recip\}\(i\), and\[\(M\(i\)\)−1\]j​j=gj\(i\)\[\(M^\{\(i\)\}\)^\{\-1\}\]\_\{jj\}=g^\{\(i\)\}\_\{j\}\. A one\-way edge hasAi​j​Aj​i=0A\_\{ij\}A\_\{ji\}=0and drops out\. A44\-node symbolic check confirms∂\[M−1\]i​i/∂ak=0\\partial\[M^\{\-1\}\]\_\{ii\}/\\partial a\_\{k\}=0for every one\-way neighbourkk\. ∎

The reading is sharp:*mutual*trust binds a swarm, one\-way authority does not\. A corrector that broadcasts to many agents but listens to none influences their answers, yet its own coherence and the trace it contributes are set solely by its diagonal: it is a cut vertex with no return path, so no feedback loop forms through it\. Equation \([17](https://arxiv.org/html/2607.09765#A8.E17)\) specializes the cavity method for sparse non\-Hermitian matrices\[[2](https://arxiv.org/html/2607.09765#bib.bib2)\]to the diagonal of the resolvent; what is specific here is that on a tree\-like directed graph the coherence feedback is carried only by reciprocal22\-cycles\. This also corrects the naive extrapolation of the block form \([14](https://arxiv.org/html/2607.09765#A7.E14)\): summing feedback over*all*incoming neighbours holds only under symmetric support, and even then the reciprocated\-only reduction is the tree\-level form\.

![Refer to caption](https://arxiv.org/html/2607.09765v1/figures/directed_cavity.png)Figure 9:Coherence of a directed swarm as edges turn one\-way \(reciprocityrrswept from fully two\-way, right, to fully directed, left; sparse graph,N=400N\{=\}400, mean degree55,κ=0\.5\\kappa\{=\}0\.5,w=3w\{=\}3,20%20\\%pinned\)\. The reciprocated\-only cavity \([17](https://arxiv.org/html/2607.09765#A8.E17)\) tracks the exacttr⁡M−1/N\\operatorname\{tr\}M^\{\-1\}/Nwithin0\.6%0\.6\\%across the whole range, including the fully directed graph\. Summing feedback over all incoming edges \(the block\-form extrapolation\) drifts badly once the graph is directed, by up to∼70%\{\\sim\}70\\%\. One\-way influence raises the coherence cost: removing return paths removes the feedback loops that bind the swarm\.Solving \([17](https://arxiv.org/html/2607.09765#A8.E17)\) by single\-instance message passing on directed Erdős–Rényi graphs and comparing against the directtr⁡M−1\\operatorname\{tr\}M^\{\-1\}over a reciprocity sweep \(Fig\.[9](https://arxiv.org/html/2607.09765#A8.F9)\) gives agreement below0\.6%0\.6\\%from the two\-way graph all the way to the fully directed one, whereas the all\-incoming form drifts by up to∼70%\{\\sim\}70\\%\(worst nearr≈0\.3r\{\\approx\}0\.3, and∼47%\{\\sim\}47\\%at the fully directed graph\)\. The reciprocated\-only cavity is thus the replica\-symmetric, tree\-level fixed point: it is exact when the underlying undirected support is locally tree\-like, and short directed cycles break the cut\-vertex step per instance but areO​\(1/N\)O\(1/N\)\-rare in sparse graphs, so theNN\-averaged trace still matches to within0\.6%0\.6\\%even fully directed\. The submodular placement guarantees of Section[4](https://arxiv.org/html/2607.09765#S4), which use the symmetry ofMM, do not transfer to the directed regime and are left open there\.