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

Conference: NeurIPS 2026
arXiv: 2605.07039
OpenReview: https://openreview.net/forum?id=5EofrdzApA
Area: Others
Keywords: Evolutionary Search Agents, Test-Time Learning, Reinforcement Learning, Advisor Models, Search Dynamics Alignment

TL;DR

PACEvolve++ introduces an advisor-model reinforcement learning framework that decouples strategic search reasoning from concrete code implementation and employs a phase-adaptive advantage estimator transitioning from group-relative to frontier-contribution feedback, achieving fast-converging and stable test-time adaptation for evolutionary search agents.

Background & Motivation

Large language models have emerged as powerful drivers of evolutionary program search, demonstrating remarkable success in open-ended optimization problems such as algorithmic discovery, combinatorial optimization, and symbolic regression. In this paradigm, an agent inspects the current best program, its evaluation metrics, and the accumulated search history to propose candidate mutations, retaining higher-scoring descendants across iterative cycles. Modern evolutionary frameworks, such as PACEvolve and AdaEvolve, have significantly boosted search reliability by incorporating advanced scaffold mechanisms, including hierarchical context management, momentum-based backtracking, and collaborative island topologies. Nevertheless, these systems almost universally rely on a fixed-parameter, prompt-elicited policy: valuable search experience accumulates within the external scaffolding, but it is never internalized into the model's actual decision preferences.

This limitation is particularly problematic in practical machine learning engineering and scientific research domains, such as mixture-of-experts (MoE) load balancing, sequential recommendation architecture design, and combinatorial protein fitness extrapolation. In these real-world settings, candidate evaluations are extraordinarily expensive, frequently requiring minutes or hours of GPU training, simulation, or multi-dataset benchmarking; as a result, each rollout step can afford only small candidate batches (e.g., 8 candidates). When existing methods attempt end-to-end reinforcement learning inside the evolutionary loop (such as ThetaEvolve or TTT-Discover), compact open-weight models struggle to handle both high-level search reasoning and complex code realization simultaneously, causing rewards to reflect low-level implementation bugs rather than algorithm quality. Furthermore, long-horizon evolutionary search exhibits a non-stationary log-diminishing reward structure: in early exploration, candidate differences are wide and diverse, making group-relative signals informative; later in refinement, candidates converge near strong parents with compressed score gaps, where GRPO amplifies evaluator noise into severe gradient spikes and entropic objectives prematurely collapse policy diversity.

To resolve these interconnected challenges, this paper decouples strategic search decisions from code implementation and aligns reinforcement learning credit assignment directly with the shifting geometry of evolutionary search dynamics. Core idea: train a compact advisor model dedicated to hypothesis generation and mutation selection while delegating executable code realization to a frozen frontier model, and optimize the advisor via a phase-adaptive advantage objective that transitions credit assignment from group-relative feedback during exploration to leave-one-out frontier-contribution feedback during refinement.

Method

Overall Architecture

The PACEvolve++ workflow tightly integrates the iterative evolutionary search loop, decoupled reasoning-implementation roles, and phase-aware test-time reinforcement learning. At each iteration, the evolutionary environment exposes the current parent program, execution metrics, and recent search history. A trainable compact advisor model first analyzes these inputs to formulate, assess, and select promising mutation hypotheses. A stronger frozen frontier implementation model then translates the selected hypothesis into a clean, executable code patch. The candidate is evaluated within the task-specific verification harness to yield empirical metrics, which update the external evolutionary population. Concurrently, the direction-aware progress reward is computed, and the phase-adaptive advantage objective updates the advisor parameters on-policy before synchronizing with rollout workers for subsequent iterations.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Current Parent Program & History<br/>Code state + metric trajectory"] --> B["1. Advisor-Implementation Decoupling<br/>Compact advisor generates & selects hypotheses"]
    B --> C["Frontier Implementation Model<br/>Realizes hypothesis into executable patch"]
    C --> D["Task Environment Evaluation<br/>Empirical metrics & progress normalization"]
    D --> E["Update Evolutionary Population<br/>Maintain best-of-k frontier"]
    D --> F["3. Progress-Normalized Reward Shaping<br/>Direction-aware mapping to [0, 5] scalar"]
    F --> G["2. Phase-Adaptive Advantage Computation<br/>Dynamic blend of group-relative & frontier-contribution"]
    G --> H["Optimize Advisor Parameters<br/>PPO surrogate loss with asymmetric clipping"]
    H -->|Sync weights| B

Key Designs

1. Advisor-Implementation Decoupling: separating strategic reasoning from low-level coding

