Motivated by the need to pick the best model from a pool of large language models (LLMs) whose query costs differ, we cast the problem as a variant of the multi‑armed bandit (MAB). The variant has two key ingredients:
- Dueling feedback: pairwise comparisons of model outputs yield robust preference signals;
- Heterogeneous sampling costs: querying each LLM incurs a distinct expense.
Empirically we find that a Condorcet winner— a model that beats every other one in pairwise duels—exists across several real‑world datasets. Assuming its existence, we propose a Track‑and‑Stop‑style algorithm for best‑arm identification with a prescribed confidence level. We prove that as the error probability approaches zero, the algorithm almost surely attains the asymptotically optimal total cost. Extensive experiments on synthetic and real‑world instances demonstrate consistent gains over classic cost‑agnostic methods and their cost‑aware extensions in both identification accuracy and overall query cost.
Review: This study uniquely integrates dueling feedback with heterogeneous costs into the best‑LLM selection problem, offering theoretical optimality guarantees and practical validation, thus providing a valuable tool for large‑scale LLM deployment.