On the Complexity of Counterfactual Reasoning

A theory of causality has emerged over the last few decades based on two parallel hierarchies, an information hierarchy and a reasoning hierarchy, often called the causal hierarchy Pearl and Mackenzie (2018). On the reasoning side, this theory has crystallized three levels of reasoning with increased sophistication and proximity to human reasoning: associational, interventional and counterfactual, which are exemplified by the following canonical probabilities. Associational ${\it Pr}(y|x)$: probability of $y$ given that $x$ was observed. Example: probability that a patient has a flu given they have a fever. Interventional ${\it Pr}(y_{x})$: probability of $y$ given that $x$ was established by an intervention. This is different from ${\it Pr}(y|x)$. Example: seeing the barometer fall tells us about the weather but moving the barometer needle won’t bring rain. Counterfactual ${\it Pr}(y_{x}|{\bar{y}},{\bar{x}})$: probability of $y$ if we were to establish $x$ by an intervention given that neither $x$ nor $y$ are true. Example: probability that a patient who did not take a vaccine and died would have recovered had they been vaccinated. On the information side, these forms of reasoning were shown to require different levels of knowledge, encoded as (1) associational models, (2) causal models and (3) functional (mechanistic) models, respectively, with each class of models containing more information than the preceding one. In the framework of probabilistic graphical models Koller and Friedman (2009), this information is encoded by (1) Bayesian networks Darwiche (2009); Pearl (1988), (2) causal Bayesian networks Pearl (2009); Peters et al. (2017); Spirtes et al. (2000), and (3) functional Bayesian networks Balke and Pearl (1995); Pearl (2009).

Counterfactual reasoning has received much interest as it inspires both introspection and contemplating scenarios that have not been seen before, and is therefore viewed by many as a hallmark of human intelligence. Figure 1 depicts a functional Bayesian network, also known as a structural causal model (SCM) Galles and Pearl (1998); Halpern (2000), which can be used to answer counterfactual queries. Variables without causes are called exogenous or root and variables with causes are called endogenous or internal. The only uncertainty in SCMs concerns the states of exogenous variables and this uncertainty is quantified using distributions over these variables. Endogenous variables are assumed to be functional: they are functionally determined by their causes where the functional relationships, also known as causal mechanisms, are specified by structural equations.¹¹1These equations can also be specified using conditional probability tables (CPTs) that are normally used in Bayesian networks, but the CPTs will contain only deterministic distributions. These equations and the distributions over exogenous variables define the parameters of the causal graph, leading to a fully specified SCM which can be used to evaluate associational, interventional and counterfactual queries. For example, the SCM in Figure 1 has enough information to evaluate the counterfactual query ${\it Pr}(y_{x}|{\bar{x}},{\bar{y}})$: the probability that a patient who did not take the treatment and died would have been alive had they been given the treatment ($2.17\%$). A causal Bayesian network contains less information than a functional one (SCM) as it does not require endogenous variables to be functional, but it is sufficient to compute associational and interventional probabilities. A Bayesian network contains even less information as it does not require network edges to have a causal interpretation, only that the conditional independences encoded by the network are correct, so it can only compute associational probabilities.

All three forms of reasoning (and models) involve a directed acyclic graph (DAG) which we call the base network; see left of Figure 1. Associational and interventional reasoning can be implemented by applying classical inference algorithms to the base network. The time complexity can be bounded by $n\cdot\exp(w)$, where $n$ is the number of network nodes and $w$ is its treewidth (a graph-theoretic measure of connectivity). Counterfactual reasoning is more sophisticated and is based on a three-step process that involves abduction, intervention and prediction Balke and Pearl (1994b). When contemplating two worlds, this process can be implemented by applying classical inference algorithms to a twin network Balke and Pearl (1994b), obtained by duplicating endogenous nodes in the base network; see right of Figure 1. To compute the counterfactual query ${\it Pr}(y_{x}|{\bar{y}},{\bar{x}})$, one asserts ${\bar{y}},{\bar{x}}$ as an observation on one side of the twin network (real world) and computes the interventional query ${\it Pr}(y_{x})$ on the other side of the network (imaginary world). The time complexity can be bounded by $n^{t}\cdot\exp(w^{t})$, where $n^{t}$ is the number of nodes in the twin network and $w^{t}$ is its treewidth. A recent result provides a much tighter bound using the notion of causal treewidth Chen and Darwiche (2022); Darwiche (2021), which is no greater than treewidth but applies only when certain nodes in the base network are functional — in SCMs every endogenous node is functional.

