# Efficient Computation of Counterfactual Bounds

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 41 references that are in the map.
- First posted on arXiv 17 Jul 2023.

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

- [Causality for Machine Learning](https://mlsanity.com/paper/1911.10500/) (2019)
- [Counterfactual Probabilities: Computational Methods, Bounds and Applications](https://mlsanity.com/paper/1302.6784/) (2013)
- [Partial Counterfactual Identification from Observational and Experimental Data](https://mlsanity.com/paper/2110.05690/) (2021)
- [Explaining Black-Box Algorithms Using Probabilistic Contrastive Counterfactuals](https://mlsanity.com/paper/2103.11972/) (2021)
- [An Automated Approach to Causal Inference in Discrete Settings](https://mlsanity.com/paper/2109.13471/) (2021)
- [Causes of Effects: Learning individual responses from population data](https://mlsanity.com/paper/2104.13730/) (2021)
- [Structural Causal Models Are (Solvable by) Credal Networks](https://mlsanity.com/paper/2008.00463/) (2020)
- [A General Method for Deriving Tight Symbolic Bounds on Causal Effects](https://mlsanity.com/paper/2003.10702/) (2020)
- [Comparing Causal Frameworks: Potential Outcomes, Structural Models, Graphs, and Abstractions](https://mlsanity.com/paper/2306.14351/) (2023)
- [Bounding Counterfactuals under Selection Bias](https://mlsanity.com/paper/2208.01417/) (2022)
- [Causality in Bayesian Belief Networks](https://mlsanity.com/paper/1303.1454/) (2013)

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

- [Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models](https://mlsanity.com/paper/2509.03548/) (2025)
- [Bayesian Networks for Causal Analysis in Socioecological Systems](https://mlsanity.com/paper/2401.10101/) (2024)
- [Causal computations in Semi Markovian Structural Causal Models using divide and conquer](https://mlsanity.com/paper/2511.13852/) (2025)
- [Bounds and Identification of Joint Probabilities of Potential Outcomes and Observed Variables under Monotonicity Assumptions](https://mlsanity.com/paper/2602.18762/) (2026)
- [Probabilities of Causation and Root Cause Analysis with Quasi-Markovian Models](https://mlsanity.com/paper/2509.02535/) (2025)
- [A Framework for Causal Concept-based Model Explanations](https://mlsanity.com/paper/2512.02735/) (2025)
- [Identification and Bounding of Central Moments of Causal Effects Using Marginal Moments Information](https://mlsanity.com/paper/2607.04957/) (2026)
- [Partial Identification under Causal Orders by Linear Programming](https://mlsanity.com/paper/2608.24427/) (2026)

## Abstract (arXiv)

We assume to be given structural equations over discrete variables inducing a directed acyclic graph, namely, a structural causal model, together with data about its internal nodes. The question we want to answer is how we can compute bounds for partially identifiable counterfactual queries from such an input. We start by giving a map from structural casual models to credal networks. This allows us to compute exact counterfactual bounds via algorithms for credal nets on a subclass of structural causal models. Exact computation is going to be inefficient in general given that, as we show, causal inference is NP-hard even on polytrees. We target then approximate bounds via a causal EM scheme. We evaluate their accuracy by providing credible intervals on the quality of the approximation; we show through a synthetic benchmark that the EM scheme delivers accurate results in a fair number of runs. In the course of the discussion, we also point out what seems to be a neglected limitation to the trending idea that counterfactual bounds can be computed without knowledge of the structural equations. We also present a real case study on palliative care to show how our algorithms can readily be used for practical purposes.