Bandit Formulations of Model Routing: Regret-Optimal Allocation Under Cost Constraints

Executive summary for technical leaders

Model routing is the highest-leverage cost lever in production AI after caching: run a cheap model on the easy majority of queries and pay for an expensive one only where it earns its price. The published record shows the lever is powerful. FrugalGPT reports matching GPT-4 quality with up to a 98 percent cost reduction on some tasks.^[1] RouteLLM reports retaining about 95 percent of GPT-4 quality at roughly an 85 percent cost reduction on MT-Bench while sending only about 14 percent of queries to the strong model.^[2] Hybrid LLM reports up to 40 percent fewer large-model calls with no drop in response quality.^[3] MetaLLM, which routes with a multi-armed bandit, reports up to a 60 percent cost reduction with a small accuracy gain.^[4]

Almost every one of these systems makes the routing decision the same way: it scores a query and thresholds the score. This paper asks whether that is the right rule and what happens when the router must learn from live traffic. The answer has three parts. First, routing under a spend budget is not a classification problem but a resource-allocation problem, and specifically a contextual bandit with a knapsack constraint: the optimal policy can strictly beat playing the best model on everything, because a budget forces a mix.^[5] Second, the optimal policy is not a confidence threshold but a single-price rule: route each query to the model with the best estimated quality minus a price lambda times its cost, where lambda is one scalar tuned so the budget binds. Third, learning that policy online is cheap, its regret shrinks like the square root of traffic, and it is minimax optimal in the horizon and feature dimension.^[7]

flowchart LR
  Q["Query x (features)"] --> R{"Route: argmax_m q_m(x) - lambda c_m"}
  R -- "cheap" --> M1["Small model (cost c1)"]
  R -- "escalate" --> M2["Large model (cost c2)"]
  M1 --> A["Answer + quality signal"]
  M2 --> A
  A --> B["Budget controller"]
  B -- "adjust price lambda" --> R

The practical upshot is a short checklist. Replace any hand-picked confidence threshold with a single price lambda, and route on quality-per-dollar. Tune lambda with a simple online controller that raises the price when you overspend and lowers it when you are under budget. Calibrate the quality signal before you price against it, because a threshold on a miscalibrated score is a threshold on the wrong axis.^[29] Measure the variance of the quality gap across your traffic, because it is the ceiling on what any router can save over a fixed fraction. And watch lambda itself: a persistently high price means you are quality-starved and should raise the budget, while a near-zero price means the budget is slack. The rest of the paper makes each of these precise, with the derivations carried out.

None of this argues against the routers already in production; the point is to run them at their optimum rather than near it, and to know which of two problems a plateau represents. The single-price rule is not more expensive to deploy than a threshold: it is the same one-comparison per query with the comparison set correctly, plus a small controller that maintains the price. Its first improvement over a hand-tuned threshold, using the budget-derived price instead of a guessed bar, is essentially free. The more expensive improvement, a learned per-query estimate of the quality gap, is worth building only when the workload's gap varies enough across queries to repay it, and the analysis tells you how to measure that (the variance of the gap) and how much it is worth (the approximation gap). The contribution is thus both a piece of theory, the identification of budgeted routing with a contextual knapsack bandit and the derivation of its optimal rule and regret, and a decision procedure for practitioners, a short ordered checklist that says what to measure, in what order, and when to stop tuning and start building.

1. Introduction

The dominant cost structure of applied language modeling is heterogeneous. The price of a token differs by up to two orders of magnitude across the available APIs, and the quality difference between the cheapest and the most capable model is large on hard queries and negligible on easy ones.^[1] That combination is what makes routing pay. If a cheap model answers the easy majority of queries acceptably, and an expensive model is reserved for the hard minority, the blended cost can approach the cheap model's while the blended quality approaches the expensive model's. The entire problem is the decision rule that separates easy from hard on a per-query basis, without knowing the ground truth, at the moment of the query, and under a fixed spend budget.

1.1 Routing is allocation, not classification

The prevailing engineering framing treats routing as a classification problem: train a model to predict whether the cheap model will be good enough, and threshold its score. This framing is natural, and the learned routers built on it work well, but it hides the structure that matters. Routing spends a scarce, shared resource, the dollar budget, across a stream of queries that compete for it. Sending one query to the expensive model consumes budget that a later query cannot use. The right question is therefore not per-query (is this query hard?) but global (how should a fixed budget be allocated across the query distribution to buy the most quality?). That is an allocation problem, and the presence of a hard budget makes it a knapsack. The distinction is not pedantic. Under a budget, the optimal policy can strictly outperform the policy that plays the single best model on every query, a fact that is the defining feature of the Bandits with Knapsacks problem and that no per-query classifier framing exposes.^[5]

