PACEvolve++: Improving Test-time Learning for Evolutionary Search Agents

Technical Summary of PACEvolve++: Improving Test-time Learning for Evolutionary Search Agents

Problem Statement
Large Language Models (LLMs) have emerged as effective drivers for evolutionary search, enabling autonomous discovery in open-ended optimization problems. However, existing systems typically rely on a fixed, prompt-elicited reasoning policy to sample next candidates. While useful search experience may accumulate in the system's context (scaffold), it is not internalized into the model's decision preferences. This limitation is particularly consequential in practical engineering and research tasks (e.g., MoE load balancing, protein fitness extrapolation) where evaluations are expensive and progress depends on recognizing patterns across previous attempts. A fixed policy can condition on history via context but fails to adapt its decision strategy to prioritize directions that are novel, feasible, and likely to improve the evolving frontier. Furthermore, end-to-end training of a single model for both strategic decision-making and code implementation often entangles hypothesis quality with implementation correctness, creating noisy signals for adaptation.

Methodology
The authors introduce PACEvolve++, an advisor-model reinforcement learning (RL) framework designed for test-time policy adaptation in evolutionary search agents. The methodology is built on two core pillars:

1. Advisor-Model Decomposition:
   The framework decouples strategic search decisions from code implementation.

   • The Advisor: A trainable, smaller model responsible for high-level strategic reasoning, including hypothesis generation, novelty assessment, and mutation selection.
   • The Frontier Model: A stronger, frozen model (e.g., Gemini) responsible for translating the advisor's selected hypotheses into executable code.
     This separation allows the system to learn task-specific search priors without being hindered by the implementation failures of complex codebases, which often plague end-to-end training.

2. Phase-Adaptive Reinforcement Learning:
   Recognizing that the nature of feedback changes as an evolutionary search progresses, PACEvolve++ employs a dynamic credit assignment strategy that adapts to the search phase:

   • Exploration Phase (Early): When candidates differ substantially in mechanism and quality, the system uses group-relative feedback (similar to GRPO). This provides dense, informative signals to learn broad search preferences and identify promising mutation families without premature convergence.
   • Refinement Phase (Late): As the search converges and reward gaps compress (candidates become near-neighbor variants of strong parents), group-relative signals become ineffective and can cause optimization instability. The system shifts to a frontier-contribution signal based on Pass@k Policy Optimization (PKPO). Specifically, it uses a low-variance SLOO (Leave-One-Out) estimator to credit candidates based on whether they change the "best-of-k" frontier. This aligns the training objective with the log-diminishing reward structure of long-horizon evolutionary search.

   The final advantage is a linear mixture of these two signals, where the weight of the frontier-contribution signal ($\alpha_t$) scales linearly from 0 to 1 throughout training. Additionally, the framework uses progress-normalized reward shaping to map heterogeneous task metrics (maximization/minimization) onto a unified scale.

Key Contributions

• Advisor-Based Policy Adaptation: The paper proposes a novel architecture that isolates the trainable decision layer (advisor) from the implementation layer. This allows the system to internalize dynamic search priors (e.g., which mutation families unlock new regions early vs. which refinements yield late-stage gains) while leveraging powerful frontier models for code generation.
• Search-Dynamics-Aware RL Algorithm: The authors design a phase-adaptive RL objective that transitions from group-relative feedback to frontier-contribution credit assignment. This addresses the instability observed in existing methods (like GRPO and entropic objectives) when dealing with small rollout batches and compressed reward landscapes typical of expensive evaluations.
• Empirical Validation: The framework is evaluated across three diverse, real-world machine learning engineering tasks:
  1. Expert-Parallel Load Balancing (EPLB): Optimizing device assignment for Mixture-of-Experts models.
  2. Sequential Recommendation: Evolving a FuXi-linear-style recommender on the KuaiRec dataset.
  3. Protein Fitness Extrapolation: Predicting fitness effects of multi-site mutations (Multi-Evolve benchmark).

Results
Across all three tasks and different model sizes (Qwen3.5-4B and DeepSeek-R1-0528-Qwen3-8B), PACEvolve++ demonstrates superior performance compared to state-of-the-art baselines, including ThetaEvolve (GRPO-based), TTT-Discover (entropic objective), and Max@k (PKPO-based) training.

• Convergence: PACEvolve++ achieves faster convergence and reaches higher final rewards than all baselines.
• Stability: Unlike baselines that exhibit gradient norm spikes (GRPO) or premature entropy collapse (Max@k), PACEvolve++ maintains stable training dynamics with smoother entropy and gradient norms.
• Efficiency: In the EPLB task, PACEvolve++ reaches a near-optimal solution using only half the evolution budget required by the non-RL PACEvolve baseline.

Significance
The paper argues that scaling self-evolving agents to realistic domains requires improving the reasoning policy itself, not just the search scaffold. By decoupling strategic reasoning from implementation and aligning the optimization objective with the intrinsic dynamics of evolutionary search (shifting from exploration to refinement), PACEvolve++ stabilizes test-time training in settings where evaluations are expensive. The work highlights that effective adaptation in long-horizon search requires a policy that can internalize feedback about what to search for, distinct from the capability to implement the search, and that this policy must adapt its learning strategy as the search landscape evolves from diverse to saturated.