KeeA*: Epistemic Exploratory A* Search via Knowledge Calibration
Authors: Dengwei Zhao
Shikui Tu
Yanan Sun
Lei Xu
Venue: NeurIPS 2025 poster ()
Keywords: A* search
neural guided heuristic search
retrosynthesis planning
Primary area: reinforcement_learning

Abstract: In recent years, neural network-guided heuristic search algorithms, such as Monte-Carlo tree search and A$^\*$ search, have achieved significant advancements across diverse practical applications. Due to the challenges stemming from high state-space complexity, sparse training datasets, and incomplete environmental modeling, heuristic estimations manifest uncontrolled inherent biases towards the actual expected evaluations, thereby compromising the decision-making quality of search algorithms. Sampling exploration enhanced A$^\*$ (SeeA$^\*$) was proposed to improve the efficiency of A$^\*$ search by constructing an dynamic candidate subset through random sampling, from which the expanded node was selected. However, uniform sampling strategy utilized by SeeA$^\*$ facilitates exploration exclusively through the injection of randomness, which completely neglects the heuristic knowledge relevant to open nodes. Moreover, the theoretical support of cluster sampling remains ambiguous. Despite the existence of potential biases, heuristic estimations still encapsulate certain valuable information. In this paper, epistemic exploratory A$^\*$ search (KeeA$^\*$) is proposed to integrate heuristic knowledge for calibrating the sampling process. We first theoretically demonstrate that SeeA$^\*$ with cluster sampling outperforms uniform sampling due to the distribution-aware selection with higher variance. Building on this insight, cluster scouting and path-aware sampling are introduced in KeeA$^\*$ to further exploit heuristic knowledge to increase the sampling mean and variance, respectively, thereby generating higher-quality extreme candidates and enhancing overall decision-making performance. Finally, empirical results on retrosynthetic planning and logic synthesis demonstrate superior performance of KeeA$^*$ compared to state-of-the-art heuristic search algorithms.

K Epistemic Exploratory A Search via Knowledge Calibration
Dengwei Zhao', Shikui Tu': Yanan Sun? Lei Xu
SScooo of Computer Science, Shanghai Jiao Tong University Schooo of Integrated Circuits, Shanghai Jiao Tong University Guangdong Laboratory of Artificial Intelligence and Digital Economy(SZ) {zdwece, tushikui, yannasun, @ edu.
Abstract
In recent years, neural retwork-guided heuristic search algorithms, such as Monte- Carlo tree search and A" search, have achieved significant advancements across diverse practical applications. Due to the challenges stemming from high state- space complexity, sparse training datasets, and incomplete environmental modeling, heuristic estimations manifest uncontrolled inherent biases towards the actual ex- pected evaluations, thereby compromising the algorithms. Sampling exploration enhanced A* (SeeA*) was proposed to improve the efficiency of A search by constructing dynamic candidate subset through random sampling, from which the expanded node was selected. However, uniform sampling strategy utilized by SeeA* facilitates exploration exclusively through the injection randomness, which completely neglects the heuristic knowledge relevant to open nodes. Moreover, the theoretical support of cluster sampling remains ambiguous, Despite the existence of potential biases, heuristic estimations still encapsulate certain valuable information. In this paper, epistemic exploratory A' search (KeeA* *) is proposed to integrate heuristic knowledge for calibrating the sampling process. We first theoretically demonstrate that SeeA* with cluster sam- pling outperforms uniform sampling due to the distribution-awv aware selection with higher variance. Building on this insight, cluster scouting and path-aware sampling are introduced in KeeA* to further exploit heuristic knowledge increase the sam- pling mean and variance, respectively, thereby generating higher-quality extreme candidates and enhancing overall cerisionmmaking performance. Finally, empir- ical results on retrosynthetic planning and logic synthesis demonstrate superior performance of KeeA* compared to wate-offthheart heuristic search algorithms.
quality of search
Introduction
With the rise of deep learning, neural networks are utilized as guiding heuristic functions within Monte Carlo Tree Search (MCTS), which has contributed crucially the successes of AlphaGo []]
and also sparked the renaissance classical search algorithms such as A search [18). Empowered by the remarkable representational capabilities of neural networks, heuristic search algorithms have demonstrated superhuman performance across a broad spectrum of real-world applications, including games[39) de novo drug design [37] functional protein generation and optimization (48),
retrosynthetic planning of organic molecules 4 40 59], logic synthesis in very large scale integration (VLSI) design (7) and combinatorial optimization tasks such traveling salesman problem 6 53
and bin packing problem [2 Moreover, heuristic search plays critical role in state-of-the-arr
Correspondence authors are Shikui Tu and Lei Xu.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

large language models by facilitating the efficient traversal of expansive solution spaces and enabling multi-step pocision-making through structured reasoning 45 [58]
A" search [8] is a best-first search algorithm that selects the node with the maximum estimated evaluation reward f at each iteration for expanding. For a given node n, f(n) is defined as the summation of gn)), the cumulative reward from the initial node no to n, and h(n), the estimated reward from n to the desired goal, i.e. f(n) - s(n) + h(n).
g(n) is derived from the historically traversed path and thus exactly corresponds the true cumulative reward g" (n)). In contrast, h(n) a heuristic estimation of the unobserved future reward, which typically diverges from the true remaining reward h" (n). A is theoretically guaranteed identify an optimal solution if hu(n) is admissible, i.e., h(n) 2 h²" (n), even in the presence of estimation bias. Nonetheless, inaccuracies in the heuristics may still substantially degrade search efficiency through inducing suboptimal node expansions. In practical applications, constructing an accurate heuristic function h((n)) challenging due the high complexity of the state space and the sparsity of available training data. Moreover, since search algorithms are inherently model-based optimization methods, inaccuracies in state transitions and immediate reward feedback, stemming from incomplete environment modeling, further compromise search performance.
SeeA* 600 introduces selective sampling process to construct dynamic subset, incorporating exploratory behavior into A search to escape from local optimal branches. Although theoretical analysis demonstrates that even uniform sampling can improve the efficiency of A" search, it entirely disregards heuristic information associated with open nodes, which, despite inherent potential biases, still encapsulate certain valuable guidance for the search process. Furthermore, while experimental results suggest that advanced strategies, such as cluster sampling, increase the likelihood of selecting higher-quality nodes and thereby contributing enhanced decision performance, the theoretical benefits remain unclear.
In this paper, KeeA*, an epistemic exploratory A search algorithm enhanced by knowledge calibra- tion, is proposed to address the aforementioned limitations of SeeA*. The main contributions are summarized from three aspects
We theoretically demonstrate that cluster sampling produces a candidate set with more favorable extrema than uniform sampling by embedding distributional knowledge into the cluster structure, and increasing both the expected mean and variance of sampled nodes contributes improved decision-making performance.
Cluster scouting and path-aware sampling are introduced by KeeA" to enhance the quality of the sampled candidate set by injecting epistemic knowledge into the sampling. We first show that for any two nodes, a greater disparity in their f-values corresponds to higher likelihood that the node with the larger f also exhibits a greater true reward f", despite the presence of prediction errors. Accordingly, cluster scouting is proposed by first evaluating clusters based on /-statisticc and subsequently allocating a larger sampling budget to clusters with higher estimated quality to improve the expected mean of candidate nodes. Furthermore, path-aware sampling mechanism is proposed to incorporate historical path dependencies into the intra-cluster sampling process, thereby increase the variance of selected nodes.
Experiments are conducted on two real-world applications: retrosynthetic planning in organic chemistry and logic synthesis in VLSI design. KeeA* demonstrates superior performance over SeeA* and other tfate-of-the-at heuristic search algorithms, achieving higher success rates in problem-solving and superior solution quality.
2 Related work
A* search 18]
is foundational algorithm in heuristic search and has been extensively applied
across diverse application domains, including route planning [46] 47 combinatorial games such as Rubik's Cube and sliding puzzles M. motion planning in robotics 14 and so on. Monte Carlo Tree Search (MCTS) [3] [0] integrates stochastic node sampling with a tree-based search framework to efficiently explore large search spaces. Upper Confidence bounds applied to Trees with predictor
"The source code is publicly available at

---

