Bayesian Network Structure Discovery Using Large Language Models

AI summary

Overview

Research area: Machine learning / probabilistic graphical models — specifically Bayesian network (BN) structure learning combined with large language model (LLM) reasoning.

Technical level: Advanced. The paper assumes familiarity with directed acyclic graphs (DAGs), constraint-based and score-based structure learning (PC, Hill Climbing, GES), scoring criteria such as the Bayesian Information Criterion (BIC), and evaluation metrics such as Structural Hamming Distance (SHD) and Normalized Hamming Distance (NHD).

Scope (one sentence): The paper introduces a two-phase, LLM-centered framework — PromptBN for data-free DAG generation and ReActBN for data-aware refinement — and evaluates it against LLM-only, data-only, and hybrid structure learning baselines on ten Bayesian network datasets.

Links reported in the paper: code at https://github.com/sherryzyh/llmbn; reviewed on OpenReview at https://openreview.net/forum?id=G4mrO8LVix. arXiv identifier arXiv:2511.00574v2 [cs.LG].

What This Paper Is About

Learning the dependency structure among variables in a complex system means recovering a directed acyclic graph, and traditional methods either need large amounts of observational data or rely on expert knowledge that must be entered by hand, which is labor-intensive and error-prone. Prior work that uses LLMs for this task treats the model as an auxiliary tool for pre-processing or post-processing, leaving the core learning process data-driven. This paper instead places the LLM at the center, supporting both a data-free setting (PromptBN) and a data-aware refinement setting (ReActBN) inside one unified framework.

Key Contributions

1. A unified LLM-based framework for flexible Bayesian network structure discovery that works with or without observational data.
2. PromptBN, a meta-prompting approach that elicits a complete directed acyclic graph in a single LLM inference, achieving constant O(1) query complexity and using dual validation (structural consistency across two output representations, and DAG acyclicity checking) to enforce global consistency.
3. ReActBN, a novel agentic search framework that refines the initial structure by integrating Reason-and-Act (ReAct) LLM reasoning with configurable structure scores such as BIC, where the LLM selects among top-k candidate actions while a tabu list prevents cycling.
4. Extensive experiments across diverse datasets showing superior structure discovery over state-of-the-art methods, with contamination tests indicating that observed gains arise from reasoning rather than memorization, plus complexity analyses demonstrating scalability to large, complex graphs.

Main Findings

• PromptBN is the strongest LLM-only method (no data). It achieves exact recovery on Asia (SHD = 0.0, NHD = 0.000), near-exact recovery on Cancer (SHD = 0.6, NHD = 0.024), the top LLM-only result on Insurance (SHD = 35.6, NHD = 0.044), and SHD 41.8 on Alarm, 76.8 on Hailfinder, 15.2 on blockchain, 45.0 on covid, and 15.6 on disputed3. On covid this compares with PairwisePrompt (82.6) and BFSPrompt (74.6).

• PromptBN improves downstream data-driven search. PromptBN+HC uses the LLM graph as initialization for hill climbing instead of an empty graph; on Hailfinder this reduces SHD from 72 (HC alone) to 63.8.

• ReActBN is the strongest overall in the data-aware setting. It exactly recovers Cancer (SHD = 0.0), attains the best results on 6 out of 9 datasets, and reports SHD values of 6.4 (Asia), 18.0 (Child), 40.2 (Insurance), 35.4 (Alarm), 75.0 (Hailfinder), 11.0 (blockchain), 32.8 (covid), and 12.2 (disputed3). On Insurance it outperforms all baselines with an SHD of 40.2.

• Strong out-of-distribution generalization. On three newer BNRep networks (blockchain, covid, disputed3) that are less likely to appear in pre-training corpora, PromptBN gives the best data-free results and ReActBN gives the best data-aware results on two of the three networks (blockchain and disputed3).

