# Hyperparameter Optimization for SecureBoost via Constrained Multi-Objective
Federated Learning

Yan Kang†1, Ziyao Ren†, Lixin Fan, Linghua Yang, Yongxin Tong, and Qiang Yang
Ziyao Ren, Linghua Yang, and Yongxin Tong are with the School of Computer
Science, Beihang University, Beijing, China. Yan Kang, Lixin Fan, and Qiang
Yang are with Webank, Shenzhen, China. Qiang Yang is also with Hong Kong
University of Science and Technology. Yan Kang and Ziyao Ren are co-first
authors. Corresponding author: Yan Kang (email: yangkang@webank.com).

###### Abstract

SecureBoost is a tree-boosting algorithm that leverages homomorphic encryption
(HE) to protect data privacy in vertical federated learning. SecureBoost and
its variants have been widely adopted in fields such as finance and
healthcare. However, the hyperparameters of SecureBoost are typically
configured heuristically for optimizing model performance (i.e., utility)
solely, assuming that privacy is secured. Our study found that SecureBoost and
some of its variants are still vulnerable to label leakage. This vulnerability
may lead the current heuristic hyperparameter configuration of SecureBoost to
a suboptimal trade-off between utility, privacy, and efficiency, which are
pivotal elements toward a trustworthy federated learning system. To address
this issue, we propose the Constrained Multi-Objective SecureBoost (CMOSB)
algorithm, which aims to approximate Pareto optimal solutions that each
solution is a set of hyperparameters achieving an optimal trade-off between
utility loss, training cost, and privacy leakage. We design measurements of
the three objectives, including a novel label inference attack named instance
clustering attack (ICA) to measure the privacy leakage of SecureBoost.
Additionally, we provide two countermeasures against ICA. The experimental
results demonstrate that the CMOSB yields superior hyperparameters over those
optimized by grid search and Bayesian optimization regarding the trade-off
between utility loss, training cost, and privacy leakage.

###### Index Terms:

Vertical Federated Learning, Multi-Objective Optimization, Hyperparameter
Optimization, Privacy Preservation, Gradient Boosted Trees

##  I Introduction

Federated learning (FL) [1] is a novel distributed machine learning paradigm
that enables multiple participants to train machine learning models without
compromising data privacy. Federated learning can be categorized into
horizontal federated learning and vertical federated learning based on how the
data is distributed among participating parties [2]. Vertical federated
learning (VFL) [3] refers to the scenario where feature data is vertically
partitioned among multiple parties, with one party possessing the data labels.
In VFL, each party holds different parts of the feature data, and they
collaborate to train machine learning models without directly sharing their
raw data. SecureBoost [4] is a widely adopted vertical federated tree-boosting
algorithm for its interpretability and privacy-preserving ability.
Nevertheless, It has the following two limitations.

Limitation 1: SecureBoost still faces the possibility of label leakage [5]
through intermediate information, despite employing homomorphic encryption to
protect instance gradients. Our experimental results in Sec. VII-B reveal that
up to 84% of labels can be leaked stemming from the absence of protection on
instance distributions. Therefore, defense mechanisms are required for
SecureBoost to protect the label privacy in addition to HE.

Limitation 2: Heuristic hyperparameter configuration may lead to suboptimal
trade-off between utility, efficiency, and privacy of the SecureBoost model.
Existing FL platforms [6, 7] typically determine the hyperparameters of
SecureBoost heuristically, which may lead to suboptimal hyperparameter choices
that do not maximize utility, efficiency, and privacy - the pivotal elements
of trustworthy federated learning.

To address the two limitations, we propose Constrained Multi-Objective
SecureBoost (CMOSB) [8] to find Pareto optimal solutions of hyperparameters
that can simultaneously minimize three conflicting objectives: utility loss,
training cost, and privacy leakage. Each solution represents an optimal trade-
off between the three objectives [9]. Consequently, Pareto optimal solutions
not only provide optimal hyperparameters for SecureBoost but also cater to the
flexible requirements of VFL participants concerning privacy and resource
constraints. For example, participants can select the most appropriate
hyperparameters from the Pareto optimal solutions that align with their
preference for utility, efficiency, and privacy. Our main contributions are
summarized as follows:

  * •

We formalize the Constrained Multi-Objective SecureBoost (CMOSB) problem and
correspondingly propose a CMOSB algorithm to identify Pareto optimal solutions
of hyperparameters that simultaneously minimize utility loss, training cost,
and privacy leakage. Our CMOSB algorithm can be readily extended to optimize
other objectives, providing a versatile and effective approach to addressing
the complex trade-offs in training federated tree-boosting models.

  * •

We design measurements of utility loss, training cost, and privacy leakage. In
particular, we propose a novel label inference attack named instance
clustering attack to measure privacy leakage. We also develop two
countermeasures against this attack.

  * •

We conduct experiments on four datasets, demonstrating that our CMOSB can find
better hyperparameters than grid search and Bayesian optimization in terms of
the trade-off between privacy leakage, utility loss, and training cost.
Moreover, CMOSB can find Pareto optimal solutions of hyperparameters that
achieve better trade-offs between utility loss, training cost, and privacy
leakage than state-of-the-art solutions.

The rest of the paper is organized as follows. We first review related work in
Sec. II and introduce the preliminary in Sec. III. Then, we describe the CMOSB
problem in Sec. IV and elaborate on our proposed label inference attack and
the corresponding defense methods in Sec. V. Next, we provide the CMOSB
algorithm in Sec. VI. We report our experimental results in Sec. VII and
conclude this paper in Sec. VIII.

##  II Related Work

In this section, we review related work from three categories: tree-based
models in VFL, label leakage in VFL, and multi-objective federated learning.

###  II-A Tree-based Models in VFL

Tree-based models are a common type of machine learning algorithm, and their
applications in federated learning require the design of appropriate privacy
protection methods. SecureBoost [4] is an XGBoost-based model that protects
data privacy by applying homomorphic encryption to intermediate gradients.
SecureBoost+ [10] extends the SecureBoost algorithm to multi-class tasks and
improves SecureBoost’s training efficiency. VF2Boost [7] is a system based on
SecureBoost that reduces model training costs through parallel computation.
HEP-XGB [11] employs a customized secret sharing method to achieve efficient
two-party XGBoost model construction. Pivot [12] utilizes a combination of
homomorphic encryption and secure multi-party computation to train XGBoost
models, ensuring that no intermediate results are leaked during the training
process.

###  II-B Label Leakage in VFL

Label leakage in vertical federated learning refers to the situation where the
passive party is able to obtain the label information of the active party
during the training process. Fu et al. [5] systematically classified the label
leakage in vertical federated learning into three categories: active attack,
passive attack, and direct attack, and provided an attack method for each
category. Zou et al. [13] proposed a label attack method on the black-boxed
VFL and presented a privacy protection method. Xie et al. [14] demonstrated
that split learning remains vulnerable to label inference attacks. Qiu et al.
[15] found that the training of GNNs in VFL may also lead to the leakage of
sample relationships. Tan et al. [16] proposed a gradient inversion attack
that utilizes the gradients of local models to reconstruct label data. Pan et
al. [17] implements an efficient data federation system using secure multi-
party computation to avoid label leakage.

###  II-C Multi-objective Federated Learning

Multi-objective federated learning is a collaborative optimization approach in
which participants of FL aim to optimize multiple conflicting objectives
simultaneously and find Pareto optimal solutions. Personalized Federated
Learning aims to optimize the federated model structure for each participating
party’s data distribution[18, 19]. Cui et al. [20] considered the utility of
participating parties as the optimization objective, model disparity as the
constraint, and optimized the objectives of all participants to calculate the
Pareto front. This approach ensures the fairness of federated learning and
enables obtaining the optimal performance model. Zhu et al. [21] formulated
the accuracy and communication cost of federated learning as the optimization
objectives and adjusted the model sparsity to minimize both the communication
cost and test errors. The algorithm proposed in [8] is a multi-objective
federated learning algorithm with constraints, which adds constraints to the
optimization objectives and finds the Pareto front more efficiently within the
feasible range.

##  III Preliminary

In this section, we introduce some preliminaries of vertical federated
learning (VFL) and SecureBoost.

###  III-A Vertical Federated Learning

Vertical Federated Learning [2, 3] is one of the scenarios in Federated
Learning. In this setting, feature data is vertically partitioned among
multiple parties, with one party possessing the data labels (Fig. 1).
Specifically, the active party holds both features and labels, while the
passive parties hold only features.

Figure 1: An illustration of data partition in VFL.

All participating parties in VFL first align their instances by private set
intersection (PSI) [22], and then perform federated model training and
inference. During the training process, each party is not allowed to reveal
its training data to others [23]. After the federated training is completed,
the federated model $M$ is obtained, which is jointly held by all
participating parties, i.e., model $M$ is split into
$M_{1},M_{2},\dots,M_{K}$. In the inference phase, all participating parties
collaboratively make the prediction, but only the active party can access the
final predicted result.

###  III-B SecureBoost

SecureBoost [4] is a widely used gradient boosting tree algorithm designed for
the vertical federated learning scenario. The core idea of SecureBoost is to
use $n$ federated decision trees to fit instance labels.

For each iteration, SecureBoost constructs a new tree from the root node based
on a node split finding algorithm, which is summarized in Algo. 1. In this
process, the active party sends the homomorphically encrypted gradients
$\left\langle g\right\rangle$, $\left\langle h\right\rangle$, and instance
space $I$ of the current node to passive parties. The passive parties then
calculate the gradient statistics and send them back to the active party. The
active party finds the optimal split of the current node with the maximal
splitting score and informs the corresponding parties to split the instance
space into child nodes. The split-finding process continues until the maximum
depth is reached. For a more detailed description, please refer to [4].

Algorithm 1 SecureBoost Split Finding (SF)

1:Input: Instance space of current node $I$;

2:Input: Gradient $\left\langle g\right\rangle$, hessian $\left\langle
h\right\rangle$.

3:Output: Partition current instance space according to the selected
attribute’s value.

4:$\triangleright$ Passive parties perform:

5:Calculate gradient statistics based on $\left\langle g\right\rangle$,
$\left\langle h\right\rangle$, and $I$;

6:$\triangleright$ Active party performs:

7:for each split point do

8: Calculate info gain based on gradient statistics;

9: Update splitting score based on the info gain;

10:Return optimal split to the corresponding party;

11:$\triangleright$ Passive party performs:

12:Partition instance space to form $I_{L}$ according to the optimal split,
and update model;

13:$\triangleright$ Active party performs:

14:Split current node according to $I_{L}$ and update model;

