Certifying Interventional Agreement Among Observationally Equivalent Causal Models

• More data from the same observational regime cannot resolve ambiguities about configurations that are never observed.Models may agree on held-out observations yet rely on different mechanisms and make different interventional predictions.Source: §1 · p. 1
• ISS queries admissible interventions that separate surviving perspectives, eliminates those contradicted by the answers, and stops when none within radius R separates a surviving pair.The stopping condition certifies agreement with the true system within that radius if the truth was in the initial candidate set.Source: §1 · p. 2, Figure 1 · p. 2
• The paper extends certification to continuous variables and applies it to MNIST classifiers, using an average of 13.6 image edits per image.The Boolean, zero-tolerance version needs at most 6 edits to certify radius 2 in the stated setting.Source: §1 · p. 2

• Model-discrimination design and active causal learning select experiments or interventions to distinguish explanations or resolve causal-structure uncertainty [Box & Hill, 1967; Chaloner & Verdinelli, 1995; Eberhardt & Scheines, 2007; Hauser & B¨uhlmann, 2014; Squires et al., 2020].ISS instead seeks a cost-bounded certificate of interventional equivalence for a version space of fully specified perspectives at a fixed context.Source: §2 · p. 2
• ISS makes disagreement-based learning causal and cost-sensitive: queries are interventions, and exhaustion of separating queries within a radius yields a certificate.Unlike recourse, the cost measures how difficult it is to expose disagreement between hypotheses.Source: §2 · p. 3
• Unlike causal abstraction evaluation, counterfactual inference, and identification theory, ISS actively chooses interventions among multiple candidate models to determine the cost needed for indistinguishability [Beckers & Halpern, 2019; Geiger et al., 2021; 2025; Balke & Pearl, 1994; Oberst & Sontag, 2019; Pearl, 1995; Shpitser & Pearl, 2008].Candidate abstractions and alignments form its hypothesis class.Source: §2 · p. 3

• A causal perspective is an SCM and context pair; perspectives are history-equivalent when they yield the same observed state.The version space comprises perspectives consistent with the observed state and observational data.Source: §3 · p. 3
• A query intervenes on selected variables and observes a target; its cost measures departure from the observed world, and radius r limits admissible queries to cost at most r.The separation cost of two perspectives is the minimum cost of a query on which their answers differ.Source: §3 · p. 3
• Interventional risk is the probability that two perspectives disagree on a uniformly drawn admissible query, and zero risk is equivalent to r-local equivalence.The paper characterizes risk as a normalized Hamming distance and separation cost as the margin between perspectives.Source: §3 · pp. 3–4
• Only completions of permanently unobserved mechanism cells remain indistinguishable on held-out observational data.Under the stated zero-noise observational regime, the zero-training-error version space is a product over unobserved cells.Source: §3 · p. 4
• Theorem 1 lower-bounds every observational learner’s expected interventional risk by half the maximum pairwise risk among observationally compatible hypotheses.The bound remains positive when permanently unobserved cells are separated by an admissible query, and does not vanish as the observational sample grows.Source: §3 · p. 4

