Program-guided fact-checkers split a complex claim into a small program of sub-questions and checks. An example is "Both Cameron and Nolan were born in Canada," which becomes two verification calls joined by AND. A language model then answers each step. This makes verdicts inspectable, but every step pays the full cost of careful, evidence-citing reasoning, even though the verdict often depends on only a few steps. We propose running every step first in a cheap, possibly opaque mode. We then compute the program slice of the verdict: the minimal set of steps whose values actually determine the output, found by following data and control dependencies backward from the final decision. Only those steps are re-run in the expensive, explicit mode that cites evidence, and the loop repeats until the slice is stable. With a deterministic explicit solver, the final verdict is provably identical to what fully explicit execution would produce. The explanation shown to a human is exactly the verbalized slice, which is a minimal sufficient justification.
This matters because two literatures are currently in direct tension. Latent-reasoning work cuts inference cost by hiding intermediate thought in continuous vectors. Explainable fact-checking needs every verdict-bearing step to be readable and grounded. Our answer is that opacity is acceptable exactly where the output provably does not depend on it. The code-property-graph machinery from program analysis is what makes "provably" precise. A code property graph is a single graph that overlays a program's syntax tree, its control flow, and its data flow.
Core Claim
For a verification program with boolean and question-answering steps, the following procedure returns the same verdict as fully explicit execution while spending explicit reasoning only on the verdict's dynamic slice:
- Draft all nodes cheaply.
- Compute the dynamic dependence slice of the final prediction.
- Re-execute slice nodes explicitly in dependency order.
- Recompute the slice and repeat to a fixed point.
Its cost is
$$C = \sum_{v \in V} c_{\text{cheap}}(v) + \sum_{v \in S^{*}} c_{\text{exp}}(v) \cdot r(v),$$
where $V$ is the set of program nodes, $S^{*}$ is the converged slice, $c_{\text{cheap}}$ and $c_{\text{exp}}$ are per-node costs in the two modes, and $r(v)$ counts how many times node $v$ is re-run explicitly because an upstream answer changed.
The savings therefore depend on two quantities, both measurable. The first is how much smaller $S^{*}$ is than $V$. The second is how often cheap drafts are wrong on nodes that land in the slice.
The equivalence argument is short. At convergence, every slice node holds an explicit value computed from explicit inputs, and by definition of a dynamic slice the output is a function of those values alone. Nodes outside the slice can only matter when their value would pull them into the slice, and the fixed-point check catches exactly that case. The new part is not the parallelism or the graph representation for its own sake. It is the combination of three things: slicing as a correctness-preserving criterion for where explicit reasoning is required, cheap drafts to predict the slice, and the slice itself as the delivered explanation.
Relation to Prior Work
The motivating system is PROGRAMFC. It has an LLM write Python-like programs of QUESTION, VERIFY and PREDICT calls, which a small solver executes line by line. It shows that this structure helps on deep claims, with a 14.9% Macro-F1 gain on HOVER 4-hop claims. The same research file notes that repeated sequential model calls make it slow, and that it treats programs as flat scripts. We keep its program format and interpreter semantics. We change what gets executed carefully and in what order.
ProgVGAT and the TabFact latent program algorithm also execute symbolic programs for verification. ProgVGAT builds a graph only after execution, linking verbalized results to table cells. It never analyzes the program's own dependencies, which is the object we operate on.
The code-analysis side supplies the method. Chakraborty et al., VISION and SIT3 build combined syntax, control-flow and data-flow graphs of source code. They use these to feed neural models: a vulnerability classifier in the first two, a summarizer whose attention is masked by graph adjacency in SIT3. We use none of the learned components. We borrow only the classical dependence analysis, because verification programs are short enough that exact slicing is cheap. The contrast is deliberate. Those works learn over graphs to find causally relevant code. We compute causal relevance exactly and spend model compute accordingly.
The latency side supplies the cheap mode and constrains its use. CoLaR and MARCOS compress reasoning into continuous latent steps, with large speedups on math benchmarks. RL length penalties such as DLER and ConciseRL shorten explicit chains. All of these apply compression uniformly across a problem. The research file stresses that this makes latent steps unreadable and that they are unvalidated outside closed math domains. We confine such compression to draft nodes, whose opacity never reaches the verdict.
Knowing Before Saying reports that hidden states encode whether a reasoning path will succeed before it is written out. This motivates the hope that cheap drafts predict the slice well. That hope is an empirical question, not an assumption.
On the explainability side, LOREN identifies the culprit phrase of a refuted claim, reporting 74.3 F1 on 100 refuted FEVER claims. It also fights "spurious programs" that reach the right label through wrong steps. The dynamic slice of a refuted conjunction is a culprit by construction. A static slice, which dependency analysis provides for free, flags program steps that can never influence PREDICT, a cheap structural diagnostic for spurious programs. QA-NatVer produces faithful proofs through natural-logic operators. Our explanation is faithful in the narrower but checkable sense that it is sufficient to recompute the verdict.
Research Program
Program analyzer. We build an analyzer for PROGRAMFC-style programs. It parses each program into a syntax tree, adds data-dependence edges from each variable definition to its uses, and adds control-dependence edges for boolean composition in PREDICT. Boolean composition is modeled with short-circuit semantics, so that AND, OR and NOT have well-defined dynamic slices. Given runtime values, it returns the dynamic slice. Before any execution, it returns the static slice and the independence structure used for parallel scheduling.
Executor. The executor runs every QUESTION and VERIFY node in draft mode, in parallel wherever data flow allows. It computes the slice, then runs slice nodes in explicit mode in topological order. Explicit mode means retrieval, step-by-step reasoning, and a cited evidence span. Whenever an explicit value differs from its draft, the executor recomputes downstream drafts and the slice. It stops when the slice is fully explicit.
Draft modes. We test two. The first is the same instruction-tuned model answering directly without reasoning. The second is a length-penalized or latent-compressed variant trained in the style of DLER or CoLaR on sub-question data. The explicit solver uses greedy decoding so that the equivalence argument holds exactly.
Analysis. We characterize, by claim type and hop count, how large slices are relative to full programs, how often drafts are wrong on slice nodes, and how many fixed-point rounds occur.
Baselines
The naive reference is fully explicit sequential execution. Every node of the generated program runs in explicit mode, one after another. This is PROGRAMFC's interpreter with a modern reasoning solver in place of FLAN-T5. It defines the accuracy target our method must match exactly, and the cost we must beat.
As the published reference point, we reproduce PROGRAMFC's own configuration. The research file reports its relative results: a 14.9% Macro-F1 improvement over the strongest baseline on HOVER 4-hop, and an 11.7% drop from 2-hop to 4-hop versus 21.7% for DeBERTaV3. No absolute HOVER Macro-F1 value and no latency figure for PROGRAMFC were found on Lacuna, so we will report our reproduced absolute numbers alongside those relative figures.
The strongest competitor is explicit short-circuit execution with dependency-based parallelism. This is what a careful engineer would build. It runs independent nodes concurrently and stops evaluating an AND chain at the first explicit false. It already preserves the explicit verdict exactly, so it isolates whether cheap drafting plus slicing buys anything beyond scheduling.
The main ablation is draft-ordered short-circuit. Drafts are used only to reorder conjuncts so that the likely-false one is checked explicitly first. There is no general slicing and no fixed-point recomputation. This separates the value of slice prediction on flat AND chains from its value on programs with chained QUESTION dependencies and nested logic.
A single-call baseline prompts the same model with the claim and retrieved evidence to reason end to end, with a DLER-style length penalty. This tests whether one short chain matches the program pipeline on cost and accuracy while giving up per-step auditability.
All systems share the same program generator, the same retriever and corpus, the same solver model, greedy decoding, and the same hardware. Any trained draft model gets the same fine-tuning budget as any trained baseline. Beating the strongest competitor means three things at once. We must match fully explicit Macro-F1 within noise. We must use substantially fewer explicit-mode tokens and fewer model calls. And our explanations must be no less sufficient, where sufficiency is judged per verdict on a held-out split.
Why not just…?
Why not just use short-circuit evaluation and parallel scheduling? This is the real threat. For AND chains, short-circuiting is a special case of dynamic slicing, and it is equally correctness-preserving. If HOVER programs are dominated by flat conjunctions, our method reduces to draft-ordered short-circuiting. Its advantage then depends only on draft accuracy and on the ratio $c_{\text{exp}}/c_{\text{cheap}}$. We will report this plainly by stratifying results by program shape. The claim survives only if gains persist where it predicts they should: on multi-hop programs whose QUESTION outputs feed later VERIFY arguments, and on refuted claims whose false conjunct is not first in program order.
Why not just compress all reasoning with a latent or length-penalized model? CoLaR and MARCOS report their gains only on math benchmarks. Their intermediate states are unreadable, which fails the evidence-attribution requirement argued by Atanasova et al. and Kotonya & Toni. Our design keeps whatever speed such models offer in draft mode while guaranteeing the verdict never rests on them. The single-call length-penalized baseline tests directly whether one short chain is competitive on accuracy.
Why not just prompt one strong model with chain of thought end to end? PROGRAMFC's own comparison shows end-to-end verifiers degrade more with depth, dropping 21.7% versus 11.7% from 2-hop to 4-hop. It also shows a program-guided 80M model matching an 11B end-to-end model. Our single-call baseline re-tests this with a modern solver. If it matches program-guided accuracy at lower cost, the case for any program pipeline weakens, and we would report that.
Why build a code property graph at all for five-line programs? The syntax, control-flow and data-flow structure is required to define the slice precisely under nested boolean logic and variable reuse. It is cheap to build at this program size, and we make no claim that graph learning helps. Its value lies in the exactness of the dependence analysis, not in scale.
Proposed Experiments
The primary benchmark is HOVER, split into 2-, 3- and 4-hop subsets, with FEVEROUS-S as a second textual setting, both as used by PROGRAMFC. We report Macro-F1, explicit-mode tokens, total tokens, model calls, and wall-clock time.
Equivalence check. The first decisive check is empirical equivalence. Verdict agreement with fully explicit execution should be 100% under greedy decoding. Any disagreement indicates a bug in the slicing semantics or nondeterminism in the solver, and we will trace each case.
Cost check. The second check is cost. The method must cut explicit tokens relative to parallel short-circuit execution at identical accuracy, broken out by hop count, program shape and gold label. We expect savings to concentrate in refuted claims and deep QUESTION chains, and to vanish for supported flat conjunctions, where the slice is the whole program. If savings appear nowhere except where short-circuiting already captures them, the idea fails.
Explanation check. The third check is explanation quality. We measure slice size. We measure sufficiency: an independent model given only the verbalized slice and its evidence spans must recover the verdict. On a human-annotated sample of refuted claims, we score whether the slice's culprit matches the annotated error, with LOREN's culprit-identification F1 serving as a reference setting rather than a directly comparable number.
Spurious-program diagnostic. As a secondary study, we test whether programs whose static slice excludes some QUESTION nodes are disproportionately wrong. That would validate the dependency analysis as a cheap diagnostic for spurious programs.
Table evidence. A small extension to TabFact complex claims tests whether slicing transfers to table programs with aggregation. There the relevant reference is ProgVGAT's reported 67.6% complex-subset accuracy and 74.4% overall.
References
- Fact-Checking Complex Claims with Program-Guided Reasoning
- Program Enhanced Fact Verification with Verbalization and Graph Attention Network
- TabFact: A Large-scale Dataset for Table-based Fact Verification
- Deep Learning Based Vulnerability Detection: Are We There Yet?
- VISION: Robust and Interpretable Code Vulnerability Detection Leveraging Counterfactual Augmentation
- Code Summarization with Structure-induced Transformer
- Think Silently, Think Fast: Dynamic Latent Compression of LLM Reasoning Chains
- MARCOS: Deep Thinking by Markov Chain of Continuous Thoughts
- DLER: Doing Length pEnalty Right — Incentivizing More Intelligence per Token via Reinforcement Learning
- ConciseRL: Conciseness-Guided Reinforcement Learning for Efficient Reasoning Models
- Knowing Before Saying: LLM Representations Encode Information About Chain-of-Thought Success Before Completion
- LOREN: Logic-Regularized Reasoning for Interpretable Fact Verification
- QA-NatVer: Question Answering for Natural Logic-based Fact Verification
- Generating Fact Checking Explanations
- Explainable Automated Fact-Checking: A Survey
- HoVer: A Dataset for Many-Hop Fact Extraction And Claim Verification