Adaptive Path-Auxiliary MCMC for Fragment-Based Molecular Design

Searching chemical space for molecules with a desired combination of properties is, at its core, a sampling problem: we want draws from a distribution concentrated on high-scoring, synthesizable structures, spread across many distinct molecular scaffolds rather than piled onto one lucky hit. Molecular design methods usually treat this as pure optimization — genetic algorithms, policy-gradient reinforcement learning, Bayesian optimization — which finds peaks but famously collapses onto them. Meanwhile, the Monte Carlo literature has spent a decade building a different toolbox: proposal distributions that adapt online to the landscape they are exploring, including learned proposal kernels for discrete spaces. Almost none of that machinery has been pointed at molecules. The one exception, MARS, uses a neural network to propose fragment edits but trains it heuristically and cannot compute the reverse proposal probabilities that correct sampling requires.

This note proposes to build a sampler for molecular graphs that combines three ideas from adaptive-proposal research, none of which has ever been applied to chemistry: multi-step path-auxiliary proposals that leap over "activity cliffs" (small edits that destroy a molecule's usefulness); learned, locally balanced proposal kernels trained with an information-theoretic objective instead of imitation; and a two-stage delayed-acceptance scheme in which a cheap surrogate ensemble screens proposal paths so that the expensive property oracle is only consulted for promising endpoints. The payoff we aim for is sample efficiency — more good molecules per oracle call — under exactly the tight evaluation budgets where the field has shown modern generative models struggle.

Core Claim

A Markov chain Monte Carlo sampler over fragment-based molecular graphs, whose proposal is a path of $L$ locally balanced fragment edits with a learned balancing function, an adaptively tuned path length, and surrogate-based delayed acceptance, will match or beat the strongest practical molecular optimization methods on the PMO benchmark's 1,000-oracle-call budget while preserving the diversity that pure optimizers lose. Each ingredient is motivated by a demonstrated result on non-chemical discrete spaces: path auxiliary sampling beat Gibbs-with-Gradients on deep energy-based models (log-likelihood −84.56 versus −96.20 on Caltech Silhouettes in Path Auxiliary Proposal for MCMC in Discrete Space), and learned balancing functions nearly tripled effective sample size over the best fixed function on Ising models (20.11 versus 7.08 in LSB: Local Self-Balancing MCMC in Discrete Spaces). Our claim is that these gains transfer to molecular graphs, where the pathology they fix — single-step proposals trapped by sharp energy barriers — is precisely the activity-cliff problem.

Research Program

The target distribution is the one MARS introduced: $p(x) \propto \exp(S(x)/T)$, where $S(x)$ is a composite score over a molecule's properties and $T$ an annealing temperature, so that sampling and optimization are the same operation at low $T$. Our state space is molecules represented as fragment assemblies, using the SAFE fragmented-SMILES encoding popularized by Refine Drugs, Don't Complete Them: Uniform-Source Discrete Flows for Fragment-Based Drug Discovery, which lets a single edit swap, insert, or delete one fragment while keeping the string chemically well-formed most of the time.

The first ingredient is the path-auxiliary proposal from Path Auxiliary Proposal for MCMC in Discrete Space. Instead of proposing one edit and accepting or rejecting it, the sampler takes $L$ informed local edits in a row and accepts the endpoint, with the acceptance probability

$$\alpha(x, x') = \min\left(1, \frac{\pi(x')\, q(x \mid x')}{\pi(x)\, q(x' \mid x)}\right)$$

depending only on the start and end states when each step is locally balanced — the intermediate transitions cancel telescopically. This is what lets long proposals survive without exponentially decaying acceptance, and in chemistry it is exactly what is needed to cross an activity cliff: any single edit on the path may produce a useless intermediate, but the chain can still jump to a good molecule on the other side. PAS was formulated and validated only on binary lattices and image grids; extending local balance and path telescoping to fragment graphs with valence constraints is the first technical contribution.

The second ingredient is learned balancing. A locally balanced proposal weights each possible edit $x \to x'$ by a balancing function $g$ of the local density ratio — Barker's rule or a square root in classic work — and LSB showed that parameterizing $g$ as a small network and training it to minimize a surrogate upper bound on the mutual information between consecutive states beats every fixed function on heterogeneous landscapes. We will train $g_\theta$ online during sampling with the same objective, adapting the edit preferences to the local chemistry of the current region of chemical space. This directly replaces MARS's self-training of its proposal MPNN on visited high-scoring edits, which MARS: Markov Molecular Sampling for Multi-objective Drug Discovery itself flags as heuristic. The choice of a principled objective is not aesthetic: Harnessing the Power of Reinforcement Learning for Adaptive MCMC showed that intuitive adaptive-MCMC rewards (jump distances, acceptance rates) cause catastrophic failures on 7% of benchmark posteriors, while a derived contrastive-divergence bound was stable — evidence that ad-hoc training signals for proposal adaptation are a real failure mode, not a style choice. To avoid the known warm-up degradation of learned proposals, we initialize $g_\theta$ at Barker's rule and blend in the learned component only after a fixed burn-in, with diminishing adaptation thereafter to protect ergodicity.

The third ingredient is adaptive path length, which PAS explicitly leaves open — $L$ is a static hyperparameter with no discrete analogue of the No-U-Turn criterion. We will grow each path until the surrogate-estimated score trajectory of the fragment edits turns back on itself (a "U-turn" in fragment-score space) or a validity constraint is hit, capping $L$ to bound cost. Path-length adaptation is what turns the cliff-leaping mechanism from a tuned constant into a sampler that spends short paths in smooth regions and long paths across barriers.

Finally, sample efficiency. Under PMO's 1,000-call budget the binding cost is oracle evaluations, not sampler steps, so we adopt delayed-acceptance Metropolis-Hastigans as in Accelerating sequential Monte Carlo with surrogate likelihoods, which reported raw speedups up to $8.8\times$ by filtering proposals through an adaptively tuned cheap surrogate before the expensive target is evaluated. Our surrogate is a small adaptively weighted ensemble over two or three fingerprint representations, following the finding in MolLIBRA: Genetic Molecular Optimization with Multi-Fingerprint Surrogates and Text-Molecule Aligned Critic that no single representation covers all tasks; the surrogate scores path steps and serves as the first acceptance stage, and only first-stage survivors consume a true oracle call as the second stage. The same design also answers PAS's $O(nL)$ path-cost concern, since path interiors never touch the oracle.

Baselines

The do-nothing reference is a uniform random fragment-edit sampler: at each step pick a SAFE fragment position and a replacement uniformly from the vocabulary, accept with the standard Metropolis ratio. This isolates what any informed proposal buys, and it doubles as the fixed-balancing ablation's floor. The strongest existing method on our primary benchmark is MolLIBRA-L, which couples genetic molecular edits with an adaptive ensemble of six Gaussian-process surrogates and a text-molecule aligned critic; on PMO at a 1,000-call budget it achieved the best Top-10 AUC on 14 of 22 tasks and the highest sum of Top-10 AUC, 14.208, versus 12.569 for the next-best method, Tripp's GP Bayesian optimization, as reported in MolLIBRA. Beating it means a higher sum of Top-10 AUC across the full PMO task suite at the same 1,000-call budget. The strongest MCMC competitor is MARS, whose message-passing network proposes fragment edits trained by self-training; on the four-objective GSK3β/JNK3/QED/SA task it improved the product-of-metrics score by 77% over RationaleRL while keeping novelty above 80%, at roughly 12 hours of convergence time, per MARS. Also included are Graph GA and REINVENT, because Sample Efficiency Matters: A Benchmark for Practical Molecular Optimization found REINVENT ranked first and Graph GA second of 25 algorithms under a 10,000-call limit. All methods will be run with the same oracle implementations, the same 1,000-call budget (and a 10,000-call variant), the same starting molecules, and the same tuning budget — a fixed grid of random hyperparameter configurations per method, counted against wall-clock parity rather than only oracle calls, so that MARS's heavy per-step cost is honestly accounted. Finally, three ablations isolate our ingredients: fixed Barker balancing in place of learned $g_\theta$; a fixed path length in place of the adaptive U-turn rule; and self-training of the proposal on visited high-scoring edits (MARS's objective) in place of the mutual-information bound. Each ablation changes exactly one component.

Why not just…?

