TL;DR.
Recursive causal discovery repeatedly identifies a removable variable, learns its local structure, removes it, and solves a smaller problem. We unify four recursive algorithms—MARVEL, L-MARVEL, RSL, and ROL—show that their worst-case complexity nearly matches lower bounds for constraint-based discovery, and release them in the RCD Python package.
Why this matters.
Recursion attacks two bottlenecks at once: it reduces the total number of conditional-independence tests and keeps conditioning sets smaller as the graph shrinks. The result is a unified causal-discovery toolkit with both theoretical efficiency and a practical implementation.
Abstract
Causal discovery from observational data, i.e., learning the causal graph from a finite set of samples from the joint distribution of the variables, is often the first step toward the identification and estimation of causal effects, a key requirement in numerous scientific domains. Causal discovery is hampered by two main challenges: limited data results in errors in statistical testing and the computational complexity of the learning task is daunting. This paper builds upon and extends four of our prior publications (Mokhtarian et al., 2021; Akbari et al., 2021; Mokhtarian et al., 2022, 2023a). These works introduced the concept of removable variables, which are the only variables that can be removed recursively for the purpose of causal discovery. Presence and identification of removable variables allow recursive approaches for causal discovery, a promising solution that helps to address the aforementioned challenges by reducing the problem size successively. This reduction not only minimizes conditioning sets in each conditional independence (CI) test, leading to fewer errors but also significantly decreases the number of required CI tests. The worst-case performances of these methods nearly match the lower bound. In this paper, we present a unified framework for the proposed algorithms, refined with additional details and enhancements for a coherent presentation. A comprehensive literature review is also included, comparing the computational complexity of our methods with existing approaches, showcasing their state-of-the-art efficiency. Another contribution of this paper is the release of RCD, a Python package that efficiently implements these algorithms. This package is designed for practitioners and researchers interested in applying these methods in practical scenarios. The package is available at github.com/ban-epfl/rcd, with comprehensive documentation provided at rcdpackage.com.
The paper at a glance
An informal guide to the problem, the idea, and the main results.
1. The problem
Constraint-based discovery often struggles because it repeatedly performs difficult conditional-independence tests over large conditioning sets. This makes both sample complexity and runtime deteriorate quickly as the graph grows.
2. The key idea
We exploit removable-variable logic: if a variable has the right local properties, we can identify it, remove it, and recurse on the smaller problem. That changes the computational profile of causal discovery in a fundamental way.
3. Recursive discovery framework
We formalize removable variables and removable orders, characterize when variables can be safely eliminated, and show how recursive removal supports causal discovery in both DAG and latent-variable settings.
4. Near-optimal complexity
We derive worst-case complexity bounds for the recursive algorithms and lower bounds for constraint-based causal discovery, with the proposed methods nearly matching those limits. We also provide the open-source RCD package implementing MARVEL, L-MARVEL, RSL, and ROL.
5. How it works
- Use local conditional-independence information to identify a removable variable.
- Orient or record the corresponding structural relations.
- Delete that variable and recurse on the smaller graph.
- Assemble the full causal graph from the recursive outputs.
What the experiments show
Where this helps
Good fit
- You want a scalable alternative to standard constraint-based causal discovery.
- Your main bottleneck is large conditioning sets and unstable conditional-independence tests.
- You care about structure learning in graphs where locality can be exploited.
Keep in mind
- RCD is a unified framework rather than a single algorithm: different recursive variants cover DAGs, latent-variable settings, and permutation-based discovery.
- The package provides a practical implementation of the theory, with documentation and reusable Python code for large-scale experiments.
Cite this paper
@article{JMLR:v26:24-0384,
author = {Ehsan Mokhtarian and Sepehr Elahi and Sina Akbari and Negar Kiyavash},
title = {Recursive Causal Discovery},
journal = {Journal of Machine Learning Research},
year = {2025},
volume = {26},
number = {61},
pages = {1--65},
url = {https://www.jmlr.org/papers/v26/24-0384.html}
}