CS Paper Radar

Data Provenance Aggregation and Structural Descriptors for Query-Template Identification

Paulo Pintor, Rogério Costa, José Moreira

cs.DB cs.LG ·submitted 2026-10-15 22:20 UTC · v1

Abstract

Runtime query similarity identification supports several activities, including workload analysis, identifying recurring behaviour, auditing, debugging, and anomaly detection. Existing methods for evaluating query similarity mostly rely on SQL text, execution plans, or result values but do not account for input data or how results are derived during query execution. This paper proposes a novel approach using data provenance for query-template identification. We construct query-level profiles that capture explicit data dependencies, occurrence frequencies, and structural properties by aggregating tuple-level Lineage and Why-provenance across entire query results. We also derive Provenance Structural Descriptors (PSD), which summarise these profiles using a small set of numerical features. We evaluate our proposals using these profiles to identify query templates over \(12{,}500\) distinct query instances generated from parametrised TPC-DS query templates. The experimental evaluation shows that query templates can be identified solely from their provenance footprints, and that accuracy improves as more historical data becomes available. It also shows that PSD achieve high classification accuracy with limited training history and low test-processing cost.

Closest papers

Nearest neighbours by meaning across the whole index.

ProvQML: Efficient Provenance Capture for Machine Learning as Recursive Aggregate SQL [Extended Version]

cs.DB ·2026-10-09 ·Nkechi J. Akinwale, Seokki Lee
similarity 0.66
Abstract

Expressing ML algorithms as recursive aggregate SQL queries over distributed systems enables large-scale declarative data analytics, yet no existing system supports scalable provenance capture, necessary for ML explainability. We present ProvQML, a provenance-aware recursive aggregate SQL engine that efficiently captures fine-grained provenance while evaluating ML algorithms as recursive aggregate queries. We capture two types of provenance: (i) local provenance that records the contribution of each training instance to gradient computation at a specific model state, and (ii) global provenance that encodes the sequence of model parameter updates across the iterations. Extensive experiments on widely used ML datasets demonstrate that our approach efficiently captures both provenance for various ML models over widely used ML datasets.

0.26

Workflow Cards: Structured Summaries of Workflow Executions Using Provenance Data

cs.DC cs.AI ·2026-08-11 ·Nicola Giuseppe Marchioro, Gabriele Padovani, Amal Gueroudji, Rafael Ferreira da Silva, Wesley Brewer +3 more
published similarity 0.64
Abstract · Accepted at eScience2026

Model Cards and Data Cards have demonstrated the value of structured, human-readable documentation for machine learning artifacts, capturing their context, parameters, limitations, and intended use. However, these practices remain focused on static artifacts (the datasets and trained models themselves) while overlooking the workflow executions that produce, transform, and evaluate them. Such executions hold critical details about data preparation, parameter choice, runtime behavior, resource use, and intermediate transformations, precisely where bias, performance variation, and reproducibility gaps tend to originate. To close this gap, we introduce Workflow Cards: structured summaries that condense the machine-readable provenance data of a workflow execution into a form both humans and large language models (LLMs) can read and analyze. This paper has two main parts. First, it defines a Workflow Card template informed by a representative set of provenance questions that surface from the execution-level data missing from Model and Data Cards. Second, it evaluates how effectively LLMs use Workflow Cards to understand workflow executions compared with querying provenance databases through a schema-based interface. Results show that Workflow Cards provide execution-level information absent from existing card types, such as Model Cards and Data Cards, thereby filling an important documentation gap; and that Workflow Cards nearly double answer quality compared with schema-based querying, consistently across LLM-as-a-Judge and human assessments.

0.19

The "Curse of Knowledge" in LLM Query Simulation: Concept Provenance for Tracing Answer-Side Intrusion

cs.IR cs.CL ·2026-08-26 ·Chenglong Ma, Xinye Wanyan, Danula Hettiachchi, Ziqi Xu, Jeffrey Chan
top venue similarity 0.62
Abstract · 12 pages, 4 figures, and 2 tables. To appear in the Proceedings of the 35th ACM International Conference on Information and Knowledge Manage…

