Paper deep dive

Causal Identification from Counterfactual Data: Completeness and Bounding Results

Arvind Raghavan, Elias Bareinboim

Year: 2026Venue: arXiv preprintArea: cs.AIType: PreprintEmbeddings: 131

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%

Last extracted: 7/20/2026, 8:29:42 AM

Summary

This paper introduces the CTFIDU+ algorithm, which establishes completeness for identifying counterfactual queries (Layer 3 of Pearl's Causal Hierarchy) using arbitrary sets of Layer 3 distributions, including physically realizable counterfactual data. It proves that the theoretical limits of counterfactual realizability correspond to the limits of exact causal inference and derives novel analytic bounds for non-identifiable counterfactuals, demonstrating via simulation that such data tightens these bounds.

Entities (10)

CTFIDU+ · algorithm · 98%Pearl's Causal Hierarchy · framework · 95%Layer 3 · concept · 92%Counterfactual Hedge · concept · 90%Counterfactual Realizability · concept · 90%Counterfactual Randomization · method · 88%Natural Direct Effect · concept · 88%CTFID · algorithm · 85%IDC* · algorithm · 85%PSIDC · algorithm · 85%

Relation Signals (9)

CTFIDU+ → identifies → Layer 3 distributions

confidence 95% · CTFIDU+ algorithm for identifying counterfactual queries from an arbitrary set of Layer 3 distributions

Layer 3 → partof → Pearl's Causal Hierarchy

confidence 95% · counterfactual distributions, which belong to Layer 3

Counterfactual Realizability → dualto → Counterfactual Identifiability

confidence 92% · a counterfactual quantity is identifiable iff its distribution is realizable

CTFIDU+ → subsumes → CTFID

confidence 90% · CTFIDU+ thus subsumes the previous algorithms in Table 1

CTFIDU+ → subsumes → IDC*

confidence 90% · CTFIDU+ thus subsumes the previous algorithms in Table 1

CTFIDU+ → subsumes → PSIDC

confidence 90% · CTFIDU+ thus subsumes the previous algorithms in Table 1

Counterfactual Hedge → witnesses → Non-identifiability

confidence 90% · CTFIDU+ returns FAIL only when it detects a data-structure called a counterfactual hedge, which offers a certificate of non-identifiability

Natural Direct Effect → isexampleof → Counterfactual Query

confidence 88% · consider the natural direct effect (NDE)... NDE is defined as... a nested counterfactual

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract: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 realizabilty. 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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

129,996 characters extracted from source content.

Expand or collapse full text

Causal Identification from Counterfactual Data: Completeness and Bounding Results Arvind Raghavan 1 Elias Bareinboim 1 Abstract Previous work establishing completeness results for counterfactual identification has been circum- scribed to the setting where the input data be- longs to observational or interventional distribu- tions (Layers 1 and 2 of Pearl’s Causal Hierarchy), since it was generally presumed impossible to ob- tain data from counterfactual distributions, which belong to Layer 3. However, recent work (Ragha- van & Bareinboim, 2025) has formally charac- terized a family of counterfactual distributions which can be directly estimated via experimental methods - a notion they call counterfactual real- izabilty. 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 counterfac- tual queries from an arbitrary set of Layer 3 distri- butions, 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 im- possibility of identifying certain critical types of counterfactuals, we derive novel analytic bounds for such quantities using realizable counterfac- tual data, and corroborate using simulations that counterfactual data helps tighten the bounds for non-identifiable quantities in practice. 1. Introduction The Pearl Causal Hierarchy (PCH) provides a foundational framework for reasoning about causality (Pearl & Macken- zie, 2018; Bareinboim et al., 2022). The hierarchy formal- izes three progressively richer modes of reasoning—seeing, 1 Causal Artificial Intelligence Lab, Department of Computer Science, Columbia University. Correspondence to: Arvind Ragha- van <ar@cs.columbia.edu>. Preprint. March 5, 2026. (Speed) (Car color) X (Ticket) Y (a) Z XY (b) Z XY (c) Z Figure 1. (a) Causal diagram for Ex. 1 (Traffic Camera); (b) Standard randomization overridingXand affecting bothZ,Y; (c) Counterfactual randomization of X affecting Y , but not Z. doing, and imagining—which correspond to observational, interventional, and counterfactual regimes within an envi- ronment of interest. Consider the following example: Example 1 (Traffic Camera). Consider a fairness auditor reviewing an AI system for issuing speeding tickets based on traffic footage.Xrepresents the color of the car,Zthe driving speed,Ythe decision to issue a ticket. Fig. 1a shows the auditor’s causal graphical assumptions: due to a high correlation in the training data between the speeding tendencies and car-color preference of different socioeco- nomic groups,Xmight directly affectYin the algorithm. Xmight affectZif pedestrians and other drivers react to, say, a red car and affect its speeding. Speeding and outcome might be affected by an unobserved confounder: unlabeled road obstacles (which present as video artifacts).□ The first layer of the PCH (L 1 ) captures observational distri- butions such asP (Y = 1 ∣ X = x), how likely are drivers ofx-colored cars to receive a ticket. The second layer (L 2 ) concerns interventional distributions, such asP (Y x = 1), how likely is a speeding ticket when car color is fixed as x, say, by an experiment recruiting drivers and randomly assigning them test cars, as shown in Fig. 1b. The third layer (L 3 ) addresses counterfactual distributions over conflicting realities, for exampleP (Y x = 1 ∣ X = x ′ ), the probability a driver receives a ticket if assigned anx-colored car, given that the original color wasx ′ . Higher layers subsume lower layers. It is well-established that higher-layer questions can- not be answered using data from lower layers alone, and require causal assumptions to perform inference (Ibeling & Icard, 2020; Bareinboim et al., 2022). Counterfactuals are widely acknowledged to be important in topics including personalized decision-making (Bareinboim 1 arXiv:2602.23541v2 [cs.AI] 3 Mar 2026 Causal Identification from Counterfactual Data: Completeness and Bounding Results Table 1. Comparison of different algorithms for counterfactual identification and the scope of input data. Ours is complete when assuming an arbitrary set of physically realizable input data. MethodID QueryInput Data IDC*L 3 queryFull L 2 data PSIDCPath-specific L 3 Full L 2 data CTFIDL 3 querySubset of L 2 data CTFIDU + (ours) L 3 querySubset of realizable L 3 data et al., 2015; Mueller & Pearl, 2023), path-specific effect estimation (Pearl, 2001; Rubin, 2004; Avin et al., 2005), fairness analysis (Zhang & Bareinboim, 2018; Plecko & Bareinboim, 2024), explainable AI (Lee et al., 2025) etc. This has spurred much work in the field of counterfactual identification (defined in Sec. 2): Shpitser & Pearl (2008) proved their IDC* algorithm is complete for identifying an L 3 quantity when assuming knowledge of allL 2 (inc.L 1 ) data. Using this result, Malinsky et al. (2019) developed the PSIDC algorithm for path-specific effect identification. Correa et al. (2021) then proved their CTFID algorithm is complete forL 3 identification, assuming access to a subset ofL 2 data, and Correa et al. (2022) extended this to counter- factual transportability across heterogenous environments. If a counterfactual is non-identifiable, Zhang et al. (2022) provide a Bayesian sampling method, which we callPID, to partially identify the bounded range of this quantity. These methods are depicted in Table 1 and Fig. 2, along with the dimensions of consideration - which quantities the method is capable of identifying (output scope) and the scope of input data it assumes. We also distinguish between iden- tification methods, which map counterfactuals to a unique function of input data, and statistical methods for practically estimating these functions using finite samples of input data. To appreciate the relevance of counterfactuals, consider the natural direct effect (NDE) of a treatmentXon outcomeY (Pearl, 2001). NDE is defined asP (Y xZ x ′ = 1) − P (Y x = 1) , where the first term is a nested counterfactual. In Ex. 1, P (Y xZ x ′ = 1) denotes the outcome probability if a driver’s car were randomly assigned colorxand speedingZwas fixed to what it would have been had her car been assigned colorx ′ . Decomposing the total effect ofXonYthis way allows an auditor to reason about algorithmic fairness in this scenario. Unfortunately, due to unobserved confounding in the graph in Fig. 1a, NDE is non-identifiable using onlyL 2 data. Hence, the algorithms cited earlier fail to identify it, since they assume the input data is limited to L 2 . It is commonly believed thatL 3 distributions are inaccessi- ble except indirectly via indentification (e.g., see Dawid, 2000; Shpitser & Pearl, 2007). However, Raghavan & Bareinboim (2025) recently provided a formal character- ization of a family of counterfactuals which can be directly Figure 2. Landscape of causal identification and estimation meth- ods. CTFIDU+ is complete forL 3 identification from a collection of realizable counterfactual data. sampled from in an experimental setting, a property they term counterfactual realizability. This is made possible by the discovery of a physical procedure called counterfactual randomization (Bareinboim et al., 2015), which permitsL 3 data collection. E.g., in Ex. 1, the auditor can randomize the RGB values in the video footage to fix the car colorX as perceived byY, without affecting the natural value of X,Z, as shown in Fig. 1c. NDE can be identified with this data as follows: P (Y xZ = 1 ∣ X = x ′ )by ctf. randomization(1) =P (Y xZ x ′ ∣ X = x ′ )X = x ′ ⟹ Z = Z x ′ (2) =P (Y xZ x ′ )d-separation(3) The NDE now becomes identifiable with the possibility of counterfactual data collection. This realization in fact opens up more fundamental questions: which other L 3 quantities also become identifiable given access to (some)L 3 data? What is the relationship between counterfactual identifiabil- ity and realizability - does one imply the other? We resolve these questions in this paper. Specifically, our contributions are as follows: • Sec. 3: we develop theCTFIDU + algorithm (Alg. 2) which identifies a counterfactual quantity using data from an arbitrary set ofL 3 input (inc. realizable counterfactual data), or returns FAIL if the query is non-identifiable. We prove the algorithm is complete (Thm. 3.5).CTFIDU + thus subsumes the previous algorithms in Table 1. •Sec. 4: we prove foundational results connecting coun- terfactual realizability and identifiability. We show that the theoretical limits of realizability are also the limits of exact identification (Thm. 4.1). This further implies a du- ality result - a counterfactual quantity is identifiable iff its distribution is realizable, in principle, via counterfactual randomization actions (Cor. 4.2). • Sec. 5: we show that, even for non-identifiable quanti- ties, the partial identification bounds can be tightened by accessing (some) counterfactual data. We derive novel 2 Causal Identification from Counterfactual Data: Completeness and Bounding Results analytic bounds for an important type ofL 3 query using counterfactual data which are provably tighter than previ- ous results (Prop. 5.4). We then show via simulations that this extra data meaningfully narrows the(1−β)credence interval for an identification query in practice (Ex. 2, 3). All proofs are provided in the supplementary material. 2. Background and Notation We denote variables by capital letters,X, and values by small letters,x. Bold letters,X, are sets of variables andx sets of values.P (x)is shorthand forP (X = x).1[.]is the indicator function. Two valuesxandzare consistent if they share the common values forX ∩ Z. We denote by x \ Zthe subset ofxcorresponding to variables inX \ Z, and byx ∩ Zthe subset ofxcorresponding to variables in X ∩ Z. We assume finite-domain discrete variables. Structural Causal Model. We use Structural Causal Models (SCMs) to describe the generative process for a system (Bareinboim, 2025; Pearl, 2000). An SCMMis a tuple⟨V, U, F,P (u)⟩.Vis the set of observable vari- ables in the system.Uis the set of unobservable variables exogenous to the system, distributed according toP M (U). F = f i is a set of functions s.t. eachf i causally generates the value ofV i ∈ VasV i ← f i (U i , Pa i ), whereU i ⊆ U and Pa i ∈ V \ V i . M is typically unknown. Causal diagram. EachMinduces a causal diagramG, which is a graph containing a vertex for eachV i ∈ V, a directed edge from each node inPa i toV i , and a bidirected edge betweenV i ,V j ifU i , U j are not independent.G XW denotes the result of removing edges coming into variables inX, and edges coming out ofW.G[W]denotes a sub- graph ofG, which includes onlyWand the edges among its elements. We use standard terminology like parents, de- scendants of a node (see App. A). Our treatment is limited to recursive SCMs, which implies acyclic diagrams. Given graphG, its vertices can be partitioned into con- founded, or c-components such that two variables belong to the same c-component if they are connected inGby a path made entirely of bidirected edges. Potential response. Thedo(x)operator indexes a sub- modelM x where the functions generatingXare replaced with constant valuesx. I.e., this is an intervention in the modelMwhich overrides natural mechanisms and assigns fixed valuesxto variablesX. A variableY /∈ Xevaluated in this regime is called a potential response, denoted Y x . Layers of the PCH.(W ⋆ = w) denotes an arbitrary coun- terfactual event, e.g. (Y x = y,Y x ′ = y ′ ,X = x ′ ) denotes the joint realization of these ”cross-regime” potential responses for a single unit in the study population.V(W ⋆ )denotes the observable variables appearing inW ⋆ , e.g.Y,Xin the preceding. The probability of this eventP (W ⋆ = w) is given by the Layer 3 (L 3 ) valuation: ∑ u ( ∏ W t ∈W ⋆ 1[W t (u) = w] ) P (u),(4) withwtaken fromw. If the subscripts of all the terms in W ⋆ are the samex, this corresponds to the Layer 2 (L 2 ) distributionP (W x ) = P (W;do(x)). If the subscripts are all∅, this is the Layer 1 (L 1 ) distributionP (W). We assume throughout that all distributions are positive. W ⋆ could include potential responses under recursively defined regimes (Correa & Bareinboim, 2025, Sec. 2.1.1). For instance, in Fig. 1, the nested counterfactualY xZ x ′ refers to the variableYmeasured in a regime whereXis fixed to bex, andZis fixed to the value it would have taken hadXbeen fixed asx ′ . Such nesting can be arbitrarily deep. Counterfactual (ctf-) factor.LetC ⋆ be a counterfactual set of the formV 1 [pa 1 ] ,...,V k [pa k ] , andc = v 1 ,...,v k , withV i ∈ V. Then,Q[C ⋆ ](c)is called the counterfactual, or ctf-factor of C ⋆ and is defined as Q[C ⋆ ](c) = P (C ⋆ = c),(5) This is a generalization of theL 2 notion of a confounded, or c-factor, defined for C ⊆ V and c ⊆ v as Q[C](v) = P (c;do(v \ c))(6) Counterfactual identification. A queryP (Y ⋆ = y)is said to be identifiable from a set of input data distributions Agiven causal diagramG, ifP (Y ⋆ = y)is uniquely com- putable from A in any causal model which induces G. 2.1. Realizability of a distribution A distributionP (Y ⋆ )is said to be realizable given graphG, if it is possible to directly draw data samples fromP (Y ⋆ ) using a sequence of physical actions taken from the set of permissible actions in the given environment (Raghavan & Bareinboim, 2025, Def. 3.4).L 1 distributions likeP (V) can be realized by observing the natural behavior of a sys- tem.L 2 distributions likeP (V;do(x))can be realized via the standard randomized intervention rand(X) - erasing the natural value ofXand assigning a random valueX = xfor each unit, and sampling from this regime (Fig. 1b). Counterfactual randomization. (Raghavan & Barein- boim, 2025, Def. 2.3) Given a graphG, this intervention allows the value of a treatment variableXas perceived by some of its child variablesC ⊆ Ch(X)to be a randomly 3 Causal Identification from Counterfactual Data: Completeness and Bounding Results assigned, notated ctf-rand(X → C). Unlike the standard randomized intervention rand(X), this neither (1) overrides the unit’s naturally realized value ofX, nor (2) affects the variables inCh(X) \ C. For instance, in Fig. 1c, the action ctf-rand(X → Y) affects onlyYwithout affectingZ, and does not override the natural X . 1 Thus, the set of permissible actions for data-collection now includes observation, and possibly rand() and ctf-rand() of one ore more variables. Of course, some randomizations may not be feasible or desirable in any given environment. 3. Identification from Counterfactual Data As discussed in previous sections, the possibility of per- forming ctf-rand() expands the scope of input data available for supporting counterfactual identification. We index each input data distribution intuitively by the actionsAan exper- imenter takes in that data-collection regime. For instance, in Fig. 1c, the input distribution is indexed by by the action setA=ctf-rand(X → Y). Here, the experimenter is able to sample directly from the counterfactual distribution P (Y xZ = y,Z = z,X = x ′ )which by the consistency rule is equivalent toP (y xz ,z,x ′ ). The set of available data distributions indexed byA = A 1 ,..., A k forms an input to our identification algorithm detailed next. 2 Our roadmap for this section is as follows. •We develop theIDENTIFY + algorithm which identifies a target ctf-factorQ[C ⋆ ](c)from an input ctf-factor Q[T ⋆ ](t) or returns FAIL if it is non-identifiable; •We prove thatIDENTIFY + is complete for this task, us- ing a novel proof technique; we show thatIDENTIFY + returns FAIL only when it detects a data-structure called a counterfactual hedge, which offers a certificate of non-identifiability; •We develop theCTFIDU + algorithm that decomposes a target counterfactual into smaller ctf-factor terms which are necessary and sufficient for identification; it then runsIDENTIFY + as a sub-routine to identify each term, or returns FAIL if one or more terms cannot be identified from the input data; and • We prove that CTFIDU + is complete for identification from realizable counterfactual data. Our first contribution is the IDENTIFY + algorithm (Alg. 1), which takes as input a ctf-factorQ[T ⋆ ](t)which can be 1 Refer to (Raghavan & Bareinboim, 2025, App. E) for the conditions that permit such a procedure to be performed. 2 A = ∅corresponds to the observational distributionP (v), whileA = rand(X)is the standard randomized intervention on Xand corresponds to the interventional distributionP (v;do(x)). Algorithm 1 IDENTIFY + 1:Input: Causal diagramG; ctf-factorQ[C ⋆ ](c); ctf- factorQ[T ⋆ ](t), s.t.c ⋆ ⊆ t ⋆ andV(T ⋆ )is a single c-component in G[V(T ⋆ )] 2:Output: Expression forQ[C ⋆ ](c), c ⋆ ⊆ t ⋆ , in terms of Q[T ⋆ ](t); or FAIL 3:LetH ⋆ be the smallest set s.t.C ⋆ ⊆ H ⋆ ⊆ T ⋆ and there is noC i [pa i ] ∈ H ⋆ ,C j [pa j ] ∈ T ⋆ \ H ⋆ where t ∩ C j ∈ pa i 4: if H ⋆ = C ⋆ then 5:Return Q[C ⋆ ](c) = ∑ t Q[T ⋆ ](t) 6: else if H ⋆ = T ⋆ then 7:Return FAIL 8: else if C ⋆ ⊂ H ⋆ ⊂ T ⋆ then 9: Q[H ⋆ ](h) = ∑ t Q[T ⋆ ](t) 10: LetH 1 ⋆ ,..., H m ⋆ be a partition ofH ⋆ s.t.each V(H i ⋆ ) forms a c-component in G[V(H ⋆ )] 11:Let H i ⋆ be the subset s.t. C ⋆ ⊆ H i ⋆ 12: ComputeQ[H i ⋆ ](h i )fromQ[H ⋆ ](h)by Thm. B.5 13:Return IDENTIFY + ( G,Q[C ⋆ ](c),Q[H i ⋆ ](h i ) ) 14: end if obtained from the input data, and computes the value of some other target ctf-factorQ[C ⋆ ](c)which is a subset (c ⋆ ⊆ t ⋆ ) iff it is identifiable from this input data. Refer to Sec. 2 for the definition of a ctf-factor. For instance, in Fig.6c, suppose we can access the P (y x ,x ′ )distribution by the action ofctf-rand(X → Y ), and we want to computeP (y x )using this input data. Call- ingIDENTIFY + (G,P (y x ),P (y x ,x ′ ))definesH ⋆ ∶= Y x in Line 3. And Line 4 returnsP (y x ) = ∑ x ′ P (y x ,x ′ )as needed. 3 Notably,IDENTIFY + generalizes the celebrated IDENTIFYalgorithm (Tian & Pearl, 2003, Sec. 4.4), which works at the level of interventional (L 2 ) c-factors. In order to build up to the completeness ofIDENTIFY + , we formulate a novel data structure that may be observed in the distributions of potential responses. We define a counterfactual forest and hedge as follows. Definition 3.1 (Counterfactual (Ctf-) Forest). Let Q[T ⋆ ](t) be a ctf-factor satisfying the following: i. V j[.] appearsatmostonceinT ⋆ = V 1 [pa 1 ] ,...,V k [pa k ] for any j; i. ForT = V(T ⋆ ),G[T]is a c-component whose bidi- 3 We show in App. B.4 a more involved example where IDENTIFY + computes a ctf-factor using a sequence of non-trivial steps, beyond just marginalizing out extra terms. 4 Causal Identification from Counterfactual Data: Completeness and Bounding Results C S BD E F Figure 3. Sugraph of a ctf-hedge rected edges form a minimum spanning tree; i. T = An(C) G[T] for someC ⋆ ⊆ T ⋆ , withC = V(C ⋆ ) and c = t ∩ C ⋆ ; iv. Each vertex in G[T] has at most one child; then T ⋆ = tis said to be a counterfactual, or ctf-forest rooted in C ⋆ = c.□ Definition 3.2 (Counterfactual (Ctf-) Hedge). LetT ⋆ = t be a ctf-forest rooted in C ⋆ = c, having subgraph G. If • T ⋆ ≠ C ⋆ ; and • For eachV i [pa i ] ∈ T ⋆ \ C ⋆ andV j = Ch(V i ) G , we havet ∩ V i [pa i ] = pa j ∩ V i [pa i ] ; that is,t ⋆ forms a ”value chain” where each term’s value is in its child’s subscript for T ⋆ \ C ⋆ , then T ⋆ = tis a counterfactual, or ctf-hedge according toG, rooted in C ⋆ = c.□ Consider the minimum spanning tree in Fig.3. s,c,b s ′ c ′ ,d b ′ ,f d ′ ,e gh is a ctf-forest rooted inE gh = e,F d ′ = f , whiles,c,b sc ,d b ,f d ,e gh satisfies the def- inition of a ctf-hedge rooted in E gh = e,F d = f. This structure marks an evolution of the previous hedge/thicket structures that have been used to witness non- identification (Shpitser & Pearl, 2006; Lee et al., 2019). This structure is designed to authenticate a failure to identify one ctf-factor from another, with a simplified proof strategy as compared to Lee et al. (2019). Lemma 3.3 (Ctf-hedge non-identifiability). LetT ⋆ = tbe a ctf-hedge rooted inC ⋆ = c, with subgraphG. Q[C ⋆ ](c) is not identifiable from Q[T ⋆ ](t) given G. Proof sketch.We develop a bit-encoding scheme to con- struct a pair of SCMs that, by virtue of the edge count in a min. spanning tree, agree onP (t ⋆ )but differ onP (c ⋆ ), witnessing non-identifiability. See App. E.1.■ Lemma 3.4 (IDENTIFY + soundness and completeness). Let Q[T ⋆ ](t)be a ctf-factor in which each observable variable appears at most once, andG[V(T ⋆ )]is a c-component. Let Q[C ⋆ ](c)be a ctf-factor s.t.C ⋆ ⊆ T ⋆ , c ⊆ t.Q[C ⋆ ](c) is identifiable fromQ[T ⋆ ](t)andGiffIDENTIFY + returns an expression for it. Algorithm 2 CTFIDU + 1:Input: Causal diagramGover variablesV; un-nested counterfactual queryP (Y ⋆ = y)involving variables in V; input distribution specifications A 2: Output: Expression forP (Y ⋆ = y), in terms of input distributions; or FAIL if not identifiable from ⟨G, A⟩ 3: Let Y ⋆ ← ∣Y ⋆ ∣, by Lem. B.3 4: if ∃y x ,y ′ x ∈ y ⋆ or y ′ y ∈ y ⋆ , s.t. y ≠ y ′ then 5:Return 0 (trivially impossible) 6: end if 7: Let W ⋆ = An(Y ⋆ ) (Def. B.2) 8:LetP (W ⋆ = w) ← P (W ⋆ = w)after applying the ancestral set transformation, or AST, to it (Thm. B.4) 9:LetC 1 ⋆ ,..., C k ⋆ be a partition ofW ⋆ s.t. eachV(C j ⋆ ) forms a c-component in G[V(W ⋆ )] 10: for each Q[C j ⋆ ](c j ) and A ∈ A do 11: P (T ⋆ = t)← REGIME-REGEX(G, A), Alg. 4 12: LetP (T ⋆ = w) ← P (T ⋆ = w)after applying the ancestral set transformation to it (Thm. B.4) 13: LetT 1 ⋆ ,..., T m ⋆ be a partition ofT ⋆ s.t. eachV(T i ⋆ ) forms a c-component in G 14: Compute eachQ[T i ⋆ ](t i )fromP (T ⋆ = t)using Thm. B.5 15:if there exists some setT i ⋆ s.t.c j ⋆ ⊆ t i ⋆ andIDENTIFY + (G, C j ⋆ ,Q[T i ⋆ ](t i ))does not FAIL then 16: Q[C j ⋆ ](c j )← IDENTIFY + ( G,Q[C j ⋆ ],Q[T i ⋆ ] ) 17:end if 18: end for 19: if some Q[C j ⋆ ](c j ) was not identified from A then 20:Return FAIL 21: end if 22: Return P (Y ⋆ = y)← ∑ w ∏ j Q[C j ⋆ ](c j ) Proof sketch. IDENTIFY + returns a valid expression, and only FAILS when it detects a ctf-hedge. See App. E.1.■ This sub-routine forms a key component in our next contri- bution: theCTFIDU + algorithm (Alg. 2).CTFIDU + takes as input a graphG, a counterfactual queryQ, and a set of available distributions (including possibly counterfactual data) indexed byA, and computesQiff it is identifiable from the input data. Naturally,CTFIDU + thus subsumes the previous identification algorithms in Table 1. The algorithm works as follows: (a) we first remove re- dundant subscripts from the input query (Line 3-4); (b) we then expand the query into its ancestral set (Line 7); and (c) 5 Causal Identification from Counterfactual Data: Completeness and Bounding Results factorize this expression into smaller ctf-factors which are necessary and sufficient for identifying the query (Line 9); (d) we then process each input distribution (Line 11-14) and run theIDENTIFY + sub-routine using input ctf-factors (Line 16) to try and identify each target ctf-factor. If all the target terms are identified, these are combined into the final value (Line 22), or the algorithm FAILS (Line 20). We summarize these as Steps (i) to (viii) again in App. B.2. Theorem 3.5 (CTFIDU + soundness and completeness). Given an un-nested counterfactual expressionY ⋆ ,P (Y ⋆ = y)is identifiable from a causal diagramGand a set of input distributions A, iff CTFIDU + returns an expression for it. Proof sketch.Any expression returned byCTFIDU + is valid. IfCTFIDU + FAILS, this is because at least one of the necessary ctf-factors could not be identified from the input data. The failure of identification of this ctf-factor means the original query is non-identifiable from the input data. See App. E.1.■ If the input queryP (Y ⋆ = y)involves a nested counter- factual, previous work shows how to first convert the query into an equivalent summation of un-nested terms (Step 0-i. in Fig. 9) which can then individually be fed into Alg. 2. We show in App. B.5 an example of howCTFIDU + correctly retrieves the classic frontdoor-adjustment formula. We also show a more involved running example, where previous methods return FAIL. However,CTFIDU + recognizes the possibility of counterfactual data-collection, and returns an expression in terms of input data. Importantly, the input data is from a different regime than the query, and identification involves a sequence of non-trivial steps (Fig. 12). 4. The Fundamental Limit of Identification A natural follow-up question is how far up the PCH we can go using identification methods - are allL 3 distributions now identifiable, in principle, when data is collected via ctf- rand()? Unfortunately, the answer is no. Next, we proceed to characterize the fundamental limit of exact causal infer- ence from experimental data in the non-parametric setting. Consider the graph in Fig. 5. Suppose we want estimate a counterfactual quantity likeP (y x ∣ x ′ ). As discussed in Sec. 1, there are two approaches one could take. Counterfactual identification uses causal assumptions to reduce the query to a function of available data: for instance,P (y x ∣ x ′ ) = P (y;do(x)). Counterfactual realizability involves directly sampling from the query’s distribution via physical actions: for instance, drawing samples underctf-rand(X → A)to get the distribution table ofP (x ′ ,a x ,y x ,z x ), from which we can directly retrieve the query. Raghavan & Bareinboim (2025, Sec. 3) provided the first formal characterization of the family ofL 3 distributions (a) L 2 X YZ (b) L 2.25 X YZ (c) L 2.5 X YZ Figure 4. Difference in how an intervention onXaffects down- stream variables in L 2 , L 2.25 , and L 2.5 . which can be physically realized given the ability to perform actions like rand() and ctf-rand() on some or more variables. Notably, the authors showed that even if an environment permits maximal ctf-rand() interventions (which may not always be the case), not all distributions are realizable. Yang & Bareinboim (2025, Defs. 11, 12) subsequently introduced a fine-grained segmentation of the PCH based on the experimenter’s data-collection capabilities. Specifically, in addition to the familiarL 1 ,L 2 ,L 3 , they define Layer 2.5 (L 2.5 ) ⊆ L 3 to delineate those counterfactual distributions which are realizable, in principle, if one were able to per- form every possible ctf-rand() action. E.g., the distribution P (y x ,z x ′ ,x ′ )w.r.t the graph in Fig. 4c can be realized by the two ctf-rand() interventions shown, and thus lies in L 2.5 . Layer 2.25(L 2.25 ) ⊆ L 2.5 is a further refinement when ctf-rand() capabilities are more restricted and cannot be performed in a path-specific way, such asP (y x ,z x ,x ′ ) as in Fig. 4b. In contrast,L 2 involves erasing and replacing the natural value of the intervened variable via a standard rand() action, such as P (y,z;do(x)), shown in Fig. 4a. Interestingly, whether a quantity falls withinL 2.5 , i.e., whether its distribution can be realized via ctf-rand(), de- pends on the causal structure, and cannot always be de- termined from the form of the expression alone. For instance, given the graph in Fig. 5, the counterfactual P (y a ∣ z a ′ ,a ′ ) is realizable via ctf-rand() and lies within L 2.5 . ButP (y x ∣ z x ′ ,x ′ )is not physically realizable, and so lies beyond L 2.5 , that is, it belongs in L 3 \ L 2.5 . 4 We can now more formally rephrase the question with which we began this section: whichL 3 distributional quantities are identifiable in principle (for some graphG), given access to some input data fromL 2.5 ? For instance, in Fig. 5, we can show that theL 2 quantityP (y;do(x))is identifiable from theL 1 distributionP (x,y). TheL 3 quantityP (z a ∣ a ′ )is identifiable from theL 2 distributionP (z,a;do(x)). What about the quantityP (y x ∣z x ′ ,x ′ ), can it similarly be identified from some combination of counterfactual data? It turns out there are no identifiable quantities inL 3 \ L 2.5 . I.e., the limits of physical data-collection also impose a theoretical limit on which causal quantities can be point- 4 Raghavan & Bareinboim (2025, Cor. 3.7) gives a simple graphical condition which detects whether a quantity lies inL 2.5 , which we reproduce in Thm. C.2 for ease of reference. 6 Causal Identification from Counterfactual Data: Completeness and Bounding Results Causal diagram G X A Z Y Figure 5.L 2.5 marks the theoretical limit of exact causal inference in the non-parametric setting (Thm. 4.1). Every layer of the PCH contains queries that may be identifiable using data from lower layers, except L 3 \ L 2.5 . identified in the non-parametric setting. Theorem 4.1 (Limit of identification). Given a queryQ belonging toL i of the PCH and no lower layer, for every j < ithere exists a graphGs.t.Qis identifiable fromGand input data from L j , except for i = 3.■ Perhaps surprisingly, this result means that there areL 2 queries identifiable fromL 1 data,L 2.25 queries identifiable fromL 2 data, andL 2.5 queries identifiable fromL 2.25 data, but no purely-L 3 queries identifiable fromL 2.5 data. E.g., in Fig. 5,P (y x ∣z x ′ ,x ′ )is fundamentally non-identifiable even from other realizable counterfactual data. This barrier has considerable practical implications. E.g., take theL 3 quantity known as the natural total effect, or NTE (Lee et al., 2025, Def. 2). While the details are out of scope, NTE is an important tool in the field of explainable AI (XAI). Thee-specific NTE is defined asNTE(X,Y ∣ e) = E u∼P (U∣e),u ′ ∼P (U) [Y X(u) (u) − Y X(u ′ ) (u)](7) The first termE[Y X(u) (u)]works out to the expected ob- servational outcomeE[Y ]. For a sub-population observed to haveE = e(E ⊆ V), the second term captures how the outcome would be affected ifXwere fixed by re-sampling from the observational distributionP (X). This difference intuitively summarizes an explanation of howXaffected an outcome Y = y (see Bareinboim, 2025, Sec. 6.2.2.1). For the example in Fig. 1, settingX = Xande = (x ′ ,y ′ ), the second term in Eq. 7 works out to E u∼P (U∣x ′ ,y ′ ),u ′ ∼P (U) [Y X(u ′ ) (u)] = ∑ y,u ′ y.P (Y X(u ′ ) = y ∣ x ′ ,y ′ )P (u ′ )(8) = ∑ y,x y.P (y x ∣ x ′ ,y ′ )P (x)(9) P (y x ∣ x ′ ,y ′ )is one of the famed probabilities of causation (Pearl, 1999). It can be shown that this quantity belongs to L 3 \ L 2.5 . So, by Thm. 4.1, NTE cannot be identified, even with sophisticated counterfactual experimental capabilities - a relevant finding for the XAI community. Further, Thm. 4.1 points to a foundational connection between the seem- ingly orthogonal notions of counterfactual realizability and counterfactual identification. Corollary 4.2 (Id - realizability duality (informal)). A query Qis identifiable from experimental and observational data and graphG, if and only if it is realizable, in principle, using ctf-rand() actions.■ The key insight of this duality is that non-parametric identi- fication of any causal quantity is essentially trying to mimic realizability: any identifiable query should be answerable by sampling from a regime where we can, in principle, jointly observe each variable under randomized interventions of its parents (i.e., a ctf-rand() for every graph edge). This marks the limit of our data-collection capabilities, so if a query is still not realizable even in principle, such asP (y x ∣ z x ,x ′ ) in Fig. 5, it means this query involves some confounding that cannot be disambiguated with any experimental data. For the interested reader, we present in App. C.3 an intu- ition for this interplay using a causal lattice consisting of all combinations of the ctf-factors generated from a realizable input distribution, and show how the ”level of inconsistency” at bottleneck nodes limits the PCH level of higher-order lat- tice combinations. This perspective could inform future research into algorithm- and experiment-design for com- puting higher-order counterfactuals like NTE, such as by incorporating stronger assumptions to overcome bottlenecks along identification pathways. 5. Partial Identification using Ctf-Data In this section, we show that even when a quantity is non- identifiable, the possibility of accessing counterfactual data through ctf-rand() can be used to derive provably tighter bounds for the range this quantity can take. Sec. 4 discussed the task of point identification, and con- cluded that causal quantities beyondL 2.5 , such as the NTE, are non-identifiable from physically realizable data, in the non-parametric setting. Next, we discuss the partial identifi- 7 Causal Identification from Counterfactual Data: Completeness and Bounding Results (a) L 1 XY (b) L 2 XY (c) L 2.5 XY Bounds for NTE using data from L 1 L 2 L 2.5 Figure 6. Increasingly tighter partial identification bounds for NTE using data from (a) L 1 , (b) L 2 , and (c) L 2.5 regimes. cation of such causal quantities: given a causal diagram, we seek to use the available observational/experimental data to bound the range of possible values of this non-identifiable quantity. The bounds of this range are called tight if it is the smallest interval s.t. there exist SCMs where the causal quantity takes the boundary values (among the space of SCMs which satisfy the causal graph and the input data con- straints). A range is uninformative if the bounds are[0, 1]. If a quantity is exactly identifiable, the tight range is simply a point value, computable using the CTFIDU + algorithm. Tian & Pearl (2000) first provided tight analytic bounds for non-identifiable counterfactuals known as the probabilities of causation, or PCs, which include quantities likeP (y x ∣ x ′ ,y ′ ) andP (y x ,y ′ x ′ ) , assuming binary treatment. Shu et al. (2025) generalized this to bounds for PCs under non-binary treatments. These prior works all assume the input data is limited to observational or interventional distributions. It stands to reason that adding more input data using ctf-rand() can only tighten bounds further - if the constraint set is larger, the space of SCMs that satisfy it (and thus, the range of possible values of the indentification query) is smaller. Proposition 5.1. Given causal diagramGand queryQ = P (y ⋆ ) , let[l,r] A ⊆ [0, 1]be the tight partial identification bounds forQgiven input data regimesA. Then, for any A ′ ⊃ A, the bounds [l,r] A ′ ⊆ [l,r] A .■ To make this concrete, consider the bow graph (Fig. 6.a) - a causal structure broadly representative of any real-world bivariate system where causation and unobserved confound- ing cannot be ruled out. For such environments, we next derive novel analytic bounds for NTE that are provably tighter than prior work, using realizable counterfactual data. Specifically, suppose we want tight identification bounds for the(x ′ ,y ′ )-specific NTE (Eq. 7). From Eq. 9, assuming that observational dataP (x)is already available, the bounds for NTE are determined byP (y x ∣ x ′ ,y ′ ). Hence, we focus on deriving analytic bounds for this term. If only observational dataP (V)is available, the bounds for P (y x ∣ x ′ ,y ′ )are uninformative, i.e., the range is the whole unit interval, as shown in yellow in Fig. 6. Bounds for NTE: P (y x ∣ x ′ ,y ′ ) NDE: P (y xZ x ′ ) truth L 2 range L 2.5 range analytic Figure 7. Example 2: partial identification bounds for NTE and NDE quantities. A density plot of values is generated by sampling from a Bayesian posterior over SCMs, given synthetic input data. The end-points of the range of values along the X-axis mark the empirically estimated range each quantity can take. Bounds are tighter when estimated using counterfactual data (blue) than inter- ventional data (orange). Since NDE is exactly identifiable from counterfactual data, blue bounds collapse to the true value (red). Lemma 5.2 (NTE -L 1 bounds). Given a bow graph causal structure (Fig. 6.a) and observational dataP (X,Y ), the identification queryP (y x ∣ x ′ ,y ′ ),x ≠ x ′ ,is tightly bounded in the range [0, 1].■ If interventional data from a standard RCT is also available, this begets more informative and tighter bounds in terms of P (y x ), depicted in orange in Fig. 6. Lemma 5.3 (NTE -L 2 bounds). Given a bow graph causal structure (Fig. 6.a), observational dataP (X,Y ), and inter- ventional dataP (Y x ),∀x, the queryP (y x ∣ x ′ ,y ′ ),x ≠ x ′ , is tightly bounded in the range [l,r] defined as l = max 0, α min − (1 − P (y ′ ∣ x ′ )) P (y ′ ∣ x ′ ) (10) r = min 1, α max P (y ′ ∣ x ′ ) , where(11) α min ∶= max 0, P (y x ) − (1 − P (x ′ )) P (x ′ ) (12) α max ∶= min 1, P (y x ) P (x ′ ) (13) Further, [l,r] ⊆ [0, 1]■ However, if the environment permits counterfactual data collection using ctf-rand(), this can be used to derive tighter bounds than the state of the art approach in Lem. 5.3, as shown in blue in Fig. 6. The novel bounds are as follows. Proposition 5.4 (NTE -L 2.5 bounds). Given a bow graph causal structure (Fig. 6.a), observational dataP (X,Y ), interventional dataP (Y x ), and counterfactual dataP (Y x ∣ X) ,∀x, the identification queryP (y x ∣ x ′ ,y ′ ),x ≠ x ′ ,is 8 Causal Identification from Counterfactual Data: Completeness and Bounding Results benefit per strategy L 2 L 2.5 sub-population ∆(1 ∣ X) bounds population-level ∆(1) bounds X = 1X = 0 Figure 8. Example 3: (Left) benefit function by unit type; (Centre) estimated bounds of population-level benefit usingL 2 data (orange) and sub-population level benefit using L 2.5 data (blue); (Right) counterfactual strategy dominates standard interventional approach. tightly bounded in the range [l ′ ,r ′ ] defined as l ′ = max 0, P (y x ∣ x ′ ) − (1 − P (y ′ ∣ x ′ )) P (y ′ ∣ x ′ ) (14) r ′ = min 1, P (y x ∣ x ′ ) P (y ′ ∣ x ′ ) (15) Further, [l ′ ,r ′ ] ⊆ [l,r] as defined in Lem. 5.3.■ The new bounds are contained within the previous bounds when using onlyL 2 data. The upshot of these results is that the standard approach in causal data science of using only observational and interventional data to bound impor- tant counterfactual quantities gives us loose bounds, which can be significantly improved if we could design exper- iments that permit counterfactual randomization. Future work could develop a more general framework to derive tighter bounds for arbitrary counterfactual queries. As men- tioned, the bounds for such counterfactuals are relevant in applications like algorithmic fairness and explainability. Finally, we provide two examples illustrating how counter- factual data can, in practice, be used to empirically tighten bounds for identification queries. We use a Bayesian sam- pling methodology to estimate a(1 − β)credible interval for the range of an identification query, and show that the range is tighter in practice when applying ctf-rand(). Example 2 (Traffic Camera - version 2). Consider an expanded version of Example 1.LetY,Z ∈ 0, 1, X ∈ 0, 1, 2. We now allow confounding between both (X,Y )and(Z,Y ), to account for unlabeled driver tenden- cies affecting car color choice, or road obstructions affecting speeding, both of which may appear as video artifacts. This, of course, is a relaxation of the earlier non-confounding (or ignorability) assumption w.r.t X . The goal is to bound two identification queries: the NDE quantityP (y xZ x ′ ) (see Eq. 3), and the NTE quantityP (y x ∣ x ′ ,y ′ )(see Eq. 9), which would help an auditor in fairness analysis and explanation-generation for the AI model used in this application. We evaluate bounds under two settings: (i) input containsL 1 data (from observational studies) and L 2 data (fromdo(x)distributions); and (i) input contains L 2.5 data obtained through ctf-rand() (Fig. 1b). We collect N = 10 4 synthetic samples per input distribution from a randomly generated (unobserved) SCM, and use this input data to empirically bound the queries by the methodology outlined earlier. The results are shown in Fig. 7. We show the 95% credible interval (ci) for each query under both data settings: orange plots give the bounds when using onlyL 2 data, and blue plots give the bounds when usingL 2.5 data. The range of these plots along the X-axis gives us the empirically estimated range that the query can take. The true value of the query is indicated by a red line. For NTE, the analytic bounds computed directly using Lem. 5.3 and Prop. 5.4 are additionally indicated with dotted lines. For both queries, the range of sampled values is signifi- cantly narrower along the X-axis for the blue plot than the orange plot, indicating thatL 2.5 data gives us tighter empir- ical bounds. For NDE, usingL 2.5 data causes the bounds (blue) to collapse to the true value (red line). This validates the results in Sec. 3 and theCTFIDU + algorithm since, as derived in Eq. 3, NDE is indeed identifiable using counter- factual randomization. These findings are consistent across five random SCM specifications. Details of the sampling process, and the random SCMs are provided in App. D.1. Example 3 (Unit Selection, Li & Pearl (2019)). Consider a drug de-addiction program with the causal diagram in Fig. 6a.Xindicates whether a participant is assigned counsel- ing sessions.Yindicates whether de-addiction succeeds within 6 months. Each participant belongs to one of four canonical types (Angrist et al., 1996; Balke & Pearl, 1997) defined in Fig. 8(left). E.g., the Helped type of partici- pant(Y X=0 = 0,Y X=1 = 1)would overcome addiction iff offered counseling, while the Always-0 type of partic- ipant(Y X=0 = 0,Y X=1 = 0)does not succeed within 6 months whether they received counseling or not. Any given participant’s unit type and the probability of each type in the population are unknown. A unit selection problem as- signs a benefit∆(1 ∣ type)for each unit type receiving treatment, asγ,α,λ,δ, respectively. The baseline benefit of non-treatment,∆(0 ∣ type), is zero for all. The goal is to maximize avg. treatment benefit, given input data from 9 Causal Identification from Counterfactual Data: Completeness and Bounding Results observations/experiments. 5 We evaluate two strategies: (1) the standard approach in- troduced in Li & Pearl (2022) of usingL 1 andL 2 data to empirically bound the quantityP (y ′ X=0 ,y X=1 ),∀y,y ′ , then combining these bounds to bound the avg.∆(1)over the population, and thus decide whether to applydo(X = 1)for the whole population; (2) a counterfactual decision strategy (Bareinboim et al., 2015; Raghavan & Bareinboim, 2025) using ctf-rand() to collectL 2.5 data, then using this to bound P (y ′ X=0 ,y X=1 ∣x ′ ), and thus estimate the conditional avg. benefit∆(1∣X)for units who would have naturally been assignedX = x ′ . Since the environment permits ctf-rand(), each unit’s natural decisionXcan be measured prior to assigning a treatment (Fig. 6c), so these conditional esti- mates can be used to decide separately whether to apply do(X = 1) for each subpopulation with natural X = x ′ . The results are shown in Fig. 8(center, right). The 95% ci for population bounds estimated by the standard interven- tional approach (1) are [−1.3, 1.6], shown in orange. The subpopulation bounds computed using the counterfactual ap- proach (2) are [5.7, 11.6] and[−2.5,−0.1]for units whose naturalX = 0, 1respectively, shown in blue. Therefore, strategy (2) counterintuitively assigns treatmentdo(X = 1) only to units who would have naturally receivedX = 0, as their benefit range is entirely positive. Strategy (1) is strictly suboptimal as it either assigns 0 to everyone, or forces 1 even on units with naturalX = 1, for whom the benefit range is entirely negative. Further details of input data and the counterfactual strategy are provided in App. D.2. 6. Conclusion In this paper, we developed theCTFIDU + algorithm (Alg. 2), a complete method for identifying counterfactuals given an arbitrary collection of physically realizable input data (Thm. 3.5). Previous completeness results for counterfac- tual identification were derived under the assumption that available data is restricted toL 1 andL 2 of the PCH, not recognizing the possibility ofL 3 data collection through the procedure of counterfactual randomization. We then showed that the theoretical limit to exact counterfactual identification in nonparametric settings coincides with the limits of counterfactual data-collection, demonstrating a foundational duality between counterfactual identifiability and realizability (Thm. 4.1, Cor. 4.2). Finally, we demon- strate that counterfactual data remains valuable even when exact identification is impossible. By incorporating such data, we derive novel analytic bounds for the counterfactual NTE quantity which are tighter than prior approaches that use onlyL 2 data (Prop. 5.4). Our simulations confirm that 5 As a special case, ifγ = δ = 0andλ = −α, this works out to maximizing the avg. treatment effect (ATE) of X on Y . this additional data can yield substantially sharper partial identification intervals in practice. Future work could explore systematic ways to select coun- terfactual interventions for experiment design that provide the tightest identification bounds. The duality result in Cor. 4.2 could also inform more principled strategies for adopt- ing stronger assumptions (structural causal, parametric etc.) to overcome non-identification hurdles. Acknowledgements This research is supported in part by the NSF, ONR, AFOSR, DoE, Amazon, JP Morgan, and The Alfred P. Sloan Foun- dation. Impact Statement This paper presents work whose goal is to advance the field of Machine Learning, and the limits of what can be inferred from data. There are many potential societal consequences of our work, none which we feel must be specifically high- lighted here. References Angrist, J. D., Imbens, G. W., and Rubin, D. B. Identifica- tion of causal effects using instrumental variables (with Comments). Journal of the American Statistical Associa- tion, 91(434):444–472, 1996. Avin, C., Shpitser, I., and Pearl, J. Identifiability of Path- Specific Effects. In Proceedings of the Nineteenth In- ternational Joint Conference on Artificial Intelligence IJCAI-05, p. 357–363, Edinburgh, UK, 2005. Morgan- Kaufmann Publishers. Balke, A. and Pearl, J. Counterfactual Probabilities: Compu- tational Methods, Bounds, and Applications. In de Man- taras, R. L. and D. ̃Poole (eds.), Uncertainty in Artificial Intelligence 10, p. 46–54. Morgan Kaufmann, San Ma- teo, CA, 1994. Balke, A. and Pearl, J. Bounds on treatment effects from studies with imperfect compliance. Journal of the Ameri- can Statistical Association, 92(439):1172–1176, 9 1997. Bareinboim, E. Causal Artificial Intelligence: A Roadmap for Building Causally Intelligent Systems. 2025. URL https://causalai-book.net/. Bareinboim, E., Forney, A., and Pearl, J. Bandits with unob- served confounders: A causal approach. In Advances in Neural Information Processing Systems, p. 1342–1350, 2015. 10 Causal Identification from Counterfactual Data: Completeness and Bounding Results Bareinboim, E., Correa, J. D., Ibeling, D., and Icard, T. On Pearl’s Hierarchy and the foundations of causal inference. In Probabilistic and Causal Inference: The Works of Judea Pearl, p. 507–556. Association for Computing Machinery, New York, NY, USA, 1st edition, 2022. Correa, J. and Bareinboim, E. Counterfactual graphical models: Constraints and inference. Technical Report R-115, Causal Artificial Intelligence Lab, Columbia Uni- versity, July 2025. URLhttps://causalai.net/ r115.pdf. Correa, J., Lee, S., and Bareinboim, E. Nested counterfac- tual identification from arbitrary surrogate experiments. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Infor- mation Processing Systems, volume 34, p. 6856–6867. Curran Associates, Inc., 2021. Correa, J. D., Lee, S., and Bareinboim, E. Counterfactual transportability: A formal approach. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Confer- ence on Machine Learning, volume 162 of Proceedings of Machine Learning Research, p. 4370–4390. PMLR, 17–23 Jul 2022. Dawid, A. P. Causal Inference Without Counterfactuals (with Comments and Rejoinder). Journal of the American Statistical Association, 95(450):407–448, 2000. Forney, A., Pearl, J., and Bareinboim, E. Counterfactual Data-Fusion for Online Reinforcement Learners. In Pro- ceedings of the 34th International Conference on Ma- chine Learning, 2017. ISBN 9781510855144. doi: http://dx.doi.org/10.1037/a0022750. Ibeling, D. and Icard, T. Probabilistic reasoning across the causal hierarchy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, p. 10170–10177, 2020. Kocaoglu, M., Shanmugam, K., and Bareinboim, E. Experi- mental Design for Learning Causal Graphs with Latent Variables. In Advances in Neural Information Processing Systems 30, 2017. ISBN 0327-3776, 1850-275X. doi: 10.1017/CBO9781107415324.004. Lee, K. Z., Plecko, D., and Bareinboim, E. Causal explana- tions through counterfactual variable attributions. Techni- cal Report R-135, Columbia Causal AI Laboratory, May 2025. URLhttps://causalai.net/r135.pdf. Columbia CausalAI Laboratory, Technical Report (R- 135). Lee, S., Correa, J. D., and Bareinboim, E. General Identifia- bility with Arbitrary Surrogate Experiments. In Proceed- ings of the Thirty-Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence, Corvallis, OR, 2019. AUAI Press. Li, A. and Pearl, J. Unit selection based on counterfactual logic. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, p. 1793–1799. International Joint Conferences on Artificial Intelligence Organization, 7 2019. Li, A. and Pearl, J. Unit selection with causal diagram. Proceedings of the AAAI Conference on Artificial In- telligence, 36(5):5765–5772, Jun. 2022. doi: 10.1609/ aaai.v36i5.20519. URLhttps://ojs.aaai.org/ index.php/AAAI/article/view/20519. Li, A., Jaber, A., and Bareinboim, E. Causal discovery from observational and interventional data across multiple en- vironments. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, 2023. Malinsky, D., Shpitser, I., and Richardson, T. A poten- tial outcomes calculus for identifying conditional path- specific effects. In Chaudhuri, K. and Sugiyama, M. (eds.), Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, vol- ume 89 of Proceedings of Machine Learning Research, p. 3080–3088. PMLR, 16–18 Apr 2019. Mueller, S. and Pearl, J. Personalized decision making – a conceptual introduction. Journal of Causal Inference, 11 (1):20220050, 2023. Pearl, J. Probabilities of causation: Three counterfactual interpretations and their identification. Synthese, 121 (1–2):93–149, 11 1999. Pearl, J. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, NY, USA, 2nd edition, 2000. ISBN 978-0-521-89560-6. Pearl, J. Direct and indirect effects. In Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intel- ligence, p. 411–420. Morgan Kaufmann, San Francisco, CA, 2001. Pearl, J. and Mackenzie, D. The Book of Why. Basic Books, New York, 2018. ISBN 978-0-465-09760-9. Plecko, D. and Bareinboim, E. Causal fairness analysis: A causal toolkit for fair machine learning. Foundations and Trends in Machine Learning, 17(3):304–589, Jan 2024. Raghavan, A. and Bareinboim, E. Counterfactual realiz- ability. In The Thirteenth International Conference on Learning Representations, number R-113, 2025. URL https://arxiv.org/abs/2503.11870. 11 Causal Identification from Counterfactual Data: Completeness and Bounding Results Rubin, D. B. Direct and indirect causal effects via potential outcomes. Scandinavian Journal of Statistics, 31:161– 170, 2004. Shpitser, I. and Pearl, J. Identification of Joint Interventional Distributions in Recursive semi-Markovian Causal Mod- els. In Proceedings of the Twenty-First AAAI Conference on Artificial Intelligence, volume 2, p. 1219–1226, 2006. ISBN 978-1-57735-281-5. URLhttp://dl.acm. org/citation.cfm?id=1597348.1597382. Shpitser, I. and Pearl, J. What Counterfactuals Can Be Tested. In Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence, p. 352–359. AUAI Press, Vancouver, BC, Canada, 2007. Shpitser, I. and Pearl, J. Complete Identification Methods for the Causal Hierarchy. Journal of Machine Learning Research, 9:1941–1979, 2008. Shu, X., Wang, S., and Li, A. Identification of probabilities of causation: A complete characterization. 2025. URL https://arxiv.org/abs/2505.15274. Spirtes, P., Glymour, C. N., and Scheines, R. Causation, Prediction, and Search. MIT Press, Cambridge, MA, 2nd edition, 2000. Tian, J. and Pearl, J.Probabilities of causation: Bounds and identification.28(1–4):287–313, Jan- uary 2000.ISSN 1012-2443.doi:10.1023/ A:1018912507879.URLhttps://doi.org/10. 1023/A:1018912507879. Tian, J. and Pearl, J. On the identification of causal effects. Technical Report R-290-L, Department of Computer Sci- ence, University of California, Los Angeles, CA, 2003. von K ̈ ugelgen, J., Besserve, M., Wendong, L., Gresele, L., Keki ́ c, A., Bareinboim, E., Blei, D. M., and Sch ̈ olkopf, B. Nonparametric identifiability of causal representa- tions from unknown interventions. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, 2023. Yang, H. and Bareinboim, E.A hierarchy of graphi- cal models for counterfactual inferences. In Proceed- ings of the 39th International Conference on Neural In- formation Processing Systems, November 2025. URL https://causalai.net/r130.pdf. Columbia CausalAI Laboratory, Technical Report (R-130). Zhang, J. and Bareinboim, E. Fairness in Decision-Making- The Causal Explanation Formula. In AAAI Conference on Artificial Intelligence, 2018. doi: 10.1016/j.energy.2007. 09.003. Zhang, J. and Bareinboim, E. Can humans be out of the loop? In Sch ̈ olkopf, B., Uhler, C., and Zhang, K. (eds.), Proceedings of the First Conference on Causal Learning and Reasoning, volume 177 of Proceedings of Machine Learning Research, p. 1010–1025. PMLR, 11–13 Apr 2022. Zhang, J., Tian, J., and Bareinboim, E. Partial counterfactual identification from observational and experimental data. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, p. 26548–26558. PMLR, 17–23 Jul 2022. 12 Causal Identification from Counterfactual Data: Completeness and Bounding Results Appendix Contents A Graphical terminology14 B Tools for Counterfactual Identification14 B.1 Previous Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14 B.2 Steps to identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16 B.3 Complexity of CTFIDU + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 B.4 Example using IDENTIFY + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18 B.5 Examples using CTFIDU + . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19 C Limits of Identification and Realizability21 C.1 Layer 2.5 (L 2.5 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21 C.2 Layer 2.25 (L 2.25 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22 C.3 Causal lattice framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23 D Partial Identification: Example Details24 D.1 Example 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 D.2 Example 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 E Proofs of Results27 E.1 Proofs for Sec. 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27 E.2 Proofs for Sec. 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31 E.3 Proofs for Sec. 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33 F Indexing an Input Data Distribution34 G Frequently Asked Questions36 13 Causal Identification from Counterfactual Data: Completeness and Bounding Results A. Graphical terminology Structural Causal Models (SCM) and causal diagrams are described in the preliminaries in Sec. 1. See Bareinboim et al. (2022) for full treatment. We use the following graphical kinship nomenclature w.r.t causal diagram G: • Parents of V i , denoted Pa i : the set V j s.t. there is a direct edge V j → V i in G. Pa i does not include V i . • Children of V i , denoted Ch(V i ): the set V j s.t. there is a direct edge V i → V j in G. Ch(V i ) does not include V i . •Ancestors ofV i , denotedAn(V i ): the setV j s.t. there is a path (possibly length 0) fromV j toV i consisting only of edges pointing toward V i , V j → ...→ V i . An(V i ) is defined to include V i . •Descendants ofV i , denotedDesc(V i ): the setV j s.t. there is a path (possibly length 0) fromV i toV j consisting only of edges pointing toward V j , V i → ...→ V j . Desc(V i ) is defined to include V i . • Non-descendants of V i , denoted NDesc(V i ): the set V \ Desc(V i ). NDesc(V i ) does not include V i . Given a graph G, G XW is the result of removing edges coming into variables in X, and edges coming out of W. G[W] denotes a vertex-induced subgraph, which includes onlyWand the edges among its elements.G[V(W ⋆ )]denotes the subgraph which includes only the vertices V ∣ V x ∈ W ⋆ and the edges among its elements. B. Tools for Counterfactual Identification In this appendix, we summarize all the components used in the task of counterfactual identification, including a review of prior work. Sec. B.1 can be skipped or skimmed if readers are already familiar with these results. B.1. Previous Results Below are some relevant conceptual components developed in prior work (Correa et al., 2021; Correa & Bareinboim, 2025). Given an arbitrarily nested counterfactual expression, the Counterfactual Un-nesting Theorem, or CUT, provides a way to compute it in terms of un-nested probability terms. Theorem B.1 (Counterfactual Un-nesting Theorem (CUT)). LetY,X ∈ V, T, Z ⊆ V, and letzbe a set of values forZ. Then, the nested counterfactual P (Y T ⋆ X z = y) can be written as an un-nested counterfactual, as follows: P (Y T ⋆ X z = y) = ∑ x P (Y T ⋆ x = y,X z = x),(16) where the subscript ⋆ is a wildcard for an arbitrarily nested counterfactual clause.■ This can be recursively applied to get fully un-nested terms. For instance, for the diagram in Fig. 1, we can write P (y xZ x ′ ) = ∑ z P (y zw ,z x ′ ). Definition B.2 (Ancestors of a counterfactual). Given a causal diagram G and a potential response Y x , the set of (counter- factual) ancestors ofY x , denotedAn(Y x ), consists of eachW z s.t.W ∈ An(Y ) G X , andz = x ∩ An(W ) G X . For a set W ⋆ , An(W ⋆ ) is defined to be the union of the ancestors of each potential response in the set.■ This generalizes the notion of ancestors of a causal variable to the ancestors of potential responses under different regimes. For instance, for the diagram in Fig. 1, An(Y x ) = Y x ,Z x and An(Y z ) = Y z ,X. Lemma B.3 (Exclusion operator). The exclusion operator∣.∣when applied to a potential response returns the minimal counterfactual subscript set, removing redundant interventions (e.g. non-ancestors) from the subscript. Consider a causal diagram G and a potential response Y x . Let ∣Y x ∣ ∶= Y z , where Z = X ∩ An(Y ) G X and z = x ∩ Z. Then, ∣Y x ∣ = Y x holds for any model compatible with G.■ If a counterfactual expression is ancestral (i.e. it contains its own ancestors), the following results shows how to convert it into a ctf-factor expression, and further decompose it based on c-components. 14 Causal Identification from Counterfactual Data: Completeness and Bounding Results Theorem B.4 (Ancestral Set Transformation (AST)). LetW ⋆ be an ancestral set, that is,An(W ⋆ ) = W ⋆ , and letwbe a vector with the values of each variable in W ⋆ . Then, P (W ⋆ = w) can be rewritten in ctf-factor format as follows, P (W ⋆ = w) = P ( ⋀ W t ∈W ⋆ W pa W = w),(17) where each w is w t and pa w is determined for each W t ∈ W ⋆ as follows: (i) the values for variables in Pa w ∩ T are the same as in t, and (i) the values for variables in Pa w \ T are taken from w corresponding to the parents of W.■ Theorem B.5 (Counterfactual factorization). LetQ[H ⋆ ](h) = P (H ⋆ = h)be a ctf-factor. LetH 1 ,..., H m be the c-components inG[V(H ⋆ )]. DefineH i ⋆ = H pa h ∈ H ⋆ ∣ H ∈ H i andh i as the values inhcorresponding toH i ⋆ . Note that H 1 ⋆ ,..., H m ⋆ form a partition of H ⋆ . Then, we have that Q[H ⋆ ](h) decomposes as Q[H ⋆ ](h) = P (H ⋆ = h) = ∏ i P (H i ⋆ = h i )(18) Furthermore, letH 1 < H 2 < ...be a topological order over the variables inG[V(H ⋆ )]. Then, each factor can be computed from P (H ⋆ = h) as Q[H i ⋆ ](h i ) = P (H i ⋆ = h i ) = ∏ H j ∈H i ∑ h∣H pa h ∈H ⋆ ,H j <H P (H ⋆ = h) ∑ h∣H pa h ∈H ⋆ ,H j−1 <H P (H ⋆ = h) (19) ■ Next, we discuss how to classify a ctf-factor as ”consistent”, based on conflicts in the counterfactual terms. And how to convert a consistent ctf-factor into a Layer 2 c-factor. Definition B.6 (Consistent ctf-factor). A ctf-factorQ[C ⋆ ](c) = P (C ⋆ = c)is called consistent if it does not contain two counterfactualsX pa x ,Y pa y ∈ C ⋆ with valuesx,ysuch that any pair of values inx ∪ y ∪ pa x ∪ pa y conflict. Otherwise, the ctf-factor is called inconsistent.■ Lemma B.7 (Collapsing operation). If a ctf-factorQ[C ⋆ ](c)is consistent, then it is equivalent to the Layer 2 confounded (c-) factor, as follows, Q[C ⋆ ](c) = Q[C](v), with v consistent with c and the subscripts in C ⋆ ,(20) where the c-factor is defined in Eq. 6.■ Finally, we reproduce for ease of reference the classic IDENTIFY algorithm that provides a method to identify a Layer 2 c-factor from an input c-factor. Algorithm 3 IDENTIFY (Tian & Pearl, 2003, Sec. 4.4) 1: Input: Causal diagram G; set C ⊆ T ⊆ V s.t. G[T] has one single c-component; c-factor Q[T](v) 2: Output: Expression for Q[C](v) in terms of Q[T](v); or FAIL 3: Let H ∶= An(C) in G T 4: if H = C then 5:Return Q[C](v) = ∑ t Q[T](v) 6: else if H = T then 7:Return FAIL 8: else if C ⊂ H ⊂ T then 9: Q[H](v) = ∑ t Q[T](v) 10:Let H i be the ctf c-component in H according to G H s.t. C ⊆ H i 11:Compute Q[H i ](v) from Q[H](v) using Theorem B.8 12:Return IDENTIFY(G, C,Q[H i ](v)) 13: end if 15 Causal Identification from Counterfactual Data: Completeness and Bounding Results Theorem B.8 (C-factor decomposition (Lem. 4, ibid.)). GivenH ⊆ V, letHbe partitioned into c-componentsH 1 ,..., H m in the subgraph G H . Then, Q[H](v) decomposes as Q[H](v) = ∏ i Q[H i ](v)(21) Furthermore, letH 1 < H 2 < ...be a topological ordering of the variables inG[H]. LetH (≤j) ∶= H 1 ,...,H j be the set of variables inHordered up to and includingH j , withH (≤0) ∶= ∅. Then, eachQ[H i ]is computable fromQ[H](v)and given by Q[H i ] = ∏ H j ∈H i Q[H (≤j) ] Q[H (≤j−1) ] ,(22) where each Q[H (≤j) ](v) can be computed simply as Q[H (≤j) ] = ∑ h (≤j) Q[H](23) The vector (v) is omitted from Eqs. 22,23 for legibility.■ B.2. Steps to identification We summarize in Fig. 9 the steps involved in algorithmic identification from counterfactual (Layer 3) data. As a pre-processing step, if the query is a nested counterfactual P (Y ′ ⋆ = y ′ ), Steps 0:Map it to un-nested terms,P (Y ⋆ = y)using the Un-Nesting Theorem (Thm. B.1) which is now the input to the CTFIDU + algorithm. Steps i-v of CTFIDU + (Alg. 2) involve Steps i:Remove any redundant subscripts (such as interventions on non-ancestors) or trivial counterfactuals (Lines 3-6) Step i-iv:Expand the query into the set of its counterfactual ancestors (Def. B.2) (Line 7); identifying this expression is both necessary and sufficient to identify the query; re-write this expression in ctf-factor format (Line 8); Steps v: Factorize this ctf-factor into smaller ctf-factors based on the confounding structure in the graph, using the ctf-factorization formulas (Thm. B.5); identifying each of these smaller ctf-factors is both necessary and sufficient to identify the query (Line 9). These steps are the same as the prior work which designed the CTFID algorithm (Correa et al., 2021, Alg. 1) for counterfactual identification from Layer 2 data, we merely extend the proof of necessity of Step i. for Layer 3 input data. After this stage, the prior CTFID maps each of these ctf-factor terms to Layer 2 c-factors only if it is ”consistent”, and then applies the celebrated IDENTIFY algorithm to identify each of these c-factors from input Layer 2 data (gray-dotted box, Steps vi-x in Fig. 9). If all ctf-factors in Step v. are thus identified, these terms can be chained to compute the query. Otherwise, identification FAILS. By contrast, Steps vi-viii of the new CTFIDU + algorithm (red boxes in Fig. 9) involve: Steps vi: For each input data regimeA, pre-process using the helper function and AST Thm. to generate the input data expression in ctf-factor format (Line 11-12); Steps vii: Map this to the smaller ctf-factors we can compute from this data, based on confounding structure (Line 13-14). These ctf-factors are sufficient to identify the query, if it is identifiable from the input data; Steps viii:For each query ctf-factor, find an input ctf-factor that contains it, and run the novelIDENTIFY + algorithm to identify the query term from the input term (Line 16); 16 Causal Identification from Counterfactual Data: Completeness and Bounding Results Nested counterfactual, P (Y ′ ⋆ = y ′ ) Step 0. Un-nested counterfactual, P (Y ⋆ = y) Step i. (Query) CUT (Thm. B.1) Redundant subcripts removed, P (Y ⋆ = y) Step i. (Line 3) Exclusion op. (Lem. B.3) An(Y ⋆ ) (Def. B.2) Ancestral expression, P (W ⋆ = w) Step i. (Line 7)Step iv. (Line 8) AST (Thm. B.4) Ctf-factor, P (W ⋆ = w) Ctf-factorization (Thm. B.5) Step v. (Line 9) Factors by c-components, P (C j ⋆ = c j ), j = 1...k Deprecated steps (from earlier CTFID alg.) ∀j, Consistency check (Def. B.6) Consistent ctf-factor, P (C j ⋆ = c j ) Step vi.Step vii. Layer 2 c-factor, Q[C j ](c j ) Collapsing operation (Lem. B.7) C-factor decomposition (Thm. B.8) Step viii. (Layer 2 input data) Input data distributions, P (v;do(z)), Z ∈ Z Step ix. ∀i Input c-factors, Q[T i ](t i ), i = 1...m Step x. IDENTIFY(G, C j ,Q[T i ](t i )) (Alg. 3) ID expression FAIL Step viii. (Line 16) IDENTIFY + (G,Q[C j ⋆ ],Q[T i ⋆ ]) (Alg. 1) ID expression FAIL Step vii. (Lines 13-14) ∀i Input ctf-factors, Q[T i ⋆ ](t i ), i = 1...m Ctf-factorization (Thm. B.5) Step vi. (Layer 3 input data - Line 11-12) Input data distributions, P A (T ⋆ = t), A ∈ A Pre-processing: Alg. 4, AST (Thm. B.4) Figure 9. Algorithmic steps for counterfactual identification. Steps in the Gray-dotted box illustrate the deprecated steps of the old CTFID algorithm from prior work (Correa et al., 2021), which only allows identification from Layer 2 input data. Red boxes illustrate the new CTFIDU + algorithm (Alg. 2), which allows identification from Layer 3 input data. Steps 0-v are shared by both. If all query ctf-factors from Step v. are identified in Step viii, these terms can be chained to identify the query (Line 22). Otherwise, identification FAILS. The necessity and sufficiency of each step (in particular, theIDENTIFY + subroutine) provide the proof for the soundness and completeness of the CTFIDU + algorithm (Thm. 3.5). B.3. Complexity of CTFIDU + It was shown by Correa & Bareinboim (2025) that constructing an ancestor set forY ⋆ isO(z(n + m)), wheren,m,z,and drefer to the number of nodes, edges, (different) interventions inY ⋆ , and maximum cardinality of any observable variable inG, respectively. Since a realizable input distribution has at mostnterms,IDENTIFY + can be invoked up toO(zn(n+m)) 17 Causal Identification from Counterfactual Data: Completeness and Bounding Results times in the main loop. And each inner-loop can be invoked up to n times. The time complexity is O(zn 2 (n + m)). B.4. Example using IDENTIFY + Below, we show an example of using theIDENTIFY + sub-routine to compute a ctf-factor if and only if it is identifiable from another ctf-factor. Each step of the computation is non-trivial, and cannot be skipped by just marginalizing out extra terms. XBY D A W CE (a) XBY D A W CE (b) XBY D A W CE (c) XBY D A W CE (d) Figure 10. Example of using IDENTIFY + to identify a ctf-factor from an input ctf-factor. Each step is a recursive call to IDENTIFY + . Example B.9. Given the graph in Fig. 10(a), consider the sub-routine call of IDENTIFY + where we want Target ctf-factor, Q[C ⋆ ](c) = P (w ′ d ,y b ′ w ) Input ctf-factor, Q[T ⋆ ](t) = P (d,a d ,x,b ′ ax ,c bx ′ ,e c ,w ′ d ,y b ′ w ) computable from the input data. Function call: IDENTIFY + ( G,P (w ′ d ,y b ′ w ),P (d,a d ,x,b ′ ax ,c bx ′ ,e c ,w ′ d ,y b ′ w ) ) goes through the following steps: 1. Line 3 : H ⋆ ≙ P (d,a d ,x,b ′ ax ,w ′ d ,y b ′ w ) - This is the minimal subseth ⋆ ⊇ c ⋆ without any subscripts appearing in the values-vector oft ⋆ \ h ⋆ . Becaused appears in the subscript ofa d , andaappears in the subscript ofb ′ ax etc., we can’t shift any more terms fromh ⋆ to t ⋆ \ h ⋆ . Note: subscripts are value sensitive and b ≠ b ′ , for instance. 2. Line 9 : Q[H ⋆ ](h) = P (d,a d ,x,b ′ ax ,w ′ d ,y b ′ w ) = ∑ c,e P (T ⋆ = t) - Marginalize out C,E, giving us the graph in Fig. 10b. - Probability axioms don’t permit marginalizing out any more terms. 3. Line 10 : the c-components in the subgraph in Fig. 10b are D,X,W,Y and A,B 4. Line 11 : H i ⋆ ≙ P (d,x,w ′ d ,y b ′ w ) - This corresponds to the smallest c-component containing C ⋆ , inducing the subgraph in Fig. 10c. 18 Causal Identification from Counterfactual Data: Completeness and Bounding Results 5. Line 12 : Compute Q[H i ⋆ ](h i ) = P (d,x,w ′ d ,y b ′ w ) from Q[H ⋆ ](h) using the ctf-factorization theorem (Thm. B.5) 6. Line 13 : Function call IDENTIFY + ( G,P (w ′ d ,y b ′ w ),P (d,x,w ′ d ,y b ′ w ) ) 7. Line 3 : H ⋆ ≙ P (d,w ′ d ,y b ′ w ) - This is the minimal subseth ⋆ ⊇ c ⋆ without any subscripts appearing in the values-vector ofh ′ ⋆ . Becausedappears in the subscript of w ′ d , we can’t shift any more terms from h ⋆ to h ′ ⋆ 8. Line 9 : Q[H ⋆ ](h) = P (d,w ′ d ,y b ′ w ) = ∑ x P (T ⋆ = t) - Marginalize out X, giving us the graph in Fig. 10d. - Probability axioms don’t permit marginalizing out any more terms. 9. Line 10 : the c-components in the subgraph in Fig. 10d are D and W,Y 10. Line 11 : H i ⋆ ≙ P (w ′ d ,y b ′ w ) - This corresponds to the smallest c-component containing C ⋆ . 5. Line 12 : Compute Q[H i ⋆ ](h i ) = P (w ′ d ,y b ′ w ) from Q[H ⋆ ](h) using the ctf-factorization theorem (Thm. B.5) 6. Line 13 : Function call IDENTIFY + ( G,P (w ′ d ,y b ′ w ),P (w ′ d ,y b ′ w ) ) immediately returns P (w ′ d ,y b ′ w ) as needed. B.5. Examples using CTFIDU + Below, we show two examples of a counterfactual query given a causal graph, and how theCTFIDU + algorithm identifies this query from counterfactual data. For a breakdown of the steps involved, refer to Sec. B.2. Example B.10 (Front-Door). Consider the front-door graph shown in Fig. 11. We show how theCTFIDU + algorithm correctly retrieves the front-door adjustment formula. Our query isP (y;do(x)) = P (y x )and input is the observational distributionP (x ′ ,z,y). The query chain in Steps i-v decomposes the query in the ctf-factors that we need to identify: P (z x ),P (y z ). The input distribution is then rewritten in ctf-factor format (Step vi) and decomposed into constituent ctf-factors by c- components which can be computed from the input data using Thm. B.5 to getP (x ′ ,y z ) = P (y ∣ z,x ′ ).P (x ′ )and P (z x ) = P (z ∣ x).IDENTIFY + (G,P (y z ),P (x ′ ,y z ))immediately returnsP (y z ) = ∑ x ′ P (x,y z ). Composing these and marginalizing as the final step in Line 22, we get P (y x ) = ∑ z P (z x ,y x ) = ∑ z P (z ∣ x)∑ x ′ P (y ∣ z,x ′ )P (x ′ ). XZY Query: P (y x ) P (z x ,y x ) Step i. (Line 7) P (z x ,y z ) Step iv. (Line 8) P (y z ) Step v. (Line 9) P (z x ) Input data: P (x,z,y) P (x ′ ,z x ′ ,y z ) Step vi. (Line 12) P (x ′ ,y z ) Step vii. (Line 9) P (y z ) Step viii. (Line 16) P (z x ′ ) Figure 11. Example B.10 showing how the CTFIDU + algorithm (Alg. 2) correctly retrieves the front-door adjustment formula. 19 Causal Identification from Counterfactual Data: Completeness and Bounding Results XBY D A W CE Query: P (a,b ′ x ,c bx ′ ,w ′ ,y xw ) P (a,b ′ x ,c bx ′ ,w ′ ,y xw ,d) Step i. (Line 7) P (a d ,b ′ ax ,c bx ′ ,w ′ d ,y b ′ w ,d) Step iv. (Line 8) P (c bx ′ ) Step v. (Line 9) P (a d ,b ′ ax ) P (d) ”Consistent” ctf-factors (Def. B.6) - identifiable (in principle) using prior work (Correa et al., 2021, Alg. 1) P (y b ′ w ,w ′ d ) ”Inconsistent” ctf-factor - non-identifiable using previous methods XBY D A W CE Data-collection regime indexed by actions: A = ctf-rand(W → Y ), ctf-rand(X → C), ctf-rand(B → C) Helper function (Alg. 4) maps this to input expression: P (x,b ′ ,c bx ′ ,e c ,w ′ ,y w ,a,d) Input Data: P (x,b ′ ,c bx ′ ,e c ,w ′ ,y w ,a,d) P (x,b ′ ax ,c bx ′ ,e c ,w ′ d ,y b ′ w ,a d ,d) Step vi. (Line 12) P (x,b ′ ax ,w ′ d ,c bx ′ ,e c ,y b ′ w ,a d ,d) Step vii. (Line 13-14) P (x,b ′ ax ,w ′ d ,y b ′ w ,a d ,d) P (x,w ′ d ,y b ′ w ,d) P (w ′ d ,y b ′ w ,d) P (y b ′ w ,w ′ d ) IDENTIFY + inner loops (App. B.4) P (x,b ′ ax ,a d ,d) P (a d ,b ′ ax ) P (d)P (c bx ′ ) Figure 12. Example B.11 involving a causal diagram (top left) and Layer 3 query (top right). The newCTFIDU + algorithm (Alg. 2) follows the steps shown, reaching the four ctf-factors that are both necessary and sufficient to identify, in order to identify the root query. Next, counterfactual data from an experimental regime (bottom) is used to systematically identify each of these ctf-factors. 20 Causal Identification from Counterfactual Data: Completeness and Bounding Results Example B.11. Consider the graph G and the query Q = P (a,b ′ x ,c bx ′ ,w ′ ,y xw ) shown in Fig. 12 (top left, top right). Calling Alg. 2 asCTFIDU + (G,Q, A)follows the steps shown in the tree sequence in Fig. 12 (upper half). First, it expands the query into an ancestral expression, and then rewrites it in ctf-factor format. Next, it decomposes this expression into the four smaller ctf-factors that are both necessary and sufficient to identify, in order to identify the root query. These are the four blue ”leaf” terms in Fig. 12 (upper half). One of these terms,P (y b ′ w ,w ′ d ), is ”inconsistent” per Def. B.6, and therefore non-identifiable using the previous CTFIDU algorithm (Correa et al., 2021, Alg. 1). At this point, previous methods will return FAIL, because they assume the input data is only from Layer 2. However, it is possible to gather Layer 3 data through counterfactual randomization, as discussed in Sec. 1. Fig. 12 (bottom half) illustrates data collection under the actionsA = ctf-rand(W → Y ), ctf-rand(X → C), ctf-rand(B → C). Mapping this to an input expression, we see that the input distribution is not trivially identical to the query expression we began with. CTFIDU + proceeds to rewrite this input distribution in ctf-factor formatQ[T ⋆ ]. There is no further decomposition at this stage, since all the variables belong to one c-component. This ctf-factor is then used to identify each of the leaf nodes in Fig. 12 (upper half) by calling IDENTIFY + (G,Q[C ⋆ ],Q[T ⋆ ]) for each leaf node C ⋆ in turn. Two of these leaf nodes are immediately computable by a simple marginalization step. The remaining two are identified by following non-trivial inner loops.□ C. Limits of Identification and Realizability In this appendix, we review the definitions of Layers 2.25 and 2.5. We also provide a helpful intuition for framing the results in Sec. 4. We follow the terminology in Raghavan & Bareinboim (2025); Yang & Bareinboim (2025). C.1. Layer 2.5 (L 2.5 ) Given a causal diagramG, Yang & Bareinboim (2025) define Layer 2.5 (L 2.5 ) of the PCH to contain precisely those counterfactual distributions from which it is hypothetically possible to draw samples, if the environment permitted this ctf-rand() procedure for all variables. Below is the formal definition, followed by an intuitive explanation. Definition C.1 (Layer 2.5). As SCMM = ⟨U, V, F,P (u)⟩induces a family of joint distributions overV, indexed by each interventional variable setX. Layer 2.5, orL 2.5 of the PCH is defined to contain all distributions satisfying the following expression. For X, Y ⊆ V: P M ( ⋀ V i ∈Y V i [x i ] = v i , ⋀ V i ∈Y∩X,v i =V i ∩x V i [x i i ] = v i ) =∑ u 1 [ ⋀ V i ∈Y V i [x i ] (u) = v i , ⋀ V i ∈Y∩X,v i =V i ∩x V i [x i i ] (u) = v i ] P (u), where(24) i. the variables in the subscript for each in each term, X i ⊆ X, x i ∈ Domain(X i ), and⋃ i X i = X; and i. for anyV i and anyB ∈ X∩ Pa i , and for allV j ∈ Y: ifV i /∈ X j andV i ∈ An(V j )inM x , thenx i ∩B = x j ∩B.■ For example, in Fig. 13a, we see how one can draw samples directly from the distributionP (y x ,z x ′ )by performing ctf-rand(X → Y) and ctf-rand(X → Z) separately. However, this distribution is not physically realizable if the graph were per Fig. 13b - the mediatorAis a bottleneck and can only receive one value, eitherxorx ′ . The causal structure matters. In Fig. 13, given graph G 1 , P (y x ,z x ′ ) is an L 2.5 distribution. But given G 2 , P (y x ,z x ′ ) lies outside L 2.5 . Theorem C.2. (Raghavan & Bareinboim, 2025, Cor. 3.7) Given causal diagram G, a counterfactual distribution P (Y ⋆ ) belongs to Layer 2.5 (i.e., it is physically realizable, in principle) iff the counterfactual ancestor setAn(Y ⋆ )(Def. B.2) does not contain a pair of potential responses W t ,W s of the same variable W under different regimes t ≠ s.■ A simple way to test to test if someP (Y ⋆ )belongs toL 2.5 is to list the counterfactual ancestors (Def. B.2) ofY ⋆ . Given G 2 in Fig. 13, An(Y x ,Z x ′ ) = Y x ,Z x ′ ,A x ,A x ′ which contains both A x ,A x ′ and thus P (y x ,z x ′ ) lies outside L 2.5 . 21 Causal Identification from Counterfactual Data: Completeness and Bounding Results Figure 13. It is physically possible to draw samples from P (y x ,z x ′ ) given graph G 1 using ctf-rand(), but not given G 2 . C.2. Layer 2.25 (L 2.25 ) L 2.5 contains distributions which are realizable possibly using multiple ctf-rand() procedures for the same variable, such as P (y x ,z x ′ )in Fig. 13a. Layer 2.25 (L 2.25 ) is a subset ofL 2.5 , containing only the distributions which can be realized using at most one ctf-rand() procedure per variable. Definition C.3 (Layer 2.25). As SCMM = ⟨U, V, F,P (u)⟩induces a family of joint distributions overV, indexed by each interventional value setx. Layer 2.25, orL 2.25 of the PCH is defined to contain all distributions satisfying the following expression. For X, Y ⊆ V and x ∈ Domain(X): P M ( ⋀ V i ∈Y V i [x i ] = v i , ⋀ V i ∈Y∩X,v i =V i ∩x V i [x i i ] = v i ) =∑ u 1 [ ⋀ V i ∈Y V i [x i ] (u) = v i , ⋀ V i ∈Y∩X,v i =V i ∩x V i [x i i ] (u) = v i ] P (u), where(25) i. the interventional subscript for each term, x i ⊆ x and⋃ i x i = x; and i. for any v i ∈ x and all V j ∈ Y, if V i ∈ An(V j ) in M x j , then v j ∈ x j .■ A visual intuition for these layers is provided in the examples in Fig. 14. a. L 1 (Fig. 14a) simply represents the observational regime of the system under its natural behavior. b. L 2 (Fig. 14b) represents interventional regimes, where a standard randomization action rand(X) is used to override and fix some variable X in the system. c. L 2.25 (Fig. 14c) represents counterfactual distributions which can be physical realized using counterfactual randomiza- tion actions of the form ctf-rand(X → Ch(X)), where at most one randomization is permitted per variable in a way that affects all outgoing causal paths from the variable. d. L 2.5 (Fig. 14d) generalizes this to all counterfactual distributions which can be physically realized using multiple ctf-rand(X → C) actions per variable, in a way that may affect separate downstream variables differently. (a) L 1 X YZ (b) L 2 X YZ (c) L 2.25 X YZ (d) L 2.5 X YZ Figure 14. Difference in how an intervention on X affects downstream variables in L 1 , L 2 , L 2.25 , and L 2.5 . 22 Causal Identification from Counterfactual Data: Completeness and Bounding Results C.3. Causal lattice framework We describe in this subsection an intuition for Thm. 4.1 and Cor. 4.2 using a causal lattice over the ctf-factors that can be generated from an input distribution (see Sec. 2 for a definition of a ctf-factor). This lattice functions as an inference generator: all the nodes in the lattice are effectively causal quantities that can be identified using input data distributions. We formulate our causal lattice as follows. Given a causal diagram and input data distributions: • The source nodes of the causal lattice are all the available (i.e. input) data distributions. •Each node has outgoing edges to all the distributional quantities that can be computed using the former node. Outgoing edges include – Mapping from a source node to an equivalent ctf-factor formulation (Thm. B.4): 1-to-1 connection – Decomposing a larger ctf-factor into smaller ctf-factors (Eq. 19): 1-to-many connections – Composing smaller ctf-factors into a larger ctf-factor (Eq. 18): many-to-1 connections –Mapping from a ctf-factor to an equivalent non-ctf-factor distribution, if the latter is ancestral (Thm. B.4): 1-to-1 connection – Marginalization of a distribution to get a smaller distribution: 1-to-1 connection •There could be multiple valid pathways from the set of input data distributions to a particular quantity of interest, via different sets of intermediate nodes. Example C.4. In Fig. 12, conjoining the respective distribution trees in the upper and lower half of the figure would constitute a valid sub-lattice of the causal lattice induced by the input data distribution P (x,b ′ ,c bx ′ ,w ′ ,y w ,a,d).□ Next, we define a way to rank the level of ”inconsistency” that characterizes any given ctf-factor. This could be seen as a generalization of Def. B.6 from Correa et al. (2021). Definition C.5 (Ctf-factor inconsistency level). A ctf-factor is said to have an inconsistency level, as defined by the table in Fig. 15. If the ctf-factor satisfies several rows, the highest number is chosen (see Sec. 2 for a definition of a ctf-factor).■ Figure 15. Levels of inconsistency of a ctf-factor, with examples for the causal diagram shown on the right. We illustrate this in the example provided in Fig. 16, which shows sections of the causal lattice generated from an example causal graph and available input distributions. Each node is a the distributions which can be identified from the input data, culminating in all possible target quantities which are identifiable. Nodes which are ctf-factors are colored blue, and assigned an inconsistency level per Fig. 15. The key insights of this causal lattice presentation are as follows: • Input distribution nodes belonging to L 1 , L 2 , L 2.25 , L 2.5 (respectively) have outgoing edges to ctf-factors of ≤ incon- sistency level 1, 2, 3, 4 (respectively). E.g. the observational distributionP (w,x,a,z,y)can only point to ctf-factors of inconsistency level 1, shown on the left in Fig. 16. 23 Causal Identification from Counterfactual Data: Completeness and Bounding Results • Different types of arrows from some ctf-factor(s) to other(s) can change the inconsistency levels differently: –A 1-to-many arrow can decrease inconsistency level from the preceding node. E.g., in the section marked (i) in Fig. 16, inconsistency level goes from 3 to 1. – A 1-to-1 arrow can reduce inconsistency level, or can increase it from 1 to 2. E.g., in the section marked (i) in Fig. 16, inconsistency level goes from 1 to 2. –A many-to-1 arrow can increase inconsistency level over each of the preceding nodes. E.g., in the section marked (i) in Fig. 16, inconsistency level goes from 3,1,1 to 4. •Target output nodes belonging toL 1 , L 2 , L 2.25 , L 2.5 (respectively) have incoming edges from ctf-factors of≤inconsis- tency level 1, 2, 3, 4 (respectively). E.g. the interventional distributionP (w x ,a x )requires an incoming edge from ctf-factor of inconsistency level 2, shown on the left in Fig. 16. • L 3 output nodes have incoming edges from otherL 3 nodes or ctf-factors of inconsistency level 5. And each ctf-factors of inconsistency level 5 has incoming edges from other L 3 nodes or ctf-factors of inconsistency level 5. This increase/decrease in inconsistency along lattice pathways is what allows higher-order counterfactual quantities from L i to be identified from lower-layer L j data, j < i. However, the last point is a fundamental limitation. If we want anL 3 output node, it needs an incoming edge from a node with inconsistency level 5. The reasoning is provided in the proof of Thm. 4.1. By induction, it follows that no quantity inL 3 \ L 2.5 is identifiable because there is no lattice path to it starting from a physically realizable input data distribution (as illustration on the bottom right in Fig. 16). Figure 16. Example illustrating sections of the causal lattice generated from a graphG, and input data distributions as source nodes. Each subsequent node is a distribution which can be identified from all distributions pointing into it. Blue nodes are ctf-factors, each assigned an inconsistency level per Fig. 15. L 3 output nodes don’t have a valid lattice path starting from a realizable input data distribution. D. Partial Identification: Example Details The simulation code is provided in the supplementary material, for reproducibility. We follow a Markov Chain Monte Carlo (MCMC) methodology developed in Zhang et al. (2022) to derive empirical bounds for quantities of interest: 24 Causal Identification from Counterfactual Data: Completeness and Bounding Results We generate synthetic input datasets from a random underlying (hidden) SCM. With this data, we derive a posterior distribution over all possible SCMs compatible with the causal graph and input data. Sampling from this posterior, we get a distribution over the values for our target query, giving us a range of feasible values. We repeat this with 5 random SCMs to ensure consistent results. Hyperparameters: N = 10 4 samples per input distribution; credible interval 95%. D.1. Example 2 The causal graph for this example is shown in Fig. 17a. Causal assumptions:Yrepresents an automated AI decision to issue a speeding ticket to a driver based on video footage.X represents the color of the driver’s car.Zis an indicator of whether the driver was over the speed limit or not.Xmight affectZif pedestrians and other drivers react to, say, a red car and affect its speeding.Xmight affectYdirectly due to a high correlation in training data between the color preference of different socioeconomic groups and their speeding tendency. Speeding and outcome might be affected by an unobserved confounder - unlabeled road obstacles (which present as video artifacts). Car color and outcome might be affected by an unobserved confounder - unlabeled driver attributes (which can be picked up in video footage). Figure 17. Causal diagram and different data-collection regimes for Example 2 (Traffic Camera v2). We are interested in obtaining empirical bounds for two queries: (i)NTE-likeP (Y X=1 ∣X = 0,Y = 0): comparison between using observational + interventional input data (orange plots) vs. using counterfactual input data from the regime shown in Fig. 17c (blue plots) (i)NDE-likeP (Y X=1,Z X=0 = 1): comparison between using observational + interventional input data (orange plots) vs. using counterfactual input data from the regime shown in Fig. 17d (blue plots) Results: in Fig. 18 we show results for each query across 5 randomly generated underlying true causal models. Across all examples, using counterfactual data (blue plots) narrows the credible interval for the query vs using observational and/or interventional data alone (orange plots). The true target value is indicated by a red line. D.2. Example 3 The causal graph for this example is shown in Fig. 19a. Causal assumptions:Yrepresents a favourable outcome in a drug de-addiction program within 6 months.Xindicates a decision made by an experienced program officer about whether to send the program participant for intensive counseling sessions with a specialized therapist. Decisions can be made under three data-collection modes, with data values as follows: a. Observational (Fig. 19a): the program officer follows their intuitive judgment based on years of experience, which may be affected by unobserved factors and biases.L 1 data reveals thatP (X = 1) = 0.85,P (Y = 1∣X = 0) = 0.35, and P (Y = 1∣X = 1) = 0.15. 25 Causal Identification from Counterfactual Data: Completeness and Bounding Results Bounds for NTE: P (y x ∣ x ′ ,y ′ ) NDE: P (y xZ x ′ ) truth L 2 range L 2.5 range Figure 18. Example 2 results (over 5 random underlying SCMs) showing partial identification bounds for NTE and NDE quantities. Bounds are tighter using counterfactual data (blue) than interventional data (orange). Since NDE is identifiable from counterfactual data, blue bounds are not visible as they collapse to the true value (red). Figure 19. Causal diagram and different data-collection regimes for Example 3 (Unit Selection). b.Interventional (Fig. 19b): the program officer overrides their natural inclination and assigns a decision to a participant, such as using a randomizing device as in a clinical trial.L 2 data revealsP (Y = 1;do(X = 0)) = 0.605, and P (Y = 1;do(X = 1)) = 0.225. c. Counterfactual (Fig. 19c): the program officer first registers what they normally would have chosen for this participant (X = x ′ )before subjecting the unit to a fixed treatmentdo(X = x)conditioned onx ′ .L 2.5 data revealsP (Y X=1 = 1∣X = 0) = 0.65, and P (Y X=0 = 1∣X = 1) = 0.65. Following the Interventional Strategy (1) , recommended by Li & Pearl (2022): Using observational and interventional data, run the MCMC methodology described earlier to estimate the bounds for the proportion of each canonical type,P (Y X=0 ,Y X=1 ). Combine these bounds with the benefit function shown in Fig. 8 to derive the estimated bound of the avg. treatment benefit for the whole population. Simulation using synthetic data (N = 10 4 samples) shows a 95% credible interval of the avg. population benefit∆(1) ∈ [−1.3, 1.6]. It is inconclusive whether to administer the treatmentX = 1to the whole population, because it could result in net negative or positive benefit on average. Following a Counterfactual Strategy (2): 26 Causal Identification from Counterfactual Data: Completeness and Bounding Results Using counterfactual data, run the MCMC methodology described earlier to estimate the bounds forP (Y X=0 ,Y X=1 ∣X = x ′ ) - the proportion of each canonical type in the sub-population for which the program officer feels naturally inclined to assign treatmentX = x ′ . Combine these bounds with the benefit function shown in Fig. 8 to derive the conditional subpopulation- level treatment benefit bounds. Simulation using synthetic data (N = 10 4 samples) shows a 95% credible interval of the conditional benefits∆(1∣X = 0) ∈ [5.7, 11.6] and ∆(1∣X = 1) ∈ [−2.5,−0.1]. The clear strategy for the program officer is to go against their intuition X = x ′ : • Assign treatmentdo(X = 1)to participants to whom they would have intuitively been inclined to reject for counseling (natural X = 0), since ∆(1∣X = 0) > 0; •Withhold treatmentdo(X = 0)for participants to whom they would have intuitively been inclined to recommend for counseling (natural X = 1), since ∆(1∣X = 1) < 0; This provably dominates Strategy (1)because ∆(1) = P (X = 0)∆(1∣X = 0) + P (X = 1)∆(1∣X = 1)Strategy 1 benefit(26) < P (X = 0)∆(1∣X = 0)Strategy 2 benefit(27) If the program officer chooses 0 for the whole population, they incur 0 benefit. If they choose 1 for the whole population, this would be strictly suboptimal than choosing 1 only for the subpopulation with natural X = 0 (Eqn. 27). E. Proofs of Results E.1. Proofs for Sec. 3 Our proof strategy for the completeness of CTFIDU+ will be to go step-by-step and show that each step is both necessary and sufficient to identify the queryP (Y ⋆ = y)from a set of input distributions indexed byA. Refer to Fig. 9 for a helpful summary of the steps. Lemma E.1 (Step i). The exclusion operation is both necessary and sufficient for identification. Proof. By Lem. B.3, Y x = ∣Y x ∣,∀Y x ∈ Y ⋆ . The identification result is the same for ∣Y ⋆ ∣ as it is the original.■ As a precursor to handling Step i., we prove an intermediary result next. Lemma E.2. SupposeP (W ⋆ = w)is not identifiable from a set of input distributions and causal diagramG, and there exist termsA t 1 ,B t 2 ∈ W ⋆ s.t.A t 1 is a counterfactual parent ofB t 2 . Then∑ a P (W ⋆ = w)is not identifiable from the same input, either. (See Def. B.2 for a definition of counterfactual ancestors.) Proof.This was proved in Correa et al. (2021, Lem. 4). The steps remain identical when the input scope includes realizable Layer 3 distributions. In particular, equations (43), (44) in their proof and the case-analysis that follows are the only location where they assume input is restricted to Layer 2. For a realizable input regimeAunder full visibility,A 1 [t ] /∈ Z ⋆ only if action-setAcontains the action rand(A) corresponding todo(a 1 ). In such a regimeA 1 [t ] would not be a counterfactual parent of any potential response, and so would not appear in D ⋆ \ Z ⋆ either, in their equations (43-44).■ Lemma E.3 (Step i). In order to identifyP (Y ⋆ = y)fromGandAit is necessary and sufficient to identifyP (W ⋆ = w) from G and A, where W ⋆ = An(Y ⋆ ), the set of counterfactual ancestors (Def. B.2) of Y ⋆ . Proof. If P (W ⋆ = w) is identifiable from G and A, then P (Y ⋆ = y) = ∑ w P (W ⋆ = w). Reverse direction: every counterfactual ancestor ofY ⋆ is contained inW ⋆ . Thus, we apply Lem. E.2 in topological order to argue by induction that if P (W ⋆ = w) is not identifiable then∑ w P (W ⋆ = w) is not identifiable either.■ 27 Causal Identification from Counterfactual Data: Completeness and Bounding Results Lemma E.4 (Step iv). In order to identifyP (W ⋆ = w)fromGandA, for someW ⋆ = An(W ⋆ ), it is necessary and sufficient to identifyP (W ′ ⋆ = w)fromGandA, whereW ′ ⋆ = wis the result of applying the ancestral set transformation, or AST, to W ⋆ = w. Further, P (W ′ ⋆ = w) satisfies the definition of a ctf-factor. Proof.By Thm. B.4,P (W ⋆ = w) = P (W ′ ⋆ = w). By construction,W ′ ⋆ = wis of the form⋀ W t ∈W ⋆ W pa W = w, satisfying the definition of a ctf-factor (see Preliminaries in Sec. 2).■ Lemma E.5 (Step v). In order to identify a ctf-factorP (W ⋆ = w)fromGandA, it is necessary and sufficient to identify each ctf-factorP (C j ⋆ = c j ),j = 1...k,fromGandA, whereC j ⋆ is a partition ofW ⋆ s.t. eachV(C j ⋆ )forms a c-component in G[V(W ⋆ )]. Proof.By Thm. B.5, if we can identify eachP (C j ⋆ = c j )we can computeP (W ⋆ = w)as the product of these terms. By the same theorem, if we can identifyP (W ⋆ = w), we can compute eachP (C j ⋆ = c j )using a topological ordering over G[V(W ⋆ )].■ Lemma E.6 (Step vi.). Lines 11-12 return an expression P (T ⋆ ) which is a valid ctf-factor. Proof. Claim: under full visibility, given an un-nestedP (T ′ ⋆ )corresponding to a realizable distributionA ∈ A,T ′ ⋆ is ancestral. I.e.,An(T ′ ⋆ ) = T ′ ⋆ . SinceAis a physically realizable distribution, by Thm. C.2,An(T ′ ⋆ )cannot contain two potential responses of the same observable variable. The ancestor set of each potential responseV x ∈ T ′ ⋆ that is measured in this regime must minimally contain itself. The only opportunity for some variable to not be measured is when it is being subjected to a rand() action (i.e. ado()intervention). But in this case, it won’t be a ctf-ancestor to any other potential response. It follows that An(T ′ ⋆ ) = T ′ ⋆ . Since any valid way of tagging a realizable input distribution satisfies this lemma, the output of REGIME-REGEX (Alg. 4) will be someP (T ′ ⋆ )whereT ′ ⋆ is ancestral. Applying the AST (Thm. B.4) gives us a ctf-factorP (T ⋆ )as needed. Note: REGIME-REGEX is merely a helper function for indexing a distribution. Any equivalent way of tagging the same counterfactual distribution works.■ Lemma 3.3 (Ctf-hedge non-identifiability). LetT ⋆ = tbe a ctf-hedge rooted inC ⋆ = c, with subgraphG.Q[C ⋆ ](c) is not identifiable from Q[T ⋆ ](t) given G. Proof.We develop a bit-encoding scheme to construct a pair of SCMsM 1 andM 2 that witnesses the non-identifiability. I.e.,P 1 (T ⋆ = t) = P 2 (T ⋆ = t)butP 1 (C ⋆ = c) ≠ P 2 (C ⋆ = c). As a preliminary step, we remove from the subscripts inT ⋆ any variables not present in subgraphG, and we also delete any directed edges withinV(C ⋆ ). We can reflect this in the SCM definition by having each variable ignore the value of the removed subscript inM 1 , M 2 . Next, we see that by virtue of the ”value chaining” in a ctf-hedge, we can apply the consistency property asPa i = pa i ⟹ V i [pa i ] = V i , to get P (T ⋆ = t) = P (T = t), the observational distribution. Thus, it suffices to construct M 1 , M 2 to match in P (t). Adapting the strategy in Shpitser & Pearl (2006, Thm. 4), let all variables take values in0, 1. W.l.o.g, pick an assignment for valuesc ⊂ ts.t.∑ c = 0 (mod 2). Assign one latent confounder per bidirected edge, independently sampled ∼ Ber(0.5). In bothM 1 , M 2 , set each observable variable to be the (mod 2) sum of its observable and latent parents, i.e. the bit parity of its parents. However, inM 2 , set the variables inC = V(C ⋆ )to ignore values of parents inT \ Cand latents shared withT \ C. By construction, the bit parity ofCis always even in both models: inM 1 the sum counts each latent bit twice as it gets passed down the chain, and inM 2 the sum counts each latent bit pointing withinCtwice. It can also be verified that any assignment having∑ c = 0 (mod 2)is equally likely in both models by virtue of the random sampling and edge count in a min. spanning tree. Thus,P 1 (t) = P 2 (t)as needed. It is straightforward to introduce positivity by adding some noise to each variable, and we leave that a post-processing step. However, if wedo(pa C \ c), this breaks the constant-0 parity inM 1 because there is always at least one bidirected edge fromT \ CtoC, which is ignored inM 2 .P 1 (0 = ∑ c (mod 2) ∣ do(pa C \ c)) = 0.5, whileP 2 (0 = ∑ c (mod 2) ∣ do(pa C \ c)) = 1 . Finally, note that if we setpa C \ caccording to the subscripts inC ⋆ and use the consistency property, P (C ∣ do(pa C \ c)) = P (C ⋆ = c), giving us the inequality that proves non-identification.■ 28 Causal Identification from Counterfactual Data: Completeness and Bounding Results Lemma 3.4 (IDENTIFY + soundness and completeness). LetQ[T ⋆ ](t)be a ctf-factor in which each observable variable appears at most once, andG[V(T ⋆ )]is a c-component. LetQ[C ⋆ ](c)be a ctf-factor s.t.C ⋆ ⊆ T ⋆ , c ⊆ t.Q[C ⋆ ](c)is identifiable from Q[T ⋆ ](t) and G iff IDENTIFY + returns an expression for it. Proof. We begin by noting that since each recursive call ofIDENTIFY + either reduces the size ofT ⋆ by at least one, or exits ifT ⋆ = C ⋆ , or FAILS, the outer call ofIDENTIFY + must terminate with either an expression returned or FAIL. Steps 5 and 9 are licensed by probability axioms. Step 12 is proved in Thm. B.5. This establishes the soundness of any expression returned by IDENTIFY + . IfIDENTIFY + FAILS, this is precisely because it has detected a ctf-hedge structure (Def. 3.2): [i]T ⋆ has at most one potential response per observable variable; [i]T ⋆ corresponds to a c-component which we can convert to a bidirected minimum spanning tree by having variable functions ignore some edges; [i]H ⋆ must minimally includeC ⋆ and is set to the wholeT ⋆ only when a parent’s value appears in some child’s subscript in a ”chained” way for the whole c-component outsideC ⋆ ; [iv] one-child policy can be enforced by ignoring extra directed edges. By Lem. 3.3, this scenario is only possible when P (C ⋆ = c) is indeed non-identifiable, giving us the completeness of IDENTIFY + .■ One might suspect that if identification using separate ctf-factors individually does not work, perhaps a combination of ctf-factors that contain a target ctf-factor might collectively make it identifiable. Let us define an aggregated structure which relieves this suspicion. Definition E.7 (Counterfactual (Ctf-) Thicket). LetT 1 ⋆ = t 1 ,..., T a ⋆ = t a be ctf-hedges all rooted inC ⋆ = c(Def. 3.2), with subgraphsG 1 ,..., G a , respectively. Then the setT i ⋆ = t i a i=1 forms a counterfactual, or ctf-thicket rooted in C ⋆ = c. Figure 20. Subgraphs of a ctf-thicket. Consider the structure in Fig. 20.s,c,b sc ,d b ,f d ,e gh (tagged in blue) and b ′ ,h b ′ ,g,e gh ,f d (tagged in red) are each individually ctf-hedges rooted inE gh = e,F d = f(tagged in purple), with their separate subgraphs. Bbelongs in both subgraphs. Taken together, they constitute a ctf-thicket rooted in E gh = e,F d = f. Lemma E.8 (Ctf-thicket non-identifiability). LetT i ⋆ = t i a i=1 be a ctf- thicket rooted inC ⋆ = c(Def. E.7), with subgraphsG i .P (C ⋆ = c) is not identifiable from P (T i ⋆ = t i ) a i=1 given⋃ i G i . Proof.Extend the bit-encoding scheme used in the proof of Lem. 3.3 by having each variable and latent in the combined subgraph be ana-bit variable, where thei-th bits are used to encode the constraints for ctf-hedge i. If a variable does not belong toG i , set thei-th bit uniformly at random. Since each dimension operates independently, it can be verified thatP (t i ) matches∀iinM 1 andM 2 , but the do-distributionP (C ∣ do(pa C \ c))differs. Settingpa C \ cas per the subscripts in C ⋆ , we see that P (C ⋆ = c) differs in M 1 and M 2 , completing the proof.■ Finally, we show why it is sufficient to deal with c-components and not the whole distribution. Lemma E.9 (Step vii). Given a set of realizable input distributionsA ∈ A, letG A be the graph corresponding to input distributionA. Let ctf-factorP A (T ⋆ = t)be the result of performing the AST transformation (Thm. B.4) on the input expression corresponding toA. LetT 1 ⋆ ,..., T m ⋆ be a partition ofT ⋆ s.t. eachV(T i ⋆ )is a c-component inG A , and P A (T 1 ⋆ = t 1 ),...,P A (T m ⋆ = t m )be their corresponding ctf-factors. LetP (C ⋆ = c)be a target ctf-factor s.t.V(C ⋆ )is a c-component inG[V(C ⋆ )]. The targetP (C ⋆ = c)is not identifiable from the overall set of input distributionsAif it is not identifiable from some ctf-factorP A (T i ⋆ = t i )whereC ⋆ ⊆ T i ⋆ andA ∈ A. In other words, ifP (C ⋆ = c)fails on identification from every single P A (T i ⋆ = t i ) where T i ⋆ contains C ⋆ , then P (C ⋆ = c) is non-identifiable from the data. Proof.Recall from Thm. C.2 that each variable in a realizable input distribution is measured at most once. Thus, for each input regimeA, the partition ofT ⋆ by c-components is s.t. there is at most oneT i ⋆ ⊇ C ⋆ . Assume the target ctf-factor P (c ⋆ ) fails on identification with every input ctf-factor P A (t i ⋆ ) where the partition subset T i ⋆ ⊇ C ⋆ in regime A. 29 Causal Identification from Counterfactual Data: Completeness and Bounding Results W.l.o.g we index the firsta = 1, 2...,a ′ regimes to be ones where the partition per regimeacontains exactly one subset T i ⋆ ⊇ C ⋆ . Define two SCMsM 1 , M 2 as follows. Let each observable variable be an(a ′ + 1)-bit encoding, where each bit a = 1,...,a ′ + 1 represents some input data regime constraint. Encoding for first a ′ bits Each bita ∈ [a ′ ]encodes constraints for the firsta ′ regimes. By the proof steps of Lem. 3.4, ifP (c ⋆ )cannot be individually identified from eachP a (t i ⋆ ), then it has detected a ctf-hedget i ⋆ rooted inc ⋆ , for eacha ∈ [a ′ ]. Collectively, these satisfy the definition of a ctf-thicket (Def. E.7). Define the SCMs following the bit-encoding scheme used in the proof of Lems. E.8, 3.3: independently draw each latent confounder in the ctf-thicket∼ Ber(0.5). Fora ∈ [a ′ ], let thea-th bit of each observable variable encodes the hedge constraints for input distributiona(refer to proof of Lem. 3.3). If a variable does not belong to the ctf-hedge for input distribution a, set the a-th bit uniformly at random. By construction, the SCMsM 1 , M 2 are s.t.P 1,a (t ⋆ ) = P 2,a (t ⋆ )for every input distributiona ∈ [a ′ ]butP 1 (c ⋆ ) ≠ P 2 (c ⋆ ), when we only consider the first a ′ bits of each variable. Encoding for last bit For the last bit, we define the encoding at the level of potential responses. Consider the ancestral multi-world network, or AMWN, comprising of the counterfactual ancestors (Def. B.2) of the setC ⋆ ∪⋃T ⋆ ∣A∣ a=a ′ +1 . The nodes of this graph are the potential responses in these sets, plus bidirected edges shared between the potential responses (representing latent confounders), and directed edges for any ancestral relationships between them. Since each potential response is of the form V pa V , there is no parent-child relationship between these potential responses. Consider the setC ⋆ in the AMWN. There is a path between any two nodes in this set sinceV(C ⋆ )is a c-component. Define a minimum spanning tree over these nodes by ignoring extra bidirected edges. As mentioned earlier, we independently draw each of these latent confounders∼ Ber(0.5). In SCMM 1 andM 2 , set the last bit of eachV pa V ∈ C ⋆ to be the(mod 2) sum of its two latent parents, i.e.,V pa V = U 1 ⊕ U 2 (since this is a min. spanning tree, there will be exactly two latent parents per potential response). However inM 2 choose an arbitraryY pa Y ∈ C ⋆ and flip its last bit asY pa Y = U 1 ⊕U 2 ⊕ 1. For every other potential response, set its last bit uniformly at random. Due to the edge count in a min. spanning tree, each latent variable figures contributes exactly twice to the bit parity ofC ⋆ , so we haveP 1 (0 = ∑ c ⋆ ) = 1andP 2 (0 = ∑ c ⋆ ) = 0, considering only the last bit. Now consider each input distributionA where each partition subsetT i ⋆ /⊇ C ⋆ . Since latent terms don’t neatly cancel out, it can be verified thatP A (0 = ∑ t i ⋆ ) = 0.5, when considering only the last bit, under bothM 1 , M 2 . By symmetry,P A (t i ⋆ )is a uniform distribution for the last bit. I.e., P A (t ⋆ ) = ∏ i P A (t i ⋆ ) is a uniform distribution for the last bit. Overall Since the dimensions operate independently under this scheme, it can be verified that input distributions match across both SCMs: P A,1 (t ⋆ ) = P A,2 (t ⋆ ),∀A ∈ A, but P 1 (c ⋆ ) ≠ P 2 (c ⋆ ). Thus, P (c ⋆ ) is non-identifiable from the data.■ We now have the ingredients for our overall result. Theorem 2.1(CTFIDU + soundness and completeness). Given an un-nested counterfactual expressionY ⋆ ,P (Y ⋆ = y)is identifiable from a causal diagram G and a set of input distributions A, iff CTFIDU + returns an expression for it. Proof. Given queryP (Y ⋆ = y)andG, Lemmas E.1, E.3, E.4, E.5 show that it is necessary and sufficient to identify each of the ctf-factors P (C j ⋆ = c j ) derived from Lines 3-9, in order to identify the query. If allP (C j ⋆ = c j )have been identified byIDENTIFY + using some input computable from the available data, Lem. 3.4 shows the returned expressions are correct, and can be composed in Line 22 to identify the original input query, by Thm. B.8. This proves the soundness of CTFIDU + . If anyP (C j ⋆ = c j )has not been identified, it is either (a) because there was no ctf-factorP (T i ⋆ = t i )computable from input data s.t.V(T i ⋆ )is a c-component andC j ⋆ ⊆ T i ⋆ ; or (b)IDENTIFY + returned FAIL on all attempts to identify P (C j ⋆ = c j )from qualifying input ctf-factors. In either case, by Lem. E.9, this meansP (C j ⋆ = c j )is not identifiable from the cross-regime collection of all the input data distributions. 30 Causal Identification from Counterfactual Data: Completeness and Bounding Results Since identifyingP (C j ⋆ = c j )is strictly necessary, this meansCTFIDU + returns FAIL in Line 20 only when the original query is indeed non-identifiable, proving the completeness of CTFIDU + .■ E.2. Proofs for Sec. 4 Lemma E.10. Given a set A of input data distributions, where each A ∈ A belongs to L 2.5 , line 13-14 of CTFIDU+ (Alg. 2) will never produce a ctf-factorQ[T i ⋆ ](t i )s.t. the counterfactual setT i ⋆ contains potential responsesW t ,W s of the same variable W under conflicting regimes t ≠ s. Proof.Each input distributionP (T ⋆ = t), corresponding to someA ∈ A, belongs toL 2.5 . We know from the proof of Lem. E.6 that T ⋆ is ancestral, i.e. An(T ⋆ ) = T ⋆ . By Thm. C.2, this meansT ⋆ cannot contain potential responsesW t ,W s of the same variableWunder conflicting regimes t ≠ s. Thus, when partitioning the set in line 13 of Alg. 2, there will be no subset T i ⋆ containing any such W t ,W s .■ Theorem 3.1 (Limit of identification). Given a queryQbelonging toL i of the PCH and no lower layer, for everyj < i there exists a graph G s.t. Q is identifiable from G and input data from L j , except for i = 3. Proof.Thm. C.2 shows that a distributionP (Y ⋆ )is physically realizable (i.e. we can physically draw iid samples from it) in principle using ctf-rand() or some other actions, iff the set of counterfactual ancestorsAn(Y ⋆ )does not contain some pair of potential outcomesW t ,W s of the same variableWunder different regimest ≠ s. For instance, in Fig. 13b,An(Y x ,Z x ′ ) is the set Y x ,Z x ′ ,A x ,A x ′ which contains both A x ,A x ′ thus rendering P (Y x ,Z x ′ ) not realizable per this graph. Since Yang & Bareinboim (2025) defineL 2.5 to be precisely those distributions which can be realized via ctf-rand() or other actions, this means a distribution falls within L 2.5 iff it passes this counterfactual ancestor check without conflict. For P (Y ⋆ = y) belonging to L 3 \ L 2.5 : From Thm. 3.5,P (Y ⋆ = y)is identifiable fromL 2.5 data and graphGiff CTFIDU+ does not FAIL on these inputs. Line 8 of Alg. 2 gathers the counterfactual ancestor setW ⋆ = An(Y ⋆ )which, by Thm. C.2 must contain someW t ,W s , t ≠ s. Line 9 partitionsW ⋆ (after subscript re-mapping) into clustersC j ⋆ s.t. potential responses belong to the same cluster if their observable variables belong to the same c-component inG.W t ,W s will always be clustered in the sameC j ⋆ since they are both of the same variable W . The ctf-factor for this clusterQ[C j ⋆ ](c j ) will then be passed through the IDENTIFY+ subroutine in hopes of identifying it from some input ctf-factorQ[T i ⋆ ](t i )s.t.C j ⋆ ⊆ T i ⋆ . By Lem. E.10 no input distribution fromL 2.5 can produce such aT i ⋆ containingW t ,W s . Thus,Q[C j ⋆ ](c j ) is never passed through IDENTIFY+, and remains unindentified. CTFIDU+ fails on P (Y ⋆ = y) regardless of the graph G. For P (Y ⋆ = y) belonging to L 2.5 , L 2.25 or L 2 : We assume that the queryP (Y ⋆ = y)satisfies the membership definition forL i . E.g., if we are told it belongs toL 2 , we assume all the subscripts in Y ⋆ are the same x etc. The layer definitions are gives in Secs. 2, C.1, C.2. Define the input distribution to be the observationalP (V)- if a query is identifiable fromL 1 data, it is automatically identifiable from higher layers because L 1 ⊆ L >1 . Define the input causal graph G ′ as follows, • For an L 2.5 or L 2.25 query - P (Y ⋆ = y)must be paired alongside a graphGto begin with. As clarified in earlier sections, membership in L 2.5 depends on the graph and not on the form of the expression alone (e.g., see Fig. 13) – Construct a new graphG ′ fromGby removing any bidirected edges from it.P (Y ⋆ = y)remains anL 2.5 orL 2.25 query according to G ′ , since the layer definition is agnostic to bidirected edges. • For an L 2 query - Start with an emptyG ′ . Add a vertex for every variable appearing inY ⋆ including subscripts. For everyY x ∈ Y ⋆ , add a directed edge from each X ∈ X to Y . 31 Causal Identification from Counterfactual Data: Completeness and Bounding Results Line 8 of Alg. 2 gathers the counterfactual ancestor setW ⋆ = An(Y ⋆ )which, by Thm. C.2 cannot contain a pair W t ,W s , t ≠ s. Thus, when line 9 partitionsW ⋆ , each clusterC j ⋆ contains at most one potential response for each SCM variableV ∈ V. Since there are no bidirected edges between any variable inG, each clusterC j ⋆ contains exactly one potential responseV pa v , and we effectively need to just identify a set of ctf-factors of the formQ[C j ⋆ ](c j ) = P (V pa v = v) = P (v;do(pa v )). Applying Rule 2 of do-calculus,P (v;do(Pa v = pa v )) = P (v ∣ Pa v = pa v ), since there are no unobserved confounders. By line 22 of the CTFIDU+ Alg. 2, P (Y ⋆ ) is identified from L 1 data and graph G ′ . Note: the input graph does not always need to be free of bidirected edges for identification to succeed. What kinds of confounding still permit identification are determined by what ctf-factors can be separated and recombined from input data - an intuition we try to convey using a causal lattice framework in Sec. C.3.■ Corollary 3.2 (Id - realizability duality (formal)). Consider a causal diagramGand a queryQ = P (Y ⋆ = y)belonging to L i . The following implication holds for identifiability ∀i: Q is ID from L j data, j < i ⟹ Q belongs to L 2.5 (28) Q is ID from L j data, j < i /⟹ Q belongs to L j (29) Furthermore, the following implication holds for realizability ∀i: Q is realizable ⟹ Q is ID from the available data(30) Q is realizable /⟹ Q is ID from L j data, j < i(31) Proof. Recall that the PCH is a containment hierarchy. Higher layers automatically contain lower ones. Eq. 28 : This follows from Theorem 4.1. If a query is identifiable, it cannot belong toL 3 \ L 2.5 . By definition, this meansQ can be physically realized, in principle, were all ctf-rand() actions to be permitted in the system (as we stress, ctf-rand() may not always be feasible or desirable in a given situation). Eq. 29: Importantly, identifiability says nothing about what physical actions are minimally necessary to realize the distribution through sampling. E.g., for the graph in Fig. 14, the query P (y x ,z x ′ ) is identifiable from L 2 data as P (y x ,z x ′ ) = P (y;do(x)).P (z;do(x ′ ))(32) However, it is not possible to physically sample fromP (y x ,z x ′ )using just the standardL 2 action of rand(X). This query belongs toL 2.5 , requiring the joint actionsctf-rand(X → Y ), ctf-rand(X → Z)in order to directly sample from it. Similar counter-examples can be constructed for other layers in a straightforward way. Eq. 30: This is a trivial implication. IfQcan be realized by physical actions, this distribution already belongs to the available data. Feeding this input distribution into the CTFIDU+ algorithm trivially returns an ID expression. Eq. 31: Importantly, realizability says nothing about the ability to reduce the query to lower layer data. E.g., given the causal graph in Fig. 21(a), we can directly sample from the distributionP (y x ,z x ′ )using the physical actionsctf-rand(X → Y ), ctf-rand(X → Z) . However, due to the confounding betweenYandZ,P (y x ,z x ′ ) is non-identifiable fromL 2 , or even L 2.25 data. It is straightforward to construct similar counter-examples for other layers, too.■ (a) X YZ (b) X YZ Figure 21. (a) Causal diagram; (b) P (y x ,z x ′ ) is realizable by joint ctf-rand() actions, but is non-ID from L 2.25 or L 2 data. 32 Causal Identification from Counterfactual Data: Completeness and Bounding Results E.3. Proofs for Sec. 5 Proposition 4.1. Given causal diagramGand queryQ = P (y ⋆ ), let[l,r] A ⊆ [0, 1]be the tight partial identification bounds for Q given input data regimes A. Then, for any A ′ ⊃ A, the bounds [l,r] A ′ ⊆ [l,r] A . Proof. Given a causal diagramG, we can parametrize the space of SCMs compatible withGusing the ”canonical model” framework. A canonical representation casts each (unknown) exogenous variable as an indicator for mapping functions for each variable from their parent variables. Following (Balke & Pearl, 1994; Zhang et al., 2022), the input distributions impose constraints which can be written as a linear/polynomial program in terms of these ”canonical” mapping parameters. Each SCM fully determines the value of the queryQ. LetΩbe the polytope of SCMs that satisfies the constraints imposed byA. For anyA ′ ⊃ A, the feasible set must be a subset of Ω, so the range of possible Q values can’t be larger.■ Lemma 4.2 (NTE -L 1 bounds). Given a bow graph causal structure (Fig. 6.a) and observational dataP (X,Y ), the identification query P (y x ∣ x ′ ,y ′ ),x ≠ x ′ is tightly bounded in the range [0, 1]. Proof.LetX,Ytake values in setsX, Yrespectively. Consider the joint probability table with columns for all potential responses in this model:(X, Y x ′ x ′ ∈X ). Fix some valuesx ′ ∈ X,y ′ ∈ Y. The probability mass for all rows havingX = x ′ in the table is fixed by the input observational data∑ y ′ P (x ′ ,y ′ ). Conditional on(X = x ′ ), the re-normalized mass assigned to each row having(Y x ′ = y ′ ∣ X = x ′ )is constrained by the observational input data as P (x ′ ,y ′ )/∑ y ′ P (x ′ ,y ′ ). This follows because X = x ′ ⟹ Y = Y x ′ by consistency. Fix some valuesx ∈ X,y ∈ Y,x ≠ x ′ . Conditional on(X = x ′ ,Y x ′ = y ′ ), the re-normalized mass assigned to each row having(Y x = y ∣ X = x ′ ,Y x ′ = y ′ )is unconstrained. We can define an assignment where all the re-normalized mass is allocated to the rows having(Y x = y ∣ X = x ′ ,Y = y ′ ), and another assignment where all the re-normalized mass is allocated to rows having Y x = y ∗ ,y ∗ ≠ y. So the tight bounds forP (y x ∣ x ′ ,y ′ ),x ≠ x ′ are [0,1] givenP (X,Y ). If we assume positivity for all distributions, this becomes the open interval (0, 1).■ Lemma 4.3 (NTE -L 2 bounds). Given a bow graph causal structure (Fig. 6.a), observational dataP (X,Y ), and interventional data P (Y x ), ∀x, the query P (y x ∣ x ′ ,y ′ ),x ≠ x ′ , is tightly bounded in the range [l,r] defined as l = max 0, α min − (1 − P (y ′ ∣ x ′ )) P (y ′ ∣ x ′ ) r = min 1, α max P (y ′ ∣ x ′ ) , where(33) α min ∶= max 0, P (y x ) − (1 − P (x ′ )) P (x ′ ) α max ∶= min 1, P (y x ) P (x ′ ) (34) Further, [l,r] ⊆ [0, 1] Proof. For any two events,A,Bhaving valid probability marginalsP (A),P (B), the intersection probabilityP (A ∩ B)is bounded by the Fr ́ echet–H ̈ offding bounds for two events, max0,P (A) + P (B) − 1 ≤ P (A ∩ B) ≤ minP (A),P (B)(35) These bounds are known to be tight in terms of inputP (A),P (B). I.e., there is some valid probability measure for which either extreme assignment is possible for P (A ∩ B), given valid P (A),P (B). Setting A = Y x = y and B = X = x ′ , max0,P (y x ) + P (x ′ ) − 1 ≤ P (y x ,x ′ ) ≤ minP (y x ),P (x ′ )(36) Dividing by P (x ′ ) > 0 gives α min ≤ P (y x ∣ x ′ ) ≤ α max , for α min = max 0, P (y x ) − (1 − P (x ′ )) P (x ′ ) ,α max = P (y x ) P (x ′ ) , 1 (37) 33 Causal Identification from Counterfactual Data: Completeness and Bounding Results Now consider the conditional version of the Fr ́ echet–H ̈ offding bounds: max0,P (A ∣ B) + P (C ∣ B) − 1 ≤ P (A ∩ C ∣ B) ≤ minP (A ∣ B),P (C ∣ B)(38) Setting C = Y = y ′ , and dividing by P (y ′ ∣ x ′ ) > 0 we have max 0, P (y x ∣ x ′ ) − (1 − P (y ′ ∣ x ′ )) P (y ′ ∣ x ′ ) ≤ P (y x ∣ x ′ ,y ′ ) ≤ min P (y x ∣ x ′ ) P (y ′ ∣ x ′ ) , 1 (39) Following the reasoning in the earlier proof of Lem. 5.2,P (y x ∣ x ′ )is unconstrained by observational dataP (y ′ ∣ x ′ )alone. We can vary this term on either side of the inequality. Assigning the extremal values for P (y x ∣ x ′ ) from Eq. 37, max 0, α min − (1 − P (y ′ ∣ x ′ )) P (y ′ ∣ x ′ ) ≤ P (y x ∣ x ′ ,y ′ ) ≤ min α max P (y ′ ∣ x ′ ) , 1 (40) This range obviously must be contained in [0,1]. If all distributions are positive, 0, 1 would be adjusted to 0 + and 1 − .■ Proposition 4.4 (NTE -L 2.5 bounds). Given a bow graph causal structure (Fig. 6.a), observational dataP (X,Y ), interventional dataP (Y x ), and counterfactual dataP (Y x ∣ X),∀x, the identification queryP (y x ∣ x ′ ,y ′ ),x ≠ x ′ ,is tightly bounded in the range [l ′ ,r ′ ] defined as l ′ = max 0, P (y x ∣ x ′ ) − (1 − P (y ′ ∣ x ′ )) P (y ′ ∣ x ′ ) r ′ = min 1, P (y x ∣ x ′ ) P (y ′ ∣ x ′ ) (41) Further, [l ′ ,r ′ ] ⊆ [l,r] as defined in Lem. 5.3. Proof. It was proved in Eq. 39, thatP (y x ∣ x ′ ) ∈ [l ′ ,r ′ ].[l,r]is derived by assigning extremal values toP (y x ∣ x ′ ) ∈ [α min ,α max ]in Eq. 40, to push[l ′ ,r ′ ]to its widest in terms ofL 2 data. So,[l ′ ,r ′ ] ⊆ [l,r]. If we assume all distributions are positive, the 0, 1 would be adjusted to 0 + and 1 − accordingly.■ F. Indexing an Input Data Distribution This section is not strictly needed to understand our main results. Thm. 3.5 works with any way of writing each input data distribution as an un-nestedL 3 expression. Here, we provide a systematic way to translate from an intuitive index for each data distribution (using the actions taken in the data-collection regime) into an un-nestedL 3 expression. Any other equivalent expression would also work. We index an input data distribution by the physical actionsAthat the experimenter takes in order to collect data. For instance, Fig. 22(Left) illustrates the observational regime, corresponding toA = ∅. Fig. 22(Center) illustrates an interventional regime, where the experimenter performs a standard randomized intervention onX,A = rand(X). Fig. 22(Right) illustrates a counterfactual data-collection regime, where the experimenter performs a counterfactual randomized intervention on X , A = ctf-rand(X → Y ). See Sec. 2 for the definitions of these actions. XYXYXY Figure 22. Data-collection regimes corresponding to (Left) A = ∅; (Center) A = rand(X); (Right) A = ctf-rand(X → Y ). Note that the regime in Figure 22(center) corresponds precisely to the sub-modelM x , where ado(x)intervention replaces the equationf X with a constant valuex. However, the regime in Figure 22(right) cannot be defined in terms of a sub-model. Next, we provide a subroutine (Alg. 4) for systematically mapping the distribution indexAto a un-nested counterfactual regular expression, corresponding to the distributionP A (v ⋆ ), i.e., the distribution of variables sampled under this regime. 34 Causal Identification from Counterfactual Data: Completeness and Bounding Results Algorithm 4 REGIME-REGEX 1: Input: Causal diagram G; actions A which index the input data distribution 2: Output: Un-nested L 3 expression P A (V ⋆ = v) for the distribution of samples drawn under action set A 3: Initialize empty conjunction V ⋆ = ∅ 4: for each V ∈ V do 5:Initialize a potential response V [.] , with empty subscript 6:for each intervention a ∈ A do 7: X ← variable intervened upon in a 8: x a ← fixed value assigned to X under a 9:C← (subset of Ch(X) affected by a) ∩ An(V ) 10:C ′ ← (Ch(X) \ C) ∩ An(V ) 11:for each C ∈ C do 12:if a is superseded by a previous a ′ involving (X,C) then 13:Skip C 14:end if 15:if C = V then 16:Add or replace x a in the subscript of V [.] 17:else if C ≠ V then 18:Add or replace C x a in the subscript of V [.] 19:end if 20:end for 21:for each C ′ ∈ C ′ do 22:if encountered a previous a ′ involving (X,C ′ ) then 23:Skip C ′ 24:end if 25:if C ′ ≠ V then 26:Add or replace C ′ in the subscript of V [.] 27:end if 28:end for 29:end for 30:Add clause V [.] = v to conjunction V ⋆ = v 31: end for 32: Apply consistency property to P (V ⋆ = v) to get un-nested P (V ′ ⋆ = v) 33: Return P (V ′ ⋆ = v) XY T WZ XY T WZ x x ′ Figure 23. Example for regular expression under a regime (right) involving actions A = ctf-rand(X → Y ), ctf-rand(X → W ). Example.Consider the graphGin Figure 23, being subjected to a regime indexed by actionsA = ctf-rand(X → Y ), ctf-rand(X → W ) , as illustrated. The intermediate output ofREGIME-REGEX(G, A) at Line 31 would be P (X,T,W x ′ ,Z W x ′ ,Y xT W x ′ ). The final output of REGIME-REGEX(G, A) would be the expression P (X = x ′ ,T = t,W x ′ = w,Z w = z,Y xtw = y)(42) ■ 35 Causal Identification from Counterfactual Data: Completeness and Bounding Results Proposition F.1. Given an input data distribution indexed by a set of physical actionsA, Alg. 4 produces an un-nested Layer 3 expression P (V ⋆ = v), corresponding to this data distribution. Proof.Note that Alg. 4 involves at most one level of nesting in the counterfactual expressionP (V ⋆ = v)after Line 31. The consistency property (Correa & Bareinboim, 2025, Lemma 2.1) shows that, for any X,Y , X ⋆ (u) = x ⟹ Y ...[X ⋆ ] (u) = Y ...[x] (u)(43) A straightforward application of the consistency property toP (V ⋆ = v)yields the equivalent un-nestedP (V ⋆ ′ = v).■ Note on indexing values: in each probability distribution expression, in general (unless otherwise stated), value terms in the main line and in the subscript are indices which can overlap. For instance,P (x ′ ,y x )refers to the distributionP (X,Y x ). The specific quantityP (x,y x ), where both thexvalues are the same, can be obtained directly from one of the lines of this distribution table. We omit this level of granularity throughout the paper for readability . G. Frequently Asked Questions Q1. Where is the causal diagram coming from? Is it reasonable to expect the data scientist to create one? Answer. First, the assumption of the causal diagram is made out of necessity. The causal diagram is a well-known flexible data structure that is used throughout the literature to encode a qualitative description of the generating model, which is often much easier to obtain than the actual mechanisms of the underlying SCM (Pearl, 2000; Spirtes et al., 2000). The goal of this paper is not to decide which set of assumptions is the best but rather to provide tools to perform the inferences once the assumptions have already been made, as well as understanding the trade-off between assumptions and the guarantees provided by the method. Second, the true underlying causal diagrams cannot be learned only from the observational distribution in general. There almost surely exist situations that two SCMs induce the same observational distribution but are compatible with different causal diagrams (see Bareinboim et al. (2022, Sec. 1.3) for details). With higher layer distributions (such as distributions fromL 2 ), it is possible to recover a more informative equivalence class of diagrams that encode additional constraints present in the input layer (Kocaoglu et al., 2017; Li et al., 2023; von K ̈ ugelgen et al., 2023). Q2. What is the complexity of the CTFIDU + algorithm? Answer.CTFIDU + runs inO(zn 2 (n+ m))time, wheren,m,z,anddrefer to the number of nodes, edges, (different) interventions in Y ⋆ , and maximum cardinality of any observable variable in G, respectively. See App. B.3. Q3.What is novel about this algorithm? Can one not use inference rules like the counterfactual calculus or do-calculus to identify counterfactuals? Answer. The scope ofCTFIDU + allows for a data scientist to additionally provide as input physically realizableL 3 data. This allows more quantities to be identified. It also subsumes previous algorithms which assume access to only L 2 data, since observational and interventional data belong in the scope of input, too. Indeed, the recent development of the counterfactual (ctf-) calculus (Correa & Bareinboim, 2025) provides a powerful set of inference rules to infer counterfactuals queries from counterfactual (or any other) input distributions. However, what’s missing is a complete method for applying these rules in a systematic way. In fact, sinceCTFIDU + makes use of the ctf-calculus in its steps, Thm. 3.5 provides proof that ctf-calculus is indeed complete for the task of identifying L 3 quantities from physically realizable data. Prior results have only shown completeness for a scope ofL 2 input data. Q4. What is meant by realizable data distribution? Is it realistic to assume access to counterfactual data? Answer. Realizable data distributions are those from which an experimenter can collect data samples directly using the following actions: passive observation of a system, standard interventional randomization of some variable(s) which we notate as rand(), or counterfactual randomization of some variable(s) which we notate as ctf-rand(). See Sec. 2 for definitions of these actions. Conventional wisdom has long assumed that data can only be gathered in the real world (i.e. not in a simulated environment where the full SCM specification is known) from observational or interventional distributions. An emerging thread of research has challenged this belief, showing there are indeed realistic settings that permit counterfactual data 36 Causal Identification from Counterfactual Data: Completeness and Bounding Results collection (Bareinboim et al., 2015; Zhang & Bareinboim, 2022; Forney et al., 2017; Yang & Bareinboim, 2025) via the procedure of ctf-rand(). Each input data distribution is indexed by which actions are taken in that data-collection regime, and for which variable(s). This distribution can then be used as input to the CTFIDU + algorithm. 37

Instant research discovery

Causal Identification from Counterfactual Data: Completeness and Bounding Results

Intelligence

Summary

Entities (10)

Relation Signals (9)

Abstract

Tags

Links

PDF

Full Text

Paper	Published	Area	Tags	Intel	Citations