acceptodds
Under review as a conference paper at ICLR 2027

Hinging Hyperplanes Tree: Transforming ReLU Neural Networks into Equivalent Decision Trees

Abstract

ReLU neural networks define continuous piecewise-affine functions, but this function-level structure is represented implicitly through neuron activations. We introduce the Hinging Hyperplanes Tree (HHT), which converts a fixed ReLU network into a tree of affine comparisons with affine output rules at its leaves. HHT is constructed from locally extracted affine functions and refined through leaf-wise linear-programming containment checks. We prove finite convergence of the sample-level construction and show that, once all leaves are certified, the resulting HHT is functionally equivalent to the source network over the prescribed bounded domain. Unlike a forward pass, which reveals the affine rule only at a queried input, a certified HHT provides a reusable polyhedral representation of the network's piecewise-affine function. Experiments demonstrate exact reconstruction on the studied ReLU MLPs and characterize the structural and computational trade-offs relative to existing network-to-tree representations.

Primary area:
interpretability and explainable AI
Keywords:
hinging hyperplanes tree, ReLU networks, affine functions

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_RTkzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors consider the problem of identifying of ReLU networks via tree structures. Given ReLU networks split the input space into linear regions (not necessarily convex, although the activation regions are) there are several questions regarding the complexity of this structure. I found the idea to construct efficient tree compositions based on the network an open problem as even the complexity of the trees given by recent algorithms varies greatly. These methods, at least in theory, may give us further insights how complex is the actual network and in the future they may be applied not just to analyse the network but also to construct novel network structures with higher generalization ability. Early results, as in the first period of generalization theory, focused on the capacity of the deep, feedforward ReLU networks via counting the number of regions. Given estimating the volume of a convex body is typically unfeasible in practice, see e.g. Lovász, L.; Vempala, S. Simulated annealing in convex bodies and an O*(n4) volume algorithm. J. Comput. Syst. Sci. 2006, 72, 392–417, estimating the distribution of the linear regions is also a hard task.

The proposed algorithm builds a tree (the hinging hyperplanes tree) structure with utilizing the regions arising in the input space with two novel steps in comparison to the existing tree building algorithms for ReLU nets. First, the tree nodes and leaves are based on the actual affine function not the activation regions. Second, the method tests via linear programming the existing tree structure and provides a witness to expand the tree. I found these reasonable, although by the first one it is not clear how much we gain in the complexity of the tree. As it is stated in the paper, the idea of building the tree based on a finite sample is not novel, however I found the LP based certification an interesting take on the problem.

I have found the paper consistent and mathematically sound. The main contribution (the HHT construction and the algorithm to build a HHT) relies on two theorems:

  1. Theorem 1: the theorem proves that under the reasonable assumptions about the fixed finite sample set the HHT building algorithm will stop at finite steps. I found the theorem to be correct.
  2. Theorem 2: this theorem that HHT in the bounded constrained domain is equivalent to the original ReLU network. I have found this theorem to be correct too. The leaf verification/resampling argument seems to be correct too.

A more detailed comparison to the cited Xu et al., Error-free .... , TAC, 2025 paper would clarify the novelty claims. Outside of this, I have found the presented related work sufficient and the comparison to other tree based methods regarding ReLU networks is clear.

The above mentioned weaknesses limit the scope and the novelty of the paper evn though the paper is addressing the ReLU net to tree problem with some novel ideas.

Minor notes:

  1. CROWN-IBP mentioned in the main text without any reference or description. It is introduced in the appendix.
  2. In equations 1-2 and Assumption 2 the lp(x)l_p(x) is referenced in various forms thus harder to read.
  3. Similarly the nonterminal and the leaf nodes are referred with different styled D-s and T-s (e.g. line 165).
Critical strengths
  1. The proposed hinging hyperplane tree and its building algorithm are presented well, although some parts are left for the appendix. I found that part novel.
  2. I can confirm the code found in the supplementary material is producing a comparison between RENTT and HHT with similar results as in the paper (the values are for (10,10) in Table 1).
