Self-Evolving Algorithm-Design Agents: Escaping In-Context Evolutionary Stagnation via Population-Curated Policy Optimization

1 Introduction

• Self-evolving algorithm-design agents iteratively design and refine algorithms, and pure in-context evolutionary frameworks have succeeded in areas including combinatorial optimization and mathematical discovery.The introduction cites these as examples of successful applications.Source: §1 · p. 1
• Prior inference-time reinforcement-learning approaches leave population-level reuse of high-quality, diverse self-generated algorithms underexplored, while specialized algorithm-design tasks have few labeled, high-quality algorithms.This motivates learning parametrically from algorithms the agent generates itself.Source: §1 · p. 2
• PCPO outperforms state-of-the-art in-context evolutionary methods across 16 chip cases after training on four, and averages 8.27× speedup over PyTorch Eager on four GPU-kernel cases.It is competitive with GPT-5.5, beating it on training cases while slightly underperforming on testing cases; it also reduces inference-time token cost.Source: §1 · pp. 2–3, Figure 1 · p. 2
• Diagnostic experiments characterize in-context evolutionary stagnation and support the hypothesis that repeatedly using flawed self-generated context can reinforce unproductive generation patterns.The paper describes the diagnostic evidence as consistent with this hypothesis.Source: §1 · p. 2
• PCPO retains and reuses high-quality, diverse self-generated algorithms in a global population, combining exploratory on-policy updates with regularized off-policy updates toward stronger neighbors.The paper presents the off-policy updates as learning elite algorithms and the on-policy updates as supporting exploration and fast correction.Source: §1 · pp. 2–3
• The Improvement Chain is a conditional abstraction: under log-probability closeness and likelihood-gain assumptions, learning a visited algorithm increases a lower-bound change in the likelihood of a neighboring algorithm.The paper uses this local-transfer perspective to motivate PCPO, not as a guarantee of monotonic fitness improvement.Source: §1 · p. 3

2 Background

• A population stores algorithms with information such as execution feedback, balancing the quality and diversity of produced algorithms.The population is represented as algorithm-information pairs, with M denoting population size.Source: §2 · p. 3
• A selection strategy injects context by choosing the references and information considered most important for the agent's current stage.Source: §2 · p. 3
• At each iteration, the method selects reference algorithms and uses guiding operators to prompt new designs, which are evaluated and written back into the population.Operators can include instructions to explore new programs.Source: §2 · p. 3

3 Related Work

• AlphaEvolve uses an island-based MAP-Elites archive to balance program quality and diversity; ShinkaEvolve revises parent selection, novelty rejection, and LLM routing.The evolutionary framework traces back to FunSearch, while EoH and ReEvo extend it to heuristic code.Source: §3 · p. 3
• Off-policy GRPO can recover learning signal when on-policy advantages collapse, but replay-buffer reuse trades off staleness against diversity.The passage notes that buffer management is first-order and that a well-designed buffer can match on-policy accuracy at lower cost.Source: §3 · p. 3
• Self-evolving agents can change their harness, update models using self-generated experience, or select and mutate program populations at test time.The definition encompasses changes to parameters, context, tools, or architecture based on trajectories and feedback.Source: §3 · p. 3

4.1 An Intuitive Analysis of In-Context Evolutionary Stagnation

• In diagnostics, omitting detailed domain knowledge reduced performance on both tasks, and in-context evolution underperformed the base model without improving across generations.The comparisons used the best results within 16 rollouts; “×” marked failure to produce a valid algorithm in all 16 rollouts.Source: §4.1 · p. 4

4.2 Improvement Chain as a motivating abstraction

• The Improvement Chain treats successors as target-directed toward A*, not necessarily fitter, and models neighboring algorithms as short token edits.The target-directed ordering is hypothesized; the proposition concerns local likelihood transfer.Source: §4.2 · pp. 4–5
• Under local log-probability closeness, training on Ai with gain at least ϵℓ yields a successor log-likelihood increase lower-bounded by ϵℓ−2κ∆.The condition uses the smallest training gain along the chain and an upper bound on neighboring log-probability gaps.Source: §4.2 · p. 5
• If successive nodes approach A*, local transfer could facilitate sampling along the chain and shift the task-conditional distribution toward the optimal algorithm.This is a conditional possibility, not a guarantee that an improvement chain exists or will be traversed.Source: §4.2 · pp. 4–5, Figure 3 · p. 5

