Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets

• URL: http://arxiv.org/abs/2609.00662v1
• Date: Tue, 01 Sep 2026 03:39:59 GMT
• Title: Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets
• Abstract summary: A multi-model language service must route each request while preserving workload-level budgets for compute, latency, memory, or monetary cost.<n>We formulate nonstationary sparse contextual routing with multiple knapsack constraints and an optional shadow-audit stream.<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $\{β_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 O\left( T\sqrt{\frac{s}{ρW}}+WV_T+\sqrt{T} \right), \] where $s$ is sparsity, $ρ$ is the audit rate, and $W$ is the window length. Optimizing $W$ yields the usual stationary $O(\sqrt{sT/ρ})$ rate when $V_T=0$ and a $O(T^{2/3}(s/ρ)^{1/3}V_T^{1/3})$ adaptation term under drift.

Related papers

• Adaptive Compute in Latent World Models: When Depth Helps, Hurts, or Doesn't Matter [0.0]
  We show that depth helps (intrinsic, 6/9 tasks, rho up to 8x), depth actively hurts (inversion, 2/9, rho down to 0.87x), or depth barely matters (flat)<n>Inversion reproduces under a transformer predictor, yet its manifestation is configuration-dependent, shifting with metric space, horizon, encoder, backbone, and -- most strongly -- training data.<n>Whether more compute helps a world model is not a task property; it is a property of the operating configuration, with a stable, predictable, mechanism-backed core.
  arXiv  Detail & Related papers  (2026-07-11T08:27:33Z)
• Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent [39.805192541498634]
  We study nonstationary linear computation (GLBs), where the expected reward is modeled through a nonlinear link function with an unknown time-varying parameter.<n>We propose a new algorithm for nonstationary GLBs that utilize discounted online mirror descent (DOMD) for parameter estimation, thereby incurring only $O(1)$ for memory costs per round.
  arXiv  Detail & Related papers  (2026-05-25T08:40:32Z)
• How Fast Should a Model Commit to Supervision? Training Reasoning Models on the Tsallis Loss Continuum [3.9929570259734604]
  We show a unified loss family $J_Q$ that interpolates between RLVR and log-marginal-likelihood over latent trajectories.<n>All members share the same per-example gradient direction, differing only by a per-instance $P_-q$ that reweights each instance independently of the learning rate.<n>We derive two Monte Carlo estimators that directly optimize fixed-$q$ on the $J_Q$ continuum, without annotated rationales.
  arXiv  Detail & Related papers  (2026-04-28T17:52:38Z)
• The Hidden Width of Deep ResNets: Tight Error Bounds and Phase Diagrams [15.246178589173523]
  We study the gradient-based training of large-depth residual networks (ResNets)<n>We show that with a diverging depth $L$, a fixed embedding dimension $D$, and an arbitrary hidden width $M$, the training dynamics converges to a Neural Mean ODE training dynamics.
  arXiv  Detail & Related papers  (2025-09-12T11:51:44Z)
• Scaling Up Liquid-Resistance Liquid-Capacitance Networks for Efficient Sequence Modeling [50.994194925685434]
  LrcSSM is a $textitnon-linear$ recurrent model that processes long sequences as fast as today's linear state-space layers.<n>By forcing its Jacobian matrix to be diagonal, the full sequence can be solved in parallel.<n>LrcSSM offers a formal gradient-stability guarantee that other input-varying systems such as Liquid-S4 do not provide.
  arXiv  Detail & Related papers  (2025-05-27T20:02:59Z)
• A statistical perspective on algorithm unrolling models for inverse problems [2.7163621600184777]
  In inverse problems where the conditional distribution of the observation $bf y$ given the latent variable of interest $bf x$ is known, we consider algorithm unrolling. We show that the unrolling depth needed for the optimal statistical performance of GDNs is of order $log(n)/log(varrho_n-1)$, where $n$ is the sample size. We also show that when the negative log-density of the latent variable $bf x$ has a simple proximal operator, then a GDN unrolled at depth $
  arXiv  Detail & Related papers  (2023-11-10T20:52:20Z)
• Regret-Optimal Federated Transfer Learning for Kernel Regression with Applications in American Option Pricing [8.723136784230906]
  We propose an optimal iterative scheme for federated transfer learning, where a central planner has access to datasets. Our objective is to minimize the cumulative deviation of the generated parameters $thetai(t)_t=0T$ across all $T$ iterations. By leveraging symmetries within the regret-optimal algorithm, we develop a nearly regret $_optimal that runs with $mathcalO(Np2)$ fewer elementary operations.
  arXiv  Detail & Related papers  (2023-09-08T19:17:03Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
  arXiv  Detail & Related papers  (2022-10-15T09:22:22Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  We consider episodic reinforcement learning in reward-mixing Markov decision processes (RMMDPs) Our goal is to learn a near-optimal policy that nearly maximizes the $H$ time-step cumulative rewards in such a model.
  arXiv  Detail & Related papers  (2022-10-05T22:52:00Z)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  We devise an online learning algorithm and provide guarantees on its expected regret. This regret at time $T$ is upper bounded (i) by $widetildeO((d_u+d_x)sqrtd_xT)$ when $A$ and $B$ are unknown.
  arXiv  Detail & Related papers  (2021-09-29T14:07:21Z)
• Minimax Regret for Stochastic Shortest Path [63.45407095296692]
  We study the Shortest Path (SSP) problem in which an agent has to reach a goal state in minimum total expected cost. We show that the minimax regret for this setting is $widetilde O(B_star sqrt|S| |A| K)$ where $B_star$ is a bound on the expected cost of the optimal policy from any state. Our algorithm runs in-time per episode, and is based on a novel reduction to reinforcement learning in finite-horizon MDPs.
  arXiv  Detail & Related papers  (2021-03-24T10:11:49Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  We prove that an optimistic $Q$-learning enjoys a $mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of states, $A$ is the number of actions, $H$ is the planning horizon, $T$ is the total number of steps, and $Delta_min$ is the minimum sub-optimality gap.
  arXiv  Detail & Related papers  (2020-06-16T13:01:33Z)
• Naive Exploration is Optimal for Online LQR [49.681825576239355]
  We show that the optimal regret scales as $widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$, where $T$ is the number of time steps, $d_mathbfu$ is the dimension of the input space, and $d_mathbfx$ is the dimension of the system state. Our lower bounds rule out the possibility of a $mathrmpoly(logT)$-regret algorithm, which had been
  arXiv  Detail & Related papers  (2020-01-27T03:44:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.