Proper Multiple Imputation with Generative Random Forests

Random forests have become a default tool for filling in missing values in medical and survey tables, because they handle mixed data types and non-linear relationships without being told what the data distribution looks like. A random forest here is an average of many decision trees, each fit to a resampled copy of the data. The trouble starts when the filled-in table feeds a statistical analysis rather than a prediction. Multiple imputation (MI) is the standard remedy for that setting. It creates several plausible completed tables, runs the analysis on each, and combines the results with Rubin's rules, which add the spread across tables to the usual standard error. Those rules only give honest confidence intervals if each completed table reflects two kinds of uncertainty: the noise in a missing value given the model, and uncertainty about the fitted model itself. The second kind is the one that separates "proper" from "improper" imputation. Current forest-based MI draws many imputations from a single trained forest. That captures the first kind of uncertainty and ignores the second.

We propose to test, and then fix, a specific prediction that follows from this. Forest MI should under-cover exactly where the fitted model is least certain: for variables and missingness patterns where many missing rows are imputed from a leaf that contains few observed rows. Blockwise dropout, high missingness and rare patterns all produce this situation. We will build a proper version of generative-forest MI in two forms. One refits the forest on bootstrap resamples. The other is a cheap variant that keeps the tree structure fixed and redraws leaf-level density parameters under Bayesian-bootstrap weights. We will evaluate both with a coverage criterion that looks inside each missingness pattern, which prior forest-MI work has never measured.

Core Claim

The closest existing work is MissARF (Missing Value Imputation With Adversarial Random Forests— <scp>MissARF</scp>; Missing value imputation with adversarial random forests - MissARF). It builds on adversarial random forests, which are forests trained until real rows and shuffled rows are indistinguishable, so that features become roughly independent within each leaf (Adversarial Random Forests for Density Estimation and Generative Modeling). MissARF imputes by sampling from the one-dimensional densities stored in the leaves that match a row's observed values. It produces $m$ imputations by resampling a single trained forest, and it reports nominal 95% confidence-interval coverage on simulations and on BRFSS 2015. That coverage is marginal, meaning averaged over the whole population. The authors themselves flag highly skewed and high-dimensional settings as open problems.

Our claim has three parts:

  1. Resampling a fixed forest is improper imputation.
  2. Its coverage deficit is predictable from leaf occupancy.
  3. The deficit is invisible in population-averaged coverage but large for pattern-specific estimands and under blockwise missingness.

The mechanism is simple. Take a leaf $\ell$ with $n_\ell$ observed training rows and within-leaf variance $\sigma_\ell^2$. Its estimated density has location uncertainty of order $\sigma_\ell^2/n_\ell$, the usual standard error of a mean. When $k_\ell$ missing rows are imputed from that leaf, their shared error inflates the variance of any average over them. That extra term grows with $k_\ell/n_\ell$, and fixed-forest sampling never adds it to the between-imputation spread. We therefore expect coverage to fall roughly with the imputed-to-observed ratio per leaf. This is a falsifiable dose–response prediction, not merely a request for more careful evaluation.

Research Program

The first component is diagnostic. On semi-synthetic versions of fully observed tables, we impose masks and compute the leaf-occupancy ratio for every imputed cell. We then regress interval miss rates on this ratio. We do this for MissARF and for an ordinary random-forest chained-equations imputer made stochastic by drawing from out-of-bag residuals.

The second component is the fix. We build two versions.

  • Full refit. Each of the $m$ imputations comes from an adversarial forest refit on a nonparametric bootstrap of the incomplete data. This follows the classical recipe for proper imputation and is affordable because adversarial forests train quickly. Adversarial Random Forests for Density Estimation and Generative Modeling reports its sampler, FORGE, running 60 to 100 times faster than deep tabular generators.
  • Leaf reweighting. The trees are kept fixed. For each imputation we draw Dirichlet weights over training rows, which is the Bayesian bootstrap, and recompute the leaf-level densities (the FORDE parameters) under those weights before sampling. This captures uncertainty in the leaf parameters at almost no cost. It ignores uncertainty in the tree structure, and the comparison with full refit measures how much that omission matters.

Both versions use the existing arf/arfpy implementations (arf: Adversarial Random Forests; arfpy: A Python Package for Density Estimation and Generative Modeling with Adversarial Random Forests). They keep MissARF's approach of letting trees split on missingness itself (missingness incorporated in attributes).

The third component is the evaluation lens. Conformal Prediction with Missing Values showed, for prediction intervals, that averaging over the population hides severe under-coverage in particular missingness patterns. That paper supplies our motivation and the concept of mask-conditional validity; we transplant the concept from prediction to inference. We define two targets:

  • Pattern-specific estimands, such as the mean of a variable, or a regression coefficient, within the subpopulation that shares a missingness pattern.
  • Whole-population estimands, such as regression coefficients fit on everyone.

For each target we report Rubin's-rules interval coverage, interval width, and the estimated fraction of missing information.

Two papers constrain the design. Variance estimation after Kernel Ridge Regression Imputation derives analytic variances for smooth kernel imputation of a single response variable. Its analysis does not transfer to the step functions of trees, which is why we resample rather than linearize. Prediction-based Inference in Electronic Health Record (EHR)-linked Biobanks shows that naively plugging in machine-learning predictions yields a "100% Type I error rate … in almost all scenarios," and that no method is safe under missing-not-at-random (MNAR) mechanisms that correlate with prediction error. We therefore restrict our validity claims to missing-at-random (MAR) settings and report MNAR results only as stress tests.

