acceptodds
Under review as a conference paper at ICLR 2027

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%–2% of the exhaustive-evaluation cost; it also offers an adaptive stopping rule that typically triggers at 1%–10%.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Efficient LLM Evaluation, Cost-Aware Decision-Making, Bayesian Bandits, Gittins Indices

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_AowwOpenReview ↗
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
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

Reviewer_dNrrOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2(+1)
Soundness
2(−1)
Read review
Paper summary

The paper uses Gittins policy to adaptively evaluate LLM across different LLM configurations and benchmark samples.

To be quite honest, the paper is super hard to follow and I was not able to understand the real problem it is solving. My assessment is that I cannot recommend it for acceptance in ICLR because of apparent clarity issues. The technical results seem valid. Therefore, it is likely that it has raw technical value and might end up being a good paper after a thorough rewrite.

Critical strengths
  • Technical results seem valid

  • Empirical results are extensive

Critical weaknesses
  • Motivation and framing of the paper are not clear to me at all.

  • Clarity of introduction is below bar for ICLR. Intro needs a complete rewrite.

  • Missing ablations. The only Bayesian bandit algorithm used is Gittins. What about Thompson sampling and other Bayesian bandits? At least a couple more baselines need to be ablated.

  • No analysis of limitations of the current work is provided.

  • Full related work is in Appendix A, while intro does not provide sufficient positioning of this paper in the current literature. It is unclear what this paper does differently from existing work after reading the intro, while related work section is not provided in the main body. Therefore, the novelty of the paper is unclear to me.

  • The problem statement is unclear. Why K LLM configurations are evaluated over N samples? I don't understand the scenario in which each sample in a benchmark must be evaluated with a different configuration of LLM. What is the end problem?

  • The Bayesian formulation covers the observation model. However, action selection does not seem to be Baysian, although contribution claims "We formulate LLM configuration selection as a cost-aware Bayesian bandit problem". The algorithm uses LCB, which may or may not be Bayesian out of the box. Section 3 might do a better job at motivating what makes the algorithm Bayesian and how it benefits the overall solution.

  • Figures 2,3 presenting the core empirical results are very hard if not impossible to parse.

Questions for authors
  • I don't understand this statement at all: "Modern LLM evaluation requires selecting among a combinatorial space of configurations—such as models, prompts, temperatures, and decoding strategies—across benchmarks...". Why do we need to select configurations of LLMs across benchmarks? Do we optimize LLM parameters for each benchmark? The first paragraph needs a complete rewrite. I am supposed to know the purpose of the paper after reading it, but instead I am totally lost.

  • The second paragraph is not much better than the first one. "In practice, different LLMs can have substantially different inference costs, while Bayesian methods can exploit even limited prior knowledge, such as the range of possible scores or a rough sense of benchmark difficulty." So what?

  • In the third paragraph the paper totally looses me. I don't understand what is configuration, recommendation and evaluation - they are all conflated. I don't understand who needs those quantities and why. And why do we need to use Gittins algorithm to provide a recommendation.

  • The next paragraph describes operational details of the algorithm that I cannot put together in a coherent picture, because they are used before being defined. For example, "lightweight updates during evaluation after offline precomputation" - this is completely meaningless to me, without the full operational context of the algorithm.

  • The paper frames contribution as Bayesian bandit problem, however only LCB results are presented. As a non-expert in bandit literature, to me the framework that makes things trivially Bayesian in bandit context is Thompson sampling. Why is this not used as a baseline?

  • Sections 3.1, 3.2 and 3.3 are standard existing theory and should be presented in a background section, rather than being presented as part of the original method in Section 3.

6 comments
AuthorsOpenReview ↗

Clarifying GittinsEval: Problem Setting, Decision Rules, and Methodological Contributions

Thank you for your detailed feedback. We have substantially revised the manuscript and expanded the experiments to address your concerns.

