Double-Ended Synthesis Planning with Goal-Constrained Bidirectional Search

Authors: kevin  yu
jihye  roh
ziang  li
georgia  tech
wenhao  gao
runzhong  wang
connor w coley
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 20:37:14

Abstract: Computer-aided synthesis planning (CASP) algorithms have demonstrated expert-level abilities in planning retrosynthetic routes to molecules of low to moderate complexity. However, current search methods assume the sufficiency of reaching arbitrary building blocks, failing to address the common real-world constraint where using specific molecules is desired. To this end, we present a formulation of synthesis planning with starting material constraints. Under this formulation, we propose Double-Ended Synthesis Planning ($\texttt{DESP}$), a novel CASP algorithm under a _bidirectional graph search_ scheme that interleaves expansions from the target and from the goal starting materials to ensure constraint satisfiability. The search algorithm is guided by a goal-conditioned cost network learned offline from a partially observed hypergraph of valid chemical reactions. We demonstrate the utility of $\texttt{DESP}$ in improving solve rates and reducing the number of search expansions by biasing synthesis planning towards expert goals on multiple new benchmarks. $\texttt{DESP}$ can make use of existing one-step retrosynthesis models, and we anticipate its performance to scale as these one-step model capabilities improve.

Main paper: 
 introduction: 
 Synthesis planning-proposing a series of chemical reactions starting from purchasable building blocks to synthesize one or more target molecules-is a fundamental task in chemistry. For decades, chemists have approached the challenge of synthesis planning with retrosynthetic analysis [1, 2] , the strategy by which a target molecule is recursively broken down into simple precursors with reversed reactions. In recent years, advances in machine learning have enabled a multitude of computer-aided synthesis planning (CASP) algorithms [3] [4] [5] [6] that navigate a combinatorially large space of reactions to propose chemically sensible routes to a variety of drug-like molecules within seconds to minutes. However, fully data-driven algorithms still underperform when generalizing to realistic use cases such as planning for more complex targets or in constrained solution spaces. In practice, expert chemists may plan syntheses with specific starting materials in mind, called "structure-goals" [1] , that constrain the solution space. For instance, efficient syntheses of highly complex drugs are often most practical when synthesized from naturally-occurring starting materials that share complex features with the target, a practice known as "semi-synthesis" [7, 8] . There is also immense interest in identifying pathways from waste or sustainable feedstocks to useful chemicals [9] [10] [11] , but existing methods have thus far relied on heuristics and brute-force enumeration of reactions.Though algorithms for planning synthetic routes from expert-specified starting materials have been proposed [12, 13] , the vast majority of CASP algorithms today cannot address starting material-Figure 1 : (a) Existing search methods are single-ended, and aim to identify a synthetic route where all leaf nodes meet certain termination criteria, e.g., buyability. (b) DESP is a bidirectional search algorithm that enables a double-ended starting material-constrained search, better reflecting certain real-world use cases in complex molecule synthesis planning. Empirically, double-ended search finds starting material-constrained solutions with fewer node expansions. constrained use cases, as they assume that solution states may comprise any combination of building blocks. It is non-trivial to extend from "general" retrosynthesis planning to the constrained setting; by requiring a solution to contain a specific goal molecule, starting material-constrained synthesis planning presents the challenge of simultaneously guiding a search towards this goal molecule and any other necessary buyable molecules.In this paper, we address these challenges by proposing a strategy for starting material-constrained synthesis planning with a bidirectional search algorithm and a goal-conditioned cost network learned offline from expert trajectories implicit to a validated reaction corpus. Given a target molecule and one or more specified starting materials, our Double-Ended Synthesis Planning (DESP) algorithm takes advantage of the natural reversibility of retrosynthesis by instantiating two AND-OR search graphs and alternately performing retrosynthetic expansions and forward synthetic expansions. We present two variations of DESP based on front-to-end (F2E) and front-to-front (F2F) bidirectional search. In F2E search, each direction of the search is conditioned on the root node of the opposing search graph, while in F2F, each search is conditioned on the "closest" nodes of the opposing search graph. In both cases, finding solutions is accelerated when the "bottom-up" search graph converges with the "top-down" retrosynthesis search graph. Each step of selection and expansion of bottom-up nodes is conditioned on a specific molecule in the retrosynthetic graph, and we devise a means of utilizing both our goal-conditioned cost network and an existing cost network for general retrosynthesis in the top-down search policy. The goal-conditioned cost network, which we term the "synthetic distance" network, is trained offline based on the observation that multi-step synthetic routes can be interpreted as expert plans where any of the non-root molecules represents a starting material goal for the final target molecule, thus bypassing the need for self-play using reinforcement learning (RL). In order to train the network on "negative experiences", we also sample pairs of molecules between which no path exists through known reactions. Our contributions can be summarized as follows:• We provide a formulation of starting material-constrained synthesis planning and release the first benchmarks for evaluating algorithms on this task, including new real-world benchmarks collected from the Pistachio database [14] addressing redundancies in the widely-used USPTO-190 test set. • We present a starting material-constrained neural bidirectional search algorithm to tackle doubleended synthesis planning. Specifically, we present a cost network that estimates the "synthetic distance" between molecules (instead of the distance between a molecule and arbitrary purchasable building blocks) and an A*-like bidirectional search algorithm that strictly reflects the constraints. • We present strong empirical results that illustrate the efficiency of double-ended synthesis planning.Compared to existing algorithms, DESP expands fewer nodes and solves more targets under goal constraints, demonstrating its value in biasing CASP algorithms towards expert goals.2 Background 
