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

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Placed in Process reward models for reasoning, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 40 of its 73 references that are in the map.
- First posted on arXiv 26 May 2024.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Process reward models for reasoning](https://mlsanity.com/alignment/process-reward-models-for-reasoning/)

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

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework](https://mlsanity.com/paper/2308.00352/) (2023)
- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (2021)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [Crowdsourcing Multiple Choice Science Questions](https://mlsanity.com/paper/1707.06209/) (2017)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing](https://mlsanity.com/paper/2404.14618/) (2024)
- [Check Your Facts and Try Again: Improving Large Language Models with External Knowledge and Automated Feedback](https://mlsanity.com/paper/2302.12813/) (2023)
- [Analysing Mathematical Reasoning Abilities of Neural Models](https://mlsanity.com/paper/1904.01557/) (2019)
- [A Dynamic LLM-Powered Agent Network for Task-Oriented Agent Collaboration](https://mlsanity.com/paper/2310.02170/) (2023)
- [A Survey on Offline Reinforcement Learning: Taxonomy, Review, and Open Problems](https://mlsanity.com/paper/2203.01387/) (2022)
- [BlenderBot 3: a deployed conversational agent that continually learns to responsibly engage](https://mlsanity.com/paper/2208.03188/) (2022)
- [AutoMix: Automatically Mixing Language Models](https://mlsanity.com/paper/2310.12963/) (2023)
- [Language Model Cascades: Token-level uncertainty and beyond](https://mlsanity.com/paper/2404.10136/) (2024)
- [InvestLM: A Large Language Model for Investment using Financial Domain Instruction Tuning](https://mlsanity.com/paper/2309.13064/) (2023)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Ekya: Continuous Learning of Video Analytics Models on Edge Compute Servers](https://mlsanity.com/paper/2012.10557/) (2020)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Efficient Exploration for LLMs](https://mlsanity.com/paper/2402.00396/) (2024)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Alleviating Matthew Effect of Offline Reinforcement Learning in Interactive Recommendation](https://mlsanity.com/paper/2307.04571/) (2023)
- [Conversational Contextual Bandit: Algorithm and Application](https://mlsanity.com/paper/1906.01219/) (2019)
- [Parameter-free online learning via model selection](https://mlsanity.com/paper/1801.00101/) (2017)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [On Optimal Caching and Model Multiplexing for Large Model Inference](https://mlsanity.com/paper/2306.02003/) (2023)
- [Contextual Combinatorial Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2303.17110/) (2023)

## Built on by (most cited first, 30 of 39)

- [GraphRouter: A Graph-based Router for LLM Selections](https://mlsanity.com/paper/2410.03834/) (2024)
- [MasRouter: Learning to Route LLMs for Multi-Agent Systems](https://mlsanity.com/paper/2502.11133/) (2025)
- [Router-R1: Teaching LLMs Multi-Round Routing and Aggregation via Reinforcement Learning](https://mlsanity.com/paper/2506.09033/) (2025)
- [IRT-Router: Effective and Interpretable Multi-LLM Routing via Item Response Theory](https://mlsanity.com/paper/2506.01048/) (2025)
- [OmniRouter: Budget and Performance Controllable Multi-LLM Routing](https://mlsanity.com/paper/2502.20576/) (2025)
- [Online Multi-LLM Selection via Contextual Bandits under Unstructured Context Evolution](https://mlsanity.com/paper/2506.17670/) (2025)
- [Learning to Route LLMs from Bandit Feedback: One Policy, Many Trade-offs](https://mlsanity.com/paper/2510.07429/) (2025)
- [ReSkill: Reconciling Skill Creation with Policy Optimization in Agentic RL](https://mlsanity.com/paper/2606.01619/) (2026)
- [Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptation](https://mlsanity.com/paper/2508.07675/) (2025)
- [How to Train a Leader: Hierarchical Reasoning in Multi-Agent LLMs](https://mlsanity.com/paper/2507.08960/) (2025)
- [FusionFactory: Fusing LLM Capabilities with Multi-LLM Log Data](https://mlsanity.com/paper/2507.10540/) (2025)
- [Task-Aware LLM Routing with Multi-Level Task-Profile-Guided Data Synthesis for Cold-Start Scenarios](https://mlsanity.com/paper/2604.09377/) (2026)
- [INFERENCEDYNAMICS: Efficient Routing Across LLMs through Structured Capability and Knowledge Profiling](https://mlsanity.com/paper/2505.16303/) (2025)
- [LLM Routing with Dueling Feedback](https://mlsanity.com/paper/2510.00841/) (2025)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [DiSRouter: Distributed Self-Routing for LLM Selections](https://mlsanity.com/paper/2510.19208/) (2025)
- [GMTRouter: Personalized LLM Router over Multi-turn User Interactions](https://mlsanity.com/paper/2511.08590/) (2025)
- [AxiomVision: Accuracy-Guaranteed Adaptive Visual Model Selection for Perspective-Aware Video Analytics](https://mlsanity.com/paper/2407.20124/) (2024)
- [PersonalizedRouter: Personalized LLM Routing via Graph-based User Preference Modeling](https://mlsanity.com/paper/2511.16883/) (2025)
- [LLMRouter: Unified Infrastructure for Developing, Evaluating, and Deploying LLM Routers](https://mlsanity.com/paper/2608.06867/) (2026)
- [Near-Optimal Online Deployment and Routing for Streaming LLMs](https://mlsanity.com/paper/2506.17254/) (2025)
- [Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing](https://mlsanity.com/paper/2607.09015/) (2026)
- [Cost and Accuracy of Long-Term Memory in Distributed Multi-Agent Systems Based on Large Language Models](https://mlsanity.com/paper/2601.07978/) (2026)
- [A Unified Online-Offline Framework for Co-Branding Campaign Recommendations](https://mlsanity.com/paper/2505.22254/) (2025)
- [SC-MAS: Constructing Cost-Efficient Multi-Agent Systems with Edge-Level Heterogeneous Collaboration](https://mlsanity.com/paper/2601.09434/) (2026)
- [A Component-Based Survey of Interactions between Large Language Models and Multi-Armed Bandits](https://mlsanity.com/paper/2601.12945/) (2026)
- [LMEdge: QoS-Aware LLM Inference Orchestration on Edge Clusters](https://mlsanity.com/paper/2607.17175/) (2026)
- [VDAR-Router: Adaptive LLMs Routing via Verbalized Query Difficulty Analysis Retrieval](https://mlsanity.com/paper/2607.18098/) (2026)
- [Online Learning with LLM Experts from Limited Feedback](https://mlsanity.com/paper/2609.05820/) (2026)
- [Faster, Smaller, and Smarter: Task-Aware Expert Merging for Online MoE Inference](https://mlsanity.com/paper/2509.19781/) (2025)

## Abstract (arXiv)

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 textitC2MAB-V, a underlineCost-effective underlineCombinatorial underlineMulti-armed underlineBandit with underlineVersatile 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, textitC2MAB-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, textitC2MAB-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 textitC2MAB-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 textitC2MAB-V effectively balances performance and cost-efficiency with nine LLMs for three application scenarios.