Why not just use Graph GA or REINVENT? This is the most serious objection, and we will not argue around it. Sample Efficiency Matters showed that these older, simpler methods beat nearly all modern deep generative models under realistic budgets, so if our sampler does not beat them on PMO's Top-10 AUC, the proposal fails on its own terms. The counter-evidence is about what they lose: MARS documented genetic-algorithm mode collapse onto a few lucky scaffolds while MCMC maintained diversity above 80% novelty, and REINVENT-style policy gradient optimization is known to produce repetitive scaffold variations. Our decisive check is therefore two-sided: we report PMO Top-10 AUC against Graph GA and REINVENT directly, and we report scaffold-diversity-adjusted discovery (top scores binned by distinct Bemis-Murcko scaffolds). If we lose on AUC and win only on diversity, we will report that honestly — the value of the sampler would then rest on multi-objective tasks where mode collapse is costly, such as the GSK3β/JNK3 setting where MARS already showed MCMC's advantage.

Why not just keep MARS's self-trained proposal network? MARS already does adaptive neural proposals on fragments, so the marginal value of our proposal machinery must come from the training objective and the path structure. The evidence that self-training is the weak part is indirect but concrete: LSB showed learned balancing functions trained on an information-theoretic bound roughly tripled effective sample size over the best fixed alternative on heterogeneous discrete targets, and the adaptive-MCMC reinforcement-learning work showed heuristic training rewards destabilize sampling on a measurable fraction of tasks while derived objectives do not. Our ablation that swaps the mutual-information objective for MARS-style self-training, holding the path machinery fixed, is designed precisely to settle whether the principled objective matters in chemistry or the gains come entirely from multi-step paths. If self-training matches it, we will conclude the path structure is the contribution and drop the learned balancing claim.

Why not just apply PAS with a fixed balancing function and tuned $L$? The simplest version of our idea is PAS ported to SAFE tokens with Barker's rule and one well-chosen path length, which a skeptical reviewer would rightly demand first. Two findings say this is probably not enough: LSB demonstrated fixed balancing functions are systematically sub-optimal on landscapes with heterogeneous curvature, and PAS itself lists path length as an open problem with no adaptive mechanism, while chemical landscapes mix smooth regions and cliffs at unpredictable distances, so no single $L$ should work across PMO's 23 tasks. But this is exactly what the fixed-balancing and fixed-$L$ ablations measure, and if the simple port captures most of the gain, the honest conclusion is that the port is the contribution and the learning is refinement.

Proposed Experiments

The primary evaluation is the Practical Molecular Optimization benchmark at the 1,000-call budget, reporting per-task and summed Top-10 AUC against MolLIBRA-L's reported sum of 14.208 and Tripp's GP BO's 12.569, with Graph GA, REINVENT, and MARS run by us under matched budgets; a 10,000-call variant tests whether the sample-efficiency advantage persists when budget pressure relaxes. The file notes that InVirtuoGen, the discrete-flow method of Refine Drugs, Don't Complete Them, achieved the highest sum of Top-10 AUC across all 23 PMO tasks, but no numeric value for that sum is given, so we state only that no reported result found on Lacuna for InVirtuoGen's summed score and treat it as a method to run or obtain numbers for rather than cite. Secondary evaluation covers GuacaMol's goal-directed suite — where GuacaMol found Graph GA generally strongest and SMILES LSTM produced 77% acceptable compounds — and the four-objective GSK3β/JNK3/QED/SA task from MARS for the multi-objective, anti-collapse story, reporting the product-of-metrics score and scaffold-level diversity against MARS's 77%-over-RationaleRL reference point.

Three decisive checks close the loop. First, a cliff-crossing study: on tasks with engineered activity cliffs (pairs of similar molecules with sharply different oracle scores), measure the fraction of accepted moves that cross a cliff as a function of adaptive path length, against the single-edit sampler — this is the direct test of the core mechanism. Second, oracle-call accounting: report surrogate-versus-oracle evaluation counts to verify that delayed acceptance actually converts sampler effort into saved oracle calls, the quantity PMO prices. Third, a diagnosis of warm-up: compare sample quality and edit diversity in the first versus post-burn-in phases to confirm that Barker-initialization avoids the early-phase degradation documented for learned adaptive proposals, using effective-sample-size-style diagnostics adapted to graph states. If the cliff-crossing fraction does not improve with adaptive $L$, or the principled objective does not beat self-training under matched paths, the corresponding component is cut and the finding reported — the proposal is built so that each ingredient can fail independently and informatively.