related work: 
 Computer-aided retrosynthetic analysis Retrosynthetic analysis has traditionally been formulated as a tree search problem, where each step involves searching for chemically feasible transformations and corresponding reagents to derive the product molecule. In defining the feasible transformation, template-based methods select graph transformation rules to apply based on expert rules [15] or use data-driven methods [16] [17] [18] , such as a neural network policy trained on a reaction corpus [19] . Template-free methods frame one-step retrosynthesis prediction as a translation task of SMILES strings [20, 21] or a graph-edit prediction [22] . In searching for multi-step synthetic pathways, the focus of late has been on selecting non-terminal nodes for expansion. Initial efforts relied on expert-defined rules and heuristics [2, 15] , whereas more recent efforts combine neural networks and Monte Carlo Tree Search (MCTS) [3] , as well as AND-OR graph searches that address the hypergraph complexity of reaction routes [23, 6, 4, 24] . Notably, Chen et al. [6] proposed Retro*, a neural-guided A*-like search algorithm that we build on as part of our approach. Much additional work has been done to improve multi-step CASP algorithms [25] [26] [27] [28] [29] [30] [31] [32] , primarily via improvements of single-step policies in a multi-step context or value functions for improved search guidance. Unlike DESP, these methods do not address the problem formulation where the pathway search is constrained by one or more starting materials, as shown Fig. 4 . One exception is GRASP [13] , which utilizes RL with hindsight experience replay [33] for goal-conditioned value estimation. Additionally, starting material-oriented planning capablities were implemented in the LHASA program [12] but rely entirely on expert-defined rules. In this work, we instead train a cost network offline using historical reaction data and use bidirectional search to augment the retrosynthesis planner.Synthesizable molecular design Recent advances in computer-aided molecular design have introduced novel approaches to synthesis planning. To ensure high synthetic accessibility of designed molecules, researchers have proposed assembling compounds in silico by applying valid chemical transformations to purchasable building blocks, effectively searching for molecules within a reaction network [34] [35] [36] [37] [38] [39] . The advent of deep generative modeling has further enabled the generation of synthetic pathways with neural models [40] [41] [42] [43] [44] . These methods commonly employ a bottom-up strategy, constructing synthetic pathways from building blocks to the final product. Gao et al. [42] proposed that this framework could enable "bottom-up synthesis planning," in which the goal of generation is to match a specified target molecule, and demonstrated the successful application of this approach despite a low empirical reconstruction rate. In this work, we build upon Gao et al. [42] 's method of conditional synthetic route generation by increasing the number of reaction templates, training on a larger reaction corpus, and integrating the models into a bidirectional search algorithm.Bidirectional search Bidirectional search is a general strategy that can accelerate search in problems that involve start and goal states by interleaving a traditional search from the start state and a reverse search from the goal state [45] , usually guided with either neural networks or expert heuristics. It has demonstrated utility in problems such as robotic path planning [46, 47] , program synthesis [48] , traffic management [49] , and puzzle solving [50] . However, the application of bidirectional search in synthesis planning has not been explored. When integrating an informed method of evaluating nodes, bidirectional search can be divided into front-to-end (F2E) and front-to-front (F2F) strategies [51, 52] . In F2E search, evaluations are made by estimating the minimal cost of a path between a frontier node and the opposite goal, while in F2F search, evaluations are made by estimating the minimal cost of a path between opposing frontier nodes. In this work, we implement both F2E and F2F variants of DESP to observe the empirical differences between the strategies in the synthesis planning setting.General synthesis planning In this work, we only consider template-based retrosynthesis methods, though any single-step model is compatible with our algorithm. Let M be the set of all valid molecules, R be the set of all valid reactions, and T be the set of all valid reaction templates. A reaction R i ∈ R is a tuple (r i , p i , t i ), comprising a set of reactants r i ⊂ M, a single product p i ∈ M, and a retro template t i ∈ T . A retro template t is a function t : M → 2 M that maps a product to precursors such that ∀i :r i ∈ t i (p i ). Likewise, a forward template t ′ ∈ T ′ is a function t ′ : 2 M → M where ∀i : p i ∈ t ′ (r i ).Given target molecule p * ∈ M and set of building blocks (BBs) B ⊂ M, synthesis planning finds a valid synthetic route-a set of reactions S = {R 1 , . . . R n } that satisfies the following constraints.Constraint 1 (Synthesize all non-BBs).∀ i : m ∈ r i , m / ∈ B =⇒ ∃ j s.t. m = p j ; Constraint 2 (Target is final molecule synthesized). ∃ i s.t. p i = p * , ∀ i : p * / ∈ r i ;Finally, we require that the graph formed by S is a directed acyclic graph (DAG), where for each i, the product p i is mapped to a node, which has a directed edge to a node mapping to reaction R i , which in turn has directed edges to nodes mapping to the reactants r i .Starting material-constrained synthesis planning Given a specific starting material (s.m.) r * ∈ M, in addition to Constraint 2, a valid synthetic route satisfies the following constraints. Fig. 1b illustrates an example of a valid starting material-constrained route found through bidirectional search. DESP can also be used for the more general form of the problem in which a set of potential starting materials {r * 1 , . . . r * n } is given on input, and at least one leaf node must map to r * i for some 1 ≤ i ≤ n. For simplicity, we only consider the single r * case unless otherwise specified.For a molecule m, given search graph G, the "reaction number" rn(m|G) represents the estimated minimum cost of synthesizing m.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The limitations are explicitly outlined and discussed in Section A.8. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
