Learning to Discover at Test Time — part 2/5

Cleaned-text code points [15416, 31035). Bibliography omitted here; source.md includes it.

Entropic objective. We define the entropic objective that favors the maximum reward actions: J β ( θ ) = E s ∼ reuse ​ ( ℋ ) [ log E a ∼ π θ ( ⋅ ∣ s ) [ e β ​ ( s ) ​ R ​ ( s , a ) ] ] , J_{\beta}(\theta)=\mathbb{E}_{s\sim\texttt{reuse}(\mathcal{H})}\left[\log\mathbb{E}_{a\sim\pi_{\theta}(\cdot\mid s)}\left[e^{\beta(s)R(s,a)}\right]\right], ∇ θ J β ​ ( θ ) = E s ∼ reuse ​ ( ℋ ) a ∼ π θ ( ⋅ | s ) ​ [ w β ​ ( s ) ​ ( a ) ​ ∇ θ ​ log ⁡ π θ ​ ( a ∣ s ) ] , w β ​ ( s ) ​ ( a ) = e β ​ ( s ) ​ R ​ ( s , a ) E π θ ( ⋅ ∣ s ) [ e β ​ ( s ) ​ R ​ ( s , a ) ] , \nabla_{\theta}J_{\beta}(\theta)=\mathbb{E}_{\begin{subarray}{c}s\sim\texttt{reuse}(\mathcal{H})\\ a\sim\pi_{\theta}(\cdot|s)\end{subarray}}\left[w_{\beta(s)}(a)\nabla_{\theta}\log\pi_{\theta}(a\mid s)\right],\qquad w_{\beta(s)}(a)=\frac{e^{\beta(s)R(s,a)}}{\mathbb{E}_{\pi_{\theta}(\cdot\mid s)}[e^{\beta(s)R(s,a)}]}, where we also shape advantages with a KL penalty: A ⁡ ( a , s ) = w β ​ ( s ) ​ ( a ) − 1 − λ ​ log ⁡ π θ ​ ( a ∣ s ) π θ 0 ​ ( a ∣ s ) A(a;s)=w_{\beta(s)}(a)-1-\lambda\log\frac{\pi_{\theta}(a\mid s)}{\pi_{\theta_{0}}(a\mid s)} Schulman et al. (2017) ; Zhang et al. (2025b) ; Tang and Munos (2025) , and − 1 -1 is the baseline since E ⁡ [ w β ​ ( s ) ] = 1 \mathbb{E}[w_{\beta(s)}]=1 . Concurrent work Jiang et al. (2025) also explored the entropic objective J β J_{\beta} to maximize the pass@k performance for (training-time) RL with binary reward problems.

As β → ∞ \beta\to\infty , the entropic objective tends to the max \max , which is intuitively what we want. However, too large β \beta early in training causes instabilities, while too small later makes advantages vanish as even smaller improvements become harder. Empirically, we found that setting a constant β \beta that works well across different tasks is challenging. Therefore, different than Jiang et al. (2025) , we set β ​ ( s ) \beta(s) adaptively per initial state by constraining the KL divergence of the induced policy; see Appendix A.1 for details.

PUCT. We select initial states using a PUCT-inspired rule Rosin (2011) ; Silver et al. (2016) ; Silver et al. (2017) ; Silver et al. (2018) . Each state s s is scored by Q ⁡ ( s ) + c ⋅ P ⁡ ( s ) ⋅ 1 + T / ( 1 + n ⁡ ( s ) ) Q(s)+c\cdot P(s)\cdot\sqrt{1+T}/(1+n(s)) , where Q ⁡ ( s ) Q(s) is the maximum reward among states generated when the initial state was s s (or R ⁡ ( s ) R(s) if s s has not yet been selected). P ⁡ ( s ) P(s) is proportional to s s ’s rank in the buffer sorted by reward, n ⁡ ( s ) n(s) counts how many times s s or its descendants have been expanded, and T T is the total number of expansions, and c c is the exploration coefficient.

Rather than the mean (as in prior work), we use the maximum reward of children in Q ⁡ ( s ) Q(s) : we care about the best outcome starting from a state, not the average. The prior P ⁡ ( s ) P(s) captures the intuition that high-reward states are more likely to yield high-reward children—e.g., a fast kernel is more likely to seed a faster kernel than a slow one—while the exploration bonus prevents over-exploitation by keeping under-visited states as candidates. See Appendix A.2 for implementation details.