• The minimum-cost rule pays the current version-space separation cost at each step, which is non-decreasing as candidates are eliminated.The halting rule, rather than the query-selection heuristic, determines whether a valid certificate is issued.Source: §4 · pp. 4–5
• With the truth in the initial version space, ISS strictly shrinks the candidates after each separating query and halts with every survivor agreeing with the truth within radius R.The stopping condition depends only on the surviving set, so the certificate is verifiable without knowing the truth.Source: §4 · p. 4
• The minimum-cost rule’s total cost is at most (|V0|−1)R, while any correct learner must refute the hardest relevant candidate and needs at least ⌈log2 C⌉ interventions in the stated binary-target worst case.A non-adaptive greedy query set costs at most (1 + ln …)OPT; the supplied theorem passage truncates the logarithm’s argument.Source: §4 · p. 5
• Finding a separating query of cost at most r is NP-complete even for Boolean SCMs with in-degree 2, unit costs, and one target.Bounded intervention size makes enumeration tractable, though finding the cheapest separating intervention can remain hard.Source: §4 · p. 5
• Exact acquisition searches the full implicit version space using feasibility checks over binary constraints, rather than treating a sample of candidates as a certificate.The acquisition rule returns a minimum-cost separating query; samples are used only for acquisition heuristics, with risk estimates based on fresh independent samples.Source: §4 · pp. 5–6
• For noisy mechanisms, a calibrated likelihood margin yields a candidate set containing the truth with probability at least 1−δ, and ISS then certifies zero risk within its radius with probability at least 1−δ.The candidate set allows bounded flips of fitted cells as well as free unobserved cells.Source: §4 · p. 6
• For continuous variables, if 2η < ε and the query family is finite, ISS halts within |Q_R| interventions and every survivor is within ε of the truth on each admissible query.When answers are linear in hypothesis parameters up to sign decisions, mixed-integer linear programs decide ε-separation exactly over the finite union of polytopes.Source: §4 · p. 6
• When the truth is outside the maintained class, ISS may still halt but its certificate is void; separate random-query validation can refute the class but certifies nothing.The certificate is conditional on realizability, including when the candidate abstractions fail to capture a network faithfully.Source: §4 · p. 6

5 EXOGENOUS GROUNDING: SUPERVISION AT ZERO INTERVENTION COST

• For any structure and observed state, exactly one exogenous context makes the perspective history-equivalent, so history-equivalence alone does not constrain structure.This is the abductive freedom described for the stated mechanism form.Source: §5 · p. 6
• A verified audit that a component operated nominally defines a grounded version space and eliminates its complement at zero intervention cost.The passage contrasts evidence about contexts with interventions that constrain mechanisms off observed configurations.Source: §5 · pp. 6–7
• Data, evidence, and interventions constrain different things: visited mechanisms, contexts, and unobserved mechanism behavior, respectively.Structural disagreement can remain invisible to evidence, while context disagreement is visible only where interventions unmask it.Source: §5 · p. 7

6 EXPERIMENTS: CONTINUOUS CAUSAL ABSTRACTION ON MNIST

• The task uses three digits—a pointer and two possible selections—with size and hue represented in a causal abstraction whose unknown percept function may use shape, hue, or both.The pointer selects the left or right digit according to its size; the selected digit's size determines the label.Source: §6 · p. 7
• The observational log constrains percept curves only at observed hues, leaving an infinite version space; visual interventions recolor or swap digits, while white-box interventions can set the pointer percept.The network's output probability is the intervention answer.Source: §6 · p. 8
• Plain CNNs reached zero held-out error yet disagreed with shape-world labels on 26% of single-digit edits; with α = 0.9, that error fell to 3% as N increased.The large and small digit hues track size in the observed images, making hue- and shape-based rules observationally indistinguishable there.Source: §6 · pp. 7–8
• ISS repeatedly selects the cheapest intervention where surviving hypotheses disagree by more than ε, retains hypotheses predicting the observed answer, and stops when none separates within R.For ε = 0.05, mixed-integer linear programs compute separation exactly over the continuous version space; certificates are checked against every admissible intervention.Source: §6 · pp. 8–9
• 1,728 in-class runs produced certificates correct on every admissible intervention; at R = 0.5, ISS used 13.6 interventions and total cost 4.0.The truth was in V0 for 96% of observed images; random separating queries cost 5.3 and random probing cost 33.9.Source: §6 · p. 9
• With interchange interventions on bypass networks, 97% of white-box runs ended in void certificates, and 20 random validation interventions refuted 69% of them.The candidate abstractions agreed about the pointer percept even though the network's router used a separate pointer encoder.Source: §6 · pp. 8–9

7 DISCUSSION AND CONCLUSION