methods: 
 DESP is built on the Retro* algorithm [6] and recent advances that enable conditional generation of synthetic routes from the bottom up [41, 42] .Like Retro* [6] , DESP is an A*-like search and thus requires a method of evaluating the expected cost of various frontier nodes. We follow Retro* and use the notation of V t (m|T ), V m , and rn functions (Section A.2 details Retro* and these functions). We also define a function c : R → R which maps a reaction to a scalar cost. For a valid synthetic route S = {R 1 , . . . , R n }, the total cost of S is n i=1 c(R i ). V m represents the minimum total cost across every valid synthetic route to molecule m, and is learned in Retro* and DESP to bias the search towards B.However, to maintain consistency in guiding A* search in the starting material-constrained setting, we require not only an estimate of the cost of synthesizing molecule m from arbitrary building blocks, but also an estimate of the cost of synthesizing molecule m 2 from m 1 specifically (in addition to other arbitrary building blocks). As such, we define a new function D : M × M → R, which we term synthetic distance, as it effectively represents the minimum cost distance between two molecules in G, the graph constructed from the set of all possible reaction tuples R. More precisely, the synthetic distance from m 1 to m 2 is the difference between the minimum cost of synthesizing m 2 across all valid synthetic routes containing m 1 and the minimum cost of synthesizing m 1 across all valid synthetic routes in general. Learning D then allows for the guidance of both top-down search towards the starting material and bottom-up search towards the target with rapid node comparisons.In practice, synthesis planning problems are generally approached by simulating a search through the complete reaction graph G. We follow Xie et al. [30] in considering an AND-OR graph structure for search graphs, in which molecules are represented by OR nodes (only one child must be solved) and reactions are represented by AND nodes (all children must be solved). In implementing most synthesis planning algorithms [3, 6] , one initializes the search graph G = {p * }. With DESP, we instead initialize two search graphs G R = {p * }, G F = {r * } and introduce two expansion policies, one for "top-down" retrosynthesis expansions on G R and another for "bottom-up" forward expansions on G F . This allows us to perform a bidirectional graph search between the target and goal molecules by interleaving retro and forward expansions, with the goal of the two search graphs converging to more efficiently find a valid synthetic route. In this work, we implement F2E and F2F variants of DESP. Notably, our implementation of F2F performs node comparisons to all nodes in the opposing search graph rather than just frontiers. For m ∈ G R , we define a goal function γ :M → M such that γ(m) = r * in F2E and γ(m) = arg min g ′ ∈G F D(g ′ , m) in F2F. Likewise, for m ∈ G F , let γ(m) = p * in F2E and γ(m) = arg min g ′ ∈G R D(m, g ′ ) in F2F.The following quantities or functions are relevant in the algorithm: rn, V t (m|G), and V m from Retro*, and somewhat analogously dn, D t (m|G R ), and D m . We briefly define the new quantities:(1) D m represents D(γ(m), m). (2) dn(m|G R ) represents the "distance numbers" of a top node m. This is a multiset of values D m -V m for related frontier nodes collected for dynamic programming from the bottom-up during the update phase. (3) D t (m|G R ) is a multiset of all values of D m -V m across frontier nodes in the minimum cost synthetic route to the target p * through molecule m. At a high level, we introduce these quantities and new policies to account for the fact that only one subgoal in a valid synthetic route needs to reach r * . The top-down searcher of DESP is thus an extension of Retro* that simultaneously utilizes general retrosynthesis and synthetic distance cost networks.Like most CASP algorithms, DESP cycles between steps of selection, expansion, and update until the termination criteria are satisfied. However, DESP also alternates between performing these steps for the top-down and bottom-up search graphs (Fig. 2 ), with each search having its own policies.Selection For top-down selection, we select an frontier molecule node that minimizes the expected total cost of synthesizing the target p * from the goal molecule r * through that node. Let F R represent the set of frontier top molecules and F F represent the set of frontier bottom molecules. Then,EQUATIONThe bottom-up selection policy is identical to that of Retro*.EQUATIONExpansion For top-down expansion, we follow other AND-OR-based algorithms in calling a single-step retrosynthesis model, applying the top n predicted templates to the selected node and adding the resulting reactions and their precursors as nodes to the graph. For each added molecule node m i , we initialize: (1) rn(m i |G R ) ← V mi , equal to the Retro* value function, and(2) dn(m i |G R ) ← {D mi -V mi } = {D(γ(m i ), m i ) -V m }.For bottom node m, we perform the forward expansion procedure detailed in Section 3.3, conditioned on γ(m). For each added product p i , we then initialize rn(p i |G F ) ← V pi = D(p i , γ(p i ))Update For G R , we propagate updates to relevant values up the graph and then back down to related nodes, similar to other AND-OR algorithms. As the update rules for the Retro* quantities are the same, we only provide the update rules for the new quantities, and details of the Retro* updates is in Section A.2. G F is also updated according to the Retro* algorithm (as branching from multiple product OR nodes is not allowed in forward expansions), so the following new updates only apply to G R . We first uppropagate, performing updates up the graph for reaction (AND) nodes R and molecule (OR) nodes m, where the ch and pr functions return the children and parent nodes for an input node:EQUATIONEQUATIONWe then downpropagate the following updates:EQUATIONJustification for the rules and additional details, including DESP pseudocode, is in Section A.5.To perform forward one-step synthesis expansions, we adapt the approach of Gao et al. [42] . Let z n m : M → R n and z n t : T → R n be functions mapping a molecule and template (respectively) to n-dimensional embeddings. We define two target functions:EQUATIONTogether, the learned approximations of f t and f b define our forward expansion policy (Algorithm 1), which generates forward reactions for the expanded node m 1 conditioned on m 2 . Algorithm 1: FORWARD_EXPAND(m 1 , m 2 , G F , N , K) m 1 : molecule selected for expansion, m 2 : molecule to condition expansion on, G F : bottom search graph, N : num. templates to propose, K: num. building blocks to searcht ′ ← TOP_N(σ(MLP t (z m (m 1 ) ⊕ z m (m 2 )))) ; /* Get top N forward templates */ for i ← 1 to N do if t ′ [i] is unimolecular then p ← t ′ [i](m 1 ) ; /* Apply fwd. template to m */ G F .ADD_RXN({m 1 }, p, t ′ [i]) ; /* Add reaction and product to G F */ else /* t ′ [i] is bimolecular */ b ← KNN B (MLP b (z m (m 1 ) ⊕ z m (m 2 ) ⊕ z t (t ′ [i]))) ; /* Get K nearest BBs by cosine sim. */ ∀j ← 1 to K: G F .ADD_RXN({m 1 , b}, t ′ [i](m 1 , b[j]), t ′ [i]) ; /* Apply t ′ [i] */ end endTo learn f t , f b , and D, we approximate G by generating the incomplete network from a reaction dataset. In this work, we use the public USPTO-Full dataset [53, 54] of approximately 1 million deduplicated reactions. The dataset is filtered and processed (details in Section A.3), and a template set T USPTO is extracted with RDChiral [55] . The dataset is randomly divided into training and validation splits with ratio 90:10. From the training split R USPTO we construct the graph G USPTO . We filter reactions that (1) involve more than 2 reactants or (2) whose product cannot be recovered by applying the forward template t ′ , yielding R FWD , G FWD , and T ′ FWD . L = (y pred -y true ) 2 if y true ≤ D max max(0, D max + 1 -y pred ) 2 else (9)This strategy allows the model to default to an approximate value of D max + 1 for any "highly distant" molecule inputs. Now, for each target p * , we randomly sample a molecule m ∈ G USPTO with no path to p * and Tanimoto similarity < 0.7 and add a training example with label ∞. In this work, we use D max = 9.For a molecule m, given search graph G with goal p * , V t (m|G) represents the estimated minimum cost of synthesizing p * using m.Retro* also cycles between selection, expansion, and update phases. We implement Retro* as follows.Selection The molecule in the set of frontier nodes F that minimizes the expected cost of synthesizing p * given the current search graph G is selected:EQUATIONExpansion As in Alg. 2, a one-step retrosynthesis model is called on the selected node and the resulting reactions and precursors are added to G. Each molecule node is then initialized with rn(m|G) ← V m .Update First, reaction number values are uppropagated to ancestor nodes. For reaction node R, the reaction number is updated as the sum of its childrens' reaction numbers.EQUATIONFor molecule node m, the reaction number becomes the minimum reaction number among its children. rn(m|G) ← minEQUATIONNext, V t (m|p * ) values are downpropagated to descendent nodes. Starting from p * itself,EQUATIONFor subsequent reaction nodes R, the value is updatedEQUATIONFinally, for molecule node m that is not p * ,EQUATION 