The instance distributions of leaf nodes in SecureBoost are not protected,
which may lead to privacy leakage. Some methods [12, 11] use a combination of
Homomorphic Encryption (HE) and Secure Multi-Party Computation (MPC) to
address this issue and enhance privacy protection. However, these methods may
result in significant training cost, making it challenging to apply them in
practical and trustworthy federated learning scenarios.

##  IV Constrained Multi-Objective SecureBoost Problem

The Constrained Multi-Objective SecureBoost Learning (CMOSB) problem aims to
find Pareto optimal solutions that each is a set of hyperparameters leading to
an optimal trade-off between three objectives under constraints: utility loss,
training cost, and privacy leakage. Inspired by [8], we formulate the CMOSB
problem as follows:

$\begin{split}&\min\limits_{x\in\mathcal{X}}(\epsilon_{u}(x),\epsilon_{c}(x),\epsilon_{p}(x))\\\
&\text{subject to
}\,\,\epsilon_{u}(x)\leq\phi_{u},\epsilon_{c}(x)\leq\phi_{c},\epsilon_{p}(x)\leq\phi_{p}.\end{split}$
(1)

where $x\in\mathbb{R}^{d}$ is a solution in the decision space $\mathcal{X}$;
$\epsilon_{u}(x)$, $\epsilon_{c}(x)$, and $\epsilon_{p}(x)$ denote the
objectives of utility loss, training cost, and privacy leakage, respectively;
$\phi_{u}$, $\phi_{c}$, and $\phi_{p}$ are the upper bounds of $\epsilon_{u}$,
$\epsilon_{c}$, and $\epsilon_{p}$, respectively.

######  Remark 1.

In this paper, a solution $x$ refers to a collection of hyperparameters, such
as the depth of decision trees, batch size, protection strength parameters,
and so on. Each set of hyperparameters corresponds to specific values of
privacy leakage, utility loss, and training cost.

During multi-objective SecureBoost training, SecureBoost participants put
constraints on utility loss, training cost, and privacy leakage to ensure that
the utility meets the specified requirements. These constraints also serve to
limit training cost and privacy leakage within the allocated budget. By doing
so, SecureBoost participants can strike a balance between utility, cost, and
privacy in a controlled manner.

Formally, SecureBoost participants aim to find Pareto front and corresponding
Pareto optimal solutions for the Constrained Multi-Objective SecureBoost
problem. We provide the definitions of Pareto dominance, Pareto optimal
solution, Pareto set, and Pareto front as follows.

######  Definition 1 (Pareto Dominance).

Let $x_{a},x_{b}\in\mathcal{X}$, $x_{a}$ is said to dominate $x_{b}$, denoted
as $x_{a}\prec x_{b}$, if and only if $f_{i}(x_{a})\leq f_{i}(x_{b}),\forall
i\in\\{1,\ldots,m\\}$ and $f_{j}(x_{a})<f_{j}(x_{b}),\exists
j\in\\{1,\ldots,m\\}$.

######  Definition 2 (Pareto Optimal Solution).

A solution $x^{*}\in\mathcal{X}$ is called a Pareto optimal solution if there
does not exist a solution $\hat{x}\in\mathcal{X}$ such that $\hat{x}\prec
x^{*}$.

A Pareto optimal solution refers to a solution that achieves an optimal trade-
off among different conflicting objectives. The collection of all Pareto
optimal solutions forms the Pareto set, while the corresponding objective
values for the Pareto optimal solutions form the Pareto front. The definitions
of the Pareto set and Pareto front are formally given as follows.

######  Definition 3 (Pareto Set and Front).

The set of all Pareto optimal solutions is called the Pareto set, and its
image in the objective space is called the Pareto front.

We use hypervolume (HV) indicator [24] as a metric to measure the Pareto
front. The definition of hypervolume indicator is provided below.

######  Definition 4 (Hypervolume Indicator).

Let $z=\\{z_{1},\cdots,z_{m}\\}$ be a reference point that is an upper bound
of the objectives $V=\\{v_{1},\ldots,v_{m}\\}$, such that $v_{i}\leq z_{i}$,
$\forall i\in[m]$. The hypervolume indicator $\text{HV}(V)$ measures the
region between $V$ and $z$ and is formulated as:

$\text{HV}(V)=\Lambda\left(\left\\{q\in\mathbb{R}^{m}\big{|}q\in\prod_{i=1}^{m}[v_{i},z_{i}]\right\\}\right)$
(2)

where $\Lambda(\cdot)$ refers to the Lebesgue measure.

To address the CMOSB problem outlined in Eq.(1), we must first quantify the
utility loss, training cost, and privacy leakage of a given solution.
Measuring utility loss and training cost is straightforward, which we will
discuss in Section VI-A. Evaluating privacy leakage requires a more
sophisticated approach, as it involves assessing the extent to which an
individual’s private information can be inferred from the model’s outputs. To
address this challenge, we propose a novel label inference attack that
exploits a vulnerability in SecureBoost, allowing us to infer private label
information. In the next section, we will delve deeper into the threat model,
the label inference attack, and potential countermeasures.

##  V Privacy Leakage in SecureBoost

In this section, we first elaborate on the threat model. Then, we design a
label inference attack and explain how this attack can lead to the leakage of
labels owned by the active party. Finally, we propose two defense methods
against this attack.

###  V-A Threat Model

Below, we discuss the threat model, which includes the attacker’s objective,
capability, and knowledge.

Attacker’s objective. We consider the passive party as the attacker, who aims
to infer labels owned by the active party.

Attacker’s capability. We assume the attacker is semi-honest, meaning that the
attacker faithfully follows the SecureBoost protocol but may attempt to infer
labels of the active party.

Attacker’s knowledge. The passive party can access instance distributions of
leaf nodes since SecureBoost does not protect this information. Additionally,
we assume that the passive party holds several labeled instances for each
class, similar to the assumption made in [5].

###  V-B Label Inference Attack

Gradient boost decision tree (GBDT) construction involves computing
information gain based on instance features owned by different parties. To
ensure that private features are not disclosed to other parties during the
process of calculating information gain, the active party needs to share
instance gradients and distributions with passive parties in a privacy-
preserving manner. While SecureBoost and its variant [10] utilize homomorphic
encryption to protect gradient information passed between the active party and
passive parties, they do not protect the instance distribution of each leaf
node owned by the passive party. This indicates that the passive party (i.e.,
the attacker) can exploit this information to infer the active party’s labels
through clustering.

Figure 2: The workflow of instance clustering attack. (1) The attacker
constructs a similarity matrix based on the instance distribution. (2) The
attacker clusters the training instances based on the similarity matrix. (3)
The attacker infers labels of unlabeled instances based on the known labels.

We propose a label inference attack named Instance Clustering Attack (ICA) to
infer the label information owned by the active party and leverage ICA to
measure the privacy leakage of the SecureBoost algorithm. The procedure of ICA
is illustrated in Fig. 2 and described in Algo. 2.

Algorithm 2 Instance Clustering Attack

1:Input: Instance distribution $\\{I_{i}\\}_{i=1}^{n}$.

2:Output: Predicted label $\hat{y}$.

3:Calculate instance similarity matrix $S$ by Eq.(3);

4:Categorize instances into $C$ clusters $\\{c_{i}\\}_{i=1}^{C}$ based on $S$;

5:for $i=1$ to $C$ do

6: $y_{i}\leftarrow$ the known label of one instance in cluster $c_{i}$;

7: Assign label $y_{i}$ to $\hat{y}$ for all instances in $c_{i}$;

8:return $\hat{y}$;

The idea behind the attack is straightforward: samples with the same label are
highly likely to be grouped into the same leaf node. The attacker first
constructs the similarity matrix based on the instance distribution of each
leaf node using Eq. (3) (line 1 of Algo. 2).

$\begin{split}sim(a,b)=&\frac{1}{n}\sum_{i=1}^{n}s(a,b,i),\\\ \text{where
}s(a,b,i)=&\begin{cases}1,\text{ if }\exists j,a,b\in I_{i,j}\\\ 0,\text{
otherwise}\end{cases}\end{split}$ (3)

where $n$ denotes the number of decision trees, and $j$ denotes the index of
the leaf node.

Then, the attacker utilizes this similarity matrix to categorize instances
into $C$ clusters (line 2). We employ spectral clustering [25], a
straightforward yet effective method for clustering instances based on the
similarity matrix. This stage essentially involves learning a mapping from
cluster IDs to the actual labels. If the attacker possesses more labeled data,
it can establish a better mapping, which improves the accuracy of ICA. We
assume the attacker knows the label of one instance in each cluster. Hence,
the attacker assigns instances in each cluster with the known labels (lines
3-5).

We use the accuracy of the instance clustering attack to measure the privacy
leakage $\epsilon_{p}$ (see Sec. VI-A).

###  V-C Defense Methods

Due to the high communication and computational overhead associated with
directly preserving the privacy of the instance distribution, Secure Multi-
Party Computation (MPC) is often challenging to apply in real-world scenarios.
In this work, we propose two defense methods that can mitigate privacy leakage
caused by the instance clustering attack (ICA).

The performance of ICA depends on the purity of leaf nodes owned by the
attacker (i.e., the passive party). We define the purity of a node as the
ratio of instances belonging to the majority class to all instances in that
node. A higher purity implies a more accurate similarity matrix, which can
lead to more precise clustering results and, consequently, more privacy
leakage. Therefore, our proposed defense methods mitigate privacy leakage by
reducing node purity, and we name the two defense methods: (1) local trees 111
Our defense method has been implemented in FATE v1.11.2. ; (2) purity
threshold.

Local Trees.

The mechanism of ICA (see Sec. V-B) indicates that the stronger the
correlation between the instance distribution and true labels, the higher the
likelihood of label privacy leakage.

We utilize mutual information [26] to measure the correlation between labels
and the instance distribution on each tree during the training of SecureBoost,
to investigate the occurrence of label leakage. Specifically, we trained 10
SecureBoost models, each consisting of 50 trees. Fig. 3 illustrates the
average variation of mutual information with respect to iterations (each
representing a tree). It indicates that the mutual information is relatively
high in the first few iterations of training, suggesting a higher likelihood
of privacy leakage during the initial stages of SecureBoost training.

Figure 3: Mutual information between instance distribution and labels. BC:
binary classification; MC: multi-class classification. Higher mutual
information implies a higher likelihood of privacy leakage. The mutual
information sharply decreases in the first few trees and then starts
fluctuating.

To mitigate the label leakage, we propose a local training stage preceding
SecureBoost, where the active party trains $n_{l}$ decision trees locally. The
objective is to reduce the mutual information between the instance
distribution and instance labels in the federated SecureBoost model.

The decision trees obtained from the local training stage are stored
exclusively on the active party’s side, ensuring no information leakage while
still participating in the federated prediction process. Once the local
training stage is completed, the federated learning stage begins, where all
participants collectively train $n_{f}$ decision trees according to the
SecureBoost protocol. These two stages together establish the SecureBoost
model with privacy protection.

