acceptodds
Under review as a conference paper at ICLR 2027

Where the Accuracy Goes in Single-Edit Causal Search

Abstract

Score-based structure learning returns the graph a greedy search reaches by repeatedly taking the single edit that most improves a score such as BIC, so its output is settled by how the score orders the candidate edits at each step, an order that evaluation by the final graph never observes. We measure it by replay on five discrete benchmark networks: at every step of searches that were actually run, every legal edit is rescored with the shipped implementation and against the ground-truth graph. On the three smaller networks the edit the search takes beats most accepted alternatives in oriented-edge F1, yet it is the best of them at only 45% of steps, and against its closest competitors in score it is truer 58% of the time. Reordering only the edits the score already accepts recovers 32.6% of the distance from a uniform draw to the single-edit ceiling, against 10.1% for the score's own order. Half of that gap is exact ties between Markov-equivalent successors, which the data cannot orient and the implementation breaks by enumeration order; a coin flip in its place moves the result significantly, in opposite directions on different networks. On the two larger networks the gap narrows to 4.3 points. Measured against what reordering can reach, a frontier language model in the reordering role recovers 76.2% on child and insurance, averaged over three runs, against 43.5% for the score's own order; its lead disappears when variable names are replaced by pseudonyms and survives plain-language descriptions. No open-weight model we tested beats the score significantly.

Primary area:
causal reasoning
Keywords:
causal discovery, structure learning, Bayesian networks, score-based search, model selection, large language models, prior knowledge

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_VgA6OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The author proposed that in the causal structure learning algorithm based on the scoring function, the modification with the highest score does not necessarily correspond to the modification closest to the real causal graph. The paper presented an analysis method based on replaying search trajectories to measure the situation of the scoring function in each step of the candidate decisions. The author selected search trajectories that had actually been run, and re-enumerated all legal modifications at each previous decision point, respectively calculating the ranking of the scoring function and the accuracy rate of the real structure. The experimental results show that the scoring function is useful, but there are situations where the best candidate is not selected; re-arranging the candidates can significantly improve the accuracy rate; nearly half of the ranking losses come from candidates with the same score; complexity penalties cause sparse preferences. The author added LLM to the causal structure, and let LLM determine which one to choose in the next step among the candidate modifications that have been filtered by the scoring function. The conclusion drawn is that the model's advantage mainly comes from the semantics of the variables, rather than specific names in the benchmark data.

Critical strengths
  1. The author did not start from the outcome but rather focused on the candidate selection process during the analysis of the causal diagram, identifying the locations where the accuracy rate suffered.
  2. The author demonstrated that the ranking order of the candidate results and the scoring processing rules also have an impact on the experimental results.
Critical weaknesses
  1. The author mainly presented experimental evidence and mechanism analysis, but did not provide new theoretical proof, nor did they prove that LLM ranking is definitely superior to the original scoring.
  2. The experimental scale of the author was limited. The research was based on five discrete benchmark networks, among which the larger networks had 70 and 76 variables. Therefore, the experimental results cannot indicate that this phenomenon has the same effect in large-scale causal discovery tasks in the real world.
Questions for authors
  1. Does the LLM's benefit stem from true semantic understanding rather than familiarity with the benchmark data?
  2. Are the main findings of the paper statistically robust?
  3. How does the paper distinguish between the search ranking problem and the problem of the scoring function itself?
2 comments
AuthorsOpenReview ↗

Response to Reviewer VgA6

Thank you for the review.

Main point for your review: your central question, meaning or familiarity, now has an answer from two networks written after the models were trained. The effect comes through the variable names; with the names replaced, the models do no better than chance.

Q1. Semantics or familiarity. The submission could not separate the two; the experiment we ran on 9 and 10 November does.

On public benchmarks the two cannot be told apart. Asked for each variable's parents with the network named, gpt-6.1-sol lists 117 of the 123 true edges, and the models name the benchmark in 5 of 6 probes from paraphrased descriptions that contain no variable name. So we wrote a network no model can have seen: 21 greenhouse variables and 30 edges, with the graph, the generator and the data checksums committed before the first model call.

The results closely match those on the benchmarks. With the real names, gpt-5.6-sol picks the truer direction at 94.7% of 151 ties, against 74.2% for the implementation's own tie-break. With the variables renamed it is right at 50.5% of 315. Choosing at every step, it recovers 89.5% of the reranking reference with names, 55.7 points above greedy [+30.4, +82.5], and falls 53.6 points below greedy when the variables are renamed. What the names convey is enough to produce the effect.

Recall still adds something on the benchmarks. There a model's parent list is nearly exact (precision 0.96 to 1.00 with the network named); on the new network the same model lists 22 of the 30 edges among 41 guesses. Its most common mistake on our network is to say that temperature drives the vents, as a thermostat would, where we drew the vents driving temperature.

We then repeated the experiment with a second model and a second network (a bike-share scheme, 24 variables). gpt-6.1-sol on the greenhouse network: 96.7% of 152 ties with names, 49.2% renamed. On the bike-share network both models are right at all 220 ties with names, and at 50.4% and 36.8% renamed.

Two caveats. Both graphs were drafted with an AI assistant from another provider and then corrected by us, in domains where common sense is a good guide. And on the greenhouse network we first ran 9 cases, then added 18 to narrow the intervals; Appendix M.4 reports the two batches separately. The submission read the description control as evidence against recall, and Appendix H withdraws that reading.

W1. Theory; whether LLM ranking is superior. The revision adds theory where the claims need it: Proposition 1 states when adding A→B and adding B→A tie under every score-equivalent score, Proposition 2 which of the two the likelihood floor prefers, and population scores remove sampling noise. Under population scores the tie choices alone decide the returned class in 166 of 199 faithful five-variable networks (Appendix A).