One would expect the more sophisticated counterfactual reasoning with twin networks to be more expensive than associational/interventional reasoning with base networks since the former networks are larger and have more complex topologies. But the question is: How much more expensive? For example, can counterfactual reasoning be intractable on a twin network when associational/interventional reasoning is tractable on its base network? We address this question in the context of reasoning algorithms whose complexity is exponential only in the (causal) treewidth, such as the jointree algorithm Lauritzen and Spiegelhalter (1988), the variable elimination algorithm Zhang and Poole (1994); Dechter (1996) and circuit-based algorithms Darwiche (2003, 2022). In particular, we show in Sections 3 & 4 that the (causal) treewidth of a twin network is at most twice the (causal) treewidth of its base network plus one. Hence, the complexity of counterfactual reasoning on fully specified SCMs is no more than quadratic in the complexity of associational and interventional reasoning, so the former must be tractable if the latter is tractable. We extend our results in Section 5 to counterfactual reasoning that requires contemplating more than two worlds, where we also discuss a class of applications that require this type of reasoning and for which fully specified SCMs can be readily available. Our results apply directly to counterfactual reasoning on fully specified SCMs but we also discuss in Section 6 how they can sometimes be used in the context of counterfactual reasoning on data and a partially specified SCM. We finally present empirical results in Section 7 which reveal that, on average, the complexity gap between counterfactual and associational/interventional reasoning on fully specified SCMs can be smaller than what our worst-case bounds may suggest.

We next review the notions of treewidth Robertson and Seymour (1986) and causal treewidth Chen and Darwiche (2022); Darwiche (2021, 2020) which we use to characterize the computational complexity of counterfactual reasoning on fully specified SCMs. We also review the notions of elimination orders, jointrees and thinned jointrees which are the basis for defining (causal) treewidth and act as data structures that characterize the computational complexity of various reasoning algorithms. We use these notions extensively when stating and proving our results (proofs of all results are in Appendix A). We assume all variables are discrete. A variable is denoted by an uppercase letter (e.g. $X$) and its values by a lowercase letter (e.g. $x$). A set of variables is denoted by a bold uppercase letter (e.g. ${\mathbf{X}}$) and its instantiations by a bold lowercase letter (e.g. ${\mathbf{x}}$).

Consider Figure 3(a) which depicts a 2-bit half adder. Suppose the binary inputs $A$ and $B$ are randomly sampled from some distribution and the gates may not be functioning properly. This circuit can be modeled using the network in Figure 3(b). Variables $A,B,S,C$ represent the inputs and outputs of the circuit; $X,Y$ represent the health of the XOR gate and the AND gate; and $U$ represents an unknown external random sampler that decides the state of inputs $A$ and $B$. Suppose that currently input $A$ is high, input $B$ is low, yet both outputs $C$ and $S$ are low which is an abnormal circuit behavior. We wish to know whether the half adder would still behave correctly when we turn both inputs $A$ and $B$ on. This question can be formulated using the following counterfactual query: $Pr((c,{\bar{s}})_{a,b}|a,{\bar{b}},{\bar{c}},{\bar{s}})$. This query can be answered using a twin network as shown in Figure 3(c), where each non-root variable $V$ has a duplicate $[V]$. The current evidence $a,{\bar{b}},{\bar{c}},{\bar{s}}$ is asserted on the variables $A,B,C,S$ representing the real world and the interventional query $Pr((c,{\bar{s}})_{a,b})$ is computed on the duplicate variables $[A],[B],[C],[S]$ representing the imaginary world. This is done by removing the edges incoming into the intervened upon variables $[A],[B]$, asserting evidence $[a],[b]$ and finally computing the probability of $[c],[{\bar{s}}]$ as shown in Figure 3(d); see Pearl (2009) for an elaborate discussion of these steps. This basically illustrates how a counterfactual query can be computed using algorithms for associational queries, like variable elimination, but on a mutilated twin network instead of the base network.

