acceptodds
Under review as a conference paper at ICLR 2027

Revisiting Vanilla Bayesian Optimization in High-Dimensional Permutation Spaces

Abstract

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.

Primary area:
optimization
Keywords:
Bayesian optimization, permutation space, high-dimensional optimization

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_MmJdOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3(+2)
Read review
Paper summary

Motivated by recent discussions in the Bayesian optimization (BO) community on applying vanilla BO to high-dimensional search spaces, the authors investigate the performance of vanilla BO in high-dimensional permutation spaces and find that it does not work effectively out of the box. They attribute this failure to geometric collapse in high-dimensional permutation spaces, and further examine the associated topological ruggedness and surrogate fragility. Based on these observations, the authors propose VaPBO, which combines three key components: (1) a dropout-style variable selection strategy, which randomly selects a permutation subspace and performs optimization within that subspace, thereby substantially reducing the difficulty of the optimization problem; (2) subspace modeling with the Merge kernel, which constructs the distance metric in a divide-and-conquer manner and enables the most compact vector representation for permutation spaces; and (3) a structure-aware fill-in strategy, which addresses how elements in the complement of the optimized subspace should be selected when reconstructing a full permutation. Experimental results show that VaPBO with greedy local search achieves strong performance across a broad range of tasks, while the different VaPBO variants generally remain among the top-performing methods.

Overall, assuming that the reported performance is supported by a valid and fair evaluation, this work may not represent a ground-breaking methodological advance, but it presents a well-motivated and internally coherent approach to high-dimensional permutation optimization. The proposed components are naturally connected to the identified challenges of the search space, and the reported results suggest that VaPBO can achieve strong and consistent performance across a broad range of benchmark problems.

Critical strengths
  1. The paper identifies an important limitation of directly transferring the recent success of vanilla BO in high-dimensional continuous spaces to high-dimensional permutation spaces. The authors provide a detailed discussion of why this transfer is nontrivial, which helps motivate the need for dimension-reduction strategies specifically designed for permutation optimization.

  2. Based on these observations, the authors combine several algorithmic components that have already demonstrated usefulness in related optimization settings to address the challenges of high-dimensional permutation optimization. These components are well aligned with the identified difficulties of permutation spaces and fit naturally within the general BO framework.

  3. Each algorithm–problem pair is evaluated over five independent random seeds. Although five runs are still relatively limited for robust statistical comparison, the use of repeated runs is nevertheless preferable to reporting results from a single trajectory and provides at least some indication of performance variability.

Critical weaknesses

I have one major concern regarding the paper, and I consider it substantial because it may affect the validity of the reported experimental comparison.

In the released code, for example in ./tsp_synthetic/tsp_merge_dropout.py, the fillin_strategy object appears to be instantiated outside the loop over independent runs:

fillin_strategy = fillin_strategy_factory[fillin_type]

for nruns in range(n_runs):
    torch.manual_seed(nruns)
    np.random.seed(nruns)
    print(f'Input dimension {dim}, active_dims {active_dims}')
    train_x = torch.from_numpy(
        np.array([np.random.permutation(np.arange(dim)) for _ in range(n_init)])
    )

If fillin_strategy is stateful and retains information such as the best filling permutation found during optimization, its internal state is not reset when a new run starts. Consequently, later runs may inherit information obtained from earlier runs. In that case, the nominally independent random-seed repetitions would no longer be truly independent, and later runs could potentially benefit from information that should not be available to them. I cannot infer from code alone how large the resulting performance inflation would be, or whether it materially changes the ranking of the methods. However, this implementation issue appears capable of introducing cross-run information leakage and therefore undermines the validity of the current repeated-run comparison.

I strongly encourage the authors to check and reset the fillin_strategy separately for every independent run and rerun the affected experiments. If VaPBO still maintains its reported top-tier performance after this issue is corrected, I would consider the experimental comparison more convincing and would be willing to raise my final score.

Questions for authors

Please check the fillin_strategy part of your code.

8 comments

Thank you for identifying the fill-in state issue. We have corrected it and evaluated the method with independent runs, as detailed below.

R4C1 Comment on cross-run fill-in state, independent reruns, and performance after correction

W1) I have one major concern regarding the paper, and I consider it substantial because it may affect the validity of the reported experimental comparison. In the released code, for example in ./tsp_synthetic/tsp_merge_dropout.py , the fillin_strategy object appears to be instantiated outside the loop over independent runs...

Q1) Please check the fillin_strategy part of your code.

Thanks for pointing out this critical issues! We have corrected the cross-run state-sharing path and re-run our methods. We also add five more independent runs to all the other methods and added two-sided Wilcoxon rank-sum tests at a significance level of 0.05 to our main results. The table below summarizes the average rank across eight high-dimensional tasks and the number of task-level comparisons with VaPBO-GLS. Lower average rank is better.

MethodAverage rankVaPBO-GLS significantly betterNo significant differenceVaPBO-GLS significantly worse
Random8.875710
LS13.125800
GLS11.125710
SA9.750710
Vanilla BO (CR)5.875350
TuRBO (CR)3.500170
BOPS8.375620
Merge8.875710
Vanilla Merge9.125710
VaP-LS13.000710
VaP-GLS6.750440
VaPBO-Grad8.000710
VaPBO-EA6.250530
VaPBO-LS5.875530
VaPBO-GLS1.500———

VaPBO-GLS has the best average rank of 1.500, followed by TuRBO (CR) at 3.500. Across the 112 comparisons with the other 14 methods on eight tasks, the tests identify 81 significant differences in favor of VaPBO-GLS, 31 comparisons with no significant difference, and zero significant differences in favor of the compared methods.

The corrected independent-run evaluation retains strong performance, with VaPBO-GLS still achieving the best average. An archive carried over from earlier runs may be dominated by high-quality templates whose inactive-item orderings are poorly suited to the active-item assignments explored in the current run. Resetting the archive allows completion to adapt to the current run's evaluated solutions, providing a plausible explanation for why the correction can also improve search performance.

We also added the following experiments to evaluate performance after the correction and examine the contributions of the framework.

  • Independent runs across eight tasks. We compared VaPBO-GLS, the no-GP VaP-GLS variant, and simulated annealing over ten independent runs per method and task, with a fresh fill-in archive in each run. VaPBO-GLS has lower mean regret than both alternatives on all eight tasks.
  • Predictive accuracy. We recomputed MSE and predictive NLL using 80 shared training observations, common test inputs, and repeated fits. In the historical-pool comparison, VaPBO has lower mean MSE than all four full-space models on both application tasks, in both ID and OOD groups.
  • Completion quality. With active-item assignments fixed, Best-K improves mean candidate cost over random completion by 1.63% on TSP318 and 2.64% on QAP256 across five independent histories. This intervention directly tests how the fill-in rule uses the ordering information in evaluated solutions.
  • Modeling space and prior scaling. Dimension-scaled priors further lower the mean regret of VaPBO-Merge, showing that the framework can benefit from the vanilla BO prior design. A separate full-space/subspace comparison holds GLS, Best-K completion, and EI fixed under both prior choices, showing that the modeling-space effect depends on the task and prior.
  • Kernel choice. On TSP127 and TSP318, we evaluated full-space and VaPBO configurations with both Merge and Mallows over five independent runs with 50 evaluations per run. VaPBO has lower mean tour cost than the full-space baselines with either kernel on both tasks, showing that the framework also works with Mallows.
  • Discrete local BO. We expanded the CASMOPOLITAN comparison to TSP127, TSP318, TTP280, and QAP256, providing an additional comparison with a discrete trust-region method.

