acceptodds
Under review as a conference paper at ICLR 2027

NADT: Neighborhood-Augmented Neural Decision Trees

Abstract

Neural decision trees enable end-to-end gradient optimization of hierarchical routing. Their split functions are globally fixed during inference, applying identical decision boundaries irrespective of local data structure. Meanwhile, -nearest neighbor methods provide sample-adaptive local awareness, but their flat architectures cannot decompose complex boundaries hierarchically. To address this limitation, we propose NADT, which equips a neural decision tree with neighborhood-adaptive routing through a Neighborhood Context Module (NCM) and a soft decision tree ensemble. NCM maintains learnable prototypes in a shared embedding space and maps sample-to-prototype distances via temperature-scaled Softmax to node-level biases. These biases are injected into the oblique split nodes of the soft tree ensemble, shifting decision boundaries dynamically with each sample's neighborhood context. Since prototypes are learned parameters, NADT achieves local awareness without retrieving the training set at inference. Extensive experiments on 30 public datasets demonstrate that NADT outperforms 11 competing methods, with ablation confirming module effectiveness and visualization validating the interpretability.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
neural decision trees, nearest neighbor, prototype learning, tabular data

Reviews

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

The paper proposes NADT, a soft decision tree ensemble that uses learned prototypes to incorporate neighborhood information into routing. A Neighborhood Context Module converts prototype affinities into input-dependent biases at internal tree nodes, without retrieving training samples during inference. Experiments on 30 classification datasets report the best average rank among the compared methods.

Critical strengths
  1. The method provides a practical way to combine prototype-based neighborhood modeling with hierarchical routing. Sharing a compact prototype bank across the ensemble allows local adaptation without storing the training set for inference.

  2. The evaluation includes repeated cross-validation, component ablations, runtime measurements, and a parameter-matched MLP router. These controls help examine the contribution of prototype-based routing beyond a standard soft tree ensemble.

Critical weaknesses
  1. The expressivity proof contains a concrete gap. Lemma 4 claims that any nonzero context projection preserves differences between affinity vectors, but a matrix with identical columns produces a constant output because the affinities sum to one. Furthermore, showing different routing from one fixed baseline configuration does not establish that the resulting classifier cannot be represented by another baseline configuration. The claimed strict function-class containment therefore remains unproven.

  2. The baseline tuning leaves uncertainty about the reported advantage. Table 4 limits XGBoost, LightGBM, and CatBoost to at most 150 boosting iterations, which may restrict their performance. The paper also does not clearly report NADT’s tuning search space or the number of Optuna trials per method, making it difficult to assess whether the comparison uses comparable tuning effort.

  3. The claim that the gains specifically come from neighborhood structure is stronger than the ablation evidence supports. NADT and the MLP router have average ranks of 2.37 and 3.60, a difference below the reported Nemenyi critical difference of 1.38. Since the controls also use shared default hyperparameters rather than separate tuning, the results suggest a benefit but do not establish a statistically significant advantage over generic input-dependent routing.

Questions for authors
  1. Can you provide a corrected strict-containment proof that accounts for degenerate nonzero context projections and LayerNorm, and rules out alternative baseline parameterizations?

  2. Does NADT retain its advantage when the boosting baselines receive broader search spaces and all methods receive a comparable tuning budget? Please specify NADT’s search space and the trial budget for each method.

  3. Does the prototype-based module outperform the MLP router when both are tuned separately and use matched parameter counts, normalization, and training schedules?

4 comments
AuthorsOpenReview ↗

Response to Q1 (strict-containment proof) and Q2 (baseline tuning budget)

We thank the reviewer for the careful reading and the constructive suggestions. We reply point by point below.

Q1

We checked the manuscript and confirmed the issue you raised, and have completed the correction in the revised manuscript.

For matrices with identical columns, we tighten the "nonzero" assumption into an explicit rank condition (Lemma 5, Eq. (13), in Appendix B.1), requiring that the projection of W_ctx on the zero-sum subspace of the affinities be non-degenerate. Matrices with identical columns are directly excluded under this condition.

For the LayerNorm collapse, we first prove a lemma (Lemma 4 in Appendix B.1). For the standard layer normalization LN(u) = (u − ū·1)/√(v + ε) (where ū and v are the mean and variance of u, 1 is the all-ones vector, and ε > 0 is any fixed constant), LN(u₁) = LN(u₂) if and only if u₁ − u₂ ∈ span{1}. That is, LN nullifies exactly the translations with equal components and preserves every other difference. This rank condition combined with this characterization guarantees that the projected difference falls outside the null space of LN, so the node biases are non-constant.