Critical weaknesses
  1. The provided theorem proves finite step convergence in case of fixed finite sample set, although the main imo innovation in the paper, the verification may be leading to a significantly longer loop of HHT building/resampling cycles and I am not sure how the witnesses can be ensured to satisfy assumptions 1 and 2.
  2. The proposed tree structure and the algorithm provide functional equivalence under the bounded domain which can be quite limited in my opinion.
  3. The authors admit that the proposed HHT would be unfeasible on large dimensional data and large wide and deep networks. This limitation concerns me even more than the previous one as imo the final purpose of these ReLU tree constructions should be to provide information to either measure the complexity of the original network or compress/reconstruct or even expand the network given the tree.
  4. Another limitation of the scope imo is ReLU as a majority of current MLP subnetworks utilize GeLU or some alteration of ReLU however I found the problem on its own interesting.
  5. The presented tree algorithm seems to be producing, at least in comparison to other methods wider trees, though the depth is occasionally significantly lower. Based on the provided tables and the code the algorithm complexity is significantly higher for larger networks.
Questions for authors
  1. It is not clear what will happen outside the bounded domain? Non perturbation based augmentation, e.g. flipping mirroring or even generative input, is prawn to be difficult to handle with knowledge solely based on the original inputs affine region.
  2. Even though the provided algorithm assume fixed ff, relu mlps, I am interested in how the structure can handle slight changes in the parameter of the network?
  3. The authors, among others, provide the depth and number of leaves of the trees. Given these it is difficult to estimate the exact complexity difference between the tree constructions. Please provide a more detailed comparison.
4 comments

We sincerely thank the reviewer for the careful reading of our manuscript and for the constructive comments on the HHT construction, its theoretical guarantees, and its computational characteristics. We are particularly encouraged that the reviewer finds the HHT construction and the LP-based certification approach interesting, and that the mathematical arguments in Theorems 1 and 2 are considered sound.

We address the concerns and questions point by point below.

1. Witness-driven refinement, convergence, and the assumptions on resampled points

We thank the reviewer for raising these questions. The required refinement depends on the initial samples and the resulting tree partition. A representative initial sample set can reduce subsequent resampling, and no resampling is needed if the initial tree passes all containment checks. Theorem 1 bounds each fixed-sample construction by $ N-1 $ splits; we currently do not have a general bound on the number of verification–resampling–reconstruction rounds.

When containment fails, we generate points within the affected leaf beyond the last intersection with the verified compatible-region union. If a newly discovered activation pattern has the same affine function as the leaf, its region is added to the containment test; otherwise, the new affine information is used to refine the leaf.

For Assumption 1, boundary candidates can be supplemented with nearby relative-interior representatives, with their activation patterns and affine functions recomputed. For Assumption 2, we have explicitly incorporated the ordering checks and segment-based resampling procedure of Xu et al. (TAC 2025). Violated ordering relations trigger additional network queries along the corresponding segments, revealing further affine pieces and enlarging the sampled function pool. Reconstruction proceeds with an enlarged batch satisfying the local affine-consistency requirement of Theorem 1. We have made explicit how the ordering conditions and the local sampling conditions establish the affine consistency required by Assumption 2.

Once all leaves pass containment verification, Theorem 2 establishes functional equivalence throughout $ \Omega $.

2. Relationship to Xu et al. (TAC 2025) and the novelty of HHT

Xu et al. (2025) and HHT share a sample-based foundation that uses local affine functions. Their work constructs disjunctive max–min and conjunctive min–max lattice expressions for explicit MPC, whereas HHT constructs an affine-comparison tree for a fixed ReLU network. Each HHT prediction follows a single root-to-leaf path, and the accumulated comparisons define an explicit leaf cell with an affine output rule.

This explicit geometry is central to HHT: the leaf cells support containment-based equivalence certification and can subsequently be reused for constrained output-range queries through leaf-wise linear programs. HHT therefore contributes a specific tree-construction procedure and a geometric certification framework, together with a reusable polyhedral representation.

The distinction concerns representation, construction, and certification rather than the possibility of exactness itself: Xu et al. also establish conditional error-free representation results. We have clarified these relationships without claiming a general computational advantage over lattice representations.

