IIT Bombay's XCount Finally Measures AI Bias in Credit and Medical Models
XCount uses algebraic decision diagrams and probabilistic counting to measure how much of a tree ensemble's input space is vulnerable to sensitive feature flips — with formal guarantees.
Takeaways
- XCount is the first tool to count how many input regions of a decision tree ensemble are vulnerable to sensitive feature changes, with certified (1±ε, 1−δ) guarantees.
- The approach encodes each tree as an Algebraic Decision Diagram (ADD), decomposes the counting problem into subproblems per bitmask pair, then merges results using a Poisson-sampling union estimator.
- On 3,194 benchmarks across 10 datasets, XCount solved 1,552 instances — 2× more than the monolithic ADD baseline and 33% more than the best model counter (Ganak), with a mean relative error of 0.1%.
- The tool validates that L1 regularization reduces sensitivity: higher regularization parameters consistently produce fewer sensitive input regions, even when predictive accuracy is unchanged.
- Scalability degrades beyond ~400 decision nodes per ensemble; completion rates drop below 50% for large ensembles, and very low gap thresholds slow performance significantly.
- Code is implemented in C++ with CUDD; the paper and tool are available on arXiv from IIT Bombay and University of Toronto.
Decision tree ensembles , the XGBoost, LightGBM, and random forest models that power credit scoring, medical diagnosis, and fraud detection , are widely trusted precisely because they feel interpretable. But a nagging question has gone largely unanswered: how much of a model's input space is actually vulnerable to flipping a protected feature like race, age, or gender and getting a different prediction? A new paper from IIT Bombay and the University of Toronto introduces XCount, the first tool that can answer that question at scale, with certified accuracy.
The gap between "does it exist" and "how much"
Sensitivity is closely related to individual fairness or causal discrimination, since any sensitive pair , two inputs that differ only on protected features but receive different predictions , is a witness to unfairness when sensitive features are seen as protected attributes. Prior work could find one such pair, or prove none exists. This problem is quite different from the well-studied local robustness problem: while local robustness can be solved by searching around the neighborhood of a given input, sensitivity requires searching across the entire input space.
The trouble is that finding a single sensitive pair is NP-hard, and counting them is even harder , it sits in the complexity class #P, the counting analog of NP. Recent work has considered quantitative notions of robustness for neural networks, but to the best of the authors' knowledge, no prior work deals with quantitative versions of sensitivity or fairness in decision tree ensembles. XCount fills that gap.
What "sensitivity" means, precisely
The paper formalizes the problem by splitting features into sensitive (protected attributes like race or gender) and non-sensitive (everything else). A model is sensitive if there exist two inputs that are identical on non-sensitive features, differ only slightly on sensitive ones (within a Hamming distance d), yet receive predictions that diverge by more than a gap threshold