Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices

Summary

The paper frames LLM configuration selection—comparing models, prompts, and sampling settings on benchmarks such as GSM8K, PIQA, AlpacaEval, and MMLU—as a cost-aware Bayesian bandit problem and proposes GittinsEval, which allocates evaluation batches using Gittins indices from Markov chain selection theory. Under a Gaussian observation model (default prior N(0.5, 0.04), conservative noise variance 1/(4B)), each arm's posterior mean evolves as a Gaussian random walk, so indices can be precomputed offline via a one-dimensional dynamic program accelerated with FFTs; online steps require only lightweight posterior updates and table lookups. The classical required-completion Gittins policy is extended with an LCB-style anytime recommendation over partially evaluated arms, decoupled from allocation. The authors prove exact batch-level Bayesian optimality under the Gaussian surrogate, explicitly excluding gridded roots, continuation past stopping, and the anytime rule. On response matrices with 122–1,500 arms, GittinsEval reportedly reaches near-zero simple regret at 1–2% of exhaustive cost, with stopping typically at 1–10%; it beats configuration-level Bayesian optimization on large-example benchmarks and cost-unaware bandit baselines on 1,500-arm MMLU subjects. Limitations: the informative benchmark-level prior is selected retrospectively from the same data, the cost-scaling factor λ=10⁻⁴ was chosen from observed performance, the LRF baseline runs at batch size 32 versus 8, and no distribution-free guarantees are provided.