Double-Ended Synthesis Planning with Goal-Constrained Bidirectional Search
Authors: Kevin Yu
Jihye Roh
Ziang Li
Wenhao Gao
Runzhong Wang
Connor W. Coley
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Retrosynthesis
synthesis planning
chemistry
bidirectional search
Primary area: machine_learning_for_other_sciences_and_fields
TL;DR: We propose a neural-guided bidirectional search algorithm for a new starting material-constrained formulation of synthesis planning

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.

Double-Ended Synthesis Planning with
Goal-Constrained Bidirectional Search
Kevin Yu MIT kyu3@mit edu
Jihye Roh MIT
Ziang Li Georgia Tech ziang0gatech. edu
Wenhao Gao MIT whgao@mit.
jroh99@mit.ee edu
Runzhong Wang
Connor W. Coley MIT
MIT runzhong@mit.edt
ccoleySmit.edd edu
Abstract
Computer-aided synthesis planning (CASP) algorithms have demonstrated expert- level abilities in planning retrosynthetic routes molecules of low to moderate complexity. However, current search methods assume the sufficiency 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 (DESP), a novel CASP algorithm under 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 valid chemical reactions. We demonstrate the utility of DESP improving solve rates and reducing the number of search expansions by biasing synthesis planning towards expert goals on multiple new benchmarks. DESP can make of existing one-step retrosynthesis models, and we anticipate its performance to scale as these one-step model capabilities improve.
Introduction
Synthesis planning prrppssnn series of chemical reactions starting from purchasable building blocks to synthesize one or more target molecules a fundamental task chemistry. For decades, chemists have approached the challenge of synthesis planning with retrosynthetic analysis 212, 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 multitude of computer-aided synthesis planning (CASP) algorithms (3/6] that navigate a combinatorially large space of reactions propose chemically sensible routes 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 in constrained solution spaces. In practice, expert chemists may plan syntheses with specific starting materials in mind, called "structure- "isturre-goas"" [I]. that constrain the solution space. For instance, efficient syntheses of highly complex drugs are often most practical when synthesized from target, practice known as "eemi-synthesis" g There is also immense interest in identifying 19 but existing methods have thus far relied on heuristics and brute-force enumeration of reactions.
starting materials that share complex features with the
pathways from waste sustainable feedstocks useful chemicals
Though algorithms for planning synthetic routes from expert-specified starting materials have been proposed 12 the vast majority of CASP algorithms today cannot address starting material-
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

