ThetaEvolve: Test-time Learning on Open Problems

1. Introduction

• AlphaEvolve evolves candidate programs by sampling prior high-scoring or diverse programs, prompting an LLM ensemble, evaluating children, and returning them to the database.This process supports continual learning from frontier attempts without unbounded context growth.Source: §1 · pp. 1–2
• AlphaEvolve remains closed-source, generally depends on frontier LLM ensembles, and does not update its underlying model during inference.The authors identify these constraints as leaving learned exploration strategies unavailable to the model itself.Source: §1 · p. 2
• ThetaEvolve builds on RL because deterministic evaluators can verify candidate programs and compute objective values for optimization.The framework applies this combination to open optimization problems with fixed evaluators.Source: §1 · pp. 2–3
• ThetaEvolve is an open-source pipeline for scaling test-time inference or RL using a single LLM, batched parent sampling, a larger program database, lazy penalties, and optional reward shaping.These changes target inference throughput, exploration, stagnant outputs, and stable RL signals.Source: Figure 1 · p. 2, §1 · p. 3
• A single open-source 8B model improved the best-known bounds for circle packing and the first autocorrelation inequality, with circle packing found in 3 seconds versus ShinkaEvolve’s roughly 75 seconds.The comparison is against AlphaEvolve results produced with frontier-model ensembles and ShinkaEvolve’s six-model ensemble.Source: Table 1 · p. 1, §1 · p. 3
• RL with ThetaEvolve consistently outperformed inference-only runs across two open-source models and four challenging problems.RL-trained checkpoints also achieved better scores and faster progress on trained tasks, with improvements transferring to other problems.Source: §1 · p. 3

2. Preliminary: AlphaEvolve Pipeline

• AlphaEvolve requires a manually designed unhackable evaluator, an initial program, and task-specific metadata describing improvement directions.Prompt advice can materially influence final performance.Source: §2 · p. 3
• The program database stores evaluated programs, ranks them by objective score or diversity, and removes entries when the population limit is reached.Its purpose is to resample high-quality or strategically diverse candidates in later generations.Source: §2 · p. 3
• Prompt construction combines task information, prior programs, evaluation scores, and code-replacement instructions before sending the prompt to an LLM ensemble.The ensemble generates reasoning and SEARCH/REPLACE blocks that modify a parent program.Source: §2 · p. 3
• A parser applies generated diff blocks to create child programs, which are evaluated and then re-ranked in the program database.AlphaEvolve uses asynchronous processing because evaluation can become the computational bottleneck.Source: §2 · pp. 3–4

3.1. Direct Adjustment

• ThetaEvolve uses one LLM, a program database of 10000 programs, and optional iterative refinement to simplify evolution while improving exploration and prompt efficiency.The database is much larger than OpenEvolve's 70-program population, while iterative refinement reduces prompt length by sampling only the parent program.Source: §3.1 · p. 4

3.2. Batch Sampling and Generation

• At each step, B parent programs produce n responses each, yielding B × n child programs that improve inference throughput and provide data for RL training.Programs are inserted sequentially and the database is reorganized after each insertion with negligible overhead relative to other system operations.Source: §3.2 · p. 4

3.3. Early Check and Lazy Penalty

• Early checks assign increasingly severe negative penalties to missing diffs, unchanged programs, absent solutions, and invalid solutions before evaluation.No-solution cases include compilation errors, execution errors, and timeouts; invalid solutions fail the evaluator's validity checks.Source: §3.3 · p. 4
• ThetaEvolve additionally penalizes children equivalent to programs already in the database, discouraging lazy repetition when improvements are difficult near best-known results.The equivalence check ignores comments, and unchanged modifications are penalized for RL training.Source: §3.3 · p. 4

3.4. (Optional) RL Reward Shaping

