Streaming Model Cascades for Semantic SQL Paweł Liskowski
Kyle Schmaus
Snowflake Inc.
Snowflake Inc.
Poznań, Poland
San Francisco, CA, USA partition rows into regions that can be accepted, rejected, or delegated to the oracle. Cascades have demonstrated substantial cost reductions across LLM workloads (up to 98% in API-based settings [2] and up to 90% in streaming inference [19]) and are recognized as a key optimization in semantic query processing systems [15, 21].
arXiv:2604.00660v1 [cs.DB] 1 Apr 2026
Abstract Modern data warehouses extend SQL with semantic operators that invoke large language models on each qualifying row, but the perrow inference cost is prohibitive at scale. Model cascades reduce this cost by routing most rows through a fast proxy model and delegating uncertain cases to an expensive oracle. Existing frameworks, however, require global dataset access and optimize a single quality metric, limiting their applicability in distributed systems where data is partitioned across independent workers. We present two adaptive cascade algorithms designed for streaming, per-partition execution in which each worker processes its partition independently without inter-worker communication. SUPG-IT extends the SUPG statistical framework to streaming execution with iterative threshold refinement and joint precision-recall guarantees. GAMCAL replaces user-specified quality targets with a learned calibration model: a Generalized Additive Model maps proxy scores to calibrated probabilities with uncertainty quantification, enabling direct optimization of a cost-quality tradeoff through a single parameter. Experiments on six datasets in a production semantic SQL engine show that both algorithms achieve 𝐹 1 > 0.95 on every dataset. GAMCAL achieves higher 𝐹 1 per oracle call at cost-sensitive operating points, while SUPG-IT reaches a higher quality ceiling with formal guarantees on precision and recall.
1
SUPG [13] provides a statistical framework for approximate selection with guarantees, using importance-weighted oracle sampling to estimate a proxy score threshold that meets user-specified recall or precision targets with high probability. However, deploying SUPG in production database systems reveals fundamental limitations along two axes. The first is architectural: SUPG assumes access to the entire dataset for computing normalized importance sampling weights, requiring a global pass over all proxy scores before any sampling can begin. In distributed database environments where data is processed in partitions by parallel workers, such global synchronization is impractical. Furthermore, SUPG estimates thresholds in a single pass with no mechanism to refine them as oracle labels accumulate across batches. Production semantic SQL engines require algorithms that operate in online, streaming mode, updating their estimates incrementally. The second axis is methodological. SUPG optimizes for a single metric (either recall or precision) but not both simultaneously. An AI_FILTER that achieves 95% recall but only 30% precision wastes downstream compute on false positives. The algorithm further assumes that proxy scores are well-calibrated, approximating the true probability 𝑃 (positive | 𝑥). In practice, proxy models are often poorly calibrated [7], leading to biased threshold estimates. Finally, users must specify fixed precision/recall targets that are often arbitrary, since different datasets have different inherent difficulty and users may not know a priori what targets are achievable for their workload.
Introduction
Modern data warehouses increasingly integrate large language models (LLMs) directly into SQL through semantic operators such as AI_FILTER, AI_CLASSIFY, and AI_JOIN [14, 21]. These operators enable users to write declarative queries that blend relational operations with semantic reasoning: filtering customer reviews by sentiment, classifying documents into categories, or joining tables based on semantic similarity. However, each semantic operator invokes an LLM on every qualifying row: a single AI_FILTER applied to a million-row table may trigger hundreds of thousands of LLM calls, incurring costs that are orders of magnitude higher than traditional SQL operations and latencies measured in hours rather than seconds [14].
We present two algorithms that address these architectural and methodological limitations, respectively: (1) SUPG with Iterative Targeting (SUPG-IT) extends SUPG to the streaming setting, refining two thresholds iteratively as oracle samples accumulate across batches while jointly targeting both precision and recall. The algorithm clips corrected targets to prevent over-delegation and collapses to a balanced threshold when precision-recall constraints conflict. Each worker processes its partition independently without inter-worker communication.
Model cascades address this challenge by routing most rows through a fast, inexpensive proxy model (e.g., a small LLM or embeddingbased classifier) while escalating only uncertain cases to a powerful but expensive oracle model (e.g., a large LLM). The proxy model produces a confidence score for each row, and learned thresholds
(2) GAM-Calibrated Cascade (GAMCAL) addresses the methodological limitations that SUPG-IT inherits from the SUPG framework: reliance on proxy calibration and the need for users to specify fixed accuracy targets. GAMCAL learns a calibration
, . 1
,,
Liskowski et al.
function mapping raw proxy scores to true probabilities using Generalized Additive Models (GAMs), then directly optimizes a cost-quality tradeoff controlled by a single parameter: min
𝜏low ,𝜏high
𝛼 · error(𝜏low, 𝜏high ) + (1 − 𝛼) · cost(𝜏low, 𝜏high )
(enabling streaming execution) and that only a single metric is targeted (enabling joint precision-recall guarantees). GAMCAL further departs from the SUPG framework by replacing statistical threshold estimation with learned probability calibration.
(1)
LLM cascades. Routing queries through progressively more capable models has been explored extensively. FrugalGPT [2] learns a scoring function that predicts answer reliability and cascades queries through increasingly expensive API endpoints. Nie et al. [19] formalize cascade learning as online imitation learning where smaller models learn from LLM demonstrations in a streaming setting. Jitkrittum et al. [11] characterize when confidence-based deferral is optimal and identify failure modes involving specialist models and label noise. Wang et al. [29] modify the small model’s training loss to focus on tokens that at least one cascade model predicts correctly. Zellinger and Thomson [34] model the joint distribution of calibrated confidences across a sequence of LLMs using Markov copulas, enabling continuous threshold optimization.
where 𝜏low and 𝜏high are the delegation thresholds and 𝛼 ∈ [0, 1] is a weighting parameter. When 𝛼 is high, the cascade prioritizes classification quality; when low, it minimizes oracle calls. The formulation adapts automatically to dataset difficulty, eliminating arbitrary target specification. The two algorithms serve complementary roles, each addressing needs the other cannot: SUPG-IT is appropriate when users have explicit quality targets and want probabilistic guarantees, while GAMCAL is appropriate when users prefer the system to automatically balance quality against cost without specifying any targets. Both algorithms are designed for and evaluated in the context of Snowflake’s Cortex AISQL, a production SQL engine that processes semantic operators over millions of rows [14]. On six benchmarks, both algorithms exceed 𝐹 1 = 0.95 on every dataset. GAMCAL outperforms the SUPG cascade in LOTUS [21] at cost-sensitive operating points, leading on all six datasets under a 20% delegation budget and requiring up to 58% fewer oracle calls to reach 𝐹 1 ≥ 0.95. SUPG-IT reaches the highest quality ceiling, with a mean peak 𝐹 1 of 0.989.
Our setting differs from these methods in two respects. First, we operate on binary predicates embedded in SQL, where the proxy produces a continuous confidence score rather than a discrete prediction or generated text. Second, our algorithms must run in a streaming, per-partition execution model imposed by distributed database architectures, whereas most LLM cascade work assumes batch access to a validation set or centralized routing.
In summary, our contributions are:
Probability calibration. Mapping model outputs to well-calibrated probabilities is a long-standing problem. Platt scaling [22] fits a logistic function to raw scores, temperature scaling [7] adjusts a single parameter, and isotonic regression [32] fits a non-parametric monotone map. Guo et al. [7] demonstrated that modern neural networks are often poorly calibrated despite high accuracy. Generalized Additive Models [8] offer a flexible middle ground through penalized spline fitting. Calibration has also been applied within cascade frameworks: Zellinger and Thomson [33] combine a nonlinear log-transform with Platt scaling to improve routing decisions in LLM cascades with abstention. GAMCAL uses calibration for a different purpose: it trains a GAM on oracle samples to predict expected quality metrics for any threshold pair in closed form, enabling direct threshold optimization without additional oracle queries.
• A formalization of the model cascade problem for streaming semantic SQL with independent parallel workers, introducing two complementary problem formulations (Section 3). • SUPG-IT, the first cascade algorithm that provides joint precisionrecall guarantees in online, streaming execution (Section 4). • GAMCAL, a calibration-based cascade that replaces user-specified targets with learned cost-quality optimization, using GAMs for probability calibration with uncertainty quantification (Section 5). The remainder of this paper is organized as follows. Section 2 reviews related work on approximate selection, model cascades, and probability calibration. Section 3 formalizes the cascade routing problem. Sections 4 and 5 present our two algorithms in detail. Section 6 evaluates both algorithms on six real-world benchmarks. Section 7 concludes with limitations and future directions.
2
Semantic query processing. Several systems embed LLM-powered operators into SQL and dataframe APIs for processing unstructured data at scale [14, 15, 21]. LOTUS [21] includes cascade support based on single-pass SUPG. Cortex AISQL [14] processes semantic predicates over millions of rows in a distributed streaming model. An alternative line of work bypasses cascading entirely by training lightweight proxy models to replace LLM invocations: UQE [6] uses embedding-based classifiers for semantic filters, and Chung et al. [3] demonstrate order-of-magnitude cost reductions through full proxy replacement in BigQuery and AlloyDB. These approaches provide no statistical guarantees on precision or recall, relying instead on heuristic quality thresholds for fallback. Our cascades occupy a middle ground: they route individual records between proxy and oracle models with statistical quality guarantees (SUPG-IT) or learned cost-quality optimization (GAMCAL), accepting higher
Related Work
Approximate selection with proxy models. Kang et al. [13] introduced SUPG, a framework for approximate data selection that uses importance-weighted oracle sampling to find a proxy score threshold meeting a user-specified recall or precision target with high probability. Earlier systems such as NoScope [12] and probabilistic predicates [16] filtered data using proxy models but provided no statistical guarantees on result quality. SUPG addressed this gap through confidence bounds and variance-optimal importance sampling with weights proportional to the square root of proxy scores. Our work builds on SUPG while removing two assumptions: that the entire dataset is available before sampling begins 2
Streaming Model Cascades for Semantic SQL
,,
per-predicate cost than full replacement in exchange for controlled accuracy.
3
3.3
Problem Formulation
We formalize the model cascade problem for binary semantic predicates, establishing a two-threshold decision framework, two complementary optimization objectives, and the streaming execution model required for deployment in distributed database systems.
3.1
Quality Metrics
The cascade’s three-region structure determines how classification errors arise. Accepted records receive 𝑦ˆ𝑖 = 1 without oracle verification; those with 𝑦𝑖 = 0 are false positives. Rejected records receive 𝑦ˆ𝑖 = 0; those with 𝑦𝑖 = 1 are false negatives. Delegated records receive 𝑦ˆ𝑖 = 𝑦𝑖 from the oracle and contribute no errors. Errors thus originate exclusively from the accept and reject regions. Precision depends on 𝜏high : raising it reduces false positives but delegates more records to the oracle. Recall is governed by 𝜏low : lowering it reduces false negatives at the cost of higher delegation. We quantify quality using:
Setting and Notation
Consider a dataset D = {𝑥 1, 𝑥 2, . . . , 𝑥𝑛 } of 𝑛 records to be processed by a binary semantic predicate (e.g., AI_FILTER). We have access to two models:
TP , TP + FP
TP TP + FN Precision · Recall 𝐹 𝛽 = (1 + 𝛽 2 ) · 2 𝛽 · Precision + Recall
Precision =
• Oracle model 𝑂 : D → {0, 1}: An expensive but accurate model (e.g., a large LLM) that produces a binary label 𝑦𝑖 = 𝑂 (𝑥𝑖 ) for each record, at per-invocation cost 𝑐𝑂 .
Recall =
(3) (4)
where 𝐹 𝛽 balances precision and recall (𝛽 > 1 favors recall; 𝛽 = 1 yields the standard 𝐹 1 score). The cascade problem is thus a threeway tradeoff among precision, recall, and oracle cost.
• Proxy model 𝐴 : D → [0, 1]: A fast, inexpensive model that returns a confidence score 𝐴(𝑥𝑖 ) ∈ [0, 1] estimating the probability that 𝑦𝑖 = 1, at per-invocation cost 𝑐 𝐴 ≪ 𝑐𝑂 .
3.4
Problem Formulations
Following standard practice in the cascade literature [13], we treat oracle labels as ground truth and measure all quality metrics with respect to {𝑦𝑖 }. The assumption is reasonable when the oracle is substantially more accurate than the proxy, as is typically the case for large versus small language models on semantic predicates [14]. Our goal is to produce predictions 𝑦ˆ𝑖 for all records while minimizing oracle invocations. Since 𝑐 𝐴 ≪ 𝑐𝑂 , we assume the proxy is executed on all records, yielding scores {𝐴(𝑥𝑖 )}𝑛𝑖=1 .
We consider two complementary problem formulations, each addressed by one of our algorithms.
3.2
while minimizing the delegation rate. The two constraints are coupled: improving recall requires lowering 𝜏low while improving precision requires raising 𝜏high , and both adjustments widen the uncertain region. Satisfying both constraints simultaneously is harder than optimizing either in isolation, particularly when the proxy score distributions of positive and negative records overlap.
3.4.1 Target-Based Formulation (SUPG-IT). Users specify minimum precision and recall targets 𝑡𝑃 and 𝑡𝑅 along with a failure probability 𝛿. The goal is to find thresholds (𝜏low, 𝜏high ) such that, over the randomness of oracle sampling: Pr[Precision ≥ 𝑡𝑃 ] ≥ 1 − 𝛿 Pr[Recall ≥ 𝑡𝑅 ] ≥ 1 − 𝛿
Two-Threshold Decision Framework
Our cascade algorithms partition records into three regions using two thresholds 𝜏low and 𝜏high where 0 ≤ 𝜏low ≤ 𝜏high ≤ 1: (1) Reject region (𝐴(𝑥) < 𝜏low ): The proxy is confident the record does not satisfy the predicate. Predict 𝑦ˆ = 0 without oracle evaluation.
(6)
3.4.2 Cost-Quality Tradeoff Formulation (GAMCAL). Rather than specifying fixed targets, users provide a tradeoff parameter 𝛼 ∈ [0, 1] controlling the balance between classification quality and oracle cost. The objective is:
(2) Accept region (𝐴(𝑥) ≥ 𝜏high ): The proxy is confident the record satisfies the predicate. Predict 𝑦ˆ = 1 without oracle evaluation. (3) Uncertain region (𝜏low ≤ 𝐴(𝑥) < 𝜏high ): The proxy lacks confidence. Invoke the oracle to obtain 𝑦ˆ = 𝑂 (𝑥).
min
𝜏low ,𝜏high
The delegation rate 𝑑 is the fraction of records routed to the oracle: |{𝑥𝑖 : 𝜏low ≤ 𝐴(𝑥𝑖 ) < 𝜏high }| 𝑑= 𝑛
(5)
𝛼 · error(𝜏low, 𝜏high ) + (1 − 𝛼) · cost(𝜏low, 𝜏high )
(7)
where error captures classification quality (derived from 1 − 𝐹 𝛽 , normalized for comparability as detailed in Section 5.4) and cost is the delegation rate. The formulation adapts to dataset difficulty: easy datasets achieve low error with low cost, while difficult datasets require higher delegation rates.
(2)
We state the framework in terms of the raw proxy score 𝐴(𝑥) for concreteness. More generally, the thresholds may operate on any monotone transformation of the proxy output. GAMCAL (Section 5) replaces 𝐴(𝑥) with a calibrated decision score that incorporates learned probability estimates (Section 5.2), but the threeregion structure, quality metrics, and delegation rate carry over unchanged.
3.5
Streaming Execution Model
Unlike batch algorithms that access the entire dataset simultaneously, our algorithms operate in a streaming setting motivated by distributed database execution (Figure 1). Data is partitioned across 𝑊 parallel workers, worker 𝑤 processing its partition as a sequence 3
,,
Liskowski et al. (1)
(1)
(2)
(2)
(3)
𝐵1 , 𝐵2 , . . .
𝐵1 , 𝐵2 , . . .
Worker 𝑊1
Worker 𝑊2
Worker 𝑊3
local state (1)
local state (2)
Algorithm 1 SUPG-IT: Iterative SUPG with Joint Targets
(3)
𝐵1 , 𝐵2 , . . .
Require: Dataset D, proxy model 𝐴, oracle 𝑂, targets 𝑡𝑃 , 𝑡𝑅 , failure probability 𝛿, budget fraction 𝜌, importance weight 𝜂 1: S ← ∅ ⊲ Accumulated samples 2: 𝜏low ← 0, 𝜏high ← 1 ⊲ Initial thresholds (wide uncertain region) 3: for each batch 𝐵𝑡 ⊆ D do 4: Compute proxy scores {𝐴(𝑥𝑖 )} for 𝑥𝑖 ∈ 𝐵𝑡 5: 𝑘𝑡 ← ⌊𝜌 · |𝐵𝑡 |⌋ ⊲ Sampling budget 6: Compute weights 𝑤𝑖 via Eq. 8 7: Sample 𝑆𝑡 (𝑘𝑡 records w/o replacement, probabilities ∝ 𝑤) 8: Query oracle: 𝑦𝑖 ← 𝑂 (𝑥𝑖 ) for 𝑥𝑖 ∈ 𝑆𝑡 9: S ← S ∪ {(𝐴(𝑥𝑖 ), 𝑦𝑖 , 𝑐𝑖 ) : 𝑥𝑖 ∈ 𝑆𝑡 } 10: ⊲ Update thresholds 11: Compute 𝜏ˆlow from weighted ROC curve 12: Compute corrected target 𝑡𝑅′′ via Eq. 18, 19 13: 𝜏low ← threshold achieving 𝑡𝑅′′ recall 14: 𝜏high ← min threshold with LB precision ≥ 𝑡𝑃 15: if 𝜏high < 𝜏low then ⊲ Conflict resolution 16: 𝜏low ← 𝜏high ← 𝜏balanced via Eq. 21 17: end if 18: ⊲ Classify non-sampled records in 𝐵𝑡 19: 𝑦ˆ𝑖 ← 𝑦𝑖 for 𝑥𝑖 ∈ 𝑆𝑡 ⊲ Sampled records use oracle labels 20: for each 𝑥𝑖 ∈ 𝐵𝑡 \ 𝑆𝑡 do 21: if 𝐴(𝑥𝑖 ) < 𝜏low then 22: 𝑦ˆ𝑖 ← 0 ⊲ Reject 23: else if 𝐴(𝑥𝑖 ) ≥ 𝜏high then 24: 𝑦ˆ𝑖 ← 1 ⊲ Accept 25: else 26: 𝑦ˆ𝑖 ← 𝑂 (𝑥𝑖 ) ⊲ Delegate to oracle 27: end if 28: end for 29: end for
local state (3)
𝜏low , 𝜏high
(1)
𝜏low , 𝜏high
(2)
𝜏low , 𝜏high
(3)
predictions
predictions
predictions
Figure 1: Streaming execution model. Each worker processes its data partition independently, maintaining local threshold estimates and updating them based on its own oracle observations. Workers do not share samples or synchronize.
of batches 𝐵 1(𝑤 ) , 𝐵 2(𝑤 ) , . . .. The execution model imposes one fundamental constraint: batches are processed incrementally and cannot be revisited. A worker’s state after processing batch 𝑡 may depend on its previous state and the current batch, but not on future batches or previously processed ones. Crucially, the constraint applies to raw data: a worker may not re-read records from earlier batches. However, lightweight derived quantities—such as accumulated oracle samples and threshold estimates—are retained in the worker’s state and remain available throughout execution. The algorithms presented in this paper satisfy a stronger property: each worker operates independently, without sharing samples, exchanging threshold estimates, or synchronizing with other workers. Independence eliminates inter-worker communication overhead and enables straightforward deployment in production SQL engines where partitions are processed in isolation. It also precludes reliance on global statistics (e.g., importance sampling weights normalized over all records), which is the key architectural limitation of SUPG that our algorithms overcome. Since all workers execute the same procedure, we present both algorithms from the perspective of a single worker.
4
SUPG-IT: Iterative SUPG with Joint Targets
SUPG-IT operates in the streaming execution model formalized in Section 3, replacing single-pass batch execution with iterative threshold refinement where importance-sampled oracle labels accumulate across batches and drive progressively tighter estimates (Section 4.1). Within SUPG’s statistical framework, SUPG-IT further introduces joint precision-recall targeting using the two-threshold decision framework of Section 3, refining 𝜏high and 𝜏low simultaneously rather than optimizing a single metric in isolation (Section 4.2). The combination of iterative execution and joint targeting raises challenges absent from single-pass, single-metric designs: Sections 4.3–4.5 present mechanisms for bounding sampling uncertainty in the corrected recall target, resolving conflicting precisionrecall constraints, and preventing feedback loops in iterative threshold estimation.
Within each batch, both algorithms sample a subset of records for oracle evaluation. The per-batch sampling budget is 𝑘𝑡 = ⌊𝜌 · |𝐵𝑡 |⌋ oracle calls, where 𝜌 ∈ (0, 1] is the budget fraction. Sampled records receive oracle labels that serve dual purposes: they inform the algorithm’s estimates, and they provide correct classifications for the sampled records themselves. Per-worker quality guarantees compose to global guarantees: since global precision (recall) is a weighted average of per-worker precisions (recalls), satisfying Pr[Precision ≥ 𝑡𝑃 ] ≥ 1 − 𝛿 on every worker implies the same bound globally. When 𝑊 workers operate independently, a union bound yields a global failure probability of at most 𝑊 𝛿; setting 𝛿 = 𝛿 global /𝑊 recovers any desired global confidence level. Appendix D confirms empirically that quality remains stable as 𝑊 increases.
Algorithm 1 presents the complete procedure. The algorithm maintains two thresholds (𝜏high for precision and 𝜏low for recall) that are iteratively refined as evidence grows over successive batches. In the first batch, thresholds are estimated from only 𝑘 1 oracle samples. As samples accumulate across subsequent batches, estimates converge and the uncertain region narrows (Figure 2). 4
Streaming Model Cascades for Semantic SQL
,,
Proxy score threshold
1.0
(1 −𝑘𝑡 /𝑚), a substantial improvement when batch sizes are modest relative to the sample budget.
Accept
0.8 0.6
To ensure that weighted statistics remain unbiased despite nonuniform sampling, each sampled record 𝑥𝑖 receives a Horvitz– Thompson [10] inverse-probability correction:
Uncertain
𝑐𝑖 =
0.4 Reject
0.2 0.0 10
20
30
40
4.2
Uncertain region 𝜏high (precision) 𝜏low (recall)
50
60
70
(9)
Iterative Threshold Refinement
The threshold refinement procedure uses the confidence bounds inherited from SUPG [13]. For a sample mean 𝜇 with standard deviation 𝜎 computed from 𝑠 samples, the upper and lower bounds at confidence level 1 − 𝛿 are: 𝜎 √︁ (10) UB(𝜇, 𝜎, 𝑠, 𝛿) = 𝜇 + √ 2 ln(1/𝛿) 𝑠 𝜎 √︁ LB(𝜇, 𝜎, 𝑠, 𝛿) = 𝜇 − √ 2 ln(1/𝛿) (11) 𝑠 √︁ where 2 ln(1/𝛿) is a conservative upper bound on the Gaussian quantile Φ−1 (1 − 𝛿) [30].
80
Sampling iteration 𝑡 Figure 2: Threshold convergence on synthetic data with overlapping bimodal class distributions (𝑚 = 5,000 records, 𝑘𝑡 = 20 samples per iteration, 𝑡𝑅 = 𝑡𝑃 = 0.8). The recall threshold 𝜏low (orange) rises as oracle samples accumulate. The precision threshold 𝜏high (red) descends as the confidence bound on precision tightens. The shaded uncertain region narrows accordingly, reducing oracle delegation.
4.1
1/𝑚 𝑤𝑖
SUPG-IT processes data in batches, refining thresholds after each batch. Let S (𝑡 ) = {(𝐴(𝑥𝑖 ), 𝑦𝑖 , 𝑐𝑖 )} denote the accumulated sample after processing 𝑡 batches, where 𝑦𝑖 is the oracle label and 𝑐𝑖 is the correction factor from Eq. 9.
Importance Sampling with Defensive Mixing
Recall threshold (𝜏low ). We compute the threshold that achieves the target recall using the weighted ROC curve. Given samples sorted by descending proxy score, the weighted true positive rate at threshold 𝜏 is: Í 𝑖:𝐴(𝑥𝑖 ) ≥𝜏 𝑐 𝑖 · 𝑦𝑖 Í TPR(𝜏) = (12) 𝑖 𝑐 𝑖 · 𝑦𝑖
Accurate threshold estimation requires oracle labels spanning the proxy-score distribution, not only near the decision boundary. We use importance sampling to concentrate labeling on high-impact records while preserving support over the full batch through defensive mixing.
Since TPR(𝜏) is monotonically non-increasing in 𝜏, the recall threshold 𝜏ˆlow is the largest threshold satisfying TPR(𝜏) ≥ 𝑡𝑅 , i.e., the most selective threshold that still achieves the user-specified recall target.
Given proxy scores {𝐴(𝑥𝑖 )} for the 𝑚 = |𝐵𝑡 | records in the current batch, we compute sampling weights: √︁ 𝐴(𝑥𝑖 ) 1 𝑤𝑖 = 𝜂 · Í √︁ (8) + (1 − 𝜂) · 𝑚 𝐴(𝑥 ) 𝑗 𝑗 where 𝜂 ∈ [0, 1] controls the√︁importance–uniform tradeoff. CruÍ cially, the normalization 𝑗 𝐴(𝑥 𝑗 ) is computed over the current batch 𝐵𝑡 , not the entire dataset: this is what enables streaming execution without the global coordination that SUPG requires.
Precision threshold (𝜏high ). For precision, we compute cumulative statistics over samples sorted by descending proxy score. At each candidate threshold 𝜏, let: Í 𝑖:𝐴(𝑥𝑖 ) ≥𝜏 𝑦𝑖 (13) 𝜇 (𝜏) = |{𝑖 : 𝐴(𝑥𝑖 ) ≥ 𝜏 }| √︁ 𝜎 (𝜏) = 𝜇 (𝜏)(1 − 𝜇 (𝜏)) (14)
Unlike SUPG, which samples with replacement, SUPG-IT samples without replacement from each batch, drawing 𝑘𝑡 records with probabilities proportional to {𝑤𝑖 }. Sampling without replacement reduces estimator variance by the finite population correction factor
where 𝑠𝜏 = |{𝑖 : 𝐴(𝑥𝑖 ) ≥ 𝜏 }| is the sample count above threshold 𝜏 and 𝛿 ′ = 𝛿/|S (𝑡 ) | applies a Bonferroni correction, since each unique proxy score in the accumulated sample defines a candidate threshold.
Note that 𝜇 (𝜏) uses raw oracle labels 𝑦𝑖 without correction factors The first√︁term follows SUPG’s importance sampling scheme where 𝑐𝑖 , unlike the recall computation. The omission follows the original 1 Í 𝑤 (𝑥) ∝ 𝐴(𝑥), the variance-optimal choice for estimating 𝑚 𝑖 𝐴(𝑥𝑖 )𝑦𝑖 [13, SUPG design [13] because precision is a ratio where both numerator 18]. The second term is a uniform component that serves as deand denominator sum over the same subpopulation (records above fensive mixing [20]. It guarantees a minimum per-record sampling 𝜏), so the Horvitz–Thompson corrections approximately cancel. probability of (1 − 𝜂)/𝑚 and prevents a failure mode of pure imporThe precision threshold 𝜏high is the minimum threshold where the tance sampling: if the proxy systematically assigns low scores to a statistical lower bound exceeds the precision target: subpopulation of positives, those records are missed entirely and downstream recall estimates become biased. 𝜏high = min{𝜏 : LB(𝜇 (𝜏), 𝜎 (𝜏), 𝑠𝜏 , 𝛿 ′ ) ≥ 𝑡𝑃 } (15)
5
,,
4.3
Liskowski et al.
4.5
Statistical Correction with Target Clipping
The initial recall threshold 𝜏ˆlow is computed from a finite sample and may not achieve the target recall on the full dataset. Following SUPG [13], we apply a corrected recall target, inflated to account for sampling uncertainty. For each record 𝑥𝑖 ∈ S (𝑡 ) , define indicator-weighted statistics over the full accumulated sample: 𝑍 1,𝑖 = 𝑐𝑖 · 𝑦𝑖 · 1[𝐴(𝑥𝑖 ) ≥ 𝜏ˆlow ]
𝑍 2,𝑖 = 𝑐𝑖 · 𝑦𝑖 · 1[𝐴(𝑥𝑖 ) < 𝜏ˆlow ]
(16) (17)
Both sequences have 𝑠 = |S (𝑡 ) | elements, with records on the opposite side of the threshold contributing zero. Sample recall decomposes as 𝑍¯1 /(𝑍¯1 + 𝑍¯2 ), which is increasing in 𝑍¯1 and decreasing in 𝑍¯2 . An upper bound on the sample recall at the true optimal threshold is therefore obtained by replacing these with their respective confidence bounds: UB(𝑍¯1, 𝜎𝑍 1 , 𝑠, 𝛿/2) (18) 𝑡𝑅′ = UB(𝑍¯1, 𝜎𝑍 1 , 𝑠, 𝛿/2) + LB(𝑍¯2, 𝜎𝑍 2 , 𝑠, 𝛿/2)
SUPG-IT avoids this by sampling from all remaining records in each batch, regardless of whether they fall in the accept, reject, or uncertain region: Sampling pool = {𝑥𝑖 : 𝑥𝑖 ∈ 𝐵𝑡 , 𝑥𝑖 ∉ S (𝑡 −1) }
4.6
Oracle delegation. The default strategy (as shown in Algorithm 1) sends all remaining uncertain records to the oracle, guaranteeing correctness at the expense of additional oracle calls. In practice, the uncertain region typically shrinks as samples accumulate across batches, limiting the delegation rate.
(19)
where Δ is a small constant. Clipping prevents over-correction that would unnecessarily increase the delegation rate, while still ensuring the corrected target remains at least as conservative as the original.
Threshold-based fallback. When the oracle budget is constrained, an alternative strategy applies a single threshold to uncertain records, classifying them by proxy score alone:
The final recall threshold is computed using the clipped target:
4.4
Handling Uncertain Records
After the sampling budget is exhausted, records in the uncertain region (𝜏low ≤ 𝐴(𝑥) < 𝜏high ) require a decision. SUPG-IT supports two strategies, chosen based on whether the application prioritizes quality or cost.
However, the correction in Equation 18 can produce extreme values when sample sizes are small or distributions are skewed. SUPG-IT extends SUPG by applying target clipping to bound the corrected target:
𝜏low = max{𝜏 : TPR(𝜏) ≥ 𝑡𝑅′′ }
(22)
The expanded sampling scope enables estimation of the score distribution across all three regions, helps detect proxy miscalibration through high-confidence errors, and provides more robust threshold refinement when initial estimates are poor.
Since 𝑡𝑅′ ≥ 𝑡𝑅 in general, the corrected target requires a lower (more inclusive) recall threshold, which is more conservative: fewer records are rejected outright, reducing the risk of missed positives.
𝑡𝑅′′ = clip(𝑡𝑅′ , 𝑡𝑅 , 𝑡𝑅 + Δ)
Expanded Sampling Scope
The two-threshold decision framework introduced in Section 3 partitions records into accept, reject, and uncertain regions, a structure absent from SUPG, which uses a single threshold and samples from the entire dataset in one pass. In the iterative, streaming setting where thresholds evolve over successive batches, a natural approach would be to restrict sampling to the uncertain region, focusing the oracle budget on records that have not yet been confidently classified. However, restricting sampling creates a feedback loop: inaccurate initial thresholds narrow the uncertain region, confining sampling to a subset of the score distribution, which in turn prevents the algorithm from correcting its thresholds.
(20)
𝜏mid = arg max 𝐹 1 (𝜏)
Threshold Conflict Resolution
(23)
𝜏
Joint precision-recall targeting can produce conflicting constraints where 𝜏high < 𝜏low , creating an invalid configuration in which the accept region falls below the reject region. Such conflicts arise when the proxy is poorly calibrated or the targets are jointly difficult to achieve with the available sample.
computed over the accumulated sample. The fallback eliminates oracle delegation for uncertain records at the cost of potential quality degradation.
When a conflict is detected, SUPG-IT collapses to a single balanced threshold that best matches the user’s desired precision-recall ratio:
GAMCAL takes a different approach from SUPG-IT by replacing statistical threshold estimation with learned calibration. The key insight is that if we can learn a function 𝑔 : [0, 1] → [0, 1] mapping raw proxy scores to calibrated probabilities 𝑔(𝐴(𝑥)) ≈ 𝑃 (𝑦 = 1 | 𝐴(𝑥)), then for any threshold pair (𝜏low, 𝜏high ) we can predict the expected precision, recall, and delegation rate in closed form, without additional oracle calls. The resulting decoupling of threshold optimization from oracle evaluation enables direct numerical optimization of a cost-quality objective in the streaming setting, where past batches cannot be revisited.
𝜏low = 𝜏high = 𝜏balanced = arg min 𝜏
Recall(𝜏) 𝑡𝑅 − Precision(𝜏) 𝑡𝑃
5
(21)
where Recall and Precision are computed from the precision-recall curve over the accumulated sample. Note that collapsing to a single threshold eliminates the uncertain region entirely, so no further records are delegated to the oracle (the cascade reduces to a simple threshold classifier). 6
GAMCAL: Calibration-Based Cascade
Streaming Model Cascades for Semantic SQL
,,
Algorithm 2 GAMCAL: GAM-Calibrated Cascade
assumptions from the SUPG framework that limit its effectiveness. Three observations motivate the shift to a calibration-based approach.
Require: Dataset D, proxy 𝐴, oracle 𝑂, tradeoff 𝛼, 𝐹 𝛽 weight 𝛽, budget fraction 𝜌, smoothing 𝜆, min samples 𝑛 min 1: S ← ∅, 𝑛 last ← 0, 𝑔 ← identity ⊲ Initialize 2: 𝜏low ← 0, 𝜏high ← 1 ⊲ Initial thresholds (wide uncertain region) 3: Compute proxy scores {𝐴(𝑥𝑖 )} and sample 𝑞𝑖 ∼ Uniform(0, 1) for all 𝑥𝑖 ∈ D 4: for each batch 𝐵𝑡 ⊆ D do ˜ 5: Compute 𝑔(𝐴(𝑥 𝑖 ), 𝑞𝑖 ) via Eq. 26 for each 𝑥𝑖 ∈ 𝐵𝑡 ˜ 6: 𝑈𝑡 ← {𝑖 : 𝜏low ≤ 𝑔(𝐴(𝑥 ⊲ Uncertain 𝑖 ), 𝑞𝑖 ) < 𝜏high } 7: 𝑘𝑡 ← min( ⌊𝜌 · |𝐵𝑡 |⌋, |𝑈𝑡 |) 8: Sample 𝑆𝑡 ∼ Uniform(𝑈𝑡 , 𝑘𝑡 ) without replacement 9: Query oracle: 𝑦𝑖 ← 𝑂 (𝑥𝑖 ) for 𝑥𝑖 ∈ 𝑆𝑡 10: S ← S ∪ {(𝐴(𝑥𝑖 ), 𝑦𝑖 ) : 𝑥𝑖 ∈ 𝑆𝑡 } 11: if |S| ≥ 2 · 𝑛 last and min |{𝑖 ∈ S : 𝑦𝑖 = 1}|, |{𝑖 ∈ S : 𝑦𝑖 = 0}| ≥ 𝑛 min then 12: Train GAM 𝑔 on S via Eq. 25 ˜ 13: Recompute 𝑔(𝐴(𝑥 𝑖 ), 𝑞𝑖 ) for all 𝑥𝑖 ∈ D 14: Optimize (𝜏low, 𝜏high ) via Eq. 31 15: 𝑛 last ← |S| 16: end if 17: ⊲ Classify non-sampled records in 𝐵𝑡 18: 𝑦ˆ𝑖 ← 𝑦𝑖 for 𝑥𝑖 ∈ 𝑆𝑡 ⊲ Sampled records use oracle labels 19: for each 𝑥𝑖 ∈ 𝐵𝑡 \ 𝑆𝑡 do ˜ 20: if 𝑔(𝐴(𝑥 𝑖 ), 𝑞𝑖 ) < 𝜏low then 21: 𝑦ˆ𝑖 ← 0 ⊲ Reject ˜ 22: else if 𝑔(𝐴(𝑥 𝑖 ), 𝑞𝑖 ) ≥ 𝜏high then 23: 𝑦ˆ𝑖 ← 1 ⊲ Accept 24: else ˜ 25: 𝑦ˆ𝑖 ← 𝑔(𝐴(𝑥 ⊲ Fallback 𝑖 ), 𝑞𝑖 ) ≥ 0.5 26: end if 27: end for 28: end for
Proxy miscalibration. Both SUPG and SUPG-IT assume that proxy scores are approximately calibrated, i.e., that 𝐴(𝑥) √︁ ≈ 𝑃 (𝑦 = 1 | 𝑥). The importance sampling weights 𝑤 (𝑥) ∝ 𝐴(𝑥) are variance-optimal only under calibration [13], and the confidence bounds on precision and recall depend on the proxy scores’ fidelity as probability estimates. In practice, proxy models, particularly small LLMs and embedding-based classifiers, are often poorly calibrated [7]. A score of 0.7 may correspond to a true positive rate anywhere from 0.4 to 0.95 depending on the dataset and predicate. Poor calibration renders SUPG-IT’s confidence bounds unreliable and produces conservative thresholds with unnecessarily high delegation rates. Limited generalization from oracle labels. In SUPG-IT, each oracle label contributes to threshold estimation only through running statistics (weighted means and variances) computed over the score region it falls in. No mechanism allows labels at one proxy score level to inform predictions at other levels. A smooth calibration model provides exactly such generalization: labels at scattered score levels jointly constrain a function that interpolates across the entire score range. In the streaming setting, where early batches yield few oracle labels, such interpolation extracts substantially more information per label than raw statistical estimation. Continuous cost-quality tradeoff. Beyond these technical concerns, the target-based formulation creates practical challenges. Specifying precision and recall targets requires a priori knowledge of dataset difficulty; identical targets produce vastly different delegation rates across workloads; and target-based methods exhibit binary success/failure behavior with no graceful degradation. A single parameter 𝛼 ∈ [0, 1] governs the tradeoff between classification error and oracle cost (Eq. 7). Replacing fixed targets with this continuous objective allows the cascade to adapt automatically to the proxy’s intrinsic accuracy.
Like SUPG-IT, GAMCAL operates in the streaming execution model of Section 3: each worker processes batches independently, accumulates oracle samples, and refines its local thresholds. However, where SUPG-IT uses oracle labels to tighten confidence bounds on empirical metrics, GAMCAL uses them to train a Generalized Additive Model (GAM) that provides calibrated probability estimates with uncertainty quantification. Thresholds are then optimized against a continuous cost-quality tradeoff rather than fixed precision/recall targets, eliminating the need for users to specify targets a priori.
Taken together, these observations motivate GAMCAL’s threestage pipeline: calibrate proxy scores using a GAM trained on oracle samples, predict expected quality metrics for any threshold configuration from the calibrated model, and optimize thresholds by minimizing the cost-quality objective via numerical optimization.
5.2
Algorithm 2 presents the complete procedure. The remainder of this section motivates the approach (Section 5.1), describes GAM-based calibration (Section 5.2), explains uncertainty-aware routing via random quantiles (Section 5.3), presents the threshold optimization objective (Section 5.4), and discusses the adaptive retraining schedule (Section 5.5) and oracle sampling strategy (Section 5.6).
5.1
GAM-Based Probability Calibration
At the calibrate stage, GAMCAL learns a monotone function 𝑔 : [0, 1] → [0, 1] mapping raw proxy scores 𝑠 = 𝐴(𝑥) to calibrated probabilities 𝑔(𝑠) ≈ 𝑃 (𝑦 = 1 | 𝐴(𝑥) = 𝑠). Several calibration methods have been proposed: Platt scaling fits a logistic function to raw scores [22], isotonic regression fits a non-parametric monotone map [32], and temperature scaling adjusts a single parameter [7]. However, none of these methods fully satisfies the requirements of the cascade setting.
From Statistical Estimation to Learned Calibration
Platt scaling assumes a linear relationship in log-odds space, which is too restrictive when the proxy model’s miscalibration is nonlinear. Isotonic regression makes no smoothness assumptions and tends to
While SUPG-IT addresses SUPG’s limitations around streaming execution and joint precision-recall targeting, it inherits deeper 7
,,
Liskowski et al.
overfit when oracle labels are scarce (precisely the regime encountered in early streaming batches). Neither method provides calibrated uncertainty estimates, which are needed for the uncertaintyaware routing described in Section 5.3.
once and held fixed for the lifetime of the record, ensuring consistent routing across retraining events. Conceptually, the mechanism is a form of posterior sampling [23] applied to the calibration model: rather than routing each record based on the posterior mean 𝑓ˆ(𝑠), GAMCAL draws a sample from the approximate posterior over the calibrated log-odds and routes based on that draw. The standard error se(𝑠) from the GAM controls the spread: when calibration uncertainty is high, the sampled scores are dispersed. When calibration is confident, the samples cluster near the mean. Consequently, records whose proxy scores fall in poorly calibrated regions receive more dispersed calibrated scores and are more likely to land in the uncertain region [𝜏low, 𝜏high ), directing oracle budget toward the records where calibration is least reliable.
Generalized Additive Models (GAMs) [8] occupy a favorable middle ground. A logistic GAM models the calibration function through a smooth spline in log-odds space: log
𝑔(𝑠) = 𝑓 (𝑠) 1 − 𝑔(𝑠)
(24)
where 𝑠 = 𝐴(𝑥) is the raw proxy score and 𝑓 is a smooth function represented by a cubic B-spline basis. The model is fit on accumulated oracle samples S = {(𝐴(𝑥𝑖 ), 𝑦𝑖 )} by maximizing the penalized log-likelihood: L (𝑓 ) =
|S| ∑︁ 𝑖=1
−𝜆
[𝑦𝑖 log 𝑔(𝐴(𝑥𝑖 )) + (1 − 𝑦𝑖 ) log(1 − 𝑔(𝐴(𝑥𝑖 )))] ∫
Soft decision boundaries. Deterministic thresholds create sharp boundaries: records with calibrated scores just above 𝜏high are always accepted, while those just below are always delegated. When many records cluster near a threshold, small estimation errors produce large swings in the delegation rate. Stochastic scoring replaces each sharp boundary with a smooth transition zone, where the probability of delegation decreases continuously as the calibrated score moves away from the threshold. The width of the transition zone adapts automatically: it is wide where se(𝑠) is large (few oracle labels nearby) and narrow where se(𝑠) is small (many oracle labels provide precise calibration).
(25)
′′ 2
(𝑓 ) 𝑑𝑠
∫ The roughness penalty 𝜆 (𝑓 ′′ (𝑠)) 2 𝑑𝑠 controls the bias-variance tradeoff: large 𝜆 produces smoother calibration curves that generalize from few samples (important in early batches), while small 𝜆 allows the model to capture fine-grained calibration structure as oracle labels accumulate. Monotonicity (𝑔′ (𝑠) ≥ 0) is enforced through linear inequality constraints on the spline coefficients during optimization and guarantees that higher proxy scores always map to higher calibrated probabilities.
Exploration for calibration improvement. Stochastic routing ensures that records near decision boundaries are occasionally delegated to the oracle even when the current model would confidently classify them. The resulting oracle labels provide training data in score regions that deterministic routing would never query. The calibration model can then refine its estimates in subsequent retraining events (Section 5.5). The mechanism mirrors Thompson sampling [23, 28], where actions (routing decisions) are randomized according to the posterior probability of being optimal. Exploration is therefore proportional to uncertainty and vanishes as the model converges. Unlike SUPG-IT, which achieves exploration through a separate design choice (expanded sampling scope, Section 4.5), GAMCAL obtains exploration as a natural byproduct of posterior sampling, requiring no additional mechanism or tuning.
GAMs combine the strengths that the alternatives lack: the spline basis captures nonlinear miscalibration patterns that Platt scaling misses (Figure 3), while the smoothness penalty prevents overfitting when oracle samples are limited, unlike isotonic regression. Crucially for the cascade setting, the penalized likelihood framework yields a posterior approximation over 𝑓 : both a mean prediction 𝑓ˆ(𝑠) and a standard error se(𝑠) at each score level. Given a quantile parameter 𝑞 ∈ [0, 1], the stochastic calibrated score is: ˜ 𝑞) = logit−1 𝑓ˆ(𝑠) + Φ−1 (𝑞) · se(𝑠) 𝑔(𝑠, (26) where Φ−1 is the standard normal quantile function. Operating in ˜ 𝑞) ∈ (0, 1) log-odds space and applying the sigmoid ensures that 𝑔(𝑠, for all 𝑞. Our primary implementation uses constrained cubic splines via the pyGAM library. Appendix A describes two alternative implementations (a regularized logistic regression variant with a Platt scaling prior and a bootstrap ensemble) that offer different tradeoffs between monotonicity guarantees, computational cost, and uncertainty robustness.
Uncertainty-directed delegation, soft boundaries, and exploration all arise from a single mechanism (per-record random quantile draws) with no additional parameters beyond the quantile distribution itself. The implicit exploration is precisely what allows GAMCAL to use the simpler oracle sampling strategy described in Section 5.6: because stochastic routing already diversifies the records entering the uncertain region, there is no need for importance sampling or expanded sampling scope.
5.3
5.4
Uncertainty-Aware Routing via Random Quantiles
A key design choice in GAMCAL is that routing decisions are stochastic rather than deterministic. The stochastic calibrated score ˜ 𝑞) (Eq. 26) incorporates a random quantile 𝑞𝑖 ∼ Uniform(0, 1) 𝑔(𝑠, sampled independently for each record 𝑥𝑖 . The quantile 𝑞𝑖 is drawn 8
Direct Threshold Optimization
Once the GAM provides calibrated probabilities, the cascade can predict the expected quality of any threshold configuration without ˜ additional oracle queries. For each record 𝑥𝑖 , let 𝑔˜𝑖 = 𝑔(𝐴(𝑥 𝑖 ), 𝑞𝑖 ) denote the stochastic calibrated score from Eq. 26. Under the twothreshold framework of Section 3, thresholds (𝜏low, 𝜏high ) partition
Streaming Model Cascades for Semantic SQL
,,
0.8
0.8
0.6 0.4 95% CI 𝑔 (𝑠 ) (GAM) Platt scaling
0.2
Observed frequency
1.0
𝑃 (𝑦 = 1 | 𝐴(𝑥 ) =𝑠 )
1.0
0.0
Raw 𝐴(𝑥 )
Platt
GAM
0.6 0.4 0.2 0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Predicted probability
Raw proxy score 𝑠 = 𝐴(𝑥 )
Figure 3: GAM-based calibration on synthetic data with nonlinear miscalibration (𝑛 = 3,000, 𝜆 = 0.6). Left: The GAM calibration curve 𝑔(𝑠) (blue) captures the S-shaped departure from the diagonal that Platt scaling (gray dashed) cannot represent. The shaded band shows the 95% confidence interval from the GAM posterior. Right: Reliability diagram comparing raw, Platt-calibrated, and GAM-calibrated scores. GAM calibration reduces expected calibration error from 0.140 (raw) to 0.005, compared to 0.047 for Platt scaling. records into reject, accept, and uncertain regions. Because 𝑔˜𝑖 estimates the probability that record 𝑥𝑖 is a true positive, each region’s expected contribution to the confusion matrix can be computed in closed form:
The error term is normalized by the error of a no-delegation baseline that classifies all records by proxy at threshold 0.5 (i.e., 𝜏low = 𝜏high = 0.5). The delegation rate lies in [0, 1] and the normalized error equals 1 at the no-delegation baseline, so 𝛼 interpolates meaningfully between the two objectives. Concretely, higher 𝛼 places more weight on quality and widens the uncertain region, while lower 𝛼 narrows the region to minimize oracle calls.
• Reject region (𝑔˜𝑖 < 𝜏low ): Each rejected record has probability Í 𝑔˜𝑖 of being a true positive, yielding 𝑖: 𝑔˜𝑖 <𝜏low 𝑔˜𝑖 expected false negatives. Í • Accept region (𝑔˜𝑖 ≥ 𝜏high ): Accepted records contribute 𝑔˜𝑖 Í expected true positives and (1 − 𝑔˜𝑖 ) expected false positives.
The 𝐹 𝛽 computation assumes full delegation of the uncertain region. In practice, the budget fraction 𝜌 limits oracle calls to ⌊𝜌 · |𝐵𝑡 |⌋ per batch, and any excess uncertain records are classified using the calibrated score at threshold 0.5 (Algorithm 2). The objective thus models idealized quality, but as the calibration model improves and thresholds converge, the uncertain region typically shrinks below the budget, closing the gap between predicted and realized 𝐹 𝛽 .
• Uncertain region (𝜏low ≤ 𝑔˜𝑖 < 𝜏high ): Oracle-delegated records Í are classified correctly, contributing 𝑔˜𝑖 expected true positives and zero classification error. Crucially, the uncertain region contributes no classification error: only oracle cost. Aggregating across regions: ∑︁ E[TP] = 𝑔˜𝑖 (27) 𝑖: 𝑔˜𝑖 ≥𝜏low
E[FP] =
(1 − 𝑔˜𝑖 )
(28)
𝑔˜𝑖
(29)
∑︁
𝑖: 𝑔˜𝑖 ≥𝜏high
E[FN] =
∑︁
Optimization is complicated by the objective’s piecewise-constant structure: because the expected confusion matrix terms are discrete sums over threshold-defined sets, the objective jumps discontinuously whenever a threshold crosses an individual calibrated score and is flat between successive scores. Gradient-based methods are therefore inapplicable. We optimize using differential evolution [27], a gradient-free global optimizer well-suited to such landscapes. To enforce the constraint 𝜏low ≤ 𝜏high , we reparameterize the search space as (𝑦1, 𝑦2 ) ∈ [0, 1] 2 with:
𝑖: 𝑔˜𝑖 <𝜏low
where E[TP] combines both the accept and uncertain regions (both contribute true positives, the former by proxy prediction, the latter by oracle evaluation). The expected 𝐹 𝛽 score follows directly: E[𝐹 𝛽 ] =
(1 + 𝛽 2 ) · E[TP] (1 + 𝛽 2 ) · E[TP] + E[FN] + 𝛽 2 · E[FP]
𝜏low = 𝑦1,
5.5
The objective from Eq. 7 is instantiated as: min
𝛼·
delegation rate
Adaptive Retraining Schedule
As oracle samples accumulate, GAMCAL must periodically update the calibration model and thresholds. Each update incurs a computational cost, since it requires GAM fitting followed by threshold re-optimization via differential evolution (Section 5.4), so retraining at every batch is wasteful.
1 − E[𝐹 𝛽 (𝜏low, 𝜏high )] |{𝑖 : 𝜏low ≤ 𝑔˜𝑖 < 𝜏high }| +(1 − 𝛼) · 1 − E[𝐹 𝛽 (0.5, 0.5)] 𝑛 | {z } | {z } normalized error
(32)
Here 𝑦1 directly sets the lower threshold, while 𝑦2 controls the gap as a fraction of the remaining range [𝑦1, 1]: 𝑦2 = 0 collapses the uncertain region (no delegation), while 𝑦2 = 1 places 𝜏high = 1 (all non-rejected records are delegated).
(30)
with E[𝐹 𝛽 ] = 0 when E[TP] = 0 (i.e., all records fall in the reject region).
𝜏low ,𝜏high
𝜏high = 𝑦1 + (1 − 𝑦1 ) · 𝑦2
(31) 9
,,
Liskowski et al.
Proxy score threshold
1.0 0.8
5.6
𝜏high 𝜏low Retrain
Accept
0.6 Uncertain
0.4 0.2
𝑆𝑡 ∼ Uniform({𝑖 ∈ 𝐵𝑡 : 𝜏low ≤ 𝑔˜𝑖 < 𝜏high }),
Reject
|𝑆𝑡 | = min(⌊𝜌 · |𝐵𝑡 |⌋, |𝑈𝑡 |)
0.0 1
Deleg. rate
Oracle Sampling Strategy
SUPG-IT uses importance sampling from all remaining records in each batch (Section 4.5) to avoid feedback loops where inaccurate thresholds restrict the sampling pool. GAMCAL takes a different approach: oracle labels are drawn by uniform random sampling without replacement from the uncertain region:
where 𝜌 is the budget fraction and |𝑈𝑡 | is the number of uncertain records in batch 𝐵𝑡 . Expanded sampling is unnecessary because GAMCAL’s stochastic routing mechanism (Section 5.3) already ensures that records with high calibration uncertainty are drawn into the uncertain region, even if deterministic thresholds would place them in the accept or reject regions. The random quantiles provide implicit exploration across the score distribution. Moreover, the GAM’s smooth spline basis generalizes from oracle labels in the uncertain region to predictions across the full score range (as argued in Section 5.1), so sampling from a restricted score interval still informs calibration globally.
0 10
20
30
40
50
Batch 𝑡
Figure 4: GAMCAL threshold convergence on synthetic bimodal data (𝑚 = 10,000, batch size 200, 𝜌 = 0.03, 𝛼 = 0.35). Top: Thresholds 𝜏low (orange) and 𝜏high (red) narrow in discrete steps at retraining events (dotted lines) on the doubling schedule. The shaded region marks the uncertain interval. Bottom: Delegation rate drops from 1.0 during the cold-start phase to approximately 0.15 as calibration improves. Each retraining event further reduces delegation.
Uniform sampling also offers a practical advantage over importance sampling: all oracle labels contribute equally to the GAM training data and require no Horvitz–Thompson correction factors [10]. As thresholds converge and the uncertain region narrows, the sampling budget is naturally redirected: fewer records require oracle evaluation, reducing the effective delegation rate without explicit budget management.
GAMCAL adopts a doubling schedule [1], a standard technique in online learning: retrain when the accumulated sample size has at least doubled since the last training event, i.e., when |S| ≥ 2𝑛 last , where 𝑛 last is the sample count at the previous training. For 𝑛 total oracle samples, the doubling schedule bounds the number of retraining events to 𝑂 (log 𝑛), while ensuring that each successive model is trained on at least twice as much data as its predecessor.
6
We evaluate both algorithms against four baselines on six datasets spanning classification, filtering, and join operators. The experiments address three questions: Does learned calibration improve cost-efficiency over statistical threshold estimation (Section 6.2)? Does GAMCAL’s 𝛼 parameter provide predictable control across datasets (Section 6.3)? Does SUPG-IT reliably satisfy user-specified precision-recall targets (Section 6.4)?
Each retraining event triggers two operations: fitting the GAM on the full accumulated sample S (updating both the calibrated probabilities 𝑓ˆ(𝑠) and the standard errors se(𝑠)), and re-optimizing the thresholds (𝜏low, 𝜏high ) via Eq. 31 using the updated calibrated scores.
6.1
To prevent overfitting during early execution, GAMCAL defers the first training until both classes have accumulated a minimum number of samples: min (|{𝑖 ∈ S : 𝑦𝑖 = 0}|, |{𝑖 ∈ S : 𝑦𝑖 = 1}|) ≥ 𝑛 min
Experimental Evaluation
Experimental Setup
Platform. All experiments run on Snowflake’s Cortex AISQL [14], a production SQL engine for semantic operators. The proxy model is Llama 3.1-8B and the oracle model is Llama 3.3-70B, deployed as Cortex LLM inference endpoints. Data is processed in the streaming execution model of Section 3.5 with a batch size of |𝐵𝑡 | = 4,096 rows and a single worker (𝑊 = 1). Within each batch, oracle samples are acquired in sub-batches of 128 records, allowing both algorithms to refine thresholds multiple times per batch. Appendix D confirms that both algorithms are robust to parallelism (𝑊 up to 16).
(33)
Before this condition is met, GAMCAL operates in a cold-start phase with default thresholds 𝜏low = 0, 𝜏high = 1 and identity calibration 𝑔 = id. Under these defaults all records fall in the uncertain region, so GAMCAL delegates every sampled record to the oracle. The resulting full-delegation strategy is conservative but maximizes information gain for the calibration model. For balanced datasets the cold-start phase typically ends within the first few batches. For highly imbalanced predicates, reaching 𝑛 min samples of the minority class may require more batches, which can be mitigated by increasing the budget fraction 𝜌. Figure 4 illustrates these dynamics on synthetic data.
Datasets. We select six datasets spanning different domains, task types, and proxy difficulty levels (Table 1). MMLU [9] (a multiplechoice QA benchmark reduced to a binary predicate: is the selected answer correct?), BoolQ [4], and SST-2 [26] cover knowledge QA, reading comprehension, and sentiment analysis with moderate proxy quality (𝐹 1 > 0.8). In this regime, the proxy alone provides 10
Streaming Model Cascades for Semantic SQL
,,
Table 2: Best 𝐹 1 operating point per algorithm. Each cascade cell shows 𝐹 1 score and delegation rate 𝑑. Bold marks the best cascade algorithm per dataset.
Table 1: Dataset characteristics. Six benchmarks spanning classification, filtering, and join operators with diverse proxy quality. Dataset
Task
MMLU BoolQ IMDB ArXiv SST-2 NYT
AI_CLASSIFY AI_FILTER AI_FILTER AI_FILTER AI_FILTER AI_JOIN
Rows
Pos%
Proxy F1
ECE
Dataset
Proxy-only
SUPG
SUPG-SP
SUPG-IT
GAMCAL
5,000 12,697 50,000 56,181 68,221 250,000
71% 79% 19% 8.5% 46% 0.9%
0.817 0.823 0.382 0.528 0.819 0.209
0.110 0.211 0.452 0.050 0.095 0.067
ArXiv BoolQ IMDB MMLU NYT SST-2
0.528 0.823 0.382 0.817 0.209 0.819
0.541 0.899 0.553 0.863 0.278 0.886
0.979 (74%) 0.980 (82%) 0.976 (80%) 0.981 (82%) 0.990 (40%) 0.972 (37%)
0.992 (86%) 0.990 (86%) 0.990 (90%) 0.993 (87%) 0.990 (44%) 0.980 (41%)
0.973 (69%) 0.997 (81%) 0.983 (84%) 0.996 (84%) 0.967 (20%) 0.996 (56%)
Table 3: 𝐹 1 at fixed delegation budgets. Each cell shows the best 𝐹 1 achievable with delegation rate 𝑑 ≤ budget. Bold marks the best algorithm per column and dataset. 𝑑 ≤ 20%
𝑑 ≤ 30%
Table 4: Minimum delegation rate to achieve target 𝐹 1 . Lower values indicate more cost-efficient algorithms. Bold marks the best algorithm per column. 𝐹 1 ≥ 0.9
𝐹 1 ≥ 0.95
Dataset
SUPG-SP
SUPG-IT
GAMCAL
SUPG-SP
SUPG-IT
GAMCAL
Dataset
SUPG-SP
SUPG-IT
GAMCAL
SUPG-SP
SUPG-IT
GAMCAL
ArXiv BoolQ IMDB MMLU NYT SST-2
0.784 0.880 — 0.857 0.953 0.934
0.798 0.893 — 0.863 0.946 0.923
0.851 0.931 0.685 0.889 0.967 0.954
0.867 0.900 0.770 0.857 0.977 0.954
0.873 0.922 0.764 0.890 0.974 0.964
0.890 0.951 0.771 0.923 0.967 0.977
ArXiv BoolQ IMDB MMLU NYT SST-2
42.5% 24.0% 52.6% 40.8% 16.1% 16.1%
38.9% 30.2% 52.8% 41.8% 16.0% 18.3%
34.5% 10.1% 54.4% 28.6% 9.4% 8.9%
55.6% 69.7% 69.9% 67.4% 21.9% 28.6%
61.9% 58.2% 69.1% 62.9% 22.4% 31.6%
61.6% 29.3% 68.4% 43.9% 17.0% 21.2%
reasonable accuracy. IMDB [17] and ArXiv [5] present harder calibration challenges: on IMDB, the proxy predicts nearly every review as positive, achieving high recall but low precision (ECE = 0.452, the highest in the suite). ArXiv combines a highly imbalanced predicate with comparable proxy accuracy. NYT [24] is the largest benchmark in the suite: 250K candidate pairs from an AI_JOIN over article titles and excerpts, with the lowest positive rate and weakest proxy.
variants use budget fraction 𝜌 = 0.1 and failure probability 𝛿 = 0.2; GAMCAL uses 𝛽 = 1 (𝐹 1 score) in the cost-quality objective. All quality metrics (𝐹 1 , precision, recall) are measured against oracle labels, following the convention established in Section 3. We also report delegation rate 𝑑. Error bars show mean ± standard deviation across seeds.
6.2
Cost-Quality Tradeoff
Figure 5 traces the cost-quality Pareto frontier for GAMCAL and SUPG-IT across all six datasets. At low-to-moderate delegation rates, GAMCAL’s frontier lies above or overlaps SUPG-IT’s on every dataset. Table 2 summarizes the best operating point per algorithm. Both algorithms exceed 𝐹 1 = 0.99 on most datasets, but GAMCAL peaks at lower delegation on BoolQ, MMLU, and SST-2, while SUPG-IT reaches a higher ceiling on ArXiv, IMDB, and NYT at the cost of 6–24 percentage points more delegation.
The expected calibration error (ECE) reported in Table 1 quantifies the gap between proxy scores and true probabilities. High ECE motivates the learned calibration approach of GAMCAL. Algorithms. We evaluate SUPG-IT (Section 4) and GAMCAL (Section 5) against four baselines. SUPG [13] is the original recall-only cascade, optimizing a single threshold with no precision control. SUPG-SP adds joint precision-recall targeting and uncertain-region delegation to SUPG but estimates thresholds from a single oracle sample per batch, without the iterative refinement loop of Algorithm 1. SUPG-SP corresponds to the cascade algorithm implemented in LOTUS [21]. Comparing SUPG-SP to SUPG-IT thus isolates the contribution of iterative refinement. Two reference baselines anchor the cost extremes: Proxy-only classifies all records using the proxy model alone (𝑑 = 0), and Oracle-only delegates every record to the oracle (𝑑 = 1.0).
Learned calibration confers a clear advantage at low delegation budgets. Table 3 reports the best 𝐹 1 achievable within delegation caps of 20% and 30%. At 𝑑 ≤ 20%, GAMCAL leads on all six datasets, outperforming both SUPG-IT and SUPG-SP (the LOTUS cascade). The widest gap is on ArXiv: 0.851 vs. 0.784 for SUPG-SP and 0.798 for SUPG-IT. On IMDB, the SUPG variants cannot operate within this budget at all because their minimum delegation includes both the 𝜌 = 10% sampling budget and mandatory uncertain-region delegation. Raising the cap to 𝑑 ≤ 30% narrows the gap: GAMCAL still leads on five of six datasets, while SUPG-SP edges ahead on NYT (0.977 vs. 0.967) where GAMCAL’s delegation ceiling limits further gains.
Protocol. Each configuration is evaluated across 10 random seeds. To trace cost-quality tradeoff curves, we sweep each algorithm’s native control parameter: SUPG-IT and SUPG-SP sweep a shared target 𝑡𝑃 = 𝑡𝑅 ∈ [0.55, 0.95]; SUPG sweeps 𝑡𝑅 over the same range; and GAMCAL sweeps 𝛼 ∈ [0.10, 0.80] with no budget cap (𝜌 = 1.0), so that 𝛼 alone controls the effective delegation rate. The SUPG
Table 4 examines the same tradeoff from the opposite direction. GAMCAL requires less delegation than SUPG-IT to reach a target 11
,,
Liskowski et al.
ArXiv
BoolQ
𝐹 1 Score
1.0
1.00 0.95
0.8
0.8
0.90 0.6
0.6
0.85 0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
MMLU
𝐹 1 Score
IMDB 1.0
1.00 0.95
0.9
0.90
0.8
0.85
0.7
0.80
0.6 0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
NYT 1.0
0.0
0.6
0.8
1.0
Delegation Rate
0.8
1.0
0.8
1.0
SST-2 1.00 0.95 0.90 0.85
0.0
0.2
0.4
0.6
0.8
1.0
0.0
Delegation Rate Proxy-only
0.6
Oracle
GAMCAL
0.2
0.4
0.6
Delegation Rate SUPG-IT
Figure 5: 𝐹 1 vs. delegation rate for GAMCAL (sweeping 𝛼) and SUPG-IT (sweeping shared target 𝑡𝑃 = 𝑡𝑅 ) across six datasets. Each point is the mean over 10 seeds (error bars: one standard deviation). Dashed horizontal lines mark the proxy-only and oracle baselines. GAMCAL’s frontier lies above or overlaps SUPG-IT’s on every dataset. 𝐹 1 on all six datasets for 𝐹 1 ≥ 0.95 and on five for 𝐹 1 ≥ 0.90. The advantage over SUPG-SP is larger still: on BoolQ, reaching 𝐹 1 ≥ 0.95 costs 𝑑 = 29.3% with GAMCAL versus 69.7% with SUPG-SP—a 58% reduction in oracle calls. On MMLU, the savings are 35% (43.9% vs. 67.4%). The GAM calibration model generalizes across the proxy score distribution: labels at one score level inform predictions at others. The sample-based bounds used by SUPG-IT and SUPG-SP extract less information from the same number of oracle labels.
Within the SUPG family, adding joint precision-recall targeting and uncertain-region delegation (the step from SUPG to SUPG-SP) produces the largest quality gain. SUPG-SP’s peak 𝐹 1 ranges from 0.972 (SST-2) to 0.990 (NYT), far above SUPG’s ceiling of 0.278– 0.899. Iterative refinement (the step from SUPG-SP to SUPG-IT) adds 1–2 𝐹 1 points on all datasets except NYT, where the clean binary join signal makes single-pass estimation already optimal. Appendix Figure 8 provides the full comparison across all four cascade algorithms and all four metrics.
Among individual datasets, NYT best illustrates GAMCAL’s cost advantage. It crosses 𝐹 1 ≥ 0.90 at under 10% delegation, the lowest threshold in the suite. SUPG-IT reaches a higher ceiling (𝐹 1 = 0.990 at 𝑑 = 44%) because the GAM classifies most NYT records confidently in this extreme-imbalance setting and caps delegation at roughly 20% regardless of 𝛼. IMDB presents the hardest calibration challenge. The proxy scores 𝐹 1 = 0.382 alone, predicting nearly every review as positive. Both algorithms nevertheless recover to near-oracle quality (𝐹 1 > 0.98) at high delegation.
In summary, the two proposed algorithms occupy complementary niches. GAMCAL achieves equal or higher 𝐹 1 per oracle call at cost-sensitive operating points, without requiring users to specify quality targets. Its calibration model is particularly effective when few oracle labels are available. SUPG-IT reaches a higher quality ceiling on datasets with challenging calibration (ArXiv, IMDB, NYT) and provides explicit probabilistic guarantees on precision and recall. Sections 6.3 and 6.4 examine these distinct strengths, evaluating GAMCAL’s parameter predictability and SUPG-IT’s target reliability.
Both algorithms substantially outperform SUPG, which is limited to 𝐹 1 ≤ 0.90 and offers no precision control. This limitation is inherent rather than budget-related. SUPG optimizes a single threshold for recall only. Increasing the sampling budget 𝜌 therefore tightens the threshold estimate but cannot address the absence of precision control that causes low 𝐹 1 on datasets with high false-positive rates (e.g., NYT).
6.3
Parameter Predictability
Section 5.1 argued that target-based control requires a priori knowledge of dataset difficulty, since the same target can yield unpredictable delegation rates across workloads. Figure 6 tests this claim 12
Streaming Model Cascades for Semantic SQL
,,
GAMCAL
Delegation Rate
1.0
SUPG-IT
0.8 0.6 0.4 0.2 0.0 0.2
0.4
0.6
0.8
0.6
GAMCAL 𝛼 ArXiv
BoolQ
IMDB
MMLU
0.7
0.8
0.9
SUPG-IT shared target (𝑡𝑃 = 𝑡𝑅 ) NYT
SST-2
Figure 6: Delegation rate as a function of each algorithm’s native control parameter across all six datasets. Left: GAMCAL sweeps 𝛼, where higher 𝛼 prioritizes classification quality over oracle cost. Right: SUPG-IT sweeps the shared target 𝑡𝑃 = 𝑡𝑅 . Each point is the mean over 10 seeds (error bars: one standard deviation). The 𝛼 parameter produces smooth monotonic curves across datasets. A target specifies desired quality, and the delegation required to achieve it varies with dataset difficulty. by plotting each algorithm’s delegation rate against its native control parameter.
Table 5: SUPG-IT target reliability across 289 (𝑡𝑃 , 𝑡𝑅 ) pairs per dataset, 10 seeds each (2,890 runs). The 𝑡𝑃 =𝑡𝑅 column reports the 17 symmetric pairs only (170 runs).
GAMCAL’s 𝛼-to-delegation mapping (left panel) is smooth and monotonic for every dataset, so practitioners can treat 𝛼 as a predictable cost dial. The spread across datasets at a given 𝛼 reflects automatic adaptation to proxy quality: at 𝛼 = 0.5, IMDB receives 34% delegation while NYT receives only 11%. Even at 𝛼 = 0.8, NYT’s delegation plateaus at roughly 20%. The GAM classifies most records confidently in this extreme-imbalance join setting, and further delegation cannot improve quality.
Satisfaction (%)
SUPG-IT’s target-to-delegation mapping (right panel) reflects qualitatively different parameter semantics. A target specifies desired quality, and the delegation required to achieve it depends on the proxy’s intrinsic accuracy: at 𝑡𝑃 = 𝑡𝑅 = 0.80, delegation ranges from 0.6% on SST-2 to 60.6% on IMDB. On easier datasets, the proxy alone satisfies low targets, so the flat regions in the right panel represent configurations where adjusting the target has no effect on cost. On SST-2, delegation stays below 1% for targets up to 0.75 before rising to 24% at 𝑡𝑃 = 𝑡𝑅 = 0.90. Delegation rises sharply only when the target exceeds what the proxy can achieve alone.
6.4
Dataset
All
𝑡𝑃 =𝑡𝑅
Failures
Deleg. (%)
ArXiv IMDB MMLU BoolQ SST-2
100.0 100.0 99.4 98.7 89.4
100.0 100.0 100.0 99.4 99.4
0 0 16 38 305
41.4 54.6 23.6 14.4 4.7
delegation is only 1.4%. The mechanism is consistent: low delegation yields insufficient oracle data for tight statistical bounds, and seed-to-seed variation produces occasional misses. Every failure in the experiment violates exactly one metric (precision or recall), never both. Appendix C visualizes the spatial pattern of these failures. The symmetric targets used in Sections 6.2–6.3 achieve near-perfect satisfaction on all five datasets (Table 5, 𝑡𝑃 =𝑡𝑅 column). Reliability degrades primarily in asymmetric configurations at low delegation levels, precisely where the cascade adds the least value.
Target Reliability
Section 6.3 examined GAMCAL’s parameter predictability. Here we evaluate whether SUPG-IT reliably delivers the joint precisionrecall targets the user specifies. A 17 × 17 grid of target pairs (𝑡𝑃 , 𝑡𝑅 ) from 0.55 to 0.95 in steps of 0.025 is swept across five datasets with 10 random seeds each, for a total of 14,450 runs. NYT is excluded due to the computational cost of the full grid on 250K rows. Table 5 summarizes the results. ArXiv and IMDB achieve perfect joint satisfaction across all 289 configurations. These are also the highestdelegation datasets.
7
Conclusion
We formalized the model cascade problem for semantic SQL in a streaming execution model with independent parallel workers and presented two complementary algorithms. SUPG-IT extends SUPG to streaming execution with iterative threshold refinement and joint precision-recall guarantees. Each worker processes its partition independently, requiring no global synchronization. GAMCAL replaces user-specified targets with a learned calibration model that directly optimizes a cost-quality tradeoff and adapts automatically to dataset difficulty. Experiments on six datasets spanning different domains, task types, and proxy quality levels confirm that both algorithms outperform existing baselines, including the SUPG cascade
BoolQ and MMLU maintain per-run satisfaction of at least 98.7%, with failures confined to low-delegation configurations. SST-2 shows the most target misses (89.4% satisfaction), concentrated in regions where the proxy’s intrinsic quality nearly satisfies the target with minimal oracle involvement. Among failing configurations, mean 13
,,
Liskowski et al.
in LOTUS [21]. GAMCAL achieves higher 𝐹 1 per oracle call at costsensitive operating points, requiring up to 58% fewer oracle calls than LOTUS to reach 𝐹 1 ≥ 0.95, while SUPG-IT reaches a higher quality ceiling with a mean peak 𝐹 1 of 0.989 and provides formal probabilistic guarantees on precision and recall. For practitioners, GAMCAL is the default choice for cost-sensitive workloads where no specific quality target is required, while SUPG-IT is preferred when formal guarantees on precision and recall are needed.
Cortex aisql: A production sql engine for unstructured data. Proceedings of the ACM on Management of Data, 2025. [15] C. Liu, M. Russo, M. Cafarella, L. Cao, P. B. Chen, Z. Chen, M. Franklin, T. Kraska, S. Madden, and G. Vitagliano. Palimpzest: A declarative system for optimizing AI workloads. arXiv preprint arXiv:2405.14696, 2025. [16] Y. Lu, A. Chowdhery, S. Kandula, and S. Chaudhuri. Accelerating machine learning inference with probabilistic predicates. In Proceedings of the 2018 International Conference on Management of Data, 2018. [17] A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 142–150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. [18] J. Neyman. On the two different aspects of the representative method: the method of stratified sampling and the method of purposive selection. Journal of the Royal Statistical Society, 97(4):558–625, 1934. [19] L. Nie, Z. Ding, E. Hu, C. Jermaine, and S. Chaudhuri. Online cascade learning for efficient inference over streams. In International Conference on Machine Learning, 2024. [20] A. Owen and Y. Zhou. Safe and effective importance sampling. Journal of the American Statistical Association, 95(449):135–143, 2000. [21] L. Patel et al. Semantic operators: A declarative model for rich, ai-based analytics over text data. arXiv preprint, 2025. [22] J. C. Platt. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In Advances in Large Margin Classifiers, pages 61–74. MIT Press, 1999. [23] D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, and Z. Wen. A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1):1–96, 2018. [24] E. Sandhaus. The new york times annotated corpus. Linguistic Data Consortium, LDC2008T19, 2008. [25] D. Servén and C. Brummitt. pygam: Generalized additive models in python. https://github.com/dswah/pyGAM, 2018. Zenodo. DOI: 10.5281/zenodo.1208723. [26] R. Socher, A. Perelygin, J. Wu, J. Chuang, C. D. Manning, A. Ng, and C. Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1631–1642, Seattle, Washington, USA, Oct. 2013. Association for Computational Linguistics. [27] R. Storn and K. Price. Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4):341–359, 1997. [28] W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285–294, 1933. [29] C. Wang, S. Augenstein, K. Rush, W. Jitkrittum, H. Narasimhan, A. S. Rawat, A. K. Menon, and A. Go. Cascade-aware training of language models. In Advances in Neural Information Processing Systems, 2024. [30] L. Wasserman. All of Statistics: A Concise Course in Statistical Inference. Springer, 2004. [31] S. N. Wood. Generalized Additive Models: An Introduction with R. Chapman and Hall/CRC, 2nd edition, 2017. [32] B. Zadrozny and C. Elkan. Transforming classifier scores into accurate multiclass probability estimates. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 694–699, 2002. [33] M. J. Zellinger and M. Thomson. Efficiently deploying LLMs with controlled risk. arXiv preprint arXiv:2410.02173, 2024. [34] M. J. Zellinger and M. Thomson. Rational tuning of LLM cascades via probabilistic modeling. Transactions on Machine Learning Research, 2025.
The approach has two limitations. Our formulation treats oracle labels as ground truth, an assumption that holds when the oracle is considerably more accurate than the proxy but may degrade under noisy or adversarial oracle conditions. The current framework handles binary predicates only, whereas production semantic SQL engines also support multi-class operators that require extending the two-threshold decision framework. Generalizing the cascade to multi-class settings is a natural next step. The union-bound composition of per-worker guarantees (Section 3.5) is conservative. Tighter global bounds that exploit partition structure could reduce the per-worker failure probability budget. Cross-partition coordination mechanisms that preserve global quality guarantees without inter-worker communication and richer calibration models that adapt to non-stationary data distributions are further promising directions.
References [1] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006. [2] L. Chen, M. Zaharia, and J. Zou. Frugalgpt: How to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.05176, 2023. [3] Y. Chung, R. Desai, J. He, Y. Xiao, T. Hottelier, Y.-L. Kom Samo, P. Kadilkar, X. Chen, S. Idicula, F. Özcan, A. Halevy, and Y. Papakonstantinou. 100x cost & latency reduction: Performance analysis of AI query approximation using lightweight proxy models. In Proceedings of the 2026 ACM SIGMOD International Conference on Management of Data, 2026. [4] C. Clark, K. Lee, M.-W. Chang, T. Kwiatkowski, M. Collins, and K. Toutanova. BoolQ: Exploring the surprising difficulty of natural yes/no questions. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Association for Computational Linguistics, 2019. [5] A. Cohan, F. Dernoncourt, D. S. Kim, T. Bui, S. Kim, W. Chang, and N. Goharian. A discourse-aware attention model for abstractive summarization of long documents. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pages 615–621, New Orleans, Louisiana, June 2018. Association for Computational Linguistics. [6] H. Dai, B. Y. Wang, X. Wan, B. Dai, S. Yang, A. Nova, P. Yin, P. M. Phothilimthana, C. Sutton, and D. Schuurmans. UQE: A query engine for unstructured databases. In Advances in Neural Information Processing Systems, 2024. [7] C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, 2017. [8] T. Hastie and R. Tibshirani. Generalized additive models. Statistical Science, 1986. [9] D. Hendrycks, C. Burns, S. Basart, A. Zou, M. Mazeika, D. Song, and J. Steinhardt. Measuring massive multitask language understanding. Sept. 2020. [10] D. G. Horvitz and D. J. Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American Statistical Association, 47(260):663–685, 1952. [11] W. Jitkrittum, N. Gupta, A. K. Menon, H. Narasimhan, A. S. Rawat, and S. Kumar. When does confidence-based cascade deferral suffice? In Advances in Neural Information Processing Systems, 2023. [12] D. Kang, J. Emmons, F. Abuzaid, P. Bailis, and M. Zaharia. Noscope: Optimizing neural network queries over video at scale. In Proceedings of the VLDB Endowment, volume 10, 2017. [13] D. Kang, E. Gan, P. Bailis, T. Hashimoto, and M. Zaharia. Approximate selection with guarantees using proxies. Proceedings of the VLDB Endowment, 13(11), 2020. [14] P. Liskowski, B. Han, P. Aggarwal, B. Chen, B. Jiang, N. Jindal, Z. Li, A. Lin, K. Schmaus, J. Tayade, W. Zhao, A. Datta, N. Wiegand, and D. Tsirogiannis. 14
Streaming Model Cascades for Semantic SQL
A
,,
structure. The regularized variant thus interpolates between Platt scaling (few samples) and a flexible spline model (many samples).
Calibration Model Variants
Section 5.2 presents the GAM calibration framework and derives the stochastic calibrated score (Eq. 26). The framework admits three implementations, each offering different tradeoffs between monotonicity guarantees, computational cost, and uncertainty robustness.
A.1
Confidence intervals are obtained via the Laplace approximation. At the fitted optimum 𝜃ˆ, the Hessian of the regularized loss is: 𝐻 = 𝑋 ⊤ diag(ℎ̂ ◦ (1 − ℎ̂)) 𝑋 + 𝜆𝐼
where 𝑋 is the spline design matrix and ℎ̂ = 𝜎 (𝑋 𝜃ˆ) are the fitted probabilities. The approximate posterior covariance is√︁Σ = 𝐻 −1 , and the standard error of 𝑓 (𝑠) at a new point is se(𝑠) = 𝜙 (𝑠) ⊤ Σ 𝜙 (𝑠) where 𝜙 (𝑠) is the spline basis vector. The stochastic calibrated score is computed as in Eq. 26.
Constrained GAM with Analytical Confidence Intervals
All experiments in Section 6 use this variant as the default calibration model. The implementation represents 𝑓 as a cubic spline and fits the penalized log-likelihood (Eq. 25) subject to monotonicity constraints 𝑔′ (𝑠) ≥ 0, enforced as linear inequality constraints on the spline coefficients during iteratively reweighted least squares (IRLS) optimization. We use the pyGAM library [25], which implements this procedure following Wood [31].
Compared to the constrained GAM, this variant does not enforce monotonicity as a hard constraint. Instead, the monotonic prior 𝜇𝜃 encourages (but does not guarantee) monotonicity. In practice, the smoothness of the spline basis and the regularization toward 𝜇𝜃 produce approximately monotone calibration curves for reasonable values of 𝜆.
The fitted model provides a posterior approximation via the Bayesian interpretation ∫ of penalized splines [31]. Concretely, the roughness penalty 𝜆 (𝑓 ′′ ) 2 𝑑𝑠 corresponds to a Gaussian prior on the spline coefficients, and the penalized likelihood yields an approximate posterior. From this posterior, the mean 𝑓ˆ(𝑠) and standard error se(𝑠) are extracted, and the stochastic calibrated score follows Eq. 26: ˜ 𝑞) = logit−1 𝑓ˆ(𝑠) + Φ−1 (𝑞) · se(𝑠) 𝑔(𝑠, (34)
A.2
A.3
Uncertainty is estimated from the ensemble spread in logit space. Let ℓ¯(𝑠) denote the mean bootstrap logit and Δ𝑏 (𝑠) the deviation of the 𝑏-th ensemble member: 𝐵 1 ∑︁ logit(𝑔𝑏 (𝑠)) (38) ℓ¯(𝑠) = 𝐵
An alternative variant replaces the constrained GAM with logistic regression over an explicit spline basis expansion, offering tighter control over the optimization and a closed-form Laplace approximation for uncertainty.
𝑏=1
Δ𝑏 (𝑠) = logit(𝑔𝑏 (𝑠)) − ℓ¯(𝑠)
Raw proxy scores are first transformed to log-odds space ℓ = logit(𝐴(𝑥)), clipped to [ℓmin, ℓmax ] for numerical stability. A degree3 B-spline basis with 𝑝 uniformly spaced knots is constructed via scikit-learn’s SplineTransformer, yielding 𝑑 basis functions 𝜙 1 (ℓ), . . . , 𝜙𝑑 (ℓ). The calibration function is then: 𝑓 (𝑠) =
𝑗=1
𝜃 𝑗 𝜙 𝑗 (logit(𝑠))
(39)
𝐵 form an empirical distribution The centered deviations {Δ𝑏 (𝑠)}𝑏=1 of calibration uncertainty at score level 𝑠. The stochastic calibrated score is: 𝐵 ˜ 𝑞) = logit−1 logit(𝜇 (𝑠)) + 𝑄𝑞 {Δ𝑏 (𝑠)}𝑏=1 𝑔(𝑠, (40)
where 𝜇 (𝑠) = 𝑔(𝑠) is the primary model’s prediction and 𝑄𝑞 denotes the 𝑞-th quantile of the empirical distribution.
(35)
Unlike the analytical CIs and Laplace approximation, the bootstrap makes no distributional assumptions about calibration uncertainty. However, it is computationally more expensive: each retraining event requires fitting 𝐵 + 1 GAMs, and each calibration query requires 𝐵 + 1 forward passes, roughly two orders of magnitude more than the primary variant. The bootstrap is most appropriate when the Gaussian approximation may be inadequate, e.g., with highly skewed class distributions or very few oracle samples, or when the calibration curve has sharp features that the analytical CIs may underestimate.
and the coefficients 𝜃 are fit by minimizing the regularized negative log-likelihood: |S| ∑︁
𝜆 [𝑦𝑖 log 𝑔(𝐴(𝑥𝑖 )) + (1 − 𝑦𝑖 ) log(1 − 𝑔(𝐴(𝑥𝑖 )))]+ ∥𝜃 −𝜇𝜃 ∥ 2 2 𝑖=1 (36) using L-BFGS-B optimization with analytically computed gradients. min −
Bootstrap Ensemble
The bootstrap variant quantifies calibration uncertainty empirically rather than analytically. A primary GAM 𝑔 is trained on the full oracle sample S as in Appendix A.1. Additionally, 𝐵 bootstrap GAMs 𝑔1, . . . , 𝑔𝐵 are trained on resamples S1∗, . . . , S𝐵∗ drawn with replacement from S (we use 𝐵 = 100).
Regularized Logistic Regression with Spline Basis
𝑑 ∑︁
(37)
𝜃
The prior mean 𝜇𝜃 encodes an inductive bias toward the identity mapping in log-odds space (no calibration adjustment): the coefficients are set to linearly spaced values 𝜇 𝑗 = ℓmin + (ℓmax − ℓmin ) · 𝑗/𝑑. When oracle samples are scarce and 𝜆 is large, the regularization pulls 𝜃 toward 𝜇𝜃 , effectively recovering Platt scaling as a default. As more samples accumulate and 𝜆’s relative influence diminishes, the model departs from this prior to capture nonlinear calibration
All experiments in this paper use the constrained GAM (Appendix A.1) as the default because it combines monotonicity guarantees, analytical uncertainty estimates, and minimal computational overhead. The regularized variant (Appendix A.2) is preferable when oracle samples are scarce: its Platt scaling prior provides a principled 15
,,
Liskowski et al.
MMLU
SST-2
0.95
0.95
0.95
0.85
0.85
0.85
0.75
0.75
0.75
0.65
0.65
0.65
0.55
0.55
0.55
1.0 0.8 0.6 0.4 0.2
Joint Satisfaction Rate
Target Precision (𝑡𝑃 )
BoolQ
5
5
0.8
0.9
5 0.6
5
5 0.5
Target Recall (𝑡𝑅 )
0.7
5 0.9
5 0.6
5
5 0.5
0.8
5 0.9
5
5 0.8
Target Recall (𝑡𝑅 )
0.7
5
5 0.6
0.7
5 0.5
0.0
Target Recall (𝑡𝑅 )
Figure 7: Joint target satisfaction rate for SUPG-IT across a 17 × 17 grid of (𝑡𝑃 , 𝑡𝑅 ) targets on BoolQ, MMLU, and SST-2 (10 seeds per configuration). White indicates 100% satisfaction. Yellow and red indicate partial or zero satisfaction. ArXiv and IMDB (not shown) achieve 100% on all 289 configurations. fallback that prevents overfitting before sufficient data accumulates. The bootstrap (Appendix A.3) trades a roughly 100× increase in computation for distribution-free uncertainty estimates, making it appropriate when the Gaussian posterior approximation may be inadequate. The GAMCAL framework is agnostic to the calibration backend: any implementation that provides calibrated probabilities with pointwise uncertainty can be substituted without modifying the cascade logic.
B
The dashed baseline markers reveal how each algorithm positions relative to the proxy-only and oracle bounds. At high recall targets, SUPG drops below the proxy-only accuracy baseline on most datasets. ArXiv is the most extreme case: all operating points fall below the proxy line. Lowering the threshold to capture more positive records admits enough false positives to degrade overall accuracy below what the unmodified proxy achieves. The three algorithms with precision control (GAMCAL, SUPG-IT, SUPG-SP) avoid this degradation and approach oracle quality at high delegation, reaching 𝐹 1 within a few percent of perfect on every dataset.
Extended Pareto Analysis
Figure 8 extends the main Pareto analysis (Figure 5) from 𝐹 1 to all four quality metrics and from two algorithms to all four.
C
Target Satisfaction Patterns
Figure 7 visualizes the spatial distribution of target failures from the experiment described in Section 6.4. The failure patterns differ across datasets but share a common cause. On BoolQ, failures cluster at high precision targets (𝑡𝑃 ≥ 0.75) with low recall targets, where the proxy’s intrinsic precision nearly meets the target and the cascade delegates few records to the oracle. The pattern on MMLU is milder: all 16 failures reach 90% satisfaction, again concentrated in low-delegation regions. About a third of configurations on SST-2 fall short of full satisfaction. The worst cases occur at high recall with low precision targets (e.g., 𝑡𝑃 = 0.575, 𝑡𝑅 = 0.95), where delegation drops below 1% and precision is the metric that misses in every case. Across all three datasets, failures concentrate where the cascade is barely active: mean delegation in failing configurations is 1–8%. The proxy alone nearly satisfies the targets in these regions, and the few oracle samples collected are insufficient for tight statistical bounds.
SUPG’s curves are vertical lines at 𝑑 = 𝜌 = 0.1 because the algorithm samples a fixed fraction 𝜌 of records for oracle labeling, regardless of the recall target. The oracle labels both estimate the recall threshold 𝜏 and provide final classifications for the sampled records. The proxy classifies the remainder using 𝜏. Because 𝜏 depends on 𝑡𝑅 but the sample size does not, sweeping 𝑡𝑅 changes quality metrics but not cost. By contrast, SUPG-SP and SUPG-IT add a second stage that delegates all uncertain-region records to the oracle, creating a variable cost that grows with the target. The precision and recall columns together expose the asymmetry that motivates joint targeting. SUPG controls recall only: as 𝑡𝑅 increases, the threshold drops to accept more records, and precision degrades in proportion. On NYT (positive rate 0.9%), precision falls from 0.17 to 0.03 across the sweep, producing 𝐹 1 below 0.06 at the highest recall targets. ArXiv and IMDB show the same pattern, with precision dropping below 0.15 and 0.25. Adding the upper threshold eliminates this failure mode: both SUPG-SP and SUPG-IT maintain precision above 0.99 on NYT while achieving the same recall range. The recall column confirms the complementary view: all SUPG variants achieve high recall at the strongest targets because recall is directly optimized through the lower threshold.
D
Robustness to Parallelism
Both algorithms are designed for independent per-worker execution. Increasing the number of workers𝑊 (the degree of parallelism) splits the data into smaller partitions. Each worker therefore runs fewer iterative refinement steps and may face partition-level class imbalance. To quantify this effect, we evaluated GAMCAL and 16
Streaming Model Cascades for Semantic SQL
,,
SUPG-IT at 𝑊 ∈ {1, 2, 4, 8, 16} on IMDB, MMLU, and SST-2 with batch size 4096 and 10 seeds per configuration.
a larger shift on SST-2 (+0.012 𝐹 1 at 𝑊 =16), where fewer batches per worker leave thresholds less converged, widening the uncertain region and raising delegation from 41% to 56%. The additional oracle labels improve quality at higher cost. Seed-level variability does not increase with 𝑊 : for both algorithms, the standard deviation of 𝐹 1 across seeds remains stable or decreases as partitions shrink.
Quality is robust to parallelism. The mean best 𝐹 1 across datasets varies by less than 0.001 for GAMCAL and less than 0.004 for SUPGIT as 𝑊 increases from 1 to 16. GAMCAL is the more stable of the two, with a maximum per-dataset shift of 0.002 𝐹 1 . SUPG-IT shows
17
,,
Liskowski et al. F1
Accuracy
1.0
0.9
ArXiv
0.8 0.6
IMDB
0.9 0.8
0.4
0.5
0.6
0.2
0.5
0.2
0.4
1.00
1.0
1.00
0.9
0.95
0.9
0.90
0.8
0.85
0.7
0.90 0.8
0.85
1.0
0.7 0.80
0.75 1.0
1.0
0.9
0.9
0.8
0.8
0.7
0.7
0.6
1.00
1.00
1.00
0.90
0.90 0.85 0.80
0.8
0.9 0.8 0.7
0.2
0.70
0.95
1.0
0.6
0.75
1.00
1.0
0.4
0.80
0.2
0.7
0.6
0.85
0.4
0.8
0.75
0.95
0.6
0.9
0.80
1.00
0.8
1.0
0.85
0.70
1.0
0.7
0.90
0.75
0.75
0.8
0.95
0.80
0.80
0.9
0.6
0.85
0.85
0.8
0.2
0.90
0.90
1.0
0.4
0.95
0.95
1.0
0.4
0.5
0.4
0.6
0.6
0.6
0.5
MMLU
0.8
0.7
0.6
0.80
NYT
1.0
0.6
0.7
0.95
SST-2
Recall
1.0
0.8
0.4
BoolQ
Precision
1.0
0.5
0.0
1.00
1.00
1.0
0.95
0.95
0.9
0.90
0.90
0.85
0.85
0.80
0.80
0.8
0.7
0.75 0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
Delegation Rate
0.4
0.6
0.8
1.0
0.0
0.2
Delegation Rate Proxy-only
Oracle
0.4
0.6
0.8
1.0
Delegation Rate GAMCAL
18
SUPG-IT
SUPG-SP
0.0
0.2
0.4
0.6
0.8
1.0
Delegation Rate SUPG
Figure 8: Complete Pareto grid: all four cascade algorithms (GAMCAL, SUPG-IT, SUPG-SP, SUPG) across six datasets and four metrics (𝐹 1 , accuracy, precision, recall). Dashed horizontal lines mark the proxy-only and oracle baselines.