We next show that the treewidth of a twin network is at most twice the treewidth of its base network plus one, which allows us to relate the complexities of assocational, interventional and counterfactual reasoning on fully specified SCMs. We first recall the definition of twin networks as proposed by Balke and Pearl (1994b).

For convenience, we use $[U]=U$ when $U$ is root. For variables ${\mathbf{X}}$, we use $[{\mathbf{X}}]$ to denote $\{[X]|X\in{\mathbf{X}}\}$. Figure 3(c) depicts the twin network for the base network in Figure 3(b).

Recall that causal treewidth is a more refined notion than treewidth as it uses more information about the network. In particular, this notion is relevant when we know that some variables in the network are functional, without needing to know the specific functions (equations) of these variables. By exploiting this information, one can construct thinned jointrees that have smaller separators and clusters compared to classical jointrees, which can lead to exponential savings in reasoning time Chen and Darwiche (2022); Darwiche (2021, 2020). As mentioned earlier, the causal treewidth corresponds to the minimum width of any thinned jointree. This is guaranteed to be no greater than treewidth and can be bounded when treewidth is not Darwiche (2021). We next show that the causal treewidth of a twin network is also at most twice the causal treewidth of its base network plus one.

This theorem shows that a thinned, base jointree can be easily converted into a thinned, twin jointree. This is significant for two reasons. First, this method avoids the explicit construction of thinned jointrees for twin networks which can be quite expensive computationally Chen and Darwiche (2022). Second, we have the following guarantee on the width of thinned, twin jointrees constructed by Theorem 3.

Due to space constraints, we include a thinned jointree for the base network and the corresponding thinned, twin jointree constructed by Algorithm 1 and Theorem 3 in Appendix C. We can now bound the causal treewidth of twin networks.

Standard counterfactual reasoning contemplates two worlds, one real and another imaginary, while assuming that exogenous variables correspond to causal mechanisms that govern both worlds. This motivates the notion of a twin network as it ensures that these causal mechanisms are invariant. We can think of counterfactual reasoning as a kind of temporal reasoning where endogenous variables can change their states over time. A more general setup arises when we allow some exogenous variables to change their states over time. For example, consider again the half adder in Figure 3(a) and its base network in Figure 5. Suppose we set inputs $A$ and $B$ to high and low and observe outputs $S$ and $C$ to be high and low, which is a normal behavior. We then set both inputs to low and observe that the outputs do not change, which is an abnormal behavior. We then aim to predict the state of outputs if we were to set both inputs to high. This scenario involves three time steps (worlds). Moreover, while the health of gates $X$ and $Y$ are invariant over time, we do not wish to make the same assumption about the inputs $A$ and $B$. We can model this situation using the network in Figure 5, which is a more general type of networks that we call $N$-world networks.

This definition corresponds to the notion of a parallel worlds model Avin et al. (2005) when ${\mathbf{R}}$ contains all roots in the base network. Moreover, twin networks fall as a special case when $N=2$ and ${\mathbf{R}}$ contains all roots of the base network. We next bound the (causal) treewidth of $N$-world networks by the (causal) treewidth of their base networks.

The class of $N$-world networks is a subclass of dynamic Bayesian networks Dean and Kanazawa (1989) and is significant for a number of reasons. First, as illustrated above, it arises when reasoning about the behavior of systems consisting of function blocks (e.g., gates) Hamscher et al. (1992). These kinds of physical systems can be easily modeled using fully specified SCMs, where the structural equations correspond to component behaviors and the distributions over exogenous variables correspond to component reliabilities; see (Darwiche, 2009, Ch 5) for a textbook discussion and Mengshoel et al. (2010) for a case study of a real-world electrical power system. More broadly, $N$-world networks allow counterfactual reasoning that involves conflicting observations and actions that arise in multiple worlds as in the unit selection problem Li and Pearl (2022)—for example, Huang and Darwiche (2023) used Theorem 4 to obtain bounds on the complexity of this problem. See also Avin et al. (2005); Shpitser and Pearl (2007, 2008) for further applications of $N$-world networks in the context of counterfactual reasoning. Appendix D shows that the treewidth bound of Theorem 4 holds for a generalization of $N$-world networks that permits the duplication of only a subset of base nodes and allows certain edges that extend between worlds.

