- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper explores how to use Gittings index policies to reduce the token consumption during benchmarking of LLMs. The objective is to use a good bandit policy to reduce the evaluation budget of LLMs. The results are validated with some experimental ablations and show gains over some other sequential decision making strategies such as an expected improvement acquisition approach.
Critical strengths
The work combines ideas from two fields well. First it takes classical ideas of the bandits, bayesian optimization literature and applies them successfully to LLM benchmarking. I see this work as a successful paper of the type (take technique X from Z and apply it to Y).
Critical weaknesses
Related to the paper's strengths, in my opinion this work is doing "take technique X from Z and apply it to Y" and as such it leaves me with some amount of skepticism towards the scale of the contribution and if it is worth an ICLR paper.
Questions for authors
Can you clarify succinctly what aspect of your work goes beyond "take technique X from Z and apply it to Y", did you expand the tehory of Gittins index policies? I didn't really see any form of innovaiton per se in that space.
2 comments
Extending Gittins-index theory with guarantees for anytime recommendation
Regarding your question about extending the theory of Gittins-index policies, we have added two new guarantees for our LCB-style anytime recommendation rule under optional completion (Appendix B.3, Theorems B.1–B.2).
First, sparse evaluations can produce optimistic posterior means, so we discount uncertain estimates to make early recommendations more stable. Compared with recommending the configuration with the highest posterior mean, our rule selects a configuration with no greater posterior standard deviation, and any increase in posterior expected simple regret is bounded by the reduction in that standard deviation.
Second, whenever we recommend a configuration, we want to know how far its full-benchmark score can fall short of the best. Under the Gaussian surrogate, we establish a high-probability posterior bound on simple regret, even before any configuration is fully evaluated.
Clarifying the Methodological Novelty and Broader Significance of GittinsEval
Thank you for your positive assessment and for raising this important question. Our work is a theory-inspired methodological and empirical paper that addresses several gaps between classical Gittins-index theory and practical cost-efficient evaluation:
1. From required completion to optional completion. The classical Gittins-index optimality result relevant to our setting requires fully evaluating a configuration before recommendation. We relax this restriction through an optional-completion setting that allows partially evaluated configurations to be considered for anytime recommendation.
2. Decoupling allocation and recommendation. This relaxation introduces a new challenge: the classical Gittins policy specifies allocation and stopping decisions but not how to recommend partially evaluated configurations. We therefore introduce a separate uncertainty-aware LCB-style recommendation rule, which empirically stabilizes recommendations and improves early-budget performance.
3. Making Gittins indices computationally practical. Gittins indices have often been viewed as primarily theoretical tools (Scully & Terenin, 2025), partly due to the computationally expensive dynamic programming involved. PBGI for cost-aware Bayesian optimization (Xie et al., 2024) is a notable practical application, but uses inspect-once Pandora's-box Gittins indices rather than the multi-stage Bayesian-bandit indices needed for repeated partial evaluations. We develop an efficient implementation for this setting, with algorithmic overhead comparable to UCB-E (Appendix E.1, Figures 8–9), and investigate key modeling and algorithmic design choices.
Beyond LLM evaluation, our framework applies to cost-aware candidate-selection problems with unknown latent performance, noisy evaluations, and recommendations based on partial observations.