3. Equivalence over a bounded domain

The bounded domain $ \Omega $ specifies where functional equivalence is required and can be chosen according to the application, rather than being restricted to the training samples. Once all leaves are certified, Theorem 2 guarantees equivalence at every input in $ \Omega $, including augmented inputs that remain within it. For flipped, mirrored, or generated inputs outside $ \Omega $, the existing certificate provides no guarantee; the domain must be expanded and the representation refined and re-verified accordingly.

4. Sensitivity to changes in network parameters

We thank the reviewer for this interesting question.

The current HHT construction targets a fixed, trained ReLU network. Its affine functions and activation regions are derived from the network parameters. In particular, for an activation pattern $ P $, the corresponding affine representation is determined by the weight matrices, bias vectors, and activation gating matrices.

Consequently, changing the network parameters may alter both the affine coefficients and the activation-region boundaries. Even a small parameter perturbation can invalidate some of the existing affine comparisons or leaf-wise containment certificates.

Therefore, the current method does not guarantee that an HHT constructed for one set of network parameters remains functionally equivalent after the network parameters are updated.

A natural direction for future work is incremental HHT updating. In principle, this could involve identifying affected affine regions, updating their affine coefficients, and re-verifying the corresponding leaf domains while retaining unaffected portions of the existing tree whenever their certificates remain valid.

5. A more detailed comparison of tree complexity

We appreciate this suggestion and agree that comparing only the number of leaves and tree depth does not fully characterize the structural differences between HHT and RENTT.

The two methods employ fundamentally different decision rules:

  • RENTT: Internal nodes represent neuron-level activation decisions. Its tree depth therefore reflects the number of sequential activation tests along a path.
  • HHT: Internal nodes compare two affine functions induced by the network. Its depth reflects the number of affine-function comparisons required to identify the output affine rule.

Thus, the depth values have different structural interpretations and should not be regarded as directly equivalent measures of computational complexity.

To provide a more complete comparison, we report the number of leaves, depth, construction time, inference latency, and inference-only storage.

For example, on the two-hidden-layer [100,100] network, the reported averages are:

MetricRENTT (Sparse)HHT
Leaves1,100.24,224.2
Depth200.021.6
Construction time (s)12.3731,081.453
Inference latency (μs/point)1,781.6110.80
Storage (KB)38,020.20462.77

These results reveal an important trade-off.

HHT produces a wider tree in terms of the number of leaves and incurs a substantially higher offline construction cost. However, its maximum tree depth is considerably lower, and its measured inference latency and inference-only storage are substantially smaller in this experiment.

The difference follows from the distinct representations: HHT stores affine-function comparisons rather than sequential neuron-activation tests.

Our complexity analysis further characterizes these costs. If $ L $ denotes the number of distinct affine functions, $ d $ the input dimension, and $ V_N $ the total number of sample-node incidences during construction, the worst-case tree-construction complexity is

$ T_{\mathrm{build}}=O(L^2dV_N). $

For approximately balanced splits, $ V_N=O(N\log N) $, giving

$ T_{\mathrm{build}}=O(L^2Nd\log N). $

In addition, the LP-based verification and resampling stage incurs separate computational costs, as characterized in Lemma 1.

We emphasize that this analysis does not imply that HHT is uniformly more efficient than RENTT. Rather, the results characterize a construction-versus-deployment trade-off: HHT can require substantially more offline computation in exchange for a shallower affine-comparison representation with lower measured online inference costs in the evaluated settings.

We have further clarified the interpretation of these metrics and distinguished the tree-construction, verification, and deployment costs in the revised manuscript.

6. Applicability to a broader class of piecewise-affine neural networks

We agree with the reviewer that restricting the current implementation to ReLU networks limits its applicability to other commonly used neural architectures. We would like to clarify that the underlying HHT representation is not inherently restricted to ReLU activation functions. Its essential requirement is that the target network represents a continuous piecewise-affine (PWA) function with finitely many affine regions. GeLU is not piecewise affine and therefore lies outside the current exact formulation.

To investigate this broader applicability, we extended our implementation to directly handle two additional piecewise-linear activation functions: LeakyReLU and PReLU.

