PaperlayerView exact revision on arXiv

Source-linked AI summary

Bolt-on, Verifiable Provenance for LLM-Powered Data Processing

Yiming Lin, Sepanta Zeighami, Aditya G. Parameswaran

arXiv:2608.25210v1cs.DB

TL;DR

LLM answers often lack trustworthy evidence of how they were derived, while existing provenance heuristics do not guarantee that selected text reproduces the answer. BLIP infers minimal verifiable provenance for any LLM through guaranteed strategies and extensions for multiple provenances, achieving guaranteed reproduction at low cost and over 30% higher accuracy than the best-performing baseline. Its scope excludes ambiguous questions and cases where the full-input answer is incorrect.

  • Problem

    LLM-powered data processing lacks reliable provenance showing how answers were derived, and existing retrieval or LLM-generated approaches do not guarantee answer reproduction.

  • Method

    BLIP is a bolt-on framework using strategies, including adaptive and top-k extensions, to infer minimal verifiable provenances compatible with any LLM.

  • Results

    Over 30% higher accuracy than the best-performing baseline was achieved while BLIP was guaranteed to return provenance reproducing the answer at low cost.

  • Takeaways & Limitations

    BLIP provides a low-cost way to infer provenance that reproduces the original answer and can identify multiple distinct provenances when one is insufficient for confidence.

  • Takeaways & Limitations

    Provenance is inapplicable when the question is ambiguous or the full-input LLM answer is incorrect.

Abstract

from arXiv · show

Large Language Models (LLMs) are powerful tools for processing data. However, LLMs are also complex black-boxes, returning answers to queries on data, without any indication for where the answer came from or whether it is trustworthy. We introduce the notion of provenance for data processing with LLMs. While existing heuristics (such as embedding similarity or directly asking an LLM) could provide some hints for where the answer was derived, they provide no guarantees that the answer can be derived using the identified provenance, and indeed, are often incorrect. Instead, we propose the notion of verifiable provenance wherein we identify a subset of the input text that reproduces the same (or equivalent) answer as that on the complete text, and introduce the notion of minimality, where the verifiable provenance is as small as possible. To identify such a provenance, a naive solution would require checking all possible subsets of the source data with the LLM, which is prohibitively expensive. We present BLIP, a bolt-on framework for efficiently inferring a small-sized verifiable provenance for any LLM-powered data processing task, with any LLM. As part of BLIP, we introduce eight strategies, each guaranteed to find a minimal verifiable provenance, as well as an adaptive strategy that combines their strengths to reduce cost further. We further extend BLIP to produce multiple minimal verifiable provenances. Experiments on seven datasets show that the provenance generated by BLIP is always guaranteed to reproduce the answer - achieving over 30% higher accuracy than the best-performing baseline with a comparable provenance size. Moreover, BLIP incurs a low cost, comparable to the original query on the original data.

1 INTRODUCTION

LLM-powered data processing lacks reliable indications of how answers were derived or whether they can be trusted. The paper introduces verifiable, minimal provenance and BLIP, a low-cost framework for inferring it with guarantees.

  • LLM-powered data processing: LLMs support extraction, cleaning, enrichment, synthesis, and question-answering over structured and unstructured data.These tasks commonly synthesize answers from source data supplied in context as text.
  • Limits of existing approaches: Retrieval-based provenance does not guarantee answer reproduction, while directly prompted LLMs reproduce answers in only 65%, 74%, and 53% of cases for three tested models.When provenance fails, human verification defaults to reading the entire document.
  • Verifiable provenance: Verifiable provenance is a text subsequence that reproduces the same or equivalent answer as the full input under the same LLM.Minimality requires this provenance to be as small as possible.
  • BLIP: BLIP uses a two-phase approach: an aggressive search for a small verifiable provenance followed by refinement that guarantees minimality.Its strategies include relevance ranking and different enumeration orders.
  • BLIP: BLIP is bolt-on, compatible with any LLM, and designed to provide minimal provenance at low cost.The framework also develops an adaptive strategy combining multiple strategies.

2 PROBLEM DEFINITION AND OVERVIEW

