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

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

arXiv:2609.03973v1 [cs.AI] 3 Sep 2026

Usef Faghihi∗ and Amir Saki∗

Abstract. Structured image editors may satisfy every regional plausibility constraint separately although no single latent explanation is compatible with the complete output. We formulate this local-to-global failure through a common-witness grade and its witness nerve. The framework separates auditing from causal identification: shared exogeneity alone permits every coupling of the regime marginals, whereas a scientifically justified witness relation yields exactly the relation-supported couplings and hence sharp feature-level partial-identification bounds. For quasiconvex regional losses, classical Helly theory gives finite incompatibility certificates. For the labeled witness structures generated by the audit, we derive a heterogeneous action-stratified certificate, a sharp tolerant certificate for finite witness atlases, and a blocker-hypergraph repair formula. Fractional Helly theory converts dense local compatibility into a large jointly coherent subset. Simultaneous confidence regions for regime marginals provide finite-sample outer confidence bounds for the complete identified interval; Bonferroni–Clopper–Pearson bands give a nonasymptotic multinomial construction. In controlled MNIST rotations and finite paired studies on Morpho-MNIST and smallNORB, archived summaries report coherent-pair acceptance of 0.9593–0.9778, while regional-action patchworks retain local acceptance of 0.9702–0.9804 but have global acceptance of 0–0.1138. Synthetic studies exercise sharp bounds, certificate recovery, and structured computation up to 104 feature states and 105 regional constraints. The method audits a prespecified feature relation; it does not identify unrestricted pixel-level counterfactuals. Key words. counterfactual images, partial identification, Helly theorem, optimal transport, finite-sample inference, infeasibility certificates MSC codes. 52A35, 62G15, 62P30, 68T45, 90C05

1. Introduction. Counterfactual image editing asks what the image of the same unit would have been under another intervention. In an augmented structural causal model (ASCM), both potential images are evaluated at the same exogenous state. That semantic convention does not reveal their joint distribution. Pan and Bareinboim show that unrestricted pixel-level counterfactuals are generally not identified from image–label samples, even when a latent causal diagram is supplied [21]. Their feature-based relaxation is therefore a bound on declared care-set quantities, not recovery of the true pixel coupling. We study a complementary auditing failure. An edited image can satisfy each protectedregion constraint with a different latent explanation while no one explanation satisfies all regions simultaneously. Formally, a witness for each region need not be one witness for every region. This global-witness gap is invisible to an audit that aggregates independent local passes. The gap becomes scientifically informative only when the witness family is anchored outside the candidate pair. Examples include a validated renderer, paired interventions, or a design guarantee. A similarity score fitted only to unpaired images is not, by itself, cross-world ∗

Department of Mathematics and Computer Science, Université du Québec à Trois-Rivières, Trois-Rivières, Quebec, Canada (usef.faghihi@uqtr.ca). Both authors contributed equally: each contributed 50% of the theoretical work and 50% of the experimental work. 1

2

U. FAGHIHI AND A. SAKI

information. We encode an externally justified witness family by regional costs, use their common sublevel intersections to audit an image pair, and project the resulting admissibility rule to a prespecified finite feature. The projection is then an explicit assumption in a support-only partial-identification model; it is not inferred from the causal graph. The contribution is a certificate-to-inference pipeline: 1. We turn regional costs into a graded feasibility complex. For the labeled witness structures produced by this audit, we derive exact certificate-size and repair formulas: a sharp q(s + 1) certificate for a finite atlas with q witnesses and s exceptional roles, a blocker-hypergraph description of minimal explanations, and a heterogeneous action-stratified certificate with P size a (da + 1). Classical Helly, union-of-convex-set, fractional-Helly, and tolerance results supply the underlying intersection principles [6, 2, 9, 20, 15]. 2. We separate this audit from identification. A boundary proposition records that shared exogeneity alone admits every coupling. Once an external relation is declared, its relationsupported couplings give the exact identified set in a stated support-only two-regime feature model. No coupling inside that set is silently selected. 3. We propagate simultaneous marginal confidence regions through the coupling program to obtain finite-sample outer confidence bounds for the complete oracle interval. Controlled and finite paired studies illustrate the local-to-global separation, while synthetic programs check the predicted interval and computational behavior. We report the empirical information boundary explicitly. The accompanying public repository contains the implementation, tests, configurations, and retained outputs; external datasets must be obtained from their original sources. The main line is regional costs −→ common-witness certificate −→ declared feature relation −→ sharp coupling bounds −→ outer confidence bounds. Technical extensions, full protocols, and secondary analyses are indexed in the Supplementary Material. 2. Related work and positioning. Pan and Bareinboim establish the nonidentification boundary for counterfactual image editing and propose feature-level causal bounds [21]; later work develops a disentangled causal latent editor [22]. Our object is different: an externally anchored same-witness audit followed by a support-only partial-identification analysis. It neither replaces their construction nor weakens their impossibility theorem. Partial identification of joint potential-outcome functionals has a long history [18, 3, 26, 11, 10, 27]. Coupling and transport methods make the remaining cross-world ambiguity explicit [25, 23, 7]. The linear program and its transport dual are established tools. The contribution here is their placement after an auditable, externally sourced relation, together with a precise support-only sharpness statement. Helly’s theorem and fractional Helly theory control intersections of convex families [6, 14, 13]. Amenta and Eckhoff–Nischke treat unions of convex components and the generalized pigeonhole mechanism [2, 9]; tolerance variants are also established [20, 15]. Our certificate theorems are exact labeled specializations for the witness structures arising in the audit, with sharpness and blocker-based repair. We do not claim that finite-feature bounding, transport duality, or Helly