• Optional reward shaping normalizes objective scores into a stable RL signal when narrow score ranges make raw rewards poorly discriminative.For nonnegative scores with shaping enabled, the system applies k · F(s); otherwise it retains s, with manually specified bounds and α controlling the transformation.Source: §3.4 · pp. 4–5

4.1. Setup

• ThetaEvolve evaluates ProRL-1.5B-v2 and Distill-Qwen3-8B on five open mathematical optimization problems using pure inference and RL.The setup includes three random seeds and task-specific evaluators; CirclePacking variants and ThirdAutoCorrIneq use evaluation procedures that differ from AlphaEvolve’s reported setup.Source: §4.1 · p. 5

4.2. Main Result: Scaling with ThetaEvolve

• ThetaEvolve with RL consistently outperforms pure inference across tasks, while Distill-Qwen3-8B improves AlphaEvolve’s CirclePacking result and finds a solution in about 3 seconds versus ShinkaEvolve’s roughly 75 seconds.The main comparison reports mean and best scores across three seeds; the CirclePacking claim remains valid after uniformly shrinking radii by 10^-6.Source: §4.2 · pp. 5–6, Table 2 · p. 6

4.3.1. DOES THE MODEL REALLY LEARN TO EVOLVE?

• RL-trained runs improve programs faster and reach better final performance than inference-only runs, while similarly scored solutions can differ substantially in structure and complexity.On ThirdAutoCorrIneq, ProRL-1.5B-v2 scores around 1.6 and Distill-Qwen3-8B around 1.5, with the latter producing a substantially more complex function.Source: §4.3.1 · p. 6, §4.2 · p. 6, Figure 2 · p. 7
• The step-150 RL-trained checkpoint improves pure-inference progress and best score over the original model, although it remains slightly below the full RL run.The result indicates that RL updates model parameters in ways that benefit program evolution.Source: §4.3.1 · p. 6, Figure 3 · p. 8
• A CirclePacking-trained RL checkpoint improves average and sometimes best performance on unseen tasks, suggesting transfer of evolution capability beyond the training task.The checkpoint often matches or surpasses the w/ RL runs on unseen tasks.Source: §4.3.1 · p. 7, Figure 3 · p. 8

4.3.2. COMPARISON WITH CONVENTIONAL RL TRAINING

• RL with ThetaEvolve’s dynamic environment substantially outperforms RL from a static initial-program environment and even beats ThetaEvolve pure inference.The authors attribute the gap to the need for incremental improvement trajectories because directly sampling advanced programs is extremely unlikely.Source: §4.3.2 · p. 7, Figure 4 · p. 8

4.3.3. FORMAT REWARD

• Format-only reward is ineffective on ThirdAutoCorrIneq and performs worse than pure inference, whereas ground-truth evaluator rewards improve evolution.The baseline rewards outputs whose program scores avoid two format-related values, while runtime and validity failures receive other error scores.Source: §4.3.3 · p. 8, Table 3 · p. 8

4.4.1. SCALING DATABASE FOR COLLABORATING WITH SCALING TEST-TIME COMPUTE

• Increasing database size improves long-run evolutionary performance, especially as test-time compute grows, because larger databases preserve greater candidate diversity.Small databases can progress faster initially through more frequent sampling of high-scoring programs, but provide limited additional improvement when compute is scaled.Source: §4.4.1 · p. 9, Figure 5 · p. 9

• Prompt-optimization and evolutionary program-search systems maintain experience in context, but their underlying LLMs generally do not internalize the discovered capabilities.Source: §5 · p. 10
• Figure 6 shows that without RL ThetaEvolve can surpass the previous human SOTA on FirstAutoCorrIneq, while AlphaEvolve-v2 remains better and initialization from its solution enables slight further improvement.Source: Figure 6 · p. 11
• ThetaEvolve applies RL to an AlphaEvolve-style program-evolution pipeline viewed as an adaptive verifiable environment for continuous-reward objectives.Source: §5 · p. 11
• AlphaEvolve uses an ensemble of frontier LLMs to iteratively modify programs from a program database, whereas ThetaEvolve is motivated by adapting this structure with RL.Source: §5 · p. 11

