#  MAP: Low-compute Model Merging with Amortized Pareto Fronts via Quadratic
Approximation

Lu Li1*, Tianyu Zhang2,3*, Zhiqi Bu4*, Suyuchen Wang 2, Huan He1, Jie Fu4,
Yonghui Wu5, Jiang Bian5, Yong Chen1, Yoshua Bengio2
1 University of Pennsylvania, 2 MILA 3 ServiceNow Research
4 Amazon AI 5 HKUST 6 University of Florida
{luli1, huanhe<EMAIL_ADDRESS>
{tianyu.zhang<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>{bianjiang<EMAIL_ADDRESS>Equal
contribution. This work does not relate to ZB’s position at Amazon.

###### Abstract

Model merging has emerged as an effective approach to combine multiple single-
task models, fine-tuned from the same pre-trained model, into a multitask
model. This process typically involves computing a weighted average of the
model parameters without any additional training. Existing model-merging
methods focus on enhancing average task accuracy. However, interference and
conflicts between the objectives of different tasks can lead to trade-offs
during model merging. In real-world applications, a set of solutions with
various trade-offs can be more informative, helping practitioners make
decisions based on diverse preferences. In this paper, we introduce a novel
low-compute algorithm, Model Merging with Amortized Pareto Front (MAP). MAP
identifies a Pareto set of scaling coefficients for merging multiple models to
reflect the trade-offs. The core component of MAP is approximating the
evaluation metrics of the various tasks using a quadratic approximation
surrogate model derived from a pre-selected set of scaling coefficients,
enabling amortized inference. Experimental results on vision and natural
language processing tasks show that MAP can accurately identify the Pareto
front. To further reduce the required computation of MAP, we propose (1) a
Bayesian adaptive sampling algorithm and (2) a nested merging scheme with
multiple stages.

##  1 Introduction

Large pre-trained foundation models have become available in many real-world
applications wornow2023ehrshot ; thirunavukarasu2023large ; cui2024scgpt .
This increasing availability has led to a popular practice of fine-tuning
these pre-trained models to adapt to a wide range of downstream tasks. The
practitioners can independently fine-tune the same pre-trained model, such as
CLIP style models clip ; clap ; zhai2023sigmoid , large language models
brown2020language ; rozière2023code ; touvron2023llama ; jiang2024mixtral etc.
and then release the fine-tuned models without releasing the training data. As
the deployment of such fine-tuned models increases, the concept of model
merging—combining models with identical architectures and initializations has
emerged as a promising approach to combine their respective capabilities. This
is useful, especially in scenarios where the training data for each task are
private and cannot be shared, such as individual-level patient data in a
hospital and behavior data in social media recommendation systems.

Existing methods for merging models typically involve calculating a weighted
average of the parameters from multiple models to enhance performance
uniformly across various tasks. However, this approach often overlooks the
conflicts or interference among the diverse objectives of these tasks, which
can lead to trade-offs in terms of model performance on various tasks. In
real-world applications, it is often useful to obtain a set of Pareto optimal
solutions rather than a single averaged model. Such solutions allow
practitioners to choose among different trade-offs, depending on their
specific needs. For example, hospitals specializing in certain areas might
prefer a model that excels in specific tasks relevant to their specialty while
maintaining adequate performance across a broader spectrum of diseases.

\begin{overpic}[width=433.62pt]{imgs/main_fig.png} \end{overpic} Figure 1: The
overall process of MAP under 2 tasks. Step 1: select tasks and their
corresponding task vectors. Step 2: sample a few scaling weights $\mathbf{c}$
to query the task metrics accordingly. Step 3: use a quadratic model to
approximate the mapping of $\mathbf{c}\rightarrow\textit{metrics}$ as a
surrogate model. Step 4: use NSGA-III (or other multi-objective optimization
algorithms) to find amortized Pareto fronts. Figure (a) shows the contour
plots of the actual accuracy landscape for the ViT models dosovitskiy2020image
obtained from 100 scaling coefficients (sampled uniformly) evaluated on the
SUN397sun397 and Carscars . Figure (b) shows the contour plots of the fitted
quadratic functions. Red lines represent the Pareto front in the decision
variable $(c_{1},c_{2})$ space. Figure (c) shows an example of the Pareto
Front. Pareto front (Grid search) is regarded as the ground truth given the
enough number of grid points. Pareto front (MAP, predicted) is the amortized
Pareto front. Pareto front (MAP, real) is the Pareto front involving the same
$\\{(c_{1},c_{2})\\}$ but re-evaluated as to get the ground truth metrics as a
comparison. The yellow lines are the evaluation performance of the fine-tuned
single task models.

In this paper, we introduce a novel method that identifies the Pareto front
without retraining the models to be merged. Our algorithm uses a quadratic
approximation of the evaluation metric as the surrogate model, and further
computes the Pareto front using existing evolutionary algorithms. Furthermore,
we enhance it with a Bayesian adaptive sampling method and a nested merging
scheme, which further brings down the computational cost. We validate our
method across a diverse set of tasks, spanning from vision to natural language
processing, and demonstrate its applicability to a variety of architectures,
including ResNet he2016deep , ViT dosovitskiy2020image , and large language
models brown2020language ; rozière2023code ; touvron2023llama ;
jiang2024mixtral .

#### Contributions

The main contributions of this paper are:

  * C1

Designing the quadratic surrogate models to approximate the evaluation metric
functions, which amortize the computation of Pareto fronts;

  * C2

Proposing a nested merging scheme to decrease computational complexity from
exponential to quadratic;

  * C3

Proposing the Bayesian adaptive sampling, which efficiently queries the
computationally expensive evaluations according to the loss information.

#### Related work

This paper is related to many existing works on multi-objective optimization,
Pareto optimality, task arithmetic, federated/private learning, Bayesian
methods, etc. We kindly refer the readers to Appendix A due to the page limit.

\begin{overpic}[width=433.62pt]{imgs/fig1.png} \end{overpic} Figure 2: (a)
Using the results of inference runs of merged ViT-B-32 models (CLIP
checkpoints from ilharco2022editing ) obtained from 250 combinations of
scaling coefficients, our method outperforms the direct search method in
finding a set of diverse solutions for eight tasks based on the same
computation expense. For both methods, we maximize a specific task while
requiring all tasks to have an evaluation metric above a certain threshold
($40\%$). The bar plot for each task shows the corresponding maximized
accuracy. (b) We increase the requiring bounds to ($65\%$) of the single-task
model. With the same computational budget, the brute-force direct search
method cannot find a feasible solution.

In Figure 2, we compare our method to the brute-force direct search. We
emphasize our setting that evaluating models is computationally expensive, and
therefore we can only query the evaluation pipeline a limited number of times.
This setting makes the direct usage of evolutionary algorithms like NSGA-III
infeasible (nevertheless, our usage of evolutionary algorithms on the
surrogate models is feasible). In particular, evolutionary algorithms need to
query the evaluation metrics so many times that exceeds our computational
budget, because each query must evaluate all single-task models. To give more
details, suppose we already have a set of solutions and know their evaluation
metrics, and we use evolutionary algorithms to pick the Pareto solutions among
them, then the set we find with the algorithms might not include all possible
Pareto solutions. Instead, it will likely be just a part of what we would find
if we have compared every possible pair of solutions directly against each
other (known as brute force search). Since brute force search compares all
possible solutions and finds all the Pareto optimums, it’s considered a
complete method. Therefore, when evaluating the effectiveness of our
algorithm, it is better to compare its results to those obtained from brute
force search in the case of a limited set of already-known solutions. Our code
is released here https://github.com/luli-git/MAP.git.

##  2 Background

###  2.1 Model merging

Model merging aims to find a way to combine multiple models with the same
architecture $\\{\bm{\theta}_{ft}^{n}\\}_{n\in[N]}$ with their initialization
$\bm{\theta}_{\textup{pre}}$ in a way such that the merged model parameterized
by
$\bm{\theta}_{m}=\bm{\theta}_{\textup{pre}}+\sum_{n=1}^{N}c_{n}\bm{\theta}_{ft}^{n}$
performs reasonably well on all $N$ tasks wortsman2022model .

A recent work by ilharco2022editing introduced task arithmetic as a simple and
effective way for performing model merging. The task vector for task $n$ is
defined as $\mathbf{v}_{n}=\bm{\theta}_{ft}^{n}-\bm{\theta}_{\textup{pre}}$,
which is the element-wise difference between the pre-trained parameters and
the fine-tuned parameters for the task $n$. To perform the model merging with
task vectors, we can compute
$\bm{\theta}_{\textup{pre}}+\sum_{n=1}^{N}c_{n}\mathbf{v}_{n}$, where $c_{n}$
is some scaling factors and has shown to be essential to the performance of
the merged model yadav2024ties ; yang2023adamerging .

Denoting the metric of task $n$ as $M_{n}$, most of the existing approaches
for model merging aim to improve an equal weight average metric
$\frac{1}{N}\sum_{n=1}^{N}M_{n}$. This target implies the user of the
algorithm has equal preferences between tasks. However, in real-world
applications, users might have biased preferences for the importance of tasks,
necessitating trade-offs. In such cases, the goal of model merging is no
longer the equal weight average metric. Instead, we need to answer a broader
question:

Given any preferences over the set of tasks, what is the best way to merge the
models?

###  2.2 Pareto fronts

#### Pareto dominance

Let $X$ be a set representing the solution space, where each element $x\in X$
is a possible solution to the multi-objective optimization problem. Let there
be $n$ objectives. Define an evaluation function $f_{i}:X\to\mathbb{R}$, where
$i\in\\{1,2,\cdots,n\\}$. Given two solutions $x,y\in X$, we define that $x$
Pareto dominates $y$, denoted by $x\succ_{P}y$, if and only if:

$\displaystyle\forall$ $\displaystyle i\in\\{1,2,\dots,n\\},f_{i}(x)\leq
f_{i}(y)\text{ and }\exists$ $\displaystyle
j\in\\{1,2,\dots,n\\},f_{j}(x)<f_{j}(y)$ (1)

#### Pareto optimal solutions

The Pareto front is the set of solutions in the solution space $X$ that are
not Pareto dominated by any other solutions in $X$.

$\text{PF}=\\{x\in X\mid\not\exists y\in X\text{s.t.}y\succ_{P}x\\}$ (2)

Pareto optimal solutions have been studied in multi-task (multi-objective)
learning (MTL) sener2018multi ; lin2019pareto . However, in most of the
studies, approximating the Pareto front is computationally expensive and data
inefficient. We introduce our method, MAP, a computationally efficient method
to find the Pareto front for model merging.

##  3 Methods

###  3.1 Quadratic approximation of evaluation metric

Given the task vectors $\\{\mathbf{v}_{n}\\}_{n\in[N]}$ and the initialization
$\bm{\theta}_{\textup{pre}}\in\mathbb{R}^{d}$, we denote the merged model
parameters as
$\bm{\theta}_{\text{merge}}(\mathbf{c})=\bm{\theta}_{\textup{pre}}+\mathbf{V}\mathbf{c}=\bm{\theta}_{\textup{pre}}+\sum_{n=1}^{N}c_{n}\mathbf{v}_{n}$,
where
$\mathbf{V}=\text{concat}(\mathbf{v}_{1},...,\mathbf{v}_{N})\in\mathbb{R}^{d\times
N}$ is the task matrix and
$\mathbf{c}=\text{concat}(c_{1},...,c_{N})\in\mathbb{R}^{N}$ is the scaling
coefficients for the task vectors.

We aim to optimize the evaluation metric for all tasks, denoted by $M_{n}$,
via the multi-objective optimization (MOOP)111The evaluation metric $M$ can be
differentiable (e.g. the mean square loss or the cross-entropy/perplexity) or
not necessarily (e.g. the classification accuracy, F1 score, BLEU or Rouge):

$\displaystyle\min_{c_{1},\cdots,c_{N}}M_{1}(\mathbf{c}),\cdots,M_{N}(\mathbf{c})$
(3)

This problem has $N$ variables and $N$ objectives, and we seek the Pareto
optimal solutions.

To do so effectively and efficiently, we use the second-order Taylor expansion
to approximate $M_{n}$:

$\displaystyle M_{n}(\mathbf{c})$ $\displaystyle\equiv
M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))=M_{n}(\bm{\theta}_{\textup{pre}})+\nabla
M_{n}(\bm{\theta}_{\textup{pre}})^{\top}(\bm{\theta}_{\text{merge}}(\mathbf{c})-\bm{\theta}_{\textup{pre}})$
$\displaystyle+\frac{1}{2}(\bm{\theta}_{\text{merge}}(\mathbf{c})-\bm{\theta}_{\textup{pre}})^{\top}\mathbf{H}_{n}(\bm{\theta}_{\textup{pre}})(\bm{\theta}_{\text{merge}}(\mathbf{c})-\bm{\theta}_{\textup{pre}})+R_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c})-\bm{\theta}_{\textup{pre}})$
$\displaystyle\approx M_{n}(\bm{\theta}_{\textup{pre}})+\nabla
M_{n}(\bm{\theta}_{\textup{pre}})^{\top}\mathbf{V}\mathbf{c}+\frac{1}{2}(\mathbf{V}\mathbf{c})^{\top}\mathbf{H}_{t}(\bm{\theta}_{\textup{pre}})\mathbf{V}\mathbf{c}$