On superiority, the paper makes no such claim; the language model is one tie rule among several. At ties with a truer member on child and insurance, the frontier models choose it at 90.2% and 92.6%, against about 79% for the implementation's own tie-break, a lead that does not survive Holm correction (p = 0.094). On alarm the lead is 36.2 points and does survive it (p = 0.047).

W2. Scale. The study now covers eleven networks, the largest being pathfinder (109 variables), andes (223) and pigs (441), with 39 cases each. Resolving ties by the truth removes 41% of greedy's CPDAG SHD on andes and 59% on pigs, and covered-edge reversal recovers 94% and 91% of that; on pathfinder the tie loss is small and not significant (Table 1). On the real Sachs data resolving ties changes almost nothing (Appendix I).

Q2. Statistical robustness. Every interval resamples whole cases (10,000 bootstrap replicates). Contrasts that rest on nine cases are also tested with exact sign-flip tests, and families of contrasts are Holm-corrected (Appendix L). For example, against a coin flip, the implementation's tie-break is better in 8 of 9 cases on child and 9 of 9 on insurance, and worse in 8 of 9 on alarm (exact p = 0.027, 0.004, 0.012, all surviving Holm).

Q3. Search ranking or the score. Both, and the paper separates them. Every policy we compare takes its edit from the set the score accepts, so any difference between policies is a difference in ranking. What the score excludes is measured separately in Appendix C. From the default start, 54.9% of the single-edit oracle's F1 gain comes from edits the score accepts and 25.5% from edits it rejects under every setting we tried; from the empty start these are 80.5% and 7.3%. On 13 November we removed the score's estimation error altogether: with exact population scores on 2,206 small networks, resolving ties by the truth still leaves 18% of the ordering loss, which ranking by the truth removes. Part of the ranking problem therefore lies in the search itself (Appendix A).

AuthorsOpenReview ↗

Update (17 November): a second provider

A second provider. Since our reply, three Google models have run the same protocol, and they repeat every reading. The run was made on 17 November, after all the results above had been read. They ran both roles on the greenhouse and bike-share networks (27 cases each, names twice, five pseudonym maps) and the full role on child and insurance; the requests are those of the GPT runs except for the reasoning setting.

gemini-4-carbon and gemini-4-argon answer without reasoning, as gpt-5.6-sol does. With names they pick the truer direction at 97.4% and 98.7% of the greenhouse ties, against 78.2% for the implementation's tie-break, and at all 220 bike-share ties. With the variables renamed they are right at 51.9% and 50.9% on greenhouse, and at 43.5% and 39.6% on bike-share. Choosing at every step, they end 54 to 68 points above greedy with names and 38 to 63 points below it renamed, on both new networks and on child and insurance.

gemini-4-hydrogen cannot turn its reasoning off. With names it reads as the other two. Its renamed runs fail our audit gate: they parse 74% to 90% of their answers, and in the full role one presented position takes most of the choices. We report those runs and do not read them.

The finding of our reply therefore holds for four models from two providers: what the variable names convey is enough, and without the names the models do no better than chance. One caveat changes wording: both graphs were drafted with Claude (Anthropic), whose models we did not test. Appendix M.4 and its new table give every number; the traces are in the supplement.

Reviewer_v5TvOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2(+1)
Soundness
3
Read review
Paper summary

The paper starts with a hypothesis that reordering edits in a hill-climbing score-based approach for finding Bayesian network structure can lead to significantly better results. They compare the greedy approach to other strategies, as well as two F1-score-based oracles compared to the ground truth graph. The measurements then show that better ordering can lead to better final structure. The paper also focuses on how the ties are selected and on the sparsity aspects of the next candidate graph selection. A technical contribution lies in the step where they decide to outsource this ordering to Large language models. LLMs are presented with valid edits to the causal structure accepted by the score, with the prompt to give the most likely.

Critical strengths
  • I like the contribution paragraph in the introduction, it nicely summarizes. Similarly, the paper presents a robust set of measurements.

  • The idea of reordering edits in the search for the causal structure is good and well supported by the experimental data. However, it needs to be said that it is not completely novel; similar approaches exist (ReActBN). The authors carefully state the difference at the end of the paper. " ReActBN (Zhang et al., 2026) is the closest design to our ordering role: at each step a model sees the ten best-scoring neighbouring graphs with their scores, may choose any of them, and a tabu list prevents revisits; its ablations, run on the data-free variant, vary whether names or descriptions are given, both of which carry meaning. Our model sees only accepted edits and no scores, cannot leave the veto, and is compared against a truth-reordering ceiling; pseudonyms are the presentation that removes meaning, and descriptions the one that keeps it without the benchmark’s spelling."

