acceptodds
Desk rejected at ICLR 2027

Certifying LLM Serving Updates with Cost-Optimal Evaluation

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

When an LLM serving pool changes, an operator must decide whether to retain an incumbent, replace it with a candidate, or combine them in a cascade. Evaluating all models on common queries can itself be costly. We formulate this pre-deployment decision as fixed-confidence identification with costly evaluation actions, separating the serving configuration to be selected from the observations used to select it. The characteristic certification cost quantifies the minimum cost of distinguishing the true environment from alternatives that change the optimal serving decision. It yields an instance-dependent lower bound, which our TRACK-AND-CERTIFY procedure asymptotically attains as under finite-class, stationary, identifiable observation models with known costs and a unique true optimum. For LLM serving, replacement depends on marginal performance, whereas a cascade triggered by verified incumbent failure also depends on same-query rescue behavior. Controlled replay across 11 model pools shows that richer multi-candidate feedback reduces certification cost only on selected pools, and that the characteristic-cost ratio strongly predicts this realized benefit. Decision-aware singleton allocation reduces median certification cost by relative to uniform singleton evaluation. These results motivate designing model evaluations around the serving decision they must resolve.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models, Sequential Decision Making

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_SRnXOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper studies cost-optimal evaluation for certifying updates to LLM serving configurations. It formulates the problem as fixed-confidence decision identification with heterogeneous evaluation costs, introduces an instance-dependent characteristic certification cost, and proposes the method `Track-and-Certify'. The paper establishes an information-theoretic lower bound and proves first-order asymptotic optimality under finite, stationary, identifiable observation models. Experiments with frozen LLM model pools demonstrate substantial savings from adaptive evaluation allocation.

Critical strengths
  • The problem of minimizing pre-deployment evaluation costs is interesting and practically relevant and distinct from optimizing inference-time routing.

  • The characteristic certification cost provides a useful interpretation of when richer same-query feedback is economically beneficial.

Critical weaknesses

Please state the theory contribution beyond prior controlled sensing results. For a nonempty alternative set with a finite characteristic cost, the cost program can be written as

=\max_{v\in\Delta(\mathcal Z)} \min_{\lambda\in\operatorname{Alt}(\theta)} \sum_z\frac{v_z}{h_z}d_z(\theta,\lambda),$$ where $v$ is the share of cost assigned to each action. A closely related reference missing from the manuscript is Nitinawarat and Veeravalli (2015) [R1]. It treats non-uniform control costs and gives an asymptotically optimal expected-cost test. Its memoryless case gives the same information-per-cost form when all other hypotheses must be ruled out. This is a separate work from Nitinawarat et al. (2013), which the manuscript already cites. Composite controlled sensing also excludes parameters in the same correct hypothesis; see Deshmukh et al., cited by the paper, and Lemma 1 and Theorems 1–3 in its [public preprint](https://arxiv.org/abs/1910.12697v1). Another relevant reference not listed in the manuscript is Degenne and Koolen (2019) [R2]. Section 2 defines the alternatives to an answer as the models where that answer is incorrect, which is the same form as Equation (7). Their treatment of multiple correct answers also gives useful context for the role of your unique-true-optimum assumption. The models and answer assumptions in these references differ from yours, so the comparison should state both the shared ideas and the new results. The paper already credits controlled sensing and Track-and-Stop. Please make the remaining new work precise: the decision-changing alternative set, ties and multiple correct configurations, the finite-model certifier, and the LLM observation design. Cost weighting and the tracking-and-stopping structure alone do not establish a new general theory. For the LLM related-work discussion, like RACER (Hao et al., 2026) [R3], relevant works are missing from the reference list. For example, RACER calibrates model sets with abstention and controls their expected miss risk under exchangeability; its guarantee averages over the calibration data and a new query. These works optimize model-set size or annotation cost, while this paper optimizes the evaluation cost of identifying a serving configuration. A short comparison in Section 2 would help clarify these different cost objectives and risk guarantees. [Reference] - **[R1]** S. Nitinawarat and V. V. Veeravalli. “Controlled Sensing for Sequential Multihypothesis Testing with Controlled Markovian Observations and Non-Uniform Control Cost.” *Sequential Analysis*, **34**(1):1–24, 2015. [DOI: 10.1080/07474946.2014.961864](https://doi.org/10.1080/07474946.2014.961864). [Open preprint](https://arxiv.org/abs/1310.1844v2). - **[R2]** Rémy Degenne and Wouter M. Koolen. “Pure Exploration with Multiple Correct Answers.” *Advances in Neural Information Processing Systems*, **32**, 2019. [Official proceedings and paper](https://proceedings.neurips.cc/paper_files/paper/2019/hash/60cb558c40e4f18479664069d9642d5a-Abstract.html). - **[R3]** S. Hao, H. Zeng, H. Wei, and B. Jing. “RACER: Risk-Aware Calibrated Efficient Routing for Large Language Models.” ICML 2026.
Questions for authors

See Weaknesses. And:

  1. The proposed framework assumes a pre-specified quality–cost trade-off parameter η\eta, but provides limited guidance on how this parameter should be selected in practical LLM serving systems. This is an important omission because η\eta directly determines the optimal serving configuration, the set of decision-changing alternatives, and consequently the characteristic certification cost. So, I have three questions:

    1. How should practitioners choose η\eta based on operational budgets or quality requirements?
    2. How sensitive are the optimal serving decisions and certification costs to changes in η\eta, particularly near decision boundaries?
    3. Can the framework be extended to certify optimal serving configurations uniformly over a range of η\eta values, rather than requiring a single pre-specified trade-off parameter?

    A sensitivity analysis over η\eta, including the corresponding changes in optimal configurations and certification costs, would substantially improve the practical relevance of the proposed framework.

  2. And in Appendix C.2, the stated adaptive Hellinger bound appears to have an unconditional expectation on the left but a random action count on the right. Could the authors provide a rigorous deterministic bound that accounts for adaptive sampling, and clarify how it yields the claimed tail bound for the MLE stabilization time?

8 comments
AuthorsOpenReview ↗

Response to Reviewer SRnX — Part 1/4

Theory contribution relative to controlled sensing and pure exploration

We thank the reviewer for the expert and constructive review and for the precise pointers. We agree with the main point. Viewed as general results, our lower bound and Track-and-Certify instantiate known machinery going back to Chernoff (1959), and the submission did not say so clearly enough. The revision adds a short paragraph to Sec. 2 ("Relation to controlled sensing") and a detailed mapping in App. B.1 with a comparison table (Table B.2). It also adds the cited references (Nitinawarat & Veeravalli 2015, Degenne & Koolen 2019, Chernoff 1959).

Shared or adapted (now stated explicitly).

  • Characteristic program. In cost shares v∈Δ(Z)v\in\Delta(\mathcal Z), program (8) is exactly the reviewer's form, C⋆(θ)−1=max⁡vmin⁡λ∈Alt(θ)∑z(vz/hz) dz(θ,λ)C^\star(\theta)^{-1}=\max_v\min_{\lambda\in\mathrm{Alt}(\theta)}\sum_z (v_z/h_z)\,d_z(\theta,\lambda). It is the memoryless case of the information-per-cost rate of N&V (2015), whose GLR-type test has the same threshold form as ours and is asymptotically optimal in expected cost (their Thm 5.1).
  • Alternative set. Excluding only environments with a different answer (Eq. 7) is the composite-hypothesis construction of Deshmukh et al. (2021) and the answer-based alternative set of Degenne & Koolen (2019).
  • Theorems 1–2 and Corollary 1. Theorem 1 uses the change-of-measure argument of Kaufmann et al. (2016). Theorem 2 adapts GLR stopping with tracking and forced exploration (Garivier & Kaufmann 2016; Deshmukh et al.) to a finite class partitioned by answers, under heterogeneous costs. Corollary 1 is a simple conditioning argument.
  • Our claim. We no longer present these as a new general theory.

What we claim as new.

  1. The formulation and LLM observation design. The answer is a serving configuration, and each action runs a subset of models on the same query. Observations are therefore projections of one joint outcome law, and actions are distinct from answers.
  2. The structure this induces (Sec. 3.2, 4.3).
    • Singleton actions already identify every keep/replace/cascade utility.
    • Multi-candidate actions therefore change only information efficiency (Eq. 10).
    • Cascade certification is governed by the incumbent-failure and rescue rates, with C⋆=h/(ρ kl(q,c))C^\star=h/(\rho\,\mathrm{kl}(q,c)) (Eq. 11).
  3. The empirical finding. The characteristic-cost ratio predicts when multi-candidate evaluation pays off: Spearman 0.88 across 11 pools, transferring to a held-out task.

Ties and multiple correct configurations (new App. C.4, referenced right after Theorem 2).

  • Correctness. δ\delta-correctness does not use uniqueness (App. C.1, which now also covers the early return when Alt(θ^)=∅\mathrm{Alt}(\hat\theta)=\varnothing). App. A.1 defines Alt(ϑ)\mathrm{Alt}(\vartheta) through the selector π∘\pi^\circ for every estimate.
  • Cost with ties. Uniqueness enters only the lower bound and the optimality constant. With ties, the analysis gives an asymptotic cost at most the characteristic cost of certifying π∘(θ)\pi^\circ(\theta).
  • Choice of selector. In a finite class the MLE settles exactly. Choosing π∘(θ)\pi^\circ(\theta) to minimize this cost over Π⋆(θ)\Pi^\star(\theta) therefore attains the cheapest correct configuration, which Degenne & Koolen characterize for multiple correct answers and attain with sticky Track-and-Stop.
  • Open question. A matching lower bound in our setting is left open. In all 11 replay pools the true optimum is unique.

We hope this makes the scope precise, and we are glad to adjust the wording if any item still reads as overstated.

AuthorsOpenReview ↗

Response to Reviewer SRnX — Part 2/4

The Hellinger step in Appendix C.2 (Question 2)

Thank you for catching this. The reviewer is right: as written, the left-hand side is a deterministic expectation while rz(θ,λ)Nz(t)r_z(\theta,\lambda)^{N_z(t)} is random, so the displayed inequality is not well-posed under adaptive sampling. The conclusion (Eq. 20 in the revision, Pθ(Tθ>t)≤Ce−ct\mathbb P_\theta(T_\theta>t)\le Ce^{-c\sqrt t}) is unchanged. We have replaced the step with the following argument, now in revised Appendix C.2.

Martingale. For a false λ\lambda, let rz=∑opθz(o)pλz(o)∈(0,1]r_z=\sum_o\sqrt{p^z_\theta(o)p^z_\lambda(o)}\in(0,1]. This is positive by uniform common support and equals 1 iff Pθz=PλzP^z_\theta=P^z_\lambda. Define Wtλ=exp⁡(ℓt(λ)−ℓt(θ)2)∏s≤trZs−1.W_t^\lambda=\exp\Big(\tfrac{\ell_t(\lambda)-\ell_t(\theta)}{2}\Big)\prod_{s\le t} r_{Z_s}^{-1}. Since ZsZ_s is Fs−1\mathcal F_{s-1}-measurable and Os∣Fs−1,Zs=z∼PθzO_s\mid\mathcal F_{s-1},Z_s=z\sim P^z_\theta, we have Eθ[exp⁡(12log⁡pλZspθZs(Os))∣Fs−1]=rZs\mathbb E_\theta[\exp(\frac12\log\frac{p_\lambda^{Z_s}}{p_\theta^{Z_s}}(O_s))\mid\mathcal F_{s-1}]=r_{Z_s}. Hence WtλW_t^\lambda is a nonnegative martingale with EθWtλ=1\mathbb E_\theta W_t^\lambda=1.

Deterministic bound. By global identifiability, choose zλz_\lambda with rˉλ=rzλ<1\bar r_\lambda=r_{z_\lambda}<1. All affinities are at most 1, and the forced-exploration rule gives the deterministic coverage Nz(t)≥cKt−CKN_{z}(t)\ge c_K\sqrt t-C_K (Eq. 18). So on every sample path, ∏s≤trZs≤rˉλNzλ(t)≤rˉλ(cKt−CK)+\prod_{s\le t}r_{Z_s}\le \bar r_\lambda^{N_{z_\lambda}(t)}\le \bar r_\lambda^{(c_K\sqrt t-C_K)_+}. Therefore Eθ e(ℓt(λ)−ℓt(θ))/2=Eθ[Wtλ∏s≤trZs]≤rˉλ(cKt−CK)+,\mathbb E_\theta\, e^{(\ell_t(\lambda)-\ell_t(\theta))/2}=\mathbb E_\theta\Big[W_t^\lambda\textstyle\prod_{s\le t}r_{Z_s}\Big]\le \bar r_\lambda^{(c_K\sqrt t-C_K)_+}, which is deterministic.

Tail of the stabilization time. Let Tθ=sup⁡{t:θ^t≠θ}T_\theta=\sup\{t:\hat\theta_t\neq\theta\}. If Tθ>tT_\theta>t, then ℓs(λ)≥ℓs(θ)\ell_s(\lambda)\ge\ell_s(\theta) for some λ≠θ\lambda\neq\theta and some s>ts>t; this covers any tie-breaking rule. By Markov's inequality and a union bound over the finitely many λ\lambda and over s>ts>t, with a=cKmin⁡λlog⁡(1/rˉλ)>0a=c_K\min_\lambda\log(1/\bar r_\lambda)>0, for t≥(CK/cK)2t\ge(C_K/c_K)^2: Pθ(Tθ>t)≤(∣Θ∣−1)eaCK/cK∫t∞e−au du=(∣Θ∣−1)eaCK/cK2(1+at)a2e−at≤Ce−ct.\mathbb P_\theta(T_\theta>t)\le(|\Theta|-1)e^{aC_K/c_K}\int_t^\infty e^{-a\sqrt u}\,du=(|\Theta|-1)e^{aC_K/c_K}\frac{2(1+a\sqrt t)}{a^2}e^{-a\sqrt t}\le Ce^{-c\sqrt t}. Appendix C.3 uses only Eq. 20 and is otherwise unchanged. While revising C.2–C.3 we also tightened four details:

  • We prove the coverage bound (Eq. 18) explicitly. It holds deterministically with cK=1/Kc_K=1/K and CK=1+1/KC_K=1+1/K, and the number of forced rounds satisfies F(t)≤t+KF(t)\le\sqrt t+K, whichever underfilled action is chosen.
  • We state that TθT_\theta and every τδ\tau_\delta are read off a single never-stopped process.
  • We cover small tt with the constant CC.
  • We add the one-line argument that τδ→∞\tau_\delta\to\infty.
AuthorsOpenReview ↗

Response to Reviewer SRnX — Part 3/4

The trade-off parameter η\eta (Question 1)

(1.1) How to choose η\eta. The utility prices serving cost in units of correct answers, so 1/η1/\eta is the value of one additional correct answer. There are three practical routes, now described in a new Appendix D.10:

  • Value-based: set η=1/V\eta=1/V if a correct response is worth VV dollars.
  • Budget-based: treat η\eta as the Lagrange multiplier of a per-query serving budget. Utilities are linear in η\eta, so the optimal configuration is piecewise constant in η\eta; take the smallest η\eta whose optimum meets the budget.
  • Quality-based: take the largest η\eta whose optimum meets a minimum accuracy.

The budget-based and quality-based routes recover only the configurations on the upper concave hull (Pareto frontier) of (cost, accuracy) points. Because they depend on unknown accuracies, η\eta should be fixed from independent historical data, as for the evaluation family in Cor. 1. We note both points explicitly.

(1.2) Sensitivity. We varied η\eta over a threefold range (s∈[0.25,0.75]s\in[0.25,0.75], η=s/m\eta=s/m) for all 11 pools, holding Θ\Theta, the evaluation costs, and δ\delta fixed (new App. D.10, Fig. D.9).

  • Every utility is linear in η\eta, so optimal sets and C⋆C^\star are piecewise constant. There are 89 breakpoints, giving 100 constant intervals; we recomputed all 6,010 characteristic programs independently.
  • Decisions. The true optimal configuration changes in only one pool (M2, at s≈0.474s\approx0.474).
  • Family rule. R=CS⋆/CA⋆R=C^\star_S/C^\star_A moves with η\eta even when the decision does not. The R≥1.25R\ge1.25 family rule is unchanged in 10 of 11 pools. For five of these the result is trivial, because R=1R=1 or both costs vanish. M10 crosses the threshold.
  • Replay at shifted η\eta (4 pools, 11 operating points, 2 families × 100 seeds; new Table D.8).
    • With Algorithm 1's stopping statistic, no run reached the horizon and 2 of 2,200 were wrong, consistent with δ=0.01\delta=0.01.
    • Realized cost is 0.98–1.26× the first-order prediction C⋆βδC^\star\beta_\delta unless C⋆C^\star is tiny.
    • Moving η\eta can also make certification cheaper, because it can remove decision-changing environments from a fixed finite class.
    • Table D.8 also reports our original replay statistic, which tests against all other environments. It coincides with Algorithm 1's on every main experiment (App. D.1) but is overly conservative at shifted η\eta.

(1.3) Certifying uniformly over [η1,η2][\eta_1,\eta_2]. Yes, under one additional assumption: under each environment, no two configurations have identical utility lines in η\eta.

  • The answer. Utilities are linear in η\eta, so each environment induces a piecewise-constant map η↦π⋆(η)\eta\mapsto\pi^\star(\eta) with finitely many breakpoints. Take this map, up to its breakpoints, as the object to certify. It is unique under the assumption, and since Θ\Theta is finite there are finitely many such answers.
  • The alternative set. It is the set of environments whose optimal configuration differs from the truth's on a subset of [η1,η2][\eta_1,\eta_2] of positive length. Using this set, rather than a union of the fixed-η\eta sets, avoids the truth's own breakpoints, where those sets depend on the tie-breaking selector.
  • The theory. Theorem 1, Algorithm 1, and Theorem 2 then carry over, because their proofs use only a finite answer set and the alternative-set definition.
  • The cost. C[η1,η2]⋆≥sup⁡ηCη⋆C^\star_{[\eta_1,\eta_2]}\ge\sup_\eta C^\star_\eta, with the supremum over η\eta that are not the truth's breakpoints. So uniform certification is at least as costly as certifying the hardest single η\eta.
  • When the cost is finite. It is finite only because Θ\Theta is finite. If the interval contains a true breakpoint, a richer class would make it diverge (Eq. 11), so a practical variant excludes ϵ\epsilon-neighbourhoods of breakpoints.
  • Fixed-η\eta repetition. Repeating fixed-η\eta certification at several values does not give this simultaneous guarantee.

This is stated as a remark in App. D.10 and is not evaluated empirically.

Reviewer_ZJrnOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how to allocate costly evaluations before deciding whether to retain an incumbent LLM, replace it with a candidate, or deploy a verifier-triggered cascade. It separates serving configurations from evaluation actions and defines a characteristic certification cost through information constraints against decision-changing alternatives. Track-and-Certify provides fixed-confidence correctness and asymptotic cost optimality under finite-class assumptions. Controlled replay on 11 model pools demonstrates savings over uniform allocation and shows that richer feedback is beneficial only in some regimes.

Critical strengths
  1. A clear formulation with a coherent theoretical treatment. Separating the deployment decision from the evaluations purchased to make that decision gives a clear account of how the evaluation budget should be allocated. The characteristic cost, lower bound, and asymptotic achievability result form a coherent framework under the stated assumptions.

  2. Evidence of evaluation cost savings, with substantial supporting checks. The replay experiments demonstrate savings over uniform allocation. Section 6.4 and Appendix D also examine harder alternatives, construction sensitivity, limited calibration data, and held-out-task family selection. These checks strengthen the evidence that the value of richer feedback depends on the evaluation setting.

Critical weaknesses
  1. Certification reliability under model misspecification remains an application limitation. The correctness guarantee assumes that the true environment belongs to the specified finite class with known observation models. Section 6.4 and Appendix D provide useful robustness checks, but the calibration study mainly measures agreement with the full-data reference, and the held-out-task study evaluates family selection. These do not establish that the nominal error guarantee is retained when a historically estimated model omits the true outcome distribution. This matters when transferring the method from controlled replay to empirical serving data; it does not contradict the theorem under its stated assumptions.

  2. The finite-sample comparative evidence is mainly against uniform allocation. The main comparisons isolate the effects of adaptive allocation and feedback choice within a common certification framework. They support the reported savings, but leave the practical cost advantage over other adaptive allocation rules unresolved. This is a gap in empirical positioning, rather than a challenge to the asymptotic optimality result.

Questions for authors
  1. Could the authors distinguish which existing robustness checks test evaluation-family selection and which, if any, test the error rate of the final certification decision under a misspecified observation model? A narrowly scoped empirical check or an explicit statement of this remaining boundary would help assess practical use.

  2. Is a comparison with another adaptive allocation rule available under the same observation model, stopping rule, and evaluation costs? If not, a discussion of an appropriate comparator and the limits of the current empirical comparison would help.

4 comments
AuthorsOpenReview ↗

Response to Reviewer ZJrn — Part 1/2

Misspecification (Weakness 1, Question 1)

We thank the reviewer for the careful and positive assessment, and for two precise questions that helped us sharpen the paper's scope.

Which checks test what. The reviewer is right that none of the original robustness checks directly measures the error rate of the final certification when the truth lies outside Θ\Theta. We now say so explicitly and have added a study that does (new App. D.11).

CheckWhereTruth in Θ\Theta?What it measuresError rate under misspecification?
Continuous hardest alternativesSec. 6.4, App. D.5n/a (geometry)C⋆C^\star and family choice over all 64-state lawsNo
Adversarially augmented replayApp. D.5yescost and error with an enlarged classNo
Finite-Θ\Theta construction perturbationsApp. D.6yesstability of the cost ratio and the family choiceNo
Calibration-data requirementApp. D.7n/aagreement of the rebuilt class with the full-data family and decisionIndirectly (see below)
Held-out-task family selectionApp. D.8yeswhich evaluation family is cheaper on a new taskNo
Misspecification study (new)App. D.11noerror rate of the final certificationYes

How D.7 bears on the question. D.7 is the closest earlier evidence. When the class is rebuilt from 512 historical prompts, its optimal configuration disagrees with the full-data reference in 3.6% of replicates; with 32 prompts, the disagreement is 31%. A certifier working with such a class would target the wrong decision at least that often, which already exceeds δ=0.01\delta=0.01.

The new study (App. D.11).

  • Design.
    • The setting is four pools (M1, M2, M8, M10), with 1,000 seeds per condition (24,000 runs).
    • The replay truth is Q=(1−ϵ)P0+ϵRQ=(1-\epsilon)P_0+\epsilon R, where RR is the nearest decision-changing alternative in Θ\Theta.
    • Everything else is frozen: the certifier, Θ\Theta, and δ=0.01\delta=0.01.
  • Results.
    • With the truth in the class (ϵ=0\epsilon=0), the error rate is 0–0.4%.
    • At a truth outside the class that keeps P0P_0's optimal configuration, 39–51% of runs certify a wrong configuration, in every pool and family. In three of these conditions, a further 9–14% of runs reach the horizon; error rates count wrong certifications over all runs.
  • Caveat. This point is adversarial. Because RR lies just past the decision boundary (ϵ⋆≈0.97\epsilon^\star\approx0.97–1.001.00), the truth there is nearly an equal mixture of P0P_0 and RR.
  • Error curve (new, pre-registered). To trace how error grows, we ran the same paths at ϵ/ϵ⋆∈{0.10,0.25,0.50,0.75}\epsilon/\epsilon^\star\in\{0.10, 0.25, 0.50, 0.75\}, all of which keep P0P_0's optimal configuration. We used 1,000 seeds per point (32,000 runs). The 0.50 point reproduces the study above exactly. Results are in App. D.11, Fig. D.10.
    • The error rises monotonically in all eight pool–family cells: 0.3–2.1% at 0.10, 2.7–7.9% at 0.25 (every Clopper–Pearson lower bound above δ\delta), 39–51% at 0.50, and 86–98% at 0.75.
    • For three pools, the 0.25 truth is only 0.001–0.004 from P0P_0 in total variation. The nominal guarantee therefore fails under small misspecification in the direction of a decision-changing alternative.
  • Mechanism. The certifier must explain off-class data by some member of Θ\Theta, and the best-fitting member can carry a different answer.

Boundary. Sec. 7 now states that the guarantee requires the class to contain the truth and can fail badly when it does not, with the numbers above in App. D.11. App. D.11 adds that robustness would require classes that also cover decision-preserving neighbours of P0P_0, or composite stopping rules. Enlarging only the decision-changing side does not address this failure. We agree with the reviewer that this is an application limitation rather than a contradiction of the theorem.

AuthorsOpenReview ↗

Response to Reviewer ZJrn — Part 2/2

Comparison with other adaptive allocation rules (Weakness 2, Question 2)

Yes; we have added this comparison (new App. D.12 with Table D.9, and one sentence in Sec. 6.2). We replay all 11 pools with three further rules. All share Track-and-Certify's likelihood model, alternative sets, GLR stopping rule and threshold, evaluation costs, δ=0.01\delta=0.01, and seeds.

  • Greedy-Info plays the single action with the largest worst-case information per unit cost at the current estimate.
  • Greedy-Alt targets the most likely decision-changing alternative and plays the action most informative against it per unit cost.
  • Oracle-Static knows the true environment and samples at its optimal mix without forced exploration. It is a non-implementable reference, and its gap reflects both oracle knowledge and the absence of forced exploration.

Greedy-Info and Greedy-Alt use the same forced-exploration schedule as Track-and-Certify.

Policy / Track-and-Certify (same family)Median pool ratioRangeWrong / censored (of 1,100)
Greedy-Info, singletons1.00[0.99, 1.46]1 / 0
Greedy-Info, all actions1.00[0.99, 1.07]1 / 0
Greedy-Alt, singletons1.00[0.99, 1.22]1 / 0
Greedy-Alt, all actions1.00[0.83, 1.17]2 / 0
Oracle-Static, singletons0.68[0.09, 1.01]2 / 0
Oracle-Static, all actions0.58[0.03, 0.95]2 / 0

Ratios above one favor Track-and-Certify.

At δ=0.01\delta=0.01.

  • Medians. Both heuristics match Track-and-Certify's median cost, including on the six non-trivial pools (medians 1.00–1.01). The savings over uniform allocation therefore come mainly from decision-aware adaptivity, which all three adaptive rules share, rather than from the specific tracking rule. Sec. 6.2 now says so.
  • Pool-level differences. These go both ways. Track-and-Certify is cheaper by 1.46× against Greedy-Info-S on M9, by 1.22× against Greedy-Alt-S on M7, and by 1.17× against Greedy-Alt-All on M9. Greedy-Alt-All costs 0.83× as much as Track-and-Certify on M7.
  • Oracle-Static. It gains most on the five easy pools, where forced exploration accounts for 70–100% of Track-and-Certify's cost. Elsewhere it costs 0.58–1.01× as much.

Why there is little separation, and where theory predicts some.

  • Why the costs tie at δ=0.01\delta=0.01. Two effects explain it.
    • Forced exploration and transient costs are shared by all non-oracle rules.
    • Asymptotically, a single-action greedy rule is already optimal whenever the characteristic design uses one action, which holds for 18 of the 22 pool–family combinations.
  • Where we expect a gap. Where the design mixes actions, theory predicts a gap. To test this we ran a pre-registered δ\delta-scaling study (δ=10−2,…,10−8\delta=10^{-2},\dots,10^{-8}; App. D.12, Fig. D.11).
    • On M7-All, the combination with the largest predicted gap, the Greedy-Info/Track ratio grows from 1.07 to 1.17 (95% CI [1.12, 1.22] at δ=10−8\delta=10^{-8}).
    • App. D.12 reports every pre-registered prediction, including those not confirmed.
    • Greedy-Alt, which retargets alternatives, remains competitive at these δ\delta: it is cheaper on M7-All and costlier on M5-S.

Summary. At practical δ\delta, Track-and-Certify's cost advantage over adaptive heuristics is modest. Its distinctive contribution is the first-order guarantee, which single-action greedy rules lack. A standard comparator such as a Top-Two or game-based sampler would be a natural addition.

We thank the reviewer again. The revised PDF also contains changes requested by other reviewers, mainly in presentation, plus a corrected proof step in App. C.2 that leaves all theorem statements unchanged. All new and changed text is marked in blue.

Thank you for the response and additional experiments. The adaptive baselines address my comparison concern. However, the targeted misspecification tests show that certification errors can substantially exceed the nominal level, even when the true optimal decision is unchanged. This does not contradict the theorem under its assumptions, but leaves a substantial practical reliability concern when the assumed environment class omits the truth. On closer reading of the latest version, I still find some technical details difficult to follow, and the abstract could communicate the main contribution and its scope more clearly. I appreciate the clarification, but these concerns remain significant. I maintain my overall rating.

AuthorsOpenReview ↗

Response to Reviewer ZJrn — Follow-up

Thank you for the follow-up and for confirming that the adaptive baselines address the comparison concern! We agree that the misspecification results identify a substantial practical limitation. Prompted by your comment, we ran two pre-registered experiments to test whether the remedy suggested in App. D.11 works.

Remedy tested. App. D.11 attributes the errors to off-class data being best fit by a member of Θ\Theta that carries a different answer, and suggests that the class should also cover decision-preserving neighbours of the historical environment. We built Θ+\Theta^+ from Θ\Theta alone. For every alternative λ∈Θ\lambda\in\Theta, it adds the mixtures (1−a)P0+aλ(1-a)P_0+a\lambda on a grid of aa that keep P0P_0's optimal configuration. The test truths of App. D.11 generally lie off this grid, so the truth is still outside the class. Algorithm 1 is rebuilt on Θ+\Theta^+: allocations come from the characteristic program against Alt\mathrm{Alt}, and the threshold is β=log⁡((∣Θ+∣−1)/δ)\beta=\log((|\Theta^+|-1)/\delta). Pools, truths, seeds, and δ=0.01\delta=0.01 are the same as for the error curve in App. D.11, with 1,000 seeds per cell and 88,000 runs in total. Before the main run, the modified code reproduced all 32,000 earlier runs exactly.

Results.

  • Wrong certifications. There are none in any of the 64 misspecified cells, for either a fine grid (step 0.05, 21–201 environments) or a coarse grid (step 0.2). The 95% upper bound is 0.37% per cell. The original class, on the same truths and seeds, gives error rates of 0.3–98%.
  • Price with the truth in the class. Mean cost rises by 1.06–1.52× with the fine grid and 1.03–1.23× with the coarse grid, mainly through the larger threshold β\beta. C⋆(P0)C^\star(P_0) is unchanged.
  • Truths near the decision boundary. Certification becomes much more expensive here, because ruling out the nearby decision-changing alternative is genuinely costly. In seven of the 32 fine-grid cells, 23–96% of runs reach the 500,000-round horizon. All of these cells are in M1 or M2 at ϵ/ϵ⋆∈{0.5,0.75}\epsilon/\epsilon^\star\in\{0.5,0.75\}. In each of them, the first-order cost C⋆(Q)βC^\star(Q)\beta at the true QQ is close to or above the horizon budget. Such runs return no certificate rather than a wrong one.

Off-segment check (second pre-registered experiment). The truths above lie on segments that Θ+\Theta^+ is built to cover. We therefore also used truths that lie on no such segment, with the same Θ+\Theta^+ and no retuning. Every truth keeps P0P_0's optimal configuration. There are 84 cells and 168,000 runs.

  • Two kinds of truth.
    • The first kind moves toward the midpoint of the two nearest decision-changing alternatives. These truths lie inside the convex hull of Θ\Theta.
    • The second kind adds a random direction to the shift toward the nearest alternative, of the same total-variation size; we used three fixed Dirichlet draws. These truths lie outside the convex hull.
  • Results.
    • The original class exceeds δ\delta in 83 of the 84 cells, with error rates up to 100%.
    • Θ+\Theta^+ makes no wrong certification in any cell, including the 66 cells outside the convex hull.
    • The price follows the same pattern as above. For shifts up to half-way to the decision boundary, cost rises 1.15–2.04×. Near the boundary in M1 and M2, runs often reach the horizon.
  • Remaining scope. These truths are still anchored at a member of Θ\Theta. Truths far from every member of the class are not covered by this construction.

Revised PDF. We have uploaded a revised PDF (all changes are in blue). It contains:

  • Both experiments, added to App. D.11 with a summary table.
  • The remedy and its price, stated in Sec. 7.
  • On technical details, a short paragraph in Sec. 5.2 and a roadmap at the start of App. C, stating which assumptions each step of the proof uses. We would be grateful to know which other parts were hardest to follow.

Thank you again for the careful and constructive reviews.

Reviewer_uepGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

They formulate a problem for deciding which set of LLMs we should use for inference (for instance for routing or cascade or etc), in particular, given a new configuration (eg new models) and old one, how to strategize a cost aware evaluation pipeline to finalize a performative configuration. They provide an algorithm to solve this problem, along with some empirical experiments to show its perfomrnace.

Critical strengths

The problem they consider is very practical and interesting. Big AI companies constantly face a similar problem where they have to decide how to evolve their ecosystem of LLMs as new models come to the picture. However, I am not able to fully understand this paper contributions to this problem (look at weakness).

Critical weaknesses

The abstract and intro can use a lot of improvements. Particularly, the part about the algorithm you give, is hard to understand. For instance, look at the following sentence copied from line 76:

"TRACK-AND-CERTIFY tracks the characteristic allocation, is δ-correct, and asymptotically attains this cost under finite-class assumptions; independent auxiliary data can select a valid evaluation family before certification."

First of all, it is a very long sentence and I can not understand what it says. This is particularly bad, as it is at a critical point where you are listing your contributions. Also so many buzz words. auxiliary data? valid evaluation family? what are these?

what is "characteristic allocation"? There was some effort to explain a term "characteristic certification cost" earlier, but cant help to figure out this other term. Also, in the abstract and intro, it is good, to keep the text very self sufficient and smooth. Like the reader should not have to jump around in your paper to find the definitions in order to be able to understand your intro.

overall, this is not a good intro. I do get the high level problem, and I am not able to fully understand the contributions, and the core findings and techniques.

On section 3.1:

It is hard to follow the problem formulation. It is good to have a running example, or try to give contexts to the reader. For example, in line 112, when you say an unknown environment, what are you exactly talking about? Is the environment a bunch of LLMs? what is unknown about it? what is a serving configuration? what is "the update" mentioned in line 113? what is the utility? how should I think about it? is it accuracy? Maybe give an example? In line 118, what is a certifier? does it have a mathematical notation? what is the input and output for it? I can continue these questions for a very long time:) It is not obvious to me whether this section is written to be read and understood, or just a manifesto of some technical arguments.

Questions for authors

none.

4 comments
AuthorsOpenReview ↗

Response to Reviewer uepG — Part 1/3

We sincerely thank the reviewer for the careful reading and for recognizing that the problem is "very practical and interesting." We fully agree that the abstract, introduction, and Section 3.1 were written too densely and relied on terms defined only later. We have substantially rewritten these parts and uploaded a revised PDF (changes in blue). Below we (1) explain the paper in plain language with a running example, (2) answer each of the reviewer's questions directly, and (3) show the revised text.

(1) The paper in plain language, with a running example

Setting. A company serves user queries with an incumbent model BB. A new candidate model jj is released. Before changing production, the operator must choose among three serving configurations:

  • Keep: continue serving with BB.
  • Replace: serve with jj instead.
  • Cascade: answer with BB first; if a verifier (e.g., unit tests or an exact-answer check) detects that BB's answer is wrong, call jj.

Why this is non-trivial. Take the controlled setting of Appendix D.4: BB is correct on 70% of queries and jj on 65%, with serving-cost penalties ηκB=0.10\eta\kappa_B=0.10 and ηκj=0.25\eta\kappa_j=0.25. Replacement is clearly worse (utility 0.400.40 vs. 0.600.60 for Keep). The cascade, however, depends on a joint quantity: on the 30% of queries where BB fails, how often does jj succeed (the rescue rate)? If jj rescues half of them, the cascade reaches 0.70+0.30×0.5=85%0.70+0.30\times0.5=85\% accuracy and utility 0.675>0.600.675>0.60, so Cascade is optimal. If jj mostly fails on the same queries as BB (rescue rate 0.150.15), the cascade reaches only 74.5%74.5\% accuracy and utility 0.57<0.600.57<0.60, so Keep is optimal. In general, Cascade beats Keep exactly when the rescue rate exceeds ηκj=0.25\eta\kappa_j=0.25. Same accuracies, different correct decisions (Fig. D.2).

The evaluation problem. These quantities are unknown for the operator's workload. Estimating them requires running models on test queries, and each run costs inference compute. For each test query, the operator chooses which candidates to run: one candidate (a "singleton" evaluation), two candidates (a "pair"), or all of them. The incumbent's outcome on that query is always recorded at no extra cost. Different choices cost different amounts and reveal different information.

Our question. What is the cheapest way to buy evaluations so that the chosen configuration is correct with probability at least 1−δ1-\delta?

Our answers.

  1. How much evaluation is unavoidable (Thm. 1). We define the characteristic certification cost C⋆C^\star: the minimum evaluation budget (per unit of log⁡(1/δ)\log(1/\delta)) needed to rule out every scenario that would change the decision. Any procedure must pay at least about C⋆log⁡(1/δ)C^\star\log(1/\delta). We do not need to estimate everything, only enough to settle keep/replace/cascade.
  2. An algorithm that matches this cost to first order (Thm. 2). The optimization defining C⋆C^\star also says how to split the budget across evaluation types (we called this the "characteristic allocation"; the revision calls it the optimal evaluation mix). TRACK-AND-CERTIFY repeatedly estimates the current scenario, steers its spending toward that mix, and stops as soon as the evidence certifies a decision. This guarantee assumes the true outcome distribution lies in a known finite class of candidate distributions; see "On soundness" below.
  3. What we learn about LLM serving (Sec. 6, 11 real model pools). (a) Deciding which evaluations to buy matters a lot: an 8.53× median cost reduction relative to cycling uniformly through the same singleton evaluations. (b) Running several candidates on the same query helps on only 4 of 11 pools. A statistic computable before certification (the characteristic-cost ratio RR) predicts which pools these are (Spearman 0.88). A rule for choosing the evaluation family, fixed on development tasks, picks the cheaper family on all 11 pools of a held-out task (MMLU-Pro).
AuthorsOpenReview ↗

Response to Reviewer uepG — Part 2/3

(2) Direct answers to the reviewer's questions on Section 3.1

We have also restructured Section 3: it now starts from the concrete LLM keep/replace/cascade instance (old Sec. 3.3) and only then introduces the general notation (Θ,Π,Z,hz,Jπ)(\Theta,\Pi,\mathcal{Z},h_z,J_\pi) as an abstraction of it. Each abstract object is explained through the example, and a new notation table (Table A.1) gives every symbol's meaning and value in the example.

Reviewer's questionAnswer (now stated explicitly in the revised Sec. 3)
"when you say an unknown environment, what are you exactly talking about? Is the environment a bunch of LLMs? what is unknown about it?"No. The models are fixed and known. θ\theta is the unknown joint distribution of the models' correctness on a random query from the operator's workload. For example, P(YB=1)P(Y_B=1), P(Yj=1)P(Y_j=1), and P(Yj=1∣YB=0)P(Y_j=1 \mid Y_B=0). In our experiments it is a distribution over the 26=642^6=64 joint correct/incorrect outcomes of one incumbent and five candidates. Our guarantees assume θ\theta lies in a known finite class Θ\Theta of candidate distributions, built from historical data. This is now stated in the Introduction and in Sec. 3.3.
"what is a serving configuration?"The rule used to answer future production traffic after the decision: Keep BB, Replace with jj, or Cascade B→jB\to j. With 5 candidates there are 1+5+5=111+5+5=11 configurations.
"what is 'the update' mentioned in line 113?"A change to the model pool, e.g., a newly released model or a price change, that triggers this keep/replace/cascade decision.
"what is the utility? how should I think about it? is it accuracy?"Expected accuracy minus η×\eta\times serving cost per query (Eqs. 1–3 of the revision). η\eta is the operator's exchange rate between accuracy and inference cost. With η=0\eta=0 the utility is plain accuracy.
"what is a certifier? does it have a mathematical notation? what is the input and output for it?"The evaluation procedure. Input: the target error δ\delta, the class Θ\Theta of candidate environments, the available evaluation actions Z\mathcal Z, and their costs hzh_z. At each step: it chooses which candidates to run on the next test query and observes whether each answer is correct. Output: a stopping time τ\tau and a configuration π^\hat\pi. Formally, it is a triple (sampling rule, stopping rule, decision rule). It is "δ\delta-correct" if π^\hat\pi is optimal with probability ≥1−δ\ge 1-\delta.
"auxiliary data? valid evaluation family? what are these? what is 'characteristic allocation'?"Optimal evaluation mix: the budget split across evaluation types achieving C⋆C^\star. Evaluation family: the menu of evaluation types the certifier may use, e.g., "singleton only" vs. "singleton + pairs + full pool". Auxiliary data: historical evaluation logs, independent of the fresh test queries, that can be used to choose the family before certification starts, without breaking the 1−δ1-\delta guarantee (Cor. 1).
AuthorsOpenReview ↗

Response to Reviewer uepG — Part 3/3

(3) Concrete revisions (in the uploaded PDF, in blue)

The changes addressing this review are expository; no theorem statement or assumption has changed, and the assumptions are now listed explicitly as (A1)–(A5) in Sec. 5.2. The revision also contains changes requested by other reviewers, notably a corrected proof step in App. C.2 and additional appendix experiments. All new or changed text is in blue, and the main text stays within the 10-page rebuttal limit.

  • Abstract and Introduction (pp. 1–2) are rewritten: the Introduction now opens with the running example above, key terms are defined at first use, and the finite-class assumption is stated up front. Figure 1, the workflow overview, is now referenced from the Introduction.
  • Section 3 is restructured to go from concrete to abstract:
    • Sec. 3.1 is the keep/replace/cascade instance, with the utilities explained in words.
    • Example 1 gives the 70%/65% numbers.
    • Sec. 3.2 defines evaluation actions, evaluation costs, and "evaluation family".
    • Sec. 3.3 states the general problem in terms of the example. A new "Certifiers" paragraph first describes a certifier in words, then defines it formally (inputs; sampling, stopping, and decision rules). An "Objective" paragraph then defines δ-correctness and states the problem as a single displayed optimization (Eq. 6).
  • New notation table (Table A.1, Appendix A.1): symbol, meaning, and value in Example 1.
  • Unified terminology.
    • "Characteristic allocation", "characteristic design", and "information design" are now one term, the optimal evaluation mix, defined right after Eq. (8).
    • "Configuration-changing" and "decision-changing" alternatives are now consistently decision-changing alternatives.
    • "Auxiliary data" is now historical evaluation logs.
    • Experiment-specific jargon ("route", "frozen") has been removed.
  • Sec. 4 now works through Example 1 numerically. With rescue rate 0.5, C⋆≈23hC^\star\approx 23h, so in the one-parameter case of Eq. (11), at δ=0.05\delta=0.05 any certifier needs at least roughly 60 singleton evaluations in expectation; at rescue rate 0.375, C⋆C^\star grows to about 87h87h. To make room for the example, the LP dual and the cost–Blackwell pruning proposition moved to Appendix B.3, with a short summary left in the main text.
  • Precise wording on multi-candidate evaluation. Evaluating several candidates on the same query never makes a new decision identifiable, but it can make identification cheaper (abstract, Sec. 3.2).
  • The sentence the reviewer quoted is now the second contribution bullet, and the abstract and all three bullets are rewritten in the same style:

Old (line 76): "TRACK-AND-CERTIFY tracks the characteristic allocation, is δ-correct, and asymptotically attains this cost under finite-class assumptions; independent auxiliary data can select a valid evaluation family before certification."

Revised: "Characteristic certification cost and an optimal certifier. Adapting controlled-sensing analysis, we show that every δ-correct procedure must spend about C⋆log⁡(1/δ)C^\star\log(1/\delta), and that TRACK-AND-CERTIFY, which tracks the evaluation mix attaining C⋆C^\star, matches this cost as δ→0. Historical evaluation logs can select which evaluations to allow without affecting the guarantee."

On soundness. If the soundness concern stemmed partly from the presentation, we hope the revision helps. We also want to be explicit about the scope of our guarantees.

  • Proof techniques. The lower bound (Thm. 1) uses the standard change-of-measure argument (Kaufmann et al., 2016). δ-correctness follows from a GLR stopping rule and Ville's inequality, and asymptotic optimality from tracking arguments (Garivier & Kaufmann, 2016). Full proofs are in Appendices B–C.
  • Scope of the guarantee. Theorem 2 assumes the true outcome distribution lies in a known finite class Θ\Theta ((A1)–(A5), Sec. 5.2). We now state this up front, and Sec. 7 and App. D.11 discuss what happens when it does not.

If any specific step remains unclear, we would be grateful to know and will clarify it promptly.

We hope the revised presentation makes the contributions clear. If our responses resolve the reviewer's concerns, we would be grateful if the reviewer would consider updating the presentation, soundness, and overall scores. We welcome any further questions during the discussion period.

Dear Reviewer uepG,

Thanks for your time and effort in reviewing this paper. Your comments are valuable to improve the quality of this paper.

As the author-reviewer discussion period will end in about 1 day, we gently request that you read the rebuttal and check whether your concerns are addressed.

Thanks again for your time and help in improving the quality of this paper.

Regards from the authors.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the Rebuttal and Revisions

Dear Reviewers and AC,

We sincerely thank the Area Chair and the reviewers for their constructive feedback. The reviewers agreed that the problem is practical and distinct from inference-time routing. Their concerns ranged from the clarity of the formulation to the novelty of the theory, one proof step, and reliability under misspecification. All changes in the PDF are marked in blue:

  • Clarity (uepG, ZJrn). The abstract, introduction, and Sec. 3 are rewritten around a keep/replace/cascade example, with terms defined at first use and unified terminology. We added a worked example in Sec. 4, a notation table (Table A.1), assumptions (A1)–(A5) with the part of Theorem 2 each supports, and a proof roadmap in App. C.
  • Theory contribution (SRnX). Sec. 2 and App. B.1 (Table B.2) credit the shared controlled-sensing machinery, and the contribution is stated as the formulation and its LLM-specific structure (Eqs. 10–11). App. C.4 treats ties.
  • Proof in App. C.2 (SRnX). The Hellinger step is replaced by a martingale argument with an explicitly proved coverage bound; no theorem statement changes.
  • η\eta and related work (SRnX). App. D.10 gives ways to set η\eta and a sensitivity analysis; over a threefold range, the decision changes in 1 of 11 pools. RACER is added to Sec. 2.
  • Adaptive baselines (ZJrn). App. D.12 compares Track-and-Certify with two greedy rules and an oracle on all 11 pools. The heuristics match its median cost, so the savings come from decision-aware evaluation.
  • Misspecification (ZJrn). App. D.11 shows that the error can exceed δ\delta even for small shifts, and Sec. 7 states this. In addition, a tested remedy that adds decision-preserving mixtures to the class gives no wrong certification in all 116 misspecified cells (the original class exceeds δ\delta in 109), at 1.03–1.52× the cost when the truth is in the class.

What the paper contributes:

  • A practical problem, solved to first order. The reviewers found the problem practical and distinct from inference-time routing. We give a lower bound on the evaluation cost of any δ\delta-correct certifier and an algorithm that matches it as δ→0\delta\to0.
  • New structure for LLM serving. Singleton evaluations alone identify every keep, replace, and cascade decision; multi-candidate evaluation changes only the cost, and cascade certification has a closed-form cost (Eqs. 10–11).
  • Usable before evaluation starts. A cost ratio computed from historical logs predicts where multi-candidate evaluation pays off (Spearman 0.88 across 11 pools) and picks the cheaper evaluation family on all 11 pools of a held-out task.
  • Large savings. On 11 model pools from LLMRouterBench, decision-aware evaluation cuts median evaluation cost by 8.53× over uniform evaluation.

We thank ZJrn for confirming that the new baselines address the comparison concern, and SRnX for noting that the revised framing helps assess the contribution. We thank uepG for finding the problem "very practical and interesting", though we have not yet heard from the reviewer on the revision.

We believe these updates resolve all pending issues and ensure the paper meets the high standards of the conference. We hope the AC finds the revised manuscript suitable for acceptance.

Best regards, The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.