PaperlayerView exact revision on arXiv

Source-linked AI summary

Fact-Checking Complex Claims with Program-Guided Reasoning

Liangming Pan, Xiaobao Wu, Xinyuan Lu, Anh Tuan Luu, William Yang Wang, Min-Yen Kan, Preslav Nakov

arXiv:2305.12744v1cs.CLcs.AI

TL;DR

Complex fact-checking claims require multiple evidence pieces and multi-step reasoning. ProgramFC generates reasoning programs with few-shot in-context learning and executes their steps through specialized functions. It outperforms seven few-shot baselines on HOVER and FEVEROUS, while limitations remain for claims requiring implicit reasoning and world knowledge.

  • Problem

    Complex real-world claims require collecting multiple evidence pieces and applying multi-step reasoning, while existing approaches may lack explainability or require many task-specific examples.

  • Method

    ProgramFC decomposes complex claims into sequential reasoning programs and executes each step through corresponding specialized sub-task functions.

  • Results

    ProgramFC outperforms seven few-shot fact-checking baselines on both HOVER and FEVEROUS, with reasoning increasingly effective as required depth increases.

  • Takeaways & Limitations

    Explicit reasoning programs provide explanations of the verification process and support data-efficient fact-checking with few in-context demonstrations.

  • Takeaways & Limitations

    The Codex-based generator struggles with implicit complex claims that require deeper understanding and world or commonsense knowledge.

Abstract

from arXiv · show

Fact-checking real-world claims often requires collecting multiple pieces of evidence and applying complex multi-step reasoning. In this paper, we present Program-Guided Fact-Checking (ProgramFC), a novel fact-checking model that decomposes complex claims into simpler sub-tasks that can be solved using a shared library of specialized functions. We first leverage the in-context learning ability of large language models to generate reasoning programs to guide the verification process. Afterward, we execute the program by delegating each sub-task to the corresponding sub-task handler. This process makes our model both explanatory and data-efficient, providing clear explanations of its reasoning process and requiring minimal training data. We evaluate ProgramFC on two challenging fact-checking datasets and show that it outperforms seven fact-checking baselines across different settings of evidence availability, with explicit output programs that benefit human debugging. Our codes and data are publicly available at https://github.com/mbzuai-nlp/ProgramFC.

1 Introduction

ProgramFC targets complex fact-checking claims that require multiple evidence pieces and multi-step reasoning while addressing explainability and data-efficiency constraints. It generates and executes reasoning programs, outperforming seven few-shot baselines on two challenging datasets.

  • Motivation: Complex claims require decomposing the claim, gathering multiple evidence pieces, and performing step-by-step reasoning rather than relying on one supporting document.This makes their verification more challenging than typical single-document fact-checking.
  • Motivation: Existing multi-step fact-checking models either lack explainable reasoning processes or require many task-specific training examples.The paper frames explainability and data efficiency as key requirements for reliable systems.
  • Approach: ProgramFC generates a reasoning program that decomposes a claim into simpler sub-tasks, then executes each step through the corresponding specialized function.The program provides a step-by-step guide and supports sub-tasks such as question answering, simple-claim verification, and logical reasoning.
  • Approach: A few dozen claim-program demonstrations enable the LLM to generate reasoning programs without extensive task-specific training data.The framework uses in-context learning to generate programs and can swap sub-task implementations across fact-checking settings.
  • Results: PROGRAMFC outperforms seven few-shot fact-checking baselines on both HOVER and FEVEROUS.The evaluation covers datasets designed for complex claims and multi-step reasoning.
  • Results: Program-guided reasoning becomes more effective with greater reasoning depth, improves open-domain evidence retrieval, and remains robust with weak sub-task solvers.The paper also evaluates program interpretability through human evaluation and error analysis.

2 Related Work

