# Cost-Aware Best-LLM Identification using Dueling Feedback

arXiv: https://arxiv.org/abs/2609.30360 · HTML: https://mlsanity.com/paper/2609.30360/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 26 references that are in the map.
- First posted on arXiv 24 Sep 2026.

## Builds on (most cited first, 15 of 15)

- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Preference-based Online Learning with Dueling Bandits: A Survey](https://mlsanity.com/paper/1807.11398/) (2018)
- [GenAI Arena: An Open Evaluation Platform for Generative Models](https://mlsanity.com/paper/2406.04485/) (2024)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [LessLeak-Bench: A First Investigation of Data Leakage in LLMs Across 83 Software Engineering Benchmarks](https://mlsanity.com/paper/2502.06215/) (2025)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Approximate Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1801.01253/) (2018)
- [Human Preferences as Dueling Bandits](https://mlsanity.com/paper/2204.10362/) (2022)
- [Line Goes Up? Inherent Limitations of Benchmarks for Evaluating Large Language Models](https://mlsanity.com/paper/2502.14318/) (2025)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Data Leakage in Visual Datasets](https://mlsanity.com/paper/2508.17416/) (2025)
- [Best-Arm Identification in Unimodal Bandits](https://mlsanity.com/paper/2411.01898/) (2024)
- [Best Arm Identification in Bandits with Limited Precision Sampling](https://mlsanity.com/paper/2305.06082/) (2023)

## Abstract (arXiv)

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.