For "one configuration does not imply strict containment", we construct a NADT function with a specific asymptotic profile (softmax saturation gives its restriction along any ray an exponentially decaying term). We then prove that the restriction of any baseline function along any ray is a rational function and cannot carry such an exponential decay term. This argument holds simultaneously for every baseline parameterization, thereby ruling out all alternative parameterizations and giving F_base ⊊ F_NADT.

The corrected lemma statements and proofs are given in Appendix B.1.

Q2

We have re-run the baselines you mentioned with broadened search spaces, and completed the tuning protocol in the revised manuscript (Appendix E, Table 5; the trial budget is added in Section 4.2). The broadened search spaces are as follows:

MethodBroadened space
Random Forestn_estimators {100, 300, 500, 1000}; max_depth {None, 5, 10}; min_samples_leaf {1, 3}; max_features {'sqrt', 0.5}
XGBoostn_estimators ∈ [100, 2000] (early stopping, patience 50); max_depth [3, 6]; learning_rate {0.05, 0.1, 0.2}; subsample {0.7, 0.9, 1.0}
LightGBMn_estimators ∈ [100, 2000] (early stopping, patience 50); num_leaves {15, 31, 63}; learning_rate {0.05, 0.1, 0.2}; colsample_bytree {0.7, 1.0}
CatBoostiterations ∈ [100, 2000] (early stopping, patience 50); depth [4, 8]; learning_rate {0.05, 0.1, 0.2}; l2_leaf_reg {1, 3, 10}

All methods use the Optuna TPE sampler with 20 trials per method per dataset. NADT's search space is now explicitly reported in Appendix E, Table 5.

With the broadened budget, the GBDT methods do become stronger on several datasets. For example, LightGBM improves from 0.9732 to 0.9754 on AP_Uterus_Kidney (becoming the best method in that row), XGBoost improves from 0.7190 to 0.7534 on SVHN, and CatBoost improves from 0.4957 to 0.5330 on tumors_C. The full per-dataset results are reported in Section 4.2, Table 1.

The overall conclusion is unchanged. NADT remains the best method. The average ranks of all 11 methods after the re-run are listed below. The best GBDT (LightGBM) still trails NADT. Table 1 and Figure 3 in Section 4.2 have been updated to the re-run results.

MethodAvg. rank
NADT2.27
TabR3.40
modernNCA3.72
LightGBM4.47
XGBoost4.70
CatBoost5.53
Random Forest6.97
GRANDE7.93
DTSemNet7.97
DOFEN9.53
SoHoT9.62

In addition, the broadened budget also substantially lengthens the training time of the GBDTs. For example, on SVHN, XGBoost takes 5,569 s and LightGBM takes 3,295 s, versus 595 s for NADT (Section 4.6 and Appendix I, Tables 15–16).

AuthorsOpenReview ↗

Response to Q3 (MLP router under independent tuning)

Q3

We have re-tuned and re-run all ablation variants independently, with the same search space, protocol, and data preprocessing as the full model, so the comparison no longer shares hyperparameters. The updated results are reported in Section 4.3, Appendix E (Table 5), and Appendix F (Tables 6–8), and are summarized below. Under these conditions, NADT still outperforms the MLP router.

VariantW/L/T vs NADTAvg F1BestAvg Rank
NADT (full)—0.852112.32
w/o NCM21/8/10.81223.78
w/ Random δ21/9/00.81933.28
w/o Projector23/7/00.84852.98
w/ Axis-Aligned24/5/10.82244.63
w/ MLP Router22/8/00.82873.90

Regarding statistical significance. After independent tuning, the ranks of Full and w/ MLP Router are 2.32 and 3.90. The difference of 1.58 exceeds the Nemenyi critical difference of 1.38 (k = 6, N = 30, α = 0.05), establishing a significant advantage. This result is now stated in Appendix F of the revision.

Thank you for the detailed response and the revised manuscript.

