A multi‑model language service must route each request while respecting workload‑level budgets for compute, latency, memory, or monetary cost. Two factors make this harder than static model selection: prompt representations are high‑dimensional, so only a small subset of embedding directions can predict a model’s incremental value; and the request mix and model frontier drift after new releases, fine‑tuning, quantization changes, or system updates.
We formalize the problem as non‑stationary sparse contextual routing with multiple knapsack constraints, optionally augmented by a shadow‑audit stream that evaluates a tiny fraction of prompts on several models to obtain ground‑truth rewards.
We propose Drift‑Aware Sparse Routing (DRS). The policy estimates reward and resource usage from a rolling audit window, routes using pessimistic reward and optimistic cost estimates, updates resource shadow prices online, and applies a hard meter before commitment to enforce budget limits.
The analysis separates control from statistics. For any event with uniform prediction radii $\{\beta_t\}$, regret against a paced dynamic fluid benchmark is bounded by the sum of the radii, a capacity‑buffer term, and an $O(\sqrt{T})$ pacing term.
Under a sparse linear model with bounded drift $V_T$, rolling estimation yields the bound $$\widetilde O\left( T\sqrt{\frac{s}{\rho W}}+WV_T+\sqrt{T} \right),$$ where $s$ is sparsity, $\rho$ is the audit rate, and $W$ is the window length. Optimizing $W$ recovers the usual stationary $O(\sqrt{sT/\rho})$ rate when $V_T=0$ and introduces an adaptation term $O\big(T^{2/3}(s/\rho)^{1/3}V_T^{1/3}\big)$ under drift.
Review