Skip to content
DraconiticResearch
Search Sources API
190,860 studies31 sourcesUpdated 35 min ago
PreprintCC BY 4.0arXiv

Cost-Aware Best-LLM Identification using Dueling Feedback

  • Sarvesh Gharat
  • Nikhil Karamchandani
  • Jayakrishnan Nair
Open at sourcePDFDOICite

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.

Related

  1. Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
    Khang Luong, Dinh Thai Son, Hoang Ta +2
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  2. Capacity-Aware Multi-UE Handover Optimization for LEO Satellite Networks Using Dueling DDQN
    Po-Heng Chou, Chiapin Wang, Chung-Chi Huang +2
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  3. Tight Sample Complexity Bounds for Entropic Best Policy Identification
    Amer Essakine, Claire Vernade
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  4. Best Arm Identification for Bandits with Shifting Means
    Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal +2
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  5. Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
    Keqin Chen, Jie Bian, Yulian Wu +1
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{gharat2026costaware,
  title = {{Cost-Aware Best-LLM Identification using Dueling Feedback}},
  author = {Sarvesh Gharat and Nikhil Karamchandani and Jayakrishnan Nair},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.30360},
  eprint = {2609.30360},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.30360},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Cost-Aware Best-LLM Identification using Dueling Feedback
AU  - Sarvesh Gharat
AU  - Nikhil Karamchandani
AU  - Jayakrishnan Nair
PY  - 2026
DA  - 2026/09/24
PB  - arXiv
DO  - 10.48550/arxiv.2609.30360
UR  - https://arxiv.org/abs/2609.30360
AB  - 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.
ER  -