Related work establishes that many fact-checking datasets use single-document evidence, while complex-claim datasets require multi-step reasoning. Prior approaches support reasoning or explanations but often sacrifice explainability, flexibility, or data efficiency.

  • Fact-Checking: Most established fact-checking datasets allow claims to be supported or refuted using evidence from a single document.In FEVER, more than 87% of claims require information from only one Wikipedia article.
  • Fact-Checking: Complex-claim datasets were introduced to study fact-checking that requires multiple evidence pieces and multi-step reasoning.Graph-based models have been used to facilitate reasoning over this evidence.
  • Fact-Checking: Existing graph-based approaches achieve sizable performance gains but lack explainability and rely on large amounts of training data.The paper positions its model as addressing these limitations with reasoning programs and in-context learning.
  • Explanation Generation: Prior explanation methods include highlighting relevant evidence with attention and generating post-hoc justifications using logic-based systems.These approaches explain predictions after model inference rather than necessarily guiding the verification process.
  • Chain-of-Thought Reasoning: Program-guided reasoning adapts chain-of-thought ideas to fact-checking by using reasoning programs to guide veracity prediction.The approach also aligns with tool-augmented language models that access external tools and resources.

3 PROGRAMFC

PROGRAMFC formulates fact-checking across gold-evidence, open-book, and closed-book settings, then generates and executes sequential programs composed of specialized function calls. The system uses Codex for program generation and sub-task modules for answering, verifying, and logical prediction.

  • 3.1 Problem Formulation: Fact-checking predicts a TRUE or FALSE label from a claim and knowledge source while also producing an explanation of the predicted veracity.The paper distinguishes gold-evidence, open-book, and closed-book knowledge settings.
  • 3.2 Program-Guided Reasoning: PROGRAMFC addresses complex claims in the few-shot setting through a program generation-and-execution paradigm.Only a small set of in-domain examples is assumed available.
  • 3.2 Program-Guided Reasoning: The planner generates sequential steps, each specifying a sub-task function, its argument, and a variable storing the returned result.A valid program ends with a Boolean value representing the claim’s veracity.
  • 3.2 Program-Guided Reasoning: The interpreter executes each step sequentially, passing arguments that may reference variables returned by earlier steps.Arguments can be logical expressions or natural-language questions and claims.
  • 3.3 Aggregating Reasoning Paths: Multiple candidate programs are executed and their predicted labels are combined by majority vote.The procedure uses diverse reasoning paths to aggregate validation outcomes.
  • 3.2 Program Generation: Codex generates Python-like reasoning programs from task instructions, in-context claim-program examples, and the input claim.The generator uses few-shot generalization rather than additional task-specific training.
  • 3.4 Sub-Task Functions: The execution library includes QUESTION for answering questions, VERIFY for binary claim verification, and PREDICT for logical expressions over previous variables.QUESTION uses FLAN-T5, with prompts varying by knowledge setting.

4 Experiments

Experiments evaluate PROGRAMFC in few-shot fact-checking across HOVER and FEVEROUS-S, using gold and retrieved evidence, and analyze performance, retrieval, model size, and reasoning-program errors.

  • Main Results: PROGRAMFC achieves the best performance on 7 out of 8 evaluations across HOVER and FEVEROUS-S.Evaluations cover gold-evidence and open-book settings for few-shot fact-checking.
  • Main Results: 10.38%, 11.37%, and 14.77% are PROGRAMFC’s average improvements over baselines on HOVER 2-hop, 3-hop, and 4-hop claims, respectively.The reported gains increase with the required reasoning depth.
  • Main Results: 6.0% and 4.5% are PROGRAMFC’s average improvements over direct FLAN-T5 verification in gold-evidence and open-book settings, respectively.For 4-hop claims, the improvements are 14.9% with gold evidence and 6.7% in the open-book setting.
  • How Does the Reasoning Program Help?: FLAN-T5-small with PROGRAMFC achieves comparable performance to end-to-end FLAN-T5-XXL on 4-hop claims despite using 80M versus 11B parameters.Program-guided reasoning reduces the burden on subsequent sub-task solvers, especially for smaller models.
  • How Does the Reasoning Program Help?: 37.1% is PROGRAMFC’s largest retrieval recall@10 improvement over one-step retrieval, observed on HOVER 4-hop.Iterative retrieval combines paragraphs retrieved across reasoning steps and benefits from information revealed during reasoning.
  • Interpretability of Reasoning Programs: No syntax errors were found in sampled incorrect predictions, while semantic and structural program errors increased as claim complexity increased.For 2-hop claims, 71% of programs were correct; most remaining errors involved incorrect question-answering or fact-checking execution.

