Source-linked AI summary

Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices

Qian Xie, Yueli He, Nairen Cao

arXiv:2609.25645v2cs.LGcs.CLstat.ML

TL;DR

Exhaustive evaluation of LLM configurations across benchmark items is costly. GITTINSEVAL uses cost-aware Bayesian Gittins allocation and an anytime recommendation rule. Across benchmarks, it is competitive and often reaches near-zero simple regret at a small fraction of exhaustive-evaluation cost.

  • Problem

    Exhaustive evaluation tests every configuration on every benchmark item, motivating a sequential policy for choosing what to evaluate next and when to stop while accounting for uncertainty.

    Source: §1 · p. 1
  • Method

    GITTINSEVAL models configuration selection as a cost-aware Bayesian bandit, using Gittins indices for allocation and stopping plus an LCB-style anytime recommendation over fully and partially evaluated configurations.

    Source: §1 · pp. 1–2
  • Results

    Across GSM8K, PIQA, AlpacaEval, and MMLU, GITTINSEVAL is consistently competitive and often attains near-zero simple regret using only 1%–2% of exhaustive-evaluation cost.

    Source: §1 · p. 2, §5 · p. 10
  • Takeaways & Limitations

    GITTINSEVAL’s anytime recommendation often uses 1%–2% of exhaustive-evaluation cost, while its adaptive stopping rule typically triggers at 1%–10%.

    Source: §5 · p. 10

    Its Bayesian optimality statement holds under the Gaussian surrogate, not as a distribution-free finite-sample identification guarantee for the realized response matrix.

    Source: §3.4 · p. 7

Abstract

from arXiv · show

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%.

1 INTRODUCTION

Exhaustive LLM configuration evaluation is costly, motivating sequential allocation that accounts for uncertainty and evaluation costs. GITTINSEVAL adapts Gittins indices for cost-aware recommendations and stopping, and is competitive across benchmarks, especially in large-example and large-candidate regimes.

1 INTRODUCTION

  • The motivating problem is choosing which configuration to evaluate next and when to stop, since exhaustive testing across all benchmark items incurs substantial cost.The candidate space can span models, prompts, temperatures, and decoding strategies.Source: §1 · p. 1
  • GITTINSEVAL models each configuration as an arm with noisy benchmark scores and configuration-dependent costs, using Gittins indices to balance estimated performance, uncertainty, and evaluation cost.The terminal objective rewards the quality of the final recommendation, not cumulative reward; near-optimal configurations can suffice when identifying the exact best would be disproportionately costly.Source: §1 · pp. 1–2
  • An LCB-style rule recommends among fully and partially evaluated configurations, while offline precomputation keeps online updates lightweight.The classical policy restricts terminal recommendations to completed arms; the extension incorporates posterior uncertainty in recommendations before full evaluation.Source: §1 · p. 2
  • Across GSM8K, PIQA, AlpacaEval, and MMLU, GITTINSEVAL is competitive, with strong gains over configuration-level Bayesian optimization on large-example benchmarks and cost-unaware bandits on large-candidate tasks.It often reaches near-zero simple regret using a small fraction of exhaustive-evaluation cost.Source: §1 · p. 2

1.1 RELATED WORK

  • Prior work includes adaptive bandit and racing methods, configuration-level Bayesian optimization, and approaches that share information across configurations or examples; GITTINSEVAL instead uses Bayesian beliefs over each configuration’s benchmark mean.Configuration-level Bayesian optimization typically evaluates each selected configuration on the entire benchmark, whereas GITTINSEVAL updates beliefs using example-level outcomes.Source: §1 · p. 1, §1.1 · pp. 2–3

2 COST-AWARE LLM CONFIGURATION RECOMMENDATION

The paper frames LLM configuration recommendation as sequential, cost-aware evaluation of benchmark examples, ending with a recommendation. It considers both returning a recommendation under a fixed budget and stopping adaptively when further evaluation is not worthwhile.

2.1 PROBLEM SETUP

  • The objective is to identify a high-performing configuration while minimizing cumulative evaluation cost, with policies querying configurations in batches and accounting for configuration-dependent per-example costs.The setup allows a single example as a batch and returns a recommendation when evaluation terminates.Source: §2.1 · p. 3

