Cost-Aware Best-LLM Identification using Dueling Feedback

Sarvesh Gharat; Nikhil Karamchandani; Jayakrishnan Nair

cs.LGSep 24, 2026

Cost-Aware Best-LLM Identification using Dueling Feedback

Authors: Sarvesh Gharat, Nikhil Karamchandani, Jayakrishnan Nair

Organizations: Centre for Machine Intelligence and Data Science (C-MInDS) Indian Institute of Technology Bombay · Department of Electrical Engineering Indian Institute of Technology Bombay

Abstract

Inspired by the problem of identifying the best model from a collection of large language models (LLMs) with heterogeneous querying costs, we formulate and analyse a variant of the multi-armed bandit (MAB) with (i) dueling feedback, where pairwise comparisons between model responses provide robust preference signals, and (ii) heterogeneous sampling costs, reflecting the differing costs of querying different LLMs. Assuming the existence of a Condorcet winner, a condition we empirically validate across multiple real-world datasets, we propose a Track-and-Stop style algorithm for best-arm identification with prescribed confidence. We prove that the algorithm almost surely achieves the asymptotically optimal cost as the error tends to zero. Finally, we extensively evaluate our approach on both synthetic and real-world instances, demonstrating consistent improvements over classical cost-unaware algorithms and their cost-aware extensions.

Figures & tables

Figure 1: Preference matrix and model costs for the Vision-based task ( Chiang et al., 2024 )

Figure 2: Total cost incurred by DCTAS, TAS, CRR, and DPCA for different values of $k$ .

Arm Pairs	Cost Unaware	Cost Aware
1 and 2	$0.5720$	$0.3706$
1 and 3	$0.4280$	$0$
2 and 3	$0$	$0.6294$

Table 1: Optimal pull fractions for cost-aware and cost-unaware algorithms for

k=4

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

Table 2: Performance of Algorithms across Real-World Datasets.

	T2I	T2T	Vision	Search
DCTAS	$2823$	$21.5$	$77.0$	$1015$
TAS	$2931$	$22.8$	$78.9$	$1079$
$\%$ reduction	$3.8\%$	$5.7\%$	$2.4\%$	$5.9\%$

Table 3: Percentage reduction in average cost of DCTAS relative to TAS across real-world datasets.

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Assumption	Text-to-Image	Text-to-Text	Vision	Search
LNM	$\times$	$\times$	$\times$	$\times$
TO	$\times$	$\checkmark$	$\times$	$\checkmark$
SST	$\times$	$\times$	$\times$	$\times$
$\gamma$ -RST	$\times$	$\checkmark$	$\times$	$\checkmark$
MST	$\times$	$\checkmark$	$\times$	$\times$
WST	$\times$	$\checkmark$	$\times$	$\checkmark$

Appendix

Table 4: Assumptions followed across real-world datasets.

Panel of Figure 3 — Figure 3: Illustration of the preference matrix and corresponding model costs for the Text-to-Image Generation task. The reported cost represents the amount required to generate one image.

Assumption	Violating Example
Low Noise Model	i=C, j=B
Strong Stochastic Transitivity	i=A, j=D, k=C
$\gamma-$ Relaxed Stochastic Transitivity	i=B, j=D, k=C
Moderate Stochastic Transitivity	i=B, j=D, k=C
Weak Stochastic Transitivity	i=B, j=D, k=C

Appendix

Table 5: Assumption-violating examples in Text-to-Image Generation task.

Panel of Figure 4 — Figure 4: Illustration of the preference matrix and corresponding model costs for the Text-to-Text Generation task. The reported cost represents the amount required to generate one million tokens.

Assumption	Violating Example
Low Noise Model	i=DeepSeek R1, j = DeepSeek V3
Strong Stochastic Transitivity	i=LLAMA 4 Maverick, j=DeepSeek R1, k=DeepSeek V3
Stochastic Triangle Inequality	i=LLAMA 4 Maverick, j=Gemini 2.0 Flash, k=Gemma 3 27b

Appendix

Table 6: Assumption-violating examples in Text-to-Text Generation task.

Panel of Figure 5 — Figure 5: Illustration of the preference matrix and corresponding model costs for the Vision-based task. The reported cost represents the amount required to generate one million tokens.

Assumption	Violating Example
Low Noise Model	i = Gemini 2.0 Flash j = Gemini 1.5 Pro
Strong Stochastic Transitivity	i=Gemini 2.5 Pro Exp, j=Gemini 2.0 Flash, k=Gemini 1.5 Pro
$\gamma-$ Relaxed Stochastic Transitivity	i=Gemini 2.0 Flash, j=Gemini 1.5 Pro, k=Claude 3.7 Sonnet
Moderate Stochastic Transitivity	i=Gemini 2.0 Flash, j=Gemini 1.5 Pro, k=Claude 3.7 Sonnet
Weak Stochastic Transitivity	i=Gemini 2.0 Flash, j=Gemini 1.5 Pro, k=Claude 3.7 Sonnet

Appendix

Table 7: Assumption-violating examples in Vision-based task.

Panel of Figure 6 — Figure 6: Illustration of the preference matrix and corresponding model costs for the Search-based task. The reported cost represents the amount required to generate one million tokens with high priority.

