Cost-Aware Best-LLM Identification using Dueling Feedback
cs.LG, cs.AI, stat.ML
Submitted: 2026-09-24
Updated: 2026-09-24
Comments: We propose a cost-aware dueling bandit algorithm for best arm identification, prove its asymptotic optimality, and demonstrate its effectiveness in reliably identifying the best LLM with a minimum cost Accepted at NeurIPS 2026
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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
Terminology
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.
Sources
- Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference
- LessLeak-Bench: A First Investigation of Data Leakage in LLMs Across 83 Software Engineering Benchmarks
- Line Goes Up? Inherent Limitations of Benchmarks for Evaluating Large Language Models
- Cost Aware Best Arm Identification
- Best-Arm Identification in Unimodal Bandits
- GenAI Arena: An Open Evaluation Platform for Generative Models
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks