PaperlayerView exact revision on arXiv

Source-linked AI summary

Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets

Cheung Hao Lee, Patrick Wong

arXiv:2609.00662v1cs.AI

TL;DR

Routing model-service requests under shared budgets is difficult when decisions affect later feasible choices and the service must preserve resource capacity. The paper proposes DR-Sparse, using rolling sparse estimates, conservative reward and cost estimates, online shadow prices, and a hard meter. Its analysis bounds paced regret using prediction uncertainty, capacity buffering, and pacing, while the supplied simulation illustrates behavior under model updates but does not establish real-LLM gains.

  • Problem

    Model choices are coupled by shared workload budgets, so using a strong model on one request changes which later decisions remain feasible.

    Source: §1 · p. 1

  • Method

    DR-Sparse combines rolling sparse predictors, lower reward and upper consumption estimates, online resource prices, and a hard meter before commitment.

    Source: §1 · p. 2

  • Results

    The expected paced regret bound combines prediction-radius error, capacity-buffer value loss, and a pacing term.

    Source: §1.1 · p. 2, §4.3 · p. 6, §5.2 · p. 7

  • Takeaways & Limitations

    The analysis separates statistical estimation from control: any valid confidence sequence can feed the regret bound, while sparse rolling windows make drift and audit rates interpretable.

    Source: §9 · p. 13

    The simulation does not establish the magnitude of gains for real LLMs and assumes clipped linear outcomes, unbiased audits, and abrupt change points.

    Source: §6.4 · p. 10

Abstract

from arXiv · show

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 $\{\beta_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}{\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.

1 Introduction

The paper frames routing as a drifting, high-dimensional allocation problem: model choices affect shared workload budgets, while only a few context directions may predict incremental value. It proposes DR-Sparse, combining rolling sparse estimation with uncertainty-adjusted decisions and resource control, and presents a confidence-to-regret analysis and an executable simulation design.

1 Introduction

  • The paper identifies shared budgets as a source of coupling: using a strong model on one request changes which later workload decisions remain feasible.Source: §1 · p. 1
  • Prompt embeddings and related features can be high dimensional even when incremental model benefit depends on few directions, creating a history-versus-variance trade-off under drift.Dense recent estimates can have high variance, while sparse estimates using full history can average across obsolete regimes.Source: §1 · pp. 1–2

1.1 Contributions

  • The model treats requests as high-dimensional contexts with time-varying action values and shared resource limits, including a free fallback.The formulation allows random output length or latency and compares policies with a paced dynamic fluid benchmark.Source: §1.1 · p. 2
  • DR-Sparse combines rolling sparse reward and resource estimation, uncertainty-adjusted surplus, online shadow prices, and a hard meter for workload-level routing.The estimator can be replaced by a sparse generalized linear model or neural uncertainty model without changing the control proof.Source: §1.1 · p. 2
  • A confidence-to-regret theorem uses simultaneous prediction radii, with a sparse-window corollary exposing the trade-off between estimation error and drift bias.Short windows track changes but require more audits; long windows reduce variance while retaining obsolete data.Source: §1.1 · p. 2
  • The executable simulator compares rolling sparse, rolling dense, full-history sparse, frozen sparse, and clairvoyant policies under identical audit traces and two hard budgets.It creates three request regimes and two model updates, and provides repetition-level data, figures, and the paper's exact table.Source: §1.1 · p. 2

2 Related Work

Related work covers cost-aware LLM routing and serving, contextual learning with resource constraints, and methods for nonstationarity. The paper positions its contribution at their intersection: workload-level control with changing query mixes and model frontiers under multiple feasible resource budgets.

2.1 LLM routing and serving

  • Prior LLM routing work addresses cost-aware cascades and prompt-level model selection, pairwise routing preferences, and panel-style router evaluation; this paper focuses on changing frontiers and multiple budgets.It distinguishes routing and cascading as different uses of a quality estimator.Source: §2.1 · p. 3
  • Serving systems show that memory management and batching shape attainable throughput; the router treats predicted compute, latency, and cache footprint as resource coordinates.Shadow prices let routing respond to congestion without embedding a full queueing model in the semantic predictor.Source: §2.1 · p. 3

2.2 Contextual learning with resource constraints

  • Contextual bandits with knapsacks, dual mirror descent, and high-dimensional contextual methods provide foundations for sequential decisions with resource constraints.The paper identifies sparse constrained methodology as statistically closest, while treating the confidence sequence from its audit model as an input to control.Source: §2.2 · p. 3

2.3 Nonstationarity

  • Variation budgets and sliding-window methods address changing rewards, while resource scarcity makes the global impact of a local quality change depend on which resource is constrained.The paper uses sup-norm path variation for a direct window-bias bound and discusses Wasserstein calibration as a complementary view.Source: §2.3 · p. 3

3 Model

The model represents each request by a context and chooses among model, tool, or pipeline actions, including a zero-reward, zero-resource fallback. It allows audited counterfactual outcomes and sparse, time-varying outcomes, and evaluates decisions against a paced benchmark rather than an unrestricted prophet.

3.1 Requests, actions, and resources

  • Action 0 is a fallback with zero reward and no scarce-resource consumption; other actions can be models, tools, or model–tool pipelines.The fallback may represent abstention, a cached response, or a deferred batch.Source: §3.1 · p. 3

3.2 Shadow-audit feedback

  • With probability at least ρ, an audit supplies an unbiased outcome vector for every approved action, supporting counterfactual comparisons beyond the selected action's ordinary feedback.Audits may use simultaneous shadow inference, delayed replay, human comparison, or a trusted evaluator; their engineering cost is not assumed to be zero.Source: §3.2 · p. 4

3.3 Sparse time-varying outcome model

  • The outcome model assumes each parameter has at most s nonzero coordinates; clipping is convenient rather than essential, and generalized linear models can replace it.Source: §3.3 · p. 4

3.4 Paced dynamic fluid benchmark

  • The paced benchmark knows the current outcome model but cannot borrow arbitrarily from distant periods, matching stable service-rate targets where early budget exhaustion is undesirable.It is no larger than the fully anticipatory fluid benchmark with only an aggregate constraint, so guarantees against it are not guarantees against an unrestricted prophet.Source: §3.4 · pp. 4–5

4 Drift-Aware Sparse Routing

DR-Sparse estimates reward and resource use from recent audited data, then chooses actions using conservative uncertainty adjustments and current resource prices. A capacity buffer and a hard meter protect feasibility as prices and remaining capacity guide routing.

4.1 Rolling estimation

  • At update times, DR-Sparse fits reward and resource regressions for each action on a rolling audit window and hard-thresholds each slope vector to its s largest coordinates.The controller receives a simultaneous prediction radius for every context and action on a high-probability event.Source: §4.1 · p. 5

4.2 Uncertainty-adjusted surplus

  • The controller clips predicted reward downward by the confidence radius and predicted consumption upward, then selects a positive-score action or falls back.This asymmetry makes uncertain actions earn their way into routing through audits rather than relying on optimistic reward or understated cost.Source: §4.2 · p. 5

4.3 Price update and buffer

  • The price update uses planned upper consumption, while the capacity buffer γ accounts for both the virtual queue and random deviations from conditional mean consumption.Before commitment, a hard meter checks the reservation envelope against remaining capacity and substitutes a feasible lower-cost action or fallback if needed.Source: §4.3 · pp. 5–6

5 Performance Guarantees

The section establishes a confidence-to-control guarantee for metered routing, derives rolling sparse-estimation guarantees, and interprets the resulting window tradeoffs.

5.1 Regularity assumptions

  • Consumption granularity bounds virtual prices on the confidence event, while the condition is not required for hard feasibility.For each resource, positive expected consumption is at least c and confidence radii are below c/4.Source: §5.1 · p. 6

5.2 A confidence-to-control theorem

  • Under the theorem’s assumptions and γ < bmin, metering is always hard feasible and, with probability at least 1 − 2δ, leaves virtual actions unchanged; expected paced regret combines prediction-radius, capacity-buffer, and pacing terms.The theorem’s nonstatistical terms are described as capacity reserved for feasibility and pacing loss from online price updates.Source: §5.2 · p. 7

5.3 Sparse rolling-window estimation

  • Rolling-window estimation trades sampling error against drift bias: short windows track changes more closely, while long windows reduce variance but retain obsolete data.The sampling-error and drift-bias terms arise from fitting one parameter across a drifting window.Source: §5.3 · p. 7, §5.4 · p. 8

5.4 Interpretation

  • The theorem does not establish hard thresholding as universally optimal; factor models may suit dense low-rank embeddings, and action-specific windows may help when drift is localized.The confidence-to-control theorem still applies if an alternative estimator supplies valid prediction radii.Source: §5.4 · p. 8

6 Synthetic Experiments

The synthetic study tests routing across changing task mixes and model quality under shared compute and latency budgets. Rolling sparse routing adapts after changes, while budget pacing and model-quality adaptation remain distinct.

6.1 Environment

  • The simulator has 4,800 requests, four nonfallback models, two resources, and 28-dimensional contexts, with task mix and model quality changing after requests 1,600 and 3,200.Audits occur at rate 0.28 after a common 400-request warm start; per-request capacity rates are 0.31 for compute and 0.35 for latency.Source: §6.1 · p. 8

6.2 Policies

  • The comparisons include rolling sparse and dense routers, full-history sparse, a static sparse router, and a clairvoyant dynamic reference.Rolling sparse refits every 200 requests on the latest 700 and thresholds regressions to seven coordinates; full-history sparse retains obsolete regimes.Source: §6.2 · p. 8

6.3 Results

  • Rolling sparse recovers more rapidly after model updates than the frozen router, which loses utility after both change points.It discards obsolete labels while controlling variance from the 28-dimensional context.Source: §6.3 · p. 9, Figure 1 · p. 9
  • Virtual prices keep average compute use close to the pro-rata path, and the hard meter records no capacity violation.The window sweep shows very short windows are noisy and very long windows mix regimes; its intermediate optimum is not a universal tuning recommendation.Source: §6.3 · p. 9
  • Rolling policies respond to the two changes in task mix and model quality, while the frozen policy retains first-regime relationships.The blockwise view makes adaptation delay visible.Source: §6.3 · p. 9, Figure 2 · p. 10

6.4 What the experiment establishes

  • The simulation illustrates the predicted qualitative behavior but does not establish the magnitude of gains for real LLMs.The outcome model is linear after clipping, audits are unbiased, and change points are abrupt; real systems may instead have gradual drift, strategic traffic, correlated evaluator error, or queue-dependent latency.Source: §6.4 · p. 10

7 Real-Data Evaluation Protocol

The real-data protocol calls for a time-indexed panel that jointly measures model quality and resource use. It then evaluates routing under natural or controlled drift, audit variation, fixed budgets, and deployment guardrails.

7.1 Construct a time-indexed query-model panel

  • Build a timestamped prompt-model panel across product surfaces or task suites, recording task metadata, lengths, frozen-encoder embeddings, and resource measurements for audited prompts run on every approved model.Record generated tokens, wall-clock latency, accelerator seconds when available, and cache footprint or a calibrated proxy.Source: §7.1 · p. 10
  • Measure application-specific quality with appropriate tests or judgments, and report underlying quality dimensions separately even if routing uses a single scalar utility.Examples include coding tests and human failure review, structured extraction metrics, and blinded judgments plus factuality and safety checks for open-ended tasks.Source: §7.1 · p. 10

7.2 Create realistic drift

  • Study natural drift across releases or periods and controlled changes to models, quantization, retrieval, task mix, or API prices, distinguishing prompt covariate shift from performance conditional shift.Source: §7.2 · p. 11

7.3 Simulate online audits

  • Subsample the panel to audit rates from 1% to 30%, compare shadow-audit regression with inverse-propensity and doubly robust estimators, and report inference required per utility point recovered.Source: §7.3 · p. 11

7.4 Workload replay

  • Replay timestamped requests under fixed hard budgets against single-model, static, cascade, dense rolling, and periodically retrained baselines, reporting workload and subgroup outcomes plus adaptation delay.Source: §7.4 · p. 11

7.5 Prospective deployment

  • Begin prospective testing with low audit rates, conservative uncertainty penalties, logged recommendations, and guardrails against unvalidated models for high-risk requests.Use workload-level utility under a fixed capacity envelope as the primary endpoint, not only per-request win rate.Source: §7.5 · p. 11

8 Extensions

The extensions address unknown drift, alternative capacity accounting, limited feedback, and coupling between routing and the serving scheduler. They outline options while noting where additional analysis or safeguards are needed.

8.1 Adaptive window selection

  • Because optimal window length depends on unknown drift, a controller can combine estimators with geometric windows using a change detector or expert algorithm.Action-specific residual tests could avoid making a specialist update erase stable generalist data, but confidence validity under data-dependent window selection remains a challenge.Source: §8.1 · p. 12

8.2 Wasserstein drift

  • Distributional drift can be measured by distances between consecutive joint laws of context, reward, and consumption; a Lipschitz surplus converts Wasserstein radius into value-error.The passage presents this as an alternative to conservative sup-norm path variation for high-dimensional prompts.Source: §8.2 · p. 12

8.3 Aggregate rather than paced capacity

  • Capacity can be borrowed across periods by allocating each epoch's remaining capacity across its remaining time and rerunning the router.Analysis against an aggregate dynamic benchmark requires control of optimal dual-price variation or advance information about change.Source: §8.3 · p. 12

8.4 Ordinary bandit feedback

  • Without shadow audits, selected-model outcomes are confounded with routing; exploration, randomized traffic splits, and doubly robust estimation are alternatives.Safety constraints may limit exploration on high-stakes tasks, making offline coverage and conservative fallback essential.Source: §8.4 · pp. 12–13

8.5 Scheduler feedback

  • Resource predictions can incorporate queue length, batch composition, or cache pressure, while a two-timescale design separates scheduler congestion prices from slower quality adaptation.Both layers should avoid overreacting to the same short-lived latency spike.Source: §8.5 · p. 13

9 Conclusion

DR-Sparse addresses nonstationary, shared-budget LLM routing by combining sparse rolling estimation with uncertainty-aware control and a hard resource meter. The paper identifies versioned multi-model panels as the key empirical opportunity for measuring the tradeoff between adaptation and audit cost.

9 Conclusion

  • DR-Sparse combines rolling sparse estimation, uncertainty-adjusted surplus, online shadow prices, and a hard meter for routing under shared budgets and drift.Its analysis separates statistical prediction from online control and translates sparse rolling windows, drift, and audit rates into an adaptation term.Source: §9 · p. 13
  • A useful router must identify context coordinates predictive of incremental model value, discard data made obsolete by frontier changes, and pace scarce resources across requests.Source: §9 · p. 13
  • Versioned multi-model panels could measure how quickly routers should forget, the value of shadow evaluation after updates, and whether sparse representations retain operational value at production scale.Source: §9 · p. 13

A Proofs

The proofs separate control guarantees from estimation error: confidence bounds support price-aware routing and feasibility, while rolling-window estimation accounts for sampling error and drift. The drift corollary makes the window-length tradeoff explicit.

A.1 Proof of the price-bound lemma

  • On the confidence event, tie-breaking toward lower consumption resolves the clipping tie case and keeps each shadow price bounded.The proof uses zero estimated consumption for the selected action in the resource coordinate to show the price cannot increase at the threshold.Source: §A.1 · p. 13

A.2 Approximate surplus maximization

  • The virtual action’s lower-confidence surplus is close to the true-surplus maximizer, with deviation bounded in terms of the prediction radius and shadow prices.Source: §A.2 · pp. 13–14

A.3 Proof of the main theorem

  • The main proof establishes hard feasibility through the meter and bounds the virtual policy on the confidence event, then combines confidence and martingale events.The meter commits only when the reservation envelope fits remaining capacity, and the fallback consumes zero.Source: §A.3 · pp. 14–15

A.4 Proof of the rolling-window proposition

  • Rolling-window prediction error combines sparse-regression sampling error with misspecification bias from changes in the mean within the window.The proof conditions on enough audited samples and bounds bias by changes across the window.Source: §A.4 · p. 15

A.5 Proof of the drift corollary

  • Each drift increment contributes to at most W windows, so the drift term is bounded by W V_T; optimizing the window balances this against the statistical term.The proof uses η = T^-1/2 and suppresses logarithmic and fixed regularity factors in the stated rate.Source: §A.5 · p. 15

B.1 Data-generating process

The appendix describes a reproducible synthetic routing setup and its estimator, controller, and hard meter. It also outlines extensions for model-specific audits, safety and fairness constraints, and cascaded actions.

B.1 Data-generating process

  • The synthetic process uses four model classes with distinct baseline compute and latency levels, noisy realized utility and consumption, and context-dependent task mixtures that change across regimes.Updates alter task bonuses and selected sparse coefficients; seven coordinates determine reward logits while remaining context coordinates are nuisance features.Source: §B.1 · pp. 15–16

B.2 Estimator and controller

  • The sparse policies use multi-output ridge regression with hard thresholding to seven slopes, while the dense baseline uses unthresholded ridge; a hard meter replaces over-budget sampled actions with fallback.The reported meter rejections are negligible or zero.Source: §B.2 · p. 16

B.3 Reproducibility

  • Running `python simulate_drift_routing.py --out .` regenerates the CSV files, table, and figures using fixed recorded seeds and ten main repetitions plus a window sweep.Source: §B.3 · p. 16

C.1 Model-specific audit rates

  • Audit rates can be increased for newly launched models, while pairwise audits against the selected model are proposed as a potentially better cost-information tradeoff than auditing all models.Source: §C.1 · p. 16

C.2 Safety constraints

  • Expected safety violations, ungrounded answers, and human escalations can be modeled as cumulative risk budgets, but hard per-request safety rules should filter inadmissible actions before scoring.Source: §C.2 · p. 16

C.3 Fairness across user groups

  • Group-specific quality or expensive-model-rate constraints can use dual variables as internal prices, but unequal audit coverage under drift can create apparent group gaps that are estimation artifacts.Source: §C.3 · p. 16

C.4 Cascades

  • A cascade can be represented as an action with expected reward and cost dependent on escalation probability, with first-stage output included in context or the full cascade treated as a compound action.Source: §C.4 · pp. 16–17

Related papers

Loading 2609.00662v1…