Assumption	Violating Example
Low Noise Model	i=PPL Sonar Pro, j=PPL Sonar
Strong Stochastic Transitivity	i=PPL Reasoning Pro, j=PPL Reasoning, k=PPL Sonar
Moderate Stochastic Transitivity	i=PPL Reasoning Pro, j=PPL Reasoning, k=PPL Sonar
Stochastic Triangle Inequality	i=PPL Reasoning Pro, j=PPL Sonar, k=GPT 4O Search High

Appendix

Table 8: Assumption-violating examples in Search-based task.

Assumption	Chatbot Arena	Text to Video	Text to Image
LNM	$\times$	$\times$	$\checkmark$
TO	$\times$	$\times$	$\checkmark$
SST	$\times$	$\times$	$\times$
$\gamma$ -RST	$\times$	$\times$	$\checkmark$
MST	$\times$	$\times$	$\times$
WST	$\times$	$\times$	$\checkmark$

Appendix

Table 9: Assumptions satisfied by the additional real-world datasets considered in our validation. The Chatbot Arena dataset is provided by LMSYS, while the Text-to-Video, and Text-to-Image datasets are provided by TigerLab.

Figure 7: Illustration of the empirical preference matrix for the LMSYS Chatbot Arena dataset, showing the pairwise preference probabilities among the models.

Assumption	Violating Example
Low Noise Model	i = chatglm-6b, j = gpt4all-13b-snoozy
Strong Stochastic Transitivity	i=RWKV-4-Raven-14B, j=alpaca-13b, k=dolly-v2-12b
$\gamma-$ Relaxed Stochastic Transitivity	i=RWKV-4-Raven-14B, j=chatglm-6b, k=gpt4all-13b-snoozy
Moderate Stochastic Transitivity	i=RWKV-4-Raven-14B, j=chatglm-6b, k=gpt4all-13b-snoozy
Weak Stochastic Transitivity	i=RWKV-4-Raven-14B, j=chatglm-6b, k=gpt4all-13b-snoozy

Appendix

Table 10: Assumption-violating examples in the LMSYS Chatbot Arena dataset.

Figure 8: Illustration of the empirical preference matrix for the TigerLab Text-to-Video dataset, showing the pairwise preference probabilities among the models.

Assumption	Violating Example
Low Noise Model	i = AnimateDiff, j = VideoCrafter2
Strong Stochastic Transitivity	i=AnimateDiff, j=VideoCrafter2, k=OpenSora
$\gamma-$ Relaxed Stochastic Transitivity	i=AnimateDiff, j=VideoCrafter2, k=T2VTurbo
Moderate Stochastic Transitivity	i=AnimateDiff, j=VideoCrafter2, k=T2VTurbo
Weak Stochastic Transitivity	i=AnimateDiff, j=VideoCrafter2, k=T2VTurbo

Appendix

Table 11: Assumption-violating examples in the TigerLab Text-to-Video dataset.

Figure 9: Illustration of the empirical preference matrix for the TigerLab Text-to-Image dataset, showing the pairwise preference probabilities among the models.

Assumption	Violating Example
Strong Stochastic Transitivity	i=PixArtAlpha, j=PixArtSigma, k=OpenJourney
Moderate Stochastic Transitivity	i=PixArtSigma, j=SDXLLightning, k=SDXLTurbo
Stochastic Triangle Inequality	i=PlayGroundV2.5, j=PixArtSigma, k=SDXLLightning

Appendix

Table 12: Assumption-violating examples in the TigerLab Text-to-Image dataset.

Explore similar work

Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similarity
Jun 5, 2026Zifan Lyu, Chahine Nejma, Tobias Wegel +2Model Selection Multi-Armed Bandits
1ETH Zurich · 2Centrale Sup´elec · 3ENS de Cachan +1
Valid Best-Model Identification for LLM Evaluation via Low-Rank Factorization
May 11, 2026Elad Tolochinsky, Yaniv Tenzer, Yaniv RomanoModel Selection Multi-Armed Bandits
Department of Computer Science, Technion – Israel Institute of Technology · Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology
Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation
Aug 5, 2026Bo Xue, Zhi Hong, Jiayi Li +3Multi-Armed Bandits LLM Evaluation
City University of Hong Kong · South China University of Technology · Zhejiang University

Jun 5, 2026J/K move · Enter open · S save

Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similarity

Zifan Lyu, Chahine Nejma, Tobias Wegel, Fanny Yang+1

1ETH Zurich · 2Centrale Sup´elec · 3ENS de Cachan+1

Model Selection Multi-Armed Bandits LLM Evaluation Language Model Generation Evaluation Best-Arm Identification

Open paper AskPDF arXiv

Large Language Models are typically benchmarked by evaluating every model on every test query. For practitioners seeking the best model to deploy, this is often wasteful: if a model clearly performs worse than others, there is no need to precisely estimate its performance. Best-arm identification algorithms can be naturally applied to drastically reduce costs by adaptively allocating evaluation budget. Further, language models often respond similarly to the same prompt-a property previous work has tried to leverage with mixed success. We propose Synchronized Successive Rejects (SySRs), augmenting the classical Successive Rejects algorithm with paired comparisons. Unlike prior attempts to leverage model similarity in best-model identification, our approach is hyperparameter-free and enjoys performance guarantees that improve with the degree of similarity between evaluated models. Empirically, our method outperforms all baselines in terms of average error rate across 15 standard benchmarks, and in terms of worst-case budget for reliably identifying the best model.

Abstract

Explore similar work

Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similarity

Valid Best-Model Identification for LLM Evaluation via Low-Rank Factorization

Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation