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.
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 denote the mean deployment cost per query for assignment . Evaluating a batch of comparable queries costs approximately . 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 index ranks 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.
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 generalized distance at low search cost, although frontier coverage varies across benchmarks. We further conduct controlled ablations and evaluate the method with server-reported LLM 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 recording task quality, deployment cost, and LLM latency. These records support evaluation 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 [3, 4]. 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 , with candidate model set for role . Let be the set of complete model assignments and its size. We number these configurations ; throughout, identifies one complete assignment. Configuration has task quality , to maximize, and mean deployment cost per query , 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
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, are the exhaustive means on the fixed -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 , with the origin as the hypervolume reference. In the quality–cost case, positive affine maps of give . Write . Let be the recommended configurations and their true objective vectors. These vectors are available to the offline evaluator, not the selector. Total search cost sums the batch charges across all evaluated configurations. For exhaustive search cost , the recommendation snapshot at cumulative cost fraction is
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 be the nonempty set of recommended assignments at their true normalized coordinates, and let be the Euclidean distance from to the nearest point in . 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
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 .
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 on 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 queries for configuration costs approximately . We use a positive estimate , fixed after warm-up, to select evaluations, while actual API charges contribute to the cumulative search cost . 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 , while the cost controller uses a transformed deployment cost , where is fixed after warm-up. We write
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 of objective , we use independent Gaussian posterior marginals
where and denote the posterior mean and variance after observed queries. The quality controller uses
while the cost controller uses
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 , let index the evaluation batches of configuration , and let be its number of observed queries at stage . We use the shorthand and . Let denote the completion stage.
Given an outside option , define the centered posterior mean . For a positive per-batch evaluation price and a mean-zero Gaussian increment , the recursion is
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 be the zero of . The two controllers use
The positive multipliers and , 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).

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 entries ( configurations and 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 and G0’s policy time on average across benchmark ratios. Bars and error bars show means and 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 () and quality () controllers alternate turns in the order . Each controller uses a multiplier , initially one, to scale the estimated evaluation cost in its Gittins index (Eq. (9)). On its turn, the controller compares the largest index among unfinished configurations with its best completed terminal value (set 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 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 remaining full batches of size to collect terminal utility, and each batch costs exactly . Among unfinished configurations,
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 ; lowering relaxes this requirement at fixed . This can expose supported trade-offs, meaning frontier points maximizing for some , 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 -question benchmark, let be the sum of observed outcomes and the frozen per-question residual variance. The predicted mean and variance of the final benchmark mean are
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:
For a Pareto recommendation, these paired scores define one point per assignment. Using each configuration’s current observation count , configuration dominates in this score space if and , 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. Figure 11 and Figure 12 illustrate the recommended configurations and quality–cost estimates available to users, comparing CC-GITTINS with the five baselines.

Figure 11. Recommendations and quality–cost estimates available to users 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. The CC-GITTINS estimates combine observed outcomes with posterior predictions for unobserved questions; baseline estimates are observed-question means. 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.

Figure 12. Recommendations and quality–cost estimates available to users at the 30% search-cost checkpoint for seed 42, using the same layout and visual encoding as Figure 11. Rows compare CC-GITTINS with the five baselines; actual coordinates provide a retrospective reference for the same recommended configurations.
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
Since evaluation costs scale with deployment costs, the evaluation-cost penalty also makes controllers targeting other objectives sensitive to deployment cost. With objectives, let collect non-cost desirabilities. For a linear utility , , Proposition 1’s deterministic assumptions give the ranking ; the explicit non-cost direction family has dimensions.
For quality , mean deployment cost , and mean latency , let , where 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
Taking the minimum favors assignments with both high quality and low latency. All four controllers share observations and independently relax their API evaluation-cost penalties. Algorithm 1 gives the common replay procedure; Appendix § 11 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 assignments on all 200 questions of each of HotpotQA [20] (planner and search-enabled solver) and MathQA [1] (answerer and critic). 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 § 12.§ 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. Metric scales are fixed across methods and seeds. We report HV regret, GD, and IGD (§ 2), dividing HV regret by 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- [10], and qNEHVI, a Bayesian optimization method that selects evaluations by noisy expected hypervolume improvement [4]. 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 § 12.§ 4 gives their replay protocols.
Quality–Cost Pareto Recommendation
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.

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 standard errors.

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

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. We prioritize representative Pareto-optimal recommendations: uncertainty penalties aim to reduce off-front selections but may exclude uncertain true Pareto points. This is consistent with low GD but weaker IGD (Figure 5); low HV regret can persist when retained points cover most dominated volume. On MathQA at 30% cost, random configuration search achieves lower IGD but higher HV regret and GD than CC-GITTINS.

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 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. 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 decay, on the HotpotQA and MathQA matrices across 20 matched seeds, comparing with the five baselines at matched search costs (Appendix § 11).
At 30% of exhaustive evaluation cost, CC-GITTINS usually outperforms the baselines in mean HV regret and GD, while its IGD is less competitive, particularly on MathQA. Pareto precision is high (99.6% and 100.0%), while frontier recovery remains incomplete (recall: 80.3% and 54.1%, respectively). Appendix § 19 assesses acquisition-cost pricing, controller directions, direction-local continuation, and warm-start prior calibration.
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
QX was supported in part by the Columbia AI Agents Initiative at Columbia Business School. 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 . At the terminal stage . If pointwise, then
Taking the maximum with zero preserves the inequality and proves it by backward induction. Continuation values are nondecreasing in ; consequently the nonnegative-continuation set for the higher price is contained in that for the lower price, and its threshold satisfies . With identical uncertainty schedules and remaining horizons, and give
We restrict to positive prices. At exactly zero cost, a nondegenerate Gaussian transition can make continuation strictly positive at every finite , 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, . For , the excess terminal value is . If , then
Thus the continuation root is . With quality terminal utility , the index is . With cost terminal utility , the same recursion gives . Since and , the cost-axis coefficient is positive. Required completion is essential: if a known terminal reward could be collected immediately, paying the remaining batches would be unnecessary. Unequal remaining horizons instead give configuration-specific penalties , 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 . If is the warm-batch mean cost and , use
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 times each configuration’s warm-start mean deployment cost to the nearest multiplicative bin with ratio 2 and anchor USD, then applies ; 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 (), the controller set is , visited in the order , with terminal utilities and . For quality–cost–latency (), use , visited in the order . Here , with frozen after warm-up, and the balanced terminal utility is . 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 and shares the observed outcomes.
The conservative Pareto recommendation rule returns configurations that are nondominated when maximizing and minimizing from Eq. (12). For , it also minimizes , with the same . 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 . Let be the best unfinished index; the implementation treats as a local stopping signal. At such a stop, let be the largest remaining effective completion penalty, where is the number of planned batches remaining and is the controller’s current effective per-batch price. The numerical threshold is
where is double-precision machine epsilon and the available implementation defaults to . If and halving keeps the multiplier and effective costs positive, the visited controller halves and yields without an evaluation. Otherwise, it records a numerical stop, including when the next halving would underflow. Let collect the current numerical-stop marks. A newly purchased batch clears . Acquisition ends when every controller in 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 , controller set and visit order, batch size , optional external API cost cap, tolerance
acquire warm batches; freeze posterior calibration, objective scales, and
set for every and
publish the conservative Pareto set in the selected objectives
while search has not been interrupted, any external cost cap permits evaluation, unfinished configurations remain, and do
next controller in the specified round-robin order
; obtain completed incumbent
if then
compute remaining penalty and threshold
if and the next halving keeps effective costs positive then
; remove from
else
add to
end if
continue to the next visit
end if
acquire ’s next batch, charge realized API cost, and update all posterior marginals
; publish the updated conservative Pareto set
end while
return the latest published Pareto recommendation
Additional Objectives and the Quality–Cost–Latency Extension
Suppose objectives include per-query deployment cost , and let collect the remaining higher-is-better objectives. For , use terminal utility . Under zero uncertainty, equal remaining horizon of full batches, and exact coupling , the index ranks
A normalized linear weight vector over objectives has degrees of freedom. Cost coupling supplies the cost weight, leaving 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 schedule realizes every weight.
Quality–cost–latency controllers. Let be the mean per-question sum of server-reported LLM request latencies, and set using a positive scale frozen after warm-up. The reported method has four directions in acquisition coordinate order : pure quality , balanced quality–latency , pure latency , and pure cost . The pure directions use the corresponding scalar desirabilities. The balanced direction instead uses the radial terminal utility 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 and . For the balanced direction, the two-coordinate radial dynamic program uses the latent posterior means and variances of 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 , 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 and return configurations nondominated when maximizing and minimizing , . 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
where and 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 11 points on MathQA and 29 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. We use cumulative server-reported LLM latency to reduce sensitivity to client-side processing and network conditions. For each configuration, we average the summed Bedrock-reported durations of successful LLM calls over all questions. Tool execution time is outside the scope of this metric. Optimizer overhead is measured separately. 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 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-, and qNEHVI.
Figure 7. Three-objective evaluation of quality, deployment cost, and cumulative server-reported LLM 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 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 instance | Workflow | Roles | Configurations | Questions |
| HotpotQA | Planner–solver | 2 | 100 | 200 |
| MathQA | Answerer–critic | 2 | 100 | 200 |
| BIRD Mini Dev | DIN-SQL | 4 | 1,115 | 500 |
| BIRD Dev | DIN-SQL | 4 | 75 | 1,534 |
| Bing Query Logs | UniDM-DT | 5 | 1,681 | 102 |
| Stack Overflow | UniDM-DT | 5 | 23 | 710 |
| Restaurant Valid | UniDM-DI | 3 | 972 | 156 |
| Restaurant Test | UniDM-DI | 3 | 36 | 86 |
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
The ten candidate models use AWS Bedrock Application Inference Profiles. 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.
| Model | Input | Output |
| Claude Haiku 4.5 | 1.00 | 5.00 |
| Claude Opus 4.6 | 5.00 | 25.00 |
| DeepSeek R1 | 1.35 | 5.40 |
| GPT-5.6 Luna | 0.22 | 1.32 |
| gpt-oss-120b | 0.15 | 0.60 |
| gpt-oss-20b | 0.07 | 0.30 |
| Kimi K2.5 | 0.60 | 3.00 |
| Ministral 3 8B | 0.15 | 0.15 |
| Qwen3 32B | 0.15 | 0.60 |
| Qwen3 Next 80B A3B | 0.15 | 1.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 to reduce wall-clock latency through parallel execution; is also valid.
| Component | Setting |
| Warm start / adaptive batch | 4 / up to 4 questions per configuration |
| Statistical target | Mean of the fixed benchmark |
| Cost coordinates | Deployment cost (USD per query); for acquisition |
| Directions (in visit order) | cost, quality |
| Scheduler | 1:1 decision opportunities, shared observations |
| Multipliers | ; independent halving |
| Numerical safeguard | Precision threshold in Eq. (18); underflow check |
| Termination | Both local numerical stops, replay cost cap, or exhaustive completion |
| Recommendation | Conservative Pareto, , no set-size cap |
| Search cost accounting | Token-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-k 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 [4].
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 , 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) and (1, 0), real per-configuration acquisition costs, independent direction-local decay, shared observations, and round-robin controller visits. The evaluation covers eight benchmarks and seeds 42–61. HotpotQA and MathQA use the complete 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 illustrate the recommended configurations and quality–cost estimates available to users under CC-GITTINS and the five baselines for seed 42.

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.

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

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 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 , we select the last recommendation event whose realized cost fraction does not exceed . 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 illustrate the recommended configurations and quality–cost estimates available to users, comparing CC-GITTINS with five baselines on 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. For CC-GITTINS, estimated coordinates are the full-benchmark posterior predictive means from Eq. (11); the baselines use means over their evaluated questions. The actual panels and exhaustive reference points and frontier serve only as retrospective references.
Controlled CC-Gittins Ablations
Protocol. We center four one-factor families and a prior-variance study (Figure 18) on G0, the CC-GITTINS protocol with real per-configuration acquisition costs, independent direction-local 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- 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.
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 ; the latter corresponds to raw cost variance 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 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 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 itself.
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 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 , where is the number of configurations and 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 and 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.
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 standard errors.
Relaxation. Figure 16 compares G0’s independent direction-local relaxation with the fixed- 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.
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- 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 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.
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 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 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 decay. The relaxation family compares G0 with fixed without Gittins stopping (G10). These identifiers refer to the three-objective controls throughout this section.

Figure 23. Three-objective prior-variance ablation on HotpotQA (top) and MathQA (bottom). Columns report HV regret, GD, and IGD (lower is better). The 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 in seconds squared and raw cost variance in USD squared. Prior means, observation noise, warm observations, and all other policy components are held constant. At 30%, G0 has low HotpotQA GD and zero 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 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 and 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 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. For the four-controller policy, using observed acquisition costs lowers HV regret and GD on both matrices at 30%. This result supports the real-cost pricing used by G0 to allocate its evaluation budget.

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%. The comparison isolates the effect of acquisition pricing on the four-controller policy. 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 standard errors.
Directions. Figure 20 compares how controller directions allocate evaluation effort. 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 . 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. At 30%, G0 has lower HV regret than each single-direction control on both matrices. Its four directions represent all three objective axes and the quality–latency interaction with fewer controllers than the six-direction variants, providing a compact main configuration.

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. All variants use real acquisition costs; curves show seed means and bands show standard errors.
Figure 21 compares policy computation at an equal number of evaluated entries. G0 takes 13.3 seconds on HotpotQA and 12.5 seconds on MathQA, within the 10.0–15.0-second range of the tested direction sets. Together with its low HV regret at 30% of evaluation cost (Figure 20), this runtime supports using four directions as the main three-objective configuration.

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.3 seconds on HotpotQA and 12.5 seconds on MathQA, within the 10.0–15.0-second range across all tested variants. The four-controller policy remains within the runtime range of the tested direction sets. For every benchmark and matched seed, all seven variants evaluate exactly entries ( configurations and 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 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 isolates the continuation rule under the same four controllers and round-robin schedule. G0 independently relaxes each direction’s evaluation-cost penalty after local stopping signals, whereas G10 holds fixed. This direction-local adaptation retains the stopping behavior used by the main anytime policy; the curves show how the alternative continuation rules affect the three frontier metrics on each benchmark.

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 and is halved after a local stopping signal when further relaxation is allowed. G10 holds fixed without local Gittins stopping. The curves compare the resulting volume recovery, recommendation proximity, and frontier coverage under the same evaluation protocol. Both policies use equal-frequency round-robin visits; curves show seed means and bands show standard errors.
Cost-mechanism curves
Direction curves
Relaxation curves
Prior-variance curves
References
- [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]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]Samuel Daulton, Maximilian Balandat, and Eytan Bakshy. Differentiable expected hypervolume improvement for parallel multi-objective Bayesian optimization. In Advances in Neural Information Processing Systems, volume 33, pp. 9851–9864, 2020. URL https://papers.neurips.cc/paper_files/paper/2020/hash/6fec24eac8f18ed793f5eaad3dd7977c-Abstract.html.
- [4]Samuel Daulton, Maximilian Balandat, and Eytan Bakshy. Parallel Bayesian optimization of multiple noisy objectives with expected hypervolume improvement. In Advances in Neural Information Processing Systems, volume 34, pp. 2187–2200, 2021. URL https://proceedings.neurips.cc/paper/2021/hash/11704817e347269b7254e744b5e22dac-Abstract.html.arxiv.org/abs/2105.08195
- [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
- [6]Wenyue Hua, Sripad Karne, Qian Xie, Armaan Agrawal, Nikos Pagomas, 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
- [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/3730855.3818067.DOI
- [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
- [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
- [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
- [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
- [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
- [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
- [14]Zifan Lyu, Chahine Nejma, Tobias Wegel, Fanny Yang, and Florian E. Dorner. Cutting LLM evaluation costs with SyRSRs: A bandit algorithm that provably exploits model similarity. In International Conference on Machine Learning, 2026.arxiv.org/abs/2606.07726
- [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
- [16]Nikos Pagonas, Matthew Lou, Tianyi Peng, Dan Rubenstein, and Kostis Kaffes. VineLLM: Trie-based fine-grained control for agentic workflows. arXiv preprint arXiv:2605.23914, 2026.arxiv.org/abs/2605.23914
- [17]Felipe Maia Polo, Ronald Xu, Lucas Weber, Mírian 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
- [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.
- [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
- [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
- [21]Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, et al. SGLang: Efficient execution of structured language model programs. Advances in Neural Information Processing Systems, 37: 62557–62583, 2024. doi: 10.52202/079017-2000.DOI
- [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







