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

• URL: http://arxiv.org/abs/2608.04333v1
• Date: Wed, 05 Aug 2026 01:21:02 GMT
• Title: Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation
• Abstract summary: We formulate large language model (LLM) configuration evaluation as a cost-aware multi-objective bandit problem.<n>For online configuration selection, we propose a hyper-based UCB algorithm that optimize an optimistic hypervolume-per-cost index.<n>Experiments on LLM configuration evaluation tasks demonstrate that the proposed framework enables efficient online decision-making.
• Score: 23.566982511686096
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $O\bigl(\sum_{i\ne i^\star}\frac{\log B}{Δ_i}\bigr)$, where $B$ is the evaluation budget, $i^\star$ is the optimal configuration in terms of hypervolume efficiency, and $Δ_i$ 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 $O\bigl(\exp(-\frac{B}{H_{μ,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.

Related papers

• Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity [68.54852541944625]
  Black-box optimization is applied when gradients are unavailable and objective evaluations rely on expensive simulations.<n>We show how the choice of oracle type, noise model, and optimization scheme induces explicit wall-clock-optimal choices for the algorithmic parameters.
  arXiv  Detail & Related papers  (2026-05-29T14:24:54Z)
• Instance-Optimal Estimation with Multiple LLM Judges on a Budget [84.31744861038106]
  We formalize this question as *budgeted heteroskedastic multi-judge estimation*.<n>Given $K$ prompt-response pairs, $J$ judges with known costs, and unknown query-judge variances, the goal is to estimate a bounded score vector while minimizing an $ell_p$-error.<n>We prove that EST-IVWE matches the oracle IVWE rate up to lower-order terms in the budget.
  arXiv  Detail & Related papers  (2026-05-22T08:26:08Z)
• Model Compression with Exact Budget Constraints via Riemannian Manifolds [39.54576236079211]
  Assigning one of K options to each of N groups under a total cost budget is a recurring problem in efficient AI.<n>We present a new approach by showing that, under softmax relaxation, the budget constraint defines a smooth Riemannian manifold in logit space with unusually simple geometry.<n>Building on these properties, we propose Riemannian Constrained Optimization (RCO), which augments a standard Adam step with tangent projection, binary-search retraction, and momentum transport.
  arXiv  Detail & Related papers  (2026-05-01T13:30:23Z)
• Budget-Aware Routing for Long Clinical Text [8.474809035213118]
  Key challenge for large language models is token cost per query and overall deployment cost.<n>We study budgeted context selection, where a subset of document units is chosen under a strict token budget.<n>We propose textbfRCD, a monotone submodular objective that balances relevance, coverage, and diversity.
  arXiv  Detail & Related papers  (2026-05-01T01:34:53Z)
• Cost-Aware Learning [72.31444819326795]
  We consider the problem of Cost-Aware Learning, where sampling different component functions incur different costs.<n>We propose the Cost-Aware Descent algorithm for convex functions, and derive its cost complexity to attain an error of $$.<n>We introduce Cost-Aware GRPO, an algorithm designed to reduce the cost of policy optimization while preserving performance.
  arXiv  Detail & Related papers  (2026-04-30T15:39:09Z)
• Learning Query-Aware Budget-Tier Routing for Runtime Agent Memory [56.0946692457838]
  BudgetMem is a runtime agent memory framework for explicit, query-aware performance-cost control.<n>A lightweight router performs budget-tier routing across modules to balance task performance and memory construction cost.<n>Across LoCoMo, LongMemEval, and HotpotQA, BudgetMem surpasses strong baselines when performance is prioritized.
  arXiv  Detail & Related papers  (2026-02-05T18:57:09Z)
• Controlling Performance and Budget of a Centralized Multi-agent LLM System with Reinforcement Learning [53.57360296655208]
  Large language models (LLMs) exhibit complementary strengths across domains and come with varying inference costs.<n>Existing approaches rely on decentralized frameworks, which invoke multiple LLMs for every input and thus lead to substantial and uncontrolled inference costs.<n>We introduce a centralized multi-LLM framework, where a controller LLM selectively coordinates a pool of expert models in a cost-efficient and cost-controllable manner.
  arXiv  Detail & Related papers  (2025-11-04T17:35:17Z)
• Scalable Neural Incentive Design with Parameterized Mean-Field Approximation [28.20524168049273]
  We show that when dynamics and rewards are Lipschitz, the finite-$N$ ID objective is approximated by the PMFG at rate $mathscrO(frac1sqrtN)$.<n>We further introduce our Adjoint Mean-Field Incentive Design (AMID) algorithm, which uses explicit differentiation of iterated equilibrium operators to compute gradients efficiently.
  arXiv  Detail & Related papers  (2025-10-24T13:18:54Z)
• Cost-aware Stopping for Bayesian Optimization [46.95172329282389]
  We propose a cost-aware stopping rule for Bayesian optimization that adapts to varying evaluation costs and is free of tuning.<n>We prove a theoretical guarantee bounding the expected cumulative evaluation cost incurred by our stopping rule when paired with state-of-the-art acquisition functions.
  arXiv  Detail & Related papers  (2025-07-16T17:54:14Z)
• Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs [3.1269598124014264]
  We propose a novel algorithm for the extension of the BOCVS problem with random and unknown costs.<n>Our algorithm achieves a sub-linear rate in both quality regret and cost regret, addressing the objective of the BOCVS problem more effectively than previous analyses.
  arXiv  Detail & Related papers  (2024-12-20T13:00:39Z)
• Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits [8.013444110633223]
  We analytically derive a class of optimal solutions to a linear program (LP) for automated mechanism design.<n>These solutions can be expressed using a set of essential variables whose cardinality is exponentially smaller than the total number of variables in the original formulation.<n>We address this by translating the evaluation of this term into a multi-armed bandit (MAB) problem.
  arXiv  Detail & Related papers  (2024-11-30T03:59:36Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning. Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system. The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
  arXiv  Detail & Related papers  (2022-06-14T08:14:14Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  We consider the problem of discovering $K related Gaussian acyclic graphs (DAGs) Under multi-task learning setting, we propose a $l_1/l$-regularized maximum likelihood estimator (MLE) for learning $K$ linear structural equation models. We theoretically show that the joint estimator, by leveraging data across related tasks, can achieve a better sample complexity for recovering the causal order.
  arXiv  Detail & Related papers  (2021-11-03T22:10:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.