Query-Guided Analysis and Mitigation of Data Verification Errors (Extended Version

Ran Schreiber, Yael Amsterdamer · 2026

Read Query-Guided Analysis and Mitigation of Data Verification Errors (Extended Version by Ran Schreiber, Yael Amsterdamer (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-08612.txt.

Introduction

Ran Schreiber and Yael Amsterdamer help data teams spend extra checks where bad labels hurt query answers most. Their Maximal Error Score rates worst-case doubt for each output row without leaning on the data spread. A side flag spots risky inputs where cutting doubt can oddly raise output doubt, and their MESReduce routine picks checks, cutting the score and lifting accuracy in tests.

Catalog record

CREATORRan Schreiber, Yael Amsterdamer
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE133149
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.08612

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Query-Guided Analysis and Mitigation of Data Verification Errors (Extended Version) Thanks: This paper is the extended version of a paper accepted to the IEEE International Conference on Data Engineering (ICDE) 2026. Ran Schreiber, Yael Amsterdamer Abstract Data verification, the process of labeling data items as correct or incorrect, is a preprocessing step that may critically affect the quality of results in data-driven pipelines. Despite recent advances, verification can still produce erroneous labels that propagate to downstream query results in complex ways. We present a framework that complements existing verification tools by assessing the impact of potential labeling errors on query outputs and guiding additional verification steps to improve result reliability. To this end, we introduce Maximal Error Score (MES) , a worst-case uncertainty metric that quantifies the reliability of query output tuples independently of the underlying data distribution. As an auxiliary indicator, we identify risky tuples – input tuples for which reducing label uncertainty may counterintuitively increase the output uncertainty. We then develop efficient algorithms for computing MES and detecting risky tuples, as well as a generic algorithm, named MESReduce, that builds on both indicators and interacts with external verifiers to select effective additional verification steps. We implement our techniques in a prototype system and evaluate them on real and synthetic datasets, demonstrating that MESReduce can substantially and effectively reduce the MES and improve the accuracy of verification results. 1 Introduction Data verification is the process of classifying data items as correct or incorrect, which can be critical in data-driven applications that require high data accuracy. Verifying the data may involve fact-checking against external knowledge sources or detecting anomalies in format or content, and thus can be viewed as part of the broader data cleaning process. Recent advances in machine learning have led to growing interest and improved performance in this area (see Section 7 ). Despite these advances, data verification can be costly in terms of latency and resources, e.g., when each tuple must be fact-checked by searching a data lake, using a Large Language Model, or consulting a human expert. Moreover, the resulting labels may still be uncertain or erroneous, especially under cost-accuracy tradeoffs. For example, data lake searches may be time-limited; verification systems that rely on human feedback, e.g., by involving domain experts or crowd workers [ 90 , 28 , 9 , 46 , 7 , 19 , 60 , 85 , 31 , 21 , 13 , 73 ] , are naturally prone to erroneous decisions – correct data might be labeled as incorrect or vice versa; similarly, systems in which labels are produced automatically, e.g., by an ML classifier, are also prone to erroneous labels. Such verification errors can then propagate, often in non-trivial ways, to downstream tasks [ 45 , 61 , 62 ] . In the context of queries issued by analysts (which we show to be affected non-trivially by the verification errors in Section 3.2 ), a notable shortcoming of existing systems is that the potential error propagation is not quantified and therefore not reported properly to the analysts, which can be particularly problematic in data-critical settings, e.g., medical applications. Example 1 . Consider a data analyst deriving business insights from a database that contains both valuable data and errors. To focus on the correct portion of the data, the analyst applies an automated data verification tool that labels each tuple as correct or incorrect. However, because verification is imperfect, these labels may themselves be erroneous and can propagate to downstream query results. This raises several key questions: (i) To what extent can the analyst trust the query results? (ii) How likely is it that correct output tuples are missing from the results? (iii) What actions can be taken to improve the reliability of the results? Answering these questions is not straightforward. Consider questions (i)-(ii) and suppose the query aims to retrieve data about company founders. For some individual X , the database contains ten distinct tuples of the form “ X founded company Y_{i} ,” where Y_{1},\ldots,Y_{10} are different companies. The higher-level conclusion that X is a company founder is supported if at least one of these tuples is correct. If all ten tuples are labeled as correct, then all ten labels would have to be erroneous to invalidate this conclusion. In contrast, if all ten tuples are labeled as incorrect, a single mislabeled tuple would be sufficient to invalidate the opposite conclusion that X is not a company founder. Now consider question (iii) and assume that the analyst can hire a domain expert to refine the labels. Verifying the entire dataset is costly, so the analyst must decide which tuples the expert should check. Prioritizing tuples solely based on their individual error likelihood may be ineffective: e.g., if the tuple “ X founded company Y_{1} ” is labeled as correct with (nearly) 100% certainty, then X is almost certainly a company founder, and refining the remaining nine labels is redundant regardless of their uncertainty. ∎ In this work, we present a generic framework that complements existing data verification tools by analyzing how uncertainty in the labels they produce affects downstream query results. First, we introduce a novel uncertainty measure, Maximal Error Score (MES) , which assigns each output tuple a worst-case error score based on the uncertainty of the labels assigned to input tuples. This measure highlights where verification provides strong reliability guarantees for query outputs and where outputs remain uncertain. Next, in settings where label error probabilities can be reduced at an additional cost, such as in Example 1 , we propose a generic algorithm that leverages our uncertainty indicators to automatically guide external verifiers and optimize the tradeoff between query result reliability and verification cost. Example uses of the framework include estimating the reliability of query output, considering both tuples labeled as correct and as incorrect; determining whether a fast, low-cost data verification tool produces sufficiently reliable results or if a more accurate, costlier tool is needed; and selecting which tuples should be labeled by a high-quality verifier under a limited budget. Figure 1: The flow of our framework 1.1 Framework Components and Flow Figure 1 illustrates the high-level flow of our framework. Novel components are enclosed in a highlighted background, and step numbers are shown in circles. Step 1 : A user-specified query is evaluated together with its provenance information , which abstractly captures how output tuples are derived and is used in subsequent steps. Step 2 : An external verification tool is applied to produce a (possibly partial) correctness labeling of input tuples, along with an estimated probability for each label (shown in the Label+Prob. column in the figure). Section 2 details how these probabilities can be estimated. The resulting instance is referred to as a database with error estimation (DES) . If the verifier is query-guided , it also receives the query results as input. Output tuples are presented to the analyst together with derived correctness labels. Step 3 : The framework provides two novel indicators to support analyst decision making. Based on these, the analyst may retain only reliable, low-MES (i.e., low-uncertainty) output tuples, apply a different verifier, or use the risky tuple indicator, which identifies tuples whose further verification may increase overall

Read the complete text