experiments: 
 Our experiments are designed to answer the following: (1) Does DESP significantly improve the performance of starting material-constrained synthesis planning compared to baseline methods?(2) To what extent do D and bidirectional search account for the performance of DESP? (3) Can DESP find routes to more complex targets than baseline methods? (4) What empirical differences do we see between F2E and F2F strategies?Datasets Few public datasets of multi-step synthetic routes exist. Previous works in multi-step synthesis planning have widely used the USPTO-190 dataset [6] , a set of 190 targets with corresponding routes extracted from the USPTO-Full dataset. Others have tested on targets sampled from databases such as ChEMBL or GDB17 [57, 27, 31] , but their lack of ground truth routes precludes the systematic selection of starting materials for our task. PaRoutes [58] has been proposed as an evaluation set, but they do not provide a standardized training set to prevent data leakage.In addition to USPTO-190, because of its large proportion of out-of-distribution and redundant reactions (Table 1 ), we create and release two additional benchmark sets, which we call Pistachio Reachable and Pistachio Hard. Details of their construction are provided in Section A.6. To obtain the ground-truth goal molecules for each of our test sets, we find the longest path from target to leaf node in each route DAG and pick the leaf node with more heavy atoms. For the building block set B, we canonicalize all SMILES strings in the set of 23 million purchasable building blocks from eMolecules used by Chen et al. [6] .Model training As in [6] , we train a single-step retrosynthesis MLP (NeuralSym) and Retro* cost network on our processed training split of USPTO-Full. The synthetic distance and forward expansion models are trained as described in Sections 3.4 and A.4.Because we utilize an AND-OR search graph with no duplicate molecule nodes, our implementation of Retro* is more comparable to RetroGraph [30] , but we do not employ [13] using the authors' published code. Since their data is not publicly available, we retrained their model on 10,000 randomly sampled targets in our training set and run their search implementation on each benchmark. For all methods, we enforce a maximum molecule depth of 11, a maximum of 500 total expansions (retro or forward), and apply 50 retro templates per expansion. For DESP, we also enforce a maximum molecule depth of 6 for the bottom-up search, apply 25 forward templates per expansion, and use the top 2 building blocks found in the k-NN search. Due to the asymmetry of the bidirectional search, we also introduce a hyperparameter λ, the number of times we repeat a select, expand, and update cycle for G R before performing one cycle for G F . For all experiments, we set λ = 2. Details and tabular summaries of the evaluations performed and hyperparameters chosen are provided in Section A.7. Though it is notoriously difficult to quantitatively evaluate synthetic routes proposed in silico without expert evaluation, there are widelyused metrics thought to correlate with successful algorithms, such as higher solve rate (under varying computational budgets), lower average number of expansions, and lower average number of reactions in found routes [59, 57] . We focus on these metrics, as they are arguably most related to a search algorithm's efficiency. Because all methods employ the same one-step model and set of templates from USPTO-Full, we treat their proposals as equally chemically feasible.Improvement on starting material-constrained synthesis planning Quantitative benchmarking results are summarized in Table 2 . Both variants of DESP outperform all baseline methods in terms of solve rate and average number of expansions across all test sets. The solve rates of baseline methods on USPTO-190 are noticeably lower than commonly reported ranges for general synthesis planning [6] , as the starting material constraint increases the difficulty of the task. Notably, unlike the other benchmarked methods, the Random, BFS, MCTS, and Retro* are standard single-ended search methods that do not make any use of the starting material constraint information.Ablation studies To investigate the contributions of D and bidirectional search, we conduct an ablation study by running Retro* guided by D on all benchmarks (denoted as Retro*+D in Tables 2 and 3 ). We find that incorporating D generally results in higher solve rates and fewer average expansions across all datasets, but still does not outperform DESP, demonstrating the role of both D and bidirectional search in improving planning efficiency. As an indicator of route quality, we also investigate the average number of reactions in the outputs of DESP (Table 3 ). DESP-F2E is able to find shorter routes on average when compared to either Retro* or Retro* guided by D. An example of a route solved by DESP-F2F (but not by Retro*) is visualized in Fig. 4 .Performance on complex targets To investigate the degree to which DESP improves planning performance on complex targets, we bin each target in Pistachio Hard by two commonly-used metrics of synthetic complexity, SCScore [60] and SAScore [61] . Both variants of DESP equal or outperform Retro* on solve rates across all complexity ranges (Fig. 3a ). This indicates that, in the starting material-constrained setting, DESP can improve planning performance on targets of higher complexity, a regime which current CASP algorithms struggle with.F2E and F2F comparisons Though DESP-F2F consistently expands slightly fewer nodes on average, the empirical differences in efficiency between F2E and F2F are small. However, DESP-F2E is able to find noticeably shorter routes on average than DESP-F2F, which finds routes even longer than Retro* on multiple benchmarks (Table 3 ). A likely reason for this difference is due to the lack of consideration of the pathway depth of existing nodes in front-to-front search, which we elaborate on in Section A.8. We also investigate the extent to which reactions from forward expansions end up in the solutions of each variant. As visualized in Fig. 3b , DESP-F2F incorporates more forward reactions, while DESP-F2E solutions are dominated by top-down search almost half the time. We hypothesize that the difficulty of bottom-up synthesis planning [42] further contributes to the increased length of DESP-F2F solutions, as DESP-F2F empirically relies more on forward reactions and thus is likely more sensitive to the performance of the forward models. 