5 Practical Algorithm: Population-Curated Policy Optimization

• PCPO retains verified elites, curates structural diversity, reinforces candidates off-policy, and samples potential successors on-policy.The chain abstraction motivates this design but does not establish monotonic fitness improvement, chain discovery, or convergence.Source: §5 · pp. 5–6

5.1 Global Population

• The outer archive reuses quality-controlled programs, removing exact duplicates, near-twins without sufficient fitness gains, and invalid code.Near-identical candidates are retained only when their fitness improves on the keeper by a specified margin.Source: §5.1 · p. 6
• Instance-specific buckets prevent mixing reward scales and task difficulties; within each, normalized reward and policy-level novelty rank candidates for elite selection.The bucket ranking combines normalized reward with structural novelty relative to codes recently generated by the policy.Source: §5.1 · pp. 6–7

5.2 Hybrid Policy Update

• Hybrid Policy Update combines fresh GRPO rollouts at every step with a regularized off-policy update every T steps to explore and reuse high-quality experience.Fresh updates provide environmental feedback and anchor the policy to its current rollout distribution; clipping and KL regularization limit off-policy drift.Source: §5.2 · p. 7
• The nonnegative ranking advantage gives stronger elites more reinforcement while keeping every verified Top-k candidate's advantage positive.This avoids the negative feedback standard within-group GRPO may assign to valid but lower-ranked elites.Source: §5.2 · p. 7

6 Experiment

• The evaluation compares Qwen3-8B-based PCPO with in-context evolutionary methods, GRPO, frontier closed-source models, and Codex across global placement and GPU kernel design.Global placement tunes DREAMPlace’s Adam learning-rate schedules to minimize HPWL while meeting target overflow.Source: §6 · p. 7, §6.1 · p. 8

6.1 Global Placement

• PCPO achieves the best average rank across all best@n HPWL metrics on the ISPD 2005 and ICCAD 2015 global-placement benchmarks.The reported best@n metric is the best result within n rollouts.Source: §6.1 · p. 8, Table 1 · p. 8
• Trained on 4 cases, PCPO improves average best@16 HPWL by 1.54% over baseline results across 16 cases, surpasses GPT-4o and Codex, and is comparable to GPT-5.5.PCPO beats GPT-5.5 on training cases, slightly underperforms it on testing cases, and has better results on 10 cases.Source: §6.1 · p. 8, Table 2 · p. 9

6.2 Extended Experiment: GPU Kernel Design

• PCPO achieves the best average rank on the four KernelBench cases evaluated for GPU kernel design.The experiment uses best speedup within the rollout budget as its metric.Source: §6.2 · p. 9, Table 3 · p. 9

• PCPO evolves algorithm-design agents by exploring and training on self-generated algorithms with population experiences.Source: §7 · p. 9
• Across global placement and GPU kernel design, PCPO improves results over state-of-the-art in-context evolutionary methods and remains competitive with frontier closed-source models based on Qwen3-8B.Source: §7 · p. 9
• PCPO reduces inference-time token cost, supporting population-curated parametric self-evolution in these algorithm-design tasks.Source: §7 · p. 9

A Proof

• The proof sets θ=θ_i and θ'=θ_{i+1}, applies Assumption 1, and exponentiates Eq. 7 to obtain Eq. 8.Source: A Proof · p. 13

B.1 Introduction to Global Placement

• Global placement minimizes HPWL subject to a density constraint, while GPU-accelerated DREAMPlace uses optimizers such as Adam and has learning-rate schedules that are difficult to tune.Schedule design requires domain knowledge to balance wire length and cell density; target overflow is 0.07 for ISPD 2005 and 0.1 for ICCAD 2015.Source: §B.1 · p. 14
• Nonlinear placement methods use Lagrangian relaxation, but their runtime limits fast verification on large chips; DREAMPlace and Xplace use GPUs to accelerate gradient descent.Source: §B.1 · p. 14

B.2 Hyperparameters

• On bigblue1, an OpenEvolve trace compounds extra learning-rate decay until the optimizer stalls, unlike the expert schedule’s noncompounding state-dependent adjustment.The trace’s program fails to reach the 0.07 overflow target.Source: Figure 5 · p. 15