This section formalizes verifiable provenance as a text subsequence that reproduces the original answer, then seeks a minimal such subsequence. It also frames BLIP as a two-phase framework whose guarantees depend on task properties and whose applicability has defined boundaries.

  • 2.1 Provenance Definition: Verifiable provenance is a text subsequence whose answer is lexically identical or semantically equivalent to the answer from the full input.Semantic equivalence can be judged by an LLM; closed-domain answers may instead use exact equality.
  • 2.1 Provenance Definition: LLM-as-a-judge achieves around 94% average accuracy across five models and four prompting variants on 2,000 GLUE text pairs.The evaluation tests whether two responses are semantically equivalent.
  • 2.1 Provenance Definition: A minimal provenance becomes invalid when any one of its sentences is removed, while strict minimality additionally excludes any valid proper subsequence.Minimality targets a small provenance for easier interpretation; strict minimality rules out local minima.
  • 2.2 Cost Model and KV-Cache: The cost model charges for input and output tokens in each LLM invocation, with prompt cost defined for the question-text input.Input and output token counts are multiplied by their respective unit costs.
  • 2.4 Strong and Weak Monotonicity: Strongly monotonic tasks comprise around 90% on average across real workloads and multiple LLMs, while weak monotonicity guarantees that minimal provenances are strictly minimal.Weak monotonicity requires a chain of valid supersets rather than every superset being valid.
  • 2.7 Overview of BLIP: BLIP uses pruning to aggressively remove unlikely contributing sentences, followed by refinement that guarantees a minimal provenance; it can also return k distinct minimal provenances.The framework is presented as applicable across LLM models, but provenance is undefined for ambiguous questions or incorrect full-input answers.

3 FINDING TOP-1 PROVENANCE

BLIP infers a single minimal provenance from the input text, question, LLM, and evaluated answer.

  • BLIP takes input text T, question Q, LLM L, and answer A as inputs to infer one minimal provenance.

3.1 Phase 1: Provenance Pruning

Phase 1 prunes the input into a small verifiable provenance using relevance ranking and alternative scan orders. Its strategies trade off search cost according to provenance location and size.

  • Four pruning strategies combine embedding- or LLM-based ranking with bottom-up or top-down enumeration.
  • Phase 1 divides T into equal-sized blocks and ranks them by embedding similarity or LLM-assigned relevance to the ⟨Q,A⟩ pair.The LLM ranker may differ from the answer-generating model.
  • The pruning phase stops when the selected blocks reproduce an answer equivalent to A.
  • Top-down search uses binary search over ranked blocks and makes at most ⌈log2 m⌉ LLM calls.
  • Bottom-up testing is preferable when a small number of top-ranked blocks contains the provenance, while top-down search is more efficient when that number is large.Bottom-up can repeatedly evaluate prefixes, whereas top-down narrows the search window by discarding ranges.

3.2 Phase 2: Provenance Refinement

Phase 2 refines the Phase 1 provenance by testing sentence removals until no further reduction preserves an equivalent answer. Sequential and exponential deletion provide complementary refinement behaviors.

  • Phase 2 receives any provenance P from Phase 1 and computes a minimal provenance by removing sentences while preserving answer equivalence.
  • Sequential-Greedy: Sequential-Greedy examines sentences one at a time and repeatedly reruns until the provenance no longer changes.Repeated passes are essential for minimality.
  • Exponential-Greedy: Exponential-Greedy removes increasingly large sentence subsequences as long as the reduced provenance continues to reproduce an answer equivalent to A.
  • Sequential-Greedy can exploit prefix caching because successive prompts share the longest possible retained context prefix.In the running example, the input-token cost is reduced by a factor of f_L = 4 in the second iteration.

3.3 Quality and Cost Analysis

BLIP’s refinement strategies are guaranteed to return minimal provenances without task monotonicity assumptions, while pruning and refinement costs depend on provenance size, ranking quality, and distribution. The analysis motivates adaptive strategy selection and favors exponential refinement in many large-provenance cases.

  • Quality guarantees: Every refinement strategy returns a minimal provenance for any task and input provenance, and every pruning–refinement combination therefore has the same guarantee.
  • Quality guarantees: BLIP’s minimality guarantee does not require weak or strong monotonicity assumptions, including for non-monotonic tasks.
  • Pruning cost: Bottom-up is preferred when the provenance lies within relatively few top-ranked blocks, whereas top-down is preferred when that number is large.Between the threshold ranges, the two cost formulas must be evaluated explicitly.
  • Refinement cost: When the refined provenance contains more than a constant number of non-provenance sentences, Exponential-Greedy costs o(C_SEQ) and is cheaper asymptotically than Sequential-Greedy.When g = Θ(1), both strategies have the same asymptotic order.
  • Scope and limitations: BLIP’s efficiency depends on task characteristics, provenance size, and ranking quality; large provenances increase refinement cost, while weak ranking reduces pruning effectiveness.Embedding rankers may be poorly suited to logical operations, for which SQL-based query answering can be more effective.
  • Strategy selection: Exponential-Greedy improves worst-case performance particularly when the Phase 1 provenance is large and its relevant sentences are locally distributed.The improvement comes from logarithmic-factor reduction in pruning non-contributing sentences.

4 FINDING TOP-K PROVENANCE

