REVIEW 4 major objections 5 minor 9 cited by
Adaptive LLM Routing under Budget Constraints
T0 review · 4 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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*||.
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 (4)
- [Section 2.2.2, Eq. (1)] 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.
- [Appendix C.1, proof of Proposition C.1] 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 2.1 vs Algorithm 1 / Limitations] 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 4 and Tables 5-6] 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.
minor comments (5)
- [Section 2.2.3] 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.
- [Algorithm 3] 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 2.2.2] 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.
- [General] 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.
- [References] The paper refers to 'ChatArena' but the cited reference is Chatbot Arena (Chiang et al., 2024). Please align the terminology with the citation.
Circularity Check
No significant circularity: the empirical routing result is measured on held-out Routerbench data after pretraining on an external preference dataset, and the theoretical prior-benefit claim is an explicitly conditional statement rather than a fitted prediction.
full rationale
The central empirical claim (93% of GPT-4 performance at 25% cost) is not circular. The preference prior is learned from ChatArena, a dataset distinct from Routerbench, and the evaluation is performed on a held-out deployment bucket after online bandit learning. The cost policy is imported from the external ZCL/online-knapsack result of Zhou et al. (2008) and is applied uniformly to all baselines, so it does not encode PILOT's own fitted values as a prediction. The linear reward model in Eq. (1), E[r_t | a, q_t] = cos(ψ(q_t), θ_a), is an explicit modeling assumption; it is not derived from, nor fitted to, the deployment rewards being predicted, so any misspecification is a correctness/validity concern rather than a circularity. Proposition C.1 is conditional: it states that IF ||θ_pref − θ*|| ≤ ||θ*||, THEN the preference-prior-initialized OFUL has a smaller regret bound. This is a monotonicity statement about the regret bound and does not assume the conclusion it purports to establish; the unverified condition is a limitation of the theory, not an instance of the paper predicting its own inputs. There is no load-bearing self-citation chain, no imported uniqueness theorem, and no renaming of a known result as a new organizational principle. The paper's stated limitations, such as decoupling bandit learning from the budget-constrained deployment phase and focusing on single-turn queries, are acknowledged design choices rather than circular steps.
Assumptions & free parameters
free parameters (5)
- exploration parameter alpha =
selected from {1, 1.5, 2, 5, 10} on tuning data
- per-arm regularization lambda_a =
inverse of arm a's pretraining accuracy, value not reported
- reward-to-cost bounds UB, LB
- bin size S
- mean output token count per LLM =
mean from tuning data
assumptions (6)
- domain assumption E[r_t | a, q_t] = cos(psi(q_t), theta_a), a linear reward model in the projected embedding space (Eq. 1).
- domain assumption Human preference data (ChatArena) transfers to the target routing task and provides a prior closer to the true reward vector than zero (Prop. C.1 condition ||theta_pref - theta*|| <= ||theta*||).
- domain assumption Known upper/lower bounds UB, LB on the reward-to-cost ratio and query costs small relative to budget B.
- ad hoc to paper Hard negatives are defined by model size: queries where the preferred LLM lost to a smaller LLM are hard negatives.
- standard math OFUL regret bound of Abbasi-Yadkori et al. applies to the per-arm ridge regression setting.
- domain assumption Binary feedback r_t = s(q_t, y_l_t) is available immediately after each selected response and is an unbiased reward signal.
Cite this review
Pith. "Pith review of Adaptive LLM Routing under Budget Constraints." pith.science (2026). https://pith.science/paper/FVQIWQ7S
@misc{pith2026250821141,
author = {Pith},
title = {Pith review of: Adaptive LLM Routing under Budget Constraints},
year = {2026},
howpublished = {\url{https://pith.science/paper/FVQIWQ7S}},
note = {Machine review of arXiv:2508.21141}
}
read the original abstract
Large Language Models (LLMs) have revolutionized natural language processing, but their varying capabilities and costs pose challenges in practical applications. LLM routing addresses this by dynamically selecting the most suitable LLM for each query/task. Previous approaches treat this as a supervised learning problem, assuming complete knowledge of optimal query-LLM pairings. However, real-world scenarios lack such comprehensive mappings and face evolving user queries. We thus propose to study LLM routing as a contextual bandit problem, enabling adaptive decision-making using bandit feedback without requiring exhaustive inference across all LLMs for all queries (in contrast to supervised routing). To address this problem, we develop a shared embedding space for queries and LLMs, where query and LLM embeddings are aligned to reflect their affinity. This space is initially learned from offline human preference data and refined through online bandit feedback. We instantiate this idea through Preference-prior Informed Linucb fOr adaptive rouTing (PILOT), a novel extension of LinUCB. To handle diverse user budgets for model routing, we introduce an online cost policy modeled as a multi-choice knapsack problem, ensuring resource-efficient routing.
Figures
Figures from the paper (4 more)
Forward citations
Cited by 9 Pith papers
-
On Time, Within Budget: Constraint-Driven Online Resource Allocation for Agentic Workflows
MCPP is a Monte Carlo simulation-based online planner that improves the probability of agentic workflows completing successfully under explicit budget and deadline constraints compared to baselines on CodeFlow and Pro...
-
ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Serving
ParetoBandit uses contextual bandits with an online primal-dual budget pacer and geometric forgetting to enforce cost ceilings and adapt to non-stationary pricing and quality shifts in LLM serving, achieving 0.4% budg...
-
RouteBalance: Fused Model Routing and Load Balancing for Heterogeneous LLM Serving
RouteBalance fuses routing and load balancing for heterogeneous LLM serving and traces the upper quality-cost-throughput frontier on a 13-instance 28-GPU cluster.
-
Learning Agent Routing From Early Experience
BoundaryRouter routes queries to LLM or agent using early experience memory from a seed set, cutting inference time 60.6% versus always using agents and raising performance 28.6% versus always using direct LLM inference.
-
On Time, Within Budget: Constraint-Driven Online Resource Allocation for Agentic Workflows
MCPP uses Monte Carlo simulations of workflow executions to dynamically allocate resources and replan, raising constrained completion probability over baselines on CodeFlow and ProofFlow.
-
Zero-Shot Confidence Estimation for Small LLMs: When Supervised Baselines Aren't Worth Training
Average token log-probability provides a zero-shot confidence signal for small LLMs that matches supervised baselines in-distribution and outperforms them out-of-distribution, with a new retrieval-conditional variant ...
-
Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization
A Lagrangian-relaxation plus imitation-learning pipeline adaptively allocates test-time compute to LLMs, outperforming uniform baselines by up to 12.8% relative accuracy on MATH while staying within a fixed average budget.
-
Learning to Assign Prediction Tasks to Agents with Capacity Constraints
Sequential explore-exploit algorithms for assigning tasks to capacity-constrained agents demonstrate performance gains over non-contextual baselines on tabular, image, and text tasks with both LLMs and humans.
-
Retrieval-Conditioned Topology Selection with Provable Budget Conservation for Multi-Agent Code Generation
RGAO combines retrieval-based complexity assessment with a formal budget algebra to enable dynamic topology selection in multi-agent code generation with provable conservation.
Reference graph
Works this paper leans on
-
[1]
Yasin Abbasi-Yadkori, D \'a vid P \'a l, and Csaba Szepesv \'a ri. 2011 a . Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24
work page 2011
-
[2]
Yasin Abbasi-Yadkori, D \'a vid P \'a l, and Csaba Szepesv \'a ri. 2011 b . Online least squares estimation with self-normalized processes: An application to bandit problems . arXiv preprint arXiv:1102.2670
arXiv 2011
-
[3]
Appcues. 2024. https://www.appcues.com/blog/rating-system-ux-star-thumbs Rating systems in ux: Star vs. thumbs up . Appcues Blog
work page 2024
-
[4]
Simran Arora, Sabri Eyuboglu, Michael Zhang, Aman Timalsina, Silas Alberti, James Zou, Atri Rudra, and Christopher Re. 2024. Simple linear attention language models balance the recall-throughput tradeoff. In Forty-first International Conference on Machine Learning
work page 2024
-
[5]
Djallel Bouneffouf and Irina Rish. 2019. A survey on practical applications of multi-armed and contextual bandits. arXiv preprint arXiv:1904.10040
arXiv 2019
-
[6]
Deeparnab Chakrabarty, Yunhong Zhou, and Rajan Lukose. 2008. Online knapsack problems. In Workshop on internet and network economics (WINE), pages 1--9
work page 2008
-
[7]
Lichang Chen, Shiyang Li, Jun Yan, Hai Wang, Kalpa Gunaratna, Vikas Yadav, Zheng Tang, Vijay Srinivasan, Tianyi Zhou, Heng Huang, and 1 others. 2024. Alpagasus: Training a better alpaca with fewer data. In The Twelfth International Conference on Learning Representations
work page 2024
-
[8]
Lingjiao Chen, Matei Zaharia, and James Zou. 2022. Efficient online ml api selection for multi-label classification tasks. In International conference on machine learning, pages 3716--3746. PMLR
work page 2022
Show all 34 references
-
[9]
Lingjiao Chen, Matei Zaharia, and James Zou. 2023. Frugalgpt: How to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.05176
2023 arXiv
-
[10]
Gonzalez, and Ion Stoica
Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Hao Zhang, Banghua Zhu, Michael Jordan, Joseph E. Gonzalez, and Ion Stoica. 2024. https://arxiv.org/abs/2403.04132 Chatbot arena: An open platform for evaluating llms by human pr...
2024 arXiv
-
[11]
Yu-Neng Chuang, Helen Zhou, Prathusha Sarma, Parikshit Gopalan, John Boccio, Sara Bolouki, and Xia Hu. 2025. Learning to route llms with confidence tokens. arXiv preprint arXiv:2410.13284, 3
2025 arXiv
-
[12]
Delighted. 2024. https://delighted.com/blog/7-customer-experience-survey-types 7 types of customer experience surveys you should know about . Delighted Blog
2024
-
[13]
Dujian Ding, Ankur Mallick, Chi Wang, Robert Sim, Subhabrata Mukherjee, Victor Ruhle, Laks VS Lakshmanan, and Ahmed Hassan Awadallah. 2024. Hybrid llm: Cost-efficient and quality-aware query routing. arXiv preprint arXiv:2404.14618
2024 arXiv
-
[14]
Tao Feng, Yanzhen Shen, and Jiaxuan You. 2024. Graphrouter: A graph-based router for llm selections. arXiv preprint arXiv:2410.03834
2024 arXiv
-
[15]
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. 2015. Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531
2015 arXiv
-
[16]
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2021. Lora: Low-rank adaptation of large language models. arXiv e-prints, pages arXiv--2106
2021
-
[17]
Qitian Jason Hu, Jacob Bieker, Xiuyu Li, Nan Jiang, Benjamin Keigwin, Gaurav Ranganath, Kurt Keutzer, and Shriyash Kaustubh Upadhyay. 2024. Routerbench: A benchmark for multi-llm routing system. arXiv preprint arXiv:2403.12031
2024 arXiv
-
[18]
Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. 2018. Quantization and training of neural networks for efficient integer-arithmetic-only inference. In Proceedings of the IEEE conference on computer vis...
2018
-
[19]
Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. 2023. Llm-blender: Ensembling large language models with pairwise ranking and generative fusion. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 14165--14178
2023
-
[20]
John Langford and Tong Zhang. 2007. The epoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20(1):96--1
2007
-
[21]
Tor Lattimore and Csaba Szepesv \'a ri. 2020. Bandit algorithms. Cambridge University Press
2020
-
[22]
Yann LeCun, John Denker, and Sara Solla. 1989. Optimal brain damage. Advances in neural information processing systems, 2
1989
-
[23]
Baolin Li, Yankai Jiang, Vijay Gadepally, and Devesh Tiwari. 2024. Llm inference serving: Survey of recent advances and opportunities. arXiv preprint arXiv:2407.12391
2024 arXiv
-
[24]
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. 2010. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661--670
2010
-
[25]
Wei Liu, Weihao Zeng, Keqing He, Yong Jiang, and Junxian He. 2024. What makes good data for alignment? a comprehensive study of automatic data selection in instruction tuning. In The Twelfth International Conference on Learning Representations
2024
-
[26]
Xiaoding Lu, Adian Liusie, Vyas Raina, Yuwen Zhang, and William Beauchamp. 2024. Blending is all you need: Cheaper, better alternative to trillion-parameters llm. arXiv preprint arXiv:2401.02994
2024 arXiv
-
[27]
Gonzalez, M Waleed Kadous, and Ion Stoica
Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E. Gonzalez, M Waleed Kadous, and Ion Stoica. 2024. https://arxiv.org/abs/2406.18665 Routellm: Learning to route llms with preference data . Preprint, arXiv:2406.18665
2024 arXiv
-
[28]
Marija S akota, Maxime Peyrard, and Robert West. 2024. Fly-swat or cannon? cost-effective language model choice via meta-modeling. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pages 606--615
2024
-
[29]
Dimitris Stripelis, Zhaozhuo Xu, Zijian Hu, Alay Dilipbhai Shah, Han Jin, Yuhang Yao, Jipeng Zhang, Tong Zhang, Salman Avestimehr, and Chaoyang He. 2024. Tensoropera router: A multi-model router for efficient llm inference. In EMNLP (Industry Track)
2024
-
[30]
Hongjin Su, Weijia Shi, Jungo Kasai, Yizhong Wang, Yushi Hu, Mari Ostendorf, Wen-tau Yih, Noah A Smith, Luke Zettlemoyer, and Tao Yu. 2023. One embedder, any task: Instruction-finetuned text embeddings. In Findings of the Association for Computational Linguistics: ACL 2023, pa...
2023
-
[31]
Hugh Zhang, Jeff Da, Dean Lee, Vaughn Robinson, Catherine Wu, William Song, Tiffany Zhao, Pranav Raja, Charlotte Zhuang, Dylan Slack, and 1 others. 2024. A careful examination of large language model performance on grade school arithmetic. Advances in Neural Information Proces...
2024
-
[32]
Yunhong Zhou, Deeparnab Chakrabarty, and Rajan Lukose. 2008. Budget constrained bidding in keyword auctions and online knapsack problems. In Proceedings of the 17th international conference on world wide web, pages 1243--1244
2008
-
[33]
online" 'onlinestring :=
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint eprinttype howpublished institution journal key month note number organization pages publisher school series title type volume year doi pubmed url lastchecked label extra.label sort.label short.list...
-
[34]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.