My concerns about the proof, the baseline tuning, and the MLP router comparison are now resolved. However, in the new ablation table, Random δ (3.28) now ranks better than w/o NCM (3.78) and the MLP router (3.90), and it is not significantly different from full NADT (gap 0.96 < CD 1.38). But Section 4.3 still says Random δ performs nearly identically to w/o NCM. Also, in Table 1, the OVA_Uterus and OVA_Lung rows have the same scores for NADT, DOFEN, GRANDE, SoHoT, and DTSemNet. I'm curious if this is a coincidence or a copy error.

I also agree with the other reviewers that the novelty is somewhat incremental and that the performance gain is not significantly better than TabR and ModernNCA.

AuthorsOpenReview ↗

Response to the new comment: Random δ statement correction, OVA_Lung data fix, and novelty positioning

We thank the reviewer for the reply and are glad that the concerns from the review stage are now resolved. We reply to the issues raised in your latest comment below.

R1(Inconsistency between the Random δ statement and the data): We checked the manuscript and confirmed that the original sentence in Section 4.3 is inconsistent with the updated ablation results. We have corrected this statement in the manuscript. Regarding significance, we provide the average rank to give a more comprehensive comparison across all variants. The updated summary table (Section 4.3, Table 2; W/L/T counts are against NADT) reads:

MethodW/L/TAvg F1#BestRank
NADT (full)--0.857122.25
w/o NCM21/8/10.81613.72
w/ Random δ\boldsymbol{\delta}22/8/00.82433.32
w/o Projector24/6/00.85243.08
w/ Axis-Aligned24/5/10.82634.67
w/ MLP Router22/8/00.83373.87

NADT leads every variant on all four metrics. It beats Random δ\boldsymbol{\delta} on 22 of 30 datasets, with a higher average F1 (0.857 vs 0.824) and the highest score on 12 datasets versus 3. A non-significant rank gap should not be taken as evidence that the methods perform the same.

R2(Identical OVA_Uterus and OVA_Lung rows): Thank you for this careful check. We traced the cause and confirmed a data loading error. The data-loading code for OVA_Lung mistakenly used the OpenML id of OVA_Uterus (1138), while the correct id is 1130. As a result, the OVA_Lung row in Table 1 actually reported results on OVA_Uterus. We have corrected the id and report the corrected OVA_Lung results in the manuscript (Sections 4.2 and 4.3). The overall conclusion is unchanged. NADT remains the best method. The average ranks of all 11 methods after the correction are listed below (ProtoGate is excluded due to missing results on 8 datasets).

MethodAvg. rank
NADT2.50
TabR4.12
modernNCA4.25
LightGBM4.83
CatBoost4.88
XGBoost4.90
DOFEN5.82
Random Forest6.27
DTSemNet8.48
SoHoT10.13
GRANDE10.33

R3(Novelty positioning and non-significant gaps within the top group): We agree with this assessment. NADT is not statistically separated from TabR and ModernNCA in the CD diagram, and we do not claim a statistical advantage over them. What we want to emphasize is that NADT achieves the best overall performance. The strong results of TabR and ModernNCA confirm the effectiveness of incorporating sample-wise local information, which is consistent with our motivation. Building on this, NADT further internalizes local information into the splits themselves and achieves stronger expressive power and performance.

After broadening the GBDT tuning budget and correcting the data, NADT attains an average rank of 2.50, ahead of TabR (4.12) and ModernNCA (4.25). It achieves the highest score on 13 datasets, more than TabR (5) and ModernNCA (4). In per-dataset counts, NADT records 20 wins and 10 losses against TabR, and 24 wins and 6 losses against ModernNCA (Section 4.2, Table 1 and Figure 3). Likewise, the rank gaps below the CD should not be taken as evidence that NADT performs on par with TabR and ModernNCA.

This mechanism also yields a separation in expressive power. The corrected proof, which accounts for LayerNorm and degenerate projections, shows that there exist NADT functions that no baseline parameterization can represent (Theorem 1, Appendix B.1). In addition, the inference cost of NADT differs. TabR must retrieve instances from the training set at inference, and ModernNCA must score all training samples. In contrast, NADT's biases depend only on a fixed prototype bank, so the training set is no longer needed after training (Appendix I).

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

