# On the Number of Conditional Independence Tests in Constraint-based Causal Discovery

arXiv: https://arxiv.org/abs/2603.21844 · HTML: https://mlsanity.com/paper/2603.21844/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 23 Mar 2026.

## Builds on (most cited first, 15 of 15)

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Causal-learn: Causal Discovery in Python](https://mlsanity.com/paper/2307.16405/) (2023)
- [A survey of Bayesian Network structure learning](https://mlsanity.com/paper/2109.11415/) (2021)
- [Greedy Relaxations of the Sparsest Permutation Algorithm](https://mlsanity.com/paper/2206.05421/) (2022)
- [Learning Sparse Causal Models is not NP-hard](https://mlsanity.com/paper/1309.6824/) (2013)
- [High-dimensional consistency in score-based and hybrid structure learning](https://mlsanity.com/paper/1507.02608/) (2015)
- [Parameter Priors for Directed Acyclic Graphical Models and the Characterization of Several Probability Distributions](https://mlsanity.com/paper/1301.6697/) (2013)
- [A Discovery Algorithm for Directed Cyclic Graphs](https://mlsanity.com/paper/1302.3599/) (2013)
- [Ancestral Causal Inference](https://mlsanity.com/paper/1606.07035/) (2016)
- [Causal Discovery with Fewer Conditional Independence Tests](https://mlsanity.com/paper/2406.01823/) (2024)
- [Recursive Causal Discovery](https://mlsanity.com/paper/2403.09300/) (2024)
- [Characterization and Learning of Causal Graphs with Small Conditioning Sets](https://mlsanity.com/paper/2301.09028/) (2023)
- [The Reduced PC-Algorithm: Improved Causal Structure Learning in Large Random Networks](https://mlsanity.com/paper/1806.06209/) (2018)
- [SparsityBoost: A New Scoring Function for Learning Bayesian Network Structure](https://mlsanity.com/paper/1309.6820/) (2013)
- [On Different Notions of Redundancy in Conditional-Independence-Based Discovery of Graphical Models](https://mlsanity.com/paper/2502.08531/) (2025)

## Built on by (most cited first, 1 of 1)

- [Relaxing Faithfulness with Intervention-Only Causal Discovery](https://mlsanity.com/paper/2607.11816/) (2026)

## Abstract (arXiv)

Learning causal relations from observational data is a fundamental problem with wide-ranging applications across many fields. Constraint-based methods infer the underlying causal structure by performing conditional independence tests. However, existing algorithms such as the prominent PC algorithm need to perform a large number of independence tests, which in the worst case is exponential in the maximum degree of the causal graph. Despite extensive research, it remains unclear if there exist algorithms with better complexity without additional assumptions. Here, we establish an algorithm that achieves a better complexity of pO(s) tests, where p is the number of nodes in the graph and s denotes the maximum undirected clique size of the underlying essential graph. Complementing this result, we prove that any constraint-based algorithm must perform at least 2Omega(s) conditional independence tests, establishing that our proposed algorithm achieves exponent-optimality up to a logarithmic factor in terms of the number of conditional independence tests needed. Finally, we validate our theoretical findings through simulations, on semi-synthetic gene-expression data, and real-world data, demonstrating the efficiency of our algorithm compared to existing methods in terms of number of conditional independence tests needed.