conclusion: 
 In this work, we introduce DESP, a novel framework for bidirectional search as applied to computeraided synthesis planning. DESP biases searches towards user-specified starting materials with a combination of a learned synthetic distance network and bottom-up generation of part of the synthetic route. This represents a task that aligns with a common use case in complex molecule synthesis planning. We demonstrate the efficiency of DESP on the USPTO-190 dataset and two new test sets derived from the Pistachio database. When compared to existing methods, both variants of DESP reduce the number of expansions required to find solutions that satisfy the specified goal, while DESP-F2E also finds more routes with fewer reactions per route. We anticipate that with future improvements to the synthetic distance network and bottom-up synthesis planning, bidirectional synthesis planning can emerge as an effective and efficient solution to navigating constraints and aligning computer-aided synthesis planning with the goals of domain experts. Additional outlook is provided in Section A.8. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: This work does not involve human subjects or privacy concerns. We do not anticipate any particular negative impacts from this work.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: This work directly addresses challenges in chemistry that can advance health and sustainability as briefly described in Section 1.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We do not anticipate any significant risks associated with releasing data and models in this work.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: We cite all originators of data or code that was used.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: A. 1. V m . For a molecule m, V m is an unconditional estimate of the minimum cost required to synthesize m. It is estimated by a neural network.Reactions in the USPTO-Full dataset are represented with simplified molecular-input line-entry system (SMILES) [62] strings, where the SMILES string of reactants, reagents, and products are separated by '>' as REACTANTS>REAGENTS>PRODUCTS. Each field can have one or more chemical species delineated with a dot (.) or be left blank in the case of reagents.For processing reaction SMILES, multi-product reaction SMILES are first separated into singleproduct reaction SMILES by creating separate entries for each product species with the same reactants and reagents. Each single-product reaction SMILES then undergoes the following process:1. Reagents in the SMILES string are moved to the reactant side.2. Chemical species with identical atom mapped SMILES in both reactants and products are moved to reagents. 3. Any products that do not contain at least one mapped atom or have fewer than 5 heavy atoms are removed. 4. Any atom mapping numbers that exist exclusively on either the reactant side or product side are removed. 5. Any reactants without atom mapping are moved to the reagent side.Resulting reaction SMILES without either reactants or products are then filtered out.Dataset construction To learn f t and f b , a full enumeration of all pathways (until reaching nodes in B) rooted at p * is performed for each molecule node p * in G FWD . For learning f t , each reaction node R i = (r i , p i , t i ) is then used as a training example for each reactant m j ∈ r i with input z n1 m (m j ) ⊕ z n1 m (p * ) and one-hot encoded label t i . Likewise, for learning f b , each reaction node R i = ({m 1 , m 2 }, p i , t i ) that is bimolecular and involves at least one building block yields a training example with inputz n1 m (m 1 ) ⊕ z n1 m (p * ) ⊕ z n1 t (t i ) and output z n2 m (m 2 ) if m 2 ∈ B and with input z n1 m (m 2 )⊕z n1 m (p * )⊕z n1 t (t i ) and output z n2 m (m 1 ) if m 1 ∈ B.The procedure for such training example generation is illustrated in Fig. 5 . With n 1 = 2048, n 2 = 256, we use the RDKit implementation of the Morgan Fingerprint [63] with radius 2 for z m and the Atom Pair fingerprint [64] for z t .Because D is used to bias both the top-down and bottom-up searches, we perform the same pathway enumeration for all molecule nodes p * / ∈ B, p * ∈ G USPTO . In this case, however, we only consider p * for which we find valid synthetic routes. Training examples are then extracted for all other molecule nodes m i in a solved search graph, with input z n m (m i )⊕z n m (p * ) and label V p * (m i |G R )-rn(m i |G R ), with n = 512. For calculating this label, we propagate the Retro* functions as described in Section A.2 such that D can be calculated as the minimum cost of synthesizing p * subtracted by the minimum cost of synthesizing m i . Here, we set c(R i ) = 1 for all R i , as a synthetic route's number of steps is an important metric in evaluating the route cost, and it is otherwise difficult to objectively quantify the cost of a reaction. This training example generation is also depicted in Fig. 5 . Finally, to obtain additional training examples, we also recover pairs of (m, p * ) where p * was not "solved" by the enumerative search but would have been solved if m ∈ B.For validation of the f t and f b models, we construct the graph G val corresponding to all reactions across both the training and validation splits. We perform the same pathway enumeration described above, and each "training example" that corresponds to a reaction not in the original training split is used as a validation example. Hyperparameters were selected based on best performance on the validation split while performing a Bayesian search through the following parameter space: In the unguided Retro* algorithm, the left-most frontier node would be chosen for expansion, as a route through that node minimizes V t (m|G), the expected cost to the target from building blocks (5 reaction steps). In DESP, either of the other two nodes would be prioritized, as the middle frontier node is predicted to be only 1 reaction step away from the starting material, resulting in only V t (m|G) + min D t (m|G) = 4 predicted reaction steps total in the final solution. G F */ end l ← l + 1; end m ← arg min m∈F F V t (m|G F ) ; /* Select best bot */ if s = F 2E then FORWARD_EXPAND(m, p * , G F , N 2 , K); /* Expand conditioned on p * */ BOT_UPDATE(G F , s); /* Retro* updates G F */ else if s = F 2F then q ← arg min q∈G R D(m, q); /* Find closest node */ FORWARD_EXPAND(m, q, G F , N 2 , K); /* Expand conditioned on q */ BOT_UPDATE(G F , s); /* Retro* updates on G F */ if met top then m met .rn ← 0, m met .dn ← [0]; /* Set expected costs of met node to 0 */ TOP_UPDATE(G F ); /* Section 3 updates on G R */ end l ← l + 1; end Design of new quantities and update rules We recall that the minimum total cost of synthesizing the target p * from a molecule m under the Retro* framework is estimated as:EQUATIONwhere A(m|G R ) represents the set of reaction node ancestors of m and V m (G R ) represents the set of molecule nodes in the search graph. This is equivalent toEQUATIONwhere g(m|G R ) aggregates the current cost from all reaction nodes in G R contributing to V t (m|G R ), and N (m|G R ) ⊆ F R accordingly represents the set of frontier top nodes for the subgraph of G R corresponding to nodes contributing to V t (m|G R ). If we add the constraint that one frontier node must implicitly be the ancestor of r * , the estimate of the minimal cost then becomes:EQUATIONEQUATIONOur update rules are implemented such that D t (m|G R ) = min mj ∈N (m|G R ) D mj , thus justifying our design of the selection and update procedures. Note that this design relies on the assumption that N (m|G R ) remains static upon adding the goal node constraint, when in reality the introduction of D may change the optimal set of frontier nodes to consider in the search graph. To avoid the combinatorial complexity of this situation and retain the efficiency from dynamic programming for our update policy, we maintain this assumption and find that introducing D in this way empirically works well (Section 4.2). A simple visual example of the update procedures is provided in Figure 7 .We follow the test set extraction procedure of Chen et al. [6] , applied within patents of the Pistachio dataset [14] (version: 2023Q4) to obtain 1,004,092 valid synthetic routes. We randomly sample synthetic routes from this set until we obtained 150 routes that satisfied the following constraints:(1) No reactions in the route are found in the training data. (2) No reactions are shared between any routes within the test set. (3) All reactions are found in the top 50 proposals of our single-step retrosynthesis model. ( 4) No two targets in the test set have a Tanimoto similarity of more than 0.7.(5) We enforce a minimum number of routes for different route lengths (Fig. 8 , Fig. 9 ). We term this set of 150 routes Pistachio Reachable. We perform the same procedure but modify condition (2) to require only 50% or more of the reactions to be reproducible (in-distribution) and obtain 100 routes which we term Pistachio Hard. Due to a bug in our implementation of criterion (2), a small number of routes share the same reaction in the final datasets, but the degree of inter-route reaction duplication is still significantly less than that of USPTO-190 for both benchmark sets (Table 1 ).Figure 8 : Distribution of reaction counts in Pistachio Reachable.Implementation details For random search, all node selections were performed at random among frontier molecule nodes. For BFS, the molecule with the lowest depth was selected at each step, with precedence for nodes whose parent reactions had the highest plausibility scores from the retro one-step model. MCTS was run by integrating our one-step model into the open-source ASKCOS code base [65] . For Retro*, we removed the synthetic distance network and bottom-up expansions from our DESP implementation. Notably, reaction costs for Retro* and DESP are both calculated as -log p, where p is the template plausibility from the one-step model (retro or forward). For GRASP, we used the authors' search implementation [13] . For a fair comparison with the AND-OR graph structure, we did not increment the iteration counter when a molecule that had previously been expanded was expanded again. In training the GRASP value network, we use the authors' reported hyperparameters where applicable and the default values in their code base otherwise. method took around 10 hours. DESP requires ∼ 3 GB of GPU memory to store the building block database for fast k-NN.Convergent syntheses Convergent synthetic routes, in which multiple non-BBs are combined, are often desirable in chemistry due to their relative efficiency. The top-down search has no problems proposing convergent routes. However, the bottom-up searcher in DESP only performs forward expansions and thus cannot handle convergent routes by adding and merging new synthetic trees.Resultantly, the bottom-up search can only plan one branch if the final route requires convergent steps. Implementing additional modules of SynNet [42] into the bottom-up search would enable planning of convergent synthetic routes and potentially further reduce the average number of reactions in solutions and improve solve rates.GPU reliance and computational overhead DESP requires GPU acceleration to tractably perform a k-NN search over ∼ 23 million building blocks in the forward expansion policy. DESP-F2F also requires GPU inference to rapidly perform node comparisons at each iteration. In all, forward expansions take around 50% more time than retro expansions, though this is in because our implementation of forward synthesis applies retro templates to each product proposed by the forward model to ensure template reversibility (i.e., to confirm that the increased success in finding routes during the bidirectional search is not an artifact of having access to "different" transformations), which creates additional overhead. Overall, we view these limitations primarily as engineering problems that do not take away from the empirical benefits demonstrated in the paper. In principle, one could also implement DESP-F2E as a parallel bidirectional search in pursuit of additional efficiency gains.Building block specification Though DESP is designed to address starting material-constrained synthesis planning, we envision that future work could optimize bidirectional search to improve general retrosynthesis capabilities by conditioning on one or more starting materials instead of constraining the solution space. These starting materials could be expert-designed or predicted algorithmically as in Gao et al. [42] .DESP-F2F implementation In general, neither DESP-F2E or DESP-F2F guarantee that the costoptimal route is found upon termination. Additionally, our implementation of DESP-F2F does not take into account the total known cost of the opposing graph's nodes V t (m ′ |G F ) -rn(m ′ |G F ) when calculating dn(m|G R ), and likewise the value of rn(m|G F ) does not take into accountV t (m ′ |G R ) -rn(m ′ |G R ).As a result, the selection policy DESP-F2F selects nodes that minimize the lowest expected cost of reaching the opposing search graph, but does not select to minimize the lowest expected cost of the final route directly. This is likely a primary contributor to DESP-F2F finding longer routes on average than DESP-F2E. As the values of V t (m|G) change after each expansion, it would be computationally expensive to re-compare nodes across the search graphs at each iteration. We have not devised an efficient means of handling the number of re-comparisons that would be required and leave such optimizations to future exploration.Sub-goal and divide-and-conquer strategies Goal-oriented synthesis planning bring to mind potential methods that involve sub-goals or divide-and-conquer strategies that have been utilized in general purpose planning [66] or program synthesis [67] . In general, there are rich bodies of literature in fields like hierarchical planning and program synthesis that remain largely untapped in applications to computer-aided synthesis planning.1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The contributions are explicitly enumerated in Section 1 and are each backed by our methods (Section 3) and experimental results (Section 4). Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Template relevance module can be found at https://gitlab.com/mlpds_mit/askcosv2/retro/ template_relevance. 