LLM-generated search queries are widely used to augment IR evaluation, yet they may contain concepts that presuppose answer-side document knowledge, violating the information-access boundary of pre-search users. Existing validation metrics, including overlap, diversity, and effectiveness, cannot distinguish rare human-tail variation from candidate answer-side intrusion. We introduce concept provenance, a framework that assigns query concepts to backstory-supported, human-central, human-tail, and candidate answer-side zones, operationalizing a boundary that retrieval metrics alone cannot detect. Applying concept provenance to 77,004 queries across 100 UQV100 topics, 8 LLMs, and 5 prompt conditions with two extraction pipelines, we obtain a cross-pipeline token-HCIR Spearman rho of 1.0 over five condition means. Candidate answer-side concepts constitute 7.40 percent of non-generic concepts and appear in 97 of 100 topics, with topic explaining approximately 67 percent of variance. Human validation yields 68.2 percent relaxed precision, revealing two mechanisms: knowledge intrusion at 45.5 percent and deployment intrusion at 45.0 percent. Diagnostic probes show disproportionate localized retrieval effects, with deletion effect size d = -0.47 compared with d = -0.34 for random deletion, but these concepts explain less than 2 percent of aggregate evaluation variance. Concept provenance therefore serves as a boundary-compliance diagnostic rather than an evaluation-shift predictor. Under the tested conditions, no prompt condition eliminates intrusion; post-generation concept-provenance selection achieves 99 percent elimination.

0.51

Diverse Why-Provenance for Datalog Queries

cs.DB ·2026-10-17 ·Marco Calautti, Mostafa Milani, Andreas Pieris
similarity 0.62
Abstract · Extended version of a conference submission

Datalog is a powerful rule-based language that allows us to express complex recursive queries and has found numerous applications over the years. Explaining why a result to a Datalog query is obtained is an essential task towards explainable and transparent data-intensive applications that rely on Datalog. A standard way of explaining a query result is the so-called why-provenance, which provides information about the witnesses to a query result in the form of subsets of the input database that as a whole can be used to derive that result. The state-of-the-art approach for efficiently computing the why-provenance explanations of a certain query result aims at enumerating, without repetitions, the relevant explanations by relying on off-the-shelf SAT solvers. However, whenever the set of explanations is very large, outputting the entire set might be prohibitively expensive. Moreover, it is questionable the practical usefulness of flooding the user with a very large number of explanations, many of them possibly differing only marginally. In this case, one can argue that it would be practically more useful to compute a small, sufficiently diverse subset of the set of why-provenance explanations. The present work initiates the study of the latter problem. In particular, we formalize the problem of interest as an optimization problem, and, after showing that it is highly intractable (it is NP-hard even in data complexity), we investigate whether ILP optimization solvers can be employed towards practical solutions. Our main finding is that this is achievable as long as we keep the requested set of explanations small, or we employ approximation algorithms (with error guarantees).

0.20

Query-Aware Source-Risk Triage for Retrieval-Augmented Generation

cs.AI ·2026-09-15 ·Kainan Zhou, Gangzhen Qian, Chuhong Xu, Lu Yi
published similarity 0.61
Abstract · 6 pages, 6 figures, 5 tables. Accepted at CAIT 2026

Retrieval-augmented generation (RAG) pipelines may omit a source's material relationship to the query. We study a pre-generation triage layer that treats this relationship as query dependent. The method routes canonical query families for enhanced review and assigns retrieved pages to pass, contextualize, exclude, or review. It combines a four-dimension page score, rank-discounted family aggregation, intent-preserving query mutations, and a family-held-out router. A single-coded pilot of 200 real URLs supplies provisional calibration anchors; a 20,000-row scenario with synthetic domain identifiers supports controlled workload analysis. An oracle page gate defines a risk-coverage target for a future learned classifier. The evaluation shows why page-level frequency cannot substitute for family-level exposure and quantifies how calibration changes scenario activation. Annotation reliability remains unmeasured, and synthetic rankings omit real retrieval dynamics. The result is an auditable triage method and validation plan, not an estimate of deployed review workload, live-Web prevalence, or downstream answer-quality gains.

0.26

VecDBLens: An Evaluatology-Based Framework for Vector Database Diagnosis

cs.DB ·2026-11-11 ·Yutong Zhou, Guoxin Kang, Wenxin Zhou, Haoyu He, Yuedong Zhu +4 more
benchmark similarity 0.60
Abstract

