- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes RECAP, a reinforcement-learning framework for causal structure discovery from observational data. It combines group-relative policy updates with an evolving edge-consensus teacher that retains information from high-reward candidate graphs across iterations. Candidate graphs are evaluated using a BIC-based score with acyclicity penalties, while selective, annealed distillation guides subsequent search. Validation includes four main benchmarks, component ablations, a matched-budget configuration-search comparison, and supplementary experiments on 100- and 200-node graphs. The authors report improved SHD and precision on the main benchmarks, with ablations suggesting that both relative evaluation and consensus guidance contribute to structural recovery.
Critical strengths
-
RECAP combines within-input relative evaluation with cross-update structural memory. The former distinguishes candidates within the current group, while the latter retains recurring edges from high-reward proposals.
-
The reported ablations show that removing either relative evaluation or consensus guidance reduces F1 and increases SHD across all four main benchmarks.
Critical weaknesses
-
The experiments in the main text evaluate the proposed method only on graphs with up to 11 nodes. Although the appendix includes experiments on 100- and 200-node graphs, the method does not achieve the best performance in either setting. I am therefore concerned about its performance on graphs with 20–100 nodes.
-
Generating and scoring multiple candidate graphs increases computational overhead, leading to slow runtimes as the number of nodes grows.
Questions for authors
Could the authors compare the total runtime required by RECAP and the baseline methods, including main experiments and experiment on graphs with 100 and 200 nodes?
3 comments
Response to Reviewer BCY2 — Part 2/2: Runtime and Total NAS Cost
W2 & Q1End-to-end runtime and total NAS cost.
We report complete runs at 20, 50 and 100 nodes. Each size uses a shared ER linear Gaussian dataset with 2,000 observations. All 16 methods run on the same Xeon Platinum 8558 and H100 server. Each timing includes training, graph selection and postprocessing at fixed settings.
| Method | 20 nodes / s | 50 nodes / s | 100 nodes / s |
|---|---|---|---|
| PC | 3.89 | 8.74 | 15.86 |
| GES | 23.33 | 3959.90 | 15591.01 |
| ICA-LiNGAM | 4.40 | 6.64 | 11.79 |
| NOTEARS | 14.72 | 195.89 | 1033.66 |
| GraNDAG | 22.09 | 38.07 | 64.94 |
| GOLEM | 339.57 | 372.27 | 379.11 |
| SDCD | 136.60 | 162.35 | 159.63 |
| COSMO | 182.27 | 181.71 | 187.80 |
| DAGMA | 14.16 | 20.07 | 37.52 |
| DiffAN | 36.96 | 647.71 | — OOM |
| CaPS | 14.53 | 434.41 | 8224.86 |
| CORL | 204.38 | 961.22 | 3684.99 |
| ALIAS | 28.38 | 216.20 | 743.99 |
| ABCNAS-RL | 193.61 | 2517.26 | 8524.59 |
| RL-BIC | 526.23 | 2050.07 | — OverflowError |
| RECAP | 51.44 | 205.41 | 962.74 |
OOM denotes GPU out-of-memory for DiffAN at 100 nodes. RL-BIC encounters an integer OverflowError in the gCastle implementation.
RECAP is faster per run than CORL and ABCNAS-RL at all three sizes and uses less peak GPU memory at 100 nodes. It retains multi-candidate exploration and teacher guidance at lower per-run resource cost than these baselines. DAGMA and SDCD are faster at 50 and 100 nodes, reflecting the efficiency of dedicated graph optimization.
At 100 nodes, RECAP takes 962.74 seconds, versus 3684.99 for CORL and 8524.59 for ABCNAS-RL. This lowers the end-to-end cost of each configuration evaluation while retaining exploration and guidance.
Total search cost at 200 nodes
We also measure 200-node search on 2,000 observations from linear Gaussian structural equations. Given the rebuttal period, we use NOTEARS as a representative differentiable causal discovery baseline.
| Method | Single-run time / s | NAS trials |
|---|---|---|
| RECAP | 3674.41 | 20 |
| NOTEARS | 6953.16 | Not applicable |
RECAP includes NAS, so its complete search requires repeated training. Using the paper's 20 trials, estimated total cost is 3674.41 × 20 = 73488.20 seconds, or 20.41 hours. A complete NOTEARS run at fixed settings takes 1.93 hours. RECAP is faster for one run, but its cumulative NAS cost exceeds this fixed-configuration baseline. Reducing configuration-search cost is therefore important for larger graphs.
Single-run time measures the cost of obtaining a graph at fixed settings. The NAS estimate covers repeated training to select those settings. Equal trial counts align configuration evaluations, while total runtime depends on the cost of each architecture and optimizer.
Further scaling
RECAP focuses on improving graph search through relative evaluation and structural memory. SDCD [2] combines a stable acyclicity constraint with sparse-graph training and scales to thousands of variables. DAGMA [3] and DAG-NoCurl [4] improve efficiency through their acyclicity formulation and graph representation.
RECAP separates candidate generation and scoring from the two learning mechanisms. We plan to combine them with sparse candidate screening, more efficient acyclicity computation and order-based graph generation. These directions target lower search cost while retaining the benefits of candidate comparison and historical guidance.
Candidate screening targets the number of connections explored. Efficient acyclicity computation and DAG parameterization aim to reduce the work needed to enforce valid structure. Relative evaluation and the teacher can then use the resulting candidate evaluations to guide recovery.
References
[2] Achille Nazaret, Justin Hong, Elham Azizi, and David Blei. Stable Differentiable Causal Discovery. International Conference on Machine Learning, 2024.
[3] Kevin Bello, Bryon Aragam, and Pradeep Ravikumar. DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization. Advances in Neural Information Processing Systems, 2022.
[4] Yue Yu, Tian Gao, Naiyu Yin, and Qiang Ji. DAGs with No Curl: An Efficient DAG Structure Learning Approach. International Conference on Machine Learning, 2021.
Thank you for your suggestions on scalability. We look forward to your feedback on the new experiments and welcome further discussion.
Follow-up on the Scaling Experiments and Runtime Analysis
Dear Reviewer BCY2,
Thank you again for highlighting the importance of scalability and computational efficiency. In response, we have added further experiments on medium-sized and larger graphs, together with comprehensive runtime comparisons under consistent computational settings. We have also provided an analysis of the total NAS cost to offer a more complete picture of the computational requirements.
As the discussion period is nearing its end, we wanted to check whether our additional experiments and clarifications have addressed your concerns, or if there are any further questions you would like us to discuss. We would be more than happy to continue the discussion and provide any additional information that might be helpful.
Thank you again for your time and consideration.
Best regards,
The Authors
Response to Reviewer BCY2 — Part 1/2: Recovery and Configuration Search
Thank you for recognizing the complementary roles of relative evaluation and structural memory. We address recovery at larger graph sizes below.
We add a 50-node experiment with matched configuration-search budgets. Within the rebuttal period, we select ALIAS, DAGMA, SDCD and GraNDAG as representative baselines covering reinforcement-learning search and continuous optimization. RECAP and each baseline receive ten configuration trials, compared with twenty in the paper. Tuning uses independently generated development data under the same generative settings as the test data. Selected configurations are evaluated on five test datasets. Each method can therefore adapt its configuration to the data-generating setting before evaluation on the shared tests.
Each Erdős–Rényi DAG has 50 nodes and approximately 100 directed edges. Each dataset contains 2,000 independent observations from linear Gaussian structural equations with equal noise variances. Results are means ± sample standard deviations. F1 measures directed-edge recovery.
RECAP has the lowest mean SHD and highest mean F1, recovering the directed structure almost exactly. ALIAS and DAGMA also have high F1. RECAP further reduces the remaining structural errors. With F1 near its upper bound, SHD makes this difference clearer: the mean graph-edit distance is 0.20.
With configurations selected on separate development data, the five-test average assesses recovery on independent samples. RECAP's lower SHD distinguishes it even from the near-complete recovery of ALIAS and DAGMA.
Appendix G.2, Table 7 also reports competitive recovery on 100-node nonlinear graphs. RECAP has SHD of 93.8 ± 13.3, compared with the lowest cited baseline value of 105.0 ± 19.5. The baseline values come from Appendix D, Table 8 of Yuan et al. [1]. These results and the additional 50-node experiment extend the evidence beyond small-graph tasks.
The nonlinear 100-node result addresses a different recovery regime. Here, the advantage is lower graph-edit distance relative to the cited baselines. The 50-node study provides a direct comparison under the same tuning budget and test datasets. Taken together, the two experiments show where RECAP is competitive and extend the empirical evidence across graph sizes and structural equation models.
Configuration search and the learning mechanisms
The Fixed Config. ablation in Section 4.3 and Appendix G.1, Table 6 retains relative evaluation and consensus guidance while removing outer search. On NetSim, it achieves F1 of 0.33 and SHD of 12.00, compared with 0.56 and 10.90 for RECAP. Configuration selection helps choose suitable capacity and training parameters.
Tuning alone does not explain the advantage. In Section 4.4, Table 3 and Appendix G.5.1, Table 10, eligible learned methods receive the same outer-search budget. ABCNAS-RL retains its original search procedure. RECAP still has the highest F1 and lowest SHD. The strongest competing values are 0.51 and 11.60, respectively.
The fixed-configuration and matched-budget comparisons address different explanations. The first measures how much choosing a suitable configuration helps RECAP. The second asks whether giving competing methods the same opportunity for configuration search removes its advantage. Together they show that tuning contributes to performance, while differences in the learning procedure remain important under matched search budgets.
Table 6 shows that removing either learning mechanism reduces recovery across all four benchmarks. Relative evaluation gives the largest F1 gain on NetSim. Consensus guidance gives the largest SHD improvement on Sachs. These results support their complementary roles in comparing current candidates and retaining information for later updates. The new teacher and interaction experiments are reported in our responses to Reviewers
GbrLand8VsV, each in Part 1/3.Reference
[1] Wei Yuan, Zixuan Shao, and Shuhui Wang. Global Directional Priors with Local Statistical Validation for Scalable Causal Discovery. International Conference on Machine Learning, 2026.