Paper deep dive
Streaming Model Cascades for Semantic SQL
Paweł Liskowski, Kyle Schmaus
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%
Last extracted: 4/2/2026, 3:29:23 AM
Summary
The paper introduces two adaptive cascade algorithms, SUPG-IT and GAMCAL, designed for streaming, per-partition execution in distributed semantic SQL engines. These algorithms optimize the cost-quality tradeoff of using large language models (LLMs) by routing queries between a fast proxy model and an expensive oracle model, addressing limitations in existing frameworks like SUPG regarding global dataset access and single-metric optimization.
Entities (5)
Relation Signals (3)
SUPG-IT → extends → SUPG
confidence 95% · SUPG-IT extends the SUPG statistical framework to streaming execution
GAMCAL → uses → Generalized Additive Models
confidence 95% · GAMCAL... using GAMs for probability calibration with uncertainty quantification
SUPG-IT → deployedin → Snowflake Cortex AISQL
confidence 90% · Both algorithms are designed for and evaluated in the context of Snowflake’s Cortex AISQL
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Modern data warehouses extend SQL with semantic operators that invoke large language models on each qualifying row, but the per-row 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 F1 > 0.95 on every dataset. GAMCAL achieves higher F1 per oracle call at cost-sensitive operating points, while SUPG-IT reaches a higher quality ceiling with formal guarantees on precision and recall.
Tags
Links
- Source: https://arxiv.org/abs/2604.00660v1
- Canonical: https://arxiv.org/abs/2604.00660v1
Trouble viewing inline? Open PDF directly →
Full Text
97,520 characters extracted from source content.
Expand or collapse full text
Streaming Model Cascades for Semantic SQL Paweł Liskowski pawel.liskowski@snowflake.com Snowflake Inc.PoznańPoland and Kyle Schmaus kyle.schmaus@snowflake.com Snowflake Inc.San Francisco, CAUSA Abstract. Modern data warehouses extend SQL with semantic operators that invoke large language models on each qualifying row, but the per-row 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 F1>0.95F_1>0.95 on every dataset. GAMCAL achieves higher F1F_1 per oracle call at cost-sensitive operating points, while SUPG-IT reaches a higher quality ceiling with formal guarantees on precision and recall. †copyright: none†conference: ; ; 1. 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 (Patel and others, 2025; Liskowski et al., 2025). 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 (Liskowski et al., 2025). Model cascades address this challenge by routing most rows through a fast, inexpensive proxy model (e.g., a small LLM or embedding-based 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 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 (Chen et al., 2023) and up to 90% in streaming inference (Nie et al., 2024)) and are recognized as a key optimization in semantic query processing systems (Patel and others, 2025; Liu et al., 2025). SUPG (Kang et al., 2020) 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 P(positive∣x)P(positive x). In practice, proxy models are often poorly calibrated (Guo et al., 2017), 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. 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. (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 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: (1) minτlow,τhighα⋅error(τlow,τhigh)+(1−α)⋅cost(τlow,τhigh) _ _low, _high\;α·error( _low, _high)+(1-α)·cost( _low, _high) where τlow _low and τhigh _high are the delegation thresholds and α∈[0,1]α∈[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 (Liskowski et al., 2025). On six benchmarks, both algorithms exceed F1=0.95F_1=0.95 on every dataset. GAMCAL outperforms the SUPG cascade in LOTUS (Patel and others, 2025) at cost-sensitive operating points, leading on all six datasets under a 20%20\% delegation budget and requiring up to 58%58\% fewer oracle calls to reach F1≥0.95F_1≥ 0.95. SUPG-IT reaches the highest quality ceiling, with a mean peak F1F_1 of 0.9890.989. In summary, our contributions are: • 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 precision-recall 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. Related Work Approximate selection with proxy models. Kang et al. (Kang et al., 2020) 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 (Kang et al., 2017) and probabilistic predicates (Lu et al., 2018) 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 (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. LLM cascades. Routing queries through progressively more capable models has been explored extensively. FrugalGPT (Chen et al., 2023) learns a scoring function that predicts answer reliability and cascades queries through increasingly expensive API endpoints. Nie et al. (Nie et al., 2024) formalize cascade learning as online imitation learning where smaller models learn from LLM demonstrations in a streaming setting. Jitkrittum et al. (Jitkrittum et al., 2023) characterize when confidence-based deferral is optimal and identify failure modes involving specialist models and label noise. Wang et al. (Wang et al., 2024) modify the small model’s training loss to focus on tokens that at least one cascade model predicts correctly. Zellinger and Thomson (Zellinger and Thomson, 2025) model the joint distribution of calibrated confidences across a sequence of LLMs using Markov copulas, enabling continuous threshold optimization. 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. Probability calibration. Mapping model outputs to well-calibrated probabilities is a long-standing problem. Platt scaling (Platt, 1999) fits a logistic function to raw scores, temperature scaling (Guo et al., 2017) adjusts a single parameter, and isotonic regression (Zadrozny and Elkan, 2002) fits a non-parametric monotone map. Guo et al. (Guo et al., 2017) demonstrated that modern neural networks are often poorly calibrated despite high accuracy. Generalized Additive Models (Hastie and Tibshirani, 1986) offer a flexible middle ground through penalized spline fitting. Calibration has also been applied within cascade frameworks: Zellinger and Thomson (Zellinger and Thomson, 2024) 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. Semantic query processing. Several systems embed LLM-powered operators into SQL and dataframe APIs for processing unstructured data at scale (Patel and others, 2025; Liskowski et al., 2025; Liu et al., 2025). LOTUS (Patel and others, 2025) includes cascade support based on single-pass SUPG. Cortex AISQL (Liskowski et al., 2025) 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 (Dai et al., 2024) uses embedding-based classifiers for semantic filters, and Chung et al. (Chung et al., 2026) 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 per-predicate cost than full replacement in exchange for controlled accuracy. 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. Setting and Notation Consider a dataset =x1,x2,…,xnD=\x_1,x_2,…,x_n\ of n records to be processed by a binary semantic predicate (e.g., AI_FILTER). We have access to two models: • Oracle model O:→0,1O:D→\0,1\: An expensive but accurate model (e.g., a large LLM) that produces a binary label yi=O(xi)y_i=O(x_i) for each record, at per-invocation cost cOc_O. • Proxy model A:→[0,1]A:D→[0,1]: A fast, inexpensive model that returns a confidence score A(xi)∈[0,1]A(x_i)∈[0,1] estimating the probability that yi=1y_i=1, at per-invocation cost cA≪cOc_A c_O. Following standard practice in the cascade literature (Kang et al., 2020), we treat oracle labels as ground truth and measure all quality metrics with respect to yi\y_i\. 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 (Liskowski et al., 2025). Our goal is to produce predictions y^i y_i for all records while minimizing oracle invocations. Since cA≪cOc_A c_O, we assume the proxy is executed on all records, yielding scores A(xi)i=1n\A(x_i)\_i=1^n. 3.2. Two-Threshold Decision Framework Our cascade algorithms partition records into three regions using two thresholds τlow _low and τhigh _high where 0≤τlow≤τhigh≤10≤ _low≤ _high≤ 1: (1) Reject region (A(x)<τlowA(x)< _low): The proxy is confident the record does not satisfy the predicate. Predict y^=0 y=0 without oracle evaluation. (2) Accept region (A(x)≥τhighA(x)≥ _high): The proxy is confident the record satisfies the predicate. Predict y^=1 y=1 without oracle evaluation. (3) Uncertain region (τlow≤A(x)<τhigh _low≤ A(x)< _high): The proxy lacks confidence. Invoke the oracle to obtain y^=O(x) y=O(x). The delegation rate d is the fraction of records routed to the oracle: (2) d=|xi:τlow≤A(xi)<τhigh|nd= |\x_i: _low≤ A(x_i)< _high\|n We state the framework in terms of the raw proxy score A(x)A(x) for concreteness. More generally, the thresholds may operate on any monotone transformation of the proxy output. GAMCAL (Section 5) replaces A(x)A(x) with a calibrated decision score that incorporates learned probability estimates (Section 5.2), but the three-region structure, quality metrics, and delegation rate carry over unchanged. 3.3. Quality Metrics The cascade’s three-region structure determines how classification errors arise. Accepted records receive y^i=1 y_i=1 without oracle verification; those with yi=0y_i=0 are false positives. Rejected records receive y^i=0 y_i=0; those with yi=1y_i=1 are false negatives. Delegated records receive y^i=yi y_i=y_i from the oracle and contribute no errors. Errors thus originate exclusively from the accept and reject regions. Precision depends on τhigh _high: raising it reduces false positives but delegates more records to the oracle. Recall is governed by τlow _low: lowering it reduces false negatives at the cost of higher delegation. We quantify quality using: (3) Precision =TPTP+FP,Recall=TPTP+FN = TPTP+FP, = TPTP+FN (4) Fβ F_β =(1+β2)⋅Precision⋅Recallβ2⋅Precision+Recall =(1+β^2)· Precision·Recallβ^2·Precision+Recall where FβF_β balances precision and recall (β>1β>1 favors recall; β=1β=1 yields the standard F1F_1 score). The cascade problem is thus a three-way tradeoff among precision, recall, and oracle cost. 3.4. Problem Formulations We consider two complementary problem formulations, each addressed by one of our algorithms. 3.4.1. Target-Based Formulation (SUPG-IT) Users specify minimum precision and recall targets tPt_P and tRt_R along with a failure probability δ. The goal is to find thresholds (τlow,τhigh)( _low, _high) such that, over the randomness of oracle sampling: (5) Pr[Precision≥tP] [Precision≥ t_P] ≥1−δ ≥ 1-δ (6) Pr[Recall≥tR] [Recall≥ t_R] ≥1−δ ≥ 1-δ while minimizing the delegation rate. The two constraints are coupled: improving recall requires lowering τlow _low while improving precision requires raising τhigh _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.2. Cost-Quality Tradeoff Formulation (GAMCAL) Rather than specifying fixed targets, users provide a tradeoff parameter α∈[0,1]α∈[0,1] controlling the balance between classification quality and oracle cost. The objective is: (7) minτlow,τhighα⋅error(τlow,τhigh)+(1−α)⋅cost(τlow,τhigh) _ _low, _high\;α·error( _low, _high)+(1-α)·cost( _low, _high) where error captures classification quality (derived from 1−Fβ1-F_β, 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. 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 W parallel workers, worker w processing its partition as a sequence of batches B1(w),B2(w),…B_1^(w),B_2^(w),…. The execution model imposes one fundamental constraint: batches are processed incrementally and cannot be revisited. A worker’s state after processing batch t 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. Worker W1W_1local stateτlow(1),τhigh(1) _low^(1), _high^(1)Worker W2W_2local stateτlow(2),τhigh(2) _low^(2), _high^(2)Worker W3W_3local stateτlow(3),τhigh(3) _low^(3), _high^(3)B1(1),B2(1),…B_1^(1),B_2^(1),…B1(2),B2(2),…B_1^(2),B_2^(2),…B1(3),B2(3),…B_1^(3),B_2^(3),…predictionspredictionspredictions 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. 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. Within each batch, both algorithms sample a subset of records for oracle evaluation. The per-batch sampling budget is kt=⌊ρ⋅|Bt|⌋k_t= ρ·|B_t| oracle calls, where ρ∈(0,1]ρ∈(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≥tP]≥1−δ [Precision≥ t_P]≥ 1-δ on every worker implies the same bound globally. When W workers operate independently, a union bound yields a global failure probability of at most WδWδ; setting δ=δglobal/Wδ= _global/W recovers any desired global confidence level. Appendix D confirms empirically that quality remains stable as W increases. 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 _high and τlow _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 precision-recall constraints, and preventing feedback loops in iterative threshold estimation. Algorithm 1 presents the complete procedure. The algorithm maintains two thresholds (τhigh _high for precision and τlow _low for recall) that are iteratively refined as evidence grows over successive batches. In the first batch, thresholds are estimated from only k1k_1 oracle samples. As samples accumulate across subsequent batches, estimates converge and the uncertain region narrows (Figure 2). Algorithm 1 SUPG-IT: Iterative SUPG with Joint Targets 1:Dataset D, proxy model A, oracle O, targets tP,tRt_P,t_R, failure probability δ, budget fraction ρ, importance weight η 2:←∅S← ⊳ Accumulated samples 3:τlow←0,τhigh←1 _low← 0, _high← 1 ⊳ Initial thresholds (wide uncertain region) 4:for each batch Bt⊆B_t do 5: Compute proxy scores A(xi)\A(x_i)\ for xi∈Btx_i∈ B_t 6: kt←⌊ρ⋅|Bt|⌋k_t← ρ·|B_t| ⊳ Sampling budget 7: Compute weights wiw_i via Eq. 8 8: Sample StS_t (ktk_t records w/o replacement, probabilities ∝w w) 9: Query oracle: yi←O(xi)y_i← O(x_i) for xi∈Stx_i∈ S_t 10: ←∪(A(xi),yi,ci):xi∈StS ∪\(A(x_i),y_i,c_i):x_i∈ S_t\ 11: ⊳ Update thresholds 12: Compute τ^low τ_low from weighted ROC curve 13: Compute corrected target tR′t_R via Eq. 18, 19 14: τlow← _low← threshold achieving tR′t_R recall 15: τhigh← _high← min threshold with LB precision ≥tP≥ t_P 16: if τhigh<τlow _high< _low then ⊳ Conflict resolution 17: τlow←τhigh←τbalanced _low← _high← _balanced via Eq. 21 18: end if 19: ⊳ Classify non-sampled records in BtB_t 20: y^i←yi y_i← y_i for xi∈Stx_i∈ S_t ⊳ Sampled records use oracle labels 21: for each xi∈Bt∖Stx_i∈ B_t S_t do 22: if A(xi)<τlowA(x_i)< _low then 23: y^i←0 y_i← 0 ⊳ Reject 24: else if A(xi)≥τhighA(x_i)≥ _high then 25: y^i←1 y_i← 1 ⊳ Accept 26: else 27: y^i←O(xi) y_i← O(x_i) ⊳ Delegate to oracle 28: end if 29: end for 30:end for Figure 2. Threshold convergence on synthetic data with overlapping bimodal class distributions (m=5,000m=5,000 records, kt=20k_t=20 samples per iteration, tR=tP=0.8t_R=t_P=0.8). The recall threshold τlow _low (orange) rises as oracle samples accumulate. The precision threshold τhigh _high (red) descends as the confidence bound on precision tightens. The shaded uncertain region narrows accordingly, reducing oracle delegation. 4.1. Importance Sampling with Defensive Mixing 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. Given proxy scores A(xi)\A(x_i)\ for the m=|Bt|m=|B_t| records in the current batch, we compute sampling weights: (8) wi=η⋅A(xi)∑jA(xj)+(1−η)⋅1mw_i=η· A(x_i) _j A(x_j)+(1-η)· 1m where η∈[0,1]η∈[0,1] controls the importance–uniform tradeoff. Crucially, the normalization ∑jA(xj) _j A(x_j) is computed over the current batch BtB_t, not the entire dataset: this is what enables streaming execution without the global coordination that SUPG requires. The first term follows SUPG’s importance sampling scheme where w(x)∝A(x)w(x) A(x), the variance-optimal choice for estimating 1m∑iA(xi)yi 1m _iA(x_i)y_i (Neyman, 1934; Kang et al., 2020). The second term is a uniform component that serves as defensive mixing (Owen and Zhou, 2000). It guarantees a minimum per-record sampling probability of (1−η)/m(1-η)/m and prevents a failure mode of pure importance sampling: if the proxy systematically assigns low scores to a subpopulation of positives, those records are missed entirely and downstream recall estimates become biased. Unlike SUPG, which samples with replacement, SUPG-IT samples without replacement from each batch, drawing ktk_t records with probabilities proportional to wi\w_i\. Sampling without replacement reduces estimator variance by the finite population correction factor (1−kt/m)(1-k_t/m), a substantial improvement when batch sizes are modest relative to the sample budget. To ensure that weighted statistics remain unbiased despite non-uniform sampling, each sampled record xix_i receives a Horvitz–Thompson (Horvitz and Thompson, 1952) inverse-probability correction: (9) ci=1/mwic_i= 1/mw_i 4.2. Iterative Threshold Refinement The threshold refinement procedure uses the confidence bounds inherited from SUPG (Kang et al., 2020). For a sample mean μ with standard deviation σ computed from s samples, the upper and lower bounds at confidence level 1−δ1-δ are: (10) UB(μ,σ,s,δ) (μ,σ,s,δ) =μ+σs2ln(1/δ) =μ+ σ s 2 (1/δ) (11) LB(μ,σ,s,δ) (μ,σ,s,δ) =μ−σs2ln(1/δ) =μ- σ s 2 (1/δ) where 2ln(1/δ) 2 (1/δ) is a conservative upper bound on the Gaussian quantile Φ−1(1−δ) ^-1(1-δ) (Wasserman, 2004). SUPG-IT processes data in batches, refining thresholds after each batch. Let (t)=(A(xi),yi,ci)S^(t)=\(A(x_i),y_i,c_i)\ denote the accumulated sample after processing t batches, where yiy_i is the oracle label and cic_i is the correction factor from Eq. 9. Recall threshold (τlow _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: (12) TPR(τ)=∑i:A(xi)≥τci⋅yi∑ici⋅yiTPR(τ)= _i:A(x_i)≥τc_i· y_i _ic_i· y_i Since TPR(τ)TPR(τ) is monotonically non-increasing in τ, the recall threshold τ^low τ_low is the largest threshold satisfying TPR(τ)≥tRTPR(τ)≥ t_R, i.e., the most selective threshold that still achieves the user-specified recall target. Precision threshold (τhigh _high). For precision, we compute cumulative statistics over samples sorted by descending proxy score. At each candidate threshold τ, let: (13) μ(τ) μ(τ) =∑i:A(xi)≥τyi|i:A(xi)≥τ| = _i:A(x_i)≥τy_i|\i:A(x_i)≥τ\| (14) σ(τ) σ(τ) =μ(τ)(1−μ(τ)) = μ(τ)(1-μ(τ)) Note that μ(τ)μ(τ) uses raw oracle labels yiy_i without correction factors cic_i, unlike the recall computation. The omission follows the original SUPG design (Kang et al., 2020) because precision is a ratio where both numerator and denominator sum over the same subpopulation (records above τ), so the Horvitz–Thompson corrections approximately cancel. The precision threshold τhigh _high is the minimum threshold where the statistical lower bound exceeds the precision target: (15) τhigh=minτ:LB(μ(τ),σ(τ),sτ,δ′)≥tP _high= \τ:LB(μ(τ),σ(τ),s_τ,δ )≥ t_P\ where sτ=|i:A(xi)≥τ|s_τ=|\i:A(x_i)≥τ\| is the sample count above threshold τ and δ′=δ/|(t)|δ =δ/|S^(t)| applies a Bonferroni correction, since each unique proxy score in the accumulated sample defines a candidate threshold. 4.3. Statistical Correction with Target Clipping The initial recall threshold τ^low τ_low is computed from a finite sample and may not achieve the target recall on the full dataset. Following SUPG (Kang et al., 2020), we apply a corrected recall target, inflated to account for sampling uncertainty. For each record xi∈(t)x_i ^(t), define indicator-weighted statistics over the full accumulated sample: (16) Z1,i Z_1,i =ci⋅yi⋅[A(xi)≥τ^low] =c_i· y_i·1[A(x_i)≥ τ_low] (17) Z2,i Z_2,i =ci⋅yi⋅[A(xi)<τ^low] =c_i· y_i·1[A(x_i)< τ_low] Both sequences have s=|(t)|s=|S^(t)| elements, with records on the opposite side of the threshold contributing zero. Sample recall decomposes as Z¯1/(Z¯1+Z¯2) Z_1/( Z_1+ Z_2), which is increasing in Z¯1 Z_1 and decreasing in Z¯2 Z_2. An upper bound on the sample recall at the true optimal threshold is therefore obtained by replacing these with their respective confidence bounds: (18) tR′=UB(Z¯1,σZ1,s,δ/2)UB(Z¯1,σZ1,s,δ/2)+LB(Z¯2,σZ2,s,δ/2)t_R = UB( Z_1, _Z_1,s,δ/2)UB( Z_1, _Z_1,s,δ/2)+LB( Z_2, _Z_2,s,δ/2) Since tR′≥tRt_R ≥ t_R 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. 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: (19) tR′=clip(tR′,tR,tR+Δ)t_R =clip(t_R ,t_R,t_R+ ) 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. The final recall threshold is computed using the clipped target: (20) τlow=maxτ:TPR(τ)≥tR′ _low= \τ:TPR(τ)≥ t_R \ 4.4. Threshold Conflict Resolution Joint precision-recall targeting can produce conflicting constraints where τhigh<τlow _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. When a conflict is detected, SUPG-IT collapses to a single balanced threshold that best matches the user’s desired precision-recall ratio: (21) τlow=τhigh=τbalanced=argminτ|Recall(τ)Precision(τ)−tRtP| _low= _high= _balanced= *arg\,min_τ | Recall(τ)Precision(τ)- t_Rt_P | 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). 4.5. 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. 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: (22) Sampling pool=xi:xi∈Bt,xi∉(t−1)Sampling pool=\x_i:x_i∈ B_t,\;x_i ^(t-1)\ 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. 4.6. Handling Uncertain Records After the sampling budget is exhausted, records in the uncertain region (τlow≤A(x)<τhigh _low≤ A(x)< _high) require a decision. SUPG-IT supports two strategies, chosen based on whether the application prioritizes quality or cost. 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. 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: (23) τmid=argmaxτF1(τ) _mid= *arg\,max_τF_1(τ) computed over the accumulated sample. The fallback eliminates oracle delegation for uncertain records at the cost of potential quality degradation. 5. GAMCAL: Calibration-Based Cascade 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 g:[0,1]→[0,1]g:[0,1]→[0,1] mapping raw proxy scores to calibrated probabilities g(A(x))≈P(y=1∣A(x))g(A(x))≈ P(y=1 A(x)), then for any threshold pair (τlow,τhigh)( _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. 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. 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). Algorithm 2 GAMCAL: GAM-Calibrated Cascade 1:Dataset D, proxy A, oracle O, tradeoff α, FβF_β weight β, budget fraction ρ, smoothing λ, min samples nminn_ 2:←∅S← , nlast←0n_last← 0, g←identityg ⊳ Initialize 3:τlow←0 _low← 0, τhigh←1 _high← 1 ⊳ Initial thresholds (wide uncertain region) 4:Compute proxy scores A(xi)\A(x_i)\ and sample qi∼Uniform(0,1)q_i (0,1) for all xi∈x_i 5:for each batch Bt⊆B_t do 6: Compute g~(A(xi),qi) g(A(x_i),q_i) via Eq. 26 for each xi∈Btx_i∈ B_t 7: Ut←i:τlow≤g~(A(xi),qi)<τhighU_t←\i: _low≤ g(A(x_i),q_i)< _high\ ⊳ Uncertain 8: kt←min(⌊ρ⋅|Bt|⌋,|Ut|)k_t← ( ρ·|B_t| ,|U_t|) 9: Sample St∼Uniform(Ut,kt)S_t (U_t,k_t) without replacement 10: Query oracle: yi←O(xi)y_i← O(x_i) for xi∈Stx_i∈ S_t 11: ←∪(A(xi),yi):xi∈StS ∪\(A(x_i),y_i):x_i∈ S_t\ 12: if ||≥2⋅nlast|S|≥ 2· n_last and min(|i∈:yi=1|,|i∈:yi=0|)≥nmin (|\i :y_i\!=\!1\|,\;|\i :y_i\!=\!0\| )≥ n_ then 13: Train GAM g on S via Eq. 25 14: Recompute g~(A(xi),qi) g(A(x_i),q_i) for all xi∈x_i 15: Optimize (τlow,τhigh)( _low, _high) via Eq. 31 16: nlast←||n_last←|S| 17: end if 18: ⊳ Classify non-sampled records in BtB_t 19: y^i←yi y_i← y_i for xi∈Stx_i∈ S_t ⊳ Sampled records use oracle labels 20: for each xi∈Bt∖Stx_i∈ B_t S_t do 21: if g~(A(xi),qi)<τlow g(A(x_i),q_i)< _low then 22: y^i←0 y_i← 0 ⊳ Reject 23: else if g~(A(xi),qi)≥τhigh g(A(x_i),q_i)≥ _high then 24: y^i←1 y_i← 1 ⊳ Accept 25: else 26: y^i←g~(A(xi),qi)≥0.5 y_i← g(A(x_i),q_i)≥ 0.5 ⊳ Fallback 27: end if 28: end for 29:end for 5.1. From Statistical Estimation to Learned Calibration While SUPG-IT addresses SUPG’s limitations around streaming execution and joint precision-recall targeting, it inherits deeper assumptions from the SUPG framework that limit its effectiveness. Three observations motivate the shift to a calibration-based approach. Proxy miscalibration. Both SUPG and SUPG-IT assume that proxy scores are approximately calibrated, i.e., that A(x)≈P(y=1∣x)A(x)≈ P(y=1 x). The importance sampling weights w(x)∝A(x)w(x) A(x) are variance-optimal only under calibration (Kang et al., 2020), 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 (Guo et al., 2017). 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]α∈[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. Taken together, these observations motivate GAMCAL’s three-stage 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. GAM-Based Probability Calibration At the calibrate stage, GAMCAL learns a monotone function g:[0,1]→[0,1]g:[0,1]→[0,1] mapping raw proxy scores s=A(x)s=A(x) to calibrated probabilities g(s)≈P(y=1∣A(x)=s)g(s)≈ P(y=1 A(x)=s). Several calibration methods have been proposed: Platt scaling fits a logistic function to raw scores (Platt, 1999), isotonic regression fits a non-parametric monotone map (Zadrozny and Elkan, 2002), and temperature scaling adjusts a single parameter (Guo et al., 2017). However, none of these methods fully satisfies the requirements of the cascade setting. 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 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 uncertainty-aware routing described in Section 5.3. Generalized Additive Models (GAMs) (Hastie and Tibshirani, 1986) occupy a favorable middle ground. A logistic GAM models the calibration function through a smooth spline in log-odds space: (24) logg(s)1−g(s)=f(s) g(s)1-g(s)=f(s) where s=A(x)s=A(x) is the raw proxy score and f is a smooth function represented by a cubic B-spline basis. The model is fit on accumulated oracle samples =(A(xi),yi)S=\(A(x_i),y_i)\ by maximizing the penalized log-likelihood: (25) ℒ(f)= (f)= ∑i=1||[yilogg(A(xi))+(1−yi)log(1−g(A(xi)))] _i=1^|S| [y_i g(A(x_i))+(1-y_i) (1-g(A(x_i))) ] −λ∫(f′)2s -λ (f )^2\,ds The roughness penalty λ∫(f′(s))2sλ (f (s))^2\,ds 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 (g′(s)≥0g (s)≥ 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. 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 f: both a mean prediction f^(s) f(s) and a standard error se(s)se(s) at each score level. Given a quantile parameter q∈[0,1]q∈[0,1], the stochastic calibrated score is: (26) g~(s,q)=logit−1(f^(s)+Φ−1(q)⋅se(s)) g(s,q)=logit^-1\! ( f(s)+ ^-1(q)·se(s) ) where Φ−1 ^-1 is the standard normal quantile function. Operating in log-odds space and applying the sigmoid ensures that g~(s,q)∈(0,1) g(s,q)∈(0,1) for all q. 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. Figure 3. GAM-based calibration on synthetic data with nonlinear miscalibration (n=3,000n=3,000, λ=0.6λ=0.6). Left: The GAM calibration curve g(s)g(s) (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.1400.140 (raw) to 0.0050.005, compared to 0.0470.047 for Platt scaling. 5.3. 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 g~(s,q) g(s,q) (Eq. 26) incorporates a random quantile qi∼Uniform(0,1)q_i (0,1) sampled independently for each record xix_i. The quantile qiq_i is drawn 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 (Russo et al., 2018) applied to the calibration model: rather than routing each record based on the posterior mean f^(s) f(s), GAMCAL draws a sample from the approximate posterior over the calibrated log-odds and routes based on that draw. The standard error se(s)se(s) 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)[ _low, _high), directing oracle budget toward the records where calibration is least reliable. Soft decision boundaries. Deterministic thresholds create sharp boundaries: records with calibrated scores just above τhigh _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(s)se(s) is large (few oracle labels nearby) and narrow where se(s)se(s) is small (many oracle labels provide precise calibration). 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 (Thompson, 1933; Russo et al., 2018), 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. 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.4. 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 xix_i, let g~i=g~(A(xi),qi) g_i= g(A(x_i),q_i) denote the stochastic calibrated score from Eq. 26. Under the two-threshold framework of Section 3, thresholds (τlow,τhigh)( _low, _high) partition records into reject, accept, and uncertain regions. Because g~i g_i estimates the probability that record xix_i is a true positive, each region’s expected contribution to the confusion matrix can be computed in closed form: • Reject region (g~i<τlow g_i< _low): Each rejected record has probability g~i g_i of being a true positive, yielding ∑i:g~i<τlowg~i _i:\, g_i< _low g_i expected false negatives. • Accept region (g~i≥τhigh g_i≥ _high): Accepted records contribute ∑g~iΣ g_i expected true positives and ∑(1−g~i)Σ(1- g_i) expected false positives. • Uncertain region (τlow≤g~i<τhigh _low≤ g_i< _high): Oracle-delegated records are classified correctly, contributing ∑g~iΣ g_i expected true positives and zero classification error. Crucially, the uncertain region contributes no classification error: only oracle cost. Aggregating across regions: (27) [TP] [TP] =∑i:g~i≥τlowg~i = _i:\, g_i≥ _low g_i (28) [FP] [FP] =∑i:g~i≥τhigh(1−g~i) = _i:\, g_i≥ _high(1- g_i) (29) [FN] [FN] =∑i:g~i<τlowg~i = _i:\, g_i< _low g_i where [TP]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 FβF_β score follows directly: (30) [Fβ]=(1+β2)⋅[TP](1+β2)⋅[TP]+[FN]+β2⋅[FP]E[F_β]= (1+β^2)·E[TP](1+β^2)·E[TP]+E[FN]+β^2·E[FP] with [Fβ]=0E[F_β]=0 when [TP]=0E[TP]=0 (i.e., all records fall in the reject region). The objective from Eq. 7 is instantiated as: (31) minτlow,τhighα⋅1−[Fβ(τlow,τhigh)]1−[Fβ(0.5,0.5)]⏟normalized error+(1−α)⋅|i:τlow≤g~i<τhigh|n⏟delegation rate _ _low, _high\;α· 1-E[F_β( _low, _high)]1-E[F_β(0.5,0.5)]_normalized error+(1-α)· |\i: _low≤ g_i< _high\|n_delegation rate The error term is normalized by the error of a no-delegation baseline that classifies all records by proxy at threshold 0.50.5 (i.e., τlow=τhigh=0.5 _low= _high=0.5). The delegation rate lies in [0,1][0,1] and the normalized error equals 11 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. The FβF_β computation assumes full delegation of the uncertain region. In practice, the budget fraction ρ limits oracle calls to ⌊ρ⋅|Bt|⌋ ρ·|B_t| per batch, and any excess uncertain records are classified using the calibrated score at threshold 0.50.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 FβF_β. 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 (Storn and Price, 1997), a gradient-free global optimizer well-suited to such landscapes. To enforce the constraint τlow≤τhigh _low≤ _high, we reparameterize the search space as (y1,y2)∈[0,1]2(y_1,y_2)∈[0,1]^2 with: (32) τlow=y1,τhigh=y1+(1−y1)⋅y2 _low=y_1, _high=y_1+(1-y_1)· y_2 Here y1y_1 directly sets the lower threshold, while y2y_2 controls the gap as a fraction of the remaining range [y1,1][y_1,1]: y2=0y_2=0 collapses the uncertain region (no delegation), while y2=1y_2=1 places τhigh=1 _high=1 (all non-rejected records are delegated). 5.5. 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. GAMCAL adopts a doubling schedule (Cesa-Bianchi and Lugosi, 2006), a standard technique in online learning: retrain when the accumulated sample size has at least doubled since the last training event, i.e., when ||≥2nlast|S|≥ 2n_last, where nlastn_last is the sample count at the previous training. For n total oracle samples, the doubling schedule bounds the number of retraining events to O(logn)O( n), while ensuring that each successive model is trained on at least twice as much data as its predecessor. Each retraining event triggers two operations: fitting the GAM on the full accumulated sample S (updating both the calibrated probabilities f^(s) f(s) and the standard errors se(s)se(s)), and re-optimizing the thresholds (τlow,τhigh)( _low, _high) via Eq. 31 using the updated calibrated scores. To prevent overfitting during early execution, GAMCAL defers the first training until both classes have accumulated a minimum number of samples: (33) min(|i∈:yi=0|,|i∈:yi=1|)≥nmin (|\i :y_i=0\|,\;|\i :y_i=1\| )≥ n_ Before this condition is met, GAMCAL operates in a cold-start phase with default thresholds τlow=0 _low=0, τhigh=1 _high=1 and identity calibration g=idg=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 nminn_ 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. Figure 4. GAMCAL threshold convergence on synthetic bimodal data (m=10,000m=10,000, batch size 200200, ρ=0.03ρ=0.03, α=0.35α=0.35). Top: Thresholds τlow _low (orange) and τhigh _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.01.0 during the cold-start phase to approximately 0.150.15 as calibration improves. Each retraining event further reduces delegation. 5.6. 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: St S_t ∼Uniform(i∈Bt:τlow≤g~i<τhigh), (\i∈ B_t: _low≤ g_i< _high\), |St| |S_t| =min(⌊ρ⋅|Bt|⌋,|Ut|) = ( ρ·|B_t| ,\;|U_t|) where ρ is the budget fraction and |Ut||U_t| is the number of uncertain records in batch BtB_t. 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. 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 (Horvitz and Thompson, 1952). 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. 6. Experimental Evaluation Table 1. Dataset characteristics. Six benchmarks spanning classification, filtering, and join operators with diverse proxy quality. Dataset Task Rows Pos% Proxy F1 ECE MMLU AI_CLASSIFY 5,000 71% 0.817 0.110 BoolQ AI_FILTER 12,697 79% 0.823 0.211 IMDB AI_FILTER 50,000 19% 0.382 0.452 ArXiv AI_FILTER 56,181 8.5% 0.528 0.050 SST-2 AI_FILTER 68,221 46% 0.819 0.095 NYT AI_JOIN 250,000 0.9% 0.209 0.067 Table 2. Best F1F_1 operating point per algorithm. Each cascade cell shows F1F_1 score and delegation rate d. Bold marks the best cascade algorithm per dataset. Dataset Proxy-only SUPG SUPG-SP SUPG-IT GAMCAL ArXiv 0.5280.528 0.5410.541 0.9790.979 (74%) 0.9920.992 (86%) 0.9730.973 (69%) BoolQ 0.8230.823 0.8990.899 0.9800.980 (82%) 0.9900.990 (86%) 0.9970.997 (81%) IMDB 0.3820.382 0.5530.553 0.9760.976 (80%) 0.9900.990 (90%) 0.9830.983 (84%) MMLU 0.8170.817 0.8630.863 0.9810.981 (82%) 0.9930.993 (87%) 0.9960.996 (84%) NYT 0.2090.209 0.2780.278 0.9900.990 (40%) 0.9900.990 (44%) 0.9670.967 (20%) SST-2 0.8190.819 0.8860.886 0.9720.972 (37%) 0.9800.980 (41%) 0.9960.996 (56%) Table 3. F1F_1 at fixed delegation budgets. Each cell shows the best F1F_1 achievable with delegation rate d≤d≤ budget. Bold marks the best algorithm per column and dataset. d≤20%d≤ 20\% d≤30%d≤ 30\% Dataset SUPG-SP SUPG-IT GAMCAL SUPG-SP SUPG-IT GAMCAL ArXiv 0.7840.784 0.7980.798 0.8510.851 0.8670.867 0.8730.873 0.8900.890 BoolQ 0.8800.880 0.8930.893 0.9310.931 0.9000.900 0.9220.922 0.9510.951 IMDB — — 0.6850.685 0.7700.770 0.7640.764 0.7710.771 MMLU 0.8570.857 0.8630.863 0.8890.889 0.8570.857 0.8900.890 0.9230.923 NYT 0.9530.953 0.9460.946 0.9670.967 0.9770.977 0.9740.974 0.9670.967 SST-2 0.9340.934 0.9230.923 0.9540.954 0.9540.954 0.9640.964 0.9770.977 Table 4. Minimum delegation rate to achieve target F1F_1. Lower values indicate more cost-efficient algorithms. Bold marks the best algorithm per column. F1≥0.9F_1≥ 0.9 F1≥0.95F_1≥ 0.95 Dataset SUPG-SP SUPG-IT GAMCAL SUPG-SP SUPG-IT GAMCAL ArXiv 42.5%42.5\% 38.9%38.9\% 34.5%34.5\% 55.6%55.6\% 61.9%61.9\% 61.6%61.6\% BoolQ 24.0%24.0\% 30.2%30.2\% 10.1%10.1\% 69.7%69.7\% 58.2%58.2\% 29.3%29.3\% IMDB 52.6%52.6\% 52.8%52.8\% 54.4%54.4\% 69.9%69.9\% 69.1%69.1\% 68.4%68.4\% MMLU 40.8%40.8\% 41.8%41.8\% 28.6%28.6\% 67.4%67.4\% 62.9%62.9\% 43.9%43.9\% NYT 16.1%16.1\% 16.0%16.0\% 9.4%9.4\% 21.9%21.9\% 22.4%22.4\% 17.0%17.0\% SST-2 16.1%16.1\% 18.3%18.3\% 8.9%8.9\% 28.6%28.6\% 31.6%31.6\% 21.2%21.2\% 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)? 6.1. Experimental Setup Platform. All experiments run on Snowflake’s Cortex AISQL (Liskowski et al., 2025), 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 |Bt|=4,096|B_t|=4,096 rows and a single worker (W=1W=1). Within each batch, oracle samples are acquired in sub-batches of 128128 records, allowing both algorithms to refine thresholds multiple times per batch. Appendix D confirms that both algorithms are robust to parallelism (W up to 16). Datasets. We select six datasets spanning different domains, task types, and proxy difficulty levels (Table 4). MMLU (Hendrycks et al., 2020) (a multiple-choice QA benchmark reduced to a binary predicate: is the selected answer correct?), BoolQ (Clark et al., 2019), and SST-2 (Socher et al., 2013) cover knowledge QA, reading comprehension, and sentiment analysis with moderate proxy quality (F1>0.8F_1>0.8). In this regime, the proxy alone provides reasonable accuracy. IMDB (Maas et al., 2011) and ArXiv (Cohan et al., 2018) present harder calibration challenges: on IMDB, the proxy predicts nearly every review as positive, achieving high recall but low precision (ECE=0.452ECE=0.452, the highest in the suite). ArXiv combines a highly imbalanced predicate with comparable proxy accuracy. NYT (Sandhaus, 2008) 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. The expected calibration error (ECE) reported in Table 4 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 (Kang et al., 2020) 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 (Patel and others, 2025). 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 (d=0d=0), and Oracle-only delegates every record to the oracle (d=1.0d=1.0). 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 tP=tR∈[0.55,0.95]t_P=t_R∈[0.55,0.95]; SUPG sweeps tRt_R over the same range; and GAMCAL sweeps α∈[0.10,0.80]α∈[0.10,0.80] with no budget cap (ρ=1.0ρ=1.0), so that α alone controls the effective delegation rate. The SUPG variants use budget fraction ρ=0.1ρ=0.1 and failure probability δ=0.2δ=0.2; GAMCAL uses β=1β=1 (F1F_1 score) in the cost-quality objective. All quality metrics (F1F_1, precision, recall) are measured against oracle labels, following the convention established in Section 3. We also report delegation rate d. Error bars show mean ± standard deviation across seeds. 6.2. Cost-Quality Tradeoff Figure 5. F1F_1 vs. delegation rate for GAMCAL (sweeping α) and SUPG-IT (sweeping shared target tP=tRt_P=t_R) 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. 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 4 summarizes the best operating point per algorithm. Both algorithms exceed F1=0.99F_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. Learned calibration confers a clear advantage at low delegation budgets. Table 4 reports the best F1F_1 achievable within delegation caps of 20%20\% and 30%30\%. At d≤20%d≤ 20\%, GAMCAL leads on all six datasets, outperforming both SUPG-IT and SUPG-SP (the LOTUS cascade). The widest gap is on ArXiv: 0.8510.851 vs. 0.7840.784 for SUPG-SP and 0.7980.798 for SUPG-IT. On IMDB, the SUPG variants cannot operate within this budget at all because their minimum delegation includes both the ρ=10%ρ=10\% sampling budget and mandatory uncertain-region delegation. Raising the cap to d≤30%d≤ 30\% narrows the gap: GAMCAL still leads on five of six datasets, while SUPG-SP edges ahead on NYT (0.9770.977 vs. 0.9670.967) where GAMCAL’s delegation ceiling limits further gains. Table 4 examines the same tradeoff from the opposite direction. GAMCAL requires less delegation than SUPG-IT to reach a target F1F_1 on all six datasets for F1≥0.95F_1≥ 0.95 and on five for F1≥0.90F_1≥ 0.90. The advantage over SUPG-SP is larger still: on BoolQ, reaching F1≥0.95F_1≥ 0.95 costs d=29.3%d=29.3\% with GAMCAL versus 69.7%69.7\% with SUPG-SP—a 58%58\% reduction in oracle calls. On MMLU, the savings are 35%35\% (43.9%43.9\% vs. 67.4%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. Among individual datasets, NYT best illustrates GAMCAL’s cost advantage. It crosses F1≥0.90F_1≥ 0.90 at under 10%10\% delegation, the lowest threshold in the suite. SUPG-IT reaches a higher ceiling (F1=0.990F_1=0.990 at d=44%d=44\%) because the GAM classifies most NYT records confidently in this extreme-imbalance setting and caps delegation at roughly 20%20\% regardless of α. IMDB presents the hardest calibration challenge. The proxy scores F1=0.382F_1=0.382 alone, predicting nearly every review as positive. Both algorithms nevertheless recover to near-oracle quality (F1>0.98F_1>0.98) at high delegation. Both algorithms substantially outperform SUPG, which is limited to F1≤0.90F_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 F1F_1 on datasets with high false-positive rates (e.g., NYT). 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 F1F_1 ranges from 0.9720.972 (SST-2) to 0.9900.990 (NYT), far above SUPG’s ceiling of 0.2780.278–0.8990.899. Iterative refinement (the step from SUPG-SP to SUPG-IT) adds 1–2 F1F_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. In summary, the two proposed algorithms occupy complementary niches. GAMCAL achieves equal or higher F1F_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. 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 tP=tRt_P=t_R. 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. 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 by plotting each algorithm’s delegation rate against its native control parameter. 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α=0.5, IMDB receives 34%34\% delegation while NYT receives only 11%11\%. Even at α=0.8α=0.8, NYT’s delegation plateaus at roughly 20%20\%. The GAM classifies most records confidently in this extreme-imbalance join setting, and further delegation cannot improve quality. 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 tP=tR=0.80t_P=t_R=0.80, delegation ranges from 0.6%0.6\% on SST-2 to 60.6%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%1\% for targets up to 0.750.75 before rising to 24%24\% at tP=tR=0.90t_P=t_R=0.90. Delegation rises sharply only when the target exceeds what the proxy can achieve alone. 6.4. Target Reliability Section 6.3 examined GAMCAL’s parameter predictability. Here we evaluate whether SUPG-IT reliably delivers the joint precision-recall targets the user specifies. A 17×1717× 17 grid of target pairs (tP,tR)(t_P,t_R) from 0.550.55 to 0.950.95 in steps of 0.0250.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 highest-delegation datasets. 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 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, tP=tRt_P=t_R column). Reliability degrades primarily in asymmetric configurations at low delegation levels, precisely where the cascade adds the least value. Table 5. SUPG-IT target reliability across 289 (tP,tR)(t_P,t_R) pairs per dataset, 10 seeds each (2,890 runs). The tP=tRt_P=t_R column reports the 17 symmetric pairs only (170 runs). Satisfaction (%) Dataset All tP=tRt_P=t_R Failures Deleg. (%) ArXiv 100.0 100.0 0 41.4 IMDB 100.0 100.0 0 54.6 MMLU 99.4 100.0 16 23.6 BoolQ 98.7 99.4 38 14.4 SST-2 89.4 99.4 305 4.7 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 in LOTUS (Patel and others, 2025). GAMCAL achieves higher F1F_1 per oracle call at cost-sensitive operating points, requiring up to 58%58\% fewer oracle calls than LOTUS to reach F1≥0.95F_1≥ 0.95, while SUPG-IT reaches a higher quality ceiling with a mean peak F1F_1 of 0.9890.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. 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 (2006) Prediction, learning, and games. Cambridge University Press. Cited by: §5.5. [2] L. Chen, M. Zaharia, and J. Zou (2023) FrugalGPT: how to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.05176. Cited by: §1, §2. [3] Y. Chung, R. Desai, J. He, Y. Xiao, T. Hottelier, Y. Kom Samo, P. Kadilkar, X. Chen, S. Idicula, F. Özcan, A. Halevy, and Y. Papakonstantinou (2026) 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, Cited by: §2. [4] C. Clark, K. Lee, M. Chang, T. Kwiatkowski, M. Collins, and K. Toutanova (2019) 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, Cited by: §6.1. [5] A. Cohan, F. Dernoncourt, D. S. Kim, T. Bui, S. Kim, W. Chang, and N. Goharian (2018-06) 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), New Orleans, Louisiana, p. 615–621. External Links: Document Cited by: §6.1. [6] H. Dai, B. Y. Wang, X. Wan, B. Dai, S. Yang, A. Nova, P. Yin, P. M. Phothilimthana, C. Sutton, and D. Schuurmans (2024) UQE: a query engine for unstructured databases. In Advances in Neural Information Processing Systems, Cited by: §2. [7] C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger (2017) On calibration of modern neural networks. In International Conference on Machine Learning, Cited by: §1, §2, §5.1, §5.2. [8] T. Hastie and R. Tibshirani (1986) Generalized additive models. Statistical Science. Cited by: §2, §5.2. [9] D. Hendrycks, C. Burns, S. Basart, A. Zou, M. Mazeika, D. Song, and J. Steinhardt (2020-09) Measuring massive multitask language understanding. External Links: 2009.03300 Cited by: §6.1. [10] D. G. Horvitz and D. J. Thompson (1952) A generalization of sampling without replacement from a finite universe. Journal of the American Statistical Association 47 (260), p. 663–685. Cited by: §4.1, §5.6. [11] W. Jitkrittum, N. Gupta, A. K. Menon, H. Narasimhan, A. S. Rawat, and S. Kumar (2023) When does confidence-based cascade deferral suffice?. In Advances in Neural Information Processing Systems, Cited by: §2. [12] D. Kang, J. Emmons, F. Abuzaid, P. Bailis, and M. Zaharia (2017) NoScope: optimizing neural network queries over video at scale. In Proceedings of the VLDB Endowment, Vol. 10. Cited by: §2. [13] D. Kang, E. Gan, P. Bailis, T. Hashimoto, and M. Zaharia (2020) Approximate selection with guarantees using proxies. Proceedings of the VLDB Endowment 13 (11). Cited by: §1, §2, §3.1, §4.1, §4.2, §4.2, §4.3, §5.1, §6.1. [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 (2025) Cortex aisql: a production sql engine for unstructured data. Proceedings of the ACM on Management of Data. Cited by: §1, §1, §2, §3.1, §6.1. [15] C. Liu, M. Russo, M. Cafarella, L. Cao, P. B. Chen, Z. Chen, M. Franklin, T. Kraska, S. Madden, and G. Vitagliano (2025) Palimpzest: a declarative system for optimizing AI workloads. arXiv preprint arXiv:2405.14696. Cited by: §1, §2. [16] Y. Lu, A. Chowdhery, S. Kandula, and S. Chaudhuri (2018) Accelerating machine learning inference with probabilistic predicates. In Proceedings of the 2018 International Conference on Management of Data, Cited by: §2. [17] A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts (2011-06) Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Portland, Oregon, USA, p. 142–150. Cited by: §6.1. [18] J. Neyman (1934) 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), p. 558–625. Cited by: §4.1. [19] L. Nie, Z. Ding, E. Hu, C. Jermaine, and S. Chaudhuri (2024) Online cascade learning for efficient inference over streams. In International Conference on Machine Learning, Cited by: §1, §2. [20] A. Owen and Y. Zhou (2000) Safe and effective importance sampling. Journal of the American Statistical Association 95 (449), p. 135–143. Cited by: §4.1. [21] L. Patel et al. (2025) Semantic operators: a declarative model for rich, ai-based analytics over text data. arXiv preprint. Cited by: §1, §1, §1, §2, §6.1, §7. [22] J. C. Platt (1999) Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In Advances in Large Margin Classifiers, p. 61–74. Cited by: §2, §5.2. [23] D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, and Z. Wen (2018) A tutorial on thompson sampling. Foundations and Trends in Machine Learning 11 (1), p. 1–96. Cited by: §5.3, §5.3. [24] E. Sandhaus (2008) The new york times annotated corpus. Note: Linguistic Data Consortium, LDC2008T19 Cited by: §6.1. [25] D. Servén and C. Brummitt (2018) PyGAM: generalized additive models in python. Note: https://github.com/dswah/pyGAMZenodo. DOI: 10.5281/zenodo.1208723 Cited by: §A.1. [26] R. Socher, A. Perelygin, J. Wu, J. Chuang, C. D. Manning, A. Ng, and C. Potts (2013-10) Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, Seattle, Washington, USA, p. 1631–1642. Cited by: §6.1. [27] R. Storn and K. Price (1997) Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization 11 (4), p. 341–359. Cited by: §5.4. [28] W. R. Thompson (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25 (3/4), p. 285–294. Cited by: §5.3. [29] C. Wang, S. Augenstein, K. Rush, W. Jitkrittum, H. Narasimhan, A. S. Rawat, A. K. Menon, and A. Go (2024) Cascade-aware training of language models. In Advances in Neural Information Processing Systems, Cited by: §2. [30] L. Wasserman (2004) All of statistics: a concise course in statistical inference. Springer. Cited by: §4.2. [31] S. N. Wood (2017) Generalized additive models: an introduction with R. 2nd edition, Chapman and Hall/CRC. Cited by: §A.1, §A.1. [32] B. Zadrozny and C. Elkan (2002) Transforming classifier scores into accurate multiclass probability estimates. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, p. 694–699. Cited by: §2, §5.2. [33] M. J. Zellinger and M. Thomson (2024) Efficiently deploying LLMs with controlled risk. arXiv preprint arXiv:2410.02173. Cited by: §2. [34] M. J. Zellinger and M. Thomson (2025) Rational tuning of LLM cascades via probabilistic modeling. Transactions on Machine Learning Research. Cited by: §2. Appendix A 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. Constrained GAM with Analytical Confidence Intervals All experiments in Section 6 use this variant as the default calibration model. The implementation represents f as a cubic spline and fits the penalized log-likelihood (Eq. 25) subject to monotonicity constraints g′(s)≥0g (s)≥ 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]. The fitted model provides a posterior approximation via the Bayesian interpretation of penalized splines [31]. Concretely, the roughness penalty λ∫(f′)2sλ (f )^2\,ds corresponds to a Gaussian prior on the spline coefficients, and the penalized likelihood yields an approximate posterior. From this posterior, the mean f^(s) f(s) and standard error se(s)se(s) are extracted, and the stochastic calibrated score follows Eq. 26: (34) g~(s,q)=logit−1(f^(s)+Φ−1(q)⋅se(s)) g(s,q)=logit^-1\! ( f(s)+ ^-1(q)·se(s) ) A.2. Regularized Logistic Regression with Spline Basis 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. Raw proxy scores are first transformed to log-odds space ℓ=logit(A(x)) =logit(A(x)), clipped to [ℓmin,ℓmax][ _ , _ ] for numerical stability. A degree-3 B-spline basis with p uniformly spaced knots is constructed via scikit-learn’s SplineTransformer, yielding d basis functions ϕ1(ℓ),…,ϕd(ℓ) _1( ),…, _d( ). The calibration function is then: (35) f(s)=∑j=1dθjϕj(logit(s))f(s)= _j=1^d _j\, _j(logit(s)) and the coefficients θ are fit by minimizing the regularized negative log-likelihood: (36) minθ−∑i=1||[yilogg(A(xi))+(1−yi)log(1−g(A(xi)))]+λ2‖θ−μθ‖2 _θ\;- _i=1^|S| [y_i g(A(x_i))+(1-y_i) (1-g(A(x_i))) ]+ λ2\|θ- _θ\|^2 using L-BFGS-B optimization with analytically computed gradients. 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 μj=ℓmin+(ℓmax−ℓmin)⋅j/d _j= _ +( _ - _ )· j/d. 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 structure. The regularized variant thus interpolates between Platt scaling (few samples) and a flexible spline model (many samples). Confidence intervals are obtained via the Laplace approximation. At the fitted optimum θ θ, the Hessian of the regularized loss is: (37) H=X⊤diag(h^∘(1−h^))X+λIH=X diag( h (1- h))\,X+λ I where X is the spline design matrix and h^=σ(Xθ^) h=σ(X θ) are the fitted probabilities. The approximate posterior covariance is Σ=H−1 =H^-1, and the standard error of f(s)f(s) at a new point is se(s)=ϕ(s)⊤Σϕ(s)se(s)= φ(s) \,φ(s) where ϕ(s)φ(s) is the spline basis vector. The stochastic calibrated score is computed as in Eq. 26. 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 λ. A.3. Bootstrap Ensemble The bootstrap variant quantifies calibration uncertainty empirically rather than analytically. A primary GAM g is trained on the full oracle sample S as in Appendix A.1. Additionally, B bootstrap GAMs g1,…,gBg_1,…,g_B are trained on resamples 1∗,…,B∗S_1^*,…,S_B^* drawn with replacement from S (we use B=100B=100). Uncertainty is estimated from the ensemble spread in logit space. Let ℓ¯(s) (s) denote the mean bootstrap logit and Δb(s) _b(s) the deviation of the b-th ensemble member: (38) ℓ¯(s) (s) =1B∑b=1Blogit(gb(s)) = 1B _b=1^Blogit(g_b(s)) (39) Δb(s) _b(s) =logit(gb(s))−ℓ¯(s) =logit(g_b(s))- (s) The centered deviations Δb(s)b=1B\ _b(s)\_b=1^B form an empirical distribution of calibration uncertainty at score level s. The stochastic calibrated score is: (40) g~(s,q)=logit−1(logit(μ(s))+Qq(Δb(s)b=1B)) g(s,q)=logit^-1\! (logit(μ(s))+Q_q\! (\ _b(s)\_b=1^B ) ) where μ(s)=g(s)μ(s)=g(s) is the primary model’s prediction and QqQ_q denotes the q-th quantile of the empirical distribution. 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 B+1B+1 GAMs, and each calibration query requires B+1B+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. Figure 7. Joint target satisfaction rate for SUPG-IT across a 17×1717× 17 grid of (tP,tR)(t_P,t_R) 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. 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 fallback that prevents overfitting before sufficient data accumulates. The bootstrap (Appendix A.3) trades a roughly 100×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. Appendix B Extended Pareto Analysis Figure 8 extends the main Pareto analysis (Figure 5) from F1F_1 to all four quality metrics and from two algorithms to all four. SUPG’s curves are vertical lines at d=ρ=0.1d=ρ=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 tRt_R but the sample size does not, sweeping tRt_R 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 tRt_R increases, the threshold drops to accept more records, and precision degrades in proportion. On NYT (positive rate 0.9%0.9\%), precision falls from 0.170.17 to 0.030.03 across the sweep, producing F1F_1 below 0.060.06 at the highest recall targets. ArXiv and IMDB show the same pattern, with precision dropping below 0.150.15 and 0.250.25. Adding the upper threshold eliminates this failure mode: both SUPG-SP and SUPG-IT maintain precision above 0.990.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. 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 F1F_1 within a few percent of perfect on every dataset. Appendix 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 (tP≥0.75t_P≥ 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%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., tP=0.575t_P=0.575, tR=0.95t_R=0.95), where delegation drops below 1%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 11–8%8\%. The proxy alone nearly satisfies the targets in these regions, and the few oracle samples collected are insufficient for tight statistical bounds. Appendix D Robustness to Parallelism Both algorithms are designed for independent per-worker execution. Increasing the number of workers W (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 SUPG-IT at W∈1,2,4,8,16W∈\1,2,4,8,16\ on IMDB, MMLU, and SST-2 with batch size 40964096 and 10 seeds per configuration. Quality is robust to parallelism. The mean best F1F_1 across datasets varies by less than 0.0010.001 for GAMCAL and less than 0.0040.004 for SUPG-IT as W increases from 1 to 16. GAMCAL is the more stable of the two, with a maximum per-dataset shift of 0.0020.002 F1F_1. SUPG-IT shows a larger shift on SST-2 (+0.012+0.012 F1F_1 at W=16W=16), where fewer batches per worker leave thresholds less converged, widening the uncertain region and raising delegation from 41%41\% to 56%56\%. The additional oracle labels improve quality at higher cost. Seed-level variability does not increase with W: for both algorithms, the standard deviation of F1F_1 across seeds remains stable or decreases as partitions shrink. Figure 8. Complete Pareto grid: all four cascade algorithms (GAMCAL, SUPG-IT, SUPG-SP, SUPG) across six datasets and four metrics (F1F_1, accuracy, precision, recall). Dashed horizontal lines mark the proxy-only and oracle baselines.