1. Problem setting and decision-making process. We have rewritten the Introduction to clarify the practical motivation and distinguish configuration selection, evaluation allocation, recommendation, and stopping. Practitioners often need to choose an LLM configuration (e.g., a model paired with a prompting technique) for deployment on a given task, but exhaustively evaluating all candidates can be costly. Our goal is to identify a high-performing configuration with fewer evaluations. During this process, allocation determines which configuration to evaluate next, anytime recommendation identifies the currently preferred configuration based on partial observations, and stopping determines when to end evaluation. The practitioner may adopt the current recommendation as the final selection upon ending evaluation. The revised Introduction and Figure 1 provide an overview of this process.

2. Gittins-index policy and LCB-style recommendation. We would like to clarify a key misunderstanding: our proposed method is built around a Gittins-index policy for evaluation allocation and stopping, not an LCB-based action-selection algorithm with Gittins indices serving merely as a baseline. For our terminal-selection objective, rather than the classical cumulative-reward objective, the relevant Gittins-index optimality result assumes required completion, where only fully evaluated configurations can be recommended. In practice, however, evaluation may end before any configuration is fully evaluated. This motivates optional completion and a separate anytime recommendation rule. Although selecting the highest posterior mean is natural, estimates based on limited observations can be overly optimistic. We therefore introduce an LCB-style recommendation rule based on Bayesian posterior means and standard deviations to reduce the risk of unreliable early recommendations. This rule does not affect Gittins-based allocation or stopping (Eqs. 12–13). Paired ablations isolate its effect while keeping evaluation allocation unchanged (Appendix E.2, Figure 14).

3. Thompson-sampling comparisons and related work. Your suggestion to consider Bayesian-bandit Thompson sampling was helpful. In response, we added FormatSpread-TS, adapting the Beta–Bernoulli Thompson-sampling approach of FormatSpread (Sclar et al., 2024)—originally developed to study sensitivity to prompt formatting—to LLM configuration selection. FormatSpread-TS reaches similarly low regret on GSM8K and PIQA, though often at higher evaluation costs, whereas GittinsEval-S achieves substantially lower regret on MMLU subjects with fewer benchmark examples (Figures 2–3). We also compare against Gaussian TS under matched Gaussian modeling assumptions as an allocation ablation (Appendix E.2, Figures 15–16). Additionally, we have moved and expanded Related Work into the main text (Section 1.1).

4. Methodological contributions beyond standard theory. While we build on established Bayesian and Gittins-index theory, translating these theoretical foundations into a practical algorithm for repeated, cost-aware partial evaluations is nontrivial. To this end, we connect batch-level observations to stage-dependent posterior dynamics, construct the corresponding cost-aware allocation and stopping policy, and make the resulting multi-stage indices computationally efficient. In particular, Section 3.3 develops an efficient computational procedure for multi-stage Gittins indices, rather than merely restating standard Gittins-index theory. We also make and empirically investigate various modeling and algorithmic design choices to improve practical performance (Appendix E.2). We present these interdependent components together since they collectively define how our method is derived and implemented.

Thank you for addressing my concerns and for substantial rewrite of the manuscript. Here is the list of concerns that I feel are satisfactorily addressed:

  • Intro, problem statement
  • Related work and positioning
  • Thompson-sampling comparisons
  • Figures 2,3

