betaFeedback

Reading v1View latest version

WorksComputer Science

Which Model for Which Role? Cost-Efficient Pareto Recommendation for LLM Agentic Workflows

Abstract

LLM agentic workflows increasingly employ different models for specialized roles. Users may prefer different trade-offs between task quality and deployment cost, sometimes also considering latency. Finding good assignments incurs a separate search cost from evaluating multiple candidates. We introduce Cost-Coupled Gittins (CC-Gittins), a multi-objective extension of single-objective cost-aware Gittins search for Pareto recommendation. It exploits the coupling between evaluation and deployment costs: assignments that cost more to deploy also cost more to evaluate. The search alternates between seeking higher quality and lower deployment cost, reusing each evaluation to inform both searches. After each batch, CC-Gittins recommends assignments that are nondominated under uncertainty-adjusted estimates of quality and deployment cost. We evaluate CC-Gittins on eight quality–cost matrices from workflows with two to five roles and up to 1,681 candidate assignments. We also evaluate the method with latency as a third objective. Across the eight benchmarks, CC-Gittins recovers a substantial fraction of the true Pareto frontier at roughly 10% of the exhaustive-evaluation cost, and recovers most of the frontier with few false positives by 30%.

Code: github.com/AgentOptimizer/agentopt-research

Introduction

Large language model (LLM) agents increasingly combine multiple interacting roles, such as planning, solving, searching, and verification [6, 9, 8]. These roles need not use the same underlying model, and using the most capable models in every role can incur substantial deployment cost. This creates a model assignment problem—given a set of candidate models for each role, which assignments best balance end-to-end task quality, deployment cost, and, when response time matters, latency? Since one role’s output can affect the inputs and behavior of subsequent roles, an assignment’s quality generally cannot be inferred by evaluating each model in isolation. The whole workflow must be treated as the unit of evaluation.

Users may want to compare the task quality of inexpensive and more costly assignments before choosing what to deploy. A representative range of quality–cost trade-offs can support this decision without requiring every Pareto-optimal assignment to be identified.

Existing methods either report quality–cost frontiers over evaluated agent assignments (TeamBench, AgentCARD, and AgentOpt) [9, 8, 6], or optimize a specified objective or constraint. In particular, AgentOpt reduces multi-objective search to single-objective optimization using a fixed weighted-sum utility [6], SCOPE minimizes deployment cost subject to a quality threshold [7], and VineLM adapts model choices at individual invocations under cost or latency budgets [16]. We study anytime recommendation of complete role assignments through costly evaluations, without fixing the preferred trade-off or final search cost in advance.

Exhaustive evaluation is costly: the number of assignments grows multiplicatively across roles, and each candidate must be run on multiple queries to estimate quality and deployment cost. Figure 1 illustrates quality–cost trade-offs recovered at a fraction of exhaustive evaluation cost.

BIRD Dev monetary savings and Pareto frontier

Figure 1. At 90% lower evaluation cost than exhaustive evaluation, CC-GITTINS (ours) recovers most of the BIRD Dev Pareto frontier with no false positives (88.75% mean recall and 100% mean precision over 20 seeds).

A key observation is that deployment cost and evaluation cost are naturally coupled. Let DiD_i denote the mean deployment cost per query for assignment ii. Evaluating a batch of BB comparable queries costs approximately κi≈BDi\kappa_i \approx BD_i. The total search cost accumulates these charges across evaluated assignments, including those never deployed. Consequently, configurations that are expensive to deploy are also expensive to learn about.

We introduce Cost-Coupled Gittins (CC-GITTINS), a multi-objective method for anytime Pareto recommendation that exploits this coupling. For quality and cost, two search policies, called controllers, take turns choosing evaluations: one seeks higher quality and the other lower deployment cost. The quality controller prices further evaluation using configuration-specific API costs. In the simplified model of § 3.4, its Gittins indices rank assignments by quality minus a deployment-cost penalty, so relaxing the evaluation-price multiplier can favor different quality–cost trade-offs. The controllers share observations. After each batch, assignments nondominated under uncertainty-adjusted quality and deployment-cost estimates form the recommendation. Figure 2 gives an overview.

Overview of CC-GITTINS in the quality–cost setting

Figure 2. Overview of CC-GITTINS in the quality–cost setting. Workflow evaluations provide quality and deployment-cost observations. Quality and cost controllers share observations, take turns choosing evaluations, and independently relax their evaluation prices. After each batch, Pareto dominance is checked using quality lower confidence bound (LCB) and cost upper confidence bound (UCB) scores. Nondominated assignments form the Pareto recommendations (green). When latency is included, additional controllers share observations and recommendations use three-objective Pareto dominance.

We evaluate CC-GITTINS through offline replay on eight quality–cost workflow benchmarks, including complete HotpotQA and MathQA assignment matrices and six SCOPE-derived instances. These benchmarks span two to five roles and up to 1,681 candidate assignments. Compared with five search baselines, CC-GITTINS achieves competitive hypervolume regret and general distance at low search cost, although frontier coverage varies across benchmarks. We further conduct controlled ablations and evaluate the method with end-to-end latency as a third objective on HotpotQA and MathQA.

Contributions. Our main contributions are as follows:

  • We formulate model assignment in multi-role LLM workflows as anytime recommendation of a useful range of Pareto trade-offs through costly end-to-end evaluations.

  • We develop CC-GITTINS, a multi-objective extension of single-objective cost-aware Gittins search for anytime Pareto recommendation. Each batch updates the recommendation, so users can stop without fixing a final search budget or preferred trade-off.

  • We implement a workflow evaluation harness in AgentOpt and collect complete response matrices that jointly record task scores (accuracy or F1), input and output token counts, token-derived API costs, and end-to-end latency for each workflow execution. These records support reproducible replay against exhaustive Pareto frontiers.

  • Across eight quality–cost workflow benchmarks, CC-GITTINS recovers a substantial fraction of the true Pareto frontier at roughly 10% of exhaustive evaluation cost, and most of

the frontier with few false positives by 30%. We also evaluate the method with latency as a third objective.

Related Work

Resource-aware LLM systems. Server-side systems improve scheduling, memory use, and serving throughput [12, 21, 13]. Client-side routing selects a model per request or call [2, 5, 15]. Agent configuration search instead assigns models to interacting roles and observes an end-to-end trajectory reward. TeamBench exhaustively studies the assignments of several providers to Planner, Executor, and Verifier [9], while AgentCARD maps deployment-aware cost–accuracy frontiers over multi-role assignments [8]. These systems characterize configuration landscapes after evaluation.

Efficient LLM evaluation. BanditEval exploits low-rank response-matrix structure [22], SySRs uses paired comparisons to identify the best model [14], and PromptEval shares information across prompts and examples to estimate multi-prompt performance [17]. Gittins indices have also been adapted to account for evaluation costs in LLM model selection [18]. These methods focus on scalar performance estimation or single-objective model selection; CC-GITTINS extends cost-aware Gittins search to multi-objective Pareto recommendation for complete agent workflows.

Multi-objective LLM configuration optimization. SCOPE and VineLM consider multiple objectives through constrained optimization: SCOPE minimizes deployment cost subject to a quality threshold [7], while VineLM maximizes accuracy under cost or latency budgets [16]. Concurrent work by Xue et al. [19] uses a frequentist approach: empirical gap elimination for Pareto identification and hypervolume-per-cost UCB for online LLM configuration selection. Its experiments vary models, prompts, and decoding settings for accuracy–latency trade-offs under token-based evaluation budgets. We take a Bayesian approach to joint model assignment across interacting agent roles, using Gittins indices to guide cost-aware search while maintaining anytime quality–deployment-cost recommendations. Our method exploits the coupling between search and deployment costs.

Pareto-set search. General-purpose multi-objective bandits study Pareto-set identification under fixed-confidence or fixed-budget objectives [10, 11]. Hypervolume-based Bayesian optimization, including qEHVI and qNEHVI, selects evaluations by expected hypervolume improvement (Daulton et al., 2020; 2021). These methods can be sample-efficient, but their standard acquisition criterion does not explicitly price the assignment-dependent API cost of each evaluation. CC-GITTINS includes that price in its scalar indices and updates its recommendation after each batch; we assess those recommendations at matched cumulative API spend.

Pareto Recommendation and Evaluation

Configurations and objectives. For a given workflow, we vary the model assigned to each role while keeping its role structure and orchestration rules fixed. The workflow has roles 1,…,L1,\ldots,L, with candidate model set Mℓ\mathcal{M}_{\ell} for role ℓ\ell. Let C=M1×⋯×ML\mathcal{C}=\mathcal{M}_{1}\times\cdots\times\mathcal{M}_{L} be the set of complete model assignments and K=∣C∣K=|\mathcal{C}| its size. We number these configurations 1,…,K1,\ldots,K; throughout, ii identifies one complete assignment. Configuration ii has task quality QiQ_i, to maximize, and mean deployment cost per query DiD_i, to minimize; § 3.6 adds latency. Since role outputs affect subsequent execution, the full assignment is the unit of evaluation. The Pareto-optimal reference set is

P⋆={i:∄j with Qj≥Qi, Dj≤Di and at least one strict inequality}.(1)\mathcal{P}^{\star}=\{i:\nexists j\text{ with }Q_j\ge Q_i,\ D_j\le D_i\text{ and at least one strict inequality}\}. \tag*{(1)}

Our goal is an anytime recommendation set offering useful coverage of quality–cost trade-offs. We assess its proximity to this reference frontier and its coverage of trade-off volume and frontier regions. For offline replay, Qi,DiQ_i,D_i are the exhaustive means on the fixed NN-question benchmark. These averages describe the fixed benchmark; they do not guarantee performance on new queries or under a different query distribution.

Objective scaling and search cost. To compute the evaluation metrics, we map each objective to a fixed scale where larger values are better. The resulting objective vectors lie in [0,1]d[0,1]^d, with the origin as the hypervolume reference. In the quality–cost case, positive affine maps of (Qi,−Di)(Q_i,-D_i) give yi=(qi,ci)∈[0,1]2y_i=(q_i,c_i)\in[0,1]^2. Write P⋆={yi:i∈P⋆}\mathcal{P}^{\star}=\{y_i:i\in P^{\star}\}. Let P^t\widehat{P}_t be the recommended configurations and At={yi:i∈P^t}A_t=\{y_i:i\in\widehat{P}_t\} their true objective vectors. These vectors are available to the offline evaluator, not the selector. Total search cost St=∑s≤tκsS_t=\sum_{s\le t}\kappa_s sums the batch charges κs\kappa_s across all evaluated configurations. For exhaustive search cost SfullS_{\mathrm{full}}, the recommendation snapshot at cumulative cost fraction bb is

