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

Si Chen, Feiyang Kang, Ning Yu, Ruoxi Jia

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

Large Language Models (LLMs) are incredible at absorbing knowledge, but they are notorious for "hallucinations"—generating plausible-sounding but unfounded information. To make these models reliable for high-stakes fields like medicine or finance, we need to perform fact tracing: identifying exactly which training data points support a generated fact.

Existing approaches generally fall into two camps, both with significant flaws. Training Data Attribution (TDA) methods like TracIn use gradient similarity to find influential data, but they are computationally expensive and often fail to scale. Information Retrieval (IR) methods like BM25 use lexical similarity; while fast, they focus on relevance rather than supportiveness. For example, a training sentence about "Apples" is relevant to a query about "Granny Smiths," but it might not actually support the specific fact that they are green. Fact tracing requires actual reasoning—the ability to distinguish between a sentence that mentions a topic and one that provides evidence for a claim.

Methodology

The authors introduce FASTTRACK, a two-stage pipeline that balances computational efficiency with deep natural language understanding (NLU).

The FASTTRACK two-stage framework: Offline semantic clustering followed by online LLM-powered fact tracing.

Stage 1: Semantic Clustering (Offline)

To avoid the $O(mN)$ complexity of comparing every query to every training point, FASTTRACK reorganizes the training corpus into a searchable "semantic tree." It uses Sentence-Transformers to embed the corpus and applies recursive k-means clustering. Crucially, it uses an LLM to assign descriptive keywords to each cluster, turning a "black box" cluster into an interpretable semantic index. This stage is performed once and can be reused for any number of queries.

Stage 2: LLM as a Tracer (Online)

When a query arrives, the system performs a two-step retrieval. First, it uses fuzzy keyword matching to find the most relevant clusters (Coarse Matching). Second, it feeds candidate samples from those clusters into an LLM for Fine-Grained Validation. Instead of checking samples one-by-one, it uses a batch prompting strategy to evaluate multiple texts simultaneously, significantly reducing API costs and latency. The LLM acts as a judge, assigning a binary score (1 for supportive, 0 otherwise).

Datasets and Experimental Setup

The paper evaluates FASTTRACK on two main benchmarks:

  1. FTRACE-TREx: A standard dataset containing 27k queries and 1M training examples (cloze-style sentences).
  2. VITATRACE: A new dataset introduced by the authors, derived from VitaminC. It is specifically designed to test a model's ability to handle contradictions and misinformation, featuring labels for "SUPPORTS," "REFUTES," and "NOT ENOUGH INFO."

Key Results

FASTTRACK demonstrates superior performance across both accuracy and efficiency metrics. It achieved an F1 score of 0.72 on FTRACE-TREx (compared to 0.40 for BM25 and <0.02 for TracIn) and 0.91 on VITATRACE.

Performance vs. Computation: FASTTRACK achieves significantly higher F1 scores with drastically lower computation time compared to baselines like TracIn.

In terms of efficiency, FASTTRACK is 33x faster than TracIn when evaluating 100 queries against a 10k corpus. While traditional TDA methods struggle with corpora larger than 500 samples, FASTTRACK was successfully tested on datasets of up to 100k samples with minimal performance degradation. Furthermore, when queries were paraphrased, BM25's precision dropped by 21 percentage points, while FASTTRACK remained consistent, highlighting its robustness.

Conclusion

FASTTRACK shifts the paradigm of fact tracing from a similarity task to a reasoning task. By leveraging LLMs for both cluster labeling and evidence validation, the framework achieves state-of-the-art accuracy while maintaining computational efficiency. Future work may involve fine-tuning smaller, specialized "tracing models" to replace general-purpose LLMs, which could further reduce costs and improve performance on niche domains.

Summary updated

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.
BibTeX
@inproceedings{chen2024fasttrack,
  author = {Si Chen and Feiyang Kang and Ning Yu and Ruoxi Jia},
  title = {{FASTTRACK: Reliable Fact Tracing via Clustering and LLM-Powered Evidence Validation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  url = {https://openreview.net/forum?id=jeCXmolDcw},
}
Figure