Because each query arrives with observable features (its length, its topic, a difficulty estimate, an embedding, the cheap model's own confidence), and because the reward of a routing choice is unknown until the model answers and is only ever observed for the model actually run, the correct formal object is a contextual bandit with a budget constraint. The contextual bandit is the standard model for sequential decisions with side information and partial feedback, introduced for exactly this shape of problem in personalized recommendation.^[6] Adding a knapsack constraint turns it into the budgeted variant whose theory we will use.^[18]

A concrete scenario fixes intuition. A support assistant handles a million queries a month across a fleet of three models: a small model at roughly a tenth the price of a frontier model and a mid-tier in between. Finance sets a monthly inference budget. The naive engineering answer is to pick a confidence threshold, ship it, and revisit when the bill looks wrong. The allocation answer is different in kind: the budget is a fixed pool of dollars that the month's queries compete for, and the job is to spend each dollar where it buys the most quality. If a burst of easy queries arrives early and the router spends freely on them, there is less budget left for the hard queries at month's end, so the right amount to spend on any single query depends on the whole month's demand, not on that query alone. That coupling across queries is what a classification threshold cannot represent and what the knapsack view makes central. The contextual-bandit formulation captures both halves: the per-query features that predict difficulty and the budget that couples the queries into one allocation.

1.2 What deployments do today

Three families of rule dominate practice. The first is a fixed escalation fraction: send a constant share of traffic, or traffic above a static difficulty percentile, to the expensive model. The second is a fixed confidence threshold: run the cheap model, read a self-reported confidence or a small auxiliary scorer, and escalate when it falls below a bar chosen offline.^[3] The third, and strongest, is a learned router: a classifier or matrix-factorization model trained on preference or win-rate data to predict, per query, whether a cheaper model suffices, whose decision boundary is then a threshold on that predicted win probability.^[2] MetaLLM is the closest prior art to this paper's framing: it routes with an explicit multi-armed bandit and a reward that trades quality against cost, and reports up to a 60 percent cost reduction with a roughly 1 percent accuracy gain on classification and question-answering tasks.^[4] LLM Bandit extends the bandit framing to preference-conditioned routing chosen at inference time.^[25]

What all three families share is that their control knob (a fraction, a threshold, a decision boundary) is set without reference to the budget-to-quality exchange rate that the optimal policy is built around. The learned routers come closest, because they read a per-query signal, but even they threshold that signal at a level chosen by hand or by a validation sweep rather than derived from the budget. This paper's contribution is to give the exact rule the budget implies, to show how far the common rules sit from it, and to bound how fast a learner can reach it.

1.3 The gap in prior work

Two mature literatures bracket this problem without joining over it. On one side, bandit theory gives the optimal policies and regret rates for sequential decisions under uncertainty, including the contextual case with linear rewards^[7] and the budgeted case with knapsack constraints.^[5] On the other side, the LLM-routing literature is largely empirical: it reports cost-quality operating points for particular routers on particular benchmarks (FrugalGPT, RouteLLM, Hybrid LLM, RouterBench) but does not state the budget-optimal policy, its Pareto frontier, or the regret of learning it for the LLM-routing setting specifically.^[24] MetaLLM applies a bandit but reports outcomes, not a regret bound or an optimality characterization.^[4] The gap this paper fills is the bridge: take the routing problem exactly as deployed (heterogeneous model costs, unknown query-dependent quality, a hard spend budget) and derive its optimal policy, its frontier, and its online regret from bandit first principles, then read the empirical record through the result.

1.4 Contributions

This paper makes five contributions, each derived and then checked against cited evidence.

1. A formalization. We cast per-query model routing under a spend constraint as a budgeted contextual bandit (Section 3) and situate it exactly within Bandits with Knapsacks and linear contextual bandits with knapsacks.^[5][18]
2. The single-price optimal policy. We prove (Theorem 1, Section 4) that the regret-optimal offline policy is a linear scalarization: route x to argmax over m of q_m(x) minus lambda times c_m, with lambda the scalar shadow price of the budget, via LP duality of the fluid relaxation.
3. The frontier-slope identity. We prove (Theorem 2) that the quality-cost Pareto frontier is concave and its slope equals lambda (an envelope identity), giving the shadow price a double meaning as both the routing threshold and the marginal value of a dollar, and we give the approximation gap of any budget-agnostic rule in closed form (Theorem 3).
4. Matching online regret. We prove (Theorems 4 to 6, Section 5) that an optimistic router with an online-dual price controller achieves reward-regret of order d times the square root of T plus budget-regret of order the square root of T, matching the linear-contextual-bandit lower bound of order the square root of dT, while explore-then-commit and epoch-greedy give the worse T-to-the-two-thirds.^[7][16]
5. A synthesis. We show (Sections 6 and 7) that the value of a contextual router over a fixed fraction scales with the variance of the quality gap across queries, that learned routers are margin estimators equivalent to the price rule only when their threshold is budget-tied, and that the published cost-quality numbers are consistent with the theory.

1.5 Scope, method, and non-goals

The method is derivation plus synthesis. The theorems are proved here from stated assumptions; the empirical numbers are quoted from published sources, each with a citation in the sentence that uses it, and the load-bearing ones cross-confirmed against a second source. We ran no experiments and report none. Every figure is either an analytical model built from the equations we derive, labeled as such in its caption with its illustrative parameters, or a table of cited results that names its sources. The non-goals are three. We do not propose a new production router or claim benchmark wins; we characterize the policy any router approximates. We do not resolve how to obtain an unbiased online quality signal (the reward), which for open-ended generation is a genuine open problem we treat honestly in Section 9. And we do not address multi-model ensembling or cascading as such, though Section 8 connects to them; our arms are single models and the choice is which one to run.

2. Background and related work

2.1 Multi-armed bandits and regret

The multi-armed bandit is the canonical model of the exploration-exploitation tradeoff. A learner repeatedly chooses one of K arms, receives a noisy reward from the chosen arm only, and seeks to maximize cumulative reward.^[8] Performance is measured by regret, the shortfall against always playing the best arm in hindsight. For a routing policy pi choosing model a_t on query x_t, write the regret against the optimal policy a-star as in Equation 1.

Two classical results anchor everything that follows. The Lai-Robbins lower bound shows that any consistent policy must incur regret growing at least logarithmically in the horizon, with a constant set by the Kullback-Leibler divergence between the arms' reward distributions: harder-to-distinguish arms cost more to sort out.^[10] The upper confidence bound algorithm UCB1 achieves a matching order, pulling each suboptimal arm only about a logarithmic number of times, by acting optimistically on a confidence interval around each arm's mean.^[11] Thompson sampling, which instead samples from a Bayesian posterior and plays the sampled best arm, is the oldest such heuristic and is now known to be near-optimal as well.^[9] The optimism principle behind UCB is what our online router will use, because it extends cleanly to the contextual and budgeted cases.^[12]

Two features of the regret framework matter for routing specifically. First, regret is the right currency because it is additive across queries and directly convertible to dollars: a reward-regret of R units of quality at a shadow price lambda is worth lambda times R dollars of misallocated budget, which is why Equation 13 prices the two regrets on a common scale. Second, the exploration-exploitation tension is real in a router and not an academic nicety. A router that always plays the model that currently looks best never learns whether a cheaper model would have sufficed on the queries it escalates, so it cannot discover savings; a router that explores too aggressively wastes budget running models it already knows are wrong. The optimism principle resolves this by exploring only where the uncertainty is large enough to possibly change the decision, which is exactly the queries whose gap estimate straddles the price threshold.

2.2 Contextual and linear bandits

In a contextual bandit each round carries a feature vector, and the learner may condition its choice on it. The workhorse assumption is that expected reward is linear in features: q_m(x) equals the inner product of an unknown parameter vector with the context. LinUCB maintains a ridge-regression estimate of each arm's parameter and an ellipsoidal confidence set, and plays the arm with the highest optimistic reward.^[6] Its analysis was tightened by SupLinUCB, which proves a regret of order the square root of T times d (up to logarithmic factors) and a matching lower bound of the same order, so the dependence on the feature dimension d and the horizon T is settled for the linear case.^[7] OFUL sharpened the confidence sets using a self-normalized martingale tail inequality, giving the cleanest modern regret of order d times the square root of T with high probability.^[13] The lower bound of order d times the square root of T for stochastic linear bandit feedback was established by Dani, Hayes, and Kakade.^[14] Thompson sampling also extends to the linear contextual case with a regret of order d-to-the-three-halves times the square root of T.^[15] Two cruder schemes matter as baselines: epoch-greedy, which alternates fixed exploration and exploitation phases and achieves regret of order T-to-the-two-thirds without needing to know the horizon,^[16] and, for the adversarial (non-stochastic) case, EXP4, which achieves regret of order the square root of KT log N against N experts.^[17]

The reason the linear case is not a toy for routing is that a modern router already computes a feature vector per query (an embedding, a difficulty score, length, the cheap model's logits) and predicts quality from it with a learned head. That head is, to first order, a linear map on features, so the linear-bandit rates are the right reference for what a router can achieve online.

2.3 Bandits with knapsacks and budgets

The budgeted variant adds one or more resource constraints. In Bandits with Knapsacks, each pull consumes a vector of resources drawn from an unknown distribution, and play halts when any budget is exhausted; the objective is total reward before the halt.^[5] The signature result is that the optimal dynamic policy can strictly beat the best fixed arm, because a budget forces a mixture, and that a primal-dual algorithm achieves regret sublinear in the budget, with a matching worst-case lower bound.^[5] The linear-contextual version, Linear Contextual Bandits with Knapsacks, is the exact home of our problem: rewards and resource consumptions depend linearly on the arm's context, budgets cap the summed consumption per resource, and the near-optimal regret is of order the square root of T.^[18] The concave-reward, convex-knapsack generalization frames the same object through online convex optimization.^[19] Simpler budget-limited bandits without context also have clean results: KUBE combines density-ordered greedy knapsack packing with UCB and achieves regret logarithmic in the budget,^[20] and a Thompson-sampling variant handles the same budgeted setting.^[21] The oldest index result, the Gittins index, gives the exact optimal policy for the discounted Bayesian bandit as a per-arm reservation value, foreshadowing the single-price structure we derive.^[22]

The optimal-beats-best-fixed-arm property deserves a concrete reading for routing because it is the formal reason routing is not just model selection. Without a budget, the best policy is to find the single best model and use it everywhere; model selection is then a pure identification problem and a bandit is overkill. A budget changes the answer qualitatively: using the best model everywhere is infeasible (it blows the budget) and using the cheapest everywhere is feasible but wasteful (it under-spends on the queries that would benefit), so the optimum is a genuine mixture that no single arm reproduces.^[5] That mixture is exactly the single-price rule, which sends different queries to different models. The knapsack literature also supplies the tool we use to learn the mixture online, the primal-dual method: maintain a dual price on the budget and run a standard bandit on the price-adjusted reward, updating the price to conserve the resource.^[18] This is the template PrimalDualLinUCB-Route instantiates in Section 5, and its regret guarantee is inherited from the linear-contextual-knapsack analysis rather than re-derived from scratch.

2.4 LLM routing and cascades

The applied literature is where the numbers live. FrugalGPT learns which cheap models suffice for which queries and escalates the rest, matching GPT-4 with up to 98 percent lower cost or beating it by 4 percent at equal cost, using an LLM cascade with a learned scorer.^[1] Its predecessor FrugalML did the same for classification prediction APIs.^[26] RouteLLM trains a router from human preference data and reports retaining about 95 percent of GPT-4 quality at an 85 percent cost reduction on MT-Bench, sending only about 14 percent of queries to the strong model.^[2] Hybrid LLM trains a deferral classifier and reports up to 40 percent fewer large-model calls at no quality cost.^[3] The mixture-of-thoughts cascade routes by answer consistency across reasoning representations.^[27] RouterBench standardizes evaluation across 405,000 inference outcomes, 64 tasks, and 11 models, scoring routers by a cost-quality area metric and the convex hull of achievable operating points.^[24] That convex hull is, precisely, the Pareto frontier we characterize analytically in Section 4. The cascade cousin of routing, where models are tried in sequence and the run stops on a confident answer, is analyzed as optimal stopping in a companion to this work; here the choice is parallel (which single model to run) rather than sequential.

It is worth noting how each of these systems maps onto the bandit vocabulary, because the mapping is what lets us read their numbers as evidence for or against the theory. FrugalGPT's learned scorer is an estimator of whether the cheap model's answer will be accepted, which is a proxy for the quality gap, and its cascade escalates when the score is low, which is the margin rule of Equation 8 with the threshold tuned on a validation set to hit a cost target; its reported 98 percent saving is achieved on tasks where a small model is genuinely competent, that is, high gap-variance tasks in our terms.^[1] RouteLLM's matrix-factorization and classifier routers are direct estimators of a win probability, a monotone transform of the gap, and its operating points are chosen by sweeping the threshold, which traces the frontier; the reported 14 percent escalation at 95 percent quality is one point on that sweep.^[2] Hybrid LLM's deferral classifier is trained to predict the quality drop of using the small model, which is the gap itself, and it thresholds that prediction.^[3] MetaLLM is the one system that names the bandit explicitly, with a cost-adjusted reward that is our scalarized quality minus lambda times cost, and it learns the routing online rather than from a fixed training set.^[4] The through-line is that all of them estimate the gap and threshold it; they differ in how they estimate it and how they set the threshold, which is exactly the estimation-versus-approximation decomposition of Section 5.

2.5 Confidence signals as routing inputs

Every threshold-based router thresholds some confidence or quality proxy, so the proxy's reliability governs the router's. Modern networks are systematically miscalibrated, typically overconfident, and post-hoc temperature scaling is the standard repair.^[29] Language models have some access to their own correctness (they can be prompted to estimate whether they know an answer), which is the basis of self-evaluation routing signals, but this access is partial and degrades off-distribution.^[30] The consequence for routing is that a threshold on a raw, miscalibrated score is a threshold on a distorted axis: the same nominal confidence means different true accuracies for different query types, so a single bar mis-sorts. Our price rule inherits this dependence, which is why calibration is a prerequisite, not an optional refinement, in the practical checklist of Section 10.

2.6 What the bandit view adds

The bandit formulation contributes three things the empirical framing lacks. It gives the exact optimal policy (a single price, not a hand-tuned threshold), derived rather than searched. It gives the Pareto frontier a closed characterization and an operational slope (the shadow price), so a team knows not just how to route but whether to change its budget. And it separates two kinds of loss that look alike in a dashboard: the estimation regret that more traffic removes, and the approximation regret that a too-weak policy class never removes. Figure 3 places the relevant regret rates side by side; the routing problem inherits the linear-contextual rate for reward and an additive square-root-of-T rate for the budget.

3. The routing model as a budgeted contextual bandit

3.1 Formal setup

Fix a fleet of K models. Model m has a known per-query cost c_m greater than zero (its price, in dollars or tokens; costs across the fleet may span two orders of magnitude^[1]) and an unknown quality q_m(x) in the unit interval for a query with features x drawn from a distribution D over the feature space. Quality is whatever scalar the deployment cares about: exact-match accuracy, a graded rubric score, or a calibrated win probability. Queries arrive one at a time; on query t the router observes x_t, chooses a model a_t, pays c_{a_t}, and receives a noisy reward with mean q_{a_t}(x_t). Crucially the router observes the reward only for the model it ran, the defining partial-feedback property of a bandit, and never learns what a different model would have returned on that query.

The deployment has a budget. Over a horizon of T queries it may spend at most B in total, equivalently an average of rho equals B over T per query. The router's objective is to maximize total expected quality subject to the budget, Equation 3, where pi denotes the (possibly randomized, context-dependent) routing policy and a_t is the model it selects.

3.2 The fluid relaxation and its LP

Because the queries are drawn independently from D and the costs are known, the constrained problem has a clean expected (fluid) relaxation that its optimal policy will track. Let z_m(x) in the unit interval be the probability that policy pi routes a query with features x to model m, so the z_m(x) sum to one for each x. The per-query expected quality is the sum over m of z_m(x) q_m(x), and the per-query expected cost is the sum over m of z_m(x) c_m. The fluid problem maximizes expected quality subject to expected cost at most rho, Equation 4.

This is an infinite-dimensional linear program in the routing distribution z. Its structure is the key to everything that follows: a single budget constraint couples all queries, and by LP duality that single coupling constraint is priced by a single scalar dual variable. That scalar is the shadow price lambda, and Section 4 shows it collapses the whole allocation into one number.

The fluid relaxation is exact in the large-horizon limit and near-exact for the volumes a production router sees. The gap between the fluid optimum and the best achievable value on a finite stream of T queries is of order the square root of T (the same order as the budget-regret), because the only thing the relaxation ignores is the integrality of a single boundary query type and the random fluctuation of realized spend around its mean. At the millions-of-queries scale of a deployed router this gap is negligible relative to the value being allocated, which is why we can reason about the price rule as if it were exactly optimal and fold the finite-sample slack into the learning cost of Section 5. The duality also explains an empirical regularity: RouterBench scores routers by the convex hull of their operating points,^[24] and the convex hull is precisely the set of points achievable by mixing pure policies, which is what the fluid LP optimizes over. A router that is not on the hull is dominated by a mixture of two that are, and the single-price rule is the mixture the budget selects.

3.3 Cost, tokens, and the resource being budgeted

A word on what c_m actually is, because it determines whether the theory applies cleanly. In the simplest deployment cost is a fixed per-query price, which makes Assumption A1 exact. More often cost is the output-token count times a per-token price, so it is a random variable whose mean depends on the query and the model (a reasoning model emits more tokens on a hard query). The budgeted-bandit theory accommodates this as stochastic resource consumption, and the single-price rule generalizes by pricing expected cost: route on q_m(x) minus lambda times the expected cost of running model m on x.^[5] The subtlety is that cost and quality are correlated through difficulty (hard queries cost more and are answered worse), so the router should use a per-query expected-cost estimate, not a flat per-model price, when the token spread is large. A second resource, latency, can be budgeted the same way with its own price, and a third, energy or carbon, likewise; the scalarization gains one lambda-times-consumption term per resource and the analysis is the convex-knapsack generalization.^[19] For the rest of the paper we take c_m as the expected cost, which keeps the derivations readable and loses nothing essential.

3.4 Assumptions

We state the assumptions the results rest on, and revisit each in Section 9.

• A1 (known costs). Each c_m is known and deterministic. In practice cost is output-token count times a price, so it has variance; we treat expected cost and discuss the correction in Section 9.
• A2 (bounded, stochastic reward). Quality lies in the unit interval and the reward is a bounded random variable with mean q_m(x), independent across queries given features.
• A3 (stationary contexts). Queries are drawn i.i.d. from a fixed distribution D. Drift is the most important violation and is treated in Section 9.
• A4 (realizability). For the online results, q_m(x) equals the inner product of an unknown parameter theta_m with a feature map of x, the standard linear-bandit assumption.^[7]
• A5 (interior budget). The budget rho lies strictly between the all-cheap cost and the all-expensive cost, so the constraint binds without being infeasible; this guarantees a finite positive shadow price.

3.5 The baseline policies

Three policies bound the problem and recur throughout. Always-cheap runs the least expensive model on every query: it costs c_min and delivers the cheap model's mean quality. Always-expensive runs the most capable model everywhere: it costs c_max and delivers the top quality but is feasible only if rho is at least c_max. Fixed-fraction sends a constant share of queries, chosen at random, to the expensive model: it can hit any budget between the two extremes but ignores which queries deserve escalation. These three trace out a straight chord in the quality-cost plane; the optimal policy we derive traces the concave frontier strictly above that chord whenever queries are heterogeneous, and the vertical distance between the chord and the frontier is exactly the value a smart router adds. Figure 4 shows the control loop that realizes the optimal policy: a per-query price comparison plus a slow feedback controller that keeps average spend on the budget.

flowchart TD
  X["Query x_t"] --> IDX["Compute q_m(x_t) - lambda_t c_m for each model"]
  IDX --> SEL["Select a_t = argmax"]
  SEL --> RUN["Run model a_t, pay c_{a_t}"]
  RUN --> SPEND["Accumulate spend S_t"]
  SPEND --> CTRL{"S_t ahead of rho*t ?"}
  CTRL -- "yes" --> UP["Raise lambda"]
  CTRL -- "no" --> DOWN["Lower lambda"]
  UP --> IDX
  DOWN --> IDX

4. The optimal routing policy

4.1 The single-price rule

We now derive the optimal policy for the fluid problem of Equation 4. Attach a scalar multiplier lambda greater than or equal to zero to the budget constraint and form the Lagrangian, Equation 5. Because the equality constraints (the z_m(x) summing to one) are per-query and separable, the Lagrangian decomposes across queries once lambda is fixed.

For a fixed lambda the inner maximization over the routing distribution z(x) is, for each query independently, a maximization of a weighted sum with weights q_m(x) minus lambda c_m subject to the weights z_m(x) forming a distribution. The maximum of a linear function over the probability simplex is attained at a vertex: put all mass on the model with the largest coefficient. That gives the pointwise rule, Equation 6.

The multiplier lambda is then set so the budget binds. By LP strong duality, which holds here because Equation 4 is a linear program with a feasible interior point under Assumption A5, there exists a lambda-star at which the primal and dual optima coincide and the budget constraint is tight, Equation 7. Complementary slackness makes this precise: either lambda-star is zero and the budget is slack, or lambda-star is positive and average spend under the pointwise rule equals rho exactly.

The proof is the argument just given: weak duality bounds any feasible primal by the dual; the pointwise rule attains the Lagrangian's inner maximum for every lambda; and strong duality plus complementary slackness pin lambda-star so the bound is met with the budget tight. The only subtlety is integrality. The pointwise rule is deterministic for almost every x, but exactly hitting the budget may require splitting the routing of a single measure-zero-boundary query type between two models; this is the standard single-fractional-item feature of a knapsack LP and contributes nothing to regret at scale. The economic reading is that a fleet of models, an arbitrary query distribution, and a budget collapse into one number, the price of quality per dollar, against which every query is judged locally.

4.2 The two-model margin rule

The two-model case makes the rule concrete and exposes why it is not a confidence threshold. Let model 1 be cheap (cost c_1) and model 2 expensive (cost c_2 greater than c_1). The pointwise rule escalates to model 2 exactly when its scalarized value exceeds model 1's, which rearranges to Equation 8: escalate when the quality gain exceeds the price times the cost difference.

Read this against a confidence threshold. A confidence threshold escalates when the cheap model's self-reported confidence falls below a fixed bar, a statement about q_1(x) alone. The optimal rule escalates on the quality gap Delta q(x), a statement about the difference q_2(x) minus q_1(x), and compares it to a bar, lambda-star times Delta c, that is set by the budget and the cost spread. A confidence threshold is a legitimate approximation only insofar as low cheap-model confidence predicts a large quality gap, which holds when the expensive model reliably rescues the cheap model's failures and fails otherwise. When the two models fail together, low confidence does not predict a large gap, and the confidence threshold escalates queries no model can answer. Figure 5 shows the frontier the price rule traces; Figure 6 shows the geometry of the scalarization that produces it.

4.3 A worked two-model example

A numerical example makes the rule and its consequences concrete. The numbers here are illustrative parameters of an analytical model, not measurements. Suppose a small model costs c_1 equal to 0.1 (in cents per query) and answers correctly with probability that depends on the query, and a large model costs c_2 equal to 1.0 and is uniformly better. Partition traffic into three query types by difficulty: easy (60 percent of traffic), where the small model is right 95 percent of the time and the large 99 percent, so the gap Delta q is 0.04; medium (30 percent), where the small is right 70 percent and the large 92 percent, so the gap is 0.22; and hard (10 percent), where the small is right 30 percent and the large 60 percent, so the gap is 0.30. The cost spread Delta c is 0.9.

Apply the margin rule of Equation 8: escalate a type when its gap exceeds lambda-star times 0.9. As lambda-star rises from zero, types drop out of escalation in increasing order of gap. At a price of lambda-star equal to 0.05, the threshold on the gap is 0.045, so the easy type (gap 0.04) stays on the small model while medium (0.22) and hard (0.30) escalate. That routes 40 percent of traffic to the large model, at an average cost of 0.6 times 0.1 plus 0.4 times 1.0, equal to 0.46 cents per query, and an average accuracy of 0.6 times 0.95 plus 0.3 times 0.92 plus 0.1 times 0.60, equal to 0.906. Raise the price to lambda-star equal to 0.28, threshold 0.252, and only the hard type escalates: 10 percent to the large model, average cost 0.19 cents, average accuracy 0.6 times 0.95 plus 0.3 times 0.70 plus 0.1 times 0.60, equal to 0.84. Each price picks a point on the frontier of Figure 5, and the frontier is the upper envelope of these choices as the price sweeps.

Now contrast the fixed-fraction policy at the same 40 percent escalation budget. It escalates a random 40 percent of every type, so it spends the same 0.46 cents but earns only 0.6 times (0.6 times 0.95 plus 0.4 times 0.99) plus 0.3 times (0.6 times 0.70 plus 0.4 times 0.92) plus 0.1 times (0.6 times 0.30 plus 0.4 times 0.60), which works out to 0.6 times 0.966 plus 0.3 times 0.788 plus 0.1 times 0.42, equal to 0.858. The single-price rule earned 0.906 at the same cost, so the fixed fraction leaves 4.8 accuracy points on the table. That shortfall is the approximation gap of Theorem 3, and it exists because the fixed fraction wastes escalations on easy queries (which barely benefit) and starves hard queries (which benefit most). The gap would be zero if all three types had the same gap, and it grows as the gaps spread, exactly the variance dependence of Equation 11.

The example also shows why a confidence threshold on the small model is a good but imperfect proxy. If the small model's confidence tracks its own correctness, then low confidence correlates with the hard type, and thresholding confidence approximates escalating the high-gap queries. But the correlation is imperfect: an easy query the small model happens to be unsure about (high confidence variance within a type) gets escalated wastefully, and a hard query it is wrongly confident about gets kept. The price rule, which reads the gap directly, has no such leakage; a calibrated confidence router closes most but not all of it, which is the residual curve in Figure 7.

4.4 Three models and the ordering of prices

With three or more models the single price still decides every query, but the geometry of Figure 6 shows how. Add a mid-tier model at cost 0.4 whose accuracy on the three types is 0.97, 0.85, and 0.45. For a given query type the router picks the model maximizing accuracy minus lambda-star times cost. On the easy type at a moderate price, the small model wins because the mid and large models add little accuracy for their extra cost; on the medium type the mid-tier can win if its accuracy-per-dollar beats both neighbors; on the hard type the large model wins because only it lifts accuracy enough to justify the price. As the price rises, each type walks down the fleet from expensive to cheap, and the sequence of switches traces the frontier's kinks. A model that is never the maximizer at any price for any query type is dominated: it lies below the upper concave envelope in the (cost, accuracy) plane and can be dropped from the fleet without loss, the routing analog of a model being off the convex hull that RouterBench computes.^[24] This gives a fleet-pruning rule for free: keep only models that are the quality-per-dollar winner for some price and some query segment.

4.5 The frontier-slope identity

The value of the fluid program as a function of the budget defines the Pareto frontier, Equation 9: Q(rho) is the best expected quality achievable at average spend rho. It is the analytical counterpart of the empirical convex hull that RouterBench reports.^[24]

Two properties follow directly. First, Q is concave in rho: it is the value of a linear program parameterized by the right-hand side of a constraint, and such value functions are concave. Concavity is the formal statement of diminishing returns to budget, and it is what makes a single tangent price meaningful. Second, and centrally, the slope of Q equals the shadow price, Equation 10. This is the envelope theorem (or, equivalently, the fact that the optimal dual variable of an LP is the derivative of the optimal value with respect to the constraint bound).

This identity is the paper's most useful practical output. The shadow price is not only how to route (Equation 6) but how much your budget is worth at the margin (Equation 10). If a router runs at a high lambda, each extra dollar per query buys a lot of quality, so the budget is the binding constraint and should be raised; if lambda is near zero, the budget is slack and can be cut with almost no quality loss. Figure 13 plots lambda-star against rho: it falls steeply where the fleet has cheap quality to buy and flattens once the easy wins are exhausted. A team that instruments lambda has a live, principled signal for the budget decision that no confidence threshold provides.

4.6 The approximation gap of budget-agnostic rules

We can now quantify what a fixed-fraction or budget-agnostic threshold loses. Consider the two-model case and a fixed-fraction policy that escalates a random share phi of queries to hit the budget, that is phi times Delta c equals rho minus c_1. Its expected quality is c_1's plus phi times the mean gap. The optimal policy instead escalates the share of queries with the largest gaps, those with Delta q(x) above the threshold lambda-star Delta c. The difference between escalating the highest-gap queries and escalating a random set of the same size is a covariance, and for the fixed-fraction policy it reduces to an expression governed by the spread of the gap, Equation 11.

The proportionality to the standard deviation of the gap is the content of Theorem 3: the fixed-fraction policy pays a penalty that vanishes when the gap is homogeneous (every query benefits equally from escalation, so which ones you escalate does not matter) and grows as the gap spreads (some queries benefit enormously and others not at all, so escalating the right ones matters greatly). A budget-agnostic confidence threshold pays a smaller version of the same penalty, reduced but not eliminated by the signal it reads, and reduced further by calibration.^[29] Figure 7 plots both penalties against heterogeneity.

The proportionality deserves one more unpacking because it explains a common surprise. Teams often find that a carefully tuned global threshold gets them most of the way to the frontier on some workloads and stalls well short on others, with no obvious difference in how hard they tuned. The gap formula says the difference is not in the tuning but in the workload: on a low-variance workload (queries that benefit similarly from escalation) even a crude fixed fraction is near optimal, so tuning a threshold looks effortless; on a high-variance workload the threshold's residual gap is large and no amount of tuning closes it, because the residual is an approximation error of the threshold class, not an estimation error the tuner can chase. The practical tell is that the marginal return to threshold tuning collapses while the frontier gap stays open, which is the signature of hitting a class floor rather than a data floor, the exact distinction Figure 10 draws. When a team sees this pattern, the correct move is to stop tuning the threshold and start estimating the gap per query, which is the enrichment of the policy class that the price rule makes precise.

4.7 Budget depletion and the dynamic price

The fluid analysis prices an average budget. When the budget is a hard cap over a window that can be exhausted early, the correct object is dynamic: the price should rise as the remaining budget per remaining query falls. This is the exact behavior of the primal-dual algorithm for Bandits with Knapsacks, where the dual variable is updated online to conserve the resource.^[5] Writing S_t for cumulative spend after t queries and treating the price as a slow control variable, the dual ascent that keeps spend on the budget line is Equation 12, an integral controller on the spend error.

The bracket with subscript plus denotes projection onto the non-negative reals, and eta is a step size of order one over the square root of T (the same schedule that yields the square-root-of-T budget regret in Section 5). The qualitative consequence, Figure 8, is that an optimal router becomes more parsimonious late in a billing period if it has been spending ahead of plan: the price rises, the escalation threshold lambda times Delta c rises with it, and fewer queries clear the bar. A fixed threshold cannot reproduce this and will either exhaust the budget early (and then be forced onto the cheap model for the remainder) or leave budget unspent. The dynamic price is what makes the allocation robust to bursty or front-loaded traffic.

4.8 The price as an index, and why one scalar suffices

The single-price rule belongs to a family of results in which a hard sequential-allocation problem reduces to a per-arm index. The Gittins index solves the discounted Bayesian bandit by assigning each arm a reservation value and always playing the arm of highest index, decoupling a joint problem into independent per-arm calculations.^[22] Weitzman's reservation value does the same for sequential search. Our price plays this role for the budgeted routing problem: q_m(x) minus lambda times c_m is an index, and the router plays the arm of highest index. What makes the routing index a single scalar shared across all arms, rather than one number per arm, is that the coupling here is a single budget constraint, and by LP duality a single constraint has a single price. If there were K separate budgets (one per model) the dual would have K prices; if there were budgets on dollars and latency together, two prices. The number of prices equals the number of coupling constraints, and a single spend budget is one constraint, so one price decides everything. This is the deep reason a router does not need a complicated policy: the problem's difficulty is entirely in estimating the qualities, and the allocation on top of the estimates is a one-line index comparison.

5. Learning the policy online: regret

5.1 Feedback model and regret decomposition

Everything so far assumed the qualities q_m(x) known. In deployment they are not; they must be learned from a stream, observing only the chosen model's reward. Two regrets now matter: reward-regret, the quality lost against the optimal price rule with known qualities, and budget-regret, the amount by which cumulative spend can exceed the budget during learning. The total loss decomposes as Equation 13, with the budget violation priced at the shadow price because that is the quality it could have bought.

5.2 An optimistic router with a dual price

Under the realizability Assumption A4, q_m(x) equals the inner product of theta_m with the features. Maintain for each model a ridge-regression estimate theta-hat_m from the queries routed to it and its design matrix V_m, and form the optimistic upper confidence bound of Equation 14, exactly the LinUCB or OFUL index.^[6][13] The router selects the model maximizing the optimistic scalarized value UCB_m(x) minus lambda_t c_m, and updates the price by the dual ascent of Equation 12. Call this PrimalDualLinUCB-Route.

The width beta_t times the feature norm in the inverse-design-matrix metric is the self-normalized confidence radius whose validity is guaranteed by the martingale tail inequality of Abbasi-Yadkori and colleagues.^[13] Optimism does the exploration automatically: a model that has been tried little on queries like x has a wide confidence interval and so a high optimistic value, which pulls the router to try it; as evidence accumulates the interval shrinks and the choice converges to the true price rule.

5.3 Reward-regret bound

The reward-regret of the optimistic router inherits the linear-contextual-bandit rate. The standard OFUL and SupLinUCB analyses bound the sum of confidence widths along the played sequence by the square root of T times the log-determinant of the design matrix, which is of order d times the square root of T up to logarithmic factors, Equation 15.^[13][7] The scalarization by a fixed price does not change the rate, because subtracting the known lambda c_m shifts every model's index by a known constant and preserves the confidence geometry.

The proof is worth seeing in outline because it shows why the rate is what it is. On each query the optimistic router picks the model with the largest UCB-scalarized value, so by construction the chosen model's optimistic value is at least the optimal model's optimistic value, which (because the true value lies below its own upper confidence bound) is at least the optimal model's true value. Rearranging, the per-query reward-regret is bounded by the confidence width of the chosen model on that query, that is beta_t times the feature norm in the inverse-design metric. Summing the widths over T queries and applying the elliptical-potential lemma (the sum of these norms is controlled by the log-determinant of the final design matrix, which grows like d log T) gives a total of order beta_T times the square root of T times d log T, which is d times the square root of T up to logarithmic factors once beta_T is itself of order the square root of d log T. The price subtraction does not enter because lambda c_m is a known constant per model, so it cancels between the chosen and optimal indices. This is the same argument that gives OFUL its bound; the routing problem simply supplies the features and the arms.^[13]

5.4 Budget-regret via the online dual

The price is not known in advance and is learned by the same dual ascent, Equation 12. This is online gradient descent on the one-dimensional dual with a bounded gradient (the per-query spend error, which lies in a bounded range because costs are bounded). Standard online-convex-optimization analysis gives a dual regret, and hence a budget violation, of order the square root of T with a step size of order one over the square root of T, Equation 16.^[18] The budget-regret and reward-regret add, so the total is dominated by the larger, order d times the square root of T.

5.5 Explore-then-commit and epoch-greedy

It is worth seeing why the optimism matters, because a tempting alternative is to explore crudely first and then freeze. Explore-then-commit runs all models on a prefix of n queries to estimate qualities, then commits to the empirical price rule for the rest. Its regret has two terms: the exploration cost, of order n (paying to run every model on n queries), and the exploitation cost, of order T over the square root of n (the residual error of a frozen estimate). Balancing them gives n of order T-to-the-two-thirds and a total regret of the same order, Equation 17. Epoch-greedy, which interleaves shrinking exploration phases, achieves the same T-to-the-two-thirds without needing to know the horizon.^[16] Both are strictly worse than the square-root-of-T of the optimistic router, and Figure 9 shows the separation.

5.6 The lower bound and minimax optimality

The square-root-of-dT rate is not merely what this particular router achieves; it is the best any router can achieve. The contextual-bandit lower bound of Chu and colleagues constructs instances on which every algorithm suffers regret of order the square root of dT, and the linear-bandit lower bound of Dani, Hayes, and Kakade gives the matching order for the stochastic-feedback case, Equation 18.^[7][14] Since the routing reward-regret is bounded above by order d times the square root of T (Theorem 4) and below by order the square root of dT, the optimistic router is minimax optimal in the horizon and the feature dimension up to a factor of the square root of d and logarithmic terms. There is no router, however cleverly engineered, that learns query-dependent qualities materially faster.

5.7 Estimation regret does not close the class gap

The regret above measures the distance to the optimal policy within the class the router searches. It says nothing about a router restricted to a weaker class. This is the crucial practical distinction. A router that only tunes a scalar confidence threshold has two regrets: an estimation regret that its online learning drives to zero at the rates above, and an approximation regret, the Theorem 3 gap between the best threshold and the true price rule, that no amount of data removes. Figure 10 shows the two learners: the single-price rule converges toward the optimum, while the threshold rule converges toward a floor strictly above it. The lesson is that when a router's performance plateaus, the right diagnosis is not always too little data; it may be too weak a rule, and the cure is to enrich the policy class (learn a per-query margin, Equation 8) rather than to collect more traffic. The bandit decomposition tells you which of the two problems you have.

This distinction has a direct budgeting consequence for the team that runs the router. Estimation regret is a one-time cost that amortizes: at a million queries a month, a square-root-of-T learning cost is a vanishing fraction of the value allocated, so a router should be allowed to explore early rather than frozen at launch to a conservative threshold. Approximation regret is a recurring cost that never amortizes: a router stuck in a weak policy class pays the same gap every month forever, so the engineering investment to escape it (a per-query gap estimator) is justified by a permanent, not a transient, return. Confusing the two leads to the two classic mistakes: freezing a router too early to avoid exploration cost (paying estimation regret you did not need to) and endlessly A/B-testing thresholds against a class floor (chasing an approximation gap that tuning cannot close). The bandit view prices both correctly and says the amortizing cost is cheap while the recurring one is what to engineer against.

5.8 A Bayesian alternative and why the rate is the same

Optimism is not the only way to explore. A Bayesian router maintains a posterior over each model's quality parameter, samples a parameter from each posterior, and routes as if the sampled values were the truth, which is Thompson sampling adapted to the scalarized reward.^[9] For linear contextual rewards this achieves regret of order d-to-the-three-halves times the square root of T, a factor of the square root of d worse than OFUL in the worst case but often better in practice because the posterior sampling matches the problem's actual uncertainty rather than a worst-case ellipsoid.^[15] For the budgeted case a Thompson variant handles the knapsack directly.^[21] The reason both optimism and sampling give a square-root-of-T rate, while explore-then-commit gives T-to-the-two-thirds, is that both adapt their exploration to the data: they stop exploring a decision as soon as the evidence resolves it, whereas a fixed exploration phase keeps paying for information it no longer needs and then stops paying just when a rare query type would benefit from more. The practical choice between them is engineering, not asymptotics: optimism needs a confidence-width calculation, sampling needs a posterior, and both need the same quality features. The dual price controller of Equation 12 sits on top of either unchanged, because it acts on realized spend, not on the exploration mechanism.

5.9 Per-segment budgets and the price function

Many deployments do not want one global budget but several: a spend cap per customer, per product surface, or per topic. This is not a cosmetic change, because it turns the single scalar price into a price function, one lambda per segment, and couples the segments only through any shared resource. If the segments have independent budgets, the problem decomposes: each segment runs its own single-price rule with its own lambda, and the analysis of Sections 4 and 5 applies per segment. If the segments share a global budget but also have per-segment floors or caps, the dual has one price for the global constraint plus one per active segment constraint, and the router routes on quality minus the sum of the applicable prices times cost. The regret picks up a factor for the number of simultaneously binding constraints, which is at most the number of segments, but the structure is unchanged: a linear program with a handful of coupling constraints has a handful of prices, and the router compares indices. The practical caution is that fine-grained per-segment budgets fragment the data each price is estimated from, so the estimation regret rises as segments shrink; there is a bias-variance tradeoff in how finely to slice the budget that mirrors the tradeoff in how finely to slice an eval suite. A team should make the segments as coarse as the governance requirement allows.

6. The value of context and heterogeneity

Sections 4 and 5 establish how to route and how fast to learn. This section answers when a contextual router is worth building at all, and the answer is a single measurable quantity. Recall from Theorem 3 that the gap between a fixed fraction and the optimum scales with the spread of the quality gap Delta q across queries. The same quantity governs the value of context in the positive direction, Equation 19: the quality a contextual router gains over the best context-free fraction is proportional to the variance of the gap.

The interpretation is intuitive once stated. If every query benefits equally from escalation (the gap is the same for all), then which queries you escalate does not matter, only how many, and a fixed fraction is optimal: context is worthless. If the gap is highly variable (some queries are trivial for the cheap model and some are impossible), then picking the right queries to escalate is everything, and a contextual router that reads the gap captures value a fraction cannot. Figure 11 plots this relationship. It has a direct operational use: before investing in a learned router, estimate the variance of the quality gap on a held-out sample (run both models on a few hundred queries and measure the spread of the per-query quality difference). That variance is the ceiling on the router's payoff, and if it is small the engineering will not repay itself.

This explains a pattern in the published record that a single headline number obscures. FrugalGPT reports up to 98 percent cost reduction on some tasks and far less on others.^[1] In the bandit reading, the tasks where a cascade or router saves the most are precisely those with a large easy majority the cheap model handles and a small hard minority it cannot, that is, high heterogeneity in the quality gap. Tasks where the models tend to succeed or fail together have a low-variance gap and little room for routing to help, whatever the average accuracies. The correlation of model errors is the same phenomenon seen from the other side: highly correlated errors mean the gap is small on most queries (both right or both wrong) and large on few, which is low variance in Delta q. The benefit-rate view and the variance view coincide.

It is worth making the benefit-rate identity explicit, because it is the quantity a team can actually measure and it bounds the achievable saving directly. Define the benefit rate as the probability that the cheap model is wrong and the expensive model is right, that is the fraction of queries that escalation actually rescues. Write p_1 for the cheap model's marginal accuracy, p_2 for the expensive model's, and let their error indicators have correlation r. A short calculation gives the rescue probability: it equals p_2 minus the probability that both are right, and under a correlation r between the correctness events the joint-right probability rises with r, so the rescue probability falls with r. In the two extremes, independent errors give the largest rescue set (of size roughly p_2 times one-minus-p_1) and perfectly correlated errors give the smallest (only the queries the expensive model uniquely fixes). The consequence for budgeting is sharp: to reach a target accuracy you must escalate at least the rescue set, so the minimum escalation fraction, and therefore the minimum cost, is set by the error correlation, not by the individual accuracies. This is the mechanism behind the spread in the published savings. A task where the cheap model is competent and its errors are uncorrelated with the expensive model's (a large, cheap rescue set) admits deep down-routing, which is how FrugalGPT reaches its highest cost reductions;^[1] a task where the models fail together admits little. The variance of the gap and the error correlation are two views of the same heterogeneity, and either one, measured on a few hundred held-out queries with both models run, tells a team the ceiling on what routing can buy before they build anything.

One caution attends the measurement. The variance of the gap is estimated from a noisy quality proxy, and proxy noise inflates the apparent variance: two models that actually agree can look like they disagree if the quality score is noisy, which overstates the routing opportunity. The correction is the same law-of-total-variance decomposition used to separate item difficulty from measurement noise in eval design: the observed variance of the measured gap equals the true variance of the gap plus the variance of the measurement error, so the routing-relevant quantity is the former, obtained by subtracting an estimate of the proxy noise (for example from repeated scoring of the same pair). A team that skips this correction will overinvest in a router for a task whose true gap variance is small and whose apparent variance is mostly scoring noise. The honest version of the recipe is therefore: run both models on a sample, score each answer several times to estimate scoring noise, and use the noise-corrected variance of the gap as the ceiling on routing value. This connects the routing-value question to the measurement-quality question, and a router built on a noisy proxy inherits the proxy's limits, a theme we return to in the threats of Section 9.

7. Comparison to learned routers

The strongest deployed routers are not fixed thresholds but learned classifiers, and the bandit framework clarifies exactly what they are and when they are optimal. RouteLLM trains a model on preference data to predict a win probability for the strong model over the weak one and routes on that prediction.^[2] Hybrid LLM trains a deferral classifier to predict quality drop.^[3] Both are, in the language of Section 4, estimators of the quality gap Delta q(x) (or a monotone transform of it). A router that estimates Delta q and thresholds it is implementing the two-model margin rule of Equation 8; the only question is where it sets the threshold. If the threshold is chosen to make average spend equal the budget, it equals lambda-star times the cost spread and the router sits on the frontier. If the threshold is a hand-picked constant unrelated to the budget, the router sits off the frontier by the Theorem 3 gap. Equation 20 makes the correspondence exact: a win-probability router with threshold p-star is optimal precisely when p-star maps through the gap's distribution to the budget-balancing quantile.

This reframes the engineering choice. The hard part of a router is not the decision rule, which is a one-dimensional threshold on an estimated margin, but two things the bandit analysis foregrounds: estimating Delta q(x) well (a supervised-learning problem whose error feeds the reward-regret) and tying the threshold to the budget through lambda (a control problem the dual solves). MetaLLM is the cleanest existing instance of the bandit framing, routing with an explicit multi-armed bandit and a cost-adjusted reward, and reporting up to 60 percent cost reduction with a small accuracy gain.^[4] Under our analysis its reward is exactly the scalarized q minus lambda c, and its regret, were it analyzed, would follow the rates of Section 5. LLM Bandit generalizes the reward to encode a user preference chosen at inference time, which in our terms is a per-request lambda.^[25] Figure 12 collects the reported operating points of the main systems; every one is a point on or inside the frontier of Figure 5.

The comparison also clarifies what a learned router should and should not be asked to do. It should estimate the quality gap as accurately as possible, because that estimate feeds the reward-regret and is the part that genuinely benefits from better features, more training data, and calibration. It should not be asked to internalize the budget, because the budget is a moving target (traffic mix and spend caps change) that a static classifier cannot track; the budget belongs to the price, which a controller adjusts online. Systems that bake a fixed threshold into a trained router conflate these two and must retrain whenever the budget changes; systems that separate a trained gap-estimator from an online price controller adapt to budget changes for free. This separation of concerns, a learned estimator plus a controlled price, is the architecture the bandit analysis recommends, and it is the pattern MetaLLM's online bandit and RouteLLM's threshold sweep each approximate from opposite directions.^[4][2]

8. Discussion

Three points deserve emphasis because they cut against common practice. The first is that one scalar suffices. It can seem that routing across many models with heterogeneous costs and a nonstationary query mix must need a complex policy, but Theorem 1 shows the budget collapses the whole problem into a single price. The complexity that remains lives entirely in estimating the qualities q_m(x); the decision rule given the estimates is trivial. This is why a well-built router is not much more code than a threshold: it is the same one-comparison-per-query decision with the comparison set correctly and the price maintained by a two-line controller.

The second is that context helps only through heterogeneity. A router that reads rich features but faces a homogeneous quality gap cannot beat a fixed fraction, no matter how good its features, because there is nothing to sort. This is a useful corrective to the instinct that more features always help. The quantity to measure first is the variance of the gap (Equation 19), and only if it is large is feature engineering worthwhile. It also predicts where routing will disappoint: on tasks where models mostly agree, whatever their average quality, routing saves little.

The third is that the shadow price is a governance instrument, not just a routing knob. Because its value is the marginal quality per dollar (Theorem 2), it belongs on the same dashboard as spend and quality. A finance owner who sees lambda trending up knows quality is getting expensive at the margin and can decide whether to fund it; an engineering owner who sees it near zero knows the budget is slack. This connects routing to the broader problem of AI cost governance, where the goal is to spend frontier tokens only when they pay. Multi-metric budgets (a dollar budget and a latency budget together) generalize cleanly: each constraint gets its own price, the scalarization becomes q minus lambda-dollars times cost minus lambda-latency times latency, and the vector of prices is maintained by the same dual ascent, exactly the convex-knapsack generalization of the theory.^[19] For deeper treatment of the cost-governance side see the companion work on autonomous cost control and on the routing-versus-cascade choice linked in Section 10.

A fourth point concerns the relationship between routing and its two neighbors, cascading and ensembling, because teams often conflate them. Routing (this paper) chooses one model per query in parallel and pays for exactly one. Cascading runs models in sequence, cheapest first, and stops when an answer looks good enough, so it may pay for several on a hard query but skips the expensive ones on an easy query; its optimal policy is a stopping rule whose reservation value is the sequential cousin of our price. Ensembling runs several models and combines their answers, paying for all of them to reduce variance. The three occupy different points on a cost-quality surface: routing minimizes cost for a target quality when a single model can be identified as sufficient per query; cascading wins when a cheap confidence check is reliable and reruns are cheap relative to escalation; ensembling wins when no single model is reliable and the combination genuinely beats its parts. The bandit framing unifies their control: each is a policy over the same arms under the same budget, and the single price is the right threshold for routing, a reservation value for cascading, and a per-model inclusion price for ensembling. A production system often layers them (route to a cascade, ensemble at the top tier), and the prices compose.

Finally, the analysis reframes a debate in the routing literature about whether to route before or after seeing a first answer. Pre-generation routing (predict difficulty from the query alone, then pick a model) is a contextual bandit on the query features. Post-generation routing (run the cheap model, read its answer and confidence, then decide) adds a feature, the cheap model's own output, that is highly informative about the gap but costs a cheap-model call to obtain. In our terms this is a feature-acquisition choice: the post-generation feature shrinks the variance of the gap estimate (and so the reward-regret) at the price of always paying c_1. Whether it is worth it is a budgeted decision of the same kind the paper analyzes, one level up, and the answer again turns on how much the extra feature reduces the gap variance relative to its cost.

A last observation ties the theory back to why the empirical routers succeed at all. The published saving numbers, an 85 to 98 percent cost reduction at near-frontier quality, are only possible because real query distributions are heterogeneous: a large easy majority the cheap model handles and a small hard minority it cannot.^[1][2] The single-price rule is the mechanism that converts that heterogeneity into savings, by spending the budget precisely on the hard minority. A workload without the heterogeneity would show none of these headline numbers, whatever the router, and the analysis makes that ceiling explicit rather than leaving it as a surprise discovered after deployment. The lesson for a technical leader is to read a reported routing saving as a joint statement about a router and a workload, and to expect the saving to transfer to a new workload only insofar as the new workload shares the old one's gap variance. The number is not a property of the router alone.

9. Threats to validity and limitations

The results are theorems from assumptions plus a synthesis of cited numbers, and both have limits we state plainly.

The reward is not observed cleanly online. The single most important limitation is that quality q_m(x) is rarely available as an honest online signal for open-ended generation. Exact-match tasks (classification, structured extraction, code that runs) do give a reward, and there the analysis applies directly; MetaLLM's reported results are on exactly such tasks.^[4] For free-form generation the router must use a proxy (a self-evaluation score, an LLM judge, a preference model), and that proxy is biased and noisy. A biased reward shifts the estimated qualities and hence the price, and the regret bounds of Section 5 degrade by the proxy's bias, which they do not model. Bounding the bias of a quality proxy is an open problem we flag in Section 11, not one we solve.

Realizability and feature quality. Theorems 4 to 6 assume q_m(x) is linear in a known feature map (A4). Real quality is not exactly linear in any fixed features, and misspecification adds a bias term to the regret that the linear analysis omits. The rates are the right reference and the practice (a learned quality head on an embedding) approximates the assumption, but the constant hidden in the order notation depends on how well the features capture difficulty, which varies by domain.

Nonstationarity. Assumption A3 (i.i.d. contexts) is violated by query drift, model updates, and feedback loops (a router that down-routes a topic stops collecting data on it). Drift makes the estimated qualities stale and the price mis-set. The stochastic analysis does not cover it; the adversarial machinery (EXP4-style) covers it at the cost of a worse rate of the square root of KT log N and the loss of the clean single-price structure.^[17] A practical router needs a forgetting mechanism whose analysis is outside our scope.

Costs have variance. Assumption A1 treats cost as known and deterministic, but output-token count (and therefore dollar cost) is random and correlated with the query. This turns the knapsack into a stochastic-consumption knapsack, which the Bandits with Knapsacks theory does handle, but our clean single-price derivation used deterministic costs; with random costs lambda multiplies expected cost and a second-order term appears.^[5]

The frontier is an expectation. Q(rho) and its slope are expected quantities. A given billing window realizes a random spend and quality around them, and the concavity and slope identity hold for the expectation, not path-wise. Tail control on spend is the budget-regret of Theorem 5, which bounds the overshoot in order but not its distribution.

The numbers are cited, not measured. Every empirical figure (FrugalGPT's 98 percent,^[1] RouteLLM's 95 percent and 85 percent,^[2] Hybrid LLM's 40 percent,^[3] MetaLLM's 60 percent^[4]) is quoted from its source and cross-checked, but the sources differ in benchmark, model vintage, and quality definition, so Figure 12 is a synthesis of claims and not a controlled comparison. We ran no experiments; the analytical figures illustrate the theory's shape, not measured performance.

Strategic and adversarial inputs. The analysis assumes queries arrive from a fixed distribution that does not react to the router. In some deployments the input source is strategic: a user who learns that verbose or oddly formatted queries get escalated to the expensive model can manufacture escalation, and an adversary who controls part of the feature can push the router off its budget. This is a routing analog of the confidence-signal gaming seen in learned rankers, and it is outside the stochastic model. The adversarial-bandit machinery (EXP4 and its budgeted variants) bounds the damage at a worse rate,^[17] but a production router that faces adversarial inputs needs an explicit robustness layer (rate limits, feature sanitization, a floor on how much any single source can escalate) that the clean theory does not supply.

Two models is the clean case. The margin rule and the approximation-gap formula are cleanest for two models; with a large fleet the frontier has many kinks and the price picks among many indices, which is still a single scalar but whose relationship to any one pairwise gap is less transparent. The single-price optimality (Theorem 1) holds for any fleet size, but the closed-form gap of Theorem 3 is stated for two models, and its multi-model generalization is a sum over adjacent frontier segments that we sketch but do not fully develop.

10. Practical implications

The theory turns into a short, ordered procedure for anyone building or tuning a router. It is deliberately concrete.

The price controller is the one component that may be unfamiliar, so it is worth spelling out. Keep a running estimate of the target spend rate rho (dollars per query, equal to the budget divided by expected volume) and the actual spend rate over a recent window. Each period, adjust the price by a small step proportional to the difference: if actual spend exceeds target, raise lambda so the router escalates less; if it lags, lower lambda so the router escalates more. This is a standard integral controller, and the step size of order one over the square root of volume from Equation 16 is what keeps it stable and gives the square-root-of-T budget guarantee. Two practical refinements matter. First, clip lambda at zero (a negative price would pay to escalate, which is never optimal) and at a ceiling (an infinite price would never escalate, which starves quality). Second, if the budget resets per window (per month, per day), let lambda drift up as the remaining budget per remaining query falls, which is the depletion dynamic of Equation 12 and Figure 8; a controller that ignores depletion will overspend early and starve late. The whole controller is a few lines of code around the existing routing call, and it replaces the recurring manual exercise of re-tuning a threshold when the bill moves.

1. Route on a price, not a threshold. Replace any fixed confidence threshold or fixed escalation fraction with the rule of Equation 6: pick the model with the best estimated quality minus lambda times cost. For two models this is the margin rule of Equation 8.
2. Tune lambda with a controller. Maintain the price with the dual ascent of Equation 12: raise it when cumulative spend runs ahead of the budget line, lower it when it runs behind. Use a step size of order one over the square root of expected volume. Do not re-derive thresholds by hand.
3. Calibrate the quality signal first. A price on a miscalibrated score prices the wrong axis; apply temperature scaling or an equivalent before routing.^[29] Prefer signals the model can actually support, and validate them off-distribution.^[30]
4. Measure the gap variance before building a router. Run both models on a few hundred held-out queries, compute the per-query quality difference, and look at its variance (Equation 19). If it is small, a fixed fraction is near-optimal and a learned router will not repay itself; if large, invest in estimating the margin well.
5. Learn qualities optimistically. If qualities are estimated online, use an upper-confidence rule (Equation 14) and expect a square-root-of-T learning cost; avoid a fixed exploration phase that freezes a bad estimate at the T-to-the-two-thirds rate.
6. Watch the price as a budget signal. A persistently high lambda means quality is expensive at the margin and the budget should be raised; a near-zero lambda means the budget is slack and can be cut (Theorem 2). Put lambda on the cost dashboard.

These implications connect to adjacent TMLS work. The routing-versus-cascade decision and the confidence-signal design are treated in Model Routing and Cascades; the sequential (stop-or-escalate) cousin of this parallel choice is analyzed as optimal stopping in Regret Bounds for Sequential Model Cascades; the make-or-buy economics that set the cost c_m for on-prem versus hosted models are in Hybrid Inference Economics; and the budget-governance loop that owns lambda in production is in Agentic FinOps. On the capability side, the cost-and-value framing sits in AI strategy and value, the spend-and-quality instrumentation in LLMOps and observability, and the routing of models inside larger agent loops in agentic systems.

It is equally worth stating when not to route, because the analysis makes the negative case precise. If the measured, noise-corrected variance of the quality gap is small, a fixed fraction is near optimal and a learned router is not worth its complexity; ship the fraction and spend the engineering elsewhere. If there is no honest online quality signal (open-ended generation with no cheap verifier and no trustworthy judge), the reward the router needs is unavailable, and a router trained on a biased proxy can quietly optimize the proxy rather than quality, which is worse than a conservative fixed policy; in that case invest first in a quality signal and only then in routing. And if the budget is not actually binding (the cheapest acceptable policy already fits under the budget), the shadow price is zero and there is nothing to allocate; route everything to the model that meets the quality bar and move on. The single most useful habit the theory encourages is to check these three conditions (gap variance, signal honesty, budget bindingness) before building anything, because each of them, if unmet, tells you the router will not pay, and each is cheap to check relative to the cost of building and operating a router that does not.

11. Open problems and future work

Several questions are left open by this analysis and matter for practice. First, and most important, is an online quality proxy with a provable bias bound: the whole regret story assumes an observable reward, and for open-ended generation the reward is a biased judge, so a bound on how much judge bias distorts the price would close the largest gap between theory and deployment. Second is regret under quality drift: a router with a forgetting mechanism that provably tracks a slowly changing quality function, extending the stationary analysis to the nonstationary regime without collapsing to the adversarial rate. Third is contextual budget feasibility: our budget is an unconditional average, but deployments often want per-segment budgets (a spend cap per customer or per topic), which turns the single price into a price function and changes the feasibility geometry. Fourth is the joint routing-and-cascade problem: this paper routes to one model in parallel, while a cascade tries models in sequence, and the optimal policy over the union (route, then possibly escalate) couples the two and is not a single price. Fifth is off-policy evaluation of routers from logged traffic, so a new price or a new quality estimator can be scored without live experiments, which the partial-feedback structure makes nontrivial. Finally, the multi-metric frontier (dollars, latency, and carbon together) has a vector price whose dynamics under coupled budgets are only sketched here.

Two further directions are worth naming because they connect the clean theory to the messier production reality. The first is the interaction between routing and the models themselves improving: a router tuned to a fleet's current qualities is stale the moment a model is upgraded, and the price and the gap estimates must both re-adapt. The stationary analysis treats the fleet as fixed; a theory of routing under a slowly improving fleet, where the arms' reward functions drift upward at different rates, would tell a team how often to re-estimate and how to avoid locking traffic away from a model that has quietly gotten better. The second is the composition of routing with the generation-time compute decisions inside each model: extended-thinking models let the same model spend more or fewer reasoning tokens, so the real action space is not just which model but how much compute to grant it, a joint routing-and-budget-within-model problem whose optimal policy is a two-level price (one across models, one across thinking depth) that the test-time-compute results suggest is worth the added complexity.^[28] Both directions keep the single-price backbone and extend the action space it prices over.

Frequently asked questions

Glossary

Contextual bandit

A sequential decision problem in which, each round, a learner observes features, chooses one of several actions (arms), and receives a reward for the chosen action only. The model for routing when each query carries features.^[6]

Bandits with knapsacks

A bandit in which each pull consumes limited resources and play is constrained by budgets. Its optimal policy can beat the best fixed arm, which is why routing under a budget is an allocation problem.^[5]

Regret

The cumulative shortfall of a policy against the best policy in hindsight. Reward-regret measures lost quality; budget-regret measures budget overshoot during learning.

Shadow price (lambda)

The scalar dual variable of the budget constraint, measured in quality per dollar. It is both the routing threshold (Equation 6) and the marginal value of the budget (Theorem 2).

Single-price rule

Route each query to the model maximizing quality minus lambda times cost. The regret-optimal policy under a spend budget (Theorem 1).

Quality gap (Delta q)

The difference in quality between the expensive and cheap model on a query. Its variance across queries governs the value of a contextual router (Equation 19).

Approximation gap

The quality a budget-agnostic rule loses relative to the single-price optimum; fixed by the policy class, not removable by more data (Theorem 3).

Optimism (UCB)

Acting on an upper confidence bound of each arm's reward, which explores automatically and gives the square-root-of-T regret rate.^[13]

Pareto frontier

The set of best-achievable quality-cost operating points, traced by the single-price rule as the budget varies; the analytical counterpart of RouterBench's convex hull.^[24]