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

Verifying real-world claims can require collecting multiple pieces of evidence and applying complex reasoning. ProgramFC decomposes claims into sub-tasks executed through specialized functions, and it outperformed seven few-shot fact-checking baselines on HOVER and FEVEROUS.

  • Problem

    Fact-checking real-world claims can require collecting multiple pieces of evidence and applying complex reasoning.

    Source: §1 · p. 1

  • Method

    ProgramFC decomposes complex claims into sub-tasks, generates a reasoning program to guide verification, and executes it by calling corresponding specialized functions.

    Source: §1 · p. 1, §3.2 · p. 4

  • Results

    ProgramFC outperformed seven few-shot fact-checking baselines on both HOVER and FEVEROUS.

    Source: §1 · p. 2

  • Takeaways & Limitations

    In open-domain fact-checking, reasoning programs can enhance retrieval of relevant evidence from knowledge sources.

    Source: §1 · p. 2

    ProgramFC’s Codex-based generator struggled with implicit complex claims requiring deeper understanding and access to world and commonsense knowledge.

    Source: Limitations · p. 9

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 tackles complex fact-checking with explanatory, data-efficient reasoning programs that delegate verification steps to specialized functions. The paper reports that it outperforms seven few-shot baselines on two challenging datasets.

1 Introduction

  • Real-world claims often require multiple pieces of evidence and step-by-step reasoning, unlike settings where a single article suffices (Jiang et al., 2020; Nguyen et al., 2020; Aly and Vlachos, 2022; Chen et al., 2022a; Thorne et al., 2018; Saakyan et al., 2021; Schuster et al., 2021; Pan et al., 2021; Wadden et al., 2022a; Krishna et al., 2022).The introduction illustrates the challenge with a claim about James Cameron and the director of Interstellar being born in Canada.Source: §1 · p. 1
  • Earlier multi-step fact-checkers either lacked explainability or required many task-specific training examples, motivating a system that is both explanatory and data-efficient (Zhou et al., 2019; Zhong et al., 2020; Aly and Vlachos, 2022).The paper identifies clear explanations and minimal or no training data as desirable for reliable fact-checking.Source: §1 · p. 1
  • ProgramFC generates a sequence of ACTION[ARGUMENT] sub-tasks for a claim and executes them sequentially through specialized handlers.Tasks can include answering questions, verifying simple claims, or conducting logical reasoning.Source: §1 · pp. 1–2, Figure 1 · p. 2
  • ProgramFC uses LLM in-context learning with a few dozen claim-program examples and supports swappable functions for open-book retrieval or closed-book parametric answers.Changing sub-task function implementations does not affect the rest of the system.Source: §1 · p. 2
  • ProgramFC outperforms seven few-shot fact-checking baselines on HOVER and FEVEROUS.The paper also reports that program-guided reasoning becomes increasingly effective as required reasoning depth increases.Source: §1 · p. 2
  • In open-domain evaluation, programs improved relevant-evidence retrieval, remained robust with weak sub-task solvers, and were assessed for interpretability through human evaluation and error analysis.The paper also reports that program-guided reasoning becomes increasingly effective as required reasoning depth increases.Source: §1 · p. 2

2 Related Work

Prior fact-checking datasets often require evidence from one document, while complex-claim methods use graph reasoning but are described as less explainable and data-hungry. ProgramFC positions reasoning programs as both explanations and guidance for prediction.

Fact-Checking

  • More than 87% of FEVER claims require information from a single Wikipedia article, reflecting the single-document evidence scope of most fact-checking datasets.Datasets also include human-crafted Wikipedia claims and naturally occurring political or scientific claims.Source: §2 · p. 2
  • Graph-based methods facilitate multi-evidence reasoning for complex claims, but are described as lacking explainability and requiring large training datasets.The paper positions its model as generating reasoning graphs and using in-context learning for few-shot learning.Source: §2 · p. 3

Explanation Generation

  • Reasoning programs explain predictions through natural-language sub-tasks, offering explanations less constrained than attention weights, more flexible than logic-based explanations, and more concise than free-form summaries.Prior approaches include evidence attention, knowledge-graph-based justifications, and summaries of retrieved evidence.Source: §2 · p. 3

Chain-of-Thought Reasoning

  • Unlike chain-of-thought prompting that uses one LLM for decomposition and answering, ProgramFC uses the language model to generate a reasoning-program blueprint and delegates sub-tasks to specialized functions.This program-guided approach can incorporate external tools such as evidence retrievers and aligns with tool-augmented language models.Source: §2 · p. 3

