betaFeedback

WorksComputer Science

Tracing Actual Causes with Counterfactual Witness Maps

Abstract

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.

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 D1PD_1^P-complete [1, 15], vs. Σ2P\Sigma_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.

DAG of the Billy and Suzy example and witness map

Figure 1. (a) The DAG of the Billy and Suzy example. The actual world is (ST,BT,¬BH,SH,BS)(ST, BT, \neg BH, SH, BS) with environment (UST,UBT)(U_{ST}, U_{BT}) (True variables are double-bordered). (b) The witness map (Definition 6) for the counterfactual target ¬BS\neg 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\neg BH) are highlighted in red. Thus we have two actual causes ST(=1)ST(=1) and SH(=1)SH(=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 (ST=1,BT=1ST=1,BT=1): Suzy Hits (SH=1SH=1), but Billy does not hit (BH=0BH=0) due to Suzy hitting first. The bottle shatters (BS=1BS=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,PU⟩\mathcal{M} = \langle\mathbf{U}, \mathbf{V}, \mathcal{F}, \mathbb{P}_{\mathbf{U}} \rangle with a set of exogenous variables U={X1,…,Xo}\mathbf{U} = \{X_1, \ldots, X_o\} and a set of endogenous variables V={Xo+1,…,Xo+p}\mathbf{V} = \{X_{o+1}, \ldots, X_{o+p}\} with full configurations O=U∪V\mathbf{O} = \mathbf{U} \cup\mathbf{V} and values o⃗∈O⃗=U⃗×V⃗=∏i=1o+pXi\vec{o} \in\vec{\mathcal{O}} = \vec{\mathcal{U}} \times\vec{\mathcal{V}} = \prod_{i=1}^{o+p} \mathcal{X}_i, a set of structural equations F={X=FX:X∈V}\mathcal{F} = \{X = F_X : X \in\mathbf{V}\} with functions FX:Xpa⁡(X)→XXF_X : \mathcal{X}_{\operatorname{pa}(X)} \to\mathcal{X}_X and a distribution PU\mathbb{P}_{\mathbf{U}} of the exogenous variables. Assignments u⃗:U→⋃Xi∈UXi\vec{u} : \mathbf{U} \to\bigcup_{X_i \in\mathbf{U}} \mathcal{X}_i of (all) exogenous variables are called environments of M\mathcal{M} and assignments w⃗:V→⋃Xi∈VXi\vec{w} : \mathbf{V} \to\bigcup_{X_i \in\mathbf{V}} \mathcal{X}_i of (all) endogenous variables are called worlds of M\mathcal{M}. A pair (M,u⃗)(\mathcal{M}, \vec{u}) is called a setting and the actual world w⃗u⃗\vec{w}_{\vec{u}} of a specific setting (M,u⃗)(\mathcal{M}, \vec{u}) is induced by the evaluation of structural equations in F\mathcal{F}. For an assignment X⃗=x⃗\vec{X} = \vec{x} with X⃗⊆V\vec{X} \subseteq\mathbf{V}, the intervened SCM Mdo(X⃗=x⃗)\mathcal{M}_{do(\vec{X}=\vec{x})} is obtained from M\mathcal{M} by replacing every structural equation FXiF_{X_i} with the constant xix_i (for Xi∈X⃗X_i \in\vec{X}); its actual world under u⃗\vec{u} is denoted w⃗u⃗∗\vec{w}^{*}_{\vec{u}} and called counterfactual when w⃗u⃗∗≠w⃗u⃗\vec{w}^{*}_{\vec{u}} \ne\vec{w}_{\vec{u}}. The corresponding modal operator satisfies M,u⃗⊨[X⃗=x⃗]φ⟺Mdo(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.

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}) we say that the event (X⃗=x⃗)(\vec{X} = \vec{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 (AC1), there exists x⃗′∈X\vec{x}' \in\mathcal{X} with M,u⃗⊨[X⃗=x⃗′]¬φ\mathcal{M}, \vec{u} \models[\vec{X} = \vec{x}']\neg\varphi (AC2*), and X⃗=x⃗\vec{X} = \vec{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}) 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 (Xi=xi)(X_i = x_i) for Xi∈X⃗X_i \in\vec{X} are referred to as parts of the cause (X⃗=x⃗)(\vec{X} = \vec{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} and Z⃗⊆V∖X⃗\vec{Z} \subseteq\mathbf{V} \setminus\vec{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 (AC2), and X⃗=x⃗\vec{X} = \vec{x} is a smallest conjunction of atomic events satisfying AC1 and that condition, then X⃗=x⃗\vec{X} = \vec{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.

References

  1. [1]G. Aleksandrowicz, H. Chockler, J. Y. Halpern, and A. Ivrii. The computational complexity of structure-based causality. Journal of Artificial Intelligence Research, 58:431–451, 2017.
  2. [2]S. Beckers. Causal sufficiency and actual causation. Journal of Philosophical Logic, 50(6): 1341–1374, 2021.arxiv.org/abs/2102.02311
  3. [3]S. Beckers. Actual causation and nondeterministic causal models. In Proceedings of the Fourth Conference on Causal Learning and Reasoning, volume 275 of Proceedings of Machine Learning Research, pages 514–532. PMLR, 2025.arxiv.org/abs/2503.07849
  4. [4]S. Beckers and J. Vennekens. A general framework for defining and extending actual causation using cp-logic. International Journal of Approximate Reasoning, 77:105–126, 2016.DOI
  5. [5]S. Beckers, H. Chockler, and J. Y. Halpern. Quantifying harm. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI), pages 363–371, 2023. doi: 10.24963/ijcai.2023/41.DOI
  6. [6]S. Beckers, H. Chockler, and J. Y. Halpern. A causal analysis of harm. Minds and Machines, 34 (3):34, 2024. doi: 10.1007/s11023-024-09689-7.DOI
  7. [7]C. Boutilier, N. Friedman, M. Goldszmidt, and D. Koller. Context-specific independence in bayesian networks. In Proc. of the 13th Conf. on Uncertainty in Artificial Intelligence, 1996.
  8. [8]K. Budhatoki, L. Minorics, P. Blöbaum, and D. Janzing. Causal structure-based root cause analysis of outliers. In International conference on machine learning, pages 2357–2369. PMLR, 2022.
  9. [9]H. Chockler and J. Y. Halpern. Responsibility and blame: A structural-model approach. Journal of Artificial Intelligence Research, 22:93–115, 2004.
  10. [10]H. Chockler and J. Y. Halpern. Explaining image classifiers. In Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 264–272, 2024.arxiv.org/abs/2401.13752
  11. [11]F. Cushman, J. Knobe, and W. Sinnott-Armstrong. Moral appraisals affect doing/allowing judgments. Cognition, 108(1):281–289, 2008.DOI
  12. [12]T. Eiter and T. Lukasiewicz. Complexity results for structure-based causality. Artificial Intelligence, 142(1):53–89, 2002.DOI
  13. [13]L. Fenton-Glynn. A proposed probabilistic extension of the Halpern and Pearl definition of ‘Actual Cause’. The British Journal for the Philosophy of Science, 68(4):1061–1124, 2017.
  14. [14]S. Galhotra, R. Pradhan, and B. Salimi. Explaining black-box algorithms using probabilistic contrastive counterfactuals. In Proceedings of the 2021 international conference on management of data, pages 577–590, 2021.arxiv.org/abs/2103.11972
  15. [15]J. Y. Halpern. A modification of the Halpern-Pearl definition of causality. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, pages 3022–3033, 2015.DOI
  16. [16]J. Y. Halpern. Actual Causality. MIT Press, 2016.
  17. [17]J. Y. Halpern and J. Pearl. Causes and explanations: A structural-model approach. Part I: Causes. The British Journal for the Philosophy of Science, 56(4):843–887, 2005.
  18. [18]T. Heskes, E. Sijben, I. G. Bucur, and T. Claassen. Causal shapley values: Exploiting causal knowledge to explain individual predictions of complex models. Advances in neural information processing systems, 33:4778–4789, 2020.arxiv.org/abs/2011.01625
  19. [19]A. Ibrahim and A. Pretschner. From checking to inference: Actual causality computations as optimization problems. In International Symposium on Automated Technology for Verification and Analysis, pages 343–359. Springer, 2020.DOI
  20. [20]A. Ikram, S. Chakraborty, S. Mitra, S. Saini, S. Bagchi, and M. Kocaoglu. Root cause analysis of failures in microservices through causal discovery. Advances in Neural Information Processing Systems, 35:31158–31170, 2022.DOI
  21. [21]D. Janzing, L. Minorics, and P. Blöbaum. Feature relevance quantification in explainable AI: A causal problem. In International Conference on artificial intelligence and statistics, pages 2907–2916. PMLR, 2020.arxiv.org/abs/1910.13413
  22. [22]A.-H. Karimi, G. Barthe, B. Schölkopf, and I. Valera. A survey of algorithmic recourse: contrastive explanations and consequential recommendations. ACM Computing Surveys, 55(5):1–29, 2022.DOI
  23. [23]M. Kim, R. Sumbaly, and S. Shah. Root cause detection in a service-oriented architecture. ACM SIGMETRICS Performance Evaluation Review, 41(1):93–104, 2013.
  24. [24]S. M. Lundberg and S.-I. Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017.arxiv.org/abs/1705.07874
  25. [25]M. S. Moore. Causation and Responsibility: An Essay in Law, Morals, and Metaphysics. Oxford University Press, 2009.
  26. [26]R. K. Mothilal, A. Sharma, and C. Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pages 607–617, 2020.DOI
  27. [27]J. Pearl. Causality. Cambridge University Press, 2009.
  28. [28]J. Pensar, H. Nyman, T. Koski, and J. Corander. Labeled directed acyclic graphs: a generalization of context-specific independence in directed graphical models. Data mining and knowledge discovery, 29(2):503–533, 2015.DOI
  29. [29]S. Reyd, A. Diaconescu, and J.-L. Dessalles. Searching for actual causes: Approximate algorithms with adjustable precision. In NeurIPS 2025 Workshop on CauScien: Uncovering Causality in Science, 2025.arxiv.org/abs/2507.07857
  30. [30]S. Wachter, B. Mittelstadt, and C. Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harvard Journal of Law & Technology, 31(2):841–887, 2018.
  31. [31]W. Yang, K. Zhang, and S. C. Hoi. A causal approach to detecting multivariate time-series anomalies and root causes. arXiv preprint arXiv:2206.15033, 2022.arxiv.org/abs/2206.15033
  32. [32]M. Zečević, D. S. Dhami, and K. Kersting. Causal articulation theory (cat): Articulating static and temporal causal models beyond llm rationalizations. In Fifth Conference on Causal Learning and Reasoning, 2026.
  33. [33]N. L. Zhang and D. Poole. On the role of context-specific independence in probabilistic inference. In IJCAI, volume 99, pages 1288–1293, 1999.

Paper details

vlnc:W_yerdjn68
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents