When is a better LLM worth paying for? Stochastic Optimization with Switching Mixed-Fidelity Oracles

1 Introduction

• Choosing a model or prompt changes both the cost and statistical quality of data used in downstream decisions, so the paper asks when additional fidelity is worth paying for.Its oracle framework accounts for price, systematic bias, state-dependent variance, and residual variance near the optimum.Source: §1 · pp. 2, 4

1.1 Contributions.

• The known-bias framework selects the most cost-efficient admissible oracle at each optimization stage, while the unknown-bias framework uses budgeted trusted-gradient certification to eliminate unsuccessful sources.The paper analyzes biased stochastic gradient extrapolation and recursive regularization as concrete subroutines.Source: §1.1 · pp. 4–5
• The 10% missingness example switches from inexpensive Nano pipelines to Luna and an ensemble, skipping several costlier alternatives while reaching the same accuracy scale at about $72 versus $240.The reported reduction in cumulative cost is roughly 70%.Source: §1.1 · p. 5

1.2 Related work

• Unlike LLM routing that selects a model for each inference query, this paper selects stochastic-oracle sources according to downstream optimization progress.Related work also covers data curation, multi-fidelity optimization, and multilevel methods; the paper allows heterogeneous black-box oracles without requiring a nested fidelity hierarchy.Source: §1.2 · pp. 5–6

1.3 Notation and organization

• The paper uses x* for an optimal solution, Euclidean and spectral norms for vectors and matrices, and ⪯ for positive-semidefinite ordering.It organizes the remainder around LLM applications, known-bias switching, break-even prices, unknown-bias certification, and experiments.Source: §1.3 · pp. 6–7

2.1 LLM-generated noisy labels

• LLM, human, or hybrid label sources induce stochastic-gradient oracles whose systematic annotation error determines their bias.Under a fourth-moment assumption, the label-oracle variance satisfies the paper’s state-dependent noise condition; repeated annotations or trusted calibration data can help estimate its parameters.Source: §2.1 · pp. 7–8

2.2 LLM completion of missing covariates

• A model–prompt pipeline that reconstructs missing covariates produces a stochastic-gradient oracle for the downstream generalized linear model.Different completion pipelines induce different costs, bias levels, and state-dependent variance.Source: §2.2 · pp. 8–9
• In linear regression, completion quality affects both bias at the optimum and local curvature mismatch, while the resulting oracle also satisfies the state-dependent noise model.The bias bound includes completion bias and covariance mismatch; higher-quality completions can reduce both.Source: §2.2 · pp. 8–9

3 Known bias: cost-aware oracle-switching

• At every stage, the known-bias policy selects the lowest-cost oracle satisfying the bias-admissibility condition for the next contraction.The subroutine contract specifies the required contraction and its oracle-call complexity, allowing different optimization methods to serve as the inner procedure.Source: §3 · pp. 9–10
• For unbiased oracles, adaptive total cost is no greater than the cost of using the best fixed oracle throughout the stages.The comparison follows because the sum of stagewise minimum costs is no larger than the minimum over fixed-oracle summed costs.Source: §3 · p. 10, §3.2 · p. 12

3.1 Biased SGE: an efficient contraction subroutine

• Biased SGE extends stochastic gradient extrapolation to persistent gradient bias and strong convexity, providing a contraction subroutine under state-dependent noise.Its analysis controls both the changing variance and accumulated bias, and the subroutine is reused in recursive regularization.Source: §3.1 · pp. 10–11

3.2 Combining the oracle-switching meta-algorithm with the SGE subroutine

• For K stages, an example yields adaptive cost Θ(M log K) versus MK for the best fixed oracle, while the possible improvement over fixed choice is at most O(K/log K).The example’s first oracle is cheaper until the final m = ⌈log2 K⌉ stages; the upper bound is shown tight by the construction described in the paper.Source: §3.2 · p. 12
• Ignoring oracle cost, the resulting sample complexity matches the optimal complexity for stochastic optimization under state-dependent noise.The paper states that adaptive switching preserves this complexity structure while improving cost efficiency.Source: §3.2 · p. 13

• At radius R, the policy uses only oracles satisfying the accuracy admissibility test, then chooses the one with the lowest total stage cost.An oracle is price-competitive when its price is no greater than its stage break-even price, subject to admissibility.Source: §4 · pp. 13–14
• Bias determines whether an oracle can support the requested accuracy; cλDλ governs coarse-scale cost, while cλEλ/R2 governs fine-scale cost.An oracle attractive at a coarse scale can become infeasible as the target accuracy tightens.Source: §4 · p. 13
• At R = 200 all displayed pipelines except Nano simple-7 pass the bias test; at R = 100 Nano pipelines are removed, and at R = 80 only Avg. Haiku+Sonnet remains admissible.In this 10% missingness experiment, the thresholds are about 2.41 at R = 100 and 1.92 at R = 80; price cannot rescue an inadmissible oracle.Source: §4 · p. 13
• Claude Haiku 4.5 dominates Claude Sonnet 5 (Bλ: 2.01 vs. 2.37; cλσ2 λ,∗: 1.23 × 105 vs. 2.76 × 105; equal Lλ), so Sonnet 5 is never selected.A reduction in Sonnet 5’s cost or bias could make it non-dominated in this experiment.Source: §4 · p. 14
• Break-even prices depend on the state-dependent and residual-variance terms and the admissible competitor set; in mixed regimes they also vary explicitly with R.In the fine-scale example, Sonnet’s break-even price varies with hypothetical bias: $4.54 for B7 ∈ [1.86, 2.01), $1.41 for [2.01, 2.31), $0.82 for [2.31, 2.87), $0.20 for [2.87, 3.95), and $0.18 for B7 ≥ 3.95.Source: §4 · pp. 14–15
• At measured bias B7 = 2.37, Sonnet 5’s fine-scale break-even price is about $0.82, so its $3.158 price would need to fall by about 3.9× to become competitive.This calculation assumes Sonnet 5 and its cheapest admissible competitor are both residual-variance dominated.Source: §4 · p. 15

5 Unknown bias: budgeted trusted certification

• The analysis assumes exact trusted-gradient certification to isolate certification-frequency costs; constructing a stochastic certificate and jointly optimizing its precision, sample size, and frequency is left to future work.In applications, certificates may use a sufficiently large trusted sample, expert-reviewed observations, or repeated measurements.Source: §5 · p. 15

5.1 Budgeted sparse certification meta-algorithm

• Homogeneous blocks train with one oracle at a time, so a failed certification can be attributed to and eliminate that source while retaining any certified partial progress.The budget B sets the uncertified training expenditure before certification; the terminal projected-gradient step is used to certify the block.Source: §5.1 · pp. 17–18
• With at least one block-admissible oracle available until the target level, the algorithm reaches an ε-accurate certified point with probability at least 1−δ in O(K+ℓ) blocks.Each unsuccessful block removes one oracle, while a successful block or certified partial progress advances the certified level.Source: §5.1 · pp. 19–20
• For a moderate number of candidate oracles ℓ, certification uses eO(log(1/ϵ)) trusted-gradient evaluations, saving a factor of L/µ over trusted-gradient optimization up to logarithmic confidence factors.The comparison is with using the trusted first-order module alone for optimization.Source: §5.1 · p. 20

5.2 Recursive regularization with SGE: an efficient PG subroutine

• RR+SGE yields a directly certifiable projected-gradient guarantee at complexity eT_RR+SGE(R, λ) = eO(T_SGE(R, λ)), with only logarithmic-factor overhead over SGE.Its bias requirement is B_λ = O(µR/S), compared with O(µR) for SGE distance contraction.Source: §5.2 · pp. 21–22
• Recursive regularization reduces the projected-gradient guarantee to solving regularized subproblems accurately, which SGE handles across O(log(L/µ)) levels.The cited passages state that sufficiently accurate subproblem solutions imply a small projected-gradient mapping for the original objective and that the total complexity sums across S = O(log(L/µ)) levels.Source: §5.2 · pp. 22–23

5.3 How often should we certify? The training-certification cost tradeoff

• The comparison benchmark uses a more restrictive PG-admissible switching policy than the known-bias benchmark to remain compatible with certification; for RR+SGE, this strengthens the bias requirement only by a logarithmic factor.Terminal PG-admissibility also makes the corresponding homogeneous block admissible, so no additional block-validity assumption is needed.Source: §5.3 · p. 24
• An oracle may remain in use after its sufficient PG-admissibility condition fails because it can still pass later exact certificates, creating unavoidable identification overhead independent of B.Even with B = 0, the algorithm may use such an oracle until a later certification fails.Source: §5.3 · p. 25
• The budgeted-certification cost bound separates the switching benchmark, a B-independent identification overhead, and a budget-dependent cost for training before failed oracles are detected.The switching benchmark is tight up to ζ, while larger B permits more uncertified training before a failed oracle is detected.Source: §5.3 · pp. 25, 27
• The certification budget B creates a U-shaped cost tradeoff: small B raises certification costs, while large B raises the training cost before failed oracles are detected.At B = 0, certification follows every successful stage; at B = ∞, an inexpensive but biased oracle may be used until a final certificate detects failure. The bound balances an increasing ℓB term against a decreasing ccert CPG_sw/B term.Source: §5.3 · p. 27

