Source-linked AI summary
Retro*: Learning Retrosynthetic Planning with Neural Guided A* Search
Binghong Chen, Chengtao Li, Hanjun Dai, Le Song
TL;DR
Retrosynthetic planning must find multistep reaction routes in a huge search space, while existing approaches face costly, high-variance rollouts or prioritize speed over solution quality. Retro* uses an AND-OR tree and neural search bias learned from prior planning experience to guide best-first search. On benchmark data, it improves success rate, efficiency, and solution quality over existing methods.
Problem
Retrosynthetic planning requires searching huge multistep reaction spaces, while existing methods can use costly high-variance rollouts or emphasize search speed over solution quality.
Method
Retro* uses an AND-OR tree and a neural network learned from previous planning experience to guide best-first search toward promising molecules.
Results
Retro* significantly improves planning efficiency and solution quality over existing methods on real-world benchmark data, with a 6% success-rate gain over Retro*-0.
Takeaways & Limitations
The method provides efficient high-quality retrosynthetic planning while also supplying route data and evaluation metrics that avoid human-expert assessment.
Takeaways & Limitations
MCTS rollouts are time-consuming and potentially inaccurate in this single-player setting, while PNS variants depend on expert-designed search functions and thresholds.
Abstract
from arXiv · showhide
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.
1. Introduction
Retrosynthetic planning must search an enormous space of multistep reaction routes, while evaluation is hindered by ambiguous quality criteria and costly expert judgment. The paper introduces Retro*, an AND-OR-tree neural-guided search method, plus benchmark route data for quantitative evaluation and learning.
- Thousands of possible transformations at each step create a huge search space that challenges even experienced chemists.
- Multistep synthesis can involve 60 or more steps and hundreds of reactant choices per molecule, making routes countless for a single product.
- Quantitative evaluation is difficult because “good synthesis routes” lack an unambiguous definition and expert comparisons are costly and time-consuming.
- Retro* represents reactions and molecules in an AND-OR tree and uses a neural network to estimate synthesis costs and prioritize molecule expansion.
- The authors construct a USPTO synthesis-route dataset for quantitative route analysis and training the method’s neural components.
- The proposed learning-based planner is reported to outperform state-of-the-art methods on a real-world benchmark, while its framework can guarantee an optimal solution.
2. Background
Retrosynthetic planning searches backward through chemical transformations to find high-quality, efficient routes, but its large combinatorial search space makes planning difficult. The background introduces one-step retrosynthesis, MCTS, and proof-number search as approaches for representing and exploring this problem.
- Problem setting: A one-step retrosynthesis model predicts source reactants and associated reactions and costs for a target molecule.The cost may represent actual reaction price or the negative log-likelihood under the one-step model.
- Problem setting: Retrosynthetic planning seeks a reaction sequence that transforms commercially available molecules into a target product through backward application of one-step reactions.Plans should be chemically sound, low-cost, and limited in the number of retrosynthesis steps.
- Monte Carlo Tree Search: MCTS represents each search node as a set of molecules and expands that set by applying a predicted reaction to one selected molecule.The resulting node replaces the selected molecule with its reactants while excluding available building blocks.
- Monte Carlo Tree Search: MCTS is limited by expensive rollouts, inaccurate single-player return estimates, and sparse variance estimation caused by set-valued tree nodes.Its formulation also does not directly expose reactions as tree nodes or exploit historical planning data.
- Proof Number Search: Proof-number search models retrosynthesis as an AND-OR tree in which molecule nodes require one successful reaction, while reaction nodes require all child molecules.It selects children using proof or disproof numbers and updates these values back toward the root after expansion.
- Proof Number Search: PNS variants improve traversal and initialization, but existing methods rely on manually designed search functions and thresholds that are costly to tune and difficult to generalize.These methods prioritize proving a feasible path rather than necessarily optimizing overall solution quality.
3. Retro* Search Algorithm
Retro* performs best-first retrosynthetic search over an AND-OR tree, using neural value estimates to prioritize frontier molecules and update route-cost estimates. Its A*-inspired design supports optimality under stated value-function and search-space assumptions, while practical updates use caching and lazy propagation.
- Search representation: Retro* represents molecules as OR nodes and reactions as AND nodes in a search tree, allowing reaction and subproblem structure to be modeled explicitly.The algorithm differs from PNS and MCTS by targeting single-player route quality with global value estimates.
- Search procedure: Each iteration selects the frontier molecule with minimum estimated cost, expands it with one-step retrosynthesis proposals, and updates affected tree values.Expansion adds reaction nodes and their reactant molecule nodes, forming an AND-OR stump.
- Value function: Retro* decomposes its selection value into accumulated reaction cost and estimated future reaction cost, following the A* cost-plus-heuristic principle.The accumulated term reflects reactions already present in the tree, while the future term estimates reactions not yet discovered.
- Value function: The reaction-number recursion computes minimum estimated costs across reaction and molecule nodes while accounting for the AND requirement that all reaction children be synthesized.The resulting value function aggregates reaction costs along a route and estimated molecule costs for required descendants.
- Guarantees: Theorem 1 guarantees an optimal solution when molecule values or lower bounds are known and the halting condition compares found-route cost with the minimum frontier estimate.With reaction cost defined as negative log-likelihood, zero supplies a lower bound and the induced algorithm is guaranteed to find the optimal solution.
- Scope and limitations: The paper mainly studies tree-structured search; repeated intermediate molecules can make this representation suboptimal, while graph extension uses shortest-path computation and is left for future work.The authors state that loopy synthesis is rare in practice, motivating the tree-focused treatment.
4. Estimating Vm from Planning Solutions
Because exact molecule value functions are unavailable in practice, Retro* estimates them offline from previously constructed retrosynthetic planning routes. The learning objective combines route-cost regression with consistency constraints that prioritize the best one-step solution over alternatives.
- Motivation: Exact values for every molecule are unavailable, so Retro* estimates the molecule value function from previous planning data.The estimated value is used to compute expansion-node selection costs.
- Value model: A single-layer neural network maps a 2048-bit radius-2 Morgan fingerprint to a scalar molecule-value estimate.The hidden dimension is 128.
- Training data: The offline training data contains target molecules, best complete-route costs, one-step candidate reactions, and the true one-step reaction used in the planning solution.Routes are constructed for feasible training molecules with a predefined available molecule set.
- Training objective: Learning combines value fitting by regression with consistency learning that preserves the ordering of the best one-step solution and alternative solutions.A positive margin ensures the preferred solution retains higher expansion priority despite tolerable value-estimation noise.
- Training objective: The overall objective balances regression and consistency losses with λ, which is set to 1 by default in experiments.The supplied description specifies the default balance but not comparative results for other values.
5. Experiments
Experiments evaluate Retro* on constructed USPTO synthesis-route datasets using route quality and one-step-model calls as efficiency measures. Retro* achieves higher success, better route costs, and faster improvement than the compared search methods.
- Datasets: The route datasets contain 299202 training routes, 65274 validation routes, and 189 challenging test routes.Test routes contain reactions covered by the one-step model’s top-50 predictions, and molecules solved by heuristic BFS within a fixed time limit are removed.
- Evaluation: The evaluation compares Retro* with DFPN-E, MCTS, and greedy DFS using route cost, route length, and one-step-model calls.Reaction cost is negative log-likelihood, while model calls approximate time because each call takes about 0.3 seconds and dominates runtime.
- Overall performance: 31% more test molecules are solved by Retro* than by DFPN-E under a 500-call limit.Among Retro* solutions, 50 are shorter than expert routes and 112 have lower total costs.
- Ablation: Retro* outperforms its non-learning version by 6% in success rate, showing a gain from learning previous planning experience.Retro*-0 sets the learned value function to zero, a lower bound for valid values.
- Efficiency: Retro* leads baselines early under increasing time limits and improves faster, widening the performance gap.Performance is plotted against the number of one-step-model calls in Figure 4.
- Solution quality: Retro* produces 4× more best routes than the second-best method by total cost and performs about as well as the best method by route length.Length is not the objective optimized by Retro*.
- Example route: A sample route found by Retro* shares the expert route’s first reaction and right branch but replaces its left branch with a shorter, more probable route.Edge numbers represent reaction likelihoods, and yellow nodes denote building blocks.
6. Conclusion
The paper presents Retro* as a learning-based planner for efficiently finding high-quality retrosynthetic routes. It also introduces route-dataset construction and expert-independent evaluation, with experiments showing improved efficiency and solution quality over existing methods.
- Contribution: Retro* uses previous planning experience to bias searches on unseen molecules toward promising directions.The method is presented as a learning-based retrosynthetic planning algorithm for efficiently finding high-quality routes.
- Contribution: The paper constructs retrosynthesis datasets from public reaction data and proposes metrics for evaluating routes without human experts.The datasets support quantitative analysis of multistep retrosynthetic planning methods.
- Conclusion: Experiments on a real-world benchmark show significant improvement over existing methods in planning efficiency and solution quality.
A. Implementation details
Retro* updates cached search values only where expansion effects propagate, using sibling sharing and bottom-up delta updates to reduce unnecessary computation.
- Sibling molecule nodes share the same Vt value, so Retro* caches that value at their common parent reaction node.This avoids storing duplicate values for sibling molecules.
- Caching Vt for reaction nodes and rn for all nodes allows each related node to be visited only once during minimal updates.The cached values support selective propagation after expansion.
- The update phase processes an expanded molecule and its expansion results, then updates affected nodes in three algorithmic phases.Figure 5 maps the phases to lines 1–8, 11–16, and 17–21 of Algorithm 2.
- The implementation updates ancestor nodes bottom-up and also propagates changes to sibling subtrees through UpdateSibling.These operations are represented in Algorithm 2 and Algorithm 3.
- A O(1) delta update replaces direct O(k) or O(depth(T)) summations, and ancestor propagation stops when the expansion influence vanishes.The implementation therefore avoids unnecessary computation during single-node and ancestor updates.
B. Guarantees on finding the optimal solution
Retro* inherits A*-style optimality guarantees when lower bounds on molecule costs are available and the search halts using the stated frontier criterion.
- Retro* assumes access to Vm or a lower bound for every encountered molecule; 0 is a universal lower bound.The assumption is described as weak because zero is always available as a lower bound.
- The value function decomposes into exact partial-route cost gt and future cost ht, with lower-bound estimates producing ˆht.The practical estimate replaces molecule costs in the future-cost summation with their lower bounds.
- ˆht(m|T) is guaranteed to be a lower bound of the true future cost ht(m|T).This admissibility property supports the subsequent optimality guarantee.
- Under the lower-bound assumption, Algorithm 1 returns an optimal solution when the found route cost is no larger than argminm∈F(T) Vt(m).The theorem is obtained by combining the lower-bound lemma with the standard A* result.
C. Sample search trees and solution routes
The paper illustrates Retro* with solution routes for two target molecules, representing each one-step reaction as edges from a product to its reactants.
- Retro* produces example solution routes and corresponding search trees for target molecules A and B.The examples are presented as demonstrations of the algorithm’s generated routes and search structures.
- The search-tree diagrams use molecule boxes, reaction arrows, and colors for available, unexpanded, and solved molecules.Edge numbers denote probabilities produced by the one-step model, and only minimal solution-leading trees are shown.
- In the route diagrams, edges from the same product molecule to reactant molecules represent one-step chemical reactions.Leaf molecules in the illustrated routes are available building blocks.
D. Retro* for hierarchical task planning
Retro* is also evaluated for hierarchical task planning, where it searches AND-OR task structures for low-cost plans under expansion limits and is compared with DFPN-E.
- Retro* is applied to hierarchical task planning, where OR task nodes have alternative methods and AND method nodes require subtasks.The experiment tests whether the general planning algorithm transfers beyond retrosynthesis.
- The HTP experiment measures time by the number of task-node expansions and uses the optimal halting condition from Theorem 1.Retro* is compared against DFPN-E, identified as the best-performing baseline.
- Retro* has a slightly higher success rate than Retro*-0, and both outperform DFPN-E.Success rate is evaluated against time limits in Table 2.
- Solution quality is evaluated with approximation ratio, defined as solution cost divided by the ground-truth best solution cost.Lower approximation ratios indicate closer agreement with the best known solution cost.
E. Related Works
Related work spans reinforcement-learning approaches and learning-to-search methods, while Retro* illustrates its search trees with molecule, reaction, and one-step-model probability annotations.
- Reinforcement learning: Reinforcement-learning methods without planning have been explored for retrosynthesis through self-play value-function fitting and policy-iteration expansion policies.These methods can potentially be combined with planning algorithms to improve practical performance.
- Learning to search: Learning from previous planning experiences has been applied to Go, Sokoban, and path planning.The cited examples include work by Silver et al., Guez et al., and Chen et al.
- Learning to search: These existing learning-to-search methods cannot be directly transferred to retrosynthesis because its search space is more complicated and state-based nodes are inefficient.The passage connects this limitation to the discussion of Monte Carlo tree search in earlier sections.
- Retro* search trees: Retro* search-tree figures distinguish available, unexpanded, and solved molecules using colors and annotate edges with one-step-model probabilities.Figures 7 and 8 show trees produced for molecules A and B, respectively.