acceptodds
Under review as a conference paper at ICLR 2027

-Approximate Structural Transformation of Decision Trees into Fixed-Depth Neural Networks

Abstract

Neural networks (NNs) are effective decision-making models, but their decision logic is often difficult to inspect and verify. A large body of research has focused on converting NNs into interpretable models to facilitate their analysis and modification. Decision trees are an attractive representation since they expose their input space partitions and can therefore be used to understand the decisions within each region. However, decision trees can be inconvenient to deploy in standard neural inference pipelines and are not directly compatible with the ecosystem of tools developed for NN verification. A reverse transformation is therefore desirable to move between interpretable and neural models while preserving their behavior. We address this problem by focusing on the transformation from decision trees to NNs. We first discuss a constructive exact transformation from decision trees to rectified linear unit (ReLU) NNs, showing that every decision tree admits an equivalent neural realization, but also that exactness can cause substantial growth in the size of the resulting neural model. We address this issue by introducing a -approximate transformation method that maps a decision tree to a fixed-depth NN while relaxing exact equivalence. Specifically, our approximation guarantees exact agreement of the neural model with the decision tree outside a -dependent neighborhood, thereby confining possible prediction discrepancies to this neighborhood. We evaluate the transformation on neural control policies on two benchmarks from the OpenAI Gym environment. Across policies obtained from multiple NN architectures and independently trained models, we evaluate the fidelity of the converted NN with respect to its source decision tree, closed-loop performance, and preservation of formally verified properties. We further evaluate a combined pruning-and-conversion pipeline, demonstrating a tunable trade-off between policy fidelity and the size of the resulting network. Overall, our method enables a practical workflow in which policies can be analyzed and modified as interpretable decision trees and then deployed as compact NNs.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Neural Networks, Decision Trees, Neural Network Transformation, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_s9tAOpenReview ↗
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 δ\delta-approximate transformation that replaces the class-wise maximum with a sum of leaf activations whose path-constraint violation is below δ\delta. 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 κSδ\kappa_S\delta, where κS\kappa_S 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 δ\delta-approximate agreement is formalized, and the constant κS\kappa_S 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 δ\delta, 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 1.2×1071.2\times10^7 parameters for CartPole at δ=10−4\delta=10^{-4}. 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 xx there exists x′x' within κSδ\kappa_S\delta such that the network and tree agree at x′x'. 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 κS\kappa_S, 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 8%8\% 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 κS\kappa_S for the trees used in the experiments. Without this, the δ\delta-guarantee cannot be interpreted in terms of actual input-space neighborhoods.

  • Please compare parameter counts and inference costs of the δ\delta-approximate network with the exact transformation and with the source tree. In particular, for CartPole at δ=10−4\delta=10^{-4}, what is the tree size, and why is a network with about 1.2×1071.2\times10^7 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 δ\delta 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

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\kappa_S for each architecture, which complement Appendix H.

W1 / Q2. We thank the reviewer for this comment. The reported value of 1.2×1071.2\times10^{7} 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 ℓ\ell is connected only to the predicates on the root-to-leaf path of ℓ\ell, so the corresponding ∣L∣×E|L|\times 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 NN, the tree SNS_N, the exactly converted NN N′N', and our four-layer approximate NN Nδ′N_\delta' (Section 6.2, Figure 3; Section 6.3, Figure 4). In median, NN has 643 parameters on MountainCar and 226 on CartPole, the tree SNS_N has 269 and 11,873, and Nδ′N_\delta' of the unpruned tree has 769 and 38,038, which pruning with δ=0.02\delta = 0.02 reduces to 514 and 29,841 (Figure 3). The comparison addresses the size concern in two ways. First, the exact construction N′N' is never smaller than our approximation: N′N' has strictly more neurons than Nδ′N_\delta' for every tree with more than one leaf, and never fewer layers. Its depth grows with the number of leaves, whereas Nδ′N_\delta' keeps four layers. This is expected because N′N' needs additional class-wise maximum layers while Nδ′N_\delta' 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δ′N_\delta' 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δ′N_\delta' (Section 6.3, Figure 4). Second, it also shows the limitation: the converted CartPole NN can still be much larger than NN 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\delta = 10^{-4}, pruning leaves these trees almost unchanged (Figure 3). The unpruned approximation has the same size for any δ\delta 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 NbcN_{bc} to imitate the tree SNS_N by behaviour cloning (Section 6.2, Figure 3). It is as deep as Nδ′N_\delta', and its hidden layers are at least as wide. In both environments, Nδ′N_\delta' of the unpruned tree is more faithful to NN than NbcN_{bc}, on uniformly sampled states and on visited states, without any training.

