Cost-Effective Online Multi-LLM Selection with Versatile Reward Models

Authors: Xiangxiang Dai, Jin Li, Xutong Liu, Anqi Yu, John C.S. Lui
Primary area: reinforcement learning
Keywords: Combinatorial multi-armed bandit, Online learning, Large language model, Long-term cost constraint

Abstract:
With the rapid advancement of large language models (LLMs),  the diversity of multi-LLM tasks and the variability in their pricing structures have become increasingly important, as costs can vary greatly between different LLMs. To tackle these challenges, we introduce the \textit{C2MAB-V}, a \underline{C}ost-effective \underline{C}ombinatorial \underline{M}ulti-armed \underline{B}andit with \underline{V}ersatile reward models for optimal LLM selection and usage.  This online model differs from traditional static approaches or those reliant on a single LLM without cost consideration. With multiple LLMs deployed on a scheduling cloud and a local server dedicated to handling user queries, \textit{C2MAB-V} facilitates the selection of multiple LLMs over a combinatorial search space, specifically tailored for various collaborative task types with different reward models. Based on our designed online feedback mechanism and confidence bound technique, \textit{C2MAB-V} can effectively address the multi-LLM selection challenge by managing the exploration-exploitation trade-off across different models, while also balancing cost and reward for diverse tasks. The NP-hard integer linear programming problem for selecting multiple LLMs with trade-off dilemmas is addressed by: i) decomposing the integer problem into a relaxed form by the local server, ii) utilizing a discretization rounding scheme that provides optimal LLM combinations by the scheduling cloud, and iii) continual online updates based on feedback. Theoretically, we prove that \textit{C2MAB-V} offers strict guarantees over versatile reward models,  matching state-of-the-art results for regret and violations in some degenerate cases. Empirically, we show that \textit{C2MAB-V} effectively balances performance and cost-efficiency with nine LLMs for three application scenarios.

Decision: reject
Reviewer scores: 6, 5, 6, 5

Reviews and discussion:
<thread>
creation date:
1730474688408

thread_type:
official_review

<thread_object>
creator: reviewer_xjc9

<content>
summary:
This paper investigates the problem of the selection of multiple large language models (LLMs) with versatile reward models in an online manner. A framework named C2MAB-V, i.e., a cost-effective combinatorial online model with a versatile reward structure, has been proposed to select multiple LLMs based on specific task and requirements while adhering to the budget constraint. The performance of C2MAB-V has been both analyzed theoretically and evaluated via experiments. On the theoretical side, both the regret and violation bounds are provided. On the numerical side, the performance of C2MAB-V has been evaluated with nine LLMs under various settings.

strengths:
- This paper studies a timely and interesting problem in the context of LLMs, in particular considering the selection of multiple LLMs with versatile reward models and in an online manner 
- A new framework named C2MAB-V, i.e., a cost-effective combinatorial online model with a versatile reward structure, has been proposed to select multiple LLMs based on specific task and requirements while adhering to the budget constraint.
- Both the regret and violation bounds for C2MAB-V have been provided.
- The performance of C2MAB-V is further evaluated via extensive experiments, e.g., including nine LLMs under various settings.

weaknesses:
- Despite the studied problem is timely and interesting, the intrinsic nature of the problem is not quite new. In other words, it is still a combinatorial online optimization problem but simply framed in a new LLM setting. 
- Likewise, the proposed online algorithm C2MAB-V is not much in difference with the exiting methods as mentioned in the related works. 
- The paper is very dense and sometimes hard to understand. For instance, it introduces three reward models, i.e., AWC, SUC, AIC. What are the fundamental differences between these models? What are the impacts on the algorithm designs and analysis? It is not quite clear and the analysis seems to only focus on one model, and not sure if you need to present all of them in the main paper. For instance, it may be better to just present AWC which has the regret analysis in Section 5, and then has a new section just to discuss the extension to SUC and AIC models with numerical evaluations. 