P^(b)=P^t(b),t(b)=max⁡{t:St≤bSfull}.(2)\widehat{P}(b)=\widehat{P}_{t(b)},\qquad t(b)=\max\{t:S_t\le bS_{\mathrm{full}}\}. \tag*{(2)}

These cost fractions select retrospective reporting checkpoints and are not required inputs to CC-GITTINS. A snapshot is reported only if a recommendation is available at or below the corresponding cost threshold, including warm-start cost.

Evaluation metrics. For an offline evaluator, let AA be the nonempty set of recommended assignments at their true normalized coordinates, and let d(x,S)d(x,S) be the Euclidean distance from xx to the nearest point in SS. Hypervolume (HV) regret measures the volume dominated by the true frontier but not by the recommendation. Generational distance (GD) averages how far reported assignments lie from the true frontier. Inverted generational distance (IGD) averages how far true frontier points lie from the recommendation. We use

RHV(A)=HV(P⋆)−HV(A),(3)R_{\mathrm{HV}}(A)=\mathrm{HV}(P^{\star})-\mathrm{HV}(A), \tag*{(3)}
GD(A,P⋆)=∣A∣−1∑a∈Ad(a,P⋆),(4)\mathrm{GD}(A,P^{\star})=|A|^{-1}\sum_{a\in A}d(a,P^{\star}), \tag*{(4)}
IGD(A,P⋆)=∣P⋆∣−1∑p⋆∈P⋆d(p⋆,A).(5)\mathrm{IGD}(A,P^{\star})=|P^{\star}|^{-1}\sum_{p^{\star}\in P^{\star}}d(p^{\star},A). \tag*{(5)}

These average or volume measures assess recommendations at a given search spend; they do not require exact frontier recovery or limit the number of returned assignments. They are not worst-case guarantees for individual assignments or frontier regions. All three metrics evaluate the returned recommendation at its true normalized coordinates, and GD and IGD use the complete set AA.

Cost-Coupled Gittins

Our goal is to progressively identify model assignments with different quality–cost trade-offs while minimizing evaluation costs. To achieve this, CC-GITTINS uses two controllers, one focusing quality and the other on deployment cost. The controllers take turns selecting assignments for evaluation and share their observations. After each evaluation batch, we update the recommended assignments based on Pareto dominance. We next explain how the controllers select evaluations and how the recommendations are constructed.

How evaluation prices guide deployment trade-offs

Deployment cost affects both the quality–cost trade-off and the cost of evaluating an assignment. For comparable benchmark and deployment queries, evaluating a batch of BB queries for configuration ii costs approximately κi≈BDi\kappa_i \approx BD_i. We use a positive estimate κ^i\widehat{\kappa}_i, fixed after warm-up, to select evaluations, while actual API charges contribute to the cumulative search cost StS_t. These costs may differ due to variations in query difficulty, output length, and batch size.

CC-Gittins incorporates these evaluation costs into its Gittins indices. As a result, the quality controller considers both potential quality improvements and the cost of obtaining further observations. Since expensive assignments also cost more to evaluate, this can favor different quality–cost trade-offs. We characterize this effect in § 3.4.

The quality controller uses task quality QiQ_i, while the cost controller uses a transformed deployment cost Ci=1−Di/RC_i = 1 - D_i/R, where R>0R > 0 is fixed after warm-up. We write

Yi=(Qi,Ci),vQ=(1,0),vC=(0,1).(6)Y_i = (Q_i, C_i), \quad v_Q = (1, 0), \quad v_C = (0, 1). \tag*{(6)}

These coordinates are used for selecting evaluations and differ from the normalized coordinates used for offline evaluation in § 2.

Shared Posterior and Gittins Indices

Each evaluation batch provides observations of quality and per-query deployment cost for the selected configuration. Both controllers share these observations and update the same posterior for each configuration. For the unknown mean θi,j\theta_{i,j} of objective j∈{Q,D}j \in\{Q, D\}, we use independent Gaussian posterior marginals

θi,j∣Di,n∼N(mi,j,n,vi,j,n),\theta_{i,j} \mid\mathcal{D}_{i,n} \sim\mathcal{N}(m_{i,j,n}, v_{i,j,n}),

where mi,j,nm_{i,j,n} and vi,j,nv_{i,j,n} denote the posterior mean and variance after nn observed queries. The quality controller uses

mi,nQ=mi,Q,n,vi,nQ=vi,Q,n,m^Q_{i,n} = m_{i,Q,n}, \qquad v^Q_{i,n} = v_{i,Q,n},

while the cost controller uses

mi,nC=1−mi,D,n/R,vi,nC=vi,D,n/R2.m^C_{i,n} = 1 - m_{i,D,n}/R, \qquad v^C_{i,n} = v_{i,D,n}/R^2.

The coupling between evaluation and deployment costs enters through evaluation prices, rather than posterior correlations. Appendix § 10 gives the posterior calibration.

To select evaluations, each controller uses the cost-aware Gittins index of Xie et al. [18]. For controller a∈{Q,C}a \in\{Q, C\}, let kk index the evaluation batches of configuration ii, and let ni(k)n_i(k) be its number of observed queries at stage kk. We use the shorthand mi,ka=mi,ni(k)am^a_{i,k} = m^a_{i,n_i(k)} and vi,ka=vi,ni(k)av^a_{i,k} = v^a_{i,n_i(k)}. Let HiH_i denote the completion stage.

Given an outside option α\alpha, define the centered posterior mean x=mi,ka−αx = m^a_{i,k} - \alpha. For a positive per-batch evaluation price γ\gamma and a mean-zero Gaussian increment Zi,kaZ^a_{i,k}, the recursion is

Vi,Hia,γ(x)=max⁡{0,x}(7)V^{a,\gamma}_{i,H_i}(x) = \max\{0, x\} \tag*{(7)}
Wi,ka,γ(x)=−γ+E[Vi,k+1a,γ(x+Zi,ka)],Vi,ka,γ(x)=max⁡{0,Wi,ka,γ(x)}.(8)W^{a,\gamma}_{i,k}(x) = -\gamma+ \mathbb{E}\left[V^{a,\gamma}_{i,k+1}(x + Z^a_{i,k})\right], \qquad V^{a,\gamma}_{i,k}(x) = \max\{0, W^{a,\gamma}_{i,k}(x)\}. \tag*{(8)}

The increment variance is the reduction in posterior variance between consecutive stages. Evaluation may stop at intermediate stages, while terminal utility is obtained only upon completion.

Let ri,ka(γ)r^a_{i,k}(\gamma) be the zero of Wi,ka,γW^{a,\gamma}_{i,k}. The two controllers use

Gi,kQ=mi,kQ−ri,kQ(ηQκ^i),Gi,kC=mi,kC−ri,kC(ηCκ^i).(9)G^Q_{i,k} = m^Q_{i,k} - r^Q_{i,k}(\eta_Q\widehat{\kappa}_i), \qquad G^C_{i,k} = m^C_{i,k} - r^C_{i,k}(\eta_C\widehat{\kappa}_i). \tag*{(9)}

The positive multipliers ηQ\eta_Q and ηC\eta_C, initially one, control the evaluation-price penalties and are adjusted independently as described next. Both indices use one-dimensional dynamic programs. Appendix § 10 gives their computation and numerical details. The two-axis design also has computational advantages. At matched evaluation counts, its mean policy runtime is lower than that of the tested three- and five-controller variants on all eight benchmarks (Figure 15, Appendix § 18).

Direction Runtime Comparison across HotpotQA, Restaurant Valid, BIRD Mini Dev, Bing Query Logs, MathQA, Restaurant Test, BIRD Dev, and Stack Overflow

Figure 15. Direction-ablation policy runtime for a fixed workload of 30% of matrix entries (lower is better). The five settings are Q-only G1, deployment-only G4, exact axes G0, axes plus midpoint G5, and five evenly spaced directions G6. For every dataset and matched seed, all five evaluate exactly ⌈0.30KN⌉\lceil0.30KN \rceil entries (KK configurations and NN questions), with a shortened final batch when needed; runs that reach their native stopping condition earlier continue to this common cap. They run sequentially on the same compute node, with execution order rotated across seeds. G0 has lower mean policy runtime than both denser direction sets on all eight benchmarks; G5 and G6 require 1.39× and 1.74× G0’s policy time on average across benchmark ratios. Bars and error bars show means and ±2 standard errors over 20 matched seeds. The timer isolates policy computation, including construction of required DP tables with reuse only within each run, and excludes data loading, result serialization, validation, and Slurm queue time.

Controller Scheduling and Asynchronous cost relaxation

The cost (CC) and quality (QQ) controllers alternate turns in the order C,QC, Q. Each controller a∈{C,Q}a \in\{C,Q\} uses a multiplier ηa\eta_a, initially one, to scale the estimated evaluation cost κ^i\hat{\kappa}_i in its Gittins index (Eq. (9)). On its turn, the controller compares the largest index among unfinished configurations with its best completed terminal value IaI_a (set Ia=−∞I_a=-\infty if none is complete). If an unfinished configuration is preferred, the controller evaluates one batch and updates the shared posteriors.

Otherwise, the controller would stop at its current evaluation price. Instead, we halve only its multiplier ηa\eta_a when possible, reducing the penalty for future evaluations. The other controller’s multiplier and actual API charges remain unchanged. The search terminates when both controllers reach stopping conditions that cannot be relaxed without an intervening evaluation, an external budget is reached, or all configurations are complete. The round-robin schedule balances controller turns rather than evaluation counts or API cost. Appendix § 10 provides the numerical stopping rules.

Why cost coupling exposes quality–cost trade-offs

At a fixed uncertainty schedule and remaining horizon, raising the information price lowers the scalar index (Appendix § 9). Coupling makes that price depend on a deployment objective. To isolate its role, consider a deterministic completion model: outcomes are known, but terminal utility still requires paying for the remaining evaluation batches.

Proposition 1 (Deterministic roles of the two exact axes). Suppose uncertainty has vanished, each unfinished configuration requires the same hh remaining full batches of size BB to collect terminal utility, and each batch costs exactly κi=BDi\kappa_i = BD_i. Among unfinished configurations,

GiQ(ηQ)=Qi−λQDi,λQ=ηQhB,GiC(ηC)=1−λCDi,λC=R−1+ηChB>0.(10)\begin{aligned} G_i^Q(\eta_Q) &= Q_i-\lambda_QD_i, & \lambda_Q &= \eta_QhB,\\ G_i^C(\eta_C) &= 1-\lambda_CD_i, & \lambda_C &= R^{-1}+\eta_ChB>0. \tag*{(10)} \end{aligned}