Decision: The authors propose a new algorithm for double-ended chemical synthesis planning,
where the goal is to find a reaction route from purchasable materials to a target molecule.
The paper is well-written and presents significant results for an important problem
with applications in drug synthesis.

Reviews: review: paper_summary: paper_summary: the authors propose a new algorithm for double ended synthesis planning. while this problem has received attention from the community a few decades ago, this has recently not been studied at all.
strength_weakness: strength_weakness: - none really
questions: questions: - results from the PAroutes paper and recent work by Tripp et al and Maziarz et al indicate that there are signficantly less or even no differences between the different uni-directional search algorithms than prior work (Chen et al; Retro*) imply. My suggestion would be more clearly flag which baseline implementation of the various algorithms used in the maintext, and also give the used hyperparams for all search algorithms.
limitations: limitations: n/a
paper_summary: paper_summary: This paper proposes a bidirectional search algorithm for chemical synthesis, in the case where we also have certain "part of the way there" molecules that we would like to include in the discovered synthesis route.
strength_weakness: strength_weakness: By adding bidirectional search, the algorithm gets a bit complicated. Due to my lack of familiarity with the area, I'm not 100% sure how to weigh the complexity vs performance tradeoff, but I am inclined to ignore it given how clearly the algorithm is described and how easy the high level motivation for it is.
questions: questions: - Is the BFS top-down only or bottom-up only? Would it be useful to include a "bidirectional BFS" baseline? 