Minor:
- This paper is framed very densely and many spaces are squeezed. For instance, there is almost no space between lines 243 and 244.

questions:
- In section 3, a subset $S_t$ is selected from the available LLMs set $\mathcal{K}$. This is termed as an "action" and satisfies $|S_t|\leq K$. Right after that, $N=\max_{S\in\mathcal{S}}|S|$ is defined as the maximum number of LLMs that can be simultaneously active. What are the differences or the relations between $K$ and $N$? 
- This paper introduces three reward models, i.e., AWC, SUC, AIC. What are the fundamental differences between these models? What are the impacts on the algorithm designs and analysis? The performance analysis in Section 5 is only for AWC. What about the performance guarantees under SUC and AIC. If there is no such results, what's the point to present these models in Sections 3 and 4, which make the paper very dense and hard to follow. 
- For a budget constraint $\rho$, why does the definition of $V(T)$ require a max operator? In many constrained RL or constrained MDPs, the violation constraint is naturally defined without a max operator. Can you elaborate on this? 
- In Section 4.1, several relaxation strategies for LLM selection have been discussed. However, are the solutions to these relaxations feasible to the "original" problem defined in Section 3 with the constraint that must be satisfied? This may be obviously infeasible. Can you clarify how to further design the solutions on top of the solutions to these relaxation problems? 
- For the violation bound in Theorem 2, the right hand size of (8) has two terms, one in the order of $\mathcal{O}(\sqrt{K/T})$ and the other $\mathcal{O}(K/T)$. The authors claimed that the violation decreases at a rate of $\mathcal{O}(\sqrt{K/T})$. In addition, why "the overall violation is shown to be $\mathcal{O}(\sqrt{KT})$ as claimed in lines 457-458? 
- How tight is the upper bound in Theorem 1? The coefficient can be extremely large on the right hand size of (7) associated with the $T$ terms. similarly for the constant term $(K+1)r^*$ that is in the order of $(K+1)NL$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730838028445

thread_type:
official_review

<thread_object>
creator: reviewer_hptz

<content>
summary:
This paper introduces a model of Cost-effective Combinatorial Multi-armed Bandit with Versatile reward for the optimal selection of multiple large language models (LLMs). The proposed approach aims to manage the exploration-exploitation trade-off while balancing costs and rewards in a collaborative LLM setting, using an online learning framework. The paper provides a theoretical analysis of regret and budget violation bounds, demonstrating that the proposed approach C2MAB-V matches state-of-the-art results in certain degenerate cases. Empirical experiments validate its effectiveness in balancing cost-efficiency and performance across three scenarios with nine LLMs.

strengths:
1. The formulation of the problem as a cost-effective combinatorial multi-armed bandit with versatile reward models is interesting and applicable in real-world scenarios where cost-efficiency is crucial. The paper reads well and includes examples/intuition to help the reader.

2.  The authors provide a rigorous theoretical analysis of the regret and budget violations of the proposed algorithm, achieving results that match the state-of-the-art in several degenerate cases. Plus, the case-by-case analysis for different reward models provides enough insights about the discretization rounding procedure, which is crucial for understanding the proposed method.

3. The paper presents extensive empirical evaluations using various LLMs across three application scenarios, providing strong evidence for the proposed method's effectiveness.

weaknesses:
1. The algorithms and theoretical analysis presented are natural extensions of previous approaches, specifically in the combinatorial multi-armed bandit literature. Also, I do not believe that non-linear rewards pose a significant challenge for the analysis, as the paper assumes that the reward function is Monotone and Lipschitz. Therefore, the regret analysis can be converted to the accumulated impact of overestimating rewards, just as most of the literature does. Hence, I cannot give a score higher than 6 (accept).

2. Lines 1240-1241 contain content that seems unrelated to the context and should be revised or removed.