where
$\mathbf{H}_{n}(\bm{\theta}_{\textup{pre}})=\nabla^{2}M_{n}(\bm{\theta}_{\textup{pre}})\in\mathbb{R}^{d\times
d}$ is the Hessian matrix and
$R_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c})-\bm{\theta}_{\textup{pre}})=R_{n}(\mathbf{V}\mathbf{c})$
is the third-order remainder, which is negligible when
$||\mathbf{V}\mathbf{c}||^{3}=||\bm{\theta}_{\text{merge}}(\mathbf{c})-\bm{\theta}_{\textup{pre}}||^{3}$
is small. Note that the second-order Taylor expansion is widely used and
provides a close approximation (see Figure 2 (a) and (b) and more discussion
in Appendix A), as neural networks tend to converge close to their
initialization, especially for fine-tuned models: it directly motivates
Newton’s method, and supports the analysis of convergence
mccandlish2018empirical ; bu2024pre and the scaling laws for large models
kaplan2020scaling ; hoffmann2022training .

Leveraging this quadratic approximation, we can define surrogate models for
each task $n$,
$\tilde{M}_{n}(\mathbf{c};\mathbf{A}_{n},\mathbf{b}_{n},e_{n})\equiv
e_{n}+\mathbf{b}_{n}^{\top}\mathbf{c}+\frac{1}{2}\mathbf{c}^{\top}\mathbf{A}_{n}\mathbf{c}$
and optimize the proxy problem of (3) via

$\displaystyle\min_{c_{1},\cdots,c_{T}}\tilde{M}_{1}(\mathbf{c}),\cdots,\tilde{M}_{T}(\mathbf{c})$
(4)

where

$\displaystyle\mathbf{A}_{n}=\mathbf{V}^{\top}\mathbf{H}_{n}(\bm{\theta}_{\textup{pre}})\mathbf{V}\in\mathbb{R}^{T\times
T},\mathbf{b}_{n}=\mathbf{V}^{\top}\nabla
M_{n}(\bm{\theta}_{\textup{pre}})\in\mathbb{R}^{T},e_{n}=M_{n}(\bm{\theta}_{\textup{pre}})+R_{n}$
(5)

Importantly, (4) is parameterized in contrast to (3), with
$\frac{(N+1)(N+2)}{2}$ unknown coefficients in ($e_{n}$, $\mathbf{b}_{n}$,
$\mathbf{A}_{n}$)222 1 coefficient for $e_{n}$, $N$ coefficients in
$\mathbf{b}_{n}$ and $N(N+1)/2$ coefficients in $\mathbf{A}_{n}$ due to its
symmetry. Thus, we can further leverage existing methods to learn the
coefficients by minimizing the empirical risk over multiple $\mathbf{c}$: for
instance,

$\displaystyle\mathbf{A}_{n}^{*},\mathbf{b}_{n}^{*},e_{n}^{*}=\arg\min_{\mathbf{A}_{n},\mathbf{b}_{n},e_{n}}\sum_{\mathbf{c}\in\Omega}|M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))-\tilde{M}_{n}(\mathbf{c};\mathbf{A}_{n},\mathbf{b}_{n},e_{n})|^{2}$
(6)

where $\Omega=\\{\mathbf{c}^{(1)},...,\mathbf{c}^{(N_{c})}\\}$ is the set of
$\mathbf{c}$ and $M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))$ is the
corresponding evaluation metric.

If the evaluation metric spanning to the whole $\mathbb{R}$, we use the
vanilla form of surrogate model:
$\tilde{M}_{n}(\mathbf{c};\mathbf{A}_{n},\mathbf{b}_{n},e_{n})\equiv
e_{n}+\mathbf{b}_{n}^{\top}\mathbf{c}+\frac{1}{2}\mathbf{c}^{\top}\mathbf{A}_{n}\mathbf{c}$.
When the evaluation metric is restricted with $\in[l,u]$, such as accuracy
$\in[0,1]$, we would warp the quadratic part with a sigmoid function, i.e.
$\tilde{M}_{n}(\mathbf{c};\mathbf{A}_{n},\mathbf{b}_{n},e_{n})\equiv(u-l)\text{sigmoid}(e_{n}+\mathbf{b}_{n}^{\top}\mathbf{c}+\frac{1}{2}\mathbf{c}^{\top}\mathbf{A}_{n}\mathbf{c})+l$.
Similarity, if the evaluation metric is restricted $\in[l,+\infty)$, a
softplus function as wrapper would be beneficial
$\tilde{M}_{n}(\mathbf{c};\mathbf{A}_{n},\mathbf{b}_{n},e_{n})\equiv\text{softplus}(e_{n}+\mathbf{b}_{n}^{\top}\mathbf{c}+\frac{1}{2}\mathbf{c}^{\top}\mathbf{A}_{n}\mathbf{c})+l$.
Please note that $u$, $l$ mentioned here are specific to the feasible domain
of the metric, not learnable parameters.

###  3.2 Model merging with amortized pareto fronts

In this section, we introduce our generalized algorithm for estimating the
amortized Pareto fronts. As mentioned in Section 3.1, we approximate the
evaluation metric $M_{n}(\cdot)$ by a surrogate quadratic model
$\tilde{M}_{n}(\cdot)$. We then utilize $\tilde{M}_{n}(\cdot)$ to compute the
amortized Pareto fronts. Please see the detailed experiments in Section 4 and
the algorithm details in Algorithm 1.

Algorithm 1 MAP

1: Prepare models $\\{\bm{\theta}_{ft}^{n}\\}$ and compute task vectors
$\\{\mathbf{v}_{n}=\bm{\theta}_{ft}^{n}-\bm{\theta}_{\textup{pre}}\\}$.

2: for $t\in[T]$ do

3: Sample $N_{c}$ vectors of $\mathbf{c}\in\mathbb{R}^{N}$. Denote the set as
$\Omega$.

4: for $\mathbf{c}=[c_{1},...,c_{N}]\in\Omega$ do

5: Compute
$\bm{\theta}_{\text{merge}}(\mathbf{c})=\bm{\theta}_{\textup{pre}}+c_{1}\mathbf{v}_{1}+\ldots
c_{N}\mathbf{v}_{N}$.

6: Derive the evaluation metric
$M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))$.

7: Fit the quadratic approximation surrogate model $\tilde{M}_{n}$ by learning
$\mathbf{A}_{n}^{*},\mathbf{b}_{n}^{*},e_{n}^{*}$ in (6).

8: Apply MOOP algorithm (e.g. NSGA-III) to $\\{\tilde{M}_{n}\\}$ and get the
Pareto front

###  3.3 Nested merging scheme

Empirically, we only need 30 pairs to get a good quality of Pareto front to
merge 2 tasks, but due to the curse of dimensionality, we need exponentially
more number of
$(\mathbf{c},\\{\tilde{M}_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))\\}_{n=1}^{N})$
pairs to get a good quality of Pareto front in the case of 8 tasks.
Theoretically, in the best case, the points to get a good quality of Pareto
front for $N$ is $O(N^{3})$. In the worst case, when the curse of
dimensionality dominates, it could be $O(N\cdot 2^{N})$. Using the nested
merging scheme, we reduce the computation complexity from $O(N\cdot 2^{N})$ to
$O(N\log_{2}^{N})$. Please refer to Table 5 for the detailed computational
complexity comparison. Algorithm details are presented in Algorithm 2.

Algorithm 2 Nested merging scheme

0: A predetermined preference $\textit{pref}\in\mathbb{R}^{N}$ over the $N$
tasks, the tuple of task, loss, task vector:
$G_{n}=(\text{task}_{n},l_{n},\bm{\theta}_{ft}^{n})$

1: Normalize pref to make sure the sum is 1

2: Initialize the set $\tau=\\{G_{1},\cdots,G_{N}\\}$

3: while $|\tau|>1$ do

4: Find the pair of $(G_{i},G_{j})\in\tau$ that are closest to each other in
terms of $(l_{i},l_{j})$

5: Implement Algorithm 1 to find the Pareto front $\text{PF}_{i,j}$ between
$(\tilde{M}_{i},\tilde{M}_{j})$

6: Select the $\mathbf{c}^{*}=(c_{i}^{*},c_{j}^{*})\in\mathbb{R}^{2}$ based on
the Pareto front $\text{PF}_{i,j}$

7: Merge the models by
$\bm{\theta}_{\text{merge}}^{i,j}=\bm{\theta}_{\textup{pre}}+c_{i}(\bm{\theta}_{ft}^{i}-\bm{\theta}_{\textup{pre}})+c_{j}(\bm{\theta}_{ft}^{j}-\bm{\theta}_{\textup{pre}})$

