Minimal Evidence Group Identification for Claim Verification
Xiangci Li Sihao Chen Rajvi Kapadia Jessica Ouyang Fan Zhang

Understanding and Improving CNNs with Complex Structure Tensor: A Biometrics Study
    Josef Bigun, Fernando Alonso-Fernandez
    April 29, 2024
==================================================================================

* Work performed while the authors are interning at Googlefootnote



Claim verification in real-world settings (e.g. against a large collection of candidate evidences retrieved from the web) typically requires identifying and aggregating a complete set of evidence pieces 

that collectively provide full support to the claim.
The problem becomes particularly challenging when there exists distinct sets of evidence that could be used to verify the claim from different perspectives. In this paper, we formally define and study the problem of identifying such minimal evidence groups (MEGs) for claim verification. 
We show that MEG identification can be reduced from Set Cover problem, based on entailment inference of whether a given evidence group provides full/partial support to a claim.  Our proposed approach achieves 








18.4% & 34.8% absolute improvements on the WiCE and SciFact datasets over LLM prompting.
Finally, we demonstrate the benefits of MEGs in downstream applications such as claim generation.











§ INTRODUCTION
 








The task of claim verification predicts whether a claim is supported by the presented evidence <cit.>. 
A claim verification model is expected to identify the correct evidence pieces (EPs; e.g. evidence sentences or snippets) among tens of retrieved candidate evidence, but a practical challenge lies in that there might exist multiple sets of evidence that verify the claim from different perspectives. Figure <ref> shows an example where, given a claim and some retrieved evidence, there exist two different — but both valid — ways of supporting the claim. 



While humans can quickly identify mutually redundant EPs, e.g. e_1 and e_3 in Figure <ref>, and propose plausible combinations of EPs as evidence groups (EGs, formally defined in Section <ref>), existing claim verification systems <cit.> focus only on the relationship between the claim and individual EPs, without considering the co-supporting relationships among EPs. This becomes problematic because the retrieved EPs might be redundant, or an individual EP may only partially support the claim. An EG with redundant EPs makes it more difficult to explain the reasoning for supporting the claim, while an EG composed of partially supporting EPs may still not fully support the claim, resulting in logical flaws. These problematic outputs not only confuse human verifiers, but also hurt the performance of downstream tasks.

In this paper, we introduce the problem of identifying minimal evidence groups (MEGs) from retrieved evidence candidates. 
Conceptually, an MEG is composed of EPs with the following properties: (1) Sufficiency: each MEG fully supports the veracity of the claim; (2) Non-redundancy: the EPs in an MEG are not redundant with each other; and (3) Minimality: the number of EPs in each MEG is minimal. 
We formally define the task of MEG identification 
and show that classic claim verification approaches cannot effectively solve this problem. We propose a simple yet practical approach to decompose it to support prediction and evidence group merging. Our proposed approach significantly outperforms the baseline of directly prompting a large-language model (LLM) by 18.4% and 34.8% absolute precision scores on the WiCE <cit.> and SciFact <cit.> benchmarks. Finally, we demonstrate the benefit of MEGs for saving computation budget in the downstream task of claim generation. 







§ RELATED WORK
 










Classic claim verification <cit.> consists of three steps: evidence retrieval, evidence selection, and stance prediction. Evidence retrieval perform coarse-grained filtering of EPs from thousands of candidates. Evidence selection and stance prediction perform fine-grained selection of EPs and predict whether the claim is supported by the selected EPs. MEG identification builds on classic claim verification by restricting evidence selection and stance prediction to predict a minimal group of EPs that fully supports the claim. 

To address the problem that claim verification systems <cit.> may predict EPs that only partially support the claim, 
<cit.> aggregated individual EPs' entailment scores into EG scores. However, they did not address the problem of redundancy within an EG; we propose MEG identification to fill this gap.


The closest work to ours is SciFact <cit.>, which annotates “minimal evidence sets” for each claim. However, the SciFact shared task does not penalize non-minimal EGs, and consequently models that evaluate on SciFact
<cit.> are trained on the union of EGs from different human annotators, which is no longer minimal. Similarly, <cit.> collect (possibly redundant) EGs from multiple annotators and use their union as training labels.
As a result, existing models prioritize EP recall and are not directly comparable to MEG identification models.





§ MINIMAL EVIDENCE GROUPS



 §.§ Problem Formulation
 

MEG identification builds on the classic claim verification task <cit.>. Formally, claim verification takes a claim c and a list of candidate EPs E={e_1, e_2, ...} as input. The evidence selection step retrieves all EPs that are relevant to c, and the stance prediction step predicts whether the selected EPs support c[We limit our scope to claim support/non-support, ignoring contradictions for simplicity. See Section <ref> for discussion.]. 
In Figure <ref>, e_1, e_2, e_3 all support c. A set of fully supporting EPs is called an evidence group (EG).


