📊 statistics

The Good, the Bad, and the Ugly of Markov Boundary for Tabular Prediction

While theoretically optimal for prediction, using the Markov boundary in tabular learning is practically hindered by the inability of current causal discovery methods to accurately recover it within compute budgets, revealing a critical gap between structural recovery and predictive performance that necessitates new feature selection strategies aligned with prediction goals.

Original authors: Shu Wan, Abhinav Gorantla, Huan Liu, K. Selçuk Candan

Published 2026-08-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shu Wan, Abhinav Gorantla, Huan Liu, K. Selçuk Candan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of data science, computers are constantly asked to make predictions based on tables of information. Imagine a spreadsheet where one column holds the answer we want to know, like the price of a house or the likelihood of a disease, and hundreds of other columns hold potential clues, such as square footage, age, or blood pressure. The goal is to find the perfect combination of clues that leads to the most accurate answer. For decades, a powerful idea from probability theory has offered a neat solution to this problem. It suggests that for any specific question, there is a tiny, perfect group of clues that contains everything necessary to make the prediction, while rendering every other clue in the table completely useless. This perfect group is called a Markov boundary. The theory is elegant: if you could find this small group, you could throw away the rest of the data, train a simpler model, and get the same result as if you had used everything. It promises a world where less data leads to better answers.

However, a team of researchers at Arizona State University decided to test whether this elegant theory actually works when applied to modern computer programs that make predictions. They built a massive testing ground called SCM3K, a collection of 3,450 different synthetic problems designed to mimic real-world data. These problems varied wildly in size, with some having as few as 40 clues and others stretching to 1,000. They tested six different types of prediction engines, ranging from simple statistical tools to advanced artificial intelligence models. The researchers first asked a straightforward question: if they gave a prediction engine only the perfect, theoretical group of clues, would it perform better than if it were forced to look at every single clue in the table? The answer was a resounding yes. When the data was large and full of redundant information, restricting the computer to just the essential clues significantly improved its accuracy. The more useless data was removed, the sharper the prediction became. It seemed the theory was right all along.

But then the researchers tried the next logical step: they asked the computer to find that perfect group of clues on its own before making a prediction. They used existing tools designed to discover these boundaries and then fed the results into the prediction engines. This is where the story took a sharp turn. The tools designed to find the perfect group failed to deliver the promised benefits. In many cases, using the computer's best guess at the perfect group actually made the predictions worse than just using the full table of data. The researchers discovered that the tools used to find these boundaries were not built for the job of prediction. They were built to find the exact mathematical structure of the data, a task that is incredibly difficult and slow when the data gets large. By the time these tools finished their work, they had often run out of computing power or time, especially in the large, complex scenarios where the perfect group would have been most helpful.

The failure was not just about speed; it was about a fundamental mismatch in goals. The tools that find these boundaries treat two types of mistakes as equally bad: missing a clue that is actually important, and including a clue that is not. In the world of prediction, these mistakes are not equal. Missing an important clue is a disaster that ruins the answer, while including an extra, useless clue is a minor annoyance that the prediction engine can often ignore. The researchers found that the tools were too cautious, often leaving out vital clues to avoid adding useless ones, and this caution hurt the final prediction. Furthermore, they discovered that the "perfect" group of clues is not the only way to get a good answer. A slightly larger group of clues that includes some extra, harmless information often works better than a fragile, exact group that might have missed a critical piece.

The study concludes that while the idea of a perfect, minimal group of clues is mathematically sound, chasing that exact group is the wrong strategy for making predictions. The researchers suggest that the future of data science lies in a different approach. Instead of trying to find the single, exact set of clues, we should look for groups that are robust and safe, even if they are slightly larger than necessary. We need methods that understand that missing a vital clue is far worse than including a useless one. The goal should not be to perfectly reconstruct the hidden structure of the data, but to find a set of clues that works best for the specific prediction engine being used. The perfect theoretical boundary exists, but for the practical task of prediction, a slightly imperfect, more forgiving set of clues is often the true winner.

Technical Summary: The Good, the Bad, and the Ugly of Markov Boundary for Tabular Prediction

Problem Statement
In tabular prediction, the goal is to estimate a target variable $Y$ from a set of features. Theoretically, the Markov boundary $B(Y)$ —the smallest set of features rendering $Y$ conditionally independent of all others—is the ideal feature set. It is both sufficient (retaining all predictive information) and minimal (excluding redundant columns). Under standard graphical assumptions (Markov and faithfulness), restricting a model to $B(Y)$ should preserve predictive power while reducing dimensionality.

However, modern tabular prediction often relies on training regressors on the full feature set, assuming the model can implicitly filter noise. Conversely, causal discovery algorithms attempt to recover $B(Y)$ explicitly but face scalability issues. The central question of this paper is: Is the Markov boundary genuinely useful for finite-sample tabular prediction, and does the standard pipeline of "discover boundary, then predict" yield practical gains?