Specifically, we considered three configurations: LeakyReLU with negative slopes $ \alpha=0.1 $ and $ \alpha=0.3 $, and PReLU with independently parameterized negative slopes for individual neurons. For PReLU, the negative slopes were sampled from [0.05, 0.30]. All networks had two hidden layers of width 10, with five random seeds per configuration. We used 5,000 initial samples for HHT construction and evaluated the resulting representations on 10,000 held-out inputs over the domain $ [0,1]^2 $.

The results are summarized below (mean ± standard deviation over five seeds).

ActivationTest MAETest maximum errorHHT leavesHHT depthConstruction time (s)
LeakyReLU ($ \alpha=0.1 $)1.13e-166.44e-1646.4 ± 21.08.0 ± 1.41.40 ± 0.62
LeakyReLU ($ \alpha=0.3 $)1.66e-168.30e-1647.8 ± 19.87.8 ± 1.11.44 ± 0.59
PReLU1.32e-167.11e-1644.8 ± 15.98.2 ± 1.11.33 ± 0.47

The results show that the HHT construction can represent these networks with numerical reconstruction errors at the level of floating-point precision. In particular, the PReLU experiments demonstrate that the construction is not limited to a shared negative slope across neurons. The resulting trees also remain relatively compact, with approximately 45–48 leaves and depths of 7.8–8.2 on average.

These experiments support the applicability of the HHT construction beyond standard ReLU networks. They also suggest that the key structural requirement is the finite piecewise-affine nature of the network rather than the specific choice of ReLU activation.

7. Construction complexity and scalability

We appreciate the reviewer's concern regarding the computational cost of constructing HHT.

We acknowledge that the offline construction cost can become substantial as the number of distinct affine regions increases. This limitation is consistent with the complexity analysis and the experiments reported in the manuscript.

In particular, HHT is not intended to replace ordinary neural-network inference or to provide a universally more efficient representation for every network architecture. Its primary objective is to obtain an explicit and certified function-level representation when structural analysis and reusable constrained queries justify the offline compilation cost.

Once constructed and certified, the HHT can be reused for different local or general polyhedral queries by changing only the additional linear constraints. Appendix G demonstrates this capability through local, general-polyhedral, and global output-range queries.

We also compare the exact HHT ranges with CROWN-IBP bounds in the original experiments. To further strengthen the exact optimization comparison, we have additionally evaluated a ReLU-MILP formulation on the same constrained range-query settings. Across the evaluated configurations and queries, the computed extrema agree to within a maximum absolute discrepancy of $ 1.8\times10^{-10} $.

These additional results support the numerical correctness of the HHT range-query implementation while illustrating its potential for repeated constrained analysis. We emphasize that the resulting timing advantage depends on the query workload and implementation, and that HHT incurs a substantial one-time compilation cost.

We have incorporated these clarifications and explicitly stated the intended application regime and computational trade-offs.

8. Minor comments

We thank the reviewer for identifying the presentation issues.

We have addressed the following points:

  1. Added the appropriate reference for CROWN-IBP at its first occurrence in the main text and briefly introduced its role as a sound bound-propagation method.
  2. Standardized the notation in Equations (1)–(2) and Assumption 2 to improve readability.
  3. Used consistent notation for nonterminal and leaf nodes throughout the main text and appendices.

We sincerely thank the reviewer again for the detailed feedback. We believe these clarifications will improve the precision of our theoretical statements, the interpretation of our experimental results, and the positioning of HHT relative to existing neural-network-to-tree methods.

First of all, I thank the authors to address my questions. A majority of my concerns were addressed although I still think the scope is limited therefore I am still on the edge of reconsidering my score during discussion.

Reviewer_cdetOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This article presents a reduction method of ReLU neural networks to decision trees that are endowed with a min or max operation at every node and a certain affine function at the edge of each tree. The main contribution of the article is to show that given finitely many inputs, one can reproduce the exact behavior of any given ReLU neural network (output-wise) via a corresponding decision tree of that kind.

Critical strengths

The idea of reducing a ReLU NN to a decision tree could be beneficial for certain purposes such as training.