implemented via deep neural networks (PUCT) has been adopted in AlphaGo 41 and its successors achieving superhuman performance and also sparking the renaissance of classical search algorithms. However, constructing accurate heuristic functions for complex real-world applications remains a significant challenge due to the combinatorial explosion of the search space and the limited availability of high-quality training data. For example, heuristic estimations in retrosynthetic planning exhibit substantial overfitting [59], thereby impairing search effectiveness by misdirecting expansion priorities. Furthermore, in applications such as functional protein design [22 [56] and de novo drug design [36], reward functions employed for learning are typically obtained through in silico simulations, which intrinsically diverge from real-world ground truth. The inherent complexities of environment modeling further hinder the effective development of robust heuristic functions.
42 39
Exploration has been incorporated into A search to escape local optima induced by biased heuristic functions. <-greedy node selection has been shown to improve the coverage of search algorithms, even when multiple enhancements have already been integrated into LAMA 44 Type-WA' [9] augments Weighted A with type-based exploration [51, randomly selecting one of T node types within the focal list [34] for expansion. LevinTS 33 incorporates node depth as a penalty term to encourage exploring alternative branches, Gumbel MuZero [12] employs Gumbel-Top-4 sampling 225 by combining Gumbel noise gummeel(a) with policy logits to generate candidate action set for subsequent selection. MENST [50] combines MCTS and entropy regularization for the first time to explicitly promote exploration. By employing relative entropy and Tsallis entropy regularization terms, RENTS and TENTS [I] significantly enhance the convergence efficiency of MCTS. SeeA
[59 600 introduces exploration into A search by stochastically sampling a subset of open nodes and selecting the expansion node from this candidate set.
Retrosynthetic planning aims to identify feasible synthetic route by recursively decomposing a target molecule into simpler and commercially available precursors. To efficiently explore the vast combinatorial space of chemical reactions, search algorithms such as MCTS 19
40 57 A"
2 60 and depth-first proof-number search [24], in conjunction with a single- step predictor, are extensively utilized to address this challenging problem. Logic synthesis (LS) is a critical step in very large scale integration (VLSI) design, transforming high-level abstract representations of logic circuits into gate-level implementations by optimizing area, delay, and power consumption. Recent developments utilizing reinforcement learning (8] (0] [00]28,22 (3]
search 4 [ 2
27
and search algorithms 73 have demonstrated substantial improvements in both the efficiency and scalability of solving LS tasks.
3 Preliminaries on A search
In A" search, nodes in the search tree divided into OPEN set O, which consists of unexpanded leaf nodes, and a CLOSED set C, containing nodes that have already been explored. At each iteration, the node E O with the maximum path reward (n) is selected, i.e., n arg max,'co f(n'). ). If n corresponds to the target goal, the search process terminates successfully. Otherwise, n is moved to the CLOSED set C, and its successors (n() are added to the OPEN set O for subsequent exploration, i.e., C + C (n), O + 0 {n) U (n). The greedy best-first expansion strategy of A search makes it highly susceptible getting trapped in local optima due the biases in the estimated fvaluus. SeeA" introduces exploratory capabilities to the A' search through the dynamic construction of candidate set D, achieving superior efficiency even with uniform sampling when the estimation bias of f is substantial. In SecA", node selection involves first constructing D from the OPEN set O using a sampling strategy, and then selecting the node n with the highest f-value from D for expansion. The expansion probability of the optimal node n² in O by SeeA* is given by
P(n" is expanded) = P(n D) x P(n arg max f())[n" E D). RDD
(2)
Advanced sampling strategies not only increase the probability of including n² in D, but also enhance the likelihood of its selection from D for expansion due to the reduced candidate set size, thus enhancing the efficiency of the search process.
Uniform sampling employed in SeeA" is con-differentiated sampling strategy that does not incor- porate any node-specific knowledge, treating all nodes equally without prioritizing more promising candidates. Cluster sampling first partitions the nodes in O into multiple clusters, from which an equal number of nodes are uniformly sampled from each cluster to construct the candidate set D. Experimental results demonstrate that cluster sampling outperforms uniform sampling, yet the
3

---

underlying mechanism remains unexplored. This paper first theoretically establishes that cluster structure introduces node-specific knowledge to calibrate the epistemic process, thereby enhancing the quality of the constructed 'D. Then, KeeA* is proposed to leverage domain-independent node knowledge for constructing more efficient search algorithm.
The superiority of cluster sampling
For the cluster sampling strategy in SeeA", N nodes in the OPEN set O are partitioned into K disjoint clusters, each containing N; open nodes:
(0,, ,K] - O = O and vi bondvijj,ooo i,,0, = 0}.
(3)
The probability node belonging to the i-th cluster given by pf = N,/NV. The mean and variance of the true reward f for nodes in O; are assumed to be 14; and o. respectively. For uniform sampling, N nodes are sampled from O to construct the candidate set Du. while in cluster sampling, N nodes sampled from each cluster O constitute De together. The probability of nodes in D being sampled from O2 is given by p = N; /N' and M denotes the extreme value of f among the No candidate nodes:
Ma max (m)), E {u, c). nED,
It is worth noting that node with larger f closer to the optimal solution, whose path reward is max Given the preceding assumptions, the following theorem established.
The candidate set constructed by cluster sampling closer to the optimal solution compared to uniform sampling, exhibiting a larger expected extreme value of f":
Theorem 4.1
[M, > [Ma]
(5)
To prove Theorem 4.1 two lemmas are provided follows.
Lemma 4.2 Suppose there are K component distributions, each with probability weight pa. mean μt and variance of. Then, the mean and variance of the overall distribution are:
Enane
1 Σ PiPts o² =pEoo
pio
Σ Ping
Lemma 4.3 Suppose a population consists of N samples with mean i and variance o². A subset 'D with n samples is drawn without replacement. Let X and 2 denote the mean and variance of D. respectively. Then:
N n o² N
E u.
Var[&]
E| o²
we demonstrate that D.. constructed through cluster sampling with P = pf. has the same expected mean but larger expected variance compared to Da, which is obtained via uniform sampling:
Leveraging Lemma 4.2 and 4.3
(D.) = (ūw), ED. > (o.)),
(8)
where Ae and j., denote the means of real path reward f for nodes in De and Da, respectively, and de and 7 are the corresponding variance. The detailed proof can be found in Appendix A According the Gumbel extreme value theorem, the expected value of M for samples with mean of y and
variance of o² is
27 + In (n' /44 Inn))
E 1
222lnn
constant. Therefore, combining with Equation & obtain that ED_ [Ma] is larger than ED, [..] because cluster sampling entails a higher expected variance, and Theorem 4.1 is proved. Let Q denote the of near-optimal nodes, defined as,
where r is the
2 (n) 2 (1 (1)=)fmm =)fmaz {u,c).
(10)

---

where E < 1 is hyperparameter that controls the gap from optimality. Based on Theorem the likelihood that D. contains least one near-optimal node exceeds that of Dus i.c. P(3n Q such that n E D.) > P(3n E Q such that D.). According to Equation 2 cluster sampling increases the probability of including near-optimal nodes, thereby promoting broader exploration of high-quality regions in the search space and leading to improved solution quality. Under the framework SeeA", drawing m samples from N nodes with uniform sampling yields a probability of m/N for including the optimal node. Under cluster sampling, m/K nodes are sampled from each the K clusters uniformly. If the optimal node resides in a large cluster with more than N/ nodes, the probability of selecting the optimal node under cluster sampling will be lower than m/N in uniform sampling, leading to reduced search efficiency. Theorem 4. offers a complementary perspective by first showing that cluster sampling increases the variance of collected candidates. Leveraging the extreme value theorem, a higher expected maximum is achieved by cluster sampling, providing theoretical justification for the advantage of cluster sampling in SeeA"
5 KeeA* search algorithm
In SeeA* search [60], cluster sampling leverages the underlying node distribution prior knowledge to calibrate the epistemic process, thereby improving search efficiency over uniform sampling. However, the strategy of equally allocating candidates across clusters and performing uniform sampling within each cluster remains suboptimal. What's more, the optimal sampling policy is inherently dependent on the distribution of the true path reward f of nodes within each cluster. which is typically inaccessible due to estimation bias. A detailed analysis is provided in Appendix C To address these limitations, KeeA* proposed incorporate distributional knowledge for more effective guidance of the epistemic process. Specifically, cluster scouting and path awahe sampling are introduced to respectively improve the mean and variance of the sampled nodes, thereby enabling the construction of higher-quality candidate sets.
! Cluster scouting
Cleeet
Z Knowledge- guided sampling
Figure The sampling procedure of cluster scouting sampling.
5.1 Cluster scouting
Despite the inherent bias of f. it still encapsulates certain valuable information. Let N(.,) denote Gaussian distribution. Theorem 5.1 established, and a detailed proof provided Appendix D
Theorem 5.1
Let the true path reward f be independently and identically sampled from N ((gg 22) and assume that the prediction errors of f follow Gaussian distribution, i.e.. f(n) ~ (n), (.). For any two nodes nı and n2, the likelihood that f (m1) > (m2) given by:
1
(f - ((22))
((( > (*(22) = exp
(11)
40 +0²) cos?
where < w/2 2 a constant, and the probability P( (m1) > (22))) increases monotonically with the magnitude of the discrepancy between f(11) and f(22).
5

---

In fact, only the derivation of Equation 11 explicitly relies on the Gaussian noise assumption. For general noise distributions, the probability P (nf) f (22)) remains monotonic function of the difference /i /2. More details are provided in Appendix B
According Theorem 5.1 nodes with larger f-values exhibit higher likelihood of being closer to the optimal solution relative to others. Motivated by this insight, cluster scouting is proposed by initially refining cluster identification through scout sampling, after which the sampling proportion strategically increased within near-optimal clusters to enable the construction of a superior D. As depicted in Figure the sampling procedure consists of two stages:
An equal number of nodes, denoted (D1, D2, Dx} } uniformly sampled from each cluster O, to perform scouting and evaluate the quality of each cluster according to:
Eif: D.)
sC,
(12)
[ +
where B[-] and SDD[-] denote the mean and standard variance of the estimated f-values of the nodes D, respectively. k introduced to avoid a zero variance. E|-] is utilized to assess the quality of cluster, while [ID mitigate the impact of within-cluster variance.
Cluster sampling is performed by selecting nodes from K clusters, with the number of nodes selected proportional to the following probability:
exp (O,))
1
p
X Lj=1,... exp(score((O))} + +1 a)
(13)
K'
where E [0, 1] is hyperparameter balancing exploitation of score(O:) and uniform exploration across clusters.
As higher f-values indicate a greater likelihood of superior f*, allocating larger sampling probabilities pf to such clusters increases the expected mean of ãe compared to the uniform allocation strategy used in SeeA*. consequently yielding higher expected extreme value Mc shown in Equation
5.2 Path-aware sampling
Beyond optimizing inter-cluster sampling distributions, conducting more effective intra-cluster sampling is also instrumental. While cluster scouting improves the expected mean of the sampled D... path-aware sampling proposed leverage path information enhance intra-cluster exploration, resulting in greater sampling variance than uniform strategies.
CLOSED
Node
d=2
OPEN
d=3
d=4
Candidate
Node
d=
Figure 2: Comparison between uniform sampling and path-awar sampling within cluster O,,
As the number of nodes grows exponentially with depth, uniform sampling disproportionately selects nodes from deeper branches as candidates, reducing exploration of shallower regions. When heuristics learned by neural networks violate the admissible condition due to their black-box nature, the search process is more susceptible to being trapped in this local optima. As illustrated in Figure 2 node depth d(n) is employed as path information to bias sampling toward shallower nodes, mitigating the concentration of samples within limited deeper branches. Enhanced exploration facilitates the generation of more diverse candidate set D. thereby increasing the sampling variance of and

---

consequently improving the expected extreme value Mc, according to Equation 9 probability of node n in cluster O is calculated by
The sampling
exp (())
No exp)(nn) pi(n) プラ=1
(1
(14)
N
where 8 E [0, 1] is hyperparameter that controls the trade-off between depth-awe aware exploration and uniform sampling.
In summary, KeeA* improves the mean and variance of candidate nodes through cluster scouting and path-aware sampling, respectively, which leads to higher extreme values of the real path reward f and yields solutions that are closer the optimum. Algorithmic details are provided in Algorithm
Algorithm 1: KeeA* " search algorithm
Input: root node the number of cluster K, candidate size No, and heuristic function f. Initialize CLOSED set <- and OPEN set O t- i with empty clusters O₂ <- 0, and cluster centers (w; i= 1, 1,.... K
Assign root to the nearest cluster = arg minj=1,.... KK [ww(no) (olo))-- - w,ll Update cluster: O; O U }no}. w, + wi + + x (w(no) w.)
repeat
Compute cluster-level sampling distribution {pi ... pi } via Equation 13 Sample 5e x N nodes from each cluster O using Equation 4 to form candidate set D.
Node selection: n arg maxneD f (n).
if is the goal node then return
else
Move from O C: C <- CU (n), 0 0 (n). for each child node E (H do
Assign nee the nearest cluster: i arg minj=1.-. .... K [[w()n)) nc) - wz 112
Update cluster: O + O U (ne). w, t wi + 17 x (w(ne) wi). end for end if
until O empty return False
6 Experiments
To evaluate the effectiveness of KeeA*, we consider two real-world applications: retrosynthetic planning in organic chemistry and logic synthesis in VI.SI design. In both domains, heuristic functions are susceptible to significant overfitting due to the large state-space complexity and limited high-quality training data, posing significant challenges for search algorithms (59 60). Additional application-speeific details are provided in Appendix [D and F All experiments are conducted on NVIDIA Tesla V100 GPUs and an Intel(R) Xeon(R) Gold 6238R CPU. Guiding heuristic models consistent with SeeA* for fair comparison.
6.1 Results on retrosynthetic planning
Retrosynthetic planning aims to iteratively decompose target molecule through predicted chemical reactions until all intermediate molecules are identified as commercially available building blocks. A the policy to generate candidate reactions
single-step retrosynthetic prediction model is employed for synthesizing input molecules, and only top 50 reaction templates ranked by predicted probability maintained form the legal action space. A heuristic value function is employed to estimate the synthesis cost. Each molecule is represented as a 2048-dime sill--imenssonal Morgan fingerprint vector [38,, which serves the input to the heuristic functions, and the last hidden state in the value network employed as the embedding feature wn)) for clustering. Both the single-step model and the cost estimator are adopted from R (23) and consistently used guide the baseline algorithms.
Experiments are conducted on the widely used USPTO benchmark, which comprises 190 target molecules [4) and additional 4719 molecules collected from logP (5), logS [54), Toxicity LD50
7

---