We hope our response has addressed your concerns. If we have missed anything, please let us know.

Reviewer_MmJdOpenReview ↗

Response to the authors

The authors corrected the code and performed extra experiments. The new results demonstrated the effectiveness of their method. I have no further question about this project, and I will raise my aassessment to 3.

Reviewer_rv34OpenReview ↗

Reply to Authors

Thank you for the thorough response and the new experiments. I especially appreciate that the authors were upfront about the scoring and aggregation bugs. The corrected NLL protocol, the matched controls, and the extra runs resolve several of my concerns (Q3, Q5, the wording in Section 3, and how the NLL evaluation was done). That said, I think the new results actually change what the paper can claim, and a few things still need clarifying before I can raise my score.

1. The new controls don't support the paper's main claim. In R3C4, the full-space Merge GP with the scaled prior beats the subspace model on TSP318 (-0.03 ± 1.96 vs. 3.06 ± 1.78), significantly. CASMOPOLITAN also does better on that task. On QAP256 the result flips depending on the prior. So once search and completion are held fixed, the vanilla lengthscale recipe does work on the largest task — which is the opposite of what the paper currently argues. The revised Figure 1 tells a similar story: the Merge concentration rate is order 1/sqrt(n log n) against 1/sqrt(n) for continuous distances. That's a logarithmic-factor difference, not the qualitative gap the original motivation described. Reading all of this together, my takeaway is that VaPBO's gains come mostly from GLS + Best-K completion + GP guidance, and the choice of modeling space depends on the task and the prior. That's a reasonable contribution, but it's a different one from the title. Could you revise the title, abstract, and Section 3 so the claims match the evidence? Right now the motivation and the conclusions point in different directions.

2. Which results were actually rerun? The fill-in archive bug means the original runs weren't independent across seeds. Does the updated Table 2 use fresh ten-run results for all 15 methods on all 8 tasks, or only for VaP-GLS, SA, and VaPBO-GLS, with the other methods kept from the affected five-seed runs? If it's the latter, the rank table mixes clean and contaminated results, and I don't think it can be presented as one comparison. Please spell out which entries were rerun, and post the full updated Table 2 rather than selected rows.

3. How were the significance tests done? For the 81/112 "nominal" significant comparisons: which test did you use, were runs paired by seed, and did you correct for multiple comparisons? Across 112 tests at alpha = 0.05 you'd expect 5–6 false positives by chance alone, and the 5-vs-5 comparisons in R3C4 can't survive Bonferroni even at the smallest possible p-value. BH-FDR-adjusted results, or at least the per-task p-values, would let readers judge for themselves. One more thing worth saying plainly: TuRBO (CR) differs significantly from VaPBO-GLS on only 1 of 8 tasks. The ranking gap over the strongest baseline looks mostly non-significant, and the paper should say so.

4. The predictive gaps are within noise as reported. The ID NLL differences are small next to the SDs — on Chip Placement, 1.4082 ± 0.0888 vs. 1.4155 ± 0.0895. Since all methods share the same splits, a paired test or confidence intervals on the paired differences would be much more informative. Without that, the ID claim rests on differences well inside the noise, and Vanilla Merge actually wins OOD NLL on Chip Placement. I'd tone down the predictive-advantage claim accordingly.

5. A few smaller items.

  • Why does CASMOPOLITAN have only seven runs? Could you complete ten and add significance tests? It would also be fair to comment on whether the Lehmer encoding hurts its trust-region locality.
  • The evolutionary baseline with order crossover wasn't added; SA alone only partly answers Q6.
  • For the two application benchmarks, please say explicitly in the paper that the task formulations are new contributions of this work, and share an anonymized repo link during the discussion. Describing the package layout isn't the same as committing to a release.

To be clear, I like the benchmarks and the component-wise experimental design, and again, the honesty about the bugs is appreciated. My remaining issue is that the corrected evidence supports a pipeline-level contribution rather than the current claim that vanilla BO fails on permutation spaces, and the statistics need the clarifications above. I'll keep my rating for now, but I'm happy to reconsider if the claims are realigned with the results and the rerun scope and testing details are cleared up.

Reviewer_rv34OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks whether recent results on "vanilla" Bayesian optimization carry over to permutation spaces. For continuous problems, those results show that plain GPs with well-scaled lengthscales match specialized high-dimensional methods. The authors argue that this does not carry over for permutation spaces. They first show that distances between random permutations concentrate as the number of items grows, and that full-space permutation kernels predict poorly on high-quality points. They then propose VaPBO. At each iteration, VaPBO picks a random subset of items, fits a Merge-kernel GP on their positions only, and optimizes the acquisition function over those positions. It then fills in the remaining items using the ordering from one of the best permutations found so far. The experiments cover TSP, QAP and the traveling thief problem, plus two new real-world tasks, chip placement and reconstructing biodiversity timelines from the fossil record, with up to 318 items. The method is compared with continuous-relaxation BO, TuRBO, BOPS, Merge-BO and a "vanilla" Merge-BO. The authors also separate variants without a GP (VaP) from GP-guided variants (VaPBO) to see where the gains come from. VaPBO with greedy local search gets the best average rank on the high-dimensional tasks. Extra experiments look at candidate selection, the fill-in strategy and sensitivity to the size of the active subset.

Critical strengths
  • The paper asks a timely question and designs its experiments to answer it honestly. Splitting each method into a version with GP guidance and a version without is a good choice, because it shows how much of the gain comes from the GP itself. The authors also report results that cut against their own method. VaP-GLS, which uses no GP, has the best average rank on the low-dimensional tasks (Table 4). The GP's benefit on QAP256 is small and inconsistent (0.57% on average, better in only 7 of 10 paired runs). The fixed-history experiments in Appendix B.5 are also well designed, because they hold the candidate pool fixed and test candidate selection and fill-in on their own.
  • The second strength is the benchmark. Chip placement with sequence pairs and fossil-record timeline reconstruction are realistic, high-dimensional permutation problems that the BO community doesn't have many of. I think these tasks could be useful well beyond this paper.
