Revisiting Vanilla Bayesian Optimization in High-Dimensional Permutation Spaces

High-dimensional Bayesian Optimization (BO) has recently witnessed a paradigm shift. Accumulating evidence suggests that ``Vanilla BO'', i.e., standard Gaussian Processes with robust kernel initialization and length-scale scaling, can achieve state-of-the-art performance in high-dimensional tasks, casting doubt on the necessity of complex dimensionality reduction techniques. However, this narrative largely overlooks permutation spaces, a distinct and ubiquitous class of discrete combinatorial problems critical to various domains such as industrial applications and scientific discovery. In this work, we revisit the efficacy of vanilla BO in high-dimensional permutation spaces on these challenging tasks. We demonstrate that standard global kernels fail in this setting due to the concentration of measure and topological ruggedness inherent to factorial search spaces. Contrary to trends in continuous optimization, we find that dimensionality reduction techniques (i.e., variable selection) are not outdated but essential for restoring kernel informativeness, yielding substantial improvements in sample efficiency and optimization quality. Our findings urge a reevaluation of vanilla BO’s generality, as well as highlight the enduring value of dimensionality reduction for intractable high-dimensional tasks.