Generative Models as Adaptive Trust Regions for Discrete Bayesian Optimisation

Michael Dodds; Erik Bodin; Sebastian W. Ober; Tom Diethe; Carl Henrik Ek; Henry Moss

cs.LGOct 12, 2026

Generative Models as Adaptive Trust Regions for Discrete Bayesian Optimisation

Authors: Michael Dodds, Erik Bodin, Sebastian W. Ober, Tom Diethe, Carl Henrik Ek, Henry Moss

Organizations: University of Cambridge · Monumo · BigHat Biosciences · AstraZeneca ·

Abstract

Bayesian optimisation (BO) is a powerful framework for sample-efficient optimisation of expensive black-box functions, but its application to high-dimensional discrete scientific design remains challenging. Local trust-region BO methods such as TuRBO address high dimensionality by restricting search to adaptively sized neighbourhoods. However, a direct discrete analogue based on edit distance can be poorly suited to structured discrete objects: neighbourhoods grow combinatorially, and metric proximity does not capture the dependencies that determine whether a design is plausible or useful. Motivated by the growing availability of pretrained generative models, we introduce GenTuRBO, which replaces the geometric trust region with an adaptively scaled proposal distribution defined by a pretrained generator. The generator provides a learned prior over discrete transformations, encoding coordinated changes without explicitly enumerating edit-distance neighbourhoods. GenTuRBO performs strongly across all three domains and achieves the highest mean final scores on Ehrlich sequence optimisation and Sokoban coordination.

Figures & tables

Figure 1: Generator-guided proposals concentrate probability on feasible sequences. Both panels show the same 24,055 sequences within two substitutions of a fixed length-12 Ehrlich reference over a 20-token alphabet. Each dot represents a distinct sequence: the centre is the reference, the inner ring contains one-substitution variants, and the outer annulus contains two-substitution variants. Left: a uniform distribution over the Hamming neighbourhood assigns 39.44% probability mass to infeasible sequences, rising to 59.63% within four substitutions. Right: 100,000 proposals from a generator trained on feasible sequences assign only 2.62% empirical probability mass to infeasible outcomes. For each generator proposal, two positions are selected for corruption and reconstructed. Sequence locations are shared across panels, with infeasible sequences grouped into a red sector for visual comparison. Marker colour and size on the right indicate proposal frequency.

Figure 2: Feasibility collapses with edit radius. Percentage of length-

256

sequences over a

20

-token alphabet within

k

substitutions of one fixed feasible reference that satisfy the Ehrlich transition rules, shown on a logarithmic vertical axis. Counts are computed exactly (Supplementary Section S2 ). Only

2.8\%

of candidates remain feasible by twelve edits, and at

k=256

— where the neighbourhood covers the entire sequence space — the feasible fraction is

2.28\times 10^{-15}\%

D_{n+|B_{n}|}\leftarrow D_{n}\cup\{(x,f(x)):x\in B_{n}\}.

Algorithm 1 GenTuRBO

Figure 3: Ehrlich optimisation. Mean best-so-far reward with one sample standard deviation across 20 seeds. The dotted line marks the shared 64-evaluation initial archive. Holo GA is recorded at completed-generation checkpoints. Hamming + GP/EI uses direct mutation proposals screened by the spaced-pair GP/EI policy. AdaLead uses root-anchored rollouts and predicted-mean selection.

Method	GFP	AAV
GenTuRBO (Kermut)	$0.983\pm 0.074$	$0.806\pm 0.033$
GenTuRBO (Tanimoto) †	$0.854\pm 0.149$	$\mathbf{0.832\pm 0.035}$
Hamming + GP/EI	$\mathbf{1.161\pm 0.067}^{*}$	$0.824\pm 0.041$
Holo GA	$0.864\pm 0.038$	$0.656\pm 0.028$
AdaLead	$0.906\pm 0.047$	$0.802\pm 0.053$
BO-EVO	$0.624\pm 0.007$	$0.607\pm 0.042$

Table 1: Protein fitness optimisation. Best normalised CNN score after 2,000 charged evaluations, mean

\pm

sample SD over 20 seeds. Bold marks the highest reported mean; ∗ denotes a positive mean difference and

p<0.05

against every other method in that task’s table. There is no explicit feasibility check, so protein results may not correspond to valid designs.