Critical weaknesses
  • The analysis motivating the paper doesn't show that permutations behave differently from continuous spaces. Figure 1 claims that permutation distances concentrate at a "factorial rate" while continuous distances don't concentrate at all. A quick calculation says otherwise. For two random permutations of nn items, the Kendall distance has mean n(n−1)/4 and variance n(n−1)(2n+5)/72n(n−1)(2n+5)/72. Dividing by the largest possible distance gives a spread of about 1/(3n)1/(3\sqrt{n}). For two random points in [0,1]d[0,1]^d, the Euclidean distance has a roughly constant spread of about 0.24. Dividing by d\sqrt{d} gives a spread of about 0.24/d0.24/\sqrt{d}. Both spreads therefore shrink at the same rate, about one over the square root of the dimension. Neither shrinks at a factorial rate.
  • The flat continuous curves in Figure 1 suggest that the two cases were normalized differently. The paper doesn't say how the normalization was done. This matters a lot, because distance concentration is exactly the problem the vanilla-BO papers address by scaling lengthscales with the dimension. So the analysis doesn't show that the vanilla recipe must fail on permutations. The NLL evidence has problems too. Tables 1 and 3 report single numbers with no error bars, computed "after 200 iterations", while the experiments use only 50 or 80 evaluations. Vanilla Merge's in-distribution NLL is 52 to 77, compared with 1.5 for plain Merge, which suggests the baseline may be misconfigured. It is also unclear whether VaPBO's subspace NLL is comparable with the full-space numbers, since it depends on which random subset of items was chosen.
  • The gains seem to come mostly from local search around good solutions, not from dimensionality reduction in the GP. VaP-GLS, which uses no GP at all, already has an average rank of 3.50 and beats every full-space BO baseline (Table 2). Adding the GP improves the rank to 1.88, but the paired extra runs show a clear gain only on TSP318. The four VaPBO variants also differ a lot depending on the acquisition optimizer, from 1.88 with greedy local search to 5.75 with gradients. So the optimizer seems to matter more than the subspace.
  • The comparison with vanilla BO also doesn't isolate the claim in the title. VaPBO differs from Vanilla Merge in four ways at once: the random subspace, the Best-K fill-in, the greedy local-search optimizer, and EI instead of LogEI. To show that dimensionality reduction is what helps, the paper needs a full-space Merge GP, with and without the vanilla lengthscale scaling, that uses the same greedy local search and fill-in.
  • The statistics are also thin for claims about average rank. There are only 5 seeds, the budgets are short for problems with up to 318 items, and many standard deviations are as large as the gaps between methods (for example 50.64 ± 28.78 on CP1). VaPBO-GLS has the best mean on only 5 of the 8 tasks. A few entries have zero standard deviation across seeds, such as Random on TTP280 (291.09 ± 0.00) and BOPS on TSP318 (4.69 ± 0.00). That is strange for randomized methods and may point to a plateau in the task or a logging issue.
  • The wording in Section 3 is stronger than the evidence. Terms like "catastrophic", "geometric collapse" and "factorial-rate decay" should be softened or backed up. It would help to compare with trust-region methods for discrete spaces, such as CASMOPOLITAN. It would also help to try applying the vanilla lengthscale scaling inside the subspace model. Finally, the paper should say clearly that the chip-placement and biodiversity tasks were written for this paper, and should release them along with the code.
Questions for authors
  • How were the distances in Figure 1 normalized for permutations and for continuous spaces? If you divide both by their largest possible distance, do the permutation and continuous curves still shrink at different rates?
  • Can you run a full-space Merge GP, with and without the vanilla lengthscale scaling, using the same greedy local-search optimizer and Best-K fill-in as VaPBO-GLS? This is the comparison that would show whether the subspace itself helps.
  • How exactly was Vanilla Merge configured? Was the lengthscale scaled with the number of items or with the length of the Merge feature vector? Why is its in-distribution NLL so much worse than plain Merge's?
  • Can you report the NLL results with error bars, at the same budgets as the optimization runs, and explain how the subspace NLL in Table 3 is computed given that the active subset is random?
  • Why do some entries in Table 2 have zero standard deviation, especially Random on TTP280? Does TTP have a large flat region where most methods get stuck?
  • Can you add more seeds or significance tests for Table 2? Can you also compare with stronger non-BO baselines at the same budget, such as simulated annealing or an evolutionary algorithm with order crossover, on all tasks rather than only two?
5 comments

Thanks for your detailed comments! We appreciate your recognition of the GP/no-GP separation, the controlled candidate experiments, and the potential value of the two application benchmarks. We have completed the matched modeling-space controls, budget-matched NLL analysis, independent reruns, and expanded statistical comparison. These results strengthen the finite-budget optimization contribution and clarify what each component contributes.

R3C1 Comment on distance normalization, concentration rates, and vanilla BO motivation

W1) The analysis motivating the paper doesn't show that permutations behave differently from continuous spaces. Figure 1 claims that permutation distances concentrate at a "factorial rate" while continuous distances don't concentrate at all. A quick calculation says otherwise. For two random permutations of n items, the Kendall distance has mean n(n−1)/4 and variance n(n − 1)(2n + 5)/72. Dividing by the largest possible distance gives a spread of about 1/(3√n). For two random points in [0, 1]^d, the Euclidean distance has a roughly constant spread of about 0.24. Dividing by √d gives a spread of about 0.24/√d. Both spreads therefore shrink at the same rate, about one over the square root of the dimension. Neither shrinks at a factorial rate.

W2) The flat continuous curves in Figure 1 suggest that the two cases were normalized differently. The paper doesn't say how the normalization was done. This matters a lot, because distance concentration is exactly the problem the vanilla-BO papers address by scaling lengthscales with the dimension. So the analysis doesn't show that the vanilla recipe must fail on permutations.

Q1) How were the distances in Figure 1 normalized for permutations and for continuous spaces? If you divide both by their largest possible distance, do the permutation and continuous curves still shrink at different rates?

The revised Figure 1 establishes distance concentration in the Merge representation used by VaPBO, motivating our study of active-item modeling together with kernel calibration and structured search. We compare Merge feature distances with Euclidean distances between independent uniform and Gaussian vectors, dividing every distance by its respective sample mean at each dimension. Merge has the narrowest central 95% relative-distance interval throughout the tested dimensions and a larger proportional reduction in width across the displayed dimension range. The revised Figure 1 presents the detailed distributions and comparisons.

The original figure used Kendall distance divided by its maximum (n2)\binom n2 and continuous Euclidean distances scaled by their per-dimension sample ranges. Sample min–max normalization removes location and scale changes for a location-scale family, explaining the approximately horizontal continuous curves. Under the diameter normalization in your question, Kendall has standard deviation (2n+5)/(18n(n−1))\sqrt{(2n+5)/(18n(n-1))}, while Euclidean distance on [0,1]n[0,1]^n, divided by n\sqrt n, has asymptotic standard deviation 7/(120n)\sqrt{7/(120n)}. Both therefore have order n−1/2n^{-1/2}. Gaussian distances have unbounded support, so we use common mean normalization in the updated three-way comparison.

The concentration rate depends on the representation. For the balanced fixed-length Merge features used here and independent uniform permutations, our derivation gives