Top-k provenance searches for multiple distinct minimal provenances by recursively expanding high-scoring text blocks, then refining verified blocks to minimality. It can return several candidate provenances, but does not guarantee discovering every distinct minimal provenance.

  • Motivation: Top-k provenance addresses cases where one minimal provenance cannot establish answer correctness by identifying multiple distinct provenances.Positive provenances support correctness, whereas negative provenances can reproduce the answer without supporting it.
  • Search strategy: The algorithm scores text blocks by their likelihood of reproducing the full-text answer and expands the highest-scoring block in a max heap.Blocks are recursively split into left and right halves and ranked by their verification scores.
  • Limitations: Top-k provenance returns only a subset of distinct minimal provenances rather than guaranteeing complete enumeration.The paper argues that finding one positive provenance may suffice when the original answer is correct, while incorrect answers ideally require examining negative provenances.

5 EVALUATION

BLIP is evaluated across diverse question-answering workloads, measuring cost, latency, provenance size, verifiability, human review effort, and recovery of known true provenance. Across these evaluations, BLIP produces compact, verifiable provenance at low cost and improves recovery and human usefulness relative to baselines.

  • Evaluation Setup: The evaluation covers five real-world question-answering workloads and two synthetic table workloads spanning scientific, encyclopedic, legal, medical, and tabular data.The real-world workloads sample 500 question-document pairs each, while Movie and Restaurant contain 100 questions each over 64,000-token tables.
  • Evaluation Setup: True provenance is available for Movie and Restaurant but unknown for the five plain-text workloads, where annotators may disagree and multiple true provenances may exist.Recovery metrics are therefore used for TableQA, while accuracy measures whether inferred provenance reproduces the answer.
  • Cost, Latency, and Provenance Size: Adaptive pruning reduces average provenance size ratios to 10.2%, 12.8%, and 20.2% for Qasper, NL_DEV, and HotpotQA, respectively, at 0.28×, 0.25×, and 0.3× the full-text answering cost.LLM_adaptive reduces provenance to around 9.8% with a 0.2× cost ratio and 2.1-second average latency across the workloads.
  • Cost, Latency, and Provenance Size: Two-phase refinement reduces provenance size ratios to about 3.7%, 4.7%, and 7.7% on Qasper, NL_DEV, and HotpotQA, respectively, with EXP strategies costing up to 1.1× full-text QA.The average latency for EXP strategies is 8.1 seconds across workloads.
  • Accuracy and Human Review Effort: BLIP guarantees accuracy of 1 and achieves over 30% higher accuracy than the best baseline with comparable provenance size.This guarantee also applies to the approximately 5% of non-monotonic queries reported in the evaluation.
  • Human Review Effort: BLIP requires only 3% to 12% human review effort across five workloads and receives an overall usefulness score of 4.75 out of 5.Participants judged BLIP provenance to contain the right amount of information 82% of the time, compared with 3.1 overall usefulness for RAG-based provenance.
  • Strategy Comparisons: The adaptive strategy is recommended when provenance size is unknown, while EXP is preferred for more than approximately 10 sentences and SEQ for smaller inputs.The recommendation reflects reported cost and speed comparisons between the strategies.
  • Recovery of True Provenance: BLIP recovers a superset of true provenance for every TableQA question and exactly recovers true tuples in over 98% of Movie and 96% of Restaurant questions.RAG-EXACT achieves only 32% to 68% exact recovery, while RAG-10% can return over 50 times more tuples than ground truth.

6 RELATED WORK

BLIP is related to provenance research in relational databases, scientific workflows, and LLM inference. Database provenance primarily tracks data lineage for reproducibility and studies which inputs produce outputs and where outputs originate.

  • Database Provenance: Database provenance focuses on tracking data lineage to ensure reproducibility.Its questions include which input tuples produce an output and which specific source locations contribute to it.

7 CONCLUSION

The paper presents BLIP as a framework for inferring verifiable minimal provenance for LLM-generated answers. It also supports multiple distinct provenances when one is insufficient for confidence, with experiments showing guaranteed answer reproduction and higher accuracy than the best baseline.

  • Conclusion: BLIP infers minimal subsets of input text that reproduce an equivalent answer to the answer from the full input.Its strategies include an adaptive strategy that combines multiple strategies for more efficient provenance inference.
  • Conclusion: BLIP can identify k distinct minimal provenances when a single provenance is insufficient to establish confidence in answer correctness.Multiple provenances allow users to explore alternative supporting or misleading evidence.
  • Conclusion: BLIP is guaranteed to return provenance that reproduces the answer at low cost and achieves over 30% higher accuracy than the best-performing baseline.The conclusion reports this result across five datasets.
Loading 2608.25210v1…