Baselines

Naive references. Complete-case analysis and deterministic single imputation serve as "do nothing" reference points. The deterministic imputers are column mean and the missForest algorithm, with Rubin's rules degenerating to $m=1$. Every method must at least beat these on interval width at comparable coverage. The Type I error inflation of the deterministic imputers is the failure we expect to reproduce.

MissARF as published. This is sampling $m=20$ imputations from one forest (Missing value imputation with adversarial random forests - MissARF). It is the strongest existing forest MI method: the only one in the file with reported valid coverage, namely "gold standard" 95% coverage for confidence intervals on BRFSS and simulations. It is also fast, generating 20 imputations on 10,000 rows in 40 seconds versus over 900 seconds for missForest. Our variants are built on it, which isolates the effect of properness. The variants use the same hyperparameters, the same $m$, and the same masks. Beating it means one of two things. Either our variants restore nominal coverage in patterns or leaf-ratio strata where MissARF falls short of 95%, without widening intervals in strata where MissARF is already valid. Or, if MissARF never falls short anywhere, we report that as a negative result.

Chained-equations MI. We run the MICE implementation from the mice package. It uses predictive mean matching, which imputes by copying observed values from donor rows with similar predictions. We also run a random-forest conditional model inside the chain with a bootstrap per imputation, both with equal numbers of imputations and iterations. This is the incumbent proper-MI approach, and MissARF reports beating predictive mean matching in non-linear settings. Its known weaknesses are a runtime of 285 minutes on SPARK and RMSE that "explodes exponentially" beyond 50% missingness (Benchmarking Machine Learning Missing Data Imputation Methods in Large-Scale Mental Health Survey Databases). We report wall-clock time on identical hardware.

Blockwise reference. On SPARK blockwise masks, MIDAS, a multiple imputer built on denoising autoencoders, is the accuracy reference. It has a reported average RMSE of 0.96, tied with KNN, in the same paper. No reported coverage result was found on Lacuna for any method on SPARK, so coverage there is new measurement.

Key ablation. Comparing fixed-forest, leaf-reweighted and full-refit variants isolates, in turn, the contribution of leaf-parameter uncertainty and of tree-structure uncertainty.

Why not just…?

Why not just bootstrap missForest or MICE with random-forest conditionals, which is already proper? This is a real threat to the method contribution but not to the diagnosis. Proper chained-forest MI exists in principle. Its cost scales with forest refits times iterations times imputations, as the 35- and 285-minute SPARK runtimes illustrate. It also inherits the blockwise collapse reported for chained forests. We run it as a baseline. If it matches our full-refit variant on pattern-specific coverage at similar cost, the contribution reduces to the evaluation protocol and the leaf-occupancy diagnostic, and we will say so.

Why not just increase $m$? More draws from the same fixed forest reduce Monte Carlo noise, but they cannot create model uncertainty the sampler never contains. We test this directly by running fixed-forest MissARF at $m=100$. The prediction is that coverage in high-ratio strata stays below nominal level.

Why not just use conformal or prediction-powered inference instead of MI? Conformal methods (Conformal Prediction with Missing Values; Extending Prediction-Powered Inference through Conformal Prediction) target prediction intervals or bounded estimands. Their guarantees for mask-conditional coverage are proved only when data are missing completely at random (MCAR). The biobank prediction-based estimators assume that only the outcome is missing. None of them handles multivariate missing covariates feeding a standard regression analysis, which is the MI use case. Where the settings overlap, on single-outcome missingness in BRFSS, we include prediction-powered inference with a random-forest predictor as a comparator.

Proposed Experiments

Simulations and sample-size sweep. We use MissARF's simulation designs (normal, binomial and Poisson variables with linear and squared relationships under MCAR, MAR and MNAR) at $n \in \{500, 2000, 10000\}$. We add BRFSS 2015 subsamples at the same sizes. The ground truth is the analysis fit on the complete data.

Real tables. We use BRFSS 2015 subsamples plus the Adult, Default and California tables from RefiDiff: Progressive Refinement Diffusion for Efficient Missing Data Imputation. On these we impose elementwise masks at 10–70% missingness, plus blockwise masks that remove groups of related columns together.

Clinical tables. We use MIMIC-III survival data following Comparison of Imputation Strategies for Incomplete Electronic Health Data. There we also track whether imputation RMSE predicts coverage, testing that paper's finding that reconstruction error and downstream accuracy decouple, this time for inference. Where access permits, we add SPARK blockwise masks.

Three checks decide the proposal:

  1. Dose–response. Fixed-forest coverage must decline with the imputed-to-observed leaf ratio. If it does not, the core claim fails.
  2. Repair without waste. The full-refit variant must restore coverage in the high-ratio strata. It must do so while widening intervals by no more than is needed in low-ratio strata, where fixed-forest sampling should already be valid.
  3. Cost of cheap properness. The leaf-reweighted variant must recover most of full refit's coverage gain at close to fixed-forest runtime. If it recovers little, then tree-structure uncertainty dominates and leaf reweighting is not worth using.