Critical weaknesses

The article lacks on several levels:

  • arguing motivations for such a reduction, even from a theoretical standpoint

  • the reduction itself depends on the data, so the entire behavior of the NN is not reproduced, only its behavior on the data points ( please see my question below to confirm this). Given this; the result is not surprising and appears to be of limited interest for practical applications.

Questions for authors

What is the main motivation of such a reduction? Would this reduction make training easier on a dataset?

2 comments

We sincerely thank the reviewer for the thoughtful comments and for recognizing the potential value of reducing ReLU networks to decision trees. We appreciate the opportunity to clarify the motivation and theoretical scope of our work.

1. Motivation of the proposed reduction

We would first like to clarify that HHT is not intended to simplify the training of the original neural network or improve its predictive performance on a dataset. Instead, its objective is to provide an explicit and reusable representation of the function implemented by a fixed, trained ReLU network.

ReLU networks provide flexible decision models amenable to gradient-based training, while the need to inspect, verify, or revise learned policies has motivated tree extraction, as exemplified by SCoBots (Delfosse et al., 2024), which distills a ReLU action selector using VIPER (Bastani et al., 2018). This raises the question of whether an extracted tree can preserve a fixed network’s function exactly throughout a prescribed domain, beyond agreement on sampled inputs or similarity in task performance.

Although a ReLU network defines a continuous piecewise-affine (PWA) function, its switching geometry is implicitly encoded in the network's activation patterns. A standard forward pass identifies the active affine mapping at a particular input, but does not directly provide an explicit representation of the polyhedral regions over which the network follows each affine rule.

HHT addresses this gap by compiling the network into a tree whose internal nodes compare network-induced affine functions and whose leaves store affine output rules. Importantly, the resulting representation can be verified through leaf-wise polyhedral containment conditions, providing a sufficient certificate of functional equivalence throughout a prescribed bounded domain.

We see three main uses of this representation:

  1. Structural auditability: HHT exposes the affine comparisons, switching boundaries, and output rules that characterize the network's piecewise-affine behavior.
  2. Exact constrained analysis: Once certified, the explicit leaf polytopes enable exact optimization of the network output over arbitrary polyhedral subsets of the prescribed domain through linear programming.
  3. Reusable function-level compilation: The same certified representation can support multiple subsequent queries without reconstructing the network's activation-region decomposition for each new input constraint.

The exact range-query experiments in Appendix G illustrate the second and third capabilities: the same compiled HHT is used for local neighborhoods, general polyhedral constraints, and global-domain queries.

To make the reusable-compilation benefit more concrete, we additionally compared the certified HHT against a direct ReLU-MILP formulation under identical input constraints. Across 105 matched HHT–MILP range-query comparisons, the maximum absolute discrepancy between computed extrema was below 1.8×10−101.8\times10^{-10}. We further measured the break-even query count N∗N^*, i.e., the number of repeated constrained queries at which one-time HHT compilation plus online queries becomes no more expensive than rebuilding and solving the MILP for each query. The average break-even counts were 29.2, 31.2, and 11.8 for the [10,10][10,10], [50,50][50,50], and [100,100][100,100] networks, respectively.

NetworkHHT compile (s)HHT query (ms/q)MILP query (s/q)$ N^* $
$ 10\times10 $$ 1.33 \pm 0.34 $$ 1.28 \pm 0.17 $$ 0.054 \pm 0.022 $$ 29.2 \pm 10.3 $
$ 50\times50 $$ 121.19 \pm 14.24 $$ 14.53 \pm 1.61 $$ 4.012 \pm 0.684 $$ 31.2 \pm 6.5 $
$ 100\times100 $$ 1096.37 \pm 215.24 $$ 50.92 \pm 9.31 $$ 108.55 \pm 62.22 $$ 11.8 \pm 6.4 $

HHT is therefore intended as a post-training function-analysis and compilation tool, rather than as a replacement for ordinary neural-network inference or a method for reducing training complexity.

2. Does the reduction reproduce the entire behavior of the network?

