Galop: Billion-Scale Genetic Programming on a Single GPU

Xavier Hill Roy, Stephen KellyarXiv 2026 · arXiv

TL;DR

Galop is a new hybrid CPU-GPU system that shatters population scale records in Genetic Programming (GP), evolving over 2.15 billion individuals on a single NVIDIA H100 GPU. By mapping one program to a CUDA warp, it achieves massive throughput and speedups of up to 13.6× over existing high-performance systems, making "billion-scale" evolution a practical reality for researchers.

What Problem Does This Paper Address?

Genetic Programming (GP) is a technique that evolves populations of computer programs to solve tasks. Historically, researchers have been limited by "small" populations (thousands or millions) because evaluating programs is computationally expensive.

While GPUs offer massive parallel power, they are designed for SIMT (Single Instruction, Multiple Threads) execution—meaning they perform best when many threads do the exact same thing. GP, however, evolves a "zoo" of heterogeneous programs. If you try to run different programs on adjacent GPU threads, you hit "warp divergence," where the hardware effectively stalls as it waits for different instructions to finish.

The authors of Galop tackle this mismatch to answer a fundamental question: How can we efficiently use GPU hardware to scale GP populations into the billions?

Methods

Galop utilizes a Linear GP (LGP) representation, where programs are sequences of instructions (like assembly code) rather than the traditional tree structures. The core innovation is its warp-per-individual mapping:

  • The Mapping: Instead of assigning one program to one thread (too much divergence) or one program to the entire GPU (not enough population parallelism), Galop assigns one program to each CUDA warp (a group of 32 threads).
  • Data Parallelism: All 32 threads in the warp execute the same program simultaneously, but each thread handles a different fitness case (data point). This perfectly aligns with the GPU's SIMT architecture.
  • Hybrid Architecture: Galop keeps selection and variation (crossover/mutation) on the CPU for flexibility while offloading the heavy lifting of fitness evaluation to the GPU.
  • Optimization: To maximize memory efficiency, Galop uses "instruction packing" and optional "intron removal" (deleting code that doesn't affect the output) before transferring programs to the GPU.
The Execution Granularity Iceberg illustrates the trade-off between concurrently active individuals and the parallel work needed for utilization.

Datasets

The authors evaluated Galop using symbolic regression, a task where the system tries to find a mathematical formula that fits a set of data points. They used:

  • Nguyen 1–6: Standard synthetic benchmarks involving polynomials and trigonometric functions.
  • Feynman I.9.18: A physics-inspired problem based on Newtonian gravitation.
  • California Housing: A real-world dataset with over 20,000 observations, used to test the system on complex, noisy data.

Key Insights and Ideas

  • The Granularity Sweet Spot: The "warp-per-individual" approach is a "Goldilocks" solution. It provides enough population-level parallelism to fill a modern GPU while maintaining enough data-level parallelism to keep the hardware efficient.
  • The Bottleneck Shift: As population sizes reach the billions, the GPU becomes so fast at evaluation that the "surrounding" evolutionary pipeline (CPU-side selection, variation, and even program initialization) becomes the primary bottleneck.
  • Memory vs. Compute: At this scale, the limit isn't how fast the GPU can "think," but how many programs can fit in VRAM. Galop’s use of compact LGP and intron removal is critical for hitting the 2-billion mark.
Fig. 2. Galop’s warp-per-individual mapping. Each CUDA warp evaluates one individual, with its 32 threads executing the same program over different fitness cases. Each block contains W warps, giving B = ⌈P/W⌉blocks (B) for a population of P individuals.

Key Results

  • Unprecedented Scale: Galop successfully evolved 2.15 billion individuals for 100 generations on a single H100 GPU. This is roughly 4× larger than the previous record for a single-GPU system.
  • Massive Speedups: In head-to-head timing against EvoGP (a state-of-the-art tree-based GPU system), Galop was faster in 27 out of 28 test configurations, achieving speedups of up to 13.6×.
  • Efficiency: A full 100-generation run with 2.15 billion individuals took a median of only 2.23 hours.
  • Solution Quality: While EvoGP generally produced higher-quality solutions (likely due to the inherent differences between tree-based and linear GP), Galop remained competitive and even outperformed EvoGP on certain problems like Nguyen 4.

Limitations and Future Work

  • CPU Bottlenecks: The authors noted that at extreme scales, the serial nature of program initialization on the CPU is a major drag. Future versions could move initialization and selection entirely onto the GPU.
  • Fixed Hyperparameters: The study focused on computational scaling rather than optimizing search. The authors used fixed mutation and crossover rates; tuning these could potentially close the solution quality gap with tree-based systems.
  • Beyond Regression: The current implementation is tailored for symbolic regression. The authors plan to extend Galop to agent-based workloads (like reinforcement learning), where sequential state transitions make parallelism even more challenging.

Summary updated

Abstract

Genetic programming (GP) evolves populations of heterogeneous programs, whereas GPUs achieve their highest throughput when groups of threads execute the same instructions. To better align GP evaluation with GPU execution, we present Galop, a hybrid CPU-GPU linear GP system that assigns one individual to each CUDA warp, a group of 32 threads that execute the same instructions across different fitness cases. We compare Galop against EvoGP, a recent high-performance GPU-based tree GP system, on data-rich symbolic regression across two unique GPUs, varying population size and fitness-case count. Galop completes evolutionary runs faster than EvoGP in 27 of the 28 main comparisons, with speedups of up to 13.6 times. Solution quality comparisons favour EvoGP overall, although Galop remains competitive on several problems. Galop also completes a full generation with 2.15 billion individuals on a single H100 GPU, approximately 4.0 times the largest population achieved by any other tested GP system. All five runs at this population complete 100 generations, with a median wall-clock time of 2.23 hours. These results make it practical to study GP populations in the billions on a single GPU. Galop's source code, experimental data, and reproducibility scripts are publicly available at https://github.com/xavierhillroy/Galop.
BibTeX
@misc{roy2026galop,
  author = {Xavier Hill Roy and Stephen Kelly},
  title = {{Galop: Billion-Scale Genetic Programming on a Single GPU}},
  year = {2026},
  eprint = {2611.14665},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.14665},
}
Figure