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

What it claims

CC-Gittins is a search procedure for choosing which LLM serves each role in a multi-role agent workflow. It returns a set of Pareto-optimal assignments over task quality and deployment cost, with latency as an optional third objective. The recommendation updates after every evaluation batch, so the user does not have to fix a weighted trade-off or a search budget in advance. This is the difference from AgentOpt, which uses a fixed weighted-sum utility, and from SCOPE and VineLM, which optimize under a quality threshold or under cost and latency budgets. On BIRD Dev, at 10% of exhaustive-evaluation cost, it reaches 88.75% mean frontier recall and 100% mean precision over 20 seeds. The code is at github.com/AgentOptimizer/agentopt-research.

How it works

The method rests on the observation that evaluating a batch of B queries on assignment i costs roughly B times that assignment's per-query deployment cost. Expensive configurations are therefore also expensive to learn about. The steps are:

1. A warm-up fixes an estimated evaluation cost per assignment and a cost-scaling constant R.
2. Every assignment gets independent Gaussian posteriors on quality and deployment cost. Two controllers share these posteriors: a quality controller and a cost controller, which uses 1 − D/R.
3. Each controller ranks assignments with the cost-aware Gittins index of Xie et al. (2026). The evaluation price in that index is a multiplier η times the assignment's estimated evaluation cost.
4. The controllers alternate turns, cost first and then quality. On its turn, a controller evaluates one batch if an unfinished assignment beats its best completed value. Otherwise it halves only its own η, which lowers its future evaluation penalty.
5. After each batch, the recommendation is the set of assignments that are nondominated on quality lower confidence bound and cost upper confidence bound.

Search stops when neither controller can relax further, when an external budget runs out, or when every assignment is complete. When latency is added, extra controllers join and dominance becomes three-objective.

flowchart TD
  T[Controller turn: C then Q] --> D{Best unfinished index beats best completed value?}
  D -->|yes| E[Evaluate one batch]
  D -->|no| H[Halve this controller's η]
  E --> P[Update shared posteriors]
  P --> R[Recommend: nondominated on quality LCB, cost UCB]
  R --> T
  H --> T

Evidence

Evaluation is offline replay against complete response matrices. The matrices record task score (accuracy or F1), input and output tokens, token-derived API cost and end-to-end latency for every workflow run. There are eight benchmarks: full HotpotQA and MathQA assignment matrices plus six instances derived from SCOPE. They cover two to five roles and up to 1,681 assignments.

The paper compares CC-Gittins with five search baselines on hypervolume regret, generational distance and inverted generational distance, at matched cumulative API spend. The authors report competitive hypervolume regret and generational distance at low search cost. Frontier coverage varies across benchmarks. Latency is tested as a third objective on HotpotQA and MathQA only.

At matched evaluation counts, the two-controller design has lower mean policy runtime than the tested three- and five-controller variants on all eight benchmarks.

Limits

• The quality and cost targets are means on a fixed N-question benchmark. The authors state these do not guarantee performance on new queries or on a different query distribution.
• The metrics are averages or volumes. They give no worst-case guarantee for any single assignment or region of the frontier.
• The round-robin schedule balances controller turns. It does not balance evaluation counts or API spend.
• Evaluation cost is approximated from deployment cost. Actual charges vary with query difficulty, output length and batch size.
• All results come from offline replay of precomputed matrices, not from live search. The fetched text ends partway through Section 3.4, so the per-benchmark tables and ablation details were not available here.