COMMON-WITNESS IMAGE AUDITING

3

theory is new. Finally, Theorem 6.1 is confidence-set propagation. Its importance here is the estimand: it covers the entire identified interval. Clopper–Pearson bands are conservative but nonasymptotic [5]; more efficient simultaneous multinomial regions can be substituted if their joint coverage is proved [12, 24, 19]. 3. Setting and the common-witness audit. 3.1. Feature target and identification boundary. Let X ∈ {0, 1} denote an intervention and Ix ∈ I the corresponding potential image, where I is a standard Borel space. We prespecify a measurable finite feature Ψ : I → Y,

Y = {1, . . . , K},

Yx = Ψ(Ix ),

and assume that the single-world laws µx (y) = P(Yx = y) are identified from randomized intervention data or another valid causal argument. Image samples alone do not generally provide this identification. Write πyy′ = P(Y0 = y, Y1 = y ′ ). Our targets are bounded linear functionals X (3.1) Hh (π) = h(y, y ′ )πyy′ . y,y ′

Transition probabilities, average feature changes, and numerators of conditional feature queries have this form. A conditional query with a positive identified denominator µ0 (B) is obtained by dividing the corresponding numerator by that fixed quantity. Proposition 3.1 (Shared-exogeneity saturation). Let µ0 , µ1 be probability laws on a common standard Borel space. Every coupling π ∈ Π(µ0 , µ1 ) is the joint potential-outcome law of a two-regime structural model with one exogenous variable shared across interventions. Proof. On the probability space with law π, let U = (U0 , U1 ) be the coordinate map and set f (x, u0 , u1 ) = ux . Then Y = f (X, U ) satisfies Yx = Ux and L(Y0 , Y1 ) = π. Both worlds use the same realization of U . Proposition 3.1 is a boundary lemma, not a novelty claim. It shows that using the same witness twice cannot by itself overcome the causal hierarchy. Information enters only through restrictions on admissible exogenous states, response functions, or cross-world pairs. 3.2. Regional losses, grade, and nerve. Let W be a declared witness space and let cr (w; i, j) ≥ 0, r ∈ [m] = {1, . . . , m}, measure the violation of role r by witness w for the factual–candidate pair (i, j). When (i, j) is fixed or clear from context, we suppress it from the notation. Thus, for example, cr (w) denotes cr (w; i, j); the same convention applies to all witness sets, grades, and tolerant quantities defined below. The ASCM response type U and the auditing witness w are distinct objects unless an external scientific argument identifies them. At tolerance ε, put (3.2)

Aεr (i, j) = {w ∈ W : cr (w; i, j) ≤ ε}.

Compactness and lower semicontinuity are imposed whenever an attained minimizer is used; the measurable version is given in Supplement S1.

4

U. FAGHIHI AND A. SAKI

Definition 3.2 (Common-witness grade and nerve). For nonempty S ⊆ [m], define (3.3)

F (S; i, j) = inf max cr (w; i, j), w∈W r∈S

ρ(i, j) = F ([m]; i, j).

The witness nerve at scale ε is ( (3.4)

Kε (i, j) = {∅} ∪

)

∅ ̸= S ⊆ [m] :

\

Aεr (i, j) ̸= ∅

.

r∈S

If T ⊆ S, then F (T ; i, j) ≤ F (S; i, j). Consequently Kε is a simplicial complex, maximal faces are maximal jointly explainable role sets, and minimal nonfaces are minimal incompatibility explanations. Under attainment, (i, j) has one global witness exactly when ρ(i, j) ≤ ε. To permit a prespecified number of regional exceptions, define (3.5)

F [s] (S; i, j) = inf min max cr (w; i, j), w∈W D⊆S r∈S\D |D|≤s

max ∅ := 0,

and ρs = F [s] ([m]). The integer s is a within-pair role budget; it is not a probability mass of inadmissible feature pairs. 3.3. From image witnesses to a feature relation. The audit induces the existential feature projection   is a lift (i, j) with Ψ(i) = y, Ψ(j) = y ′ , . (3.6) Rε = (y, y ′ ) : there and ρ(i, j) ≤ ε The causal model must separately assume P{(Y0 , Y1 ) ∈ Rε } = 1. The relation is therefore an externally declared Layer-3 restriction, not a consequence of its definition. An existential feature projection can also be an outer relaxation of the image-level problem; it is lossless only under a feature-saturation or conditional-fiber condition (Supplement S3). Without an external anchor, the honest default is Rε = Y 2 . 4. Combinatorial certificates and repair. We first give the finite-atlas result used directly by the experiments, then place its convex analogue in the classical Helly context. 4.1. Finite atlases. Theorem 4.1 (Exact finite-atlas tolerant certificate). Suppose W is finite with q = |W| and 0 ≤ s < m. Then (4.1)

