[arXiv 2025] EGGROLL: Scaling Evolution Strategies to the Billion-Parameter Frontier

TL;DR

Evolution Strategies (ES) have long been the "black sheep" of deep learning—theoretically elegant for non-differentiable objectives but practically too slow for modern GPUs. EGGROLL changes this by refactorizing perturbations into low-rank matrices. By increasing arithmetic intensity, EGGROLL allows ES to train billion-parameter models at speeds nearly equal to pure inference, even enabling the pretraining of pure integer-only (int8) neural networks.

The Bottleneck: Why ES Failed to Scale

The central challenge of Evolution Strategies on GPUs isn't just the memory footprint of the population; it's arithmetic intensity. In standard backpropagation, we benefit from highly optimized GEMM (General Matrix Multiply) operations. In naïve ES, adding unstructured noise to a weight matrix $M$ for $N$ population members creates $N$ different matrices. Calculating $u(M+\sigma E_i{)}^T$ for a batch of inputs $u$ results in a series of matrix-vector products that are memory-bound, not compute-bound.

As models hit the billion-parameter mark, the ratio of operations to memory traffic (arithmetic intensity) drops so low that the GPU spends all its time moving data rather than calculating gradients.

Methodology: The Low-Rank Insight

The authors introduce EGGROLL (Evolution Guided GeneRal Optimisation via Low-rank Learning). Instead of sampling a full-rank noise matrix $E\in {\mathbb{R}}^{mimesn}$, they sample two low-rank matrices $A\in {\mathbb{R}}^{mimesr}$ and $B\in {\mathbb{R}}^{nimesr}$ and define the perturbation as: $E=\frac{1}{\sqrt{r}}A{B}^{o}p$

1. Hardware-Efficient Forward Pass

This decomposition allows the forward pass for a layer to be rewritten: $u(M+\sigma E_i{)}^{o}p=u{M}^{o}p+\frac{\sigma }{\sqrt{r}}(u{B}_i)A_i^{o}p$ The term $u{M}^{o}p$ is a standard, efficient matrix multiply shared across the whole population. The second term is a cheap, low-rank update. This allows EGGROLL to saturate GPU compute even with millions of unique perturbations.

Figure 1: Comparison of hardware-efficient low-rank perturbations vs. naïve full-rank ES.

2. Full-Rank Updates from Low-Rank Noise

A common misconception might be that EGGROLL restricts the model's learning to a low-rank subspace (like LoRA). However, because the final parameter update is a weighted sum of $N$ different low-rank matrices, the resulting update is rank $\min (Nr,m,n)$. With large population sizes ($N>10^6$), the updates remain effectively full-rank.

Theoretical Rigor: Linearization in High Dimensions

The paper provides a profound theoretical analysis of why ES works in high-dimensional spaces. They prove a "Linearization Theorem": as the parameter dimension $d\to \infty$, the Gaussian ES update converges to the first-order derivative $ablaf(\mu )$, provided the noise scales at a critical rate of ${\sigma }_d=o(d^{-1/2})$.

This bridges the gap between zeroth-order "black-box" optimization and the Neural Tangent Kernel (NTK) regime of standard deep learning, explaining why EGGROLL can pretrain models despite only seeing scalar rewards.

Experimental Breakthroughs

1. The Integer-Only Language Model (EGG)

Perhaps the most radical result is the EGG architecture. Since ES doesn't require backpropagation, we don't need differentiable activation functions or high-precision floats. The authors trained a nonlinear RNN using pure int8 datatypes (no explicit activations, relying on integer clipping).

• Result: The EGG model pretrained with EGGROLL achieved 3.40 bits/byte, actually outperforming a float32 Transformer trained with SGD on the same data.

2. LLM Reasoning & Fine-tuning

EGGROLL was tested on fine-tuning RWKV-7 and Qwen models for reasoning (GSM8K, AIME).

• Performance: In the "Countdown" task, EGGROLL reached 35% accuracy compared to 23% for GRPO (a popular RL alignment method) given the same wall-clock time.
• Pass@K Optimization: Because EGGROLL is a black-box optimizer, it can directly maximize pass@k—a non-differentiable metric that standard RL often struggles to optimize directly.

Figure 2: Throughput and test loss for the EGG integer-only model across population sizes.

Critical Analysis & Outlook

Strengths:

• Hardware Alignment: It turns a memory-bound problem into a compute-bound one.
• Flexibility: Opens the door for non-differentiable neurosymbolic systems and hardware-native (bit-level) training.

Limitations:

• Compute Cost: While throughput is high, ES typically requires significantly more total FLOPS/samples than backprop to reach the same loss in standard supervised settings (though it excels where gradients are noisy or unavailable).
• Hyperparameter Sensitivity: The noise scale $\sigma$ remains a critical hyperparameter that requires careful tuning as the model scales.

Takeaway

EGGROLL is a "hyperscale" reset for Evolution Strategies. By making ES as fast as inference, the authors have provided a viable pathway to train the next generation of non-differentiable and low-precision AI models.