6.1 Simulated experiments - regression with noisy labels

• At squared error around 10^-3, switching costs about 2.7 × 10^4, versus 7.0 × 10^4 for always using oracle 2 and 8.5 × 10^4 for always using oracle 1.The policy starts with inexpensive SO1, then switches to SO2 as residual variance becomes dominant.Source: §6.1 · p. 28, Figure 2 · p. 28

6.2 LLM-completion experiments - known bias

• At the finest displayed accuracy with 10% missingness, adaptive Algorithm 1 costs about $72 versus about $240 for always using SO8, a roughly 70% reduction.It skips several pipelines, including both stand-alone Claude models at the tightest stage.Source: §6.2 · p. 30, Figure 3 · p. 30
• At 20% missingness, the adaptive method uses only inexpensive Nano pipelines; at 40%, it switches from Nano LR-short-7 to Haiku and costs about $11.5 versus $30 for fixed SO6.The 40% comparison is at the finest displayed accuracy and represents about a 62% cost reduction.Source: §6.2 · p. 31, Figure 4 · p. 31

6.3 LLM-completion experiments - budgeted certification with unknown bias

• As certification budget B increases, certification cost falls, but beyond an intermediate range training cost rises because failed sources can consume more training before rejection.This is the training-versus-certification cost tradeoff shown for Algorithm 3.Source: §6.3 · p. 32, Figure 5 · p. 32
• For 10%, 20%, and 40% missingness, selected budgets are approximately B = 1.40, 1.64, and 2.24, each within a factor of two of its theory-inspired proxy.The corresponding proxies are approximately 2.81, 0.82, and 1.12; they identify the scale, not the exact empirical minimizer.Source: §6.3 · p. 32, Figure 5 · p. 32
• Near the finest scales, unsuccessful trials and higher-fidelity training make both stochastic-oracle training and trusted-certification costs increase more sharply.Figure 6 decomposes cumulative cost into those components alongside the known-bias benchmark.Source: §6.3 · p. 33, Figure 6 · p. 33
• The known-bias policy is more cost-efficient, while the unknown-bias method recovers the same qualitative coarse-to-fine fidelity pattern without bias parameters.At 10% missingness, trajectories remain relatively close until the finest stages; at 20% and 40%, the final switch entails more failed trials and certification cost.Source: §6.3 · p. 33, Figure 7 · p. 33
• The LLM regression experiments are a controlled setting chosen so the clean downstream objective and mixed-fidelity oracle parameters can be measured directly.Their stated purpose is not to claim that regression experiments exhaust LLM-assisted decision pipelines.Source: §6.3 · pp. 33–34

7 Concluding remarks

• A cheap source can be the right choice far from the solution, while higher fidelity is worth paying for only when it improves cost-efficient progress or lowers the attainable bias floor.Break-even prices link this decision to the value of information.Source: §7 · p. 34
• A task-specific oracle card could report benchmark accuracy, token price, bias, residual variance, and state-dependent variance to support stage-dependent willingness-to-pay estimates.The passage suggests repeated or trusted labels for labeling, and a held-out fully observed subset for data completion.Source: §7 · p. 34
• The mixed-fidelity framework also applies to human experts, crowd workers, sensors, simulators, laboratory measurements, and computational solvers.Future directions include online oracle-parameter learning and correlated errors across data sources.Source: §7 · p. 34
• The LLM analysis abstracts away fixed setup costs, finite-sample certification, and approximate fidelity estimates; Section 6's normalization and admissibility rules isolate switching rather than model every API deployment feature.Jointly learning oracle quality, acquisition cost, and certification uncertainty is left for future work.Source: §7 · p. 34

A Proofs in Section 3

• The section provides full proofs of the main results in Section 3.Source: A Proofs in Section 3 · p. 39

A.1 Proof of Theorem 1