ρs (i, j) =

max

F [s] (S; i, j).

∅̸=S⊆[m] |S|≤min{q(s+1),m}

Thus tolerant incompatibility has a certificate using at most q(s + 1) roles. The bound is best possible. Proof. For fixed w, arrange its m costs in nonincreasing order, c[1] (w) ≥ · · · ≥ c[m] (w). Deleting at most s roles leaves the smallest possible maximum c[s+1] (w), hence ρs = min c[s+1] (w). w∈W

COMMON-WITNESS IMAGE AUDITING

5

S For every w, choose Tw containing s + 1 roles with its largest costs and put S⋆ = w Tw . Then |S⋆ | ≤ q(s + 1). The (s + 1)st largest cost of each w on S⋆ equals its (s + 1)st largest cost on [m], so F [s] (S⋆ ) = ρs . Monotonicity gives the reverse inequality for every subfamily. For sharpness, take m = q(s + 1) and partition the roles into disjoint blocks Bw of size s + 1. Fix 0 ≤ b < d and set cr (w) = d for r ∈ Bw and cr (w) = b otherwise. The complete family has tolerant grade d. Every proper role set omits a role from some Bw ; for that witness, at most s retained roles have cost d, so its tolerant grade is at most b. Thus all q(s + 1) roles can be necessary. The proof is an exact consequence of the labeled finite-atlas structure. We do not claim that tolerant Helly theory is new; generic tolerance transfers and modern tolerance complexes are studied in [20, 15]. The audit-specific value of Theorem 4.1 is its sharp certificate and the explicit repair formula below. Proposition 4.2 (Blocker duality and exact repair). For fixed ε, let ε Bw = {r : cr (w; i, j) > ε},

ε Gεw = [m] \ Bw .

Then (4.2)

F [s] (S; i, j) ≤ ε

⇐⇒

ε ∃w ∈ W : |S ∩ Bw | ≤ s.

