Research map / Image generation / Autoregressive and latent generation
Neural Genetic Search in Discrete Spaces
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Neural Genetic Search (NGS), a test-time search that uses parent-conditioned generation (token-restricted crossover with unrestricted mutation) over a pretrained sequential generative policy, evaluated on routing, LLM red-teaming, and molecular design.
Problem
Improving test-time search for deep sequential generative models over discrete spaces, where existing GA hybrids apply problem-specific genetic operators after generation rather than integrating evolution into generation.
Approach
Crossover is defined as parent-conditioned generation: the pretrained policy's vocabulary is masked to tokens appearing in two parents, and mutation un-masks the vocabulary (forced when constraints block all parent tokens, or stochastically with probability mu), with rank-based selection and replacement forming a population loop.
Key results
- On TSP-500 with the same GNN, NGS reaches a 0.322% gap versus 1.733% for ACO and 1.827% for sampling at similar time; with a 10x budget, NGS reaches 0.110% (long).
- In red-teaming with Llama-3.2-3B source, NGS achieves transfer toxicity of 0.45 on Llama-3.1-8B and 0.59 on Qwen2.5-7B versus best sampling baselines around 0.40 and 0.40.
- In molecular design over 10 PMO tasks, NGS achieves the best average Top-10 score (0.835) versus 0.768 for Graph GA, and best on 8 of 10 tasks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use NGS instead of MCTS | GNN routing policy · TSP N=200 | Gap (%): 0.164 -> 0.028 | Helped |
| Use NGS instead of MCTS | GNN routing policy · TSP N=500 | Gap (%): 1.324 -> 0.322 | Helped |
| Use NGS instead of ACO | GNN routing policy · CVRP N=200 | Gap (%): 1.485 -> 0.981 | Helped |
| Use NGS instead of ACO | GNN routing policy · CVRP N=500 | Gap (%): 1.975 -> 1.840 | Helped |
| Use NGS instead of sampling | LEHD autoregressive policy · TSP N=200 | Gap (%): 0.022 -> 0.004 | Helped |
| Use NGS instead of sampling | LEHD autoregressive policy · TSP N=500 | Gap (%): 0.376 -> 0.152 | Helped |
| Use NGS decoding rather than temperature sampling at τ=0.5 | GPT-2 red-teaming attacker · Llama-3.2-3B-Instruct source | Toxicity: 0.79 -> 0.71 | Hurt |
| Use NGS instead of sampling | GPT-2 red-teaming attacker · Llama-3.2-3B-Instruct source | Diversity: 0.84 -> 0.79 | Hurt |
| Use NGS rather than sampling-based decoding | GPT-2 red-teaming attacker · Transfer victims | Toxicity | Helped |
| Use NGS rather than Graph GA | Molecular optimization policy · Molecular benchmark average (10 tasks) | Top-10 score: 0.768 -> 0.835 | Helped |
| Use NGS rather than STONED | Molecular optimization policy · Sitagliptin MPO | Top-10 score: 0.706 -> 0.640 | Hurt |
| Use NGS during the last 2K evaluations instead of spending all 10K on training (ablation) | Molecular optimization policy · Molecular benchmark average | Top-10 score: 0.826 -> 0.835 | Helped |
Surprising findings
- A smaller population size generally yields better outcomes in sensitivity analysis, attributed to greedier parent selection.
- In red-teaming, the token-restriction crossover could lead to meaningless repetition of parent words that hacks the reward, requiring discarding used tokens.
Limitations
- Effectiveness depends on the quality of the underlying pretrained policy; gains limited if its distribution lacks high-quality solutions.
- Introduces GA hyperparameters (population size, offspring size, mutation rate) that may need task-specific tuning.
- No theoretical guarantees on generated distributions or convergence to optimal solutions.
Experimental setup
Datasets: ZINC250K TSPLib CVRPLib-X PMO benchmark
Benchmarks: TSP CVRP PCTSP OP TSPLib CVRPLib-X PMO
Metrics: optimality gap (%) mean toxicity diversity (average pairwise cosine distance) Top-10 average score running time
Baselines: Sampling Beam search MCTS ACO LKH3 Random Re-Construct SynNet SMILES GA STONED Graph GA Temperature sampling top-k sampling
Builds on: genetic algorithm GFlowNet Graph GA LEHD rank-based prioritized sampling
Closest papers by meaning
- Towards Neural Architecture Search through Hierarchical Generative Modeling (ICML 2024 · similarity 0.86)
- Genetic-guided GFlowNets for Sample Efficient Molecular Optimization (NeurIPS 2024 · similarity 0.84)
- An LLM-Empowered Adaptive Evolutionary Algorithm for Multi-Component Deep Learning Systems (AAAI 2025 · similarity 0.84)
- Variational Search Distributions (ICLR 2025 · similarity 0.84)
- Gen-Searcher: Reinforcing Agentic Search for Image Generation (NeurIPS 2026 · similarity 0.84)
- Runtime Analysis of Evolutionary NAS for Multiclass Classification (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.