Externalized CPDAG Summaries Improve LLM Causal Deduction

Conference: NeurIPS2026
arXiv: 2609.31071
Code: https://anonymous.4open.science/r/cpdag-llm-reasoning-B48A
Area: LLM Reasoning
Keywords: causal deduction, CPDAG, Markov equivalence class, constrained decoding, structured intermediate state

TL;DR

Structured Thinking asks the same large language model to produce a format-constrained CPDAG summary before checking whether a causal hypothesis holds in every compatible DAG, raising Qwen3.5-27B primary-seed F1(YES) on Corr2Cause from 73.01 to 86.36 without formally guaranteeing graph validity or reasoning over the entire equivalence class.

Background & Motivation

Corr2Cause provides correlations and conditional independencies between variables and asks whether a causal hypothesis follows. Finding a plausible causal story is insufficient: observational information generally identifies a Markov equivalence class whose DAGs share the same conditional independencies. Consequently, “some compatible graph supports the hypothesis” and “every compatible graph supports it” are different decision criteria. The latter requires retaining the skeleton, separating sets, collider structures, and unresolved directions, rather than drawing a conclusion from a local path.

Free-form chain-of-thought can entangle these facts in prose. A model may mistake correlation for direct adjacency, arbitrarily orient an undirected edge, or stop after finding one DAG that supports the hypothesis. This paper does not merely add PC instructions to a model with no causal-discovery guidance and compare it with ordinary question answering: the principal baseline already explicitly requests skeleton construction, collider identification, forced-orientation propagation, and an equivalence-class check. The further question is whether an implicit graph state remains a bottleneck even with algorithmic guidance. If the label depends on that graph, it should first become an inspectable intermediate that can be intervened on.

A completed partially directed acyclic graph, or CPDAG, represents this object: directed edges carry orientations compelled across the equivalence class, while undirected edges retain genuine ambiguity. Recording these facts in fixed fields, rather than adding more prose, permits direct downstream queries and separates graph-construction errors from graph-readout errors. Core Idea: externalize the CPDAG summary that defines the label, constrain its output format, and make the final decision query that graph state over all compatible graphs instead of reconstructing another causal story from prose.

Method

Overall Architecture

The input comprises correlation/conditional-independence premises and a causal hypothesis; the output is YES or NO. The method is a two-turn inference-time conversation: Turn 1 organizes graph construction with a “PC scaffold” and records it as a “Constrained graph summary”; Turn 2 performs an “All-completions query” after returning that summary to the same model. No external PC algorithm, symbolic causal solver, or newly trained verifier automatically executes these steps: the LLM still constructs the graph and judges the hypothesis.

Turn 1 emits a CausalAnalysis object rather than one unique causal DAG. Turn 2 receives its fields and a compact DOT representation, while retaining the original premise and hypothesis by default. The graph is therefore a decision anchor, not the only information source. Every arrow in the diagram represents inference-time data flow; reference CPDAGs and labels are used only for offline evaluation, do not enter this pipeline, and do not form a training-supervision branch.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Correlation and CI premises<br/>Causal hypothesis"] --> B["PC scaffold"]
    B --> C["Constrained graph summary"]
    C -->|Return fields and DOT| D["All-completions query"]
    A -->|Original input retained by default| D
    D --> E["YES / NO"]

Key Designs

1. PC scaffold: convert statistical constraints into graph-construction steps

The Turn-1 prompt starts from a complete undirected graph over the variables. Whenever the premise states that a pair is independent conditional on a set, the model removes that edge and records the separating set. Marginal correlation must not be interpreted as direct adjacency: correlation may travel through an indirect path, whereas adjacent variables in a faithful DAG cannot be separated by another variable set. This step distinguishes an absent edge from a present edge with an unresolved orientation, preventing two different uncertainties from being conflated.

The model then examines shared neighbors of non-adjacent endpoints. If the middle variable is absent from the endpoints’ separating set, the triple should become a v-structure with both arrows entering the middle variable. If it belongs to the separating set, the triple does not justify that collider orientation. The prompt next requests iterative application of Meek rules, such as propagating an orientation from an arrow followed by an undirected edge when the outer endpoints are non-adjacent, or using an existing directed path to constrain a shortcut. The skeleton, colliders, and compelled orientations must be updated consistently; unresolved edges remain undirected.