• Gains come from reasoning, not memorization. In three controlled contamination tests — supplying only variable names (VarName), only variable descriptions (VarDescription), or full metadata in randomly permuted order (ScrambleOrder) — restricted inputs degraded sharply: Child (SHD 27.3–31.3), Insurance (41.3–44.3), Alarm (43.8), and Hailfinder (118.7–119.8). Under ScrambleOrder, performance stayed close to full PromptBN, e.g. Child (24.8 vs. 21.6) and Insurance (37.4 vs. 35.6), indicating that the method does not depend on memorized ordering.

• More data narrows the gap. Comparing 100 versus 250 observational samples across HC, PromptBN+HC, and ReActBN, ReActBN was best in both regimes, but conventional data-only methods improve as sample size grows — expected, since reliance on LLM priors naturally decreases when sufficient data is available. On Child at 250 samples, ReActBN reached SHD 12.6 versus 13.2 for PromptBN+HC and 17 for HC.

• Results vary by LLM choice. PromptBN was evaluated across o3-pro, o3, o4-mini, gpt-4.1, gpt-4o, Deepseek-r1, Deepseek-v3, gemini-2.5-pro, and gemini-2.0-flash. Model choice materially changes SHD on several networks; Deepseek-v3 produced unparsable output ("UnP") on Insurance, failing to follow the required output format.

• Query complexity is the key efficiency advantage. PromptBN achieves O(1) query complexity by generating the whole DAG in a single invocation, versus O(N²) for PairwisePrompt, O(N) for BFSPrompt, and O(N²·2^k) for ChatPC. ReActBN achieves O(1) queries per iteration with overall runtime O(N²), compared with LLM-CD(HC) costing O(N) for metadata derivation plus up to O(N²) validation queries.

• Qualitative results on Earthquake. No quantitative results were available for comparison on Earthquake, so the authors visualize the learned structure instead; ChatPC likewise reports only qualitative evaluations. PromptBN produced structures that exactly match the ground truth on Asia and Cancer.

Methodology in Plain English

The authors split the problem into two phases.

Phase 1 (PromptBN): The LLM is given only metadata about the variables — names, descriptions, and distributions — and is asked in a single prompt to output the entire graph. The prompt is a "meta-prompt": it specifies not just the task but the reasoning protocol, the response structure, and the output constraints. The model must answer in two complementary formats, one listing parents for each variable and one listing edges as "from-to" pairs. Two checks then run: a structural consistency check (do the two formats agree?) and a DAG constraint check (is the graph acyclic?). If either fails, the LLM regenerates until validation passes or a retry limit is hit.

Phase 2 (ReActBN): When observational data exist, the initial graph is refined iteratively. At each step the method enumerates all valid neighboring graphs, scores each one with a configurable criterion (BIC in this work), and computes the score difference from the current graph. The top-k candidates, along with the current graph, its score, and a tabu list of already-visited structures, are passed to the LLM. Unlike greedy algorithms that always pick the single highest-scoring move, the LLM reasons over the candidates and chooses an action (or terminates), returning an explicit reasoning trace and a confidence estimate.

Experimental protocol: Seven classical benchmarks came from Bnlearn (Asia, Cancer, Earthquake, Child, Insurance, Alarm, Hailfinder) and three newer ones from BnRep (blockchain, consequenceCovid referred to as covid, and disputed3). Baselines were grouped into LLM-only (PairwisePrompt, BFSPrompt, Scalability, ChatPC), data-only (PC-Stable, HC, GES, plus low-data methods RAI-BF, rI^eB, rBF_chi2), and hybrid (LLM-CD(HC), PairwisePrompt+Data, BFSPrompt+Data). Unless stated otherwise, 100 observational samples were used, following Cui et al. (2022a). PromptBN used o3-2025-04-16 and ReActBN used gpt-4.1-2025-04-14 via the OpenAI API. Because LLMs are stochastic, results are reported over five valid runs, where a valid run completes and produces a graph passing the dual-validation checks; runs continued until five valid runs were collected or five consecutive invalid runs occurred.

Why This Matters

Impact on research: The paper reframes LLMs from auxiliary helpers into the central decision-maker for graphical model structure discovery, and it provides an efficiency argument in terms of LLM query complexity rather than only accuracy. It also supplies evidence — through contamination tests — that reported accuracy reflects relational reasoning rather than recall of memorized graphs, which is a recurring concern for LLM-based scientific inference. Its O(1) query complexity makes it competitive in settings where API cost or latency, not data volume, is the binding constraint.

