PROBE: Learned Proxy-Based Execution for Highly Selective Multimodal Semantic Queries

PROBE: Learned Proxy-Based Execution for Highly Selective Multimodal Semantic Queries Haikai Zhao

Simon Fraser University Burnaby, Canada hza214@sfu.ca

Haisheng Fu

University of British Columbia Vancouver, Canada Haisheng.fu@ubc.ca

arXiv:2611.01454v1 [cs.DB] 1 Nov 2026

ABSTRACT

Large language models (LLMs) enable semantic queries over unstructured data, but invoking an LLM on every row is prohibitively expensive. Proxy-based execution can reduce this cost by labeling a small sample with the LLM and training a lightweight proxy to label the remaining rows. Nevertheless, in practical scenarios where semantic queries are highly selective, it remains challenging to identify representative samples for labeling under a limited LLM budget and to achieve accurate predictions over the remaining data using the proxy. We present PROBE, a learned proxy-based execution framework for highly selective multimodal semantic queries. PROBE uses selectivity-adaptive sampling to discover rare positive regions and trains a lightweight proxy on the acquired labels. It then refines proxy predictions through residual correction and homogeneity smoothing over a similarity graph. To address sampling bias, PROBE jointly calibrates refined scores using training labels and a separate calibration sample, then selectively routes candidates to the LLM by optimizing the tradeoff between estimated 𝐹 1 and evaluation cost. On queries from SemBench and LRO-Bench with positive rates as low as 2.17×10−5 , PROBE with a 10% sampling budget yields a geometric-mean 𝐹 1 of 0.762, compared with 0.797 for exhaustive LLM evaluation, at a geometric-mean speedup of 4.87× and a maximum speedup of 9.3×. PVLDB Reference Format: Haikai Zhao, Haisheng Fu, Zhengjie Miao, and Zhenman Fang. PROBE: Learned Proxy-Based Execution for Highly Selective Multimodal Semantic Queries. PVLDB, 20(1): XXX-XXX, 2027. doi:XX.XX/XXX.XX

1

INTRODUCTION

Semantic query processing extends relational analytics with naturallanguage predicates over unstructured data, enabling semantic filters and joins beyond conventional SQL predicates [10, 11, 15, 24, 31, 33, 38]. For example, the following query, simplified from MMQA Q7 in SemBench [29], identifies airline-image pairs in which the image shows the airline’s logo. Exhaustive execution evaluates

This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 20, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX

Zhengjie Miao

Simon Fraser University Burnaby, Canada zhengjie@sfu.ca

Zhenman Fang

University of Minnesota Twin Cities, USA zhenman@umn.edu

the semantic predicate with a large language model (LLM) for every candidate pair, making the query prohibitively expensive even when only a few pairs match. SELECT t.Airlines, i.uri FROM mmqa.airport t, mmqa.images i WHERE SEM_FILTER( "Determine if the image shows the logo of the airline.", t.Airlines, i.uri)

A promising alternative is proxy-based execution [8, 10, 17, 54]: evaluate a small sample with the LLM, train a lightweight classifier on the resulting labels, and use the classifier to process the remaining candidates. However, this approach becomes unreliable for highly selective queries, where matching candidates are extremely rare. For example, MMQA Q7 contains only five matching pairs among 230,400 candidates, a positive rate of only 2.17 × 10−5 . In such an extremely highly selective scenario, even uniformly sampling 10% of the candidates has approximately a 59% chance of missing all five matches.1 Without positive examples, a proxy cannot learn to recognize the very results the query seeks. Highly selective semantic queries also arise in established benchmarks such as SemBench and LRO-Bench [29, 47], as shown in Table 2, where the positive rates range from 2.17 × 10−5 to 1.39 × 10−1 . The challenge extends beyond discovering the first few matches. Rare positives may span across multiple separated regions of the input space, so sampling around discovered matches can leave other regions unexplored. Even when some positives are found, the limited and potentially biased training labels may not adequately support predictions on the remaining candidates. Moreover, the scarcity of positives makes it difficult to estimate which proxy predictions are incorrect: a classifier can achieve high overall accuracy while missing many matches [51]. Re-evaluating uncertain predictions with the LLM can recover prediction quality, but undermines the cost savings that motivate proxy execution. The central challenge is how to acquire and use limited LLM supervision effectively—to discover rare matches, generalize from scarce labels, and selectively correct remaining prediction errors. Limitations of Existing Systems. Existing proxy-based systems generally follow two approaches: limiting the number of LLM evaluations through a fixed labeling budget, or selecting proxy thresholds to satisfy a quality target. Both face difficulties under high selectivity, but for different reasons. Budget-based systems may miss rare matches. UQE [10] and CSV [17] acquire a limited number of LLM labels for proxy-based execution. When positives are extremely scarce, uniform or active sampling

1 The probability is 207360 / 230400 ≈ 0.59. 5 5

Calibration Sample

Graph-Based Proxy Refinement k-NN Graph

Pilot sampling

Labeled (neg) Labeled (pos)

high selectivity → otherwise → multi-cluster search stratified sampling …

LLM

Calibration refined scores

Unlabeled

Bias Diffusion Before

ScoreSeparate stratified calibration sample sample

Match probability

Selectivity-Adaptive Sampling

After

Refined score

Acquire labels Semantic Query + Candidate Rows

Training Sample

Proxy Training

Cost-Aware Routing Homogeneity Smoothing Before After

Trust proxy

Learn from acquired labels

LLM verification LLM

Query Results

Figure 1: Overview of PROBE: Selectivity-Adaptive Sampling and proxy training, graph-based proxy refinement, and Cost-Aware Routing between the proxy and the LLM. may miss entire regions containing matches, as illustrated in Figure 2. A proxy trained on these incomplete labels may classify the remaining matches as non-matches. In CSV, clusters with no positive samples can receive confident negative votes and bypass further re-clustering, leaving their matches undiscovered. Target-based systems struggle to estimate quality reliably. LOTUS [38], ScaleDoc [54], and BARGAIN [51] use labeled samples to select proxy thresholds under quality constraints. With very few positive examples, estimating precision or recall becomes difficult, potentially leading to conservative thresholds that require many LLM evaluations or poorly estimated thresholds that fail to meet the desired quality. Moreover, accuracy targets can be misleading under severe class imbalance: predicting every candidate as a non-match can achieve high accuracy while missing all matches, as illustrated by BARGAIN’s accuracy mode. These limitations reveal three interdependent challenges: acquiring labels that cover rare positive regions, leveraging scarce labels to generalize to unlabeled candidates, and identifying which remaining predictions require additional LLM evaluations. Importantly, the targeted sampling used to discover rare matches may also introduce selection bias, complicating the estimation of prediction errors and decisions about which predictions to verify. To address these challenges, we present PROBE, a learned proxybased execution framework for highly selective multimodal semantic queries (Figure 1). Given an initial sampling budget 𝐵 and a quality–cost tradeoff parameter 𝛼, PROBE integrates targeted label acquisition, graph-based prediction refinement, and calibrated LLM routing for re-evaluation. Importantly, PROBE separates the training sample, which is selected to discover rare matches, from a calibration sample with known inclusion probabilities, enabling more reliable estimation of match probabilities among the remaining candidates. Our contributions are as follows: 1) Selectivity-Adaptive Sampling (SAS). We propose an adaptive sampling strategy that uses a pilot sample to choose between stratified sampling and multi-cluster search. For highly selective queries, SAS locates positive regions along the candidate ranking, expands sampling around discovered positive seeds and cluster boundaries, and reserves part of the labeling budget

Positive row Negative row Labeled (Uniform)

Labeled (Active) Labeled (Stratified)

Labeled (Top-K) Labeled (PROBE (ours))

Uniform

1/5 positives

Active

1/5 positives

Stratified

2/5 positives

Top-K

2/5 positives

PROBE (ours)

5/5 positives 0

2,000

4,000

6,000

8,000

10,399

Rank of each row

Figure 2: Sampling outcomes on MMQA Q2a, with five matching pairs among 10.4k candidates ranked by descending semantic relevance score. Red dots indicate ground-truth matches, while squares indicate candidates selected for LLM labeling. With the same 5% labeling budget, different sampling policies miss matches scattered across the ranking. for uniform exploration. This helps acquire rare positives and nearby negatives with limited LLM calls. 2) Graph-Based Proxy Refinement. We develop a graph-based refinement method that exploits the structure of unlabeled candidates to augment the supervision provided by scarce LLM labels. It combines proxy residual correction and homogeneity smoothing over a query-conditioned similarity graph to refine scores for unlabeled inputs using the acquired LLM labels. 3) Learned Calibrated Cascade Routing. To address the sampling bias introduced by targeted label acquisition, PROBE fits a calibrator using the acquired training labels and a separate probability sample with known inclusion probabilities. It then uses calibrated match probabilities to select candidates for LLM reevaluation, balancing their estimated contribution to 𝐹 1 against the additional evaluation cost. 4) Experimental evaluation. We evaluate PROBE on highly selective queries from SemBench and LRO-Bench, with positive rates as low as 2.17 × 10−5 . With a 10% initial sampling budget, PROBE achieves a geometric-mean 𝐹 1 of 0.762, compared with 0.797 for exhaustive LLM evaluation, while achieving a geometric-mean speedup of 4.87× and a maximum speedup of 9.3×. 2

2 BACKGROUND 2.1 Semantic Operators

objectives may further reinforce such errors, as predicting all candidates as negative can still achieve high accuracy.

A semantic filter applies a natural-language predicate 𝜙 to each tuple of a relation 𝑇 . Let 𝑦𝜙LLM (𝑡) ∈ {0, 1} denote the label returned by the LLM for tuple 𝑡. Under exhaustive LLM evaluation, the filter returns SemFilter𝜙 (𝑇 ) = {𝑡 ∈ 𝑇 : 𝑦𝜙LLM (𝑡) = 1}.

2.3

