Beyond Imputation: Mask-Adaptive Conformal Prediction via Tree Embeddings on General Missing Data Mechanisms

Jiarong Fan, Juhyun Park, Thi Phuong Thuy Vo, Nicolas J-b. BrunelarXiv 2026 · arXiv

Uncertainty quantification is a cornerstone of reliable machine learning, especially in high-stakes fields like medicine or autonomous driving. Conformal Prediction (CP) has emerged as a favorite tool because it provides "distribution-free" guarantees: if you ask for 90% coverage, CP gives you a prediction interval that contains the true value at least 90% of the time.

However, there’s a catch. Standard CP usually only guarantees marginal coverage—the average performance across the whole dataset. In the real world, data is often missing. If your model is 90% accurate on average but fails completely whenever a specific sensor is offline, that’s a major safety risk. This paper, recently published by researchers at Université Paris-Saclay and Capgemini Invent, tackles this "mask-conditional" coverage gap without relying on the traditional (and often problematic) crutch of data imputation.

What Problem Does This Paper Address?

When data is missing, it creates distributional heterogeneity. The relationship between observed features and the target variable can shift dramatically depending on which features are absent.

The standard industry response is to "impute" (fill in) the missing values. But the authors argue that imputation is a double-edged sword:

  1. It’s expensive: Imputation adds significant computational overhead.
  2. It destroys information: The fact that a value is missing (the "mask") is often a signal in itself. Imputation hides this pattern, making it harder for CP to adapt its uncertainty intervals to specific missingness scenarios.

Existing CP methods that try to handle missingness often assume the data is Missing Completely at Random (MCAR), which is rarely true in practice. This paper seeks a robust pipeline that provides valid, informative prediction sets under general missingness mechanisms (MAR and MNAR) without ever filling in a single NA.

Methods

The authors propose a framework that is adaptive to missingness patterns. Instead of fixing the data, they fix the feature representation.

  1. Tree Embeddings: They use tree ensembles (like LightGBM) to handle missing values natively. Trees naturally split data based on whether a value is present or absent. The ensemble induces a deterministic "tree embedding"—essentially a high-dimensional map of where a data point lands in the forest.
  2. Mask Augmentation: They augment this tree embedding with the raw binary missingness mask ($M$). This ensures the model explicitly "knows" what is missing.
  3. Regularized Quantile Learning: They learn a score threshold function by solving a regularized optimization problem using a pinball loss. By carefully choosing the penalty matrix ($J$), they can target different levels of validity:
  4. Coordinate-wise validity: Ensuring coverage when a specific feature $j$ is missing.
  5. Observed-mask validity: Ensuring coverage for every specific pattern seen in the calibration set.
  6. Approximate conditional validity: Providing theoretical bounds for general, unseen missingness patterns.

To make this computationally feasible, they derive a dual formulation that allows them to find the prediction intervals efficiently using standard solvers.

Datasets

The researchers evaluated their method across a range of environments:

  • Synthetic Gaussian Data: Controlled environments to test MCAR, MAR, and a "Pattern Mixture" (PMIX) setting where the covariate distribution shifts linearly with the mask.
  • Concrete Compressive Strength: A semi-synthetic benchmark where they manually introduced missingness into a real-world dataset of 8 continuous features.
  • MIMIC-IV Length-of-Stay (LOS): A high-dimensional (300 features) real-world medical dataset. This represents a "wild" missingness scenario where measurements are irregular and sparse.

Key Insights and Ideas

  • Trees are "Missingness-Aware": Tree-based models are uniquely suited for this task because their splitting logic inherently accounts for the presence or absence of data. As shown in Figure 3, using tree embeddings is critical; without them (using only the mask), coverage drops significantly below the target.
  • Imputation is Not Required: By preserving the mask and using embeddings, the model can learn "mask-specific" uncertainty. This avoids the task-dependent overhead and potential biases introduced by imputation.
  • Adaptivity vs. Conservatism: A major challenge in conditional CP is that being too specific can lead to intervals that are so wide they are useless. This framework allows for a "smooth" trade-off, providing tight intervals for common masks and becoming more conservative only for rare, "difficult" patterns.

Key Results

The proposed method, "Ours," consistently outperformed baselines in maintaining the target 90% coverage while keeping intervals informative.

  • Subgroup Reliability: In coordinate-wise tests (Table 1), the method maintained coverage near the 90% nominal level across all missingness mechanisms.
Table 1: Coordinate-wise coverage estimates with d = 6 and nominal level 90%. Entries are mean percentage coverage ± 95% CI half-width over 10 seeds.
  • Handling Heterogeneity: In the PMIX setting (where missingness strongly correlates with the data distribution), the method significantly reduced shortfall risk (the amount of undercoverage) compared to standard CP and other advanced baselines like MDA-Exact or Weighted-CP.
Figure 1: Empirical shortfall risk and average interval length across missingness mechanisms. Our method is competitive with the baselines on MCAR/MAR and gives a stronger coverage–length trade-off on the mask-heterogeneous PMIX setting. Here ntree = 256.
  • Rare Mask Performance: As seen in Figure 2, even for masks that appeared fewer than 10 times in the calibration set, the empirical coverage remained centered around the 0.9 target.
Figure 2: Validity across observed masks. The scatter plot shows the empirical coverage on 100 stratified test points for every mask pattern that exists in the calibration set.

Limitations and Future Work

While powerful, the method has some trade-offs:

  • Computational Cost: The exact dual optimization path is slower than simple CP baselines, particularly as the number of trees in the embedding grows. However, it remains much more feasible than "Nested" CP methods in high dimensions.
  • Regime-Specific Theory: The theoretical guarantees for general, unseen masks are approximate and depend on the quality of the tree representation and certain regularity conditions.
  • Future Directions: The authors suggest extending this work to achieve even richer $X$-conditional validity (beyond just the mask) and exploring more complex embedding models.

In summary, this paper provides a robust path forward for uncertainty quantification in the messy, "holey" datasets common in real-world applications, proving that sometimes, the best way to handle missing data is to embrace the gaps rather than trying to fill them.

Summary updated

Abstract

Conformal prediction (CP) provides a distribution-free framework for uncertainty quantification with finite-sample marginal coverage guarantees. Yet, missing values introduce distributional heterogeneity, where marginal coverage can hide systematic undercoverage for certain missingness patterns. At the same time, existing methods based on distances or smoothness require a continuous representation of partially observed covariates. Although imputation restores continuity, it obscures the missingness patterns and introduces task-dependent overhead. We develop a new CP framework that is \emph{adaptive to missingness patterns}, without imputing covariates. We rely on data augmentation by feature embedding that accounts for missingness. Our framework represents each input with missing values by a tree embedding together with its raw missingness mask, and then learns a regularized quantile score function. Varying the choices for the penalty function and the augmentation enables us to characterize three practically relevant validity levels: exact coordinate-wise validity, exact validity on observed masks, and approximate missingness-conditional guarantees for general mechanisms (MCAR, MAR, MNAR). Experiments on synthetic and real datasets support these guarantees and show that the proposed method reduces miscoverage risk while maintaining informative intervals, especially in non-MCAR settings. These results highlight the practical value of uncertainty quantification that adapts to missingness.
BibTeX
@misc{fan2026beyond,
  author = {Jiarong Fan and Juhyun Park and Thi Phuong Thuy Vo and Nicolas J-B. Brunel},
  title = {{Beyond Imputation: Mask-Adaptive Conformal Prediction via Tree Embeddings on General Missing Data Mechanisms}},
  year = {2026},
  eprint = {2611.01724},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01724},
}
Figure