Double-Ended Synthesis Planning with Goal-Constrained Bidirectional Search

Thank you for your feedback and questions, they bring up some interesting discussion points that will help improve our work!

Reviewer: Proof of soundness and completeness of algorithm 1...

Response:

We agree that some detail regarding algorithm 1 is missing and will add the following justification in the final manuscript.

The purpose of Algorithm 1 is to add the $N$ “best” forward reactions to add to the search graph given a particular reactant $m_1$ from which we want to eventually reach some target molecule $m_2$. If we had access to the complete reaction graph $\mathcal{G}$, we could find the $N$ reactions that use $m_1$ as a reactant that minimize the total cost to reach $m_2$ in $\mathcal{G}$. Thus, $f_t(m_1, m_2)$ would yield the set of templates corresponding to these $N$ reactions, and for each of the bidirectional templates $t_i$, $f_b(m_1, m_2, t_i)$ would yield the missing reactant $m_{3,i}$ in the reaction. We instead approximate $\mathcal{G}$ with the partial reaction graph $G_{\text{FWD}}$ and train neural networks to predict the best templates and building blocks using the reactions in $G_{\text{FWD}}$. Thus, to perform a forward expansion in DESP on $m_1$ conditioned on $m_2$, we approximate $f_t$ with a trained forward template model and return the $N$ most likely templates to apply to $m_1$. For each template, if the template is unimolecular, we can simply apply the template $m_1$ and add the reaction to the search graph. For bimolecular templates, we instead use a building block model that approximates $f_b$ to predict the missing building block $m_3$. The model predicts the fingerprint of $m_3$, and we perform a $k$-nearest neighbors search on our building block set $\mathcal{B}$ to retrieve the $k$ best building blocks to use as $m_3$. Finally, we apply the bimolecular template to $m_2$ and each retrieved building block and add the reaction to the search graph.

The forward expansion algorithm relies on some limiting assumptions, which we touch on in the paper. Particularly, we ignore the existence of $\geq$3-component reactions, and assume that the missing reactant $m_3$ is a member of $\mathcal{B}$, thus precluding “convergent” bottom-up synthesis plans.

Reviewer: ...I fail to see its broader impact to the community...

Response:

We would argue that a novel contribution to synthesis planning is in itself a contribution of broad significance to the scientific community. Synthesis planning is a crucial component in the formulation and discovery of most of our medicines, as well as desirable agrochemicals and materials used across a wide swath of industries. Anecdotally, we have received interest in the algorithm from chemists, chemical engineers, and pharmaceutical companies.

Reviewer: Why Bi-directional search?...

Response:

Thank you for the constructive feedback and references! Our implementations of the unidirectional search baselines (including our top-down guided ablation, Retro* + D) do define the starting material goal constraints, and we posited that bidirectional search may be well suited for affording efficiency gains on this task. We find that DESP outperforms all baseline methods on the task, and the ablation study demonstrates that bidirectional search contributes to the improved performance. We believe that these results provide a solid empirical case for the utility of bidirectional search in synthesis planning. Though there are many exciting avenues for improvement of either unidirectional or bidirectional search with preferences and/or constraints, we view such explorations as out of the scope of this paper.

Reviewer: Could there be multiple solutions...

Response:

Thank you for raising this question. For a given target, it is essentially guaranteed that there are many solutions to the general synthesis planning problem. In spite of this, the problem is intractable for many targets without the use of ML or heuristics to prune the search space, so we frame the problem as efficiently finding some solution rather than finding the optimal solution. In any case, knowing that each reaction step is costly in the real world motivates our evaluation in Table 3 of average number of reaction steps as an indicator of quality / cost. Our heuristic cost networks are also trained with this notion of cost in mind--the training labels correspond to the optimal number of reaction steps (to reach the specified goal molecule) based on the reaction corpus.

A limitation of DESP is that the first route found is not necessarily the cost-optimal route. First, each end of our search is a variant of Retro*. As proven in [1], the unidirectional search only guarantees an optimal solution on termination with admissible heuristics, which our neural networks do not provide. Second, even with an admissible heuristic, bidirectional A* search does not guarantee optimality upon meeting [2].

We emphasize that chemists generally care more about obtaining multiple reasonable routes quickly than obtaining the theoretically optimal route, and our evaluations are designed accordingly. Nevertheless, we will summarize the discussed limitations and outlook in our final manuscript.

Reviewer: Is starting material-constraints the same as the goal constraints?

Response: Yes, thank you for raising this question; we will make an effort to be more clear / consistent about such terminology in the final version.

Reviewer: Can you point to where in the paper you discuss how you learned the goal-conditioned cost network offline...

Response:

Section 3.4 discusses the high level procedure and loss function, while details (including Figure 5) can be found in Section A.4.

[1] Chen, B. et al. "Retro*: Learning Retrosynthetic Planning with Neural Guided A* Search". ICML (2020).

[2] Kaindl & Kainz. "Bidirectional Heuristic Search Reconsidered". JAIR (1997).

Thank you for your review and positive reception of our paper! Addressing your comments:

Reviewer:

I was not able to find any major weakness in this paper. Perhaps including a small numerical example to show more clearly how the node values are computed and updated during search would help improve the quality of the presentation.

Response:

This is a great suggestion! We have created such a figure (Figure 1 in author rebuttal) and will include it in the final version of the paper.

Reviewer:

What is dn() and rn() refering to in Equations 3-6? Are these values related to the proof and disproof numbers from the A* algorithm proposed by [Kishimoto et al, 2019]?

