Tracing Actual Causes with Counterfactual Witness Maps
Authors: Tim Woydt, Matej Zečević, Kristian Kersting, Moritz Willig
Organizations: Department of Computer Science, Technical University of Darmstadt · Hessian Center for AI (hessian.AI) · German Research Center for AI (DFKI)
Halpernian actual causation, the formal study of which events in a specific situation caused a specific outcome in acyclic structural causal models, underpins legal responsibility, moral blame, and the assessment of causal harm. Despite the rich logical framework, no prior sound and complete enumeration procedure is known for finding all actual causes in a given setting, blocking downstream tasks such as responsibility attribution, blame assessment, and causal-harm grading that aggregate over the full cause set. We close this gap by introducing witness targets: sets of joint configurations containing every counterfactual witness. In combination with an ancestor intervention grammar we derive a finite directed acyclic witness map. We prove that for every actual cause there exists a contingency set such that the joint intervention set appears as a node of this map, and present an algorithm for Tracing Actual Causes (TrAC) that is sound and complete for enumerating all actual causes of any target event. We compare TrAC empirically with existing single-cause baselines on random Boolean structural causal models, demonstrating practical feasibility for graphs of up to 15 nodes.
Figures & tables
Figure 1: (a) The DAG of the Billy and Suzy example. The actual world is (ST,BT,¬BH,SH,BS) with environment (UST,UBT) (True variables are double-bordered). (b) The witness map (Definition 6 ) for the counterfactual target ¬BS 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 ( ¬BH ) are highlighted in red. Thus we have two actual causes ST(=1) and SH(=1) . See Example 3 for details. (Best viewed in color.)
Figure 2: (a) Example DAG with pa(Y)={A,C} , pa(C)={B} , pa(B)={A} . (b) Ancestral map AM(Y) (Definition 5 ): the root’s children are the non-empty subsets of paMV(Y) ; the children of every other node follow from Proposition 3 . Node {A,C} has four children, {A} , {B} , {C} and {A,B} (Example 1 ).
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} nodes & edge density d∈{41,21,43} ; structural equations are random AND/OR gates with independently negated inputs. (Best viewed in color.)
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Symbol
Meaning
Variables and subsets
V,U
sets of endogenous, exogenous variables
O=U∪V
set of all variables (full configurations)
X,Y,Xi
single variables
X,Z,S
arbitrary subsets of V ( Z used as contingency, S as intervention/node)
pa(X),ch(X),anc(X)
parents, children, ancestors of X ( paMV,ancMV restricted to endogenous)
Appendix
Table 1: Notation summary.
Figure 4: (a) Shared DAG for the forest-fire scenario. All variables in the actual world are double-bordered as they are true (UL,UA,L,A,Y)=(1,1,1,1,1) . (b) Witness map for Case I ( FY=L∨A , symmetric overdetermination): singleton nodes {L} and {A} fail the node-level pre-check; only the joint node {L,A} passes. (c) Witness map for Case II ( FY=L∧A , conjunctive causation): all non-root nodes pass but the joint node is non-minimal.
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.
Figure 6: Pruning rates. Fraction of witness-map nodes eliminated by each strategy (mean ±[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 at d≥0.5 , and 73 – 94% at d=0.25 .
Figure 7: TrAC wall-clock runtime on random Boolean SCMs. Box-and-whisker across 10 seeds per (n,d) cell (median line, [25,75] -IQR box, whiskers, outlier markers). Runtime scales steeply at high density ( d=0.75 ) due to the larger witness maps induced by denser graphs.
Figure 8: Worst-case runtime comparison. Maximum observed runtime per (n,d) cell. HP2SAT BF was excluded at n=15 due to exploding runtime and memory requirements; TrAC completes every instance, with a worst-case runtime of approximately 1,600s at n=15 , d=0.75 .
Fault trees are a widely used as effective risk models for complex systems, answering the question "what can go wrong?", especially through minimal cut set analysis. We study fault trees from the perspective of Halpern & Pearl's theory of actual causality. This allows us to use fault trees to answer the question "why has it gone wrong?", which is fundamental to failure diagnostics. We give a complete classification of each of the different notions of actual causality in terms of the fault tree's graph structure and logical structure, and show how minimal cut sets give rise to actual causes.
Georgiana Caltais, Milan Lopuhaä-Zwakenberg, Mariëlle Stoelinga
University of Twente, The Netherlands · Radboud University, The Netherlands
Explaining why a specific outcome occurred, and which inputs deserve the blame or credit, is central to philosophical, scientific, and policy analysis. Existing tools split into two camps. The theory of actual causality (AC) gives principled verdicts, but only for toy-sized models, because computing them requires enumerating counterfactual scenarios. Scalable attribution methods like SHAP (or even causal SHAP) at least partially ignore the causal structure that generated the data, and can give answers that conflict with a careful causal analysis. We close this gap with Probabilistic Causal Impact (PCI). PCI builds on actual causality and on Pearl's notions of probability of necessity and sufficiency, but recasts the question of explainability as an estimation problem on a probabilistic causal model that is easily approximated via Monte Carlo. By specifying a distribution over "candidate explanations," a distribution over counterfactual values, and a scoring function, PCI provides tractable, causally grounded, graded explanations, generalizing AC and Pearl's probability of causation as degenerate cases. We evaluate PCI in synthetic and real-world examples, spanning consistency checks with AC, scaling experiments, complex continuous-valued dynamical systems, and a real-world deployed causal machine learning model trained on millions of datapoints.
Rafal Urbaniak, Sam Witty, Daniel Waxman +7
Basis Research Institute · Sorbus AI · Massachusetts Institute of Technology +3
Counterfactual explanation in abstract argumentation calls for an answer to the what-if query: would the topic argument still be accepted if the status of certain other arguments were changed? Existing approaches are limited to the but-for test and fail to accommodate more refined counterfactual conditions. To overcome these limitations, we introduce an intervention-based counterfactual reasoning framework in abstract argumentation. Our approach encodes the acceptance conditions of arguments as equations, then defines an intervention operator that supports (1) changing sets of arguments simultaneously, and (2) fixing witness arguments to their actual labels. Guided by the refined counterfactual condition introduced in the Halpern-Pearl definition, our method goes beyond the but-for test, thereby correctly identifying causes in argumentation structures such as Preemption and Overdetermination. Through comparison, we show that our method surpasses prior methods in both expressiveness and reliability.