Cost-Aware Best-LLM Identification using Dueling Feedback

Conference: NeurIPS2026
arXiv: 2609.30360
Area: Learning Theory
Keywords: dueling bandits, best-arm identification, heterogeneous querying costs, Condorcet winner, sequential testing

TL;DR

The paper formulates fixed-confidence identification of the best model under pairwise preferences as a heterogeneous-cost dueling bandit, allocates comparisons using rejection evidence per unit cost, tracks sampling targets, and stops through best-arm hypothesis testing, with an almost-sure asymptotic cost guarantee; however, the confidence-interval variant DCTAC costs less than the main algorithm DCTAS in the finite experiments.

Background & Motivation

Model evaluation does not always produce reliable absolute scores. Given two answers to the same question, users often find it easier to judge which is better, motivating pairwise comparisons on platforms such as Chatbot Arena. Yet preferences need not admit a complete ranking: one model can beat every opponent while the remaining models still form cycles. The paper assumes only a Condorcet winner, whose true win probability against every other model strictly exceeds one half; it requires neither a global total order nor stochastic transitivity.

Existing fixed-confidence dueling-bandit methods primarily optimize comparison counts, but comparing inexpensive models is not equivalent to comparing expensive ones. Here each model's querying cost is known beforehand, and a comparison costs the sum of its two model costs. The objective is not to select the model with the best quality-to-price ratio, but the best model by preference; costs determine how to find it without changing the definition of the winner.

The key shift is that an expensive winner need not repeatedly defeat every competitor itself. Finding a credible losing opponent for each non-winner rules out that model as a Condorcet winner, and these opponents need not be the winner. Core Idea: identify the best model by purchasing the most effective rejection evidence for each competitor, allocating budgets according to information per comparison cost, and using the same identification objective to guide stopping.

Method

Overall Architecture

DCTAS (Dueling Bandit Cost-Aware Track and Stop) takes candidate models, a known cost vector, and an allowed error probability. The true preference matrix is unknown and estimated online. Each round computes rejection evidence per unit cost from empirical win probabilities, obtains budget and sampling allocations, selects a pair through forced exploration and allocation tracking, receives one win/loss observation, and applies best-arm hypothesis testing. No model parameters are trained: feedback updates only preference estimates and comparison counts.

Two information flows should remain distinct: the allocator decides which models to compare next, while the stopping rule decides whether the evidence is sufficient. Win/loss observations update both the next allocation and the stopping test. Costs and confidence are control inputs in the diagram, not generated answers or training labels.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Known costs and empirical preferences"] --> B["Rejection evidence per unit cost"]
    B --> C["Budget-to-sampling allocation"]
    C --> D["Forced exploration and allocation tracking"]
    D --> E["Compare selected pair<br/>Observe outcome and update statistics"]
    E --> F["Best-arm hypothesis testing"]
    G["Allowed error probability"] --> F
    F -->|Threshold passed| H["Return estimated winner"]
    F -->|Not passed: allocate again| B

Key Designs

1. Rejection evidence per unit cost: find the most economical losing witness for each non-winner

Let \(p_{m,n}\) denote the true win probability, \(c_m\) the model cost, \(a^*\) the true winner, and \(d(x,y)\) the KL divergence between two Bernoulli distributions. If model \(m\) loses to \(n\), raising its win probability against \(n\) to one half is a statistical boundary it must cross to qualify as a winner; a greater distance from this boundary makes rejection easier. If it already beats \(n\), that edge provides no rejection evidence and its KL contribution is zero. The authors obtain the following closed-form quantities:

\[ \alpha_m=\max_{n\ne m}\frac{d\!\left(p_{m,n},\max\{0.5,p_{m,n}\}\right)}{c_m+c_n},\qquad c^*(\nu)=\sum_{m\ne a^*}\frac{1}{\alpha_m}. \]

\(\alpha_m\) is the best information rate per unit cost for rejecting model \(m\), while the characteristic cost \(c^*(\nu)\) aggregates the difficulty of rejecting all non-winners. The set \(\Gamma_m\) of maximizing opponents can contain several models and need not include the true winner. The information-theoretic lower bound on expected total cost is \(c^*(\nu)\log(1/(4\delta))\); it measures the information needed to distinguish different winners under an unknown matrix, not the expense of deploying the winner.