Test-time Training to Discover. With these building blocks, we can introduce our method, TTT-Discover. We combine J β ​ ( s ) J_{\beta(s)} as our (test-time) training objective and PUCT as our reuse routine:

train : θ i + 1 = θ i + η ​ ∇ θ J β ​ ( s i ) ​ ( θ i ) , reuse : s i ∼ PUCT ​ ( ℋ i ) . \texttt{train}:\quad\theta_{i+1}=\theta_{i}+\eta\nabla_{\theta}J_{\beta(s_{i})}(\theta_{i}),\qquad\texttt{reuse}:\quad s_{i}\sim\text{PUCT}(\mathcal{H}_{i}).

### 3.3 Implementation Details

We run TTT-Discover with gpt-oss-120b Agarwal et al. (2025) on Tinker Lab (2025) for 50 50 training steps. We use LoRA Hu et al. (2022) with rank 32 32 . At each step, we generate a batch of 512 512 rollouts, with 8 8 groups of 64 64 rollouts each. Each group of rollouts is generated using the same context and initial state selected from the reuse buffer. We use the entropic objective, and apply importance sampling ratio correction to the gradients due to the sampler/learner mismatch in the RL infrastructure Yao et al. () . We do not take any off-policy steps, i.e., take 1 1 gradient step on the entire batch.

We set the reasoning effort to high. The context window of gpt-oss-120b is limited to 32,768 32,768 tokens on Tinker. Thus, each rollout stops when the context window is exhausted or the LM produces the end of sequence token. In most domains, we limit the total length of the prompt and the thinking tokens to 26000 26000 tokens, so as to leave enough tokens to generate the final response, e.g., to allow generating longer algorithm code. We enforce this by token forcing the model to generate its final response. All hyperparameters reported in Table 9 , and are fixed unless otherwise stated. Assuming an average prompt length of 3000 3000 tokens and 16000 16000 sampling tokens on average, a training run with 50 50 steps and 512 512 rollouts costs around $ 500 \$500 on Tinker.

## 4 Applications

We evaluate TTT-Discover on problems in GPU kernel engineering, mathematics, algorithm design, and biology. We report our performance on every task we attempted. Besides potential impact, we pick domains with 2 criteria. First, we pick domains where we can compare our performance to human experts. This is possible, for example, by comparing to the best submissions in human engineering competitions, or to the best results reported in academic papers. We also want to compare to AI baselines. As we discuss below, mathematics and algorithm design are discovery domains where prior work recently made progress Novikov et al. (2025) ; Georgiev et al. (2025) ; Imajuku et al. (2025) ; Sakana AI (2026) ; Wang et al. (2025a) .

In every application, we report the best known human results and the best known AI results. Importantly, we always report the Best-of- N N baseline that matches the sampling budget and the model that TTT-Discover uses. That is, since we perform 50 50 steps with 512 512 rollouts per step, and compare to the Best-of- 25600 25600 baseline. For a closest evolutionary algorithm baseline, we also run OpenEvolve Sharma (2025) , an open-source version of AlphaEvolve Novikov et al. (2025) , with the same 25600 25600 sampling budget. We use the same context window budget and the Tinker client for gpt-oss-120b throughout the experiments. We caution that the context window limit led to a large number of rollouts in OpenEvolve to be truncated before the model completes its response, as OpenEvolve’s prompts grow very large in length. However, to stay faithful to their implementation, we did not modify their prompts or rollouts.

### 4.1 Mathematics

We explore multiple open problems in mathematics. These are often problems where even small numerical improvements carry real weight, since each result potentially rules out families of approaches and extends the frontier of what is mathematically known. Here, proofs are by construction: one can construct a concrete mathematical object – a step function or a sequence – that certifies, e.g., a bound for an inequality can be achieved. This property makes these problems amenable to search.

Environment: The state s s is a construction. Specifically, a construction is a step function represented as a numerical array, to certify a proof. The action a a consists of thinking tokens followed by Python code that either constructs a new step function or modifies an existing one. The dynamics execute the parsed code to produce the next state: s ′ = Python ​ ( Parse ​ ( a ) ) s^{\prime}=\texttt{Python}(\texttt{Parse}(a)) . The reward is the bound certified by s ′ s^{\prime} , or zero if s ′ s^{\prime} fails validity checks (e.g., the function must satisfy constraints on its support, sign, or integral). Most often, actions involve optimization algorithms to improve the constructions.

