Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices

Abstract

Exhaustively evaluating every candidate LLM configuration on every benchmark item to identify a high-performing one is costly. We formulate configuration selection as a cost-aware Bayesian bandit problem and propose GittinsEval, which draws on the Bayesian-optimal Gittins policy to determine which configuration to evaluate next and when to stop. We extend the policy with an anytime recommendation rule over both fully and partially evaluated configurations, using an LCB-style score to account for posterior uncertainty. GittinsEval is computationally efficient, requiring only lightweight online updates after offline precomputation. Across GSM8K, PIQA, AlpacaEval, and MMLU response matrices, GittinsEval is consistently competitive, with particularly strong gains over configuration-level Bayesian optimization on large-example benchmarks and over cost-unaware bandit baselines on large-candidate tasks. Crucially, GittinsEval often attains near-zero simple regret using only 1% to 2% of the exhaustive-evaluation cost; it also offers an adaptive stopping rule that typically triggers at 1% to 10%.

The Gittins Index for a Transparent One-Armed Bandit with a Continuous Payoff Spectrum in Equilibrium States
Marcin Makowski, Edward W. Piotrowski, Jan L. Cieśliński
arXiv1 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Scaling Bayesian Bandit Encoding with Shared Learning
Bhaskar Krishnamachari
arXiv5 Sep 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv
The Staged Pandora's Box: Reservation Indices for Multi-Fidelity Bayesian Optimization
Long Vu, Jongseong Brad Choi, Binoy Ravindran +1
arXiv2 Nov 2026PreprintarXiv licenceFull textOptimisation & control StatisticsarXiv
Modeling bounded well-being indices using Bayesian double generalized beta regression with spatial and temporal borrowing
Abhi Jain, Michael LaValley, Kimberly A. Dukes +1
arXiv22 Sep 2026PreprintCC BY-NC-ND 4.0Full textStatisticsarXiv
Efficient Bayesian inference for multiple network data
Francesco Barile, Sara Capozio, Bernardo Nipoti
arXiv1 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{xie2026efficient,
  title = {{Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices}},
  author = {Qian Xie and Yueli He and Nairen Cao},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.25645},
  eprint = {2609.25645},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.25645},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices
AU  - Qian Xie
AU  - Yueli He
AU  - Nairen Cao
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2609.25645
UR  - https://arxiv.org/abs/2609.25645
AB  - Exhaustively evaluating every candidate LLM configuration on every benchmark item to identify a high-performing one is costly. We formulate configuration selection as a cost-aware Bayesian bandit problem and propose GittinsEval, which draws on the Bayesian-optimal Gittins policy to determine which configuration to evaluate next and when to stop. We extend the policy with an anytime recommendation rule over both fully and partially evaluated configurations, using an LCB-style score to account for posterior uncertainty. GittinsEval is computationally efficient, requiring only lightweight online updates after offline precomputation. Across GSM8K, PIQA, AlpacaEval, and MMLU response matrices, GittinsEval is consistently competitive, with particularly strong gains over configuration-level Bayesian optimization on large-example benchmarks and over cost-unaware bandit baselines on large-candidate tasks. Crucially, GittinsEval often attains near-zero simple regret using only 1% to 2% of the exhaustive-evaluation cost; it also offers an adaptive stopping rule that typically triggers at 1% to 10%.
ER  -

Abstract

Related

Cite