Methods that learn a causal graph from data search over graphs one small change at a time: add an edge, drop one, or swap two variables in a candidate causal order. At every step they score the candidates on the same dataset they have already used to reach the current graph. Two things can make such a search stop at a wrong answer. The first is the shape of the problem: some good graphs can only be reached by passing through worse ones. The second is the data itself: the search picks whichever candidate happens to fit this sample's noise best, and later steps judge the next candidates against a graph already bent toward that noise. The literature treats only the first cause. Better search operators, lookahead, and exact solvers all try to escape bad regions of the scoring landscape. The second cause, which we call reuse-induced traps, has never been measured separately.
This note proposes to separate the two causes and to fix the second directly. The fix is to score every candidate move by its leave-one-out prediction error, meaning the error on each data point when that point is left out of the fit. For the per-variable linear regressions used by standard graph scores, this quantity has a closed form and costs about the same as the ordinary fit. The fix also changes the stopping rule: a move is accepted only when its leave-one-out gain is larger than its own sampling noise. We will test whether this "honest" search changes where the search ends up, across starting points and across sample sizes. Two settings matter most. One is standardized data, where current continuous methods are known to collapse. The other is the growing-sample regime, where greedy search is known to stop improving.
Core Claim
In score-based structure learning, a meaningful part of what looks like local-optimum failure at small and moderate sample sizes is the search overfitting through repeated reuse of the data, not landscape geometry. The two causes can be told apart empirically. Rerun the search from the same starting point on leave-one-out or bootstrap perturbations of the data. If the final graph changes, the trap belongs to the sample. If the final graph is stable under perturbation but changes with the starting point, the trap belongs to the landscape. Replacing in-sample score gains with leave-one-out gains, applied inside every step of a topological-swap search, should remove the first kind of trap at nearly no extra cost. It should leave the second kind untouched. A smaller spread of outcomes across starting points will be the observable sign of this.
The rest of this section places the claim relative to prior work. The search we modify is TOPO from Optimizing NOTEARS Objectives via Topological Swaps. TOPO fixes a candidate causal order, fits edge weights consistent with that order, and uses gradient information to pick which pair of variables to swap. It reports SHD 19 against NOTEARS's roughly 1198 on a 50-node dense graph. (SHD, the structural Hamming distance, counts the edge additions, deletions, and reversals needed to turn one graph into another.) TOPO's authors leave open both how data reuse across its inner and outer loops affects results and whether its greedy swaps get trapped. We keep TOPO's search operator and change only how moves are scored and accepted. DAGs with No Fears supplies a second local-search operator, KKTS, which uses the gradient of the acyclicity constraint to find and remove edges that create cycles. It also motivates our setup by showing that post-hoc local search is where much of the accuracy comes from; the paper reports that KKTS typically cuts SHD by a factor of 2 or more. Improving Causal Discovery By Optimal Bayesian Network Learning shows that the precision of Greedy Equivalence Search (GES) stops improving as sample size grows. That paper attributes this to early irreversible commitments and responds with exact search on small clusters. We ask how much of that effect, at finite sample size, is reuse rather than landscape. Beware of the Simulated DAG! constrains our design. On standardized data, NOTEARS's SID rises from near zero to over 1500. (SID, the structural intervention distance, measures how often a learned graph gives wrong answers about the effects of interventions.) Any claimed improvement must therefore hold after standardization and not rely on marginal variance ordering. Out-of-Sample Tuning for Causal Discovery is the closest existing use of held-out evaluation in causal discovery. It uses cross-validation, but only to choose hyperparameters of a black-box learner, at a cost of about 73 minutes versus 25 minutes for StARS on a 10-node graph. We move held-out scoring inside the search and make it essentially free.
Research Program
The scoring change is concrete. For a candidate order and parent set $\mathrm{pa}(j)$ of variable $j$, the in-sample score uses the residual sum of squares from regressing $x_j$ on its parents. We replace that residual sum with the leave-one-out residual sum:
$$\mathrm{LOO}_j = \sum_{i=1}^{n} \left( \frac{e_{ij}}{1 - h_{ii}^{(j)}} \right)^2 .$$
Here $e_{ij}$ is the ordinary residual of sample $i$ in the regression for node $j$, and $h_{ii}^{(j)}$ is the $i$-th diagonal entry of the hat matrix of that regression (a measure of how strongly sample $i$ pulls its own fitted value). We use a Gaussian log-likelihood with a separate noise variance for each node, so the score does not rely on equal variances and remains meaningful after standardization.
A swap proposed by TOPO's gradient rule changes only the regressions of the two swapped variables and of any nodes whose parent sets change. Its leave-one-out gain is therefore a sum of per-sample terms. We accept the swap only when the mean gain exceeds $z$ times the standard error of those per-sample terms. Here $z$ is a fixed constant, set once on a small calibration grid and never tuned per dataset. This rule, rather than a BIC penalty, is what stops the search. The same rule is applied to KKTS edge edits.
The analysis has three parts. The first is the perturbation diagnostic described above. For each dataset we take 20 starting orders and 20 leave-one-out or bootstrap perturbations per start. For each final graph we record the SHD between graphs, the true SHD, and the in-sample score. We then decompose the variance of the outcome into an across-start part (landscape) and an across-perturbation part (reuse).
The second part measures the landscape directly. We estimate the basin of the best-found graph as the fraction of random starting orders that reach it, and we compare that fraction under in-sample and honest scoring, on raw and standardized data.
The third part is a simple optimism calculation, run in simulation. At each accepted step we compare the in-sample gain with the true population gain, and the gap measures the step's optimism. The prediction is that under in-sample scoring, optimism accumulates across steps and grows with the number of candidate moves available per step, roughly $d^2$ where $d$ is the number of variables. Under honest scoring it should stay near zero.
Baselines
The naive reference points are two variance-based heuristics from Beware of the Simulated DAG!, both run on raw and standardized data. The first is NOTEARS from DAGs with NO TEARS, which learns a graph by gradient descent on a smooth penalty for cycles. The second is sortnregress, which orders variables by marginal variance and regresses each on those before it. Reporting both prevents gains that come only from variance ordering.
The strongest existing competitor is TOPO, because it is the best-performing local search over causal orders in the file and our method is TOPO with one change. We run it from the same starting orders, with the same inner solver, the same iteration cap, and the same wall-clock budget. For graphs small enough to be solved exactly, we tune its sparsity penalty over a grid of the same size used to calibrate $z$. The best reported figure is SHD 19 on a 50-node dense graph, from Optimizing NOTEARS Objectives via Topological Swaps. We found no reported result on Lacuna for TOPO on standardized data or on Sachs. We will produce those numbers ourselves. Beating TOPO means a lower median true SHD in our specified regimes at matched compute, and in particular a smaller across-perturbation spread.
NOTEARS followed by KKTS, from DAGs with No Fears, is the second strong competitor, run with the same budget. GES and PC from Causal-learn are classical references and are needed for the sample-size curves.
The GOBNILP exact solver, applied at $d \le 30$, gives the global optimum of the in-sample score. It is the most informative reference point. If honest search reaches a lower true SHD than the exact in-sample optimum, the problem was the score, not the search.
Out-of-sample tuning with cross-validation, from Out-of-Sample Tuning for Causal Discovery, wrapped around TOPO, is the held-out-evaluation competitor. We compare it on accuracy and on runtime.
Two ablations isolate the key ingredient. The first uses leave-one-out scoring only to choose among final graphs, not inside each step. The second keeps in-sample scoring inside the search but adds the standard-error acceptance threshold, computed from in-sample per-sample terms.
Why not just…?
Why not just use BIC, which already penalizes complexity? BIC corrects the fit of one fixed model for its number of parameters. It does not correct for choosing the best of roughly $d^2$ candidate moves at every step, which is the optimism that accumulates under data reuse. The Out-of-Sample Tuning paper already reports that in-sample BIC and AIC overfit when used to select causal graphs. The comparison with GOBNILP settles this directly. If the exact BIC optimum is no better in true SHD than greedy BIC search at small sample sizes, the score is the bottleneck. BIC-scored TOPO against honest TOPO then measures how much of that bottleneck our change removes.
Why not just split the data or cross-validate? Splitting reduces the data available at each step. Arguments from the data-reuse literature, such as Cai et al., show that splitting inflates the required sample size, and the Out-of-Sample Tuning paper's runtime (73 versus 25 minutes at 10 nodes) shows the computational cost. Leave-one-out scoring uses all $n$ samples and adds only the cost of computing hat-matrix diagonals. We still include cross-validated TOPO. If it matches honest TOPO at equal cost, our contribution shrinks to an efficiency gain, and we will report it that way.
Why not just use random restarts and bootstrap aggregation of TOPO? This is the real threat, because aggregating over bootstrap runs also averages away sample-specific traps. The difference is where the correction acts. Bagging repairs trapped runs after the fact, at about $B$ times the cost for $B$ bootstrap replicates. Honest acceptance is meant to stop individual runs from being trapped in the first place. We run bagged TOPO with $B$ chosen to match the compute of honest TOPO with a single restart, and also at $10\times$ that compute. If bagging at matched compute is equally good, we will state that the diagnostic, not the scoring rule, is the lasting result.
Proposed Experiments
The synthetic benchmarks use Erdős–Rényi and scale-free graphs with $d \in \{10, 20, 50, 100\}$ and $n$ from 50 to 10,000 on a log grid. Data come from linear models with Gaussian, exponential, and Gumbel noise, and include an equal-variance condition and a heteroscedastic (unequal noise variance) condition. We run every configuration on raw and on standardized data and report varsortability, the measure from Reisach et al. of how well marginal variance ordering recovers the causal order. For Gaussian noise we score against the Markov equivalence class, meaning the set of graphs the data cannot distinguish; otherwise we score against the true DAG. Metrics are SHD, SID, precision, recall, runtime, and the landscape-versus-reuse variance split. To probe precision saturation, we also add near-cancelling paths that approximately violate faithfulness, following the regime described by Lu, Zhang, and Yuan. For real data we use Sachs, where the file reports varsortability of 0.57, scored against the consensus network. We also use the resimulated UCI datasets from the Out-of-Sample Tuning paper.
The decisive checks are four. First, on standardized data at small and moderate $n$, the across-perturbation share of outcome variance should be large for TOPO and GES. Honest TOPO should reduce it and lower true SHD. If the reuse share is already negligible, the core claim fails and we will report that. Second, honest search should match or beat the exact in-sample optimum in true SHD at $d \le 30$ and small $n$. Third, in the precision-versus-$n$ curves, honest scoring should raise precision where the landscape share is small. It should leave saturation in place where the landscape share dominates, which would locate the effect Lu et al. describe on the landscape side. Fourth, the measured optimism per accepted step should grow with $d$ under in-sample scoring and stay near zero under honest scoring. All four outcomes, including the negative ones, identify which cause is responsible for the local optima that the three research directions each study separately.
References
- Optimizing NOTEARS Objectives via Topological Swaps
- DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks
- Improving Causal Discovery By Optimal Bayesian Network Learning
- Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy to Game
- Out-of-Sample Tuning for Causal Discovery
- DAGs with NO TEARS: Continuous Optimization for Structure Learning
- Causal-learn: Causal Discovery in Python
- Nonconvex Low-Rank Tensor Completion from Noisy Data