3. The literature on Combinatorial Multi-Armed Bandit with Knapsack Constraints is highly relevant to this paper's content, yet it has not been formally reviewed in Section 2.1 (Related Work). I highly recommend the authors Incorporate a formal review of these works in the revised paper.

questions:
1. I noticed that LLaMA 2 was used for comparison in the experiments, but LLaMA 3 has also been released. I am curious why there was no comparison with LLaMA 3 in the experiments.

2. When the reward function is linear, can instance-dependent performance bounds be derived based on a sub-optimality gap defined by the extreme points?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730954300895

thread_type:
official_review

<thread_object>
creator: reviewer_rm4a

<content>
summary:
This paper formulates the multi-LLM selection problem as a combinatorial bandit problem. The authors develop an online bandit algorithm for online multi-LLM selection where different types of reward modes are applied. Also, the authors consider a computational cost constraint on the LLM selection. The paper provides analysis for regret and constraint violation.  The performance is evaluated based on  the SciQ dataset.

strengths:
This paper has the following strengths:
+ This paper consider an interesting problem which selects LLM models on cloud. 
+ This paper provides good formulations for online LLM selection problem. Different reward models are considered. Budget constraint of the scheduling cloud is also modeled.
+ Performance analysis is provided for the combinatorial bandit problem.

weaknesses:
The paper can be improved in the following aspects.
- This paper considers the LLM selection problem. However the reward are modeled as some simple equations in page 5 and look like some toy models. These models cannot accurately reflect the real evaluation of combinatorial LLMs.
- The algorithm design is a simple extension of combinatorial bandits. The analysis of the algorithm also loos similar as the previous results on combinatorial bandits. It would be better if the authors can present the new challenges and techniques used in the algorithm and analysis.
- The empirical results are carried out for only one dataset.  Also, the choices of the parameters like budget threshold, $\alpha$, etc are not explained. This is not enough to verify the proposed algorithms.

questions:
Please see the questions above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731007174680

thread_type:
official_review

<thread_object>
creator: reviewer_wq9g