In complex engineering tasks, high-level scientific reasoning and low-level code implementation impose drastically different capacity requirements. Training open-weight models (such as 4B to 8B parameter networks) end-to-end to generate complete function-level code modifications often results in frequent syntax or dependency failures, causing the reward signal to entangle implementation fidelity with conceptual hypothesis quality. PACEvolve++ addresses this by restricting reinforcement learning exclusively to a dedicated advisor model. The advisor is tasked solely with strategic evolutionary decisions: diagnosing past failure trajectories, evaluating novelty relative to the existing pool, formulating mutation hypotheses, and selecting promising directions. The concrete implementation of code edits is delegated to an frozen, highly capable frontier model (e.g., Gemini 3.1 Pro Preview). This decoupling isolates the learning of task-specific search priors from the general mechanics of code synthesis, providing clean, noise-free credit assignment for search decisions.

2. Phase-Adaptive Advantage Computation: aligning credit assignment with evolutionary dynamics

Evolutionary search naturally transitions from an early exploratory regime characterized by broad candidate diversity and large score margins to a late refinement regime where candidates are near-neighbor variations of an already strong solution. In small rollout groups (\(N=8\)), static RL objectives fail: GRPO amplifies compressed late-stage score gaps into catastrophic gradient spikes, while Pass@k policy optimization (PKPO) destroys policy entropy too early. PACEvolve++ introduces a linearly scheduled advantage blend over search iterations \(t\). In early exploration (\(\alpha_t \to 0\)), it adopts a raw group-relative baseline without variance denominator to preserve dense exploration signals without division instability: $\(\hat{A}_i^G = R_i - \bar{R}\)$ In late refinement (\(\alpha_t \to 1\)), it transitions smoothly to an unbiased, low-variance leave-one-out marginal-contribution estimator (SLOO) derived from Pass@k policy optimization: $\(\hat{A}_i^{\text{top-k}} = w_i^{\text{SLOO}} = \frac{1}{\binom{N}{k}} \sum_{\substack{I \subseteq \{1,\ldots,N\}\\ |I|=k, \, i \in I}} \left(\max_{j \in I} g_j - \max_{b \in I \setminus \{i\}} g_b\right)\)$ This term assigns positive credit strictly when candidate \(i\) improves the maximum reward of a size-\(k\) subset over the best alternative in that subset. To resolve scale discrepancies between the two estimators, PACEvolve++ standardizes each branch within the current rollout group \(\mathcal{G}_t\): $\(\tilde{A}_i^{(\cdot)} = \frac{\hat{A}_i^{(\cdot)} - \mu_{\mathcal{G}_t}(\hat{A}^{(\cdot)})}{\sigma_{\mathcal{G}_t}(\hat{A}^{(\cdot)}) + \epsilon_{\mathrm{num}}}\)$ yielding the phase-adaptive scalar advantage: $\(A_i^{\text{mix}}(t) = (1 - \alpha_t) \tilde{A}_i^G + \alpha_t \tilde{A}_i^{\text{top-k}}\)$ If the branch standard deviation drops below \(\epsilon_{\text{skip}}\), updates are skipped to prevent fitting numerical noise. Theorem 1 rigorously establishes that under affine reward compression \(g_i(\delta) = c + \delta r_i\), the standardized \(L_2\) norm of both branches remains strictly bounded by \(N\), and the SLOO branch preserves the exact ordering of frontier-changing candidates, ensuring bounded gradients throughout late-stage evolution.

3. Progress-Normalized Reward Shaping: unifying heterogeneous evaluation metrics

Real-world engineering problems feature vastly diverse performance metrics—such as load variance and wall-clock execution speed in distributed systems, ranking NDCG and hit rates in recommender systems, or Pearson correlation in biology—spanning both maximization and minimization objectives. To provide a standardized, scale-invariant learning signal, PACEvolve++ maps arbitrary finite scores \(y\) into a direction-aware normalized progress variable \(u(y)\). For maximization objectives: $\(u(y) = \operatorname{clamp}\left(\frac{y - y_{\min}}{y_{\max} - y_{\min}}, \, 0, \, 1\right)\)$ whereas the numerator is inverted to \(y_{\max} - y\) for minimization tasks. The bounds \(y_{\min}\) and \(y_{\max}\) are determined from the baseline initialization \(y_{\text{init}}\) and predefined target \(y_{\text{target}}\). The final reinforcement learning reward scales progress linearly: $\(R_{\text{RL}}(y) = 5.0 \cdot u(y)\)$ Candidates that crash, encounter compilation errors, or exceed strict execution budgets (e.g., 600s for EPLB or 1,200s for KuaiRec) are assigned an explicit penalty reward of \(R = -1.0\). This transformation eliminates task-specific reward scale tuning and stabilizes surrogate gradient estimation across disparate domains.

Loss & Training

