Compressing tree ensembles through Level-wise Optimization and Pruning
Authors: Laurens Devos
Timo Martens
Deniz Can Oruc
Wannes Meert
Hendrik Blockeel
Jesse Davis
Venue: ICML 2025 poster (2025)
Keywords: ensembles
decision forests
model efficiency
energy efficiency
verification
compression
Primary area: general_machine_learning->supervised_learning
TL;DR: A method is proposed that can reduce the size of decision tree ensembles by orders of magnitude with negligible cost in accuracy.

Abstract: Tree ensembles (e.g., gradient boosting decision trees) are often used in practice because they offer excellent predictive performance while still being easy and efficient to learn. In some contexts, it is important to additionally optimize their size: this is specifically the case when models need to have verifiable properties (verification of fairness, robustness, etc. is often exponential in the ensemble's size), or when models run on battery-powered devices (smaller ensembles consume less energy, increasing battery autonomy).  For this reason, compression of tree ensembles is worth studying.  This paper presents LOP, a method for compressing a given tree ensemble by pruning or entirely removing trees in it, while updating leaf predictions in such a  way that predictive accuracy is mostly unaffected. Empirically, LOP achieves compression factors that are often 10 to 100 times better than that of competing methods.

Compressing Tree Ensembles through Level-wise Optimization and Pruning
Laurens Devos" 12
Timo Martens 12
Deniz Can Orug
Wannes Meert 12 Hendrik Blockeel Jesse Davis! 12
Abstract
much from reducing their size? The answer is yes, for multiple reasons: (1) Due their efficiency, forests very suitable for use on embedded or battery-powered de- vices (Fan et al., 2013; Donos et al., 2015; Daghero et al., 2021; Lauwereins et al., 2015). A smaller forest has a smaller memory footprint and consumes less energy per pre- diction (Buschjäger & Morik, 2023). On nattery-powerdd devices, this can have substamtial effect on battery auton- omy. (2) Forest size is relevant when models must be veri- fiable, for instance, in the context of fairness or robustness against adversarial attacks (Devos et al., 2021 Verifica- tion methods for decision forests tend to scale exponentially in the size of the forest (Kantchelian et al., 2016; Devos et al., 2023). Therefore, any size reduction has an important effect on verifiability.
Tree ensembles (e.g., gradient boosting decision trees) are often used in practice because they offer excellent predictive performance while still being easy and efficient learn. In some contexts, it is important additionally optimize their size: this is specifically the case when models need to have verifiable properties (verification of fair- ness, robustness, etc. is often exponential in the ensemble's ' size), or when models run on battery- powered devices (smaller ensembles consume less energy, increasing battery autonomy). For this reason, compression of tree ensembles is worth studying. This paper presents LOP, method for compressing given tree ensemble by pruning or entirely removing trees in it, while updating leaf predictions in such a way that predictive accuracy is mostly unaffected. Empirically, LOP achieves compression factors that are often 10 100 times better than that of competing methods.
While one could try construct smaller forests from the start, the success of existing methods such as Random Forests or XGBoost is an argument for not changing the method of growing the forest, but reducing its size after- wards (Ren et al., 2015; Buschjäger & Morik, 2023). In this formulation, the original forest provides a reference point in terms of predictive performance. This enables designing compression approaches that more explicitly trade off pre- dictive accuracy versus other aspects of performance, such as memory footprint, energy consumption, and verifiability (all of which correlate with size).
1. Introduction
Ensembles of decision trees, a.k.a. decision forests, are frequently used in practice because of their ease of training, excellent overall performance, and high efficiency. Their training requires little or no hyperparameter tuning, the computational cost of both training and prediction is very small, and for tabular data, they are usually among the best performing models (Grinsztajn et al., 2022).
Multiple methods for reducing the size of forests have been proposed. There has been extensive research on remov- ing component models from ensembles (Tsoumakas et al., 2009). More recently, methods specific to forests have been proposed. These usually optimize the values stored in the leaves, with size reduction as possible side-effect rather than the primary goal (e.g, Ren et al., 2015), though several approaches explicitly add pruning as an objective (Buschjäger & Morik, 2023; Liu & Mazumder, 2023a), Gen- erally, all these methods try to find an optimum for some cost function that trades off size versus accuracy.
This paper is about compressing decision forests: reducing their size as measured by, e.g., the total number of leaves in the forest, while maintaining their accuracy. In the light of the above successes, one might wonder whether this is worthwhile: if forests are already so efficient, can we gain
'Equal contribution 'KU Leuven Department of Computer Science, Leuven, Belgium LLuuvenAAl KU Leuven Institute for Artificial Intelligence, Leuven, Belgium. Correspondence to: Jesse Davis <jesse. ejesse.davis@e kuleuven. be>, Hendrik Blockeel <hen- drik.blocken blockeolokkl@ekkkk Bonekkel@@uueuvonn kuleuven.be>>.
In this paper, we propose novel method called LOP for compressing decision forests. LOP tries to find the small- est forest whose predictive accuracy is still within a user- provided margin to that of the original forest. Like other methods, it starts from a given forest. In contrast existing methods that restrict what can be pruned, LOP can prune any
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
(sub)tree in the forest. It proceeds level-wise, from the root towards the leaves. At each level, it formulates an optimiza- tion problem that tries to prune subtrees rooted at that level while updating the values in the remaining leaves to avoid drop in accuracy. Empirically, L.P can find much smaller forests than existing methods: sometimes by a factor 100 or more, if small loss in accuracy (< 0.5%) is acceptable; and often by a factor 2-3 when comparing forests with the same accuracy. This substantially increases the applicability of forests in contexts where verifiability, robustness, battery autonomy, etc. matter.
where k indexes all L leaves in the forest and each vy equals some WmDm.js and ultimately
T(x) = s())
the dot product of an T-dimensional vector e with a binary vector s(x) that indicates which leaves x is sorted into (i.e., the k'th component of sxx) is 1 (x)).
Postprocessing decision forests. Forests are learned in a greedy manner: tree Tm is learned in the context of the partial forest (7i, 72.................. Tm-1). but the tree that seems most useful at that point may turn out less useful in the context of the forest as a whole. Furthermore, because the number of trees is predefined, more trees may be added than strictly needed to achieve a certain level of accuracy.
2. Preliminaries
Decision trees. Decision trees exist in many variants (Bloc- keel et al., 2023). We take the following view: A decision tree is a tree-shaped representation of function X' + V: internal nodes of the tree are labeled with a test that can be performed on instances; there is an outgoing edge for each possible outcome of the test; leaves are labeled with a value g E y. A tree associates each instance x with a value ù by sorting x down the tree according to the outcome of the tests until leaf is reached, and returning the value stored in that leaf. Here, we assume y R: this covers regression trees but also binary classification trees by using threshold on ý to decide the predicted class.
This has prompted researchers to investigate whether forests can be further optimized after learning them. Forests can often be simplified without loss of predictive accuracy by removing trees that eventually turn out to be redundant (Margineantu & Dietterich, 1997; Buciluă et al., 2006; Tsoumakas et al., 2009; Lu et al., 2010; Zhang et al., 2006). These approaches aim primarily at reducing the forest size, ideally no loss in accuracy.
A different type of postprocessing approach (c.g., Ren et al., 2015) is based on changing the values predicted in the leaves of the trees, which is often referred to as leaf refinement. By default, the values inserted into Tm 's leaves are optimal in the context in which Tm is learned. They may not be optimal in the context of the whole forest. In fact, it is easy to show that in general, individual trees may have make suboptimal predictions for the ensemble to make optimal ones (see Appendix A).
Decision forests. Decision forests are ensembles of deci- sion trees. Learning algorithms for them include popular algorithms such as Random Forests (Breiman, 2001) and gradient boosted decision trees (Friedman, 2001), of which XGBoost (Chen& & Guestrin, 2016) is well-known example. Forests are typically constructed iteratively, growing one tree at time using a standard tree learner and adding it to the forest until that contains a predefined number of trees. A for- makes predictions by combining
est T = (Ti, .2.... T JM the predictions of the individual trees Tm The combination rule can be standard voting for classification or averaging for regression, but more generally it is linear combination of the individual predictions: T(x)= Σm WmTm (x) where both the Tm and the wm are learned.
3. The LOP Algorithm
We introduce Level-wise Optimization and Pruning (LOOP), novel algorithm which tackles the following problem:
Given: A previously learned tree ensemble T and a dataset (xg (h)) of N examples.
A tree can be written as an additive model: T(x) = Σ, (x)0, with ūj the value stored in the j'th Ieaf, and 1, is if x gets sorted into the j'th leaf and O otherwise. Hence, the entire forest can be written in an additive form:
Do: Compress T into a (much) smaller ensemble I' such that there is a minimal difference in predictive perfor- mance between T and T"
T(x)
Σ Wm E1ma(1))ne
Σ Wm Im (1))m. m.
The core idea underlying LOP is that, starting with the root nodes (level 0), it processes the ensemble in a level-by- level manner. At each level, it formulates optimization problem that simultaneously attempts to prune (sub)trees and optimize the leaf values. This problem is global in that it involves all nodes in the ensemble at the considered level.
where indexes trees and j leaves in tree. The notation can be simplified to
T(x) = Σ 1
To illustrate the intuition behind the approach. consider the simple ensemble shown in Figure 1a and suppose the
km
2

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
algorithm is processing level If the leaf values V11 V12 and V13 under the node HEIGHT 190 in 72 were all equal to v, then clearly that subtree could be replaced by leaf with value v. To encourage such compression, LOP jointly optimizes the leaf values under each node n at this level by learning a transformation G + bn where Gn and d, are learnable parameters. LOP then runs an optimization problem that finds ca. by such that the new forest (with leaf values of the form C + b,,) best fits the training data. During this optimization, LOP applies the sparsity inducing Ll regularization on Gns yielding two cases:
where X is the data matrix, 0 contains the parameters to be optimized, and r is regularization term (see 3.2). Let us denote with the number of active nodes at the current level. For now, assume the set of active nodes contains no roots or leaves. 0 is then a 2n-dimensional vector
0 = [a b
C2
b2
ba] ba]²
X represents the dataset in terms of the nodes and leaves that each instance will be sorted into, and the corresponding leaf values. X can be computed as SB with S an N x L matrix with as i'th row s(æ;), and B an L x 2a matrix that has on row the values 2/ and in columns 2n(k) - and (n()). Basically, maps instances to leaves and B links the corresponding leaf values to the right c, parameters. is easily verified that X is then column matrix whose i'th row equals s(x;) (c' +6)).. The general case where active nodes can be leaves is obtained by simply omitting from 0 the Cn component for leaves (leaves need not be pruned any further) and dropping the corresponding columns B. Level 0 another special case: pruning at level 0 removes the tree entirely, so no bias term is used at that level.
1. On = 0: the subtree rooted n is pruned and re- placed by a leaf node with value bn Figure lb shows this for our running example where the internal node HRIGHT < 190 is replaced by b4,
2. On * O: the values of all leaf nodes under n are updated to be Cn + bn- This shown for the nodes under node AGE < 50 in Figure lb.
For leaf nodes (i.e., i1 and ug in this example), the en value already zero and the above simply entails learning a new, globally optimal leaf value.
Example 3.1. The ensemble shown in Figure 1, top, has 8 leaves. Counting leaves from left to right, assume that the first three instances in the training set are sorted into leaves and 7; I and 6; and and 5. SBO is then:"
Next, we formalize more rigorously how LOP works.
3.1. Formulating the optimization problem
When formulating the optimization problem for level I, there is one complicating factor that must be considered: some trees may have leaf nodes at higher level (i.e., some level < l). For example, in Figure I this is the case for both trees at level 2. Because these leaves affect the prediction for each example, they must also be considered in the optimization problem. Moreover, the values of such leaves will also need to be updated to reflect any changes the ensembles at
V2
0
0
0
0
0
0
0
0
0
13
b
0
0
0
1
0
0
0
0
1
16
0
0
h2
0
0
28
1
0
0
:
0
0
0
1712
by
013
0
0
0
1.
[b
and we have
level 1. Hence, for level I we define the set of active nodes as the union of all nodes (both internal and leaf) at level together with all leaf nodes with a level < l. Below, we use n to index active nodes, and le to index leaf nodes.
0
0
V/3
1
0
0
V13
U1
1
0
0
0
1
V12
X = SB
0
U/
U/
1
0
:
:
:
:
Before the transformation, the prediction for an instance equals s(x)- v. Changing all e2 into Cn(t))* + bu(k). with ni(k) the active node above the k'th leaf, turns into (d' @ + b'), where @ is componentwise multiplication and the vectors c' and 1' associate the right e, and b,, value with each us (that is, 8/2 = buc(k) and ce = C.(R)). Thus, the cost function minimized at each level is
and
0302 + b2 + 01364 + b4
X9
Uic + 01201 + b₁
U962 + b2 + U8 by
N
3.2. Maintaining predictive performance
+a Σ ccnl
There are two issues contend with when solving our optimization problem. First, compression, i.e., pruning (sub)trees, may adversely affect the predictive performance.
with é loss function.
Practically, this optimization problem can be written as
In practice, the columns/rows shown in red would he omitted and are just shown to better visualize the matrix structure.
min ((X0,y) y) + ar(
3

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
[a)
LEVEL. 0
T1
Height < 200
T2
BMI
LEVEL. I
0x
by
Age < 50
+b₂
x
bby
x2X
Height < 190 + b.
LEVEL 2
BMI 26
Age 40
LEVEL 3
(b)
LEVEL. 0
T1
Height 200
+
T2
BMI
LEVEL.
by
Age < 50
by
b,
LEVEL 2
Narth by
BMI 26
LEVEL. 3
1/ Ni+bby
Nottlyy
Figure 1. An example ensemble consisting of two trees Ti and T2, and the effect of applying the LOP subroutine at level 1. The Icaf constants of the ensemble are denoted by ux. (A) shows the original ensemble annotated with scaling and shifting parameters on and 6, on level I. Note that leaf nodes have scaling factor. (B) shows the resulting ensemble after applying the LOP subroutine at level 1, assuming the case where c2 # O and ca = O. When scaling parameter oa nonzero, the leaf values in the subtree rooted at node n are updated to t + bes as shown for the subtree in Ti. For the case where the scaling parameter Cy is zero, the entire subtree rooted n is removed and replaced by a leaf with value by. This the case for the subtree in T2.
For this reason, LOP imposes the constraint that the com- pressed model's predictive performance on a validation set must differ by less than a user-defined margin A from the performance of the original forest.
compression to be performed and A the maximum allowed loss predictive performance compared to the original ensemble. The process of level-wise optimization is carried out for all levels starting level at the maximum depth of the deepest tree in the ensemble. When / = 0, setting Cn 0 effectively removes whole tree from the forest. As increases, the approach considers pruning ever smaller subtrees.
(root) and ending
LOP tunes the regularization strength parameter a to obtain maximal compression while satisfying the constraint the decrease in performance using search procedure that performs consecutive halving in log space. Starting from a wide range [10", 10"). LOP is run with a = 10(o+w)/2 and the resulting model satisfies the constraint, is updated to (o+ + u)/2, otherwise u is. The process is repeated until the interval is narrow enough with LOP choosing the highest o that satisfies the constraint. Initially, practice, LOP uses balanced accuracy² as the performance measure for classification, and RMSE for regression, but other measures could be used.
The level-wise procedure is repeated R times. As compres- sion progresses, subtrees that were not prunable in first round may become so in a subsequent round.
-3 and 4. In
Algorithm Level-by-level compression of tree ensembles
Input: Ensemble T, training set D {(x,, (1)) valida-
tion set D, = (x;;,,))) )
Settings: Number of rounds R, maximum loss A in valida-
Second, there a risk of overfitting. The number of parame- ters to be fit is at most twice the total number of active nodes, which for binary trees is upper-bounded by M2 with M the number of trees in the ensemble. Thus for small values of there is little risk but the chance for overfitting increases as I does. LOP's validation set approach helps counter this.
tion set performance
1: T' + T
2: for r < 1. do
3: for / < 1..d, with the maximum depth of T'' do
4: Construct = SB (see Section 3.1)
Find largest a for which performance loss on D.-
is larger than A.
3.3. Overall algorithmic working
6: Fit 0 using Equation 2 using the selected
7: Update T": for all n on this level, update all up
Algorithm 1 shows the pseudocode for LOP. It takes two hyperparameters: the number of rounds R of level-wise
under n to Cy + bn, making n a leaf if c,, = 0
8: end for
Balanced accuracy is the accuracy of the model under uni- form class distribution; it avoids disadvantages of accuracy under skewed distributions.
9: end for
10: return pruned ensemble T

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
4. Related Work
The objective is optimized using convex optimization tech- niques, with the sparsity of S speeding up the process. Note that GR optimizes all Uk entirely independently. As ex- plained before, this carries risk of overfitting: when there are more leaves than training instances, there are infinitely many ways to perfectly fit the training data. L2 regular- ization (r(v) = [|vll²) is used to counter overfitting. In addition this, GR combines neighboring leaves if the dif- ference in their values is sufficiently small. This operation leads to reduction of the size of the trees.
Many methods have been proposed for reducing the size of ensembles (Tsoumakas et al., 2009). They usually perform a search through the space of subsets of the ensembles, trad- ing off accuracy versus the number of component models. These methods are generic in the sense that they can be used on many different types of ensembles, not just ensembles of decision trees. A few methods have been proposed specif- ically for forests, making use of the fact that component models are known to trees. Some of these methods have been proposed in a knowledge distillation context: these methods prioritize simplicity over accuracy. For instance, Liu & Mazumder (2023b) and Hara & Hayashi (2018) re- spectively aim for ensembles that contain at most 15 or 10 leaves in their experiments, accepting any accuracy loss (they minimize but do not bound it). As these methods serve a different purpose than LOP, they are less relevant here. Among other, more closely related methods, the following three are of partieular interest.
Leaf Refinement with L1 Ensemble Pruning (LRL1): Buschjäger & Morik (2023) proposed combining leaf re- finement with "ensemble pruning", " which removes entire trees with minimal performance loss. Contrary to GR, size reduction is an explicit goal of their approach.
Recall our earlier formulation of forests as T(z) Σr, wi I ( (1) which ultimately was simplified to T(x) = s(x) - v. Rather than combining the product of wy and Di.5 into one parameter Uk. LRL keeps them sepa- rate and tries to push the w, to O. Thus, it keeps separate vectors w and ý and optimizes the following objective:
ForestPrune (FP): Liu & Mazumder (2023a) propose optimization approach in which decision variables indicate at what level each tree in the forest should be cut. They minimize training set loss plus a regularization term that rewards solutions with smaller average tree depth. While dif- ferent trees can be cut at different levels, within each tree the cut depth is constant. This is an important difference with LOP, which can prune individual subtrees at different depths within the same tree. By cutting at one level inside each tree, ForestPrune loses crucial aspect of trees, namely, that some subtrees can be deeper than others: a tree can partition the input space in a finer-grained manner in some areas, and in coarser manner elsewhere. A second difference is that LOP refines leaf values whereas ForestPrune does not. Due to these two differences, LOP explores ensembles that are not in ForestPrune's 's search space.
min 9,00 N ((((x:) vi) + a||w||1
(4)
where is the regularization parameter, and D.. is diago- nal matrix storing tree coefficients w. This non-smooth ob- jective is optimized using a proximal approach (Buschjäger & Morik, 2023).
An essential difference between LOP and both GR and LRL is that LOP does not optimize all the uk values indepen- dently, at least not for the original forest. It consecutively solves optimization problems with much fewer parameters (the b, and G, parameters) in order to prune as much as possible. It is still the case that at the deepest level, when k is maximal, all remaining leaf values (the b,) are optimized independently, but the number of leaves is typically dramat- ically reduced by the preceding pruning (more details in Appendix B). Thus, LOP solves more, but simpler, optimiza- tion problems, and is inherently less prone to overfitting.
Global Refinement (GR): Ren et al. (2015) point out that the leaf values in trees are not necessarily optimal in the con- text of the forest. After the full ensemble has been learned, they collectively fine-tune all the leaf values simultaneously using a single optimization problem. Their method reformu- lates the forest in the form T(x) s(x) v and solves the following minimization problem:
At level O, LOP behaves similarly to LRL in that it removes entire trees and it uses no bias terms at this level. It still differs in that LRL optimizes all leaf values, while LOP only rescales them by one scaling factor per tree, For > O. LOP's use of bias terms is essential and there is no counter- part in LRL
min- Σ (s(x.)) . v.,))) + arr(),
Collecting the ys in one vector y and the s(z;) in a matrix S whose i'th row equals s(x;), and defining the loss over a dataset as the sum of its instances' losses, this can also be written as
In summary, LOP can prune nodes at any level of the tree, whereas L is limited to pruning only at level 0, GR (re- peatedly) merges leaves at the lowest level, and FP removes all nodes below selected level in each tree.
min ((i,( v) + ar(v).
5

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
Table Compression results on XGBoost models. For the original models, we report their number leaves (#Leaf) and balanced accuracy the test set (Bacc). For the compression techniques, we report the compression ratio and drop in balanced accuracy versus the original model. 8x compression ratio means that compressed model has times fewer leaf nodes than the original ensemble. positive (negative) balanced accuracy difference means the compressed model is less (more) accurate than the original model. The best
compression ratios are given bold.
#Leaf
Compress. ratio (x)
Bacc
DifT. Bace (% Point)
Dataset
XGB
GR
IC
LRL 1
FP
LOP
XGB
GR
IC
LRL1
FP
LOP
Mnist
773.0
6.4
2.8
1.8
3.2
8.0
99.0
0.5
0.4
0.0
0.4
0.6
Electricity
2548.4
2.8
1.5
1.2
1.5
5.2
86.2
0.1
0.4
-0.1
0.2
0.5
Jannis
3319.9
11.1
6.6
1.4
14.7
18.1
77.0
0.3
0.4
0.3
0.3
0.6
Vehicle
396.2
2.2
2.6
1.1
2.0
8.0
94,4
0.1
1.0
-0.4
1.1
1.4
DryBean
1117.8
4.3
6.7
1.6
19.6
28.8
91.2
0.0
0.3
0.0
0.2
0.3
California
2232.1
5.8
2.2
1.3
2.5
9.1
88.8
0.2
0.4
-0.1
0.4
0.6
Compas
1525.3
26.7
15,4
2.2
240.8
356.8
65.3
-0.4
-0.2
0.0
-0.5
-0.1
Volkert
1101.0
8.0
3.9
2.0
4.8
8.3
98.7
0.5
0.4
0.2
0.4
0.6
Adult
2214.2
3.6
3.9
1.6
37.5
31.8
75,9
-0.3
0.2
0.1
0.1
-0.2
Ijennl
2421.1
4.2
1.2
1.2
2.4
6.5
93.3
-0.4
0.4
-0.6
0.2
0.4
MiniBooNE
3239.6
6.0
2.0
1.3
2.5
6.2
92.8
0.5
0.5
0.2
0.4
0.6
Phoneme
1346.1
2.1
1.7
1.3
4.1
7.5
84.7
0.2
0.6
-0.2
0.7
1.3
Spambase
792.3
3.0
2.1
1.5
3.9
8.5
94.0
0.4
0.6
-0.1
0.6
0.9
Credit
2230.4
24.8
18.6
2.0
133.7
196.6
76.4
0.2
0.0
0.7
0.4
0.5
average 1804.1
7.9
5.1
1.5
33.8
50.0
87.0
0.1
0.4
0.0
0.4
0.6
5. Experiments
pruning (Buschjäger & Morik, 2023) (I.RI.1), and Forest- Prune (Liu & Mazumder, 2023a) (FP).
We empirically evaluate LOP and aim to answer the follow- ing questions: (Q1) Given a learned binary classification forest, what the effect of compression on model size and performance? (Q2) How does LOP's compression affect energy consumption, memory footprint, and verifiability of models? (Q3) How sensitive is LOP to its hyperparameters A and R?
We consider 14 binary classification benchmark datasets. available on OpenML. (Vanschoren et al., 2013): Compas, Vehicle, Spambase, Phoneme, Adult, Ijennl, Mnist (2 vs. 4), DryBean (6 vs. rest), Volkert (2 vs. 7), Credit, California, MiniBooNE, Electricity, and Jannis.
We use 5-fold validaaai with folds for training (both training the ensemble and compressing it), 1 for validation, and I for testing. In each fold, train models on all combinations of the following hyperparameters:
Appendix C addresses two additional questions: (Q4) What the effect of compression on regression forests? (Q5) How does the runtime of compression scale with forest size?
XGBoost
RandomForest
5.1. Experimental setup
M
E [10, 25, 50, 100] E [4, 6,
E [50, 100, 250]
We compress XGBoost and RandomForest models because they are widely used, but LOP is equally applicable other types tree ensembles.
D
E [10, 15)
E [0.1, 0.25, 0.5, 1.0]
not applicable
with M the number of trees, D the maximum depth of the trees and n the learning rate in XGBoost. This yields 48 XGBoost models and RandomForest models, to which then apply the different compression algorithms.
We compare LOP to the original ensembles (XGB RF) and to four baseline methods. Individual Contribution (Lu et al., 2010) (IC) ranks and selects subset of trees in forest based on accuracy and diversity. It performed well previous evaluations (Buschjäger & Morik, 2023). It represents the coarsest extreme by operating only the tree level, serving as level 0 ablation of our method. Be- yond this method, also consider the previously described closely related methods of Global Refinement (Ren et al., 2015) (GR), leaf refinement combined with LI ensemble
The validation set is used to tune the regularization hyper- parameter for LOP, GR, LRL1 and FP. More specifically, its optimal value is the one that leads to the smallest model and is within a maximum drop A 0.5% on the validation set's balanced accuracy. The same is done to find the optimal
Dataset characteristics can be found Table A1
6

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
Table Compression results on RandomFores models. For original models, report their number of leaves (#Leaf) balanced accuracy the test set (Bacc). For the compression techniques, we report the compression ratio and drop in balanced accuracy versus the original model: see the caption of Table for precise definitions. best compression ratios are given bold.
#Leaf
Compress. ratio (x)
Bacc
Diff. Bace (% Point)
Dataset
RF
GR
IC
LRL
FP
LOP
RF
GR
IC
LRL
FP
LOP
Mnist
20039.0
61.9
22.7
2.4
22.5
74.1
99.3
0.5
0.4
0.3
0.6
0.8
Electricity
135271.6
114.4
21.9
7.8
19.5
125.0
85.3
0.2
0.3
-0.6
0.6
0.5
Jannis
183003.7
158.8
6.5
2.1
3.7
249.0
77.5
0.5
0.5
0.1
0.3
0.5
Vehicle
5111.0
7.7
16.9
1.0
12.8
46.4
94.9
-0.1
1.2
0.5
0.7
1.3
DryBean
26042.8
16.7
16.9
1.2
202.0
66.6
91.5
0.1
0.6
0.9
California
89481.1
174.4
22.5
1.7
13.0
196.2
88.4
0.4
0.6
-0.1
0.5
0.5
Compas
68893.7
473.7
15.3
1.0
8998.6
12086.8
63.3
-1.4
0.5
0.3
-0.7
-1.3
Volkert
25773.5
90.3
31.5
9.0
38.1
110.9
98.4
0.5
0.4
0.3
0.5
0.6
Adult
99148.2
194.6
90.9
11.0
322.6
1046.8
75.2
-0.6
-0.3
-0.4
0.1
0.0
Ijennl
131413.7
199.6
80.0
3.0
59.0
227.9
89.8
-0.1
-0.2
4.2
-0.6
0.4
MiniBooNE
149448.7
132.5
14.1
5.0
8.5
121.4
92.6
0.5
0.6
-0.1
0.5
0.7
Phoneme
31578.2
8.0
12.5
2.0
15.9
23.7
87.0
0.3
0.8
0.0
1.1
2.2
Spambase
18634.6
44.5
23.5
1.3
32.5
106.7
93.4
0.1
0.9
0.0
1.1
0.8
Credit 91428.9
216.9
9.1
1.0
26.9
1859.5
77.5
0.3
0.7
0.0
0.5
0.7
average
76804.9
135.3
27.5
3.5
698.3
1167.2
86.7
0.1
0.5
-0.3
0.4
0.6
number of trees in IC. Additionally, we
for LOP.
nearest competitor and can be up to orders of magnitude better than the worst competitor. LOP benefits from having much more fine fineigrained control of where it prunes than its competitors. Moreover, it can perform multiple rounds of pruning unlike FP, IC, and LRL However, the sensitivity analysis discussed in Q3 indicates that even one round of LOP yields substantially more compression than its competi- tors. FP and GR typically achieve the next best compression, though which of the two best varies: each outperforms the other on half the datasets. On XGBoost when FP out- performs GR, it tends to have much bigger compression factors whereas this trend does not hold on RandomForest. IC typically is the fourth best approach with LRL uniformly achieving the least amount of compression. Generally, all methods achieve better compression on RandomFores mod- els, likely because these models (much) bigger than the XGBoost ones.
For GR and LOP, GR solves its optimization problem using linear SVM with 1.2 regularization. IOP uses logistic regression and optimizes the negative lieeliiel with LI regularization. For LRL1 and FP", we adapt their public implementations to work with our internal representation of tree ensembles.
scikit-learn (Pedregosa et al., 2011).
All experiments are run on an Intel(R) Core(TM) 17-12700 with 64GB of memory. Each individual compression task is run on single thread (i.e., timing results measure single- thread performance). We apply a time limit of 6 hours for compressing a single model.?
5.2. Results
Q1: Comparing compression, predictive performance, and runtime. The left hand side of Tables and show the compression factors obtained by each method averag- ing over all learned XGBoost and RandomForest models per dataset. For both XGBoost and RandomForest, LOP systematically achieves the best compression factor. Its erage compression factors range from 5 to 356 XGBoost models and from 23 to 12 086 on RandomForest models. LOP typically has 2-3x better compression factor than its
The right-hand side of Tables and 2 shows the difference in balanced accuracy between the compressed ensemble and the original ensemble for respectively the XGBoost and RandomForest models. All compression methods result in models that, on average, only have a small loss. The differ- ence in performance is typically less than 0.5 percentage points. For LOP,, see that the accuracy loss the test set is quite close to 0.5% (i.e., the chosen value for A), which suggests that no overfitting occurs on the validation set. Even with its far superior compression rates, LOP maintains balanced accuracy as well as the other methods.
oven/ compreess
hit //tp:////ttt thub sbusch bhaschjaaggrr s leaaf re nement exper
"sttps:/ httpsss//aittut /aithas. cwn/ www///eundee--eee http/aros///eeeeeeeeoo
'The time limit was only exceeded for a small number of Ran- domForest models; see Table A8 in the Appendix for an overview.
The above tables show compression rates and balanced ac-

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
LOP
XGB
LOP
XGB
GR
0.50
0.95
0.90
0.95
Balanced Accurccy
0.94
Baianced Accurccy
0.94-
0.88
0.95
0.93
0.86
0.86
0.92
0.92
0.84
0.91
0.91
0.82
California
0.90
Spambestt
0.82
Callfornia
0.50
Spambesse
10a
10
202
10
102
16
Number of Leaves
Number of Leaves
Number of
Number Leaves
(a)
(b)
Figure 2. Comparison of Pareto fronts for (a) LOP vs. XGBoost (b) and all methods two representative datasets. The x-axis shows the number of leaves in log scale and the y-axis shows the balanced accuracy. In (a), the dashed line connect a compressed LOP model to the performance of its original XGBoost model. These are colored red the original model is not the Pareto front for XGBoost.
curacies separately, but a user may want to select the "best" model according to some size versus performance trade-off mechanism. This can be visualized using a Pareto curve where model appears on the curve only if achieving a bet- ter balanced accuracy requires larger ensemble making smaller ensemble requires sacrificing balanced accuracy.
tacks (Moshkovitz et al., 2021; Devos et al., 2021a). For each fold, we use Kantchelian et al.'s (2016) exact MILP approach to find the nearest adversarial example for 500 randomly selected test examples using global timeout of 30 minutes.
Table 3 shows that the median time for finding the nearest adversarial example on an XGBoost model compressed by LOP is 2.5 to 10 times less than for models compressed by its competitors. It is much more efficient to perform robustness checking on the compressed models than the original XGBoost models. Interestingly, Table A7 in the appendix shows that LOP returns more robust ensembles.
A question that comes to mind is: can we preselect models to compress based on the Pareto front? Figure 2a shows that the answer is no: Pareto-optimal compressed models can be obtained from Pareto-suboptimal XGBoost models.
Figure 2b shows the Parcto fronts obtained for the different compression methods applied to the XGBoost models on two datasets." 9 Again LOP clearly outperforms the other methods, in terms of how much size reduction can be ob- tained for a given level of balanced accuracy.
For resource constrained devices, two things are relevant. First, prediction time is correlated with energy (i.c., battery) use (Verachtert et al., 2016). Second, the memory footprint of the model is also important. However, both factors de- pend (strongly) on the precise implementation of decision forest and therefore, we look at two proxies instead. Be- cause test time is typically dominated by the number of splits to evaluate, we report the median number of nodes that an instance passes through when using the ensemble to make a prediction. For memory footprint, we use a formula from prior work that assumes that storing each node requires 17 + 4- C bytes, with C the number of classes (Buschjäger & Morik, 2023). Table 3 shows that LOP leads to better ensembles on both metrics. In particular, LOP produces models that use substantially less memory than the other approaches.
Finally, Figure A8 and A9 in the Appendix show the run- times of each compression method on the XGBoost and Ran- domForest models, respectively. IC is the fastest method, typically taking on the order of seconds, but it yields very lit- tle compression. T.OP and FP exhibit similar runtimes. GR is slightly slower than LOP and FP on the XGBoost models, but much slower on the Rores models that are generally larger in size. LRL 1 is clearly the slowest approach.
Q2: Robustness checking and resource usage. Next, we evaluate the effect of compression on two use cases where it is beneficial to have smaller models: robustness checking and resource-constrainee devices. Empirical ro- bustness measures the average distance to the nearest ad- versarial example for a given set of correctly classified nor- mal examples, which NP-complete problem for de- cision forests (Kantchelian et al., 2016). It is often used as measure of a model's susceptibility to evasion at-
Q3: Sensitivity analysis LOP. We now explore the effect of two of LOP's hyperparameters: (1) A which controls the maximum allowable loss in predictive performance com- pared to the original ensemble, and (2) R which specifies the number of rounds of level-by-level compression that is performed. We now investigate how varying these hyperpa- rameters affects performance on four representative datasets: Adult, California, Phoneme, and Spambase.
'Figure A2 in the appendix shows these for all datasets. The same is true for other baselines, see Figures A3, A4, A5 and A6 Figure A7 in the appendix shows these for all datasets.
8

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
Table Distribution (25%, Median 75%) rohustness checking runtime (in seconds), number of splits to evaluate at test time model size (in KB) before and after applying the different compression methods to XGBoost ensemble. Results are obtained by (1)
finding the median per XGBoost parameter combination (i.c., number of trees, max depth and learning rate) over the datascts and folds and (2) computing the quantiles these 48 median values (i.c., the number of parameter combinations).
Verif. time (s)
#Splits to evaluate
Memory footprint (KB)
25%
Median
75%
25%
Median
75%
25%
Median
75%
XGB
116.49
369.24
1092.64 64
94.5
197.00
386.13
45.6
92.3
211.0
GR
22.91
44.31
78.39
40.88
90.75
151.00
11.5
22.4
33.0
IC
31,90
70.75
134.06
37.00
66.25
120.00
17.1
28.6
48.4
LRL
65,30
148.28
447.86
71.88
147.25
226.50
29.6
58.8
130.0
FP
17.27
32.05
79.67
36.75
53.75
101,50
9.7
15.3
29.2
LOP
9.60
13.34
21.17
21.13
28.75
35.75
5.6
8.2
12.0
Table 4. Effect of varying A E {0.25,0.5, 1,2] and R E {1,2,3} while keeping, respectively, R and A = 0.5 on LOP's performances on four representative datasets. The hand side shows compression ratios while right hand side shows difference in balanced accuracy (i.e., percentage point difference) between LOP's compressed model and the original ensemble. For each dataset, results are averaged over 48 learned XGBoost ensembles and corresponding compressed models obtained by LOP.
Compress. ratio (x)
Diff. Bacc (% Point)
R=2
0.5.
R=2
A=0.5
Dataset
-0025
=0.5
=1
-2
R=1
=2
=3
A
0.25
=0.5
=1
=2
R=1
=2
Adult
26.0
31.8
45.3
67.5
23.0
31.8
35.5
-0.4
-0.2
0.5
1.4
0.1
-0.2
-0.1
California
7.3
9.2
11.9
17.4
7.0
9.2
10.1
0.3
0.6
1.1
2.0
0.5
0.6
0.6
Phoneme
6.7
7.5
10.4
6.0
6.0
7.5
8.6
1.2
1.3
1.8
2.6
1.0
1.3
1.4
Spambase
7.0
8.5
12.1
17.2
6.8
8.5
9.2
0.7
0.9
1.4
2.4
0.8
0.9
0.9
while keeping R affects both the compression ratio and the difference in balanced accuracy obtained by LOP compared the base XGBoost ensembles. There is clear effect: increasing A yields more compression but harms predic- tive performance. Setting A 0.25 yields slightly less compression than A = 0.5 but does give better predictive performance. Moving from twice as much compression but tends to lead to slightly bigger drops in predictive performance.
Table shows how varying A E {0.25,
tude larger than those of prior methodologies while obtain- ing similar predictive performance to the baselines. More- over, we show that LOP has several other benefits. In terms of robustness checking. I.OP produces more robust models than its competitors and it is faster check the robustness of LOP models. For resource constrained devices, LOP offers more efficiency in terms of making predictions and produces models that have a much smaller memory footprint.
0.5 to A = 2 achieves
Alternatively, Table shows how varying R (1,2,3) while keeping A 0.5 affects the compression ratio and predictive performance obtained by T.P.. Going from R = to It = 2, yields larger wins in compression while slightly degrading performance on three datasets but marginally im- proving it on the Adult dataset. Performing third round es- sentially does not change predictive performance while still allowing for (slightly) more compression. This increases runtime (see Figure All in the Appendix).
6. Conclusion
We propose LOP, a novel beeeel approach to com- pressing previously learned tree ensembles. Empirically, LOP achieves compression ratios that are order of magni-

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
Acknowledgements
Devos, L., Perini, L., Meert, W., and Davis, J. Detecting evasion attacks in deployed tree ensembles. In Proceeding of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 120-136, 2023.
This research is supported by the Flemish government under the "Onderzzeksprogrammaa Artificièle Intelligentie (AI) Vlaanderen" programme (HB, JD & WM), the European Union's 's Horizon Europe Research and Innovation program under the grant agreement TUPLES No. 101070149 (LD & JD), the KU Leuven Research Fund (C2E/23/007, HB & WM) and iBOF/21/075 (TM& & JD).
Donos, C., Dimmpllmann M., and Schulze-Bonhage, A. Early seizure detection algorithm based on intracranial eeg and random forest classification. International Jour- nal of Neural Systems, 25(05): 2015.
Impact Statement
Fan, L., Wang. Z., and Wang, H. Human activity recognition model based on decision tree. In Proceedings of the 1st International Conference on Advanced Cloud and Big Data, pp. 64-68, 2013.
This paper presents work whose goal is advance the field of Machine Learning, and the standard societal conse- quences of such work apply. More particularly, the work positively affects sustainability and reliability (fairness, ro- bustness) of machine-learned models.
Friedman, H. Greedy function approximation: gradient boosting machine. Annals of Statistics, pp. 1189-1232, 2001.
References
Grinsztajn, L., Oyallon, E., and Varoquaux, G. Why do tree-based models still outperform deep learning on typ- ical tabular data? In Advances in Neural Information Processing Systems, volume 35, pp. 507-520, 2022.
Blockeel, H., Devos, L.., Frénay, B., Nanfack, G., and Ni-
jssen, S. Decision trees: from efficient prediction to responsible AI. Frontiers in Artificial Intelligence, 6, 2023.
Hara, S. and Hayashi, K. Making tree ensembles inter- pretable: A Bayesian model selection approach. In Pro- ceedings of the 2 International Conference on Artificial Intelligence and Statistics, volume 84, pp. 77-85, 2018.
Breiman, L. Random forests. Machine learning, 45(1): 5-32, 2001.
Buciluă, C., Caruana, R., and Niculescu-Mizil, A. Model compression. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 335-541, 2006.
Kantchelian, A., Tygar, J. D., and Joseph, Evasion and hardening of tree ensemble classifiers. In Proceedings of the 33rd International Conference on Machine Learning, pp. 2387-23990 2016
Buschjäger, S. and Morik, K. Joint leaf-refinement and ensemble pruning through regularization. Data Mining and Knowledge Discovery, 37(3):1230-1266) 2023.
Lauwereins, S., Badami, K., Meert, W., and Verhelst, M. Optimal resource usage in ultra-low-power sensor inter- faces through context- and resource-cost-aware machine learning. Neurocompating, 169:236-245, 2015.
Chen, T. and Guestrin, C. XGBoost: A scalable tree boost- ing system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 785-794, 2016.
Liu, B. and Mazumder, R. FORESTPRUNE: Compact depth- pruned tree ensembles. In Proceedings of the 26th Inter- national Conference on Artificial Intelligence and Statis- tics, pp. 9417-9428 2023a.
Daghero, F., Burrello, A., Xie, C., Benini, L., Calimera, A., Macii, E., Poncino, M., and Pagliari, D. J. Adaptive random forests for energy- energy-efficient inference on micro- controllers. In Proceedings of the 29th IFIP/EEEE Inter- national Conference on Very Large Scale Integration, pp. 1-6, 2021.
Liu, B. and Mazumder, FIRE:
An optimization approach for fast interpretable rule extraction. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 1396-1405, 2023b.
Devos, L., Meert, W., and Davis, J. Versatile verification of tree ensembles. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pp. 2654 2664, 2021a.
Lu, Z., Wu, X.,, Zhu, X., and Bongard, J. Ensemble prun- ing via individual contribution ordering. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 871-880, 2010.
Devos, L., Meert, W., and Davis, J. Verifying tree ensembles by reasoning about potential instances. In Proceedings of the 2021 SIAM International Conference on Data Mining, pp. 450-458, 2021b. doi: 10. 10.1113/1.997 0777/119971111111 1976700.51.
Margineantu, D. D. and Dietterich, T. G. Pruning adap- tive boosting. In Proceedings of the 14th International Conference on Machine Learning, pp. 211 11-2188 1997.
10

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
Moshkovitz, M., Yang, Y.-Y., and Chaudhuri, K. Con- necting interpretability and robustness in decision trees through separation. In Proceedings of the 38th Interna- tional Conference on Machine Learning, volume 139, pp. 7839-7849, 2021.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Ren, S., Cao, X., Wei, Y., and Sun, J. Global refinement of random forest. In 2015 IEEE Conference on Computer Vision and Pattern Recognition, pp. 723-730, 2015.
Tsoumakas, G., Partalas, I., and Vlahavas, I. An ensemble pruning primer. In Applications of Supervised and Unsu- pervised Ensemble Methods, pp. 1-13. Springer, 2009.
Vanschoren, van Rijn, N., Bischl, B., and Torgo, L. Openml: Networked science in machine learning. SIGKDD Explorations, 15(2):99-60, 2013.
Verachtert, A., Blockeel, H., and Davis, Dynamic early stopping for naive Bayes. Proceedings of the 25th International Joint Conference Artificial Intelligence, 2016.
Zhang, Y., Burer, S., Nick Street, W., Bennett, P., and Parrado-Hernáne E. Ensemble pruning via semi- definite programming. Journal of Machine Learning Research, 7(7), 2006.

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
A. Usefulness of leaf refinement
We claim in the paper that individual trees may need to suboptimal in order for an ensemble be optimal. We now make that claim more precise.
Trees induce partition of the input space through their leaves. Given a tree T, let s(x:) {1, 21,2..... n be the index of the leaf r is sorted into, and let A; {x E (x)) = z}. The tree defines a piecewise constant function that is constant within each X; From a least squares point if view, the tree is optimal if its prediction in leaf i is the mean of all target values of instances in XG
y
X-0.6
0.8
An ensemble similarly partitions the input space into sub- sets Xx l E 21,2,.. L} (with k indexing all leaves in the ensemble), such that the ensemble's predictions are constant within each subset. The ensemble is optimal if its predic- tions in each subset equals the mean of all target values in that subset.
0.3
0.6
X
Our claim, now, is that ensembles exist such that if all individual trees 73 in ensemble are optimal in the above sense, the ensemble is not optimal, and vice versa. To prove the claim, it suffices to show an example.
X-1.2
0.6
Figure Al show two decision stumps (trees of depth 1) with mie-dmmesiional inputs. Each tree represents piecewise constant function; the optimal value in each leaf is the mean of the target function in the interval covered by the leaf. The forest is then piecewise constant function with three intervals, but the constants are biased: they differ from the mean of the target function over the interval. The bias can be removed by changing the leaf values, which then leads to trees that are not individually optimal.
12
2
y
X
Averaging gives biased predictions. Squared loss: 0.044
0.96
Optirall trees (b Uj:
X-0
X-12
0.18
This examples shows how leaf values that optimal in individual tree are suboptimal in the forest, and vice versa. This is an argument for optimizing u after the whole forest has been learned.
Squared loas: 0.028
0.8
1.2
2 X
Blas: -0 Blox D5
Bler -0
Figure Al. Bias in forests. Consider approximating x with decision stumps with random splits x. The first stump (red) splits on x < 0.6, the second (bluc) on x < 1.2. Both have in their lcaves an optimal prediction (the population mean of all instances in that leaf). A forest that averages their predictions represents a partitioning of the input space into intervals, with predictions showing a clear bias w.r.t. the optimal prediction for each interval (dashed line). An unbiased forest exists with exactly the same splits: it suffices to store different values in the leaves, which are then suboptimal from an individual tree's point of view.
B. Size of optimization problems
Consider a forest with M trees, and consider the optimiza- tion problems of the form discussed in the paper, which contain on and 6n parameter for each active node (ex- cept root nodes, which have only Cn2 and leaf nodes, which have only b..).
The number of parameters to optimize at level is M (and not 2M) because the b's are excluded on this level. If the pruning results in M remaining trees, then on level the number of parameters is 2 2 M' (2 parameters for each of the 2M active nodes on level 1), with M' < M. On each level, the algorithm tries to prune, and each pruned subtree becomes a leaf n that contributes only parameter bn to all lower levels, rather than 2, 4, 8, ... parameters as we go
12

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
tive to its competitors. Here, we detail the differences in compression between the baselines. While worse than I.P,, FP and GR offer the next best performance. On XGBoost models, FP achieves better compression than GR half the time. However, when FP wins, it tends to result in much bigger compression factors and hence it has a higher average compression ratio than GR. For RandomForest, GR performs better on nine datasets. In contrast to the XGBoost results, sometimes GR can achieve orders of magnitude better com- pression than FP. While they achieve substantially less com- pression than I.OP, GR and FP yield better compression than LRL and IC on both XGBoost and RandomFores models. This is because they have more fine-grasd one-grained pruning mecha- nisms. FP can prune at any level of tree, whereas LRL and IC only remove trees. GR typically applies multiple rounds of refinement/pruning until convergence, whereas LRL and IC only apply round of refinement.
Table AI. Properties of the binary classification datasets: Name, number of examples, number of features, and class prior (i.e., proportion of positive examples).
Name
# Examples
# Features
Mnist
13814
784
0.49
Electricity
38474
8
0.50
Jannis
57580
54
0.50
Vehicle
846
18
0.49
DryBean
13611
16
0.19
California
20634
8
0.50
Compas
4966
11
0.50
Volkert
24325
180
0.53
Adult
48842
32
0.24
Ijennl
141691
22
0.10
MiniBooNE
72998
50
0.50
Phoneme
5404
5
0.71
Spambase
4601
57
0.39
We now discuss the effect of compression on the number of trees retained in the ensemble. We compute the tree re- duction ratio, which is the number of trees in the original ensemble divided by the number of trees in the compressed model. Tables A3 and A4 show this ratio for each method on XGBoost and RandomForest models, respectively. Higher numbers indicate fewer trees in the compressed model. On XGBoost models, ensembles compressed by LOP have the fewest number of trees. Among the baselines, IC is more effective at pruning full trees than LRL reduces the number of trees in the original forest by a factor 23.3 com- pared to a factor 2. Note that GR never removes trees from the ensembles. In contrast, on RandomForest models, both IC and FP reduce the number of trees more than LOP. How- ever, the fact that LOP has better compression ratios than FP, suggests that FP's compression ratios are mainly obtained through pruning full trees.
Credit
16714
10
0.50
Table A2. Properties of the regression datasets: Name, number of examples and number of features.
Name
# Examples
# Features
Abalone
4177
8
Ailerons
13750
33
Cpu
8192
12
Houses
20640
8
House 16H
22784
16
WineQuality
6497
11
Elevators
16599
16
deeper. Generally, at level 1, if there are a active nodes, of and are internal nodes, there are a1 + 2 * a2 S 2a parameters. At the lowest level d, this number can be 2d M in the worst case, if nothing ever gets pruned; but the point is of course that LOP does prune a lot, starting at the upper levels.
which @1 are wateess-on----hhe------
Table shows the average performance over a wide vari- cty of XGBoost settings. However, often a user wants to understand the trade-off between model size and predictive performance. This can be visualized using Pareto curves, which show all models that are not dominated by another model. That is, model appears on the curve only if achiev- ing better balanced accuracy requires a larger ensemble or making smaller ensemble requires sacrificing balanced accuracy.
C. Detailed experimental results
In this section, we provide more detailed results about the three experimental questions in the main text. Finally, we answer the additional two questions: (Q4) What the effect of compression on regression forests? (Q5) How does the runtime of compression scale with forest size?
Figures A2- A6 show the Pareto front for each compression algorithm versus XGBoost on all datasets. Moreover, for the compressed models on the front, they show the perfor- mance of its original, uncompressed XGBoost variant using a dashed line. Interestingly, there exists no direct mapping between compression algorithm's 's Pareto front and XG- Boost's Pareto front. That is, the best compressed models do not necessarily come from the best XGBoost models.
Q1: Comparing compression, predictive performance and runtime. Tables and 2 in the main text show the com- pression factors obtained by the considered compression algorithms, averaged over respectively all learned XGBoost and RandomForest settings per dataset. The main body of the paper focused on discussing I.OP's performance rela-
Figure A7 shows that typically LOP's Pareto front dominates
13

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
Table A3. The average reduction ratio for each dataset for the XGBoost models on the binary classification experiments. This ratio computed as the number of trees in the original ensemble divided by the number of trees in the compressed model. Higher ratios are better. The ratios are indicated bold.
Table A4. The average reduction ratio for each dataset for the RandomForest models on the binary classification experiments. This ratio is computed as number trees semble divided by the number of trees in the compressed model. Higher ratios are better. The best ratios are indicated bold.
original en-
GR
IC
LRL1
FP
LOP
LRL1
FP
LOP
Mnist
1.0
5.4
2.5
2.7
8.1
Mnist
1.0
23.2
2.4
20.7
15.1
Electricity
1.0
1.6
1.3
1.3
2.2
Electricity
1.0
23.1
8.2
18.8
20.4
Jannis
1.0
8,5
1.5
3.7
8.1
Jannis
1.0
7.1
2.2
3.7
5.5
Vehicle
1.0
4.4
1.2
2.7
7.5
Vehicle
1.0
16.5
1.0
11.0
14.2
DryBean
1.0
10.3
1.7
5.0
24.1
DryBean
1.0
18.6
1.2
33.3
14.4
California
1.0
2.5
1.4
1.9
3.3
California
1.0
22.3
1.8
12.7
16.5
Compas
1.0
25.1
2.8
22.5
35.6
Compas
1.0
15.5
1.0
80.1
46.9
Volkert
1.0
7.1
2.5
2.9
8.2
Volkert
1.0
33.5
9.3
29.6
20.6
Adult
1.0
4.4
1.6
4.2
10.3
Adult
1.0
96.6
12.1
47.8
17.4
Ijenn
1.0
1.3
1.3
1.6
3.1
Ijennl
1.0
77.9
3.0
49.3
29.7
MiniBooNE
1.0
2.2
1.3
1.6
2.4
MiniBooNE
1.0
14.8
5.1
8.4
9.2
Phoneme
1.0
2.2
1.4
2.4
5.7
Phoneme
1.0
13.3
2.0
14.3
6.8
Spambase
1.0
3.0
1.6
2.9
5.9
Spambase
1.0
24.3
1.3
29.6
21.7
Credit
1.0
23.3
2.0
10.5
26.8
Credit
1.0
9.8
1.0
8.0
11.5
average
1.0
7.2
1.7
4.7
10.8
average
1.0
28.3
3.7
26.2
17.8
large parts of the other fronts. This conclusion aligns with what found in Table 1.
Figures A8 and A9 show the distribution of compression time (s) for each method every dataset for XGBoost mod- els and RandomForest models, respectively. On XGBoost models, LOP takes on average 241s to compress a forest. This is equally as fast as GR, which takes 240s. FP and IC are faster, taking respectively 84s and 6s. LRL is clearly the slowest, taking 812s average. On RordomForest models, which are larger than the XGBoost models, LOP takes 434s. FP and IC remain faster at respectively 250s and 17s, but they result in less compression. GR is now much slower, taking 3404s. IRI.l remains the slowest method, taking 4470s on average.
Q3: Sensitivity analysis. Here we explore how sensitive LOP is to two of its hyperparameters: A, which controls the maximum allowed loss in predictive performance when tuning the regularization parameter, and R, which denotes the number of rounds of level-by-level compression that is performed. In addition the compression and predictive performance results shown Table 4, we now discuss how these hyperparameters affect LOP's runtime.
Figure A A10 shows a boxplot of LOP's runtime for each value of per dataset. Increasing A leads to decreased runtimes. Essentially, allowing for a larger loss in accuracy allows LOP be more aggressive in its compression.
Q2: Robustness checking and resource usage. addi- tion the time needed compute the empirical robustness (shown in Table and discussed in the main paper), it is also relevant to know how compression affects the robust- ness of the learned XGBoost ensembles. Table A7 reports the average test set empirical robustness for considered approaches for each dataset. Higher values indicate a more robust model. Interestingly, applying LOP uniformly leads models that are more robust than the original XGBoost models. More generally, LOP has the best average empirical robustness scores nine out of 14 datasets. While IC and FP also improve the robustness of the XGBoost models, GR and LRL1 do not always increase robustness. In fact, they can actually yield less robust models than XGBoost in some cases.
Figure A1l shows boxplot of LOP's runtime for each value of R per dataset. Increasing R leads to longer runtimes. However, the last rounds are typically faster than the first rounds. This makes sense: The initial rounds compress the model. Hence, the optimization problem becomes smaller, leading to faster runtimes later rounds.
Q4: Performance on regression forests. We now consider compressing regression forests. We omit IC because it is tailored to classification problems, and it is non-trivial to adapt it to handle regression tasks. We evaluate the methods on seven regression datasets, which are detailed in Table A2. We use 5-fold cross- validdaai with folds for training. for validation, and for testing. In each fold, we train models
14

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
XGB
LOP
0.79
0.90
0.76
0.99
Balancen Accuracy
0.88
0.74
0.95
0.77
0.72
0.80
Adult
0.78
169
30a
0.97
10P
10F
0.96
0.92
0.90
0.67
Balanced Accuracy
0.94
0.91
0.06
0.96
0.92
0.05
0.84
0.64
0.90
Vehicle
DryBean
California
10"
16
107
10'
100
10'
10*
10
107
0.99
0.94
0.95
0.85
Balanced Accuracy
0.90
0.92
0.98
0.85
0.91
Volleert
lcrn1
MiniBooNE
Phonems
10
10a
30
10
10
107
10a
10
10'
107
10
Number of Leads
Number Leafs
0.78
Balanced Accuracy
0.94
0.9%
0.76
0.75
Spambase
Creait
0.73
Number of Leafs
Number of Leafs
Figure A2. Comparison of Pareto fronts of LOP vs. XGBoost on all datasets. The x-axis shows the number of leaves in log scale and the y-axis shows balanced accuracy. dashed connect a compressed LOP model to performance of an original XGBoost model. These are colored red if the original model is not on the Pareto front for XGBoost.
15

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
XGB
GR
0.79
0.76
0.90
Balancen Accuracy
0.74
0.86
0.77
0.72
0.98
0.82
0.80
0.74
16R
10P
10a
16
18P
16
0.90
Balanced Accuracy
0.67
0.95
0.89
0.91
0.88
0.87
0.90
0.92
Vehicle
DryBean
California
Compas
0'32
1x3P
107
10
0.94
Balanced Accuracy
0.95
0.93
0.55
0.92
0.80
0.98
0.85
0.30
Vallsert
linn11
0.89
MiniBooNE
0.75
Phonems
107
10"
102
10
107
10"
10'
10'
10"
Number of Leads
Number Leafs
Bolanced Accuracy
0.77
Spambase
0.75
Creait
1.'0
10
Number of Leafs
Number of Leafs
Figure A3. Comparison of Pareto fronts of GR vs. XGBoost on all datasets. The x-axis shows the number of leaves in log scale and the y-axis shows balanced accuracy. The dashed lines connect compressed GR model the performance of an original XGBoost model. These are colored red if the original model is not on the Pareto front for XGBoost.
16

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
XGB
IC
0.79
0.90
Balancen Accuracy
0.78
0.74
0.86
0.77
0.72
0.76
0.98
0.80
annis
104
104
18a
304
0.96
0.95
Balanced Accuracy
0.88
0.67
0.96
0.92
0.91
Vehicle
DryBean
California
Compas
0.32
16
10
109
10'
10*
0.87
Balanced Accuracy
0.96
0.93
0.95
0.91
0.84
0.93
0.92
Volkert
licnn]
0.89
MiniBoo
0.82
Phonems
102
30
10*
107
10"
10
10
10'
Number of Leafs
Number of Leafs
0.95
Balanced Accuracy
0.93
Spambase
0.75
Credit
10'
Number of Leafs
Number of Leafs
Figure A4. Comparison of Pareto fronts of IC vs. XGBoost on all datasets. The x axis shows the number of leaves in log scale and the y-axis shows the balanced accuracy. The dashed lines connect a compressed IC model to performance an original XGBoost model. These are colored red if the original model is not on the Pareto front for XGBoost.
17

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
XGB
LRL1
0.79
0.30
Balancen Accuracy
0.78
0.74
0.80
0.72
0.76
0.82
0.98
0.75-
annis
0.78
36
104
16P
0.92
Balanced Accuracy
0.95
0.88
0.91-
0.86
Vehicle
DryBcan
Calirmii
10'
3255 3875 10
10'
10
10
Balanced Accuracy
0.93
0.52
0.90
0.91
0.98
0.90
Volkert
jicnn1
Min
Phonems
0.89
109
30
10'
10'
10'
10a
10a
10"
Number of Leafs
Number Lf
Balanced Accuracy
0.94
Spambaas
Credi
30"
10
10'
Number of Leafs
Number of Leafs
Figure A5. Comparison of Pareto fronts of LRLI vs. XGBoost on all datasets. The x-axis shows the number of leaves in log scale and the y a-axis shows the balanced accuracy. The dashed lines connect compressed LRLI model to performance of an original XGBoost model. These are colored red if the original model is not on the Pareto front for XGBoost.
18

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
XGB
FP
0.92
0.79
Balanced Accumcr
0.80
0.74
0.99
0.77
0.86
0.76
0.72
0.84
0.82
0.50
Electricity
0.74
Janis
0.90
Balancca Accurary
0.95
0.66
0.88
0.97
0.94
0.64
Vehiclo
DryB.can
Califoria
Com
10a
10F
10P
102
107
10'
0.85
Balanced Accuracy
0.93
0.85
0.92
0.98
0.80
Volkert
iinn
MiniBocNE
0.75
Phonems
167
107
10'
10a
10
10"
10
10'
30'
10'
Number of Leats
Number of Leafs
Balanced Accuracy
0.94
0.93
0.76
0.91
0.90
Spambaase
Credit
10
Number of Leafs
Number of Leafs
Figure A6. Comparison of Pareto fronts of FP vs. XGBoost on all datasets. The x-axis shows the number of leaves in log scale and the y-axis shows the balanced accuracy. The dashed lines connect a compressed FP model to the performance an original XGBoost model. These are colored red if the original model is not on the Pareto front for XGBoost.
19

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
LOP
XGB
GR
LRL1
FP
0.99
0.78
Balanced Accuracy
0.88
0.74
0.96
0.84
0.76
0.75
Adut
Minss
0.78
Electricity
16
107
10
107
20*
10
30
10
0.68
0.90
0.67
Balarced Accuracy
0.88
0.65
0.84
0.54
Vehicle
DryBcon
0.82
California
Compas
0.89
10
16
10'
10'
10'
10'
10
10
10'
0.94
0.95
Balanced Accuracy
0.84
0.90
0.52
0.98
0.85
0.92
0.90
0.78
0.80
0.89
Vollortt
jcnn1
MiniBooNF
0.74
Phonome
10'
10a
10'
107
10
10'
10'
10*
10'
10'
10'
Number of Leaves
Number Leaves
0.78
0.95
Balsnced Accurary
0.94
0.92
0.75
0.91
0.74
Spambase
10a
Figure A7. Pareto fronts for all compression methods on all datasets. The x-axis shows the number leaves in log scale and the y-axis shows the balanced accuracy.
20

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
GR
IC
LRL1
FP
LOP
10a
Compression
101
10
Anist
Electriity
Janeis
Vahide
DryBean
Califonia
Compus
Volkert
Adul
Honrl
MiniBookt
Phoneme
Spambase
Cradit
Figure A8. The distribution of the compression time (s) of XGBoost models in seconds log scale.
GR
IC
LRL1
FP
LOP
101
10a
Compression (8)
10²
20
10a
Mnist
Electricity
Jannis
Vehide
DryBean
Califonia
Compas
Volkert
Aduit
licml1
MiniBrotE
Phoneme
Spanbase
Credit
Figure A9, The distribution of the compression time (s) of RandomForest models in seconds log scale.
21

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
averaging over all learned XGBoost and RandomForest per dataset. Similarly the binary classification setting, LOP achieves the best compression factors, with FP and GR being second and third best. LOP's average compression factor ranges from 19 to 234 on XGBoost models and from 5 to 744 on RandomForest models.
Table A5. The average tree reduction ratio for each dataset for the XGBoost models on the regression experiments. This ratio is computed as the number of trees in the original ensemble divided by the number of trees in the compressed model. Higher ratios are better. The best ratios are indicated in bold.
GR
LRL
1
FP
LOP
Abalone
1.0
1.5
11.2
25.9
The right hand side of Tables 1 and 2 show the RMSE for respectively the XGBoost and RandomForest models before and after compression. All compression methods yield an average performance loss on an independent test set that typically remains below the threshold A. This indicates, as also found in the binary classification setting, that overfitting to the validation set is unlikely. Consequently, LOP achieves higher compression ratios for the same loss in predictive performance compared to the baselines.
Ailerons
1.0
1.4
4.6
12.7
CpuSmall
1.0
1.5
1.0
9.5
Houses
1.0
1.3
3.4
6.5
House16H
1.0
1.6
12.5
16.2
WineQuality
1.0
1.4
11.7
15.3
Elevators
1.0
1.2
1.3
6.2
average
1.0
1.4
6.5
13.2
We now discuss how the compression methods affect the number of trees retained in the ensembles. Tables A5 and A6 show the average tree reduction ratios for the different meth- ods on XGBoost and RandomForest models, Higher numbers indicate fewer trees in the compressed model. On both XGBoost and RandomForest models, en- sembles compressed by LOP have the fewest number of trees. This finding deviates slightly from the results on bi- nary classification, where FP is more effective at pruning full trees in RandomFores models; see Table A4). The fact that FP prunes fewer trees than in the binary classification setting could explain why it achieves lower compression ratios for RandomForest regression.
Table A6. The average tree reduction ratio for each dataset for the RandomForest models on the regression experiments. This ratio is computed as the number of trees in the original ensemble divided by the number of trees in the compressed model. Higher ratios are better. The best ratios are indicated in bold.
GR
LRL1
FP
LOP
Abalone
1.0
1.0
2.9
6.4
Ailerons
1.0
1.0
6.2
5.5
CpuSmall
1.0
1.0
8.4
6.6
Houses
1.0
4.2
12.0
9.9
House
1.0
5.6
3.7
9.0
WineQuality
1.0
2.4
5.6
4.8
Flevators
1.0
2.9
7.5
7.3
Q5: Scalability analysis.
average
1.0
2.6
6.6
7.1
We now explore how compression approaches scale based on two ways of characterizing the size of the original en- semble: (1) M, the number of trees in an ensemble and (2) D, the maximum allowed depth of an individual tree. We consider the same four binary classification datasets that we used for Q3.
on all combinations of the following hyperparameters:
XGBoost
RandomForest
M E [10, 25, 50, 100]
E [50, 100, 250] E [10, 15]
D E [4, 6, 8]
First, explore varying M E [100, 250, 500 while keep- ing the maximum tree depth fixed. For XGBoost, we fix D = 6 and the learning rate = 0.1 and for RandomFor- est we fix D = 10. Figures A12 and A13 show how the compression time in seconds varies as a function of M for XGBoost and RandomForest, respectively. Note that time on log scale. Interestingly, LOP maintains a nearly constant compression time as the number of trees increases. This is likely because it is able to remove many trees upfront and this initial optimization problem is very simple. In contrast, the compression time for the other approaches increases as the number of trees in the original ensemble increases. Finally, LOP is typically the second faster approach after IC, however, IC achieves very little compression compared to LOP. In conclusion, LOP offers excellent scalability with respect to the number of trees in an ensemble compared to
7 E [0.1, 0.25, 0.5, 1.0]
not applicable
with M the number of trees, D the maximum depth of the trees and 17 the learning rate in XGBoost. This yields 48 XGBoost models and 6 RandomForest models, to which we then apply the different compression algorithms. There are two differences to our binary classification setup in that we (1) evaluate the Root Mean Squared Error (RMSE) in- stead of balanced accuracy and (2) use a maximum allowed drop in performance
2% that is relative to the un- compressed model's performance (e.g., if the uncompressed model achieves RMSE of 0.250 on the validation set, then the compressed model's R MSE on that same validation set should be smaller than 0.255).
The left hand side of Tables A9 and A10 show the com- pression factors obtained by each compression algorithm by
22

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
Table A7. The average empirical robustness hefore (XGR) and after compressing the ensemble according Kantchelian al's (Kantchelian et al., 2016) exact MILP approach to find the nearest adversarial example for 500 randomly selected test examples. Results are averaged over the binary classification XGBoost models. The best results are bold.
XGB
GR
LRL
I.OP
Mnist
0.194
0.195
0.214
0.180
0.221
0.221
Electricity
0.043
0.031
0.041
0.039
0.035
0.048
Jannis
0.067
0.097
0.098
0.079
0.096
0.108
Vehicle
0.145
0.147
0.158
0.138
0.155
0.162
DryBean
0.181
0.182
0.209
0.176
0.219
0.215
California
0.079
0.078
0.083
0.077
0.080
0.092
Compas
0,050
0.165
0.076
0.055
0.175
0.170
Volkert
0.164
0.187
0.196
0.178
0.198
0.197
Adult
0.348
0.338
0.410
0.341
0.449
0.469
Ijenn
0.224
0.197
0.230
0.216
0.224
0.226
MiniBooNE
0.114
0.122
0.128
0.123
0.121
0.134
Phoneme
0.098
0.088
0.109
0.081
0.106
0.103
Spambase
0.091
0.091
0.100
0.087
0.114
0.120
Credit 0.112
0.275
0.207
0.132
0.283
0.301
Average
0.136
0.157
0.161
0.136
0.177
0.183
Table A8. Summary of which methods exceed the 6 hour timeout for Q1 for RandomForest (i.c., on how many folds out 5). and D denote the number of trees and depth of the trees in a forest.
4=0.25
A=0.5
4=1
A=2
10a
Compression Time (S)
M
D
GR
LRL
Adult
250
15
2/5
NA
10a
Ijennl
100
15
NA
5/5
Ijennl
250
10
2/5
5/5
Ijenn1
250
15
4/5
5/5
10a
Jannis
250
15
NA
5/5
MiniBooNE
250
10
NA
4/5
Adult
Califarnia
Phoneme
Spambass
MiniBooNE
250
15
5/5
5/5
Figure A10. The distribution of compression time (in seconds) when varying LOPPs hyperparameter [0.25, 0.5, 1,2)
its competitors.
Second, we explore varying the maximum tree depth while keeping the number of trees in the ensemble fixed. For XG- Boost, we consider D [6, 8, 10) with M 50 and v) 0.1. For RandomForest, we consider D E [10, 15, 20, 25] with M = 100. Figures A and A15 show how the com- pression time in seconds varies as a function of D for XG- Boost and RandomForest, respectively. Note that time is
little, if any, compression. For RandomForests, the story is slightly different. The runtime for LOP and FP tends to increase as the maximum tree depth does whereas this pa- rameter has less effect on the other approaches. Still, this hyperparameter does not affect the relative order of runtime performance for the compression methods.
on a log scale and that some methods exceed the time limit; see Table All for an overview. For XGBoost, the maxi- mum tree depth does not exhibit strong influence on the compression time of any of the approaches. An interesting exception occurs with GR on XGBoost models for Adult: its runtime decreases substantially as the tree depth increases. This is likely because the compression operations that GR can perform yield larger than permitted performance drops meaning; hence it has small runtime because performs
23

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
Table Compression results on XGBoost regression models. The original models are characterized by their number leaves (#Leaf) and root mean squared error (RMSE) on the test set. We report the compression ratios and test set RMSE for each compression technique. 8x compression ratio means that compressed model has times fewer leaf nodes than original ensemble. The best compression ratios are given in bold.
#Leef
Compress. ratio (x)
RMMS
Dataset
XGB
LRL1
FP
LOP
XGB
GR
LRL1
LOP
Abalone
2557.6
28.6
1.4
178.3
120.4
0.298
0.297
0.308
0.303
0.293
Ailerons
3406.3
11.1
12.9
35.2
0.202
0.200
0.196
0.202
0.205
Cpu
2803.3
4.8
1.5
1.8
29.2
0.141
0.132
0.129
0.140
0.140
Houses
3810.4
8.4
1.3
6.9
19.6
0.173
0.173
0.167
0.175
0.176
Housel6H
3783.3
16.6
1.6
82.4
233.8
0.330
0.335
0.327
0.339
0.343
WineQuality
2969.0
16.8
1.3
71.6
234.6
0.352
0.353
0.355
0.351
0.358
Elevators
3795.2
8.4
1.2
2.2
21.6
0.213
0.207
0.202
0.213
0.219
Average
3303.6
13.5
1.4
50.9
99.2
0.244
0.243
0.240
0.246
0.248
Table A10. Compression results on RandomForest regression models. The original models are characterized by their number of leaves (#Lcaf) and root mean squared error (RMSE) on the test We report the compression ratios and set RMSE for each compression technique, A 8x compression ratio means that the compressed model has 8 times fewer Icaf nodes than the original ensemble. The best compression ratios are given bold.
#Leaf
Compress, ratio (x)
RMSE
Dataset
RF
GR
LRL
FP
LOP
RF
GR
LRL
FP
LOP
Abalone
79168.6
19.8
1.0
35.3
744.6
0.272
0.273
0.272
0.274
0.280
Ailerons
184674.7
2.2
1.0
6.2
7.7
0.185
0.185
0.185
0.189
0.190
Cpu
118589.5
1.6
1.0
8.3
10.1
0.118
0.118
0.118
0.122
0.125
Houses
300815.2
81.9
4.2
12.0
51.5
0.159
0.162
0.158
0.163
0.164
House 16H
200964.8
105.6
5.3
3.7
492.5
0.306
0.316
0.313
0.311
0.327
WineQuality
62076.9
6.0
2.4
5.3
5.8
0.322
0.326
0.325
0.328
0.331
Elevators
189162.0
93.9
2.9
7.4
23.6
0.204
0.203
0.206
0.206
0.207
Average
162207.4
44.4
2.5
11.2
190.8
0.224
0.226
0.225
0.227
0.232
R=1
R-2
R-3
10a
Comprission Time (4)
Table A11. Summary of which methods exceed the hour timeout for Q5 (scalability) for RandomForest (i.e., on how many folds out of 5). M and D denote the number trees and depth of the trees in forest.
10a
10l
M
D
GR
I.R.1
Adult
100
15
3/5
NA
Adult
100
20
2/5
NA
10a
Adult
Califonia
Phoneme
Spambase
Adult
100
25
3/5
4/5
Adult
250
10
5/5
1/5
Adult
500
10
5/5
5/5
Figure AII. The distribution of compression time (in seconds)
when varying LOP's hyperparameter | [1..
24

---

Compressing Tree Ensembles through Level-wise Optimization and Pruning
LGP
GR
IC
LRL1
FP
Adult
105
California
Phoneme
Spambase
10a
Compression Timi [s)
10'
10'
z0z-
10*
10a
250 Number
500
250
560
1.00
Number Trees
Number of
Trees
Figure A12. Average compression time (s) function of the number of trees M in the original XGBoost models with D and = 0.1. Results are shown for each compression method on four representative datascts.
LOP
GR
LAL1
FP
Adult
Ca liforiaa
Phoneme
Spambase
Compriccioo Time
109
10"
102
10a
10
102
10P
10a
10'
24a Number Trees
250 Number of Trees
Number Trees
Number Trees
Figure A13. Average compression time (s) as function of the number of trees M in the original RandomForest models with D 10. Results are shown for each compression method on four representative datasets.
LOP
GR
LAL1
FP
Adul
California
Phoneme
Spambase
10>
10a
102
Compression Time
10
10a
10c
10
Maximum depth
Maximum depth
Maximum depth
Maximum depth
Figure A14. Average compression time (s) function of the maximum tree depth D used when learning the original XCBoost models
with M = 50 and 0.1. Results are shown for each compression method on four representative datasets.
LOP
GR
LRL1
FP
Adult
Cal
10'
Phoneme
Spambase
Comprecsion Time (6)
10r
10'
100
102
102.
10a.
107
20 Maximum depth
15
10
25
15
20
Maximum depth
Maximum depth
Maximum death
Figure A15. Average compression time (s) as function of the maximum tree depth used when learning the original RandomForest models with M- = 10. Results are shown for each compression method on four representative datasets.
25


Reviews:
[{"review_id": "79tRdkyi2A", "reviewer": "Reviewer_fAT9", "summary": "The paper introduces LOP (Level-wise Optimization and Pruning), a method for compressing decision tree ensembles by pruning subtrees level by level while updating leaf values to maintain predictive accuracy. Unlike prior methods that prune entire trees or merge only leaf nodes, LOP can remove subtrees at any level, achieving compression rates 10 to 100 times higher than competitors. By optimizing leaf values globally, it minimizes accuracy loss, typically staying within 0.5% of the original model. Empirical results show that LOP significantly reduces memory footprint, speeds up robustness verification, and enhances efficiency on resource-constrained devices, making tree ensembles more practical for deployment.\n\n## update after rebuttal\nThank you to the authors for providing detailed feedback and clarifications. While the responses are appreciated, they do not sufficiently address my primary concerns or significantly alter my overall evaluation of the manuscript. Therefore, I will maintain my original score, and I strongly recommend a major revision to strengthen the paper.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your comments. We acknowledge that this work has many links with XAI (including knowledge distillation), and also with robustness, verification, inference efficiency, and other topics. However, the focus of this work is on the specific task of ensemble compression; we position this work in that area and that is also what the comparative evaluation focuses on. Reaching out to all these other areas would lengthen the paper, would raise more questions that warrant investigating, and would detract from the main message. Rejecting the paper just for not doing this would mean it is held to a much higher standard than related work in this area (none of that work does all these comparisons).\n\nQ1: LOP can be applied to regression by using an appropriate regression loss in Eq. 2. Applying it to multi-class problems would require a wrapper around it, such as one-versus-all classification. The same holds for most of the related work. \nFor regression, we trained multiple XGBoost ensembles with [10, 25, 50, 100] trees and [4, 6, 8] max depth with learning rate 0.1 on 2 datasets (Wine Quality, Houses) using 5 fold CV. These datasets are a subset of those used in the paper by Liu et al. (2023) as suggested by reviewer CuzX. LOP achieves an average compression ratio of 14.3, compared to 7.7 for GR, 1.4 for LRL1 and 4.4 for ForestPrune (Liu et al., 2023). In terms of predictive performance, LOP increases the Root Mean Square Error by only 2% compared to the uncompressed model, which equals the allowed loss in performance (i.e., hyperparameter $\\Delta$). Hence, the conclusions are similar to the binary classification case. We will add these results to the paper.  \n\n\nQ2: We have not measured actual times; prediction requires sequential execution of if-statements and it seems obvious that the computation time is linear in the number of such statements.\n\nQ3: We have not investigated this; this is a different research question, completely out of scope for this paper. None of the related work investigates this, and we do not see how it could even fit in an 8 pages paper.\n\nQ4: As said, we focus on ensemble compression, and while exploring links with distillation based approaches may be interesting, we consider it out of scope in this paper. Furthermore, we do not know of distillation approaches that start from a forest and return a forest; if the reviewer has specific approaches in mind, a concrete reference would be appreciated.\n\nQ5: LOP typically takes longer than XGBoost itself. Ensembles are trained (and potentially compressed) once but used many times: the point of this work is to make them more efficiently usable / analyzable. The combination of training and compression time is usually in the order of seconds or minutes on a laptop: it is not an issue in practice.\n\nQ6: In response to the reviews, we ran experiments on Random Forests. Results are comparable to those with XGBoost.\nSpecifically, we use Scikit-Learn Random Forest classifiers with a maximum tree depth in [10, 15] and number of trees in [100, 250, 500], on 3 representative datasets: Spambase, Phoneme and California. A full table of results can be found in our answer to reviewer N4NE (this table also contains results for an additional method called ForestPrune (Liu et al. 2023) suggested by reviewer CuzX). LOP averages a compression ratio of 228.2, whereas GR achieves a ratio of 120.2, and both IC and LRL1 achieve a ratio of 1.3. The average drop in balanced accuracy for LOP is 0.01, which is similar to most baselines. In terms of run time, it takes LOP on average 164 seconds to compress these ensembles, compared to 6892 seconds for GR, and 5071.8 seconds for LRL1. IC takes on average 71.6 seconds, but it has much worse compression ratios than LOP. Hence, LOP compresses more than the competitors without losing accuracy. Moreover, it is around 42x faster than GR which is its nearest competitor in terms of compression ratio. We will add these results to the paper.", "claims_and_evidence": "The paper’s central claims are well supported by empirical evaluations on multiple datasets and rigorous comparisons with baseline compression methods. Specifically, the assertion that LOP can achieve compression rates 10 to 100 times greater than existing techniques while maintaining nearly the same predictive performance is backed by quantitative results across 14 benchmark datasets, demonstrating high compression ratios with minimal accuracy loss. Additionally, the paper provides strong evidence that robustness verification is significantly faster on LOP-compressed models compared to both the original XGBoost models and those compressed by competing methods. The authors further substantiate LOP’s efficiency gains with explicit memory footprint calculations via proxies, highlighting its advantages in resource-constrained environments. However, one limitation is that the experiments are confined to binary classification tasks, leaving open the question of whether LOP’s compression benefits extend to multi-class problems or other data modalities such as image data.", "methods_and_evaluation_criteria": "The proposed LOP method and the evaluation criteria are well-aligned with the problem of compressing tree ensembles while maintaining predictive performance. The authors assess LOP using 14 benchmark datasets from OpenML, covering diverse binary classification domains, which is appropriate given that tree ensembles like XGBoost and Random Forests are widely used for structured data tasks. The evaluation metrics—compression ratio, accuracy retention, robustness verification speed, and memory footprint—are relevant for assessing the trade-offs between model size and performance.\n\nMoreover, comparisons against three competitive baselines (Global Refinement, Individual Contribution, and Leaf refinement combined with L1 ensemble pruning) ensure a fair assessment of LOP’s effectiveness. The use of Pareto front visualizations to illustrate the trade-off between compression and accuracy further strengthens the evaluation. However, a potential limitation is that all datasets are binary classification tasks, leaving unanswered how LOP would perform in multi-class classification or regression settings. Additionally, while LOP is tested on XGBoost ensembles, further validation on Random Forests or other tree-based architectures could enhance generalizability.", "theoretical_claims": "The paper does not present detailed formal proofs of correctness.", "experimental_designs_or_analyses": "The experimental design in the paper appears well-structured, with a strong benchmarking approach against relevant baselines. However, there are a few potential concerns:\n\n- The evaluation is entirely on binary classification tasks, leaving out multi-class classification and regression, which could behave differently under compression. It is unclear whether LOP’s effectiveness generalizes to tasks with continuous target variables or high-cardinality categorical targets.\n- The chosen baselines (GR, IC, and LRL1) are reasonable, but other pruning techniques, such as cost-complexity pruning in decision trees or neural network-inspired distillation methods, are not considered.\n- The authors conduct a sensitivity analysis on $\\Delta$ (allowed accuracy loss) and $R$ (number of pruning rounds), which is good practice. However, their choice of hyperparameters for the base XGBoost models (e.g., number of trees, learning rate, tree depth) is based on a predefined grid, which may not always yield the best initial models before compression. A stronger baseline might slightly alter results.\n- Since LOP makes significant changes to the model structure, it would be useful to see results on unseen test distributions to test robustness.", "relation_to_broader_scientific_literature": "LOP builds on prior research in tree ensemble pruning, model compression, and robustness verification by introducing a level-wise pruning approach that optimizes leaf values while reducing model size. Unlike traditional ensemble pruning methods (e.g., Margineantu & Dietterich, 1997; Tsoumakas et al., 2009) that remove entire trees, or global refinement techniques (Ren et al., 2015) that adjust leaf predictions post hoc, LOP prunes subtrees at any level while simultaneously updating leaf values, achieving significantly higher compression with minimal accuracy loss. Its focus on reducing memory footprint aligns with recent efforts to make tree ensembles more efficient for edge computing (Fan et al., 2013; Daghero et al., 2021). Additionally, by producing smaller models, LOP accelerates robustness verification (Kantchelian et al., 2016; Devos et al., 2021), addressing a key challenge in ensuring the safety and fairness of machine learning systems.", "essential_references_not_discussed": "While the paper covers traditional ensemble pruning techniques, it overlooks more recent advancements, such as knowledge distillation methods introduced by Hinton, Vinyals, and Dean (2015) in Distilling the Knowledge in a Neural Network. This technique, which transfers knowledge from a large model to a smaller one while preserving performance, has been adapted for tree ensembles, including gradient boosting distillation.", "other_strengths_and_weaknesses": "While the paper discusses memory footprint and decision path length, it does not directly measure inference latency. Including actual prediction time benchmarks on different hardware (e.g., CPU, embedded systems) would provide stronger evidence of real-world efficiency gains.", "other_comments_or_suggestions": "A deeper analysis of how accuracy degrades as more pruning is applied (beyond the Pareto front visualization) would provide useful insights for practitioners.", "questions_for_authors": "**Question 1:** Have you tested LOP on multi-class problems or regression tasks? If not, do you anticipate any fundamental challenges in applying LOP to these settings?\n\n- If LOP does not generalize well beyond binary classification, its applicability would be more limited than suggested. Demonstrating strong performance in multi-class or regression tasks would increase confidence in LOP’s generalizability.\n\n**Question 2:** Have you measured actual inference time improvements on different hardware configurations (e.g., CPU, embedded devices)?\n\n- If inference time is not significantly reduced despite the smaller model size, the practical efficiency gains may be overstated. Reporting real-world latency measurements would strengthen the claim that LOP improves efficiency.\n\n**Question 3:** Have you evaluated LOP’s compressed models on out-of-distribution (OOD) data or domain shifts? Does aggressive pruning increase sensitivity to dataset shifts?\n\n- If LOP sacrifices robustness for compression, this would be a key limitation. A robustness analysis would clarify whether LOP is suitable for real-world deployment in dynamic environments.\n\n**Question 4:** Did you consider comparing LOP against gradient boosting distillation or other distillation-based tree compression methods? If not, what are the key differences that make LOP preferable?\n\n- If LOP outperforms both pruning-based and distillation-based compression techniques, it would further validate its significance. If not, distillation may be a viable alternative that should be acknowledged.\n\n**Question 5:** How does the runtime of LOP compare to the time required to train an original XGBoost model? Is LOP feasible for large-scale datasets?\n\n- If LOP takes significantly longer than training from scratch, its use case may be limited to scenarios where model compression is a strict requirement.\n\n**Question 6:** Have you tested LOP on Random Forests, BART, or other tree ensemble models?\n\n- If LOP is specifically optimized for boosting-based ensembles (e.g., XGBoost) but does not work as effectively on bagging-based methods like Random Forests or Bayesian ensemble methods like BART, its applicability may be more limited than suggested. Demonstrating strong performance across diverse tree-based models would increase confidence in LOP’s versatility.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y5YXRm5iHV", "reviewer": "Reviewer_N4NE", "summary": "The paper \"Compressing tree ensembles through Level-wise Optimization and Pruning\" proposes a combination of ensemble pruning, decision tree pruning and leaf-refinement to reduce the memory footprint of forests for reduced resource usage during deployment. To do so, the authors re-formulate the inference of a forest into a tensor-based formulation that also captures the inferencing process on each level of each tree in the forest. Based on this formulation, a pruning algorithm is presented, that starts at the root node of each tree and iteratively refines labels while removing subtrees. For level $l=0$ this means removing entire trees, while at the last level we remove leaf nodes. In-between, partial trees are removed. The experimental evaluation on 14 datasets shows that the pruned forests are comparable (in a 0.5% environment) in performance, while being much, much smaller.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive comments, and especially that this paper “could become the go-to paper in this area”, and “more [experiments] is always better, but not always necessary”. Thanks also for the suggestions for improvement, which we will take into account.\n\nTo answer your questions:\n\nQ1, Q3: The 5 fold cross-validation and tuning of alpha work as follows. We partition into 5 subsets. In each fold, 1 subset serves as test set. Of the 4 remaining subsets, 3 are used for training and pruning the ensemble (that is, X in Eq. 2 is based on these 3 subsets). The fourth 'validation' set is used to tune alpha; a model with performance drop $>\\Delta$ is discarded. A log-range of alphas (range 0.001 to 10000) is tried, and among the models not discarded, the smallest model is returned. This is the model for which we ultimately report size, accuracy on test set, etc.\n\nQ2: The number of parameters to optimize at level 0 is M (not 2M because the b’s are excluded on this level, see lines 142-143, right column). At level 1, the number of parameters is not 2\\*2\\*M but 2\\*2\\*M’ with M’ the number of trees not pruned at level 0 (M’<=M). On each level we try to prune, and each pruned subtree becomes a leaf that contributes only 1 parameter to all lower levels, rather than 2, 4, 8… as we go deeper. Generally, at level l, if there are x active nodes (of which y leaves-on-a-higher-level and z internal nodes), there are y+2\\*z < 2x parameters. By the time we proceed to the lowest level d, this number can be 2\\*2^d\\*M in the worst case, if nothing ever gets pruned, but the point is of course that we do prune a lot, starting at the upper levels.\n\nQ3: See Q1.\n\nQ4: Yes, the implementation is publicly available.\n\nQ5: We used XGBoost because we consider it the state of the art. In response to the review, we have run additional experiments with Random Forests. We also include results for ForestPrune (Liu et al. 2023) suggested by reviewer CuzX. Specifically, we use sklearn RFs with a max depth in [10, 15] and number of trees in [100, 250, 500], on 3 datasets. The table below shows those results. LOP averages a compression ratio of 228.2, whereas GR achieves a ratio of 120.2 and both IC and LRL1 achieve a ratio of 1.3. The average drop in balanced accuracy for LOP is 0.01, similar to the baselines. ForestPrune fails to compress the biggest models; it returned the empty model. Over the successful runs, ForestPrune has a compression ratio of 5 and loses 0.09 in balanced accuracy. In terms of run time, it takes LOP on average 164s to compress these ensembles, compared to 6892s for GR, 5072s for LRL1, and 2665s for ForestPrune. While IC is faster (72s), it has much worse compression ratios than LOP. Hence, LOP compresses more than the competitors without losing accuracy. Moreover, it is around 42x faster than GR which is its nearest competitor in terms of compression ratio. We will add these results to the paper.\n\n| Dataset | depth | nb_trees | Compr.: GR | IC | LRL1 | LOP | ForestPrune |Runtime: GR | IC| LRL1| LOP | ForestPrune |\n|------------|-------|----------|--------------:|------:|--------:|-------------:|---------:|----------------:|-------:|-------------:|------:|-------:|\n| California |10|100|120.7|1.1|2.6|166.6|2.5|3752.7|14.9|3209.2|213.0|562.6|\n| California ||250|210.8|1.1|1.0|396.5|2.7|13884.5|82.7|7718.6|235.1|2844.8|\n| California ||500|254.8|1.1|1.0|788.7|2.5|33363.5|352.2|18589.8|305.2|6030.0|\n| California |15|100|178.2|1.1|1.0|89.0|6.8|3358.0|19.6|5350.0|370.4|788.7|\n| California ||250|370.9|1.2|1.0|418.8|6.7|13987.4|105.5|12709.3|404.8|4385.3|\n| California ||500|564.1|1.2|1.0|533.5|6.8|32928.4|447.2|24220.1|446.9|9698.1|\n| Spambase |10|100|32.5|1.1|1.2|71.8|3.8|392.7|3.4|316.2|39.8|161.1|\n| Spambase || 250 | 52.7 | 1.1 | 1.0| 214.0 | 3.5 | 1514.8 | 12.8 | 778.2 | 44.1 | 951.4 |\n| Spambase || 500 | 81.5 | 1.2 | 1.0 | 405.0 | (fail) | 4978.8 | 44.7 | 1932.3 | 44.5 | 3478.4 |\n| Spambase | 15| 100 | 64.8 | 1.2 | 1.0 | 128.6 | 5.8 | 597.5 | 3.5 | 357.2 | 58.9 | 246.9 |\n| Spambase || 250 | 71.6 | 1.1 | 1.0 | 148.2 | 5.5 | 1833.6 | 14.7 | 1233.3 | 59.4 | 1478.6 |\n| Spambase || 500 | 86.9 | 1.2 | 1.0 | 390.1 | (fail) | 5134.0 | 54.2 | 2590.2 | 58.0 | 5122.1 |\n| Phoneme | 10 | 100 | 9.2 | 1.6 | 2.2 | 21.0 | 5.3 | 208.0 | 3.4 | 466.2 | 70.0 | 174.5 |\n| Phoneme | | 250 | 13.9 | 1.6 | 1.7 | 54.6 | (fail) | 981.1 | 13.7 | 1734.5  | 72.7  | 1026.4 |\n| Phoneme | | 500 | 21.6 | 1.6 | 1.3 | 162.3 | (fail) | 3771.3 | 45.5 | 3193.5 | 93.1 | 3650.6 |\n| Phoneme | 15 | 100 | 6.2 | 1.6 | 1.9 | 17.1 | 8.2 | 173.8 | 3.9 | 569.0 | 131.0 | 273.3 |\n| Phoneme | | 250 | 7.4 | 1.6 | 1.9 | 25.3 | (fail) | 626.9 | 15.0 | 2130.4 | 154.1 | 1571.6 |\n| Phoneme | | 500 | 15.3  | 1.6 | 1.1 | 77.0 | (fail) | 2577.8 | 51.8 | 4194.9 | 150.2 | 5523.0 |\n| Average ||| 120.2 | 1.3 | 1.3 | 228.2 | 5.0  | 6892.5 | 71.6 | 5071.8 | 164.0 | 2664.9 |", "claims_and_evidence": "The paper is generally well-written and the arguments of the authors can be easily followed. While I do have some minor questions wrt. to the experimental evaluation, I think the authors present convincing evidence for each claim.", "methods_and_evaluation_criteria": "Although somewhat limited (14 datasets, 5 methods), the experimental evaluation fits the proposed method.", "theoretical_claims": "No theoretical claims are made.", "experimental_designs_or_analyses": "The experimental design is overall sound. Direct competitors are compared over 14 benchmarking datasets. The runtime and memory footprint is included. While I generally prefer larger sets of experiments for tree ensembles (i.e. more datasets and comparisons via critical difference diagrams), I think the overall analysis still holds.", "relation_to_broader_scientific_literature": "The paper presents a non-trivial, but somewhat natural extension of the recent \"Joint leaf-refinement and ensemble pruning through l1 regularization\" paper by Buschjäger and Morik from 2023. While the original paper combines leaf-refinement with ensemble pruning, the method presented in this paper goes one step further and allows for pruning at every stage/level of every tree in the forest. Personally, I see that there is a growing (re-)interest in tree/ensemble pruning in the literature, and hence this paper fits perfectly. Due to its strong performance, it could become one of the go-to papers in this area of research.", "essential_references_not_discussed": "I am not aware of any missing essential references.", "other_strengths_and_weaknesses": "The paper is generally well-written (minus a few questions I state below) and was easy to follow for me. I think, the formulation of the forest in tensor-notation is generally helpful given the current trend in tensor-based computations. The appendix A offers an example of when leaf-refinement is useful, which is nice for future reference. \nThe experimental evaluation could be enhanced by including more datasets and other methods, however, given that this is a conference submission I don't see any issue here (i.e. more is always better, but not always necessary).", "other_comments_or_suggestions": "In case the paper is not accepted, I suggest improving the following parts: \n- Personally, the example in section 3.0 and 3.1 was not really helpful to me. I would have preferred more explanations on the method itself\n- Neither $\\alpha$, nor $\\Delta$ are explained in detail. While the meaning of both parameters are somewhat clear (see my question below), they are detrimental for Alg 1. I would suggest adding more explanations about that\n- I think Q3 in the experimental evaluation is slightly misleading: While it is true, that LOP has only two hyperparameters $\\Delta$ and $R$, the overall approach has more hyperparameters such as learning rate, optimization method, loss etc. While I understand that these are \"additional\" hyperparameters, a practitioner has to choose these as well. I would add more discussions about this.", "questions_for_authors": "1) In the experimental evaluation, you state that you use a 5-fold cross-validation, with 3 folds for training, 1 for validation and 1 for testing. For fitting $\\alpha$ you also mention that you are using a validation set. I am a bit confused by this. Typically, I would expect a three-way split: train data (for the forest), prune data (for running LOP) and then test data for testing. Now I would repeat this splitting X times with X different random seed. Please explain how you did this here? \n2) Algorithm 1 shows that we have to perform an optimization problem $R\\cdot d$ times (line 6). You mention that these are comparably simple / easy and the runtimes you show reflect this, but could you please comment on the exact sizes of these optimization problems. On $l=0$, I have to optimize over 2M parameters and then on the next level $2\\cdot 2\\cdot M$ (given all trees are balanced and have the same height) and so on? \n3) How did you choose $\\alpha$?\n4) Do you have plans to make your implementation publicly available? \n5) The \"Joint leaf-refinement and ensemble pruning through l1 regularization\" uses Random Forest while you use XGBoost. Why? And, did you try RF as well?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "55rarEaSRT", "reviewer": "Reviewer_sKmw", "summary": "The manuscript proposes a novel method (LOP) for compressing tree-based ensembles by pruning leaves and/or entire trees. LOP is based on sparse optimization and has applications to bagging or boosting ensembles. Experimental results show that the approach cuts down model size with minimal impact on performance. This makes models more energy-efficient and easier to formally verify.\n\n## update after rebuttal\n\nThe new experiments in reply to other reviewers' comments only reaffirm my view that LOP is a fast and effective method for compressing tree-based models. I think this manuscript makes a meaningful contribution to the literature on this topic, and therefore stand by my original assessment.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your positive comments! We will take your suggestions into account.", "claims_and_evidence": "The primary claim of the manuscript is that LOP reduces model size without harming performance (too much). This is verified in a wide range of experiments on benchmark datasets. Three relevant baselines are considered (GR, IC, LRL1). LOP fares well in all trials.", "methods_and_evaluation_criteria": "The selection of datasets and benchmarks are sensible. The experiments appear well-designed. The results are clear and compelling.", "theoretical_claims": "The manuscript does not make any theoretical claims.", "experimental_designs_or_analyses": "The experimental design is sensible and rigorous. I especially like the Pareto frontier plots.", "relation_to_broader_scientific_literature": "The work connects with recent efforts to distill ensemble models into more compressed representations.", "essential_references_not_discussed": "I'm unaware of any essential references that were omitted.", "other_strengths_and_weaknesses": "The writing is clear and direct. The proposal is not exactly revolutionary, but the experimental results clearly suggest that LOP is effective at reducing model size with minimal information loss. This is an important contribution.", "other_comments_or_suggestions": "-p. 7: \"LRL1 is by clearly the slowest approach\" -> \"LRL1 is clearly\" or \"LRL1 is by far...\"\n\n-In Tables 1 and 3, it would be helpful to bold the winning results as elsewhere.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "iVmO0Phpb6", "reviewer": "Reviewer_CuzX", "summary": "This paper proposes a new algorithm for compressing a learned tree ensemble while keeping its generalization performance. \nIn each depth of a given tree ensemble, the proposed method prunes its redundant subtrees and adjusts the remaining leaf values. \nThrough the experiments on binary classification datasets, the authors demonstrated that the proposed method attained higher compression rates than the existing baseline methods without significantly degrading accuracy. \nIn addition, the experimental results showed that the proposed method could improve the computational costs of both test inference and robustness verification.\n\n## update after rebuttal\nI appreciate the authors for their insightful response. Because the additional experimental results provided by the authors address my concern regarding the lack of comparisons with the existing methods, I have decided to improve my score. If the paper is accepted, I hope the authors will include these results in the final version.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your insightful comments. Below, we address your main concerns: (a) baselines for comparison and (b) scaling behavior.\n\nExisting baselines:\nThank you for pointing us to this related work. Among the listed papers, we find Nan et al. (2016) less relevant as it solves a different problem: obtaining the value of each feature has a cost and the goal is to minimize the expected feature acquisition cost at prediction time.  This is a very different goal. The other papers are more relevant and we will discuss them in the revised version (it seems we missed them because they are not connected through citations with the body of literature we studied or the baselines we compare to, so thank you for pointing us to them).\n\nThe novelty of our work is not jeopardized, as all these methods clearly differ from our approach:\n\n- ForestPrune (Liu et al. 2023) simplifies forests by cutting whole trees at a specific level, rather than pruning individual nodes like LOP does. This way, it loses a crucial aspect of trees, namely, that some subtrees can be deeper than others: a tree can partition the input space in a finer-grained manner in some areas, and in a coarser manner elsewhere. A second difference is that LOP refines leaf values, while ForestPrune does not. Hence, LOP explores ensembles that are not in ForestPrune’s search space. \n\nEmpirically, we have compared LOP and ForestPrune on XGBoost classifiers on all datasets mentioned in our paper. We have taken the same XGB settings, that is, number of trees in [10, 25, 50, 100], tree depth in [4, 6, 8] and learning rate in [0.1, 0.25, 0.5, 1] and averaged the results. As the table below shows, LOP’s compression factors are up to 10 times better than ForestPrune’s, for comparable accuracy:\n\n| | Compr.: | LOP   | forestprune  | Diff. BAcc.: | LOP  | forestprune |\n|-----------------|--------|------:|-------------:|-----|-----:|-----------: |\n|Spambase || 8.5   | 3.6  || 0.9  | 0.7 |\n|Phoneme || 7.5   | 3.7  || 1.3  | 0.9 |\n|Electricity || 5.2   | 1.4  || 0.5  | 0.2 |\n|Adult || 31.8  | 37.2 || -0.2 | 0.1 |\n|Credit || 196.6 | 133.2|| 0.5  | 0.4 |\n|CompasTwoYears  || 356.8 | 240.3|| -0.1 | -0.5 |\n|DryBean[6vRest] || 28.8  | 15.6 || 0.3  | 0.4 |\n|Mnist[2v4] || 8.0   | 3.1  || 0.6  | 0.4 |\n|Volkert[2v7] || 8.3   | 4.9  || 0.6  | 0.4 |\n|Jannis  || 18.1  | 15.3 || 0.6  | 0.5 |\n|Vehicle || 8.0   | 2.6  || 1.4  | 1.8 |\n|MiniBooNE || 6.2   | 2.6  || 0.6  | 0.4 |\n|California || 9.2   | 2.5  || 0.6  | 0.4 |\n|Ijcnn1 || 6.5   | 2.3  || 0.4  | 0.1 |\n|Average || 50.0  | 33.4 || 0.6  | 0.4 |\n\nIn terms of runtime, compressing an ensemble takes LOP on average 236.5 seconds, whereas ForestPrune takes 98.5 seconds. We will include the full results in a revised version of the paper.\n\n- Hara et al. (2018) learn an additive model that contains a small set of “rules”; a rule is one path from root to leaf. This corresponds to an ensemble where each tree is constrained to have 1 leaf with non-zero value. LOP has no such constraint. Their experiments only consider models with at most 10 rules. \n\n- FIRE (Liu et al. 2024) re-learns leaf weights, regularizing for sparsity and “fusion” of non-zero leaves. It is very similar to the Global Refinement method (Ren et al. 2015), which we do cite and compare to in our paper; the main difference between GR and FIRE is in the fusion regularization and in the optimizer. LOP uses a different parametrization than FIRE: it uses fewer variables, yielding simpler optimization problems to be solved.  \n\nScaling:\nWe only considered up to 100 trees because it is known that including more trees rarely improves predictive performance. Similarly, XGBoost may overfit with deeper trees. We felt that testing the method on larger ensembles would artificially boost compression factors. That being said, we ran two experiments.\n\n1. We trained XGBoost with 100, 250 and 500 trees and max depth 8 on four datasets: Adult, California, Spambase, and Phoneme. LOP scales well. For LOP, the average run time on 100 trees is 195s, 250 trees is 520s and 500 trees is 425s. We hypothesize that adding more trees allows LOP to prune full trees more aggressively, leading to more efficient pruning on lower levels. For GR, average run time is 225s for 100 trees, 436s for 250 trees and 1988s for 500 trees. For LRL1 it is 2704s, 3667s, 7581s.  For IC it is 9s, 45s and 128s. All times are in seconds. \nThe average compression ratios are 86.4 for LOP, 4.6 for GR, 3.8 for LRL1 and 4.9 for IC.\n\n2. For scaling depth, the response to reviewers N4NE/fAT9 shows results for Random Forests with up to 500 trees and depth 15. ForestPrune fails to compress the biggest models, in which case it returns the empty model. We hypothesise that this is due to the greedy bottom-up approach of ForestPrune: it starts with the empty model and adds (partial) trees incrementally. We will investigate this further.\n\nWe will add these results to the paper.", "claims_and_evidence": "My main concern is the lack of comparisons to the existing methods, such as [Nan+, NeurIPS2016] and [Liu+, AISTATS2023], that aim to reduce the complexity of tree ensembles by pruning each tree. \nI believe the novelty and effectiveness of the proposed method can not be supported without comparisons with these existing baselines. \n\n- [Nan+, NeurIPS2016] Feng Nan, Joseph Wang, Venkatesh Saligrama. Pruning Random Forests for Prediction on a Budget. NeurIPS, 2016. \n- [Liu+, AISTATS2023] Brian Liu, Rahul Mazumder. ForestPrune: Compact Depth-Pruned Tree Ensembles. AISTATS, 2023.", "methods_and_evaluation_criteria": "- I think the proposed representation $c_n v_k + b_n$ is an interesting idea that can simultaneously express pruning a redundant subtree or refinements of leaf values. \n- I also think the experimental results shown in Table 2 demonstrated well the effectiveness of the proposed method in terms of not only compression performance but also verification efficiency. However, as mentioned above, I am concerned about the lack of comparisons to the related baselines.", "theoretical_claims": "This paper does not include theoretical claims.", "experimental_designs_or_analyses": "- My main concern is the lack of comparisons to the related baselines ([Nan+, NeurIPS2016] and [Liu+, AISTATS2023]), as mentioned above. \n- Another concern is that the number of trees and maximum tree depth were only examined up to 100 and 8, respectively. Since the computational complexity of the proposed method depends on these parameters, I think the scalability and sensitivity of the proposed method with respect to these parameters should be investigated.", "relation_to_broader_scientific_literature": "The key contributions of the paper are related to the field of practical techniques for learning tree ensembles. In particular, pruning a learned tree ensemble is one of the promising approaches from the perspectives of generalization performance [Ren+, CVPR2015], computational efficiency [Nan+, NeurIPS2016] [Liu+, AISTATS2023], and interpretability [Hara+, AISTATS2018] [Liu+, KDD2024]. \n\n- [Hara+, AISTATS2018] Satoshi Hara, Kohei Hayashi. Making Tree Ensembles Interpretable: A Bayesian Model Selection Approach. AISTATS, 2018. \n- [Liu+, KDD2024] Brian Liu, Rahul Mazumder. Fire: An Optimization Approach for Fast Interpretable Rule Extraction. KDD, 2024.", "essential_references_not_discussed": "As mentioned above, the key contributions of this paper seem to be related to the work by [Nan+, NeurIPS2016] and [Liu+, AISTATS2023]. \nI also think this paper is related to the existing studies on extracting rules from tree ensembles from the perspective of interpretability, e.g., [Hara+, AISTATS2018] and [Liu+, KDD2024].", "other_strengths_and_weaknesses": "I believe the presentation of this paper could be improved. \nFor example, this paper seems to use parentheses too frequently, which makes some sentences complex and difficult to follow.", "other_comments_or_suggestions": "Nothing in particular.", "questions_for_authors": "Nothing in particular.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a method to compress ensembles of decision trees. With this goal, the authors propose LOP, a method for pruning ensemble members or entirely removing them from the ensemble. The leaf predictions are updated in such a way that predictive accuracy is mostly unaffected. The authors carry out several experiments showing that LOP gives compression factors that are often 10 to 1000 better than other competing methods. The reviewers indicate that experimental design in the paper appears well-structured, with a strong benchmarking approach against relevant baselines. A limitation is that the evaluation is only on binary classification problems, however. The reviewers also indicate that the paper is generally well written. Some reviewers expressed points of criticism regarding missing comparisons with related methods from the literature. However, the authors in the rebuttal provided extra experimnetal results comparing with some of them. Overall I believe this is a borderline paper, but I think it is closer to the acceptance level.
Decision: Accept (poster)