Compositional reliability bounds for multi-agent systems multiply component reliabilities, a step licensed by a conditional-independence assumption that is routinely stated and rarely tested. We test it. Two instances of one model, in a two-agent handoff, co-fail on 90.0% of the missions on which either fails (log OR 6.66, 95% CI [6.38, 7.00]; phi 0.916), in a preregistered evaluation of 18,000 missions scored by deterministic code with no LLM judge. Substituting a different model reduces the association in six of six contrasts; substituting a different vendor, model already different, does not -- a registered hypothesis reported as a null. The error is signed and runs against the operator: positive dependence inflates joint failure above the independence product, so redundancy is over-credited exactly when components share a model. The assumption-free alternative is often vacuous, and fitting a dependence model is worse: we prove a bootstrap bound on a fitted model's functional loses coverage of the truth as n grows, the identification gap being O(1) while the bootstrap haircut is O(n^{-1/2}). More data makes such a certificate worse, with no visible symptom. We give a finite-sample certificate assuming no dependence structure: a linear program over the joint, over a Bonferroni-Clopper-Pearson box around measured co-execution moments. It is sound, sharp for the information supplied, and monotone in the moment family. Enriching ten moment functionals to fourteen narrows the identified interval by 85.7% and lifts the certified floor from 0.2455 to 0.4116. A companion anytime-valid certificate holds type-I error at 0.0471 under optional stopping. Common dependence statistics are marginal-bounded and can reverse an apparent ordering of conditions when the compared agents fail at different rates. Contracts, scoring code, analysis scripts, and the preregistration are released.
Multi-agent LLM systems route among model-backed advisors, yet a deployer rarely knows before shipping whether routing will help at all. Prevailing routers optimize a gate's AUC and presume that advisor complementarity suffices. We show that neither determines the deployable gain. We introduce RouteGuard, a deployment-certification framework. Routing gain decomposes as $G = πΔ_E$, and the achievable gain is governed by a conditional-regret functional $Φ$, not by AUC. A finite-sample certification bracket comes with a matching Le Cam lower bound, constant-sharp over the fixed-activity class, and a robustness phase transition. On two benchmarks the framework acts as a guardrail. On RouterBench (11 cross-family models) the verdict depends on the sampling unit: the protocol certifies a gain over GPT-4 under prompt-level sampling and withholds it under workload-cluster resampling, because the gain rests on 3 of 86 workload cells. On OpenRCA (three Gemini advisors) the advisors are statistically redundant: the realized oracle sits at or below the independence baseline in all pools we tested (221 RouterBench pools and three OpenRCA distributions), so the protocol correctly refuses to certify. A pre-registered semi-synthetic control confirms calibration: the protocol certifies a genuine gain once $m \ge m^\star$ and does not certify a true null. Code and frozen artifacts will be released with the published version.
In the big-world regime, agents cannot be universally capable and their ability is inevitably specialized across a world model in pieces. Consequently, standard uniform guarantees fail to distinguish between the understanding of critical bottlenecks and irrelevant failures. We first formalize this limitation by proving that general agents are not universal, rendering standard worst-case analysis uninformative. To overcome this, we introduce structural certification, a transition-local framework that maps bounded goal-conditioned performance to entry-wise guarantees on the agent's internal world model. Our main contribution is constructive. We provide algorithms that filter specific transitions using deep compositional goals and prove that a general agent on these goals has a structural world model with a $\mathcal{O}(1/n) + \mathcal{O}(δ)$ error bound. Conversely, this bound is tight in the small-$δ$ regime, whose existence is explicitly guaranteed by our certification. These results enable the certifiable deployment of general agents by localizing the specific transitions where long-horizon planning is reliable.
Haoran Xu, Lei Zhang, Iadh Ounis +1cs.MA cs.AI cs.DC
Can a committee of LLM agents reach agreement that is certifiable at the level of meaning, not only at the level of a label? We build a protocol to find out. H-CSC emits one of three typed outcomes per round -- semantic commit, verdict commit, or typed abort -- under a common 2f+1 distinct-signer certificate, and we use it to measure what such agreement costs and buys. The answer is conditional, and the condition is not the protocol. We prove a containment lemma: whenever the semantic core is large enough to make the committed verdict deterministically valid, the verdict margin already exceeds f, so at matched deterministic guarantees no coverage separation from certificate-wrapped majority is possible. Measurement agrees: the two rules commit the identical task set. What matters instead is the admissibility instrument. Against adversaries that preserve the verdict and corrupt only the reasoning, a 442 MB fine-tuned encoder reaches AUROC 0.621-0.744 at 0-8% TPR (5% honest FPR), while a training-free lexical predicate reaches 0.865-0.982 at 38-80% (50 tasks, 200 attacks, 400 honest) and is exactly deterministic, discharging an assumption the digest proofs rely on. Honest agents disperse further than attacks displace (90th-percentile honest angular distance 0.992 rad against a 0.65 radius), so on free-text rationales no embedding filter is viable -- a property of the output schema, which when tightened collapses dispersion twenty-fold. The committed digest is not inert: under non-disclosure a similarity-preserving sketch separates faithful from substituted derived statements at AUROC 0.741 (n=350), where a cryptographic hash and a verdict-only digest score exactly 0.500. We also report a tie-break capture vulnerability found in our own protocol, and its four-line fix. We claim no safety or coverage advantage over verdict-only certification; the lemma explains why there is none to claim.