PC here is a linguistic scaffold, not a black-box program that performs conditional-independence tests, enumerates graphs, and returns the correct result. The model also receives already-written statistical relations rather than raw observations. The prompt uses a closed-world assumption: unlisted independencies are treated as absent. This fits the benchmark’s exhaustive premises but should not be directly applied to incomplete real-world independence lists containing statistical test errors.

2. Constrained graph summary: make intermediate state parseable rather than implicit in prose

The model records graph information in six fields: variables lists variables; skeleton records adjacent pairs; non_adjacent records non-adjacent pairs and separating sets; v_structures records colliders; directed contains oriented edges; and undirected contains edges with unresolved directions. Separating sets matter because the same undirected skeleton can support different collider structures: adjacency lists alone do not recover the equivalence class. Explicitly distinguishing directed from undirected edges also prevents interpreting “adjacent” as “a determined parent–child relation.”

For Qwen, JSON Schema is converted into a regex grammar that constrains the tool-call region. When thinking is enabled, the preceding reasoning remains free text; not every reasoning token is constrained by a graph grammar. API models enforce the same interface through strict JSON-schema tool calling. Gemma retains the structured interface without hard constrained decoding because the available backend was unreliable for its tokenizer. “Structured” therefore does not denote an identical implementation across model families.

The tool call only records and returns the model’s own analysis; it does not invoke a causal solver to supply missing orientations. The schema primarily guarantees parseable fields and types: its lists contain strings and do not automatically establish acyclicity, Meek closure, agreement between fields, or the existence of a valid DAG extension. Calling an output a CPDAG describes its intended semantics, not semantic certification of every instance. Stable formatting can reduce state drift and facilitate auditing, but it cannot turn incorrect causal reasoning into mathematical correctness.

3. All-completions query: distinguish possibility from deducibility

Turn 2 returns the structured fields and DOT graph to the model and requests hypothesis-specific checks of adjacency, compelled orientation, and directed reachability. For unresolved edges, the prompt requests consideration of all valid DAG completions; for indirect causation, the directed path must exist in every valid completion. A valid completion is not an arbitrary choice of direction for each undirected edge: it must preserve equivalence-class constraints, including avoiding new collider structures and directed cycles.

The task’s core decision semantics are given below. Here \(P\) is the premise, \(H\) the hypothesis, \(G\) the reference CPDAG identified by the premise, and \(\mathrm{MEC}(G)\) its Markov equivalence class. This formula defines the label; it does not imply that the LLM invokes a solver capable of an exhaustive proof.

\[ y(P,H)=\mathrm{YES}\iff\forall D\in\mathrm{MEC}(G),\ H\text{ holds in }D. \]

This explains why “there is an unresolved edge, therefore NO” is not a general rule. A direct-parent claim may fail because the relevant edge can reverse, while a more global claim may still hold across every valid completion. The model must test the actual hypothesis rather than merely detect an undirected edge. Conversely, a supporting path or one supporting completion does not justify YES: any valid counterexample defeats deducibility.

The distinguishing feature relative to the principal baseline is mandatory graph-state construction before the final decision. The baseline has explicit PC guidance but answers directly; the two-turn prose control writes free-text analysis before answering without a typed graph object. These controls address simple explanations such as an extra turn or a baseline lacking PC knowledge. However, the prompts are not token-identical, and the full method bundles graph externalization, field semantics, hard constraints, and Turn-2 query instructions. Its entire gain cannot be attributed exclusively to one component.

A Worked Example

The following three-variable example illustrates the pipeline; it is constructed for explanation and is not an additional experimental result from the paper. Suppose the premise states that A and B, B and C, and A and C are correlated, but A and C become independent given B, with no other independencies holding.

Turn 1 removes the A–C edge from the complete graph, records B as their separating set, and obtains the A—B—C skeleton. Because B belongs to the separating set, the triple cannot be oriented as A→B←C; no other rule forces an orientation. The summary therefore has an empty directed field, puts both skeleton edges in undirected, and records A-C|B in the non-adjacency field.

If Turn 2 asks whether A is a parent of B, the model cannot select A→B→C and answer YES. The equivalence class also admits A←B→C and A←B←C, where that parent claim fails, so the correct answer is NO. Likewise, correlation between A and C does not justify inserting a direct causal adjacency.

If instead A and C are marginally independent but become correlated conditional on B, their separating set is empty. The triple becomes A→B←C, compelling A to be a parent of B. This contrast shows that the intermediate is not merely a better layout for natural language: it preserves the separating-set and collider information that determines orientations, preventing the final decision from conflating different equivalence classes.