Figure 4: Protein fitness optimisation. Mean best-so-far normalised CNN score with one sample standard deviation across 20 seeds. The 2,000-label budget includes the shared 128-sequence archive. For GFP-Medium, GenTuRBO (Tanimoto) and Hamming + GP/EI fix likelihood noise variance to 0.001 in standardised outcome units; other Tanimoto tasks learn noise. Holo GA points mark completed generations. Hamming + GP/EI uses uniform exact-distance mutation proposals with an adaptive radius, a one-hot Tanimoto GP, and marginal EI on all four tasks.

Figure 5: Sokoban coordination optimisation. (a) Best box-switch score found so far, averaged across 20 seeds. Shading shows one sample standard deviation. Each seed contributes its highest exactly scored

B

. Curves update at recorded batch checkpoints; the dotted line marks the shared 64-query initial archive. (b,c) Highest-scoring boards across the current 20-seed cohorts at 2,000 queries: independent sampling (

B=13

) and GenTuRBO (

B=18

), both independently verified. Amber squares are boxes, purple circles are goals, and blue marks the player. Search implementation details are reported in Supplementary Section S5 .

Setting	Ehrlich	Protein	Sokoban
Design space	256 tokens; alphabet 20	GFP: 237 residues; AAV: 28-residue window	$10\times 10$ grid; four boxes and goals
Frozen generator	Residual CTMC CNN	EvoDiff	Masked Transformer
Initial / online labels	64 / 1,936	128 / 1,872	64 / 1,936
Proposal pool	128	GP: 256; Random: 24	128
Acquired batch	8	8	8
Conditional parent	Best observed sequence	Best observed sequence	Best exactly scored solvable board

Table S1 : Configurations for the main GenTuRBO comparisons. Pool and batch sizes describe generator variants; baseline exceptions are documented separately. GFP-Medium Tanimoto uses fixed likelihood noise variance 0.001 in standardised outcome units; other displayed protein configurations use learned noise.

Task	Length	Published count	Executed rows	Unique sequences	Fitness range	Minimum edits
GFP-Medium	237	2,828	2,828	2,828	$[0.01,0.62]$	6
GFP-Hard	237	2,426	2,426	2,426	$[0.00,0.10]$	7
AAV-Medium	28	2,139	2,145	2,111	$[0.29,0.38]$	6
AAV-Hard	28	3,448	3,453	3,347	$[0.00,0.33]$	7

Table S2: Protein initial-data subsets. Published counts are benchmark reference values; executed rows and unique sequences describe the input CSV subsets used in these experiments. Each search starts from the fixed top-128 archive within its subset. Fitness ranges are those of the benchmark subsets.

Task	$t_{\min}$	$t_{\max}$	$t_{\rm init}$	$\gamma_{\rm expand}$	$\gamma_{\rm shrink}$	$\tau_{s}$	$\tau_{f}$
GFP-Medium / Hard	0.0	0.99	0.75	1.5	0.75	1	1
AAV-Medium / Hard	0.0	0.95	0.50	1.5	0.75	1	1

Table S3: Protein adaptive-noising parameters. The controller updates

r=1-t

; the stored parameter tr_mean is

t_{\rm init}

. The two difficulty levels use the same settings within each protein.

Figure S1 : Requested versus realised absolute edit distance on the Ehrlich mechanism diagnostic. Points show mean parent–proposal Hamming distance at each requested edit budget for all proposals, valid acquisition-eligible proposals, and the eight randomly selected proposals per batch. Error bars span the observed minimum and maximum within each requested-budget group; they are not confidence intervals. The dashed diagonal is exact calibration. Each panel aggregates 20 source seeds and 61,440 raw proposals.

Condition	Population	$n$	Realised edits	MAE
$L=128,Q=4,K=4$	All	61,440	28.66	4.69
	Eligible	55,498	28.62	4.67
	Selected	3,840	28.62	4.66
$L=256,Q=4,K=8$	All	61,440	27.65	5.00
	Eligible	48,799	26.68	4.82
	Selected	3,840	27.53	4.90

Table S4: Absolute edit-budget calibration. Values aggregate 20 source seeds. MAE is the mean absolute difference between the requested and realised parent–proposal Hamming distance.

Method	Final best reward
GenTuRBO	$\mathbf{0.1619\pm 0.0719}^{*}$
Hamming + GP/EI	$0.0563\pm 0.0118$
Holo GA	$0.0586\pm 0.0100$
AdaLead	$0.0555\pm 0.0156$
BO-EVO	$0.0336\pm 0.0105$
LaMBO-2 (online)	$0.0672\pm 0.0114$

