New Routing Policy Optimizes Multi-Model LLM Services

This research addresses the complex problem of routing requests in multi-model language services, where the goal is to efficiently allocate prompts to different LLMs while staying within predefined budgets for compute, latency, memory, or cost. The authors highlight two key challenges: the high dimensionality of prompt representations, meaning only a few embedding directions truly predict a model's incremental value, and the constant "drift" in both request patterns and model performance due to updates and fine-tunes. To tackle these issues, the paper proposes Drift-Aware Sparse Routing (DRS). This policy estimates rewards and resource usage from a continuously updated "rolling audit window." It then routes requests using pessimistic reward and optimistic cost estimates, dynamically adjusting resource shadow prices online. A hard meter is applied before commitment to ensure budget adherence. The theoretical analysis provides regret bounds, demonstrating the policy's effectiveness in nonstationary environments with sparse contextual routing and multiple knapsack constraints.