MEG identification requires the EGs to be sufficient, non-redundant, and minimal. We consider a set of EPs S ⊆ E to fully or partially support a claim c if the EPs in S collectively entail all or only part of c, respectively; S does not support c if none of EPs in S entail c. If S fully supports c, it is an EG; an MEG is a minimal EG such that none of its EPs are redundant in terms of supporting c.
In Figure <ref>, e_1 and e_3 are redundant; {e_1, e_2} and {e_2, e_3} are MEGs that fully support c.



 §.§ Task Evaluation
 
We focus on precision-oriented scores (precision and F_0.5) to penalize predicting non-minimal EGs because we observe from prior claim verification datasets <cit.> that (1) one MEG is sufficient for claim verification in practice; (2) humans are good at finding one plausible MEG but struggle to exhaustively find all valid MEGs; and (3) different annotators propose distinct MEGs. 

Given a claim c with reference MEGs RG={G_1, G_2, ...}, we measured the following metrics:

Exact match of MEGs treats each reference MEG atomically and considers a predicted MEG to be correct if it exactly matches a reference MEG. 



Best soft match of MEGs gives partial credits to the predicted MEGs. We calculate the EP-level scores between the predicted MEG G' and the most similar reference MEG chosen by Ĝ=_G_i∈ RG F_0.5(G', G_i).











§ MEG IDENTIFICATION APPROACH
 

The challenge of MEG identification is to find the smallest set of EPs that fully supports the claim. As discussed in Section <ref>, classic claim verification models treat the EP as the basic unit; they are neither designed nor trained for groups of evidence. 

Our experiments of prompting directly with LLMs also show poor performance (Table <ref>, “Direct”)
[The explicit verification of combinations of EPs reduces from Set Cover and is NP-hard (see proof in Appendix <ref>.)]. 

As Algorithms <ref> shows, 
we decompose MEG identification into two steps: (1) predicting whether a candidate set of EPs fully supports, partially supports, or does not support the claim and (2) bottom-up merging partially supporting groups in search of a fully supporting group.

The support prediction Model can be implemented by any reasonable approach, such as prompting LLMs or fine-tuning models like T5 <cit.>.
When merging groups, we increment the overall group size by 1 at each step.

Note that if we only evaluate the base case with size=1, this is equivalent to classic claim verification <cit.>. 

















Based on the definition of MEG (Section <ref>), we derive three principles to prune the problem space for a tractable solution:
(1) any superset of an MEG fully supports the claim c;
(2) any non-empty subset of an MEG partially supports c; 
and (3) if a set of EPs S fully supports or does not support c, then S is not a strict subset of any MEG.
Therefore, we stop merging sets that are predicted as fully supporting or not supporting to maintain the non-redundancy and minimality of the candidate EP sets. In addition, when choosing a pair of sets to merge, we prune the candidate merge partners for each set using a redundancy checker notRedundant (implemented as a zero-shot LLM prompt; see Appendix <ref>). Finally, upon finding a fully supporting set, we stop merging and return all fully supporting sets of the current size.




§ INTRINSIC EVALUATION
 


 §.§ Experimental Settings




  §.§.§ Datasets

We perform filtering to convert classic claim verification datasets to align with our MEG identification task. Both of the datasets listed below annotate EGs with multiple annotators. We assume that every human-annotated EG fully supports its claim, every subset of an EG partially supports its claim, and all non-labeled sentences do not support the claim. In addition, we assume each reference EG to be an MEG proposed by a different annotator.




  
SciFact <cit.> is a biomedical fact-checking dataset and is the only existing dataset whose annotation instructions match the sufficiency, non-redundancy, and minimality requirements of MEGs. We remove all examples whose claims contradict the evidence
, resulting in 268 samples from the development set. We use the non-contradictory EGs as-is. To distinguish it from the original SciFact dataset and task[As discussed in Section <ref>, while the SciFact dataset annotates EGs that meet the requirements of MEGs, the task does not evaluate redundancy or minimality, only sufficiency.], we call this modified dataset SciFact-MEG.



  
WiCE <cit.> distinguishes EGs that fully or partially support claims from Wikipedia. We use the subclaim-level partition of the dataset and only use samples labeled as fully supporting, resulting in 528 samples from the test set. We call this modified dataset WiCE-MEG.



  §.§.§ Implementation
 
For both the support prediction Model and notRedundant checker, we prompt PaLM-2L <cit.> with few-shot demonstrations and greedy decoding (see Appendix <ref>). We follow <cit.> to select the LLM's most confident examples for few-shot demonstrations. To prioritize precision, we take the top-1 predicted MEG, ranked according to the LLM's predicted fully supporting score, if multiple MEGs are predicted.



  §.§.§ Baseline Approaches
 