Thus the quality axis ranks a quality–cost scalarization, while the cost axis ranks configurations by increasing deployment cost.

Coupled prices favor a more expensive assignment when ΔQ>λQΔD\Delta Q>\lambda_Q\Delta D; lowering ηQ\eta_Q relaxes this requirement at fixed hh. This can expose supported trade-offs, meaning frontier points maximizing Qi−λDiQ_i-\lambda D_i for some λ≥0\lambda\geq0, while the cost axis targets the inexpensive endpoint. Equal evaluation prices would preserve the quality ranking. Bayesian uncertainty, unequal remaining horizons, and estimated prices break this exact scalarization interpretation. Discrete price relaxation need not visit every supported point, while unsupported points lie outside this linear argument. Thus the policy has no complete-frontier recovery guarantee.

Anytime conservative Pareto recommendation

Acquisition prices choose which evidence to buy; recommendations are formed from all configurations, rather than only controller winners. For the fixed NN-question benchmark, let Si,j,nS_{i,j,n} be the sum of nn observed outcomes and σj2\sigma_j^2 the frozen per-question residual variance. The predicted mean and variance of the final benchmark mean are

Mi,j,n=Si,j,n+(N−n)mi,j,nN,Ui,j,n=(N−n)2vi,j,n+(N−n)σj2N2.(11)M_{i,j,n}=\frac{S_{i,j,n}+(N-n)m_{i,j,n}}{N},\qquad U_{i,j,n}=\frac{(N-n)^2v_{i,j,n}+(N-n)\sigma_j^2}{N^2}. \tag*{(11)}

At completion, this mean is the observed benchmark mean and its variance is zero. After only a few evaluations, however, an assignment may appear to offer high quality or low cost while its full-benchmark means remain uncertain. Following the scalar uncertainty-penalized recommendation design of Xie et al. [18], we form quality-LCB and cost-UCB scores for reporting:

Qi,n−=Mi,Q,n−βUi,Q,n,Di,n+=Mi,D,n+βUi,D,n,β=1.(12)Q_{i,n}^{-}=M_{i,Q,n}-\beta\sqrt{U_{i,Q,n}},\qquad D_{i,n}^{+}=M_{i,D,n}+\beta\sqrt{U_{i,D,n}},\qquad\beta=1. \tag*{(12)}

For a Pareto recommendation, these paired scores define one point per assignment. Using each configuration’s current observation count nin_i, configuration jj dominates ii in this score space if Qj,nj−≥Qi,ni−Q_{j,n_j}^{-}\geq Q_{i,n_i}^{-} and Dj,nj+≤Di,ni+D_{j,n_j}^{+}\leq D_{i,n_i}^{+}, with at least one strict inequality. Return all configurations that are nondominated under this relation. Partially evaluated configurations remain eligible, and there is no restriction to one recommendation per controller. At exhaustive completion, the recommended set equals the true benchmark frontier. The current set is available after warm-up and after each subsequent batch, allowing users to stop without specifying a final evaluation budget.

This adjustment aims to reduce unstable off-front recommendations but is not a simultaneous or time-uniform confidence certificate. It does not guarantee that every reported assignment lies near the true frontier. The single-objective Gittins results do not establish Bayes optimality for the full multi-objective search method.

Additional deployment objectives

The same mechanism lets an evaluation-price penalty introduce deployment cost into controllers whose terminal utilities concern other deployment objectives. With dd objectives, let zi∈Rd−1z_i \in\mathbb{R}^{d-1} collect non-cost desirabilities. For a linear utility Uv(i)=v⊤ziU_v(i) = v^\top z_i, v∈Δd−2v \in\Delta^{d-2}, Proposition 1’s deterministic assumptions give the ranking v⊤zi−λDiv^\top z_i - \lambda D_i; the explicit non-cost direction family has d−2d - 2 dimensions. This dimensional count motivates, but does not guarantee the coverage of, a finite controller set.

For quality QiQ_i, mean deployment cost DiD_i, and mean latency LiL_i, let ℓi=1−Li/T\ell_i = 1 - L_i/T, where T>0T > 0 is a latency scale fixed after warm-up. Alongside the pure quality, latency, and cost controllers, our three-objective experiment adds a balanced quality–latency controller with terminal utility

Ubal(i)=min⁡{Qi,ℓi},Gi,baldet=Ubal(i)−λDi.(13)U_{\mathrm{bal}}(i) = \min\{Q_i, \ell_i\}, \qquad G^{\mathrm{det}}_{i,\mathrm{bal}} = U_{\mathrm{bal}}(i) - \lambda D_i. \tag*{(13)}

This radial-min choice favors assignments that perform well on both non-cost objectives; it is not the linear midpoint 12(Qi+ℓi)\frac{1}{2}(Q_i + \ell_i) and does not inherit the linear supported-front interpretation. All four controllers share observations and independently relax their API evaluation-cost penalties. Algorithm 1 gives the common replay procedure; Appendix C specifies the three-objective indices, recommendation rule, and metrics.

Experiments

Experimental setup

Benchmarks. Our quality–cost evaluation uses eight exhaustive or replay-complete matrices across five workflow families. We evaluate 102=10010^2 = 100 assignments on all 200 questions of each of HotpotQA [20] (planner and search-enabled solver) and MathQA [1] (answerer and critic). Their ten candidate models use AWS Bedrock Application Inference Profiles; Appendix D.2 lists invocation prices. Six further instances use SCOPE’s released query-level evaluations [7], covering three-to-five-role text-to-SQL, data-transformation, and data-integration workflows. These configurations form subsets of the nominal assignment spaces, each evaluated on every benchmark question. All methods replay the same complete score–cost matrices (Appendix D.1).

Evaluation protocol and metrics. The offline replay reveals only purchased observations. CC-Gittins uses four warm questions per configuration, batches of up to four unseen questions, and two exact-axis controllers with independent price relaxation. Both quality and deployment-cost prior variances are estimated from warm-start observations. Comparisons use 20 matched question-order seeds (42–61) and charge observed API costs, including warm-up. Every 0.5 percentage points of exhaustive cost, curves aggregate each contributing seed’s latest recommendation at or below that checkpoint (Eq. (2)). Metric scales are fixed across methods and seeds. We report HV regret, GD, and IGD (§ 2), dividing HV regret by HV(P∗P^*) for the quality–cost plots; lower is better.

Baselines. We compare CC-GITTINS with EGE-SH for fixed-budget Pareto-set identification [11], the adaptive Pareto-exploration sampling rule of APE-kk [10], and qNEHVI, a Bayesian optimization method that selects evaluations by noisy expected hypervolume improvement (Daulton et al., 2021). We also compare CC-GITTINS with two random search baselines: random questions, which evaluates all assignments on the same randomly drawn benchmark questions, and random configurations, which fully evaluates randomly drawn assignments. Appendix D.4 gives their replay protocols.

Quality–cost results

Main findings. At matched search costs up to 30% of exhaustive evaluation, CC-GITTINS is generally competitive with the five baselines in HV regret and GD across eight benchmarks (Figure 3–Figure 4). Partial evaluation can thus return assignments close to the exhaustive quality–cost frontier.

Hypervolume regret on eight benchmarks over 0–30% of exhaustive evaluation cost

Figure 3. Hypervolume (HV) regret on eight benchmarks over 0–30% of exhaustive evaluation cost (lower is better). CC-GITTINS is generally competitive with the baselines across benchmarks and the displayed cost range. All methods use 20 matched seeds; curves report seed means and bands show ±2 standard errors.

Generational distance on eight benchmarks over 0–30% of exhaustive API evaluation cost

Figure 4. Generational distance (GD) on eight benchmarks over 0–30% of exhaustive API evaluation cost (lower is better). CC-GITTINS is generally competitive with the baselines across benchmarks and the displayed cost range. Curves show seed means; bands show ±2 standard errors.

Recommendation example. On Stack Overflow, CC-GITTINS nearly recovers the entire frontier at 10% of exhaustive evaluation cost (mean precision 0.97, recall 0.98); both reach 1.00 at 30% (Figure 6). Two acquisition controllers can return many trade-offs because the shared recommendation rule considers all configurations nondominated under uncertainty-adjusted estimates.

Mean quality versus mean deployment cost for six recommendation methods

Figure 6. CC-GITTINS recovers nearly the entire Stack Overflow frontier at 10% of exhaustive API evaluation cost, with few off-front recommendations (mean precision 0.97, recall 0.98). Panels compare CC-GITTINS with five baselines using exhaustive mean quality and deployment cost to locate configurations. Gray points show the full configuration set; black lines show the full-data Pareto frontier. Colored markers indicate recommendation frequency across 20 matched seeds. The line beneath each method name reports the mean start–end interval over which the checkpoint recommendation remains stable, as a fraction of exhaustive search cost.

Coverage limitations. On HotpotQA, mean recall is 0.58 at 10% cost and 0.74 at 30%, despite precision of 0.97 and 0.99, respectively. High precision therefore coexists with incomplete frontier recovery. Low HV regret and GD likewise do not imply broad frontier coverage: competing methods achieve lower IGD on some benchmarks (Figure 5).

Inverted generational distance on eight benchmarks

Figure 5. Inverted generational distance (IGD) on eight benchmarks over 0–30% of exhaustive API evaluation cost (lower is better). CC-GITTINS achieves competitive frontier coverage, but does not consistently outperform the baselines. Curves show seed means; bands show ±2\pm2 standard errors.

Ablation findings. At the 30% cost checkpoint, combining configuration-specific evaluation prices with quality and cost controllers yields the lowest average HV regret, GD, and IGD across eight benchmarks among the cost-mechanism controls. Relative to fixed-η\eta continuation, independent price relaxation lowers average HV regret, GD, and IGD. Additional controllers improve particular metrics but do not uniformly outperform the two-axis design (Appendix § 18).

Weighted-score coverage. Across all eight benchmark matrices, the supported subset (§ 3.4) loses less than 0.10% of full-frontier hypervolume despite omitting some Pareto points. This full-information oracle considers all weights, showing that weighted scores can represent most dominated area without guaranteeing CC-GITTINS’s performance under limited search cost and discrete price relaxation. Appendix § 13 details the geometry and representative results.

Latency-aware three-objective evaluation

We evaluate the four-controller policy (§ 3.6), with direction-local η\eta decay, on the HotpotQA and MathQA matrices across 20 matched seeds, comparing with the five baselines at matched search costs. Metric computation retains the original quality score and transforms cost and latency so that higher scores are better, using fixed benchmark-specific scales shared across methods and seeds (Appendix § 11). These transformations are used only to evaluate recommendations.