8: Calculate the weighted average loss on the two tasks
$l_{ij}=\textit{pref}_{i}l_{i}+\textit{pref}_{j}l_{j}$

9: Update $\tau$ by replacing $\\{G_{i},G_{j}\\}$ with $\\{G_{ij}\\}$, where
$G_{ij}\equiv(\text{task}_{i,j},l_{ij},\bm{\theta}_{\text{merge}}^{i,j})$

10: return $\bm{\theta}_{\text{merge}}^{1,2,\cdots,N}$

\begin{overpic}[width=173.44534pt]{imgs/2D.pdf} \put(-8.0,71.5){(a)}
\end{overpic}

\begin{overpic}[width=216.81pt]{imgs/nestedt.png} \put(-5.0,60.0){(b)}
\end{overpic}

Figure 3: (a) Discretizing of two task scaling coefficients along the angular
dimension in 2D polar coordinate system (please refer to Figure 9 for an
example of 3D spherical discretization.); (b) An example of nested model
merging for $N=6$ models (see more details in Appendix E);

###  3.4 Bayesian adaptive sampling

We have discussed the strategy of bringing down the computation in the sense
of big $O$ notation. It is effective when the number of tasks involved in the
Pareto fronts is high.

In the case of a relatively low number of tasks ($N\leq 4$), we consider using
the Bayesian adaptive sampling method inspired by Bayesian optimization.

In Algorithm 1, we only sample a single round of scaling weights $\mathbf{c}$
and query the ground truth metric by evaluation through the
$M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))$. In contrast, as for the
Bayesian adaptive sampling, we sample the scaling weights $\mathbf{c}$ in
multiple rounds. In each round, the sampling strategy depends on the previous
sampling $\mathbf{c}$ and its evaluation metrics. The process begins with an
initial uniform sampling of scaling coefficients,
$\\{(c_{1},\cdots,c_{N})_{i}\\}_{i=0}^{n_{0}}$, from $[0,1]^{T}$. For
simplicity, we define $\mathbf{c}_{i}$ as $(c_{1},\cdots,c_{N})_{i}$. We
evaluate the merged model $\theta_{m}(\mathbf{c}_{i})$ across tasks $1$ to $N$
and compute the corresponding $L2$ loss. We then discretize the regions of
$\mathbf{c}$ into joint bins within a hyper-spherical coordinate system and
discretize along the angular dimensions. Please refer to figure 9 as examples
in 2-dimensional and 3-dimensional discretization. The posterior distribution
is computed proportional to an acquisition function (e.g., upper confidence
bound) of the approximation loss within specific bins.

We iteratively update each surrogate model for tasks $\\{t\\}_{n=1}^{N}$. See
the algorithm 3 for a simplified version of the process. For more details,
please refer to the LABEL:{alg:BASM} in the appendix. After meeting the
stopping criterion, we use the $N$ surrogate models to generate a lot of
$(\mathbf{c},\\{\tilde{M}_{n}(\theta_{m}(\mathbf{c}))\\}_{n=1}^{N})$ pairs and
apply MOOP algorithm (e.g. NSGA-III) to $\\{\tilde{M}_{n=1}^{N}\\}$ to
calculate the Pareto front.

Algorithm 3 Bayesian Adaptive for Surrogate Model

0: Number of iterations $J$, Buffer $\mathcal{B}$, Pretrained model
$\bm{\theta}_{\textup{pre}}$, Task vectors
$\mathbf{V}=(\mathbf{v}_{1},\cdots,\mathbf{v}_{n})$, Evaluation function
$M_{n}(\cdot)$ for task $n$.

1: Initialize $\mathcal{B}$ to an empty set.

2: for each iteration $j=0$ to $J$ do

3: Sample scaling coefficients $\\{\mathbf{c}_{i}\\}_{i=1}^{n_{j}}$ based on
updated distribution from previous results (uniformly sampled if $j=0$).

4: for each scaling coefficient $i=1$ to $n_{j}$ do

5: Adjust the model with
$\bm{\theta}_{\text{merge}}(\mathbf{c}_{i})=\bm{\theta}_{\textup{pre}}+\mathbf{c}_{i}\cdot\mathbf{V}$.

6: Evaluate this model configuration
$m_{n,i}=M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}_{i}))$ and store
$(\mathbf{c}_{i},m_{n,i})$ in $\mathcal{B}$.

7: Update the surrogate model based on the
$(\mathbf{c},\\{\tilde{M}_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))\\}_{n=1}^{N})$
pairs in $\mathcal{B}$.

8: Estimate acquisition function (UCB) for different model configurations.

9: Adjust the sampling strategy for the next iteration based on these
evaluation metrics.

10: return

##  4 Experiments

In this section, we present our empirical findings across a wide range of
tasks including zero-shot classification (CLIP-based), and LLMs
(Llama3-based).

Through our experiments, we aim to answer the following questions:

  1. Q1

How well do our surrogate quadratic functions approximate the true performance
metric? How well do the amortized Pareto fronts approximate the ground truth
Pareto front?

  2. Q2

For a smaller number of tasks ($N<4$), how many fewer queries would Bayesian
adaptive sampling require compared to the traditional single-shot merging
scheme?

  3. Q3

With identical preferences and computational budgets, how does the performance
of the nested merging scheme compare to that of the traditional single-shot
merging scheme?

###  4.1 Experiment setup

Table 1: Experiment setup in terms of tasks and models Task type | Metric | # of total tasks | Model type
---|---|---|---
Zero-shot Classification (normal) | Accuracy | 8 | ViT-B/32 (CLIP)
Zero-shot Classification (medical) | Accuracy | 2 | ViT-B/32 (CLIP)
Language Generation | Loss / Perplexity | 4 | Llama3-8B
Image Classification | Accuracy | 3 | ResNet-18

#### Datasets and models

We study multi-task model merging on eight normal zero-shot image
classification datasets following ilharco2022editing : SUN397 sun397 , Cars
cars , GTSRB gtsrb , MNIST lecun1998mnist , EuroSAT eurosat , SHVN shvn , DTD
dtd , RESISC45 RESISC45 . We use the ViT-B/32 architecture in CLIP clip as the
pre-trained model for the experiments on vision tasks in the main text. We
show the results of them in the main pages. For the rest of the experiments,
due to the page limits, we show them in the appendix. The result of dataset
and task we experiment on are as follows: a zero-shot medical chest x-ray
image classification tasks to show our model merging scheme also works in a
read world application domain wang2017chestx ; 4 fine-tuned Llama3 models in
different languages: French, Arabic, Chinese, and Japanese. 333All the fine-
tuned language Llama3 models can be found on huggingface. The IDs of the model
are: French: jpacifico/French-Alpaca-Llama3-8B-Instruct-v1.0; Arabic:
MohamedRashad/Arabic-Orpo-Llama-3-8B-Instruct; Chinese: shenzhi-
wang/Llama3-8B-Chinese-Chat; Japanese: haqishen/Llama-3-8B-Japanese-Instruct.;
3 vision tasks on the ResNet18 architecture, CIFAR-10 krizhevsky2009learning ,
Flowers-102 nilsback2008automated , and GTSRB gtsrb .

###  4.2 Baseline and metrics

#### Baseline

Our baseline method for obtaining Pareto fronts is the brute-force direct
search. When the number of tasks is low ($N<4$), we can sample enough grid
points of $\mathbf{c}$ and query the corresponding evaluation metrics
$\\{M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))\\}_{n=1}^{N}$. We can then
directly use the resulting evaluation metrics to find the Pareto front by
direct comparisons of each task performance of the merged model by
$c_{i}\in\mathbf{c}$. When the number of tasks is low, we can regard the
resulting Pareto front as the ground truth Pareto front. However, when the
number of tasks grows, the required number of
$(\mathbf{c},\\{M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))\\}_{n=1}^{N})$
pairs grows exponentially, which is way larger than the points we evaluated.
Thus, when the number of tasks is high ($N\geq 4$), the results from the
brute-force direct search can no longer be considered as ground truth.

#### Win rate

We used the win rate to measure how often the Pareto front found by MAP
outperforms the Pareto front found by the baseline in terms of multiple
objectives. Let $PF_{\text{MAP}}$ and $PF_{\text{baseline}}$ represent the set
of solutions in the Pareto fronts obtained from the MAP and the baseline
methods, respectively. Each solution in these sets is a vector in
$\mathbb{R}^{N}$, where $N$ is the number of objectives or tasks. We sample
$K=\min(100,|PF_{\text{baseline}}|)$ points from each of the two Pareto
fronts, denoted as $\mathbf{c}_{k}^{\text{MAP}}$ and
$\mathbf{c}_{k}^{\text{baseline}},k=1,\ldots,K$. Then, we compare
$M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}_{k}^{\text{MAP}}))$ and
$M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}_{k}^{\text{baseline}}))$ pairwise
for $k=1,\ldots,K$ and $n=1,\ldots,N,$ resulting in $K\times K\times N$
comparisons. The ratio of instances where
$M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}_{k}^{\text{MAP}}))>M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}_{k}^{\text{baseline}}))$
is computed as the win rate of our amortized Pareto front $PF_{\text{MAP}}$.

#### Generational distance and inverted generational distance

We evaluated the quality of the Pareto front in capturing the shape of the
ground truth Pareto front by measuring how much the predicted Pareto front
converges to the ground truth Pareto front by calculating the generational
distance (GD) van1999multiobjective and how much the predicted Pareto front
covers the ground truth Pareto front by calculating the inverted generational
distance (IGD) coello2005solving . GD and IGD are standard measures used in
evolutionary multi-objective optimization to evaluate the solutions found by
the evolutionary algorithms.

Given two solution sets
$PF_{i}=\\{\tilde{M}_{1}^{i}(\bm{\theta}_{\text{merge}}(\mathbf{c})),\ldots,\tilde{M}_{N}^{i}(\bm{\theta}_{\text{merge}}(\mathbf{c}))\\},i=1,2$,
the GD and IGD metrics are defined as
$GD(PF_{1})\equiv\frac{1}{K}\left(\sum_{i=1}^{K}d_{i}^{p}\right)^{1/p}\text{
and
}IGD(PF_{1})\equiv\frac{1}{M}\left(\sum_{i=1}^{M}\tilde{d}_{i}^{p}\right)^{1/p}$
where $d_{i}$ is the minimal Euclidean distance from
$\tilde{M}_{1}^{1}(\bm{\theta}_{\text{merge}}(\mathbf{c}))$ to $PF_{2}$ and
$\tilde{d}_{i}$ is the minimal Euclidean distance from
$\tilde{M}_{1}^{2}(\bm{\theta}_{\text{merge}}(\mathbf{c}))$ to $PF_{1}$.

###  4.3 Win rate of MAP over the direct search method

