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

AI summary

Overview

Research area: Machine learning systems — specifically, model selection and configuration optimization for multi-role LLM agentic workflows, combining multi-objective bandit search with cost-aware evaluation.

Technical level: Intermediate (the core idea is intuitive; the Gittins-index dynamic programming and posterior calibration in the appendices are Advanced).

Scope: The paper introduces CC-Gittins, a multi-objective, cost-aware search method that recommends a spread of quality–cost trade-offs across complete LLM agent role assignments while spending only a fraction of the cost of evaluating every assignment.

What This Paper Is About

An LLM agent workflow often splits work across roles — planning, solving, searching, verification — and each role can use a different underlying model. Because one role's output feeds the next, you cannot judge a model in isolation: the whole assignment has to be run end to end. With several candidate models per role, the number of possible assignments grows multiplicatively (up to 1,681 in the paper's benchmarks), and evaluating each one on many queries is expensive.

The paper's goal is to recommend a useful range of quality-versus-deployment-cost trade-offs early and cheaply, without the user having to specify a final search budget or a preferred trade-off in advance. Its key observation is that deployment cost and evaluation cost are coupled: an assignment that is expensive to run is also expensive to test, since evaluating a batch of B queries costs roughly κ_i ≈ B·D_i, where D_i is mean deployment cost per query.

Key Contributions

1. Problem formulation. The authors frame model assignment in multi-role LLM workflows as anytime recommendation of a useful range of Pareto trade-offs obtained through costly end-to-end evaluations — rather than as single-objective optimization or one-shot exhaustive mapping.

2. The CC-Gittins method. A multi-objective extension of single-objective cost-aware Gittins search for anytime Pareto recommendation. Two controllers (quality-seeking and cost-seeking) take turns choosing which assignment to evaluate, share observations, and independently relax their evaluation-price multipliers. After each batch, the recommendation is the set of assignments nondominated under uncertainty-adjusted quality and deployment-cost estimates, so a user can stop at any point.

3. An evaluation harness and open response matrices. The authors implement a workflow evaluation harness in AgentOpt and collect complete response matrices recording task score (accuracy or F1), input and output token counts, token-derived API costs, and end-to-end latency for each workflow execution — enabling reproducible offline replay against exhaustive Pareto frontiers.

4. Empirical results across eight benchmarks. Across eight quality–cost workflow benchmarks (two to five roles, up to 1,681 candidate assignments), 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%. The method is also evaluated with latency as a third objective.

Main Findings

• Frontier recovery at a fraction of the cost: Across the eight 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%.

• Headline example on BIRD Dev: Figure 1 reports that at 90% lower evaluation cost than exhaustive evaluation, CC-Gittins recovers most of the BIRD Dev Pareto frontier with no false positives — 88.75% mean recall and 100% mean precision over 20 seeds.

• Near-complete recovery on Stack Overflow: CC-Gittins nearly recovers the entire frontier at 10% of exhaustive evaluation cost, with mean precision 0.97 and recall 0.98; both reach 1.00 at 30%.

• High precision can coexist with incomplete coverage: On HotpotQA, mean recall is 0.58 at 10% cost and 0.74 at 30%, while precision is 0.97 and 0.99 respectively. Low hypervolume regret and generational distance therefore do not imply broad frontier coverage.

• Competitive but not dominant: At matched search costs up to 30% of exhaustive evaluation, CC-Gittins is generally competitive with the five baselines in hypervolume regret and generational distance. It does not consistently outperform them on inverted generational distance — competing methods achieve lower IGD on some benchmarks.

• Ablation on cost mechanism: 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 the eight benchmarks among the cost-mechanism controls. Independent price relaxation lowers average HV regret, GD, and IGD relative to fixed-η continuation.

• Two controllers are also the cheaper design: At matched evaluation counts, the two-axis design's mean policy runtime is lower than the tested three- and five-controller variants on all eight benchmarks (Fig. 15, Appendix J).

• Weighted scores cover most of the dominated volume: Across all eight benchmark matrices, the supported subset of the frontier loses less than 0.10% of full-frontier hypervolume despite omitting some Pareto points — a full-information oracle result, not a guarantee for CC-Gittins under limited search cost.

• Three-objective extension works but coverage lags: With latency added on HotpotQA and MathQA, the four-controller policy shows low HV regret and GD, but several baselines achieve lower IGD over substantial search-cost ranges.

• Stated limitations: Complete frontier recovery is not guaranteed; the uncertainty-adjusted scores are not a simultaneous or time-uniform confidence certificate; and single-objective Gittins results do not establish Bayes optimality for the full multi-objective search.

Methodology in Plain English

Setup. Fix the workflow's role structure and orchestration, then vary which model fills each role. Each complete assignment is one "configuration" to be evaluated; the whole workflow is the unit of evaluation because role outputs affect later roles.

