Auditing the Plan, Not the Prose: Graph-Level Faithfulness Tests for Program-Guided Fact-Checking

Some fact-checking systems do not write a free-text justification. Instead, a language model turns the claim into a small program, such as "ask who directed film X, then verify that this person was born in Y, then combine the results with AND." An interpreter runs the program by calling smaller question-answering and verification models. These systems are called explainable by design because the verdict is whatever the executed program returns. We argue that this only relocates the faithfulness problem. The model that writes the program can already hold an opinion about whether the claim is true. It can then write a program built to reach that opinion. Examples include omitting a hop, inserting a verification step that restates the conclusion, or computing an intermediate answer that nothing downstream uses. The interpreter will then run an unfaithful plan with perfect fidelity.

We propose to measure and reduce this "plan-level" rationalization. We do it by treating each generated program as what it is: a data-flow graph, meaning a graph of which call's output feeds which later call. We do not treat it as a string. Because the programs are tiny, the graph can be extracted exactly and cheaply. Because the interpreter sits outside the model, we can run causal interventions on individual nodes with black-box access only: delete a node, swap its answer, or rewire an edge, then re-execute. The resulting diagnostics would tell a journalist or auditor whether each sub-question actually carried weight in the verdict. They would also tell us whether the program's shape was determined by the claim or by the generator's prior belief about the answer.

Core Claim

In program-guided fact-checking, a correct verdict and a runnable program do not show that the program encodes the claim's reasoning. We hypothesize three measurable failures in Fact-Checking Complex Claims with Program-Guided Reasoning (PROGRAMFC) on many-hop claims. First, decorative nodes: sub-calls whose outputs do not causally affect the verdict. Second, verdict leakage: verification nodes whose arguments paraphrase the full claim or conclusion, which is the fact-checking analogue of adding the conclusion as an axiom. Third, prior-tracking structure: logical shape, such as where a NOT or an OR is placed, that follows the generator's own zero-shot verdict more than the gold label.

We further claim that constraints stated on the data-flow graph can repair many of these programs, and that string-level checks cannot. The graph constraints are liveness (every node reaches the final prediction), coverage (every atomic part of the claim is checked by some live node), and non-leakage.

This combines three directions, each with a different role. Structural code representation supplies the object of analysis. Post-hoc rationalization supplies the causal tests. Explainable fact-checking is the application, where the stakes and benchmarks live.

What Prior Work Establishes and Leaves Open

PROGRAMFC has an LLM write programs from three primitives, QUESTION, VERIFY, and PREDICT, and executes them with FLAN-T5. It reports strong robustness to reasoning depth on HOVER. Its programs are generated and handled as flat text, however, and it never asks whether the generator wrote the program because of the claim's meaning. Our proposal builds directly on it and audits it.

Learning to Generate Programs for Table Fact Verification via Structure-Aware Semantic Parsing worries about spurious programs, but only for tables under weak supervision, and it has no causal diagnostics.

The strongest motivating evidence comes from formal reasoning. Do LLMs Game Formalization? shows that Lean compilation rates of 87–99% hide premise mistranslation and fabricated axioms. It also shows that LLM judges struggle to spot the mistranslations. That finding constrains our design: we cannot rely on an LLM judge as the detector. The paper stops at logic puzzles. We carry its question into retrieval-based fact-checking, where the "axioms" are sub-questions answered from Wikipedia.

The causal tools come from work on post-hoc rationalization in natural-language chains of thought:

  • Can Aha Moments Be Fake? defines necessity and sufficiency tests per reasoning step. It finds a mean step score of 0.03 on AIME, but computing it needs white-box, many-pass perturbation of token spans.
  • How Likely Do LLMs with CoT Mimic Human Reasoning? classifies models by whether reasoning mediates the answer or merely shares a common cause with it.
  • RFEval finds 49.7% unfaithful outputs under injected flawed reasoning, with code among the worst domains.

We reuse their logic of necessity, sufficiency, and counterfactual intervention. We apply it to a different unit, the program node, where interventions are exact and need only black-box model access.

