💻 computer science

Beyond the Best Guess: Improving LLM Solution Coverage with Evolution Strategies

This paper demonstrates that Evolution Strategies (ES) outperform Reinforcement Learning (RL) in post-training Large Language Models for discovery domains by maintaining broader solution coverage and higher pass@k scores, thereby avoiding the output distribution collapse that limits RL's effectiveness in generating diverse candidate solutions.

Original authors: Conor F. Hayes, Elliot Meyerson, Kajetan Schweighofer, Roberto Dailey, Babak Hodjat, Risto Miikkulainen, Xin Qiu

Published 2026-08-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Conor F. Hayes, Elliot Meyerson, Kajetan Schweighofer, Roberto Dailey, Babak Hodjat, Risto Miikkulainen, Xin Qiu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find a hidden treasure on a vast, foggy island. In the world of Artificial Intelligence, Large Language Models (LLMs) are like incredibly smart explorers who can read maps and guess where the treasure might be. For a long time, the best way to train these explorers was to show them a problem, let them guess, and then reward them only if their single best guess was perfect. This method, known as Reinforcement Learning (RL), is like a strict coach who yells "Wrong!" at every wrong guess and "Perfect!" at the one right answer. The problem is, this coach gets so obsessed with finding that one perfect answer that the explorer stops looking anywhere else. They stop exploring the foggy edges of the island where other treasures might be hiding, focusing only on the one spot they think is right.

But what if the treasure isn't just one thing? What if there are many different ways to solve a math problem or discover a new scientific fact? In these "discovery" domains, it's not enough to have one perfect guess; you need a wide net to catch any correct solution. This is where a new idea called "test-time scaling" comes in. Instead of just asking the model for one answer, we ask it to generate dozens or even hundreds of different attempts and see if any of them are right. The paper you are about to read investigates whether our strict coach (RL) or a different kind of training method is better at helping the explorer cast a wide net. The researchers found that while the strict coach makes the explorer very confident in one spot, a different method called Evolution Strategies (ES) keeps the explorer curious and wandering, ensuring that if a solution exists anywhere in the fog, the explorer is much more likely to find it.

The Paper: Beyond the Best Guess

This paper tackles a tricky problem in training AI: how do we make sure an AI model doesn't just get really good at guessing the one right answer, but actually keeps its options open to find any right answer? The authors, researchers from Cognizant AI Lab and the University of Texas at Austin, compared two training methods: the standard Reinforcement Learning (RL) and a newer approach called Evolution Strategies (ES).

Think of Reinforcement Learning like a student cramming for a test by memorizing the exact answer key. If the student gets a question right, they get a treat; if they get it wrong, they get nothing. Over time, the student becomes a master at that specific question but stops trying to understand the underlying concepts. In the AI world, this causes something called "distribution collapse." The model becomes so focused on its "best guess" that it stops generating diverse answers. It's like a musician who only plays one note because it's the only one that gets applause, forgetting how to play a whole song.

Evolution Strategies (ES), on the other hand, works more like a natural ecosystem. Instead of training one single model, ES creates a whole "population" of slightly different versions of the model. It tweaks their "brains" (weights) randomly, like nature mutating genes, and sees which versions perform best. Crucially, it doesn't just pick the single winner and discard the rest; it learns from the whole group. This keeps the AI's "brain" flexible and diverse, allowing it to explore many different paths to a solution.

The researchers tested these methods on math problems, ranging from simple arithmetic to complex Olympiad-level challenges, using models of different sizes (from 1.5 billion to 32 billion parameters). They measured success using a metric called pass@k. Imagine asking the AI to generate 100 different answers to a problem. Pass@1 asks, "Is the very first answer correct?" Pass@k asks, "Is at least one of the 100 answers correct?"

Here is what they found:

1. The "Best Guess" Trap
When the researchers looked at pass@1 (the single best guess), the RL-trained models were often very good. They were sharp and confident. However, as the researchers increased the number of guesses (k) to 2, 8, 16, or even 128, the RL models hit a wall. Their performance stopped improving. In fact, for some difficult problems, the RL models became worse than the original, untrained model when given many chances to guess. The RL model had become so narrow in its thinking that it stopped finding correct answers that were slightly different from its "favorite" one.

2. The Power of Diversity
In contrast, the ES-trained models showed a different pattern. While they were also good at getting the first guess right, their real superpower showed up as the number of guesses increased. As the researchers asked for more and more samples (up to 128), the ES models kept finding new, correct solutions. The paper shows that ES consistently achieved higher pass@k scores than RL across all the model sizes and math benchmarks they tested.

3. Why It Happens
The authors dug into why this happened. They found that RL training tends to "prune" the AI's knowledge. It deletes the paths that lead to correct but less common answers, effectively making some problems impossible to solve even if the AI tries 100 times. The ES method, however, preserves the "broadness" of the AI's knowledge. It doesn't just learn the right answer; it learns to keep many doors open. When the researchers looked at the AI's "entropy" (a measure of how diverse its answers are), they saw that when RL models failed, they were confidently wrong (low diversity). When ES models failed, they were still diverse and uncertain, which means they were still exploring and had a better chance of finding the right answer if given more time or compute.

4. The Real-World Impact
The paper suggests that for problems where we need to discover new things—like solving a hard math proof, writing code, or finding a new scientific fact—having a model that can generate a wide variety of correct solutions is more valuable than having a model that is just really good at one specific guess. By using ES, we can get better results in these discovery domains because the model is less likely to get stuck in a "local trap" and more likely to find the global solution.