Direct prediction. We zero-shot prompt PaLM-2L <cit.> to predict the MEG via EP indices, given a claim and a list of candidate EPs (Appendix Table <ref>). 

Classic claim verification. To simulate classic claim verification without considering groups of EPs <cit.>, we use our proposed approach but early stop after computing size=1. If we find any fully supporting EP, the output MEG will be the same as our proposed approach. Otherwise, we concatenate all partially supporting EPs as a single EG.

Classic claim verification with less redundancy (Classic+LR). Given the output from “classic claim verification” above, we additionally remove EPs that cause redundancy, as predicted by the pair-wise nonRedundant checker[We simply remove redundant combinations when size=2.].





 §.§ Experimental Results





Table <ref> shows the top-1 MEG identification performance using the metrics introduced in Section <ref>. 


For both datasets, our approach significantly outperforms all baselines on precision and F_0.5 scores. The baselines underperform our approach because their predicted MEGs contain too many EPs, especially the “Direct" LLM prompting baseline. Decomposing MEG identification into many individual entailment problems (“Classic”) greatly improves the precision score. Further removing pair-wise redundancy (“Classic+LR") slightly improves performance, showing the impact of redundancy. Finally, although requiring significantly more computation, our bottom-up MEG identification approach performs the best because every combination of EPs is explicitly verified.








§ EXTRINSIC EVALUATION

The non-redundancy of MEGs not only makes the evidence more human-readable, it also improves the performance of downstream applications. Inspired by <cit.>, we use WiCE-MEG to highlight the MEG's minimality and sufficiency properties using claim generation as an example downstream task, with a computation budget measured in the number of words or sentences. 



 §.§ Experimental Settings
 
Since EGs fully entail their claims, they contain the information to reconstruct the claim. We compare the following input settings for the task of claim reconstruction using PaLM-2L <cit.>:

MEGs. We use the top-1 MEG obtained with our proposed approaches
, each baseline in Table <ref>, and the human-annotated reference EG with the smallest number of EPs for each claim. 

Union of EGs (UEGs). We take the union of reference EGs (from different annotators) for a claim. 

First-k. To simulate a low computation budget setting, we follow <cit.> in taking the first k EPs, where k is the size of the top-1 MEG.







 §.§ Experimental Results

Table <ref> shows that both our predicted and gold MEG settings perform comparably to settings with much lower computation budgets, while significantly outperforming the most constrained “first-k” settings. These results indicate that (1) our proposed approach for MEG identification is effective; (2) MEGs contain complete information for the claim generation task; (3) MEGs are much more compact than EGs from other approaches, with more than 45% fewer words, allowing them to be used in low-computation scenarios. 












§ CONCLUSION


We have addressed the challenging scenario in claim verification where a model is expected to identify a minimal group of evidence pieces (EPs) among a relatively large amount of candidate evidence, and there might exist different sets of evidence that verify the claim from different perspectives.
We formally define and study the problem of such minimal evidence group (MEG) identification and show that it can be reduced from a Set Cover-like problem. Our proposed approach achieves significant improvements over direct LLM prompting. Finally, we demonstrate the benefit of MEGs over classic claim verification approaches in downstream applications such as claim generation.



§ LIMITATIONS



  
Ignoring contradictions. In this work, we only consider supporting/non-supporting evidence for simplicity, and leave contradicting evidence for future work. Our proposed approach avoids the edge case of full/partial entailment problem brought by contradiction.


Nonetheless, we claim that contradiction can be regarded as the opposite of support, where our proposed concepts and approaches still apply with minor fix.





  
Reliability of human annotations. As we point out in Section <ref>, there is no gold-standard annotated dataset designed for this task, and it is practically difficult to enforce and verify the sufficiency, non-redundancy, and minimality requirements of MEGs in the existing annotations. In practice, unless explicitly stated, it is unknown whether the annotated EGs are simply relevant to or fully support the claim. Although human annotators are good at proposing salient EGs, annotators usually do not exhaustively find all possible EGs. Moreover, human annotators tend to over-select EPs for a better contextualization, which breaks the non-redundancy and minimality requirements. As a result, we argue that the human annotations should only be treated as a reference, instead of an absolute gold standard. 
Therefore, the measured performance in Table <ref> can should be regarded as each approach's agreement with the human annotators, and does not necessarily measure MEG correctness. 



  
Definition of partial support. It is challenging to precisely define partial support. Even <cit.>, who proposed this label, did not clearly define it. Our proposed approaches do not rely on the precise definition of partial support but simply regard it as the intermediate label between not support and fully support because the precise definition may vary case-by-case in different datasets that the support prediction Model is trained on. 
Because of this ambiguity, partial support is the most challenging label for LLMs to predict (Appendix <ref>) and hurts the performance of MEG identification.



  
Running time. Due to the NP-hardness (Appendix <ref>) of the MEG identification problem, we trade off running time for higher performance, thus the worst case running time for the proposed solution is too long to be practically useful in a production system. Our proposed approach is currently more suitable for dataset creation, which requires a robust solution without strict running time requirements. We leave more efficient approaches for future work.