Harder-to-reject models receive more rejection budget: their shares are proportional to \(1/\alpha_m\), normalized and assigned to their most effective opponents. When several opponents are equally effective, the optimum is a set of allocations rather than a unique vector, and budget can be distributed among equivalent opponents. Proposition 1 has a notational interpretation issue between total weight involving a model and budget for rejecting that model. This note uses the latter interpretation to explain the mechanism, rather than treating the former's literal formula as an unambiguous implementation specification.

2. Budget-to-sampling allocation: budget shares are not comparison-count shares

The optimization first produces \(w_{i,j}\), the share of total expenditure assigned to a model pair. If two comparisons cost 2 and 5 respectively, equal budgets do not imply equal sampling counts: divide by the cost per comparison before normalizing into sampling fractions. Let \(\mathcal K\) be the set of unordered model pairs. The conversion in Lemma 2 is:

\[ \alpha_{i,j}=\frac{w_{i,j}/(c_i+c_j)}{\sum_{(m,n)\in\mathcal K}w_{m,n}/(c_m+c_n)}. \]

Here \(\alpha_{i,j}\) is a pair's sampling fraction, distinct from the single-subscript rejection information rate \(\alpha_m\) in the previous design. WeightPullAllocation substitutes the empirical matrix for the true one, computes a budget allocation, and applies this conversion; its pseudocode distributes budget uniformly among tied optimal opponents. Costs are not merely multiplied into the bill after sampling: they change which comparisons are selected and how often they occur.

3. Forced exploration and allocation tracking: prevent early errors from permanently removing information sources

The algorithm first compares every model pair once. Subsequently, if any pair has been compared fewer than \(\sqrt t\) times, it chooses a pair with the smallest comparison count. Otherwise, it selects the pair minimizing actual comparison count minus the sum of its target sampling fractions over previous rounds, compensating the pair most under-sampled relative to its target. Tracking cumulative targets rather than only current probabilities also realizes past allocation decisions.

Forced exploration is important because the empirical matrix can temporarily select the wrong rejection opponent or fail to show a clear empirical winner; neither should permanently prevent an edge from receiving new observations. As time increases, every edge continues to receive observations and empirical preferences converge almost surely. The appendix proves that tracking fractions approach the optimal allocation set, not necessarily one unique weight vector, directly addressing ties between optimal opponents. However, the main allocation pseudocode does not fully specify fallback handling when the early empirical matrix lacks a winner, so its implementation details should not be considered complete on that basis alone.

4. Best-arm hypothesis testing: test who can be the winner, not merely who wins one duel

The stopping rule compares two global hypotheses: model \(i\) is the Condorcet winner, or model \(j\) is the Condorcet winner. Each hypothesis requires its model's win probability against every opponent to reach at least one half, allowing the difference between constrained maximum likelihoods to be computed from the KL penalties of its losing edges. Lemma 3 provides a closed-form statistic; the expression below omits irrelevant self-comparison terms:

\[ Z_{i,j}(t)=\sum_{k\ne j}N_{j,k}(t)d\!\left(\hat p_{j,k}(t),\max\{\hat p_{j,k}(t),0.5\}\right)-\sum_{k\ne i}N_{i,k}(t)d\!\left(\hat p_{i,k}(t),\max\{\hat p_{i,k}(t),0.5\}\right). \]

The first term measures how much observed evidence must be contradicted to force \(j\) to be a winner; the second applies the same measure to \(i\). A larger difference favors \(i\). Consequently, evidence that a different, inexpensive model reliably defeats \(j\) also helps reject \(j\): the evidence need not come only from direct duels between \(i\) and \(j\).

The algorithm stops and returns a model only if some \(i\) exceeds the dynamic threshold \(\beta(t,\delta)\) against every alternative winner hypothesis. The paper's threshold comes from a mixture-martingale sequential bound and depends on the number of models, time, and error probability; it is not a fixed 0.5 win-rate threshold. This note does not reproduce the lengthy definition of its auxiliary function \(C\). Theorem 2 bounds the probability of stopping with an incorrect answer by \(\delta\), whereas Theorem 3 establishes a separate property:

