Principled Model Routing for Unknown Mixtures of Source Domains
Authors: Christoph Dann
Yishay Mansour
Teodor Vanislavov Marinov
Mehryar Mohri
Venue: NeurIPS 2025 poster ()
Keywords: model routing
domain adaptation
theory
Primary area: general_machine_learning

Abstract: The rapid proliferation of domain-specialized machine learning models
presents a challenge: while individual models excel in specific
domains, their performance varies significantly across diverse
applications. This makes selecting the optimal model when faced with
an unknown mixture of tasks, especially with limited or no data
to estimate the mixture, a difficult problem.  We address this
challenge by formulating it as a multiple-source domain adaptation
(MSA) problem. We introduce a novel, scalable algorithm that
effectively routes each input to the best-suited model from a pool of
available models.  Our approach provides a strong performance
guarantee: remarkably, for any mixture domain, the accuracy achieved by the best
source model is maintained.  This guarantee is established through a
theoretical bound on the regret for new domains, expressed as a convex
combination of the best regrets in the source domains, plus a
concentration term that diminishes as the amount of source data
increases.  While our primary contributions are theoretical and
algorithmic, we also present empirical results demonstrating the
effectiveness of our approach.

Principled Model Routing for Unknown Mixtures of Source Domains
Christoph Dann Google Research
Yishay Mansour Google Research Tel Aviv University
Teodor V. Marinov Google Research
Mehryar Mohri Google Research Courant Institute
Abstract
The rapid proliferation of Nomain-specialle machine learning models presents a challenge: while individual models excel in specific domains, their performance varies significantly across diverse applications. This makes selecting the optimal model when faced with an unknown mixture of tasks, especially with limited or no data to estimate the mixture, a difficult problem. We address this challenge by formulating it as multiple-source domain adaptation (MSA) problem. We introduce a novel, scalable algorithm that effectively routes each input to the best-suited model from pool of available models. Our approach provides strong performance guarantee: remarkably. for any mixture domain, the accuracy achieved by the best source model is maintained. This guarantee is established through theoretical bound on the regret for new domains, expressed as a convex combination of the best regrets in the source domains, plus concentration term that diminishes as the amount of source data increases. While our primary contributions theoretical and algorithmic, we also present empirical results demonstrating the effectiveness of our approach.
Introduction
Fine-tuning is key step in adapting large language models (LLMs) specialized tasks domains after their general pre-training. In this process, an LLM trained on vast datasets further trained on smaller, task-specific datasets. As organizations and researchers fine-tune LLMs for tasks like summarization, translation, or customer service, the result is a growing collection of models, each optimized for different tasks.
Routing algorithms are crucial for efficiently managing this diversity of specialized models, by determining which existing model best fits given input. Recently, various routing algorithms have been proposed [Chen et al., 2023; Wang et al., 2023; Hu et al., 2024; Madaan et al., 2023; Yue et al., 2023; Lee et al., 2023; Shnitzer et al., 2023; Narayanan Hari and Thomson, 2023; Lu et al., 2023], including some with strong theoretical and empirical guarantees [Mao et al., 2023, 2024a,b). While these routing solutions distributions, they offer no guarantees for inputs originating from an unknown mixture of domain distributions. Building fine-tuned model for every possible task combination is impractical, so how can routing be designed to handle such mixed-task inputs?
perform well when inputs are drawn from clearly defined task
To address this problem, this paper frames model routing multiple-souree domain adaptation (MSA) problem [Mansour et al., 2008] and derives a principled solution for enhancing robustness and adaptability across diverse and dynamic task distributions. Our approach grounded in strong MSA theory [Mansour et al., 2008, 2012; Hoffman et al., 2021: Cortes et al., 2021c] ensures that our routing model system performs well as the best individual expert model across any task mixture. While our contributions are primarily theoretical and algorithmic, we also provide empirical evidence demonstrating the effectiveness of our methods. Our solution is easily implemented and compatible
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

with existing router training approaches. It enhances existing router training by strategically adjusting task domain weights.
A detailed survey of related work is provided in Appendix A. Here, we briefly emphasize that our setting differs significantly from routing in Mixture-of-Experts (MoE) architectures [Shazeer et al., 2017], where experts are trainable components within unified network. In contrast, our work focuses on predictive model routing [Shnitzer et al., 2023; Narayanan Hari and Thomson, 2023; Lu et al., 2023; Mao et al., 2023, 2024a,b,c, 2025], where the router selects among fixed set of independently trained models. The central challenge we tackle is making accurate routing decisions when the target distribution is unknown and assumed to be arbitrary mixture over source domains.
Our analysis builds on the multiple-source adaptation (MSA) framework, first studied theoretically by Mansour et al. [2008, 2012], with subsequent algorithmic and theoretical advances by Hoffman et al. [2021] and Cortes et al. [2021c,a]. Our goal, however, is not to improve theoretical bounds for domain adaptation per se, nor to boost routing accuracy when the test-time distribution is known in advance. Instead, we offer a practical, theoretically grounded framework for robust model routing under unknown task mixtures.
The rest of this paper is organized as follows. In Section 2. we formally define the model routing problem under unknown target distributions and cast it in the MSA framework. Section introduces two algorithms along with their practical implementations, Section 4 presents theoretical analyses of our methods, including regret bounds under natural oracle assumptions. We prove regret bound for arbitrary target mixtures, showing that the regret a convex combination of the best somrce-domain regrets, plus data-dependent concentration term that vanishes with increasing source data. Finally, Section 5 reports our empirical results, demonstrating the benefits of our min-max optimization approach.
2
Problem Formulation
We begin by introducing the model routing problem and then show how it can be framed within the multiple-source adaptation (MSA) framework.
2.1 Model Routing
We consider finite set of generative models, denoted by II, where each model X A()) maps inputs X' to probability distributions over outputs V For example, if TI consists of generative language models, X' would represent prompts and y their corresponding generations. Additionally, we assume there are k benchmark tasks, DI..... Dr. where each D; is a distribution over inputs. Typically, access to D; is limited to finite dataset. We will denote by D; the empirical distribution consisting of n; i.i.d. samples drawn from D.. Let x x y - [0, 1] represent scoring function y for a given input
that evaluates the quality of a generation indicate the probability that human evaluators prefer y over the output of a reference model. Although r" may be unknown, we assume access to scoring oracle R that provides unbiased estimates of r* for any input-output pair (ar,) y). For simplicity, we assume that the scoring function r is uniform across all benchmark tasks, though this assumption can be relaxed. The value of a model n e 11 on an input æ or distribution over inputs D is defined as follows:
X. For example, r" could
((TTz))
[r" (x.,)] (-<(")
E
U( (T D) E [.(
z-D
Goal of predictive model routing. Given access to II, R, and the datasets D....., Dr. our goal is to select high-quality probabilistic routing function f:X' + (III from a family F of such functions. Each routing function maps an input & X' to a probability distribution over the models in II. For any input x, model ι Il is selected by sampling from the distribution f(x).
For any n: X' + ())) and (x. y) E Xxx), let T (g)æz) denote the probability of y under the distribution (xx). Given routing function f e F, we define the induced distribution π T (t(+)z) over outputs y as:
V( v) E X y, ग (
Σ (()l)))(v)x)) well
The objective is for f to route inputs x, drawn from an unknown test domain D A(Y), to models in II that yield high scores according the oracle R. Specifically, we aim to find an f that maximizes

---

the expected score e(Ty, D), without prior knowledge of D. The performance of routing function f is evaluated by the regret of its induced policy ς on the test domain D, defined as:
( D) == max o ( D) v DD)
(I)
mel
that is the gap between the performance of the best model in II and that of the model selected by f-
Why is the test domain unknown? The test distribution D, representing the real-world data an application will encounter, typically unknown during development. We often know which kind of tasks model may be used for but how popular a specific task is, cannot be known ahead of deployment and may also change over time. We therefore focus on the problem where D is composed of a mixture of the benchmark tasks Di...., D& but the weights of this mixture are unknown at training time of the routing function. We formalize this in the next section.
2.2 Predictive Model Routing as Multiple-Source Domain Adaptation
Multiple-souree domain adaptation (MSA) is a closely related problem that has been extensively studied, particularly in classification and regression problems [Mansour et al., 2008, 2012: Hoffman et al., 2021; Cortes et al., 2021c]. In MSA, the task involves multiple source domains, DI.... Dr. each associated with a near-optimal model h,,..., h4 [Mansour al., 2008]. The target domain, Dx. defined as X-mixture of the source domains, Dx 1/2 Σ D, where é A([+]) represents unknown mixture weights. The objective is to devise a combination rule for the models h; such that the resulting model performs well on any target domain x),
We can formulate the predictive model routing problem as multiple-source domain adaptation task by first selecting an appropriate model, Ty. for each dataset, which we refer to as the expert model for domain Dr. In many applications, natural choices for т; arise, such as when a model π has been fine-tuned to perform well on a specific domain D;. More generally, we can define म; as the model in the set II that achieves the highest value estimate for D, Next, we augment the empirical distributions D Dx with score samples from each expert model. For each input æ in the support of D., we compute scores Fi....,77 T.k by generating responses 3, ~ TT (+2z) from each expert тт and querying the reward oracle, which returns scores r- ~ RR( w,). These scores, T'y, serve as unbiased estimates of the value 2x). We denote the augmented version of D, as D..
With the score-augnen -urgentddd distributions (D:) in hand, the objective is find a routing function (or combination rule) f:X' A[[+]) that maps inputs to distribution over expert models. This routing function induces mixed generation policy y (u/ar) = Σt [ilarr)= m (ylær) which is evaluated based on its performance across any target domain Dx The quality of the routing function f is measured by its regret relative the full policy set II, as defined in (I). For the remainder of the paper, we adopt this domain adaptation perspective on predictive model routing, assuming that we are provided with score-augmented empirical distribution D, for each domain D, and that the goal is to learn an effective routing function to the expert models.
3 Algorithm
To ensure robustness in model routing across test domains, we draw on two key areas of research: multiple-source domain adaptation [Mansour et al., 2008; Cortes et al., 2021c] and minimax-regret optimization [Alaiz-Rodriguez et al., 2007; Rigter et al., 2021; Mohri et al., 2019; Agarwal and Zhang, 2022]. Our approach is particularly aligned with the approaches of Cortes et al. [2021c], Mohri et al. [2019] and Agarwal and Zhang [2022]. Specifically, we adopt the mixture over test domains and the associated theoretical guarantees from [Cortes et al., 2021c], while the objective formulation and optimization strategy are inspired by [Mohri et al., 2019; Agarwal and Zhang, 2022].
To design our algorithm, we begin by considering the idealized infinite-dati setting and then introduce maite-sample approximations, Rather than minimizing regret under a fixed distribution, as defined in (I), we adopt a more robust objective inspired by the minimax regret optimization literature [Alaiz-Rodrgee Rodriguzz et al., 2007; Rigter et al., 2021; Mohri et al., 2019; Agarwal and Zhang, 2022]. Specifically, we aim to minimize the worst-cuse regret over all possible test domains:
min max maxu( D2) u(T D2)-
(2)
feF XeA([]] s'ell
3

---