\sim\frac{1}{2\sqrt{F_n}}, \qquad F_n\sim n\log_2n.$$ The corresponding relative standard deviations for uniform and Gaussian Euclidean distances are asymptotic to $\sqrt{7/(20n)}$ and $1/\sqrt{2n}$, respectively. The central 95% widths have the same respective orders. Here $n$ denotes permutation items or continuous coordinates, while Merge contains $F_n$ feature coordinates. Its inverse-square-root concentration in $F_n$ yields the additional logarithmic factor relative to item count. Appendix B.6 provides the complete derivation for the implemented Merge features, including their terminal padding. This concentration motivates active-item dimensionality reduction, which focuses GP modeling on selected ordering decisions in a smaller permutation space. VaPBO computes Merge features directly from the active-item positions. For a fixed active set and independent uniform permutations, their relative order is uniform, and the same geometric result applies at the smaller item count. Its dependence on item count provides a geometric motivation for using smaller active sets to retain greater relative variation in pairwise distances. The controlled experiments evaluate this modeling choice within the adaptive search procedure.

VaPBO combines this dimensionality-reduction design with structure-aware completion and GP-guided search. The expanded independent-run comparison supports the effectiveness of this framework, with VaPBO-GLS achieving lower mean regret than both the no-GP VaP-GLS variant and SA on all eight tasks, with significant gains on multiple tasks (R3C5). Dimension-scaled priors can further improve VaPBO. The crossed controls show improvements in both modeling spaces, with the preferred space depending on the task and scaled full-space modeling significantly better on TSP318 (R3C4). These controls clarify how prior calibration complements the active-item design.

We have specified the Merge distance and common normalization in Section 3.1 and the Figure 1 caption, stated the representation-specific rate, and included its derivation in Appendix B.6. The permutation-space cardinality grows factorially as n!n!; this does not imply a factorial rate of distance concentration.

R3C2 Comment on NLL budgets, uncertainty, and random active-set aggregation

W2) The NLL evidence has problems too. Tables 1 and 3 report single numbers with no error bars, computed "after 200 iterations", while the experiments use only 50 or 80 evaluations.

W2) It is also unclear whether VaPBO's subspace NLL is comparable with the full-space numbers, since it depends on which random subset of items was chosen.

Q4) Can you report the NLL results with error bars, at the same budgets as the optimization runs, and explain how the subspace NLL in Table 3 is computed given that the active subset is random?

Thank you for requesting this clarification. We recomputed the predictive comparison at the application evaluation budget, added error bars, and averaged VaPBO’s scores over random active subsets as described below.

1. Evaluation budget and repeated fits. Tables 1 and 3 concern Chip Placement and Biodiversity, both of which use an optimization budget of 80 evaluations. The updated comparison uses 80 training observations per fit, with five repeated splits and fits for Chip Placement and ten for Biodiversity. We report mean ± sample SD across these repetitions. The 50-evaluation budget applies to the combinatorial tasks.

Within each repetition, all five methods share the training observations, test inputs, and training-only target standardization. We exclude the best 10% of the historical pool before constructing the training and ID sets and report the best 5% of the complete pool as the OOD group.

2. Scoring random active subsets. Within each repetition, we fit VaPBO on five random active subsets. Each fit predicts the original objective on the same full-permutation test inputs, using their active-item representations. We average pointwise MSE or NLL over the test set, then average these scores over the five subsets. This gives one score per repetition, from which the reported mean and sample SD are computed.

3. Updated predictive results. After correcting the GP fitting and predictive scoring, we report MSE alongside predictive NLL. MSE measures predictive mean error, while NLL also assesses predictive uncertainty. The table gives absolute scores in training-target standardized units, with lower values better for both metrics.

Task / test setMSE CRMSE MallowsMSE MergeMSE Vanilla MergeMSE VaPBONLL CRNLL MallowsNLL MergeNLL Vanilla MergeNLL VaPBO
Chip Placement (ID)1.0161 ± 0.19861.0160 ± 0.19850.9844 ± 0.16821.0135 ± 0.19750.9648 ± 0.15591.4269 ± 0.09841.4270 ± 0.09931.4155 ± 0.08951.4319 ± 0.08541.4082 ± 0.0888
Biodiversity (ID)1.0919 ± 0.23241.0553 ± 0.22731.0574 ± 0.23631.0881 ± 0.23250.9929 ± 0.20611.4645 ± 0.11521.4507 ± 0.12321.4493 ± 0.13161.4598 ± 0.11091.4202 ± 0.1187
Chip Placement (OOD)3.7423 ± 0.59213.7421 ± 0.59193.5021 ± 0.36873.7244 ± 0.58493.2975 ± 0.32512.7780 ± 0.29342.7899 ± 0.29592.7591 ± 0.25732.6610 ± 0.31512.6918 ± 0.2377
Biodiversity (OOD)5.0526 ± 0.47494.6579 ± 0.50834.6035 ± 0.61995.0202 ± 0.47334.0226 ± 0.47453.4274 ± 0.23533.4273 ± 0.24603.3735 ± 0.24483.3314 ± 0.20723.1837 ± 0.2447

In this evaluation, VaPBO has the lowest mean MSE on both tasks in both ID and OOD groups, and the lowest mean ID NLL. Its OOD MSE is 11.5% lower than Vanilla Merge on Chip Placement and 19.9% lower on Biodiversity. VaPBO also has the lowest mean OOD NLL on Biodiversity, with a 4.4% reduction relative to Vanilla Merge, while Vanilla Merge has the lowest mean OOD NLL on Chip Placement.

R3C3 Comment on exact Vanilla Merge configuration

W2) Vanilla Merge's in-distribution NLL is 52 to 77, compared with 1.5 for plain Merge, which suggests the baseline may be misconfigured.

Q3) How exactly was Vanilla Merge configured? Was the lengthscale scaled with the number of items or with the length of the Merge feature vector? Why is its in-distribution NLL so much worse than plain Merge's?

Vanilla Merge scales its lengthscale prior with the Merge feature-vector width, m=ϕ(X).shape[−1]m=\phi(X).\mathrm{shape}[-1]. It uses an ARD RBF kernel with a scale parameter and the priors