• ThetaEvolve and AlphaEvolve apply broadly to optimization problems with continuous rewards beyond open mathematical problems.Source: §6 · p. 11
• Observed task transfer suggests training across multiple target instances or entirely different tasks may be possible.Source: §6 · p. 11
• Continual learning may require dynamic environments that co-evolve with the model, leaving substantial room for improving exploration and optimization.Source: §6 · p. 11

A.1. Circle Packing

• CirclePacking maximizes the sum of radii for n disjoint circles inside a unit square; for n = 26, prior bounds progressed from 2.634 to 2.635983283 across earlier systems.The paper distinguishes tolerance-based CirclePacking-T from the strict atol = 0 formulation because different evaluators define slightly different optimization problems.Source: §A.1 · p. 14

A.2. First Autocorrelation Inequality

• FirstAutoCorrIneq seeks the largest constant C1 satisfying the inequality for all non-negative functions, with bounds connected to additive combinatorics and step-function constructions.AlphaEvolve-v2 used 600 evenly spaced intervals over [−1/4, 1/4] for its step-function construction.Source: §A.2 · p. 14

A.3. Second Autocorrelation Inequality

• SecondAutoCorrIneq seeks the smallest constant C2, with prior improvements obtained from step functions and gradient-based methods, including a 50,000-piece AlphaEvolve-v2 construction.AlphaEvolve-v2 describes that construction as highly irregular and difficult to optimize or visualize.Source: §A.3 · pp. 14–15

A.4. Third Autocorrelation Inequality

• ThirdAutoCorrIneq uses an evaluator whose implementation differs from the mathematical formulation, so the paper's corrected bounds are not directly comparable to AlphaEvolve's reported 1.4581 and 1.4557.The discrepancy reflects two closely related but distinct optimization problems, and the paper uses the theoretically correct expression.Source: §A.4 · p. 15

A.5. Hadamard matrix

• A Hadamard matrix is an n × n ±1 matrix satisfying H H^T = nI, and the n = 29 task maximizes its determinant subject to the classical upper bound.The paper computes the objective for n = 29 as s = |det(H)| 228 × 712 × 342.Source: §A.5 · p. 15

B. Details of ThetaEvolve

• ThetaEvolve penalizes invalid changes and database duplicates to discourage stagnant outputs, while reward normalization can stabilize training when objective values occupy narrow ranges.These implementation choices support RL in settings where most modifications do not improve already strong solutions.Source: B. Details of ThetaEvolve · p. 16

B.1. More Implementation Details

• The verifier separates validity checking, objective scoring, and solution files in an immutable evaluator, while lazy penalties compare outputs against all historical programs.These mechanisms target reward hacking and memorization of previously successful database programs.Source: §B.1 · p. 16
• ThetaEvolve samples multiple fixed meta-information entries by weight, replacing OpenEvolve’s two-stage setup with a unified strategy-mixture prompt.Each entry describes a different strategy and remains unevolved during generation.Source: §B.1 · p. 16

B.2. Parameters in ThetaEvolve

• Reward shaping is mainly applied to narrow-score or minimization tasks, while ThirdAutoCorrIneq uses L = 1.4557 from AlphaEvolve and task-dependent α values of 3 or 1.The α = 3 setting is used for Distill-Qwen3-8B and α = 1 for ProRL-1.5B-v2.Source: §B.2 · p. 16

B.3. Details of Meta Information

• Meta-information is reused from OpenEvolve or AlphaEvolve-v2 when available, while GPT-5 and Claude 4.5 generate insights for the remaining tasks rather than advanced programs.All runs use the same task prompt for fair comparison, and initial programs are generally simple and far from best-known bounds.Source: §B.3 · pp. 16–17

