Linear Mode Connectivity in Differentiable Tree Ensembles

## Abstract

Abstract Linear Mode Connectivity (LMC) refers to the phenomenon that performance remains consistent for linearly interpolated models in the parameter space. For independently optimized model pairs from different random initializations, achieving LMC is considered crucial for validating the stable success of the non-convex optimization in modern machine learning models and for facilitating practical parameter-based operations such as model merging.
While LMC has been achieved for neural networks by considering the permutation invariance of neurons in each hidden layer, its attainment for other models remains an open question.
In this paper, we first achieve LMC for soft tree ensembles , which are tree-based differentiable models extensively used in practice.
We show the necessity of incorporating two invariances: subtree flip invariance and splitting order invariance , which do not exist in neural networks but are inherent to tree architectures, in addition to permutation invariance of trees.
Moreover, we demonstrate that it is even possible to exclude such additional invariances while keeping LMC by designing decision list -based tree architectures, where such invariances do not exist by definition.
Our findings indicate the significance of accounting for architecture-specific invariances in achieving LMC.

## 1 Introduction

A non-trivial empirical characteristic of modern machine learning models trained using gradient methods is that models trained from different random initializations could become functionally almost equivalent, even though their parameter representations differ.
If the outcomes of all training sessions converge to the same local minima, this empirical phenomenon can be understood. However, considering the complex non-convex nature of the loss surface, the optimization results are unlikely to converge to the same local minima.
In recent years, particularly within the context of neural networks, the transformation of model parameters while preserving functional equivalence has been explored by considering the *permutation invariance* of neurons in each hidden layer [, ]. Notably, only a slight performance degradation has been observed when using weights derived through linear interpolation between permuted parameters obtained from different training processes [, ]. This demonstrates that the trained models reside in different, yet functionally equivalent, local minima.
This situation is referred to as *Linear Mode Connectivity* (LMC) [].
From a theoretical perspective, LMC is crucial for supporting the stable and successful application of non-convex optimization. In addition, LMC also holds significant practical importance, enabling techniques such as model merging [, ] by weight-space parameter averaging.

Although neural networks are most extensively studied among the models trained using gradient methods, other models also thrive in real-world applications. A representative is tree ensemble models, such as random forests []. While they are originally trained by not gradient but greedy algorithms, differentiable *soft tree ensembles*, which learn parameters of the entire model through gradient-based optimization, have recently been actively studied. Not only empirical studies regarding accuracy and interpretability [, , ], but also theoretical analyses have been performed [, ].
Moreover, the differentiability of soft trees allows for integration with various deep learning methodologies, including fine-tuning [], dropout [], and various stochastic gradient descent methods [, ]. Furthermore, the soft tree represents the most elementary form of a hierarchical mixture of experts [, , ]. Investigating soft tree models not only advances our understanding of this particular structure but also contributes to broader research into essential technological components critical for the development of large-scale language models [].

Figure: Figure 1: A representative experimental result on the MiniBooNE [] dataset (left) and conceptual diagram of the LMC for tree ensembles (right).

A research question that we tackle in this paper is: “Can LMC be achieved for soft tree ensembles?”.
Our empirical results, which are highlighted with a green line in the top left panel of Figure 1, clearly show that the answer is “Yes”.
This plot shows the variation in test accuracy when interpolating weights of soft oblivious trees, perfect binary soft trees with shared parameters at each depth, trained from different random initializations.
The green line is obtained by our method introduced in this paper, where there is almost zero performance degradation. Furthermore, as shown in the bottom left panel of Figure 1, the performance can even improve when interpolating between models trained on split datasets.

The key insight is that, when performing interpolation between two model parameters, considering only tree permutation invariance,
which corresponds to the permutation invariance of neural networks, is *not sufficient* to achieve LMC, as shown in the orange lines in the plots. An intuitive understanding of this situation is also illustrated in the right panel of Figure 1.
To achieve LMC, that is, the green lines, we show that two additional invariances beyond tree permutation, *subtree flip invariance* and *splitting order invariance*, which inherently exist for tree architectures, should be accounted for.

Moreover, we demonstrate that it is possible to exclude such additional invariances while preserving LMC by modifying tree architectures.
We realize such an architecture based on *a decision list*, a binary tree structure where branches extend in only one direction.
By designating one of the terminal leaves as an empty node, we introduce a customized decision list that omits both subtree flip invariance and splitting order invariance, and empirically show that this can achieve LMC by considering only tree permutation invariance.
Since incorporating additional invariances is computationally expensive, we can efficiently perform weight-space averaging in model merging on our customized decision lists.

Our contributions are summarized as follows:

- •
First achievement of LMC for tree ensembles with accounting for additional invariances beyond tree permutation.
- •
Development of a decision list-based tree architecture that does not involve the additional invariances.
- •
A thorough empirical investigation of LMC across various tree architectures, invariances, and real-world datasets.

## 2 Preliminary

We prepare the basic concepts of LMC and soft tree ensembles.

### 2.1 Linear Mode Connectivity

Let us consider two models, $A$ and $B$, that have the same architecture.
In the context of evaluating LMC, the concept of a “barrier” is frequently used [, ].
Let $\boldsymbol{\Theta}_{A},\boldsymbol{\Theta}_{B}\in\mathbb{R}^{P}$ be vectorized parameters of models $A$ and $B$, respectively, for $P$ parameters.
Assume that $\mathcal{C}:\mathbb{R}^{P}\rightarrow\mathbb{R}$ measures the performance of the model, such as accuracy, given its parameter vector.
If higher values of $\mathcal{C}(\cdot)$ mean better performance, the barrier between two parameter vectors $\boldsymbol{\Theta}_{A}$ and $\boldsymbol{\Theta}_{B}$ is defined as:

$$ $\mathcal{B}(\boldsymbol{\Theta}_{A},\boldsymbol{\Theta}_{B})=\sup_{\lambda\in[ 0,1]}\left[\,\lambda\mathcal{C}(\boldsymbol{\Theta}_{A})+(1-\lambda)\mathcal{C }(\boldsymbol{\Theta}_{B})-\mathcal{C}(\lambda\boldsymbol{\Theta}_{A}+(1- \lambda)\boldsymbol{\Theta}_{B})\,\right].$ (1) $$

We can simply reverse the subtraction order if lower values of $\mathcal{C}(\cdot)$ mean better performance like loss.

Several techniques have been developed to reduce barriers by transforming parameters while preserving functional equivalence.
Two main approaches are *activation matching* (AM) and *weight matching* (WM). AM takes the behavior of model inference into account, while WM simply compares two models using their parameters. The validity of both AM and WM has been theoretically supported []. Numerous algorithms are available for implementing AM and WM. For instance, [] uses a formulation based on the Linear Assignment Problem (LAP) to find suitable permutations, while [] employs a differentiable formulation that allows for the optimization of permutations using gradient-based methods.

Existing research has focused exclusively on neural network architectures such as multi-layer perceptrons (MLP) and convolutional neural networks (CNN). No study has been conducted from the perspective of linear mode connectivity for soft tree ensembles.