• ISS certifies agreement within radius R when no admissible intervention in that budget separates survivors, provided the truth lies in the version space; under misspecification, separate validation is needed.The method's exact separation has scope limits, including a finite intervention family, restricted answer forms, and exponential worst-case cost.Source: §7 · p. 9

A.1 PROOF OF PROPOSITION 1

• For history-equivalent perspectives, positive separation risk at radius r is equivalent to having minimum separation cost at most r; history-equivalence excludes cost-zero separating queries.Without that condition, cost-zero separation can coexist with no separating query in the positive-cost query family.Source: §A.1 · p. 16

A.2 PROOF OF PROPOSITION 2

• With zero noise, the observational version space fixes mechanisms on observed cells and leaves each unobserved cell unconstrained; with positive noise, each observed cell's likelihood is maximized by its majority value.Cells with no observations contribute nothing to the likelihood.Source: §A.2 · pp. 16–17

A.3 PROOF OF THEOREM 1

• An observational learner receives the same data under consistent perspectives, so its worst-case expected interventional risk is at least half their disagreement; the bound can persist for cells the regime never reaches.Any separating query gives a positive normalized disagreement, and permanently unobserved cells can keep such a pair in the version space for every sample size.Source: §A.3 · p. 17

A.4 PROOF OF THEOREM 2

• When the truth is in V0, each update retains exactly the perspectives matching its answer, so the true perspective is never removed.The refutation branch is reached only if the truth was not in V0.Source: §A.4 · p. 17
• Each chosen query separates two survivors, so at least one is eliminated and the loop runs at most |V0| − 1 times.Source: §A.4 · p. 17
• If ISS halts because no pair separates within R, every survivor agrees with the true perspective on all queries within R; budget halting yields the same guarantee at a smaller radius.The stopping calculation uses candidate answers to admissible queries and does not require knowing the truth.Source: §A.4 · p. 17

A.5 PROOF OF THEOREM 3

• Theorem 3 bounds the truth-specific cost by the hardest relevant pair and makes the separation threshold non-decreasing as hypotheses are eliminated.A weighted set-cover strategy also certifies the radius with cost at most (1 + ln M) times the optimum, while adaptivity may spend less.Source: §A.5 · pp. 17–18
• For binary targets, answer strings across R-local classes form a prefix-free code, giving a worst-case query count of at least ⌈log2 C⌉ and uniform-class expected length at least log2 C.The proof also gives a run-by-run cost bound for randomized learners that halt with correct certificates.Source: §A.5 · p. 18

A.6 PROOF OF COROLLARY 1

• The corollary’s stated cell-agreement condition ensures a model survives every query, but it is not necessary because reachable differences outside the target’s ancestry can remain unobserved.The proof also describes the terminal class through Theorem 2(c).Source: §A.6 · p. 18

A.7 PROOF OF PROPOSITION 7

• Adding evidence shrinks the version space, raises the minimum separating cost, and can make the radius stopping condition hold sooner.The proof also notes the stated Theorem 3 bound increases with version-space size.Source: §A.7 · p. 18

A.8 PROOF OF PROPOSITION 3

• The exact stopping test can represent query answers with DNF cubes and use 0-1 feasibility checks; adaptive query selection requires a fresh uniform risk sample.Filtering a uniform sample works for fixed queries but can bias it when queries are chosen from that sample.Source: §A.8 · pp. 18–19

A.9 PROOF OF PROPOSITION 4

• With ε-separation and 2η < ε, the truth survives elimination, stopping leaves no ε-separating query, and each query in the finite family runs at most once.The argument extends to risk measured by the expected supremum-norm answer difference.Source: §A.9 · p. 19

A.10 PROOF OF THEOREM 4

• Per-variable budgets place the truth in the constrained version space with probability at least 1 − δ, after which Theorem 2’s truth-preserving certificate guarantee applies.Roots need no budget; they equal their exogenous variables and have no fitted cells.Source: §A.10 · pp. 19–20

