Multiverse Bayesian Optimization with Joint Finite-Feature Surrogates

Bayesian optimization (BO) typically relies on a Gaussian process (GP) surrogate whose performance depends on the choice of kernel. When an objective contains several patterns, committing to one kernel can miss useful structure and direct acquisition toward uninformative regions. We propose Multiverse Bayesian Optimization (MvBO), a novel BO framework that represents candidate kernels as complementary worlds and learns their contributions jointly in a compact feature space. By retaining features from each world before combining them, the surrogate can preserve structure that compressing the kernel sum would discard. The resulting Bayesian linear regression provides a Gaussian posterior that captures dependence between worlds, supports standard acquisition functions, and requires $O(r^2)$ time per update for a fixed total feature dimension $r$. For upper confidence bound (UCB) acquisition with fixed features, we establish best-query regret $\tilde{O}(\sqrt{r/T})$ under a well-specified prior on a finite domain without repeated queries, and extend this guarantee to account for the error introduced by the finite-feature approximation. We also study when preserving each world's features helps and quantify the accuracy and computational trade-offs of the proposed representation. Across three emerging scientific and AI design tasks, including molecular conformer search, virtual screening for drug discovery, and LLM data-mixture optimization, MvBO-UCB reduces final normalized simple regret by approximately $42\%$, $32\%$, and $38\%$, respectively, relative to the strongest competing BO baseline.