\qquad s\sim\operatorname{Gamma}(2.0,0.15),$$ where the outputscale prior is specified in the implementation as GammaPrior(2.0,0.15). The previous test score included training-prior contributions. We corrected this by computing NLL from the predictive distribution. The updated results in R3C2 no longer show the anomalous ID NLL gap. Thank you. ### R3C4 Comments on subspace modeling, dimension-scaled priors, and the contributions of search and completion > W3) The gains seem to come mostly from local search around good solutions, not from dimensionality reduction in the GP. VaP-GLS, which uses no GP at all, already has an average rank of 3.50 and beats every full-space BO baseline (Table 2). Adding the GP improves the rank to 1.88, but the paired extra runs show a clear gain only on TSP318. The four VaPBO variants also differ a lot depending on the acquisition optimizer, from 1.88 with greedy local search to 5.75 with gradients. So the optimizer seems to matter more than the subspace. > > W4) The comparison with vanilla BO also doesn't isolate the claim in the title. VaPBO differs from Vanilla Merge in four ways at once: the random subspace, the Best-K fill-in, the greedy local-search optimizer, and EI instead of LogEI. To show that dimensionality reduction is what helps, the paper needs a full-space Merge GP, with and without the vanilla lengthscale scaling, that uses the same greedy local search and fill-in. > > Q2) Can you run a full-space Merge GP, with and without the vanilla lengthscale scaling, using the same greedy local-search optimizer and Best-K fill-in as VaPBO-GLS? This is the comparison that would show whether the subspace itself helps. > W6) It would also help to try applying the vanilla lengthscale scaling inside the subspace model. Thank you for suggesting this control. We compared full-space and subspace Merge GPs under both base and dimension-scaled priors, holding the active-item schedule, GLS effort, Best-K completion, EI, and initial observations fixed. The full-space GP receives the completed permutation, while the subspace GP receives its active-item projection. Each configuration uses five independent runs with 50 objective evaluations per run, including five initial observations. The combined results are reported in Table 9 of the revised manuscript. | Task / GP input | Base prior | Dimension-scaled prior | |---|---:|---:| | TSP318 / full | 6.71 ± 1.44 | -0.03 ± 1.96 | | TSP318 / subspace | 6.36 ± 0.89 | 3.06 ± 1.78 | | QAP256 / full | 660.11 ± 45.24 | 630.87 ± 43.77 | | QAP256 / subspace | 648.53 ± 21.62 | 566.93 ± 54.96 | Entries are mean regret ± sample SD on the Table 2 scales. Lower values are better. Negative regret indicates performance exceeding the fixed historical reference. **Full-space/subspace control.** The subspace has lower means under the base prior on both tasks and under the scaled prior on QAP256. Scaled full-space modeling performs significantly better on TSP318, with a two-sided Wilcoxon rank-sum $p=0.032$. These results establish a task- and prior-dependent effect of the GP input space under shared search and completion settings. **Prior scaling within VaPBO.** We additionally compared the base and dimension-scaled prior configurations in VaPBO-Merge on two tasks, keeping active-item selection, GLS, Best-K completion, EI, and initial observations fixed. The scaled prior lowers mean regret on both tasks, showing that the vanilla BO prior design can further improve VaPBO-Merge. Appendix B.7 describes the prior scaling and its corresponding lengthscale initialization.
Reviewer_ctegOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This manuscript introduces VaPBO that seaks to apply BO to permutation spaces where the goal is to identify the optimial permutation for a blackbox evaluation function. The manuscript demonstrates that recent advances in continue-space BO do not directly translate to permutation spaces, and introduces VaPBO as one methodology that aims to overcome this limitation.

The manuscript argues that in permutation spaces the “geometric collapse” is more pronouced: the distance between randomly sampled permutations will be more tightly concentrated around an average distance, which limits BO’s ability to sample both similar and dissimilar permutations. It aassembles a set of permutation learning into a benchmark for evaluating BO on permutation objectives.

VaPBO is presented as a principled way to apply dimensionality reduction in the face of permutation constraints: active items are chosen, the merge kernel is used only over the active items (which are placed in permutation slots) and then a fill-in proceedure (that draws from the top-k solutions found so far) reconstructs the positions of the non-active items.

Critical strengths
  1. The manuscript takes a principle-driven algorithm design approach with empirical evidence and dervied principles that identifies some weaknesses with optimizing over permutation space and seeks to overcome those limitations. The problem setting is a strong one, with mutiple natural applications, that is of interest to both practitioners and algorithm designers. The algorithmic design choices are well motivated

  2. The set of baselines covers a reasonable set of the existing methods, and the set of data sets to which they are applied is diverse and covers various types of applications. The results demonstrate that the proposed VaPBO-GLS is typically the stronger optimizer, with occasional excepts favoring either other variants or baseline approaches.

Critical weaknesses
  1. Only the merge kernel is tested in the main experiments. This isn’t a huge weakness, and the rationale for choosing it is clear, but it is one place where the experiments don’t directly eliminate a potentially confounding choice. The Mallows kernel is slower, but is it better? Do the other ideas of VaBPO still help when using other kernels?
Questions for authors
  1. Permutation vs. discrete high-dimension: A permutation of 100 parameters is more constrained than 100 parameters that can take on integer values between [0,99]. Is it the permutation or the discretenees that poses the main challenge? I don’t think the answer changes the results / utility of this manuscript, but it might affect the positioning in the introduction. I think the answer might be: the problem is not unique to permutation spaces, it’s that permutation spaces are one natural, frequently encountered manifestation of it.

  2. Right-invariance: The manuscript notes that the merge kernel is not right invariant. But how does this affect anything that follows? The discussion of right invariance seems a little disconnected from the algorithm design — it is never mentioned again after the initial discussion. If there is someplace where that property influenced the design it would be helpful to point that out.

Suggestion:

  • Table 1 is hard to interpret w/o looking at Table 3. With Table 1 in isolation, it’s not clear if these are “big” numbers or not. Table 3 shows that they are. It would help to add a forward reference/disucssion to Table 3 to calibrate the interpretation of Table 1.

A (hopefully reasonable and helpful) thought that’s just a suggestion and not a question or a criticism of this manuscript:

  • The history-based fill in is interesting and reasonable. But that history is a byproduct of the optimization trajectory. I wonder if an interesting extention (certainly not required for this manuscript) would be to explictly optimize for informative histories? For example, if none of the histories has a similar placement of the active items, the fill in is probably close to “random”, but maybe explicitly getting diverse/conditionally good pool of top-k (or changing top-k to favor diversity) might lead to even more improvements.
3 comments

Thanks for your comments! We appreciate your positive assessment of the problem setting, the structure-aware design, and the breadth of the benchmarks. Your questions help sharpen both the method's positioning and the role of the kernel. Below please find our responses.

R2C1 Comment on Merge versus Mallows

W1) Only the merge kernel is tested in the main experiments. This isn’t a huge weakness, and the rationale for choosing it is clear, but it is one place where the experiments don’t directly eliminate a potentially confounding choice. The Mallows kernel is slower, but is it better? Do the other ideas of VaBPO still help when using other kernels?

Yes, VaPBO improves over the full-space baselines with both Merge and Mallows on the two TSP benchmarks. The relative performance of the two kernels varies by task, as shown below. We evaluate all four configurations over five independent runs per task, using 50 objective evaluations including five initial observations.

TaskFull-space MergeFull-space MallowsVaPBO-GLS / MergeVaPBO-GLS / Mallows
TSP1278.51 ± 1.779.11 ± 0.833.95 ± 5.124.76 ± 3.78
TSP3187.48 ± 0.643.93 ± 3.462.48 ± 2.521.49 ± 2.10

Entries are mean regret ± sample SD, lower is better. The two VaPBO configurations use the same initial observations within each paired run, active-item selection, GLS acquisition optimizer, and Best-K completion, with the kernel representation replaced. The full-space baselines retain their respective acquisition-search configurations.

VaPBO versus full-space BO. On both tasks, VaPBO-GLS with either kernel achieves a lower mean cost than both full-space baselines. In particular, replacing Merge with Mallows preserves the framework's improvement over full-space Mallows on both tasks.

Applicability to both kernels. Merge has the lower mean on TSP127, while Mallows has the lower mean on TSP318, in both the full-space and VaPBO comparisons. Thus, the preferred kernel depends on the task, while VaPBO works with both kernels in this evaluation. We use Merge as the default for its compact representation; the improvement of the complete framework is also observed with Mallows. The matched controls in Table 9 and Appendix B.7 of the revised manuscript separately examine the contributions of modeling space and prior scaling.

