PAIR-CI: Calibrated Conditional Independence Testing for Causal Discovery with Incomplete Data

arXiv:2605.04838 · stat.ME, cs.LG, stat.ML · Submitted 2026-05-06 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "PAIR-CI: Calibrated Conditional Independence Testing for Causal Discovery with Incomplete Data".

Jane: Here's the gist of the paper. The standard constraint-based paradigm for causal discovery with incomplete data—impute first, test second—is frequently miscalibrated: any consistent conditional independence (CI) test rejects a true null with probability approaching 1 when imputation error induces spurious conditional dependence PAIR-CI, a nonparametric CI test that restores calibration by integrating multiple imputation directly into the inferential procedure via a paired permutation design Core Problem and Proposed Solution Conditional independence (CI) testing is the inferential engine of constraint-based methods for causal discovery across the sciences This creates a fundamental problem when data are incomplete: missing values in the conditioning set X prevent direct evaluation of relationships between test variables Imputing missing values before testing is valid under Preprint However, imputing can lead to miscalibration under MNAR and other forms of misspecified imputation, where residual bias in the completed data may introduce spurious associations between test variables that are mistaken for genuine conditional dependence To avoid this miscalibration, PAIR-CI proposes a nonparametric CI test that integrates multiple imputation directly into the inferential procedure via a paired permutation design PAIR-CI compares cross-validated models of Z that differ in access to the candidate variable but receive the same imputed conditioning set, ensuring that any distortion introduced by imputation affects both models identically and thus cancels in their loss difference rather than entering the test statistic Theoretical Guarantees and Calibration PAIR-CI achieves exact asymptotic size for the internal null Z ⊥⊥ Y Xˆ under four relatively undemanding assumptions (Proposition 2) The paired design cancels imputation bias by feeding both models the same imputed conditioning set, while caching further reduces residual bias κ by absorbing the test variables’ correlation with Xmiss into Xˆ Under Assumptions (A1)–(A4), and applying Theorem 4 to the combined variance estimator, PAIR-CI has exact asymptotic size: P(tCI > tα,ν) → α The unified inference under cross-validation and multiple imputation is achieved by nesting the provably consistent within-imputation estimator developed by Bayle et al.

2020: inside Rubin’s rules This combined estimator delivers asymptotically valid inference with correct size and power—to our knowledge, the first formal result connecting cross-validation and multiple imputation Empirical Performance Across Mechanisms In simulations spanning multiple data-generating processes (DGPs), sample sizes, and missingness mechanisms, existing imputation-based CI tests exhibit false positive rates of 28–45% under MNAR whereas PAIR-CI averages below the nominal level The resulting gains in graph recovery grow with scale, rising from an 8% reduction in structural Hamming distance (SHD) on 10-variable graphs to 15% on 30-variable equivalents and up to 44% on the 56-variable HAILFINDER network Standalone performance shows that PAIR-CI maintains an average false positive rate ≤ 4% across all missingness conditions Only one DGP × mechanism cell slightly exceeds the nominal level at 7%—still an order of magnitude below the 41–59% inflation observed for FZ-single, FZ-Rubin, GCM, and KCI Graph Recovery and Robustness In synthetic graph recovery experiments, PAIR-CI yields SHD 11 with nonlinear edges under all mechanisms At p = 56 in the HAILFINDER weather forecasting network, PAIR-CI delivers SHD 62.5–65.5 across all three missingness mechanisms The performance of PAIR-CI is stable across MAR, MNAR, and mixed mechanisms for all graph sizes The distinctive feature of PAIR-CI at this scale is perfect precision: conservatism manifests as missing edges rather than spurious ones PAIR-CI addresses a key gap in constraint-based causal discovery, achieving false positive rates near nominal levels across missingness mechanisms, edge types, and graph sizes The primary cost is reduced power relative to well-specified parametric tests when their assumptions hold—that is, when relationships are approximately linear and missingness is either MCAR or MAR Where parametric assumptions are violated or the missingness mechanism is unverifiable, PAIR-CI’s calibration advantage outweighs its loss in power, opening a performance gap that widens with scale The paper concludes that PAIR-CI requires—among other, less demanding conditions—that the imputation model converge to the true conditional distribution of missing values The paired design’s κ-cancellation is robust in these settings because cached imputation includes Y and Z in the imputer, allowing the linear MICE model to absorb information about Xmiss into Xˆ Practitioners working with strongly nonlinear DGPs and adversarial missingness should verify calibration empirically prior to deployment References Bruce Abramson, John Brown, Ward Edwards, Allan Murphy, and Robert L Winkler.