The scalar advantage \(A_i^{\text{mix}}(t)\) computed for rollout response \(i\) is broadcast across all valid response tokens \((i, \tau) \in \mathcal{T}_t\), setting \(A_{i, \tau}^{\text{tok}} = A_i^{\text{mix}}(t)\). The advisor policy \(\pi_\theta\) is trained via a masked clipped surrogate PPO objective incorporating asymmetric clipping thresholds from DAPO to foster exploration of rare but promising tokens: $\(\mathcal{L}(\theta) = -\mathbb{E}_{(i, \tau) \sim \mathcal{T}_t} \left[ \min \left\{ r_{i, \tau}(\theta) A_{i, \tau}^{\text{tok}}, \, \operatorname{clip}(r_{i, \tau}(\theta), \, 1 - \epsilon_{\text{lo}}, \, 1 + \epsilon_{\text{hi}}) A_{i, \tau}^{\text{tok}} \right\} \right]\)$ where \(r_{i, \tau}(\theta) = \frac{\pi_\theta(a_{i, \tau} \mid s_{i, <\tau})}{\pi_{\theta_{\text{old}}}(a_{i, \tau} \mid s_{i, <\tau})}\) is the token importance ratio, with clipping parameters set to \(\epsilon_{\text{lo}} = 0.2\) and \(\epsilon_{\text{hi}} = 0.28\). The optimization is carried out online using AdamW with learning rate \(1 \times 10^{-6}\), weight decay \(0.1\), and one gradient step per rollout batch of \(N=8\) parallel evolutionary threads.

Key Experimental Results

Main Results

PACEvolve++ is evaluated across three challenging machine learning engineering benchmarks: 1. EPLB (Expert-Parallel Load Balancing): Optimizing expert-to-device allocation algorithms under DeepSeek-V3 MoE traces to maximize balancedness and assignment speed. 2. KuaiRec (Sequential Recommendation): Evolving sequence feature encoders and multi-channel mixers for FuXi-Linear recommenders on Kuaishou interaction data, evaluated via full-catalog NDCG, Hit Rate, and MRR. 3. Multi-Evolve (Protein Fitness Extrapolation): Extrapolating combinatorial protein fitness from low-order mutant data, evaluated by Pearson correlation \(r\) and Precision@5 (P@5).

The table below summarizes the disaggregated metrics for the best candidates discovered by DeepSeek-R1-0528-Qwen3-8B (advisor) paired with Gemini-3.1-pro-preview (implementation model):

Task	Metric	PACEvolve++ (Ours)	GRPO (ThetaEvolve)	Max@k (PKPO)	TTT-Discover
EPLB	Balancedness (Bal.)	0.510	0.478	0.458	0.443
EPLB	Speed (1 / Latency)	0.035	0.056	0.080	0.050
KuaiRec	NDCG@10	0.110	0.107	0.104	0.103
KuaiRec	NDCG@50	0.145	0.138	0.136	0.134
KuaiRec	HR@10	0.166	0.159	0.156	0.155
KuaiRec	HR@50	0.327	0.303	0.309	0.302
KuaiRec	MRR	0.104	0.101	0.098	0.097
Multi-Evolve	Pearson \(r\)	0.733	0.688	0.697	0.703
Multi-Evolve	Precision@5	0.452	0.456	0.448	0.415

When evaluated on the smaller Qwen3.5-4B advisor, PACEvolve++ maintains superior performance across all benchmarks: reaching NDCG@10 of 0.102 on KuaiRec (vs. 0.101 for GRPO and 0.073 for TTT-D) and Pearson \(r\) of 0.726 on Multi-Evolve (vs. 0.675 for GRPO and 0.630 for Max@k), proving consistent gains across model scales.

Ablation Study & Training Diagnostics

To isolate the contribution of the phase-adaptive schedule and advantage estimators, training stability diagnostics were tracked across 1,000 evolution steps:

Configuration / Variant	Final Combined Gain	Gradient Norm Stability	Policy Entropy Trajectory	Optimization Behavior
PACEvolve++ (Full Model)	Highest (Fastest SOTA)	Stable in narrow band ~1.0	High initial entropy, smooth decay	Eliminates gradient spikes; balanced exploration & refinement
Pure GRPO (Group-Relative)	Suboptimal	Severe spikes (>4.0 in late stages)	Highly volatile throughout	Reward compression causes late-stage variance explosion
Pure Max@k (PKPO)	Lower	Small gradient norm	Monotonic collapse from 1.0 to <0.4	Over-commits to exploitation too early; loses search diversity
TTT-Discover (Entropic + KL)	Lowest	Irregular volatile jumps	Repeated catastrophic collapses	Over-concentrates on rare outliers under dense reward setups
No-RL Scaffold (PACEvolve)	Near-optimal (needs 2x budget)	N/A (Static prompt policy)	Constant static distribution	Requires full 1,000 steps to match 500-step RL performance

