# Online LLM Selection via Constrained Bandits with Time-Varying Demand

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 49 references that are in the map.
- First posted on arXiv 16 Jun 2026.

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

- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [Time Series Forecasting With Deep Learning: A Survey](https://mlsanity.com/paper/2004.13408/) (2020)
- [Check Your Facts and Try Again: Improving Large Language Models with External Knowledge and Automated Feedback](https://mlsanity.com/paper/2302.12813/) (2023)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Ekya: Continuous Learning of Video Analytics Models on Edge Compute Servers](https://mlsanity.com/paper/2012.10557/) (2020)
- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [Sustainable LLM Inference for Edge AI: Evaluating Quantized LLMs for Energy Efficiency, Output Accuracy, and Inference Latency](https://mlsanity.com/paper/2504.03360/) (2025)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [ThriftLLM: On Cost-Effective Selection of Large Language Models for Classification Queries](https://mlsanity.com/paper/2501.04901/) (2025)
- [Device-Cloud Collaborative LLM Inference with Multi-Modal, Multi-Task, Multi-Turn Conversations](https://mlsanity.com/paper/2502.11007/) (2025)
- [Invisible Tokens, Visible Bills: The Urgent Need to Audit Hidden Operations in Opaque LLM Services](https://mlsanity.com/paper/2505.18471/) (2025)
- [Online Resource Allocation under Horizon Uncertainty](https://mlsanity.com/paper/2206.13606/) (2022)
- [Resource Allocation for Stable LLM Training in Mobile Edge Computing](https://mlsanity.com/paper/2409.20247/) (2024)
- [Learning the Optimal Path and DNN Partition for Collaborative Edge Inference](https://mlsanity.com/paper/2410.01857/) (2024)
- [Quantum Entanglement Path Selection and Qubit Allocation via Adversarial Group Neural Bandits](https://mlsanity.com/paper/2411.00316/) (2024)

## Abstract (arXiv)

Large Language Models (LLMs) are increasingly deployed in edge-cloud inference systems to handle diverse user tasks with heterogeneous accuracy, latency, and cost profiles. Selecting the appropriate LLM for each incoming task is critical for ensuring service quality and efficient resource utilization. However, model heterogeneity, stochastic and unknown performance characteristics, and time-varying task demands make static selection strategies inadequate. Real-world deployments often impose hard resource budgets such as monetary expenditure limits, along with soft service-level requirements such as latency guarantees. These constraints introduce additional challenges for online decision-making. We formulate this problem as a constrained stochastic bandit learning task, where the learner sequentially selects models under both packing-type (hard) and covering-type (soft) constraints, while adapting to time-varying task demand. The learner operates without access to the underlying reward, cost, or latency distributions and must rely on partial feedback. We develop a novel online learning algorithm that leverages confidence-bound estimates and demand predictions to balance reward maximization with long-term constraint satisfaction. We provide theoretical guarantees showing sublinear regret and sublinear covering constraint violations compared to an offline benchmark with full information. Experimental results on synthetic workloads demonstrate the effectiveness and robustness of our approach in dynamic, resource-constrained environments.