Introduction
What actually caused a specific outcome, such as a patient’s death after medication, an accident, or a software failure? Actual causation [16 ] answers this question for singular, context-dependent cases, grounding legal responsibility [25 ] , moral blame [11 ] , and algorithmic accountability [9 ] . Downstream tasks that aggregate over the full cause set, notably responsibility and blame scores [9 ] and the grading of causal harm [6 ] , are blocked without an efficient enumeration procedure. The dominant framework [17 , 16 ] formalises actual causation in acyclic structural causal models (SCMs) [27 ] via three conditions (AC1)–(AC3) on a candidate variable assignment, requiring its actual co-occurrence with the effect, a contingency set of variables held at actual values exposing counterfactual dependence, and subset-minimality (formal definitions in Sec. 3). We adopt the modified HP definition [15 , 16 ] , one of several proposals in the literature, for its conceptual clarity and favourable complexity profile: verifying a single candidate is D 1 P D_1^P D 1 P -complete [1 , 15 ] , vs. Σ 2 P \Sigma_2^P Σ 2 P -complete in general under the original [12 ] . The modified definition is also the natural fit for our construction: holding contingencies at their actual values is exactly the membership constraint of Corollary 2 , so condition AC2 collapses to a single query against a precomputed target set, whereas the original definition’s additional universal clause over contingency subsets admits no such collapse in general.
Figure 1. (a) The DAG of the Billy and Suzy example. The actual world is ( S T , B T , ¬ B H , S H , B S ) (ST, BT, \neg BH, SH, BS) ( S T , B T , ¬ B H , S H , B S ) with environment ( U S T , U B T ) (U_{ST}, U_{BT}) ( U S T , U B T ) (True variables are double-bordered). (b) The witness map (Definition 6) for the counterfactual target ¬ B S \neg BS ¬ B S with double-bordered intervention sets for global targets (Definition 3) allowing the observed environment. As no singleton passes and none of these sets contains another, all four are but-for causes. The nodes that allow for non-empty contingency (¬ B H \neg BH ¬ B H ) are highlighted in red. Thus we have two actual causes S T ( = 1 ) ST(=1) S T ( = 1 ) and S H ( = 1 ) SH(=1) S H ( = 1 ) . See Example 3 for details. (Best viewed in color.)
Existing exact algorithms suffer from two limitations: Ibrahim and Pretschner [19 ] translate HP conditions into ILP clauses for a single smallest cause, restricted to Boolean SCMs and unable to enumerate the full cause set; Reyd et al. [29 ] extend coverage to non-Boolean and black-box SCMs via forward simulation with sampled alternative values, but offer no soundness or completeness guarantee. We present the first constructive, sound-and-complete algorithm for enumerating all actual causes of an event in an acyclic SCM. Rather than iterating over alternative values forward, we propagate the complement of the target event backward through the structural equations, yielding the witness targets : for each candidate intervention set, the exact set of joint variable configurations compatible with that complement. This converts the existential search in AC2 into a single set-membership query, eliminating the dependence on alternative-value cardinality from the per-candidate verification cost. A finite witness map over structurally admissible ancestor subsets then enumerates all candidate intervention sets; its worst-case cost remains exponential (§ 4.3 ), which pruning substantially reduces in practice. Figure 1 introduces the running rock-throwing preemption example (Suzy- and Billy throw rocks at a bottle with perfect accuracy (S T = 1 , B T = 1 ST=1,BT=1 S T = 1 , B T = 1 ): Suzy Hits (S H = 1 SH=1 S H = 1 ), but Billy does not hit (B H = 0 BH=0 B H = 0 ) due to Suzy hitting first. The bottle shatters (B S = 1 BS=1 B S = 1 ) due to either of them hitting.) used throughout, with the formal machinery developed in Section 4.
Contributions. We introduce three components that together yield a sound and complete enumeration procedure for actual causes. First, witness targets (§ 4.1 ) provide an exact backward-propagation criterion for counterfactual satisfaction, converting AC2 into a set-membership query (Definitions 1–3, Theorem 1 , Corollary 2 ). Second, the witness map (§ 4.2 ) builds on the ancestor intervention grammar and ancestral map to enumerate all structurally admissible candidate intervention sets (Definitions 4–6, Propositions 3–4 ). Third, the Tracing Actual Causes (TrAC) algorithm (§ 4.3 , Algorithm 1) combines both with soundness and completeness guarantees (Theorem 7) and an explicit complexity analysis (Appendix § 11 ).
Related Work
HP causation: extensions and algorithms. Foundational work formulates responsibility and blame [9 ] (whose computation requires precisely the enumeration we provide), recasts HP via causal sufficiency [2 ] , develops actual causation in CP-logic with graded judgements [4 ] , and extends to probabilistic [13 ] and nondeterministic [3 ] settings; downstream aggregations such as causal harm [5 ] all presuppose an enumeration step. Context-specific independence (CSI) [7 , 33 ] provides an algebraic lens on overdetermination and preemption that the outer approximation of Appendix § 10 realises in marginal form [28 ] ; we discuss this connection further in Appendix § 14 .
Explainability and attribution. Instance-level XAI sits close to but is distinct from actual causation. Shapley-value attributions, both associational [24 , 21 ] and DAG-aware [18 ] , quantify marginal contributions rather than identify singular causes. Counterfactual explanations [30 , 26 ] and causally-augmented recourse [22 ] implement but-for reasoning (AC2 without contingency), missing overdetermination and preemption. Population relative unit-level SCM explanations are discussed in [32 ] . Galhotra et al. [14 ] apply probabilistic contrastive counterfactuals in databases; Chockler and Halpern [10 ] bridge HP causation to image-level XAI under an assumed SCM, and causal root-cause analysis [23 , 8 , 20 , 31 ] addresses a related root-cause diagnosis problem under different assumptions and outside the HP framework; these methods neither target nor guarantee HP actual causes. We take the SCM as given and address the prerequisite enumeration step; SCM extraction is orthogonal.
Adopted and new components. We adopt the modified HP definition (AC1)–(AC3) [15 , 16 ] with the responsibility measure used in the examples [9 , 16 ] , the complexity results for verifying a single candidate cause [1 , 12 ] , which motivate our choice of definition, and the baselines with their solution strategies [19 , 29 ] , used unchanged for comparison; context-specific independence [7 , 33 , 28 ] serves only to interpret the pruning (Appendix § 14 ). New are the witness targets (Definitions 1–3) with their exactness (Theorem 1) and the reduction of the AC2 test to a single set-membership query (Corollary 2); the ancestor intervention grammar, ancestral map and witness map (Definitions 4–6) with the closed-form child characterisation (Proposition 3) and the reachability criterion (Proposition 4); TrAC with the first soundness-and-completeness guarantee for enumerating all actual causes (Theorem 7), where prior exact methods return a single smallest cause [19 ] or lack guarantees [29 ] ; and the three-parameterisation complexity analysis (Appendix § 11 ), the constraint-based outer approximation (Appendix § 10 ) and the formally justified pruning strategies (Appendix § 12 ).
Preliminaries
Structural causal models (SCM) are structures M = ⟨ U , V , F , P U ⟩ \mathcal{M} = \langle\mathbf{U}, \mathbf{V}, \mathcal{F}, \mathbb{P}_{\mathbf{U}} \rangle M = ⟨ U , V , F , P U ⟩ with a set of exogenous variables U = { X 1 , … , X o } \mathbf{U} = \{X_1, \ldots, X_o\} U = { X 1 , … , X o } and a set of endogenous variables V = { X o + 1 , … , X o + p } \mathbf{V} = \{X_{o+1}, \ldots, X_{o+p}\} V = { X o + 1 , … , X o + p } with full configurations O = U ∪ V \mathbf{O} = \mathbf{U} \cup\mathbf{V} O = U ∪ V and values o ⃗ ∈ O ⃗ = U ⃗ × V ⃗ = ∏ i = 1 o + p X i \vec{o} \in\vec{\mathcal{O}} = \vec{\mathcal{U}} \times\vec{\mathcal{V}} = \prod_{i=1}^{o+p} \mathcal{X}_i o ∈ O = U × V = ∏ i = 1 o + p X i , a set of structural equations F = { X = F X : X ∈ V } \mathcal{F} = \{X = F_X : X \in\mathbf{V}\} F = { X = F X : X ∈ V } with functions F X : X pa ( X ) → X X F_X : \mathcal{X}_{\operatorname{pa}(X)} \to\mathcal{X}_X F X : X pa ( X ) → X X and a distribution P U \mathbb{P}_{\mathbf{U}} P U of the exogenous variables. Assignments u ⃗ : U → ⋃ X i ∈ U X i \vec{u} : \mathbf{U} \to\bigcup_{X_i \in\mathbf{U}} \mathcal{X}_i u : U → ⋃ X i ∈ U X i of (all) exogenous variables are called environments of M \mathcal{M} M and assignments w ⃗ : V → ⋃ X i ∈ V X i \vec{w} : \mathbf{V} \to\bigcup_{X_i \in\mathbf{V}} \mathcal{X}_i w : V → ⋃ X i ∈ V X i of (all) endogenous variables are called worlds of M \mathcal{M} M . A pair ( M , u ⃗ ) (\mathcal{M}, \vec{u}) ( M , u ) is called a setting and the actual world w ⃗ u ⃗ \vec{w}_{\vec{u}} w u of a specific setting ( M , u ⃗ ) (\mathcal{M}, \vec{u}) ( M , u ) is induced by the evaluation of structural equations in F \mathcal{F} F . For an assignment X ⃗ = x ⃗ \vec{X} = \vec{x} X = x with X ⃗ ⊆ V \vec{X} \subseteq\mathbf{V} X ⊆ V , the intervened SCM M d o ( X ⃗ = x ⃗ ) \mathcal{M}_{do(\vec{X}=\vec{x})} M d o ( X = x ) is obtained from M \mathcal{M} M by replacing every structural equation F X i F_{X_i} F X i with the constant x i x_i x i (for X i ∈ X ⃗ X_i \in\vec{X} X i ∈ X ); its actual world under u ⃗ \vec{u} u is denoted w ⃗ u ⃗ ∗ \vec{w}^{*}_{\vec{u}} w u ∗ and called counterfactual when w ⃗ u ⃗ ∗ ≠ w ⃗ u ⃗ \vec{w}^{*}_{\vec{u}} \ne\vec{w}_{\vec{u}} w u ∗ = w u . The corresponding modal operator satisfies M , u ⃗ ⊨ [ X ⃗ = x ⃗ ] φ ⟺ M d o ( X ⃗ = x ⃗ ) , u ⃗ ⊨ φ \mathcal{M}, \vec{u} \models[\vec{X} = \vec{x}]\varphi\Longleftrightarrow\mathcal{M}_{do(\vec{X}=\vec{x})}, \vec{u} \models\varphi M , u ⊨ [ X = x ] φ ⟺ M d o ( X = x ) , u ⊨ φ .
The actual causes easiest to define are so-called but-for causes, which are necessary conditions of an event. In a given setting ( M , u ⃗ ) (\mathcal{M}, \vec{u}) ( M , u ) we say that the event ( X ⃗ = x ⃗ ) (\vec{X} = \vec{x}) ( X = x ) is a but-for cause of the event φ \varphi φ if and only if M , u ⃗ ⊨ ( X ⃗ = x ⃗ ) ∧ φ \mathcal{M}, \vec{u} \models(\vec{X} = \vec{x}) \land\varphi M , u ⊨ ( X = x ) ∧ φ (AC1), there exists x ⃗ ′ ∈ X \vec{x}' \in\mathcal{X} x ′ ∈ X with M , u ⃗ ⊨ [ X ⃗ = x ⃗ ′ ] ¬ φ \mathcal{M}, \vec{u} \models[\vec{X} = \vec{x}']\neg\varphi M , u ⊨ [ X = x ′ ] ¬ φ (AC2*), and X ⃗ = x ⃗ \vec{X} = \vec{x} X = x is a smallest conjunction of atomic events satisfying the previous conditions (i.e., there is no subevent ( X ⃗ = x ⃗ ′ ) ⊂ ( X ⃗ = x ⃗ ) (\vec{X} = \vec{x}') \subset(\vec{X} = \vec{x}) ( X = x ′ ) ⊂ ( X = x ) satisfying both AC1 and AC2*) (AC3). Note here that a variable alone is not a cause; only the variable taking a specific value can be a cause. The atomic components ( X i = x i ) (X_i = x_i) ( X i = x i ) for X i ∈ X ⃗ X_i \in\vec{X} X i ∈ X are referred to as parts of the cause ( X ⃗ = x ⃗ ) (\vec{X} = \vec{x}) ( X = x ) . To also capture causes whose but-for dependence is masked by a backup process, the modified HP definition [15 ] relaxes the second condition as follows: if there exist x ⃗ ′ ∈ X \vec{x}' \in\mathcal{X} x ′ ∈ X and Z ⃗ ⊆ V ∖ X ⃗ \vec{Z} \subseteq\mathbf{V} \setminus\vec{X} Z ⊆ V ∖ X such that M , u ⃗ ⊨ [ Z ⃗ = w ⃗ u ⃗ ( Z ⃗ ) , X ⃗ = x ⃗ ′ ] ¬ φ \mathcal{M}, \vec{u} \models[\vec{Z} = \vec{w}_{\vec{u}}(\vec{Z}), \vec{X} = \vec{x}']\neg\varphi M , u ⊨ [ Z = w u ( Z ) , X = x ′ ] ¬ φ (AC2), and X ⃗ = x ⃗ \vec{X} = \vec{x} X = x is a smallest conjunction of atomic events satisfying AC1 and that condition, then X ⃗ = x ⃗ \vec{X} = \vec{x} X = x is called an actual cause of the event φ \varphi φ . Preemption is the canonical example (Figure 1, Appendix § 9 .§ 2 ): Suzy’s throw is not a but-for cause of the shattered bottle, but it is an actual cause, since holding Billy’s miss at its actual value exposes the dependence.
As the but-for causes and actual causes are defined via the existence of counterfactual worlds where the target event φ \varphi φ does not hold, we call such a world w ⃗ u ⃗ ∗ \vec{w}^{*}_{\vec{u}} w u ∗ a counterfactual witness for the actual cause or but-for cause X ⃗ = x ⃗ \vec{X}=\vec{x} X = x of the event φ \varphi φ in the setting ( M , u ⃗ ) (M,\vec{u}) ( M , u ) . For a given setting ( M , u ⃗ ) (M,\vec{u}) ( M , u ) , we can identify such a witness for an actual cause X ⃗ = w ⃗ u ⃗ ( X ⃗ ) \vec{X}=\vec{w}_{\vec{u}}(\vec{X}) X = w u ( X ) of an event φ \varphi φ by a tuple ( Z ⃗ , X ⃗ , x ⃗ ′ , φ ) (\vec{Z},\vec{X},\vec{x}^{\prime},\varphi) ( Z , X , x ′ , φ ) with Z ⃗ ⊆ V ∖ X ⃗ \vec{Z}\subseteq V\setminus\vec{X} Z ⊆ V ∖ X . We call Z ⃗ \vec{Z} Z the contingency set : it consists of variables held fixed at their actual values w ⃗ u ⃗ ( Z ⃗ ) \vec{w}_{\vec{u}}(\vec{Z}) w u ( Z ) in order to reveal the counterfactual dependence of φ \varphi φ on X ⃗ \vec{X} X . The causal claim ( X ⃗ = w ⃗ u ⃗ ( X ⃗ ) ) (\vec{X}=\vec{w}_{\vec{u}}(\vec{X})) ( X = w u ( X )) thus holds as a cause contingent on the context Z ⃗ = w ⃗ u ⃗ ( Z ⃗ ) \vec{Z}=\vec{w}_{\vec{u}}(\vec{Z}) Z = w u ( Z ) . If X ⃗ = w ⃗ u ⃗ ( X ⃗ ) \vec{X}=\vec{w}_{\vec{u}}(\vec{X}) X = w u ( X ) is (also) a but-for cause of φ \varphi φ , then Z ⃗ = ∅ \vec{Z}=\emptyset Z = ∅ , i.e., no contingency is required.
Tracing Actual Causes
We assume throughout that the SCM induces an acyclic causal graph. W.l.o.g., the target Y ∈ V Y\in V Y ∈ V is a single variable with value domain Y \mathcal{Y} Y ; if not, introduce a fresh variable whose structural equation copies the joint configuration of the target set. We write ( Y ∈ Y ∗ ) (Y\in\mathcal{Y}^{*}) ( Y ∈ Y ∗ ) with Y ∗ ⊆ Y \mathcal{Y}^{*}\subseteq\mathcal{Y} Y ∗ ⊆ Y for the target event and ( Y ∈ Y ^ ) (Y\in\widehat{\mathcal{Y}}) ( Y ∈ Y ) for the induced counterfactual target with Y ^ = Y ∖ Y ∗ \widehat{\mathcal{Y}}=\mathcal{Y}\setminus\mathcal{Y}^{*} Y = Y ∖ Y ∗ . We characterise the exact set of joint variable configurations compatible with the counterfactual target via backward propagation through the structural equations. The construction proceeds through two building blocks: parent targets and descendant targets .
Our construction separates verification from enumeration. Section 4.1 develops witness targets, computed by a single backward pass through the structural equations; they reduce the AC2 test for a fixed candidate pair ( X ⃗ , Z ⃗ ) (\vec{X},\vec{Z}) ( X , Z ) to one membership query in a precomputed set (Corollary 2), with no search over alternative values. Section 4.2 develops the ancestor intervention grammar and the witness map, a finite DAG whose nodes are the candidate intervention sets that have to be tested. Section 4.3 combines both into Algorithm 1 (TrAC) and proves it sound and complete (Theorem 7).
Witness Targets
Definition 1 (parent targets). For an endogenous variable X ∈ V X\in V X ∈ V and a set O ^ ⊆ O ⃗ \widehat{O}\subseteq\vec{\mathcal{O}} O ⊆ O , the parent targets are
O ^ M p a ( X , O ^ ) : = { o ⃗ ∈ O ^ ∣ o ⃗ p a ( X ) ∈ F X − 1 ( o ⃗ X ) } , \widehat{\mathcal{O}}^{\mathrm{pa}}_{M}(X,\widehat{O}) := \left\{\vec{o}\in\widehat{O}\mid\vec{o}_{\mathrm{pa}(X)}\in F_X^{-1}(\vec{o}_X)\right\}, O M pa ( X , O ) := { o ∈ O ∣ o pa ( X ) ∈ F X − 1 ( o X ) } ,
where o ⃗ p a ( X ) \vec{o}_{\mathrm{pa}(X)} o pa ( X ) is the projection of o ⃗ \vec{o} o onto the parent components of X X X and F X − 1 ( o ⃗ X ) ⊆ X ⃗ p a ( X ) F_X^{-1}(\vec{o}_X)\subseteq\vec{\mathcal{X}}_{\mathrm{pa}(X)} F X − 1 ( o X ) ⊆ X pa ( X ) is the preimage of o ⃗ X \vec{o}_X o X under F X F_X F X .
Note that the parent target operator is exact because a configuration o ⃗ \vec{o} o is retained if and only if its parent values are structurally consistent with producing o ⃗ X \vec{o}_X o X , hence no feasible assignment is lost and no spurious one is introduced.
The parent target operator handles a single step of backward propagation. To accumulate constraints all the way from the target Y Y Y up to any ancestor X X X , we apply it recursively across the graph.
Definition 2 (descendant targets). For a given SCM M \mathcal{M} M , target variable Y ∈ V Y\in V Y ∈ V , target values Y ^ ⊆ Y \widehat{\mathcal{Y}}\subseteq\mathcal{Y} Y ⊆ Y , variable X ∈ V X\in V X ∈ V , and intervention set S ⊆ V S\subseteq V S ⊆ V , the descendant targets O ^ M , d o ( S ˉ ) ↓ ( X , Y ^ ) \widehat{\mathcal{O}}^{\downarrow}_{\mathcal{M},do(\bar{S})}(X,\widehat{\mathcal{Y}}) O M , d o ( S ˉ ) ↓ ( X , Y ) (written O ^ ↓ ( X ) \widehat{\mathcal{O}}^{\downarrow}(X) O ↓ ( X ) when the context is fixed) are defined recursively by:
O ^ M , d o ( S ˉ ) ↓ ( X , Y ^ ) : = { { o ⃗ ∈ O ⃗ ∣ o ⃗ Y ∈ Y ^ } if X = Y , O ⃗ if ch ( X ) = ∅ , ⋂ Z ∈ ch ( X ) ∖ S ˉ O ^ M p a ( Z , O ^ M , d o ( S ˉ ) ↓ ( Z , Y ^ ) ) otherwise. (1) \widehat{\mathcal{O}}^{\downarrow}_{\mathcal{M},do(\bar{S})}(X,\widehat{\mathcal{Y}}):=
\begin{cases}
\left\{\vec{o}\in\vec{\mathcal{O}}\mid\vec{o}_Y\in\widehat{\mathcal{Y}}\right\} & \text{if }X=Y,\\
\vec{\mathcal{O}} & \text{if }\operatorname{ch}(X)=\emptyset,\\
\bigcap_{Z\in\operatorname{ch}(X)\setminus\bar{S}}\widehat{\mathcal{O}}^{\mathrm{pa}}_{\mathcal{M}}\left(Z,\widehat{\mathcal{O}}^{\downarrow}_{\mathcal{M},do(\bar{S})}(Z,\widehat{\mathcal{Y}})\right) & \text{otherwise.}
\end{cases} \tag*{(1)} O M , d o ( S ˉ ) ↓ ( X , Y ) := ⎩ ⎨ ⎧ { o ∈ O ∣ o Y ∈ Y } O ⋂ Z ∈ ch ( X ) ∖ S ˉ O M pa ( Z , O M , d o ( S ˉ ) ↓ ( Z , Y ) ) if X = Y , if ch ( X ) = ∅ , otherwise. (1)
This is the exact set of joint configurations of M d o ( S ˉ ) \mathcal{M}_{do(\bar{S})} M d o ( S ˉ ) compatible with ( Y ∈ Y ^ ) (Y\in\widehat{\mathcal{Y}}) ( Y ∈ Y ) , as constrained by the causal mechanisms between X X X and Y Y Y .
The recursion traverses the causal graph from Y Y Y upward. At the target Y Y Y , the set consists of all full configurations where Y Y Y takes a value in Y ^ \widehat{\mathcal{Y}} Y . For leaves with no children, the set is unconstrained. Otherwise, the descendant targets of all non-intervened children are intersected via parent targets, propagating the joint feasibility constraint upward.
Remark 1 (connection to causal sufficiency). *The preimage F X i − 1 ( o ⃗ i ) F^{-1}_{X_i}(\vec{o}_i) F X i − 1 ( o i ) used by the parent target operator (Definition 1) is exactly the set of joint parent configurations directly sufficient for o ⃗ i \vec{o}_i o i in the sense of Beckers [2 ] ; iterating across descendants Definition 2 realises a graph-aware version of strong sufficiency, the transitive closure of direct sufficiency along the network.
Remark 2 (target reuse under intervention). For any variable X ∈ V X \in\mathcal{V} X ∈ V that is either (i) a strict descendant of some S ′ ∈ S ⃗ S' \in\vec{S} S ′ ∈ S (with X ∉ S ⃗ X \notin\vec{S} X ∈ / S ), meaning S ′ S' S ′ lies above X X X in the DAG and hence not on any directed path from X X X toward Y Y Y , or (ii) an element of S ⃗ \vec{S} S with desc ( X ) ∩ S ⃗ = ∅ \operatorname{desc}(X) \cap\vec{S} = \varnothing desc ( X ) ∩ S = ∅ , the intervention on S ⃗ \vec{S} S does not alter the structural equations on any directed path from X X X to Y Y Y , so the descendant targets are invariant: O ^ M , do ( S ⃗ ) ↓ ( X , Y ^ ) = O ^ M , do ( ∅ ) ↓ ( X , Y ^ ) \widehat{O}^{\downarrow}_{\mathcal{M},\operatorname{do}(\vec{S})}(X,\widehat{Y}) = \widehat{O}^{\downarrow}_{\mathcal{M},\operatorname{do}(\varnothing)}(X,\widehat{Y}) O M , do ( S ) ↓ ( X , Y ) = O M , do ( ∅ ) ↓ ( X , Y ) . This enables efficient recomputation when moving along the witness map introduced in the next subsection; only the ancestors of and within the intervention set need to be recomputed; all descendant targets below the intervention are reused from the observational pass.
The descendant targets O ^ M , do ( S ⃗ ) ↓ ( X , Y ^ ) \widehat{O}^{\downarrow}_{\mathcal{M},\operatorname{do}(\vec{S})}(X,\widehat{Y}) O M , do ( S ) ↓ ( X , Y ) capture what is required at each individual variable X X X . To obtain the complete set of joint configurations compatible with the counterfactual target across the entire model, we aggregate over all roots of the intervened model.
Definition 3 (global targets). For a given SCM M \mathcal{M} M , target variable Y ∈ V Y \in\mathcal{V} Y ∈ V , target values Y ^ ⊆ Y \widehat{Y} \subseteq\mathcal{Y} Y ⊆ Y , and intervention set S ⃗ ⊆ V \vec{S} \subseteq\mathcal{V} S ⊆ V , the global targets O ^ M , do ( S ⃗ ) ( Y ^ ) : = ⋂ R ∈ U ∪ S ⃗ O ^ M , do ( S ⃗ ) ↓ ( R , Y ^ ) \widehat{O}_{\mathcal{M},\operatorname{do}(\vec{S})}(\widehat{Y}) := \bigcap_{R \in\mathcal{U} \cup\vec{S}} \widehat{O}^{\downarrow}_{\mathcal{M},\operatorname{do}(\vec{S})}(R,\widehat{Y}) O M , do ( S ) ( Y ) := ⋂ R ∈ U ∪ S O M , do ( S ) ↓ ( R , Y ) are the set of all variable configurations o ⃗ ∈ O \vec{o} \in\mathcal{O} o ∈ O compatible with the target event ( Y ∈ Y ^ ) (Y \in\widehat{Y}) ( Y ∈ Y ) when constraints are propagated backward from Y Y Y through the structural equations of M do ( S ⃗ ) \mathcal{M}_{\operatorname{do}(\vec{S})} M do ( S ) , obtained by intersecting the descendant targets of all roots of M do ( S ⃗ ) \mathcal{M}_{\operatorname{do}(\vec{S})} M do ( S ) , that is, of all exogenous and all intervened variables. Concrete instances at the four pair-intervention sets of the Billy-and-Suzy example appear in the side panel of Figure 1.
The global targets are constructed by a purely algebraic backward pass. The following theorem validates this construction for the variable configurations that are actually realised: for the unique joint configuration o ⃗ u ⃗ , s ⃗ \vec{o}_{\vec{u},\vec{s}} o u , s induced by M do ( S ⃗ = s ⃗ ) \mathcal{M}_{\operatorname{do}(\vec{S}=\vec{s})} M do ( S = s ) under environment u ⃗ \vec{u} u , global-target membership is equivalent to counterfactual satisfaction of ( Y ∈ Y ^ ) (Y \in\widehat{Y}) ( Y ∈ Y ) .
Theorem 1 (witness target membership). Let M \mathcal{M} M be an acyclic S C M SCM S C M , Y ∈ V Y \in\mathcal{V} Y ∈ V , Y ^ ⊆ Y \widehat{Y} \subseteq\mathcal{Y} Y ⊆ Y , and S ⃗ ⊆ V \vec{S} \subseteq\mathcal{V} S ⊆ V with fixed values s ⃗ ∈ S ⃗ \vec{s} \in\vec{S} s ∈ S . For the unique configuration o ⃗ u ⃗ , s ⃗ : = ( u ⃗ ( X 1 ) , … , u ⃗ ( X o ) , w ⃗ u ⃗ ∗ ( X o + 1 ) , … , w ⃗ u ⃗ ∗ ( X o + p ) ) \vec{o}_{\vec{u},\vec{s}} := (\vec{u}(X_1),\ldots,\vec{u}(X_o),\vec{w}^{*}_{\vec{u}}(X_{o+1}),\ldots,\vec{w}^{*}_{\vec{u}}(X_{o+p})) o u , s := ( u ( X 1 ) , … , u ( X o ) , w u ∗ ( X o + 1 ) , … , w u ∗ ( X o + p )) of setting ( M do ( S ⃗ = s ⃗ ) , u ⃗ ) (\mathcal{M}_{\operatorname{do}(\vec{S}=\vec{s})},\vec{u}) ( M do ( S = s ) , u ) we have:
o ⃗ u ⃗ , s ⃗ ∈ O ^ M , do ( S ⃗ ) ( Y ^ ) ⟺ M do ( S ⃗ = s ⃗ ) , u ⃗ ⊨ ( Y ∈ Y ^ ) . (2) \vec{o}_{\vec{u},\vec{s}} \in\widehat{O}_{\mathcal{M},\operatorname{do}(\vec{S})}(\widehat{Y}) \Longleftrightarrow\mathcal{M}_{\operatorname{do}(\vec{S}=\vec{s})},\vec{u} \models(Y \in\widehat{Y}). \tag*{(2)} o u , s ∈ O M , do ( S ) ( Y ) ⟺ M do ( S = s ) , u ⊨ ( Y ∈ Y ) . (2)
Proof sketch. By induction on the reverse topological order of the DAG. The ( ⇒ ) (\Rightarrow) ( ⇒ ) direction follows from the base case of Definition 2, propagated along a directed path from a root of M do ( S ⃗ ) \mathcal{M}_{\operatorname{do}(\vec{S})} M do ( S ) to Y Y Y . For ( ⇐ ) (\Leftarrow) ( ⇐ ) , acyclicity guarantees that o ⃗ u ⃗ , s ⃗ \vec{o}_{\vec{u},\vec{s}} o u , s is the unique configuration of ( M do ( S ⃗ = s ⃗ ) , u ⃗ ) (\mathcal{M}_{\operatorname{do}(\vec{S}=\vec{s})},\vec{u}) ( M do ( S = s ) , u ) ; membership in every descendant target set then follows by upward induction, using structural consistency of F Z F_Z F Z at each step. The full inductive proof is given in Appendix § 8 .
Theorem 1 gives a membership criterion for fixed values s ⃗ \vec{s} s . For the AC2 condition, we need to check existence over all alternative values x ⃗ ′ ∈ X ⃗ \vec{x}' \in\vec{\mathcal{X}} x ′ ∈ X . The following corollary shows that this existential quantifier can be collapsed into a single projection of the global targets, converting AC2 from a search into a membership test.
Corollary 2 (witness existence). For an acyclic SCM M \mathcal{M} M , Y ∈ V Y \in\mathcal{V} Y ∈ V , Y ^ ⊆ Y \widehat{Y} \subseteq\mathcal{Y} Y ⊆ Y , X ⃗ , Z ⃗ ⊆ V \vec{X},\vec{Z} \subseteq\mathcal{V} X , Z ⊆ V with X ⃗ ∩ Z ⃗ = ∅ \vec{X} \cap\vec{Z} = \varnothing X ∩ Z = ∅ , there exists o ⃗ ∈ O ^ M , do ( X ⃗ , Z ⃗ ) ( Y ^ ) \vec{o} \in\widehat{O}_{\mathcal{M},\operatorname{do}(\vec{X},\vec{Z})}(\widehat{Y}) o ∈ O M , do ( X , Z ) ( Y ) with o ⃗ Z ⃗ = w ⃗ u ⃗ ( Z ⃗ ) \vec{o}_{\vec{Z}} = \vec{w}_{\vec{u}}(\vec{Z}) o Z = w u ( Z ) , the actual values of Z ⃗ \vec{Z} Z (the restriction of the actual world w ⃗ u ⃗ \vec{w}_{\vec{u}} w u to Z ⃗ \vec{Z} Z ), if and only if there exists some x ⃗ ′ ∈ X ⃗ \vec{x}' \in\vec{\mathcal{X}} x ′ ∈ X such that M , u ⃗ ⊨ [ X ⃗ = x ⃗ ′ , Z ⃗ = w ⃗ u ⃗ ( Z ⃗ ) ] ( Y ∈ Y ^ ) \mathcal{M},\vec{u} \models[\vec{X} = \vec{x}',\vec{Z} = \vec{w}_{\vec{u}}(\vec{Z})](Y \in\widehat{Y}) M , u ⊨ [ X = x ′ , Z = w u ( Z )] ( Y ∈ Y ) . The membership condition thus collapses the existential quantifier over alternative values x ⃗ ′ ∈ X ⃗ \vec{x}' \in\vec{\mathcal{X}} x ′ ∈ X in (AC2) into a set-membership query against the global targets.
Proof. S ⃗ : = Z ⃗ ∪ X ⃗ \vec{S} := \vec{Z} \cup\vec{X} S := Z ∪ X . (⇐ \Leftarrow ⇐ ) Suppose there is x ⃗ ′ ∈ X ⃗ \vec{x}' \in\vec{X} x ′ ∈ X s.t. M , u ⃗ ⊨ [ X ⃗ = x ⃗ ′ , Z ⃗ = w ⃗ u ⃗ ( Z ⃗ ) ] ( Y ∈ Y ^ ) \mathcal{M}, \vec{u} \models[\vec{X} = \vec{x}', \vec{Z} = \vec{w}_{\vec{u}}(\vec{Z})](Y \in\widehat{Y}) M , u ⊨ [ X = x ′ , Z = w u ( Z )] ( Y ∈ Y ) . By Theorem 1 (with intervention set S ⃗ \vec{S} S fixed at ( x ⃗ ′ , w ⃗ u ⃗ ( Z ⃗ ) ) (\vec{x}', \vec{w}_{\vec{u}}(\vec{Z})) ( x ′ , w u ( Z )) ), the configuration o ⃗ u ⃗ , s ⃗ ∈ O M , d o ( S ⃗ ) ( Y ^ ) \vec{o}_{\vec{u},\vec{s}} \in\mathcal{O}_{\mathcal{M},do(\vec{S})}(\widehat{Y}) o u , s ∈ O M , d o ( S ) ( Y ) . Since ( o ⃗ u ⃗ , s ⃗ ) U = u ⃗ (\vec{o}_{\vec{u},\vec{s}})_{U} = \vec{u} ( o u , s ) U = u and ( o ⃗ u ⃗ , s ⃗ ) Z ⃗ = w ⃗ u ⃗ ( Z ⃗ ) (\vec{o}_{\vec{u},\vec{s}})_{\vec{Z}} = \vec{w}_{\vec{u}}(\vec{Z}) ( o u , s ) Z = w u ( Z ) , the configuration o ⃗ u ⃗ , s ⃗ \vec{o}_{\vec{u},\vec{s}} o u , s witnesses the existence statement. (⇒ \Rightarrow ⇒ ) Suppose there exists o ⃗ ′ ∈ O M , d o ( S ⃗ ) ( Y ^ ) \vec{o}' \in\mathcal{O}_{\mathcal{M},do(\vec{S})}(\widehat{Y}) o ′ ∈ O M , d o ( S ) ( Y ) with o ⃗ U ′ = u ⃗ \vec{o}'_{U} = \vec{u} o U ′ = u and o ⃗ Z ⃗ ′ = w ⃗ u ⃗ ( Z ⃗ ) \vec{o}'_{\vec{Z}} = \vec{w}_{\vec{u}}(\vec{Z}) o Z ′ = w u ( Z ) . Let x ⃗ ′ : = o ⃗ X ⃗ ′ \vec{x}' := \vec{o}'_{\vec{X}} x ′ := o X ′ . Since M \mathcal{M} M is acyclic, the joint configuration of M d o ( X ⃗ = x ⃗ ′ , Z ⃗ = w ⃗ u ⃗ ( Z ⃗ ) ) \mathcal{M}_{do(\vec{X}=\vec{x}',\vec{Z}=\vec{w}_{\vec{u}}(\vec{Z}))} M d o ( X = x ′ , Z = w u ( Z )) under environment u ⃗ \vec{u} u is unique (each endogenous variable is determined by its parents and the structural equations); hence o ⃗ ′ = o ⃗ u ⃗ , x ⃗ ′ , w ⃗ u ⃗ ( Z ⃗ ) \vec{o}' = \vec{o}_{\vec{u},\vec{x}',\vec{w}_{\vec{u}}(\vec{Z})} o ′ = o u , x ′ , w u ( Z ) . Theorem 1 then yields M , u ⃗ ⊨ [ X ⃗ = x ⃗ ′ , Z ⃗ = w ⃗ u ⃗ ( Z ⃗ ) ] ( Y ∈ Y ^ ) \mathcal{M}, \vec{u} \models[\vec{X} = \vec{x}', \vec{Z} = \vec{w}_{\vec{u}}(\vec{Z})](Y \in\widehat{Y}) M , u ⊨ [ X = x ′ , Z = w u ( Z )] ( Y ∈ Y ) .
Corollary 2 solves the verification half of the enumeration problem: given a candidate pair ( X ⃗ , Z ⃗ ) (\vec{X}, \vec{Z}) ( X , Z ) , a single membership query suffices to decide AC2. What remains is the enumeration half: which intervention sets ( X ⃗ , Z ⃗ ) (\vec{X}, \vec{Z}) ( X , Z ) need to be tested at all? Naively, one would search over all subsets of V V V , a search space that is exponential in ∣ V ∣ |V| ∣ V ∣ . The next subsection replaces this brute-force search with a grammar-based structure that generates only the structurally admissible candidate sets via backward unfolding of the causal graph.
Witness Maps
In the grammar, every variable of the current set either stays as it is (keep) or is replaced by its direct endogenous causes (unfold), moving the search one step further back through the graph. Starting from { Y } \{Y\} { Y } and repeating these two local steps generates all candidate intervention sets; Figure 2 shows a complete example.
Figure 2. (a) Example DAG with pa ( Y ) = { A , C } \operatorname{pa}(Y) = \{A, C\} pa ( Y ) = { A , C } , pa ( C ) = { B } \operatorname{pa}(C) = \{B\} pa ( C ) = { B } , pa ( B ) = { A } \operatorname{pa}(B) = \{A\} pa ( B ) = { A } . (b) Ancestral map A M ( Y ) \mathcal{A}_{\mathcal{M}}(Y) A M ( Y ) (Definition 5): the root’s children are the non-empty subsets of pa M V ( Y ) \operatorname{pa}^{V}_{\mathcal{M}}(Y) pa M V ( Y ) ; the children of every other node follow from Proposition 3. Node { A , C } \{A, C\} { A , C } has four children, { A } \{A\} { A } , { B } \{B\} { B } , { C } \{C\} { C } and { A , B } \{A, B\} { A , B } (Example 1).
Definition 4 (ancestor intervention grammar). Let M \mathcal{M} M have a DAG and Y ∈ V Y \in V Y ∈ V . Write Σ M ( Y ) : = anc M V ( Y ) ∪ { Y } \Sigma_{\mathcal{M}}(Y) := \operatorname{anc}^{V}_{\mathcal{M}}(Y) \cup\{Y\} Σ M ( Y ) := anc M V ( Y ) ∪ { Y } for the endogenous ancestors of Y Y Y including Y Y Y itself. The ancestor intervention grammar G M ( Y ) \mathcal{G}_{\mathcal{M}}(Y) G M ( Y ) is the parallel set-rewriting system with alphabet Σ M ( Y ) \Sigma_{\mathcal{M}}(Y) Σ M ( Y ) , start set { Y } \{Y\} { Y } and productions for every X ∈ Σ M ( Y ) X \in\Sigma_{\mathcal{M}}(Y) X ∈ Σ M ( Y ) :
( P k e e p ) X ⟶ { X } , (3) (P_{\mathrm{keep}})\quad X \longrightarrow\{X\}, \tag*{(3)} ( P keep ) X ⟶ { X } , (3)
( P u n f o l d ) X ⟶ pa M V ( X ) . (4) (P_{\mathrm{unfold}})\quad X \longrightarrow\operatorname{pa}^{V}_{\mathcal{M}}(X). \tag*{(4)} ( P unfold ) X ⟶ pa M V ( X ) . (4)
Both productions are applicable to every symbol (Remark 3 gives their causal reading); for X X X with pa M V ( X ) = ∅ \operatorname{pa}^{V}_{\mathcal{M}}(X) = \varnothing pa M V ( X ) = ∅ , applying ( P u n f o l d ) (P_{\mathrm{unfold}}) ( P unfold ) has the effect of removing X X X from the current set.
A derivation step S ⃗ ⇒ G S ⃗ ′ \vec{S} \Rightarrow_{\mathcal{G}} \vec{S}' S ⇒ G S ′ between non-empty sets S ⃗ , S ⃗ ′ ⊆ Σ M ( Y ) \vec{S}, \vec{S}' \subseteq\Sigma_{\mathcal{M}}(Y) S , S ′ ⊆ Σ M ( Y ) applies a production to each element independently. Choose S ⃗ = S ⃗ u n f o l d ∪ S ⃗ k e e p \vec{S} = \vec{S}_{\mathrm{unfold}} \cup\vec{S}_{\mathrm{keep}} S = S unfold ∪ S keep and set:
S ⃗ ′ ⊆ ⋃ X ∈ S ⃗ u n f o l d pa M V ( X ) ∪ S ⃗ k e e p , S ⃗ ′ ≠ ∅ , (5) \vec{S}' \subseteq\bigcup_{X \in\vec{S}_{\mathrm{unfold}}} \operatorname{pa}^{V}_{\mathcal{M}}(X) \cup\vec{S}_{\mathrm{keep}}, \qquad\vec{S}' \ne\varnothing, \tag*{(5)} S ′ ⊆ X ∈ S unfold ⋃ pa M V ( X ) ∪ S keep , S ′ = ∅ , (5)
where S ⃗ u n f o l d ≠ ∅ \vec{S}_{\mathrm{unfold}} \ne\varnothing S unfold = ∅ (at least one element is unfolded or dropped). Note that for X ∈ S ⃗ u n f o l d X \in\vec{S}_{\mathrm{unfold}} X ∈ S unfold with pa M V ( X ) = ∅ \operatorname{pa}^{V}_{\mathcal{M}}(X) = \varnothing pa M V ( X ) = ∅ , applying ( P u n f o l d ) (P_{\mathrm{unfold}}) ( P unfold ) contributes nothing to S ⃗ ′ \vec{S}' S ′ , so unfolding a source node is equivalent to dropping it. We write S ⃗ ⇒ G + S ⃗ ′ \vec{S} \Rightarrow^{+}_{\mathcal{G}} \vec{S}' S ⇒ G + S ′ if S ⃗ ′ \vec{S}' S ′ is obtained from S ⃗ \vec{S} S by one or more derivation steps (the transitive closure of ⇒ G \Rightarrow_{\mathcal{G}} ⇒ G ). The generated language is L ( G M ( Y ) ) : = { S ⃗ ⊆ Σ M ( Y ) ∣ S ⃗ ≠ ∅ , { Y } ⇒ G + S ⃗ } \mathcal{L}(\mathcal{G}_{\mathcal{M}}(Y)) := \{\vec{S} \subseteq\Sigma_{\mathcal{M}}(Y) \mid\vec{S} \ne\varnothing, \{Y\} \Rightarrow^{+}_{\mathcal{G}} \vec{S}\} L ( G M ( Y )) := { S ⊆ Σ M ( Y ) ∣ S = ∅ , { Y } ⇒ G + S } .
Remark 3 (productions and their roles). The two productions have distinct causal meanings. Keep (X ∈ S ⃗ k e e p X \in\vec{S}_{\mathrm{keep}} X ∈ S keep ): the variable is already at the right ancestral depth and will remain in the intervention set. Unfold (X ∈ S ⃗ u n f o l d X \in\vec{S}_{\mathrm{unfold}} X ∈ S unfold ): the variable’s causal influence is traced one step further back through its endogenous parents pa M V ( X ) \operatorname{pa}^{V}_{\mathcal{M}}(X) pa M V ( X ) . This allows the grammar to generate sets of ancestors at various depths, which is crucial for identifying actual causes that may lie at different levels of the causal graph. In particular, the grammar allows to move from an intervention set to any of its non-empty proper subsets in one step, since unfolded elements need not be selected for S ⃗ ′ \vec{S}' S ′ .
Definition 5 (ancestral map). For an SCM M \mathcal{M} M and target Y ∈ V Y \in\mathbf{V} Y ∈ V , the ancestral map A M ( Y ) \mathcal{A}_{\mathcal{M}}(Y) A M ( Y ) is the directed graph whose nodes are the elements of L ( G M ( Y ) ) \mathcal{L}(G_{\mathcal{M}}(Y)) L ( G M ( Y )) together with the root { Y } \{Y\} { Y } , and whose edges are the derivation steps: S ⃗ → S ⃗ ′ \vec{S} \to\vec{S}' S → S ′ in A M ( Y ) \mathcal{A}_{\mathcal{M}}(Y) A M ( Y ) iff S ⃗ ⇒ G S ⃗ ′ \vec{S} \Rightarrow_{G} \vec{S}' S ⇒ G S ′ in a single step.
The ancestral map is defined implicitly via derivation steps of the grammar. For computational purposes, it is useful to have a closed-form expression for the children of any node S ⃗ \vec{S} S directly in terms of the graph structure of G M G_{\mathcal{M}} G M , without simulating individual derivation steps.
Proposition 3 (grammar–graph equivalence). For a set S ⃗ ′ \vec{S}' S ′ , write p a M V ( S ⃗ ′ ) : = ⋃ X ∈ S ⃗ ′ p a M V ( X ) pa^{\mathbf{V}}_{\mathcal{M}}(\vec{S}') := \bigcup_{X \in\vec{S}'} pa^{\mathbf{V}}_{\mathcal{M}}(X) p a M V ( S ′ ) := ⋃ X ∈ S ′ p a M V ( X ) , let c h A ( S ⃗ ) ch_{\mathcal{A}}(\vec{S}) c h A ( S ) denote the set of children of a node S ⃗ \vec{S} S in A M ( Y ) \mathcal{A}_{\mathcal{M}}(Y) A M ( Y ) , and let P ( ⋅ ) \mathcal{P}(\cdot) P ( ⋅ ) be the powerset operator. Then c h A ( S ⃗ ) = ⋃ ∅ ≠ S ⃗ ′ ⊆ S ⃗ P ( p a M V ( S ⃗ ′ ) ∪ ( S ⃗ ∖ S ⃗ ′ ) ) ∖ { ∅ } ch_{\mathcal{A}}(\vec{S}) = \bigcup_{\varnothing\ne\vec{S}' \subseteq\vec{S}} \mathcal{P}\left(pa^{\mathbf{V}}_{\mathcal{M}}(\vec{S}') \cup\left(\vec{S} \setminus\vec{S}'\right)\right) \setminus\{\varnothing\} c h A ( S ) = ⋃ ∅ = S ′ ⊆ S P ( p a M V ( S ′ ) ∪ ( S ∖ S ′ ) ) ∖ { ∅ } . The proof is given in Appendix § 8 .
Example 1 (derivation steps). In Figure 2 , consider the node S ⃗ = { A , C } \vec{S} = \{A, C\} S = { A , C } . Unfolding C C C and keeping A A A yields the candidate set p a M V ( C ) ∪ { A } = { A , B } pa^{\mathbf{V}}_{\mathcal{M}}(C) \cup\{A\} = \{A, B\} p a M V ( C ) ∪ { A } = { A , B } , whose non-empty subsets { A } \{A\} { A } , { B } \{B\} { B } and { A , B } \{A, B\} { A , B } are children. Unfolding A A A drops it, since p a M V ( A ) = ∅ pa^{\mathbf{V}}_{\mathcal{M}}(A) = \varnothing p a M V ( A ) = ∅ , and keeping C C C yields { C } \{C\} { C } ; unfolding both yields { B } \{B\} { B } . Hence c h A ( { A , C } ) = { { A } , { B } , { C } , { A , B } } ch_{\mathcal{A}}(\{A, C\}) = \{\{A\}, \{B\}, \{C\}, \{A, B\}\} c h A ({ A , C }) = {{ A } , { B } , { C } , { A , B }} , as stated by Proposition 3.
Finiteness bounds the search space; the next question is which ancestor sets actually appear as nodes. The following proposition gives a sufficient condition for reachability, a criterion we will invoke in the completeness proof of Theorem 6 to show that every actual cause’s intervention set is represented in the map.
Proposition 4 (ancestor reachability). Let S ⃗ ⊆ a n c M V ( Y ) \vec{S} \subseteq anc^{\mathbf{V}}_{\mathcal{M}}(Y) S ⊆ an c M V ( Y ) , S ⃗ ≠ ∅ \vec{S} \ne\varnothing S = ∅ . If every X ∈ S ⃗ X \in\vec{S} X ∈ S has a directed path to Y Y Y in G M ∗ p a s s i n g t h r o u g h n o o t h e r e l e m e n t o f ∗ G_{\mathcal{M}} *passing through no other element of* G M ∗ p a ss in g t h r o ug hn oo t h er e l e m e n t o f ∗ \vec{S}$, then S ⃗ ∈ A M ( Y ) \vec{S} \in\mathcal{A}_{\mathcal{M}}(Y) S ∈ A M ( Y ) .
Proof. Starting at the root node { Y } \{Y\} { Y } in A M ( Y ) \mathcal{A}_{\mathcal{M}}(Y) A M ( Y ) , we iteratively unfold variables into their parents until some node contains an element X ∈ S ⃗ X \in\vec{S} X ∈ S . We keep X X X and continue unfolding the remaining variables until a node also contains the next element of S ⃗ \vec{S} S , and so on. If some X ∈ S ⃗ X \in\vec{S} X ∈ S were not reachable by this procedure, every directed path from X X X to Y Y Y would pass through another element of S ⃗ \vec{S} S already included, contradicting the assumption.
We now have both ingredients needed to identify actual causes: the global targets from § 4.1 , which capture counterfactual satisfaction algebraically, and the ancestral map, which enumerates all structurally admissible candidate intervention sets. Combining them yields the witness map : the ancestral map annotated at each node with the corresponding global targets.
Definition 6 (witness map). For an ancestral map A M ( Y ) \mathcal{A}_{\mathcal{M}}(Y) A M ( Y ) and target values Y ^ ⊆ Y \hat{\mathcal{Y}} \subseteq\mathcal{Y} Y ^ ⊆ Y , the witness map W M ( Y ∈ Y ^ ) \mathcal{W}_{\mathcal{M}}(Y \in\hat{\mathcal{Y}}) W M ( Y ∈ Y ^ ) is the directed graph obtained from A M ( Y ) \mathcal{A}_{\mathcal{M}}(Y) A M ( Y ) by labelling each node S ⃗ \vec{S} S (a set of ancestors of Y Y Y ) with O ^ M , d o ( S ⃗ ) ( Y ^ ) \hat{\mathcal{O}}_{\mathcal{M},do(\vec{S})}(\hat{\mathcal{Y}}) O ^ M , d o ( S ) ( Y ^ ) , where the root node { Y } \{Y\} { Y } is labelled O ^ M , d o ( ∅ ) ( Y ^ ) \hat{\mathcal{O}}_{\mathcal{M},do(\varnothing)}(\hat{\mathcal{Y}}) O ^ M , d o ( ∅ ) ( Y ^ ) . Each node thus encodes the exact set of joint variable configurations of M d o ( S ⃗ ) \mathcal{M}_{do(\vec{S})} M d o ( S ) compatible with the target event, and traversal of the map corresponds to systematically extending the intervention set along the causal ancestry of Y Y Y . Figure 1(b) displays the witness map for the Billy-and-Suzy preemption example.
We now establish soundness (Lemma 5) and sufficiency of the witness map (Theorem 6), the latter directly inducing completeness of Algorithm 1.
Lemma 5 (AC-witness identification). Let ( M , u ⃗ ) (\mathcal{M}, \vec{u}) ( M , u ) be a setting of an acyclic SCM with M , u ⃗ ⊨ ( Y ∈ Y ∗ ) \mathcal{M}, \vec{u} \models(Y \in\mathcal{Y}^{*}) M , u ⊨ ( Y ∈ Y ∗ ) , and let Y ∈ V Y \in\mathbf{V} Y ∈ V , Y ∗ ⊆ Y \mathcal{Y}^{*} \subseteq\mathcal{Y} Y ∗ ⊆ Y , Y ^ : = Y ∖ Y ∗ \hat{\mathcal{Y}} := \mathcal{Y} \setminus\mathcal{Y}^{*} Y ^ := Y ∖ Y ∗ . For disjoint X ⃗ , Z ⃗ ⊆ V \vec{X}, \vec{Z} \subseteq\mathbf{V} X , Z ⊆ V the following two statements hold: (But-for causes.) If X ⃗ ∈ L ( G M ( Y ) ) \vec{X} \in\mathcal{L}(G_{\mathcal{M}}(Y)) X ∈ L ( G M ( Y )) is a non-root node of W M ( Y ∈ Y ^ ) \mathcal{W}_{\mathcal{M}}(Y \in\hat{\mathcal{Y}}) W M ( Y ∈ Y ^ ) and there exists o ⃗ ∈ O ^ M , d o ( X ⃗ ) ( Y ^ ) \vec{o} \in\hat{\mathcal{O}}_{\mathcal{M},do(\vec{X})}(\hat{\mathcal{Y}}) o ∈ O ^ M , d o ( X ) ( Y ^ ) with o ⃗ U = u ⃗ \vec{o}_{\mathbf{U}} = \vec{u} o U = u , then there exists x ⃗ ′ ∈ X ⃗ \vec{x}' \in\vec{X} x ′ ∈ X with x ⃗ ′ ≠ w ⃗ u ⃗ ( X ⃗ ) \vec{x}' \ne\vec{w}_{\vec{u}}(\vec{X}) x ′ = w u ( X ) such that ( ∅ , X ⃗ , x ⃗ ′ , Y ∗ ) (\varnothing, \vec{X}, \vec{x}', \mathcal{Y}^{*}) ( ∅ , X , x ′ , Y ∗ ) is a counterfactual witness for ( X ⃗ = w ⃗ u ⃗ ( X ⃗ ) ) (\vec{X} = \vec{w}_{\vec{u}}(\vec{X})) ( X = w u ( X )) satisfying (AC1) and (AC2 ). In particular,* ( X ⃗ = w ⃗ u ⃗ ( X ⃗ ) ) (\vec{X} = \vec{w}_{\vec{u}}(\vec{X})) ( X = w u ( X )) is a but-for cause of ( Y ∈ Y ∗ ) (Y \in\mathcal{Y}^{*}) ( Y ∈ Y ∗ ) if additionally X ⃗ \vec{X} X is minimal. (Actual causes.) If X ⃗ ∪ Z ⃗ ∈ L ( G M ( Y ) ) \vec{X} \cup\vec{Z} \in\mathcal{L}(G_{\mathcal{M}}(Y)) X ∪ Z ∈ L ( G M ( Y ))
is a non-root node of W M ( Y ∈ Y ^ ) W_{\mathcal{M}}(Y \in\hat{Y}) W M ( Y ∈ Y ^ ) and there exists o ⃗ ∈ O ^ M , d o ( X ⃗ , Z ⃗ ) ( Y ^ ) \vec{o} \in\hat{O}_{M,do(\vec{X},\vec{Z})}(\hat{Y}) o ∈ O ^ M , d o ( X , Z ) ( Y ^ ) with o ⃗ U = u ⃗ \vec{o}_{U} = \vec{u} o U = u and o ⃗ Z ⃗ = w u ⃗ ( Z ⃗ ) \vec{o}_{\vec{Z}} = w_{\vec{u}}(\vec{Z}) o Z = w u ( Z ) , then there exists x ⃗ ′ ∈ X ⃗ \vec{x}' \in\vec{X} x ′ ∈ X with x ⃗ ′ ≠ w u ⃗ ( X ⃗ ) \vec{x}' \ne w_{\vec{u}}(\vec{X}) x ′ = w u ( X ) such that ( Z ⃗ , X ⃗ , x ⃗ ′ , Y ∗ ) (\vec{Z},\vec{X},\vec{x}',\mathcal{Y}^{*}) ( Z , X , x ′ , Y ∗ ) is a counterfactual witness for ( X ⃗ = w u ⃗ ( X ⃗ ) ) (\vec{X} = w_{\vec{u}}(\vec{X})) ( X = w u ( X )) satisfying (AC1) and (AC2) with contingency set Z ⃗ \vec{Z} Z . In particular, ( X ⃗ = w u ⃗ ( X ⃗ ) ) (\vec{X} = w_{\vec{u}}(\vec{X})) ( X = w u ( X )) is an actual cause of ( Y ∈ Y ∗ ) (Y \in\mathcal{Y}^{*}) ( Y ∈ Y ∗ ) if additionally X ⃗ \vec{X} X is minimal.
Proof sketch. (AC1) holds trivially since w u ⃗ w_{\vec{u}} w u is the actual world. For (AC2), Corollary 2 yields an x ⃗ ′ ∈ X ⃗ \vec{x}' \in\vec{X} x ′ ∈ X with M , u ⃗ ⊨ [ X ⃗ = x ⃗ ′ , Z ⃗ = w u ⃗ ( Z ⃗ ) ] ( Y ∈ Y ^ ) \mathcal{M},\vec{u} \models[\vec{X} = \vec{x}',\vec{Z} = w_{\vec{u}}(\vec{Z})](Y \in\hat{Y}) M , u ⊨ [ X = x ′ , Z = w u ( Z )] ( Y ∈ Y ^ ) ; that x ⃗ ′ ≠ w u ⃗ ( X ⃗ ) \vec{x}' \ne w_{\vec{u}}(\vec{X}) x ′ = w u ( X ) follows from the consistency of structural equations (setting x ⃗ ′ = w u ⃗ ( X ⃗ ) \vec{x}' = w_{\vec{u}}(\vec{X}) x ′ = w u ( X ) would reproduce the actual world, contradicting Y ∈ Y ^ Y \in\hat{Y} Y ∈ Y ^ ). See Appendix B for the full proof.
Lemma 5 handles the soundness direction : any node in the witness map that passes the membership test certifies a genuine cause. The converse, which states that no actual cause can be missed, requires showing that every actual cause is represented by some node in the map.
Theorem 6 (sufficiency of witness map). Let ( M , u ⃗ ) (\mathcal{M},\vec{u}) ( M , u ) be a setting of an acyclic SCM with M , u ⃗ ⊨ ( Y ∈ Y ∗ ) \mathcal{M},\vec{u} \models(Y \in\mathcal{Y}^{*}) M , u ⊨ ( Y ∈ Y ∗ ) , and let Y ^ : = Y ∖ Y ∗ \hat{Y} := \mathcal{Y} \setminus\mathcal{Y}^{*} Y ^ := Y ∖ Y ∗ . For every actual cause ( X ⃗ = w u ⃗ ( X ⃗ ) ) (\vec{X} = w_{\vec{u}}(\vec{X})) ( X = w u ( X )) of ( Y ∈ Y ∗ ) (Y \in\mathcal{Y}^{*}) ( Y ∈ Y ∗ ) , there exists a contingency set Z ⃗ ⊆ V ∖ X ⃗ \vec{Z} \subseteq V \setminus\vec{X} Z ⊆ V ∖ X such that X ⃗ ∪ Z ⃗ ∈ L ( G M ( Y ) ) \vec{X} \cup\vec{Z} \in\mathcal{L}(G_{\mathcal{M}}(Y)) X ∪ Z ∈ L ( G M ( Y )) and
∃ o ⃗ ∈ O ^ M , d o ( X ⃗ , Z ⃗ ) ( Y ^ ) with o ⃗ U = u ⃗ and o ⃗ Z ⃗ = w u ⃗ ( Z ⃗ ) . (6) \exists\vec{o} \in\hat{O}_{\mathcal{M},do(\vec{X},\vec{Z})}(\hat{Y}) \text{ with } \vec{o}_{U} = \vec{u} \text{ and } \vec{o}_{\vec{Z}} = w_{\vec{u}}(\vec{Z}). \tag*{(6)} ∃ o ∈ O ^ M , d o ( X , Z ) ( Y ^ ) with o U = u and o Z = w u ( Z ) . (6) In particular, but-for causes are the special case Z ⃗ = ∅ \vec{Z} = \emptyset Z = ∅ , for which the membership condition reduces to the existence of o ⃗ ∈ O ^ M , d o ( X ⃗ ) ( Y ^ ) \vec{o} \in\hat{O}_{\mathcal{M},do(\vec{X})}(\hat{Y}) o ∈ O ^ M , d o ( X ) ( Y ^ ) with o ⃗ U = u ⃗ \vec{o}_{U} = \vec{u} o U = u .
Proof. By (AC2), there exist Z ⃗ 0 ⊆ V ∖ X ⃗ \vec{Z}_{0} \subseteq V \setminus\vec{X} Z 0 ⊆ V ∖ X and x ⃗ ′ ≠ w u ⃗ ( X ⃗ ) \vec{x}' \ne w_{\vec{u}}(\vec{X}) x ′ = w u ( X ) such that M , u ⃗ ⊨ [ X ⃗ = x ⃗ ′ , Z ⃗ 0 = w u ⃗ ( Z ⃗ 0 ) ] ( Y ∈ Y ^ ) \mathcal{M},\vec{u} \models[\vec{X} = \vec{x}', \vec{Z}_{0} = w_{\vec{u}}(\vec{Z}_{0})](Y \in\hat{Y}) M , u ⊨ [ X = x ′ , Z 0 = w u ( Z 0 )] ( Y ∈ Y ^ ) . (For but-for causes, (AC2*) gives this with Z ⃗ 0 = ∅ \vec{Z}_{0} = \emptyset Z 0 = ∅ directly.) Let Z ⃗ ⊆ Z ⃗ 0 \vec{Z} \subseteq\vec{Z}_{0} Z ⊆ Z 0 be inclusion-minimal such that M , u ⃗ ⊨ [ X ⃗ = x ⃗ ′ , Z ⃗ = w u ⃗ ( Z ⃗ ) ] ( Y ∈ Y ^ ) \mathcal{M},\vec{u} \models[\vec{X} = \vec{x}', \vec{Z} = w_{\vec{u}}(\vec{Z})](Y \in\hat{Y}) M , u ⊨ [ X = x ′ , Z = w u ( Z )] ( Y ∈ Y ^ ) still holds; such a minimum exists since the collection of valid Z ⃗ ′ ⊆ Z ⃗ 0 \vec{Z}' \subseteq\vec{Z}_{0} Z ′ ⊆ Z 0 is non-empty and finite. For node existence: X ⃗ ∪ Z ⃗ ∈ L ( G M ( Y ) ) \vec{X} \cup\vec{Z} \in\mathcal{L}(G_{\mathcal{M}}(Y)) X ∪ Z ∈ L ( G M ( Y )) . By Proposition 4, it suffices to show that every element of X ⃗ ∪ Z ⃗ \vec{X} \cup\vec{Z} X ∪ Z has a directed path to Y Y Y in G M G_{\mathcal{M}} G M passing through no other element of X ⃗ ∪ Z ⃗ \vec{X} \cup\vec{Z} X ∪ Z . Suppose for contradiction that some V ′ ∈ X ⃗ ∪ Z ⃗ V' \in\vec{X} \cup\vec{Z} V ′ ∈ X ∪ Z has all directed paths to Y Y Y blocked at some V ′ ′ ∈ ( X ⃗ ∪ Z ⃗ ) ∖ { V ′ } V'' \in(\vec{X} \cup\vec{Z}) \setminus\{V'\} V ′′ ∈ ( X ∪ Z ) ∖ { V ′ } . In M d o ( X ⃗ = x ⃗ ′ , Z ⃗ = w u ⃗ ( Z ⃗ ) ) \mathcal{M}_{do(\vec{X}=\vec{x}',\vec{Z}=w_{\vec{u}}(\vec{Z}))} M d o ( X = x ′ , Z = w u ( Z )) , the structural equation for V ′ ′ V'' V ′′ is overridden, so V ′ V' V ′ cannot influence w u ⃗ ( Y ) w_{\vec{u}}(Y) w u ( Y ) through V ′ ′ V'' V ′′ . Since every causal path from V ′ V' V ′ to Y Y Y passes through V ′ ′ V'' V ′′ , the value of V ′ V' V ′ is causally inert for Y Y Y in this model; hence M , u ⃗ ⊨ [ X ⃗ = x ⃗ ′ , ( Z ⃗ ∪ X ⃗ ∖ { V ′ } ) = w u ⃗ ( Z ⃗ ∪ X ⃗ ∖ { V ′ } ) ] ( Y ∈ Y ^ ) \mathcal{M},\vec{u} \models[\vec{X} = \vec{x}',(\vec{Z} \cup\vec{X} \setminus\{V'\}) = w_{\vec{u}}(\vec{Z} \cup\vec{X} \setminus\{V'\})](Y \in\hat{Y}) M , u ⊨ [ X = x ′ , ( Z ∪ X ∖ { V ′ }) = w u ( Z ∪ X ∖ { V ′ })] ( Y ∈ Y ^ ) . If V ′ ∈ X ⃗ V' \in\vec{X} V ′ ∈ X , this contradicts the minimality (AC3) of X ⃗ \vec{X} X (we could drop V ′ V' V ′ from the cause). If V ′ ∈ Z ⃗ V' \in\vec{Z} V ′ ∈ Z , this contradicts the minimality of Z ⃗ \vec{Z} Z . Hence every V ′ ∈ X ⃗ ∪ Z ⃗ V' \in\vec{X} \cup\vec{Z} V ′ ∈ X ∪ Z has a path to Y Y Y through no other element of X ⃗ ∪ Z ⃗ \vec{X} \cup\vec{Z} X ∪ Z , and X ⃗ ∪ Z ⃗ ∈ L ( G M ( Y ) ) \vec{X} \cup\vec{Z} \in\mathcal{L}(G_{\mathcal{M}}(Y)) X ∪ Z ∈ L ( G M ( Y )) follows. The membership condition now directly follows from Corollary 2.
Algorithm
We summarise the identification procedure in Algorithm 1. By Theorem 6, every actual cause admits a witness ( Z ⃗ , X ⃗ , x ⃗ ′ , Y ∗ ) (\vec{Z},\vec{X},\vec{x}',\mathcal{Y}^{*}) ( Z , X , x ′ , Y ∗ ) with X ⃗ ∪ Z ⃗ ∈ L ( G M ( Y ) ) \vec{X} \cup\vec{Z} \in\mathcal{L}(G_{\mathcal{M}}(Y)) X ∪ Z ∈ L ( G M ( Y )) , so every relevant intervention set already appears as a node of the witness map. By Corollary 2, the AC2 condition for a pair ( X ⃗ , Z ⃗ ) (\vec{X},\vec{Z}) ( X , Z ) then reduces to a single membership query against the precomputed global targets O ^ M , d o ( X ⃗ ∪ Z ⃗ ) ( Y ^ ) \hat{O}_{\mathcal{M},do(\vec{X}\cup\vec{Z})}(\hat{Y}) O ^ M , d o ( X ∪ Z ) ( Y ^ ) . The algorithm therefore treats each node S ⃗ ∈ A M ( Y ) \vec{S} \in\mathcal{A}_{\mathcal{M}}(Y) S ∈ A M ( Y ) directly as the total intervention set and enumerates all partitions S ⃗ = X ⃗ ∪ Z ⃗ \vec{S} = \vec{X} \cup\vec{Z} S = X ∪ Z , where X ⃗ \vec{X} X is the candidate cause and Z ⃗ = S ⃗ ∖ X ⃗ \vec{Z} = \vec{S} \setminus\vec{X} Z = S ∖ X is the contingency set, testing each against these targets (Phase 2).
Theorem 7 (soundness and completeness). Let ( M , u ⃗ ) (\mathcal{M},\vec{u}) ( M , u ) be a setting of an acyclic SCM with M , u ⃗ ⊨ ( Y ∈ Y ∗ ) \mathcal{M},\vec{u} \models(Y \in\mathcal{Y}^{*}) M , u ⊨ ( Y ∈ Y ∗ ) , and let Y ^ : = Y ∖ Y ∗ \hat{Y} := \mathcal{Y} \setminus\mathcal{Y}^{*} Y ^ := Y ∖ Y ∗ . Algorithm 1 returns exactly the collection C \mathcal{C} C of variable sets X ⃗ ⊆ V \vec{X} \subseteq V X ⊆ V such that ( X ⃗ = w u ⃗ ( X ⃗ ) ) (\vec{X} = w_{\vec{u}}(\vec{X})) ( X = w u ( X )) is an actual cause of ( Y ∈ Y ∗ ) (Y \in\mathcal{Y}^{*}) ( Y ∈ Y ∗ ) : X ⃗ ∈ C \vec{X} \in\mathcal{C} X ∈ C iff ( X ⃗ = w u ⃗ ( X ⃗ ) ) (\vec{X} = w_{\vec{u}}(\vec{X})) ( X = w u ( X )) is an actual cause of ( Y ∈ Y ∗ ) (Y \in\mathcal{Y}^{*}) ( Y ∈ Y ∗ ) .
Proof. Soundness (⇒ \Rightarrow ⇒ ). Suppose X ⃗ ∈ C \vec{X} \in\mathcal{C} X ∈ C upon termination of Algorithm 1. By Phase 2, there exists a node S ⃗ ∈ A M ( Y ) \vec{S} \in\mathcal{A}_{\mathcal{M}}(Y) S ∈ A M ( Y ) such that X ⃗ ⊆ S ⃗ \vec{X} \subseteq\vec{S} X ⊆ S and, with Z ⃗ : = S ⃗ ∖ X ⃗ \vec{Z} := \vec{S} \setminus\vec{X} Z := S ∖ X , the membership test ∃ o ⃗ ∈ O ^ M , d o ( S ⃗ ) ( Y ^ ) \exists\vec{o} \in\hat{O}_{\mathcal{M},do(\vec{S})}(\hat{Y}) ∃ o ∈ O ^ M , d o ( S ) ( Y ^ ) with o ⃗ U = u ⃗ , o ⃗ Z ⃗ = w u ⃗ ( Z ⃗ ) \vec{o}_{U}=\vec{u},\vec{o}_{\vec{Z}}=w_{\vec{u}}(\vec{Z}) o U = u , o Z = w u ( Z ) passed. Since S ⃗ ∈ L ( G M ( Y ) ) \vec{S}\in\mathcal{L}(G_{M}(Y)) S ∈ L ( G M ( Y )) , S ⃗ \vec{S} S is a non-root node of W M ( Y ∈ Y ^ ) W_{M}(Y\in\hat{\mathcal{Y}}) W M ( Y ∈ Y ^ ) . Lemma 5 then gives the existence of x ⃗ ′ ≠ w u ⃗ ( X ⃗ ) \vec{x}^{\prime}\ne w_{\vec{u}}(\vec{X}) x ′ = w u ( X ) such that ( Z ⃗ , X ⃗ , x ⃗ ′ , Y ^ ) (\vec{Z},\vec{X},\vec{x}^{\prime},\hat{\mathcal{Y}}) ( Z , X , x ′ , Y ^ ) is a counterfactual witness satisfying (AC1) and (AC2). Phase 3 retains only minimal elements, so X ⃗ \vec{X} X satisfies (AC3). Hence ( X ⃗ = w u ⃗ ( X ⃗ ) ) (\vec{X}=w_{\vec{u}}(\vec{X})) ( X = w u ( X )) is an actual cause.
Completeness (⇐). Suppose ( X ⃗ = w u ⃗ ( X ⃗ ) ) (\vec{X}=w_{\vec{u}}(\vec{X})) ( X = w u ( X )) is an actual cause of ( Y ∈ Y ∗ ) (Y\in\mathcal{Y}^{*}) ( Y ∈ Y ∗ ) . By Theorem 6, there exists Z ⃗ ⊆ Σ M ( Y ) ∖ X ⃗ \vec{Z}\subseteq\Sigma_{M}(Y)\setminus\vec{X} Z ⊆ Σ M ( Y ) ∖ X such that S ⃗ : = X ⃗ ∪ Z ⃗ ∈ L ( G M ( Y ) ) \vec{S}:=\vec{X}\cup\vec{Z}\in\mathcal{L}(G_{M}(Y)) S := X ∪ Z ∈ L ( G M ( Y )) and some o ⃗ ∈ O ^ M , do ( X ⃗ , Z ⃗ ) ( Y ^ ) \vec{o}\in\hat{O}_{M,\operatorname{do}(\vec{X},\vec{Z})}(\hat{\mathcal{Y}}) o ∈ O ^ M , do ( X , Z ) ( Y ^ ) satisfies o ⃗ U = u ⃗ , o ⃗ Z ⃗ = w u ⃗ ( Z ⃗ ) \vec{o}_{U}=\vec{u},\vec{o}_{\vec{Z}}=w_{\vec{u}}(\vec{Z}) o U = u , o Z = w u ( Z ) . Hence the membership test for the partition ( X ⃗ , Z ⃗ ) (\vec{X},\vec{Z}) ( X , Z ) of S ⃗ \vec{S} S succeeds in Phase 2, so X ⃗ \vec{X} X is added to C C C . Since ( X ⃗ = w u ⃗ ( X ⃗ ) ) (\vec{X}=w_{\vec{u}}(\vec{X})) ( X = w u ( X )) satisfies (AC3) by assumption, X ⃗ \vec{X} X is not removed in Phase 3. Therefore X ⃗ ∈ C \vec{X}\in C X ∈ C upon termination.
Relative to the theoretical framework of § 4.2 , correctness is established by Theorem 7 below: soundness rests on Lemma 5, which shows that every positive membership test corresponds to a genuine counterfactual witness; completeness rests on Theorem 6, which guarantees that every actual cause is represented by some node in the witness map. Phase 3 compares the collected candidates pairwise under set inclusion and removes every X ⃗ \vec{X} X for which some strict subset is also in C C C . This filter is exact: by Lemma 5, every removed X ⃗ \vec{X} X has a strict subset satisfying AC1 and AC2 and hence violates AC3, and by Theorem 6, every actual cause is in C C C , so every non-minimal X ⃗ \vec{X} X contains one as a strict subset and is removed.
Having established that Algorithm 1 is both sound and complete, we briefly comment on its computational cost. Crucially, Corollary 2 eliminates any enumeration over alternative values x ⃗ ′ \vec{x}^{\prime} x ′ , so the cost depends only on the causal graph and intervention-set sizes, not on the domain size. The number of membership queries is O ( 3 a ) O(3^{a}) O ( 3 a ) in the worst case (with a : = ∣ anc M ( Y ) ∣ a:=|\operatorname{anc}_{M}(Y)| a := ∣ anc M ( Y ) ∣ ) and reduces to a polynomial number under bounded intervention size; the full three-parameterisation analysis is deferred to Appendix § 11 . The remainder of this section describes pruning strategies that substantially reduce the practical cost without affecting soundness or completeness.
Remark 6 (Phase 2 pruning strategies). Three strategies reduce the cost of Phase 2 without affecting soundness or completeness: (i) size-first traversal processes smaller nodes first, letting confirmed causes prune supersets early; (ii) node-level pre-check tests existence of o ⃗ ∈ O ^ M , do ( S ⃗ ) ( Y ^ ) \vec{o}\in\hat{O}_{M,\operatorname{do}(\vec{S})}(\hat{\mathcal{Y}}) o ∈ O ^ M , do ( S ) ( Y ^ ) with o ⃗ U = u ⃗ \vec{o}_{U}=\vec{u} o U = u before enumerating the 2 ∣ S ⃗ ∣ − 1 2^{|\vec{S}|}-1 2 ∣ S ∣ − 1 subsets of S ⃗ \vec{S} S , skipping the node on failure; (iii) superset pruning skips any X ⃗ ⊆ S ⃗ \vec{X}\subseteq\vec{S} X ⊆ S for which a confirmed X ⃗ ′ ⊊ X ⃗ \vec{X}^{\prime}\subsetneq\vec{X} X ′ ⊊ X already exists. The completeness proof of Theorem 6 only needs nodes satisfying the condition of Proposition 4 , so nodes violating it never have to be tested. Justifications, the implication that (iii) makes Phase 3 redundant when combined with (i), and continuous-domain adaptations (interval, LP, and bisection-based pre-checks) are given in Appendix § 12 .
Figure 1 (PDF p. 9).
Algorithm 1: Tracing Actual Causes (TrAC)
Input: SCM M M M , environment u ⃗ \vec{u} u , target variable Y Y Y , target event Y ∗ \mathcal{Y}^{*} Y ∗
Output: Set of (nodes of) actual causes C ⊆ P ( V ) C\subseteq\mathcal{P}(V) C ⊆ P ( V )
Y ^ ← Y ∖ Y ∗ \hat{\mathcal{Y}}\leftarrow\mathcal{Y}\setminus\mathcal{Y}^{*} Y ^ ← Y ∖ Y ∗ ;
/* Phase 1: Precompute observational global targets (single bottom-up pass) */
foreach X ∈ V ∪ U X\in V\cup U X ∈ V ∪ U in reverse topological order do
\quad Compute O ^ M , do ( ∅ ) ↓ ( X , Y ^ ) \hat{O}^{\downarrow}_{M,\operatorname{do}(\emptyset)}(X,\hat{\mathcal{Y}}) O ^ M , do ( ∅ ) ↓ ( X , Y ^ ) ;
O ^ M , do ( ∅ ) ( Y ^ ) ← ⋂ U ∈ U O ^ M , do ( ∅ ) ↓ ( U , Y ^ ) \hat{O}_{M,\operatorname{do}(\emptyset)}(\hat{\mathcal{Y}})\leftarrow\bigcap_{U\in U}\hat{O}^{\downarrow}_{M,\operatorname{do}(\emptyset)}(U,\hat{\mathcal{Y}}) O ^ M , do ( ∅ ) ( Y ^ ) ← ⋂ U ∈ U O ^ M , do ( ∅ ) ↓ ( U , Y ^ ) ;
C ← ∅ C\leftarrow\emptyset C ← ∅ ;
/* Check that the actual world is incompatible with the counterfactual target */
if ∃ o ⃗ ∈ O ^ M , do ( ∅ ) ( Y ^ ) \exists\vec{o}\in\hat{O}_{M,\operatorname{do}(\emptyset)}(\hat{\mathcal{Y}}) ∃ o ∈ O ^ M , do ( ∅ ) ( Y ^ ) with o ⃗ U = u ⃗ \vec{o}_{U}=\vec{u} o U = u then
\quad return C C C
/* Phase 2: Traverse witness map */
foreach node S ⃗ \vec{S} S in A M ( Y ) \mathcal{A}_{M}(Y) A M ( Y ) do
/* Recompute targets above S ⃗ \vec{S} S only; reuse below (Remark 2) */
\quad Compute O ^ M , do ( S ⃗ ) ( Y ^ ) \hat{O}_{M,\operatorname{do}(\vec{S})}(\hat{\mathcal{Y}}) O ^ M , do ( S ) ( Y ^ ) ;
/* Enumerate all cause/contingency partitions of S ⃗ \vec{S} S */
\quad foreach non-empty X ⃗ ⊆ S ⃗ \vec{X}\subseteq\vec{S} X ⊆ S do
Z ⃗ ← S ⃗ ∖ X ⃗ \qquad\vec{Z}\leftarrow\vec{S}\setminus\vec{X} Z ← S ∖ X ;
\qquad if ∃ o ⃗ ∈ O ^ M , do ( S ⃗ ) ( Y ^ ) \exists\vec{o}\in\hat{O}_{M,\operatorname{do}(\vec{S})}(\hat{\mathcal{Y}}) ∃ o ∈ O ^ M , do ( S ) ( Y ^ ) with o ⃗ U = u ⃗ \vec{o}_{U}=\vec{u} o U = u and o ⃗ Z ⃗ = w u ⃗ ( Z ⃗ ) \vec{o}_{\vec{Z}}=w_{\vec{u}}(\vec{Z}) o Z = w u ( Z ) then
C ← C ∪ { X ⃗ } \qquad\quad C\leftarrow C\cup\{\vec{X}\} C ← C ∪ { X } ;
/* Phase 3: Apply minimality (AC3) */
Remove each X ⃗ ∈ C \vec{X}\in C X ∈ C with a strict subset in C C C ;
return C C C
Appendix C.1 works through the forest-fire scenario, contrasting overdetermination (F Y = L ∨ A F_Y = L \lor A F Y = L ∨ A , unique joint cause) with conjunctive causation (F Y = L ∧ A F_Y = L \land A F Y = L ∧ A , two singleton but-for causes). Appendix C.2 (Figure 1) covers the Billy-and-Suzy preemption example, illustrating the role of non-empty contingency sets and the derivation of responsibility scores.
Baseline Comparisons
We benchmark TrAC on random Boolean SCMs from acyclic Erdős-Rényi DAGs (n ∈ { 3 , … , 15 } n \in\{3,\ldots,15\} n ∈ { 3 , … , 15 } , density d ∈ { 0.25 , 0.50 , 0.75 } d \in\{0.25, 0.50, 0.75\} d ∈ { 0.25 , 0.50 , 0.75 } , 10 seeds each), comparing against Reyd et al. [29 ] (beam search, ISI) and Ibrahim and Pretschner [19 ] (HP2SAT brute-force (BF), SAT, MaxSAT). Runtimes are shown in Figure 3 . The comparison is not perfectly direct: TrAC is the only method that provably enumerates all actual causes, while the baselines target a single cause without completeness guarantees. On these benchmarks, the combined pruning of Remark 6(ii+iii) removes on average over 97% of witness-map nodes at n ≥ 10 n \ge10 n ≥ 10 for d ≥ 0.5 d \ge0.5 d ≥ 0.5 and 73–94% for d = 0.25 d = 0.25 d = 0.25 (Figure 6 ); the rate is instance-dependent and leaves the O ( 3 a ) O(3^a) O ( 3 a ) worst case of § 4.3 unchanged. As a result, TrAC is typically more than an order of magnitude faster than the brute-force search, while single-cause methods (SAT, MaxSAT, beam, ISI) are faster per query, as expected given they solve a strictly simpler task without completeness guarantees. Further plots and discussion are in Appendix G. All code is available at https://github.com/MoritzWillig/tracingActualCauses.
Figure 3. Runtime comparisons to adjacent baselines. Mean runtime (lines) with [25, 75]-IQR bands (shading) across 10 seeds for TrAC, Reyd et al. [29 ] (beam search, ISI), & Ibrahim and Pretschner [19 ] (HP2SAT BF, SAT, MaxSAT) on random Boolean SCMs. Each SCM is drawn from an acyclic Erdős-Rényi DAG with n ∈ { 3 , … , 15 } n \in\{3,\ldots,15\} n ∈ { 3 , … , 15 } nodes & edge density d ∈ { 1 4 , 1 2 , 3 4 } d \in\{\frac{1}{4},\frac{1}{2},\frac{3}{4}\} d ∈ { 4 1 , 2 1 , 4 3 } ; structural equations are random AND/OR gates with independently negated inputs. (Best viewed in color.)
Figure 6. Pruning rates. Fraction of witness-map nodes eliminated by each strategy (mean ± \pm ± [25, 75]-IQR), broken down by node count and density. The node-level pre-check dominates; combined with superset pruning, on average over 97% of nodes are eliminated for n ≥ 10 n \ge10 n ≥ 10 at d ≥ 0.5 d \ge0.5 d ≥ 0.5 , and 73–94% at d = 0.25 d = 0.25 d = 0.25 .
Conclusion
We presented a constructive procedure for enumerating all actual causes of an event in an acyclic SCM. The key insight is a change of direction: rather than searching forward over alternative values, we propagate the counterfactual target backward through the structural equations. This yields witness targets (Definitions 1–3, Theorem 1), a criterion for counterfactual satisfaction that converts the existential search in AC2 into a single set-membership query, eliminating any dependence on domain size from the per-candidate verification cost. An ancestor intervention grammar then generates all structurally admissible candidate intervention sets as nodes of a finite DAG and the witness map (Definitions 4–6, Propositions 3–4), whose traversal is guaranteed to cover every actual cause (Theorem 6). Algorithm 1 combines both ingredients and is proven sound and complete (Theorem 7) for the modified HP definition.
Limitations. TrAC works with fully specified acyclic SCM; latent confounders can be encoded as exogenous roots, but unknown or partially specified models are out of scope. The main computational limitation is storage: exact global targets require O ( ∣ D O ∣ ) O(|D^{O}|) O ( ∣ D O ∣ ) space in the worst case, with D D D the largest domain size, plus preimage tables of size O ( ∣ V ∣ ⋅ D Δ + 1 ) O(|V| \cdot D^{\Delta+1}) O ( ∣ V ∣ ⋅ D Δ + 1 ) , with Δ \Delta Δ the largest number of endogenous parents (Appendix E.1). All 390 benchmark instances up to n = 15 n=15 n = 15 completed on a single 32 GB machine (Appendix G), whereas our attempts at n = 16 n=16 n = 16 ran out of memory; since each additional Boolean variable doubles the number of configurations, added memory buys roughly one further node. The outer approximation of Appendix D needs only O ( ∣ V ∣ ⋅ D Δ ) O(|V| \cdot D^{\Delta}) O ( ∣ V ∣ ⋅ D Δ ) storage, but it can only screen candidates: a failed check safely rules a candidate out. Compact exact target representations (e.g. BDDs, polytopes) for broader mechanism classes, full distributions P ( U ) P(U) P ( U ) for probabilistic actual causation, and nondeterministic SCMs are the most pressing open directions (Appendix H).
Acknowledgments and Disclosure of Funding
We thank the reviewers for their constructive and thoughtful feedback, which helped to improve this work. This work has benefited from the German Research Foundation (DFG) research grant “Tractable Neuro-Causal Models” (KE 1686/8-1), from the clusters of excellence “Reasonable Artificial Intelligence” (RAI, EXC 3057) and “The Adaptive Mind” (TAM, EXC 3066) under Germany’s Excellence Strategy, and from the LOEWE Center DYNAMIC of the State of Hesse. It was also funded by the European Union (Grant Agreement no. 101120763, TANGO). Views and opinions expressed are, however, those of the author(s) only and do not necessarily reflect those of the European Union or the European Health and Digital Executive Agency (HaDEA). Neither the European Union nor the granting authority can be held responsible for them.
Notation
Table 1. Notation summary.
Extended Proofs
Proof of Theorem 1 (Witness Target Membership)
Proof. We proceed by induction on the reverse topological order of the DAG, traversing from the target Y Y Y upward to the roots of M d o ( S ⃗ ) \mathcal{M}_{do(\vec{S})} M d o ( S ) .
( ⇒ ) (\Rightarrow) ( ⇒ ) Suppose o ⃗ u ⃗ , s ⃗ ∈ O ^ M , d o ( S ⃗ ) ( Y ^ ) \vec{o}_{\vec{u},\vec{s}} \in\widehat{\mathcal{O}}_{\mathcal{M},do(\vec{S})}(\widehat{\mathcal{Y}}) o u , s ∈ O M , d o ( S ) ( Y ) . By Definition 3, o ⃗ u ⃗ , s ⃗ ∈ O ^ M , d o ( S ⃗ ) ↓ ( R , Y ^ ) \vec{o}_{\vec{u},\vec{s}} \in\widehat{\mathcal{O}}^{\downarrow}_{\mathcal{M},do(\vec{S})}(R,\widehat{\mathcal{Y}}) o u , s ∈ O M , d o ( S ) ↓ ( R , Y ) for every root R ∈ U ∪ S ⃗ R \in\mathcal{U} \cup\vec{S} R ∈ U ∪ S . Since every endogenous variable has a parent, following parents upward from Y Y Y through non-intervened variables reaches such a root along a directed path R → X 1 → ⋯ → X k = Y R \to X_1 \to\cdots\to X_k = Y R → X 1 → ⋯ → X k = Y ; since O ^ p a ( X j , O ^ ) ⊆ O ^ \widehat{\mathcal{O}}^{pa(X_j,\widehat{\mathcal{O}})} \subseteq\widehat{\mathcal{O}} O p a ( X j , O ) ⊆ O , the recursion of Definition 2 gives O ^ ↓ ( R ) ⊆ O ^ ↓ ( X 1 ) ⊆ ⋯ ⊆ O ^ ↓ ( Y ) \widehat{\mathcal{O}}^{\downarrow}(R) \subseteq\widehat{\mathcal{O}}^{\downarrow}(X_1) \subseteq\cdots\subseteq\widehat{\mathcal{O}}^{\downarrow}(Y) O ↓ ( R ) ⊆ O ↓ ( X 1 ) ⊆ ⋯ ⊆ O ↓ ( Y ) . Hence the base case of Definition 2 at X = Y X=Y X = Y requires ( o ⃗ u ⃗ , s ⃗ ) Y ∈ Y ^ (\vec{o}_{\vec{u},\vec{s}})_Y \in\widehat{\mathcal{Y}} ( o u , s ) Y ∈ Y , i.e. w u ⃗ ∗ ( Y ) ∈ Y ^ w_{\vec{u}}^*(Y) \in\widehat{\mathcal{Y}} w u ∗ ( Y ) ∈ Y , which gives M d o ( S ⃗ = s ⃗ ) , u ⃗ ⊨ ( Y ∈ Y ^ ) \mathcal{M}_{do(\vec{S}=\vec{s})},\vec{u} \models(Y \in\widehat{\mathcal{Y}}) M d o ( S = s ) , u ⊨ ( Y ∈ Y ) .
( ⇐ ) (\Leftarrow) ( ⇐ ) Suppose M d o ( S ⃗ = s ⃗ ) , u ⃗ ⊨ ( Y ∈ Y ^ ) \mathcal{M}_{do(\vec{S}=\vec{s})},\vec{u} \models(Y \in\widehat{\mathcal{Y}}) M d o ( S = s ) , u ⊨ ( Y ∈ Y ) , i.e. w u ⃗ ∗ ( Y ) ∈ Y ^ w_{\vec{u}}^*(Y) \in\widehat{\mathcal{Y}} w u ∗ ( Y ) ∈ Y . Since M \mathcal{M} M is acyclic, o ⃗ u ⃗ , s ⃗ \vec{o}_{\vec{u},\vec{s}} o u , s is the unique joint configuration consistent with u ⃗ \vec{u} u and the structural equations of M d o ( S ⃗ = s ⃗ ) \mathcal{M}_{do(\vec{S}=\vec{s})} M d o ( S = s ) . We show o ⃗ u ⃗ , s ⃗ ∈ O ^ M , d o ( S ⃗ ) ↓ ( X , Y ^ ) \vec{o}_{\vec{u},\vec{s}} \in\widehat{\mathcal{O}}^{\downarrow}_{\mathcal{M},do(\vec{S})}(X,\widehat{\mathcal{Y}}) o u , s ∈ O M , d o ( S ) ↓ ( X , Y ) for every X ∈ V ∪ U X \in\mathcal{V} \cup\mathcal{U} X ∈ V ∪ U by induction on reverse topological order (from Y Y Y upward):
Base case X = Y X=Y X = Y : By the first branch of Definition 2, O ^ ↓ ( Y ) = { o ⃗ ∈ O ^ ∣ o ⃗ Y ∈ Y ^ } \widehat{\mathcal{O}}^{\downarrow}(Y) = \{\vec{o} \in\widehat{\mathcal{O}} \mid\vec{o}_Y \in\widehat{\mathcal{Y}}\} O ↓ ( Y ) = { o ∈ O ∣ o Y ∈ Y } , and ( o ⃗ u ⃗ , s ⃗ ) Y = w u ⃗ ∗ ( Y ) ∈ Y ^ (\vec{o}_{\vec{u},\vec{s}})_Y = w_{\vec{u}}^*(Y) \in\widehat{\mathcal{Y}} ( o u , s ) Y = w u ∗ ( Y ) ∈ Y by assumption. Inductive step: Assume the claim holds for all children Z ∈ c h ( X ) ∖ S ⃗ Z \in ch(X) \setminus\vec{S} Z ∈ c h ( X ) ∖ S . By definition, O ^ ↓ ( X ) = ⋂ Z ∈ c h ( X ) ∖ S ⃗ O ^ p a ( Z , O ^ ↓ ( Z ) ) \widehat{\mathcal{O}}^{\downarrow}(X) = \bigcap_{Z \in ch(X) \setminus\vec{S}} \widehat{\mathcal{O}}^{pa(Z,\widehat{\mathcal{O}}^{\downarrow}(Z))} O ↓ ( X ) = ⋂ Z ∈ c h ( X ) ∖ S O p a ( Z , O ↓ ( Z )) . For each such Z Z Z , the inductive hypothesis gives o ⃗ u ⃗ , s ⃗ ∈ O ^ ↓ ( Z ) \vec{o}_{\vec{u},\vec{s}} \in\widehat{\mathcal{O}}^{\downarrow}(Z) o u , s ∈ O ↓ ( Z ) . Furthermore, the structural equation F Z F_Z F Z evaluated at the actual parent configuration ( o ⃗ u ⃗ , s ⃗ ) p a ( Z ) (\vec{o}_{\vec{u},\vec{s}})_{pa(Z)} ( o u , s ) p a ( Z ) produces ( o ⃗ u ⃗ , s ⃗ ) Z (\vec{o}_{\vec{u},\vec{s}})_Z ( o u , s ) Z by construction, so ( o ⃗ u ⃗ , s ⃗ ) p a ( Z ) ∈ F Z − 1 ( ( o ⃗ u ⃗ , s ⃗ ) Z ) (\vec{o}_{\vec{u},\vec{s}})_{pa(Z)} \in F_Z^{-1}((\vec{o}_{\vec{u},\vec{s}})_Z) ( o u , s ) p a ( Z ) ∈ F Z − 1 (( o u , s ) Z ) and hence o ⃗ u ⃗ , s ⃗ ∈ O ^ p a ( Z , O ^ ↓ ( Z ) ) \vec{o}_{\vec{u},\vec{s}} \in\widehat{\mathcal{O}}^{pa(Z,\widehat{\mathcal{O}}^{\downarrow}(Z))} o u , s ∈ O p a ( Z , O ↓ ( Z )) (Definition 1). The intersection over all non-intervened children yields o ⃗ u ⃗ , s ⃗ ∈ O ^ ↓ ( X ) . \vec{o}_{\vec{u},\vec{s}} \in\widehat{\mathcal{O}}^{\downarrow}(X). o u , s ∈ O ↓ ( X ) . Leaves c h ( X ) = ∅ ch(X)=\varnothing c h ( X ) = ∅ : The second branch of Definition 2 sets O ^ ↓ ( X ) = O ‾ \widehat{\mathcal{O}}^{\downarrow}(X) = \overline{\mathcal{O}} O ↓ ( X ) = O , which trivially contains o ⃗ u ⃗ , s ⃗ \vec{o}_{\vec{u},\vec{s}} o u , s . Taking the intersection over all roots R ∈ U ∪ S ⃗ R \in\mathcal{U} \cup\vec{S} R ∈ U ∪ S (Definition 3) yields o ⃗ u ⃗ , s ⃗ ∈ O ^ M , d o ( S ⃗ ) ( Y ^ ) \vec{o}_{\vec{u},\vec{s}} \in\widehat{\mathcal{O}}_{\mathcal{M},do(\vec{S})}(\widehat{\mathcal{Y}}) o u , s ∈ O M , d o ( S ) ( Y ) . □
Proof of Proposition 3 (Grammar–Graph Equivalence)
Proof. We show that the closed-form expression of Proposition 3 characterises exactly the one-step derivates of S ⃗ \vec{S} S under G M ( Y ) G_M(Y) G M ( Y ) . ( ⊇ ) (\supseteq) ( ⊇ ) Let S ⃗ ′ ′ ∈ P ( p a M V ( S ⃗ ′ ) ∪ ( S ⃗ ∖ S ⃗ ′ ) ) ∖ { ∅ } \vec{S}^{\prime\prime} \in\mathcal{P}(pa_M^{\mathcal{V}}(\vec{S}^{\prime}) \cup(\vec{S} \setminus\vec{S}^{\prime})) \setminus\{\varnothing\} S ′′ ∈ P ( p a M V ( S ′ ) ∪ ( S ∖ S ′ )) ∖ { ∅ } for some non-empty S ⃗ ′ ⊆ S ⃗ \vec{S}^{\prime} \subseteq\vec{S} S ′ ⊆ S . Set S ⃗ u n f o l d : = S ⃗ ′ \vec{S}_{\mathrm{unfold}} := \vec{S}^{\prime} S unfold := S ′ and S ⃗ k e e p : = S ⃗ ∖ S ⃗ ′ \vec{S}_{\mathrm{keep}} := \vec{S} \setminus\vec{S}^{\prime} S keep := S ∖ S ′ , so that the candidate set in (5) is p a M V ( S ⃗ ′ ) ∪ ( S ⃗ ∖ S ⃗ ′ ) pa_M^{\mathcal{V}}(\vec{S}^{\prime}) \cup(\vec{S} \setminus\vec{S}^{\prime}) p a M V ( S ′ ) ∪ ( S ∖ S ′ ) and S ⃗ ′ ′ \vec{S}^{\prime\prime} S ′′ is a non-empty subset of this candidate, hence S ⃗ ⇒ G S ⃗ ′ ′ \vec{S} \Rightarrow_G \vec{S}^{\prime\prime} S ⇒ G S ′′ , i.e. S ⃗ ′ ′ ∈ c h A ( S ⃗ ) \vec{S}^{\prime\prime} \in ch_A(\vec{S}) S ′′ ∈ c h A ( S ) . ( ⊆ ) (\subseteq) ( ⊆ ) Let S ⃗ ′ ′ ∈ c h A ( S ⃗ ) \vec{S}^{\prime\prime} \in ch_A(\vec{S}) S ′′ ∈ c h A ( S ) , i.e. S ⃗ ⇒ G S ⃗ ′ ′ \vec{S} \Rightarrow_G \vec{S}^{\prime\prime} S ⇒ G S ′′ by Definition 5, via partition S ⃗ u n f o l d ∪ ˙ S ⃗ k e e p \vec{S}_{\mathrm{unfold}} \mathbin{\dot\cup} \vec{S}_{\mathrm{keep}} S unfold ∪ ˙ S keep with S ⃗ u n f o l d ≠ ∅ \vec{S}_{\mathrm{unfold}} \ne\varnothing S unfold = ∅ . Setting S ⃗ ′ : = S ⃗ u n f o l d \vec{S}^{\prime} := \vec{S}_{\mathrm{unfold}} S ′ := S unfold in the closed-form union implies S ⃗ k e e p = S ⃗ ∖ S ⃗ ′ \vec{S}_{\mathrm{keep}} = \vec{S} \setminus\vec{S}^{\prime} S keep = S ∖ S ′ and S ⃗ ′ ′ \vec{S}^{\prime\prime} S ′′ being a non-empty subset of p a M V ( S ⃗ ′ ) ∪ ( S ⃗ ∖ S ⃗ ′ ) pa_M^{\mathcal{V}}(\vec{S}^{\prime}) \cup(\vec{S} \setminus\vec{S}^{\prime}) p a M V ( S ′ ) ∪ ( S ∖ S ′ ) . Hence, S ⃗ ′ ′ \vec{S}^{\prime\prime} S ′′ lies in the right-hand side. □
Proof of Lemma 5 (AC-Witness Identification)
Proof. (AC1): By assumption, M , u ⃗ ⊨ ( Y ∈ Y ∗ ) \mathcal{M},\vec{u} \models(Y \in\mathcal{Y}^*) M , u ⊨ ( Y ∈ Y ∗ ) . Moreover, M , u ⃗ ⊨ ( X ^ = w u ⃗ ( X ^ ) ) \mathcal{M},\vec{u} \models(\widehat{X} = w_{\vec{u}}(\widehat{X})) M , u ⊨ ( X = w u ( X )) holds trivially, since w u ⃗ w_{\vec{u}} w u is the actual world induced by u ⃗ \vec{u} u . Hence M , u ⃗ ⊨ ( X ^ = w u ⃗ ( X ^ ) ) ∧ ( Y ∈ Y ∗ ) \mathcal{M},\vec{u} \models(\widehat{X} = w_{\vec{u}}(\widehat{X})) \wedge(Y \in\mathcal{Y}^*) M , u ⊨ ( X = w u ( X )) ∧ ( Y ∈ Y ∗ ) , which is (AC1). (AC2)/(AC2 ): * By Corollary 2 , the existence of o ⃗ ∈ O ^ M , d o ( X ⃗ , Z ⃗ ) ( Y ) \vec{o} \in\widehat{\mathcal{O}}_{\mathcal{M},do(\vec{X},\vec{Z})}(\mathcal{Y}) o ∈ O M , d o ( X , Z ) ( Y ) with o ⃗ U ⃗ = u ⃗ \vec{o}_{\vec{U}} = \vec{u} o U = u and o ⃗ Z ⃗ = w u ⃗ ( Z ⃗ ) \vec{o}_{\vec{Z}} = w_{\vec{u}}(\vec{Z}) o Z = w u ( Z ) gives the existence of x ⃗ ′ ∈ X ′ \vec{x}^{\prime} \in\mathcal{X}^{\prime} x ′ ∈ X ′ such that M , u ⃗ ⊨ [ X ^ = x ⃗ ′ , Z ⃗ = w u ⃗ ( Z ⃗ ) ] ( Y ∈ Y ^ ) \mathcal{M},\vec{u} \models[\widehat{X} = \vec{x}^{\prime}, \vec{Z} = w_{\vec{u}}(\vec{Z})](Y \in\widehat{\mathcal{Y}}) M , u ⊨ [ X = x ′ , Z = w u ( Z )] ( Y ∈ Y ) . It remains to verify x ⃗ ′ ≠ w u ⃗ ( X ^ ) \vec{x}^{\prime} \ne w_{\vec{u}}(\widehat{X}) x ′ = w u ( X ) . If x ⃗ ′ = w u ⃗ ( X ^ ) \vec{x}^{\prime} = w_{\vec{u}}(\widehat{X}) x ′ = w u ( X ) , then M d o ( X ⃗ = x ⃗ ′ , Z ⃗ = w u ⃗ ( Z ⃗ ) ) , u ⃗ \mathcal{M}_{do(\vec{X}=\vec{x}^{\prime},\vec{Z}=w_{\vec{u}}(\vec{Z}))},\vec{u} M d o ( X = x ′ , Z = w u ( Z )) , u agrees with the actual setting ( M , u ⃗ ) (\mathcal{M},\vec{u}) ( M , u ) in all structural equations, so Y Y Y takes its actual value w u ⃗ ( Y ) ∈ Y ∗ w_{\vec{u}}(Y) \in\mathcal{Y}^* w u ( Y ) ∈ Y ∗ , contradicting Y ∈ Y ^ = Y ∖ Y ∗ Y \in\widehat{\mathcal{Y}} = \mathcal{Y} \setminus\mathcal{Y}^* Y ∈ Y = Y ∖ Y ∗ . Therefore x ⃗ ′ ≠ w u ⃗ ( X ^ ) \vec{x}^{\prime} \ne w_{\vec{u}}(\widehat{X}) x ′ = w u ( X ) , and ( Z ⃗ , X ^ , x ⃗ ′ , Y ∗ ) (\vec{Z},\widehat{X},\vec{x}^{\prime},\mathcal{Y}^*) ( Z , X , x ′ , Y ∗ ) constitutes a valid counterfactual witness for (AC2). For (AC2*), the same argument applies with Z ⃗ = ∅ \vec{Z} = \varnothing Z = ∅ . In both cases, ( X ^ = w u ⃗ ( X ^ ) ) (\widehat{X} = w_{\vec{u}}(\widehat{X})) ( X = w u ( X )) is a but-for or actual cause, respectively, upon applying the minimality filter (AC3). □
Counterexample to the Necessity of Proposition 4
The path-disjointness condition of Proposition 4 is sufficient but not necessary for S ⃗ ∈ A M ( Y ) \vec{S} \in\mathcal{A}_{\mathcal{M}}(Y) S ∈ A M ( Y ) . Consider the DAG with edges A → B A \to B A → B , B → X 1 B \to X_{1} B → X 1 , B → X 2 B \to X_{2} B → X 2 , X 1 → Y X_{1} \to Y X 1 → Y , X 2 → Y X_{2} \to Y X 2 → Y . The ancestor set S ⃗ = { A , B } \vec{S} = \{A, B\} S = { A , B } is reachable in A M ( Y ) \mathcal{A}_{\mathcal{M}}(Y) A M ( Y ) via the derivation
{ Y } ⇒ { X 1 , X 2 } ⇒ { B , X 2 } ⇒ { A , B } , \{Y\} \Rightarrow\{X_{1}, X_{2}\} \Rightarrow\{B, X_{2}\} \Rightarrow\{A, B\}, { Y } ⇒ { X 1 , X 2 } ⇒ { B , X 2 } ⇒ { A , B } ,
where the diamond structure allows B B B to re-enter the set after being unfolded (the last step unfolds both B B B and X 2 X_{2} X 2 , with pa ( B ) ∪ pa ( X 2 ) = { A } ∪ { B } = { A , B } \operatorname{pa}(B) \cup\operatorname{pa}(X_{2}) = \{A\} \cup\{B\} = \{A, B\} pa ( B ) ∪ pa ( X 2 ) = { A } ∪ { B } = { A , B } ). Yet every directed path from A A A to Y Y Y passes through B B B , so the path-disjointness condition fails on A A A while { A , B } ∈ A M ( Y ) \{A, B\} \in\mathcal{A}_{\mathcal{M}}(Y) { A , B } ∈ A M ( Y ) . Reachability of an ancestor set is therefore generated by a non-local sequence of grammar steps that can re-introduce intermediate variables; it is not captured by any local property of cause-to-effect path structure.
Examples
Forest-Fire Example
We use the forest-fire scenario to contrast two qualitatively different causal structures that share the same DAG but differ in the structural equation for Y Y Y . Both cases use the DAG L → Y ← A L \to Y \leftarrow A L → Y ← A with binary variables X i = { 0 , 1 } X_{i} = \{0, 1\} X i = { 0 , 1 } , independent exogenous roots U L , U A U_{L}, U_{A} U L , U A , and equations F L = U L F_{L} = U_{L} F L = U L , F A = U A F_{A} = U_{A} F A = U A . The setting u ⃗ \vec{u} u has U L = U A = 1 U_{L} = U_{A} = 1 U L = U A = 1 , so w ⃗ u ⃗ = ( L , A , Y ) = ( 1 , 1 , 1 ) \vec{w}_{\vec{u}} = (L, A, Y) = (1, 1, 1) w u = ( L , A , Y ) = ( 1 , 1 , 1 ) . We explain Y ∗ = { 1 } Y^{*} = \{1\} Y ∗ = { 1 } , hence Y ^ = { 0 } \hat{Y} = \{0\} Y ^ = { 0 } .
Example 2 (Forest fire: overdetermination and joint causes). The DAG, actual world, and witness maps for both cases are shown in Figure 4 .
Figure 4. (a) Shared DAG for the forest-fire scenario. All variables in the actual world are double-bordered as they are true ( U L , U A , L , A , Y ) = ( 1 , 1 , 1 , 1 , 1 ) (U_{L}, U_{A}, L, A, Y) = (1, 1, 1, 1, 1) ( U L , U A , L , A , Y ) = ( 1 , 1 , 1 , 1 , 1 ) . (b) Witness map for Case I (F Y = L ∨ A F_{Y} = L \lor A F Y = L ∨ A , symmetric overdetermination): singleton nodes { L } \{L\} { L } and { A } \{A\} { A } fail the node-level pre-check; only the joint node { L , A } \{L, A\} { L , A } passes. (c) Witness map for Case II (F Y = L ∧ A F_{Y} = L \land A F Y = L ∧ A , conjunctive causation): all non-root nodes pass but the joint node is non-minimal.
Case I: Overdetermination (F Y = L ∨ A F_{Y} = L \lor A F Y = L ∨ A ). Both a lightning strike (L = 1 L = 1 L = 1 ) and an arsonist (A = 1 A = 1 A = 1 ) simultaneously ignite fires, each alone sufficient to burn down the forest. Backward propagation gives O ^ d o ( ∅ ) ( { 0 } ) = { ( 0 , 0 , 0 ) } \hat{\mathcal{O}}_{do(\varnothing)}(\{0\}) = \{(0, 0, 0)\} O ^ d o ( ∅ ) ({ 0 }) = {( 0 , 0 , 0 )} ; the actual world ( 1 , 1 , 1 ) (1, 1, 1) ( 1 , 1 , 1 ) is absent.
No singleton but-for causes. At node S ⃗ = { L } \vec{S} = \{L\} S = { L } : d o ( L = 0 ) do(L = 0) d o ( L = 0 ) gives F Y = 0 ∨ 1 = 1 F_{Y} = 0 \lor1 = 1 F Y = 0 ∨ 1 = 1 , so w ⃗ u ⃗ ∗ = ( 0 , 1 , 1 ) ∉ Y ^ \vec{w}_{\vec{u}}^{*} = (0, 1, 1) \notin\hat{Y} w u ∗ = ( 0 , 1 , 1 ) ∈ / Y ^ : × \times × . The node-level pre-check (Remark 6(ii)) fails because every o ⃗ ∈ O ^ d o ( { L } ) ( { 0 } ) \vec{o} \in\hat{\mathcal{O}}_{do(\{L\})}(\{0\}) o ∈ O ^ d o ({ L }) ({ 0 }) requires U A = 0 U_{A} = 0 U A = 0 (since A = U A A = U_{A} A = U A keeps F Y = 0 ∨ 1 = 1 F_{Y} = 0 \lor1 = 1 F Y = 0 ∨ 1 = 1 unless A = 0 A = 0 A = 0 ), whereas u ⃗ \vec{u} u has U A = 1 U_{A} = 1 U A = 1 . By symmetry, S ⃗ = { A } \vec{S} = \{A\} S = { A } fails identically.
One joint actual cause. At the joint node S ⃗ = { L , A } \vec{S} = \{L, A\} S = { L , A } , both L L L and A A A are intervened, so U L U_{L} U L and U A U_{A} U A are disconnected from Y Y Y : the global target leaves the environment unconstrained and, by propagation from the intervened roots L L L and A A A , contains exactly the configurations with L = A = Y = 0 L = A = Y = 0 L = A = Y = 0 . The node-level pre-check therefore passes for any u ⃗ \vec{u} u , whereas the partition X ⃗ = { L } \vec{X} = \{L\} X = { L } , Z ⃗ = { A } \vec{Z} = \{A\} Z = { A } fails, since it would require A = w ⃗ u ⃗ ( A ) = 1 A = \vec{w}_{\vec{u}}(A) = 1 A = w u ( A ) = 1 . Partition X ⃗ = { L , A } \vec{X} = \{L, A\} X = { L , A } , Z ⃗ = ∅ \vec{Z} = \varnothing Z = ∅ : do ( L = 0 , A = 0 ) ⇒ Y = 0 ∨ 0 = 0 ∈ Y ^ \operatorname{do}(L = 0, A = 0) \Rightarrow Y = 0 \lor0 = 0 \in\hat{Y} do ( L = 0 , A = 0 ) ⇒ Y = 0 ∨ 0 = 0 ∈ Y ^ : ✓. No proper subset of { L , A } \{L, A\} { L , A } satisfies AC2, so minimality holds: ( L = 1 , A = 1 ) (L=1, A=1) ( L = 1 , A = 1 ) is the unique joint actual cause of ( Y = 1 ) (Y=1) ( Y = 1 ) . Following Halpern [16 ] (Definition 6.1.6), responsibility under the modified HP definition is ρ = 1 / ( ∣ Z ⃗ ∣ + ∣ X ⃗ ∣ ) \rho= 1/(|\vec{Z}| + |\vec{X}|) ρ = 1/ ( ∣ Z ∣ + ∣ X ∣ ) for a cause X ⃗ \vec{X} X with contingency Z ⃗ \vec{Z} Z ; here ∣ X ⃗ ∣ = 2 |\vec{X}| = 2 ∣ X ∣ = 2 , Z ⃗ = ∅ \vec{Z} = \varnothing Z = ∅ , giving ρ = 1 / 2 \rho= 1/2 ρ = 1/2 per conjunct.
Case II: Conjunctive causation (F Y = L ∧ A F_Y = L \land A F Y = L ∧ A ). Both ignition sources are now necessary. O ^ do ( ∅ ) ( { 0 } ) = { ( 0 , 0 , 0 ) , ( 1 , 0 , 0 ) , ( 0 , 1 , 0 ) } \hat{\mathcal{O}}_{\operatorname{do}(\varnothing)}(\{0\}) = \{(0, 0, 0), (1, 0, 0), (0, 1, 0)\} O ^ do ( ∅ ) ({ 0 }) = {( 0 , 0 , 0 ) , ( 1 , 0 , 0 ) , ( 0 , 1 , 0 )} ; the actual world ( 1 , 1 , 1 ) (1, 1, 1) ( 1 , 1 , 1 ) is again absent.
Two singleton but-for causes. For S ⃗ = { L } \vec{S} = \{L\} S = { L } : do ( L = 0 ) \operatorname{do}(L = 0) do ( L = 0 ) gives F Y = 0 ∧ 1 = 0 ∈ Y ^ F_Y = 0 \land1 = 0 \in\hat{Y} F Y = 0 ∧ 1 = 0 ∈ Y ^ : ✓. Symmetrically, S ⃗ = { A } \vec{S} = \{A\} S = { A } : ✓. Both singletons are minimal, so ( L = 1 ) (L=1) ( L = 1 ) and ( A = 1 ) (A=1) ( A = 1 ) are the two distinct but-for causes of ( Y = 1 ) (Y=1) ( Y = 1 ) , each with Z ⃗ = ∅ \vec{Z} = \varnothing Z = ∅ and responsibility ρ = 1 \rho= 1 ρ = 1 .
Joint node pruned by minimality. The node S ⃗ = { L , A } \vec{S} = \{L, A\} S = { L , A } also passes the pre-check, and do ( L = 0 , A = 0 ) ⇒ Y = 0 \operatorname{do}(L = 0, A = 0) \Rightarrow Y = 0 do ( L = 0 , A = 0 ) ⇒ Y = 0 : ✓. However, { L } ⊊ { L , A } \{L\} \subsetneq\{L, A\} { L } ⊊ { L , A } and { L } ∈ C \{L\} \in\mathcal{C} { L } ∈ C , so Phase 3 removes { L , A } \{L, A\} { L , A } as non-minimal.
Summary. In Case I, the unique cause is the joint conjunction ( L = 1 , A = 1 ) (L=1, A=1) ( L = 1 , A = 1 ) . In Case II, each variable is individually necessary, yielding two singleton but-for causes. In both cases the result is read off the witness map without any forward simulation over alternative values.
Billy-and-Suzy Example
Example 3 (Billy and Suzy: preemption and contingency). The Billy-and-Suzy scenario is the canonical illustration of preemption : an actual cause whose counterfactual dependence is masked by a backup process, so that a non-empty contingency set is required to reveal it. Suzy (S T = 1 ST = 1 S T = 1 ) and Billy (B T = 1 BT = 1 B T = 1 ) both throw rocks at a bottle. Suzy’s rock arrives first: her hit (S H = 1 SH = 1 S H = 1 ) shatters the bottle (B S = 1 BS = 1 B S = 1 ), preempting Billy’s rock from ever connecting (B H = 0 BH = 0 B H = 0 ).
The DAG and witness map are shown in Figure 1. The SCM has binary variables X i = { 0 , 1 } \mathcal{X}_i = \{0, 1\} X i = { 0 , 1 } , independent exogenous roots U S T , U B T U_{ST}, U_{BT} U S T , U B T , and structural equations
F S H = S T , F B H = B T ∧ ¬ S H , F B S = S H ∨ B H . F_{SH} = ST,\quad F_{BH} = BT \land\neg SH,\quad F_{BS} = SH \lor BH. F S H = S T , F B H = B T ∧ ¬ S H , F B S = S H ∨ B H .
In the setting u ⃗ \vec{u} u with U S T = U B T = 1 U_{ST} = U_{BT} = 1 U S T = U B T = 1 the actual world is
w ⃗ u ⃗ = ( S T , B T , S H , B H , B S ) = ( 1 , 1 , 1 , 0 , 1 ) . \vec{w}_{\vec{u}} = (ST, BT, SH, BH, BS) = (1, 1, 1, 0, 1). w u = ( S T , B T , S H , B H , B S ) = ( 1 , 1 , 1 , 0 , 1 ) .
We explain Y ∗ = { 1 } Y^* = \{1\} Y ∗ = { 1 } , so Y ^ = { 0 } \hat{Y} = \{0\} Y ^ = { 0 } .
Observational global targets. Backward propagation of Y ^ = { 0 } \hat{Y} = \{0\} Y ^ = { 0 } through F B S = S H ∨ B H F_{BS} = SH \lor BH F B S = S H ∨ B H requires S H = B H = 0 SH = BH = 0 S H = B H = 0 . The set O ^ do ( ∅ ) ( { 0 } ) \hat{\mathcal{O}}_{\operatorname{do}(\varnothing)}(\{0\}) O ^ do ( ∅ ) ({ 0 }) therefore contains exactly those worlds with S H = B H = 0 SH = BH = 0 S H = B H = 0 ; since w ⃗ u ⃗ \vec{w}_{\vec{u}} w u has S H = 1 SH = 1 S H = 1 , the actual world is absent, confirming that AC1 holds and the search is non-trivial.
No singleton but-for causes. All four singleton but-for tests fail: do ( S T = 0 ) \operatorname{do}(ST=0) do ( S T = 0 ) gives B H = 1 ∧ ¬ 0 = 1 BH = 1 \land\neg0 = 1 B H = 1 ∧ ¬0 = 1 , so B S = 0 ∨ 1 = 1 BS = 0 \lor1 = 1 B S = 0 ∨ 1 = 1 : ×. do ( B T = 0 ) \operatorname{do}(BT=0) do ( B T = 0 ) gives B H = 0 ∧ ¬ 1 = 0 BH = 0 \land\neg1 = 0 B H = 0 ∧ ¬1 = 0 , so B S = 1 ∨ 0 = 1 BS = 1 \lor0 = 1 B S = 1 ∨ 0 = 1 : ×. do ( S H = 0 ) \operatorname{do}(SH=0) do ( S H = 0 ) gives B H = 1 ∧ ¬ 0 = 1 BH = 1 \land\neg0 = 1 B H = 1 ∧ ¬0 = 1 , so B S = 0 ∨ 1 = 1 BS = 0 \lor1 = 1 B S = 0 ∨ 1 = 1 : ×. do ( B H = 0 ) \operatorname{do}(BH=0) do ( B H = 0 ) leaves B S = S H ∨ 0 = 1 BS = SH \lor0 = 1 B S = S H ∨ 0 = 1 : ×. Suzy’s preemption of Billy’s path, and Billy’s backup of Suzy’s, each mask the singleton counterfactual dependencies.
Four joint but-for causes. Moving to pairs in A M ( B S ) \mathcal{A}_M(BS) A M ( B S ) , the node-level pre-check (Remark 6(ii)) passes for exactly the four double-bordered nodes visible in Figure 1(b). Setting both members to 0 in each case witnesses Y ^ = { 0 } \hat{Y} = \{0\} Y ^ = { 0 } :
do ( S T = 0 , B T = 0 ) ⇒ S H = 0 , B H = 0 , B S = 0 \operatorname{do}(ST=0, BT=0) \Rightarrow SH = 0, BH = 0, BS = 0 do ( S T = 0 , B T = 0 ) ⇒ S H = 0 , B H = 0 , B S = 0 . ✓
do ( S T = 0 , B H = 0 ) ⇒ S H = 0 , B S = 0 \operatorname{do}(ST=0, BH=0) \Rightarrow SH = 0, BS = 0 do ( S T = 0 , B H = 0 ) ⇒ S H = 0 , B S = 0 . ✓
do ( S H = 0 , B T = 0 ) ⇒ B H = 0 , B S = 0 \operatorname{do}(SH=0, BT=0) \Rightarrow BH = 0, BS = 0 do ( S H = 0 , B T = 0 ) ⇒ B H = 0 , B S = 0 . ✓
do ( S H = 0 , B H = 0 ) ⇒ B S = 0 \operatorname{do}(SH=0, BH=0) \Rightarrow BS = 0 do ( S H = 0 , B H = 0 ) ⇒ B S = 0 . ✓
No pair is a strict subset of another, so all four are the four joint but-for causes of ( B S = 1 ) (BS = 1) ( B S = 1 ) .
Two actual causes via non-empty contingency. The two red-highlighted nodes in Figure 1(b), which are { S T , B H } \{ST, BH\} { S T , B H } and { S H , B H } \{SH, BH\} { S H , B H } , additionally admit singleton-cause partitions with contingency Z ⃗ = { B H } \vec{Z}=\{BH\} Z = { B H } , where w ⃗ u ⃗ ( B H ) = 0 \vec{w}_{\vec{u}}(BH)=0 w u ( B H ) = 0 .
Actual cause test for S T = 1 ST=1 S T = 1 , node S ⃗ = { S T , B H } \vec{S}=\{ST,BH\} S = { S T , B H } , partition X ⃗ = { S T } \vec{X}=\{ST\} X = { S T } , Z ⃗ = { B H } \vec{Z}=\{BH\} Z = { B H } : In M d o ( S T = 0 , B H = 0 ) \mathcal{M}_{do(ST=0,BH=0)} M d o ( S T = 0 , B H = 0 ) : S H = 0 SH=0 S H = 0 , B H = 0 BH=0 B H = 0 (fixed by contingency), B S = 0 ∨ 0 = 0 ∈ Y ^ BS=0\lor0=0\in\hat{Y} B S = 0 ∨ 0 = 0 ∈ Y ^ . Hence there exists o ⃗ ∈ O ^ d o ( { S T , B H } ) ( { 0 } ) \vec{o}\in\hat{O}_{do(\{ST,BH\})}(\{0\}) o ∈ O ^ d o ({ S T , B H }) ({ 0 }) with o ⃗ U ⃗ = u ⃗ \vec{o}_{\vec{U}}=\vec{u} o U = u and o ⃗ B H = w ⃗ u ⃗ ( B H ) \vec{o}_{BH}=\vec{w}_{\vec{u}}(BH) o B H = w u ( B H ) : ✓. Since { S T } \{ST\} { S T } is minimal, ( S T = 1 ) (ST=1) ( S T = 1 ) is an actual cause of ( B S = 1 ) (BS=1) ( B S = 1 ) with responsibility ρ = 1 / ( ∣ Z ⃗ ∣ + ∣ X ⃗ ∣ ) = 1 / 2 \rho=1/(|\vec{Z}|+|\vec{X}|)=1/2 ρ = 1/ ( ∣ Z ∣ + ∣ X ∣ ) = 1/2 .
Actual cause test for S H = 1 SH=1 S H = 1 , node S ⃗ = { S H , B H } \vec{S}=\{SH,BH\} S = { S H , B H } , partition X ⃗ = { S H } \vec{X}=\{SH\} X = { S H } , Z ⃗ = { B H } \vec{Z}=\{BH\} Z = { B H } : In M d o ( S H = 0 , B H = 0 ) \mathcal{M}_{do(SH=0,BH=0)} M d o ( S H = 0 , B H = 0 ) : B H = 0 BH=0 B H = 0 (fixed by contingency), B S = 0 ∨ 0 = 0 ∈ Y ^ BS=0\lor0=0\in\hat{Y} B S = 0 ∨ 0 = 0 ∈ Y ^ . Hence there exists o ⃗ ∈ O ^ d o ( { S H , B H } ) ( { 0 } ) \vec{o}\in\hat{O}_{do(\{SH,BH\})}(\{0\}) o ∈ O ^ d o ({ S H , B H }) ({ 0 }) with o ⃗ U ⃗ = u ⃗ \vec{o}_{\vec{U}}=\vec{u} o U = u and o ⃗ B H = w ⃗ u ⃗ ( B H ) \vec{o}_{BH}=\vec{w}_{\vec{u}}(BH) o B H = w u ( B H ) : ✓. Since { S H } \{SH\} { S H } is minimal, ( S H = 1 ) (SH=1) ( S H = 1 ) is an actual cause of ( B S = 1 ) (BS=1) ( B S = 1 ) with responsibility ρ = 1 / ( ∣ Z ⃗ ∣ + ∣ X ⃗ ∣ ) = 1 / 2 \rho=1/(|\vec{Z}|+|\vec{X}|)=1/2 ρ = 1/ ( ∣ Z ∣ + ∣ X ∣ ) = 1/2 .
Intuitively, Suzy’s throw ( S T = 1 ) (ST=1) ( S T = 1 ) and her hit ( S H = 1 ) (SH=1) ( S H = 1 ) are both actual causes: each alone, with Billy’s miss held fixed at its actual value, suffices to counterfactually explain the broken bottle. Their equal responsibilities reflect that the contingency { B H } \{BH\} { B H } is the same for both, a consequence of the preemption structure F B H = B T ∧ ¬ S H F_{BH}=BT\land\neg SH F B H = B T ∧ ¬ S H .
Why ( B T = 1 ) (BT=1) ( B T = 1 ) is not an actual cause. For every node S ⃗ ∈ A M ( B S ) \vec{S}\in\mathcal{A}_{\mathcal{M}}(BS) S ∈ A M ( B S ) containing B T BT B T and every subset X ⃗ \vec{X} X including B T BT B T with contingency Z ⃗ = S ⃗ ∖ X ⃗ \vec{Z}=\vec{S}\setminus\vec{X} Z = S ∖ X , holding Z ⃗ \vec{Z} Z at actual values and setting d o ( B T = 0 ) do(BT=0) d o ( B T = 0 ) leaves Suzy’s path S T → S H → B S ST\to SH\to BS S T → S H → B S intact. Since S H = 1 SH=1 S H = 1 in the actual world, B S = S H ∨ B H = 1 BS=SH\lor BH=1 B S = S H ∨ B H = 1 regardless of B T BT B T ’s value, and no contingency over non-Suzy variables can block this route without altering actual values. No membership test passes for any node containing B T BT B T : ( B T = 1 ) (BT=1) ( B T = 1 ) is not an actual cause, correctly reflecting that Billy’s rock never reached the bottle.
Summary. Algorithm 1 returns two actual causes, ( S T = 1 ) (ST=1) ( S T = 1 ) and ( S H = 1 ) (SH=1) ( S H = 1 ) , each with contingency Z ⃗ = { B H } \vec{Z}=\{BH\} Z = { B H } and responsibility ρ = 1 / 2 \rho=1/2 ρ = 1/2 . The four joint but-for causes and the two actual causes are read off directly from Figure 1(b) without any forward simulation over alternative values: the contingency set Z ⃗ = { B H } \vec{Z}=\{BH\} Z = { B H } is discovered automatically by the witness map traversal.
Constraint-Based Outer Approximation
As an efficient alternative to computing the exact global targets, we can track per-variable marginal subsets O ^ = { X ^ i ∣ X i ∈ U ∪ V , X ^ i ⊆ X i } \hat{\mathcal{O}}=\{\hat{\mathcal{X}}_i\mid X_i\in U\cup V,\ \hat{\mathcal{X}}_i\subseteq\mathcal{X}_i\} O ^ = { X ^ i ∣ X i ∈ U ∪ V , X ^ i ⊆ X i } , which is a collection of individual domain subsets rather than joint configurations. This yields an outer approximation of the global targets that is cheaper to compute and store, at the cost of possible false positives. We re-use the operator names O ^ M p a \hat{\mathcal{O}}^{pa}_{\mathcal{M}} O ^ M p a and O ^ M , d o ( S ⃗ ) ↓ \hat{\mathcal{O}}^{\downarrow}_{\mathcal{M},do(\vec{S})} O ^ M , d o ( S ) ↓ from Definitions 1–2 for their constraint analogues throughout this appendix; the marginal nature of the codomain is implicit in the input being a constraint collection rather than a joint set.
Definition 7 (parent constraints). For SCM M \mathcal{M} M , variable X ∈ V X\in V X ∈ V , and constraint collection O ^ \hat{\mathcal{O}} O ^ , the parent constraints O ^ M p a ( X , O ^ ) \hat{\mathcal{O}}^{pa}_{\mathcal{M}}(X,\hat{\mathcal{O}}) O ^ M p a ( X , O ^ ) are defined by marginal preimage projection:
O ^ M p a ( X , O ^ ) : = ( { ( F X − 1 ( O ^ X ) ) i ∣ X i ∈ p a ( X ) } ∪ { X j ∣ X j ∈ ( U ∪ V ) ∖ ( X ∪ p a ( X ) ) } ) ∩ O ^ , (7) \hat{\mathcal{O}}^{pa}_{\mathcal{M}}(X,\hat{\mathcal{O}}):=\left(\left\{\left(F_X^{-1}(\hat{\mathcal{O}}_X)\right)_i\mid X_i\in pa(X)\right\}\cup\left\{\mathcal{X}_j\mid X_j\in(U\cup V)\setminus(X\cup pa(X))\right\}\right)\cap\hat{\mathcal{O}}, \tag*{(7)} O ^ M p a ( X , O ^ ) := ( { ( F X − 1 ( O ^ X ) ) i ∣ X i ∈ p a ( X ) } ∪ { X j ∣ X j ∈ ( U ∪ V ) ∖ ( X ∪ p a ( X )) } ) ∩ O ^ , (7)
where ( F X − 1 ( O ^ X ) ) i : = { x i ∈ X i ∣ ∃ o ⃗ p a ∈ F X − 1 ( O ^ X ) with ( o ⃗ p a ) i = x i } \left(F_X^{-1}(\hat{\mathcal{O}}_X)\right)_i:=\{x_i\in\mathcal{X}_i\mid\exists\vec{o}_{pa}\in F_X^{-1}(\hat{\mathcal{O}}_X)\text{ with }(\vec{o}_{pa})_i=x_i\} ( F X − 1 ( O ^ X ) ) i := { x i ∈ X i ∣ ∃ o p a ∈ F X − 1 ( O ^ X ) with ( o p a ) i = x i } and ∩ \cap ∩ denotes component-wise intersection.
Definition 8 (descendant constraints). For SCM M \mathcal{M} M , target variable Y ∈ V Y\in V Y ∈ V , target Y ^ ⊆ Y \hat{\mathcal{Y}}\subseteq\mathcal{Y} Y ^ ⊆ Y , variable X ∈ V X\in V X ∈ V , and intervention set S ⃗ ⊆ V \vec{S}\subseteq V S ⊆ V , the descendant constraints O ^ M , d o ( S ⃗ ) ↓ ( X , Y ^ ) \hat{\mathcal{O}}^{\downarrow}_{\mathcal{M},do(\vec{S})}(X,\hat{\mathcal{Y}}) O ^ M , d o ( S ) ↓ ( X , Y ^ ) are:
O ^ M , d o ( S ⃗ ) ↓ ( X , Y ^ ) : = { { X i ∣ X i ∈ ( U ∪ V ) ∖ Y } ∪ { Y ^ } , if X = Y , { X i ∣ X i ∈ U ∪ V } , if c h ( X ) = ∅ , ⋂ Z ∈ c h ( X ) ∖ S ⃗ O ^ M p a ( Z , O ^ M , d o ( S ⃗ ) ↓ ( Z , Y ^ ) ) , otherwise. (8) \hat{\mathcal{O}}^{\downarrow}_{\mathcal{M},do(\vec{S})}(X,\hat{\mathcal{Y}}):=
\begin{cases}
\{\mathcal{X}_i\mid X_i\in(U\cup V)\setminus Y\}\cup\{\hat{\mathcal{Y}}\}, & \text{if }X=Y,\\
\{\mathcal{X}_i\mid X_i\in U\cup V\}, & \text{if }ch(X)=\varnothing,\\
\bigcap_{Z\in ch(X)\setminus\vec{S}}\hat{\mathcal{O}}^{pa}_{\mathcal{M}}\left(Z,\hat{\mathcal{O}}^{\downarrow}_{\mathcal{M},do(\vec{S})}(Z,\hat{\mathcal{Y}})\right), & \text{otherwise.}
\end{cases} \tag*{(8)} O ^ M , d o ( S ) ↓ ( X , Y ^ ) := ⎩ ⎨ ⎧ { X i ∣ X i ∈ ( U ∪ V ) ∖ Y } ∪ { Y ^ } , { X i ∣ X i ∈ U ∪ V } , ⋂ Z ∈ c h ( X ) ∖ S O ^ M p a ( Z , O ^ M , d o ( S ) ↓ ( Z , Y ^ ) ) , if X = Y , if c h ( X ) = ∅ , otherwise. (8)
Definition 9 (global constraints). The global constraints O ^ M , do ( S ⃗ ) c o n ( Y ^ ) : = ⋂ R ∈ U ∪ S ⃗ O ^ M , do ( S ⃗ ) ↓ ( R , Y ^ ) \widehat{O}^{\mathrm{con}}_{\mathcal{M},\operatorname{do}(\vec{S})}(\widehat{Y}) := \bigcap_{R\in\mathcal{U}\cup\vec{S}} \widehat{O}^{\downarrow}_{\mathcal{M},\operatorname{do}(\vec{S})}(R,\widehat{Y}) O M , do ( S ) con ( Y ) := ⋂ R ∈ U ∪ S O M , do ( S ) ↓ ( R , Y ) are the component-wise intersection of descendant constraints across all roots of M do ( S ⃗ ) \mathcal{M}_{\operatorname{do}(\vec{S})} M do ( S ) (Definition 3).
Remark 7 (outer approximation). The projection ( F X − 1 ( O ^ X ) ) i (F_X^{-1}(\widehat{O}_X))_i ( F X − 1 ( O X ) ) i preserves marginal feasibility but not joint feasibility: every x i ∈ ( F X − 1 ( O ^ X ) ) i x_i \in(F_X^{-1}(\widehat{O}_X))_i x i ∈ ( F X − 1 ( O X ) ) i admits some complete parent configuration o ⃗ p a \vec{o}_{\mathrm{pa}} o pa with ( o ⃗ p a ) i = x i (\vec{o}_{\mathrm{pa}})_i=x_i ( o pa ) i = x i , but the valid configurations for different parent components may be incompatible. As a consequence, the global constraints satisfy O ^ M , do ( S ⃗ ) c o n ( Y ^ ) ⊇ O ^ M , do ( S ⃗ ) ( Y ^ ) \widehat{O}^{\mathrm{con}}_{\mathcal{M},\operatorname{do}(\vec{S})}(\widehat{Y}) \supseteq\widehat{O}_{\mathcal{M},\operatorname{do}(\vec{S})}(\widehat{Y}) O M , do ( S ) con ( Y ) ⊇ O M , do ( S ) ( Y ) : they are an outer approximation of the exact global targets. False positives arise precisely when some mechanism on the path from X X X to Y Y Y has a non-product-structured preimage (e.g., XOR: F C ( A , B ) = A ⊕ B F_C(A,B)=A\oplus B F C ( A , B ) = A ⊕ B with C ^ = { 1 } \widehat{C}=\{1\} C = { 1 } gives projections A ^ = B ^ = { 0 , 1 } \widehat{A}=\widehat{B}=\{0,1\} A = B = { 0 , 1 } , yet ( 0 , 0 ) (0,0) ( 0 , 0 ) passes both checks but violates the target). For mechanisms with product-structured preimages (e.g., AND, OR, or any parent-separable function), the approximation is exact.
The global constraints can replace the global targets in Algorithm 1 as an efficient screening step for a partition ( X ⃗ , Z ⃗ ) (\vec{X},\vec{Z}) ( X , Z ) of a node S ⃗ \vec{S} S : if u ⃗ ( U ) ∉ ( O ^ M , do ( S ⃗ ) c o n ( Y ^ ) ) U \vec{u}(U)\notin(\widehat{O}^{\mathrm{con}}_{\mathcal{M},\operatorname{do}(\vec{S})}(\widehat{Y}))_U u ( U ) ∈ / ( O M , do ( S ) con ( Y ) ) U for some U ∈ U U\in\mathcal{U} U ∈ U , or w ⃗ u ⃗ ( Z j ) ∉ ( O ^ M , do ( S ⃗ ) c o n ( Y ^ ) ) Z j \vec{w}_{\vec{u}}(Z_j)\notin(\widehat{O}^{\mathrm{con}}_{\mathcal{M},\operatorname{do}(\vec{S})}(\widehat{Y}))_{Z_j} w u ( Z j ) ∈ / ( O M , do ( S ) con ( Y ) ) Z j for some Z j ∈ Z ⃗ Z_j\in\vec{Z} Z j ∈ Z , then no witness exists (sound exclusion). If all component checks pass, a forward-simulation verification M do ( X ⃗ = x ⃗ ′ , Z ⃗ = w ⃗ u ⃗ ( Z ⃗ ) ) , u ⃗ ⊨ ( Y ∈ Y ^ ) \mathcal{M}_{\operatorname{do}(\vec{X}=\vec{x}^{\prime},\vec{Z}=\vec{w}_{\vec{u}}(\vec{Z}))},\vec{u}\models(Y\in\widehat{Y}) M do ( X = x ′ , Z = w u ( Z )) , u ⊨ ( Y ∈ Y ) confirms or refutes the candidate; this step needs a candidate value x ⃗ ′ \vec{x}^{\prime} x ′ and therefore, in general, reintroduces a search over alternative values. The screen thus trades exactness for space: with D : = max i ∣ X i ∣ D:=\max_i|\mathcal{X}_i| D := max i ∣ X i ∣ , the constraint collection needs O ( ( ∣ U ∣ + ∣ V ∣ ) ⋅ D ) O((|\mathcal{U}|+|\mathcal{V}|)\cdot D) O (( ∣ U ∣ + ∣ V ∣ ) ⋅ D ) space, and a backward pass over the mechanism tables takes O ( ∣ V ∣ ⋅ D Δ + 1 ) O(|\mathcal{V}|\cdot D^{\Delta+1}) O ( ∣ V ∣ ⋅ D Δ + 1 ) time, with Δ \Delta Δ the largest number of endogenous parents (Appendix § 11 .§ 1 ), avoiding the potentially exponential joint target representation.
Full Complexity Analysis
We give the complete cost analysis of Algorithm 1 across three parameterisations of the search space. Throughout, write a : = ∣ anc M ( Y ) ∣ a:=|\operatorname{anc}_{\mathcal{M}}(Y)| a := ∣ anc M ( Y ) ∣ , D : = max i ∣ X i ∣ D:=\max_i|\mathcal{X}_i| D := max i ∣ X i ∣ , Δ : = max X ∣ pa M ( X ) ∣ \Delta:=\max_X|\operatorname{pa}_{\mathcal{M}}(X)| Δ := max X ∣ pa M ( X ) ∣ , p : = ∣ V ∣ p:=|\mathcal{V}| p := ∣ V ∣ , and o : = ∣ U ∣ o:=|\mathcal{U}| o := ∣ U ∣ .
Setup: Base Costs
Two components determine the per-node cost in Phase 2 and are shared by all three parameterisations below.
Target representation. The global targets O ^ M , do ( S ⃗ ) ( Y ^ ) \widehat{O}_{\mathcal{M},\operatorname{do}(\vec{S})}(\widehat{Y}) O M , do ( S ) ( Y ) are subsets of the joint domain O ⃗ = ∏ i X i \vec{O}=\prod_i\mathcal{X}_i O = ∏ i X i , which has cardinality ∣ O ⃗ ∣ ≤ D o + p |\vec{O}|\leq D^{o+p} ∣ O ∣ ≤ D o + p . With an explicit (enumerated) set representation, storing a single global target requires O ( D o + p ) O(D^{o+p}) O ( D o + p ) space; this is the fundamental bottleneck of exact computation and motivates the factored outer approximation of Appendix § 10 . The required preimage projections ( F X i − 1 ( x i ) ) j (F_{X_i}^{-1}(x_i))_j ( F X i − 1 ( x i ) ) j can be precomputed once in O ( p ⋅ D Δ + 1 ) O(p\cdot D^{\Delta+1}) O ( p ⋅ D Δ + 1 ) time and stored as lookup tables of total size O ( p ⋅ D Δ + 1 ) O(p\cdot D^{\Delta+1}) O ( p ⋅ D Δ + 1 ) . Phase 1 performs one bottom-up pass over the p p p endogenous variables at worst-case cost O ( p ⋅ D o + p ⋅ Δ ) O(p\cdot D^{o+p}\cdot\Delta) O ( p ⋅ D o + p ⋅ Δ ) .
Per-node target recomputation. Per-node recomputation in Phase 2 (Remark 2) costs
T t a r g e t = O ( ∣ anc M ( S ⃗ ) ∣ ⋅ ∣ O ⃗ ∣ ⋅ Δ ) ≤ O ( a ⋅ D o + p ⋅ Δ ) . T_{\mathrm{target}}=O\left(|\operatorname{anc}_{\mathcal{M}}(\vec{S})|\cdot|\vec{O}|\cdot\Delta\right)\leq O\left(a\cdot D^{o+p}\cdot\Delta\right). T target = O ( ∣ anc M ( S ) ∣ ⋅ ∣ O ∣ ⋅ Δ ) ≤ O ( a ⋅ D o + p ⋅ Δ ) .
The mechanism class modulates T t a r g e t T_{\mathrm{target}} T target substantially: for mechanisms with product-structured preimages (AND, OR, linear, monotone), the global targets factorise and T t a r g e t = O ( a ⋅ D Δ ) T_{\mathrm{target}}=O(a\cdot D\Delta) T target = O ( a ⋅ D Δ ) ; for continuous variables X i ⊆ R \mathcal{X}_i\subseteq\mathbb{R} X i ⊆ R , targets are represented implicitly (polytopes, intervals, semialgebraic sets) at cost T t a r g e t = O ( a ⋅ ρ ) T_{\mathrm{target}}=O(a\cdot\rho) T target = O ( a ⋅ ρ ) , where ρ \rho ρ is the cost of a single preimage computation: ρ = O ( p ) \rho=O(p) ρ = O ( p ) for linear mechanisms (preimage is a hyperplane), ρ = O ( 1 ) \rho=O(1) ρ = O ( 1 ) for monotone mechanisms (marginal interval arithmetic, exact via Appendix § 10 ), and ρ = O ( log ( 1 / ε ) ) \rho=O(\log(1/\varepsilon)) ρ = O ( log ( 1/ ε )) for general smooth mechanisms (bisection). In all cases the logical structure of Algorithm 1 and the guarantees of Theorem 7 are unaffected; only the membership subroutine requires adaptation to the mechanism class.
Enumeration Cost under Three Parameterisations
The three parameterisations restrict the search space of the ancestral map in qualitatively different ways; the per-node cost T t a r g e t T_{\mathrm{target}} T target from Section E.1 applies uniformly in each case.
(i) Unrestricted. The ancestral map has at most 2 a 2^a 2 a nodes. At a node S ⃗ \vec{S} S of size s s s , the algorithm tests 2 s − 1 2^s-1 2 s − 1 subsets with exactly one membership query each (Corollary 2 ). The total number of membership queries is bounded by
∑ s = 1 a ( a s ) ⋅ ( 2 s − 1 ) < ∑ s = 0 a ( a s ) ⋅ 2 s = 3 a . \sum_{s=1}^{a} \binom{a}{s}\cdot(2^s-1)<\sum_{s=0}^{a}\binom{a}{s}\cdot2^s=3^a. s = 1 ∑ a ( s a ) ⋅ ( 2 s − 1 ) < s = 0 ∑ a ( s a ) ⋅ 2 s = 3 a .
The total enumeration cost is therefore exponential in a a a in the worst case.
(ii) Bounded depth d d d . Restricting traversal to nodes reachable within d d d derivation steps from { Y } \{Y\} { Y } , the analysis of case (i) applies with a a a replaced by a d ≤ 2 Δ d a_d\leq2\Delta^d a d ≤ 2 Δ d (the number of ancestors within d d d hops for bounded in-degree Δ \Delta Δ ), yielding a membership-query bound of 3 2 Δ d 3^{2\Delta^d} 3 2 Δ d . At depth d = 1 d=1 d = 1 the search is restricted to direct parents of Y Y Y and performs at most 3 Δ 3^\Delta 3 Δ membership queries.
(iii) Bounded intervention size ∣ S ⃗ ∣ ≤ s |\vec{S}| \leq s ∣ S ∣ ≤ s . Restricting to nodes of size at most s s s yields at most ∑ k = 1 s ( a k ) = O ( a s ) \sum_{k=1}^{s}\binom{a}{k}=O(a^s) ∑ k = 1 s ( k a ) = O ( a s ) nodes, with at most 2 s − 1 2^s-1 2 s − 1 membership queries per node. For product-structured mechanisms the total cost is
O ( a s ⋅ 2 s ⋅ p ⋅ D Δ ) . O(a^s\cdot2^s\cdot p\cdot D^\Delta). O ( a s ⋅ 2 s ⋅ p ⋅ D Δ ) .
which is polynomial in p p p , a a a , and D D D for fixed s s s and Δ \Delta Δ . For continuous or general mechanism classes, substituting T t a r g e t = O ( a ⋅ ρ ) T_{\mathrm{target}}=O(a\cdot\rho) T target = O ( a ⋅ ρ ) gives the unified bound
O ( a s ⋅ 2 s ⋅ ( p ⋅ ρ + T m e m ) ) , O(a^s\cdot2^s\cdot(p\cdot\rho+T_{\mathrm{mem}})), O ( a s ⋅ 2 s ⋅ ( p ⋅ ρ + T mem )) ,
where T m e m T_{\mathrm{mem}} T mem is the cost of a single membership query. Phase 3 verification requires checking at most 2 s 2^s 2 s strict subsets per candidate.
Expected-case behaviour. The worst-case bound ∣ A M ( Y ) ∣ ≤ 2 a |\mathcal{A}_{\mathcal{M}}(Y)|\leq2^a ∣ A M ( Y ) ∣ ≤ 2 a is loose in practice: ancestor subsets violating the path-disjointness condition of Proposition 4 are typically not reached, and those that are tend to fail the node-level pre-check (Appendix § 12 (ii)) in overdetermined regimes. Empirically (Appendix § 13 , Figure 6), the combined pruning of Remark 6(ii) and (iii) eliminates on average over 97% of witness-map nodes for n ≥ 10 n\geq10 n ≥ 10 at densities d ≥ 0.5 d\geq0.5 d ≥ 0.5 and 73–94% at d = 0.25 d=0.25 d = 0.25 . Under bounded in-degree Δ \Delta Δ and bounded tree-width τ \tau τ of G M \mathcal{G}_{\mathcal{M}} G M , paths from ancestors to Y Y Y are more constrained, so fewer subsets satisfy the path-disjointness condition; while this does not change the O ( a s ) O(a^s) O ( a s ) asymptotic for case (iii), the implicit constant decreases with τ \tau τ . A formal expected-case analysis under random-DAG models is beyond the present scope.
Phase 2 Pruning Strategies
The three strategies are stated in Remark 6; we give the formal justifications here, including how each strategy behaves under continuous variable domains.
(i) Size-first traversal. Because the ancestral map A M ( Y ) \mathcal{A}_{\mathcal{M}}(Y) A M ( Y ) is a finite DAG and actual causes form an antichain under ⊆ \subseteq ⊆ (AC3), processing nodes in non-decreasing order of ∣ S ⃗ ∣ |\vec{S}| ∣ S ∣ means that whenever a cause X ⃗ ′ ∈ C \vec{X}'\in C X ′ ∈ C is confirmed, every node S ⃗ ′ \vec{S}' S ′ with X ⃗ ′ ⊆ S ⃗ ′ \vec{X}'\subseteq\vec{S}' X ′ ⊆ S ′ has not yet been processed, so strategy (iii) achieves its maximal pruning effect. This strategy operates purely on the lattice structure of the ancestral map and carries over unchanged to continuous variable domains. Cost saving. Combined with strategy (iii), size-first traversal makes Phase 3 redundant: the antichain invariant of C C C is maintained during Phase 2, eliminating the O ( ∣ C ∣ 2 ⋅ s max ) O(|C|^2\cdot s_{\max}) O ( ∣ C ∣ 2 ⋅ s m a x ) post-filter pairwise antichain comparisons (where s max = max X ⃗ ∈ C ∣ X ⃗ ∣ s_{\max}=\max_{\vec{X}\in C}|\vec{X}| s m a x = max X ∈ C ∣ X ∣ ) at zero per-query overhead. (ii) Node-level pre-check. For any non-empty partition X ⃗ ∪ Z ⃗ = S ⃗ \vec{X} \cup\vec{Z} = \vec{S} X ∪ Z = S , the existence of o ⃗ ∈ O ^ M , do ( S ⃗ ) ( Y ^ ) \vec{o} \in\widehat{O}_{M,\operatorname{do}(\vec{S})}(\hat{Y}) o ∈ O M , do ( S ) ( Y ^ ) with o ⃗ U = u ⃗ \vec{o}_{U} = \vec{u} o U = u and o ⃗ Z ⃗ = w ⃗ u ⃗ ( Z ⃗ ) \vec{o}_{\vec{Z}} = \vec{w}_{\vec{u}}(\vec{Z}) o Z = w u ( Z ) implies in particular the existence of o ⃗ ′ ∈ O ^ M , do ( S ⃗ ) ( Y ^ ) \vec{o}' \in\widehat{O}_{M,\operatorname{do}(\vec{S})}(\hat{Y}) o ′ ∈ O M , do ( S ) ( Y ^ ) with o ⃗ U ′ = u ⃗ \vec{o}'_{U} = \vec{u} o U ′ = u (taking o ⃗ ′ : = o ⃗ \vec{o}' := \vec{o} o ′ := o ). Contrapositively, failure of the latter weaker condition is a sufficient reason to skip the entire node, since no partition ( X ⃗ , Z ⃗ ) (\vec{X}, \vec{Z}) ( X , Z ) of S ⃗ \vec{S} S can pass the membership test. In redundantly overdetermined settings (e.g. F Y = A ∨ C F_{Y} = A \lor C F Y = A ∨ C with independent A = C = 1 A = C = 1 A = C = 1 ), this eliminates every root-adjacent node whose intervention set is a strict subset of p a M V ⃗ ( Y ) pa_{M}^{\vec{V}}(Y) p a M V ( Y ) , while p a M V ⃗ ( Y ) pa_{M}^{\vec{V}}(Y) p a M V ( Y ) itself typically passes the check. Cost saving. Each failed node S ⃗ \vec{S} S skips all 2 ∣ S ⃗ ∣ − 1 2^{|\vec{S}|} - 1 2 ∣ S ∣ − 1 partition queries at the cost of one membership query, a net saving of 2 ∣ S ⃗ ∣ − 2 2^{|\vec{S}|} - 2 2 ∣ S ∣ − 2 queries. Across the witness map, the Phase 2 query count drops from ∑ S ⃗ ( 2 ∣ S ⃗ ∣ − 1 ) \sum_{\vec{S}}(2^{|\vec{S}|} - 1) ∑ S ( 2 ∣ S ∣ − 1 ) to N + ∑ S ⃗ p a s s e s ( 2 ∣ S ⃗ ∣ − 1 ) N + \sum_{\vec{S}\ \mathrm{passes}}(2^{|\vec{S}|} - 1) N + ∑ S passes ( 2 ∣ S ∣ − 1 ) , where N N N is the number of pre-check failures. The savings dominate in overdetermined regimes (e.g. Forest-fire Case I in Appendix § 9 .§ 1 , where two of three non-root nodes fail the pre-check).
The pre-check remains formally valid in continuous domains; only its implementation changes, since deciding the existence of o ⃗ ∈ O ^ M , do ( S ⃗ ) ( Y ^ ) \vec{o} \in\widehat{O}_{M,\operatorname{do}(\vec{S})}(\hat{Y}) o ∈ O M , do ( S ) ( Y ^ ) with o ⃗ U = u ⃗ \vec{o}_{U} = \vec{u} o U = u becomes a real-valued feasibility problem rather than a hash-table lookup. The constraint-based outer approximation of Appendix § 10 provides an efficient and often exact screening step in all three mechanism classes: for monotone mechanisms , marginal preimage projections are closed intervals and the check reduces to component-wise interval comparisons, which are exact (Remark 7); for linear-Gaussian mechanisms , the check reduces to a single LP feasibility query; for general smooth mechanisms , bisection or gradient-based root-finding locates a witness x ⃗ ′ \vec{x}' x ′ or certifies non-existence.
(iii) Superset pruning. If X ⃗ ′ ⊊ X ⃗ \vec{X}' \subsetneq\vec{X} X ′ ⊊ X and X ⃗ ′ ∈ C \vec{X}' \in C X ′ ∈ C , then by (AC3) X ⃗ \vec{X} X cannot be minimal and would be discarded in Phase 3 regardless. Maintaining C C C as an antichain under ⊆ \subseteq ⊆ throughout Phase 2 therefore makes Phase 3 redundant when combined with strategy (i):
X ⃗ ∈ { ∅ ≠ X ⃗ ⊆ S ⃗ ∣ ∄ X ⃗ ′ ∈ C : X ⃗ ′ ⊆ X ⃗ } . \vec{X} \in\left\{\varnothing\ne\vec{X} \subseteq\vec{S} \mid\nexists\ \vec{X}' \in C : \vec{X}' \subseteq\vec{X}\right\}. X ∈ { ∅ = X ⊆ S ∣ ∄ X ′ ∈ C : X ′ ⊆ X } .
Like strategy (i), superset pruning operates purely on the antichain structure of C C C and carries over unchanged to continuous variable domains. Cost saving. For each confirmed cause X ⃗ ′ ∈ C \vec{X}' \in C X ′ ∈ C of size k k k and each later-processed node S ⃗ ⊇ X ⃗ ′ \vec{S} \supseteq\vec{X}' S ⊇ X ′ , the 2 ∣ S ⃗ ∣ − k − 1 2^{|\vec{S}|-k} - 1 2 ∣ S ∣ − k − 1 proper supersets of X ⃗ ′ \vec{X}' X ′ within S ⃗ \vec{S} S (every set extending X ⃗ ′ \vec{X}' X ′ by a non-empty subset of S ⃗ ∖ X ⃗ ′ \vec{S} \setminus\vec{X}' S ∖ X ′ ) are skipped before the membership query. The savings compound multiplicatively in regimes with many small confirmed causes.
Extended Experimental Results
Setup
All experiments use randomly generated Boolean SCMs. The causal DAG is sampled from an acyclic Erdős-Rényi model: each ordered pair of nodes is connected by a directed edge independently with probability d d d . Every structural equation F X F_{X} F X is a random AND/OR gate applied to the parents of X X X , with each parent input independently negated with probability 0.5 0.5 0.5 . We vary the number of endogenous nodes n ∈ { 3 , 4 , … , 15 } n \in\{3, 4, \ldots, 15\} n ∈ { 3 , 4 , … , 15 } and edge density d ∈ { 0.25 , 0.50 , 0.75 } d \in\{0.25, 0.50, 0.75\} d ∈ { 0.25 , 0.50 , 0.75 } , drawing 10 independent seeds per ( n , d ) (n,d) ( n , d ) configuration (390 instances in total). The target variable Y Y Y is chosen as the deepest node in the graph; the environment u ⃗ \vec{u} u is drawn uniformly at random, and target event γ ∗ = { 1 } \gamma^{*} = \{1\} γ ∗ = { 1 } is used throughout. TrAC is run with all three pruning strategies of Remark 6 implemented (size-first traversal, node-level pre-check, superset pruning). Individual runs are sequentially benchmarked on a single CPU core of an AMD Ryzen Threadripper 1900X 8-Core Processor with 32GB RAM.
Baselines. Rey et al. [29 ] identify a single cause via forward simulation with beam search and ISI by sampling alternative variable values. This method supports non-Boolean and black-box SCMs but provides no soundness or completeness guarantee. Ibrahim and Pretschner [19 ] encode the HP conditions as propositional formulae and apply three solving strategies: Brute Force (BF), SAT, and MaxSAT. These methods are restricted to Boolean SCMs. ILP/ILP-WHY strategies are excluded as they require a Gurobi licence. Both baselines target a single (minimal) cause and are not designed for full enumeration; the runtime comparison is therefore indicative rather than strictly analogous to TrAC.
Results
Cause counts. Figure 5 shows the number of actual cause sets found by TrAC per instance. The number of causes grows moderately with both n n n and d d d . Even at moderate cause counts, a principled enumeration algorithm is indispensable for downstream aggregation tasks such as responsibility and blame, as the combinatorial structure of the witness map, not the number of causes alone, drives the difficulty of complete enumeration.
Figure 5. Number of actual cause sets found by TrAC. Box-and-whisker across 10 seeds (median line, [25, 75]-IQR box, whiskers, outlier markers). The number of causes grows moderately with graph size and edge density.
Pruning effectiveness. Figure 6 reports the fraction of work eliminated by each pruning strategy of Remark 6. The node-level pre-check (strategy (ii)) is by far the most effective: at n ≥ 10 n \ge10 n ≥ 10 it prunes more than 96% of all witness-map nodes before any partition enumeration, reaching 99.98% at n = 15 n=15 n = 15 , d = 0.75 d=0.75 d = 0.75 . Superset pruning (strategy (iii)) provides additional savings at the partition level, while size-first traversal (strategy (i)) amplifies both by ensuring confirmed causes are discovered as early as possible. Together, these three strategies reduce the practical cost of Phase 2 by several orders of magnitude relative to exhaustive traversal.
TrAC standalone runtime. Figure 7 presents TrAC’s wall-clock runtime for each ( n , d ) (n,d) ( n , d ) configuration. Runtime grows with both n n n and d d d : at n = 15 n=15 n = 15 the mean ranges from 0.30 0.30 0.30 s (d = 0.25 d=0.25 d = 0.25 ) to 18 18 18 s (d = 0.50 d=0.50 d = 0.50 ) and 773 773 773 s (d = 0.75 d=0.75 d = 0.75 ), with substantial inter-seed variance at high density visible in the widening IQR bands.
Figure 7. TrAC wall-clock runtime on random Boolean SCMs. Box-and-whisker across 10 seeds per ( n , d ) (n,d) ( n , d ) cell (median line, [25, 75]-IQR box, whiskers, outlier markers). Runtime scales steeply at high density (d = 0.75 d=0.75 d = 0.75 ) due to the larger witness maps induced by denser graphs.
Worst-case runtime. Figure 8 shows the maximum runtime per ( n , d ) (n,d) ( n , d ) cell, highlighting the tail behaviour of each method. HP2SAT BF exhibits the most extreme worst cases and was excluded at n = 15 n=15 n = 15 due to exploding runtime and memory requirements. TrAC’s worst-case runtime grows with n n n and d d d but remains finite across all tested configurations.
Figure 8. Worst-case runtime comparison. Maximum observed runtime per ( n , d ) (n,d) ( n , d ) cell. HP2SAT BF was excluded at n = 15 n=15 n = 15 due to exploding runtime and memory requirements; TrAC completes every instance, with a worst-case runtime of approximately 1,600 1{,}600 1 , 600 s at n = 15 n=15 n = 15 , d = 0.75 d=0.75 d = 0.75 .
Roadmap and Open Problems
Context-specific independence and pruning. The node-level pre-check (Remark 6(ii)) has a precise algebraic interpretation that connects to context-specific independence (CSI) [7 , 33 ] . Specifically, the parent target operator (Definition 1) filters joint configurations by checking, for each child X i X_i X i along the backward path, whether the parent tuple of a configuration lies in the joint preimage F X i − 1 ( o ⃗ i ) F_{X_i}^{-1}(\vec{o}_i) F X i − 1 ( o i ) at that configuration’s child value o ⃗ i \vec{o}_i o i . The outer approximation of Appendix D relaxes this joint check to a set-level operation that tracks per-variable marginal subsets via ( F X − 1 ( O ^ X ) ) i (F_{X}^{-1}(\widehat{O}_{X}))_i ( F X − 1 ( O X ) ) i , and thereby already realises the marginal (component-wise) version of CSI-based pruning [28 ] , making the precision gap between the exact and approximate algorithms transparent (see Remark 7). A formal characterisation of the conditions under which pre-check failure coincides with graph-theoretic CSI criteria remains an open problem.
Compact representations of global targets. Global targets are subsets of the joint domain O ⃗ \vec{O} O , requiring O ( D o + p ) O(D^{o+p}) O ( D o + p ) space in the worst case. For product-structured mechanisms (AND, OR, linear, monotone), targets factorise and storage reduces to O ( p ⋅ D Δ ) O(p \cdot D^{\Delta}) O ( p ⋅ D Δ ) ; for Boolean mechanisms, binary decision diagrams (BDDs) support polynomial-time set operations (intersection, union, complement) on the target sets, though BDD size can itself be exponential in the number of variables in the worst case; for linear mechanisms, polytopes in half-space representation reduce membership to LP feasibility. A systematic characterisation of the broadest mechanism classes admitting compact representations would eliminate the exponential storage bottleneck and enable the algorithm to scale to large acyclic models.
Responsibility, blame, harm, and risk. Algorithm 1 returns all actual causes for a fixed environment u ⃗ \vec{u} u ; responsibility and blame scores [9 ] and causal harm assessments [6 ] are defined as weighted aggregates over actual causes and contingency sets, so the witness map provides precisely the missing computational substrate for these downstream quantities. Extending the algorithm to a full distribution P ( U ) P(U) P ( U ) amounts to marginalising over environments: for a fixed variable set X ⃗ \vec{X} X and value x ⃗ \vec{x} x , the probability that ( X ⃗ = x ⃗ ) (\vec{X}=\vec{x}) ( X = x ) is an actual cause of ( Y ∈ Y ∗ ) (Y \in\mathcal{Y}^{*}) ( Y ∈ Y ∗ ) equals the P ( U ) P(U) P ( U ) -measure of environments u ⃗ \vec{u} u satisfying w u ⃗ ( X ⃗ ) = x ⃗ w_{\vec{u}}(\vec{X})=\vec{x} w u ( X ) = x , M , u ⃗ ⊨ ( Y ∈ Y ∗ ) \mathcal{M},\vec{u}\models(Y \in\mathcal{Y}^{*}) M , u ⊨ ( Y ∈ Y ∗ ) , and passing the membership test for X ⃗ \vec{X} X (with some contingency Z ⃗ \vec{Z} Z ) in Phase 2 with X ⃗ \vec{X} X retained after the minimality filter of Phase 3. This probabilistic lifting connects directly to the framework of probabilistic actual causation [13 ] and to nondeterministic extensions [3 ] : in both cases the witness map structure is preserved, with the binary membership predicate replaced by a measure over the set of witnessing environments.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?
Answer: [Yes]
Justification: The paper presents a sound and complete algorithm for tracing all actual causes. Individual contributions regarding witness targets are given in § 4.1 , specifically Definitions 1–3, Theorem 1, Corollary 2. Witness maps are outlined in § 4.2 , specifically Definitions 4-6, Propositions 3-4. The Tracing Actual Causes (TrAC) algorithm is introduced in § 4.3 and Algorithm 1 with soundness and completeness proof (Theorem 7) and complexity analysis (Sec. E). Finally, experiments and baseline comparisons are presented in § 4.4 and Appendix § 13 .
Guidelines:
The answer [N/A] means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Verifying a single candidate cause under the modified Halpern–Pearl definition is D P D^{P} D P -complete [1 , 15 ] , so exponential worst-case cost is inherent to exact enumeration. Runtime and storage limitations of TrAC are analysed in § 4.3 , Appendix § 11 and the limitations paragraph of Sec. 5.
Guidelines:
The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate “Limitations” section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best
judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The paper presents a sound and complete algorithm for tracing all actual causes under the modified Halpern-Pearl definition of actual causality on acyclic SCM. (Stated in the abstract, Sec. 1 and Sec. 4). Individual definitions regarding witness targets are given in Section 4.1, Definitions 1–3, Theorem 1, Corollary 2. Witness maps are outlined in Section 4.2, specifically Definitions 4-6, Propositions 3-4. The complete Tracing Actual Causes (TrAC) algorithm is introduced in Section 4.3 and Algorithm 1 with soundness and completeness proof (Theorem 7) and complexity analysis (Sec. E).
Guidelines:
The answer [N/A] means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Experimental details on tested parameter configurations, graph and data sampling, as well as repetitions are described in Sec. 4.4 and Appendix G. All code is available at <https://github.com/MoritzWillig/tracingActualCauses>.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general, releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All code and recorded runtime results are available at https://github.com/MoritzWillig/tracingActualCauses. The included README contains all instructions to run the benchmark and plot the figures.
Guidelines:
The answer [N/A] means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results?
Answer: [Yes]
Justification: Experimental details on tested parameter configurations, graph and data sampling, as well as repetitions are described in Sec. 4.4 and Appendix G. Baselines algorithms are tested as provided by their respective code repositories.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Each ( n , d ) (n,d) ( n , d ) configuration is evaluated on 10 independently sampled instances (random graph, structural equations and environment), so the reported variability is across instances. Figure 3 and Figure 6 show the mean with [25, 75]-IQR bands, Figure 7 and Figure 5 box-and-whisker plots (median, IQR, whiskers, outliers), and Figure 8 the worst case per configuration.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).
If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: Sec. G describes the hardware of a single AMD Ryzen Threadripper 1900X 8-Core PC with 32GB RAM (no GPU required). Runtime comparisons to baselines, individual repetition runtimes and worst-case runtimes for TrAC are reported in Figure 3 , Figure 7 and Figure 8 .
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics [https://neurips.cc/public/EthicsGuidelines]?
Answer: [Yes]
Justification: The research is purely theoretical/methodological. It involves no human subjects, no personally identifiable information or sensitive data. Experiments are conducted exclusively on synthetic data (randomly sampled causal graphs), and illustrative examples are standard, well-established toy scenarios from the causal inference literature (rock-throwing, forest fires). We anticipate no direct ethical concerns, risks of discrimination or privacy violation arising from this work.
Guidelines:
The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer [No], they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Actual causation underpins definitions of legal responsibility, moral blame, and the assessment of causal harm. Previous works in this area primarily focused on finding single smallest cause sets, blocking these tasks that either depend on finding all actual causes in a given setting or assume a particular case was already established apriori. By enumerating all actual causes, TrAC may thus advance reasoning in all of these areas. Conversely, automated cause enumeration could be misused to attribute blame or responsibility mechanically; its output is only as reliable as the specified causal model, and conclusions drawn from a misspecified model can be misleading. TrAC should therefore support, not replace, human judgement. Relevant discussions are included in the abstract, introduction and Appendix H.
Guidelines:
The answer [N/A] means that there is no societal impact of the work performed.
If the authors answer [N/A] or [No], they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?
Answer: [N/A].
Justification: Experiments are on purely synthetic data. Guidelines:
The answer [N/A] means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The baselines of Reyd et al. [29 ] (actualcauses, MIT licence) and Ibrahim and Pretschner [19 ] (HP2SAT1.0, MIT licence) are cited in the paper and used unchanged under their licences; their code is referenced in our repository. All other code was written by the authors with the help of coding agents.
Guidelines:
The answer [N/A] means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset’s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The structure and license of the accompanying code repository, as well as the required commands for running experiments and plotting results are described in the README of the repository. All code is released under MIT license.
Guidelines:
The answer [N/A] means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [N/A]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [N/A]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required.
Answer: [N/A]
Justification: LLMs have only been used for writing, editing, and formatting of the paper and code in a way that does not impact the originality, rigor or core methodology of the paper.
Guidelines:
The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.