FASTTRACK : Reliable Fact Tracing via Clustering and LLM -Powered Evidence Validation (2024)

Abstract: Fact tracing seeks to identify specific training examples that serve as the knowledge source for a given query. Existing approaches to fact tracing rely on assessing the similarity between each training sample and the query along a certain dimension, such as lexical similarity, gradient, or embedding space. However, these methods fall short of effectively distinguishing between samples that are merely relevant and those that actually provide supportive evidence for the information sought by the query. This limitation often results in suboptimal effectiveness. Moreover, these approaches necessitate the examination of the similarity of individual training points for each query, imposing significant computational demands and creating a substantial barrier for practical applications. This paper introduces FASTTRACK, a novel approach that harnesses the capabilities of Large Language Models (LLMs) to validate supportive evidence for queries and at the same time clusters the training database towards a reduced extent for LLMs to trace facts. Our experiments show that FASTTRACK substantially outperforms existing methods in both accuracy and efficiency, achieving more than 100% improvement in F1 score over the state-of-the-art methods while being x33 faster than TracIn.

## introduction recent years have witnessed large language models (llms) demonstrating remarkable abilities in absorbing vast knowledge from extensive text corpora, yielding impressive advancements in nlp tasks such as question answering (qa). however, these models often produce seemingly coherent yet unfounded outputs, known as 'hallucinations' @xcite , posing risks in high-stake scenarios such as healthcare and finance, where reliability is of paramount importance (master of @xcite . this critical challenge has motivated research on fact tracing @xcite , aiming to identify the training data that serves as the knowledge source for llms' generation. in an effort to understand and mitigate the issue of hallucination, prior work @xcite formulates fact tracing similarly to the training data attribution problem, seeking to find the most influential data points that lead an lm to generate a particular fact. however, this formulation faces the challenge of collecting ground truth data, making it impossible to accurately evaluate a method's performance. instead, they label the training data that supports the generation of a fact as ground truth, resulting in a mismatch between the formulation and the evaluation setup. to address this limitation, we propose a new formulation of fact tracing that focuses on finding training data that support a fact generated by an llm. this reformulation allows for the collection of ground truth data, enabling practical evaluation and providing insight into whether the generation is grounded in the model's training data, facilitating the detection of hallucinations. building upon this formulation, we summarize the desiderata for fact-tracing methods as follows: ⋄ d-i. effective and accurate. for a target query, fact-tracing methods need to identify all supporting facts in the training corpus and achieve both high precision and recall simultaneously. current methods all miss one or more of these principles. specifically, gradient-similarity-based methods @xcite are notoriously computationally demanding (dii). also, gradients are considerably susceptible to noises, rendering their performance rather unstable even with extensive hyper-parameter tuning @xcite ) (d-i, d-iii). lexical-similarity-based methods @xcite are typically faster, but relying on queries and samples with supporting facts being similarly phrased. this assumption is not necessarily true in realistic use cases (d-iii). figure 1 : fasttrack achieves the best tradeoffs between fact tracing efficacy and efficiency. the x-axis the the computational time of evaluating 100 queries using a 10k corpus, and the y-axis is the tracing performance when using top-k thresholds (if applicable). tda methods yield consistently low performance across top-k thresholds, making them look like dots in the plot. the limitations of existing methods highlight the need for a more effective approach to fact tracing. determining whether a training example supports a factual statement in a query requires reasoning abilities beyond simple sample similarities. support for a factual assertion often arises through the inference of connections among related pieces of information. the current methods, which are all based on similarity measures, share a common dilemma: no single representation works in all cases. the similarity in these pre-defined spaces may easily fail to capture the nuance of supportiveness effectively. inspired by the recent advancement in llm's abilities in natural language un-derstanding (nlu), a natural idea is to directly evaluate the supportiveness between each training sample and the target query using an llm. unprecedented in-context learning (icl) capabilities make these models notably versatile and easily adaptable to novel cases with minimal customization, effectively bridging the realistic gap between fact-tracing methods and real-world scenarios. our preliminary investigation shows that this idea indeed enhances the efficacy in the identification of supportive training samples to an impressive extent. however, when applied to practical-sized training corpora, this approach faces immediate challenges: traversal evaluation for all training sample-query pairs requires a massive number of queries to the llm, unaffordable in both computation time and costs, hindering it from being practically useful. to address this dilemma, we propose fast-track, a two-stage scheme decomposed into offline and online components. in the first stage, we build semantic indexes for the training corpus through hierarchical clustering, a process that is completely offline and only needs to be run once. during online stage, these pre-built semantic indexes facilitate the retrieval of relevant clusters for any given query, significantly reducing the search range. fasttrack then runs a fine-grained examination by employing a llm to evaluate the supportiveness of training data in the retrieved clusters. while the entire pretraining corpus for llms could be overwhelmingly massive, prior work @xcite deploys a setup that requires careful selection of small candidate set of size around 500 for practical evaluation. in this context, we demonstrate that fasttrack enables a balance between computational feasibility and fine-grained analysis, accommodating large corpora of size 10k or even 100k while ensuring both satisfactory efficiency and efficacy (high precision and recall). this scalability makes fasttrack a viable tool for current use and suitable for scenarios with smaller training datasets, such as those used in continuous pre-training. our contributions are summarized as follows: training data attribution (tda). tda aims to trace model predictions back to the training examples that responsible for these predictions, sharing a similar goal with fact tracing and often being repurposed as a viable approach in this context. prior work @xcite proposes to use two main types of tda methods as baselines: gradient-based and embedding-based attributions. gradient-based methods, such as tracin @xcite , estimate the attribution score of training data on predictions by calculating the cosine similarity between the gradients of the training data and the query. embedding-based methods employs the model's internal representations to determine the relevance of training examples to a given test prediction @xcite . the attribution score is defined as a cosine product of hidden representations. to retrieve supporting training data for a given query z query , one need to score every training data and rank them by their influence score. as it could be computationally infeasible for gradient-based tda scoring all training data in large datasets, @xcite only evaluates on carefully selected small subsets (i.e., around 500) for each query. this limitation motivates us to design a framework that is both more computationally efficient and more effective. information retrieval (ir). ir focuses on retrieving relevant documents in a large collection given specific queries @xcite . though not originally designed for fact tracing task, prior work @xcite found it effective and outperforms principled tda methods by a large margin. ir splits into two categories: termfrequency-based methods like bm25 @xcite , which score each training data base on the token overlap with the given query, inversely weighted with the frequency of such tokens, and neural network-based methods @xcite , which, despite their advanced capabilities, often require extensive manual annotations, making them less suited for fact tracing due to the absence of necessary annotations. recent attempts to adapt neural methods through zero-shot learning have not matched bm25's performance @xcite . therefore, following prior work, we select bm25 as the baseline for fact tracing due to its superior retrieval quality without the need for annotated data. all of the methods above focus on relevance while neglecting the supportiveness of the connection between training data and the query. in this paper, we introduce fasttrack, the first supportiveness-aware approach for fact tracing, offering substantial benefits in real scenarios where training data may contain conflicting information. ## methodology fact tracing aims to identify knowledge source of a particular query. while similar to tda, it focuses more on the fact-support correspondance between training data and query. this distinction is crucial: existing methods often retrieve relevant examples but fail to provide factual support, misaligning with the objective. the strong capability of llms such as chatgpt makes it a perfect solution to provide justification based on 'supportiveness'. however, directly doing pair-level comparison could be very time-consuming: given a corpus of size n and m queries, the computation complexity is o(mn ). in this section, we introduce an original twostage framework fasttrack, as illustrated in figure 2. in the first stage, fasttrack leverages a recursive clustering scheme to mine the semantic structure in the training corpus, which enables a coarse matching for a given query. this significantly refines the search range, making it feasible to perform a fine-grained examination of each candidate training examples in the second stage. ## ablation study and analysis in-depth analysis of fasttrack. the first stage of fasttrack-cluster level retrieval -decides the performance upper bound of our methods. if relevant clusters are not identified during this phase, it becomes impossible to recover them in the later stage. we report the upper bound performance achievable in the last row of query: president of the executive yuan is a legal term in _____. (taiwan) false negative examples (mask removed): 1. he has interviewed financial services regulators including sean chen (politician), the premier of taiwan, when he was the chairman of the financial supervisory commission (republic of china) of taiwan and negotiated the financial memorandum of understanding with china. 2. hsich tung-min was the ninth governor of taiwan province @xcite @xcite @xcite @xcite and the sixth and first local taiwanese vice president of the republic of china @xcite @xcite @xcite @xcite under president chiang ching-kuo. ## conclusion in this paper, we introduce fasttrack, a pioneering two-stage framework designed to address the shortcomings in current fact tracing methodologies, particularly their neglect of the 'supportiveness' of evidence. fasttrack substantially improves the tracing performance by more than 100% in f1 score, and offers computational efficiency, capable of handling large datasets up to 100k in size. we introduce the vitatrace which is uniquely curated for the fact tracing task, to promote reproducibility and support the community. we also provide a thorough analysis of each tracing method to shed light on future direction in fact tracing. prioritizing efficiency, we choose gpt for its extensive context window and batch processing capabilities, while other open-source llms require more engineering to achieve similar outcomes. future research might explore these alternatives or focus on fine-tuning a model specifically for tracing tasks, addressing current performance bottlenecks.