We agree that this distinction deserves clarification. The initial tree construction is indeed sample-driven, and Theorem 1 establishes exact interpolation on the given finite sample set. However, sample-level interpolation is not the final equivalence guarantee of HHT.

Our method distinguishes between the following two stages:

  • Initial construction: Algorithm 1 constructs a tree that exactly reproduces the network outputs on the fixed construction samples.
  • Certification and refinement: Algorithm 2 checks leaf-wise containment in a union of compatible activation-region closures. A failed containment test returns a witness used to discover additional activation regions, expand the verification union, or refine the affected leaf.

Specifically, for a leaf $ t $, let $ D_t $ denote its routed domain and $ R_t $ the union of the closures of all activation regions whose associated affine functions coincide identically with the leaf output. Theorem 2 establishes that

$ f_{\mathrm{HHT}}(x)=f_{\mathrm{ReLU}}(x), \qquad \forall x\in D_t\cap R_t. $

If the containment condition

$ D_t\subseteq R_t $

holds for every leaf, then, since the leaf domains cover the prescribed input domain $ \Omega $,

$ f_{\mathrm{HHT}}(x)=f_{\mathrm{ReLU}}(x), \qquad \forall x\in\Omega. $

Therefore, the final equivalence guarantee is not restricted to the construction samples or an empirical test set. It is established over the entire prescribed bounded domain through leaf-wise LP certification.

We emphasize that Theorem 1 proves finite termination of the tree construction for a fixed sample set satisfying the stated assumptions, whereas Theorem 2 establishes domain-wide equivalence conditional on successful certification of all leaves.

We have clarified this distinction and further emphasize the intended post-training analysis and compilation perspective in the revised manuscript.

Reviewer_q7uAOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces HHT, a procedure to obtain a tree based equivalent representation of ReLU NN. The tree structure uses affine decision rules and leaf outputs. The tree is constructed from a greedy procedure with subsequent refinement.

Critical strengths
  • The trees obtained are relatively shallow since affine maps that are shared across activation patterns don't require multiple leaves.
  • The method provides a LP containment certificate.
Critical weaknesses
  • The method compares aganist [3], which is not an appropriate/natural choice as the only baseline to report. The two methods are structurally different, have significantly different complexity and offer different guarantees.
  • Some relevant related work is missing. In particular [1] builds trees over piecewise affine partitions, using affine rules and affine leaves predictions, which is closely related to the proposed construction. This approach (paired with exact enumeration) seems like the more natural competitor.
  • In the regime tested the networks are small enough that region enumeration is not only tractable but cheap [4,5,6]. If the appeal of the method is the superior scalability, it should be tested on the regime where enumeration breaks.
  • Comparing aganist CROWN-IBP is insufficient. ReLU networks can be encoded with mixed integer linear programming (MILP) [7] which gives exact ranges.

[1] P. Tøndel, T. A. Johansen, A. Bemporad. Evaluation of piecewise affine control via binary search tree. Automatica, 39(5):945–950, 2003.

[3] H. Monke, B. Fresz, M. Bernreuther, Y. Chen, M. F. Huber. Efficiently transforming neural networks into decision trees: A path to ground truth explanations with RENTT. arXiv:2511.09299, 2025.

[4] A. Berzins. Polyhedral complex extraction from ReLU networks using edge subdivision. ICML, 2023.

[5] J. A. Vincent, M. Schwager. Reachable Polyhedral Marching (RPM): A safety verification algorithm for robotic systems with deep neural network components. ICRA, 2021.

[6] J. A. Vincent, M. Schwager. Reachable Polyhedral Marching (RPM): An exact analysis tool for deep-learned control systems. IEEE TNNLS, 2025.

[7] V. Tjeng, K. Xiao, R. Tedrake. Evaluating robustness of neural networks with mixed integer programming. ICLR, 2019.

Questions for authors
  • Can you substantiate the claim "enumerating all regions is intractable"? It seems to me that it would be tractable for the regime tested [4,5,6].
  • Why was RENNT chosen as the main comparison?
3 comments

