acceptodds
Under review as a conference paper at ICLR 2027

Beyond Feature Importance: Hierarchical Explanations of Feature Selection

Abstract

An emerging family of explainable AI methods aims to identify, for each input, a minimal subset of observed feature values sufficient for predicting the output of a black box. These instance-wise feature-selection methods can reveal which features are important for a prediction. In this work, we go one step further and ask: why were these features selected rather than others? We introduce a recursive framework for hierarchical explanations of feature selection. At the first order, a sufficient-subset explainer produces an instance-wise binary feature-selection mask for explaining the original black-box output. Each subsequent order explains the selection mask produced at the previous order. Repeating this process yields an ordered hierarchy in which each level explains why the features at the previous level were selected. We develop a training procedure for learning these hierarchies. On nonlinear mechanisms generated by decision trees, our method recovers the underlying decision-tree structure substantially more accurately than conventional decision-tree baselines, while maintaining high predictive fidelity at every order. Our framework moves beyond identifying what features are selected toward explaining why they are selected.

Primary area:
interpretability and explainable AI
Keywords:
Explainable AI, Sufficient-subset explanations, Instance-wise feature selection

Reviews

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

The paper proposes HEX, which recursively explains feature-selection masks to identify what determines the choice of features for each input. I view its central contribution as distinguishing features needed for prediction from those governing which predictive features are selected. The method builds on Hide&Seek and presents nesting and feature-block recovery results under idealized assumptions. Validation uses five synthetic mechanisms with independent inputs and CoverType covariates. The results show strong recovery of ordered feature structure with independent inputs, while performance on correlated covariates is more sensitive to the training procedure.

Critical strengths
  • The distinction between features needed for prediction and features governing their selection conceptually useful. Recursively explaining selection masks makes this distinction concrete and helps reveal how a model changes its predictive mechanism across inputs.
  • The experiments explicitly evaluate ordered feature structure. HEX-M’s reported 97.5–99.1% exact-path recovery on Models 1–3 with independent inputs provides encouraging evidence that this hierarchy can recover meaningful structure in controlled settings.
Critical weaknesses
  1. My main concern is the gap between predictive fidelity and the sufficiency of the returned masks. Algorithm 2 trains the predictor using zig=gi(x)⊙x+(1−gi(x))⊙x~z_i^g=g_i(x)\odot x+(1-g_i(x))\odot\tilde x, whereas the hierarchy uses mi(x)=1{gi(x)≥0.5}m_i(x)=\mathbf 1\{g_i(x)\ge 0.5\}. If zimz_i^m denotes the corresponding input constructed with the hard mask, then zig−zim=(gi(x)−mi(x))⊙(x−x~)z_i^g-z_i^m=(g_i(x)-m_i(x))\odot(x-\tilde x). Thus, a feature with gate value 0.490.49 still contributes to the predictor’s input despite being absent from the reported explanation. A small soft-gate prediction loss does not, by itself, establish the stated sufficiency condition pBi(Y∣XSi=xSi)=pBi(Y∣X=x)p_{B_i}(Y\mid X_{S_i}=x_{S_i}) = p_{B_i}(Y\mid X=x). This distinction matters because Bi+1(x)=mi(x)B_{i+1}(x)=m_i(x): later levels can faithfully explain an earlier selector’s thresholding artifacts. The structural results provide evidence on the tested mechanisms, but Tables 5–6 report predictive fidelity only at the first order. I would need per-order soft-versus-hard fidelity, threshold sensitivity, and direct sufficiency checks to trust the interpretation of the full hierarchy.
  2. I find the evidence for structural superiority difficult to separate from differences in representation. The generating mechanisms have the form B(x)=hr(x)(x)B(x)=h_{r(x)}(x), with potentially multivariate routing r(x)r(x) and nonlinear leaf functions hrh_r. Conventional regression trees instead approximate the output through partitions, B^(x)=∑ℓcℓ 1{x∈Rℓ}\widehat B(x)=\sum_{\ell}c_\ell\,\mathbf 1\{x\in R_\ell\}. Approximating a leaf function such as h(x)=x1x2h(x)=x_1x_2 requires additional splits, so an accurate predictor need not resemble the generating tree structurally. Although OBA can merge consecutive feature blocks, global tree-edit distance remains sensitive to this mismatch. Averaging structural distances over constituent trees is also questionable for boosting, whose components model corrections to an ensemble rather than the complete mechanism individually. Consequently, poor baseline structural scores do not convincingly establish HEX’s advantage. Comparisons with multivariate splits and flexible leaf models, together with ablations of HEX-M’s training stages, would make the empirical contribution substantially clearer.
