Tractable Bayesian Optimization over Combinatorial Protein Spaces

Protein engineering requires optimizing sequences with limited experimental data over combinatorial spaces of up to $20^L$ variants. Gaussian processes (GPs) provide data-efficient surrogates, but optimizing acquisition functions over these spaces is computationally challenging. We introduce BaLiSq, a framework that addresses this bottleneck by recasting any kernel on single-mutant variants as a Bayesian linear regression prior over one-hot variant features. BaLiSq is provably equivalent to GP regression with the original kernel on single-mutant variants and extends additively to multi-mutant variants. This reformulation enables exact constrained Thompson sampling over the combinatorial design space. Using the Kermut kernel, BaLiSq substantially outperforms established multi-mutant predictors in the low-data regime while matching their performance as data grows. BaLiSqO combines BaLiSq with Thompson sampling and achieves lower mean regret than directed evolution based baselines on simulated landscapes. Together, these results demonstrate that kernel-informed additive models combine data-efficient prediction with tractable acquisition optimization over large combinatorial sequence spaces.