Our findings indicate that for a small number of tasks ($N<4$), we achieve
similar performance to the ground truth Pareto front with only 30 to 50
evaluation queries of
$(\mathbf{c},{M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))}{n=1}^{N})$ pairs.
However, in scenarios with a higher number of tasks ($N\geq 4$), MAP
significantly outperforms the brute-force (non-ground truth) Pareto solutions.
This is because, as detailed in Section 4.2, the number of required
$(\mathbf{c},{M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))}{n=1}^{N})$ pairs
increases exponentially with the number of tasks. This exponential growth far
exceeds the number of pairs that can be realistically evaluated.

For instance, when $N=3$ and we have 50
$(\mathbf{c},{M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))}_{n=1}^{N})$
pairs, the approximate number of points on the grid line is around
$\sqrt{50}\approx 6.69$. However, when $N$ increases to 8, achieving 5 points
on each grid line would require $5^{8}=390,625$ total points to evaluate,
which is significantly more than the 1,000 points we realistically evaluated.

Table 2: Win rate of the amortized Pareto front and the Pareto front by brute-force direct search. The number of points is the number of points each algorithm used to find the Pareto front. Note that the number of evaluations by each method is the number of points multiplied by the number of tasks. The number of points per dimension is the number of points raised to the power of $\frac{1}{N}$, which measures the sparsity of points the direct search method uses per dimension to approximate the Pareto front. Subscripts denote standard deviations over 3 runs. # of tasks |  # of pts direct search |  # of pts per dim | # of pts (MAP) | Win rate (MAP) |  $R^{2}$ (MAP)
---|---|---|---|---|---
2 |  200 |  14.14 | 30 | 49.81% $(\pm 0.30)$ | 0.953 $(\pm 0.018)$
3 |  300 |  6.69 | 50 | 46.90% $(\pm 0.71)$ | 0.980 $(\pm 0.003)$
4 |  300 |  4.16 | 60 | 50.67% $(\pm 2.44)$ | 0.984 $(\pm 0.004)$
5 |  500 |  3.47 | 85 | 53.00% $(\pm 1.88)$ | 0.941 $(\pm 0.019)$
6 |  500 |  2.82 | 100 | 60.71% $(\pm 1.34)$ | 0.941 $(\pm 0.030)$
7 |  1000 |  2.68 | 140 | 63.42% $(\pm 1.91)$ | 0.891 $(\pm 0.024)$
8 |  1000 |  2.37 | 250 | 65.58% $(\pm 0.94)$ | 0.868 $(\pm 0.028)$

###  4.4 Performance of the quadratic approximation

We further validated the quadratic approximation of the surrogate models and
the true performance by measuring the out-of-sample $R^{2}$. Figure 4 shows
the relationship between the average $R^{2}$ across all tasks and the number
of total points used to fit the quadratic function. As we can see from Figure
4 (a), the average $R^{2}$ values are close to $1$ when the dimension of the
decision space is low ($N<4$) when using around $30$ points. However, as the
dimension of the decision space increases ($N\geq 4)$, the average $R^{2}$
depends more heavily on the number of points (Figure 4 (b)).

\begin{overpic}[width=212.47617pt]{imgs/rsquared1.png} \put(0.0,71.5){(a)}
\end{overpic}

\begin{overpic}[width=212.47617pt]{imgs/rsquare2.png} \put(0.0,71.5){(b)}
\end{overpic}

Figure 4: (a) An example of uncertainty in 2D polar coordinate system. The
more uncertain within a bin, the more
$(\mathbf{c},\\{M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c}))\\}_{n=1}^{N})$
pairs information we should collect in the next round. (b) An illustration of
discretization of a 3D spherical coordinate system. When the dimension is
higher, the discretization would be in a hyper-spherical coordinate system
along with the angular dimensions.

###  4.5 Bayesian adaptive sampling algorithm

We further improve the efficiency of MAP by proposing an adaptive Bayesian
sampling algorithm. This Bayesian approach samples the points from regions
with the highest level of uncertainty, where uncertainty is quantified with
the Upper confidence bound (UCB).

Below, we define points (pts) as scaling coefficients and evaluation metrics
of the corresponding merged models.

All of these experiments are initialized with 6 pairs of
$\mathbf{c},\\{M_{n}\\}_{n=1}^{N}$ (iter 0). In every following iteration, we
sample more points following the Bayesian adaptive sampling algorithm. We
compare the Bayesian adaptive sampling beginning with 6 points and adding 3
additional points (6+3 pts) with running Algorithm 1 with 9 points in a row.
We also compare the Bayesian adaptive sampling beginning with 6 points and
adding 3 additional points 2 times (6+2$\times$3 pts) with running Algorithm 1
with 12 points in a row.

We show that, utilizing the same number of points, Bayesian adaptive sampling
performs better than the run-in-a-row scheme in Algorithm 1. The metrics in
Figure 7 are average numbers over 7 experiments in different datasets. Please
refer to Table 7 for detailed results in every experiment.

Table 3: Results obtained using Bayesian adaptive sampling using 3 iterations. The initial number of points is 6, and we sample an additional 3 points using the Bayesian adaptive sampling method. The “init $n$” shows the metrics when we use $n$ points to calculate the amortized Pareto front in a single row. Subscripts denote standard deviations over 6 runs. | Iter 0 (6 pts) | Iter 1 (6+3 pts) | Init 9 | Iter 2 (6+3$\times$2 pts) | Init 12
---|---|---|---|---|---
GD ($\downarrow$) | $0.234_{0.154}$ | $\mathbf{0.11_{0.085}}$ | $0.118_{0.106}$ | $\mathbf{0.079_{0.062}}$ | $0.091_{0.082}$
IGD ($\downarrow$) | $0.124_{0.118}$ | $\mathbf{0.047_{0.082}}$ | $0.067_{0.09}$ | $0.038_{0.053}$ | $\mathbf{0.034_{0.037}}$
GD+IGD ($\downarrow$) | $0.357_{0.211}$ | $\mathbf{0.158_{0.137}}$ | $0.185_{0.165}$ | $\mathbf{0.118_{0.08}}$ | $0.125_{0.101}$
$R^{2}_{0}$ ($\uparrow$) | $-2.237_{3.792}$ | $\mathbf{-0.103_{2.218}}$ | $-0.194_{1.675}$ | $\mathbf{0.459_{0.784}}$ | $0.44_{0.902}$
$R^{2}_{1}$ ($\uparrow$) | $-1.186_{2.291}$ | $\mathbf{0.342_{0.959}}$ | $0.165_{1.33}$ | $\mathbf{0.428_{0.844}}$ | $0.409_{0.27}$

\begin{overpic}[width=212.47617pt]{imgs/0_6_3_plot.png} \put(0.0,60.5){(a)}
\end{overpic}

\begin{overpic}[width=212.47617pt]{imgs/1_6_3_plot.png} \put(0.0,60.5){(b)}
\end{overpic}

Figure 5: (a) This plot shows a failure case of amortized Pareto front when we
only have 6 initial randomly sampled pairs of
$(\mathbf{c},\\{M_{i}(\theta_{m}(\mathbf{c}))\\}_{i=1}^{N})$ (b) After one
iteration of Bayesian adaptive sampling for 3 more pairs (9 in total), our
amortized Pareto front much better than the previous one.

###  4.6 Reduction of the number of models merged simultaneously

We performed nested model merging on four tasks and compared its performance
with merging four tasks directly. When merging two models, we require that all
models should achieve 70% of the single-task fine-tuned model, while
maximizing the performance on the first task. We note that even though we
require that all models should achieve 70% of the single-task fine-tuned
model, the nested merging method can only achieve 60% of the single-task fine-
tuned models during the final combine. Therefore, in Table 4, we report the
results when we require achieving at least 60% of each task’s single-task
fine-tuned model. From the Table 4, we can conclude that even if the nested
merging scheme needs way fewer queries of evaluation metric calculations
compared to directly merging 4 models, it is still capable of recovering more
than 80 percent performances of directly merging 4 models and sometimes even
higher than the directly merging scheme. The direct merging approach uses $80$
evaluation queries, while the nested merging uses $20$ evaluation queries in
each round of merging.

Table 4: Accuracy on four tasks when using nested merging vs direct merging. We first merge models 1 and 2, and models 3 and 4 in parallel, using the preference that requires all tasks to have a normalized performance of at least 70% while optimizing the performance on tasks (1 and 3). We then compute the Pareto front for the two combined models. The table shows the highest accuracies on each task, while requiring all tasks to achieve a normalized performance of 65%. Subscripts denote standard deviations over 10 runs. | SUN397 (1) | DTD (2) | GTSRB (3) | Cars (4)
---|---|---|---|---
Nested merging | $\mathbf{73.24_{1.03}}$ | $50.69_{1.67}$ | $96.26_{0.31}$ | $56.20_{3.46}$
Directly merge 4 models | $68.36_{2.63}$ | $\mathbf{61.70_{6.78}}$ | $\mathbf{98.97_{0.41}}$ | $\mathbf{68.24_{3.38}}$
Performance recovering | 107% | 82.2% | 97.3% | 82.4%

##  5 Conclusion and Limitations

Our method (MAP) can serve as an out-of-box plug-in that can easily combine
with other model merging methods, including but not limited to linear merging
model wortsman2022model and tasks arithmetic ilharco2022editing . From the
Section 3 and Section 4, we have shown that our method Algorithm 1, Algorithm
2, Algorithm 3 can efficiently bring down the computational cost from
$O(N\cdot 2^{N})$ to $O(N\cdot\log_{2}{N})$, which are even less costly in the
parameter-efficient training (e.g. LoRA). However, we would like to point out
some limitations of our method. First, during the design of the Algorithm 1,
we do not deal with the situation of the non-convex Pareto front. In the case
of 2 tasks, most likely the Pareto fronts with proper trade-offs would have a
convex Pareto front, but if we deal with more tasks, it is very likely that
the ground truth Pareto fronts are non-convex and we will end up with
approximating a convex hull with Algorithm 1. A quick but naive fix would be
to implement Algorithm 2 in this case so that the Pareto fronts between 2
tasks would be more likely to be convex. Second, we don’t have a detector
algorithm to detect if 2 tasks have proper trade-offs. Trying to approximate a
Pareto front with only one Pareto solution inside will result in very unstable
and bad-perform results. The practitioners should be informed in this case.