Key Findings

• 2x Convergence Acceleration: On EPLB, while both the non-RL PACEvolve scaffold and PACEvolve++ ultimately discover near-optimal assignment strategies, PACEvolve++ reaches the saturated ceiling within 500 iterations—halving the costly evaluation budget required by prompt-only search.
• Elimination of Gradient and Entropy Pathologies: Auxiliary diagnostic curves demonstrate that GRPO suffers from frequent gradient spikes exceeding 4.0 during late evolution as reward variance diminishes. Max@k suffers premature entropy collapse within 200 iterations. In contrast, PACEvolve++ maintains gradient norms tightly centered around 1.0 and preserves healthy exploration entropy throughout.
• Navigation of Domain-Specific Pareto Frontiers: Disaggregated metrics indicate that different optimization strategies uncover distinct trade-offs (e.g., speed vs. balancedness in EPLB, top-tier precision vs. broad correlation in Multi-Evolve). PACEvolve++ consistently maximizes aggregate progress while uncovering superior overall frontier programs.

Highlights & Insights

• Decoupled Architecture for Practical MLE Evolution: Freeing reinforcement learning from the burden of generating end-to-end bug-free code allows compact open-weight models to specialize purely in scientific hypothesis discovery, while relying on frontier models for robust code synthesis.
• Credit Assignment Geometry Aligned with Search Phases: Recognizes that evolutionary optimization shifts from broad mutation exploration to fine-grained frontier refinement, mathematically pairing scale-conditioned group differences with leave-one-out top-\(k\) frontier contributions.
• Sample-Efficient Adaptation under Expensive Evaluators: Demonstrates that high-capacity test-time policy adaptation can be accomplished with rollout batch sizes as small as \(N=8\), making test-time RL practical for compute-intensive tasks requiring real training runs.

Limitations & Future Work

• Evaluation Budget Constraints: Due to the severe computational cost of executing full model training and multi-hour benchmarks for each candidate, experiments could not be extended beyond 1,000 iterations or replicated across multiple random seeds.
• Reliance on Commercial Frontier Implementers: The system currently relies on proprietary frontier models (Gemini 3.1 Pro Preview) for code realization; future efforts could investigate co-adapting or fine-tuning open-weight code generation models to operate entirely on-premise.
• Linear Phase Scheduling Heuristic: The current mixture schedule \(\alpha_t\) relies on a predetermined linear progression over total search steps; dynamic, performance-aware scheduling based on population stagnation or empirical fitness diversity remains an open direction.

Related Work & Insights

• vs. AlphaEvolve / PACEvolve: Conventional evolutionary coding agents rely exclusively on scaffold engineering (prompting, context compression, memory pools, backtracking) while keeping model weights static; PACEvolve++ directly adapts the search policy at test time via reinforcement learning.
• vs. ThetaEvolve: ThetaEvolve trains a single model end-to-end with GRPO, which suffers from low implementation success rates on complex MLE code and severe gradient spikes during late-stage reward compression; PACEvolve++ decouples code realization and uses phase-adaptive advantage estimation.
• vs. TTT-Discover: TTT-Discover optimizes an entropic objective geared toward single breakthrough discovery, causing rapid entropy collapse on dense continuous metrics; PACEvolve++ preserves steady exploration through standardized group-relative feedback before shifting to frontier contributions.

Rating

• Novelty: ⭐⭐⭐⭐⭐ Decoupling advisor reasoning from frontier code realization and aligning advantage estimation with evolutionary dynamics is both innovative and practically effective.
• Experimental Thoroughness: ⭐⭐⭐⭐☆ Rigorously tested on three demanding, real-world machine learning engineering benchmarks with comprehensive diagnostic curves.
• Writing Quality: ⭐⭐⭐⭐⭐ Well-structured, mathematically sound, and clearly motivated with coherent theoretical and empirical justifications.
• Value: ⭐⭐⭐⭐⭐ Provides an essential paradigm for scaling self-evolving AI agents to computationally expensive scientific and engineering domains.

Related Papers

• [ICLR 2026] EvoTest: Evolutionary Test-Time Learning for Self-Improving Agentic Systems
• [NeurIPS 2026] CLIFT: Conformal Self-Verification for Web Agent Training and Test-Time Scaling
• [NeurIPS 2026] SkillOS: Learning Skill Curation for Self-Evolving Agents
• [NeurIPS 2026] Auto-Dreamer: Learning Offline Memory Consolidation for Language Agents
• [NeurIPS 2026] PROBE: Learning to Audit Policy Compliance in Tool-Using LLM Agents