Evolutionary algorithms — population-based search methods that mutate and recombine candidate solutions, keep the best, and repeat — have recently become startlingly fast by moving their entire loop, including fitness evaluation, into the memory of a single GPU. Libraries like evosax and QDax process billions of evaluations per hour this way, but only when the objective is a tidy numeric function that fits next to the population in video memory. Sequence alignment — scoring how many insertions, deletions, and substitutions separate two strings, the workhorse of genomics — is the opposite: exact scoring needs a quadratic dynamic-programming grid, and realistic tasks score each candidate against a reference corpus of gigabytes that cannot sit in GPU memory at all. So today we have two isolated fast worlds: evolutionary search that runs entirely on-chip over toy objectives, and alignment engines like Accelign and LOGAN that run exact dynamic programming at trillions of cell updates per second, but only as static batch jobs over fixed inputs.
This proposal builds the missing bridge and gives it a convergence story. The core claim is that we can run an accelerator-resident evolutionary loop whose fitness function is exact edit distance against a corpus held in host RAM, by tiering evaluation between cheap on-chip "scout" scores and exact wavefront kernels running on asynchronously prefetched corpus chunks, and — separately — that we can say something rigorous about where such a search converges, by optimizing in a continuous sequence-embedding space where the stationary-point machinery of Karimi et al. and the subsampling bounds of Foster et al. become applicable.
Core Claim
Concretely, consider the task family of corpus-constrained sequence design: find a sequence that minimizes an aggregate alignment objective over a large reference database — for example, minimizing the worst-case off-target alignment score of a short candidate against a whole genome, or finding a consensus motif closest in total edit distance to a family of reads. One candidate's fitness already requires thousands of exact alignments; a population of candidates multiplies that; the corpus itself cannot be resident in GPU memory. No existing system addresses this: evosax and QDax require the objective to be a tensorized function on-chip and break down otherwise — QDax's authors themselves note that external, non-tensorized evaluation reintroduces the CPU–GPU transfer stall. GMPEA tensorizes a constrained multi-objective evolutionary loop for a 62.6x CPU speedup, but only over continuous benchmarks. On the other side, Accelign and LOGAN align fixed read pairs and never iterate or search; Embed-Search-Align retrieves with embeddings but is a feed-forward pipeline, not an optimizer; and GEDEVO does run an evolutionary loop on an edit-distance objective, but purely on CPU with no acceleration, offloading, or convergence analysis. The intersection is genuinely empty.
The proposal has two coupled parts. The system part keeps the population, variation operators, and a cheap approximate scorer permanently in GPU memory. Each generation, the on-chip scout — a tensorized bitwise filter in the spirit of Shifted Hamming Distance and a low-dimensional sequence embedding in the spirit of Embed-Search-Align — produces two things at once: a ranking that lets weak candidates be discarded or down-weighted, and a prediction of which corpus chunks the surviving candidates will need for exact scoring. Those chunks are streamed across PCIe asynchronously while the GPU's wavefront kernel (an Accelign-style register-resident anti-diagonal implementation) finishes exact scoring of the previous generation — the same speculative-prefetch trick SpeCache uses to hide key–value cache transfers during language-model decoding, transplanted from token generation to population fitness. The theory part makes the tiering principled: writing the corpus objective as an expectation over reference entries,
$$F(z) = \mathbb{E}_{r \sim \text{corpus}}\left[d\big(g(z), r\big)\right],$$
where $z$ is a continuous embedding-vector genotype and $g(z)$ decodes it to a sequence, exact evaluation on a subsample $S$ gives an empirical objective $\hat F_S$ in exactly the empirical-risk sense of Foster et al., who prove that finding an $\epsilon$-stationary point of the empirical objective yields a near-stationary point of the population objective with optimal sample complexity $O(\epsilon^{-2})$ under gradient domination. Their machinery directly answers the design question the system poses: how few corpus entries per candidate does the scout's subsample need before its ranking is trustworthy?
Research Program
Workstream one builds the system. The population container, mutation and crossover over embedding genotypes, and the bitwise scout filter are implemented as pure tensor operations in the style of GMPEA, which showed that replacing conditional branches with vectorized masks is what buys near-constant runtime across population sizes. The exact evaluator is a wavefront dynamic-programming kernel following Accelign (register-resident anti-diagonals, three active diagonals of memory as in LOGAN). The corpus lives in pinned host RAM as fixed-size chunks with an embedding index in the style of Embed-Search-Align; the prefetcher issues asynchronous chunk streams for generation $t+1$ predicted from generation $t$'s scout scores, with a popularity cache for hot chunks as in Fiddler. The design question is the prefetch policy: scout-prediction-driven, popularity-driven, or hybrid, and how mispredictions (which SpeCache identifies as the main failure mode of lookahead) degrade the pipeline.
Workstream two develops the convergence analysis in three steps. First, establish empirically that the embedding genotype makes the landscape smooth enough to talk about gradients: evolution strategies estimate gradients by finite differences over noisy perturbations, as catalogued in evosax, and we track the norm of these estimated gradients along trajectories. Second, test whether the smoothed objective satisfies a Polyak–Łojasiewicz condition,
$$\tfrac{1}{2}\|\nabla F(z)\|^2 \;\ge\; \mu\,(F(z) - F^*),$$
which Karimi et al. show is the weakest standard condition guaranteeing linear convergence to a global optimum without convexity — every stationary point is then a global minimum. We cannot prove PL for an arbitrary corpus, and we will not claim to; the deliverable is a characterization of when it holds (locally, in embedding neighborhoods where geometric proximity tracks edit distance, which Embed-Search-Align demonstrates with over 99% recall) and what breaks it. Third, bound the surrogate gap: a stationary point of the scout objective or the subsampled objective is only useful if it is near-stationary for the true corpus objective, and the uniform-gradient-convergence framework of Foster et al. is precisely the tool for this — with the honest caveat, which they prove, that non-smoothness destroys dimension-free bounds, so our guarantees live on the smoothed embedding objective, not the raw discrete one.
Proposed Experiments
The corpora and reads come from the benchmarks already established in the literature: the E. coli and C. elegans long-read datasets used by LOGAN, the GIAB Ashkenazim Trio PacBio CCS reads used by Embed-Search-Align, UniRef50 protein sequences from the Accelign evaluation, and the 1000 Genomes ERR240726_1 reads from SHD. Two task families are run on each corpus: worst-case off-target score minimization, and minimum-total-edit-distance consensus design. Primary metrics are time-to-target-fitness and best fitness at fixed wall-clock budgets of 10 seconds and 60 seconds (echoing the strict 10-second limit under which GMPEA reports its results), plus system-level diagnostics: effective exact alignments per second, PCIe bytes moved per generation, fraction of transfers hidden behind compute, and prefetch misprediction rate. Scientific diagnostics are the Spearman correlation between scout score and exact fitness (per generation, per error regime) and the trajectory of the estimated gradient norm, which tells us whether the search is converging to a stationary point of the surrogate or still descending.
Baselines
The naive reference point is a CPU-only evolutionary loop with CPU-side exact alignment, in the mold of GEDEVO, which solved a graph edit-distance problem by evolutionary search entirely on CPU. It is the "do nothing" comparator: same task, same total number of exact alignments allowed, same tuning budget of algorithm settings, run on the same machine's host cores. Beating it means reaching equal or better final fitness in strictly less wall-clock; anything less is not worth the system's complexity.
The strongest competitor is a hybrid CPU–GPU evolutionary algorithm: population state, selection, and variation on the host, with fitness batches shipped to the GPU and scored by an Accelign-class wavefront kernel — the fastest exact pairwise alignment engine in the file, reporting up to 16.1 TCUPS (trillions of dynamic-programming cell updates per second) at 77% of theoretical peak on an RTX PRO 6000 Blackwell, and outperforming SeqAn, Parasail, EdLib, KSW2, WFA2, and CUDASW++4.0 on real Illumina, Nanopore, and UniRef50 datasets. We implement this baseline ourselves on the same GPU and corpus layout as our system, give it the identical evaluation budget (number of exact alignments) and the same tuning effort, and score both by fitness-per-wall-clock. This baseline matters because it is exactly the architecture the tensorized-EA literature says fails: GMPEA reports that GPU ports preserving host–device coordination achieved only 5x to 15x CPU speedups versus its 62.6x, and QDax attributes its 10x runtime reduction specifically to eliminating CPU–GPU transfers. If our prefetching system cannot beat this hybrid, the prefetch machinery is not paying for itself.
Two ablations isolate the key ingredients. The first removes the scout and prefetcher but keeps everything else: exact scoring of every candidate against synchronously fetched corpus chunks, entirely on GPU. The gap between this and the full system is the value of speculative prefetching alone. The second swaps the embedding genotype for a raw discrete sequence genotype with the same operators, isolating whether the continuous search space is what enables the convergence behavior — and, pragmatically, whether it hurts final fitness through decode bias.
Why not just…?
Why not just use static GPU alignment kernels like Accelign or LOGAN and skip the evolutionary machinery? For aligning a fixed set of reads, this is the right answer, and our proposal concedes that regime entirely. The argument only flips for design and search tasks, where the space of candidate sequences is combinatorially large and each candidate's fitness is itself a corpus-scale quadratic workload; LOGAN at 181.6 GCUPS and a 10.6x mapper speedup still assumes the inputs are given, not searched over, and both Accelign and LOGAN identify CPU–GPU data movement over the interconnect as a remaining bottleneck at corpus scale. Our experiments include a "generate-and-test everything" arm on the smallest task instance to measure exactly where brute-force batch alignment stops being viable.
Why not just keep the evolutionary algorithm on the CPU and ship fitness batches to the GPU? This is the hybrid baseline above, and it is a real threat rather than a strawman — it is simpler and reuses a proven kernel. The evidence against it is consistent across the file: hybrid host–device coordination caps GPU-ported evolutionary algorithms at 5x–15x speedups versus 62.6x for end-to-end tensorization (GMPEA), and QDax gets its 10x speedup precisely by removing transfers. But because our setting cannot be fully tensorized (the corpus will not fit on-chip), the head-to-head experiment against this baseline is the decisive test of the whole proposal, and we treat it as such rather than arguing around it.
Why not just pre-filter with a CPU-side SIMD filter like Shifted Hamming Distance? SHD discards 93% of junk mappings and processes 86 billion mappings in 40 minutes on a single CPU thread, so a host-side prefilter is cheap and will be included as a variant of the hybrid baseline. It falls short in two ways the file documents: its filtering power degrades badly above 15% sequence divergence, flooding downstream exact scoring with false positives exactly in the noisy long-read regime, and it is a binary rejector with no directional signal — it cannot rank or guide a search trajectory, whereas the embedding scout provides a continuous fitness estimate. The experiments measure scout–exact correlation across error regimes, which directly quantifies how much the embedding scout buys over the bitwise filter.
Why not just accept that edit distance is non-differentiable and drop the stationary-point analysis? The objection is correct for the raw discrete objective, and we do not claim gradients exist there. The response is that the search happens in a continuous embedding space where Embed-Search-Align shows geometric distance tracks edit distance, and evolution strategies supply finite-difference gradient estimates over arbitrary black boxes (evosax). What remains genuinely open — and is a real risk — is whether stationary points of the smoothed surrogate correspond to good points of the true objective; Foster et al. prove non-smoothness imposes dimension-dependent penalties, so our claims are conditional and empirical: we report the measured gap between surrogate-stationary and true-corpus fitness, not just surrogate convergence.
Decisive Checks
The proposal succeeds if, on at least two corpora, the full system reaches a target fitness strictly faster than both the CPU-only loop and the hybrid CPU–GPU baseline at matched evaluation budgets, and if the prefetcher hides the large majority of transfer time (measured as the fraction of PCIe bytes whose arrival overlaps active wavefront computation). It succeeds theoretically if the surrogate gap shrinks with subsample size at roughly the $O(\epsilon^{-2})$ rate Foster et al. establish, and if measured gradient-norm trajectories show convergence to approximate stationary points whose true-corpus fitness is within a stated tolerance of the best found by any method. It fails — and we would report this honestly — if the hybrid baseline matches the full system, which would mean speculative prefetching adds nothing over synchronous batching in this regime, or if scout–exact correlation collapses on noisy long reads, which would mean the embedding scout inherits the high-error breakdown of bitwise filters and the tiering is unsound exactly where it matters most.
References
- evosax: JAX-Based Evolution Strategies
- QDax: A Library for Quality-Diversity and Population-based Algorithms with Hardware Acceleration
- Accelign: a GPU-based Library for Accelerating Pairwise Sequence Alignment
- LOGAN: High-Performance GPU-Based X-Drop Long-Read Alignment
- Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
- Uniform Convergence of Gradients for Non-Convex Learning and Optimization
- Fully Tensorized GPU-accelerated Multi-population Evolutionary Algorithm for Constrained Multiobjective Optimization Problems
- Embed-Search-Align: DNA sequence alignment using Transformer models
- GEDEVO: An Evolutionary Graph Edit Distance Algorithm for Biological Network Alignment
- Shifted Hamming distance: a fast and accurate SIMD-friendly filter to accelerate alignment verification in read mapping
- SpeCache: Speculative Key-Value Caching for Efficient Generation of LLMs
- Fiddler: CPU-GPU Orchestration for Fast Inference of Mixture-of-Experts Models