\[ \limsup_{\delta\to0}\frac{J(\tau_\delta)}{\log(1/\delta)}\le c^*(\nu)\quad\text{almost surely}. \]

This is an almost-sure asymptotic upper bound on total cost. It shares a leading constant with the expected-cost lower bound, but does not guarantee that DCTAS is cheaper than every other method at an arbitrary finite error probability. Nor can it be rewritten as an expected-cost convergence theorem without an additional argument.

A Worked Example

In the paper's three-arm instance, model 1 beats models 2 and 3 with probabilities 0.63 and 0.65, and model 2 beats model 3 with probability 0.60, making model 1 the winner. The cost vector is \((k,1,1)\), so the winner becomes progressively more expensive. The following sampling fractions are optimal targets for the known true matrix, not actual counts necessarily attained in every finite run.

At \(k=4\), the cost-unaware method assigns all target sampling to \((1,2)\) and \((1,3)\). The cost-aware method instead uses \((1,2)\) to reject model 2 and the inexpensive \((2,3)\) comparison to reject model 3. Although model 2 is not the winner, it provides an effective losing witness for model 3.

No missing win probability is inferred through transitivity: direct evidence that model 3 loses to model 2 rules out model 3 as a Condorcet winner, and rejecting model 2 leaves model 1. The main text describes this example as exploiting transitivity, but the general method requires only the existence of a winner; this note does not turn that statement into an additional algorithmic assumption. A zero target share for \((1,3)\) also does not imply that finite runs never compare this pair, because forced exploration remains active.

Key Experimental Results

Main Results

The real-data experiments construct Bernoulli comparison instances from four Chatbot Arena preference matrices and public prices, set \(\delta=10^{-10}\), and run 100 trials per data point. The table below reproduces selected results from Table 2: mean cumulative cost with 99.7% confidence intervals, lower being better. Cost definitions and scales differ across tasks, so absolute values should not be compared across columns.

Algorithm	T2I	T2T	Vision	Search
DCTAS	2823 ± 89	21.5 ± 0.9	77.0 ± 4.3	1015 ± 28
TAS	2931 ± 171	22.8 ± 1.2	78.9 ± 4.0	1079 ± 59
DPCA	13017 ± 138	Not reported	304.2 ± 70.4	9184 ± 212
CRR	Not reported	73.8 ± 2.0	364.2 ± 16.3	Not reported
DCTAC	1461 ± 907	12.8 ± 1.7	42.6 ± 2.9	973 ± 67

“Not reported” means neither zero cost nor an unusable algorithm: the authors state that these runs were prohibitively expensive, with mean cost exceeding ten times DCTAS's mean cost. The ± values are the authors' stated confidence intervals, not standard deviations. DCTAC has the lowest mean cost in all four columns, but its T2I interval is especially wide, so means alone do not establish a stable advantage.

These experiments neither train models nor execute live GPU inference to measure latency. They simulate comparisons on a Google Cloud e2-highcpu-8 instance with 8 vCPUs and 8 GB of memory. T2I uses a per-image price; T2T and Vision assume 1000 generated tokens per query; Search uses High-tier pricing and request/token normalization assumptions.

Ablation Study

The paper does not provide conventional neural-module removal ablations. Its clearest mechanism analyses hold preferences fixed while changing the winner's cost, and replace the stopping rule while retaining the same tracking mechanism. The following table comes from Table 1 and compares optimal sampling fractions in the three-arm instance at \(k=4\).

Pair	Cost-unaware sampling fraction	Cost-aware sampling fraction	Mechanism
1 and 2	0.5720	0.3706	Retain the comparison that rejects model 2
1 and 3	0.4280	0	The expensive winner no longer carries model 3's main rejection budget
2 and 3	0	0.6294	Reject model 3 using an inexpensive losing witness

The synthetic experiment varies \(k\) from 1 to 19, runs 500 trials per value, and uses \(\delta=0.01\). Figure 2 reports mean costs with 95% confidence intervals. Exact plotted costs are absent from the cached text, so no pointwise costs are invented. The main text reports that TAS and DCTAS are close for the small-cost regime \(k<4\), with a growing gap as the winner becomes more expensive.