Vector databases are increasingly deployed as retrieval pipelines in which representation, indexing, and query-time execution jointly determine accuracy, throughput, and cost. Existing vector database evaluations primarily focus on indexing while treating embeddings as fixed inputs and ignoring the role of query-time execution, making it difficult to decide whether a bottleneck should be addressed by changing the embedding model, the index, or the query-processing functions. To address the above limitation, we introduce VecDBLens, an Evaluatology-based framework that treats the function under diagnosis as an evaluated object and all remaining dataset, workload, parameter, and runtime factors as matched evaluation conditions. VecDBLens attributes performance differences to individual evaluated objects through comparisons under matched evaluation conditions, summarizing their performance and stability across multiple datasets and workloads. It further analyzes interactions among objects using analysis of variance (ANOVA), thereby turning vector database benchmarking from leaderboard ranking into a reproducible diagnostic procedure. VecDBLens reveals two key insights. First, retrieval performance is fundamentally upper-bounded by embedding quality, revealing that many apparent indexing failures are therefore representation-side limitations. Second, stronger index parameterization is not always beneficial: overly aggressive configurations can reshape neighborhood topology and cause recall regression. These results challenge the common practice of evaluating vector databases primarily through indexing and show that real-world limitations arise from constraints across retrieval functions rather than any single function alone. VecDBLens provides a principled basis for identifying the true performance drivers of vector databases and for guiding their design in practical applications.

0.25

Tool Retrievers Are Underestimated: Annotation Expansion Reveals True Capability

cs.SE cs.IR ·2026-09-08 ·Yanyu Zhu, Chenheng Zhang, Shaoshen Chen, Hoilam Pao, Yufei zhang +6 more
benchmark similarity 0.60
Abstract

In open-world scenarios with massive and evolving tool repositories, tool-augmented large language models rely on a retriever to surface relevant tools for a given query. Because such repositories often contain many tools that implement the same functionality, a single query can often be resolved by several distinct but functionally equivalent tool combinations, making the natural query-to-tool mapping inherently one-to-many. However, existing tool retrieval benchmarks annotate each query with a single relevant tool combination, collapsing this one-to-many mapping into a rigid one-to-one annotation and causing valid retrieved tools to be misjudged as failures. To address this, we propose ToolEX (Tool Equivalent eXpansion), a framework that automatically discovers and annotates the tool combinations functionally equivalent to the labeled ones. Applied to the 7,360-query Tool-DE benchmark, ToolEX finds that 67.9% of sub-queries admit equivalent alternatives, expanding the singular ground truth to an average of 5.3 valid combinations per query. Using the expanded benchmark ToolEQ, we re-evaluate eight base retrievers and two fine-tuned variants; metrics on ToolEQ rise substantially over Tool-DE, showing that one-to-one annotation systematically underestimates retrievers and that 30--47% of the reported fine-tuning gain is an evaluation artifact rather than genuine improvement. Applying the same pipeline to skill retrieval on SkillRet further confirms that the one-to-one problem extends beyond tool retrieval.

0.42

Route Me If You Can: A Benchmark for Query Reformulation Selection

cs.IR ·2026-09-14 ·Hai Son Le, Negar Arabzadeh, Amin Bigdeli, Radin Hamidi Rad, Sajad Ebrahimi +2 more
top venuebenchmarkcode/data similarity 0.60
Abstract

LLM-based query reformulation can improve retrieval, but no single reformulation strategy is consistently optimal across queries, domains, retrievers, or model backbones. This creates an inference-time decision problem: ``Given an original query and a pool of candidate reformulations, which one should be issued to the retriever?''. Existing studies are hard to compare because they use different reformulator pools, retrievers, relevance signals, training labels, and evaluation metrics. We introduce QueryRoute, a benchmark that freezes the expensive artifacts needed to study this decision reproducibly: original queries, generated variants, ranked lists under multiple retrievers, retrieval scores, and per-query oracle labels. The benchmark contains 3,757 queries, 11 candidate systems, five reformulator backbones, and three retrievers across TREC DL, BEIR, and BRIGHT, yielding 619,905 retrieval outcomes. We benchmark supervised classification, routing, QPP, and LLM-as-judge selectors. Results show substantial oracle headroom over fixed reformulators, but current selectors recover only part of it; selector rankings change across retrievers, and similar mean effectiveness can hide different query-level behavior. The released artifacts and evaluation harness allow future selectors to be compared without regenerating variants, rerunning retrieval, or rebuilding judge pipelines. Code and data are available at https://github.com/haisonle001/QueryRoute

0.49