- 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
-
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.
-
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.
-
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
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.
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.
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
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.
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.
We hope our response has addressed your concerns. If we have missed anything, please let us know.