## References

  * [1] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In International conference on machine learning, pages 242–252. PMLR, 2019.
  * [2] Anne Auger, Johannes Bader, Dimo Brockhoff, and Eckart Zitzler.  Theory of the hypervolume indicator: optimal $\mu$-distributions and the choice of the reference point.  In Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, pages 87–102, 2009.
  * [3] Oscar Brito Augusto, Fouad Bennis, Stephane Caro, et al.  Multiobjective optimization involving quadratic functions.  Journal of optimization, 2014, 2014.
  * [4] Nicola Beume, Boris Naujoks, and Michael Emmerich.  Sms-emoa: Multiobjective selection based on dominated hypervolume.  European Journal of Operational Research, 181(3):1653–1669, 2007.
  * [5] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901, 2020.
  * [6] Zhiqi Bu, Xinwei Zhang, Mingyi Hong, Sheng Zha, and George Karypis.  Pre-training differentially private models with limited public data.  arXiv preprint arXiv:2402.18752, 2024.
  * [7] Sébastien Bubeck et al.  Convex optimization: Algorithms and complexity.  Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015.
  * [8] Gong Cheng, Junwei Han, and Xiaoqiang Lu.  Remote sensing image scene classification: Benchmark and state of the art.  Proceedings of the IEEE, 105(10):1865–1883, 2017.
  * [9] Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  Advances in neural information processing systems, 32, 2019.
  * [10] Mircea Cimpoi, Subhransu Maji, Iasonas Kokkinos, Sammy Mohamed, and Andrea Vedaldi.  Describing textures in the wild.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3606–3613, 2014.
  * [11] Carlos A Coello Coello and Nareli Cruz Cortés.  Solving multiobjective optimization problems using an artificial immune system.  Genetic programming and evolvable machines, 6:163–190, 2005.
  * [12] Haotian Cui, Chloe Wang, Hassaan Maan, Kuan Pang, Fengning Luo, Nan Duan, and Bo Wang.  scgpt: toward building a foundation model for single-cell multi-omics using generative ai.  Nature Methods, pages 1–11, 2024.
  * [13] Kalyanmoy Deb and Himanshu Jain.  An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints.  IEEE transactions on evolutionary computation, 18(4):577–601, 2013.
  * [14] Kalyanmoy Deb, Manikanth Mohan, and Shikhar Mishra.  Towards a quick computation of well-spread pareto-optimal solutions.  In Evolutionary Multi-Criterion Optimization: Second International Conference, EMO 2003, Faro, Portugal, April 8–11, 2003. Proceedings 2, pages 222–236. Springer, 2003.
  * [15] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [16] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai.  Gradient descent finds global minima of deep neural networks.  In International conference on machine learning, pages 1675–1685. PMLR, 2019.
  * [17] Saeed Ghadimi and Guanghui Lan.  Stochastic first-and zeroth-order methods for nonconvex stochastic programming.  SIAM journal on optimization, 23(4):2341–2368, 2013.
  * [18] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [19] Patrick Helber, Benjamin Bischke, Andreas Dengel, and Damian Borth.  Eurosat: A novel dataset and deep learning benchmark for land use and land cover classification.  IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 12(7):2217–2226, 2019.
  * [20] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al.  Training compute-optimal large language models.  arXiv preprint arXiv:2203.15556, 2022.
  * [21] Evan J Hughes.  Evolutionary many-objective optimisation: many once or one many?  In 2005 IEEE congress on evolutionary computation, volume 1, pages 222–227. IEEE, 2005.
  * [22] Gabriel Ilharco, Marco Tulio Ribeiro, Mitchell Wortsman, Suchin Gururangan, Ludwig Schmidt, Hannaneh Hajishirzi, and Ali Farhadi.  Editing models with task arithmetic.  arXiv preprint arXiv:2212.04089, 2022.
  * [23] Moksh Jain, Emmanuel Bengio, Alex Hernández-García, Jarrid Rector-Brooks, Bonaventure F. P. Dossou, Chanakya Ajit Ekbote, Jie Fu, Tianyu Zhang, Michael Kilgour, Dinghuai Zhang, Lena Simine, Payel Das, and Yoshua Bengio.  Biological sequence design with gflownets.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 9786–9801. PMLR, 2022.
  * [24] Moksh Jain, S. Raparthy, Alex Hernández-García, Jarrid Rector-Brooks, Y. Bengio, Santiago Miret, and Emmanuel Bengio.  Multi-objective gflownets.  International Conference on Machine Learning, 2022.
  * [25] Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, Gianna Lengyel, Guillaume Bour, Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie-Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang, Szymon Antoniak, Teven Le Scao, Théophile Gervet, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed.  Mixtral of experts.  arXiv preprint arXiv: 2401.04088, 2024.
  * [26] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models.  arXiv preprint arXiv:2001.08361, 2020.
  * [27] Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei.  3d object representations for fine-grained categorization.  In Proceedings of the IEEE international conference on computer vision workshops, pages 554–561, 2013.
  * [28] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [29] Yann LeCun.  The mnist database of handwritten digits.  http://yann. lecun. com/exdb/mnist/, 1998.
  * [30] Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing-Fu Zhang, and Sam Kwong.  Pareto multi-task learning.  Advances in neural information processing systems, 32, 2019.
  * [31] Michael S Matena and Colin A Raffel.  Merging models with fisher-weighted averaging.  Advances in Neural Information Processing Systems, 35:17703–17716, 2022.
  * [32] Sam McCandlish, Jared Kaplan, Dario Amodei, and OpenAI Dota Team.  An empirical model of large-batch training.  arXiv preprint arXiv:1812.06162, 2018.
  * [33] Henry B. Moss, David S. Leslie, Daniel Beck, Javier Gonzalez, and Paul Rayson.  Boss: Bayesian optimization over string spaces.  In Advances in Neural Information Processing Systems, 2020.
  * [34] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Baolin Wu, Andrew Y Ng, et al.  Reading digits in natural images with unsupervised feature learning.  In NIPS workshop on deep learning and unsupervised feature learning, volume 2011, page 7. Granada, Spain, 2011.
  * [35] Maria-Elena Nilsback and Andrew Zisserman.  Automated flower classification over a large number of classes.  In 2008 Sixth Indian conference on computer vision, graphics & image processing, pages 722–729. IEEE, 2008.
  * [36] National Institutes of Health et al.  Nih clinical center provides one of the largest publicly available chest x-ray datasets to scientific community, 2017.
  * [37] E. O. Pyzer-Knapp.  Bayesian optimization for accelerated drug discovery.  IBM Journal of Research and Development, 62(6):2:1–2:7, 2018.
  * [38] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In International conference on machine learning, pages 8748–8763. PMLR, 2021.
  * [39] Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, Jérémy Rapin, Artyom Kozhevnikov, Ivan Evtimov, Joanna Bitton, Manish Bhatt, Cristian Canton Ferrer, Aaron Grattafiori, Wenhan Xiong, Alexandre Défossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve.  Code llama: Open foundation models for code.  arXiv preprint arXiv: 2308.12950, 2023.
  * [40] Ozan Sener and Vladlen Koltun.  Multi-task learning as multi-objective optimization.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * [41] Johannes Stallkamp, Marc Schlipsing, Jan Salmen, and Christian Igel.  The german traffic sign recognition benchmark: a multi-class classification competition.  In The 2011 international joint conference on neural networks, pages 1453–1460. IEEE, 2011.
  * [42] Hui Su, Zhi Tian, Xiaoyu Shen, and Xunliang Cai.  Unraveling the mystery of scaling laws: Part i.  arXiv preprint arXiv:2403.06563, 2024.
  * [43] Kei Terayama, Masato Sumita, Ryo Tamura, and Koji Tsuda.  Black-box optimization for automated discovery.  Accounts of Chemical Research, XXXX, 02 2021.
  * [44] Arun James Thirunavukarasu, Darren Shu Jeng Ting, Kabilan Elangovan, Laura Gutierrez, Ting Fang Tan, and Daniel Shu Wei Ting.  Large language models in medicine.  Nature medicine, 29(8):1930–1940, 2023.
  * [45] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom.  Llama 2: Open foundation and fine-tuned chat models.  arXiv preprint arXiv: 2307.09288, 2023.
  * [46] David Allen Van Veldhuizen.  Multiobjective evolutionary algorithms: classifications, analyses, and new innovations.  Air Force Institute of Technology, 1999.
  * [47] Xiaosong Wang, Yifan Peng, Le Lu, Zhiyong Lu, Mohammadhadi Bagheri, and Ronald M Summers.  Chestx-ray8: Hospital-scale chest x-ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases.  In Proceedings of the IEEE conference on computer vision and pattern recognition, 2017.
  * [48] James T. Wilson, Riccardo Moriconi, Frank Hutter, and Marc Peter Deisenroth.  The reparameterization trick for acquisition functions, 2017.
  * [49] Michael Wornow, Rahul Thapa, Ethan Steinberg, Jason Fries, and Nigam Shah.  Ehrshot: An ehr benchmark for few-shot evaluation of foundation models.  2023\.
  * [50] Mitchell Wortsman, Gabriel Ilharco, S. Gadre, R. Roelofs, Raphael Gontijo-Lopes, Ari S. Morcos, Hongseok Namkoong, Ali Farhadi, Y. Carmon, Simon Kornblith, and Ludwig Schmidt.  Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time.  International Conference on Machine Learning, 2022.
  * [51] Mitchell Wortsman, Gabriel Ilharco, Jong Wook Kim, Mike Li, Simon Kornblith, Rebecca Roelofs, Raphael Gontijo Lopes, Hannaneh Hajishirzi, Ali Farhadi, Hongseok Namkoong, et al.  Robust fine-tuning of zero-shot models.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 7959–7971, 2022.
  * [52] Yusong Wu, Ke Chen, Tianyu Zhang, Yuchen Hui, Taylor Berg-Kirkpatrick, and Shlomo Dubnov.  Large-scale contrastive language-audio pretraining with feature fusion and keyword-to-caption augmentation.  In IEEE International Conference on Acoustics, Speech and Signal Processing ICASSP 2023, Rhodes Island, Greece, June 4-10, 2023, pages 1–5. IEEE, 2023.
  * [53] Jianxiong Xiao, Krista A Ehinger, James Hays, Antonio Torralba, and Aude Oliva.  Sun database: Exploring a large collection of scene categories.  International Journal of Computer Vision, 119:3–22, 2016.
  * [54] Prateek Yadav, Derek Tam, Leshem Choshen, Colin A Raffel, and Mohit Bansal.  Ties-merging: Resolving interference when merging models.  Advances in Neural Information Processing Systems, 36, 2024.
  * [55] Enneng Yang, Zhenyi Wang, Li Shen, Shiwei Liu, Guibing Guo, Xingwei Wang, and Dacheng Tao.  Adamerging: Adaptive model merging for multi-task learning.  arXiv preprint arXiv:2310.02575, 2023.
  * [56] Xiaohua Zhai, Basil Mustafa, Alexander Kolesnikov, and Lucas Beyer.  Sigmoid loss for language image pre-training.  IEEE International Conference on Computer Vision, 2023.

##  Appendix A Related Work

#### Multi-objective optimization

Multi-objective optimization (MOOP) aims at identifying a variety of Pareto
solutions, each offering different trade-offs, instead of just a single
solution. In fact, the multi-task problem is approached from a MOOP view point
sener2018multi ; lin2019pareto , which leverages a rich literature of
algorithms including MGDA, IMTL, GradNorm, RLW, PCGrad, scalarization, and so
on. We note these training algorithms iteratively optimize over the
$\mathbb{R}^{d}$ model parameters and can be computationally costly (in order
to instantiate and modify the per-task gradient). In contrast, our algorithm
is a post-training MOOP over the $\mathbb{R}^{N}$ scaling coefficients, which
is significantly low-compute.

