acceptodds
Withdrawn from ICLR 2027

Data-Aware Sensitivity Quantification of Tree Ensembles

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Decision tree ensembles (DTEs) are widely used for classification in domains such as finance and healthcare, motivating the need to formally analyze their behavior. One important property is sensitivity, where changes to a designated subset of input features can alter the model’s prediction. Most existing work studies quali- tative notions of sensitivity, while the few quantitative approaches measure sensi- tivity over the input space without accounting for how likely different inputs are under the underlying data distribution. In this work, we introduce a data-aware notion of quantitative sensitivity. Our input consists of a DTE together with a Bayesian network capturing the distribution of the underlying data. We first iden- tify the regions of the input space that exhibit sensitivity and then weight each region by its probability, so that the measure reflects how likely sensitivity is to occur in practice, and changes with the data distribution even though the model does not. We develop a knowledge-compilation-based algorithm that computes weighted sensitivity within certified error and confidence bounds, and implement it in our tool Weighted-XCount, which scales well beyond direct weighted model counting and shows that weighted and unweighted sensitivity can differ sharply.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Decision Trees Ensembles, Bayesian networks, Sensitivity, Approximate model counting, Algebraic decision diagram, Quantitative Robustness

Reviews

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

This paper proposes a new way to measure sensitivity in decision tree ensembles weighting input regions based on how likely they actually occur in real data, rather than treating all inputs equally. The topic is relevant for trustworthy AI because models often encounter data distributions different from their training data. The authors introduce an approximate algorithm called Weighted-XCount using decision diagrams to compute these weighted sensitivity scores. The experiments are conducted using 8 tabular datasets and considering distinct model sizes. Results shows that the method scales better than an exact counting baseline and concludes that weighting significantly improves result.

Critical strengths
  • Overall paper is well written with a logical structure and easy to follow.

  • The shift from traditional formal verification and sensitivity analysis treats all parts of the input space uniformly (unweighted) to consider a data-aware approach that accounts for the actual likelihood or rarity of different regions under the data distribution. The approach is also theoretically sound.

  • Authors demonstrates their approach are able to solve more instances (1,669) instances compared to the exact baseline's 84. Thus they demonstrate that the algorithmic architecture is a significant performance step-up for symbolic reasoning over tree ensembles.

Critical weaknesses
  • Manuscript also omits main characteristics of the datasets. How many features they have? Do they suffer from class imbalance? Are they noisy? Do they have categorial features? Only continuous? With a few datasets and a more in-depth analysis regarding their characteristics (more importantly the number of features) it is hard to see how they affect results. In addition, the source of the dataset are not explicitly available (also code and data are not available).

  • Furthermore, the evaluation arbitrarily fixes the sensitive feature subset size to 8 features. For several datasets, 8 features represents the entirety of the feature space, making it impossible to evaluate how the approach scales or behaves as dimensionality increases.

  • The paper lacks an analysis of dataset dimensionalities as well as other dataset characteristics and feature-space scaling. With a small amount of datasets used for the benchmark (8 datasets only). To demonstrate the scalability and practical utility of Weighted-XCount, the authors should consider incorporating more diverse and challenging tabular benchmarks such as the ones from the TabZilla suite [1]

  • The paper frames its scope broadly around Decision Tree Ensembles (DTEs) Random Forests. However, its mathematical preliminaries and formulation are focused on additive/boosting methods (lines 133 to 136). This can cause confusions and would be better to use a different, more narrow term if a subcategory is considered.

  • I find the answer to question 2 too strong given the fact it was computed over the 84 instances that were provided with exact count. So a question still remains whether the results are good for these because these are easy to solve. And whether there is a strong bias in this analysis.

  • In my opinion, the paper lacks an more in depth analysis in a controlled scenario prior to the real world dataset analysis using like SCM [2, 3] to synthetically generate datasets with different characteristics and have more control in the simulaitions. IN particular since having the bayesian network must be empirically estimated from the original dataset which introduces estimation errors and noise. Therefore, the paper would benefit greatly from utilizing Structural Causal Models (SCMs) to generate synthetic environments allowing the authors to precisely control feature correlations, noise levels, and specific distribution shifts to rigorously isolate how these variables impact weighted sensitivity.

Refs: [1] When Do Neural Nets Outperform Boosted Trees on Tabular Data? [2] Accurate predictions on small data with a tabular foundation model [3] Elements of causal inference: foundations and learning algorithms.

Questions for authors