Throughout mathematics applications, we initialize the buffer with random states. Specifically, initial states are sampled uniformly at random within the problem’s valid range. For each action, we give a 10-minute limit to execute the code given by the action. In the case of a timeout, the action gets a reward of 0 0 . For minimization problems (certifying upper bounds), we set the reward proportional to 1 / bound 1/{\text{bound}} for the certified bound, and otherwise we set it proportional to bound . We report further details about the environment and the prompts we use in Appendix B .

Previous state-of-the-art. Such problems are recently explored in Georgiev et al. (2025) ; Novikov et al. (2025) . We report both the best known human results, and the recent progress by AI: AlphaEvolve Novikov et al. (2025) , AlphaEvolve V2 Georgiev et al. (2025) which was released around 6 months after AlphaEvolve, ShinkaEvolve Lange et al. (2025) , and ThetaEvolve Wang et al. (2025a) .

We select one representative problem from each area in AlphaEvolve Novikov et al. (2025) : Erdős’ minimum overlap problem (combinatorics), autocorrelation inequalities (analysis), circle packing (geometry).

#### 4.1.1 Erdős’ Minimum Overlap Problem

This is a classic problem in combinatorial number theory, posed by Erdős in 1955, with connections to the distribution of sequences and difference sets. Partition { 1 , 2 , … , 2 ​ n } \{1,2,\ldots,2n\} into two sets A A and B B of equal cardinality n n . Define M k M_{k} as the number of solutions to a i − b j = k a_{i}-b_{j}=k for a i ∈ A , b j ∈ B a_{i}\in A,b_{j}\in B , and let M ⁡ ( n ) = min A , B ⁡ max k ​ M k M(n)=\min_{A,B}\max_{k}M_{k} over all partitions. The problem is to bound c = lim n → ∞ M ⁡ ( n ) / n c=\lim_{n\to\infty}M(n)/n . Bounds before AlphaEvolve were 0.379005 < c < 0.380927 0.379005<c<0.380927 , with the upper bound due to Haugland Haugland (2016) and the lower bound due to White (2023) . AlphaEvolve Novikov et al. (2025) ; Georgiev et al. (2025) improved the upper bound to 0.380924 0.380924 .

Following Novikov et al. (2025) , we optimize step functions f f describing the density of A A throughout [ 1 , 2 ​ n ] [1,2n] . Due to a result of Swinnerton-Dyer Haugland (2016) , density functions yield valid upper bounds on lim M ⁡ ( n ) / n \lim M(n)/n without constructing explicit partitions for large n n . Validity checks require f ⁡ ( x ) ∈ [ 0 , 1 ] f(x)\in[0,1] and ∫ f = 1 \intop\nolimits f=1 .

Results. We improve the upper bound on Erdős’ Minimum Overlap Problem to 0.380876 0.380876 , surpassing AlphaEvolve’s recent construction with 0.380924 0.380924 Novikov et al. (2025) . Our improvement over AlphaEvolve is 16 times larger than AlphaEvolve’s improvement over the previous state-of-the-art. Unlike AlphaEvolve’s symmetric construction, our method discovered a 600-piece asymmetric step function. Surprisingly, the Best-of- 25600 25600 baseline also improved upon the AlphaEvolve construction.

The discovered algorithm minimizes the correlation bound using FFT-accelerated gradient descent combined with random hill climbing and simulated annealing. The code maintains feasibility by projecting onto the constraint set where f ⁡ ( x ) ∈ [ 0 , 1 ] f(x)\in[0,1] with with ∫ f = 1 \intop\nolimits f=1 . Interestingly, the solution found by TTT-Discover is asymmetric.

#### 4.1.2 Autocorrelation Inequalities

Autocorrelation inequalities are motivated by additive combinatorics Barnard and Steinerberger (2020) . Improving these inequalities tightens a constant that propagates into sharper limits on how large a set can be while still avoiding repeated additive patterns (a central theme in additive combinatorics). Similar to the Erdős’ minimum overlap problem, we will construct a step function f f to certify bounds.

