Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets

arXiv:2609.00662v1 Announce Type: new Abstract: 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 {eta_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 and bounded drift V_T, rolling estimation gives [ widetilde Oleft( Tsqrt{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 yields the usual stationary O(sqrt{sT/rho}) rate when V_T=0 and a O(T^{2/3}(s/rho)^{1/3}V_T^{1/3}) adaptation term under drift.

Related

• Scrouting: Cost-Aware Routing of Coding Agents by Scouting the Repository First
• Multi-Agent Routing as Set-Valued Prediction: A WildChat Benchmark and Cost-Aware Evaluation
• MTRouter: Cost-Aware Multi-Turn LLM Routing with History-Model Joint Embeddings
• LLMs Can Predict Failure Risk, But Struggle to Predict Which Collaboration Protocol Pays Off: Cost-Aware Protocol Routing Across Reasoning Tasks
• Pro-Router: Token-Aware Progressive Model Routing with Adaptive Edge-Cloud Collaboration for Efficient Multimodal LLM Inference

Source: arXiv cs.AI | 2026-09-02