Auditing Memorized Causal Graphs with Held-Out Prediction

Language models are increasingly asked to propose causal graphs: diagrams saying which variables directly influence which. The standard way to score those proposals is to compare them with a published "true" graph from a public benchmark. The trouble is that the best-known benchmark graphs, such as the Bayesian networks in the bnlearn repository, have been printed in textbooks and papers for decades. A model can reproduce them from memory without reading the data at all. CausalGraphBench confirms this: several models had prior exposure to these graphs, and on small graphs that exposure makes their scores look significantly better. When the answer key has leaked, scoring against the answer key cannot tell recall apart from inference.

We propose scoring proposed graphs against the data instead of the answer key. Out-of-sample causal tuning (OCT) is a method for choosing among causal discovery settings without knowing the true graph. For each variable, you read off its Markov blanket from the candidate graph (its parents, its children, and its children's other parents). You then train a predictor of that variable from its blanket on some data folds and measure the prediction error on held-out folds. A correctly shaped graph gives the smallest blanket that still predicts well. This score depends only on the observed data, so memorizing a published diagram cannot improve it. We pair it with a stress test that is new here. We make small, deliberate edits to benchmark graphs, sample fresh data from the edited versions, and check whether a model's proposed graph follows the data or follows the textbook.

Core Claim

We claim two things. First, held-out Markov-blanket loss can tell graphs that fit the observed data apart from graphs recalled from memory, and it can do so without the true graph and without access to the model's internals. Second, "structurally edited" benchmarks turn that ability into a measurable contamination audit for causal discovery. This is the structural counterpart of ConStat, which detects contamination in question-answering benchmarks by rephrasing questions and measuring how much the score drops. ConStat rephrases text. We rewrite the causal mechanism that generates the data and keep the variable names the same. A model that memorized the published graph will keep producing the canonical edges. OCT on the edited data will then charge it a predictive penalty, and that penalty can be computed in deployment, where no answer key exists.

This differs from the closest work in three ways. CausalGraphBench detects contamination but still ranks graphs only by Structural Hamming Distance (SHD), the number of edge insertions, deletions and reversals needed to turn one graph into another, measured against the possibly leaked truth. LLM Cannot Discover Causality argues that language models should only guide the search and that data-driven scores should make the final call. It uses in-sample scores (the Bayesian Information Criterion, BIC, and the Bayesian Dirichlet score, BDeu), and it never asks whether its bnlearn test graphs were memorized. Unveiling Causal Reasoning in LLMs avoids contamination by gathering text published after the model's training cutoff. That protection wears off once the new text is published and scraped, and it applies to question answering, not to graphs estimated from data.

Research Program

The first component is an edited-benchmark generator. We start from the bnlearn networks, from the 8-node Asia network up to the 221-node Andes network, and from the 21 paper-extracted graphs in CausalGraphBench. For each graph we apply edits that change at least one variable's Markov blanket: removing an edge, adding an edge, or creating or breaking a collider (a node with two parents that are not linked to each other). We fit conditional probability tables or nonlinear mechanisms to the edited graph and sample data from it. We also make mixed-type and nonlinear resimulations, in the style of the OCT papers.

We restrict edits to changes that alter Markov blankets for a principled reason. OCT sees only conditional-independence structure, so an edit that only reverses an edge inside the same Markov equivalence class is invisible to it. We report memorization of orientation alone as a limitation, not a success.

The main confound is semantic implausibility. An edit such as "lung cancer causes smoking" would be rejected by a model with correct domain knowledge, and that rejection would look like memorization even though it is not. To control for this, independent annotators rate each edit's plausibility given only the variable names, and we analyze the plausible-edit and implausible-edit strata separately.

The second component applies OCT, following Tuning Causal Discovery Algorithms and Out-of-Sample Tuning for Causal Discovery. For every candidate graph we compute the held-out Markov-blanket prediction loss. Among candidates whose losses are statistically indistinguishable, we apply the OCT sparsity rule and prefer the graph with smaller blankets. The candidates are language-model graphs, data-driven graphs from PC and FGES (constraint-based and score-based search) over a grid of settings, and hybrid graphs in which the language model only initializes the search, as in LLM Cannot Discover Causality. We implement all of this inside the ETIA pipeline (ETIA).

Cost is manageable because the audit scores each graph once. It does not tune over dozens of settings. The reported cost of 73 minutes for 51 settings on a 10-node graph therefore bounds the grid search, not the audit itself.

The third component defines a memorization gap for each model and network. It is the difference in held-out Markov-blanket loss between the model's graph and the OCT-selected data-driven graph, measured once on edited data and once on unedited data. A model that reads the data should have similar gaps on both. A model that recites the textbook should have a small gap on unedited data and a large one on edited data.

Baselines

The first reference point is the language model's graph scored by normalized SHD against the published truth, which is current practice. On CausalGraphBench graphs of up to 10 nodes, GPT-4o with a single prompt reaches a normalized SHD of 0.65 and the fine-tuned variant reaches 0.64 (CausalGraphBench). We rerun these prompting strategies ourselves on unedited and edited graphs, using the same models and prompts.

The strongest competitor for data-grounded scoring is an in-sample score: BIC or BDeu, as used for final selection in LLM Cannot Discover Causality, plus stability selection with StARS. On discrete bnlearn data, BDeu is well matched to the model class, so it is a serious threat. We compute every score on the same samples and the same candidate graphs. We give the in-sample scores the full data where OCT uses folds, which favors them. The file contains no reported number for BIC or BDeu on edited bnlearn data, and the OCT papers do not report SHD or SID values in the material we have. For that reason we treat both as measured quantities rather than quoted targets.

The strongest existing black-box contamination detector is Min-K% Prob, which checks whether a model assigns unusually high confidence to a text's least likely tokens. We apply it to textual descriptions of each network, as CausalProbe-2024 does for its news text. No reported result was found on Lacuna for Min-K% applied to causal-graph descriptions.

Two ablations isolate what drives the audit. The first replaces held-out loss with in-sample loss on the same blankets, which tests whether data splitting matters. The second removes the sparsity rule. OCT beats the alternatives if its score ranks candidate graphs by SHD to the edited truth with higher rank correlation than BDeu, BIC and StARS, especially on the mixed and nonlinear resimulations, and if its memorization gap separates contaminated models from clean ones with a higher area under the ROC curve (AUROC) than Min-K%.

Why not just…?

Why not just use BIC or BDeu? This is the real threat. On purely discrete networks with enough samples, an in-sample score may penalize memorized edges just as well as OCT. The OCT papers argue that such scores depend on parametric assumptions and cannot be computed for graphs with hidden variables, the setting of the FCI algorithm. The mixed, nonlinear and hidden-variable resimulations test exactly that claim. If BDeu matches OCT everywhere, the contribution shrinks to the edited-benchmark protocol plus any data-grounded score, and we will say so.

Why not just rename the variables? Anonymizing variables removes contamination, but it also removes legitimate domain knowledge. The resulting test measures something different: inference from data alone, not whether the model's knowledge has been corrupted by memorization. Edits with plausibility ratings keep the variable names and separate the two effects. We also run anonymized graphs as a side condition so the two protocols can be compared.

Why not just use Min-K% or n-gram checks? These methods detect exposure, not harm. DICE reports that perplexity-style detectors perform "no better than a coin flip" against paraphrased contamination. They also cannot say whether a particular graph fits the data at hand. The planted-contamination experiment below compares them head to head.

Why not just use fresh graphs? Fresh graphs lose their protection once they are published. They also still need a trusted answer key, which is exactly what is missing when these tools are used on real data.

Proposed Experiments

Planted contamination. We fine-tune small open models on descriptions of either the canonical graphs or the edited graphs, at contamination rates similar to those in the DICE and CANARY setups. This gives known contamination labels. We then measure the memorization-gap AUROC against Min-K%. As an upper reference that requires access to model internals, we cite CANARY's AUROC of 1.000 at 1% contamination and its AUROC of about 0.83 under low-rank (LoRA r=4) fine-tuning (CANARY). Our method uses no internals.

Frontier models. We apply the audit to closed frontier models on the bnlearn and CausalGraphBench graphs. We report SHD against the canonical graph versus SHD against the edited graph, stratified by edit plausibility and by graph size. The size stratification matters because CausalGraphBench found that contamination affected small graphs far more than large ones.

Selection. We test whether choosing by OCT among language-model, data-driven and hybrid graphs lowers SHD and SID (Structural Intervention Distance, which counts how many interventional predictions a graph gets wrong) to the edited truth, compared with choosing by BDeu or by the model's own stated preference.

The decisive check. On plausible edits, a model with a low SHD to the canonical graph should also show a large OCT memorization gap, and OCT's graph ranking should track SHD to the edited truth, not SHD to the published graph. If both hold, a score computed without any answer key has caught memorization that SHD against the leaked answer key rewarded.