Reward-Based Online LLM Routing via NeuralUCB

Ming-Hua Tsai, Phat Tran · 2026

Read Reward-Based Online LLM Routing via NeuralUCB by Ming-Hua Tsai, Phat Tran (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-30035.txt.

Introduction

Tsai and Tran test NeuralUCB for routing queries among language models by cost and reward. Supervised routers adapt poorly, while partial-feedback methods trade efficiency for flexibility. Their bandit policy learns from reward signals in a simulated online setting. On RouterBench, it beats random and cheapest-first baselines on utility. Against a max-quality reference, it costs far less while staying competitive. The authors flag action discrimination and exploration as open challenges.

Catalog record

CREATORMing-Hua Tsai, Phat Tran
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14678
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.30035

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Reward-Based Online LLM Routing via NeuralUCB Ming-Hua Tsai, Phat Tran Abstract This study investigates the use of NeuralUCB for cost-aware large language model (LLM) routing. Existing routing approaches can be broadly grouped into supervised routing methods and partial-feedback methods, each with different tradeoffs in efficiency and adaptivity. We implement a NeuralUCB-based routing policy and evaluate it on RouterBench under a simulated online setting. Experimental results show that the proposed method consistently outperforms random and min-cost baselines in utility reward. Compared with the max-quality reference, our method achieves substantially lower inference cost while maintaining competitive reward. These findings suggest that NeuralUCB is a promising approach for cost-aware LLM routing, while also highlighting remaining challenges in action discrimination and exploration. 1 Problem Definition Large language models (LLMs) exhibit substantial variation in both capability and inference cost across tasks. High-end models often provide higher quality at higher cost, while cheaper models may fail on complex reasoning or coding queries. We study reward-based online LLM routing, which dynamically selects an appropriate LLM for each user query to balance answer quality and inference cost. Formally, at interaction round t , the system observes a query x_{t} and selects a model a_{t} from a candidate set \mathcal{A}=\{1,...,K\} . To operationalize this in our framework, raw text queries are mapped into a dense semantic feature space using pre-trained sentence encoders. Since deployment typically invokes only one model per query, we only observe the feedback of the selected model r_{t}=r(x_{t},a_{t}) and do not observe outcomes for other models on the same query. The goal is to learn a routing policy that maximizes the long-horizon expected utility: \max_{\pi}\ \mathbb{E}\Big[\sum_{t=1}^{T}r(x_{t},a_{t})\Big],\qquad a_{t}\sim\pi(\cdot\mid x_{t}). A key challenge is that feedback is sparse and the mapping from queries to optimal model choices can be highly non-linear. We therefore cast routing as a contextual bandit problem and adopt NeuralUCB to learn a non-linear routing policy that improves average utility and the cost–quality tradeoff over time. 2 Related Work LLM routing aims to dynamically select an appropriate model for each query to balance answer quality and inference cost. A representative framework views routing as allocating queries of different difficulty to models with different cost profiles to reduce the average inference cost 2 . Existing approaches can be broadly categorized into two groups. Existing approaches can be broadly categorized into two groups. The first group is full-information supervised routing, which trains a router as a classification or ranking model using multiple candidate-model outputs and scores for the same query, such as RouterDC 1 and GraphRouter 3 . While effective, these methods incur high data-collection cost and often require re-labeling and re-training when the query distribution or the model pool changes. The second group learns from partial feedback and naturally fits the contextual bandit setting 5 ; 12 . While LinUCB assumes linear rewards and kernelized methods (e.g., KernelUCB or GP-UCB) can be computationally expensive for high-dimensional embeddings, we adopt a neural contextual bandit perspective and use NeuralUCB to efficiently learn a non-linear query-to-model mapping under partial feedback while explicitly modeling the cost-quality tradeoff. To evaluate these approaches practically without the prohibitive cost of live API experimentation, this framework builds an offline replay pipeline over the RouterBench benchmark 4 . This allows for robust, split-level simulation of an online environment, enabling continuous tracking of cumulative rewards, action rates, and domain-specific performance (e.g., math versus coding). 3 Methodology 3.1 Problem Setup and Utility Function We formulate cost-aware LLM routing as a contextual decision-making problem. For each input sample, we observe a context representation: x=(x_{\text{emb}},x_{\text{feat}},d), where x_{\text{emb}} denotes the prompt embedding produced by a text encoder, x_{\text{feat}} denotes auxiliary features, and d denotes the domain of the sample. Given the context x , the policy selects an action: a\in\mathcal{A}=\{1,\dots,K\}, from a set of candidate LLMs. In our setting, K=11 . For each sample-action pair, we consider two feedback signals, model quality and inference cost, denoted by: q(x,a),\qquad c(x,a). Under our simulated online LLM routing setting, the benchmark provides the quality and cost of all candidate models for each sample, which allows us to compare the utility of different actions over a fixed data stream. Our objective is not to maximize model quality alone, but to achieve a tradeoff between quality and cost. To this end, we define the utility reward as: r(x,a)=q(x,a)\exp\bigl(-\lambda\tilde{c}(x,a)\bigr), (1) where \tilde{c}(x,a) is the normalized cost and \lambda>0 controls the strength of the cost penalty. To stabilize the reward scale, we apply logarithmic normalization to the raw cost: \tilde{c}(x,a)=\frac{\log\bigl(1+c(x,a)\bigr)}{\log\bigl(1+C_{\max}\bigr)}, where C_{\max} denotes the maximum observed cost in the dataset. This transformation maps \tilde{c}(x,a) into [0,1] and reduces instability caused by large cost-scale differences across candidate models. 3.2 UtilityNet Text Embedding x_{emb}\in\mathbb{R}^{384} shape: (B,384) Meta Features x_{feat}\in\mathbb{R}^{3} shape: (B,3) Domain Id d\in\{0\dots 85\} shape: (B,) Action Id a\in\{0\dots 10\} shape: (B,) \oplus Domain Emb Embedding( 86,16 ) out: (B,16) Action Emb Embedding( 11,32 ) out: (B,32) Text MLP Linear( 384\to 256 ) ReLU out: (B,256) Feature MLP Linear( 19\to 32 ) ReLU out: (B,32) \oplus \oplus Gating MLP Linear( 288\to 64 ) ReLU out: (B,64) Utility MLP Linear( 320\to 256 ) ReLU Linear( 256\to 256 ) ReLU Linear( 256\to 128 ) ReLU out: (B,128) Gating Head Linear( 64\to 1 ) out: (B,1) Utility Head Linear( 128\to 1 ) out: (B,1) Figure 1 : Architecture of UtilityNet. The utility branch predicts the utility reward for each context-action pair, while the gating branch predicts whether UCB-bonus-based action selection should be activated. As shown in Figure 1 , UtilityNet serves as the utility predictor in our routing framework. Given a context-action pair, it estimates the corresponding utility reward, while its last hidden representation is further used by the NeuralUCB policy for uncertainty-aware action selection. We first encode the text input and auxiliary features as: h_{\text{emb}}=f_{\text{text}}(x_{\text{emb}}),\qquad e_{d}=\mathrm{Emb}_{d}(d),\qquad h_{\text{feat}}=f_{\text{feat}}([x_{\text{feat}},e_{d}]), where f_{\text{text}}(\cdot) and f_{\text{feat}}(\cdot) denote the text and feature encoders, respectively, and \mathrm{Emb}_{d}(\cdot) denotes the domain embedding. For utility prediction, we define the action embedding: e_{a}=\mathrm{Emb}_{a}(a), and construct the fused representation: z_{u}(x,a)=[h_{\text{emb}},h_{\text{feat}},e_{a}]. The utility branch then computes: h(x,a)=f_{\text{mlp}}(z_{u}(x,a)),\qquad\mu(x,a)=f_{\text{u-head}}(h(x,a)), and is trained to regress Equation ( 1 ) using the Huber loss: \mathcal{L}_{u}=\mathrm{Huber}\bigl(\mu(x,a),r(x,a)\bigr). In addition, we include an auxiliary gating branch based on the context-dependent representation: z_{g}(x)=[h_{\text{emb}},h_{\text{feat}}], which predicts: p(x)=f_{\text{g-head}}\bigl(f_{\text{gate}}(z_{g}(x))\bigr). The gating head is trained with a binary cross-entropy loss: \mathcal{L}_{g}=\mathrm{BCE}\bigl(p(x),y_{\text{gate}}(x)\bigr). 3.3 NeuralUCB-based Routing Policy Based on the utility prediction provided by UtilityNet, we further adopt NeuralUCB for action selection. Specifically, for each context-action pair, we use the last hidden representation h(x,a) produced by UtilityNet as the feature representation for UCB, and define the augmented feature: g(x,a)=[h(x,a);1], where the appended constant 1 serves as a bias term. Instead of maintaining separate uncertainty statistics for each action, we use a shared inverse covariance matrix: A^{-1}, to estimate uncertainty in the last-layer feature space. Under this setting, the UCB score of action a is defined as: s(x,a)=\mu(x,a)+\beta\sqrt{g(x,a)^{\top}A^{-1}g(x,a)}, where \mu(x,a) is the utility score predicted by UtilityNet, and \beta controls the strength of the exploration bonus. NeuralUCB therefore favors actions with both high predicted utility and high uncertainty. In addition to the UCB score, we define a conservative fallback action: a^{\text{safe}}=\arg\max_{a\in\mathcal{A}}\mu(x,a), which selects the action solely based on the predicted mean utility. Using the gating probability p(x) produced by the gating branch, the final action selection rule

Read the complete text