### 2.2 Soft Tree Ensemble

Unlike typical hard decision trees, which explicitly determine the data flow to the right or left at each splitting node, soft trees represent the proportion of data flowing to the right or left as continuous values between 0 and 1. This approach enables a differentiable formulation.

We use a $\operatorname{sigmoid}$ function, $\sigma:\mathbb{R}\to(0,1)$ to formulate a function $\mu_{m,\ell}(\boldsymbol{x}_{i},\boldsymbol{w}_{m},\boldsymbol{b}_{m}):\mathbb
{R}^{F}\times\mathbb{R}^{F\times\mathcal{N}}\times\mathbb{R}^{1\times\mathcal{
N}}\to(0,1)$ that represents the proportion of the $i$th data point $\boldsymbol{x}_{i}$ flowing to the $\ell$th leaf of the $m$th tree as a result of soft splittings:

$$ $\displaystyle\mu_{m,\ell}(\boldsymbol{x}_{i},\boldsymbol{w}_{m},\boldsymbol{b} _{m})\!=\!\prod_{n=1}^{\mathcal{N}}{\underbrace{\sigma(\boldsymbol{w}_{m,n}^{ \top}\boldsymbol{x}_{i}+b_{m,n})}_{\text{{flow to the left}}}}^{\mathds{1}_{ \ell\swarrow n}}{\underbrace{(1-\sigma(\boldsymbol{w}_{m,n}^{\top}\boldsymbol{ x}_{i}+b_{m,n}))}_{\text{{flow to the right}}}}^{\mathds{1}_{n\searrow\ell}},$ (2) $$

where $\mathcal{N}$ denotes the number of splitting nodes in each tree. The parameters $\boldsymbol{w}_{m,n}\in\mathbb{R}^{F}$ and $b_{m,n}\in\mathbb{R}$ correspond to the feature selection mask and splitting threshold value for $n$th node in a $m$th tree, respectively. The expression $\mathds{1}_{\ell\swarrow n}$ (resp. $\mathds{1}_{n\searrow\ell}$) is an indicator function that returns 1 if the $\ell$th leaf is positioned to the left (resp. right) of a node $n$, and 0 otherwise.

If parameters are shared across all splitting nodes at the same depth, such perfect binary trees are called *oblivious trees*. Mathematically, $\boldsymbol{w}_{m,n}=\boldsymbol{w}_{m,n^{\prime}}$ and $b_{m,n}=b_{m,n^{\prime}}$ for any nodes $n$ and $n^{\prime}$ at the same depth in an oblivious tree. Oblivious trees can significantly reduce the number of parameters from an exponential to a linear order of the tree depth, and they are actively used in practice [, ].

To classify $C$ categories, the output of the $m$th tree is computed by the function $f_{m}:\mathbb{R}^{F}\times\mathbb{R}^{F\times\mathcal{N}}\times\mathbb{R}^{1
\times\mathcal{N}}\times\mathbb{R}^{C\times\mathcal{L}}\to\mathbb{R}^{C}$ as sum of the leaf parameters $\boldsymbol{\pi}_{m,\ell}$ weighted by the outputs of $\mu_{m,\ell}(\boldsymbol{x}_{i},\boldsymbol{w}_{m},\boldsymbol{b}_{m})$:

$$ $\displaystyle f_{m}(\boldsymbol{x}_{i},\boldsymbol{w}_{m},\boldsymbol{b}_{m}, \boldsymbol{\pi}_{m})=\sum_{\ell=1}^{\mathcal{L}}\boldsymbol{\pi}_{m,\ell}\mu_ {m,\ell}(\boldsymbol{x}_{i},\boldsymbol{w}_{m},\boldsymbol{b}_{m}),$ (3) $$

where $\mathcal{L}$ is the number of leaves in a tree. By combining this function for $M$ trees, we realize the function $f:\mathbb{R}^{F}\times\mathbb{R}^{M\times F\times\mathcal{N}}\times\mathbb{R}^
{M\times 1\times\mathcal{N}}\times\mathbb{R}^{M\times C\times\mathcal{L}}\to
\mathbb{R}^{C}$ as an ensemble model consisting of $M$ trees:

$$ $\displaystyle f(\boldsymbol{x}_{i},\boldsymbol{w},\boldsymbol{b},\boldsymbol{ \pi})=\sum_{m=1}^{M}f_{m}(\boldsymbol{x}_{i},\boldsymbol{w}_{m},\boldsymbol{b} _{m},\boldsymbol{\pi}_{m}),$ (4) $$

with the parameters $\boldsymbol{w}=(\boldsymbol{w}_{1},\dots,\boldsymbol{w}_{M})$, $\boldsymbol{b}=(\boldsymbol{b}_{1},\dots,\boldsymbol{b}_{M})$, and $\boldsymbol{\pi}=(\boldsymbol{\pi}_{1},\dots,\boldsymbol{\pi}_{M})$ being randomly initialized.

Despite the apparent differences, there are correspondences between MLPs and soft tree ensemble models.
The formulation of a soft tree ensemble with $D=1$ is:

$$ $\displaystyle f(\boldsymbol{x}_{i},\boldsymbol{w},\boldsymbol{b},\boldsymbol{ \pi})$ $\displaystyle=\sum_{m=1}^{M}\Bigl{(}\,\sigma(\boldsymbol{w}_{m,1}^{\top} \boldsymbol{x}_{i}+b_{m,1})\boldsymbol{\pi}_{m,1}+(1-\sigma(\boldsymbol{w}_{m, 1}^{\top}\boldsymbol{x}_{i}+b_{m,1}))\boldsymbol{\pi}_{m,2}\,\Bigr{)}$ $\displaystyle=\sum_{m=1}^{M}\Bigl{(}\,(\boldsymbol{\pi}_{m,1}-\boldsymbol{\pi} _{m,2})\sigma(\boldsymbol{w}_{m,1}^{\top}\boldsymbol{x}_{i}+b_{m,1})+ \boldsymbol{\pi}_{m,2}\,\Bigr{)}.$ (5) $$

When we consider the correspondence between $\boldsymbol{\pi}_{m,1}-\boldsymbol{\pi}_{m,2}$ in tree ensembles and second layer weights in the two-layer perceptron, the tree ensembles model matches to the two-layer perceptron. It is clear from the formulation that the permutation of hidden neurons in a neural network corresponds to the rearrangement of trees in a tree ensemble.

## 3 Invariances Inherent to Tree Ensembles

In this section, we discuss additional invariances inherent to trees (Section 3.1) and introduce a matching strategy specifically for tree ensembles (Section 3.2). We also show that the presence of additional invariances varies depending on the tree structure, and we present tree structures where no additional invariances beyond tree permutation exist (Section 3.3).

### 3.1 Parameter modification processes that maintains functional equivalence in tree ensembles

First, we clarify what invariances should be considered for tree ensembles, which are expected to reduce the barrier significantly if taken into account.
When we consider perfect binary trees, there are three types of invariance:

