ThetaEvolve: Test-time Learning on Open Problems

AI summary

Overview

• Research area: Machine learning — test-time scaling, reinforcement learning (RL) for language models, and LLM-driven evolutionary program search for open mathematical optimization problems.
• Technical level: Advanced. The paper assumes familiarity with LLM inference pipelines, GRPO-style RL training, and program-evolution search.
• Scope in one sentence: The paper introduces ThetaEvolve, an open-source framework that turns AlphaEvolve-style program evolution into a verifiable environment where a single open-source LLM — as small as 8B parameters — can be improved through reinforcement learning at test time to push best-known bounds on open problems.

What This Paper Is About

AlphaEvolve showed that frontier LLM ensembles can evolve programs that improve best-known bounds on open mathematical optimization problems, but it is closed-source, relies on ensembles of large closed models, and never updates the underlying model — its strategies stay trapped in the inference pipeline. ThetaEvolve asks whether a simplified, open-source pipeline with a single small model can both match such results and, more importantly, let the model learn evolving behavior through RL at test time, rather than only executing a fixed search procedure.

Key Contributions

1. An open-source test-time learning pipeline. ThetaEvolve scales test-time compute either purely through inference or through RL on challenging open problems, with simplifications relative to AlphaEvolve/OpenEvolve: a single LLM instead of an ensemble, a much larger program database, batch sampling at each step, optional parent-only prompting, lazy penalties against stagnant outputs, and optional reward shaping.
2. New best-known bounds from a small open-source model. Using DeepSeek-R1-0528-Qwen3-8B (referred to as Distill-Qwen3-8B), ThetaEvolve improves the best-known bounds on two problems considered in AlphaEvolve — circle packing and the first autocorrelation inequality — where previous results came from ensembles such as Gemini-2.0-Flash/Pro.
3. RL at test time consistently beats inference-only. Across two open-source models and four tasks in the main RL comparison, ThetaEvolve with RL outperforms inference-only runs, and RL-trained checkpoints show faster progress and better final scores on both the trained task and unseen tasks, indicating the model internalizes transferable evolutionary capability.
4. Evidence that the learning is real, not cosmetic. Improvements are not reproduced by a format-only reward, and RL in a static environment performs worse than pure inference under ThetaEvolve, while ablations confirm the importance of database size, batch sampling, and reward shaping.

Main Findings