Computational cost. Merge uses a compact Θ(nlog⁡n)\Theta(n\log n) comparison representation, whereas our explicit full-space Mallows implementation uses (n2)\binom{n}{2} pairwise features, reaching 38,503 features on Bio278. In our earlier runs of this implementation, some Bio278 and QAP256 CPU runs remained incomplete after more than two days, while a Bio278 GPU run occupied approximately 44 GiB on a 48 GiB device, leaving little memory headroom. These implementation-specific observations illustrate the substantial computational and memory costs that can arise in high-dimensional full-space modeling and motivate compact representations and active-item modeling.

R2C2 Comment on permutation structure and general discrete high dimensionality

Q1) Permutation vs. discrete high-dimension: A permutation of 100 parameters is more constrained than 100 parameters that can take on integer values between [0,99]. Is it the permutation or the discretenees that poses the main challenge? I don’t think the answer changes the results / utility of this manuscript, but it might affect the positioning in the introduction. I think the answer might be: the problem is not unique to permutation spaces, it’s that permutation spaces are one natural, frequently encountered manifestation of it.

We agree that limited-data modeling in high dimensions is a broader challenge. Permutations provide an important instance with additional coupling. The positions assigned to different items must be distinct, and placing the active items determines which slots remain for all other items. A coordinate-wise update must therefore be followed by a compatible assignment of the inactive items.

VaPBO handles that coupling explicitly through active-item optimization and order-preserving completion. This is the structural reason for the method's permutation-specific design. We have clarified the distinct-position constraint and the role of order-preserving completion in the introduction.

R2C3 Comment on right-invariance and algorithm design

Q2) Right-invariance: The manuscript notes that the merge kernel is not right invariant. But how does this affect anything that follows? The discussion of right invariance seems a little disconnected from the algorithm design — it is never mentioned again after the initial discussion. If there is someplace where that property influenced the design it would be helpful to point that out.

Thank you for pointing this out. We included the right-invariance discussion to describe the properties of the kernel used in VaPBO. Right-invariance means that kernel similarity is preserved under a common relabeling of items. Mallows satisfies this property, while Merge uses a fixed comparison path and its similarity can depend on item indexing. We have clarified this descriptive role in Section 3.1.

The algorithmic choices have separate motivations: we use Merge for its compact representation, active-item modeling to limit the size of the surrogate's input representation, and Best-K completion to preserve useful ordering from previously evaluated good solutions. These choices do not rely on Merge lacking right-invariance. The additional Mallows results in R2C1 also show that the framework works with a right-invariant kernel.

R2C4 Comment on interpreting Tables 1 and 3

S1) Table 1 is hard to interpret w/o looking at Table 3. With Table 1 in isolation, it’s not clear if these are “big” numbers or not. Table 3 shows that they are. It would help to add a forward reference/disucssion to Table 3 to calibrate the interpretation of Table 1.

Thank you for this suggestion. We have added a forward reference linking the absolute full-space scores in Table 1 to VaPBO's relative reductions in MSE and NLL in Table 3.

The revised Table 1 compares the four full-space models, with MSE on the left and predictive NLL on the right. All models use the same 80 training observations and test points within each repetition. Both metrics use targets standardized by the training mean and standard deviation, and each entry reports mean ± sample SD. The table retains the ID/OOD organization, with OOD defined as the best-quality 5% of the historical observation pool, excluded before training.

MSE makes the size of prediction errors directly visible alongside NLL's assessment of the predictive distribution. Each column in Table 3 uses the corresponding full-space model in Table 1 as its baseline: positive percentages indicate lower MSE or NLL for VaPBO, and negative percentages indicate higher values. In this evaluation, VaPBO has the lowest mean MSE on both tasks in both ID and OOD groups, and the lowest mean ID NLL. Relative to Vanilla Merge, VaPBO reduces OOD MSE by 11.5% on Chip Placement and 19.9% on Biodiversity.

R2C5 Comment on diversity-aware histories

S2) A (hopefully reasonable and helpful) thought that’s just a suggestion and not a question or a criticism of this manuscript: The history-based fill in is interesting and reasonable. But that history is a byproduct of the optimization trajectory. I wonder if an interesting extention (certainly not required for this manuscript) would be to explictly optimize for informative histories? For example, if none of the histories has a similar placement of the active items, the fill in is probably close to “random”, but maybe explicitly getting diverse/conditionally good pool of top-k (or changing top-k to favor diversity) might lead to even more improvements.

Thank you for this suggestion. Best-K combines objective quality with positional agreement by choosing, among the best solutions evaluated so far, the template closest to the proposed active-item positions. A more diverse archive could provide suitable completion templates for a wider range of active assignments.

Our completion control shows that the current rule improves average candidate quality, and the sensitivity analysis in Appendix B.3 shows that the preferred archive size varies across tasks. Explicitly balancing quality, positional agreement, and diversity is a promising extension of this mechanism.

We hope our response has addressed your concerns. If we have missed anything, please let us know.

Thank you for addressing my comments. I think this substantiates my original score.

Reviewer_zLTjOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper discusses high-dimensional BO in the specific setting of permutation spaces. The authors argue that, while there is some evidence from prior work on „vanilla BO“ that show that with proper scaling of the hyperparameters such basic BO can perform on par with specialized high-dimensional BO algorithms, that this is not the case for the specific setting of permutation spaces. Based on that observation, the authors continue to develop a subspace BO algorithm for that specific setting which performs variable selection to derive active sub-permutations in combination with ways to optimize the resulting acquisition fucntion. The derived approaches are then benchmarked against other specialized algorithms as well as local BO algorithms on the continuous relaxations of the input space.

Critical strengths

S1) The problem of efficient BO in permutation spaces is very interesting and relevant and as such is also well motivated in the paper.

S2) The authors evaluate and compare their method on various (and interesting) benchmarks, including different ablations of their approaches.

S3) The developed local BO algorithm for permutation spaces is also interesting and I believe such a local approach is novel though I am not an expert on permutation-space BO.

Critical weaknesses

W1) The core of the paper I believe is not an investigation of the claims of „vanilla BO is all you need“ in permutation spaces but rather a method contribution, ie, designing a method specifically for high-dim BO over permutation spaces. This is a bit misleading from the title IMO.

W2a) A lot of the motivation and story builds on Figure 1 but there are several things that I find confusing here. For continuous, the interval width stays constant but without any scaling I would expect the normalised distance to shrink by 1/sqrt(D) here. Can you clarify how the distances were normalized?

W2b) Touching on the point above, I am surprised by the stated „factorial decay“. Looking at the Kendall distance, I would also expect here a 1/sqrt(n) (with some constants) but I dont quite see how one can theoretically show a factorial. Also for the merge kernel with the n log n I would expect this to still be polynomial in the decay and not factorial.


(more minor points)

W3) I believe there is an important branch of RW missing for local BO, specifically papers such as GiBO [R1] (and follow-ups like MPD [R2], or [R3]) which seem to be conceptually similar to the GLS- and Grad-variants of VaPBO.

