mlsanityData to 14 Oct 2026

Near-Optimal Online Deployment and Routing for Streaming LLMs

arXiv 2506.17254 ↗First posted 8 Jun 2025cs.LG cs.AIcited by 3

Not on the map. Why?

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.

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

45 of 66 references.

References · 45

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2023GPT-4 Technical Reportcited by 18,396
  3. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  4. 2021Training Verifiers to Solve Math Word Problemscited by 10,109
  5. 2023Judging LLM-as-a-Judge with MT-Bench and Chatbot Arenacited by 8,626
  6. 2020Measuring Massive Multitask Language Understandingcited by 7,963
  7. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,708
  8. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,326
  9. 2018Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challengecited by 4,886
  10. 2019HellaSwag: Can a Machine Really Finish Your Sentence?cited by 4,100
  11. 2021Program Synthesis with Large Language Modelscited by 3,637
  12. 2021Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsitycited by 3,073
33 more
  1. 2021GLaM: Efficient Scaling of Language Models with Mixture-of-Expertscited by 897
  2. 2023FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performancecited by 853
  3. 2021Scaling Vision with Sparse Mixture of Expertscited by 747
  4. 2024RouteLLM: Learning to Route LLMs with Preference Datacited by 682
  5. 2023LLM-Blender: Ensembling Large Language Models with Pairwise Ranking and Generative Fusioncited by 564
  6. 2019Introduction to Multi-Armed Banditscited by 481
  7. 2024Hybrid LLM: Cost-Efficient and Quality-Aware Query Routingcited by 372
  8. 2024RouterBench: A Benchmark for Multi-LLM Routing Systemcited by 238
  9. 2024GraphRouter: A Graph-based Router for LLM Selectionscited by 165
  10. 2013Bandits with Knapsackscited by 164
  11. 2023Routing to the Expert: Efficient Reward-guided Ensemble of Large Language Modelscited by 145
  12. 2023Large Language Model Cascades with Mixture of Thoughts Representations for Cost-efficient Reasoningcited by 143
  13. 2023AutoMix: Automatically Mixing Language Modelscited by 125
  14. 2024Language Model Cascades: Token-level uncertainty and beyondcited by 121
  15. 2024RouterDC: Query-Based Router by Dual Contrastive Learning for Assembling Large Language Modelscited by 88
  16. 2025Universal Model Routing for Efficient LLM Inferencecited by 86
  17. 2014Bandits with concave rewards and convex knapsackscited by 83
  18. 2024TensorOpera Router: A Multi-Model Router for Efficient LLM Inferencecited by 60
  19. 2025MixLLM: Dynamic Routing in Mixed Large Language Modelscited by 59
  20. 2024EmbedLLM: Learning Compact Representations of Large Language Modelscited by 48
  21. 2023Fusing Models with Complementary Expertisecited by 46
  22. 2024MetaLLM: A High-performant and Cost-efficient Dynamic Framework for Wrapping LLMscited by 41
  23. 2024Cost-Effective Online Multi-LLM Selection with Versatile Reward Modelscited by 39
  24. 2025LLM Bandit: Cost-Efficient LLM Generation via Preference-Conditioned Dynamic Routingcited by 34
  25. 2025Capability Instruction Tuning: A New Paradigm for Dynamic LLM Routingcited by 25
  26. 2020Online Learning with Vector Costs and Bandits with Knapsackscited by 20
  27. 2020Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Banditscited by 18
  28. 2022A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Banditscited by 12
  29. 2023Tight Regret Bounds for Single-pass Streaming Multi-armed Banditscited by 9
  30. 2024Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyondcited by 7
  31. 2024Optimal Streaming Algorithms for Multi-Armed Banditscited by 5
  32. 2025Offline Learning for Combinatorial Multi-armed Banditscited by 5
  33. 2023Tight Memory-Regret Lower Bounds for Streaming Banditscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026MonoScale: Scaling Multi-Agent System with Monotonic Improvementcited by 5
  2. 2026TRACE-ROUTER: Task-Consistent and Adaptive Online Routing for Agentic AIcited by 1
  3. 2026POLAR: Online Learning for LoRA Adapter Caching and Routing in Edge LLM Servingcited by 0