5 Conclusion and Future Work

PROGRAMFC is a few-shot neuro-symbolic fact-checking model that maps claims to executable reasoning programs, combining explainability with data efficiency. Results on HOVER and FEVEROUS indicate promising performance and effective balancing of model capability, learning efficiency, and interpretability.

  • Conclusion: PROGRAMFC maps input claims to sequences of sub-task function calls and performs fact-checking by executing the resulting reasoning programs.The sub-tasks support question answering, simple-claim fact-checking, and logical-expression computation.
  • Conclusion: PROGRAMFC combines symbolic-program explainability with the flexibility of end-to-end neural models.Using Codex as the program generator, it requires only a small number of in-context demonstrations.
  • Conclusion: PROGRAMFC demonstrates promising performance on HOVER and FEVEROUS with few-shot in-context demonstrations.The paper also reports benefits of programs for retrieval and analyzes model errors.
  • Conclusion and Future Work: The results indicate that PROGRAMFC effectively balances model capability, learning efficiency, and interpretability.Future work targets fake news detection and multi-modal fact-checking with more advanced program designs and subtask functionalities.

Limitations

The paper identifies two main limitations: benchmark claims often permit explicit decompositions, while implicit claims demand deeper understanding and knowledge access; the framework also incurs substantially higher computational cost.

  • HOVER and FEVEROUS claims mostly require explicit multi-step reasoning, making their reasoning programs easier to generate.Their decompositions can often be derived from claim syntax or framing.
  • Implicit complex claims require deeper claim understanding and access to world and commonsense knowledge.
  • Preliminary experiments found that the Codex-based generator struggled to produce correct programs for implicit complex claims.The paper identifies this as a gap in applying PROGRAMFC to real-world claims.
  • PROGRAMFC requires approximately 4–5× more computational time than an end-to-end FLAN-T5 model.The additional cost comes from program generation and multiple sub-task model calls.

Ethics Statement

The ethics statement notes potential biases in training data and factuality judgments, possible misuse by malicious actors, and environmental costs from GPU-based language-model computation.

  • Biases may exist in the data used to train the LLMs and in some factuality judgments.The paper states that both sources of bias are beyond the authors’ control.
  • The models may interest the public and save human fact-checkers time, but malicious actors could misuse them.The authors therefore ask researchers to exercise caution.
  • Using large language models requires substantial computation and GPU/TPU resources, contributing to global warming.The authors note that few-shot in-context learning reduces, but does not eliminate, this concern.

A Implementation Details about the Baselines

The baseline implementation study organizes few-shot fact-checking systems into categories and describes pretrained Transformer baselines trained or configured using limited examples and evidence inputs.

  • The study categorizes few-shot fact-checking baselines into three groups: fine-tuning, in-context learning, and pretrained models.
  • Pretrained-model baselines use BERT or T5 and are fine-tuned on 20 randomly sampled HOVER or FEVEROUS training examples.Training is repeated 10 times with different random seeds, and validation performance is averaged.
  • BERT-FC concatenates the claim and evidence, then predicts the claim’s veracity with binary classification.The implementation uses bert-large-uncased with 345M parameters.
  • LisT5 concatenates candidate evidence sentences and fine-tunes T5-large to classify claims as Supported or Refuted.