Figure 4: Illustration of the purity threshold method. (1) The active party
sends instance distribution and calculates the optimal split point based on
statistical data. (2) The active party performs a purity check of the optimal
split point. (3) If the purity exceeds $p$ the threshold $\theta_{p}$, it
builds the subtree locally; otherwise, the training continues normally.

Purity Threshold.

The purity threshold mitigates privacy leakage by preventing the sharing of
instance distributions of high-purity nodes with passive parties. The active
party sends the instance distributions to passive parties, calculates the
information gain based on the returned statistical data, and identifies the
optimal split point of a node $j$. Subsequently, the active party calculates
its purity $p_{j}$, and if the purity $p_{j}$ exceeds the pre-specified
threshold $\theta_{p}$, passive parties are excluded from the federated
training of the subtree rooted at node $j$, and the active party proceeds to
train this subtree locally. Otherwise, all participants continue with the
SecureBoost algorithm.

Although the two defense methods can effectively thwart the instance
clustering attack, they may introduce utility loss. Therefore, trade-offs need
to be made between utility and privacy. We consider their hyperparameters as
decision variables when optimizing the Constrained Multi-Objective SecureBoost
problem (Sec. VI).

##  VI Constrained Multi-Objective SecureBoost Algorithm

In this section, we elaborate on our Constrained Multi-Objective SecureBoost
algorithm (CMOSB).

###  VI-A Measurements of Objectives

Prior to delving into the algorithmic aspects, we first establish the
measurements used to evaluate the three objectives we aim to optimize: utility
loss, training cost, and privacy leakage.

Utility Loss. The utility loss $\epsilon_{u}$ measures the amount of decrease
in utility when certain defense methods are applied to thwart the label
inference attack:

$\epsilon_{u}=1-U(M,D)$ (4)

where $M$, $D$, and $U$ denote the SecureBoost model, the test dataset, and
the performance metric, respectively. $U$ is AUC for binary classification and
accuracy for multi-class classification.

Training Cost. We use training time to measure the training cost of
SecureBoost. Since HE operations dominate training time, we estimate the
training cost $\epsilon_{c}$ by summing the time spent on each HE operation:

$\epsilon_{c}=c_{enc}\times t_{enc}+c_{dec}\times t_{dec}+c_{add}\times
t_{add}$ (5)

where $c_{enc}$, $c_{dec}$, and $c_{add}$ denote the number of encryption,
decryption, and addition operations, respectively, while $t_{enc}$, $t_{dec}$,
and $t_{add}$ represent the average time required for each corresponding HE
operation.

Privacy Leakage. We use the accuracy of the instance clustering attack (see
Sec. V-B) to measure the privacy leakage $\epsilon_{p}$. The attack is
evaluated based on a randomly sampled set of instances denoted as $I_{pl}$,
where the number of instances belonging to each class is the same. The privacy
leakage $\epsilon_{p}$ can be measured as follows:

$\epsilon_{p}=\frac{1}{N_{pl}}\sum_{i\in
I_{pl}}\mathcal{I}[\hat{y_{i}}==y_{i}]$ (6)

where $\hat{y_{i}}$ denotes the label inferred by the instance clustering
attack, and $y_{i}$ denotes the true label, $N_{pl}=|I_{pl}|$ and
$\mathcal{I}$ denotes the indicator function.

###  VI-B The CMOSB Algorithm

In this section, we propose the Constrained Multi-Objective SecureBoost
algorithm (CMOSB), which aims to obtain approximate Pareto optimal solutions
and front. It achieves a balance between the three optimization objectives and
provides guidance for hyperparameter selection.

Algorithm 3 CMOSB Algorithm

1:Input: Generations $T$, dataset $D_{k}$ owned by client $k\in[K]$,
constraints $\phi_{p},\phi_{c}$.

2:Output: Pareto optimal solutions and front $\\{X_{T},Y_{T}\\}$.

3:Initialize solutions $\\{X_{0}\\}$;

4:for each generation $t$ $=1,2,\cdots,T$ do

5: Crossover and mutate parent solutions $X_{t-1}$ to produce offspring
solutions $P$;

6: $R$ $\leftarrow$ Merge $X_{t-1}$ and $P$;

7: $Y$ $\leftarrow$ SBO$(R,\\{D_{j}\\}_{j=1}^{K})$ ;

8: for each tuple ($\epsilon_{p},\epsilon_{c}$) in $V$ do

9: $\epsilon_{i}=\epsilon_{i}\text{ +
}\alpha_{i}\max\\{0,\epsilon_{i}-\phi_{i}\\},i\in\\{p,c\\}$;

10: $R^{S}\leftarrow$ Non-dominated sorting and crowding distance sorting $R$
based on $Y$;

11: $X_{t}$ $\leftarrow$ Select $N$ high-ranking solutions from $R^{S}$;

12:return $\\{X_{T},Y_{T}\\}$;

CMOSB is based on NSGA-II and described in Algo. 3. Offspring solutions of the
current generation are generated by performing crossover and mutation using
solutions found during the previous generation (line 3). All newly generated
candidate solutions are evaluated using Algo. 4 (line 5). The algorithm adds a
constraint to limit the search space of the solutions (lines 6-7). Lines 8-9
sort the candidate solutions and select the top $N$ for the next generation.

Algorithm 4 SecureBoost Optimization (SBO)

1:Input: Solutions X, feature data $D_{k}$ owned by client $k$.

2:Output: Objective values $Y$ for $X$.

3:for each solution $x$ $\in$ $X$ do

4: Set hyperparameters $n_{l}$, $n_{f}$, $p$ according to $x$;

5: for each boosting iteration $i\in 1,\dots,n_{l}$ do

6: $\triangleright$ Local training stage

7: Active party train decision tree $i$ locally;

8: for each boosting iteration $i\in n_{l}+1,\dots,n_{l}+n_{f}$ do

9: $\triangleright$ Federated learning stage

10: Active party computes gradient $\left\langle g\right\rangle$, hessian
$\left\langle h\right\rangle$;

11: for each node $j$ satisfies depth criteria do

12: Active party computes purity $p_{j}$ of node $j$;

13: if $p_{j}<\theta_{p}$ then

14: Get instance space $I_{i,j}$ of current node;

15: Split the node using $\text{SF}(I_{i,j},\left\langle
g\right\rangle,\left\langle h\right\rangle)$;

16: else

17: Active party split the node locally;

18: Measure training cost $\epsilon_{e,i}$;

19: Measure privacy leakage $\epsilon_{p,i}$;

20: $\epsilon_{e}\leftarrow\epsilon_{e}+\epsilon_{e,i}$;

21: $\epsilon_{p}\leftarrow\max(\epsilon_{p},\epsilon_{p,i})$;

22: Measure utility loss $\epsilon_{u}$;

23: $Y\leftarrow Y+(\epsilon_{p},\epsilon_{c},\epsilon_{u})$;

24:return $Y$;

Algo. 4 aims to measure the utility loss, training cost, and privacy leakage
while training a SecureBoost model. The variable $x$ represents a set of
hyperparameters for SecureBoost, and Table III provides a detailed description
of these hyperparameters. Lines 3-5 correspond to the local training stage
mentioned in Sec. V-C, while lines 6-19 constitute the federated learning
stage, forming the SecureBoost framework. In line 10, the active party
calculates the purity of node $j$, and if it is below the threshold
$\theta_{p}$, all participants will jointly calculate the split point;
otherwise, only the active party will calculate it locally. Training cost and
privacy leakage will be calculated during the iteration process, while utility
will be calculated after the training is completed.

##  VII Experiments

In this section, we empirically investigate the effectiveness of our proposed
attacking method, defense methods, and the hyperparameter optimization
algorithm CMOSB.

###  VII-A Experimental Settings

Dataset and setting. We conduct experiments on two synthetic datasets and two
real-world datasets. The synthetic datasets, generated using the sklearn
library222https://scikit-learn.org/stable/, consist of Synthetic1 for binary
classification and Synthetic2 for multi-class classification. The
DefaultCredit 333https://www.kaggle.com/uciml/default-of-credit-card-clients-
dataset dataset involves predicting whether users can repay their loans on
time, while the Sensorless 444https://archive.ics.uci.edu/dataset/325/ dataset
is used for sensorless drive diagnosis.

To create datasets for the federated scenario, each dataset was vertically
partitioned into two sub-datasets. We used 2/3 of the data as the training set
and the remaining as the test set. Table I summarizes these datasets.

We implement all the methods with Python 3.8. The experiments were conducted
on two Intel(R) Xeon(R) Platinum 8269CY 3.10GHz CPUs each with 4 cores.

TABLE I: Datasets for evaluation. S: # of samples; PF: # of features in passive party; AF: # of features in active party; C: # of classes. Name | S | AF | PF | C
---|---|---|---|---
Synthetic1 | 2,000 | 5 | 5 | 2
DefaultCredit | 30,000 | 12 | 13 | 2
Synthetic2 | 10,000 | 5 | 5 | 10
Sensorless | 58,509 | 12 | 36 | 11

Baseline. We compared our Constrained Multi-objective SecureBoost (CMOSB)
method with the following methods:

  * •

Empirical Selection (ES): Empirical Selection represents the default
hyperparameters that are typically determined empirically.

  * •

Grid Search (GS): Grid Search is a traditional hyperparameter optimization
method that exhaustively evaluates different combinations for the optimal
hyperparameter combination [27].

  * •

Bayesian Optimization (BO): Bayesian Optimization [28] is a classic
hyperparameter optimization method for machine learning algorithms. It
utilizes Gaussian processes to improve search efficiency. However, BO is only
suitable for single-objective optimization. For multi-objective optimization,
we leverage BO to optimize each objective separately.

Hyperparameter. We chose three sets of hyperparameters for the ES baseline.
The first two sets of hyperparameters are chosen from the default
hyperparameters of FATE [6] and VF2Boost [7], respectively. The third set of
hyperparameters is the average of the first two.

To make a fair comparison, the sampling rate is set to $0.8$, and complete
secure is set to true.

The complete secure corresponds to the local tree defense method, where
$n_{l}$ is set to $1$, indicating that local training of a single tree is
performed before federated learning.

The specific hyperparameter settings are shown in Table II.