Key Findings

• TAS and DCTAS use the same GLRT stopping mechanism and differ primarily in whether allocation uses costs, making their comparison a more direct test of cost-aware sampling. Their real-data difference is much smaller than their advantages over CRR and DPCA.
• Table 3 reports DCTAS cost reductions relative to TAS of 3.8% for T2I, 5.7% for T2T, 2.4% for Vision, and 5.9% for Search. Recomputing T2I from the displayed means gives about 3.7%, differing from the reported 3.8% through rounding or a statistical reporting convention. The reported value is retained and the discrepancy flagged rather than silently corrected.
• DCTAC shares DCTAS's sampling rule but checks whether a candidate's win-probability confidence lower bound exceeds one half against every opponent. Its lower finite experimental costs distinguish asymptotically optimal allocation from finite-sample stopping overhead; the paper does not give DCTAC the same asymptotic cost theorem.

Highlights & Insights

• The useful reformulation is to find a losing witness for each non-winner, rather than make the winner certify itself against everyone. Comparisons among non-winners can handle rejection when the winner is expensive, allowing costs to change the evidence structure.
• Information per unit cost combines statistical difficulty and prices in one quantity. Simply selecting the cheapest pair is insufficient, because an inexpensive comparison near a fifty-fifty preference can still require substantial evidence to reject a model.
• Non-unique optimal allocations are not merely implementation noise; they arise mathematically from equivalent rejection opponents. Approaching the optimal allocation set avoids requiring a unique weight vector that may not exist.

Limitations & Future Work

• The guarantees assume a Condorcet winner, independent comparisons from fixed Bernoulli preferences, and known model costs. They cannot be applied unchanged when there is no winner, ties occur, the user population changes, or costs depend on output length.
• Experiments treat existing empirical matrices as true instances and simulate observations. They do not evaluate original preference-estimation error, online annotation expense, response caching, or actual API cost fluctuations. They support statistical cost advantages in allocating comparisons, not end-to-end savings in a live evaluation service.
• Proposition 1 defines a model's weight as the sum of all incident edge weights while restricting its mass to opponents that can reject it. These interpretations can differ when an edge is used to reject its other endpoint. Algorithm 2 also does not fully specify allocation when the initial empirical matrix has no winner; reproduction needs implementation checks or clarification of the notation.
• DCTAC's finite-cost advantage, the wide T2I interval, and the rounding discrepancy in Table 3 should be read separately from the asymptotic result. Future work could tighten finite-sample stopping thresholds and incorporate stochastic querying costs, rather than claim that the main algorithm already dominates all alternatives.

Related Work & Insights

• vs Karnin (2016): its verification-based dueling best-arm identification assumes uniform comparison costs. DPCA is a cost-aware two-phase extension, whereas DCTAS combines rejection evidence with dynamic optimal allocations and has lower costs in the experiments.
• vs Garivier and Kaufmann (2016), Kanarios et al. (2024): the former develops classical Track-and-Stop, and the latter studies heterogeneous costs with scalar feedback. This paper must handle model pairs, potentially cyclic preferences, and non-unique allocations, so scalar-reward allocation formulas do not transfer directly.
• vs Borda-winner identification: Borda selects the model with the highest average win probability against all opponents and remains applicable without a Condorcet winner, but it changes the identification objective. This paper derives a closed-form cost structure under the stronger winner-existence condition; it does not define the best model for every preference graph.
• Research direction: investigate whether rejection evidence per unit cost still supports useful allocations under uncertain prices or context-dependent preferences. This is a direction proposed by this note, not an experimentally established contribution of the paper.

Rating

• Novelty: 4/5. Combines heterogeneous costs with Condorcet dueling identification and an interpretable closed-form information structure.
• Experimental Thoroughness: 3/5. Includes a synthetic cost sweep, four real preference matrices, and stopping-rule comparisons, but no live model-calling experiment.
• Writing Quality: 3/5. The main argument is clear, while weight notation, early allocation handling, and local numerical reporting require clarification.
• Value: 4/5. Relevant to budget-sensitive model selection and active comparison design, with practical use contingent on preference and cost assumptions.