Figure 7 shows low HV regret and GD, but several baselines achieve lower IGD over substantial search-cost ranges. Ablations vary evaluation-cost pricing, controller sets, and cost-penalty relaxation (Appendix § 19). Accounting for configuration-specific evaluation costs during search improves volume recovery and recommendation proximity for multi-controller variants; controller choice and relaxation have effects that vary by benchmark and metric.

Discussion and Conclusions

CC-GITTINS exploits the coupling between deployment and evaluation costs for anytime multi-objective Pareto recommendation. Across eight quality–cost benchmarks, it recovers substantial portions of the exhaustive Pareto frontier at low evaluation cost. Experiments including latency also demonstrate applicability to three-objective Pareto recommendation.

We consider static role-level assignments under fixed orchestration. Complete frontier recovery is not guaranteed, and controller design remains empirical. Future work could adapt model choices, retries, and execution paths to intermediate outcomes.

Reproducibility Statement

Experiments use offline replay of fixed benchmark matrices without new model API calls. Appendices B–D document posterior calibration, index computation and stopping, the three-objective extension, and data sources, pricing, settings, and baselines. Plotting and ablation protocols are in Appendices I–K. Code, benchmark matrices, and replay instructions are available at https://github.com/AgentOptimizer/agentopt-research.

AI Use Statement

The authors used generative AI tools, including LLM-based assistants, to draft and revise parts of the manuscript, improve the clarity of the writing, and assist with LaTeX formatting. The tools also assisted in developing mathematical proofs by working out detailed derivations and proof steps from statements of theoretical results, proof sketches, and arguments provided by the authors. The authors checked cited sources, mathematical arguments, and AI-assisted text, revised them as needed, and take full responsibility for the paper’s contents.

Separately, LLMs are components of the agent configurations evaluated in this work. The quality–cost experiments replay HotpotQA and MathQA response matrices collected with our workflow evaluation harness and six SCOPE-derived instances; the three-objective replay uses the same two matrices with recorded latency. The replay makes no new model API calls. Appendix D.1 documents data sources and processing.

Acknowledgements

This research received funding from DAPLab corporate support in the form of funding and/or compute from Amazon, IntellectAI, Infosys, Tidalwave, Veris, Shopify, Microsoft, Thinking Machines, Dandy, Perplexity, and Daytona. The authors also thank Wenxin Zhang for a helpful discussion and for suggestions on an earlier draft of the manuscript.

Effects of Evaluation Costs on Gittins Indices

Price monotonicity of the scalar recursion. Fix the transition schedule and terminal stage, and take 0<γ1≤γ20 < \gamma_1 \le\gamma_2. At the terminal stage VHγ1=VHγ2=x+V_H^{\gamma_1}=V_H^{\gamma_2}=x_+. If Vk+1γ1≥Vk+1γ2V_{k+1}^{\gamma_1}\ge V_{k+1}^{\gamma_2} pointwise, then

Wkγ1(x)=−γ1+E[Vk+1γ1(x+Zk)]≥−γ2+E[Vk+1γ2(x+Zk)]=Wkγ2(x).(14)W_k^{\gamma_1}(x)=-\gamma_1+\mathbb{E}[V_{k+1}^{\gamma_1}(x+Z_k)]\ge-\gamma_2+\mathbb{E}[V_{k+1}^{\gamma_2}(x+Z_k)]=W_k^{\gamma_2}(x). \tag*{(14)}

Taking the maximum with zero preserves the inequality and proves it by backward induction. Continuation values are nondecreasing in xx; consequently the nonnegative-continuation set for the higher price is contained in that for the lower price, and its threshold satisfies rk(γ1)≤rk(γ2)r_k(\gamma_1)\le r_k(\gamma_2). With identical uncertainty schedules and remaining horizons, miQ≥mjQm_i^Q\ge m_j^Q and κ^i≤κ^j\hat{\kappa}_i\le\hat{\kappa}_j give

GiQ−GjQ=(miQ−mjQ)+rk(ηκ^j)−rk(ηκ^i)≥0.(15)G_i^Q-G_j^Q=(m_i^Q-m_j^Q)+r_k(\eta\hat{\kappa}_j)-r_k(\eta\hat{\kappa}_i)\ge0. \tag*{(15)}

We restrict to positive prices. At exactly zero cost, a nondegenerate Gaussian transition can make continuation strictly positive at every finite xx, so a finite stopping root need not exist. This also motivates the positive-price and underflow safeguards below. □

Proof of Proposition 1. With zero uncertainty, Zk=0Z_k=0. For h=0h=0, the excess terminal value is V0(x)=x+V_0(x)=x_+. If Vh−1(x)=max⁡{0,x−(h−1)γ}V_{h-1}(x)=\max\{0,x-(h-1)\gamma\}, then

Vh(x)=max⁡{0,−γ+max⁡{0,x−(h−1)γ}}=max⁡{0,x−hγ}.(16)V_h(x)=\max\{0,-\gamma+\max\{0,x-(h-1)\gamma\}\}=\max\{0,x-h\gamma\}. \tag*{(16)}

Thus the continuation root is hγh\gamma. With quality terminal utility QiQ_i, the index is GiQ=Qi−hηQκi=Qi−ηQhBDiG_i^Q=Q_i-h\eta_Q\kappa_i=Q_i-\eta_QhBD_i. With cost terminal utility Ci=1−Di/RC_i=1-D_i/R, the same recursion gives GiC=Ci−hηCκi=1−(R−1+ηChB)DiG_i^C=C_i-h\eta_C\kappa_i=1-(R^{-1}+\eta_ChB)D_i. Since R>0R>0 and ηC>0\eta_C>0, the cost-axis coefficient is positive. Required completion is essential: if a known terminal reward could be collected immediately, paying the remaining hh batches would be unnecessary. Unequal remaining horizons instead give configuration-specific penalties ηChiBDi\eta_Ch_iBD_i, not a common scalarization weight. □

Posterior Calibration and Search Implementation

Warm-start batches use independent seeded question orders for each configuration. The prior means are equal-weight averages of configuration warm-batch means. Quality prior variance is the sample variance of configuration warm-batch quality means, floored at 10−1210^{-12}. If Dˉiwarm\bar{D}_i^{\mathrm{warm}} is the warm-batch mean cost and K>1K>1, use

v0,D=max⁡{1K−1∑i=1K(Dˉiwarm−1K∑j=1KDˉjwarm)2,10−12R2}.(17)v_{0,D}=\max\left\{\frac{1}{K-1}\sum_{i=1}^{K}\left(\bar{D}_i^{\mathrm{warm}}-\frac{1}{K}\sum_{j=1}^{K}\bar{D}_j^{\mathrm{warm}}\right)^2,10^{-12}R^2\right\}. \tag*{(17)}

Freeze calibration after warm-up and include each warm observation in the likelihood once. Empirical-Bayes reuse of warm data and the independent Gaussian approximation are modeling choices, not coverage certificates.

Equation (8) is one-dimensional on either exact axis. Only the active objective’s latent-posterior-mean innovation variance enters its scalar dynamic program; the unused objective is still observed and updates the shared posterior. Root tables are cached by variance schedule, horizon, and positive effective cost. The quality and cost axes therefore do not require the expected-minimum formula or a two-dimensional radial dynamic program. The cached tables plan full-batch posterior updates; a shorter final batch uses its actual size for the observation update and API accounting. Proposition 1 assumes equal-sized, equal-price remaining batches. For acquisition, the reported implementation rounds BB times each configuration’s warm-start mean deployment cost to the nearest multiplicative bin with ratio 2 and anchor 10−410^{-4} USD, then applies ηa\eta_a; these frozen prices allow table reuse. The deployment-cost posterior and realized-dollar accounting continue to update.

Controller sets and Pareto recommendation. Algorithm 1 covers both objective settings. For quality–cost (d=2d=2), the controller set is A={C,Q}\mathcal{A}=\{C,Q\}, visited in the order C,QC,Q, with terminal utilities CiC_i and QiQ_i. For quality–cost–latency (d=3d=3), use A={Q,bal,ℓ,C}\mathcal{A}=\{Q,\mathrm{bal},\ell,C\}, visited in the order Q,bal,ℓ,CQ,\mathrm{bal},\ell,C. Here ℓi=1−Li/T\ell_i=1-L_i/T, with T>0T>0 frozen after warm-up, and the balanced terminal utility is min⁡{Qi,ℓi}\min\{Q_i,\ell_i\}. Pure controllers use one-dimensional indices; the balanced controller uses the two-coordinate radial dynamic program described in Appendix § 11. Every controller has its own positive multiplier ηa\eta_a and shares the observed outcomes.

The conservative Pareto recommendation rule returns configurations that are nondominated when maximizing Q−Q^{-} and minimizing D+D^{+} from Eq. (12). For d=3d = 3, it also minimizes Li,n+=Mi,L,n+βUi,L,nL^{+}_{i,n} = M_{i,L,n}+\beta\sqrt{U_{i,L,n}}, with the same β=1\beta= 1. Thus each purchased batch updates two or three posterior marginals, and the recommendation is formed in the corresponding objective space.

Numerical stopping rule. The replay does not impose a fixed lower bound on ηa\eta_a. Let Gmax⁡aG^{a}_{\max} be the best unfinished index; the implementation treats Gmax⁡a≤Ia+τG^{a}_{\max} \le I_a+\tau as a local stopping signal. At such a stop, let ρa=max⁡i unfinishedhiγi,a\rho_a = \max_{i\ \mathrm{unfinished}} h_i\gamma_{i,a} be the largest remaining effective completion penalty, where hih_i is the number of planned batches remaining and γi,a\gamma_{i,a} is the controller’s current effective per-batch price. The numerical threshold is

δa=max⁡{τ,ϵmachmax⁡(1,∣Ia∣,∣Gmax⁡a∣)}(18)\delta_a = \max\{\tau,\epsilon_{\mathrm{mach}}\max(1,\lvert I_a\rvert,\lvert G^{a}_{\max}\rvert)\} \tag*{(18)}

where ϵmach\epsilon_{\mathrm{mach}} is double-precision machine epsilon and the available implementation defaults to τ=10−9\tau= 10^{-9}. If ρa>δa\rho_a > \delta_a and halving keeps the multiplier and effective costs positive, the visited controller halves ηa\eta_a and yields without an evaluation. Otherwise, it records a numerical stop, including when the next halving would underflow. Let FF collect the current numerical-stop marks. A newly purchased batch clears FF. Acquisition ends when every controller in A\mathcal{A} is marked without an intervening observation, an optional external cost cap is reached, or all configurations are complete. Users may also stop after any completed batch and retain the latest recommendation. A numerical stop is not statistical certification. Algorithm 1 gives the replay rule.