2.2 PROBLEM FORMULATIONS

  • Under a fixed evaluation budget, the anytime formulation returns a recommendation that may be an unfinished configuration and seeks low expected simple regret across budgets.The setup permits recommendations after any allocation step, even when the chosen configuration is incomplete.Source: §2.2 · p. 3, §2.1 · p. 3
  • The adaptive-stopping formulation trades recommendation quality against further evaluation cost, requiring policies to evaluate unfinished configurations and recommend completed ones.GITTINSEVAL’s Gittins allocation and stopping policy is derived from this formulation.Source: §2.2 · pp. 3–4
  • For finite benchmarks, GITTINSEVAL adapts the Gittins construction to empirical means and adds an LCB-style recommendation across configurations; the overview shows batch selection, posterior updates, and stopping.The figure’s recommendation score is the posterior mean minus one posterior standard deviation; stopping occurs when the highest-index configuration is fully evaluated.Source: Figure 1 · p. 4, §2.2 · p. 4

3 GITTINS INDEX POLICY FOR COST-AWARE BAYESIAN EVALUATION

GITTINSEVAL models configuration evaluation as cost-aware Bayesian bandit allocation and stopping, then extends the policy to recommend partially evaluated configurations. Its Gittins indices can be precomputed offline, leaving lightweight online updates and decisions.

3.1 BAYESIAN LATENT-MEAN MODEL AND POSTERIOR UPDATES

  • Each batch supplies a Gaussian-approximated observation of an arm’s latent mean, with fixed observation noise producing a deterministic posterior-variance schedule.The posterior mean evolves as a Gaussian random walk, and arms with the same prior variance and noise share that schedule.Source: §3.1 · pp. 4–5

3.2 POSTERIOR DYNAMICS AND THE GITTINS POLICY

  • The cost-aware Gittins index balances an arm’s current posterior mean against its evaluation cost, uncertainty, and remaining horizon to guide allocation and stopping.The index rises when an arm looks promising, uncertainty increases information value, or evaluation becomes cheaper.Source: §3.2 · pp. 5–6

3.3 EFFICIENT GITTINS INDEX COMPUTATION

  • FFT-accelerated precomputation takes O(HP log P) time and O(P) working memory; afterward, index lookup is O(1) and selecting among K arms is O(K).The offline computation replaces O(HP^2) explicit summation, so online allocation needs only posterior updates, root lookups, and index comparisons.Source: §3.3 · p. 6

3.4 EMPIRICAL-MEAN ALLOCATION, STOPPING, AND ANYTIME RECOMMENDATION

  • For finite response matrices, the method targets each configuration’s full-row empirical mean, which remains unknown until that row is exhaustively observed.Under the Gaussian surrogate, the posterior mean of this target follows a Gaussian random walk at batch boundaries.Source: §3.4 · pp. 6–7
  • Under the Gaussian surrogate and stated batch-level assumptions, the exact empirical-target Gittins policy is optimal among required-completion policies acting at batch boundaries.It evaluates the unfinished arm with the largest index unless a completed arm attains the maximum, in which case it stops and recommends a completed arm with the largest terminal index.Source: §3.4 · p. 7
  • The anytime rule recommends the configuration with the highest uncertainty-penalized LCB-style score, including when no configuration has completed its benchmark.The penalty discounts poorly evaluated arms for reporting without changing the Gittins indices, sampling trajectory, or stopping time.Source: §3.4 · p. 7

3.5 DESIGN CHOICES FOR LLM BENCHMARKS

  • The benchmark design uses a general N(0.5, 0.04) prior, a fixed conservative observation-noise approximation, and costs scaled from per-example API-price proxies.A common difficulty-bucket prior is also tested; the cost-scaling factor controls the relative expense of evaluation and affects stopping.Source: §3.5 · pp. 7–8

4 EXPERIMENTS

Experiments compare GITTINSEVAL with bandit and configuration-level Bayesian optimization baselines across four benchmarks, under unit-cost and heterogeneous-cost settings. GITTINSEVAL reaches low regret early on large-example benchmarks and large-candidate MMLU tasks, with stopping typically well before the evaluation budget is exhausted.

