# BOSS: Bayesian Optimization over String Spaces

arXiv: https://arxiv.org/abs/2010.00979 · HTML: https://mlsanity.com/paper/2010.00979/

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2020.

## Built on by (most cited first, 30 of 54)

- [GFlowNets for AI-Driven Scientific Discovery](https://mlsanity.com/paper/2302.00615/) (2023)
- [High-Dimensional Bayesian Optimisation with Variational Autoencoders and Deep Metric Learning](https://mlsanity.com/paper/2106.03609/) (2021)
- [Sample-efficient Multi-objective Molecular Optimization with GFlowNets](https://mlsanity.com/paper/2302.04040/) (2023)
- [A Study of Bayesian Neural Network Surrogates for Bayesian Optimization](https://mlsanity.com/paper/2305.20028/) (2023)
- [GIBBON: General-purpose Information-Based Bayesian OptimisatioN](https://mlsanity.com/paper/2102.03324/) (2021)
- [Reinforced Genetic Algorithm for Structure-based Drug Design](https://mlsanity.com/paper/2211.16508/) (2022)
- [Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces](https://mlsanity.com/paper/2111.01186/) (2021)
- [GAUCHE: A Library for Gaussian Processes in Chemistry](https://mlsanity.com/paper/2212.04450/) (2022)
- [Group SELFIES: A Robust Fragment-Based Molecular String Representation](https://mlsanity.com/paper/2211.13322/) (2022)
- [Inducing Point Allocation for Sparse Gaussian Processes in High-Throughput Bayesian Optimisation](https://mlsanity.com/paper/2301.10123/) (2023)
- [Bootstrapped Training of Score-Conditioned Generator for Offline Design of Biological Sequences](https://mlsanity.com/paper/2306.03111/) (2023)
- [A survey and benchmark of high-dimensional Bayesian optimization of discrete sequences](https://mlsanity.com/paper/2406.04739/) (2024)
- [MAP: Low-compute Model Merging with Amortized Pareto Fronts via Quadratic Approximation](https://mlsanity.com/paper/2406.07529/) (2024)
- [De novo Drug Design using Reinforcement Learning with Multiple GPT Agents](https://mlsanity.com/paper/2401.06155/) (2023)
- [BOiLS: Bayesian Optimisation for Logic Synthesis](https://mlsanity.com/paper/2111.06178/) (2021)
- [Searching for High-Value Molecules Using Reinforcement Learning and Transformers](https://mlsanity.com/paper/2310.02902/) (2023)
- [Risk-averse Heteroscedastic Bayesian Optimization](https://mlsanity.com/paper/2111.03637/) (2021)
- [Bayesian Optimization over Permutation Spaces](https://mlsanity.com/paper/2112.01049/) (2021)
- [AntBO: Towards Real-World Automated Antibody Design with Combinatorial Bayesian Optimisation](https://mlsanity.com/paper/2201.12570/) (2022)
- [Framework and Benchmarks for Combinatorial and Mixed-variable Bayesian Optimization](https://mlsanity.com/paper/2306.09803/) (2023)
- [Adaptive machine learning for protein engineering](https://mlsanity.com/paper/2106.05466/) (2021)
- [Molecule Generation for Drug Design: a Graph Learning Perspective](https://mlsanity.com/paper/2202.09212/) (2022)
- [DiscoBAX: Discovery of Optimal Intervention Sets in Genomic Experiment Design](https://mlsanity.com/paper/2312.04064/) (2023)
- [Kermut: Composite kernel regression for protein variant effects](https://mlsanity.com/paper/2407.00002/) (2024)
- [Trieste: Efficiently Exploring The Depths of Black-box Functions with TensorFlow](https://mlsanity.com/paper/2302.08436/) (2023)
- [Deep Learning Methods for Small Molecule Drug Discovery: A Survey](https://mlsanity.com/paper/2303.00313/) (2023)
- [Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars](https://mlsanity.com/paper/2211.01842/) (2022)
- [ODBO: Bayesian Optimization with Search Space Prescreening for Directed Protein Evolution](https://mlsanity.com/paper/2205.09548/) (2022)
- [Be aware of overfitting by hyperparameter optimization!](https://mlsanity.com/paper/2407.20786/) (2024)
- [Fourier Representations for Black-Box Optimization over Categorical Variables](https://mlsanity.com/paper/2202.03712/) (2022)

## Abstract (arXiv)

This article develops a Bayesian optimization (BO) method which acts directly over raw strings, proposing the first uses of string kernels and genetic algorithms within BO loops. Recent applications of BO over strings have been hindered by the need to map inputs into a smooth and unconstrained latent space. Learning this projection is computationally and data-intensive. Our approach instead builds a powerful Gaussian process surrogate model based on string kernels, naturally supporting variable length inputs, and performs efficient acquisition function maximization for spaces with syntactical constraints. Experiments demonstrate considerably improved optimization over existing approaches across a broad range of constraints, including the popular setting where syntax is governed by a context-free grammar.