A.11 PROOF OF PROPOSITION 6

• Separation cost is symmetric, monotone in the query family and costs, bounded below for history-equivalent perspectives, and obeys an ultrametric inequality that makes its radius classes nested.Zero-cost queries cannot distinguish history-equivalent perspectives.Source: §A.11 · p. 20

A.12 PROOF OF LEMMA 1

• When induced mechanisms agree, perspectives answer every intervention identically; a differing mechanism can be exposed by setting its parents and targeting that variable.The proof bounds the cost using the differing mechanism’s parent configurations.Source: §A.13 · p. 20

A.13 PROOF OF THEOREM 5

• The separation cost is infinite when induced mechanisms agree, while a difference in a mechanism cell yields a finite separating intervention under the full query family.The proof also gives a procedure comparing parent configurations to find a differing cell and minimizing intervention.Source: §A.13 · p. 20

A.14 PROOF OF THEOREM 6

• Finding minimum separation cost is NP-hard: the proof reduces SAT to root-only interventions and vertex cover to the setting where gates are manipulable.The reductions use different constructions because intervened gates can shortcut the circuit.Source: §A.14 · p. 21

A.15 PROOF OF PROPOSITION 5

• At an observed state, every structure can abduce a context that makes that state satisfy its equations, yielding history-equivalent perspectives.The proof uses uniqueness of solutions under the abduced context.Source: §A.15 · p. 21

A.16 PROOF OF THEOREM 7

• With a shared context, differences in a mechanism at other values of its noise variable affect neither the observational state nor any query answer.The proof ties possible divergence to mechanisms differing at the shared context.Source: §A.16 · p. 21

A.17 PROOF OF THEOREM 8

• In the constructed example, the minimum separating cost is exactly r, but a query family with domain size at most r − 1 cannot separate the perspectives.A separating query must intervene on all r roots and target the output.Source: §A.17 · pp. 21–22

B STRUCTURAL RESULTS USED IN THE MAIN TEXT

• Separation cost is symmetric and monotone in query families and costs, and its ultrametric inequality makes budget-indexed equivalence classes refine as r grows.When two perspectives have identical induced mechanisms, no query family or cost function separates them.Source: B STRUCTURAL RESULTS USED IN THE MAIN… · p. 22
• For Boolean SCMs, deciding whether separation costs at most r is NP-complete, while finite separation is polynomial for fully manipulable variables and bounded-size query families.The middle bound can be loose when an upstream intervention steers several differing mechanisms more cheaply.Source: B STRUCTURAL RESULTS USED IN THE MAIN… · p. 22
• For every r ≥ 1, evidence can make rival elimination cost zero even when full-family intervention separation costs r and interventions of size at most r − 1 cannot separate the pair.The construction uses history-equivalent perspectives with identical structural functions; a verified differing noise coordinate eliminates one at zero cost.Source: B STRUCTURAL RESULTS USED IN THE MAIN… · p. 23

C.1 NETWORKS

• The continuous MNIST networks use digit hue and size inputs, percept units, and output routing, with trained, planted, and bypass variants.In bypass networks, the router reads a second pointer-image encoder rather than the percept used by the candidate abstractions.Source: §C.1 · p. 23

C.2 THE AUDITOR

• The auditor fits a continuous version space from logged percepts, then uses mixed-integer linear programs to compute each query’s output range over all candidates.Its admissible queries vary hues, swap a fixed held-out digit, and, in the white-box family, set the pointer percept; answers and agreement are evaluated with specified tolerances.Source: §C.2 · p. 24
• The continuous version space is built from logged-percept quantile bounds, and images are used only when their own percepts fall within those bounds.The bounds are estimated from other digits, so the true percept can fall outside the candidate class.Source: §C.2 · p. 24

C.3 RESULTS

