Can Tabular Foundation Models Predict Algorithm Runtime Distributions?

Algorithm runtime prediction is a natural testbed for tabular foundation models: it is structured, data-limited, practically important, and requires calibrated uncertainty estimates. Since runtimes can be highly variable and heavy-tailed, we study not only point prediction but full instance-specific runtime distribution prediction. We evaluate TabPFN, a pretrained tabular foundation model performing in-context Bayesian prediction, on established SAT and AI planning benchmarks. TabPFN outperforms classical tabular baselines and specialized neural models, with especially large gains in low-data regimes. At the same time, we uncover a surprising failure mode: on some benchmarks, larger contexts degrade predictive performance. These results establish TabPFN as a strong baseline for empirical runtime modeling and runtime prediction as a challenging benchmark for uncertainty quantification and context scaling in tabular foundation models.