Making Reasoning Matter (FRODO) trains with preference optimization so that answers depend on reasoning. It operates on free text and never on evidence-grounded verification. We use it as a training-time comparator.

Direction 1 papers, such as Chakraborty et al. and Zhang et al., show that sequence models of code latch onto identifiers and miss control and data flow. This is our reason to expect that generators emit syntactically plausible programs with broken data flow. It is also our reason to expect that string-level checks will miss those breaks.

One tension deserves to be stated plainly. Direction 1 notes that graph extraction is a scalability bottleneck. For a three-primitive language with explicit variable bindings, the bottleneck disappears: def-use chains can be recovered exactly. This is precisely why fact-checking programs are a clean testbed for structure-aware faithfulness analysis.

Research Program

We build three pieces.

A parser. It maps each PROGRAMFC-style program into a typed data-flow graph. Nodes are QUESTION, VERIFY, and PREDICT calls. Edges mark where a variable produced by one call is substituted into another. From this graph we read, statically, dead nodes (no path to PREDICT) and leaked nodes (a VERIFY argument with high entailment to the whole claim while other VERIFY nodes are present).

A black-box causal audit. For each node $v$, we re-execute the program with $v$'s output replaced by a counterfactual value: the negated boolean for VERIFY, or a type-matched distractor entity for QUESTION. We define node necessity as

$$N(v) = \Pr\left[\hat y(\text{do}(v = \tilde v)) \neq \hat y\right],$$

where $\hat y$ is the original executed verdict and the probability is over sampled counterfactual values $\tilde v$. A node with $N(v)=0$ under all interventions is decorative. We also rewire edges, feeding a correct upstream answer into a node that previously ignored it, to test sufficiency in the sense of the TTS work.

A plan-level test of the generator. This is the most novel measurement. We elicit the generator's zero-shot verdict prior $p$ on each claim. We then execute its program with oracle sub-module answers derived from HOVER's gold evidence, so that the program's structure alone determines the result. We define prior leakage as

$$L = \Pr[\hat y_{\text{oracle}} = p \mid p \neq y^{*}] ,$$

where $y^{*}$ is the gold label. If programs were faithful encodings of the claim, oracle execution would recover $y^{*}$ regardless of $p$. A high $L$ means the program's shape was bent toward the generator's belief.

We complement this with claim counterfactuals: minimal edits that flip the gold label, generated by an LLM and human-validated on a sample. For each edit we ask whether the program's graph changes at the edited entity or relation, or whether it stays the same while the verdict flips for other reasons.

A repair method. Graph-constrained regeneration rejects and resamples programs that violate liveness, coverage, or non-leakage. Coverage is checked by aligning claim spans to live VERIFY arguments. For settings with fine-tuning access, we add a FRODO-style preference step whose preferred programs pass the graph checks and whose dispreferred programs are the generator's own violating samples.

We run everything across generator scales. This tests whether the inverse-scaling pattern reported by On the Hardness of Faithful Chain-of-Thought Reasoning and RFEval, where larger models are less faithful, appears as higher prior leakage in larger program writers.

Baselines

The naive reference point is a retrieve-then-verify model: DeBERTaV3 over retrieved evidence, as used among the baselines in PROGRAMFC, run end to end. It shows how much program guidance buys at all. On faithfulness it has no plan to audit, so it anchors only the accuracy axis. For context, HoVer reports that TF-IDF recall falls from 80% on 2-hop to 15% on 4-hop claims.

The strongest existing method is PROGRAMFC itself, run unmodified with the same generator, the same FLAN-T5 sub-modules, and the same retrieval, in both closed-book and open-book settings. On HOVER 4-hop it reports a 14.9% Macro-F1 improvement over the strongest baseline. The file gives no absolute Macro-F1 value on Lacuna, so we will reproduce its numbers ourselves before comparing. Beating it has a specific meaning here. We must reduce the decorative-node rate and prior leakage $L$ significantly while keeping Macro-F1 within one point on each hop subset of HOVER and on FEVEROUS-S. If faithfulness rises and F1 falls further, we will report that trade-off rather than claim a win, since the Hardness paper found drops of up to 20%.