Suggestions/typos:
- I would suggest including a high level explanation of how Retro* compares with DESP in the main text . it sounds like Retro* is top-down only, and DESP = Retro* + synthetic distance + bottom up expansions?

- it might be good to include more details about the compared baselines during the paper. In particular, what is Retro*+$D$? the appendix only describes Retro*. This is almost certainly clear to someone who reads through all the details of the approaches and understands them (Retro* + D just adds the synthetic distance D to Retro*, somehow based on how Retro* and the current work works, and the appendix probably meant ...)  but to clarify, the appendix describes Retro* as DESP without bottom-up expansions. So, at a high level, is Retro* just top-down only, and  DESP is bidirectional, plus the synthetic distance? 
- line 106 typo, two front-to-end's 

You should check out this reference: https://dl.acm.org/doi/pdf/10.1145/3571226. They use "cuts", which I believe are similar in that using certain "cuts" lets you stake out some target in the "middle" of the search and then split the synthesis problem into two problems, one of reaching the midpoint, and then going from the midpoint to the target. (I haven't read this paper in a while, and sort of forget it, so I might be wrong)
- Maybe this is relevant to addressing the convergent synthesis limitation? not sure.
limitations: limitations: The limitations section looks great!
paper_summary: paper_summary: The paper considers computer aided synthesis planning with applications to retrosynthetic analysis in chemistry where the goal is to find a reaction route from purchasable materials to a target molecule. The latter is an important problem with real applications in areas such as drug discovery. In the current landscape of algorithms for retrosynthetic analysis the common practice is to assume reachability to arbitrary materials thus failing to address an important constraint where using specific molecules is most desired. Therefore, the paper proposes a bi-directional graph search algorithm that is restricted to using a user specified set of purchasable basic materials. The algorithm called DESP is guided by a heuristic function derived from a goal-conditioned cost network (neural network) learned offline from a set of valid chemical reactions. The empirical evaluation is carried out on standard benchmarks for retrosynthetic analysis. The results show clearly that the new bi-directional search algorithm improves considerably over existing state-of-the-art algorithms for this domain.
strength_weakness: strength_weakness: I was not able to find any major weakness in this paper. Perhaps including a small numerical example to show more clearly how the node values are computed and updated during search would help improve the quality of the presentation.
questions: questions: - What is dn() and rn() refering to in Equations 3-6? Are these values related to the proof and disproof numbers from the A* algorithm proposed by [Kishimoto et al, 2019]?
limitations: limitations: The limitations of the proposed method are discussed fairly clearly in the paper.
paper_summary: paper_summary: The paper addresses the synthesis planning problem where constrains are taken into account. To that end, the authors propose a double-ended synthesis planning grounded with bidirectional search to ensure that the added constrains are met. They show experimentally that their proposed approach helps with solve rate as well as reduction in number of node expansion.
strength_weakness: strength_weakness: - See the questions section.
- Proof of soundness and completeness of algorithm 1 is missing. In particular, what can be said about the properties of this algorithm? 
- This paper provides a novel contribution for synthesis planning, but I fail to see its broader impact to the community (its significance is of narrow scope).
questions: questions: 1. Why Bi-directional search? Have you tried other search algorithms? You can potentially still define goal constrains and be in the forward search algorithm and ensure those goals are met. Forward search algorithms with heuristic search can address soft and hard constraints on goals or even on the full trajectory. Some examples follow. While these examples are from Automated planning literature, perhaps some can be relevant in this context. Note the specification of constraints in Linear Temporal Logic, as well as heuristics to meet these constraints has been a topic of interest in several publications.  
    1. https://www.cs.toronto.edu/~sheila/publications/bai-mci-aim08.pdf
    2. https://www.sciencedirect.com/science/article/pii/S0004370208001975
    3. https://cdn.aaai.org/ICAPS/2005/ICAPS05-019.pdf