This paper proposes Neighborhood-Augmented Neural Decision Trees (NADT), a framework that incorporates local neighborhood information into neural decision tree ensembles to address the limitations of globally fixed splitting functions. The key component is a Neighborhood Context Module (NCM), which uses learnable prototypes and temperature-scaled softmax to generate input-dependent biases for adaptive tree routing. The model is trained end-to-end with a prototype diversity regularization term. Experiments on 30 classification datasets against 11 baselines show that NADT achieves the best average rank in Macro-F1. Ablation studies and visualizations further demonstrate the effectiveness of the proposed components.

Critical strengths
  1. The paper presents an intuitive way to incorporate local neighborhood information into hierarchical decision-making. By using learnable prototypes to generate input-dependent routing biases, NADT combines the hierarchical structure of neural decision trees with the local adaptivity of neighborhood-based methods. The approach is relatively simple and does not require retrieving training instances during inference.
  2. The evaluation covers 30 datasets and a diverse set of 11 baselines, including strong traditional tree ensembles and recent neighborhood-based methods. NADT achieves the best overall average rank. The synthetic decision boundary visualization further illustrates the intended behavior of the proposed method.
Critical weaknesses
  1. Theorem 1 claims that the proposed neighborhood context module strictly enlarges the function class of the baseline soft decision tree ensemble. However, the argument is relatively brief and does not clearly establish that nonconstant prototype affinities necessarily lead to output functions that cannot be represented by the baseline architecture. In particular, the stated conditions do not appear sufficient to guarantee nonconstant node biases after the context projection and LayerNorm. The distinction between increased architectural flexibility and a rigorously established strict increase in expressivity should be clarified.

  2. Although NADT achieves the best average rank, the critical difference analysis places NADT, TabR, and ModernNCA in the same top-performing group, so the reported results do not establish a statistically significant advantage over these strong neighborhood-based alternatives.

  3. While the MLP-router ablation is useful, the experiments do not directly measure whether the learned prototypes accurately capture meaningful local structures or how neighborhood heterogeneity relates to the performance improvements. The paper would benefit from a more targeted analysis connecting the proposed mechanism to the types of data distributions for which it is most effective.

Questions for authors
  1. In Appendix B.1, Lemma 4 states that any nonzero context projection matrix preserves differences between prototype affinity vectors. However, a nonzero matrix can map distinct affinity vectors to the same output, and LayerNorm may further eliminate differences. Could the authors clarify the sufficient conditions for the NCM to produce nonconstant node biases and provide a more rigorous justification of strict function-class containment?

  2. Can the authors provide a more direct evaluation of the relationship between local data heterogeneity and the improvements achieved by NADT? For example, how does performance change as the degree of local heterogeneity increases in controlled synthetic experiments? This would help establish whether neighborhood-adaptive routing is the primary source of the observed gains.

1 comment
AuthorsOpenReview ↗

Response to Q1 (strict-containment proof), W2 (CD analysis), and Q2 (heterogeneity–gain experiment)

We thank the reviewer for the careful reading. We reply point by point below.

Q1

We have completed the correction in Appendix B.1. Specifically, we (i) add a characterization of what LN nullifies (Lemma 4), (ii) tighten the sufficient condition on W_ctx into an explicit rank condition (Lemma 5, Eq. (13)), and (iii) replace the strict-containment proof with a constructive one. Details follow.

Sufficient conditions for LN non-collapsing and nonconstant biases: we first give the exact nullification characterization of LN (Lemma 4, for LN(u) = (u − ū·1)/√(v + ε) with any fixed ε > 0): LN(u₁) = LN(u₂) if and only if u₁ − u₂ ∈ span{1}, i.e., LN nullifies exactly the translations with equal components and no other differences. The revision tightens the condition of the original Lemma 4 (now Lemma 5) into an explicit rank condition (non-degeneracy of the projection of W_ctx on the zero-sum subspace of the affinities, Eq. (13)). This rank condition together with Lemma 4 guarantees that a non-constant difference in affinities, after projection, falls outside the null space of LN, so the node biases are non-constant.

Strict containment: the proof is now constructive. We construct a NADT function whose restriction along any ray carries an exponentially decaying term produced by softmax saturation. We then prove that the restriction of the baseline architecture along any ray is a rational function and cannot exhibit such exponential decay. The argument holds simultaneously for any fixed baseline parameterization, ruling out representation by all alternative parameterizations and yielding F_base ⊊ F_NADT.

The corrected theorem and lemma statements, together with the complete proofs, are given in Appendix B.1.

W2

