Fact-Checking Complex Claims with Program-Guided Reasoning (2023)

Abstract: 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 .

## introduction the proliferation of disinformation, e.g., in social media, has made automated fact-checking a crucial application of natural language processing (nlp). given a claim, the goal is to find evidence and then to make a verdict about the claim's veracity based on that evidence @xcite @xcite . evaluating the veracity of real-world claims often involves collecting multiple pieces of evidence and applying complex reasoning @xcite @xcite . for instance, consider the claim "both james cameron and the director of the film interstellar were born in canada". it may be challenging to find direct evidence on the web that refutes or supports this claim. instead, a human fact-checker needs to decompose the claim, gather multiple pieces of evidence, and perform step-by-step reasoning @xcite , as illustrated in figure 1 . this makes verifying complex claims much more challenging than the typical setting explored in previous work, where information from a single article is sufficient to support/refute the claim @xcite @xcite @xcite . besides multi-step reasoning, we still need to consider two key aspects for developing a reliable fact-checking system: (i) explanability: the model should not only predict the veracity of the claim, but it should also provide a clear explanation of its reasoning process to help users understand and trust the results. (ii) data efficiency: human annotation is often time-consuming, costly, and potentially biased, making it difficult to collect sufficient highquality labeled data for model training, particularly for complex claims. therefore, it is desirable to build a model that can perform well with minimal or no training data. despite a few models @xcite @xcite being proposed to facilitate multi-step reasoning in fact-checking, they either lack explainability in their reasoning process or require a large number of task-specific training examples. in this paper, we present program-guided fact-checking (programfc), a novel fact-checking framework that is both explanatory and dataefficient. figure 1 illustrates our approach. to verify complex claims, programfc decomposes them into simpler sub-tasks that can be solved using a shared library of specialized sub-task functions. to be specific, programfc begins by generating a reasoning program for the input claim, which is a sequence of sub-tasks (e.g., s1-s4 in figure 1 ) in the form of @xcite , where action and argument define the type and the content of the sub-task, respectively. claim: both james cameron and the director of the film interstellar were born in canada. gold evidence open-book closed-book question [who is the director of the film interstellar?] verify [james cameron was born in canada.] verify [ {answer_1} was born in canada.] the generated reasoning program serves as a step-by-step guide for verifying the claim. we then execute the program by sequentially delegating each sub-task to the corresponding sub-task handler, as shown in the functions columns in figure 1 . these sub-tasks may include answering questions, verifying simple claims, or conducting logical reasoning. programfc combines explainability with data efficiency. it uses reasoning programs to provide clear explanations of its reasoning process. for data efficiency, large language models (llms) can solve various tasks given only a few examples as prompts, e.g., in-context learning @xcite . we leverage this ability of llms to generate reasoning programs for a given claim by showing the model just a few dozen of (claim, program) pairs as demonstrations. programfc is also flexible as it allows for easy swapping of subtask function implementations to work under different settings of fact-checking, without affecting the rest of the system. we can allow the functions to retrieve information from external sources (in an open-book setting) or we can ask them to generate answers based solely on the llm's internal parametric knowledge (in a closed-book setting). we evaluate programfc on two challenging datasets designed for fact-checking complex claims: hover @xcite and fever-ous @xcite , and we show that it outperforms seven few-shot fact-checking baselines on both datasets ( § 4.1). the strategy of program-guided reasoning becomes increasingly effective as the required reasoning depth increases ( § 4.1). in the open-domain setting, we find that reasoning programs can enhance the retrieval of relevant evidence from knowledge sources ( § 4.2). moreover, programfc is robust even when we use weak models as sub-task solvers ( § 4.2). we also evaluate the interpretability of the reasoning programs through human evaluation and error analysis ( § 4.3). ## related work fact-checking. automated fact-checking has gained significant attention in the nlp research community in recent years as a means of combating misinformation and disinformation. various datasets have been proposed that enable the development and the evaluation of systems for automatic fact-checking, the most popular ones being based on human-crafted claims from wikipedia content @xcite @xcite and naturally occurring claims in the political or in the scientific domain @xcite @xcite @xcite @xcite . notably, most of these datasets are constructed in a way that the evidence to support or to refute a claim can be found in a single document. for example, in fever @xcite , more than 87% of the claims only require information from a single wikipedia article @xcite . to bridge this gap, datasets have been proposed to study fact-checking complex claims that require multi-step reasoning @xcite . graph-based models @xcite @xcite @xcite are used to facilitate the reasoning over multiple pieces of evidence. although such models achieve sizable performance gains, they lack explanability and thet rely on large amounts of training data. to address the above problems, we propose an explainable, flexible, and data-efficient model that generates reasoning graphs as explanations and utilizes incontext learning to enable few-shot learning. explanation generation. facing the complexities of real-world claims, simply giving a final veracity to a claim often fails to be persuasive @xcite . previous research has proposed various approaches to provide post-hoc explanations for model predictions, such as using attention weights to highlight relevant parts of the evidence @xcite @xcite , generating justifications with logic-based systems based on knowledge graphs @xcite , and generating a summary of the retrieved relevant evidence @xcite @xcite . in contrast, we propose to use reasoning programs to provide explanations that consist of sub-tasks described in a program-like natural language. this offers several advantages: it allows for explanations that are not confined to the evidence, like attention weights, it is more flexible than logic-based explanations, and it is more concise than free-form summarization. chain-of-thought reasoning. moreover, unlike previous work that generates post-hoc explanations, we also use reasoning programs as guidance for predicting the veracity of the claim. this is motivated by the recent success of chain-of-thought prompting (cot) @xcite @xcite , which generates step-bystep natural language reasoning steps to guide the model in answering complex questions. we adopt this idea to fact-checking complex claims. unlike the original cot, which uses a single llm for both decomposition and question answering, we use the language model only to generate reasoning programs as the blueprint for problem-solving, and we delegate each sub-task to specialized functions. this approach reduces the burden on the language model and allows for more flexibility in incorporating necessary components for factchecking such as an evidence retriever. the strategy of program-guided reasoning is also in line with the recent trend of tool-augmented language models @xcite , i.e., augmenting language models with access to external tools and resources. ## programfc we first formulate the problem of fact-checking and then we introduce our proposed model for program-guided fact-checking (programfc). ## experiments datasets. most fact-checking datasets consist primarily of simple claims that can be substantiated through a single piece of evidence. however, here we focus on complex claims that need multi-step reasoning. given this context, we opt to evaluate our model on the only two datasets that, to the best of our knowledge, fulfill these criteria: hover @xcite and feverous @xcite . we use the validation sets for evaluation since the test sets are not publicly released. hover contains claims that require integration and reasoning over multiple wikipedia articles. we divide its validation set into three subsets based on the number of "hops" required to verify the claim: 1,126 two-hop claims, 1,835 three-hop claims, and 1,039 four-hop claims. feverous focuses on fact-checking complex claims over unstructured and structured data, where each claim is annotated with evidence in the form of sentences and/or cells from tables in wikipedia. since we focus on textual fact-checking, we only selected claims that require exclusively sentence evidence, constituting 2,962 claims. we call this subset feverous-s. for evaluation in the open-book setting, we use the corresponding wikipedia corpus constructed for these two datasets as the knowledge sources. hover uses the october 2017 wikipedia dump processed by @xcite , consisting of the introductory sections of 5.2 million wikipedia pages. feverous uses the december 2020 dump, including 5.4 million full wikipedia articles. baselines. we compare programfc to seven baselines, categorized into three groups. (i) pretrained models: bert-fc @xcite and list5 @xcite are two models that leverage bert and t5 for fact verification, respectively. (ii) fc/nli fine-tuned models: we choose three pretrained models that are fine-tuned on other fact-checking datasets or natural language inference (nli) datasets. roberta-nli @xcite few-shot learning. we study few-shot learning where only a few in-domain examples are available. therefore, for a fair comparison, we restrict all models to have access to only 20 examples from hover or feverous-s. we use these examples either for fine-tuning pre-trained models (bert-fc and list5), for continuous fine-tuning the fc/nli fine-tuned models, or as in-context examples for flan-t5 and codex. for programfc, we use them as in-context examples for reasoning program generation. we evaluate both the gold evidence setting and the open-book setting. the baseline models are the same for both settings. however, during testing in the open-book setting, the models are given the retrieved evidence rather than the ground-truth evidence. we use bm25 @xcite implemented with the pyserini toolkit @xcite as the retriever for both programfc and the baselines. we use as evidence the top-10 paragraphs retrieved from the knowledge corpus. ## conclusion and future work we proposed programfc, a few-shot neurosymbolic model for fact-checking that learns to map input claims to a reasoning program consisting of a sequence of sub-task function calls for answering a question, for fact-checking a simple claim, and for computing a logical expression. then factchecking is performed by executing that program. programfc combines the advantages of symbolic programs, such as explainability, with the flexibility of end-to-end neural models. using codex as the program generator, programfc demonstrates promising performance on hover and feverous with only a small number of incontext demonstrations and no additional training. we also investigated the impact of model size and the benefits of programs for retrieval, and we analyzed the errors. the results indicated that pro-gramfc effectively balances model capability, learning efficiency, and interpretability. in future work, we want to adapt programfc to more real-world fact-checking scenarios, such as fake news detection and multi-modal fact-checking, with advanced reasoning program design and subtask functionalities.