PINE: Pruning Boosted Tree Ensembles with Conformal In-Distribution Prediction Equivalence

Haruki Yajima, Yusuke Matsui

Introduction

Tree ensembles, such as XGBoost and Random Forests, are the workhorses of tabular data machine learning due to their strong predictive performance and interpretability. However, they often suffer from "bloat," growing to include hundreds or thousands of trees. This complexity leads to slow inference times and high memory usage.

Standard pruning methods attempt to resolve this by cutting trees to maintain overall accuracy. Unfortunately, this often sacrifices fidelity—the pruned model may yield different predictions than the original model for the exact same input. In high-stakes domains like medicine or finance, this "prediction churn" is unacceptable. Existing "faithful" pruning methods solve this by guaranteeing the pruned model is mathematically identical to the original across the entire input space. Yet, this strict requirement imposes an "Out-of-Distribution (OOD) tax." It forces the model to remain identical even on logically impossible inputs (e.g., a person with "Preschool education" but "13.5 years of schooling"), severely limiting compression potential.

To address this, researchers introduce PINE (Pruning with In-distribution Equivalence), a novel framework that guarantees the pruned model behaves identically to the original—but only on data it is likely to actually encounter.

Methodology: The PINE Framework

PINE relaxes the requirement for global equivalence, ensuring prediction consistency only within a specific in-distribution (ID) region. The framework operates through several key mechanisms:

  1. Defining the ID Region: PINE utilizes Split Conformal Prediction to define the boundaries of the ID region. It calculates a "plausible score" for inputs using a Chow-Liu Tree, a probabilistic model that captures dependencies between features.
  2. Tunable Guarantees: Users select a miscoverage level parameter, $\alpha$. PINE then calibrates a threshold ensuring that any future "normal" data point has at least a $1-\alpha$ probability of falling into the guaranteed equivalence region.
  3. Iterative Pruning Loop: PINE employs an iterative optimization process. An Oracle—powered by Mixed-Integer Linear Programming (MILP)—searches for "counterexamples" (points within the ID region where the pruned model differs from the original). A Pruner then adjusts the tree weights to resolve these discrepancies until no counterexamples remain in the region.
  4. Efficient MILP Encoding: A major technical contribution of the paper is demonstrating how the probability constraints of the Chow-Liu tree can be efficiently converted into linear constraints manageable by standard solvers like Gurobi.

Experimental Evaluation

The researchers evaluated PINE across 12 public tabular datasets from the UCI repository and OpenML. These datasets span various domains, including social/financial (Adult, FICO, COMPAS), medical/biological (Breast Cancer, Diabetes, Seeds), and technical/physical (Spambase, ELEC2).

Key Findings

  • Superior Compression: By ignoring "zombie" constraints (logical impossibilities in the data), PINE frees up the optimizer to cut more trees. It consistently outperformed faithful baselines like FIPE, increasing the pruning rate by up to 30% while maintaining 100% fidelity on in-distribution test data.
  • Fidelity Over Accuracy: For deployed models, consistency with the original model is often more critical than marginal test accuracy gains. PINE provides a principled method to trade off model size against a strict "consistency budget," maintaining significantly higher fidelity than accuracy-oriented methods.
  • Robust Conformal Calibration: Empirical test coverage almost perfectly matched the theoretical $1-\alpha$ target across all 12 datasets, proving that conformal prediction is a highly robust tool for defining "normality" in tabular data.
  • Computational Efficiency: By restricting the search space to the ID region, the Oracle often finds solutions faster than global methods, particularly as the miscoverage level $\alpha$ increases.

Limitations and Future Work

While PINE offers a substantial leap forward in model compression, it has limitations. The guarantees rely on the "exchangeability" assumption—that future data will resemble the calibration data. If significant distribution shift occurs, the $1-\alpha$ guarantee may degrade. Furthermore, despite being more efficient than global methods, PINE still relies on MILP solvers; as the number of classes or tree depth increases, computational costs can grow significantly. Future research will need to address these scaling challenges, particularly extending the MILP formulation to handle complex multi-class tasks efficiently.

Summary updated

Abstract

Tree ensembles are machine learning models with strong predictive performance and interpretability, and remain widely used for tabular data. Standard pruning methods for tree ensembles typically optimize an accuracy-compression trade-off and may change a subset of predictions, potentially compromising decision consistency. Faithful pruning methods address this issue by preserving prediction equivalence over the entire input space, but this requirement leads to lower compression ratios. We propose **PINE**, a pruning method that provides strong guarantees within an in-distribution region. PINE preserves prediction equivalence within this region and controls the region size using a single parameter $\alpha$ via conformal calibration. Experiments on 12 public tabular datasets show that PINE improves the compression ratio by up to 30% while preserving predictions at a comparable level to existing faithful pruning methods.
BibTeX
@inproceedings{yajima2026pine,
  author = {Haruki Yajima and Yusuke Matsui},
  title = {{PINE: Pruning Boosted Tree Ensembles with Conformal In-Distribution Prediction Equivalence}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=LxAy8UpVUC},
}
Figure