Query-Specific Causal Graph Pruning Under Tiered Knowledge
Authors: Yizuo Chen
Jane E. Barker
Venue: ICLR 2026 Poster (2026)
Keywords: Causal Inference
Graph Pruning
Tiered Knowledge
Primary area: causal reasoning
TL;DR: We present a method for pruning edges from causal graphs by leveraging tiered knowledge, which leads to significant speedups in causal discovery.

Abstract: We present a systematic method for pruning edges from causal graphs by leveraging tiered knowledge. We characterize conditions under which edges can be removed from a causal graph while preserving the identifiability of (conditional) causal effects. This result enables causal identification on simplified graphs that are substantially smaller than the original graphs. The approach is particularly valuable when researchers are interested in causal relationships within specific tiers while accounting for broader influences from other tiers without fully specifying them. Building on this, we introduce a query-specific causal discovery algorithm that takes a causal query and observational data as input and returns a graph tailored specifically to that query. Through both theoretical analysis and empirical studies, we demonstrate that our discovery algorithm can achieve exponential speedups compared to the existing method when tiered knowledge is available.

Published as a conference paper at ICLR 2026
QUERY-SPECIFIC CAUSAL GRAPH PRUNING UNDER TIERED KNOWLEDGE
Yizuo Chen'
Jane E. Barker Amazon Bellevue, WA 98004, USA
University of California, Los Angeles Los Angeles, CA 90095, USA y rizuo. Sehhenuullaa edu
com
ABSTRACT
We present systematic method for pruning edges from causal graphs by lever- aging tiered knowledge. We characterize conditions under which edges can be removed from a causal graph while preserving the identifiability of (conditional) causal effects. This result enables causal identification on simplified graphs that are substantially smaller than the original graphs. The approach is particularly valuable when researchers are interested in causal relationships within specific tiers while accounting for broader influences from other tiers without fully speci- fying them. Building on this, we introduce a query-specific causal discovery algo- rithm that takes a causal query and observational data as input and returns a graph tailored specifically to that query. Through both theoretical analysis and empiri- cal studies, we demonstrate that our discovery algorithm can achieve exponential speedups compared the existing method when tiered knowledge available.
INTRODUCTION
Pearl's Causal Hierarchy categorizes queries into three separate layers: associational, interventional, and counterfactual (Pearl & Mackenzie 2018). The first layer examines statistical associations es- timable from observational data, while the latter two layers involve causal interventions and require understanding causal relationships between variables typically established through experimental studies (e.g., randomized controlled trials). We focus on the second layer and consider two widely studied types of interventional queries: causal effects and conditional causal effects. A causal effect quantifies the impact of an intervention on an outcome, exemplified by the question "What is the probability that a patient will recover after the doctor instructs them to undergo surgery?"' whereas a conditional causal effect further restricts the query to a subpopulation and asks "What is the prob- ability that patient older than 65 will recover after the doctor instructs them to undergo surgery?"
common approach to answering these causal queries is through causal identification. Given a causal graph G and observational distribution Pr(V), causal identification aims to estimate the values of these causal queries from G and Pr(V). This gives rise to the identifiability problem, which checks whether the values of causal queries uniquely determined by G and Pr(V (V.. Sound and complete methods for testing identifiability have been developed, including the IDENTIFY algo- rithm in (Tian & Pearl 2003 Huang & Valtorta 2006). the ID algorithm (Shpitser & Pearl 2006). do-calculus (Pearl 2009) for identifying causal effects, and the IDC algorithm (Shpitser & Pearl 2008) for identifying conditional causal effects. Among these methods, the choice of causal graph plays a crucial role in determining both identifiability and the values of causal queries. For instance, consider the causal effect of surgery on patient recovery. The causal effect identifiable if the graph contains a directed edge Surgery + Recovery but becomes unidentifiable if hidden con- founder introduces an additional bidirected edge Surgery + Recovery The causal effect remains identifiable if the graph contains reversed edge Surgery +- Recovery but becomes negligible.
Recent advancements in causal inference have expanded beyond traditional frameworks by integrat- ing background knowledge with causal graphs and data, leading improvements in both identifi-
TThis work was done during the author's 's internship at Amazon.
'The bidirected edge A <+ B means A +- U + B where U is hidden confounder causing both A and B. For example, patients' symptoms are potential hidden confounders hetween "Surgery" and "Recovery".

---

Published as a conference paper at ICLR 2026
A
Aa
As
A
Aa
Aa
A
Aa
As
A 8
O. O
8
B
B
B
B
B
B
B
B
B
B
8
B
B3
C
Ca
Ca
Ca
Ca
(a) original graph G
(b) pruned graph H
(c) mutilated graph
(d) PAG
Figure 1: Pruned, mutilated, and partial ancestral graph (PAG) for G. Tiers are indicated using distinct alphabetical letters. For example, the three tiers in the graph may represent the lecture quality, the student's 's learning effort, and quiz scores over three consecutive weeks.
ability and computational efficiency. These include leveraging the knowledge of functional depen- dencies (Darwiche, 2021| Chen & Darwiche 2022: 2024), context-specific independencies (Tikka et al., 2019 Mokhtarian et al. (022), and fully-known observational distributions (Chen & Dar- wiche 2025 y. In this work, we extend this research line by showing another benefit of incorporating background knowledge: it simplifies the causal graphs required for causal identification. In partic- ular, we consider tiered knowledge, which partitions variables into "tiers" with a predefined causal ordering, allowing only directed edges from higher tiers to lower tiers (Andrews et al. 2020). Such type of knowledge arises frequently, for example, in temporal reasoning where variables are ordered according their time steps, and when exogenous context (background) variables are included in causal graphs; see (Andrews et al. 2020) for detailed discussions.
The main contribution of this work is technique for pruning edges from causal graphs using tiered knowledge while preserving the identifiability of (conditional) causal effects. We show that this technique enables testing identifiability on simpler graphs while maintaining soundness and com- pleteness. As preliminary example, consider the causal graph in Figure Ta which contains three tiers (distinguished by alphabetical letters). Our pruning method allows us to establish the identifi- ability of Pr (B3, Ca) and Pre, (Ba, CalAi) by showing that they are identifiable in the smaller graph H (Figure lb) constructed specifically for the given causal queries. A key advantage of using such query-specinie graphs is that they reduce the effort for graph specification when edges either determined through background knowledge or learned from data. We demonstrate this advantage by presenting causal discovery algorithm that learns query-specifie graphs from observational data, achieving exponential computational speedups over the existing method that constructs full graphs.
The paper is structured follows. We start by reviewing some key definitions and methodolo- gies in the literature on causal inference and discovery in Section [ In Section 3 we present our main results on graph pruning that preserves the identifiability of both unconditional and condi- tional causal effects. We follow this by introducing causal discovery algorithm for learning query- We provide experimental We finally close with some
specific graphs along with an analysis of its complexity in Section results demonstrating the effectiveness of our method in Section 5 concluding remarks in Section All proofs are included in the Appendix.
2 TECHNICAL PRELIMINARIES
We assume all variables are discrete, though all the results presented in this work can be extended to continuous domains. Single variables are denoted by uppercase letters (c.g., X) and their states are denoted by lowercase letters (e-g., 2)). Sets of variables are denoted by bold uppercase letters (e.g., X) and their instantiations are denoted by bold lowercase letters (e.g., x).
2.1 CAUSAL GRAPHS AND TIERED KNOWLEDGE
Causal graphs are widely used to model the causal relationship among variables. In this work, we consider causal graphs in the form of Acyclic Directed Mixed Graphs (ADMGs), which contain both directed and bidirected edges and do not assume causal sufficiency.
Definition 2.1. (Richardson 2003 An acyclic directed mixed graph (ADMG) is a graph that con- tains directed edges (-)) and bidirected edges (<>) and in which directed edges do not form cycles.
2

---

Published as a conference paper at ICLR 2026
Figures La and lb are both valid ADMGs. The edges in ADMG are interpreted follows. Each directed edge A - B means that A is a direct cause of B: in this case, we call A a parent of B and B a child of A. Each bidirected edge A <+ B indicates the existence of a hidden (unobserved) confounder causing both A and B. In Figure Ta for example, A₁ is a direct cause of C2. and there exists hidden confounder between B, and B3- We denote the observed variables in an ADMG by V and the hidden confounders by U. Variable A is a neighbor of B if there is an edge (directed or bidirected) between A and B. Two variables A, 1 are said be in same c-component if they are connected by bidirected path, i.e., a path containing only bidirected edges (Tian & Pearl 2002). The variables in graph can always be partitioned into e-components. For example, the variables in Figure Ta can be partitioned into (A1, A2, A3). {Bi, Ba). (B2). (Ci), {C2), and {Ca).
Tiered knowledge imposes additional constraints on causal graphs by specifying a causal ordering over its variables (Andrews et al. 2020 By definition, tiered knowledge partitions V into / tiers (disjoint subsets), denoted [V'..... V where only directed edges can be added from higher tiers (tiers with smaller indexes) to lower tiers (tiers with larger indexes). That is, for each pair X E V and Y E V where i < j. only the edge X + Y is permitted. Consider Figure Ia with tiers { {A1, A2, As), {B1, B2, By). and {C1, C2, Cs}. The directed edge A1 - C2 is allowed since A1 belongs to a higher tier than C2, whereas neither B2 + A2 nor B2 + A2 is allowed since B2 belongs to a lower tier than A2. All edges in Figures Ta and Tb satisfy this constraint. Such tiered knowledge commonly arises in scenarios where time-series features exhibit contemporaneous confounding, a set of context (background) variables are exogenous to the variables of interest, or features are organized into hierarchical order, see Appendix B for further elaboration on these scenarios and (Andrews et al. 2020) for additional examples.
For simplicity, we use I' to denote the tier mapping where r(() = i for each X E V For a set of variables W, let -- (W) denote the minimum tier index of W, i... - (W) = minwew I(W), and let I+ (W) denote the maximum tier index of W, i.e., I* (W) = mazwew I(W). In Fig-
ure Ta for example, (B,,, B3, C2) = 2 and r+ (B1, B3, C2) 3.
2.2 IDENTIFYING (CONDITIONAL) CAUSAL EFFECTS
The identification of unconditional and conditional causal effects from observational data has been studied extensively in the past; see, c.g., (Pearl) 2009 Hernán & Robins 2020; Peters et al., 2017 Imbens & Rubin 2015 Tian 2004; Shhptser & Pearl 2008). Let G be a causal graph and M be model (parameterization) for G, an intervention do(x) induces mutilated graph Gx obtained from G by removing all the incoming edges of X, and a modified model Mx obtained by fixing the states of X x in M. Figure [[] depicts the mutilated graph under interventions on Ag, Bi The modified model Mx induces an interventional distribution, denoted (rx(V, U). used to compute (conditional) causal effects. Given set of treatments X and set of outcomes Y. the causal effect of X on Y. denoted Prx (Y). computes the marginal distribution Prx (Y) ) for each instantiation x. The conditional causal effect further takes a variable set Z and computes Prx( Y [Z) for each x.
The identifiability problem studies whether a causal query is uniquely determined by the causal graph G and observational distribution Pr(V). We next review the formal definition of conditional causal effect identifiability unconditional causal effect identifiability is special case when Z = 0.
Definition 2.2. (Tia 2004) The conditional causal effect of X on Y given Z is said to be identifiable with respect to (G, V) if Pr (r (2) = Pr (ylz) for every pair of distributions P,1
and P.2 induced by G such that Pr (V) = Pr (v2(V)
A causal query is called unidentifiable if it is not identifiable. In Figure la Pre. (Ba, Cis) and Pra,,,, C2) are both identifiable. On the other hand, PF (Bs, C2) and PTA, (CalAs) unidentifiable. Sound and complete methods based on c-components have been developed for iden- tifying both unconditional and conditional causal effects in the past; see, e.g., (Tian & Pearl 2003 Huang& & Valttrrtl 2006, [Shpitser & Pearl 2008). Intuitively, these methods test the identifiabll- ity of (conditional) causal effects by reducing to independent identifiability problems over the c-components in the causal graph. Moreover, they provide a formula for estimating the causal ef- fects if they are deemed identifiable. For example, the IDENTIFY algorithm (Tian & Pearl 2003) not
'The strict positivity here is commonly assumed by existing identification methods such do- calculus (Pearl 2009) and IDENTIFY (Tia & Pearl 2003).
3

---

Published as a conference paper at ICLR 2026
(a) original
(b) projected
(c) funetionally-Projccteed
Figure 2: Original. projected, and functionally projected graphs that preserve identifiability.
only establishes the identifiability of Prø, (B3, C3) in Figure la but also yields the following for- mula: Pre, (bs, Cx) = Eui,oo Luu.aa,bb.c. a03.b2,...c Pr(a1, 0z) Pr(by)) Pr(cc ( Pr(cy) b2, ea )P((calb,, 02) Eg Pr(bslas, Bi) Pr(bt); see Appendix A for additional details on the identification methods.
2.3 CAUSAL DISCOVERY WITH TIERED KNOWLEDGE
When causal graphs are learned from observational data, it is standard to consider the class of Max- imal Ancestral Graphs (MAGs), subelass of ADMGs that satisfy additional properties Existing causal discovery algorithms such as Fast Causal Inference (FCI) (Spirtes et al.] 20000 take obser- vational data input and learn a Markov equivalence class (MEC) consisting of all MAGs that encode the same conditional independencies. Such MECs are commonly represented using Partial Ancestral Graphs (PAGs), which contain edges of the forms -, ++, c- and a-o, where each can be either an arrowhead or a tail. For example, Figure Id depicts a PAG representing the MEC that contains the MAG in Figure Ta To utilize these PAGs for causal identification, is common to per- form a postprocessing step that recovers the true causal graph (MAG) by replacing each mark in the learned PAG with either an arrowheads or a tail. This can be achieved using approaches that leverage background knowledge (Meek] 1995, Heckerman et al. 1995 BBrboudakis & Tsamardinos 2012) or incorporate experimental data (He & Geng. 2008: Hauser & Bühlmann] 2014]] Kocaoglu et al.,
2017]. Another line of work derives bounds by enumerating MAGs from the PAG and computing
causal effects for each MAG (Hyttinen et al. 2015 Malinsky & Spirtes, 2017 Wang et al. 2024
When tiered knowledge is available, modified FCI algorithm was proposed in (Andrews et al, 2020) to learn a PAG from observational data. The algorithm is sound and complete for recovering the maximally informative PAG that encodes the conditional independencies in the observational distribution Pr(V) and that respects the tiered knowledge Moreover, suppose Pr(V) reflects the conditional independencies implied by causal graph G, the algorithm is guaranteed to return a PAG representing the Markov equivalence class that contains G; see Section for more details.
3 GRAPH PRUNING UNDER TIERED KNOWLEDGE
We now present methods for pruning edges from causal graph while preserving the identifiability of a given (conditional) causal effect under tiered knowledge. These methods allow us to reduce the identifiability problem in the original graph G to the identifiability problem in pruned graph G', which is advantageous when G' is easier to attain than G. In this case, we say that G and G' are ID-equivalent since they yield the same identifiability results for the given causal effect.
Such type of pruning-based approach for testing identifiability have been explored in prior works. A well-known example the (latent) projection operation (Verma 1993] Tian & Pearl (002). which removes hidden variables from a DAG before applying causal identification methods such as those
2 MAAS are a subclass of ADMGs that satisfy ancestrality and maximality. Ancestrality prohibits bidirected edges between nodes X and there is a directed path from to Y. Maximality requires that any non- adjacent nodes X, Y can he m-separated by some other variables; see (Richardson & Spirtes 2002) for details.
An alternative approach avoids the conversion to MAGS by directly identifying causal queries from PAGs;
sec, e.g., (Jaber et al. 2022 Perkovic et al. (2077).
Formaall, a PAG maximally informative if cach edge mark in the PAG corresponds to an arrowhead in
MAG and an arrow tail in another MAG within the MRC.
4

---

Published as a conference paper at ICLR 2026
4
42
As
4
42
As
A
A2
As
A
42
4
B.
B2
B3
B
B3
B1
B2
B3
B1
B
G
C
C2
C3
6
C
G
C₂
Cs
D
D2
Dg
D
D2
D2
D
D2
Da
D
D2
Da
(a) original
(b) Prø, (Ci, Cz)
(c) Pre, (D2, Da] B2)
(d) Pre, (Ci Bs)
Figure 3: Original graph and its pruned graphs for identifying Prø, (C1, C2), Prc, (D2, D3 A1, B2)
and Prø, BC, Bz). Tiers are indicated using distinct alphabetical letters.
in (Tian & Pearl 2003 Shpitser & Pearl
2006) Figure 2b depicts the result of applying projection
on Figure 2a when varialle B is hidden. Tikka & Karvanen (2017) further studied the pruning of
observed variables from causal graphs to simplify the identification process. More recently, a refined projection operation called functional projection was introduced to eliminate (remove) variables that exhibit functional dependencies on their parents (e.g.. "legal driving age" is functionally determined by "country") (Chen & Darwiche, 2024). For example, suppose variable D in Figure 2b exhibits functional dependency on its parents {X,C), C). then eliminating D using functional projection yields the graph in Figure 2c Both projected and functionally projected graphs are ID>equivalent to the original graph and can thus be used to test causal effect identifiability.
The pruning methods introduced in this work also construct ID-equivalent graphs but differ from the above approaches in two key aspects. First, our methods remove edges rather than variables from causal graphs. Second, our methods can be applied whenever tiered knowledge is available, whereas the previous approaches require the full causal graph to be known. The second distinction allows us to identify causal effects using a smaller graph by leveraging tiered knowledge. avoiding the need to specify (or learn) the entire causal graph as typically required in classical approaches.
3.1 EDGE PRUNING FOR CAUSAL EFFECTS
Unless stated otherwise, let G denote a causal graph in which the observational variables V are partitioned into tiers (V1,... Vt) with tier mapping r. Moreover, let X and Y denote disjoint sets of treatment and outcome variables, respectively. We start by reviewing key graphical notion introduced in (Andrews et al., (2020), which we refer to as "T-component" for convenience.
Definition 3.1. (Andrews et al. 2020) The 5th (1 < () tiered-component (T-component) is the subgraph of G containing all variables of G and all edges (I, for which maz (1()),,((r))
For simplicity, we denote the 7hh T-component as G In Figure 3al edges in different T-components are highlighted with distinct colors. One key result is that causal graph can always be decomposed into T-components based on tiered knowledge, i.e., G Ul=1 G
We now present our main result which prunes edges from the original graph G while preserving the identifiability of causal effect Prx (Y).
Proposition 3.2. Let Н be the union of all T-components G with (X) S i (+) Then Prx (Y) is identifiable in G iff it is idenrifiable in H and can be computed as Prx(y) Ewly Pr( w DDEEIIIEE и (x U w.y \ w), where W is the set of variables whose tier indexes are smaller than 1' (X), and IDENTIFY H (xJw,y' y'(()) denotes the formula returned by IDENTIFY TTan & Pearl 2003 for identifying Prxw (y w) in the graph H
Consider the causal graph G in Figure 3a and the causal effect PRB, (C1,C2). Without tiered knowl- edge, we would typically construct the full graph G containing all edges and use it to identify the causal effect. However, suppose we know in advance that G can be partitioned into four tiers (in- dicated by different alphabetical letters), we can apply Proposition 3.2 and use the pruned graph H
'hhe union graphs G (V1, E.). G (V., E.) induces a new graph G(U!., Vr,U E.).
"The completeness of IDENTIFY was proven in (Huang & Valtorta 2006). The IDENTIFY algorithm here can also be replaced by the ID algorithm (Shpitser & Pearl (006) which is also sound and complete. We cannot replace IDENTIFY with Prxw (y \ w) here since the distrihution Pr not induced hy the subgraph H.
5

---

Published as a conference paper at ICLR 2026
shown in Figure 3b for identification. Specifically, H is constructed as the union of T-components
G2 and G since (X) = (B1) = 2 and (Y) =T C2) = 3. The pruned graph H. contains in-tier edges (e.g.. Ci + C2) and cross-tier edges (e.g., A - C1). It is important to include cross-tier edges in pruned graphs for several reasons. First, when the pruned graph is learned from observational data using causal discovery algorithms, omitting cross-tier edges may lead to erroneous edges in the graph, which can potentially alter identifiability results. For example, ignoring C3 + D2 and C3 + D3 in Figure 3a would introduce a false-positive edge between D2 and D3. Second, cross-tier edges capture parent-child relationships that can be leveraged to simplify the identifying formulas in Proposition [32] see footnote X for a concrete example.
Proposition 3.2 establishes two key properties of the pruned graph H. First, the identifiability of the given causal effect is preserved, i.e., the original and pruned graphs are IDDequivvalent For example, we can apply existing methods such as IDENTIFY to establish the identifiability of Præ, (C1, C2) in Figure 3bb Second, the proposition provides an identifying formula for estimating the causal effect from H if it is identifiable. In this example, one such formula is PTo, (c1, 02) Lar.ag.b Pr(a1, a2)
Pr(b2laz, by )Pr(e2 a1, b2, 01) Pr(ci laı) Note that the formula in Proposition 3.2 is constructed in particular way, as general identifying formulas derived from pruned graphs may not be valid for identifying causal effects in the original graph. To illustrate, the following formula correctly
computes Prz, (C1, C2) in H: Pro, (c),02) Es, IEag Pr(cz]a1, b2, e1) Pr(ai, ct]] [ a2 Pr(az)
Pr(bglag, b ).)]. yet it does not compute the causal effect in the original graph in Figure 3a and hence
cannot be used. Such errors occur since the pruned graphs ignore dependencies among variables in tiers above treatment variables X, which are essential for estimating causal effects correctly.
A remaining question is whether the ID-equivalent causal graphs constructed by Proposition 3.2 are optimal in size. Finding minimal ID-equivalent causal graphs offers significant benefits for causal graph specification. For graphs constructed from human knowledge, only edges in the minimal graphs need to labeled, which can save significant manual effort when the original graphs are large or when some edge orientations are unknown. For graphs learned from data, using smaller graphs can substantially reduce the computational cost of causal discovery as we demonstrate later.
We show that the bounds (X) and I+t (Y) provided in Proposition 3.2 are tight. Specifically, the identifiability of causal effects may no longer be preserved if we prune additional edges from G by increasing (X) or decreasing I r+t (Y). This holds trivially when r-(X)= > r r-YY) since the pruned graph contains no edges. The next proposition proves the tightness for all remaining cases.
Proposition 3.3, Let L.U, L', , be positive integers satisfying L. S U, L' < U', and at least one of C or U' < U holds. Then there exists a causal graph G and a tier mapping I' for which C, (Y) are replaced with L' and
U, and Proposition 3.2 no longer holds if the bounds I' (X) and 1 (Y)
Before discussing edge pruning for conditional causal effects, we highlight an important result on the size of pruned graphs: there exists a class of graphs where the sizes of original graphs are un- bounded, while the sizes of their pruned graphs (from Proposition 3.22) are bounded. Such graphs can be constructed, for example, by adding more tiers to Figure Bal As more tiers are added above B, 's, the size of the original graph grows to infinity. whereas the size of the pruned graph used to iden- tify PrB, (C1, C2) remains constant. This result has important implications for graph specification: when causal graphs are constructed from background knowledge may suffice to specify or learn a constant number of edges to identify the causal effect, even if the full causal graph is arbitrarily large. We formalize this result in the following proposition.
learned via causal discovery, it
Proposition 3.4. There exists a class of causal graphs Gt with tiers such that the number of edges in G grows without bound as t increases, while the corresponding pruned graphs (Proposition 3.2) contain constant number of edges.
3.2 EDGE PRUNING FOR CONDITIONAL CAUSAL EFFECTS
We now consider another class of causal queries called conditional causal effects. These queries generalize causal effects by taking an additional set of conditioning variables Z as input and compute Prx (z)( Analogous to the case of causal effects, we introduce a method that prunes edges from
"The formula simplified from the output of IDENTIFY: Pre, (2) = E., a2. Pr(an, 02, as)
Pr(b2/as, b1) Pr(czlas, b2, e1) Pr(ci]aa). This illustrates the benefit of including cross-tier edges.

---

Published as a conference paper at ICLR 2026
causal graphs while preserving the identifiability of Prx (T)). The pruming criterion, however, is more subtle for conditional causal effects as it depends on the choice of conditioning variables Z.
We start with the case where variables in Z belong to higher tiers than the treatments X.
Proposition 3.5. Ler H be the union of all T-components G with (X) I i S I+()). If
(Z) < (X), then Prx(Y(Z) is identifiable in G iff it is identifiable in H and can be com- puted as (rx(y (Ix(y,2)
Pr(x)
That is, a conditional causal effect is identifiable in the original graph G iff it is identifiable in the pruned graph H. We stress again that this reduction only holds when the conditioning variables Z are in tiers above the treatment variables X. The identifying formula contains two parts: an interventional probability Prx(y,2, z) and an observational probability Pr(z). While Pr(z) can be directly computed from the observational distribution, Proposition 3.2 can be applied to estimate Prx (y: z) by setting the treatments to X' X and the outcomes to Y Y U Z. Interestingly,
the pruned graph constructed for (ixx(')) using Proposition 3.2 is always identical to the pruned graph constructed for Prx (Y) using Proposition 3.5 when r+1 (Z) < (X))
Consider again the causal graph in Figure 3a but with a conditional causal effect PRB, C2
Since I+ (Z) = (A2) = 1 is less than I (X) = - (=)BB = =2, we can apply Proposition 3.5 and test identifiability in the pruned graph H in Figure 3b Specifically, the conditional causal
effect is identifiable in H according to the IDC algorithm (Shpitser & Pearl (006) and can be
computed Pre, (e1, C2(22
Prs, (01.02.02), where Pro, (c1, is further identified from H Pr(ez) as Pro, (c1,02, a2) = Ean .b Pr(ai, a2) Pr(bz]a2,b1, bi) Pr(c2 (a,, b2, ci) Pr(cilai) (ai) using Proposi- tion 3.2 Our second example examines the same graph but a different conditional causal effect Pra, (1), A1 B2). Since (A1, B2) < (C1), we can again apply Proposition 3.5 and test identifiability using the pruned graph in Figure 3e which concludes that Prc, (D2, Da B2) is
unidentifiable by the IDC algorithm. Similar to the case of unconditional causal effects, the bounds in Proposition 3.6 are tight, which we formulate and prove as Proposition D.2 in the Appendix.
One may naturally ask whether the edge pruning method remains valid when the condition r (Z) (x() is violated. The answer is no. To illustrate, consider the causal graph in Figure 3a and the conditional causal effect Pr (Cr [2,, Ba). The condition required by Proposition 3.5 longer holds since r+ B3) = r (B.). In this case, the causal effect is unidentifiable in the original graph according to the IDC algorithm but becomes identifiable in the pruned graph shown in Fig- ure 3d This example demonstrates that the edge pruning method does not, in general, preserve the identifaailityy of conditional causal effects when conditioning variable lies in the same or lower tier than treatment variable under tiered knowledge.
However, we can always prune edges in tiers below (Y U Z) while preserving the identifiability of Prx (Y We state this result as Proposition 3n6 illustrate with an example below.
Proposition 3.6. Let H be the union of all T-components G with S (+(YU))) Then Prx (YIZ) is identifiable in G iff it is identifiable in H. Moreover, any formula that computes Prx (Y (Z) in H also correctly computes it in G.
Consider again the graph in Figure and the conditional causal effect Pra, (C₂ on the right depicts the graph resulting from Proposition 3.6 In contrast to Figure 3d prune all edges below the C,'s while retaining all edges at or above them. We can then apply the IDC algorithm to the pruned graph and conclude that Præ, (C1l B2, B₂)) is unidentifiable. Although the edge pruning described by Proposition appears to be more con- servative than that in Proposition [35] it is applicable regardless of the choice of conditioning variables and can still improve the efficiency of existing causal discovery algorithms, which we demonstrate in the following sections.
Bg, B2).
The figure
A
A
As
B
B
B
C C2
Ca
1)
D2
QUERY-SPECIFIC CAUSAL DISCOVERY
We now present key application of edge pruning methods introduced in the previous sections: celerating causal discovery when causal graphs are learned from data. This task happens frequently in practice when causal graphs are not available from background knowledge and hence need to be
7

---

Published as a conference paper at ICLR 2026
Algorithm 1 Query-Specific Causal Discovery Under Tiered Knowledge
Input: Variables V = (V',.... ,...,,'J with t tiers; conditional causal effect Prx (2)
Output: PAG P
I: M Preprocessing to determine the min and max tier indexes */
2: if Z = @ or 1 (2) < T=(00 (X) then
3:
mazTTier - (Y)). minTier + (X)
else
mazTier < P UYZU, minTier +-
6: end if
7: / The following is adapted from (Andrews et al. 2020 Algorithm 1) */
8: G <- unconnected graph over V
9: for mazTierr minlieer ier do
10:
A. -
11:
B, --V V
12: p + FCIEXOGENOUS(A; B.)
Andrews et al. 2020
Algorithm 2)
13: p+ PUP
14: end for
inferred from data. From now on, we assume that the causal graphs are in form of MAGs which is commonly assumed in existing causal discovery algorithms that account for hidden confounders; see, e.g., the setups of FCI (Spirtes et al. 2000) and GFCI (Ogarrio et al., 2016). When the goal to compute (or bound) a causal effect, it is standard to first apply causal discovery algorithms to learn Markov equivalence class (MEC) represented by PAG, and then extract MAG (or multiple MAGs) from the class to estimate the causal effect, see Section 2.3 for our earlier discussion. Once a MAG is obtained, we can apply the methods in Propositions 3.2 3.6 to identify the causal effects 10
We show how the pruning methods introduced in earlier sections can be applied to speed up causal discovery when tiered knowledge is available. In partieular, extend these methods to PAGs so that it suffices to learn smaller PAGs tailored to the causal query of interest, which reduces overall computational cost. Given full PAG whose variables are partitioned into tiers, the corresponding partial PAG can be obtained by applying Propositions 3.6 replacing causal graphs with PAGs. For example, identify the causal effect Prg, (C2) in Figure 4a we only need learn the partial PAG in Figure 4d from observational data, rather than the full PAG in Figure 4b This is because
the pruning methods in Propositions 3.2 3.6 enable identification using the smaller MAG shown in Figure 4c whose Markov equivalence class Is captured exactly by the partial PAG.
Algorithm | presents the detailed procedure for query-specific causal discovery. The algorithm follows a structure similar to the FCITIERS algorithm introduced in (Andrews et al. 2020 but includes an additional preprocessing step in lines 1-6. Given a conditional causal effect Prx( (YZZ. the preprocessing step identifies the remaining T-components in the partial PAG after pruning edges according to Proposition 3.2 3.6 For example, G² and G are the only remaining T-components after pruning edges from the PAG in Figure 4b for the causal effect Pra, (C2). The algorithm then iterates over each remaining T-component, learning its edges using the FCIEXOGENOUS procedure described in (Andrews al. (2020) (lines 7-14); see Appendix Copeenix(Cforr further details. In this example, learning T-components G and G yields the partial PAG in Figure 4d
The following result states that Algorithm is sound and complete for learning partial PAGs. That is, the algorithm is guaranteed to find the maximally informative PAG when the observational dis- tribution reflects all the conditional independencies implied by the true causal graph.
Proposition 4.1. Let G be a MAG, P be the maximally informative PAG for the MEC of G under tiered knowledge, and Pt be the result of pruning edges from P according to Propositions 3.2 3.6 Then Algorithm returns P' when using G as the conditional independence oracle.
Results in previous sections hold for MAGs well since they are subclass of ADMGS.
1ooo illustrate, the edge C3 a-t C22 in the PAG in Figure 4d may be oriented as C3 ++ C2 based on background knowledge, yielding MAG in Figure 4c which is used to identify the causal effect Prø, (C2). Causal identification methods (e.g., IDENTIFY, ID, IDC) run in polynomial time and are much faster than causal discovery, so the time required for identifiability checks negligible here.
8

---

Published as a conference paper at ICLR 2026
A
A2
4s
4 0
0420
04
A
A2
A3
A
A2
B1
B2
B3
B
B1
B
B3
B2
B3
0
C2
C
C2
0
C2
C3
C1
C2
OC
D
D2
Da
D
D2
D
D2
Da
D
D2
Da
(a) MAG
(b) PAG
(c) MAG for Pre, (C2)
(d) PAG for Prøy (C2)
Figure 4: MAG G. PAG for G. MAG required for PRB, (C2), and PAG learned from Algorithm
A key benefit of focusing on a partial (smaller) PAG is the reduction in computational cost during causal discovery. In Section 2.3 we presented class of causal graphs whose size grows unbound- edly with an increasing number of tiers, but which can be reduced to a bounded size with edge pruning. This example remains relevant for causal discovery, where learning full PAGs can be com- putationally unbounded, while learning the corresponding partial PAGs is tractable. Here, we show an additional result demonstrating that the edge pruning technique can yield exponential speedups in causal discovery even when the number of tiers is fixed. This happens when most edges are located the higher tiers of PAGs and can therefore be pruned, avoiding the need to perform an exponential number of conditional independence tests to learn these edges.
Proposition 4.2. There exists a class of causal effects and distributions induced by causal graphs with n nodes and tiers for which FCITIERS (Andrews el al., 2020) takes On 2n) time, whereas Algorithm takes O(n²) time, assuming access to conditional independence oracle.
5 EXPERIMENTS
We present empirical results to demonstrate the improved computational efficiency enabled by our query-specific causal discovery algorithm. Specifically, we compare the execution times of FcI- TIERS (Andrews et al. 2020), which learns full PAGs, and our Algorithm D which learns partial PAGs, on randomly generated causal graphs and (conditional) causal effects.
We start by generating random causal graphs with T E (5, 6, 7, 9, 10) tiers, where each tier contains 10 variables that have either two or three states. We randomly assign at most 5 parents for each variable and randomly convert 30% of the in-tier (directed) edges into bidirected edges. To ensure sparsity, we bound the number of neighbors for each node by 4. We then randomly assign a parameterization for the causal graph and sample 500, 000 data instances from the model. Finally, we generate a conditional causal effect by randomly selecting treatment variables, 3 outcome variables, and conditioning set of size {0, 1,2,3) 3} from the causal graph.
Figure 3 compares the execution times of FCITIERS (Andrews et al.) 2020) and Algorithm D for learning PAGs from generated samples, averaged over 30 runs. We observe the following patterns. First, Algorithm [ acchieess shorter execution times in all cases, which matches our expectation that edge pruning accelerates the learning of partial PAGs. Moreover, for fixed number of conditioning variables, the performance gap between the two algorithms widens as the number of tiers in the causal graph increases, since additional tiers provide more opportunities for edge pruning. Second, for a fixed causal graph, increasing the size of the conditioning set Z reduces the performance gap. This happens because the constraint I (Z) r (X) in Proposition 3.5 is less likely hold under a larger Z, resulting in less edge pruning.
In addition computation time, we evaluate the precision and recall of the adjacencies and arrow- heads learned by both methods, as reported in Table in the Appendix [T] In particular, the PAGs returned by each method are compared against the ground truth obtained by running FCITIERS with the true causal graph the conditional independence oracle. The results show that Algorithm
"Thee adjacency (arrowhead) precision and recall are used in (Scheines & Ramsey 2016 to evaluate the soundness and completeness of causal discovery algorithms. Adjacency (arrowhead) precision measures the proportion of predicted edges (arrowheads) that are present in the true PAG, and adjacency (arrowhead) recall measures the proportion of true edges (arrowheads) correctly predicted by the algorithm.

---

Published as a conference paper at ICLR 2026
Twred FCI Aigonihim
Tesed FCI
120
Tired FCI
Tixed FCI Algorthm
100
100
Aigenthi
302
Aigorthm
Time
Troe
80
60-
60-
60-
20
20
20-
Num Tlers
Num Tlers
Num Tiers
Num Tiers
(a)
Z
(b)
Z
(c)
Z
Z
Figure 5: Comparison of execution times between tiered FCI (Andrews et al.
2020 and Algorithm
for varying sizes of the conditioning set Z. The queries are reduced to causal effects when |Z]
achieves precisions and recalls comparable to FCITIERS, supporting the soundness and complete- ness of Algorithm Tin in identifying partial PAGs.
6 CONCLUSION
We proposed a graph pruning method that removes edges from causal graphs while preserving the identifiability (conditional) causal effects under tiered knowledge. This approach can enable more efficient specification of causal graphs for causal effect identification, whether the graphs are constructed from background knowledge or learned from observational data. this work, we fo- cused on the latter case and developed a causal discovery algorithm that incorporates graph pruning as a preprocessing step, achieving significant speedups over the cxisting method. Potential future research directions include extending the pruning methods to additional query types such coun- terfactuals and generalizing the framework to handle bidirected edges across tiers.
ACKNOWLEDDGMENTS
This work is supported by Amazon. The authors would like to thank Shreya Sarawgi, Mauro Florez, Heather Hodges, and Megan Kinney for all the useful discussions and feedback.
REFERENCES
Bryan Andrews, Peter Spirtes, and Gregory Cooper. On the completeness of causal discovery in the presence of latent confounding with ticred background knowledge. In AISTATS, volume 108 of Proceedings of Machine Learning Research, pp. 4002-4011 PMIR, 2020.
Giorgos Borboudakis and loannis Tsamardinos. Incorporating causal prior knowledge as path- constraints in bayesian networks and maximal ancestral graphs. In ICML. ieml.ec / Omnipress, 2012.
Yizuo Chen and Adnan Darwiche. On the definition and computation of causal treewidth. In UAI, volume 180 of Proceedings of Machine Learning Research, pp. 368-377. PMLR, 2022.
Yizuo Chen and Adnan Darwiche. Identifying causal effects under functional dependencies. En- tropy, 26(12), 2024.
Yizuo Chen and Adnan Darwiche. Constrained identifiability of causal effects. AAAI AICT Work- shop, 2025.
Adnan Darwiche. Causal inference with tractable circuits. In WHY Workshop, NeurlPS, 2021. http::/arriv.or/aas//002229999
Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. Int. Approx. Reason., 55(4):926-92) 2014.
Yang-Bo He and Zhi Geng, Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(84):25232544 2008
10

---

Published as a conference paper at ICLR 2026
David Heckerman, Dan Geiger, and David Maxwell Chickering. Learning bayesian networks: The combination of knowledge and statistical data. Mach. Learn., 20(3):197-244 1995.
Miguel A. Hernán and James M. Robins. Causal Inference: What If. Boca Raton: Chapman & Hall/CRC, 2020.
Yimin Huang and Marco Valtorta. Identifiability in causal bayesian networks: A sound and complete algorithm. AAAI, pp. 1149-1154. AAAI Press, 2006.
Antti Hyttinen, Frederick Eberhardt, and Matti Järvisalo. Do-calculus when the true graph is un- known. UAI, pp. 395-404, AUAI Press, 2015.
Guido W. Imbens and Donald B. Rubin. Causal Inference for Statistics, Social, and Biomedical Sciences: An Introduction. Cambridge University Press, 2015.
Amin Jaber, Adèle H. Ribeiro, Jiji Zhang, and Elias Bareinboim. Causal identification under markov equivalence: Calculus, algorithm, and completeness. In NeurlPS, 2022.
Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Experimental design for learning causal graphs with latent variables. In NIPS, pp. 7018-7028, 2017.
Daniel Malinsky and Peter Spirtes. Estimating bounds on causal effects in high-dimensional and possibly confounded systems. Int. J. Approx. Reason., 88:371-384, 2017.
Christopher Meek. Causal inference and causal explanation with background knowledge. In UAI, pp. 403-410. Morgan Kaufmann, 1995.
Ehsan Mokhtarian, Fateme Jamshidi, Jalal Etesami, and Negar Kiyavash. Causal effect identification with context-specific independence relations of control variables. In AISTATS, volume 151 of Proceedings of Machine Learning Research, pp. 11237-11246. PMLR, 2022.
Juan Miguel Ogarrio, Peter Spirtes, and Joe Ramsey. A hybrid causal search algorithm for latent variable models. Probabilistic Graphical Models, volume 52 of JMLR Workshop and Confer- ence Proceedings, pp. JMM.. JMLR.org, 2016.
Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, second edition, 2009.
Judea Pearl and Dana Mackenzie. The Book of Why: The New Science of Cause and Effect. Basic Books, 2018.
Emilija Perkovic, Johannes Textor, Markus Kalisch, and Marloes H. Maathuis. Complete graphical characterization and construction of adjustment sets in markov equivalence classes of ancestral graphs. J. Mach. Learn. Res.,
2017.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of Causal Inference: Founda- tions and Learning Algorithms. MIT Press, 2017.
Thomas Richardson. Markov properties for acyelic directed mixed graphs. Scandinavian Journal of Statistics, 3051))144-15555 2003. ISSN 03036898, 14679469.
Thomas Richardson and Peter Spirtes. Ancestral graph Markov models. The Annals of Statistics, 30 (4):962 1030, 2002. doi:
URL. https: / /oi. 1214
aos/ 103/1003189015
Richard Scheines and Joseph D. Ramsey. Measurement error and causal discovery. In CFA@ UAI, volume 1792 of CEUR Workshop Proceedings, pp. 1-7. CEUR- CEUR-WS.org. 2016.
Ilya Shpitser and Judea Pearl. Identification of joint interventional distributions in recursive semi- markovian causal models. AAAL, pp. 1219-1226. AAAI Press, 2006.
Ilya Shpitser and Judea Pearl. Complete identification methods for the causal hierarchy. J. Mach. Learn. Res., 1999 2008
11

---

Published as a conference paper at ICLR 2026
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search, Second Edition. Adaptive computation and machine learning. MIT Press, 2000.
Jin Tian. Identifying conditional causal effects. In UAI, pp. 561-568. AUAI Press, 2004.
Jin Tian and Judea Pearl. On the testable implications of causal models with hidden variables. In UAL, pp. 519 527. Morgan Kaufmann, 2002.
Jin Tian and Judea Pearl. On the identification causal effects. Technical Report, R-290-I,, 2003.
Santtu Tikka and Juha Karvanen. Enhancing identification of causal effects by pruning. J. Mach. Learn. Res., 18:194:1-194:23 2012
Santtu Tikka, Antti Hyttinen, and Juha Karvanen. Identifying causal effects via context-specific independence relations. In NeurIPS, pp. 2800-2810, 2019.
Thomas S. Verma. Graphical aspects of causal models. Technical Report, R-191, 1993.
Tian-Zuo Wang, Wen-Bo Du, and Zhi-Hua Zhou An efficient maximal ancestral graph listing algorithm. In ICML, volume 235 of Proceedings of Machine Learning Research, pp. 50353- 50378. PMLR/ / OpenReview.net, 2024.
Jiji Zhang. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artif. Intell., 172(16-17)1873-1886 2008
12

---

Published as a conference paper at ICLR 2026
A METHODS FOR IDENTIFYING (CONDITIONAL) CAUSAL EFFECTS
We review the IDENTIFY algorithm (Tian & Pearl 2003 for unconditional causal effects Prx (Y)
and the IDC algorithm (Shiitser& & Pearl 2008) for conditional causal effects Prx (YIZ). Both algorithms are sound and complete for testing identifiability and return a formula for estimating the (conditional) causal effects if they are identifiable.
The IDENTIFY algorithm first constructs a mutilated graph An(Y) by removing treatments X from the original graph and retaining variables that are ancestors of outcomes Y. It then decom- poses the variables in the mutilated graph into c-components S = (S]..... S J and reduces the particular, Prx PY is identifi- able iff identifiability can be established for each S; E S (Huang & Valtorta|2000)
identifiability of Prx (Y) to the identifiability of c-components.
For each c-component S,, there exists a c-component C in the original graph G such that C S. Let T be the subgraph formed by variables in S; and H be the subgraph formed by variables in C. The c-component S, is deemed identifiable iff T can be obtained from H by repeatedly applying the following operations: (1) replace H with the subgraph formed by the e-component containing S,, or (2) removing from H all variables that are not ancestors of S see (Tian & Pcarl (2003) for the detailed algorithm. This procedure for testing identifiability has been shown to be both sound and complete in (Huang & Valtorta 2006) and (Shpitser & Pearl (2066)
The IDC algorithm (Shpitser & Pearl 2008) tests the identifiability of conditional causal effects Prx(Y [ by reducing the problem to the identifiability of unconditional causal effects. The re- duction involves finding maximal set of variables W such that Prx ( Prxw (YlZ \ W), using rule 2 of do-calculus (Pearl, 2009). Existing methods for identifying causal effects - such as IDENTIFY and ID (Shpitser& & Pearl 2006) can then be applied test the identifiability of Prxw(Y \ W); see (Shpitser& & Pearl 2008 for further details.
B REAL- WORLD SCENARIOS OF TIERED KNOWLEDGE
We present several real-world scenarios where tiered knowledge can occur. The first two were discussed in (Andrews al. 2020), while the third is introduced in this paper.
The first scenario arises when the causal graph models sime-series features with contemporaneous confounding (Andrews et al.) 2020): that is. the hidden confounders only influence variables within the same timestamp but not across different timestamps. For example, consider classroom setting where the lecture quality, the student's learning effort, and the quiz scores are recorded every week and hence can be divided into tiers by their timestamp. While directed edges may exist across weeks (e.g., e. a student's quiz score in one week can affect their learning effort in the next week), hidden confounders such as holidays that simultaneously impact both lecture quality and student's is effort - -only affect variables within a same week since their effects rarely persist across weeks.
In the second scenario. features are divided into context (background) variables and system vari- ables (Andrews et al.] (2020). In particular, the context variables are exogenous to the system vari- ables and hence hidden confounder exists between these two sets of variables. Consider med- ical example in which the context variables describe the month of the year (M), the region (R), and the temperature (I'), whereas the system variables represent whether individuals become sick (S) and whether they recover (Y). The figure below depicts a causal graph over these variables. Directed edges may exist among context variables or from context variables system variables. For example. month and region determine the temperature, and temperature affects the likelihood of people getting sick, as low temperatures facilitate the spread of influenza by increasing indoor crowding and enhancing virus stability cold, dry air. Moreover, hidden confounder may exist between system variables; for example, sickness and recovery may be confounded by unobserved variables (c.g., immunity). However, there is no plausible hidden confounder between context variables and system variables.
The third scenario occurs when variables can be grouped into different tiers within hierarchy, with confounding restricted to occur only within each tier. To illustrate, consider an education system consisting of three tiers corresponding to the district, school, and student levels. The district level contains variables such as total district education funding and demographic features. The school level contains variables such teaching quality and extracurricular activities. The student level
13

---

Published as a conference paper at ICLR 2026
contains variables such as test grades and college admission outcomes. Hidden confounders (e.g., parental involvement and student motivation) may exist among variables within each level but do not span across different levels in general.
C CAUSAL DISCOVERY WITH TIERED KNOWLEDGE
We review the FCIEXOGENOUS procedure introduced in (Andrews al. 2020), which is used in our query-specific causal discovery (Algorithm[]] D
Specifically, the FCIEXOGENOUS procedure recovers the edges in the 7th T-component from obser- vational data. It takes two sets of variables A and B as input, where B contains the variables in tier i and A contains the variables above tier i. The procedure learns the T-component by following the standard FCI algorithm (Spirtes et al. 2000) but with two restrictions. First. edges among variables in A are forbidden. Second, every edge between A E A and B B is oriented as A - B before applying orientation rules Ro- RR10 in (Zhang 2008 see Algorithm for the detailed procedure.
D PROOFS
D.1 PROOF OF PROPOSITION 3.2
We start with the following lemma that shows an identifying formula for Prx (Y) in G.
Lemma D.1. The causal effect Pyx
(Y) is identifiable in G and can be computed as Prx(y)
Ew Pr(w) Pxxw (y \ w) iff Pixw (y \ w) is identifiable in G. where W denotes variables whose fier indexes are smaller than P-X)).
Proof. We first prove that (yx Ewyy Pr(w) Prxw w) in all graphs that satisfy tiered knowledge using do-calculus PPaal 2009).
Pr(y) Σ Prly. w) Σ Pr(w) Pr((y \ w)]w)
wiy
wiy
= Σ Pr(w) Pr((y) w)(w) (do-calculus, Rule and I* (W) (X)) w'y
(I)
Σ Pr(w) Pr(y w) (do-calculus, Rule and I (W) I (Y W))
why
This immediately implies that Prx (Y) is identifiable and can be computed using the formula if Prxw(Y W) is identifiable. We are left to show that Prxw \ W) is identifiable Prx is identifiable. Suppose Prxw(Y W) is unidentifiable, there exists hedge (H. H") for Prxw
W) where H' C H are c-forests in G that share a same set of roots (Shpitser & Pearl 20066 Moreover, H' must only contain variables that are ancestors of (Y W) in the mutilated graph Gxw in which all incoming edges of X and W are removed. This implies that all variables H' have a tier index between I' (X) and (+ W) (no hedge exists if I*+ \ W) rx)X)).
Since H is a c-component containing H', it also contains variables whose tier indexes are between I' (X) and I I++(Y (Y W) since bidirected edge is allowed across tiers. In this case, (11, H") is
also a hedge for Prx (Y), which concludes the unidentifiability of Prx(Y).
Proof of Proposition 3.2 By Lemma D.I Prx (Y) is identifiable in iff Prxw (Y) W) is identi- fiable G. Similarly, Prx (Y) is identifiable in H iff Prxw W) is identifiable in H. Hence, suffices to show (1) Prxw YY) W) is identifiable in G iff is identifiable in H, and (2) the formula returned by IDENTIFY U w.y w) in H is valid for identifying Prxw(y w) in G.
First observe that An(Y W) Gxw and An W Hxw are identical, where An(V)c denotes the ancestors of variables V in graph G. Hence, we obtain the same c-component decomposition
A c-forest is c-component in which all nodes have most one child. The roots of c-component are the nodes that do not have any child.
14

---

Published as a conference paper at ICLR 2026
Algorithm 2 FCIEXOGENOUS (Andrews et al. 2020
Algorithm 2)
Input: Variable sets A, B
Output: PAG
I: Add X; + -X,, to P for all X; A and X, B
Add X; a-o X3 for all distinct X., Xy E B
3: n --0 -0
4: repeat
5:
for all adjacent (X,, X2) E A U B and subset S adj(X;) \ (X,) where |S]
do
6: if X, S then
Delete edge (X,, X;) from P
8:
< S, (epsel(X3,3a) +
end if 10: end for
9:
n -nn n
12: until n > ladj((X) (X.) \ HX;H) for all adjacent X5) EAU EAUB
13: Apply Ro to P
14: for all adjacent (X,, X2) E A UUBUA do
15: / Checking possible d-separating pds */
if there exists S E (X,, where X: 1l Xy then
17:
Delete edge Xx) from P
18:
sepset(Xi. Xz) & S, sepset X:) S 19: end if
20: end for
21: for all adjacent (X,, x,) E B do
22: Replace edge (X;, X;) with X; a- X2 in P
23: end for
24: Apply Ro R4, Rs to
(S....., Sm) for An(Y W)axw and An(Y Y W) Hxw Moreover, G and H have the C- components CC....., Cm where C₁ 2 S1, C2 2 S.,.... and Cm 2 Sm. Therefore, Prxw Y W) is identifiable in G iff it is identifiable in H. Since all variables in the e-components have the same parents in G and H, the formula returned by IDENTIFY applied on H can be used to identify Lemma 4).
Prxw (y w) in G according (Tian & Pearl 2003
D.2 PROOF OF PROPOSITION 3.3
Proof. The proof is based on constructing a causal graph G such that Proposition 3.2 is violated under any such L, L' Let X be treatment variable where r(X) L and Y be an outcome variable where r(Y)= = 24 Suppose L = U, we simply construct G with two edges: X + Y and X + Y. The causal effect (Y) unidentifiable under (L") does not contain X, Y: hence, Prx(Y) is identifiable in these subgraphs, which means that the identifiability variable where T(W) L. We construct G with the following edges: X - W. X ++ W, W - Y, where Prx is unidentifiable. However, the causal effect becomes identifiable either when L L, which removes X, W from G, when 't' < U, which removes Y from G.
U'
this case. However, any subgraph obtained
not preserved. Suppose now < U, let W be non-treatment
D.3 PROOF OF PROPOSITION 3.4
Proof. Consider the following chain graph V1 - 1/2 - ... - V, where V; belongs to 7th tier and the causal effect Prv, a (V)). As L grows, the number of edges in the chain becomes unbounded. However, the size pruned graph remains V + V2, which contains a single edge.
D.4 PROOF OF PROPOSITION 3.5
We start by showing that Prx (Y|Z) is identifiable in G (or H) iff Prx (Y, Z) is identifiable in G (or H). Consider the following equality based on do-calculus, Rule 3:
Pr Y 2 = Prx (Y, Z) X
Prx (Yx(Y,2 Z)
(2)
Prx (Z)
Pr(Z)
15

---

Published as a conference paper at ICLR 2026
Since Pr(Z) is fixed by the observational distribution, Prx Prx((YT (Y Z) is identifiable iff Prx (Y. Z) is identifiable. Since r (Z) < (X), the graph is identical to the subgraph induced by Propo- sition 3.2 for Prx[] ( Y. Z). Hence, Prx (Y, Z) is identifiable in G iff it is identifiable in H, which concludes that Prx (Y (Y|Z) is identifiable in G' iff it identifiable in H. The identifying formula for Prx (Y Z) follows from Eq.
D.5 PROOF OF PROPOSITION D.2
Proposition D.2. Let L,U, ,'' be positive inlegers satisfying & U, C' S U', and at least one L or UI < u holds. Then there exists causal graph and tier mapping T for which of (X) L, (Y) U, and Proposition 3.5 no longer holds if the bounds I' (X) and 1 (Y)
are replaced with L' and
Proof. This follows directly from the proof of Proposition 3.3
D.6 PROOF OF PROPOSITION 3.6
Proof. According to (Shpitser & Pearl 2008), Prx (Y is identifiable in G iff Prxz, (Y, Zz) where Z₁ and Zi partition Z. Moreover, Z₁ is the unique maximal subset
such that Prx (Y Prxz, Z2) by rule 2 of do-calculus. This set Z₁ is the same in G and H since when H only removes edges below U Z.
(Y Z X, Gxx
iff (Y X Ze (2)Hxz Xz
D.7 PROOF OF PROPOSITION
Proof. By construction, the partial PAG p' masTier P if we check each case in Proposi- ier Moreover, the soundness and completeness of learning each partial graph Pl' follows directly from (ndrews et al. 2020 Lemma 12).
tions 3.2 3.6
D.8 PROOF OF PROPOSITION 4.2
Proof. WLG, A = {A1..... An be the variables in the first tier, and B [B....., B, be the variables in the second tier. We add bidirected edges between every pair of variables in A, directed edges from each A; to B,, and directed edges from each B, to Bi+1- Suppose we are interested in the causal effect Prø, (B,). It takes O(n² 2 conditional independence (CI) tests for tiered FCI algorithm to learn all the edges among A. In contrast, Algorithm ignores iigorethmjignoress all edges among and learns the T-component G by conditioning edges and (n²² possible conditioning sets, Algorithm takes at most O ) CI tests.
most 2 variables. Since there are O(n²) possible
16

---

Published as a conference paper at ICLR 2026
Adjacency Precision 0.96
Adjacency Recall
Arrowhead Precision
Arrowhead Recall
T
Z
Time (s)
Full
0.86
0.94
22.13
0.97
0.97
0.88
0.95
I1.89
5
0.97
0.97
0.87
0.95
14.31
0.97
0.97
0.86
0.95
16.53
0.96
0.97
0.86
0.95
17.64
Full
0.95
0.85
0.95
32.37
0.96
0.98
0.88
0.96
19.62
6
0,96
0.97
0.86
0.95
24.57
0.95
0.97
0.86
0.95
26.94
0.96
0.97
0.86
0.95
27.30
Full
0.95
0.85
0.95
46.57
0.95
0.98
0.86
0.95
26.30
7
0.95
0.97
0.87
0.94
31.77
0.95
0.98
0.86
0.95
35.16
0.95
0.97
0.86
0.95
38.33
Full
0.94
0.84
0.94
65.83
0.95
0.97
0.87
0.95
38,80
8
0.95
0.97
0,86
0.95
45. 13
0.94
0.97
0.86
0.95
49.63
0.94
0.97
0.86
0.95
50.09
Full
0.93
0.84
0.94
89.52
0.94
0.97
0.86
0.94
64.60
9
0.93
0.97
0.85
0.94
71.43
0.93
0.97
0.84
0.94
74.32
0.93
0.97
0.84
0.94
75.64
Full
0.94
0.97
0.85
0.94
123.04
0.94
0.97
0.86
0.94
74.69
10
0.94
0.97
0.85
0.94
87.89
0.94
0.97
0.85
0.94
92.42
0.94
0.97
0.85
0.94
99.82
Table 1: Adjacency Precision/Recal, Arrowhead Precision/Recall, and time for FCITIERS (rows with /l=Full) and Algorithm ! (rows with |Z| E: 10, 2,,,2) 3}) under varying numbers of tiers (2).
17


Reviews:
[{"review_id": "ri3K0ETRiz", "reviewer": "Reviewer_z3UD", "summary": "A method is presented that prunes edges from causal graphs under tiered knowledge. Conditions for the removal of edges are specified that don't affect the identifiability of (conditional) causal effects. These are subsequently used to develop a query-specific causal discovery procedure.", "questions": "- How is the data generated in the experiments?\n- How are propositions 3.5 and 3.6 related? Would it be possible to just use Proposition 3.6?\n- How does this work compare to existing work using pruning, such as [1]?\n\n[1] Tikka, Santtu, and Juha Karvanen. \"Enhancing identification of causal effects by pruning.\" Journal of Machine Learning Research 18.194 (2018): 1-23.\n\n### Other comments\n- \"casual\" -> \"causal\" in line 97", "limitations": "", "rating": 2, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "The presented method is potentially computationally more efficient than the FCITiers algorithm it is based on. The presentation is clear.", "weaknesses": "- Bidirected edges across tiers are not allowed, which is a strong limitation. In fact, in the medical context example (lines 121-123) used to justify the assumption of tiers, I don't believe it can be assumed that there are no latent confounders between, say, treatment and recovery. This restriction makes me doubt whether this paper is appropriate for a top conference like ICLR.\n- The paper conflates ADMGs and MAGs. Initially, ADMGs are used for causal graphs, and their intuitive semantics are explained. But the theoretical developments later in the paper use MAGs and PAGs, which have different semantics. I am not sure the presented results are correct if the ground-truth graph is an ADMG that is not a MAG.\n- The pruning method seems to be incremental compared to existing pruning techniques.\n- Proposition 4.2 proves the possibility of exponential speedup, but this only applies to \"a class of distributions\". This makes the statement rather weak. (And indeed, the proof constructs a family of graphs that contains one graph for each $n$.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5QNNJmAHzi", "reviewer": "Reviewer_xo6S", "summary": "This paper studies the identification and computation formula for causal (treament) effect and conditional causal effect under tiered knowledge. It shows the identification and computation can be infered from a simplified (pruned) graph based on the original graph using the tiered knowledge. The pruning procedure is given and a query-specific causal discovery method is proposed based on the pruning procedure.", "questions": "- One of the main message of this work is: to check the idenfication of a given (conditional) causal effect, it suffices to look at a prune graph, then use the existing identification formula. However, it there truely benefit of doing so in terms of computation? Would calling identification formula on the whole graph reduce to calling identification formula on the pruned graph? What is the gain of using the pruned graph when there is an extra step to prune the graph?\n- The experiment only shows the speedup against existing methods on causal discovery. With the main motivation to be causal effect identification check, would there be experiment showing the speedup in this check?\n- Why does the experiment in Figure 5 seem not depend on $|Z|$?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper well-motivated. It introduces the concept of query-specific learning, which reframes causal discovery from global reconstruction to task-focused learning, suitable when full-graph recovery is unnecessary or infeasible.\n- The exposition is generally clear and the examples (especially motivating ones in the introduction) make the idea intuitive.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cHkJIeYcnm", "reviewer": "Reviewer_hPcC", "summary": "The paper focuses on the challenge of answering causal queries in complex systems without having to fully specify or learn an entire causal graph. This comes from the motivation that in some settings the causal model can involve many variables, but a researcher may only be interested in the effect of certain treatments on certain outcomes. The paper focuses on how incorporating background knowledge (tiered knowledge) about the system can improve both identifiability of causal effects and computational efficiency.   They introduce a graph pruning approach to remove certain edges from the causal graph without affecting the identifiability (causal identification on simplified graphs). Based on this, the paper introduces a query-specific causal discovery algorithm that takes as input not just observational data but also a specific causal query of interest to only learn the portion of the causal graph relevant to that query. The paper shows theoretically and empirically that their method can achieve exponential speedups", "questions": "- can you provide some examples of practical applications where we actually have tiered knowledge? \n- It is hard to imagine a practical setting in which we can rule out bidirected edges across tiers. I know that the authors mention that this extension is left for future work, but what kind of steps would be necessary for this extension?\n- it seems that the advantages of the algorithm decrease be increasing the size of the conditioning set $Z$. What happens when this is substantially larger? It would also be nice to see the improvement in terms of num tiers as percentage of the entire set of nodes, and then analyse how this changes with different sizes of underlying causal graph", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I think the paper is clear and well written. Sometimes a bit too heavy in notation, but this is perhaps necessary for introducing the theoretical results. I would encourage having more intuitive introductions to some of the notations (for instance c-components/tiered knowledge). I enjoyed the graph examples in the paper, they made the understanding easier. \n- the research question is relevant in the field, further improvements in this direction can potentially help causal effect estimation be more applicable in practical scenarios. It is also important to start from this kind of theoretically-grounded contribution to understand to what extent identifiability can hold with different kinds of domain knowledge.\n- the theoretical results show that the proposed algorithm is sound and complete\n- the experimental result show promising results in terms of efficiency without sacrificing correctness of the learned structures", "weaknesses": "- I think the paper could be strengthened by adding some examples of real world applications in introduction where tier knowledge is available to practitioners\n- The authors should explicitly mention as well that this paper relies on acyclicity of the causal structure\n- in Line 078, the notation $Pr_{B_1}(B_3,C_3)$ is introduced, however the subscript notation had not previously been introduced. The authors should fix this. \n- related to the previous sentence, also when mentioning 'they are identifiable in the pruned graph G' I would add a reference to Fig 1b, to make it easier for the reader to understand the example.\n- Minor: format of the title seems different from the ICLR layout", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)