Many methods have been proposed to solve MOOP and derive the Pareto optimal
solutions. One may leverage the scalarization technique to transform a multi-
objective problem into many single-objective ones, aiming to find one solution
for each problem and approximate the Pareto front. Additionally, one can solve
the Karush-Kuhn-Tucker conditions, which are easy to work with, given that
$\mathbf{c}^{*}$ has a closed form under our quadratic approximation. Another
approach is to use evolutionary algorithms, a major branch of bio-inspired
search heuristics widely applied.

In order to select an appropriate MOOP algorithm, we need to take into account
the computational costs and the quality of the Pareto front. For instance,
many indicator-based and selection-based methods (e.g. the hypervolume
indicator auger2009theory ) have a time complexity that grows super-
polynomially with the number of objectives. Indeed, for $N\geq 3$, the MOOP is
termed as the many-objective optimization, which is significantly challenging
for well-established algorithms (e.g. NSGA-II and SPEA2) and requires more
advanced algorithms such as $\epsilon$-MOEA deb2003towards , MSOPS
hughes2005evolutionary , SMS-EMOA beume2007sms , and NSGA-III
deb2013evolutionary , or the KKT approach augusto2014multiobjective .

#### Task arithmetic

Task arithmetic, a method of model merging that has drawn increasing
attention, applies a weighted average of models (controlled by the scaling
coefficients) to obtain high performance on multiple tasks simultaneously.
Several existing works have studied ways to select the scaling coefficients
ilharco2022editing ; yadav2024ties ; yang2023adamerging : ilharco2022editing
simply uses equal scaling, similar to Model Soup paper, which is heuristic and
sub-optimal, plus the applicability is limited to certain tasks and small
scales; yang2023adamerging aims to learn the optimal scaling weights by using
the Shannon entropy as a surrogate objective function to the cross entropy
loss. However, it requires the use of unlabeled test data from all tasks. In
most real-world applications, data cannot be directly shared, which is what
makes model merging appealing initially matena2022fishermerging . In addition,
such an approach only works for classification tasks due to the use of cross-
entropy loss.

wortsman2022robust proposed “WiSE-FIT” to perform robust fine-tuning by
computing the weighted average of the pre-trained model parameters with the
parameters of the models fine-tuned on different tasks, with different weights
determining different trade-offs between pre-training and fine-tuning task
performance. Task Arithmetic ilharco2022editing adds the weighted sum of the
differences between the fine-tuned model and the pre-trained model to the
weights of the pre-trained model. Again, the weights are used to distinguish
the importance of various models.

#### Second-order Taylor expansion

In deep learning, the second-order Taylor expansion and thus the quadratic
approximation on the evaluation metric is an important technique, that
characterizes the metric landscape. For example, the Newton-Ralphson method is
derived from it:
$\mathbf{w}_{t}-\mathbf{w}_{t+1}=\mathbf{H}^{-1}\mathbf{G}=\text{argmin}_{\mathbf{v}}M(\mathbf{w}_{t}-\mathbf{v})$
given that
$M(\mathbf{w}_{t}-\mathbf{v})=M(\mathbf{w}_{t})-\mathbf{v}\mathbf{G}+\frac{1}{2}\mathbf{v}^{\top}\mathbf{H}\mathbf{v}$.
The quadratic approximation is also combined with Lipschitz smoothness ($L$)
in the classic convergence analysis of SGD bubeck2015convex ;
ghadimi2013stochastic , through $M(\mathbf{w}_{t}-\eta\mathbf{G})\leq
M(\mathbf{w}_{t})-\eta||\mathbf{G}||^{2}+\frac{L\eta^{2}}{2}||\mathbf{G}||^{2}$.
Interestingly, although the approximation is only accurate in the local
neighborhood, it can be used to indicate the global convergence over the
iterations. One reason is that state-of-the-art neural networks are usually
over-parameterized and go through lazy training, meaning that the converging
parameters are close to the initialization chizat2019lazy ; du2019gradient ;
allen2019convergence , and thus the local approximation informs on the global
convergence behavior. In particular, this approximation has played important
roles in the scaling laws of neural networks (e.g. Equation 3.3 in
su2024unraveling ), that predict the performance and select the
hyperparameters before the training actually takes place.

#### Federated/Private Learning

Because the model merging is a post-training approach, it can be naturally
used in federated learning, which protects both the model privacy and data
privacy. To be specific, for the data privacy, the only operation that
requires the data is line 6 in Algorithm 1, where each dataset can be kept at
one site without sharing with other sites: the $i$-th site holding its own
data will take in the model $\bm{\theta}(\mathbf{c})$ and only share
$M_{n}(\bm{\theta}(\mathbf{c}))\in\mathbb{R}$; for the model privacy, the only
operator that requires an aggregation is line 5 in Algorithm 1, where each
model can be kept at one site and the aggregation is privacy-preserving using
a safe center site, or the secure multi-party computation without a center
site.

#### Multi-Task Learning

Multi-task learning (MTL) algorithms are designed to enhance the performance
of several related tasks by learning them concurrently. These algorithms
typically build a shared parameter representation to integrate multiple tasks.
Although, the primary emphasis of most MTL algorithms is on developing shared
representations, with less attention given to balancing the trade-offs between
different tasks. Existing multitask learning strategies achieve this by
computing a set of Pareto optimal solutions lin2019pareto ; sener2018multi ;
jain2022multiobjective , yet they still require extensive and expensive
training.

#### Bayesian Optimization

Bayesian optimization has been widely used in scenarios that require efficient
exploration of parameter spaces, particularly when evaluating the performance
of each configuration is costly or time-consuming. This method is especially
advantageous in machine learning and hyperparameter tuning, where traditional
optimization techniques may be computationally prohibitive. Popular Bayesian
optimization methods and applications are wilson2017reparameterization ;
bioGFN ; moss2020bayesian ; bayes4DD ; bayesDD2 .

##  Appendix B Nested merging scheme

Table 5: Computational cost of model merging for $N$ models. | # evals per task | minimum # evals (total) | # evals (total)
---|---|---|---
Naive model merging | $O(N^{2})$ | $O(N^{3})$ | $O(N\cdot 2^{N})$
Nested model merging | $O(1)$ | $O(N\log_{2}^{N})$ | $O(N\log_{2}^{N})$

To estimate the computational complexity, we $N/2\times
2+\cdots+N/{2^{m}}\times 2^{m}=O(N\log_{2}^{N})$ where $2^{m-1}<N\leq 2^{m}$.

In our experiments, we explored the strategy of decomposing tasks into pairs,
identifying the Pareto front for each pair, and then sequentially merging
these binary-combined models two at a time. Our goal was to determine if this
incremental merging approach affects performance negatively when compared to
merging multiple models in a single operation.

The results are summarized in the table below, which compares the outcomes of
merging four models using both the nested merging approach and the direct
merging approach. In the nested merging method, we initially merged the pairs
SUN397 with DTD and GTSRB with Cars to form two combined models. Each
objective metric was weighted equally at 0.5, and the optimal combinations
were selected from the Pareto fronts to create the two preliminary merged
models. These were subsequently merged into a final model. In contrast, the
direct merging approach combines all four models simultaneously.

Contrary to our expectations, the performance of the nested merging approach
was comparable to that of merging all four models at once. However, a
potential disadvantage of the nested approach is that it does not allow the
practitioners to explore the Pareto front as thoroughly as the direct merging
method. Nevertheless, the nested merging strategy could be advantageous for
practitioners who prefer to work with a predefined weighting scheme for
different objectives.

We also want to mention that, in the Algorithm 2, for simplicity of
illustration, we use a preference weight as an example of preference
representation. However, preference can be complex and interdependent on
multiple tasks. In these complex scenarios, the number of tasks in each
cluster does not need to be two because it is necessary to group
interdependent tasks within the same cluster. For example, consider a case
where the total number of tasks $N$ is four, and the user preference is
specified as follows: If $M_{1}>\frac{1}{2}(M_{2}+M_{3})$, then maximize
$M_{1}$ \+ $M_{4}$. Otherwise, maximize $\frac{1}{2}(M_{2}+M_{3})+M_{4}$.
$M_{n}$ is the metric of task $N$. In this case, preferences of task 1, 2 and
3 are interdependent. Thus, we have to put them into the same cluster. In
extreme cases, where all tasks are interdependent based on the given
preferences, it is necessary to group all tasks into a single cluster. This
scenario causes the nested merging algorithm to degenerate into the algorithm
1.

##  Appendix C Proof: Negligibility of the Remainder in Multivariate Taylor
Series

#### Corollary: Accurate Local Approximation by Taylor Expansion

If $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is $(k+1)$ times continuously
differentiable in a neighborhood around a point $a\in\mathbb{R}^{n}$, then the
Taylor polynomial $T_{k}(x)$ of order $k$ provides an accurate approximation
of $f(x)$ when $x$ is sufficiently close to $a$. Furthermore, the remainder
term $R_{k}(x)$ becomes negligibly small as $||x-a||$ approaches zero,
assuming that the $(k+1)$th derivatives of $f$ are bounded by a constant $M$
in the neighborhood between $a$ and $x$.

#### Proof

Consider the Taylor series expansion of $f$ around the point $a$, truncated at
order $k$:

$T_{k}(x)=\sum_{|\alpha|\leq k}\frac{D^{\alpha}f(a)}{\alpha!}(x-a)^{\alpha}$

where $\alpha$ is a multi-index of non-negative integers, $D^{\alpha}f(a)$
denotes the partial derivatives of $f$ at $a$ corresponding to $\alpha$, and
$(x-a)^{\alpha}=(x_{1}-a_{1})^{\alpha_{1}}\cdots(x_{n}-a_{n})^{\alpha_{n}}$.

#### Assumptions

  1. 1.

Proximity: $\|x-a\|\rightarrow 0$ where $\|\cdot\|$ denotes the Euclidean norm
in $\mathbb{R}^{n}$.

  2. 2.

Bounded Derivatives: There exists a constant $M$ such that for all multi-
indices $\alpha$ with $|\alpha|\equiv k+1$, the norm of the tensor
$D^{\alpha}f$ evaluated at any point $\xi$ between $a$ and $x$ is bounded by
$M$.

$\|D^{\alpha}f(\xi)\|=\sup_{\|v_{1}\|=1,\ldots,\|v_{k+1}\|=1}|D^{\alpha}f(\xi)(v_{1},\ldots,v_{k+1})|\leq
M$

The remainder term of the Taylor series expansion is given by:

$R_{k}(x)=\sum_{|\alpha|=k+1}\frac{D^{\alpha}f(\xi)}{\alpha!}(x-a)^{\alpha}$

Given the assumptions, we estimate:

$|R_{k}(x)|\leq\sum_{|\alpha|=k+1}\frac{\|D^{\alpha}f(\xi)\|}{\alpha!}\|x-a\|^{k+1}\leq\sum_{|\alpha|=k+1}\frac{M}{\alpha!}\|x-a\|^{k+1}$