Benchmarks

  • The experiments use completed response matrices for GSM8K, PIQA, AlpacaEval, and MMLU, with 122, 103, 152, and 1,500 arms per task or subject, respectively.MMLU covers 57 subject datasets; GSM8K and PIQA each contain 1,000 examples, while AlpacaEval contains 805 instructions.Source: §4 · p. 8

Experimental conditions

  • Policies are compared under unit and model-price-proxy cost settings, using simple regret against cumulative evaluation cost and a nominal budget of 10% of exhaustive evaluation.Bayesian optimization evaluates complete configurations; GITTINSEVAL and UCB-E use batch size 8 in the main large-example plots, while LRF uses 32.Source: §4 · pp. 8–9

Main findings

  • On GSM8K, PIQA, and AlpacaEval, GITTINSEVAL reaches low simple regret earlier than configuration-level Bayesian optimization, while also markedly outperforming LRF.The comparison is shown under both unit-cost and cost-aware evaluation.Source: Figure 2 · p. 9, §4 · p. 10

Implementation and reporting

  • GITTINSEVAL precomputes prior-variance, batch-noise, cost, and horizon schedules, then uses posterior updates, moment computation, and root-table lookup online.Figures 2 and 3 show raw simple-regret curves by cumulative exhaustive-evaluation cost; shaded bands denote one standard error and dashed lines mark mean stopping times.Source: §4 · pp. 9–10

Main findings

  • On MMLU with 1,500 arms per subject, GITTINSEVAL-S reaches low regret earlier than frequentist baselines and is stronger across most size–difficulty buckets.LRF has substantially higher aggregate simple regret than UCB-E.Source: Figure 3 · p. 10, §4 · p. 10
  • Across benchmarks, GITTINSEVAL stopping typically occurs at 1–10% of exhaustive-evaluation cost, after regret curves flatten and earlier than Bayesian optimization stopping times or fixed-budget endpoints.Prior calibration matters most on challenging MMLU subjects; the general prior remains competitive on simpler tasks.Source: §4 · p. 10

5 CONCLUSION

The conclusion presents GITTINSEVAL as a cost-aware Bayesian bandit method for adaptive benchmark-query allocation. It reports competitive performance across benchmarks, with near-zero regret often reached at a small fraction of exhaustive cost and stopping at 1–10%.

Conclusion

  • GITTINSEVAL adaptively allocates benchmark queries using precomputed Gittins indices in a cost-aware Bayesian bandit method.The method is presented as a framework that may extend to evaluation problems with similar modeling and decision structure.Source: §5 · p. 10
  • Across benchmarks, GITTINSEVAL is consistently competitive, with stronger gains over configuration-level Bayesian optimization on large-example benchmarks and cost-unaware bandit baselines in large-candidate tasks.Source: §5 · p. 10
  • Near-zero simple regret is often attained at 1%–2% of exhaustive-evaluation cost, while adaptive stopping typically triggers at 1%–10%.Source: §5 · p. 10

AI USE STATEMENT

The authors report using generative-AI tools for literature discovery, research support, manuscript drafting and revision, and mathematical derivations. They state that they checked the outputs, revised them as needed, and take responsibility for the paper.

AI use

  • Generative-AI tools assisted literature discovery, research ideation and execution, manuscript drafting and revision, and writing clarity.Source: AI USE STATEMENT · p. 11
  • The tools also helped work through detailed derivations and proof steps from author-provided sketches and arguments.Source: AI USE STATEMENT · p. 11
  • The authors checked cited sources, derivations, and AI-assisted text, revised them as needed, and take full responsibility for the paper’s contents.Source: AI USE STATEMENT · p. 11
  • The experiments evaluate precomputed response matrices and did not query model APIs to generate new responses.Source: AI USE STATEMENT · p. 11

REPRODUCIBILITY STATEMENT

The reproducibility statement maps the paper’s methods, assumptions, data, and experimental settings to the appendices. Its Gaussian random-walk details describe posterior updates for an arm under a fixed-noise likelihood.