Figure: Figure 2: (a) Subtree flip invariance. (b) Splitting order invariance for an oblivious tree.

- •
Tree permutation invariance.
In Equation (4), the behavior of the function does not change even if the order of the $M$ trees is altered. This corresponds to the permutation of internal nodes in neural networks, which has been a subject of active interest in previous studies on LMC.
- •
Subtree flip invariance.
When the left and right subtrees are swapped simultaneously with the inversion of the inequality sign at the split, the functional behavior remains unchanged, which we refer to *subtree flip invariance*. Figure 2(a) presents a schematic diagram of this invariance, which is not found in neural networks but is unique to binary tree-based models. Since $\sigma(-c)=1-\sigma(c)$ for $c\in\mathbb{R}$ due to the symmetry of $\operatorname{sigmoid}$, the inversion of the inequality is achieved by inverting the signs of $\boldsymbol{w}_{m,n}$ and $b_{m,n}$. [] also focused on the sign of weights, but in a different way from ours. They pay attention to the amount of change from the parameters at the start of fine-tuning, rather than discussing the sign of the parameters.
- •
Splitting order invariance.
Oblivious trees share parameters at the same depth, which means that the decision boundaries are straight lines without any bends. With this characteristic, even if the splitting rules at different depths are swapped, functional equivalence can be achieved if the positions of leaves are also swapped appropriately as shown in Figure 2(b).
This invariance does not exist for non-oblivious perfect binary trees without parameter sharing, as the behavior of the decision boundary varies depending on the splitting order.

Note that MLPs also have an additional invariance beyond just permutation. Particularly in MLPs that employ ReLU as an activation function, the output of each layer changes linearly with a zero crossover. Therefore, it is possible to modify parameters without changing functional behavior by multiplying the weights in one layer by a constant and dividing the weights in the previous layer by the same constant.
However, since the soft tree is based on the $\operatorname{sigmoid}$ function, this invariance does not apply.
Previous studies [, , ] have consistently achieved significant reductions in barriers without accounting for this scale invariance. One potential reason is that changes in parameter scale are unlikely due to the nature of optimization via gradient descent. Conversely, when we consider additional invariances inherent to trees, the scale is equivalent to the original parameters.

### 3.2 Matching Strategy

Figure: Figure 3: Weighting strategy.

Here, we propose a matching strategy for binary trees.
When considering invariances, it is necessary to compare multiple functionally equivalent trees and select the most suitable one for achieving LMC. Although comparing tree parameters is a straightforward approach, since the contribution of all the parameters in a tree is not equal, we apply weighting for each node for better matching. By interpreting a tree as a rule set with shared parameters as shown in Figure 3, we determine the weight of each splitting node by counting the number of leaves to which the node affects. For example, in the case of the left example in Figure 3, the root node affects eight leaves, nodes at depth $2$ affect four leaves, and nodes at depth $3$ affect two leaves. This strategy can apply to even trees other than perfect binary trees. For example, in the right example of Figure 3, the root node affects four leaves, a node at depth $2$ affects three leaves, and a node at depth $3$ affects two leaves.

In this paper, we employ the LAP, which is used as a standard benchmark [] for matching algorithms. The procedures for AM and WM are as follows. Detailed algorithms (Algorithms 1 and 2) are described in Section A in the supplementary material.

- •
Activation Matching (Algorithm 1).
In trees, there is nothing that directly corresponds to the activations in neural networks. However, by treating the output of each individual tree as an activation value of a neural network, it is possible to optimize the permutation of trees while examining their output similarities.
Regarding subtree flip and splitting order invariances, it is possible to find the optimal pattern from all the possible patterns of flips and changes in the splitting order. Since the tree-wise output remains unchanged, the similarity between each tree, generated by considering additional invariances, and the target tree is evaluated based on the inner product of parameters while applying node-wise weighting.
- •
Weight Matching (Algorithm 2).
Similar to AM, WM also involves applying weighting while extracting the optimal pattern by exploring possible flipping and ordering patterns. Although it is necessary to solve the LAP multiple times for each layer in MLPs [], tree ensembles require only a single run of the LAP since there are no layers.

The time complexity of solving the LAP is $\mathcal{O}(M^{3})$ using a modified Jonker-Volgenant algorithm without initialization [], implemented in SciPy [], where $M$ is the number of trees.
If only considering tree permutation, this process needs to be performed only once in both WM and AM. However, when considering additional invariances, we need to solve the LAP for each pattern generated by considering these additional invariances.
In a non-oblivious perfect binary tree with depth $D$, there are $2^{D}-1$ splitting nodes, leading to $2^{2^{D}-1}$ possible combinations of sign flips. Additionally, in the case of oblivious trees, there are $D!$ different patterns of splitting order invariance. Therefore, for large values of $D$, conducting a brute-force search becomes impractical.

In Section 3.3, we will discuss methods to eliminate additional invariance by adjusting the tree structure. This enables efficient matching even for deep models. Additionally, in Section 4.2, we will present numerical experiment results and discuss that the practical motivation to apply these algorithms is limited when targeting deep perfect binary trees.

### 3.3 Architecture-dependency of the Invariances

Figure: Figure 4: Tree architecture where neither subtree flip invariance nor splitting order invariance exists.

In previous subsections, tree architectures are fixed to perfect binary trees as they are most commonly and practically used in soft trees.
However, tree architectures can be flexible as we have shown in the right example in Figure 3, and here we show that we can specifically design tree architecture that has neither the subtree flip nor splitting order invariances. This allows efficient matching as considering such two invariances is computationally expensive.

**Table 1: Invariances inherent to each model architecture.**
|  | Perm | Flip | Order |
| --- | --- | --- | --- |
| Non-Oblivious Tree | $\checkmark$ | $\checkmark$ | $\times$ |
| Oblivious Tree | $\checkmark$ | $\checkmark$ | $\checkmark$ |
| Decision List | $\checkmark$ | $(\checkmark)$ | $\times$ |
| Decision List (Modified) | $\checkmark$ | $\times$ | $\times$ |

Our idea is to modify a *decision list* shown on the left side of Figure 4, which is a tree structure where branches extend in only one direction. Due to this asymmetric structure, the number of parameters does not increase exponentially with the depth, and the splitting order invariance does not exist.
Moreover, subtree flip invariance also does not exist for any internal nodes except for the terminal splitting node, as shown in the left side of Figure 4. To completely remove this invariance, we virtually eliminate one of the terminal leaves by leaving the node empty, that is, a fixed prediction value of zero, as shown on the right side of Figure 4.
Therefore only permutation invariance exists for our proposed architecture. We summarize invariances inherent to each model architecture in Table 1.

## 4 Experiment

We empirically evaluate barriers in soft tree ensembles to examine LMC.

### 4.1 Setup

Datasets.
In our experiments, we employed Tabular-Benchmark [], a collection of tabular datasets suitable for evaluating tree ensembles. Details of datasets are provided in Section B in the supplementary material.
As proposed in [], we randomly sampled $10,000$ instances for train and test data from each dataset. If the dataset contains fewer than $20,000$ instances, they are randomly divided into halves for train and test data. We applied quantile transformation to each feature and standardized it to follow a normal distribution.