Minimal s-tolerant incompatibility explanations are the inclusion-minimal (s + 1)-fold transversals of the bad-role hypergraph. Each has at most q(s + 1) roles. For s = 0, [ ε ε (4.3) Kε = 2Gw , s⋆ε := min{s : ρs ≤ ε} = min |Bw |. w∈W

w∈W

Proof. For fixed w, all retained costs are at most ε after at most s deletions exactly when ε . This proves (4.2); negating it yields the multipleat most s members of S belong to Bw transversal description. Choosing s + 1 bad roles for every witness gives the size bound. Finally, ε | is exactly the number of deletions required for witness w, and minimizing over w proves |Bw (4.3). Rowwise order selection computes ρs , one valid certificate, and the exact repair number in O(qm) selection time (or O(qm log m) by sorting). Enumeration of all minimal transversals can still be exponential [1]. 4.2. Convex and action-stratified atlases. For a compact convex witness set of affine dimension d, continuous quasiconvex role losses have convex closed sublevel sets. The classical Helly theorem then gives (4.4)

ρ(i, j) =

max F (S; i, j). ∅̸=S⊆[m] |S|≤d+1

Indeed, at the maximum local grade every d + 1 sublevel sets intersect, so the complete family intersects. Equation (4.4) is a direct application of Helly’s theorem, not a new intersection theorem. Many audits have a discrete requested action and continuous nuisance parameters. The resulting witness space is a labeled disjoint union rather than one convex set.

6

U. FAGHIHI AND A. SAKI

F Theorem 4.3 (Heterogeneous action-stratified certificate). Suppose W = qa=1 Wa , where Wa is nonempty, compact, convex, and has affine dimension da . Assume every role loss is continuous and quasiconvex on each stratum. Define Fa (S) = min max cr (w), w∈Wa r∈S

and H = min{m, (4.5)

F (S) = min Fa (S), a

Pq

a=1 (da + 1)}. Then

F ([m]) =

max F (S). ∅̸=S⊆[m] |S|≤H

The bound is sharp for every dimension list when m =

P

a (da + 1).

Proof. Let ρa = Fa ([m]).SApplying (4.4) within stratum a gives Sa ⊆ [m], |Sa | ≤ da + 1, with Fa (Sa ) = ρa . Put S⋆ = a Sa . Monotonicity gives ρa = Fa (Sa ) ≤ Fa (S⋆ ) ≤ Fa ([m]) = ρa for every a. Hence F (S⋆ ) = mina ρa = F ([m]) and |S⋆ | ≤ H. For sharpness, create one block of da + 1 roles (a, j) per stratum and take Wa = ∆da . For x ∈ ∆db set ( (da + 1)xj , a = b, c(a,j) (b, x) = 0, a ̸= b. The complete block has grade one in its stratum, so the full-family grade is one. If (a, j) is removed, choose stratum a and vertex ej ; every remaining cost is zero. Thus every proper subfamily has grade zero. Classical results for unions of convex sets already imply closely related q(d + 1) Helly numbers [2, 9]. The content of Theorem 4.3 is the audit-specialized exact grade equality, heterogeneous dimension sum, and sharp labeled construction, not a claim of a fundamentally new general Helly theorem. The witness nerve also quantifies approximate coherence. Let h = d + 1 and let Nh (ε) count its feasible h-faces. If Dε is the largest number of roles explained by one witness and tε = m − Dε , Kalai’s exact fractional-Helly bound gives     m d + tε (4.6) Nh (ε) ≤ − . h h In particular, if at least an α fraction of the h-subsets are feasible, one witness explains at least l  m (4.7) 1 − (1 − α)1/(d+1) m roles [14, 13, 8]. The complete proof and exact integer inversion are in Supplement S4. Dense local compatibility yields a large coherent core, not global compatibility.

COMMON-WITNESS IMAGE AUDITING

7

If estimated losses obey maxr supw |b cr (w; i, j) − cr (w; i, j)| ≤ δ, then every tolerant grade changes by at most δ and [s] b [s] ⊆ K [s] . Kε−δ ⊆ K ε ε+δ

(4.8)

This is a deterministic robustness statement; statistical use requires an independently justified uniform error bound. Finite-net outer approximation and exact nerve recovery away from critical grades are in Supplement S4. 5. Sharp feature bounds. For a declared relation R ⊆ Y 2 , let (5.1)   X X ′ = µ0 (y), ΠR (µ0 , µ1 ) = π ∈ RK×K : π πyy′ = µ1 (y ′ ), yy +  ′ y

y

πyy′ = 0 outside R

 

.



Equivalently, π1 = µ0 fixes row sums and π ⊤ 1 = µ1 fixes column sums. The transpose is needed because left multiplication by π ⊤ sums the original matrix down its rows, producing one total for each column. The support-only feature model contains every two-regime feature SCM with these marginals and P{(Y0 , Y1 ) ∈ R} = 1, with no other response function, latent-DAG, or full-image restriction. Theorem 5.1 (Sharp support-only identified interval). If ΠR (µ0 , µ1 ) is nonempty, then the sharp identified set for (3.1) in the support-only feature model is   (5.2) min Hh (π), max Hh (π) . π∈ΠR (µ0 ,µ1 )

π∈ΠR (µ0 ,µ1 )

Both endpoints and every intermediate value are attainable. Proof. The feasible set is a nonempty compact convex polytope and Hh is linear, so its image is a closed interval with attained endpoints. Every model in the declared class induces a feasible coupling. Conversely, Proposition 3.1 realizes every feasible coupling as a shared-exogenous feature SCM, and mixtures realize all intermediate values. Sharpness is relative to the displayed model. If a fixed full-image law, latent DAG, or nonsaturated image relation imposes further restrictions, the feature program can be only outer. This qualification prevents an audit relation from being mistaken for identification of the Pan–Bareinboim pixel counterfactual. If the external science supports only a violation-mass budget τ , replace hard support by (5.3)

(τ )

ΠR (µ0 , µ1 ) = {π ∈ Π(µ0 , µ1 ) : π(Rc ) ≤ τ }.

The same compactness argument makes its optimized interval sharp in the corresponding budget model and nested in τ . The smallest feasible budget is the Hall deficiency δR (µ0 , µ1 ) = max{µ0 (A) − µ1 (R(A))}, A⊆Y

by max-flow/min-cut and the finite Hall–Strassen criterion [25]. These established transport results, their duals, and the Polish-space extension are collected in Supplements S2–S3. The parameter τ is sensitivity input, not a probability learned from unpaired images.

8

U. FAGHIHI AND A. SAKI

For sparse R, the two endpoint programs use one variable per allowed edge and 2|R| nonzeros in the marginal equality matrix. The relation is first checked for feasibility; infeasibility is reported rather than hidden by renormalization. 6. Finite-sample outer inference. Let Cα be any random simultaneous confidence region for the two regime marginals satisfying P{(µ0 , µ1 ) ∈ Cα } ≥ 1 − α.

(6.1)

For a fixed known relation define the union of compatible couplings bα (R) = P

(6.2)

[

ΠR (ν0 , ν1 ).

(ν0 ,ν1 )∈Cα

Theorem 6.1 (Outer coverage of the complete oracle interval). Let [L⋆ , U ⋆ ] be the sharp interval over ΠR (µ0 , µ1 ). If the random endpoints are measurable, then ( (6.3)

P [L⋆ , U ⋆ ] ⊆

"

#) inf bα (R) π∈P

Hh (π),

sup

Hh (π)

≥ 1 − α.

bα (R) π∈P

If the random feasible set is empty, reporting the vacuous payoff range preserves the guarantee. Proof. On the event in (6.1), every oracle-feasible coupling belongs to (6.2). Minimizing over the larger set cannot increase the lower endpoint, and maximizing cannot decrease the upper endpoint. A distribution-free concrete choice uses independent within-regime samples. If Nx (y) is the count in cell y among nx observations, construct a two-sided Clopper–Pearson interval for each of the M = 2K marginal cells at cellwise noncoverage α/M . In beta-quantile notation its endpoints are ( 0, Nx (y) = 0,
(6.4) ℓx (y) = −1 α Beta 2M ; Nx (y), nx − Nx (y) + 1 , Nx (y) > 0, ( 1, Nx (y) = nx ,
(6.5) ux (y) = −1 α Beta 1 − 2M ; Nx (y) + 1, nx − Nx (y) , Nx (y) < nx . Each count is marginally binomial, so Bonferroni gives simultaneous coverage despite dependence among cells within a multinomial sample [5]. Here, exact means finite-sample coverage of at least the nominal level, not equality or shortest possible width. Hoeffding bands provide a simpler alternative. The inference target is the complete oracle interval, not one selected coupling. b + ) ≥ 1 − β, the same containment argument If a random outer relation satisfies P(R⋆ ⊆ R b + . Sample splitting and a union bound give coverage at least 1−α −β when the program uses R alone does not establish this outer-relation property. Compatibility tests and independent finite-panel variants, with their required sampling assumptions, are in Supplement S4.

COMMON-WITNESS IMAGE AUDITING

9

7. Audit and optimization pipeline. The operational procedure keeps its information sources separate: 1. Prespecify Ψ, protected roles, allowed descendants, the witness atlas, tolerance, and any role or relation-violation budget. 2. For a candidate pair compute ρ or ρs and return a short blocking-role certificate and exact repair count when the audit fails. 3. Project the externally justified audit to a feature relation and state explicitly whether that projection is exact or outer. 4. Estimate the two single-world marginals and solve the lower and upper support or budget transport programs, using simultaneous marginal bands when finite-sample coverage is required. 5. Return the identified interval, outer confidence interval, and incompatibility explanation. Selecting a point inside the interval requires a separate declared decision rule. For nonconvex neural witness spaces not represented by a verified finite atlas, a verified global optimizer would be needed; the certificates above do not validate an arbitrary local neural search. 8. Numerical studies. The numerical studies address three questions that correspond directly to the theory: whether regional plausibility can coexist with global incompatibility, whether a declared relation can sharpen feature-level bounds without concealing infeasibility or misspecification, and whether the resulting optimization and certificate computations remain tractable in structured large instances. The studies are not presented as evidence that an unrestricted pixel-level counterfactual is identified. Status of the numerical evidence. The accompanying public repository contains the implementation, tests, configurations, retained outputs, and integrity manifests supporting the numerical studies. External datasets are not redistributed and must be obtained from their original sources. The repository documents the scope of the retained evidence and the limitations of exact historical and cross-platform replay. 8.1. Common-witness audits. Controlled rotation audit.. We first use the official MNIST training and test partitions [16] in a controlled renderer experiment. For a source image S, one angle A ∈ {−20, −10, 0, 10, 20} degrees is applied to the whole image, followed by clipped independent Gaussian measurement noise with standard deviation 0.02. The witness atlas is the same declared set of five renderer responses. For rectangular region Pr , the discrepancy of angle a is  1/2 X cr (a) = |Pr |−1 {I1 (p) − Rotate(I0 , a)(p)}2  . p∈Pr

The local and common-witness scores are L = max min cr (a), r

a

ρ = min max cr (a). a

r

10

U. FAGHIHI AND A. SAKI

Thus L permits a different angle in each region, whereas ρ requires one angle to explain every region. A split of 3,000 training images sets the 0.975 order-statistic threshold and a disjoint 3,000-image split assesses relation violations. The archived protocol evaluates the official 10,000 test images at three seeds and four fixed partitions (4, 9, 16, and 64 regions). These are twelve configurations, not 120,000 independent test units: the same 10,000 images recur. The principal negative control selects angles separately by region, so it is constructed to satisfy the local quantifier while violating the common-angle quantifier. Because every split uses the same specified renderer, this is held-out validation within a controlled mechanism, not independent scientific validation of a causal relation. Separately fitted editor and witness.. The second study uses paired responses supplied by Morpho-MNIST [4] and smallNORB [17]. Morpho-MNIST provides index-matched plain, thin, and thick digits; these are benchmark-generated transformations rather than physical interventions. smallNORB provides physical toy objects photographed under factorially varied pose and illumination. Lighting 0 is paired with lightings 1, 3, and 5, holding object, pose, and camera fixed. These are matched photographs, not observations of the same stochastic unit in two counterfactual worlds. An action-conditional latent-residual editor is fitted on units disjoint from a separate PCA–ridge witness. The editor is an experimental vehicle rather than a claimed architectural contribution. The witness divides each image into a fixed 4×4 grid and normalizes each regional discrepancy by an action-specific held-out threshold qa . For normalized costs e cr (a) = cr (a)/qa , the relevant scores are L = max min e cr (a), r

a

ρfree = min max e cr (a), a

r

ρreq = max e cr (areq ). r

A strictly positive qa is required; the protocol uses a positive calibration quantile, and any zero quantile would require a positive floor fixed before evaluation. A score at most one is accepted. The free score asks whether some declared action explains the complete image; only the requested-action score tests compliance with the requested edit. The negative control alternates paired actions across the sixteen regions. It can therefore be locally plausible even though no single action explains the image. The relation panel contains 4,000 Morpho-MNIST base digits and ten smallNORB physical objects. The editor evaluation uses a disjoint 6,000 Morpho-MNIST base digits and fifteen smallNORB physical objects, with three prespecified editor seeds. Repeated actions and views are dependent measurements of the same base digit or object and are not counted as new independent units. In particular, the smallNORB threshold was calibrated from only five physical objects and is an empirical rule, not a distribution-free conformal guarantee. Table 1 shows the intended local-to-global separation in all three studies. In the controlled renderer, patchworks retain approximately the same local acceptance as coherent pairs but almost never admit one global angle. The learned-witness study shows the same qualitative separation, although the Morpho-MNIST free-action global acceptance of 0.113750 is materially above zero. On the disjoint editor sets, the conditional editor’s archived mean whole-image SSIM is 0.903131 versus 0.870558 for conditional ridge on Morpho-MNIST, and 0.986064 versus 0.985821 on smallNORB. We report the corresponding improvements only to appropriate precision, 0.0326 and 0.00024: the latter is practically very small.

COMMON-WITNESS IMAGE AUDITING

11

Study

Evaluation unit

Coherent

Patch local

Patch global

AUROC

MNIST rotations Morpho-MNIST smallNORB

10,000/setting 4,000 digits 10 objects

0.9709–0.9777 0.977750 0.959259

0.9702–0.9804 0.976750 0.972840

0–0.0018 0.113750 0

0.9988–1.0000 0.987213 1.000000

Table 1 Archived aggregate common-witness results. Coherent is the free-angle global acceptance for controlled MNIST and requested-action acceptance for the paired studies; patch global uses the free common-action score. MNIST entries are ranges over twelve seed–partition configurations that reuse the same test images. The smallNORB AUROC of 1 is complete separation on a fixed ten-object panel, not a population-perfect guarantee.

The smallNORB aggregate also conceals important object-level uncertainty. Requestedaction acceptance ranges from 0.779835 to 1 across ten objects. Zero global patchwork acceptances among ten objects has one-sided 95% Clopper–Pearson upper limit 0.2589. Consequently, the reported AUROC 1 supports finite-panel separation of the constructed control but does not establish population-perfect detection or a population patchwork acceptance below 0.20. 8.2. Sharp bounds and finite-sample outer inference. A three-state synthetic feature provides a direct numerical check of the support-constrained coupling program. With only the two regime marginals, the sharp target interval is [0.35, 0.80]. Imposing the declared one-step relation narrows it to [0.55, 0.70]. A misspecification control places 0.20 of the true coupling mass outside that relation, and the constrained interval then fails to cover the true target. The negative control is essential: narrowing is created by the added relation, not by the observed marginals alone. For finite-sample inference, independent samples from each regime are drawn at n ∈ {100, 300, 1000, 3000, 10000, 30000}, with 300 repetitions per sample size. The archived Hoeffding outer intervals cover the complete oracle identified interval in all 1,800 repetitions, with mean width decreasing from 0.9237 to 0.2075. A later analysis applies the exact Bonferroni–Clopper–Pearson construction in (6.4)–(6.5) to the same archived cell counts. Its reported mean widths decrease from 0.7413 to 0.1861, reductions of 10.3%–27.8% relative to Hoeffding, and all 1,800 intervals again cover. These successes are an implementation check under the stated simulation law, not evidence of exact nominal calibration; the coverage guarantee follows from the theorem. The exact-band comparison is post-confirmatory and descriptive because it was specified after the Hoeffding outcomes had been inspected. The controlled audit-to-bound panel also records a necessary negative result. It fixes ten images per digit, for N = 100 units, and the raw witness relation contains 0.0097 of the N 2 candidate pairs. The hard-support transport program is infeasible and is reported as such; no renormalization or silent relaxation is used. With the predeclared empirical violation budget τ = 0.08, the archived interval is [0.1517, 0.2600], compared with [0.0600, 0.8200] without the image relation, and contains the hidden paired target 0.2100. However, balancing the panel by digit violates the i.i.d. premise of the intended pooled binomial guarantee. A post-hoc stratified sensitivity calculation uses τ = 0.12 and gives [0.1183, 0.2975], also containing 0.2100.

12

U. FAGHIHI AND A. SAKI

Figure 1. Archived synthetic summaries. Left: all pairs can be compatible while the complete witness intersection is empty. Middle and right: observed coverage of the complete oracle interval and contraction of the Hoeffding outer interval as the regime sample sizes increase.

Structured problem Sparse coupling Affine minimax, d = 4 Affine minimax, d = 8 Affine minimax, d = 16 Helly-tight Finite-atlas sharpness

Largest instance

Representation

Time (s)

10,000 states 100,000 roles 100,000 roles 100,000 roles 1,024 roles 12 roles

109,970 edges 5-role certificate 9-role certificate 17-role certificate dimension 1,023 4,094 proper faces

18.521 0.251 0.385 0.786 9.704 0.192

Table 2 Largest successful cases in the archived hardware-specific scaling summary. Relations and affine certificate families are supplied rather than learned. Times are descriptive and hardware-specific.

Neither relaxed result is a confirmatory 95% confidence statement; a new independent panel with the stratified procedure fixed in advance would be required. 8.3. Structured computational checks. The archived computations use sparse edge variables for banded transport and short dual certificates for repeated-simplex minimax instances. These tests check the implementations against known optima and residual conditions; they do not claim comparable scaling for dense arbitrary relations, face enumeration, or nonconvex neural witness optimization. All 35 archived scaling cases are reported as successful in 34.85 seconds total with peak resident memory 0.483 GiB. At 10,000 states, sparse transport replaces 108 dense state pairs by 109,970 edge variables; the reported marginal residuals are below 1.4 × 10−18 . Across the affine cases, the largest reported primal, stationarity, or duality error is 3.34 × 10−16 . Constructed leave-one-out atlases with m = 4, . . . , 12 accept every nonempty proper role set and reject the full set, attaining the finite-atlas certificate bound. These are numerical verification and structured-scaling results, not an empirical claim about naturally occurring high-order image obstructions. 8.4. Empirical scope. The experiments validate the declared computations and local-toglobal failure mode on controlled or finite paired response families. They do not establish the

COMMON-WITNESS IMAGE AUDITING

13

scientific correctness of an arbitrary relation, identify an unrestricted counterfactual image, or infer a joint multi-regime image law. Morpho-MNIST is synthetic, and smallNORB has only ten physical objects in the relation panel. The reported large-state computations rely on supplied sparse or repeated structure. 9. Scope, information boundary, and limitations. We first clarify the scope of the results. Unrestricted pixel-level counterfactuals are generally not identified from unpaired regime marginals. Accordingly, the framework targets sharp bounds for prespecified finite-dimensional image features under a declared support restriction. This is the identified object of the analysis rather than an approximation to an otherwise identified pixel-level counterfactual. The witness atlas and the cross-world relation are additional scientific inputs, not consequences of the observed regime marginals. The witness atlas determines the coherence question being audited, whereas the relation determines the admissible feature couplings used for partial identification. If either is misspecified, the audit may reject coherent pairs or the identified interval may exclude the true target. Sample splitting can assess empirical performance but cannot by itself establish the causal validity of these inputs. Likewise, violation budgets are sensitivity parameters unless they are independently calibrated. A further information boundary arises from feature projection. Projecting an image-level relation onto a coarse feature space can discard image-level restrictions. The feature-level and image-level analyses coincide only under the feature-saturation or conditional-fiber conditions stated in the Supplementary Material. The current experiments provide controlled evaluations on MNIST, Morpho-MNIST, and smallNORB, together with synthetic and computational studies. They validate the predicted local–global separation, sharp-bound calculations, finite-sample coverage, and structured computational scaling in these settings. Evaluation on broader natural-image domains and empirical validation of the multi-regime extension are left for future work. 10. Conclusion. Local regional plausibility need not imply one globally coherent counterfactual explanation. The common-witness grade records this distinction as a feasibility complex. Finite and action-stratified witness structures yield short exact certificates and repair counts; an externally justified feature relation then narrows, but does not select within, the coupling of the regime marginals. Optimizing over all compatible couplings gives sharp feature bounds in the stated support-only model, and simultaneous marginal confidence regions give finite-sample outer coverage of the complete oracle interval. The resulting pipeline is mathematically explicit about where information enters and where ambiguity remains. Its validity in a new application rests on prespecification, external validation of the witness relation, and reproducible evidence at the correct independent unit. Code and data availability. The implementation code, experiment runners, tests, protocols, retained aggregate outputs, and reproduction instructions are available here. External datasets are not redistributed and must be obtained from the original sources cited in the Supplementary Material. Documented reproduction limitations are provided in the repository. REFERENCES

14

U. FAGHIHI AND A. SAKI

[1] E. Amaldi, M. E. Pfetsch, and J. Trotter, Leslie E., On the maximum feasible subsystem problem, IISs and IIS-hypergraphs, Mathematical Programming, 95 (2003), pp. 533–554, https://doi.org/10. 1007/s10107-002-0363-5. [2] N. Amenta, A short proof of an interesting helly-type theorem, Discrete & Computational Geometry, 15 (1996), pp. 423–427, https://doi.org/10.1007/BF02711517. [3] A. Balke and J. Pearl, Bounds on treatment effects from studies with imperfect compliance, Journal of the American Statistical Association, 92 (1997), pp. 1171–1176, https://doi.org/10.1080/01621459. 1997.10474074. [4] D. C. Castro, J. Tan, B. Kainz, E. Konukoglu, and B. Glocker, Morpho-MNIST: Quantitative assessment and diagnostics for representation learning, Journal of Machine Learning Research, 20 (2019), pp. 1–29, https://www.jmlr.org/papers/v20/19-033.html. [5] C. J. Clopper and E. S. Pearson, The use of confidence or fiducial limits illustrated in the case of the binomial, Biometrika, 26 (1934), pp. 404–413, https://doi.org/10.1093/biomet/26.4.404. [6] L. Danzer, B. Grünbaum, and V. Klee, Helly’s theorem and its relatives, in Convexity, vol. 7 of Proceedings of Symposia in Pure Mathematics, American Mathematical Society, 1963, pp. 101–180. [7] L. De Lara, A. González-Sanz, N. Asher, L. Risser, and J.-M. Loubes, Transport-based counterfactual models, Journal of Machine Learning Research, 25 (2024), pp. 1–59, https://www.jmlr.org/ papers/v25/21-1440.html. [8] J. Eckhoff, An upper-bound theorem for families of convex sets, Geometriae Dedicata, 19 (1985), pp. 217–227, https://doi.org/10.1007/BF00181472. [9] J. Eckhoff and K.-P. Nischke, Morris’s pigeonhole principle and the helly theorem for unions of convex sets, Bulletin of the London Mathematical Society, 41 (2009), pp. 577–588, https://doi.org/10.1112/ blms/bdp024. [10] Y. Fan, E. Guerre, and D. Zhu, Partial identification of functionals of the joint distribution of potential outcomes, Journal of Econometrics, 197 (2017), pp. 42–59, https://doi.org/10.1016/j.jeconom.2016.10. 005. [11] Y. Fan and S. S. Park, Sharp bounds on the distribution of treatment effects and their statistical inference, Econometric Theory, 26 (2010), pp. 931–951, https://doi.org/10.1017/S0266466609990168. [12] L. A. Goodman, On simultaneous confidence intervals for multinomial proportions, Technometrics, 7 (1965), pp. 247–254, https://doi.org/10.1080/00401706.1965.10490252. [13] G. Kalai, Intersection patterns of convex sets, Israel Journal of Mathematics, 48 (1984), pp. 161–174, https://doi.org/10.1007/BF02761162. [14] M. Katchalski and A. Liu, A problem of geometry in Rn , Proceedings of the American Mathematical Society, 75 (1979), pp. 284–288, https://doi.org/10.1090/S0002-9939-1979-0532152-6. [15] M. Kim and A. Lew, Leray numbers of tolerance complexes, Combinatorica, 43 (2023), pp. 985–1006, https://doi.org/10.1007/s00493-023-00044-5. [16] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, Gradient-based learning applied to document recognition, Proceedings of the IEEE, 86 (1998), pp. 2278–2324, https://doi.org/10.1109/5.726791. [17] Y. LeCun, F. J. Huang, and L. Bottou, Learning methods for generic object recognition with invariance to pose and lighting, in Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2, 2004, pp. 97–104, https://doi.org/10.1109/CVPR.2004.1315150. [18] C. F. Manski, Nonparametric bounds on treatment effects, American Economic Review, 80 (1990), pp. 319–323. [19] W. L. May and W. D. Johnson, Constructing two-sided simultaneous confidence intervals for multinomial proportions for small counts in a large number of cells, Journal of Statistical Software, 5 (2000), pp. 1–24, https://doi.org/10.18637/jss.v005.i06. [20] L. Montejano and D. Oliveros, Tolerance in helly-type theorems, Discrete & Computational Geometry, 45 (2011), pp. 348–357, https://doi.org/10.1007/s00454-010-9296-6. [21] Y. Pan and E. Bareinboim, Counterfactual image editing, in Proceedings of the 41st International Conference on Machine Learning, vol. 235 of Proceedings of Machine Learning Research, 2024, pp. 39087–39101, https://proceedings.mlr.press/v235/pan24a.html. [22] Y. Pan and E. Bareinboim, Counterfactual image editing with disentangled causal latent space, in Advances in Neural Information Processing Systems, vol. 38, 2025, https://proceedings.neurips.cc/ paper files/paper/2025/hash/54e1419b1cbca8ada96a87c96567e954-Abstract-Conference.html.

COMMON-WITNESS IMAGE AUDITING

15

[23] S. T. Rachev and L. Rüschendorf, Mass Transportation Problems, Volume I: Theory, Springer, New York, 1998, https://doi.org/10.1007/b98893. [24] C. P. Sison and J. Glaz, Simultaneous confidence intervals and sample size determination for multinomial proportions, Journal of the American Statistical Association, 90 (1995), pp. 366–369, https://doi.org/ 10.1080/01621459.1995.10476521. [25] V. Strassen, The existence of probability measures with given marginals, Annals of Mathematical Statistics, 36 (1965), pp. 423–439, https://doi.org/10.1214/aoms/1177700153. [26] J. Tian and J. Pearl, Probabilities of causation: Bounds and identification, Annals of Mathematics and Artificial Intelligence, 28 (2000), pp. 287–313, https://doi.org/10.1023/A:1018912507879. [27] J. Zhang, J. Tian, and E. Bareinboim, Partial counterfactual identification from observational and experimental data, in Proceedings of the 39th International Conference on Machine Learning, vol. 162 of Proceedings of Machine Learning Research, 2022, pp. 26548–26558, https://proceedings.mlr.press/ v162/zhang22ab.html.

Related documents

• UNMATCH: Selective Unbalanced Token-Patch Matching for Forensic Image-Claim Verification#1115722
• MIC: Explaining Image-Claim Inconsistencies in AI-Generated Multimodal Misinformation#1118153
• Identity-Aware Vision-Language Model for Explainable Face Forgery Detection#793423
• Identity-Aware Vision-Language Model for Explainable Face Forgery Detection#789419
• Blood Never Lies: The PopPK-Based Lie Detector#311852