A second strong competitor is self-consistency PROGRAMFC: sample $k$ programs and take the majority verdict. It is given exactly the same number of generator samples as our reject-and-resample loop, so the compute is matched.

A third is an LLM-judge filter, which asks a strong model whether each program faithfully encodes the claim and resamples when it says no. It uses the same sample budget.

For the natural-language comparison on explanation faithfulness, we run MADR from Can LLMs Produce Faithful Explanations For Fact-checking? on PolitiHop. There it reports 30% fully faithful explanations under human evaluation, against 20% for zero-shot and Self-Refine. We render our executed programs as explanations and have the same style of human annotation judge them.

The key ablation replaces graph-level checks with string-level ones of comparable cost. These are keyword coverage of claim spans across all VERIFY arguments, with no reachability, and string-similarity leakage detection. This isolates whether the data-flow structure matters or whether surface text checks suffice.

Why not just…?

Why not just use a bigger program generator? Scaling is the default reviewer answer, but the file's evidence points the other way on faithfulness. RFEval found gpt-oss-120B less faithful than its 20B sibling, and How Likely Do LLMs with CoT Mimic Human Reasoning? found that scaling Llama from 7B to 70B did not strengthen the reasoning-to-answer chain. Our scale sweep tests this directly for program writers. If prior leakage falls with scale, that result would weaken our motivation, and we would report it.

Why not just sample several programs and vote? This is the real threat on accuracy, and it may match or beat us on Macro-F1. Voting hides disagreement rather than removing it, however. If the generator's prior bends most samples the same way, the majority inherits the leakage. Our matched-budget comparison measures $L$ and the decorative-node rate for the voted program as well as F1. If voting also drives $L$ down, the graph constraints are unnecessary, and we would say so.

Why not just ask an LLM judge whether the program matches the claim? Do LLMs Game Formalization? reports that LLM judges struggled to detect premise mistranslations, which is the exact failure we target. The judge-filter baseline, scored against human-annotated program faithfulness on a sample, will show whether that finding transfers to fact-checking programs.

Why not just apply token-level True Thinking Scores to the generator's output? That approach needs logits or activations and many perturbation passes per step, as Can Aha Moments Be Fake? acknowledges. It also perturbs text spans whose semantic unit is unclear. Node interventions are exact, cheap, and need only black-box access. On an open model we will compute both and report their agreement, to check that the cheaper node-level score is not missing signal.

Why not just refine explanations with multi-agent debate? MADR still leaves 70% of explanations not fully faithful. It also cannot tell whether a sentence carried causal weight, because free text has no executable structure to intervene on. The PolitiHop comparison tests whether executed, graph-audited programs rendered as explanations do better under the same human protocol.

Proposed Experiments

The first experiment is purely diagnostic and needs no new method. On HOVER, split into 2-, 3-, and 4-hop, and on FEVEROUS-S, we run PROGRAMFC and measure four things: decorative-node rate, leaked-node rate, prior leakage $L$ under oracle execution, and program sensitivity to label-flipping claim edits. We break these down by hop count and by generator scale. The prediction is that among correctly verified 3- and 4-hop claims, a non-trivial share run through programs with at least one decorative or leaked node. We also predict that $L$ exceeds the rate expected from chance agreement. Any rate close to zero would falsify the core claim, and that null result would itself be publishable: it would be evidence that program guidance delivers the faithfulness it promises.

The second experiment validates the measures. Annotators judge whether a sample of programs encodes the claim's reasoning, and we check that decorative and leaked flags predict their judgments better than the LLM-judge and string-level checks do.

The third experiment evaluates the repair. It compares graph-constrained regeneration, and its preference-trained variant, against all baselines at matched sample budgets. It reports Macro-F1 alongside every faithfulness measure, so that any accuracy-faithfulness trade-off is visible rather than averaged away.

The decisive check is the key ablation. If string-level coverage and leakage checks achieve the same reduction in $L$ and the same agreement with human judgments as the graph-level checks, then the structural half of this proposal is unnecessary. The contribution would then reduce to the causal audit alone.