- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies the transformation from decision trees (DTs) to ReLU neural networks (NNs). It first presents a constructive exact transformation that realizes a DT as an NN, and shows that the class-wise maximum over leaf scores makes the network depth grow with the number of leaves. To avoid this depth dependence, the paper introduces a -approximate transformation that replaces the class-wise maximum with a sum of leaf activations whose path-constraint violation is below . The resulting network has a fixed depth of four layers. The main guarantee states that, for every input, the transformed network agrees with the source DT at some nearby input within distance , where depends on the geometry of the tree predicates. Experiments on MountainCar and CartPole evaluate preservation of formally verified properties and a pruning-and-conversion workflow that trades network size against fidelity and closed-loop performance.
Critical strengths
- The paper clearly identifies why exact DT-to-NN transformations can become deep and introduces a fixed-depth approximation with an explicit geometric guarantee. The distinction between exact agreement and -approximate agreement is formalized, and the constant is defined carefully. This is consequential because it gives a principled alternative to depth-growing exact encodings.
- The paper evaluates five architectures and twenty seeds per environment, studies verified-property preservation as a function of , and reports a pruning-and-conversion trade-off. The code is released. This breadth supports the claim that the transformation is not tied to a single tree or controller.
Critical weaknesses
-
The fixed-depth network still has width linear in the number of tree nodes, and the experiments report about parameters for CartPole at . For simple low-dimensional control tasks, this is very large. The paper does not compare parameter counts against the exact transformation, against the source tree, or against training-based DT-to-NN baselines. This matters because the main motivation is deployability, and fixed depth alone does not imply a compact model.
-
Theorem 5.2 guarantees that for every there exists within such that the network and tree agree at . It does not directly bound the measure or frequency of disagreements unless the tree is locally constant. The paper does not report empirical or estimated values of , so readers cannot judge how wide the disagreement region is in the tested trees. This weakens the practical interpretation of the guarantee.
-
Only two low-dimensional environments and a small set of local properties are used. The reference controllers are trained for reward, not for these properties, so the baseline verified fraction is already low, especially for MountainCar. About of MountainCar checks are inconclusive and counted as not verified. The paper reports aggregate fractions but does not provide a per-property analysis of which properties are lost or preserved. This makes it difficult to assess whether the transformation preserves verified behavior in a meaningful sense.
Questions for authors
-
Please report the estimated or computed for the trees used in the experiments. Without this, the -guarantee cannot be interpreted in terms of actual input-space neighborhoods.
-
Please compare parameter counts and inference costs of the -approximate network with the exact transformation and with the source tree. In particular, for CartPole at , what is the tree size, and why is a network with about parameters preferable for deployment?
-
Please provide per-property verified and unverified results before and after conversion, rather than only aggregate verified fractions. This would clarify which properties are actually preserved and whether the MountainCar increase at large is meaningful or an artifact of the small property set.
-
In the pruning-and-conversion pipeline, is the fidelity measured against the original tree or the pruned tree? Please also report the performance of pruning alone without conversion, so the benefit of conversion can be isolated.
-
The sum aggregation can favor classes with more active leaves. Does the guarantee account for class-wise leaf imbalance, and can the disagreement region be larger than the boundary-neighborhood interpretation suggests in such cases?
6 comments
W2 / Q1 — Is meaningful for the tested trees? We agree with the reviewer that this should be measured, and we added the values to the revised paper (Appendix H, Figure 9). We computed for every tree by enumerating linearly independent predicate subsets along root-to-leaf paths. The median is on MountainCar and on CartPole, and the largest is and , so the median at is 23 and . We also measured, for sampled disagreement points , the distance to the nearest point where the tree outputs the converted NN's class. This is the distance controlled by Lemma 5.3. We use up to 500 disagreement points per tree, found among uniformly sampled inputs and the inputs visited in 50 episodes of .
The results expose a gap between the bound of Lemma 5.3 and the observed behavior. All measured deviations satisfy the lemma, but they are far smaller than , by four to six orders of magnitude, and they grow roughly linearly with : the measured distance is at most on MountainCar and on CartPole, with a median of about . The reason is that is a worst-case constant, which becomes very large when some split hyperplanes are nearly parallel, as in trees extracted from ReLU networks. In such cases, can exceed the input domain even though the measured deviations remain relatively small. For axis-aligned trees, , and the bound is .
A complementary disagreement guarantee. After observing the gap between and the measured deviations, we investigated why the theoretical bound can be this conservative. We found that the construction provides an additional guarantee on where disagreements can occur, independently of .
Intuitively, in , the leaf reached by the tree always has activation , because its path violation is zero. Any other leaf can only be active if its path violation is smaller than . Since its path must diverge from the path followed by at some split, this can happen only if lies within distance of that split's hyperplane. Thus, away from these hyperplanes, exactly one leaf is active, and the network predicts the tree's class. The revised paper formalizes this intuition as its new Theorem 5.2.
Theorem 5.2 (revised paper). Write the normalized predicate of node as .
If at every split on the path followed by , then and predict the same class. Equivalently, disagreement can occur only if lies within distance of a splitting hyperplane on its own tree path.
The proof is in Appendix B. It also shows that class-wise leaf counts cannot affect predictions outside these regions.
Relation to the distance bound. The distance bound of the original Theorem 5.2 is now Lemma 5.3. The new Theorem 5.2 follows directly from the same construction (Equations 11–15) and requires no additional assumptions. We did not state it in the original submission because our analysis focused on the distance-based guarantee. The reviewer's request to measure prompted us to study this matter and make this property explicit.
The two results answer different questions:
- Lemma 5.3 bounds how far an input must be moved for the tree to predict the network's class. This is particularly informative when is small, e.g., for axis-aligned trees, where the distance is at most .
- Theorem 5.2 identifies where disagreements can occur, independently of . It is particularly informative when is large, since disagreements are confined to -slabs around splitting hyperplanes on the input's tree path.
Distance-based results, including the property-preservation corollary discussed in W3, continue to rely on Lemma 5.3.
Example. Theorem 5.2 guarantees that every disagreement lies within Euclidean distance of a splitting hyperplane on its path, but not that every point inside these slabs disagrees. In Figure 1b, at , lies outside the relevant slabs and agrees, whereas is near the split at and disagrees. Theorem 5.2 thus gives an informative guarantee when is too conservative.
We also checked the theorem empirically: on uniformly sampled states, no disagreement occurred outside the -slabs of any tree, for .
Measured frequency. The frequency of disagreement is the conversion-only curve of Figure 3, which compares of the unpruned tree with . At , they disagree on less than 1% of the inputs in both environments. At and , they disagree on 1.3% and 14.6% of the uniformly sampled MountainCar inputs and on 0.02% and 0.4% of the CartPole inputs. For inputs visited by , the values are 5.9% and 29.2% for MountainCar and 0.6% and 17.1% for CartPole.
W3 / Q3 — Additional verification results We thank the reviewer for raising this point. Indeed, the original paper gave aggregate verified fractions, which could hide lost properties and numerical verifier failures. The inconclusive checks of the original submission, about 8% on MountainCar, were caused by numerical errors of the verifier, such as invalid counterexamples, and not by timeouts. We therefore repeated every check with an exact MILP encoding of the ReLU network, which searches for a counterexample to the property (Section 6.1, Appendix D). We now report results for each property (Appendix F, Figure 7).
For CartPole, all proven properties are preserved up to . For MountainCar, at most one proven property is lost for . For larger , a few proven properties are lost, and others are newly proven.
The per-property results also explain MountainCar's higher verified fraction at large : more properties are newly proven than are lost. This does not imply that the controller has improved. Approximation can change decisions near splitting boundaries, causing some properties to become satisfied while others may no longer hold. We will formalize this discussion in the paper with the following corollary of Lemma 5.3, which establishes when action constraints are guaranteed to remain satisfied.
Action-constraint preservation corollary. If the tree satisfies a given action constraint throughout the property region enlarged by , then satisfies the same constraint on the original region. For axis-aligned trees, the required enlargement is .
The proof follows directly from Lemma 5.3: for every in the original region, there exists an with such that . Since lies in the enlarged region, the network's action satisfies the constraint.
Q4 — Fidelity measurements and Pruning effect Figure 3 reports end-to-end action agreement against , equivalently the original tree . To separate the two steps, we now also compare (1) the pruned tree with , and (2) of the unpruned tree with (Section 6.2, Figure 3).
The separation shows why end-to-end fidelity decreases: for , the pruned tree alone stays close to , while the conversion-only and end-to-end curves nearly coincide. Thus, most observed disagreement comes from the conversion, not from pruning. The same holds on visited states.
We also ran all four policies from the same initial states to separate their closed-loop rewards. Pruning alone leaves the mean reward essentially unchanged for , and the reward of the converted networks stays close to that of . Therefore, the tree-pruning step contributes little to the observed reward change in these tests. Theorem 5.2 guarantees a relation only between and the tree that was converted ( after pruning). The pruning comparison assesses deviations from the original .
Q5 — Leaves summation. Can summing leaf activations favor classes with more leaves and enlarge disagreement? Yes, class imbalance can affect the summed scores near splits, as the original running example illustrates. However, it does not invalidate the guarantee. Lemma 5.3 already covers the class returned after summation. More strongly, Theorem 5.2 shows that outside the -slabs exactly one leaf is active. In that region, having more leaves in another class cannot affect the result. Thus, class imbalance can change a prediction only inside the identified slabs, not arbitrarily far from the relevant splitting hyperplanes.
We use a sum because it keeps the NN at four layers regardless of the number of leaves. A class-wise maximum would avoid accumulating activations from multiple leaves of the same class, but would require up to additional reduction layers. In our measurements, the exact construction of Section 4, which uses this maximum, is a median of 2.1 (MountainCar) and 2.6 (CartPole) times slower than the fixed-depth architecture, and up to 11 times for larger trees (Section 6.3, Figure 4). The empirical trade-off is limited disagreement at : only a small fraction of uniformly sampled states disagree, 1.3% on MountainCar and 0.02% on CartPole (conversion only, Figure 3). These results quantify the trade-off between inference speed and fidelity.
We sincerely thank the reviewer for the detailed and technically insightful review. The comments helped us identify concrete improvements and new theoretical results, and we have revised our paper to address each point. Below, we address each point in turn, together with additional supporting experiments where needed.
To make the results easier to read, we report in a final comment the per-property verification results (Appendix F, Figure 7) as numbers, together with the values of κS for each architecture, which complement Appendix H.
W1 / Q2. We thank the reviewer for this comment. The reported value of 1.2×107 counts every entry of the dense weight matrices. Most of these entries are zero by construction: between Layer 2 and Layer 3, the neuron associated with a leaf ℓ is connected only to the predicates on the root-to-leaf path of ℓ, so the corresponding ∣L∣×E weight matrix is sparse. Such a matrix can be stored in sparse form, for example as a sparse tensor in PyTorch. In the revised version, Figure 3 therefore reports the number of parameters of these sparse matrices, which is substantially smaller: on CartPole, more than 99% of the dense entries are zero.
We also added a direct size comparison with the source NN N, the tree SN, the exactly converted NN N′, and our four-layer approximate NN Nδ′ (Section 6.2, Figure 3; Section 6.3, Figure 4). In median, N has 643 parameters on MountainCar and 226 on CartPole, the tree SN has 269 and 11,873, and Nδ′ of the unpruned tree has 769 and 38,038, which pruning with δ=0.02 reduces to 514 and 29,841 (Figure 3). The comparison addresses the size concern in two ways. First, the exact construction N′ is never smaller than our approximation: N′ has strictly more neurons than Nδ′ for every tree with more than one leaf, and never fewer layers. Its depth grows with the number of leaves, whereas Nδ′ keeps four layers. This is expected because N′ needs additional class-wise maximum layers while Nδ′ uses a sum. Measured on the same trees, the construction of Section 4 has a median of 1.15 (MountainCar) and 1.11 (CartPole) times the nonzero parameters of Nδ′ and 9 and 14 layers, so its main cost is depth rather than parameters: it is a median of 2.1 and 2.6 times slower than Nδ′ (Section 6.3, Figure 4). Second, it also shows the limitation: the converted CartPole NN can still be much larger than N because the preceding exact NN-to-DT step produces trees with many leaves: a median of 1,689 and at most 11,065 over all 100 CartPole controllers, against 55 and 793 on MountainCar (Figure 4). At δ=10−4, pruning leaves these trees almost unchanged (Figure 3). The unpruned approximation has the same size for any δ on a fixed tree, but pruning reduces it.
Comparison with distillation. Training a smaller MLP to imitate the tree can reduce parameter count, but it provides no structural guarantee about which inputs may change label. As a baseline, we trained a dense MLP Nbc to imitate the tree SN by behaviour cloning (Section 6.2, Figure 3). It is as deep as Nδ′, and its hidden layers are at least as wide. In both environments, Nδ′ of the unpruned tree is more faithful to N than Nbc, on uniformly sampled states and on visited states, without any training.
For small δ, the verified fraction of our converted NN also stays at the baseline of N (Section 6.1, Figure 2). The networks differ in size, so this is a comparison of guarantees, not of compression.
Inference latency. We measured latency because size alone does not establish whether an NN is useful for deployment. For every tree, we measured the median time of a forward pass of a single state for Nδ′ and for the exact construction of Section 4 (Section 6.3, Figure 4). The latency of Nδ′ stays nearly constant for small trees, close to 20 µs up to about 100 leaves, whereas the exact construction is a median of 2.1 (MountainCar) and 2.6 (CartPole) times slower, and up to 11 times for larger trees, because its depth grows with the number of leaves. This supports the practical value of avoiding the exact construction's reduction layers in neural inference pipelines.