Table S5 : Ehrlich sequence optimisation. Best reward after 2,000 charged evaluations, mean

\pm

sample SD over 20 seeds. Bold marks the highest reported mean; ∗ denotes a positive mean difference and

p<0.05

against every other method in that task’s table. Tests are exploratory and unadjusted (Supplementary Section S6 ). Paired tests are used.

Figure S2 : Selected twenty-seed best-so-far trajectories. Lines show the mean incumbent and bands show one sample standard deviation. The dotted line marks the end of the shared 64-evaluation initial archive for iterative policies; unconditional generation has no shared initial archive. Panels use separate reward ranges. The oracle-pool curve is privileged and incurs additional unbudgeted physical scores. Holo GA is shown at completed-generation checkpoints. Hamming + GP/EI screens direct mutation proposals with the same spaced-pair GP/EI policy; AdaLead uses the shared GP with root-anchored rollouts and predicted-mean selection.

Condition	Kernel	Fit (s)	Warm inference (s)
$L=128$	Positional one-hot	0.344	0.012
	Spaced pair ( $W=32$ )	3.315	0.395
	Spaced pair ( $W=48$ )	5.049	0.573
	Spaced trigram ( $W=16$ )	12.158	1.358
	Pair+trigram additive	14.443	1.931
	Task-aware (privileged)	0.595	0.046

Table S8: Ehrlich kernel fitting and inference cost. CPU double-precision measurements on held-out source seed 0: one fit and the median of warm posterior calls two and three, with the first call excluded and garbage collection outside measured intervals.

Figure S3 : Five-seed online Ehrlich kernel confirmation. Curves show mean best reward so far and shaded bands show one sample standard deviation. The dotted line marks the end of the shared 64-evaluation initial archive. Panels use separate, condition-specific reward scales. The comparison is exploratory because it contains only five paired seeds.

Method	Best $B$
GenTuRBO	$\mathbf{12.450\pm 2.438}^{*}$
Hamming + GP/EI	$5.350\pm 1.137$
Direct-grid GA	$7.500\pm 1.701$
AdaLead	$6.950\pm 1.791$

Table S10 : Sokoban coordination optimisation. Best minimum box-switch count after 2,000 charged evaluations, mean

\pm

sample SD over 20 seeds. Bold marks the highest reported mean; ∗ denotes a positive mean difference and

p<0.05

against every other method in that task’s table. Tests are exploratory and unadjusted (Supplementary Section S6 ). Paired tests are used.

Method	Final best $B$	Maximum $B$	Solvable	Unresolved / 40,000
Independent sampling	$9.450\pm 1.669$	13	88.09%	146
Direct-grid GA	$7.500\pm 1.701$	11	11.22%	62
AdaLead	$6.950\pm 1.791$	11	19.79%	4
Hamming + GP/EI	$5.350\pm 1.137$	9	2.85%	4
GenTuRBO	$\mathbf{12.450\pm 2.438}$	$\mathbf{18}$	$\mathbf{88.76\%}$	127

Table S11 : Sokoban outcomes and solver coverage. Final best

B

is each seed’s best exact score after 2,000 queries, reported as mean

\pm

sample SD over 20 matched seeds. Maximum

B

is the highest exact score across all seeds; solvability and unresolved counts cover all 40,000 charged queries per method. Bold marks the highest score or solvability; unresolved counts describe solver coverage rather than an optimisation target.

Noising scale	Proposal selection	Final best reward
Random time	Random	$0.0844\pm 0.0245$
Random time	GP	$0.1070\pm 0.0270$
Adaptive	Random	$0.1266\pm 0.0368$
Adaptive	GP (GenTuRBO)	$0.1619\pm 0.0719$

Table S13 : Ehrlich component comparison. Final best reward under the shared 2,000-evaluation protocol. All GP arms use the spaced-pair kernel.

