Source-linked AI summary
The Good, the Bad, and the Ugly of Markov Boundary for Tabular Prediction
Shu Wan, Abhinav Gorantla, Huan Liu, K. Selçuk Candan
TL;DR
The paper asks whether Markov boundaries improve tabular prediction and compares oracle and recovered feature masks across regressors. Oracle boundaries help in high-dimensional sparse settings, but recovery rarely outperforms using all features, motivating prediction-aligned selection.
Problem
Whether regressors benefit from seeing only Markov-boundary features remains an empirical finite-sample question because the full table is population-sufficient too.
Method
The paper evaluates oracle boundaries, recovered masks from causal-discovery methods, and controlled mask perturbations across downstream regressors.
Results
Oracle boundaries improve prediction for most regressors, with widening gains in larger, sparser spaces, whereas recovered masks rarely beat the full feature set.
Takeaways & Limitations
Feature selection should guide prediction with scalable, prediction-aligned masks that preserve boundary information without requiring exact boundary recovery.
Takeaways & Limitations
Prediction-gain maps are descriptive and regressor-conditioned because their true-positive, false-negative, and false-positive counts ignore feature identity.
Abstract
from arXiv · showhide
Under standard graphical assumptions, the Markov boundary of a target variable is the smallest set of features that renders every other feature redundant. Once the boundary is observed, the target is conditionally independent of the rest of the table. This is a tempting object for tabular prediction, since it names exactly the columns a model should need. Yet modern regressors are still trained on the full feature set. We ask whether the Markov boundary is genuinely useful for prediction on SCM3K, a 3,450-task synthetic SCM benchmark with feature counts from 40 to 1000 and six SCM families, evaluated with six regressors. The answer is more nuanced than the theory suggests. Restricting a regressor to the oracle boundary often improves prediction substantially, and the improvement grows as the feature space becomes larger and sparser. But the natural pipeline of recovering the boundary with causal discovery and training on the recovered mask does not deliver. Existing estimators exhaust the compute budget before reaching the regime where the boundary helps most, and even where they run they rarely beat the full feature set. We trace this to three causes. Discovery optimizes structural recovery rather than prediction. False negatives and false positives carry sharply asymmetric predictive cost. The exact boundary is only one of many feature sets that beat all features. We then develop what these facts imply for prediction-aligned feature selection and for tabular models that learn to use causal structure.
1 Introduction
The paper asks whether the Markov boundary improves tabular prediction beyond using all features. Across a controlled SCM benchmark, oracle boundaries help, but recovering them is costly and prediction-aligned selection may require relaxing exact minimality.
- The Markov boundary is attractive because it is both sufficient for predicting the target and minimal in its feature usage.A sufficient set preserves all predictive signal, while a minimal set excludes redundant columns.
- Scalability complicates classical boundary recovery because independence-search costs grow steeply with feature count.Implicitly selective models also do not resolve the paper’s central question about whether regressors benefit from seeing only relevant columns.
- Oracle boundary restriction improves prediction for most regressors, with the MB gap widening as feature spaces become larger and sparser.The paper then tests whether off-the-shelf Markov-boundary and causal-discovery estimators can recover this advantage.
- Recovered-boundary pipelines disappoint because estimators exhaust their compute budget before reaching the regime where boundary benefits are greatest.The introduction also notes that feature sets differing from the exact boundary can still outperform the full table, motivating scalable, prediction-aligned selection that trades strict minimality for robustness.
2 Preliminaries
The preliminaries define Bayes risk and the graphical Markov boundary for tabular regression, then show that under graphical sufficiency and non-degeneracy the boundary is the unique inclusion-minimal Bayes-sufficient feature set. They also establish that the full feature set is Bayes sufficient, so population sufficiency alone cannot distinguish the boundary from using every feature.
- For candidate features X and target Y, the analysis evaluates population squared-loss risk on restricted feature vectors X_S for subsets S⊆[F].
- Under Markovness, faithfulness, positive product support, train/test invariance, and conditional-mean non-degeneracy, the graphical Markov boundary B(Y) is Bayes sufficient.The assumptions require every boundary coordinate to change E[Y|X_B] on a set of positive measure.
- The boundary is the unique inclusion-minimal Bayes-sufficient set, because every Bayes-sufficient set contains B(Y), while the boundary itself matches the full feature set’s Bayes risk.The proof uses conditional independence to obtain E[Y|X]=E[Y|X_B] and product support to rule out omitted boundary coordinates.
- The full feature set [F] is also Bayes sufficient, so population sufficiency alone does not distinguish it from the Markov boundary.
- SCM3K contains 3,450 synthetic SCM tasks spanning F∈{40, 60, 80, 100, 200, 400, 600, 800, 1000}, with dense low-dimensional and sparse higher-dimensional graph regimes.Each task uses a DAG with F+1 nodes and selects the target using an MB-ratio band.
3 When the Boundary Helps
The Markov boundary improves finite-sample prediction when redundant dimensions stress a regressor, but gains depend strongly on the regressor’s implicit feature selection. Across SCM3K, redundancy and regressor identity dominate the observed boundary gap, while SCM family contributes little after adjustment.
- 3 When the Boundary Helps: The oracle boundary’s prediction gain is finite-sample and regressor-dependent, increasing when redundant dimensions stress the learner and shrinking with stronger implicit feature selection.The boundary helps most for regressors that pay a higher finite-sample cost for extra columns.
- 3 When the Boundary Helps: +35% median relative oracle RMSE reduction for Ridge, versus +24% for MLP, +18% for TabICL, +12% for TabPFN, +4% for XGBoost, and +2% for LASSO.These six regressors span shrinkage, neural, boosting, and prior-fitted tabular foundation models.
- 3 When the Boundary Helps: LASSO and XGBoost have small oracle gaps because sparsification and split-variable selection absorb part of the feature-selection burden, not because feature selection is unimportant.TabPFN and TabICL remain vulnerable to redundant features, including cases above a 10% prediction-loss change.
- 3 When the Boundary Helps: Redundancy ratio and regressor identity have the largest adjusted R^2 values, 0.221 and 0.219, followed by density at 0.187 and log10 F at 0.166; SCM family explains 0.012.Density largely duplicates redundancy with the opposite sign, while SCM family is weak after these covariates are included.
- 3 When the Boundary Helps: For OLS in the linear Gaussian model, the full-versus-boundary gap is the variance cost of estimating F−k extra coefficients whose population contribution is zero once the boundary is observed.The leading large-sample term is σ^2(F−k)/n, while regularized and nonlinear regressors replace raw parameter count with effective complexity.
4 The Emperor’s New Blanket
Oracle Markov boundaries can improve prediction, but current causal estimators rarely convert that advantage into gains. Boundary recovery is limited by scaling, precision-heavy errors, and regressor-dependent sensitivity to noisy masks.
- Oracle boundaries can improve prediction, but current causal estimators rarely turn that advantage into wins.
- The evaluated pipeline estimates a Markov boundary, selects its feature mask, and trains the same downstream regressor using GES, Grow-Shrink, or HITON-MB.
- 0% GES completion at F=100, after falling to 9.4% at F=80, shows that causal discovery becomes unusable as feature counts grow.Grow-Shrink reaches F=200 with mean F1 0.633, while HITON-MB reaches F=200 with mean F1 0.588 and recall 0.485.
- Causal recovery is often precision-heavy: HITON-MB has higher precision than recall at every evaluated feature count, while Grow-Shrink remains precision-heavy through F=100.False negatives are usually more costly than false positives for prediction.
5 Failure Mechanisms
Causal boundary recovery fails as a prediction pipeline because computational limits coincide with the settings where oracle gains are largest, while mask errors have asymmetric predictive costs. Moreover, controlled supersets preserve population-optimal prediction, making exact boundary recovery an overly narrow objective.
- Computational limits: Constraint-based discovery can require O(F^d) candidate conditional-independence tests, while score-search methods face rapidly growing graph spaces.The scale problem reflects combinatorial structure-learning pressure rather than merely implementation overhead.
- Computational limits: GES is effectively limited to F≤80, while Grow-Shrink and HITON-MB cap around F=200, where the oracle prediction gap remains weakest.The oracle gap grows above F=200 in higher-dimensional redundant settings, so available estimators rarely reach the regime with the largest reward.
- Asymmetric mask errors: False negatives damage prediction more than false positives: αFN/αFP exceeds one in every reported regressor cell.False positives preserve the boundary and mainly add finite-sample variance, whereas omitted boundary variables create a nonvanishing population-risk penalty.
- Asymmetric mask errors: High-precision, low-recall estimators can appear successful on exact-recovery metrics while harming prediction, making F1, SHD, and constraint satisfaction incomplete objectives.The omitted-signal penalty does not vanish with more samples, unlike the leading variance cost from redundant variables.
- Superset sufficiency: If S⊇B, then S remains a Markov blanket and R*(S)=R*(B), so exact boundary recovery is not the only prediction-relevant target.Controlled supersets preserve the population conditional, though larger masks may lose finite-sample efficiency.
6 Beyond the Boundary
Section 6 replaces exact-boundary recovery with prediction-aligned feature selection: layered blankets expose structured supersets, while a regressor-conditioned gain map characterizes masks that can beat all features. Finite-sample prediction rewards balancing missed boundary information against estimation variance, so nonminimal masks may be preferable.
- Layered blankets: Layered blankets accumulate Markov-boundary closure, with Layered@1 equal to the oracle boundary and every later layer remaining a Markov blanket.They are computational devices rather than new structural results, and contrast with expansion by target proximity.
- Layered blankets: +10.8 to +20.9 percentage points: for TabPFN at F = 200–800, layered@1 substantially outperforms target-proximity@1.The oracle boundary is the peak for every F; later layers expose structured over-inclusive masks rather than improving on it.
- Prediction gain map: The prediction gain map evaluates masks by true positives, false negatives, and false positives, identifying regions predicted to beat the all-feature baseline.It is descriptive and regressor-conditioned, because identical counts can produce different risks when feature identities differ.
- Prediction gain map: TabPFN’s map has R^2 = 0.758 and penalizes missed boundary features strongly, whereas Ridge has R^2 = 0.436 and a much larger false-positive penalty.For TabPFN, recall must exceed roughly 0.8 to beat all features, making false-negative and false-positive costs asymmetric.
- Prediction-aligned target: Finite-sample prediction can favor masks near the exact boundary because dropping columns reduces estimation variance, even when the mask is not Bayes sufficient.Second layers, mixed-layer masks, and proxy-variable shells trade some efficiency for robustness when boundary variables are missing or noisy.
7 Implications
The paper proposes using SCM supervision to make boundary information reusable through pre-training and to align mask learning with prediction rather than structural recovery alone. These directions preserve sufficiency while allowing prediction loss to determine the finite-sample feature set.
- Amortized boundary prediction: SCM-generated tasks can supervise a tabular model to predict the target’s Markov boundary alongside its regression output.This converts the synthetic ground-truth boundary into a training signal unavailable in real observational tables.
- Amortized boundary prediction: At inference, amortized boundary estimates avoid repeating the combinatorial search for every dataset by paying its cost during pre-training.The proposal parallels causal foundation models trained on SCM-generated tasks and reused at test time.
- Amortized boundary prediction: A recall-weighted mask penalty should discourage false negatives because dropping boundary features carries greater predictive risk than retaining false positives.The proposed loss writes the predictive asymmetry identified earlier directly into Lmask.
- Prediction-aligned selection: The deeper fix treats the feature mask m as a latent variable so the predictor and mask are learned jointly rather than in sequence.This makes prediction loss inform boundary discovery instead of leaving discovery as an unsupervised preprocessing step.
- Prediction-aligned selection: The proposed objective combines prediction loss with a structural prior Ω that rewards preserving the sufficiency structure of B, bridging implicit selection and boundary discovery.Prediction determines how far to depart from exact structural recovery because causal structure alone does not identify the finite-sample optimum.
8 Related Work
Related work frames Markov-boundary recovery through full-graph and local causal-discovery methods, while this paper evaluates the resulting estimate-then-predict pipeline. It also situates the study alongside tabular and causal foundation models without proposing either.
- Markov blanket discovery: Full-graph causal-discovery methods recover a DAG, CPDAG, or equivalence class before deriving the target’s Markov blanket.The cited approaches include score-based search such as GES and constraint-based discovery using conditional-independence tests.
- Markov blanket discovery: Local algorithms such as Grow-Shrink and HITON-MB search directly around the target using conditional-independence tests.The paper uses this literature as the natural baseline for estimating a blanket and then predicting.
- Prediction-aligned feature selection: The paper refines feature-selection work by showing that oracle-boundary gains are finite-sample and regressor-dependent, while exact identification is not the only prediction-relevant objective.False negatives and false positives have different costs, and many over-inclusive masks can preserve most of the oracle gain.
- Foundation models: TabPFN and TabICL provide synthetic-prior tabular predictors used here as downstream regressors to test whether the Markov-boundary gap persists for modern models.They are not the paper’s main method or narrative device.
- Foundation models: Causal foundation models likewise learn from SCM-generated tasks, motivating future use of SCM-prior blanket information for prediction-aligned feature learning.The paper explicitly does not propose a causal or tabular foundation model.
9 Conclusion
Markov boundaries clarify when feature parsimony improves tabular prediction, but exact unsupervised boundary recovery is too narrow to serve as the prediction objective. Prediction-aligned masks should preserve boundary information, control redundant features for the downstream regressor, and scale to high-dimensional regimes where the oracle gap is visible.
- Conclusion: The paper’s main evidence is simulated, so validation on real-world benchmarks remains necessary.Suggested candidates include ARTH150, causalAssembly, DREAM4, DREAM5 in-silico Net 1, and SynTReN.
- Conclusion: Markov boundaries identify when feature parsimony improves tabular prediction, with a real oracle gap in high-dimensional redundant settings.The exact boundary is the minimal population-sufficient feature set.
- Conclusion: Exact unsupervised boundary recovery is too narrow as a prediction objective because useful masks need not equal the minimal boundary.Prediction requires masks that preserve boundary information while managing redundant features according to the downstream regressor.
- Conclusion: Prediction-aligned feature selection should preserve boundary information, regulate redundant features for the downstream regressor, and scale to regimes where the oracle gap is visible.These requirements follow from the conclusion that exact recovery alone does not meet prediction needs.