2. Could there be multiple solutions to the general synthesis planning problem defined in Section 2.2. If so is the notion of cost you mentioned taken into account? Also is the algorithm in section 3.2 going to favor the least costly solution? If so do you have a proof of that?

3. Is starting material-constraints the same as the goal constraints? 

4. Can you point to where in the paper you discuss how you learned the goal-conditioned cost network offline (mentioned in the abstract).
limitations: limitations: Authors discuss limitations and those are not concerning (re societal impact, etc).

Comments: title: Proof of soundness and correctness
Reply to rebuttal
comment: Thanks for the clarifications.
Thank you for your response. We provide a proof of soundness and completeness below.

---

Assume that we have access to all unimolecular and bimolecular reactions that involve at most one non-buyable (forming $G_{\text{FWD}}$), giving us access to target functions $f_t$ and $f_b$ (as described in our response). We prove that **Algorithm 1** is sound and complete for $N = 1$ and $K = 1$.

Consider the set of routes $S$ for which $m_1$ is a leaf node and $m_2$ is a root and no such route in  $G_{\text{FWD}}$ has lower total cost. On input $m_1, m_2$, the algorithm is sound if the algorithm only adds a reaction $R$ involving $m_1$ if $R$ is in some route in $S$. We call such $R$ an _optimal reaction_. Additionally, the algorithm is complete if it adds an optimal reaction for any input. Since we know $f_t$ and $f_b$, our algorithm computes $f_t(m_1, m_2)$ (and $f_b(m_1, m_2, f_t(m_1, m_2))$ if necessary) which comprises an optimal reaction by the definition of the functions. Thus, the algorithm is sound and complete.

---

In practice, we do not have $f_t$ and $f_b$ and instead approximate them with neural networks, meaning that the algorithm is not sound or complete. This applies to **any** expansion policy of an existing CASP tool and justifies the use of search with higher branching ratios ($N$ and $K$), as the expansion policy will only sometimes give the “optimal reaction” as its top-1 output. Thus, we believe that the provided proof is somewhat tautological and does not significantly enhance our contributions. In any case, we will provide more detail about **Algorithm 1** into our final version, incorporating our initial response and the discussed properties of CASP expansions.
Thank you! Again: great paper!
Thank you for answering my questions. I think more details on Algorithm 1 is definitely needed even the full proof of soundness and correctness.
Thank you for your response to each of my questions and comments! I have no further questions and will maintain my score of 8.