• Bounds improved with an 8B model (Table 1). Circle packing (CP, higher is better): Human 2.634, AlphaEvolve (Gemini-2.0-Flash/Pro) 2.63586276, ShinkaEvolve (Claude-sonnet-4/o4-mini/…) 2.63598283, ThetaEvolve with Distill-Qwen3-8B 2.63598308. First autocorrelation inequality (FACI, lower is better): Human 1.5098, AlphaEvolve 1.503164, ThetaEvolve 1.503133 (ShinkaEvolve's value is not reported in that table).
• Dramatic speed advantage. The circle-packing program discovered by ThetaEvolve takes only 3 seconds to consistently find the same best solution, versus around 75 seconds for the program found by ShinkaEvolve, which uses an ensemble of six advanced closed-source models including Claude-Sonnet-4 and o4-mini (and GPT-4.1).
• RL beats pure inference on every task in the main table (Table 2). Examples: CirclePacking-T (↑) with Distill-Qwen3-8B — w/ RL at step 65: mean 2.6359840, best 2.6359857; w/o RL (early, step 65): mean 2.6354195, best 2.6359831; w/o RL (late, step 100): mean 2.6359541, best 2.6359834. ThirdAutoCorrIneq (↓) with ProRL-1.5B-v2 — initial 3.1586; w/ RL at step 200: mean 1.6412, best 1.6053; w/o RL (early, step 200): mean 1.6831, best 1.6155. HadamardMatrix (↑) with ProRL-1.5B-v2 — initial 0.1433; w/ RL at step 100: mean 0.4808, best 0.5635; w/o RL (early, step 100): mean 0.3264, best 0.4961. SecondAutoCorrIneq (↑) with Distill-Qwen3-8B — initial 0.9055; w/ RL at step 65: mean 0.9444, best 0.9469.
• The RL-trained checkpoint genuinely evolves better. Loading the step-150 checkpoint from the best w/ RL run of ProRL-1.5B-v2 on CirclePacking-T (best score 2.5225), denoted "Load_CP@150", and running pure inference, climbs faster than the original model and attains a better best score, though still slightly worse than the full RL run.
• Evolutionary capability transfers to unseen tasks. The CirclePacking-trained checkpoint, evaluated on unseen tasks, significantly improves average performance relative to the base model, often matching or surpassing w/ RL runs on those tasks, with slight improvements in best performance.
• Static-environment RL fails. RL where every rollout starts from the initial program performs much worse than RL with ThetaEvolve's dynamic environment, and even worse than the pure inference baseline with ThetaEvolve.
• Format reward is not enough (Table 3). On ThirdAutoCorrIneq with ProRL-1.5B-v2: w/o RL mean 1.6766 / best 1.6123; w/ RL mean 1.6412 / best 1.6053; w/ RL with format reward mean 1.6783 / best 1.6744 — worse than pure inference.
• Bigger databases pay off at scale. ThetaEvolve uses population_size = 10000, versus 70 in OpenEvolve (AlphaEvolve does not specify). Ablated configurations: Small (population_size 70, archive_size 25, num_islands 5), Medium (1000, 100, 10), Large (10000, 1000, 10). Smaller databases progress faster at low test-time compute (the Large database needs roughly 10K programs, or about 20 inference steps, before it is fully populated), but larger databases improve diversity and final performance as compute grows.
• Batch sampling makes inference far more efficient (Table 6). On CirclePacking-T with ProRL-1.5B-v2 over 400 inference steps (204.8K new programs) on 4 A6000 GPUs, OpenEvolve took 63.6 hours versus 5.4 hours for ThetaEvolve without RL.
• Test-time compute matters regardless of pipeline (Table 5). On CirclePacking-T with ProRL-1.5B-v2: OpenEvolve at 512 programs gives mean 1.0955 / best 1.2634; OpenEvolve at 307.2k programs gives mean 2.1313 / best 2.1773; ThetaEvolve w/o RL at 307.2k programs gives mean 2.0991 / best 2.2491; ThetaEvolve w/ RL gives mean 2.3498 / best 2.5225. The initial program scores 0.9598.
• Reward shaping needs task-specific tuning (Table 7). On ThirdAutoCorrIneq, ProRL-1.5B-v2 does better with U = 2.5, L = 1.5, α = 1.0 (mean 1.6412, best 1.6053) than with U = 3.2, L = 1.4557, α = 3.0 (mean 1.6535, best 1.6231), while Distill-Qwen3-8B prefers the latter (mean 1.5210, best 1.4930). Distill-Qwen3-8B reaches roughly 1.53–1.57 by step 20, whereas ProRL-1.5B-v2 only reaches 1.8–2.0 at step 20 and never surpasses 1.60.
• Head-to-head with AlphaEvolve on autocorrelation tasks. Starting from AlphaEvolve-v2's provided initial program (score 1.5214) on FirstAutoCorrIneq, Distill-Qwen3-8B finds after around 50 steps a step function whose autoconvolution is highly similar to AlphaEvolve-v2's; the resulting score 1.5068 is worse than the AlphaEvolve-v2 SOTA 1.5032 but better than the previous human SOTA 1.5097. On SecondAutoCorrIneq, ThetaEvolve's 0.9469 is worse than AlphaEvolve-v2's 0.9610 but better than the previous human best 0.9414. When additionally initialized from the AlphaEvolve-v2 SOTA solution, ThetaEvolve still makes slight further improvements.
• Structural differences, not just numbers. Solutions with similar scores can differ qualitatively: on ThirdAutoCorrIneq, the function constructed by Distill-Qwen3-8B is substantially more complex than that of ProRL-1.5B-v2, despite both starting from the same initial program and prompt. ThetaEvolve's circle-packing solution is asymmetric, while AlphaEvolve's is symmetric.

Methodology in Plain English

ThetaEvolve builds on OpenEvolve, an open-source reimplementation of AlphaEvolve. A task is set up by hand: an automatic evaluator scores candidate programs, an initial program shows the expected format, and meta-information describes the problem and hints at promising directions.

From there, the loop works like this. A program database stores previously generated programs and their scores. At each step, the system samples a batch of B = 32 parent programs and writes a prompt for each; each prompt asks the model to modify only its parent program (an optional simplification that keeps prompts short). The model then produces n = 16 responses per prompt, giving B × n child programs per step, which is far more throughput-friendly for batched inference engines such as vLLM or SGLang than AlphaEvolve's one-at-a-time asynchronous requests. Responses are parsed into SEARCH/REPLACE diff blocks and applied to the parent to create child programs.

Before spending time on evaluation, cheap checks assign fixed penalty scores: -0.4 if no diff blocks are found, -0.3 if the change is a no-op, -0.2 if the program produces no solution (compile errors, execution errors, timeouts), and -0.1 if the solution fails validity checks (for example, overlapping circles). A "lazy penalty" additionally punishes any child equivalent (up to comments) to a program already in the database, discouraging the model from resubmitting strong existing solutions.

Because those penalties are exact and automatic, the evaluator acts as a verifiable reward signal, which lets the same loop be used for RL instead of inference alone. Training uses GRPO with asymmetric clipping (clip_low = 0.2, clip_high = 0.28), learning rate 10⁻⁶, weight decay

Authors’ abstract

Recent advances in large language models (LLMs) have enabled breakthroughs in mathematical discovery, exemplified by AlphaEvolve, a closed-source system that evolves programs to improve bounds on open problems. However, it relies on ensembles of frontier LLMs to achieve new bounds and is a pure inference system that models cannot internalize the evolving strategies. We introduce ThetaEvolve, an open-source framework that simplifies and extends AlphaEvolve to efficiently scale both in-context learning and Reinforcement Learning (RL) at test time, allowing models to continually learn from their experiences in improving open optimization problems. ThetaEvolve features a single LLM, a large program database for enhanced exploration, batch sampling for higher throughput, lazy penalties to discourage stagnant outputs, and optional reward shaping for stable training signals, etc. ThetaEvolve is the first evolving framework that enable a small open-source model, like DeepSeek-R1-0528-Qwen3-8B, to achieve new best-known bounds on open problems (circle packing and first auto-correlation inequality) mentioned in AlphaEvolve. Besides, across two models and four open tasks, we find that ThetaEvolve with RL at test-time consistently outperforms inference-only baselines, and the model indeed learns evolving capabilities, as the RL-trained checkpoints demonstrate faster progress and better final performance on both trained target task and other unseen tasks. We release our code publicly: https://github.com/ypwang61/ThetaEvolve