# Near-Optimal Online Deployment and Routing for Streaming LLMs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 66 references that are in the map.
- First posted on arXiv 8 Jun 2025.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [GLaM: Efficient Scaling of Language Models with Mixture-of-Experts](https://mlsanity.com/paper/2112.06905/) (2021)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [Scaling Vision with Sparse Mixture of Experts](https://mlsanity.com/paper/2106.05974/) (2021)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [LLM-Blender: Ensembling Large Language Models with Pairwise Ranking and Generative Fusion](https://mlsanity.com/paper/2306.02561/) (2023)
- [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)
- [RouterBench: A Benchmark for Multi-LLM Routing System](https://mlsanity.com/paper/2403.12031/) (2024)
- [GraphRouter: A Graph-based Router for LLM Selections](https://mlsanity.com/paper/2410.03834/) (2024)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Routing to the Expert: Efficient Reward-guided Ensemble of Large Language Models](https://mlsanity.com/paper/2311.08692/) (2023)
- [Large Language Model Cascades with Mixture of Thoughts Representations for Cost-efficient Reasoning](https://mlsanity.com/paper/2310.03094/) (2023)
- [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)
- [RouterDC: Query-Based Router by Dual Contrastive Learning for Assembling Large Language Models](https://mlsanity.com/paper/2409.19886/) (2024)
- [Universal Model Routing for Efficient LLM Inference](https://mlsanity.com/paper/2502.08773/) (2025)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [TensorOpera Router: A Multi-Model Router for Efficient LLM Inference](https://mlsanity.com/paper/2408.12320/) (2024)

## Built on by (most cited first, 3 of 3)

- [MonoScale: Scaling Multi-Agent System with Monotonic Improvement](https://mlsanity.com/paper/2601.23219/) (2026)
- [TRACE-ROUTER: Task-Consistent and Adaptive Online Routing for Agentic AI](https://mlsanity.com/paper/2607.22465/) (2026)
- [POLAR: Online Learning for LoRA Adapter Caching and Routing in Edge LLM Serving](https://mlsanity.com/paper/2604.16583/) (2026)

## Abstract (arXiv)

The rapid pace at which new large language models (LLMs) appear, and older ones become obsolete, forces providers to manage a streaming inventory under a strict concurrency cap and per-query cost budgets. We cast this as an online decision problem that couples stage-wise deployment (at fixed maintenance windows) with per-query routing among live models. We introduce StageRoute, a hierarchical algorithm that (i) optimistically selects up to Mmax models for the next stage using reward upper-confidence and cost lower-confidence bounds, and (ii) routes each incoming query by solving a budget- and throughput-constrained bandit subproblem over the deployed set. We prove a regret of tildeO(T2/3) with a matching lower bound, establishing near-optimality, and validate the theory empirically: StageRoute tracks a strong oracle under tight budgets across diverse workloads.