Critical weaknesses
  • The paper has presentation issues and is difficult to read for a human reader. The abstract and introduction are hard to digest. I recommend that the authors focus more on the ideas presented in the paper, rather than the numeric results, even if that includes rewriting the abstract and introduction manually without LLMs. For those who are not aware of the exact datasets used, sentences such as "a frontier language model in the reordering role recovers 76.2% on child and insurance" are raising questions, such as "What child? Some child nodes?". Similarly, "averaged over three runs" is information not needed in the abstract. Some abbreviations lack a definition, such as CPDAG. The first sentence in the abstract seems misleading. For example, GOBNILP (not my paper, https://arxiv.org/abs/1605.04071) is a score-based method, which, however, does not use the hill-climbing approach stated. As this is the motivation in the introduction, later as well, I recommend that the authors look for the exact methods in Bayesian learning as well. It might also be more helpful to stress that the paper presents measurements rather than a method.

  • The difference between ReActBN and the presented paper is quite small, which raises a question of why ReActBN is not included in the experiments.

Questions for authors
  • You are aware of the possible data leakages, as the models might have learned about those well-known datasets. Could you comment more on the way pseudonyms for the variables are found?

  • Why did you choose the F1-score for comparing to the ground truth? I am asking as this does not give any information about the Markov equivalence class, as A->B->C and C->B->A are in the same Markov equivalence class, while A->B<-C is not. If A->B->C is correct, then the result from the same Markov equivalence class is scored worse than the collider.

  • What do you mean by the shipped score in the replay? It does not look like a standard term.

2 comments
AuthorsOpenReview ↗

Response to Reviewer v5Tv

Thank you for the review. Readability was your main concern, and we spent most of the revision on it.

Main changes for your review: the abstract and introduction now state one idea with few numbers, each section opens with its question and its answer, and ReActBN's presentation is now an experiment inside our replay (W2).

W1. Readability. We rewrote the abstract and the introduction by hand. Going through your list:

  • "What child?" Child is introduced as a 20-variable network in the caption of Figure 1 and again in Section 2, before any result on it.
  • CPDAG. Defined in the introduction and in Section 2, together with what CPDAG SHD counts.
  • "Averaged over three runs." Moved from the abstract to Section 7.
  • GOBNILP. The opening no longer groups it with hill climbing.
  • Numbers without context. Each headline number in the abstract and introduction now states its metric and its starting graph, and the introduction gives the three findings in three short paragraphs.
  • An example. Figure 1b now draws a three-variable collider, and Appendix A works through it: one column order returns the true graph and another a graph wrong at every pair of variables. If the idea is still unclear after the abstract, this example makes it concrete.
  • Method or measurement. The abstract now opens by calling the work a measurement experiment on greedy hill climbing, and states the idea two sentences later: "when two variables share the same parents, adding an edge between them in either direction yields two graphs that no score computed from observational data can distinguish, so the direction is set by implementation details such as the column order in the data file."

W2. ReActBN. The two papers ask different questions. ReActBN lets the model choose among high-scoring neighbours and reports the final graph. We hold the search fixed and measure, step by step, how much a different choice could gain and how much a model's choice does gain. ReActBN's presentation is now part of the experiments, run inside our replay: the model sees the ten best-scoring neighbours that are not on a tabu list, with their score changes, and may stop (Section 7). On 18 cases with names, gpt-5.6-sol ends 17.6 points above greedy [+0.4, +37.9] and gpt-6.1-sol 24.9 above [+8.8, +44.7]; under pseudonyms neither is significantly ahead of greedy. The intervals are wide.

Appendix D (Table 6) goes one step further and crosses the two ingredients of that presentation, the candidate set and whether score changes are shown, for gpt-5.6-sol, gemma-4-31B and Llama-3.1-70B. Showing the scores makes every model follow them more closely. Llama-3.1-70B then takes the top-scoring option at every step and ends exactly at greedy, which is 22.4 points above its own choices. gpt-5.6-sol takes the top-scoring option at 72.6% of steps on ReActBN's candidates and 37.6% on the full accepted set, and ends 17.5 points lower on ReActBN's candidates [−36.4, −0.4].

Q1. Pseudonyms. Each variable is renamed either to an ordinal label (V1 to Vn) or to a pronounceable three-syllable non-word that is absent from the system dictionary. The assignment is a seeded permutation, so the order of the labels says nothing about the order of the columns. We use five such maps. A run enters the analysis only if it passes an audit on how many answers parse and on where in the list the chosen option sits (Section 7, Appendix M).

Q2. Why F1. Section 2 now has a chain like your A→B→C against C→B→A. Oriented-edge F1 scores the second graph as entirely wrong although the two are Markov equivalent. The revision therefore reports CPDAG SHD beside F1 for every main result and states the tie claims in it. F1 stays because the systems we study report it. The paper also says how much of an F1 gain is such an open direction. From the default start it is 1.46 of the 2.77 DAG-distance edges that reranking gains (52.8%), and 84.6% of the 1.33 edges that resolving ties gains.

Q3. "Shipped score." The revision says "the implementation's own score" and defines it in Section 2.

Dear authors,

Apologies for the last-minute reply. Thank you for the changes, such as the graphical abstract, SHD measurements, and Figure 4. From the introduction, the message of the paper is now much clearer, and since my main concern was the readability of the paper, I would not object to acceptance of the paper; i.e., in its current form, my score would be a weak accept. Overall, I think that the topic is important, as many causal learning algorithms use the presented hill-climbing approach, and your paper provides measurements that can serve as grounds for improving the existing approaches.

Reviewer_iQb6OpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper investigates the limitations of score-based greedy causal discovery by analyzing how scoring functions rank candidate graph modifications during the search process. Rather than evaluating only the final learned graph, the authors examine individual search decisions and compare the ranking induced by a BIC-based score with the ranking obtained using ground-truth graph information.

The authors conduct experiments on five discrete Bayesian networks and report that the greedy search frequently selects edits that are suboptimal in terms of oriented-edge F1. They attribute the resulting accuracy gap primarily to two factors: ties between Markov-equivalent graphs and a preference for sparser graphs induced by the complexity penalty. The paper additionally investigates whether large language models can improve the selection of candidate edits by exploiting semantic information about the variables.

The main contribution is an empirical analysis of the sources of accuracy loss in single-edit greedy causal search, rather than a new causal discovery algorithm.

Critical strengths
  1. Interesting research question. The paper investigates the quality of individual decisions made during greedy causal discovery, rather than focusing exclusively on the final estimated graph. This perspective could provide useful insights into the behavior and limitations of score-based search procedures.

  2. Analysis of tie-breaking behavior. The observation that implementation-dependent tie-breaking rules can significantly affect the final directed-edge accuracy is interesting and highlights a potential reproducibility issue in causal discovery benchmarks.

Critical weaknesses
  1. Insufficiently clear methodological description and missing formal definitions. The paper is difficult to follow because the experimental methodology is not presented in a sufficiently systematic and formal manner. In particular, the scoring function, the different selection policies, and the proposed decomposition of accuracy loss are introduced primarily through verbal descriptions rather than precise mathematical definitions. Although several implementation details are provided in the appendices, the main text lacks a unified mathematical formulation and an algorithmic description of the experimental procedure. It is also initially unclear whether the authors are proposing a new causal discovery method or conducting an empirical analysis of an existing one. The distinction should be explicitly established and the contributions better organized.

  2. The paper's central accuracy-loss decomposition and the associated performance comparisons are based on oriented-edge F1. Although the authors also report results using CPDAG SHD, the central decomposition is not repeated using an equivalence-class-based metric. This is a significant limitation because oriented-edge F1 penalizes incorrect orientations even when they are not identifiable from observational data.

Questions for authors
  1. Why is oriented-edge F1 used as the primary metric for quantifying accuracy loss when some edge orientations are not identifiable from observational data?
  2. How robust are the conclusions to different search procedures, initialization strategies, and graph sizes? In particular, could the authors further investigate why the measured ordering loss decreases considerably on the two larger networks and whether the reported effects persist for substantially larger or real-world causal discovery problems?
1 comment
AuthorsOpenReview ↗

Response to Reviewer iQb6

Thank you for the review.

Main changes for your review: Section 2 now states the method formally (score, rejection rule, Algorithm 1, policies; two propositions proved in Appendix A), and every main result is also reported in CPDAG SHD, which narrowed one claim.

W1. Formal presentation; method or analysis. The paper is an analysis of an existing learner. The introduction now opens with what evaluating only the final graph misses, states that we replay a released learner, and then gives three findings. The formal part is the new Section 2. It gives the score (BIC plus a per-edge penalty), the score change of an edit and the rule that rejects one, the search as Algorithm 1, and each policy we compare as a choice rule over a candidate set. The sets are nested: the tied edits are among the edits the score accepts, which are among all legal edits. With these definitions the gap between reranking and greedy splits into a part due to ties and a remainder,

Q(reranked) − Q(greedy) = [Q(ties resolved) − Q(greedy)] + [Q(reranked) − Q(ties resolved)].

Appendix A proves when adding A→B and adding B→A tie under any score-equivalent score, and which of the two the likelihood floor prefers. It also works through one example, which we think is the easiest way into the paper: a three-variable collider A→B←C scored from its exact distribution. With the columns ordered (A, C, B) the search returns the true graph. With the common effect listed first, both edges are drawn out of B, the two causes become dependent given B, a third edge joins them, and the search stops at the complete graph. Covered-edge reversal returns the true graph from the same order.

W2 and Q1. Why F1; the decomposition on other metrics. The decomposition is now also reported in CPDAG SHD, and this changed what the paper claims. The answer depends on the start (Appendix K, Table 19):

startF1: ties, of the ordering loss (share of the reference)CPDAG SHD: ties, of the edges reranking gains
default (output of another algorithm)11.4 of 22.5 points0.08 of 1.85, interval includes zero
empty graph25.4 of 45.3 points6.81 of 15.30

The tie finding on equivalence classes therefore holds for the empty start. From the default start, resolving ties closes 1.33 edges of DAG distance, 84.6% of them directions that observational data leave open, and CPDAG SHD moves by +0.08 edges [−0.05, +0.23]. The submission's F1-only headline overstated the identifiable loss, and the revision states the tie claims in CPDAG SHD. We keep F1 beside it because the systems we study report it, and a user who needs a DAG cares about it. Section 2 has a three-variable chain showing where the two metrics disagree. The loss not due to ties also appears in CPDAG SHD: with exact scores, ranking the accepted edits by CPDAG SHD instead of F1 removes it just the same (Appendix A, 13 November).

Q2. Robustness. We varied every item on your list.

Search, start and size. Table 1 runs Tabu, random restarts, HC-Stable and Tabu-Stable beside greedy on eleven networks from 11 to 441 variables, from the empty start. Resolving ties by the truth removes up to 59% of greedy's CPDAG SHD on the largest. GES and BOSS now run under the hill climbers' own score on all eleven networks (Appendix E): GES does not move with the column order and ends 10.1 CPDAG SHD edges closer than greedy once the columns are shuffled, and covered reversal stays within 3.4 edges of it. Appendix K reports the ordering loss from seven starting graphs (Table 17) and the tie cost from two, as in the table above.

Scores, sample sizes and a second implementation. Resolving ties still helps under BDeu, under Gaussian BIC on four linear Gaussian networks, and at 20,000 and 50,000 rows (Appendix F). We also repeated the analysis on a textbook hill climber (BIC alone, no edge penalty, no likelihood floor, empty start), with the decision rules written before its runs. There 303 of 920 steps are tied, and resolving ties closes 8.56 CPDAG SHD edges [+5.63, +11.67].

Why the loss shrank on the two larger networks. We had misread this. The data files of hepar2 and win95pts list their variables in a causal order, so the file-order tie-break happened to be right there. With the columns shuffled, under BDeu, the tie loss is significant on all eleven networks (Appendix F, Table 11). Appendix H withdraws the earlier reading.

Real data. On real data we find no effect. On the Sachs data greedy reaches an oriented-edge F1 of 0.27; resolving ties and reordering move CPDAG SHD by +0.05 and +0.24 edges under the standard discretisation, and by −1.6 and −1.1 under a tertile one (Appendix I). All other data are sampled from benchmark networks.

Reviewer_SGSrOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies greedy single-edit hill climbing for causal structure learning on discrete data. It argues that the learned graph is decided by how the score (BIC) ranks candidate edits at each step, something that evaluation on the final graph does not reveal. The authors replay recorded searches and score every legal edit at each step both with the original scorer (reproducing all 2,400 recorded score changes) and against the true graph (oriented-edge F1 and CPDAG SHD). On the three smaller networks, the edit greedy takes is the best of the score-improving edits at only about 45% of steps, and is truer than its closest competitors in score only 58% of the time (chance is 50%). Restricting every policy to score-improving edits and reordering them by the truth recovers about three times more accuracy than the score’s own order. About half of this loss comes from exact ties between Markov-equivalent graphs, broken by the variable order in the network file, which helps on some networks and hurts on others. The authors attribute the rest to a sparsity preference from BIC’s complexity term. The effect shrinks on larger networks. Finally, among 17 language models placed in the ordering role, only the frontier model beats the score significantly, and its advantage depends on variable meaning (it disappears under pseudonyms). Validation uses data sampled from five benchmark networks, case-level bootstrap intervals, and partial controls for memorization (pseudonyms and plain-language descriptions).

Critical strengths
  1. A new, well-designed measurement of how the score guides search. Instead of evaluating only final graphs, the paper measures how BIC ranks the candidate edits at every step against the truth. It isolates the ordering’s contribution by keeping the score’s veto fixed: every policy may take only score-improving edits. The “ties resolved” policy separates exact indifference from misordering. The finding that the score is weakest against its closest competitors is intuitive and suggests a new perspective on why greedy search fails. This matters for my assessment because it is the paper’s main conceptual contribution. While the tie and variable-order mechanism has been studied before (see Weaknesses), the step-level evaluation of ranking fidelity against the truth appears to be new.

  2. Rigor and transparency of the empirical work. The replay reproduces all 2,400 recorded score changes. Intervals come from a case-level bootstrap, with contrasts computed within replicates. Language-model results pass an explicit audit gate and include pseudonym controls and, on child, description controls. The authors state that all traces and result files are released, and some of the limitations are stated candidly. This matters because the paper’s value is mainly diagnostic, so the credibility of its measurements is central to its contribution.

Critical weaknesses
  1. The submission does not discuss closely related work by Kitson and Constantinou. The submission states that “no study has measured how faithfully the score orders the candidates a search actually weighs,” and describes its tie-break effect as “a new instance of the order effects known for constraint-based search and simulated benchmarks.” However, Kitson and Constantinou’s DMKD 2024 paper (arXiv:2206.08952) traces hill climbing step by step on bnlearn networks, including the five used here, and measures how often the best move is a tie between Markov-equivalent neighbors, oriented by column order. At moderate-to-large sample sizes, that paper shows that variable ordering changes hill climbing’s CPDAG F1 more than sample size, the choice of score, or BIC’s complexity scaling. Kitson and Constantinou’s follow-up paper (PGM 2024, introducing HC-Stable and Tabu-Stable; extended in arXiv:2504.01740) breaks these ties with a data-derived node order, removing order instability and improving CPDAG F1 on categorical networks. This qualifies the submission’s claim that “an outside source is the only thing that can supply the direction.” The HC-Stable paper also reports that BIC often scores the true graph below learned graphs, and that learned categorical graphs are sparser than the truth. Together, the two Kitson and Constantinou papers anticipate the submission’s tie mechanism and its network-dependent tie-break effect, and also vary the complexity scaling. The submission should discuss HC-Stable and compare against it as a truth-free tie-break baseline. The submission’s step-level replay against the truth, its decomposition of ties vs. misordering, and its LLM ordering role remain distinctive, but would be strengthened by positioning them against this prior work.

  2. The analysis is limited to single-edit hill climbing. The authors acknowledge this and justify it by its use in LLM-based proposal systems. However, no method with larger moves is evaluated under the same protocol: Tabu search, random restarts, GES, or permutation-based search (GRaSP/BOSS). Since GES avoids Markov-equivalent ties by construction, and Tabu has been reported to be less sensitive to variable order than plain hill climbing (Kitson & Constantinou, 2024), it is unclear how much of the reported ordering loss would remain for practitioners who can use these alternatives. Even a limited comparison on the smaller networks would help establish the practical relevance of the findings.

  3. The paper is dense, with many numerical results packed into the text. Some results are reported without interpretation (for example, the opposite trends of the two metrics on the larger networks in Table 7), and the use of different reference ceilings across sections makes numbers hard to compare. Brief interpretation of such results and a consistent reference scale would improve readability.

Questions for authors
  1. Report the LLM results under both pooling methods, perhaps in an appendix, so readers can see which conclusions depend on the choice.
  2. Clarification on score-gap quartiles (Section 3, Table 7). Are the “closest quarter” and “farther half” defined by quartiles of the score gap computed within each step, or pooled across all steps and cases? If pooled, BIC score gaps grow with sample size, so the closest quarter could consist mostly of comparisons from small-sample cases. The 57.7% figure might then reflect sample size rather than closeness in score.
  3. Several results are reported without interpretation, which makes the paper hard to follow for readers less familiar with this literature. For example, Section 3 and Table 7 show that on hepar2 and win95pts the taken edit is the best accepted edit at 53.6% of steps by oriented-edge F1 but only 21.7% by CPDAG SHD, compared with 44.9% and 36.5% on the smaller networks. The two metrics move in opposite directions, and the paper does not explain why. Could the authors explain this discrepancy (for example, how ties on the metric are handled when determining the “best” edit)? More generally, a sentence of interpretation after key numerical results would make the paper considerably more accessible.
  4. The paper notes (Section 4, Table 4) that hepar2 and win95pts are listed in exact topological order, so every true edge points forward in the file. Since exact ties are broken by enumeration order, which follows the file order, the default tie-break may systematically favor the true orientation on these two networks. This could contribute to the smaller ordering loss reported there (4.3 vs. 22.5 points), in addition to the per-tie F1 explanation the authors give. Could the authors report how often the first-generated member of a tie is the truer one on hepar2 and win95pts (as they do for the smaller networks), or repeat the analysis with shuffled or randomized tie-breaks?
  5. Can the authors offer an explanation (for example, model size, domain knowledge, or reasoning ability) for why none of the open-weight models beats the score significantly, and why several are above it in point estimate on insurance but none on child (Table 14)?
  6. Why do the frontier model’s three runs differ by about 21 points (67.3–88.7%) at temperature 0, and how does this affect the reliability of the single-run conditions (pseudonyms, descriptions, alarm)?
  7. Three larger open-weight models on the roster (deepseek-v4-flash, llama3.1-70b, llama-4-scout) were not run, and two others (gemma-4-31b, qwen3-next-80b) failed to start, so, as far as the checkpoint names show, the tested open models are about 32B parameters or smaller. Could the authors run at least one or two larger open models? The paper acknowledges in Section 7 that the result covers only the models run, but testing larger open models would show whether the gap to the frontier model reflects scale.
  8. The paper is primarily diagnostic, and its actionable takeaways are limited to reporting practice: stating the tie-break rule, reporting equivalence-class metrics, and sweeping the complexity term. The remedy for ties the paper explores, a frontier language model, depends on a closed model and on well-known benchmark networks. The paper would be strengthened by evaluating at least one truth-free remedy under the same protocol, for example, the stable tie-breaking of HC-Stable (Kitson & Constantinou, 2024/2025). Placing it alongside the existing truth-based ceilings (“ties resolved by the truth” and “reranked”) would show how much of the ordering loss a practical method can recover, and would turn the diagnosis into guidance practitioners can act on.
  9. The ordering loss (reranked − greedy, 22.5 points) is the paper’s focus. But the gap between reranked (32.6%) and the single-edit oracle (100%) is about three times larger, and the paper reports it only as a ceiling. This gap comes from BIC’s veto blocking edits that would have improved F1. The oracle ignores the data, though: it reaches F1 = 1.0 on child and insurance even at 250 rows. So part of this gap likely reflects weak true edges that no data-driven method could detect, not a flaw in BIC. Could the authors break down the blocked but helpful edits, separating weak true edges the data cannot support from those blocked by BIC’s bias (for example, the complexity penalty)? This would show whether the larger gap is fixable or a fundamental data limit, and would help put the 22.5-point ordering loss in perspective.
3 comments
AuthorsOpenReview ↗

Response to Reviewer SGSr (1/3): W1

Thank you for the detailed review.

Main changes for your review: the work of Kitson & Constantinou is now credited, with HC-Stable and Tabu-Stable as baselines on all eleven networks (W1), and GES and BOSS now run under the hill climbers' own score (W2).

We reply in three comments: W1 here, W2–W3 and Q1–Q4 in the second, Q5–Q9 in the third.

W1. Kitson & Constantinou (2024); HC-Stable and Tabu-Stable.

We agree that this was the biggest gap in the submission; both papers should have been discussed. Section 8 and Appendix G (Table 15) now credit them with the finding that variable order changes what hill climbing returns. We test their stable order as a tie rule, include HC-Stable and Tabu-Stable as baselines on all eleven networks, and also ran the authors' released code. The sentence saying that only an outside source can supply the direction is gone.

Beyond their finding, we add three things, measured on a released language-model-guided learner whose scorer and search we replay (Section 2).

First, in this learner the likelihood floor acts before the column order. The residue of the floor decides 59 of the 93 ties that have a truer member before the column order is read, so a causal column order helps little under its score. Under BDeu, where ties are exact, a causal order removes the tie loss on six of ten networks (Appendix F).

Second, we can say where a stable order helps. HC-Stable's order agrees with the causal order on 50% to 74% of the true edges. Under BDeu it helps where that agreement is better than the file order's and hurts where the file is already causal. Six of the eleven bnlearn files list their variables in a causal order, so on those files the plain file order happens to be a good tie rule.

Third, the order effect holds with unlimited data. With population scores a causal order returns the true class in 90% to 91% of tie-dependent faithful networks and the reversed order in 7% to 19% (Appendix A), so the effect they report survives without sampling noise.

You also point out that the HC-Stable paper finds learned graphs that outscore the true graph and are sparser than it. Appendix G now credits this, and we measure the same preference against the truth: between two finished graphs, BIC prefers the sparser one 57.7% of the time, while the sparser one is truer 35.7% of the time by F1 and 55.5% by CPDAG SHD. The misordering that the submission attributed to this preference persists with exact scores and leaves surplus edges (Appendix A), so the revision no longer links the two.

HC-Stable as a baseline. Table 1 reports HC-Stable and Tabu-Stable on all eleven networks under the learner's score. HC-Stable recovers 65% of the tie loss on child and 19% on pigs, and ends further from the truth than greedy on andes (by 10.9 edges). Covered-edge reversal ends significantly closer than HC-Stable on five networks and further on two. Because many files are in causal order, we repeated the comparison under BDeu with each case's columns shuffled (Table 11). There HC-Stable is significantly closer than greedy on six networks and further on none, in line with their paper; covered reversal is closer than HC-Stable on six and further on two. As a check on our implementation: on alarm, the authors' HC-Stable ends 7.22 CPDAG SHD edges further than their own hill climbing, and ours 7.56.

Every implementation we ran depends on the order. Over the file order and ten random column orders, the authors' hill climbing returns 10.3 distinct equivalence classes per case on average, and bnlearn's hc 10.5.

AuthorsOpenReview ↗

Response to Reviewer SGSr (2/3): W2, W3, Q1–Q4

W2. Other searches. Table 1 includes Tabu and random restarts beside greedy on all eleven networks. Tabu recovers 73% of the tie loss on child and ends further from the truth than greedy on pathfinder; restarts recover at most 20%.

We also ran searches over equivalence classes, and the result supports the paper's main point. This is a new experiment (9 and 10 November): GES and BOSS on all eleven networks under the same BDeu score as the hill climbers, so that only the move set differs (Appendix E, Table 8).

The column order matters for greedy and hardly at all for GES. Shuffling the columns moves greedy's CPDAG SHD by 10.2 edges and GES's by at most 0.3 on seven of eight networks. In the published order GES is 2.1 edges closer to the true class than greedy; with the columns shuffled it is 10.1 closer [+8.7, +11.6]. On the four networks whose files happen to list causes before effects, greedy matches or beats GES in the published order and loses that lead once the columns are shuffled. How greedy compares with GES on a benchmark thus depends on how the file was written.

Covered-edge reversal stays within 3.4 edges of GES under shuffled columns. On pigs (441 variables) it ends 8.0 edges from the true class, against 3.2 for GES and 126.7 for greedy.

GES did not finish everywhere. On 8 of 13 pathfinder cases at 5,000 rows, causal-learn's GES must enumerate every subset of 41 to 47 neighbours of one variable, which no machine can store. On andes 26 of 39 runs finished and 13 hit our limit of 60 hours per run, ten of them at 250 rows, where the score prefers denser graphs. On the 26, GES ends 5.3 edges closer than greedy. BOSS finished on both and ended further from the truth than greedy.

You mention that Tabu is reported to be less sensitive to the order. In our runs it moves as much as greedy: across three column shuffles, a case's CPDAG SHD ranges over 14.1 edges for greedy and 16.1 for Tabu, against 6.7 for covered reversal and 1.0 for HC-Stable (Appendix F).

One exception: on win95pts GES also moves with the column order, by 17.1 edges. Its tables produce exact score ties between different pairs of variables, and a search over classes removes only the ties within a class.

W3. Density, numbers without interpretation, two reference ceilings. The abstract and introduction now state the idea with few numbers. Each results section starts with its question and its answer, and each paragraph with its finding, so the argument can be followed from these sentences alone; intervals given in a table are no longer repeated in the prose. The sections still report many numbers, a good part of them added in response to the reviews. Section 3 has a paragraph on the opposite trends of the two metrics on the larger networks (Q3 below). Section 2 defines the two references once (the single-edit reference and the reranking reference), and each share states which one it is measured against.

Q1. Pooling. Every share is a ratio of sums over cases (Appendix L). Appendix D also reports each model as a mean of per-case ratios and as a paired F1 difference. The mean of ratios divides by per-case headrooms as small as 0.011 F1, which is why it moves greedy from 43.5% to 21.2% and gives qwen3-32b-fp8 a nominal lead of 33.4 points, while its paired F1 difference is −0.4 [−4.1, +2.7].

Q2. Quartiles. The quartiles were pooled over sample sizes, which was a mistake. 826 of the 1,027 pairs in the closest quarter came from the 250-row runs, so the pooled cut partly compared sample sizes. Cut within each sample size, the taken edit is the truer one 62.5% of the time in the closest quarter and 82.5% in the farther half, 19.9 points apart [+12.6, +26.5]. Section 3 now reports this cut; Appendix H keeps the pooled figure and explains why it was replaced.

Q3. F1 against CPDAG SHD on hepar2 and win95pts. The two metrics reward different edits: F1 values every true addition alike, while CPDAG SHD rewards the one that also fixes directions. On these two networks the taken edit is the truest accepted edit at 52.7% of steps by F1 and 24.5% by CPDAG SHD. We count only steps with two or more accepted edits, and an edit that ties for truest counts as truest. At 91 of the 298 steps, the taken edit adds a true edge and ties for best F1 with a median of ten other true additions, one of which would also complete a collider and fix 2.1 more CPDAG marks. Section 3 now has a paragraph on this.

Q4. Topological order. Yes. Both files list their variables in a causal order, and at all 80 ties with a truer member on these two networks the first-enumerated member is the truer one. Shuffling the columns raises the open-direction loss from 0.06 to 0.31 edges [+0.11, +0.53]. Appendix F then sets the order by intervention (causal, reversed, shuffled) on ten networks. Appendix H withdraws the submission's reading that ties matter less on larger networks.

AuthorsOpenReview ↗

Response to Reviewer SGSr (3/3): Q5–Q9

Q5. Why no open-weight model beats the score; insurance against child. The submitted statement holds for the sixteen models we served first, and fails for one served later. gemma-4-31B beats greedy with names by 26.1 points [+14.4, +43.5] and loses the lead under pseudonyms. Over 26 open-weight models, the share reached with names grows with model size (Spearman ρ = +0.54, p = 0.009, over the 22 with a published size), and the share under pseudonyms does not (ρ = −0.19). What a model adds comes through the names, and smaller models add less (Appendix M, Figure 9 and Table 23). On the two networks, eleven of the fifteen models in that comparison do better on insurance than on child, and the revision reports the networks separately. We have no controlled explanation for why insurance is easier.

Q6. Run-to-run variation of the frontier models. The relay we use to reach these models returns different answers to the same request at temperature 0, so the paper reports every run. gpt-5.6-sol reaches 97.0% and 84.5% in its two planned runs and 69.0% in a later run made for the ReActBN comparison, 83.5% over the three. The reproducible part of the model study is the open-weight models, served locally from pinned checkpoints. As a check on decoding, we re-ran one of them, Qwen3.8-27B, three times with sampling (Appendix M).

Q7. Larger open-weight models. All five you name now run: DeepSeek-V4-Flash, Llama-3.1-70B, Llama-4-Scout, gemma-4-31B and Qwen3-Next-80B. Size alone does not help: Llama-3.1-70B ends 24.6 points below greedy in the tie role [−42.6, −5.7] and takes the first option shown at 78.5% of ties. Nemotron-3.5-Bolt and Step-3.7-Flash did not load on our serving stack, and the paper lists them as such.

Q8. A truth-free remedy. Section 5 is now built around this, and we consider it the most useful addition in the revision. Covered-edge reversal (Kočka & Castelo, 2001) recovers more than half of the tie loss on six of eleven networks, 94% on andes and 91% on pigs, at 1.1 to 1.3 times greedy's local score evaluations. It recovers nothing on sachs and pathfinder. With 20,000 and 50,000 rows, over all eleven networks and 13 seeds, it recovers 94% and 96% of the tie loss (Appendix F, run on 13 November). It leaves the misordering in place: with exact scores, covered reversal and tie branching both stop short of ranking by the truth (Appendix A). HC-Stable is in the same table. On files already in causal order with a score that ties exactly, covered reversal can undo a correct choice, and Appendix F says so.

Q9. From the reranking reference to the single-edit oracle. From the default start, 54.9% of the oracle's F1 gain comes from edits the score accepts. Appendix C logs every step of the oracle and records what the score does with the edit taken. Of the rest, a smaller complexity term would admit 14.9%, 5,000 rows 3.4%, and dropping the edge penalty 1.3%; 25.5% [19.6, 31.8] is rejected under every setting we tried. From the empty start the accepted share is 80.5% and the always-rejected share 7.3%.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General response to all reviewers

We thank all four reviewers. The question and the contributions are those of the submission; the revision states them more plainly and tests them more widely.

The revision in one sentence: single-edit search meets exact ties that the data cannot break, the implementation breaks them by accident (the column order, a numerical floor), and from the empty start this costs identifiable structure that a move needing no ground truth recovers on the largest networks.

The main changes:

  1. The mechanism comes first. The paper now opens with what every measurement depends on: single-edit search meets exact ties that no observational score can break, and the implementation breaks them by the column order of the data file or by a numerical floor. Each section starts with its question and its answer.
  2. Equivalence classes. Every main result is reported in CPDAG SHD as well as F1, and the tie claims are stated in CPDAG SHD. This narrowed one claim: the identifiable tie loss is specific to searches that start from the empty graph.
  3. Scale and alternatives. Eleven networks of up to 441 variables; Tabu, restarts, HC-Stable, GES and BOSS under the same score; a remedy that needs no ground truth; and population scores, which remove sampling noise.
  4. What a language model knows. On two networks written after the models were trained, we separate recall of the benchmark from the meaning of the variable names.

Appendix H lists every change, including the readings of the submission we withdraw. The two most important withdrawn readings are that the rest of the loss comes from BIC's preference for sparse graphs, and that ties matter less on larger networks.

The idea. If A and B have the same parents, adding A→B and adding B→A give Markov-equivalent graphs (Proposition 1), so the data cannot choose the direction and something else does. From the empty graph this choice is made before the collider that would settle it exists, and later edges are built on top of it. Appendix A works through a three-variable collider with the exact distribution: one column order returns the true graph, another returns a graph that is wrong at every pair of variables.

Main results.

  1. Ties matter even with unlimited data. Under population scores the tie choices alone decide the returned class in 166 of 199 faithful five-variable networks, and breaking ties by a causal order returns the true class in 90% to 91% of them (Appendix A).
  2. On the benchmarks the loss grows with network size. Resolving ties by the truth removes up to 59% of greedy's CPDAG SHD (pigs, 441 variables). Covered-edge reversal, which uses no ground truth, recovers 94% of that loss on andes and 91% on pigs (Table 1).
  3. A language model helps through the variable names. With names, gpt-5.6-sol reaches 83.5% of the reranking reference over three runs; with the variables renamed it ends 47.1 points below greedy (Section 7).

New experiments run during the discussion (9 to 17 November).

  • GES under the hill climbers' own score (SGSr): GES barely reacts to the column order, while shuffling the columns moves greedy by 10.2 CPDAG SHD edges (Appendix E).
  • Networks no model has seen (VgA6): with the real names gpt-5.6-sol is right at 94.7% of ties; with the variables renamed, at 50.5% (Appendix M.4).
  • A second provider (VgA6), run on 17 November: two Google models, gemini-4-carbon and gemini-4-argon, are right at 97.4% and 98.7% of the greenhouse ties with names and at about half renamed, and repeat every reading on a second network and on child and insurance (Appendix M.4).
  • The remaining loss (SGSr, iQb6, VgA6): with exact scores it is still 18% of the ordering loss, and at 50,000 rows still 20% of greedy's error. It comes from the order in which single-edit search takes edits, and it leaves surplus edges (Appendix A).

Limitations. The identifiable tie loss is a finding about the empty start; from the learner's default start, ties cost almost only directions the data leave open (Appendix K). All data are sampled from benchmark networks except Sachs et al.'s, where resolving ties changes almost nothing (Appendix I). The new-network result rests on two networks we wrote; it holds for four models from two providers (Appendix M.4).

The supplement contains the scripts, the result files and a checker that recomputes the revision's new numbers from them.

Area_Chair_pqqzOpenReview ↗

Discussion

Dear reviewers,

if you want further questions answered, the time to ask is now. The forum will close to the authors on November 18, 2026: https://iclr.cc/Conferences/2027/Dates

Robust discussion is an important part of the review process!

Sincerely Your AC

AuthorsOpenReview ↗

Before the response period closes

Dear reviewers, thank you again for your reviews. The author response period closes in a few hours. Our replies above and the revised PDF address each point you raised; if any concern remains, we would be glad to answer it before the deadline.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.