The Good, the Bad, and the Ugly of Markov Boundary for Tabular Prediction Conference: Proceedings of the 35th ACM International Conference on Information and Knowledge Management; October 26–30, 2026; Toronto, Canada CCS: Computing methodologies Supervised learning by regression CCS: Computing methodologies Feature selection CCS: Computing methodologies Causal reasoning and diagnostics
Shu Wan, Abhinav Gorantla, Huan Liu, K. Selçuk Candan · 2026
Read The Good, the Bad, and the Ugly of Markov Boundary for Tabular Prediction Conference: Proceedings of the 35th ACM International Conference on Information and Knowledge Management; October 26–30, 2026; Toronto, Canada CCS: Computing methodologies Supervised learning by regression CCS: Computing methodologies Feature selection CCS: Computing methodologies Causal reasoning and diagnostics by Shu Wan, Abhinav Gorantla, Huan Liu, K. Selçuk Candan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29411.txt.
Introduction
Shu Wan asks whether the Markov boundary is truly useful for prediction on tabular data. Under standard rules, the Markov boundary of a target is the smallest feature set that renders every other feature needless. On a made-up benchmark, using only the oracle set, a model often lifts scores, with gains growing as columns grow larger and sparser. But the natural path of finding it with causal search does not deliver. Current methods exhaust the compute budget before reaching the regime where it helps most.
Catalog record
| CREATOR | Shu Wan, Abhinav Gorantla, Huan Liu, K. Selçuk Candan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49576 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.29411
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Good, the Bad, and the Ugly of Markov Boundary for Tabular Prediction Conference: Proceedings of the 35th ACM International Conference on Information and Knowledge Management; October 26–30, 2026; Toronto, Canada CCS: Computing methodologies Supervised learning by regression CCS: Computing methodologies Feature selection CCS: Computing methodologies Causal reasoning and diagnostics Shu Wan, Abhinav Gorantla, Huan Liu, K. Selçuk Candan Abstract . 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 40 to 1000 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 Sufficiency Scalability Minimality Tabular foundation models Markov boundary discovery Implicit feature selection Open design space Figure 1 . The scalability–minimality–sufficiency triangle for tabular prediction. A good feature set should be sufficient, minimal, and cheap to find. Existing methods often satisfy two of the three goals: Markov boundary discovery is sufficient and minimal but does not scale; implicit feature selection (e.g., LASSO, XGBoost) scales and selects sparse predictors but does not guarantee sufficiency; tabular foundation models (e.g., TabPFN, TabICL) scale and are sufficient but perform no feature selection. The center remains an open design space. Triangle with corners Sufficiency, Scalability, and Minimality. Tabular foundation models sit on the Scalability–Sufficiency edge, Markov boundary discovery on the Sufficiency–Minimality edge, and implicit feature selection on the Scalability–Minimality edge. The center is labeled Open design space. The goal of tabular prediction is to estimate a target variable Y from a table of candidate features. Two properties make a feature set ideal for this task. It should be sufficient . Conditioning on it must preserve everything the table reveals about Y , so that no predictive signal is discarded. It should also be minimal . It should hold nothing beyond what sufficiency demands, so that the learner is not charged for redundant columns. Causal graphical models give these two properties a single, precise solution. For a target Y in a directed graphical model, the Markov boundary B(Y) consists of its parents, its children, and the other parents of those children. It is the smallest graphical feature set for which Y is conditionally independent of every remaining feature once B(Y) is observed ( Pearl 1988 ; Koller and Friedman 2009 ) . Under the standard Markov and faithfulness assumptions ( Pearl 2009 ; Spirtes et al. 2000 ) , the boundary is at once minimal and sufficient. Minimality and sufficiency, however, are not all a practitioner needs. A selection procedure must also be scalable . It has to stay tractable as a table widens to hundreds or thousands of columns. On this third axis the comfortable picture breaks. Classical Markov boundary and causal discovery algorithms recover a minimal sufficient set by design, but lean on independence search whose cost grows steeply with the feature count ( Margaritis and Thrun 1999 ; Aliferis et al. 2003 ; Tsamardinos et al. 2003 ) . Models with implicit feature selection, such as the LASSO ( Tibshirani 1996 ) and tree-based ensembles ( Chen and Guestrin 2016 ) , scale well and select sparse predictors, but their selection follows marginal predictive correlation rather than the conditioning structure, so the retained set need not be sufficient. Figure 1 places these families at the edges of a triangle whose corners are scalability, minimality, and sufficiency. Each method tends to satisfy two of the three goals. The remaining case is the regressors that increasingly define tabular prediction. TabPFN and TabICL are transformers pre-trained on millions of synthetic prediction tasks. At test time they ingest an entire table in context and predict without any per-dataset fitting ( Hollmann et al. 2023 ; Qu et al. 2025 ; Müller et al. 2022 ) . They are fast, accurate, and scalable, yet by construction they consume every column handed to them. Feature selection is simply not part of the recipe. The model is trusted to discount whatever is irrelevant on its own. Whether that trust is warranted is an empirical question. This leads us to the central question: Is the Markov boundary useful for tabular prediction? If B(Y) is minimal and sufficient, a regressor restricted to B(Y) should lose no predictive information while carrying far fewer columns. But the full table is sufficient too, so population theory alone cannot answer the question. It is a finite-sample claim about how a particular regressor reacts to redundant columns, and it has to be measured. We measure it with SCM3K 1 1 1 https://huggingface.co/datasets/CSE472-blanket-challenge/SCM3K , a controlled benchmark of 3,450 synthetic SCM tasks. It pairs Erdős–Rényi DAGs with six SCM families. It sweeps the candidate feature count from 40 to 1000 and evaluates six regressors. They include shrinkage baselines, a tree ensemble, a neural network, and tabular foundation models. For every task and regressor we compare the test error of training on all features against training on the oracle Markov boundary, and call their difference the MB gap . The story that emerges is more tangled than the theory predicts. First, the boundary delivers. Restricting to B(Y) improves prediction for most regressors, and the MB gap widens steadily as the feature space grows larger and sparser. Encouraged by this, we test the obvious pipeline. We estimate the boundary with off-the-shelf Markov-boundary and causal discovery, then train on the recovered mask. The result disappoints. The estimators exhaust the compute budget long before reaching the high-dimensional regime where the gap is largest, and even where they do run, the recovered masks rarely beat the full feature set. We then ask why, and find three reasons. Causal discovery optimizes structural recovery, which is not the same objective as prediction. Missing a boundary feature and adding a redundant one are scored identically by recovery metrics, yet they carry sharply asymmetric predictive cost. And the exact boundary is not the only good answer. Many feature sets that differ from B(Y) still beat the full table. The three desiderata of Figure 1 pull against one another exactly in the regime where prediction