When a language model answers from retrieved documents and the documents do not contain what it needs, it rarely says so. It fills the gap from memory and states the result confidently. Fact-checking research calls the honest alternative "Not Enough Info" (NEI). Current systems handle it badly in two ways. They treat missing information as contradiction (Sizhen Li et al.). They also fail to notice when a small but necessary qualifier is absent: classifiers catch an omitted adverb only 21% of the time, and an omitted date only 63% of the time (Fact Checking with Insufficient Evidence). Program-of-thought prompting has the model write a short program that an interpreter then runs. It has made multi-hop fact-checking more reliable (Fact-Checking Complex Claims with Program-Guided Reasoning). Yet those programs only ever return True or False, so they have no way to express "this was never established."
We propose a different contract between the claim and the program. Before any retrieval, the model turns the claim into a program whose variables name every fact the claim depends on: entities, bridge entities, dates, quantities, and qualifiers such as "first," "briefly," or "only." Each variable can be bound only by a span quoted verbatim from retrieved text. A claim counts as checkable only when all of its variables are bound. An unbound variable produces an Unknown value, and that value has three uses. It is the NEI verdict, it explains what is missing, and it serves as a targeted query that tells us whether the gap comes from retrieval failure or from absence in the corpus.
Core Claim
Insufficient-evidence detection should happen at the level of named, claim-derived slots, not at the level of the whole claim–evidence pair. Our hypothesis is that forcing the model to list the claim's dependencies as program variables, and requiring verbatim grounding for each one, will catch the fine-grained omissions that encoder classifiers and direct prompting miss. The adverbial-modifier case is the one where current models are worst. We also expect it to make NEI verdicts explainable ("the date of the second event was never found") and to make retrieval failure separable from a genuine evidence void.
Three-valued logic is part of the system, but we do not claim it as the contribution. Once leaf checks can return Unknown, combining them is easy, and a reviewer could reasonably say an LLM aggregator would do as well. We test that directly rather than assume it. The contribution we stake is the slot enumeration plus the grounding requirement, and the diagnostic re-query that both make possible.
Where This Sits
Prior work supplies the method. PROGRAMFC decomposes claims into QUESTION, VERIFY and PREDICT calls combined with Boolean logic. We reuse its decomposition-and-execute structure. We differ in three ways: variables are derived from the claim's qualifiers and not only its sub-questions, bindings must be quoted, and failures propagate as Unknown instead of collapsing to False. Pelican checks vision-model outputs with code over a table of detected objects. It shows that variables help keep entity identity consistent across steps. It also shows the weakness we target: when the detector misses an object, Pelican cannot tell absence from tool error. RLSeek trains models to quote exact source spans before judging hallucination. We borrow its quotation requirement as a binding rule, but apply it inside an executed program instead of free-text reasoning, and without span-level training labels.
Prior work also motivates the gap. FacTool uses tools for verification but outputs only TRUE or FALSE. The work on insufficient evidence defines evidence-sufficiency prediction, introduces the SufficientFacts diagnostic set, and improves encoders with synthetic omissions and contrastive training. It never tests generative or program-guided verifiers, and that is the comparison we make. Chien-Sheng Wu et al. name the confusion between retrieval failure and evidence gaps but do not build a system that separates them. RAGTruth finds that RAG models add baseless content far more often than they contradict their sources. That is exactly the failure an unbound-variable check should catch.
Two findings constrain the design. PROGRAMFC's authors report failures on implicit commonsense. Our slot enumeration could fail the same way, by omitting a dependency the claim leaves unstated, so we measure enumeration recall explicitly. Second, Unveiling Confirmation Bias in Chain-of-Thought Reasoning shows that step-by-step text reasoning can rationalize what the model already believes. For this reason the decision that a slot is bound is made by a deterministic span-match check, not by the model's own judgment.
Research Program
The system has four parts.
- Program generation. A prompted code model reads the claim and writes a program. The program declares typed variables, for example
founder: Entity,founding_date: Date, orqualifier_first: Bool. It populates each variable with aFIND(question)call and ends with a verdict expression. - Binding. At runtime,
FINDretrieves passages and asks a reader model for an answer. It accepts the answer only if the answer comes with a verbatim span from a retrieved passage that the interpreter can locate. A missing or unlocatable span leaves the variable asUnknown. - Aggregation. The verdict expression is evaluated under strong three-valued (Kleene) semantics. Under these rules, a conjunction is False if any part is False, True only if every part is True, and Unknown otherwise.
- Diagnosis. For each Unknown that decides the verdict, the system runs a bounded re-query step. It rewrites the question, issues sparse and dense variants, and follows the bridge entity. If the slot becomes bound, the original Unknown is logged as a retrieval failure. If it stays unbound after the budget is spent, it is reported as a probable evidence void, and the unbound variable is the explanation.
The research questions are as follows. Does slot enumeration close the qualifier blind spot on SufficientFacts? Does the full program beat its own ablations on three-way verification with realistic retrieval? Can the diagnosis step distinguish documents that exist but were not retrieved from documents that were deleted? We also measure how often failures come from the enumeration step, meaning the model did not create a variable for something the claim needs. That is the main way we expect the method to fail.
Baselines
The naive reference point is the reader model alone, given the claim and the same top-k retrieved passages, asked for Supported, Refuted or Not Enough Info. It answers directly and receives the same few-shot examples. This tells us how much any added structure buys.
The strongest existing method for the sufficiency question is the contrastive, augmentation-trained encoder from Fact Checking with Insufficient Evidence. It reports gains of up to 17.8 F1 on evidence-sufficiency prediction and up to 27 accuracy points on NEI detection over standard training. The file gives only those relative gains plus the per-omission accuracies for untrained models (21% for adverbs, 63% for dates), and we found no absolute post-training sufficiency score for it on Lacuna. We will retrain it using the released procedure on the same training splits. To beat it, the system must exceed its sufficiency F1 overall and, specifically, its per-type accuracy on adverbial and noun-modifier omissions. Matching it on dates while failing on adverbs would count as a loss on the central claim.
For multi-hop verification, the strongest competitor is PROGRAMFC run open-book with the same retriever, reader model and number of LLM calls. It reports a 14.9% Macro-F1 gain on 4-hop HOVER over the strongest baseline, and smaller degradation from 2 to 4 hops (11.7% versus 21.7% for DeBERTaV3). No absolute 4-hop Macro-F1 is given in the file. We will therefore reproduce it and report our own numbers next to the published relative gains. For three-way evaluation with gold evidence, the reference is the FEVEROUS verdict predictor's macro-F1 of 0.70 (FEVEROUS). For the retrieval-coupled hallucination setting, the references are RAGTruth's span-level F1: 52.7% for a fine-tuned 13B detector and 28.3% for prompted GPT-4. We found no numeric RLSeek score on Lacuna.
Three ablations isolate the key ingredient. In the first, we keep the three-valued program but replace claim-derived slot enumeration with PROGRAMFC-style sub-questions only. In the second, we keep slots but drop the verbatim-span requirement, so the reader's word decides whether a slot is bound. In the third, we keep everything but replace Kleene aggregation with an LLM that reads the leaf results and decides. All systems share the same retriever, the same reader model, a matched cap on generated tokens and LLM calls, and the same development set for tuning prompts and thresholds.
Why not just…?
Why not just ask a strong model whether the context is sufficient? Direct prompting is the cheapest option, and the existing evidence is mixed rather than damning. Prompted GPT-4 reached 63.4% response-level and 28.3% span-level F1 on RAGTruth, well below a fine-tuned detector. FacTool reports that self-checking without tools has weak sensitivity. Neither result tests sufficiency on qualifier omissions, though. The naive baseline does exactly that on SufficientFacts and on our controlled HOVER deletions. If it matches the program on adverbial omissions, the core claim is wrong.
Why not just let PROGRAMFC's verify step output NEI and let the model combine the results? This is the most serious threat. It may capture most of the benefit with less machinery. The third ablation (LLM aggregation over three-valued leaves) and the first ablation (sub-questions without qualifier slots) are designed to settle it. Our prediction is that aggregation style matters little and slot enumeration matters a lot. If both differences are small, the honest conclusion is that three-valued leaves are enough, and we would report that result.
Why not just fine-tune an encoder on omission-augmented data? This is the strongest existing method, and it needs no code execution. Its limits are that it scores a fixed claim–evidence pair. It cannot say which fact is missing, and it does not interact with retrieval, so it cannot tell a retrieval miss from a void. We compare it head-to-head on sufficiency accuracy. The explanation and diagnosis experiments measure capabilities it lacks by design.
Why not just threshold the retriever or reranker score? A high similarity score for the first hop says nothing about whether the bridge entity for later hops was found. Retrieval recall on HOVER falls from 80% at 2 hops to 15% at 4 hops (HoVer). Similarity scores can also be gamed by topical poison passages (Reranker Helps, but Not Enough). We include the threshold as a baseline tuned on the development set and report it on the deletion splits, where a topically similar document survives while the needed sentence has been removed.
Proposed Experiments
The first experiment tests the qualifier blind spot. SufficientFacts provides 1,000 human-verified omission instances. We report sufficiency accuracy for each omission type (adverb, date, noun modifier, sentence), plus enumeration recall: the fraction of instances where the generated program declared a variable for the omitted element. If enumeration recall is high but accuracy is low, the binding check is the bottleneck. If both are low, slot enumeration does not work.
The second experiment is three-way verification with realistic retrieval. We use FEVER and FEVEROUS-S, both of which have native NEI labels, and report macro-F1 together with per-class NEI precision and recall. A useful contrast here: FEVER's own baselines scored 50.91% accuracy when ignoring evidence and 31.87% when given it (FEVER). This shows how easily claim-only shortcuts can hide failures of evidence use, so we also report claim-only controls.
The third experiment is the decisive check for diagnosis, built on HOVER. HOVER merges Refuted and NEI, so we construct controlled NEI variants of Supported 2-, 3- and 4-hop claims in two ways. In the hidden condition, one gold evidence sentence stays in the corpus but is demoted out of the initial top-k. In the void condition, it is deleted from the corpus entirely. A system that separates the two causes should recover and correctly verify most hidden-condition claims after re-query. It should keep void-condition claims at Unknown without inventing a binding. Its reported missing variable should match the deleted hop, which we can check automatically because we know which sentence was removed. The fabrication rate on the void condition is the hallucination measure we care most about.
The final experiment checks transfer to generated answers. We apply the slot check to RAGTruth responses, treating each unbound variable in a response's claims as a candidate baseless span, and compare against the 52.7% and 28.3% span-F1 reference points. Throughout, we report LLM calls and latency per claim, since the cost of iterative orchestration is a known weakness of program-guided methods. Any accuracy gain will be presented next to that cost.
References
- An End-to-End Multi-task Learning Model for Fact Checking
- Fact Checking with Insufficient Evidence
- Fact-Checking Complex Claims with Program-Guided Reasoning
- Pelican: Correcting Hallucination in Vision-LLMs via Claim Decomposition and Program of Thought Verification
- RLSeek: Evidence-Grounded Reasoning for RAG Hallucination Detection
- FacTool: Factuality Detection in Generative AI -- A Tool Augmented Framework for Multi-Task and Multi-Domain Scenarios
- Improving Large-Scale Fact-Checking using Decomposable Attention Models and Lexical Tagging
- RAGTruth: A Hallucination Corpus for Developing Trustworthy Retrieval-Augmented Language Models
- Unveiling Confirmation Bias in Chain-of-Thought Reasoning
- FEVEROUS: Fact Extraction and VERification Over Unstructured and Structured information
- HoVer: A Dataset for Many-Hop Fact Extraction And Claim Verification
- Reranker Helps, but Not Enough: Towards Strong Poisoning Attacks Against Retrieval-Augmented Generation
- FEVER: a Large-scale Dataset for Fact Extraction and VERification