However, solving this optimization problem during training is challenging due to the maximization over x' E IT. To address this challenge, we propose two practical variants that avoid optimization over N.. Each variant minimizes regret relative to a specific policy, denoted as T or T
Option A: Pointwise Comparator: In this first variant, we aim to compete against a policy TAA that, for each input context z, achieves the performance of the best expert model. Formally, (TT),) [aX (TT,20) 2:) for all x. This leads to the following objective:
min max Ca(f.0) == min max 2( ((T ((T JeF (AA(
(3)
fef (())
In the finite-sample setting, this min-max objective becomes:
A Σ ri E-
min max Ex(1,0)= == min max Per (AA(
E E
maxT, [4[R]
jEP ((((
where the maximum is taken over expert scores for each sample. While being easy implement, this approach introduces additional bias when there is high variance in the expert scores for given input.
leverage the structure of the model routing problem by using TB as the comparator in the regret calculation. This policy, Tg:A x [k] - A()). takes both the imput x and the domain label i, following the expert model x; for samples from domain Dj that is, TB (x, = (z). As we will demonstrate later, this fixed comparator provides strong regret guarantees without requiring additional inner optimization over policies. This leads to the following optimization objective:
Option B: Domain Comparator. To limit bias in the finite-sample objective,
min max Ln(s,d)= min max o( Dx) u(Ts, D2)
(5)
JEF ((A)
fef (eA([s)
with the sample counterpart:
min max ΣB(S,0) == min max JeF (E(((A])
E
Pt S(1x))
(6)
JEF (eA((R])
(F.F1omnn))-, )-D,
Note that TA and TB coincide when domain experts perfect, producing the best score for each individual x from their respective domain. However, in practice, even गy that are well-tuned for their domain D; typically do not achieve this, which distinguishes T from z in general.
Algorithm. We follow the standard approach and tackle the saddle-point problems in Equation 4 or as two-player game, which can be solved by dueling two no-regret learners (see Mohri et al. [2019] for a general Mirror descent solution). Our algorithm is shown in Algorithm The max-player can be solved efficiently with Hedge [Littlestone and Warmuth, 1994]. For the min-player, we do not prescribe the exact update for J+ as we not wish to prescribe specific function class F. Instead, we follow prior work [e.g. Cheng et al., 2022] and rely on online learning oracles. When the update aims to optimize (4) or (6) directly, which are linear losses in the predictions of ft. then we refer to this as OLO oracle. Alternatively, it is common in practice to frame such an objective classification problem and instead aim to minimize the weighted log-loss as proxy instead. We also support such choice for updates and refer to it oracle rigorously in the next section, but we generally assume that the oracle of choice is a no-regret learner and note that there is large family of online meline-learning algorithms available with appropriate guarantees [Cesa- BesscBBi and Lugosi, 2006).
weighted
OLLO oracle. We formalize the notion of
Practical Implementation. Algorithm I can be seamlessly integrated into existing model training frameworks. For instance, in the case of language model routing, the class F can be a moderate-sine sized language model architecture, where the initial policy fi is pre-trained model with its final layer replaced by a randomly initialized linear layer. At each round t E [T']. a batch of samples is drawn from the augmented datasets, with equal proportions from each. The Hedge update of domain weights A can be efficiently computed in closed form with minimal computational cost.
The update of f: is handled using standard gradient- maadient-based optimizers on the objectives in (4) or (6). augmented with a Kllrreularizzatin, similar to RLHF training objectives [Christiano et al., 2017], such as regularization toward uniform domain distribution or a given domain prior. This corresponds to an OLO oracle. Alternatively, the model can be optimized with a proxy log-loss, similar to standard supervised fine-tuning objectives and corresponding an OLLO oracle.

---

Algorithm 1: Domain adaptation for model routing algorithm
Input: Score-augmented distributions D; for e [k]] of size n,, Each sample is of the form
(C,,Pi...,,P,, where is the context and rj is reward estimate for expert policy xys 2 Output: Routing policy f:X + A&:
Initialize A1 = ...... 1 and fi in F arbitrarily;
4 for t == 2, T do
Sample (12 (1) (1) (.ke Dj for each i [k]
Determine benchmark with option A y1 &argmaxxex Tig or option y/
Set benchmark score ((() =)())))))
C.)
Max-player: Hedge
Update A X exp(-76) with losses & IR* where b,t = 4 - En-1 to sclloo)
10
Min-player: no-regret online learning update
Update ft-1 with OLO for all i [k] contexts x, and losses (()) R with
11
2 Xt,s (c(
rt.j
(t)
or OLLO for all i [k] contexts 2. and targets ye (0) with weight Ar,
12
return f= Et=I /
13
Finally, Algorithm 1 returns an averaged model f, where f(i]z) = ΣL, f((z)) for all x e X' and i [k]. While exact output averaging might not always be feasible, we can adopt "model souping" approach by averaging the parameters O, of the models ft across iterations. The final model is then represented by 1 Σt lr. technique that has proven effective practice [Wortsman et al., 2022; Ramé et al., 2024].
4 Theoretical Analysis
Before formally stating our results, first introduce the oracle assumptions.
4.1
Oracles
The first oracle we support no-regret learner directly on the losses linear f:
Definition (Online learning oracle). An algorithm OLO is referred to online learning oracle for a class FF S X As if it xatisfies the following condition. Given an arbitrary, potentially adversarial sequence of context-loss pairs (51,,1,...,JAA (KT)) OLO observes the context-loss pairs sequentially and maintains a sequence of policies ft+1 F, updating the policy after observing k contexts Tht....IIttk. and losses Ckt....,
CR The regret of OLO is given by:
Tk- Reg (L)(()) -axx (f - (aan)))-(((KKt.. fe(Dstti), Casrs)
JEF
and is sublinear Reg OLO (T) o()) with probability at least 1-
We expect that standard gradeent-based optimizers on the objectives in (4) or (6), augmented with appropriate entropy regularization, are no-regret learners that satisfy this definition at least approxi- mately. Note that our definition of online learning oracle deviates slightly from the standard no-regret definition because it uses batched updates where fe is only updated after predictions. This is a minor difference and algorithms that satisfy the standard definition also satisfy our definition above with regret increased by a factor of at most
For the alternate updates of fe with OLLO, we view the problem as a classification problem with weighted datapoints and prescribe that the updates lead to small log-loss (or cross-entropy loss), formalized as:
Definition (Online log-loss oracle), algorithm OLLO is referred to as an online log-loss orucle for class F X Ab if it satisfies the following condition. Given arbitrary, potentially
5

---

Oracle
Option
Main term
Assumptions
best expert r deterministic & F con-
OLO
A
re Dx)
tains perfect predictor for best score
Di....y Dj
OLO
A
reg(*", D.) + biasA +0(V +O(1 m/mmm))
J contains perfect predictor best ex-
pected score on Di...., Dy F contains f,5 for every A Åe
OLO
B
Σis1 reg( D.)
OLO
B
Σls A reg T.. D.) O(v 1/Mmin)
F contains fx. for every A As
OLLO
&&B
min max4ely P.W.D D, (og(f(1())))))
second moment of logits bounded for all f
Table 1: Summary Guarantees. Amin = min n, denotes the size of the smallest dataset.
adversarial sequence of context-weight-targe triples (I1, w1: "1,...,, TKT, WKT, & OLLO observes the triples sequentially and maintains sequence of policies fi+1 6 F,, updating the policy after observing k contexts Lkts Iktsk-1, weights Wkts Wkttk-1 and targets ykts Vkt-k-1- The regret of OLO given by:
k-1
Reg
OLLO (T) = max
Σ
Wki- log
feF
1=1
1-0
f(ykers(
and is sublinear Reg,
OLOO (T) = ((T) with prob. 2 1
4.2 Guarantees
We begin by building intuition for the terms that will appear in our final eπror bounds. Since do not have access to the underlying domains D; directly, but only through datasets of finite size, we should expect to pay for finite-sample error for this approximation. For test domain Dx. this appears in our bounds as a concentration term of the form
Conc(A, =0 o
k X llgg(
(FF
A log Cc
Σ
max
n1
72,
where Cy is an appropriate complexity measure for e.g. the loo covering number of F. The error term Conc(>, n) decreases as the sizes of the datasets n, increase, Fortunately, À here the mixture weights of the test domain and thus, the dominating first term that shrinks slowest with n. only depends on the dataset size of source domain that build the support of Dx-
Another source of error in Algorithm is that it aims to find solutions to (6) or (4) in an iterative fashion and if the number of iterations small, we incur additional approximation errors. This yields eгror terms of the form
Approx(T) Reg of
o
log (8)
T
OLO (T) or Reg OLLO (T), depending on the oracle choice. This term includes the eиrоr due to updates of fü (hence the Reg, (T) dependency). error due to updating X (regret of Hedge) and uniform concentration errors due to sampling datapoints for updates from the dataset in each iteration. As long as the chosen oracle work and Reg o(T). this Approx(T') term will shrink with T and we can make it as close to zero we like by running Algorithm for enough iterations. Note that increasing the number of iterations T only incurs a computational overhead but does not require more data.
where (T) is either Reg
We can now state our main result when fr-updates are performed by an OLO oracle. We discuss here the results for OLO oracles and defer those for OLLO oracles to the appendix (see Table 1).
Theorem 1.
Let Dx be the test domain, F be a convex set and updated to ft performed by an OLO oracle. Then, with probability at least 1 O()), the regret of the function f returned by Algorithm I with Option A satisfies
reg(Tj, Dx) S Sreg(TA, Dx)+ Ví Approx(T)) Cono(A,

---

where A is the competitor policy for option A and VA maxxeds inf fer I(S,) is the optimal value of the objective in Equation 4. The same guarantee holds for Option B with TA replaced by "i and V by Vg.
In addition to the two enror terms Approx(T) and Cone(A, n) discussed above, our performance guarantee contains the main reg(# Dx) Vi Since the game in (5) and (3) are designed to make f match the performance of the chosen competitor T or я B. the regret of this competitor naturally appears in the our error bound. The V term is the value of the game / saddle-poin and small long as the function class F is expressive enough. How expressive IF needs to be depends on the chosen option.
Option B. Building the analysis of Mansour et al. [2008], we show in Lemma in the appendix that the value Vg is non-positive, as long as I can represent the conditional probabilities of datapoint coming from each source dataset given its context x which, by Bayes rule, is
X,D)(x)
(x,D( ΣØ-1 Dx))
Further note that due the specific definition of Tj its regret can be bounded by the regret of each domain expert on its own domain
reg T B. Qx) max
v(T' (T'' DA)
A D.) Σ Aerg(a D:).
s'ell
F=1
This yields the following corollary of Theorem 1:
Corollary 1. Assume F to be a convex set and assume F contains fx, for every X d Dr. Let Dx be the test domain. Then, with probability at least - O6)) the regret (T Dx) of J returned by Algorithm I with OLO oracle and Option B is bounded by
Σ A Aege(T, (T, D,) Approx(T) + Conc(A,
This recovers the canonical results from prior domain adaptation works, and shows that long as the experts are optimal on their domain, the produced routed model will be optimal on any test domain Dx as well, up to the error terms which decrease with and n.
We expect that for many modern neural network architectures, the condition that F can represent fx,5 to hold. However, this condition does depend on the (randomly drawn) datasets D, To obtain a condition that does not depend on the realized datasets, we can instead just assume that the condition holds for the true source domains D,. However, we incur an additional O(/k/ min; n:) error term in this case. See Table for summary and the appendix for details.
Further, we expect the algorithm performance to degrade gracefully when the realizability assumption in Corollary 1 does not hold exactly and that the bound could be extended to reflect this through an additional additive approximation error scaling with min max;[[K]] E E.. D. [1f(1 - fx. (1))()
Computational efficiency at inference time We note that when deploying the router f returned by Algorithm 1 there is no need to call all of the domain experts x, Instead, given a context, we sample i /((la:) and only play according to nH (-(rr) This modification inherits the regret guarantees of Theorem as the sampled follows exactly the same distribution as that of y T (-|x) and so
the values of the two sampling procedures are exactly the same. Figure we show an experiment which shows the regret with respect to the above sampling for Option A with log-loss. We also include comparison in Table 2.
Option A. To show that V is small, we need stronger assumptions compared to Option B. In order for Di to be zero, there must be f F that can match the performance of 7 which always takes the best expert for given sample. This f needs to satisfy
maxi;
Σ f())))rm Vi. m=1
(7)

---

regret vs best expert
regret domain expert
Loss for f
Option
Baseline
Alg
Baseline
Alg
linear
A
4.60
4.28
1.65
0.49
linear
B
4.60
7.09
1.64
1.08
log
A
2.70
2.37
-0.06
-0.39
log (sampled)
A
2.70
1.90
-0,06
-0.85
log
B
7.90
7.84
0.58
0.23
Table 2: Overview of regret in the worst-case test domain (lower is better), comparing the routing function produced by Algorithm against a routing function produced by training with uniform and fixed domain weights. Results averages across 5 seeds. Algorithm consistently reduces the regret against the competitor targeted by the selected option.
If there is significant stochasticity in the rewards r; generated by an expert for a given J, then this condition might be impossible to satisfy. Specifically, if there are multiple samples with the same but where optimal score obtained by different experts with distinct scores, then no such mapping can exist. However, sufficient condition for such an f to exist is that for every x there is some expert which with probability always has the highest score among all experts. In this case, the finite-sample approximation in (4) is an unbiased estimator of (3). If, in addition this f is contained in F, then we can show that V = and the regret bound for f becomes
reg( n Dx) s reg( Dx) + Approx(T) + Conc(A,
In general, if there are contexts for which the distributions of scores between experts overlap and the identity of the best expert varies with the random draws of generations and score assignment, then
(4) incurs bias and we can still show Vi bias +O (10)(C=/6) where we incur an additional
/min,
1/ V/miin n; term and the bias
bias max E E
mmxx mm] max v (Tm 2)
D-
This term essentially quantifies the bias from estimating the maximum expected score by taking the maximum over realizations, thus exchanging the expectation and maximum in the expression. There are many scenarios where bias is favorably small. For example, we can show that for any æ
E [maxrm FERL=
-max v (Tmm x)) s max
m
m
holds where of is the variance of and thus when all scores near-deterministic bias a is small. Another favorable case when for every x there is some model that always the best, which case A O.
Option A Option B. By construction, T'A a stronger competitor than T since the inequality "( xx) S max+{[K] u(T,,a)) = u( ar) holds for all x X. Thus, in the most favorable cases when V 0, Option
indeed preferable as reg( (A Dx)= Σt_, X reg( Dz). However, as we alluded to earlier, the conditions for Vi 0 are much stronger than those required for Vg. Thus, in many practical settings, Option might be preferable to Option A.
5 Empirical Evaluation
Our primary contributions are thcoretical and algorithmic, but we now also validate the effectiveness of our approach empirically. Prior studies have explored optimal strategies for learning routing function tailored to specific data distributions [c.g. Jiang et al., 2023; Hu et al., 2024]. We view our algorithm as framework that can be applied top of these approaches, by using them for updating ft- Thus, we do not aim to compare different learning methodologies but to assess the given oracle choice, and how it makes the routing function
oracle
impact of applying our framework more robust by adjusting the domains weights in training. We therefore compare Algorithm with and without updates A (i.e., 7 0 7 0), while keeping other parameters fixed.
As oracles, we use stochastic gradient based updates on either the linear objective in (6) or (4) directly on a log-loss proxy, described in Definition 2. The routing function f is initialized as

---

Regnet against domain expert
Regret against best expert
weights
1.00
domain
Demain
Domain
Domain
0.25
Domain 4
0.00
1.00
0.75
2000
4000
8000
100000
2000
6000
8000
10000
4000
6000
10.000
stop
stop
Stop
Figure I: Comparison of Algorithm I with Option B (bottom row) versus the baseline without domain weight adjustment (top row), evaluated using log-loss under an OLLO oracle. The left panel shows the regret against each expert, the middle one the regret against the best per example expert.
domain
Regret against best
Domain weights
1.00
domalh
0.75
Damain
Domain 1
2.5
0.30
Domain
Domain
5.0
1.00
0.75
0.0
-2.5
0.50
0.00
0
2000
4000
5000
8000
10000
0
2000
4000
6000
5000
10000
2000
4000
6000
8000
10000
step
stop
stop
Figure 2: Comparison of Algorithm with Option (bottom) where rewards are sampled according to the computationally efficient inference procedure against Algorithm I with Option A without sampling (top), corresponding to an OLLO oracle.
pre-trained Gemma 2B model [Team et al., 2024], with the final layer replaced by fully connected, randomly initialized linear layer to produce the logits of f. When we use Algorithm with Option A, we use learning rate 1e 4 and with Option B learning rate y = 1e 3 to update the domain weights. We choose different learning rates as the magnitude of regret for the max-player different due the the different comparator in the regret. We train each routing function for 10,000 batches of 256 samples from each domain. Each experiment repeated 5 times where the datasets are shuffled between instances of the same experiment.
We conduct our evaluation on the MixInstruct benchmark by Jiang et [2023] which consists of 5 individual domains. Each domain D, contains samples with prompts and various metrics for the generations of 11 open-source LLMs. We focus exclusively on the BLEU score and select the model with the highest average BLEU score per domain from the training split serve as the domain expert.
Table 2 shows a summary of our empirical results, listing for each choice of oracle (loss function linear log-loss) and algorithm option (A B) the average regret of our algorithm per step against the baseline which does not update domain weights during training on the the worst-case domain mixture. Algorithm 1 reduces in all cases the regret targeted by the chosen option, regret against best expert for Option A and regret against domain expert for Option B. While this typically results in reduction of the other notion of regret, an increase may happen (e.g., for linear loss and Option
B). The regret computed with respect to Ty, that is with respect to E fe(l yr except for (t) log (sampl ed), where we sample j fe(()az(")) and play the corresponding "i Overall, the table shows that the efficient inference strategy performs on par with, or better than, computing regret using the full distribution fo(- (z)))

---

Figure shows the regret of the routing model each domain during training, for the example of log-loss and Option B. We show both the regret against each of the domain experts in the first column and the regret against the best per example expert in the second column. The baseline experiment is in the top row and Algorithm with Option B and OLLO is in the bottom row. As expected from the min-max game formulation we see that the regrets against each of the domain experts across domains are being equalized by Algorithm 1. This leads to a decreased regret on Domain 4, compared to the baseline, regret which matches that of the baseline on domains 1 and 3, and a slightly increased regret for Domain 4 and Domain O. This is in accordance with how the domain weights, A é As. change over the course of the game, that is high regret on Domain 4 is penalized more compared to the baseline uniform distribution and the regret of Domain 0 and Domain 2 is penalized less. The second column of Figure shows that, for the harder objective of competing against the per-example best, Algorithm 1 decreases the regret of Domain 4 while maintaining performance on the others. Figure 2 compares the efficient inference strategy with against using the full distribution defined by ft on our best performing setting for Algorithm I. As expected, the sampling strategy performs similarly both with respect to the regret and domain weight behavior.
In Appendix D we present results for the remaining 3 settings of Algorithm I with Option A and Option with OLO oracle and with Option A with OLLO oracle. Overall we find the results to be consistent with our observations for Figure 1 and that there is always a benefit to using the min-max max optimization approach compared to the uniform weights of the baseline.
6
Conclusion
We presented a novel approach for combining multiple domain expert algorithms through the use of online learning oracles, achieving regret bounds that are tightly linked to the performance of these oracles. Our method offers strong theoretical guarantees, ensuring robustness across broad range of scenarios, including settings with unknown mixtures of source domains. Empirically, we validated the effectiveness of our model routing strategy on the MixInstruct dataset, demonstrating its practical advantages real-world tasks. These results underscore the promise of our approach as a principled and scalable solution for predictive model selection in heterogeneous environments. Appendix B briefly discusses further extensions of our results.
References
A. Agarwal and T. Zhang. Minimax regret optimization for robust machine learning under distribution shift. In Conference on Learning Theory, pages 2704-2729. PMLR, 2022.
R. Alaiz-Ree MoizigRod A. Guerreto-Curieses, and J. Cid-Suciro. Minimax regret classifier for imprecise class distributions. Journal of Machine Learning Research, 8:10--130, 2007.
N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
L. Chen, M. Zaharia, and Zou. Frugalgpt: How use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.051 2023.
C.-A. Cheng, T. Xie, N. Jiang, and A. Agarwal. Adversarially trained actor critic for offline reinforcement learning. In International Conference on Machine Learning, pages 3852-3878. PMLR, 2022.
P. F. Christiano, J. Leike, T. Brown, M. Martic, S. Legg, and D. Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
C. Cortes, M. Mohri, D. Storcheus, and A. T. Suresh. Boosting with multiple sources. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, edi- tors, Advances Neural Information Processing Systems 34: Annual Conference on Neu- rat Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 17373-17387, 2021a. URL htwps:tttts.oc. htt.httts///prroeeeeeee in ngs neurips cttccc///p//. cccppppp///2// Abstract html.
10

---

C. Cortes, M. Mohri, and A. T. Suresh. Relative deviation margin bounds. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 2122-2131. PMLR, 2021b.
C. Cortes, M. Mohri, A. T. Suresh, and N. Zhang. A discriminative technique for multiple-source adaptation. In International Conference on Machine Learning, pages 2132-2143, PMLR, 2021c.
G. DeSalvo, M. Mohri, and U. Syed. Learning with deep cascades. In Algorithmic Learning Theory: 26th International Conference, ALT 2015, Banff. AB, Canada, October 4-6, 2015, Proceedings 26, pages 254 269. Springer, 2015.
D. J. Foster, S. Kale, H. Luo, M. Mohri, and K. Sridharan. Logistic regression: The importance of being improper. In Conference on learning theory, pages 167-208. PMLR, 2018.
E. Hazan, T. Koren, and K. Y. Levy. Logistic regression: Tight bounds for stochastic and online optimization. In Conference Learning Theory, pages 197-209. PMLR, 2014.
J. Hoffman, M. Mohri, and N. Zhang. Multiple-source adaptation theory and algorithms. Ann, Math. Artif. Intell., 893-4))237-277, 2021.
Q. Hu, Bieker, X. Li, N. Jiang, B. Keigwin, G. Ranganath, K. Keutzer, and S. K. Upadhyay. Routerbench: A benchmark for multi-llm routing system. arXiv preprint arXiv:2403. /2031, 2024.
D. Jiang. X. Ren, and B. Y. Lin. Lim-blender: Ensembling large language models with pairwise ranking and generative fusion. arXiv preprint arXiv:2306.0256/ 2023.
S. M. Kakade and A. Ng. Online bounds for bayesian algorithms. Advances in neural information processing systems, 17, 2004.
C.-H. Lee, H. Cheng, and M. Ostendorf. Orchestrallm: Efficient orchestration of language models for dialogue state tracking. arXiv preprint arXiv:2311.09758. 2023.
N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-261, 1994.
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. arXiv preprint arXiv:2311 1..062231.00869,, 2023.
A. Madaan, P. Aggarwal, A. Anand, S. P. Potharaju, S. Mishra, P. Zhou, A. Gupta, D. Rajagopal, K. Kappaganthu, Y. Yang. et al. Automix: Automatically mixing language models. arXiv preprint arXiv:2310.12963 2023.
Y. Mansour, M. Mohri, and A. Rostamizadeh. Domain adaptation with multiple sources. Advances in neural information processing systems, 21, 2008
Y. Mansour, M. Mohri, and A. Rostamizadeh. Multiple source adaptation and the rényi divergence. /wt.. arXiv:/205.200 2012.
arXiv preprint arXiv:
A. Mao, C. Mohri, M. Mohri, and Y. Zhong. Two-stage learning to defer with multiple experts. In Oh, T. Naumann, Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems 36: Anmual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
A. Mao. M. Mohri, and Y. Zhong. Principled approaches for learning defer with multiple experts. In R. P. Barneva, V. E. Brimkov, C. Gentile, and A. Pacchiano, editors, Artificial Intelligence and Image Analysis 18th International Symposium on Artificial Intelligence and Mathematics, ISAIM 2024, and 22nd International Workshop Combinatorial Image Analysis. IWCIA 2024, Fort Lauderdale, FI, USA, January 8-10, 2024, Revised Selected Pupers, volume 14494 of Lecture Notes in Computer Science, pages 107-135. Springer, 2024a.

---

A. Mao, M. Mohri, and Y. Zhong. Regression with multi-expert deferral. In Forty-first International Conference on Machine Learning, 2024, Vienna, Austria, July 21-27, 2024, OpenReview.net, 2024b.
A. Mao, M. Mohri, and Y. Zhong. Realizable h-consistent and bayes-consistent loss functions for learning defer. In A. Globersons, I.. Mackey, D. Belgrave, A. Fan, U. Paquet, J. M. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024c.
A. Mao, M. Mohri, and Y. Zhong. Mastering multiple-expert routing: Realizable H-consistency and strong guarantees for learning to defer. In G. Kamath and P. Loh, editors, 42nd International Conference on Machine Learning (ICML 2025), Proceedings of ICML 2025, 2025.
H. B. McMahan and M. Streeter. Open problem: Better bounds for online logistic regression. In Conference Learning Theory, pages 44- 1. JMLR Workshop and Conference Proceedings, 2012.
M. Mohri, G. Sivek, and A. T. Suresh. Agnostic federated learning. In K. Chaudhuri and R. Salakhut- dinov, editors, Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 4615-4625, PMLR, 2019.
S. Narayanan Hari and M. Thomson. Tryage: Real-time, intelligent routing of user prompts to large language models. arXiv e-prints, pages arXiv-2309 2023.
A. Ramé, J. Ferret, N. Vieillard, R. Dadashi, L. Hussenot, P.-L. Cedoz, P. G. Sessa, S. Girgin, A. Douillard, and O. Bachem. Warp: On the benefits of weight averaged rewarded policies. arXiv preprint 24X.::24066166666 2024.
M. Rigter, B. Lacerda, and N. Hawes. Minimax regret optimisation for robust planning in uncertain markov decision processes, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35 (13), pages 11930-1 1938, 2021.
G. I. Shamir. Logistic regression regret: What's the catch? In Conference on Learning Theory, pages 3296-3319, PMLR, 2020.
N. Shazeer, Mirhoseini, K. Maziarz, A. Davis, Q. V. Le, G. E. Hinton, and J. Dean. Outrageously large neural networks: The sparsely-gated mixture-of-expprts layer. In 5th International Confer- ence on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Truck Proceedingy. OpenReview.net, 2017.
T. Shmitzer, A. Ou, M. Silva, Soule, Y. Sun, Solomon, N. Thompson, and M. Yurochkin. Large language model routing with benchmark datasets. arXiv preprint arXiv: 15789, 2023.
G. Team, Mesnard, C. Hardin, R. Dadashi, S. Bhupatiraju, S. Pathak, L. Sifre, M. Rivière, M. Kale, J. Love, et al. Gemma: Open models based on gemini research and technology. arXiv preprint arXiv:2403.080 08295, 2024.
Y. Wang, K. Chen, H. Tan, and K. Guo. Tabi: An efficient multi-level inference system for large language models. In Proceedings of the Eighteenth European Conference on Computer Systems, pages 233-248, 2023.
M. Wortsman, G. Ilharco, S. Y. Gadre, Roelofs, R. Gontijo-Lopes, A. S. Morcos, H. Namkoong, A. Farhadi, Y. Carmon, S. Kornblith, et al. Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time. In International conference on machine learning, pages 23965-2222 239988. PMLR, 2022.
L. Xiao. Dual averaging method for regularized stochastic learning and online optimization. Advances in Neural Information Processing Systems, 22, 2009.
M. Yue, J. Zhao, M. Zhang, L. Du, and Z. Yao. Large language model cascades with mixture of thoughts representations for cost-efficient reasoning. arXiv preprint arXiv:2310.03004 2023.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Answer: [Yes]
Justification: Algorithm is introduced in Section 3, the theoretical guarantees in Section 4 and the empirical results in Section 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss a thorough discussion of the quality of the theoretical bounds, i.e.. when each term is favorably small, and also discuss the assumptions required in Section We also acknowledge the limitations of the empirical comparison in Section 5, our primary contribution theoretical and algorithmic.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
All statements and full proofs included in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Details of the practical implementation of the algorithm provided at the end of Section 3 and the setup of our empirical evaluation is contained in Section 5 and Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification: We are unable to provide the source code but our experiments only rely on public models and datasets and we aimed to provide all details necessary to reproduce our results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https: /nipssips./....//// cc/
public/ guides CodeSubmt asionPolicy oollyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (ht (nttps: /nips.. cc/ cttps/ccccpplbaacccccceecc public/guidiii /wcp/uuisss.. Codee Submi ss ssionnoooo Lonooooooooo o olicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The setup of our empirical evaluation described in detail in Section 5 and Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report the number of independent trials of our evaluation (5) and figures contain error bands.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
We provide this information in Appendix D.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /nnuripisss.. cc http:rippp...ppppceettttttteeeae
Answer:
[Yes]
Justification:
The research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We do not anticipate societal impact of this work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. deploymen of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No models or data released with paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Original papers of the used model (Gemma) and dataset (MixInstruct) cited.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use package should be provided. For popular datasets, papersw rswi thoode. com / da sets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets are released.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Paper does involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Bthics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Paper does involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: Our methods can be applied to routing to LLMs but is not specific them. Our method development did not involve L.LMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy (https: : //npurips...p///// cc/ Con/efeeneeeccsccceeeeeeeeeceese / 2025/ LLM) for what should or should not described.
19

---

Contents of Appendix
Related Work
B Extensions to other settings
21
C Theoretical Analysis
21
C.1 Analysis for Option A
24
C.2 Analysis for Option B
25
C,3 Alternate Oracles
27
D Experiments
30
D.1 Experimental setup details
30
D.2 Additional results
30
Unbounded loss bound
30
20

---

A Related Work
Mixture-of-expere vs. model routing. The term model routing has been used in the literature to describe related but distinct problems, including token-level routing in Mixture-of- Mixture-of-Experts (MoE) architectures [Shazeer et al., 2017]. In MoEs, individual tokens are routed, each routing layer within a transformer network, to a small subset of expert modules, typically feed-forward networks. These routing layers are trained jointly with the experts, and key challenges include maintaining diversity and ensuring balanced utilization across experts, In contrast, the routing problem we consider in this paper involves assigning the entire input, rather than individual tokens, to one of several fixed (pre-trained) expert models, each specialized for a particular task. When we refer to model routing in this work, we mean this form of input-level assignment. this setting, load balancing and diversity are not primary concerns.
Model routing. Learning a routing function for a collection of fixed specialized models has been studied in the literature in several variations. We can categorize existing work based on the input of the routing function: In post-hoe routing [Chen al., 2023; Wang et al., 2023; Hu al., 2024; Madaan et al., 2023; Yue et al., 2023; Lee et al., 2023), the inputs are first processed by the experts and the routing function and selects the best output after seeing both the input and the output from each expert. A specific form of post-hoc routing, known as cascading routing, was studied by Chen et al. [2023]; Wang et al. [2023]: Yue al. [2023]; Hu et al. [2024], where inputs are processed sequentially by experts until a sufficiently high-quality response is obtained. Theoretical investigations of cascading ideas in classification have been conducted by DeSalvo et al. (2015]. Relatedly, Mao et al. [2023, 2024a,b] have introduced deferral algorithms, which can be used in particular for routing applications, together with an extensive theoretical guarantees. In predictive routing [Shnitzer et al., 2023; Narayanan Hari and Thomson, 2023; Lu et al., 2023] the router only gets to see the input and selects the expert, which alone processes it. Recent efforts by Hu et al. [2024] and Jiang et al. [2023] have proposed benchmarks for evaluating mixtures of LLMs. For more comprehensive review of this literature, we refer readers to Hu et al. [2024]. Our work focuses on the predictive routing setting, but our techniques can also be applied to other forms of model routing, such as post-hoc routing.
Multiple-souree domain adaptation. The multiple-source adaptation (MSA) problem was theoreti- cally studied by Mansour et al. [2008, 2012]. Later, Hoffman et al. [2021] introduced an efficient algorithm based on domain density estimation. This approach was subsequently improved by Cortes et al. [2021c], who replaced density estimation with domain classifier. However, despite this simplification, their method still requires solving a difference of convex (DC) programming problem, which may not be well-suited for modern LLM inference scenarios.
B Extensions to other settings
For the sake of exposition, we focus in this paper on predictive routing for generative models. However, our approach can be readily extended to other settings as well. For example, our algorithm can be used without modifications with discrimative base models æ, e.g. for classifying inputs æ. In that case Y' corresponds to class labels and policies output class probabilities. When we choose scores as binary indicator for correct classification, our regret guarantees below naturally provide a bound on the misclassification rate of the resulting classifier xy. Further, we can tackle post-hoc routing problems, where the decision which model to use is done after seeing the generations from the candidate models, by small modification of the framework above: Instead of routing functions f:X' - ([&)), we consider functions f:X'> x )* (((k)) that additionally receive the generations from all candidates as input. In practice this simply corresponds to appending the generations to the prompt v with appropriate divider tokens. Up to passing in this additional information to the routing models, our algorithm remains unaffected and the theoretical guarantees continue to hold.
C Theoretical Analysis
Our main performance guarantees for Algorithm with OLO stated in Theorem in the main paper are proven separately for each option Theorem and Theorem below. The guarantee with OLLO is proven in Theorem 4 afterwards in Appendix C.3
21

---

We first derive of useful results that apply to all variants. Recall the definitions of the objectives used by our algorithms as
CA(F,A) E
E A- Z-D;
max ((T: 20 v(TT.
(8)
5-f(2)
m
EA(1,A) = E
E
[maxrm rz]
(9)
Yー (a. L........DDDD,
j-f(w))
(B(f,A)= E
E
E
[t( -((T,,
(10)
i-d IDD,
j-f(x)
EB(f,))= = E i- (er
E
[r--rr]] ry]. f-f(w)
E
(11)
In the following, we refer by jointly to LA or LB and C to LA or LB respectively.
Lemma 1. The objectives CA, LB, LA.EB EB are bilinear in f and X. I = X A is convex, then
inf max (A(,.)) max inf LA(S.)) NEAL
(12)
dEdx feF
and analogously for LB, LA and LB.
Proof. We see directly from (8) that all objectives are linear in both arguments. The second part follows from Sion's 's minimax theorem, since both As and F are convex and A is compact.
The following lemma shows that the costs and rewards concentrate around their expectations.
Lemma 2. The following hold
T
P
sup (k)(k)
ΣΣ
X
c
(1)
-
-B[
Σ f10ll))) - 2 TVllog()//)
5
/=1
T
k X
P
sup JCF
(1)
Σ 20 E[
- -(r 2 (1o((()8888
88.
Proof. We start by showing the first inequality. First note that for every i [k]. (ep f(lla() (r - Dh is martingale difference sequence with respect to the filtration created by the online oracle. Azuma- Hoef--'oes''ing's inequality and a union bound implies that
B[c (
& 0 - E
Σ f:G1 -11--91----11111 E1--11) 2//Tlog(//6) 6.
sup Σ [=[A]
1-1
Next, we have
T
sup (k)
Σ A Σ
C
1=1
3-1
= sup Σ dE[k] 1=1
E[c (1) -
Σ E((1)(0)
(BI -11)
is linear in and the supremum will be achieved at one of the corners of the probability simplex.
since Σ X, 1
--
-
The second inequality holds in similar way by using Azuma- Hooff-noes inequality and union bound over F.
We note that the notation log((F)) is overloaded to mean the metric entropy for function classes which have infinite cardinality. For the rest the paper we consider log([Fl) to be the metric entropy with respect to the following distance d(f.f') sup [] f1
22

---

Lemma 3. Let Let ET-1 Se, Etz de be the average iterates Algorithm Then
- Reg (T) + +0 Ae
(V log (k(F1/8)
max
(13)
with high probability at least 1 1 0(), where Reg (T) is the regret of the online learning oracle from Definition I.
Proof. We begin by noting that
x(f.))=Bi = BEAA,,00-D
Σ Ai(c(0) - -(f.r(0 -((c(0((,r
ΣΣ A
E[c 1
Σ
T 1=12=
J=1
T &
k (0k(())
Z(J,)= = -A-
Σ - - (1,
ΣΣ f1
Xt,
[[c
j=1
Further, using Lemma 2, we can write that, with probability 1- 8 for all f e F and all é (k). the following holds:
-
1 T
T
Σ
X
E(c(o)
E[ce
ΣΣ
A
B[c("]] Σ /G1oo (1) [[r:3]]]
T
21
F=1
5=1
T
+ (0
log (A(FF1/116)
$
Σ
Σ
ΣΣ A1.
Σ (G
(1) )r
1=1
j=1
1 Σ E
f(x)) f(x(())) 0
(108(H)FF100
E
(A
Xe. (1)
f((2
T
T 1-1
T
Rega (T)
Reg,(1) +0
log(k[F118)
T
T
T
Since Rega (T) 0 (2
log (lgg(((F18) with probability least 1 - 0(8), the result follows.
Lemma Let V inf fer maxxes. C(f.N) be the optimal value of the saddle-point. Then Algorithm 1 converges that value with probability at least 1- O()), that is,
max E(f Regx((T)
-
log(k)/F111 T
T
This statement is true for either option and option B.
Proof. By Lemma 1, the following chain of inequalities holds
inf Σ(f,A) max inf Σ(f, V inf max Σ(f.)) s max E(F,)) A). Xcax
feF dedx fcF
feF Ar
Rearranging terms yields
E(J,)) V. max E(F A) inf ((f,5)
deda
fer
Reg, (T)
0 (V
log(k(F1/8)
S V.
(Lemma 3)
T
T
23

---

C.1
Analysis for Option A
Lemma (Concentration for option A). For a fixed X and J F, we have with probability at least
1-6
X? 118(
de log((188)
Ca(F.)) - -A
max
k X log( 1/8)
de lo10(1166)
EA(S,A) LA(S,A) So
Σ
Σ X bias (i)
74
14
where
bias (
ni Σ Thi 1-1
max u (Tm: (1(
E 1ina
max mm
Proof. Consider and ordering the samples in each augmented dataset and denote by (x) (t) (1)
(m the 1-th sample in D,. Further define
a
max ( (0)
E Tm..
maxx mm
nh
and
Y
max
Fm
max (1) t.m ((TT,,
Σ m-1
( (mlz)))
m
m
Then we can decompose the difference in losses
k A
CA(S,A) -A((,A) A (i)s
Σ
Y
T4e
Since YL, are all independent from each other, we can bound the second term using concentration arguments
$ A Σ Σ Vi, So
# Σ
log((110)
A log(1/0)
max
M4:
n
n2;
with probability least 1- O()). Note that we can bound the negative, - Σ/n Yi, analogously. Further, by Jensen's 's inequality, (i) 0 for all i. Combining these bounds yields the desired statement.
Theorem 2 (Regret bound for Option A). Assume that the function class F is convex. Then the solution returned by Algorithm with Option A satisfies with probability at least O(8)
Reg,(T) o (og(k(F1/8)
reg(Tj, D2) reg( D2) Vi
(14)
T
T
X (lg(())18)
X loogg( (FF6)
+ max
(15)
T4:
Further, if there exists an f E F which perfectly predicts the maximum score per sample, ie.. Eh ((a. [max rm] Σi- E B(a.rt....ra-- Ez- Fj then V s O. If this only holds on population level and for expected scores, i.e. Σ Ez-D, max, x( Σk= Br-D, (r), then we can still bound V $ max; bias (i)) O (og((F(/6)
//min,
24

---

Proof. We can decompose the regret of f on D2
reg(TT, D2) max r0 R, D2)
E
max ( mm: x)
max (mxx((Tm 0( D2)
x
x>Da
max v n. Dx)- well
E
max u mm 2t)
(A(fA))
m
< max u (T, Dx) sell
E
max U T.
+ ZA)(FA))
m
#
X log( (116)
A Aogg((FF10))
+
max
(Lemma 5)
n2
To obtain a bound on LA A), we apply the game-theoretic arguments from Lemma 4
Reg +o
(V
log (og((()11))
Ea(f,A)
T
T
and it only remains to control the optimal value of the game V
Vi max inf AEAp fer (1. j-f(x)
[maxx I' - ry]
m
k Σ
X (1F188))8))
A logg((1116)
VA + max A
A bias (1)
+ max
ni
log( log( (F18))
VÁ + max bias (1)) O
Vmnn; n2
C.2 Analysis for Option B
Lemma 6 (Concentration for option B). For a fixed and f F, we have with probability least 1-00 1-)
X
log(1/8)
A log(1/5)
- -
Σ
max
n1
and
log log(1/0) 1/5)
EB(F,A) S0
Proof. Consider a fixed X, f and i [k]. Order D, arbitrarily and denote (It, rr. re,k) the I-th datapoint in D,- Then Y,,, = [E - Fr.j] are i.i.d. random variables with mean D.). Since scores are bounded, Y,, centered to its mean is aub-Gaussian
E EY,, = v(T, D.) - and we can bound with probability at least 1 1-6 8
> EY EY, Y.d
-
1=1 n4
X log(1/8)
<0
log(1/0) max n2
X2 1og(1115
A log(1/8)
max
14
n2g
25

---

Lemma 7 (Value of the game for option B). Let VB inf value of the saddle-poine Assume that the function class F contains for every X E As where JA.D defined as f2(1))) D,())
jeF feF maxxes, LB(S:\) X) be the optimal
x=Di(z) Then the value of the game is non-positive, i.e., VB O.
Proof. Let A 4 be arbitrary and consider f(ilx))
A.Di(w) Σ5.1 AyDx(w)*
We then have
(B(f,)) (TTom, Qx) - UOT,
A
Σ
Dz(x) (z,
(z,
Σ (x())
Σ
A
Σ
(1,
Σ Σ (T) (2))
zed
(definition of f)
k Σ A Σ act
(T()) (z)))
1-1
0
(T (x,i) TT: (I()))
Theorem 3 (Regret bound for Option B). Assume that the function class F convex. Then the solution J returned by Algorithm with Option B satisfies with probability at least 1 - 0()) for any
fixed X
rog( Dx) Σ d rege((m n4 D:) V Regx(T) +0 log(k(FF118)
(V
(16)
X
A log
F
Σ F-1 n4
log
+ max The
(17)
8
Further, if the function class F contains Jx for every X E Ais where J2. is defined as [a(i)))= = x.).(z) (zD(()) then Vi O. this only holds on population level, i.e, F {S.D A As), then
can still bound Vi= 0
(log(1/8) min; ni
Proof. We can decompose the regret of on Da as
reg( (T. D2)= max v Dx) - u(m' Qx) u(=" Qx) -U(T,
well
max (( |, Dx) (x)) (b(f,A) xell
FF
$ maxu(T, Dx) `( (x) E
Σ 1-1
log
+ max
log
sell
n2g
(Lemma 6)
where the last inequality follows from a union bound over f é F and holds with probability at least 1 (6). The first two terms can be upper-bounde by the regret of each expert policy n; on its own dataset, weighted by X, i.c..
max (T,, Dx) u(T", QA) max xell
> (o(R, - D:)) s Σ X reg( D:).
We now bound ΣD(f,)) further by Lemma 4 with probability at least 1- (6)
Reg
+o log log(k) (1(F)
EB(F A) s Vi
T
T
Plugging both bounds in the previous decomposition yields the desired bound. For the bound on V apply Lemma 7 on D directly on D and apply Lemma 6 with union bound over Ak- D
26

---

C33
Alternate Oracles
In this section we consider replacing the linear losses, e, from Algorithm with a log-loss. Such choice is natural whenever consider F be some family of Transformer networks for which modern MI packages use optimizers tailored to the cross-entropy loss. The losses constructed by Algorithm are log-losses and which we defined in Definition 2 The problem of Online Logistic Regression has been extensively studied in the online learning literature [Kakade and Ng. 2004; Xiao, 2009; McMahan and Streeter, 2012; Hazan et al., 2014; Foster et al., 2018; Shamir, 2020]. Using OLLO we can instantiate a where new version of Algorithm with the following losses for the min-player e! = v.
need different version of the Online Learning Oracle
(1)
(1) =."). Option A and Option B then correspond to the following two choices of {j E [k]:r
2/ (i)
V/ (6)
argimx
Je[K] 1t
Option A Option B.
Next, we prove the counterpart to Lemma 4 for the classifier setting. Lemma 8. For any À ε A(k) it holds that
ΣΣ
Σ 2-1
Eliel
T
<min Σ1
Σ
a (og(s((1)) (x()))
(x(211(()) + Reg (LT)) + (lV/kloo((4411/0))
feF t=1 1=1
with probability 1 0()).
Proof. The definition of OLLO together with the standard analysis for the regret of the max-player imply the following holds with probability 1 (0))
Ar.
log(Si(vi
(1
log(S(>)
(1) (oo)))) Reg
OLLO (T)
T
Σ
As
c/
Σ EulON
=1=1
1=1
*
Σ
X
qt
EEGLEND s 0( (((/ETlog(()))1))
Σ
Elil
J=1
And so for any fixed A A(k) have
k 1
ΣΣ
\
F=
T &
No.
- Σ (1
+0(//TTog(A1110))
(1 (1- 1-(((v(") (00) ((V
(0)
T k
ΣΣΣ
log (o((s((V))
(1) (()) 0 (Tlooogg(((((
for any i, where the last inequality uses 1 x -og (z) x é [0. 1]. The min-player regret guarantee together with the fact that (1)
(. [00 1] imply
T ΣΣ ii
Σ (G
27

---

I k
( S min Σ Σ - log(/ (f((i, (11))
Reg (T) O(1 (oggk
fef Iel 2m1
We need the following assumption to be able guarantee concentration of the empirical log-loss the expected log-loss.
Assumption 1. We assume that E (D. [- log((((()) < +oo for f & (kk) and ( defined according option A option B.
This assumption is weaker than just assuming the log-loss is bounded which can be achieved by simply mixing of the uniform distribution with the predictors in F. Under Assumption we have the following corollary which follows from Theorem stated in Appendix E.
Corollary Suppose that Assumption I holds and fix an (0, 1). Then w.p. 6 holds that for all E
(o
(0--D (og
log (og(E( (-loo())
(i) 1:27: i [A]))/)]
$ O log(T))
E io
[- Lo
T
where No denotes the too covering number of the log-losses of F with respect sample from the empirical process induced by Algorithm 1 for 2T rounds.
The main result for OLLO found in Theorem below is very similar that for OLO. The terms Approx(T), Cone X, n) which depend on the oracle's regret and number of samples from the population still appear in the bound, however, reg(T'A A Dx) Vī is replaced by the log-loss of the best e F on the game: maX{{[K] E log( (o (1( (=())) This term depends both the max-player's actions throughout the empirical game, A, and the population through D;, i [A]]. The only difference between Option A and Option B is that g(()) argmax,, r" (y, ()) for Option and y( = i for Option B. Comparing Option vs. Option B similar to the comparison for the OLO. particular min 5. - (1)(0() is negligible under much stricter conditions for Option A, outlined for OLOs, compared Option B, where existence of accurate domain classifier in F is sufficient. Finally, because the log-loss is potentially unbounded we need boundedness of its second moment for all f F be able to show concentration of measure.
Theorem 4. Fix E E (0, 1). Under Assumption I with probability - 8 it holds that for any X A (k)
and f F
1 DE -(fr E -,
logg[ (2)
Reg (T)
OLLO (
+ o
log((110)
log(k/ kk/))
T
T
T
log( Ar/0)
log(T")
E
[- (o)
in (O.DD
k
X? (og(K(F(T10)
X (og(
max
where AT denotes the covering number from Corollary 2.
Proof. We begin by arguing that
Ers,, D, (c( -f,, (f)] s (-gg
Reg.
OLLO
OLLO
(T)
log log((F1/5)
log kk)))
+ +0
T
T
T
28

---

+ co(18((T)
log( A /0)
E a(
[- (o(((((())()))
T
This holds as follows. We combine the regret bound from Lemma together with the concentration of Lemma 2 and Corollary 2.
Finally, we convert the LHS of the above lemma to a concentration over the population Ei-A,--D,(c (f,r())] follows. First note that for any fixed f:F:
x n4
E - (f. (
-c
- (..
We can then argue as Lemma 2 that for all À E (k) uniformly it holds that
X log((k/0)
x log(k/0)
Σ 1=1
E 6 (f. (f.r,
(f.r) SO
max
n4
14
w.p. 1- 0()), where Bernstein's 's inequality instead of Hoeffding's inequality. An additional union bound over F now implies
P
sup deA(K),
E
(U:r
Σ ~の -U,,))
X log (1)8)
A log (k]F110)
20
max
74
n2
Finally, we that I E F by convexity of F. and thus need extra union bound over T. This completes the proof of the theorem.
We now show counterparts Theorem and Theorem 3.
Corollary 3. Fix (0, 1). For any convex F for which Assumption I holds we have that for all E A(k) with probability 1
reg(#j, D2) s min D,-A,,t)-D(--ooo (()
fEF
Reg
OLLO (L)((T)
to
log()F100)
log(k//)
T
T
T
-- log(f (z(00(())))))))))))))))))))))))) log( AT/0) +
0 log(2))
E ~A,,0((9-D)
X (og(k/((T/))
As log(k(F(T/j))
max
n;
n
where for Option A we have ( argmax r' (1, and for Option we have ()
Proof. The definition of regret for Option A implies that
reg(Ty, Dx) = V(TA, Dx) - u(s, = Ei-A D. [max (TT,, - - v(Fx(())] sa(M]
$ BAnAAED [argmax (y,, -))
yelk]
= =EAA, (c))) (f,r
The bound now follows from Theorem 4. For Option B we have similar derivation with
reg(Tj,Dx) v(TA, v( Dx) Dx) EA-A.- E, v(TT,,(()))
29

---

#: k r" (i),a())-
-EE 1=1
(T) (1p()))))) (l,0()))))))
E D.. (wli) The bound again follows from Theorem
(olo)(
-[f,r(0)).
D Experiments
D.1 Experimental setup details
We identify domain in the mix-instruct dataset by the prefix in the sample id, which is dolly 15k, twgptt4, aion, sha regpt, or uni fied chip2. The number of samples for each domain 6858, 20754, 106, 2719 and 69563 respectively.
Results report the regret during training and Table shows metrics aggregated from checkpoints during training. Since we had metrics available for each checkpoint, there was need for creating single routing function, e.g., through model souping. The same evaluation procedure was used for all approaches including baselines.
All reported results are averaged over replications.
We conducted our experiment on a cluster with 256 v5e TPUs. A single experiment run took about 2 hours. We estimate that all experiments involved in this research project took about 1 week of compute time.
D.2 Additional results
In Figure 3, Figure and Figure 5 we present the remaining comparisons for Algorithm 1 for OLO Option B and Option A, and for OLLO Option respectively.
For Figure 3, OLO with Option B, we make the same observations as in the main text for OLLO with Option B, that Algorithm tries equalize the regrets across all domains which leads to reduced regret for Domain 4, but slightly higher regret for the remaining domains. The regret against the best per example expert uniformly higher across domains compared the baseline. This is surprising as the objective which Algorithm works with in this setting is not aimed at optimizing the regret against this stronger competitor.
For Figure 4, OLO with Option A, and Figure 5, OLLO with Option A we make the following observations. The regret against the best per example expert is decreased compared to the baseline across all domains for the OLO oracle and is decreased or remains the same for the OLLO oracle. This is in contrast with the results for Option B, where when the domain weight is decreased by the max player. Further, we see that minimizing the regret the best expert per token results in smaller regret against the domain experts well. This is to be expected as the competitor defining the regret for Option A is stronger compared to that of Option B.
that the regret for domains increases
E
Unbounded loss bound
The following generalization bound follows directly Theorem of [Cortes et al., 2021b). It holds for any unbounded loss function with bounded second-momon moment. In particular, can be applied the log loss when the second-moment is bounded.
Theorem 5. Fix 1). Then, for any hypothesis set H such that E E0--[[ (f),[(((h,xx)) < +o0 for all h e H, the following holds with probably at least - 8 over the draw of sample of size m from D:
((((,,x)) x- 50
(E,[E(h,,))] S s 5-.5
E x-
(12
+
where Am. log (E 2 log 3, 7 To
(logm), and To(p)
VI+ 2/2 log for any μ > O. No. (((H)) 5 x2t represents the lao -coerring number of the f-losses axsociated with the hypotheses H. bused on sample of size 2m, denote by x with a precision of 5.
30

---

Regret against domain expert
Regret agairst expert
weights
domain
Demain
Domain
0.25
Domain
0.00
1.00
0.25
0.00
2000
4000
6000
8000
10000
2000
60.00
10000
2000
4000
10000
step
step
Step
Figure 3: Comparison of Algorithm with Option (bottom) against baseline (top) without domain weight adjustment using linear loss, corresponding to an OLO oracle.
Regret against expert
Regret against expert
weights
2.5
domaih
Domain
0.0
Domain
0.50
0.25
Domain
0.00
2.5
0.0
0.50
0.25
2000
4000
5C00
8000
10000
2000
4000
6003
8000
10000
2000
4000
6000
ROCO
10000
Figure 4: Comparison of Algorithm with Option A (bottom) against baseline (top) without domain weight adjustment using linear loss, corresponding OLO oracle.
Regret against domain expert
Regret against best expert
Domain weights
1.00
domalh
0.0
0.75
Domwin
-2.5
Domain 2
Damain
Domain
0.30
1.00
0.75
0.0
2.5
0.25
0.30
4000
4000
10000
2000
6000
10000
step
step
step
Figure 5: Comparison of Algorithm with Option (bottom) against baseline (top) without domain weight adjustment using log-loss, corresponding to an OLLO oracle.
31

---

In particular, choose in the bound. The result generalizes the case where only higher-order moment of the loss (higher than 2) is bounded.
72
32


Reviews:
[{"review_id": "wEa5QWeYNz", "reviewer": "Reviewer_y9hx", "summary": "The paper introduces an algorithm for predictive model routing in the presence of unknown mixtures of source domains, framed as a multiple-source domain adaptation problem. The authors leverage minimax regret optimization and online learning oracles to design a routing function that selects the best model for a given input among several domain-specialized models. The approach is supported by theoretical regret bounds  and evaluated empirically on the MixInstruct benchmark using LLMs.", "questions": "I suggest analyzing routing failures in existing LLMs to motivate scenarios where predictive, input-only routing with unknown mixtures is practically impactful.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 1, "originality": 1, "strengths_and_weaknesses": "strengths:\n- The paper provides detailed, formal regret bounds for both online learning oracles and online Log-Loss oracle -based algorithms grounded in established multiple-source domain adaptation literature.\n- The paper openly discusses limitations of assumptions \n\nweakness:\n- LLMs typically have prior knowledge of application tasks and their relative frequencies (contrary to the paper's assumption on unknown domain mixtures\n- The proposed framework targets robustness to arbitrary mixtures. In practice, adversarial or drastically shifting mixtures are rare, and the central technical contributions seem tailored to an artificially difficult setting rather than one current generative ML systems face.\n- The saddle-point approach and dueling no-regret learners follow closely from the cited literature, the problem framing and regret decomposition rely directly on classic MSA theory. The paper primarily applies these known tools to this contrived setting without introducing theoretical innovations beyond careful integration.", "was_revised": false, "final_justification": "", "rebuttal": ">LLMs typically have prior knowledge of application tasks and their relative frequencies (contrary to the paper's assumption on unknown domain mixtures\n\n>The proposed framework targets robustness to arbitrary mixtures. In practice, adversarial or drastically shifting mixtures are rare, and the central technical contributions seem tailored to an artificially difficult setting rather than one current generative ML systems face.\n\nWe respectfully disagree with the claim that the assumption of an unknown domain mixture is invalidated by the use of large language models (LLMs). While LLMs are indeed pretrained on broad web-scale corpora (e.g., Wikipedia, StackOverflow, news, books, code) the specific domain weights used in training are carefully handcrafted and training is very sensitive to the mixture choices. For example improving pre-trained performance on coding can adversely affect the performance on natural language tasks such as text summarization or reasoning on math datasets. Furthermore, pretraining on a wide range of domain mixtures does not eliminate the need to explicitly model uncertainty over domain mixtures at deployment time.\n\nIn fact, the unknown mixture assumption remains critical in many practical settings:\n\n\n- Specialized deployment domains: LLMs are increasingly deployed in high-stakes areas such as medical triage, legal document analysis, or scientific assistant tools. These domains often involve highly skewed, out-of-distribution inputs. For instance, a model used in an emergency room chatbot will encounter a mixture of rare and critical conditions not seen in pretraining, with dramatically different costs of error.\n\n\n- Dynamic task distributions: Applications like customer support, AI tutoring systems, or internal enterprise tools often face time-varying or user-dependent mixtures of sub-tasks (e.g., billing issues vs. technical queries). These subpopulations shift over time or across users and are not captured by static pretraining priors.\n\n\n- Multi-agent or expert systems: In systems involving deferral to humans, collaboration between models, or fallback mechanisms, modeling the domain/task distribution is essential. For example, if an AI assistant can defer to a human or another model, it must reason about the uncertainty of task types and associated costs—something naturally handled via mixture models.\n\n\n- Fairness and group robustness: In fairness-sensitive applications (e.g., lending or hiring), subpopulations (e.g., based on age, location, or socioeconomic status) may have distinct conditional distributions and label noise characteristics. The test-time population may be an unknown mixture of these, and performance guarantees require reasoning under distributional uncertainty.\n\n\n- Security and robustness: Adversarial attacks or distributional shifts (e.g., bots or prompt hacking) can skew the input distribution in unpredictable ways. Modeling the deployment distribution as an unknown mixture helps reason about worst-case behavior and supports robust optimization.\n\n\nThese and other examples demonstrate that, even though LLMs encode useful inductive biases, they do not explicitly model the task or domain distribution at inference time, nor do they adapt to new mixtures unless fine-tuned or combined with adaptive mechanisms such as routing, calibration, or deferral.\n\n\nMoreover, even during fine-tuning, similar mixture-related challenges arise: practitioners must balance multiple competing objectives, e.g., truthfulness, creativity, helpfulness, safety (see, e.g., [1–4]). These can be viewed as distinct domains, with specialized models or loss functions acting as domain experts. Modeling such cases as mixtures is not only natural but essential for scalable adaptation and control.\n\n\nOur framework explicitly captures this setting, providing a principled basis for learning and decision-making under unknown and heterogeneous domain mixtures.\n\n>The saddle-point approach and dueling no-regret learners follow closely from the cited literature, the problem framing and regret decomposition rely directly on classic MSA theory. The paper primarily applies these known tools to this contrived setting without introducing theoretical innovations beyond careful integration.\n\nWe appreciate the reviewer’s feedback and agree that the online min-max framework we use draws on known tools from the literature, including dueling no-regret learners and classic MSA theory. We do not claim to introduce fundamentally new techniques for analyzing such games, and we explicitly acknowledge the standard nature of the regret decomposition in the paragraph starting on line 151.\n\n\nThat said, we would like to emphasize that the key novelty of our work lies in the formulation and tractable instantiation of the min-max optimization problem in Equation (2), which is distinct from classical MSA settings. While our setup is inspired by the MSA framework, the problem we introduce is not a direct or trivial extension. Specifically:\n\n\nThe problem structure in Equation (2) is tailored to a setting involving instance-dependent deferral decisions, requiring a careful rethinking of both the minimization and maximization objectives.\nWe propose two computationally tractable versions, Option A and Option B, that admit practical implementations using first-order online learning oracles. These variants are significantly simpler to implement compared to typical MSA approaches, which often require solving non-convex DC (difference-of-convex) programs that are computationally more intensive and less scalable.\n\n\nThus, our contribution is not in reinventing the theory behind online min-max games, but in developing a new problem formulation and practical algorithmic strategy that enables efficient training in settings where MSA would be theoretically applicable but operationally cumbersome. We believe this design perspective is both novel and valuable, especially in domains where computational simplicity is essential. Additionally, we provide a series of theoretical guarantees supporting our suggested solutions.\n\n>I suggest analyzing routing failures in existing LLMs to motivate scenarios where predictive, input-only routing with unknown mixtures is practically impactful.\n\nThank you for the suggestion. We agree that analyzing failure modes in LLMs can help motivate the need for predictive, input-only routing under unknown mixtures.\n\n\nThere is growing empirical evidence that LLMs struggle to specialize simultaneously across diverse domains and objectives. For example, several recent works [1–5] highlight issues such as catastrophic forgetting during continual fine-tuning [5], instability in multi-objective alignment [1–4], and interference between domain-specific capabilities. These failures become particularly pronounced when LLMs are expected to handle heterogeneous tasks without explicit task supervision or routing.\n\n\nThese observations underscore the need for modular systems with effective input-level routing mechanisms—especially in settings where the input distribution is a latent mixture over tasks or domains. In such settings, predictive routing (based solely on input features) offers a practical solution that avoids costly retraining or fine-tuning, and our framework provides a principled way to learn such routing policies under domain uncertainty.\n\n\nWe will revise the text to better highlight this motivation and thank the reviewer again for pointing out this connection.\n\n\n[1] Wang, Kaiwen, et al. \"Conditional language policy: A general framework for steerable multi-objective finetuning.\" arXiv preprint arXiv:2407.15762 (2024).\n\n[2] Guo, Yiju, et al. \"Controllable preference optimization: Toward controllable multi-objective alignment.\" arXiv preprint arXiv:2402.19085 (2024).\n\n[3] Jang, Joel, et al. \"Personalized soups: Personalized large language model alignment via post-hoc parameter merging.\" arXiv preprint arXiv:2310.11564 (2023).\n\n[4] Rame, Alexandre, et al. \"Rewarded soups: towards pareto-optimal alignment by interpolating weights fine-tuned on diverse rewards.\" Advances in Neural Information Processing Systems 36 (2023): 71095-71134.\n\n[5] Luo, Yun, et al. \"An empirical study of catastrophic forgetting in large language models during continual fine-tuning.\" arXiv preprint arXiv:2308.08747 (2023)."}, {"review_id": "2sR4dnLr0m", "reviewer": "Reviewer_BcKM", "summary": "This submission investigates the model routing problem for testing data that are unknown mixtures of source data domains. The authors formulate this challenge as a multi-source domain adaptation problem and propose a novel and scalable routing algorithm that can achieve regret bounds tightly linked to the online learning oracles. Strong theoretical guarantees ensure the robustness of the proposed model routing strategy. Empirical results on LLM instruction tasks also demonstrate its advantage over the baseline of uniform routing.", "questions": "Check the weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. The studied model routing or selection problem is of great significance in improving model performance in complex real-world deployment scenarios.\n\n2. Both the perspective of taking model routing as multi-source domain adaptation and the proposed routing algorithm are novel.\n\n3. The presentation is clear, and the theoretical analysis is very solid.\n\n## Weaknesses\n\n1. Although I acknowledge that the primary contributions of the paper are theoretical and algorithmic, current empirical results are not extensible. First, it only demonstrates the advantage of the proposed routing algorithm over the vanilla uniform routing strategy. It would enhance the empirical justification by providing results of advanced model selection or routing baselines. Second, since multi-source domain adaptation is widely studied in vision tasks [Hoffman et al., 2021],  adding empirical results of vision tasks would also enhance the justification.\n\n2. The efficiency analysis of the algorithm is not discussed. Whether efficiency may be a concern depends on the problem setting. What is the sample size of the target domain? Is target access and evaluation offline or online? What if the target domain is not a trivial mixture of source domains, i.e., the target domain consists of various out-of-distribution data?", "was_revised": true, "final_justification": "I would like to maintain my original rating.", "rebuttal": ">First, it only demonstrates the advantage of the proposed routing algorithm over the vanilla uniform routing strategy. It would enhance the empirical justification by providing results of advanced model selection or routing baselines.\n\nThank you for the suggestion. We would like to clarify that our method is not only compared against uniform routing, but also against two stronger baselines for router learning without domain adaptation: direct accuracy maximization and cross-entropy minimization. Across all settings, we observe consistent performance gains, demonstrating the practical advantage of our approach beyond naive or uniform strategies.\n\n\nWhile we agree that additional experiments are always valuable, scaling them, especially in large-scale settings, is computationally expensive. To ensure fair and meaningful comparisons, we designed our evaluation using the benchmark task introduced in Jiang et al. (2023), which reflects current state-of-the-art experimental setups for this problem. We believe these experiments are sufficient to validate the effectiveness of our method in a realistic and widely accepted setting.\n\n\nThat said, we appreciate the suggestion to include more advanced model selection or routing baselines. We consider this a valuable direction for follow-up work, particularly as new methods emerge. Additionally, incorporating multi-source domain adaptation tasks from vision, as studied in works such as Hoffman et al. (2021), could further enrich our empirical validation. We plan to explore such extensions in future iterations of this work.\n\n\n>The efficiency analysis of the algorithm is not discussed. Whether efficiency may be a concern depends on the problem setting.\n\nEfficiency is not a concern in our experimental setup even though we use a relatively large LLM for the policy class. This is because the OLO and OLLO have particularly nice forms where we can use the simple closed form update of Hedge for the max player and use standard first order optimization methods for the min-player. Overall the computational complexity is no higher than mini-batched versions of gradient descent for optimizing LLMs.\n\n>What is the sample size of the target domain?\n\nThe number of samples for each domain are 6858, 20754, 106, 2719 and 69563 respectively. These details are already included in Appendix D.1\n\n\n>Is target access and evaluation offline or online?\n\nThe evaluation is online, that is we plot the current instantaneous regret.\n\n\n>What if the target domain is not a trivial mixture of source domains, i.e., the target domain consists of various out-of-distribution data?\n\nWhile a full analysis of this setting is beyond the scope of our work, we note that, similar to prior results in the MSA literature (Mansour et al., 2021; Hoffman et al., 2021; Cortes et al., 2021b), one can show that if the R'enyi divergence between the target distribution and the convex hull of the source domain distributions is sufficiently small, then our performance guarantees remain approximately valid and practically meaningful."}, {"review_id": "WbCQwM8bWR", "reviewer": "Reviewer_APhc", "summary": "The paper addresses the problem of routing inputs to the best model from a pool of domain experts when the test-time distribution is an unknown mixture of the source domains. The authors formulate the problem as a multiple-source domain adaptation (MSA) problem and propose an algorithm based on minimax-regret optimization. \n\nThey provide theoretical guarantees and validate the approach empirically.", "questions": "I refrain from posing questions due to my low confidence, and apologize for this to the AC and the other reviewers.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- Presentation: The paper is exceptionally well-written, clear, and logically structured.\n- Theoretically Grounded: The work is built on a solid theoretical foundation. The minimax-regret formulation seem sound\n\nI appreciate the note on applying the framework to discriminative models.\n\n## Weaknesses\n- None of the paper as far as I am aware. My primary limitation as a reviewer, detailed below, is in assessing the novelty and significance\n\nI have spent considerable time on this paper. Its quality is apparent. The formalism, the derivations, and the theoretical analysis all appear to be correct. However, the specific field of multiple-source domain adaptation is outside my expertise. While I can attest to quality of the writing, I cannot comment on the novelty or significance of the work.\n\nThis appears to be a high-quality paper, and I recommend accepting it. My confidence is, however, low.", "was_revised": true, "final_justification": "My initial review noted my low confidence in assessing novelty of the paper, as the specific subfield is outside my area of expertise. \n\nThe assessments from other reviewers have partially resolved this uncertainty. After reading their comments I have raised my confidence score while maintaining my recommendation for acceptance.", "rebuttal": "Response: Thank you very much for your thoughtful review and for taking the time to carefully read through our paper. We greatly appreciate your positive assessment of the writing, formalism, and theoretical analysis.\nWe understand that the specific topic of multi-source domain adaptation (MSA) may fall outside your primary area of expertise. To help clarify the novelty and significance of our contribution within this field, we would like to briefly summarize the key aspects:\n\n\n - Our work introduces a new input-dependent framework grounded in a formal min-max formulation, which differs from standard MSA settings that typically assume access to domain labels or covariate shift assumptions.\n\n\n - We present tractable algorithms based on online learning oracles, enabling efficient implementation in large-scale settings, a practical gap in much of the prior MSA literature.\n\n\n - Our theoretical guarantees are derived under general conditions and extend existing results by removing some assumptions typically made in prior work (e.g., domain or task supervision).\n\n\n - Empirically, we evaluate our method on a benchmark task introduced in recent state-of-the-art work (Jiang et al., 2023) and compare against multiple stronger baselines beyond uniform routing.\n\nWe hope this helps situate our contribution within the broader MSA literature and reassures you of its relevance. Once again, we are grateful for your recommendation and the time you dedicated to this review."}, {"review_id": "PJLpjBQSWi", "reviewer": "Reviewer_83vD", "summary": "This paper addresses the problem of routing inputs to the best-suited machine learning model from a set of domain-specialized models when the target distribution is an unknown mixture of source domains. It frames the problem as one of multiple-source domain adaptation (MSDA) and introduces a theoretically grounded algorithm to address it. Two algorithmic variants are proposed, and some empirical results are collected to demonstrate the approach.", "questions": "- Speaking of Option A, the authors claim that \"this approach introduces additional bias when there is high variance in the expert scores for a given input\" (lines 139 and 140). Can you explain the source/cause of this additional bias?\n- On lines 171 and 172, the authors mention including a KL regularization term, to make the predicted distribution closer to \"a uniform domain distribution or a given domain prior\". Did you include this regularization in your experiments? Did you measure its impact on the results? Have you used any other prior besides the uniform?", "limitations": "The limitations are mentioned and acnowledged, although they are spread throughout the paper. I think the paper would benefit from having a dedicated section with a summary of those limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The problem is relevant and well-motivated, with clear distinctions from prior MoE and model routing works.\n- The proposed method has a strong theoretical foundation, building on MSA theory to derive novel regret bounds that hold under reasonable assumptions. Although I did not do a step-by-step review for the proofs in the appendix, the arguments used in the proofs are correct and the obtained results are compatible with the existing prior work in DA, so I think it is safe to assume that they are at least mostly correct.\n- The paper is technically high-quality, well written, well organized, and presents sufficient details and intuitions in most parts.\n\nWeaknesses:\n- The main weakness of the paper is its limited experimental scope. Although the authors claim to be mostly interested in making theoretical and algorithmic contributions, a more robust set of experiments could have been conducted.\n- The evaluation should also be conducted in a practical usage scenario, e.g. where the learned router is used to select the best model for the given input and then a single prediction is generated from the chosen model and its quality is evaluated. I am willing to raise my score if such an experiment is added (or if the authors can convince me it would bring no additional value).\n- The chosen reward metric (BLEU) has many known flaws and is no-longer the most reliable metric for virtually any NLP problem. It is therefore hard to understand its choice in this work.\n- The distinction between OLO and OLLO oracles should be made more explicit, e.g. by providing the explicit equations for both.\n- The choice of LLMs as the base models to which apply the proposed approach is a bit questionable. State of the art LLMs can handle several domains without much need for specialization / fine-tuning. This is not a major concern though, since the proposed approach is completely agnostic to the type of models it is being applied to.", "was_revised": true, "final_justification": "As mentioned in my response to the Authors' rebuttal, they addressed one of my two major concerns favorably (lack of experiments with a single expert), while providing convincing arguments for not extending the experiments to more datasets. The answers to the remaining questions were also satisfactory. Therefore, I recommend acceptance of this manuscript.", "rebuttal": "> The main weakness of the paper is its limited experimental scope. Although the authors claim to be mostly interested in making theoretical and algorithmic contributions, a more robust set of experiments could have been conducted.\n\nThank you for your feedback. We appreciate the importance of broad empirical validation and agree that additional benchmarks would further strengthen the paper. That said, our primary goal in this work is to introduce a new perspective on model routing through a domain adaptation lens, along with a principled optimization framework supported by theoretical guarantees and a tractable implementation.\n\n\nTo evaluate our approach empirically, we focused on the MixInstruct dataset, a recent and challenging benchmark specifically designed to study instruction tuning across diverse tasks. Our experiments demonstrate consistent gains over multiple baselines, including stronger alternatives to uniform routing, and we believe this provides solid evidence of the method’s practical effectiveness.\n\n\nWe also note that identifying publicly available benchmark datasets that align well with our setting, involving input-dependent routing under unknown domain mixtures, is not straightforward. Existing benchmarks for multi-source adaptation or instruction tuning often lack the required structure for evaluating input-only routing or do not include domain/task metadata in a form compatible with our framework. We would be grateful for any suggestions the reviewer may have regarding additional suitable datasets.\n\n\nExtending our evaluation to other domains such as vision or multi-modal tasks is a promising direction that we intend to pursue. However, we believe the core contributions, a novel problem formulation, tractable algorithms with theoretical guarantees, and strong empirical results on a relevant benchmark, are already significant and valuable in their own right.\n\n\n>The evaluation should also be conducted in a practical usage scenario, e.g. where the learned router is used to select the best model for the given input and then a single prediction is generated from the chosen model and its quality is evaluated. I am willing to raise my score if such an experiment is added (or if the authors can convince me it would bring no additional value).\n\nAt inference time we can certainly include an additional experiment where, instead of computing the prediction using the weighted mixture of experts, the router samples a single expert according to the learned distribution and outputs the prediction from that expert alone. This setup naturally aligns with the practical usage case the reviewer described.\n\n\nImportantly, this sampling-based strategy retains similar regret guarantees to those in Theorem 1 and Corollary 1. A standard martingale concentration argument shows that the cumulative reward obtained by sampling experts according to the learned distribution closely tracks the expected reward from using the mixture, ensuring the same asymptotic guarantees hold up to high-probability deviations.\n\n\nWe will include this version of the algorithm, along with the corresponding theoretical justification, in the revised paper. We are also happy to include an experiment for the above version of the algorithm.\n\nWe appreciate the reviewer’s openness to reconsidering their score and hope this addition addresses the concern.\n\n>The chosen reward metric (BLEU) has many known flaws and is no-longer the most reliable metric for virtually any NLP problem. It is therefore hard to understand its choice in this work.\n\nWe agree that BLEU has well-known limitations. However, our choice was motivated by a desire to ensure comparability with MixInstruct (Jiang et al., 2023), which serves as the most relevant and recent benchmark for our setting and also uses BLEU as the reward metric. Grounding our experiments in this benchmark allowed us to align with prior work and highlight the benefits of our method under consistent evaluation conditions.\n\n\nThat said, we agree that experimenting with more task-appropriate or learning-signal-aligned reward metrics is important and could further strengthen our results. We plan to explore alternative reward metrics in future versions and would be happy to consider specific suggestions from the reviewer.\n\n>The distinction between OLO and OLLO oracles should be made more explicit, e.g. by providing the explicit equations for both.\n\nWe will provide explicit equations to further clarify Definitions 1 and 2, and will comment on the distinction.\n\n>The choice of LLMs as the base models to which apply the proposed approach is a bit questionable. State of the art LLMs can handle several domains without much need for specialization / fine-tuning. This is not a major concern though, since the proposed approach is completely agnostic to the type of models it is being applied to.\n\nThis really depends on the domains, for extended discussion please see our response to Reviewer y9hx.\n\n\n>Speaking of Option A, the authors claim that \"this approach introduces additional bias when there is high variance in the expert scores for a given input\" (lines 139 and 140). Can you explain the source/cause of this additional bias?\n\nIn essence, bias_A quantifies the bias from estimating the maximum expected score by taking the maximum over realizations, thus exchanging the order of the expectation and maximum in the expression. This term is favorably small, e.g. when all scores are deterministic or they are random but there is always a single fixed model that is best. See also our discussion regarding Option A in the paragraph between lines 259-278.\n\n\n>On lines 171 and 172, the authors mention including a KL regularization term, to make the predicted distribution closer to \"a uniform domain distribution or a given domain prior\". Did you include this regularization in your experiments? Did you measure its impact on the results? Have you used any other prior besides the uniform?\n\nYes, we included the KL regularization term in our experiments, using a uniform domain distribution as the prior and a regularization weight of 1.7. This choice was motivated by preliminary experiments where omitting the KL term led to the following behavior: after several thousand training steps, we observed that the instantaneous regret began to increase, indicating that the router was overfitting or drifting toward degenerate policies.\n\n\nThe KL regularization serves to stabilize training by encouraging the learned routing distribution to remain close to a uniform baseline, effectively shrinking the policy class and preventing overconfident or brittle behavior in early stages of training. While we did not carry out an extensive \"ablation\" across different priors, we did experiment briefly with removing the regularization altogether and found it to negatively affect stability.\n\n\nWe have not explored alternative priors beyond the uniform in this work, but doing so, e.g., by incorporating domain frequency estimates or prior knowledge, could be a promising direction for future research. We will clarify this in the revised version and include a brief discussion of the KL term’s impact."}]

Author rebuttal:

Meta-review: This paper focuses on the multiple-source domain adaptation problem when target data follow an unknown mixture of source data domains. The authors propose an algorithm based on minimax regret optimization and online learning oracles that selects for each input  the best model among several trained (source) models, 2 variants (options) are proposed to improve the practical efficiency. Another contribution is the theoretical analysis in the form of regret bound(s) on the performance on new domains is proposed, expressed as a convex combination of the best regrets in the source domains accompanied with a concentration term that diminishes when the concentration of source data increases.  An empirical evaluation studying the behavior of the method is also proposed.  

Based on the released reviews, the following strengths have been identified:  
-Paper well written, presence of a discussion on the limitations.  
-Strong theoretical foundations.  
-The proposed selection model is innovative and interesting.  
-The model is interesting for addressing complex scenarios.  

The following weaknesses have also been identified:  
-The proposed setting is limited to arbitrary mixtures.  
-Limited theoretical innovation.  
-Limited empirical evaluation.  
-Efficiency not sufficiently discussed.  

During rebuttal, authors provided multiple answers to reviewers’ issues, many of them were addressed but some remarks related to limited experimental evaluation and limited setting were maybe not completely addressed. During discussion and final evaluation, the reviewers made the following feedbacks.  


-Reviewer APhc reminded that for him the paper is well-written and the theory presented is sound. While the empirical evaluation is limited and efficiency is not discussed, he did not consider these to be grounds for rejection for a theoretical paper. Concerning the assessment of novelty, he was initially not confident as the specific subfield is outside his area of expertise, but he mentioned that the assessments from other reviewers have partially resolved this uncertainty and after reading their comments he was more confident on his evaluation. Notably, he carefully considered Reviewer y9hx comments and while the presented theory is an extension of existing work he still leaned towards acceptance. Eventually, he maintained his recommendation as borderline accept.   
-Reviewer 83vD mentioned that authors’ rebuttal addressed one of his two major concerns favorably (lack of experiments with a single expert), while providing convincing arguments for not extending the experiments to more datasets. He also indicated that the answers to the remaining questions were also satisfactory. During discussion, he mentioned that he understood the concerns of Reviewer y9hx that the theoretical contribution of this paper might be somewhat incremental and the underlying assumptions might be too pessimistic in many cases, but he was still convinced that the theoretical results represent an interesting contribution to the community. Then he proposed the direct acceptance of this paper and supported it.  
-Reviewer BcKM indicated that most of his initial questions have been addressed. He would like to maintain his original rating of borderline acceptance but did not support the paper beyond.   
-Reviewer y9hx argued in his review that the building of the methods come directly from existing Multiple-source Domain Adaptation and minimax regret literature. Eq.(2) for example is a standard minimize worst-case regret over domain mixtures formulation adapted notably from Cortes et al. (2021b) and that the 2 options proposed are common to simplify regret computation. However, the reviewer did not participate actively to discussion. Note tha  I skipped here the remarks on LLMs which I found not directly relevant for the evaluation of the paper.  

Authors have answered to reviewer y9hx that they did not aim at fundamentally introducing new techniques, but a formulation and a tractable instantiation of the min-max problem of Eq.(2). A novelty of the work is the formulation in terms of regret rather than loss (in comparison to the literature). One important strength of the paper lie the theoretical results which has been recognized as a strength by the reviewer. The other reviewer have a positive evaluation of the paper and at least 2 of them (Reviewer 83vD and APhc) felt that the strengths of the paper outweighed the weaknesses mentioned by reviewer y9hx. Reviewer BcKM maintained his borderline accept evaluation while reviewer y9hx did not react against acceptance. I read the paper and I saw that the theoretical part was a strong point of the contribution.  

I then decided to follow the line of the majority of the reviewers by proposing acceptance.  
I recommend to the authors to integrate in their revised version the elements provided notably to reviewer 83vD and also those clarifying the novelty of the contribution that appear along the discussions with reviewers.
Decision: Accept (poster)