Jane: HAILFINDER: A Bayesian System for Forecasting Severe Weather.

Tom: International Journal of Forecasting, 12(1):57–71, 1996 John Barnard and Donald B Rubin.

Title and authors: Tom: Moving on to the authors and title, we have Thomas S. Robinson from London School of Economics and Political Science and Ranjit Lall from Oxford University. Their work, "PAIR-CI: Calibrated Conditional Independence Testing for Causal Discovery with Incomplete Data," is a big name in this area >

Jane: It sounds very technical, but the main idea is that they are building a nonparametric test for conditional independence that handles missing data without getting biased by it >

Lu: The paper focuses on how to make these tests robust when we can't just assume simple missingness like MCAR or MAR, because those assumptions often lead to miscalibration in standard methods >

Meng: So they are trying to build a tool that works even when the missing data mechanism is more complex, like MNAR, where the data is not just randomly missing >

Tom: That’s right. They want to avoid those spurious edges in your causal graph that come from imputation error propagating through the structure >

Jane: It suggests a new way of looking at conditional independence testing where the multiple imputation isn't just a preprocessing step, but part of the inferential procedure itself >

Lu: It’s about comparing models under different access to variables while keeping the imputed set consistent, which is a clever way to control for that bias >

Tom: So, instead of just fixing the data first and hoping it works, they are building a test that's inherently designed to be stable against imputation errors >

Jane: It’s about making sure the test statistic doesn't get skewed by the missing values we had to guess >

The paper's summary: Jane: Now let’s look at what the paper actually summarizes. They are proposing PAIR-CI, which is this nonparametric conditional independence test that uses a paired permutation design to integrate multiple imputation directly into the testing >

Tom: Basically, they compare cross-validated models of Z that differ only by whether they can see the candidate variable but both receive the same imputed conditioning set >

Lu: They evaluate the difference in out-of-sample loss between these two models, and then average that across different folds and imputations using Rubin’s rules to get a combined test statistic >

Meng: That sounds like a lot of computation. What's the practical cost of running this whole procedure compared to just running a standard PC algorithm on complete data?

Tom: The paper claims they achieve exact asymptotic size for the internal null, which means if your hypothesis is true, the test has that exact probability of rejecting it as you increase your sample size >

Jane: And they claim this unified inference—combining cross-validation and multiple imputation—delivers asymptotically valid inference with correct size and power, which is a first for connecting those two things formally >

Lu: It’s about showing that you can get asymptotically exact results even when dealing with the uncertainty from both the imputation process and the cross-validation error simultaneously >

Meng: So, if this works as claimed, does it mean we can deploy this on massive datasets where running standard CI tests is too slow?

Tom: The paper suggests it’s particularly useful because when missingness is not well-specified, like MNAR, existing imputation-based tests have been showing false positive rates up to forty-five percent > <ref:2605.04838#pg3>

The paper's improvements: Jane: The authors highlight several key improvements. First, they show that their method achieves a false positive rate near nominal levels across all missingness mechanisms and edge types, which is a huge win for reliability >

Lu: They see gains in graph recovery that grow with scale; it starts at an eight percent reduction in structural Hamming distance on ten-variable graphs and goes up to forty-four percent on the HAILFINDER weather network with fifty-six variables >

Meng: Forty-four percent? That’s significant. But what about when the imputation quality is poor, like if we use mean or marginal imputation instead of a full MICE process?

Tom: When imputation quality degrades, they report that the false positive rate inflates substantially, reaching twenty-nine point zero percent under MAR and forty-three point three percent under MNAR >

Jane: That part is important. The authors are clear that when you use simpler imputation methods, the false positive rate shoots up because those methods don't cancel out the imputation bias properly >

Lu: So, in a practical sense, it means you have to be careful about which imputation method you choose; it’s load-bearing for calibration >

Meng: So the paper isn't just proposing a black box solution; it’s telling us we need to verify the quality of our imputation models before we trust the final result >