Algorithm 1 CC-Gittins replay for quality–cost and quality–cost–latency

Require: configurations, objective setting d∈{2,3}d \in\{2,3\}, controller set A\mathcal{A} and visit order, batch size BB, optional external API cost cap, tolerance τ\tau

  1. acquire warm batches; freeze posterior calibration, objective scales, and κ^i\hat{\kappa}_i

  2. set ηa=1\eta_a = 1 for every a∈Aa \in\mathcal{A} and F=∅F = \varnothing

  3. publish the conservative Pareto set in the selected dd objectives

  4. while search has not been interrupted, any external cost cap permits evaluation, unfinished configurations remain, and F≠AF \ne\mathcal{A} do

  5. &nbsp;&nbsp;&nbsp;&nbsp;a←a \leftarrow next controller in the specified round-robin order

  6. &nbsp;&nbsp;&nbsp;&nbsp;i←arg⁡max⁡j unfinishedGj,kjai \leftarrow\arg\max_{j\ \mathrm{unfinished}} G^{a}_{j,k_j}; obtain completed incumbent IaI_a

  7. &nbsp;&nbsp;&nbsp;&nbsp;if Gi,kia≤Ia+τG^{a}_{i,k_i} \le I_a+\tau then

  8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;compute remaining penalty ρa\rho_a and threshold δa\delta_a

  9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if ρa>δa\rho_a > \delta_a and the next halving keeps effective costs positive then

  10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ηa←ηa/2\eta_a \leftarrow\eta_a/2; remove aa from FF

  11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else

  12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;add aa to FF

  13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end if

  14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;continue to the next visit

  15. &nbsp;&nbsp;&nbsp;&nbsp;end if

  16. &nbsp;&nbsp;&nbsp;&nbsp;acquire ii’s next batch, charge realized API cost, and update all dd posterior marginals

  17. &nbsp;&nbsp;&nbsp;&nbsp;F←∅F \leftarrow\varnothing; publish the updated conservative Pareto set

  18. end while

  19. return the latest published Pareto recommendation

Additional Objectives and the Quality–Cost–Latency Extension

Suppose d≥2d \ge2 objectives include per-query deployment cost DiD_i, and let zi∈Rd−1z_i \in\mathbb{R}^{d-1} collect the remaining higher-is-better objectives. For v∈Δd−2v \in\Delta^{d-2}, use terminal utility Uv(i)=vTziU_v(i) = v^{\mathsf{T}}z_i. Under zero uncertainty, equal remaining horizon hh of full batches, and exact coupling κi=BDi\kappa_i = BD_i, the index ranks

vTzi−ηhBDi=vTzi−λDi.(19)v^{\mathsf{T}}z_i-\eta hBD_i = v^{\mathsf{T}}z_i-\lambda D_i. \tag*{(19)}

A normalized linear weight vector over dd objectives has d−1d-1 degrees of freedom. Cost coupling supplies the cost weight, leaving d−2d-2 explicit direction dimensions among non-cost objectives. This statement concerns linear scalarizations with positive total weight on non-cost objectives; a pure cost controller handles the remaining cost extreme. It does not remove unsupported-front geometry or guarantee that a discrete η\eta schedule realizes every weight.

Quality–cost–latency controllers. Let LiL_i be mean end-to-end workflow latency in the recorded execution environment, and set ℓi=1−Li/T\ell_i = 1 - L_i/T using a positive scale TT frozen after warm-up. The reported method has four directions in acquisition coordinate order (Q,C,ℓ)(Q,C,\ell): pure quality (1,0,0)(1,0,0), balanced quality–latency (12,0,12)\left(\frac{1}{2},0,\frac{1}{2}\right), pure latency (0,0,1)(0,0,1), and pure cost (0,1,0)(0,1,0). The pure directions use the corresponding scalar desirabilities. The balanced direction instead uses the radial terminal utility min⁡{Qi,ℓi}\min\{Q_i,\ell_i\} in Eq. (13); its direction specifies equal scaling of two desirabilities, not their arithmetic mean. The choice of this intermediate direction is empirical. In particular, the linear supported-front argument above does not prove that these four controllers cover the three-objective frontier.

Posterior and acquisition. The three raw outcomes have independent Gaussian posterior marginals. Quality and cost use the scalar indices in Eq. (8); latency uses the latent-posterior transform mi,nℓ=1−mi,L,n/Tm^{\ell}_{i,n}=1-m_{i,L,n}/T and vi,nℓ=vi,L,n/T2v^{\ell}_{i,n}=v_{i,L,n}/T^2. For the balanced direction, the two-coordinate radial dynamic program uses the latent posterior means and variances of (Qi,ℓi)(Q_i,\ell_i) and the expected minimum as its terminal reward. The finite-benchmark-mean bridge in Eq. (11) is used for recommendation. The balanced controller does not project a joint posterior onto the linear average (Qi+ℓi)/2(Q_i+\ell_i)/2, and it makes no fitted cross-objective covariance claim. Each measured execution updates all three outcomes for every controller. Controllers take turns, independently relax their positive evaluation-cost penalties after local stopping signals, and charge observed token-priced API spend; latency does not price evaluation.

Recommendation and evaluation geometry. Augment Eq. (12) with Li,n+=Mi,L,n+βUi,L,nL^+_{i,n}=M_{i,L,n}+\beta\sqrt{U_{i,L,n}} and return configurations nondominated when maximizing Q−Q^- and minimizing D+,L+D^+,L^+. This conservative recommendation rule retains the same heuristic status as its two-objective counterpart; the random baselines form empirical three-objective Pareto recommendations. For offline evaluation only, the true means are mapped to

yi(3)=(Qi,RLRL+Li,RDRD+Di),(20)y_i^{(3)}=\left(Q_i,\frac{R_L}{R_L+L_i},\frac{R_D}{R_D+D_i}\right), \tag*{(20)}

where RLR_L and RDR_D are medians of strictly positive full-data assignment means for latency and deployment cost, respectively. These nonlinear reciprocal scales never enter acquisition. Using the origin reference, we compute three-dimensional HV regret and Euclidean GD/IGD on these fixed coordinates. The complete three-dimensional frontiers have 17 points on MathQA and 23 on HotpotQA; we did not compute a three-dimensional supported-front oracle.

Experimental integration. The two three-objective replays use the complete HotpotQA and MathQA matrices (100 assignments and 200 questions each), four warm questions per assignment, batches of up to four unseen questions, and 20 paired question-order seeds. End-to-end workflow latency is the recorded per-question wall-clock time of an assignment, distinct from optimizer overhead. On a fixed 0.5-percentage-point grid, we show each seed’s latest completed checkpoint at or below the target fraction of exhaustive observed API spend, without interpolating or overspending. At each target, means and ±2\pm2 sample-standard-error bands summarize the contributing seeds, and band lower bounds are clipped at zero. The random-question baseline evaluates a shared question prefix across assignments, while random configurations evaluates complete assignment prefixes; both form empirical three-objective Pareto recommendations. These comparisons therefore include differences in both evaluation selection and recommendation rules. Figure 7 also includes three-objective EGE-SH, APE-kk, and qNEHVI.

Three-objective evaluation of quality, deployment cost, and latency on HotpotQA and MathQA

Figure 7. Three-objective evaluation of quality, deployment cost, and latency on HotpotQA (top) and MathQA (bottom) over 0–30% of exhaustive API evaluation cost. CC-GITTINS uses four controllers. Curves show seed means; bands show ±2 standard errors.

Controlled ablations. Appendix § 19 compares real and unit acquisition prices, single-axis and multi-direction controller sets, direction-local relaxation against fixed-price continuation, and prior-variance calibration. These controls retain the same three-objective recommendation rule and realized-dollar accounting. Their results distinguish improvements in dominated-volume recovery and recommendation proximity from improvements in frontier coverage.

Experimental Setup and Implementation Details

Benchmark Matrices

Each response matrix has one row per retained role-level model assignment and one column per question. We collect complete HotpotQA and MathQA matrices by evaluating all 102=10010^2 = 100 assignments of ten candidate models to two roles on all 200 questions, or 20,000 observed cells per benchmark. The two workflow settings follow those described in AgentOpt (Hua et al., [6]). The calculated exhaustive API costs are $62.58 and $234.34, respectively. Their full-data Pareto frontiers contain 15 and 6 assignments, and their maximum mean quality scores are 74.66% token-level F1 for HotpotQA and 97.50% accuracy for MathQA. The six SCOPE matrices use fully evaluated configuration rows from SCOPE’s released per-query cache for three data-processing systems (Huang et al., [7]). Every retained SCOPE configuration has score and token records for all questions in its corresponding benchmark split. Summing the per-entry API costs over each retained configuration–question matrix gives calculated exhaustive API costs of $2,067.38, $946.78, $149.24, $14.84, $80.15, and $2.55 for BIRD Mini Dev, BIRD Dev, Bing Query Logs, Stack Overflow, Restaurant Valid, and Restaurant Test, respectively. These configurations cover a subset of the nominal Cartesian product of role-level model choices; we do not infer results for unobserved configurations. Table 1 reports the retained dimensions used by every compared method. Thus, the exhaustive-evaluation cost and full-data Pareto frontier for each instance refer to its retained matrix; paired development and test instances may contain different assignment sets.

Benchmark instanceWorkflowRolesConfigurationsQuestions
HotpotQAPlanner–solver2100200
MathQAAnswerer–critic2100200
BIRD Mini DevDIN-SQL41,115500
BIRD DevDIN-SQL4751,534
Bing Query LogsUniDM-DT51,681102
Stack OverflowUniDM-DT523710
Restaurant ValidUniDM-DI3972156
Restaurant TestUniDM-DI33686

Table 1. Benchmark matrices used in the eight-instance evaluation. We collected HotpotQA and MathQA observations with our workflow evaluation harness; the other six instances use SCOPE’s released evaluation records. “Configurations” counts retained role-level model assignments (the arms of the search problem), and “Questions” counts each instance’s evaluation horizon, covered by every retained configuration.

At the question level, HotpotQA uses a continuous token-level F1 score in [0, 1]. Since HotpotQA produces free-form answers, token-level F1 preserves partial credit for token overlap that binary exact match would discard. MathQA uses a binary correctness indicator, and each released per-query evaluation in the six SCOPE-derived instances likewise provides a binary task-success outcome. Consequently, configuration-level mean quality is mean F1 for HotpotQA and the empirical success rate for the other seven instances.

Model Pricing and Cost Accounting

