# Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets

arXiv: https://arxiv.org/abs/2609.00662 · HTML: https://mlsanity.com/paper/2609.00662/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 16 references that are in the map.
- First posted on arXiv 1 Sep 2026.

## Builds on (most cited first, 13 of 13)

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [RouterBench: A Benchmark for Multi-LLM Routing System](https://mlsanity.com/paper/2403.12031/) (2024)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [A Unified Approach to Routing and Cascading for LLMs](https://mlsanity.com/paper/2410.10347/) (2024)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [Online Stochastic Optimization with Wasserstein Based Non-stationarity](https://mlsanity.com/paper/2012.06961/) (2020)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [High-dimensional Linear Bandits with Knapsacks](https://mlsanity.com/paper/2311.01327/) (2023)

## Built on by (most cited first, 1 of 1)

- [Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory](https://mlsanity.com/paper/2610.05659/) (2026)

## Abstract (arXiv)

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.