Hyperparameters.
We used three different learning rates $\eta\in\{0.01,0.001,0.0001\}$ and adopted the one that yields the highest training accuracy for each dataset.
The batch size is set at $512$. It is known that the optimal settings for the learning rate and batch size are interdependent []. Therefore, it is reasonable to fix the batch size while adjusting the learning rate.
During AM, we set the amount of data used for random sampling to be the same as the batch size, thus using $512$ samples to measure the similarity of the tree outputs. As the number of trees $M$ and their depths $D$ vary for each experiment, these details will be specified in the experimental results section. During training, we minimized cross-entropy using Adam [] with its default hyperparameters(^1^11[https://pytorch.org/docs/stable/generated/torch.optim.Adam.html](https://pytorch.org/docs/stable/generated/torch.optim.Adam.html)). Training is conducted for $50$ epochs.
To measure the barrier using Equation (1), experiments were conducted by interpolating between two models with $\lambda\in\{0,1/24,\ldots,23/24,1\}$, which has the same granularity as in [].

Randomness.
We conducted experiments with five different random seed pairs: $r_{A}\in\{1,3,5,7,9\}$ and $r_{B}\in\{2,4,6,8,10\}$.
As a result, the initial parameters and the contents of the data mini-batches during training are different in each training. In contrast to spawning [] that branches off from the exact same model partway through, we used more challenging practical conditions. The parameters $\boldsymbol{w}$, $\boldsymbol{b}$, and $\boldsymbol{\pi}$ were randomly initialized using a uniform distribution, identical to the procedure for a fully connected layer in the MLP(^2^22[https://pytorch.org/docs/stable/generated/torch.nn.Linear.html](https://pytorch.org/docs/stable/generated/torch.nn.Linear.html)).

Resources.
All experiments were conducted on a system equipped with an Intel Xeon E5-2698 CPU at 2.20 GHz, 252 GB of memory, and Tesla V100-DGXS-32GB GPU, running Ubuntu Linux (version 4.15.0-117-generic).

### 4.2 Results for Perfect Binary Trees

Figure: Figure 5: Barriers averaged across 16 datasets with respect to considered invariances for non-oblivious (top row) and oblivious (bottom row) trees. The error bars show the standard deviations of 5 executions.

Figure 5 shows how the barrier between two perfect binary tree model pairs changes in each operation.
The vertical axis of each plot in Figure 5 shows the averaged barrier over datasets for each considered invariance. The results for both the oblivious and non-oblivious trees are plotted separately in a vertical layout. The panels on the left display the results when the depth $D$ of the tree varies, keeping $M=256$ constant. The panels on the right show the results when the number of trees $M$ varies, with $D$ fixed at $2$.
For both oblivious and non-oblivious trees, we observed that the barrier significantly decreases as the considered invariances increase. Focusing on the test data results, after accounting for various invariances, the barrier is nearly zero, indicating that LMC has been achieved.

Figure: Figure 6: Interpolation curves of test accuracy for oblivious trees on 16 datasets from Tabular-Benchmark []. Two model pairs are trained with on the same dataset. The error bars show the standard deviations of $5$ executions. We used $M=256$ trees with a depth $D=2$.

In particular, the difference between the case of only permutation and the case where additional invariances are considered tends to be larger in the case of AM. This is because parameter values are not used during the rearrangement of the tree in AM.
Additionally, it has been observed that the barrier increases as trees become deeper, and the barrier decreases as the number of trees increases. These behaviors correspond to the changes observed in neural networks when the depth varies or when the width of hidden layers increases [, ].
Figure 6 shows interpolation curves when using AM in oblivious trees with $D=2$ and $M=256$. Other detailed results, such as performance for each dataset, are provided in Section C in the supplementary material.

Figure: Figure 7: Interpolation curves of test accuracy for oblivious trees on 16 datasets from Tabular-Benchmark []. Two model pairs are trained on split datasets with different class ratios. The error bars show the standard deviations of $5$ executions. We used $M=256$ trees with a depth $D=2$.

Furthermore, we conducted experiments with split data following the protocol in [, ], where the initial split consists of randomly sampled 80% negative and 20% positive instances, and the second split inverts these ratios. There is no overlap between the two split datasets.
We trained two model pairs using these separately split datasets and observed an improvement in performance by interpolating their parameters. Figure 7 illustrates the interpolation curves under AM in oblivious trees with parameters $D=2$ and $M=256$. We can observe that considering additional invariances improves performance after interpolation.
Note that the data split is configured to remain consistent even when the training random seeds differ. Detailed results for each dataset using WM or AM are provided in Section C of the supplementary material.

**Table 2: Barriers, accuracies, and model sizes for MLP, non-oblivious trees, and oblivious trees.**
|  | MLP |  |  |  |
| --- | --- | --- | --- | --- |
|  | Barrier |  |  |  |
| Depth | Naive | Perm [] | Accuracy | Size |
| 1 | 8.755 ± 0.877 | 0.491 ± 0.062 | 76.286 ± 0.094 | 12034 |
| 2 | 15.341± 1.125 | 2.997 ± 0.709 | 75.981 ± 0.139 | 77826 |
| 3 | 15.915 ± 2.479 | 5.940 ± 2.153 | 75.935 ± 0.117 | 143618 |

Table 2 compares the average test barriers of an MLP with a ReLU activation function, whose width is equal to the number of trees, $M=256$. The procedure for MLPs follows that described in Section 4.1. The permutation for MLPs is optimized using the method described in []. Since [] indicated that WM outperforms AM in neural networks, WM was used for the comparison.
Overall, tree models exhibit smaller barriers compared to MLPs while keeping similar accuracy levels. It is important to note that MLPs with $D>1$ tend to have more parameters at the same depth compared to trees, leading to more complex optimization landscapes. Nevertheless, the barrier for the non-oblivious tree at $D=3$ is smaller than that for the MLP at $D=2$, even with more parameters. Furthermore, at the same depth of $D=1$, tree models have a smaller barrier. Here, the model size is evaluated using $F=44$, the average input feature size of 16 datasets used in the experiments.

In Section 3.2, we have shown that considering additional invariances for deep perfect binary trees is computationally challenging, which may suggest developing heuristic algorithms for deep trees. However, we consider it is rather a low priority, supported by our observations that the barrier tends to increase as trees deepen even if we consider invariances. This trend indicates that deep models are fundamentally less important for model merging considerations.
Furthermore, deep perfect binary trees are rarely used in practical scenarios. [] have demonstrated that generalization performance degrades with increasing depth in perfect binary trees due to the degeneracy of the Neural Tangent Kernel (NTK) []. This evidence further supports the preference for shallow perfect binary trees, and increasing the number of trees can enhance the expressive power while reducing barriers.

### 4.3 Results for Decision Lists

Figure: Figure 8: Averaged barrier for 16 datasets as a function of tree depth. The error bars show the standard deviations of 5 executions. The solid line represents the barrier in train accuracy, while the dashed line represents the barrier in test accuracy.

We present empirical results of the original decision lists and our modified decision lists, as shown in Figure 4.
As we have shown in Table 1, they have fewer invariances.

**Table 3: Barriers averaged for 16 datasets under WM with $D=2$ and $M=256$.**
|  | Train | Test |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | Barrier |  | Barrier |  |  |  |  |  |
| Architecture | Naive | Perm | Ours | Accuracy | Naive | Perm | Ours | Accuracy |
| Non-Oblivious Tree | 13.079 ± 0.755 | 4.707 ± 0.332 | 3.303 ± 0.104 | 85.646 ± 0.090 | 6.801 ± 0.464 | 0.811 ± 0.333 | 0.455 ± 0.105 | 76.631 ± 0.052 |
| Oblivious Tree | 14.580 ± 1.108 | 4.834 ± 0.176 | 2.874 ± 0.108 | 85.808 ± 0.146 | 7.881 ± 0.866 | 0.919 ± 0.093 | 0.348 ± 0.172 | 76.623 ± 0.042 |
| Decision List | 13.835 ± 0.788 | 3.687 ± 0.230 | — | 85.337 ± 0.134 | 7.513 ± 0.944 | 0.436 ± 0.120 | — | 76.629 ± 0.119 |
| Decision List (Modified) | 12.922 ± 1.131 | 3.328 ± 0.204 | — | 85.563 ± 0.141 | 6.734 ± 1.096 | 0.468 ± 0.150 | — | 76.773 ± 0.051 |

Figure 8 illustrates barriers as a function of depth, considering only permutation invariance, with $M$ fixed at $256$. In this experiment, we have excluded non-oblivious trees from comparison as the number of their parameters exponentially increases as trees deepen, making them infeasible computation.
Our proposed modified decision lists reduce the barrier more effectively than both oblivious trees and the original decision lists.
However, barriers of the modified decision lists are still larger than those obtained by considering additional invariances with perfect binary trees. Tables LABEL:tbl:wm_models and LABEL:tbl:am_models show the averaged barriers for 16 datasets, with $D=2$ and $M=256$. Although barriers of modified decision lists are small when considering only permutations (Perm), perfect binary trees such as oblivious trees with additional invariances (Ours) exhibit smaller barriers, which supports the validity of using oblivious trees as in [, ]. To summarize, when considering the practical use of model merging, if the goal is to prioritize efficient computation, we recommend using our proposed decision list. Conversely, if the goal is to prioritize barriers, it would be preferable to use perfect binary trees, which have a greater number of invariant operations that maintain the functional behavior.

## 5 Conclusion

We have presented the first investigation of LMC for soft tree ensembles.
We have identified additional invariances inherent in tree architectures and empirically demonstrated the importance of considering these factors.
Achieving LMC is crucial not only for understanding the behavior of non-convex optimization from a learning theory perspective but also for implementing practical techniques such as model merging.
By arithmetically combining parameters of differently trained models, a wide range of applications such as task-arithmetic [], including unlearning [] and continual-learning [], have been explored. Our research extends these techniques to soft tree ensembles that began training from entirely different initial conditions. We will leave these empirical investigations for future work.

This study provides a fundamental analysis of ensemble learning, and we believe that our discussion will not have any negative societal impacts.

## Appendix A Detailed Algorithms

We present pseudo-code of algorithms for activation matching (Algorithm 1) and weight matching (Algorithm 2).
In these algorithms, if there is only one possible pattern for $U\in\mathbb{N}$, which represents the number of possible operations, and the corresponding operation does nothing in particular, it becomes equivalent to simply considering tree permutations.

Figure: Algorithm 1 Activation matching for soft trees

Figure: Algorithm 2 Weight matching for soft trees

Here, we describe the specifications of the notations and functions used in Algorithms 1 and 2.
In Section 2.1, $\boldsymbol{\Theta}_{A}$ and $\boldsymbol{\Theta}_{B}$ are initially defined as vectors. However, for ease of use, in Algorithms 1 and 2, $\boldsymbol{\Theta}_{A}$ and $\boldsymbol{\Theta}_{B}$ are represented as matrices of size $\mathbb{R}^{M\times P_{\text{{Tree}}}}$, where $P_{\text{{Tree}}}$ denotes the number of parameters in a single tree. Multidimensional array elements are accessed using square brackets [$\cdot$]. For example, for $\boldsymbol{G}\in\mathbb{R}^{I\times J}$, $\boldsymbol{G}[i]$ refers to the $i$th slice along the first dimension, and $\boldsymbol{G}[:,j]$ refers to the $j$th slice along the second dimension, with sizes $\mathbb{R}^{J}$ and $\mathbb{R}^{I}$, respectively. Furthermore, it can also accept a vector $\boldsymbol{v}\in\mathbb{N}^{l}$ as an input. In this case, $\boldsymbol{G}[\boldsymbol{v}]\in\mathbb{R}^{l\times J}$.
The Flatten function converts multidimensional input into a one-dimensional vector format.
As the LinearSumAssignment function, $\operatorname{scipy.optimize.linear_sum_assignment}$(^3^33[https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html)) is used to solve the LAP. In the AdjustTree function, the parameters of a tree are modified according to the $u$th pattern among the enumerated $U$ patterns. Additionally, in the Weighting function, parameters are multiplied by the square root of their weights defined in Section 3.2 to simulate the process of assessing a rule set. If the first argument for the UpdateBestOperation function, the input inner product, is larger than any previously input inner product values, then $u^{\prime}$ is updated with $u$, the second argument. If not, $u^{\prime}$ remains unchanged.

## Appendix B Dataset

**Table 5: Summary of the datasets used in the experiments.**
| Dataset | $N$ | $F$ | Link |
| --- | --- | --- | --- |
| Bioresponse | 3434 | 419 | [https://www.openml.org/d/45019](https://www.openml.org/d/45019) |
| Diabetes130US | 71090 | 7 | [https://www.openml.org/d/45022](https://www.openml.org/d/45022) |
| Higgs | 940160 | 24 | [https://www.openml.org/d/44129](https://www.openml.org/d/44129) |
| MagicTelescope | 13376 | 10 | [https://www.openml.org/d/44125](https://www.openml.org/d/44125) |
| MiniBooNE | 72998 | 50 | [https://www.openml.org/d/44128](https://www.openml.org/d/44128) |
| bank-marketing | 10578 | 7 | [https://www.openml.org/d/44126](https://www.openml.org/d/44126) |
| california | 20634 | 8 | [https://www.openml.org/d/45028](https://www.openml.org/d/45028) |
| covertype | 566602 | 10 | [https://www.openml.org/d/44121](https://www.openml.org/d/44121) |
| credit | 16714 | 10 | [https://www.openml.org/d/44089](https://www.openml.org/d/44089) |
| default-of-credit-card-clients | 13272 | 20 | [https://www.openml.org/d/45020](https://www.openml.org/d/45020) |
| electricity | 38474 | 7 | [https://www.openml.org/d/44120](https://www.openml.org/d/44120) |
| eye_movements | 7608 | 20 | [https://www.openml.org/d/44130](https://www.openml.org/d/44130) |
| heloc | 10000 | 22 | [https://www.openml.org/d/45026](https://www.openml.org/d/45026) |
| house_16H | 13488 | 16 | [https://www.openml.org/d/44123](https://www.openml.org/d/44123) |
| jannis | 57580 | 54 | [https://www.openml.org/d/45021](https://www.openml.org/d/45021) |
| pol | 10082 | 26 | [https://www.openml.org/d/44122](https://www.openml.org/d/44122) |

## Appendix C Additional Empirical Results

Tables LABEL:tbl:non_oblivious_wm_full, LABEL:tbl:non_oblivious_am_full, LABEL:tbl:oblivious_wm_full and LABEL:tbl:oblivious_am_full present the barrier for each dataset with $D=2$ and $M=256$. By incorporating additional invariances, it has been possible to consistently reduce the barriers.

Tables LABEL:tbl:dl_wm_full and LABEL:tbl:dl_am_full detail the characteristics of the barriers in the decision lists for each dataset with $D=2$ and $M=256$. The barriers in the modified decision lists tend to be smaller.

Tables 13 and 13 show the barrier for each model when only considering permutations with $D=2$ and $M=256$. It is evident that focusing solely on permutations leads to smaller barriers in the modified decision lists compared to other architectures.

Figures 9, 10, 11, 12, 13, 14, 15 and 16 show the interpolation curves of oblivious trees with $D=2$ and $M=256$ across various datasets and configurations. Significant improvements are particularly noticeable in AM, but improvements are also observed in WM. These characteristics are also apparent in the non-oblivious trees, as shown in Figures 17, 18, 19, 20, 21, 22, 23 and 24.
Regarding split data training, the dataset for each of the two classes is initially complete (100%). It is then divided into splits of 80% and 20%, and 20% and 80%, respectively. Each model is trained using these splits. Figures 13, 15, 21, and 23 show the training accuracy evaluated using the full dataset (100% for each class).

**Table 6: Accuracy barrier for non-oblivious trees with WM.**
|  | Train | Test |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Dataset | Naive | Perm | Perm&Flip | Naive | Perm | Perm&Flip |
| Bioresponse | 18.944 ± 10.076 | 5.876 ± 1.477 | 4.132 ± 0.893 | 8.235 ± 6.456 | 1.285 ± 0.635 | 0.314 ± 0.432 |
| Diabetes130US | 2.148 ± 0.601 | 1.388 ± 1.159 | 0.947 ± 0.888 | 1.014 ± 0.959 | 0.540 ± 0.999 | 0.784 ± 0.840 |
| Higgs | 27.578 ± 1.742 | 18.470 ± 0.769 | 14.772 ± 1.419 | 4.055 ± 1.089 | 0.662 ± 0.590 | 0.292 ± 0.421 |
| MagicTelescope | 2.995 ± 1.198 | 0.576 ± 0.556 | 0.307 ± 0.346 | 2.096 ± 1.055 | 0.361 ± 0.618 | 0.229 ± 0.348 |
| MiniBooNE | 18.238 ± 4.570 | 2.272 ± 0.215 | 1.506 ± 0.211 | 12.592 ± 4.190 | 0.231 ± 0.314 | 0.000 ± 0.000 |
| bank-marketing | 13.999 ± 4.110 | 2.711 ± 1.183 | 1.521 ± 0.463 | 13.593 ± 4.567 | 1.843 ± 1.001 | 0.953 ± 0.688 |
| california | 6.396 ± 2.472 | 0.873 ± 0.551 | 0.520 ± 0.327 | 5.226 ± 2.377 | 0.224 ± 0.248 | 0.206 ± 0.131 |
| covertype | 16.823 ± 4.159 | 1.839 ± 0.336 | 0.914 ± 0.546 | 14.900 ± 4.016 | 1.035 ± 0.106 | 0.376 ± 0.333 |
| credit | 7.317 ± 2.425 | 3.172 ± 2.636 | 2.615 ± 0.831 | 5.861 ± 2.064 | 2.202 ± 3.103 | 1.830 ± 0.588 |
| default-of-credit-card-clients | 14.318 ± 4.509 | 5.419 ± 1.318 | 3.273 ± 0.793 | 6.227 ± 4.205 | 0.937 ± 1.036 | 0.243 ± 0.172 |
| electricity | 10.090 ± 2.930 | 1.035 ± 0.543 | 0.221 ± 0.192 | 9.422 ± 2.795 | 0.771 ± 0.478 | 0.130 ± 0.071 |
| eye_movements | 18.743 ± 1.994 | 11.605 ± 1.927 | 7.866 ± 1.301 | 1.495 ± 0.467 | 0.463 ± 0.183 | 0.180 ± 0.206 |
| heloc | 4.434 ± 1.611 | 1.652 ± 0.475 | 1.012 ± 0.481 | 0.830 ± 0.727 | 0.475 ± 0.447 | 0.322 ± 0.338 |
| house_16H | 8.935 ± 2.504 | 3.362 ± 0.482 | 2.660 ± 1.208 | 4.230 ± 2.189 | 0.219 ± 0.224 | 0.404 ± 0.782 |
| jannis | 17.756 ± 3.322 | 10.442 ± 1.404 | 7.362 ± 0.219 | 3.205 ± 2.849 | 0.029 ± 0.064 | 0.007 ± 0.016 |
| pol | 20.542 ± 2.873 | 4.612 ± 0.912 | 3.225 ± 1.080 | 15.830 ± 2.562 | 1.708 ± 0.599 | 1.012 ± 0.859 |

**Table 10: Accuracy barrier for decision lists with WM.**
|  | Train | Test |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Dataset | Naive | Perm | Naive (Modified) | Perm (Modified) | Naive | Perm | Naive (Modified) | Perm (Modified) |
| Bioresponse | 21.323 ± 6.563 | 4.259 ± 0.698 | 14.578 ± 3.930 | 4.641 ± 0.918 | 9.325 ± 3.988 | 0.346 ± 0.277 | 7.346 ± 4.261 | 1.309 ± 0.827 |
| Diabetes130US | 5.182 ± 3.745 | 1.483 ± 1.006 | 2.754 ± 1.098 | 1.088 ± 0.608 | 4.910 ± 4.244 | 1.293 ± 1.332 | 1.476 ± 1.308 | 0.849 ± 0.885 |
| Higgs | 27.778 ± 1.036 | 16.110 ± 0.518 | 28.915 ± 1.314 | 14.071 ± 0.395 | 4.777 ± 0.803 | 0.106 ± 0.203 | 5.136 ± 0.946 | 0.039 ± 0.083 |
| MagicTelescope | 4.855 ± 3.388 | 0.355 ± 0.682 | 5.138 ± 2.655 | 0.182 ± 0.141 | 4.137 ± 3.763 | 0.280 ± 0.519 | 4.534 ± 2.588 | 0.157 ± 0.162 |
| MiniBooNE | 23.059 ± 1.479 | 1.911 ± 0.138 | 14.916 ± 3.616 | 1.580 ± 0.178 | 17.248 ± 1.683 | 0.025 ± 0.036 | 9.340 ± 3.585 | 0.035 ± 0.042 |
| bank-marketing | 11.952 ± 3.794 | 0.979 ± 0.478 | 11.589 ± 2.167 | 0.373 ± 0.448 | 11.387 ± 4.113 | 0.536 ± 0.472 | 10.540 ± 2.067 | 0.349 ± 0.348 |
| california | 6.522 ± 3.195 | 0.621 ± 0.363 | 8.435 ± 3.273 | 0.538 ± 0.214 | 5.167 ± 2.962 | 0.236 ± 0.146 | 6.844 ± 3.087 | 0.151 ± 0.147 |
| covertype | 13.408 ± 3.839 | 1.341 ± 0.433 | 11.114 ± 2.689 | 1.257 ± 0.904 | 11.162 ± 3.620 | 0.472 ± 0.340 | 8.826 ± 2.729 | 0.477 ± 0.889 |
| credit | 11.238 ± 8.115 | 1.968 ± 0.990 | 14.626 ± 5.448 | 1.390 ± 0.423 | 10.880 ± 9.040 | 1.421 ± 1.046 | 13.667 ± 5.951 | 0.940 ± 0.612 |
| default-of-credit-card-clients | 12.513 ± 5.116 | 3.107 ± 1.123 | 11.378 ± 2.123 | 3.793 ± 0.881 | 5.161 ± 4.304 | 0.328 ± 0.512 | 3.197 ± 1.916 | 0.666 ± 0.651 |
| electricity | 6.524 ± 1.863 | 0.725 ± 0.451 | 9.101 ± 2.685 | 0.944 ± 0.557 | 5.834 ± 1.838 | 0.420 ± 0.354 | 8.487 ± 2.460 | 0.543 ± 0.511 |
| eye_movements | 19.125 ± 1.791 | 9.433 ± 1.385 | 19.738 ± 1.490 | 8.755 ± 1.391 | 1.990 ± 1.623 | 0.329 ± 0.102 | 1.916 ± 1.492 | 0.277 ± 0.302 |
| heloc | 4.513 ± 1.826 | 1.564 ± 0.617 | 5.116 ± 0.793 | 1.574 ± 0.154 | 0.725 ± 0.598 | 0.155 ± 0.190 | 1.263 ± 0.711 | 0.359 ± 0.346 |
| house_16H | 9.195 ± 2.408 | 2.520 ± 0.446 | 8.693 ± 1.302 | 2.222 ± 0.730 | 4.629 ± 2.314 | 0.063 ± 0.129 | 4.192 ± 1.517 | 0.185 ± 0.296 |
| jannis | 20.766 ± 2.097 | 9.484 ± 0.371 | 20.520 ± 1.017 | 7.400 ± 0.324 | 3.947 ± 2.605 | 0.006 ± 0.013 | 4.451 ± 1.300 | 0.004 ± 0.009 |
| pol | 23.401 ± 5.448 | 3.137 ± 1.038 | 20.137 ± 4.200 | 3.435 ± 0.675 | 18.933 ± 5.249 | 0.952 ± 0.925 | 16.522 ± 3.502 | 1.143 ± 0.565 |

Figure: Figure 9: Interpolation curves of train accuracy for oblivious trees with AM.

Figure: Figure 10: Interpolation curves of test accuracy for oblivious trees with AM.

Figure: Figure 11: Interpolation curves of train accuracy for oblivious trees with WM.

Figure: Figure 12: Interpolation curves of test accuracy for oblivious trees with WM.

Figure: Figure 13: Interpolation curves of train accuracy for oblivious trees with AM by use of split dataset.

Figure: Figure 14: Interpolation curves of test accuracy for oblivious trees with AM by use of split dataset.

Figure: Figure 15: Interpolation curves of train accuracy for oblivious trees with WM by use of split dataset.

Figure: Figure 16: Interpolation curves of test accuracy for oblivious trees with WM by use of split dataset.

Figure: Figure 17: Interpolation curves of train accuracy for non-oblivious trees with AM.

Figure: Figure 18: Interpolation curves of test accuracy for non-oblivious trees with AM.

Figure: Figure 19: Interpolation curves of train accuracy for non-oblivious trees with WM.

Figure: Figure 20: Interpolation curves of test accuracy for non-oblivious trees with WM.

Figure: Figure 21: Interpolation curves of train accuracy for non-oblivious trees with AM by use of split dataset.

Figure: Figure 22: Interpolation curves of test accuracy for non-oblivious trees with AM by use of split dataset.

Figure: Figure 23: Interpolation curves of train accuracy for non-oblivious trees with WM by use of split dataset.

Figure: Figure 24: Interpolation curves of test accuracy for non-oblivious trees with WM by use of split dataset.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 8
presentation: 4
questions: - In Figure 6, I don't quite understand why AM considering only permutation increases the barrier more than naive interpolation. Why does considering only activation result in a worse match than identity? The authors explain this in the main text as follows, but I would like a more detailed explanation.
    
    > This is because parameter values are not used during the rearrangement of the tree in AM.
    > 
- Why do the authors think that the barrier after matching increases as depth increases? Ainsworth et al. (2023) showed that the barrier decreases as width increases, but they did not experiment with depth, and Entezari et al. (2022) measured the barrier for changes in width and depth without matching, which is different from the experiment in Figure 6, which measured the barrier after matching.
- Is there a compelling reason to use activation matching over weight matching, given that it does not seem to offer any clear advantages? Or is it simply intended to replicate the methodology of Ainsworth et al. (2023) for validation purposes?
- It would be useful to know the actual runtime required for matching. Compared to neural networks commonly considered in standard LMC research, such as ResNet, the number of parameters here is significantly lower. Given this, even with a large number of invariance patterns, it may not take very long to check all of them.
- Some minor suggestions:
    - In Figure 6, the x-axis represents different categories without a clear order, making the use of a line plot appear unnatural. A bar plot or box plot would be more appropriate in this case.
    - In the tables and figures, the notation "Ours" does not clearly give the intended meaning. While I understand that it stands for "Perm & Flip & Order", it is somewhat confusing. This is especially noticeable in Tables 3 and 4, where "Decision List (Modified)" is also the proposed method ("Ours"), which makes the absence of results in the corresponding cell seem unnatural. Furthermore, I assume that "Naive" is meant to indicate the results without matching, but this is not explained anywhere. To improve clarity, it would be helpful either to label it more explicitly as "naive interpolation", as in the cited papers, or to provide additional clarification in the main text.
soundness: 3
strengths: - The approach of exploring linear mode connectivity, which has been mainly studied in neural networks, in a different architecture is novel.
- The organization and flow of the paper effectively explains the existing research and the proposed method and is easy to understand.
- Through various experiments, the authors show that linear mode connectivity can be achieved in soft tree ensembles.
- The authors show that soft tree ensembles trained on different data splits can be merged to form better performing models.
summary: This paper explores Linear Mode Connectivity (LMC) in soft tree ensemble models. LMC is well studied in neural networks, but achieving it in tree models presents unique challenges due to their architectural differences. The authors identify additional invariants, subtree flip and splitting order, that are necessary to achieve LMC in tree structures that differ from neural networks, including permutation invariance. With a matching algorithm that takes these invariants into consideration, the authors show that LMC can also be achieved in soft tree ensembles. And they further present a modified decision list architecture that preserves LMC without these additional invariances, aiming to simplify model merging and other parameter-based applications.
weaknesses: - The authors do not provide a more efficient matching algorithm other than exhaustive search.
- The paper does not provide sufficient justification for using the proposed modified decision list. Specifically, the proposed architecture presents a higher barrier compared to an oblivious tree that includes all invariants. Furthermore, it lacks a compelling practical use case demonstrating more efficient matching relative to other tree-based architectures, such as model merging, which can be used to improve performance. To strengthen the argument, it would be necessary to include some experiment similar to the one shown in Figure 8, applied to the proposed architecture.

---

confidence: 2
contribution: 2
initial_rating: 6
presentation: 4
questions: See the Weaknesses section.
soundness: 3
strengths: The paper has several strengths:

- The problem addressed in this work is of general interest, and illuminates an interesting property of decision trees.
- The paper is very clearly written, and easy to follow
- This paper hinges upon it's empirical evaluation: the experiments are quite thorough, and clearly show how incorporating *additional* invariances into model interpolation leads to better accuracy (the key claim of the work).
- The notion of the *modified decision list* architectures is an interesting and potentially highly useful one (as it seems to reduce computation cost per inference)
summary: This work studies the phenomenon of linear mode connectivity (LMC) in decision tree models (as opposed to neural networks, where they have been studied extensively). Specifically, they investigate whether soft-tree ensembles can be interpolated, while retaining accuracy. Unlike in neural networks, where permutation invariance is sufficient, the authors show that additional invariances unique to decision tree models are necessary for LMC to hold - in fact, this is the key finding of the work.
weaknesses: There is one significant weakness in this work:

- Lack of Rigorous Theory: the paper would have been strengthened significantly had the authors provided a rigorous analysis of the effect of the stated invariances (permutation, subtree flip, and splitting order) on the ability to interpolate 2 (or more) models - even if only on extremely simple cases. Were that so, the empirical results would have been used to support rigorous theory, which would have been a much more powerful argument.
-  Linear Mode Connectivity was proposed to understand how deep neural networks could be sparsified (Frankle et al, 2020). Can a similar analysis of methods to sparsify decision trees be done, provided the insights proposed in this work? An analysis of this sort - where the need to interpolate models becomes evident - would have also noticeably improved this work.
- The authors do not highlight specific tasks for which interpolation of trees would be of significant benefit. This weakens the argument motivating the need for this work. For instance, does model interpolation in tree ensembles improve robustness to distribution shift?

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: See Weakness.
soundness: 3
strengths: **Originality:** This work is original in extending the concept of LMC to tree-based models, an area previously unexplored. By identifying invariances specific to tree structures, the paper introduces a new perspective on achieving functional equivalence in non-neural models.

**Clarity:** Despite the complexity of the topic, the paper is clearly written, with detailed explanations of both the mathematical framework and empirical results. Figures and diagrams (such as Figure 3 on invariances) effectively support comprehension.

**Significance:** The work expands the applicability of LMC, which is valuable for understanding stability in non-convex optimization and facilitating practical applications such as model merging. The findings on tree-specific invariances could have a substantial impact on future research in tree ensemble models and their integration with neural network techniques.
summary: This paper investigates Linear Mode Connectivity (LMC) in the context of differentiable tree ensemble models, particularly focusing on soft tree ensembles. LMC refers to the property where linearly interpolating two models (in parameter space) does not degrade performance, a phenomenon previously established for neural networks. The authors extend this concept to tree-based models, identifying specific architectural invariances unique to trees—namely, subtree flip invariance and splitting order invariance—as critical for achieving LMC. They further propose a novel decision list-based architecture that bypasses these invariances, simplifying the conditions necessary for LMC. Through empirical evaluation, the paper demonstrates that LMC can be achieved in tree ensembles, broadening the understanding of LMC beyond neural networks. In summary, I believe that both the research topic and methods are relatively novel and will significantly contribute to the deep learning community.
weaknesses: **Empirical Validation Scope:** The empirical results are primarily based on tabular datasets. Extending the validation to additional types of data (e.g., image or sequential data processed via tree ensembles) could further strengthen the findings.

**Scalability of Additional Invariance Handling:** The paper discusses the computational expense associated with handling additional invariances for deeper trees. However, a more detailed discussion of potential optimizations or heuristic approaches to manage this complexity would be beneficial.

**Comparative Analysis:** While the results demonstrate LMC in tree ensembles, the paper could benefit from a more in-depth comparison with related methods or model architectures, particularly alternative approaches to model merging or parameter interpolation that do not rely on LMC.

**Equation Reference:** Please use "Equation (1)" instead of "Equation 1."

Meta-review: The paper extends the results on linear mode connectivity (LMC) to differentiable tree ensembles. LMC was previously demonstrated only for neural network models  and this paper studies this phenomenon for a new class of models. In neural networks, accounting for permutation invariance in neurons is sufficient for LMC typically. The authors show that the analogous notion of permutation invariance does not lead to LMC in differentiable tree ensembles. However, accounting for a broader class of invariances (subtree flip, splitting order) is sufficient for LMC. The authors propose two matching methods: activation and weight matching; they then study LMC when accounting for different classes of invariance in different model classes and on different problems. The authors also provide results on model merging via LMC and propose decision lists, a variation of decision trees with reduced set of invariances.

Strenghts:
- The paper for the first time extends mode connectivity research beyond neural networks. Model merging is a potentially exciting application. Moreover, combinations of decision trees and neural networks (such as MoE transformer models) are highly practically relevant.
- The paper is well-written and the main results are easy to follow.
- The authors perform an extensive evaluation on a range of tabular tasks. During the rebuttal, the authors also added experiments on the MNIST dataset.
- The proposed methods work well empirically and achieve their goal (establishing LMC).

Weaknesses:
- No theoretical understanding of LMC in differentiable tree ensembles.
- Not completely clear how practically relevant these models are at the moment, and to what extent LMC is practically relevant. Model merging is potentially exciting, but it’s not clear if there are practical settings where it would be relevant.
- Similarly, not clear if the proposed decision lists architecture is practically relevant.

Decision recommendation: This is an original, interesting paper extending linear mode connectivity to a new class of models. While the practical relevance is not completely clear, I believe the paper makes a valuable contribution to LMC literature and recommend accepting it.

Decision: Accept (Spotlight)