Table 2 lists the ten models in the HotpotQA and MathQA matrices and the AWS Bedrock US standard on-demand prices used for cost accounting.3 Each workflow execution’s API cost is the sum, across both roles, of its recorded input and output token counts multiplied by the corresponding per-million-token rates. The GPT-5.6 Luna rate uses the US commercial short-context tier (up to 272K input tokens per request). The six SCOPE-derived matrices use the token records and model API prices in their released evaluation cache.

ModelInputOutput
Claude Haiku 4.51.005.00
Claude Opus 4.65.0025.00
DeepSeek R11.355.40
GPT-5.6 Luna0.221.32
gpt-oss-120b0.150.60
gpt-oss-20b0.070.30
Kimi K2.50.603.00
Ministral 3 8B0.150.15
Qwen3 32B0.150.60
Qwen3 Next 80B A3B0.151.20

Table 2. AWS Bedrock US standard on-demand input and output prices used for the ten models in our HotpotQA and MathQA evaluations, in USD per million tokens.

Two-objective CC-Gittins configuration

In practice, evaluation queries can be run in batches of size BB to reduce wall-clock latency through parallel execution; B=1B = 1 is also valid.

ComponentSetting
Warm start / adaptive batch4 / up to 4 questions per configuration
Statistical targetMean of the fixed benchmark
Cost coordinatesDeployment cost (USD per query); C=1−D/RC = 1 - D/R for acquisition
Directions (in visit order)(0, 1) cost, (1, 0) quality
Scheduler1:1 decision opportunities, shared observations
MultipliersηC=ηQ=1\eta_C = \eta_Q = 1; independent halving
Numerical safeguardPrecision threshold in Eq. (18); underflow check
TerminationBoth local numerical stops, replay cost cap, or exhaustive completion
RecommendationConservative Pareto, β=1\beta= 1, no set-size cap
Search cost accountingToken-based API cost (USD), including warm start

Table 3. Two-objective CC-Gittins settings for the reported replay.

Baseline implementations

All five baselines use the same frozen response matrices but follow their own sampling protocols; checkpoints are aligned by realized cumulative API search cost. EGE-SH allocates observations in rounds and uses empirical Pareto gaps to halve the active assignments [11]. We use the confidence-bound sampling rule of APE-kk to direct observations toward uncertain Pareto comparisons; its fixed-confidence stopping condition is disabled, and sampling continues until the replay observation cap is reached or available observations are exhausted [10]. qNEHVI uses a Bayesian surrogate over categorical assignment features and chooses evaluations by noisy expected hypervolume improvement (Daulton et al., 2021).

The two random search baselines differ in the sampled unit: random questions evaluates all assignments on the same randomly drawn questions, while random configurations fully evaluates randomly drawn assignments. Both recommend the empirical Pareto set from their observed outcomes.

Supported-Front Analysis

The full-data supported-front analysis examines what the weighted-score family can represent on each matrix. For this analysis, HV and distances use (Qi,1−Di/(1.05max⁡jDj))(Q_i, 1 - D_i/(1.05 \max_j D_j)), with the origin as the HV reference. For HotpotQA, 6 of the 15 true Pareto points are supported. Keeping those six loses only 0.00066 of absolute hypervolume, although the furthest omitted frontier point is 0.0716 away in normalized coordinates. Stack Overflow and Restaurant Test have no unsupported frontier points. This offline oracle considers all nonnegative weights and known outcomes; it does not assess CC-GITTINS recommendations at intermediate search costs.

CC-Gittins Replay Results

Protocol and scope. CC-GITTINS uses the exact cost and quality axes (0,1)(0, 1) and (1,0)(1, 0), real per-configuration acquisition costs, independent direction-local η\eta decay, shared observations, and round-robin controller visits. The evaluation covers eight benchmarks and seeds 42–61. HotpotQA and MathQA use the complete 10×1010 \times10 assignment matrices.

The 0–30% curves use fixed 0.5-percentage-point targets and summarize the latest recommendation recorded at or below each target.

Recommendation snapshots at cost checkpoints

Figure 9 and Figure 10 in Appendix § 16 show recommendation snapshots at cost checkpoints of 10% and 30% of exhaustive API evaluation cost across eight instances. Each snapshot is the latest recommendation available at or below the checkpoint on the recorded search trajectory. At 10%, the recommendation contains a small set of configurations supported by the available observations. By 30%, more configurations have narrower predictive intervals, and the set traces more of the quality–cost frontier. The quality controller can favor interior supported trade-offs through its cost penalty, while the cost controller directly explores the low-cost region. Figure 11 and Figure 12 then compare checkpoint-estimated and exhaustive coordinates for the same seed-42 recommendation sets, separating estimation error from configuration selection.

CC-Gittins recommendation snapshots at the 10% checkpoint of exhaustive API evaluation cost across eight benchmark instances and 20 seeds

Figure 9. CC-Gittins recommendation snapshots at the 10% checkpoint of exhaustive API evaluation cost across eight benchmark instances and 20 seeds. Each snapshot uses the latest recommendation available at or below the checkpoint. Gray points show all configurations; the black line shows the full-data Pareto frontier. Orange markers locate recommended configurations at their exhaustive mean quality and deployment cost, with color indicating recommendation frequency across seeds. The line beneath each panel title reports the mean start–end interval over which the checkpoint recommendation remains stable, first as cumulative API cost (USD) and then as a fraction of exhaustive search cost.

Cost-Coupled Gittins recommendations at 30% of brute-force search cost across HotpotQA, Restaurant Valid, BIRD Mini Dev, Bing Query Logs, MathQA, Restaurant Test, BIRD Dev, and Stack Overflow

Figure 10. CC-GITTINS recommendation snapshots at the 30% checkpoint of exhaustive API evaluation cost, displayed as in Figure 9. Marker color gives recommendation frequency across 20 seeds; positions use exhaustive mean quality and deployment cost for retrospective comparison.

Estimated and actual Pareto recommendations at the 10% search-cost checkpoint for seed 42

Figure 11. Estimated and actual Pareto recommendations at the 10% search-cost checkpoint for seed 42. Rows show CC-GITTINS and the five baselines; columns show exhaustive (actual) and checkpoint-estimated coordinates for the same recommended configurations on HotpotQA and Stack Overflow. Gray points are all configurations, hollow markers and connecting lines show the exhaustive Pareto frontier, and orange points show the configurations recommended by each method.

Estimated and actual Pareto recommendations at the 30% search-cost checkpoint for seed 42

Figure 12. Estimated and actual Pareto recommendations at the 30% search-cost checkpoint for seed 42, using the same layout and visual encoding as Figure 11. The paired columns separate checkpoint estimation error from the choice of recommended configuration identifiers.

Ablations and interpretation

Appendix § 18 varies one conceptual component around G0: acquisition-cost pricing, controller directions, relaxation, scheduling, or prior calibration. At the 30% checkpoint, G0 has lower mean HV regret, GD, and IGD than every cost-mechanism control. Adding a midpoint or five directions can lower HV regret or GD further, but neither improves all three metrics: G0 retains the lowest mean IGD in that family. The fixed-η\eta no-stop control has worse HV regret, GD, and IGD than G0’s relaxation mechanism, while sequentially draining one axis underperforms round-robin independent relaxation. We report HV, GD, and IGD together since improvements in dominated area, recommendation reliability, and frontier coverage need not coincide.

Runtime Results

Figure 8 compares the total wall-clock runtime of the six methods. qNEHVI has the highest mean runtime on all eight benchmarks, and the gap widens substantially on the three largest SCOPE matrices. Its mean runtime reaches 6.2 hours on Restaurant Valid, 10.4 hours on BIRD Mini Dev, and 22.5 hours on Bing Query Logs, compared with 1.1, 3.6, and 3.0 minutes for CC-GITTINS, respectively. CC-GITTINS has a mean runtime below 3.6 minutes on every benchmark. EGE-SH and APE-kk also remain below 18 minutes, while the two random baselines finish in approximately 8–14 seconds. These results show that qNEHVI’s computational overhead becomes the dominant cost as the configuration matrix grows.

Mean total wall-clock runtime of the six methods across eight benchmark instances

Figure 8. Mean total wall-clock runtime of the six methods across eight benchmark instances. The vertical axis uses a base-10 logarithmic scale, with major ticks marking successive powers of ten. Bars show means and error bars show ±2 standard errors across 20 matched seeds. CC-Gittins timings cover the complete child Python process, including startup, data loading, policy computation, postprocessing, and result serialization; parent validation and Slurm queue time are excluded.

CC-Gittins Pareto Plots

Pareto Plot Protocol at Cost Checkpoints

For every benchmark, seed, and target b∈{0.1,0.3}b \in\{0.1, 0.3\}, we select the last recommendation event whose realized cost fraction does not exceed bb. The selected configurations are then placed at exhaustive raw mean quality and mean deployment cost (USD per query). These exhaustive coordinates are used only for offline evaluation and are not available to the selector.

The plot distinguishes completed from partial recommendations since their online semantics differ. A completed point has zero predictive variance for the benchmark mean and its displayed coordinate matches its recommendation estimate. A partial point is selected using Eq. (12), while its displayed exhaustive coordinate reveals estimation error. All methods use the same axis limits within a benchmark.

Figure 11 and Figure 12 isolate estimation error from configuration selection for HotpotQA and Stack Overflow at seed 42. Within each benchmark, the actual and estimated columns contain the same recommended configuration identifiers; only their plotted coordinates change. Thus, displacement between a method’s paired panels reflects error in the online estimates available at the checkpoint rather than a change in the returned set.

Controlled CC-Gittins Ablations

Protocol. We center four one-factor families and a 2×22 \times2 prior-variance study (Figure 18) on G0, the CC-Gittins protocol with real per-configuration acquisition costs, independent direction-local η\eta decay, and round-robin axis visits. The cost family compares G0 with quality-only real cost (G1), quality-only unit cost (G2), and exact axes with unit cost (G3). The direction family includes quality-only G1, deployment-only G4, G0, axes plus the midpoint (G5), and five evenly spaced directions (G6), all with real costs. The relaxation family compares G0’s independent direction-local relaxation with the fixed-η\eta no-stop control (G7). The scheduler family compares G0 with quality-then-deployment (G8) and deployment-then-quality (G9), which drain one axis before visiting the other.

Prior-variance curves across eight benchmarks, showing HV Regret, GD, and IGD

Figure 18. Prior-variance ablation across eight benchmarks (lower is better). Rows group workflows by role count; columns report HV regret, GD, and IGD. G0 estimates both quality (Q) and deployment-cost (D) prior variances from warm-start batches to calibrate initial uncertainty to the observed data. G10 fixes only Q, G11 fixes only D, and G12 fixes both. Fixed entries use variance 0.04 in the quality or cost-desirability coordinate C=1−D/RC = 1 - D/R; the latter corresponds to raw cost variance 0.04R20.04R^2 in USD squared. G0 has the lowest aggregate mean GD at 30%, while HV regret and IGD show trade-offs across settings. Prior means, observation noise, warm observations, and all other policy settings are held constant. Curves show means over 20 matched seeds; bands show ±2 standard errors.