TABLE II: Default hyperparameters used in the comparison.  Baseline | $n_{f}$ | $d$ | $\eta$ | $r$ |  complete secure
---|---|---|---|---|---
FATE | 5 | 3 | 0.3 | 0.8 | true
VF2Boost | 20 | 7 | 0.1 | 0.8 | true
Average | 10 | 5 | 0.3 | 0.8 | true
TABLE III: Hyperparameter variables used in CMOSB algorithm. Variable | Range | Chromosome Type | Description
---|---|---|---
$n_{f}$ | $[1,16]$ | Binary | The number of iterations for boosting in federated learning
$n_{l}$ | $[1,16]$ | Binary | The number of iterations for boosting locally
$d$ | $[1,8]$ | Binary | Maximum depth of each decision tree
$r$ | $[0.1,1.0]$ | Real-value | Subsample ratio of the training instances
$\theta_{p}$ | $[0.1,1.0]$ | Real-value | The purity threshold to stop the federated learning
$\eta$ | $[0.01,0.3]$ | Real-value | Step size shrinkage used in update to prevents overfitting

CMOSB Setup. The proposed CMOSB algorithm is based on NSGA-II. Thus, we follow
the setup proposed in literature [21]. We apply a single-point crossover for
binary chromosomes with a probability of 0.9 and a bit-flip mutation with a
probability of 0.1. We apply a simulated binary crossover (SBX) [29] for real-
valued chromosome with a probability of 0.9 and $n_{c}$ = 2, and a polynomial
mutation with a probability of 0.1 and $n_{m}$ = 20, where $n_{c}$ and $n_{m}$
denote spread factor distribution indices for crossover and mutation,
respectively. The number of generations for CMOSB is set to 40.

###  VII-B Effectiveness of Defense Methods

In this section, we investigate the efficacy of our proposed defense methods
in mitigating privacy leakage. The experiments are conducted on Synthetic1
dataset, with the default hyperparameter set as follows: $n=20$, $d=7$,
$\eta=0.1$, $r=0.8$.

Figure 5:  Effectiveness of Defense Methods. The yellow line represents
privacy leakage, where lower values indicate a more secure model. The blue
line represents utility loss, where lower values indicate better model
performance. The first and second columns are experiments on Local Trees and
Purity Threshold, respectively. BC: binary classification; MC: multi-class
classification. Reducing $p$ or increasing $n_{l}$ can decrease privacy
leakage while sacrificing utility.

Fig. 5 shows that both methods can trade-off model performance for privacy
protection. The lack of protection on instance distribution resulted in up to
84% of instance label leakage. As shown in Fig. 5 (a), training 10 decision
trees locally reduced privacy leakage risk by 25.1% while sacrificing only
1.6% of utility. The impact of the purity threshold is illustrated in Fig.
5(b), where we observe a decrease in privacy leakage as the active party
constructs more nodes locally.

###  VII-C Optimal Tradeoffs between Utility, Efficiency, and Privacy achieved
by CMOSB

In this section, we use CMOSB (Algo. 3) without constraints to find the Pareto
optimal solutions of hyperparameters for SecureBoost. Each solution is a set
of hyperparameters that achieves an optimal tradeoff between utility loss,
training cost, and privacy leakage.

We summarize the variables and their descriptions involved in multi-objective
optimization in Table III. Among the variables, the definitions of $n_{f}$,
$d$, $r$, and $\eta$ are the same as those used in SecureBoost [4]. $n_{l}$
refers to the number of iterations for boosting locally, and $\theta_{p}$
refers to the threshold of purity. For binary classification problems, we
further constrain the range of $\theta_{p}$ to $[0.7,1.0]$ to improve search
efficiency.

We first present the comparison between CMOSB and the baselines through 3D
plots illustrated in Fig. 6 and Fig. 7 on the four datasets (see Table I).

(a) Synthetic1

(b) DefaultCredit

(c) Synthetic2

(d) Sensorless

Figure 6:  Comparison between 3D Pareto fronts of CMOSB and GS (Grid Search).
The blue, green, and red dots represent solutions obtained by CMOSB, GS, and
ES (Empirical Selection), respectively. Solutions closer to the origin are
better.

Fig. 6 illustrates the comparison between CMOSB and Grid Search. The red,
green, and blue dots represent solutions obtained from Empirical Selection
(ES), Grid Search (GS), and CMOSB, respectively. It can be observed that the
solutions found by CMOSB dominate those found by ES and GS, indicating that
CMOSB achieves a better Pareto front (closer to the origin).

Fig. 7 illustrates the comparison between CMOSB and Bayesian optimization. The
red, orange, and blue dots represent solutions obtained from Empirical
Selection (ES), Bayesian Optimization (BO), and CMOSB, respectively. Similar
to Fig. 6, CMOSB outperforms BO and ES overall, achieving a better Pareto
front.

(a) Synthetic1

(b) DefaultCredit

(c) Synthetic2

(d) Sensorless

Figure 7:  Comparison between 3D Pareto fronts of CMOSB and BO (Bayesian
Optimization). The blue, orange, and red dots represent solutions of CMOSB,
BO, and ES, respectively. Solutions closer to the origin are better.

Figure 8:  Comparing the Pareto front of CMOSB with baseline methods in terms
of the tradeoff between Training Cost and Utility Loss. The first two columns
are for two binary classification tasks, Synthetic1 and Credit2, while the
last two columns are for multi-class classification tasks, Synthetic2, and
Sensorless. In each sub-figure, solutions closer to the bottom-left corner are
considered better.

Figure 9:  Comparing the Pareto front of our proposed CMOSB with baseline
methods in terms of the tradeoff between Privacy Leakage and Utility Loss. The
first two columns are for two binary classification tasks, Synthetic1 and
Credit2, while the last two columns are for multi-class classification tasks,
Synthetic2, and Sensorless. In each sub-figure, solutions closer to the
bottom-left corner are considered better.

To provide a more intuitive observation of the experimental results, we
project each 3D plot onto two 2D plots: one for training cost vs. utility loss
and another for privacy leakage vs. utility loss, as shown in Fig. 8 and Fig.
9, respectively. In Fig. 8 and Fig. 9, the blue, green, orange, and red dots
represent CMOSB, GS (Grid Search), BO (Bayesian Optimization), and ES
(Empirical Selection), respectively. Each dot represents a solution, and each
line represents a Pareto front.

For the trade-off between training cost and utility loss (see Fig. 8), all
four datasets demonstrate that the training cost increases as the utility loss
decreases. CMOSB (in blue) can find a better Pareto front than GS (in green),
BO (in orange), and ES (in red). More specifically, BO (in orange) can find a
set of decent solutions but is slightly inferior to CMOSB. This is because BO
optimizes one objective at a time and does not consider all three objectives
as a whole for optimization. The solutions found by GS are noticeably inferior
to CMOSB, as GS only heuristically searches for solutions. The solutions
achieved by ES are farther away from the lower-left corner, indicating that ES
performs poorly in simultaneously optimizing utility loss, training cost, and
privacy leakage. This suggests that the default hyperparameters set by FATE
[6] and VF2Boost [7] were not suitable for multi-objective SecureBoost.

For the trade-off between privacy leakage and utility loss (see Fig. 9), all
four datasets demonstrate that as the utility loss decreases, the privacy
leakage increases. CMOSB outperforms all baseline methods in terms of the
Pareto front. BO performs slightly worse than CMOSB because it is a single-
objective optimization algorithm and thus cannot simultaneously optimize
privacy leakage, utility loss, and efficiency. GS demonstrates inferior search
results, as applying grid search to optimize continuous hyperparameters is
often challenging. More specifically, the privacy protection threshold $p$,
which significantly impacts privacy leakage, is a continuous variable, and the
performance of grid search is limited in this case. ES overall performs quite
badly in preserving label privacy (the worst among all methods) because FATE
and VF2Boost were not well-prepared for defending against ICA.

TABLE IV: Hypervolume Comparison between our CMOSB and baseline methods, including ES (Empirical Selection), GS (Grid Search), and BO(Bayesian Optimization) . Baseline | Synthetic1 | Credit | Synthetic2 | Sensorless
---|---|---|---|---
ES | 0.516 | 0.094 | 0.368 | 0.134
GS | 0.826 | 0.746 | 0.706 | 0.822
BO | 0.902 | 0.900 | 0.805 | 0.964
CMOSB | 0.920 | 0.920 | 0.879 | 0.968

We also compare the hypervolume of CMOSB with those of baseline methods (see
Table IV) for a clear performance comparison between the four hyperparameter
tuning methods. We normalize the three objectives for each dataset to ensure a
fair comparison. The performance of ES varies widely across the four datasets
due to its empirical selection of default hyperparameters for SecureBoost.
While obtaining relatively stable results by searching a large number of
hyperparameters, GS suffers from a heuristically pre-specified discrete
hyperparameter search space, which is not well-suited for our proposed two
defense methods, as they are sensitive to their defense parameters (i.e.,
$n_{l}$ and $p$). BO performs better than ES and GS but worse than CMOSB
because BO optimizes each objective separately and does not consider all
objectives as a whole for optimization.

###  VII-D Multi-Objective SecureBoost under Constraints

In real-world VFL scenarios, participants typically have specific requirements
or constraints on objectives. Hence, we apply the CMOSB algorithm (with
constraints) to ensure that the Pareto optimal solutions found satisfy the
constraints as much as possible. Adding constraints focuses the search space
of the CMOSB algorithm on the feasible region, which improves the efficiency
of finding better Pareto optimal solutions.

We conduct this experiment on Synthetic1 and constrain the training cost and
privacy leakage to be below 100 seconds and 0.6, respectively. We set the
penalty coefficient to 20 (see lines 6-7 of Algorithm 3).

(a) PL Constraint

(b) TC Constraint

Figure 10:  Comparison of hypervolume between MOSB and CMOSB algorithms. TC:
training cost; PL: privacy leakage. The red line represents CMOSB, and the
blue line represents MOSB. A higher hypervolume implies that better solutions
can be found.

Fig. 10 illustrates the hypervolume comparison between CMOSB and MOSB when
applying constraints to training cost and privacy leakage, respectively. For
the privacy leakage constraint, CMOSB grows more rapidly in the first few
generations and surpasses MOSB in the final generation, indicating that it can
effectively find better Pareto solutions. For the training cost constraint,
CMOSB also surpasses MOSB after the 10th generation and maintains a lead until
the last generation.

(a) PL vs UL

(b) TC vs UL

Figure 11:  Comparison of Pareto front between MOSB and CMOSB algorithm. UL:
utility loss; TC: training cost; PL: privacy leakage. We add a constraint on
PL in Figure(a), and add a constraint on TC in Figure(b). The red line
represents CMOSB, and the blue line represents MOSB. The solutions located
closer to the bottom left corner of the graph are considered better.

We further compare the Pareto fronts (at the 40th generation) obtained by the
CMOSB and MOSB algorithms. Fig. 11(a) demonstrates the effect of adding a
privacy leakage constraint, showing a reduction of approximately 3% in privacy
leakage of the Pareto solutions at the same level of utility loss. The Pareto
front found by CMOSB in Fig. 11(b) is also superior to that found by MOSB,
especially for solutions with lower utility loss.

