Keeping Up with the Models: Online Deployment and Routing of LLMs at Scale

Shaoang Li, Jian Li

Abstract

The rapid release cycle of Large Large Models (LLMs) creates a "streaming inventory" problem where providers must decide which models to keep active under strict concurrency caps and how to route queries to them. This paper introduces StageRoute, a hierarchical algorithm that achieves near-optimal performance by coupling strategic stage-wise deployment with tactical per-query routing. StageRoute manages the trade-off between exploring new models and exploiting known incumbents, matching a theoretical lower bound of $\tilde{O}(T^{2/3})$ regret.

Introduction

In the current AI landscape, new models arrive almost weekly, each with different performance, latency, and pricing profiles. Cloud providers and enterprise users face a two-fold challenge:

  1. Deployment Constraints: Hardware limits and deployment quotas (concurrency caps) prevent keeping every model active simultaneously.
  2. Routing Constraints: For every incoming query, a model must be chosen from the currently deployed set to maximize quality while respecting long-term cost budgets and per-model throughput limits.

Existing research often assumes a static pool of models. This paper addresses the fluid scenario where models arrive in a stream, requiring the system to decide when to "evict" a reliable incumbent to "explore" a promising newcomer.

The StageRoute Framework

The authors propose StageRoute, a hierarchical framework operating on two distinct timescales to manage streaming LLM inventory.

The StageRoute framework couples strategic stage-wise deployment with tactical per-query routing to manage continuous LLM rollouts.

Strategic Layer: Stage-wise Deployment

At fixed intervals (update points), the algorithm selects a subset of up to $M_{max}$ models to deploy for the next stage. It employs an "optimism in the face of uncertainty" approach, calculating Upper Confidence Bounds (UCB) for model rewards and Lower Confidence Bounds (LCB) for costs. A Mixed-Integer Program (MIP) is then solved to identify the most promising active set that satisfies budget and throughput constraints.

Tactical Layer: Per-query Routing

Once models are deployed, incoming queries are routed via a Linear Program (LP). This LP determines a probability distribution over the currently deployed models to maximize estimated quality while strictly adhering to per-query budgets and per-model throughput limits. This coupling ensures the system explores high-quality models while adaptively managing load in real-time.

Evaluation and Datasets

StageRoute was evaluated using two primary benchmarks:

  • RouterBench: A dataset of 36,497 queries across eight tasks (math, code, RAG, etc.) featuring 11 LLMs (e.g., GPT-4, Claude, Llama-2).
  • Synthetic "State-of-the-Art" Benchmark: A simulation of 15 high-performance LLMs (including GPT-4o, DeepSeek-R1, and Gemini 2.0 Flash) arriving every 1,000 queries to test the algorithm against continuous model rollouts.

Key Results

StageRoute demonstrates significant performance advantages over traditional methods, achieving near-optimal regret.

Cumulative regret comparison: StageRoute significantly outperforms Greedy and Random baselines.
  • Tracking the Oracle: StageRoute's performance-cost trajectory closely follows a "Strong Oracle" with perfect future knowledge.
  • Baseline Comparison: It outperforms "Greedy" strategies, which are often too conservative to adopt new models, and "Random" strategies, which frequently violate cost budgets.
  • Operational Efficiency: The system is viable for production; an experimental run of 36k queries finished in under 10 minutes on a standard consumer processor.

Key Insights and Limitations

The paper identifies a structural "Model Discovery Bottleneck." If the concurrency cap is small, a system might miss a high-performing model simply because it lacked a slot to test it. StageRoute manages this by being optimistic about newcomers while using conservative cost estimates to ensure budget safety.

While effective, StageRoute does not explicitly optimize for per-query latency requirements, though throughput limits act as a proxy. Additionally, the current deployment step is non-contextual. Future work could integrate contextual estimators—using query features to predict model performance for specific prompts—directly into the deployment phase to further refine routing accuracy.

Summary updated

BibTeX
@inproceedings{li2026keeping,
  author = {Shaoang Li and Jian Li},
  title = {{Keeping Up with the Models: Online Deployment and Routing of LLMs at Scale}},
  booktitle = {International Conference on Learning Representations},
  year = {2026},
  url = {https://openreview.net/forum?id=JJ3cwtUxzo},
}
Figure