Response:

Thank you for the question. $rn(m|G)$ is actually a quantity directly from the Retro* algorithm of Chen et al. [1]. It represents the “reaction number,” the total estimated cost of synthesizing a particular molecule $m$ based on the current search graph. $dn(m|G)$ is an analogous quantity that we developed in order to incorporate the guidance from the synthetic distance values as well. $rn(m|G)$ is more specifically described in Section A.2, and $dn(m|G)$ can be better understood by our explanation in Section A.5, as well as the new Figure 1 we have included in the author rebuttal. We will make sure these quantities are clearly described in the final version of the paper.

[1] Chen, B. et al. "Retro*: Learning Retrosynthetic Planning with Neural Guided A* Search". ICML (2020).

Thank you for your review and the kind words about our work! We address your comments one by one.

Reviewer:

By adding bidirectional search, the algorithm gets a bit complicated. Due to my lack of familiarity with the area, I'm not 100% sure how to weigh the complexity vs performance tradeoff, but I am inclined to ignore it given how clearly the algorithm is described and how easy the high level motivation for it is.

Response:

Thank you for pointing this out. We agree that the bidirectional search introduces complexity, though we would argue that some amount of increased complexity is inherent (and not unnecessary) to a double-ended search. One area to tackle the increased complexity is the forward expansion policy (Algorithm 1), which is more complex than the retro expansion policy (Algorithm 2), as some templates necessitate a second model call and k-NN search over a large database. Synthesizable molecular generation is rapidly attracting more attention ([1], [2], [3] published since we submitted this paper), and we believe a simpler or more elegant method of performing the bottom-up search can likely be integrated in future work. While it cannot trivially be plugged into DESP, ChemProjector (Luo et al. [1]), for instance, demonstrated that a lone transformer architecture can improve bottom-up planning performance by directly decoding the actions to perform, comprising an arguably less complex overall algorithm.

Reviewer:

Is the BFS top-down only or bottom-up only? Would it be useful to include a "bidirectional BFS" baseline?

Response:

The BFS is top-down only. The new baseline is a great idea! We have performed the bidirectional BFS experiment and attached the updated results table in the author rebuttal (Table 3). We find that the bidirectional BFS results in fewer node expansions on average than uni-directional BFS, but does not consistently outperform uni-directional baselines like MCTS or Retro*. Thank you for the suggestion.

Reviewer:

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

Response:

Thank you for the suggestion. Your understanding is correct, and we will make this more explicit in the final version!

Reviewer:

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

Response:

Yes, your understanding is correct. “Retro* + D” is DESP as described in Section 3.2 but without any bottom-up expansions to serve as an ablation. As with our last response, we will make these distinctions more clear in Section 4.1. We have also included Table 2 in the author rebuttal to summarize the evaluated algorithms and their components. We will include this in the appendix of the final manuscript and hope this helps with some of the points of confusion.

Reviewer:

line 106 typo, two front-to-end's

Response:

Thank you for pointing this out! We will fix that.

Reviewer:

You should check out this reference: https://dl.acm.org/doi/pdf/10.1145/3571226. They use "cuts", which I believe are similar in that using certain "cuts" lets you stake out some target in the "middle" of the search and then split the synthesis problem into two problems, one of reaching the midpoint, and then going from the midpoint to the target. (I haven't read this paper in a while, and sort of forget it, so I might be wrong) Maybe this is relevant to addressing the convergent synthesis limitation? not sure.

Response:

Thank you for the reference; it brings to mind some very interesting starting points for future work and seems related to ideas we’ve been thinking about as well. The divide-and-conquer or “middle-out” approach sounds like an intriguing method for synthesis planning and would likely naturally extend from DESP. Using something like a “cut” to break a synthesis planning task for a particularly complex molecule into subgoals (i.e. by predicting a key intermediate) also intuitively seems like a promising avenue. We will incorporate these general future directions and the reference into Section A.8!

[1] Luo, S., Gao, W., et al. “Projecting molecules into synthesizable chemical spaces” ICML (2024).

[2] Koziarski, M., et al. "RGFN: Synthesizable Molecular Generation Using GFlowNets" arXiv:2406.08506 (2024).

[3] Guo, J. & Schwaller, P. "Directly Optimizing for Synthesizability in Generative Molecular Design using Retrosynthesis Models" arXiv:2407.12186v1 (2024).

Thank you for your review! We address your comments and suggestions as follows:

Reviewer:

results from the PAroutes paper and recent work by Tripp et al and Maziarz et al indicate that there are signficantly less or even no differences between the different uni-directional search algorithms than prior work (Chen et al; Retro*) imply.

Response:

Thank you for bringing this up. Though these papers perform evaluations on a different problem setting and with different test sets (other than USPTO-190), our results on the starting material-constrained task also find relatively small differences between the two widely used uni-directional search algorithms (MCTS and Retro*) on both USPTO-190 and our new benchmark sets. We will make note of this in the final version of the manuscript.

Reviewer:

My suggestion would be more clearly flag which baseline implementation of the various algorithms used in the maintext, and also give the used hyperparams for all search algorithms.

Response:

Thank you for the suggestion! While we do outline the various baselines and relevant hyperparameters in the “Multi-step algorithms” paragraph of Section 4.1, we will also add a table to summarize descriptions of our implementations and algorithm-specific hyperparameters to make this more clear. We have included such tables in the author rebuttal (Tables 1 and 2) and will incorporate them in our final manuscript.