From Sorting Algorithms to Scalable Kernels: Bayesian Optimization in High-Dimensional Permutation Spaces
Authors: Zikai Xie
Linjiang Chen
Venue: ICLR 2026 Poster (2026)
Keywords: Bayesian Optimization
Combinatorial Optimization
Permutation Space
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: Our Merge Kernel, derived from merge sort, creates scalable permutation kernels with O(nlogn) complexity, breaking the SOTA's O(n^2)

Abstract: 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(n^2)$ 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 \textbf{Merge Kernel} , which leverages the divide-and-conquer structure of merge sort to produce a compact, $\Theta(n\log 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.

Published as a conference paper at ICLR 2026
FROM SORTING ALGORITHMS TO SCALABLE KERNELS: BAYESIAN OPTIMIZATION IN HIGH- DIMENSIONAL PERMUTATION SPACES
Zikai X Linjiang Chen
State Key Laboratory of Precision and Intelligent Chemistry University of Science and Technology of China Hefei, Anhui 230000, China
{zikaix, linj annchennn@uueee @ustc edu...edu. eduu on
ABSTRACT
Bayesian Optimization (BO) is 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 ap- proach for permutation spaces relies on an exhaustive 22(2²) pairwise comparison, inducing a dense representation that 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 special instance derived from enumeration sort. Further, introduce the Merge Kernel which leverages the divide-and-conquu (n log n) to achieve the lowest possible complexity with no information loss and effectively capture permutation structure. Our central thesis is that the Merge Ker- nel performs competitively with the Mallows kernel low-dimensional settings, but significantly outperforms it in both optimization performance and computa- tional efficiency as the dimension n grows. Extensive evaluations on various per- mutation optimization benchmarks confirm our hypothesis, demonstrating that the Merge Kernel provides a scalable and more effective solution for Bayesian opti- mization 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.
structure of Merge Sort to produce compact,
INTRODUCTION
As of the most widely adopted approaches to black-box optimization, Bayesian optimization (BO) (Shahriari et al. 2015) has found broad application in machine-learning hyper-parameter tun- ing (Wu al. [2019) financial portfolio optimization (Gonzalvez al., 2019), chemical and ma- terial discovery (Luo et al. 2025). and catalyst formulation design (Xie et al. 2023). BO employs approximate the unknown objective and uses an acquisition function to balance exploration and exploitation, thereby approaching the global optimum with the fewest possible evaluations.
probabilistic surrogate models most commonly Gaussian processes (GPs)
While BO has thrived in continuous and categorical domains (Greenhill et al 2020 Garrido-
Merchán & Hernández-Lobatoo 2020 Nguyen et al.) 2020 Bartolli et al. 2025). permutation spaces remain underexplored despite their ubiquity in tasks like traveling-soe saleling-salesman problems, robotic plan- ning, and sequential order-of-addition experiments (Guidi et al. 2020 Lin & Rios 2025). The core
challenge lies in kernel design, while existing approaches fall into two categories:
General discrete BO (e.g., COMBO): Rely graph encodings but struggle with the specific structural constraints of permutations (Oh et al. 2019).
"Conesponding author.
1 "Co-correpponding author.

---

Published as a conference paper at ICLR 2026
Permutation-speeiffc kernels (e.g., BOPS): The state-of-the-ar (SOTA) Mallows ker- nel (Deshwal et al,, (002) uses an exhaustive O(n²) pairwise representation. While ef- fective in low dimensions, this quadratic complexity creates massive statistical redundancy compared all possible representations (2 > n!) and becomes computationally in- tractable for large n.
To address the limitations of existing approaches, we propose a sorting- algorithh -ereritthm-riveeen design framework for permutations and instantiate with the Merge kernel, which reduces the fea- ture dimension to (n log nh- iiformation-thoreeee The central insight that any comparison- based sorting algorithm defined by fixed sequence of element comparisons; recording the binary outcome of each comparison yields feature vector for the permutation. Choosing an algorithm with deterministic comparison tree-sttee as Merge Sort or Bitonic Sort-thus produces a representation that is both fixed in length and highly compact.
driven kemel-
lower bound for encoding permutation.
Contributions. Our work makes three principal contributions:
General framework. We propose unified design framework that constructs permutation- space kernels by treating any comparison-bel based sorting algorithm feature generator. Within this view, the classic Mallows kernel is recovered as the special case obtained when the framework is instantiated with enumeration sort.
Merge kernel. Applying the framework to Merge Sort yields Merge Kernel, whose (n log n) construction matches the information-theoretic lower bound on comparison complexity.
Comprehensive evaluation. We assess the effectiveness of our kernels on diverse syn- thetic and real-world benchmarks. Results on low-dimensional benchmarks show compet- itive performance against the SOTA Mallows kemnel, while significantly outperforms the Mallows kernel and BO on nigh-dimensional benchmarks.
Our results demonstrate that the Merge kernel provides practical and efficient tool for permutation optimization, significantly enhancing BO's applicability to diverse Al scenarios.
2 BACKGROUND AND RELATED WORKS
2.1 PERMUTATION OPTIMIZATION
Here we describe the problem formulation of permutation optimization with a fixed length a E N. permutation is function [n] - [ni] such that æ is bijective. The set of all permutations of [n] is the symmetric group
Let [n] (1, ...,, n). n.).
S, {T : [m] + [n] is bijective).
We are given a costly-to-evaluate, possibly noisy black-box function f: S, - R. which assigns a valuev quality (e.g., cost, loss, reward) to every permutation л. Hence, the optimization problem can be formulated
π arg min, E f
where F C Sn, is the feasible set. In this study we only consider the unconstrained case, therefore we have F Sn. in practice J may exclude permutations violating domain rules.
2.2 BAYESIAN OPTIMIZATION
Bayesian optimization (BO) (Shahriari et al. 2015) is an optimization algorithm for black-box ob- jective functions that no closed-form expression gradient information is available and whose evaluation is often an expensive physical or computational experiment. The algorithm first fits the observed data with surrogate model, most commonly Gaussian process (GP) (Williams & Ras- mussen 2006), and then employs an acquisition function to select the next query point, balancing exploration of uncertain regions against exploitation of promising areas identified by the surrogate.
The kernel K(x, x') is the central design lever in a Gaussian prooses surrogate: it defines the sim- ilarity metric between inputs, thereby specifying the prior smoothness assumptions and, through
2

---

Published as a conference paper at ICLR 2026
GP inference, the posterior mean and uncertainty. Extending BO to any new search domain is therefore tantamount to endowing that domain with an appropriate kernel function. Whereas Eu- clidean spaces typically rely Gaussian (RBF) kernels, discrete structures- and permutations in particular- requiee bespoke constructions that faithfully encode ordering relationships. For exam- ple, (Oh et al. 2022) uses the Position kernel (Zaefferer al. 2014) and L-ensemble with Acquisi- tion Weights to extend BO on permutation space to a batched BO scheme.
While significant progress has been made in scaling BO high-dimensional continuous domains (e.g.. Eriksson et al. (2019;; Wang et al. (2016)), extending BO to large-scale structured discrete domains like permutations presents a distinct set of challenges centered on kernel design, which is the primary focus of this work.
2.3 MALLOWS KERNEL FOR PERMUTATION SPACE
BOPS-H (Deshwal al. 2022) is the current SOTA BO algorithm for permutation optimization, which proposes to employ Mallows kernel (Jiao & Vert 2015) on the symmetric group S, a similar manner the RBF kernel the Euclidean space. The Mallows kernel K (t, x²) for the permutation pair (ı, x²) is defined as the exponential negative of the number of discordant pairs na( between ı and n':
( x') exp(-Id(z,,TT)
(I)
where / >> 0 is the length-scale parameter of the Mallows kernll, and d(TT, X') is the Kendall-T distance [Kendall 1938) which counts the number pairs of elements ordered oppositely by a and r':
d = Σ C1o0=0op
+((())
Intuitively, the Kendall-7 distance counts the differences of all pair-wise comparisons between æ and n'. For example, let (1, 4) and n'' (2, 1,4.3). Two pairs discordant among the six unordered pairs: (1, 2). (3, 4), hence ((T,T') = 2 and K MaI(T, T') exp(-21)
MERGE KERNEL: GENERATING KERNELS FROM SORTING ALGORITHMS
In the previous section, we have shown that the core of the Mallows kernel the pairwise compari- son of all elements. Equivalently, it maps a permutation π to feature vector
① ( ())
where each coordinate corresponds to the comparison of pair of elements: 0 if they in ascending order, and otherwise. We then have
1 Mat Mad 112
KMa x') expl
282
KREE (PMa(()) T *Ma
under the reparameterization 1 2 for the length-scale parameter E in the Gaussian RBF kernel. Since the RBF kernel KREF is strictly positive definite on dd and thus satisfies Mercer's condi- tion (Mercer 1909), and because positive definiteness is preserved under composition with any de- terministic mapping क. it follows that K(T, x²) constructed from T also satisfies Mercer's condition and is therefore a valid kernel function.
Thus, other pairwise comparison methods also be used to construct analogous feature vectors and yield valid kernel functions when combined with an RBF kernel. Naturally, we can extend the idea of pairwise comparison to sorting algorithms: the essence of sorting algorithm is to compare
3

---

Published as a conference paper at ICLR 2026
2
Merge Process
lafahaif
Left half
Right half
9
7 8
Righd
Viterge
0, 0, 1,
0,0
0, 1, 1, 1,0
0,1,1,0, 1,1
Merr (T)) = Votat
Figure Diagram of generating Merge feature vector Mer-
elements in sequence and swap them when necessary. Consequently, each sorting algorithm bodies unique pairwise comparison strategy, suggesting that we can build permutation-space ker- nels based sorting procedures. As sorting algorithm traverses all elements, it records whether each comparison leads to a swap, thereby fully reconstructing the original permutation; hence, the resulting feature vector retains all information without any loss. Viewed in this light, the Mal- lows kernel's 's exhaustive enumeration of every element pair can be interpreted as an enumeration- sort-inspired featurization, where enumeration sort ranks each item by comparing it with every other element and then places it directly in its final position. Therefore, we can replace the above Enumer- Sort with sorting algorithm to generate another feature vector for permutation kernel: it used to obtain the information whether swap occurred during every comparison in the comparison map.
Constraint: Fixed Comparison Map. To serve a valid kernel feature vector ((x), ). the sorting al- gorithm must execute a fixed sequence comparisons regardless of the input. Otherwise, elements at the same position in two feature vectors would represent information with different meanings, rendering comparison impossible. This excludes adaptive algorithms like Quicksort. We implement stabilized Merge Sort that enforces redundant comparisons (totaling L R per merge step). Specifically, each comparison evaluates the leading unmerged elements of the subsequences; stabi- lizing the path ensures that the feature each index consistently encodes the same local structural decision, enabling meaningful distance computation.
Merge Kernel. We introduce the Merge Kernel, leveraging the divide-and-conque structure of Merge Sort. The construction of the feature vector mirrors the recursive sorting process: (1) di- vide the sequence into two halves; (2) recursively generate feature vectors $ Le and Right for each half; and (3) merge the sorted halves, recording the binary outcome of each comparison into Merge (e.g., 0 the element from the left half is larger, and 1 otherwise). The final feature vector Φ is formed by concatenating [ LeLeft. 4 Righh 4 Mergel. This results in compact representation of length (n log nt), matching the information-thee -thhoreit- lower bound for lossless encoding. The ker- nel is defined as Equation and an example of generating Merge feature is illustrated in Figure comparison mapping $ (mr is shown in Algorithm Here we present an ex- ample below for permutation [1,4.3,2] to show the Merging process. Detailed discussion of sorting algorithm choices is included Appendix B.T
The element-part
K (z, n²) exp( De Mer (TT) T ner (Tr') (71)
282
(4)
= KREF @erer (TT),
1 Mer (TT)).
Example: Feature Mapping for ग = (1, (1,4)322
1. Initial Split: æ splits into Lo (1, 4) and Ro (3,2). 2).
2. Recurse on Lp = (1, 4) Merging sorted lists '[1]' and "[4]' yields feature vector Vz = [0]
Recurse on Rg (3, 2): Merging sorted lists '[2]' and '[3]' yields feature vector VR [1].

---

Published as a conference paper at ICLR 2026
Final Merge:
Merge Sorted lists '(1,4)' and '(2.3). The fixed comparison path generates
the merge vector V Merge = [0(1 < 2), ( > 2), 1(4 > 3), (leff padding)].
Concatenate: The final feature vector is Me
= Vv. VR @
VMerge = [0] +
[1] +
10, (0,1,,, 10,1
Algorithm MERGE FEATURE MAPPING (T)
Input: Permutation π of length
Output: Feature vector & (Mer(T)
if (e) == then
return 0
end if'
if length(Tr) == then
refurn [1] [00 x[1] else [0]
end if
Let mid
= -
2-
Let VLeft, V Right = Darer (Tr]: mid)), & M (r(mid :))
Let ât, R, = ( mid)), sorted [mid :])
0 while < leeeghhhht (t) and j < (f,) do
Let Verree = [l. i
if [o] [ then
append()
j+
end if
if +
< R then
V Merge.append(( append(())
i+=1
end if end while
return VLett + VRight + Vieerge
We have established that Merge sort, with specially designed fixed-comparison procedure, is uniquely capable constructing valid kernel functions among common sorting algorithms with complexity of Q(n log We now demonstrate that the feature vector derived from Merge Sort achieves the thcoretical lower bound on vector length for lossless permutation encoding. First, note that the lower bound time complexity for any comparison-basee sorting algorithm is 2(n log n); as this complexity directly corresponds to the number of element comparisons during sorting, similarly sets a lower bound on the length of the feature vector. On the other hand, consider the per- mutation space consisting of all n.! possible permutations of length n. From an cooommationthhoreeee viewpoint, encoding all nı! permutations without loss using binary feature vector composed solely of 0, 1 requires a minimum vector length of logz (n!). Applying Stirling's approximation (Knuth, 1999., we have: logz = n log2 nlogze + (log Q(n log n) Consequently, the feature vector length of the merge-sort-based kernel (Merge Kernel) reaches this theoretical lower bound for lossless permutation encoding.
It is worth noting that, when constructing the Merge kernel via Merge Sort, we have not required the feature mapping to possess any group invariance property, such as right-invariance. Traditionally, permutation-distance measure should be invariant under right multiplication, meaning that apply- ing an identical night-multiplicatiee tween them. However, only sorting algorithms with complexity O(n²) can yield fully right-invariant kernel functions with no information loss (otherwise, a simple Spearman's 's footrule (Diaconis & Graham 1977) with O(n) complexity can hold right-invariance well), since such invariance
operation to two permutations should not alter the distance be-
cessitates exhaustive pairwise comparisons among all n(n-1) pairs of elements an impossibility for more efficient sorting algorithms like Merge Sort. Consequently, although the Merge kernll achieves better computational efficiency through a more compact encoding, it sacrifices a certain degree of performance due to the loss of right-invariance
2
5

---

Published as a conference paper at ICLR 2026
We can view the relationship between the Merge and Mallows kernels as feature selection process. Given that the (T) vector corresponds to a structured subset of the complete (M feature space, incrementally adding the missing comparison positions to Mer is equivalent to gradual transformation towards the Ma vector. This transformation represents a principled trade-off: the process of "buying back" the property of right-invariance through the incorporation of more fea- tures is achieved at the explicit cost of sacrificing computational efficiency. However, because this requires the development of appropriate analytical tools quantify the exact marginal gain in in- variance per added comparison, this remains fascinating, yet highly complex, direction for future research that beyond the scope of this paper.
4 EXPERIMENTS
4.1
BENCHMARKS AND EXPERIMENT SETTINGS
Our empirical evaluation focuses on the SOTA BOPS-H algorithm (Deshwal et al. 2022) as the pri- mary control baseline. This choice is twofold: first, BOPS-H was shown to substantially outperform other permutation-sped
methods like COMBO (Oh et al. 2019). Second, our core objective is a principled comparison between our Merge Kernel and the Mallows Kernel-both natively designed for permutations. This comparison serves as a direct evaluation of representation power without confounding factors from domain adaptation. Furthermore, we adapt TuRBO (Eriksson al., 2019) as a high-dimensional BO algorithm of general purpose to evaluate the overall competitiveness of our framework. Since TuRBO is designed for continuous space, we apply a continuous relaxation to the permutation space: we define the search space as a dd-dimensional unit hypercube [0, 1) where the discrete permutation induced by the argsort of the continuous vector elements.
To disentangle whether the performance of the Merge kernel stems merely from its compact dimen- sionality from the specific structured information it captures, we introduce a randomized baseline. Specifically, we randomly subsample fixed number of pairwise comparisons from the full Mallows feature vector, ensuring the total dimensionality exactly matches that of the Merge kernel. We then apply the same RBF kernel to these features. If the success of the Merge kernel were driven solely by "compression" rather than the "informative structure" of the features, this baseline should achieve comparable performance. In addition, discussion of using Spearman's 's footrule as featurization method is also added to Appendix [B.3] due to limited space in the main manuscript. The resources and source code of BOPS algorithms are available at: https///iiiubbcoo///////////////
4.1.1 LOW-DIMENSIONAL BENCHMARKS
The study by Deshwal et al. 2022) exclusively considers problems with dimensions of 30 less. Accordingly, we adopt their experimental settings to form our suite of low-dimensional benchmarks. The BOPS-H algorithm follows and modifies the local-search strategy used in COMBO, examining only the set of neighbouring permutations of the current incumbent to restrict the combinatorial search space, we therefore adopt the same procedure in our experiments. GPryTorch (Gardner al., 2018) and BoTTorch (Balandat et al. (2020) libraries are used to implement both algorithms. Expected Improvement acquisition function is used for all the experiments, and 10 restarts are used for local search based EI optimization for BOPS-H and MergeBO. Each benchmark is evaluated with 20 independent trials, each consisting of 50 iterations. The random seed for each trial set to its trial index.
We evaluate our method on the same two synthetic benchmarks and the same two real-world appli- cations following Deshwal et al. 2022). Detailed information for all benchmarks are listed below:
(1)uuarratic Assignment (QAP)==1- This a classic facility-location problem: assign n facil- ities to locations that flow costs and distances align optimally. We use the 15-city instances from QAPLIB (Burkard et al., [197), each with cost matrix A and distance matrix B, and minimise Tr(APBPT) over permutation matrices P.
(2)rravelling Salesman (TSP) The TSP seeks the shortest Hamiltonian cycle through a set of cities and is standard benchmark for voute-nlanning. Our instances are 15 city PCB drill tours from TSPLIB (Reinelt) 1995): the score is the total travel time to visit all holes exactly once and return.

---

Published as a conference paper at ICLR 2026
(3)Floor Planning (FP) Floor planning is an NP-hard VLSI layout task that packs rectangular modules on a chip while minimising area and manufacturing cost. We evaluate two 15-block variants (FP-1 and FP-2); each permutation defines block placement whose cost we minimise.
(4) Placement (CP) Cell placement arranges logic cells on a row to reduce wire-length and hence circuit delay. We consider 30 equal-height cells with fixed net-list; the objective is the total Manhattan wire-length induced by a permutation of cell positions.
Because the publicly available implementation of the Mallows kernel does not provide the interface required to run the Rodinia's heterogeneous many-core benchmark (Che et al.) 2009), we did not perform experiments on this benchmark. We note numerical discrepancy between our replicated results and those reported in the original paper, which we attribute to subtle implementation details not specified in the publication, such as problem instance choices. However, we emphasize that within our experimental framework, both the Merge Kernel and the Mallows Kernel were evaluated under identical conditions, ensuring a fair and controlled comparison of their relative performance.
4.1.2 DIMESSINENIIN BENCHMARKS: TRAVELING THIEF PROBLEMS
We introduce traveling thief problems (TTP) (Bonyadi et al. 2013) as high-ding high-dimensional bench- marks, which is defined combination of TSP and knapsack problem: a thief must determine tour through n cities with distance matrix D = (diy) while simulraneously selecting items of vary- ing weights wy and values Pk maximize profit without exceeding knapsack capacity W. This structure defines complex, hybrid search space, combining an n-dimensional permutation space for the city tour with {0, 1)mH discrete space for item selection. Despite its typical application in evaluating white-box or heuristic algorithms (Polyakovskiy et al., 2014; Gupta et al., 2015), we adapt the TTP as a true black-box benchmark, providing no structural information to the optimizer.
Following the implementation in Polyakovskiy et al. (2014), we create three distinct instances based on a n = 280-city problem (a 280-dimensional permutation space). These instances feature a large number of items with varying properties: (1) m = 279 items with uncorrelated weights; (2) m = 837 items with bounded strong correlation in the weights; and (3) m = 837 items with uncorrelated weights. These benchmarks provide strenuous test for our proposed MergeBO and the baseline BOPS-H. Notice that the TTP is hybrid space problem, we modified both MergeBO and BOPS-H H by multiplying RBF kernel on the {0, 1)" discrete space:
KrTP((T,O), (H', o')) = K(T, "n,,")) x')Knnr(o,d))
Where a is the item picking strategy. The neighbouring permutation search method for BOPS-H is computationally infeasible on such vast space. Therefore, we adopt continuous relaxation approach, treating the entire set of optimization variables (T, ar) as a continuous vector for gradient- based optimization, and the result is subsequently projected back to the nearest permutation and binary vectors.
Crucially, this relaxation approach relies on the existence of feasible projection from the contin- uous feature space back to the permutation space. While our Merge kernel features preserve the structural logic of the sorting algorithm to allow for valid reconstruction, the randomized baseline lacks this structural consistency (e.g., potentially inducing cyclic or conflicting comparisons). Con- sequently, a valid projection for the randomized baseline is ill-defined, rendering it inapplicable to this high-dimensional optimization setting.
All experiments the El acquisition function. Each benchmark is evaluated with 50 independent trials, each consisting of 55 iterations (5 iterations of random initialization and 50 iterations of optimization). The random seed for each trial is set its trial index.
4.1.3 EVALUATION METRICS
In this study, we employ two evaluation metrics: the final simple regret and the area under the best-so-far regret curve (AUC). In optimization, regret defined as the difference between the best objective value observed to date and the global optimum:
best
Ft
7

---

Published as a conference paper at ICLR 2026
Table 1: Feature length comparison of Merge and Mallows kernel over problems of different scales.
Problem
Dimension
Merge feature length
Mallows feature length
TSP
15
45
105
QAP
15
45
105
FP
30
119
435
CR
30
119
435
TTP
280
2009
39060
Following this concept, the final simple regret is the regret value obtained in the last iteration and reflects the algorithm's 's ultimate optimization capability when computational cost is disregarded. By contrast, the regret AUC, or cumulative regret- the (area under the curve) of the simple regret across all iteaatins-qqanttffes the convergence speed of the entire optimization process:
AUCT Er,
Generally speaking, the final simple regret and AUC represent different, valuable aspects of an algorithm's 's performance: the former represents the the quality of the solution it ultimately finds while the latter represents the "journey", or convergence speed during optimization. For sample- efficient methods like BO, these two evaluation metrics standard practices as they allow for comprehensive comparison.
Table 2: Performance comparison between MergeBO, BOPS-H (Mallows kernel), BOPS-H with random comparisons and TuRBO. Underlined results indicate the best numerical results in terms of mean value + standard deviation of all trials, and bold font indicates statistically significant superi- ority of MergeBO against BOPS-H as determined by binomial sign test (p 0.05, corresponding to more than 15 wins of 20 trials).
Problem
Simple final Regret
Regret Wins
Merge
Mallows
Random
TukBO
Merge Wins
Ties
Mallows Wins
TSP
0.077 0.125
0.013 0.039
0.332 18.1 10
0.329
1.213 0.879
QAP
14.9 5.5 x 10a
8.1 4.1 x 10²
14.2 5.9 10a
3
16
24.0 9-7
30.1 + 12.8
35.7 11.2
20.5
10
4
6
CR,
6.1 2.2.
6.1 1. 3.0
52.15 1. 19.0
33.85 1. 15.7
8
TTPI T-21,=200
23.0
11.3 x 10a
88.9 7.5 x 10
54.8 12.6 x 10"
50
0
0
TTP2,-250
14.9
7.2 10
56.5 1 6.1 x 10
36.8 1. 9.4 10
50
0
8.0 3.2
10
2.8 10'
10"
50
Problem
Best so far AUC
AUC Wins
Merge
Mallows
Random
TuRBO
Merge Wins
Ties
Mallows Wins
TSP..15
527.6 + 162.8
428.2 + 121.9
559.7 = 224.9
877.2 +: 352.4
5
0
15
QAP
38.3 1. 8.4 x 10a
27.5 L. 7.4 10
42.5 1. 6.1 10
46.7 -1: 9.2
2
8097.5 2163.7
8665.7 2638.8
94810 2086.2
5032.1 1636.9
CR
5495.6 +: 687.7
5350.5 +: 910.1
13970.8 2408.8
103400.5 2477.5
8
0
12
TTP nim200
20.5 x 10"
48.5 10P
40.0 4.9 109
50
0
0
250
12.3
10"
30.5
10"
25.9
TTP3
6.7.1.44 10"
15.2 1.3 10"
13.2 :1: 1.5 10
50
0
It is important to note that this study does not include comparison of wall-clock computation times. This is deliberate choice grounded in the fundamental premise of BO, where the cost of function evaluations (e.g., physical experiments or complex simulations) is assumed to far outweigh the computational cost of the algorithm itself. Consequently, our analysis prioritizes metrics related to sample efficiency, which is the primary bottleneck in such real-world scenarios. As more sta- ble and implementaaiionagnnsst proxy for computational complexity, we instead report the feature vector dimensions generated by each kernel in Table [ which directly reflects the compactness of the learned representations. Furthermore, as our experiments were conducted on a shared high- performance computing (HPC) cluster, reported wall-clock times would be subject scheduler- induced variability, making them an unreliable metric for rigorous algorithmic comparison.
Instead, report rough time estimation based local, small-scale experiments here: the Merge kernel is approximately 10% slower than the Mallows kernel in www-dimensional problems. This is because the Mallows kernel's calculation relies on two clean for-loops, whereas the Merge
8

---

Published as a conference paper at ICLR 2026
50000
Merga
Fandom Compartion
Smn fogge: Sreaa 3240
Random Comparteon
160030
30
20000
20030
20030
23
202
125
275
202
Rerstin
(a) TSP (a=15)
(b) QAP (a=15)
275
Merga
Fandom Compartion
Randon Compactton
LR50
1,180
2000
100-
to.
50
200
175
202
25
50
102
125
150
175
Rerot
(c) Floor planning (n=30)
(d) Cell placement (n=30)
Merga
Merge
Marge
1.2
1.2
Strple 3etd
-0.4
BAABO
0.8
0.8-
0.8-
-1.
0.6-
-12
0.4
-14
0.2
0.2
10
20
30
50
10
20
50
10
20
30
50
Iterationn
Beration
lteration
(e) TTP (1)
TTP (2)
(g) TTP (3)
Figure 2: Low- and high-dimensional results comparing Mallows kernel (BOPS-H H)) and Merge ker- nel (MergeBO) on the current regret value (difference between best-so-far and optimal value) number of iteration. Solid lines show the average regrets, while the shaded areas denote one stan- dard deviation.
kernel requires recursive calls to Merge Sort, which involves significant constant overhead from function calls, Python list slicing, and deepcopy operations. However, high-dimensional prob- lems, we believe the kernel value computation bottleneck arising from the O(n²) feature space will lead to significant performance degradation.
4.2 RESULTS AND DISCUSSION
Our experimental results, as presented in Table Figure systematically reveal strong correla- tion between the performance advantage of the Merge kernel and the problem's dimensionality. For low-dimensional permutation problems (TSP and QAP), the Mallows kernel, which is specifically designed for such tasks, exhibited a slight performance advantage. However, on problems of inter- mediate dimensionality (FP and CR), the performance of the two kernels was comparable, with no statistically significant difference observed. This trend shifted decisively on the digherrdimensional TTP problems, where the Merge kernel demonstrated definitive superiority. The statistical data in Table 2 indicates that the Merge kernel significantly outperformed the Mallows kernel across all TTP instances both the final regret and AUC metrics. Furthermore, the convergence curves in

---

Published as a conference paper at ICLR 2026
Figure 2 confirm its substantially faster convergence speed. This validates the superior performance and scalability of our proposed method on complex, high high-dimensional optimization problems.
The consistent underperformance of the randomized baseline confirms that unstructured feature lection fails to capture necessary permutation similarities. This validates that our method's ' efficiency stems from preserving principled structural information, rather than mere dimensionality reduction. Regarding TuRBO, while it demonstrates scalability by outperforming BOPS-E H in high-dimensionn tasks, remains significantly inferior our method. This substantial gap underscores the necessity of our specialized permutation optimization framework over generic continuous relaxation strategies and general digensinenio optimization approaches.
These results corroborate our core hypothesis: the Merge kerel possesses an inherent advantage in sigh-dimensional permutation optimization problems, owing to more compact structural design. The disparity between its On log n) feature complexity and the Mallows kernel's O(n²) complexity widens dramatically as the dimensionality n increases. This is explicitly quantified by the feature length comparison in Table D for low, intermediate, and high-dimensional problems, the feature dimensionality of the Mallows kernel approximately 2, 3.5, and 19.5 times that of the Merge kernel, respectively. These results indicate that the experimental performance is governed by trade-off between two key factors: (1) the ability to capture global information via the distance metric, and (2) the search efficiency driven by the compactness of the feature space. Due to its right-invariance property, the Mallows kernel possesses a stronger distance metric capability than the Merge kernel. However, dimensionality increases, the vast disparity in feature vector length leads to a more pronounced space-compression effect. The resulting gains in search efficiency begin outweigh the performance benefits afforded by the superior distance metric. Consequently, as the problem dimensionality continues to grow, the performance of the Merge kernel ultimately surpasses that of the Mallows kernel by significant margin. This naturally suggests a peneension-dependenn heuristic for practitioners: leveraging the Mallows kernel's robust, right-invarian distance metric for low-dimensional tasks, while switching to the Merge kernel to capitalize on its superior scalability in high-dimensional regimes.
CONCLUSIONS
In this work, we proposed a novel kernel construction framework for permutation spaces by leverag- ing sorting algorithms as structured comparison schemes. Within this framework, we introduced the Merge kernel an efficient, compact, and theoretically grounded alternative to the quadratic Mal- lows kernel. We showed that the Merge kernel achieves the information-theonn feature complexity while preserving meaningful structural information. This contribution bridges sorting theory and kernel design, revealing a fundamental trade-off between a model's structural invariance and the compactness of its feature space.
lower bound on
Empirical experiments confirmed this trade-off: while the BOPS-H algorithm held a marginal advantage in low-dimensional problems, their performances were comparable on intermediate- dimensional tasks. In high-dimensional settings, however, MergeBO's compact representation en- abled far superior search efficiency, allowing it to sigmificantly outperform BOPS-H and TuRBO. This work opens exciting possibilities for scaling Bayesian optimization to larger permutation spaces. Future directions include exploring other sorting algorithms with constant comparison counts or constructing stabilized sorting algorithm of O(n log n) complexity for kernel design, and applying this framework to challenging real-world domains like combinatorial neural architecture search and computational biology.
6 ACKNOWLEDGGMEETS
The computational resources for this work were provided by the robotic Al-Scientist platform of the Chinese Academy of Sciences (CAS). The authors thank Dr. Xenophon Evangelopoulos (University of Liverpool) for insightful early discussions and for raising questions regarding right-invariance, which helped clarify the limitations of earlier approaches.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wil- son, and Eytan Bakshy. Botorch: framework for efficient monte-carlo bayesian optimization. Advances in neural information processing systems, 33:21524-21538, 2020.
Nathalic Bartoli, Thierry Lefebvre. Rémi Lafage, Paul Saves, Youssef Diouane, Joseph Morlier, Jasper Bussemaker, Giuseppa Donelli, Joao Marcos Gomes de Mello, Massimo Mandorino, al. Multi-objective bayesian optimization with mixed-categorical design variables for expensive-to- evaluate aeronautical applications. arXiv preprint arXiv:2504 09930, 2025.
Kenneth E Batcher. Sorting networks and their applications. Proceedings of the April 30-May 2, 1968, spring joint computer conference, pp. 307-314, 1968.
Mohammad Reza Bonyadi, Zbigniew Michalewicz, and Luigi Barone. The travelling thief problem: The first step in the transition from theoretical problems to realistic problems. In 2013 JEEE congress evolutionary computation. pp. 1037-1044. IEEE, 2013.
Rainer E Burkard, Stefan E Karisch, and Franz Rendl. Qaplib-a quadratic assignment problem library. Journal of Global optimization, 10:391 403, 1997.
Shuai Che, Michael Boyer, Jiayuan Meng, David Tarjan, Jeremy W Sheaffer, Sang-Ha Lee, and
Kevin Skadron. Rodinia: benchmark suite for heterogeneous computing. In 2009 IEEE inter- national symposium on workload characterization (IISC),, pp. 44-54, Icee, 2009.
Aryan Deshwal, Syrine Belakaria, Janardhan Rao Doppa, and Dac Hyun Kim. Bayesian optimiza- tion over permutation spaces. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pp. 6515-6523, 2022.
Persi Diaconis and Ronald L Graham. Spearman's footrule as measure of disarray. Journal of the Royal Statistical Society Series B: Statistical Methodology, 39(2)262-2268, 1977.
David Eriksson, Michael Pearce, Jacob Gardner, Ryan Turner, and Matthias Poloezek. Scalable global optimization via local bayesian optimization. Advances in neural information processing systems, 32, 2019.
Jacob Gardner, Geoff Pleiss, Kilian Q Weinberger, David Bindel, and Andrew Wilson. Gpytorch: Blackbox matrix-matrii gaussian process inference with gpu acceleration. Advances in neural information processing systems, 31, 2018.
Eduardo C Garrido-Merchal and Daniel Hernández-Lobate Dealing with categorical and integer- valued variables in bayesian optimization with gaussian processes. Neurocomputing, 380:20-35, 2020.
Joan Gonzalvez, Edmond Lezmi. Thierry Roncalli, and Jiali Xu. Financial applications of gaussian processes and bayesian optimization. arXiv preprint 14Xx:19903.04411, 2019.
Stewart Greenhill, Santu Rana, Sunil Gupta, Pratibha Vellanki, and Svetha Venkatesh. Bayesian optimization for adaptive experimental design: A review. IEEE access, 8:13937-13948, 2020.
Mara Guidi, Peter H Seeberger, and Kerry Gilmore. How to approach flow chemistry. Chemical Society Reviews, 49(24):8910-893) 2020.
Abhishek Gupta, Yew-Soon Ong, and Liang Feng. Multifactorial evolution: Toward evolutionary multitasking, IEEE Transactions Evolutionary Computation, 2433):34 2015.
Yunlong Jiao and Jean-Philippe Vert. The kendall and mallows kernels for permutations. In Inter- national Conference on Machine Learning, pp. 1935-1944. PMLR, 2015.
Maurice G Kendall. A new measure of rank correlation. Biometrika, 30(1 (0(1-)):1193,, 1938.
Donald E. Knuth. The art of computer programming. Sorting and searching. 3(426-458):4, 1999.
Dennis KJ Lin and Nicholas Rios. Order-of-addiiee experiments: A review and some recommen- dations. Wiley Interdisciplinary Reviews: Computational Statisties, 17(2):470024, 2025.

---

Published as a conference paper at ICLR 2026
Man Luo, Zikai Xie, Huirong Li, Baicheng Zhang, Jiaqi Cao, Yan Huang, Hang Qu, Qing Zhu, Linjiang Chen, Jun Jiang, et al. syssics-informed, dual-objective optimization of high-entropy- alloy nanozymes by robotic ai chemist. Matter, 8(4), 2025.
James Mercer. Xvi. functions positive and negative type, and their connection the theory of integral equations. Philosophical transactions the royal society London. Series A, containing papers of a mathematical or physical character, 209(441-458):4155444
1909.
Dang Nguyen, Sunil Gupta, Santu Rana, Alistair Shilton, and Svetha Venkatesh. Bayesian opti- mization for categorical and category-specific continuous inputs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5256-5263, 2020.
Changyong Oh, Jakub Tomezak, Efstratios Gavves, and Max Welling, Combinatorial bayesian opti- mization using the graph cartesian product. Advances in Neural Information Processing Systems, 32, 2019.
Changyong Oh, Roberto Bondesan, Efstratios Gavves, and Max Welling. Batch bayesian optimiza- tion permutations using the acquisition weighted kernel. Advances in Neural Information Processing Systems, 35:6843-6858, 2022.
Sergey Polyakovskiy, Mohammad Reza Bonyadi, Markus Wagner, Zbigniew Michalewicz, and Frank Neumann. A comprehensive benchmark set and heuristics for the traveling thief prob- lem. In Proceedings of the 2014 annual conference genetic and evolutionary computation, pp- 477 484, 2014.
Gerhard Reinelt. Tsplib95. Interdisziplindies Zentrum für Wissenschaftliches Rechnen (IWR), Hei- delberg, 3-8:1-16, 1995.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1):
148-175, 2015.
Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando De Feitas. Bayesian op- timization in billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55:361-387, 2016.
Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
Jia Wu, Xiu- Yun Chen, Hao Zhang, Li-Dong Xiong, Hang Lei, and Si-Hao Deng. Hyperparameter optimization for machine learning models based on bayesian optimization. Journal of Electronic Science and Technology, 17(1):26-40, 2019. 2011.
Zikai Xie, Xenophon Evangelopoulos, Joseph CR Thacker, and Andrew I Cooper. Domain knowl- edge injection in bayesian search for new materials. In ECAI 2023, pp. 2768-2775. IOS Press, 2023.
Martin Zaefferer, Jörg Stork, and Thomas Bartz-Beielstein. Distance measures for permutations in combinatorial efficient global optimization. In International Conference Parallel Problem Solving from Nature, pp. 373-383. Springer, 2014.
A THE USE OF LARGE LANGUAGE MODELS
We declare that the large language models (LLMs) ChatGPT and Gemini are only used to aid and polish writing. No further upplications of LLMs are used this research, including but not limited to retrieval, research ideation and experiment designing.
12

---

Published as a conference paper at ICLR 2026
B EXTRA DISCUSSIONS
B.1 DISCUSSION ON SORTING ALGORITHM CHOICES
Thanks to the fixed comparison map constraint, not every sorting algorithm can induce a valid fea- ture mapping suitable for kernel construction. This is because the mapping from permutations fea- ture space must yield feature vectors of fixed length; otherwise, feature vectors of differing lengths would not be compatible with the RBF kernel. Hence, only sorting algorithms that have a fixed comparison path and a constant number of comparisons across all inputs can generate valid feature mappings, e.g., a fixed sorting network with a predetermined comparator sequence [Batcher] (1968). This strict constraint allows us to exclude the vast majority of O log complexity sorting algo- rithms that are stochastic or adaptive, such as quicksort, heapsort, and standard Merge Sort, since their comparisons are data-dependent, not fixed. Nevertheless, Merge Sort could be exception: although typically Merge Sort ceases comparisons once all elements from one subsequence have been merged, redundant comparisons be artificially introduced during the merge procedure, sulting in a fixed number comparisons L + - 1, where L and R are the length of the two subsequences. This ensures that both the comparison path and the number of comparisons remain identical across different permutations, thus establishing a fixed comparison path.
Stabilizing the comparison map of other O(n.lgg n) sorting algorithms is quite challenging, and other (n²² sorting algorithms are equivalent to Mallows kernel. At the moment we can confirm that Bitonic Sort satisfy the above constraint: the comparison maps of permutations are fixed and identical according their length. Given its (n log" n) complexity, we excluded this algorithm from the present study, but we consider it a viable direction for future extensions of this framework.
B.2 DISCUSSION ON INFORMATION-
LOWER ROUND
It is important to clarify that the feature vector lower bound discussed in this paper refers to the information- lower bound on the number pairwise comparisons required to reconstruct the relative order of two permutations, i.e., the lower bound implied by lossless information com- pression. This should be distinguished from the algorithmic lower bound for computing a distance regarding to the original permutations. For example, the Mallows kernel relies the Kendall- dis- tance, and although the latter can be computed in ( log n1) time using algorithms such as modified Merge Sort, this does reduce the information requirement to On lo. Such algorithms still implicitly depend on the relative order of all Onn²) pairs of elements, but accelerate computation by batch processing rather than by reducing the underlying information model. In contrast, our method does not require explicit access to all (n²)) pairs. Instead, it achieves a complete reconstruction of the relative order using only O(n log n) pairwise comparisons.
B.3 DISCUSSION ON SPEARMAN'S FOOTRULE
To evaluate the trade-off between permutation information, dimension reduction and right- invariance, employ Spearman's footruleDiaconis & Graham (1977) distance another bench- mark baseline. Similar to Euclidean measures on raw coordinates, Spearman's footrule operates directly on the permutation group Sn. Formally, for two permutations (rankings) a and of n el- ements, the distance is defined as the sum of the absolute differences between the ranks of each element:
divoorute (2t, x²)
lrs r/1
(6)
1=1
Obviously, the corresponding featurization method 4 footrate (T) is an identical mapping that di- rectly uses the permutation w its feature vector. The computational complexity of Spearman's footrule is Onn), and fully right-invariant since it simply calculates the L1 distance between two vectors.
However, while this mapping retains the raw rank values, it treats permutations merely as vectors in Fuclidean space, thereby ignoring the underlying algebraic structure of the symmetric group.
13

---

Published as a conference paper at ICLR 2026
Table 3: Performance comparison between MergeBO, BOPS-H (Mallows kernel,, BOPS-H with random comparisons, TuRBO and Spearman's 's footrule. Underlined results indicate the best numer- ical results in terms of mean value standard deviation of all trials.
Problem
Simple final Regret
Merge
Mallows
Random
TuRBO
Spearman
T5
0.077 + 0.125
0.013 = 0.039
0.329 0.332
1.213 0.879
0.026 + 0.052
QAPR-15
14.9 + 5.5 10
8.1 10
18.1 8 10
14.2 5.9 x 10
10.2 4.7 x 10
FP 800
24.0 1: 9.7
30.1 + 12.8
35.7 + 11.2
20.5 +: 8.4
34.6 1 9.0 1.5 + 2.4
CR,,a0
6.1 + 2.2
6.1 + 3.0
52.15 + 19.0
33.85 + 15.7
TTP 280
23.0 11.3
10
88.9 7.5
10
54.8 12.6 10
88.7 + 10.1
10
280
14.9
7.2 10
56.5 6.1
104
36.8
104
56.2 6.2
10
288
3.0 10
28.1
2.8
10a
19.1 = 3.6
10a
28.4 2.5 x 10
Problem
Best so far AUC
Merge
Mallows
Random
TuRBO
Spearman
TSP 1-16
527.6 + 162.8
428.2 + 121.9
559.7 224.9
877.2 :: 352.4
397.1 + 98.0
QAP 1-15
8.4 10
27.5 7.4 10
42.3 6.1 10
46.7 +.2 10
31.8 8.5 x 10
8097 3 + 2163.7
8665.7 = 2638.8
9481.0 + 2086.2
5932. +: 1636.9
9187.7 1 2024.1
CR,-30
5495.6 + 687.7
5350.5 + 910.1
13970.8 + 2408.8
10340.55 +: 2477.3
4673.4 = 1020.15
TTPI 280
20.5
10
48.5 3.1 10
40.0 + 4.9 10
48.2 4.3 x 10
TTP2, 280
12.3 12.3+304 3.2 106
30.5 2.4 10
25.9 = 3.8 108
30.3 2.4 10
2-50
6.7 1.4 10"
15.2 1.3 10
13.2 1 10
15.3 x 10
Unlike the Mallows kernel or our proposed Merge kernel, which embed specific probabilistic or hierarchical priors, this naive representation doesn't It project the permutation compact manifold and fails to capture the compact dependencies within the feasible space. Nevertheless, its L₁ nature allows effectively approximate local structural discrepancies through simple summation.
The experiment results of Spearman's footrule are added in Table above. In now-dimensional set- tings, Spearman's 's footrule performs slightly worse than the Mallows kernel but marginally better than the Merge kernel. This can be attributed to the high relevance of right-invariance lower di- mensions, where accurately measuring the similarity between local ilar performance characteristic--is critical. Notably, the method exhibits rapid convergence on TSP and CR tasks, stemming from the inherent local additivity of these problems. However, Spearman's footrule offers lower discriminative resolution for permutations compared to the Mallows kernel. This coarser granularity tends to bias the search towards exploitation rather than exploration; while this enables quick convergence to local optima, it may limit the model's 's ability to escape them for global solution.
often share sim-
Conversely, in high-dimensional problems, Spearman's 's footrule performs comparably to the Mal- lows kernel but significantly lags behind the Merge kernel. This stark contrast highlights the Merge kernel's s superior capability to compress high-dimensional search spaces and accelerate optimization through hierarchical decomposition.
14


Reviews:
[{"review_id": "LsE6UXCgYE", "reviewer": "Reviewer_W1JA", "summary": "This paper addresses the scalability issue of Bayesian Optimization (BO) over high-dimensional permutation spaces by proposing a novel sorting algorithm-based kernel design framework. This framework sophisticatedly generates fixed-length feature vectors for permutations via the internal binary comparison results from any sorting algorithms, which theoretically interprets the traditional Mallows kernel as its special case with an $O(n^2)$ feature dimension. Based on this framework, the authors further propose a novel Merging Sorting-based kernel (i.e., Merge kernel), with only $O(n \\log n)$ feature dimensions. Incorporating the proposed kernel, permutations can be assigned theoretically shortest features with limited information loss, which achieves the lower bound from the perspective of information theory. Experiments show that the proposed kernel can achieve competitive performance than the traditional Mallows kernel on both low-dimensional and high-dimensional problems, yet with better convergence speed and final regrets, providing potential solutions for large-scale permutation optimization problems such as feature sorting or neural architecture searching.", "questions": "1. Can we design a technique to randomly select and record the binary comparison? Can the proposed Merging kernel be further improved by incorporating some stochastic binary comparisons? Or can the authors give a further analysis on which pairs of comparisons are critical for a given permutation optimization problem? Based on this analysis, can we add some extra important yet limited number of binary comparisons (e.g., top-K important pairs) to supplement the information loss of permutations due to the loss of right-invariance?\n\n2. See Weakness.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper addresses a critical challenge for Bayesian Optimization over permutations, showing potential in efficient permutation encoding and searching.\n\n2. The idea is novel and interesting. The authors are the first to incorporate traditional sorting algorithms into permutation kernel design, forming a powerful and general framework. It provides a new paradigm for kernel functions over permutation spaces.\n\n3. The motivation is clear and easy to follow. The proposed general framework interprets the traditional Mallows kernel as a special case, which reveals the intrinsic limitation of prior techniques and well motivates the proposed kernel design.\n\n4. The proposed kernel is efficient and can generate the shortest permutation encodings, achieving the theoretical information lower bound. This would pave the way for future exploration of complex, large-scale permutation-related combinatorial optimizations.", "weaknesses": "1. While the authors propose a kernel based on Merging Sort and achieve competitive performance, the generality of the selection of sorting algorithms can be discussed in more detail, especially for some stochastic sorting algorithms that contain non-fixed times of binary comparisons. In other words, since the authors make connections between the traditional sorting algorithms and the permutation kernel, readers may be interested in how different properties of sorting algorithms affect the performance.\n\n2. I recommend that the authors conduct a further scaling experiment, in which the explicit relationship between the permutation scale and running time can be studied. This exploration would provide valuable suggestions for practitioners to check whether the proposed framework is suitable for their real-world problems.\n\n3. The quality (in latex) of tables can be significantly improved, e.g., Tab. 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "R4zhkQY5VW", "reviewer": "Reviewer_T7An", "summary": "The paper shows how sorting algorithms can direct the design of GP kernels for permutation spaces, and that in particular merge sort produces a MergeKernel that can be used for compact modeling in high-dimensional permutation spaces.\n\nThe baseline method (the Mallows kernel) has a higher-dimensional representation and performs worse for BO.", "questions": "*  What do the effects of loss of right invariance look like in practice?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces what is to my knowledge a novel connection between sorting algorithms and permutation kernels. This connection is very interesting, original, and useful.\n\nThe fact that the primary existing permutation falls out as a special case in this framework is very interesting and provides strong validity for thinking about permutation kernels this way.\n\nThe paper is clear and well written.", "weaknesses": "The empirical evaluation is not completely satisfying.\n- Of five problems, only 2 shows significant differences between the methods. The conclusion would be that most of the time it doesn't matter what kernel you use? I recommend trying to expand the set of problems further to include more with clear differences in performance. The paper hypothesizes that the MergeKernel does better in high-dimensional spaces, but I did not find that very convincing based on a signal of just 2 of 5 problems having different performance. Please add a couple more high-dimensional problems to confirm the hypothesis that MergeKernel is important and better in high-dimensional settings.\n\n* Comparison is only with the Mallows kernel. The paper tries to justify this by saying that it is focused specifically on sorting-based methods, and so only needs to compare sorting-based methods. But I don't think that is correct. The end of the introduction states \"Our results demonstrate that the Merge kernel provides a practical and efficient tool for permutation optimization, significantly enhancing BO’s applicability to diverse AI scenarios.\" So, the paper is claiming that the method \"significantly enhances\" BO for permutation optimization. Generally, not just compared to only other sorting-based methods. The paper does not provide evidence for that claim. The paper mentions TurBO - it has an implementation available and is fast to run and may work well in the high-dimensional spaces where Mallows kernel performed poorly. Running that on the benchmark problems would significantly strengthen the results.\n\n* One other example of a kernel derived from a sorting algorithm would really emphasize the generality of the result.\n\n* The paper describes that the merge kernel is not invariant under right multiplication and that as a result it \"sacrifices a certain degree of performance.\" I don't have good intuition for what type of issues that will cause downstream in the BO, I think it would be helpful to give some examples in the paper of how lack of right invariance can cause modeling difficulties.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DEcShK9QUk", "reviewer": "Reviewer_gPDf", "summary": "The authors propose a new embedding of permutations to parameterize an RBF kernel, and compare bayesian optimization against kernels using simpler / slower permutation embeddings.", "questions": "Would it be possible to consider a simple randomized baseline version of the Mallow kernel?  A small concern I have with the method is that, because it’s not super clear what distance the Merge kernel captures, it may be introducing some extra element of stochasticity that is helpful for exploration in BO.  A comparison to a version of the Mallow kernel where one randomly selects O(n \\log n) features out of the total O(n^2) features and only uses these for the permutation embedding would be a useful benchmark to show the proposed method is doing something more substantial, and that one couldn’t naively get the reduced complexity.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The method is very well-motivated and performs well on the high-dimensional setting, and stays competitive on the smaller dimensional tasks.  I’m also happy the authors acknowledged the lack of right-invariance of the method, which doesn’t invalidate the embedding but at first blush looks a little surprising.  Their discussion of sacrificing this property for the sake of a fast method is convincing.", "weaknesses": "I’m somewhat surprised the authors didn’t benchmark with other notions of permutation distance, for example they mention Spearman’s footrule on page 5, and there are other notions like the Cayley distance.  The results would I think be a bit stronger if it was demonstrated that a new notion of distance between permutations is strictly necessary to get better performance in bayesian optimization.\n\nThe lack of right invariance is still concerning, mainly as it makes it very difficult to interpret what the difference between merge embedding is actually calculating.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dAdbAC1oUo", "reviewer": "Reviewer_ctDW", "summary": "This paper addresses the problem of black-box optimization over permutation spaces. Such problems play a role, for instance, in compiler optimization or chip design, where one searches for a permutation that optimizes some quantity of interest, which is expensive to evaluate. Bayesian optimization (BO) is a popular technique for black-box optimization, but has received little attention in the context of permutation spaces. A popular exception is [1], which uses the Mallows (BOPS-H) and Kendall kernels (BOPS-T) discussed in [2] to perform Bayesian optimization over permutation spaces. BOPS-H performs considerably better and is defined in terms of the number of discordant pairs, resulting in $\\frac{n^2-n}{2}$ possible candidates.\n\nIn this paper, the authors propose a different approach. Given some permutation, they employ merge sort to transform the permutation into the identity permutation and construct a feature vector by appending a 1 if, during a merge operation, an element is chosen from the left vector, and a -1 otherwise. This way, the number of possible candidates is reduced to $\\mathcal{O}(n\\log n)$ (worst-case complexity of merge sort). Since this representation does not capture all invariances the Mallows kernel exhibits, the authors apply three tricks to augment the feature vector with additional features that are designed to capture such invariances, such as right-, cyclic-rotation, and cyclic shift invariances.\n\nThe authors compare their method to BOPS-H and show that it achieves better simple regret and regret AUC values. They further conduct an ablation study to study the effect of the additional 'invariance'-features, showing that the 'shift-histogram module' leads to the highest performance degradation upon removal, indicating that it is the most expressive added feature.", "questions": "- Clearly, the $\\Phi_{\\textrm{Mer}}$ feature vector does not capture invariances (as acknowledged by the authors), motivating the need for additional features. Does $\\Phi_{\\textrm{Mal}}$  have similar shortcomings? How do they relate to\n?\n- In the conclusion, what do you mean when saying that gradient methods could exploit the lower-dimensional feature space?\n\nOther comments:\n\n- For the ablation study, it would be interesting to see the performance without any tricks.\n- It shouldn't be hard to construct an ARD version of Eq. 4, potentially sharing one length scale for $\\Phi_{\\textrm{Mer}}$ and using separate length scales for $\\Phi_{\\textrm{Spi}}$, etc. Studying their length scales would make it easier to quantify the importance of each feature group and might even improve performance.\n- Eqs 1 and 3 are only equal when re-scaling $\\ell$.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper addresses a relevant but little-discussed problem setting.\n- The paper is mostly clear and well-written.\n- The paper clearly defines the boundary between related work and its own contribution.\n- The proposed approach outperforms the state-of-the-art in BO over permutation spaces.", "weaknesses": "- While the approach is smart, it is hard to get an intuition for the feature vectors proposed in this paper. A '-1' or '1' in the $\\Phi_{\\textrm{Mal}}$ vector has an easy-to-grasp interpretation. In contrast, the $\\Phi_{\\textrm{Mer}}$ feature vector is a concatenation of features originating from different levels in the merge-sort operation.\n- The addition of the 'tricks' makes this work seem more heuristic than BOPS-H.\n- While the proposed approach outperforms BOPS-H, it only does so by a slight margin. The differences between BOPS-H and COMBO, for instance, are considerably larger than the difference of 'Merge' to BOPS-H, which, judging from the figures and tables, could be a coincidence. The paper is not very critical about its empirical performance.\n- The explanation of the additional features is quite brief. Some examples would make it easier to understand their design.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)