Tom: Right. They are saying that if your imputation model converges to the true distribution of missing values, then this paired design’s bias cancellation is robust >

Conclusion: Jane: So, to wrap up, PAIR-CI addresses the fundamental problem of miscalibration in constraint-based causal discovery by integrating multiple imputation directly into the test via a paired permutation design >

Lu: It gives us a unified framework where we can get asymptotically exact inference with correct size and power when combining cross-validation and multiple imputation >

Tom: The big implication here is that for researchers dealing with strongly nonlinear data or adversarial missingness, PAIR-CI’s calibration advantage outweighs any loss in power compared to simpler parametric tests if those assumptions are violated >

Meng: If you're running something at scale, the gain in structural Hamming distance reduction can be up to forty-four percent on networks like HAILFINDER, which suggests this could be a useful tool for large-scale graph recovery >

Lalam: I’m confident that the paper confirms what we see in simulations—that standalone performance stays below four percent false positive rate across all missingness conditions >

Tom: So, in short, PAIR-CI is a nonparametric CI test that achieves near nominal false positive rates even when imputation error introduces spurious conditional dependence >

Jane: It requires the authors to verify that their imputation model converges to the true conditional distribution of missing values for their strongest claims to hold >

Thomas S. Robinson, Ranjit Lall

London School of Economics and Political Science · University of Oxford

stat.ME, cs.LG, stat.ML

Submitted: 2026-05-06

Updated: 2026-11-16

Comments: Camera-ready version, accepted at NeurIPS 2026. 64 pages. Code and replication materials: https://github.com/tsrobinson/pair-ci (doi:10.5281/zenodo.23976940)

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 95/100

The gist: The standard constraint-based paradigm for causal discovery with incomplete data—impute first, test second—is frequently miscalibrated…

Key concepts

Conditional Independence (CI) Testing
This is the statistical engine used in constraint-based causal discovery methods to determine if two variables are related given a set of conditioning variables. When data is incomplete, standard CI tests become unreliable because missing values prevent direct evaluation of these relationships.
Multiple Imputation
This technique involves creating several complete datasets by filling in missing values based on statistical models. The challenge is that imputing first and then testing can introduce errors that falsely suggest a relationship between variables, miscalibrating the test results.
Paired Permutation Design
PAIR-CI uses this design to fix the calibration problem. It compares two models of the missing variable Z under cross-validation, ensuring both models receive the exact same imputed conditioning set. This forces imputation bias to cancel out in their loss difference, leading to a more accurate test statistic.

Terminology

Summary

The standard constraint-based paradigm for causal discovery with incomplete data—impute first, test second—is frequently miscalibrated: any consistent conditional independence (CI) test rejects a true null with probability approaching 1 when imputation error induces spurious conditional dependence

PAIR-CI, a nonparametric CI test that restores calibration by integrating multiple imputation directly into the inferential procedure via a paired permutation design

Core Problem and Proposed Solution

Conditional independence (CI) testing is the inferential engine of constraint-based methods for causal discovery across the sciences This creates a fundamental problem when data are incomplete: missing values in the conditioning set X prevent direct evaluation of relationships between test variables Imputing missing values before testing is valid under Preprint However, imputing can lead to miscalibration under MNAR and other forms of misspecified imputation, where residual bias in the completed data may introduce spurious associations between test variables that are mistaken for genuine conditional dependence

To avoid this miscalibration, PAIR-CI proposes a nonparametric CI test that integrates multiple imputation directly into the inferential procedure via a paired permutation design PAIR-CI compares cross-validated models of Z that differ in access to the candidate variable but receive the same imputed conditioning set, ensuring that any distortion introduced by imputation affects both models identically and thus cancels in their loss difference rather than entering the test statistic

Theoretical Guarantees and Calibration

PAIR-CI achieves exact asymptotic size for the internal null Z ⊥⊥ Y Xˆ under four relatively undemanding assumptions (Proposition 2) The paired design cancels imputation bias by feeding both models the same imputed conditioning set, while caching further reduces residual bias κ by absorbing the test variables’ correlation with Xmiss into Xˆ Under Assumptions (A1)–(A4), and applying Theorem 4 to the combined variance estimator, PAIR-CI has exact asymptotic size: P(tCI > tα,ν) → α