Questions for authors
  1. Are the fidelity results in Tables 5–6 computed using soft gates gig_i or hard masks mim_i? What fidelity is obtained with hard masks at each hierarchy level, measured against that level’s target BiB_i? This distinction materially affects my confidence in the returned explanations.
  2. How are baseline leaves labelled, and how does tree-edit distance account for additional splits needed to approximate nonlinear leaf functions? What justifies averaging constituent-tree structural distances for boosting, where individual trees do not represent the complete predictive mechanism?
  3. Are ablations available that isolate pseudo-mask pre-training and regime-support refinement while keeping the HEX recursion and other settings fixed? These would help establish which components drive the substantial improvement of HEX-M over HEX-S.
1 comment
AuthorsOpenReview ↗

Response to Reviewer pSdw

Thank you for the careful review and for recognizing the central distinction made by HEX. We have substantially strengthened the revision in direct response to the three main concerns, which are (1) quantifying the role of thresholded masking, (2) comparisons with multivariate splits and flexible leaf models, (3) ablations of HEX-M’s training stages.

1. Hard-mask fidelity, per-order evaluation, and threshold sensitivity

We added a new appendix section, “Hard-mask fidelity and threshold sensitivity,” that evaluates every saved HEX-M order using both its continuous soft gate and its thresholded hard mask.

At order one, both versions are evaluated against the original model output. At higher orders, both are evaluated against that order’s fixed target: the preceding reported mask at the default threshold.

The new results report:

  • per-order soft-versus-hard fidelity at the reported threshold;
  • hard-mask threshold sensitivity from 0.1 to 0.9;
  • selected-mask mass at each threshold; and
  • higher-order exact-mask fidelity under hard masking.

Soft and hard fidelity are nearly identical on independent inputs; correlated CoverType features reveal a few harder higher-order cases.

2. Comparisons with multivariate splits and flexible leaf models

We added NNRT (Bertsimas, Dunn, and Wang, 2021) as a new baseline in the appendix. NNRT is a decision-tree method with multivariate splits and flexible polynomial leaf models, directly addressing the reviewer’s requested comparison.

On the same CoverType experiments, we report NNRT beside HEX-S and HEX-M for predictive fidelity, OBA/F1, exact-path recovery, and tree-edit distance. NNRT achieves strong predictive fidelity, but its recovered paths and trees remain much less similar to the true generating mechanism than those returned by HEX.

3. Ablations of HEX-M’s training stages

We added a controlled ablation that removes, one at a time, selector pseudo-mask pretraining and regime-support refinement, while keeping the data, architecture, recursion, and all other training stages fixed.

Removing pseudo-mask pretraining causes structural recovery to collapse on all five models. Removing only regime-support refinement causes a smaller but consistent decline in OBA, aligned F1, and exact-path recovery. Thus, pseudo-mask pretraining provides the initial selector, while refinement improves the stability of the recovered hierarchy.

Other points

For conventional trees, each internal node is labelled by its split feature and each leaf by the empty set, because it returns a constant. For NNRT, routing nodes and leaves are labelled by the variables occurring in their fitted routing and polynomial leaf formulas.

We distinguish predictive fidelity, reported in Appendix D, from recovery of the true generating decision-tree structure, reported in Tables 3 and 4. These results quantify how far the trees generated by axis-aligned decision-tree methods are from the true tree. The new results show that NNRT, whose decision nodes are multivariate and whose leaves are flexible polynomial models, also performs poorly in structural recovery.

For boosting, we average constituent-tree distances because every constituent contributes to the ensemble prediction. Thus, for a given input, if the ensemble reconstructs the true generating decision path, each contributing tree should use a subset of the decision variables on that path. We hypothesize that this similarity is reflected in the expected constituent-tree distance. In practice, the resulting expected component-level distances are only slightly closer to the true decision tree than CART and NNRT. The only methods that completely or partly recover the true generating structure are the proposed HEX-S and HEX-M.

Reviewer_4cy3OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses an interesting problem in the field of XAI by proposing an approach that goes beyond state-of-the-art methods, which usually identifies which features are relevant to a prediction. The authors introduce HEX a hierarchical (recursive) framework that aims to explain why particular features are selected at different levels of a decision mechanism. The method is presented as a generally applicable approach, but the experimental evaluation is limited to 5 predefined decision-tree-based mechanisms. These mechanisms are evaluated using synthetic data as well as real-world input features from one dataset. The results on synthetic data show that HEX can recover the hierarchical structure of the investigated decision mechanism more accurately than traditional decision tree-based methods. The results on real-world data are more heterogeneous.