For small δ\delta, the verified fraction of our converted NN also stays at the baseline of NN (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δ′N_\delta' and for the exact construction of Section 4 (Section 6.3, Figure 4). The latency of Nδ′N_\delta' 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.

W2 / Q1 — Is κS⋅δ\kappa_S\cdot\delta 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 κS\kappa_S for every tree by enumerating linearly independent predicate subsets along root-to-leaf paths. The median κS\kappa_S is 2.3×1032.3\times10^3 on MountainCar and 6.6×1056.6\times10^5 on CartPole, and the largest is 3.37×1053.37\times10^5 and 8.25×1058.25\times10^5, so the median κSδ\kappa_S\delta at δ=0.01\delta = 0.01 is 23 and 6.6×1036.6\times10^3. We also measured, for sampled disagreement points xx, the distance d(x)d(x) 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 10510^5 uniformly sampled inputs and the inputs visited in 50 episodes of NN.

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 κS⋅δ\kappa_S\cdot\delta, by four to six orders of magnitude, and they grow roughly linearly with δ\delta: the measured distance is at most 20.9δ20.9\delta on MountainCar and 9.5δ9.5\delta on CartPole, with a median of about 0.1δ0.1\delta. The reason is that κS\kappa_S 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, κS⋅δ\kappa_S\cdot\delta can exceed the input domain even though the measured deviations remain relatively small. For axis-aligned trees, κS=1\kappa_S=1, and the bound is δ\delta.

A complementary disagreement guarantee. After observing the gap between κSδ\kappa_S\delta 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 κS\kappa_S.

Intuitively, in Nδ′N_\delta', the leaf reached by the tree always has activation δ\delta, because its path violation is zero. Any other leaf can only be active if its path violation is smaller than δ\delta. Since its path must diverge from the path followed by xx at some split, this can happen only if xx lies within distance δ\delta 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 uu as p^u(x)=pu(x)/∥w∥2\hat p_u(x)=p_u(x)/\Vert w\Vert_2.

If ∣p^u(x)∣≥δ|\hat p_u(x)| \ge \delta at every split on the path followed by xx, then Nδ′(x)N_\delta'(x) and S(x)S(x) predict the same class. Equivalently, disagreement can occur only if xx lies within distance δ\delta 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 κS\kappa_S 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 κS\kappa_S is small, e.g., κS=1\kappa_S=1 for axis-aligned trees, where the distance is at most δ\delta.
  • Theorem 5.2 identifies where disagreements can occur, independently of κS\kappa_S. It is particularly informative when κS\kappa_S is large, since disagreements are confined to δ\delta-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 δ\delta of a splitting hyperplane on its path, but not that every point inside these slabs disagrees. In Figure 1b, at δ=0.002\delta=0.002, x2=0.004x_2=0.004 lies outside the relevant slabs and agrees, whereas x2=0.0012x_2=0.0012 is near the split at 0.0010.001 and disagrees. Theorem 5.2 thus gives an informative guarantee when κSδ\kappa_S\delta is too conservative.

We also checked the theorem empirically: on uniformly sampled states, no disagreement occurred outside the δ\delta-slabs of any tree, for δ∈0.001,0.01,0.1\delta \in \\{0.001, 0.01, 0.1 \\}.

Measured frequency. The frequency of disagreement is the conversion-only curve of Figure 3, which compares Nδ′N_\delta' of the unpruned tree with NN. At δ=0.001\delta = 0.001, they disagree on less than 1% of the inputs in both environments. At δ=0.01\delta= 0.01 and 0.10.1, 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 NN, 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 δ=0.02\delta = 0.02. For MountainCar, at most one proven property is lost for δ≤0.01\delta \le 0.01. For larger δ\delta, a few proven properties are lost, and others are newly proven.

The per-property results also explain MountainCar's higher verified fraction at large δ\delta: 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 κSδ\kappa_S\delta, then Nδ′N_\delta' satisfies the same constraint on the original region. For axis-aligned trees, the required enlargement is δ\delta.

The proof follows directly from Lemma 5.3: for every xx in the original region, there exists an x′x' with ∥x′−x∥2<κSδ\Vert x'-x\Vert_2<\kappa_S\delta such that fNδ′(x)=fS(x′)f_{N_\delta'}(x)=f_S(x'). Since x′x' 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 NN, equivalently the original tree SNS_N. To separate the two steps, we now also compare (1) the pruned tree SδS_\delta with NN, and (2) Nδ′N_\delta' of the unpruned tree SNS_N with NN (Section 6.2, Figure 3).

The separation shows why end-to-end fidelity decreases: for δ≤0.02\delta \le 0.02, the pruned tree alone stays close to NN, 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 δ≤0.02\delta \leq 0.02, and the reward of the converted networks stays close to that of NN. Therefore, the tree-pruning step contributes little to the observed reward change in these tests. Theorem 5.2 guarantees a relation only between Nδ′N_\delta' and the tree that was converted (SδS_\delta after pruning). The pruning comparison assesses deviations from the original NN.

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 δ\delta-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 ⌈log⁡2∣L∣⌉\lceil \log_2 |L| \rceil 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 δ=0.01\delta=0.01: 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.

Reviewer_R1NROpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes a methodology for converting decision trees (DTs) into neural networks. It also introduces a strategy to limit tree size using a δ-approximate transformation method. The proposed strategies are evaluated on two benchmarks from the OpenAI Gym environment.

Critical strengths
  • The paper is easy to read, and the notation is clearly explained.
  • The authors clearly state their research question: “How can a decision tree be systematically converted back into a neural network while controlling the behavioral distortion introduced by the conversion?”
  • The authors address an important problem: the complexity of decision trees obtained from neural networks.
Critical weaknesses
  • Contribution and motivation: I believe the authors should better explain the motivation behind this work. If the decision trees (DTs) exactly reproduce the behavior of the original neural network (NN), why can the original NN not be used after the analysis? What is the purpose of constructing a new neural network (NN′) that exhibits the same behavior as the original NN?

  • Experiments and results: The experimental results need some clarification and details. How does the proposed δ-approximate transformation method compare with existing neural network pruning strategies in terms of the number of neurons and similarity to the original network? The benchmarks used in the paper also appear relatively simple. How would the proposed methodology perform when applied to more complex models trained on more challenging datasets?

Questions for authors

I have included questions above.

6 comments

We thank the reviewer for the thoughtful review and for the opportunity to motivate our contribution. The points raised have helped us identify aspects that can be clarified more explicitly, and we have revised our paper to address each point. In the revision, Theorem 5.2 is a new result that localizes where disagreements can occur, while the distance bound of the original Theorem 5.2 is Lemma 5.3, and the size bound of the original Lemma 5.3 is Lemma 5.4.

To make the results easier to read, we report in a final comment the numerical values of the size comparison with the original network (Figure 3) and of the comparison with magnitude pruning (Appendix G, Figure 8), together with additional results of the repair experiment for different margins, which complement Appendix J.

W1. We thank the reviewer for this question, as it helps clarify the practical relevance of the paper's contribution. We agree that if the original network NN has not changed, it is better to deploy NN directly. The reverse transformation becomes relevant when the desired policy is not NN anymore. In particular, examples of such occurrences are:

  1. The tree has been modified, for example, repaired (Appendix J) or restricted so that unsafe actions are removed.
  2. The tree has been pruned. The pruned tree SδS_\delta used in RQ2 (Section 6.2) has no corresponding neural network of its own.
  3. The policy originates as a tree, for example, a learned decision tree (Appendix I), a policy extracted with VIPER, or a set of expert rules.

More generally, the transformation allows a policy to move between the two representations: it can be inspected and refined as a decision tree, then deployed and verified as a neural network. Theorem 5.2 characterizes conversion-induced deviations relative to the tree actually converted, not necessarily relative to the original network.

As a concrete supporting example for case 1, we added an experiment that runs this workflow end to end (Appendix J). We considered the 40 MountainCar controllers with architectures (16,16) and (16,16,16). Of these, 37 violate local action consistency and 18 the absence of the left action near the goal, giving 55 controller–property pairs in total. For each case, we tested three values of δ\delta (0.001, 0.01, 0.1). For each instance, we:

  • Repair the tree by splitting leaves that predict forbidden actions and overlap with the property's input region enlarged by δ\delta, then assign allowed actions to the affected regions.
  • Convert the repaired tree back into a neural network.
  • Formally verify the property on both models, using an exact leaf-by-leaf check for the repaired tree and an exact MILP for the converted network.

Every repaired tree satisfies its property, and every converted network is formally verified to satisfy it, at every δ\delta. The repaired networks also retain much of the original policy's behavior: outside the property region, they agree with NN on almost all visited states at δ=0.001\delta=0.001 and on most of them at δ=0.01\delta=0.01. This matters because the objective is to correct the unsafe behavior without unnecessarily changing the rest of the policy. Their mean reward stays the same as that of NN at small δ\delta, and they are slightly faster at inference than NN. The results are consistent with Theorem 5.2, which bounds conversion-induced deviations relative to the edited tree, but does not guarantee property preservation. The properties of the converted networks are established by exact MILP verification. This experiment demonstrates the benefit of the proposed workflow: a policy can be repaired as a decision tree and converted into a neural network whose repaired properties can be formally verified.

W2. We thank the reviewer for pointing this out. We added three comparisons to answer these separate points.

Size and similarity to NN. RQ1 already measures whether properties proved for NN remain proved after conversion without pruning. RQ2 measures action agreement with NN after pruning and conversion. The original evaluations, however, did not compare the size of the original network NN with that of the converted NN, so we added a size comparison with NN to the revised paper (Section 6.2, Figure 3). We count the parameters of the sparse weight matrices, since Layer 3 is sparse: a leaf connects only to predicates on its path. In terms of neurons, NN has a median of 64 hidden neurons on MountainCar and 32 on CartPole, against 134 and 3,221 for Nδ′N_\delta' of the unpruned tree and 96 and 2,790 after pruning with δ=0.02\delta = 0.02. In terms of parameters, NN has a median of 643 parameters on MountainCar and 226 on CartPole, against 769 and 38,038 for Nδ′N_\delta' of the unpruned tree and 514 and 29,841 after pruning with δ=0.02\delta = 0.02 (Figure 3).

What the comparison shows: On MountainCar, the converted NNs have fewer parameters than NN from δ\delta = 0.01 on, at the reward of NN up to δ\delta = 0.02. CartPole's NNs remain much larger than NN (by one to two orders of magnitude), although action agreement stays close to 100% for δ≤0.02\delta \le 0.02. The reason is that the exact NN-to-DT step produces much larger CartPole trees, with a median of 1,689 leaves and at most 11,065 (Figure 4). Our NN has a number of neurons linear in tree size (Lemma 5.4).

Comparison with NN pruning. For completeness, we also compared against global magnitude pruning, a standard NN compression method that removes weights with the smallest absolute values across all layers of the original network NN. Unlike our method, it reduces the number of weights directly, without converting NN into a tree. We evaluated it on MountainCar at 50% and 90% sparsity, where sparsity is the fraction of weights removed, with a fine-tuning step after pruning (Appendix G, Figure 8). It removes individual weights and leaves the layer widths of NN unchanged, with a median of 64 hidden neurons, whereas our pipeline has a median of 63 hidden neurons at δ=0.05\delta = 0.05 and 19 at δ=0.1\delta = 0.1.

At 90% sparsity, our pipeline reaches a comparable size and agreement with NN without fine-tuning: at δ=0.1\delta = 0.1, it has a median of 73 parameters and agrees with NN on 67.6% of uniformly sampled and 61.7% of visited inputs, against 110 parameters, 68.0% and 64.6% for magnitude pruning. At 50% sparsity, magnitude pruning is more faithful than our pipeline at a similar size: 94.9% and 91.4% at 347 parameters, against 85.1% and 76.9% at 306 parameters for δ=0.05\delta = 0.05.

Agreement, however, does not show whether verified properties are kept. We therefore also verified the fine-tuned magnitude-pruned networks with the exact MILP of Section 6.1. Of the 69 properties proven on the 100 MountainCar controllers NN, the pruned networks no longer prove 2 at 50% sparsity, both inconclusive within the 600 s time limit, and 19 at 90% sparsity, 16 of them with a counterexample and 3 inconclusive. At a similar size, our pipeline keeps fewer of them: 61 at δ=0.05\delta = 0.05 (306 parameters) against 67 at 50% sparsity (347 parameters), and 46 at δ=0.1\delta = 0.1 (73 parameters) against 50 at 90% sparsity (110 parameters), because pruning the tree changes its decisions with respect to NN. Our approach is therefore not a better way to compress NN. Without pruning, Nδ′N_\delta' at δ=10−4\delta = 10^{-4} preserves all 69 (Section 6.1, Figure 2), but it is larger than NN (Appendix G).

Instead, our objective is to construct a neural representation of a given decision tree, with a formal bound on where its predictions may differ from the tree (Theorem 5.2), which in practice keeps the verified properties of NN at small δ\delta. A network pruned by magnitude has no tree behind it, so it cannot be used to deploy a tree that was edited or repaired (W1).

More complex tasks. The main scalability limitation of the complete workflow comes from exact NN-to-DT transformation, which must enumerate regions of the original network NN. In contrast, our DT-to-NN transformation accepts any decision tree with affine splits and produces a network with a number of neurons linear in the tree size. To evaluate this transformation independently of the extraction step, we conducted additional experiments by adding to the benchmark suite four CART datasets (Wine, Breast Cancer Wisconsin, Digits, and a synthetic task with 100 features), for several tree sizes (5 to 6,911 leaves) and three seeds each (Appendix I, Figure 10). These experiments test higher-dimensional inputs (up to 100 dimensions) and trees with up to 6,911 leaves, extending the evaluation beyond MountainCar and CartPole.

We measure the fidelity of Nδ′N_\delta' to its tree on test points perturbed with Gaussian noise. For small δ\delta, Nδ′N_\delta' reproduces its tree on every dataset (100% fidelity for δ≤10−3\delta \le 10^{-3}, at least 99.9% at δ=10−2\delta = 10^{-2}), and its fidelity stays high at δ=0.1\delta=0.1 even with 100 features: 100%, 99.5%, 99.0% and 97.9% on average with 13, 30, 64 and 100 features. We have included this discussion in the revised paper (Appendix I).

We hope that our responses have shed more light on the scope of the contribution. We have revised the paper accordingly, incorporating the additional discussions described above. Should any point remain unclear, we would be happy to provide further clarification.

Supplementary tables. For convenience, we report here in numerical form some of the results that the revised paper shows as figures.

Repair in the tree (W1, Appendix J, Figure 11). MountainCar controllers with architectures (16,16) and (16,16,16): 37 violate local action consistency and 18 violate the absence of the left action near the goal. The property region is enlarged by a margin mm before the repair. The table reports how many converted networks Nδ′N_\delta' are formally verified (exact MILP), and, for m=δm = \delta, the fidelity to NN on visited states outside the property region and the mean reward of Nδ′N_\delta' (reward of NN: −188.0 and −186.1). The repaired tree satisfies the property in every case with m>0m > 0.

Propertyδ\deltaverified, m=0m = 0m=δ/2m = \delta/2m=δm = \deltam=2δm = 2\deltafidelity outside (m=δm = \delta)reward (m=δm = \delta)
local action consistency0.0010/371/3737/3737/3799.5%−188.7
local action consistency0.011/376/3737/3737/3793.7%−189.2
local action consistency0.13/3729/3737/3737/3763.9%−194.1
no left near goal0.0010/180/1818/1818/1899.3%−186.1
no left near goal0.010/183/1818/1818/1893.3%−187.0
no left near goal0.10/1810/1818/1818/1869.5%−191.8

Verifying the repaired tree alone is therefore not sufficient: without a margin, almost no converted network satisfies the property, whereas with m=δm = \delta all of them are formally verified.

Size compared with NN (W2, Section 6.2, Figure 3). Medians of hidden neurons / parameters (sparse matrices for Nδ′N_\delta').

EnvNNNδ′N_\delta' of the unpruned treeNδ′N_\delta' after pruning, δ=0.02\delta = 0.02
MountainCar64 / 643134 / 76996 / 514
CartPole32 / 2263,221 / 38,0382,790 / 29,841

Comparison with magnitude pruning (W2, Appendix G, Figure 8). MountainCar, median parameters and mean fidelity to NN on uniform / on-policy states. Magnitude pruning is followed by fine-tuning, and our pipeline is not.

Modelparametersfidelity uniform / on-policy
NN643100% / 100%
magnitude pruning, 50%34794.9% / 91.4%
our pipeline, δ=0.05\delta = 0.0530685.1% / 76.9%
magnitude pruning, 90%11068.0% / 64.6%
our pipeline, δ=0.1\delta = 0.17367.6% / 61.7%
Reviewer_ferTOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Summary: The paper proposes a training-free approach for converting a decision tree into a neural network, including an exact conversion and a fixed-depth approximate conversion.

Critical strengths

Strengths:

  • The paper is well written containng rigourus mathatical statements.
  • The paper provides an exact conversion of decision trees to neural networks as well as an approximate conversion to fixed-depth neural networks.
Critical weaknesses

Weaknesses:

  • Limited evaluation with: (i) small source neural networks; (ii) no exact-construction comparison; (iii) no pruning-vs-approximation ablation (RQ2); and (iv) only 2–4 input dimensions.
  • The conversion creates very large neural networks (e.g. stated in l.426 for Cartpole 1.2*10^7 parameters) whereas the initial source networks have a few hundred parameters.
  • Lemma 5.3 has no proof.
Questions for authors

Questions:

  1. What is the practical advantage of the approach over the deployment of the decision tree? The converted neural network is signifiacntly larger.
  2. How does the pruning and delta (RQ2) compare to the source network?
  3. How exactly is pruning done (l.413)?
  4. Could more aggressive pruning be used to overcome the size blowup of the constructed neural network?
13 comments

We sincerely thank the reviewer for carefully reading our paper and for the opportunity to clarify our contribution. The points raised helped us strengthen both the experimental evaluation and the presentation. We have revised our paper to address each point, as described below, with additional experimental results where relevant. In the revision, Theorem 5.2 is a new result that localizes where disagreements can occur, while the distance bound of the original Theorem 5.2 is Lemma 5.3, and the size bound of the original Lemma 5.3 is Lemma 5.4.

To make the results easier to read, we report in a final comment the numerical values of the comparison between the exact and the approximate network (Section 6.3, Figure 4) and of the fidelity on the higher-dimensional benchmarks (Appendix I, Figure 10).

W1 (i, iv). We thank the reviewer for this observation. Both limitations originate from the preceding NN-to-DT transformation, not from the DT-to-NN transformation proposed here. The exact NN-to-DT step must enumerate the linear regions of the source network NN, which restricts both the size and the input dimension of the networks to which it can be applied. In contrast, our transformation accepts any decision tree with affine predicates, and the number of its neurons grows linearly with the tree size (Lemma 5.4). To demonstrate this, we added experiments with up to 100 input dimensions (Appendix I, Figure 10). They start directly from a decision tree (CART trees trained on the Wine, Breast Cancer Wisconsin, and Digits datasets and on a synthetic task with 100 features), for several tree sizes (5 to 6,911 leaves) and three seeds each. The trees of the case studies are also large: the CartPole trees have up to 11,065 leaves, and Section 6.3 converts every one of them (Figure 4).

We measure the fidelity of Nδ′N_\delta' to its tree on test points perturbed with Gaussian noise. For small δ\delta, Nδ′N_\delta' reproduces its tree on every dataset (100% fidelity for δ≤10−3\delta \le 10^{-3}, at least 99.9% at δ=10−2\delta = 10^{-2}), and its fidelity stays high at δ=0.1\delta = 0.1 even with 100 features: 100%, 99.5%, 99.0% and 97.9% on average with 13, 30, 64 and 100 features. For the axis-aligned CART trees, κS=1\kappa_S = 1, and Lemma 5.3 bounds the disagreement radius by δ\delta. These results show that the DT-to-NN transformation handles larger trees and higher-dimensional inputs while closely preserving tree predictions.

W1 (ii). We thank the reviewer for suggesting this comparison. Although the exact construction has analytically determined size and behavior, reporting the measured comparison makes the depth and deployment trade-off clearer. The exact construction of Section 4 has the same predicate layer as Nδ′N_\delta', a leaf-score layer of the same size, and up to ⌈log⁡2∣L∣⌉\lceil \log_2 |L| \rceil additional layers that compute the class-wise maximum. It reproduces the tree, and therefore NN, away from splitting boundaries. We built it for every controller and measured its size and latency (Section 6.3, Figure 4). It has a median of 1.15 (MountainCar) and 1.11 (CartPole) times the nonzero parameters of Nδ′N_\delta', and a median of 9 layers on MountainCar and 14 on CartPole, against 4 for Nδ′N_\delta'. Its additional depth affects inference: its latency at batch size 1 is a median of 2.1 (MountainCar) and 2.6 (CartPole) times that of Nδ′N_\delta', and up to 11 times for large trees. The main advantage of Nδ′N_\delta' over the exact construction is therefore its fixed depth (Section 6.3).

W1 (iii). We thank the reviewer for this suggestion and have added the ablation to the experimental section (Section 6.2, Figure 3). For a fixed tree, δ\delta does not affect the size of Nδ′N_\delta' (Lemma 5.4). The size reduction observed in Figure 3 is therefore due to pruning alone. The ablation compares, for each δ\delta, the network obtained from the unpruned tree with the network obtained from the pruned tree.

Pruning thus removes up to about a third of the parameters for δ≤0.02\delta \le 0.02, while end-to-end fidelity to NN stays almost the same as when converting the unpruned tree: most of the fidelity loss comes from the conversion, not from pruning. Pruning alone also leaves the closed-loop reward essentially unchanged. The revised paper also states that Theorem 5.2 holds for whichever tree is converted, i.e., for SδS_\delta after pruning.

W2. We thank the reviewer for raising this point. The reported value of 1.2×1071.2\times10^{7} 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 ℓ\ell is connected only to the predicates on the root-to-leaf path of ℓ\ell, so the corresponding ∣L∣×E|L|\times 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. The count of Figure 3 describes the sparse parameter structure. Actual sparse storage also includes indices and metadata, while implementations requiring dense weights incur the dense count.

W3. We thank the reviewer for pointing out this missing point. Lemma 5.4 follows directly from the construction by counting: Layer 2 contains two neurons per distinct normalized predicate, Layer 3 contains one neuron per leaf, and Layer 4 contains one neuron per class. In our implementation, internal nodes whose normalized predicates coincide up to sign share the same pair of Layer-2 neurons. The network therefore has four layers and 2P+∣L∣+c2P + |L| + c neurons, where P≤∣I∣P \le |I| is the number of distinct predicates. We added this argument to Appendix B, together with the count 2P+∣L∣+c2P + |L| + c, of which the bound 2∣I∣+∣L∣+c2|I| + |L| + c of Lemma 5.4 is the worst case.

Q1. If the original network remains the desired policy, it can indeed be deployed directly. The reverse transformation becomes useful when the policy is modified in its tree representation. The intended workflow starts from a trained neural network whose parameters are available. The network is first converted into a decision tree, which can be inspected and modified, for instance by pruning or by editing thresholds and leaf labels. Our method then maps the modified tree back to a neural network with a formal guarantee relative to the modified tree (Theorem 5.2). A policy can thus be refined in its tree representation and deployed and verified in its network representation. We demonstrate this workflow end to end in the revised paper (Appendix J): properties violated by the source network are repaired in the tree, and the repaired tree is converted into a network that keeps the policy of NN away from the repaired region. Deploying the tree directly remains a valid option on platforms that support it. Furthermore, when measured in the parameters of the sparse matrices (see our response to W2), the converted network is considerably smaller than Figure 3 suggested, which makes deployment as a neural network more feasible. The inference measurements of Section 6.3 (Figure 4) further characterize deployment cost.

Q2. The fidelity reported in Figure 3 is measured with respect to the source network NN. We have added a size comparison with NN, measured in parameters, to the revised paper (Figure 3).

For MountainCar, Nδ′N_\delta' has fewer parameters than NN from δ=0.01\delta = 0.01 on, at the reward of NN up to δ=0.02\delta = 0.02. For CartPole, the network remains one to two orders of magnitude larger than NN, because the exact NN-to-DT step produces large trees, and the neuron count of Nδ′N_\delta' is linear in the tree size. The parameter count also depends on total path lengths. Thus, the complete workflow can substantially increase network size when exact extraction produces large trees. Our DT-to-NN transformation is not intended to compress the original network, but to provide a fixed-depth neural representation of a given tree.

Q3. Pruning is applied directly while the exact NN-to-DT procedure builds the tree, avoiding the expansion of branches that would later be removed. This is done for computational efficiency, and the result is the same as first constructing the complete tree and then applying the same pruning rules in a separate pass.

The tree is pruned by removing the branches whose region contains no state xx with ∣pu(x)∣≥δ|p^u(x)| \ge \delta for every split uu on its path, where pu(x)=w⊤x+bp^u(x) = w^\top x + b is the pre-activation of the hidden neuron tested at uu. This is checked with an LP over the input box. If only one child passes, the node is replaced by that child's subtree, so inputs in the removed region are routed to the sibling. If neither child passes, the node is marked infeasible, and its parent treats it as an infeasible child.

A final bottom-up pass merges sibling leaves that predict the same class, and δ=0\delta = 0 yields the unpruned tree SNS_N. The pruned tree SδS_\delta is then converted into Nδ′N_\delta' with the same numerical value of δ\delta.

Q4. Stronger pruning is possible and may reduce the size of the network further. Examples include pruning with a larger δ\delta than the one used for the conversion, depth limits, or cost-complexity pruning. Our transformation applies unchanged to any such tree, and Theorem 5.2 bounds the deviation of Nδ′N_\delta' from the tree that is actually converted. However, the theorem does not bound the deviation of the pruned tree from SNS_N, and hence from NN. That deviation can compound the deviation introduced by conversion and must be measured separately, as in the ablation of W1 (iii). In the paper, we use the same numerical δ\delta for the raw-predicate pruning test and the normalized conversion, providing a simple one-parameter empirical trade-off. Since their geometric scales differ by ∥w∥2\Vert w\Vert_2, this choice does not guarantee that the regions affected by the two steps have comparable Euclidean widths. Empirically, for δ<0.02\delta < 0.02, the pruned tree SδS_\delta itself stays close to NN before conversion, and after conversion, pruning lowers end-to-end fidelity only slightly (W1 (iii)). Pruning also leaves the closed-loop reward essentially unchanged (pruning only, Figure 3). Therefore, stronger pruning gives a different trade-off between size and fidelity.

We hope that our responses address the reviewer’s concerns. We thank the reviewer again for their consideration, and we would be happy to discuss any additional points further.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Overview of the revision: new experiments and where they address each review

We thank the reviewers for their constructive feedback, and the area chair and program chairs for managing the review process. In response to the reviews, we added the following experiments to the paper. All changes are marked in blue in the revised version.

  1. Sparse parameter counts and comparison with the source network (Section 6.2, Figure 3). Figure 3 now reports the parameters of the sparse weight matrices of Nδ′N'_\delta and marks the size of the source network NN. This addresses ferT W2 and Q2, s9tA W1/Q2, and R1NR W2.
  2. Ablation of pruning and conversion (Section 6.2, Figure 3). We evaluate the pruned tree alone and the network of the unpruned tree, which separates the effect of the two steps on fidelity, reward, and size. This addresses ferT W1 (iii) and Q4, and s9tA Q4.
  3. Behaviour-cloning baseline (Section 6.2, Figure 3). An MLP trained to imitate the tree is less faithful to NN than the converted network and has more parameters. This addresses s9tA W1.
  4. Exact versus approximate transformation (new research question RQ3, Section 6.3, Figure 4). For every tree, we compare the size, depth, and inference latency of the exact network and of Nδ′N'_\delta. This addresses ferT W1 (ii) and s9tA W1/Q2.
  5. Per-property verification results (Section 6.1, Appendix F, Figure 7). We now report the verified fraction for each property separately, in addition to the results per architecture. This addresses s9tA W3/Q3.
  6. Magnitude-pruning baseline (Appendix G, Figure 8). We compare the pruning-and-conversion pipeline with magnitude pruning of NN on MountainCar. This addresses R1NR W2.
  7. κS\kappa_S and disagreement radius (Appendix H, Figure 9). We compute κS\kappa_S of every tree and measure the distance at which disagreements occur, which is four to six orders of magnitude below κSδ\kappa_S\delta. This analysis led us to restate Theorem 5.2 in a form that does not depend on κS\kappa_S; the κSδ\kappa_S\delta bound is now Lemma 5.3. This addresses s9tA W2/Q1.
  8. Higher-dimensional inputs (Appendix I, Figure 10). We convert CART trees trained on the Wine, Breast Cancer Wisconsin, and Digits datasets and on a synthetic task with 100 features. This addresses ferT W1 (i, iv) and R1NR W2.
  9. Repair in the tree (Appendix J, Figure 11). We repair properties violated by NN in the tree and convert the repaired tree back into a network. This addresses R1NR W1 and ferT Q1.

The remaining points are answered by clarifications in the individual responses.

AuthorsOpenReview ↗

Revision Update

Revision update: Exact construction from Section 4 (Figure 4). Following the discussion with the reviewers, we have updated Section 6.3 and Figure 4 of the revised paper. Previously, Figure 4 reported our implementation of an alternative exact construction based on pairwise minima over each leaf's constraints. The updated figure now evaluates the Section 4 construction directly in both environments. Both networks are built from the same unpruned tree SNS_N, so this comparison does not use any pruning, which would further reduce the size of Nδ′N_\delta' (Section 6.2).

Nδ′N_\delta' is smaller, shallower, and faster than the exact network for every tree measured. Its depth is fixed to 4 layers, while the exact network's depth grows with tree size (median 9 and 14 layers for MountainCar and CartPole, respectively). In our measurements, the exact network has a median batch-size-1 inference latency of 2.1× and 2.6× that of Nδ′N_\delta', reaching up to 11× for large trees. It also has more nonzero parameters for every tree, by a median of 15% (MountainCar) and 11% (CartPole). These results are independent of δ\delta, since the architecture of Nδ′N_\delta' remains unchanged (Lemma 5.4).

Nevertheless, these experiments lead to the same qualitative conclusion. They show that Nδ′N_\delta' is shallower, smaller, and faster than the exact construction, although gaps in size and latency are smaller than previously reported. We have updated our responses accordingly with the new numbers.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.