Loss & Training

The paper introduces no loss function or fine-tuning. Open-weight models run under vLLM, normally with temperature 0.6, top-p 0.95, and maximum context length 32768; GPT-5.4-mini uses high reasoning effort. The method combines prompts, output constraints, and a second-turn graph query rather than learning a new causal-discovery network.

There is no training-supervision arrow from a reference graph to the model. Evaluation separately checks final labels and the graphs constructed by the model. This separation reveals an important case: the final answer can be correct while the intermediate graph is inaccurate or internally inconsistent. Task accuracy alone should not be interpreted as evidence that the model has mastered the complete PC procedure.

Key Experimental Results

Main Results

The ID test split contains 1162 instances, only 180 of which are YES, making positive-class F1(YES) the primary metric and accuracy secondary. Paraphrase-OOD contains 2246 instances and changes wording while preserving graph instances; it is not a new causal-graph distribution. The table below draws from the paper’s Tables 1 and 6. Both F1 and accuracy are percentages, and “±” in the mean rows denotes standard deviation across seeds.

Model	Setting	Method	F1(YES)	Accuracy
Qwen3.5-27B	ID, seed 42	BaselineEnhanced	73.01	92.43
Qwen3.5-27B	ID, seed 42	TwoTurn-Prose-PC	67.55	89.41
Qwen3.5-27B	ID, seed 42	Structured Thinking	86.36	95.87
Qwen3.5-27B	ID, 3 seeds	BaselineEnhanced	77.49 ± 4.07	93.61 ± 1.04
Qwen3.5-27B	ID, 3 seeds	Structured Thinking	85.57 ± 1.70	95.58 ± 0.50
Qwen3.5-27B	Paraphrase-OOD	BaselineEnhanced	72.33	92.61
Qwen3.5-27B	Paraphrase-OOD	Structured Thinking	82.79	95.06

The primary-seed F1 gain is 13.35 percentage points, with a paired-bootstrap 95% confidence interval of [+8.42, +18.59] and an exact McNemar test on label correctness of \(p=2.4\times10^{-6}\). Across three seeds, the mean F1 gain is 8.08 ± 5.34 percentage points, so the larger primary-seed gain should not be treated as the stable average. The additional runs improve by 2.68 and 8.21 percentage points.

Cross-model results are also positive: Qwen3.6-27B improves from 75.92 to 85.71, Gemma-4-31B from 85.38 to 87.39, Qwen3.5-9B from 39.18 to 59.56, and GPT-5.4-mini from 85.39 to 88.58. Outside the principal three-seed ID comparison, these and the OOD results are generally single-seed. Gemma additionally lacks hard constraints, so cross-backend comparisons must retain implementation caveats.

Ablation Study

The following full-ID Qwen3.5-27B ablations come from the paper’s Table 2. Changes are absolute F1 percentage-point differences relative to the full method, not relative percentage decreases.

Config	F1(YES)	Accuracy	Change versus full method
Structured Thinking, full method	86.36	95.87	—
Remove thinking	71.95	92.08	−14.41
Remove constrained decoding	76.88	93.37	−9.48
Remove PC-algorithm prompt	36.21	87.26	−50.15

Removing PC content produces the largest decline, showing that an arbitrary tool object does not solve the task. The no-hard-constraint condition retains soft tool-format instructions, so it compares enforced syntax with a request for structured output, not the presence versus absence of a tool prompt. These one-factor removals are sensitivity tests, not an additive decomposition of independent contributions.

The intermediate-graph audit in the paper’s Table 4 further distinguishes graph-shaped output from correct graphs. Edge/collider F1 uses a decimal scale, whereas exact match, consistency violations, and conditional accuracy are percentages; these are not interchangeable metrics.

Audit metric	ID	Paraphrase-OOD
Skeleton F1	0.960	0.959
Directed-edge F1	0.896	0.884
V-structure F1	0.923	0.920
Exact CPDAG match	75.9%	74.4%
Graph-consistency violations	18.4%	20.7%
Accuracy when graph exact	97.2%	96.6%
Accuracy with consistency violation	91.1%	90.1%

Key Findings