We thank the reviewer for the constructive comments and for recognizing the compact tree representations and LP-based containment criterion as strengths of HHT. We agree that our original submission insufficiently discussed enumeration-based PWA search trees and exact MILP optimization, and that our statement regarding the intractability of region enumeration was overly broad.

To address these concerns, we conducted additional experiments with an enumeration-based PWA binary search tree (PWA-BST) and a ReLU-MILP baseline. We clarify the methodological distinctions and report the results below.

1. Why RENTT? Relationship to PWA search trees

We selected RENTT because it directly transforms a fixed ReLU network into a decision-tree representation, making it a relevant baseline for NN-to-tree conversion. However, we agree that it should not be the only structural baseline.

The methods highlighted by the reviewer are related but address different stages of the representation problem.

  • RENTT (Monke et al., 2025) directly transforms a ReLU network into a tree by organizing neuron-level activation decisions.
  • Tøndel et al. (2003) construct binary search trees from an already available piecewise-affine partition. Applying this approach to ReLU networks naturally requires obtaining the underlying PWA partition first.
  • Region-enumeration methods, including Berzins (2023) and RPM (Vincent and Schwager, 2021, 2025), provide approaches for extracting the polyhedral regions induced by neural networks.
  • HHT (ours) directly constructs a tree from sampled network-induced affine functions and subsequently uses leaf-wise containment verification to establish domain-wide equivalence.

These approaches can be understood through the following alternative pipelines:

$ \text{ReLU network} \rightarrow \text{region enumeration} \rightarrow \text{PWA partition} \rightarrow \text{binary search tree} $

versus

$ \text{ReLU network} \rightarrow \text{sampled affine functions} \rightarrow \text{HHT} \rightarrow \text{LP certification}. $

The distinction is not that HHT eliminates the need for global verification or that region enumeration is necessarily intractable. Rather, HHT avoids requiring a complete PWA partition as an intermediate representation for its initial tree construction. Its domain-wide equivalence guarantee is established separately through the sufficient leaf-wise containment conditions in Theorem 2.

We agree that RENTT alone is insufficient to characterize the structural alternatives available for this problem. We have incorporated Tøndel et al. and the relevant region-extraction literature into the revised related-work section, while distinguishing direct NN-to-tree construction from PWA-region extraction and subsequent tree construction.

2. New enumeration-based PWA-BST baseline

Following the reviewer's suggestion, we constructed this comparison baseline, which first performs numerical enumeration of activation regions and then builds a facet-based PWA binary search tree (PWA-BST) via our independent implementation of Tøndel et al. (2003).

We evaluated this baseline on Moons, Circles, and Airfoil using the same two-hidden-layer 6×6 ReLU network settings and five seeds as the main experiments. Construction time includes both numerical region enumeration and subsequent tree construction.

The results (mean over five seeds) are:

DatasetMethodLeavesBuild (s)
MoonsHHT66.01.069
MoonsPWA-BST56.40.669
CirclesHHT71.61.112
CirclesPWA-BST62.20.714
AirfoilHHT85.01.520
AirfoilPWA-BST813.686.821

All three PWA-BST experiments completed across five seeds, with test-set reconstruction errors near floating-point precision. These results reveal a meaningful geometry-dependent trade-off. On the two-dimensional Moons and Circles datasets, PWA-BST produces smaller trees with lower construction costs. However, on the five-dimensional Airfoil dataset, HHT achieves a substantially more compact representation on average: 85.0 versus 813.6 leaves, depth 8.4 versus 16.8, and construction time 1.52 versus 86.82 seconds, together with lower measured inference latency (1.02 versus 2.56 μs/point).

3. Clarification regarding region enumeration and scalability

We agree with the reviewer that complete region enumeration can be practical for the small, low-dimensional networks considered in our experiments.

Indeed, our additional PWA-BST experiments successfully completed numerical enumeration of the activation regions for all five seeds on Moons, Circles, and Airfoil. These results directly support the reviewer's observation that enumeration is tractable in the evaluated regime.

We further evaluated our enumeration-to-PWA-BST pipeline for Abalone and Diabetes. Numerical region enumeration completed (973 and 184 regions, respectively), but the subsequent PWA-BST construction did not finish within the 1,800-second time limit in either case. These implementation-specific observations further illustrate that search-tree construction can be substantially more expensive than region enumeration itself.

