Catching Wrong Causal Graphs with a Replaced-Value Detector

When a causal discovery algorithm returns a graph for real data, there is usually no true graph to compare it against. We propose to check such graphs with the training trick behind ELECTRA. In ELECTRA, a small model replaces some words in a sentence and a second model learns to spot which words were replaced. In our version, each candidate causal graph defines a way of faking table entries. To fake the value of a variable, we resample it using only the variables the graph says it depends on, which is its Markov boundary: parents, children, and co-parents of children. A single detector, trained once on the dataset, then tries to tell fake cells from real ones. If the graph is right, the faked values are statistically indistinguishable from real ones, because the variable really is independent of everything else given that set. If the graph drops a true dependency, the fakes break a relationship that the detector, which sees the whole row, can notice. How easily the detector spots a graph's fakes becomes a label-free score of how wrong the graph is.

This matters because current label-free validators are either slow or easy to fool. Out-of-sample causal tuning fits a separate predictor for every variable, fold and candidate graph, which took about 73 minutes for 51 configurations on a 10-node graph (Out-of-Sample Tuning for Causal Discovery). Consistency checks across variable subsets can be passed by an empty graph (Self-compatibility: Evaluating causal discovery without ground truth). A shared detector covers every variable in a single forward pass, and it punishes the empty graph harshly, since the empty graph's fakes ignore every dependency.

Core Claim

Replaced token detection, which here means training a classifier to label every position of a corrupted input as original or replaced, can be turned from a pretraining objective into a model-checking instrument for causal graphs. The key design choice is where the corruptions come from. We use one masked-cell generator for tabular rows, trained with random context masks so it can condition on any subset of columns. A candidate graph $G$ is then imposed purely as an attention mask: when generating cell $i$, the generator may only look at the Markov boundary of $i$ in $G$. The detector is trained against the unrestricted generator and then frozen. For each graph we measure excess detectability:

$$ S(G) = \mathrm{AUROC}_D(\text{cells resampled given } \mathrm{MB}_G) - \mathrm{AUROC}_D(\text{cells resampled given all other columns}). $$

Here $D$ is the frozen detector, and AUROC is its accuracy at ranking replaced cells above original ones on held-out rows. The subtracted term is a floor. It measures how detectable the generator's own imperfections are, and it is exactly the artifact that ELECTRA warned discriminators spend capacity on (ELECTRA: Pre-training Text Encoders as Discriminators Rather Than Generators). Near-zero $S(G)$ means that $G$'s claimed conditional independences survive a powerful whole-row adversary. Large $S(G)$ means some dependency the graph omits is real. Per-cell scores also localize the failure to specific variables.

The score has one blind spot that we will not hide. Any supergraph of the true graph also yields undetectable fakes, and Markov-equivalent graphs are identical under observational data. The procedure therefore validates the conditional-independence content of a graph, not its edge directions. It must be paired with a minimality rule: among graphs whose $S$ is statistically indistinguishable from the best, choose the sparsest. This is the same remedy that OCT uses for dense graphs inflating its predictive score. Edge orientation can only be probed with interventional data, which we treat as an extension below.

Relation to Prior Work

Two lines of work motivate the proposal. The first is Markov-boundary validation. OCT (Out-of-Sample Tuning for Causal Discovery; Tuning Causal Discovery Algorithms) tests a graph by how well each variable is predicted from its implied Markov boundary. It measures predictive information, so it can miss graphs that get the conditional mean right but the conditional shape wrong, and it retrains per node. Our detector compares whole conditional distributions and is shared across nodes and graphs.

The second is subset invariance. Self-compatibility (Self-compatibility: Evaluating causal discovery without ground truth) and Leave-One-Variable-Out (Cross-validating causal discovery via Leave-One-Variable-Out) test whether a discovery algorithm is stable across variable subsets. LOVO must abstain when the hidden pair is a collider. Our test needs no omitted joint data and scores the graph itself rather than the algorithm's behaviour, so it has no collider abstention.

TabStruct (TabStruct: Measuring Structural Fidelity of Tabular Data) supplies both a benchmark and a caution. Its Global Utility predicts every column from all others to score synthetic data. It also found that imposing a column order hurts autoregressive generators, which is why our generator and detector are order-free, bidirectional models over cells.

The closest neural work is a different kind of project. Causal Discovery and Inference through Next-Token Prediction trains a GPT on symbolic strings from 4-variable linear Gaussian models with known graphs. A Causal World Model Underlying Next Token Prediction in GPT reads conditional independences out of attention in an Othello model, with code in IntelLabs/causality-lab. Both ask whether a network learns causal structure internally. We do not ask the network to know the graph at all. We use it as an adversary against externally proposed graphs.

Causal-JEPA: Learning World Models through Object-Level Latent Masking frames masking an object's history as a latent intervention, but it trains a world model and outputs no graph. The prompt-based use of a detector's "is this original?" probability in Pre-trained Token-replaced Detection Model as Few-shot Learner is the methodological precedent for reading a frozen detector's per-position scores as a judgment. Its sensitivity to how candidates are phrased is a warning that our floor term must be estimated carefully.

Research Program

We will build a cell-level transformer for tables. Each cell is a token formed from a column-identity embedding plus a value embedding, with continuous values handled through a learned quantile-bin embedding. The generator is a masked-cell model, kept smaller than the detector following ELECTRA's finding that generators near a quarter to half the detector's size work best. It is trained with random context masks so that it can later be restricted to any Markov boundary. The detector labels all cells of each corrupted row. Unlike ELECTRA, a fraction of its training corruptions come from generators with randomly restricted context. This teaches it to catch omitted-dependency fakes, and it does so without ever seeing a candidate graph.

