# Searching for Actual Causes: Approximate Algorithms with Adjustable Precision

arXiv: https://arxiv.org/abs/2507.07857 · HTML: https://mlsanity.com/paper/2507.07857/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 59 references that are in the map.
- First posted on arXiv 10 Jul 2025.

## Builds on (most cited first, 19 of 19)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [Causality matters in medical imaging](https://mlsanity.com/paper/1912.08142/) (2019)
- [Explainable Reinforcement Learning Through a Causal Lens](https://mlsanity.com/paper/1905.10958/) (2019)
- [Algorithmic recourse under imperfect causal knowledge: a probabilistic approach](https://mlsanity.com/paper/2006.06831/) (2020)
- [CXPlain: Causal Explanations for Model Interpretation under Uncertainty](https://mlsanity.com/paper/1910.12336/) (2019)
- [Causal Interpretability for Machine Learning -- Problems, Methods and Evaluation](https://mlsanity.com/paper/2003.03934/) (2020)
- [Contrastive Explanation: A Structural-Model Approach](https://mlsanity.com/paper/1811.03163/) (2018)
- [Counterfactuals and Causability in Explainable Artificial Intelligence: Theory, Algorithms, and Applications](https://mlsanity.com/paper/2103.04244/) (2021)
- [A Modification of the Halpern-Pearl Definition of Causality](https://mlsanity.com/paper/1505.00162/) (2015)
- [Causal Sufficiency and Actual Causation](https://mlsanity.com/paper/2102.02311/) (2021)
- [Graded Causation and Defaults](https://mlsanity.com/paper/1309.1226/) (2013)
- [The Computational Complexity of Structure-Based Causality](https://mlsanity.com/paper/1412.3076/) (2014)
- [Deep Backtracking Counterfactuals for Causally Compliant Explanations](https://mlsanity.com/paper/2310.07665/) (2023)
- [Actual Causality and Responsibility Attribution in Decentralized Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2204.00302/) (2022)
- [From Checking to Inference: Actual Causality Computations as Optimization Problems](https://mlsanity.com/paper/2006.03363/) (2020)
- [Automated Discovery of Functional Actual Causes in Complex Environments](https://mlsanity.com/paper/2404.10883/) (2024)
- [Efficient Discovery of Actual Causality using Abstraction-Refinement](https://mlsanity.com/paper/2407.16629/) (2024)

## Built on by (most cited first, 1 of 1)

- [Computing Actual Causes for Neural Network Predictions under Structured Causal Inputs](https://mlsanity.com/paper/2608.03772/) (2026)

## Abstract (arXiv)

Causality has gained increasing attention in recent years, notably for improving the interpretability of machine learning models. Yet the field of explainable artificial intelligence (XAI) has been criticized for emphasizing general tendencies rather than the situation-specific facts, which users typically expect as explanations. These expectations align with the notion of actual causes, which identify what made the observed outcome happen, in the specific context at hand. Halpern and Pearl provided a formal basis for actual causation, but identifying actual causes is NP-complete. Practical identification algorithms are extremely scarce, restricted to narrow classes of models, and typically identify only the shortest cause. We address this gap between the formal theory and its applicability through two main contributions. First, we introduce a baseline approximate polynomial-time algorithm with adjustable precision, together with two complementary algorithms that improve its efficiency. Second, we provide a theoretical result showing that the actual-cause identification problem can be decomposed into smaller sub-instances that preserve the set of solutions. This result directly motivates one of the complementary algorithms. Our experiments demonstrate that the baseline method can approximate the set of actual causes, notably for non-Boolean and stochastic models, and that the complementary algorithms further improve its performance in most cases.