Critical strengths

Overall, the idea of explaining not only which features are important for a decision but also why these features are important is essential from a human user's perspective. Providing explanations at different levels of a decision mechanism is not entirely novel, e.g., attribution-based methods have been used to explain different layers of neural networks in order to identify which input regions the model considers relevant at each level. The proposed approach is interesting because it formulates the problem recursively, identifying the features responsible for determining the feature selection at the preceding level. This allows to uncover the hierarchical structure of the underlying decision mechanism.

Critical weaknesses

It remains unclear if the proposed approach is feasible for complex real-world decision mechanisms (e.g., deep neural networks). Even for the 5 relatively simple synthetic mechanisms, a certain level of engineering effort was required to achieve a small set of relevant explanations. For more complex decision mechanisms, the number of explanation paths and rules is typically much higher, which raises concerns regarding the scalability of the approach. Furthermore, w.r.t. the aforementioned engineering effort, the impact of pruning on the fidelity and completeness of the recovered decision structure has not been systematically evaluated.

Questions for authors

Major issues:

  • In practice, a learned mask can contain errors, and those errors can affect later orders.” Even though the theoretical framework is sound, I agree with the authors that in practice, the explanation masks may contain artifacts that propagate through subsequent levels of explanations due to the recursive nature of the approach. In addition, there are a couple of assumptions that the approach is making, that wouldn’t hold for complex real-world decision mechanisms. An empirical evaluation on real-world decision mechanisms and datasets is therefore essential to assess the robustness of HEX.
  • The threshold of 80% of a node’s path mass used for pruning seems arbitrary. The authors should investigate different thresholds and their impact on the recovered decision structure. The paper lacks empirical evidence motivating the proposed pruning procedure (e.g. “Paths assigned to the other, unlikely regimes are pruned.”
  • In general, ablation/sensitivity studies for hyper-parameters are missing.

Minor issues:

  • The authors should consider using terminology other than "black box" throughout the paper as it is unspecific and oversimplifying (there is not just black and white box).
  • Related approaches to instance-wise feature selection and other attention mechanisms, are not discussed (e.g. Baumhauer et al., 2022). Exploring such methods could be interesting from a scalability perspective, particularly by introducing differentiable attention bottlenecks into the decision mechanism and applying HEX to these intermediate representations.
  • The table captions could be more specific about the data used to obtain the results.
1 comment

Thank you for the careful review and for recognizing that HEX addresses an interesting problem beyond existing explainability methods. We also thank the reviewer for suggesting ablation and hyperparameter-sensitivity studies; these additions have strengthened the empirical analysis.

Scope and contribution

To our knowledge, HEX is the first use of instance-wise feature selection to reconstruct a target model’s generating decision-tree structure from observed inputs and outputs. We do not claim that the present method can reconstruct an arbitrarily complex system such as a deep neural network. Rather, the paper establishes a new use of instancewise feature-selection (IWFS): recursively explaining selected feature sets can reveal the decision variables that determine which local predictive rule applies.

Even on the controlled mechanisms studied here, none of the compared alternatives recovers the generating structure as successfully as HEX-S or HEX-M. This establishes a new explanatory capability of IWFS, even when the recovered hierarchy contains only a small number of levels.

Engineering, sensitivity, and path-mass threshold

We respectfully disagree that the results require extensive model-specific engineering for the simple mechanisms. HEX-S uses the original single-phase Hide&Seek training procedure. On most models, it already substantially improves structural recovery over the conventional baselines.

HEX-M that further improves the results through its multi-phase training procedure, is not very sensitive to the hyperparameters either. Appendix I evaluates hard-mask thresholds from 0.1 to 0.9, and Appendix J evaluates path-mass pruning thresholds from 0.5 to 0.9. On independent inputs, HEX-M is stable over broad ranges of both choices. With correlated CoverType covariates, sensitivity is greater, but remains moderate.

Real-world decision mechanisms

We agree that evaluation on real-world target mechanisms is important. Structural recovery, however, requires access to the true instance-wise decision structure, which is generally unavailable for deployed systems. To our knowledge, there is no realistic benchmark that exposes this structure.

We therefore use the semi-synthetic strategy adopted in related IWFS work, including INVASE and Hide&Seek: the target mechanisms remain known, while the inputs follow the standardized real-world CoverType covariate distribution. This tests the effect of correlated, realistic covariates while preserving the ground truth required for structural evaluation.

Error propagation through levels

Error propagation is a genuine limitation of a recursive procedure, and the paper identifies it as a reason not to claim recovery of long and complex hierarchies. Appendix I now measures hard-mask fidelity at every available order, rather than only first-order fidelity. It shows that hard and soft masks agree closely on independent inputs, while later orders are more difficult with correlated CoverType covariates.

Even when HEX reliably recovers only one or two decision layers, it identifies variables governing feature selection, rather than only variables supporting a prediction. Our experiments show that existing IWFS methods and all tested decision-tree methods, including NNRT with multivariate routing and flexible polynomial leaves, do not recover this structure.

Ablation and sensitivity studies

Appendix G contains a controlled ablation of HEX-M. It removes pseudo-mask pretraining and regime-support refinement separately, while keeping the data, architecture, recursion, and remaining training stages fixed.

Removing pseudo-mask pretraining severely degrades structural recovery on every mechanism. Removing regime-support refinement causes a smaller but consistent decline in OBA, aligned F1, and exact-path recovery. Appendices I and J provide the complementary sensitivity analyses for hard-mask thresholding and path-mass pruning.

Minor revisions

We replaced “black box” with “target model” throughout the paper. We also added Baumhauer et al. (2022) on bounded logit attention. BLA learns a variable-size attention selection at one representation level, whereas HEX recursively explains the selected set itself. Finally, all result captions identify whether they use synthetic mechanisms or CoverType covariates.

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

This paper addresses the problem of generating local explanations for the outputs of machine learning models. Instance-wise feature explainers (IWFS) are methods that reveal which features are ``important'' (sufficient) for the prediction of a model ff on a particular instance xx. This paper tries to investigate why an instance-wise explainer returns a particular set of features. To do so, the authors introduce an iterative algorithm that repeatedly explains the previous explanation. By using this approach, their method, HEX, is able to reveal an ordered hierarchy, where at each level of the algorithm, we get an explanation as to why the features in the previous explanation were selected. When the data is generated by a decision tree, HEX can recover the structure of the tree substantially better than previous algorithms.

The main contributions of this paper are the following:

  1. A new algorithm, HEX. HEX is an iterative algorithm that explains why a set of features is selected by an IWFS.
  2. The authors provide a theoretical guarantee for HEX, demonstrating when it provides a nested set of explanations.
Critical strengths

Strength 1: Clarity

This paper was very easy to follow. The problem was well motivated with an intuitive example early on. This was effective because, as a reader, I had a clear picture of the problem and could keep returning to the example (as the authors do). I also think the figures made it easy to follow what HEX does as an algorithm. Overall, I did not have much of an issue following the flow of ideas.

Critical weaknesses

Weakness 1: Vague definition of necessity

Much of the paper revolves around the idea of sufficient subsets. The definition of a sufficient subset is well-established in previous literature (although the authors do not cite the various works that have introduced this idea already, e.g. [1-7]). However, in Section 2.1, the authors also introduce "necessary" features. They state, "After observing xS(x)x_{S(x)}, the remaining features cannot change the black-box output. We call the retained indices necessary." This is very confusing. By definition, xS(x)x_{S(x)} is sufficient (and why it's sufficient makes sense). Why are they necessary? There have been numerous works that introduce what a necessary subset of features is [8-9]. By those standard definitions, xS(x)x_{S(x)} need not be necessary. Later, on page 5, the authors state, "a necessary subset is a sufficient set from which no selected features can be removed." I do not agree with this statement. Other works in the logic, probability, causality, and interpretability literature have introduced notions of necessity [3, 7, 8, 9]. The authors' definitions of necessity do not seem to agree with these definitions. Note that these others technically provide different definitions as well, but they encapsulate the right idea: a necessary subset is one, that, when removed, you cannot reconstruct the original prediction f(x) [see 3 for a more precise characterization]. Given that the theorem seems to rely on the authors' notion of necessity, which to me is not necessarily a valid definition, I am a bit skeptical of the theorem statement.

Weakness 1: Lack of cited work There is tons of literature on local sufficient explanations that the authors do not mention. All the citations below are key works in this area that I believe should be discussed. If the authors do not think they should be discussed, I would like an explanation as to why.

[1] Eric Wang, Pasha Khosravi, and Guy Van den Broeck. Probabilistic sufficient explanations. 2021. [2] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High-precision model-agnostic explanations. In Proceedings of the AAAI conference on artificial intelligence, 2018. [3] Beepul Bharti, Paul Yi, Jeremias Sulam. Sufficient and Necessary Explanations (and What Lies in Between). Conference on Parsimony and Learning (2025) [4] Alexey Ignatiev, Nina Narodytska, Nicholas Asher, and Joao Marques-Silva. From contrastive to abductive explanations and back again. In the International Conference of the Italian Association for Artificial Intelligence, 2020. [5] Adnan Darwiche and Auguste Hirth. On the reasons behind decisions. 2020 [6] Adnan Darwiche and Chunxi Ji. On the computation of necessary and sufficient explanations. In Proceedings of the AAAI Conference on Artificial Intelligence. 2022. [7] Ryan Pilgrim, Beepul Bharti, Kyle Poe, Rene Vidal, and Jeremias Sulam. Let Me Explain, Again: Multiplicity in Local Sufficient Explanations. 2026. [8] Amit Dhurandhar, Pin-Yu Chen, Ronny Luss, Chun-ChenTu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. Advances in neural information processing systems, [9] Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. On counterfactual explanations under predictive multiplicity. In Conference on Uncertainty in Artificial Intelligence. [10] Ronny Luss and Amit Dhurandhar. When Stability Meets Sufficiency: Informative Explanations that do not Overwhelm. 2024

Questions for authors
  1. Could the authors please elaborate on their notion of necessary features, why they believe this is a correct definition vs. other established definitions?

  2. Could the authors highlight in which ways their work differs from [1,2]? These two works seem to be highly relevant to the problem the authors discuss in their work. In particular, the abstract of [2] states, "We propose a novel method called Path-Sufficient Explanations Method (PSEM) that outputs a sequence of stable and sufficient explanations for a given input of strictly decreasing size (or value) -- from original input to a minimally sufficient explanation -- which can be thought to trace the local boundary of the model in a stable manner, thus providing better intuition about the local model behavior for the specific input."

This is similar to what HEX is trying to do as well right?

1 comment

Thank you for your careful review, your positive comments on the clarity of the paper, and for pointing out relevant literature. We appreciate your feedback and have revised the manuscript to address your concerns.

1. Definition of necessary features

We agree that our use of the term "necessary feature set" was imprecise and confusing. Our intended assumption is simple: at each order and for each input, there is exactly one sufficient feature set from which no feature can be removed without losing sufficiency. This is the assumption used in Proposition 3.1 and its proof.

We have revised Sections 2.1 and 3 and Appendix A to state this condition directly, without using the term "necessary". This clarification does not change the mathematical assumption or the nesting result.

2. Related literature

Thank you for highlighting these references. We agree that several of them are relevant and should be discussed.

We have expanded the introduction to acknowledge prior work on probabilistic sufficient explanations (Wang et al., 2021), logical sufficient and contrastive explanations (Ignatiev et al., 2020/2021; Darwiche and Hirth, 2020; Darwiche and Ji, 2022), sufficiency and necessity (Bharti et al., 2025), and multiplicity of sufficient explanations (Pilgrim et al., 2026). We have also added Dhurandhar et al. (2018). Anchors (Ribeiro et al., 2018) was already cited in the original manuscript. Pawelczyk et al. primarily address counterfactual explanations under predictive multiplicity across models, which is less directly related to our setting.

3. Difference between HEX and PSEM

We believe there is an important distinction between HEX and PSEM (Luss and Dhurandhar, 2024). We note that the PSEM abstract quoted in the review corresponds to reference [10], rather than [2], which is Anchors.

PSEM produces a sequence of progressively smaller explanations while preserving the original model classification. In contrast, HEX changes the prediction target at each level: the next explainer predicts the feature-selection mask produced by the preceding explainer, $ \mathcal B_{i+1}(\mathbf x)=\mathbf m_i(\mathbf x). $

Consequently, a higher-order HEX explanation does not need to be sufficient for the original prediction. Instead, it identifies the features that determine why the preceding feature set was selected.

For example, in our switching example, the first-order explanation is X1,X2\\{X_1, X_2\\} when X1<0X_1<0, whereas the second-order explanation is X1\\{X_1\\}. The second set cannot predict the original output X2X_2, but it explains why X2X_2, rather than X3X_3, was selected.

Thus, although both approaches produce sequences of feature subsets, they address different questions. PSEM studies how a prediction can be preserved as features are progressively removed. HEX studies what determines the selection of features at each preceding level. We have added this distinction explicitly to the introduction.

We have uploaded a revised PDF incorporating these changes, with the modifications addressing your comments highlighted in blue for easy identification.

Thank you again for your constructive feedback. We hope these clarifications address your concerns, and we would welcome any further discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.