acceptodds
Under review as a conference paper at ICLR 2027

Tractable Bayesian Optimization over Combinatorial Protein Spaces

Abstract

Protein engineering requires optimizing sequences with limited experimental data over combinatorial spaces of up to 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.

Primary area:
applications to physical sciences (physics, chemistry, biology, etc.)
Keywords:
Protein Engineering, Bayesian optimization, protein variant effect prediction, Bayesian linear regression, active learning, combinatorial optimization, Thompson sampling

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_mLrKOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses an practical problem: efficiently selecting promising protein variants when the combinatorial search space is large and experimental evaluations are expensive. This paper introduces BaLiSq, a Bayesian linear regression framework for protein sequence optimization that constructs a Gaussian prior over substitution weights from a positive-definite kernel defined on single-mutant variants. Building on BaLiSq, the authors propose BaLiSqO, a Bayesian optimization method based on Thompson sampling over mutation-constrained combinatorial protein spaces. The paper also derives a closed-form information-gain expression and evaluates predictive performance on ProteinGym multi-mutant assays, as well as optimization performance on simulated landscapes involving FoldX, RaSP, and a ProGen2-derived score.

Critical strengths

S1. The paper uses a kernel on single-mutant variants to construct a prior over substitution weights, preserving a connection to GP regression in the single-mutant setting while obtaining an additive representation for multi-mutant sequences. This offers a practical compromise between incorporating kernel-derived information and maintaining a tractable representation of large combinatorial spaces.

S2. The sampled linear objective can be optimized efficiently under a mutation-count constraint, avoiding explicit enumeration of the entire candidate space. The treatment of previously selected variants and the closed-form information-gain result further develop the framework into a usable Bayesian optimization approach rather than merely a predictive model.

Critical weaknesses

W1. The equivalence to GP regression on single mutants is an important characterization, but by itself it does not establish a substantial methodological advance. Likewise, additive sequence models and Thompson sampling are established ideas. The most distinctive contribution appears to be their particular combination: kernel-induced Bayesian substitution weights, structured posterior covariance on multi-mutants, and tractable constrained acquisition optimization.

The paper would be stronger if it more clearly isolated the benefit of this combination relative to the closest existing approaches. The current results suggest that the method can be useful in low-data regimes and competitive in data-rich regimes, but do not fully establish which of its design choices account for the observed gains or when those gains are most reliable.

W2. The computational objectives provide controlled and reproducible test cases, but their evidential scope is limited. In particular, additive FoldX/RaSP settings cannot establish robustness to arbitrary substitution-specific interactions, and a ProGen2-derived score is not equivalent to experimentally measured protein fitness.

The paper acknowledges that its additive predictive mean does not model arbitrary epistasis. This is a reasonable design choice in some low-data regimes, but it also defines a meaningful boundary on the method's applicability. The current evidence does not establish that the reported optimization advantage generalizes to experimentally measured landscapes dominated by specific interactions.

Questions for authors

Q1. Could the authors more explicitly distinguish the contribution of BaLiSq from existing kernel-based Bayesian regression and additive sequence models? In particular, which experiments demonstrate that the combination of kernel-induced weight covariance and tractable Thompson sampling provides an advantage beyond the additive mean representation alone?

Q2. Can the authors provide evidence on an available experimentally measured multi-mutant landscape with meaningful epistasis, or otherwise clarify the scope of the conclusions supported by the current computational objectives? It would be particularly helpful to distinguish the intended low-data use case from settings where specific higher-order interactions dominate.

2 comments

We thank the reviewer for their careful efforts and constructive feedback. We will upload the revised manuscript before the revision deadline.

W1+Q1

We agree with the reviewer that a clearer understanding of what drives the observed gains would strengthen the study. In response to this suggestion, we have now added additional ablations and baselines to the study to isolate the benefits of our approach.

