NOTE-080: Evolution Strategies at the Hyperscale

Contribution

Removes the reason ES was impractical at LLM scale, which was never memory alone. Batched matrix multiplications against unstructured random perturbations have no data reuse, so accelerators run them far below peak. Giving every worker a rank-r perturbation makes the population’s forward pass an arithmetic-intensive operation, and the paper pairs that engineering move with a convergence theory saying what it costs — which turns out to be less than the geometry suggests.

Key insight

The rank constraint is per-worker, and the update is per-population. A single rank-one perturbation is a severe restriction on where a worker can look. But the ES update is an average over N workers, and an average of N rank-one matrices is generically rank min(N, m, n). So the search stays full-dimensional while each evaluation becomes cheap. The saving and the expressiveness live at different levels, and reading the rank constraint as a restriction on the optimizer is the mistake the paper exists to prevent.

Assumptions

• Assumption 1 — the entries of the two factor matrices A and B are i.i.d. from a zero-mean, symmetric, absolutely continuous distribution with finite fourth moments and variance σ². Symmetry is load-bearing: it is what produces the faster-than-parametric rate.
• The outer product is scaled by 1/√r so that the variance of the perturbation stays O(σ²) as r grows, rather than summing r terms.
• Assumption 2 — the fitness f is bounded.
• A technical device rather than an assumption: AB^T lives on a measure-zero manifold of rank-r matrices and has no density with respect to Lebesgue measure, so the analysis studies AB^T + δG with a small independent Gaussian G. That variable has a density for every δ > 0, and δ can be taken arbitrarily small, so the analysed update differs negligibly from the implemented one.
• The LLM experiments assume a recurrent (RWKV-7) architecture, where memory not spent on a KV cache funds population members. This is a property of the pairing, not of the method.

Key results

• Theorem 1 (low-rank ES gradient). Under Assumption 1 and for finite r, the low-rank objective’s gradient has a score-function form, with the perturbation generated by sampling the factors and taking the scaled outer product. Holds when: the factor entries satisfy Assumption 1.
• Theorem 2 (consistency with full-rank ES). Under Assumptions 1 and 2, the Frobenius-norm error between the low-rank update’s Gaussian score approximator and the true full-rank Gaussian ES gradient vanishes as dimension grows, at a rate faster than the O(1/√r) a general parametric CLT would give. The improvement comes from the symmetry in Assumption 1, via an Edgeworth expansion in which the first correction term cancels. Holds when: the fitness is bounded and the parameter dimension is large — it is a high-dimensional result, and the paper describes the mechanism as a linearising effect.
• Throughput. Auxiliary storage per layer falls from O(mn) to O(r(m+n)); the per-member forward cost falls correspondingly. A hundredfold increase in training speed for billion-parameter models at large population sizes, reaching up to 91% of pure batch-inference throughput.
• LLM post-training. RWKV-7 1.5B on Countdown: 35% validation accuracy against GRPO’s 23% at the same hardware and wall clock, with 1024 parallel generations per GPU against GRPO’s 32. RWKV-7 7B on GSM8K across 8 GPUs: EGGROLL ahead, with 8096 parallel generations against 256.
• A harder Countdown comparison. RWKV-7g7B reaches 72.9% against 52.8% reported for GRPO and 66.8% for OpenES — from a weaker base model than the Qwen2.5-7B those figures come from, which makes it striking and not like-for-like.
• Integer-datatype pretraining. Stable pretraining of nonlinear recurrent language models operating purely in integer datatypes — something backpropagation cannot do, and the strongest standalone argument in the paper for gradient-free optimization existing at all.
• Tabula rasa RL. No performance loss against full-rank ES despite being much faster.
• A negative result. Large population sizes are necessary for pretraining performance, which the authors read as evidence that zeroth-order methods are unsuitable for pretraining in general.

Claims