§ ETHICAL STATEMENTS

Similar to all prior claim verification works <cit.>, we stress that the MEG identification problem and the MEGs predicted by our proposed approach only consider the relative entailment relationship between the evidence and the claim. In other words, the MEG identification problem and our proposed approach do not guarantee the absolute correctness of the claim or the EPs or EGs themselves. Any future application must be cautious in distinguishing between retrieving evidence that supports the claim, correct or not, and verifying the absolute factual correctness of the claim.



acl_natbib


















§ PROOF OF NP-HARDNESS


In this section, we provide a simple proof to show that the MEG identification problem is NP-hard.



 §.§ Simplifying to an Ideal Scenario
 
Inspired by <cit.>, who break complicated claims into subclaims and verify each subclaim individually, we assume the solution of the MEG identification problem explicitly breaks down the claim c into one or more atomic claim units CU={cu_1, cu_2, ...} and verifies them one-by-one. Each claim unit cu can be more fine-grained or abstractive than the subclaims introduced by Kamoi et al. If all claim units cu_i ∈ CU are verified, then c is fully supported. Otherwise, if only a subset of CU is verified, then c is only partially supported. In an ideal scenario, we have a perfect model that is able to decompose c into CU and output a binary vector for each EP to indicate which cu_i are verified by the EP; this ideal MEG identification problem becomes the task of minimizing the number of selected EPs such that all elements in CU can be covered.



 §.§ Reduction from Set Cover

Based on the formulation in <ref>, we can trivially many-one reduce the Set Cover problem, which is NP-Complete <cit.>, to ideal MEG identification by mapping the universe to CU and the collection of subsets to the full set of EPs E={e_1, e_2, ...}. 
Therefore the ideal MEG identification problem is NP-Complete, and the actual MEG identification problem is NP-hard. Because the assumption of explicitly tracking which cu_i are covered/remaining is challenging for state-of-the-art models, it is difficult to develop approximation solutions for MEG identification.














§ BASE MODEL PERFORMANCE
 


  
Experimental settings. To assess the support prediction Model performance, we construct datasets of 2255 and 462 entailment examples respectively from WiCE test-set and SciFact dev-set. The sampled WiCE subset contains 1139, 322, 794 fully support, partially support, and do not support examples, respectively. We directly use the annotated EGs from fully and partially supporting examples as inputs and randomly sample 1∼3 EPs to serve as negative labels in not supporting examples. Similarly for SciFact, we treat each annotated evidence group as fully supporting and the subsets of annotated evidence groups as partially supporting; we randomly sample 1∼3 non-annotated EPs to as negative lables for not supporting examples, obtaining 216, 42, and 204 fully support, partially support, and do not support examples, respectively. Table <ref> shows the prompt used for the LLM.



  
Experimental results. Table <ref> shows the support prediction Model performance. Overall the model yields satisfactory performance on fully and not supporting examples but performs poorly on partially supporting examples. This is because the partial support label is vaguely defined, and presumably the LLM <cit.> did not encounter sufficient partially supporting entailment examples in its pretraining.





§ IMPLEMENTATION DETAILS
 


 §.§ Additional Preprocessing

For the WiCE-MEG dataset, since the majority of the candidate EPs are not relevant to the claim, but some may be selected as part of the EGs by the LLM, we additionally filter out sentences without any stemmed token overlap with the claim in advance. This filtering removes 55.6% of candidate EPs but affects only 6.7% of gold EGs, significantly speeding up inference with minimal performance loss.



 §.§ Detailed Algorithm
 
To avoid redundant computation, we iteratively merge two partially supporting set of EPs to a larger candidate set and store it in PGs in Algorithm <ref>. Therefore, PGs is implemented by a Python dictionary with size of the set of EPs as keys and another nested Python dictionary CS as values. Each CS has a key of the merged set of EPs G_1 ∪ G_2, and values of pair of the (G_1, G_2). Algorithm <ref> & <ref> presents the full pseudo code of our implementation. In Algorithm <ref> we prepare non-redundant candidate sets of EPs by running notRedundant checker implemented by a zero-shot LLM prompt (Table <ref>).



 §.§ Inter-annotator Disagreement

In WiCE <cit.> dataset, we observe some inter-annotator disagreements where some human-labeled EGs are supersets of the other EGs for the same claim, but in these cases we still include both EGs as references.