Consider the 𝑁 candidates in X = {𝑥 1, . . . , 𝑥 𝑁 } of a semantic filter or join, with LLM labels 𝑦𝑖LLM as defined in Section 2.1. Before routing, proxy-based execution acquires LLM labels for a set 𝑆 ⊆ X of at most 𝐵 candidates for LLM evaluation and uses the acquired labels to train a proxy model and, when applicable, calibrate its prediction. proxy Let 𝑦ˆ𝑖 denote the proxy’s predicted label for candidate 𝑥𝑖 . An additional set 𝐷 ⊆ X \ 𝑆 may then be sent to the LLM. The final output for each candidate is ( 𝑦 LLM, 𝑥𝑖 ∈ 𝑆 ∪ 𝐷, 𝑦ˆ𝑖 (𝐷) = 𝑖proxy 𝑦ˆ𝑖 , otherwise.

A semantic join between relations 𝑇 𝐿 and 𝑇 𝑅 evaluates a naturallanguage predicate 𝜓 on tuple pairs. Its output under exhaustive LLM evaluation is SemJoin𝜓 (𝑇 𝐿 ,𝑇 𝑅 ) = {(𝑡 𝐿 , 𝑡 𝑅 ) ∈ 𝑇 𝐿 × 𝑇 𝑅 : 𝑦𝜓LLM (𝑡 𝐿 , 𝑡 𝑅 ) = 1}. For both operators, let X = {𝑥 1, . . . , 𝑥 𝑁 } denote the set of candidate inputs, where 𝑥𝑖 is a tuple for a semantic filter or a tuple pair for a semantic join. We use 𝑦𝑖LLM ∈ {0, 1} to denote the label returned by the LLM for candidate 𝑥𝑖 . These LLM labels are not assumed to be ground truth; benchmark ground-truth labels are used only for query result quality evaluation.

2.2

Problem Definition

Let ŷ(𝐷) denote the resulting label vector over all 𝑁 candidates, and yLLM the corresponding vector of exhaustive LLM labels. We measure execution quality by the 𝐹 1 score of ŷ(𝐷) relative to yLLM , | and execution cost by the delegation rate 𝑑 (𝐷) = |𝑆 |+|𝐷 , the frac𝑁 tion of candidates evaluated by the LLM. Given an initial sampling budget 𝐵 and a user-specified tradeoff parameter 𝛼 ∈ [0, 1], the objective is to minimize
𝛼 1 − 𝐹 1 ( ŷ(𝐷), yLLM ) + (1 − 𝛼)𝑑 (𝐷), (1)

Technical Background

Sampling. Uniform sampling selects candidates with equal probability, whereas importance sampling favors candidates according to a cheap signal and uses sampling weights to estimate population quantities [27, 57]. Stratified sampling partitions candidates into disjoint groups and allocates samples across them. Neyman allocation assigns samples in proportion to stratum sizes and withinstratum standard deviations to reduce estimation variance [36, 57]. Under low positive rates, uniform sampling may yield few or no positive examples. The efficiency of importance sampling depends on whether the guiding signal identifies likely positives and informative candidates, while stratified allocation requires reliable estimates of within-stratum variances, which are difficult to obtain when positive observations are scarce.

subject to |𝑆 | ≤ 𝐵. Larger 𝛼 prioritizes output quality, while smaller 𝛼 prioritizes reducing LLM evaluation cost. Since exhaustive LLM labels are unavailable during execution, the 𝐹 1 term must be estimated to guide routing decisions.

3

SELECTIVITY-ADAPTIVE SAMPLING AND PROXY TRAINING 3.1 Challenges and Design Goals

Semi-supervised Learning. Semi-supervised learning uses labeled and unlabeled data to improve predictions [48]. Graph-based methods construct a similarity graph over the inputs and propagate information from labeled to unlabeled nodes [49, 55]. These methods typically assume local label consistency: connected nodes tend to have similar labels. Under low positive rates, positive labels may be too scarce to provide supervision for many regions containing matches, while propagation from negative labels may reinforce the majority class. Moreover, when the similarity graph does not reflect label consistency, propagating labels can amplify errors [6, 56].

This section constructs the labeled set 𝐿 used to train the proxy. The initial sample 𝑆 defined in Section 2.3 consists of the training set 𝐿 and a separate calibration sample 𝐴 (Section 5.1), acquired at different stages. PROBE splits the sampling budget 𝐵 into 𝐵𝐿 = ⌊𝜅𝐿 𝐵⌋ for proxy training and 𝐵𝐴 = 𝐵 − 𝐵𝐿 for calibration, where 𝜅𝐿 = 0.6 by default is the fraction allocated to training. Additional LLM calls from routing or whole-query fallback are not included in 𝐵, so the delegation rate may exceed 𝐵/𝑁 . Challenges. To train an accurate proxy, 𝐿 must contain sufficient positive examples and informative negatives near the decision boundary to distinguish matches from similar non-matches. Under high selectivity and a small 𝐵𝐿 , uniform sampling may find no positives, while top-𝐾 sampling can miss positive regions below its cutoff. Stratified sampling distributes the labeling budget across strata, but under high selectivity, even strata containing matches may yield no positive samples, limiting its ability to discover rare positives. Similarly, UQE’s active sampling [10] may fail to acquire positive labels when its initial sample contains no positives. Design goals. SAS therefore aims to (1) assess query selectivity with a small pilot sample, (2) find initial positive examples quickly, (3) explore around discovered positives to locate cluster boundaries and informative negatives, while reserving uniform samples to discover unseen positive clusters, and (4) train the proxy only

Learned Proxy-Expert Routing. Proxy-expert routing decides whether an input is handled by a lightweight proxy or delegated to a more expensive expert [12, 35, 37, 42]. Such cascades have been studied in video analytics [1, 18, 25, 26] and semantic query processing [2, 33, 38, 44]. Learned routing methods use expertlabeled examples and aim to estimate the reliability of proxy predictions, for example, by calibrating proxy scores into probabilities or learning a routing policy. These estimates guide delegation decisions to satisfy quality constraints or balance output quality against expert-evaluation cost [32]. Under low positive rates, scarce positive labels make it difficult to estimate proxy errors reliably. Overestimating these errors leads to excessive LLM calls, while underestimating them risks missing rare matches. Accuracy-based 3

Pilot sampling on rows sorted by encoder score → 95% lower bound 𝜋low on the positive rate no

Multi-cluster search

(highly selective)

yes

Input: ranked rows X, budget 𝐵𝐿 , SAS parameters (§3.2).

yes

𝜋 low > 𝑝★?

Explore phase scan from the highest scores 𝑛 + ≥ 𝑛 min Exploit phase fit clusters and windows + uniform exploration

Train proxy (§3.3)

Algorithm 1 Selectivity-Adaptive Sampling (SAS)

Has both classes?

1: 𝑋 0 ← SampleUniform( X, ⌊ 𝑓pilot 𝐵𝐿 ⌋ ) 2: 𝐿 ← Label(𝑋 0 ), 𝜋 low ← Eq. (2) 3: if 𝜋 low > 𝑝★ then 4: 𝐿 ← Stratified(𝐿) 5: else 6: 𝐿 ← MultiCluster(𝐿) 7: end if 8: if 𝐿 does not include both positive and negative classes then 9: return 𝐿 ∪ Label( X \ 𝐿) ⊲ whole query to the LLM 10: end if 11: return 𝐿

(not highly selective)

Stratified sampling

no

LLM on all rows

12: Function Stratified(𝐿) 13: 𝐻 ← min(𝑀train , ⌊log2 𝑁 ⌋ + 1) 14: 𝑤0 ← 𝑁 /(2𝐻 − 1) 15: for ℎ = 1, . . . , 𝐻 do 16: Xℎ ← {𝑖 : 𝑤0 (2ℎ−1 − 1) ≤ 𝑟𝑖 < 𝑤0 (2ℎ − 1) }

Figure 3: Selectivity-Adaptive Sampling. Pilot sampling selects between stratified sampling and multi-cluster search based on estimated selectivity.

17:

max(1, √︁ |𝑋 0 ∩ Xℎ | ) 𝜂ℎ ← | Xℎ | 𝜋ˆℎ (1 − 𝜋ˆℎ ) end for while |𝐿 | < min(𝐵𝐿 , 𝑁 ) do 𝑈 ← X \ 𝐿, 𝑏 ← min(𝑏 0 , 𝐵𝐿 − |𝐿 |, |𝑈 | ) 𝐻 ← NeymanAlloc(𝑏, (𝜂 ) , ( | X ∩ 𝑈 | ) ) (𝑏ℎ )ℎ=1 ℎ ℎ ℎ ℎ Ð𝐻 23: 𝐿 ← 𝐿 ∪ Label( ℎ=1 SampleUniform( Xℎ ∩ 𝑈 , 𝑏ℎ ) ) 24: end while 25: return 𝐿 26: end Function

Selectivity-Adaptive Sampling

Overview. Selectivity-Adaptive Sampling (SAS) processes candidates ranked by descending cross-encoder score 𝑠𝑖 , computed in one pass that reads the predicate and the candidate together without LLM evaluation. As shown in Algorithm 1, it first labels a pilot sample and computes a lower confidence bound on the positive rate. If the bound exceeds the threshold 𝑝★, SAS uses stratified sampling; otherwise, it performs the multi-cluster search of Algorithm 2. Before sufficient positives are discovered to form clusters, the search prioritizes the highest-scoring candidates. During multicluster search, each batch also reserves a share for uniform sampling across the ranking, allowing SAS to find positives that lie far below the highest-scoring candidates. SAS returns 𝐿 for proxy training if it contains both positive and negative class, and otherwise falls back to exhaustive LLM evaluation. Notation and parameters. Let 𝑟𝑖 ∈ {0, . . . , 𝑁 − 1} denote the rank of candidate 𝑥𝑖 in descending score order, and let 𝑈 = X \ 𝐿 denote the unlabeled candidates. The current class Í counts are 𝑛 + = 𝑥𝑖 ∈𝐿 𝑦𝑖LLM and 𝑛 − = |𝐿| − 𝑛 + . For a candidate set 𝑇 , SampleUniform(𝑇 , 𝑚) draws min(𝑚, |𝑇 |) candidates uniformly, SampleHighestScore(𝑇 , 𝑚) selects the min(𝑚, |𝑇 |) highest-scoring candidates, and Label(𝑇 ) contains their LLM labels. The default parameters are the batch size 𝑏 0 = max(1, ⌊0.01𝑁 ⌋), pilot share 𝑓pilot = 0.3, selectivity threshold 𝑝★ = 0.05, stratum cap 𝑀train = 10, Explore threshold 𝑛 min = 2, exploration share 𝜀 explore = 0.25, cluster penalty 𝜇 = 1.5, and maximum cluster counts 𝐼 max = 6. Pilot sampling. We call a query highly selective if its LLMpositive rate is below 𝑝★ = 0.05. SAS draws a uniform pilot sample 𝑋 0 of 𝑛 0 candidates, of which 𝑛 +0 are positive. It computes a onesided 95% lower confidence bound on the positive rate by inverting the hypergeometric upper tail:  𝜋 low = min 𝐾/𝑁 : 𝑛 +0 ≤ 𝐾 ≤ 𝑁 , Pr[𝑋𝐾 ≥ 𝑛 +0 ] > 0.05 , (2)

LLM 𝑖 ∈𝑋 0 ∩Xℎ 𝑦𝑖

18: 19: 20: 21: 22:

when 𝐿 contains both of positive and negative class, falling back to exhaustive LLM evaluation otherwise.

3.2

𝜋ˆℎ ←

Í

Algorithm 2 Multi-cluster search Input: pilot-labeled 𝐿, ranked rows X, budget 𝐵𝐿 , batch 𝑏 0 , exploration share 𝜀 explore , explore threshold 𝑛 min , cluster penalty 𝜇, maximum cluster counts 𝐼 max . 1: Function MultiCluster(𝐿) 2: 𝜆 ← 0, 𝑗 ← 0, W ← ∅ 3: while |𝐿 | < min(𝐵𝐿 , 𝑁 ) do 4: 𝑈 ← X \ 𝐿, 𝑏 ← min(𝑏 0 , 𝐵𝐿 − |𝐿 |, |𝑈 | ) , 𝜆 ← 𝜆 + 𝜀 explore𝑏 5: 𝑇 ← SampleUniform(𝑈 , ⌊𝜆⌋ ), 𝜆 ← 𝜆 − |𝑇 | ⊲ Explore 6: if 𝑛 + < 𝑛 min then 7: 𝑇 ← 𝑇 ∪ SampleHighestScore(𝑈 \ 𝑇 , 𝑏 − |𝑇 | ) 8: else ⊲ Exploit 9: 𝑗 ← 𝑗 + 1; if 𝑗 = 1: 𝜌 ← 𝑁 1/⌈(𝐵𝐿 −|𝐿|)/𝑏 0 ⌉ 10: I ← FitClusters(𝐿) ⊲ Eq. (3) 11: S ← {𝑖 ∈ 𝐿 : 𝑦𝑖LLM = 1, 𝑟𝑖 ∉ 𝐼 ∀𝐼 ∈ I } ⊲ seeds 12: G ← Gaps( I, S, 𝐿) ⊲ 𝑔 ∈ G: |𝑔| rows, center rank 𝑐𝑔 13: 𝑤𝑔 ← width of the window in W with 𝑐𝑔 , else 𝑁 /𝜌 𝑗 −1
14: 𝑤𝑔 ← min 𝑁 , max(1, |𝑔|, ⌈𝑤𝑔 /𝜌 ⌉ ) ⊲ ∀𝑔 ∈ G 15: W ← Merge( I ∪ {Window(𝑐𝑔 , 𝑤𝑔 ) }𝑔∈G ) 16: 𝑇 ← 𝑇 ∪ SampleNearSeeds(𝑈 \ 𝑇 , S, ⌊ (𝑏 − |𝑇 | )/2⌋ ) 17: 𝑇 ← 𝑇 ∪ SampleInWindow(𝑈 \ 𝑇 , W, 𝑏 − |𝑇 | ) 18: end if 19: 𝐿 ← 𝐿 ∪ Label(𝑇 ) 20: end while 21: return 𝐿 22: end Function

where 𝑋𝐾 ∼ Hypergeom(𝑁 , 𝐾, 𝑛 0 ) is the number of positives in a pilot sample drawn from a population with 𝐾 positives If 𝜋 low > 𝑝★, 4

Unlabeled Labeled negative Labeled positive

Sampled Seed Positive cluster

− (I) the number of labeled negative samples inside cluster, and 𝑛 in a cluster. The clusters minimize the sum of three terms,

Cluster window Seed window

Pilot

𝑛 +out (I) | {z }

positive samples outside

Batch 1

Batch 3 2,000

4,000

6,000

8,000

10,399

Rank of each row

Figure 4: Multi-cluster search on MMQA Q2a among 10.4k candidates. Blue and orange boxes show the selected windows used for sampling; purple boxes show the positive clusters. Red points show selected positive samples, and orange circles mark selected seed samples. SAS rules out high selectivity at the 95% confidence level and uses stratified sampling. Otherwise, SAS cannot rule out high selectivity and starts a multi-cluster search. Stratified sampling. When the pilot rules out high selectivity, it already contains positive examples, so SAS focuses the remaining budget on acquiring informative training labels. Stratified is described in Algorithm 1. SAS divides the score ranking into 𝐻 strata whose widths double with rank and estimates each stratum’s positive rate 𝜋ˆℎ from the √︁ pilot sample. It assigns stratum ℎ the Neyman weight 𝜂ℎ = |Xℎ | 𝜋ˆℎ (1 − 𝜋ˆℎ ) [36]. Large strata with mixed pilot labels receive higher weights, while strata with only one observed class receive zero weight. For each batch of 𝑏 labels, NeymanAlloc allocates samples across strata according to these weights (i.e., Í 𝑏ℎ = 𝑏 𝜂ℎ / 𝑗 𝜂 𝑗 ), with minimum allocations to maintain coverage. SAS samples uniformly within each stratum. Multi-cluster search. When pilot sampling cannot rule out high selectivity, SAS searches for rare positives and their neighboring negatives along the score ranking. It models positive regions as at most 𝐼 max contiguous clusters, treating candidates outside these clusters as negative during fitting. A cluster is a contiguous rank range supported by labeled positives, while a labeled positive outside every fitted cluster is a seed. The rank ranges around cluster boundaries and seeds form windows for subsequent sampling. While 𝐿 contains fewer than 𝑛 min positives, SAS is in the Explore phase: with too few positives to fit clusters, it prioritizes the highest-ranked unlabeled candidates to find initial positives. In every batch, a share 𝜀 explore of the labeling budget is reserved for uniform sampling, allowing SAS to discover positives far below the top-ranked candidates. Once enough positives are found, SAS enters the Exploit phase: it refits the cluster model of Equation 3 using all acquired labels and directs sampling toward seeds and windows around fitted cluster boundaries, while continuing uniform exploration. As labels accumulate, clusters may emerge, grow, shrink, split, or merge. Figure 4 illustrates the process. Fitting clusters. FitClusters covers the labeled positive samples with at most 𝐼 max disjoint clusters I. For a set of clusters I, let 𝑛 +out (I) be the number of labeled positive samples outside every

− 𝑛 in (I) | {z }

negative samples inside

+

𝜇|I| |{z}

,

(3)

penalty per cluster

where |I| is the number of clusters. PROBE minimizes Eq. (3) with the dynamic program in Eq. (4). Eq. (4) follows the standard dynamic program for optimally partitioning ordered data with a penalty per segment [4, 21]. Unlike the standard form, segments alternate between inside and outside; only inside segments pay 𝜇, and their number is capped at 𝐼 max . Eq. (4) scans the labeled rows in rank order and adds the terms of Eq. (3) one row at a time. Let 𝑦𝑖 ∈ {0, 1} be the LLM label of the 𝑖-th labeled row, In𝑖 [𝑞] be the lowest value of Eq. (3) over the first 𝑖 labeled rows using 𝑞 clusters when row 𝑖 lies inside the 𝑞-th cluster, and let Out𝑖 [𝑞] be the same when row 𝑖 lies outside every cluster. Two states are needed because the cost of putting a row inside a cluster depends on the previous row. If the previous row is inside a cluster, the row extends that cluster at no cost. If the previous row is outside, the row starts a new cluster and adds 𝜇. Then

Batch 2

0

+

In𝑖 [𝑞] = (1 − 𝑦𝑖 ) + min In𝑖 −1 [𝑞], Out𝑖 −1 [𝑞 − 1] + 𝜇 ,
Out𝑖 [𝑞] = 𝑦𝑖 + min In𝑖 −1 [𝑞], Out𝑖 −1 [𝑞] ,

(4)

for 1 ≤ 𝑖 ≤ |𝐿|, with 1 ≤ 𝑞 ≤ 𝐼 max for In and 0 ≤ 𝑞 ≤ 𝐼 max for Out. In Eq. (4), the first term is the cost of row 𝑖 itself: 1 − 𝑦𝑖 counts a negative sample inside a cluster, and 𝑦𝑖 counts a positive sample outside every cluster. The minimum picks the cheaper state of row 𝑖 − 1. The smallest entry of In |𝐿 | [𝑞] and Out |𝐿 | [𝑞] over 0 ≤ 𝑞 ≤ 𝐼 max is the minimum of Eq. (3), and backtracking recovers I. The penalty 𝜇 sets how much labeled evidence a cluster needs. A cluster that covers 𝑛𝐼+ labeled positives and 𝑛𝐼− labeled negatives lowers Eq. (3) only if 𝑛𝐼+ − 𝑛𝐼− > 𝜇. For example, with 𝜇 = 1.5, a cluster must cover at least two more positive than negative samples. A lone positive sample stays a seed, while two positives with no labeled negative between them can support a cluster. Windows and allocation. Let S be the set of seeds, i.e., labeled positives outside the fitted clusters I. The boundaries of these clusters and the extents of positive regions around seeds remain uncertain within the unlabeled gaps up to the nearest labeled candidates. Gaps(I, S, 𝐿) identifies these gaps; let |𝑔| and 𝑐𝑔 denote the size and center rank of gap 𝑔. Since early clusters may have inaccurate boundaries, SAS samples from wider windows around these gaps, where Window(𝑐, 𝑤) denotes the 𝑤 ranks centered at 𝑐. Let W be the windows from the previous Exploit batch. In the 𝑗-th Exploit batch, a gap centered within a previous window inherits its width reduced by a factor of 𝜌; otherwise, its window starts with width 𝑁 /𝜌 𝑗 . SAS sets 𝜌 in the first Exploit batch so that 𝑁 /𝜌 𝑗 approaches one when the sampling budget runs out. Fitted clusters are also included as windows, allowing negative labels within them to trigger splits, and Merge combines overlapping windows. After reserving the uniform exploration share, SampleNearSeeds(𝑈 , S, 𝑚) uses up to half of the remaining budget to sample near seeds in round-robin order, or sample uniformly 5

Algorithm 3 Graph-Based Proxy Refinement

1. Build kNN graph

Input: row embeddings 𝑒, proxy scores 𝑍 , labeled set 𝐿 with LLM labels 𝑦𝐿LLM , neighbor count 𝑘, diffusion and propagation rounds 𝑇1,𝑇2 , diffusion decay 𝛽, propagation weight 𝛾, label threshold 𝜃 ref . 1: 𝑊 ← SymmetricKNN(𝑒, 𝑘) 2: 𝑃 ← diag(𝑊 1) −1𝑊 (0) 3: Δ (0) ← 0, Δ𝐿 ← 𝑦𝐿LLM − 𝑍 𝐿 4: for 𝑡 = 1, . . . ,𝑇1 do 5: Δ (𝑡 ) ← 𝛽𝑃 Δ (𝑡 −1) 6: Δ𝐿(𝑡 ) ← 𝑦𝐿LLM − 𝑍 𝐿 7: end for 8: 𝑓 (0) ← clip(𝑍 + Δ (𝑇1 ) , 0, 1) 9: for 𝑡 = 1, . . . ,𝑇2 do 10: 𝑓 (𝑡 ) ← (1 − 𝛾)𝑓 (0) + 𝛾𝑃 𝑓 (𝑡 −1) 11: 𝑓𝐿(𝑡 ) ← 𝑦𝐿LLM 12: end for 13: 𝑓 ← 𝑓 (𝑇2 ) 14: 𝑦 refined ← 1 [𝑓 ≥ 𝜃 ref ] 15: return (𝑓 , 𝑦 refined )

0.42 ->0.56

0.55

Y=1

0.85

0.40 0.31

+.02 +.04

+.12

Y=0

+.12

0.55 ->0.39

0.40

0.31 +.06 ->0.47 0.48 ->0.50

0.20 0.48

−.16

0.20

−.04

3. Homogeneity Propagation 0.56 ->0.71 1.00 +.03 +.10

+.12

1.00 +.05

4. Label Assignment ŷ=1

0.39 ->0.23 −.16

1.00

Labeled +

Labeled −

0.71

ŷ=0 0.23

1.00

ŷ=1

0.47 +.05 0.00 ->0.62 0.5 ->0.43 −.12

0.62

0.00 0.43

ŷ=0

Unlabeled

Newly classified

Figure 5: Graph-based proxy refinement: (1) build a 𝑘-NN graph with LLM labels and proxy scores; (2) correct scores by bias diffusion; (3) smooth scores while pinning labeled rows; and (4) threshold at 𝜃 ref to assign refined labels. same direction. Second, local homophily assumes that nearby rows tend to have the same LLM-predicted label. The two assumptions motivate propagating the residuals and smoothing the corrected scores, respectively [20, 55].

4.2

Graph Construction

4.3

Score Propagation

SymmetricKNN in Algorithm 3 builds a symmetric 𝑘-NN graph whose nodes are the input rows (pairs for a join), each represented by its cross-encoder feature 𝑒𝑖 . PROBE first normalizes each embedding, 𝑒˜𝑖 = 𝑒𝑖 /∥𝑒𝑖 ∥ 2 , and connects every input to its 𝑘 nearest neighbors under Euclidean distance. It assigns each edge the Gaussian weight 𝑊𝑖 𝑗 = exp(−∥𝑒˜𝑖 − 𝑒˜ 𝑗 ∥ 22 /2𝜎 2 ) for 𝑗 ∈ N𝑖 and sets 𝑊𝑖 𝑗 = 0 otherwise. The bandwidth 𝜎 is the median distance from each embedding to its 𝑘th nearest neighbor. N𝑖 contains both the 𝑘 neighbors selected by row 𝑖 and any rows that select 𝑖 as one of their own nearest neighbors. Both refinement phases use 𝑃 = diag(𝑊 1) −1𝑊 . Here, 1 is the all-ones vector, diag(𝑧) denotes the diagonal matrix with diagonal 𝑧.

Proxy Training

PROBE trains a lightweight proxy on the LLM-labeled set 𝐿 acquired by SAS. For each candidate 𝑥𝑖 , the cross-encoder used for ranking processes the natural-language predicate together with the candidate and produces a score 𝑠𝑖 . We also extract its last-token hidden state, normalize it to unit length, and project it to 256 dimensions using PCA. The resulting feature vector 𝑒𝑖 represents 𝑥𝑖 conditioned on the predicate. For a semantic join, the cross-encoder processes both tuples of the candidate pair, so 𝑒𝑖 represents the pair rather than either tuple alone. The proxy ℓ is an 𝐿2 -regularized logistic regression model trained on 𝐿, with weight vector 𝑣 and intercept 𝑣 0 . Its inverse regularization strength 𝐶 LR controls the penalty on model weights; larger values correspond to weaker regularization (𝐶 LR = 1 by default). To mitigate class imbalance, we weight each class inversely to its frequency in 𝐿. Applying ℓ to all candidates produces proxy scores

Score propagation returns refined scores 𝑓𝑖 ∈ [0, 1] and refined labels 𝑦𝑖refined ∈ {0, 1}, without retraining the proxy or calling the LLM. Figure 5 illustrates how the algorithm works. Bias diffusion. PROBE initializes Δ𝐿(0) = 𝑦𝐿LLM −𝑍 𝐿 and Δ𝑈(0) = 0. At each iteration, it applies 𝛽𝑃 and restores the observed residuals on 𝐿. After 𝑇1 iterations, PROBE clips 𝑍 + Δ (𝑇1 ) to [0, 1] and sets its labeled entries to 𝑦𝐿LLM . Homogeneity propagation. At each iteration, PROBE combines the corrected vector 𝑓 (0) and 𝑃 𝑓 (𝑡 −1) with weights 1 − 𝛾 and 𝛾, then restores the labels on 𝐿. After 𝑇2 iterations, it thresholds the unlabeled scores at 𝜃 ref (0.5 by default).

𝑍𝑖 = sig(𝑣 ⊤𝑒𝑖 + 𝑣 0 ) ∈ (0, 1),

where sig is the logistic sigmoid function.

4 GRAPH-BASED PROXY REFINEMENT 4.1 Refinement Assumption

The proxy scores each row from its own feature, independently of the others. PROBE adds a weighted 𝑘-nearest-neighbor (𝑘-NN) graph to share residual error and score information between nearby rows, using the LLM labels in 𝐿 as anchors. The refinement relies on two empirical assumptions. First, local error correlation assumes that when the proxy over- or underestimates the score of one labeled row, nearby rows may exhibit a residual error 𝑦𝑖LLM − 𝑍𝑖 in the

0.42

0.85

if no seeds exist. SampleInWindow(𝑈 , W, 𝑚) allocates the remaining budget across windows: each cluster-associated window receives one share, while seed-only windows together receive one share. Candidates are sampled uniformly within each window.

3.3

2. Bias Diffusion

Y=1

5

LEARNED CALIBRATED CASCADE ROUTING

Target-based cascades select candidates for LLM evaluation to meet a user-specified quality target. Under low positive rates, scarce 6

1 Calibration

sampling

Refined scores f

Remaining rows U

2 Probability

calibration

Input: rows X, labeled set 𝐿 with LLM labels 𝑦𝐿LLM , refined scores 𝑓 and labels 𝑦 refined , out-of-fold scores 𝑓𝐿oof , calibration budget 𝐵𝐴 , score bins 𝑛 bin , even-allocation share 𝜀𝐴 , quality–cost weight 𝛼. 1: 𝑈 ← X \ 𝐿, 𝑚 ← min(𝐵𝐴 , |𝑈 | ) ⊲ calibration budget 2: (𝐴, 𝜔 ) ← CalibrationSample(𝑈 , 𝑓 , 𝑚, 𝑛 bin , 𝜀𝐴 ) 3: 𝐴 ← Label(𝐴), 𝑆 ← 𝐿 ∪ 𝐴 4: 𝑦ˆ ← 𝑦 refined , 𝑦ˆ𝑆 ← 𝑦𝑆LLM 5: if 𝐴 = ∅ or 𝑆 = X then 6: return 𝑦ˆ 7: end if 8: (𝑎, 𝑐 ) ← Calibrate(𝐴, 𝐿, 𝜔, 𝑓 , 𝑓𝐿oof ) 9: if calibration fails then 10: return 𝑦ˆ 11: end if 12: 𝑝𝑖 ← sig(𝑎logit𝜖 ( 𝑓𝑖 ) + 𝑐 ), 𝑖 ∉ 𝑆  |𝑆 |+|𝐷 | 13: 𝐷 ∗ ← arg min 𝛼 (1 − 𝐹e1 (𝐷 ) ) + (1 − 𝛼 ) 𝑁

Tradeoff α Training sample L

Score-stratified sampling

Calibration sample A

Routing optimization (select D*) Refined score f

Platt calibration

p

High-score negatives

Low-score positives Other D* rows

LLM verification (on D*)

Keep refined label

LLM f Calibration sample A

Algorithm 4 Learned Calibrated Cascade Routing

3 Cost-aware routing

Calibrated match probability p

LLM

Final labels

Figure 6: Learned calibration and cost-aware routing. positive labels make it difficult to assess whether a routing policy meets the target. PROBE instead estimates output quality from learned match probabilities and optimizes its tradeoff with LLM cost. Overestimating the benefit of LLM verification can lead to unnecessary LLM calls, while underestimating it can leave proxy errors uncorrected, including missed rare positives. Learning reliable match probabilities is challenging under high selectivity. SAS concentrates positive examples in 𝐿, but its preference for likely matches makes 𝐿 unrepresentative of the remaining candidates. A calibrator fitted on 𝐿 alone may overestimate their match probabilities. In contrast, uniform sampling of the remaining candidates may yield too few positives for reliable calibration. Positive-label scarcity can also delay calibration in GAMCAL [32], which samples uniformly from its uncertain region and requires examples of both classes. PROBE therefore fits a calibrator jointly on 𝐿 and a separate calibration sample 𝐴. The positives in 𝐿 help learn the relationship between refined scores and LLM labels, while the known inclusion probabilities of 𝐴 support weighted calibration that corrects for the selection bias in 𝐿. Figure 6 illustrates the three steps, summarized in Algorithm 4. First, PROBE draws a score-stratified calibration sample 𝐴 from 𝑈 = X \ 𝐿 and obtains its LLM labels. Second, it fits the calibrator on 𝐿 and 𝐴 and converts the refined scores of candidates outside 𝑆 = 𝐿 ∪𝐴 into match probabilities 𝑝𝑖 . Finally, guided by the quality– cost weight 𝛼, it selects a set 𝐷 ∗ ⊆ X \ 𝑆 for LLM verification, potentially including high-score predicted negatives and low-score predicted positives. Other candidates retain their refined labels. If 𝐴 or X \ 𝑆 is empty, or calibration fails, PROBE keeps the available LLM labels and uses refined predictions for the rest.

5.1

𝐷 ⊆X\𝑆

LLM 14: 𝐷 ∗ ← Label(𝐷 ∗ ), 𝑦ˆ𝐷 ∗ ← 𝑦𝐷 ∗ 15: return 𝑦ˆ

𝐻𝐴 ≤ ⌈𝜀𝐴𝑚⌉ strata 𝑈 1, . . . , 𝑈𝐻𝐴 . Stratum 𝑈 𝑗 has size 𝑁 𝑗 = |𝑈 𝑗 |, √︃ mean refined score 𝑓¯𝑗 , and Neyman weight 𝜂 𝑗 = 𝑁 𝑗 𝑓¯𝑗 (1 − 𝑓¯𝑗 ).

PROBE spreads ⌈𝜀𝐴𝑚⌉ draws evenly over the strata, one at a time to a non-full stratum with the fewest draws, so every stratum gets at least one. It splits the other draws in proportion to 𝜂 𝑗 [36] over the non-full strata and assigns leftover draws by the same fewestÍ 𝐴 𝑛 𝑗 = 𝑚. draws rule. The final quotas satisfy 1 ≤ 𝑛 𝑗 ≤ 𝑁 𝑗 and 𝐻𝑗=1 CalibrationSample draws 𝑛 𝑗 rows uniformly from each stratum and returns 𝐴 with 𝜔𝑖 = 𝑁 𝑗 /𝑛 𝑗 for 𝑖 ∈ 𝐴 ∩ 𝑈 𝑗 . Calibrator. PROBE uses a Platt-style model [39] to estimate LLM match probabilities from refined scores. Eq. (5) specifies the model, and Eq. (6) gives its fitting objective. At a finite optimum, the fitted probabilities satisfy Eq. (7): the predicted and observed positive counts on 𝐴 agree after inverse-probability weighting.
𝑔𝑖 = sig 𝑎 logit𝜖 ( 𝑓ˆ𝑖 ) + 𝑐ˆ𝑖 ,

𝑎 ≥ 0, (5) oof ˆ where ( 𝑓𝑖 , 𝑐ˆ𝑖 ) = (𝑓𝑖 , 𝑐 𝐿 ) for 𝑖 ∈ 𝐿 and (𝑓𝑖 , 𝑐) for 𝑖 ∈ 𝑈 , 𝑓𝑖 is the refined score from
Algorithm 3, sig(𝑥) = 1/(1 + 𝑒 −𝑥 ), and logit𝜖 (𝑓 ) = ln 𝑓¯/(1− 𝑓¯) with 𝑓¯ = min(1−𝜖, max(𝜖, 𝑓 )). The slope 𝑎 sets how fast the match probability rises with the refined score, and the intercept sets the overall level of the probabilities, i.e., how many positive samples the model expects. The shared slope 𝑎 learns the score–label relationship from both samples, while separate intercepts 𝑐 𝐿 and 𝑐 allow their baseline match probabilities to differ. This parameterization is motivated by the intercept shift under case–control sampling [28, 40], although it remains a modeling approximation for SAS’s adaptive sampling. Fitting. PROBE fits 𝑎, 𝑐 and 𝑐 𝐿 together by weighted maximum likelihood, as in Platt scaling [39]. PROBE minimizes it over both samples,

Learned Calibration

Calibration Set Sampling. The calibration sample 𝐴 provides labels from 𝑈 for the weighted fit. PROBE draws 𝑚 = min(𝐵𝐴 , |𝑈 |) rows from 𝑈 with known inclusion probabilities, so each row of 𝐴 can be weighted by the number of rows of 𝑈 it represents. A uniform sample would spend most draws on low-score rows that are almost all negative, so PROBE stratifies 𝑈 by refined score and uses score-based estimates of within-stratum variability to guide sample allocation. It partitions 𝑈 into 𝑛 bin = 10 equal-width score bins and drops empty bins. While more than ⌈𝜀𝐴𝑚⌉ bins remain, it merges the adjacent pair with the smallest combined size , which leaves

min

𝑎≥0, 𝑐, 𝑐 𝐿

∑︁ 𝜔𝑖 𝜔¯ 𝑖 ∈𝐴

BCE(𝑦𝑖LLM, 𝑔𝑖 ) +

∑︁ 𝑖 ∈𝐿

BCE(𝑦𝑖LLM, 𝑔𝑖 ),

(6)

where BCE(𝑦, 𝑔) = −𝑦 log 𝑔 − (1 − 𝑦) log(1 − 𝑔), 𝜔𝑖 is the inverse of the probability that row 𝑖 was drawn into 𝐴, i.e., the number of rows of 𝑈 it stands for, and 𝜔¯ is the mean weight over 𝐴, so that 𝐴 7

Table 1: Default parameters of proxy training, graph refinement, calibration and routing.

counts as |𝐴| rows. Weighting the log-likelihood of each row by the inverse of its inclusion probability is the standard way to fit a model on an unequal-probability sample [5, 34]. For the rows of 𝐿, PROBE uses out-of-fold features: it splits 𝐿 into 𝑅fold stratified folds and, for each fold, retrains the proxy and reruns graph refinement without it, yielding 𝑓𝑖oof on the held-out rows. This prevents calibration on training scores that were computed using the candidates’ own LLM labels. Weighted fit on calibration sample set 𝐴. For a fixed shared slope 𝑎, the intercept 𝑐 is determined by the inverse-probabilityweighted loss on 𝐴. For 𝑚 > 0, every row in 𝑈 𝑗 has inclusion probability 𝑛 𝑗 /𝑁 𝑗 > 0. Conditional on 𝐿, the Horvitz–Thompson b+ = Í𝑖 ∈𝐴 𝜔𝑖 𝑦 LLM is unbiased for the number of estimate [16] 𝑁 𝑖 LLM-positive rows in 𝑈 under the calibration sampling. At a finite optimum of Eq. (6), setting its derivative with respect to 𝑐 to zero gives ∑︁ 𝑖 ∈𝐴

b+ = 𝜔𝑖 sig 𝑎 logit𝜖 (𝑓𝑖 ) + 𝑐 = 𝑁

∑︁

𝜔𝑖 𝑦𝑖LLM .

(7)

estimated quality loss

10 0.2 min(5, 𝑛 + , 𝑛 − ) 10 −6 0.15, 0.05 0.5

delegation rate

Routing set. Verifying a predicted positive removes an expected 1− 𝑝𝑖 false positives, while verifying a predicted negative converts an expected 𝑝𝑖 false negatives into true positives. Since the calibrated probabilities 𝑝𝑖 are non-decreasing in refined scores 𝑓𝑖 (𝑎 ≥ 0), PROBE prioritizes predicted positives with the lowest scores and predicted negatives with the highest scores. + index the predicted positives outside 𝑆 in increasLet 𝑖 1+, . . . , 𝑖𝑚 + − index the predicted negatives in ing order of 𝑓𝑖 , and 𝑖 1− , . . . , 𝑖𝑚 − decreasing order. An optimal routing set therefore has the form 𝐷 ∗ = {𝑥𝑖 +𝑗 : 1 ≤ 𝑗 ≤ 𝑟 + } ∪ {𝑥𝑖 −𝑗 : 1 ≤ 𝑗 ≤ 𝑟 − },

(10)

for some 𝑟 + and 𝑟 − .

For a fixed number 𝑟 = 𝑟 + + 𝑟 − of routed candidates, the delegation cost is constant depending only on 𝑟 = 𝑟 + + 𝑟 − , so PROBE picks the split 𝑟 + that maximizes 𝐹e1 . The numerator and denominator of 𝐹e1 are linear in the 𝑝𝑖 of the selected candidates, so PROBE uses Dinkelbach’s method [13] to transform this ratio optimization into a sequence of objectives concave in 𝑟 + , each solved by binary search. It then selects the best 𝑟 to minimize Eq. (9).

After calibration, the candidates in 𝑆 = 𝐿 ∪𝐴 have LLM labels, while each remaining candidate 𝑥𝑖 ∉ 𝑆 has a calibrated match probability 𝑝𝑖 and a refined label 𝑦𝑖refined . PROBE selects an additional set 𝐷 ⊆ X \ 𝑆 for LLM evaluation. As defined in Section 2.3, the final output uses LLM labels for candidates in 𝑆 ∪ 𝐷 and refined labels for the others. To estimate output quality before evaluating 𝐷, PROBE uses 𝑝𝑖 to estimate the true-positive, false-positive, and false-negative counts relative to exhaustive LLM evaluation:

6 EVALUATION 6.1 Experimental Setup

Implementation and configuration. PROBE is implemented on a SparkSQL/vLLM stack. Unless otherwise stated, all systems use Gemma 4 26B-A4B [14] as the expert LLM. All systems send their LLM calls to the same vLLM server with the same batching configuration. All experiments run on one server with two NVIDIA RTX PRO 6000 Blackwell Max-Q GPUs, a 20-core Intel Xeon w73445 and 128 GB of DRAM. SAS uses the default parameters of §3.2, and Table 1 lists those of the later stages. Datasets and queries. We evaluate PROBE on the queries with the lowest ground-truth positive rates across SemBench [29] and LROBench [47]. The workload mixes semantic filters and joins over text and image inputs, with positive rates ranging from 2.17×10−5 to 1.39×10−1 and rows from a few hundred to over half a million as

(8)

𝑖

Í where 𝐶 = 𝑥𝑖 ∈𝑆 𝑦𝑖LLM counts the known positives in 𝑆. The estimated output quality is f (𝐷) 2TP f f f (𝐷) 2TP (𝐷) + FP (𝐷) + FN

1 ⌊3 log2 𝑁 ⌉ 0.8, 0.8 50 0.5 0.6

Replacing the unknown 𝐹 1 in Eq. (1) with this estimate, PROBE selects 𝐷 by minimizing
min 𝛼 1 − 𝐹e1 (𝐷) + (1 − 𝛼) 𝑑 (𝐷) . (9) 𝐷 ⊆ X\𝑆 |{z} | {z }

Routing Objective

𝐹e1 (𝐷) =

Default

𝑅fold 𝜖 𝜈CP , 𝛿 CP 𝛼

𝑖 ∈𝐴

Í f (𝐷) = 𝐶 + Í TP 𝑖∉𝑆, 𝑦𝑖refined =1 𝑝𝑖 + 𝑖 ∈𝐷, 𝑦𝑖refined =0 𝑝𝑖 , f (𝐷) = Í FP 𝑖∉𝑆∪𝐷, 𝑦𝑖refined =1 (1 − 𝑝𝑖 ), Í f (𝐷) = FN 𝑖∉𝑆∪𝐷, 𝑦 refined =0 𝑝𝑖 ,

Meaning inverse 𝐿2 strength of the logistic-regression proxy neighbors per row in the 𝑘 -NN graph weight of bias diffusion and of homogeneity propagation maximum iterations of the two refinement phases threshold that turns refined scores into labels share of the sampling budget for proxy-training labels, the rest is for calibration equal-width refined-score strata for calibration share of calibration draws split evenly across strata (at least one per stratum) cross-fitting folds, 𝑛 ± : positive/negative training labels score clipping level before the calibration logit share and level of the Clopper–Pearson target (§5.1) quality–cost tradeoff of routing

𝑛 bin 𝜀𝐴

This equality balances the weighted predicted and observed positive counts on the calibration sample 𝐴. It is the weighted form of a known property of logistic regression: with an intercept, the fitted and the observed numbers of positives are equal. PROBE routes with 𝑝𝑖 = sig(𝑎 logit𝜖 (𝑓𝑖 ) + 𝑐) and drops 𝑐 𝐿 . When 𝐴 contains no b+ = 0, and Eq. (7) would set every 𝑝𝑖 to zero. positive sample, 𝑁 PROBE then uses an upper bound to set a target number of positives in 𝑈 and fits 𝑐 to this target. It fits 𝑎 and 𝑐 𝐿 on 𝐿 alone, computes a one-sided Clopper–Pearson upper bound [9] at level 𝛿 CP = 0.05 b+ on the number of positives in 𝑈 , and solves Eq. (7) for 𝑐 with 𝑁 replaced by a heuristic share 𝜈 CP = 0.15 of this bound. Calibration fails if the solver for Eq. (6) does not converge. PROBE then keeps the refined labels without calibration.

5.2

Symbol

𝐶 LR 𝑘 𝛽, 𝛾 𝑇1 ,𝑇2 𝜃 ref 𝜅𝐿

8

Quality

No proxy

1.00 0.75 0.50 0.25 0.00

UQE

BARGAIN

CSV

LOTUS

ScaleDoc

PROBE

2a A Q7 m Q7 m Q8 m Q9 13 13 21 02 05 Q1 Q3 Q4 Q8 Q m Q Cars Cars Cars imals LRO 1 LRO 1 LRO 2 LRO 3 m m m M o o o m c c c o M E E E An Ec

AQ

Q MM

Figure 7: Mean 𝐹 1 over five runs on the evaluated queries. Error bars indicate ±1 standard deviation across seeds. Budget-based systems use a 10% sampling budget and target-based systems use a target of 0.9.

No proxy (1×)

UQE

BARGAIN

CSV

LOTUS

ScaleDoc

PROBE

Speedup

10× 8× 6× 4× 2× 0×

A MQ

M

Q2a QA Q7 m Q7 m Q8 m Q9 m Q13 ars Q3 ars Q4 ars Q8 als Q1 O 113 O 121 O 202 O 305 C C C m LR LR LR LR MM Ecom Ecom Ecom Ecom Ani Figure 8: Speedup over the no-proxy baseline under the settings of Figure 7.

Table 2: The 14 evaluated queries. Type F is a semantic filter, and J is a semantic join, and Size is the number of candidates (tuples for filters, tuple pairs for joins). Query

Scenario

Type Modality

MMQA Q2a MMQA Q7 Ecomm Q7 Ecomm Q8 Ecomm Q9 Ecomm Q13 Cars Q3 Cars Q4 Cars Q8 Animals Q1 LRO 113 LRO 121 LRO 202 LRO 305

MMQA MMQA E-commerce E-commerce E-commerce E-commerce Cars Cars Cars Animals Santos Santos Movie Schools

J J J J J F F F F F J J J J

text+image text+image text text+image text+image text+image text+image text text+image text+image text text text text

• BARGAIN [51] cascades a cheap proxy before the LLM and calibrates a confidence threshold to meet a SUPG-style [27] statistical guarantee. We use its accuracy mode with target 0.9 and failure probability 𝛿 = 0.1, with no cap on LLM budget. It uses the cosine similarity between the row and predicate embeddings as the proxy score, computed with the same embedding models as LOTUS’s join proxy. • ScaleDoc [54] trains a query-specific proxy, an MLP projection over the frozen embeddings trained with contrastive learning, and calibrates a two-threshold cascade that sends rows between the thresholds to the LLM. We use 5%/5% of the rows for training/calibration and an 𝐹 1 target of 0.9. • CSV [17] clusters the embeddings with 𝑘-means (𝑘 = 4, and 𝑘 = 2 when re-clustering), samples 10% of each cluster for LLM labels, and assigns a cluster’s label when at least 90% of its sampled rows agree. • UQE [10] is the sampling and proxy training method that AIQA [8] uses. It spends the budget 𝐵 with online active learning: in each round, it labels the unlabeled rows that the current logistic-regression proxy scores highest and refits the proxy on all labeled rows. The final proxy labels all remaining rows.

Size Positive Rate

10,400 230,400 525,625 115,768 25,440 3,992 10,070 157,269 30,130 1,600 266 1,426 384 1,421

5×10 −4 2.17×10 −5 9.4×10 −3 3×10 −4 2.65×10 −2 3×10 −3 3.39×10 −2 1.39×10 −1 5.4×10 −3 6.1×10 −2 7.52×10 −3 4.91×10 −3 7.81×10 −3 7.74×10 −3

shown in Table 2. PROBE’s routing objective measures 𝐹 1 against the expert LLM labels (§5.2), since these are the only labels available during execution. The 𝐹 1 values reported in this section are instead measured against the human-annotated ground-truth labels. Baselines. We compare PROBE against five recent proxy based semantic query systems and the no-proxy baseline, which is the PROBE implementation that disables all optimizations and invokes the LLM on every input row. All systems use the same prompts. PROBE uses the scores of the Qwen3-VL-Reranker-2B [30] crossencoder to rank rows for sampling. • LOTUS [38] optimizes semantic operators with model cascades and accuracy-aware approximation. For filters, its proxy is the token log-probability of Qwen3-VL-2B [3]. For joins, we enable LOTUS’s join cascade, whose proxy is the embedding similarity of e5-base-v2 for text and CLIP ViT-B/32 for images. We set both its recall and precision targets to 0.9, with failure probability 𝛿 = 0.1 and a default sampling rate of 10%.

6.2

End-to-end Comparison

Figure 7 and Figure 8 compare the systems under the defaults of §6.1: the budget-based systems (UQE, CSV and PROBE) use 𝐵/𝑁 = 10%, with 𝛼 = 0.5 for PROBE, and the target-based systems (LOTUS, BARGAIN and ScaleDoc) use a target of 0.9. The two limitations of section 1 both appear. LOTUS and ScaleDoc over-delegate yet achieve lower quality: ScaleDoc reaches a geometric-mean 𝐹 1 of 0.530 at a geometric-mean delegation rate of 59.8%, and LOTUS sends 54.6% of the rows to the LLM for an 𝐹 1 of 0.485. BARGAIN delegates 25.6%, but its accuracy target is met mostly by the many 9

UQE

BARGAIN

Quality

MMQA Q2a

CSV

MMQA Q7

1.0

0.9

0.6

0.6

0.3

0.3

LOTUS

Ecomm Q7

10

Ecomm Q9

10

0.75

0.75

0.50

0.50

0.50

0.50

0.25

0.25

0.25

0.25

100

10

Cars Q8

100

Cars Q3 1.00 0.88 0.80

0.00 10

Animals Q1

No proxy

Ecomm Q13

0.75

0.00

100

Cars Q4

Ecomm Q8

PROBE (α=0.5)

0.75

0.0

0.0

ScaleDoc

100

10

LRO 113

100

10

LRO 121

100

10

LRO 202

0.3

0.75

1.0

1.0

1.0

0.75

0.4

0.2

0.50

0.6

0.6

0.6

0.50

0.2

0.1

0.25

0.3

0.3

0.3

0.25

0.0

0.0

0.00

0.0

0.0

0.0

10

100

1

10

10

100

10

100

10

100

100

LRO 305

0.00 10

100

10

100

Delegation rate (% of N)

6.3

Geometric-mean quality

non-matching rows, so its geometric-mean 𝐹 1 stays at 0.473. The budget-based systems delegate less but lose quality: UQE and CSV reach 𝐹 1 below 0.2 on 9 and 6 queries, respectively. PROBE attains a geometric-mean 𝐹 1 of 0.762, compared to 0.797 for the no-proxy baseline, with a geometric-mean delegation rate of 12.8%, a 4.87× geometric-mean speedup and a maximum speedup of 9.3×. Because several queries have very few positives, we rerun each system’s configuration with five seeds and test whether PROBE’s 𝐹 1 differs from that of each baseline. We draw bootstrap samples by resampling the seeds and, within each query, the positive and negative rows separately, and compute the 95% confidence interval (CI) for each mean 𝐹 1 and each difference. A difference is significant at the 0.05 level when its 95% CI excludes zero. Over the 14 queries, PROBE’s geometric mean 𝐹 1 is 0.762 (95% CI [0.733, 0.789]), and it significantly outperforms all five proxy-based baselines. On the seven queries with fewer than 20 positives, PROBE reaches an 𝐹 1 of 0.902 (95% CI [0.848, 0.920]), compared to 0.905 [0.865, 0.961] for the full LLM evaluation. These results show that PROBE can approach exhaustive LLM quality under extreme positive scarcity without evaluating most candidates with the LLM.

0.6 0.5 0.4 0.3 0.2 0.1 0.0

Uniform Stratified Top-K

Active PROBE

5% 10% 15% 20% 25%

Sampling Budget

(a) Sampling policy

Geometric-mean quality

Figure 9: Quality–cost tradeoff of each system. The grey dashed line marks the quality of full LLM evaluation.

1.0 0.8 0.6 0.4 0.2 0.0

No Refinement Bias Diffusion + Homogeneity Prop.

5% 10% 15% 20% 25%

Sampling Budget

(b) Graph refinement stage

Figure 10: Geometric-mean quality for (a) five sampling policies with graph refinement disabled and (b) the graph refinement stages added on top of PROBE sampling. 17.9% of the rows to the LLM. Its geometric-mean latency is 59.5 s against 213.9 s, a 3.6× speedup. The strongest baseline, ScaleDoc, only reaches 0.530 while sending 59.8% of the rows to the LLM. At its cost-first points, PROBE keeps at least 90% of the no-proxy quality except on Ecomm Q9 and achieves a geometric-mean quality of 0.760 at 12.7% delegation. Its geometric-mean latency is 43.8 s, corresponding to a 4.9× speedup.

Quality–Cost Tradeoff

We sweep target values over {0.1, 0.3, 0.5, 0.7, 0.9} for the targetbased systems, and sampling budgets over 𝐵/𝑁 ∈ {5, 10, 15, 20, 25}% for the budget-based systems. Figure 9 shows the quality-cost tradeoff curves of each system, and Table 3 reports selected best operating points. For each baseline it reports the lowest-𝑑 point among those that reach the baseline’s highest quality on the query. For PROBE, the quality-first and cost-first points are selected from separate budget sweeps with 𝛼 = 0.9 and 𝛼 = 0.1, respectively. At each fixed 𝛼, we sweep the sampling budget and, for each query, select the lowest-𝑑 point attaining the highest 𝐹 1 in the budget sweep. These two operating-point configurations are separate from the default setting of 𝛼 = 0.5 and 𝐵/𝑁 = 10%. Figure 9 shows that across the delegation range, PROBE’s curve lies above or on the baselines’ on most queries. As Table 3 shows, at its quality-first points, PROBE attains a geometric-mean quality of 0.790, against 0.797 for the no-proxy baseline, while sending

6.4

Ablation on Sampling Policy

We isolate the sampling policy by disabling graph refinement, calibration, and routing. Each method uses the same training-label budget and trains the same logistic-regression proxy on its acquired LLM labels, and then applies the proxy to predict the remaining candidates. We compare PROBE’s SAS with uniform sampling, stratified sampling (Neyman allocation), top-𝐾 sampling, and UQE’s active sampling [10], varying the training-label budget |𝐿|/𝑁 from 5% to 25%. As Figure 10(a) shows, PROBE achieves the highest geometric-mean 𝐹 1 at every budget. Top-𝐾 and active sampling perform worst at 5% and 10%, while active sampling outperforms uniform and top-𝐾 sampling only at 20% and 25%. The results highlight the difficulty and importance of acquiring sufficient positive samples under high selectivity to train an accurate proxy, independently of subsequent proxy refinement and routing. 10

Table 3: Best operating points from §6.3, averaged over five seeds. Each configuration uses the lowest-𝑑 point attaining its highest 𝐹 1 ; PROBE uses 𝛼 = 0.9 (quality-first) or 𝛼 = 0.1 (cost-first). Cells with dark green bold and light green indicate the best and second-best 𝐹 1 , and blue bold indicates the lowest latency; ties are broken by the other metrics. Delegation 𝑑 is in percent and latency is in seconds (𝑘 denotes thousands). The bottom rows report geometric means and standard deviations across seeds. Dataset Query

No proxy

LOTUS

BARGAIN

CSV

ScaleDoc

UQE

𝐹 1 ↑ Lat.↓ 𝐹 1 ↑ 𝑑 ↓ Lat.↓ 𝐹 1 ↑ 𝑑 ↓ Lat.↓ 𝐹 1 ↑ 𝑑 ↓ Lat.↓ 𝐹 1 ↑ 𝑑 ↓ Lat.↓ 𝐹 1 ↑ 𝑑 ↓ Lat.↓

PROBE Quality-first

PROBE Cost-first

𝐹 1 ↑ 𝑑 ↓ Lat.↓

𝐹 1 ↑ 𝑑 ↓ Lat.↓

Q2a MMQA Q7

1.000 1.13k 0.750 85.5 1.03k 0.333 10.3 161.2 0.075 10.9 194.6 0.288 24.4 404.2 0.500 25.0 433.0 1.000 13.5 225.9 0.909 6.6 124.9 0.909 4.30k 0.769 82.9 3.76k 0.800 10.1 509.3 0.068 11.5 601.1 0.068 34.7 2.19k 0.040 25.0 1.35k 0.909 15.1 810.6 0.833 11.6 640.4

Q7 Q8 Ecomm Q9 Q13

0.895 6.79k 0.694 29.4 0.889 5.24k 0.782 89.0 0.833 438.1 0.719 93.0 0.818 316.9 0.650 73.0

Q3 Q4 Q8

Cars

2.04k 0.778 50.5 4.68k 0.571 12.1 436.2 0.381 76.5 284.8 0.696 28.0

4.03k 0.588 39.2 3.10k 0.796 78.9 6.30k 0.364 25.0 2.07k 0.827 21.5 2.29k 0.810 13.4 1.42k 1.01k 0.364 15.4 1.35k 0.762 73.0 4.10k 0.034 5.0 573.2 0.869 42.6 3.03k 0.807 19.2 1.40k 358.7 0.617 39.5 174.1 0.574 69.5 358.0 0.308 25.0 143.3 0.737 36.1 178.3 0.737 36.0 177.4 118.7 0.667 42.8 165.5 0.774 91.2 304.4 0.750 25.0 110.3 0.793 23.2 93.9 0.769 14.4 74.5

0.998 711.9 0.982 28.2 249.9 0.949 63.8 574.6 0.987 29.7 267.1 0.993 13.5 116.4 0.996 25.0 216.1 0.997 11.7 127.3 0.996 7.5 87.8 0.542 1.99k 0.023 11.0 254.9 0.427 68.4 1.63k 0.473 71.0 1.88k 0.528 83.9 1.70k 0.452 25.0 582.0 0.540 27.5 586.2 0.540 26.5 569.4 0.294 1.83k 0.096 17.0 490.0 0.170 47.7 895.3 0.248 32.8 932.7 0.274 47.0 1.18k 0.203 25.0 708.6 0.294 18.6 473.2 0.273 12.3 321.2

Animals Q1

0.800

77.6 0.800 78.0

60.8 0.800 18.0

46.0 0.800 43.0

52.8 0.800 54.0

65.9 0.800 20.0

24.1 0.800 12.0

16.2 0.800 11.0

16.0

113 121 202 305

1.000 0.875 1.000 0.762

4.4 0.667 78.0 3.0 0.824 96.0 1.2 1.000 93.0 5.5 0.286 58.0

3.7 0.444 44.7 2.7 0.359 9.1 1.1 0.414 28.5 5.1 0.246 8.9

2.8 0.333 43.9 0.5 0.824 83.8 0.4 0.545 30.3 0.9 0.078 15.9

2.4 0.571 89.3 2.7 0.857 99.1 0.6 0.667 97.0 1.4 0.696 98.0

3.8 0.333 5.0 2.3 0.111 25.0 1.1 0.261 25.0 5.2 0.176 25.0

0.3 1.000 9.8 1.1 1.000 11.3 0.4 1.000 14.0 1.9 0.762 19.9

0.8 0.9 0.4 2.0

1.000 9.8 0.923 9.9 1.000 14.0 0.700 7.4

0.8 0.7 0.4 0.8

0.797 213.9 0.485 54.6 132.0 0.473 25.6 – – 0.088 6.2 11.1 0.010 0.2

77.4 0.354 30.7 2.5 0.087 1.8

88.8 0.530 59.8 145.6 0.262 19.6 6.9 0.066 3.9 10.2 0.042 0.0

58.8 0.790 17.9 4.7 0.051 0.8

59.5 0.760 12.7 4.7 0.012 0.2

43.8 3.3

LRO

Geo. mean Std. dev.

PROBE + Platt PROBE w/o calib. PROBE + GAM PROBE+BARGAIN-A PROBE+BARGAIN-P BARGAIN-A (embed. proxy)

Quality

0.8 0.6 0.4

30

100

Geometric-mean latency (s) Figure 11: Quality (𝐹 1 ) versus latency as 𝛼 or the BARGAIN target (0.1–0.9) varies.

SigLIP CLIP Qwen Jina 0

Bi

and no calibration, where routing uses uncalibrated refined scores. At the default 𝛼 = 0.5, Platt calibration improves geometric-mean 𝐹 1 from 0.691 to 0.762 at a geometric-mean latency of 43.9 s, while reducing expected calibration error (ECE) from 0.213 to 0.057. GAM reaches an 𝐹 1 of 0.744 at the same 𝛼 and remains below Platt calibration at all higher tested values of 𝛼. These improvements in both calibration error and output 𝐹 1 highlight the importance of reliable match probabilities for cost-aware routing. Without routing (𝛼 = 0), PROBE achieves 0.672 at 27.5 s. Further increasing 𝛼 yields diminishing returns: compared with 𝛼 = 0.5, 𝛼 = 0.9 improves 𝐹 1 by about 5% but increases latency by 2.6×. To compare PROBE’s calibrated routing with BARGAIN, we replace PROBE’s calibration and routing with BARGAIN [51], while keeping the same refined scores. We denote its accuracy and precision modes by PROBE+BARGAIN-A and PROBE+BARGAIN-P, respectively. PROBE+BARGAIN-A achieves a geometric-mean 𝐹 1 of 0.56–0.63, outperforming BARGAIN-A with an embedding proxy in both quality and latency across all tested targets. However, accuracy-based routing remains ineffective under high selectivity: the dominant negative class allows BARGAIN’s accuracy mode to meet its target despite missing positives. Its precision mode does not obtain a certified threshold in these runs and relies heavily on LLM evaluation, limiting cost savings. In contrast, PROBE directly optimizes estimated 𝐹 1 against LLM cost and achieves a better empirical quality–latency tradeoff than these BARGAIN variants.

Cross 0.73 0.72 0.76 0.74 0.5 1 Quality

Figure 12: Geometric-mean quality across different embedding models.

6.5

Ablation on Graph Refinement Stage

6.6

Ablation on Learned Calibrated Cascade Routing

We fix the labeled set acquired by PROBE’s SAS and incrementally enable the two graph refinement stages, bias diffusion and homogeneity propagation (§4), using the unrefined logistic-regression proxy as the baseline. As Figure 10(b) shows, graph refinement improves geometric-mean 𝐹 1 from 0.47–0.53 to 0.60–0.79 across sampling budgets, with a gain of 1.3–1.5×. Bias diffusion accounts for most of the improvement, while homogeneity propagation adds at most 0.07. The larger contribution of bias diffusion is consistent with the local error correlation assumption in §4.1.

6.7

Figure 11 compares three PROBE variants with the same sampling, graph refinement, and routing algorithm, but different calibration methods: Platt calibration (the default), the GAM calibrator [32],

Sensitivity to Model Choice

Representation model. PROBE uses one pretrained model to rank candidates for sampling (§3) and to embed them for proxy training and graph construction (§4). We compare two bi-encoders, 11

No proxy

PROBE

0.5 0.0

3.8 a 4 .6V -VL n3 wen emm M-4 Q G GL

e Qw

Geometric-mean speedup

Geometric-mean quality

1.0

4.6× 4.9× 4

3.2×

Table 4: 𝐹 1 and delegation rate 𝑑 on less selective queries (𝜋: positive rate). Baselines use target 0.9, PROBE 𝛼 = 0.5. 3.7×

Cars Q7

2

System

0

(b) Speedup

Embedding Sampling

LLM calling Graph refinement

Proxy train Proxy predict

𝑑

𝐹1

𝑑

100% 0.620 40.2% 0.516 41.7% 0.463

100% 0.768 13.5% 0.723 11.7% 0.746

100% 78.0% 86.9%

PROBE, 𝐵/𝑁 = 10% 0.627 PROBE, 𝐵/𝑁 = 25% 0.667

35.2% 0.435 44.2% 0.620

11.1% 0.650 30.2% 0.710

13.6% 29.4%

6.9

Calibration

7

Figure 14: Normalized end-to-end runtime breakdown of PROBE by query. LLM calling covers the expert calls during sampling and cascade routing.

𝐹1

𝑑

Case Study: Less Selective Queries

RELATED WORK

AI query systems. Prior semantic query systems such as LOTUS [38], Palimpzest [33], Abacus [44], DocETL [46] and Stretto [45] expose LLM operators and optimize them through model selection, cascades, indexes, or plan-level search. PROBE instead spends the LLM budget within a single operator.

SigLIP [53] and CLIP-base [43], which embed the predicate and each candidate independently, with two multimodal cross-encoders, Qwen3-VL-Reranker-2B [30] and jina-reranker-m0 [22], which jointly encode the predicate and the candidate. As Figure 12 shows, Qwen3-VL-Reranker-2B attains the highest geometric-mean quality, 0.762, against 0.74 for jina-reranker-m0, 0.73 for SigLIP and 0.72 for CLIP-base. PROBE’s quality varies by at most 0.04 across representation models.

Approximate query processing for AI query systems. SUPG [27] samples proxy scores to return an approximate selection meeting a user-specified precision or recall target. ThalamusDB [24] calibrates similarity thresholds from a small sample set with deterministic error bounds. Other systems use cluster-level voting or decomposition-based pruning [17, 52] and stratified allocation to estimate semantic-join aggregates [57]. All of them expose a userdefined target, whereas GAMCAL [32] exposes a single cost–quality parameter.

Expert LLM. Figure 13 replaces the expert LLM with four open multimodal models: Qwen3-VL-30B-A3B-Instruct [3], Qwen3.827B [41], Gemma 4 26B-A4B [14], and GLM-4.6V-Flash [50]. For each model, PROBE uses 𝐵/𝑁 = 10% and 𝛼 = 0.5 and is compared with the no-proxy baseline on the same model. Across the four models, PROBE’s geometric-mean quality stays within 0.04 of the no-proxy baseline, and it attains a geometric-mean speedup of 3.2–4.9×.

6.8

𝐹1

Table 4 evaluates three less selective queries outside the main evaluation, with positive rates from 0.147 to 0.497. Increasing the sampling budget from 10% to 25% raises PROBE’s 𝐹 1 from 0.627 to 0.667 on Cars Q7, from 0.435 to 0.620 on Ecomm Q6, and from 0.650 to 0.710 on Movie Q5. At the larger budget, delegation rates range from 29.4% to 44.2%. For the less selective queries in our case study, a larger sampling budget is needed to bring PROBE closer to the quality of full LLM evaluation. This is due to the weaker separation between positive and negative rows in the representation space, which would limit the effectiveness of graph-based refinement and increase the need for LLM supervision.

MM Q MM A Q2 Ec QA a o Q Ec mm 7 o Q Ec mm 7 Ec omm Q8 om Q m 9 Ca Q13 r Ca s Q3 rs An Cars Q4 im Q a 8 LR ls Q1 O LR 113 O LR 121 O LR 202 O3 05

% of PROBE time

Figure 13: (a) Geometric-mean quality of the same-model noproxy baseline and of PROBE. (b) Geometric-mean speedup of PROBE over the same-model no-proxy baseline.

100 75 50 25 0

Movie Q5

0.669 0.643 0.612

No proxy BARGAIN-A ScaleDoc

8 a 4 4.6V -VL n3. en3 Qwe Gemm LMw G Q

(a) Quality

Ecomm Q6

𝑁 =30,130, 𝜋 =0.147 𝑁 =9,280, 𝜋 =0.200 𝑁 =65,024, 𝜋=0.497

Learned routing and deferral. Model cascades and learned deferral decide whether an input is handled by a cheap proxy or escalated to an expert model [7, 12, 23, 35, 37, 42]. Prior LLM-routing work commonly treats each model request as the routing unit [19], whereas a database query may apply a semantic operator to many rows. AIQA [8] makes the routing decision for the entire database query. PROBE decides per row and routes only likely-wrong rows.

Time Breakdown

8

As Figure 14 shows, LLM calling takes 72.1% of PROBE’s end-to-end time and embedding all rows 16.7%. Sampling (6.6%), calibration (2.3%), graph refinement with 𝑘-NN construction (1.7%), and proxy training and prediction (0.6%) add modest overhead. LLM calls remain the dominant cost, and embedding cost grows with the number of candidate pairs for large joins, and optimization such as blocking that prunes pairs before embedding is left to future work.

CONCLUSION

PROBE reduces LLM evaluations for highly selective semantic queries by combining selectivity-adaptive sampling, graph-based proxy refinement, and calibrated routing. On the evaluated queries, the default 10% sampling budget yields a geometric-mean 𝐹 1 of 0.762, compared with 0.797 for full LLM evaluation, while delegating 12.8% of rows and achieving a 4.87× geometric-mean speedup. 12

REFERENCES

2, 3 (2024), 1–26. [25] Daniel Kang, Peter Bailis, and Matei Zaharia. 2019. BlazeIt: optimizing declarative aggregation and limit queries for neural network-based video analytics. Proceedings of the VLDB Endowment 13, 4 (2019), 533–546. [26] Daniel Kang, John Emmons, Firas Abuzaid, Peter Bailis, and Matei Zaharia. 2017. NoScope: Optimizing Neural Network Queries over Video at Scale. Proceedings of the VLDB Endowment 10, 11 (2017). [27] Daniel Kang, Edward Gan, Peter Bailis, Tatsunori Hashimoto, and Matei Zaharia. 2020. Approximate selection with guarantees using proxies. Proc. VLDB Endow. 13, 12 (July 2020), 1990–2003. https://doi.org/10.14778/3407790.3407804 [28] Gary King and Langche Zeng. 2001. Logistic Regression in Rare Events Data. Political Analysis 9, 2 (2001), 137–163. [29] Jiale Lao, Andreas Zimmerer, Olga Ovcharenko, Tianji Cong, Matthew Russo, Gerardo Vitagliano, Michael Cochez, Fatma Özcan, Gautam Gupta, Thibaud Hottelier, H. V. Jagadish, Kris Kissel, Sebastian Schelter, Andreas Kipf, and Immanuel Trummer. 2026. SemBench: A benchmark for semantic query processing engines. Proceedings of the VLDB Endowment 19, 8 (2026), 1754–1767. [30] Mingxin Li, Yanzhao Zhang, Dingkun Long, Keqin Chen, Sibo Song, Shuai Bai, Zhibo Yang, Pengjun Xie, An Yang, Dayiheng Liu, Jingren Zhou, and Junyang Lin. 2026. Qwen3-VL-Embedding and Qwen3-VL-Reranker: A unified framework for state-of-the-art multimodal retrieval and ranking. arXiv preprint arXiv:2601.04720 (2026). [31] Paweł Liskowski, Benjamin Han, Paritosh Aggarwal, Bowei Chen, Boxin Jiang, Nitish Jindal, Zihan Li, Aaron Lin, Kyle Schmaus, Jay Tayade, et al. 2026. Cortex aisql: A production sql engine for unstructured data. In Companion of the International Conference on Management of Data. 400–412. [32] Paweł Liskowski and Kyle Schmaus. 2026. Streaming Model Cascades for Semantic SQL. arXiv preprint arXiv:2604.00660 (2026). [33] Chunwei Liu, Matthew Russo, Michael Cafarella, Lei Cao, Peter Baile Chen, Zui Chen, Michael Franklin, Tim Kraska, Samuel Madden, Rana Shahout, et al. 2025. Palimpzest: Optimizing ai-powered analytics with declarative query processing. In Proceedings of the Conference on Innovative Database Research (CIDR). 2. [34] Charles F. Manski and Steven R. Lerman. 1977. The Estimation of Choice Probabilities from Choice Based Samples. Econometrica 45, 8 (1977), 1977–1988. [35] Harikrishna Narasimhan, Wittawat Jitkrittum, Aditya K Menon, Ankit Rawat, and Sanjiv Kumar. 2022. Post-hoc estimators for learning to defer to an expert. Advances in Neural Information Processing Systems 35 (2022), 29292–29304. [36] Jerzy Neyman. 1992. On the two different aspects of the representative method: the method of stratified sampling and the method of purposive selection. In Breakthroughs in statistics: Methodology and distribution. Springer, 123–150. [37] Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E Gonzalez, Mohammed Kadous, and Ion Stoica. 2025. Routellm: Learning to route llms from preference data. In International Conference on Learning Representations, Vol. 2025. 34433–34448. [38] Liana Patel, Siddharth Jha, Melissa Pan, Harshit Gupta, Parth Asawa, Carlos Guestrin, and Matei Zaharia. 2025. Semantic operators and their optimization: Enabling llm-based data processing with accuracy guarantees in lotus. Proceedings of the VLDB Endowment 18, 11 (2025), 4171–4184. [39] John C. Platt. 1999. Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods. In Advances in Large Margin Classifiers, Alexander J. Smola, Peter Bartlett, Bernhard Schölkopf, and Dale Schuurmans (Eds.). MIT Press, Cambridge, MA, 61–74. [40] Ross L. Prentice and Ronald Pyke. 1979. Logistic Disease Incidence Models and Case-Control Studies. Biometrika 66, 3 (1979), 403–411. [41] Qwen Team. 2026. Qwen3.8-27B. https://huggingface.co/Qwen/Qwen3.8-27BFP8. Hugging Face model card, Alibaba Group. [42] Stephan Rabanser, Nathalie Rauschmayr, Achin Kulshrestha, Petra Poklukar, Wittawat Jitkrittum, Sean Augenstein, Congchao Wang, and Federico Tombari. 2026. Gatekeeper: Improving model cascades through confidence tuning. Advances in Neural Information Processing Systems 38 (2026), 19518–19547. [43] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. 2021. Learning transferable visual models from natural language supervision. In International conference on machine learning. PmLR, 8748–8763. [44] Matthew Russo, Chunwei Liu, Sivaprasad Sudhir, Gerardo Vitagliano, Michael Cafarella, Tim Kraska, and Samuel Madden. 2025. Abacus: A cost-based optimizer for semantic operator systems. arXiv preprint arXiv:2505.14661 (2025). [45] Gabriele Sanmartino, Matthias Urban, Paolo Papotti, and Carsten Binnig. 2026. The Stretto Execution Engine for LLM-Augmented Data Systems. arXiv preprint arXiv:2602.04430 (2026). [46] Shreya Shankar, Tristan Chambers, Tarak Shah, Aditya G Parameswaran, and Eugene Wu. 2025. DocETL: Agentic Query Rewriting and Evaluation for Complex Document Processing. Proceedings of the VLDB Endowment 18, 9 (2025), 3035– 3048. [47] Yunxiang Su, Tianjing Zeng, Zhongjun Ding, Yin Lin, Rong Zhu, Zhewei Wei, Bolin Ding, and Jingren Zhou. 2026. Large Language Model-Enhanced Relational Operators: Taxonomy, Benchmark, and Analysis. arXiv preprint arXiv:2603.02537 (2026).

[1] Michael R. Anderson, Michael Cafarella, German Ros, and Thomas F. Wenisch. 2019. Physical Representation-Based Predicate Optimization for a Visual Analytics Database. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 1466–1477. [2] Simran Arora, Brandon Yang, Sabri Eyuboglu, Avanika Narayan, Andrew Hojel, Immanuel Trummer, and Christopher Ré. 2024. Language Models Enable Simple Systems for Generating Structured Views of Heterogeneous Data Lakes. Proceedings of the VLDB Endowment 17, 2 (2024), 92–105. [3] Shuai Bai, Yuxuan Cai, Ruizhe Chen, Keqin Chen, Xionghui Chen, Zesen Cheng, Lianghao Deng, Wei Ding, Chang Gao, Chunjiang Ge, et al. 2025. Qwen3-vl technical report. arXiv preprint arXiv:2511.21631 (2025). [4] Richard Bellman. 1961. On the Approximation of Curves by Line Segments Using Dynamic Programming. Commun. ACM 4, 6 (1961), 284. [5] David A. Binder. 1983. On the Variances of Asymptotically Normal Estimators from Complex Surveys. International Statistical Review 51, 3 (1983), 279–292. [6] Jeff Calder, Brendan Cook, Matthew Thorpe, and Dejan Slepcev. 2020. Poisson learning: Graph based semi-supervised learning at very low label rates. In International conference on machine learning. PMLR, 1306–1316. [7] Lingjiao Chen, Matei Zaharia, and James Zou. 2023. Frugalgpt: How to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.05176 (2023). [8] Yeounoh Chung, Rushabh Desai, Jian He, Yu Xiao, Thibaud Hottelier, YvesLaurent Kom Samo, Pushkar Khadilkar, Xianshun Chen, Sam Idicula, Fatma Ozcan, et al. 2026. 100x Cost & Latency Reduction: Performance Analysis of AI Query Approximation using Lightweight Proxy Models:[Experiments & Analysis]. Proceedings of the ACM on Management of Data 4, 3 (SIGMOD (2026), 1–23. [9] C. J. Clopper and E. S. Pearson. 1934. The Use of Confidence or Fiducial Limits Illustrated in the Case of the Binomial. Biometrika 26, 4 (1934), 404–413. [10] Hanjun Dai, Bethany Y Wang, Xingchen Wan, Bo Dai, Sherry Yang, Azade Nova, Pengcheng Yin, Phitchaya M Phothilimthana, Charles Sutton, and Dale Schuurmans. 2024. Uqe: A query engine for unstructured databases. Advances in Neural Information Processing Systems 37 (2024), 29807–29838. https://arxiv. org/abs/2407.09522v2 [11] Databricks. 2025. AI Functions on Databricks. https://docs.databricks.com/aws/ en/large-language-models/ai-functions. [12] Dujian Ding, Ankur Mallick, Chi Wang, Robert Sim, Subhabrata Mukherjee, Victor Rühle, Laks Lakshmanan, and Ahmed H Awadallah. 2024. Hybrid llm: Cost-efficient and quality-aware query routing. In International Conference on Learning Representations, Vol. 2024. 41348–41366. [13] Werner Dinkelbach. 1967. On Nonlinear Fractional Programming. Management Science 13, 7 (1967), 492–498. [14] Gemma Team. 2026. Gemma 4 Technical Report. arXiv preprint arXiv:2607.02770 (2026). [15] Google Cloud. 2025. SQL Reimagined for the AI Era with BigQuery AI Functions. https://cloud.google.com/blog/products/data-analytics/sql-reimaginedfor-the-ai-era-with-bigquery-ai-functions. [16] Daniel G. Horvitz and Donovan J. Thompson. 1952. A Generalization of Sampling Without Replacement from a Finite Universe. J. Amer. Statist. Assoc. 47, 260 (1952), 663–685. [17] Nan Hou, Kangfei Zhao, Jiadong Xie, and Jeffrey Xu Yu. 2026. Beyond Linear LLM Invocation: An Efficient and Effective Semantic Filter Paradigm. arXiv preprint arXiv:2603.04799 (2026). [18] Kevin Hsieh, Ganesh Ananthanarayanan, Peter Bodik, Shivaram Venkataraman, Paramvir Bahl, Matthai Philipose, Phillip B. Gibbons, and Onur Mutlu. 2018. Focus: Querying Large Video Datasets with Low Latency and Low Cost. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 269–286. [19] Keke Huang, Yimin Shi, Dujian Ding, Yifei Li, Yang Fei, Laks Lakshmanan, and Xiaokui Xiao. 2025. Thriftllm: On cost-effective selection of large language models for classification queries. arXiv preprint arXiv:2501.04901 (2025). [20] Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R Benson. 2020. Combining label propagation and simple models out-performs graph neural networks. arXiv preprint arXiv:2010.13993 (2020). [21] Brad Jackson, Jeffrey D. Scargle, David Barnes, Sundararajan Arabhi, Alina Alt, Peter Gioumousis, Elyus Gwin, Paungkaew Sangtrakulcharoen, Linda Tan, and Tun Tao Tsai. 2005. An Algorithm for Optimal Partitioning of Data on an Interval. IEEE Signal Processing Letters 12, 2 (2005), 105–108. [22] Jina AI. 2025. jina-reranker-m0: Multilingual Multimodal Document Reranker. https://huggingface.co/jinaai/jina-reranker-m0. [23] Wittawat Jitkrittum, Neha Gupta, Aditya K Menon, Harikrishna Narasimhan, Ankit Rawat, and Sanjiv Kumar. 2023. When does confidence-based cascade deferral suffice? Advances in Neural Information Processing Systems 36 (2023), 9891–9906. [24] Saehan Jo and Immanuel Trummer. 2024. Thalamusdb: Approximate query processing on multi-modal data. Proceedings of the ACM on Management of Data 13

[48] Zhu Xiaojin. 2008. Semi-supervised learning literature survey. Computer Sciences TR 1530 (2008), 60–60. [49] Zhu Xiaojin, Zoubin Ghahramani, and John D Lafferty. 2003. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03). 912–919. [50] Z.ai. 2025. GLM-4.6V-Flash. https://huggingface.co/zai-org/GLM-4.6V-Flash. Hugging Face model card. [51] Sepanta Zeighami, Shreya Shankar, and Aditya Parameswaran. 2025. Cut Costs, Not Accuracy: LLM-Powered Data Processing with Guarantees. Proceedings of the ACM on Management of Data 3, 6 (2025), 1–26. https://arxiv.org/abs/2509.02896v2 [52] Sepanta Zeighami, Shreya Shankar, and Aditya Parameswaran. 2026. FeaturizedDecomposition Join: Low-Cost Semantic Joins with Guarantees. Proc. VLDB Endow. 19, 11 (Sept. 2026), 3048–3061. https://doi.org/10.14778/3836663.3836672 [53] Xiaohua Zhai, Basil Mustafa, Alexander Kolesnikov, and Lucas Beyer. 2023. Sigmoid Loss for Language Image Pre-Training. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV). 11975–11986. [54] Hengrui Zhang, Yulong Hui, Yihao Liu, and Huanchen Zhang. 2026. ScaleDoc: Scaling LLM-based Predicates over Large Document Collections. Proceedings of the ACM on Management of Data 4, 3 (SIGMOD) (2026), 1–26. [55] Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. 2003. Learning with local and global consistency. Advances in neural information processing systems 16 (2003). [56] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems 33 (2020), 7793–7804. [57] Yuxuan Zhu, Tengjun Jin, Chenghao Mo, and Daniel Kang. 2026. Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees. Proceedings of the ACM on Management of Data 4, 3 (SIGMOD (2026), 1–28.

14

Related documents

• SemReuse: Certified Reuse of Cached Natural-Language Views for Semantic Operators#1327625
• SemReuse: Certified Reuse of Cached Natural-Language Views for Semantic Operators#1319128
• Natural Language Knowledge Graph Query Execution: Leveraging Controlled Semantics in the LLM Context Window#1084587
• Natural Language Knowledge Graph Query Execution: Leveraging Controlled Semantics in the LLM Context Window#919517
• TACO: A Benchmark for Open-Domain Text-to-SQL with Ambiguous and Cross-Database Queries#271943