Table I: Success rate seven test dataset for refrosynthetic planning problem (%).
Algorithm
USPTO
logP
logS
Toxicity LD50
Ames
BBBP
ClinTox
Mean
Retro"
86.84
53.96
67.08
55.39
57.40
47.87
38.69
54.66
Retro"+
91.05
61.14
69.29
59.98
63.51
52.46
43.15
59.93
A'
88.42
58.71
68.55
59.17
62.98
51.80
42.04
58.73
WA"
84.21
58.43
68.30
59.52
62.89
52.30
44.59
58.87
MCTS
89.47
58.15
67.08
58.26
63.42
52.95
46.34
59.20
LevinTS
96.84
61.14
70.76
60.32
64.84
54.92
43.63
61.01
PHS
87.37
55.45
65.60
57.00
59.96
50.98
39.01
56.16
SeeA" (enA*(Uniform)
96.84
63.37
71.00
62.73
67.32
56.39
45.70
62.97
SeeA"(Cluster (Clusterr
98.42
64.12
72.73
63.53
66.08
57.54
47.77
63.56
KeeA" w/o
98.94
63.93
72.48
63.76
66.52
57.05
48.25
63.74
KeeA*
98.94
64.21
72.97
63.30
66.60
57.21
48.25
63.76
Ames [7]. BBBP (29), and Clin'Tox 15] dataset. Molecules from the eMolecules database" used as the set of commercially available building blocks. As the majority of computational overhead arises from invoking the single-step retrosynthetic prediction model, all search algorithms constrained a maximum of 500 calls 10 minutes of wall-clock time, following prior works To avoid redundant computation, predictions from the single-step model are cached and reused when the same molecule revisited [30]. The candidate size fixed at N 50, and the number of clusters is K = 5, which are consistent with SeeA". The hyperparameters and / in KeeA* are set 0.5 and 0.8. respectively.
49).
4 [23]
Synthesis success rate and average solution length are employed as valuation metrics for model comparison. The success rate is defined as the percentage of target molecules for which complete and valid synthesis route successfully identified. To penalize failures, molecules for which no valid route found are assigned fixed path length of 32. Experiment results are summarized in Table 1 and Table 21 KeeA* achieves a success rate of 63.76% across seven benchmark datasets, slightly outperforming SeeA*, which attains 63. 63.56%. A McNemar test is conducted compare the success rates of KeeA* and SeeA" on paired binary outcomes. The chi-square statistic is 3.615 with p-value 0. 0.0286(<< 0.05). indicating that KeeA* achieves a statistically significant improvement in success rate over SeeA*. See Appendix G for additional details. The average path length generated by KeeA* is 14.14. shorter than SeeA "ecAA's T4.31. When considering only successfully synthesized molecules, KeeA* achieves an average path length of 3.95, significantly shorter than SeeA 's 4.17. KeeA* highlighting its overall superiority by not only increasing the likelihood of finding valid synthesis route but also identifying shorter and more efficient reaction pathways.
In terms of computational cost, SeeA" with cluster sampling requires average runtime of 37.98 seconds per molecule on the USPTO benchmark, while KeeA* costs a comparable 37.40 seconds, demonstrating that KeeA* improves synthesis quality without introducing significant computational overhead. Ablation studies reveal that removing cluster scouting module degrades both success rate and solution quality, with the average solution length of successful cases increasing to 4.01, though still surpassing SeeA'. Both cluster scouting and path-aware sampling contribute to the overall effectiveness of synthesis planning.
6.2 Results on logic synthesis
For the logic synthesis task, an And-Inverter Graph (AIG) is optimized to minimize the area-delay transformations. 7 legal transformations are
product (ADP) via a sequence of functionality-preserr allowed, and the action sequence is constrained be 10 steps. Due diverse functionalities in VLSI design, the logic synthesis problem exhibits substantial combinatorial complexity. The widely used resyn2 transformation script is adopted as the baseline 8 32], and the solution is evaluated by 1 ADP(S)/AD) (F((S)/AD((resnn2)) where ADP is approximately estimated using the ABC synthesis tool 12 MCNC benchmark circuits {C1 ~ C12) 551 are used for evaluation. The guiding heuristics
http:://dwwloo emolecules.. com/ (arree2222311 02-01/
Values marked in red and blue correspond to the best and second beotddbbest performance, respectively. CS is short
for cluster scouting.

---

Table 2: Solution length on seven dataset for retrosynthetic planning problem.
Algorithm
USPTO
logP
logS
ToxicityL.DSi
Ames
BBBP
ClinTox
Mean
Retro"
9.71
16.67
12.63
16.24
15.91
18.29
21.11
16.58
R
8.74
15.01
12.26
15.23
14.67
17.37
20.06
15.44
A'
9.27
15.64
12.44
15.49
14.94
17.56
20.26
15.78
WA*
10.16
15.62
12.46
15.39
14.90
17.36
19.43
15.66
MCTS
8.23
16.27
13.00
15.99
15.05
17.35
19.15
15.91
LevinTS
7.45
15.55
12.48
15.74
15.02
17.25
20.24
15.74
PHS
10.19
16.56
13.29
16.11
15.72
17.79
21.09
16.51
s-Greedy
43.78
23.21
12.76
16.70
16.32
18.43
23.82
19.88
SeeA' (Uniform)
7.34
14.64
11.81
14.76
14.00
16.62
19.41
14.85
SeeA (Cluster)
6.48
14.05
11.20
14.21
13.79
15.85
18.65
14.31
KeeA" w/o CS
6.15
13.95
11.10
14.03
13.70
15.66
18.45
14.16
KeeA"
5.89
13.93
10.96
14.19
13.55
15.82
18.41
14.14
remain consistent across the different search algorithms, and the final hidden embedding vector is employed for clustering. The candidate size is fixed at N 10, with the number of clusters K Five nodes are sampled from each cluster for scouting. Hyperparameters and are set to 0.5 and 0.8, respectively.
Experimental results are summarized in Table KeeA* achieves 25.2% ADP improvement, surpassing SeeA* with cluster sampling, which attains 23.5% improvement. SeeA (Cluster) outperforms KeeA* only of the 12 benchmark circuits, highlighting the strong generalization of KeeA" across diverse design instances. With only the path-aware sampling module enabled, KeeA* still achieves 24.0% performance improvement, exceeding SeeA* and highlighting the complementary contributions of both proposed components.
Table 3: The ADP reduction (%) rates against resym2 MCNC testing datasets.
Algorithm
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
Mean
DRiLLS
18.9
6.7
8.0
13.0
38.4
19.1
5.4
18.0
14.3
18.6
6.6
11.0
14.8
Online-RL
20.6
6.6
8.1
13.5
39.4
21.0
5.0
17.9
16.2
20.2
4.7
11.4
15.4
SA+Pred.
17.6
17.0
15.6
13.0
46.5
18.2
8.5
23.6
19.9
17.6
10.0
20.3
19.0
MCTS
17.1
15.9
13.1
13.0
46.9
14.9
6.5
23.2
17.7
20.5
13.1
19.7
18.5
ABC-RL.
19.9
19.6
16.8
15.0
46.9
19.1
12.1
24.3
21.3
21.1
13.6
21.6
20.9
A" search
18.3
16.6
19.7
15.7
43.6
15.2
13.3
25.5
19.4
20.8
7.5
18.8
19.5
PV-MCTS
17.3
20.0
27.9
20.1
27.3
20.7
13.5
24.7
14.3
14.1
14.7
20.0
19.5
PHS
21.4
17.1
11.7
8.4
47.9
5.2
8.7
10.2
20.5
12.0
7.3
20.8
15.9
SeeA (Uniform)
21.9
18.7
21.9
16.5
37.2
13.8
12.3
25.5
21.5
24.1
21.5
24.0
21.6
SeeA (Cluster)
23.2
20.8
22.7
16.2
45.9
22.6
13.4
24.8
22.4
24.2
20.3
25.1
23.5
KeeA" w/o CS
21.0
21.6
24.5
15.5
50.8
26.5
12.1
24.8
22.4
27.2
17.5
23.6
24.0
KeeA*
23.7
24.6
28.3
16.2
53.6
24.2
14.7
26.0
22.4
24.5
16.9
26.7
25.2
6.3
The impact the hyperparameters
The hyperparameter in cluster scouting controls the balance between exploration and exploitation of the heuristic function I the allocation of candidate nodes across clusters. When a 1.0, number of candidates sampled from each cluster is fully determined by the evaluations of scouted nodes, which may lead to suboptimal performance due to hcuristic bias. Conversely, setting a = results in uniform allocation across clusters, failing to exploit epistemic knowledge of cluster quality and thereby reducing search efficiency. Similarly, 3 controls the trade-off between exploration and exploitation during intro-cluster sampling. When 3 1.0, the sampling process is dominated by biased path information, misguiding the search toward a breadth- results in uniform sampling, disregarding potentially informative knowledge. As presented in Appendix excessively large or small values a and 3 lead to performance degradation, emphasizing the necessity of tuning the hyperparameters ensure performance robustness.
strategy. Conversely,
K represents the number of clusters, which critical parameter of KeeA*. An excessively small K induces under-fitting, leading to a model of limited flexibility, while overly large K risks

---

overfitting to collected states. Both extremes impair the efficacy of decision makiing during search, highlighting the importance appropriate cluster number K selection optimize the efficiency of KeeA". Details are provided in Appendix
To quantify KeeA"ss variability induced by randomness, we executed three runs for each of ten random seeds on the USPTO test set. A T-test with the significance level is used to compute the error intervals. SeeA" not only exhibits larger variance across multiple runs but also shows greater performance fluctuations under different random seeds, highlighting the superiority of KeeA over SeeA* * (Cluster) with respect to stability. More details are provided in Appendix g
7 Conclusion
In this paper, we first theoretically demonstrate the superiority of cluster sampling over uniform sampling within the SeeA" framework and reveal that the optimal sampling strategy is intrinsically determined by the underlying distribution of the real path reward f*. Cluster scouting and path- aware sampling is proposed by KeeA' to exploit node distributional knowledge for epistemic calibration, enhancing the mean and variance of sampled candidate nodes, respectively. The likelihood of incorporating nodes closer to the optimal solution into the candidate set is increased, thereby enhancing the decision-making efficiency of search algorithms. Due to the dynamic construction of candidate set, KeeA* exhibits slight randomness. Nevertheless, extensive empirical experiments across thousands of test instances and statistical hypothesis testing results validate the effectiveness and robustness of KeeA"
Beyond improving the predictive accuracy of the heuristic function, increasing the likelihood of sampling the optimal solution within smaller D can also significantly improve search efficiency. Besides raising the mean reward of candidate nodes, enhancing variance improves the likelihood of sampling near-optimal nodes, providing promising direction for future research. This work is still in the nascent stages and has not yet been applied to real-world scenarios directly impacting everyday human activities. Substantial ethical risks or detrimental social impacts are not anticipated.
8
Acknowledgement
This work was supported by the National Natural Science Foundation of China under Grant No. 62172273, 62174110, by the Science and Technology Commission of Shanghai Municipality under Grant 245 14300, and by the Shanghai Municipal Science and Technology Major Project under Grant No. X0ZISH2000000 Natural Science Foundation of Shanghai 23ZR14332000
References
[1] Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the rubik's cube with deep reinforcement learning and search. Nature Machine Intelligence, 188):366-363, 2019.
[2] Robert Brayton and Alan Mishchenko. Abe: An academic ceabustrill-strnnthh verification tool. In Computer Aided Verification: 22nd International Conference, CAV 2010, Edinburgh, UK, July 15-19, 2010. Proceedings 22, pages 24- Springer, 2010.
[3] Hyeong Soo Chang, Michael C Fu, Jiaqiao Hu, and Steven Marcus. An adaptive sampling algorithm for solving markov decision processes. Operations Research, 53(1):126-133) 2005.
[4] Binghong Chen, Chengtao Li, Hanjun Dai, and Le Song. Retro*: learning retrosynthetic planning with neural guided * search. In International Conference on Machine Learning, pages 1608-1616. PMLR, 2020.
[5] Tiejun Cheng, Yuan Zhao, Xun Li, Fu Lin, Yong Xu, Xinglong Zhang, Yan Li, Renxiao Wang, and Luhua Lai. Computation of octanol- water partition coefficients by guiding an additive model with knowledge. Journal of chemical information and modeling, 476))2140-21488 2007.
[6] Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tierney and Youngjune Gwon. Simulation guided beam search for neural combinatorial optimization. Advances in Neural Information Processing Systems, -7777607777 2022.
10

---