The unified inference under cross-validation and multiple imputation is achieved by nesting the provably consistent within-imputation estimator developed by Bayle et al. [2020] inside Rubin’s rules This combined estimator delivers asymptotically valid inference with correct size and power—to our knowledge, the first formal result connecting cross-validation and multiple imputation

Empirical Performance Across Mechanisms

In simulations spanning multiple data-generating processes (DGPs), sample sizes, and missingness mechanisms, existing imputation-based CI tests exhibit false positive rates of 28–45% under MNAR whereas PAIR-CI averages below the nominal level The resulting gains in graph recovery grow with scale, rising from an 8% reduction in structural Hamming distance (SHD) on 10-variable graphs to 15% on 30-variable equivalents and up to 44% on the 56-variable HAILFINDER network

Standalone performance shows that PAIR-CI maintains an average false positive rate ≤ 4% across all missingness conditions Only one DGP × mechanism cell slightly exceeds the nominal level at 7%—still an order of magnitude below the 41–59% inflation observed for FZ-single, FZ-Rubin, GCM, and KCI

Graph Recovery and Robustness

In synthetic graph recovery experiments, PAIR-CI yields SHD 11 with nonlinear edges under all mechanisms At p = 56 in the HAILFINDER weather forecasting network, PAIR-CI delivers SHD 62.5–65.5 across all three missingness mechanisms

The performance of PAIR-CI is stable across MAR, MNAR, and mixed mechanisms for all graph sizes The distinctive feature of PAIR-CI at this scale is perfect precision: conservatism manifests as missing edges rather than spurious ones

Conclusion

PAIR-CI addresses a key gap in constraint-based causal discovery, achieving false positive rates near nominal levels across missingness mechanisms, edge types, and graph sizes The primary cost is reduced power relative to well-specified parametric tests when their assumptions hold—that is, when relationships are approximately linear and missingness is either MCAR or MAR Where parametric assumptions are violated or the missingness mechanism is unverifiable, PAIR-CI’s calibration advantage outweighs its loss in power, opening a performance gap that widens with scale

The paper concludes that PAIR-CI requires—among other, less demanding conditions—that the imputation model converge to the true conditional distribution of missing values The paired design’s κ-cancellation is robust in these settings because cached imputation includes Y and Z in the imputer, allowing the linear MICE model to absorb information about Xmiss into Xˆ Practitioners working with strongly nonlinear DGPs and adversarial missingness should verify calibration empirically prior to deployment

References

Bruce Abramson, John Brown, Ward Edwards, Allan Murphy, and Robert L Winkler. HAILFINDER: A Bayesian System for Forecasting Severe Weather. p. 9

Where the paper says it

References Bruce Abramson, John Brown, Ward Edwards, Allan Murphy, and Robert L Winkler. HAILFINDER: A Bayesian System for Forecasting Severe Weather.

International Journal of Forecasting, 12(1):57–71, 1996

John Barnard and Donald B Rubin. Small-sample degrees of freedom with multiple imputation. p. 9

Where the paper says it

John Barnard and Donald B Rubin. Small-sample degrees of freedom with multiple imputation.

Biometrika, 86(4):948–955, 1999

Pierre Bayle, Alexandre Bayle, Lucas Janson, and Lester Mackey. Cross-validation confidence intervals for test error. p. 9

Where the paper says it

Pierre Bayle, Alexandre Bayle, Lucas Janson, and Lester Mackey. Cross-validation confidence intervals for test error.

Advances in Neural Information Processing Systems, 33:16339–16350, 2020

Ingo A Beinlich, Henri Jacques Suermondt, R Martin Chavez, and Gregory F Cooper. The ALARM Monitoring System: A Case Study with Two Probabilistic Inference Techniques for Belief Networks. p. 9

Where the paper says it

Ingo A Beinlich, Henri Jacques Suermondt, R Martin Chavez, and Gregory F Cooper. The ALARM Monitoring System: A Case Study with Two Probabilistic Inference Techniques for Belief Networks.

In Proceedings of the Second European Conference on Artificial Intelligence in Medicine (AIME), pages 247–256. p. 9
Where the paper says it