<content>
summary:
Main problem statement: the problem statement is clear and well-motivated (i.e. the setup of selecting a subset of LLMs/experts to answer a given query, in a cost and reward-sensitive environment. I do think combinatorial bandits are a reasonable way to model this problem, although I do have some nits about it which I’ll mention below).
Idea - the technical/intellectual contribution of the paper isn’t inherently about LLMs, in my opinion.I think the main idea is a new combinatorial bandit algorithm (which they dub C2MAB-V), which attempts to do exploration/exploitation and bandit-feedback updates in tandem with solving the submodular optimization described in Eq.3. I certainly have not seen this algorithm in the literature before, but I should caveat by saying that I am not an expert on combinatorial bandits. (As an aside, I do see a paper of Karthik’s referenced here on comb. bandits, so it may be worth getting his gut-check?) In addition to the new algorithm, the authors also derive a regret bound.
Novelty - Both the C2MAB-V and its regret analysis (Theorem 1) are novel as far as I (a non-expert) know.
Evaluation - the empirical evaluations are interesting and suggest that C2MAB-V does empirically outperform other “naive” alternatives such as always going with the best/most expensive model. I am curious to know why the y-axis in Fig 4 is reward / budget violation. The presence of the budget violation term there is a bit puzzling to me. Any feasible solution of (3) should be budget feasible and so budget should never really be violated (i.e. the denominator should always be zero)?
Benchmark - In Fig 4., evaluation is done against a good set of benchmarks including eps-greedy, Thompson sampling, and combinatorial UCB
Practical deployability?
I have some “weak” concerns about the practical “deployability” of the ideas proposed here in the context of LLMs. Some alternative ways that cost and performance tradeoffs may potentially be navigated for practical large-scale systems involve avoiding the appeal to MAB altogether, and its unclear whether this paper can prescribe into any insights about the relative merits of leveraging MAB versus other approaches. One such approach is Mixture-of-Experts (MoE) where the experts are directly absorbed as “sub-models” inside a larger model and the task of identifying which expert to direct a task to is also captured inside the model and learnt in the pre-training phase. Another approach is to appeal to “Composition of Experts (https://arxiv.org/pdf/2405.07518)”, where given some expert models, a new model is trained to learn to route a given task to the best set of experts. Based on this paper, can we draw any conclusions vis-a-vis MoE vs CoE vs MAB-combination of different LLMs?
One other deployability challenge that I see (and I don’t think was adequately addressed in the paper) is the contextual nature of the problem. Given a task, it seems to me that the context for that task (e.g. the required expertise e.g. medicine vs biology vs math) is needed to meaningfully identify the potential reward and also cost, and we’d need the bandit feedback to be contextual. In the method described by the authors, it is unclear whether and how the context is captured. I do believe the regret analysis itsef would also change substantially based on whether the algorithm describes a non-contextual vs a contextual implementation (since uncertainty quantification is far more nuanced in the contextual setup)

strengths:
I think the core explore-exploit algorithm that was introduced is new (to this reviewer), interesting, and also comes with potentially new regret guarantees.

weaknesses:
I have some concerns about the practical deployability of the approach.

questions:
No direct questions, but I welcome responses from the authors on the deployability and other aspects raised above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731991147971

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We sincerely thank all the reviewers for their thoughtful feedback and valuable comments on our paper. We have addressed the suggestions by incorporating revisions, detailed in the **revised manuscript PDF**. Newly added sections and modifications are highlighted in **blue** for easy reference. Additionally, to clarify common concerns regarding the novel challenges and techniques in our combinatorial multi-armed bandit approach, we would like to provide the following statement.

---

**Regarding  the new challenges and techniques used in the algorithm and analysis**:

We acknowledge that the problem we study falls within the broader context of combinatorial online optimization, but it presents several novel aspects that distinguish it from existing work. To our knowledge, we are the first to study the CMAB problem with **long-term constraints** for **general reward functions** and **partial feedback models**. Additionally, we propose a **unified and computationally efficient solution** using the **relaxation and rounding (RR) approach** that provides both **regret** and **violation guarantees**.

The key innovation of our approach lies in its formulation of **constraint-effective combinatorial multi-armed bandits**, a new variant of combinatorial semi-bandits. While previous CMAB research has made significant progress in minimizing regret, many existing approaches overlook the critical aspect of **cost constraints**, often allowing for excessive violations. Our work directly addresses this gap by adopting a **constraint-effective** perspective, where we aim to minimize both **regret** and **constraint violation** simultaneously. 

*Solving Constrained Optimization with Relaxation and Rounding*: 

A distinguishing feature of our work is the way we tackle the constrained optimization problem. Traditional methods typically treat the constraint as a **discrete** optimization problem, which is often NP-hard and computationally inefficient. Direct solutions to this problem tend to yield suboptimal approximation ratios. In contrast, we propose a **relaxation and rounding (RR)** technique, which transforms the problem into a **continuous** optimization problem. This transformation not only improves approximation guarantees but also offers better time complexity compared to traditional methods. 

*Tackling Online Challenges with RR Techniques*:

However, implementing RR techniques in an **online setting** presents new challenges, as RR methods were originally designed for **offline** optimization problems. The flexibility in choosing relaxation functions and rounding procedures complicates the guarantee of low regret and low violation in the online case. To overcome this challenge, we propose a detailed analysis that identifies the conditions under which the RR approach can effectively perform in online scenarios. This involves establishing a connection between regret and over-estimation terms, i.e., $ \mathbb{E}\left[\tilde{r}\left(\tilde{\boldsymbol{Z}}\_t, \bar{\boldsymbol{\mu}}\_t\right)-\mathbb{E}\left[\tilde{r}\left(\mathbb{I}\_{S\_t}, \bar{\boldsymbol{\mu}}\_t\right)\right]\right]+\mathbb{E}\left[r\left(S\_t, \bar{\boldsymbol{\mu}}\_t\right)-r\left(S\_t, \boldsymbol{\mu}\right)\right]$, where only the second term can be bounded using standard CMAB  analysis. 

*Addressing Complex Reward Models in Multi-LLM Tasks*:

The complexity of multi-LLM tasks introduces additional challenges due to non-linear reward models. Specifically:  1) **Non-linear reward** cannot be relaxed using a simple concave function. Instead, we model it as a **submodular function** and use its **multi-linear extension**; 2) Ensuring the quality of an action in expectation requires us to introduce a **randomized swap rounding procedure** tailored for non-linear rewards. This ensures that the rounded solution maintains the desired **convexity properties**, i.e., $\mathbb{E}\left[\tilde{r}\left(\mathbb{I}\_{S\_t}, \boldsymbol{\mu}\right)\right] \geq \tilde{r}(\tilde{\boldsymbol{Z}}\_t, \boldsymbol{\mu})$.

