Retro-fallback: retrosynthetic planning in an uncertain world
Authors: Austin Tripp
Krzysztof Maziarz
Sarah Lewis
Marwin Segler
José Miguel Hernández-Lobato
Venue: ICLR 2024 poster (2024)
Keywords: Retrosynthesis
planning
chemistry
search
Primary area: applications to physical sciences (physics, chemistry, biology, etc.)
TL;DR: We propose an algorithm to produce multiple retrosynthesis plans whose real-life outcomes are uncorrelated

Abstract: Retrosynthesis is the task of planning a series of chemical reactions to create a desired molecule from simpler, buyable molecules. While previous works have proposed algorithms to find optimal solutions for a range of metrics (e.g. shortest, lowest-cost), these works generally overlook the fact that we have imperfect knowledge of the space of possible reactions, meaning plans created by algorithms may not work in a laboratory. In this paper we propose a novel formulation of retrosynthesis in terms of stochastic processes to account for this uncertainty. We then propose a novel greedy algorithm called retro-fallback which maximizes the probability that at least one synthesis plan can be executed in the lab. Using in-silico benchmarks we demonstrate that retro-fallback generally produces better sets of synthesis plans than the popular MCTS and retro* algorithms.

Published as a conference paper at ICLR 2024
RETRO-FALLBACK: RETROSYNTHETIC PLANNING IN AN UNCERTAIN WORLD
Austin Tripp' 1M Krzysztof Maziarz
Sarah Lewis²
Marwin Segler? José Miguel Hernández-Lobato
Uniiversity Cambridge "Microsoft Research AI4Science {ajt212, jmh2 ac uk
(krmaziaz, swrahlewwaaaaaeeeaaeeaeee w marwinsegler) @mi crwsoft. com
ABSTRACT
Retrosynthesis is the task of planning a series of chemical reactions to create a desired molecule from simpler, buyable molecules. While previous works have proposed algorithms to find optimal solutions for a range of metrics (e.g. short- est, lowest-cost), these works generally overlook the fact that have imperfect knowledge of the space of possible reactions, meaning plans created by algorithms may not work in laboratory. In this paper we propose novel formulation of ret- rosynthesis in terms of stochastic processes to account for this uncertainty. We then propose a novel greedy algorithm called etro-fallback which maximizes the probability that at least one synthesis plan can be executed in the lab. Using in- silico benchmarks we demonstrate that retro-fallback generally produces better sets of synthesis plans than the popular MCTS and retro algorithms.
INTRODUCTION
Retrosynthesis (planning the synthesis of organic molecules via series of chemical reactions) is common task chemistry with a long history of automation (Vleduts) 1963; Corey & Wipke 1969).
Although the combinatorially large search space of chemical reactions makes naive brute-force methods ineffective, recently significant progress has been made by developing modern machine- learning based search algorithms for retrosynthesis Stanley & Segler] 2023). However, there remain obstacles to translating the output of retrosynthesis algorithms into real-world syntheses. One significant issue is that these algorithms have imperfect knowledge of the space of chemical reactions. Because the underlying physics of chemical reactions cannot be efficiently simulated, retrosynthesis algorithms typically rely on data-driven reaction pre- diction models which can "hallucinate" unrealistic or otherwise infeasible reactions (Zhong et al., 2023). This results in synthesis plans which cannot actually be executed.
Kalthoff et al.) 2020; Tu et al. 2023]
Although future advances in modelling may reduce the prevalence of infeasible reactions, we think it is unlikely that they will ever be eliminated entirely, as even the plans of expert chemists do not always work on the first try. One possible workaround to failing plans is to produce multiple syn- thesis plans instead of just a single one: the other plans can act as backup plans in case the primary plan fails. Although existing algorithms may find multiple synthesis plans, they are generally not designed to do so, and there is no reason to expect the plans found will be suitable as backup plans (e.g. they may share steps with the primary plan and thereby also share the same failure points).
In this paper, we present several advancements towards retrosynthesis with backup plans. First, in section 3 we explain how uncertainty about whether synthesis plan will work in the lab can be quantified with stochastic processes. We then propose an evaluation metric called successful synthesis probability (SSP) which quantifies the probability that least one synthesis plan found by an algorithm will work. This naturally captures the idea of producing backup plans. Next, present novel search algorithm called retro-fallback which greedily optimizes
in section
Work done partly during intersship Microsoft Research A14Science

---

