Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices

Evaluating large language models (LLMs) is increasingly a sequential decision problem: practitioners must compare many candidate models, prompts, or decoding configurations using finite benchmark data, while each additional query incurs costs such as API pricing, token usage, latency, or human grading effort. We formulate the task as cost-aware Bayesian bandit evaluation and propose a Gittins index policy that treats benchmark performance as latent, updates posterior uncertainty, allocates queries according to their value of information, and recommends when to stop. The method combines sample efficiency with computational efficiency: after precomputing Gittins indices for the Gaussian posterior dynamics, online allocation only requires table lookup and posterior updates, and it naturally handles heterogeneous evaluation costs such as API pricing. Across GSM8K, PIQA, and MMLU response matrices, the policy achieves lower simple regret in both unit-cost and cost-aware settings than UCB-E, a frequentist best-arm identification method, and UCB-E-LRF, its low-rank correlation-aware extension.