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 continuous 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 industrial applications and scientific discovery. In this work, we revisit the efficacy of vanilla BO in high-dimensional permutation spaces under limited evaluation budgets. We propose VaPBO, a framework that performs variable selection over permutation elements, fits a Merge-kernel surrogate on active sub-permutations, and reconstructs full permutations through a structure-aware fill-in strategy. Across classical combinatorial problems, chip placement, and biodiversity history reconstruction, VaPBO with greedy local search achieves the best average rank among the compared methods. Further experiments show that surrogate guidance improves candidate selection and that fill-in preserves useful ordering from good solutions. Our findings call for a reevaluation of vanilla BO’s generality and highlight the enduring value of dimensionality reduction for high-dimensional permutation optimization.