# Agent Behavioral Contracts II: Certifying Compositional Reliability Without Assuming Independence arXiv: https://arxiv.org/abs/2608.12895 ยท HTML: https://mlsanity.com/paper/2608.12895/ ## Key facts - Cited by 3 papers in the map (data through 14 Oct 2026). - Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use. - Builds on 28 of its 64 references that are in the map. - First posted on arXiv 13 Aug 2026. ## Placed in - LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/) ## Builds on (most cited first, 28 of 28) - [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022) - [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022) - [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022) - [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023) - [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023) - [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023) - [Constitutional AI: Harmlessness from AI Feedback](https://mlsanity.com/paper/2212.08073/) (2022) - [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023) - [AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation](https://mlsanity.com/paper/2308.08155/) (2023) - [MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework](https://mlsanity.com/paper/2308.00352/) (2023) - [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023) - [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023) - [Encouraging Divergent Thinking in Large Language Models through Multi-Agent Debate](https://mlsanity.com/paper/2305.19118/) (2023) - [ChatDev: Communicative Agents for Software Development](https://mlsanity.com/paper/2307.07924/) (2023) - [NeMo Guardrails: A Toolkit for Controllable and Safe LLM Applications with Programmable Rails](https://mlsanity.com/paper/2310.10501/) (2023) - [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018) - [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020) - [Multi-Agent Risks from Advanced AI](https://mlsanity.com/paper/2502.14143/) (2025) - [Game-theoretic statistics and safe anytime-valid inference](https://mlsanity.com/paper/2210.01948/) (2022) - [Safe Testing](https://mlsanity.com/paper/1906.07801/) (2019) - [International AI Safety Report 2026](https://mlsanity.com/paper/2602.21012/) (2026) - [Agent Behavioral Contracts: Formal Specification and Runtime Enforcement for Reliable Autonomous AI Agents](https://mlsanity.com/paper/2602.22302/) (2026) - [Rethinking the Reliability of Multi-agent System: A Perspective from Byzantine Fault Tolerance](https://mlsanity.com/paper/2511.10400/) (2025) - [FALAT: Tracing Failures in LLM Agent Trajectories via Dependency-Guided Search](https://mlsanity.com/paper/2606.00765/) (2026) - [Can AI Agents Agree?](https://mlsanity.com/paper/2603.01213/) (2026) - [Counterfactual Graph for Multi-Agent LLM Calibration](https://mlsanity.com/paper/2605.30653/) (2026) - [VerifyMAS: Hypothesis Verification for Failure Attribution in LLM Multi-Agent Systems](https://mlsanity.com/paper/2605.17467/) (2026) - [Harnessing Disagreement: Detecting Correlated Agreement Blindness in Multi-Agent Triage](https://mlsanity.com/paper/2607.19899/) (2026) ## Built on by (most cited first, 3 of 3) - [Bounded Loops: Pre-Run Spend Bounds, Proved Termination, and Verified Completion for Agent Harnesses](https://mlsanity.com/paper/2609.27871/) (2026) - [Reliability Engineering for AI Systems: Challenges, Methods, and Directions](https://mlsanity.com/paper/2609.35316/) (2026) - [agent-risk: Risk Assessment for Changes to AI Agents](https://mlsanity.com/paper/2610.16280/) (2026) ## Abstract (arXiv) 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.