Neural Genetic Search in Discrete Spaces
Authors: Hyeonah Kim
Sanghyeok Choi
Jiwoo Son
Jinkyoo Park
Changhyun Kwon
Venue: ICML 2025 poster (2025)
Keywords: Genetic algorithm
test-time search
discrete sequence generation
Primary area: deep_learning

Abstract: Effective search methods are crucial for improving the performance of deep generative models at test time. In this paper, we introduce a novel test-time search method, Neural Genetic Search (NGS), which incorporates the evolutionary mechanism of genetic algorithms into the generation procedure of deep models. The core idea behind NGS is its crossover, which is defined as parent-conditioned generation using trained generative models. This approach offers a versatile and easy-to-implement search algorithm for deep generative models. We demonstrate the effectiveness and flexibility of NGS through experiments across three distinct domains: routing problems, adversarial prompt generation for language models, and molecular design.

Neural Genetic Search in Discrete Spaces
Hyeonah Kim 12
Sanghyeok Choi *
Jiwoo Son
Jinkyoo Park 34
Changhyun Kwon
Abstract
Parent
Offspring
Roustig
O-A-B D-C-E----
Effective search methods are crucial for improv- ing the performance of deep generative models at test time. In this paper, we introduce a novel test-time search method, Neural Genetic Search (NGS), which incorporates the evolutionary mech- anism of genetic algorithms into the generation procedure of deep models. The core idea behind NGS is its crossover, which is defined as parent- conditioned generation using trained generative models. This approach offers a versatile and easy- to-implement search algorithm for deep gener- ative models. We demonstrate the effectiveness and Elexibility of NGS through experiments across three distinct domains: routing problems, adver- sarial prompt generation for language models, and molccular design.
E-D-B C AA
----A-
Langunge
She dances gracefully on stege
The river dances
The liver fows downstream
gracefully and slowly
Molecule
NC D C [[=
D.C.C [CSH] (0))
(C (C@H) (O)) ( Br )
Figure 1. Illustrative examples of parents and offspring in various tasks. Offisprnng are generated through crossover and mutation. Crossover combines parent chromosomes (Yellow and Blue) by restricting the vocabulary to tokens present in one of the parents. Mutation (Pink) occasionally removes this limitation, promoting the solution diversity.
process to refine the outputs of generative models using existing problem-specific GAs (Ahn et al., 2020; Kim et al., 2024). In contrast, our goal is to integrate the evolutionary principles of GAs directly into the generation process of deep models rather than simply chaining the deep models and GAs.
1. Introduction
Genetic algorithms (GAs) have demonstrated remarkable performance across a diverse range of tasks with discrete search space, from classic combinatorial optimization prob- lems (Holland, 1992; Omara & Arafa, 2010; Vidal et al., 2012; Nagata & Kobayashi, 2013; Mahmoudinazlou & Kwon, 2024) to more recent applications in molecular de- sign (Morris et al., 1998; Jensen, 2019; Nigam et al., 2021; Kerstjens& & De Winter, 2022). By maintaining a population of candidate solutions and iteratively applying evolution- ary operators, such crossover and mutation, GAs can systematically explore vast search spaces.
We present Neural Genetic Search (NGS), GA-inspired new search algorithm for deep generative models. NGS enhances the sequential generation process by incorporat- ing genetic operators, crossover, and mutation. Specifically, we define the crossover as a parent-conditione generation, where the model's 's vocabulary is restricted the tokens used in the selected parents, while mutation simply removes this restriction (Figure 1), allowing for more diverse outputs. The generation with the genetic operators proceeds itera- tively with an evolving population, steering the generation toward better results over time, similar to traditional GAs.
In this work, we investigate how to incorporate the powerful search capabilities of GAs into deep generative models. Previous efforts that combined GAs with deep learning for better scarch typically applied GAs after the generation
Since the generation process is still governed by the trained generative models, NGS effectively combine the search ca- pability of GAs with the generative power of deep models. Furthermore, the proposed genetic operators are problem- agnostic, NGS can be applied to any sequential generative model across various tasks, in contrast to traditional GAs, which require significant effort to design wroblem-specitn operators. NGS also can be easily implemented by adding the population and the parent-conditioned masking rule to
'Equal contribution 'Mila - Quebec AI Institute Universsité de Montréal *KAIST "Omelet. Correspondence to: Hyeonah Kim <hyeonah.king @ mila..uebec>>. Sanghyeok Choi <sanghycok.chl kr. Changhyun Kwon <ehk- won @ kr.>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Neural Genetic Search in Discrete Spaces
any existing algorithm with sequential generative models. Finally, compared single-pass generation, the population- based iterative generation in NGS allows the generation process to adapt over time, improving the quality of gener- ated outputs and even the robustness to distribution shifts.
probability of an object X' being generated is defined as po -x:g(()==> Po(s). Additionally, we assume the existence of a reward function rx X - IR which evaluates the quality of generated object x. For instance, in routing problems, we can define rx(x) = -c(x) where c(x) is the length of the route x that we want to minimize. In molecular optimization, & could represent a property such as binding affinity or likeeli,,,ess, which we aim to maximize. Since this work focuses sequence generation, mainly use the reward function over sequences, -xx g.
We evaluated our algorithm in three distinct domains where sequential generative models are widely applied: routing problems, red-teaming language models, and de novo molec- ular design. Our extensive experiments validate that NGS can serve as an effective test-time search method, fulfill- ing its main purpose. We also found that NGS can replace the conventional decoding algorithms, offering improved robustness. Additionally, NGS can be viewed as an auto- mated genetic algorithm that leverages sequential generative models to learn genetic operators, eliminating the need for extensive labor for algorithm design. These results suggest that NGS has significant potential as versatile and efficient search strategy, adaptable to wide range of applications with sequential generative models.
Our task is to maximize the reward function by generat- ing a set of objects using the sequential generative model. Depending on the task, we may also want to maintain the di- versity in the generated objects. We provide a more detailed discussion for each problem we considered in Appendix A.
2.2. Genetic Algorithm
Genetic algorithms (GAs) are evolutionary-inspired meta- heuristics. By mimicking natural selection and genetic evo- lution, GAs iteratively refine population of candidate solu- tions. The main components of GA are as follows:
2. Background
2.1. Sequential Generation in Diserete Space
A representation of potential solution, encoded in a suitable format (e.g.. sequence of numbers).
Chromosome:
This paper focuses on the sequential generation of discrete objects to optimize predefined criteria, i.e., maximize re- ward functions. This setting includes many practical appli- cations, including solution generation for vehicle routing problems, prompt optimization in language models, and atom or fragment-base based generation for molecular optimiza- tion.
A group of chromosomes that evolve over the iterative refinement by GA.
Population:
Selection: Parent chromosomes are selected based on their reward, with chromosomes having higher reward being more likely to be chosen.
Crossover: Parents exchange genetic material to create offspring, combining strengths from both.
Let's E S represent sequence that corresponds a discrete object X. Without loss of generality and to make the explanation simpler, we assume that the sequence length is T. i.e... s = ($1, .2, where E V is a token from vocabulary V. We also denote the partial sequence with length+ f f- as 8<t-
Mutation: Random changes to the offspring's 's genetic material to maintain diversity and explore new regions of the solution space.
Replacement: Offspring replace individuals with low rewards in the population.
We assume that we have a sequential generative policy pe- The probability of a sequence s being generated by the policy pe is:
The challenge in developing GAs lies in designing each component, particularly erossover and mutation operators, that respect the unique problem-specific constraints while effectively searching the solution space. In various do- mains, extensive effort has been devoted to developing highly specialized operators that can handle these complex- ities. While these specialized operators are essential for handling problem-specific constraints, they make chal- lenging to generalize across different problems or adapt to new variations without redesigning the operators.
(s) = II po (88
where 8=1 is defined as an empty sequence and (o(5((8<1) denotes the conditional distribution over next token 8, given the partial sequence S<ı modeled by pg. In our work, this conditional distribution is given by pretrained neural net- work, which is often conditioned on some contexts or con- strained with problem-specific constraints.
Despite these challenges, the evolving framework of GAs remains highly powerful due to their inherent capacity to ex- plore large, complex solution spaces. The GA's population- based approach, which maintains a diverse set of solutions, enables the algorithm to explore many potential solutions si-
Note that the mapping from a sequence to a discrete object g S + X is not necessarily injective, i.e., there can be mul- tiple sequences that correspond to a single object. Thus, the
2

---

Neural Genetic Search in Discrete Spaces
Initialize
Select
Crassover Mutate
Evaluate
Population
Porents
Pu
0.74
Po
Generation with paarett condit-coddii mask
Replace the population
Figure 2. Overview of GA with NGS. (1) The pretrained generative policy sequentially constructs sequences, which correspond to chromosomes, to initialize the population. From this population, (2) parents are selected, and then (3) the policy reproduces offspring by sampling sequences with connt-conditione mask. Finally, (4) the newly generated candidates replace members of the population. completing one evolutionary cycle.
multaneously, increasing the likelihood of finding global op- tima. GAs have been successfully applied to various fields, including routing (Vidal et al., 2012; Nagata & Kobayashi, 2013; Kobeaga et al., 2018; Wouda et al., 2024), molecu- lar design (Morris et al., 1998; Jensen, 2019; Nigam al., 2021; Kerstjens & De Winter, 2022), scheduling (Murata et al., 1996; Gonçalves et al., 2005), and robotics (Davidor, 1991; Lamini et al., 2018; Ismail et al., 2008).
distribution after the crossover with parents (s*,s") as:
Penss(ss (=)((5)))))) [[(s Vists=) (st(S<a);
(2)
where II is an indicator function. As result, the crossover operator functions as a parent-conditioned generative pro- cess.
Mutation. In classical GA, mutation introduces diversity by allowing new genetic material that may not appear in either parent. Analogously, our mutation allows new components by un-masking the masked tokens. Thus, mutation removes the effect of the crossover and reverts to the normal sequence generation. This mutation is conducted in two cases:
3. Neural Genetic Search
We begin by assuming a pretrained sequential generative policy pe-. Pe-TTh The only requirement is that the policy po- sam- ples solutions in factorized manner in Eq. (1), which allows flexible use of training approaches and architec- tures.' An overview of our algorithm is provided in Figure 2 and Algorithm 1.
Constraint-enforring mutation. If all tokens in V/ cannot satisfy the specific constraints the sequence, i.e., E,,e,,,, Pa. (sr = 0, we forcibly do the mutation.
Stochastic mutation. Even if constraints are met, apply mutation with probability μ [0, 1].
3.1. Crossover and Mutation
Considering the mutation, the next token distribution is then modified further as:
We propose -agootia crossover and mutation operations that integrate readily into the generative process of the pretrained model.
PNGS(s sP,1)
Crossover. Given two parent chromosomes (s ss², we define our crossover operation token-restriction, i.., the vocabulary for child is restricted V (st...., s7) U (of...., J.2 With this restricted vocab- ulary. the pretrained generative policy constructs new se- quences while ensuring they follow structural constraints from the parents. The crossover is simply implemented by masking out the tokens not in Vgt.a g² during the sequence generation process in Eq. (1). We define the next token
M a : Po- (8t(8es)
(3)
+ (1 Mo .s sx) Peross(s ($)(((
where the binary variable M indicates whether or not the mutation occurs, i.e.
M M
if Σ pa (5e(8 = S.VV
Bernoulli(u)) otherwise.
'Toough we aim to maximize the reward function, the policy can be trained via supervised learning by distilling pre-collected solutions with designe solvers; see Section 5.1.3.
The resulting probability of a sequence s being generated by the policy with NGS conditioned on parents s' and s becomes:
"W fixed the number parents two, but note that is allowed to use more than two parents in our algorithm.
T
PNGS (s) II PNoS(s wh (solSee).
(4)
3

---

Neural Genetic Search in Discrete Spaces
Construction with pa
MA
G-A-B---C-E-F-
B
= (V.6)
D-G-A-F-EDD-C-B
E-D -B
Crossover
E-D 1-0-B-0
Mutate
CDD---C--A--AA
Figure 3. An illustration of crossover and mutation in TSP (Section 3.1.1). At t', the token-restriction crossover masks out edges not included in the parents, and then the pretrained policy gives the distribution over the remaining valid edges. At = t' + 1, since all edges included in the parents are invalid (X), the constraint-cnforeing mutation activates, allowing selection of any unvisited node.
3.1.1. A CONCRETE EXAMPLE: TSP
the function f as rankp(s), which ranges from 0 (highest reward) to p - (lowest reward). Rank-based prioritized sampling probability defined as:
We provide a concrete example with the traveling sales- man problem (TSP) to provide further insight into how the crossover and mutation work. Generally, a TSP instance is defined on a complete graph = (V, where V is the set of N nodes and the set of edges. The goal is to find a tour that visits each node exactly once and returns to the starting point, minimizing the total travel distance; the reward is defined as the negative total distance. Note that the vocabulary V is the set of edges E, and a token is an edge, ie., 8, E E
Pr(s) (x|P) + rankp(s))
(5)
To generate a pair of parents, we sample two chromosomes without replacement and repeat this independently until we obtain Nowr pairs. Those pairs are fed into the crossover and mutation process to generate the next generation. In the replacement phase, we use P U O, instead of P and sample Npop chromosomes without replacement.
Figure illustrates how new offspring solutions are gener- ated using NGS in TSP. A route is constructed sequentially by choosing edges, with the constraint that each node cannot be visited more than once. At time step i, the policy samples an edge that connects the current node to the next node. This sequence of selected edges is directly used as a chromosome. The policy masks out the edges connecting the current nodes to already-visited nodes to prevent repeated visits. Once all nodes are visited, tour formed by returning to the starting node. During offspring generation, the parent vocabulary is defined as the set of edges that appear in either of the two parent routes; that is, Va+ = U (st, E E where s', s²,s² are selected parents. This in turn defines Peross as in Eq. (2). If no edge in the parent set remains valid-they they all lead to visited nodes-the the token restriction on parents relaxed through meastraint-effrriigg mutation, allowing the policy choose from any edge connected to unvisited nodes to maintain route validity.
Algorithm 1 Neural Genetic Search
Require: Npop. Non, the number of iterations Nuter a pre- trained policy po-
1: P ((str )) New where st -po-(s) {Eq. (1))
2: for i to Niur do
3:
O - 0
4: for n = 1 to Norr do
5: Select parents ,²) from P using Eq.
6: Generate offspring s ~ 22) (E),
7:
O O+ O-OU ((s, r(s))
end for
Replace P by sampling Npup chromosomes from P U O using Eq. (5).
10: end for
3.3. Algorithmic Overview and Viewpoints
The NGS algorithm is summarized in Algorithm 1. NGS offers an improved search capability for the sequential gen- crative models by gracefully combining the strength of GA with the neural policy po-. more detailed analysis of its time and memory complexities can be found in Appendix D. Below, highlight two perspectives NGS: 1) novel decoding strategy that leverages evolutionary principles and 2) as GA enhanced by learned operators.
3.2. Rank-based Selection and Replacement
For selection and replacement, we employ rank-based pri- oritized sampling (Tripp et al., 2020; Kim et al., 2023). Rank-based sampling works as a stochastic elitism, provid- ing controllability for balancing the stochasticity and the eagerness in selection. In this section, we define rank with regard to reward, but it is possible to use multiple criteria see Appendix A.2.
3.3. NGS AS A DECODING STRATEGY
Assume that the population P is filled with [P] chromo- somes. We denote the rank of sequence in P respect to
NGS can viewed as a decoding scheme for sequential generative models because it converts the learned (condi-

---

Neural Genetic Search in Discrete Spaces
TSP500
CVRP500 (
PCTSP500 (4)
OP500 (
64.4
13.5
1.6.9
137.5
64.3
Avg. objertive
16.8
04.2
13.0
135.0
1.6.7
64.1
132.5
16.6
64.0
12.5
130.0
Concorde
PyRP: 62.96
127.5
100
300
1000
3000
10000
100
300
1000
3000
10000
100
300
1000
3000
10000
100
300
1000
3000
10000
Number samples
Number samples
Number of samples
Number samples
Sampling
ACO
NGS (Ours)
Figure 4. Benchmark results on various routing problems. NGS outperformed sampling and ACO by significant margin in all problems, showing its effectiveness as an inference-time search method. See Appendix E.1 for more comprchensive results.
tional) probability distribution into explicit outputs. Specif- ically, NGS belongs to stochastic decoding methods and shares similarities with top-k or top-p sampling, as it mod- ifies (masking-out) the sampling distribution for better re- sults. However, unlike single-pass approaches, NGS adopts population-basee approach, which iteratively refines a set of candidate solutions. This population-base procedure often produces more diverse and higher-quality solutions, especially for complex tasks that benefit from repeated im- provement steps. Our experiments in Section 5. and Sec- tion 5.2 verify that NGS effectively decodes outputs from a model's s learned distribution.
ensure the plausibility, SynNet employs domain-specific re- action rules in the subsequent synthesis planning. Gao et al. (2024) utilizes the generative model to refine the molecules obtained by Graph GA to more synthesizable ones. In Re- inforeed Genetic Algorithm (RGA; Fu et al., 2022), the neural models guides the crossover and mutation process with protein target structure embedding to overcome random- work exploration with predefined rules.
More broadly, there is a growing trend that leverages large language models (LLMs) as a black-box operator within GAs, where parent samples are directly fed into LLM to obtain new samples. These LLM-based GAs have been studied in various domains, including prompt optimization (Meyerson et al., 2024; Liu et al., 2024; Guo al., 2024), molecular design (Wang et al., 2024), and code genera- tions (Lehman et al., 2023; Chen et al., 2023a; Ye et al., 2024). However, a primary challenge is the reliance on hand-crafted prompt engineering, and many approaches continue to employ problem-specific rules along with the LLM- operator (Liu et al., 2024; Wang et al., 2024).
3.3.2. NGS AS GENETIC ALGORITHM
From another perspective, NGS can be viewed genetic algorithm (GA) with learned operator, where pretrained model specifies how to combine and modify parent solutions via parent-conditioned generation. This approach provides two key benefits: (1) it replaces traditional, hand-crafted heuristics, and (2) produces more informed, higher-quality offssring by using the model's learned distribution to guide the combination process, rather than relying on random- walk behavior with predefined rules. As shown in Sec- tion 5.3, NGS can thus serve as an effective alternative GA.
Test-time search for enhanced inference. Recent work in large language models (LLMs) (Bai et al., 2022; Madaan et al., 2023; Snell et al., 2024; Brown et al., 2024) demon- strates that dedicating additional computation at test time can greatly improve outputs (see Dong et al. (2024) for an overview). Meanwhile, combinatorial optimization (CO), its mathematically rigorous algorithmic foundations have inspired line of research integrating traditional al- gorithms into test-time search within deep learning. For instance, Kool et al. (2022) employ restricted dynamic pro- gramming guided by a graph neural network (GNN) that predicts a solution heatmap in routing problems. Mean- while, Ye et al. (2023) and Kim al. (2025) use a predicted edge heatmap in ant colony optimization (ACO) for broader CO applications. Luo et al. (2023) propose new greedy decoding brased search that randomly destroys the generated solutions and reconstructs solutions. Although effective, this method relies on handcrafted rules for destruction. In addition to external algorithmic integrations, there exist a
4. Related Works
Deep generative models with GA. Several studies explore combining GAs and deep generative models, particularly in chemical domains. One direction is that utilizing expert- designed GA to improve the generative models' outcome. Ahn et al. (2020) and Kim et al. (2024) employ Graph GA (Jensen, 2019) whose crossover and mutation are designed to guarantee the validity in chemical space, to refine the generated molecules. Conversely, some researches suggest to incorporate neural models to enhance or design GAs. Notably, in SynNet (Gao et al., 2022b), the neural policy construct offspring conditioned on molecule embedding from the parent, allowing exploiting the generative capabil- ity from the deep model similar to our works. However, to
5

---

Neural Genetic Search in Discrete Spaces
range of self-improvement approaches, such as beam search (Joshi et al., 2021; Choo al., 2022), sampling (also called best-of-N) (Kool et al., 2019), and Monte Carlo Tree Search (Qiu et al., 2022), and active searches (Bello et al., 2016; Hottung et al., 2022; Son et al., 2023) are also employed for refining solutions at test time.
Table I. Results on TSP and CVRP. Gap (%) is measured using Concorde (Applegate et al., 2006) for TSP and Py PyRP (Wouda et al., 2024) for CVRP. "Timc" shows the average duration needed to solve a single instance.
200
N = 500
Gap (%)
Time
Gap (%)
Time
Concorde
1s
10s
LKH3 (Helsgaun, 2017)
0.001
10s
0.022
32s
5. Experiments
GNN (Kim et al.. 2025)
To verify the effectiveness and versatility of the proposed method, we conduct extensive experiments on solving rout- ing problems (Section 5. red-teaming language models (Section 5.2), and molecular optimization (Section 5.3). The code available at http://ggthhbbooommyyyonnnnmmmn
+ Sampling
0.307
2s
1,827
10s
BS (to = 1000)
1.378
4s
20.637
18s
MCTS
0.164
20s
1.324
60s
ACO
0,294
5s
1.733
17s
NGS (Ours)
0,028
5s
0.322
17s
Sampling (long)
0,130
16s
1,479
101s
MCTS (long)
0.126
100s
1.268
300s
ACO (long)
0.102
47s
1.162
167s
5.1. Routing Problems
NGS (Ours, long)
0.011
50s
0.110
170s
In this section, we evaluate ours on various routing problems to verify how NGS efficiently explores the combinatorial solution space test time. We consider four classic routing problems - Traveling Salesman Problem (TSP), Capaci- tated Vehiele Routing Problem (CVRP), Prize-Collecting TSP (PCTSP), and Orienteering Problem (OP) all of which have been widely studied in both genetic algorithm and deep learning research. Detailed descriptions for each task are provided in Appendix C.
VRP
4. 4.0m
21.0m
LKH3 (Helsgaun, 2017)
0,304
2.4m
0.182
18.6m
GNN (Kim et al., 2025)
Sampling
1.487
4s
1.982
7s
CVRP
+ BS (w = 1000)
2.659
4s
2.624
7s
ACO
1.485
7s
1,975
14s
NGS (Ours)
0.981
8s
1.840
15s
Sampling (long)
1.104
0.7m
1.738
1.2m
ACO (long)
1.055
1.2m
1.684
2.3m
NGS (Ours, long)
0.126
1.3m
1,502
2.5m
Table 2. Experiment on TSP with an autoregressive model. We adopt the pretrained model from LEHD. "Time" is measured as the average duration needed to solve single instance.
5.1.1. EXPERIMENTAL SETUP
Implementation details. Following Joshi al. (2021), we adopt graph neural network (GNN) to generate edge heatmap for given problem instance G. The heatmap serves as policy that provides the conditional distribution of which edge to select. This caatmap-based approach has been widely adopted in prior works (Kool et al., 2022; Ye et al., 2023; Kim et al., 2025) thanks to its simplicity and scalability to large instances. We train the GNN for each setting of the problem following the advanced off- off- policy reinforcement learning algorithm suggested by Kim et al. (2025) to obtain the pretrained GNN. All training and testing are performed three times independently.
N=
200
N = 500
Gap (%)
Time
Gap (%)
Time
LEHD RRC
0.020
5.07m
0.172
16.5m
LEHD + Sampling
0.022
0. 0.14m
0.376
1.46m
LEHD + NGS (Ours)
0.004
0.18m
0.152
1.48m
5.1.2. RESULTS
As shown in Table 1, in TSP and CVRP with the number of nodes 200 and 500, NGS achieves significantly smaller optimality gaps than the search baselines. Notably. NGS out- performs both Sampling (long) and ACO (long), which used 10x larger search budget except for CVRP with N 500, demonstrating its search efficiency. Moreover, Figure 4 illus- trates that NGS consistently delivers significant performance gains in all routing problems considered. These results un- derscore the flexibility and broad applicability of NGS. is noteworthy that all the search algorithms are based on the same pre-trained neural network, i.e., all searches start from the same heatmap; the only difference resulting in the huge performance gaps between the algorithms is the search procedure. We omit standard deviations for this benchmark due to their negligible values, but Figure 5 shows + 1-std error ranges across three independent runs. More results are provided in Appendix E.
Baselines. To validate the effectiveness of our method as a test-time search method, we compare ours against var- ious search algorithms while using the same pretrained GNN. These search algorithms include sampling (best-of- N), beam search (BS; Joshi et al., 2021), Monte Carlo Tree Search (MCTS; Qiu et al., 2022), and ant colony optimiza- tion (ACO; Ye et al., 2023; Kim et al., 2025). Note that the ACO-based search of Kim et al. (2025) has already achieved comparable results to ofte-of-the-at learning-basse based meth- ods for routing problems; see details in Appendix B.I.
HHattmap-ased approaches are often referred to as "non- autoregressive" methods in that they only call the neural network once to generate heatmap.
6

---

Neural Genetic Search in Discrete Spaces
Table 3. The attacker model is fine-tuned and evaluated with Source victim model (Llama-3.2-3B -.stts-tttt... The attacker is also evaluated on other various victim models, which corresponds to Transfer setting. The highest mean toxicities among sampling- based algorithms are highlighted with Bold. All the reported values are averaged over five independent runs with distinct secds.
Red-teaming language model aims to generate attack prompts to induce undesirable output from "victim" lan- guage model. Our experiment is based on the approach that fine-tunes "attacker" LM to serve as an automated attack prompt generator (Perez. et al., 2022; Lee et al., 2024a). We fine-tune the attacker LM following the fine-tuning approach proposed by Lee et al. (2024a). Specifically, the reward of an attack prompt defined as the probability of it being toxic (see Appendix A.2 for details). This reward signal is then used for fine-tuning based on the combination of GFlowNets and maximum likelihood estimation. Given the fine-tuned attacker LM, we investigate how the decoding schemes affect the red-teaming performance.
Source
Transfer
Llama 3.2 31-Ims.
Llama-3.1 3.1 1--B--Inst
Llama-3.3- 1---3------- Inst.
Qwen2.5 2.5 7B--ssttt.
Gemma- 2 i--iiit
phi-4 (14B)
Method
Texicity
Div.
Toxicity
BS (w0 4)
0.93
0.24
0.18
0.52
0.00
0.67
0.00
The evaluation of an attack algorithm follows these steps: 1) Generate 1,024 attack prompts using an attacker LM and decoding algorithm to evaluate. 2) For each attack prompt, generate 5 responses using the target victim model, calculate the toxicity of each response using the classifier, and take the average, resulting in the toxicity of the prompt. 3) Calculate average toxicity and diversity over 1,024 attack prompts. Note that generating diverse, high-reward prompts is desirable in red-teaming unlike optimization tasks. We use average pairwise cosine distance in the embedding space using Mvn (Wang et al., 2021) as diversity measure.
BS (w 8)
0.99
0.21
0.37
0.74
0.02
0.91
0.00
Sampling
0.59
0.84
0.28
0.50
0.05
0.25
0.08
Temp. (r=0.8)
0.67
0.82
0.31
0.52
0.04
0.29
0.07
Temp. (r=0.5)
0.79
0.77
0.40
0.58
0.04
0.40
0.04
(k=1))
0.65
0.82
0.31
0.53
0.04
0.25
0.06
top-k (k=5)
0.79
0.35
0.52
0.04
0.28
0.05
lop-p (p=0.8)
0.81
0.32
0.51
0.04
0.30
0.07
lop-p (p5).))
0.78
0.77
0.39
0.56
0.03
0.38
0.04
NGS (Ours)
0.71
0.79
0.45
0.61
0.14
0.59
0.23
Results on real-world instances. We further evaluate the proposed method on real-world benchmark problems, TSPLib (Reinelt, 1991) and CVRPLib (Uchoa et al., 2017). As shown in Table 5 of Appendix E.2, NGS preserves strong performance despite the distribution shift, demonstrating robust adaptability.
Experimental setup. Throughout the experiments, GPT- 2 (Radford et al., 2019) is used as an attacker and Llama- Guard-3-8B (Llama Team, 2024) as the safety classifier. 3.2-a--..-3BBmmm
is used vic- tim. For testing, we evaluate the attacker LM using various victim LMs, not only the one used in the fine-tuning phase, but also unseen LMs:
During fine-tuning,
5.1.3. FURTHER STUDIES
Llama-3.3- 70B-Instrue (Llama Team, 2024), Demma-2-9b-in (Team et al., 2024), 2ween2,5-7B-Instrun (Yang et al., 2024), and phi-4 (Abdin et al., 2024).
NGS with an autoregressive policy. To verify our versa- tility, we integrate NGS with autoregressive policy as well. We adopt the state-of-thed art model, the Light Encoder and Heavy Decoder (LEHD; Luo et al.. 2023), which trained via supervised learning- We compare NGS with Random Re-Construct (RRC) that refines solutions by repeatedly restarting from the randomly destroyed and augmented sub- routes. Table 2 shows that LEHD NGS achieves the lowest optimality gap compared to sampling and RRC. While RRC achieves competitive outcomes, it is specifically tailored to routing problems and can struggle to generate diverse solutions when further constraints are introduced.
Implementation details. First, to further encourage diver- sity in the selection and replacement, we introduce the nov- elty of chromosomes and use weighted rank in rank-based prioritized sampling in Eq. (5). In addition, in crossover, we optionally discard the used token from Va after each token selection to avoid meaningless repetition; please refer to Appendix A.2 for details.
Baselines. We considered canonical sampling- -ased decod- ing strategies for language models, specifically, tempered sampling (Temp.) with temperature т, top-k sampling, and top-p sampling (also known as Nucleus sampling, Holtz- man et al. 2020). We also include beam search (BS) with beam width w, while we did not directly compare against it because it is deterministic.
Sensitivity Analysis. We examine the impact of GA hyper- parameters. As reported in Appendix E.3, NGS consistently performs well across a broad range of parameter settings, indicating its robustness and practical usability.
5.2. Red- Led-Teaming Language Models
Results. We summarized the results in Table 3. The 'Source' column result shows that NGS could compara- bly balance the toxicity (reward) and diversity. The results
In this experiment, we view NGS as an alternative decoding strategy, especially in the context of automated red-teaming of language models (LMs).
7

---

Neural Genetic Search in Discrete Spaces
Table 4. Average scores of Top- 10 molecules discovered within 10,000 evaluations
Type
Score Func. (1)
SynNet
SMILES GA
STONED
Graph GA
NGS (Ours)
qed
0.947 1 0.001
0.947 1 0.001
0.948 1 0.000
0.944 1 0.001
0.948 1 0,000
Property
jnk3
0.673 0.078
0.407 1 0.088
0.616 1 0.083
0.830 1 0.135
0.891
0.059
Optimization
drd2
0.998 + 0.003
0.993 = 0.009
0.998 = 0.004
1.000 = 0.001
1.000 + 0.000
gsk3b
0.824 1 0.069
0.799 1 0.041
0.755 1 0.044
0.915 1 0.065
0.958 1 0.021
perindopril_mng mpo
0.563 1 0.025
0.447 1 0.018
0.503 1 0.020
0,546 1 0.038
0.600 T 0.017
Multi-prop property
ranolazine mpo
0.784 = 0.012
0.768 = 0.030
0.850 = 0.022
0.763 = 0.028
0.854 0.020
Optimization
sitaglipin.mmo
0.337 = 0.051
0.477 = 0.074
0.706 = 0.081
0.629 = 0.068
0.640 + 0.061
(somers_c9h Batisc9hhh00 1n222222ee
0,715 + 0.030
0.878 + 0.049
0.949 = 0.041
0.908 + 0.025
0.914 + 0.023
Structure-based Optimization
deco_hop
0.676 1 0.103
0.621 1 0.006
0,625 1 0.014
0,610 1 0.017
0.851 T. 0.130
scaffold_hop hop
0.517 + 0.011
0.519 + 0.012
0.533 = 0.031
0.530 = 0.035
0.697 0.145
Average
0.703
0.686
0.748
0.768
0.835
in 'Transfer' setting are more remarkable in that NGS out- performs the other decoding schemes significantly, showing robustness toward the distribution shift. This is attributed to NGS's unique characteristic, population-based iterative generation, which could adapt the generation process to- wards better search space by conditioning on promising parents from the previous generations. For more compre- hensive results with standard deviation and results obtained using another model source victim models, please refer to Appendix F.
Baselines. We compare NGS with GA methods specially designed for molecular design: Graph GA (Jensen, 2019), SMILES GA (Brown et al., 2019), STONED (Nigam et al., 2021), and SynNet (Gao et al., 2022b). They utilize fragment- based graphs, SMILES, SELFIES (Krenn et al., 2020), and synthesis, respectively, as molecular represen- tations. Note that in SMILES GA and STONED, where the string-based representations are employed, mutation is solely applied to obtain offspring molecules.
Results. As depicted in Table 4, NGS outperforms previous GA methods in average Top-10 scores across 10 tasks in different types by achieving the best scores in 8 tasks out of 10. These results highlight the effectiveness of NGS as an alternative GA method despite the computational cost of policy training. In Appendix G, we compare NGS with the results with training only. Morcover, NGS manages to produce valid molecules without explicitly enforcing validity checks or SMILES grammar constraints at each step. Because the policy is trained on valid examples, it naturally learns to generate syntactically correct SMILES strings and thus maintains a high rate of validity in its outputs.
5.3. De novo Molecular Design
In this experiments, we focus on verifying the effectiveness of NGS as a new GA method, unlike the experiments in rout- ing and red-teaming. In molecular design, various studies have found that GA methods still remain as strong baselines for recent deep learning methods. Furthermore due to the black-box properties in chemical space, test-time search with deep generative models have rarely studied. In several works, Graph-baser based GA (Jensen, 2019), expert-desinned GA, is directly employed to refine the solutions or support the policy explorations (Ahn et al., 2020; Kim et al., 2024; Gao et al., 2024; Wang et al., 2024; Lee et al., 2024b)
6. Conclusion
Experimental setup. De novo molecular design aims to discover molecules with the desired property, which is measured by the score function. We follow the experimen- tal setting in the Practical Molecular Optimization (PMO) benchmark (Gao et al., 2022a), which limits evaluations to 10,000. We provide further details in Appendix A.3.
Contributions. We propose Neural Genetic Search (NGS), a test-time search algorithm that combines the population- based exploration of genetic algorithms with the expres- sive power of pretrained generative models. By replacing domain- specific crossover rules with a parent-conditioned generation process and allowing mutation through unre- stricted sampling, NGS offers an iterative refinement strat- egy that boosts solution quality across diverse tasks without needing specialized heuristics. Our experiments, conducted across diverse tasks such as routing problems, adversarial prompt generation, and molecular design, show that NGS improves solution quality compared to previous search meth- ods. Beyond its strong performance, NGS is flexible and easy to adopt: it only requires a pretrained model that con- structs discrete outputs sequentially.
Implementation details. This work employs a string-based molecular representation, the Simplified Molecular-Inpu Line-Entry System (SMILES) strings (Weininger, 1988), to generate molecules; the examples are provided in Figure 1. Following prior works (Olivecrona et al., 2017; Kim al., 2024), we adopt an LSTM policy to generate SMILES se- quences. Since we have a limited budget, we use 8K calls to train the policy using Nets and 2K to conduct the genetic search with NGS; see details in Appendix B.3.
8

---

Neural Genetic Search in Discrete Spaces
Future works. A promising extension of NGS is its inte- gration into model-based optimization (MBO) frameworks, where the objective function is proxy model rather than di- rectly interacting with environments. The population- based and diversity-awan nature of NGS can enhance the robust- ness for inaccurate proxies, especially with conservative proxy estimations (Trabucco et al., 2021; Yu et al., 2021; Chen et al., 2022: 2023b; Reddy et al., 2024).
corde TSP solver, 2006. URL htwp:: www.mah.
Bai, Y., Kadavath, S., Kundu, S., Askell, A., Kernion, J., Jones, A., Chen, A., Goldie, A., Mirhoseini, A., McKin- non, C.,, et al. Constitutional AI: Harmlessness from Al feedback. arXiv preprint
2022.
Balas, E. The prize collecting traveling salesman problem. Networks, (9(6):21-636) 1989.
Limitations. NGS has several key limitations. First, its effectiveness relies the quality of the underlying neural policy. The potential performance gains may be limited if the pretrained model's 's distribution does not encompass high- quality solutions. In such cases, the policy can be fine-tuned by incorporating NGS, similar to approaches introduced by Choo al. (2022); we leave this future work. Another limitation is that NGS introduces set of GA-related hy- perparameters. While we provide the rationale behind their selection and demonstrate their robustness across diverse configurations, practitioners may still need to adjust them for specific tasks. Lastly. NGS lacks theoretical guaran- tees for generated distributions or convergence to optimal solutions, since both deep generative models and genetic algorithms are inherently difficult to analyze theoretically.
Bello, I,, Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 161 1.09940, 2016.
Bengio, E., Jain, M., Korablyov, M., Precup, D., and Ben- gio, Y. Flow network based generative models for non- iterative diverse candidate generation. In Advances in Neural Information Processing Systems (NewrIPS), 2021.
Bengio, Y., Lahlou, S., Deleu, T., Hu, E. Tiwari, M., and Bengio, E. GFlowNet foundations. Journal of Machine Learning Research, 24(210):1-55, 2023.
Brown, B., Juravsky, J., Ehrlich, R., Clark, Lc, Q. V.,
Ré, C., and Mirhoseini, A. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024.
Impact Statement
Neural Genetic Search (NGS) enhances the test-time per- formance of deep generative models by integrating genetic Eggorithm-inspiree search into the generation process. It is model-agnostic and broadly applicable any generative model that produces discrete objects through sequential gen- eration. NGS offers lightweight yet effective framework for improving solution quality, diversity, and robustness across a wide range of domains.
Brown, N., Fiscato, M., Segler, M. H., and Vaucher, A. C. GuacaMol: benchmarking models for de novo molecular design. Journal of Chemical Information and Modeling. 59(3):1096-1108 2019.
Chen, A., Dohan, D., and So, D. EvoPrompting: Lan- guage models for code-level neural architecture search. Advances in neural information processing systems (NeurIPS), 2023a.
Acknowledgements
This work supported by the National Research Foun- dation of Korea (NRF) grant funded by the Korean gov- ermment (MSIT) (85-2023-00255550, RS-2024-00410082,, RS-2025-00563763),
Chen, C., Zhang, Y., Fu, J., Liu, X. S., and Coates, M. Bidirectional learning for offline indinite-width model- based optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
References
Chen, C., Zhang, Y., Liu, X., and Coates, M. Bidirectional learning for offline model-based biological sequence de- sign. In International Conference on Machine Learning (ICML), 2023b.
Abdin, M., Aneja, J., Behl, H., Bubeck, S., Eldan, R., Gunasekar, S., Harrison, M., Hewett, R. J., Javaheripi, M.. Kauffmann, P., et al. Phi-4 technical report. arXiv preprint Xww::2212.08090 2024.
Choo, J., Kwon, Y.-D., Kim, J., Jae, J., Hottung, A., Tierney, K., and Gwon, Y. Simulation -gidded beam search for neural combinatorial optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Ahn, S., Kim, J., Lee, H., and Shin, J. Guiding deep molec- ular optimization with genetic exploration. Advances in neural information processing systems (NeurIPS), 2020.
Dantzig, G. B. and Ramser, J. H. The truck dispatching problem. Management Science, 6(1):80 1959.
Applegate, D., Bixby, R., Chvatal, V., and Cook, W. Con-

---

Neural Genetic Search in Discrete Spaces
Davidor, Y. Genetic Algorithms and Robotics: A heuristic strategy for optimization, volume 1. World Scientific Publishing Company, 1991.
Hottung, A., Kwon, Y.-D., and Tierney, K. Efficient ac- tive search for combinatorial optimization problems. In International Conference on Learning Representations (ICLR), 2022.
Dong, X., Teleki, M., and Caverlee, J. A survey LLM inference-time self self-improvement. arXiv preprint arXiv:2412 14352, 2024.
Ismail, A., Sheta, A., and Al-Weshah, M. A mobile robot path planning using genetic algorithm in static environ- ment. Journal of Computer Science, 4(4):341-344, 2008.
Fu, T., Gao, W., Coley, C., and Sun, J. Reinforced genetic algorithm for structure-based drug design. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Jensen, J. H. A graph-based genetic algorithm and gener- ative model/Monte Carlo tree search for the exploration of chemical space. Chemical Science, 10(12):357-33772 2019.
Gao, W., Fu, T., Sun, J., and Coley, C. Sample efficiency matters: a benchmark for practical molecular optimiza- tion. Advances in Neural Information Processing Systems (NeurIPS), 2022a.
Joshi, C. K., Cappart, Q., Rousseau, L.-M.,, and Laurent, T. Learning TSP requires rethinking generalization. In International Conference Principles and Pracfice of Constraint Programming (CP), 2021.
Gao, W., Mercado, R., and Coley, C. W. Amortized tree generation for bottom-up synthesis planning and synthe- sizable molecular design. In International Conference on Learning Representations (ICLR), 2022b.
Kerstjens, A. and De Winter, H. LEADD: Lamarckian evolutionary algorithm for de novo drug design. Journal of Cheminformatics, 14(1):3, 2022.
Kim, H., Kim, M., Choi, S., and Park, J. (eenetic-giided GFlowNets for sample efficient molecular optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Gao, W., Luo, S., and Coley, C. W. Generative artificial intelligence for navigating synthesizable chemical space. arXiv preprint arXiv:2410.3394. 2024.
Golden, B. L., Levy, L.,, and Vohra, R. The orienteering problem. Naval Research Logistics (NRL), 34(3):307- 318, 1987.
Kim, M., Berto, F., Ahn, S., and Park, J. Bootstrapped train- ing of condiicond generator for offline design of biological sequences. Advances in Neural Information Processing Systems (NeurIPS), 2023.
Gonçalves, J. F., de Magalhães Mendes, J. J., and Re- sende, M. G. A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research, 167(1):77-95, 2005. ISSN 0377-2217. doi:
Kim, M., Choi, S., Son, J., Kim, H., Park, J., and Bengio, Y. Ant colony sampling with GelowNets for combinato- rial optimization. International Conference Artificial Intelligence and Statistics (AISTATS), 2025.
012. URL /Rt.sttess///w....ceeeeeeeeeeeee com/ /tlaace/artcce////////7722221222
Kobeaga, G., Merino, M., and Lozano, J. A. An efficient
lutionary algorithm for the orienteering problem. Com- puters & Operations Research, 90:42-59, 2018. ISSN 0305-0548. doi: http:://tbiioggg//0.000lcoooooo0
Guo, Q., Wang, R., Guo, J., Li, B., Song. K., Tan, X., Liu, G., Bian, J., and Yang, Y. Connecting large language mod- els with evolutionary algorithms yields powerful prompt optimizers. In International Conference on Learning Representations (ICLR), 2024.
003. URL htt.thttts///wwwtte httppppps//www.ccccccneeeeeeeeee sttiene//attcceee///////00001111
Kool, W., van Hoof, H., and Welling, Attention, learn to solve routing problems! In International Conference on Learning Representations (ICLR), 2019.
Helsgaun, K. An extension of the Lin- Hinn-Keniighan-Heee Hellgauu TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, pp. 966- 980, 12 2017. doi: 10.13314///G 40807.
Kool, W., van Hoof, H., Gromicho, J., and Welling, M. Deep policy dynamic programming for vehicle routing problems. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPATOR), 2022.
Holland, J. H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, 1992.
Krenn, M., Häse, F., Nigam. A., Friederich, P., and Aspuru- Guzik, A. Self-referencing embedded strings (SELFIES): A 100% robust molecular string representation. Machine Learning: Science and Technology, 144):045024, 2020.
Holtzman, A., Buys, J., Du, L., Forbes, M., and Choi, Y. The curious case of neural text degeneration. In International Conference on Learning Representations (ICLR), 2020.
10

---

Neural Genetic Search in Discrete Spaces
Lamini, C., Benhlima, S., and Elbekri, A. Genetic algorithm based approach for autonomous mobile robot path plan- ning. Procedia Computer Science, 127:180-188 2018.
docking using a lamarckian genetic algorithm and an empirical binding free energy function. Journal of com- putational chemistry, 19(14); 1639-166,,,,, 1998.
Lee, S., Kim, M., Cherif, L., Dobre, D., Lee, J., Hwang, S. J., Kawaguchi, K., Gidel, G., Bengio, Y., Malkin, N., et al. Learning diverse attacks on large language models for robust red-teaming and safety tuning, arXiv preprint arXiv:2405. 1855.88544 18540, 2024a.
Murata, T., Ishibuchi, H., and Tanaka, H. Ge- netic algorithms for flowshop scheduling prob- lems. Computers & Industrial Engineering, 30
(4): (4):10011,,7,, 1996. ISSN 0360-8352.
doi:
http://c...a///..000000002222220 URL
Lee, S., Kreis, K., Veccham, S. P., Liu, M., Reidenbach, D., Paliwal, S. G., Vahdat, A., and Nie, W. Molecule genera- tion with fragment retrieval augmentation. In Advances in Neural Information Processing Systems (NeurlPS), 2024b.
Nagata, Y. and Kobayashi, A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. INFORMS Journal on Computing, 25(2):346- 363, 2013.
Lehman, J., Gordon, J., Jain, S., Ndousse, K., Yeh, C.,, and Stanley, K. O. Evolution through large models. In Handbook of Evolutionary Machine Learning, pp. 331- 366. Springer, 2023.
Nigam, A., Pollice, R., Krenn, M., dos Passos Gomes, G., and Aspuru-Guzik, A. Beyond generative models: super- fast traversal, optimization, novelty, exploration and dis- covery (STONED) algorithm for molecules using SELF. IES. Chemical Science, 12(20):7079-700 70900 2021.
Liu, X., Xu, N., Chen, M., and Xiao, C. AutoDAN: Generat- ing stealthy jailbreak prompts aligned large language models. In International Conference on Learning Repre- sentations (ICLR), 2024.
Olivecrona, M., Blaschke, T., Engkvist, O., and Chen, H. Molecular de-oovo design through deep reinforcement learning. Journal of Cheminformatics, I1): 2017.
Llama Team, A. M. The Ilama herd of models, 2024. URL https:: / //////raaa arriv..iiv.////ai//aaaa/aaaaavvv orgo abs////b///// /407s 21333.
Omara, A. and Arafa, M. M. Genetic algorithms for task scheduling problem. Journal of Parallel and Distributed Computing, 70(1):13-22, 2010. ISSN 0743-7315. doi: http:://bb..ogg/oo..00o6//.o...p
Luo, F. Lin, X., Liu, F., Zhang, Q. and Wang, Z. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances in Neural Infor- mation P Processing Systems (NeurIPS), 2023.
009. URL httphtttsss//ww..sceeeeee....... octerne//rricceee//////772333333
Madaan, A., Tandon, N., Gupta, P., Hallinan, S., Gao, I.., Wiegreffe, S., Alon, U., Dziri, N., Prabhumoye, S., Yang, Y., Gupta, S., Majumder, B. P., Hermann, K., Welleck, S., Yazdanbakhsh, A., and Clark, P. Self-refine: Iterative refinement with self-feedback. In Advances in Neural Information Processing Systems (NeurlPS), 2023.
Perez, E., Huang, S., Song, F,, Cai, T., Ring, R., Aslanides, J.. Glaese, A., McAleese, N., and Irving, G. Red teaming language models with language models. In Conference Empirical Methods in Natural Language Processing (EMNLP), 2022.
Mahmoudinazlou, S. and Kwon, C. hybrid genetic algo- rithm for the min-max multiple traveling salesman prob- lem. Computers & Operations Research, 162:105 2024.
Qiu, R., Sun, Z., and Yang, Y. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Malkin, N., Lahlou, S., Deleu, T., Ji, X., Hu, E., Everett, K., Zhang, D., and Bengio, Y. GFlowNets and variational inference. In International Conference on Learning Rep- resentations (ICLR), 2023.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. Language models are unsupervised multitask learners. OpenAl blog, 188):9 2019.
Reddy, A. J., Geng, X., Herschl, M. H., Kolli, S., Kumar, A., Hsu, P. D., Levine, S., and loannidis, N. M. Designing cell-type-specific promoter sequences using conservative model-based optimization. In Advances in Neural Infor- mation Processing Systems (NeurIPS). 2024.
Meyerson, F., Nelson, M. J., Bradley, H., Gaier, A., Moradi, A., Hoover, A. K., and Lehman, J. Language model crossover: Variation through few-shot prompting. ACM Transactions on Evolutionary Learning, 4(4):1-40, 2024.
Morris, G. M., Goodsell, D. S., Halliday, R. S., Huey, R.,
Reinelt, G. TSPLIB A traveling salesman problem library. ORSA journal on computing, 3(4):376-384 1991.
Hart, W. E., Belew, K., and Olson, J. Automated

---

Neural Genetic Search in Discrete Spaces
Snell, C., Lee, Xu, K., and Kumar, A. Scaling IIm test- time compute optimally can be more effective than scal- ing model parameters. arXiv preprint arXiv:2408.03314, 2024.
Wouda, N. A., Lan, L.,, and Kool, W. PyVRP: a high- performance VRP solver package. INFORMS Jour- nal on Computing, 2024. doi: 10. 10.1287/jjo::0223.0033 URL nttps:://oi.e org/ 1tt.////11////...// 20233. 0055.
Son, J., Kim, M., Kim, H., and Park, meta-learning scheduled adaptation with guided explo- ration for mitigating scale shift on combinatorial opti- mization. In International Conference on Machine Learn- ing (ICML), 2023.
scale
Yang, A., Yang, B., Hui, B., Zheng, B., Yu, B., Zhou, C., Li, C.. Li, C.,, Liu, D., Huang, F., Dong, G., Wei, H., Lin, H., Tang, J., Wang, J., Yang, J., Tu, J., Zhang, J., Ma, J., Xu, J., Zhou, J., Bai, J., He, J., Lin, J., Dang, K., Lu, K., Chen, K., Yang, K., Li, M., Xue, M., Ni, N., Zhang, P., Wang. P., Peng. R., Men, R., Gao, R., Lin, R., Wang, S., Bai, S., Tan, S., Zhu, T., Li, T., Liu, T., Ge, W. Deng, X., Zhou, X., Ren, X., Zhang, X., Wei, X., Ren, X., Fan, Y., Yao, Y., Zhang, Y., Wan, Y., Chu, Y., Liu, Y., Cui, Z., Zhang. Z., and Fan, Z. Qwen2 technical report. arXiv preprint arXiv:2407.10677 2024.
Team, G., Riviere, M., Pathak, S., Sessa, P. G., Hardin, C., Bhupatiraju, S., Hussenot, L., Mesnard, T., Shahri- ari, B., Ramé, A., et al. Gemma Improving open language models at practical size. arXiv preprint arXiv:2408.0011 0000000011100 18, 2024.
Trabucco, B., Kumar, A., Geng, X., and Levine, S. Conser- vative objective models for effective offline model-based optimization. In International Conference on Machine Learning (ICML), 2021.
Ye, H., Wang, J., Cao, Z., Liang, H., and Li, Y. Deep- ACO: Neural-enhanced ant systems for combinatorial optimization. In Advances in Neural Information Pro- cessing Systems (NeurIPS), 2023.
Tripp, A., Daxherger, E.,, and Hernández-Lobato, M. Sample-efficient optimization in the latent space of deep generative models via weighted retraining. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Ye, H., Wang, J., Cao. Z., Berto, F., Hua, C., Kim, H., Park, J., and Song, G. ReEvo: Large language models as hyper-heuristics with reflective evolution. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Uchoa, E.,, Pecin, D., Pessoa, A., Poggi, M., Vidal, T., and Subramanian, A. New benchmark instances for the ca- pacitated vehicle routing problem. European Journal of Operational Research, 257(3):845 -558 2017.
Yu, S., Ahn, S., Song, L., and Shin, J. RoMA: Ro- bust model adaptation for offline model-based optimiza- tion. Advances in Neural Information Processing Systems (NeurIPS), 2021. 2021.
Vidal, T. Hybrid genetic search for the evrp: Open-source implementation and swap" neighborhood. Computers & Operations Research, 140:105643, 2022.
Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., and Rei, W. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, (113)661-6224, 2012.
Wang, H., Skreta, M., Ser, C.-T., Gao, W., Kong, L., Strieth- Kalthoff, F., Duan, C., Zhuang. Y., Yu, Y.. Zhu, Y., al. Efficient evolutionary search over chemical space with large language models. arXiv preprint arXiv:2406. 169766 2024.
Wang, W., Bao, H., Huang, S., Dong, I.., and Wei, Minilmv2: Multi-head self-attention relation distillation for compressing pretrained transformers. In Findings of the Association for Computational Linguistics: ACL- IJCNLP 2021, pp. 2140-2151, 2021.
Weininger, D. SMILES, chemical language and informa- tion system. 1. introduction to methodology and encoding rules. Journal of chemical information and computer sci- ences, 28(1):31-3333 1988.
12

---

Neural Genetic Search in Discrete Spaces
A. Detailed problem formulations
This section provides more detailed explanations each sequential generation problem we considered.
A.1. Routing problems
In all routing problem we considered, a problem instance can be defined on the fully connected graph g = (V,E), where is the set of N nodes, and a set of edges, each associated with a weight representing the distance between two connected nodes. The goal is to find the optimal route that satisfies all problem-speetie constraints.
In this context, candidate solution for routing problem be defined can be represented as sequence of edges. Thus, the vocabulary corresponds to all the edges, i.e., V = E, chromosome corresponds to sequence of edges, and the policy Pa- is conditional distribution that enables sequential selection of edges. Note that the policy should be conditioned on the problem-specific constraints, which mask out the infeasible edges based on these constraints. The reward r is defined as the objective function of each problem. We provide details about problem-specific components for each problem in Appendix C.
of edges that compose route, which in turn
A.2. Red- Teamien Language Models
In this task, we use an attacker language model (LM) to generate attack prompts to elicit toxic responses from victim LM. The V corresponds to the vocabulary of the attacker LM (GPT-2 (Radford et al., 2019) in our experiment), and a chromosome is an attack prompt (a sentence in natural language). We define our sequential generative policy po- with a pretrained attacker LM equipped with top-p (Nucleus) sampling (Holtzman al., 2020) (p=0.95). The top-p serves "plausibility constraint," which prevents the crossover (Eq. (2)) from generating highly unlikely tokens.
The reward for an attack prompt is defined as the average toxicity of the response from the victim LM given the attack prompt. The toxicity is the probability of the 'unsafe' token of the safety classifier model (Llama-Guard-3 (Llama Team, 2024)) given the victim's 's response.
We found that the token restriction using Vss,s as suggested in Section 3.1 could lead to meaningless repetition of set of words in the parents (and this often 'hacks' the reward function and gives better quantitative results). To prevent this undesirable behavior, we discard the token from Vs, once it is selected. Algorithmically, at step t, sample s, following Eq. (3) and then replace Vs, Va,,, with Va \ {s+).
As discussed in Section 5.2, it is desirable to generate a diverse set of toxic prompts in the red-teaming language model task. To promote diversity in the population, we incorporate novelty measure during selection and replacement. We define the novelty / of a chromosome s as averaged pairwise cosine distance against the population, i.e.,
v(s:P)
1
Σ S'EP
(1-
(1-cosiee cosine similarity(e(s).e()))
(6)
PP|
where e is the sentence encoder MMi (Wang et al., 2021)). Then, we define weighted rank using both reward and novelty as follows:
rank = (1 - w) rank, + w (sn
where w is novelty rank weight (we set w 0.1) and rank,,p and ranku, reward and novelty rank, respectively. This weighted rank used for selection and mutation, following the rank-based selection rule in Eq. (5).
A.3. De novo molecular design
We employ the string-based representation, the Simplified Molecular- Line-Entry System (SMILES; Weininger, 1988), which represents molecules using ASCII text. SMILES encodes a molecule's 's connectivity (which atoms are bonded to which), as well as additional details such as bond types, charges, and stereochemistry. We directly adopt the vocabulary set from Olivecrona et al. (2017), which consists of 55 tokens, including start and end tokens. The examples are illustrated in Figure 1.
The reward defined as a normalized scalar in [0, 1] that measures a pharmaceutically relevant property. For example, QED quantifies the drug-likenes of molecules, whereas JNK3, DRD2, and GSK3b measure a molecule's 's activity against specific proteins. Please refer to Gao et al. (2022a) and Brown et (2019) for additional details on each task.
13

---

Neural Genetic Search in Discrete Spaces
Lastly, we employ an LSTM policy without explicitly enforcing validity constraints. Following previous work (Olivecrona al., 2017), the poliey is initialized with a prior policy trained public dataset (e.g.. ZINC250K) to learn valid SMILES patterns. We then rely on this policy to guide the crossover process and produce valid SMILES strings.
B. Additional experimental details
Computing resource. We use server with two sockets of AMD EPYC 7542 32-Core Processor, and a single GPU, the NVIDIA RTX A6000, for the routing and De novo molecular design experiments. For the red-teaming language models task, we use cloud server with four NVIDIA A100 HBM2e 80GB PCIe gpus.
B.1. Routing problems
Training procedure. We followed the training procedure of Kim al. (2025).* Specifically, we train a graph neural network (GNN) that generates heatmaps using the GFlowNet (Bengio et al., 2021) training, combined with off-policy exploration through the local-search operators (2opt for TSP, Swap* (Vidal, 2022) for CVRP, and destroy-and-reeair local search for others). For details regarding the training procedure, please refer to the original paper (Kim et al., 2025).
Hyperparameters. For sampling, we use 1,000 for mini-batch size. We use 100 for the number of ants in ACO and the number of offspring in NGS, which makes the two algorithms have the same number of iterations: 10 when generating 1,000 candidates and 100 when 10,000 (long). Note that for TSP and CVRP, we employ the local search after solution generation for all baselines, as usually done heatmap-basee approaches. We use 100 for both population size and offspring size of NGS, 0.01 for the stochastic mutation rate μl, and 0.001 for the weight-shifting factor in rank- sampling.
B.2. Red-Teaming Language Models
Fine-tuning procedure. We mainly followed the two-stage fine-tuning procedure of Lee al. (2024a). In the first stage, a policy explores the space of prompts during the GFlowNet-based fine-tuning. All evaluated prompts stored in the buffer. In the second stage, we fine-tune the attack language model (LM) with high-quality prompts obtained by filtering prompts with both high toxicity and high likelihood from the buffer. For more details, please check the original paper (Lee et al., 2024a).
Hyperparameters. At test time, we attack a victim LM using the fine-tuned attack LM. We considered common sampling- based decoding strategies as baselines, including sampling, tempered sampling with temperature E [0.5, 0.8), top-k sampling with k E [5, 10), and top-p sampling with p E [0.5, 0.8]. Each baseline only changes the specified hyperparameter, and the others remain the same. For NGS, we use 256 and 16 for the population size and offspring size, respectively. We use 0.05 for the stochastic mutation rate and 0.01 for the weight-shifting factor in the rank-based sampling.
B.3. De novo molecular design
Training procedure. Unlike routing problems or language- modell attacks, molecular design constrains the total number of evaluations rather than distinctly separating training from inference. Therefore, we allocate 8K evaluations to train the policy and then conduct NGS with the trained policy. Following Kim et al. (2024), we adopt generative flow networks (GFlowNets; Bengio et al., 2021; 2023) but without guided exploration. Because GFlowNets are off-policy, they can leverage replay training extensively, thus exhibiting sample-efficieed learning. Indeed, the results in Kim et al. (2024) show that GFlowNets outperform REINVENT (Olivecrona et al., 2017) even without guided exploration. Specifically, we initialize our policy with the same pretrained parameters used in REINVENT, trained on an unlabeled dataset. We then use the allocated 8K evaluations to train this policy by generating samples, storing them in an experience buffer, and minimizing the trajectory- balance loss (Malkin et al., 2023) using those buffered samples. We follow the hyperparameter setup from Kim et al. (2024), including the batch size, number of replay training iterations, inverse temperature, and learning rates; please refer to their original implemetation for more details.
Hyperparameters. During NGS, we use the population size and offspring size as 100 and 5, respectively. The stochastic mutation rate y is set as 0.01, and the weight-shifting factor x in Eq. (5) as 0.01.
'nttps://githut con/ aomm/aioe ai4co/r144c Shtpps: potttps://geee h/ttthub.tttttt////// comm/hyennakinm. gen.eiineeeeeeeeeeeeeeeeeeeeeeee
14

---

Neural Genetic Search in Discrete Spaces
C. Description of routing problems
In routing problems, the problem is defined on the fully connected graph G = (V, 8), where Vis the set of N nodes, and a set of edges, each associated with a weight representing the distance between two connected nodes. The goal is find the optimal route that satisfies all given constraints. In this context, a route is defined as a cycle within the graph, and the vocabulary is composed of the set of edges& E. We provide details about problem-specific components for each problem. All problem instances are generated according to Ye et al. (2023).
C.1. Traveling salesman problem
The traveling salesman problem (TSP) aims find the shortest route that visits all cities exactly once and returns to the starting point. A solution is defined as a Hamiltonian cycle with minimum total weights (i.e., total distance to travel), Consequently, the reward function r(z) is defined as negative value of total distance. Starting from a random node, route is generated by sequentially selecting the next node to visit. This is done by choosing an edge connected to the current node, thus extending the route. To avoid revisiting nodes, the model masks out edges that lead to already visited nodes.
C.2. Capacitated vehicle routing problem
The capacitated vehicle routing problem (CVRP; Dantzig & Ramser, 1959) is defined on a fully connected graph g EV, where V is the set of nodes, which includes a depot (the starting and ending point for the vehicles) and the customers (the locations that need to be served with demand), and & the set of edges representing the connections between nodes, each with an associated travel distance. In CVRP, we assume the use of multiple homogeneous vehicles, each with a capacity Q. and the goal is to serve all customers exactly once while minimizing the total travel distance. The reward function is defined as the negative of the total distance, and the solution consists of a set of multiple routes, each starting and ending at the depot (a special node with zero demand). Additionally, the total demand of each route cannot exceed the vehicle capacity Q.
Similar to the TSP, the solution is generated sequentially by selecting the next node, which corresponds to choosing an edge connected to the current node. However, the process begins at the depot, which allows multiple visits. At each step, the policy masks out edges that lead to already visited nodes, except for the depot. To enforce the capacity constraints, edges leading to nodes with demands that exceed the remaining vehicle capacity are also masked out to have zero probability.
C.3. Prize-collecting traveling salesman problem
The prize-collecting traveling salesman problem (PCTSP: Balas, 1989) a variation of the TSP, where the constraints for visiting all nodes are relaxed. Instead, the PCTSP introduces the prize constraints about the minimum prizes to collect. In the PCTSP, each node has prize and penalty; thus, the salesman gets prizes for visiting the cities and penalties for the unvisited cities. The reward is defined as the summation of the total distance and the net penalties from un-visited nodes.
Similar to the CVRP, a route starts and ends with the depot whose prize and penalty are zero. To prevent repeated visiting, the policy masks out all edges connected to already visited nodes. In addition to satisfy the prize constraints, when the collected prize is less than the minimum prizes the edge connected to the depot is also masked out.
C.4. Orienteering problem
The orienteering problem (OP; Golden et al., 1987) is a variation of the classical routing problems where the objective is to find a route that maximizes the total prize collected from visited cities, subject to a constraint on the total travel distance. Unlike the PCTSP, where the goal is minimize penalties for unvisited cities, the orienteering problem is focused on maximizing the reward within a limited travel budget.
In the OP, each city has prize associated with it, and the objective is to visit a subset of cities in order to maximize the total prize collected, while ensuring that the total distance traveled does not exceed specified maximum distance. Thus, tshe reward is defined as the sum of the prizes from the cities visited.
Similar to the PCTSP, the solution is represented as a set of routes starting from a depot. Each route must respect the distance constraint while selecting cities that contribute to the total prize. To prevent revisiting cities, the policy masks out edges connected to previously visited cities, ensuring that each city is visited at most once. Additionally, the edge connecting the depot can be masked out if the total distance constraint has already been met exceeded, ensuring no additional unnecessary travel occurs.
15

---

Neural Genetic Search in Discrete Spaces
D. Time and memory complexities
The proposed crossover, mutation, selection, or replacement Section 3 does not require a significant amount of time to perform. However, may increase the generation time depending on the mini-batch size.
Consider that want generate K sequences in total and assume that mini-batch size is limited to (K m). Then, we need to iterate [ K/m] times of generation, regardless of the generation algorithm. On the other hand, when considering the NGS iteration with specified Npop and Non, we need to iterate [Nop/m) mm] + [(K NNpp)/Not) [Nanmm times. When m is smaller than Nof the number of iterations of NGS is similar to the normal generation. Otherwise, the number of iterations can increase much larger than [K/m]. In practice, however, m is usually smaller compared to Nor. and thus, the time complexity is not increased too much (see Table 2).
Our algorithm slightly increases memory usage, the population should be kept in memory, which usually negligible. In routing problem experiments, NGS requires additional memory since we need construct the N x N edge matrix for each chromosome. However, using the sparse matrix could largely relieve this.
E. Additional experimental results on routing problems
E.1. Extended results
Figure shows extended results for the routing problems (Section 5.1), including the results for instances with 1,000 nodes. Overall, NGS substantially outperforms the baseline methods all settings except for CVRP with 1,000 nodes. We suspect two reasons for the worse results in CVRP1000: (1) our heatmap-based policy may be suboptimal given the increased complexity of large-scale CVRP, and (2) the post-processing local search, Swap (Vidal al., 2012), largely overshadows any differences between the generation algorithms.
TSP20D
CVRP200
PCTSP200 (
OP200
Rvg. objective value value
10.78
59-
10.76
8.4
58
28.2
57
10.74
56
Concorde
28.0
PARR
10.72
TSP500 (1)
CVRP500 (1)
PCTSP500 (1)
OP500 1
Avg objective valbe
36.9
13.5
13.0
135.0
64.1
132.5
64.0
12.5
130.0
Concerde
63.9
PyRR:: 62.96
127.5
TSP1000 (1)
CVRP1000 ( (1)
PCTSP1000 (1)
0P1000 ( (T)
Avg. objective value
20.0
280
19.5
121.9
19.0
121.8
18.5
23.4
18.0
260
23.2
Concorde
121.5
121.6
PyWRP: 119.29
17.5
255
300
1000
3000
10000
300
1000
100
1000
3000
10000
300
3000
10000
Number of samples
Number of samples
Number samples
Number of samples
Sampling
ACO
NGS (Ours)
Figure 5. Comprehensive results on routing problems.
E.2. Results on real-world instances
We benchmark our model against baselines on real-world TSP and CVRP instances from TSPLib (Reinelt, 1991) and CVRPLib-X (Uchoa et al., 2017). We use the models trained on random uniform instances size 200, 500, and 1,000 for evaluation of ISP/CVRPLib instances with sizes 100-299, 300-699, and larger than 700, respectively. As shown in Table
16

---

Neural Genetic Search in Discrete Spaces
NGS achieves significantly better performance than the baselines these real-world datasets.
Table 5. Average optimality gap with the
solutions TSPLib and CVRPLib-X.
N
#
Sampling
ACO
NGS (ours)
CVRPLib TSPLib
100-299
30
1.29%
1.26%
1.08%
300-699
10
3.32%
3.19%
1.65%
700-1499
12
5.62%
5.40%
3.14%
100-299
43
2.44%
2,43%
2.04%
300-699
40
3.42%
3,43%
3.27%
700-1001
17
4.15%
4.16%
4.02%
E.3. Sensitivity analysis
We conduct sensitivity analysis for the key hyperparameters- - population size Nppp offssring size Non. and the mutation rate μl on TSP and CVRP with 500 nodes. The results in Figure 6 indicate that smaller population size generally yields better outcomes, likely due to more greedy parent selection. Increasing the offspring size tends to degrade performance, as it reduces the number of search iterations.
TSP500
TSP500
TSP500
Avg. objective value (1)
16.85
Sampling
Avg. objective value (1)
16.85
Sampling
16.85
Sampling
ACO
16.80
16.80
Avg. objective value
16.80
16.75
MCTS
16.75
16.75
MCTS
16.70
NGS (Ours)
16.70
16.70
16.65
16.65
NGS (Ours)
16.65
(Ours)
16.60
16.60
CVRP500
CVRP500
CVRP500
Avg. objective value (1)
Sampling
Avg. objective value )
Sameling
Avg. objective value (1)
Sampling
64.20
ACO
64.200
64.20
NGS (Ours)
64.18
64.175
64.18
64.16
NGS (Urs)
64.16
NGS (Ours)
64.14
64.14
64.100
64.12
64.075
64.12
100
200
300
10
50
70
100
150
0.001
0.003
0.01
0.03
0.1
Npop
Nowt
Analysis of the population size N Sum-
Analysis of the offspring size Non.
(c) Analysis of the mutation μ.
Figure 6. Sensitivity analysis on TSP and CVRP with 500 nodes.
17

---

Neural Genetic Search in Discrete Spaces
F. Additional experimental results red-teaming language models
F.I Extended Results
In Table 6, we provide a more detailed version of Table with standard deviation. Also, in Table 7, we provide additional results obtained by using Llama-3.1-8B 8---trruuct (Llama Team, 2024) as source victim LM.
Table The attacker model finc-tuned and evaluated using Llama-3.2 1amma-3.2-B-IInttruue toxicities among sampling-base based algorithms are highlighted with Bold. All the reported values are averaged over five independent runs with distinct seeds. Note that the diversity for the Transfer settings is almost identical to the Source setting.
Source vietim model. The highest mean
Source
Transfer
Llama-3 1amma-3.3708-. Inst.
Liama-3 1amnu-3.2:-0 3.2--B--mmss Inst.
Llama-3 3. 1-8B-18SSS Inst.
Qwen2.5 11-22--7B-JB 15-7B-Inss Inst.
Gemma-22 -- 2.9b-it
phi-4 (14B)
Method
Toxicity
Div.
Toxicity
BS (w = 4)
0.93 0.01
0.24 + 0.00
0.18 0.02
0.52 + 0.04
0.00 + 0.00
0.67 + 0.05
0.00 + 0.00
BS 8)
0.99 0.00
0.21 0.00
0.37
0.00
0.74 0.03
0.02 0.02
0.91 0.01
0.00 0.00
Sampling
0.59 + 0.02
0.84 + 0.00
0.28 + 0.02
0.50 0.01
0.05 + 0.00
0.25 + 0.01
0.08 + 0.01
Temp- (r=0.8)
0.67 0.01
0.82 0.00
0.02
0.52 0.00
0.04 0.00
0.00
0.07 + 0.01
Temp. (r=0.5)
0.79 + 0.01
0.77 0.00
0.40
0.00
0.04 + 0.00
0.40
0,04 + 0.00
top-k (k=10)
0.65 0.02
0.82+
+.02
0.53 0.01
0.04 0.00
0.25
0.06 0.01
top-k (k=5)
0.69 + 0.01
0.79+
0.35+ 0.01
0,52+
0.04 + 0.00
+.01
0.05 + 0.00
top-p (p=0.8)
0.69 0.01
0.81
0.32
0.51
0.04 0.00
0.01
0.07 0.00
top-p (p=0.5)
0.78 0.01
0.77 0.00
0.39 0.02
0.01
0.03 0.00
0.38 + 0.01
0.04 0.01
NGS (Ours)
0.71 0.01
0.79 0.01
0.45 0.03
0.61 0.01
0.14 0.03
0.59 0.06
0.05
Table 7. The attacker model is fine-tuned and evaluated using L -B-tsruttttt as Source victim model. The highest mean toxicities among sampling-ber algorithms are highlighted with Bold. All the reported values are averaged over five independent runs with distinct seeds. Note that the diversity for the Transfer settings is almost identical to the Source setting.
Source
Transfer
Llama- 3.1 8B- 1-8BBInntt Inst.
Llama-3 1ama--322-30 1.tta--.----Inn- 2--3-IInst.
3.ama-333--11 70B-00--11 Inst.
Twem2.5-7BB-in Inst.
Gemma-2 2-9-i- ---iitt
phi-4 (14B)
Method
Toxicity
Div.
Toxicity
BS (w 4)
0.97 + 0.01
0.22 + 0.00
0.49 - 0.00
0.98 + 0.00
0.71 + 0.06
0.02 + 0.00
0.03 + 0.00
BS (w
0.71 = 0.01
0.26 - 0.00
0.25 = 0.00
0.65 = 0.01
0.29 = 0.07
0.00 0.00
0.01 = 0.00
Sampling
0.53 + 0.01
0.84 + 0.00
0.45 =.01
0.52 = 0.01
0.18 + 0.00
0.30 0.01
0.25 0.01
Temp. (7=0.8)
0.60 + 0.01
0.81 0.00
0.50 0.01
0.56
0.27
0.22 0.00
Temp. (7=0.5)
0.73 + 0.01
0.66
0.57 = 0.01
0.65 = 0.01
0.38 - 0.00
0.00
0.14
0.12 0.12 0.01
top-k (k=10)
0.59
0.00
0.55 0.00
0.21
0.23 0.29
top-k (k=5)
0.62 0.01
0,53 0.00
0.57 =
0,22 0.26 0.25
top-p (p=0.8)
0.61 0.01
0.82
0.51 = 0.01
0.57 0.01
0.22
0.31 0.00
0.24
top-p (p=0.5)
0.01
0.75 +
0.57 -
0.63
0.01
0.01
0.21
NGS (Ours)
0.65 0.01
0.77 0.02
0.55 0.02
0.59
0.39 0.01
0.50
0.51 0.02
18

---

Neural Genetic Search in Discrete Spaces
G. Additional experimental results molecular design
Table 8. Average Top-10 10 scores with 10K training and ours where we conduct NGS during last 2K evaluations.
Training (8K)
Type
Score Func. (1)
Fully Training
NGS (2K)
qed
0.948 0.000
0.948 0.000
Property Optimization
jnk3
0.883 + 0.054
0.891 + 0.059
drd2
1.000 + 0.000
1.000 + 0.000
gsk3b
0.935 0.049
0.958 0.021
perindopril_mpu ranolazine_mpe
0.616 0.035
0.600 0.017
Multi property Optimization
0.862 0.022
0.854 0.020
sitagliptin_mpo
0.568 + 0.076
0.640 0.061
isomers, wetpersschhh02222222222
0.911 0.030
0.914 0.023
Structure-based Optimization
deco_bo _hop scaffold.hop
0.837 + 0.135
0.851 + 0.130
0.699 + 0.147
0.697 0.145
Average
0.826
0.835
In this section, we examine the effect of conducting NGS rather than training the policy by fully leveraging the limited evaluation budgets. The results Table shows that NGS achieves higher Top- 10 scores overall. Although NGS discovers new high-reward molecules during search, the policy exploration is still effective. These findings suggest that NGS can be further enhanced alternative GA method by incorporating policy exploration.
19


Reviews:
[{"review_id": "Y7k9mPitC3", "reviewer": "Reviewer_r57C", "summary": "This paper proposes a test-time search method, Neural Genetic Search (NGS), for efficient searching of generative models in discrete spaces. NGS incorporates genetic algorithms into the generation procedure, where the generative model is used to generate offspring conditioned on parents. Experimental results across different domains showcase the effectiveness of NGS.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Theoretical guarantees\n> The method lacks theoretical guarantees or a rigorous understanding of the generated distribution.\n\nThanks for highlighting the importance of theoretical guarantees and analysis. \n\nWe acknowledge that rigorous theoretical guarantees, such as formal convergence rates, are indeed valuable. However, deriving such guarantees for deep-learning-based search algorithms is exceptionally challenging. Moreover, in the genetic algorithm literature, existing guarantees are often contingent on idealized assumptions or specific problem classes, making them difficult to generalize widely. We will include this in our limitations of Section 6.\n\nThe primary goal of this work is to provide a methodological and empirical contribution. We demonstrate NGS’s flexibility and effectiveness by presenting performance gains on four distinct routing problems, adversarial prompt generation for language models, and molecular optimization tasks. We believe these results clearly illustrate the practical benefits of our proposed approach across various domains.\n\n### Optimization target and related works\n\nOur goal is to find a discrete object $x$ that maximizes a given objective function $f$ (lines 73-74). More specifically, we aim to find $x^*=\\arg\\max_{x \\in \\mathcal{X}} f(x)$, where $\\mathcal{X}$ is a set of all possible objects. Our objective function $f$ can be ground truth, noisy simulation, or even proxy models (i.e., model-based optimization).\n- When the objective function is not group-truth-based, we use diversity as additional evaluation criteria; generating more diverse solutions leads to more robustness to the reward hacking (e.g., our red-teaming experiments).\n- NGS can be incorporated into MBO methods that use conservative proxy models, e.g., the one proposed in [1]. Verifying the effectiveness of NGS within the MBO framework is an interesting future work. We will include this discussion in the conclusion. Note that MBO methods are orthogonal to NGS, so they are not included as our baseline.\n\nThanks for pointing out this important perspective. We will further emphasize our setup in the introduction and at the beginning of Section 3. \n\n[1] Designing Cell-Type-Specific Promoter Sequences Using Conservative Model-Based Optimization. NeurIPS 2024.\n\n### Analysis on pretrained model \n> An analysis of how the pretrained model helps the parent-conditioned offspring generation and what makes an optimal policy in the generation would be helpful.\n\nTo clarify how the pretrained model supports parent-conditioned offspring generation, we refer to Equations (2)–(4). Note that, for simplicity, we omit the explicit notation $\\theta^*$ for the pretrained policy.\n\nIn Eq. 2, our crossover mechanism works by masking out tokens not present in the parents. So $p_{\\text{cross}}$ is essentially the pretrained model with certain tokens masked out based on selected parents $\\textbf{s}^1$ and $\\textbf{s}^2$. In Eq. 3, we combine $p_{\\text{cross}}$ with the original pretrained model $p$ using a binary random variable $M_{s_{t},\\textbf{s}^1,\\textbf{s}^{2},\\mu}$ that indicates whether mutation occurs. If mutation occurs, we sample the next token from the full pretrained model $p$; if not, we sample from the masked version $p_{\\text{cross}}$.\n\nUsing a pretrained generative model is advantageous:\n- Reward-awareness: Since the model is trained to generate high-reward solutions, it implicitly captures useful patterns for guiding offspring toward promising regions—not just blending parents, but extrapolating toward better candidates.\n- Validity: In contrast to hand-crafted crossover rules, the pretrained model has already learned how to construct valid solutions, so offspring remain feasible without requiring domain-specific heuristics.\n\nAs will be discussed in the following question, balancing exploitation (resembling high-reward parents) and exploration (introducing new components via mutation) is important to find optimal solutions.\n\n### Effect of mutation rate\n\n> ... in Figure 6, for the mutation rate $\\mu$ of NGS, a very small value (0.001) is always preferred.\n> How does the performance scale with an increasing number of mutations?\n\nMutation encourages explorations during the generation procedure by removing the token restriction from crossover. Using a too-low value of $\\mu$ makes it hard to escape from local optima.\n\nAlthough the results in Fig 6c for TSP seem to give better results with a lower mutation rate, this trend is not consistently observed in CVRP or the red-teaming LM task.\n\nWe have included additional experiments analyzing the impact of different mutation rates (𝜇) on the red-teaming LM task using Llama-3.2 victim. As shown in the table below, our method remains robust across a range of 𝜇 values. \n\n|$\\mu$|Toxicity|Diversity|\n|-|-|-|\n|0.01|0.699 ± 0.029|0.790 ± 0.013|\n|0.02|0.698 ± 0.009|0.791 ± 0.011|\n|0.05|**0.712** ± 0.008|0.791 ± 0.015|\n|0.1|0.681 ± 0.015|0.801 ± 0.010|\n|0.2|0.659 ± 0.012|**0.804** ± 0.008|", "claims_and_evidence": "Most claims in the submission are supported by convincing evidence. However, there are several gaps in the proposed method and experiments to support the novelty and performance of this paper. Please refer to details in \"Methods and Evaluation Criteria\" and \"Experimental Designs or Analyses\" sections.", "methods_and_evaluation_criteria": "Most parts of the proposed methods and evaluation make some sense. However, there remain several issues:\n\n- The method lacks theoretical guarantees or a rigorous understanding of the generated distribution. \n- The optimization target is not clear: is it to generate samples to maximize the evaluation criteria $r(x)$, or to generate reward-tilted distributions $\\frac{1}{Z}p_0(x) e^{r(x)/\\alpha}$? For each case, the methods to compare, the tasks, and the evaluations are different. For the case of reward maximization, the tasks and evaluations should be robust to reward hacking and there exist model-based optimization methods (eg. [1]) for this. For the case of the reward-guided generative model, the evaluations should consider some measures to verify that the generated sample remains valid samples with respect to the pretrained distribution, and there are many reward-guided sampling methods for this (eg. [2-4]). However, the paper lacks discussion and comparison to these methods.\n- An analysis of how the pretrained model helps the parent-conditioned offspring generation and what makes an optimal policy in the generation would be helpful.\n\n[1] Designing Cell-Type-Specific Promoter Sequences Using Conservative Model-Based Optimization. NeurIPS 2024.\n\n[2] Unlocking guidance for discrete state-space diffusion and flow models. ICLR 2025.\n\n[3] Practical and asymptotically exact conditional sampling in diffusion models. NeurIPS 2023.\n\n[4] Derivative-free guidance in continuous and discrete diffusion models with soft value-based decoding. arXiv 2024.", "theoretical_claims": "There are no theoretical claims in this paper.", "experimental_designs_or_analyses": "- In the ablation study in Figure 6, for the mutation rate $\\mu$ of NGS, a very small value (0.001) is always preferred. This seems to indicate that the mutation is harmful to the algorithm.\n- How does the performance scale with an increasing number of mutations?\n- The model lacks comparison with model-based optimization methods and reward-guided methods (see \"Methods and Evaluation Criteria\").", "relation_to_broader_scientific_literature": "The paper is related to sequential generation, discrete space optimization, and evolutionary algorithms.", "essential_references_not_discussed": "- Model-based optimization: \n\n  [1] Designing Cell-Type-Specific Promoter Sequences Using Conservative Model-Based Optimization. NeurIPS 2024.\n\n- Reward-guided sampling:\n\n  [2] Unlocking guidance for discrete state-space diffusion and flow models. ICLR 2025.\n\n  [3] Practical and asymptotically exact conditional sampling in diffusion models. NeurIPS 2023.\n\n  [4] Derivative-free guidance in continuous and discrete diffusion models with soft value-based decoding. arXiv 2024.", "other_strengths_and_weaknesses": "The paper proposes an interesting method that combines evolutionary algorithms and discrete space generative models, and experiments on a variety of domains. I'm open to increasing my score if the author can provide a convincing clarification on the optimization target and a more rigorous understanding of the algorithm, as well as a complete comparison to related baselines.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QAuNZTEeCk", "reviewer": "Reviewer_Synt", "summary": "Neural Genetic Search (NGS) which incorporate ideas from genetic algorithms with generative models as test-time compute method to improve quality/diversity of generation. Crossover: Generating each token autoregressively, masking all tokens not used in the parents. Mutation: random chance of removing the masking token restrictions at each token allowing for more diverse output. It evolves a population akin to GA; given some reward function between 0 and 1, they use rank-based priority sampling to push toward higher rewards. This approach is problem-agnostic, as long as autoregressive token-based models are used and that there is a reward. Its powerful, because it doesn't need backpropagation.\n\nThey evaluate NGS on molecule generation, language models, and routing problems comparing to beam search, Monte Carlo Tree\nSearch, ant colony and other search algorithms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review. We greatly appreciate your recognition of the novelty and effectiveness of our proposed method, as well as your positive remarks on the diversity and rigor of our experiments. \n\n\n> NGS can be viewed as an automated genetic algorithm with learned genetic operators (yes, but they should clarify that this is for autoregressive models with tokens)\n\n\nWe appreciate your suggestion to clarify the scope of our claim regarding NGS as an automated genetic algorithm with learned operators. We will revise the sentence in lines 62-64 (left) to \"NGS can be viewed as an automated genetic algorithm that leverages sequential generative models to learn genetic operators, eliminating the need for extensive labor for algorithm design.\"", "claims_and_evidence": "Claims:\n- novel method (yes, as far as I can tell)\n- effective test-time search method based on the 3 sets of experiments (yes, they have good evidence)\n- NGS can replace conventional decoding with improved robustness (yes, they have good evidence)\n- NGS can be viewed as an automated genetic algorithm with learned genetic operators (yes, but they should clarify that this is for autoregressive models with tokens)", "methods_and_evaluation_criteria": "Yes the evaluation and problems tested are very diverse and convincing", "theoretical_claims": "There is no strong theory, its a clever algorithm to improve diversity/quality based on a reward without backprop", "experimental_designs_or_analyses": "See \"Methods And Evaluation Criteria\"", "relation_to_broader_scientific_literature": "Fits well with recent trend for test-time compute and its very general and can be applied to various situations, basically any autoregressive model. They properly cite GA with generative models and test-time compute literature as far as I can tell.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": ".", "other_comments_or_suggestions": ".", "questions_for_authors": ".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aBHEzreUHF", "reviewer": "Reviewer_Xt6a", "summary": "The paper proposes a novel test-time search method that integrates genetic algorithm evolutionary mechanisms into deep generative models, particularly for sequential discrete generation tasks. NGS defines crossover as a parent-conditioned generation process, wherein offspring are generated by restricting the vocabulary based on selected parents, and introduces mutation by occasionally removing this restriction to enhance diversity. Experiments are conducted on routing optimization, adversarial prompt generation for language models, and molecular design, and show its effectiveness.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### GA illustration\n> 1. ... add a flow chart to illustrate GA\n\nThanks for the valuable feedback. We’ve found that Fig 2 can also serve as a flow chart of general GA. We’ll revise the caption to further explain the overall GA process and our distinguished features:  \nNGS leverage pretrained generative models within the GA framework. While conventional GAs typically relies on random initialization and problem-specific crossover and mutation, NGS begins with samples from the pretrained models and evolves the population by incorporating novel crossover and mutation mechanisms.\n\n### Why restrict the vocabulary?\n\nThe token-restriction in our **crossover** has the same purpose as crossover in traditional GAs: to focus search on promising regions near high-quality parents. By restricting vocabulary to tokens present in parents, we guide the generation process toward promising regions near parents.\n\nWe agree that crossover alone would limit applicability for tasks like text editing. This is why the **mutation** is essential in NGS. When the mutation occurs, token restrictions are removed, allowing the model to introduce tokens not present in either parent. This is how “changing/replacing one single word” happens in our framework.\n\nIn practice, we’ve found this balance between restricted crossover and strategic mutation effectively explores the solution space. We’ll make this point clearer in the revised manuscript.\n\n### Novelty\n> 3. exactly the same with general GA ... lacks novelty\n\n> ... just proposes a very general genetic algorithm\n\nThanks for raising these important points about novelty.\nFirst, Genetic Algorithms (GAs) are meta-heuristics that define general search protocols, but their effectiveness depends heavily on how components like crossover and mutation are designed—often requiring significant domain expertise. NGS introduces a novel approach by learning these operators using a sequential generative model, as detailed in Section 3.3.2.\nSecond, our work is positioned within the deep learning domain, and our primary contribution is proposing NGS as a test-time search method for sequential generative models. To our knowledge, this is the first approach that integrates GAs directly into the generative process via neural models—unlike prior work that applies GAs to outputs post-generation. A novel combination of a traditional algorithm and a deep generative model should not be underrated.\nWe appreciate the reviewer’s recognition of the method’s generality. We will clarify these points and better highlight our contributions in the revised manuscript.\n\n### Convergence\n> 3. ... will the proposed GA converge?\n\nUnfortunately, we don’t have formal theoretical guarantees for the convergence. Please refer to our response to reviewer r57C (Theoretical guarantee) for detailed discussions regarding this point. \n\n> 5. ... trapped to a loop?\n\nNGS won’t get trapped in a loop as long as the pretrained policy has full support (which is usually true). Our stochastic mutation mechanism ensures that all $x\\in\\mathcal{X}$ have a positive probability of being generated. Specifically, $p_{\\text{NGS}}(x) > 0$ whenever $p_{\\theta^*}(x)>0$. This property prevents the algorithm from getting stuck exploring only a subset of the solution space.\n\n### Bound/Error bar\n> 4. add a bound/error bar\n\nWe provided the $\\pm$ 1-sigma range over three independent runs in Fig 5. As depicted in the figure, the results are robust to randomness.\n\nWe’ll include the comprehensive results with standard deviation for Tables 1, 2, and 5 in our camera-ready version.\n\n### Baselines in Table 5\n> in Table 5 ... the baseline is just Kim et al., 2025\n\nWe limit our baselines to the various search methods that can be used with the **same pretrained model** for fair evaluations. The works you mentioned rely on different pretraining schemes from what we used.\n\nNote that the “ACO” baseline represents [1] ’s performance. NGS significantly outperformed this method, which is notable because [1] already demonstrated superior performance compared to the other works you mentioned. For comprehensive comparisons against other algorithms, please refer to Kim et al. (2025).\n\n[1] Kim et al. “Ant colony sampling with GFlowNets for combinatorial optimization.”, AISTATS, 2025.\n\n### Suggestions\n> add more explanations to the caption of Figure 1.\n\nThanks for the suggestion! We will add the following: “Two parent chromosomes (Yellow, Blue) are crossover by following one of the parents at each step of the sequential generation process. Mutation (Pink) occasionally occurs that can take any allowed actions modeled by the generative model.”\n\nAlso, please refer to Fig 3 for the detailed generation process. We will also improve the caption of Fig 3.\n\n> \"replace\" => \"replaces\".\n\nThanks. We will fix it.\n\n---\n**We appreciate your valuable input; please let us know if we can provide any further clarifications.**", "claims_and_evidence": "Claims and evidence in the paper look good to me.", "methods_and_evaluation_criteria": "1. The problem is defined clearly to me. In section 2.2, I would suggesting to add a flow chart to illustrate GA to audience who is not familiar with it.\n\n2. Line 139-Line 149, why should we put the restriction on vocabulary? For example, in language generation, changing/replacing one single word may make the sentence look better. If we restrict the vocabulary, it seems that some tasks such as text editting can not longer be done.\n\n3. I feel the proposed method in section is exactly the same with general GA, which may indicate that the paper lacks novelty. Also, will the proposed GA converge? \n\n4. In results such as Table 1 and Table 2, I would suggest to add a bound/error bar to indicate if the comparisons are significant.\n\n5. Is there any chance that the algorithm is trapped to a loop?\n\n6. I feel in Table 5, for both CVRP and TSP, the baseline is just Kim et al., 2025, which is too limited as the author mentioned a lot of other works such as Kool et al., 2022; Ye et al., 2023; Kim et al., 2025.", "theoretical_claims": "No heavy theories are involved.", "experimental_designs_or_analyses": "In results such as Table 1 and Table 2, I would suggest to add a bound/error bar to indicate if the comparisons are significant.", "relation_to_broader_scientific_literature": "I feel the paper just proposes a very general genetic algorithm by modifying some of its steps. To me it's definitely related to works that use genetic algorithm for data generation but not that novel.", "essential_references_not_discussed": "References look good to me.", "other_strengths_and_weaknesses": "Please refer to my comments in previous sessions.", "other_comments_or_suggestions": "1. Please add more explanations to the caption of Figure 1. When I read that part, I still got confused about how GA works to generated offsprings.\n\n2. Line 84, right side: \"replace\" => \"replaces\".", "questions_for_authors": "Please refer to my comments in previous sessions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper incorporates methods from genetic algorithms into the (test time) generative process of autoregressive models. Notably, they define a "crossover" operation which limits the vocabulary of children conditioned on that of the parents. The method is a nice contribution in the sense that it bring ideas from GA into generative modeling in language which expand on the functionality of existing models.

There are concerns about theoretical guarantees, but I think the authors are right that lacking these guarantees should not signify that the main ideas here have value: both in the context of deep learning and GA said guarantees (particularly with LLMs) are hard to quantify. Other than that, I think that there's potential for future contributions as tokenized autoregressive models are only becoming more popular (such as in vision and RL).
Decision: Accept (poster)