Duel-Evolve: Reward-Free Test-Time Scaling via LLM Self-Preferences

AI summary

Overview

Research area: Test-time scaling and search for large language model outputs, sitting at the intersection of evolutionary optimization over discrete spaces, preference-based (dueling) bandits, and Bayesian ranking models.

Technical level: Advanced. The paper assumes familiarity with Bradley–Terry models, Laplace approximations, Thompson sampling, and dueling-bandits formulations, though the core idea can be understood without that background.

Scope: The paper introduces Duel-Evolve, an evolutionary test-time optimizer that replaces external scalar reward models with pairwise preferences elicited from the same LLM that generates candidate solutions, and evaluates it on mathematical reasoning (MathBench) and code generation (LiveCodeBench).

What This Paper Is About

Many methods improve LLM outputs at test time by proposing candidates, scoring them with a calibrated scalar evaluator, and refining the best ones. For many tasks, however, such scalar scores are unavailable, too sparse, or unreliable. Duel-Evolve's goal is to run the same propose–evaluate–refine loop using only pairwise comparisons that the LLM itself produces, with no reward model, no ground-truth labels during search, and no hand-crafted scoring function.

Key Contributions

1. Preference-only optimization signal. The paper replaces external scalar rewards with pairwise preferences elicited from the same LLM used to generate candidates, proposing that comparisons are easier to elicit and more stable than numeric self-ratings, which the paper describes as poorly calibrated and mutually inconsistent.

2. A Bayesian aggregation layer. Noisy, local candidate comparisons are pooled into a global quality estimate using a Bayesian Bradley–Terry model, fit with a MAP estimate plus a Laplace approximation to yield per-candidate posterior means and variances.

3. Budget-aware comparison allocation. The method adapts Double Thompson Sampling to a combinatorially large, growing candidate pool, directing comparisons toward candidates that remain plausible optima, with a confidence-based survivor set to prune confidently suboptimal candidates.

4. An evolutionary loop that couples inference and generation. Posterior means and uncertainties are fed back into the LLM generator as scored parents, so the generator conditions on quality estimates rather than on external rewards; the algorithm is reported to need no reward model, labels, or task-specific scorer.

Main Findings

• MathBench accuracy: Duel-Evolve reaches 94.0% accuracy, the highest in the comparison. The abstract and introduction describe the gain as 20 percentage points over existing methods and baselines; the results section states it exceeds the strongest baseline by 22 percentage points. Baselines listed: Zero-shot CoT 57.3%, Few-shot CoT (k=8) 64.0%, Self-consistency 62.7%, Best-of-N 65.3%, GEPA 51.3%, Feedback Descent 72.0%.

• LiveCodeBench accuracy: Duel-Evolve attains 37.4% (reported as 37% in the abstract), exceeding Feedback Descent (24.2%) and GEPA (25.3%) by over 12 percentage points. Other baselines: Zero-shot CoT 13.1%, Few-shot CoT (k=3) 16.2%, Self-consistency 20.2%, Best-of-N 31.3%.

• Fast early convergence on MathBench: Accuracy rises from 57% to 90% within the first 10 generations, then improves more slowly to 94% by generation 64 (figure reported over 150 generations). Roughly 90% of total improvement occurs within the first 10 generations.

• Difficulty-stratified MathBench behavior: Middle-difficulty problems are solved fastest, reaching 96% by generation 6 and 98% at convergence; High and College problems converge more slowly, both reaching 92%.

• LiveCodeBench convergence: Duel-Evolve surpasses other iterative baselines by the fifth generation, with steady gains on Easy and Medium problems, out of 200 generations.

• Best-of-N is a strong baseline on code: Best-of-N performs competitively on LiveCodeBench, which the authors suggest reflects the higher generation temperature leading to more exploration and explaining why it does relatively better there than on MathBench.

• GEPA's mixed behavior: GEPA underperformed on MathBench (51.3%) and the authors attribute this to prompts overfitting the validation set, where the best prompt achieved 67% accuracy. On LiveCodeBench, GEPA outperformed the sampling baselines except Best-of-N and exceeded Feedback Descent's final accuracy, but was limited to 125 iterations because of substantially higher wall-clock cost.

• Ablation-style diagnostic on preference selection: Best-of-N, which uses the same pairwise preference mechanism as Duel-Evolve but no evolutionary loop, performs usefully, indicating the preference-based selection procedure provides meaningful signal on its own.

Methodology in Plain English

Duel-Evolve treats the search for a good LLM output as a dueling-bandits problem. It keeps a growing pool of candidate answers. Each round, it does three things.

First, it updates a statistical model of candidate quality. Every candidate gets a latent utility score. Past duels (candidate A versus candidate B) are modeled with a Bradley–Terry likelihood, which says the chance A beats B depends on the difference in their utilities passed through a logistic function. The model places a Gaussian prior on utilities and is fit by maximizing the penalized likelihood, with an L-BFGS solver; a Laplace approximation with a diagonal Hessian then gives each candidate an estimated mean and uncertainty.