For the optimization part we have:

  • Kernel-induced prior covariance. Isotropic TS has swapped the Kermut prior for an isotropic covariance matrix but is otherwise equal to BaLiSqO. This shows the importance of the prior kernel choice.
  • Additional comparators.
    • We include BOCS-SA, a related method for Thompson sampling that includes pairwise interactions. This model achieved comparably to random selection, and we speculate it is because of the enormous number of parameters it tries to fit.
    • Moreover we are currently running LaMBO2 (discrete diffusion), but the heavy model’s runs are still ongoing (see our response to reviewer G8EQ for preliminary results).
  • Use of posterior uncertainty.
    • BaLiSqO ShuffleVar compares the effect of the uncertainty estimates of BaLiSqO to a version where these have been shuffled (see appendix), showing the importance of the uncertainty estimates.
    • BaLiSqO Zero Uncertainty completely removes the uncertainty estimates, comparing BaLiSqO to a completely exploitative greedy version (see appendix), showing the importance of an exploration component.
  • Selection policy.
    • MLDE compares the BO setting of BaLiSqO to a "one mutation at a time" approach, showing the value of free exploration in the entire design space from the start.

Figure 2 and C1 shows that BaLiSq performs better (in terms of prediction) than competing methods when we have less observations than the number of possible substitutions in the design space. Figure C1 shows how much of this is due to the prior mean and how much is the kernel.

We expect that once the training data grows substantially above the design space, non-additive models will be able to model the interaction effects and get better predictions than an additive model. Our method focuses on the low-data regime in a large design space that characterizes many experimental settings. Here batch sizes are usually 96 and only a limited number of batches are evaluated. Figure 2 shows that in this regime it is hard to learn more than additive effects. Though there might be epistatic effects, it would require much more data to model it and our point is, that if you do not have that much data, then an additive model can offer a useful balance between predictive performance and computational tractability.

W2+Q2

We thank the reviewer for highlighting this limitation. We have added a dedicated evaluation on the experimentally measured four-site GB1 landscape (Figure C6), comparing BaLiSq with the ALDE DNN ensemble and MULTI-evolve across training-set sizes.

In five-fold cross-validation with more than 100,000 training variants per fold (Figure C5), neither neural-network baseline consistently outperforms BaLiSq, showing that greater model flexibility does not automatically translate into better predictions on an experimental landscape with meaningful epistasis, even with substantial training data.

We agree that in silico objectives such as additive FoldX/RaSP- or ProGen2-derived scores are not equivalent to experimentally measured protein fitness. Ideally, we would validate optimization experimentally, but we unfortunately do not have access to wet-lab facilities. A comparable wet-lab benchmark would however require independent campaigns for each method, repeated across starting proteins and runs resulting in hundreds of experimental campaigns per batch (23 wild types x 6 baselines x 3 repeats for statistical inference). Even with access to wet-lab facilities, this would require substantial experimental resources and time. We therefore use computational oracles as rational alternatives for controlled optimization comparisons.

We chose to use an additive version of FoldX, because of its computational complexity, but are now rerunning the study with the non-additive (epistatic) version of FoldX Stability and will include the results in the camera ready version.

As complementary evidence, Figure 2 evaluates the underlying base BaLiSq model on real DMS datasets with experimentally measured fitness values. While BaLiSq does not explicitly model substitution-specific interactions, its predictive performance shows that it can still accurately predict experimental multi-mutant fitness in the evaluated low-data settings.

We appreciate this suggestion and have clarified the distinction between experimental wet-lab validation and computational optimization benchmarks in the discussion of the manuscript and will add the non-additive (epistatic) version of FoldX in the camera ready version to strengthen the paper with an additional epistatic oracle.

Reviewer_G8EQOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper introduces BaLiSq (Bayesian Linear Regression of Sequences), which is Bayesian linear regression over protein variants, which is using any positive-define kernel on single mutant protein variants. The Authors prove theoretical properties of a BaLiSq like additivity on single-mutant variants. The Authors combines BaLiSq with Thompson sampling, which results in Bayesian Optimization method (BaLiSqO). The Authors shows that additive structure of BaLiSq allows for feasible exact Thomson sampling. In contrast to naive dense joint GP sampling over the full design space, which is infeasible. The Authors evaluate BaLiSq on ProteinGym multi-mutant variant dataset and show the increased or comparable performance. The Authors evaluate BaLiSqO on optimizing in silico oracles task measuring mean regret on the best variants and mean regret on diverse set of variants.