Method	GFP-Medium	GFP-Hard	AAV-Medium	AAV-Hard
RT + Random	$0.623\pm 0.004$	$0.300\pm 0.050$	$0.565\pm 0.058$	$0.445\pm 0.043$
RT + GP	$0.627\pm 0.019$	$0.284\pm 0.083$	$0.759\pm 0.049$	$0.668\pm 0.061$
TR + Random	$0.672\pm 0.057$	$0.644\pm 0.077$	$0.680\pm 0.040$	$0.534\pm 0.061$
GenTuRBO (Kermut)	$0.983\pm 0.074$	$0.845\pm 0.069$	$0.806\pm 0.033$	$0.757\pm 0.090$
RT + GP (Tanimoto) †	$0.623\pm 0.004$	$0.368\pm 0.064$	$0.780\pm 0.048$	$0.697\pm 0.090$
GenTuRBO (Tanimoto) †	$0.854\pm 0.149$	$0.933\pm 0.081$	$0.832\pm 0.035$	$0.766\pm 0.109$

Table S14: Protein component and surrogate comparison. Best normalised CNN proxy score at 2,000 charged evaluations. GP denotes Kermut unless Tanimoto is named; Random arms do not use a surrogate for selection. † Both GFP-Medium Tanimoto arms fix noise variance to 0.001 in standardised outcome units; other Tanimoto tasks learn noise.

Component	TuRBO	GenTuRBO
Centre	Incumbent	Incumbent or archive parents
Local region	Geometric trust region	Generator-defined proposal distribution
Scale	Region size	Noising depth
Adaptation	Success/failure	Success/failure
Surrogate	GP	GP
Acquisition	Candidates within region	Generated candidate pool

Table S15: From TuRBO to GenTuRBO. Comparison with a single TuRBO region.

Bayesian Optimization

Bayesian optimization uses probabilistic models and sequential experiments to find strong solutions when evaluating a black-box objective is costly.

See all 240 papers

Acquisition Function-Guided Generation for Bayesian Optimization over Discrete Spaces
Oct 16, 2026Tommaso Ancilli, Thomas Wedenig, Henry Moss +1Bayesian Optimization Molecular Optimization
Institute of Machine Learning and Neural Computation, TU Graz, Austria · Graz Center for Machine Learning (GraML), Austria · School of Mathematical Sciences, Lancaster University, UK
Rethinking Trust Region Bayesian Optimization in High Dimensions
Apr 24, 2026Wei-Ting Tang, Joel A. PaulsonBayesian Optimization Black-Box Optimization
University of Wisconsin–Madison
Memory-Guided Trust-Region Bayesian Optimization (MG-TuRBO) for High Dimensions
Mar 25, 2026Abhilasha Saroj, Shaked Regev, Guanhao Xu +3Bayesian Optimization Black-Box Optimization

Oct 16, 2026J/K move · Enter open · S save

Acquisition Function-Guided Generation for Bayesian Optimization over Discrete Spaces

Tommaso Ancilli, Thomas Wedenig, Henry Moss, Robert Peharz

Institute of Machine Learning and Neural Computation, TU Graz, Austria · Graz Center for Machine Learning (GraML), Austria · School of Mathematical Sciences, Lancaster University, UK

Bayesian Optimization Molecular Optimization

Open paper AskPDF arXiv

Bayesian optimization (BO) over discrete spaces is challenging due to missing gradients and the sparsity of valid solutions. Latent-space BO sidesteps both issues by fitting a surrogate in the latent space of a generative model, which however substantially complicates the direct incorporation of domain knowledge that is naturally expressed in the original discrete space. In this work, we instead combine a pretrained generative model with a surrogate defined directly in data space, where inductive biases such as domain-specific kernels can be readily incorporated. Rather than maximizing the acquisition function over the discrete design space, our method samples candidates from the generative model under a distribution tilted by the acquisition function. To recover useful gradients for sampling, we embed this tilted distribution into a diffusion bridge that yields a smooth, posterior-averaged acquisition function. This leads to acquisition function guided generation (AFGG), which we instantiate with a categorical diffusion model and an autoregressive normalizing flow. Across a broad suite of molecular benchmarks, the diffusion model variant performs on par with leading BO methods, while the flow model variant outperforms state-of-the-art methods in most cases and remains highly competitive otherwise. Our implementation is available at https://anonymous.4open.science/r/afgg.

Abstract

Bayesian Optimization

Explore similar work

Acquisition Function-Guided Generation for Bayesian Optimization over Discrete Spaces

Rethinking Trust Region Bayesian Optimization in High Dimensions

Memory-Guided Trust-Region Bayesian Optimization (MG-TuRBO) for High Dimensions