# Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the 1+K Lower Bound

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 49 references that are in the map.
- First posted on arXiv 26 May 2026.

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

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game](https://mlsanity.com/paper/2102.13647/) (2021)
- [DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization](https://mlsanity.com/paper/2209.08037/) (2022)
- [Score matching enables causal discovery of nonlinear additive noise models](https://mlsanity.com/paper/2203.04413/) (2022)
- [DiBS: Differentiable Bayesian Structure Learning](https://mlsanity.com/paper/2105.11839/) (2021)
- [Amortized Inference for Causal Structure Learning](https://mlsanity.com/paper/2205.12934/) (2022)
- [BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery](https://mlsanity.com/paper/2112.02761/) (2021)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [On the Identifiability and Estimation of Causal Location-Scale Noise Models](https://mlsanity.com/paper/2210.09054/) (2022)
- [Interventions, Where and How? Experimental Design for Causal Models at Scale](https://mlsanity.com/paper/2203.02016/) (2022)
- [Variational Causal Networks: Approximate Bayesian Inference over Causal Structures](https://mlsanity.com/paper/2106.07635/) (2021)
- [Identifying Patient-Specific Root Causes with the Heteroscedastic Noise Model](https://mlsanity.com/paper/2205.13085/) (2022)
- [Tearing Apart NOTEARS: Controlling the Graph Prediction via Variance Manipulation](https://mlsanity.com/paper/2206.07195/) (2022)

## Abstract (arXiv)

Causal-discovery algorithms return a directed graph, yet provide no principled means of distinguishing edge directions identified by the data from those assigned without an identifying assumption. Under the standard Markov and faithfulness conditions, the observational distribution identifies only a Markov equivalence class; orientations within that class are not determined by the joint distribution and cannot be recovered from additional samples alone, but require either a functional restriction or an intervention. We introduce a protocol for observational causal discovery on continuous data that attaches to each candidate edge a discrete impossibility certificate: a RESOLVED code records the identifiability theorem under which the direction was committed, while an IMPOSSIBLE code records the failure mode together with the specific question a domain expert must answer to resolve it. The bivariate cascade is extended with five gated identifiability tiers LSNM, IGCI, Stein, MDL, and PEIT that abstain when their precondition test rejects. Two oracle primitives, the meta-hub query and the node-children query, jointly establish an upper bound of 1+K expert interactions sufficient to recover any DAG, where K denotes the number of non-leaf vertices. Under an ideal-oracle assumption, the bound is met exactly on the asia, sachs, child, and alarm benchmarks.