We agree with your point and have adjusted the text. What we intended to emphasize with this experiment is that NADT has the best overall performance. The strong results of TabR and ModernNCA confirm the effectiveness of incorporating sample-wise local information, which is consistent with our motivation. Building on this, NADT further internalizes local information into the splits themselves and achieves stronger expressive power and performance. After broadening the GBDT tuning budget, NADT obtains the highest score on 13 datasets (Section 4.2, Table 1), far more than TabR (5) and ModernNCA (4). Its average rank of 2.50 is also clearly ahead (TabR 4.12, ModernNCA 4.25; Section 4.2, Figure 3). The CD diagram indicates which pairwise gaps cannot be statistically resolved; it is not evidence of method equivalence.

In addition, the inference cost of these methods is of a different nature. TabR must retrieve instances from the training set at inference, and ModernNCA must score all training samples. In contrast, NADT's NCM biases depend only on a fixed prototype bank, so the training set is no longer needed after training, and both the model size and the inference cost are independent of the training set size (Appendix I.2).

Q2

We have run the controlled synthetic experiment as you suggested. The results are in Appendix F.3 (Figure 8) of the revised manuscript. The experiment constructs 25 blocked synthetic instances covering five split-direction offsets Δ ∈ {0°, 15°, 30°, 45°, 60°}. Each quadrant carries its own rotated discriminative direction, and Δ controls how far the local rules deviate from the global rule. For each instance we compute a model-agnostic heterogeneity index H: using only the first two features, the per-block local linear classifier accuracy minus the global linear classifier accuracy. A large H means the single global rule fails while the local rules remain effective. The evaluation protocol follows the main text.

NADT outperforms the no-NCM ablation on 20 of the 25 instances (sign test p = 0.0041, Wilcoxon p = 0.0004). The per-instance NCM gain correlates positively with H (Spearman ρ = 0.44, p = 0.027, n = 25). The gain is larger in places where the local distribution is more heterogeneous and the single global rule fails more. The data for the five offset levels corresponding to Appendix Figure 8(b) are listed below. The average gain is positive at every level, and the instance-level gains correlate with H, indicating that neighborhood-adaptive routing is the primary source of the gains.

Offset ΔNADT avg. F1no-NCM avg. F1Avg. gain
0°0.5820.537+4.5%
15°0.6160.603+1.3%
30°0.6670.656+1.1%
45°0.6250.609+1.6%
60°0.6040.576+2.9%
Reviewer_iZ1aOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes NADT, a neural decision tree framework that incorporates neighborhood-aware routing through learnable prototypes. A Neighborhood Context Module (NCM) generates sample-dependent biases for oblique split nodes, enabling adaptive decision boundaries without explicit nearest-neighbor retrieval. Experiments on 30 classification datasets demonstrate competitive performance against tree-based and neighborhood-based baselines, supported by ablation and visualization studies.

Critical strengths

S1. Intuitive motivation and reasonable design. Incorporating neighborhood information into hierarchical routing is a meaningful direction. The prototype-based module provides sample-dependent routing without explicit training-set retrieval.

S2. Comprehensive empirical comparisons. The evaluation covers 30 datasets and multiple competitive baselines. The ablation studies, including a parameter-matched MLP router, provide useful evidence for the effectiveness of prototype-based routing.

Critical weaknesses

W1. Limited methodological novelty. NADT primarily combines established techniques, including learnable prototypes, soft decision trees, and input-conditioned routing biases. The proposed integration is reasonable, but the conceptual advance beyond existing prototype-based and neural tree methods appears incremental.

W2. Limited evidence of a decisive practical advantage. Although NADT achieves the best average rank, the critical difference analysis does not establish a statistically significant advantage over all strong competitors. In particular, the practical gains over established gradient-boosted tree methods should be evaluated alongside computational cost, training stability, and model complexity.

W3. Limited validation of robustness and interpretability. The evaluation focuses on classification datasets, leaving generalization to regression and distribution shifts unexplored. Moreover, the qualitative visualizations do not sufficiently establish that the learned routing mechanism provides meaningful interpretability.

Questions for authors

Q1. What is the key conceptual difference between NADT and existing prototype-conditioned neural tree models?

Q2. Could the authors provide a more detailed accuracy-efficiency comparison with strong baselines, including training time, inference latency, and model complexity?

Q3. How robust is NADT under distribution shifts, and can the learned prototypes be interpreted consistently across different datasets?

