{"id":"8e0aec68-cbf5-4736-b160-a926522632f5","arxiv_id":"2607.23765","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"LLM routing under a workload-level expected-cost budget is cast as a constrained contextual bandit; WR-Offline/Online use adaptive LP and achieve O(√T) end-to-end regret when costs and rewards are learned online.","lead":"WISERouter routes each LLM query to one model under a single workload budget, not a per-query cap, using constrained contextual bandits and adaptive linear programs. It offers offline and online variants, an O(√T) regret bound for the online case, and better budget adherence than prior routers on RouterBench and SWE-Bench.","discovery_kind":"new_method","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"Theorem 5.3's proof sketch substitutes \"correctly ordered estimates\" for the \"known statistics\" that Theorem 5.1 actually requires; residual estimation error in (ū, c̄) perturbs the LP solution and the budget accounting itself, and no appendix bounds these terms — the O(√T) end-to-end claim is unpro","rationale":"The reader's weakest assumption (intra-cluster homogeneity, i.i.d. arrivals) is a real modeling limitation, but it is stated openly in §4.1/§7 and Appendix A, and the ablations (H.4, H.7) engage it honestly — it bounds where the theory transfers, not whether the stated results hold. My concern is different and more load-bearing for contribution (ii): the proof of the paper's flagship theorem does not close as written. Theorem 5.1 covers ALP with exact statistics; WR-Online's exploitation uses estimates whose errors (constant-order, since exploration is only O(log T)) propagate into the LP solution values and into the budget accounting, which itself runs on ĉ rather than realized costs. Neither error term is bounded anywhere in §5 or Appendices C–G — Theorem 5.3 has no full proof, only the sketch that conflates correct ordering with known statistics. If the concrete test shows per-round value perturbation Θ(t) or expected budget violation, the O(√T)/O(log T) claim needs either a new analysis (e.g., Lipschitz-value arguments plus drift control on the b-update) or a weakened statement. The empirical contributions (WR-Offline's budget adherence, training-data reduction, simulation trends) are unaffected, so this does not warrant rejection outright: the verdict should stay CONDITIONAL, but the condition should be sharpened from the reader's artifact/fairness items to \"provide a complete proof of Theorem 5.3 accounting for value perturbation and estimated-cost budget tracking, or demonstrate numerically that these terms are negligible.\" If that check fails, the theoretical claim should be downgraded, which would push the verdict toward REJECT for the paper as currently framed, since the end-to-end regret bound is a headline contribution.","tokens_in":26198,"tokens_out":6196,"duration_ms":124455,"concrete_test":"Two-part check. (a) Numerical sensitivity: treat RouterBench's fitted (û, ĉ) as ground truth; generate perturbed statistics within Lemma 5.2's concentration radius t = L/(8√2) that preserve all ξ orderings but adversarially shift ĉ; solve LP_{T,B} under true vs. perturbed stats and record the per-round value gap and the true-cost drift Σ(c − ĉ) under the perturbed policy. If the per-round value gap is Θ(t) or the budget drift is Θ(t·T), Theorem 5.3 cannot follow from Theorem 5.1 and the proof is incomplete. (b) Simulation: extend Appendix H.8 to T ∈ {1500, 3000, 6000, 12000} at a non-boundary ρ, log (i) regret growth exponent and (ii) E[Σ S_t] − B across seeds; linear regret growth or positive expected overspend confirms the concern.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central theoretical contribution is Theorem 5.3 (end-to-end O(√T)/O(log T) regret with both rewards and costs estimated). Its entire proof is the sketch in §5: \"When rankings are correct, the exploitation phase runs ALP with correctly ordered statistics and incurs the regret from Theorem 5.1.\" But Theorem 5.1 is explicitly stated for \"ALP with known statistics.\" Correct ordering of the ratios ξ (Lemma 5.2's deliverable) is not the same as correct statistics, and the gap matters through two channels the sketch never analyzes:\n\n(1) Solution-value perturbation. The ALP/LP solution is a greedy threshold: probabilities are 1 up to index ĩ(ρ), then fractional with (ρ − Q_{ĩ})/(π_j c̄) at the boundary pair. The cumulative cost masses Q_i and the fractional weight depend on the values of c̄, not just their order. Under Lemma 5.2's good event, estimates concentrate only to radius t = L/(8√2), where L = (∆c_min)²∆ξ_min is a constant in T (exploration length is O(log T), so per-pair error does not vanish). A worst-case systematic perturbation within this radius shifts the fractional allocation and the per-round realized expected reward/cost by O(t) every round — an O(t·T) = O(T) contribution, which would swamp the claimed O(log T) (non-boundary) and O(√T) (boundary) bounds. The text's remark that \"smaller separations imply misorderings are less consequential\" addresses ordering errors, not value perturbation of correctly ordered solutions.\n\n(2) Budget accounting with estimated costs. Both Algorithm 1 (line 5) and Algorithm 2 (line 11) decrement b by ĉ_{j,A}, not by realized cost S_t. The constraint in §3.1 is on E[Σ S_t] with true costs. Enforcing Σ ĉ ≤ B guarantees E[Σ S_t] ≤ B only if ĉ = c on the deployment distribution; conditioned on Lemma 5.2's good event the bias can be a systematic Θ(t) per round, i.e., Θ(t·T) cumulative true-cost overshoot. Feasibility of WR-Online w.r.t. its own constraint — the premise making regret-to-oracle meaningful — is never established. A","agreement_with_reader":"disagree"},"referee_report":{"model":"moonshotai/kimi-k3","summary":"The paper formulates workload-budget-constrained LLM routing as a constrained contextual bandit (CCB): query embeddings are clustered into a finite context set, and Adaptive Linear Programming (ALP, Wu et al. 2015) converts the remaining workload budget into a per-round constraint at each step. Two variants are proposed: WR-Offline, which estimates cluster-level reward/cost statistics from a dense historical dataset and adapts to new budgets without retraining; and WR-Online, an ε-first scheme that jointly estimates rewards and costs under the same shared budget, then exploits via ALP. The main theoretical claim is Theorem 5.3: end-to-end regret of O(log T) (non-boundary) and O(√T) (boundary) under a sufficient exploration condition (Lemma 5.2), whose proof uses a cross-product sign test to avoid random denominators. Experiments on RouterBench and SWE-Bench show WR-Offline competitive or better than FrugalGPT, CascadeRouting, MetaLLM, and SingleBest at tight budgets, with near-exact budget utilization and ~5,900× lower training latency; WR-Online matches offline methods with ~90% less supervision data.","tokens_in":26636,"tokens_out":9281,"duration_ms":221543,"significance":"If the theory is repaired, the contribution is meaningful: the workload-level (rather than per-query) budget formulation is well-motivated for API-quota deployments, the ALP reduction gives a practical, retraining-free mechanism for adapting to new budgets, and the extension of ε-first ALP to jointly unknown rewards and costs under a single shared budget — including the cross-product concentration argument in Lemma 5.2 and explicit failure-probability bookkeeping — is a genuine technical step beyond Wu et al. [40], which assumes known costs. The empirical package is solid for a systems-oriented claim: two public benchmarks, fixed 50:50 splits, five seeds with means±std, budget-utilization analysis, latency comparisons, a static-LP ablation isolating the adaptive constraint, robustness ablations over J, embeddings, and clustering algorithms, and a controlled simulation. The 90% supervision reduction for WR-Online and the 5,900× training-latency improvement are practically significant. However, the headline theoretical claim (Theorem 5.3) currently has a load-bearing gap, detailed in Major Comment 1, which tempers the overall assessment until addressed.","major_comments":[{"comment":"§5, proof sketch of Theorem 5.3 (and its reliance on Theorem 5.1/D.1): the inference 'correct ordering of ξ ⇒ exploitation incurs the regret of Theorem 5.1' does not hold as stated, and the missing term appears to be O(T), not negligible. Theorem 5.1 is explicitly for ALP with KNOWN statistics: its regret is E[v(ρ)] − E[v(b/τ)] where v is evaluated at the true (u,c). Under Lemma 5.2's good event, estimates concentrate only to the constant radius t = L/(8√2) (exploration is O(log T), so per-pair error does not vanish with T). With correct ordering, the greedy threshold structure is preserved, but the fractional boundary allocation p̃ = (b/τ − Q̃_ĩ)/(π_j c̃) and the cumulative masses Q̃_i depend on the VALUES of c̄, not only their order, and Algorithm 2 freezes (ū,c̄) after exploration. A within-radius perturbation therefore shifts the per-round realized expected reward by O(t·Δη/(π_min·Δc","section":null}],"minor_comments":[],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"Punchline: the practical framing is good and the offline system is clean; the headline O(√T) claim for WR-Online is not fully closed. A referee will care about both.\n\nWhat is actually new is not “bandits for routing” (MetaLLM, PILOT, etc. already live there). It is (i) enforcing a single workload-level expected budget via adaptive LP so you can change B at inference without retraining, and (ii) pushing Wu et al.’s ε-first ALP into the regime where both reward and heterogeneous cost are learned online under that same shared budget, with an explicit ordering lemma via cross-products. WR-Offline’s budget adherence and the no-retrain story are the parts I would actually use. Experiments on RouterBench/SWE-Bench are honest enough: means±std, remaining-budget plots, and a clear win at tight budgets; the 90% data cut for WR-Online is the right comparison axis.\n\nSoft spots, in proportion. The stress-test on Theorem 5.3 lands. Lemma 5.2 only buys correct ξ-ordering w.h.p. under O(log T) exploration; Theorem 5.1 needs known (u,c). The sketch jumps from “order correct” to “ALP regret applies.” Residual error is controlled to a fixed radius t ~ L, not vanishing in T, so solution-value perturbation and the fact that Algorithms 1–2 debit b by ĉ rather than realized S are not bounded. That can spoil both the claimed O(log T)/O(√T) and feasibility w.r.t. E[Σ S]. This is a writeup/proof gap, not a fake result—but it is load-bearing for the main theoretical claim. Secondary: cluster homogeneity is assumed while intra-cluster reward variance is ~0.2; CascadeRouting gets noisified ground truth on RouterBench; CLT is derived then abandoned. None of that sinks the method paper.\n\nMath chain through the oracle bound and the ratio lemma looks auditable; citation pattern is appropriate (Wu, Badanidiyuru, FrugalGPT, RouteLLM). No code/artifacts in the text.\n\nWho it is for: people building multi-LLM gateways under monthly quotas, and bandit folks who care about shared-budget exploration. Worth a serious referee. I would engage, ask them to either bound the estimation gap through the LP and the true-cost constraint or soften the end-to-end claim to “ordering + empirical.” Not a desk reject.","headline":"Useful workload-budget routing with a real but incomplete end-to-end regret story—the ordering lemma is fine; equating it to known-stats ALP is not.","tokens_in":27760,"tokens_out":626,"would_cite":true,"duration_ms":24908,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"LLM routing under a single workload budget can be cast as a constrained contextual bandit and solved with adaptive linear programming, meeting the global cost cap without per-budget retraining.","keywords":["LLM routing","workload budget","constrained contextual bandit","adaptive linear programming","online learning","cost-aware inference","regret bound"],"falsifier":"On a held-out stream with the same models and a fixed workload budget B, measure whether WR-Offline’s total spend stays within B while average quality exceeds FrugalGPT, CascadeRouting, MetaLLM, and SingleBest at the tightest budgets; if it overspends or underperforms those baselines, or if raising intra-cluster reward variance collapses the gains, the central claim fails.","tokens_in":27288,"feed_emoji":"🔀","tokens_out":970,"duration_ms":23964,"temperature":0.7,"pith_summary":"Using the strongest language model for every query is too expensive at scale, yet fixed per-query cost caps and dense supervised training leave money on the table and require expensive data. This paper argues that routing should instead maximize total quality subject to one expected cost budget over the whole workload. It turns that problem into a constrained contextual bandit: each query embedding is a context, each model is an arm, and quality and cost are the observed reward and spend. After clustering embeddings into a finite context set, Adaptive Linear Programming converts remaining budget into a per-step average and picks a model without retraining when the budget changes. An offline version uses historical statistics; an online version explores under the same shared budget and is proved to have sublinear regret. On RouterBench and SWE-Bench the offline router beats prior selectors at tight budgets and stays closer to the cap, while the online router matches them with far less training data.","feed_headline":"One workload budget routes LLMs without retraining","feed_subtitle":"Adaptive linear programming meets the global cost cap and cuts training data by up to 90%.","key_machinery":"Adaptive Linear Programming (ALP): at each step it solves a small LP that turns remaining budget b over remaining rounds τ into the average constraint b/τ, then samples a model from the resulting probabilities; WR-Online wraps ALP in an ε-first exploration phase that estimates both rewards and costs under the same budget B.","core_discovery":"Workload-constrained LLM routing is a constrained contextual bandit that Adaptive Linear Programming can solve: WR-Offline estimates reward and cost once from history and re-solves a lightweight LP at each step so any new global budget is met without retraining, and WR-Online jointly learns those statistics under one shared budget with end-to-end regret O(√T) (O(log T) off boundary points) when exploration is long enough to recover the true reward-cost ordering.","pith_inferences":["If query traffic drifts by time of day or product surface, periodically re-estimating only the cluster frequencies (not full model statistics) may restore budget adherence without a full re-exploration.","The same discretization-plus-ALP pattern could route among speculative-decoding, quantized, or cascade configurations rather than whole models.","When several models sit on nearly identical cost tiers, the ratio-ordering test becomes the practical bottleneck; cheaper pairwise A/B probes on the hardest clusters may shorten exploration more than uniform least-played sampling.","Workloads with strong query dependence (multi-turn chats) would need a contextual or restless extension before the stated regret bound can be claimed."],"forward_implications":["Operators can change monthly API budgets at inference time without recollecting responses or retraining a router.","A single shared budget can cover both exploration and deployment, so online routers need far less than a full query–model response matrix.","At tight budgets, allocating expensive models only to hard clusters raises average quality more than any fixed per-query cap.","End-to-end regret of order √T gives a concrete sample-complexity target for how long exploration must run before exploitation.","The same ALP template applies to non-monetary costs such as latency or energy once they are normalized per query."],"fun_headline_variants":["Workload budget makes LLM routing a constrained bandit","WISERouter meets global cost caps without per-query retraining","Adaptive LP enforces one shared budget across the full workload","WR-Offline beats baselines on budget adherence from history alone","WR-Online hits O(√T) regret with far less exploration data"],"cache_read_input_tokens":128,"weakest_assumption_plain":"After embedding and clustering, queries in the same cluster are treated as sharing the same expected quality and cost for each model, and those clusters arrive independently from a fixed distribution over a known finite horizon.","fun_headline_variants_meta":{"raw":{"variants":["Workload budget makes LLM routing a constrained bandit","WISERouter meets global cost caps without per-query retraining","Adaptive LP enforces one shared budget across the full workload","WR-Offline beats baselines on budget adherence from history alone","WR-Online hits O(√T) regret with far less exploration data"]},"model":"grok-4.5","effort":"low","cost_usd":0.001904,"raw_usage":{"total_tokens":879,"prompt_tokens":788,"num_sources_used":0,"completion_tokens":71,"cost_in_usd_ticks":19044000,"prompt_tokens_details":{"text_tokens":788,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":20,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":788,"tokens_out":71,"duration_ms":2398,"temperature":1.0,"reasoning_tokens":20,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T13:15:30.065317+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On a held-out stream with the same models and a fixed workload budget B, measure whether WR-Offline’s total spend stays within B while average quality exceeds FrugalGPT, CascadeRouting, MetaLLM, and SingleBest at the tightest budgets; if it overspends or underperforms those baselines, or if raising intra-cluster reward variance collapses the gains, the central claim fails.","supporting_citations":[],"review_version":1}