Abstract
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.
Introduction
Bayesian Optimization (BO) is a powerful framework for optimizing expensive black-box functions. While highly effective in continuous domains, applying BO to discrete, structured data like strings (e.g., DNA, SMILES, or code) remains a significant challenge. Traditional methods often rely on Variational Autoencoders (VAEs) to map these discrete inputs into a continuous latent space. However, this "latent space BO" approach suffers from high data requirements for VAE training, potential "dead zones" in the latent space that decode to invalid strings, and the inherent difficulty of tuning complex generative architectures.
The BOSS Framework
We propose BOSS (Bayesian Optimization over String Spaces), a framework that performs optimization directly on raw strings. BOSS replaces the standard continuous kernels with a Sub-sequence String Kernel (SSK) within a Gaussian Process (GP) surrogate model. The SSK measures similarity by identifying shared non-contiguous sub-sequences, allowing the model to capture long-range dependencies crucial in biological and chemical sequences.
To maximize the acquisition function over the discrete string space, BOSS utilizes Genetic Algorithms (GA). These are specifically tailored to respect the underlying syntax of the search space, whether it is unconstrained, locally constrained, or governed by a Context-Free Grammar (CFG). For grammar-constrained spaces, the GA operates directly on parse trees to ensure all generated candidates are syntactically valid.
Experimental Evaluation
The BOSS framework was evaluated across several challenging domains:
- Synthetic String Optimization: Pattern matching tasks in binary and multi-character strings.
- Protein Design: Minimizing the minimum free-folding energy (MFE) for protein sequences of varying lengths.
- Symbolic Regression: Finding mathematical expressions that fit target data, constrained by a CFG.
- Molecule Search: Navigating a large library of SMILES strings to optimize molecular properties.
Results and Discussion
BOSS consistently demonstrates superior sample efficiency compared to VAE-based methods and standard feature-based BO. In tasks like symbolic regression and molecule search, BOSS found high-performing, valid strings where VAE-based approaches often failed due to the mismatch between the latent representation and the optimization objective.
In protein design, the advantage of the string kernel became more pronounced as sequence length increased. By tuning kernel hyperparameters directly to the objective function during the BO loop, BOSS learns a "supervised" similarity measure that is far more effective for optimization than unsupervised latent representations.
Conclusion
BOSS offers a robust and sample-efficient alternative to latent space BO for string optimization. By operating directly on raw strings using string kernels and grammar-aware genetic algorithms, it bypasses the need for large-scale pre-training and handles complex syntactical constraints naturally. Future work will explore extending this direct optimization philosophy to other discrete structures like graphs and trees.
Summary updated