W4) The statistical evidence is not super strong with only 5 independent seeds. If possible, I would highly recommend to run additional seeds.

(Very minor) W5) Please add explicit forward references in the main text when referring to the appendix (eg line 111).

(Very minor) W6) PBO is in the BO community the short form for preferential BO and with this the algorithm name VaPBO could on first glance be interpreted as a PBO algorithm; but again this is very minor but just wanted to raise awareness for this.


[R1] Müller, Sarah, Alexander von Rohr, and Sebastian Trimpe. "Local policy search with Bayesian optimization." Advances in Neural Information Processing Systems 34 (2021): 20708-20720.

[R2] Nguyen, Quan, et al. "Local Bayesian optimization via maximizing probability of descent." Advances in neural information processing systems 35 (2022): 13190-13202.

[R3] Brunzema, Paul, and Sebastian Trimpe. "BayeSQP: Bayesian Optimization through Sequential Quadratic Programming." Advances in Neural Information Processing Systems 38 (2026): 59821-59848.

Questions for authors

Q1) What kernel did you use for the permutation in Figure 1? I couldn’t find this in the text and it seems critical (see above) for the main motivation and argument, but also let me know if I missed this!

Q2) Can you please clarify how you come to the conclusion that the decay in Figure 1 has a factorial rate?

Q3) In Table 2, the random baseline has a variance of 0 on TTP280. Can you explain why?

Q4) in Table 3, how is it possible that the Vanilla Merge performs so much worse compared to the standard Merge on the in-distribution test set? It seems strange that a GP fitted with MLE or MAP using the same kernel would result in such a huge difference. And connected to that, how you then explain the significant improvement in OOD of vanilla merge?

Q5) If I understood the main text correctly, Vanilla Merge essentially uses the same conceptual ideas as the vanilla BO for high-dim BO papers right? What are the concrete priors that you used here?

Q6) Can you give additional intuition on why VaP-GLS already performs so strongly? Even without the GP?

9 comments

Thanks for your comments! We appreciate your recognition of the importance of permutation-space BO, the breadth of the evaluation, and the potential of the local approach. We have added more independent runs, conducted statistical tests, added controls that separate GP guidance, completion, and modeling-space choices. Below please find our responses.

R1C1 Comment on connection between the title and the contribution

W1) The core of the paper I believe is not an investigation of the claims of ``vanilla BO is all you need“ in permutation spaces but rather a method contribution, ie, designing a method specifically for high-dim BO over permutation spaces. This is a bit misleading from the title IMO.

Thank you for this comment. The title revisits whether the vanilla BO recipe alone is sufficient for high-dimensional permutation optimization. We first examine the remaining difficulties in predicting high-quality permutations with full-space vanilla models. We then evaluate how VaPBO’s active-item modeling, acquisition-guided search, and order-preserving completion improve optimization under limited evaluation budgets. These two parts connect the investigation of vanilla BO to our method contribution and highlight the continuing value of dimensionality reduction and permutation-aware search. The added controls examine the contribution of each component and show how dimension-scaled priors can further improve VaPBO.

  • Geometric motivation. We added a common-normalization comparison and derived the concentration rate of the Merge representation. Its relative spread decreases at order Θ((nlog⁡n)−1/2)\Theta((n\log n)^{-1/2}), motivating active-item dimensionality reduction as a way to alleviate concentration in the surrogate representation (R1C2–R1C3).
  • Surrogate predictive accuracy. We corrected the predictive evaluation and added MSE alongside NLL. In this fair comparison, VaPBO has lower mean MSE than all four full-space models on both application tasks, in both ID and OOD groups (R1C9).
  • Modeling space and prior scaling. Dimension-scaled priors further lower the mean regret of VaPBO-Merge, showing that the framework can benefit from the vanilla BO prior design. A separate full-space/subspace comparison holds GLS, Best-K completion, and EI fixed under both prior choices, showing that the modeling-space effect depends on the task and prior.
  • Kernel choice. We evaluated full-space and VaPBO configurations with both Merge and Mallows. VaPBO has lower mean regret than the full-space baselines with either kernel on both tasks, showing that the framework also works with Mallows (Table 5 of the revised manuscript).
  • Optimization performance. We added more seeds and statistical comparisons for our main results. VaPBO-GLS achieves the best average rank of 1.500 across eight tasks, followed by TuRBO (CR) at 3.500. Across all the 112 task-level comparisons with the other 14 methods, 81 significantly favor VaPBO-GLS (R1C5).
  • Component contributions. Best-K improves mean candidate quality on both tested tasks (Figure 4 and Appendix B.5), and VaPBO-GLS has lower mean regret than the no-GP VaP-GLS variant on all eight tasks (R1C11). These results explain how completion and surrogate guidance contribute to the framework.
  • Connection to local BO. We expanded the related-work discussion and added a CASMOPOLITAN comparison. VaPBO-GLS has lower mean regret on three of the four combinatorial tasks. The comparison connects VaPBO to acquisition-guided local search and highlights its active-item modeling and order-preserving completion for permutations (R1C4).

We have clarified this connection in the introduction and Section 2.2, with the comparative results and component analyses summarized in Sections 4.2 and 4.3 and detailed in the corresponding appendix sections.

R1C2 Comment on Figure 1 distance definition and normalization

W2a) A lot of the motivation and story builds on Figure 1 but there are several things that I find confusing here. For continuous, the interval width stays constant but without any scaling I would expect the normalised distance to shrink by 1/sqrt(D) here. Can you clarify how the distances were normalized?

Q1) What kernel did you use for the permutation in Figure 1? I couldn’t find this in the text and it seems critical (see above) for the main motivation and argument, but also let me know if I missed this!

The original Figure 1 used the common used Kendall inversion counts divided by (n2)\binom n2 for permutations. For continuous samples, it used Euclidean distances with sample min–max normalization, (d−dmin⁡,n)/(dmax⁡,n−dmin⁡,n)(d-d_{\min,n})/(d_{\max,n}-d_{\min,n}), applied separately at each dimension. This transformation removes location and scale changes when distribution shapes are similar, explaining the approximately horizontal continuous curves.

To align Figure 1 with the Merge kernel actually used in VaPBO, we now measure distances in its feature representation. For permutations, the revised distance is

dMerge(π,π′)=∥ϕMerge(π)−ϕMerge(π′)∥2.d_{\mathrm{Merge}}(\pi,\pi')=\|\phi_{\mathrm{Merge}}(\pi)-\phi_{\mathrm{Merge}}(\pi')\|_2.

We also apply a common normalization to make the dimension-wise comparison consistent. Merge feature distances and Euclidean distances between independent uniform or Gaussian vectors are each divided by their sample mean at the corresponding dimension, r=d/dˉr=d/\bar d. Under this fair comparison, Merge has the narrowest central 95% relative-distance interval at every tested dimension, and its width decreases by a larger proportion across the displayed dimension range than those of the continuous distances.

We have updated Figure 1 and specified the distance definitions and common normalization in its caption and Section 3.1.

R1C3 Comment on factorial space growth and distance concentration

