Model Checking Causality

Tiago de Lima, Emiliano LoriniIJCAI 2024

Introduction

The field of Explainable AI (XAI) currently faces a divide between two primary approaches to causal reasoning: the logic-based Prime Implicant (PI) family and the intervention-based Causal Intervention (CI) family. The PI-family focuses on finding sufficient conditions for an outcome, while the CI-family utilizes Structural Equation Models (SEMs) to determine "actual cause" through counterfactual analysis. This paper bridges this gap by introducing a unified modal logic framework, $\mathcal{L}_{ICN}$, designed for the formal verification of causal explanations.

Methodology: The $\mathcal{L}_{ICN}$ Framework

The authors propose a novel representation of causal information using "causal bases"—sets of propositional formulas that define variable relationships. Unlike traditional SEMs, causal bases can naturally represent incomplete information and avoid rigid distinctions between endogenous and exogenous variables.

The core of the framework is the modal operator $\Box^\pi \phi$, representing conditional causal necessity: "After performing causal change $\pi$, $\phi$ is necessarily true." These changes include both expansions (adding rules) and retractions (removing rules), allowing the logic to express complex "what-if" scenarios.

A causal graph illustrating dependencies between literature review ($lt$), high quality ($hq$), review ($re$), and final acceptance ($ac$) in a collaborative writing scenario.

To facilitate algorithmic verification, the model-checking problem for $\mathcal{L}_{ICN}$ is reduced to solving Quantified Boolean Formulas (QBF). This reduction allows the system to leverage state-of-the-art QBF solvers and Binary Decision Diagrams (BDDs) for efficient computation.

Experimental Evaluation and Results

The framework was evaluated using classic causal puzzles, such as the "Suzy and Billy" preemption problem, and synthetic benchmarks designed to test scalability. The implementation, a symbolic model checker written in Haskell, demonstrates significant efficiency even as the state space grows exponentially.

Performance results for the symbolic model checker, showing execution times for state spaces up to $10^{79}$ states.

As shown in the table above, the checker handles a model with 3 agents (4,096 states) in 0.0866 seconds. Remarkably, for a massive configuration with 256 agents and approximately $9.93 \times 10^{79}$ states, the execution time remains under 6 seconds (5.3242s). This suggests that while the general problem is in PSPACE, practical causal queries—often limited in modal depth—are highly tractable.

Conclusion and Future Work

This research provides a robust mathematical foundation for unifying abductive and interventionist explanations. By formalizing Halpern & Pearl’s "actual cause" within a modal logic, the authors enable the use of formal verification tools in XAI. Future work will focus on extending the logic to handle cyclic causal graphs and integrating the model checker with real-world "black-box" AI systems to provide provably correct explanations.

Summary updated

BibTeX
@inproceedings{lima2024model,
  author = {Tiago de Lima and Emiliano Lorini},
  title = {{Model Checking Causality}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure