TL;DR
This paper introduces TrAC (Tracing Actual Causes), the first algorithm capable of finding all actual causes of an event in a causal model with a guarantee of soundness and completeness. By shifting from a forward search of alternative values to a backward propagation of "witness targets," the authors transform a complex existential search into a series of efficient set-membership queries.
What Problem Does This Paper Address?
In causal inference, "actual causation" asks: What specifically caused this outcome in this exact situation? For example, if both Suzy and Billy throw rocks at a bottle, but Suzy's rock hits first, Suzy is the actual cause, even though the bottle would have shattered anyway if she had missed (preemption).
While the Halpern-Pearl (HP) framework provides a rigorous logical definition for actual causation, finding these causes computationally is hard. Existing algorithms typically only find the "smallest" cause or use heuristics that don't guarantee they've found everything. This is a major bottleneck for downstream tasks like legal responsibility attribution or moral blame assessment, which require knowing the full set of causes to calculate accurate scores.
Methods
The authors propose a three-part solution to move from logical definitions to a practical enumeration algorithm:
- Witness Targets: Instead of iterating through all possible alternative values for variables (forward simulation), they propagate the "counterfactual target" (the outcome we wanted to avoid) backward through the structural equations. This identifies the exact configurations of variables that would have changed the outcome. This converts the "existence" check in the HP definition into a simple set-membership query.
- Ancestor Intervention Grammar: They define a formal grammar to systematically explore candidate intervention sets. By "unfolding" variables into their parents or "keeping" them, the grammar generates a finite Directed Acyclic Graph (DAG) called an Ancestral Map.
- The TrAC Algorithm: Combining these, TrAC traverses the Witness Map (the ancestral map annotated with witness targets). It identifies candidate causes, checks them against the precomputed targets, and finally filters for minimality to satisfy the HP conditions.
Datasets
The authors evaluated TrAC using randomly generated Boolean Structural Causal Models (SCMs).
- Graph Structure: Acyclic Erdős-Rényi DAGs with 3 to 15 nodes.
- Edge Densities: $p \in \{0.25, 0.50, 0.75\}$.
- Mechanisms: Random AND/OR gates with independently negated inputs.
- Baselines: They compared TrAC against existing single-cause solvers (Ibrahim & Pretschner) and approximate search methods (Reyd et al.).
Key Insights and Ideas
- Backward is Better: The "aha moment" is realizing that backward propagation of constraints is far more efficient than forward sampling of values. It eliminates the dependence on the size of variable domains during the verification step.
- The Power of Pruning: While the search space is theoretically exponential, the authors introduced several pruning strategies (size-first traversal, node-level pre-checks, and superset pruning) that eliminate over 97% of the search space in many practical scenarios.
- Structural Admissibility: The grammar ensures that the algorithm only tests "structurally admissible" sets—those that actually have a path to the target event—drastically reducing the number of candidates compared to a brute-force subset search.
Key Results
- Completeness: TrAC is the first exact method to provably enumerate all actual causes, whereas previous exact methods only returned the single smallest cause.
- Efficiency: Despite solving a harder problem (full enumeration vs. single cause), TrAC is typically more than an order of magnitude faster than brute-force search.
- Scalability: The algorithm demonstrated practical feasibility for causal graphs of up to 15 nodes on standard hardware (32GB RAM). Beyond 15 nodes, memory becomes the primary bottleneck due to the storage requirements for exact global targets.
Limitations and Future Work
- Memory Bottleneck: Storing exact "global targets" requires space that grows exponentially with the number of variables and their domain sizes. The authors suggest using more compact representations like Binary Decision Diagrams (BDDs) or polytopes in the future.
- Model Scope: TrAC currently requires a fully specified, acyclic SCM. It does not yet handle latent confounders (unobserved common causes) or models with cyclic dependencies.
- Probabilistic Extension: The current work is deterministic. Extending this to probabilistic actual causation (where we have a distribution over environments) is a logical next step, which would involve marginalizing the witness map over different possible worlds.
For more details, you can find the full paper and code at https://github.com/MoritzWillig/tracingActualCauses.
Summary updated