Our complexity bounds thus far apply to any counterfactual query. For a specific counterfactual query, we can further reduce the complexity of inference by pruning nodes and edges as in (Darwiche, 2009, Ch 6) and merging nodes which leads to counterfactual graphs as in Shpitser and Pearl (2007).

The results we presented on $N$-world networks, which include twin networks, apply directly to fully specified SCMs. In particular, in the context of variable elimination and jointree algorithms, these results allow us to bound the complexity of computing counterfactual queries in terms of the complexity of computing associational/interventional queries. Moreover, they provide efficient methods for constructing elimination orders and jointrees that can be used for computing counterfactual queries based on the ones used for answering associational/interventional queries, while ensuring that the stated bounds will be realized. Recall again that our bounds and constructions apply to both traditional treewidth and the more recent causal treewidth.

Causal reasoning can also be conducted on partially specified SCMs and data, which is a more common and challenging task. A partially specified SCM typically includes the SCM structure and some information about its parameters (i.e., its structural equations and the distributions over its exogenous variables). For example, we may not know any of the SCM paramaters, or we may know the structural equations but not the distributions over exogenous variables as assumed in Zaffalon et al. (2021). A central question in this setup is whether the available information, which includes data, is sufficient to obtain a point estimate for the causal query of interest, in which case the query is said to be identifiable. A significant amount of work has focused on characterizing conditions under which causal queries (both counterfactual and interventional) are identifiable; see, Pearl (2009); Spirtes et al. (2000) for textbook discussions of this subject and Shpitser and Pearl (2008); Correa et al. (2021) for some results on the identification of counterfactual queries.

When a query is identifiable, the classical approach for estimating it is to derive an estimand using techniques such as the do-calculus for interventional queries Pearl (1995); Tian and Pearl (2002); Shpitser and Pearl (2006).⁴⁴4See Jung et al. (2021b, a, 2020) for some recent work on estimating identifiable interventional queries from finite data. Some recent approaches take a different direction by first estimating the SCM parameters to yield a fully specified SCM that is then used to answer (identifiable) interventional and counterfactual queries using classical inference algorithms Zaffalon et al. (2022, 2021); Darwiche (2021). Our results on twin and $N$-world networks apply directly in this case as they can be used when conducting inference on the fully parameterized SCM. For unidentifiable queries, the classical approach is to derive a closed-form bound on the query; see, for example, Balke and Pearl (1994a); Pearl (1999); Tian and Pearl (2000); Dawid et al. (2017); Rosset et al. (2018); Evans (2018); Zhang et al. (2021); Mueller et al. (2022). Some recent approaches take a different direction for establishing bounds, such as reducing the problem into one of polynomial programming Duarte et al. (2021); Zhang et al. (2022) or inference on credal networks Zaffalon et al. (2020); Cozman (2000); Mauá and Cozman (2020). Another recent direction is to establish (approximate) bounds by estimating SCM parameters and then using classical inference algorithms on the fully specified SCM to obtain point estimates Zaffalon et al. (2021, 2022). Since the query is not identifiable, different parametrizations can lead to different point estimates which are employed to improve (widen) the computed bounds. Our results can also be used in this case for computing point estimates based on a particular parametrization (fully specified SCM) within the overall process of establishing bounds.

We consider experiments that target random networks whose structures emulate the structures of SCMs used in counterfactual reasoning. We have a few objectives in mind. First, we wish to compare the widths of base and twin jointrees, with and without thinning. These widths do not correspond to (causal) treewidth since the jointrees are constructed using heuristics (finding optimal jointrees is NP-hard). Next, we want to compare the quality of twin jointrees constructed by Algorithm 1 (TWIN-ALG1), which operates directly on a base jointree, to the quality of twin jointrees obtained by applying the minfill heuristic to a twin network (TWIN-MF). Recall that the former method is more efficient than the latter method. Finally, we wish to conduct a similar comparison between the thinned, twin jointrees constructed according to Theorem 3 (TWIN-THM3) and the thinned, twin jointrees obtained by applying the minfill heuristic and thinning rules to a twin network (TWIN-MF-RLS). Again, the former method is more efficient than the latter. The widths of these jointrees will be compared to the widths of base jointrees constructed by minfill (BASE-MF) and thinned, base jointrees constructed by minfill and thinning rules (BASE-MF-RLS).