My main concern about the manuscript are regarding the experimental protocol which several design decisions are not clear, important details (dataset configurations) as well as more ablations were missing and whether the answers of some RQ (in particular #2) is well fundamental or could be biased (see critical weakness section for more details). So far, due to these problems my recommendation would be rejection. I would like the authors to provide a in-depth answer to the following points during the rebuttal and I am willing to revise my score if my concerns are properly addressed:

  1. Can the authors provide details on the total feature dimensionality of each benchmark dataset, and clarify how Weighted-XCount behaves when the number of sensitive features varies relative to the total feature space?

  2. Given the complexities of learning accurate Bayesian networks on noisy real-world data, have the authors considered evaluating their framework on synthetic data generated via Structural Causal Models (SCMs) ?

  3. Can you justify why 8 dimension was used? Or run with multiple values to see how it impact the conclusions taken and the sensitivity of this choice regarding different dimensionalities? This is important in particular since at least 50% of the dataset used have dimensionality <= 8 which makes the experiments a bit strange due to the fact not all datasets had the same amount of instances.

  4. Can you add main dataset characteristics (like number of instances features, types of features, etc) and also analyze the impact of such characteristics in the method's performance?

  5. Regarding RQ2, the relative error bounds are evaluated exclusively on the 84 instances where the exact baseline successfully finished. Can the authors provide empirical evidence or proxy evaluations showing how the estimation error behaves on unsolved or harder instances where exact counts are unavailable?

  6. Given that the current suite relies on datasets without source citations, have the authors considered evaluating their framework on more challenging, tabular benchmarks such as TabZilla?

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

The paper extends the XCount framework by incorporating Bayesian networks (BNs) to estimate probability-weighted sensitive regions in decision tree ensembles. The proposed Weighted-XCount provides approximation guarantees and demonstrates scalability compared with exact weighted counting.

Critical strengths
  1. Incorporating data distributions allows the method to account for differences in the importance of sensitive regions.
  2. The method provides theoretical guarantees and demonstrates good scalability compared with exact weighted counting.
  3. Combining Bayesian networks with symbolic counting offers a practical approach to distribution-aware sensitivity analysis.
Critical weaknesses
  1. The methodological novelty is limited, as the core representations and counting techniques are largely inherited from Naik et al. (2026). The main contributions lie in probability weighting and its associated theoretical extensions.
  2. The evaluation lacks comparisons with approximate weighted-counting methods, making the computational advantages less convincing.
  3. The distribution-shift experiments rely on artificially removing data from sensitive regions, which limits their realism and provides limited evidence beyond expected behavior.
  4. The study focuses on a specific sensitivity metric and model class, leaving its broader relevance to the machine learning community unclear.
Questions for authors
  1. How does Algorithm 7 preserve the dependencies encoded by the BN when sampling BDD assignments and sensitive-feature masks separately?
  2. How does using Hamming distance with d=1d=1 reflect perturbation magnitudes in the original feature space, and does this affect comparisons across features?
  3. What model or BN characteristics explain why Weighted-XCount fails to complete 885 instances?
Reviewer_sqtVOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper argues that existing quantitative sensitivity verification of decision tree ensembles (DTE) can overestimate the sensitivity of protected features because the techniques disregard the joint probability of features, and proposes an algorithm that more appropriately weights sensitive pairs according to their probability, as the decision variable should take the expected frequency of sensitivity into account when judging a DTE.

The main contribution is an approximate weighted counting algorithm, which is significantly faster than its exact counterpart at the price of being approximate. It takes a DTE and a Bayesian network over the input features and hyperparameters for the operationalization of sensitivity as pairs of protected features that differ more than a threshold only based on protected features, while the other features are held fixed.

Critical strengths
  • The argument for data-awareness for quantified sensitivity is strong, thus the motivation for this paper is clear. (I personally cannot judge the motivation of quantitative sensitivity itself due to lack of familiarity with such fairness auditing.)
  • Significant speed up compared to exact (weighted) procedure while at the same time retaining provable guarantees (in a epsilon delta formulation) that are also validated experimentally lead to a very clear applicability jump of this kind of quantitative sensitivity validation.
Critical weaknesses
  • The proposed measure C_w is computed relative to a Bayesian network obtained from pgmpy with “standard learning algorithms” which is should be specified more precisely for the presented experiments and it would further be good to quantify the uncertainty of C_w from estimating the network (e.g. via bootstraping) and, insofar as the structure learning is fragile, assess error that network misspecification leads to.
  • It is not clear to me that RQ3 is answered robustly by the presented evidence. The given answer at the end of section 5 seems to be based on just one dataset and model, which is very little compared to RQ1 and 2, and the considered domain shift is artificial and specific to data-aware trimming, as opposed to a more general domain shift that the introduction motivates.
Questions for authors

Is there motivation for an aggregate sensitivity measure outside of fairness? The experiments do not seem to use protected features that are relevant to fairness. I lack the experience in fairness applications to judge whether the fact that experiments select protected features at random threats the relevance of the results (it might be fine as is), but nonetheless to me a more obviously fairness shaped experiment/dataset/case-study would benefit the paper.

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

Related papers

Discussion (0)

Sign in to comment.