[7] Animesh Basak Chowdhury, Marco Romanelli, Benjamin Tan, Ramesh Karri, and Siddharth Garg. Retrieval-guided reinforcement learning for boolean eircuit minimization, In The Tweifth International Conference on Learning Representations, 2023.
[8] Animesh Basak Chowdhury, Benjamin Tan, Ryan Carey, Tushit Jain, Ramesh Karri, and Siddharth Garg. Bulls-eye: Active few-shot learning guided logic synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022.
[9] Eldan Cohen, Richard Anthony Valenzano, and Sheila A Mcllraith. Type-wa*; Using explo- ration in bounded suboptimal planning. In IJCAL, pages 4047-4053, 2021.
[10] Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pages 72-83. Springer, 2006.
[11] Tuan Q Dam, Carlo D' D'Eramo, Jan Peters, and Joni Pajarinen. Convex regularization in monte- carlo tree search. In International Conference on Machine Learning, pages 2365 2375. PMLR, 2021.
[12] Ivo Danihelka, Arthur Guez, Julian Schritwieser, and David Silver. Policy improvement by planning with gumbel. In International Conference on Learning Representations, 2022.
[13] Jacob Devlin, Ming- Weig Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR, abs/ 1 810.04805, 2018.
[14] František Duchoñ, Andrej Babinec, Martin Kajan, Peter Beño, Martin Florek, Tomás Fico, and Ladislav Jurišica. Path planning with modified a star algorithm for a mobile robot. Procedia engineering, 96:59-69, 2014.
[15] Kaitlyn M Gayvert, Neel Madhukar, and Olivier Elemento. A data-driven approach to predicting successes and failures of clinical trials. Cell chemical biology, 23(10):1294-1333 1301, 2016.
[16] Peng Han, Peilin Zhao, Chan Lu, Junzhou Huang, Jiaxiang Wu, Shuo Shang, Bin Yao, and Xian- gliang Zhang. Gan-retro: Retrosynthetic planning with graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pages 4014-4021, 2022.
[17] Katja Hansen, Sebastian Mika, Timon Schroeter, Andreas Sutter, Antonius Ter Laak, Thomas Steger- Hartman, Nikolaus Heinrich, and Klaus- Robert Muller. Benchmark data set for in silico prediction of ames mutagenicity. Journal of chemical information and modeling, 49(9):2077- 2081, 2009.
[18] Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cyhernetics, 4(2):100-107, 1968.
[19] Siqi Hong, Hankz Hankui Zhuo, Kebing Jin, Guang Shao, and Zhanwen Zhou. Retrosynthetic planning with experience-guiee monte carlo tree search. Communications Chemistry, 6(1):120, 2023.
[20] Abdelrahman Hosny, Soheil Hashemi, Mohamed Shalan, and Sherief Reda. Drills: Deep rein- forcement learning for logic synthesis. In 2020 25th Asia and South Pacific Design Automation Conference (ASP-DACE (DD), pages 581 586-586 IEEE, 2020.
[21] Zhiming Hu, James Tu, and Baochun Li. Spear: Optimized dependency aware task scheduling with deep reinforcement learning. In 2019 IEEE 39th international conference on distributed computing systems (ICDCS), pages 2037-2046 IEEE, 2019.
[22] Hyeonah Kim, Minsu Kim, Taeyoung Yun, Sanghyeok Choi, Emmanuel Bengio, Alex Hernández-Garria, and Jinkyoo Park. Improved off-policy reinforcement learning in biological sequence design. In NeuriPS Workshop on Al for New Drug Modalities, 2024.
[23] Junsu Kim, Sungsoo Ahn, Hankook Lee, and Jinwoo Shin. Self-improved retrosynthetic planning, In International Conference on Machine Learning, pages 5486-5495. PMLR, 2021.
11

---

[24] Akihiro Kishimoto. Beat Buesser. Bei Chen, and Adi Botea. Depth- firstfirstttt proof-numbee search with heuristic edge cost and application chemical synthesis planning. Advances in Neural Information Processing Systems, 32, 2019.
[25] Wouter Kool, Herke Van Hoof, and Max Welling. Stochastic beams and where to find them: The gumbel-top-k trick for sampling sequences without replacement. In International Conference on Machine Learning, pages 3499-3508, PMLR, 2019.
[26] Xihan Li, Xing Li, Lei Chen, Xing Zhang, Mingxuan Yuan, and Jun Wang. Circuit transformer: transformer that preserves logical equivalence. The Thirleenth International Conference on Learning Representations, 2025.
[27] Guoqing Liu, Di Xue, Shufang Xie, Yingce Xia, Austin Tripp, Krzysztof Maziarz, Marwin Segler, Tao Qin, Zongzhang Zhang, and Tie- Liu. Retrosynthetic planning with dual value networks. In International Conference on Machine Learning, pages 22266.22276. PMLR, 2023.
[28] Chenyang Lv, Ziling Wei, Weikang Qian, Junjie Ye, Chang Feng, and Zhezhi Hc. Gpt-Is: Generative pre-trained transformer with offline reinforcement learning for logic synthesis. In 2023 IEEE st International Conference on Computer Design (ICCD), pages 320-326. IEEE, 2023.
[29] Ines Filipa Martins, Ana L Teixeira, Luis Pinheiro, and Andre O Falcao. A bayesian approach to in silico blood-brain barrier penetration modeling. Journal of chemical information and modeling, 52(6): 686-16977 2012.
[30] Krzysztof Maziarz, Austin Tripp, Guoqing Liu, Megan Stanley, Shufang Xie, Piotr Gaiński, Philipp Seidl, and Marwin Segler. Re-evaluating retrosynthesis algorithms with syntheseus. arXiv preprint arXiv:2310. 19796, 2023.
[31] Quinn McNemar. Note on the sampling error of the difference between correlated proportions or percentages. Psychometrika, 12(2):153-177, 1947.
[32] Walter Lau Neto, Yingjie Li, end automatic logic optimization exploration via domain-specific multi-armed bandit. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022.
Gaillardon, and Cunxi Yu. Flowtune: End-to-
[33] Laurent Orseau, Levi Lelis, Tor Lattimore, and Théophane Weber. Single-agent policy tree search with guarantees. Advances in Neural Information Processing Systems, 31, 2018.
[34] Judea Pearl and Jin Kim. Studies in admissiiis heuristics. IEEE transactions on pattern analysis and machine intelligence, (4):392-399, 1982.
[35] Yasasvi V Peruvemba, Shubham Rai, Kapil Ahuja, and Akash Kumar. Rl-guided runtime- constrained heuristic exploration for logic synthesis. In 2021 IEEE/ACM International Confer- ence On Computer Aided Design (ICCAD), pages 1-9. IEEE, 2021.
[36] Mariya Popova, Olexandr Isayev, and Alexander Tropsha. Deep reinforcement learning for de novo drug design. Science advances, a(7))eaa,7885, 2018
[37] Hao Qian, Cheng Lin, Dengwei Zhao, Shikui Tu, and Lei Xu. Alphadrug: protein target specific de novo molecular generation. PNAS nexus, 144):pgac227, 2022.
[38] David Rogers and Mathew Hahn. Extended-commectivtyy fingerprints. Journal of chemical information and modeling, 50(5):742-75, 2010.
[39] Julian Schritwwessrr, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604-M)) 2020.
[40] Marwin HS Segler, Mike Preuss, and Mark Waller. Planning chemical syntheses with deep neural networks and symbolic AI. Nature, 555(7698):604-61)) 2018.
12

---