W2b) Touching on the point above, I am surprised by the stated „factorial decay“. Looking at the Kendall distance, I would also expect here a 1/sqrt(n) (with some constants) but I dont quite see how one can theoretically show a factorial. Also for the merge kernel with the n log n I would expect this to still be polynomial in the decay and not factorial.

Q2) Can you please clarify how you come to the conclusion that the decay in Figure 1 has a factorial rate?

Thanks for this comment. We are sorry for not making this clear. The permutation-space cardinality grows factorially, ∣Sn∣=n!|\mathbb S_n|=n!; this does not imply a factorial rate of distance concentration. The concentration rate depends on the representation and normalization. For the diameter-normalized Kendall distance in the original figure, the exact variance is (2n+5)/(18n(n−1))(2n+5)/(18n(n -1)), giving standard deviation Θ(n−1/2)\Theta(n^{-1/2}).

The Merge kernel is our main choice because its compact Θ(nlog⁡n)\Theta(n\log n) representation, compared with the (n2)\binom n2 pairwise coordinates underlying Mallows. We therefore analyze distance concentration in the Merge representation used by our surrogate.

For two independent uniformly sampled permutations, the balanced merge-sort feature construction in our implementation has

Fn=n⌈log⁡2n⌉−2⌈log⁡2n⌉+1∼nlog⁡2nF_n=n\lceil\log_2n\rceil-2^{\lceil\log_2n\rceil}+1\sim n\log_2n

coordinates. Writing HnH_n for the number of differing feature signs gives dMerge=2Hn/(n2)d_{\mathrm{Merge}}=2\sqrt{H_n/\binom n2}. The independent interleavings at the merge-tree nodes yield E[Hn]=Fn/2+O(n)\mathbb E[H_n]=F_n/2+O(n) and Var⁡(Hn)=Fn/4+O(n)\operatorname{Var}(H_n)=F_n/4+O(n), including the implementation's terminal padding. Consequently,

\sim\frac{1}{2\sqrt{F_n}} =\Theta\!\left((n\log n)^{-1/2}\right).$$ The central 95% width has the same asymptotic order. For uniform and Gaussian Euclidean distances in $n$ dimensions, the corresponding mean-normalized widths have order $n^{-1/2}$. The additional logarithmic factor is measured relative to the number of permutation items, $n$. In terms of its $F_n$ feature coordinates, Merge has inverse-square-root concentration. This makes the role of the representation explicit and explains the stronger concentration observed as the item count increases in the revised diagnostic. The figure uses sample means to estimate the population normalization above. We have stated these explicit concentration rates in Section 3.1 and included the complete derivation in Appendix B.6.

R1C4 Comment on connections to local Bayesian optimization

(more minor points) W3) I believe there is an important branch of RW missing for local BO, specifically papers such as GiBO [R1] (and follow-ups like MPD [R2], or [R3]) which seem to be conceptually similar to the GLS- and Grad-variants of VaPBO.

[R1] Müller, Sarah, Alexander von Rohr, and Sebastian Trimpe. "Local policy search with Bayesian optimization." Advances in Neural Information Processing Systems 34 (2021): 20708-20720.

[R2] Nguyen, Quan, et al. "Local Bayesian optimization via maximizing probability of descent." Advances in neural information processing systems 35 (2022): 13190-13202.

[R3] Brunzema, Paul, and Sebastian Trimpe. "BayeSQP: Bayesian Optimization through Sequential Quadratic Programming." Advances in Neural Information Processing Systems 38 (2026): 59821-59848.

Thank you for pointing out this connection. GIBO, MPD, and BayeSQP use GP function or derivative information to guide local improvement in continuous spaces. VaPBO shares this use of surrogate-guided local search. Its permutation-specific design combines active-item modeling with Best-K completion, which preserves the relative order of inactive items and produces feasible full permutations. We have added these connections in Section 2.2.

Comparison with discrete local BO. As suggested in Reviwer 3, CASMOPOLITAN uses acquisition-guided local search within an adaptive categorical trust region. We added a Lehmer-encoded version for the permutation tasks, obtaining the following comparison.

TaskCASMOPOLITANVaPBO-GLS
TSP1277.29 ± 2.313.13 ± 4.40
TSP3182.64 ± 2.172.81 ± 2.84
TTP280414.75 ± 8.7185.89 ± 13.75
QAP256537.29 ± 43.98527.00 ± 78.00

Entries are mean regret ± sample SD, with lower values better. VaPBO-GLS has lower means on three tasks, and CASMOPOLITAN has a slightly lower mean on TSP318. Table 4 of the revised manuscript reports the comparison, and Appendix B.1 describes the experimental setup.

Search within VaPBO. The variants use the shared active-item and completion framework with different search mechanisms.

VariantSearch mechanismAverage rank
VaP-GLSStructured greedy local search using evaluated objectives6.750
VaPBO-GradAcquisition gradients in Merge feature space as proxy search directions8.000
VaPBO-EAEvolutionary acquisition optimization6.250
VaPBO-LSLocal acquisition optimization5.875
VaPBO-GLSGreedy acquisition search around good incumbents1.500

Ranks summarize the eight-task analysis in Table 2, with lower values better. The gradient in VaPBO-Grad guides acquisition optimization. VaPBO-GLS has the best average rank among these variants, highlighting the importance of the acquisition optimizer. The GP/no-GP comparison (R1C11) and completion control (Figure 4 and Appendix B.5) examine the contributions of surrogate guidance and Best-K, and the full-space/subspace control examines the modeling choice (Table 9 and Appendix B.7).

R1C5 Comment on additional independent runs and statistical evidence

W4) The statistical evidence is not super strong with only 5 independent seeds. If possible, I would highly recommend to run additional seeds.

Thank you for this suggestion. We expanded the comparison in the main results to ten independent runs per method on all eight tasks. VaPBO-GLS has lower mean regret than both alternatives on every task. We have also added two-sided Wilcoxon rank-sum tests at a significance level of 0.05 to Table 2. The table below summarizes the average rank across eight high-dimensional tasks and the number of task-level comparisons with VaPBO-GLS. Lower average rank is better.

MethodAverage rankVaPBO-GLS significantly betterNo significant differenceVaPBO-GLS significantly worse
Random8.875710
LS13.125800
GLS11.125710
SA9.750710
Vanilla BO (CR)5.875350
TuRBO (CR)3.500170
BOPS8.375620
Merge8.875710
Vanilla Merge9.125710
VaP-LS13.000710
VaP-GLS6.750440
VaPBO-Grad8.000710
VaPBO-EA6.250530
VaPBO-LS5.875530
VaPBO-GLS1.500———

VaPBO-GLS has the best average rank of 1.500, followed by TuRBO (CR) at 3.500. Across the 112 comparisons with the other 14 methods on eight tasks, the tests identify 81 significant differences in favor of VaPBO-GLS, 31 comparisons with no significant difference, and zero significant differences in favor of the compared methods. Each count uses the same test and threshold as Table 2.

We have added the ranking and rank-sum summaries to Table 2.

Comments on the paper

1 comment

The author-reviewer discussion period will end soon. Please review and acknowledge the authors’ responses. If your concerns have been addressed, please reconsider your score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.