RouterWise: Joint Resource Allocation and Routing for Latency-Aware Multi-Model LLM Serving
arXiv:2604.10907v1 [cs.NI] 13 Apr 2026
Hossein Hosseini Kasnavieh Chris Leckie Adel N. Toosi School of Computing and Information Systems, The University of Melbourne, Australia [email protected] {caleckie, adel.toosi}@unimelb.edu.au Abstract—Multi-model LLM routing has emerged as an effective approach for reducing serving cost and latency while maintaining output quality by assigning each prompt to an appropriate model. However, prior routing methods typically assume that each model has a fixed latency. In real deployments, this assumption is inaccurate: multiple models often share limited GPU resources, and a model’s latency depends strongly on both its allocated resources and the request load induced by the routing policy. Consequently, routing and resource allocation are tightly coupled. In this work, we study joint resource allocation and routing for latency-aware multi-model LLM serving in GPU clusters. Given a set of deployed models and a latency service-level objective (SLO), we seek a system setup and routing policy that maximize overall output quality while satisfying the latency target. We formalize this problem as a constrained joint optimization over deployment setup and routing fractions, and propose ROUTERW ISE, which combines a dual-price formulation for score-maximizing routing with setup-specific latency models derived from system profiling. ROUTERW ISE searches over feasible system setups and, for each fixed setup, computes the best routing policy under the latency target. Our results show that even on the same GPU cluster, achievable output-quality score can vary by up to 87% across retained setups, highlighting that resource allocation is a key determinant of routing performance. Index Terms—Prompt routing, LLM serving, Resource allocation
I. I NTRODUCTION Large Language Models (LLMs) have demonstrated remarkable capabilities across a wide range of complex tasks, including reasoning, coding, and multi-step problem solving [1], [2]. In recent years, numerous proprietary models with varying scales have been developed by industry leaders, such as GPT [3] and Claude [4], alongside high-quality open-source models like Llama [5] and Qwen [6]. These models span a broad spectrum of sizes, leading to significant differences in their performance, computational cost, and latency characteristics. In practice, user prompts exhibit substantial variability in complexity, ranging from simple factual queries to multi-step reasoning tasks. This heterogeneity suggests that not all requests require the full capability of the largest models. Prompt routing has therefore emerged as an effective strategy for improving system efficiency by dynamically selecting an appropriate model for each input. In particular, simpler prompts can often be handled accurately by smaller, faster models, while more complex queries are routed to larger models with
(a) I solated deployment
(b) Co-located deployment
GPU cluster
GPU cluster
GPU 1
Qwen3-8B
GPU 1
8B
14B
GPU 2
Qwen3-14B
GPU 2
8B
14B
GPU 3
Qwen3-32B
GPU 3
Qwen3-32B
GPU 4
Qwen3-32B
GPU 4
Qwen3-32B
Qwen3 8B
Qwen3 14B
Qwen3 32B
Fig. 1. Resource allocation strategies in multi-model LLM serving. Models can be deployed in isolation or co-located on shared GPUs. Co-location enables flexible compute and memory resource sharing and improves utilization.
stronger reasoning capabilities. By adapting model selection to prompt complexity, routing systems can significantly reduce computational cost and latency without sacrificing overall output quality [7], [8]. Prior work on prompt routing has primarily focused on two directions. First, a large body of research develops efficient models to estimate prompt complexity or predict output quality for use in the routing layer. Most approaches adopt encoderbased architectures, often fine-tuning variants of BERT for this purpose [7]–[11]. In addition to these approaches, [12] introduces confidence tokens that signal output correctness after the decoding phase, while [13] proposes IntroLM, which predicts output quality during the prefilling phase. Second, these quality estimation models are integrated into routing policies that explicitly trade off performance and efficiency, enabling systems to decide when to route a prompt to a smaller model versus escalating it to a more capable one. In particular, existing approaches that study the performance-efficiency trade-off implicitly assume that each model invocation has a fixed cost and latency, independent of system configuration and workload [10], [11]. This assumption effectively treats model serving as a stateless API call, ignoring the fact that in real deployments, multiple models share limited GPU resources and compete for compute, memory, and bandwidth. As a result, latency and throughput are not fixed, but depend critically on resource allocation decisions, such as tensor parallelism, GPU thread partitioning, and memory assignment, as well as the incoming
Traffic load
3.11 RPS 5.22 RPS
90
80 9.44 RPS 11.56 RPS
80 70 60
P95 TTFT (ms)
P95 TTFT (ms)
100
Traffic load
3.11 RPS 5.22 RPS
75
9.44 RPS 11.56 RPS
70 65 60 55
50 40
50
60
70
80
90
GPU thread percentage (%)
(a) tp = 2
100
40
50
60
70
80
90
GPU thread percentage (%)
to capture the impact of resource allocation and load on model latency in realistic GPU deployments. • We propose an efficient solution framework that combines dual-price routing and learned latency models to solve the joint optimization problem without requiring expensive end-to-end system simulation. II. P RELIMINARIES
100
(b) tp = 4
Fig. 2. P95 TTFT versus GPU thread percentage under different traffic loads for two tensor parallelism (tp) settings, measured for Vicuna-13B served with vLLM. Higher thread allocation generally lowers TTFT.
request load. This mismatch leads to a fundamental limitation: prior routing formulations fail to capture the non-linear and load-dependent behavior of latency in practical multi-model serving systems. In this work, we address the problem of jointly optimizing resource allocation and routing in multi-model LLM serving systems. Given a GPU cluster, a pool of models, and a routing component that estimates the performance of each model for a given prompt, our goal is to determine both (i) the allocation of system resources—including GPU thread share and memory (VRAM)—to each model, and (ii) a routing policy that assigns prompts to models. The objective is to maximize overall output quality while satisfying latency service-level objectives (SLOs). Crucially, these two components are tightly coupled: the resources allocated to a model directly affect its latency and throughput, which in turn influence optimal routing decisions. As a result, resource allocation and routing must be optimized jointly. Figure 1 illustrates this trade-off. Models can be deployed either in isolation on dedicated GPUs or co-located on shared GPUs. While isolated deployment simplifies scheduling, it may lead to underutilization. In contrast, co-location enables flexible resource sharing, allowing resources to be shifted toward high-demand models and improving overall utilization. To solve this problem, we formulate it as a joint optimization over resource allocation and routing. ROUTERW ISE addresses this problem by searching over feasible system setups and, for each fixed setup, optimizing the routing policy under a latency target. For the routing subproblem, we adopt a dual-price approach that assigns a cost to each model reflecting its resource usage, and routes each prompt to the model that maximizes its utility after accounting for this cost. Our contributions are summarized as follows: • We formulate multi-model LLM serving as a joint optimization problem, where resource allocation and routing decisions are optimized together under latency constraints. • We develop a dual-price-based routing method that efficiently computes optimal routing policies for a fixed resource allocation by reducing a constrained assignment problem to simple per-prompt decisions. • We construct latency models from system profiling data
A. GPU Sharing Model Large language models are often deployed across multiple GPUs to satisfy memory and performance requirements. A common approach is tensor parallelism (TP), in which model weights are partitioned across GPUs and each GPU stores a shard [14]. A straightforward deployment strategy is to dedicate a full GPU to each shard, as in Fig. 1(a). While simple to manage, this static allocation can lead to inefficient resource use in multi-model serving. In practice, different models may experience different request rates and may require different amounts of compute and memory to sustain their incoming load under a latency target. As a result, some GPUs may remain underutilized while others become bottlenecks. To address this, we allow multiple shards to share a GPU, enabling fine-grained allocation of compute and memory resources across co-located models. This flexibility allows the system to assign more resources to models with higher load or greater compute demand, while avoiding overprovisioning for less demanding models. Consequently, co-location can improve overall GPU utilization and help the system satisfy latency objectives more efficiently than isolated deployment. In our system, compute sharing is enabled by NVIDIA MPS [15]. MPS allows the CUDA kernels submitted by shards of different co-located models to be scheduled concurrently on the same GPU. More importantly, it allows us to cap the fraction of GPU compute resources (i.e., active threads) that each shard can use. This provides a practical mechanism for controlling interference among co-located shards and mitigating resource contention. GPU memory, in contrast, is partitioned explicitly across the co-located models. Figure 2 illustrates the benefit of such flexible compute allocation. For a fixed tensor parallelism level, increasing the GPU thread percentage generally reduces P95 TTFT under different traffic loads, indicating that latency is sensitive to the compute share assigned to a model. This suggests that, under co-location, allocating more compute to heavily loaded models can improve serving efficiency and reduce latency. B. Routing Model We assume access to a lightweight routing model that estimates the expected utility of each deployed model for a given prompt. For an input prompt x, the router outputs a score vector s(x) = (s1 (x), . . . , sM (x)) ∈ [0, 1]M , where M is the number of deployed models and si (x) denotes the predicted output quality of model i on prompt x.
Density
Mistral 7B Yi 34B Vicuna 13B
2
1
0 0.0
0.2
0.4
0.6
0.8
1.0
Predicted score
Fig. 3. Distribution of predicted routing scores for different models on RouterBench. Larger models generally achieve higher scores, but the distributions overlap substantially, indicating that a non-trivial fraction of prompts can also be served effectively by smaller models.
In our implementation, the router is instantiated as a DeBERTa-v3-Large encoder [16] with a multi-head regression layer attached to the [CLS] representation, where each head predicts the score of one candidate model. The router is trained on RouterBench [17], which provides prompts paired with model-specific quality scores. The router supplies the per-prompt utility estimates used by our allocation and routing framework, but is not itself the focus of this work. Our formulation is agnostic to the router architecture and only assumes access to per-model quality estimates for each prompt. Figure 3 shows the distribution of predicted scores across models on the RouterBench dataset after training the router model. As expected, larger models tend to achieve higher scores on average. However, the score distributions overlap substantially, indicating that a non-trivial fraction of prompts can also be served effectively by smaller models. This heterogeneity creates an opportunity for more efficient serving, by routing simpler prompts to smaller models while reserving larger models for prompts that benefit most from their additional capability. C. System Setup We consider a multi-model LLM serving system deployed on a GPU cluster with G GPUs and a pool of M models, indexed by i ∈ {1, . . . , M }. The system serves an incoming workload with global arrival rate λ (requests per second). Each model is assigned a setup that specifies both the GPUs on which it is deployed and the resources allocated to it. Formally, the setup of model i is represented as θi = (Gi , tpi , ρi , µi ) ∈ Θi , where Gi ⊆ {1, . . . , G} denotes the set of GPUs assigned to model i, tpi denotes the tensor parallelism level, ρi ∈ (0, 1] denotes the fraction of GPU compute resources allocated to model i (e.g., GPU thread percentage), and µi ∈ (0, 1] denotes the fraction of GPU memory allocated to model i. The set Θi captures all feasible configurations for model i. A system setup is defined as the collection of setups for all models, Θ = (θ1 , θ2 , . . . , θM ) ∈ S,
where S denotes the set of candidate system-level configurations. Feasibility is governed by deployability constraints such as GPU memory capacity, tensor-parallel placement requirements, and the requirement that model shards can be placed on the available GPUs without violating these constraints. In addition to these deployability constraints, we later apply a separate pruning rule that discards setups whose total compute demand is below a specified utilization threshold. Moreover, for each model i and tensor parallelism level tpi , we denote by mi (tpi ) the minimum fraction of GPU memory required by one shard of model i under that tensor parallelism level, as obtained from profiling. This quantity is later used to determine whether the shards induced by a candidate system setup can be feasibly placed on the available GPUs. In addition to the system setup, we consider a workload consisting of prompts drawn from an underlying distribution D. A routing policy is a function π : X → {1, . . . , M }, which maps each input prompt x ∈ X to one of the deployed models. Intuitively, π(x) specifies the model selected to serve prompt x. Our goal is to determine a joint system setup and routing policy that maximize overall utility while satisfying latency requirements. These two decisions are tightly coupled. Changing a model’s setup—for example, by modifying its GPU placement, tensor parallelism level, or allocated compute share— changes its latency and throughput characteristics, which in turn affects the routing policy that should be used. Conversely, the routing policy determines the load presented to each model, which influences how resources should be allocated across the system. This interdependence motivates the joint treatment of resource allocation and routing in our framework. III. P ROBLEM F ORMULATION We now formulate the problem for jointly optimizing resource allocation and routing decisions in a multi-model LLM serving system. As discussed in Section II, these two decisions are tightly coupled: the system setup determines the latency characteristics of each model, while the routing policy determines the average output load assigned to each model. Our goal is therefore to select a system setup and routing policy that together maximize overall utility while satisfying latency requirements. Let Θ ∈ S denote a feasible system setup. At inference time, a routing policy assigns each incoming prompt to one of the deployed models. Although routing decisions are made at the prompt level, over a workload distribution such a policy induces an aggregate traffic split across models. We capture this system-level view using a routing fraction vector w = (w1 , . . . , wM ) ∈ ∆M , ( ) M X M wi = 1 , ∆M ≜ w ∈ R≥0 i=1
(1)
where wi denotes the fraction of prompts routed to model i. Thus, w specifies the aggregate traffic split induced across the M deployed models. The set ∆M is the M -dimensional probability simplex, i.e., the set of all feasible nonnegative routing fraction vectors whose entries sum to one. This fraction-based view allows us to characterize routing at the workload level through two quantities: the maximum achievable average score under a target traffic split, and the resulting latency under a given system setup. a) Maximum achievable score under routing fractions: Let X = {x1 , . . . , xN } denote a finite set of prompts sampled from the workload distribution, and let si (xj ) ∈ [0, 1] denote the predicted score of model i on prompt xj . Given routing fractions w, we define Ŝ(w) as the maximum average score achievable by assigning prompts to models such that model i serves a fraction wi of the workload:
c) Joint optimization problem: Using these definitions, we formulate the joint resource allocation and routing problem as follows: max
Θ∈S, w∈∆M
Ŝ(w)
s.t. L(Θ, w) ≤ τ,
(6)
where τ denotes the latency target. In the next section, we propose our RouterWise method to solve the formalized optimization problem. IV. ROUTERW ISE We now present ROUTERW ISE, our method for solving the joint setup-and-routing problem in Eq. (6). A. RouterWise Pipeline
Ŝ(w) =
N X M X
1 max zji si (xj ) N {zji } j=1 i=1
(2)
subject to
M X
zji ∈ {0, 1},
∀j, i,
(3)
zji = 1,
∀j,
(4)
max Ŝ(w)
i=1 N X
ROUTERW ISE solves the joint setup-and-routing problem in Eq. (6) through three stages. Stage 1: Relax routing under a fixed setup. For a fixed system setup Θ, ROUTERW ISE first considers the latencyconstrained routing problem
∀i.
zji = ci ,
(5)
j=1
where zji = 1 indicates that prompt xj is assigned to model i, and ci denotes the target number of prompts assigned to model i, with M X
ci = N,
ci ≈ N wi .
i=1
w∈∆M
s.t. L(Θ, w) ≤ τ,
where Ŝ(w) is the maximum achievable average score under routing fractions w, and L(Θ, w) is the corresponding latency under setup Θ. To make this problem tractable, ROUTERW ISE relaxes the latency constraint using a Lagrange multiplier β ≥ 0 and defines the objective J (Θ, w; β) = Ŝ(w) − β L(Θ, w) − τ .
(7)
For a fixed setup Θ and a fixed value of β, ROUTERW ISE then solves max J (Θ, w; β).
b) Latency under system setup and routing fractions: Let λ denote the global arrival rate. Under routing fractions w, model i receives load λi = λwi . Given a system setup Θ, we denote by L(Θ, w) the resulting average latency metric under routing fractions w. Depending on the target service-level objective (SLO), L(Θ, w) may represent average end-to-end latency, average time to first token (TTFT), or average time per output token (TPOT). For request-level average latency metrics, we define L(Θ, w) =
M X
wi ℓi (Θ, λwi ),
i=1
where ℓi (Θ, λi ) denotes the corresponding average latency of model i under setup Θ and load λi .
w∈∆M
Stage 2: Search over the Lagrange multiplier. For a fixed setup Θ, different values of β produce different operating points on the score-latency trade-off curve. Smaller values of β place more emphasis on score, while larger values penalize latency more strongly and therefore favor lowerlatency routing fractions. ROUTERW ISE searches over β to identify the operating point that best satisfies the latency target for the given setup. Stage 3: Search over feasible system setups. After computing the best feasible routing solution for a fixed setup, ROUTERW ISE searches over the feasible system setups and selects the setup that yields the highest score while satisfying the latency constraint. Sections IV-B and IV-C introduce the two components required to evaluate the relaxed objective, and Section IV-D describes how ROUTERW ISE combines them in the optimization procedure.
60 40 20 0
10
20
30
Mean TTFT (ms)
80
Mean TTFT (ms)
Mean TTFT (ms)
tp = 4, ρ = 100% tp = 4, ρ = 70% tp = 2, ρ = 100% tp = 2, ρ = 70%
100
80
60
40
40
Input load (RPS)
(a) Mistral 7B
5
10
15
400
200
20
2
Input load (RPS)
4
6
8
10
12
14
Input load (RPS)
(b) Vicuna 13B
(c) Yi 34B
Fig. 4. Average TTFT as a function of input load under different tensor parallelism levels and maximum GPU compute shares (ρ) for three models. Each curve corresponds to a different setup, showing that the latency-load relationship varies substantially across model sizes and deployment configurations.
B. Dual-Price Formulation of the Score Function Ŝ(w) Proposition 1 (Dual-price characterization of the score function). Consider the primal score-maximization problem in Eqs. (2)–(5), where the target number of prompts assigned to model i is ci . Let αi ∈ R denote the dual variable associated with the count constraint N X
zji = ci .
j=1
Then, after dualizing these count constraints, the resulting dual problem is min g(α), α∈RM
where N M X 1 X g(α) = max si (xj ) − αi + αi ci . (8) N j=1 i∈{1,...,M } i=1 Moreover, for any fixed dual vector α, the maximizing assignment in the inner problem is obtained independently for each prompt xj as i∗ (xj ; α) = arg max si (xj ) − αi . i∈{1,...,M }
Thus, the dual variables αi admit a natural interpretation as model-specific prices: increasing αi makes model i less attractive in the prompt assignment, while decreasing αi makes it more attractive. □
Proof. See Appendix A.
Proposition 2 (Convexity of the dual objective). The dual objective in Eq. (8) is convex with respect to the dual variable vector α ∈ RM . Proof. See Appendix B. □ By Proposition 2, the dual objective in Eq. (8) is convex in α. Therefore, ROUTERW ISE can solve the dual problem efficiently using the subgradient method. In each iteration, ROUTERW ISE first computes the prompt-level assignments induced by the current dual prices according to i∗ (xj ; α) = arg max si (xj ) − αi , i∈{1,...,M }
and then counts how many prompts are assigned to each model. Let N X ni (α) = 1[i∗ (xj ; α) = i] j=1
denote the number of prompts assigned to model i under the current dual vector α. A subgradient of g(α) with respect to αi is then given by 1 ci − ni (α) . N ROUTERW ISE therefore updates the dual prices as 1 (t+1) (t) αi = αi + ηt ni (α(t) ) − ci , N where ηt is the step size. Intuitively, if model i receives more prompts than its target count ci , its price is increased, making it less likely to be selected in subsequent iterations; if it is under-assigned, its price is decreased. C. Latency Modeling for a Fixed System Setup To optimize the relaxed objective in Eq. (7), ROUTERW ISE requires a latency model that predicts how each deployed model behaves under different resource allocations and traffic loads. In our setting, latency depends not only on the input load λ, but also on the serving configuration of the model, including its tensor parallelism level (tp) and assigned GPU compute share (ρ). As a result, latency behavior is highly setup-dependent. Our profiling on deploying three models on A100 GPUs further show that latency characteristics vary substantially not only across setups, but also across model families. Figure 4 illustrates this behavior for three representative models under different tensor parallelism levels and GPU thread allocations. The latency-load relationship changes significantly across models and configurations, both in scale and in shape. Moreover, the effect of a configuration knob is not uniform across models: for example, for Mistral 7B, a tensor parallelism level of 2 yields lower TTFT than 4 across a broad range of loads. This variability makes it difficult to construct a single unified latency predictor that generalizes accurately across all models, setups, and operating regimes. ROUTERW ISE therefore adopts a setup-specific latency modeling strategy. We discretize the setup space into a finite
set of feasible configurations. In our experiments, the tensor parallelism level is chosen from {1, 2, 4}, and the GPU thread percentage is selected from a predefined discrete set. For each model and each feasible setup, we profile the model under multiple input load levels and record latency statistics such as TTFT and TPOT. For a fixed model and setup, these measurements define a one-dimensional latency curve as a function of input load. ROUTERW ISE approximates this curve using a piecewiselinear model constructed from the profiled operating points. Let θi denote a fixed setup of model i, and let ℓi (θi , λi ) denote the latency metric of interest under load λi . We model ℓi (θi , λi ) by linearly interpolating between neighboring profiled load points. This yields a simple and efficient representation while preserving the setup-specific latency behavior observed in profiling. Once a system setup Θ is fixed, the corresponding permodel latency functions {ℓi (θi , ·)}M i=1 are also fixed. ROUTER W ISE then evaluates the latency term L(Θ, w) =
M X
wi ℓi (θi , λwi )
i=1
for request-level average latency metrics. This provides the latency component required to solve the relaxed optimization problem for a fixed system setup. This setup-specific modeling strategy avoids imposing a single smooth latency model over a heterogeneous configuration space. Instead, ROUTERW ISE treats each model–setup pair as a distinct operating regime and uses profiling to characterize its load-dependent latency accurately.
Since Θ is fixed, the optimization is carried out only over the routing fractions w. ROUTERW ISE solves this problem using projected gradient ascent on the simplex ∆M . At each iteration, the score term Ŝ(w) is evaluated using the dual-price formulation in Section IV-B. For the current routing fractions w, ROUTERW ISE solves the corresponding dual problem to obtain the optimal dual prices α⋆ . By Proposition 3, these dual prices give the gradient of the score term with respect to the routing fractions: ∇w Ŝ(w) = α⋆ . The latency term L(Θ, w) is evaluated using the setupspecific piecewise-linear latency models described in Section IV-C. For request-level average latency metrics, L(Θ, w) =
M X
wi ℓi (θi , λwi ),
i=1
D. Optimization Procedure We now describe the optimization procedure used to solve the ROUTERW ISE pipeline introduced in Section IV-A. We begin by considering a fixed system setup Θ and a fixed Lagrange multiplier β, and show how to optimize the relaxed objective in Eq. (7) with respect to the routing fractions. We then sweep over β to recover the best routing solution for that setup that satisfies the latency constraint. Finally, we repeat this procedure across feasible system setups and select the setup that achieves the highest score while meeting the latency target. Proposition 3 (Gradient of the score function). Assume that Ŝ(w) is differentiable at the current routing fractions w. Under the continuous approximation ci = N wi , let α⋆ denote an optimal solution of the dual problem in Proposition 1. Then ⋆
∇w Ŝ(w) = α . Proof. See Appendix C. □ Stage 1: Optimize routing fractions for fixed (Θ, β). For a fixed system setup Θ and a fixed Lagrange multiplier β, ROUTERW ISE solves max J (Θ, w; β) = Ŝ(w) − β L(Θ, w) − τ . w∈∆M
Algorithm 1 O PTIMIZE F RACTIONS(Θ, β) Require: Fixed setup Θ, multiplier β, initial routing fractions −1 w(0) ∈ ∆M , step sizes {ηt }Tt=0 , maximum iterations T Ensure: Optimized routing fractions w⋆ 1: w ← w (0) 2: for t = 0, 1, . . . , T − 1 do 3: Solve the dual problem for Ŝ(w) and obtain α⋆ 4: Set gŜ ← α⋆ 5: Evaluate L(Θ, w) and ∇w L(Θ, w) 6: Set g ← gŜ − β∇w L(Θ, w) 7: Update w ← Π∆M (w + ηt g) 8: end for 9: return w
where ℓi (θi , λi ) denotes the latency of model i under setup θi and load λi . Since each ℓi (θi , λi ) is piecewise linear in λi , its derivative with respect to load is given by the slope of the active segment. Therefore, ∂L(Θ, w) ∂ℓi (θi , λi ) = ℓi (θi , λwi ) + λwi ∂wi ∂λi
. λi =λwi
Combining the two terms, the gradient of the relaxed objective is ∇w J (Θ, w; β) = α⋆ − β∇w L(Θ, w). ROUTERW ISE then updates the routing fractions as w(t+1) = Π∆M w(t) + ηt ∇w J (Θ, w(t) ; β) , where ηt is the step size and Π∆M denotes projection onto the simplex ∆M defined in Eq. (1), i.e., after each gradient step, the updated vector may no longer represent a valid routing fraction vector since its entries may not remain nonnegative or sum to one. We therefore project it to the closest point in ∆M using the method of [18]. This procedure is summarized in Algorithm 1. Stage 2: Search for the optimal β. For a fixed system setup Θ, different values of β produce different operating
Algorithm 2 O PTIMIZE B ETA(Θ) Require: Fixed system setup Θ, arrival rate λ, latency target τ , lower and upper bounds βmin , βmax , latency tolerance ε Ensure: Best routing fractions w⋆ and corresponding β ⋆ for setup Θ 1: w ⋆ ← ∅, β ⋆ ← ∅ 2: while βmax − βmin > ε do 3: β ← (βmin + βmax )/2 4: w ← O PTIMIZE F RACTIONS(Θ, β) 5: Evaluate L(Θ, w) 6: if L(Θ, w) > τ then 7: βmin ← β ▷ Latency too high; penalize more 8: else 9: βmax ← β 10: w⋆ ← w, β ⋆ ← β 11: end if 12: end while 13: return (w ⋆ , β ⋆ )
points on the score-latency trade-off curve. Smaller values of β place more emphasis on maximizing score, while larger values penalize latency more strongly and therefore favor lower-latency routing fractions. ROUTERW ISE uses bisection to search for the value of β whose corresponding solution satisfies the latency target τ . At each step, it solves the relaxed problem for the current β, evaluates the resulting latency, and then adjusts the search interval accordingly. Once the target latency is met within a tolerance, ROUTERW ISE returns the corresponding routing solution as the best achievable score for the fixed setup. The overall bisection-based search over β is summarized in Algorithm 2. Stage 3: Evaluate and select the best setup. ROUTERW ISE selects the final system setup by enumerating candidate setups from a discretized setup space S. Specifically, for each model i, we discretize its tensor parallelism level tpi and GPU compute fraction ρi , and construct S as the Cartesian product of these per-model configuration choices. Each candidate setup is then filtered through a compute-utilization pruning rule and a deployability check before optimization. For a candidate setup Θ = (θ1 , . . . , θM ), model i contributes tpi shards, where tpi is taken directly from its setup θi . ROUTERW ISE first computes the total compute demand C(Θ) =
M X
tpi ρi
i=1
and discards setups whose aggregate compute demand is below a prescribed utilization threshold, i.e., C(Θ) < Gρmin , as well as setups whose compute demand exceeds the total available budget, i.e., C(Θ) > G. It then checks whether the setup is deployable under GPU memory and placement constraints. Specifically, it constructs a shard memory list Q(Θ) by adding mi (tpi ) once for each shard of model i, and verifies that all shards can be placed on the G GPUs using first-fit decreasing
(FFD), without co-locating multiple shards of the same model on the same GPU. Setups that fail this placement test are considered infeasible and are discarded. For each remaining feasible setup, ROUTERW ISE runs O PTIMIZE B ETA to obtain the best routing solution under the latency target. If the resulting latency satisfies τ , the corresponding score is compared against the best score found so far. The final output is the feasible setup-routing pair (Θ⋆ , w⋆ ) with the highest achievable score. The complete procedure is summarized in Algorithm 3. The complexity of ROUTERW ISE is dominated by the search over candidate system setups. Let Ki denote the number of discretized configuration choices for model i, induced by the candidate tensor-parallelism levels and GPU thread percentages. A naive enumeration would therefore consider QM K system setups, which can be large even for a modi i=1 erate number of models. However, in practice, ROUTERW ISE prunes a substantial fraction of these candidates before optimization. In particular, setups with aggregate compute demand below the utilization threshold or above the total available compute budget are discarded immediately, and many of the remaining candidates are further removed by the deployability check under GPU memory and placement constraints. Let Se ⊆ S denote the retained setup set after pruning. The overall come plexity can then be written as O |S| · CO PTIMIZE B ETA , where CO PTIMIZE B ETA is the cost of solving the routing problem for one retained setup. Since O PTIMIZE B ETA performs a bisection search over β, and each iteration invokes O PTIMIZE F RAC TIONS, we have CO PTIMIZE B ETA = O(Tβ CO PTIMIZE F RACTIONS ), where Tβ is the number of bisection steps. Thus, although the worst-case setup space is combinatorial in the number of discretized choices, the effective running time is governed by the much smaller set of retained setups after pruning. V. E VALUATION A. Experimental Setup We evaluate our ROUTERW ISE framework on GPU clusters with G ∈ {4, 8} GPUs. All experiments are conducted assuming NVIDIA A100 80GB PCIe GPUs. These two cluster sizes allow us to study the behavior of the proposed method under both moderate and larger deployment budgets. While most prior routing work focuses on routing between two models [8]–[11], [19], we consider a more general multimodel setting with three models of different sizes and capabilities: mistral-7b-chat [20], WizardLM-13B-V1.2 [21], and Yi-34B-Chat [22]. These models are selected from the RouterBench dataset [17], which contains 36,000 prompts together with model outputs and model-specific quality scores derived from benchmark correctness criteria. Each model is served using vLLM [23], and all latency profiling used to construct the setup-specific latency models is also conducted with vLLM. Following the routing setup described in Section II-B, we train a multi-head DeBERTa-v3-Large [16] router on RouterBench, where each head predicts the output quality of one candidate model. At inference time, given an
Retained setups
Retained setups
Retained setups 510
500
505
740
Retained setups Latency target τ
720
Equal-Split Size-Proportional Isolated Best setup
700 680
0.40
0.45
450 425
Retained setups Latency target τ
400
Equal-Split Size-Proportional Isolated Best setup
375 350 0.50
0.55
0.35
0.40
Best achievable score
λ = 50, τ = 800
480
460
440
420 0.45
0.50
0.55
Latency (ms)
Latency (ms)
760
Latency (ms)
475
780
Latency (ms)
Retained setups
500
800
0.38
Retained setups Latency target τ Equal-Split Size-Proportional Best setup
500 495 490
Retained setups Latency target τ
485
Equal-Split Size-Proportional Best setup
480 475
0.40
0.42
0.44
0.46
0.48
0.50
0.52
0.54
0.485
0.490
0.495
0.500
Best achievable score
Best achievable score
Best achievable score
λ = 60, τ = 500
λ = 70, τ = 500
λ = 80, τ = 500
0.505
(a) G = 4: Maximum achievable score in different setups with 4 GPUs.
Retained setups Latency target τ Equal-Split Size-Proportional Isolated Best setup
390
385 0.53
0.54
0.55
404
500
505.0
402
480
502.5 500.0
Retained setups Latency target τ
497.5
Equal-Split Size-Proportional Isolated Best setup
495.0 492.5 0.56
0.57
0.58
0.400
0.425
0.450
0.475
400 398 396 394 392
0.500
0.525
0.550
Latency (ms)
400
Retained setups
507.5
Latency (ms)
Latency (ms)
Latency (ms)
405
395
Retained setups
Retained setups
Retained setups
Retained setups Latency target τ Equal-Split Size-Proportional Best setup 0.515
0.520
0.525
460 440
Retained setups Latency target τ
420
Equal-Split Size-Proportional Best setup
400
0.530
0.535
0.540
0.545
0.505
0.510
0.515
0.520
0.525
Best achievable score
Best achievable score
Best achievable score
Best achievable score
λ = 50, τ = 400
λ = 60, τ = 500
λ = 70, τ = 400
λ = 80, τ = 500
0.530
(b) G = 8: Maximum achievable score in different setups with 8 GPUs. Fig. 5. Score-latency scatter plots of retained setups under two settings of G, where retained setups denote deployable setups that also pass the computeutilization filter. Row (a) shows the case G = 4, and row (b) shows the case G = 8.
input prompt, the router outputs a score for each model; these scores are used as the per-model utility estimates in ROUTERW ISE and enter the dual-price formulation through the adjusted assignment rule si (x) − αi . For the system setup space, the tensor parallelism level of each model is selected from {1, 2, 4}. In addition, the GPU compute fraction assigned to each model, implemented through GPU thread percentage, is discretized into {10, 20, 30, . . . , 100}. As described, shards of the same model are not allowed to be co-located on the same GPU. ROUTER W ISE enumerates candidate system setups from this discretized configuration space and filters them through the feasibility checks described in Section IV-D. B. Metrics and Baselines Our evaluation aims to quantify the impact of resource allocation on the best achievable routing performance under latency constraints. In particular, we study how different feasible system setups affect the trade-off between output quality and latency, and whether jointly optimizing setup and routing yields better operating points than simpler allocation strategies. For a fixed GPU count, input load, and latency target, we evaluate each deployable setup that also passes the computeutilization filter by solving for its best routing solution using ROUTERW ISE. We then record the resulting achievable score and latency, and visualize the distribution of feasible setups in the score–latency plane. This analysis makes the role of resource allocation explicit: it shows how different deployment setups can lead to substantially different maximum achievable scores under the same latency budget. In doing so, it highlights an important factor that is largely overlooked in prior routing
studies, which typically treat model cost and latency as fixed and therefore ignore the impact of resource allocation on routing performance. Existing multi-model routing methods typically treat the cost and latency of each candidate model as fixed, ignoring their dependence on deployment configuration, resource allocation, and induced load. Consequently, prior methods do not address the setup-selection component of our problem and do not provide direct baselines for joint resource allocation and routing. We therefore introduce three resource-allocation baselines for comparison. Equal-Split Setup. This baseline allocates the available GPU compute budget equally across the deployed models. Concretely, for a cluster with G GPUs and M models, each model is assigned a target compute budget of G/M . The final setup is chosen from the same discretized configuration space as ROUTERW ISE by selecting the feasible setup whose per-model allocations best match this equal-share target. Size-Proportional Setup. This baseline allocates resources in proportion to model size. Let pi denote the parameter count of model i. The target computePbudget of model i is then set proportional to pi , i.e., Gpi / k pk . As in the equal-split baseline, the final deployment is selected from the feasible discretized setup space by choosing the setup whose per-model allocations best match these size-proportional targets. Isolated Setup. This baseline disables co-location and deploys model shards in isolation on dedicated GPUs whenever feasible. It reflects a conventional deployment strategy in which models do not share GPUs and therefore cannot benefit from fine-grained resource sharing. This baseline is included to quantify the benefit of co-located deployment and flexible
resource allocation in ROUTERW ISE. C. Evaluation Results Figure 5 visualizes the score–latency operating points obtained under different retained system setups for each evaluation setting. Each point corresponds to the best routing solution found for one deployable setup that also passes the computeutilization filter. In the experiments of Fig. 5, we set ρmin = 1. This choice reflects the fact that, under NVIDIA MPS, the thread percentage assigned to a process acts as a cap on the fraction of GPU compute resources that the corresponding model shard can use. Therefore, if the aggregate compute cap assigned to the processes sharing a GPU is below 100%, then part of the GPU compute capacity cannot be utilized concurrently, even when sufficient workload is available. By enforcing ρmin = 1, we exclude underutilized setups in which the total assigned compute cap leaves GPU resources idle, and focus the comparison on setups that can fully utilize the available compute budget. This makes the effect of resource allocation more meaningful: the differences observed in Fig. 5 are not due to trivially leaving GPU compute unused, but rather to how
Feasible configs
Feasible configs
Algorithm 3 S ELECT S ETUP Require: Candidate setup space S, GPUs G, latency target τ Ensure: Best setup-routing pair (Θ⋆ , w⋆ ) 1: BestScore ← −∞, (Θ⋆ , w ⋆ ) ← ∅ 2: for each Θ = (θ1 , θ2 , . . . , θM ) ∈ S do PM 3: C(Θ) ← i=1 θi .ρ θi .tp 4: // Prune underutilized or over-budget setups 5: if C(Θ) < Gρmin or C(Θ) > G then 6: continue 7: end if... 8: // Check deployability under memory and placement constraints 9: if FFD-F EASIBLE(Q(Θ), G) is false then 10: continue 11: end if 12: Q(Θ) ← [ ] 13: for i = 1, . . . , M do 14: for r = 1, . . . , θi .tp do 15: append mi (θi .tp) to Q(Θ) 16: end for 17: end for 18: if FFD-Feasible(Q(Θ), G) is false then 19: continue 20: end if 21: (w, β) ← O PTIMIZE B ETA(Θ) 22: if L(Θ, w) ≤ τ and Ŝ(w) > BestScore then 23: BestScore ← Ŝ(w) 24: (Θ⋆ , w⋆ ) ← (Θ, w) 25: end if 26: end for 27: return (Θ⋆ , w ⋆ )
600 400 200 1
2
3
4
5
6
7
GPUs
(a) Three-model setting
8
15000 10000 5000 0 1
2
3
4
5
6
7
8
GPUs
(b) Four-model setting
Fig. 6. Scalability of the setup space as the number of GPUs increases. Each plot shows the number of retained system setups for a fixed model pool, where retained setups denote deployable setups that also pass the compute-utilization filter. Plot (a) corresponds to the three-model setting, and plot (b) corresponds to the four-model setting.
the available compute and memory resources are distributed across models. A clear trend emerges from these plots: different retained setups can lead to substantially different achievable scores, even under the same GPU count, input load, and latency target. This variation is notable because all plotted setups are deployable and pass the compute-utilization filter, meaning that they do not leave obvious compute resources idle. In other words, even when GPU compute can be actively utilized through MPS-based sharing, the particular allocation of compute and memory across models still has a major effect on the best routing performance that can be achieved. In our experiments, even in settings where ρ = 1 and the full compute share can be activated, we observe average relative scores ranging from 0.30 to 0.56 across retained setups. This result shows that resource allocation is not merely a deployment detail, but a key factor in determining the maximum achievable output quality under latency constraints. We also observe that the number of retained setups is smaller for G = 8 than for G = 4. With a larger GPU budget, candidate configurations can assign higher tensor-parallelism levels and larger compute shares to models more easily, so many setups quickly consume most of the available compute budget. This makes the utilization filter more selective and leaves a smaller set of retained setups. In contrast, the G = 4 case admits a larger variety of intermediate allocations, resulting in a denser distribution of retained setups. In addition, as the input load increases, fewer retained setups are able to satisfy the latency target, since more configurations incur excessive delay under higher offered load. Consequently, the number of plotted setups also decreases with increasing load. D. Scalability Analysis Figure 6 shows how the number of retained system setups grows as the number of deployed models increases. For the three-model setting, the retained setup space contains roughly 700 candidates, while for the four-model setting it increases to about 16,000. Although the setup space grows substantially with the number of models, the optimization remains practically manageable in our setting: in our implementation, evaluating one retained setup takes about one second
on average, which allows ROUTERW ISE to handle both the three-model and four-model cases within a reasonable time. This is particularly relevant because prior multi-model routing studies predominantly focus on two-model settings, whereas our results show that the proposed framework can scale to richer deployment scenarios with three and four candidate models. VI. C ONCLUSION In this paper, we presented ROUTERW ISE, a framework for jointly optimizing resource allocation and routing in latency-aware multi-model LLM serving. To the best of our knowledge, this is the first work to explicitly investigate how resource allocation affects routing performance in multi-model LLM systems. Unlike prior routing methods, which typically assume fixed per-model cost and latency, our formulation captures the fact that model latency depends strongly on both deployment configuration and induced load. We formalized this setting as a constrained joint optimization problem over system setup and routing fractions, and proposed a practical solution based on a dual-price formulation of the routing objective together with setup-specific latency models derived from profiling. Our results show that different retained setups on the same GPU cluster can yield substantially different achievable output quality, demonstrating that resource allocation is not merely a systems detail but a key determinant of routing performance. We believe this work opens several promising directions for future research. One important direction is improving scalability to larger candidate model pools and larger cluster sizes through more efficient setup search or learned pruning strategies. Another is extending the framework to jointly reason about multiple input-load regimes, rather than optimizing for a single fixed arrival rate. A further direction is to study robustness under input distribution shift, where both routing behavior and system-level demand may change over time. More broadly, our work suggests that bringing systems considerations into routing can open the door to a richer class of methods for adaptive, deployment-aware multi-model LLM serving. VII. L IMITATIONS Our current framework is designed for multi-model deployments with up to four candidate models across different GPU cluster sizes. This already extends beyond the common bimodel setting used in much of the prior routing literature, but investigating how to efficiently support a larger number of deployed models remains an important direction for future work. In particular, as the number of candidate models grows, the setup space expands rapidly, which motivates the development of more scalable setup-search and pruning strategies. In addition, our formulation assumes that input prompts are drawn from a fixed underlying distribution, which is used both in router training and in estimating the routing objective. In practical deployments, however, the prompt distribution may change over time due to workload evolution or domain shift.
Making the system robust to such input-distribution changes, and adapting routing and resource allocation decisions online as workloads evolve, is left for future work. VIII. ACKNOWLEDGEMENTS We used AI-based tools to assist with proofreading and improving the clarity and presentation of the manuscript. R EFERENCES [1] Z. Mo, J. Liao, H. Xu, Z. Zhou, and C. Xu, “Hetis: Serving llms in heterogeneous gpu clusters with fine-grained and dynamic parallelism,” in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2025, pp. 1710–1724. [Online]. Available: https://doi.org/10.1145/3712285.3759784 [2] T. Guo, X. Zhang, J. Du, Z. Chen, N. Xiao, and Y. Lu, “gllm: Global balanced pipeline parallelism systems for distributed llms serving with token throttling,” in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2025, pp. 1725–1741. [Online]. Available: https: //doi.org/10.1145/3712285.3759823 [3] OpenAI, “ChatGPT,” https://openai.com, 2025. [4] Anthropic, “Claude,” https://www.anthropic.com, 2025. [5] Meta AI, “The Llama 4 Herd: The beginning of a new era of natively multimodal AI innovation,” Meta AI Blog, April 2025, technical Release and Model Documentation. [Online]. Available: https://ai.meta.com/blog/llama-4-multimodal-intelligence/ [6] A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv et al., “Qwen3 technical report,” arXiv preprint arXiv:2505.09388, 2025. [Online]. Available: https://doi.org/10.48550/arXiv.2505.09388 [7] D. Ding, A. Mallick, S. Zhang, C. Wang, D. Madrigal, M. D. C. H. Garcia, M. Xia, L. V. S. Lakshmanan, Q. Wu, and V. Rühle, “BEST-Route: Adaptive LLM routing with test-time optimal compute,” in Proceedings of the International Conference on Machine Learning, 2025. [Online]. Available: https://doi.org/10.48550/arXiv.2506.22716 [8] K. Lu, H. Yuan, R. Lin, J. Lin, Z. Yuan, C. Zhou, and J. Zhou, “Routing to the expert: Efficient reward-guided ensemble of large language models,” in Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2024, pp. 1964–1974. [Online]. Available: https://doi.org/10.18653/v1/2024.naacl-long.109 [9] L. Chen, M. Zaharia, and J. Zou, “FrugalGPT: How to use large language models while reducing cost and improving performance,” Transactions on Machine Learning Research, 2023. [Online]. Available: https://doi.org/10.48550/arXiv.2305.05176 [10] I. Ong, A. Almahairi, V. Wu, W.-L. Chiang, T. Wu, J. E. Gonzalez, M. W. Kadous, and I. Stoica, “RouteLLM: Learning to route LLMs from preference data,” in Proceedings of the International Conference on Learning Representations, 2025. [Online]. Available: https://doi.org/10.48550/arXiv.2406.18665 [11] D. Ding, A. Mallick, C. Wang, R. Sim, S. Mukherjee, V. Rühle, L. V. S. Lakshmanan, and A. H. Awadallah, “Hybrid LLM: Cost-efficient and quality-aware query routing,” in Proceedings of the International Conference on Learning Representations, 2024. [Online]. Available: https://doi.org/10.48550/arXiv.2404.14618 [12] Y.-N. Chuang, P. K. Sarma, P. Gopalan, J. Boccio, S. Bolouki, X. Hu, and H. Zhou, “Learning to route LLMs with confidence tokens,” in Proceedings of the International Conference on Machine Learning, 2025. [Online]. Available: https://doi.org/10.48550/arXiv.2410.13284 [13] H. H. Kasnavieh, G. Haffari, C. Leckie, and A. N. Toosi, “Introlm: Introspective language models via prefilling-time selfevaluation,” arXiv preprint arXiv:2601.03511, 2026. [Online]. Available: https://doi.org/10.48550/arXiv.2601.03511 [14] Y. Xiang, X. Li, K. Qian, Y. Yang, D. Zhu, W. Yu, E. Zhai, X. Liu, X. Jin, and J. Zhou, “Aegaeon: Effective gpu pooling for concurrent llm serving on the market,” in Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles, 2025, pp. 1030–1045. [15] NVIDIA, NVIDIA CUDA Multi-Process Service, 2025, nVIDIA Deployment Guide, Release r590. [Online]. Available: https://docs. nvidia.com/deploy/mps/index.html
[16] P. He, X. Liu, J. Gao, and W. Chen, “DeBERTa: Decoding-enhanced BERT with disentangled attention,” arXiv preprint arXiv:2006.03654, 2020. [Online]. Available: https://doi.org/10.48550/arXiv.2006.03654 [17] Q. J. Hu, J. Bieker, X. Li, N. Jiang, B. Keigwin, G. Ranganath, K. Keutzer, and S. K. Upadhyay, “Routerbench: A benchmark for multiLLM routing system,” in Agentic Markets Workshop at ICML 2024, 2024. [Online]. Available: https://doi.org/10.48550/arXiv.2403.12031 [18] J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra, “Efficient projections onto the l1-ball for learning in high dimensions,” in Proceedings of the 25th International Conference on Machine Learning, ser. ICML ’08. New York, NY, USA: Association for Computing Machinery, 2008, p. 272–279. [Online]. Available: https://doi.org/10.1145/1390156.1390191 [19] P. Aggarwal, A. Madaan, A. Anand, S. P. Potharaju, S. Mishra, P. Zhou, A. Gupta, D. Rajagopal, K. Kappaganthu, Y. Yang et al., “AutoMix: Automatically mixing language models,” Advances in Neural Information Processing Systems, 2023. [Online]. Available: https://doi.org/10.48550/arXiv.2310.12963 [20] Mistral AI Team, “Introducing Mistral 3,” Mistral AI Blog, December 2025, official Model Release and Technical Documentation. [Online]. Available: https://mistral.ai/news/mistral-3 [21] C. Xu, Q. Sun, K. Zheng, X. Geng, P. Zhao, C. Feng, and D. Tao, “Wizardlm: Empowering large language models to follow complex instructions,” arXiv preprint arXiv:2304.12244, 2023. [Online]. Available: https://doi.org/10.48550/arXiv.2304.12244 [22] A. Young, B. Chen, B. Li, C. Cai, D. Cao, G. Ge, H. Li, H. Lin, N. Ning, J. Qu, S. Rajasekaran et al., “Yi: Open foundation models by 01.ai,” arXiv preprint arXiv:2403.04652, 2024. [Online]. Available: https://doi.org/10.48550/arXiv.2403.04652 [23] W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. Gonzalez, H. Zhang, and I. Stoica, “Efficient memory management for large language model serving with pagedattention,” in Proceedings of the 29th Symposium on Operating Systems Principles, ser. SOSP ’23. New York, NY, USA: Association for Computing Machinery, 2023, p. 611–626. [Online]. Available: https://doi.org/10.1145/3600006.3613165
A PPENDIX A P ROOF OF P ROPOSITION 1
The corresponding Lagrangian is N M M N X 1 XX 1 X J (Z, α) = αi ci − zji si (xj )+ zji . N j=1 i=1 N i=1 j=1 (13) Rearranging (13) gives N M M X 1 X X J (Z, α) = zji si (xj ) − αi + αi ci . (14) N j=1 i=1 i=1 PM For fixed α, the term i=1 αi ci is constant with respect to the assignment variables. Therefore, maximizing J (Z, α) over Z reduces to maximizing N X M X j=1 i=1
subject to the remaining constraints M X
zji ∈ {0, 1},
zji = 1
∀j.
i=1
These constraints couple variables only within each prompt j. Hence, the maximization decomposes across prompts. For a fixed prompt xj , assigning it to model i contributes
to the objective. Since each prompt must be assigned to exactly one model, the optimal choice is i∗ (xj ; α) = arg
1 zji si (xj ) max Ŝ(w) = N {zji } j=1 i=1
si (xj ) − αi
In this appendix, we derive the dual-price formulation of the primal score-maximization problem. Recall the primal problem: M N X X
zji si (xj ) − αi
max
i∈{1,...,M }
si (xj ) − αi .
(15)
(9) Substituting this optimal prompt-wise assignment into (14) yields the dual function
subject to
M X i=1 N X
zji ∈ {0, 1},
∀j, i,
(10)
zji = 1,
∀j,
(11)
zji = ci ,
∀i.
(12)
g(α) = max J (Z, α) Z N M X 1 X max si (xj ) − αi + αi ci . (16) = N j=1 i∈{1,...,M } i=1 Therefore, the dual problem is
j=1
min g(α),
Here, zji = 1 indicates that prompt xj is assigned to model i, and ci is the target number of prompts assigned to model i. We derive the dual by dualizing only the target-count constraints (12). Let αi ∈ R denote the dual variable associated with the constraint N X zji = ci . j=1
α∈RM
(17)
where g(α) is given by (16). This proves the dual-price characterization in Proposition 1. In addition, (15) shows that, for fixed dual prices α, the maximizing inner assignment is obtained independently for each prompt by selecting the model with the largest adjusted score si (xj ) − αi .
A PPENDIX B P ROOF OF P ROPOSITION 2 In this appendix, we prove that the dual objective N M X 1 X si (xj ) − αi + g(α) = max α i ci N j=1 i∈{1,...,M } i=1
Assume that V (c) is differentiable at the current c, and let α⋆ (c) be an optimal dual solution. Since the dependence of g(α; c) on c appears only through the linear term M
1 X αi ci , N i=1 the envelope theorem gives
is convex in α ∈ RM . For each prompt xj , define hj (α) =
max
i∈{1,...,M }
∂V (c) ∂g(α; c) αi⋆ = = . ∂ci ∂ci N α=α⋆ si (xj ) − αi .
Then g(α) can be written as N M X 1 X g(α) = hj (α) + α i ci . N j=1 i=1
Now define Ŝ(w) = V (c) under the continuous approximation ci = N wi . Applying the chain rule, M
∂ Ŝ(w) X ∂V (c) ∂ck = . ∂wi ∂ck ∂wi k=1
Because ck = N wk , ∂ck = N 1[k = i]. ∂wi
We first show that each function hj (α) is convex. For any fixed model i, the function hj,i (α) = si (xj ) − αi is affine in α, since it is a constant si (xj ) plus a linear term −αi . The function hj (α) is the pointwise maximum of the finite collection of affine functions {hj,i (α)}M i=1 . A pointwise maximum of affine functions is convex. Therefore, each hj (α) is convex. Next, the term M X α i ci i=1
is linear in α, and every linear function is both convex and concave. Therefore, this term is convex. Finally, g(α) is obtained by summing PM the convex functions {hj (α)}N and the linear term j=1 i=1 αi ci , and then scaling the result by the positive constant 1/N . Since nonnegative weighted sums of convex functions remain convex, it follows that g(α) is convex in α. This proves Proposition 2. A PPENDIX C P ROOF OF P ROPOSITION 3 Let V (c) =
N X M X 1 max zji si (xj ) N {zji } j=1 i=1
denote the optimal value of the count-constrained scoremaximization problem as a function of the target count vector c = (c1 , . . . , cM ). By Proposition 1, V (c) admits the dual representation V (c) = min g(α; c), α∈RM
where N M X X 1 g(α; c) = max si (xj ) − αi + αi ci . N j=1 i i=1
Therefore, α⋆ ∂ Ŝ(w) = i · N = αi⋆ . ∂wi N Hence, ∇w Ŝ(w) = α⋆ . This proves the proposition.