We generated random networks according to the method used in Darwiche (2020). Given a number of nodes $n$ and a maximum number of parents $p$, the method chooses the parents of node $X_{i}$ randomly from the set $X_{1},\ldots,X_{i-1}$. The number of parents for node $X_{i}$ is chosen randomly from the set $0,\ldots,min(p,i-1)$. We refer to these networks as rNET. We then consider each internal node $N$ and add a unique root $R$ as parent for $N$. This is meant to emulate the structure of SCMs as the exogenous variable $R$ can be viewed as representing the different causal mechanisms for endogenous variable $N$. We refer to these modified networks as rSCM. The twin networks of rSCM are more complex than those for rNET since more variables are shared between the two slices representing the real and imaginary worlds (i.e., more information is shared between the two worlds). We used $n\in\{50,75,100,125,150,200,250,300\}$ and $p\in\{3,5,7\}$. For each combination of $n$ and $p$, we generated $50$ random, base networks and reported averages of two properties for the constructed jointrees: width and normalized width. If a jointree has clusters ${\mathbf{C}}_{1},\ldots,{\mathbf{C}}_{n}$, then normalized width is $\log_{2}\sum_{i=1}^{n}2^{|{\mathbf{C}}_{i}|}$. This accounts for all clusters in the jointree (instead of just the largest one) and the jointree size. The data we generated occupies significant space so we included it in Appendix E while providing representative plots in Figure 6 for jointree widths under $p=5$. We next discuss patterns exhibited in these plots and the full data in Appendix E, which also includes experiments using random networks generated according to the method in Ide and Cozman (2002).

First, the widths of twin jointrees are always less than twice the widths of their base jointrees and often significantly less than that. This is not guaranteed by our theoretical bounds as those apply to (causal) treewidth not to the widths of jointrees produced by heuristics — the latter widths are an upper bound on the former. Second, constructing a twin jointree by directly applying Algorithm 1 to a base jointree (TWIN-ALG1) is relatively comparable to constructing the twin jointree by operating on the twin network (TWIN-MF), as would normally be done. This also holds for thinned jointrees (TWIN-THM3 vs TWIN-MF-RLS) and is encouraging since the former methods are much more efficient than the latter ones. Third, the employment of thinned jointrees can lead to significant reduction in width and hence an exponential reduction in reasoning time. This can be seen by comparing the widths of twin jointrees TWIN-THM3 and TWIN-ALG1 since the former is thinned but the latter is not (similarly for TWIN-MF-RLS and TWIN-MF). Fourth, the twin jointrees of rSCM have larger widths than those of rNET. Recall that in rSCM, every endogenous variable has its own exogenous variable as a parent. Therefore, the distribution over exogenous variables has a larger space in rSCM compared to rNET. Since this distribution needs to be shared between the real and imaginary worlds, counterfactual reasoning with rSCM is indeed expected to be more complex computationally than reasoning with rNET. Finally, consider Figure 6(b) for a bottom-line comparison between the complexity of counterfactual reasoning and the complexity of associational/interventional reasoning in practice. Jointrees BASE-MF have the smallest widths for base networks so these are the jointrees one would use for associational/interventional reasoning. The best twin jointrees are TWIN-MF-RLS which are thinned. This is what one would use for counterfactual reasoning. The widths of latter jointrees are always less than twice the widths of the former, and quite often significantly much less.⁵⁵5See footnote 3 for why BASE-MF is better than BASE-MF-RLS for rSCM.

We studied the complexity of counterfactual reasoning on fully specified SCMs in relation to the complexity of associational and interventional reasoning on these models. Our basic finding is that in the context of algorithms based on (causal) treewidth, the former complexity is no greater than quadratic in the latter when counterfactual reasoning involves only two worlds. We extended these results to counterfactual reasoning that requires multiple worlds, showing that the gap in complexity is bounded polynomially by the number of needed worlds. Our empirical results suggest that for two types of random SCMs, the complexity of counterfactual reasoning is closer to that of associational and interventional reasoning than our worst-case theoretical analysis may suggest. While our results directly target counterfactual reasoning on fully specified SCMs, we also discussed cases when they can be applied to counterfactual reasoning on partially specified SCMs that are coupled with data.