B.3.1. PROMPT OF CIRCLEPACKING-T

• CirclePacking-T uses two prompt components: one asks for an explicit constructor producing a specific arrangement of 26 circles in a unit square, while the other seeks significant improvements toward AlphaEvolve’s target value 2.635.The optimization prompt highlights variable-sized circles, edge effects, corner and edge placement, and larger central circles with smaller edge circles.Source: §B.3.1 · p. 17

B.3.2. PROMPT OF FIRSTAUTOCORRINEQ

• FirstAutoCorrIneq prompts the model to search non-negative coefficient sequences under a fixed evaluator and runtime, while preserving AlphaEvolve-v2’s formulation and constraints.The search function must return the best sequence within the time limit, or receive negative-infinity points if it returns nothing.Source: §B.3.2 · p. 18

B.3.3. PROMPT OF SECONDAUTOCORRINEQ

• SecondAutoCorrIneq uses three weighted components: constructive spike-envelope-comb ansätze, peak-aware optimization, and lightweight structural exploration under short evaluation budgets.The optimization component uses Top-k smooth maxima, Toeplitz-aware preconditioning, mirror descent, and local multi-resolution; exploration adds frequency shaping, beat-pattern plateaus, and budget-aware gating.Source: §B.3.3 · pp. 18–20

B.3.4. PROMPT OF THIRDAUTOCORRINEQ

• ThirdAutoCorrIneq combines a literature-grounded window-times-oscillation construction, targeted local refinement, and radical exploration through wavelets, fractals, chirps, splines, and algebraic structures.Refinement uses adaptive perturbations, convolution-peak targeting, simulated-annealing escapes, and sign flipping to reduce autocorrelation peaks.Source: §B.3.4 · pp. 20–21
• The third autocorrelation prompt explicitly prioritizes diverse, unconventional candidates and drastic mathematical shifts over replicating similar prior programs.Source: §B.3.4 · p. 21

B.3.5. PROMPT OF HADAMARDMATRIX

• The Hadamard prompts target maximizing |det(H)| / theoretical_max under bounded runtime, combining local and global search, algebraic constructions, parallelism, diagnostics, and robust output handling.They encourage techniques including conference and finite-field constructions, simulated annealing, multi-scale optimization, memory-guided search, evolutionary methods, and efficient O(n^2) determinant updates.Source: §B.3.5 · pp. 22–24

C. Details of AlphaEvolve/OpenEvolve Pipeline

• The AlphaEvolve/OpenEvolve pipeline requires a scalar evaluator, an initial program with an #EVOLVE-BLOCK-START/#EVOLVE-BLOCK-END region, and meta-information describing the problem and improvement directions.The evaluator must handle corner cases to prevent loophole exploitation, while OpenEvolve and this work do not support AlphaEvolve’s meta-prompt evolution.Source: §C.1 · p. 24

C.1. Meta Information and Initial Program

• Prompt advice can materially influence performance, so the pipeline’s meta-information specifies the problem and possible ways to improve existing bounds.Source: §C.1 · p. 24

C.2. LLM Ensemble

• AlphaEvolve uses frontier LLMs and ensembles to balance evolutionary performance with computational throughput, with outputs typically containing CoT reasoning and SEARCH/REPLACE diffs.ShinkaEvolve (Lange et al., 2025) further emphasizes ensembles and specialized model selection strategies.Source: §C.2 · pp. 24–25

C.3. Global Best Solution

• OpenEvolve and this work do not maintain AlphaEvolve’s global best solution, although adding it may improve bounds under the same time budget for search-heavy tasks.Global-best reuse may instead reduce diversity when the initial referenced solution is already strong and the meta-prompt is simple, causing only small perturbations to the SOTA solution.Source: §C.3 · p. 25

C.4. Evolutionary Database

• The database combines island-based evolution with MAP-Elites-style feature bins to retain diverse programs across relatively independent populations.AlphaEvolve’s database is described as drawing on MAP-Elites and island-based population models.Source: §C.4 · p. 25