As $\|x-a\|\rightarrow 0$, the term $\|x-a\|^{k+1}$ goes to zero. Thus, the
remainder term $R_{k}(x)$ becomes arbitrarily small, making it negligible.

In conclusion, under the stated assumptions, the Taylor series truncated at
order $k$, $T_{k}(x)$, provides an accurate approximation of $f(x)$ near $a$,
and the remainder $R_{k}(x)$ can be ignored as $\|x-a\|\rightarrow 0$ and the
higher-order derivatives remain bounded by $M$.

##  Appendix D Additional Experiment Results

###  D.1 Zero-shot Medical Image Classification

In addition to natural images, we used another dataset consisting of over
112,000 chest X-rays and 30,000 unique patients national2017nih . It
originally contained 15 classes (14 diseases and 1 class for no finding). We
split the dataset into two groups, where medical task 1 specifically tries to
classify Atelectasis, Consolidation, Infiltration, Pneumothorax, and medical
task 2 tries to classify Nodule, Mass and Hernia. An example image taken from
the dataset is shown in Figure 6 (a).

\begin{overpic}[width=130.08731pt]{imgs/medical_raw.png} \put(0.0,105.5){(a)}
\end{overpic}

\begin{overpic}[width=260.17464pt]{imgs/medical_30_points.png}
\put(0.0,60.5){(b)} \end{overpic}

Figure 6: (a) Example figure from the NIH national2017nih dataset. (b) Pareto
fronts found by brute-force direct search using 400 points and by MAP using 30
points. We randomly sampled 25 points from the predicted Pareto front by MAP.
The resulting IGD is 0.016, and GD is 0.014.

###  D.2 Merging language model

We merged French and Arabic, as well as Chinese and Japanese. Please refer to
Table 6 and Figure 7. As we can see, the ground truth Pareto front is not in
good shape. There are only a few points on the ground truth Pareto fronts
which means few merged models could dominate the rest and the trade-off
between the metrics of different languages might not be very significant. Even
under this condition, our algorithm is still able to find out the Pareto
fronts. We further try to merge ‘Arabic+French’ and ‘Chinese+Japanese’ in the
nested scheme, Algorithm 2 with various preferences. However, the Pareto front
usually only contains a single model which prevents us from predicting a
Pareto front.

Table 6: Llama-3 fine-tuned models merging | GD | IGD | GD+IGD
---|---|---|---
Arabic+French | $0.023_{0.010}$ | $0.035_{0.018}$ | $0.058_{0.028}$
Chinese+Japanese | $0.014_{0.013}$ | $0.028_{0.017}$ | $0.041_{0.026}$

\begin{overpic}[width=180.67499pt]{imgs/ar_fr_ar_fr_ar_fr_plot.png}
\put(0.0,71.5){(a)} \end{overpic}

\begin{overpic}[width=180.67499pt]{imgs/zh_ja_zh_ja_zh_ja_plot.png}
\put(0.0,71.5){(b)} \end{overpic}

Figure 7: (a) Amortized Pareto front on merging Llama-3 fine-tuned on French
with Llama-3 fine-tuned on Arabic; (b) Amortized Pareto front on merging
Llama-3 fine-tuned on Chinese with Llama-3 fine-tuned on Japanese

###  D.3 Bayesian adaptive sampling experiments detail

Please refer to Table 7 as the detailed experiments result for Bayesian
adaptive sampling. The very left column shows the name of the 2 tasks being
merged. Below, we define points (pts) as scaling coefficients and evaluation
metrics of the corresponding merged models.

All of these experiments are initialized with 6 pairs of
$\mathbf{c},\\{M_{n}\\}_{n=1}^{N}$ (iter 0). In every following iteration, we
sample more points following the Bayesian adaptive sampling algorithm. We
compare the Bayesian adaptive sampling beginning with 6 points and adding 3
additional points (6+3 pts) with running Algorithm 1 with 9 points in a row.
We also compare the Bayesian adaptive sampling beginning with 6 points and
adding 3 additional points for 2 times (6+2 $\times$ 3 pts) with running
Algorithm 1 with 12 points in a row. We show that, under most cases, utilizing
the same number of points, Bayesian adaptive sampling performs better than the
run-in-a-row scheme in Algorithm 1.

Table 7: Detailed experiments using Bayesian adaptive sampling. In ‘Iter 0, 6
pts’, the method starts with an initial set of 6 points. In ‘Iter 1, 6+3 pts’,
the method begins with 6 points and adds 3 additional points based on the
Bayesian adaptive sampling results from the previous iteration. ‘Iter 2, 6+3
pts’ follows the same procedure as ‘Iter 1, 6+3 pts’. In ‘Init $n$’, the
experiment runs the Algorithm 1 with $n$ points in a row.

| GD | IGD | GD+IGD | $R^{2}_{1}$ | $R^{2}_{2}$
---|---|---|---|---|---
DTD+Cars (Iter 0, 6 pts) | $0.265_{0.16}$ | $0.213_{0.161}$ | $0.478_{0.251}$ | $-2.708_{4.513}$ | $-1.774_{2.791}$
DTD+Cars (Iter 1, 6+3 pts) | $0.195_{0.133}$ | $0.109_{0.172}$ | $0.303_{0.273}$ | $-1.475_{3.769}$ | $0.576_{0.73}$
DTD+Cars (Iter 2, 6+2*3 pts) | $0.1_{0.076}$ | $0.018_{0.008}$ | $0.118_{0.075}$ | $0.489_{0.647}$ | $0.902_{0.113}$
DTD+Cars (Init 9) | $0.086_{0.085}$ | $0.024_{0.014}$ | $0.11_{0.085}$ | $0.606_{0.497}$ | $0.85_{0.144}$
DTD+Cars (Init 12) | $0.099_{0.117}$ | $0.034_{0.025}$ | $0.132_{0.113}$ | $0.742_{0.148}$ | $0.922_{0.078}$
DTD+RESISC45 (Iter 0, 6 pts) | $0.178_{0.054}$ | $0.111_{0.129}$ | $0.289_{0.175}$ | $-2.677_{5.195}$ | $0.359_{0.694}$
DTD+RESISC45 (Iter 1, 6+3 pts) | $0.067_{0.062}$ | $0.051_{0.027}$ | $0.118_{0.059}$ | $0.715_{0.2}$ | $0.003_{0.717}$
DTD+RESISC45 (Iter 2, 6+2*3 pts) | $0.049_{0.05}$ | $0.052_{0.035}$ | $0.101_{0.049}$ | $0.813_{0.088}$ | $0_{0.74}$
DTD+RESISC45 (9) | $0.092_{0.084}$ | $0.018_{0.008}$ | $0.11_{0.089}$ | $0.7_{0.389}$ | $0.351_{1.101}$
DTD+RESISC45 (Init 12) | $0.056_{0.048}$ | $0.026_{0.013}$ | $0.082_{0.039}$ | $0.796_{0.079}$ | $0.801_{0.222}$
EuroSAT+RESISC45 (Iter 0, 6 pts) | $0.279_{0.137}$ | $0.061_{0.047}$ | $0.341_{0.178}$ | $-4.381_{4.102}$ | $-1.028_{1.668}$
EuroSAT+RESISC45 (Iter 1, 6+3 pts) | $0.154_{0.069}$ | $0.019_{0.012}$ | $0.173_{0.066}$ | $-1.888_{2.977}$ | $0.557_{0.224}$
EuroSAT+RESISC45 (Iter 2, 6+2*3 pts) | $0.148_{0.051}$ | $0.056_{0.076}$ | $0.204_{0.077}$ | $-1.085_{0.896}$ | $0.513_{0.215}$
EuroSAT+RESISC45 (Init 9) | $0.147_{0.084}$ | $0.075_{0.092}$ | $0.222_{0.134}$ | $-1.419_{2.475}$ | $0.213_{0.75}$
EuroSAT+RESISC45 (Init 12) | $0.182_{0.099}$ | $0.059_{0.076}$ | $0.242_{0.166}$ | $-0.722_{1.182}$ | $0.724_{0.275}$
GTSRB+Cars (Iter 0, 6 pts) | $0.394_{0.128}$ | $0.203_{0.083}$ | $0.597_{0.122}$ | $-1.549_{3.747}$ | $-1.089_{0.58}$
GTSRB+Cars (Iter 1, 6+3 pts) | $0.085_{0.062}$ | $0.025_{0.018}$ | $0.11_{0.074}$ | $-0.28_{1.745}$ | $0.937_{0.087}$
GTSRB+Cars (Iter 2, 6+2*3 pts) | $0.036_{0.011}$ | $0.02_{0.021}$ | $0.055_{0.018}$ | $0.617_{0.268}$ | $0.962_{0.037}$
GTSRB+Cars (Init 9) | $0.205_{0.118}$ | $0.186_{0.152}$ | $0.391_{0.244}$ | $-1.111_{1.992}$ | $-0.529_{1.742}$
GTSRB+Cars (Init 12) | $0.091_{0.044}$ | $0.046_{0.052}$ | $0.138_{0.082}$ | $-0.177_{1.533}$ | $0.93_{0.046}$
GTSRB+RESISC45 (Iter 0, 6 pts) | $0.13_{0.092}$ | $0.111_{0.066}$ | $0.241_{0.076}$ | $-2.81_{1.772}$ | $-1.037_{1.184}$
GTSRB+RESISC45 (Iter 1, 6+3 pts) | $0.059_{0.007}$ | $0.04_{0.067}$ | $0.098_{0.067}$ | $0.449_{0.493}$ | $0.615_{0.363}$
GTSRB+RESISC45 (Iter 2, 6+2*3 pts) | $0.038_{0.011}$ | $0.043_{0.065}$ | $0.081_{0.074}$ | $0.672_{0.171}$ | $0.642_{0.313}$
GTSRB+RESISC45 (Init 9) | $0.075_{0.056}$ | $0.056_{0.07}$ | $0.131_{0.085}$ | $-0.676_{2.08}$ | $0.76_{0.364}$
GTSRB+RESISC45 (Init 12) | $0.105_{0.052}$ | $0.017_{0.013}$ | $0.122_{0.061}$ | $0.721_{0.39}$ | $0.863_{0.169}$
RESISC45+SVHN (Iter 0, 6 pts) | $0.168_{0.161}$ | $0.09_{0.092}$ | $0.258_{0.15}$ | $-1.005_{2.14}$ | $-1.415_{2.14}$
RESISC45+SVHN (Iter 1, 6+3 pts) | $0.12_{0.043}$ | $0.058_{0.075}$ | $0.179_{0.069}$ | $0.822_{0.156}$ | $0.12_{1.539}$
RESISC45+SVHN (Iter 2, 6+2*3 pts) | $0.099_{0.038}$ | $0.058_{0.076}$ | $0.157_{0.081}$ | $0.749_{0.249}$ | $0.206_{1.482}$
RESISC45+SVHN (Init 9) | $0.108_{0.109}$ | $0.081_{0.081}$ | $0.19_{0.159}$ | $0.324_{0.843}$ | $0.156_{0.932}$
RESISC45+SVHN (Init 12) | $0.023_{0.015}$ | $0.033_{0.025}$ | $0.055_{0.025}$ | $0.797_{0.216}$ | $0.782_{0.405}$
SUN397+SVHN (Iter 0, 6 pts) | $0.221_{0.144}$ | $0.075_{0.108}$ | $0.296_{0.195}$ | $-0.528_{2.117}$ | $-2.319_{3.904}$
SUN397+SVHN (Iter 1, 6+3 pts) | $0.094_{0.064}$ | $0.028_{0.018}$ | $0.122_{0.067}$ | $0.939_{0.047}$ | $-0.412_{1.255}$
SUN397+SVHN (Iter 2, 6+2*3 pts) | $0.086_{0.064}$ | $0.022_{0.005}$ | $0.108_{0.066}$ | $0.954_{0.029}$ | $-0.228_{0.925}$
SUN397+SVHN (Init 9) | $0.112_{0.17}$ | $0.031_{0.014}$ | $0.143_{0.181}$ | $0.216_{1.643}$ | $-0.647_{2.573}$
SUN397+SVHN (Init 12) | $0.083_{0.088}$ | $0.024_{0.005}$ | $0.107_{0.085}$ | $0.922_{0.046}$ | $0.639_{0.453}$