• 0 errors occurred in 1,728 runs whenever the truth lay in the version space.A certificate is checked against every admissible intervention within its radius.Source: §C.3 · p. 24
• On one CPU core, a minimum-cost run takes 0.3 seconds on average and at most 7 seconds, while random probing averages 5.9 seconds and reaches 263 seconds.The full continuous study, including training, takes under an hour on one RTX 4080 Super GPU and 15 CPU cores.Source: §C.3 · p. 24
• 26.6% of single-slot edits are cases where the shape and color worlds disagree.Table 3 reports plain CNNs’ held-out observed-image error and shape-world error on every single-slot edit of cost at most 1.Source: Table 3 · p. 25
• Both certificates shown in Figure 4 hold on all 21 interventions of cost at most 2, checked on the networks.The figure shows two networks whose logs fit the same cells and the interventions selected during auditing.Source: Figure 4 · p. 26

D THE BOOLEAN MNIST STUDY

• In the Boolean MNIST study, the version space is finite and every certificate is exact, with no tolerance.The paper states that every claim of Theorems 2 and 3 can be checked on every run.Source: D THE BOOLEAN MNIST STUDY · p. 26

D.1 SETTING AND RESULTS

• The task uses three digits: pointer size selects the left or right digit, and the label indicates whether the selected digit is large.The abstraction gives each digit size and ink-color inputs, a percept bit, and an output computed from the three percepts; audited networks align these percepts with binary units.Source: §D.1 · p. 26

D.2 TASK, DATA AND NETWORKS

• The audit trains 50 networks, logs 5,000 images per network where ink matches size, and leaves six off-diagonal percept cells unobserved, producing 64 candidate abstractions.The network architecture uses a separate encoder and binary percept unit per digit, with an MLP head; bypass networks add a second pointer encoder that the output uses instead of the pointer bit.Source: §D.1 · p. 27, §D.2 · p. 29, §D.3 · p. 30

D.1 SETTING AND RESULTS

• 50% of single-variable interventions from plain CNNs trained on up to 60,000 observed images disagree with shape-world labels despite zero held-out error; at α = 0.9, the error falls to 3%.When ink always matches size, shape and color worlds label observed images identically, and observation alone cannot resolve their different intervention predictions.Source: §D.1 · p. 27, Figure 5 · p. 28
• When the network abstraction is among the candidates, every certificate agrees with the network on every intervention within its radius across 53,496 runs.The abstraction is in the class at every observed image except for 8% of those from α = 0.99 networks.Source: §D.1 · p. 27
• At R = 2, ISS uses at most 6 visual interventions, while the average variables changed are 8.6 for ISS, 7.0 for a learner told the truth, 15.1 for greedy cover, and 25.9 for random probing.The six-intervention maximum is ⌈log2 C⌉, the fewest any learner can guarantee; the averages compare visual-intervention acquisition rules.Source: §D.1 · pp. 27–28, Figure 5 · p. 28

D.3 THE AUDIT

• The audit tests certificates against every admissible query within the radius, while validation samples up to 20 unexecuted queries and refutes the class at the first contradiction.ISS selects among separating queries; acquisition rules differ in how they choose a query, and all share the elimination and stopping test.Source: §D.3 · p. 30

D.4 ADDITIONAL RESULTS

• Certificates recovered planted tables at 98% of observed images and 99.5% of slots, but followed the network when it departed from its planted table.ISS certifies the network, not its training target.Source: §D.4 · p. 30
• No Theorem 2 or 3 claim failed when the truth lay in the class; adaptive minimum-cost runs beat non-adaptive greedy cover in 4,887 of 15,000 instances.Greedy cover cost less in 15 instances.Source: §D.4 · p. 30, Table 8 · p. 32
• At radius 1, about half of white-box bypass certificates remain correct; both validation interventions in the illustrated run contradict every survivor.The bypass can make an unchanged answer appear to describe the left digit, yielding a wrong certified table.Source: §D.4 · p. 31, Figure 6 · p. 31, Table 10 · p. 33
• The four-way-pointer audit found no certificate failures in 12,000 runs when the truth was in the class, while random probing cost over ten times more than ISS at R = 3.The version space had 4,096 members, and separating queries could require up to three edits.Source: §D.4 · p. 31, Table 11 · p. 33
• ISS’s Boolean MNIST results are compared across query-selection rules, certification radii, and certificate correctness; the table caption does not report individual cell values.The audit takes about 5 seconds per network for the three-digit task and about 80 seconds for the four-way pointer.Source: §D.4 · p. 31, Table 7 · p. 32