2 comments
AuthorsOpenReview ↗

Response to Q1 (conceptual difference) and Q2 (accuracy–efficiency comparison)

We thank the reviewer for the careful review. We reply point by point below.

Q1

We acknowledge your comment. What we would like to emphasize is that the conceptual difference lies in where local information enters the model, which is a substantive distinction from existing methods:

  • Nearest-neighbor and prototype methods: local information acts at prediction time. They retrieve training instances, compute distances to class centroids, or score candidate neighbors, and then output a prediction. The model itself contains no hierarchical decision structure, which limits the room for further performance gains.
  • Neural decision trees: in axis-aligned trees (e.g., GRANDE), each split compares a single feature against a threshold, which yields coarse rules and limited expressiveness. In oblique trees (e.g., DTSemNet), each split uses a linear combination of features and is more expressive. In both forms, however, each split is determined only by the sample's own feature values. Neighborhood information plays no role in the routing decisions, which limits performance.
  • NADT: the prototypes provide a bias added on top of the split activations, giving the model local awareness inside each split during training. Neighborhood information is internalized into the model, so every split can exploit both the sample itself and the local distribution when making routing decisions, yielding stronger expressive power.

Theorem 1 (Appendix B.1) proves that the input-dependent split biases are exactly the part that the baseline function class cannot represent, providing theoretical support for the difference above. Sections 2.1–2.2 have also been rewritten to reposition the related work and state this conceptual difference explicitly.

Q2

Regarding the CD diagram, we would like to emphasize that NADT has the best overall performance. The strong results of TabR and ModernNCA confirm the effectiveness of incorporating sample-wise local information, which is consistent with our motivation. Building on this, NADT further internalizes local information into the splits themselves and achieves stronger expressive power and performance. After broadening the GBDT tuning budget following another reviewer's suggestion, NADT obtains the highest score on 13 datasets (Section 4.2, Table 1), more than TabR (5) and ModernNCA (4). Its average rank of 2.50 is also clearly ahead (TabR 4.12, ModernNCA 4.25; Section 4.2, Figure 3).

Regarding training time, inference latency, and model complexity, the manuscript already contains the relevant analyses and data (Section 4.6, Appendix I.1 Tables 15–16, and Appendix I.2 Model Complexity). Further details are as follows.

  • Training time: taking SVHN as an example, NADT trains in 595 s, on par with ModernNCA (532 s) and far faster than TabR (18,323 s), GRANDE (3,456 s), and SoHoT (42,349 s) (Appendix I.1, Table 15; Figure 7(b)). The GBDT methods remain very fast on small datasets; after the broadened tuning budget, however, their training on large datasets becomes noticeably slower (e.g., XGBoost takes 5,569 s on SVHN). Overall, NADT achieves an acceptable training time. This is because the NCM performs only fixed-cost prototype distance computations without retrieving the training set, and the tree ensemble operates only on compact bias vectors.

  • Inference latency: NADT infers in under 0.1 s on 29 of the 30 datasets, with SVHN the only exception at 0.621 s. This is on par with efficient baselines such as XGBoost, ModernNCA, and DTSemNet. For comparison, ProtoGate takes up to 389 s (OVA_Uterus), GRANDE 76 s (ovarianTumour), TabR 37 s (SVHN), and SoHoT 32 s (jannis) (Section 4.6; Appendix I.1, Table 16). Inference requires only a single forward pass over the T trees plus the fixed-cost prototype bias computation, with no access to the training set. The inference time therefore does not grow with the training set size, and NADT's inference latency is at the same level as the fastest tree-based methods.

  • Model complexity: we have added a model complexity analysis in Appendix I.2 (Model Complexity). The per-sample forward complexity is O(dD + MD + T·2^depth·(M + rd + C)), and the parameter count is of the same order. Both are determined by architectural hyperparameters and contain no term involving the training set size n, so the model size is fixed before training starts (Appendix I.2, Eqs. 15–16). In contrast, retrieval-based methods such as TabR must retain the training set at inference (O(nd) memory), and the size of GBDT ensembles grows with the training set.

AuthorsOpenReview ↗

Response to Q3 (distribution-shift robustness and prototype interpretability)

Q3