Critical strengths
  1. The authors propose an feasible Bayesian Optimization algorithm which leverages Bayessian linear regression model with weights corresponding to single-mutation variants and apply it to protein optimization. This method may serve as a foundation to further research on Bayesian Linear Reggression models used for optimization of proteins.

  2. The authors measure not only a performance of optimization but also the diversity of the results. The procedure of assessing the diversity is general and can be used to various tasks.

Critical weaknesses
  1. The authors didn't compare to other newer baselines for protein optimization. Especially other Bayesian Optimization for sequence design, like LaMBO2. It would be beneficial to compare to them or argue why it is not relevant.
Questions for authors
  1. Is it possible to use other acquisition functions with BaLiSq to obtain other Bayesian Optimization methods?
2 comments

We thank the reviewer for their efforts and feedback. We will upload the revised manuscript before the revision deadline.

Weaknesses

Thank you for suggesting LaMBO2. Its guided discrete diffusion for protein optimization is a relevant comparator. In our original submission we prioritized comparisons that isolate the effects of our design choices. We are now working on adding LaMBO2. As it is quite heavy to run it is not finished on all benchmarks yet. So far we have results for 5 protein-oracle combinations, where it ranks above Random and BOCS, but below MLDE and BaLiSqO, both on final and cumulative regret. We will include the final results in the camera ready version. Moreover we have added BOCS and Isotropic TS as suggested by reviewer ofbD.

Final normalized regret on the completed runs. Lower is better.

Protein / oracleSeedBaLiSqOMLDELaMBO2BOCSIsotropic TSDERandom
AMIE_PSEAE / FoldX Stability00.2000.1730.7190.8410.7140.3500.883
HIS7_YEAST / FoldX Stability00.0870.2570.7390.8770.6940.2480.812
POLG_PESV / FoldX Stability00.0000.0000.1650.6650.3930.2130.581
POLG_PESV / FoldX Stability10.0000.0550.1120.6670.5290.1190.649
POLG_PESV / FoldX Stability20.0000.0330.0710.5660.3900.2030.674
SBI_STAAM / ProGen200.0000.0760.0910.7190.0380.1690.692
VRPI_BPT7 / ProGen200.0120.0770.2240.6540.0410.3180.698

Questions

Yes, it is possible to use other acquisition functions with BaLiSq, such as EI or UCB using the predicted mean and variance. However, their optimization generally loses the additive separability that makes our implementation of Thompson sampling tractable.

Other acquisition functions such as those based on expected information gain (EIG), often rely on being calculated over the entire design space. Using BaLiSq we can instead efficiently and exact calculate EIG over the parameters of the model which are interpretable and reflect the EIG over the design space (see appendix A.4).

We agree that clarifying this would strengthen the paper and have now clarified it in the discussion of the revised manuscript.

Reviewer_ofbDOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents BaliSq, a Bayesian Linear regression model on Sequences, which uses the Kermut kernel to form a prior for Bayesian linear regression & thompson sampling in weight space. At iteration tt this inolves fitting the kernels hyperparameters to the existing data Dt−1D_{t-1}  to form them prior, then sampling a weight vector w∼N(μw∣Dt−1,Σw∣Dt−1)w\sim \mathcal{N}(\mu_{w| D_{t-1}},\Sigma_{w | D_{t-1}}) , and using this to form the function ft(x)=μb+xTwtf_t(x)=\mu_b+x^Tw_t to perform exact constrained arg⁡max⁡x∈XM∖Eft(x)\arg \max_{x \in X_M \setminus E} f_t(x)   thompson sampling sampling to collect the data to label to form the additional data collected in round t to form the next dataset DtD_t once labelled.

    The paper provides propositions about the properties of the proposed method and evaluates it against 4 oracles (3 additive by construction - rasp,foldx sasa, foldx tability +   1 epistatic - progen2 sequence likelihood  pooled into an empirical pseudo regret) on proteingym datasets wtih multi-mutant variants, comparing against kermut-GP,MoCHI,MULTI-evolve surrogates, and later comparing the thompson sampling form BaLiSQ against DE, MLDE and  rnadom search, again performing competetively..

