Common-Witness Certificates and Sharp Feature Bounds for Counterfactual Image Auditing

Summary

This paper formalizes a local-to-global failure mode in counterfactual image auditing: an edited image can satisfy every regional plausibility constraint with different latent 'witnesses' while no single witness explains all regions simultaneously. The authors define a common-witness grade and witness nerve, and derive exact certificate-size results: a sharp q(s+1)-role tolerant certificate for finite witness atlases (Theorem 4.1), a blocker-hypergraph characterization yielding exact repair counts (Proposition 4.2), and a heterogeneous action-stratified certificate of size Σ(d_a+1) (Theorem 4.3) — all labeled specializations of classical and fractional Helly theory. The framework explicitly separates auditing from identification: shared exogeneity admits every coupling (Proposition 3.1), while an externally declared feature-support relation yields sharp partial-identification intervals via coupling linear programs (Theorem 5.1); simultaneous Clopper–Pearson/Hoeffding marginal regions give finite-sample outer coverage of the entire identified interval (Theorem 6.1). Experiments: MNIST rotation audits show patchwork local acceptance 0.9702–0.9804 versus 0–0.0018 globally (AUROC 0.9988–1.0000); Morpho-MNIST and smallNORB paired studies show similar separation (Morpho global acceptance 0.113750); synthetic checks cover in all 1,800 repetitions; 35 structured scaling cases finish in 34.85 s. Main limitations: validation is confined to synthetic renderers and toy benchmark datasets; the witness relation is assumed rather than scientifically validated; smallNORB uses only ten objects; and negative controls are constructed, so the separation is demonstrated rather than discovered in real editors.