Remaining questions:

  • The blue text indicating the changes covers only a subset of manuscript revisions. Could you please provide the paper where the full set of revisions appears in blue, with respect to the original version?

  • No analysis of limitations of the current work is provided, for example:

    • theory coverage (optimality under the Gaussian, LCB recommendation rule, continuing past the stopping signal, noise model, cost model, priors and prior/reality gap)
    • negative results on subjects with fewer examples
    • the batch sizes and the -S priors were tuned on the same benchmarks used for evaluation
    • App E.2 picks λ=1e−4\lambda=1e-4 after sweeping 1e-3, 1e-4 and 1e-5 on the same benchmarks
    • The LCB ablation was chosen after seeing results. App B.2: "After reviewing the benchmark results, we selected GSM8K and MMLU Hard-Large because both clearly illustrate the reduction in simple regret."
    • arms are modeled as independent
    • all experiments are retrospective
    • "1-10% stopping" claim depends directly on λ\lambda
  • In Figure 2, FormatSpread-TS baseline and GITTINSEVAL are comparable, whereas in Figure 3 they are drastically different.

    • what is the mechanism explaining this behaviour?
    • what is the mechanism that explains the win of GITTINSEVAL over FormatSpread-TS, both being Baysian algorithms?
    • qre they evaluated in an apple-to-apple scenario?
    • could you report FormatSpread-TS with posterior-mean and LCB-style recommendation, and GittinsEval with empirical-mean recommendation to make apple-to-apple comparison and isolate the source of gains?
  • The Bayesian formulation. The LCB layer is not Bayes-optimal. The final output is not fully Bayesian-optimal, only motivated by the posterior. Multiple statements across manuscript may imply it, leading to overstatement of contributions. Please clarify. Examples:

    • abstract "propose GittinsEval, which draws on the Bayesian-optimal Gittins policy"
    • After proposition 3.2 "This is a Bayesian optimality statement"
    • "A.2 PROOF OF BAYESIAN OPTIMALITY"
  • Related to previous point. Theorem B.1 shows that LCB rule has equal or higher posterior expected simple regret than posterior-mean recommendation. Fig. 14 shows LCB substantially reduces realized regret for GittinsEval-G. Given Theorem B.1, the gain indicates misspecification between prior and the noise model. Please clarify this. Please clarify in the abstract and contributions that the optimality guarantee covers the required-completion policy, not the actual proposed algorithm GittinsEval

  • Sections 3.1, 3.2 and 3.3 are standard existing theory. I appreciate the clarified attributions, but my concern about structure remains. Rebuttal overclaims: "3.3 develops an efficient computational procedure… rather than merely restating standard Gittins-index theory". But the paper itself credits the key pieces to Xie (2026). If I have missed a component of 3.3 that is new relative to Xie (2026), please point to it specifically. A fair resolution would be to move 3.1-3.3 into a Preliminaries/Background section, or at a minimum to mark explicitly within Section 3 which components are inherited and to revise the contributions list accordingly. Based on my reading, the new parts are:

    • the full-benchmark empirical-target chain (3.4, App. B)
    • the batch and partial-final-batch handling and the LCB-style anytime recommendation layer (Eq. 13, App. B.3)
AuthorsOpenReview ↗

Follow-up Part 1: Revisions and Experimental Design

Thank you for the detailed follow-up and for recognizing the improvements to the manuscript. We address the remaining concerns in two parts, following the order raised.

1. Revision highlighting.

We initially used blue selectively to preserve readability after the extensive rewrite. We have now expanded the highlighting of revisions addressing both your original review and this follow-up.

2. Limitations, experimental choices, and future work.

We agree that the scope of the claims and the consequences of design choices should be explicit. Sections 3.1 and 3.5 state the Gaussian batch approximation and model-level cost proxies; we now explicitly note that the latter omit variation in token usage and latency across individual evaluations. The main findings acknowledge weaker results on some smaller MMLU subjects.

The G–S comparison examines the value of informative priors and sensitivity to prior choice. The S-prior uses aggregate empirical accuracies to assign coarse difficulty buckets, with one shared prior across all configurations of each MMLU subject. We have clarified this provenance and interpretation in Section 3.5 and Appendices D and E.2. FormatSpread-TS in Figures 2–3 also uses the same data-specific prior means as GittinsEval-S, encoded in its native Beta prior (Appendix D). We have also added a complementary comparison with general priors for both methods (Appendix E.2, Figures 18–19). GittinsEval-G remains broadly competitive using the same general prior across benchmarks; GittinsEval-S provides more pronounced gains on some benchmarks, especially hard MMLU subjects.

We have clarified in Section 4 and Appendix E.2 that batch size and λ\lambda are experimental choices informed by sensitivity studies on these benchmarks. The abstract now qualifies the empirical 1–10% stopping range by the cost–quality tradeoff parameter, with λ=10−4\lambda=10^{-4} specified in Section 4. These changes are highlighted in blue; the sensitivity curves remain in the appendix.