Each configuration uses the same eight benchmark matrices, 20 seeds, model ordering, exhaustive truth vectors, recommendation rule, batch size, and cost checkpoints spanning 0–30% of exhaustive API evaluation cost. The frontier-metric grid contains thirteen configurations and 2,080 validated benchmark–seed runs. At each fixed 0.5-percentage-point target, we score each contributing seed’s last recommendation not exceeding that cost. Curves show seed means and bands show ±2\pm2 standard errors. HV regret, GD, and IGD are all lower-is-better and use the same frozen per-benchmark metric space as the primary comparison.

Cost mechanism. Figure 13 separates acquisition pricing from controller choice. G0 versus G3 and G1 versus G2 compare real with unit prices; the comparisons retain deployment-cost observations, the Pareto recommendation rule, and realized-dollar accounting. G0 versus G1 and G3 versus G2 test adding the cost controller at fixed pricing. Real prices align acquisition with monetary spend; the cost controller targets inexpensive assignments. These controls support combining both mechanisms, with benchmark-dependent gains. They assess pricing and controller choices within the coupled setting, rather than isolating the effect of the relation κi=BDi\kappa_i = BD_i itself.

Cost-mechanism ablation curves across eight benchmarks

Figure 13. Cost-mechanism ablation across eight benchmarks (lower is better). Rows group the two-, three-, four-, and five-role workflows; columns report hypervolume (HV) regret, generational distance (GD), and inverted generational distance (IGD). G0 combines real acquisition costs with quality and deployment-cost controllers and achieves the lowest aggregate mean of all three metrics at the 30% checkpoint. Its advantage over quality-only acquisition (G1, G2) and unit-cost axes (G3) is especially clear on several benchmarks, while the coverage advantage remains benchmark-dependent. Curves show seed means at fixed API cost checkpoints; shaded bands indicate ±2\pm2 standard errors.

Directions. Figure 14 shows that extra directions redistribute evaluation effort rather than uniformly improving the recommendation. Intermediate controllers can concentrate evidence on a compact set of high-value trade-offs, improving dominated-volume recovery and recommendation proximity while weakening uniform frontier coverage. The one-axis controls show the benefit of retaining both endpoint-oriented controllers, while adding directions does not mechanically enlarge the final set because all controllers share observations and a common conservative recommendation rule forms the returned set. The frontier-metric curves compare variants at matched fractions of exhaustive API evaluation cost, whereas the runtime experiment fixes the number of evaluated matrix entries at [0.30K N][0.30K\,N], where KK is the number of configurations and NN is the number of questions in the benchmark matrix. The latter measures policy computation at equal evaluation counts rather than equal search cost. Including the single-direction controls, the runtime experiment covers five settings (Figure 15). G0 has lower mean policy runtime than both denser direction sets on all eight benchmarks. Averaging per-benchmark runtime ratios, G5 and G6 require 1.39×\times and 1.74×\times G0’s policy time, respectively. Together with the frontier-quality controls, these results support the two-axis configuration as a trade-off between frontier recovery and policy computation.

Direction ablation curves across eight benchmarks, showing HV Regret, GD, and IGD metrics for eight benchmarks and six controller variants

Figure 14. Direction ablation across eight benchmarks (lower is better). Columns report HV regret, GD, and IGD, and rows are ordered by workflow role count. G0 achieves competitive frontier metrics using only two exact-axis controllers and substantially improves on the single-direction controls on most benchmarks. At 30%, G0 has the lowest aggregate mean IGD; adding directions does not uniformly improve all three frontier metrics. Together with G0’s runtime relative to denser direction sets (Figure 15), these results support the two-axis design as an economical overall choice. All variants use real acquisition costs; curves show seed means and shaded bands indicate ±2\pm2 standard errors.

Relaxation. Figure 16 compares G0’s independent direction-local relaxation with the fixed-η\eta no-stop control G7. In G0, a local stopping signal triggers a reduction of the visited controller’s information-price multiplier when possible, allowing configurations whose value of information was marginal at an earlier price scale to become eligible for further evaluation. G7 instead retains the initial price scale and continues without a Gittins stop. G0 achieves lower aggregate mean HV regret, GD, and IGD at the 30% checkpoint. These results support the relaxation mechanism for improving volume recovery and frontier coverage while maintaining competitive recommendation proximity; the gains vary across benchmarks.

Relaxation ablation curves across eight benchmarks

Figure 16. Relaxation ablation across eight benchmarks (lower is better). Columns report HV regret, GD, and IGD, and rows are ordered by workflow role count. G0’s independent direction-local relaxation maintains competitive recommendation proximity and improves volume recovery and frontier coverage over the fixed-η\eta no-stop control (G7) on several benchmarks. At 30%, G0 has lower aggregate mean HV regret, GD, and IGD, supporting our choice of the relaxation mechanism. Curves show seed means at fixed API cost checkpoints; shaded bands indicate ±2\pm2 standard errors.

Scheduler. Figure 17 shows that controller order affects recommendation quality at matched cumulative search cost: a sequential policy allocates early evaluations to its first controller and postpones evidence about the opposite frontier extreme. Round-robin scheduling instead balances directional attention from the outset, while shared observations allow every purchased batch to inform both controllers. This combination exposes both endpoints early enough for their evidence to shape the interior recommendation, making interleaving more robust than draining either axis first.

Scheduler ablation curves across eight benchmarks, with columns for HV Regret, GD, and IGD

Figure 17. Scheduler ablation across eight benchmarks (lower is better). Columns report HV regret, GD, and IGD, and rows are ordered by workflow role count. G0’s 1:1 round-robin interleaving achieves competitive recommendation quality across the displayed benchmarks and substantially improves on quality-first scheduling (G8) or deployment-first scheduling (G9) in several cases. At 30%, G0 has the lowest aggregate mean of all three metrics in this family, supporting interleaving at matched cumulative search cost while acknowledging benchmark-dependent effect sizes. Curves show seed means at fixed cost checkpoints; shaded bands indicate ±2 standard errors.

Cost-mechanism curves

Direction curves

Relaxation curves

Scheduler curves

Prior-variance curves

Controlled Three-Objective Ablations

Protocol. We center three one-factor families and a 2×2×22 \times2 \times2 prior-variance study (Figure 23) on G0, the four-controller CC-GITTINS protocol with the Q, L, and D axes plus the balanced Q–L midpoint, real acquisition costs, independent direction-local η\eta decay, and round-robin visits. The cost family pairs Q-only real and unit pricing (G1, G7), pure-axis real and unit pricing (G4, G8), and midpoint-augmented real and unit pricing (G0, G9). The direction family compares Q-only G1, L-only G2, D-only G3, pure axes G4, G0, six Q–L-dense directions G5, and six three-edge directions G6, all with real costs and independent direction-local η\eta decay. The relaxation family compares G0 with fixed η=1\eta= 1 without Gittins stopping (G10). These identifiers refer to the three-objective controls throughout this section.

Three-objective prior-variance ablation curves for HotpotQA and MathQA

Figure 23. Three-objective prior-variance ablation on HotpotQA (top) and MathQA (bottom). Columns report HV regret, GD, and IGD (lower is better). The 2×2×22 \times2 \times2 design crosses warm-start estimation and fixed variance for quality (Q), latency desirability (L), and deployment-cost desirability (D). G0 estimates all three variances from warm-start batches; G11–G17 cover the other seven combinations, as specified in the legend. Fixed entries use variance 0.04 in the corresponding desirability coordinate, equivalent to raw latency variance 0.04T20.04T^{2} in seconds squared and raw cost variance 0.04R20.04R^{2} in USD squared. Prior means, observation noise, warm observations, and all other policy components are held constant. At 30%, G0 has zero HotpotQA GD and low MathQA GD. HV regret and IGD show benchmark-dependent trade-offs across prior settings. The main policy uses warm-start estimates for all three priors to calibrate initial uncertainty from the observed data. Curves show means over 20 matched seeds; bands show ±2\pm2 standard errors.

Each configuration uses the same complete HotpotQA and MathQA matrices, 20 paired question-order seeds, four warm questions per assignment, batches of up to four questions, conservative three-objective recommendation rule, and cost checkpoints spanning 0–30% of exhaustive API evaluation cost. The frontier-metric grid contains eighteen configurations and 720 benchmark–seed runs. In the legends, Q, L, and D denote quality, latency-desirability, and deployment-cost-desirability controllers; L and D correspond to ℓ\ell and CC in Appendix § 11. At each 0.5-percentage-point target, we score each contributing seed’s latest completed recommendation not exceeding that cost, retaining the final recommendation after a policy stops. Curves show means and ±2 standard errors. HV regret, GD, and IGD are lower-is-better and use the fixed metric space in Appendix § 11; GD and IGD score the complete returned set.

Cost mechanism. Figure 19 separates acquisition pricing from controller choice. G1 versus G7, G4 versus G8, and G0 versus G9 compare real with unit prices while retaining observed deployment costs, the Pareto recommendation rule, and realized-dollar accounting. Real pricing improves volume recovery and recommendation proximity for the multi-controller variants on both matrices, while coverage gains remain benchmark-dependent. These controls support cost-aware acquisition without implying that lower HV regret and GD guarantee better frontier coverage.

Three-objective cost-mechanism ablation curves for HotpotQA and MathQA, showing HV Regret, GD, and IGD against Percentage of Exhaustive Evaluation Cost; legend: G0 Axes + midpoint, real cost; G1 Q-only, real cost; G4 Axes, real cost; G7 Q-only, unit cost; G8 Axes, unit cost; G9 Axes + midpoint, unit cost; shaded bands $\pm 2$ SE

Figure 19. Three-objective cost-mechanism ablation on HotpotQA (top) and MathQA (bottom). Columns report HV regret, GD, and IGD (lower is better). G0 combines real acquisition costs with four controllers and achieves lower mean HV regret and GD than its unit-cost counterpart G9 on both benchmarks at 30%. G0 also improves HotpotQA IGD, while coverage gains remain benchmark-dependent. The Q-only pair G1/G7 and pure-axis pair G4/G8 provide corresponding pricing controls. These comparisons vary only the acquisition penalty, retaining observed deployment costs, the Pareto recommendation rule, and realized-dollar accounting. Curves show seed means and bands show ±2\pm2 standard errors.