First autocorrelation inequality. For nonnegative f f supported on [ − 1 / 4 , 1 / 4 ] [-1/4,1/4] , define C 1 C_{1} as the largest constant such that max | t | ≤ 1 / 2 ⁡ ( f ∗ f ) ​ ( t ) ≥ C 1 ​ ( ∫ f ) 2 \max_{|t|\leq 1/2}(f*f)(t)\;\geq\;C_{1}\Bigl(\intop\nolimits f\Bigr)^{2} holds for all such f f . The goal is to certify the tightest upper bound on C 1 C_{1} ; any valid construction f f certifies C 1 ≤ ‖ f ∗ f ‖ ∞ ‖ f ‖ 1 2 . C_{1}\leq\frac{\|f*f\|_{\infty}}{\|f\|_{1}^{2}}. Until early 2025, the best known upper bound was C 1 ≤ 1.50973 C_{1}\leq 1.50973 Matolcsi and Vinuesa (2010) . AlphaEvolve improved this to C 1 ≤ 1.5053 C_{1}\leq 1.5053 , and AlphaEvolve V2 further improved it to C 1 ≤ 1.50317 C_{1}\leq 1.50317 , and ThetaEvolve refined AlphaEvolve’s construction to get C 1 ≤ 1.50314 C_{1}\leq 1.50314 .

Second autocorrelation inequality. For nonnegative f f , define C 2 = sup f ≥ 0 ‖ f ∗ f ‖ 2 2 ‖ f ∗ f ‖ 1 ​ ‖ f ∗ f ‖ ∞ . C_{2}\;=\;\sup_{f\geq 0}\;\frac{\|f*f\|_{2}^{2}}{\|f*f\|_{1}\,\|f*f\|_{\infty}}. The problem is to certify the tightest known lower bound on C 2 C_{2} ; any valid construction f f with ratio r r certifies C 2 ≥ r C_{2}\geq r . The best human bound was C 2 ≥ 0.8892 C_{2}\geq 0.8892 Matolcsi and Vinuesa (2010) . AlphaEvolve first improved this to C 2 ≥ 0.8962 C_{2}\geq 0.8962 , Boyer and Li (2025) improved this to 0.9015 0.9015 , and AlphaEvolve V2 further improved it to C 2 ≥ 0.9610 C_{2}\geq 0.9610 using a 50,000-piece step function.

Results. We improved the best known upper bound to prove C 1 ≤ 1.50286 C_{1}\leq 1.50286 , with a 30000-piece step function. The comparisons are reported in Table 2 . The previous state-of-the-art, ThetaEvolve, achieved their result by refining the AlphaEvolve V2 construction. In contrast, TTT-Discover found a new construction by starting from scratch. We visualize our and prior works’ step functions in Figure 3 . In the second autocorrelation inequality, we have not made a discovery. Our best construction certified a bound of 0.959 0.959 , where the AlphaEvolve construction had certified a tighter lower bound of 0.961 0.961 .

For the first inequality, early improvements down to 1.510 1.510 came from trying and improving gradient-based optimization (e.g., using Adam with softmax parameterization). To reduce the bound from around 1.510 1.510 to 1.504 1.504 , the policy mostly used linear programming (LP), following the insights in Matolcsi and Vinuesa (2010) . The key insight for the later steps, that gradually achieved the state-of-the-art, was using heuristics to focus optimization only on the constraints that are close to being tight—where each constraint in the LP bounds one position of the convolution. Heuristics included picking the top K positions where the convolution was largest and only including those in the LP, as well as computing gradients from all near-maximum positions rather than just the single largest for gradient-based methods. Unlike AlphaEvolve Georgiev et al. (2025) , which mentions the authors suggested ideas such as using Newton type methods, we never intervened on the optimization process.

For a better comparison to the concurrent work, ThetaEvolve, we also report TTT-Discover with Qwen3-8B Yang et al. (2025) . The Qwen3-8B variant they used, DeepSeek-R1-0528-Qwen3-8B that was released by DeepSeek, is not available on Tinker. Thus, we used the original Qwen model ( Qwen/Qwen3-8B ) that was reportedly worse than the DeepSeek variant. ThetaEvolve reports using 65 65 steps with 512 512 rollouts ( 32 32 groups of 16 16 rollouts) each, however we do not modify our hyperparameters otherwise and keep 50 50 steps of 512 512 rollouts each. For both inequalities, TTT-Discover with Qwen3-8B certified tighter bounds than ThetaEvolve, using a worse model and a smaller sampling budget.

#### 4.1.3 Circle Packing