id	claim	strength	support
C1	Rank-r perturbations give a large throughput gain at billion scale	strong	direct measurement, up to 91% of batch-inference throughput
C2	The low-rank update converges to the full-rank ES update as dimension grows	strong	Theorem 2, with the rate and its mechanism identified
C3	The population update remains high-rank despite rank-r members	strong	it is an average of N rank-r matrices; structural, not empirical
C4	EGGROLL is competitive with GRPO for LLM reasoning post-training	moderate	two tasks, RWKV-7 only, both arms swept — the architecture is unusually favourable
C5	EGGROLL matches full-rank ES in tabula rasa RL	moderate	reported without loss; the comparison is the paper’s own
C6	Zeroth-order methods are unsuitable for pretraining	weak	an inference from needing large populations, not a measurement of the boundary
C7	The low-rank population field is the gradient of something	not claimed	and false in general — see LIT-232, which is the correction

Method

Each worker holds A ∈ R^{m×r} and B ∈ R^{n×r} drawn i.i.d., and perturbs a weight matrix by (1/√r)·AB^T. Workers are reconstructed from seeds rather than shipped, so the population shares base weights and the per-member forward passes batch. Fitnesses are centered per prompt, averaged over prompts, and standardized by their standard deviation; the reported implementation evaluates antithetic pairs +E and −E for each direction.

Concepts

• Arithmetic intensity — FLOPs per byte moved into fast memory. The quantity this paper optimizes, and the reason a memory-efficient method can still be slow.
• Low-rank perturbation — (1/√r)AB^T, replacing a dense Gaussian E of the same covariance.
• Linearising effect — the paper’s name for the high-dimensional regime in which the low-rank and full-rank fields agree.

Connections

The direct predecessor is Qiu et al.’s full-parameter ES at billion scale, and the paper’s criticism of it is specific: that line uses populations on the order of a hundred unique perturbations per update and collects hundreds of rollouts per perturbation to keep GPUs busy, whereas here every generation uses a different perturbation and the population per update is bounded by the inference batch size instead. It also distinguishes itself from the ES-over- LoRA and SVD-basis work by searching the full parameter space. Machine- readable lineage is on the LIT.

Recommendations

• R1 — If you are running ES on a model large enough for the forward pass to be matmul-bound, structure the perturbations as low-rank products. Topic: post-training. Status: experimental. Strength: strong. Applies when: billion-parameter models and large populations; the gain comes from arithmetic intensity, so it is smallest where the population is small.
• R2 — Size the population by the inference batch size rather than by what the perturbation memory allows, once perturbations are cheap to generate. Topic: post-training. Status: experimental. Strength: moderate.
• R3 — Do not expect zeroth-order methods to pretrain a large model. Topic: training. Status: experimental. Strength: weak — the paper infers rather than delimits this.

Bearing on the record

Filed as LIT-229, extends: LIT-211. It is the engineering half of the line SOTA-154 heads, and it is deliberately not in that practice’s source: — its LLM comparison is on a recurrent architecture and on its own variant, so it is evidence about the line rather than about the recommendation.

Its antithetic implementation is what SOTA-211 argues against, and LIT-232 is the paper that both corrects its theory and supplies the cheaper estimator. This note takes Theorem 2 at its stated result; the later paper’s analysis of what the finite-rank field actually is does not contradict it — Theorem 2 is asymptotic in dimension, and the correction is about finite rank at finite radius.

Limitations

The authors state the LLM evidence is on RWKV-7 and frame the architecture’s suitability as an advantage rather than a caveat; this reading treats it as both. Two further limits from this reading: the analysis is asymptotic in parameter dimension and says nothing about the finite-rank field at a fixed radius, which is the gap LIT-232 walks into; and the technical device of adding δG to obtain a density is clean but means the object analysed is not literally the object implemented.

Open questions

• Does the throughput advantage survive on transformers? The KV-cache argument is why RWKV is favourable. What would close it: the same Countdown and GSM8K comparison on a transformer of matched capability.
• Where is the population-size floor for pretraining? The paper asserts unsuitability from needing large populations. What would close it: a measured curve of pretraining loss against population size.
• Is rank a useful knob at all? Unaddressed here and answered elsewhere — LIT-232 finds no reproducible reward advantage for rank eight over rank one.