C.4.1. ADD AND REPLACE

• New programs inherit their parent’s island, compete within discretized feature-grid cells by fitness, and enter an elite archive for exploitation-based sampling.A candidate replaces an occupied cell only when it has higher fitness than the incumbent.Source: §C.4.1 · p. 25

C.4.2. DATABASE CAPACITY MANAGEMENT

• When the population exceeds its limit, the system removes the lowest-fitness programs while preserving the global best and most recently added program.This cleanup controls memory usage and maintains stable selection pressure.Source: §C.4.2 · p. 25

C.4.3. INTER-ISLAND MIGRATION

• Periodic migration copies a small fraction of top programs between neighboring islands, where MAP-Elites selection retains them only if they improve fitness.Source: §C.4.3 · p. 25

D. Discussions: Limitations of RLVR on Challenging Problems

• Static-environment RL makes advanced program P extremely unlikely to be sampled from the same initial state, producing sparse rewards.The discussion assumes P has probability ϵθ ≪1 under the initial context and program.Source: D. Discussions: Limitations of RLVR on… · pp. 25–26
• Dynamic evolutionary RL samples intermediate programs from successive database states, providing richer training signals than directly sampling the final advanced program.The intermediate probabilities are estimated as Θ(logN(ϵθ)) ≫ϵθ.Source: D. Discussions: Limitations of RLVR on… · p. 26
• As RL training increases the intermediate sampling probabilities ϵθ,i, it also improves the probability ϵθ of sampling the final advanced program P.Source: D. Discussions: Limitations of RLVR on… · p. 26

E.1. Main Experiments

• The full results of the main experiments are presented in Table 9.Source: §E.1 · p. 26
• The section identifies these experiments as the paper’s main experimental results.Source: §E.1 · p. 26
• Table 9 is the referenced location for the complete main-experiment results.Source: §E.1 · p. 26

E.2. Analysis of Discovered Program

• w/ RL consistently outperforms w/o RL baselines with proper reward shaping, while both improve the initial program across models and tasks.Table 9 reports means and best values over three seeds for maximization and minimization tasks.Source: Table 9 · p. 27
• The evolved program replaces heuristic geometry construction with SLSQP-based constrained optimization that maximizes the sum of circle radii under geometric constraints.This formulation introduces explicit non-overlap and boundary constraints to maintain feasible configurations during optimization.Source: §E.2 · p. 28
• For n=26, hexagonal-lattice initialization with dynamic centering approximates dense packing and improves convergence for benchmark cases.The implementation also adds solver tolerances and fallback strategies for robustness during large-scale or batch RL execution.Source: §E.2 · p. 28
• The modular design can incorporate gradient information and potentially support hybrid RL–SLSQP training loops.The passage identifies objective_jac integration as a future performance-optimization direction.Source: §E.2 · p. 28

E.3. More Visualizations

• Figures 7–10 provide performance curves for CirclePacking-T, ThirdAutoCorrIneq, SecondAutoCorrIneq, and HadamardMatrix.The supplied captions identify the task and optimization direction for each curve but do not report numerical outcomes.Source: Figure 7 · p. 29, Figure 8 · p. 29, Figure 9 · p. 29
• In Fig. 11, ThetaEvolve’s best circle-packing solution differs from AlphaEvolve’s: although the configurations look very similar, ThetaEvolve’s is clearly asymmetric, whereas AlphaEvolve’s appears almost symmetric.Source: §E.3 · p. 29

E.4. Ablation of Database Management

• Simplifying the program database to one island, one score-only feature dimension, and one MAP-Elites bin noticeably weakens evolutionary performance.The ablation uses a vanilla priority queue that depends only on objective scores and is evaluated on CirclePacking-T with ProRL-1.5B-v2.Source: §E.4 · p. 29, Table 10 · p. 30