From Sorting Algorithms to Scalable Kernels: Bayesian Optimization in High-Dimensional Permutation Spaces

A new machine-learning paper proposes a kernel function derived from merge sort that cuts the computational cost of Bayesian Optimization on high-dimensional permutation problems from quadratic to linearithmic time, potentially opening the technique to previously intractable tasks such as large-scale feature ordering and combinatorial neural architecture search. The work, posted to the arXiv preprint server and authored by Zikai Xie, introduces the Merge Kernel, a representation that exploits the divide-and-conquer structure of merge sort to produce a compact Θ(n log n) encoding of permutations [1][2]. The current state-of-the-art Bayesian Optimization (BO) approach for permutation spaces relies on an exhaustive Ω(n²) pairwise comparison, which yields a dense representation that becomes impractical as the number of items n grows [1][2]. “Our central thesis is that the Merge Kernel performs competitively with the Mallows kernel in low-dimensional settings, but significantly outperforms it in both optimization performance and computational efficiency as the dimension n grows,” the paper states [2]. The Mallows kernel itself is recast within the new framework as a special instance derived from enumeration sort [1][2]. Bayesian Optimization is a black-box optimization method used widely in hyperparameter tuning and experimental design [1][2]. Permutation spaces arise naturally in problems such as feature ordering, where the sequence of variables matters, and in combinatorial neural architecture search, where the arrangement of layers and operations defines a model [1][2]. The paper’s evaluations on multiple permutation optimization benchmarks show that the Merge Kernel provides a scalable alternative, matching the Mallows kernel on low-dimensional tasks and pulling ahead as n increases [1][2]. The manuscript was submitted to arXiv on 17 July 2025 and has undergone four revisions, with the latest version posted on 12 June 2026 and weighing 429 KB [1]. arXiv, which began in 1991 and now receives roughly 24,000 articles per month, hosts preprints across physics, mathematics, computer science, and related fields [10]. The repository is moderated but not peer-reviewed [10]. The paper’s abstract page also links to community-built tools through the arXivLabs framework, including the Bibliographic Explorer and CORE Recommender, which help readers navigate citation trees and discover related open-access research [8][9]. By lowering the representation complexity from quadratic to linearithmic, the Merge Kernel addresses a bottleneck that has limited BO’s reach on permutation-structured design spaces [1][2]. The authors argue the method achieves the lowest possible complexity with no information loss, a claim supported by the benchmark results detailed in the paper [1][2].