##  VIII Conclusion

In this paper, we address two main limitations of the SecureBoost algorithm:
privacy leakage and hyperparameter optimization. We first propose the instance
clustering attack (ICA) that can infer the labels of active party and then we
develop two defense methods that can thwart ICA. Next, we propose the
Constrained Multi-Objective SecureBoost (CMOSB) algorithm, which identifies
Pareto optimal solutions of hyperparameters for SecureBoost by simultaneously
minimizing utility loss, training cost, and privacy leakage. We conduct
experiments on four datasets to validate the effectiveness of the proposed ICA
and the corresponding defense methods. Furthermore, experimental results
demonstrate that the Pareto optimal solutions of hyperparameters found by
CMOSB outperform those obtained by the baselines in terms of the Pareto front.

## References

  * [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , 2017, pp. 1273–1282.
  * [2] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” _ACM Transactions on Intelligent Systems and Technology_ , vol. 10, no. 2, pp. 12:1–12:19, 2019.
  * [3] Y. Liu, Y. Kang, T. Zou, Y. Pu, Y. He, X. Ye, Y. Ouyang, Y. Zhang, and Q. Yang, “Vertical federated learning: Concepts, advances, and challenges,” _IEEE Transactions on Knowledge Data Engineering_ , pp. 1–20, 2024.
  * [4] K. Cheng, T. Fan, Y. Jin, Y. Liu, T. Chen, D. Papadopoulos, and Q. Yang, “Secureboost: A lossless federated learning framework,” _IEEE Intelligent Systems_ , vol. 36, no. 6, pp. 87–98, 2021.
  * [5] C. Fu, X. Zhang, S. Ji, J. Chen, J. Wu, S. Guo, J. Zhou, A. X. Liu, and T. Wang, “Label inference attacks against vertical federated learning,” in _31st USENIX Security Symposium, USENIX Security 2022_ , 2022, pp. 1397–1414.
  * [6] Y. Liu, T. Fan, T. Chen, Q. Xu, and Q. Yang, “FATE: an industrial grade platform for collaborative learning with data protection,” _Journal of Machine Learning Research_ , vol. 22, pp. 226:1–226:6, 2021.
  * [7] F. Fu, Y. Shao, L. Yu, J. Jiang, H. Xue, Y. Tao, and B. Cui, “Vf${}^{\mbox{2}}$boost: Very fast vertical federated gradient boosting for cross-enterprise learning,” in _International Conference on Management of Data_ , 2021, pp. 563–576.
  * [8] Y. Kang, H. Gu, X. Tang, Y. He, Y. Zhang, J. He, Y. Han, L. Fan, and Q. Yang, “Optimizing privacy, utility and efficiency in constrained multi-objective federated learning,” _arXiv preprint arXiv:2305.00312_ , 2023.
  * [9] X. Zhang, Y. Kang, K. Chen, L. Fan, and Q. Yang, “Trading off privacy, utility, and efficiency in federated learning,” _ACM Trans. Intell. Syst. Technol._ , vol. 14, 2023.
  * [10] W. Chen, G. Ma, T. Fan, Y. Kang, Q. Xu, and Q. Yang, “Secureboost+ : A high performance gradient boosting tree framework for large scale vertical federated learning,” _CoRR_ , vol. abs/2110.10927, 2021.
  * [11] W. Fang, D. Zhao, J. Tan, C. Chen, C. Yu, L. Wang, L. Wang, J. Zhou, and B. Zhang, “Large-scale secure XGB for vertical federated learning,” in _The 30th ACM International Conference on Information and Knowledge Management_ , 2021, pp. 443–452.
  * [12] Y. Wu, S. Cai, X. Xiao, G. Chen, and B. C. Ooi, “Privacy preserving vertical federated learning for tree-based models,” _Proceedings of the VLDB Endowment_ , vol. 13, no. 11, pp. 2090–2103, 2020.
  * [13] T. Zou, Y. Liu, Y. Kang, W. Liu, Y. He, Z. Yi, Q. Yang, and Y.-Q. Zhang, “Defending batch-level label inference and replacement attacks in vertical federated learning,” _IEEE Transactions on Big Data_ , pp. 1–12, 2022.
  * [14] S. Xie, X. Yang, Y. Yao, T. Liu, T. Wang, and J. Sun, “Label inference attack against split learning under regression setting,” _CoRR_ , vol. abs/2301.07284, 2023. [Online]. Available: https://doi.org/10.48550/arXiv.2301.07284
  * [15] P. Qiu, X. Zhang, S. Ji, T. Du, Y. Pu, J. Zhou, and T. Wang, “Your labels are selling you out: Relation leaks in vertical federated learning,” _IEEE Transactions on Dependable and Secure Computing_ , pp. 1–16, 2022.
  * [16] J. Tan, L. Zhang, Y. Liu, A. Li, and Y. Wu, “Residue-based label protection mechanisms in vertical logistic regression,” in _8th International Conference on Big Data Computing and Communications_ , 2022, pp. 356–364.
  * [17] X. Pan, Y. Tong, C. Xue, Z. Zhou, J. Du, Y. Zeng, Y. Shi, X. Zhang, L. Chen, Y. Xu, K. Xu, and W. Lv, “Hu-fu: A data federation system for secure spatial queries,” _Proceedings of the VLDB Endowment_ , vol. 15, no. 12, pp. 3582–3585, 2022.
  * [18] Y. Wang, Y. Tong, Z. Zhou, R. Zhang, S. J. Pan, L. Fan, and Q. Yang, “Distribution-regularized federated learning on non-iid data,” in _39th IEEE International Conference on Data Engineering_ , 2023, pp. 2113–2125.
  * [19] W. Zhang, Z. Zhou, Y. Wang, and Y. Tong, “Dm-pfl: Hitchhiking generic federated learning for efficient shift-robust personalization,” in _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , 2023, pp. 3396–3408.
  * [20] S. Cui, W. Pan, J. Liang, C. Zhang, and F. Wang, “Addressing algorithmic disparity and performance inconsistency in federated learning,” in _Advances in Neural Information Processing Systems_ , 2021, pp. 26 091–26 102.
  * [21] H. Zhu and Y. Jin, “Multi-objective evolutionary federated learning,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 31, no. 4, pp. 1310–1322, 2020.
  * [22] M. J. Freedman, K. Nissim, and B. Pinkas, “Efficient private matching and set intersection,” in _Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques_ , ser. Lecture Notes in Computer Science, vol. 3027, 2004, pp. 1–19.
  * [23] Y. Tong, X. Pan, Y. Zeng, Y. Shi, C. Xue, Z. Zhou, X. Zhang, L. Chen, Y. Xu, K. Xu, and W. Lv, “Hu-fu: Efficient and secure spatial queries over data federation,” _Proceedings of the VLDB Endowment_ , vol. 15, no. 6, pp. 1159–1172, 2022.
  * [24] E. Zitzler and S. Künzli, “Indicator-based selection in multiobjective search,” in _Parallel Problem Solving from Nature_ , ser. Lecture Notes in Computer Science, vol. 3242, 2004, pp. 832–842.
  * [25] A. Y. Ng, M. I. Jordan, and Y. Weiss, “On spectral clustering: Analysis and an algorithm,” in _Advances in Neural Information Processing Systems_ , 2001, pp. 849–856.
  * [26] A. Kraskov, H. Stögbauer, and P. Grassberger, “Estimating mutual information,” _Physical Review E_ , vol. 69, p. 066138, 2004.
  * [27] S. Holly, T. Hiessl, S. R. Lakani, D. Schall, C. Heitzinger, and J. Kemnitz, “Evaluation of hyperparameter-optimization approaches in an industrial federated learning system,” in _Proceedings of the 4th International Data Science Conference_ , 2022, pp. 6–13.
  * [28] J. Snoek, H. Larochelle, and R. P. Adams, “Practical bayesian optimization of machine learning algorithms,” in _Advances in Neural Information Processing Systems_ , 2012, pp. 2960–2968.
  * [29] K. Deb and A. Kumar, “Real-coded genetic algorithms with simulated binary crossover: Studies on multimodal and multiobjective problems,” _Complex Systems_ , vol. 9, no. 6, 1995.


# Comparing Abstraction in Humans and Large Language Models
Using Multimodal Serial Reproduction

Sreejan Kumar 1,2* , Raja Marjieh 3*, Byron Zhang 4, Declan Campbell1,Michael
Y. Hu2,
Umang Bhatt 2, Brenden M. Lake 2,5, Thomas L. Griffiths 3,4
1 Princeton Neuroscience Institute, 2 NYU Center for Data Science, 3 Princeton
University Dept. of Psychology
4 Princeton University Dept. of Computer Science, 5 NYU Dept. of Psychology *
equally contributing co-first authors

###### Abstract

Humans extract useful abstractions of the world from noisy sensory data.
Serial reproduction allows us to study how people construe the world through a
paradigm similar to the game of telephone, where one person observes a
stimulus and reproduces it for the next to form a chain of reproductions. Past
serial reproduction experiments typically employ a single sensory modality,
but humans often communicate abstractions of the world to each other through
language. To investigate the effect language on the formation of abstractions,
we implement a novel multimodal serial reproduction framework by asking people
who receive a visual stimulus to reproduce it in a linguistic format, and vice
versa. We ran unimodal and multimodal chains with both humans and GPT-4 and
find that adding language as a modality has a larger effect on human
reproductions than GPT-4’s. This suggests human visual and linguistic
representations are more dissociable than those of GPT-4.

Keywords: serial reproduction, Bayesian inference, multimodal models,
abstraction, vision, language

## Introduction

Abstraction is a hallmark of human intelligence that helps us make sense of
our complex environment. The ability to form abstractions has been proposed as
a key component of human cognition, and necessary for artificial intelligence
to exhibit the same ability to generalize from limited data Lake . (2017).
Large Language Models (LLMs) are sophisticated, high-performing artificial
intelligence systems that have emergent properties some claim may rival human-
level general intelligence Wei . (2022); Bubeck . (2023). However, others have
pointed out inconsistencies in their reasoning abilities Mitchell . (2023).
The difficulty of assessing these capacities highlights the need to develop
rigorous experimental tools for probing abstraction in humans and machines
Lake . (2017); Mitchell . (2023); Kumar . (2023).

Abstraction involves capturing the essential details of incoming information
that will help us generalize to future experiences while discarding less
useful information Giunchiglia Walsh (1992). The choice of what to focus on
and what to ignore can be a reflection of our prior beliefs or expectations.
Serial reproduction Bartlett (1932) is a method used to elicit such priors in
human perception and memory through a telephone-game-like experiment Xu
Griffiths (2008). People are asked to pass a piece of information to one
another in sequence, with each person reproducing the information from memory
for the next person. Studying how the information changes as it is passed
along the chain of people can be used as a window into their prior beliefs.

When using serial reproduction to study abstraction, one must consider that
abstractions are not only a noisy compression of a stimulus, but they are also
formed to communicate information to others Tessler Goodman (2019); Tessler .
(2021). In humans this is often done through language Lupyan Bergen (2016).
The extent to which our abstractions are influenced by language is a central
but unanswered question in cognitive science Quilty-Dunn . (2023); Kumar .
(2022); Lupyan . (2007). Most experiments involving human participants
constructing a serial reproduction chain (e.g.
langlois2021serial,anglada2023large) employ only one sensory modality.
Therefore, incorporating language as a transmission modality in multimodal
serial reproduction potentially provides a way to understand its influence on
human abstractions.

In this work, we explore how adding language to a visual serial reproduction
chain influences the output of that chain, comparing human participants and
GPT-4 (a contemporary LLM with visual capabilities; achiam2023gpt). To
simulate multimodal serial reproduction, participants who observed a visual
stimulus were asked to produce a textual stimulus for the next participant and
vice versa. As a result, the multimodal serial reproduction chain alternates
between the visual and language modalities. We present a theoretical analysis
showing that comparing unimodal and multimodal chains can allow us to assess
whether distinct priors are being used to make inferences in different
modalities.

To establish this comparison, we collected data from both human participants
and GPT-4 in two serial reproduction paradigms, one unimodal and one
multimodal. This allows us to compare emergent distributions from vision-only
vs. hybrid vision-language chains to see the impact of transmission through
multiple modalities. Our results show that transmission through both language
and vision has a significant impact on the level of abstraction demonstrated
within human participants’ chains but does not have as significant impact on
GPT-4, suggesting that GPT-4, unlike humans, naturally relies on language
representations by default even in a vision-only paradigm.

## Methods

### Theoretical Framework

bartlett1995remembering proposed serial reproduction to study how bias from
people’s previous experiences influences how they perceive new experiences. In
a unimodal serial reproduction study, the original stimulus is presented to
the first participant, who then reproduces it for the second participant, and
so on. Formally, serial reproduction can be interpreted as a Markov chain over
a pair of variables $(x,\mu)$ where $x$ represents the distribution of stimuli
in the world and $\mu$ represents the abstractions people infer from those
stimuli, $\cdots x_{t}\rightarrow\mu_{t}\rightarrow
x_{t+1}\rightarrow\mu_{t+1}\rightarrow\cdots$. A mathematical interpretation
of this process used by xu2010rational treats $x_{t}$ as a noisy stimulus, and
assumes humans share a prior distribution $p_{S}(\mu)$ about the world. To
reconstruct the observed stimulus $x_{t}$, humans try to estimate the true
state of the world $\mu_{t}$ by sampling the posterior distribution
$p(\mu_{t}|x_{t})$, and the next stimulus is then sampled from the likelihood
$p_{S}(x_{t+1}|\mu_{t})$. Under this assumption and ergodicity (i.e., that
there is a finite probability for reaching any one state from another), the
stationary distribution of the Markov chain over $\mu$ converges to the prior
$p_{S}(\mu)$. Related analyses for this paradigm offer similar conclusions
Jacoby McDermott (2017).

Consider next a serial reproduction process in which information is
transmitted bimodally, e.g., through images $x$ and language $\ell$. The
process unfolds as follows: at a given iteration $t$, a human participant
observes a stimulus $x_{t}$ and forms an abstraction $\mu_{t}$ about its
content which they then use to form a text description $\ell_{t+1/2}$. The
text description is then read by another participant who in turn forms an
abstraction $\mu_{t+1/2}$ and uses that abstraction to produce a new stimulus
$x_{t+1}$. In other words, we are concerned with the Markov process
$\cdots\rightarrow
x_{t}\rightarrow\mu_{t}\rightarrow\ell_{t+1/2}\rightarrow\mu_{t+1/2}\rightarrow
x_{t+1}\rightarrow\cdots$ and want to characterize the stationary distribution
of $p(x_{t+1}|x_{t})$. Following xu2010rational, we assume the agents are
Bayesian and that they use some prior knowledge to form abstractions from
language and stimuli, namely $p(\mu|x)\propto p_{S}(x|\mu)p_{S}(\mu)$ and
$p(\mu|\ell)\propto p_{L}(\ell|\mu)p_{L}(\mu)$ where $S$ and $L$ indicate
stimulus and language, respectively. The stimulus and language priors over
abstractions need not be the same (the likelihoods are by definition different
because they are defined on different input). If, however, they were aligned,
i.e. $p_{S}(\mu)=p_{L}(\mu)$ for all $\mu$, then propagation through the
additional linguistic modality does not alter the stationary distribution over
stimuli $x$. This can be verified by checking that the prior predictive
distribution $\hat{p}(x)=\int p_{S}(x|\mu)p_{S}(\mu)d\mu$ satisfies the
stationarity condition $\int
p(x_{t+1}|x_{t})\hat{p}(x_{t})dx_{t}=\hat{p}(x_{t+1})$, similar to the
unimodal case of xu2010rational. Discrepancies in the stationary distribution
over stimuli $x$ between the unimodal and multimodal serial reproduction
chains in this theoretical setup would reflect a difference in priors
$p_{L}(\mu)$ and $p_{S}(\mu)$. This suggests that comparison of the stationary
distributions produced by unimodal and multimodal chains is an effective way
of discovering differences in the way that agents construe the world across
different modalities.

Figure 1: Example Multimodal Serial Reproduction Chain in Humans. One
participant sees a stimulus and transmits a language description of the
stimulus. The next participant sees a language description and produces a
stimulus matching the description. The chain alternates between vision and
language.  Figure 2: Serial Reproduction Chains Across Modalities. Five
example human and GPT-4 chains for each paradigm.

### Human Experiments

We recruited $N=348$ participants from Prolific. Participants were required to
be native English speakers to ensure high textual data quality, and they
provided informed consent prior to participation in accordance with an
approved institional review board (IRB) protocol. We collected $100$ chains of
$10$ visual steps of both unimodal and multimodal serial reproduction. Both
conditions were intitialzed with the same set of randomly sampled boards.
Although 10 iterations can be considered on the short side, sampling-based
chains with people tend to converge much faster than their theoretical
counterparts Sanborn Griffiths (2007); Harrison . (2020). To compensate for
the chain length, we run many different chains Harrison . (2020).

In this work, we use a simple stimulus space of binary $7\times 7$ grid
patterns (Fig. 1), which has previously been used to study abstraction in
humans and machines Kumar . (2021, 2022, 2023) due to having a nice balance
between being rich enough to elicit interesting abstractions but small enough
to enable rigorous experimentation.

Unimodal Serial Reproduction: To implement unimodal serial reproduction in
humans, at each step, the participant is asked to memorize a stimulus board
for 5 seconds and tasked with reproducing the board afterwards. The new board
serves as the stimulus for the next iteration of the chain. After running all
the unimodal chains, we then collected language descriptions of all boards
produced post-hoc by having a separate set of participants give board
descriptions. Each participant completed up to 10 trials and was allowed to
visit each chain only once (to reduce trial dependence within chains).

Multimodal Serial Reproduction: In multimodal serial reproduction, a
participant can be shown either a stimulus board, or a string of textual
description. If shown a board, then they are asked to provide an accurate
textual description of the board such that the board can be reconstructed from
it. If shown a string of textual descriptions, then they are asked to
reproduce a board that most accurately illustrates the textual description.
The new board or text will serve as the stimulus for the next iteration in the
chain. Here too participants completed up to 10 trials and were allowed to
participate in a given chain once.

### Machine Experiments

To study machine priors, we use GPT-4 vision Achiam . (2023), a Large Language
Model (LLM) with multimodal capabilities. We implement the serial reproduction
chains with GPT-4 to be as close to the human experiments as possible. Just
like the human experiments, we ran $100$ unimodal and multimodal chains of
$10$ iterations.

Unimodal Serial Reproduction: To implement unimodal serial reproduction in
GPT-4, we present it an image of a $7\times 7$ binary grid and ask it to
produce the grid in matrix form, with $1$ corresponding to red tiles and $0$
corresponding to white tiles. We then use the matrix GPT-4 produced for the
next iteration’s input.

Multimodal Serial Reproduction: In multimodal serial reproduction, GPT-4 can
be shown either a stimulus board, or a string of textual description. If shown
a board, then it is asked to provide an accurate textual description of the
board. If shown a textual description, then it is asked to reproduce a board
that most accurately illustrates the textual description. The new board or
text will serve as the stimulus for the next iteration in the chain. We used
the same prompt given to human participants.

### Measures of Board Complexity

The process of human abstraction aims to compress complex stimuli or inputs to
simpler representations that enable generalization Giunchiglia Walsh (1992);
Kumar . (2022). Therefore, measuring the compressibility of the stimuli that
emerge from the serial reproduction chains can be informative of the
underlying abstract priors that generate them. There are many measures of
board complexity, so we utilize three measures from the work of
nath2023relating, which are specifically tailored to binary grid stimuli:

  1. 1.

Kolmogorov Complexity (KC): a measure formalized through algorithmic
information theory, defined as the length of the shortest computer program
that can produce the desired stimulus. The exact computation is intractable,
so most empirical methods estimate an upper bound. nath2023relating use the
Block Decomposition Method Zenil . (2018), which breaks the grid stimulus into
$4\times 4$ blocks and uses theoretically defined complexity measures of each
binary $4\times 4$ block.

  2. 2.

Shannon Entropy: a measure of the information content/complexity Shannon
(1948) of the grids using its distribution of red and white tiles:
$-(P(red)\log_{2}P(red)+P(white)\log_{2}P(white))$

  3. 3.

Local Spatial Complexity (LSC): the mean information gain of tiles having the
same color or different colors in their adjacent tiles. This takes into
account the local probabilistic spatial distribution of tiles. It is defined
as
$-\frac{1}{8}\sum_{d=1}^{8}\sum_{s_{1}=0}^{1}\sum_{s_{2}=0}^{1}P(s_{1},s_{2})_{d}\log_{2}P(s_{1}|s_{2})$
where $s_{1}$ and $s_{2}$ are adjacent tiles whose spatial relation is defined
through $d$. There are eight possible values for $d$ corresponding to the four
cardinal directions as well as four diagonals.

Each of these measures provide a slightly different window into the complexity
of a board. For example, Kolmogorov Complexity is the only measure taking into
account the algorithimic complexity of the board (e.g. algorithms to generate
the patterns). Shannon Entropy formally measures the information-theoretic
content based on the distribution of tile colors, but does not take into
account spatial information. Local Spatial Complexity is an information theory
measure more sensitive to spatial information because it looks at the local
distribution of a tile’s nearest neighbors.

## Results

### Qualitative Board Distribution

Figure 3: Most Frequent Boards Across Conditions. Numbers indicate the
frequency of the board below it.

Fig. 3 shows the most frequent boards across the four conditions. Because
there is more variance across different human participants’ responses than
GPT-4 responses, the largest frequencies of GPT-4 are typically higher than
humans. The most frequent human multimodal boards seem to be patterns that are
most easily identifiable by language, e.g., checkerboard, square shapes, and
stripes (the checkerboard pattern, in particular, seems to only show up in
multimodal chains for both humans and GPT-4) whereas unimodal boards are
patterns that are harder to describe in language. However, in the case of
GPT-4, both unimodal and multimodal patterns are more easily describable
through language.

### Chain Dynamics

Fig. 4 shows the mean distance traveled between consecutive timesteps in each
of the four types of serial reproduction chains. This can be thought of as a
measure of instantaneous velocity since it measures distance traveled within
consecutive timesteps ($dt=1$).

Figure 4: Mean Chain Velocity We computed mean instantaneous velocity of each
chain by computing the hamming distance traveled between boards of consecutive
timesteps. Error bars denote 95% confidence intervals across chains.  Figure
5: Transmitting through language has a larger effect on humans than GPT-4 (A).
95% confidence intervals for complexity measures across humans and GPT-4 for
both types of chains. GPT-4 boards typically have higher complexity.
Multimodal serial reproduction typically reduces complexity, and this
reduction is more pronounced in humans than GPT-4. (B). Decoding ($R^{2}$)
performance for predicting board complexity from the corresponding language
description’s sentence embeddings. Higher performance suggests that the
complexity of the boards can be represented in language. Decoding performance
increases from unimodal to multimodal chains and GPT-4 boards have higher
decoding performance than human boards.

We see that multimodal chains have significantly higher velocity than unimodal
chains in both conditions (human: $t(198)=4.05,p<0.0001$; GPT-4:
$t(198)=-7.01,p<0.0001$). Since the chief difference between these conditions
is the addition of language as a bottleneck between state transitions in the
chain, this shows that transmitting through language further accelerates the
sampling of the abstraction space more. GPT-4 has significantly higher chain
velocity than humans in both conditions (unimodal: $t(198)=6.97,p<0.0001$;
GPT-4: $t(198)=10.87,p<0.0001$), which may suggest that GPT-4, by default,
relies more on language representations than humans do.

### Board Complexity Analyses

We looked at the distribution of complexities across human and machine chains
for different conditions (Fig. 5A). Qualitatively, running a multimodal serial
reproduction chain seems to have a bigger effect on mean board complexity for
humans than for GPT-4 (signified by the red line having a larger slope than
the blue line). To statistically evaluate this, for each complexity measure,
we ran a two-way ANOVA with subject (human or GPT-4) and modality (unimodal
and multimodal) as factors that account for the mean complexity of the boards
(Table 1).

Table 1: Two-way ANOVAs for Board Complexity Measure | Effect | F | p |
---|---|---|---|---
KC | Modality | 6.99 | 0.009 |
KC | Subject | 65.39 |  $<$0.001 |
KC | Interaction | 4.08 | 0.044 |
Entropy | Modality | 65.94 |  $<$0.001 |
Entropy | Subject | 43.68 |  $<$0.001 |
Entropy | Interaction | 8.09 | 0.005 |
LSC | Modality | 151.49 |  $<$0.001 |
LSC | Subject | 24.09 |  $<$0.001 |
LSC | Interaction | 14.63 |  $<$0.001 |

We find all two-way interaction effects between the subject (human vs. GPT-4)
vs. modality (unimodal vs. multimodal) to be consistent in direction and
statistically significant. As seen in Fig. 5A, this effect is driven by a
tendency for there to be a greater difference between human unimodal and
multimodal board complexity than GPT-4 unimodal vs. multimodal board
complexity. We also found significant one-way effects of subject. The
direction of this effect was consistent in all measures — GPT-4 tends to have
a higher mean board complexity than humans. In addition, we also find
significant one-way effects of modality (unimodal vs. multimodal), suggesting
that additionally transmitting through language decreases board complexity.

Since the chief difference between the modality conditions (unimodal vs.
multimodal) is explicit transmission through a language description, the fact
that these conditions have a significantly larger effect on humans than GPT-4
may suggest that GPT-4 relies more on language-compatible representations than
humans, leading to a lesser effect when explicitly forcing it to transmit
through a language bottleneck. Equivalently, this may suggest that humans’
abstract vision and language priors have less overlap than GPT-4’s vision and
language priors.

### Decoding Board Complexity from Language

We now employ an analysis to see if the complexity within each of these boards
measured in Fig. 5A is the kind of complexity that can be represented in
language (Fig. 5B). To do this, we obtained pretrained LLM sentence embeddings
of each board’s corresponding language description using the
SentenceTransformers package (https://www.sbert.net/, based on
reimers2019sentence). The pretrained model we used was Microsoft’s MPNet Song
. (2020). The SentenceTransformers model maps text into a 768 dimensional
dense semantically meaningful vector space. reimers2019sentence do this by
using a contrastive objective on a dataset of semantically-paired text where
embeddings from the same pair are pushed closer and embeddings from different
pairs are pushed further apart.

In multimodal boards, we use the language description that was obtained by a
participant (or GPT-4) who viewed the board and wrote the description (see
Fig. 1). In unimodal boards, we repeated this process post-hoc after the
chains were completed by showing a separate set of participants (or GPT-4)
each unimodal board and asked them to write a language description (using the
same prompt as the participants who wrote descriptions in the multimodal chain
condition).

We then take these embeddings and train a Ridge Regression model to predict
board complexities from its corresponding sentence embedding (Fig. 5B). We use
five-fold cross validation and report mean prediction accuracy ($R^{2}$) on
the held-out test set across all five folds. The regularization parameter is
tuned using a nested five-fold cross validation procedure within the training
set (so, for each outer fold, the regularization parameter is tuned before the
test set is ever seen). Qualitatively, we see that there is a general upward
trend (more pronounced in humans than GPT-4) in decoding performance from
unimodal to multimodal boards. To quantify this effect, we repeated the two-
way ANOVA analyses employed in the last section, with subject (human vs.
GPT-4) and modality (unimodal vs. multimodal) as factors that influence the
decoding performance of the Ridge Regression model. Results are shown in Table
2.

Table 2: Two-way ANOVAs for Language Decoding Measure | Effect | F | p |
---|---|---|---|---
KC | Modality | 19.28 | 0.005 |
KC | Subject | 225.70 |  $<$0.001 |
KC | Interaction | 65.67 |  $<$0.001 |
Entropy | Modality | 11.14 | 0.004 |
Entropy | Subject | 10.24 | 0.006 |
Entropy | Interaction | 1.12 | 0.31 |
LSC | Modality | 35.75 |  $<$0.001 |
LSC | Subject | 8.84 | 0.009 |
LSC | Interaction | 1.45 | 0.25 |

The one-way effect of subject (human vs. GPT-4) was significant across all
three measures and was consistent in direction — GPT-4 decoding performance is
higher. Additionally, the one-way effect of modality (unimodal vs. multimodal)
was also significant across all three measures, showing that multimodal boards
have higher decoding performance than unimodal boards. The interaction
(subject + modality) effect was only significant in one measure, Kolmogorov
Complexity.

These results suggest two main findings. First, decoding performance of
complexity from language embeddings is generally higher in multimodal chains
than in unimodal chains. This suggests that the complexity of the multimodal
boards, compared to unimodal boards, is more the kind of complexity that can
be accounted for by language representations. Second, GPT-4 generally has a
higher decoding performance than humans. Although the complexity of GPT-4
boards are generally higher than those of humans (see previous section and
Fig. 5A), this complexity is the kind of complexity that is decodable by
language representations.

## Discussion

In this work, we explored abstractions in humans and GPT-4 using a framework
involving serial reproduction within a simple yet rich stimulus space of
binary grid boards (Fig. 1). Previously, serial reproduction has been used to
elicit human priors (e.g., langlois2021serial). Humans often share
abstractions of their sensory experience with each other through language
Tessler Goodman (2019). However, the abstractions humans build of the world
can be represented through multiple modalities Hawkins . (2023), and serial
reproduction and similar iterative methods typically only employ a single
modality. This paper presents a novel multimodal serial reproduction paradigm,
in which people alternate between transmitting through both vision and
language. This provides a way to determine the extent to which priors are
shared across modalities.

We ran both unimodal and multimodal serial reproduction chains for both humans
and GPT-4 (Fig. 2). Qualitatively, for humans, we found that multimodal chain
samples seem much easier to describe in language (Fig. 3). Quantitatively, we
found evidence that the addition of transmission through language leads to the
emergence of more compressible (and, therefore, more abstract) stimuli in the
stationary distribution (Fig. 5A). Additionally, language representations are
more predictive of the complexity of human multimodal boards than that of
unimodal boards (Fig. 5B), suggesting that, in humans, a purely unimodal
paradigm does not tap into abstractions that can be shared with language as
much as a multimodal paradigm. In contrast, GPT-4 unimodal and multimodal
boards both qualitatively seem easy to describe in language (Fig. 3).
Quantitatively, the change in complexity across unimodal and multimodal boards
is significantly less in GPT-4 than the corresponding change in humans (Fig.
5A). Language representations are more predictive of GPT-4 board complexities
than human representations (Fig. 5B).

This evidence suggests that GPT-4 abstract visual representations are much
closer to linguistic representations than those of humans. This may have
resulted from the training paradigm for GPT-4. Although the information on how
GPT-4 was trained is not fully public, many similar vision-language models are
trained on large amounts of text data and jointly match images with their
language descriptions during trainingRadford . (2021), leading to a tight
coupling between vision and language representations. The fact that human
unimodal and multimodal boards have a significantly greater difference than
those of GPT-4 (Figs. 3 and 5) suggests that humans, in contrast, have more
dissociable representations between vision and language. This may be because
the human visual system was first evolutionarily refined to support embodied
sensation and movement within the environment Cisek (2019) before
communicating sensory experience to other humans through language.

One limitation of this work is that we use a fairly constrained domain of two-
dimensional binary grids. It is possible results could differ on more
realistic visual inputs for humans as well as GPT-4’s. Our multimodal serial
reproduction framework can easily be extended to more realistic-looking visual
domains, potentially using drawing to transmit images from language Mukherjee
. (2023). Likewise, our chains were relatively short, and longer chains could
be useful as a control for the initial effect of mixing. This can be easily
addressed by deploying larger online experiments.

It is also possible to extend our work to run hybrid serial reproduction
chains with both humans and machines. This could help us see what concepts
arise from joint shared abstractions between humans and machines, which will
become increasingly relevant as AI systems become further incorporated into
our daily lives Brinkmann . (2023).

## Acknowledgements

This research project and related results were made possible with the support
of the NOMIS Foundation. S.K. is supported by a Google PhD Fellowship. M.Y.H.
is supported by an NSF Graduate Research Fellowship and NSF Award 1922658. We
thank Guy Davidson for helpful comments and feedback on the manuscript.

## References

  * Achiam . (2023) achiam2023gptAchiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, FL.others  2023\.  GPT-4 technical report GPT-4 technical report.  arXiv preprint arXiv:2303.08774.
  * Anglada-Tort . (2023) anglada2023largeAnglada-Tort, M., Harrison, PM., Lee, H. Jacoby, N.  2023\.  Large-scale iterated singing experiments reveal oral transmission mechanisms underlying music evolution Large-scale iterated singing experiments reveal oral transmission mechanisms underlying music evolution.  Current Biology3381472–1486.
  * Bartlett (1932) bartlett1995rememberingBartlett, FC.  1932\.  Remembering: A study in experimental and social psychology Remembering: A study in experimental and social psychology.  Cambridge University Press.
  * Brinkmann . (2023) brinkmann2023machineBrinkmann, L., Baumann, F., Bonnefon, JF., Derex, M., Müller, TF., Nussberger, AM.others  2023\.  Machine culture Machine culture.  Nature Human Behaviour1–14.
  * Bubeck . (2023) bubeck2023sparksBubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E.others  2023\.  Sparks of artificial general intelligence: Early experiments with GPT-4 Sparks of artificial general intelligence: Early experiments with GPT-4.  arXiv preprint arXiv:2303.12712.
  * Cisek (2019) cisek2019resynthesizingCisek, P.  2019\.  Resynthesizing behavior through phylogenetic refinement Resynthesizing behavior through phylogenetic refinement.  Attention, Perception, & Psychophysics812265–2287.
  * Giunchiglia Walsh (1992) giunchiglia1992theoryGiunchiglia, F. Walsh, T.  1992\.  A theory of abstraction A theory of abstraction.  Artificial Intelligence572-3323–389.
  * Harrison . (2020) harrison2020gibbsHarrison, P., Marjieh, R., Adolfi, F., van Rijn, P., Anglada-Tort, M., Tchernichovski, O.Jacoby, N.  2020\.  Gibbs sampling with people Gibbs sampling with people.  Advances in Neural Information Processing Systems3310659–10671.
  * Hawkins . (2023) hawkins2023visualHawkins, RD., Sano, M., Goodman, ND. Fan, JE.  2023\.  Visual resemblance and interaction history jointly constrain pictorial meaning Visual resemblance and interaction history jointly constrain pictorial meaning.  Nature Communications141.
  * Jacoby McDermott (2017) jacoby2017integerJacoby, N. McDermott, JH.  2017\.  Integer ratio priors on musical rhythm revealed cross-culturally by iterated reproduction Integer ratio priors on musical rhythm revealed cross-culturally by iterated reproduction.  Current Biology273359–370.
  * Kumar . (2022) kumar2022usingKumar, S., Correa, CG., Dasgupta, I., Marjieh, R., Hu, MY., Hawkins, R.others  2022\.  Using natural language and program abstractions to instill human inductive biases in machines Using natural language and program abstractions to instill human inductive biases in machines.  Advances in Neural Information Processing Systems35167–180.
  * Kumar . (2021) kumar2020metaKumar, S., Dasgupta, I., Cohen, J., Daw, N. Griffiths, T.  2021\.  Meta-Learning of Structured Task Distributions in Humans and Machines Meta-learning of structured task distributions in humans and machines.  International Conference on Learning Representations. International conference on learning representations.
  * Kumar . (2023) kumar2023disentanglingKumar, S., Dasgupta, I., Daw, ND., Cohen, JD. Griffiths, TL.  2023\.  Disentangling abstraction from statistical pattern matching in human and machine learning Disentangling abstraction from statistical pattern matching in human and machine learning.  PLoS computational biology198e1011316.
  * Lake . (2017) lake2017buildingLake, BM., Ullman, TD., Tenenbaum, JB. Gershman, SJ.  2017\.  Building machines that learn and think like people Building machines that learn and think like people.  Behavioral and brain sciences40.
  * Langlois . (2021) langlois2021serialLanglois, TA., Jacoby, N., Suchow, JW. Griffiths, TL.  2021\.  Serial reproduction reveals the geometry of visuospatial representations Serial reproduction reveals the geometry of visuospatial representations.  Proceedings of the National Academy of Sciences11813.
  * Lupyan Bergen (2016) lupyan2016languageLupyan, G. Bergen, B.  2016\.  How language programs the mind How language programs the mind.  Topics in Cognitive Science82408–424.
  * Lupyan . (2007) lupyan2007languageLupyan, G., Rakison, DH. McClelland, JL.  2007\.  Language is not just for talking: Redundant labels facilitate learning of novel categories Language is not just for talking: Redundant labels facilitate learning of novel categories.  Psychological Science18121077–1083.
  * Mitchell . (2023) mitchell2023comparingMitchell, M., Palmarini, AB. Moskvichev, AK.  2023\.  Comparing Humans, GPT-4, and GPT-4V On Abstraction and Reasoning Tasks Comparing humans, GPT-4, and GPT-4V on abstraction and reasoning tasks.  AAAI 2024 Workshop on”Are Large Language Models Simply Causal Parrots?”. AAAI 2024 workshop on”Are Large Language Models Simply Causal Parrots?”.
  * Mukherjee . (2023) mukherjee2023sevaMukherjee, K., Huey, H., Lu, X., Vinker, Y., Aguina-Kang, R., Shamir, A. Fan, JE.  2023\.  SEVA: Leveraging sketches to evaluate alignment between human and machine visual abstraction SEVA: Leveraging sketches to evaluate alignment between human and machine visual abstraction.  Advances in Neural Information Processing Systems Datasets and Benchmarks Track.
  * Nath . (2023) nath2023relatingNath, SS., Brändle, F., Schulz, E., Dayan, P. Brielmann, AA.  2023\.  Relating Objective Complexity, Subjective Complexity and Beauty Relating objective complexity, subjective complexity and beauty.  PsyArXiv.
  * Quilty-Dunn . (2023) quilty2023bestQuilty-Dunn, J., Porot, N. Mandelbaum, E.  2023\.  The best game in town: The reemergence of the language-of-thought hypothesis across the cognitive sciences The best game in town: The reemergence of the language-of-thought hypothesis across the cognitive sciences.  Behavioral and Brain Sciences46.
  * Radford . (2021) radford2021learningRadford, A., Kim, JW., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S.others  2021\.  Learning transferable visual models from natural language supervision Learning transferable visual models from natural language supervision.  International conference on machine learning International conference on machine learning ( 8748–8763).
  * Reimers Gurevych (2019) reimers2019sentenceReimers, N. Gurevych, I.  2019\.  Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks Sentence-bert: Sentence embeddings using siamese bert-networks.  Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (EMNLP-IJCNLP).
  * Sanborn Griffiths (2007) sanborn2007markovSanborn, A. Griffiths, T.  2007\.  Markov Chain Monte Carlo with people Markov Chain Monte Carlo with people.  Advances in Neural Information Processing Systems20.
  * Shannon (1948) shannon1948mathematicalShannon, CE.  1948\.  A mathematical theory of communication A mathematical theory of communication.  The Bell System Technical Journal273379–423.
  * Song . (2020) song2020mpnetSong, K., Tan, X., Qin, T., Lu, J. Liu, TY.  2020\.  Mpnet: Masked and permuted pre-training for language understanding Mpnet: Masked and permuted pre-training for language understanding.  Advances in Neural Information Processing Systems3316857–16867.
  * Tessler Goodman (2019) tessler2019languageTessler, MH. Goodman, ND.  2019\.  The language of generalization. The language of generalization.  Psychological Review1263.
  * Tessler . (2021) tessler2021learningTessler, MH., Madeano, J., Tsividis, PA., Harper, B., Goodman, ND. Tenenbaum, JB.  2021\.  Learning to solve complex tasks by growing knowledge culturally across generations Learning to solve complex tasks by growing knowledge culturally across generations.  arXiv preprint arXiv:2107.13377.
  * Wei . (2022) wei2022emergentWei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S.others  2022\.  Emergent Abilities of Large Language Models Emergent abilities of large language models.  Transactions on Machine Learning Research.
  * Xu Griffiths (2008) xu2008memoryXu, J. Griffiths, T.  2008\.  How memory biases affect information transmission: A rational analysis of serial reproduction How memory biases affect information transmission: A rational analysis of serial reproduction.  Advances in Neural Information Processing Systems21.
  * Xu Griffiths (2010) xu2010rationalXu, J. Griffiths, TL.  2010\.  A rational analysis of the effects of memory biases on serial reproduction A rational analysis of the effects of memory biases on serial reproduction.  Cognitive psychology602107–126.
  * Zenil . (2018) zenil2018decompositionZenil, H., Hernández-Orozco, S., Kiani, NA., Soler-Toscano, F., Rueda-Toicen, A. Tegnér, J.  2018\.  A decomposition method for global evaluation of Shannon entropy and local estimations of algorithmic complexity A decomposition method for global evaluation of shannon entropy and local estimations of algorithmic complexity.  Entropy208.

## Appendix

### GPT4v Prompts

The prompt for the unimodal reproduction chains was:

> This image is a 7x7 grid represented as an image of red and white tiles. Red
> corresponds to 1 and white corresponds to 0. Please print the grid
> represented as a 2-d matrix of 1s (red) and 0s (white). Be as accurate as
> possible. Only respond with the matrix such that the output can be accepted
> by np.loadtxt. No quotation marks.

The prompt for the language multimodal reproduction chain step was:

> The image presented here is a 7x7 grid of red and white tiles. Please write
> a description of the grid such that a person reading the description should
> be able to reconstruct the board. In doing so, please keep in mind the
> following instructions:
>
> Describe all important details relevant for reconstruction. Try to use
> simple instructions.
>
> Descriptions should contain at least 5 words.
>
> Descriptions should contain at least 4 unique words.

The prompt for the vision multimodal reproduction chain step was:

> You are going to be given a description of a 7x7 grid of red and white
> tiles. Please print the grid being described represented as a 2-d matrix of
> 1s (red) and 0s (white). Red corresponds to 1 and white corresponds to 0. Be
> as accurate as possible. Only respond with the matrix such that the output
> can be accepted by np.loadtxt. No quotation marks. Here is the description:
> $<$insert description from language step $>$