Critical strengths
  1. The paper is mainly written cleanly and understandably, altough I think the writing would have been better without LLM. I appreciate that the text does not read as sloppy as “writing and polish the writing of the manuscript” would imply and thank the autors for the effort.

  2. The combination of ideas applied to protein engineering appears novel and worthwhile, if properly framed and evaluated

Critical weaknesses
  1. Theoretical novelty is overstated, the similarity to prior art is not properly framed and acknowledged

    1. The papers method is exactly BOCS https://arxiv.org/abs/1806.08838 with the interaction terms nulled out (leaving a linear model) , using the Kermut kernel instead of the horseshoe prior and replacing the soft penalty with a strict constraint on numbers of mutations.  The paper just mentions they don’t apply to proteins, but don’t credit the similarity

    2. Propositions 1 to 5 are trivial or well known  (1 + 2 are textbook from the GP book, 3 is https://arxiv.org/abs/1503.01673  +  uniform matroid greedy   and pigeonhole arguments, 4  is the Bernstein–von Mises theorem (see e.g. van der Vaart, Asymptotic Statistics 1998, Ch 10)  ,5 is gaussian channel mutual information, e.g. the Lindsay 1956 paper the submission cites

    3. The additive model is by construciton, and does not need a proof

  2. The empirical evaluation/results are weak:

    1. for the progen oracle on the BaLiSqO vs MLDE comparison the method has overlapping CI with a baseline

    2. the other oracles are close on the same dataset

    3. the paper discloses that the CI are not paired tests => why not perform the paired tests?

    4. the baselines are not the real prior art: missing ALDE, TS-DE,BOCS or isotropic BRR + TS, which would be closer comparisons

    5. if I see correctly, there is only one oracle that isn’t additive by construction,and the one that is progen2s biased  pooled pseudo regret => this is biased towards making the additive model look good, and should be grounded on some deep mutational scanning dataset e.. GB1

Combined, I think the paper is framed as too novel, if all prior art was acknowledged and better evaluation was performed, I think it would be a decent incremental work

Questions for authors

Suggestion for improvement:

  1. Did you consider using Falcon or https://proceedings.mlr.press/v119/wilson20a/wilson20a.pdf to run the kermit GP on the datasets it did not finish on? Can you get the comparisons on those?
3 comments

We would like to thank the reviewer for their thorough feedback and input on related work. The results below refer to the revised manuscript, which we will upload before the revision deadline.

W1

We acknowledge your points. Our first submission was over-compressed, and was lacking some clarity on the theoretical part and on the relation to BOCS. We have now elaborated on these topics and rephrased several sections to make our contribution clearer.

1)

We acknowledge the similarity to BOCS and have expanded the related work section to reflect it explicitly. BOCS combines Bayesian regression over combinatorial features with Thompson sampling over the weights. BaLiSq uses a kernel on single-mutant variants to specify a prior over substitution effects. Its first-order representation permits exact maximization of each posterior draw under a mutation budget.

2)

We agree that our original contribution statement did not sufficiently distinguish established results from the contribution of the proposed construction. Our intention was to characterize the model and explain the consequences of using a kernel-induced prior over substitution effects. We have revised the contribution statement and the presentation of the propositions to make this distinction explicit.

Specifically, we now describe GP equivalence and additivity as a characterization, explicitly attribute Propositions 1–2 to the standard GP weight-space formulation, and clarify the connections to established results before Propositions 3–5.

  • The contribution point has been updated to a characterization, so that it doesn't sound like we are giving a novel proof (section 1).
  • We now explicitly write that proposition 1 and 2 are specializations of the weight-space formulation from Rasmussen & Williams (2006) (section 4).
  • We have also updated the introduction to proposition 3, citing relevant work, and acknowledge Kandasamy et al. (2015) in related work (section 4 and 6).
  • Appendix A.4 attributes Bernstein–von Mises theorem and Lindley explicitly before proposition 4 and 5 respectively.

3)

We agree that the model is additive by construction and have now stated this explicitly in the contribution point. The purpose of Proposition 2 is to spell out what this choice implies for predictions, and the posterior variance of a multi-mutant.

W2

1-3 

