Retro*: Learning Retrosynthetic Planning with Neural Guided A* Search

Binghong Chen, Chengtao Li, Hanjun Dai, Le Song

Abstract

Retrosynthetic planning is a critical task in organic chemistry which identifies a series of reactions that can lead to the synthesis of a target product. The vast number of possible chemical transformations makes the size of the search space very big, and retrosynthetic planning is challenging even for experienced chemists. However, existing methods either require expensive return estimation by rollout with high variance, or optimize for search speed rather than the quality. In this paper, we propose Retro, a neural-based A-like algorithm that finds high-quality synthetic routes efficiently. It maintains the search as an AND-OR tree, and learns a neural search bias with off-policy data. Then guided by this neural network, it performs best-first search efficiently during new planning episodes. Experiments on benchmark USPTO datasets show that, our proposed method outperforms existing state-of-the-art with respect to both the success rate and solution quality, while being more efficient at the same time.

Introduction

In organic chemistry, retrosynthesis is the process of working backward from a complex target molecule to identify a sequence of reactions using simple, commercially available "building blocks." This task is plagued by a "combinatorial explosion": at every step, a molecule might be produced by hundreds of different reactions, each requiring different sets of reactants. For a synthesis involving 10 or 20 steps, the number of possible paths becomes astronomical.

Existing computational planners often struggle with this complexity. Monte Carlo Tree Search (MCTS) methods rely on slow, high-variance "rollouts," while Breadth-First Search (BFS) often prioritizes speed over the chemical quality of the resulting routes. Retro* addresses these issues by treating retrosynthesis as a guided single-player search problem, leveraging a learned neural network to navigate the massive search space efficiently.

Methodology: Searching the AND-OR Tree

Retro models the search space as an AND-OR tree. In this framework, an "OR" node represents a molecule, which can be synthesized by any one of several possible reactions. An "AND" node represents a specific reaction, which is only successful if all* of its required reactants are available.

The basic building block of the search space: an AND-OR stump representing a molecule and its potential reaction pathways.

The algorithm utilizes a neural-guided A search framework. Like the classic A algorithm used in pathfinding, Retro employs a value function $V(m) = g(m) + h(m)$, where $g(m)$ represents the cost of reactions already chosen and $h(m)$ is a neural network's estimate of the remaining cost to complete the synthesis. This value function is a multi-layer perceptron (MLP) trained on the Morgan fingerprints* of molecules to predict their synthesis costs.

The Retro* Algorithm

The search process follows an iterative cycle designed to find the optimal path with minimal computational overhead:

  1. Selection: The algorithm picks a frontier node (molecule) that has the best estimated value $V_t(m|T)$.
  2. Expansion: The selected node is expanded using an "AND-OR stump," where the one-step retrosynthesis model proposes potential reactions and their reactants.
  3. Update: The values are propagated back through the tree to update the costs of parent nodes, ensuring the search remains guided by the most current information.
The iterative Retro* search cycle consisting of selection, expansion, and value propagation.

To ensure efficiency, Retro uses a "lazy propagation" mechanism, only recalculating values when a new discovery actually changes the current best-known path. Furthermore, the authors prove that if the neural heuristic is "admissible" (providing a lower bound on true cost), Retro is guaranteed to find the mathematically optimal synthesis route.

Experimental Results

The authors evaluated Retro using the USPTO Reaction Dataset (~3.8 million reactions) and a database of 231 million commercially available molecules from eMolecules*. They also introduced a new multi-step benchmark consisting of 189 complex test routes to provide a standardized quantitative comparison.

Key findings include:

  • Success Rate: Retro achieved an 86.84% success rate* within a fixed time limit, significantly outperforming the next best method, DFPN-E, which reached only 55.26%.
  • Efficiency: Retro* required far fewer calls to the computationally expensive one-step reaction predictor than MCTS-based methods.
  • Solution Quality: The algorithm found routes that were both shorter and had lower total costs. Retro* produced four times more "best" routes (lowest cost) than the second-best competing method.

Conclusion

Retro* demonstrates that retrosynthetic planning can be solved more effectively by combining classic search algorithms with modern deep learning. By learning from historical reaction data, the planner develops an "intuition" for which molecules are easier to synthesize, allowing it to bypass the need for expensive simulations. Future work aims to extend this framework from trees to bipartite graphs to account for shared intermediate molecules across different synthesis branches.

Summary updated

Abstract

Retrosynthetic planning is a critical task in organic chemistry which identifies a series of reactions that can lead to the synthesis of a target product. The vast number of possible chemical transformations makes the size of the search space very big, and retrosynthetic planning is challenging even for experienced chemists. However, existing methods either require expensive return estimation by rollout with high variance, or optimize for search speed rather than the quality. In this paper, we propose Retro*, a neural-based A*-like algorithm that finds high-quality synthetic routes efficiently. It maintains the search as an AND-OR tree, and learns a neural search bias with off-policy data. Then guided by this neural network, it performs best-first search efficiently during new planning episodes. Experiments on benchmark USPTO datasets show that, our proposed method outperforms existing state-of-the-art with respect to both the success rate and solution quality, while being more efficient at the same time.
BibTeX
@inproceedings{chen2020retro,
  author = {Binghong Chen and Chengtao Li and Hanjun Dai and Le Song},
  title = {{Retro*: Learning Retrosynthetic Planning with Neural Guided A* Search}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=r87WEqismW5},
}
Figure