Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets

A multi-model language service must route each request while preserving workload-level budgets for compute, latency, memory, or monetary cost. Two features make this problem materially harder than static model selection. Prompt representations are high dimensional, so only a small subset of embedding directions may predict the incremental value of a model, and both the request mix and the model frontier drift after launches, fine-tunes, quantization changes, and system updates. We formulate nonstationary sparse contextual routing with multiple knapsack constraints and an optional shadow-audit stream that evaluates a small fraction of prompts on several models. We propose Drift-Aware Sparse Routing (DRS). The policy estimates reward and resource use 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. The analysis separates control from statistics. On any event with uniform prediction radii βt, regret against a paced dynamic fluid benchmark is bounded by the sum of the radii, a capacity-buffer term, and an O(√T) pacing term. Under a sparse linear model and bounded drift VT, rolling estimation gives [ widetilde Oleft( T√fracsρ W+WVT+√T right), ] where s is sparsity, ρ is the audit rate, and W is the window length. Optimizing W yields the usual stationary O(√sT/ρ) rate when VT=0 and a O(T2/3(s/ρ)1/3VT1/3) adaptation term under drift.