基于贝叶斯老虎机 Gittins 指数的高效成本感知 LLM 评估

# Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices
Source: [https://arxiv.org/html/2609.25645](https://arxiv.org/html/2609.25645)
Qian Xie Yueli He Nairen Cao22footnotemark:2††thanks:Corresponding authors: Qian Xie \(qx66@cornell\.edu\); Nairen Cao \(caonairen@sufe\.edu\.cn\)\.New York University Shanghai University of Finance and Economics

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

Code:[github\.com/QianJaneXie/BanditGittinsEval](https://github.com/QianJaneXie/BanditGittinsEval)

## 1Introduction

Modern LLM evaluation requires selecting among a combinatorial space of configurations—such as models, prompts, temperatures, and decoding strategies—across benchmarks like GSM8K, PIQA, and MMLU\([Cobbe et al\., 2021](https://arxiv.org/html/2609.25645#bib.bib6);[Bisk et al\., 2020](https://arxiv.org/html/2609.25645#bib.bib7);[Hendrycks et al\., 2020](https://arxiv.org/html/2609.25645#bib.bib9)\)\. Exhaustive evaluation—testing every configuration on every benchmark item—incurs substantial cost and is often unnecessary: adaptive evaluation can allocate fewer queries to weak candidates and concentrate evaluation on promising or uncertain ones\. This motivates a fundamental sequential decision problem:*which configuration should be evaluated next, and how can uncertainty be incorporated to make reliable recommendations?*A practical method can further provide a principled stopping rule\.

Bandit and racing algorithms provide a natural framework for adaptive evaluation\([Zhou et al\., 2025](https://arxiv.org/html/2609.25645#bib.bib1);[Polo et al\., 2024](https://arxiv.org/html/2609.25645#bib.bib10);[Shi et al\., 2024](https://arxiv.org/html/2609.25645#bib.bib12);[Lyu et al\., 2026](https://arxiv.org/html/2609.25645#bib.bib17)\)\. Some methods further share information across configurations or examples through low\-rank response models, item\-response models, prompt embeddings, or response\-vector similarities\. A complementary paradigm is configuration\-level Bayesian optimization\([Snoek et al\., 2012](https://arxiv.org/html/2609.25645#bib.bib15)\), which adaptively chooses candidates but typically evaluates each on the entire benchmark\. However, existing methods predominantly operate in cost\-unaware or frequentist regimes\. 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\. This motivates a cost\-aware Bayesian approach that jointly accounts for estimated performance, uncertainty in those estimates, and evaluation cost\.

We introduceGittinsEval, a cost\-aware LLM evaluation framework that models configuration selection as a Bayesian bandit\([Gittins et al\., 2011](https://arxiv.org/html/2609.25645#bib.bib5)\)\. Each configuration is an arm whose evaluations reveal noisy benchmark scores at configuration\-dependent costs\. Here,*Bayesian bandit*describes the familiar arm\-based sampling model, not a cumulative\-reward objective: benchmark scores are measurements, and the payoff is the quality of the final recommendation\. Our goal is therefore to identify a high\-performing configuration at low evaluation cost\. Rather than posing evaluation as exact best\-arm identification, we assess recommendation quality through simple regret or net utility, so a near\-optimal configuration can be sufficient when distinguishing the exact best would require disproportionate evaluation cost\. Under a terminal\-recommendation objective, this formulation is an instance of Markov chain selection\([Dumitriu et al\., 2003](https://arxiv.org/html/2609.25645#bib.bib13);[Scully and Terenin, 2025](https://arxiv.org/html/2609.25645#bib.bib3)\)\.GittinsEvaluses the corresponding Gittins indices to account for estimated performance, uncertainty, and evaluation cost\. For this problem, the classical Gittins policy evaluates the arm with the largest index and stops once a completed arm attains the largest index\.

MakingGittinsEvalpractical for LLM benchmarks hinges on two key components\. First, it is computationally efficient, requiring only lightweight updates during evaluation after offline precomputation\. Second, the classical Gittins policy above restricts terminal recommendations to fully evaluated arms, whereas practical LLM evaluation need not require full evaluation before recommending a configuration\. We therefore add an LCB\-style anytime recommendation rule that accounts for posterior uncertainty when selecting among fully and partially evaluated configurations\.

Across extensive experiments on GSM8K, PIQA, AlpacaEval, and MMLU,GittinsEvalis consistently competitive, with particularly strong advantages in two regimes\. On large\-example benchmarks, it vastly outperforms configuration\-level Bayesian optimization, which evaluates each selected configuration on the entire benchmark rather than allocating partial batches across candidates\. On large\-candidate MMLU tasks \(1,500 arms per subject\), it decisively outperforms cost\-unaware frequentist baselines, which do not use evaluation costs or Bayesian priors in their allocation rules\. Across these settings,GittinsEvalreaches near\-zero simple regret using only a small fraction of the exhaustive\-evaluation cost\.

Our core contributions are:

- •We formulate LLM configuration selection as a cost\-aware Bayesian bandit problem that incorporates heterogeneous evaluation costs and prior information, and establish its connection to classical Markov chain selection, providing the theoretical basis forGittinsEval\.
- •We adapt the Gittins framework to practical LLM evaluation through modeling and algorithmic design choices that enable efficient offline index precomputation and lightweight online decision\-making, and extend it with an LCB\-style anytime recommendation rule over both fully and partially evaluated configurations\.
- •We show empirically thatGittinsEvalis consistently competitive across diverse LLM evaluation settings, with particular advantages in large\-example and large\-candidate regimes, often achieving near\-zero simple regret at a small fraction of the exhaustive\-evaluation cost\.

### 1\.1Related Work

#### Efficient LLM evaluation\.

Recent work has studied how to reduce the cost of evaluating many LLM configurations by adaptively allocating benchmark queries\. BanditEval uses UCB\-E for best\-arm identification and introduces UCB\-E\-LRF \(hereafter LRF\), which exploits low\-rank structure in the response matrix\([Zhou et al\., 2025](https://arxiv.org/html/2609.25645#bib.bib1)\)\. TRIPLE combines successive halving with a predictive model of final arm performance\([Shi et al\., 2024](https://arxiv.org/html/2609.25645#bib.bib12)\), while SySRs exploits similarities among model response vectors within a successive\-rejection framework\([Lyu et al\., 2026](https://arxiv.org/html/2609.25645#bib.bib17)\)\. PromptEval uses configuration covariates to improve multi\-prompt evaluation and best\-arm identification\([Polo et al\., 2024](https://arxiv.org/html/2609.25645#bib.bib10)\)\. These methods primarily target efficient identification under a fixed evaluation budget\. Concurrent work has also explored complementary forms of cost\-aware LLM evaluation, including best\-model identification with low\-rank response\-matrix structure\([Tolochinsky et al\., 2026](https://arxiv.org/html/2609.25645#bib.bib23)\), selective human auditing of LLM judges\([Ao et al\., 2026](https://arxiv.org/html/2609.25645#bib.bib24)\), and budget\-aware multi\-agent judging through debate and deliberation\([Harrasse et al\., 2026](https://arxiv.org/html/2609.25645#bib.bib25)\)\. Our setting additionally allows heterogeneous evaluation costs and Bayesian prior information, and we evaluate recommendation quality throughout the allocation process using simple regret\.

#### Bayesian optimization\.

Configuration\-level Bayesian optimization places a surrogate prior, typically a Gaussian process, over performance as a function of the configuration and can account for heterogeneous query costs\([Snoek et al\., 2012](https://arxiv.org/html/2609.25645#bib.bib15)\)\. Our approach instead places Bayesian beliefs on each configuration’s benchmark mean and updates them through repeated example\-level outcomes; its uncertainty is therefore within configurations rather than primarily across them\. Multi\-fidelity Bayesian optimization is also related through its use of cheaper approximations\([Klein et al\., 2017](https://arxiv.org/html/2609.25645#bib.bib19);[Kandasamy et al\., 2017](https://arxiv.org/html/2609.25645#bib.bib20);[Wu et al\., 2020](https://arxiv.org/html/2609.25645#bib.bib21)\)\.

#### Gittins indices and terminology\.

Gittins indices are most familiar from the classical Bayesian multi\-armed bandit, which maximizes expected discounted cumulative reward over an infinite sequence of arm pulls\([Gittins, 1979](https://arxiv.org/html/2609.25645#bib.bib4);[Gittins et al\., 2011](https://arxiv.org/html/2609.25645#bib.bib5)\)\. Following[Scully and Terenin \(2025\)](https://arxiv.org/html/2609.25645#bib.bib3), we use*Markov chain selection*for the broader structure that unifies Gittins\-index applications: at each step, the decision maker chooses one of several independent Markov chains to advance\. This name separates the indexable structure from the particular reward objective\. Our method uses a terminal\-selection objective—benchmark observations are costly measurements, and reward comes from the final recommended configuration—and is closely related to terminal\-state problems such as the golf problem of[Dumitriu et al\. \(2003\)](https://arxiv.org/html/2609.25645#bib.bib13)\. Pandora’s\-box problems provide a related inspect\-once setting that has been used for cost\-aware Bayesian optimization and stopping\([Xie et al\., 2024](https://arxiv.org/html/2609.25645#bib.bib11);[Xie et al\., 2025](https://arxiv.org/html/2609.25645#bib.bib14)\)\. We retain*Bayesian bandit*as a familiar description of our Bayesian arm\-sampling model, while using*Markov chain selection*when referring to the decision framework that establishes the Gittins policy\.

## 2Cost\-Aware LLM Configuration Recommendation

### 2\.1Problem Setup

We considerKKcandidate LLM configurations evaluated across a benchmark ofNNexamples\. Evaluating configurationk∈\[K\]k\\in\[K\]on examplej∈\[N\]j\\in\[N\]yields a scalar scoreZk,j∈ℝZ\_\{k,j\}\\in\\mathbb\{R\}\(\[0,1\]\[0,1\]in this work\), modeled as an observation with latent meanθk\\theta\_\{k\}\. The latent meanθk\\theta\_\{k\}represents configurationkk’s expected performance on the underlying example distribution and is our primary evaluation target\.

An adaptive evaluation policy sequentially queries configurations in batches \(with a single example as the special caseB=1B=1\) and terminates by returning a recommendationk^T\\hat\{k\}\_\{T\}\. LetAtA\_\{t\}andbtb\_\{t\}denote the configuration and batch size at allocation steptt\. Ifc~k\\widetilde\{c\}\_\{k\}is the raw per\-example cost of configurationkk, the effective cost of this batch isck,bt:=λ​bt​c~k\>0c\_\{k,b\_\{t\}\}:=\\lambda b\_\{t\}\\widetilde\{c\}\_\{k\}\>0\. For batch sizeBB, we abbreviateck:=ck,Bc\_\{k\}:=c\_\{k,B\}\. Our goal is to identify a high\-performing configuration while minimizing cumulative evaluation cost\.

When each configuration has a finite evaluation horizon, we call a configuration*completed*once all allowed benchmark observations have been collected\. In practical LLM evaluation, however, completion is optional: an unfinished configuration remains eligible for recommendation based on the observations collected so far\. We therefore allow an anytime recommendation after any allocation step, whether or not the recommended configuration is completed\.

### 2\.2Problem Formulations

We consider two complementary cost\-aware formulations\. The first targets*anytime recommendation*: under any externally specified evaluation budgetCC, the policy returns a recommendationk^TC\\hat\{k\}\_\{T\_\{C\}\}, which may be an unfinished configuration\. LetTCT\_\{C\}denote the last allocation step satisfying∑t=1TCcAt,bt≤C\\sum\_\{t=1\}^\{T\_\{C\}\}c\_\{A\_\{t\},b\_\{t\}\}\\leq C\. The policy’s budget\-indexed simple regret is

Rπ​\(C\):=𝔼π​\[maxk∈\[K\]⁡θk−θk^TC\]\.R\_\{\\pi\}\(C\):=\\mathbb\{E\}\_\{\\pi\}\\\!\\left\[\\max\_\{k\\in\[K\]\}\\theta\_\{k\}\-\\theta\_\{\\hat\{k\}\_\{T\_\{C\}\}\}\\right\]\.We seek an anytime policy with lowRπ​\(C\)R\_\{\\pi\}\(C\)across evaluation budgets\.

The second targets*adaptive stopping*: rather than fixingCCin advance, the evaluator chooses when to stop by trading off recommendation quality against the cost of further evaluation\. We formulate this objective under required completion\. LetΠreq\\Pi^\{\\mathrm\{req\}\}denote policies that evaluate only unfinished configurations and recommend only completed ones\. Its expected net\-utility objective is

supπ∈Πreq𝔼π​\[θk^T−∑t=1TcAt,bt\]\.\\sup\_\{\\pi\\in\\Pi^\{\\mathrm\{req\}\}\}\\;\\mathbb\{E\}\_\{\\pi\}\\\!\\left\[\\theta\_\{\\hat\{k\}\_\{T\}\}\-\\sum\_\{t=1\}^\{T\}c\_\{A\_\{t\},b\_\{t\}\}\\right\]\.\(1\)The Gittins allocation and stopping policy underlyingGittinsEvalis derived from this adaptive\-stopping formulation\. For evaluation on a fixed finite benchmark, Section[3\.4](https://arxiv.org/html/2609.25645#S3.SS4)specializes the same Gittins construction to an observable empirical target and augments it with an LCB\-style recommendation over all configurations to provide the anytime output in the first formulation\. Thus, our method supports both anytime recommendation and adaptive stopping\.

In our experiments,c~k\\widetilde\{c\}\_\{k\}is derived from published API prices and is constant across examples for a given arm\. The factorλ\>0\\lambda\>0scales measurement cost to the utility of benchmark performance; a smaller final batch is automatically charged according to its actual sizebtb\_\{t\}\.

## 3Gittins Index Policy for Cost\-Aware Bayesian Evaluation

We developGittinsEvalby starting from the Gittins policy for Markov chain selection\. Throughout this section,ttdenotes the global allocation step, whilenndenotes the local number of batch pulls of a particular arm\. We first analyze the adaptive\-stopping formulation under required completion in a latent\-mean Gaussian model\. Each arm’s posterior mean evolves as a Gaussian random walk with a deterministic variance schedule\. The corresponding Gittins policy yields cost\-aware allocation indices and a stopping rule\. We then show how to precompute the indices efficiently, adapt the construction to full\-benchmark empirical means, and extend the required\-completion policy with an LCB\-style anytime recommendation for optional completion\. Figure[1](https://arxiv.org/html/2609.25645#S3.F1)summarizes the overall evaluation loop\.

Figure 1:Overview ofGittinsEval\. Each iteration evaluates a fresh batch from the selected response\-matrix row, uses a Gaussian approximation to its mean to update the posterior, recomputes the empirical\-target Gittins indices, and selects the highest\-index unfinished configuration for the next batch\. The updated posterior yields an anytime recommendation based on the posterior mean minus one posterior standard deviation\. The policy can return its current recommendation at any time or, under adaptive stopping, terminate once the highest\-index configuration is fully evaluated\. Highlighted cells mark the new batch; model names and values are illustrative\.### 3\.1Gaussian Bayesian Observation Model

Throughout, one pull means evaluating one batch\. Afternnlocal pulls of armkk, let𝒟k,n\\mathcal\{D\}\_\{k,n\}denote the batch means collected from that arm\. Suppose theiith pull evaluates a fresh batchℬk,i\\mathcal\{B\}\_\{k,i\}ofBBbenchmark examples\. The scalar observation used for posterior updating is

Y¯k,i:=1B​∑j∈ℬk,iZk,j\.\\overline\{Y\}\_\{k,i\}:=\\frac\{1\}\{B\}\\sum\_\{j\\in\\mathcal\{B\}\_\{k,i\}\}Z\_\{k,j\}\.Under the working population model, example scores are conditionally i\.i\.d\. givenθk\\theta\_\{k\}, so the batch mean has conditional meanθk\\theta\_\{k\}\. For binary correctness observations, its conditional variance isθk​\(1−θk\)/B\\theta\_\{k\}\(1\-\\theta\_\{k\}\)/B\. More generally, we use a Gaussian approximation to the batch mean and a fixed observation\-noise varianceτ2\\tau^\{2\}:

θk∼𝒩\(μ0,v0\),Y¯k,i∣θk∼𝒩\(θk,τ2\)\.\\theta\_\{k\}\\sim\\mathcal\{N\}\(\\mu\_\{0\},v\_\{0\}\),\\qquad\\overline\{Y\}\_\{k,i\}\\mid\\theta\_\{k\}\\sim\\mathcal\{N\}\(\\theta\_\{k\},\\tau^\{2\}\)\.\(2\)Section[3\.5](https://arxiv.org/html/2609.25645#S3.SS5)describes our choice ofτ2\\tau^\{2\}for binary and continuous benchmark scores\.

To state the posterior update compactly, fix a representative arm and suppress the arm index\. Afternnlocal pulls,

θ\|𝒟n∼𝒩⁡\(μn,vn\)\.\\theta\\mid\\mathcal\{D\}\_\{n\}\\sim\\mathcal\{N\}\(\\mu\_\{n\},v\_\{n\}\)\.After observingY¯n\+1\\overline\{Y\}\_\{n\+1\}, conjugacy gives

vn\+1\\displaystyle v\_\{n\+1\}=\(vn−1\+τ−2\)−1,\\displaystyle=\\left\(v\_\{n\}^\{\-1\}\+\\tau^\{\-2\}\\right\)^\{\-1\},\(3\)μn\+1\\displaystyle\\mu\_\{n\+1\}=μn\+vnvn\+τ2​\(Y¯n\+1−μn\)\.\\displaystyle=\\mu\_\{n\}\+\\frac\{v\_\{n\}\}\{v\_\{n\}\+\\tau^\{2\}\}\\left\(\\overline\{Y\}\_\{n\+1\}\-\\mu\_\{n\}\\right\)\.Under fixedτ2\\tau^\{2\}, the variance schedule is deterministic\. In particular,

vn−vn\+1=vn2vn\+τ2\.v\_\{n\}\-v\_\{n\+1\}=\\frac\{v\_\{n\}^\{2\}\}\{v\_\{n\}\+\\tau^\{2\}\}\.Thus, arms with the same initial variancev0v\_\{0\}and observation noiseτ2\\tau^\{2\}share the same posterior variance schedule\. The framework can also be extended to accommodate arm\-specific prior variances or noise levels\. Appendix[A\.1](https://arxiv.org/html/2609.25645#A1.SS1)provides the full derivation of the posterior update and the induced Gaussian random\-walk transition\.

### 3\.2Posterior Dynamics and the Gittins Policy

The posterior update also characterizes the future evolution of an arm’s posterior mean\. LetSnS\_\{n\}denote the posterior mean of a representative arm afternnlocal pulls, viewed as a random variable over future observations\. Conditional on the current realized stateSn=sS\_\{n\}=s, Eq\. \([3](https://arxiv.org/html/2609.25645#S3.E3)\) implies

Sn\+1\|Sn=s∼𝒩⁡\(s,vn2vn\+τ2\)\.S\_\{n\+1\}\\mid S\_\{n\}=s\\sim\\mathcal\{N\}\\left\(s,\\frac\{v\_\{n\}^\{2\}\}\{v\_\{n\}\+\\tau^\{2\}\}\\right\)\.\(4\)Hence the posterior mean follows a Gaussian random walk with a transition variance determined by the local pull count\.

The horizon is measured in batch pulls\. Fix a finite per\-arm horizonHH, so that an arm is completed afterHHbatches; for a benchmark withNNexamples and batch sizeBB,H:=⌈N/B⌉H:=\\lceil N/B\\rceil\. Its state is therefore\(Sn,n\)\(S\_\{n\},n\)\. Selecting an arm changes only that arm’s state and incurs its batch cost\. A smaller final batch, when needed, has a known stage\-specific noise variance and cost and is handled by the same construction\.

The Gittins construction reduces the multi\-arm allocation problem to a single\-arm stopping problem\. Intuitively, it asks:*how attractive must the best alternative be before we prefer to stop evaluating the current arm?*

Fix one arm with stateSn=sS\_\{n\}=s, pull costcc, and remaining horizonH−nH\-n, alongside an outside terminal rewardα\\alphaavailable from competing arms\. Forn<Hn<H, the local decision balances the continuation costccand future information gain against terminating with outside valueα\\alpha\. Consequently, the terminal value isVH​\(s,α\):=max⁡\{s,α\}V\_\{H\}\(s;\\alpha\):=\\max\\\{s,\\alpha\\\}, and forn<Hn<Hthe value function satisfies the Bellman recursion:

Vn​\(s,α\):=max⁡\{α,−c\+𝔼⁡\[Vn\+1​\(Sn\+1,α\)∣Sn=s\]\}\.V\_\{n\}\(s;\\alpha\):=\\max\\left\\\{\\alpha,\\;\-c\+\\mathbb\{E\}\[V\_\{n\+1\}\(S\_\{n\+1\};\\alpha\)\\mid S\_\{n\}=s\]\\right\\\}\.\(5\)Forn<Hn<H, the cost\-aware Gittins indexGnc​\(s\)G\_\{n\}^\{c\}\(s\)is the smallest outside value for which stopping is optimal:

Gnc​\(s\):=inf\{α∈ℝ:α≥−c\+𝔼⁡\[Vn\+1​\(Sn\+1,α\)∣Sn=s\]\}\.G\_\{n\}^\{c\}\(s\):=\\inf\\left\\\{\\alpha\\in\\mathbb\{R\}:\\alpha\\geq\-c\+\\mathbb\{E\}\[V\_\{n\+1\}\(S\_\{n\+1\};\\alpha\)\\mid S\_\{n\}=s\]\\right\\\}\.\(6\)The index is larger when the arm currently looks promising, when uncertainty creates greater value of information, or when evaluation is cheaper\.

At global allocation steptt, letnk​\(t\)n\_\{k\}\(t\)denote the number of pulls previously made from armkk\. For an unfinished arm,

Gk,t:=Gnk​\(t\)ck​\(μk,nk​\(t\)\)\.G\_\{k,t\}:=G\_\{n\_\{k\}\(t\)\}^\{c\_\{k\}\}\\left\(\\mu\_\{k,n\_\{k\}\(t\)\}\\right\)\.\(7\)For a completed arm,

Gk,t:=μk,H\.G\_\{k,t\}:=\\mu\_\{k,H\}\.In the required\-completion adaptive\-stopping formulation, the policy evaluates an unfinished arm with the largest index\. If an arm attaining the largest index is already completed, the policy stops and recommends a completed arm with the largest terminal index\. GittinsEval uses this allocation and stopping policy while retaining optional\-completion anytime recommendations\.

Since the arms evolve as independent Markov chains, the classical Markov\-chain selection theorem implies that this batch\-level Gittins policy is optimal for the latent\-mean required\-completion objective\([Dumitriu et al\., 2003](https://arxiv.org/html/2609.25645#bib.bib13);[Scully and Terenin, 2025](https://arxiv.org/html/2609.25645#bib.bib3)\)\. Appendix[A\.2](https://arxiv.org/html/2609.25645#A1.SS2)states the objective and policy class formally and gives the reduction\.

### 3\.3Efficient Gittins Index Computation

A direct dynamic\-programming computation of the Gittins index involves a continuous posterior\-mean state at every local stage\. In our Gaussian setting, however, translation invariance implies that the stopping problem depends on the posterior mean and the outside option only through their difference\. This reduces the computation to a one\-dimensional dynamic program and, ultimately, to one stage\-dependent stopping root that can be precomputed offline\.

The Gaussian transition in Eq\. \([4](https://arxiv.org/html/2609.25645#S3.E4)\) is translation invariant, and its variance schedule is deterministic\. Consequently, for fixed\(c,v0,τ2,H\)\(c,v\_\{0\},\\tau^\{2\},H\), the exact single\-arm index has the form

Gnc​\(s\)=s−rn​\(c,v0,τ2,H\),G\_\{n\}^\{c\}\(s\)=s\-r\_\{n\}\(c,v\_\{0\},\\tau^\{2\},H\),\(8\)wherernr\_\{n\}is a stage\-dependent stopping root that does not depend on the current posterior meanss\.

We compute these roots offline using a discretized dynamic program\. Let

\{r^n​\(c,v0,τ2,H\)\}n=0H−1\\left\\\{\\widehat\{r\}\_\{n\}\(c,v\_\{0\},\\tau^\{2\},H\)\\right\\\}\_\{n=0\}^\{H\-1\}denote the resulting numerical approximation to the root schedule\. Arms with the same pull cost, prior variance, observation noise, and horizon share the same table\.

The numerical counterpart of the exact single\-arm index is obtained by a single lookup:

G^nc​\(s\):=s−r^n​\(c,v0,τ2,H\)\.\\widehat\{G\}\_\{n\}^\{c\}\(s\):=s\-\\widehat\{r\}\_\{n\}\(c,v\_\{0\},\\tau^\{2\},H\)\.\(9\)
The following proposition summarizes the computational guarantee of the FFT construction adapted from[Xie \(2026, Sections 5\.3\.2–5\.3\.3 and Appendix D\.2\)](https://arxiv.org/html/2609.25645#bib.bib18)\.

###### Proposition 3\.1\(FFT precomputation complexity\)\.

On a uniform grid ofPPpoints, FFT\-accelerated Bellman updates compute theHH\-stage numerical root schedule in𝒪⁡\(H​P​log⁡P\)\\mathcal\{O\}\(HP\\log P\)time and𝒪⁡\(P\)\\mathcal\{O\}\(P\)working memory, plus𝒪⁡\(H\)\\mathcal\{O\}\(H\)root storage\. Once stored, each index lookup takes𝒪⁡\(1\)\\mathcal\{O\}\(1\)time, and selecting amongKKarms takes𝒪⁡\(K\)\\mathcal\{O\}\(K\)time\.

The FFT computation replaces the𝒪⁡\(H​P2\)\\mathcal\{O\}\(HP^\{2\}\)cost of explicit summation over the discretized state space\. Thus the dynamic program is solved offline; online allocation requires only posterior updates, root lookups, and index comparisons\. Appendices[A\.3](https://arxiv.org/html/2609.25645#A1.SS3)and[A\.4](https://arxiv.org/html/2609.25645#A1.SS4)give the root characterization and FFT construction\.

### 3\.4Empirical\-Mean Allocation, Stopping, and Anytime Recommendation

For a fixed finite benchmark, the latent population meanθk\\theta\_\{k\}remains unobserved even when the response matrix is complete\. Our offline response\-matrix experiments therefore use each configuration’s full\-row empirical mean as an observable finite\-benchmark proxy and specialize the allocation, stopping, and recommendation rules to this target\. We retain the batch as the decision unit: under the Gaussian surrogate, the posterior mean of each empirical target again follows a Gaussian random walk at batch boundaries \(with the arm\-wise processes forming independent Markov chains\)\.

#### Full\-benchmark empirical target\.

Define the full\-benchmark empirical target of armkkas

Z¯k:=1N​∑j=1NZk,j\.\\bar\{Z\}\_\{k\}:=\\frac\{1\}\{N\}\\sum\_\{j=1\}^\{N\}Z\_\{k,j\}\.\(10\)It remains unknown until rowkkis exhaustively observed\. LetMk,tM\_\{k,t\}andVk,tV\_\{k,t\}denote the posterior mean and variance, respectively, ofZ¯k\\bar\{Z\}\_\{k\}given the batches observed by global timett\. Appendix[B](https://arxiv.org/html/2609.25645#A2)derives this posterior process\.

Under the Gaussian surrogate,\(Mk,t,nk​\(t\)\)\(M\_\{k,t\},n\_\{k\}\(t\)\)is a Markov state with a deterministic transition variance schedule; at completion,Mk,t=Z¯kM\_\{k,t\}=\\bar\{Z\}\_\{k\}\. Thus the same Markov\-chain selection result applies\.

For this finite\-benchmark specialization, the required\-completion objective is

supπ∈Πreq𝔼π​\[Z¯k^T−∑t=1TcAt,bt\]\.\\sup\_\{\\pi\\in\\Pi^\{\\mathrm\{req\}\}\}\\;\\mathbb\{E\}\_\{\\pi\}\\\!\\left\[\\bar\{Z\}\_\{\\hat\{k\}\_\{T\}\}\-\\sum\_\{t=1\}^\{T\}c\_\{A\_\{t\},b\_\{t\}\}\\right\]\.\(11\)
###### Proposition 3\.2\(Exact batch\-level Gittins optimality\)\.

Under the Gaussian surrogate, suppose the arms are independent, example scores are conditionally i\.i\.d\. within each arm, and the batch sizes, transition variances, and positive batch costs are predetermined functions of the arm’s local stage\. AssignGk,t:=Mk,t−rk,nk​\(t\)G\_\{k,t\}:=M\_\{k,t\}\-r\_\{k,n\_\{k\}\(t\)\}to an unfinished arm andGk,t:=Z¯kG\_\{k,t\}:=\\bar\{Z\}\_\{k\}to a completed arm\. If a completed arm attainsmaxk⁡Gk,t\\max\_\{k\}G\_\{k,t\}, stop and recommend a completed arm with largest terminal index; otherwise, evaluate an unfinished arm with largest index\. This exact empirical\-target Gittins policy attains the supremum in Eq\. \([11](https://arxiv.org/html/2609.25645#S3.E11)\) among required\-completion policies that act at batch boundaries\.

This is a Bayesian optimality statement under the Gaussian surrogate; it’s not a distribution\-free finite\-sample identification guarantee for the realized response matrix\. Appendices[A\.2](https://arxiv.org/html/2609.25645#A1.SS2)and[B](https://arxiv.org/html/2609.25645#A2)give the Markov\-chain reduction and empirical\-target transition calculation, respectively\.

Applying the same construction to the empirical\-target chains, our implementation precomputes gridded stopping rootsr^k,n\\widehat\{r\}\_\{k,n\}and, for an unfinished arm, uses

G^k,t:=Mk,t−r^k,nk​\(t\)\.\\widehat\{G\}\_\{k,t\}:=M\_\{k,t\}\-\\widehat\{r\}\_\{k,n\_\{k\}\(t\)\}\.\(12\)The index of a completed arm isZ¯k\\bar\{Z\}\_\{k\}\. The hat marks the numerical root approximation\. Thus Proposition[3\.2](https://arxiv.org/html/2609.25645#S3.Thmtheorem2)applies to the corresponding exact batch\-level roots, not to their gridded approximation, continuation past the stopping time, or the anytime recommendation below\.

The numericalGittinsEvalstopping time is the first post\-batch time at which a completed arm attains the largest value ofG^k,t\\widehat\{G\}\_\{k,t\}\. The recommendation at stopping is a completed arm with largest terminal index\. In fixed\-budget experiments, we record this stopping time but continue evaluation to the prescribed budget so that the anytime regret trajectories remain comparable across methods\.

#### Anytime recommendation\.

To accommodate arbitrary evaluation budgets where no candidate has completed its full benchmark horizon, we evaluate an anytime recommendation rule\. Although online sampling is guided by the numerical empirical\-target index in Eq\. \([12](https://arxiv.org/html/2609.25645#S3.E12)\), naive posterior\-mean maximization can induce erratic early switching due to sparsely observed configurations with optimistic estimates\. We therefore decouple online allocation from anytime reporting\. We recommend the candidate that maximizes an uncertainty\-penalized LCB\-style score:

k^t∈arg​maxk=1,…,K⁡\{Mk,t−Vk,t\}\.\\hat\{k\}\_\{t\}\\in\\operatorname\*\{arg\\,max\}\_\{k=1,\\ldots,K\}\\left\\\{M\_\{k,t\}\-\\sqrt\{V\_\{k,t\}\}\\right\\\}\.\(13\)The uncertainty penalty vanishes as an arm becomes fully observed\. Crucially, this penalty discounts poorly evaluated arms purely for reporting, without altering the numerical Gittins indices, the sampling trajectory, or the stopping time\. When fixed\-budget experiments continue past the stopping time, simple regret is measured against the anytime recommended arm’s true full\-row meanZ¯k^t\\bar\{Z\}\_\{\\hat\{k\}\_\{t\}\}rather than its penalized score\.

Full expressions for the posterior mean and variance of the full\-benchmark empirical target, the batch\-level transition schedule, and pseudocode appear in Appendix[B](https://arxiv.org/html/2609.25645#A2)and Algorithm[1](https://arxiv.org/html/2609.25645#alg1)\.

### 3\.5Design Choices for LLM Benchmarks

#### Prior specification\.

For accuracy\-style benchmarks, performance lies naturally on the\[0,1\]\[0,1\]scale\. Our general prior is𝒩⁡\(0\.5,0\.04\)\\mathcal\{N\}\(0\.5,0\.04\), whose mean expresses no preference between low and high accuracy and whose standard deviation is0\.20\.2\. To study the value of coarse task\-level prior calibration, our retrospective response\-matrix experiments also use an informative common prior selected from four pre\-specified difficulty buckets\. Each benchmark, or MMLU subject, is assigned to a bucket based on its aggregate empirical difficulty, and all arms in that problem instance share the corresponding prior\. The bucket therefore provides no arm\-specific information; in a prospective application, it could instead be selected using domain knowledge, evaluations of related tasks, or a separate pilot sample\. Table[6](https://arxiv.org/html/2609.25645#A4.T6)gives the prior values and experimental assignments\.

#### Observation noise\.

Under the working Bernoulli population model, a batch ofBBbinary correctness observations has conditional mean varianceθk​\(1−θk\)/B\\theta\_\{k\}\(1\-\\theta\_\{k\}\)/B\. Batching can also reduce wall\-clock latency when examples are evaluated in parallel or request overhead is amortized, at the cost of less frequent adaptation\([Zhou et al\., 2025](https://arxiv.org/html/2609.25645#bib.bib1)\)\. Sinceθk\\theta\_\{k\}is unknown, we use the conservative fixed approximationτ2:=1/\(4​B\)\\tau^\{2\}:=1/\(4B\), corresponding to the worst\-case Bernoulli variance\. This approximation may overestimate the noise for very easy or very hard tasks, but fixingτ2\\tau^\{2\}makes the posterior variance schedule deterministic and allows the Gittins root schedule to be precomputed\. More generally, any random variable supported on\[0,1\]\[0,1\]has variance at most1/41/4\. We therefore use the same conservative bound for the continuous pairwise preference scores in AlpacaEval: the per\-comparison working variance isτcell2:=1/4\\tau\_\{\\mathrm\{cell\}\}^\{2\}:=1/4, and, treating comparisons within a batch as conditionally independent in the working model, the batch\-mean variance isτ2:=τcell2/B=1/\(4​B\)\\tau^\{2\}:=\\tau\_\{\\mathrm\{cell\}\}^\{2\}/B=1/\(4B\)\. This is a fixed working approximation rather than an estimate of the empirical AlpacaEval score variance\.

#### Cost scaling\.

As in Section[2](https://arxiv.org/html/2609.25645#S2),c~k\\widetilde\{c\}\_\{k\}is a raw per\-example API\-price proxy and a full batch has effective costck:=ck,B=λ​B​c~kc\_\{k\}:=c\_\{k,B\}=\\lambda B\\widetilde\{c\}\_\{k\}\. We do not use example\-specific token counts or latency in this monetary\-cost proxy\. Smallerλ\\lambdamakes additional evaluation relatively cheap and therefore encourages more exploration, whereas largerλ\\lambdamakes evaluation more expensive and leads to earlier stopping\. We study several cost\-scaling factors in addition to the raw inference\-cost ratios\.

## 4Experiments

#### Benchmarks\.

We evaluate adaptive allocation policies using completed LLM response matrices built on four standard benchmarks: GSM8K for grade\-school mathematical reasoning\([Cobbe et al\., 2021](https://arxiv.org/html/2609.25645#bib.bib6)\), PIQA for physical commonsense reasoning\([Bisk et al\., 2020](https://arxiv.org/html/2609.25645#bib.bib7)\), AlpacaEval for instruction\-following quality\([Li et al\., 2023](https://arxiv.org/html/2609.25645#bib.bib16)\), and MMLU for multitask knowledge and reasoning\([Hendrycks et al\., 2020](https://arxiv.org/html/2609.25645#bib.bib9)\)\. The benchmark examples define the evaluation tasks, while the observed scores come from existing response\-matrix datasets\. GSM8K, PIQA, and AlpacaEval use response matrices released with BanditEval\([Zhou et al\., 2025](https://arxiv.org/html/2609.25645#bib.bib1)\)\. GSM8K contains122122model–sampling\-configuration arms and10001000examples, while PIQA contains103103arms and10001000examples\. The AlpacaEval matrix is derived from AlpacaEval 2\.0 leaderboard comparisons and contains152152leaderboard\-model arms and805805instructions; its entries are continuous scores in\[0,1\]\[0,1\]rather than binary correctness values\.

MMLU uses response matrices from DOVE\([Habba et al\., 2025](https://arxiv.org/html/2609.25645#bib.bib2)\)across5757subject datasets\. For each subject, we evaluate1515models with100100prompting templates; each arm is a model\-template pair, giving15001500arms per subject\. For MMLU, we group subjects into easy, medium, and hard categories according to their empirical mean arm quality\. Appendix[C](https://arxiv.org/html/2609.25645#A3)provides full dataset details and descriptive analyses\.

#### Baselines\.

We compare the twoGittinsEvalvariants with UCB\-E\([Audibert and Bubeck, 2010](https://arxiv.org/html/2609.25645#bib.bib8)\), BanditEval’s low\-rank\-factorization variant LRF\([Zhou et al\., 2025](https://arxiv.org/html/2609.25645#bib.bib1)\), SySRs\([Lyu et al\., 2026](https://arxiv.org/html/2609.25645#bib.bib17)\), PromptEval\-BAI\([Polo et al\., 2024](https://arxiv.org/html/2609.25645#bib.bib10)\), and the configuration\-level Bayesian optimization baselines PBGI, LogEI, and LogEIPC\. We use PromptEval’s one\-hot PE\-OneHot variant and label it PromptEval\-BAI in figures; PBGI and LogEIPC are cost\-aware\.GittinsEval\-Guses the general prior, whereasGittinsEval\-Suses a shared benchmark\-level prior selected from four pre\-specified difficulty buckets\. Table[6](https://arxiv.org/html/2609.25645#A4.T6)lists the prior values and assignments\. UCB\-E, LRF, SySRs, and PromptEval\-BAI do not natively account for heterogeneous evaluation costs or use Bayesian priors and Gittins\-index stopping values\. Initialization percentages refer to the sampling unit: a5%5\\%arm\-level initialization fully evaluates5%5\\%of the arms, whereas LRF uses BanditEval’s entry\-level warm\-up ofT0=0\.05​K​NT\_\{0\}=0\.05KNarm–example entries\.

#### Evaluation metric\.

The primary metric is simple regret versus evaluation resources\. After steptt, each policy recommends an armk^t\\hat\{k\}\_\{t\}\. TheGittinsEvalvariants use the LCB\-style rule in Eq\. \([13](https://arxiv.org/html/2609.25645#S3.E13)\), while the baselines retain their native recommendation rules\. Since the latent meansθk\\theta\_\{k\}are not observed even in the completed response matrices, we use the full\-benchmark empirical targets in Eq\. \([10](https://arxiv.org/html/2609.25645#S3.E10)\) as observable proxies and computeSRt:=maxk⁡Z¯k−Z¯k^t\\mathrm\{SR\}\_\{t\}:=\\max\_\{k\}\\bar\{Z\}\_\{k\}\-\\bar\{Z\}\_\{\\hat\{k\}\_\{t\}\}\. Thus, the uncertainty penalty affects theGittinsEvalrecommendation but not its reported regret\. We plot regret against cumulative evaluation costCt:=∑s=1tbs​c~AsC\_\{t\}:=\\sum\_\{s=1\}^\{t\}b\_\{s\}\\tilde\{c\}\_\{A\_\{s\}\}, wherebsb\_\{s\}is the batch size andc~k\\tilde\{c\}\_\{k\}is the raw per\-example cost; the unit\-cost setting is the special casec~k≡1\\tilde\{c\}\_\{k\}\\equiv 1\. A Bayesian optimization query evaluates one configuration on all benchmark examples and incurs its all\-example cost\.

#### Experimental conditions\.

For each benchmark, we consider both unit\-cost and cost\-aware settings\. Each evaluation has unit cost in the former and incurs a model\-specific cost derived from API\-price proxies in the latter, requiring the policy to account for heterogeneous costs when allocating evaluations\. Configurations that use the same base model share the same model\-level price, computed from published input/output rates using fixed benchmark\-level ratios described in Appendix[D](https://arxiv.org/html/2609.25645#A4); we do not model example\-specific token usage\.

Here, exhaustive evaluation means evaluating every configuration on every benchmark item\. All methods receive a nominal budget equal to 10% of exhaustive evaluation, measured in response\-matrix entries under unit costs and total entry cost under heterogeneous costs\. UCB\-E and LRF run to this limit following the BanditEval protocol of[Zhou et al\. \(2025\)](https://arxiv.org/html/2609.25645#bib.bib1); for theGittinsEvalvariants, we record the stopping time from Section[3\.4](https://arxiv.org/html/2609.25645#S3.SS4)while continuing each trajectory to the same limit\. The Bayesian optimization baselines evaluate complete configurations, use random initialization capped at 5% of the configurations, and then select configurations by acquisition until the remaining budget is exhausted, without overshooting the limit in the cost\-aware setting\.

For the main GSM8K, PIQA, and AlpacaEval plots, UCB\-E andGittinsEvaluse batch sizeB=8B=8\. For the main MMLU aggregate plots, the small size bucket \(at most150150examples\) usesB=2B=2and the large size bucket \(more than400400examples\) usesB=8B=8for UCB\-E andGittinsEval\. Because LRF’s repeated low\-rank updates make smaller batches prohibitively slow, LRF usesB=32B=32throughout\. The medium\-size bucket, full subject\-level MMLU results, and batch\-size ablations are included in the appendix\.

#### Reporting\.

Figures[2](https://arxiv.org/html/2609.25645#S4.F2)and[3](https://arxiv.org/html/2609.25645#S4.F3)report the main simple\-regret curves\. PromptEval\-BAI is included for GSM8K, PIQA, and MMLU, but not AlpacaEval because its released best\-arm\-identification implementation assumes binary outcomes rather than continuous pairwise preference scores\. Shaded bands denote one standard error\. Dashed vertical lines mark average stopping times forGittinsEvaland Bayesian optimization; eachGittinsEvaltrajectory continues to the fixed budget after its stopping time\. Thexx\-axis reports cumulative evaluation cost as a percentage of exhaustive evaluation, and theyy\-axis reports raw simple regret\. Appendix[B](https://arxiv.org/html/2609.25645#A2)describes the LCB\-style recommendation rule, while Appendix[E](https://arxiv.org/html/2609.25645#A5)provides additional MMLU results, ablations, and prior\-bucket diagnostics\.

![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/2x3/figure_gsm8k_piqa_alpaca_steps.png)Figure 2:Simple regret on GSM8K, PIQA, and AlpacaEval under unit\-cost \(top\) and cost\-aware \(bottom\) evaluation\. The horizontal axis reports cumulative evaluation cost as a percentage of exhaustive evaluation\. Curves average 100 runs for GSM8K and PIQA and 20 runs for AlpacaEval; shaded regions denote±1\\pm 1standard error\. Bayesian optimization curves begin after the5%5\\%initialization phase, and dashed vertical lines mark mean stopping times\.GittinsEval\-Sreaches near\-zero regret earliest in most settings\.![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/2x3/mmlu_combined_unit_cost_cost_aware.png)Figure 3:Aggregate raw MMLU simple regret by subject size and difficulty under unit\-cost \(top\) and cost\-aware \(bottom\) evaluation\. Columns show the easy–small, easy–large, hard–small, and hard–large buckets\. Curves average raw simple regret over 20 runs per subject and are then aggregated within each bucket; shaded regions denote±1\\pm 1standard error\. Bayesian optimization curves begin after the5%5\\%initialization phase, and dashed vertical lines mark mean stopping times\.GittinsEval\-Sachieves the strongest overall performance across the reported buckets\.
#### Implementation details\.

ForGittinsEval, we precompute empirical\-target root schedules for the prior variance, batch\-level noise and cost schedules, and horizon used in each condition\. Online allocation then requires only posterior updates, empirical\-target moment computation, and root\-table lookup, keeping runtime close to UCB\-E and well below LRF; Appendix[E](https://arxiv.org/html/2609.25645#A5)reports timing comparisons\. After random initialization, the Bayesian optimization baselines fit mixed Gaussian\-process models and optimize their acquisition functions in BoTorch\([Balandat et al\., 2020](https://arxiv.org/html/2609.25645#bib.bib22)\)\. Their categorical kernels represent BanditEval configurations with four coordinates and DOVE configurations with two\. GSM8K and PIQA results average five response matrices and 20 randomized trials per matrix; AlpacaEval uses 20 trials on its single response matrix\. MMLU results aggregate 20 trials per subject within each reported bucket\.

#### Main findings\.

GittinsEvalrapidly reduces simple regret in the low\-budget regime under both cost settings\. On GSM8K, PIQA, and AlpacaEval, configuration\-level Bayesian optimization spends a substantial part of its 10% budget on full\-benchmark evaluations during initialization, leaving few acquisition\-driven updates\. By allocating partial batches across configurations,GittinsEvalreaches low regret substantially earlier and also markedly outperforms LRF\.

On MMLU, with 1,500 model–template arms per subject,GittinsEval\-Sconsistently reaches low regret earlier than the cost\-unaware bandit baselines\. LRF has substantially higher simple regret than UCB\-E across the MMLU aggregates, consistent with[Lyu et al\. \(2026\)](https://arxiv.org/html/2609.25645#bib.bib17)\. Bayesian optimization remains competitive on smaller tasks, where full\-configuration evaluations are cheaper, but theGittinsEvalvariants are stronger across most size–difficulty buckets\.

Across benchmarks, theGittinsEvalstopping time typically occurs after the regret curves flatten, at1​–​10%1\\text\{\-\-\}10\\%of exhaustive\-evaluation cost and earlier than the Bayesian optimization stopping times or fixed\-budget endpoints\. ComparingGittinsEval\-GandGittinsEval\-Salso shows that prior calibration matters most on challenging MMLU subjects, while the general prior remains competitive on simpler tasks\.

## 5Conclusion

We introducedGittinsEval, which formulates LLM configuration selection as a cost\-aware Bayesian bandit problem and adaptively allocates benchmark queries via Gittins indices\. By precomputing index schedules offline, the policy reduces online decision\-making to lightweight posterior updates and table lookups while naturally accommodating heterogeneous evaluation costs\. Empirically, GittinsEval is consistently competitive across benchmarks, with particularly strong gains over configuration\-level Bayesian optimization on large\-example benchmarks and over cost\-unaware bandit baselines across large candidate spaces\. Its anytime recommendation often attains near\-zero simple regret using only1%​–​2%1\\%\\text\{\-\-\}2\\%of the exhaustive\-evaluation cost;GittinsEvalalso offers an adaptive stopping rule that typically triggers at1%​–​10%1\\%\\text\{\-\-\}10\\%\.

## AI Use Statement

The authors used generative\-AI tools, including LLM\-based assistants, to retrieve and discover potentially relevant literature, support research ideation and execution, draft and revise portions of the manuscript, and improve the clarity of the writing\. The tools also assisted in proving mathematical claims by working out detailed derivations and proof steps from sketches and arguments provided by the authors\. The authors checked the cited sources, mathematical derivations, and AI\-assisted text, revised them as needed, and take full responsibility for the paper’s contents\.

Separately, LLMs are the objects of evaluation in this work\. The experiments use precomputed response matrices released by BanditEval for GSM8K, PIQA, and AlpacaEval, and by DOVE for MMLU\. We did not query model APIs to generate new evaluation responses for this study; the provenance and processing of the experimental data are described in Appendix[C](https://arxiv.org/html/2609.25645#A3)\.

## Reproducibility Statement

The main text specifies the probabilistic model, allocation rule, numerical index computation, stopping rule, evaluation metrics, and experimental conditions\. Appendix[A](https://arxiv.org/html/2609.25645#A1)states the theoretical assumptions and provides the derivations and proofs; Appendix[B](https://arxiv.org/html/2609.25645#A2)derives the finite\-benchmark recommendation and index construction and gives pseudocode\. Appendix[C](https://arxiv.org/html/2609.25645#A3)documents the data sources, processing, and dataset statistics, while Appendix[D](https://arxiv.org/html/2609.25645#A4)reports the computing environment, repetitions, priors, batch sizes, cost construction, baseline setup, and aggregation procedures\. Additional results and sensitivity analyses appear in Appendix[E](https://arxiv.org/html/2609.25645#A5)\. All experiments operate on the precomputed response data rather than requiring new LLM API calls\.

## Acknowledgments

QX thanks Theodore Brown, Ziv Scully, and Alexander Terenin for a prior collaboration from which the translational\-invariance reduction and FFT\-based approach to efficient Gittins\-index computation originated\. QX also thanks Kyuseong Choi for introducing QX to the area of efficient LLM evaluation and sharing related work, Tianyi Peng for inviting QX to a related project and discussions connecting LLM evaluation with multi\-armed bandits, and Jin Peng Zhou and Ruihan Wu for sharing the BanditEval data and answering questions about the datasets\.

## References

- Aoet al\.\(2026\)R\. Ao, H\. Chen, S\. Gao, H\. Li, and D\. Simchi\-LeviBest arm identification with llm judges and limited human audits\.arXiv preprint arXiv:2601\.21471\.Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px1.p1.1)\.
- Audibert and Bubeck \(2010\)J\. Audibert and S\. BubeckBest arm identification in multi\-armed bandits\.InCOLT\-23th Conference on learning theory\-2010,pp\. 13–p\.Cited by:[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px2.p1.1)\.
- Balandatet al\.\(2020\)M\. Balandat, B\. Karrer, D\. Jiang, S\. Daulton, B\. Letham, A\. G\. Wilson, and E\. BakshyBoTorch: a framework for efficient Monte\-Carlo Bayesian optimization\.Advances in Neural Information Processing Systems33,pp\. 21524–21538\.Cited by:[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px6.p1.1)\.
- Bisket al\.\(2020\)Y\. Bisk, R\. Zellers, J\. Gao, Y\. Choi,et al\.Piqa: reasoning about physical commonsense in natural language\.InProceedings of the AAAI conference on artificial intelligence,Vol\.34,pp\. 7432–7439\.Cited by:[§C\.1](https://arxiv.org/html/2609.25645#A3.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2609.25645#S1.p1.1),[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px1.p1.1)\.
- Cobbeet al\.\(2021\)K\. Cobbe, V\. Kosaraju, M\. Bavarian, M\. Chen, H\. Jun, L\. Kaiser, M\. Plappert, J\. Tworek, J\. Hilton, R\. Nakano,et al\.Training verifiers to solve math word problems\.arXiv preprint arXiv:2110\.14168\.Cited by:[§C\.1](https://arxiv.org/html/2609.25645#A3.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2609.25645#S1.p1.1),[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px1.p1.1)\.
- Dumitriuet al\.\(2003\)I\. Dumitriu, P\. Tetali, and P\. WinklerOn playing golf with two balls\.SIAM Journal on Discrete Mathematics16\(4\),pp\. 604–615\.Cited by:[§A\.2](https://arxiv.org/html/2609.25645#A1.SS2.p4.1.1),[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2609.25645#S1.p3.1),[§3\.2](https://arxiv.org/html/2609.25645#S3.SS2.p6.1)\.
- Gittins \(1979\)J\. C\. GittinsBandit processes and dynamic allocation indices\.Journal of the Royal Statistical Society: Series B \(Methodological\)41\(2\),pp\. 148–177\.External Links:[Document](https://dx.doi.org/10.1111/j.2517-6161.1979.tb01068.x)Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px3.p1.1)\.
- Gittinset al\.\(2011\)J\. Gittins, K\. Glazebrook, and R\. WeberMulti\-armed bandit allocation indices\.John Wiley & Sons\.Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2609.25645#S1.p3.1)\.
- Habbaet al\.\(2025\)E\. Habba, O\. Arviv, I\. Itzhak, Y\. Perlitz, E\. Bandel, L\. Choshen, M\. Shmueli\-Scheuer, and G\. StanovskyDOVE: a large\-scale multi\-dimensional predictions dataset towards meaningful LLM evaluation\.InFindings of the Association for Computational Linguistics: ACL 2025,pp\. 11744–11763\.External Links:[Document](https://dx.doi.org/10.18653/v1/2025.findings-acl.611),[Link](https://aclanthology.org/2025.findings-acl.611/)Cited by:[§C\.1](https://arxiv.org/html/2609.25645#A3.SS1.SSS0.Px3.p1.1),[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px1.p2.1)\.
- Harrasseet al\.\(2026\)A\. Harrasse, C\. Bandi, and H\. BandiDebate, deliberate, decide \(D3\): a cost\-aware adversarial framework for reliable and interpretable LLM evaluation\.InProceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics \(Volume 1: Long Papers\),Rabat, Morocco,pp\. 8376–8392\.External Links:[Document](https://dx.doi.org/10.18653/v1/2026.eacl-long.392)Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px1.p1.1)\.
- Hendryckset al\.\(2020\)D\. Hendrycks, C\. Burns, S\. Basart, A\. Zou, M\. Mazeika, D\. Song, and J\. SteinhardtMeasuring massive multitask language understanding\.arXiv preprint arXiv:2009\.03300\.Cited by:[§1](https://arxiv.org/html/2609.25645#S1.p1.1),[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px1.p1.1)\.
- Kandasamyet al\.\(2017\)K\. Kandasamy, G\. Dasarathy, J\. Schneider, and B\. PóczosMulti\-fidelity bayesian optimisation with continuous approximations\.InInternational conference on machine learning,pp\. 1799–1808\.Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px2.p1.1)\.
- Kleinet al\.\(2017\)A\. Klein, S\. Falkner, S\. Bartels, P\. Hennig, and F\. HutterFast bayesian optimization of machine learning hyperparameters on large datasets\.InArtificial intelligence and statistics,pp\. 528–536\.Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px2.p1.1)\.
- Liet al\.\(2023\)X\. Li, T\. Zhang, Y\. Dubois, R\. Taori, I\. Gulrajani, C\. Guestrin, P\. Liang, and T\. B\. HashimotoAlpacaeval: an automatic evaluator of instruction\-following models\.Cited by:[§C\.1](https://arxiv.org/html/2609.25645#A3.SS1.SSS0.Px2.p1.1),[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px1.p1.1)\.
- Lyuet al\.\(2026\)Z\. Lyu, C\. Nejma, T\. Wegel, F\. Yang, and F\. E\. DornerCutting llm evaluation costs with sysrs: a bandit algorithm that provably exploits model similarity\.arXiv preprint arXiv:2606\.07726\.Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2609.25645#S1.p2.1),[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px2.p1.1),[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px7.p2.1)\.
- Poloet al\.\(2024\)F\. M\. Polo, R\. Xu, L\. Weber, M\. Silva, O\. Bhardwaj, L\. Choshen, A\. F\. de Oliveira, Y\. Sun, and M\. YurochkinEfficient multi\-prompt evaluation of llms\.Advances in Neural Information Processing Systems37,pp\. 22483–22512\.Cited by:[Appendix D](https://arxiv.org/html/2609.25645#A4.SS0.SSS0.Px7.p1.1),[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2609.25645#S1.p2.1),[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px2.p1.1)\.
- Scully and Terenin \(2025\)Z\. Scully and A\. TereninThe gittins index: a design principle for decision making under uncertainty\.InTutorials in Operations Research: Advances in Analytics and Operations Research: Improving Decisions to Secure the Future,pp\. 28–70\.Cited by:[§A\.2](https://arxiv.org/html/2609.25645#A1.SS2.p4.1.1),[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2609.25645#S1.p3.1),[§3\.2](https://arxiv.org/html/2609.25645#S3.SS2.p6.1)\.
- Shiet al\.\(2024\)C\. Shi, K\. Yang, Z\. Chen, J\. Li, J\. Yang, and C\. ShenEfficient prompt optimization through the lens of best arm identification\.Advances in Neural Information Processing Systems37,pp\. 99646–99685\.Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2609.25645#S1.p2.1)\.
- Snoeket al\.\(2012\)J\. Snoek, H\. Larochelle, and R\. P\. AdamsPractical bayesian optimization of machine learning algorithms\.Advances in Neural Information Processing Systems\.Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2609.25645#S1.p2.1)\.
- Tolochinskyet al\.\(2026\)E\. Tolochinsky, Y\. Tenzer, and Y\. RomanoValid best\-model identification for llm evaluation via low\-rank factorization\.arXiv preprint arXiv:2605\.10405\.Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px1.p1.1)\.
- Wuet al\.\(2020\)J\. Wu, S\. Toscano\-Palmerin, P\. I\. Frazier, and A\. G\. WilsonPractical multi\-fidelity bayesian optimization for hyperparameter tuning\.InUncertainty in Artificial Intelligence,pp\. 788–798\.Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px2.p1.1)\.
- Xieet al\.\(2024\)Q\. Xie, R\. Astudillo, P\. I\. Frazier, Z\. Scully, and A\. TereninCost\-aware bayesian optimization via the pandora’s box gittins index\.Advances in Neural Information Processing Systems37,pp\. 115523–115562\.Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px3.p1.1)\.
- Xieet al\.\(2025\)Q\. Xie, L\. Cai, A\. Terenin, P\. I\. Frazier, and Z\. ScullyCost\-aware stopping for bayesian optimization\.arXiv preprint arXiv:2507\.12453\.Cited by:[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px3.p1.1)\.
- Xie \(2026\)Q\. XieThe Gittins Index design principle for cost\-aware Bayesian decision\-making under uncertainty\.Ph\.D\. dissertation,Cornell University\.Note:ProQuest Dissertations & Theses, ProQuest document ID 3385501903External Links:[Link](https://www.proquest.com/docview/3385501903)Cited by:[§A\.3](https://arxiv.org/html/2609.25645#A1.SS3.p1.1),[§A\.4](https://arxiv.org/html/2609.25645#A1.SS4.p1.1),[§3\.3](https://arxiv.org/html/2609.25645#S3.SS3.p5.1)\.
- Zhouet al\.\(2025\)J\. P\. Zhou, C\. K\. Belardi, R\. Wu, T\. Zhang, C\. P\. Gomes, W\. Sun, and K\. Q\. WeinbergerOn speeding up language model evaluation\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=3cvwO5DBZn)Cited by:[§C\.1](https://arxiv.org/html/2609.25645#A3.SS1.SSS0.Px1.p1.1),[§C\.1](https://arxiv.org/html/2609.25645#A3.SS1.SSS0.Px2.p1.1),[Appendix D](https://arxiv.org/html/2609.25645#A4.SS0.SSS0.Px5.p1.1),[§1\.1](https://arxiv.org/html/2609.25645#S1.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2609.25645#S1.p2.1),[§3\.5](https://arxiv.org/html/2609.25645#S3.SS5.SSS0.Px2.p1.1),[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px1.p1.1),[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px2.p1.1),[§4](https://arxiv.org/html/2609.25645#S4.SS0.SSS0.Px4.p2.1)\.

## Appendix ATheoretical Details

### A\.1Gaussian Random\-Walk Details

We derive the posterior update and the induced random\-walk transition used in Section[3](https://arxiv.org/html/2609.25645#S3)\. Fix an arm and suppress the arm index\. LetY¯n\+1\\overline\{Y\}\_\{n\+1\}denote the batch mean observed on the next pull\. Suppose that afternnlocal pulls the current posterior distribution of the arm mean is

θ\|𝒟n∼𝒩⁡\(μn,vn\),\\theta\\mid\\mathcal\{D\}\_\{n\}\\sim\\mathcal\{N\}\(\\mu\_\{n\},v\_\{n\}\),and that the next observation follows the fixed\-noise Gaussian likelihood

Y¯n\+1\|θ∼𝒩⁡\(θ,τ2\)\.\\overline\{Y\}\_\{n\+1\}\\mid\\theta\\sim\\mathcal\{N\}\(\\theta,\\tau^\{2\}\)\.
By Bayes’ rule, the posterior density after observingY¯n\+1\\overline\{Y\}\_\{n\+1\}is proportional to the likelihood times the current posterior:

p⁡\(θ∣𝒟n\+1\)∝p⁡\(Y¯n\+1∣θ\)​p​\(θ∣𝒟n\)\.p\(\\theta\\mid\\mathcal\{D\}\_\{n\+1\}\)\\propto p\(\\overline\{Y\}\_\{n\+1\}\\mid\\theta\)\\,p\(\\theta\\mid\\mathcal\{D\}\_\{n\}\)\.Substituting the Gaussian likelihood and the current Gaussian posterior gives

p⁡\(θ∣𝒟n\+1\)∝exp⁡\(−12​\[\(θ−μn\)2vn\+\(Y¯n\+1−θ\)2τ2\]\)\.p\(\\theta\\mid\\mathcal\{D\}\_\{n\+1\}\)\\propto\\exp\\left\(\-\\frac\{1\}\{2\}\\left\[\\frac\{\(\\theta\-\\mu\_\{n\}\)^\{2\}\}\{v\_\{n\}\}\+\\frac\{\(\\overline\{Y\}\_\{n\+1\}\-\\theta\)^\{2\}\}\{\\tau^\{2\}\}\\right\]\\right\)\.Expanding the terms that depend onθ\\theta,

\(θ−μn\)2vn\+\(Y¯n\+1−θ\)2τ2=\(vn−1\+τ−2\)​θ2−2​\(μnvn\+Y¯n\+1τ2\)​θ\+const\.\\frac\{\(\\theta\-\\mu\_\{n\}\)^\{2\}\}\{v\_\{n\}\}\+\\frac\{\(\\overline\{Y\}\_\{n\+1\}\-\\theta\)^\{2\}\}\{\\tau^\{2\}\}=\\left\(v\_\{n\}^\{\-1\}\+\\tau^\{\-2\}\\right\)\\theta^\{2\}\-2\\left\(\\frac\{\\mu\_\{n\}\}\{v\_\{n\}\}\+\\frac\{\\overline\{Y\}\_\{n\+1\}\}\{\\tau^\{2\}\}\\right\)\\theta\+\\text\{const\.\}Thus the exponent is quadratic inθ\\theta, so the posterior is Gaussian\. Matching the quadratic and linear coefficients with the Gaussian form

exp⁡\(−\(θ−μn\+1\)22​vn\+1\)\\exp\\left\(\-\\frac\{\(\\theta\-\\mu\_\{n\+1\}\)^\{2\}\}\{2v\_\{n\+1\}\}\\right\)gives

vn\+1−1=vn−1\+τ−2,μn\+1vn\+1=μnvn\+Y¯n\+1τ2\.v\_\{n\+1\}^\{\-1\}=v\_\{n\}^\{\-1\}\+\\tau^\{\-2\},\\qquad\\frac\{\\mu\_\{n\+1\}\}\{v\_\{n\+1\}\}=\\frac\{\\mu\_\{n\}\}\{v\_\{n\}\}\+\\frac\{\\overline\{Y\}\_\{n\+1\}\}\{\\tau^\{2\}\}\.Therefore,

vn\+1=\(vn−1\+τ−2\)−1,μn\+1=vn\+1​\(μnvn\+Y¯n\+1τ2\)\.v\_\{n\+1\}=\\left\(v\_\{n\}^\{\-1\}\+\\tau^\{\-2\}\\right\)^\{\-1\},\\qquad\\mu\_\{n\+1\}=v\_\{n\+1\}\\left\(\\frac\{\\mu\_\{n\}\}\{v\_\{n\}\}\+\\frac\{\\overline\{Y\}\_\{n\+1\}\}\{\\tau^\{2\}\}\\right\)\.Equivalently, the posterior mean update can be written in the incremental form

μn\+1=μn\+vnvn\+τ2​\(Y¯n\+1−μn\)\.\\mu\_\{n\+1\}=\\mu\_\{n\}\+\\frac\{v\_\{n\}\}\{v\_\{n\}\+\\tau^\{2\}\}\\left\(\\overline\{Y\}\_\{n\+1\}\-\\mu\_\{n\}\\right\)\.This form shows that the new posterior mean moves from the old posterior mean toward the new observation, with gain

vnvn\+τ2\.\\frac\{v\_\{n\}\}\{v\_\{n\}\+\\tau^\{2\}\}\.
To describe the posterior mean as a state process, we first compute the predictive distribution of the next observation\. Conditioned on the current data𝒟n\\mathcal\{D\}\_\{n\}, we may write

Y¯n\+1=θ\+εn\+1,θ∣𝒟n∼𝒩\(μn,vn\),εn\+1∼𝒩\(0,τ2\),\\overline\{Y\}\_\{n\+1\}=\\theta\+\\varepsilon\_\{n\+1\},\\qquad\\theta\\mid\\mathcal\{D\}\_\{n\}\\sim\\mathcal\{N\}\(\\mu\_\{n\},v\_\{n\}\),\\qquad\\varepsilon\_\{n\+1\}\\sim\\mathcal\{N\}\(0,\\tau^\{2\}\),withθ\\thetaandεn\+1\\varepsilon\_\{n\+1\}conditionally independent given𝒟n\\mathcal\{D\}\_\{n\}\. Hence

Y¯n\+1\|𝒟n∼𝒩⁡\(μn,vn\+τ2\)\.\\overline\{Y\}\_\{n\+1\}\\mid\\mathcal\{D\}\_\{n\}\\sim\\mathcal\{N\}\(\\mu\_\{n\},v\_\{n\}\+\\tau^\{2\}\)\.
We now view the posterior mean as the Markov state used below\. LetSnS\_\{n\}denote the posterior mean afternnlocal pulls, viewed as a random variable over future observations\. If the current realized state isSn=sS\_\{n\}=s, then the posterior update gives

Sn\+1=s\+vnvn\+τ2​\(Y¯n\+1−s\)\.S\_\{n\+1\}=s\+\\frac\{v\_\{n\}\}\{v\_\{n\}\+\\tau^\{2\}\}\\left\(\\overline\{Y\}\_\{n\+1\}\-s\\right\)\.Since

Y¯n\+1−s\|Sn=s∼𝒩⁡\(0,vn\+τ2\),\\overline\{Y\}\_\{n\+1\}\-s\\mid S\_\{n\}=s\\sim\\mathcal\{N\}\(0,v\_\{n\}\+\\tau^\{2\}\),we have

Sn\+1\|Sn=s∼𝒩⁡\(s,\(vnvn\+τ2\)2​\(vn\+τ2\)\)\.S\_\{n\+1\}\\mid S\_\{n\}=s\\sim\\mathcal\{N\}\\\!\\left\(s,\\left\(\\frac\{v\_\{n\}\}\{v\_\{n\}\+\\tau^\{2\}\}\\right\)^\{2\}\(v\_\{n\}\+\\tau^\{2\}\)\\right\)\.Therefore,

Sn\+1\|Sn=s∼𝒩⁡\(s,vn2vn\+τ2\)\.S\_\{n\+1\}\\mid S\_\{n\}=s\\sim\\mathcal\{N\}\\\!\\left\(s,\\frac\{v\_\{n\}^\{2\}\}\{v\_\{n\}\+\\tau^\{2\}\}\\right\)\.
Finally, under the fixed\-noise likelihood, the variance update

vn\+1=\(vn−1\+τ−2\)−1v\_\{n\+1\}=\\left\(v\_\{n\}^\{\-1\}\+\\tau^\{\-2\}\\right\)^\{\-1\}does not depend on the realized observationY¯n\+1\\overline\{Y\}\_\{n\+1\}\. Therefore the posterior variance follows a deterministic schedule indexed only by the local pull countnn, while the posterior mean follows the Gaussian random\-walk transition above whenever the arm is selected\. Across arms, this schedule is identical only for arms with the same initial variance and fixed noise level; otherwise each arm has its own deterministic schedule\.

### A\.2Proof of Bayesian Optimality

###### Proposition A\.1\(Latent\-mean optimality under required completion\)\.

Consider the Gaussian Bayesian bandit model in Section[3\.1](https://arxiv.org/html/2609.25645#S3.SS1)with independent arms, common prior𝒩⁡\(μ0,v0\)\\mathcal\{N\}\(\\mu\_\{0\},v\_\{0\}\), fixed observation noiseτ2\\tau^\{2\}, finite per\-arm horizonHH, and nonnegative effective costs of arm pullsckc\_\{k\}for armsk=1,…,Kk=1,\\ldots,K\. LetΠHreq\\Pi\_\{H\}^\{\\mathrm\{req\}\}be the class of policies that evaluate only unfinished arms and may terminate only by recommending an arm that has reached its finite horizon\. For the required\-completion objective

supπ∈ΠHreq𝔼π​\[θk^T−∑t=1TcAt\],\\sup\_\{\\pi\\in\\Pi\_\{H\}^\{\\mathrm\{req\}\}\}\\;\\mathbb\{E\}\_\{\\pi\}\\\!\\left\[\\theta\_\{\\hat\{k\}\_\{T\}\}\-\\sum\_\{t=1\}^\{T\}c\_\{A\_\{t\}\}\\right\],an optimal policy is to assign terminal indexGk,t=μk,HG\_\{k,t\}=\\mu\_\{k,H\}to completed arms, assignGk,t=Gnk​\(t\)ck​\(μk,nk​\(t\)\)G\_\{k,t\}=G\_\{n\_\{k\}\(t\)\}^\{c\_\{k\}\}\(\\mu\_\{k,n\_\{k\}\(t\)\}\)to unfinished arms, and stop when an arm attainingmaxk⁡Gk,t\\max\_\{k\}G\_\{k,t\}is completed\. Otherwise, the policy evaluates an unfinished arm with largest Gittins indexGk,tG\_\{k,t\}\. At stopping, an optimal recommendation is any completed arm with largest posterior mean among completed arms, equivalently any completed arm with largest terminal index\.

Proposition[3\.2](https://arxiv.org/html/2609.25645#S3.Thmtheorem2)applies the same Markov\-chain selection result to the full\-benchmark empirical target at batch boundaries\. Numerical root approximation, continuation beyond the stopping time, and the LCB\-style anytime recommendation are not part of either optimality claim\.

###### Proof\.

We prove the proposition by reducing the required\-completion problem to a Markov chain selection problem\. For each armkk, define one local chain:

State\.The local state isxk=\(sk,nk\)x\_\{k\}=\(s\_\{k\},n\_\{k\}\), wheresks\_\{k\}is the posterior mean andnk∈\{0,…,H\}n\_\{k\}\\in\\\{0,\\ldots,H\\\}is the number of observed batches\. The terminal states are those withnk=Hn\_\{k\}=H\.

Action\.At each decision time, choose one armkk\. Only the chosen arm moves; every other arm keeps its current state\.

Reward\.If the chosen arm is unfinished, the immediate reward is−ck\-c\_\{k\}\. If the chosen arm is terminal, the process stops and the terminal reward issks\_\{k\}\.

Transition\.If the chosen arm is in state\(sk,nk\)\(s\_\{k\},n\_\{k\}\)withnk<Hn\_\{k\}<H, then its next state is\(S′,nk\+1\)\(S^\{\\prime\},n\_\{k\}\+1\), where

S′\|sk,nk∼𝒩⁡\(sk,vnk2vnk\+τ2\)\.S^\{\\prime\}\\mid s\_\{k\},n\_\{k\}\\sim\\mathcal\{N\}\\\!\\left\(s\_\{k\},\\frac\{v\_\{n\_\{k\}\}^\{2\}\}\{v\_\{n\_\{k\}\}\+\\tau^\{2\}\}\\right\)\.
The global state is the collection of local states, initialized at\(\(μ0,0\),…,\(μ0,0\)\)\(\(\\mu\_\{0\},0\),\\ldots,\(\\mu\_\{0\},0\)\)\.

By Eq\. \([3](https://arxiv.org/html/2609.25645#S3.E3)\), the state of armkkcan be represented by\(μk,nk,nk\)\(\\mu\_\{k,n\_\{k\}\},n\_\{k\}\)\. Under fixedτ2\\tau^\{2\}, Appendix[A\.1](https://arxiv.org/html/2609.25645#A1.SS1)shows that the posterior mean follows the Gaussian random\-walk transition, so this state is Markov\. Conditional on this state, the next state distribution of armkkis independent of the states and histories of all other arms, and pulling armkkincurs only its own effective costckc\_\{k\}\. Sincesk=𝔼⁡\[θk∣xk\]s\_\{k\}=\\mathbb\{E\}\[\\theta\_\{k\}\\mid x\_\{k\}\], the terminal reward is the posterior expected reward from recommending completed armkk\. Thus maximizing expected total reward in the constructed selection problem is exactly the required\-completion objective\.

The Gittins\-index optimality theorem for Markov chain selection implies that an optimal policy selects a chain with largest index until a terminal chain has largest index\([Dumitriu et al\., 2003](https://arxiv.org/html/2609.25645#bib.bib13);[Scully and Terenin, 2025](https://arxiv.org/html/2609.25645#bib.bib3)\)\. Applying this result to the single\-arm value function used to defineGnc​\(s\)G\_\{n\}^\{c\}\(s\)gives the stated rule\. Terminal chains have index equal to their posterior mean, so when a completed arm attains the largest index, recommending any completed arm with largest posterior mean among completed arms gives an optimal terminal reward\. ∎

The same reduction allows predetermined stage\-specific batch sizes\. The local stagennthen determines both the next batch\-mean variance and its cost, so includingnnin the state preserves the Markov property and arm independence\.

### A\.3One\-Dimensional Gittins Index Computation

We now spell out the reduction used by the precomputation step in Algorithm[1](https://arxiv.org/html/2609.25645#alg1); the corresponding translational\-equivariance argument also appears in\([Xie, 2026](https://arxiv.org/html/2609.25645#bib.bib18), Section 5\.3\.2\)\. Fix a single arm, suppress the arm index, and letα\\alphabe the outside terminal reward available from the other arms\. With the costccfixed and suppressed in the value\-function notation, the terminal value is

VH​\(s,α\)=max⁡\{s,α\},V\_\{H\}\(s;\\alpha\)=\\max\\\{s,\\alpha\\\},and, forn<Hn<H,

Qncont​\(s,α\)\\displaystyle Q\_\{n\}^\{\\mathrm\{cont\}\}\(s;\\alpha\)=−c\+𝔼⁡\[Vn\+1​\(Sn\+1,α\)∣Sn=s\],\\displaystyle=\-c\+\\mathbb\{E\}\\\!\\left\[V\_\{n\+1\}\(S\_\{n\+1\};\\alpha\)\\mid S\_\{n\}=s\\right\],Qnstop​\(s,α\)\\displaystyle\\qquad Q\_\{n\}^\{\\mathrm\{stop\}\}\(s;\\alpha\)=α,\\displaystyle=\\alpha,Vn​\(s,α\)\\displaystyle V\_\{n\}\(s;\\alpha\)=max⁡\{Qncont​\(s,α\),Qnstop​\(s,α\)\}\.\\displaystyle=\\max\\\{Q\_\{n\}^\{\\mathrm\{cont\}\}\(s;\\alpha\),Q\_\{n\}^\{\\mathrm\{stop\}\}\(s;\\alpha\)\\\}\.The transition kernel depends only on differences in posterior means:

Sn\+1∣Sn=s∼𝒩\(s,σn2\),σn2=vn2vn\+τ2\.S\_\{n\+1\}\\mid S\_\{n\}=s\\sim\\mathcal\{N\}\(s,\\sigma\_\{n\}^\{2\}\),\\qquad\\sigma\_\{n\}^\{2\}=\\frac\{v\_\{n\}^\{2\}\}\{v\_\{n\}\+\\tau^\{2\}\}\.
###### Lemma A\.2\(Translational invariance of the continuation value\)\.

Fix the costccand Gaussian random\-walk transition\. For any shiftβ∈ℝ\\beta\\in\\mathbb\{R\}and any stagen<Hn<H,

Qncont​\(s\+β,α\+β\)=Qncont​\(s,α\)\+β\.Q\_\{n\}^\{\\mathrm\{cont\}\}\(s\+\\beta;\\alpha\+\\beta\)=Q\_\{n\}^\{\\mathrm\{cont\}\}\(s;\\alpha\)\+\\beta\.

###### Proof of Lemma[A\.2](https://arxiv.org/html/2609.25645#A1.Thmtheorem2)\.

The terminal value satisfies

VH​\(s\+β,α\+β\)=max⁡\{s\+β,α\+β\}=VH​\(s,α\)\+β\.V\_\{H\}\(s\+\\beta;\\alpha\+\\beta\)=\\max\\\{s\+\\beta,\\alpha\+\\beta\\\}=V\_\{H\}\(s;\\alpha\)\+\\beta\.Assume the corresponding shift identity holds for the next\-stage value\. Since the transition kernel is Gaussian with additive mean, the next state froms\+βs\+\\betahas the same distribution asSn\+1\+βS\_\{n\+1\}\+\\betawhen the current state isss\. Therefore

Qncont​\(s\+β,α\+β\)\\displaystyle Q\_\{n\}^\{\\mathrm\{cont\}\}\(s\+\\beta;\\alpha\+\\beta\)=−c\+𝔼⁡\[Vn\+1​\(Sn\+1\+β,α\+β\)∣Sn=s\]\\displaystyle=\-c\+\\mathbb\{E\}\\\!\\left\[V\_\{n\+1\}\(S\_\{n\+1\}\+\\beta;\\alpha\+\\beta\)\\mid S\_\{n\}=s\\right\]=−c\+𝔼⁡\[Vn\+1​\(Sn\+1,α\)\+β∣Sn=s\]\\displaystyle=\-c\+\\mathbb\{E\}\\\!\\left\[V\_\{n\+1\}\(S\_\{n\+1\};\\alpha\)\+\\beta\\mid S\_\{n\}=s\\right\]=Qncont​\(s,α\)\+β\.\\displaystyle=Q\_\{n\}^\{\\mathrm\{cont\}\}\(s;\\alpha\)\+\\beta\.Taking the maximum with the shifted outside reward gives the next\-stage value identity needed for the induction\. The result follows by backward induction\. ∎

###### Corollary A\.3\(Centered continuation value\)\.

Letx:=s−αx:=s\-\\alphaand defineqn​\(x\):=Qncont​\(x,0\)q\_\{n\}\(x\):=Q\_\{n\}^\{\\mathrm\{cont\}\}\(x;0\)\. For anyn<Hn<H,

Qncont​\(s,α\)=qn​\(s−α\)\+α\.Q\_\{n\}^\{\\mathrm\{cont\}\}\(s;\\alpha\)=q\_\{n\}\(s\-\\alpha\)\+\\alpha\.Thus evaluating the unfinished arm is worthwhile exactly whenqn​\(s−α\)\>0q\_\{n\}\(s\-\\alpha\)\>0\.

###### Proof\.

Apply Lemma[A\.2](https://arxiv.org/html/2609.25645#A1.Thmtheorem2)to the centered statex=s−αx=s\-\\alpha, outside reward00, and shiftβ=α\\beta=\\alpha\. Then

Qncont​\(s,α\)=Qncont​\(s−α,0\)\+α=qn​\(s−α\)\+α\.Q\_\{n\}^\{\\mathrm\{cont\}\}\(s;\\alpha\)=Q\_\{n\}^\{\\mathrm\{cont\}\}\(s\-\\alpha;0\)\+\\alpha=q\_\{n\}\(s\-\\alpha\)\+\\alpha\.Continuing is preferable to the outside reward precisely whenQncont​\(s,α\)\>αQ\_\{n\}^\{\\mathrm\{cont\}\}\(s;\\alpha\)\>\\alpha, which is equivalent toqn​\(s−α\)\>0q\_\{n\}\(s\-\\alpha\)\>0\. ∎

Define the centered value

Wn​\(x\):=Vn​\(α\+x,α\)−α\.W\_\{n\}\(x\):=V\_\{n\}\(\\alpha\+x;\\alpha\)\-\\alpha\.Then the recursion no longer depends onα\\alpha:

WH​\(x\)\\displaystyle W\_\{H\}\(x\)=max⁡\{x,0\},\\displaystyle=\\max\\\{x,0\\\},\(14\)Wn​\(x\)\\displaystyle W\_\{n\}\(x\)=max⁡\{0,qn​\(x\)\},\\displaystyle=\\max\\\{0,q\_\{n\}\(x\)\\\},qn​\(x\)\\displaystyle q\_\{n\}\(x\)=−c\+𝔼⁡\[Wn\+1​\(Xn\+1\)∣Xn=x\],\\displaystyle=\-c\+\\mathbb\{E\}\\\!\\left\[W\_\{n\+1\}\(X\_\{n\+1\}\)\\mid X\_\{n\}=x\\right\],whereXn\+1\|Xn=x∼𝒩⁡\(x,σn2\)X\_\{n\+1\}\\mid X\_\{n\}=x\\sim\\mathcal\{N\}\(x,\\sigma\_\{n\}^\{2\}\)and the recursion forWnW\_\{n\}applies forn<Hn<H\. This is the one\-dimensional dynamic program: for each stagenn, the numerical grid is only over the centered posterior\-mean advantagexx\.

For comparison with an outside rewardα\\alpha, evaluating an unfinished arm is worthwhile exactly whenqn​\(s−α\)\>0q\_\{n\}\(s\-\\alpha\)\>0\. Letrnr\_\{n\}denote the crossing point satisfying

qn​\(rn\)=0\.q\_\{n\}\(r\_\{n\}\)=0\.The Gittins index for costccis therefore

Gnc​\(s\)=s−rn\.G\_\{n\}^\{c\}\(s\)=s\-r\_\{n\}\.\(15\)The online policy does not need to store the full two\-argument value function\. During precomputation we represent the one\-dimensional functionsWnW\_\{n\}andqnq\_\{n\}on a grid in order to propagate the recursion backward\. The exact policy is characterized by the roots\{rn\}n=0H−1\\\{r\_\{n\}\\\}\_\{n=0\}^\{H\-1\}, while the numerical policy stores their gridded approximations\{r^n\}n=0H−1\\\{\\widehat\{r\}\_\{n\}\\\}\_\{n=0\}^\{H\-1\}defined below\.

### A\.4FFT Implementation

For completeness, we summarize the offline FFT computation used in our implementation\. The piecewise\-linear expected\-improvement construction and its Gaussian expectation are derived in\([Xie, 2026](https://arxiv.org/html/2609.25645#bib.bib18), Section 5\.3\.3 and Appendix D\.2\)\.

Fixn<Hn<H, letZn∼𝒩⁡\(0,σn2\)Z\_\{n\}\\sim\\mathcal\{N\}\(0,\\sigma\_\{n\}^\{2\}\)withσn2:=vn2/\(vn\+τ2\)\\sigma\_\{n\}^\{2\}:=v\_\{n\}^\{2\}/\(v\_\{n\}\+\\tau^\{2\}\), and use a uniform gridξj:=ξ0\+j​δ\\xi\_\{j\}:=\\xi\_\{0\}\+j\\delta,j=0,…,P−1j=0,\\ldots,P\-1\. Forwj:=Wn\+1​\(ξj\)w\_\{j\}:=W\_\{n\+1\}\(\\xi\_\{j\}\), set

m0:=0,mi:=wi−wi−1δ​\(1≤i<P\),mP:=1,di:=mi\+1−mi\.m\_\{0\}:=0,\\qquad m\_\{i\}:=\\frac\{w\_\{i\}\-w\_\{i\-1\}\}\{\\delta\}\\ \(1\\leq i<P\),\\qquad m\_\{P\}:=1,\\qquad d\_\{i\}:=m\_\{i\+1\}\-m\_\{i\}\.The boundary\-extended piecewise\-linear surrogate is

W^n\+1​\(x\):=w0\+∑i=0P−1di​\(x−ξi\)\+\.\\widehat\{W\}\_\{n\+1\}\(x\):=w\_\{0\}\+\\sum\_\{i=0\}^\{P\-1\}d\_\{i\}\(x\-\\xi\_\{i\}\)\_\{\+\}\.WritingEIσ⁡\(z\):=𝔼⁡\[\(z\+Z\)\+\]=z​Φ​\(z/σ\)\+σ​ϕ​\(z/σ\)\\operatorname\{EI\}\_\{\\sigma\}\(z\):=\\mathbb\{E\}\[\(z\+Z\)\_\{\+\}\]=z\\Phi\(z/\\sigma\)\+\\sigma\\phi\(z/\\sigma\)forZ∼𝒩⁡\(0,σ2\)Z\\sim\\mathcal\{N\}\(0,\\sigma^\{2\}\)gives

𝔼⁡\[W^n\+1​\(ξj\+Zn\)\]=w0\+∑i=0P−1di​EIσn⁡\(\(j−i\)​δ\)\.\\mathbb\{E\}\[\\widehat\{W\}\_\{n\+1\}\(\\xi\_\{j\}\+Z\_\{n\}\)\]=w\_\{0\}\+\\sum\_\{i=0\}^\{P\-1\}d\_\{i\}\\operatorname\{EI\}\_\{\\sigma\_\{n\}\}\(\(j\-i\)\\delta\)\.
The sum is a linear convolution\. Store𝒅=\(d0,…,dP−1\)\\bm\{d\}=\(d\_\{0\},\\ldots,d\_\{P\-1\}\)and the length\-\(2​P−1\)\(2P\-1\)kernel

eℓ\(n\):=EIσn\(\(ℓ−\(P−1\)\)δ\),ℓ=0,…,2P−2\.e^\{\(n\)\}\_\{\\ell\}:=\\operatorname\{EI\}\_\{\\sigma\_\{n\}\}\(\(\\ell\-\(P\-1\)\)\\delta\),\\qquad\\ell=0,\\ldots,2P\-2\.If𝒉\(n\):=𝒅∗𝒆\(n\)\\bm\{h\}^\{\(n\)\}:=\\bm\{d\}\*\\bm\{e\}^\{\(n\)\}is their full convolution, the requiredPPvalues are the*valid*slicehP−1\(n\),…,h2​P−2\(n\)h^\{\(n\)\}\_\{P\-1\},\\ldots,h^\{\(n\)\}\_\{2P\-2\}\. The full convolution has lengthP\+\(2​P−1\)−1=3​P−2P\+\(2P\-1\)\-1=3P\-2, so zero\-padding both inputs to an FFT lengthL≥3​P−2L\\geq 3P\-2prevents circular wrap\-around; for the experimental gridP=1025P=1025, we useL=4096L=4096\.

The backward update and numerical crossing are

qn​\(ξj\):=−c\+w0\+hj\+P−1\(n\),Wn​\(ξj\):=max⁡\{0,qn​\(ξj\)\},r^n:=min⁡\{ξj:qn​\(ξj\)≥0\}\.q\_\{n\}\(\\xi\_\{j\}\):=\-c\+w\_\{0\}\+h^\{\(n\)\}\_\{j\+P\-1\},\\qquad W\_\{n\}\(\\xi\_\{j\}\):=\\max\\\{0,q\_\{n\}\(\\xi\_\{j\}\)\\\},\\qquad\\widehat\{r\}\_\{n\}:=\\min\\\{\\xi\_\{j\}:q\_\{n\}\(\\xi\_\{j\}\)\\geq 0\\\}\.Each stage takes𝒪⁡\(P​log⁡P\)\\mathcal\{O\}\(P\\log P\)time and𝒪⁡\(P\)\\mathcal\{O\}\(P\)working memory, giving𝒪⁡\(H​P​log⁡P\)\\mathcal\{O\}\(HP\\log P\)time overHHstages rather than𝒪⁡\(H​P2\)\\mathcal\{O\}\(HP^\{2\}\)for explicit summation\. In exact arithmetic the FFT reproduces the discrete convolution; approximation relative to the continuous dynamic program remains from the grid, boundary extension, root discretization, and floating\-point arithmetic\.

## Appendix BAnytime Recommendation for Full\-Benchmark Empirical Means

#### Posterior of the full empirical mean\.

For the finite\-benchmark specialization in Section[3\.4](https://arxiv.org/html/2609.25645#S3.SS4), fix an arm and suppress its index\. Of theNNavailable scores, letNtN\_\{t\}have been observed with sumRtR\_\{t\}, leavingmt=N−Ntm\_\{t\}=N\-N\_\{t\}unobserved\. Conditional on the latent meanθ\\theta, the remaining scores are independent under our Gaussian surrogate, with meanθ\\thetaand varianceτcell2\\tau\_\{\\mathrm\{cell\}\}^\{2\}\. Letℋt\\mathcal\{H\}\_\{t\}denote all observations collected through global allocation steptt\. Given the latent posteriorθ\|ℋt∼𝒩⁡\(μt,vt\)\\theta\\mid\\mathcal\{H\}\_\{t\}\\sim\\mathcal\{N\}\(\\mu\_\{t\},v\_\{t\}\),

Z¯:=Rt\+∑j​unobservedZjN\.\\bar\{Z\}:=\\frac\{R\_\{t\}\+\\sum\_\{j\\,\\mathrm\{unobserved\}\}Z\_\{j\}\}\{N\}\.Restoring the arm index, letNk,tN\_\{k,t\}be the observed\-example count,mk,t:=N−Nk,tm\_\{k,t\}:=N\-N\_\{k,t\}the remaining\-example count, andnk​\(t\)n\_\{k\}\(t\)the number of posterior updates \(batches\)\. Taking conditional expectations and applying the law of total variance give

Mk,t\\displaystyle M\_\{k,t\}:=𝔼⁡\[Z¯k∣ℋt\]=Rk,t\+mk,t​μk,nk​\(t\)N,\\displaystyle:=\\mathbb\{E\}\[\\bar\{Z\}\_\{k\}\\mid\\mathcal\{H\}\_\{t\}\]=\\frac\{R\_\{k,t\}\+m\_\{k,t\}\\mu\_\{k,n\_\{k\}\(t\)\}\}\{N\},\(16\)Vk,t\\displaystyle V\_\{k,t\}:=Var⁡\(Z¯k∣ℋt\)=mk,t2​vk,nk​\(t\)\+mk,t​τcell2N2\.\\displaystyle:=\\operatorname\{Var\}\(\\bar\{Z\}\_\{k\}\\mid\\mathcal\{H\}\_\{t\}\)=\\frac\{m\_\{k,t\}^\{2\}v\_\{k,n\_\{k\}\(t\)\}\+m\_\{k,t\}\\tau\_\{\\mathrm\{cell\}\}^\{2\}\}\{N^\{2\}\}\.For full batches,τcell2=B​τ2\\tau\_\{\\mathrm\{cell\}\}^\{2\}=B\\tau^\{2\}\. Both terms are needed: uncertainty about unobserved example scores remains even when the latent mean is accurately estimated\. At completion, the posterior collapses to the known full\-row mean\. Before any observations,M0=μ0M\_\{0\}=\\mu\_\{0\}andV0=v0\+τcell2/NV\_\{0\}=v\_\{0\}\+\\tau\_\{\\mathrm\{cell\}\}^\{2\}/N\. These moments follow from the Gaussian approximation, including when the original benchmark scores are binary or bounded\.

#### Empirical\-target indices and stopping\.

For fixedNN, prior\(μ0,v0\)\(\\mu\_\{0\},v\_\{0\}\), and per\-example noise, the posterior mean of the full\-benchmark empirical target is an affine transformation of the latent posterior mean:

Mt=a​μt\+\(1−a\)​μ0,a:=1\+τcell2N​v0\.M\_\{t\}=a\\mu\_\{t\}\+\(1\-a\)\\mu\_\{0\},\\qquad a:=1\+\\frac\{\\tau\_\{\\mathrm\{cell\}\}^\{2\}\}\{Nv\_\{0\}\}\.LetH:=⌈N/B⌉H:=\\lceil N/B\\rceiland letbn:=min⁡\{B,N−n​B\}b\_\{n\}:=\\min\\\{B,N\-nB\\\}be the predetermined size of local batchn\+1n\+1\. Its noise variance isτcell2/bn\\tau\_\{\\mathrm\{cell\}\}^\{2\}/b\_\{n\}, and

Mn\+1\|Mn∼𝒩⁡\(Mn,a2​vn2vn\+τcell2/bn\)\.M\_\{n\+1\}\\mid M\_\{n\}\\sim\\mathcal\{N\}\\\!\\left\(M\_\{n\},a^\{2\}\\frac\{v\_\{n\}^\{2\}\}\{v\_\{n\}\+\\tau\_\{\\mathrm\{cell\}\}^\{2\}/b\_\{n\}\}\\right\)\.This deterministic schedule of transition variances lets us reuse the centered recursion in Eq\. \([14](https://arxiv.org/html/2609.25645#A1.E14)\) with stateMnM\_\{n\}\. Charging batch costck,n:=λ​bn​c~kc\_\{k,n\}:=\\lambda b\_\{n\}\\widetilde\{c\}\_\{k\}gives the batch\-level root schedule\{rk,n\}n=0H−1\\\{r\_\{k,n\}\\\}\_\{n=0\}^\{H\-1\}\. Thus an unfinished arm has exact index

Gk,t:=Mk,t−rk,nk​\(t\),G\_\{k,t\}:=M\_\{k,t\}\-r\_\{k,n\_\{k\}\(t\)\},whereas a completed arm has terminal indexZ¯k\\bar\{Z\}\_\{k\}\. The transition variance here is the uncertainty resolved by a new batch, not the total remaining varianceVtV\_\{t\}used in the recommendation penalty\.

###### Proof of Proposition[3\.2](https://arxiv.org/html/2609.25645#S3.Thmtheorem2)\.

At batch boundaries,\(Mk,t,nk​\(t\)\)\(M\_\{k,t\},n\_\{k\}\(t\)\)is an arm\-wise Markov state, and the chains are independent under the Gaussian surrogate\. The local stage determines the next batch size, transition variance, and positive batch cost\. Completion reveals the terminal valueMk,t=Z¯kM\_\{k,t\}=\\bar\{Z\}\_\{k\}\. Substituting these chains into the Markov\-chain selection reduction in Appendix[A\.2](https://arxiv.org/html/2609.25645#A1.SS2)therefore gives the stated Gittins policy and required\-completion optimality among policies that act at batch boundaries\. ∎

The implementation replaces the exact roots by gridded approximationsr^k,n\\widehat\{r\}\_\{k,n\}, with each transition using the corresponding batch size, including a partial final batch\. Budget checks occur after each batch, so the final batch can cross the nominal budget\. Completed arms have numerical index equal to their known empirical mean\. The stopping rule records the first post\-batch crossing at which a completed arm attains the largest numerical index\. The optional\-completion evaluation may end before this signal because of a budget or external interruption, use the signal as an adaptive endpoint, or continue sampling past it; in every case, the LCB\-style anytime recommendation remains available\. Numerical discretization, continuation past the signal, and the recommendation rule are outside the batch\-level optimality claim\.

Algorithm 1Optional\-completion Gittins evaluation for full\-benchmark empirical scores0:Prior

\(μ0,v0\)\(\\mu\_\{0\},v\_\{0\}\), raw per\-example costs

\{c~k\}k=1K\\\{\\widetilde\{c\}\_\{k\}\\\}\_\{k=1\}^\{K\}, noise

τcell2\\tau\_\{\\mathrm\{cell\}\}^\{2\},

NNexamples, batch size

BB, cost scale

λ\\lambda, and an evaluation\-end condition \(for example, a budget, external interruption, or the inherited stopping signal\)\.

1:Set

H=⌈N/B⌉H=\\lceil N/B\\rceiland

bn=min⁡\{B,N−n​B\}b\_\{n\}=\\min\\\{B,N\-nB\\\}; precompute gridded empirical\-target roots

\{r^k,n\}n=0H−1\\\{\\widehat\{r\}\_\{k,n\}\\\}\_\{n=0\}^\{H\-1\}using batch noise

τcell2/bn\\tau\_\{\\mathrm\{cell\}\}^\{2\}/b\_\{n\}and batch cost

λ​bn​c~k\\lambda b\_\{n\}\\widetilde\{c\}\_\{k\}\.

2:Initialize latent moments

\(μk,0,vk,0\)=\(μ0,v0\)\(\\mu\_\{k,0\},v\_\{k,0\}\)=\(\\mu\_\{0\},v\_\{0\}\), batch counts

nk​\(0\)=0n\_\{k\}\(0\)=0, observed counts

Nk,0=0N\_\{k,0\}=0, sums

Rk,0=0R\_\{k,0\}=0, and

t=0t=0\.

3:Compute

\(Mk,0,Vk,0\)\(M\_\{k,0\},V\_\{k,0\}\)by Eq\. \([16](https://arxiv.org/html/2609.25645#A2.E16)\); set

k^0\\hat\{k\}\_\{0\}by Eq\. \([13](https://arxiv.org/html/2609.25645#S3.E13)\)\.

4:Compute

G^k,0=Mk,0−r^k,0\\widehat\{G\}\_\{k,0\}=M\_\{k,0\}\-\\widehat\{r\}\_\{k,0\}for every arm\.

5:whilean unfinished arm exists and evaluation has not endeddo

6:Select an unfinished arm

AtA\_\{t\}with largest

G^k,t\\widehat\{G\}\_\{k,t\}\.

7:Evaluate

b=min⁡\{B,N−NAt,t\}b=\\min\\\{B,N\-N\_\{A\_\{t\},t\}\\\}fresh examples and observe their batch mean

Y¯\\overline\{Y\}; charge

λ​b​c~At\\lambda b\\widetilde\{c\}\_\{A\_\{t\}\}to the budget\.

8:Let

n=nAt​\(t\)n=n\_\{A\_\{t\}\}\(t\); update

\(μAt,n\+1,vAt,n\+1\)\(\\mu\_\{A\_\{t\},n\+1\},v\_\{A\_\{t\},n\+1\}\)from

\(μAt,n,vAt,n\)\(\\mu\_\{A\_\{t\},n\},v\_\{A\_\{t\},n\}\)by Eq\. \([3](https://arxiv.org/html/2609.25645#S3.E3)\) with batch noise

τcell2/b\\tau\_\{\\mathrm\{cell\}\}^\{2\}/b\.

9:For every arm

kk, set

Rk,t\+1:=Rk,t\+𝟏\{k=At\}bY¯R\_\{k,t\+1\}:=R\_\{k,t\}\+\\mathbf\{1\}\\\{k=A\_\{t\}\\\}b\\overline\{Y\}and

Nk,t\+1:=Nk,t\+𝟏\{k=At\}bN\_\{k,t\+1\}:=N\_\{k,t\}\+\\mathbf\{1\}\\\{k=A\_\{t\}\\\}b\.

10:Set

nk\(t\+1\):=nk\(t\)\+𝟏\{k=At\}n\_\{k\}\(t\+1\):=n\_\{k\}\(t\)\+\\mathbf\{1\}\\\{k=A\_\{t\}\\\}for every arm

kk, then set

t←t\+1t\\leftarrow t\+1\.

11:Compute

\(Mk,t,Vk,t\)\(M\_\{k,t\},V\_\{k,t\}\)by Eq\. \([16](https://arxiv.org/html/2609.25645#A2.E16)\); set and report

k^t\\hat\{k\}\_\{t\}by Eq\. \([13](https://arxiv.org/html/2609.25645#S3.E13)\)\.

12:Set

G^k,t=Mk,t\\widehat\{G\}\_\{k,t\}=M\_\{k,t\}for completed arms and

G^k,t=Mk,t−r^k,nk​\(t\)\\widehat\{G\}\_\{k,t\}=M\_\{k,t\}\-\\widehat\{r\}\_\{k,n\_\{k\}\(t\)\}otherwise\.

13:ifa completed arm attains

maxk⁡G^k,t\\max\_\{k\}\\widehat\{G\}\_\{k,t\}then

14:Record the inherited Gittins stopping signal if this is the first crossing\.

15:endif

16:endwhile

17:return

k^t\\hat\{k\}\_\{t\}\.

#### Why subtract a posterior standard deviation?

The required\-completion adaptive\-stopping formulation excludes unfinished arms from its terminal output, but the anytime formulation must be able to recommend such an arm at any time\. A mean\-only recommendation treats a high estimate based on very few examples as favorably as the same estimate supported by many examples\. Under a general prior that is optimistic for a benchmark, an unobserved or sparsely observed arm can repeatedly become the recommended arm, lose its lead when evaluated, and be replaced by another uncertain arm\. The scoreMk,t−Vk,tM\_\{k,t\}\-\\sqrt\{V\_\{k,t\}\}discounts this uncertainty without preventing later recommendation once enough evidence accumulates\. Changing the target from the latent mean to the full\-benchmark empirical mean alone does not resolve this effect: when all arms shareNN, prior, and noise, the affine transformation above preserves their mean\-only ranking on the same observed data\.

The coefficient is fixed to one for the reported LCB\-style rule\. It affects which arm is recommended, not which arm is sampled or the stopping time\. The penalty is a stabilization choice rather than a confidence guarantee\. In particular,

𝔼⁡\[maxj⁡Z¯j−Z¯k∣ℋt\]=𝔼⁡\[maxj⁡Z¯j∣ℋt\]−Mk,t,\\mathbb\{E\}\\left\[\\max\_\{j\}\\bar\{Z\}\_\{j\}\-\\bar\{Z\}\_\{k\}\\mid\\mathcal\{H\}\_\{t\}\\right\]=\\mathbb\{E\}\\left\[\\max\_\{j\}\\bar\{Z\}\_\{j\}\\mid\\mathcal\{H\}\_\{t\}\\right\]\-M\_\{k,t\},so mean\-only recommendation remains Bayes optimal for posterior expected simple regret under a trusted model\. LCB can reduce switching without improving average regret in every setting\.

#### Paired recommendation diagnostic\.

An existing diagnostic isolates the recommendation rule on one GSM8K response matrix \(122122arms and10001000examples, matrix seed 1\), using sampling seed 0, batches of1616, unit costs, and Gittins cost scale10−410^\{\-4\}\. For each prior, both rules use the same empirical\-target Gittins sampling trajectory and differ only in the recommendation computed after each batch\. Under the general prior𝒩⁡\(0\.5,0\.04\)\\mathcal\{N\}\(0\.5,0\.04\), subtracting one posterior standard deviation reduces recommendation switches from139139to3838and budget\-weighted mean simple regret from0\.048240\.04824to0\.029030\.02903\. Under the data\-specific prior𝒩⁡\(0\.2,0\.01\)\\mathcal\{N\}\(0\.2,0\.01\), switches decrease from4949to3737, while budget\-weighted mean regret slightly increases from0\.031280\.03128to0\.031770\.03177\. All four recommendations have zero regret at the budget endpoint\. These single\-seed observations illustrate the stabilization mechanism, especially under the general prior; they are not aggregate results or a guarantee of improvement across benchmarks\. The comparison uses unsmoothed post\-batch recommendations over a common12,20012\{,\}200\-evaluation budget; any observation beyond that budget is excluded\.

## Appendix CDataset Details

### C\.1Dataset Description

#### GSM8K and PIQA\.

For GSM8K and PIQA, we use the response matrices released with BanditEval\([Zhou et al\., 2025](https://arxiv.org/html/2609.25645#bib.bib1)\)\. The underlying benchmarks are Grade School Math 8K \(GSM8K\)\([Cobbe et al\., 2021](https://arxiv.org/html/2609.25645#bib.bib6)\)and Physical Interaction: Question Answering \(PIQA\)\([Bisk et al\., 2020](https://arxiv.org/html/2609.25645#bib.bib7)\)\. GSM8K consists of grade\-school math word problems, while PIQA evaluates physical commonsense reasoning through question answering\.

The BanditEval response matrices are constructed from a collection of publicly available language models and sampling configurations\. In particular, BanditEval considers1111models: GPT2, GPT2\-Large, CodeLLaMA, Tulu\-7B, Tulu\-2\-7B, Gemma\-7B, Phi2, Llema\-7B, LLaMA\-2\-7B, Mistral\-7B, and StarCoder\-7B\. For each model, responses are generated using three temperature choices\{0,0\.5,1\}\\\{0,0\.5,1\\\}, two maximum decoding lengths\{128,512\}\\\{128,512\\\}, and two zero\-shot prompting strategies: directly asking for the answer, and using the chain\-of\-thought prompt “Let’s think step by step\.” The Cartesian product of these choices yields11×3×2×2=13211\\times 3\\times 2\\times 2=132possible model–configuration arms\.

However, the released response matrices contain some missing configurations\. As a result, the final matrices used in our experiments contain122122arms for GSM8K and103103arms for PIQA\. Both GSM8K and PIQA contain1,0001\{,\}000examples in the response matrices\. Each benchmark is represented by five independently generated response matrices, corresponding to five random seeds used when querying the LLMs\. Since the benchmark examples and arm set are fixed, the differences across these matrices mainly reflect randomness in LLM response generation\.

#### AlpacaEval\.

We use the AlpacaEval response matrix released with BanditEval\([Zhou et al\., 2025](https://arxiv.org/html/2609.25645#bib.bib1)\)to evaluate instruction\-following quality\([Li et al\., 2023](https://arxiv.org/html/2609.25645#bib.bib16)\)\. Unlike the BanditEval GSM8K and PIQA model×\\timesprompt configuration matrices, this matrix is derived from the AlpacaEval 2\.0 leaderboard comparisons annotated byweighted\_alpaca\_eval\_gpt4\_turbo\. Each row corresponds to one AlpacaEval leaderboard model, and each column corresponds to one of the805805fixed AlpacaEval instructions\. Entry\(k,n\)\(k,n\)stores the model’s pairwise score against the GPT\-4 Turbo baseline on instructionnn\. These scores are continuous values in\[0,1\]\[0,1\]derived from the auto\-annotator’s preference probabilities; they are*not*binary correctness labels\. Accordingly, the full\-benchmark empirical targetZ¯k\\bar\{Z\}\_\{k\}in Eq\. \([10](https://arxiv.org/html/2609.25645#S3.E10)\) is the row mean of these pairwise scores\.

We exclude the annotator rowgpt4\_1106\_preview\_verboseand the degenerategpt4\_1106\_previewrow, whose805805comparison values are all0\.50\.5\. The resulting matrix contains152152leaderboard\-model arms and805805instruction examples\. It keeps the AlpacaEval pairwise scores as continuous values rather than converting them to binary outcomes\. Each arm is therefore a single leaderboard model rather than a model×\\timessampling\-configuration pair\. In contrast to GSM8K and PIQA, we use one fixed AlpacaEval matrix rather than five independently generated response matrices; algorithm randomness enters only through the2020randomized trial seeds used in each sweep\.

For configuration\-level Bayesian optimization baselines, we convert this matrix into152152configuration\-level arms\. Each Bayesian optimization arm evaluates one model on all805805instructions, revealing the row\-average score and consuming that model’s all\-example evaluation cost\. Cost\-aware experiments use model\-specific token prices from our Alpaca pricing table, with an input\-to\-output token ratio of1:81\{:\}8estimated from typical AlpacaEval prompt/response lengths \(Appendix[D](https://arxiv.org/html/2609.25645#A4)\)\. For GittinsEval\-S on AlpacaEval, we use the dataset\-specific prior mean/variance\(0\.2,0\.01\)\(0\.2,\\,0\.01\); GittinsEval\-G uses the general prior\(0\.5,0\.04\)\(0\.5,\\,0\.04\)listed in Table[6](https://arxiv.org/html/2609.25645#A4.T6)\.

#### MMLU\.

For MMLU, we use the DOVE response matrices\([Habba et al\., 2025](https://arxiv.org/html/2609.25645#bib.bib2)\)\. MMLU is a multiple\-choice question\-answering benchmark consisting of5757subjects and approximately14,00014\{,\}000examples in total\. We treat each MMLU subject as a separate problem instance\. Each subject is evaluated across1515LLM configurations and100100prompting techniques, resulting in15001500arms per subject\.

The1515LLM configurations used in the MMLU response matrices are Llama\-3\-8B, Llama\-3\-8B\-Instruct, Llama\-3\-70B\-Instruct, CodeLlama\-34B\-Instruct, FLAN\-T5\-XL, FLAN\-T5\-XXL, FLAN\-UL2, Merlinite\-7B, Mixtral\-8x7B\-Instruct\-v0\.1, Mistral\-7B\-Instruct\-v0\.2, Gemma\-7B, Gemma\-7B\-IT, Falcon\-40B, Mistral\-7B\-v0\.1, and Falcon\-180B\. The number of examples varies across subjects; the full list of subjects used in our evaluation is provided in Table[1](https://arxiv.org/html/2609.25645#A3.T1)\.

### C\.2Dataset Statistics

We provide descriptive statistics for the response matrices used in our evaluation\. For each dataset or subject, we compute the empirical quality of each arm as its mean score over benchmark examples\. For binary correctness matrices, this score is mean accuracy; for AlpacaEval, it is the mean pairwise preference score\. The following figures visualize the resulting distribution of arm qualities\. These plots help illustrate the spread of arm performance, the location of the empirical mean, the best arm, and the prior mean used in informative\-prior experiments\.

#### GSM8K and PIQA\.

Figure[4](https://arxiv.org/html/2609.25645#A3.F4)shows the per\-arm quality distributions for GSM8K and PIQA across the five independently generated response matrices\. The distributions are highly stable across seeds for both datasets\. This indicates that, although the response matrices are generated independently, the randomness from LLM response generation introduces only limited variation at the aggregate level\. GSM8K has a noticeably lower overall accuracy distribution than PIQA, while PIQA exhibits a tighter concentration of high\-quality arms\.

![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/quality_distributions/banditeval_quality_gsm8k_piqa_alpaca_11panels_cols4.png)Figure 4:Per\-arm quality distributions for GSM8K, PIQA, and AlpacaEval\. Each panel shows one response matrix; bars report mean accuracy for GSM8K and PIQA and mean pairwise score for AlpacaEval\. Vertical lines mark the empirical mean \(red\), best arm \(green\), and prior mean \(purple\)\.
#### MMLU\.

For MMLU, we treat each subject as a separate problem instance\. We divide the subjects into three difficulty buckets according to the empirical mean arm quality of the subject\. The intuition is that if the mean arm quality is high, then the subject is easier for the collection of LLM configurations and prompting techniques; conversely, a lower mean arm quality indicates a harder subject\. We refer to these buckets as high\-, medium\-, and low\-prior buckets, with prior meansμ0=0\.75\\mu\_\{0\}=0\.75,μ0=0\.6\\mu\_\{0\}=0\.6, andμ0=0\.4\\mu\_\{0\}=0\.4, respectively\. Figures[5](https://arxiv.org/html/2609.25645#A3.F5)–[7](https://arxiv.org/html/2609.25645#A3.F7)show the per\-arm quality distributions for the three buckets\.

![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/quality_distributions/mmlu_quality_distributions_prior_high_17tasks_cols4.png)Figure 5:Per\-arm accuracy distributions for easy MMLU subjects in the high\-prior bucket \(μ0=0\.75\\mu\_\{0\}=0\.75\)\. Each panel shows one subject; vertical lines mark the empirical mean \(red\), best arm \(green\), and prior mean \(purple\)\.![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/quality_distributions/mmlu_quality_distributions_prior_medium_22tasks_cols4.png)Figure 6:Per\-arm accuracy distributions for medium\-difficulty MMLU subjects in the medium\-prior bucket \(μ0=0\.6\\mu\_\{0\}=0\.6\)\. Each panel shows one subject; vertical lines mark the empirical mean \(red\), best arm \(green\), and prior mean \(purple\)\.![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/quality_distributions/mmlu_quality_distributions_prior_low_18tasks_cols4.png)Figure 7:Per\-arm accuracy distributions for hard MMLU subjects in the low\-prior bucket \(μ0=0\.4\\mu\_\{0\}=0\.4\)\. Each panel shows one subject; vertical lines mark the empirical mean \(red\), best arm \(green\), and prior mean \(purple\)\.Table 1:MMLU datasets used in our evaluation\. Each subject produces a response matrix with15001500rows \(arms\), corresponding to1515LLM configurations paired with100100prompting techniques, andNNcolumns corresponding to the benchmark examples\. Thus, the matrix has shape1500×N1500\\times Nand contains1500​N1500Nobservation cells\. Difficulty is based on prior accuracy: datasets with high prior accuracy are labeled easy, those with medium prior accuracy are labeled medium, and those with low prior accuracy are labeled hard\. The size category groups datasets by the number of benchmark examples\.DatasetMatrix ShapeDifficultySizeFull NameAbstract Alg\.1500×1001500\\times 100hardsmallAbstract AlgebraAnatomy1500×1351500\\times 135mediumsmallAnatomyAstronomy1500×1521500\\times 152mediummediumAstronomyBusiness Ethics1500×1001500\\times 100mediumsmallBusiness EthicsClinical Know\.1500×2651500\\times 265mediummediumClinical KnowledgeCollege Biology1500×1441500\\times 144mediumsmallCollege BiologyCollege Chem1500×1001500\\times 100hardsmallCollege ChemistryCollege CS1500×1001500\\times 100hardsmallCollege Computer ScienceCollege Math1500×1001500\\times 100hardsmallCollege MathematicsCollege Medicine1500×1731500\\times 173mediummediumCollege MedicineCollege Physics1500×1021500\\times 102hardsmallCollege PhysicsComp Security1500×1001500\\times 100easysmallComputer SecurityConceptual Phys1500×2351500\\times 235mediummediumConceptual PhysicsEconometrics1500×1141500\\times 114hardsmallEconometricsElectrical Eng1500×1451500\\times 145mediumsmallElectrical EngineeringElementary Math1500×3781500\\times 378hardmediumElementary MathematicsFormal Logic1500×1261500\\times 126hardsmallFormal LogicGlobal Facts1500×1001500\\times 100hardsmallGlobal FactsHS Biology1500×3101500\\times 310easymediumHigh School BiologyHS Chem1500×2031500\\times 203hardmediumHigh School ChemistryHS CS1500×1001500\\times 100mediumsmallHigh School Computer ScienceHS Euro Hist1500×1651500\\times 165mediummediumHigh School European HistoryHS Geography1500×1981500\\times 198easymediumHigh School GeographyHS Gov & Pol1500×1931500\\times 193easymediumHigh School Government and PoliticsHS Macroecon1500×3901500\\times 390mediummediumHigh School MacroeconomicsHS Math1500×2701500\\times 270hardmediumHigh School MathematicsHS Microecon1500×2381500\\times 238mediummediumHigh School MicroeconomicsHS Physics1500×1511500\\times 151hardmediumHigh School PhysicsHS Psychology1500×5451500\\times 545easylargeHigh School PsychologyHS Statistics1500×2161500\\times 216hardmediumHigh School StatisticsHS US Hist1500×2041500\\times 204easymediumHigh School US HistoryHS World Hist1500×2371500\\times 237easymediumHigh School World HistoryHuman Aging1500×2231500\\times 223mediummediumHuman AgingHuman Sexuality1500×1311500\\times 131easysmallHuman SexualityInt’l Law1500×1211500\\times 121easysmallInternational LawJurisprudence1500×1081500\\times 108easysmallJurisprudenceLogical Fallacies1500×1631500\\times 163easymediumLogical FallaciesMachine Learning1500×1121500\\times 112hardsmallMachine LearningManagement1500×1031500\\times 103easysmallManagementMarketing1500×2341500\\times 234easymediumMarketingMedical Genetics1500×1001500\\times 100mediumsmallMedical GeneticsMisc1500×7831500\\times 783easylargeMiscellaneousMoral Disputes1500×3461500\\times 346mediummediumMoral DisputesMoral Scenarios1500×8951500\\times 895hardlargeMoral ScenariosNutrition1500×3061500\\times 306mediummediumNutritionPhilosophy1500×3111500\\times 311mediummediumPhilosophyPrehistory1500×3241500\\times 324mediummediumPrehistoryProf Accounting1500×2821500\\times 282hardmediumProfessional AccountingProf Law1500×15341500\\times 1534hardlargeProfessional LawProf Medicine1500×2721500\\times 272mediummediumProfessional MedicineProf Psychology1500×6121500\\times 612mediumlargeProfessional PsychologyPublic Relations1500×1101500\\times 110mediumsmallPublic RelationsSecurity Studies1500×2451500\\times 245mediummediumSecurity StudiesSociology1500×2011500\\times 201easymediumSociologyUS Foreign Policy1500×1001500\\times 100easysmallUS Foreign PolicyVirology1500×1661500\\times 166hardmediumVirologyWorld Religions1500×1711500\\times 171easymediumWorld Religions

## Appendix DExperiment Setup and Implementation Details

#### Computing environment\.

Experiments were run on CPU\-only computing resources using precomputed response matrices rather than online LLM inference\. The response matrix serves as the offline ground\-truth oracle: during bandit simulation, each policy observes only the selected\(arm,question\)\(\\text\{arm\},\\text\{question\}\)entries, while per\-arm matrix means are used to compute simple regret\. For the Bayesian optimization baselines, the response matrices are converted into configuration\-level inputs, where evaluating one candidate reveals its aggregate score\. For GSM8K and PIQA, each converted BanditEval configuration corresponds to a model×\\timesprompt arm\. The BanditEval AlpacaEval matrix instead has one leaderboard\-model arm per row, so each converted Bayesian optimization configuration evaluates that model on all805805instructions\. For MMLU, each converted DOVE configuration corresponds to a model×\\timestemplate arm\. Reported per\-batch runtime therefore measures policy\-side allocation overhead rather than model\-inference time\.

#### Experimental repetitions\.

For GSM8K and PIQA, we run each adaptive policy on each of the five independently generated response matrices\. For every response matrix, we perform2020independent algorithm trials, each with independently randomized example orders and algorithmic randomness\. We report averages over all matrix–trial pairs\. For AlpacaEval, we use a single fixed pairwise score matrix with152152models and805805instructions\. As in MMLU, we run2020independent algorithm trials on this matrix and report averages over those trials\. Unlike GSM8K and PIQA, we do not average over multiple independently generated response matrices for AlpacaEval\. For MMLU, we run2020randomized algorithm trials for each subject and aggregate results across the corresponding set of subjects\. The Bayesian optimization baselines use the same randomized\-trial structure on their converted configuration\-level inputs\.

#### Anytime recommendations and regret\.

At each reporting step, GittinsEval\-G and GittinsEval\-S recommend the arm maximizingMk,t−Vk,tM\_\{k,t\}\-\\sqrt\{V\_\{k,t\}\}as in Eq\. \([13](https://arxiv.org/html/2609.25645#S3.E13)\), whereMk,tM\_\{k,t\}andVk,tV\_\{k,t\}are the posterior mean and variance of the full\-row empirical score, given in Eq\. \([16](https://arxiv.org/html/2609.25645#A2.E16)\)\. This optional\-completion recommendation considers all arms, including those with unevaluated examples; it does not require the recommended arm to be completed\. For an arm that has been fully evaluated,Mk,tM\_\{k,t\}equals its observed row mean andVk,t=0V\_\{k,t\}=0\. The uncertainty penalty is intended to reduce early recommendation switching when arms with few observations have unreliable mean estimates, especially under a general prior; see Appendix[B](https://arxiv.org/html/2609.25645#A2)\. Simple regret is always computed from the recommended arm’s actual full\-row mean in the response matrix, not from its posterior mean or its penalized recommendation score\. The penalty affects recommendation only; it does not enter the numerical Gittins indices used for allocation or affect the stopping time\.

#### GittinsEval stopping time\.

The GittinsEval stopping time is the first post\-batch time at which an arm attaining the largest numerical empirical\-target Gittins index is fully observed\. This is the stopping rule from the required\-completion adaptive\-stopping formulation; it does not restrict the optional\-completion LCB\-style recommendation\. Root discretization, continuation beyond the signal, and the recommendation rule do not inherit the exact batch\-level optimality guarantee\. In fixed\-budget experiments, we record this time and continue the regret trajectory to the evaluation budget\.

#### Baseline initialization and warm\-up\.

For a response matrix withKKarms andNNexamples, the Bayesian optimization baselines use a configuration\-level random\-initialization phase\. In our main Bayesian optimization runs, a5%5\\%random initialization means drawing approximately0\.05​K0\.05Karms uniformly without replacement and observing the full rows for those arms, i\.e\., evaluating the selected configurations on allNNexamples before the acquisition\-driven phase begins\. This corresponds to66initial configurations for GSM8K \(K=122K=122\),55for PIQA \(K=103K=103\),88for AlpacaEval \(K=152K=152\), and7575for each MMLU subject \(K=1500K=1500\)\. Under the nominal10%10\\%Bayesian optimization budget, the corresponding total configuration budgets are1212,1010,1515, and150150configurations, respectively\. This convention is distinct from the low\-rank\-factorization warm\-up in BanditEval\([Zhou et al\., 2025](https://arxiv.org/html/2609.25645#bib.bib1)\)\. There, LRF first drawsT0T\_\{0\}individual arm–example pairs uniformly from theK×NK\\times Nresponse matrix, and the default experimental setting usesT0=0\.05​K​NT\_\{0\}=0\.05KN\. The standalone LRF baseline in that paper is also written with aT0T\_\{0\}entry\-level warm\-up parameter, so any such warm\-up should be interpreted as a percentage of response\-matrix entries rather than a percentage of arms evaluated on all benchmark examples\.

#### Curve aggregation and visualization\.

Unless otherwise noted, repeated trajectories for GittinsEval\-G, GittinsEval\-S, UCB\-E, LRF, and SySRs are aggregated on a common budget grid\. For each method and panel, we linearly interpolate each randomized\-run trajectory onto a shared grid of350350evenly spaced points spanning the observed budget range and compute the mean and standard error across the runs available at each grid point\. Values outside a run’s observed range are treated as missing rather than extrapolated, so early\-ending runs are not right\-extended\. The same procedure is used in the unit\-cost and cost\-aware settings, with cumulative evaluation cost defining the horizontal coordinate in both; under unit costs, this equals cumulative example evaluations\. Gittins stopping points are reported only as overlays and do not truncate the regret trajectories\. Bayesian optimization trajectories are handled separately\. We omit the random\-initialization segment from the displayed curves, align the post\-initialization trajectories across randomized runs to their mean initialization endpoint, and aggregate them on the resulting common budget axis\. Runs that terminate earlier are right\-held at their final observed simple regret so that they continue to contribute over the displayed post\-initialization budget range\. This convention is used in both the unit\-cost and cost\-aware settings and is particularly relevant in the latter, where heterogeneous configuration costs lead to different initialization endpoints across runs\. For the cross\-subject MMLU aggregates, each task–run trajectory is first normalized to its reported budget range before interpolation on a common\[0,1\]\[0,1\]grid of350350evenly spaced points, and the resulting task–run curves are pooled within each size–difficulty bucket\. LRF retains its warm\-up offset under this normalization\.

#### PromptEval evaluation and aggregation\.

We evaluate PromptEval\-BAI\([Polo et al\., 2024](https://arxiv.org/html/2609.25645#bib.bib10)\), using this name for PromptEval’s best\-prompt\-identification instantiation in figures and captions\. Its native allocation follows a unit\-cost successive\-halving best\-arm\-identification rule that exploits configuration covariates; costs are recorded so that the same trajectories can be plotted against cumulative observations in the unit\-cost setting and against recorded cumulative costs in the cost\-aware setting\. On GSM8K and PIQA we use five response matrices with2020randomized trials each; on each MMLU subject we use2020randomized trials\. Across GSM8K, PIQA, and MMLU, we use PE\-OneHot, which assigns each candidate arm an identity feature vector; the other PromptEval covariate variants are not included in our comparison\. We do not report PromptEval\-BAI on AlpacaEval because the released best\-arm\-identification implementation assumes binary correctness matrices and therefore does not directly apply to our continuous model\-by\-instruction preference matrix\. PromptEval’s own AlpacaEval experiment instead studies sensitivity to judge prompts and binarizes continuous judge scores for model fitting; it is separate from the paper’s best\-prompt\-identification experiments on MMLU, BBH, and LMentry\. Applying PromptEval\-BAI here would therefore require an additional, non\-native modeling choice such as thresholding the scores\. For the main GSM8K/PIQA curves, we aggregate repeated trajectories by successive\-halving phase, reporting mean simple regret at the mean phase budget with standard\-error bands\. Since PromptEval\-BAI produces recommendations at discrete successive\-halving phase boundaries, we preserve this native phase structure rather than interpolating additional intermediate points\. For individual MMLU subject panels, cost\-aware curves use the same phase\-wise aggregation, while unit\-cost curves instead align trajectories by their average initial budget and interpolate with step\-hold on the union of observed normalized\-cost points, where cost is expressed as a percentage of the exhaustive\-evaluation cost; early\-finishing runs are right\-held to the largest observed end budget among those trajectories\. For the cross\-subject MMLU aggregate plots, we pool subject–seed trajectories on this shared normalized\-cost axis, apply average\-initial alignment, interpolate with step\-hold on the union of observed budget points at or below the nominal10%10\\%budget, and right\-hold early\-finishing runs through that endpoint\.

#### Evaluation costs\.

The cost\-aware bandit experiments assign each arm a batch cost proportional to the estimated cost of running that model configuration onBBbenchmark examples\. For GSM8K and PIQA, an arm is a model plus sampling or prompting configuration; when several arms share a base model, they share the model\-level price, while the batch multiplier accounts for how many examples are queried at that allocation step\. For MMLU, each arm is a model–prompt pair, and model\-level input prices are repeated across the corresponding prompt arms\. For AlpacaEval, each arm is a single leaderboard model rather than a model×\\timessampling\-configuration pair\. Throughout our experiments, costs are model\-level proxies derived from published API prices or model\-level price metadata\. Fixed benchmark\-level input/output ratios convert these prices into a per\-example arm cost, so all examples evaluated by the same arm have the same cost; we do not use example\-specific token counts or latency\. For the Bayesian optimization baselines, each converted input row corresponds to a complete configuration, and its cost is the estimated all\-example evaluation cost of that configuration on the corresponding benchmark or MMLU subject\. The Gittins dynamic program uses costs rescaled to the same utility units as the index computation, while the Bayesian optimization baselines use configuration\-level costs for cost\-aware acquisition and budget accounting\.

#### AlpacaEval evaluation costs\.

AlpacaEval uses model\-specific API or proxy prices for the152152leaderboard models in the response matrix\. For each model, we record separate input and output costs in USD per 1M tokens and form the evaluation cost as

cost=cin\+8​cout,\\text\{cost\}=c\_\{\\mathrm\{in\}\}\+8\\,c\_\{\\mathrm\{out\}\},using the estimated AlpacaEval input\-to\-output token ratio1:81\{:\}8\. These model\-level costs define the per\-arm cost vector for cost\-aware bandit experiments and the all\-example evaluation costs used by the converted Bayesian optimization inputs\. Since AlpacaEval arms are individual leaderboard models rather than BanditEval\-style model×\\timesprompt configurations, we do not repeat a single model price across multiple prompting arms as in MMLU\. Table[2](https://arxiv.org/html/2609.25645#A4.T2)and Table[3](https://arxiv.org/html/2609.25645#A4.T3)therefore do not apply to AlpacaEval; the complete Alpaca pricing table is reported in Table[4](https://arxiv.org/html/2609.25645#A4.T4)\.

Table 2:Model\-level evaluation costs used for GSM8K and PIQA\. Costs are reported in USD per 1M tokens\. GSM8K uses an assumed input\-to\-output token ratio of1:21:2, so the evaluation cost is computed as input cost plus twice the output cost\. PIQA uses input\-only pricing\. These model\-level costs are used to construct the per\-arm cost vectors for the cost\-aware experiments\.Table 3:Model\-level input costs used for MMLU\. Costs are reported in USD per 1M input tokens\. MMLU uses input\-only pricing\. Each MMLU subject contains 1500 arms, corresponding to 15 models paired with 100 prompt configurations; therefore, each model\-level input cost is repeated across the corresponding prompt arms\.Table 4:AlpacaEval model\-level pricing for the152152\-model response matrix\. Input \(In\.\) and output \(Out\.\) prices are in USD per 1M tokens\. The combined evaluation cost isCost=Input\+8×Output\\mathrm\{Cost\}=\\mathrm\{Input\}\+8\\times\\mathrm\{Output\}, matching the input\-to\-output token ratio used for cost\-aware runs\. Models are alphabetized down the left block, then the right block, continuing on the next page\.Table 5:AlpacaEval model\-level pricing \(continued\)\. Prices are in USD per 1M tokens;Cost=Input\+8×Output\\mathrm\{Cost\}=\\mathrm\{Input\}\+8\\times\\mathrm\{Output\}\.
#### Gaussian approximation\.

For benchmark scores grouped in batches, a batch ofBBresponses produces an empirical mean score\. For binary\-accuracy benchmarks such as GSM8K, PIQA, and MMLU, the default observation variance isτ2=1/\(4​B\)\\tau^\{2\}=1/\(4B\), the worst\-case binary variance divided by the batch size\. AlpacaEval matrix entries are continuous pairwise preference scores in\[0,1\]\[0,1\]rather than binary correctness labels\. Since any random variable supported on\[0,1\]\[0,1\]has variance at most1/41/4, we also use the conservative per\-comparison working varianceτcell2=1/4\\tau\_\{\\mathrm\{cell\}\}^\{2\}=1/4for AlpacaEval\. Under the working conditional\-independence approximation, this gives the batch\-mean varianceτ2=1/\(4​B\)\\tau^\{2\}=1/\(4B\)\. This fixed value is a conservative working bound, not an empirical variance estimate\.

#### Prior settings\.

All arms use the same prior mean and variance, representing a shared belief before benchmark\-specific evidence is collected\. Table[6](https://arxiv.org/html/2609.25645#A4.T6)lists the general default prior and the data\-specific common priors used by GittinsEval\-G and GittinsEval\-S\. Figures[5](https://arxiv.org/html/2609.25645#A3.F5),[6](https://arxiv.org/html/2609.25645#A3.F6), and[7](https://arxiv.org/html/2609.25645#A3.F7)show the MMLU latent\-accuracy distributions used to motivate the informative prior buckets\.

Table 6:Prior settings used in the Gittins\-index experiments\. We report Gaussian priors as𝒩⁡\(μ0,v0\)\\mathcal\{N\}\(\\mu\_\{0\},v\_\{0\}\)\. The default prior is a general accuracy\-scale choice\. Dataset\-specific priors provide shared benchmark\-level information without using arm\-specific prior means\.

## Appendix EAdditional Experiment Results

### E\.1Ablation Studies

We include four ablations to separate the statistical and cost\-sensitive components of the Gittins index policy\.

#### Choice of common prior\.

We compare the common priors listed in Table[6](https://arxiv.org/html/2609.25645#A4.T6)\. This ablation tests whether Bayesian allocation gains come from useful shared prior information or from the index rule alone, without giving different arms different prior means\. The resulting comparison between GittinsEval\-G, which uses the general prior, and GittinsEval\-S, which uses the data\-specific common prior, is reported in Figures[2](https://arxiv.org/html/2609.25645#S4.F2)and[3](https://arxiv.org/html/2609.25645#S4.F3); full per\-subject MMLU results are provided in Figures[13](https://arxiv.org/html/2609.25645#A5.F13)–[18](https://arxiv.org/html/2609.25645#A5.F18)\.

Table 7:Batch\-size settings used in the simple\-regret experiments\. For UCB\-E and both Gittins variants, batch sizeBBdenotes the number of examples queried for the selected arm at each allocation step\. For AlpacaEval, these examples correspond to instruction\-level pairwise preference scores rather than binary correctness labels\. Because LRF’s repeated low\-rank updates make smaller batches prohibitively slow, LRF usesB=32B=32in all reported settings\. Bayesian optimization baselines operate at the configuration level, so evaluating one candidate reveals its aggregate score and does not use a bandit batch size\. For MMLU, subject matrices are grouped by the number of benchmark examples, and the batch\-size grid for UCB\-E and Gittins is chosen according to this subject\-size bucket\.
#### Batch size\.

For UCB\-E and the Gittins variants, we vary the batch sizeBBused to construct empirical batch\-mean observations\. Smaller batches provide more frequent adaptation but noisier observations; larger batches reduce Gaussian approximation error and posterior noise but make each allocation decision coarser\. Because LRF’s repeated low\-rank updates make smaller batches prohibitively slow, we useB=32B=32for LRF in the reported settings\. Bayesian optimization baselines operate at the configuration level and therefore do not use a bandit batch size\. Table[7](https://arxiv.org/html/2609.25645#A5.T7)summarizes the batch\-size grids used for GSM8K, PIQA, MMLU, and AlpacaEval\. On AlpacaEval, each batch query corresponds toBBadditional pairwise comparisons for the selected model rather thanBBindependent benchmark examples with binary labels\.

Figures[8](https://arxiv.org/html/2609.25645#A5.F8)and[9](https://arxiv.org/html/2609.25645#A5.F9)show that batch size primarily affects the low\-budget regime\. On GSM8K, PIQA, and AlpacaEval,B=8B=8consistently provides the best early sample efficiency: its simple regret falls more quickly, whereas larger batches can spend more evaluations before the posterior and acquisition policy are updated\. The effect is clearest forB=32B=32on unit\-cost GSM8K, where early regret is substantially higher\. The curves approach one another as the budget grows, suggesting that batch size has a larger effect on early efficiency and stopping cost than on the final recommendation\. Differences are smaller under cost\-aware evaluation, butB=8B=8still provides the best overall cost efficiency across these benchmarks\.

![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/ablation/gsm8k_piqa_alpaca_batch_size_sensitivity_2x3.png)Figure 8:Batch\-size sensitivity on GSM8K, PIQA, and AlpacaEval forB∈\{8,16,32\}B\\in\\\{8,16,32\\\}\. The top row uses unit costs and the bottom row uses original costs\. Curves show mean simple regret against cumulative evaluation cost as a percentage of exhaustive evaluation; bands denote±1\\pm 1standard error and dashed lines mark mean natural\-stopping cost\. GSM8K and PIQA average 100 runs each, and AlpacaEval averages 20 runs\.For MMLU, the smallest batch in each size\-specific grid likewise tends to have the lowest overall simple regret:B=2B=2for small subjects,B=4B=4for medium subjects, andB=8B=8for large subjects\. Larger batches are generally less efficient at low budgets because the policy updates only after an entire batch is completed; on the medium and large groups, they also tend to delay natural stopping\. The late\-budget convergence indicates qualitative robustness to batch size and supports the size\-adaptive defaultB=2/4/8B=2/4/8\. The stopping lines for the small group require additional care: some configurations stop naturally on only a subset of subjects, so the plotted mean is conditional on the subjects with an observed stop and should not be compared without also considering stopping coverage\.

![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/ablation/mmlu_batch_size_sensitivity_aggregate_2x3.png)Figure 9:Batch\-size sensitivity across the 57 MMLU subjects, grouped as small \(22\), medium \(30\), and large \(5\), with gridsB∈\{2,4,8\}B\\in\\\{2,4,8\\\},B∈\{4,8,16\}B\\in\\\{4,8,16\\\}, andB∈\{8,16,32\}B\\in\\\{8,16,32\\\}\. The top row uses unit costs and the bottom row uses original costs\. Curves show equally weighted subject means against cumulative evaluation cost as a percentage of exhaustive evaluation; bands denote±1\\pm 1subject\-level standard error and dashed lines average subjects with observed natural stops\.
#### Cost\-scaling factor\.

The Gittins index policy uses a cost\-scaling factor to map evaluation costs into the continuation penalty in the index computation\. In the unit\-cost setting, this factor is applied to a common unit cost for each evaluation; in the cost\-aware setting, it is applied to the original per\-evaluation costs\. This parameter controls the effective price of continuing to sample: larger values make additional evaluations more costly and therefore favor earlier stopping, whereas smaller values encourage longer exploration\. In our experiments, we sweep three cost\-scaling factors,10−310^\{\-3\},10−410^\{\-4\}, and10−510^\{\-5\}, for both unit\-cost and cost\-aware Gittins variants\. Unless otherwise specified, the main reported figures use10−410^\{\-4\}, which we found to provide a representative balance between stopping early and continuing exploration\.

Figure[10](https://arxiv.org/html/2609.25645#A5.F10)confirms the expected stopping\-time trade\-off on GSM8K, PIQA, and AlpacaEval: increasingλ\\lambdatriggers natural stopping earlier, butλ=10−3\\lambda=10^\{\-3\}is often too aggressive\. Under unit costs it consistently shows higher early simple regret on GSM8K and AlpacaEval, indicating that stopping too soon can degrade recommendation quality\. The regret curves for10−510^\{\-5\}and10−410^\{\-4\}are generally close, but10−510^\{\-5\}usually requires more evaluation cost before stopping\. The three settings are less separated in the cost\-aware panels\. Thus,λ=10−4\\lambda=10^\{\-4\}is not uniformly optimal on every individual dataset, but it provides the most reliable trade\-off among regret, stopping time, and cross\-dataset stability\.

![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/ablation/gsm8k_piqa_alpaca_lambda_sensitivity_2x3.png)Figure 10:Cost\-scaling sensitivity on GSM8K, PIQA, and AlpacaEval forλ∈\{10−5,10−4,10−3\}\\lambda\\in\\\{10^\{\-5\},10^\{\-4\},10^\{\-3\}\\\}\. The top row uses unit costs and the bottom row uses original costs\. Curves show mean simple regret against cumulative evaluation cost as a percentage of exhaustive evaluation; bands denote±1\\pm 1standard error and dashed lines mark mean natural\-stopping cost\. GSM8K and PIQA average 100 runs each, and AlpacaEval averages 20 runs\.The same pattern is visible across the MMLU size groups in Figure[11](https://arxiv.org/html/2609.25645#A5.F11)\. The conservativeλ=10−5\\lambda=10^\{\-5\}setting reduces regret more slowly and does not naturally stop within the 10% budget on some subjects\. In contrast,λ=10−3\\lambda=10^\{\-3\}stops very early but has consistently higher early regret on the medium and large groups\. This behavior is especially pronounced for cost\-aware large subjects, suggesting that a large continuation penalty can terminate evaluation before a reliable configuration has been identified\. Across size groups and cost settings,λ=10−4\\lambda=10^\{\-4\}reduces regret quickly while retaining reasonable stopping times\. Althoughλ=10−3\\lambda=10^\{\-3\}sometimes attains slightly lower late regret on the small group, its worse early behavior does not overturn10−410^\{\-4\}as the global default\. Since the large group contains only five subjects and some error bands are wide, we interpret these results as a consistent trend rather than a claim of statistical significance\.

![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/ablation/mmlu_lambda_sensitivity_aggregate_2x3.png)Figure 11:Cost\-scaling sensitivity across the 57 MMLU subjects, grouped as small \(22\), medium \(30\), and large \(5\), forλ∈\{10−5,10−4,10−3\}\\lambda\\in\\\{10^\{\-5\},10^\{\-4\},10^\{\-3\}\\\}\. The top row uses unit costs and the bottom row uses original costs\. Curves show equally weighted subject means against cumulative evaluation cost as a percentage of exhaustive evaluation; bands denote±1\\pm 1subject\-level standard error and dashed lines mark mean natural\-stopping cost\.Overall, the method is qualitatively robust over the examined hyperparameter ranges, while hyperparameter selection matters most in the low\-budget regime\. The defaultλ=10−4\\lambda=10^\{\-4\}avoids both the overly conservative behavior of10−510^\{\-5\}and the premature stopping associated with10−310^\{\-3\}\. Batch\-size sensitivity is likewise modest beyond the low\-budget regime: smaller batches generally provide better early sample efficiency through more frequent adaptation, whereas larger batches require fewer sequential posterior updates and allocation decisions and can therefore reduce policy\-side overhead\. Accordingly, the main\-text plots use the smaller, empirically stronger setting for each reported group:B=8B=8for GSM8K, PIQA, and AlpacaEval,B=2B=2for MMLU\-small, andB=8B=8for MMLU\-large\. The full MMLU results use the size\-adaptive configurationB=2/4/8B=2/4/8for small, medium, and large subjects, respectively\.

#### Choice of recommendation rule\.

We compare the unpenalized posterior\-mean recommendation

k^tmean=arg⁡maxk⁡Mk,t\\widehat\{k\}^\{\\mathrm\{mean\}\}\_\{t\}=\\arg\\max\_\{k\}M\_\{k,t\}with the LCB\-style recommendation used by GittinsEval\-G,

k^tLCB=arg⁡maxk​\{Mk,t−Vk,t\}\.\\widehat\{k\}^\{\\mathrm\{LCB\}\}\_\{t\}=\\arg\\max\_\{k\}\\left\\\{M\_\{k,t\}\-\\sqrt\{V\_\{k,t\}\}\\right\\\}\.Here,Mk,tM\_\{k,t\}andVk,tV\_\{k,t\}are respectively the posterior mean and variance of armkk’s complete, fixed evaluation\-row mean\. The two recommendation rules are evaluated on the same finite\-population Gittins allocation trajectory; therefore, they share the same inherited Gittins stopping time\.

Figure[12](https://arxiv.org/html/2609.25645#A5.F12)shows the two cost\-aware settings with the largest observed differences\. At2%2\\%of the exhaustive\-evaluation cost, the LCB recommendation reduces mean simple regret on GSM8K from0\.0780±0\.01210\.0780\\pm 0\.0121to0\.0080±0\.00130\.0080\\pm 0\.0013, an89\.7%89\.7\\%reduction\. On MMLU Hard\-Large, it reduces aggregate raw simple regret from0\.0828±0\.01430\.0828\\pm 0\.0143to0\.0018±0\.00040\.0018\\pm 0\.0004, a97\.9%97\.9\\%reduction\. Since the recommendation rule changes neither the allocation trajectory nor the inherited Gittins stopping rule, the stopping times are shared by the two curves\. Thus, the improvement comes from stabilizing the anytime recommendation rather than changing either what GittinsEval evaluates or when it stops\.

The aggregate comparison does not imply uniform behavior across individual MMLU subjects: several subjects still exhibit noticeable differences between the posterior\-mean and LCB\-style recommendations, consistent with the single\-seed recommendation diagnostic above\.

![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/ablation/choice_of_recommendation_rule_gittinseval_g.png)Figure 12:Recommendation\-rule ablation for GittinsEval\-G under cost\-aware evaluation\. The left panel compares the LCB\-style and posterior\-mean recommendations on GSM8K \(100 randomized runs\); the right panel compares them on MMLU Hard\-Large \(40 subject–run pairs, comprising 20 runs for each of two subjects\)\. Both rules use the same allocation trajectories and stopping times\. Curves show mean simple regret \(left\) and aggregate raw simple regret \(right\); bands denote±1\\pm 1standard error and dashed lines mark the shared mean stopping time\.

### E\.2Per\-Subject MMLU Results

We provide additional MMLU results under informative priors in Figures[13](https://arxiv.org/html/2609.25645#A5.F13)–[18](https://arxiv.org/html/2609.25645#A5.F18)\. The subjects are grouped into easy, medium, and hard groups according to their empirical mean arm quality\. The corresponding prior means areμ0=0\.75\\mu\_\{0\}=0\.75,μ0=0\.6\\mu\_\{0\}=0\.6, andμ0=0\.4\\mu\_\{0\}=0\.4, respectively\. For each bucket, we report both unit\-cost and cost\-aware results, with the horizontal axis showing cumulative evaluation cost as a percentage of the exhaustive\-evaluation cost\. Across the MMLU subjects, the Gittins\-based policies generally improve over UCB\-E, but the stronger variant depends on the difficulty bucket\. Across the MMLU subjects, GittinsEval\-S generally reaches lower simple regret earlier than UCB\-E and GittinsEval\-G across difficulty buckets\. This suggests that the data\-specific prior is broadly helpful for MMLU, especially when subjects are more challenging\.

![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/mmlu_prior/mmlu_easy_unit.png)Figure 13:Per\-subject MMLU unit\-cost results for easy subjects \(high\-prior bucket\)\. Simple regret is plotted against cumulative evaluation cost as a percentage of exhaustive evaluation\. Labels S, M, and L denote matrix size and useB=2,4,8B=2,4,8, respectively; LRF usesB=32B=32\. Bands denote±1\\pm 1standard error, and dashed lines with faint bands mark mean stopping times with±1\\pm 1standard error\.![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/mmlu_prior/mmlu_easy_aware.png)Figure 14:Per\-subject MMLU cost\-aware results for easy subjects \(high\-prior bucket\)\. Simple regret is plotted against cumulative evaluation cost as a percentage of exhaustive evaluation\. Labels S, M, and L denote matrix size and useB=2,4,8B=2,4,8, respectively; LRF usesB=32B=32\. Bands denote±1\\pm 1standard error, and dashed lines with faint bands mark mean stopping times with±1\\pm 1standard error\.![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/mmlu_prior/mmlu_medium_unit.png)Figure 15:Per\-subject MMLU unit\-cost results for medium\-difficulty subjects \(medium\-prior bucket\)\. Simple regret is plotted against cumulative evaluation cost as a percentage of exhaustive evaluation\. Labels S, M, and L denote matrix size and useB=2,4,8B=2,4,8, respectively; LRF usesB=32B=32\. Bands denote±1\\pm 1standard error, and dashed lines with faint bands mark mean stopping times with±1\\pm 1standard error\.![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/mmlu_prior/mmlu_medium_aware.png)Figure 16:Per\-subject MMLU cost\-aware results for medium\-difficulty subjects \(medium\-prior bucket\)\. Simple regret is plotted against cumulative evaluation cost as a percentage of exhaustive evaluation\. Labels S, M, and L denote matrix size and useB=2,4,8B=2,4,8, respectively; LRF usesB=32B=32\. Bands denote±1\\pm 1standard error, and dashed lines with faint bands mark mean stopping times with±1\\pm 1standard error\.![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/mmlu_prior/mmlu_hard_unit.png)Figure 17:Per\-subject MMLU unit\-cost results for hard subjects \(low\-prior bucket\)\. Simple regret is plotted against cumulative evaluation cost as a percentage of exhaustive evaluation\. Labels S, M, and L denote matrix size and useB=2,4,8B=2,4,8, respectively; LRF usesB=32B=32\. Bands denote±1\\pm 1standard error, and dashed lines with faint bands mark mean stopping times with±1\\pm 1standard error\.![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/mmlu_prior/mmlu_hard_aware.png)Figure 18:Per\-subject MMLU cost\-aware results for hard subjects \(low\-prior bucket\)\. Simple regret is plotted against cumulative evaluation cost as a percentage of exhaustive evaluation\. Labels S, M, and L denote matrix size and useB=2,4,8B=2,4,8, respectively; LRF usesB=32B=32\. Bands denote±1\\pm 1standard error, and dashed lines with faint bands mark mean stopping times with±1\\pm 1standard error\.
### E\.3Computational Overhead Comparison

#### Timing protocol\.

Wall\-clock timing measurements report the total runtime of each allocation policy over a completed simulated evaluation run\. Since the response matrices are precomputed, each evaluation is implemented as an array lookup rather than an LLM inference call\. Therefore, the reported runtime reflects the computational overhead of the allocation procedure itself, including method\-specific setup and the repeated online computation required during the run\. This includes confidence\-bound computation for UCB\-E, low\-rank\-factorization updates for LRF, similarity\-based updates for SySRs, Gittins\-index computation for the Gittins variants, and Gaussian\-process fitting and acquisition computation for the Bayesian optimization baselines, as well as the PromptEval\-BAI allocation procedure\. These measurements should be interpreted as simulation\-time algorithmic overhead rather than model\-serving or benchmark\-construction cost\.

![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/computational_overhead/wall_time_unit.png)Figure 19:Total wall\-clock runtime under unit costs for GSM8K, PIQA, AlpacaEval, and the three MMLU size groups\. Bars show the mean total wall\-clock runtime across completed runs, with black error bars indicating±1\\pm 1standard error across runs\. Diamond and circle markers indicate the mean estimated stopping time for GittinsEval and BO methods, respectively\. UCB\-E and Gittins useB=8B=8on GSM8K/PIQA/AlpacaEval andB=2,4,8B=2,4,8on MMLU\-small/medium/large; LRF usesB=32B=32, and the Bayesian\-optimization baselines are PBGI and LogEI\. Gittins is generally close to UCB\-E, whereas LRF is much slower on larger MMLU tasks; the broken vertical axis accommodates this gap\. PromptEval\-BAI is not reported on AlpacaEval\.![Refer to caption](https://arxiv.org/html/2609.25645v1/figures/computational_overhead/wall_time_aware.png)Figure 20:Total wall\-clock runtime under cost\-aware evaluation for GSM8K, PIQA, AlpacaEval, and the three MMLU size groups\. Bars show the mean total wall\-clock runtime across completed runs, with black error bars indicating±1\\pm 1standard error across runs\. Diamond and circle markers indicate the mean estimated stopping time for GittinsEval and BO methods, respectively\. UCB\-E and Gittins useB=8B=8on GSM8K/PIQA/AlpacaEval andB=2,4,8B=2,4,8on MMLU\-small/medium/large; LRF usesB=32B=32, and the Bayesian\-optimization baselines are PBGI and LogEIPC\. Gittins is generally close to UCB\-E, whereas LRF is much slower on larger MMLU tasks; the broken vertical axis accommodates this gap\. PromptEval\-BAI is not reported on AlpacaEval\.