비용 고려형 다목적 방랑자 알고리즘: 이론 및 예산 제한 환경에서의 대규모 언어 모델 구성 평가 적용

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

대규모 언어 모델(LLM)의 구성 평가는 제한된 평가 예산, 다양한 비용, 그리고 여러 가지 상충되는 목표로 인해 어려운 과제입니다. 본 논문에서는 LLM 구성 평가를 비용을 고려한 다목적 방랑자 문제로 정의합니다. 여기서 각 구성 평가는 구성에 따라 달라지는 비용이 발생하며, 노이즈가 섞인 벡터 형태의 결과를 제공합니다. 이러한 프레임워크 하에서 우리는 온라인 구성 선택과 파레토 최적 구성 식별이라는 두 가지 중요한 문제를 연구합니다. 온라인 구성 선택을 위해, 우리는 낙관적인 초부피(hypervolume) 대비 비용 지표를 최적화하는 초부피 기반 UCB 알고리즘을 제안합니다. 제안된 알고리즘은 평가 예산 $B$, 초부피 효율성 측면에서 최적인 구성 $i^ oline{*} $, 그리고 구성 $i$의 해당 효율성 격차 $Δ_i$에 대해, $Oigl(rac{ ext{log } B}{ ext{Δ}_i}igr)$ 크기의 예산 기반 후회 경계를 갖습니다. 이 경계는 고전적인 단일 목적 방랑자 알고리즘의 로그형 예산 의존성을 유지합니다. 또한, 고정된 예산을 사용하여 파레토 최적 집합을 식별하기 위해 비용을 고려한 경험적 격차 제거 알고리즘을 개발하고, 그 오류 확률이 $Oigl( ext{exp}(-rac{B}{H_{μ,c}})igr)$의 크기를 가짐을 증명합니다. 여기서 $H_{μ,c}$는 구성 비용과 파레토 분류 격차에 따라 결정되는 비용을 고려한 파레토 식별 복잡도입니다. 이 오류 확률은 평가 예산에 대해 지수적으로 감소하며, 모든 구성 비용이 동일한 경우 표준적인 파레토 집합 식별 보장으로 회귀합니다. 실제 LLM 구성 평가 작업에서 수행된 실험 결과는 제안된 프레임워크가 제한된 예산 하에서 효율적인 온라인 의사 결정과 정확한 비용을 고려한 파레토 최적 구성 식별을 가능하게 함을 보여줍니다.

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.