The panels in Figure 15 (previously Figure 14) were selected to illustrate a visible recommendation effect within limited space. We have revised this explanation in Appendix B.2 and highlighted it in blue. The expanded recommendation ablations now cover both prior categories on MMLU, GSM8K, and PIQA (Figures 16–19). LCB's benefits vary across settings; Appendix B.2 also reports a case where it reduces switching but slightly increases regret.

We do not regard every modeling or evaluation choice as a limitation in itself: independent-arm modeling provides tractability, and precollected response matrices support controlled comparisons. Policies still adaptively choose which entries to reveal, with individual unqueried responses hidden. Nevertheless, we have added future-work directions to the conclusion, including principled prior calibration, selection of λ\lambda, better use of cross-arm correlations, and modeling costs that vary across individual evaluations. Cross-arm information can be valuable; exploiting it effectively at reasonable computational cost remains an algorithmic direction, informed by the mixed results in Appendix E.2.

Reviewer_Mvv2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the problem of selecting candidate model and prompt templates under budget constraints, and proposes optimizing for such LLM configuration as a cost-aware bandit problem. Candidate configurations are mutually independent Gaussian-Bernoulli arms. The proposed GittinsEval makes use of cost-weighted Gittins indices and optimizes using anytime LCB. The framework was tested on a range of experiments such as on GSM8K, PIQA, MMLU etc.

Critical strengths
  • The paper adapts Gittins index theory to the paper's LLM evaluation setting, with an efficient computational approach. Though not novel as the paper indicated that it borrowed from past works, the formulation and approach provides computational advantages over other methods like standard BO.
  • Experiments were conducted across various LLM benchmarks and candidate pools.
Critical weaknesses
  • The independent arm assumption for LLM configuration spaces seems questionable. Prompt and model family checkpoints would likely be correlated and have shared covariance information. Furthermore, assuming independence also does not allow for exploitation of any structure (e.g., prompt template performance on many models v.s. that prompt for another one). This is unlike other works using joint surrogate modeling for optimizing over LLM configurations.
  • Empirical comparisons should be with proper baselines. For example, the BO baseline currently is implemented such that all benchmark items are required for every candidate query exhausting the entire budget in just a few trials. A fairer comparison would involve multi-fidelity item subsampling or using other surrogates or proxies relevant to the setting [1,2], or at least basic multi-fidelity BO native in BoTorch.
  • It is very hard to read the empirical results. Fig 2,3 are too small and the baselines are all too compressed (except for BO with issues as mentioned above and burns off half its budget on warm-up alone). No tables of the results were provided nor statistical significance.
  • The PromptEval baseline was adjusted such that its semantic sentence embeddings and designed cross-prompt generalization was removed.
  • There is a theoretical disconnect with implementation. Gittins indices are not provably optimal for fixed-budget best-arm identification, and while using the anytime LCB rule as a heuristic the theoretical guarantees would no longer hold.

[1] Chen et al., Rethinking Bayesian Optimization for Co-Optimizing LLM Training Configurations, DEMO workshop ICML 2026 [2] Falkner et al, BOHB: Robust and Efficient Hyperparameter Optimization at Scale, ICML 2018

Questions for authors
  • Could the authors provide clearer empirical results for the experiments, including statistical tests? As mentioned above, it is hard to tell much from the main body results. Would log-scale plots help better show how GittinEvals compare against baselines?
  • Could the authors provide fairer evaluation of BO methods, e.g., using at least standard multi-fidelity sample subset BO (e.g., in BoTorch) or other methods [2]?
  • Would the framework still perform well when there will clearly be more correlated information with combinatorially growing configuration spaces (e.g, including other llm inference parameter settings too) and where not exploiting such information will be an exploration bottleneck?
5 comments
AuthorsOpenReview ↗

Additional Experiments and Clarifications

Thank you for your detailed feedback. In response to your questions, we have added multi-fidelity Bayesian optimization comparisons, investigated cross-configuration correlations, and improved the presentation of our empirical results.