E.1 STRUCTURAL CAUSAL MODELS, INTERVENTIONS, AND THE CAUSAL HIERARCHY

• Structural causal models provide the paper’s setting, where interventions expose differences between perspectives that can agree on an observed history.The paper frames its individual-level, fixed-context underdetermination in relation to the Pearl Causal Hierarchy.Source: §E.1 · p. 34

E.2 OBSERVATIONAL AND INTERVENTIONAL EQUIVALENCE

• Unlike population-level Markov equivalence, the paper’s equivalence is individual-level, cost-graded, and relative to an admissible intervention family.Distributional equivalence is neither necessary nor sufficient for history-equivalence.Source: §E.2 · p. 34

E.3 CONFOUNDING, IDENTIFICATION, AND EXOGENOUS GROUNDING

• Grounding verified shared exogenous facts does not establish exchangeability or measured common causes; the fixed-context theory makes no population-level identification claim.The benchmark does not evaluate robustness to latent confounding.Source: §E.3 · p. 35

E.5 AMORTIZED AND COST-CONSTRAINED ACTIVE INTERVENTIONAL DESIGN

• ISS addresses unknown mechanisms on unobserved parent configurations and exogenous context, whereas structure-learning methods target causal structure; the two targets are sequential.The paper lists given parent sets as a limitation.Source: §E.5 · p. 36
• ISS defines intervention cost as distance from the observed state, so radius R is both the intervention budget and the scope of the guarantee.The compared methods use intervention counts, oracle costs, or budgets that do not index the guarantee in this way.Source: §E.5 · p. 36
• ISS stops when no query separates the survivors, an exact test over the whole version space that can be checked without knowing the truth.A vanishing maximum expected information gain under an approximate posterior does not establish that the version space is exhausted.Source: §E.5 · p. 36
• Separation cost is worst-case and budget-indexed, unlike expected-information criteria that average over a prior; in the Boolean MNIST study, information-per-cost nearly matched minimum-cost rule cost.The criteria differ in what they license at the end of a run.Source: §E.5 · p. 36

E.6 UNDERSPECIFICATION, MULTIPLICITY, AND DISAGREEMENT BETWEEN PREDICTORS

• ISS formalizes a minimal stress test for observationally agreeing predictors, whose held-out performance can coexist with divergent behavior under intervention.The paper relates this problem to underspecification and predictor multiplicity.Source: §E.6 · p. 36

E.7 COUNTERFACTUAL EXPLANATIONS, RECOURSE, AND MINIMAL PERTURBATIONS

• Unlike recourse, which seeks a minimum-cost intervention flipping one model’s output, separation seeks the cheapest intervention making two models disagree.Its interventions use do-semantics rather than pixel perturbations.Source: §E.7 · p. 37

E.8 DIFFERENTIAL TESTING, DISTINGUISHING SEQUENCES, AND QUERY LEARNING

• Separation cost is a cheapest counterexample to interventional equivalence, measured by departure from an observed state rather than input norm or sequence length.Source: §E.8 · p. 37

E.9 CAUSAL ABSTRACTION AND INTERVENTIONAL INTERPRETABILITY

• Interventional interpretability methods measure network-hypothesis agreement across interventions; ISS instead seeks the minimum-cost environment intervention separating two abstracted models.Source: §E.9 · p. 37