3 PROGRAMFC

PROGRAMFC targets few-shot fact-checking of complex claims through generated reasoning programs that execute specialized sub-tasks, with multiple candidate programs combined by majority vote.

3.1 Problem Formulation

  • Fact-checking predicts a TRUE or FALSE label and an explanation, with the available knowledge source defining gold-evidence, open-book, and closed-book settings.The cited works associate claim verification with the gold-evidence setting (Pan et al., 2021; Wright et al., 2022), corpus retrieval with open-book fact-checking (Jiang et al., 2021; Wadden et al., 2022b), and parameter-stored knowledge with closed-book fact-checking (Lee et al., 2020, 2021).Source: §3.1 · p. 3

3.2 Program-Guided Reasoning

  • For complex claims in the few-shot setting, PROGRAMFC generates sequential reasoning steps, executes each through its assigned function, and takes a majority vote across candidate programs.Each step specifies a function, its argument, and a variable for the returned result; later steps can refer to earlier results, and the final step returns TRUE or FALSE.Source: §3.2 · pp. 3–4

3.3 Reasoning Program Generation

  • Codex generates reasoning programs from in-context claim-program examples; the system uses 20 examples and sampling-based decoding at temperature 0.7 to produce varied programs.The examples use a Python-like format in which each step is written as a function call assigned to a variable.Source: §3.3 · p. 4

3.4 Sub-Task Functions

  • The three sub-task functions are QUESTION for answering questions, VERIFY for returning TRUE or FALSE, and PREDICT for evaluating logical expressions over earlier variables.FLAN-T5 implements QUESTION and VERIFY; QUESTION prompts vary by fact-checking setting.Source: §3.4 · p. 4

4 Experiments

ProgramFC is evaluated on complex fact-checking benchmarks in few-shot, open-book, and closed-book settings. It performs best in most few-shot evaluations, while analyses show benefits from program-guided reasoning and identify challenges with longer reasoning chains.

4 Experiments

  • Evaluation uses HOVER validation claims split into 2-, 3-, and 4-hop groups and FEVEROUS-S, restricted to claims requiring sentence evidence.For few-shot evaluation, all models receive 20 in-domain examples; open-book testing uses the top 10 paragraphs retrieved with BM25 instead of gold evidence.Source: §4 · pp. 5–6

4.1 Main Results

  • PROGRAMFC achieves the best performance in 7 of 8 few-shot evaluations across HOVER and FEVEROUS-S.Table 1 reports macro-F1 scores for gold-evidence and open-book settings.Source: Table 1 · p. 6, §4.1 · p. 6
  • On HOVER, PROGRAMFC (N=5) beats baselines by 10.38%, 11.37%, and 14.77% on 2-, 3-, and 4-hop claims; its 4-hop performance drop is 11.7%, versus DeBERTaV3-NLI’s 21.7%.DeBERTaV3-NLI’s F1 falls from 77.22 on 2-hop claims to 60.49 on 4-hop claims.Source: §4.1 · p. 6
  • Compared with direct FLAN-T5 verification, PROGRAMFC improves average performance by 6.0% in gold-evidence and 4.5% in open-book settings; aggregating programs adds 1.5% on average.For 4-hop claims, the gains over direct FLAN-T5 verification are 14.9% with gold evidence and 6.7% open-book.Source: §4.1 · p. 6

4.2 How Does the Reasoning Program Help?

  • With FLAN-T5-small (80M) as subtask solvers, PROGRAMFC achieves comparable performance to end-to-end FLAN-T5-XXL (11B) on HOVER 4-hop claims.Program-guided reasoning is particularly effective with smaller language models, whose end-to-end reasoning performance falls more as model size decreases.Source: Figure 4 · p. 7, §4.2 · p. 7
  • Iterative program-guided retrieval improves recall@10 over one-step BM25 retrieval on all datasets, with the largest gain, 37.1%, on HOVER 4-hop.The retrieved paragraphs from all program steps are combined and evaluated as the top 10 results.Source: Figure 5 · p. 7, §4.2 · p. 7

4.3 Interpretability of Reasoning Programs

  • In an analysis of 300 incorrect HOVER predictions, no generated programs had syntax errors; 71% of 2-hop programs were correct, while semantic errors increased with claim complexity.Structural errors became particularly prevalent as reasoning chains lengthened; execution failures accounted for most errors among incorrect 2-hop programs.Source: §4.3 · pp. 7–8, Table 2 · p. 8