B.3.1 Practical examples for diagnostic experiments of in-context evolutionary stagnation

• OpenEvolve traces show compounding decay that stalls placement, reversed HPWL and fitness interpretations, and comparisons between incommensurable gradient and HPWL logs.One trace also emits invalid code using a phantom input in other cases.Source: §B.3.1 · pp. 15–16, Figure 6 · p. 16

B.3.3 Online performance comparison

• With matched 64-rollout budgets, PCPO achieves the best online performance among the compared methods, including OpenEvolve, ShinkaEvolve, ThetaEvolve, and GRPO.The comparison also includes JitRL, which does not achieve great results in this experiment.Source: Table 6 · p. 16, §B.3.3 · p. 17

B.3.2 Practical examples for the Improvement Chain

• At one Qwen3-8B checkpoint, ρℓ=51−2×2.5×10>0; PCPO’s adaptec1 generations also show small edits with progressively better rewards.The likelihood check is described as a limited sanity check for Assumption 1 and Proposition 1.Source: §B.3.2 · p. 16

B.3.3 Online performance comparison

• PCPO outperforms Qwen3-8B equipped with a generalizable skill distilled by GPT-6-Astra from PCPO training logs under a 64-rollout generation budget.Source: §B.3.3 · p. 18

B.3.4 Ablation

• PCPO’s hybrid updates avoid the training-performance degradation observed in GRPO and off-policy GRPO, with the mixed-case curves showing better overall performance.The ablation attributes evidence of effectiveness to both the Regularized Off-policy Update and the Refreshing On-policy Update.Source: §B.3.4 · p. 18, Figure 9 · p. 19, Figure 10 · p. 19
• PCPO outperforms RePO and random replay in the global-population ablation; its population balances sample quality and diversity when selecting promising off-policy candidates.Table 8 covers best@n HPWL results for RePO, Random Replay, and PCPO; lower is better.Source: §B.3.4 · pp. 18–19, Table 8 · p. 20

B.3.5 Reducing token costs

• About 4× fewer total tokens than OpenEvolve and ShinkaEvolve over the same 16 rollouts, while PCPO’s generated programs demonstrate higher quality.The paper attributes the reduction to internalizing domain knowledge and distilling detailed prompts into the weights.Source: §B.3.5 · p. 19, Figure 11 · p. 20

C.1 Introduction to GPU Kernel Design

• GPU kernel design jointly optimizes algorithmic transformation, parallel program construction, and hardware-specific performance tuning for a target accelerator.Kernel implementations map tensor computations onto the accelerator’s parallel execution and memory hierarchy.Source: §C.1 · pp. 20–21

C.2 Experiment Settings

• Speedup is PyTorch Eager wall-clock time divided by generated-kernel time on NVIDIA RTX 4090 GPUs; correctness uses randomized inputs and runtime follows KernelBench’s mean-timing protocol.Each method receives 64 rollouts per case, and Qwen3-8B is the base model for OpenEvolve, ShinkaEvolve, GRPO, and PCPO.Source: §C.2 · p. 21
• The per-task Eager reference is profiled once and frozen, limiting ratio distortion from timing fluctuations and contamination during evaluation.The frozen baseline is hardware-local and shared across methods and seeds.Source: §C.2 · p. 21
• The evaluation reports continuous per-task speedups on four Level-1 cases rather than KernelBench’s thresholded fastp coverage to diagnose optimization quality.The selected cases cover distinct computational structures, including elementwise computation, pointwise computation, structured broadcasting, and multi-input reduction.Source: §C.2 · p. 21

D Cross-Model Experiment

• Gemma4-E4B relies on external domain knowledge rather than intrinsic knowledge to improve performance, and in-context evolutionary stagnation also occurs with this base model.Figure 12 presents diagnostic experiments based on Gemma4-E4B.Source: D Cross-Model Experiment · p. 21, Figure 12 · p. 22
• PCPO based on Gemma4-E4B achieves the best average rank on all best@n metrics across 16 global-placement cases.Table 9 reports best@n HPWL, for which lower is better.Source: D Cross-Model Experiment · p. 21, Table 9 · p. 22