*Ensuring Long-term Constraint Satisfaction*:

Additionally, we use a novel **martingale construction** technique to bound long-term violations, which is essential for addressing constraints in online combinatorial optimization.

We have added a detailed discussion of the challenges and techniques used in the algorithm and analysis in **Appendix A.3**. Additionally, we provide a unified **instance-dependent** performance bound for diverse reward models in **Appendix D.4**, addressing the key limitation where **expectation-based analysis** overlooks crucial **action-dependent terms** needed for instance-dependent guarantees.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732460021611

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Expanded Evaluation Across Diverse Datasets

comment:
Dear Reviewers,  


We have extended our empirical evaluation to include multiple publicly available datasets and the LLaMA 3 model, aiming to validate the robustness of our approach across diverse deployment settings. The latest experimental results are detailed in **Appendix E.4**.  

For your convenience, all changes have been highlighted in blue. We hope these revisions effectively address your comments and enhance the manuscript. 

Please do not hesitate to let us know if further clarification or additional adjustments are required.  

Thank you once again for your valuable and constructive feedback.  

Best regards,  
The Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes a new algorithm for selecting a subset of large language models (LLMs) to answer a given query, considering both cost and reward. The algorithm, called C2MAB-V, is based on combinatorial bandits and attempts to balance exploration and exploitation while solving a submodular optimization problem. The paper also derives a regret bound for the algorithm.


The problem statement is clear and well-motivated, and the use of combinatorial bandits is a natural approach to address the trade-off between cost and reward (WQ9G, hptZ) in this setup. The paper provides a regret bound for the algorithm (WQ9G, hptZ), which involves a number of novel moving parts. The empirical evaluations are interesting and suggest that C2MAB-V outperforms other naive alternatives (WQ9G, hptZ).

However, while the application to LLMs is timely, reviewers found the algorithm to be not substantially different from existing methods, and the analysis is similar to previous results on combinatorial bandits (RM4A, XJC9).   RM4A points out that reward models used in the paper are simple and may not accurately reflect real-world scenarios. The paper only evaluates the algorithm on one dataset and does not provide enough information on the choice of parameters (RM4A). Moreover, the paper does not address the practical deployability of the algorithm, particularly in the context of LLMs (WQ9G, XJC9), and does not provide a clear comparison with other approaches, such as Mixture-of-Experts (MoE) and Composition of Experts (CoE) (WQ9G). One reviewer found the paper to be dense and hard to follow (XJC9), perhaps because this is more of a bandit paper.

Given the weaknesses and the lack of clarity around the contribution,  I would recommend rejecting this paper.  The authors should address whether this is solving a generalizable bandit problem that is a durable contribution to the literature, in which case framing the contribution as such (with an appropriate title, and cases beyond the LLM routing problem) would be appropriate.  If it is simply solving a specific problem with deployment of LLMs, more practical evaluation must be done (and perhaps breaking up the work into two papers may be logical).