A.2 FC/NLI Fine-Tuned Models

The fine-tuned FC/NLI baselines adapt pretrained language models to claim verification, using prior NLI or fact-checking training to support complex-claim evaluation.

  • Fine-tuned FC/NLI models are pretrained Transformers adapted to fact-checking or natural language inference tasks.Their additional training is intended to support generalization to complex claims during few-shot fine-tuning.
  • RoBERTa-NLI combines four NLI datasets before further fine-tuning on 20 HOVER or FEVEROUS examples.
  • DeBERTaV3-NLI is trained on FEVER hypothesis–premise pairs plus four NLI datasets.The passage identifies it as the best-performing NLI model on HuggingFace as of 06/06/2022.
  • MULTIVERS uses LongFormer for claim verification to address long-input evidence.The selected checkpoint was fine-tuned on FEVER.

A.3 In-Context Learning Models

The section compares in-context learning baselines for fact-checking, using Codex and FLAN-T5 under matched demonstration settings. The comparisons aim to make evaluation fair by aligning prompts and, for FLAN-T5, model size.

  • Motivation: The baselines are motivated by the strong few-shot learning ability recently demonstrated by large language models across NLP tasks.The paper uses in-context demonstrations to support task learning without conventional task-specific training.
  • Codex baseline: Codex generates reasoning programs for ProgramFC, while a baseline uses Codex directly to classify claims as true or false.Both approaches receive the same 20 in-context examples before their prompts.
  • FLAN-T5 baseline: FLAN-T5 is an instruction-fine-tuned T5 variant evaluated for zero-shot and few-shot in-context learning.The model was fine-tuned on 1.8K instruction-formulated tasks, including reasoning and question-answering.
  • Matched evaluation: The FLAN-T5 baseline uses the same prompt format and 20 in-context examples as ProgramFC.The comparison also uses the same FLAN-T5-XXL 3B model size as ProgramFC.

B Examples of Generated Reasoning Programs

ProgramFC generates reasoning programs covering diverse reasoning chains, illustrated through six examples in Figure 7.

  • Generated programs: Figure 7 presents six generated reasoning programs from ProgramFC.The examples are intended to illustrate the model's generated reasoning behavior.
  • Generated programs: The six examples cover diverse reasoning chains rather than a single fixed decomposition pattern.This diversity is stated as the organizing characteristic of the examples.
  • Generated programs: The figure provides concrete examples of ProgramFC's generated programs for inspecting its reasoning chains.These examples make the program outputs directly available for examination.

C Error Analysis for Reasoning Programs

The examples show how generated programs decompose claims with Question, Verify, and Predict operations, while error analysis identifies logical, resolution, decomposition, and redundancy failures. The prompts and examples also illustrate both compound and question-driven verification patterns.

  • Error analysis: The error analysis reports five erroneous program cases, including an incorrect final logical operator and failed co-reference resolution.The first error should negate the conjunction, while the second leaves references such as “This album” context-dependent.
  • Error analysis: Other errors produce trivial or insufficient decompositions, including repeating the claim or merely separating it into sentences.These failures are described as lacking meaningful or fine-grained reasoning structure.
  • Error analysis: A further error adds a redundant question that contributes no new information to the reasoning chain.The example asks when the musician was born without advancing the verification process.
  • Program generation: ProgramFC's generation prompt asks for a Python-like step-by-step verification program using Question(), Verify(), and Predict().Question answers a question, Verify checks a simple claim, and Predict produces the veracity label.
  • Program generation: Compound claims are represented by verifying separate facts and combining them with Predict(), as in the Howard University Hospital example.The example verifies each hospital's location before predicting the conjunction's label.
  • Program generation: Question-driven programs first retrieve an entity or value, then verify a claim containing that answer before prediction.Examples retrieve an arena, Formula 1 car, village, country, or person and use the result in a verification step.
Loading 2305.12744v1…