Directions. Figure 20 shows that additional directions redistribute evaluation effort rather than uniformly improving the recommendation. All controllers observe the same three outcomes, which a common recommendation rule uses to form the returned set. G4 interleaves the three pure axes; G0 adds the Q–L midpoint with radial utility min⁡{Qi,ℓi}\min\{Q_i,\ell_i\}. G5 combines the Q–L endpoints, quarter points, and midpoint with the D axis; G6 combines the three axes with the Q–L, L–D, and Q–D midpoints. Round-robin scheduling balances decision opportunities, not purchased batches or dollars. Multi-controller search improves volume recovery over the single-direction controls. The three-edge geometry helps on HotpotQA, while pure axes remain competitive on MathQA; adding the Q–L midpoint can improve early coverage without retaining that advantage at later cost checkpoints. The preferred geometry therefore depends on the benchmark, cumulative search cost, and frontier metric.

Three-objective direction ablation curves for HotpotQA and MathQA, showing HV Regret, GD, and IGD

Figure 20. Three-objective direction ablation on HotpotQA (top) and MathQA (bottom). Columns report HV regret, GD, and IGD (lower is better). G0 combines the three pure axes with the Q–L midpoint, achieving strong volume recovery and low GD on both benchmarks. At 30%, its mean HV regret is lower than that of all three single-direction controls G1, G2, and G3. Increasing the direction count does not uniformly improve all three frontier metrics, and coverage remains benchmark- and budget-dependent. Together with G0’s modest policy computation overhead (Figure 21), these results support our choice of four directions as the main three-objective configuration. All variants use real acquisition costs; curves show seed means and bands show ±2\pm2 standard errors.

Figure 21 compares policy computation at an equal number of evaluated entries. All tested direction sets have mean runtimes on the same tens-of-seconds scale, with G0 remaining within this range on both matrices. Together with G0’s strong hypervolume recovery and low GD (Figure 20), this modest computational overhead motivates our choice of four directions as the main configuration for the three-objective experiments.

Direction Runtime Comparison bar charts for HotpotQA and MathQA showing mean policy wall-clock runtime for seven direction configurations with ±2 SE error bars

Figure 21. Three-objective direction-ablation policy runtime for a fixed workload of 30% of matrix entries (lower is better). G0’s four-direction configuration takes 13.6 seconds on HotpotQA and 14.3 seconds on MathQA, within the 10.2–16.5-second range across all tested variants. Its mean runtime is about 2–3 seconds above the three-axis control on each matrix, indicating modest absolute computational overhead for the main configuration. For every benchmark and matched seed, all seven variants evaluate exactly ⌈0.30KN⌉=6,000\lceil0.30KN \rceil= 6{,}000 entries (K=100K = 100 configurations and N=200N = 200 questions), with a shortened final batch when needed; native stopping signals do not terminate these runs before the common cap. Bars and error bars show means and ±2\pm2 standard errors over 20 matched seeds. The timer isolates online policy computation and excludes data loading, offline oracle analysis, result serialization, and Slurm queue time. Runs use the same code and data and are independently scheduled on HPC compute nodes, so node conditions may differ.

Relaxation. Figure 22 compares G0’s independent direction-local relaxation with fixed-price continuation G10 under the same four controllers and round-robin schedule. Relaxation can favor early volume recovery or recommendation proximity, but fixed-price continuation provides better frontier coverage at the final reported checkpoint on both matrices. The coverage benefit observed in the two-objective ablation therefore does not transfer uniformly to three objectives; the continuation policy requires a separate empirical assessment.

Three-objective relaxation ablation curves for HotpotQA and MathQA, showing HV Regret, GD, and IGD

Figure 22. Three-objective relaxation ablation on HotpotQA (top) and MathQA (bottom). Columns report HV regret, GD, and IGD (lower is better). G0 applies independent direction-local relaxation to four real-cost controllers: each multiplier starts at η=1\eta= 1 and is halved after a local stopping signal when further relaxation is allowed. Compared with fixed-η=1\eta= 1 no-stop control G10, G0 achieves lower HotpotQA HV regret at 10% and lower MathQA GD at 30%, illustrating gains in early volume recovery and recommendation proximity. G0 also has zero HotpotQA GD at 30%; its gains in volume recovery and recommendation proximity do not extend uniformly to frontier coverage. Both policies use equal-frequency round-robin visits; curves show seed means and bands show ±2\pm2 standard errors.

Cost-mechanism curves

Direction curves

Relaxation curves

Prior-variance curves

References

  1. [1]Aida Amini, Saadia Gabriel, Shanchuan Lin, Rik Koncel-Kedziorski, Yejin Choi, and Hannahaj Hajishirzi. MathQA: Towards interpretable math word problem solving with operation-based formalisms. In Proceedings of NAACL-HLT, pp. 2357–2367, 2019. doi: 10.18653/v1/N19-1245.DOI
  2. [2]Lingjiao Chen, Matei Zaharia, and James Zou. FrugalGPT: How to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.05176, 2023.arxiv.org/abs/2305.05176
  3. [5]Qitian Jason Hu, Jacob Bieker, Xiuyu Li, Nan Jiang, Benjamin Keigwin, Gaurav Ranganath, Kurt Keutzer, and Shrivash Kaushik Upadhyay. RouterBench: A benchmark for multi-LLM routing system. arXiv preprint arXiv:2403.12031, 2024.arxiv.org/abs/2403.12031
  4. [6]Wenyue Hua, Sripad Karne, Qian Xie, Armaan Agrawal, Nikos Pagontas, Kostis Kaffes, and Tianyi Peng. AgentOpt v0.1 technical report: Client-side optimization for LLM-based agent. arXiv preprint arXiv:2604.06296, 2026.arxiv.org/abs/2604.06296
  5. [7]Yiqian Huang, Shiqi Zhang, Tianyuan Jin, and Xiaokui Xiao. SCOPE: Cost-efficient model selection for compound AI systems under quality constraints. In Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2, pp. 1922–1931. Association for Computing Machinery, 2026. doi: 10.1145/37370855.3818067.
  6. [8]Yinsicheng Jiang, Liang Cheng, Yeqi Huang, Yufan Zhao, Zhan Lu, Li Dong, Wenda Li, Edoardo Ponti, and Luo Mai. Specialize roles, mix deployments: Pushing the cost–accuracy frontier of LLM agent teams. arXiv preprint arXiv:2606.20629, 2026.arxiv.org/abs/2606.20629
  7. [9]Yubin Kim, Chanwoo Park, Taehan Kim, Eugene Park, Samuel Schmidgall, Salman Rahman, Chunjong Park, Cynthia Breazeal, Xin Liu, Hamid Palangi, Hae Won Park, and Daniel McDuff. TeamBench: Evaluating agent coordination under enforced role separation. arXiv preprint arXiv:2605.07073, 2026.arxiv.org/abs/2605.07073
  8. [10]Cyrille Kone, Emilie Kaufmann, and Laura Richert. Adaptive algorithms for relaxed Pareto set identification. In Advances in Neural Information Processing Systems, volume 36, pp. 35190–35201, 2023. doi: 10.52202/075280-1528. URL https://proceedings.neurips.cc/paper_files/paper/2023/hash/6e976e7930460b5c3167a104ba8cc39c-Abstract-Conference.html.DOI
  9. [11]Cyrille Kone, Emilie Kaufmann, and Laura Richert. Bandit Pareto set identification: The fixed budget setting. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 2548–2556. PMLR, 2024. URL https://proceedings.mlr.press/v238/kone24a.html.arxiv.org/abs/2311.03992
  10. [12]Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with PagedAttention. In Proceedings of the 29th Symposium on Operating Systems Principles, pp. 611–626, 2023.arxiv.org/abs/2309.06180
  11. [13]Michael Luo, Xiaoxiang Shi, Colin Cai, Tianjun Zhang, Justin Wong, Yichuan Wang, Chi Wang, Yanping Huang, Zhifeng Chen, Joseph E. Gonzalez, et al. Autellix: An efficient serving engine for LLM agents as general programs. arXiv preprint arXiv:2502.13965, 2025.arxiv.org/abs/2502.13965
  12. [14]Zifan Lyu, Chahine Nejma, Tobias Wegel, Fanny Yang, and Florian E. Dorner. Cutting LLM evaluation costs with SyJSRs: A bandit algorithm that provably exploits model similarity. In International Conference on Machine Learning, 2026.
  13. [15]Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E. Gonzalez, M Waleed Kadous, and Ion Stoica. RouteLLM: Learning to route LLMs from preference data. In International Conference on Learning Representations, volume 2025, pp. 34433–34448, 2025.arxiv.org/abs/2406.18665
  14. [16]Nikos Pagonas, Matthew Lou, Tianyi Peng, Dan Rubenstein, and Kostis Kaffes. VineLM: Trie-based fine-grained control for agentic workflows. arXiv preprint arXiv:2605.23914, 2026.arxiv.org/abs/2605.23914
  15. [17]Felipe Maia Polo, Ronald Xu, Lucas Weber, Mirian Silva, Onkar Bhardwaj, Leshem Choshen, Allysson Flavio Melo de Oliveira, Yuekai Sun, and Mikhail Yurochkin. Efficient multi-prompt evaluation of LLMs. In Advances in Neural Information Processing Systems, volume 37, pp. 22483–22512, 2024. doi: 10.52202/079017-0707.DOI
  16. [18]Qian Xie, Yueli He, and Nairen Cao. Efficient cost-aware LLM evaluation via Bayesian bandit Gittins indices. In ICML 2026 Workshop on Decision-Making from Offline Datasets to Online Adaptation: Black-Box Optimization to Reinforcement Learning, 2026. URL https://arxiv.org/abs/2609.25645.
  17. [19]Bo Xue, Zhi Hong, Jiayi Li, Yuanyu Wan, Ji Cheng, and Shuang Qiu. Cost-aware multi-objective bandits: Theory and application to budgeted LLM configuration evaluation. arXiv preprint arXiv:2608.04333, 2026.arxiv.org/abs/2608.04333
  18. [20]Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2369–2380, 2018. doi: 10.18653/v1/D18-1259.DOI
  19. [21]Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Koyzrakis, Ion Stoica, Joseph E. Gonzalez, et al. SLang: Efficient execution of structured language model programs. Advances in Neural Information Processing Systems, 37: 62557–62583, 2024. doi: 10.52202/079017-2000.DOI
  20. [22]Jin Peng Zhou, Christian K. Belardi, Ruihan Wu, Travis Zhang, Carla P. Gomes, Wen Sun, and Kilian Q. Weinberger. On speeding up language model evaluation. In International Conference on Learning Representations (ICLR), 2025.arxiv.org/abs/2407.06172

Paper details

vlnc:W_x2cehh3e
Published
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

generative AI tools

View statement
Looking for related papers…
Contents