At evaluation, each candidate graph costs only masked sampling plus one detector pass over held-out rows. We will calibrate $S(G)$ with a permutation null: rescore after resampling the same cells from the unrestricted generator. This yields a p-value per graph and per variable. Per the negative-controls argument of Are You Doing Better Than Random Guessing? A Call for Using Negative Controls When Evaluating Causal Discovery Algorithms, we will also score random graphs of matched density.

The analysis will cover three things. We will measure how $S$ degrades with nonlinearity, discreteness and hidden confounders, where the Markov boundary of a maximal ancestral graph replaces that of a DAG. We will measure how sample size limits the detector's power. And we will measure whether localized per-variable scores point to the true missing edges.

Baselines

The naive reference points are two random scorers: one that ranks graphs at random, and one that ranks them by edge count, since sparsity alone correlates with SHD on some suites. Negative-control random graphs at matched density give the null distribution for every method, following Are You Doing Better Than Random Guessing?.

The strongest competitor on graph ranking under sample scarcity is LOVO, and it is the only method in the file with a reported number in a setting we can reproduce. It reports Spearman correlation between LOVO error and true structural Hamming distance (SHD) of 0.72 for DirectLiNGAM and 0.75 for RCD on 10-node random graphs (Cross-validating causal discovery via Leave-One-Variable-Out). We will regenerate that suite with the same generator settings and algorithms and report the same statistic. Beating it means a Spearman above 0.75 for RCD graphs with overlapping bootstrap intervals excluded, and it must hold without LOVO's collider abstentions. Self-compatibility reports Pearson 0.52 with SHD for RCD and correct selection of the better sensitivity threshold in 72–76% of cases (Self-compatibility: Evaluating causal discovery without ground truth). We will report the matching statistics on its setup.

OCT is the closest method conceptually. For its accuracy we found no reported result on Lacuna beyond runtime, 73 minutes for 51 configurations on 10 nodes versus 25 for StARS. We will therefore run it ourselves on its synthetic suite with random-forest predictors and its sparsity rule, and compare tuning accuracy and wall-clock time on identical hardware. Every learned component, including OCT's forests and our transformers, gets the same hyperparameter search budget, and all methods see the same training and holdout rows.

A key ablation isolates the replaced-value detector. It replaces our detector with a per-column gradient-boosted classifier trained to separate real cells from MB-conditioned fakes, retrained per graph, using the same generator. A second ablation keeps the shared detector but uses a naive corruptor, independent marginal resampling in place of Markov-boundary conditioning. This tests whether graph-constrained plausibility, the ELECTRA insight, carries the signal.

Why not just…?

Why not just use OCT's Markov-boundary predictive score? In the limit of infinite data and flexible predictors, both methods test the same conditional independences, so OCT is a real threat on accuracy. Our bet has two parts. First, a distributional adversary catches conditional misspecification that a mean predictor measured by mutual information handles only indirectly. Second, amortization removes the per-node, per-fold retraining that makes OCT slow. The OCT-suite comparison settles both. If OCT matches us on tuning accuracy in the nonlinear and mixed regimes, then our contribution reduces to speed, and we will say so.

Why not just apply TabStruct's Global Utility to data sampled from each candidate graph? Global Utility scores synthetic data, so one could fit a model to each graph, sample, and score. But it needs a full generative fit and ensemble training per graph, and it reports one scalar with no localization. Its reported Spearman of 0.84 (TabStruct) correlates generators with structural fidelity, not candidate graphs with SHD, so the numbers are not comparable. We will run this construction as an additional baseline on TabStruct's SCM datasets (Hailfinder, Insurance).

Why not just use a per-column classifier two-sample test instead of a pretrained detector? This is the most dangerous alternative, because it keeps our core idea of graph-constrained fakes and drops the RTD machinery. It is exactly our first ablation. If it matches the shared detector on correlation with SHD, then the shared detector's only claim is cost, which we measure. We expect the shared detector to win at small sample sizes and larger graphs, where per-column classifiers retrained per graph overfit and scale poorly. Both OCT and TabStruct report degradation beyond roughly ten variables.

Proposed Experiments

The decisive synthetic check uses 10-node random DAGs and graphs with bidirected confounding, following LOVO. It covers linear Gaussian, discrete, conditional-Gaussian mixed, and nonlinear non-Gaussian regimes as in OCT. For each dataset we score every graph produced by PC, GES, DirectLiNGAM and RCD across their hyperparameter grids. Metrics are Spearman correlation of $S$ with SHD, the fraction of pairwise hyperparameter comparisons won, and wall-clock time. We then scale to the larger expert graphs in TabStruct's SCM benchmarks to test the dimensionality claim directly.

On real data, we use Sachs with its consensus graph. There, PC was the only tested algorithm clearly separated from random guessing (SHD p = 0.001) while GES and BOSS were not (Are You Doing Better Than Random Guessing?). A credible validator should reproduce that ordering without seeing the consensus graph. We also use the static, non-time-series configurations of the Causal Chambers (Causal chambers as a real-world physical testbed for AI methodology), whose physically derived graphs include the nonlinear polarizer effects that defeated GES and UT-IGSP. We deliberately leave aside the time-series benchmarks CausalRivers and TCD-Arena in the first phase, because their lagged structure requires a different notion of Markov boundary.

The interventional extension also uses the chambers, which log their interventions. The generator is conditioned on an intervention token and restricted by the mutilated graph. This asks whether the detector can separate Markov-equivalent graphs that the observational score cannot.

The proposal fails if $S$ does not beat the per-column ablation or LOVO's reported 0.75 on its own suite. It also fails if its ranking on Sachs contradicts the negative-control ordering.