{"id":"270c78e6-020a-4ab1-9efd-910bfb170871","arxiv_id":"2508.21141","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"LLM routing is framed as a budget-constrained contextual bandit, solved by a preference-prior initialized LinUCB variant with an online multi-choice knapsack cost policy.","lead":"This paper treats LLM routing as an online learning problem, where the router only sees a yes/no reward for the model it picked, and couples this with a budget policy that spreads a fixed cost budget across queries. The proposed PILOT algorithm starts from human preference data and adapts online, reporting 93% of GPT-4 performance at 25% of its cost on Routerbench.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The linear reward model in Eq. (1) is the load-bearing assumption; without a diagnostic that cosine affinity predicts true rewards, the UCB exploration and cost policy are built on an untested premise, and the headline 93%/25% result lacks a theoretical guarantee.","rationale":"The paper's three contributions (bandit formulation, preference-prior LinUCB, online cost policy) all rely on the cosine reward being the true conditional mean. The strongest empirical claim is a performance/cost tradeoff; if the reward model is wrong, the cost policy may make poor choices and the UCB regret bound is invalid. The reader's weakest assumption aligns with this. The proof error is a concrete flaw but likely fixable; the main issue is the absence of any validation of the reward model. A simple correlation test would settle it. This doesn't change the CONDITIONAL verdict; it reinforces the need for the requested diagnostics.","tokens_in":16932,"tokens_out":6922,"duration_ms":69107,"concrete_test":"Take a held-out split of Routerbench. For each query q and each LLM a, compute the cosine affinity cos(ψ(q), θ_a) using the pretrained embeddings (and/or the final online-updated ones) and pair it with the actual reward s(q,y_a). Compute the Pearson/Spearman correlation and a binned calibration plot. If the correlation is weak (e.g., < 0.3) or rewards are not monotone in cosine, the linear reward model is falsified. As a follow-up, retrain the router with a non-linear reward model (e.g., a small MLP) and test whether the 93%/25% claim still holds; also check whether ||θ_pref−θ*|| ≤ ||θ*|| holds on the tuning split to validate Prop. C.1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"PILOT's every component depends on the exact linear reward model E[r_t|a,q_t] = cos(ψ(q_t), θ_a) (Eq. 1). The UCB selection, ridge-regularized posterior, and the cost policy's eligibility thresholds all use this cosine as the value estimate. The paper provides no empirical check that Routerbench scores (GPT-4 eval or exact match) are linear in the preference-pretrained embedding space. If the true reward is non-linear, the UCB bonus is not a valid confidence bound, exploration is misdirected, and the online ridge regression is fitting a mis-specified mean. The theoretical claim (Prop. C.1) also requires the unmeasured condition ||θ_pref−θ*|| ≤ ||θ*||, and its proof contains an algebraic error: the expression for ˜θ_t lacks the inverse (X^T X+λI)^{-1} on the λ(θ*−θ_pref) term, so the confidence bound derivation is not self-consistent. Thus the central empirical claim of 93% of GPT-4 at 25% cost is only as reliable as this untested linearity.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes to reformulate LLM routing as a budget-constrained contextual bandit problem, where for each query the router selects one LLM and observes binary-quality feedback only for the selected arm. The proposed method, PILOT, (1) pretrains a shared query/LLM embedding space using offline human preference data from ChatArena with a triplet/BCE objective, (2) initializes per-arm ridge-regression parameters in LinUCB with these embeddings, and (3) adds an online multi-choice knapsack cost policy (ZCL-style) for deployment under a token-cost budget. Experiments on Routerbench compare PILOT with LinUCB, Epoch-Greedy, explore-only, random, and all-to-one baselines; the paper reports 93% of GPT-4's performance at 25% of its cost in the multi-task setting. Appendix C.1 claims a regret-bound improvement for a preference-prior-initialized OFUL algorithm under the condition ||theta_pref - theta*|| <= ||theta*||.","tokens_in":17218,"tokens_out":5240,"duration_ms":55762,"significance":"The formulation is a useful step: it removes the need for exhaustive query-LLM labeling and permits online adaptation to query drift. The held-out deployment protocol is a reasonable way to simulate a two-bucket system, and using ChatArena as an external preference prior avoids circular evaluation. If the empirical results are robust, the method could be practically valuable. However, the central linear reward model is not validated, the theoretical proposition contains an algebraic error, the stated budget-constrained problem is only solved at deployment, and the empirical claims rest on single runs without uncertainty estimates. These issues must be addressed before the contribution can be fully assessed.","major_comments":[{"comment":"The paper assumes E[rt | a, qt] = cos(psi_hat(qt), theta_hat_a), and this exact linearity is used for UCB selection, ridge-regression posterior, and cost-policy value estimates. No diagnostic is provided that Routerbench rewards (GPT-4 eval or exact match) are linear in the preference-pretrained embedding space, or that the cosine scores are even monotonically related to rewards. Please add a calibration/correlation analysis on the tuning set (e.g., Spearman correlation, binned calibration plots, or a comparison against a non-linear reward model). Without this, the exploration bonus is not a valid confidence bound and the headline 93%/25% result is not theoretically supported.","section":"Section 2.2.2, Eq. (1)"},{"comment":"The displayed expression for tilde_theta_t is dimensionally incorrect: the term lambda(X^T X + lambda I)(theta* - theta_pref) is missing the inverse (X^T X + lambda I)^{-1}. The correct form is theta* + (X^T X + lambda I)^{-1} X^T epsilon + lambda (X^T X + lambda I)^{-1}(theta_pref - theta*). This error propagates to the confidence-bound derivation. In addition, the condition ||theta_pref - theta*|| <= ||theta*|| is not verified for the actual pretrained embeddings; without it, Proposition C.1 does not apply. Please fix the proof and report whether the learned theta_pref is closer to theta* than the zero vector is, or discuss how this condition can be checked.","section":"Appendix C.1, proof of Proposition C.1"},{"comment":"The problem statement defines an objective with a budget constraint over Q queries, but Algorithm 1 runs unconstrained and the cost policy is applied only after learning, as the Limitations section acknowledges. The stated problem is therefore not solved as posed. Either revise the problem formulation to explicitly define a two-phase protocol (unconstrained bandit learning followed by constrained deployment) or modify the algorithm to respect budgets during learning. As written, contribution (i) overclaims the scope of the proposed solution.","section":"Section 2.1 vs Algorithm 1 / Limitations"},{"comment":"All empirical results appear to be single-run; no confidence intervals, standard errors, or repeated-seed averages are reported. For a stochastic bandit algorithm, the reported differences between PILOT and LinUCB (e.g., Table 5: $1 budget 0.63 vs 0.60; $3 budget 0.73 vs 0.68) may be within noise. Please run multiple random seeds (at least 5) and report mean +/- standard deviation, or apply paired significance tests. This is necessary to support the central performance claim.","section":"Section 4 and Tables 5-6"}],"minor_comments":[{"comment":"The upper/lower bounds UB and LB on the reward-to-cost ratio are never specified, although the ZCL-style guarantee relies on them. Please state the values used and report sensitivity to them.","section":"Section 2.2.3"},{"comment":"The 'Insufficient budget' termination path is not analyzed. What happens to the remaining queries in the bin, and how often does this branch occur in the experiments?","section":"Algorithm 3"},{"comment":"The setting 'lambda_a as the inverse of arm a's accuracy during the pretraining phase' is not precisely defined. Please specify how the accuracy is measured and how the inverse is computed.","section":"Section 2.2.2"},{"comment":"Typos and formatting issues: 'birds eye', 'PILOTadds', 'maybe be interested', 'worth noting', and the threshold formula in Algorithm 2 is rendered without necessary parentheses. Figure 3 is dense and the sub-column labels should be more legible.","section":"General"},{"comment":"The paper refers to 'ChatArena' but the cited reference is Chatbot Arena (Chiang et al., 2024). Please align the terminology with the citation.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"I agree with the reader's circularity assessment: the held-out evaluation and external preference prior are not circular. The main blocking issues are the unvalidated linearity assumption in Eq. (1), the algebraic error in Proposition C.1's proof, the mismatch between the stated budget-constrained problem and the two-phase algorithm, and the absence of uncertainty quantification. These are fixable within the scope of the paper, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The real contribution here is the framing: LLM routing as a contextual bandit with a preference-pretrained prior and an online knapsack cost policy. That combination is new, and the deployment protocol — tuning, learning bucket, held-out deployment bucket — is a reasonable way to simulate online traffic from RouterBench. The ablation in Table 5 gives real evidence that the pretrained prior plus online data helps, and the cost-policy comparison against a hindsight-optimal P−λC baseline is a nice touch. The headline 93% of GPT-4 quality at 25% of its cost is plausible, and the qualitative routing decisions (GPT-4 for MMLU/ARC, Claude for math) make sense.\n\nThe soft spots, in order of severity. First, Equation (1) assumes the expected reward is exactly the cosine similarity between the projected query and the arm embedding. Everything downstream — the UCB selection, the ridge regression posterior, the eligibility thresholds in the cost policy — rests on that linearity. The paper gives no diagnostic showing that RouterBench rewards are actually linear in this embedding space. If that assumption fails, the UCB bonus is not a valid confidence bound and the regret guarantees don't transfer. Second, the budget constraint is only applied at deployment, not during bandit learning. The Limitations section says this explicitly, but it weakens the title-level claim: the learned router isn't budget-aware, it's just filtered by a budget-aware policy. That's an honest and possibly practical choice, but it's not the full problem stated in the abstract. Third, the proof of Proposition C.1 contains an algebraic error: the expression for \\tilde\\theta_t drops the inverse on the \\lambda(\\theta^* - \\theta_{\\text{pref}}) term. That's fixable, but as written the confidence-bound derivation isn't self-consistent. And the condition \\|\\theta_{\\text{pref}} - \\theta^*\\| \\le \\|\\theta^*\\| is unmeasured, so the theoretical improvement is conditional on something the paper never checks. Finally, no confidence intervals, repeated seeds, or code. The 'consistently outperforms' claim is not yet quantified.\n\nThis is a solid engineering paper with a genuinely new problem formulation, not a paradigm shift. Who benefits: people building LLM serving systems and bandit practitioners looking for a realistic application. It deserves a serious referee, but the referee should ask for code, error bars, a linearity diagnostic, and a corrected proof. I'd want to see those before trusting the 93%/25% number.\n\nMy recommendation: engage with it. Send it to review, but expect substantive revision.","headline":"A useful bandit formulation for LLM routing with a solid empirical setup, but the linear reward assumption is untested, error bars are missing, and the theory has a fixable algebraic slip.","tokens_in":17727,"tokens_out":2116,"would_cite":true,"duration_ms":22385,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that LLM routing can be learned online from binary user feedback using a preference-prior-informed linear bandit, and that this reaches GPT-4-level performance at a fraction of its cost while adapting to new queries.","keywords":["LLM routing","contextual bandits","LinUCB","human preference data","budget constraints","online multi-choice knapsack","adaptive routing","Routerbench"],"falsifier":"On a held-out set of Routerbench queries, compute PILOT's predicted cosine affinity cos(ψ(q), θ_l) for every LLM and compare it with the recorded reward s(q, y_l). If the rank correlation is weak or the relation is strongly nonlinear, Eq. (1) is false and the UCB rule loses its justification; similarly, estimating θ* by ridge regression and checking whether ||θ_pref − θ*|| ≤ ||θ*|| holds would settle the Proposition C.1 comparison.","tokens_in":16809,"feed_emoji":"🤖","tokens_out":11318,"duration_ms":104935,"temperature":0.7,"pith_summary":"The paper tries to establish that LLM routing can be treated as a budget-constrained contextual bandit problem, where the only supervision is binary feedback such as thumbs up/down on the selected model's answer. To learn from this sparse feedback, the authors build a shared embedding space for queries and LLMs, pretrain it on human preference data, and refine it online with a preference-prior-informed LinUCB algorithm called PILOT. They report that PILOT reaches 93% of GPT-4's performance at 25% of its cost on the multi-task Routerbench setting, with higher performance than the bandit baselines, and that their online multi-choice knapsack cost policy handles budget constraints better than fixed per-query allocation and generally matches a hindsight-tuned offline policy. If the claim is right, deployable routers no longer need exhaustive query-LLM labels and can adapt to changing query distributions through ordinary user feedback.","feed_headline":"Bandit router reaches 93% of GPT-4 at 25% cost","feed_subtitle":"A preference-prior bandit learns from simple feedback and spends budgets online—no exhaustive query-LLM labels.","key_machinery":"The mechanism is PILOT, a LinUCB variant whose ridge-regression posterior is initialized with preference-prior embeddings (A0_a = λ_a I, b0_a = λ_a θ_pref_a). The expected reward is defined as the cosine similarity between a normalized query projection and an LLM embedding (Eq. 1), which is linear in the arm parameter and therefore fits the upper-confidence-bound and ridge-regression machinery of linear bandits. The companion online cost policy frames each query as a choice set in an online multi-choice knapsack problem and uses the ZCL algorithm to select the highest-reward LLM whose cost fits a budget-utilization threshold, with binned budgets and forward spillover.","core_discovery":"The central claim is that a router initialized from human-preference embeddings and run as a linear contextual bandit can learn good routing from bandit feedback alone. The paper models the expected reward of routing query q to LLM a as the cosine similarity between normalized embeddings, E[r_t | a, q_t] = cos(ψ(q_t), θ_a), which makes the problem linear in the arm parameters. PILOT then runs ridge-regression UCB with the preference embeddings as the prior (A0_a = λ_a I, b0_a = λ_a θ_pref_a), so the arm estimate starts at the human-preference cosine affinity and moves toward observed rewards. In the multi-LLM Routerbench setting the paper reports performance equal to 93% of GPT-4 at 25% of i","pith_inferences":["The paper's own setting takes the linear reward model in Eq. (1) as given and gives no diagnostic for it; a direct test would compare PILOT's cosine predictions with recorded scores on held-out Routerbench queries. If rewards are nonlinear in the embedding, a kernel or neural extension of the UCB would be needed.","The preference-prior bandit recipe transfers to other black-box model-selection problems—retrieval rerankers, code executors, image models—wherever a pool of services can be embedded and feedback is binary.","Because the paper explicitly separates bandit learning from the budget policy, an immediate extension is to fold costs into the bandit objective itself and learn under budget constraints, not just deploy under them.","The reported cost-performance frontier depends on the Routerbench score function and the embedding model; rerunning PILOT with human ratings or task-specific metrics as the reward would show whether the 93%-at-25%-cost result is a property of the algorithm or of that scoring choice."],"forward_implications":["Deployment no longer requires running every LLM on every training query; the router learns only from the selected model's reward.","Because the router updates online, it can track shifts in the query distribution instead of freezing at training time.","Budget control is separated from reward learning: the cost policy can be adjusted or replaced without retraining the bandit.","A good preference prior reduces the regret bound relative to standard OFUL, implying fewer online samples are needed to reach the same routing quality.","Routing overhead stays small relative to LLM inference time, so online adaptation is practical in a serving loop."],"supporting_citations":[{"why":"Supplies the LinUCB algorithm and the learning-bucket/deployment-bucket evaluation protocol that PILOT extends to routing.","marker":"Li et al., 2010"},{"why":"Provides Routerbench, the dataset with 11 LLM responses, scores, and costs used for all routing evaluation.","marker":"Hu et al., 2024"},{"why":"Supplies the ChatArena human-preference dataset used to pretrain the query and LLM embeddings.","marker":"Chiang et al., 2024"},{"why":"Defines OFUL, the optimism-in-the-face-of-uncertainty linear bandit whose regret bound Proposition C.1 compares against.","marker":"Abbasi-Yadkori et al., 2011a"},{"why":"Provides the self-normalized least-squares concentration argument that Proposition C.1's proof builds on.","marker":"Abbasi-Yadkori et al., 2011b"},{"why":"Supplies the ZCL online knapsack algorithm and its near-optimal guarantee used by the online cost policy.","marker":"Zhou et al., 2008"},{"why":"Introduces the online multi-choice knapsack problem that the budget policy is formulated as.","marker":"Chakrabarty et al., 2008"},{"why":"HybridLLM is the supervised router baseline whose performance PILOT matches or exceeds without full supervision.","marker":"Ding et al., 2024"},{"why":"RouteLLM is the preference-data baseline against which the pretraining stage's routing accuracy is measured.","marker":"Ong et al., 2024"}],"fun_headline_variants":["Bandit routing hits 93% of GPT-4 for a quarter of the cost","Adaptive router learns on the fly, matches GPT-4 at 25% cost","Preference-prior bandit: 93% of GPT-4, 25% of the price","LLM routing as bandit: near-GPT-4 quality at budget cost"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is that the true reward for routing a query to an LLM is a linear function of cosine similarity in the learned embedding space, and that the preference prior is at least as close to the true reward vector as the origin; if either fails, the UCB exploration bonuses and the regret comparison no longer transfer.","fun_headline_variants_meta":{"raw":{"variants":["Bandit routing hits 93% of GPT-4 for a quarter of the cost","Adaptive router learns on the fly, matches GPT-4 at 25% cost","Preference-prior bandit: 93% of GPT-4, 25% of the price","LLM routing as bandit: near-GPT-4 quality at budget cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000232,"raw_usage":{"total_tokens":1330,"prompt_tokens":754,"completion_tokens":576,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":498,"completion_tokens_details":{"reasoning_tokens":482}},"tokens_in":498,"tokens_out":576,"duration_ms":5188,"temperature":1.0,"reasoning_tokens":482,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T14:33:45.249334+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a held-out set of Routerbench queries, compute PILOT's predicted cosine affinity cos(ψ(q), θ_l) for every LLM and compare it with the recorded reward s(q, y_l). If the rank correlation is weak or the relation is strongly nonlinear, Eq. (1) is false and the UCB rule loses its justification; similarly, estimating θ* by ridge regression and checking whether ||θ_pref − θ*|| ≤ ||θ*|| holds would settle the Proposition C.1 comparison.","supporting_citations":[],"review_version":1}