Exploiting cost coupling. Evaluating a batch of B queries for configuration i costs roughly κ_i ≈ B·D_i, using that configuration's mean deployment cost per query. Expensive-to-deploy configurations are therefore expensive to learn about, and the search prices that in.

Two alternating controllers. A quality controller and a cost controller take turns, in the order cost then quality. Each scores configurations with a cost-aware Gittins index — intuitively, an optimism-adjusted value that already subtracts the price of buying more evidence. The quality controller's index ranks a quality-minus-cost-penalty scalarization; the cost controller's index ranks configurations by increasing deployment cost. Both share a single posterior, so every evaluation informs both searches.

Price relaxation instead of hard stopping. If a controller would rather stop than pay the current evaluation price, it halves only its own price multiplier η_a (initially one), making further evaluations cheaper in its index. Actual API charges are unaffected and the other controller's multiplier is untouched. The search ends when both controllers hit stopping conditions that cannot be relaxed without an intervening evaluation, an external budget is reached, or all configurations are complete.

Recommendations from uncertainty-adjusted scores. For the fixed N-question benchmark, the method predicts each configuration's full-benchmark mean and variance from the n queries observed so far. It then reports a quality lower confidence bound (mean minus β·standard deviation) and a cost upper confidence bound (mean plus β·standard deviation), with β = 1. Any configuration not dominated in this score space is recommended; partially evaluated configurations stay eligible, and there is no limit of one recommendation per controller. At exhaustive completion the recommended set equals the true benchmark frontier.

Testing. Evaluation is offline replay on fixed, complete score–cost matrices, so no new model API calls are made. The protocol uses four warm-up questions per configuration, batches of up to four unseen questions, and 20 matched question-order seeds (42–61), charging observed API costs including warm-up. Checkpoints are reported every 0.5 percentage points of exhaustive cost. Metrics are hypervolume regret, generational distance, and inverted generational distance.

Benchmarks and baselines. Eight quality–cost matrices span five workflow families: HotpotQA (planner and search-enabled solver) and MathQA (answerer and critic), each with 10² = 100 assignments over all 200 questions using ten candidate models via AWS Bedrock Application Inference Profiles, plus six SCOPE-derived three-to-five-role text-to-SQL, data-transformation, and data-integration instances. Baselines are EGE-SH, APE-k, qNEHVI, random questions, and random configurations.

Why This Matters

Impact on research. The paper reframes agent configuration search as an anytime, multi-objective problem whose search cost is itself tied to the objective being optimized — a coupling that standard Pareto bandit methods and hypervolume Bayesian optimization do not explicitly price. It also releases complete response matrices with quality, token counts, API cost, and latency, which supports reproducible offline replay and fair comparison at matched API spend.

Real-world applications

• Text-to-SQL and analytics assistants: choosing which model plans, writes, and validates queries so that most of the quality is retained at a fraction of the per-query API bill.
• Customer-support agent pipelines: routing, drafting, and verification roles can use cheaper models where their contribution is marginal and stronger models only where they measurably help.
• Research and document-analysis agents: planner/search/solver setups like the HotpotQA configuration, where both quality and latency affect perceived usefulness.
• Coding and data-transformation agents: multi-role workflows where a critic or transformer stage can be downgraded without losing end-to-end accuracy.

Industry relevance. Deployment teams generally have a cost ceiling and a quality bar but no single fixed trade-off, and they need an answer before the evaluation bill arrives. An anytime method that produces a nondominated recommendation set after every batch lets teams stop when the trade-off curve is informative enough, and the explicit per-configuration API pricing means the recommendation is expressed in the same currency as the budget.

Future Directions

• Dynamic rather than static assignments: the current method assumes fixed role-level model choices under fixed orchestration; the authors suggest future work could adapt model choices, retries, and execution paths to intermediate outcomes during a run.
• Better controller design: controller design remains empirical, additional controllers improve particular metrics without uniformly beating the two-axis design, and frontier coverage varies across benchmarks — leaving room for principled controller selection.
• Stronger coverage and confidence guarantees: complete frontier recovery is not guaranteed, and the LCB/UCB recommendation is not a simultaneous confidence certificate; tightening these would make recommendations more trustworthy at very low search cost.
• Extension to further objectives and settings: latency is demonstrated as a third objective on HotpotQA and MathQA; whether the same evaluation-price mechanism scales cleanly to more objectives or to new query distributions is not reported.

Target Audience

ML systems researchers and engineers working on LLM agent architecture, model routing, and inference-cost optimization; practitioners who must pick models per agent role under a budget; and readers interested in multi-objective bandit methods and cost-aware experimental design. The main text is accessible to someone familiar with LLM agents and basic multi-objective optimization, while the appendices on posterior calibration, index computation, and the deterministic price analysis are aimed at specialists.

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