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

arXiv: https://arxiv.org/abs/2507.13263 · HTML: https://mlsanity.com/paper/2507.13263/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 17 Jul 2025.

## Builds on (most cited first, 13 of 13)

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [Dealing with Integer-valued Variables in Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1706.03673/) (2017)
- [Optimizing Sequential Experimental Design with Deep Reinforcement Learning](https://mlsanity.com/paper/2202.00821/) (2022)
- [Bayesian Optimization for Categorical and Category-Specific Continuous Inputs](https://mlsanity.com/paper/1911.12473/) (2019)
- [Large Sequence Models for Sequential Decision-Making: A Survey](https://mlsanity.com/paper/2306.13945/) (2023)
- [Bayesian Optimization over Permutation Spaces](https://mlsanity.com/paper/2112.01049/) (2021)
- [Financial Applications of Gaussian Processes and Bayesian Optimization](https://mlsanity.com/paper/1903.04841/) (2019)
- [Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel](https://mlsanity.com/paper/2102.13382/) (2021)
- [Multi-objective Bayesian Optimization With Mixed-categorical Design Variables for Expensive-to-evaluate Aeronautical Applications](https://mlsanity.com/paper/2504.09930/) (2025)
- [Domain Knowledge Injection in Bayesian Search for New Materials](https://mlsanity.com/paper/2311.15162/) (2023)

## Built on by (most cited first, 1 of 1)

- [Optimal Transport-based Permutation-Invariant Bayesian Optimization of Offshore Wind Farm Layouts](https://mlsanity.com/paper/2606.00009/) (2026)

## Abstract (arXiv)

Bayesian Optimization (BO) is a powerful tool for black-box optimization, but its application to high-dimensional permutation spaces is severely limited by the challenge of defining scalable representations. The current state-of-the-art BO approach for permutation spaces relies on an exhaustive Omega(n2) pairwise comparison, inducing a dense representation that is impractical for large-scale permutations. To break this barrier, we introduce a novel framework for generating efficient permutation representations via kernel functions derived from sorting algorithms. Within this framework, the Mallows kernel can be viewed as a special instance derived from enumeration sort. Further, we introduce the Merge Kernel , which leverages the divide-and-conquer structure of merge sort to produce a compact, Theta(nlog n) to achieve the lowest possible complexity with no information loss and effectively capture permutation structure. 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. Extensive evaluations on various permutation optimization benchmarks confirm our hypothesis, demonstrating that the Merge Kernel provides a scalable and more effective solution for Bayesian optimization in high-dimensional permutation spaces, thereby unlocking the potential for tackling previously intractable problems such as large-scale feature ordering and combinatorial neural architecture search.