4.4 Closed-Book Fact-Checking

  • In closed-book evaluation, most models score only slightly above random on HOVER; chain-of-thought prompting averages 2.7 points above direct prompting, but loses to PROGRAMFC on HOVER 3- and 4-hop claims.Chain-of-thought beats PROGRAMFC on HOVER 2-hop and FEVEROUS, while the paper attributes its long-chain weakness to unpredictable errors from free-form explanations; program generation and execution are more stable for longer chains.Source: Table 3 · p. 8, §4.4 · pp. 8–9

5 Conclusion and Future Work

PROGRAMFC maps claims to executable reasoning programs, combining symbolic-program explainability with neural-model flexibility; it showed promising performance on HOVER and FEVEROUS with few in-context demonstrations and no additional training. The authors propose extending it to real-world scenarios including fake-news detection and multimodal fact-checking.

5 Conclusion and Future Work

  • PROGRAMFC showed promising performance on HOVER and FEVEROUS using only a small number of in-context demonstrations and no additional training.The authors also investigated model size, programs’ benefits for retrieval, and errors; they concluded that PROGRAMFC balances model capability, learning efficiency, and interpretability.Source: §5 · p. 9
  • PROGRAMFC maps input claims to sequences of sub-task function calls for answering questions, fact-checking simple claims, and computing logical expressions, then verifies claims by executing the program.The few-shot neuro-symbolic model combines the explainability of symbolic programs with the flexibility of end-to-end neural models.Source: §5 · p. 9
  • Future work aims to adapt PROGRAMFC to fake-news detection and multimodal fact-checking through advanced reasoning-program design and sub-task functionalities.Source: §5 · p. 9

Limitations

PROGRAMFC has two stated limitations: generating programs for implicit real-world reasoning is difficult, and its computational cost is higher than that of end-to-end models.

Limitations

  • HOVER and FEVEROUS claims mostly require explicit reasoning derivable from syntax or framing, but Codex struggled to generate correct programs for implicit real-world claims.Such claims require deeper understanding and world and commonsense knowledge; addressing this gap is a direction for future work.Source: Limitations · p. 9
  • PROGRAMFC takes ∼4-5× the computational time of an end-to-end FLAN-T5 model because it calls large language models for program generation and multiple sub-task models.Developing more efficient program generation and execution methods is a direction for future work.Source: Limitations · p. 9

Ethics Statement

The authors acknowledge potential biases in training data and factuality judgments, warn that the models could be misused, and note their computational environmental costs despite using few-shot in-context learning.

Biases

  • The authors note that biases in LLM training data and factuality judgments may affect the work, and that both are beyond their control.Source: Ethics Statement · p. 9

Intended Use and Misuse Potential

  • The models could save human fact-checkers time and interest the general public, but could also be misused by malicious actors; researchers are urged to exercise caution.Source: Ethics Statement · p. 9

Environmental Impact

  • LLM use requires substantial computation and GPU/TPU training that contributes to global warming; although the authors use few-shot learning rather than training from scratch, Codex likely runs on a GPU.Source: Ethics Statement · p. 9

A Implementation Details about the Baselines · A.1 Pre-trained Models

The appendix describes seven baselines organized into three categories; this subsection details two pretrained-model baselines and their few-shot evaluation setup.

A Implementation Details about the Baselines

A.1 Pre-trained Models

  • The pretrained baselines are fine-tuned on 20 randomly sampled HOVER or FEVEROUS training examples, with validation performance averaged across 10 random seeds.Source: §A.1 · p. 14
  • BERT-FC concatenates the claim and evidence as [CLS] claim [SEP] evidence and uses binary classification to predict claim veracity.The implementation uses HuggingFace’s bert-large-uncased model with 345M parameters.Source: §A.1 · p. 14
  • LisT5 uses pretrained T5 as its sequence-to-sequence backbone and applies listwise concatenation to combine candidate evidence sentences into one input.Source: §A.1 · p. 14
  • For LisT5 label prediction, the t5-large model is trained to classify claims directly as Supported or Refuted.Source: §A.1 · p. 14
  • The authors use LisT5’s original implementation.Source: §A.1 · p. 14

A.2 FC/NLI Fine-Tuned Models

This category comprises pretrained Transformers fine-tuned on single-hop fact-checking or NLI data to improve simple-claim fact-checking and generalize to complex claims through few-shot fine-tuning.

