Agent Behavioral Contracts II: Certifying Compositional Reliability Without Assuming Independence

Summary

Multi-agent reliability analysis routinely assumes component failures are conditionally independent, and almost never tests it. This paper tests it and finds strong positive dependence, which inflates joint failure rates well beyond what independence-based bounds predict. It replaces the assumption with a certificate that assumes no dependence structure at all — a linear program over the joint distribution, bounded by a Bonferroni–Clopper–Pearson box — and proves that fitting a dependence model instead degrades coverage as sample size grows.

Our summary of the paper. The full abstract is on arXiv. Preprint, not peer reviewed.

Authors

• Varun Pratap Bhardwaj
• Garima Singh
• Arun Pratap Bhardwaj

Cite this paper

@misc{bhardwaj2026abcii,
  title        = {Agent Behavioral Contracts II: Certifying Compositional Reliability Without Assuming Independence},
  author       = {Varun Pratap Bhardwaj and Garima Singh and Arun Pratap Bhardwaj},
  year         = {2026},
  eprint       = {2608.12895},
  archivePrefix= {arXiv},
  primaryClass = {cs.AI},
  url          = {https://arxiv.org/abs/2608.12895}
}