# On the Complexity of Counterfactual Reasoning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 80 references that are in the map.
- First posted on arXiv 24 Nov 2022.

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

- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [Probabilities of Causation: Bounds and Identification](https://mlsanity.com/paper/1301.3898/) (2013)
- [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)
- [An Automated Approach to Causal Inference in Discrete Settings](https://mlsanity.com/paper/2109.13471/) (2021)
- [Nested Counterfactual Identification from Arbitrary Surrogate Experiments](https://mlsanity.com/paper/2107.03190/) (2021)
- [Causes of Effects: Learning individual responses from population data](https://mlsanity.com/paper/2104.13730/) (2021)
- [Margins of discrete Bayesian networks](https://mlsanity.com/paper/1501.02103/) (2015)
- [Structural Causal Models Are (Solvable by) Credal Networks](https://mlsanity.com/paper/2008.00463/) (2020)
- [Bucket Elimination: A Unifying Framework for Several Probabilistic Inference](https://mlsanity.com/paper/1302.3572/) (2013)
- [Counterfactuals and Policy Analysis in Structural Models](https://mlsanity.com/paper/1302.4929/) (2013)
- [Unit Selection with Nonbinary Treatment and Effect](https://mlsanity.com/paper/2208.09569/) (2022)
- [An Advance on Variable Elimination with Applications to Tensor-Based Computation](https://mlsanity.com/paper/2002.09320/) (2020)
- [Causal Expectation-Maximisation](https://mlsanity.com/paper/2011.02912/) (2020)
- [Tractable Boolean and Arithmetic Circuits](https://mlsanity.com/paper/2202.02942/) (2022)
- [Bounding Counterfactuals under Selection Bias](https://mlsanity.com/paper/2208.01417/) (2022)
- [Reduction of Computational Complexity in Bayesian Networks through Removal of Weak Dependencies](https://mlsanity.com/paper/1302.6825/) (2013)
- [Inter-causal Independence and Heterogeneous Factorization](https://mlsanity.com/paper/1302.6855/) (2013)

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

- [Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations](https://mlsanity.com/paper/2501.06078/) (2025)
- [Identifying Causal Effects Under Functional Dependencies](https://mlsanity.com/paper/2403.04919/) (2024)
- [Causal Unit Selection using Tractable Arithmetic Circuits](https://mlsanity.com/paper/2404.06681/) (2024)
- [Tractable Bounding of Counterfactual Queries by Knowledge Compilation](https://mlsanity.com/paper/2310.03352/) (2023)
- [An Algorithm and Complexity Results for Causal Unit Selection](https://mlsanity.com/paper/2302.14412/) (2023)
- [Constrained Identifiability of Causal Effects](https://mlsanity.com/paper/2412.02869/) (2024)
- [Teleporter Theory: A General and Simple Approach for Modeling Cross-World Counterfactual Causality](https://mlsanity.com/paper/2406.11501/) (2024)

## Abstract (arXiv)

We study the computational complexity of counterfactual reasoning in relation to the complexity of associational and interventional reasoning on structural causal models (SCMs). We show that counterfactual reasoning is no harder than associational or interventional reasoning on fully specified SCMs in the context of two computational frameworks. The first framework is based on the notion of treewidth and includes the classical variable elimination and jointree algorithms. The second framework is based on the more recent and refined notion of causal treewidth which is directed towards models with functional dependencies such as SCMs. Our results are constructive and based on bounding the (causal) treewidth of twin networks -- used in standard counterfactual reasoning that contemplates two worlds, real and imaginary -- to the (causal) treewidth of the underlying SCM structure. In particular, we show that the latter (causal) treewidth is no more than twice the former plus one. Hence, if associational or interventional reasoning is tractable on a fully specified SCM then counterfactual reasoning is tractable too. We extend our results to general counterfactual reasoning that requires contemplating more than two worlds and discuss applications of our results to counterfactual reasoning with a partially specified SCM that is coupled with data. We finally present empirical results that measure the gap between the complexities of counterfactual reasoning and associational/interventional reasoning on random SCMs.