1. Fairer comparisons with multi-fidelity Bayesian optimization. We agree that the configuration-level BO baseline with PBGI acquisition can be disadvantaged under limited budgets, as each selected configuration is evaluated on the full benchmark. Following your suggestion, we added multi-fidelity Bayesian optimization with knowledge-gradient acquisition (MF-KG; Wu et al., 2020), using BoTorch (Balandat et al., 2020). MF-KG jointly selects a configuration and an example-subsampling fidelity, reuses previously observed examples, and incurs only incremental evaluation costs. We evaluate it under both unit-cost and heterogeneous-cost settings. On the large-example BanditEval benchmarks, MF-KG generally reduces regret faster than PBGI, but GittinsEval reaches low simple regret at lower evaluation costs (Figure 2). Importantly, MF-KG also incurs substantially higher algorithmic runtime (Appendix E.1, Figures 8–9). This computational overhead has so far prevented us from completing all MF-KG runs on MMLU; we will update the results promptly once the remaining runs finish. We retain PBGI to compare our adaptive stopping rule with one from Bayesian optimization. We also strengthened the PromptEval comparison on MMLU by incorporating pretrained prompt-template embeddings and model-specific interactions, with additional representation comparisons in Appendix E.2 (Figure 24). We have also expanded Related Work in the main text (Section 1.1) to discuss multi-fidelity and budgeted optimization, including the two papers you suggested (Falkner et al., 2018; Chen et al., 2026).

2. Exploiting cross-configuration correlations. We agree that the independent-arm assumption limits information sharing among related configurations. We additionally introduce Gaussian Thompson sampling as an allocation ablation, which also provides a useful comparison for examining cross-configuration correlations. Specifically, we conduct a 2 × 2 comparison of Gittins versus Gaussian Thompson-sampling allocation, with and without cross-configuration correlations, under matched priors and recommendation rules (Appendix E.2, Figures 20–21). The correlated variants use a joint Gaussian surrogate that allows evaluations of one configuration to inform others. Exploiting correlations improves performance on some benchmark tasks, particularly for Gaussian TS on MMLU and GittinsEval on smaller MMLU subjects, but can worsen regret on other benchmarks. It also increases computational overhead (Figures 22–23). Our experiments cover up to 1,500 configurations, although exploiting structure in substantially larger combinatorial spaces remains an important direction.

3. Clearer empirical results and uncertainty reporting. We have revised Figures 2–3 by expanding the lower-regret portion of the vertical axis to make differences near zero easier to distinguish. We retain raw simple-regret values rather than using a logarithmic scale, so zero remains visible and absolute performance gaps remain interpretable (e.g., a regret of 0.01 corresponds to a one-percentage-point accuracy gap on accuracy benchmarks). The figures include standard-error bands to reflect variability across randomized trials or benchmark subjects, with additional per-subject MMLU results in Appendix E.3.

Additional clarification on novelty and theoretical scope. Beyond applying classical Gittins theory, we extend the required-completion framework with optional-completion anytime recommendation and develop an efficient implementation of multi-stage indices for repeated partial evaluations, with algorithmic overhead comparable to UCB-E (Appendix E.1). The optimality established in Proposition 3.2 applies to the exact Gittins policy for the required-completion adaptive-stopping objective under our assumptions, rather than to fixed-budget best-arm identification. To accommodate optional completion, we augment the Gittins-based allocation and stopping policy with an uncertainty-penalized LCB-style anytime recommendation rule for partially evaluated configurations. This extension, as well as the numerical index approximations, is not covered by the optimality guarantee of Proposition 3.2.

AuthorsOpenReview ↗

New guarantees for LCB-style anytime recommendation under optional completion

In response to your concern about the disconnect between classical Gittins-index theory under required completion and our anytime recommendation under optional completion, we added a theoretical justification for our LCB-style rule. A natural alternative is to recommend the configuration with the highest posterior mean. To make early recommendations more stable, our LCB-style rule subtracts one posterior standard deviation from each posterior mean, discounting optimistic estimates from sparse evaluations. Appendix B.3 gives two guarantees (Theorems B.1–B.2).

First, given the same observations, the LCB-style choice has no greater posterior standard deviation than the posterior-mean choice. Any increase in posterior expected simple regret is bounded by the reduction in posterior standard deviation. Our empirical comparisons of the same two recommendation rules complement this theoretical result. The LCB-style rule changes the recommended configuration less often on the same evaluation trajectory (Appendix B.2) and yields smoother simple-regret curves for GittinsEval-G (Figure 14).