• Higher F1 does not imply higher precision on every run. On the primary seed, true positives increase from 119 to 152, false negatives decrease from 61 to 28, and false positives decrease from 27 to 20. The additional seeds incur small precision declines, with gains mainly driven by recall. The robust claim is improved F1 and recall, not universal reductions in every error type.
• Graph content affects downstream answers. Removing the premise from Turn 2 gives 82.56 F1, whereas scrambling the full graph gives 74.32, declines of 3.80 and 12.04 percentage points relative to the full method. Corruption can create invalid CPDAGs, however: these probes establish content dependence, not formally valid reasoning over all completions on every instance.
• Thinking depends on model scale. In the appendix, disabling thinking raises Qwen3.5-9B Structured Thinking from 59.56 to 64.46. A reasoning switch useful at 27B should not be transferred to smaller models without validation.
• Larger graphs remain stress tests. The appendix finds further gains on random and ALARM-derived seven-variable graphs and ASIA-derived eight-variable graphs, but graph families differ and runs are single-seed. They do not establish a controlled variable-count trend; network names and semantic variable names are also withheld from the model.

Highlights & Insights

• The intermediate matches the object defining truth. This is not a generic plan-then-answer workflow: it preserves equivalence-class information that determines the label. A similar approach could represent program states or constraint systems, but first identifying the relevant formal object matters more than simply emitting JSON.
• Construction and readout are evaluated separately. High skeleton F1 alongside lower directed-edge F1 identifies orientation as a remaining challenge, and correct labels do not conceal graph-consistency violations. An auditable state makes it possible to target missing edges, incorrect directions, or hypothesis readout rather than only lengthening prompts.
• Controls bound the interpretation. Neither two-turn prose nor single-turn structured vocabulary recovers the gains, supporting the value of typed state. The paper also retains caveats about bundled prompts and interfaces instead of elevating behavioral probes into a complete mechanistic explanation.

Limitations & Future Work

• This is not real-world observational causal discovery. Experiments deduce claims from verbalized statistical constraints; they do not establish causal-graph recovery with finite samples, latent confounding, or missing/incorrect independencies, nor measure the accuracy of real-world intervention effects.
• Syntactic constraints do not certify semantics. Consistency violations include field conflicts, collider inconsistencies, missing closure, and the absence of a valid DAG extension. An independent graph validator and a repair route for uncertified summaries would be more appropriate than treating parseability as truth.
• Components remain bundled. Graph-field names, structured output, tool-result formatting, and Turn-2 instructions change together, while current probes do not preserve graph validity. Finer factorial designs, lightly structured prose controls, and valid-CPDAG interventions could better localize the source of gains.
• Cost and interface choices matter. The two-turn workflow uses roughly twice the baseline’s tokens and about 1.5 times its wall-clock time in batched vLLM. The appendix shows that forced API tool selection can compress the reasoning budget; automatic selection with a prompt instruction restores performance. Reproduction therefore needs the calling strategy, not just the model name.
• The failure gallery is not an unbiased error distribution. The appendix’s 32 manually labeled cases were selected to cover failure categories. Their shares of missing-edge errors, readout errors, equivalence-class ambiguity, and invalid graphs should not be interpreted as population frequencies. Transfer to SCM, intervention, or world-model tasks also remains untested.

Related Work & Insights

• vs Corr2Cause / Jin et al.: The benchmark defines deduction from correlations and independencies to causal hypotheses. This paper improves the LLM reasoning interface for that task; it does not introduce PC or a new identifiability theorem.
• vs Sun et al.’s earlier Structured Thinking work: The earlier approach uses a knowledge-graph-style intermediate for causal generalization. This paper specializes the state to a CPDAG summary and adds a strong PC baseline, graph-corruption probes, and full-split field audits.
• vs modular causal prompting and C2P: These approaches organize prompting steps or prose sub-answers, whereas this method requires a fixed-type graph object. The transferable lesson is to preserve checkable task state at each stage, not merely another natural-language conclusion.
• vs PAL / Program of Thoughts: Program-aided methods delegate computation to code; this tool only records model analysis, with no symbolic solver deriving the answer. That reduces external execution dependencies but retains model errors in both graph construction and readout.

Rating

• Novelty: 4/5 — Ties the intermediate state to the object defining the label and tests its role through content probes, while remaining within structured prompting.
• Experimental Thoroughness: 4/5 — Strong baselines, multiple seeds for the principal comparison, and full-graph audits are valuable; single-seed conditions and bundled factors limit mechanistic conclusions.
• Writing Quality: 4/5 — Clearly describes the method, prompts, and backend differences, especially the boundary between valid formatting and valid graph semantics.
• Value: 4/5 — Offers a causal-deduction improvement without fine-tuning and a reusable auditing approach, but does not replace a reliable causal solver.