Second, it evaluates. Rather than comparing random pairs, it samples utilities from the posterior ("virtual" scores), pairs the top-ranked candidates, and asks the LLM judge to pick a winner. Judging is order-consistent: each pair is judged twice with the presentation order swapped, and only concordant outcomes are kept as decisive comparisons; disagreements are dropped as non-informative.

Third, it evolves. It selects a small set of high-scoring parents, mixing Thompson-sampled top scorers with recent, still-uncertain candidates, and prompts the generator LLM with those parents and their estimated scores to propose new candidates. A survivor set prunes candidates whose upper confidence bound falls below the best lower confidence bound, while the pruned candidates remain in the pool so their comparison data still informs the model. Judge queries and generation calls within each phase run in parallel, so wall-clock cost per generation is dominated by a single round of LLM inference rather than by the number of comparisons or children.

Implementation specifics reported: MathBench uses Gemma-3-4b-it, batches of 12 candidates per generation, 6 scored parents, and temperature 0.7; LiveCodeBench uses Gemma-3-27b-it (4-bit quantized), batches of 40 candidates, 5 scored parents, temperature 1.2, AST-based de-duplication, and an "evolving memory" scratchpad capped at 500 characters. The population is capped at 200 solutions.

Why This Matters

Impact on research. The paper argues that pairwise self-preferences are a viable substitute for scalar reward models in test-time optimization, placing the method in the quadrant of test-time scaling approaches that need no external reward yet keep improving as compute increases. It also distinguishes itself from concurrent work: Feedback Descent performs single-trajectory hill-climbing against one incumbent with no global quality model, and Prompt Duel Optimizer targets dataset-level prompt selection with independent Beta posteriors and a Copeland-style objective rather than a global Bradley–Terry posterior.

Real-world applications (as suggested by the paper's framing of discrete structured spaces and open-ended generation):

• Competitive programming assistance, where solutions can be iteratively refined using public tests as coarse feedback (and where the paper reports hidden-test success rates).
• Mathematical problem solving and tutoring systems, where only final correctness is available as a signal.
• Prompt and response optimization pipelines where designing a reliable scalar evaluator is expensive or impossible.
• Open-ended generation domains such as summarization, dialogue, and creative writing, which the paper names as areas where quality criteria are subjective and judge bias could be amplified.

Industry relevance. Removing the need for a calibrated reward model or task-specific scoring function reduces the engineering cost of deploying test-time search, and the paper reports that within-phase judge and generation calls are parallelized so per-generation wall-clock cost is dominated by a single LLM inference round. At the same time, the paper notes that all iterative methods incur additional inference cost relative to k-shot baselines.

Future Directions

• Mitigating judge bias. Because the optimization signal comes entirely from the model's own preferences, the method will amplify rather than correct systematic biases, such as preferring confident-sounding answers over correct ones. The authors propose ensembling models or calibrating against labeled subsets.
• Extending to open-ended domains. The paper identifies summarization, dialogue, and creative generation as settings where subjective quality criteria could expose bias amplification, leaving validation there as open work.
• Using stronger models as subroutines. The paper suggests reasoning models and single-generation refinement techniques could serve as a stronger judge or generator inside the Duel-Evolve loop.
• Reducing the cost of comparison-based iterative methods. GEPA's substantially higher wall-clock cost on LiveCodeBench forced the authors to cap it at 125 iterations and extrapolate, pointing to throughput as a practical constraint for iterative test-time methods.

Target Audience

Researchers and practitioners working on test-time compute scaling, preference-based learning, and LLM self-improvement will get the most from this paper. It is also relevant to engineers building LLM pipelines for math reasoning, code generation, or prompt optimization who lack a reliable scalar evaluator, and to readers interested in dueling-bandits and Bayesian ranking methods applied beyond fixed, finite arm sets. The Bayesian machinery and bandit formulation mean the paper is best suited to readers with some background in probabilistic modeling or online learning.

Authors’ abstract

Many applications seek to optimize LLM outputs at test time by iteratively proposing, scoring, and refining candidates over a discrete output space. Existing methods use a calibrated scalar evaluator for the target objective to guide search, but for many tasks such scores are unavailable, too sparse, or unreliable. Pairwise comparisons, by contrast, are often easier to elicit, still provide useful signal on improvement directions, and can be obtained from the LLM itself without external supervision. Building on this observation, we introduce Duel-Evolve, an evolutionary optimization algorithm that replaces external scalar rewards with pairwise preferences elicited from the same LLM used to generate candidates. Duel-Evolve aggregates these noisy candidate comparisons via a Bayesian Bradley-Terry model, yielding uncertainty-aware estimates of candidate quality. These quality estimates guide allocation of the comparison budget toward plausible optima using Double Thompson Sampling, as well as selection of high-quality parents to generate improved candidates. We evaluate Duel-Evolve on MathBench, where it achieves 20 percentage points higher accuracy over existing methods and baselines, and on LiveCodeBench, where it improves over comparable iterative methods by over 12 percentage points. Notably, the method requires no reward model, no ground-truth labels during search, and no hand-crafted scoring function. Results show that pairwise self-preferences provide strong optimization signal for test-time improvement over large, discrete output spaces.