Technical Summary: Cost-Aware Multi-Objective Bandits for LLM Configuration Evaluation

1. Problem Formulation

The paper addresses the challenge of evaluating Large Language Model (LLM) configurations under limited budgets. In practical scenarios, selecting optimal configurations (e.g., base models, prompt templates, decoding parameters) involves balancing multiple competing objectives—such as task accuracy, latency, and robustness—while incurring varying evaluation costs. These costs arise from token consumption, API fees, or human annotation efforts, which differ significantly across configurations.

The authors formulate this challenge as a cost-aware multi-objective bandit problem with a finite evaluation budget $B$. The problem is defined by two complementary learning objectives:

1. Online Configuration Selection: Minimizing regret over time by adaptively selecting configurations to maximize cumulative utility per unit cost.
2. Pareto Configuration Identification: Identifying the set of non-dominated (Pareto-optimal) configurations within a fixed budget.

The framework models each configuration as an arm that yields a stochastic vector-valued reward $\mathbf{r}_{i,t} \in [0,1]^D$ and incurs a configuration-dependent cost $c_{i,t}$. Unlike prior work, this formulation explicitly accounts for the trade-off between multi-objective performance and the heterogeneous costs of evaluation.

2. Methodology

The paper proposes two distinct algorithms tailored to the two learning objectives:

A. CoHV-UCB: Cost-Aware Hypervolume UCB (Online Selection)

For the online selection problem, the authors propose CoHV-UCB, an algorithm based on the "optimism-in-the-face-of-uncertainty" principle.

• Mechanism: The algorithm constructs an optimistic reward vector $\mathbf{U}_{i,t}$ for each configuration using upper confidence bounds. It then computes a hypervolume-per-cost index:
  $$I_{i,t} = \frac{HV(\mathbf{U}_{i,t})}{\underline{c}_{i,t}}$$
  where $HV(\cdot)$ is the hypervolume indicator (measuring multi-objective quality) and $\underline{c}_{i,t}$ is a lower confidence bound on the expected evaluation cost.
• Cost Handling: To prevent the index from being artificially inflated by underestimating costs, the algorithm uses a truncated lower confidence bound for the cost denominator, ensuring it remains bounded away from zero.
• Selection: At each round, the configuration with the highest index is selected until the budget is exhausted.

B. CoPSI: Cost-Aware Pareto Set Identification (Fixed Budget)

For the fixed-budget identification problem, the authors propose CoPSI, a successive-rejects algorithm that allocates samples based on configuration costs.

• Mechanism: The algorithm operates in phases. In each phase, it maintains an active set of configurations and computes a sampling target $n_r$ proportional to the inverse of the total cost of the active set.
• Gap-Based Elimination: It computes empirical Pareto gaps ($\hat{\gamma}_{i,r}$) for active configurations. These gaps measure the empirical evidence for a configuration being either dominated or Pareto-optimal.
• Strategy: The algorithm identifies the configuration with the largest empirical classification gap and removes it from the active set (accepting it as Pareto-optimal or rejecting it as dominated). This process continues until only one configuration remains, which is included in the final output.
• Cost Awareness: The sampling target in each phase is explicitly adjusted based on the aggregate cost of the remaining active configurations, ensuring the budget is utilized efficiently.

3. Theoretical Contributions

The paper establishes rigorous theoretical guarantees for both algorithms:

• Regret Bound for CoHV-UCB: The authors prove that the hypervolume-efficiency regret is bounded by:
  $$O\left(\sum_{i \neq i^*} \frac{\log B}{\Delta_i}\right)$$
  where $B$ is the budget, $i^*$ is the optimal configuration in terms of hypervolume efficiency, and $\Delta_i$ is the efficiency gap. This bound retains the logarithmic dependence on the budget found in classical single-objective budgeted bandits.

• Error Probability for CoPSI: For fixed-budget identification, the probability of misidentifying the Pareto set is bounded by:
  $$O\left(\exp\left(-\frac{B}{H_{\mu,c}}\right)\right)$$
  where $H_{\mu,c}$ is a cost-aware complexity measure depending on configuration costs and Pareto classification gaps. This result shows that the error probability decays exponentially with the budget and recovers standard Pareto set identification guarantees when all costs are identical.

4. Experimental Results

The authors evaluate their methods on LLM configuration tasks using the GSM8K and PIQA datasets. Configurations involve various models, temperatures, and prompting strategies, with objectives including accuracy and normalized inverse latency.

• Online Selection: CoHV-UCB significantly outperforms baselines (including cost-insensitive HV-UCB and single-objective Accuracy-Cost-UCB). On the PIQA dataset, CoHV-UCB reduced hypervolume-efficiency regret by 83.2% compared to uniform allocation. The results highlight that accounting for cost dispersion is crucial when the configuration maximizing raw performance differs from the one maximizing efficiency.
• Pareto Identification: CoPSI demonstrates superior performance in identifying the Pareto set compared to uniform allocation and cost-insensitive successive-rejects (PSI-SR). On GSM8K, CoPSI reduced the identification error probability by 84.6% relative to uniform allocation at the largest budget. The experiments confirm that cost-aware sampling allows the algorithm to concentrate resources on ambiguous configurations near the Pareto boundary.

5. Significance and Claims

The paper claims to be the first study of cost-aware multi-objective bandits. Its primary significance lies in bridging the gap between theoretical bandit frameworks and the practical constraints of LLM evaluation, where:

1. Costs are heterogeneous: Evaluation costs vary significantly based on model size and prompting strategies.
2. Objectives are multi-dimensional: Practitioners must balance accuracy, latency, and efficiency simultaneously.
3. Budgets are limited: Exhaustive evaluation is computationally and financially prohibitive.

The authors assert that their framework enables efficient online decision-making and accurate cost-aware Pareto identification. By jointly optimizing for performance and cost, the proposed methods allow practitioners to extract more value from limited evaluation budgets, avoiding the pitfalls of strategies that ignore cost variations or focus on single objectives. The work provides a principled foundation for adaptive LLM evaluation, moving beyond static benchmarking toward resource-efficient, multi-criteria optimization.