Partial Identification under Causal Orders by Linear Programming

Eric Rossetto; Alessandro Antonucci

cs.AIAug 25, 2026

Partial Identification under Causal Orders by Linear Programming

Authors: Eric Rossetto, Alessandro Antonucci

Organizations: Istituto Dalle Molle di Studi sull’Intelligenza Artificiale (IDSIA) Scuola Universitaria Professionale della Svizzera Italiana (SUPSI) Lugano, Switzerland

Abstract

Non-parametric (partial) identification of counterfactual queries typically relies on a fully specified causal graph. Motivated by settings with incomplete domain knowledge, we challenge this requirement by leveraging structural assumptions that are inherently implied by the query itself. We show that any counterfactual inquiry induces a, mostly partial, topological ordering over relevant variables, which, in turn, enables an explicit query parametrisation reducing the identification task to a linear program. This allows bounding arbitrary counterfactual and nested counterfactual queries. Our work can be viewed as a generalisation of the classical bounding framework of Tian and Pearl (2000), originally developed for probabilities of causation. We also prove the tightness of our bounds by constructing structural causal models that attain the bounds whilst being compatible with both the observed data and the query-implied order. To assess both the generality and practical utility of the proposed bounding procedure, we revisit several case studies from the literature, demonstrating how the derived bounds can be used to yield informative insights even in the absence of an input causal graph.

Figures & tables

Panel of Figure 1 — Figure 1: Causal diagrams considered in the examples. (a) Confounded treatment-outcome pair. (b) Instrumental Variable (IV) setting, where $Z$ serves as an instrument for $X$ . (c) Mediation model with a direct effect and confounding between the mediator $W$ and the outcome. Grey nodes denote unobserved exogenous variables.

Assumption Set	$\mathrm{CDE}^{w_{0}}_{x_{0},x_{1}}(y_{1})$		$\mathrm{CDE}^{w_{1}}_{x_{0},x_{1}}(y_{1})$		$\|\bm{\mathcal{S}}_{\sigma}\|$	$\|\bm{\mathcal{T}}_{\sigma}\|$
Assumption Set	Lower	Upper	Lower	Upper	$\|\bm{\mathcal{S}}_{\sigma}\|$	$\|\bm{\mathcal{T}}_{\sigma}\|$
No additional assumptions
Cai et al. (2008) (Fig. 1(c) )	-0.200	0.385	-0.781	0.634	–	–
This paper	-0.599	0.694	-0.891	0.817	128	20
Monotonicity
Cai et al. (2008)	0.000	0.036	0.000	0.582	–	–

Table 1: Comparison of CDE bounds on the (binary) Lipid data ( Cai et al., 2008 , Tab. 1) against analytical bounds under varying assumptions. In this experiment, Monotonicity forces positive effects of

X

W

X

Y

, and

W

Y

; whilst, weak exogeneity imposes no-interaction between

X

and

W

Y

	Lower	Upper	$\|\bm{\mathcal{S}}_{\sigma}\|$	$\|\bm{\mathcal{T}}_{\sigma}\|$
Assumptions for $\mathrm{NDE}_{x_{0},x_{1}}(y_{1})$
Query-induced Order	-0.691	0.688	294,912	60
$Y\perp\!\!\!\perp X$	-0.503	0.497	294,912	96
$\{Y,W\}\perp\!\!\!\perp X$	-0.503	0.497	294,912	528
$Y\perp\!\!\!\perp\{X,W\}$	-0.628	0.679	294,912	89,172
$Y\perp\!\!\!\perp\{X,W\}$ & $W\perp\!\!\!\perp X$	-0.489	0.637	294,912	294,912

Table 2: UC Berkeley dataset: NDE bounds under various weak exogeneity assumptions (top) and individual unnested query terms under query-induced assumptions (bottom).

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Vitamin A
Method	Lower	Upper
Balke and Pearl (1997)	-0.195	0.005
This paper	-0.587	0.412
Coronary
Balke and Pearl (1997)	0.262	0.868
This paper	-0.685	0.971

Appendix

Table 3: Comparison of ACE bounds. Lower and upper bounds for the ACE grouped by Study.

Panel of Figure 2 — Figure 2: End-to-end computation time for $\mathrm{GPNS}(r)$ bounds, on a semi-logarithmic scale, as a function of the variable cardinalities ( $n=|\mathcal{X}|=|\mathcal{Y}|$ ).

Panel of Figure 3 — Figure 3: Examples of canonical PSCM specifications compatible with the endogenous order $\sigma\coloneq(X,W,Y)$ . (a) Markovian specification. (b) Specification with one exogenous variable shared by $W$ and $Y$ . (c) Specification with one exogenous variable shared by all endogenous variables. Grey nodes denote exogenous variables.

Partial Identification

Partial identification studies what can be learned when data and defensible assumptions narrow a target to a set rather than a single value.

See all 29 papers

Causal Identification from Counterfactual Data: Completeness and Bounding Results
Feb 26, 2026Arvind Raghavan, Elias BareinboimCausal Inference Causal Identifiability
Causal Artificial Intelligence Lab, Department of Computer Science, Columbia University
Foundation Models for Partial Causal Identification
Aug 21, 2026Alexis Bellot, Anish DhirCausal Foundation Models Causal Effect Estimation
Independent · University College London
Bounding Probabilities of Causation with Partial Causal Diagrams
Feb 16, 2026Yuxuan Xie, Ang LiCausal Inference Causal Identifiability
University of Ottawa, Ontario, Canada · Department of Computer Science, Florida State University, FL, U.S.A.

Feb 26, 2026J/K move · Enter open · S save

Causal Identification from Counterfactual Data: Completeness and Bounding Results

Arvind Raghavan, Elias Bareinboim

Causal Artificial Intelligence Lab, Department of Computer Science, Columbia University

Causal Inference Causal Identifiability Partial Identification

Open paper AskPDF arXiv

Previous work establishing completeness results for counterfactual identification has been circumscribed to the setting where the input data belongs to observational or interventional distributions (Layers 1 and 2 of Pearl's Causal Hierarchy), since it was generally presumed impossible to obtain data from counterfactual distributions, which belong to Layer 3. However, recent work (Raghavan & Bareinboim, 2025) has formally characterized a family of counterfactual distributions which can be directly estimated via experimental methods - a notion they call counterfactual realizability. This leaves open the question of what additional counterfactual quantities now become identifiable, given this new access to (some) Layer 3 data. To answer this question, we develop the CTFIDU+ algorithm for identifying counterfactual queries from an arbitrary set of Layer 3 distributions, and prove that it is complete for this task. Building on this, we establish the theoretical limit of which counterfactuals can be identified from physically realizable distributions, thus implying the fundamental limit to exact causal inference in the non-parametric setting. Finally, given the impossibility of identifying certain critical types of counterfactuals, we derive novel analytic bounds for such quantities using realizable counterfactual data, and corroborate using simulations that counterfactual data helps tighten the bounds for non-identifiable quantities in practice.

Abstract

Partial Identification

Explore similar work

Causal Identification from Counterfactual Data: Completeness and Bounding Results

Foundation Models for Partial Causal Identification

Bounding Probabilities of Causation with Partial Causal Diagrams