In short, the paper argues that if you want an AI to be a great explorer in the unknown, you shouldn't just train it to be the best guesser of the day. You should train it to keep its options open, wander a bit, and be ready to find the treasure no matter where it's hiding. Evolution Strategies, it turns out, is the better coach for that kind of adventure.

Technical Summary: Beyond the Best Guess: Improving LLM Solution Coverage with Evolution Strategies

Problem Statement

Large Language Models (LLMs) are increasingly deployed in discovery domains such as mathematics and science, where the goal is not merely to provide a single "best guess" but to explore a solution space to find correct answers among many candidates. The standard paradigm for improving LLM reasoning involves post-training with Reinforcement Learning (RL), specifically Reinforcement Learning with Verifiable Rewards (RLVR). While RLVR effectively maximizes single-sample accuracy (pass@1), this paper identifies a critical limitation: distribution collapse.

RL updates, typically via policy gradient methods like PPO or GRPO, sharpen the model's output distribution to concentrate probability mass on high-reward outputs. This process narrows the support of the distribution, effectively pruning low-probability but correct solutions. Consequently, as the number of samples ( $k$ ) increases during test-time scaling (TTS), the solution coverage (pass@k) of RL-trained models often plateaus or even degrades, sometimes falling below the performance of the untrained base model. This phenomenon limits the efficacy of TTS strategies like sampling multiple candidates, which rely on a broad distribution of viable solutions.

Methodology

The paper proposes Evolution Strategies (ES) as a gradient-free, population-based alternative to RL for post-training LLMs. Unlike RL, which operates in action space by updating a single model's parameters based on token-level gradients, ES operates directly in weight space.

The ES Approach:

Population Generation: A population of models is generated by applying random Gaussian perturbations ( $\epsilon$ ) to the base model's weights ( $\theta$ ).
Evaluation: Each perturbed model is evaluated on a task, and a reward is assigned based on performance (e.g., correctness of the answer).
Weight Update: The weights are updated by aggregating the perturbations weighted by their normalized rewards, effectively moving the parameters toward regions of weight space that are robust to perturbations and encompass a broader set of solutions.

Experimental Setup:
The study empirically compares ES against state-of-the-art RL (specifically GRPO and OatZero) across multiple model families and scales (1.5B to 32B parameters).

Datasets: Training and evaluation were conducted on GSM8K, MATH (levels 3-5), MATH500, Olympiad Bench, and Minerva.
Metrics: The primary metric is pass@k, defined as the probability that at least one correct solution exists within $k$ samples. The study also analyzes accuracy distributions, model progressions/regressions, and answer entropy.
Test-Time Scaling: The paper evaluates performance as $k$ increases (up to 128 or 256 samples) and applies Self-Consistency (voting) as a downstream TTS method.

Key Contributions

Comprehensive Evaluation: The paper provides the most extensive evaluation of ES as an LLM post-training technique to date, spanning model sizes from 1.5B to 32B and multiple model families (Qwen2.5, Qwen3).
Superiority in Solution Diversity: It establishes that ES consistently improves pass@k over RL-trained models across all scales and benchmarks. Unlike RL, ES does not suffer from distribution collapse.
Mechanistic Analysis: Through systematic analysis, the paper identifies the origins of ES's success:
- Progressions vs. Regressions: ES adds new correct solutions (progressions) while preserving existing knowledge (minimizing regressions), whereas RL often overwrites base model knowledge to maximize reward.
- Entropy Preservation: In failure modes, ES maintains higher answer entropy (uncertainty), whereas RL collapses to low-entropy, confidently incorrect answers.
Downstream Validation: The paper demonstrates that the high-quality output distributions of ES lead to superior performance in Self-Consistency voting, a non-verifiable TTS method.

Results

Pass@k Performance: Across all benchmarks (GSM8K, MATH500, Olympiad Bench, Minerva) and model sizes, ES models consistently outperform RL models as $k$ increases. While RL curves often plateau early, ES curves continue to rise. Notably, for sufficiently large $k$ , the base model often outperforms the RL-fine-tuned model, but the ES-fine-tuned model consistently outperforms the base model.
Distribution Analysis:
- Accuracy Bins: RL increases the frequency of prompts where no solution is found (bin 0.0) relative to the base model, indicating a loss of solvability. ES reduces this frequency.
- Regressions: RL exhibits significantly higher rates of "regressions" (problems the base model solved but the fine-tuned model failed to solve) compared to ES. For example, on the Olympiad Bench, RL had 49 regressions versus 15 for ES.
- Entropy: When models fail, RL fails with low entropy (confidently wrong), while ES fails with higher entropy (preserving diversity), making ES failures more amenable to correction via increased sampling.
Self-Consistency: In voting scenarios, ES-generated distributions yield higher accuracy than both RL and the base model as the number of samples increases.

Significance and Claims

The paper argues that Evolution Strategies provide a better foundation for post-training in discovery problems where diverse solution coverage is critical. While RL is effective for maximizing single-shot accuracy (pass@1), it fundamentally conflicts with the requirements of test-time scaling (TTS) by collapsing the solution space.

The authors claim that ES resolves this tension by optimizing for a robust solution distribution rather than a single high-reward mode. By preserving the broad support of the base model's output distribution while simultaneously improving pass@1, ES enables LLMs to effectively leverage increased test-time compute. The paper concludes that ES is the state-of-the-art approach for post-training in domains like science, math, and coding, particularly where the ability to explore alternative viable solutions is essential for performance.