• The SGE recursion is used to handle state-dependent variance and persistent bias in the proof of Theorem 1.The proof incorporates a persistent bias term and strongly convex regularization in Algorithm 2.Source: §A.1 · p. 39
• The recursion defines the mean oracle output as g(x), its bias as b(x)=g(x)−∇f(x), and its centered noise as δ_t(x)=G_t(x)−g(x).Source: §A.1 · p. 39
• The proof's parameter choices satisfy Proposition 4, and the resulting key condition absorbs state-dependent variance into telescoping function-value terms.Source: §A.1 · p. 39
• The proof takes expectations in the recursion, bounds the bias using ∥b(x_t)∥≤B, and uses the martingale property E[δ_t(x_j)]=0 for j≤t.Source: §A.1 · p. 40
• The proof substitutes the explicit parameter choices into its recursion, drops a nonnegative terminal term, and rearranges the resulting bounds to establish the theorem's inequalities.Source: §A.1 · pp. 40–41

A.1.1 Proof of Proposition 4

• The proof uses smoothness of f to obtain an inequality relating function values and gradient differences between successive iterates.Source: §A.1.1 · p. 41
• The update identity and the optimality condition of Algorithm 2's Step 3 combine to bound the iterate and auxiliary-sequence terms.Source: §A.1.1 · pp. 41–42
• Taking a θ_t-weighted sum and applying the parameter relations yields a telescoping inequality, which completes the recursion proof after substitution and expectation.Source: §A.1.1 · pp. 42–44

A.2 Proof of Corollary 1

• Cost_adap(ϵ) ≤ Cost_fixed(ϵ) for every instance.The adaptive cost is compared with the best fixed-oracle cost.Source: §A.2 · p. 44
• The adaptive rule uses SO1 in early stages and switches to SO2 for the final m = Θ(log K) stages.The switch occurs m stages before termination.Source: §A.2 · p. 45
• The order cannot be improved beyond O(K/log K), because stage minima are nondecreasing and the adaptive policy pays at least (m + 1)d_{K−m} over the final stages.An oracle minimizing cost at stage K−m costs at most O(Kd_{K−m}) over all K stages.Source: §A.2 · p. 46
• The two-oracle construction shows that the Θ(K/log K) savings factor is tight up to constants.The lower-bound argument applies to arbitrary stage costs Cλ(s) = max{Aλ, Bλ2^s−1}.Source: §A.2 · p. 46

B Proofs in Section 5

• The appendix section collects proofs for results in Section 5.The supplied proof passage identifies Lemma 1 as one such result.Source: B Proofs in Section 5 · p. 46, §B.1 · p. 46

B.1 Proof of Lemma 1

• The proof of Lemma 1 combines projection optimality and the definition of G_{X,γ}(x) to derive an inequality.It then invokes μ-strong convexity, L-smoothness, y = x*, and γ ≤ 2/L.Source: §B.1 · pp. 46–47
• Dividing by ∥x − x*∥ establishes the first claim, while the second follows immediately.Source: §B.1 · p. 47

• The proof uses the deterministic quadratic regularization to establish a bias claim, while the stochastic error itself remains unchanged.Source: §B.2 · p. 47
• The state-dependent variance term is rewritten for the regularized objective and iterated before being substituted into the original variance condition.The argument then sums the resulting inequality over i = 1 to j and takes expectations.Source: §B.2 · pp. 47–48

B.3 Proof of Proposition 3

• Strong convexity of ϕ_{j−1} is used to control the displacement of minimizers induced by regularizers.Source: §B.3 · p. 48
• The proof combines inequalities across stages with projection nonexpansiveness and a projected-gradient descent inequality using γ = 1/(2L).The stated step size is valid because the accumulated regularization is bounded by 2L.Source: §B.3 · pp. 48–49

C Prompt templates for the LLM-completion experiments

• The experiment appendix defines three prompt templates: simple imputation, short low-rank, and detailed low-rank.The LR-short and LR names refer to the short and detailed low-rank prompts; suffixes -7 and -10 indicate the number of input features.Source: C Prompt templates for the… · pp. 49–50
• The simple-imputation prompt uses median-like choices for continuous scores and mode-like choices for discrete indicators, while preserving observed values.Source: C Prompt templates for the… · p. 50
• The detailed low-rank prompt assumes approximately low-rank data and asks for imputations aligned with a few latent factors.Source: C Prompt templates for the… · p. 50