We have removed the blanket claim that enumerating all regions is intractable and have incorporated the relevant RPM literature. Our motivation is not that enumeration necessarily fails on the networks studied. Rather, HHT offers an alternative construction route that does not require complete global region enumeration before building its initial tree.

4. Exact output-range comparison with ReLU-MILP

We agree that CROWN-IBP alone is insufficient as a baseline for exact constrained optimization, since it computes sound bounds rather than directly optimizing the original ReLU network. We therefore implemented a direct ReLU-MILP formulation and compared it against HHT under identical input constraints.

The additional evaluation covers three two-dimensional network configurations, [10,10], [50,50], and [100,100], with five seeds each. For each network, we evaluate the six general polyhedral queries (C1–C6) and the global-domain query from Appendix G, yielding 105 matched HHT–MILP range-query comparisons. Across all comparisons, the maximum absolute discrepancy between the computed extrema was below 1.8 × 10⁻¹⁰, demonstrating near-floating-point agreement with direct MILP optimization.

We also investigated the benefit of reusing the compiled HHT for repeated queries. For this evaluation, we implemented a two-dimensional polygon-clipping query engine over the HHT leaf polytopes, and compared its online query time against a direct ReLU-MILP formulation solved using HiGHS. The compiled HHT exhibited lower measured online query times across the evaluated queries, while incurring a substantial one-time construction cost.

Using the measured per-query runtimes from seven representative queries, we compute the break-even number of queries $ N^* $: the minimal discrete query count where the total cost of HHT (one-time compilation + $ N $ queries) is no larger than the total MILP cost for $ N $ queries. We compute this break-even value separately for each seed and then average over the five seeds. With the MILP model rebuilt from scratch for every query, the resulting average break-even counts are 29.2, 31.2, and 11.8 queries for the [10,10], [50,50], and [100,100] networks, respectively.

NetworkHHT compile (s)HHT query (ms/q)MILP query (s/q)$ N^* $
$ 10\times10 $$ 1.33 \pm 0.34 $$ 1.28 \pm 0.17 $$ 0.054 \pm 0.022 $$ 29.2 \pm 10.3 $
$ 50\times50 $$ 121.19 \pm 14.24 $$ 14.53 \pm 1.61 $$ 4.012 \pm 0.684 $$ 31.2 \pm 6.5 $
$ 100\times100 $$ 1096.37 \pm 215.24 $$ 50.92 \pm 9.31 $$ 108.55 \pm 62.22 $$ 11.8 \pm 6.4 $

These results illustrate the potential value of compiling a network into an explicit, reusable PWA representation when multiple constrained queries are required.

We have incorporated the MILP comparison and clarified the offline compilation versus repeated-query trade-off in the revised manuscript.

5. Clarification of our contribution

We appreciate the reviewer drawing attention to these closely related approaches.

HHT introduces a direct, sample-driven NN-to-tree construction based on comparisons of network-induced affine functions, together with a sufficient leaf-wise containment criterion for domain-wide functional equivalence.

Theorem 1 establishes finite termination and sample-level correctness for the fixed-sample construction, while Theorem 2 establishes domain-wide equivalence when the required containment conditions are satisfied. We distinguish these theoretical guarantees from empirical reconstruction accuracy.

The additional comparisons clarify the relationship between HHT and existing approaches:

  • Against RENTT: HHT organizes network-induced affine functions rather than sequential neuron-activation decisions.
  • Against enumeration-based PWA-BST: HHT constructs its initial tree without first enumerating the complete PWA partition, and can yield a more compact representation in some settings.
  • Against ReLU-MILP: HHT provides an explicit, reusable PWA representation that can amortize its construction cost across repeated constrained queries.

We have revised the related-work discussion, corrected the enumeration claims, incorporated the new PWA-BST and MILP comparisons, and explicitly stated the observed computational trade-offs and certification conditions.

We thank the reviewer again for these valuable suggestions, which have helped us better position HHT relative to existing methods and clarify its practical and theoretical contributions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.