Second, under the Gaussian surrogate, we use the posterior standard deviations of the true best and recommended configurations to derive a high-probability posterior upper bound on the rule’s simple regret. As you point out, the Gittins optimality guarantee is specific to the required-completion setting with adaptive stopping. For anytime recommendation under optional completion, the new bound quantifies how far the recommended configuration’s full-benchmark score can fall short of the best, even when no configuration has been fully evaluated.

Thank you for the responses. I have considered them and also read the rebuttals of the other reviewers.

The discussion has confirmed my concern that the paper has weakened theoretical contributions and novelty compared to what the paper claimed and had given an impression of. The main theoretical results do not apply to the anytime LCB algo evaluated in the paper's experiments, and the additional provided analysis (The B.1-B2) do not provide regret convergence guarantees for the anytime Gittins trajectory. The framework in Section 3.3 is also largely adapted from Xie(2026) which reduces the methodological's novelty.

When assessed as an empirical or methods paper, my concerns remain that the experimental results are not sufficiently rigorous. As the authors clarified in the other responses, the presented large gains (e.g. Fig 3) involved unfair recommendation rules and under matched setting the results became mixed. The author's new experiments with MF-KG was a good step to add a relevant baseline, but it is a well-known computationally intensive method. Standard scalable approaches e.g., BOHB etc could have been used and compared against, but MF-KG was used instead with computational cost cited as justification for GittinsEval. The revised paper would benefit from results for the unfinished key benchmark MMLU as well as these more scalable methods. The ablations on cross-configuration correlations also highlights GittinsEval's limitations on structured configuration spaces, and a more thorough analysis would strengthen the paper.

Overall, given my concerns above regarding both the narrower theoretical contributions and gaps in empirical rigor, I maintain my score. The paper already has significant edits as seen in the edited markup, and would benefit from more revisions as well given the above.

Comments on the paper

2 comments

Dear reviewers,

The author-reviewer discussion period is approaching the deadline. Please read through the author's rebuttals and update your reviews. Thank you for your time and work.

Best Regards, AC.

AuthorsOpenReview ↗

Summary of Key Clarifications and Additional Evidence

We thank all three reviewers for their constructive feedback. As the discussion period concludes, we would like to summarize how we have addressed the main concerns raised across the reviews.

1. Methodological contributions and broader applicability. Existing Gittins-index theory provides Bayesian-optimal allocation and stopping under required completion, where only fully evaluated configurations can be recommended. We extend this framework to support anytime recommendation under optional completion, develop the corresponding full-benchmark empirical-target dynamics, and provide an efficient computational realization. The resulting framework also applies to a broader class of cost-aware candidate-selection problems beyond LLM evaluation.

2. Theoretical guarantees for anytime recommendation. We established two new theoretical guarantees for the LCB-style recommendation rule (Theorems B.1–B.2), supporting our motivation of reducing uncertainty in early recommendations while characterizing the associated regret trade-off. These results complement our empirical findings of more stable recommendations and improved realized simple regret, without claiming Bayesian optimality for the anytime recommendation rule.

3. Stronger baselines and controlled comparisons. Following the reviewers' suggestions, we added multi-fidelity Bayesian optimization, Bayesian-bandit Thompson sampling, and stronger PromptEval baselines. While these methods improve upon several existing baselines, GittinsEval generally achieves low simple regret at lower evaluation costs, while multi-fidelity Bayesian optimization incurs substantially greater computational overhead. We also conducted detailed, apple-to-apple comparisons between GittinsEval and Bayesian-bandit Thompson sampling, examining allocation and recommendation effects, cross-configuration correlations, and possible explanations for the observed performance differences.

We have also improved the clarity of the problem formulation, methodological presentation, related-work positioning, and empirical results. We appreciate Reviewer dNrr's explicit acknowledgment that these concerns, together with the Thompson-sampling comparisons, have been satisfactorily addressed.

We hope the final assessments will reflect these clarifications and the additional theoretical and empirical evidence presented during the discussion.

Thank you again for your time and consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.