Real-world applications (these follow from the domains the paper's benchmarks model; the paper itself does not enumerate application areas):

• Medical and clinical reasoning, where the Cancer and Asia networks stand in for diagnostic dependency structure among symptoms, risk factors, and diseases.
• Monitoring and alarm systems, where the Alarm network represents sensor and fault dependencies in industrial or medical monitoring.
• Environmental and meteorological modeling, illustrated by Hailfinder.
• Emerging technical and policy domains, represented by the newer blockchain, covid, and disputed3 networks, where little observational data exist but textual documentation about the variables is plentiful.

Industry relevance: The practical claim is that a system can produce a usable dependency graph from documentation alone — no logged data — and then improve that graph once modest data becomes available. That two-stage behavior suits organizations that need structured causal hypotheses early and only later accumulate enough samples for statistical estimation, and the O(1) query complexity keeps LLM API costs flat as the number of variables grows.

Future Directions

Note: the provided paper content is truncated at the factor-analysis section, so the authors' own stated future work is not included here. The following open questions follow directly from what is reported.

1. Extending beyond fixed refinement budgets. ReActBN's query complexity of O(1) per iteration depends on the number of refinement iterations being fixed, following standard Hill Climbing practice; whether allowing more iterations on large graphs such as Hailfinder or Insurance yields better structures without losing query efficiency is untested here.
2. Output-format robustness across models. Deepseek-v3 returned unparsable output on Insurance, showing that the dual-validation and retry mechanism does not guarantee a valid structure for every model; a systematic study of which model families fail, and whether the prompt can be made format-agnostic, is a natural next step.
3. Tighter characterization of the data-versus-priors trade-off. The paper shows that data-only methods close the gap with ReActBN as samples grow from 100 to 250, but does not report the crossover point or behavior at other sample sizes.
4. Scaling to genuinely large networks. The complexity analysis is largely theoretical — ChatPC is argued to be unsuitable for moderate or large graphs — while the largest datasets used here (Hailfinder at SHD 76.8 for PromptBN, web-scale networks are not evaluated) leave empirical scaling behavior on very large graphs open.

Target Audience

This paper is most useful to researchers and practitioners working on causal discovery, Bayesian network structure learning, and probabilistic graphical models who are evaluating whether LLMs can replace or augment classical constraint-based and score-based algorithms. It also speaks to applied machine learning engineers building pipelines where observational data are scarce but textual metadata are abundant, and to researchers interested in contamination testing and query-complexity accounting for LLM-based scientific methods. Readers without background in DAGs, structure learning metrics, or scoring functions such as BIC will find the quantitative sections difficult, since results are reported almost entirely in SHD and NHD terms across nine tabulated benchmarks.

Authors’ abstract

Understanding probabilistic dependencies among variables is central to analyzing complex systems. Traditional structure learning methods often require extensive observational data or are limited by manual, error-prone incorporation of expert knowledge. Recent studies have explored using large language models (LLMs) for structure learning, but most treat LLMs as auxiliary tools for pre-processing or post-processing, leaving the core learning process data-driven. In this work, we introduce a unified framework for Bayesian network structure discovery that places LLMs at the center, supporting both data-free and data-aware settings. In the data-free regime, we introduce \textbf{PromptBN}, which leverages LLM reasoning over variable metadata to generate a complete directed acyclic graph (DAG) in a single call. PromptBN effectively enforces global consistency and acyclicity through dual validation, achieving constant $\mathcal{O}(1)$ query complexity. When observational data are available, we introduce \textbf{ReActBN} to further refine the initial graph. ReActBN combines statistical evidence with LLM by integrating a novel ReAct-style reasoning with configurable structure scores (e.g., Bayesian Information Criterion). Experiments demonstrate that our method outperforms prior data-only, LLM-only, and hybrid baselines, particularly in low- or no-data regimes and on out-of-distribution datasets. Code is available at https://github.com/sherryzyh/llmbn.