The ALARM Monitoring System: A Case Study with Two Probabilistic Inference Techniques for Belief Networks. In Proceedings of the Second European Conference on Artificial Intelligence in Medicine (AIME), pages 247–256.

Springer, 1989

Alexis Bellot and Mihaela van der Schaar. Conditional independence testing using generative adversarial networks. p. 9

Where the paper says it

Alexis Bellot and Mihaela van der Schaar. Conditional independence testing using generative adversarial networks.

Advances in Neural Information Processing Systems, 32, 2019

Thomas B Berrett, Yi Wang, Rina Foygel Barber, and Richard J Samworth. The conditional permutation test for independence while controlling for confounders. p. 9

Where the paper says it

Thomas B Berrett, Yi Wang, Rina Foygel Barber, and Richard J Samworth. The conditional permutation test for independence while controlling for confounders.

Journal of the Royal Statistical Society Series B: Statistical Methodology, 82(1):175–197, 2020

Alexander Gain and Ilya Shpitser. Structure learning under missing data. p. 0

Where the paper says it

Widely used algorithms such as PC (Peter–Clark), FCI (Fast Causal Inference), and their variants reduce the problem of learning causal structure to a sequence of CI tests over variable pairs with progressively expanding conditioning sets [Spirtes et al. This creates a fundamental problem when data are incomplete: missing values in the conditioning set X prevent direct evaluation of relationships between test variables.

In International Conference on Probabilistic Graphical Models (PGM), pages 121–132, 2018

Erdun Gao, Ignavier Ng, Mingming Gong, Li Shen, Wei Huang, Tongliang Liu, Kun Zhang, and Howard Bondell. MissDAG: Causal discovery in the presence of missing data with continuous additive noise models. p. 9

Where the paper says it

Erdun Gao, Ignavier Ng, Mingming Gong, Li Shen, Wei Huang, Tongliang Liu, Kun Zhang, and Howard Bondell. MissDAG: Causal discovery in the presence of missing data with continuous additive noise models.

Advances in Neural Information Processing Systems, 35:5024–5038

Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. p. 9

Where the paper says it

Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees.

Machine learning, 63(1):3–42, 2006

John W Graham. Missing data analysis: Making it work in the real world. p. 9

Where the paper says it

John W Graham. Missing data analysis: Making it work in the real world.

Annual review of psychology, 60(1):549–576, 2009

Markus Kalisch and Peter Bühlmann. Estimating high-dimensional directed acyclic graphs with the PC-algorithm. p. 9

Where the paper says it

Markus Kalisch and Peter Bühlmann. Estimating high-dimensional directed acyclic graphs with the PC-algorithm.

Journal of Machine Learning Research, 8(3):613–636, 2007

Christopher Meek. Causal inference and causal explanation with background knowledge. p. 9

Where the paper says it

Christopher Meek. Causal inference and causal explanation with background knowledge.

In UAI, pages 403–410, 1995

Karthika Mohan and Judea Pearl. Graphical models for processing missing data. p. 9

Where the paper says it

Karthika Mohan and Judea Pearl. Graphical models for processing missing data.

Journal of the American Statistical Association, 116(534):1023–1037, 2021

Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. p. 0

Where the paper says it

lall@politics. uk Abstract The standard constraint-based paradigm for causal discovery with incomplete data— impute first, test second—is frequently miscalibrated: any consistent conditional independence (CI) test rejects a true null with probability approaching 1 when imputation error induces spurious conditional dependence.

p. 0
Where the paper says it

lall@politics. uk Abstract The standard constraint-based paradigm for causal discovery with incomplete data— impute first, test second—is frequently miscalibrated: any consistent conditional independence (CI) test rejects a true null with probability approaching 1 when imputation error induces spurious conditional dependence.

In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, UAI’11, page 804–813, Arlington, Virginia, USA, 2011

Alexandre B Tsybakov. Introduction to Nonparametric Estimation. p. 3

Where the paper says it

2The neighborhood size is knn = max(2, ⌊n 2/(d+2)⌋), where d = |X|. This is the minimax-optimal bandwidth for nonparametric density estimation in dimension d [Tsybakov, 2009], ensuring that U | Xˆ converges to Y | Xˆ at the rate required by the exchangeability argument in Proposition 2.

p. 3
Where the paper says it

2The neighborhood size is knn = max(2, ⌊n 2/(d+2)⌋), where d = |X|. This is the minimax-optimal bandwidth for nonparametric density estimation in dimension d [Tsybakov, 2009], ensuring that U | Xˆ converges to Y | Xˆ at the rate required by the exchangeability argument in Proposition 2.

Springer Series in Statistics. p. 9
Where the paper says it

In Proceedings of the Second European Conference on Artificial Intelligence in Medicine (AIME), pages 247–256. Springer, 1989.

p. 9
Where the paper says it

In Proceedings of the Second European Conference on Artificial Intelligence in Medicine (AIME), pages 247–256. Springer, 1989.

Springer, New York, NY, 2009

Ruibo Tu, Cheng Zhang, Paul Ackermann, Karthika Mohan, Hedvig Kjellström, and Kun Zhang. Causal discovery in the presence of missing data. p. 9

Where the paper says it

Erdun Gao, Ignavier Ng, Mingming Gong, Li Shen, Wei Huang, Tongliang Liu, Kun Zhang, and Howard Bondell. MissDAG: Causal discovery in the presence of missing data with continuous additive noise models.

In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1762–1770. p. 9
Where the paper says it

The ALARM Monitoring System: A Case Study with Two Probabilistic Inference Techniques for Belief Networks. In Proceedings of the Second European Conference on Artificial Intelligence in Medicine (AIME), pages 247–256.

Pmlr, 2019

Stef Van Buuren and Karin Groothuis-Oudshoorn. mice: Multivariate imputation by chained equations in R. p. 2

Where the paper says it

2 relaxes this restriction for computational tractability, with the added benefit of improved calibration. Our default imputation method is MICE (Multiple Imputation by Chained Equations) with Bayesian ridge regression [Van Buuren and Groothuis-Oudshoorn, 2011].

Journal of statistical software, 45:1–67, 2011

David S Watson and Marvin N Wright. Testing conditional independence in supervised learning algorithms. p. 0

Where the paper says it

1 Introduction Conditional independence (CI) testing—determining whether Z ⊥⊥ Y | X—is the inferential engine of constraint-based methods for causal discovery across the sciences. Widely used algorithms such as PC (Peter–Clark), FCI (Fast Causal Inference), and their variants reduce the problem of learning causal structure to a sequence of CI tests over variable pairs with progressively expanding conditioning sets [Spirtes et al.

Machine Learning, 110(8):2107–2129, 2021

Janine Witte, Ronja Foraita, and Vanessa Didelez. Multiple imputation and test-wise deletion for causal discovery with incomplete cohort data. p. 2

Where the paper says it

Incomplete data in causal discovery. Test-wise deletion [Tu et al.

Statistics in medicine, 41(23):4716–4743, 2022

Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, UAI’11, page 804–813, Arlington, Virginia, USA, 2011

Donald B Rubin. Multiple Imputation for Nonresponse in Surveys. p. 0

Where the paper says it

uk Abstract The standard constraint-based paradigm for causal discovery with incomplete data— impute first, test second—is frequently miscalibrated: any consistent conditional independence (CI) test rejects a true null with probability approaching 1 when imputation error induces spurious conditional dependence. We introduce PAIR-CI, a nonparametric CI test that restores calibration by integrating multiple imputation directly into the inferential procedure via a paired permutation design.

Wiley, 1987

Erwan Scornet, Gérard Biau, and Jean-Philippe Vert. Consistency of random forests. p. 3

Where the paper says it

In Step 2, any supervised learner satisfying modest stability conditions (Theorem 4) can be used to train the full and partial models. In subsequent validation experiments, we implement two variants of PAIR-CI: a general variant based on random forests, which meet these conditions and exhibit universal consistency [Scornet et al.

The Annals of Statistics, 43(4):1716 – 1741, 2015 doi: 10. p. 3
Where the paper says it

In subsequent validation experiments, we implement two variants of PAIR-CI: a general variant based on random forests, which meet these conditions and exhibit universal consistency [Scornet et al. , 2015]; and a fast variant based on ExtraTrees [Geurts et al.

1214/15-AOS1321 URL https://doi.org/https://doi.org/https://doi.org/ https://doi.org/https://doi.org/

Rajat Sen, Ananda Theertha Suresh, Karthikeyan Shanmugam, Alexandros G Dimakis, and Sanjay Shakkottai. Model-powered conditional independence test. p. 0

Where the paper says it

lall@politics. uk Abstract The standard constraint-based paradigm for causal discovery with incomplete data— impute first, test second—is frequently miscalibrated: any consistent conditional independence (CI) test rejects a true null with probability approaching 1 when imputation error induces spurious conditional dependence.

Advances in Neural Information Processing Systems, 30, 2017

Rajen D Shah and Jonas Peters. The hardness of conditional independence testing and the generalised covariance measure. p. 2

Where the paper says it

, 2011] and the Randomized Conditional Independence Test [RCIT; Strobl et al. , 2019] assess CI by embedding variables into high-dimensional feature spaces, while the Generalized Covariance Measure [GCM; Shah and Peters, 2020] measures dependence between regression errors.

The Annals of Statistics, 48(3):1514 – 1538 doi: 10. p. 6
Where the paper says it

447 post-nonlinear (13. 7%) DGPs, where a Bayesian ridge imputer is misspecified, FZ-Rubin’s MAR false positive rate increases monotonically with n, confirming that pooling test statistics does not restore calibration when bias enters through the imputed conditioning set (Proposition 1).

1214/19-AOS1857 URL https://doi.org/https://doi.org/

Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search. p. 4

Where the paper says it

[2020, Theorem 3], which holds for random forests with bounded loss [Scornet et al. , 2015]; (A5) universal consistency: the learner converges to the Bayes-optimal prediction function for any distribution as n → ∞; and (A6) faithfulness: every CI relation in the observed distribution corresponds to a d-separation in the true DAG.

MIT Press, 2nd edition, 2000

Eric V Strobl, Kun Zhang, and Shyam Visweswaran. Approximate kernel-based conditional independence tests for fast non-parametric causal discovery. p. 0

Where the paper says it

1 Introduction Conditional independence (CI) testing—determining whether Z ⊥⊥ Y | X—is the inferential engine of constraint-based methods for causal discovery across the sciences. Widely used algorithms such as PC (Peter–Clark), FCI (Fast Causal Inference), and their variants reduce the problem of learning causal structure to a sequence of CI tests over variable pairs with progressively expanding conditioning sets [Spirtes et al.

Journal of Causal Inference, 7(1):20180017, 2019

Alexandre B Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York, NY, 2009 doi: 10. p. 9

Where the paper says it

In Proceedings of the Second European Conference on Artificial Intelligence in Medicine (AIME), pages 247–256. Springer, 1989.

1007/b13794 URL https://doi.org/

Pruning redundant reasoning tokens

The standard constraint-based paradigm for causal discovery with incomplete data—impute first, test second—is frequently miscalibrated: any consistent conditional independence (CI) test rejects a true null with probability approaching 1 when imputation error induces spurious conditional dependence

PAIR-CI restores calibration by integrating multiple imputation directly into the inferential procedure via a paired permutation design

How the training signal is built

The PAIR-CI testing procedure involves four steps: 1) Multiple imputation, 2) Cross-validated model comparison, 3) Loss comparison, and 4) Combined test statistic Step 2 involves comparing two models of Z on the remaining K − 1 folds: a full model gˆZYkm and a partial model gˆZUkm Step 3 evaluates the difference in out-of-sample loss: µˆkm = lgˆZUkm - lgˆZYkm (1)

The combined test statistic T is estimated by averaging across folds and imputations, combining within-imputation cross-validation variance W¯ with between-imputation variation B using Rubin’s rules The resulting combined estimator delivers asymptotically exact inference with correct size and power—to our knowledge, the first formal result connecting cross-validation and multiple imputation

Where the gains come from

The gains in graph recovery grow with scale, rising from an 8% reduction in structural Hamming distance (SHD) on 10-variable graphs to 15% on 30-variable equivalents and up to 44% on the 56-variable HAILFINDER network PAIR-CI overtakes test-wise deletion by p = 30 (SHD 53 vs. 58) as conditioning sets grow larger and partial correlations degrade in higher dimensions

The paired comparison cancels imputation bias by feeding both models the same Xˆ, causing imputation-induced bias to enter both losses identically and cancel in the difference This cancellation occurs when error varies randomly across observations—as with MICE under MNAR—but fails when it is systematic, as with mean or marginal imputation The residual κ is thus controlled by the differential dependence of Y and Z on δ

Imputation Degradation

When imputation quality is degraded—such as using mean or marginal imputation—the false positive rate inflates substantially, reaching 29.0% under MAR and 43. p. 1

Where the paper says it

MCAR or missing at random (MAR) but can lead to miscalibration under MNAR and other forms of misspecified imputation: residual bias in the completed data may introduce spurious associations between test variables that are mistaken for genuine conditional dependence. 1 We formalize this bias in Proposition 1: miscalibration is not a small-sample artifact but an asymptotic inevitability whenever imputation error induces residual conditional dependence between test variables.

3% under MNAR This inflation arises because the conditioning set Xˆ induces spurious associations between Z and Y —exactly the failure mode identified in Proposition 1 Imputation quality is therefore load-bearing for calibration—not merely for power

PAIR-CI reliably detects moderate-to-strong conditional dependencies (signal ≥ 0.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Integrated Causal Discovery Oracle for Constraint-Based Methods The improved system can serve as a drop-in oracle for algorithms like FCI by incorporating PAIR-CI to recover true Directed Acyclic Graphs (DAGs) under incomplete conditioning sets with calibration guarantees.

  2. Unified Variance Estimation Framework The system can provide a provably consistent variance estimator that jointly accounts for uncertainty arising from crossvalidation and multiple imputation, yielding asymptotically valid inference even when combining these two inferential frameworks.

  3. Robust Causal Discovery Across Missingness Mechanisms The system can achieve false positive rates near nominal levels across all missingness mechanisms (MAR, MNAR, mixed) and edge types (linear/nonlinear), significantly outperforming existing imputation-based CI tests which exhibit false positive rates of 28–45% under MNAR.

  4. Enhanced Structural Hamming Distance Reduction The system can reduce structural Hamming distance by up to 44% on complex networks like the 56-variable HAILFINDER network when integrated into the PC algorithm, with gains growing with causal graph size and nonlinearity.

  5. Improved Inference Under Misspecification The system restores calibration by ensuring that any consistent conditional independence (CI) test rejects a true null with probability approaching 1 when imputation error induces spurious conditional dependence is avoided by forcing imputation error to cancel in their loss difference rather than contaminate the test statistic.

  6. Principled Inference with Correct Size and Power Estimation The system enables principled inference by combining cross-validation and multiple imputation via a variance estimator that delivers asymptotically exact inference with correct size and power, improving power by 9–10 percentage points at intermediate effect sizes.

Abstract

The standard constraint-based paradigm for causal discovery with incomplete data -- impute first, test second -- is frequently miscalibrated: any consistent conditional independence (CI) test rejects a true null with probability approaching 1 when imputation error induces spurious conditional dependence. We introduce PAIR-CI, a nonparametric CI test that restores calibration by integrating multiple imputation directly into the inferential procedure via a paired permutation design. PAIR-CI compares cross-validated models that include and exclude the candidate variable while receiving the same imputed conditioning set, so that imputation error cancels in their loss difference rather than contaminating the test statistic. A variance estimator that nests a provably consistent cross-validation estimator inside Rubin's rules yields inference that is asymptotically valid in the many-imputation limit and conservative by a derived, sign-definite mechanism -- to our knowledge, the first formal result combining these two inferential frameworks. In simulations, existing imputation-based CI tests exhibit false positive rates of 28-45% when data are missing not at random (MNAR), whereas PAIR-CI's pooled rate is at most 3.6%, exceeding the nominal 5% only in some cells with five or more conditioning variables. Integrated into the PC algorithm, PAIR-CI is stable across functional forms and missingness mechanisms, whereas every parametric pipeline we consider, including missing-value PC, has a regime in which it fails badly. On nonlinear network benchmarks it reduces structural Hamming distance by 18% (ALARM) and 11% (HAILFINDER) relative to missing-value PC and by 31-48% relative to test-wise deletion and imputation-based Fisher- Z pipelines, while attaining the highest skeleton F1; when relationships are linear, a well-specified parametric pipeline remains preferable.

Related papers