REPRODUCIBILITY STATEMENT

  • Appendix A gives theoretical assumptions and proofs; appendices B–E document recommendation and index construction, data, experimental procedures, and additional results.The experiments use precomputed response data rather than new LLM API calls.Source: REPRODUCIBILITY STATEMENT · p. 11

A.1 GAUSSIAN RANDOM-WALK DETAILS

  • For an arm, the next batch mean is modeled under a fixed-noise Gaussian likelihood, and Bayes’ rule yields a Gaussian posterior update.Source: §A.1 · pp. 13–14
  • The posterior mean follows a Gaussian random-walk transition when the arm is selected, while its variance follows a deterministic schedule indexed by local pulls.The variance schedule is identical across arms only when their initial variances and fixed noise levels match.Source: §A.1 · pp. 13–14

A.2 PROOF OF BAYESIAN OPTIMALITY

The proof reduces required-completion evaluation to independent Markov chains, establishing a Gittins allocation and stopping rule. Centering the continuation value yields a one-dimensional index computation, implemented with an FFT-based backward update.

A.2 PROOF OF BAYESIAN OPTIMALITY

  • The optimal policy samples the unfinished arm with the largest Gittins index and stops when a completed arm attains the maximum, recommending the completed arm with the highest posterior mean.The reduction uses independent arm-wise Markov states, with each pull incurring its own cost and completion providing the posterior mean as terminal reward.Source: §A.2 · pp. 14–15

A.3 ONE-DIMENSIONAL GITTINS INDEX COMPUTATION

  • Centering the posterior mean against the outside reward makes the continuation recursion one-dimensional; continuing is worthwhile exactly when q_n(s − α) > 0.The Gittins index is determined by the crossing point of this centered continuation value.Source: §A.3 · p. 16

A.4 FFT IMPLEMENTATION

  • The FFT implementation reduces the backward update to O(P log P) time and O(P) working memory per stage, or O(HP log P) across H stages.Approximation relative to the continuous dynamic program remains from grid, boundary-extension, root-discretization, and floating-point effects.Source: §A.4 · p. 17

B ANYTIME RECOMMENDATION FOR FULL-BENCHMARK EMPIRICAL MEANS

For fixed finite benchmarks, the section adapts the Gittins policy to the full-row empirical mean and provides recommendations before all arms are complete. A posterior-uncertainty penalty can stabilize recommendations, though the single-matrix diagnostic does not show regret improvement in every prior setting.

B ANYTIME RECOMMENDATION FOR FULL-BENCHMARK EMPIRICAL MEANS

  • The full-benchmark empirical target has a posterior mean and variance that account for both latent-mean uncertainty and unobserved example scores, with uncertainty collapsing at completion.The moments are derived under a Gaussian approximation, including for binary or bounded benchmark scores.Source: B ANYTIME RECOMMENDATION FOR… · p. 17
  • At batch boundaries, the empirical-target state forms independent Markov chains under the Gaussian surrogate, so the Gittins policy is optimal for required completion among policies acting at those boundaries.The implementation may stop at the inherited signal, a budget, or an external interruption, while keeping an anytime recommendation available.Source: B ANYTIME RECOMMENDATION FOR… · p. 18
  • The anytime score subtracts posterior uncertainty so a sparsely observed high estimate is not treated like an equally high estimate supported by more observations.The penalty affects recommendations, not the Gittins sampling trajectory or stopping time.Source: B ANYTIME RECOMMENDATION FOR… · pp. 18–19
  • Under the general prior, subtracting one posterior standard deviation reduced recommendation switches from 139 to 38 and budget-weighted mean simple regret from 0.04824 to 0.02903; under the data-specific prior, regret rose from 0.03128 to 0.03177.These are single-seed observations on one GSM8K response matrix, and all four recommendations had zero regret at the budget endpoint.Source: B ANYTIME RECOMMENDATION FOR… · p. 19

C.1 DATASET DESCRIPTION

The evaluation uses response matrices from GSM8K, PIQA, AlpacaEval, and MMLU, with different arm definitions and benchmark sizes across datasets. GSM8K and PIQA have multiple generated matrices, while AlpacaEval uses one fixed matrix.

