Neural Genetic Search in Discrete Spaces

GA illustration

1. ... add a flow chart to illustrate GA

Thanks 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:
NGS 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.

Why restrict the vocabulary?

The 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.

We 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.

In 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.

Novelty

3. exactly the same with general GA ... lacks novelty

... just proposes a very general genetic algorithm

Thanks for raising these important points about novelty. First, 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. Second, 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. We appreciate the reviewer’s recognition of the method’s generality. We will clarify these points and better highlight our contributions in the revised manuscript.

Convergence

3. ... will the proposed GA converge?

Unfortunately, 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.

5. ... trapped to a loop?

NGS 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.

Bound/Error bar

4. add a bound/error bar

We provided the $\pm$ 1-sigma range over three independent runs in Fig 5. As depicted in the figure, the results are robust to randomness.

We’ll include the comprehensive results with standard deviation for Tables 1, 2, and 5 in our camera-ready version.

Baselines in Table 5

in Table 5 ... the baseline is just Kim et al., 2025

We 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.

Note 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).

[1] Kim et al. “Ant colony sampling with GFlowNets for combinatorial optimization.”, AISTATS, 2025.

Suggestions

add more explanations to the caption of Figure 1.

Thanks 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.”

Also, please refer to Fig 3 for the detailed generation process. We will also improve the caption of Fig 3.

"replace" => "replaces".

Thanks. We will fix it.

---

We appreciate your valuable input; please let us know if we can provide any further clarifications.

Theoretical guarantees

The method lacks theoretical guarantees or a rigorous understanding of the generated distribution.

Thanks for highlighting the importance of theoretical guarantees and analysis.

We 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.

The 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.

Optimization target and related works

Our 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).

• 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).
• 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.

Thanks for pointing out this important perspective. We will further emphasize our setup in the introduction and at the beginning of Section 3.

[1] Designing Cell-Type-Specific Promoter Sequences Using Conservative Model-Based Optimization. NeurIPS 2024.

Analysis on pretrained model

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.

To 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.

In 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 $**s**^1$ and $**s**^2$. In Eq. 3, we combine $p_{\text{cross}}$ with the original pretrained model $p$ using a binary random variable $M_{s_{t},**s**^1,**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}}$.

Using a pretrained generative model is advantageous:

• 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.
• 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.

As 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.

Effect of mutation rate

... in Figure 6, for the mutation rate $\mu$ of NGS, a very small value (0.001) is always preferred. How does the performance scale with an increasing number of mutations?

Mutation 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.

Although 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.

We 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.

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.

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)

We 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."