We have added a distribution-shift evaluation experiment in Appendix F.3 (Figure 8). We construct a blocked synthetic dataset in which each quadrant carries a rotated discriminative direction, and the offset controls how far the local distributions deviate from the global one. A model-agnostic heterogeneity index H (per-block local linear accuracy minus global linear accuracy) measures the degree of deviation. NADT outperforms the no-NCM ablation on 20 of the 25 instances (sign test p = 0.0041, Wilcoxon p = 0.0004), and the per-instance gain correlates positively with H (Spearman ρ = 0.44, p = 0.027). The advantage of neighborhood-adaptive routing is larger in places where the local distribution is more heterogeneous and the single global rule fails more.

The data for the five offset levels corresponding to Appendix Figure 8(b) are listed below. The average gain is positive at every level, showing that NADT's gains arise precisely where the controlled distribution shift hurts the global rule.

Offset ΔNADT avg. F1no-NCM avg. F1Avg. gain
0°0.5820.537+4.5%
15°0.6160.603+1.3%
30°0.6670.656+1.1%
45°0.6250.609+1.6%
60°0.6040.576+2.9%

Interpretability and prototype consistency. The main text presents a visualization analysis in Section 4.5 (Figures 5 and 6), showing what the prototypes learn and how they affect decisions. Figure 6(b) reports the mean affinity weights of the 10 most active prototypes on the two classes: the prototypes split into two groups, each responding to only one class with no cross-activation, indicating that the prototypes learn class-specific representations. The t-SNE projection in Figure 6(a) shows that high-attention prototypes lie at class-cluster centers while low-attention prototypes sit near the boundary between the two classes. Figure 5(b) further shows that the routing-probability changes induced by the prototype bias δ are largest near the decision boundary (about 0.26) and drop to 0.026 away from it. This means the prototypes act where the model is least certain. The boundary-focused behavior itself (Figure 5(b)) is a property of the routing function (Lemma 11, Appendix B.2) and therefore holds regardless of the dataset. The Appendix F.3 study shows the same mechanism behaving consistently across synthetic instances.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of rebuttal revisions

We thank the PC and the AC for their work during the conference, and the three reviewers for their careful reviews and suggestions. We summarize the changes made during the rebuttal period. All revisions are marked in the updated manuscript for easy checking. Our work falls into five parts.

1. Theory (Pu3m Q1, e3cF Q1). Following the reviewers' comments, we revised the expressivity proof: a characterization of what LayerNorm nullifies (Lemma 4), an explicit rank condition replacing the previous nonzero assumption (Lemma 5), and a constructive strict-containment proof that holds for all baseline parameterizations (Appendix B.1).

2. Main comparison (e3cF Q2). We broadened the search spaces of the baselines as suggested and re-ran them under a unified protocol. The protocol and NADT's search space are reported in Appendix E, Table 5. We also fixed a data-loading error found during this period. NADT remains the best overall method.

3. Ablation (e3cF Q3). All ablation variants were re-tuned and re-run independently with the same search space and protocol as the full model, so the comparison no longer shares hyperparameters. NADT (rank 2.25) shows a significant advantage over the MLP router (3.87). We also corrected an outdated statement in Section 4.3 accordingly.

4. Source of gains (Pu3m Q2, iZ1a Q3). We added a controlled synthetic study (Appendix F.3, Figure 8) with a model-agnostic heterogeneity index HH. NADT outperforms the no-NCM ablation on 20 of 25 instances (sign test p=0.0041p=0.0041, Wilcoxon p=0.0004p=0.0004), and the per-instance gain correlates positively with HH (Spearman ρ=0.44\rho=0.44, p=0.027p=0.027). The gain is larger where the local distribution is more heterogeneous, supporting neighborhood-adaptive routing as the source of the gains.

5. Clarifications (iZ1a Q1/Q2/Q3, Pu3m W2). Novelty positioning (iZ1a Q1): we re-analyzed existing methods and made NADT's advantages and contributions explicit. Efficiency and complexity (iZ1a Q2, Pu3m W2): we added a model complexity analysis (Appendix I.2) and runtime measurements (Appendix I.1), showing that the model size and inference cost are independent of the training set size, unlike retrieval-based methods. Interpretability (iZ1a Q3): we further explained that the visualization in Section 4.5 shows the prototypes learn class-specific representations and act most strongly near decision boundaries.

All changes above are included in the updated manuscript. We thank the reviewers again for their comments, which substantially improved the paper's theoretical rigor, experimental credibility, and clarity.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.