###  D.4 Additional experiment results on ResNet

We performed additional experiments on ResNet18 he2016deep on CIFAR10
krizhevsky2009learning and Flowers102 nilsback2008automated and show the
Pareto front obtained in Figure 8. Unlike ViT models which perform zero-shot
classification, ResNet requires additional fine-tuning of the classification
head after model merging. We demonstrate that our method still applies to
those models.

Figure 8: Pareto front obtained for two ResNet18 models on CIFAR10 and Flowers
102. We perform additional finetuning of the classification head after merging
the model weights.

##  Appendix E More details about algorithms

###  E.1 Algorithm 1

In this section, we extend the discussion on line 7 of the algorithm and on
Remark 1. In (6), the optimization problem is essentially minimizing the mean
squared error (MSE) of a linear regression. The predictors are
$\mathbf{C}=\text{concat}(c_{1}^{2},c_{2}^{2},\cdots,c_{T}^{2},c_{1}c_{2},c_{1}c_{3},\cdots,c_{T-1}c_{T},c_{1},c_{2},\cdots,c_{T},1)$,
the variables are $(\mathbf{A}_{n}^{*},\mathbf{b}_{n}^{*},e_{n}^{*})$, and the
responses are $M_{n}(\bm{\theta}_{\text{m}}(\mathbf{c}))$. Subscripts denote
standard deviations over 6 runs.

We can certainly seek other designs to improve the accuracy and robustness of
$(\mathbf{A}_{n}^{*},\mathbf{b}_{n}^{*},e_{n}^{*})$. On one hand, we can use
other loss functions like mean absolute error or Huber loss, while still using
the linear regression. On the other, we can modify
$\tilde{M}_{n}(\mathbf{c})$. If the metric $M_{n}$ has a specific bounded
region, we could restrict the fitting interval. For example, if the metric is
the accuracy or F1 score between 0 and 1, we could switch the definition to
$\tilde{M}_{n}(\mathbf{c};\mathbf{A}_{n},\mathbf{b}_{n},e_{n})\equiv\text{sigmoid}(e_{n}+\mathbf{b}_{n}^{\top}\mathbf{c}+\frac{1}{2}\mathbf{c}^{\top}\mathbf{A}_{n}\mathbf{c})$.
This is equivalent to a logistic regression with the same definition of
predictors and responses as the linear regression. If the metric is loss,
which ranges from 0 to positive infinity, then we could switch to
$\tilde{M}_{n}(\mathbf{c};\mathbf{A}_{n},\mathbf{b}_{n},e_{n})\equiv\text{softplus}(e_{n}+\mathbf{b}_{n}^{\top}\mathbf{c}+\frac{1}{2}\mathbf{c}^{\top}\mathbf{A}_{n}\mathbf{c})$.
In summary, one may extend (6) to

$\mathbf{A}_{n}^{*},\mathbf{b}_{n}^{*},e_{n}^{*}=\arg\min_{\mathbf{A}_{n},\mathbf{b}_{n},e_{n}}\text{MSE}\left(M_{n}(\bm{\theta}_{\text{merge}}(\mathbf{c})),\sigma(\tilde{M}_{n}(\mathbf{c};\mathbf{A}_{n},\mathbf{b}_{n},e_{n}))\right),$

and replace MSE and $\sigma=\mathbb{I}$ with other functions.

We emphasize that Algorithm 1 is an out-of-box plugin-like method. Many parts
of it are kept generic: there are multiple ways to sample $\Omega$ in terms of
the number of $\mathbf{c}$ and the style of sampling (Bayesian or not), thus
creating a tradeoff between the quality of Pareto front and the computational
time; the task vector can be computed on the more memory-capable CPU and
possibly in a parameter-efficient manner (e.g. LoRA, Adapter, and BiTFiT): for
example, computing $\mathbf{v}_{n}$ via the subtraction of two full 7B models
requires $2\times 23=46$GB of memory capacity, but the memory cost for PEFT
models may reduce to 16MB by only subtracting the non-frozen components; the
for-loops in line 2 and 4 can be computed in parallel, possibly using a much
smaller subset of the data, and thus enjoying a computational speed-up.

######  Remark 1 (quadratic surrogate model fitting)

In Algorithm 1, $\mathbf{A}_{n}^{*},\mathbf{b}_{n}^{*},e_{n}^{*}$ in (6) can
be readily solved by off-the-shelf methods, such as close-form solution (if
applicable), LBFGS, Newton’s method and gradient descent, since this is a
convex problem. In Appendix E, we generalize the ways to learn the
coefficients in (5), besides minimizing the mean square error in (6).

###  E.2 Algorithm 2

In this section, we explain the operations of the algorithm in Figure 3 in
details. Here task 1 to 8 is Cars, GTSRB, DTD, SUN397, Resisc45, and SVHN. If
we minimize (4) without the nested merging, we would need to estimate
$\mathbf{A}_{1},...,\mathbf{A}_{8}\in\mathbb{R}^{8\times 8}$, with hundreds of
$\mathbf{c}$.

With the nested merging, for the first round, we merge
$(\bm{\theta}_{ft}^{1},\bm{\theta}_{ft}^{2})$into
$\bm{\theta}_{\text{merge}}^{1,2}$, thus approximating $\mathbf{A}_{1}$ and
$\mathbf{A}_{2}\in\mathbb{R}^{8\times 8}$ by $\mathbf{A}_{1}[1:2,1:2]$ and
$\mathbf{A}_{2}[1:2,1:2]\in\mathbb{R}^{2\times 2}$, respectively. That is, we
only care about the interference between task 1 and 2, but not task 1 and 5.
Similarly, we merge $(\bm{\theta}_{ft}^{3},\bm{\theta}_{ft}^{4})$into
$\bm{\theta}_{\text{merge}}^{3,4}$, and
$(\bm{\theta}_{ft}^{5},\bm{\theta}_{ft}^{6})$into
$\bm{\theta}_{\text{merge}}^{5,6}$. Next, we merge
$(\bm{\theta}_{\text{merge}}^{1,2},\bm{\theta}_{\text{merge}}^{3,4})$into
$\bm{\theta}_{\text{merge}}^{1,2,3,4}$, and finally into
$\bm{\theta}_{\text{merge}}^{1,2,3,4,5,6,7,8}$.

###  E.3 Algorithm 3

Algorithm 4 is a detailed version of Algorithm 3. Figure 9 includes an
illustration of our discretization method (how we create bins) in 2D and 3D
decision variable ($\mathbf{c}$) space.

(a)

(b)

Figure 9: (a) Discretizing of two task scaling coefficients along the angular
dimension in 2D polar coordinate system; (b) Discretizing of three task
scaling coefficients along the angular dimensions in 3D spherical coordinate
system; Algorithm 4 Bayesian Adaptive of Surrogate Model

0: Number of iterations $J$, Buffer $\mathcal{B}$, Pretrained model
$\bm{\theta}_{\textup{pre}}$, Task vectors $\mathbf{v}_{n}$, Evaluators for
task $N$, $M_{n}(\cdot)$, Discretization bin number $K$, sample size for every
iteration $n_{j}$, $j=0$ to $J$, Bootstrap dropping rate $\alpha=20\%$,
Bootstrap sampling number $Q=30$.

1: $\mathcal{B}\leftarrow\emptyset$

2: for $j=0$ to $J$ do

3: if $j=0$ then

4: Sample $n_{0}$ scaling coefficients $\\{\mathbf{c}_{i}\\}_{i=1}^{n_{j}}$
from $U([0,1]^{T})$

5: else

6: Sample $n_{j}$ scaling coefficients $\\{\mathbf{c}_{i}\\}_{i=1}^{n_{j}}$
based on the posterior distribution

7: for $i=0$ to $n_{j}$ do

8: Merge the model
$\theta_{m}(\mathbf{c}_{i})=\bm{\theta}_{\textup{pre}}+\mathbf{c}_{i}\cdot\mathbf{v}_{n}$

9: Evaluate $m_{n,i}=M_{n}(\theta_{m}(\mathbf{c}_{i}))$

10: $\mathcal{B}\leftarrow\mathcal{B}\cup\\{(\mathbf{c}_{i},m_{n,i})\\}$

11: Fit the quadratic approximation surrogate model $\tilde{M}_{n}$ by
learning $\mathbf{A}_{n}^{*},\mathbf{b}_{n}^{*},e_{n}^{*}$ in (6).

12: Discretize the scaling coefficients along the angular dimensions in hyper-
spherical coordinates (see figure 9 as examples)

13: for $k=0$ to $K$ do

14: Calculate the mean of $L2$ loss between $\tilde{M}_{n}(\mathbf{c}_{i})$
and ${M}_{t}(\mathbf{c}_{i})$, where $\mathbf{c}_{i}$ are in bin $k$, denoted
as $\text{mean}_{k}$ {Bootstrap to estimate the standard deviation of the
losses.}

15: for $q=0$ to $Q$ do

16: Randomly (uniformly) drop $\alpha$ scaling coefficient in bin $k$

17: Calculate the mean of $L2$ loss between $\tilde{M}_{n}(\mathbf{c}_{i})$
and ${M}_{t}(\mathbf{c}_{i})$ with the rest points and denoted with $l_{q}$

18: Calculate the standard deviation of the $\\{l_{q}\\}_{q=0}^{Q}$ and
denoted as $\text{std}_{k}$

19: $\text{score}_{k}=\text{mean}_{k}+\frac{1}{2}\text{std}_{k}$

20: Calculate probability distribution across the discretized bins by
$\text{score}_{k}$ as the posterior sampling strategy in the next round

21: return