Methodology
The authors evaluate this question using SCM3K, a synthetic benchmark comprising 3,450 tasks generated from Structural Causal Models (SCMs).

Dataset Construction: Tasks vary in feature count ( $F$ ) from 40 to 1,000, graph densities (sparse to dense), and six SCM families (linear/non-linear, Gaussian/non-Gaussian, heteroskedastic).
Regressors: Six distinct models are tested: Ridge, LASSO, MLP, XGBoost, and two tabular foundation models (TabPFN, TabICL).
Evaluation Metrics:
- Oracle MB Gap: The difference in test RMSE between training on the full feature set versus training on the true (oracle) Markov boundary.
- Estimation Pipeline: The authors test the practical pipeline of using off-the-shelf causal discovery algorithms (GES, Grow-Shrink, HITON-MB) to estimate the boundary, then training the regressor on the recovered mask.
- Failure Analysis: The study dissects why the estimation pipeline fails, analyzing scalability limits and the asymmetric costs of false negatives (missing a boundary feature) vs. false positives (including redundant features).
- Alternative Sets: The paper explores "layered blankets" (supersets of the boundary) and "prediction gain maps" to identify feature sets that are not strictly minimal but are prediction-optimal.

Key Results

The Oracle Gap is Real and Regressor-Dependent:
- Training on the oracle Markov boundary significantly improves prediction for most regressors, particularly in high-dimensional, sparse regimes.
- The improvement is most pronounced for models with weak implicit feature selection (e.g., Ridge, +35% RMSE reduction) and less for those with strong intrinsic selection (e.g., LASSO, +2%).
- Even tabular foundation models (TabPFN, TabICL) show non-trivial gains from oracle boundaries, indicating they are not immune to redundant features.
The "Estimate-Then-Predict" Pipeline Fails:
- Current causal discovery estimators (GES, Grow-Shrink, HITON-MB) fail to deliver practical gains. They exhaust computational budgets before reaching the high-dimensional regimes where the oracle gap is largest.
- Even when they run, the recovered masks rarely outperform the full feature set.
- Scalability: Constraint-based methods suffer from combinatorial explosion ( $O(F^d)$ ), limiting them to low-dimensional settings ( $F \le 200$ ) where the oracle benefit is minimal.
Asymmetric Loss and Structural Mismatch:
- False Negatives are Costly: Missing a true boundary feature introduces a population-level bias (omitted variable bias) that does not vanish with sample size.
- False Positives are Tolerable: Adding redundant features increases finite-sample variance but preserves the population conditional expectation.
- Causal discovery metrics (e.g., F1 score, SHD) treat these errors symmetrically, optimizing for structural recovery rather than prediction. Consequently, high-precision/low-recall estimators (common in causal discovery) often fail to improve prediction because they drop critical boundary variables.
Beyond Minimality:
- The exact Markov boundary is not the only feature set that beats the full table. Supersets of the boundary (e.g., "layered blankets" that include spouses and neighbors) preserve sufficiency and can be more robust to estimation errors than brittle, exact boundary estimates.
- A "prediction gain map" reveals that for many regressors, a mask with high recall (even with some false positives) is superior to a mask with high precision but low recall.

Key Contributions

Empirical Evidence: Provides a large-scale, controlled evaluation showing that while the Markov boundary is theoretically optimal, the practical pipeline of causal discovery followed by prediction is currently ineffective for tabular data.
Diagnosis of Failure: Identifies three root causes for the failure: (1) Scalability limits of causal estimators, (2) The asymmetric cost of false negatives vs. false positives in prediction, and (3) The misconception that the exact minimal boundary is the only useful target.
New Objectives: Proposes shifting the goal from "exact boundary recovery" to "prediction-aligned feature selection." This involves tolerating some redundancy to ensure sufficiency and robustness.
Future Directions: Suggests two concrete research paths:
1. Amortized Estimation: Pre-training foundation models on synthetic SCM tasks to jointly learn prediction and boundary estimation, bypassing per-dataset search costs.
2. Joint Learning: Learning the feature mask and the predictor simultaneously, optimizing for prediction loss while regularizing toward population sufficiency, rather than treating feature selection as a separate pre-processing step.

Significance and Claims
The paper argues that the "Markov boundary" is a useful theoretical concept but a poor practical target for unsupervised causal discovery in the context of tabular prediction. The authors claim that the community should move away from the goal of exact structural recovery as a proxy for prediction. Instead, feature selection should be prediction-aligned, prioritizing the retention of boundary information (recall) over strict minimality, and leveraging synthetic priors to scale boundary estimation. The work bridges the gap between causal feature selection and empirical model selection, suggesting that the "good" feature set is a robust neighborhood around the boundary, not the boundary itself.

Technical Summary: The Good, the Bad, and the Ugly of Markov Boundary for Tabular Prediction

More like this