a. Prior Work: Single-ended search
b. This Work Double-ended search
Non buyable
Ruilding block
Reaction
solution
Explored paths
arbttrory building blocks
expert specifred
starting motarioi
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 caterial-constrained search, better reflecting certain real-world use cases in complex molecule synthesis planning. Empirically, double-ended search finds solutions with fewer node expansions.
starting
constrained use cases, as they assume that solution states may comprise any combination of building blocks. It non-trivial to extend from "general" retrosynthesis planning to the constrained setting; by requiring a solution to contain specific goal molecule, starting material celtriil-oonstrained synthesis planning presents the challenge of simultaneously guiding 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 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 conditioned on specific molecule in the retrosynthetic graph, and we devise means of utilizing both our goal-conditioned cost network and an existing cost network for general retrosynthesis 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 expert plans where any of the non-root molecules represents 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 formulation of starting material-constie constraied 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 double- ended synthesis planning. Specifically, we present cost network that estimates the "synthetic distance" between molecules (instead of the distance between molecule and arbitrary purchasable building blocks) and an A Aile bidirectional search algorithm that strietly 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
2.1 Related work
Computer-aided retrosynthetic analysis Retrosynthetic analysis has traditionally been formulated as 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-ber crrplae--based methods select graph transformation rules to apply based on expert rules [15 or use data-driven methods [8) such as neural network policy trained on a reaction corpus [19
Template-free free methods frame one-step retrosynthesis prediction as translation task of SMILES
strings (20] 21 or 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] [5]. 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 24.. Notably, Chen et al. [6] proposed Retro*, a neural-guide guided A A search algorithm that we build as part of our approach. Much additional work has been done to improve multi-step CASP algorithms [25 primarily via improvements of single-step policies in 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 more starting materials, shown Fig. 4 One exception is GRASP (13), which utilizes RI. 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 augment the retrosynthesis planner.
Synthesizable molecular design Recent advances in computer-aided molecular design have intro- duced 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 reaction network 39) The advent of deep generative modeling has further enabled the generation of synthetic pathways with neural models 40 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 prob- lems 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 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
(F2F) strategies [51] 52).
In F2E search, evaluations are made by estimating the minimal cost of a path between 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.
2.2 Formulation of general and starting material--onstraaine synthesis planning problems
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₂ E R is a tuple (r., ps, tt,),, comprising a set of reactants т; C. M, a single product p. -M, and retro template t, E T. A retro template t is function M - 2M that maps product to precursors such that Vi:, : r3 E t((p). Likewise, a forward template t' E T' is a function f' : :.M M where Vi: pa E (rx:)).
Given target molecule p" E M and set of building blocks (BBs) B C M, synthesis planning finds a valid synthetic route-a set of reactions S {R.... R, that satisfies the following constraints.
Constraint 1 (Synthesize all non-BBs). V m E ri, m $ B = 3j s.t. m = Pf;
Constraint 2 (Target is final molecule synthesized). i s.t. p. = p" V':Vi:p'' $ Tm
3

---

Finally, we require that the graph formed by S is directed acyclic graph (DAG), where for each i, the product P; is mapped to node, which has a directed edge to a node mapping to reaction R, which in turn has directed edges to nodes mapping to the reactants ri.
Starting material-constrrannd synthesis planning Given a specific starting material (s.m.)
r" E M, in addition to Constraint 2 valid synthetic route satisfies the following constraints.
Constraint 3 (s.m. used). 3 s.t. r" rs: s.t. r* E Ps:
Constraint 4 (s.m. not necessarily BB). v E rı, m BUU = s.t.t. m m= Pj:
Fig. Tb illustrates an example of a valid starting search. DESP can also be used for the more general form of the problem in which set of potential starting materials {ri (ri....rn)) ] is given on input, and least one leaf node must map to r for some 1 < i S n. For simplicity, we only consider the single r" case unless otherwise specified.
route found through bidirectional
3
Methods
DESP is built on the Retro* algorithm 6 and recent advances that enable conditional generation of synthetic routes from the bottom up [4 42).
3.1 Definition of synthetic distance, a goal-conditioned cost function
Like Retro 6 DESP is A*llike search and thus requires method of evaluating the expected cost of various frontier nodes. We follow Retro and use the notation (. (T). Vn. and rn functions (Section[A.2 details Retro and these functions). We also define function R > E which maps a reaction to a scalar cost. For a valid synthetic route S = (R,,.... Ra). the total cost of S is Σi= c( (. Vn represents the minimum total cost across every valid synthetic route 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-constraie setting, we require not only an estimate the cost of synthesizing molecule m from arbitrary building blocks, but also an estimate of the cost of synthesizing molecule m2 from m. specifically (in addition to other arbitrary building blocks). As such, we define a new function D .M x M + R, which term synthetic distance, it effectively represents the minimum cost distance between two molecules G, the graph constructed from the set of all possible reaction tuples R. More precisely, the synthetic distance from m, m2 is the difference between the minimum cost of synthesizing m2 across all valid synthetic routes containing my and the minimum cost of synthesizing m. 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.
3.2 DESP algorithm overview
In practice, synthesis planning problems are generally approached by simulating search through the complete reaction graph G. We follow Xie et al. (30) 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 GR = {p"} Gr = =rr" and introduce two expansion policies, one for "top-down" retrosynthesis expansions on GR and another for "bottom-up" forward expansions on Gr. 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 all nodes in the opposing search graph rather than just frontiers. For m & GR. we define a goal function 7 M + M such that (m) r* in F2E and 7(m) arg min D(g', m) in F2F. Likewise, for m GF, let (mm) = p" in F2E and ((m) arg min D(m, g²) in F2F.
The following quantities functions are relevant in the algorithm: rn, V.(m and V., from Retro*, and somewhat analogously dn, (mm)G)) and Dm. We briefly define the new quantities: (1) Dm represents ((7(m), m). (2) dn(m]G GR)))) represents the "distance numbers" of top node m.

---

DESP algorithm
promising frontier rode from
Expand selected and Update
Select promising frontier from
Expand the selected and Update search
mi
(F2E)
mi
Searchee
Viu
here
00
(F2E]
(F2F)
Sdil ineds reach BBs
b. Expansion procedures
search buildiin block cistabase
templates
top templates
Pred fingerprint building block
Retro expand Selected
Duilding block
bimolecular fwd. exp.
Forward expand Selected
If F2C: Target
Closes: my
uunimolacular exp, or retro exp.
Add product
precursors
Apply templates
search graph
Figure (a) DESP algorithm. Evaluation of top nodes is based on both Vm and D For F2E search, synthetic distance is calculated between molecule and the opposing goal, while for F2F, it is calculated based on the closest opposing molecule. (b) Overview of the one-step expansion procedures.
This is multiset of values Dm Vm for related frontier nodes collected for dynamic programming from the bottom-up during the update phase. (3) (m) multiset of all values of D,, Vm across frontier nodes in the minimum cost synthetic route to the target p" through molecule m. At high level, we introduce these quantities and new policies account for the fact that only one subgoal in 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 with each search having its own policies.
Selection For top-down selection, select an frontier molccule node that minimizes the expected total cost of synthesizing the target p" from the goal molecule r" through that node. Let Fn represent the set of frontier top molecules and Fr represent the set of frontier bottom molecules. Then, Mselect, < arg min [V: (m))Gn) min(D.(m\\nz)
(1)
mEFR
The bottom-up selection policy is identical to that of Retro*
Moelect, + arg min (m/GF)
(2)
mEFF
Expansion For top-down expansion, we follow other AND-OR-based algorithms in calling single-step retrosynthesis model, applying the top n predicted templates to the selected node and adding the resulting reactions and their precursors nodes the graph. For each added
molecule node m,, we initialize: (1) rn(m,|RR) + Vn.. equal to the Retro value function, and (Dm; Vnn) (D(7(m:), m.) Vn).
(2) RR(m;//R)
For bottom node m, we perform the forward expansion procedure detailed in Section 3.3 conditioned on (m). For each added product p;, then initialize rn(p:[GF) + Vp, D(p,, (p.))
5

---

Update For GR. we propugate updates to relevant values up the graph and then back down to related nodes, similar 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 Gr 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 GR. We first uppropagate, performing updates up the graph for reaction (AND) nodes and molecule (OR) nodes m, where the ch and pr functions return the children and parent nodes for an input node:
dn(R|Gn)
Σ
dn(m|GR)
(3)
mEch(R)
[1Dm- Sln--an Vm
if E Fr
dn(m/Gn) & dn aar min Rech(m) rn rn(R) GR)
(4)
GR)
otherwise
We then downpropagate the following updates:
De(H]GR) + dn(pr(R))Ga dn aarg (arg (ec rn(R) GR) + dd(R|GR)
(5)
De(m)Gn) +- Di (arg mim Répr(() rn (R) Gn)
(6)
Justification for the rules and additional details, including DESP pseudocode, in Section A.5
3.3 Forward expansion policy with conditional generation of one-step reactions
To perform forward one-step synthesis expansions, we adapt the approach of Gao et al.
42 Let
= M R and z! ' Ra be functions mapping molecule and template (respectively) to n-dimensional embeddings. We define two target functions:
: M MMMMM---- T' (MLP, (2 (m1) @ 2 (m2)))
(7)
fo : fx:Mxxx7 + k- NN (MLP (m1) + 2 (m2) @ 2 (t'))
(8)
Together, the learned approximations of fe and fo define our forward expansion policy (Algorithm which generates forward reactions for the expanded node my conditioned on m2.
Algorithm 1: FORWARD EXPAND(m,, m2, GF, N, K)
mi molecule selected for expansion, m2: molecule to condition expansion on, Gr: bottom search graph, N: num. templates to propose, K: num. building blocks search
< TOP N(o (MLP; (m1) @ 2m (m²)))) /* Get top N forward templates +/
for <- to N do
if ['i] is unimolecular then
p (m)1;
/* Apply fwd. template to m
F ADD B.AAADDRX(((( (M,
/* Add reaction and product to GF */
else
/* l'i is bimolecular */
b KNN (MLP, (2m (m1) 2m (m²) (+((t))
/* Get K nearest BBs by
cosine sim. */
Vj + K: Gp..ADDDRX(((E__ RXN((m), b), ( b[]), f(t):
/* Apply {[] */
end
end
3.4 Extracting multi-step reaction data from a reaction corpus for offline learning
To learn ft, ft, 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] 154 of approximately million deduplicated reactions. The dataset is filtered and processed (details in Section A.3). and template set TusPto extracted with RDChiral (55). The dataset is randomly divided into training and validation splits with ratio 90:10. From the training split RuSPTO we construct the graph GusPro- We filter reactions that (1) involve more than reactants or (2) whose product cannot be recovered by applying the forward template f', yielding REWD. GFWD, and TFWD-

---

Table 1: Benchmark dataset summary. Avg. In-Dist. % is the mean percentage of reactions in each route within the top 50 suggestions of the retro model. Unique Rxn. % the ratio of deduplicated reactions to total reactions across all routes. Avg. # Rxns. is the mean number of reactions in each route, and Avg. Depth is the mean number reactions in the longest path of each route.
Dataset
Routes
Avg. In-Dist. %
Unique Rxn. % Avg. # Rxns.
Avg. Depth
USPTO-190
190
65.6
50.5
6.7
6.0
Pistachio Reachable
150
100
86.1
5.5
5.4
Pistachio Hard
100
59.9
95.2
7.5
7.2
To learn ft and fo. a full enumeration of all pathways (until reaching nodes in B) rooted at p* is performed for each molecule node y" in GFWD. Reaction nodes in the enumerated pathways then each provide a training example for fe and fi. Likewise, we enumerate pathways GUSPTO, and each molecule node in pathway yields training example for learning (m,, p²). The details for our training procedures are described in Section
Notably, we inject "negative" examples into our training set for D, as the distribution of costs is highly skewed towards low values. We define a modified MSE loss function in Kim et al. [56 for learning D:
C == (Upred Ytruue )² max((, Dmaar + Upred)? else
if yorwe Dmaa
L - (maxxx
This strategy allows the model to default to an approximate value of Dmaz + 1 for any "highly distant" molecule inputs. Now, for each target p", we randomly sample molecule m GusPto with no path to p" and Tanimoto similarity < 0.7 and add training example with label co. In this work, we use Dmaz= 9.
Experiments
Our experiments are designed answer the following: (1) Does DESP significantly improve the performance of starting material-constraine synthesis planning compared to baseline methods? (2) To what extent do D and bidirectional search account for the performance 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?
4.1 Experimental setup
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], set of 190 targets with corre- sponding 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 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 distii-iistiibuttin and redundant reactions (Table T). 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-trun -trth 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 al. (6).
Model training As in 66, we train 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
Multi-step algorithms 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
7

---

planning performance across the three benchmarks. Solve rate refers to the percentage of (p", r*) pairs in the dataset solved at the given expansion limits. The average number of expansions N is given for each method, with max budget of 500.
Table 2: Summary of starting
Algorithm
USPTO-190
Pistachio Reachable
Pistachio Hard
Solve Rate (%)
N
Solve Rate (%)
t
N
Solve Rate (%) 1
N +
N=100
300
500
50
100
300
100
300
500
Random
4.2
4.7
4.7
479
16.0
26.7
40.7
325
6.0
12.0
13.0
452
BFS
12.1
20.0
24.2
413
48.7
57.3
74.0
169
16.0
26.0
29.0
390
MCTS
20.5
32.1
35.3
364
52.0
72.7
85.3
111
27.0
31.0
32.0
361
Retro*
25.8
33.2
35.8
351
70.7
78.0
92.7
73
32.0
35.0
37.0
342
GRASP
15.3
21.1
23.7
410
46.7
51.3
66.7
198
14.0
22.0
29.0
402
Bi-BES
20.0
26.3
28.4
382
66.0
75.3
86.0
101
28.0
34.0
38.0
341
Retro*+D
27.4
32.6
37.4
348
77.3
87.3
96.0
49
31.0
40.0
42.0
323
DESP-F2E
30.0
35,3
39.5
340
84.0
90.0
96.0
41
35.0
44.0
50.0
300
DESP-F2F
29.5
34.2
39.5
336
84.5
88.9
97.3
38
39.0
45.0
48.0
293
their GNN guided value estimation and thus refer to the algorithm as Retro for simplicity. This serves both baseline and ablated version of DESP (without bidirectional search D). In addition, we test the performance of random selection, breadth-first search (BFS), bidirectional-BFS, and MCTS. Finally, we integrate our single-step model into GRASP K 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 benehmark. For all methods, we enforce a maximum molecule depth of 11. maximum of 500 total expansions (retro or forward), and apply 50 retro templates per expansion. For DESP, we also enforee 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 the asymmetry of the bidirectional search, we also introduce a hyperparameter X, the number of times we repeat a select, expand, and update cycle for Gn before performing one cycle for GF. For all experiments, we set À = 2. Details and tabular summaries of the evaluations performed and hyperparameters chosen are provided in Section A.7
4.2 Results
Though it is notoriously difficult quantita- tively evaluate synthetic routes proposed in sil- ico without expert evaluation, there are widely- used metrics thought to correlate with successful algorithms, such as higher solve rate (under vary- ing computational budgets), lower average num- ber of expansions, and lower average number of reactions in found routes [59 [5]. We focus on these metrics, as they are arguably most related to search algorithm's '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.
Table 3: Average + stdev of the number reactions in proposed routes. Comparisons are made across (p" r")r") pairs solved by all methods.
Dataset
USPTO-190
Pistachio Easy
Pistachio Hard
# Routes
63
139
36
Avg. Rxus.
Retru*
5.56
4,94
4.81 2:2
Retm++/)
5.87 2:30
4.92 a: 1m
4,80 2.2
DESP-F2E
5.56
4,86
4.67
DESP-
5.95 1.591
5.17 1: 1.31
4,78 1.200
Improvement on starting material-constraamed synthesis planning Quantitative benchmarking results are summarized in Table 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 benchmarks (denoted as Retro*+D in Tables and We find that incorporating D generally results in higher solve rates and fewer average
8

---

b.
Pistachio Hard
Pistachio Hard
Combined Benchmarks
DEEP FAE
120
DESP
Solve Rate
Solve Rate
Routes
SCScore
SAScore
Fwd. Reactions
Figure 3: Ablation study. (a) Solve rate function of the binned complexity of target molecules in
Pistachio Hard. (b) Number of forward reactions DESP routes across all benchmark sets.
Keto-alpha
Appel
reduction
alkylation
target
hydrogenation
Williamson
starting
material
Figure 4: Exemplary synthetic route for test case that DESP-F22 was able to solve but Retro was unable to solve. DESP-F2F was able to match every step of the reference route this case.
expansions across all datasets, but still does not outperform DESP, demonstrating the role of both D and bidirectional search improving planning efficiency. As indicator of route quality, also investigate the average number of reactions in the outputs of DESP (Table 3). DESP-F28 is able to find shorter routes on average when compared to either Retro or Retro* guided by D. An example of route solved by DESP-F22 (but not by Retro*) is visualized in Fig.
Performance on complex targets To investigate the degree 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 [6]. Both variants of DESP equal or outperform Retro* on solve rates across all complexity ranges (Fig. (3)). This indicates that, in the starting
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-F28 able to find noticeably shorter routes on average than DESP-F2F, which finds routes even longer than Retro on multiple benchmarks 3). A likely reason for this difference is due to the lack of consideration of the pathway depth 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 in the solutions of each variant. As visualized in Fig. pp, DESP 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 [2] 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.
5 Conclusion
In this work, introduce DESP, a novel framework for bidirectional search as applied computer- aided 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 task that aligns with 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 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 provided in Section A.8
Code and Data Availablity
Relevant code with documentation can be found htttpee//ggtuubb.c//o/o///r////p
Acknowledgments and Disclosure of Funding
This research was supported by the Machine Learning for Pharmaceutical Discovery and Synthesis consortium. J.R. acknowledges funding support from the NSF Center for Computer Assisted Synthesis (C-CAS) under Grant CHE-2202693. W.G. is supported by the Google Ph.D. Fellowship and Office of Naval Research under grant number N00014-21-1-211
We thank Prof. Sarah Reisman and Prof. Richmond Sarpong for discussions during the ideation of the project. We thank Dr. Roger Sayle and NextMove Software for granting permission to release the Pistachio-derived benchmark sets. We thank Prof. Yunan Luo for providing computational resources used an earlier prototype of DESP. We thank Dr. Babak Mahjour for discussions around the chemical feasibility of proposed routes.
References
[1] E. J. Corey and Xue-Min Cheng. Logic of chemical synthesis. Wiley, New York, new ed. edition, 1995. ISBN 978-0-441-50979- 978-0-471-115944-6
[2] David A. Pensak and E. J. Corey. LHASA- and Heuristics Applied to Synthetic Analysis. In Computer-Assiisted Organic Synthesis, volume 61 of ACS Symposium Series, pages 1-32. American Chemical Society, June 1977. ISBN 978 07777--8442--03944 doi: 10. 1021/0//bbkb- 1977-0011
ch001. URL httpsstts://dii org 10. 1021/bk 1977 ch001 Section:
[3] Marwin H. S. Segler, Mike Preuss, and Mark Waller, Planning chemical syntheses with deep neural networks and symbolic AI. Nature, 655(7699):604-610,, March 2018. ISSN 1476-4687. doi: 10. 10.8////
www.nnatureecomm wwtpaatweee.ca.aarareeeeaaaaaeee
Pub-
lisher: Nature Publishing Group.
[4] Akihiro Kishimoto, Beat Buesser, Bei Chen, and Adi Botea. Depth-First Proof-Number Search with Heuristic Edge Cost and Application to Chemical Synthesis Planning. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. htt.tttts://ppcceeeiie neur.pss........................ wtc/paper_fiii /tagperffleesspper///1////////// httpp/appe/29//aaaae/e html
4f 1I122776811162211//880//66666663
[5] Philippe Schwaller, Riccardo Petraglia, Valerio Zullo, Vishnu H. Nair, Rico Andreas Haeusel- mann, Riccardo Pisoni, Costas Bekas, Anna luliano, and Teodoro Laino. Predicting ret- rosynthetic pathways using transformer-based models and a hyper-graph exploration strat- egy. Chemical Science, 11(12):33163333 March 2020. ISSN 2041-6539, doi: 10.1039,
10

---

C9SC05704H. URL https: rsc. http://pi.......ooo//ooooottttra http://///ooottttttrrrr////l////
c9sc05704h
Publisher: The Royal Society of Chemistry.
[6] Binghong Chen, Chengtao Li, Hanjun Dai, and Le Song. Retro*; Learning Retrosynthetic
Planning with Neural Guided A* Search, June 2020. URL http::/arxii......////// org/ hts//bbs/2000
15820 arXiv:2006. 15820 [es, stat].
[7] Iwao Ojima, Ivan Habus, Mangzhu Zhao, Martine Zucco, Young Hoon Park, Chung Ming Sun, and Thierry Brigaud. New and efficient approaches to the semisynthesis of taxol and its C-13 side chain analogs by means of 3-lactam synthon method. Terrahedron, 48(34): 7012, January 1992. ISSN 0040-4020. doi: 10. 10.1016//00040040200001999999999 http://///c..aaaeaaaaaaaa///////
URL
[8] Zachary G. Brill. Matthew Condakes, Chi Ting, and Thomas Maimone. Navigating the Chiral Pool in the Total Synthesis of Complex Terpene Natural Products. Chemical Reviews, 117188:11553-11795 September 2017. ISSN 0009-2668 2665. doi:
http:///s.ccemme../000 Publisher: American Chemical
BRRpstts:://dd org 1021/ acs. chemrev. 6b00834 Society.
[9] Agnieszka Wotos, Dominik Koszelewski, Rafal Roszak, Sara Szymkué, Martyna Moskal, Ryszard Ostaszewski, Brenden T. Herrera, Josef M. Maier, Gordon Brezicki, Jonathon Samuel, Justin A. M. Lummiss, D. Tyler McQuade, Luke Rogers, and Bartosz A. Grzybowski. Computer- designed repurposing of chemical wastes into drugs. Nature, 604(7907):666 676, April 2022. doi: 10. seriiceesss4158e5 022-00002-------00 04503-9
ISSN 1476-4687.
URL ptttps::/wwrrr nature com/ Publisher: Nature Publishing Group.
[10] Lauren M. Lopez, Quan Zhang, Orion Dollar, Jim Pfaendmerr Brent H. Shanks, and Linda Broadbelt. Application of automated network generation for retrosynthetic planning of poten- tial corrosion inhibitors. Molecular Systems Design & Engineering. 9(4):52 2711, 2024. doi:
10. (0.103/D3MM00012H URL hhttps//pubb rsc Publisher: Royal Society of Chemistry.
[11) Anna Ządio Dobrowolska, Karol Molga, Olga O. Kolodiazhna, Sara Szymkuć, Martyna Moskal, Rafal Roszak, and Bartosz. Grzybowski. Computational synthesis design for controlled degradation and revalorization. Nature Synthesis, pages 1-12, April 2024. ISSN 2731- 0582. doi: 10. 10000///44100000--000000
URL hhttps://mvt nawure. www.aaeee.oeeeeeeeeee...oooooooe articlet/ Publisher: Nature Publishing Group.
0111600004--04333
[12) A. Peter Johnson, Chris Marshall, and Philip N. Judson. Starting material oriented retrosyn- thetic analysis in the LHASA program. 1. General description. Journal of Chemical Infor- mation and Computer Sciences, 32(5):411 1-4177 September 1992. ISSN 0095-2338. doi: 11100//00000900033 utthstts::/ http:://.:o.oo......ee// 1001///000001/000000000000000000 Publisher: Ameri- can Chemical Society.
[13) Yemin Yu, Ying Wei, Kun Kuang, Zhengxing Huang, Huaxiu Yao, and Fei Wu. GRASP: Navigating Retrosynthetie Planning with Goal-driven Policy. Ad- vances in Neural Information Processing Systems, 35:10257-1026. December
2022. URL http:///ppppeeeeeeeeeeeeeeeeeeea
www.:nn.urii.cc.ooooo.. http://aarr..ileeeepppe///////// htmll html
[14] Pistachio, January 2024. URL // wttp://wwwwwttttttttttttee.....
html
[15] Sara Szymkuć, Ewa P. Gajewska, Tomasz Klucznik, Karol Molga, Piotr Dittwald, Michal Startek, Michal Bajezyk, and Bartosz A. Grzybowski. Computer-Assisted Syn- thetic Planning: The End of the Beginning. Angewandle Chemie International Edi- tion, 55(20):5904-5937, 2016. ISSN 1521-3773. doi: 20.10002aniee.01550611
URL
https:://ollneelibrrr wiley. com/ cww/doi doi (itoo//abe absaaaas/1111 1002/anie 201506101 http:///ppp0...0000..0m000110130
_eprint:
[16] Connor W. Coley, Luke Rogers, William H. Green, and Klavs Jensen.
Computer- Assisted Retrosynthesis Based on Molecular Similarity. ACS Central Science, 3(12): 1245, December 2017. ISSN 2374-7943. doi: (0..02//acscentsci./b000
URL hhtpps
//doi. eddii.org/11 1021/ 1w2.////cceeccc....c....... 7b00355
Publisher: American Chemical Society.

---

[17] Hanjun Dai, Chengtao Li, Connor Coley, Bo Dai, and Le Song. Retrosynthesis Prediction with Conditional Gruph Logic Network. In Advances Neural Information Processing Systems, vol- ume 32. Curran Associates, Inc., 2019. URL https: httpp:://proceedddiii neurips. weurips.cc/paper Abstract..ttall
[18] Shuan Chen and Yousung Jung. Deep Retrosynthetic Reaction Prediction using Local Reactivity and Global Attention. JACS Au, 1(10): 1620. October 2021. doi: 10. 10.1021/jacsau, Iafaacauulc00244 lc00246. /tR.hhtts:://o...rg/// 10. 1021// ety.
1c00246
Publisher: American Chemical Soci-
[19] Marwin H. S. Segler and Mark P. Waller. Neural-Symbolic Machine Learning for Retrosynthesis and Reaction Prediction.
Chemistry A European Journal, 23
(25):5966-5971. 2017. ISSN 1521-3765.
doi:
10. 1..100022000 www10002chemmoo 2001002/chem.22160544444 201605499.
URL
https://oullieelbraayy wiley coom/doi/aann /boo//a///// 10. 1002/ chem 201605499 http:///ww...m/////o/o///////mm/ 201.0le.....009999
eprint:
[20] Bowen Liu, Bharath Ramsundar, Prasad Kawthekar, Jade Shi, Joseph Gomes, Quang Luu Nguyen, Stephen Ho, Jack Sloane, Paul Wender, and Vijay Pande. Retrosynthetic Models. ACS Central Science, doi: (a0102//acscentsii..7ooo
Reaction Prediction Using Neural Sequence-to-Sequee
(10):1103-1113 October 2017. ISSN 7943.
URL
https://doi. http:///ooo.og////// org/10.. 1021 a00aacccettsc....... 7b00303 ety.
Publisher: American Chemical Soci-
[21] Philippe Schwaller, Teodoro Laino, Théophile Gaudin, Peter Bolgar, Christopher A. Hunter, Costas Bekas, and Alpha A. Lee. Molecular Transformer: A Model for Uncertainty-Calibrad Chemical Reaction Prediction. ACS Central Science, 5(9):1572-1183, September 2019. ISSN 2374-7943, doi: 10. wttp///accentci.bbOO000
URL https://doo oro.i...//00...222. Publisher: American Chemical Society.
acscentsci 9b00576
[22] Mikolaj Sacha, Mikolaj Blaž, Piotr Byrski, Pawel Dabrowskii-ummafskt Mikolaj Chrominski, Rafat Loska, Pawel Wiodarczyk-PPruzzyúss and Stanislaw Jastrzębski. Molecule Edit Graph Attention Network: Modeling Chemical Reactions Sequences of Graph Edits, May 2021.
URL htttp://axaii htrrg/abs/2006.. 15426 arXiv:2006. 110006..54420 15426 [physics, stat].
[23] Abraham Heifets and Igor Jurisica. Construction of New Medicines via Game Proof Search. Pro- ceedings the AAAI Conference Artificial Intelligence,
2012. ISSN 2374- 3468. doi: 10.16.0//... 1609/660.. v26il....66..... v26i1..23311 URL https://ojs aaai orgginde/s php/ AAAI/
article/view/aee /8311
Number: 1.
[24] Austin Tripp, Krzysztof Maziarz, Sarah Lewis, Marwin Segler, and José Miguel Hernández- Lobato. Retro-fallback: retrosynthetic planning an uncertain world, April 2024. URL
http:://arxxv.orr/aa//22133
arXiv:2310.09270 [es].
[25] John S. Schreck, Connor W. Coley, and Kyle J. M. Bishop. Learning Retrosynthetic Planning through Simulated Experience. ACS Central Science, 5(6):970-99) 981, June 2019. ISSN 2374. 7943. doi: 9b00055
0.00000 URL https://ddol orw.aa..rr/.... 1ttp////0.00///ccetttccc Publisher: American Chemical Society.
[26] Siqi Hong. Hankz Hankui Zhuo, Kebing Jin, Guang Shao, and Zhanwen Zhou. Retrosynthetic planning with experience- guided Monte Carlo tree search. Communications Chemistry, 6(1): 1-14, June 2023. ISSN 2399-3669. doi: 10. 000086444000002-009991
Utthttts:://ww
nature. com/ attp:/rttillsaaeee attpicclee//42244000---0000
Publisher: Nature Publishing Group.
[27] Guoqing Liu, Di Xue, Shufang Xie, Yingce Xia, Austin Tripp, Krzysztof Maziarz, Marwin Segler, Tao Qin, Zongzhang Zhang, and Tie- Liu. Retrosynthetic Planning with Dual Value Networks, March 2024. http://///r wwtp:///wwaa......o./.// 2300 13755 arXiv:2301.1377 [cs].
[28] Junsu Kim, Sungsoo Ahn, Hankook Lee, and Jinwoo Shin. Self- Improvedd Retrosynthetic Planning, June 2021. URL htt:://tt/// 04880) arXiv:2106.04889 (es, q-bio] version: 1.
12

---

[29] Songtao Liu, Zhengkai Tu, Minkai Xu, Zuobai Zhang, Lu Lin, Rex Ying, Jian Tang, Peilin Zhao, and Dinghao Wu. FusionRetro: molecule representation fusion via in-context learning for retrosynthetic planning. In Proceedings of the 40th International Conference Machine Learning, volume 202 of ICMI''23, pages 22028 22044, <conf-loc>, <citysoono </conf-loc>, July 2023. JMLR.org.
<stat>>>awaii<sttteee Ccountr>>USA</countt
[30] Shufang Xie, Rui Yan, Peng Han, Yingce Xia, Lijun Wu, Chenjuan Guo, Bin Yang, and Tao Qin. RetroGraph: Retrosynthetic Planning with Graph Search. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2120- 1129. August 2022. doi: 10. 10.1145/533478..5594444 arXiv:2206.1142 14477 [es].
BRLhhtt:///axx/
httg/ab//22000 11477
[31] Dengwei Zhao, Shikui Tu, and Lei Xu. Efficient retrosynthetic planning with MCTS explo- ration enhanced A search. Communications Chemistry, 7(1):1-12, March 2024. ISSN 2399. 3669. doi: 10. 100011/42000002--001101
URL htttps//wwet nature. com/ hammarticless Publisher: Nature Publishing Group.
942004-02--011332
[32] Jiasheng Guo, Chenning Yu, Kenan Li, Yijian Zhang, Guoqiang Wang, Shuhua Li, and Hao Dong. Retrosynthesis Zero: self-Improving Global Synthesis Planning Using Reinforcement Learning. Journal of Chemical Theory and Computation, May 2024. ISSN 1549-9618. doi: 10. 1021/acs.jctc.4c000 4c0007.. URL atttps://do org/ /0///..000 1021/ jctc 4c00071 Publisher:
American Chemical Society.
[33] Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojciech Zaremba. Hindsight Experience Replay, February 2018. URL /tttp//arazzi http::///aaxx....orr////////000 01495 vrXiv:1707.01495 [cs].
[34] H Maarten Vinkers, Marc R de Jonge, Frederik FD Daeyaert, Jan Heeres, Lucien MH Koymans, Joop H van Lenthe, Paul J Lewi, Henk Timmerman, Koen Van Aken, and Paul AJ Janssen. Synopsis: synthesize and optimize system in silico. Journal of medicinal chemistry, 46(13): 2765-2773, 2003.
[35] Markus Hartenfeller, Heiko Zettl, Miriam Walter, Matthias Rupp, Felix Reisen, Ewgenij Proschak, Sascha Weggen, Holger Stark, and Gisbert Schneider. Dogs: reaction-driven de novo design of bioactive compounds. PLoS computational biology, 8())xe0023800 2012.
[36] Alexander Button, Daniel Merk. Jan A. Hiss, and Gisbert Schneider. Automated de novo molec- ular design by hybrid machine intelligence and quleedriven chemical synthesis. Nature Machine Intelligence, 1(7):307-315, July 2019. ISSN 2522-5833 doi: 001138//42256-009-0006
http:ttss:///ww www.re.aarr...m com www.ecoo/aaa...eee 001p: 009-00---77--9-7----777---- lishing Group.
Publisher: Nature Pub-
[37] Ksenia Korovina, Sailun Xu, Kirthevasan Kandasamy, Willie Neiswanger, Barnabas Poczos, Jeff Schneider, and Eric P. Xing. ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations, October 2019. URL http::/t///// http//xxvv..o./ abs/ /908
01425
arXiv: 000880014440 425 [physics, stat].
[38] Sai Krishna Gottipati, Boris Sattarov, Sufeng Niu, Yashaswi Pathak, Haoran Wei. Shengchao Liu. Karam M. J. Thomas, Simon Blackburn, Connor W. Coley, Jian Tang, Sarath Chandar, and Yoshua Bengio. Learning To Navigate The Synthetically Accessible Chemical Space Using Reinforcement Learning, May 2020. URL htth:://aaxiiii org/ arg/abs/ 2004. 12485 arXiv:2004.1 12485 [cs].
[39] Kyle Swanson, Gary Liu, Denise B Catacutan, Autumn Arool, James Zou, and Jonathan M Stokes. Generative ai for designing and validating easily synthesizable and structurally novel antibiotics. Nature Machine Intelligence, 6(3):338-33 2024.
[40] John Bradshaw, Brooks Paige, Matt Kusner, Marwin H. S. Segler, and José Miguel Hernández- Lobato. Model to Search for Synthesizable Molecules, December 2019. URI. http: //arxiv. abs/1906...11//////// 1906. 05221 arXiv:1906.0522 052221 [physics, stat].
13

---

[41] John Bradshaw, Brooks Paige, Matt J. Kusner, Marwin H. S. Segler, and José Miguel Hernández- Lobato. Barking up the right tree: an approach search over molecule synthesis DAGs. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, pages 0852-6866, Red Hook, NY, USA, December 2020. Curran Associates Inc. ISBN 978- 978-1-71382-990
[42] Wenhao Gao, Rocío Mercado, and Connor W. Coley, Amortized Tree Generation for Bottom-up Synthesis Planning and Synthesizable Molecular Design, March 2022. URL httt::/arxii
Org/abs/21100
06389 arXiv:2110.0633 [es, q-bio]
[43] Miruna Cretu, Charles Harris, Julien Roy, Emmanuel Bengio, and Pietro Liò. SynFlowNet: Towards Molecule Design with Guaranteed Synthesis Pathways, May 2024. URL http:
/ //arxiv. wttp://///bbb..../// 2015b TrXiv:2405.01155 [cs, q-bio].
[44] Shitong Luo, Wenhao Gao, Zuofan Wu, Jian Peng, Connor W. Coley, and Jianzhu Ma. Projecting Molecules into Synthesizable Chemical Spaces, June 2024. WtRlhhttp//arrt wrgg /bs/ 2406. 04628 arXiv:2406.04622 [cs, q-bio].
[45] Ira Pohl. BI-DIRECTIONAL AND HEURISTIC SEARCH IN PATH PROBLEMS. 1969.
[46] Ping He, Zhixian Xu, Xiaoqing Long, Kang Hou, and Yu Xiang. Path Planning of Mobile Robot Based on Improved A-Star Bidirectional Search Algorithm. In 2023 IEEE International Confer- ence Unmanned Systems (ICUS), pages 1517-1522, October 2023. doi: 10.1 10/11U//13 1123.10384422 URL https: btttps://ieeeploore www.. www.ee/.ggggasstttttt/ooommm///e ISSN: 2771-7372
[47] Chenming Li, Han Ma, Jiankun Wang. and Max Q.-H. Meng. Bidirectional Search Strategy for Incremental Search-based Path Planning. In 2023 JEEE/RSJ International Conference on Iniel- ligent Robots and Systems (IROS), pages 7311-7317, October 2023. doi: 10/1005//0055555 2023. 103330934 URL htttps://eeeexplore ieee. wwweee.rrg/eee watsssttrccc/occeet////oo/. ISSN: 2153-0866.
[48] Simon Alford, Anshula Gandhi, Akshay Rangamani, Andrzej Banburski, Tony Wang. Sylee Dandekar, John Chin, Tomaso Poggio, and Peter Chin. Neural-Guided, Bidirectional Program Search for Abstraction and Reasoning. In Rosa Maria Benito, Chantal Cherifi, Hocine Cherifi, Esteban Moro, Luis M. Rocha, and Marta Pares, editors, Complex Networks & Their Applications X, pages 657-668, Cham, 2022. Springer International Publishing. ISBN 978-3- 030-93409-5. doi: 10010007797---10 3--30-93409-5--00
[49] A. Lakshna. S. Gokila, and K. Ramesh. Shortest Route Bidirectional Search Algorithm for Predicting Shortest Routes in Traffic. In 2023 4th International Conference on Smart Electronics and Communication (ICOSEC), pages 533-539, September 2023. doi: 10. 19// 2023. 10275999 URL htt.:tttss//eeeppleeeeeee
ieee. org/ ottp///astaacc/aaccmeee///255553
[50] Robert Holte, Ariel Felner, Guni Sharon, and Nathan Sturtevant. Bidirectional Search That Is Guaranteed Meet in the Middle. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1), March 2016. ISSN 2374-3468. doi: 10. 10.99/9//ai v30i1.10033 URL https://ojs aaai org/ index. ahtp/AAA///arrrccle///s/////////
Number:
[51] Lenie Sint and Dennis De Champeaux. An Improved Bidirectional Heuristic Search Algorithm. Journal of the ACM, 24(2):177-111, April 1977. ISSN 0004-5411, 1557-735X. doi: 10.1145/ 022003.32208 |tl.:tttss///.......oo////////00
322004
[52] H. Kaindl and G. Kainz. Bidirectional Heuristic Search Reconsidered. Journal of Artificial Intelligence Research, 7:283-317, December 1997. ISSN 1076-9757. doi: 10.1613/jair.40)
URL /www http://pw.r.ggeee..pp/////////// httpp//wwwpppppppaaaaaaa////////
org wwwrr/iinde..cc
[53] Daniel Mark Lowe. Extraction of chemical structures and reactions from the literature. October
2012. URL
cam ac htt.aaaccchhaaaad////////7777
[54] Daniel Lowe. Chemical reactions from US patents
URL
14

---

[55] Connor W. Coley, William H. Green, and Klavs F. Jensen. RDChiral: An RDKit Wrapper for Handling Stereochemistry in Retrosynthetic Template Extraction and Application. Journal of Chemical Information and Modeling, 596))2529-25377 June 2019. ISSN 1549-9596. ort/ 1021/acc.. jeim. 9b00286
doi: 10. (0.1021/acs.jcinn jem.m..m..00066...... URL. httpps://oo..org//10000////
Publisher: American Chemical Society.
[56] Hyeongwoo Kim, Kyunghoon Lee, Chansu Kim, Jaechang Lim, and Woo Youn Kim. DFRscore: Deep Learning- -Band Scoring of Synthetic Complexity with Druu-Focused Retrosynthetic Analysis for
Virtual Screening. Journal of Chemical Information and Model- ing, 64(7):2432 2444, April 2024. ISSN 1549 1549-9596. doi: 10. 10.100//ass.jimm 3300 134. URL Publisher: American Chemical Society.
https://doi.
20221/ac..cciii 3c01134
[57] Krzysztof Maziarz, Austin Tripp, Guoqing Liu, Megan Stanley, Shufang Xie. Piotr Gaiński, Philipp Seidl, and Marwin Segler. Re-evaluating Retrosynthesis Algorithms with Syntheseus, February 2024. http:t /tttxiv///axvv.../ org/ abs/aas////0/ 19796 0rXiv:2310.19796 [cs, q-bio].
[58] Samuel Genheden and Esben Bjerrum. PaRoutes: towards framework for benchmark- ing retrosynthesis route predictions. Digital Discovery, 1(4):527-539, August 2022. ISSN 2635-098X. doi: 10. 00.103//22D00005E. URL https://pubs: httpppubsrsc..ooo or/p///co//////tttt///////////// content/ Publisher: RSC.
articlelandinng2022// /d/
2ttp:///0200222////2220000000 a2dd00015f
[59] Paula Torren-Peraire, Alan Kai Hassen, Samuel Genheden, Jonas Verhoeven, Djork-Ame Clevert, Mike Preuss, and Igor Tetko. Models Matter: The Impact of Single-Step Retrosynthesis on Synthesis Planning. Digital Discovery, 3())555--57,, 2024. ISSN 2635-098X. doi:
10. 10.1039/D3DD00252. URL Sttt:///axxiv org/ aws/abs///e/ 2308 05522 [physics, q-bio].
arXiv:2308.05522
[60] Connor W. Coley, Luke Rogers, William H. Green, and Klavs F. Jensen. SCScore: Synthetic Complexity Learned from a Reaction Corpus. Journal of Chemical Information and Modeling, 58(2)252-261, February 2018. ISSN 1549-9596.
doi: 10. 1/cc//.jccmmmm... /tiacsjjjimm70006222 URL
1at111..12//aa/ 1021/acs. jcim. 7b00622
Publisher: American Chemical Society.
[61] Peter Ertl and Ansgar Schuffenhauer. Estimation of synthetic accessibility score of drug-like molecules based on molecular complexity and fragment contributions. Journal of Chem- informatics, 1(1):8 June 2009. ISSN 1758-2946. doi:
URL
https://ddi. org/10...00... 10. 1186/ 2947588--9---8888
[62] David Weininger. Smiles, chemical language and information system. 1. introduction to methodology and encoding rules. Journal of Chemical Information and Computer Sciences, 28 (1):31-36, Feb 1988. doi: 10. 10.1021/c100057:000.
[63] Gregory Landrum. RDKit. URL httpt://t//ete www.t...ww....o. org/
[64] Raymond E. Carhart, Dennis H. Smith, and R. Venkataraghavan. Atom pairs as molecular fea- tures structure-activity studies: definition and applications. Journal of Chemical Information and Computer Sciences, 25(2):64-73, May 1985. ISSN 0095-2338. doi: (0.102/cc000AAA0000 Publisher: American Chemical Society.
URL (ttLlhttts://dde wrg/100 10. 1010000000000
[65] Connor W. Coley, Dale A. Thomas, Justin A. M. Lummiss, Jonathan N. Jaworski, Christo- pher P. Breen, Victor Schultz, Travis Hart, Joshua S. Fishman, Luke Rogers, Hanyu Gao, Robert W. Hicklin, Pieter P. Plehiers, Joshua Byington, John S. Piotti, William H. Green, A. John Hart, Timothy F. Jamison, and Klavs F. Jensen. A robotic platform for flow synthesis of organic compounds informed by AI planning. Science, 365(6453) 1566, August 2019, doi: 10. /e11////ienceeaann 1566. URL / h/www///wwwwww.w. science. org/ doi/10. 1/////00..1....1 1126/ Publisher: American Association for the Advancement of Science.
aax1566
[66] Michal Zawalski, Michal Tyrolski, Konrad Czechowski, Tomasz Odrzygóčdz, Damian Stachura, Piotr Piękos, Yuhuai Wu, Eukasz Kucinski, and Piotr Miloć. Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search, May 2024. URI //trx//avvvvv//////// wwwpsiii.orrreeee 2206.00702 arXiv:2206.0011 00702.
org/org..................... abs/
15

---

[67] José Cambronero, Sumit Gulwani, Vu Le. Daniel Perelman, Arjun Radhakrishna, Clint Simon, and Ashish Tiwari. FlashFill++: Scaling Programming by Example by Cutting to the Chase. Proceedings of the ACM on Programming Languages, 7(POPL):952 981, January 2023. ISSN 14755-421. doi: 10.1 1 145/3571226. URL htt..https://// //d1 acm. http:///oo/.1111//55////11111111
16

---

A
Appendix supplemental material
A.1
Summary of notation
Symbol
Note
set all valid molecules
R
set of all valid reactions
T
set all valid retro templates
T
of all valid single-product fwd. templates
set of building blocks, where B C M
the AND-OR graph constructed from all possible reaction tuples R
R
single-product reaction retro reaction template
fwd. reaction template target molecule
p"
r"
starting material goal valid synthetie route
s
reaction cost function
7(m)
given m, opposing molecule condition selection or expansion on top-down search graph
GR
Gr
bottom-up search graph frontier molecule nodes in Gr
Fr
FF
frontier molecule nodes in GF
Vm (retro)
estimated minimum cost of synthesizing m estimated value of (mm)
Vn (fwd.)
rn(m G)
"reaction number." estimated cost of synthesizing given search graph G
Vi(m/G)
estimated cost of synthesizing p" using m given search graph G
D
synthetic distance (network)
Dm
estimated value of D(>(m).
dn(m)
"distance numbers," multiset of descendent Dm Vnn values for in G multiset of related Dm Vm values for m G
Dm
fe
forward template predictor model building block predictor model loss function
fo
L
Dmaz
maximum value of D considered in retro expansions perform before one fwd. expansion
A.2 R algorithm details
Retro* defines the following quantities:
1. Vm. For a molecule m, Vm is an unconditional estimate of the minimum cost required to synthesize m. is estimated by neural network.
2. rn(m]G). For molecule m, given search graph G, the "reaction number" rn(m GG) represents the estimated minimum cost of synthesizing m.
3. (m) For a molecule m, given search graph with goal p", (.(m 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 frontier nodes F that minimizes the expected cost of synthe- sizing p" given the current search graph G' is selected:
Meleett arg min Ve(mG))
(10)
mEF
Expansion is Alg. 2 one-step retrosynthesis model is called on the selected node and the resulting reactions and precursors are added to G. Each molecule node then initialized with rn(m[G) <- Vn.
17

---

Update
First, reaction number values are uppropagated to ancestor nodes. For reaction node R, the reaction number is updated the sum of its childrens' reaction numbers.
rn G - c(R)+ +
Σ rn(m|G)
(11)
mech(
For molecule node m, the reaction number becomes the minimum reaction number among its children.
rn(m G)
min (n(R)
(12)
REch(m)
Next, Vi(mlpp) values are downpropagated descendent nodes. Starting from p" itself,
Vi(p"G) + rn(p"|G)
(13)
For subsequent reaction nodes R, the value is updated
Vi(RG)) + rn (R|G) rn(pr(R))G) (AAr()))))))
()(p((R))G)
(14)
Finally, for molecule node m that is not p",
(i + min rn (R[G) REpr(m)
(15)
A.3 Reaction pre-processing
Reactions in the USPTO-Fuu 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 RREACTTANTSSREAAEEEES>PPOOO
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 single- product reaction SMILEE by creating separate entries for each product species with the same reactants and reagents. Each pegllctrrodcc 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 products are then filtered out.
A.4 Model training details
Dataset construction To learn ft and fu, full enumeration of all pathways (until reaching nodes in B) rooted at p" is performed for each molecule node p" in GEWD. For learning f., each reaction node R2 (rr, Pr; (4) is then used as a training example for each reactant my E ra with input Fm (m,) ( zm (p") and one-hot encoded label l, Likewise, for learning fb. each reaction node R. = (fm1, m2..:12.0 Pt, t4) that is bimolccular and involves at least one building block yiclds a training example with input 2m (m²) ) 1 2 (p') @ 2 (t.) and output 2 (m2) if m2 E B and with input 2 (m2) (m2)a2m (p*) 2 (t,) and output na (m1 mf E B. The procedure for such training example generation is illustrated in Fig. With nı 2048, n22 256, we use the RDKit implementation of
the Morgan Fingerprint 63 with radius for 2m and the Atom Pair fingerprint (44 for 24-
Because D is used to bias both the sop-down and bottom-up searches, we perform the same pathway enumeration for all molecule nodes p² & B.pp E GUSPTO. 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 mn in a solved search graph, with input = (m;) am (p" and label Vp- (m:/Gn) (n)))rnnnn GR), with 512. For calculating this label, we propagate the Retro functions as described in Section
18

---

A.2 such that D can be calculated as the minimum cost of synthesizing p" subtracted by the minimum cost of synthesizing m,. Here, we set c(R,) 1 for all R,, 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 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 m E
For validation of the fs and fa models, we construct the graph Gval 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 reaction not in the original training split used validation example. For validation of the D model, we construct Gval from RUSPTO and perform the pathway enumeration only on p" SUSPTO to obtain validation examples.
Enumerate full search tree across reaction network
Extract distance and forward reaction data from subgraph
fe p p'==
fummayp" P,)))
Target
Non buyable
ma
D(mavp") D(mi,p")
Building block
Reaction
Figure 5: Illustration of data extraction procedure for offline training of for for and D. (a) For each target, the full search graph is enumerated by recursively tracing outgoing edges and propagating Retro* quantities. (b) For each bimolecular reaction with least one buyable reactant, training examples for fo and fo are labeled. For each molecule node m other than the target, ((m, is computed.
Predicted vs Actual Synthetic Distance (R*2 0.852)
12
predicted values
Actual Values (Capped at 10)
Figure 6: Predicted vs. actual values of synthetic distance on the validation examples. Actual values above are set 10.
Model hyperparameters models are MLPs trained with the Adam optimizer, early stopping (patience 2), and decayed learning rate on plateau with factor 0.3 and patience 1 on single NVIDIA RTX 4090. The following table summarizes the hyperparameters and details each model used in experiments.
19

---

Model
Batch Size
Dropout
Activation
Hidden Layers
Hidden Units
Learning Rate
Input Dim.
Output Dim.
Retro Template
2048
0.5
Sigmoid
2048
0.002758
2048
270794
Template
1024
0.005113
196339
BB Model
4096
0.3
Rel.ll
20488
0.001551
6144
256
Retro Vi
4096
0.2
SILU
128
0.0025
2048
Synthetic
Sigmoid
0.00489
Hyperparameters were selected based on best performance on the validation split while performing Bayesian search through the following parameter space:
1. Dropout: [0.1, 0.2, 0.3, 0.4, 0.5]
2. Activation: [ReLU, SiLU, Sigmoid, Tanh]
3. Hidden layers: [2, 3, 4]
4. Hidden units: [1024, 2048] for retro, forward, and BB. [128, 256] for D and Vn
5. Learning rate: [0.00001 0.01]
The template relevance module from the open-source ASKCOS codehase was used to train the one-step retro model!]
A.5 DESP additional details
Uppropagation
b. Downpropagation
m min([5, 11)) =
V==5 DE= [0]
dn dn(arg mina((5, I1])) [0]
5 dn 4
=I=11
dn m 4- [-7,2]
D [O]
D [-7,2]
Vm Dm 4
Vm 8 Dm =1
Vm Dm 4
V==
V== 11
===
D.= [0]
D.= (-7,2)
D. [-7,2)
V++ min(D:)= V+ min(D:)=
Figure 7: Simple visual example of DESP update procedure for guiding top-down search with synthetic distance, where each reaction has cost In the unguided Retro* algorithm, the left-most frontier node would be chosen for expansion, as a route through that node minimizes Vi(m G'), the expected cost to the target from building blocks (5 reaction steps). 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 (G + min D, (m|G) = predicted reaction steps total in the final solution.
Algorithm 2: RETRO BETER_DE GR. N) m: expanded molecule node, GR top search graph, N: num. templates to propose
t + TOP (OP_N(((MMPP (( (m))))) ;
/* Get top N templates from retro model */
for f- to
r (mm)
/* Apply retro template to */ Add reaction and precursors to GR */
AR ADD_ADDDD,,,,__ m, ([);
end
'Template relevance module can be found at http:://gttab.ooo//pppssttttsts/
Semplate_relevance
20

---

Algorithm 3: DESP(p", r", Ni. N2, K, L, X,
p": target, starting material goal, N1: num. retro templates to propose, N2: num. forward templates to propose, K: num. building blocks to search, L: max num. expansions, A: num. times expand top before expanding bottom, s: strategy (F2E F2F)
GR
/* Initialize search graphs */
GF
1- 0:
while not solved OR | I L do
for i 4 to X do
m f- arg min [Vi(m]Gn) + min(Di(m[Gn))
/* Select best top */
RETRO EXPAND(m, N
/* Expand with Alg 2 */
TOP UPDATE(GR):
/* Update Gn with Section 3 rules */
met bottom then
myet- 0:
/* Set expected cost of met node to 0 */ /* Retro* updates on GF */
BOT UPDATE(Gr):
end
( 1+1;
end
m < arg min Ve(mlGp);
/* Select best bot */
if F2E then FORWARD EXPAND(m,, (m. p", GF. N2, BOT BOT_UPDAN SFLPUUDATE(G.F...
/* Expand conditioned on p" */
/* Retro* updates GF */
else if F2F then
@ + arg min 9);
/* Find closest node */
FORWARD BERRD_EEPADDmm... q, Gr, N2, K);
/* Expand conditioned on q */
BOT BOL_PDATTE(Gr.
/* Retro* updates GF +/
if met top then
Mmee-TT +- O, mm + [0]: /* Set expected costs of met node to 0 */ TOP
TOP .OP_UPDATE(F)::
/* Section 3 updates on GR */
end
1 + 1+1;
end
Design of new quantities and update rules recall that the minimum total cost synthesizing the target p" from molecule under the Retro framework is estimated as:
Vz(mGR)
Σ
c(r)+
Σ
rn(m' GR)
(16)
rEAT(M GR)
where Am]|GR) represents the set of reaction node ancestors of m and y (GR) represents the set of molecule nodes in the search graph. This is equivalent to
V((m|GR) ((mmmnn)
Σ
Vm
(17)
mmEE((((RR)
where g(m Gn) aggregates the current cost from all reaction nodes in Gn contributing to (m(m) R). and Gm))R)) C Fn accordingly represents the set of frontier top nodes for the subgraph of Gr corresponding to nodes contributing to Vi(m GR). If we add the constraint that one frontier node must implicitly be the ancestor of r* the estimate of the minimal cost then becomes:
Vi(m/GR) = g(m|GR) +
min myEN(( GR)
Σ
Vm, + D(r", my)
(18)
g(m|GR) +
Vin + min (m mmEA((|(GR)
Σ
(D(r", ())) ) Vm,)
(19)
Vv(mm(R)) +
min Dm,
(20)
my [M([(G)
21

---

Our update rules are implemented such that (m) m (m( Dmy, thus justifying our design of the selection and update procedures. Note that this design relies on the assumption that M (m/[G remains static upon adding the goal node constraint, when in reality the introduction of 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 in this way empirically works well (Section 4.2) A simple visual example of the update procedures is provided in Figure
A.6 New benchmark set details
We follow the test set extraction procedure of Chen et [6], applied within patents of the Pistachio dataset [4]] (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 routes for different route lengths (Fig. 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 term Pistachio Hard. Due to bug in implementation of criterion (2), small number routes share the same reaction in the final datasets, but the degree inter-route reaction duplication is still significantly less than that of USPTO-199 for both benchmark sets (Table
Pistachio Reachable
40
35
Routes
25
20
#
10
2
3
5
7
9
10
# Reactions
Figure 8: Distribution of reaction counts in Pistachio Reachable.
A.7 Additional experimental details
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 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 * and DESP are both calculated as log p, where is the template plausibility from the one-step model (retro or forward). For GRASP, we used the authors' search implementation I3. For fair comparison with the AND-OR graph structure, we did not increment the iteration counter when molecule that had previously been expanded was expanded again. training the GRASP value network, we use the authors' reported hyperparameters where applicable and the default values in their code base otherwise.
22

---

Pistachio Hard
14-
12
10
# Routes
8
6-
4-
2
2
10
12
14
# Reactions
Figure 9: Distribution of reaction counts in Pistachio Hard.
Table 4: Summary of hyperparameters used for evaluated algorithms.
Algorithm
Hyperparameter
Value
All
Max # expansions
500
Max mol. depth (top)
11
Max mol. depth (bottom)
Max retro templates
DESP / Bi-BFS
Max # fwd. templates
25
Max # BBs retrieved
MCTS
Exploration weight
1.0
Table 5: Summary of components of each evaluated algorithm.
Algorithm
Selection Policy
Guidance
Bidirectional?
Random
Randomly selected frontier node
None
No
BFS
Lowest depth frontier node, ties broken by reaction cost
None
No
MCTS
Start from root and use UCB select children until reaching frontier node
None
No
Retro*
Node minimizing (mm
No
GRASP
Same MCTS
BB
No
Bi-BFS
Same
None
Retro D
Node minimizing (1 G) min( (.(m)))
BB and s.m.
No
DESP
Alternate between top-down and bottom-up.
BB and s.m. and target
Yes
both using Retro and D
Approximate nearest neighbors search In selecting building blocks the forward expansion with k-NN search, the Python library Faiss is used. A 256-dimension Morgan fingerprint of each building block is stored vector database and compressed using product quantization for approximate nearest neighbor search at dramatically faster speeds and significantly lower memory overhead.
Compute All experiments were performed on a 32-core AMD Threadripper Pro 5975WX processor and with single NVIDIA RTX 4090 GPU, Running experiments all benchmark sets for given
23

---

method took around 10 hours. DESP requires ~ 3 GB of GPU memory to store the building block database for fast k-NN.
A.8 Limitations and Outlook
Convergent syntheses Convergent synthetic routes, in which multiple non-BBs are combined, are often desirable in chemistry due 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-uy 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 expansions take around 50% more time than retro expansions, though this is part because our implementation of forward synthesis applies retro templates to each product proposed by the forward model to ensure template reversibility (i.c., 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.
each iteration. In all, forward
Building block specification Though DESP is designed to address starting material-constraine synthesis planning, we envision that future work could optimize bidirectional search to improve general retrosynthesis capabilities by conditioning
starting materials instead of constraining the solution space. These starting materials could be expert-designed or predicted algorithmically in Gao et al. 42
DESP-F2F implementation In general, neither DESP-F2E or DESP-F2F guarantee that the cost- optimal 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 's nodes (1 Gr) rn(m' rn(m'(Gr) when calculating dn(m GR), and likewise the value of rn(m GF) does not take into account V.(m'|GR) rn(mn' ()) As result, the selection policy DESP-F2F selects nodes that minimize the lowest expected cost of reaching the opposing search graph, but does not select 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 (mmmG) 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- divide-and-conuuer strategies that have been utilized in general purpose planning [66] or program synthesis [67]. general, there are rich bodies of literature in fields like hierarchical planning and program synthesis that remain largely untapped in applications computer-aided synthesis planning.
24

---

NeurIPS Paper Checklist
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 explicitly enumerated in Section I and are each backed by our methods (Section 3 and experimental results (Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations 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 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 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
25

---

Justification:
This paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Experimental setup provided in Section 4 and further details are provided in Section A.7 Source code is also included in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
26

---

Answer: [Yes]
Justification: We provide the full source code and new benchmarks for DESP our sub- mission and will release the exact model weights, processed data files, and data processing scripts upon publication. Trained model weights are too large to share through an anonymous Github repo during review.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
Bealiic/guies//// /ote///ummmiiiiooooooooo oolic) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ /ttps.cccppbllcc////ccpcoopopopp
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity. the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We provide dataset construction and model training details in Section A.4
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provide standard deviations for the average number of reactions in the solved routes in Table 3 The general performance experiments for methods (solve
rate) are deterministic because they are statistics over the entire test set, following previous papers.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
27

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Compute details are described in Sections A.4 and A.7
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. 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 Section
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
28

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 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 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).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We do not anticipate any significant risks associated with releasing data and models this work.
Guidelines:
The answer NA means that the paper poses 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 best faith effort.
12. Licenses for existing assets
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?
Question:
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 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.
29

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
datasets.papersstt
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification: We introduce new benchmark targets using small number of molecules from the Pistachio database (license for this subset: CC BY-SA-NC). We describe how they were extracted in Section A.6
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
30

---

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.
31


Reviews:
[{"review_id": "jLmcFuEJz4", "reviewer": "Reviewer_qRkp", "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.", "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": "n/a", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- addresses an important outstanding problem in the community\n- sound experimentation from the chemistry perspective", "weaknesses": "- none really", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We address your comments and suggestions as follows:\n\n---\n\n**Reviewer:** \n\n_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._\n\n**Response:** \n\nThank you for bringing this up. Though these papers perform evaluations on a different problem setting and with different test sets (other than USPTO-190), our results on the starting material-constrained task also find relatively small differences between the two widely used uni-directional search algorithms (MCTS and Retro*) on both USPTO-190 and our new benchmark sets. We will make note of this in the final version of the manuscript.\n\n---\n\n**Reviewer:**\n\n_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._\n\n**Response:**\n\nThank you for the suggestion! While we do outline the various baselines and relevant hyperparameters in the “Multi-step algorithms” paragraph of **Section 4.1**, we will also add a table to summarize descriptions of our implementations and algorithm-specific hyperparameters to make this more clear. We have included such tables in the author rebuttal (**Tables 1 and 2**) and will incorporate them in our final manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gzNoQg9XcB", "reviewer": "Reviewer_WuVQ", "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.", "questions": "- Is the BFS top-down only or bottom-up only? Would it be useful to include a \"bidirectional BFS\" baseline? \n\nSuggestions/typos:\n- 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?\n\n- 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? \n- line 106 typo, two front-to-end's \n\nYou 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)\n- Maybe this is relevant to addressing the convergent synthesis limitation? not sure.", "limitations": "The limitations section looks great!", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is very clearly written, with lots of great notation and detail provided. Despite not being familiar with this area, I found the high level ideas easy to follow. \n\nI am familiar with top-down and bottom up program synthesis, so I can follow the high level ideas. But I am not very knowledgable about chemical synthesis and the literature on it. I did not closely read the details of the algorithm, other than trying to understand the high level additions compared with the Retro* baseline. The fact that I could still get a lot of technical value from the paper, despite not paying attention to the chemistry details, and thinking of it just as a generic synthesis-y problem, is to be commended and a sign of the paper's strength and significance. \n\nThe results look good. \n\nBidirectional search seems useful to apply to chemical synthesis, especially to the problem studied.\n\nit really seems like great technical caliber has been applied to this problem. Care and precision is applied to creating the algorithm.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and the kind words about our work! We address your comments one by one.\n\n---\n\n**Reviewer:**\n\n_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._\n\n**Response:**\n\nThank you for pointing this out. We agree that the bidirectional search introduces complexity, though we would argue that some amount of increased complexity is inherent (and not unnecessary) to a double-ended search. One area to tackle the increased complexity is the forward expansion policy (**Algorithm 1**), which is more complex than the retro expansion policy (**Algorithm 2**), as some templates necessitate a second model call and k-NN search over a large database. Synthesizable molecular generation is rapidly attracting more attention ([1], [2], [3] published since we submitted this paper), and we believe a simpler or more elegant method of performing the bottom-up search can likely be integrated in future work. While it cannot trivially be plugged into DESP, ChemProjector (Luo et al. [1]), for instance, demonstrated that a lone transformer architecture can improve bottom-up planning performance by directly decoding the actions to perform, comprising an arguably less complex overall algorithm. \n\n---\n\n**Reviewer:**\n\n_Is the BFS top-down only or bottom-up only? Would it be useful to include a \"bidirectional BFS\" baseline?_\n\n**Response:**\n\nThe BFS is top-down only. The new baseline is a great idea! We have performed the bidirectional BFS experiment and attached the updated results table in the author rebuttal (**Table 3**). We find that the bidirectional BFS results in fewer node expansions on average than uni-directional BFS, but does not consistently outperform uni-directional baselines like MCTS or Retro*. Thank you for the suggestion.\n\n---\n\n**Reviewer:**\n\n_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?_\n\n**Response:**\n\nThank you for the suggestion. Your understanding is correct, and we will make this more explicit in the final version!\n\n---\n\n**Reviewer:**\n\n_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?_\n\n**Response:**\n\nYes, your understanding is correct. “Retro* + D” is DESP as described in **Section 3.2** but without any bottom-up expansions to serve as an ablation. As with our last response, we will make these distinctions more clear in **Section 4.1**. We have also included **Table 2** in the author rebuttal to summarize the evaluated algorithms and their components. We will include this in the appendix of the final manuscript and hope this helps with some of the points of confusion.\n\n---\n\n**Reviewer:**\n\n_line 106 typo, two front-to-end's_\n\n**Response:**\n\nThank you for pointing this out! We will fix that.\n\n---\n\n**Reviewer:**\n\n_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._\n\n**Response:**\n\nThank you for the reference; it brings to mind some very interesting starting points for future work and seems related to ideas we’ve been thinking about as well. The divide-and-conquer or “middle-out” approach sounds like an intriguing method for synthesis planning and would likely naturally extend from DESP. Using something like a “cut” to break a synthesis planning task for a particularly complex molecule into subgoals (i.e. by predicting a key intermediate) also intuitively seems like a promising avenue. We will incorporate these general future directions and the reference into **Section A.8**!\n\n---\n\n[1] Luo, S., Gao, W., et al. “Projecting molecules into synthesizable chemical spaces” _ICML_ (2024).\n\n[2] Koziarski, M., et al. \"RGFN: Synthesizable Molecular Generation Using GFlowNets\" _arXiv:2406.08506_ (2024).\n\n[3] Guo, J. & Schwaller, P. \"Directly Optimizing for Synthesizability in Generative Molecular Design using Retrosynthesis Models\" _arXiv:2407.12186v1_ (2024).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4lHVtH1mVN", "reviewer": "Reviewer_pGH2", "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.", "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": "The limitations of the proposed method are discussed fairly clearly in the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper considers an important problem in AI and develops a new more efficient search algorithm to solve it optimally. Specifically, bi-directional search (although a well established search method) appears to be a novel application to retrosynthetic analysis.\n\n- The paper is well written and organised. It is therefore relatively easy to follow. The quality of the presentation is overall quite good.\n\n- The experimental evaluation is sound and covers well most of the prior work in terms of competing algorithms. The results are presented in a relatively clear manner and therefore it is fairly easy to understand the performance gains achieved by the proposed method.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and positive reception of our paper! Addressing your comments:\n\n---\n\n**Reviewer:**\n\n_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._\n\n**Response:**\n\nThis is a great suggestion! We have created such a figure (**Figure 1** in author rebuttal) and will include it in the final version of the paper.\n\n---\n\n**Reviewer:**\n\n_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]?_\n\n**Response:**\n\nThank you for the question. $rn(m|G)$ is actually a quantity directly from the Retro* algorithm of Chen et al. [1]. It represents the “reaction number,” the total estimated cost of synthesizing a particular molecule $m$ based on the current search graph. $dn(m|G)$ is an analogous quantity that we developed in order to incorporate the guidance from the synthetic distance values as well. $rn(m|G)$ is more specifically described in **Section A.2**, and $dn(m|G)$ can be better understood by our explanation in **Section A.5**, as well as the new **Figure 1** we have included in the author rebuttal. We will make sure these quantities are clearly described in the final version of the paper.\n\n---\n\n[1] Chen, B. et al. \"Retro*: Learning Retrosynthetic Planning with Neural Guided A* Search\". _ICML_ (2020).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sQrRzP1B21", "reviewer": "Reviewer_FuFE", "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.", "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.  \n    1. https://www.cs.toronto.edu/~sheila/publications/bai-mci-aim08.pdf\n    2. https://www.sciencedirect.com/science/article/pii/S0004370208001975\n    3. https://cdn.aaai.org/ICAPS/2005/ICAPS05-019.pdf\n\n2. 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?\n\n3. Is starting material-constraints the same as the goal constraints? \n\n4. Can you point to where in the paper you discuss how you learned the goal-conditioned cost network offline (mentioned in the abstract).", "limitations": "Authors discuss limitations and those are not concerning (re societal impact, etc).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper presents a novel idea.\n- The real-world aspect of having constraint is addressed in this paper\n-  Experiments have a clear objective and look sound.", "weaknesses": "- See the questions section.\n- Proof of soundness and completeness of algorithm 1 is missing. In particular, what can be said about the properties of this algorithm? \n- 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and questions, they bring up some interesting discussion points that will help improve our work!\n\n---\n\n**Reviewer:** _Proof of soundness and completeness of algorithm 1..._\n\n**Response:**\n\nWe agree that some detail regarding algorithm 1 is missing and will add the following justification in the final manuscript.\n\nThe purpose of Algorithm 1 is to add the $N$ “best” forward reactions to add to the search graph given a particular reactant $m_1$ from which we want to eventually reach some target molecule $m_2$. If we had access to the complete reaction graph $\\mathcal{G}$, we could find the $N$ reactions that use $m_1$ as a reactant that minimize the total cost to reach $m_2$ in $\\mathcal{G}$. Thus, $f_t(m_1, m_2)$ would yield the set of templates corresponding to these $N$ reactions, and for each of the bidirectional templates $t_i$, $f_b(m_1, m_2, t_i)$ would yield the missing reactant $m_{3,i}$ in the reaction. We instead approximate $\\mathcal{G}$ with the partial reaction graph $G_{\\text{FWD}}$ and train neural networks to predict the best templates and building blocks using the reactions in $G_{\\text{FWD}}$. Thus, to perform a forward expansion in DESP on $m_1$ conditioned on $m_2$, we approximate $f_t$ with a trained forward template model and return the $N$ most likely templates to apply to $m_1$. For each template, if the template is unimolecular, we can simply apply the template $m_1$ and add the reaction to the search graph. For bimolecular templates, we instead use a building block model that approximates $f_b$ to predict the missing building block $m_3$. The model predicts the fingerprint of $m_3$, and we perform a $k$-nearest neighbors search on our building block set $\\mathcal{B}$ to retrieve the $k$ best building blocks to use as $m_3$. Finally, we apply the bimolecular template to $m_2$ and each retrieved building block and add the reaction to the search graph. \n\nThe forward expansion algorithm relies on some limiting assumptions, which we touch on in the paper. Particularly, we ignore the existence of $\\geq$3-component reactions, and assume that the missing reactant $m_3$ is a member of $\\mathcal{B}$, thus precluding “convergent” bottom-up synthesis plans. \n\n---\n\n**Reviewer:** _...I fail to see its broader impact to the community..._\n\n**Response:**\n\nWe would argue that a novel contribution to synthesis planning is in itself a contribution of broad significance to the scientific community. Synthesis planning is a crucial component in the formulation and discovery of most of our medicines, as well as desirable agrochemicals and materials used across a wide swath of industries. Anecdotally, we have received interest in the algorithm from chemists, chemical engineers, and pharmaceutical companies. \n\n---\n\n**Reviewer:** _Why Bi-directional search?..._\n\n**Response:**\n\nThank you for the constructive feedback and references! Our implementations of the unidirectional search baselines (including our top-down guided ablation, Retro* + D) do define the starting material goal constraints, and we posited that bidirectional search may be well suited for affording efficiency gains on this task. We find that DESP outperforms all baseline methods on the task, and the ablation study demonstrates that bidirectional search contributes to the improved performance. We believe that these results provide a solid empirical case for the utility of bidirectional search in synthesis planning. Though there are many exciting avenues for improvement of either unidirectional or bidirectional search with preferences and/or constraints, we view such explorations as out of the scope of this paper.\n\n---\n\n**Reviewer:** _Could there be multiple solutions..._\n\n**Response:**\n\nThank you for raising this question. For a given target, it is essentially guaranteed that there are many solutions to the general synthesis planning problem. In spite of this, the problem is intractable for many targets without the use of ML or heuristics to prune the search space, so we frame the problem as efficiently finding _some_ solution rather than finding the optimal solution. In any case, knowing that each reaction step is costly in the real world motivates our evaluation in **Table 3** of average number of reaction steps as an indicator of quality / cost. Our heuristic cost networks are also trained with this notion of cost in mind--the training labels correspond to the optimal number of reaction steps (to reach the specified goal molecule) based on the reaction corpus. \n\nA limitation of DESP is that the first route found is not necessarily the cost-optimal route. First, each end of our search is a variant of Retro*. As proven in [1], the unidirectional search only guarantees an optimal solution on termination with admissible heuristics, which our neural networks do not provide. Second, even with an admissible heuristic, bidirectional A* search does not guarantee optimality upon meeting [2].\n\nWe emphasize that chemists generally care more about obtaining multiple reasonable routes quickly than obtaining the theoretically optimal route, and our evaluations are designed accordingly. Nevertheless, we will summarize the discussed limitations and outlook in our final manuscript.\n\n---\n\n**Reviewer:** _Is starting material-constraints the same as the goal constraints?_\n\n**Response:**\nYes, thank you for raising this question; we will make an effort to be more clear / consistent about such terminology in the final version.\n\n---\n\n**Reviewer:** _Can you point to where in the paper you discuss how you learned the goal-conditioned cost network offline..._\n\n**Response:**\n\n**Section 3.4** discusses the high level procedure and loss function, while details (including **Figure 5**) can be found in **Section A.4**.\n\n---\n\n[1] Chen, B. et al. \"Retro*: Learning Retrosynthetic Planning with Neural Guided A* Search\". _ICML_ (2020).\n\n[2] Kaindl & Kainz. \"Bidirectional Heuristic Search Reconsidered\". _JAIR_ (1997).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their thoughtful feedback and comments. We have addressed stated weaknesses, questions, and comments in the individual rebuttals. We also include a single page PDF containing additional tables and a figure as referenced in the rebuttals.

Meta-review: 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.
Decision: Accept (spotlight)