Agent Behavioral Contracts II: Certifying Compositional Reliability Without Assuming Independence

Technical Summary: Agent Behavioral Contracts II

Problem Statement
Current frameworks for certifying the reliability of multi-agent systems rely on a compositional approach: bounding the reliability of individual components and multiplying these bounds to derive a system-wide guarantee. This step is licensed by a conditional independence assumption (C5), which posits that a downstream agent's contract satisfaction is independent of an upstream agent's execution given a compliant handoff. The authors argue this assumption is routinely stated but rarely tested, and is particularly implausible when redundant agents (e.g., a writer and a reviewer) share the same underlying model weights. If components share a model, they share "blind spots," leading to positive dependence in failures. The paper demonstrates that ignoring this dependence results in a "signed error" that runs against the operator: positive dependence inflates joint failure probabilities above the independence product, causing redundant designs to be over-credited precisely when they are most needed.

Furthermore, the paper identifies that standard "fixes" are inadequate:

1. Dropping the assumption entirely leads to Fréchet–Hoeffding bounds, which are often vacuous (certified floor of zero) when mean component reliability falls below $1 - 1/m$.
2. Fitting a parametric dependence model (e.g., a Gaussian one-factor copula) is worse; the authors prove that as sample size $n \to \infty$, the coverage of a bootstrap lower bound on a misspecified model's functional collapses to zero. The identification gap remains $O(1)$ while the bootstrap uncertainty shrinks as $O(n^{-1/2})$, meaning more data makes the certificate confidently wrong without any visible symptom.

Methodology
The paper employs a rigorous, preregistered experimental design combined with a novel finite-sample certification framework.

• Experimental Design: The authors conducted a campaign of 30,820 missions across 12 arms, with a confirmatory core of 18,000 missions in a two-agent handoff topology. They manipulated the "sharing condition" at three levels:

  1. Same Model: Both agents run mistral-small-24b.
  2. Same Vendor: Agents run different models from the same vendor (mistral-small-24b vs. ministral-8b).
  3. Different Vendor: Agents run models from different vendors.
     Scoring was deterministic (gold code) with no LLM in the judging loop to prevent induced correlation.

• Certification Framework (Tiered Approach):

  • Tier 0 (Observed): Direct Clopper–Pearson lower bound on the observed graph outcome (requires end-to-end execution).
  • Tier 1 (Copula-Agnostic): A finite-sample certificate that assumes no dependence structure. It formulates a linear program (LP) over the joint distribution of agent outcomes, constrained by a Bonferroni–Clopper–Pearson box around measured co-execution moments (marginals, pairwise, and higher-order co-success moments). This approach is sound, sharp for the supplied information, and monotone in the moment family under a specific allocation.
  • Tier 2 (Model-based): A diagnostic-only floor based on a fitted Gaussian copula, explicitly not used for certification due to the proven coverage collapse.

• Anytime-Valid Certification: To address the reality of continuous monitoring (optional stopping), the paper introduces an e-process based on game-theoretic probability. This certificate constrains only the conditional mean of the graph outcome, requiring no independence assumption across missions or components. It recovers the Sequential Probability Ratio Test (SPRT) exactly at the optimal betting fraction.

Key Results

1. Correlated Failure: In the same_model condition, two instances of the same model co-fail on 90.0% of the missions on which either fails ($\log OR = 6.66$, 95% CI [6.38, 7.00]). This confirms that model sharing induces massive positive dependence.
2. Model vs. Vendor: Substituting a different model significantly reduces the association (6/6 contrasts across topologies were significant). However, substituting a different vendor (while keeping models different) did not significantly reduce the association. The "vendor" variable was not a reliable predictor of failure correlation once model identity differed.
3. Marginal Sensitivity: Common dependence statistics like Jaccard overlap, $\phi$, and Kendall's $\tau_a$ are shown to be bounded by marginal failure rates. In specific conditions, these statistics reversed the apparent ordering of conditions purely due to differences in marginal failure rates, whereas marginal-free statistics (log odds ratio, Yule's Q) remained consistent.
4. Certification Improvement: Enriching the moment set from 10 functionals (marginals + pairs) to 14 (adding triples) on real data narrowed the identified interval by 85.7% and lifted the certified floor from 0.2455 to 0.4116.
5. Model-Based Collapse: In a controlled experiment, a model-based floor's coverage dropped from 0.36 to 0.01 as sample size increased from 250 to 2000 under a moment-indistinguishable misspecification, while the Tier-1 copula-agnostic floor maintained 100% coverage.
6. Anytime Validity: The e-process implementation maintained an empirical Type-I error rate of 0.0471 or below across all tested betting fractions, even under arbitrary stopping.

Significance and Claims
The paper claims to provide the first finite-sample, copula-agnostic reliability certificate for composed agent pipelines that does not assume independence. Its primary contribution is not merely measuring that failures correlate (which concurrent work has done), but providing a sound, sharp, and actionable bound that degrades honestly when dependence is unmeasured, rather than silently producing a confidently wrong number.

The authors explicitly state what they do not claim:

• They do not claim to have discovered that shared models fail together for the first time.
• They do not claim a three-level ordering of sharing (same model > same vendor > different vendor), as the vendor-level contrast failed to replicate.
• They do not claim the certificate scales to large numbers of agents ($m$) without exponential cost, nor that it applies to aggregators that are themselves LLMs.
• They do not claim the results generalize to frontier models or open-ended dialogue tasks, as the evaluation was limited to mid-sized models and deterministic retail/financial tasks.

The work is presented as a corrective to the "quiet failure" of independence assumptions in multi-agent reliability, offering a methodology that makes correlated failure measurable and ensures that guarantees degrade transparently rather than silently. All code, contracts, generators, and preregistrations are released under AGPL-3.0.