[41] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre. George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mas- tering the game of Go with deep neural networks and tree search. nature, 529(7587):484 2016.
[42] David Silver, Thomas Hubert, Julian Schrittwisser, loannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, (1226641991114--111 2018.
[43] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of go without human knowledge. nature, 550(7676):354 355-39999599999 2017.
[44] Richard Valenzano. Nathan Sturtevant, Jonathan Schaeffer, and Fan Xie. A comparison of knowledge-based gbfs enhancements and knowledger free exploration. In Proceedings of the International Conference Automated Planning and Scheduling, volume 24, pages 375-379,
2014.
[45] Ziyu Wan, Xidong Feng, Muning Wen, Stephen Marcus McAleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero-like tree-search can guide large language model decoding and training. In Forty-first International Conference on Machine Learning. 2024.
[46] Jiankun Wang, Wenzheng Chi, Chenming Li, Chaoqun Wang, and Max Q-H Meng. Neural n Learning-basse optimal path planning. IEEE Transactions on Automation Science and Engineering, 1(4):1748-11 1758, 2020.
[47] Jingyuan Wang, Ning Wu, Wayne Xin Zhao, Fanzhang Peng, and Xin Lin. Empowering a* search algorithms with neural networks for personalized route recommendation. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 539-547, 2019.
[48] Yi Wang, Hui Tang, Lichao Huang, Lulu Pan, Lixiang Yang. Huanming Yang. Feng Mu, and Meng Yang. Self-play reinforcement learning guides protein engineering. Nature Machine Intelligence, 5(8):845-860, 2023.
[49] Kedi Wu and Guo-Wei Wei. Quantitative toxicity prediction using topology based multitask deep neural networks. Journal of chemical information and modeling, 58(2):220-531, 2018.
[50] Chenjun Xiao, Ruitong Huang, Jincheng Mei, Dale Schuurmans, and Martin Müller. Maximum entropy monte-carlo planning. Advances in Neural Information Processing Systems, 32, 2019.
[51] Fan Xie, Martin Müller, Robert Holte, and Tatsuya Imai. Type-based exploration with multiple search queues for satisficing planning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
[52] Shufang Xie, Rui Yan, Peng Han, Yingce Xia, Lijun Wu, Chenjuan Guo, Bin Yang, and Tao Qin. Retrograph: Retrosynthetic planning with graph search. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2120-2129, 2022.
[53] Zhihao Xing and Shikui Tu. graph neural network assisted monte carlo tree search approach to traveling salesman problem. IEEE Access, 8:108418-108428 2020.
[54] Guoli Xiong, Zhenxing Wu, Jiacai Yi, Li Fu, Zhijiang Yang, Changyu Hsieh, Mingzhu Yin, Xiangxiang Zeng, Chengkun Wu, Aiping Lu, al. Admetlab 2.0: an integrated online platform for accurate and comprehensive predictions of admet properties. Nucleic Acids Research, 49(W1):55W14, 2021.
[55] Saeyang Yang. Logic synthesis and optimization benchmarks user guide: version 3.0. Citeseer, 1991.
[56] Michael Yao, Yimeng Zeng, Hamsa Bastani, Jacob Gardner, James Gee, and Osbert Bastani. Generative adversarial model-based optimization via source critic regularization, Advances in Neural Information Processing Systems, 37:44009-440333 2024.
13

---

[57] Yemin Yu, Ying Wei, Kun Kuang, Zhengxing Huang, Huaxiu Yao, and Fei Wu. Grasp: Navigating retrosynthetic planning with goal-driven policy, Advances in Neural Information Processing Systems, 35:10277-10268, 2022.
[58] Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. Rest-mets*: LLM self-training via process reward guided tree search. Advances in Neural Information Processing Systems, 37:64735-647777 2024.
[59] Dengwei Zhao, Shikui Tu, and Lei Xu. Efficient retrosynthetic planning with MCTS exploration enhanced A search. Communications Chemistry, 7(1):52, 2024.
[60] Dengwei Zhao, Shikui Tu, and Lei Xu. Seea Efficient exploration-enhaneed A search by selective sampling. Advances in Neural Information Processing Systems, 37:104138-104179, 2024.
[61] Keren Zhu, Mingjie Liu, Hao Chen, Zheng Zhao, and David Z. Pan. Exploring logic optimiza- tions with reinforcement learning and graph convolutional network. Proceedings of the 2020 ACM/IEEE Workshop on Machine Learning for CAD, pages 145-150, 2020.
14

---

A Proof of the sampling expectation
In the section, we will provide the detailed proof of comparing the uniform sampling and cluster sampling with p p = N:/N. In this situation, the number of nodes selected by cluster sampling from O, is pf N and the number of nodes selected from cluster O by uniform sampling, denoted as N2. is also expected to be proportional to the cluster size N;, i.e., E| Pf x N'. According to Lemma 4.2 the mean and variance of the global distribution encompassing K clusters are:
K Mg = Σ PiPS
K =
K
P
+
Pip.
(15)
1=1
In each sampling iteration, N nodes are directly acquired from the global distribution, exhibiting empirical mean and variance j. and o respectively. Building upon Lemma 4.3 the expected values of Bu and o of the sampled nodes using uniform sampling are:
K
ED, My Σ Dir
ED.
1o
o
Pip
1
(16)
For cluster sampling, let jú; and o? denote the empirical mean and variance, respectively, of the N nodes drawn from O₁, According to Lemma 4.3 the following relations hold:
N;
N of No N,
ED. [
Mii
Varp, [7:]]
E lof) =
(17)
Based on Lemma 4.2 the mean and variance of the candidate set D are:
K
je Entie ae
Σ
of
Σ
p 126
(18)
i=1
Considering that pt p. have:
ED. [ie] = Σ p ETa =
Σ
p Elpul
(19)
1=1
ED. [0
pi f
K
p
N₂ No of
+ +x2)
Σ
K
(pi)
No -Nº of N: - No
ED lão
(20)
N:
No
N₂ No of
K
No N of
ED. [02]
ED. [d
pi
Σ
(ps)
N; N
N; - N
K
N₁ N
pf of > 0
(21)
N; - N
Therefore, for cluster sampling proportional to the cluster size, the expected value of the mean Ep, [Ac] remains consistent with Ep., [Pu), but the expected variance Ep, [6?]] is larger than Ep,, [62].
B Error assumption of Theorem 5.1
Due to the presence of prediction errors, for two nodes n, and n2, we have that fi fi + c and f2 fī + 62, where is the prediction error of f to the real evaluation f Define A = ʃ2 - f1 > 0
and 17 = e2 é1, we have that
P( - A) P(S - f 0/4) = P(A n/4).
(22)
Since P(A >> A/ is increasing with A, P( > f A) also increases with the gap between fi and f2. The monotonicity property established Theorem 5.1 remains valid even when
the noise distribution is non-Gaussian and node-dependent.
15

---

C Suboptimal of cluster sampling in SeeA* *
We further delve into the sampling strategies within cluster sampling by decomposing Equation 20 into
ED. [02] = 0(11.-. .. .KK) + ( ,ok),
(23)
where
Φ
Σ
Pip
2
Σ Dipi
(24)
i=1
K
K
N of N
K
N, No of N M-1- N
e = o
2
(xt) Σ
(25)
No
i=1
is the variance of the mean of different clusters, while vi evaluates the uncertainty of the sampling distribution. Given that the true node path reward f* is unobservable, the corresponding mean 14, and variance of for cluster O2 are inherently difficult to estimate. Assume that μe for cluster O is drawn from distribution with E E[u,] pm= and V Varlu:]
o and that variance of is also sampled from a distribution with E [oo]] = Pvs and V ar [a = de. Therefore,
K
E ED. [+]] = Σ
p Flps) = pmm
(26)
K
E
Σ
pt ETu E
Σ
(pt)² 12 + >
171
Σ (pi)² (o + (mn))
Σ
m=
+ um
ifj
K
K
2
(pt) (2
Σ
0 mp
+ 1mm
Pt
P
1m1
K
K
1
(pt)²
(27)
mx
K
where the equality holds if and only if Vi. p. 1/K. Therefore, E [0], which sampling equal number of nodes from each cluster, is larger than E cluster. What's more,
[0). which proportional sampling from each
Eylb
Muv
Σ
pi)
(N; 1)Nc
N, NC
Mum
1+
Σ
K
pf)
Nc
pf N₂
]
1=1
K-1 1
K
P. 1)
K K-1
= Mox
1+ No
S Mun
11
(28)
N;
Ne
where the equality holds if and only 3f, pf = and Vjj + i, p2 0. What's more, if each cluster has the same number of nodes, i.e., NN = N₁ = summary, sampling from each cluster evenly maximizes Fpp (o). while sampling from single cluster maximizes [b)). Considering both Equation 27d 28 Lagrange multiplier method is employed to
Nx. p; 1/K will minimize [5, In
maximize E, [B]
K >
K-1
K P
(pf 1)
max
22
(xt)²
+ Mux
1+
+
Ne
N
i=1
[=1
K Σ
subject to
pp
=
1 pp
<1
Vi.
16

---

The optimal sampling distribution is p min L, max (0, AN
2[J - N.) where À a constant
to ensure Σx= P = 1. Based on Equation 26 the expectation of the mean of sampled nodes is
independent of the sampling distribution pj and the optimal p to maximize the expectation of
the sampling variance is related to the unknown om and o Therefore, considering Equation 9 selecting nodes from each cluster evenly employed in SeeA" not guaranteed to be the optimal for cluster sampling, and the optimal sampling distribution still needs further investigation to achieve trade-off between [o] and [p]
D Proof of Theorem 5.1
We begin by establishing lemma that supports the proof of T'hhorem 5.1
Lemma D.1 Assume x is random variable from distribution N (10: og), from N(11, ((11,ff of). If and y are independent of each other and p1 po, then
(11 no)/ Vod 00 of
P(x > y) exp
(29)
COS2E
where 0 E x/2 is constant.
According to Bayes' theorem,
. x NN og) =N (o
-N(08) +
optlgg
o
P(flf) ((1)))))))))))>)))))))))))) x
(30)
o3 + o²
0 + og
According to Lemma D.1 for two nodes n, and n2 with f(n1) f(12):
(fm)) f(nz))
P(f*(m1) (1-
P( <f = =1 exp
40 + oz)) cos? (31)
According to Equation 31
likelihood (m) > f" (m22)) increases with the difference f(11)
[122). Theorem 5.1 is proved.
E Introduction of retrosynthesis planning
Retrosynthetic planning aims to identify a synthetic route from available molecules to a target compound. It can be formulated Markov Decision Process and solved using heuristic tree search algorithms:
State: The current of molecules obtained through sequence of retrosynthetic steps from the target molecule.
Action: The reaction provided by the single-step retrosynthesis model to synthesize the first non- hont-bilddigg-boss block intermediate in the current retrosynthetic state
The cost of a chemical reaction is defined as the negative logarithm of its predicted probability by the single-step retrosynthesis model, and the reward given as the negative of this cost.
Reward:
new molecular state is obtained by replacing the product in the current molecular with the reactants of the applied chemical reaction.
Transition function:
A terminal state is reached when all molecules are identified as available building blocks. indicating a complete synthetic route. The single-step retrosynthesis model is designed for multi-class task based on 381, 302 chemical reaction templates. The input is a 2048-dimensional Morgan Fingerprint vector 3x and the architecture of the policy network is:
A fully connected layer with dimensions [2048, 512].
17

---

A batch normalization layer.
A dropout layer with dropout rate of 0.3.
A fully connected layer with dimensions [512, 381302).
A softmax layer.
The synthesis cost of state defined as the sum of the synthesis costs of all molecules in the set, where the cost of available building blocks is O, and the synthesis costs of other molecules are estimated by well-trained value network. The input 2048-dimealional molecular vector, and the architecture is as follows:
A fully connected layer with dimensions [2048, 128).
A ReLU activation layer.
A dropout layer with dropout rate of 0.1.
A fully connected layer with dimensions [128, 1].
Normalize the output y with log(1 + e²).
The parameters of the policy and value networks are identical to those of Retro"+ (23 and also consistent with SeeA" [60]. The set of molecules used for testing is derived from the following seven datasets:
190 molecules are collected from the United States Patent and Trademark Office (USPTO) used primarily for retrosynthetic planning and related research. Only molecules for which reactions in the synthesis route are all covered by the top-50 predictions by the one-step model are kept.
USPTO 4
logP (5) The logarithm of the partition coefficient quantities the solubility of a molecule in a particular solvent, which is crucial for understanding the molecule's 's pharmacokinetics and pharmacodynamics. 1073 molecules are collected.
This property is used to assess the solubility of molecules, which significantly impacts the absorption, distribution, metabolism, and excretion of drug candidates. 407
logS [54] :
molecules are contained in the logS.
The LD50 value measures the toxicity of substance, playing a critical role in evaluating the safety and efficacy of pharmaceutical compounds. 872 molecules are considered.
Toxicity LD50 [4)
Ames (17] The Ames widely employed in drug development assess the mutagenic potential of drug candidates and other chemicals used in drug formulation or as excipients. Ames benchmark consists of 1129 molecules.
BBBP 29
The Blood-Brain Brain Barrier Penetration dataset evaluates the ability of molecules to cross the blood-brain barrier, a critical factor in the development of central nervous system drugs. 610 molecules included.
ClinTox [15]: A dataset comprising 628 FDA -approee drugs and those that failed clinical trials due to toxicity concerns, providing insight into the safety profiles of pharmaceutical compounds.
F
Introduction of logic synthesis
Logic synthesis refers to the process of converting hardware design described at the register-transfer level (RTL) into a gate-level Boolean representation, typically modeled as an And-Inverter Graph (AIG)-o netlist composed solely of AND and NOT gates. An optimized AIG is then produced by applying series of semantics- semantics-preserringg preserving transformations aimed at improving circuit performance. area, and power. The logic synthesis problem can also be formulated as a Markov Decision Process and addressed using tree search algorithms:
State: The current state is encoded as an And-Inverter Graph, which captures the structural and functional characteristics of the circuit.
18

---

Following ABC [2 and recent reinforcement learning approaches 20), seven logic optimization operations are permitted: balance, re-substitution, re-substitution -z rewrite, rewrite -7, refactor, and refactor -7.
Action:
Reward: resyn2 synthesis recipe is used as the baseline during the evaluation. The immedi- ate reward for non-termination state and the area-delay product (ADP) reduction for an action sequence S is used as the reward for termination state:
R(S,t) - max (-1, 0,
ADP(S) ADP(resgn2)
if ||
(32)
Otherwise
where ADP(-) is estimated by the ABC library [2].
Transition model: Each action is designed to perform a global structural transformation on the AIG. The state transition function implemented using ABC (2), resulting in newly transformed AIG.
value network employed to estimate the expected reduction in ADP, thereby guiding the search process. The input to the value estimator consists of the initial AIG and the sequence of actions. Each node in the AIG is encoded as a two-dimensional vector that captures both types and the number of inverted predecessors, while the adjacency matrix encodes the structural connectivity of AIG. A Graph Convolutional Network (GCN) utilized to extract AIG embedding, with the architecture specified as follows:
A GCN layer with a hidden size of 32.
A batch normalization layer.
A LeakyReLU activation layer.
A second GCN layer with hidden size of 32.
A batch normalization layer.
Mean pooling and max pooling applied independently, and their outputs concatenated to yield a 64-dimensional graph embedding.
The action sequence, along with the number of steps, is encoded as string and passed to BERT model [13], which generates 768- (68-dimenssinal sequence embedding. The final input to the value estimator is formed by concatenating the 64-dimensional AIG embedding with the 768-dimensional BERT embedding. The architecture of the value estimator is as follows:
A fully connected layer with dimensions [832, 256).
A LeakyReLU activation layer.
A fully connected layer with dimensions [256, 256).
A LeakyReLU activation layer.
A fully connected layer with dimensions [256, 1].
* A Tanh activation layer.
The parameters of the value networks are identical to those of SeeA* [60] Twelve benchmark circuits from the MCNC dataset used for evaluation, each exhibiting varying numbers of components and structure connections. Detailed specifications are provided in Table
G McNemar test on success rate
To assess the statistical significance of the difference in success rates between two models on paired binary outcomes, we employ the McNemar test [31]. This non-parametric test is employed to evaluate classification performance differences on matched samples. Given a 2 contingency table:
Model B Correct
Model Incorrect
Model A Correct
7110
Model A Incorrect
Mo1
7400
19

---

Table 4: Characterization of testing circuits from MCNC dataset.
Circuit
# Inputs
# Outputs
# Nodes
Depth
alu4
10
6
735
42
apexl
45
45
2655
apex2
39
3
445
29
apex4
9
3452
b9
41
21
105
10
c880
60
26
327
c7552
207
108
2074
29
88
63
889
m4
8
16
760
14
pair
173
137
1500
24
max1024
10
1021
20
proml
9
40
7803
24
The test statistic is defined as:
x² (no1 n=10)²
(33)
Tuu1 + 1'10
Under the null hypothesis of difference,, x2 approximately follows chi-square distribution with one degree of freedom. A p-value less than 0.05 indicates statistically significant difference in performance.
The synthesis outcomes 4, 909 molecules across seven datasets are used for hypothesis testing. The resulting chi-square statistic 3.615 with p-value of 0. 0.0286(<< 0.05). leading to the rejection of the null hypothesis. These results indicate that KeeA* achieves a statistically significant improvement over SeeA".
H An investigation of hyperparameters
(8)
(b)
-
Ang Length
Success Rate (1)
Avg Length
Avg Length
+ Arg Lergth
32
0.5
1.0
8
Figure 3: Success rate and average solution length on the USPTO benchmark with different (a) a and (b) 8.
The comparative experiments under different hyperparameter settings on the USPTO and ClinTox test benchmark are presented in Figure 3 and respectively. The best success rate and average solution length are achieved when a U.4. however, more significant drop is observed when a + 1.0, highlighting the adverse impact of an overly imprecise heuristic on the search process. KeeA* performs best when 8 0.8, while both excessively large and small values of 3 lead to performance degradation. These results indicate that appropriate choices of a and effectively balance exploration and exploitation, thereby enhancing the overall search performance. The comparative experimental results on the b9 circuit for logic synthesis task are shown in Figure 5 yielding a similar conclusion: appropriate values of a and lead to improved performance.
approaches performance slightly degrades;
20

---

-D Loggh
6442
Success Rate (%)
0.44
Success Rate (N6
Avg. Length
Lengs
0.42
-O-
Success
Aug Length
18:51
644
228
12.1
6474
13.45
636
6472
13.43
Figure 4: Success rate and average solution length the ClinTTx benchmark with different (a) and (b) 33.
(a) 14.0
M
(b)
20.5
15.0
Roduction (%0
Reduction (%)
V
24.0
146
20
0.0
B 686
Figure 5: ADP reduction on the b9 circuit on logic synthesis with different (a) and (b) B.
To demonstrate the robustness of KeeA", an exhaustive grid search is conducted with three indepen- dent runs per configuration, and a 'Ttest at the 0.05 significance level is used to compute the error intervals. Because only three runs conducted, the deviation is relatively large. Both the mean and the error interval are reported Table KeeA* demonstrates robust performance, consistently outperforming SeeA*'s 97.30 + 2.36% across a wide range of hyperparameter settings, with the highest success rate reaching 98.77 + 0.62%.
0.1
0.3
0.5
3 = 0.7
0 0.9
Q = 0.1
98.07 + 2.68
97.72 - 1.64
97.72 + 1.24
0.3
17.89
97.72 1.64
98.60 2
98.60 2.68
97.54 + 1.24
@ = 0.5
2.46
98.77 2.46
08.07+0..
97.37 1.84
97.89 + 0.00
0.7
0.62
98.07 1.64
08.07 0.62
98.77 + 0.62
97.89 + 1.07
α = 0.9
6..74
62.81 + 8.57
64.04
60.88 + 4.32
64.74 4 2.14
Table 5: Success rate KeeA* under different a and on the USPTO benchmark (%).
I Investigation of cluster number K
To assess the influence of the number of clusters K on KeeA", three runs are performed for various K, and a T-test with the 0.05 significance level is used to compute error intervals. Because only three runs are conducted, the enror interval is relatively large. KeeA* consistently outperforms SeeA* (Cluster) on the USPTO test set. An excessively small induces under-fitting, leading to model of limited flexibility, while overly large K risks overfitting collected states. Both extremes impair
21

---

Table 6: Success rate of KeeA* and SeeA* (Cluster) with different cluster number K on the USPTO benchmark (%).
K
KeeA
SeeA" (Cluster)
95.44 + 0.66
94.91 1.74
97.54 0.50
97.37 = 0.86
98.53
0.60
97.30 0.95
6
97.36
+ 1.55
96.32 + 0.43
95.26 0.86
94.04 0.89
94.91 1.74
92.98 2.21
the efficacy of decision Deeision-making during search, highlighting the importance of appropriate cluster number K selection to optimize the efficiency of SeeA" and KeeA*.
Variability of KeeA* due to randomness.
To quantify KeeA"'s variability induced by randomness, we executed three runs for each of ten random seeds on the USPTO test set. T-test with the significance level used to compute the eπror intervals. The average success rate over all 30 runs is 98 18.53% which is comparable to the 98.84% reported in the paper. KeeA* * exhibits robust performance across various random seeds, achieving more stable results compared to SeeA* (Cluster). SeeA* not only exhibits a larger variance across multiple runs but also shows greater performance fluctuations under different random seeds, highlighting the superiority of KeeA* over SeeA* (Cluster) with respect to stability.
Table 7: Success rate of KeeA* and SeeA" (Cluster) with different random seed on the USPTO benchmark (%).
Seed
KeeA*
SeeA* (Cluster)
98.07 + 0.25
96.49 0.66
97.89 + 0.86
98.07 + 0.66
98.60 + 0.25
96.84 0.00
98.60 + 0.50
97.89 + 0.43
98.25 + 0.25
98.60 0.25
98.95 + 0.43
97.37 + 0.00
99.30
96.67 1.08
98.95 0.00
96.67 + 0.89
98.07 0.25
96.84 4.14
98.60 0.25
97.54 0.25
All
98.53 0.60
97.30 0.95
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the main claims made in the abstract and introduction accurately reflect the paper's 's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in the Conclusion section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

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

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is provided in the supplemental material and will be publicly available once acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc)
aablic/guudees/Codeetuiiiss ott.eeeuuuuiiiiiooooooooioooii for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https wwwpee/e/oooSSeeessssedeeee
/ wwtps/cccppplgguuuuaaeeeae
www.ssssiicggsoooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details are summarized in the Experiment section and appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Although error bars are not provided, the proposed method was evaluated on over 4, 909 test instances far exceeding the 190 molecules used in previous studies. The McNemar test is employed to statistically validate the robustness of KeeA".
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
25

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computer resources employed in this work is summarized in Experiments section
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics stttiisstttts////t
Answer: [Yes]
Justification:
We believe that this paper conform with the NeurIPS Code of Ethies.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Discussion of societal impacts is provided in the Conclusion section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
26

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This work focuses heuristic search algorithms and currently poses no risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All materials used in this study are publicly available and well-cited.
Guidelines:
The answer NA means that the paper does
existing assets. The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
27

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets, but the associated code will be made publicly available upon acceptance.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
28

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs are not involved as any important, original, non-standard components.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https:/ /tappp:///eurps..... http//rripsscccoooffeerrsss///// cc//oonferences/22255L/.. for what should or should be described.
29


Reviews:
[{"review_id": "gv8fVt6ZoS", "reviewer": "Reviewer_6xHD", "summary": "This paper introduces KeeA*, an epistemic exploratory A* search method that incorporates heuristic knowledge to refine the sampling process. Through theoretical analysis, they first prove that SeeA* with cluster sampling outperforms uniform sampling by leveraging distribution-aware selection. Built on this, KeeA* introduces two key techniques: 1) cluster scouting, which increases the sampling mean, and 2) path-aware sampling, which enhances the sampling variance. These advancements enable KeeA* to generate higher-quality extreme candidates. Empirical evaluations on retrosynthetic planning and logic synthesis confirm that KeeA* achieves superior performance compared to state-of-the-art heuristic search algorithms, e.g., SeeA*, A*, MCTS, etc.", "questions": "Discuss on application scenarios where KeeA* might underperform compared to SeeA*", "limitations": "No", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1) How to effectively leverage heuristic knowledge relevant to open nodes is a important question to explore in search algorithms.\n2) Theretical analysis on cluster sampling and the two proposed techniques is novel and robust.\n3) Experiment design and execution are excellent, with KeeA* demonstrating clear performance improvements over the baselines.\n\nWeaknesses:\n1) Discuss on application scenarios where KeeA* might underperform compared to SeeA*.", "was_revised": true, "final_justification": "Thank you to the authors for their thorough discussion of the scenarios where SeeA* may outperform KeeA*, offering valuable insights to help users better understand. Overall, I recommend acceptance.", "rebuttal": "We sincerely thank the reviewer for the insightful comment. The following content will be added to the revised manuscript to provide further clarification.\n\nQ1: Discuss application scenarios where KeeA* might underperform compared to SeeA*.\n\nA1: KeeA* and SeeA* are both search algorithms designed to address the discrepancy between the heuristic estimate $f$ and the true return $f^\\*$. Compared to SeeA*, KeeA* introduces two key improvements: \n\n(1) KeeA* allocates the number of sampled nodes from each cluster in proportion to the mean of the estimated $f$-values of their nodes, while SeeA* samples the same number of nodes from each cluster,\n\n(2) KeeA* improves the probability of sampling nodes at shallower depths for exploration, instead of uniformly selecting candidates from the chosen cluster as in SeeA*\n \nThe improvement (1) exploits the observation that, despite potential bias, $f$ estimated by a well-trained heuristic remains informative. The improvement (2) introduces a depth-based penalty to encourage exploration. Given the exponential growth of the search tree, the number of nodes increases significantly at deeper levels; favoring shallower nodes helps escape from over-explored branches. The effectiveness of both improvements depends on the degree of bias between the heuristic estimate $f$ and the true evaluation $f^\\*$. Therefore, there are two scenarios where KeeA* might underperform SeeA*:\n\nCase (1): If the prediction quality of $f$ is very low, then the clusters with higher $f$ are more likely to have lower true returns $f^\\*$. In such cases, KeeA* may over-sample from suboptimal clusters, reducing the likelihood of selecting the optimal node and thereby impairing search efficiency.\n\nCase (2): If the prediction quality of $f$ is sufficiently high, greedy expansion based on $f$-values becomes an effective strategy to identify the node with the highest true return $f^\\*$. The depth-based penalty used to encourage exploration introduces unnecessary node expansions, reducing the search efficiency of KeeA*.\n\nExcluding the two aforementioned extreme cases, KeeA* leverages both exploitation of the heuristic function $f$ and exploration encouraged by the depth-based penalty, enhancing search efficiency under biased estimates by effectively balancing exploitation and exploration."}, {"review_id": "JispmutWZT", "reviewer": "Reviewer_8kiH", "summary": "The paper proposes KeeA*, an extension of SeeA* that augments selective‑sampling A* search with two knowledge‑guided mechanisms, cluster scouting and path‑aware sampling. A theoretical argument shows that cluster sampling should raise the expected extreme reward relative to uniform sampling, after which the two new heuristics are introduced to further raise the candidate‑set mean and variance. Experimental results cover retrosynthetic planning and logic‑synthesis benchmarks and include ablations and a McNemar test for significance.", "questions": "+ Typos such as “an dynamic subset” (abstract) and a few inconsistent variable names between Algorithm 1 and the appendix remain. \n\n+ Figures 3-5 lack confidence intervals; error bars would complement the McNemar test. The derivation in Appendix B occasionally drops expectation brackets, which may confuse readers unfamiliar with the notation.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n+ The topic is timely: many modern search systems rely on neural heuristics whose bias can cripple performance, and methods that inject principled exploration are valuable. \n\n+ The theoretical development, while idealised, cleanly connects distributional variance to extreme‑value rewards and clarifies why cluster sampling helps. KeeA* moves beyond a conceptual observation by designing concrete, lightweight modifications that integrate readily with SeeA*, so the methodological increment is small in implementation but effective in practice. \n\n+ The two applications, retrosynthetic planning in organic chemistry and logic synthesis in VLSI design, are interesting and the performance shows clear evidence the proposed method outperforms existing state-of-the-art methods.\n\nWeaknesses\n- The analysis in Theorem 5.1 still rests on homoscedastic Gaussian error assumptions. In practice, heuristic inaccuracies are heavy‑tailed and state‑dependent; some discussion of robustness would help readers better understand applicability. \n\n- While the authors use consistent \\alpha and \\beta, baseline hyper‑parameter parity is not fully demonstrated: different search algorithms may require different choices of \\alpha and \\beta to achieve the optimal performance. Part of KeeA*’s gain may just come from the fact that the current setup of \\alpha and \\beta works better compared to the baselines. A small grid search on both SeeA* and KeeA* might dispel this doubt.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the valuable comments. We will carefully revise the manuscript to correct typos and clarify variable notations to improve readability. Our responses to the concerns are provided below.\n\nQ1: Theorem 5.1 still rests on homoscedastic Gaussian error assumptions\n\nA1: Due to the presence of prediction errors, for two nodes $n_1$ and $n_2$, we have that $f_1=f^\\*_1+\\epsilon_1$ and $f_2=f^\\*_2+\\epsilon_2$. Define $\\Delta=f_2-f_1>0$ and $\\eta=\\epsilon_2-\\epsilon_1$.\n$$\nP(f^\\*_2>f^\\*_1|f_2-f_1=\\Delta)=P(f^\\*_2-f^\\*_1>0|\\Delta)=P(\\Delta>\\eta|\\Delta)\n$$\nSince $P(\\Delta>\\eta|\\Delta)$ is increasing with $\\Delta$, $P(f^\\*_2>f^\\*_1|f_2-f_1=\\Delta)$ also increases with the gap between $f_1$ and $f_2$. The monotonicity property established in Theorem 5.1 remains valid even when the noise distribution $\\epsilon$ is non-Gaussian and node-dependent; however, Equation (11) can no longer be derived.\n\nQ2: Grid search on both SeeA* and KeeA* and confidence intervals. \n\nA2: KeeA* extends SeeA* by incorporating two additional hyperparameters, $\\alpha$ and $\\beta$. Other parameters remain consistent with the optimal settings provided in SeeA*. To demonstrate the robustness of KeeA*, an exhaustive grid search is conducted with three independent runs per configuration, and a t-test at the $0.05$ significance level is used to compute the error intervals. Because only three runs are conducted, the deviation is relatively large. Both the mean and the error interval are reported in the following table. KeeA* demonstrates robust performance, consistently outperforming SeeA*'s $97.30\\pm 2.36\\\\%$ across a wide range of hyperparameter settings, with the highest success rate reaching $98.77\\pm 0.62\\\\%$. This observation aligns with the findings shown in Appendix G, which provides the performance of KeeA* under various $\\alpha$ and $\\beta$.\n\nTo strengthen the statistical validity of Figures 4–6, confidence intervals (t-test, $\\alpha$=0.05) based on empirical standard deviations can be computed. Revisions will be incorporated into the final manuscript. Due to time constraints, we have not completed the grid search and confidence interval calculations for the McNemar test across all seven datasets. We will include the comprehensive results in the final version of the paper.\n\n||$\\beta=0.1$|$\\beta=0.3$|$\\beta=0.5$|$\\beta=0.7$|$\\beta=0.9$|\n|:-|:-|:-|:-|:-|:-|\n|$\\alpha=0.1$|$97.72\\pm2.46$|$98.07\\pm2.68$|$97.54\\pm1.64$|$97.72\\pm1.64$|$97.72\\pm1.24$|\n|$\\alpha=0.3$|$97.89\\pm2.83$|$97.72\\pm1.64$|$98.60\\pm2.21$|$98.60\\pm2.68$|$97.54\\pm1.24$|\n|$\\alpha=0.5$|$97.54\\pm2.46$|$98.77\\pm2.46$|$98.07\\pm0.62$|$97.37\\pm1.84$|$97.89\\pm0.00$|\n|$\\alpha=0.7$|$98.25\\pm0.62$|$98.07\\pm1.64$|$98.07\\pm0.62$|$98.77\\pm0.62$|$97.89\\pm1.07$|\n|$\\alpha=0.9$|$64.74\\pm7.70$|$62.81\\pm8.57$|$64.04\\pm6.43$|$60.88\\pm4.32$|$64.74\\pm2.14$|"}, {"review_id": "CuFcoMa535", "reviewer": "Reviewer_CTFv", "summary": "This paper proposed a heuristic search algorithm called Keep A*, which utilizes a cluster sampling instead of a simple random sampling. Experimental evaluations on extensive real-world datasets demonstrated the effectiveness of the proposed method. Furthermore, the authors provided theoretical backgrounds of Keep A* to clarify the reasons for the performance improvements by Keep A*.", "questions": "See the Strengths And Weaknesses section.", "limitations": "See the Strengths And Weaknesses section.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. Clear motivation and extensive related work study supporting the motivation of the proposed method.\n\n2. Theoretical analysis that clarifies the reasons for the performance improvements by the proposed method.\n\n3. State-of-the-art performance on real-world datasets.\n\n\nWeaknesses\n1. Which of the following categories does the proposed cluster sampling belong to: distance-based, density-based, or their combination? Each clustering method has inherent advantages and disadvantages. Please clarify the advantages and disadvantages of the cluster sampling. It will be helpful in justifying the proposed method.\n\n2. I was not able to fully analyze the reasons for the accuracy improvements by Keep A* in the the retrosynthetic planning problems because the problem definition of the retrosynthetic planning is not clear. In the current problem definition, I didn't fully understand why state-of-the-art machine learning algorithms for organic retrosynthesis have not been compared in the experiments.\n\n3. K is a crucial hyperparameter in the clustering methods with a fixed K. However, a hyperparameter analysis of K is not provided in the manuscript. If I missed the description of K, please let me know where the description of K is.", "was_revised": true, "final_justification": "The author's thorough rebuttal addressed many of my concerns, so I raised my score accordingly. Thank you for the author's comprehensive response.", "rebuttal": "We sincerely appreciate the reviewer’s insightful comments and constructive suggestions. We provide detailed responses to the concerns raised below, and the relevant revisions and clarifications will also be incorporated into the updated version of the manuscript.\n\nQ1: Please clarify the advantages and disadvantages of cluster sampling.\n\nA1: Following SeeA*, competitive learning as a distance-based clustering algorithm is employed to reduce computational overhead, where nodes are grouped by measuring their distance in the embedding space. A key advantage of this clustering algorithm is that it improves computational efficiency by avoiding re-clustering from scratch with each node generation. Newly generated nodes are incrementally assigned to the nearest cluster, with the cluster centers updated in turn. Meanwhile, besides the initialization of cluster centers, cluster sampling depends on the quality of feature vectors extracted by neural networks and the sequence of node expansions. As this study primarily focuses on tree search algorithms, the development of more advanced clustering methods is an essential avenue for future research.\n\n\nQ2: Why keep A* in the retrosynthetic planning problems and the exclusion of state-of-the-art machine learning algorithms. \n\nA2: This paper focuses on neural network‑guided heuristic search algorithms, aiming to enhance search efficiency when the estimated $f$-values deviate from the true optimal cost $f^\\*$. A* search is the foundation of both SeeA* and KeeA*, and is retained as a baseline search algorithm. KeeA* is designed as a general‑purpose problem‑solving algorithm, not limited to retrosynthesis planning. SOTA general search algorithms, such as LevinTS and PHS, are also evaluated under the same heuristic function for a fair comparison.\n\nAs summarized in Appendix D, retrosynthetic planning aims to identify a synthetic route from available building block molecules to a target compound. One-step retrosynthesis model is employed to predict single-step chemical reactions that can generate the target molecule. If the reactants of a reaction are non-building-block molecules, one-step model is called recursively to find chemical reactions that can decompose these molecules until all molecules are reduced to building blocks. Machine learning algorithms are commonly employed to learn the one-step retrosynthesis model to guide the search process, and a synthesis route composed of multiple chemical reactions typically requires search algorithms for a solution. Directly generating the entire pathway using machine learning models remains highly challenging, and current SOTA retrosynthesis algorithms still rely heavily on search algorithms. \n\nThe following table is a comparative analysis on the USPTO benchmark against SOTA retrosynthesis algorithms. Notably, KeeA* attains comparable performance despite using less accurate heuristics, benefiting from search algorithm refinements without the need for expensive neural network training. We also test EG-MCTS [4] on the entire seven benchmarks, attaining an average success rate of $62.78\\\\%$, below KeeA*’s $63.76\\\\%$. Furthermore, both GRASP [1] and RetroGraph [2] are not open-source. PDVN [3] did not release their trained guiding heuristic models. Therefore, the results for [1,2,3] on all seven benchmarks could not be obtained. The latest DESP algorithm [5] requires processing a large set of starting molecules, leading to significant computational overhead and failing to yield feasible solutions within the 10-minute time constraint.\n|Algorithm|Succ ($\\\\%$)| Avg length|\n|:-|:-|:-|\n|GRASP [1]|$98.95$ |$6.17$ |\n|RetroGraph [2]|$99.47$ |$6.33$ |\n|PDVN+Retro* [3]|$98.95$ |-|\n|EG-MCTS [4]|$96.84$ |$5.92$|\n|KeeA*|$98.95$ |$5.89$ |\n\n[1] Yu, Yemin, et al. \"Grasp: Navigating retrosynthetic planning with goal-driven policy.\" Advances in Neural Information Processing Systems 35 (2022): 10257-10268.\n\n[2] Xie, Shufang, et al. \"Retrograph: Retrosynthetic planning with graph search.\" Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.\n\n[3] Liu, Guoqing, et al. \"Retrosynthetic planning with dual value networks.\" International conference on machine learning. PMLR, 2023.\n\n[4] Hong, Siqi, et al. \"Retrosynthetic planning with experience-guided Monte Carlo tree search.\" Communications Chemistry 6.1 (2023): 120.\n\n[5] Yu, Kevin, et al. \"Double-ended synthesis planning with goal-constrained bidirectional search.\" Advances in Neural Information Processing Systems 37 (2024): 112919-112949.\n\n\n\nQ3: Investigations on the hyperparameter $K$.\n\nA3: As indicated in Line 204 and Algorithm 1, $K$ represents the number of clusters, which is also a critical parameter of SeeA* (Cluster) and was comprehensively analyzed in the original study. KeeA* adopts the same $K$ value as SeeA* in the paper. To assess the influence of $K$ on KeeA*, three runs are performed for various $K$, and a t-test with the $0.05$ significance level is used to compute the error intervals. Because only three runs are conducted, the error interval is relatively large. KeeA* consistently outperforms SeeA* (Cluster) on the USPTO test set. An excessively small $K$ induces under-fitting, leading to a model of limited flexibility, while an overly large $K$ risks overfitting to collected states. Both extremes impair the efficacy of decision-making during search, highlighting the importance of appropriate cluster number selection to optimize the efficiency of SeeA* and KeeA*. We will include the relevant discussions and results in the revised manuscript to address this point.\n\n|K|KeeA* ($\\\\%$)| SeeA*(Cluster)($\\\\%$)|\n|:-|:-|:-|\n|3|$95.44\\pm 1.64$ |$94.91\\pm 4.32$ |\n|4|$97.54\\pm 1.24$ |$97.37\\pm 2.14$ |\n|5|$98.53\\pm 1.49$ |$97.30\\pm 2.36$ |\n|6|$97.36\\pm 3.85$ |$96.32\\pm 1.07$ |\n|7|$95.26\\pm 2.13$ |$94.04\\pm 2.21$ |\n|8|$94.91\\pm 4.32$ |$92.98\\pm 5.49$ |"}, {"review_id": "GLok30WgmM", "reviewer": "Reviewer_6UxX", "summary": "This paper proposes a new search algorithm that incorporates several modifications compared to the SeeA* algorithm. First, the paper provides theoretical evidence that sampling within clusters can increase the likelihood of finding good solutions since this increases the variance of the reward among the candidate nodes to be expanded. Compared to SeeA*, the paper introduces cluster scouting, where samples within each cluster are evaluated to determine a score for each cluster which is used to bias candidate node sampling towards the clusters with a higher score. The paper also introduces a method for intra-cluster sampling that biases candidate node selection towards nodes that have been expanded fewer times. This algorithm is then evaluated on two sets of benchmarks involving retrosynthetic planning and logic synthesis.", "questions": "1)\tPlease provide more information about the additional overhead involved in the reward function estimations that are required to assign scores to clusters. This seems to be a potentially limiting factor.\n2)\tPlease provide a comparison of this work to SeeA* with UCT, and explain why this was not included as a baseline in the benchmarking. This seems to be a very relevant comparison that is currently missing.\n3)\tCould you please include more information about the variability of KeeA* due to randomness, for example how the performance changes between different seeds on a given problem?\n4)\tCould the authors please respond to my concerns about their choice of score metric for the clusters, and discuss the interplay with path-aware sampling? I am not currently convinced these are good design choices in KeeA*.\n5)\tCould the authors please respond to my concerns that the performance improvement compared to SeeA* could be due to overfitting KeeA*’s hyperparameters to these problems, instead of an underlying algorithmic advantage?\nA satisfactory answer to these questions could improve my “Quality” score.", "limitations": "Limitations are only addressed superficially in the conclusion. More information specifically about the variability due to randomness would be appreciated.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Quality**: The first two claims in the paper, concerning the theoretical foundation for cluster sampling and the rationale for introducing cluster scouting and path-aware sampling, are well supported by the theoretical and empirical evidence. However, I do see two issues with the implementation of cluster scouting. First, and this is a point I may have misunderstood, is that this appears to be a computationally intensive process since it requires evaluating a potentially large number of reward functions to determine the score for each cluster. I expect this could be a limitation of this method compared to SeeA*. Second, I’m not convinced dividing the expectation value of the reward by the standard deviation is a good way of assessing the score. This would attribute a higher score to clusters with very low rewards but much smaller standard deviation than it would to clusters with much higher rewards and a higher (but still potentially quite small) standard deviation. I also have a concern about how path-aware sampling is combined with cluster scouting. Cluster scouting may return high scores to clusters where the reward for deeper nodes is much higher than shallower nodes, but the path-aware sampling would then focus on the shallower nodes which is counter-productive. I feel a more principled sampling approach would include the expansion depth into the score.\n\nThe third claim concerns the experimental benchmarking. A strength of the paper is that the experiments are extensive and contain a statistical robustness test for the results. However, a weakness is that the results for KeeA* are very close to those of SeeA*. Though the statistical tests run in the paper show that the difference is statistically significant, these tests do not rule out the possibility that these better results are achieved through overfitting the hyperparameters of KeeA* to the specific problems investigated in the experiments. This concern is reinforced by results in the appendix that show that the performance sometimes seems to vary by more than the difference between the two algorithms for different (but close) hyperparameter choices. Another concern I have about these experiments is that they do not include SeeA* with UCT as a baseline in the benchmarks. The SeeA* paper shows that SeeA* with UCT outperforms KeeA* on the USPTO dataset in both success rate and average runtime. Considering UCT plays a similar role as path-aware sampling, I feel this is a valid baseline that should have been included in this comparison.\n\nThough the paper does mention some limitations, some additional discussion of these limitations would have been welcome. For instance, more information about the variability of KeeA* due to sampling randomness would be welcome.\n\n**Clarity**: The paper is clear and well-written. Extensive additional information is provided in the appendix. There are a few minor typos that need correcting. A minor detail is that how clusters are made and maintained in the nodes is not explained in the main text apart from Algorithm 1. It would help the reader to include a small discussion of this before section 4 that discusses the motivation for these clusters.\n\n**Significance**: The paper proposes some interesting directions for improving SeeA*, and I can see some of these being picked up by the community. The observation that sampling from clusters is a theoretically well-founded way of improving performance is useful and does motivate further exploration of ways in which clusters could be better defined and sampled from. The expanded evaluation on multiple retrosynthetic planning datasets compared to SeeA* is also a step forward. However, the very small performance improvement over SeeA* limits the significance of the work.\n\n**Originality**: The way in which KeeA* investigates and makes use of different clusters, and the evaluation on additional retrosynthetic datasets, are original and interesting. This work is well-referenced and is appropriately compared to prior work. However, some of the contributions in this paper appear somewhat incremental. The observation that cluster sampling can lead to higher variance in the samples is quite intuitive, and there is little additional insight provided by the mathematical proof. Theorem 5.1 is also quite basic and does not add new insight.", "was_revised": true, "final_justification": "The authors provide a convincing response to my questions. My original low quality score stemmed mainly from doubts about the benchmarking against SeeA*: the small difference in performance, combined with variable performance for different hyperparameter choices and the absence of SeeA* with UCT as a benchmark all raised doubts about whether the proposed algorithm actually does outperform SeeA*. In their response, the authors put forward convincing evidence that this is indeed the case. As such, I am raising my Quality score to 3. Though I feel the gains are still a bit incremental compared to SeeA*, now that my main objection has been raised I am increasing my overall rating to 4.", "rebuttal": "We sincerely appreciate the reviewers’ insightful comments and constructive suggestions. We will carefully revise the manuscript and refine the relevant details accordingly. Our detailed responses to each of the concerns are presented as follows.\n\nQ1: Additional overhead is involved in assigning scores to clusters.\n\nA1: We agree that calculating cluster reward increases the computational overhead per node expansion, because an additional presampling step is required to evaluate each cluster, along with computations for cluster rewards and path‑aware sampling. However, in practical scenarios, the computational overhead is usually dominated by calls to the policy and value functions as well as the realization of state transitions, and thus the additional cost of node selection is negligible. In particular, by improving search efficiency, our search algorithm is able to identify solutions with fewer node expansions, which in turn reduces the overall computation time. Taking retrosynthesis as an example, the primary bottleneck lies in the policy network’s single-step reaction prediction. On the USPTO benchmark, the average decision time of KeeA* is $38.70$s, which is only slightly higher than SeeA* (Cluster)'s $37.98$s.\n\nQ2: Concerns on the experimental benchmarking, and comparisons of this work to SeeA* with UCT.\n\nA2: In the logic synthesis task, the average ADP reduction rate of SeeA* (Cluster) is $22.5\\\\%$, while KeeA* achieves $25.2\\\\%$. In the retrosynthesis task, SeeA* (UCT) achieves an average success rate of $63.31\\\\%$, below KeeA*’s $63.76\\\\%$. SeeA* (UCT) is not included as a baseline in this paper due to its inferior performance compared to SeeA (Cluster). Although SeeA* (UCT) outperforms SeeA* (Cluster) on the USPTO test set, this benchmark comprises only $190$ carefully selected molecules, and the guiding heuristics are also trained on the USPTO dataset, raising concerns of potential overfitting. Across $4,909$ diverse test cases from seven benchmarks, SeeA* (Cluster) performs better than SeeA* (UCT). Moreover, the actual success rate of KeeA* is $98.9473\\\\%$, consistent with that of SeeA* (UCT), and the discrepancy arises from a rounding error. We appreciate your attention to this detail. Relevant results will be included in the revised paper.\n\n\nQ3: Variability of KeeA* due to randomness.\n\nA3: To quantify KeeA*’s variability induced by randomness, we executed three runs for each of ten random seeds on the USPTO test set. A t-test with the $0.05$ significance level is used to compute the error intervals. The average success rate over all $30$ runs is $98.53\\\\%$, which is comparable to the $98.84\\\\%$ reported in the paper. KeeA* exhibits robust performance across various random seeds, achieving more stable results compared to SeeA* (Cluster). SeeA* not only exhibits a larger variance across multiple runs but also shows greater performance fluctuations under different random seeds, highlighting the superiority of KeeA* over SeeA* (Cluster) with respect to stability.\n|Seed|KeeA* ($\\\\%$)| SeeA*(Cluster)($\\\\%$)|\n|:-|:-|:-|\n|0|$98.07\\pm 0.62$ |$96.49\\pm 1.64$ |\n|1|$97.89\\pm 2.14$ |$98.07\\pm 1.64$ |\n|2|$98.60\\pm 0.62$ |$96.84\\pm 0.00$ |\n|3|$98.60\\pm 1.24$ |$97.89\\pm 1.07$ |\n|4|$98.25\\pm 0.62$ |$98.60\\pm 0.62$ |\n|5|$98.95\\pm 1.07$ |$97.37\\pm 0.00$ |\n|6|$99.30\\pm 1.24$ |$96.67\\pm 2.68$ |\n|7|$98.95\\pm 0.00$ |$96.67\\pm 2.21$ |\n|8|$98.07\\pm 0.62$ |$96.84\\pm 2.83$ |\n|9|$98.60\\pm 0.62$ |$97.54\\pm 0.62$ |\n|All|$98.53\\pm 0.22$ |$97.30\\pm 0.35$ |\n\nQ4: Choice of score metric for the clusters, and the interplay with path-aware sampling\n\nA4: We agree that the clustering score metric can be improved, and it is necessary to design more effective metrics. However, the mean-to-variance ratio employed in this paper aligns with a commonly used risk-adjusted evaluation metric, designed to provide solutions with higher returns relative to their variability, similar to the Sharpe Ratio. Clusters with reduced variance exhibit more concentrated and stable performance, leading to higher reliability in obtaining rewards and improved robustness under uncertainty. Clusters with high mean and low variance are preferred, while those with low mean and high variance are least desirable. In clusters with high mean and high variance, while the chance of sampling superior nodes increases, the risk of sampling inferior nodes also grows, thereby reducing performance stability. For clusters with low mean and low variance, the upper extremes of node quality are constrained, yet their stability increases the probability of achieving relatively consistent and satisfactory performance. The latter two scenarios involve a trade-off between potential gains and stability. Therefore, the cluster scoring method employed in this paper is reasonable. In three independent runs on the USPTO test set, using the mean alone yields an average success rate of $98.07\\pm 1.64\\\\%$, whereas the result of MEAN/STD scoring is $98.53\\pm 1.49\\\\%$, achieving higher average performance with lower variance and reflecting its greater robustness and overall superiority.\n\nIn the situation that deeper nodes may receive a higher reward $f$ than shallower ones, selecting nodes with lower $f$-values at shallower depths reflects the algorithm’s exploratory behavior, rather than greedy expansion based on maximal estimates $f$. Since $f$ is a biased estimate of the true return $f^\\*$, the node with the highest $f$ does not necessarily correspond to the optimal node with the highest $f^\\*$. Depth-penalty encourages selecting nodes beyond those with the highest $f$ values, introducing exploration into the search algorithm to escape local optima. Depth-based penalties have also been adopted in LevinTS [1] to encourage exploration. It is a classical exploitation-exploration trade-off in search algorithms, and is not necessarily detrimental to the search algorithm.\n\n[1] Orseau, Laurent, et al. \"Single-agent policy tree search with guarantees.\" Advances in Neural Information Processing Systems 31 (2018).\n\nQ5: Performance improvement compared to SeeA*\n\nA5:  KeeA* demonstrates greater robustness than SeeA*, while consistently yielding solutions with significantly higher quality. Both SeeA* and KeeA* are sampling-based search algorithms. As shown in Table A3, KeeA* exhibits greater stability across different random seeds, achieving an average success rate of $98.53\\pm 0.22\\\\%$ , outperforming SeeA* (Cluster), which achieves $97.30\\pm 0.35\\\\%$. Furthermore, solution length is a critical indicator of solution quality. With $30$ test runs, KeeA* achieves a significantly shorter average path length of $6.15\\pm0.06$ versus $6.78\\pm0.10$ for SeeA* (Cluster) on USPTO benchmark . Similar advantages in solution quality are also observed on other test sets, as shown in Table 2 of the paper. The substantial difference in solution quality indicates that KeeA*’s advantage is not due to hyperparameter settings obtained by chance. In addition, we conducted a grid search over different hyperparameter settings, with three trials conducted for each configuration. The results are consistent with those in Appendix G: KeeA* demonstrates robust performance across a wide range of hyperparameter settings and outperforms $97.30\\pm 2.36\\\\%$ of SeeA* (Cluster), for which the number of runs is also limited to three. It need to be noticed that the limited $3$ runs lead to higher variability than the $30$-run setting in t-test.\n\n||$\\beta=0.1$|$\\beta=0.3$|$\\beta=0.5$|$\\beta=0.7$|$\\beta=0.9$|\n|:-|:-|:-|:-|:-|:-|\n|$\\alpha=0.1$|$97.72\\pm2.46$|$98.07\\pm2.68$|$97.54\\pm1.64$|$97.72\\pm1.64$|$97.72\\pm1.24$|\n|$\\alpha=0.3$|$97.89\\pm2.83$|$97.72\\pm1.64$|$98.60\\pm2.21$|$98.60\\pm2.68$|$97.54\\pm1.24$|\n|$\\alpha=0.5$|$97.54\\pm2.46$|$98.77\\pm2.46$|$98.07\\pm0.62$|$97.37\\pm1.84$|$97.89\\pm0.00$|\n|$\\alpha=0.7$|$98.25\\pm0.62$|$98.07\\pm1.64$|$98.07\\pm0.62$|$98.77\\pm0.62$|$97.89\\pm1.07$|\n|$\\alpha=0.9$|$64.74\\pm7.70$|$62.81\\pm8.57$|$64.04\\pm6.43$|$60.88\\pm4.32$|$64.74\\pm2.14$|\n\n\nQ6: Theoretical contributions of this work.\n\nA6: In this work, we theoretically demonstrate that cluster sampling outperforms uniform sampling in expectation for the first time. It is not readily intuitive since the advantage of cluster sampling does not universally hold. In uniform sampling, drawing $m$ samples from $N$ nodes yields a probability of $m/N$ for including the optimal node. Under cluster sampling, $m/K$ nodes are sampled from each of the $K$ clusters uniformly. If the optimal node resides in a large cluster with more than $N/K$ nodes, the probability of selecting the optimal node under cluster-based sampling will be lower than $m/N$ in uniform sampling, leading to reduced search efficiency. This paper offers a complementary perspective by first showing that cluster sampling increases the variance of collected candidates. Leveraging the extreme value theorem, a higher expected maximum is achieved by cluster sampling, providing a theoretical justification for SeeA* (Cluster). What's more, Theorem 5.1 establishes a theoretical connection between the predicted value $f$ and the ground-truth value $f^\\*$, which is rarely investigated in neural-guided search algorithms."}]

Author rebuttal:

Meta-review: This paper introduces KeeA, an Asearch variant that incorporates heuristic knowledge into its sampling process. The authors provide a theoretical analysis arguing that SeeA* with cluster sampling outperforms uniform sampling. The KeeA* method is built on this foundation and proposes two techniques: cluster scouting, intended to increase the sampling mean, and path-aware sampling, intended to enhance the sampling variance. The claim is that these allow the algorithm to generate higher-quality candidate solutions. The paper supports this claim with empirical evaluations on retrosynthetic planning and logic synthesis, reporting superior performance compared to SeeA, A, and MCTS.
Decision: Accept (poster)