A.2 FC/NLI Fine-Tuned Models

  • These pretrained Transformer models are fine-tuned on single-hop fact-checking or NLI datasets, which helps them handle simple claims and generalize to complex claims during few-shot fine-tuning.Source: §A.2 · p. 14
  • RoBERTa-NLI (Nie et al., 2020) was fine-tuned on four NLI datasets and further fine-tuned using 20 random HOVER/FEVEROUS examples.The four datasets were SNLI, MNLI, FEVER-NLI, and ANLI (R1, R2, R3).Source: §A.2 · p. 14
  • DeBERTaV3-NLI was trained on 885,242 FEVER hypothesis–premise pairs and four NLI datasets, and was HuggingFace’s best-performing NLI model as of 06/06/2022.The four datasets were MNLI, ANLI, LingNLI, and WANLI (Liu et al., 2022).Source: §A.2 · p. 14
  • MULTIVERS (Wadden et al., 2022b), formerly LongChecker, uses LongFormer to address long evidence inputs, with a checkpoint fine-tuned on FEVER.LongFormer is attributed to Beltagy et al. (2020).Source: §A.2 · p. 14

A.3 In-Context Learning Models

This section defines two in-context-learning fact-checking baselines and the prompting controls used to compare them fairly with ProgramFC.

A.3 In-Context Learning Models

  • Codex (Chen et al., 2021) is evaluated directly for fact-checking with an evidence-and-claim True/False prompt prefixed by the same 20 demonstrations used for ProgramFC.The prompt asks whether the claim is true based on the evidence.Source: §A.3 · p. 14
  • FLAN-T5 (Chung et al., 2022), instruction-fine-tuned on 1.8K tasks, uses the Section 3.4 prompt format, the same 20 examples, and FLAN-T5-XXL 3B to match ProgramFC’s model size.The prompt asks whether the claim is true based on the evidence.Source: §A.3 · p. 15

B Examples of Generated Reasoning Programs

Figure 7 presents six examples of ProgramFC-generated reasoning programs that span diverse reasoning chains.

B Examples of Generated Reasoning Programs

C Error Analysis for Reasoning Programs … Self-Ask Prompting

This appendix section examines generated reasoning programs through examples of common errors and Self-Ask Prompting. It also provides prompts for program generation and closed-book fact-checking, including the Program Generation prompt for FEVEROUS-S.

C Error Analysis for Reasoning Programs

  • Examples show generated programs using the wrong final logic operator, failing to resolve co-references, producing trivial decompositions that repeat or sentence-split claims, and adding a redundant birth-date question with no new information.Source: C Error Analysis for Reasoning Programs · p. 15

Direct Prompting

  • Direct prompting asks whether a claim is true or false and supplies in-context examples before an input-claim template.Source: Direct Prompting · p. 15

ZS-CoT Prompting

  • Zero-shot CoT asks whether the input claim is true or false and prompts the model to think step by step.Source: ZS-CoT Prompting · p. 15

CoT Prompting

  • CoT prompting adds step-by-step reasoning to the true-or-false question, with an example that states intermediate facts before its answer.Source: CoT Prompting · p. 15

Self-Ask Prompting

  • Self-Ask prompting breaks a true-or-false claim into explicit questions and answers before giving a final answer.Its example identifies who the story behind Girl Crazy is credited to, then compares that person’s age with Ted Kotcheff’s.Source: Self-Ask Prompting · p. 15
  • The program-generation prompt directs the model to build a stepwise, Python-like verification program using Question(), Verify(), and Predict().Examples verify separate facts and predict their conjunction, or ask a question for an intermediate entity before verifying a related claim.Source: Self-Ask Prompting · p. 18
  • The examples decompose claims into separate Verify calls and combine them with Predict over a conjunction of the resulting facts.For example, the Maupihaa and Shulin programs each verify two component facts before predicting a label.Source: Self-Ask Prompting · p. 21
  • A four-part program checks Alfredo Cornejo Cuevas’s boxing background, medal, Games location and dates, and world amateur title as separate facts.The resulting checks cover the 1959 Pan American Games and the title in Mexico City.Source: Self-Ask Prompting · p. 22
  • The FEVEROUS-S prompt example ends with an <input_claim> placeholder for generating a program.The passage identifies this as the prompt used for Program Generation for FEVEROUS-S.Source: Self-Ask Prompting · p. 22

Related papers

Loading 2305.12744v1…