Revisiting Vanilla Bayesian Optimization in High-Dimensional Permutation Spaces

Motivation

• Known: 고차원 연속 Bayesian Optimization(BO)에서는 최근 additive model, embedding, axis-aligned variable selection 등 구조적 차원축소 기법 없이도, robust kernel initialization과 dimension-aware length-scale scaling(l ∝ √D)만 적용한 표준 GP인 "Vanilla BO"가 SOTA 성능을 달성한다는 "Vanilla Hypothesis"가 확립되어 왔다(Hvarfner et al., 2024; Xu et al., 2025; Papenmeier et al., 2025b). 또한 permutation space를 위한 Mallows kernel과 Merge kernel 등 permutation 전용 커널이 제안되어 있다.
• Gap: 기존 Vanilla Hypothesis 연구는 연속 최적화 문제에 국한되어 있으며, TSP, QAP, chip placement 등 다양한 산업·과학 응용에 필수적인 permutation space(대칭군 Sn, factorial하게 증가하는 이산 조합 공간)에서는 이 가설이 검증되지 않았다. permutation space는 n!으로 증가하는 탐색공간과 이에 따른 고유한 위상적 병리(distance concentration, landscape ruggedness)를 가지므로 연속공간의 결론이 그대로 이전될 수 있는지가 미해결 문제이다.
• Why: 산업 응용(EDA 칩 배치)과 과학적 발견(생물다양성 역사 복원) 등 실세계 고차원 permutation 문제에서 어떤 BO 전략이 실제로 효과적인지 규명하는 것은 실용적 가치가 크며, 최근 연속공간에서 확립된 "차원축소는 더 이상 필요 없다"는 통념이 이산 조합 공간에도 그대로 적용되는지 재검토하는 것은 고차원 BO 분야 전반의 방법론적 방향성에 중요한 시사점을 준다.
• Approach: 표준 global 커널(Mallows, Merge kernel) 기반 vanilla BO가 permutation space에서 겪는 실패 원인을 geometric collapse(distance concentration + topological ruggedness)로 진단하고, 이를 해결하기 위해 permutation 원소에 대한 variable selection을 수행하는 원리 기반 프레임워크 VaPBO를 제안한다.

Achievement

1. Geometric Collapse 현상 규명: 고차원 permutation space(Sn)에서 표준 global 커널이 distance concentration과 topological ruggedness로 인해 대부분의 후보가 관측 데이터와 등거리로 인식되는 "Geometric Collapse" 현상을 정의하고 실증적으로 진단함.
2. VaPBO 프레임워크 제안: permutation 원소에 대한 variable selection을 BO와 결합하고, active sub-permutation에 대해 최적화 후 structure-aware fill-in 전략으로 나머지 원소를 채우는 원리 기반 차원축소 프레임워크를 제안함.
3. 광범위한 실증 검증: TSP, QAP, traveling thief problem 등 고전 조합 문제와 EDA 칩 배치, 생물다양성 역사 복원 등 실제 응용 8개 고차원 벤치마크에서 vanilla 기법 대비 샘플 효율성과 최적화 품질 모두에서 일관된 성능 개선을 입증함.

How

• 진단 단계: permutation space에서의 거리 분포와 landscape ruggedness를 실증 분석하여 global 커널 행렬이 거의 무정보화(uninformative)됨을 보이는 Geometric Collapse 진단 실험 수행 (Figure 1)
• VaPBO 알고리즘: permutation 원소 중 영향력 있는 부분집합(active sub-permutation)을 선정하는 variable selection을 BO 루프에 결합하여 거리 분포에 인위적으로 분산을 복원
• Structure-aware fill-in: 선택되지 않은 원소들은 구조를 보존하는 fill-in 전략으로 채워 넣어 유효한 전체 permutation을 구성
• 커널: Mallows kernel과 Merge kernel(Kendall-tau distance 기반, divide-and-conquer 기반 Θ(n log n) 표현)을 기반 커널로 사용
• 벤치마크: TSP(Reinelt, 1991), QAP(Burkard et al., 1997), traveling thief problem(Bonyadi et al., 2013), EDA 칩 배치(Mirhoseini et al., 2021), 생물다양성 역사 복원(AI-for-Science) 등 8개 고차원 조합 문제에서 vanilla 베이스라인과 비교
• 분석 도구: subspace dimension na에 대한 민감도 분석(Figure 4), OTSD(Optimal Transport-based Solution Diversity 등으로 추정) 기반 exploration dynamics 분석(Figure 5)

Originality

• 연속 최적화 분야에서 최근 확립된 "Vanilla BO가 충분하다"는 통념을 permutation이라는 이산 조합 공간에 처음으로 체계적으로 반박하고, 그 원인을 Geometric Collapse라는 새로운 개념으로 정식화함
• 차원축소(특히 variable selection)가 "outdated"한 것이 아니라 factorial search space에서는 오히려 구조적으로 필수적임을 주장하며 최근 트렌드에 반하는 실증적 근거를 제시함
• EDA 칩 배치, 생물다양성 역사 복원 등 학계에서 잘 다루지 않는 실세계 permutation 응용에 BO를 적용해 검증함

Limitation & Further Study

• 논문이 workshop(ICML 2026 AI for Science Workshop) 형태로 제출되어 발췌된 본문만으로는 VaPBO의 variable selection 및 fill-in 전략의 구체적 알고리즘 세부사항과 이론적 보장(예: 수렴성, 정보 손실 분석)이 충분히 제시되지 않음
• Geometric Collapse 진단이 특정 벤치마크와 커널(Mallows, Merge)에 국한되어 일반적인 permutation 커널 전반에 대한 결론으로 일반화 가능한지 추가 검증이 필요함
• subspace dimension na 등 하이퍼파라미터 선택에 대한 민감도가 존재하는 것으로 보이며(Figure 4), 이에 대한 자동화된 선택 전략이 부족해 보임
• 향후 연구로 permutation 외 다른 이산 조합 공간(예: 그래프, 조합 집합)에 대한 Geometric Collapse의 일반화 가능성과, variable selection과 embedding 기반 접근의 결합 가능성을 탐구할 필요가 있음

Evaluation

총평: 연속 최적화 공간에서의 최근 통념(Vanilla Hypothesis)이 이산 조합 공간에는 그대로 적용되지 않음을 명확한 진단(Geometric Collapse)과 실용적 프레임워크(VaPBO)로 설득력 있게 반박한 시의적절하고 의미 있는 연구이다. 다만 workshop 논문 특성상 방법론의 세부 이론적 근거와 일반화 가능성에 대한 추가 검증이 향후 필요하다.