Published as a conference paper at ICLR 2024
SSP. Finally, in section demonstrate quantitatively that retro- farl-ff outperforms existing algorithms on several in-silico benchmarks. Together, we believe these contributions form a notable advancement towards translating results from retrosynthesis algorithms into the lab.
2 BACKGROUND: STANDARD FORMULATION OF RETROSYNTHESIS
Let M denote the space of molecules, and R. denote the space of single-product reactions which transform set of reactant molecules in 2M into a product molecule in M. The set of reactions which produce given molecule is given by a backward reaction model B .M + 2 B can be used to define an (implicit) reaction graph 9 with nodes for each molecule and each reaction, and edges linking molecules to reactions which involve them. Figure T illustrates a small example graph. Note that by convention the arrows are drawn backwards (from products towards reactants). This kind of graph is sometimes called an AND/OR graph (see Appendix B for details).
A synthesis plan for a molecule m is sequence of chemical reactions which produces m as the fi- nal product. Synthesis plans usually form trees T S G (more generally directed acyelic subgraphs), wherein each molecule produced by at most one reaction. The set of all synthesis plans in G which produce molecule is denoted P (G). Figure Db provides example (sce Appendix B.2 for a detailed definition). Not all synthesis plans are cqually useful however. Most importantly, for a synthesis plan to actually be executed by chemist the starting molecules must all be bought. Typ- ically this is formalized as requiring all starting molecules to be contained in an inventory I S M (although will propose alternative formulation in section B3. It is also desirable for synthesis plans to have low cost, fewer steps, and reactions which are easier to perform.
In retrosynthesis, one usually seeks create synthesis plans for specific larget molecule m.- Typ- ically this is formulated as a search problem over G. Various search algorithms have been proposed which, at a high level, all behave similarly. First, they initialize an explicit subgraph G C with G + }. Nodes whose children have not been added to G' form the frontier F(G"). Then, at each iteration they select a frontier molecule ma()) E F('') (necessarily m, on the first iteration), query B to find reactions which produce m(j), then add these reactions and their corresponding reactant molecules to the explicit graph G'. This process is called expansion. and is illustrated for me in Figure L.. Search continues until a suitable synthesis plan is found or until the computational budget is exhausted. Afterwards, synthesis plans can be enumerated from g'.
The most popular retrosynthesis search algorithms compute some sort of metric of synthesis plan quality, and use a search heuristic to guide the search towards high-quality synthesis plans. For example, Monte Carlo Tree Search (MCTS) searches for synthesis plans which maximize an ar- bitrary scalar reward function (Segler et al. 2018). Retro is a best-first search algorithm to find minimum-cost synthesis plans, where the cost of a synthesis plan is defined as the sum of costs for each reaction and each starting molecule (Chen et al. 2220)). In both algorithms, frontier nodes are chosen using the heuristic to estimate the reward (or cost) which could be achieved upon expansion. We introduce these algorithms more extensively in Appendix E
T1
m
T2
F'
m
ma
mc
m
T3
m+
mn
m+
T4
m+
F2
mc
expansion of ml
TM
g
b) Pmn. (g")
Figure 1: a) graph g' with (backward) reactions m, = my + my (r1). m. = my + M. + ma (r2),
and m, + m. (r3). Dashed box illustrates expansion of mc- b) All synthesis plans in P... (g').
2

---

Published as a conference paper at ICLR 2024
3 REFORMULATING RETROSYNTHESIS WITH UNCERTAINTY
The "standard" formulation of retrosynthesis presented in section 2 requires knowledge of which reactions are possible (encoded by the backward reaction model 13 and which molecules are pur- chasable (encoded by the inventory Z). In reality, neither of these things are perfectly known. As mentioned in the introduction, predicting the outcome of chemical reactions is difficult even for experts, and machine learning models for B can "hallucinate" unrealistic reactions. Perhaps surpris- ingly, is also not totally clear which molecules can be bought. Things like shipping delays mean you might not always receive molecules which you order. However, many companies now advertise large "virtual libraries" with billions of molecules which they believe they can synthesize upon re- This section presents our first main contribution to account for
quest, but not with 100% reliability | this: a novel formulation of retrosynthesis which explicitly represents uncertainty.
3.1 STOCHASTIC PROCESSES FOR "FEASIBILITY" AND "BUYABILITY"
There are many reasons why chemists may consider a reaction unsuccessful, ranging from having low yield to producing the wrong product altogether. Similarly, "unsuccessfully" buying a molecule could indicate anything from a prohibitively high cost to the molecule not being delivered. In either case, for simplicity we propose to collapse this nuance into a binary outcome: reactions are either feasible infeasible, and molecules either buyable not. We therefore postulate the existence of an unknown "feasibility" function f R + {0, 1} and "buyability" function b" : 1}.
Uncertainty about f* and by can be represented by stochastic processes (essentially distributions over functions). We define feasibility model E, to be a binary stochastic process over R, and define buyability model &a to be binary stochastic process over M. This formulation is very general: E and & not only represent belief's of I' (r) = 1] and P [b* (m) = 1] for all molecules m and reactions r, but also allows correlations between feasibilities and buyabilities to be modelled.
Although this formalism may seem esoteric, it is possible to re-cast almost all existing approaches to reaction prediction as stochastic processes. Any model which implicitly assigns probability to each reaction (e.g. the softmax outputs of a neural network) can be trivially converted into a stochastic process by assuming that all outcomes are independent. Correlations can be induced via Bayesian inference over the model's parameters (MacKay 1992) or using a non-parametric model like a Gaussian process (Williams & Rasmussen (006). Importantly however, is not at all clear how to produce realistic models & and &s. Intuitively, producing such models is at least as challenging as predicting reaction outcomes without uncertainty estimates, which is itself an active (and challenging) research area. Therefore, will generally discuss Ey/Eb in model-agnostic way.
3.2 NEW EVALUATION METRIC: SUCCESSFUL SYNTHESIS PROBABILITY (SSP)
Given f and b, a synthesis plan T is successful if all its reactions r are feasible (f(r) = 1) and all its starting molecules m are buyable (b(m)= = 1). We formalize this with the function
oT: (T: = {
S()) = e T, 6(m) = 1 and Vm E F(T)
(1)
0
otherwise
Finding successful synthesis plans are unknown, we can at best search for synthesis plans with high probability of being successful. Given a set of synthesis plans T, we define the successful synthesis probability (SSP) as:
natural goal of retrosynthesis. Of course, because f and b
SSP(T: Eb) = Py [ E T with o f.b) = =1]
Given just a single plan T. S) = E [T[ f.b) and represents the probability that T is successful, which will hereafter refer as the success probability of T. When T contains multiple synthesis plans, then SSP quantifies the probability that any of these synthesis plans is successful. We argue that SSP is good evaluation metric for the synthesis plans produced by retrosynthesis search algorithms. It simultancously captures the goals of producing synthesis plans with high success probability and producing "backup" plans which could succeed if the primary synthesis plan does not. Note that by definition, SSP is non-decreasing with respect to T, implying that an algorithm will never be penalized for producing additional synthesis plans.
For example, Fnamine a popular supplier, only claims that 80% of its virtual "REAL" lihrary can he made
3

---

Published as a conference paper at ICLR 2024
3.3 EFFICIENTLY ESTIMATING SSP FOR ALL SYNTHESIS PLANS IN Pm., (g')
Recall from section 2 that many retrosynthesis search algorithms do not directly output synthesis plans: they produce search graph g' which (implicitly) contains set of synthesis plans Pm, (9"). Therefore, it is natural to calculate the SSP of the entire set Pm. (g"). However, this set may be combinatorially large, making calculating SSP by enumerating Pm. (9') intractable. Instead, we propose a method to estimate SSP using functions sampled from ε, and Ço.
Let s(n; (, .MUT R + {0, 1} define the success of node synthesis plan in G contains nt (we write s(n) when G¹, ff, b are clear from context). s(n) will satisfy
G: whether any successful
s(n; G" f.b)
(A)
(TT" (B) ff
T E
arg max o ff TEP) NET
(3)
where P.(g)) U UE Pm (9') is the set of all synthesis plans for all molecules in G'. Equality (A) follows directly from the definition above, and equality (B) holds because 7 would still satisfy the arg max if nodes not in T were pruned from G'. Let C'hg- (n)) denote the children of node n. For reaction r E G' to succeed, it must be feasible (f(r) = 11) and have all its reactant molecules m' E (r) succeed. Conversely, a molecule E g' will succeed if it is buyable (b(m) = 1) or any reaction producing m succeeds. This suggests s(-) will satisfy the recursive equations
s(m; g'. = max ((m),
max s(r: s(r: f. (mCh
(4)
(r: = f(r)
II mEChgr(r)
s(m; D'n f.b).
(5)
SSP can then be estimated by averaging s(m.) over k ii.dd functions sampled from fy and Es:
SSP(Pm, (g'); (A) Py-ey Ae [s(m,; J,b) = 1]
s s(m;; G', G',k,,b))
(6)
Note that equality (A) above follows directly from equations and 3 The existence of such re- cursive equations suggests that s(.) could be efficiently computed for all nodes in g' in polynomial time using dynamic programming (we discuss this further in Appendix [D2)), allowing an overall polynomial time estimate of SSP. That being said, it is still only an estimate. Unfortunately, we able to prove that an exact calculation is generally intractable.
Theorem 3.1. Unless P NP, there does not exist algorithm compute (P. (G'); Ey. En) for arbitrary &f. Ea whose time complexity grows polynomially with the number of nodes in G'
The proof is given in Appendix D.I We therefore conclude that estimating SSP using equation 6 is the best realistic option given limited computational resources.
4
RETRO-FALLBACK: A GREEDY ALGORITHM TO MAXIMIZE SSP
4.1 INGREDIENTS FOR AN INFORMED, GREEDY SEARCH ALGORITIM
Intuitively. a greedy search algorithm would expand molecules in F(g') which are predicted to improve SSP. Given that calculating SSP exactly is intractable, calculating potential changes is likely to be intractable well. Therefore, we will estimate SSP changes by averaging over samples from Ey and &s. and will consider how expansion might change s(m,; G' b)b) for fixed samples f, b.
Specifically, we consider the effect of simultaneously expanding every frontier molecule on fixed synthesis plan T E P We represent the hypothetical effect of such an expansion with a random function er .M + t0, (0,1), 1}. where eT (m) = 1 implies that expanding m produces new successful synthesis plan for m. We assume the value of eT is independently distributed for every molecule, with probabilities given by a search heuristic function h M + J0, 1]
(h(m) to
m E FT m F(g')
IP Per (m)(m) 1] [0
We do not consider expanding just single node because, for reaction with multiple non- non-buyable reactant molecules in F(G'), expanding just one reactant will never produce new successful synthesis plan.
4

---

Published as a conference paper at ICLR 2024
The effect of this expansion the success of T is given by o': PG) - {0, 1), defined
d((:ff,berr) = (
f(r) = Vr T and (b(m) (r 1) Vm E F(T).
(8)
otherwise
Equation 8 for o' is almost identical to equation 1 for a. The key difference (highlighted) is that T can be successful if starting molecule is not buyable (6(m) 0) but has instead had ey (m) 1.
Recalling that er is a random function, we define o' Pg' ~ [0, 1] as
o' d'(Tf,,b,
Eey [o (T:
namely the probability that a synthesis plan T will be successful upon expansion A natural choice for a greedy algorithm could be to expand frontier nodes on synthesis plans 7 with high d b, h). However, not all synthesis plans contain frontier nodes (c.g. plan T₁ in Figure [p) or
produce m, To select frontier nodes for expansion, we define the function p: MMMRR + [0, by
max pl; G' b,b, TEP.. (0'): NET
d'
E
(10)
For m F(G'). ((m) represents the highest estimated success probability of all synthesis plans for m, which also contain m (conditioned on particular f. b). Therefore, a greedy algorithm could sensibly expand frontier molecules m with maximal p(m).
Unfortunately, the combinatorially large number of synthesis plans in graph G' makes evaluating أ potentially infeasible. To circumvent this, we assume that no synthesis plan in G' uses the same molecule in two separate reactions, making all synthesis plans trees (we will revisit this assumption later). This assumption guarantees that the outcomes from different branches of synthesis plan will always be independent. Then, to help efficiently compute P, we will define the function
max 5' d' (T:f.b, (n; G', f.b,b), TEP. WET
(11)
for every node n E g'. v is essentially a less constrained version of p. The key difference in their definitions is that & maximizes over all synthesis plans containing n, including plans which do not produce m.- The independence assumption above means that & has a recursively-dffined analytic solution (' J,b,h) M R - [0, given by the equations
"'m; b, = max [b(m), M(m)]
m E F(g")
max [mm), max,eChgr(m) (r::' S.,,) m $ F(g') , (12)
Mr::''J.b. = f(r) (EChggrr)
II
(mm; (.,,,',.,b,h....
(13)
Details of this solution are presented in Appendix C.I expected success value for upon expansion." In fact, the relationship between e and of is exactly analogous to the relationship between and a in equation 3
(n) can be roughly interpreted as "the best
To compute ツ. first note that p(m..) (mm)). ). as for m. the constraints in equations 10 and 11 are equivalent. Second, because of the independence assumption above, the best synthesis plan contain- ing both a node n and its parent n'' can be created by taking an optimal synthesis plan for n'' (which may or may not contain 11), removing the part "below" n', and adding in (unconstrained) optimal plan for n. Letting (-) denote a node's parents 4 under this assumption has recursively-
defined analytic solution p'=:'', f. b, MUR + [0, 1] defined as
(mmm G.
m is target molecule m. all other m
pmm; I'
(14)
maxFePagr(m)) p(r; O(r:'',A f.,b,b,
=0 (r: f. f,b,h)=0
V'rg (.b.K) plrig',f.6,h. g0 (0mm 39" J.b.h)
(r: (r. 0, (r))(r) (15)
'The dependence on because it defines the distribution of er equation g 'Recall that because we consider only single-product reactions, all reaction nodes will have exactly one parent, making equation 15 well-defined.
5

---

Published as a conference paper at ICLR 2024
Details of this solution are presented in Appendix C.1 Like s(-). 1 and have recursive definitions, and can therefore be calculated with dynamic programming techniques. Since 1 depends on a node's 's children, it can generally be calculated "bottom-up", while p can be calculated "top-down" because depends on a node's parents. We discuss details of computing s and in Appendix provide full worked-through example in Appendix CC22
C.1 and
However, in deriving 1 and p we assumed that all synthesis plans T E (g') were trees. In prac- tice, this assumption may not hold (see Figure C.I for an example). If this assumption is violated, vi and can both still be calculated, but will effectively double-count molecules which occur multiple times in synthesis plan. and therefore not equal v and p. This is well-known issue in AND/OR graphs: for example, Nilsson 19822 page 102) describes the essentially same issue when calculat- ing minimum cost synthesis plans. Ultimately we will simply accept this and use thlp instead of Vll despite their less principled interpretation, chiefly because the recursive definitions of shp are amenable to efficient computation. Synthesis plans which use the same molecule twice are unusual in chemistry; therefore we do not expect this substitution to be problematic in practice.
4.2 RETRO-FALLBACK: FULL GREEDY ALGORITHM
Recall our original goal at the start of section 4.1 to estimate how expansion might affect SSP. We considered single sample ʃ ~ Ey and b Eb. and developed the function p. which for each frontier molecule m E F(g") gives the best estimated synthesis plan for m, if m is expanded (simultaneously along with other frontier molecules will now use to construct a full algorithm.
optimally chosen synthesis plan). We
Expanding a frontier molecule can improve SSP if, for samples f and b where ((m.;g',f.. O, the expansion changes this to 1. In this scenario, expanding a frontier molecule m E arg maX"))()") p(m; G', f b, h) is prudent choice, as it lies on synthesis plan with the high- est probability of "flipping" s(m_; J'. f.b) to 1. In contrast, because s(-) will never decrease as nodes are added, if g = then it does not matter which molecule is expanded. There- fore, when aggregating over samples of f and b to decide which molecules to expand to improve SSP, we will consider the value of p only in cases when s(m,; G', 6) 0.
For our greedy algorithm, we propose to simply expand the molecule with the highest expected improvement of SSP. Letting 1()) be the indicator function, this is a molecule m E F(G') which maximizes
am;; G', Ey,, h)) By [1. fbb)== [o(m; f', A)]]
(16)
In practice, a would be estimated from a finite number of samples from ε and &.- Using p to select single molecule may seem odd, especially because p is defined a hypothetical outcome of simul- taneously expanding multiple nodes. However, note that in principle there is nothing problematic about expanding these nodes one at time.
We call our entire algorithm retro-fallback (from "retrosynthesis with fallback plans") and state it explicitly in Algorithm|] [ The sections are colour-coded for clarity. After initializing G', the algo- rithm performs L iterations of expansion (although this termination condition could be changed as needed). In each iteration, first the values of s, v, and p are computed for each sample of ʃ and b Next, the algorithm checks whether there are no frontier nodes or whether the estimated SSP 100%, and if so terminates (both of these conditions mean no further improvement is possible). Finally, a frontier node maximizing (16) is selected and expanded. Of course, practical imple- mentation of retro-fallback may look slightly different from Algorithm [ We refer the reader to Appendix [oor further discussion about the design and implementation of cello-fallback.
5 RELATED WORK
Retro-fallbaci is most comparable with other retrosynthesis search algorithms including MCTS (Segler et al., 2018). retro" (Chen et al. 2020), and proof number search (Heifets Jurisica 2012] Kishimoto et al. 2019). At high level these algorithms are all similar: they use a heuristic to
"This order is chosen because depends only f & b, ab depends and p depends t.. Because the optimal algorithm compute s, 1h may depend on G', we only specify this computation generically.

---

Published as a conference paper at ICLR 2024
Algorithm Retro-fallback algorithm 4.2)
Require: target molecule m., max iterations backward reaction model B, search heuristic h Require: samples .1.....fa ~ Eg, bi...., G' t- {m..}
......,.. by C6
2: for in 1...., L do
3: for j 1..... k do
4: Compute s( G', Jj. by) for all nodes using equations
5: Compute ((: / fz, by, h) for all nodes using equations
13
6: Compute p(=: JJ. bj, h) for all nodes using equations
7:
end for
8:
Terminate early if [F(g)) = 0 OR s(m,; 9 [5, j
9: mi( f arg FaX a(m; G', Ey, Eo. h) (equation 16
breaking ties arbitrarily)
10: Add all reactions and molecules from (m) to g'
11:
end for
12:
return g'
guide the construction of explicit search graph. However, previous algorithms may struggle to maximize SSP because their internal objectives consider only individual synthesis plans, while SSP depends multiple synthesis plans simultaneously. In Appendix [2.2 we argue that for most algo- rithms the best proxy for SSP is the success probability of individual synthesis plans, but illustrate in Appendix E.3 that this objective does not always align with SSP. In contrast, retro-fallback is specifically designed to maximize SSP.
Mechanistically, retro- fatoo-falbbcck most closely resembles retro* (Chen et al. 2020). which a variant of the older A algorithm (Chang & Slagle 1971 Martelli & Montanari 1978] Nilsson [982] Mahanti & Bagchi] 1985). Both retro and falleck perform a bottom-up and top-down update to determine the value of each potential action, then select actions greedily. In fact, retro-fallback's updates have minimizaiioonnn interpretation, presented in Appendix CCI.4. The key difference between the algorithms is the node selection step: retro* considers just single cost for each node, while retro-fallben fallbaf aggregates over a vector of samples to directly optimize SSP.
Lastly, we briefly comment on several research topics which are only tangentially related (deferring fuller coverage to Appendix F). Works proposing search heuristics for retrosynthesis search algo- rithms (F.I) complement rather than compete with our work: such heuristics could also be applied to retro-fallback. Generative models to produce synthesis plans (F.2) effectively also function as heuristics. Methods to predict individual chemical reactions sometimes also referred to "ret- rosynthesis models" (F.)) but solve a different problem than multi-step synthesis. Finally, other works have considered generally planning in stochastic graphs (F5)) but typically in scenario where the agent is embedded in the graph.
6 EXPERIMENTS
In this section we evaluate retro-fallback experimentally. The key question we seek to answer is whether retro-fallback does indeed maximize SSP more effectively than existing algorithms. We present additional results and explain details of the setup experimental in Appendix G
6.1 EXPERIMENT SETUP
We have based our experiment design on the USPTO benchmark from Chen et al. (2020). which has been widely used to evaluate multi-step retrosynthesis algorithms. However, because this benchmark does not include fcasibility or buyability model we have made some adaptations to make it suitable for our problem setting. Importantly, because we do not know what the "best" feasibility model is, instead test multiple feasibility models in the hope that the conclusions of our experiments could potentially generalize to future, more advanced feasibility models. We summarize the setup below and refer the reader Appendix G. for further details.
We base all of our feasibility models on the pre-trained template classifier from Chen et al. (2020) restricted the top-50 templates. We vary feasibility model across two axes: the marginal fea-
7

---

Published as a conference paper at ICLR 2024
& const. GP
y const., ind.
& rank, GP
E rank, ind.
0.6
mean SSP
0.4
0.2
0.0
10
10
10"
10
10
10"
10"
num. calls to B
num. calls to B
num. calls to B
num. calls to B
retro-fallbuck
hreadth-firs
retro
MCTS
Mean SSP across all 190 test molecules vs. time using the SA score heuristic. 3 trials are done for each molecule. Solid lines are sample means (averaged across molecules), and error bars represent standard errors. "ind." means "independent".
Figure 2:
sibility assigned each reaction and the correlation between feasibility outcomes. Marginally, we consider a constant value of 0.5, and value which starts at 0.75 and decreases with the rank of the reaction in the template classifier's output. For correlations, we consider all outcomes being inde- pendent or determined by latent GP model which positively correlates similar reactions. Details of these models are given in Appendix [G..2] Analogous to Chen et al. (2020), we create buyability model based on the eMolecules library which designates only chemicals shipped within 10 business days as 100% buyable. See Appendix G.1.3 for details.
We compare retro-fallback to breadth-first search (an uninformed search algorithm) and the heuristic-guided algorithms retro* (Chen et al.) 2020) and MCTS (Segler et al.) 2018 Genheden et al. 20200] Coley et al.) 2019b). All algorithms were implemented using the SYNTHESEUS library (Maziarz et al. 2023) and run with a fixed budget of calls to B. MCTS and retro* were configured to maximize SSP by replacing costs rewards from the backward reaction model B with quantities derived from y and & (see Appendices E.2
for details). However, the presence of heuris- ties makes comparing algorithms difficult. Because the choice of heuristic will strongly influence an algorithm's 's behaviour, we tried to use similar heuristics for all algorithms to ensure a meaningful comparison. Specifically, we tested an optimistic heuristic (which gives the best possible value for each frontier node) and a heuristic based on the synthetic accessibility (SA) score (Ertl & Schuf- fenhauer 2009), which has been shown to good heuristic for retrosynthesis in practice despite its simplicity (Skoraczyáski et al. 2023). ). The SA score heuristic was minimally adapted for each algorithm to roughly have the same interpretation (see Appendix G.1.6 for details).
We tested all algorithms the set of 190 "hard" molecules from Chen et al. (2020). which do not have straightforward synthesis plans. Our primary evaluation metric is the SSP values estimated with & = 10 100 samples, averaged over all test molecules.
6.2 How EFFECTIVE IS
MAXIMIZING SSP?
Figure plots the average SSP for all test molecules as a function of the number of calls to the reac- tion model B using the SA score heuristic. Retro-fallback clearly outperforms the other algorithms in all scenarios by a significant margin. The difference is particularly large for the feasibility models with no correlations between reactions ("ind."). We suspect this is because the reaction model B tends to output many similar reactions, which can be used to form backup plans when feasibility outcomes are independent. Retro-fallback will naturally be steered towards these plans. However, when GP-induced correlations are introduced, these backup plans disappear (or become less effec- tive), since similar reactions will likely both be feasible or both be infeasible. The same trends are visible when using the optimistic heuristic (Figure G.4 and on test set of easier molecules (Fig- ure G.5) Overall, this result shows us what we expect: that retro-fallback maximizes the metric was specifically designed to maximize more effectively than baseline algorithms.
We investigate the origin of these performance differences in Appendix G.2. plotting SSP over time for a small selection of molecules (repeated over several trials). It appears that, rather than retro-
8

---

was more effective at Published as a conference paper at ICLR 2024
fallback being consistently little bit better, the performance gap is driven by a larger difference for a small number of molecules. This is actually not surprising: the advantage of different approaches will vary depending the graph, and for some graphs finding individual feasible plans is probably a promising strategy.
A natural follow-up question is whether retro-fallbas also performs well by metrics other than SSP. In Figures G.I) we plot the highest success probability of any individual synthesis plan found, plus two metrics frequently used by previous papers: the fraction of molecules with any synthesis plan (called "fraction solved" in prior works) and the length of the shortest synthesis plan found (a proxy for quality). The SSP of the single best plan is generally similar for all algorithms. This suggests that in general all algorithms find similar "best" plans, and retro-fallback 's extra success comes from finding more effective "backup" plans. Retro-fallback seems slightly better than other algorithms in terms of fraction solved and similar to other algorithms in terms of shortest plan length (although retro* is better in some cases). Finally, Appendix [.2.33 shows that retro-fallback is able to find synthesis plans which use the same starting molecules real-world syntheses: metric proposed by Liu et al. (2023)) Overall, these results suggest that retro-fallback also an effective search algorithm if metrics from past papers which do not account for uncertainty are used.
6.3 SPEED AND VARIABILITY RETRO-FALLBACK
First we consider the speed of retro-fallback. Retro-fallback requires calculating s, v and for every node at every iteration. The complexity of this calculation could scale linearly with the number of nodes in the graph (which we denote (g')), or potentially sub-linearly if the s/p/p values for many nodes not change every iteration. Therefore, from this step we would expect a time complexity which is between linear and quadratic in [9" However, retro-fallback also requires sampling / and b for all nodes created during an expansion: a process which will scale as (1) for independent models and O((G')²) for GP-correlated models. This yields overall ((Ig")) ((((") complexity from the sampling step. Figure G. 12 plots the empirical scaling for the experiments from the previous section, and suggests overall scaling between between different feasibility models and heuristics.
(-(g") with considerable variation
To study the effect of the number of samples io from ε, and &o. run retro-fallback 10 times on a sub-sample of 25 molecules with a variety of different sample sizes. Figure [G13 shows that as lt decreases, the mean SSP value achieved by retro-fallback decreases and the variance of SSP increases. This is not surprising, since when the number of samples is small the internal estimates of SSP used by retro-fallback deviate more from their expected values, enabling suboptimal decisions. Empirically, & > 100 seems sufficient (minimal further improvement is seen for higher k).
7 DISCUSSION, LIMITATIONS, AND FUTURE WORK
In this paper we reformulated retrosynthesis using stochastic processes, presented a novel evaluation metric called "successful synthesis probability" (SSP), and proposed a novel algorithm called retro- fallback which greedily maximizes SSP. In our experiments, maximizing SSP than previously-proposed algorithms.
Our work has some important limitations. Conceptually, chemists may also care about the length or quality of synthesis plans, and may only be willing consider limited number of backup plans. These considerations do not fit into our formalism. Practically, algorithms and may not scale as well. We discuss these limitations further in Appendix
is slower than other
The most important direction for future work is creating better models of reaction feasibility, as without high-quality models the estimates of SSP are not meaningful. We see collaborations with domain experts as the best route to achieve this. Since retro-fallback uses search heuristic, learning this heuristic using the results of past searches ("self-play") would likely improve performance. We elaborate other potential directions for future work in Appendix [
Overall, even though reaction outcomes is least step in the right direction, and hope it inspires further work in this area.
is far from perfect, we believe that modelling uncertainty about

---

Published as a conference paper at ICLR 2024
ETHICS
Our work is foundational algorithm development and we do not see any direct ethical implications. The most likely use case for our algorithm automate the production of synthesis plans in drug discovery, which we hope can aid the development of new medicines. We acknowledge the possi- bility that such algorithms could be used by bad actors develop harmful chemicals. but do see this as a probable outcome: countless harmful chemicals already cxist and can be readily obtained, It therefore hard imagine why bad actors would expend significant effort to develop new harmful chemicals with complicated syntheses.
REPRODUCIBILITY
We aim for high standard of reproducibility in this work. We explicitly state our proposed algo- rithm in the paper (Algorithm D and dedicate Appendix Ci discussing its minor (but still impor- tant) details, including guidance for future implementations (C.5) Proofs of all theorems given in Appendix D The experimental setup is described in more detail in Appendix|G (including hyper- parameters, etc). Code reproduce all experiments is available at: https: / /
Aust wtteiinnreeerreo wawrrroooallaaaaaaaaaaaalaalaall lback-icl
Our code was thoroughly tested with unit tests and builds on libraries which are widely-used, mini- mizing the chance that our results are corrupted by software errors. We include the results generated by our code json format, and also include code to read the results and reproduce the plot from the paper. The inclusion of raw data will freely allow future researchers to perform alternative analyses.
Note that this paper will be kept updated at hatts::/arxiv.oorrabb//// 09270
AUTHOR CONTRIBUTIONS
The original idea of SSP was proposed by Sarah and jointly developed by Sarah, Austin, Krzysztof, and Marwin. Sarah and Austin jointly developed an initial version of retro-fallback for AND/OR trees. Sarah originally proposed an algorithm using samples in a different context. Austin adapted these two algorithms to yield the version of retro-fallback proposed in this paper. Krzysztof pro- posed and proved Theorem 3.1 Writing was done collaboratively but mostly by Austin. All code was written by Austin with helpful code review from Krzysztof. Marwin and José Miguel advised the project. Marwin in particular provided helpful feedback about MCTS estimated fcasibility of chemical reactions from the model. José Miguel provided extensive feedback the algorithm de- tails and the clarity of writing.
ACKNOWLEDGMENTS
Thanks to Katie Collins for proofreading the manuscript and providing helpful feedback. Austin Tripp acknowledges funding via a CT Taylor Cambridge International Scholarship and the Canadian Centennial Scholarship Fund. José Miguel Hemmáneez-Lobato acknowledges support from Turing AI Fellowship under grant EP/V023756/1.
Austin is grateful for the affordable meals (with generous portion sizes) from Queens' College Cam- bridge which greatly expedited the creation this manuscript.
REFERENCES
John Bradshaw, Brooks Paige, Matt J Kusner, Marwin Segler, and José Miguel Hernández-Lobato. A model to search for synthesizable molecules. Advances in Neural Information Processing Systems, 32, 2019.
Note that because algorithms the paper use randomness, re-running code is unlikely to reproduce our exact results.
Beecaus include the exact data, the reproduction of the plots will be exact. We were inspired to include this by the noought-provokiig paper of Hurnel 2023
10

---

Published as a conference paper at ICLR 2024
John Bradshaw, Brooks Paige, Matt J Kusner, Marwin Segler, and José Miguel Hernández-Lobato Barking up the right tree: an approach to search over molecule synthesis dags. Advances in neural information processing systems, 33:6852-6888 2020.
Nathan Brown, Marco Fiscato, Marwin HS Segler, and Alain C Vaucher. Guacamol: benchmarking models for de novo molecular design. Journal of chemical information and modeling, 59(3): 1096-1108, 2019.
Ryan Burnell, Wout Schellaert, John Burden, Tomer D Ullman, Fernando Martinez-Plumma Joshua B Tenenbaum, Danaja Rutar, Lucy G Cheke, Jascha Sohl-Dickstein, Melanic Mitchell, et al. Rethink reporting of evaluation results ai. Science, 380(6641):136-1) 2023.
PP Chakrabarti. Algorithms for searching explicit and/or graphs and their applications problem reduction search. Artificial Intelligence, 65(2):329-345, 1994.
Chin-Liang Chang and James R. Slagle. An admissible and optimal algorithm for searching and/or graphs. Artificial Intelligence, 2(2):117-128, 1971.
Binghong Chen, Chengtao Li, Hanjun Dai, and Le Song. Retro*: learning retrosynthetic planning with neural guided a search. In International Conference Machine Learning, pp. 1608-1616. PMLR, 2020.
Shuan Chen and Yousung Jung. Deep retrosynthetic reaction prediction using local reactivity and global attention. JACS Au, 1(10):1612-1620, 2021.
Connor W Coley, Luke Rogers, William H Green, and Klavs F Jensen. Sescore: synthetic com- plexity learned from reaction corpus. Journal of chemical information and modeling, 58(2): 252-261, 2018.
Connor Coley, William Green, and Klavs F Jensen. Rdchiral: An rdkit wrapper for handling stereochemistry in retrosynthetic template extraction and application. Journal of chemical infor- mation and modeling, 59(6):2529 253222577. 2019a.
Connor W Coley, Dale A Thomas III, Justin AM Lummiss, Jonathan N Jaworski, Christopher P Breen, Victor Schultz, Travis Hart, Joshua S Fishman, Luke Rogers, Hanyu Gao, et al. A robotic platform for flow synthesis of organic compounds informed by ai planning. Science, 365(6453): eaax 1566, 2019b.
Elias James Corey and W Todd Wipke. Computer-asse assisted design of complex organic syntheses: Pathways for molecular synthesis can be devised with computer and equipment for graphical communication. Science, 166(3902):1) 178-199 1969.
Hanjun Dai, Chengtao Li, Connor Coley, Bo Dai, and Le Song. Retrosynthesis prediction with conditional graph logic network. Advances in Neural Information Processing Systems, 32, 2019.
Peter Ertl and Ansgar Schuffenhauer. Estimation of synthetic accessibility score of drug- like molecules based on molecular complexity and fragment contributions. Journal of cheminfor- matics, 1:1-11, 2009.
Wenhao Gao, Rocío Mercado, and Connor W Coley. Amortized tree generation for bottom-up synthesis planning and synthesizable molecular design. In International Conference on Learning Representations, 2021.
Samuel Genheden, Amol Thakkar, Veronika Chadimová, Jean-Louis Reymond, Ola Engkvist, and Esben Bjerrum. Aizynthinnde: fast, robust and flexible open- software for retrosynthetic planning. Journal of cheminformatics, 12(1):70, 2020.
Sai Krishna Gottipati, Boris Sattarov, Sufeng Niu, Yashaswi Pathak, Haoran Wei, Shengchao Liu, Simon Blackburn, Karam Thomas, Connor Coley, Jian Tang, et al. Learning to navigate the synthetically accessible chemical space using reinforcement learning. In International conference machine learning, pp. 3668-3679 PMLR, 2020.

---

Published as a conference paper at ICLR 2024
Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and func- tion using networkx. Technical report, Los Alamos National Lab.(LAN)), Los Alamos, NM (United States), 2008.
Charles R Harris, K Jarrod Millman, Stéfan Van Der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor. Sebastian Berg, Nathaniel J Smith, et al. Array program- ming with numpy. Nature, 585(7825):357-336) 2020.
Abraham Heifets and Igor Jurisica. Construction of new medicines via game proof search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 26, pp. 1564-1570, 2012.
Dušan Hvalica. Best first search algorithm in and/or graphs with cycles. Journal of Algorithms, 21 (1):102-110, 1996. ISSN 0196-6774. doi: https::/doi.org/ 10.g//00.ii 1006/0000..1990000 1996..099.
Ross Irwin, Spyridon Dimitriadis, Jiazhen He, and Esben Jannik Bjerrum. Chemformer: pre- trained transformer for computational chemistry. Machine Learning: Science and Technology, (1):015022, 2022.
Pablo Jiménez and Carme Torras. An efficient algorithm for searching implicit and/or graphs with cycles. Artificial Intelligence, 124(1):1-30, 2000.
Richard M. Karp. Reducibility among Combinatorial Problems, pp. 85-103. Springer US, Boston, MA, 1972. ISBN 978-1 177--1-4684-2001-2 doi:
Junsu Kim, Sungsoo Ahn, Hankook Lee, and Jinwoo Shin. Self-improved retrosynthetic planning. In International Conference on Machine Learning, pp. 1498-5545. PMLR, 2021.
Akihiro Kishimoto, Beat Buesser, Bei Chen, and Adi Botea. Depth-first proof-number search with heuristic edge cost and application to chemical synthesis planning. Advances in Neural Informa- fion Processing Systems, 32, 2019.
Greg Landrum, Paolo Tosco, Brian Kelley, Ric, sriniker, gedeck, Riccardo Vianello, David Cos- grove, NadineSchneider, Eisuke Kawashima, Dan N, Andrew Dalke, Gareth Jones, Brian Cole, Matt Swain, Samo Turk, AlexanderSavelyev, Alain Vaucher, Maciej Wójeikowski, Ichiru Take, Daniel Probst, Vincent F. Scalfani, Kazuya Ujihara, guillaume godin, Axel Pahl, Francois Berenger, JLVaro,, jasondbiggs. strets123, and JP. rdkit/rdkit: 2022.09 4 (q3 2022) release, Jan- uary 2023.
Baiqing Li and Hongming Chen. Prediction of compound synthesis accessibility based reaction knowledge graph. Molecules, 27(3):1039, 2022.
Cheng-Hao Liu, Maksym Korablyov, Stanislaw Jastrzebski, Pawet Bondarrzyk-Pruszynnee Yoshua Bengio, and Marwin Segler. Retrognn: fast estimation of synthesizability for virtual screening and de novo design by learning from slow retrosynthesis software. Journal of Chemical Information and Modeling, 62(10):2293- 200000002000000 2022.
Guoqing Liu, Di Xue, Shufang Xie, Yingee Xia, Austin Tripp, Krzysztof Maziarz, Marwin Segler, Tao Qin, Zongzhang Zhang, and Tie-Yan Liu. Retrosynthetic planning with dual value networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.). Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 2023a.
PMLR, 23-29 Jul
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 ret- rosynthetic planning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th Internationaal Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. -2041.22041. PMLR, 23-29 Jul 2023b. URL htl.:ttt::0.. http:///////cceeeeeee /tt.httsss:/ppooceedd
www.sml......///mmmmmmm.mmm ing.. ml www.s/rssseeo..... v22 2222//
html
David JC MacKay, A practical bayesian framework for backpropagation networks. Neural compu- tation, 4(3):488 472, 1992.
12

---

Published as a conference paper at ICLR 2024
A. Mahanti and A. Bagchi. And/or graph heuristic search methods. J. ACM, 32(1):2 51, jan 1985. ISSN 0004-5411.
doi: 10.1145/2455.2455
URL
2459
Alberto Martelli and Ugo Montanari. Optimizing decision trees through heuristically guided search. Communications of the ACM, 21(12):1025-1039 1978.
Krzysztof Maziarz, Austin Tripp. Guoqing Liu, Megan Stanley, Shufang Xie, Piotr Gaiński, Philipp Scidl, and Marwin Segler. Re-evaluating retrosynthesis algorithms with syntheseus. arXiv preprint arXiv:2310.19790 2023.
NJJ. Nilsson. Principles of Artificial Intelligence. Symbolic Computation. Springer Berlin Heidel- berg, 1982. ISBN 97835401 13409.
Christos H Papadimitriou and Mihalis Yannakakis. Shortest paths without map. Theoretical Computer Science, 84(1): 1991.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Judea Pearl. Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley Longman Publishing Co., Inc., 1984.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournaneau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
David Rogers and Mathew Hahn. Extended-commecctitty fingerprints. Journal of chemical informa- tion and modeling, 50(5):742-754 2010.
Mikotaj Sacha, Mikotaj Blaz, Piotr Byrski, Pawel Dabrowski-Tumaann Mikotaj Chrominski, Rafal Loska, Pawel Sonddarcyyk-Puuzynaaee and Stanislaw Jastrzebski. Molecule edit graph attention network: modeling chemical reactions as sequences of graph edits. Journal of Chemical Infor- mation and Modeling, 6773332233-328 3284, 2021.
Nadine Schneider, Daniel Lowe, Roger A Sayle, and Gregory A Landrum. Development of novel fingerprint for chemical reactions and its application to large-scale reaction classification and similarity. Journal of chemical information and modeling. 55(1):39-53, 2015.
Philippe Schwaller, Riccardo Petraglia, Valerio Zullo, Vishnu H Nair, Rico Andreas Haeuselmann, Riccardo Pisoni, Costas Bekas, Anna Iuliano, and Teodoro Laino. Predicting retrosynthetic path- ways using transformer-base models and hyper-graph exploration strategy. Chemical science, 11(12):33163332, 2020.
Marwin HS Segler and Mark P Waller. Neural-symbolic machine learning for retrosynthesis and reaction prediction. Chemistry-A European Journal, 23(25):5966-597) 2017.
Marwin HS Segler, Mike Preuss, and Mark P Waller. Planning chemical syntheses with deep neural networks and symbolic ai. Nature, 555(7698):604--11 2018.
Philipp Seidl, Philipp Renz, Natalia Dyubankova, Paulo Neves, Jonas Verhoeven, Marwin Segler, Jörg K Wegner, Sepp Hochreiter, and Günter Klambauer. Modern hopfield networks for few-and zero-shot reaction template prediction. arXiv preprint 1rXiv:2204.03277 2021.
Ryosuke Shibukawa, Shoichi Ishida, Kazuki Yoshizoe, Kunihiro Wasa, Kiyosei Takasu, Yasushi Okuno, Kei Terayama, and Koji Tsuda. Compret: a comprehensive recommendation framework for chemical synthesis planning with algorithmic enumeration. Journal of cheminformatics, 12 (1):1-14, 2020.
Grzegorz Skoraczyúski, Mateusz Kitlas, Blažej Miasojedow, and Anna Gambin. Critical assessment of synthetic accessibility scores in computer-assisted synthesis planning. Journal of Cheminfor- matics, 15(1):6, 2023.
13

---

Published as a conference paper at ICLR 2024
Megan Stanley and Marwin Segler. Fake it until you make it? generative de novo design and virtual screening of synthesizable molecules. Current Opinion in Structural Biology, 82:102658, 2023.
Felix Strieth-Kalthoff, Frederik Sandfort, Marwin HS Segler, and Frank Glorius. Machine learn- ing the ropes: principles, applications and directions in synthetic chemistry. Chemical Society Reviews, 49(17))6154-61168, 2020.
Amol Thakkar, Veronika Chadimová, Esben Jannik Bjerrum, Ola Engkvist, and Jean-Louis Rey- mond. Retrosynthetic accessibility score (rascore)-rapid machine learned synthesizability classi- fication from ai driven retrosynthetic planning. Chemical Science, 12(9):3339-333 -339, 2021.
Austin Tripp, Sergio Bacallado, Sukriti Singh, and José Miguel Hemmáneez-Lobtto. Tanimoto ran- dom features for scalable molecular machine learning. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 33656-33686. Curran Associates, Inc., 2023.
Zhengkai Tu, Thijs Stuyver, and Connor W Coley. Predictive chemistry: machine learning for reaction deployment, reaction development, and reaction discovery. Chemical Science, 2023.
Pauli Virtanen, Ralf Gommers, Travis Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: funda- mental algorithms for scientific computing in python. Nature methods, 17(3)2611-222, 2020.
GE Vleduts. Concerning one system of classification and codification of organic reactions. Infor- mation Storage and Retrieval, 122-3):117-146 1963.
Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning. MIT press Cambridge, MA, 2006.
Shufang Xie, Rui Yan, Peng Han, Yingce Xia, Lijun Wu, Chenjuan Guo, Bin Yang, and Tao Qin. Retrograph: Retrosynthetic planning with graph search. Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 2120-212111111 2022.
Yemin Yu, Ying Wei, Kun Kuang, Zhengxing Huang, Huaxiu Yao, and Fei Wu. Grasp: Navigat- ing retrosynthetic planning with goal-driven policy. Advances in Neural Information Processing Systems, 15:10277-10268, 2022.
Weihe Zhong, Ziduo Yang, and Calvin Yu-Chian Chen. Retrosynthesis prediction using an end-to- end graph generative architecture for molecular graph editing. Nature Communications, 14(1): 3009, 2023.
Zipeng Zhong, Jie Song, Zunlei Feng, Tiantao Liu, Lingxiang Jia, Shaolun Yao, Min Wu, Tingjun Hou, and Mingli Song. Root-aligned smiles: tight representation for chemical reaction predic- tion. Chemical Science, 13(31):90339900 9034,, 2022.
14

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
Summary of Notation
16
B Details of search graphs in retrosynthesis
18
B.1 AND/OR graphs
18
B.2 Synthesis plans
20
B.3 OR graphs
21
C
Further details of retro-fallback
22
C.I Details of s(-), (b()) and p())
22
C.2 Example of calculating t and
26
Justification of node selection
28
Rejected alternative algorithms
28
Practical implementation details
28
D Proofs and Theoretical Results
30
D.I Proof of Theorem
30
D.2 Computing s(.), w(-) and p(-) polynomial time
30
E
Discussion of previous search algorithms and why they might struggle to optimize
SSP
32
E.1
Can we say anything definitive about the ability of different algorithms to maxi-
mize SSP?
32
E.2
Existing algorithms and their configurabile
32
E.3
Finding individually successful synthesis plans may not be enough to maximize
SSP
34
F
Extended related work (excluding previous search algorithms)
36
F11
Search heuristics for retrosynthesis
36
Generative models]
36
F3
Single-stop retrosynthesis
36
F4
RusionRetro
36
F55
Planning in stochastic graphs
37
G
Extended experiment section
38
G.1
Details of experimental setup
38
Additional results section 6.2 how effective is retro black maximizing
SSP)
44
G.3 Plots for time complexity and variability of retro cetro-falback for section 6.3
55
Limitations
57
Future work
58
15

---

Published as a conference paper at ICLR 2024
A SUMMARY OF NOTATION
Although we endeavoured to introduce all notation the main text of the paper in the section where is first used, we re-state the notation here for clarity,
General Math
2
Power set of set S (set of all subsets of S)
Plevent]
Probability of
1event
Indicator function: if "event" is True, otherwise 0
((NP)
Big-O notation (describing scaling of an algorithm)
O(NP)
Big-O notation, omitting poly-logarithmic factors (e.g.
(N log N) is equivalent to ((N))
Molecules and reactions
m
a molecule
ssingle-poddue reaction
M
space of molecules
R
space of (single-product) reactions
I
Inventory of buyable molecules
B
backward reaction model .M | 2
Forward reaction arrow (e.g. + B C)
Backward reaction arrow (e.g. C A+ + B)
Search Graphs
m.
target molecule to be synthesized
implicit search graph with molecule (OR) nodes in M and reaction (AND) nodes in R.
gr
explicit graph stored and expanded for search. G' C G
(ag)(x)
The parents of molecule or reaction æ in g'
Cho (z)
The children of molecule or reaction z in g'
T
A synthesis plan in G or G' (conditions in Appendix B.2 of all synthesis plans in G' that produce molecule set of all synthesis plans in G' producing any molecule
(9')
P9')")
16

---

Published as a conference paper at ICLR 2024
Feasibility and Buyability
f
Feasible function (assigns whether a reaction is feasible)
b
Buyable function (assigns whether molecule is buyable)
Et
feasibility stochastic process (distribution over
buyability stochastic process (distribution over b) success of an individual synthesis plan 7 (equation
(T:
SS;(T:E,,
Successful synthesis probability: probability that any syn- thesis plan T E T is successful (equation 2)
s(m; ff
Whether molecule is synthesizable using reac- G'. with feasible/buyable outcomes given by J.b. Takes values in {0, 1). Defined in equations 4
tions/starting molecules
s(m)
Shorthand for s(m; f.b) when f. b are clear from context.
Retro-fallback
h
Search heuristic function .M - [0. 1]
er
random expansion function (cquation 7
E'(T;Er,
estimated expected success of synthesis plan T all its frontier nodes are expanded (equation g
p'; b,,
o' value of best synthesis plan for m, including node n (equation 10
o' value of best synthesis plan including node (equa- tion
v(m; ff
Analytic solution for db under independence assumption. Defined in equations 13
plm; f,b,,)
Analytic solution for under independence assumption. Defined equations
13
alm; E,, h))
expected improvement in SSP for expanding a frontier node (equation 16).
We also use the following mathematical conventions throughout the paper:
log -00
max,e0 fz) oo (the maximum of an empty set always -0)
17

---

Published as a conference paper at ICLR 2024
B DETAILS OF SEARCH GRAPHS IN RETROSYNTHESIS
Here we provide details on the type of search graphs considered in this paper. Section introduced AND/OR graphs. These are defined more formally in section B.1 Section
also informally in- troduced synthesis plans without giving proper definition. Section B.2 provides more precise introduction. Finally, AND/OR graphs are not the only kind of graph retrosynthesis: MCTS typically uses OR graph, which is introduced in section B.3
2
B.1 AND/OR GRAPHS
Definition An AND/OR graph is directed graph containing two types of nodes: AND nodes (corresponding to reactions) and OR nodes (corresponding to molecules). The name "AND/OR" originates from general literature search. "AND" suggests that all child nodes must be "solved" for the node to be considered "solved", while "OR" suggests that at least one child node must be "solved" for the node to be considered "solved." AND nodes correspond to reactions because reaction requires all input molecules, while OR nodes correspond to molccules because a molecule be made from any reaction. The connectivity of AND/OR graphs satisfies the following properties:
Edges only exist between molecules and reactions producing them, and between reactions and their reactant molecules. This makes the graph biparlite.
2. All reactions have at least one reactant (you cannot make something from nothing).
3. All reaction nodes must be connected to their product and reaction molecule nodes.
4. No molecule appears as both the product and reactant in single reaction. This implies that at most single directed edge will exist between any two nodes.
5. All molecules are product of a finite (and bounded) number of reactions, and all re- actions have finite (and bounded) number of molecules. This means all nodes in and AND/OR graph will always have a finite number of children.
6. Reactions contain exactly one product molecule. Although this may seem restrictive, the reaction A + B C D could simply be encoded two reactions: A + B C' and A D.
Reaction cycles: graph and tree formulations Reactions can form cycles (e.g. A
A
...). There are two general ways of handling such cycles, illustrated in Figure B. One is to simply allow the graph to have cycles (Figure|B.])
The second is to "unroll" all cycles into a tree (Figure B)).). Both of these ways are legitimate. Importantly however, in the tree version of an AND/OR graph molecules and reactions may not be unique: i.c. a molecule or reaction may occur multiple times in the graph. Because of this, in general, we assume that all functions in this paper which act on the space of molecules or reactions (e.g. s(-), (-)) really act on the space molecule and reaction nodes. For example, this means that the same molecule may have different té values at different locations in the graph.
Implicit Search Graph In section 2 we stated that the implicit search graph & is defined by the backward reaction model. This can be either a (possibly cyclic) graph tree (as described above). In either case, the nodes in G are defined in the following way:
1. G contains the target molecule m...
2. If molecule m G. then all reactions in ((m) are also in
3. If G contains the reaction r (with product m), then E B(m) (i.e. the output of the backward model).
9 can also be defined constructively by initializing Go + (m-): and 9.+1 is produced by using B(m) to add reactions to add leaf nodes in Gi. is the product of repeating this infinitely many times (essentially Goo), Note that by this definition, & could very well be an infinite graph especially if
Hence the limit tom d G. is well-defined.
18

---

Published as a conference paper at ICLR 2024
73
me
mc
ma
mh
73
a) Graph version
b) Tree version
Figure B.1: Graph and tree representation of the reaction set m, + ma (ri), ma + my (r2),
= me (ra), and me = m, (r4).
the tree construction is used (the presence of a single cycle will make g infinitely deep). This procedure guarantees the following properties of G:
1. G is (weakly) connected. Every node in 9 is reachable from the target molecule m. by following directed edges.
2. Only molecule nodes will have no children (reaction nodes always include their children).
Explicit Search Graph The explicit search graph g' C G is a subgraph of G which is stored explicitly during search. G' will satisfy the following properties:
1. g' will always include the target molecule m...
2. G' always contains finite number of nodes and edges (even if is infinite).
3. If two nodes n1, n2 G', G' will contain an edge between n, and n2 any only if G contains an edge between nı and n2. This means g' will not "drop" any edges originally present in g.
4. For a node n E G', if C'ig (n) A 0, then no further children can be added to n. This means that nodes are only expanded once. Typically Chz (n) = Cn)( although some children may potentially
excluded.
5. If a reaction r E G', then (h) = (r)( This means that reaction nodes will always be expanded. Expansion of molecule node therefore involves adding all reactions in (m) and also adding the reactant molecules for all those reactions. This also means that all leaf nodes (i.e. childless nodes) in G' will be molecule nodes.
6. The conditions above imply that g' will also be weakly connected, with every node reach- able from m...
Frontier The frontier of the implicit graph g' is the set of nodes whose children in & have not been added to G': i.e. they are non-expanded. The frontier is denoted by F(G'). Note that the frontier of the implicit search graph G is empty by definition: the graph is "maximally expanded" (and therefore possibly infinite in size). However, there is one ambiguous case which must be dealt with in practice: molecules nodes have no children in G, and therefore expanding them will not add any children. In practice, because (mm) is only calculated upon expansion, treat these molecules they are first added the graph, and then remove them from the frontier when they are expanded. This has practical implications:
which are not the product of any reaction (i.e. B(m) = 0). These
the frontier when
19

---

Published as a conference paper at ICLR 2024
1. F(G") is not just the set of leaf nodes in G': there may be some leaf nodes not the frontier because they have no child reactions.
2. The frontier therefore cannot determined simply by looking at the connectivity of g'. Our code therefore explicitly stores whether each leaf node is on the frontier. However, F(G") will always be a subset of leaf nodes in G"
B.2 SYNTHESIS PLANS
Synthesis plans were defined informally in section More formally, synthesis plan T is subgraph of G (either as a graph or a tree) satisfying the following properties:
T a weakly connected subgraph of g.
2. If nodes 81, 72 E T share an edge in G. this edge will also be present in T.
3. T is acyclie. This means there will always be meaningful order to "execute" T.
4. Every molecule m E T has at most one child reaction (which will also be in G). This means that there is unique way to make each molecule in T. Molecules with no child reactions form the frontier F(T)
5. If reaction r E T, then all its children must all be in T (i.e. Cha(r) T
6. T contains special "root molecule" my, which can be thought of as the "product" of the synthesis plan. my has no parents in T (hence the plan "terminates" m²).
Note in particular that each molecule has a valid synthesis plan {m). i.e. a singleton synthesis plan. This is not mistake; such synthesis plans would be a prudent choice for buyable molecules (and would correspond to just buying the molecule). Jiménez & Torras (2000) contains more thorough discussion what constitutes a synthesis plan (although using different terninology).
(9') denotes the set of all synthesis plans in G' whose product is (g') be enumerated recursively, for example using Algorithm Shibukawa et al. (2020) provides another method to do this.
Algorithm Simple algorithm enumerate all synthesis plans.
Require: Explicit graph G', product molecule m4.
1: S 0
{Initialize the of plans be returned) (Include the "singleton" plan}
2: S + Smmm}
3: for E (m;) do
4: m1:..., + (hg:(r)
(Extract reactant molecules)
5: Recursively compute Pm, (9'), ,,..,,P (g')
6: for every combination of Ti P m; (g"), ....,
Te E Pm, (G') do
7: Form the subgraph T + {m,, r 1U.
8: if T is acyclic then
9:
5-St SU {
{T is a valid synthesis plan}
10: end if
11: end for
12: end for
13: return
Thhis is almost identical the definition of the frontier for AND/OR graphs from section leaf nodes are considered frontier nodes (i.c. there no special treatment for leaf nodes with no children 9). However, this particular algorithm stated may not terminate unless care is taken to avoid subgraphs which include my when recursively computing synthesis plans for reactant molecules.
B.1 except all
20

---

Published as a conference paper at ICLR 2024
B.3 OR GRAPHS
AND/OR graphs are not the only type of graph in retrosynthesis. Other works, notably MCTS Segllr et al. 2018), use OR graphs: a graph type where each node corresponds to of molecules. Synthesis plans in such graphs are simple paths. An example of an OR graph (specifically a tree) is given Figure B.2
{ 3
(ma
ime?
{mL) }
(m.
(mE)
Figure B.2: OR graph for same set of reactions as Figure B.I
21

---

Published as a conference paper at ICLR 2024
C FURTHER DETAILS OF RETRO-FALLBACK
C.1 DETAILS OF s(.), (b))) AND p(-)
C.I.1 MNEMONICS
The names of th, and p were chosen in an attempt to make them intuitive possible:
was chosen to represent "success".
vb (psi) chosen from the phrase "probability of success," it more less be interpreted as the probability that a node could be successful upon expansion.
was chosen as the probability of success of the root molecule of the search graph, which is another term for the target molecule m..
We hope the reader finds these mnemonics useful.
C.1.2 RELATIONSHIPS BETWEEN s(-), (0),, AND p(-)
Note that, for all E (g)) and ET
S So:
(T:
(17)
equation
equation
f
Taking an expectation with respect to eT on both sides gives
(T:ffbb S < (T;
(18)
Noting the relationship between s(.) and vb(-), this implies for all nodes n E G' and heuristics h
s(n; g', f)b) (n; G', f.bhh.
(19)
Finally, since the set of synthesis plans considered for f is a subset of the plans considered for 6 must be that
p(n; f,b,,,,,,,) S (nn; f.b.h).
(20)
C.1.3 ANALYTIC SOLUTIONS FOR w0-) AND p(-)
First, we state more formally the assumptions under which these analytic solutions hold.
Assumption C.1 (No synthesis plan uses the same molecule twice). Assume for all E (g")), if 11,72 E T are distinct reactions in T (i.e. rı * r2), then Clvr(ri) n Chr((z) (i.e. in and ra share no children in T).
Furthermore, if mi, m2 T are distinct molecule nodes, then my and m2 are themselves distinct molecules 11
Corollary C.2. Under assumption
C.1 all synthesis plans T E (G') are trees
Proof. Synthesis plans were explicitly defined to be acyclic in Appendix B.2 so it is sufficient to show that two nodes in an arbitrary T share the same parent. Two reaction nodes cannot share the same parent (synthesis plans were defined as having at most one child for each molecule node), and if molecule node has two reaction parents assumption C.I would be violated.
Next, we state a useful lemma for the upcoming proofs about v and p. This lemma and the following propositions all assume a fixed (and arbitrary) graph g' and functions f. b, h.
Lemma C.3. IfT; and T. are synthesis plans, and F(Ti) S F(T2) (i.e. all frontier nodes in T₁ are in T2), then o' (T;; f. b, h) < d((2;; f. b, h).
This additional statement is necessary for tree-structured search graphs, wherein the same molecule may in several different nodes.
22

---

Published as a conference paper at ICLR 2024
Proof. er.
Equation g imposes condition on all frontier nodes for synthesis plan, clearly for all
o' (T er) o' [, Since this equality holds for all er, it will also hold in expectation er. which is the definition of o' (equation
Now prove the statements from the main text. First, we consider (-) (equation 11
Proposition C.4. Under assumption
C.1 c(: f. h) satisfies equations 12-13 13
Proof. Nodes in g' can be partitioned into the following sets, for which the result is shown sepa- rately.
Frontier molecules m F(G'): the synthesis plan Tm {m] has d'(mm: S, b, h)
max [b(m), h(m)] (from equation g and equation 7). All other synthesis plans T in- cluding m will include it as a leaf node, and by lemma C.3 will have "T"; f. b, h) I o' (TTmi J. b, h). Therefore T maximizes o' (although it might not be unique), justifying the first case of equation 12
2. Non-frontier molecules m & F(G"): first, if m is a non frofrentier node with no children, then all synthesis plans including m will terminate m, giving (mm) b(m). Equation I2 matches this (because we use the convention max 0 = -0))
Otherwise, first consider the case where b(m) = Clearly T. = {m] maximizes equa- tion 11 so v f. h) = b(m) =
Otherwise, consider b(m) = In this case, o' (T h) O, so all other synthesis plans will be equal to or better than Tm. Therefore we look to m's child reactions. Synthesis plans containing one of m's child reactions will necessarily contain m, making (mm) =
maxpeCha-mmn (r)): exactly what is in equation 12
3. Reaction nodes r: Because of assumption C.I and the fact that er (equation 7 is indepen- dent for every node, the optimal synthesis plan including will be formed by combining the optimal synthesis plans for all reactions m E (r) Due to independence, the probability of them all being successful is simply the product of each synthesis plan being successful, justifying equation I3
Finally, we consider أ (equation 10 Proposition C.5. Under assumption C.I
(l:g",f,,,l satisfies equations I4.5 15
Proof. First, note that from our definition of AND/OR graphs in section B.I all nodes in G' will be included on least synthesis plan which produces m...
We partition nodes in g' into the following sets and provide a separate proof for each set.
1. The target molecule m,: first, any synthesis plan T including m4 as intermediate molecule (i.e. not the product of the synthesis plan) will have d'(T; f. b, h) bounded by d'(I"; f, b, h) for some synthesis plan I" whose final product is m. (by lemma C.3 Therefore, and synthesis plan achieving ('m,;; f' f,b,h) h) will also maximize p. So, p(m.;9] f. b, h) (mm.; g', f'.f. h).
2. A non-target molecule m: m will have at least one parent r. Any synthesis plan for m. which includes must necessarily include (because synthesis plans will always contain all reactants for every reaction). Therefore, the set of synthesis plans for m, which also contain m is given by
UrePag (m) (T E (.
p(m) will simply be the maximum of these values.
23

---

Published as a conference paper at ICLR 2024
Together with the previous case, this justifies equation 14
3. A reaction First, if (r;;; 9 f,b, h) 0 then clearly p(r; f,b, 0 as maximizes over a larger set of synthesis plans than
Otherwise, let be the single parent of The synthesis plan T justifying p(m; g, f, b, h) will be composed a synthesis plan Tmm for m (i.e "below" m) and a partial synthesis plan T T. which uses as intermediate molecule (or potentially the product molecule if m = m.). Because of the independence of different branches resulting from equation and assumption C.1 o' (T; f; b, h) will be the product of o' d'(Tmi - b,,b,h) (b 9', f b, h) and term for T Tm. The optimal synthesis plan which includes r can therefore be constructed by removing Tm (and dividing by its probability (", b, h)) and adding the optimal synthesis plan for m which includes (with probability (r(;; g', f,b, h)).
Together, these cases justify equation
C.1.4 COST-MINIMIZATION INTERPRETATION
The functions s(-). (.), and p()) have a cost minimization interpretation when transformed by mapping f() + log f(-) (using the convention that log -oo). To see, this, write the transformed equations explicitly. To simplify notation, we write:
b(m) log b(m)
(21)
f(r) log (r)
(22)
h(m) - log h(m)
(23)
s(-) log s(-)
(24)
vi() log (-)
(25)
p(-) = log p(-)
(26)
For s(-) (equations 5) we have
s(m: ff.) = min (((m), min
$(r:
(27)
(m)
((r:)). -(()
Σ $(m; S.
(28)
mEChor(r)
Since s(-) E (0, 1), this corresponds to a pseudo-cost of molecule synthesizable and cost of too otherwise.
For v-)-) (equations 12
13 and p(-) (equations 14 we have:
min ((m), h(m))
m E F(g')
(29)
min b(m), min echhr p(r; ('r:"'.. I.b, m F(g')
G'r: = f(r) + mcChar())
Σ
(30)
(mm; f.b.h)
m is target molecule m,
"mm;'', S.b,h)
(31)
minge (m) g(r; G.b.
all other m
+00
= +00
g'm';g,,11 f,b,h,
f.b
(32)
"', (rr:''...b.)) < ca,m' E (r)
+vbr: g', f,
Since (--) and p(-) have ranges [0, 1], (.) and p(-) have ranges [0, +oo] (i.c. explicitly including infinity).
24

---

Published as a conference paper at ICLR 2024
C.1.5 CLARIFICATION OF rs, D AND P FOR CYCLIC GRAPHS
If G' is an acyclic graph, the recursive definitions of s(-), (h)., and p(-) will always have a unique solution obtained by direct recursion (from children to parents for s(-) and v((), and from parents
children for p(-)). However, for cyclic graphs, such recursion is not possible and therefore these equations do not (necessarily) uniquely define the functions s(-), (-(),, and p(-).
The minimum cost interpretation from section C.I.4...oviiiiiii
a resolution. Minimum cost solutions in AND/OR graphs with cycles have been extensively studied (Hvalica 1996, Jiménez. & Tooras 2000) and indeed exist. HHalica (1996) Lemma 1) in particular suggests that the presence of multiple solutions will happen only because of the presence of zero-cost cycles (which could be caused by a cycle of feasible reactions). To produce a unique solution, we re-define all costs to to be a constant e > 0 (for which there will unique solution for š, uh. and p), and take the limit as produce unique solution which includes 0 costs.
C.1.6 COMPUTING S, v, AND P
The best method of computation will depend on g'. If g' is acyclic (for example, as will always be the case for tree-struse rre-structured search graphs) then direct recursion is clearly the best option. This approach also has the advantage that the computation can stop early if the value of node does not change.
In graphs with cycles, any number of algorithms to find minimum costs in AND/OR graphs can be applicd to the minimum-cost formulations of s(-), v0(),, and p(-) from section C.1.4 CChakrabarti 1994 HHalica [996] Jiménez & Torras 2000).
25

---

Published as a conference paper at ICLR 2024
0
$:.0
m/
P:
f:1
J:
f:
5
P1
0
0:
1: 0.01
0.9
000.1
6:
1
0
0.1
mh
4:
0.1
5:
p: 0.9
my
mg
h:
f:1
f:1
x: 0
57
F:
$:
v:: 0.1
s/ 0.1
41 0
s/: 0.8
p:
t: 0.9
0.9
FG
8:.0
0.01
mc
md
m
m2
5:
0:
V: 0.5
A: 0.1
s:
$:
p=
p:
Figure C.I: A search graph G' with values for vh, and p worked out. A detailed explanation is given in Appendix C.2
C.2 EXAMPLE OF CALCULATING S, AND p
presents search graph G' with labels from sample of f, and heuristic values h. The graph contains three branches stemming from m, starting with V1, 14, and rs respectively. designed to highlight several interesting corner cases, which will be emphasized below. We will work through the calculations of s, t, and for all nodes below. To simplify notation, we will omit the dependence of these quantities on g', f, b, h, this is implicit.
Figure C.1
C.2.1 CALCULATION OF
Note that only molecules mc. me. and my are buyable (b(-) = 1); the rest are non-buyable All reactions are feasible (f(-) 1), except for тĄ. This means that s(-) 1 only for me. Me, and
my. Their parent reactions all have one other reactant with s(.) = 0; therefore all other nodes in the graph have s(.)
C.2.2 CALCULATION OF &
Since depends only on node's children, we will show the calculation bottom-up for each branch. branch:
Leaf nodes: me and m. are buyable molecules whose heuristic values are less than 1. Therefore, f((m)) h(ma) = 0.5 dominated by b(-) 1, the max of equation 12 yielding vb(-) = 1. For my which is not buyable, ((mm)) h(ma) = 0.1.
T2, Both these reactions are feasible (f(.) = 1). so v)(-) will just be the product of vi values of its children, which in this case yields (122) vb(r)) 0.1.
ma; myt Both molecules inherit y values from their children, so (mmm.))) = (mm))) = 0.1.
71: f(r1) 1, so by equation 13 (r1) = ((mm)ee(m) = 0.01. Note however that this is instance of double counting. because ma occurs twice in this synthesis plan. ((r1) calculates a success probability for rı as if m, needs to independently succeed twice, yielding value of 0.01 instead of 0.1. Synthesis plans like this unusual however, and
26

---

Published as a conference paper at ICLR 2024
explained previously simply accept that to calculate v efficiently it may occasionally double-count certain nodes.
14 branch:
myt Here, (m))) - h(my) = 0.8 (since b(my) = 0)-
74: (raa) = (my) = 0(0.8) = 0. Essentially, because this reaction is infeasible, yb will be O, since amount of expansion below 74 will make it feasible.
rs branch:
m,t Here, (mm,)) = (m,)) 0.5.
r6t (b(a) ((r)))(m.) = (1)(0.5) = 0.5.
ma: This is another edge case: buyable molecule with child nodes. Here, vb(m)) =
max [b(m,), (+())] = Essentially, it inherits 1 value from b, not from up values of its children.
my Here, mmm)) = h(m,) = 0.9.
rst (rrs) = (1s))) (1)(0.))(1) 0.9.
m.:
(m..) = max (6(m.), v(r)) (r4)), (r)))
max [0, 0.00
= 0.9
The optimal synthesis plan achieving this success probability is
{m+, Ts, my (expanded), my (bought))
C.2.3 CALCULATION OF
Since depends only on node's parents, we will show the calculation top-down.
m.: By definition in equation p(m.) (m.) 0.9.
branch: Note that the optimal synthesis plan which justifies (mm,) comes from this branch, so we should expect many nodes to have p(-) = (m.).
7s: From equation 15 p(rs) = p(m.) v(rs) (m..).
w(m.) = 0.9 0.9 = 0.9. As expected, this equals
0.9
my: mg From equation 14 p(mp)) p(mm) p(rs) = 0.9.
T6: This is an interesting edge case because To 's parent, m., is buyable. From the definition p. p(r6) should be a quantity which only considers synthesis plans which include re. and therefore must not buy mi. We can work out:
p(rs) p(mm) v1(6)
(mm)))
0.5 0.9
I
0.45
Intuitively this lower value makes sense: using re, which is only predicted succeed with 50% probability, reduces the success probability of the best synthesis route by half.
m,: p(m)) = p(rs) = 0.5
ra branch: This branch uses infeasible reaction, so any synthesis plan forced contain nodes in this branch should have a success probability of O. Indeed we see this below:
T4t p(rx) p(m.) (mm.)
((rs) 0.9 0.
27

---

Published as a conference paper at ICLR 2024
myt p(m)) p(ra)= =0
This branch contains just one synthesis plan with predicted success of 0.01 (due to the double counting). Calculating should therefore propagate this value down to the leaf nodes. Indeed, this is what we see below:
branch:
T1 p(r1) = plm.) *(r1)
0.9 0.01
0.9
0.01. 0.9
[(m.)
Moy myi p(ma) p(mo) p(r1) 0.01.
T2, Tst p(r2) = p(maa ((ne) 0.01 0.1
0.1 = 0.01 (and same for rz).
me, ma. m,: Note that p(m,)) = p(r2) = 0.01 and p(m.)) = p(ra) = 0.01. Node my has multiple parents, but all with the same p value, p(ma) min [0.01, 0.01] 0.01.
C.3 JUSTIFICATION OF NODE SELECTION
Selecting nodes for expansion based p values for samples f.b where s(m.; f. 0 will always have the interpretation of improving SSP. Taking the expected value in this scenario is a natural choice. However, it is not the only choice. The formulas
a'oode G', Ey Eb, h)) Mode (s( (o(m; G', f, hi]]
(33)
ag((m G', Ey; Eh, h) Quantile?>~sy.be [1s(m. (',))) (1 [p(m; J' b, h)]]
(34)
are also sensible choices. We choose the expected value mainly out of simplicity.
C.4 REJECTED ALTERNATIVE ALGORITHMS
The first iteration of retro- farto-- (proto retro-fallback) used a search tree instead of a search graph, and assumed that the feasibility/buyaailiy of all reactions/moleeules was independent. In this spe- cial case, the values of s, &b and can all be computed analytically using dynamic programming. However, major weakness of this algorithm is that forcing G' to be some molecules and reactions in the graph (e.g. if both the reactions A + B + C' and A + D = are possible then the molecule A and any reactions under it would be duplicated). The assumption of independence meant that the feasibility of the same reactions would be sampled multiple times independently, leading to "backup plans" that actually used the same reaction. practice this was often not an issue, but it did mean that the internal estimates of s used by proto retro-fallback did not have a clear relationship to true SSP. Hence we decided to proceed using samples, which provided a natural avenue to remove the independence assumption. More details about proto retro-fallback can be given upon request to the authors. An implementation of this version of retro-farll cato-ffllbacck is also available in our public code.
required duplicating
When designing the version of retro-fallback presented in this paper, we first considered sampling outcomes for frontier nodes using the heuristic function, and updating using the standard equations for s. This would effectively be a random heuristic, and although other algorithms use random heuristics (e.g. rollouts in MCTS) we decided that it would be an extra source of variance, and upon realizing that the expected value of such a heuristic can be computed analytically if the outcomes are assumed be independent other researchers wish to remove the independence assumption in the heuristic then probably its outcomes would also need be sampled.
proceeded to develop the equation for v.. However, in the future
C.5 PRACTICAL IMPLEMENTATION DETAILS
Here we give further details of how retro-fallback be implemented. This section is not de- scription of our specific software implementation used in this paper: that is in Appendix G.I.I Instead, we try give general guidance that would be applicable for alternative implementations and alleviate potential sources of confusing or ambiguities.
Graph initialization In Algorithm I we start by initializing g' to contain just the target molecule. Strictly speaking this is not required: any starting graph can be used (as long it satisfies the
28

---

Published as a conference paper at ICLR 2024
assumptions about AND/OR graphs in Appendix B.1 e.g. not having reactions frontier nodes or edges between molecules and reactions that should not be connected). All that is needed is to properly initialize the variables (s, 16, p) before entering the main loop.
Samples from stochastic processes A full sampled function from &, or & contains outcomes for every possible molecule or reaction. In reality this could not be calculated or stored. Therefore, in practice one would only sample these functions for nodes in G", and sample from the posterior stochastic processes when new nodes are added. For processes where this is inexpensive (e.g. pro- cesses with independent outcomes) this is fast and the implementation is not important. However, when it is slow likely very important use caching. For example, drawing samples from a GP posterior scales with O(N if Ey & use a GP, this O(N3) operation at every step will result in an overall algorithm speed of O(N+)! To avoid this, we cached a Cholesky decomposition of the GP covariance matrix at every step and used incremental updating of the Cholesky decomposition to bring the overall complexity to most O(N9). For other stochastic processes different techniques may be applicable, but in general for non-independent stochastic processes we anticipate some form of caching may be necessary.
Vectorized computation Vectorized computation could also be used instead of explicit for loops over the sampled functions in ,, wherein values for v.. and p would be simultaneously updated for all samples.
Priority Queues In each iteration of algorithm a frontier node maximizing a is found. prac- tice, this could be accelerated using a priority queue to avoid explicitly considering every frontier node in every iteration (which has a cost linear the number frontier nodes).
Backward reaction model Algorithm requires backward reaction model B. This is also not necessary: all that needed is some way to decide what reactions to add to the graph. For example, if it was possible to obtain a list of reactions from &, whose marginal feasibility is non-zero, this could be used as a replacement for B.
Tie-breaking Algorithm [ suggests when choosing nodes, ties should be broken arbitrarily. How- ever, some frontier nodes may be buyable, and will only have a high value because they belong to the synthesis plans with other expandable nodes. Therefore, in general it would be beneficial to break ties in favour of non-buyable nodes, since expanding buyable node will never produce new synthesis plan.
Termination conditions Algorithm uses several termination conditions, some of which may be necessary or could be modified:
No nodes are left to expand. We believe this one is necessary.
2. L iterations of expansion are done. This is not necessary: the algorithm alternatively ter- minate after a fixed wall-clock time, or simply never terminate until it is killed by the user.
3. All s (m.) are 1: this is a sensible point to terminate because means that ex(m) = 0 for all frontier nodes m. However, the algorithm could easily keep running past this point; would just expand nodes arbitrarily because all nodes would have an equivalent value of (m). This condition could also be loosened: for example the algorithm could terminate when (m..)= > 1 e for some small > O. This is sensible if one believes that improvement beyond a certain point redundant.
29

---

Published as a conference paper at ICLR 2024
D PROOFS AND THEORETICAL RESULTS
This appendix contains proof' of theoretical results from the paper.
D.1 PROOF OF THEOREM 3.1
Theorem 3.1 is corollary of the following theorem, which we prove below.
Theorem D.1. Unless P = NP, there does not exist an algorithm to determine whether (P,, (g'); Eb) 0.for arbitrary Eg, Ea whose time complexity grows polynomially with the number of nodes in G
Note that Theorem D.I is similar to but distinct from Theorem 3.1 The difference (highlighted)
is that Theorem 3.1 is about the difficulty of computing SSP, while Theorem D.I only about the difficulty of determining whether or not SSP is O. We now state proof of Theorem D.I
Proof. We will show a reduction from the Boolean 3-Satisfiability Problem (3-SAT) to the problem of determining whether SSP is non-zero. As 3-SAT is known to be NP-hard Karp 1972). this will imply the latter is also NP-hard, completing the proof.
To construct the reduction, assume an instance of 3-SAT with n variables 21, In. and m clauses C1. ..... Cms each ej consisting of three literals (where a literal is either variable or its negation). We will construct an AND-OR graph G(T) with size O(n + m), alongside with distribu- tions (T) and (T), such that the SSP in the constructed instance is non-zero if and only if is satisfiable.
In our construction first set f i.e. assume all reactions descrihed below always feasible.
We then construct a set P of 2n potentially buyable molecules, corresponding to variables 2; as well their negations -r;; to simplify notation, will refer these molecules I; -.; We then set (1) to a uniform distribution over all subsets S C P such that |S n {I;,-I; - = for all i; in other words, either x; or - can be bought, but never both the same time. Note that with this construction it is easy to support all necessary operations on &d. such as (conditional) sampling or computing marginals.
It remains to translate / to G()) in way that encodes the clauses ej. We start by creating root OR- node r, with a single AND-node child r'. Under r' we build m OR-node children, corresponding to clauses Cy: again, we refer to these nodes cj for simplicity. Finally, for each cj. we attach 3 chil- dren, corresponding
the literals in cy- Intuitively these 3 children would map to three molecules from the potentially buyable set P. but formally the children of oj should be AND-nodes (while P contains molecules, i.e. Oo-nods)); however, this can resolved by adding dummy single-reactant reaction nodes.
To see that the reduction valid, first note that r is synthesizable only if all ej are, which reflects the fact that / is binary AND of clauses cy. Moreover, each cj is synthesizable if at least one of its 3 children is, which translates to at least one of the literals being satisfied. Our construction of & allows any setting of variables 2; long it's consistent with negations -a;, Taken together, this means the SSP for (I) is non-zero and only if there exists an assignment of variables x; that satisfies I, and thus the reduction is sound.
Corollary D.2. If a polynomial time algorithm did exist to compute the exact value of SSP(PPL. m. (') this algorithm would clearly also determine whether SSP(P... G', Et, > 0 in polynomial time, violating Theorem D. This proves Theo-
rem 3.
D.2 COMPUTING s(.), (6-) AND p(-) POLYNOMIAL TIME
Here, state provide proofs that these quantities can be computed in polynomial time. These proofs require the following assumption:
Assumption D.3 (Bound on children size). Assume [Cha(m)) < K. [Cha(m)) s L, [Pag(m)] S J for all molecules and reactions r, where J, K, L. E N are fixed constants.
30

---

Published as a conference paper at ICLR 2024
This assumption essentially ensures that even the retrosynthesis graph grows, the number of neighbours for each node does not grow.
Now state our main results.
Lemma D.4 (s and & in polynomial time). There exists algorithm to calculate s(n; G' (. and ()::; 9¹, Sf., h) for every node n E G' whose time complexity polynomial in the number of nodes in g'.
Proof. Section C.1.4 showed how how s.)) and - log 1-(-) correspond exactly cost equations for minimum-cost synthesis plans, studied for the AO* algorithm. (Chakrabarti T994) provides two algorithms, Iterat inrrativee.e ive.revieeieeeeee number of nodes (assuming a number of edges which does not grow more than linearly with the number of nodes, which assumption D.3 guarantees).
and REV* whose runtime is both worst-case polynomial in the
The following lemma shows that, with bit of algebraic manipulation, the same strategy can be applied to p.
Lemma D.5. There exists an algorithm to calculate p(n;; G', S. J.b)for for every eveery node E G' whose time complexity is polynomial the number of nodes in G'
Proof. To do this, first compute (-) for every node (which lemma D.4 states can be done in poly- nomial time). Next, define the function 17(-) = log 30m, G .fb.k)
This is essentially a constant
p( f.h.)
transformation of p(-) each point (since (mm G', . b, h) is just constant). Therefore v has the analytical solution:
n(m; k.
m
(35)
mminre (agr
all other m
[
w(r: I, =0 v(r: f. b,b,)) h) < co, m' E Pag
nrr: 2' f.b,h)
nmmm g', f.b,h) + log v(rie'
s6m'sg (.b.h)
(36)
Now, define the graph g' by flipping the direction of all edges in g' (so all parents become children, and vice versa). can be written as:
nm(m; (,b,,,
m
(37)
ecinreChgitre nrr; f,b,,,
all other m
"r. = (rr; < 00
nr:: Em (Ch S,, log i'm'g'' (AA) (.b..)
(38)
introduced because reactions in g' have only one parent. These equations correspond precisely to minimum cost equations from AO*, allowing algorithms from Chakrabarti (1994) to be applied. p can then be straightforwardly recovered from ?).
where the sum in equation 38
However, since the sum in equation 38 has only one element, this is in fact equivalent to path-finding in ordinary graph, Dijkstra's 's algorithm could be used to solve for in log- log-linear time (once v solved).
31

---

Published as a conference paper at ICLR 2024
E DISCUSSION OF PREVIOUS SEARCH ALGORITHMS AND WHY THEY MIGHT STRUGGLE TO OPTIMIZE SSP
This section aims to provide a more detailed discussion of previously previouslyprrooosed algorithms. It is structured into 3 parts. In T. we qualify the content of this section by explaining how the per- formance of algorithms will depend algorithm will be incapable of maximizing SSP. In E.2 we review previous algorithms and state how they might be configured to maximize SSP. For most algorithms, the closest configuration to maximizing SSP is to reward individual synthesis plans with high success probability. Section E.3 provides an argument of why this may not always maximize SSP.
lot of factors, and therefore cannot really say that any
E.
CAN WE SAY ANYTHING DEFINITIVE ABOUT THE ABILITY OF DIFFERENT ALGORITHMS TO MAXIMIZE SSP?
The behaviour a search algorithm can depend on many configurable parameters (including function-valued parameters):
1. Reward functions (or similar): algorithms will behave differently based on the kinds of synthesis plans which are rewarded.
2. Heuristics: most heuristic-guided search algorithms will, to some degree, follow the guid- ance of the search heuristic.
3. Other hyperparameters (e.g. the exploration constant in MCTS).
How can these parameters be adjusted? One option is to set these parameters independently of & or & (i.e. completely ignoring them). Even under these conditions, algorithm could possibly return a set of synthesis plans with high SSP. This could happen due to random chance (e.g. lucky choice of nodes to expand), due some kind of "alignment" between the algorithm's 'ss internals, &y. and & (for example, reactions with high feasibility having low cost). However, such outcomes are clearly not attainable systematically without accessing & and &,, since random chance is not repeatable, and "alignment" for one feasibilit//uyaaiiity model necessarily means misalignment for another one. Therefore, we argue only makes sense to compare algorithms' ability to maximize SSP when they are configured to use information from & and &b to maximize SSP.
Even under these conditions however, given particular m., it is likely possible design custom heuristic and setting of the algorithm's 's parameters which will lead an algorithm to maximize SSP very effectively for that particular Wi.. This makes it difficult [perhaps impossible] to prove state- ments like "algorithm A is fundamentally incapable of effectively maximizing SSP. At the same time, given any configured version of an algorithm (including a search hcuristic, reward, etc.), is likely possible to find particular m, and feasibility model E,, & where the algorithm fails catas- trophically (a little bit like the no free lunch thcorem in machine lcarning). This makes difficult [perhaps impossible] to prove statements like "algorithm A is generally better than algorithm B at maximizing SSP"
Therefore, when discussing previous algorithms in this section, merely adopt the goal of showing how the algorithm cannot be configured to directly and straightforwardly maximize SSP in the same manner as retro-fallback.
E.2 EXISTING ALGORITHMM AND THEIR CONFIGURABILITY
E.2.1 BREADTH-FIRST SEARCH
Description of algorithm were added.
A very basic search algorithm: expand frontier nodes in the order they
Configurable inputs/paramettr None.
How to configure to maximize SSP? N/A
Potential modifications to the algorithm that could help? We see obvious changes.
32

---

Published as a conference paper at ICLR 2024
E.2.2 MONTE-CARLO TREE SEARCH (MCTS)
Description algorithm Used in (Segler et al. 2018 Coley et al. 2019b Genheden al. 2020).
MCTS creates an MDP where "states" are set of molecules and "actions" are reactions which react one molecule state and replace it with other molecules. This corresponds the "OR" tree At each step, it descends the tree choosing nodes which maximize
introduced in section B.3
W(s,, a) (st,
(N(5(-1.0-1)
+ cP(s a) 1+ 1+N(s,,,))
(39)
where (s,,, a) is the total reward accumulated while taking action to reach state St, (sts,, a) is the number of times when the algorithm has performed action a to reach state 8 and P( a) is some sort of prior probability of performing action reach 8t, and c is constant. The algorithm is designed to eventually converge to the action sequence which maximizes reward.
Configurable imputs/parameters search heuristic V (an estimate of the value function, e.g. based on rollouts), the policy prior P. and the UCB exploration constant c.
The reward function (mapping states to scalar rewards) R, the
How to configure to maximize SSP? Rewards and value functions in MCTS depend on individual synthesis plans, so reward of (T;; Eo: Ey) would reward individually successful synthesis plans. In practice, this reward could be estimated with samples.
Potential modifications to the algorithm that could help? One option is to make the reward and policy change over time. For example, one could have the reward be the additional SSP gained from discovering a new plan. However, it is possible that MCTS will not behave well in this scenario: principle of MCTS is to narrow down on the best sequence confidence interval around their expected return. However, if the rewards change over time then these interval estimates will likely become inaccurate. Although the intervals could be widened (e.g. by increasing c) this will result in MCTS behaving more randomly and not searching efficiently. Also, we note that there are many possible design choices here, and further probing of alternative options might yield improved results.
actions by slowly tightening
E.2.3 DEPTH-FIRST PROOF NUMBER SEARCH (WITH HEURISTIC EDGE INITIALIZATION)
Description of algorithm Proposed Heifets Jurisica (012)) and augmented by Kishimoto et al. (019). Basic proof number search assigns "proof numbers" and "disproof numbers" which represent the number of nodes needed to prove or disprove whether there exist a synthesis plan to synthesize given molecule and selects nodes using this information. The heuristic edge initializa- tion Kishimoto et al. (2019) uses a heuristic to initialize the proof and disproof numbers for each reaction.
Configurable inputs/parameter The edge initialization heuristic h and threshold functions to control depth-first vs breadth-first search behaviour.
How to configure to maximize SSP? This algorithm inherently takes a very binary view of ret- rosynthesis (seeing nodes either proven disproven). and therefore is not very amenable to maximizing SSP. At best one could change the heuristic values to reflect feasibilities.
Potential modifications to the algorithm that could help? Aside from changing the definitions of proof/disproof numbers, we do not see any options here.
E.2.4 RETRO*
Description of algorithm An algorithm for minimum cost search in AND/OR trees (Chen et al,
2020), essentially identical to the established * algorithm (Chang & Slagle 1971 Martelli & Montanari 1978 Nilsson] 1982, Mahanti & Bagchi 1985). At each step, the algorithm selects potential synthesis plan 7' with minimal estimated cost, where the cost of synthesis plan is defined
33

---

Published as a conference paper at ICLR 2024
Giotal (T) -==oan cR((r)+ +
Σ cad (m)
rET
WET
(i.e. a sum of individual costs for each reaction and molecule), then expands one frontier node from T. A heuristic is used set the costs cas for frontier molecules.
Configurable inputs/parameters The parameters of retro* are the costs of each molecule and reaction, and the heuristic functions.
How to configure to maximize SSP? SSP does not [in general] decompose into a straightforward sum or product of values for every node. Most likely, the closest proxy to SSP would be to set a cost for each molecule and reaction with & and &s. One option is to set the cost of each reaction/molecule
to the negative log of its marginal fcasibilitybuyaaiiity:
Ca (m) log Es-es [6m)]
<R(r) = log E [f(r]]
This option does have a somewhat principled interpretation: if all feasibility/buyaaiitty outcomes are independent then the cost of plan is just the negative log of its joint SSP. Of course, this relationship does not hold the general non-independent case. However, we do not see a way to adjust this formula to account for non-independence in general, so we suggest using this setting in all cases.
Potential modifications to the algorithm that could help? One could potentially change the reaction and molecule costs with time to account for changes elsewhere in the search graph. For example, reactions/molecules which are already part of feasible plan could be re-assigned higher costs to make the algorithm search for non-overlapping plans. However, this strategy seems unlikely work in general: for some search graphs possible that the best backup plans will share some reactions with established synthesis plans. We were unable to come up with a strategy that did not have obvious and foreseeable failure modes, so we decided not pursue this direction.
E.2.5 RETROGRAPH
Description of algorithm Proposed in Xie et al. (2022), this algorithm functions like modified version of retro* but on a minimal AND/OR graph instead of a tree. A graph neural network is used prioritize nodes.
Configurable inputs/parameters Like retro*, this method uses additive costs across reactions and heuristic functions, but also uses graph neural network select promising nodes.
How to configure to maximize SSP? Similar to retro we believe the closest proxy is to set costs equal to the negative log marginal feasibilit/buyaaiiity and minimize this.
Potential modifications to the algorithm that could help? We could not think of anything.
E.3 FINDING INDIVIDUALLY SUCCESSFUL SYNTHESIS PLANS MAY NOT BE ENOUGH TO MAXIMIZE SSP
Since the best configuration for most existing algorithms to maximize SSP appears to be reward finding individual synthesis plans with high success probability, here we examine to what degree this objective overlaps with optimizing SSP. Clearly the objectives are somewhat related: SSP will always be at least high as the success probability of any individual synthesis plan considered. However, is not difficult to imagine cases where these objectives diverge.
Figure E. illustrates such case, wherein synthesis plan with reactions 11, has been found and the algorithm must choose between expanding my or m4. When considering whether to expand my however, it must be noted that any new synthesis route proceeding via ra will also use Fı, and therefore will only increase SSP for samples f, where f(ri) = 1 and f(rz) = and f(22) = 0 (or b(m2)= 0). For example, if TP, (r2) 0) very small, or the feasibility of ra and r3 are highly
34

---

Published as a conference paper at ICLR 2024
mL
Figure E.I: ANDIOR graph illustrating how maximizing SSP can be different from finding indi- vidually successful synthesis plans (cf. E.3). Green nodes are part of an existing synthesis plan with non-zero success probability, red nodes are not.
correlated, then it is very unlikely that expanding 73 will increase SSP, even if the (ri, synthesis plan may have an individually high success probability. In these cases expanding my would be better choice. In other cases, expanding my would be the better choice.
This exactly illustrates that to maximize SSP beyond finding an individually successful synthesis plan, an algorithm would clearly need to account for the statistical dependencies between existing and prospective synthesis plans in its decision-making, which simply is not possible by reasoning about individual synthesis plans in isolation. This provides compelling motivation to develop algo- rithms which can reason directly about of synthesis plans.
35

---

Published as a conference paper at ICLR 2024
F EXTENDED RELATED WORK (EXCLUDING PREVIOUS SEARCH ALGORITHMS)
Here we cite and discuss papers which are relevant to retrosynthesis, but do not propose multi-step search algorithms (which are discussed in Appendix
F.1 SEARCH HEURISTICS FOR
Many papers propose search heuristics for retrosynthesis algorithms, including rollouts (Segler et al.
2018), parametric models (Chen et al. 2020), and a variety of heuristics informed by chemical
knowledge (Schwaller al., 2020; Ertl & Schuffenhauer 2009 Thakkar et al.) 2021; Li & Chen
2022). Many papers also propose to learn heuristics using techniques from machine or rein forcemett
learning where heuristic learned based on previous searches or data (Coley et al. 2018 Liu
et al. 2022, some of these works describe their contribution as "retrosynthesis algorithm" or "retrosynthetic
Kim et al.) [021]] Yu et al., [022] Liu et al. 2023a). A potential point of contusion is that
planning algorithm." Given that the end product of these papers is a value function (or cost estimate)
which is plugged into a previously proposed algorithm (typically MCTS or retro*), we think these papers should be more accurately viewed proposing heuristics. The heuristic is orthogonal to the underlying search algorithm, so we view these works as complementary rather than competitive. We hope in the future investigate learning heuristics for eetro-fallback using similar principles.
F.2 GENERATIVE MODELS
Several works propose parametric generative models of synthesis plans (Bradshaw al. 2019 2020 Gottipati et al., 2020; Gao et al. [202]). Although this resembles the goal of explicit search algorithms, such generative models are fundamentally limited by their parametrization: they have no guarantee to find synthesis plan if it exists, and are often observed to fail to produce valid synthesis plan in practice (Gao al., (021]. We think such models are best viewed as trying to amortize the output of an explicit planning algorithms, making them more similar in spirit to search heuristics F.T
F.3 SINGLE- RETROSYNTIEESIS
Many models have been proposed to predict possible chemical reactions, including template clas- sifiers (Segler& & Waller 2017 Seidl al. 2021), graph editing methods (Dai et al.. 2019 Sacha et al. 2021: & Jung 2021| and transformers (Iwwin et al. 2022 Zhong et al. [002 Liu et al.,
2023b). Such models are a useful component of a retrosynthesis algorithm, but do not themselves perform multi-slep retrosynthesis.
F,4 FUTIONRETRO
One work which does not fit nicely into any of the previous subsections is FusionRetro (Liu al. 2023b). On one level, the paper describes a reaction prediction model based on a transformer, which essentially a single-step reaction prediction model (F.)) However, unlike other models which just condition on a single input molecule, in FusionRetro the predictions are conditioned on all predecessor molecules in multi-step search graph. The paper describes an inference procedure to make predictions from the model autoregressively, which resembles both a generative model for synthesis plans (F.2) or a pruning heuristic for breadth-fire first search (F.T). A significant portion of the paper also describes benchmarking and evaluation of plan quality.
We think that FusionRetro and retro-fallback can both be viewed as responses to unrealistically lenient evaluation metrics used in prior works retrosynthesis (chiefly reporting success if a "so- lution" is found without any regard to whether the solution is realistic). Liu et al. (2023b)'s 's general response is to evaluate the quality of entire plans rather than individual steps, and perform this eval- uation using entire synthesis plans from the literature. The advantage of this approach is that is close ground-truth data, but has the disadvantage that high-quality ground truth data is fairly scarce, especially for long plans involving rare reactions. In contrast, our response is to model un- certainty about reactions and use this uncertainty in evaluation (to define SSP). The advantage of our
36

---

Published as a conference paper at ICLR 2024
approach is that it does not [necessarily] require any data, while the disadvantage is that it requires a good model of reaction uncertainty, which we currently do not have (and creating such a model is likely to be difficult).
Critically, the approaches described these papers are not mutually exclusive: a backward reac- tion model which depends the entire search graph g' (such as FusionRetro) could be used in retro-fallback, while the quality of synthesis plans proposed by a method like FusionRetro could be evaluated using SSP. We leave combining and building upon these works in more realistic retrosyn- thesis programs to future work.
F.5 PLANNING IN STOCHASTIC GRAPHS
Prior works have also considered planning in stochastic graphs, albeit in other contexts. For exam- ple, the "Canadian Traveller Problem" and its variants (Papadimitriou & Yannakakis 1991) study search on a graph where edges can be randomly deleted However, this is an online problem, meaning that the planning algorithm leams about edge deletions during the planning process. In contrast, our algorithm assumes offline planning because chemists desire complete synthesis plans before performing any lab experiments. Moreover, works in this area seem assume explicit OR graphs with independent probabilities, while our problem uses implicit AND/OR graphs with non- independent probabilities.
12The original problem statement was to find path between two cities in Canada, where roads may be randomly blocked by snow and force the driver turn back and find alternative path (in reality however, Canadians simply drive through the snow).
37

---

Published as a conference paper at ICLR 2024
G EXTENDED EXPERIMENT SECTION
G.1 DETAILS OF EXPERIMENTAL SETUP
G.1.1 SOFTWARE IMPLEMENTATION
Our code available at https: http:://gitthbbttt / http://c/m/tttt//rrrrro---- rretrofat lback-icl
We built our code around the open-source library SYNTHESFUS Maziarz al. 2023) and used its implementations of retro* and MCTS in our experiments. The exact template classifier from Chen
al. 2020) was used by copying their code and using their model weights. Our code benefitted from the following libraries:
pytorch Paszke et al. 2019). rdki and rdchiral ral (oley et al. 2019a). Used in the template classifier.
networkx (Hagberg al.
2008 Used to store search graphs and for analysis.
numpy (Harris et al.
2020). scipy (Virtanen et al., 2020), and scikit kiii-learrn Pe-
dregosa et al. 2011). Used for array programming and linear algebra (e.g. in the feasibility
models).
G.1.2 FEASIBILITY MODELS
As stated in section 6 we examined four feasibility models for this work, which assign different marginal feasibility values and different correlations between feasibility outcomes. The starting point for feasibility models reactions outputted by the pre-trained template classification model from Chen et al. (2020) were "obviously wrong". From this, we proposed the following marginal values for feasibility:
the opinion of trained organic chemist that around 25% of the
1. (C) A constant value of 1/2 for all reactions. This is attempt account for the 25% of reactions which were "obviously wrong", plus an additional unknown fraction of reactions which seemed plausible but may work in practice. Ultimately anything in the interval (0.2, 0.6) seemed sensible to use, and we chose 1/2 as a nice number.
2. (R) Based on previous work with template classifiers suggesting that the quality of the proposed reaction decreases with the softmax value (Segler & Waller 2017 Segler al., 2018), we decided to assign higher feasibility values to reactions with high softmax values. To avoid overly high or low feasibility values, decided to assign values based on the rank of the outputted reaction, designed the following function which outputs a high feasibility
(=:5%) for the top reaction and decreases (=10%) for lower-ranked reactions:
0.75
prrank) rank/10
(40)
Note that "rank" in the above equation starts from 1.
We then added correlations on top of these marginal feasibility values. The independent model is simple: reaction outcomes sampled independently using the marginal feasibility values described above. To introduce some correlations without changing the marginal probabilities, we created the following probabilistic model which assigns feasibility outcomes by applying threshold to the value of a latent Gaussian process (Williams & Rasmussen 2006):
outcome(2 2) = 1:20
(41)
2(r) GP (u()),(;,)))
(42)
p(r) - (Pif(r) 1))
(43)
K(r,r) = Vr
(44)
Here, & represents the CDF of the standard normal distribution. Because of equation the
marginal distribution of each reaction's value is (((==(((rr))) which will be positive with
http::///gihuu..m///iccoos////// 14 "Specificllly version 2022.09.4 (Landrum et al. 2023
38

---

Published as a conference paper at ICLR 2024
2..9 D
Loo
xQ. 2000 D
notagia R Rooa
D
Figure G.I: Sample pairs of reactions where Kwai > 0.8. Top: both reactions join a COCI group to NH group in ring form molecules which differ only by the location of the CI atom on the right side ring (far away from the reaction site). Middle: two reactions transforming a tert-butyl ester into ketone with fluorine-cottaniing ring (difference between reactions is the location of the CI atom on the ring far away from the reaction site). Bottom: two reactions removing a fluorine atom from an aromatic ring on similar molecules (difference is between the CI and OH groups). Summary: these pairs of reactions are all very similar.
probability P P(((r) = (i.e. it preserves arbitrary marginal distributions). If K is the identity kernel (i.e. K ((ri r2) -r.=r?) then this model implies all outcomes are independent. However, non-zero off-diagonal values of K will induce correlations (positive or negative).
We aimed to design model which assigns correlations very conservatively: only reactions involving similar molecules and which induce similar changes in the reactant molecules will be given a high positive correlation; all other correlations will be near zero. We therefore chose a kernel a product of two simpler kernels:
Kooal (r1, r2) = K Kmot (f1, 12) Kmcch (r1,
We chose (mot(F1, 12) to be the Jaceard kernel
Σ. min(x;, x!)
k(1,, x')
Σ min(x;;2
between the Morgan fingerprints (Rogers & Hahn 2010) with radius of the entire set of product and reactant molecules [5 We chose (T r2) to be the Jaccard kernel of the absolute value of the difference between the product and reactant fingerprints individually. The difference vector between two molecular fingerprints will essentially yield the set of subgraphs which are added/removed as part of the reaction. For this reason, has been used to create representations of chemical reactions in previous work (Schneider et al. (015)..
We illustrate some outputs of this kernel in Figures G. Figure G.I shows that reactions with a high kernel value (> 0.8) are generally quite similar, both in product and in mechanism. Fig- ure G.2 shows that reactions with modest similarity values [0.4, 0.6) have some similarities but clearly less related. Figure G.3 shows that reactions with low similarity values in (0.05, 0.1] are generally quite different. After a modest amount of exploratory analysis we were satísfied that this kernel behaved as we intended, and therefore used it in our experiments without considering further alternatives. However, we imagine there room for improvement of the kernel in future work to better align with the beliefs of chemists.
For feasibility models based on Gaussian processes, drawing & independent samples for a set of N reactions will generally scale as OkkN3). This makes the feasibility model expensive for longer
This the adding the fingerprint vectors for all component molecules.
39

---

Published as a conference paper at ICLR 2024
9-0 D
l
soo
D
Figure G.2: Examples of reactions where 0.4 < Kitt I 0.6. Top: similar conjugation reactions, but the reactant on the right side is now COO anion instead of COCI group. Middle: similar reaction, although on the right reaction has a Zn + on the ring instead of F. Bottom: two reactions which remove fluorine atom from aromatic ring but molecules which much less similar than Figure G.T Summary: these pairs of reactions have similarities but are less similar than the reactions in Figure G.1
2-00 D 2 looa
O 200
Figure G.3: Examples of reactions where 0.05 < Kioul E 0.1. The pairs of reactions are generally
quite different.
searches. Other feasibility models which induce correlations are likely have similar scaling. However, for this particular kernel, approximate samples could be drawn in OKkN time by using random features approximation for the Jaccard kernel (Tripp et al. 2023
40

---

Published as a conference paper at ICLR 2024
G.1.3 BUYABILITY MODELS
Following Chen et 2020) we based our buyability models on the inventory of eMolecules: chemical supplier which acts as middleman between more specialized suppliers and consumers. According to eMolecule's 's promotional materia To they offer 6 "tiers" of molecules:
0. (Accelerated Tier). "Delivered in 2 days or less, guaranteed. Most reliable delivery service. Compound price inclusive of a small service fee, credited back if not delivered time. Available in the US only."
1. "Shipped within location in < 5 days."
business days. Compounds from suppliers proven to ship from their
2. "Shipped within 10 business days. Compounds from suppliers proven to ship from across the globe in 10 days"
3. "Shipped within 4 weeks. Shipped from suppliers further from your site and often with more complex logistics. Synthesis may be required using proven reactions."
4. "Shipped within 12 weeks. Usually requires custom synthesis on demand."
5. "Varied ship times. Requires custom synthesis for which a quote can be provided on re- quest."
Much like machine learning researchers, chemists usually want to complete experiments as quickly possible and probably would prefer not to wait 12 weeks for rare molecule to be shipped to them. Such molecules could arguably be considered less "buyable" on this subjective basis alone, we decided to create buyability models based on the tier of molecule. Unfortunately, the public repository for retro* does not contain any information on the tier of each molecule, and because their inventory was downloaded in 2019 this information is no longer available on eMolecules' website. Therefore we decided to re-make the inventory using the latest data.
We downloaded data from eMolecules downloads page specifically their "orderable" molecules and "building blocks" with quotes, After filtering out small number of molecules (3 (31407) whose SMILES were not correctly parsed by rdkit we were left with 14903392 molecules with their asso- ciated purchase tiers. Based on this we created 2 buyability models:
Binary: all molecules in tiers 0-2 are purchasable with 100% probability. Corresponds to realistic scenario where chemists want to do synthesis and promptly.
Stochastic: molecules are independently purchasable with probability that depends on the tier (100% for tiers 0-2, 50% for tier 3, 20% for tier 4, 5% for tier 5). These numbers were chosen as subjective probabilities that the compounds would be delivered within just 2 weeks (shorter than the longer times advertised). This still corresponds to chemist wanting to do the synthesis within weeks, but being willing to risk ordering a molecule whose stated delivery time is longer.
All of the experiments in this text (except for G.2.4) were run using the binary buyability model. In the future, we believe that better buyability models could be formed by introducing correlations between molecules coming from the same supplier, but we do not investigate that here (chiefly because the eMolecules data we downloaded does not contain information about suppliers).
G.1.4
TEST MOLECULES
The 190 test molecules were accessed using the syntheseus wrapper package for this bench- mark [8
To include molecules with wider range of synthetic difficulties, we also performed experiments on a set of 1000 randomly selected molecules from the GuacaMol test set (Brown al., 2019). These test molecules were generated with the following procedure:
16 At the time of publication, this was hwbspotuseecconcentttooo httpa//t///////////////////////. ebb.leeuleex20T1erer00t.... pdd
available at:
https://2126648 fs1.
K-
0--02.000 02.01-0322
Downloaded 2023-09-08.
Available at: httppp///ppppoooooopppeee//////e
41

---

Published as a conference paper at ICLR 2024
1. Download the publicly available test set from Brown et al. (2019)
2. Filter our all molecules available in the eMolecules inventory G.1.3
3. Shuffle all molecules and take the first 1000
Code to reproduce this process, and the entire test set in shuffled order is included in our code.
Finally, we also experiment with the test data from FusionRetro (Liu al. 2023b), using the test dataset found on their GitHub repository.
G.1.5 ALGORITHM CONFIGURATION
Retro-fallback was run with k 256 samples from Ey- A graph-structured AND/OR search graph was used (which may contain eycles). s(.). v))),, and p(-) were solved by iterating the recur- sive equations (including around cycles) until convergence (if this did not occur reset all values to and resumed iteration).
All other algorithms were configured to maximize SSP, as described in Appendix 122 In particular, this means:
Breadth-first search was run with no modifications, using the implementation from
syntheseus.
retro* was run using log By(s(r) as the reaction cost and log Es [m())
MCTS was run using ET; as the reward for finding synthesis plan (empirically estimated from finite number of samples). To allow the algorithm to best make of its budget of reaction model calls, we only expanded nodes after they were visited 10 times. The marginal feasibility value of reach reaction was used the policy in the upper- confidence bound. We used an exploration constant of c = 0.01 to avoid "wasting" reaction model calls on exploration, and only gave non-zero rewards for up to 100 visits to the same synthesis plan to avoid endlessly re-visiting the same solutions.
All of these algorithms are run with tree-structured search graph (which for MCTS is "OR" graph; AND/OR for all others).
We chose not compare with proof-number search KKihhimoto et al. 2019) because we did not see way to configure to optimize SSP (see Appendix F..2.3 We chose not to compare with algorithms requiring some degree of learning from self-play (including RetroGraph and the methods discussed in Appendix [F.I) due to computational constraints, and because it seemed inappropriate to compare with self-play methods without also learning heuristic for retro-fallback with self self-play.
1.1.6 HEURISTIC FUNCTIONS
The heuristic obviously plays critical role in heuristic-guided search algorithms! Ideally one would control for the effect of the heuristic by using the same heuristic for different methods. However, this is not possible when comparing algorithms from different families because the heuristics are interpreted differently! For example, in retro-fallback the heuristic is interpreted SSP value in [0, 1] (higher is better), while in retro* it is interpreted as a cost between [0, oo] (lower better). If we used literally the same heuristic it would give opposite signals both of these algorithms, which is clearly not desirable or meaningful. Therefore, we tried our best to design heuristics which were "as similar as possible."
potential future
Optimistic heuristic Heuristics which predict the best possible value are a common choice of naive heuristic. Besides being an important baseline, optimistic heuristics are always admissible (i.e. they never overestimate search difficulty), which is requirement for some algorithms like A to converge to the optimal solution (Pearl 1984). For retro- falllffal the most optimistic heuristic is (m)) 1. while for retro* it is (,m) 0. these represent the best possible values for SSP and cost respectively. For MCTS, the heuristic is a function of a partial plan T" rather than a single molecule. We choose the heuristic be Eyss, [min,er: f(r)], which is the expected SSP of the
42

---

Published as a conference paper at ICLR 2024
plan T' if it were completed by making every frontier molecule buyable In practice this quantity was estimated from samples (same as retro-fallback).
SA score heuristic SA score gives molecule score between and 10 based on dictionary
assigning synthetic difficulties to different subgraphs of a molecule (Ertl & Schuffenhauer 2009). score of means easy to synthesize, while score of 10 means difficult synthesize. For retro- fallback, we let the heuristic decrease linearly with the SA score:
SA(m) -1
hab = 1
10
Because the reaction costs in retro* were set to negative log feasibility values, we thought a natural extension retro would be
(m) log hmm(mm)
This choice has the advantage of preserving the interpretation of total cost as the negative log joint probability, which also perfectly matches eetro-fallback ' interpretation of the heuristic (recall that in section [. the heuristic values were assumed to be independent). We designed MCTS's heuristic also match the interpretation of "joint probability":
hMCTS (OcTssTT)) =ESEE
min f(r)
II
hnd (m)
mEF(T"),
Ireactions feasible/
which is the expected SSP of the plan if all non-purchasable molecules are made purchasable inde- pendently with probability hmm(m).
G.1.7 COMPUTING ANALYSIS METRICS
Our primary analysis metric is the SSP. For algorithms which use AND/OR graphs (retro-fallback, retro*, breadth-first search), we computed the SSP using equations 45 with 10 000 samples from E,, &o. For algorithms using tree-structured search graph, this was processed into cyclic search graph before analysis (for consistency).
For algorithms which use OR trees (in this paper, just MCTS) the best method for analysis is some- what ambiguous. One option is extract plans T S G' and calculate whether each plan succeeds on series of samples fi, b, A second option is to convert g' into an AND/OR graph and analyze like other AND/OR graphs. Although they seem similar, these options are subtly different: an OR graph may contain reactions in different locations which are not connected to form a synthesis plan, but could form a synthesis plan if connected. The process graph would effectively form all possible synthesis plans which could be made using reactions in the original graph, even if they are not actually present in the original graph. We did implement both methods and found that converting choice does make a meaningful difference. We think the most "realistic" option unclear, so for consistency with other algorithms chose just convert an AND/OR graph.
converting into an AND/OR
AND/OR graph tends to increase performance, this
All analysis metrics involving individual synthesis routes were calculated by enumerating the routes in best-first order using a priority queue, implemented in SYNTHESEUS.
Note that the min function will be if all reactions feasible, otherwise O. Using II, instead of min, would yield the same output.
43

---

Published as a conference paper at ICLR 2024
G.2
ADDITIONAL RESULTS FOR SECTION 6.2 (HOW EFFECTIVE RETRO-FALLBACE AT MAXIMIZING SSP)
Figure G.4
shows that if the optimistic heuristic used instead of the SA heuristic, retro- fallback still maximizes SSP more effectively than other algorithms.
t const, GP
&1 const, ind.
&r rank, GP
E/ rank, ind.
mean SSP
0.4
0.2
0.0
10
10
10
10
10
10
10
10
10
10
10
10
num. calls
num. calls
num. calls
num. calls
retro-fallack
breadit--irst
retro
MCT8
Figure G.4; Mean SSP across all 190 molecules from Chen al. (2020) vs time using the optimistic heuristic. Interpretation is identical to Figure (except for the different heuristic).
shows a similar result for the easier GuacaMol test molecules. However, the difference between retro- fallback and other algorithms is smaller than on the 190 "hard" molecule test set from Chen al. (2020). This likely because this test set contains many molecules which are easier to synthesize. For example, after single iteration algorithms achieve mean SSP of Rs 0.15 on the GuacaMol test set, compared to 0 for the molecules from Chen al. (2020).
Figure G.5
We also note the following:
For the "constant, independent" feasibility model, breadth-fire search and retro are essen- tially the same algorithm. Therefore their performance is almost identical.
Comparing results with the SA score and optimistic heuristic, it appears that the use of non-trivial heuristic does not actually make terribly large difference. This consistent with the results of Chen et al. (2020) in their experiments with retro*, where adding heuristic provided only modest increase in performance.
44

---

Published as a conference paper at ICLR 2024
SA score heuristic
f const., GP
&r const,, ind.
rank, GP
Ey rank, ind.
mean SSP
0.6
0.4
0.2
10
10
10²
10
10
10²
10
10
10
10
10
num. calls to
num. calls to
num. calls to
num. calls to
retroffallback
breadth-finst
MCTS
optimistic heuristic
Šr const., GP
f const., ind.
& rank, GP
& rank, ind.
mean SSP
0.4
10
10
10
10
10'
10
10
10
10
10
10
10
calls B
calls B
calls B
calls B
retro-fallbck
breadth-fürst
rotzo
MCTS
Figure G.5; Mean SSP time for 1000 molecules from GuacaMol (described in G.I. Interpre- lation identical to Figure
45

---

Published as a conference paper at ICLR 2024
G.2.1 RESULTS FOR INDIVIDUAL MOLECULES
The SSP results in Figures G.4 and G.5 are aggregated across all test molecules. To understand where performance differences come from, Figures G.6 and G.7 plot SSP over time for individual molecules. It appears that there is high amount of variation due randomness, and variation in outcomes between molecules.
46

---

Published as a conference paper at ICLR 2024
5 const. GP
E, const, ind.
fy rank, GP
E rank, ind.
min/ tain/median/mas SSP
100
200
100
200
100
200
100
200
SMILES: wec.he/eeeeeceeeeeooooooseeeeeee
retro-fallback
breadth-first
+ retro*
- MCTS
const. GP
S const., ind.
E rank, GP
E rank, ind.
thin/median/max SSP
0.8
0.6
0.2
0.0
SMILES: CISJCCC pegp:r/epeoooaaaaaeeeeeeeeeeeeee
Aecco(N S(CX D)N
retro-fallback
breadth-first
+
5y const. GP
S const., ind.
Sy rank, GP
E rank, ind.
min/median/mma SSP
0.8
0.6
0.2
0.0
100
200
100
200
100
200
100
200
SMILES COelou2nc3s
retro retro- fallbuck
breadth. first
+
retro*
+ MCTS
E const... GP
const., ind.
Eo rank, GP
rank, ind.
min/median/mmn SSP
1.0
0.8
0.6
0.2
0.0
retro-fallack
breadth-ffrst
retro*
Min/median/maa SSP vs time for individual molecules from the 190 "hard" molecule test (across? 3 trials). Algorithms are run using the SA score heuristic.
Figure G.6:
47

---

Published as a conference paper at ICLR 2024
5 const. GP
E const, ind.
fy rank, GP
E rank, ind.
min/m htn/meddin/maa SSP
0.6
0,4
0.2
100
200
100
200
100
200
100
200
SMILES: Cccccmccechnnnoooooooooooosoo/oo
retro-fallback
breadth-first
+ retro*
I MCTS
const. GP
S const., ind.
E rank, GP
E rank, ind.
thin/median/max SSP
0.8
0.6
0.2
0.0
SMILES: GISICCCC wwtp://///oooo//g/ogogooec.o potprp/oorooooooeeeeeeeeeeeoneee
Accoo(N SICX D)N
retro-fallback
breadth-first
+ retro*
+
5y const. GP
c const., ind.
S rank, GP
E rank, ind.
min/median/max SSP
0.8
0.6
0.4
100
200
100
200
100
200
100
200
SMILES COelozhmess haw.:/aaaesseenatteeoooeemoooooo
retro retro- fallbuck
breadth. first
+
retro*
+ MCTS
E const. GP
const., ind.
Eo rank, GP
Š rank, ind.
min/median/mma SSP
1.0
0.8
0.6
0.2
0.0
retro-fallack
breadth--fisst
retro*
Figure G.7: Min/median/max SSP vs time for individual molecules run with the optimistic heuristic
(same molecules as Figure G.6).
48

---

Published as a conference paper at ICLR 2024
G.2.2 RESULTS USING OTHER METRICS
Figure G.8 shows box plots of the most successful synthesis plan by the end the search. With the exception of constant independent feasibility model on GuacaMol, retro-fallback always performs least well other algorithms.
Figure s.owsswss box plots of the shortest synthesis plan (with non-zero success probability) found by all algorithms by the end of the search. Retro-fallback consistently performs least as well as other algorithms.
Figure G.10 shows the fraction of molecules for which any synthesis plan with non-zero success consistently performs better than other algorithms.
probability is found over time.
49

---

Published as a conference paper at ICLR 2024
190 "hard" molecules; SA score heuristic
f/ const., GP
T const. ind.
rank,
t rank, ind,
Most successful plan
0.4
0.2
0.0
vtro-falback
breadth-fin firor
tele
MCTS
totr- fallbackk
breadth-frst
MCTS
rroofiilbbck
Mil--kibbackk
breadd-ffrd
retro
MCTS
retro-fallbek
breadhh-fist
retro
MCTS
190 "hard" molecules; optimistic heuristic
& const,, GP
S const, ind.
rank, GP
$y rank, ind.
Most successful plan
0.2
0.0
retro-fallbck
broadit-fin fost
retr
MCTS
rato rato-Silllaek Salbbck
bread fiee
retro
MCTS
rewo- remo-fallbck fallback
breadd- first
reto
MCTS
retro- fallback
breadth- first
retto
MCTS
GuacaMol; SA score heuristic &y const, ind.
Sy const, GP
Frran,, GP
rank, ind.
Most successful plan
0.50
0.25
0.00
retro-Adllan retro-Aalback
breadth- breadti-fist Finst
retro
MCTS
retro-fllback
breadth-fitst
rotro
MCTS
retm- fallback
breadth-fie find
retra
MCTS
retro- metro-falbeck
breadth-fins
mwao
MCTS
GuacaMol; optimistic heuristic
const., GP
Er const., ind.
rank, GP
Ey rank, ind.
Most successful plan
0.75
0.50
0.25
tetoo follback
breadth-fin firet
retro
MCTS
miro- fallback
breadth-fin firs
retm
MCTS
reto- fallback
breadth- firr
retuo
MCTS
teteo fallbackk
breatth-fie fimm
retro
MCTS
Figure G.8:
Success probability of most feasible synthesis plan at end of search (i.e. maxrep.... (9) o (T; Er, 5x)) for different algorithms.
50

---

Published as a conference paper at ICLR 2024
190 "hard" molecules; SA score heuristic
t const, GP
& const, ind.
S rank, GP
S rank, ind.
00
Shortest plan
15
10
5
0
reto-fallback
breadth-fin first
remto
MCTS
vetro-falback
bread firs
mitr
MCTS
retrofialusck
breaddb-fred
rtrr
MCTS
ratro fallffakkkckk
brandth-firt
retro
MCTS
190 "hard" molecules; optimistic heuristic
const., GP
S const., ind.
SJ rank, GP
S7 rank, ind.
Shortest plan
retro-fallback
breadthh- first
retrr
MCTS
retro-flllbac
bread flos
rotro*
MCTS
retro-fallack
breadth- first
retro*
MCTS
tetm- tetrofAilback
bread ftrst
rebuu
MCTS
GuacaMol; SA heuristic
const., GP
& const., ind.
$ rank, GP
$) rank, ind.
Shortest plan
retto fallback
breadthiffrs first
ramm
MCTS
fall-fallback
breadth-ffes
retro
MCTS
retro Con-falllll Allback
breadth- first
retro
MCTS
rem- fallback
breadth-frrt
retro
MCTS
GuacaMol: optimistic heuristic
Er const., GP
E const., ind.
f rank, GP
rank, ind.
Shortest plan
15
10
tetro-fallaan Fallback
breadd-ftret
MCTS
Caro-fallbcck
breadth-fit first
retr*
MCTS
fabba-albackk
breadth-fin fint
to
MCTS
maro Pal-fallback
breaddh-fint
netro*
MCTS
Figure G.9: Distribution of lengths of the shortest synthesis plan with non-zero success probability at end of search for different algorithms.
51

---

Published as a conference paper at ICLR 2024
190 "hard" molecules; SA score heuristic
f const., GP
f const, ind.
rank, GP
E rank, ind.
Fraction solved
0.6
0.4
0.2
0.0
10"
10'
10"
10'
10'
10"
10'
10
10"
10'
10'
10"
calls to
calls B
calls B
calls to
fetro-fallbck
first
190 "hard" molecules; optimistic heuristic
f const., GP
&r const, ind.
Ey rank, GP
Ey rank, ind.
Fraction solved
0.6
0.4
0.2
0.0
10
10'
10"
10
10
10"
10
10
10'
10'
10
num. calls to
num. calls B
num. calls to B
num. calls to
retre fallb-fallback
breadth- first
retro
MCTS
GuacaMol: SA score heuristic
const., GP
const., ind.
& rank, GP
& rank, ind.
0.8
Fraction solved
0.6
0.4
10º
10'
10a
10'
10'
10'
10
10a
10'
10'
10a
num. calls to
num. calls to
num, calls B
num. calls to
retro-Ballack
breadth-first
retro
MCTS
GuacaMol: optimistic heuristic
& const., GP
& const., ind.
f rank, GP
rank, ind.
Fraction solved
0.4
10
10"
10
10'
10'
num. calls B
num. calls to
num. calls to
num. calls to B
edro-falllact
breadth-first
retrn*
MCTS
Figure G.10: Fraction of molecules for which synthesis plan with non-zero success probability was found vs time for different algorithms.
52

---

Published as a conference paper at ICLR 2024
G.2.3 RESULTS ON FUSIONRETRO BENCHMARK
Here we present results on the benchmark dataset from ResionRetro, which is derived from USPTO routes and contains 5838 test molecules (Liu et al. (023b). In addition to SSP and the fraction solved, we also evaluate performance by checking whether the outputted synthesis plans use the same starting molecules as a known ground- truth synthesis route. [iuu et al. (2023b) call this met- ric "exact set-wise matching," " but we will call precursor matching because we think this name is less ambiguous. Because this metric depends on the purchasable molecules, we use a buya- bility model derived from the inventory of Liu et al. (2023b) instead of the model derived from eMolecules used for all other experiments. This is deterministic model: molecules in the inventory are independently buyable with probability 1, and all other molecules are not buyable. We use the rank-independent feasibility model from section 6.2 All other details are kept the same.
The results after 50 reaction model calls are tabulated Table G.I As expected, retro- retro-fallback attains higher SSP scores than the baseline retro and breadth-firs search methods, regardless of the heuristic. Just like on the GuacaMol test set from section 6.2 retro-fallback also finds at least one potential synthesis route for higher fraction of molecules than the baselines. Finally, the precursor matching for the single most feasible synthesis plan is extremely similar for all methods (around 11%, with differences between the methods not being statistically significant) 20 This what one would expect: the best synthesis plans found by all methods will likely be similar; the difference between retro-fallback and the other algorithms is in the secondary synthesis plans that it finds. Overall, these results show that retro-fallback outperforms baseline algorithms on the SSP metric while being no worse than the baselines on metrics which involve only single synthesis plans.
Algorithm
Heuristic
Mean SSP (%)
Solved (%)
Precursor Match (%)
vetro-fallback retro-fallback
optimistic
0.55
0..0
10.84
SAScore
68.66
73.19
10.84
breadth-fistt
N/A
61.66++0061
10.96++0.41 6.62
retro*
optimistic
6..40
68.6240.61
11.58=00.4
retro*
SAScore
65.93:10600
69.1010.60
11.58:10.42
MCTS
optimistic
6.60
68.43
11.20
MCTS
SAScore
65.37=10.00
68.6440.61
11.13+0.41
Table G.I: Results on 5838 test molecules FusionRetro benehmark (Liu al. 2023b). Experimen- tal details and metrics are explained in section G.2.3 Larger values are better for all metrics. + values indicate standard error of the mean estimate.
Reeddrrs familiar with Liu et al. (2023b) may wonder why the precursor matching scores are much lower than what is reported in Table of Liu et al. (2023b). This is because we used the same pre-trained reaction model from Chen et al. (2020) as our single-step model, whereas Liu et al. (2023b) retrains the models using their training dataset. We did not re-train the model because it also forms the basis for our feasibility model, which loosely calibrated with the inspections of an expert chemist.
53

---

Published as a conference paper at ICLR 2024
G.2.4 RESULTS USING NON-BINARY BUYABILITY MODEL
Figure shoss buyability model from Appendix G.I.3 The results are essentially indistinguishable from Figure and Figure G.4
shows the result of repeating the experiment from section 6.2 but using the "stochastic"
SA score heuristic
const., GP
Sr const. ind.
E rank, GP
Ej rank, ind.
0.6
mean SSP
0.4
0.2
0.0
10
10
10²
10
10²
10
10²
10'
10
num. calls
num. calls
num. calls
num. calls
retrofflllhck
breadth-frsst
retro*
MCTS
optimistic heuristic
& const, GP
& const, ind.
&r rank, GP
& rank, ind.
0.6
mean SSP
0.4
0.2
10
10
10
10
10
10
10
10"
10
10
10
num calls to B
num calls to
num calls to
num calls to
retro-fallack
breaditi-frst
MCTS
Figure G.11:
SSP vs time 190 "hard" molecules using the stochastic buyability model from
G.1.3
54

---

Published as a conference paper at ICLR 2024
G.3
PLOTS FOR TIME COMPLEXITY AND VARIABILITY OF BETRO-FALLBACK FOR SECTION 66.
G.3.1 TIME COMPLEXITY
Figure G.12 plots the observed empirical scaling of retro- ettro-fallback with respect to the search graph size for experiments on the 190 "hard" molecule test set.
SA score heuristic
f const., GP
$ const, ind.
& rank, GP
& rank, ind.
10
p=1.70
p=1.44
P=1.74
p=1.51
Runtime (s)
10
10
10*
10 Nodes in g
10*
10a
10*
10
Nodes in g
Nodes in
Nodes in g
optimistic heuristic
5 const., GP
E const., ind.
S7 rank, GP
E rank, ind.
p=1.51
p-1.12
p=1.52
p=1.13
Runtime ($)
10'
10
10
8%
1-76
10
10
10
10*
10
10"
10
10
Nodes in G'
Nodes in
Nodes in
Nodes in ç
Figure G.12:
Number of nodes total runtime for retro-fallback experiments on 190 "hard"
molecule test set from section 6.2 along with log-log fit of runtime (log t = log C).
G.3.2 VARIABILITY
Figure G.13 plots the mean and standard deviation SSP values for a 25 molecule subset of the GuacaMol dataset. Analysis is in section 6.3
55

---

Published as a conference paper at ICLR 2024
SA score heuristic
y const., GP
&r const. ind.
rankk GP
Ef rank, ind.
mean SSP
0.6
0.2
hp
10
10
10¹
10'
10
10"
10
10
10"
10
10'
10
num. calls to
num. calls to
num. calls to
num. calls to
k=
k
1024
4096
optimistic heuristic
E const., GP
Sr const., ind.
& rank, GP
Eo rank, ind.
mean SSP
10
10a
10
10
10
10a
10
num. calls to
num. calls to
num. calls to
num. calls to
256
1024
4096
Figure G.13: Mean and standard deviation (over 10 trials) of average SSP for 25 molecules from the GuacaMol dataset when retro-fallback is run with different number of samples for the feasibility and buyability models.
56

---

Published as a conference paper at ICLR 2024
H LIMITATIONS
Here we explicitly list and discuss some limitations of retro-fallback and SSP.
SSP is contingent on high-quality feasibility model With low-quality feasibility model, the probabilities implied by SSP will likely not be meaningful. We think the line of research advocated for in this paper will primarily be impactful if we are able to produce better-quality feasibility models in the future.
Speed Netro-fallbact appears to be significantly slower than other algorithms. This likely comes from the need do perform updates for many samples from & and & (256 in most of our periments). In contrast, other algorithms perform simple scalar updates. However, we note that retro-fallback is used with tional cost of the search algorithm's internal computations will be less significant compared to the cost of performing an expansion. We therefore do not expect the speed of retro-fallback limit its long-term potential utilityy.
complex reaction model (e.g. transformer) then the computa-
Success as a binary notion A lot of nuance was lost by modelling reactions and molecules as binary outcomes. In practice, chemists may care about this nuance. For example, in some cir- cumstances having a low yield may acceptable, but producing the wrong product may not be acceptable. Marking both outcomes "infeasible" destroys this distinction.
Plan length Chemists generally prefer synthesis plans with a few steps as possible. Retro-fallback does not directly optimize for this (and we do not see a straightforward way extend retro-fallback to this). However, one of the main justifications for preferring short plans is that there are fewer steps that can go wrong, and therefore we expect retro-fallback have strong bias towards short plans regardless (similar to existing algorithms which apply more direct penalty to the length of synthesis plans).
Number of synthesis plans Our definition of SSP considers arbitrary number of plans, in practice chemists are unlikely to try more than around 10 plans before moving on to something else. For large search graphs with many synthesis plans, SSP may therefore lose its connection with what a chemist might do in the lab. Unfortunately, we do not believe there is a straightforward way to calculate the SSP of limited number of synthesis plans (the limit on the number of plans will likely preclude a dynamic programming solution).
57

---

Published as a conference paper at ICLR 2024
I FUTURE WORK
Relaxing assumptions If one wishes to re-insert the nuance lost by defining feasibility and buya- bility as binary outcomes, one could potentially explicitly model factors such as yields and shipping times and build a binary stochastic process on top of this. We do not have a clear idea of how retro- fallback or SSP could be generalized into some sort of continuous "degree of success", but imagine future work in this area could be useful. Relaxing the independence assumption of the heuristic function was discussed in Appendix C.4 The heuristic could potentially also be modified to depend on the remaining compute budget. Finally, using separate feasibility and buyability model implic- itly assumes that these outcomes are independent. We think this is a reasonable assumption because reaction feasibility is uncertain due not fully understanding the physical system or not having reliable model B, while uncertainty in buyability would originate from issues of shipping, etc. That being said, "virtual libraries" one area where molecule not being buyable meant that some- body else was unable to synthesize it. This may impact which reactions chemist would predict be feasible (although it seems unlikely in practice that vendor would tell you the reactions that they tried). Nonetheless, if one wanted to account for this & and & could be merged into a joint beasibility model Enr from which functions and are simultaneously sampled.
Theoretical guarantees of performance We suspect that it is possible to give theoretical guar- antee that retro-fallback's worst-case performance is better than that of retro by formalizing the scenario in section E.3 However, we were unable to complete such proof. We also expect it could be possible (and useful) to theoretically characterize how the behaviour retro-fallbaee with a finite number of samples & deviates from the behaviour of "exact" vetro-fallback in the limit of l where all estimates of SSP are exact. Such analysis might provide insight into how large h should be set to for more general feasibility models.
Benchmark
If high-quality feasibility model could be created, it would be useful to use SSP values based on this feasibility model to create a benchmark for retrosynthesis search algorithms. This might help to accelerate progress in this field, just as benchmarks have accelerated progress in other sub-fields of machine learning.
58


Reviews:
[{"review_id": "F81g4R35MM", "reviewer": "Reviewer_L6R1", "summary": "This paper proposes an algorithm for retrosynthetic planning named Retro-Feedback.\nThe algorithm is tested on a benchmark problem and achieved improving\nperformance compared with existing algorithms, including Retro* and MCTS.", "questions": "1. On page 4.\n\"... while algorithms like breadth-first search or proof-number search (Kishimoto et al., 2019) have no customizable rewards or costs of any kind.\"\\\nIn Section 5.\n\"In fact, if costs are defined to be negative log probabilities then the updates for ψ and ρ are essentially equivalent to the “reaction number” and “retro* value” updates from (Chen et al., 2020).\"\\\nThe reviewer could not find the key difference between retro-fallback and the two existing algorithms, DFPN-E [Kishimoto+ 2019] or Retro* [Chen+ 2020].\nIf we use the negative log probabilities as the proof or disproof number, retro-feedback, Retro*, and DFPN-E seem very similar.\\\nProbably, the reviewer did not understand what this sentence meant.\n\"The key difference is that retro-fallback performs parallel updates...\"\\\nWhat does \"parallel\" mean in this case?\nCould the authors elaborate on this part?\n\n1. The reviewer might have misunderstood something, but the problem described in Section   4.1 could easily avoided if the authors used a hash table for implementing the search algorithms.\n(Using a hash table is a standard technique for proof-number search.)\nIf a hash table is used, a cycle could be easily detected, so it is possible to avoid problems caused by the same molecule or reaction appearing multiple times in a path.\n\n1. P. 1.\n\"Although existing algorithms may find multiple synthesis plans, they are generally not designed to do so, and there is no reason to expect the plans found will be suitable as backup plans (e.g. they may share steps with the primary plan and thereby fail alongside it).\"\\\nThe following paper proposes an AND-OR-tree-based search algorithm for retrosynthesis, which keeps enumerating (probably) all the synthetic routes one by one in the order of some preference.\n> Shibukawa, R., Ishida, S., Yoshizoe, K. et al. CompRet: a comprehensive recommendation framework for chemical synthesis planning with algorithmic enumeration. J Cheminform 12, 52 (2020). https://doi.org/10.1186/s13321-020-00452-5\n\nMinor comments.\n1. There is an older paper that proposes to use AND-OR tree search for retrosynthesis. Please consider referring to this paper.\n> Heifets, A., & Jurisica, I. (2021). Construction of New Medicines via Game Proof Search. Proceedings of the AAAI Conference on Artificial Intelligence, 26(1), 1564-1570. https://doi.org/10.1609/aaai.v26i1.8331\nhttps://ojs.aaai.org/index.php/AAAI/article/view/8331\n\n1. Is it reasonable to assume there is always only one product?\n\n1. P. 2. \"tip nodes\"\n  In graph search terminology, I think this is called \"frontier nodes\".", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The algorithm is described in detail.\n\n- The improving performance on the benchmark problems.\n\n- Proposed a novel measure of successful synthesis probability (SSP) for retrosynthesis.", "weaknesses": "- The reviewer has several questions explained in the Questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "dH2z8rlsma", "reviewer": "Reviewer_ghCd", "summary": "This paper aims to find multiple retrosynthesis plans to cope with the uncertainty of infeasible reactions or non-buyable molecules. To achieve this goal, the paper first presents a evaluation metric SSP to quantify the probability of at least one synthesis plan can work (judged by a feasibility and buyability model), and further designs a retrosynthetic planning algorithm retro-fallback that can greedily expand molecules to maximizes SSP, specially when all existing synthesis plans currently fail.", "questions": "1. How does Algorithm 1 generate multiple possible reaction graph for a target molecule? \n2. Algorithm 1 could generate plan that is not a valid plan, e.g., when the algorithm terminates, there are still tip nodes in G'. To take such cases into consideration, can the authors also evaluate performance using two other metrics: the success rate as in Retro*, and the set-wise exact match accuracy as in FusionRetro?\n3. How sensitive the method is to the number of samples when computing line 4-6 in Algorithm 1?\n4. It is interesting to see retro-fallback with transformer can be more computational efficient, and the authors elaborate more on that (e.g., how to combine both for improvement)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The objective for addressing the uncertainty of infeasible reactions or non-buyable molecules is well-motivated and important in practice, and the paper laid out a clear and general formalism for this objective (e.g., feasibility, buyability, SSP);\n2. The path from motivation to solution is well-paved, from trivial/straightforward solution to the proposed one, and discussed the connection to related work systematically;\n3. The evaluation directly answers questions about the claims made by the paper.", "weaknesses": "1. While I appreciate the general formulation and systematic discussion about planning algorithms, given the existence of retro*, the novelty and advantage of this work (e.g., performing parallel updates using multiple samples) is not that obvious to me. I would encourage adding more discussion when talking about detailed method. \n2. Since this work focuses on multi-step retrosynthesis, related works [1] working on this should be discussed.\n\n[1] Liu, Songtao, et al. \"FusionRetro: molecule representation fusion via in-context learning for retrosynthetic planning.\" International Conference on Machine Learning. PMLR, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "POfqOCbFrA", "reviewer": "Reviewer_1DzG", "summary": "The submission has a clear description and clarifies that low-feasibility of retrosynthetic routes limit the real-world practicability in lab. The quantitative results and the comparison to prior methods may need to be clarified to support the statement of enhancing the generated route practicability.", "questions": "The quantitative results seem not adequate enough to support the findings, could the author present more quantitative results?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper draws an insight to the unperfect reactions by the one-step prediction model and redefined the buyability of real-world molecules.\n\n2. This paper uses a novel approach based on stochastic processes to solve the retrosynthetic problem.", "weaknesses": "1. More quantitative experimental results and baseline comparisons need to be clarified.\n\n2. This paper has a solid motivation and a novel solution to perform the route planning but is limited by the proposed SSP metric. SSP attempts to calibrate the feasibility of chemical reactions. However, it will not perform better than a forward one-step prediction model since they are trained on the similar reaction dataset. Besides, SAScore is a trivial metric as it prefers unrealistic large carbon rings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)