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%.
Figures & tables
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).
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.
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.
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.
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 standard errors.
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.
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.
Appendix figures & tables19 assets
Supplementary material from the paper’s appendix.
Appendix
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
Appendix
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.
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
Appendix
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.
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); C=1−D/R for acquisition
Directions (in visit order)
(0,1) cost, (1,0) quality
Scheduler
1:1 decision opportunities, shared observations
Multipliers
ηC=ηQ=1 ; independent halving
Appendix
Table 3: Two-objective CC-Gittins settings for the reported replay.
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.
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 Fig. 9 . Marker color gives recommendation frequency across 20 seeds; positions use exhaustive mean quality and deployment cost for retrospective comparison.
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.
Figure 12: Estimated and actual Pareto recommendations at the 30% search-cost checkpoint for seed 42, using the same layout and visual encoding as Fig. 11 . The paired columns separate checkpoint estimation error from the choice of recommended configuration identifiers.
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 standard errors.
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 (Fig. 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 standard errors.
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⌉ entries ( K configurations and N 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.
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 ±2 standard errors.
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.
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/R ; the latter corresponds to raw cost variance 0.04R2 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.
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 standard errors.
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 (Fig. 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 standard errors.
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 entries ( K=100 configurations and N=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 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.
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 and is halved after a local stopping signal when further relaxation is allowed. Compared with fixed- η=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 standard errors.
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×2 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.04T2 in seconds squared and raw cost variance 0.04R2 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 standard errors.
LLM agents are increasingly deployed as multi-role teams, where tasks are divided across specialized roles such as planner, executor, and verifier. In these systems, cost and accuracy are no longer properties of a single model: they depend on which model fills each role and where it is hosted, including API, self-hosted, and hybrid deployment. Existing agentic benchmarks typically evaluate fixed models or fixed agent configurations, and therefore offer limited guidance for cost-accuracy-optimal deployment. We introduce AgentCARD, a role-aware benchmark suite for evaluating LLM agent teams across role assignment and deployment mode. AgentCARD combines a role-decomposed evaluation harness, a unified API/self-hosted cost model, Pareto-frontier analysis, and a Shapley-based diagnostic for identifying role bottlenecks. Our evaluation shows that heterogeneous teams consistently occupy the cost-accuracy frontier. They improve accuracy by up to 44% over cost-equivalent homogeneous teams, or match the strongest homogeneous team at up to 12× lower per-task cost through hybrid deployment. We further find that the best role assignment is domain-dependent: some domains are planner-bottlenecked, while others are executor-bottlenecked. Finally, AgentCARD extends beyond planner--executor teams to workflows with additional roles such as verification, and supports continual evaluation as new domains and team structures emerge. Our code is released at: https://github.com/Auto-CAP/AgentCAP
Modern AI systems increasingly rely on workflows composed of multiple interacting agents, some powered by large language models (LLMs) and others by conventional computational modules. This paper analyzes the fundamental tradeoffs between latency, reliability, and cost in LLM-enabled agentic workflows. We introduce performance models for both LLM and non-LLM agents that capture the relationship between computational effort and output quality, incorporating the impact of reasoning and output tokens for LLM agents using a parametric exponential reliability function. Then, we study the design of sequential workflows under latency and cost constraints. Main results include a water-filling token allocation policy and characterizations of optimal workflow reliability in terms of shadow prices.
A company with a fixed artificial intelligence (AI) budget must decide which large language model (LLM) handles each recurring workload. What it lacks is the quality table, how well each model performs on each workload. Given that table, the decision is a multiple-choice knapsack problem and is routine to solve, so estimating it is the difficulty, and that estimation fails in two ways. Models are rarely compared on the same work, and the recorded score is usually a proxy rather than the outcome the company values. Causal and off-policy methods repair the first but condition on the second, while evaluator-validation methods estimate the second but stop short of the decision. Worse, buying more re-evaluation cannot settle the second: randomization governs which requests are scored, not how a score is produced, so the table stays uncertain however much evaluation is purchased. Yet the deployment decision may still be determined even when the table is not. We therefore ask whether one assignment stays optimal across every quality table consistent with the evidence. For the fixed-budget problem, this admits an exact two-solve certificate: solve once at the estimated table and once at a least-favourable table. Agreement certifies the assignment; disagreement identifies the model-workload pairs where further evidence can matter. We propose CASE (causal active sequential experimentation), which targets evaluation to those pairs and repeats the test as evidence accumulates. On a production log, the measurement failure is the larger of the two: correcting assignment exactly still leaves most of the loss, and randomized re-evaluation does not remove it. In our experiments, the available evidence often does not determine the assignment. On paid software tasks, better information about model quality yields more savings than further optimization of the assignment on the same estimates.
Hamed Khosravi, Xiaoming Huo
H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332