C.1 DATASET DESCRIPTION

  • GSM8K and PIQA each have 1,000 examples and five independently generated response matrices, with 122 and 103 arms, respectively.The response matrices contain subsets of 132 possible model–configuration arms; variation across matrices mainly reflects LLM response-generation randomness.Source: §C.1 · p. 19
  • AlpacaEval contains 152 model arms and 805 instructions, with continuous pairwise scores against the GPT-4 Turbo baseline and one fixed response matrix.The two degenerate GPT-4 rows are excluded; trials vary by randomized seed.Source: §C.1 · p. 20
  • MMLU is treated as 57 separate subject problems, each with 1,500 model–prompt arms formed from 15 LLM configurations and 100 prompting techniques.The benchmark has approximately 14,000 examples in total, with the number varying by subject.Source: §C.1 · p. 20

C.2 DATASET STATISTICS

The dataset statistics describe distributions of per-arm quality and prior placement. GSM8K and PIQA show stable aggregate distributions across generated matrices, while MMLU subjects are grouped by empirical difficulty into prior buckets.

C.2 DATASET STATISTICS

  • GSM8K and PIQA distributions are highly stable across five response-matrix seeds; GSM8K has lower overall accuracy, while PIQA’s high-quality arms are more tightly concentrated.Figure 4 displays per-arm accuracy for these datasets and pairwise scores for AlpacaEval, marking empirical mean, best arm, and prior mean.Source: §C.2 · p. 20, Figure 4 · p. 22
  • MMLU subjects are grouped by empirical mean arm quality into high-, medium-, and low-prior buckets with prior means µ0 = 0.75, 0.6, and 0.4, respectively.The buckets correspond to easy, medium-difficulty, and hard subjects; Table 1 also reports subject size by example count.Source: §C.2 · p. 20, Table 1 · p. 21

D EXPERIMENT SETUP AND IMPLEMENTATION DETAILS

The experiments use precomputed response matrices to simulate adaptive evaluation, with repeated randomized trials and model-level cost proxies. They compare recommendation and stopping behavior under specified Gaussian observation and shared-prior assumptions.

D EXPERIMENT SETUP AND IMPLEMENTATION DETAILS

  • Policy runtimes measure allocation overhead in simulations using precomputed response matrices, not online LLM inference.Each policy observes selected arm–question entries, while full-row means supply simple-regret targets.Source: D EXPERIMENT SETUP AND IMPLEMENTATION… · p. 26
  • GSM8K and PIQA average five response matrices with 20 trials each, while AlpacaEval uses one fixed matrix and MMLU aggregates 20 trials per subject.Bayesian-optimization baselines use the same randomized-trial structure on converted inputs.Source: D EXPERIMENT SETUP AND IMPLEMENTATION… · p. 26
  • The anytime recommendation selects the arm maximizing posterior mean minus a variance penalty, while simple regret uses its actual full-row mean; the penalty does not alter allocation or stopping.The required-completion stopping rule stops when an arm with the largest numerical Gittins index is fully observed.Source: D EXPERIMENT SETUP AND IMPLEMENTATION… · p. 26
  • Bayesian-optimization warm-up evaluates about 5% of arms on their full rows, whereas LRF warm-up samples 5% of arm–example entries.The corresponding initial configuration counts are 6, 5, 8, and 75 for GSM8K, PIQA, AlpacaEval, and each MMLU subject.Source: D EXPERIMENT SETUP AND IMPLEMENTATION… · p. 26
  • Cost-aware bandit costs are model-level proxies with a fixed benchmark token ratio, so examples queried from one arm share a cost; converted BO inputs price full-configuration evaluation.GSM8K/PIQA arms are model-plus-prompting configurations, MMLU arms are model–prompt pairs, and AlpacaEval arms are individual models.Source: D EXPERIMENT SETUP AND IMPLEMENTATION… · pp. 27–28
  • Binary-accuracy batch means use variance 1/(4B), while AlpacaEval uses the same conservative variance bound under a conditional-independence approximation.AlpacaEval entries are continuous preference scores in [0, 1], and its fixed working variance is not an empirical estimate.Source: D EXPERIMENT SETUP AND IMPLEMENTATION… · p. 31

