# Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation

arXiv: https://arxiv.org/abs/2608.04333 · HTML: https://mlsanity.com/paper/2608.04333/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 44 references that are in the map.
- First posted on arXiv 5 Aug 2026.

## Builds on (most cited first, 30 of 32)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [PIQA: Reasoning about Physical Commonsense in Natural Language](https://mlsanity.com/paper/1911.11641/) (2019)
- [A Survey on Evaluation of Large Language Models](https://mlsanity.com/paper/2307.03109/) (2023)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [From Generation to Judgment: Opportunities and Challenges of LLM-as-a-judge](https://mlsanity.com/paper/2411.16594/) (2024)
- [A Survey on Efficient Inference for Large Language Models](https://mlsanity.com/paper/2404.14294/) (2024)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [A Thorough Examination of Decoding Methods in the Era of LLMs](https://mlsanity.com/paper/2402.06925/) (2024)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization](https://mlsanity.com/paper/2006.04655/) (2020)
- [Resourceful Contextual Bandits](https://mlsanity.com/paper/1402.6779/) (2014)
- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)
- [Prompt Optimization with EASE? Efficient Ordering-aware Automated Selection of Exemplars](https://mlsanity.com/paper/2405.16122/) (2024)
- [Use Your INSTINCT: INSTruction optimization for LLMs usIng Neural bandits Coupled with Transformers](https://mlsanity.com/paper/2310.02905/) (2023)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [Thompson Sampling for Budgeted Multi-armed Bandits](https://mlsanity.com/paper/1505.00146/) (2015)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [Online Multi-LLM Selection via Contextual Bandits under Unstructured Context Evolution](https://mlsanity.com/paper/2506.17670/) (2025)
- [Sample-Efficient Human Evaluation of Large Language Models via Maximum Discrepancy Competition](https://mlsanity.com/paper/2404.08008/) (2024)
- [Adaptive Algorithms for Relaxed Pareto Set Identification](https://mlsanity.com/paper/2307.00424/) (2023)
- [On Speeding Up Language Model Evaluation](https://mlsanity.com/paper/2407.06172/) (2024)
- [Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2407.17466/) (2024)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Bandit Pareto Set Identification: the Fixed Budget Setting](https://mlsanity.com/paper/2311.03992/) (2023)
- [Bandit-Based Prompt Design Strategy Selection Improves Prompt Optimizers](https://mlsanity.com/paper/2503.01163/) (2025)

## Built on by (most cited first, 3 of 3)

- [Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices](https://mlsanity.com/paper/2609.25645/) (2026)
- [Few-for-Many Best-Arm Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2610.16840/) (2026)
- [When More Objectives Make Identification Easier: The Role of Preferences and Feedback](https://mlsanity.com/paper/2610.18577/) (2026)

## Abstract (arXiv)

Large language model (LLM) configuration evaluation is challenging due to limited evaluation budgets, varying costs, and multiple competing objectives. In this paper, we formulate LLM configuration evaluation as a cost-aware multi-objective bandit problem, where each configuration evaluation incurs a configuration-dependent cost and yields a noisy vector-valued outcome. Under this framework, we study two fundamental problems: online configuration selection and Pareto configuration identification. For online configuration selection, we propose a hypervolume-based UCB algorithm that optimizes an optimistic hypervolume-per-cost index. We establish a budgeted regret bound of order Obigl(sumine i^starfraclog BDeltaibigr), where B is the evaluation budget, i^star is the optimal configuration in terms of hypervolume efficiency, and Deltai is the corresponding efficiency gap of configuration i. This bound retains the logarithmic budget dependence of classical single-objective budgeted bandits. For fixed-budget Pareto identification, we develop a cost-aware empirical gap elimination algorithm and prove that its error probability is of order Obigl(exp(-fracBHμ,c)bigr), where Hμ,c is a cost-aware Pareto identification complexity depending on configuration costs and Pareto classification gaps. This error probability decays exponentially with the evaluation budget and recovers the standard Pareto set identification guarantee when all configuration costs are identical. Experiments on LLM configuration evaluation tasks demonstrate that the proposed framework enables efficient online decision-making and accurate cost-aware Pareto identification under limited budgets.