Thank you for raising this point. We have updated Table 1 to report paired comparisons across wild types. For MLDE minus BaLiSqO, the final-regret differences are 0.052 [0.031, 0.070] on the additive panel and 0.055 [−0.002, 0.101] on ProGen2. The cumulative-regret differences are 0.788 [0.675, 0.888] and 0.499 [0.046, 0.912], respectively.

DE (directed evolution), MLDE, and ALDE are all very successful methods for protein engineering. However, ALDE is limited by the size of the design space, while DE and MLDE are limited by their incremental nature only allowing them to explore a single mutation from the current reference sequence at each iteration - it is these limitations that our method address by enabling free optimization over the entire space of possible combinations of substitutions.

The limitations of MLDE and DE make them slow and less diverse, requiring evaluation of M batches to search for a variant with M mutations. BaLiSqO speeds up this process substantially by being able to explore the space of M mutations from the start.

We have in the experiment in table 1 restricted BaLiSqO to only 6 mutations, to investigate the difference between BaLiSqO and MLDE in the scenario that is most favorable for MLDE, i.e. when M=B (the number of allowed mutations is equal to the number of batches). Figure C4 and C5 illustrate that if we increase M, BaLiSqO performs increasingly better compared to MLDE (we have now included additional runs of BaLiSqO for different values of M).

The cumulative regret shows that BaLiSqO can obtain good results faster than MLDE, and the final regret shows that even if we run 6 batches, we are not worse off than if we used MLDE. Hence, a practitioner may need to run fewer batches by increasing the allowed number of mutations for BaLiSqO (Figure C4 and C5).

We have now explained this more clearly in the paper and updated the confidence intervals to being paired.

4-5

Thank you for suggesting relevant baselines. We agree that BOCS and Isotropic BRR + TS are relevant baselines and have now included both.

Isotropic TS retains the ESM prior mean, additive representation, and Thompson-sampling procedure, with the prior covariance replaced by an isotropic matrix. Its final normalized regret is higher than BaLiSqO by 0.336 [0.299, 0.374] on the additive panel and 0.206 [0.112, 0.314] on ProGen2 (paired 95% intervals, Table 1). This supports the value of the kernel-induced covariance in the evaluated setting.

BOCS-SA performs similarly to random selection in our benchmark. The comparison changes both the prior and the interaction model, so it does not isolate the reason for that outcome. We speculate it is because of the enormous number of parameters it needs to fit.

TS-DE is phrased as a method for binary inputs and its directed mutation and crossover selection makes the mutation count explode unless substantially restricted. It could in principle be adapted to a categorical input and with a restricted mutation count, but we see this as out of scope for this paper.

To our understanding ALDE requires a complete enumeration of the entire design space. Using ALDE on a restricted design space (e.g. on 4 sites as in the GB1 dataset) with our model and Thompson sampling would result in the same optimization procedure. Our method is a way to enable this strategy to work on larger design spaces, where a complete enumeration becomes infeasible. We have now included the DNN ensemble model from ALDE in the prediction comparison (figure 2) - demonstrating that BaLiSq obtains better prediction results when the training set is small and similar results on the largest training data size. We also compare their predictions on GB1 on the small training sets as well as a larger cross validation with >100,000 training points (figure C5) where BaLiSq obtains better performance than the neural network based methods - indicating the difficulty of modelling epistatic effects.

These results suggest that even if we could enumerate all possible variants in a large design space with a model such as the DNN ensemble from ALDE or the NN from MULTI-evolve, it would not give us better predictions than our additive model.

Questions

Thank you for the suggestions. We have now optimized the Kermut implementation, so that it can fit on the larger datasets. Figure 2b now includes all 17 assays, including the seven previously omitted because Kermut did not finish. We have updated the appendix accordingly.

Thanks again for your feedback.

Comments on the paper

1 comment

Dear Reviewers,

Thank you for your time and valuable feedback.

We have uploaded a revised manuscript that incorporates your feedback.

Upon acceptance, we will include the LaMBO2 results and the benchmark results on the non-additive (epistatic) version of FoldX Stability in the camera ready version (both are still in progress).

Best regards,
The authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.