E.1 ABLATION STUDIES

The ablations examine recommendation rules, batch sizes, cost scaling, and common priors. Results show how these choices trade early regret and stopping behavior, while the LCB recommendation can sharply reduce regret on selected settings without changing allocation or stopping.

Choice of common prior

  • The common-prior ablation compares GittinsEval-G’s general prior with GittinsEval-S’s data-specific common prior to test the contribution of shared prior information.The comparison does not give arms different prior means.Source: §E.1 · p. 31

Batch size

  • Smaller batches provide more frequent adaptation but noisier observations, while larger batches reduce approximation error and posterior noise; LRF uses B = 32 because smaller batches are prohibitively slow.Bayesian-optimization baselines operate at configuration level and do not use a bandit batch size.Source: Table 6 · p. 31, §E.1 · p. 32
  • For GSM8K, PIQA, and AlpacaEval, B = 8 gives the best early sample efficiency, while MMLU’s lowest-overall-regret batches are B = 2, 4, and 8 for small, medium, and large subjects.Larger batches generally update less often and can be less efficient at low budgets; MMLU medium and large groups also tend to stop later with larger batches.Source: §E.1 · p. 32, Figure 8 · p. 33, Figure 9 · p. 33

Cost-scaling factor

  • The cost-scaling sweep tests λ values 10−3, 10−4, and 10−5, with 10−4 used in main figures as a balance between stopping early and continued exploration.The factor applies to common unit costs in unit-cost experiments and original per-evaluation costs in cost-aware experiments.Source: §E.1 · p. 32
  • Across GSM8K, PIQA, and AlpacaEval, λ = 10−3 often stops too aggressively, whereas λ = 10−5 generally needs more evaluation before stopping; λ = 10−4 provides the most reliable trade-off.Across MMLU size groups, λ = 10−4 reduces regret quickly while retaining reasonable stopping times; the large group has only five subjects and some wide error bands.Source: §E.1 · p. 32, Figure 10 · p. 34, Figure 11 · p. 34

Choice of recommendation rule

  • At 2% of exhaustive-evaluation cost, LCB lowers GSM8K mean simple regret from 0.0780 ± 0.0121 to 0.0080 ± 0.0013, and MMLU Hard-Large aggregate raw simple regret from 0.0828 ± 0.0143 to 0.0018 ± 0.0004.Both recommendations use the same allocation trajectories and stopping times, so the improvement is attributed to stabilizing the anytime recommendation.Source: §E.1 · p. 35, Figure 12 · p. 35

E.2 PER-SUBJECT MMLU RESULTS

Across MMLU difficulty buckets, GittinsEval-S generally reaches lower simple regret earlier than UCB-E and GittinsEval-G, suggesting data-specific priors are broadly helpful, especially on harder subjects. The accompanying runtime comparisons report Gittins close to UCB-E and LRF much slower on larger MMLU tasks.

E.2 PER-SUBJECT MMLU RESULTS

  • Across MMLU subjects, GittinsEval-S generally reaches lower simple regret earlier than UCB-E and GittinsEval-G, especially on more challenging subjects.The subjects are grouped by empirical mean arm quality, with prior means of 0.75, 0.6, and 0.4 for easy, medium, and hard buckets.Source: §E.2 · pp. 35–36
  • Figures 13–18 plot per-subject simple regret against evaluation cost for easy, medium, and hard MMLU subjects under both unit-cost and cost-aware settings.S, M, and L denote matrix size and use B = 2, 4, and 8, respectively; LRF uses B = 32.Source: Figure 13 · p. 36, Figure 14 · p. 37, Figure 15 · p. 38

E.3 COMPUTATIONAL OVERHEAD COMPARISON

  • Gittins runtime is generally close to UCB-E, whereas LRF is much slower on larger MMLU tasks under both unit costs and cost-aware evaluation.These figures report total wall-clock runtime across completed runs, with markers for mean estimated stopping time.Source: Figure 19 · p. 42, Figure 20 · p. 42
Loading 2609.25645v2…