- 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:
- 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.
- 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:
- CROWN-IBP mentioned in the main text without any reference or description. It is introduced in the appendix.
- In equations 1-2 and Assumption 2 the is referenced in various forms thus harder to read.
- Similarly the nonterminal and the leaf nodes are referred with different styled D-s and T-s (e.g. line 165).
Critical strengths
- 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.
- 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
- 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.
- The proposed tree structure and the algorithm provide functional equivalence under the bounded domain which can be quite limited in my opinion.
- 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.
- 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.
- 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
- 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.
- 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?
- 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
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:
| Metric | RENTT (Sparse) | HHT |
|---|---|---|
| Leaves | 1,100.2 | 4,224.2 |
| Depth | 200.0 | 21.6 |
| Construction time (s) | 12.373 | 1,081.453 |
| Inference latency (μs/point) | 1,781.61 | 10.80 |
| Storage (KB) | 38,020.20 | 462.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).
| Activation | Test MAE | Test maximum error | HHT leaves | HHT depth | Construction time (s) |
|---|---|---|---|---|---|
| LeakyReLU ($ \alpha=0.1 $) | 1.13e-16 | 6.44e-16 | 46.4 ± 21.0 | 8.0 ± 1.4 | 1.40 ± 0.62 |
| LeakyReLU ($ \alpha=0.3 $) | 1.66e-16 | 8.30e-16 | 47.8 ± 19.8 | 7.8 ± 1.1 | 1.44 ± 0.59 |
| PReLU | 1.32e-16 | 7.11e-16 | 44.8 ± 15.9 | 8.2 ± 1.1 | 1.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:
- 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.
- Standardized the notation in Equations (1)–(2) and Assumption 2 to improve readability.
- 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.
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.